From c6c9fc53ac3212df8dfb582247ce6d5f8eb17389 Mon Sep 17 00:00:00 2001 From: David Devecsery Date: Mon, 18 May 2020 10:27:54 -0400 Subject: [PATCH] Got string library updated so stab compiles, now have stab info integrated --- include/types.h | 2 + kernel/Sources.cmake | 1 + kernel/include/buf.h | 4 + kernel/include/date.h | 5 + kernel/include/defs.h | 9 -- kernel/include/stab.h | 69 +++++++++++++ kernel/include/string.h | 28 ++++++ kernel/src/console.c | 1 + kernel/src/exec.c | 1 + kernel/src/fs.c | 1 + kernel/src/kalloc.c | 1 + kernel/src/lapic.c | 1 + kernel/src/log.c | 1 + kernel/src/main.c | 1 + kernel/src/mp.c | 1 + kernel/src/proc.c | 1 + kernel/src/stab.c | 209 ++++++++++++++++++++++++++++++++++++++++ kernel/src/string.c | 14 +++ kernel/src/sysfile.c | 1 + kernel/src/vm.c | 1 + 20 files changed, 343 insertions(+), 9 deletions(-) create mode 100644 kernel/include/stab.h create mode 100644 kernel/include/string.h create mode 100644 kernel/src/stab.c diff --git a/include/types.h b/include/types.h index 97bff57..94507eb 100644 --- a/include/types.h +++ b/include/types.h @@ -1,6 +1,8 @@ #ifndef INCLUDE_TYPES_h_ #define INCLUDE_TYPES_h_ +typedef unsigned long size_t; + typedef unsigned int uint; typedef unsigned short ushort; typedef unsigned char uchar; diff --git a/kernel/Sources.cmake b/kernel/Sources.cmake index 78ce385..cb6d6cc 100644 --- a/kernel/Sources.cmake +++ b/kernel/Sources.cmake @@ -28,6 +28,7 @@ set(kernel_SOURCES src/proc.c src/sleeplock.c src/spinlock.c + src/stab.c src/string.c src/syscall.c src/sysfile.c diff --git a/kernel/include/buf.h b/kernel/include/buf.h index 3266495..d3ece22 100644 --- a/kernel/include/buf.h +++ b/kernel/include/buf.h @@ -1,3 +1,6 @@ +#ifndef KERNEL_INCLUDE_BUF_h_ +#define KERNEL_INCLUDE_BUF_h_ + struct buf { int flags; uint dev; @@ -12,3 +15,4 @@ struct buf { #define B_VALID 0x2 // buffer has been read from disk #define B_DIRTY 0x4 // buffer needs to be written to disk +#endif // KERNEL_INCLUDE_BUF_h_ diff --git a/kernel/include/date.h b/kernel/include/date.h index 94aec4b..ac6eb8d 100644 --- a/kernel/include/date.h +++ b/kernel/include/date.h @@ -1,3 +1,6 @@ +#ifndef KERNEL_INCLUDE_DATE_h_ +#define KERNEL_INCLUDE_DATE_h_ + struct rtcdate { uint second; uint minute; @@ -6,3 +9,5 @@ struct rtcdate { uint month; uint year; }; + +#endif // KERNEL_INCLUDE_DATE_h_ diff --git a/kernel/include/defs.h b/kernel/include/defs.h index 82fb982..f1f20fd 100644 --- a/kernel/include/defs.h +++ b/kernel/include/defs.h @@ -139,15 +139,6 @@ void releasesleep(struct sleeplock*); int holdingsleep(struct sleeplock*); void initsleeplock(struct sleeplock*, char*); -// string.c -int memcmp(const void*, const void*, uint); -void* memmove(void*, const void*, uint); -void* memset(void*, int, uint); -char* safestrcpy(char*, const char*, int); -int strlen(const char*); -int strncmp(const char*, const char*, uint); -char* strncpy(char*, const char*, int); - // syscall.c int argint(int, int*); int argptr(int, char**, int); diff --git a/kernel/include/stab.h b/kernel/include/stab.h new file mode 100644 index 0000000..1c5aaf5 --- /dev/null +++ b/kernel/include/stab.h @@ -0,0 +1,69 @@ +#ifndef KERNEL_INCLUDE_STAB_h_ +#define KERNEL_INCLUDE_STAB_h_ + +#include "types.h" + +// STABS debugging info + +// The XV6 kernel debugger can understand some debugging information +// in the STABS format. For more information on this format, see +// http://sourceware.org/gdb/onlinedocs/stabs.html + +// The constants below define some symbol types used by various debuggers +// and compilers. XV6 uses the N_SO, N_SOL, N_FUN, and N_SLINE types. + +#define N_GSYM 0x20 // global symbol +#define N_FNAME 0x22 // F77 function name +#define N_FUN 0x24 // procedure name +#define N_STSYM 0x26 // data segment variable +#define N_LCSYM 0x28 // bss segment variable +#define N_MAIN 0x2a // main function name +#define N_PC 0x30 // global Pascal symbol +#define N_RSYM 0x40 // register variable +#define N_SLINE 0x44 // text segment line number +#define N_DSLINE 0x46 // data segment line number +#define N_BSLINE 0x48 // bss segment line number +#define N_SSYM 0x60 // structure/union element +#define N_SO 0x64 // main source file name +#define N_LSYM 0x80 // stack variable +#define N_BINCL 0x82 // include file beginning +#define N_SOL 0x84 // included source file name +#define N_PSYM 0xa0 // parameter variable +#define N_EINCL 0xa2 // include file end +#define N_ENTRY 0xa4 // alternate entry point +#define N_LBRAC 0xc0 // left bracket +#define N_EXCL 0xc2 // deleted include file +#define N_RBRAC 0xe0 // right bracket +#define N_BCOMM 0xe2 // begin common +#define N_ECOMM 0xe4 // end common +#define N_ECOML 0xe8 // end common (local name) +#define N_LENG 0xfe // length of preceding entry + +// Entries in the STABS table are formatted as follows. +struct stab { + uint n_strx; // index into string table of name + uchar n_type; // type of symbol + uchar n_other; // misc info (usually empty) + ushort n_desc; // description field + uint n_value; // value of symbol +}; + +// Debug information about a particular instruction pointer +struct stab_info { + const char *eip_file; // Source code filename for EIP + int eip_line; // Source code linenumber for EIP + + const char *eip_fn_name; // Name of function containing EIP + // - Note: not null terminated! + int eip_fn_namelen; // Length of function name + uint eip_fn_addr; // Address of start of function + int eip_fn_narg; // Number of function arguments +}; + + +// Populates info to contain the stab_info about the given eip. +// Returns 0 on success, non-zero on failure. +int stab_info(uint eip, struct stab_info *info); + +#endif // KERNEL_INCLUDE_STAB_h_ + diff --git a/kernel/include/string.h b/kernel/include/string.h new file mode 100644 index 0000000..8326583 --- /dev/null +++ b/kernel/include/string.h @@ -0,0 +1,28 @@ +#ifndef KERNEL_INCLUDE_STRING_h_ +#define KERNEL_INCLUDE_STRING_h_ + +#include "types.h" + +int strlen(const char *s); +int strnlen(const char *s, size_t size); +char *strcpy(char *dst, const char *src); +//char * strncpy(char *dst, const char *src, size_t size); +char *strcat(char *dst, const char *src); +size_t strlcpy(char *dst, const char *src, size_t size); +int strcmp(const char *s1, const char *s2); +int strncmp(const char *s1, const char *s2, size_t size); +char *strchr(const char *s, char c); +char *strfind(const char *s, char c); + +void *memset(void *dst, int c, size_t len); +void *memcpy(void *dst, const void *src, size_t len); +void *memmove(void *dst, const void *src, size_t len); +int memcmp(const void *s1, const void *s2, size_t len); +void *memfind(const void *s, int c, size_t len); + +long strtol(const char *s, char **endptr, int base); + +char *safestrcpy(char *s, char *t, int n); +char *strncpy(char *s, const char *t, int n); + +#endif // KERNEL_INCLUDE_STRING_h_ diff --git a/kernel/src/console.c b/kernel/src/console.c index 7dd649d..d8a1d9e 100644 --- a/kernel/src/console.c +++ b/kernel/src/console.c @@ -15,6 +15,7 @@ #include "memlayout.h" #include "mmu.h" #include "proc.h" +#include "string.h" static void consputc(int); diff --git a/kernel/src/exec.c b/kernel/src/exec.c index 3cde317..42a1d6d 100644 --- a/kernel/src/exec.c +++ b/kernel/src/exec.c @@ -7,6 +7,7 @@ #include "proc.h" #include "defs.h" #include "elf.h" +#include "string.h" int exec(char *path, char **argv) diff --git a/kernel/src/fs.c b/kernel/src/fs.c index f77275f..0bd4a0c 100644 --- a/kernel/src/fs.c +++ b/kernel/src/fs.c @@ -20,6 +20,7 @@ #include "fs.h" #include "buf.h" #include "file.h" +#include "string.h" #define min(a, b) ((a) < (b) ? (a) : (b)) static void itrunc(struct inode*); diff --git a/kernel/src/kalloc.c b/kernel/src/kalloc.c index 14cd4f4..45f0aef 100644 --- a/kernel/src/kalloc.c +++ b/kernel/src/kalloc.c @@ -8,6 +8,7 @@ #include "memlayout.h" #include "mmu.h" #include "spinlock.h" +#include "string.h" void freerange(void *vstart, void *vend); extern char end[]; // first address after kernel loaded from ELF file diff --git a/kernel/src/lapic.c b/kernel/src/lapic.c index bacc192..1bfe6bd 100644 --- a/kernel/src/lapic.c +++ b/kernel/src/lapic.c @@ -9,6 +9,7 @@ #include "memlayout.h" #include "traps.h" #include "mmu.h" +#include "string.h" // Local APIC registers, divided by 4 for use as uint[] indices. #define ID (0x0020/4) // ID diff --git a/kernel/src/log.c b/kernel/src/log.c index a64c0f6..a940fca 100644 --- a/kernel/src/log.c +++ b/kernel/src/log.c @@ -5,6 +5,7 @@ #include "sleeplock.h" #include "fs.h" #include "buf.h" +#include "string.h" // Simple logging that allows concurrent FS system calls. // diff --git a/kernel/src/main.c b/kernel/src/main.c index 43c722d..6b6d639 100644 --- a/kernel/src/main.c +++ b/kernel/src/main.c @@ -7,6 +7,7 @@ #include "memlayout.h" #include "mmu.h" #include "proc.h" +#include "string.h" static void startothers(void); static void mpmain(void) __attribute__((noreturn)); diff --git a/kernel/src/mp.c b/kernel/src/mp.c index 1caec8e..cc48ac3 100644 --- a/kernel/src/mp.c +++ b/kernel/src/mp.c @@ -10,6 +10,7 @@ #include "mp.h" #include "mmu.h" #include "proc.h" +#include "string.h" struct cpu cpus[NCPU]; int ncpu; diff --git a/kernel/src/proc.c b/kernel/src/proc.c index aa52660..90f286b 100644 --- a/kernel/src/proc.c +++ b/kernel/src/proc.c @@ -6,6 +6,7 @@ #include "mmu.h" #include "proc.h" #include "spinlock.h" +#include "string.h" struct { struct spinlock lock; diff --git a/kernel/src/stab.c b/kernel/src/stab.c new file mode 100644 index 0000000..5c1e505 --- /dev/null +++ b/kernel/src/stab.c @@ -0,0 +1,209 @@ +#include "stab.h" +#include "memlayout.h" +#include "defs.h" +#include "string.h" + +extern const struct stab __STAB_BEGIN__[]; // Beginning of stabs table +extern const struct stab __STAB_END__[]; // End of stabs table +extern const char __STABSTR_BEGIN__[]; // Beginning of string table +extern const char __STABSTR_END__[]; // End of string table + + +// stab_binsearch(stabs, region_left, region_right, type, addr) +// +// Some stab types are arranged in increasing order by instruction +// address. For example, N_FUN stabs (stab entries with n_type == +// N_FUN), which mark functions, and N_SO stabs, which mark source files. +// +// Given an instruction address, this function finds the single stab +// entry of type 'type' that contains that address. +// +// The search takes place within the range [*region_left, *region_right]. +// Thus, to search an entire set of N stabs, you might do: +// +// left = 0; +// right = N - 1; /* rightmost stab */ +// stab_binsearch(stabs, &left, &right, type, addr); +// +// The search modifies *region_left and *region_right to bracket the +// 'addr'. *region_left points to the matching stab that contains +// 'addr', and *region_right points just before the next stab. If +// *region_left > *region_right, then 'addr' is not contained in any +// matching stab. +// +// For example, given these N_SO stabs: +// Index Type Address +// 0 SO f0100000 +// 13 SO f0100040 +// 117 SO f0100176 +// 118 SO f0100178 +// 555 SO f0100652 +// 556 SO f0100654 +// 657 SO f0100849 +// this code: +// left = 0, right = 657; +// stab_binsearch(stabs, &left, &right, N_SO, 0xf0100184); +// will exit setting left = 118, right = 554. +// +/** + * @param stabs -- the stab array + * binsearh documentation + */ +static void +stab_binsearch(const struct stab *stabs, int *region_left, int *region_right, + int type, uint addr) +{ + int l = *region_left, r = *region_right, any_matches = 0; + + while (l <= r) { + int true_m = (l + r) / 2, m = true_m; + + // search for earliest stab with right type + while (m >= l && stabs[m].n_type != type) + m--; + if (m < l) { // no match in [l, m] + l = true_m + 1; + continue; + } + + // actual binary search + any_matches = 1; + if (stabs[m].n_value < addr) { + *region_left = m; + l = true_m + 1; + } else if (stabs[m].n_value > addr) { + *region_right = m - 1; + r = m - 1; + } else { + // exact match for 'addr', but continue loop to find + // *region_right + *region_left = m; + l = m; + addr++; + } + } + + if (!any_matches) + *region_right = *region_left - 1; + else { + // find rightmost region containing 'addr' + for (l = *region_right; + l > *region_left && stabs[l].n_type != type; + l--) + /* do nothing */; + *region_left = l; + } +} + + +// stab_info(addr, info) +// +// Fill in the 'info' structure with information about the specified +// instruction address, 'addr'. Returns 0 if information was found, and +// negative if not. But even if it returns negative it has stored some +// information into '*info'. +// +int +stab_info(uint addr, struct stab_info *info) +{ + const struct stab *stabs, *stab_end; + const char *stabstr, *stabstr_end; + int lfile, rfile, lfun, rfun, lline, rline; + + // Initialize *info + info->eip_file = ""; + info->eip_line = 0; + info->eip_fn_name = ""; + info->eip_fn_namelen = 9; + info->eip_fn_addr = addr; + info->eip_fn_narg = 0; + + // Find the relevant set of stabs + if (addr >= KERNBASE) { + stabs = __STAB_BEGIN__; + stab_end = __STAB_END__; + stabstr = __STABSTR_BEGIN__; + stabstr_end = __STABSTR_END__; + } else { + // Can't search for user-level addresses yet! + panic("User address"); + } + + // String table validity checks + if (stabstr_end <= stabstr || stabstr_end[-1] != 0) + return -1; + + // Now we find the right stabs that define the function containing + // 'eip'. First, we find the basic source file containing 'eip'. + // Then, we look in that source file for the function. Then we look + // for the line number. + + // Search the entire set of stabs for the source file (type N_SO). + lfile = 0; + rfile = (stab_end - stabs) - 1; + stab_binsearch(stabs, &lfile, &rfile, N_SO, addr); + if (lfile == 0) + return -1; + + // Search within that file's stabs for the function definition + // (N_FUN). + lfun = lfile; + rfun = rfile; + stab_binsearch(stabs, &lfun, &rfun, N_FUN, addr); + + if (lfun <= rfun) { + // stabs[lfun] points to the function name + // in the string table, but check bounds just in case. + if (stabs[lfun].n_strx < stabstr_end - stabstr) + info->eip_fn_name = stabstr + stabs[lfun].n_strx; + info->eip_fn_addr = stabs[lfun].n_value; + addr -= info->eip_fn_addr; + // Search within the function definition for the line number. + lline = lfun; + rline = rfun; + } else { + // Couldn't find function stab! Maybe we're in an assembly + // file. Search the whole file for the line number. + info->eip_fn_addr = addr; + lline = lfile; + rline = rfile; + } + // Ignore stuff after the colon. + info->eip_fn_namelen = strfind(info->eip_fn_name, ':') - info->eip_fn_name; + + + // Search within [lline, rline] for the line number stab. + // If found, set info->eip_line to the right line number. + // If not found, return -1. + stab_binsearch(stabs, &lline, &rline, N_SLINE, addr); + if (rline < lline) { + return -1; + } + // line no is held in desc -- per the stab documentation (blerg) + info->eip_line = stabs[rline].n_desc; + + + // Search backwards from the line number for the relevant filename + // stab. + // We can't just use the "lfile" stab because inlined functions + // can interpolate code from a different file! + // Such included source files use the N_SOL stab type. + while (lline >= lfile + && stabs[lline].n_type != N_SOL + && (stabs[lline].n_type != N_SO || !stabs[lline].n_value)) + lline--; + if (lline >= lfile && stabs[lline].n_strx < stabstr_end - stabstr) + info->eip_file = stabstr + stabs[lline].n_strx; + + + // Set eip_fn_narg to the number of arguments taken by the function, + // or 0 if there was no containing function. + if (lfun < rfun) + for (lline = lfun + 1; + lline < rfun && stabs[lline].n_type == N_PSYM; + lline++) + info->eip_fn_narg++; + + return 0; +} + diff --git a/kernel/src/string.c b/kernel/src/string.c index 430f11e..3446c12 100644 --- a/kernel/src/string.c +++ b/kernel/src/string.c @@ -103,3 +103,17 @@ strlen(const char *s) return n; } +// Return a pointer to the first occurrence of 'c' in 's', +// or a pointer to the string-ending null character if the string has no 'c'. +char * +strfind(const char *s, char c) +{ + for (; *s; s++) + { + if (*s == c) + { + break; + } + } + return (char*)s; +} diff --git a/kernel/src/sysfile.c b/kernel/src/sysfile.c index bfe61b7..65d21f3 100644 --- a/kernel/src/sysfile.c +++ b/kernel/src/sysfile.c @@ -15,6 +15,7 @@ #include "sleeplock.h" #include "file.h" #include "fcntl.h" +#include "string.h" // Fetch the nth word-sized system call argument as a file descriptor // and return both the descriptor and the corresponding struct file. diff --git a/kernel/src/vm.c b/kernel/src/vm.c index 365322f..ebebf64 100644 --- a/kernel/src/vm.c +++ b/kernel/src/vm.c @@ -6,6 +6,7 @@ #include "mmu.h" #include "proc.h" #include "elf.h" +#include "string.h" extern char data[]; // defined by kernel.ld pde_t *kpgdir; // for use in scheduler() -- 2.47.3