[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [Xen-changelog] Local merge
# HG changeset patch # User sd386@xxxxxxxxxxxxxxxxx # Node ID dc7c14e533c259d45bac02b2a2ca4bed0f999946 # Parent 460405b4723bc65623e6fe9d61e653709a66c850 # Parent 48aed1403fe35f80aaed8f03c354cbb8c1a0c4ab Local merge Stephan.Diestelhorst@{cl.cam.ac.uk, inf.tu-dresden.de} diff -r 460405b4723b -r dc7c14e533c2 xen/arch/ia64/Makefile --- a/xen/arch/ia64/Makefile Fri Jul 22 15:32:31 2005 +++ b/xen/arch/ia64/Makefile Fri Jul 22 17:58:52 2005 @@ -62,10 +62,4 @@ rm -f *.o *~ core xen.lds.s $(BASEDIR)/include/asm-ia64/.offsets.h.stamp asm-offsets.s rm -f lib/*.o -# setup.o contains bits of compile.h so it must be blown away -delete-unfresh-files: - echo any unfresh-files to delete for ia64\? -# rm -f setup.o - -.PHONY: default clean delete-unfresh-files - +.PHONY: default clean diff -r 460405b4723b -r dc7c14e533c2 xen/Makefile --- a/xen/Makefile Fri Jul 22 15:32:31 2005 +++ b/xen/Makefile Fri Jul 22 17:58:52 2005 @@ -50,10 +50,10 @@ $(MAKE) -C arch/$(TARGET_ARCH) clean rm -f include/asm *.o $(TARGET)* *~ core rm -f include/asm-*/asm-offsets.h - rm -f tools/figlet/*.o tools/figlet/figlet rm -f include/xen/acm_policy.h $(TARGET): delete-unfresh-files + $(MAKE) -C tools $(MAKE) include/xen/compile.h $(MAKE) include/xen/acm_policy.h [ -e include/asm ] || ln -sf asm-$(TARGET_ARCH) include/asm @@ -71,7 +71,6 @@ delete-unfresh-files: @if [ ! -r include/xen/compile.h -o -O include/xen/compile.h ]; then \ rm -f include/xen/{banner,compile}.h; \ - $(MAKE) -C arch/$(TARGET_ARCH) delete-unfresh-files; \ fi # acm_policy.h contains security policy for Xen @@ -105,12 +104,7 @@ @cat include/xen/banner.h >> $@.new @mv -f $@.new $@ -tools/figlet/figlet: tools/figlet/figlet.o - $(HOSTCC) -o $@ $< -tools/figlet/figlet.o: tools/figlet/figlet.c - $(HOSTCC) -o $@ -c $< - -include/xen/banner.h: tools/figlet/figlet tools/figlet/xen.flf +include/xen/banner.h: tools/figlet/figlet -d tools/figlet Xen $(XEN_FULLVERSION) > $@.new @mv -f $@.new $@ diff -r 460405b4723b -r dc7c14e533c2 xen/arch/x86/Makefile --- a/xen/arch/x86/Makefile Fri Jul 22 15:32:31 2005 +++ b/xen/arch/x86/Makefile Fri Jul 22 17:58:52 2005 @@ -37,6 +37,15 @@ $(TARGET)-syms: boot/$(TARGET_SUBARCH).o $(ALL_OBJS) $(TARGET_SUBARCH)/xen.lds $(LD) $(LDFLAGS) -T $(TARGET_SUBARCH)/xen.lds -N \ boot/$(TARGET_SUBARCH).o $(ALL_OBJS) -o $@ + nm -n $@ | $(BASEDIR)/tools/symbols >$(BASEDIR)/xen-syms.S + $(MAKE) $(BASEDIR)/xen-syms.o + $(LD) $(LDFLAGS) -T $(TARGET_SUBARCH)/xen.lds -N \ + boot/$(TARGET_SUBARCH).o $(ALL_OBJS) $(BASEDIR)/xen-syms.o -o $@ + nm -n $@ | $(BASEDIR)/tools/symbols >$(BASEDIR)/xen-syms.S + $(MAKE) $(BASEDIR)/xen-syms.o + $(LD) $(LDFLAGS) -T $(TARGET_SUBARCH)/xen.lds -N \ + boot/$(TARGET_SUBARCH).o $(ALL_OBJS) $(BASEDIR)/xen-syms.o -o $@ + rm -f $(BASEDIR)/xen-syms.S $(BASEDIR)/xen-syms.o asm-offsets.s: $(TARGET_SUBARCH)/asm-offsets.c $(HDRS) $(CC) $(CFLAGS) -S -o $@ $< @@ -53,7 +62,4 @@ rm -f genapic/*.o genapic/*~ genapic/core rm -f cpu/*.o cpu/*~ cpu/core -delete-unfresh-files: - # nothing - -.PHONY: default clean delete-unfresh-files +.PHONY: default clean diff -r 460405b4723b -r dc7c14e533c2 .hgignore --- a/.hgignore Fri Jul 22 15:32:31 2005 +++ b/.hgignore Fri Jul 22 17:58:52 2005 @@ -162,10 +162,6 @@ ^xen/arch/x86/asm-offsets\.s$ ^xen/arch/x86/boot/mkelf32$ ^xen/ddb/.*$ -^xen/drivers/pci/classlist\.h$ -^xen/drivers/pci/devlist\.h$ -^xen/drivers/pci/gen-devlist$ -^xen/figlet/figlet$ ^xen/include/asm$ ^xen/include/asm-.*/asm-offsets\.h$ ^xen/include/hypervisor-ifs/arch$ @@ -175,8 +171,8 @@ ^xen/include/xen/banner\.h$ ^xen/include/xen/compile\.h$ ^xen/tags$ -^xen/tools/elf-reloc$ ^xen/tools/figlet/figlet$ +^xen/tools/symbols$ ^xen/xen$ ^xen/xen-syms$ ^xen/xen\..*$ diff -r 460405b4723b -r dc7c14e533c2 xen/arch/x86/x86_32/traps.c --- a/xen/arch/x86/x86_32/traps.c Fri Jul 22 15:32:31 2005 +++ b/xen/arch/x86/x86_32/traps.c Fri Jul 22 17:58:52 2005 @@ -6,6 +6,7 @@ #include <xen/console.h> #include <xen/mm.h> #include <xen/irq.h> +#include <xen/symbols.h> #include <asm/current.h> #include <asm/flushtlb.h> #include <asm/vmx.h> @@ -63,10 +64,10 @@ } } - printk("CPU: %d\nEIP: %04lx:[<%08lx>] \nEFLAGS: %08lx " - "CONTEXT: %s\n", - smp_processor_id(), (unsigned long)0xffff & regs->cs, - eip, eflags, context); + printk("CPU: %d\nEIP: %04lx:[<%08lx>]", + smp_processor_id(), (unsigned long)0xffff & regs->cs, eip); + print_symbol(" %s\n", eip); + printk("EFLAGS: %08lx CONTEXT: %s\n", eflags, context); printk("eax: %08x ebx: %08x ecx: %08x edx: %08x\n", regs->eax, regs->ebx, regs->ecx, regs->edx); printk("esi: %08x edi: %08x ebp: %08x esp: %08lx\n", @@ -119,8 +120,10 @@ /* Find information saved during fault and dump it to the console. */ tss = &init_tss[cpu]; - printk("CPU: %d\nEIP: %04x:[<%08x>] \nEFLAGS: %08x\n", - cpu, tss->cs, tss->eip, tss->eflags); + printk("CPU: %d\nEIP: %04x:[<%08x>]", + cpu, tss->cs, tss->eip); + print_symbol(" %s\n", tss->eip); + printk("EFLAGS: %08x\n", tss->eflags); printk("CR3: %08x\n", tss->__cr3); printk("eax: %08x ebx: %08x ecx: %08x edx: %08x\n", tss->eax, tss->ebx, tss->ecx, tss->edx); diff -r 460405b4723b -r dc7c14e533c2 xen/include/asm-x86/types.h --- a/xen/include/asm-x86/types.h Fri Jul 22 15:32:31 2005 +++ b/xen/include/asm-x86/types.h Fri Jul 22 17:58:52 2005 @@ -1,10 +1,9 @@ #ifndef __X86_TYPES_H__ #define __X86_TYPES_H__ -/* - * __xx is ok: it doesn't pollute the POSIX namespace. Use these in the - * header files exported to user space - */ +#ifndef __ASSEMBLY__ + +#include <xen/config.h> typedef __signed__ char __s8; typedef unsigned char __u8; @@ -25,8 +24,6 @@ #endif #endif -#include <xen/config.h> - typedef signed char s8; typedef unsigned char u8; @@ -39,9 +36,6 @@ #if defined(__i386__) typedef signed long long s64; typedef unsigned long long u64; -#define BITS_PER_LONG 32 -#define BYTES_PER_LONG 4 -#define LONG_BYTEORDER 2 #if defined(CONFIG_X86_PAE) typedef u64 physaddr_t; #else @@ -50,12 +44,21 @@ #elif defined(__x86_64__) typedef signed long s64; typedef unsigned long u64; -#define BITS_PER_LONG 64 -#define BYTES_PER_LONG 8 -#define LONG_BYTEORDER 3 typedef u64 physaddr_t; #endif typedef unsigned long size_t; +#endif /* __ASSEMBLY__ */ + +#if defined(__i386__) +#define BITS_PER_LONG 32 +#define BYTES_PER_LONG 4 +#define LONG_BYTEORDER 2 +#elif defined(__x86_64__) +#define BITS_PER_LONG 64 +#define BYTES_PER_LONG 8 +#define LONG_BYTEORDER 3 +#endif + #endif /* __X86_TYPES_H__ */ diff -r 460405b4723b -r dc7c14e533c2 xen/arch/x86/x86_64/traps.c --- a/xen/arch/x86/x86_64/traps.c Fri Jul 22 15:32:31 2005 +++ b/xen/arch/x86/x86_64/traps.c Fri Jul 22 17:58:52 2005 @@ -6,6 +6,7 @@ #include <xen/errno.h> #include <xen/mm.h> #include <xen/irq.h> +#include <xen/symbols.h> #include <xen/console.h> #include <xen/sched.h> #include <asm/current.h> @@ -14,8 +15,10 @@ void show_registers(struct cpu_user_regs *regs) { - printk("CPU: %d\nEIP: %04x:[<%016lx>] \nEFLAGS: %016lx\n", - smp_processor_id(), 0xffff & regs->cs, regs->rip, regs->eflags); + printk("CPU: %d\nEIP: %04x:[<%016lx>]", + smp_processor_id(), 0xffff & regs->cs, regs->rip); + print_symbol(" %s\n", regs->rip); + printk("EFLAGS: %016lx\n", regs->eflags); printk("rax: %016lx rbx: %016lx rcx: %016lx rdx: %016lx\n", regs->rax, regs->rbx, regs->rcx, regs->rdx); printk("rsi: %016lx rdi: %016lx rbp: %016lx rsp: %016lx\n", diff -r 460405b4723b -r dc7c14e533c2 xen/arch/x86/traps.c --- a/xen/arch/x86/traps.c Fri Jul 22 15:32:31 2005 +++ b/xen/arch/x86/traps.c Fri Jul 22 17:58:52 2005 @@ -40,6 +40,7 @@ #include <xen/perfc.h> #include <xen/softirq.h> #include <xen/domain_page.h> +#include <xen/symbols.h> #include <asm/shadow.h> #include <asm/system.h> #include <asm/io.h> @@ -100,7 +101,7 @@ static int debug_stack_lines = 20; integer_param("debug_stack_lines", debug_stack_lines); -static inline int kernel_text_address(unsigned long addr) +int is_kernel_text(unsigned long addr) { extern char _stext, _etext; if (addr >= (unsigned long) &_stext && @@ -110,6 +111,12 @@ } +unsigned long kernel_text_end(void) +{ + extern char _etext; + return (unsigned long) &_etext; +} + void show_guest_stack(void) { int i; @@ -150,11 +157,12 @@ while ( ((long) stack & (STACK_SIZE-1)) != 0 ) { addr = *stack++; - if ( kernel_text_address(addr) ) + if ( is_kernel_text(addr) ) { if ( (i != 0) && ((i % 6) == 0) ) printk("\n "); - printk("[<%p>] ", _p(addr)); + printk("[<%p>]", _p(addr)); + print_symbol(" %s\n", addr); i++; } } @@ -177,10 +185,7 @@ if ( (i != 0) && ((i % 8) == 0) ) printk("\n "); addr = *stack++; - if ( kernel_text_address(addr) ) - printk("[%p] ", _p(addr)); - else - printk("%p ", _p(addr)); + printk("%p ", _p(addr)); } if ( i == 0 ) printk("Stack empty."); diff -r 460405b4723b -r dc7c14e533c2 xen/tools/Makefile --- a/xen/tools/Makefile Fri Jul 22 15:32:31 2005 +++ b/xen/tools/Makefile Fri Jul 22 17:58:52 2005 @@ -1,6 +1,13 @@ + +include $(BASEDIR)/../Config.mk default: $(MAKE) -C figlet + $(MAKE) symbols clean: - $(MAKE) -C figlet clean \ No newline at end of file + $(MAKE) -C figlet clean + rm -f *.o symbols + +symbols: symbols.c + $(HOSTCC) -o $@ $< diff -r 460405b4723b -r dc7c14e533c2 xen/include/xen/symbols.h --- /dev/null Fri Jul 22 15:32:31 2005 +++ b/xen/include/xen/symbols.h Fri Jul 22 17:58:52 2005 @@ -0,0 +1,45 @@ +#ifndef _XEN_SYMBOLS_H +#define _XEN_SYMBOLS_H + +#include <xen/config.h> +#include <xen/types.h> + +#define KSYM_NAME_LEN 127 + +extern int is_kernel_text(unsigned long addr); +extern unsigned long kernel_text_end(void); + +/* Lookup an address. */ +const char *symbols_lookup(unsigned long addr, + unsigned long *symbolsize, + unsigned long *offset, + char *namebuf); + +/* Replace "%s" in format with address, if found */ +extern void __print_symbol(const char *fmt, unsigned long address); + +/* This macro allows us to keep printk typechecking */ +static void __check_printsym_format(const char *fmt, ...) + __attribute__((format(printf,1,2))); + static inline void __check_printsym_format(const char *fmt, ...) +{ +} + +/* ia64 and ppc64 use function descriptors, which contain the real address */ +#if defined(CONFIG_IA64) || defined(CONFIG_PPC64) +#define print_fn_descriptor_symbol(fmt, addr) \ +do { \ + unsigned long *__faddr = (unsigned long*) addr; \ + print_symbol(fmt, __faddr[0]); \ +} while (0) +#else +#define print_fn_descriptor_symbol(fmt, addr) print_symbol(fmt, addr) +#endif + +#define print_symbol(fmt, addr) \ +do { \ + __check_printsym_format(fmt, ""); \ + __print_symbol(fmt, addr); \ +} while(0) + +#endif /*_XEN_SYMBOLS_H*/ diff -r 460405b4723b -r dc7c14e533c2 xen/tools/symbols.c --- /dev/null Fri Jul 22 15:32:31 2005 +++ b/xen/tools/symbols.c Fri Jul 22 17:58:52 2005 @@ -0,0 +1,716 @@ +/* Generate assembler source containing symbol information + * + * Copyright 2002 by Kai Germaschewski + * + * This software may be used and distributed according to the terms + * of the GNU General Public License, incorporated herein by reference. + * + * Usage: nm -n <object-file> | scripts/symbols [--all-symbols] > symbols.S + * + * ChangeLog: + * + * (25/Aug/2004) Paulo Marques <pmarques@xxxxxxxxxxxx> + * 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> +#include <stdlib.h> +#include <string.h> +#include <ctype.h> + +/* 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 */ +#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 + +struct sym_entry { + unsigned long long addr; + char type; + unsigned char flags; + unsigned char len; + unsigned char *sym; +}; + + +static struct sym_entry *table; +static int size, cnt; +static unsigned long long _stext, _etext; +static int all_symbols = 0; +static char symbol_prefix_char = '\0'; + +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; /* 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]; + + +static void +usage(void) +{ + fprintf(stderr, "Usage: symbols [--all-symbols] [--symbol-prefix=<prefix char>] < in.map > out.S\n"); + exit(1); +} + +/* + * This ignores the intensely annoying "mapping symbols" found + * in ARM ELF files: $a, $t and $d. + */ +static inline int +is_arm_mapping_symbol(const char *str) +{ + return str[0] == '$' && strchr("atd", str[1]) + && (str[2] == '\0' || str[2] == '.'); +} + +static int +read_symbol(FILE *in, struct sym_entry *s) +{ + char str[500]; + char *sym; + int rc; + + rc = fscanf(in, "%llx %c %499s\n", &s->addr, &s->type, str); + if (rc != 3) { + if (rc != EOF) { + /* skip line */ + fgets(str, 500, in); + } + return -1; + } + + sym = str; + /* skip prefix char */ + if (symbol_prefix_char && str[0] == symbol_prefix_char) + sym++; + + /* Ignore most absolute/undefined (?) symbols. */ + if (strcmp(sym, "_stext") == 0) + _stext = s->addr; + else if (strcmp(sym, "_etext") == 0) + _etext = s->addr; + else if (toupper(s->type) == 'A') + { + /* Keep these useful absolute symbols */ + if (strcmp(sym, "__kernel_syscall_via_break") && + strcmp(sym, "__kernel_syscall_via_epc") && + strcmp(sym, "__kernel_sigtramp") && + strcmp(sym, "__gp")) + return -1; + + } + else if (toupper(s->type) == 'U' || + is_arm_mapping_symbol(sym)) + return -1; + + /* include the type field in the symbol name, so that it gets + * compressed together */ + s->len = strlen(str) + 1; + s->sym = (char *) malloc(s->len + 1); + strcpy(s->sym + 1, str); + s->sym[0] = s->type; + + return 0; +} + +static int +symbol_valid(struct sym_entry *s) +{ + /* Symbols which vary between passes. Passes 1 and 2 must have + * identical symbol lists. The symbols_* symbols below are only added + * after pass 1, they would be included in pass 2 when --all-symbols is + * specified so exclude them to get a stable symbol list. + */ + static char *special_symbols[] = { + "symbols_addresses", + "symbols_num_syms", + "symbols_names", + "symbols_markers", + "symbols_token_table", + "symbols_token_index", + + /* Exclude linker generated symbols which vary between passes */ + "_SDA_BASE_", /* ppc */ + "_SDA2_BASE_", /* ppc */ + NULL }; + int i; + int offset = 1; + + /* skip prefix char */ + if (symbol_prefix_char && *(s->sym + 1) == symbol_prefix_char) + offset++; + + /* if --all-symbols is not specified, then symbols outside the text + * and inittext sections are discarded */ + if (!all_symbols) { + if (s->addr < _stext || s->addr > _etext) + return 0; + /* Corner case. Discard any symbols with the same value as + * _etext _einittext or _eextratext; they can move between pass + * 1 and 2 when the symbols data are added. If these symbols + * move then they may get dropped in pass 2, which breaks the + * symbols rules. + */ + if (s->addr == _etext && strcmp(s->sym + offset, "_etext")) + return 0; + } + + /* Exclude symbols which vary between passes. */ + if (strstr(s->sym + offset, "_compiled.")) + return 0; + + for (i = 0; special_symbols[i]; i++) + if( strcmp(s->sym + offset, special_symbols[i]) == 0 ) + return 0; + + return 1; +} + +static void +read_map(FILE *in) +{ + while (!feof(in)) { + if (cnt >= size) { + size += 10000; + table = realloc(table, sizeof(*table) * size); + if (!table) { + fprintf(stderr, "out of memory\n"); + exit (1); + } + } + if (read_symbol(in, &table[cnt]) == 0) + cnt++; + } +} + +static void output_label(char *label) +{ + if (symbol_prefix_char) + printf(".globl %c%s\n", symbol_prefix_char, label); + else + printf(".globl %s\n", label); + printf("\tALGN\n"); + if (symbol_prefix_char) + printf("%c%s:\n", symbol_prefix_char, label); + else + 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; + } + data++; + len--; + } + *result=0; + + return total; +} + +static void +write_src(void) +{ + int i, k, off, valid; + unsigned int best_idx[256]; + unsigned int *markers; + char buf[KSYM_NAME_LEN+1]; + + printf("#include <asm/types.h>\n"); + printf("#if BITS_PER_LONG == 64\n"); + printf("#define PTR .quad\n"); + printf("#define ALGN .align 8\n"); + printf("#else\n"); + printf("#define PTR .long\n"); + printf("#define ALGN .align 4\n"); + printf("#endif\n"); + + printf(".data\n"); + + output_label("symbols_addresses"); + valid = 0; + for (i = 0; i < cnt; i++) { + if (table[i].flags & SYM_FLAG_VALID) { + printf("\tPTR\t%#llx\n", table[i].addr); + valid++; + } + } + printf("\n"); + + output_label("symbols_num_syms"); + 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("symbols_names"); + valid = 0; + off = 0; + for (i = 0; i < cnt; i++) { + + if (!table[i].flags & SYM_FLAG_VALID) + continue; + + if ((valid & 0xFF) == 0) + markers[valid >> 8] = off; + + printf("\t.byte 0x%02x", table[i].len); + for (k = 0; k < table[i].len; k++) + printf(", 0x%02x", table[i].sym[k]); + printf("\n"); + + off += table[i].len + 1; + valid++; + } + printf("\n"); + + output_label("symbols_markers"); + for (i = 0; i < ((valid + 255) >> 8); i++) + printf("\tPTR\t%d\n", markers[i]); + printf("\n"); + + free(markers); + + output_label("symbols_token_table"); + off = 0; + for (i = 0; i < 256; i++) { + best_idx[i] = off; + expand_symbol(best_table[i],best_table_len[i],buf); + printf("\t.asciz\t\"%s\"\n", buf); + off += strlen(buf) + 1; + } + printf("\n"); + + output_label("symbols_token_index"); + for (i = 0; i < 256; i++) + printf("\t.short\t%d\n", best_idx[i]); + printf("\n"); +} + + +/* table lookup compression functions */ + +static inline unsigned int rehash_token(unsigned int hash, unsigned char data) +{ + return ((hash * 16777619) ^ data); +} + +static unsigned int hash_token(unsigned char *data, int len) +{ + unsigned int hash=HASH_BASE_OFFSET; + int i; + + for (i = 0; i < len; i++) + hash = rehash_token(hash, data[i]); + + 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; + + ptr = hash_table[hash]; + + while (ptr) { + if ((ptr->len == len) && (memcmp(ptr->data, data, len) == 0)) + return ptr; + ptr=ptr->next; + } + + return NULL; +} + +static inline void insert_token_in_group(struct token *head, struct token *ptr) +{ + ptr->right = head->right; + ptr->right->left = ptr; + head->right = ptr; + ptr->left = head; +} + +static inline void remove_token_from_group(struct token *ptr) +{ + ptr->left->right = ptr->right; + 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; + int i, newprofit; + unsigned int hash = HASH_BASE_OFFSET; + unsigned int hashes[MAX_TOK_SIZE + 1]; + + 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]); + hashes[i] = HASH_FOLD(hash); + } + + last_ptr = NULL; + ptr = NULL; + + for (i = len; i >= 2; i--) { + hash = hashes[i]; + + 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; + + insert_token_in_group(&bad_head, ptr); + + 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; + } + + if (last_ptr) last_ptr->smaller = ptr; + last_ptr = ptr; + + ptr = ptr->smaller; + } +} + +/* 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; + int i, newprofit; + unsigned int hash=0; + + if (len > MAX_TOK_SIZE) len = MAX_TOK_SIZE; + + hash = hash_token(data, len); + ptr = find_token_hash(data, len, hash); + + for (i = len; i >= 2; i--) { + + newprofit = ptr->profit - (ptr->len - 1); + if ((ptr->profit >= 0) && (newprofit < 0)) { + remove_token_from_group(ptr); + insert_token_in_group(&bad_head, ptr); + } + ptr->profit=newprofit; + + ptr=ptr->smaller; + } +} + +/* count all the possible tokens in a symbol */ +static void learn_symbol(unsigned char *symbol, int len) +{ + int i; + + for (i = 0; i < len - 1; i++) + 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; + + for (i = 0; i < len - 1; i++) + forget_token(symbol + i, len - i); +} + +/* set all the symbol flags and do the initial token count */ +static void build_initial_tok_table(void) +{ + int i, use_it, valid; + + valid = 0; + for (i = 0; i < cnt; i++) { + 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++) { + + /* subsample the available symbols. This method is almost like + * a Bresenham's algorithm to get uniformly distributed samples + * across the symbol table */ + if (table[i].flags & SYM_FLAG_VALID) { + + use_it += WORKING_SET; + + if (use_it >= valid) { + table[i].flags |= SYM_FLAG_SAMPLED; + use_it -= valid; + } + } + 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].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 this symbol was used to count, decrease it */ + if (table[i].flags & SYM_FLAG_SAMPLED) + forget_symbol(table[i].sym, len); + learn = 1; + } + + *p = idx; + size = (len - (p - table[i].sym)) - tlen + 1; + memmove(p + 1, p + tlen, size); + p++; + len -= tlen - 1; + + } while (size >= tlen); + + if(learn) { + table[i].len = 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; + int bestprofit; + + bestprofit=-10000; + + /* failsafe: if the "good" list is empty search from the "bad" list */ + if(good_head.right == &good_head) head = &bad_head; + else head = &good_head; + + ptr = head->right; + best = NULL; + while (ptr != head) { + if (ptr->profit > bestprofit) { + bestprofit = ptr->profit; + best = ptr; + } + ptr = ptr->right; + } + + 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 */ + 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; + + memset(best_table, 0, sizeof(best_table)); + memset(best_table_len, 0, sizeof(best_table_len)); + + for (i = 0; i < cnt; i++) { + 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; + best_table_len[c]=1; + } + } + } +} + +static void optimize_token_table(void) +{ + memset(hash_table, 0, sizeof(hash_table)); + + good_head.left = &good_head; + good_head.right = &good_head; + + bad_head.left = &bad_head; + bad_head.right = &bad_head; + + build_initial_tok_table(); + + insert_real_symbols_in_table(); + + /* When valid symbol is not registered, exit to error */ + if (good_head.left == good_head.right && + bad_head.left == bad_head.right) { + fprintf(stderr, "No valid symbol.\n"); + exit(1); + } + + optimize_result(); +} + + +int +main(int argc, char **argv) +{ + if (argc >= 2) { + int i; + for (i = 1; i < argc; i++) { + if(strcmp(argv[i], "--all-symbols") == 0) + all_symbols = 1; + else if (strncmp(argv[i], "--symbol-prefix=", 16) == 0) { + char *p = &argv[i][16]; + /* skip quote */ + if ((*p == '"' && *(p+2) == '"') || (*p == '\'' && *(p+2) == '\'')) + p++; + symbol_prefix_char = *p; + } else + usage(); + } + } else if (argc != 1) + usage(); + + read_map(stdin); + optimize_token_table(); + write_src(); + + return 0; +} diff -r 460405b4723b -r dc7c14e533c2 xen/common/symbols.c --- /dev/null Fri Jul 22 15:32:31 2005 +++ b/xen/common/symbols.c Fri Jul 22 17:58:52 2005 @@ -0,0 +1,158 @@ +/* + * symbols.c: in-kernel printing of symbolic oopses and stack traces. + * + * Copyright 2002 Rusty Russell <rusty@xxxxxxxxxxxxxxx> IBM Corporation + * + * ChangeLog: + * + * (25/Aug/2004) Paulo Marques <pmarques@xxxxxxxxxxxx> + * Changed the compression method from stem compression to "table lookup" + * compression (see tools/symbols.c for a more complete description) + */ + +#include <xen/config.h> +#include <xen/symbols.h> +#include <xen/init.h> +#include <xen/lib.h> +#include <xen/string.h> + +/* These will be re-linked against their real values during the second link stage */ +extern unsigned long symbols_addresses[] __attribute__((weak)); +extern unsigned long symbols_num_syms __attribute__((weak,section("data"))); +extern u8 symbols_names[] __attribute__((weak)); + +extern u8 symbols_token_table[] __attribute__((weak)); +extern u16 symbols_token_index[] __attribute__((weak)); + +extern unsigned long symbols_markers[] __attribute__((weak)); + +/* 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 symbols_expand_symbol(unsigned int off, char *result) +{ + int len, skipped_first = 0; + u8 *tptr, *data; + + /* get the compressed symbol length from the first symbol byte */ + data = &symbols_names[off]; + len = *data; + 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 = &symbols_token_table[ symbols_token_index[*data] ]; + data++; + len--; + + while (*tptr) { + if(skipped_first) { + *result = *tptr; + result++; + } else + skipped_first = 1; + tptr++; + } + } + + *result = '\0'; + + /* return to offset to the next symbol */ + return off; +} + +/* find the offset on the compressed stream given and index in the + * symbols 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 = &symbols_names[ symbols_markers[pos>>8] ]; + + /* sequentially scan all the symbols up to the point we're searching for. + * Every symbol is stored in a [<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; + + return name - symbols_names; +} + +const char *symbols_lookup(unsigned long addr, + unsigned long *symbolsize, + unsigned long *offset, + char *namebuf) +{ + unsigned long i, low, high, mid; + unsigned long symbol_end = 0; + + /* This kernel should never had been booted. */ + BUG_ON(!symbols_addresses); + + namebuf[KSYM_NAME_LEN] = 0; + namebuf[0] = 0; + + if (!is_kernel_text(addr)) + return NULL; + + /* do a binary search on the sorted symbols_addresses array */ + low = 0; + high = symbols_num_syms; + + while (high-low > 1) { + mid = (low + high) / 2; + if (symbols_addresses[mid] <= addr) low = mid; + else high = mid; + } + + /* search for the first aliased symbol. Aliased symbols are + symbols with the same address */ + while (low && symbols_addresses[low - 1] == symbols_addresses[low]) + --low; + + /* Grab name */ + symbols_expand_symbol(get_symbol_offset(low), namebuf); + + /* Search for next non-aliased symbol */ + for (i = low + 1; i < symbols_num_syms; i++) { + if (symbols_addresses[i] > symbols_addresses[low]) { + symbol_end = symbols_addresses[i]; + break; + } + } + + /* if we found no next symbol, we use the end of the section */ + if (!symbol_end) + symbol_end = kernel_text_end(); + + *symbolsize = symbol_end - symbols_addresses[low]; + *offset = addr - symbols_addresses[low]; + return namebuf; +} + +/* Replace "%s" in format with address, or returns -errno. */ +void __print_symbol(const char *fmt, unsigned long address) +{ + const char *name; + unsigned long offset, size; + char namebuf[KSYM_NAME_LEN+1]; + char buffer[sizeof("%s+%#lx/%#lx [%s]") + KSYM_NAME_LEN + + 2*(BITS_PER_LONG*3/10) + 1]; + + name = symbols_lookup(address, &size, &offset, namebuf); + + if (!name) + sprintf(buffer, "???"); + else + sprintf(buffer, "%s+%#lx/%#lx", name, offset, size); + + printk(fmt, buffer); +} _______________________________________________ Xen-changelog mailing list Xen-changelog@xxxxxxxxxxxxxxxxxxx http://lists.xensource.com/xen-changelog
|
![]() |
Lists.xenproject.org is hosted with RackSpace, monitoring our |