Re: [patch] voluntary-preempt-2.6.8-rc4-O8

Ingo Molnar
2004-08-14T11:42:29Z

* 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;
}