Messages in this thread Patch in this message | | | Date | Sat, 14 Aug 2004 13:42:51 +0200 | From | Ingo Molnar <> | Subject | Re: [patch] voluntary-preempt-2.6.8-rc4-O8 |
| |
* Sam Ravnborg <sam@ravnborg.org> wrote:
> > other changes in -O8: the massive kallsyms-lookup speedup from Paulo > > Marque > > Do you have this as an independent patch - or an URL?
yeah, attached below.
Ingo
--- linux/kernel/kallsyms.c.orig +++ linux/kernel/kallsyms.c @@ -22,6 +22,13 @@ extern char kallsyms_names[] __attribute /* Defined by the linker script. */ extern char _stext[], _etext[], _sinittext[], _einittext[]; +/* auxiliary markers to speed up symbol lookup */ +#define KALLSYMS_STEM_MARKS 8 + +static int kallsyms_stem_mark_idx[KALLSYMS_STEM_MARKS]; +static char *kallsyms_stem_mark[KALLSYMS_STEM_MARKS]; + + static inline int is_kernel_inittext(unsigned long addr) { if (addr >= (unsigned long)_sinittext @@ -56,13 +63,42 @@ unsigned long kallsyms_lookup_name(const return module_kallsyms_lookup_name(name); } +/* build markers into the compressed symbol table, so that lookups can be faster */ +static void build_stem_marks(void) +{ + char *name = kallsyms_names; + int i, mark_cnt; + + unsigned prefix; + + mark_cnt = 0; + for (i = 0 ; i < kallsyms_num_syms; i++) { + prefix=*name; + if (prefix == 0) { + /* if this is the first 0-prefix stem in the desired interval */ + if(i > (mark_cnt + 1) * (kallsyms_num_syms / (KALLSYMS_STEM_MARKS + 1)) && + kallsyms_stem_mark_idx[mark_cnt]==0) { + kallsyms_stem_mark[mark_cnt] = name; + kallsyms_stem_mark_idx[mark_cnt] = i; + mark_cnt++; + if(mark_cnt >= KALLSYMS_STEM_MARKS) break; + } + } + do { + name++; + } while(*name); + name ++; + } +} /* Lookup an address. modname is set to NULL if it's in the kernel. */ const char *kallsyms_lookup(unsigned long addr, unsigned long *symbolsize, unsigned long *offset, char **modname, char *namebuf) { - unsigned long i, best = 0; + unsigned long i, last_0idx = 0; + unsigned long mark, low, high, mid; + char *last_0prefix = NULL; /* This kernel should never had been booted. */ BUG_ON(!kallsyms_addresses); @@ -72,39 +108,67 @@ const char *kallsyms_lookup(unsigned lon if (is_kernel_text(addr) || is_kernel_inittext(addr)) { unsigned long symbol_end; - char *name = kallsyms_names; + char *name; - /* They're sorted, we could be clever here, but who cares? */ - for (i = 0; i < kallsyms_num_syms; i++) { - if (kallsyms_addresses[i] > kallsyms_addresses[best] && - kallsyms_addresses[i] <= addr) - best = i; + /* do a binary search on the sorted kallsyms_addresses array */ + low = 0; + high = kallsyms_num_syms; + while( high-low > 1 ) { + mid = (low + high) / 2; + if( kallsyms_addresses[mid] <= addr ) low = mid; + else high = mid; } /* Grab name */ - for (i = 0; i <= best; i++) { - unsigned prefix = *name++; - strncpy(namebuf + prefix, name, KSYM_NAME_LEN - prefix); - name += strlen(name) + 1; - } + i = 0; + name = kallsyms_names; - /* At worst, symbol ends at end of section. */ - if (is_kernel_inittext(addr)) - symbol_end = (unsigned long)_einittext; - else - symbol_end = (unsigned long)_etext; + if(kallsyms_stem_mark_idx[0]==0) + build_stem_marks(); + + for(mark = 0; mark < KALLSYMS_STEM_MARKS; mark++) { + if( low >= kallsyms_stem_mark_idx[mark] ) { + i = kallsyms_stem_mark_idx[mark]; + name = kallsyms_stem_mark[mark]; + } + else break; + } - /* Search for next non-aliased symbol */ - for (i = best+1; i < kallsyms_num_syms; i++) { - if (kallsyms_addresses[i] > kallsyms_addresses[best]) { - symbol_end = kallsyms_addresses[i]; - break; + /* find the last stem before the actual symbol that as 0 prefix */ + unsigned prefix; + for (; i <= low; i++) { + prefix=*name; + if (prefix == 0) { + last_0prefix = name; + last_0idx = i; } + do { + name++; + } while(*name); + name ++; } - *symbolsize = symbol_end - kallsyms_addresses[best]; + /* build the name from there */ + name = last_0prefix; + for (i = last_0idx; i <= low; i++) { + prefix = *name++; + strncpy(namebuf + prefix, name, KSYM_NAME_LEN - prefix); + name += strlen(name) + 1; + } + + if(low == kallsyms_num_syms - 1) { + /* At worst, symbol ends at end of section. */ + if (is_kernel_inittext(addr)) + symbol_end = (unsigned long)_einittext; + else + symbol_end = (unsigned long)_etext; + } + else + symbol_end = kallsyms_addresses[low + 1]; + + *symbolsize = symbol_end - kallsyms_addresses[low]; *modname = NULL; - *offset = addr - kallsyms_addresses[best]; + *offset = addr - kallsyms_addresses[low]; return namebuf; } - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |