[PATCH] kallsyms: speed up /proc/kallsyms
From: Paulo Marques (pmarques_at_grupopie.com)
Date: 08/31/04
- Previous message: Adrian Bunk: "Re: [patch] 2.6.9-rc1-mm2: char/pcxx.c doesn't compile"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 31 Aug 2004 21:26:28 +0100 To: linux-kernel <linux-kernel@vger.kernel.org>
This patch implements the "is_exported" bit in the kallsyms_names
compressed stream, so that a "cat /proc/kallsyms" doesn't call
is_exported on every iteration.
It also adds all the suggestions from Matt Mackall and others,
and fixes the compilation error "Inconsistent kallsyms data"
when compiling with KALLSYMS_ALL.
A "time cat /proc/kallsyms" goes from 0.25s without the patch to
0.00s with the patch. (Pentium4 2.8GHz, defconfig)
There is still a problem with the previous patch (and probably
remains in this patch too, but it must be tested) reported by
wli, that on big-endian machines the result is gibberish. This
was tested by wli on a sparc64.
Reading through the code, I can not find anything that assumes
any particular endian-ness.
I really need someone with a sparc64 hardware to do a kernel
build and then send me the ".tmp_kallsyms2.S" and "System.map"
files (gzip'd and in private), so that I can try to track down
the problem.
Also, someone with some other big-endian machine could test it
and see if it works or not, so that we know if the problem is
sparc64 specific or not.
The patch was built against 2.6.9-rc1-mm2.
As always, comments, suggestions, etc. are welcome.
--
Paulo Marques - www.grupopie.com
To err is human, but to really foul things up requires a computer.
Farmers' Almanac, 1978
Signed-Off-By: Paulo Marques <pmarques@grupopie.com>
kernel/kallsyms.c | 67 +++++++++++++------
scripts/kallsyms.c | 185 ++++++++++++++++++++++++++++++++++++++++++++---------
2 files changed, 202 insertions(+), 50 deletions(-)
diff -uprN -X ../dontdiff linux-2.6.9-rc1-mm2/kernel/kallsyms.c linux-2.6.9-rc1-mm2-kall/kernel/kallsyms.c
--- linux-2.6.9-rc1-mm2/kernel/kallsyms.c 2004-08-31 11:53:34.000000000 +0100
+++ linux-2.6.9-rc1-mm2-kall/kernel/kallsyms.c 2004-08-31 21:18:10.000000000 +0100
@@ -4,13 +4,12 @@
* Rewritten and vastly simplified by Rusty Russell for in-kernel
* module loader:
* Copyright 2002 Rusty Russell <rusty@rustcorp.com.au> IBM Corporation
- * Stem compression by Andi Kleen.
*
* ChangeLog:
*
- * (25/Aug/2004) Paulo Marques
+ * (25/Aug/2004) Paulo Marques <pmarques@grupopie.com>
* Changed the compression method from stem compression to "table lookup"
- * compression
+ * compression (see scripts/kallsyms.c for a more complete description)
*/
#include <linux/kallsyms.h>
#include <linux/module.h>
@@ -48,40 +47,61 @@ static inline int is_kernel_text(unsigne
return 0;
}
+/* expand a compressed symbol data into the resulting uncompressed string,
+ given the offset to where the symbol is in the compressed stream */
static unsigned int kallsyms_expand_symbol(unsigned int off, char *result)
{
- int len, tlen;
+ int len;
u8 *tptr, *data;
+ /* get the compressed symbol length from the first symbol byte,
+ * masking out the "is_exported" bit */
data = &kallsyms_names[off];
+ len = (*data) & 0x7F;
+ data++;
- len=*data++;
+ /* update the offset to return the offset for the next symbol on
+ the compressed stream */
off += len + 1;
+
+ /* for every byte on the compressed symbol data, copy the table
+ entry for that byte */
while(len) {
- tptr=&kallsyms_token_table[kallsyms_token_index[*data]];
+ tptr = &kallsyms_token_table[ kallsyms_token_index[*data] ];
data++;
len--;
- tlen=*tptr++;
- while(tlen) {
- *result++=*tptr++;
- tlen--;
+ while (*tptr) {
+ *result = *tptr;
+ result++;
+ tptr++;
}
}
- *result = 0;
+ *result = '\0';
+ /* return to offset to the next symbol */
return off;
}
+/* find the offset on the compressed stream given and index in the
+ kallsyms array */
static unsigned int get_symbol_offset(unsigned long pos)
{
u8 *name;
int i;
+ /* use the closest marker we have. We have markers every
+ 256 positions, so that should be close enough */
name = &kallsyms_names[ kallsyms_markers[pos>>8] ];
+
+ /* sequentially scan all the symbols up to the point we're
+ searching for. Every symbol is stored in a
+ [bit 7: is_exported | bits 6..0: <len>][<len> bytes of data]
+ format, so we just need to add the len to the current
+ pointer for every symbol we wish to skip */
for(i = 0; i < (pos&0xFF); i++)
- name = name + (*name) + 1;
+ name = name + ((*name) & 0x7F) + 1;
return name - kallsyms_names;
}
@@ -122,12 +142,16 @@ const char *kallsyms_lookup(unsigned lon
/* 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;
}
- while (low && kallsyms_addresses[low-1] == kallsyms_addresses[low])
+
+ /* search for the first aliased symbol. Aliased symbols are
+ symbols with the same address */
+ while (low && kallsyms_addresses[low - 1] == kallsyms_addresses[low])
--low;
/* Grab name */
@@ -141,8 +165,8 @@ const char *kallsyms_lookup(unsigned lon
}
}
+ /* if we found no next symbol, we use the end of the section */
if (!symbol_end) {
- /* At worst, symbol ends at end of section. */
if (is_kernel_inittext(addr))
symbol_end = (unsigned long)_einittext;
else
@@ -182,7 +206,7 @@ void __print_symbol(const char *fmt, uns
printk(fmt, buffer);
}
-/* To avoid O(n^2) iteration, we carry prefix along. */
+/* To avoid using get_symbol_offset for every symbol, we carry prefix along. */
struct kallsym_iter
{
loff_t pos;
@@ -217,16 +241,20 @@ static unsigned long get_ksymbol_core(st
{
unsigned off = iter->nameoff;
- off = kallsyms_expand_symbol(off, iter->name);
-
iter->owner = NULL;
iter->value = kallsyms_addresses[iter->pos];
+
if (is_kernel_text(iter->value) || is_kernel_inittext(iter->value))
iter->type = 't';
else
iter->type = 'd';
- upcase_if_global(iter);
+ /* check the "is_exported" bit on the compressed stream */
+ if (kallsyms_names[off] & 0x80)
+ iter->type += 'A' - 'a';
+
+ off = kallsyms_expand_symbol(off, iter->name);
+
return off - iter->nameoff;
}
@@ -306,7 +334,8 @@ struct seq_operations kallsyms_op = {
static int kallsyms_open(struct inode *inode, struct file *file)
{
/* We keep iterator in m->private, since normal case is to
- * s_start from where we left off, so we avoid O(N^2). */
+ * s_start from where we left off, so we avoid doing
+ * using get_symbol_offset for every symbol */
struct kallsym_iter *iter;
int ret;
diff -uprN -X ../dontdiff linux-2.6.9-rc1-mm2/scripts/kallsyms.c linux-2.6.9-rc1-mm2-kall/scripts/kallsyms.c
--- linux-2.6.9-rc1-mm2/scripts/kallsyms.c 2004-08-31 11:53:34.000000000 +0100
+++ linux-2.6.9-rc1-mm2-kall/scripts/kallsyms.c 2004-08-31 21:09:50.000000000 +0100
@@ -9,10 +9,19 @@
*
* ChangeLog:
*
- * (25/Aug/2004) Paulo Marques
+ * (25/Aug/2004) Paulo Marques <pmarques@grupopie.com>
* Changed the compression method from stem compression to "table lookup"
* compression
*
+ * Table compression uses all the unused char codes on the symbols and
+ * maps these to the most used substrings (tokens). For instance, it might
+ * map char code 0xF7 to represent "write_" and then in every symbol where
+ * "write_" appears it can be replaced by 0xF7, saving 5 bytes.
+ * The used codes themselves are also placed in the table so that the
+ * decompresion can work without "special cases".
+ * Applied to kernel symbols, this usually produces a compression ratio
+ * of about 50%.
+ *
*/
#include <stdio.h>
@@ -20,28 +29,38 @@
#include <string.h>
#include <ctype.h>
-/* compression tunning settings */
+/* maximum token length used. It doesn't pay to increase it a lot, because
+ * very long substrings probably don't repeat themselves too often. */
#define MAX_TOK_SIZE 11
#define KSYM_NAME_LEN 127
/* we use only a subset of the complete symbol table to gather the token count,
- to speed up compression, at the expense of a little compression ratio
-*/
+ * to speed up compression, at the expense of a little compression ratio */
#define WORKING_SET 1024
+
+/* first find the best token only on the list of tokens that would profit more
+ * than GOOD_BAD_THRESHOLD. Only if this list is empty go to the "bad" list.
+ * Increasing this value will put less tokens on the "good" list, so the search
+ * is faster. However, if the good list runs out of tokens, we must painfully
+ * search the bad list. */
#define GOOD_BAD_THRESHOLD 10
+/* token hash parameters */
#define HASH_BITS 18
#define HASH_TABLE_SIZE (1 << HASH_BITS)
#define HASH_MASK (HASH_TABLE_SIZE - 1)
#define HASH_BASE_OFFSET 2166136261U
#define HASH_FOLD(a) ((a)&(HASH_MASK))
+/* flags to mark symbols */
+#define SYM_FLAG_VALID 1
+#define SYM_FLAG_SAMPLED 2
+#define SYM_FLAG_EXPORTED 4
struct sym_entry {
unsigned long long addr;
char type;
- char sample;
- char valid;
+ unsigned char flags;
unsigned char len;
unsigned char *sym;
};
@@ -49,23 +68,28 @@ struct sym_entry {
static struct sym_entry *table;
static int size, cnt;
-static unsigned long long _stext, _etext, _sinittext, _einittext;
+static unsigned long long _stext, _etext, _sinittext, _einittext, _start_ksymtab, _stop_ksymtab;
static int all_symbols = 0;
+/* aray of pointers into the symbol table sorted by name */
+static struct sym_entry **sorted_table;
struct token {
unsigned char data[MAX_TOK_SIZE];
unsigned char len;
+ /* profit: the number of bytes that could be saved by inserting this
+ * token into the table */
int profit;
- struct token *next;
- struct token *right;
- struct token *left;
- struct token *smaller;
+ struct token *next; /* next token on the hash list */
+ struct token *right; /* next token on the good/bad list */
+ struct token *left; /* previous token on the good/bad list */
+ struct token *smaller; /* token that is less one letter than this one */
};
struct token bad_head, good_head;
struct token *hash_table[HASH_TABLE_SIZE];
+/* the table that holds the result of the compression */
unsigned char best_table[256][MAX_TOK_SIZE+1];
unsigned char best_table_len[256];
@@ -101,6 +125,10 @@ read_symbol(FILE *in, struct sym_entry *
_sinittext = s->addr;
else if (strcmp(str, "_einittext") == 0)
_einittext = s->addr;
+ else if (strcmp(str, "__start___ksymtab") == 0)
+ _start_ksymtab = s->addr;
+ else if (strcmp(str, "__stop___ksymtab") == 0)
+ _stop_ksymtab = s->addr;
else if (toupper(s->type) == 'A' || toupper(s->type) == 'U')
return -1;
@@ -126,7 +154,10 @@ symbol_valid(struct sym_entry *s)
if (strstr(s->sym, "_compiled.") ||
strcmp(s->sym, "kallsyms_addresses") == 0 ||
strcmp(s->sym, "kallsyms_num_syms") == 0 ||
- strcmp(s->sym, "kallsyms_names") == 0)
+ strcmp(s->sym, "kallsyms_names") == 0 ||
+ strcmp(s->sym, "kallsyms_markers") == 0 ||
+ strcmp(s->sym, "kallsyms_token_table") == 0 ||
+ strcmp(s->sym, "kallsyms_token_index") == 0)
return 0;
/* Exclude linker generated symbols which vary between passes */
@@ -161,16 +192,21 @@ static void output_label(char *label)
printf("%s:\n",label);
}
+/* uncompress a compressed symbol. When this function is called, the best table
+ * might still be compressed itself, so the function needs to be recursive */
static int expand_symbol(unsigned char *data, int len, char *result)
{
int c, rlen, total=0;
while (len) {
c = *data;
+ /* if the table holds a single char that is the same as the one
+ * we are looking for, then end the search */
if (best_table[c][0]==c && best_table_len[c]==1) {
*result++ = c;
total++;
} else {
+ /* if not, recurse and expand */
rlen = expand_symbol(best_table[c], best_table_len[c], result);
total += rlen;
result += rlen;
@@ -205,7 +241,7 @@ write_src(void)
output_label("kallsyms_addresses");
valid = 0;
for (i = 0; i < cnt; i++) {
- if (table[i].valid) {
+ if (table[i].flags & SYM_FLAG_VALID) {
printf("\tPTR\t%#llx\n", table[i].addr);
valid++;
}
@@ -216,6 +252,8 @@ write_src(void)
printf("\tPTR\t%d\n", valid);
printf("\n");
+ /* table of offset markers, that give the offset in the compressed stream
+ * every 256 symbols */
markers = (unsigned int *) malloc(sizeof(unsigned int)*((valid + 255) / 256));
output_label("kallsyms_names");
@@ -223,13 +261,15 @@ write_src(void)
off = 0;
for (i = 0; i < cnt; i++) {
- if (!table[i].valid)
+ if (!table[i].flags & SYM_FLAG_VALID)
continue;
if ((valid & 0xFF) == 0)
markers[valid >> 8] = off;
- printf("\t.byte 0x%02x", table[i].len);
+ k = table[i].len;
+ if (table[i].flags & SYM_FLAG_EXPORTED) k |= 0x80;
+ printf("\t.byte 0x%02x", k);
for (k = 0; k < table[i].len; k++)
printf(", 0x%02x", table[i].sym[k]);
printf("\n");
@@ -244,14 +284,15 @@ write_src(void)
printf("\tPTR\t%d\n", markers[i]);
printf("\n");
+ free(markers);
+
output_label("kallsyms_token_table");
off = 0;
for (i = 0; i < 256; i++) {
best_idx[i] = off;
expand_symbol(best_table[i],best_table_len[i],buf);
- k = strlen(buf);
- printf("\t.byte 0x%02x\n\t.ascii\t\"%s\"\n", k, buf);
- off += k + 1;
+ printf("\t.asciz\t\"%s\"\n", buf);
+ off += strlen(buf) + 1;
}
printf("\n");
@@ -280,6 +321,7 @@ static unsigned int hash_token(unsigned
return HASH_FOLD(hash);
}
+/* find a token given its data and hash value */
static struct token *find_token_hash(unsigned char *data, int len, unsigned int hash)
{
struct token *ptr;
@@ -309,6 +351,9 @@ static inline void remove_token_from_gro
ptr->right->left = ptr->left;
}
+
+/* build the counts for all the tokens that start with "data", and have lenghts
+ * from 2 to "len" */
static void learn_token(unsigned char *data, int len)
{
struct token *ptr,*last_ptr;
@@ -319,6 +364,7 @@ static void learn_token(unsigned char *d
if (len > MAX_TOK_SIZE)
len = MAX_TOK_SIZE;
+ /* calculate and store the hash values for all the sub-tokens */
hash = rehash_token(hash, data[0]);
for (i = 2; i <= len; i++) {
hash = rehash_token(hash, data[i-1]);
@@ -334,10 +380,19 @@ static void learn_token(unsigned char *d
if (!ptr) ptr = find_token_hash(data, i, hash);
if (!ptr) {
+ /* create a new token entry */
ptr = (struct token *) malloc(sizeof(*ptr));
+
memcpy(ptr->data, data, i);
ptr->len = i;
+
+ /* when we create an entry, it's profit is 0 because
+ * we also take into account the size of the token on
+ * the compressed table. We then subtract GOOD_BAD_THRESHOLD
+ * so that the test to see if this token belongs to
+ * the good or bad list, is a comparison to zero */
ptr->profit = -GOOD_BAD_THRESHOLD;
+
ptr->next = hash_table[hash];
hash_table[hash] = ptr;
@@ -346,11 +401,13 @@ static void learn_token(unsigned char *d
ptr->smaller = NULL;
} else {
newprofit = ptr->profit + (ptr->len - 1);
+ /* check to see if this token needs to be moved to a
+ * different list */
if((ptr->profit < 0) && (newprofit >= 0)) {
remove_token_from_group(ptr);
insert_token_in_group(&good_head,ptr);
}
- ptr->profit = newprofit;
+ ptr->profit = newprofit;
}
if (last_ptr) last_ptr->smaller = ptr;
@@ -360,6 +417,10 @@ static void learn_token(unsigned char *d
}
}
+/* decrease the counts for all the tokens that start with "data", and have lenghts
+ * from 2 to "len". This function is much simpler than learn_token because we have
+ * more guarantees (tho tokens exist, the ->smaller pointer is set, etc.)
+ * The two separate functions exist only because of compression performance */
static void forget_token(unsigned char *data, int len)
{
struct token *ptr;
@@ -384,6 +445,7 @@ static void forget_token(unsigned char *
}
}
+/* count all the possible tokens in a symbol */
static void learn_symbol(unsigned char *symbol, int len)
{
int i;
@@ -392,6 +454,7 @@ static void learn_symbol(unsigned char *
learn_token(symbol + i, len - i);
}
+/* decrease the count for all the possible tokens in a symbol */
static void forget_symbol(unsigned char *symbol, int len)
{
int i;
@@ -400,49 +463,98 @@ static void forget_symbol(unsigned char
forget_token(symbol + i, len - i);
}
+static int symbol_sort(const void *a, const void *b)
+{
+ return strcmp( (*((struct sym_entry **) a))->sym,
+ (*((struct sym_entry **) b))->sym );
+}
+
+
+/* find out if a symbol is exported. Exported symbols have a corresponding
+ * __ksymtab_<symbol> entry and their addresses are between __start___ksymtab
+ * and __stop___ksymtab */
+static int is_exported(char *name)
+{
+ struct sym_entry key, *ksym, **result;
+ char buf[KSYM_NAME_LEN+32];
+
+ sprintf(buf, "__ksymtab_%s", name);
+ key.sym = buf;
+
+ ksym = &key;
+ result = bsearch(&ksym, sorted_table, cnt,
+ sizeof(struct sym_entry *), symbol_sort);
+
+ if(!result) return 0;
+
+ ksym = *result;
+
+ return ((ksym->addr >= _start_ksymtab) && (ksym->addr < _stop_ksymtab));
+}
+
+/* set all the symbol flags and do the initial token count */
static void build_initial_tok_table(void)
{
int i, use_it, valid;
+ /* build a sorted symbol pointer array so that searching a particular
+ * symbol is faster */
+ sorted_table = (struct sym_entry **) malloc(sizeof(struct sym_entry *) * cnt);
+ for (i = 0; i < cnt; i++)
+ sorted_table[i] = &table[i];
+ qsort(sorted_table, cnt, sizeof(struct sym_entry *), symbol_sort);
+
valid = 0;
for (i = 0; i < cnt; i++) {
- table[i].valid = symbol_valid(&table[i]);
- if (table[i].valid) valid++;
+ table[i].flags = 0;
+ if ( symbol_valid(&table[i]) ) {
+ table[i].flags |= SYM_FLAG_VALID;
+ valid++;
+ }
}
use_it = 0;
for (i = 0; i < cnt; i++) {
- table[i].sample = 0;
- if (table[i].valid) {
+ if (table[i].flags & SYM_FLAG_VALID) {
+
use_it += WORKING_SET;
+
if (use_it >= valid) {
- table[i].sample = 1;
+ table[i].flags |= SYM_FLAG_SAMPLED;
use_it -= valid;
}
+
+ if( is_exported(table[i].sym) )
+ table[i].flags |= SYM_FLAG_EXPORTED;
}
- if (table[i].sample)
+ if (table[i].flags & SYM_FLAG_SAMPLED)
learn_symbol(table[i].sym, table[i].len);
}
}
+/* replace a given token in all the valid symbols. Use the sampled symbols
+ * to update the counts */
static void compress_symbols(unsigned char *str, int tlen, int idx)
{
int i, len, learn, size;
unsigned char *p;
for (i = 0; i < cnt; i++) {
- if (!table[i].valid) continue;
+
+ if (!(table[i].flags & SYM_FLAG_VALID)) continue;
len = table[i].len;
learn = 0;
p = table[i].sym;
do {
+ /* find the token on the symbol */
p = (unsigned char *) strstr((char *) p, (char *) str);
if (!p) break;
if (!learn) {
- if (table[i].sample)
+ /* if this symbol was used to count, decrease it */
+ if (table[i].flags & SYM_FLAG_SAMPLED)
forget_symbol(table[i].sym, len);
learn = 1;
}
@@ -457,11 +569,14 @@ static void compress_symbols(unsigned ch
if(learn) {
table[i].len = len;
- if(table[i].sample) learn_symbol(table[i].sym, len);
+ /* if this symbol was used to count, learn it again */
+ if(table[i].flags & SYM_FLAG_SAMPLED)
+ learn_symbol(table[i].sym, len);
}
}
}
+/* search the token with the maximum profit */
static struct token *find_best_token(void)
{
struct token *ptr,*best,*head;
@@ -486,29 +601,37 @@ static struct token *find_best_token(voi
return best;
}
+/* this is the core of the algorithm: calculate the "best" table */
static void optimize_result(void)
{
struct token *best;
int i;
/* using the '\0' symbol last allows compress_symbols to use standard
- fast string functions
- */
+ * fast string functions */
for (i = 255; i >= 0; i--) {
+
+ /* if this table slot is empty (it is not used by an actual
+ * original char code */
if (!best_table_len[i]) {
+
+ /* find the token with the breates profit value */
best = find_best_token();
+ /* place it in the "best" table */
best_table_len[i] = best->len;
memcpy(best_table[i], best->data, best_table_len[i]);
/* zero terminate the token so that we can use strstr
in compress_symbols */
best_table[i][best_table_len[i]]='\0';
+ /* replace this token in all the valid symbols */
compress_symbols(best_table[i], best_table_len[i], i);
}
}
}
+/* start by placing the symbols that are actually used on the table */
static void insert_real_symbols_in_table(void)
{
int i, j, c;
@@ -517,7 +640,7 @@ static void insert_real_symbols_in_table
memset(best_table_len, 0, sizeof(best_table_len));
for (i = 0; i < cnt; i++) {
- if (table[i].valid) {
+ if (table[i].flags & SYM_FLAG_VALID) {
for (j = 0; j < table[i].len; j++) {
c = table[i].sym[j];
best_table[c][0]=c;
-
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/
- Previous message: Adrian Bunk: "Re: [patch] 2.6.9-rc1-mm2: char/pcxx.c doesn't compile"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
|
