path: root/scripts/kallsyms.c

/* 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 vmlinux | scripts/kallsyms [--all-symbols] > symbols.S
 *
 * ChangeLog:
 *
 * (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>
#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, _sinittext, _einittext, _sextratext, _eextratext;
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: kallsyms [--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 (strcmp(sym, "_sinittext") == 0)
		_sinittext = s->addr;
	else if (strcmp(sym, "_einittext") == 0)
		_einittext = s->addr;
	else if (strcmp(sym, "_sextratext") == 0)
		_sextratext = s->addr;
	else if (strcmp(sym, "_eextratext") == 0)
		_eextratext = 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 kallsyms_* 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[] = {
		"kallsyms_addresses",
		"kallsyms_num_syms",
		"kallsyms_names",
		"kallsyms_markers",
		"kallsyms_token_table",
		"kallsyms_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)
		    && (s->addr < _sinittext || s->addr > _einittext)
		    && (s->addr < _sextratext || s->addr > _eextratext))
			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 kallsyms data are added.  If these symbols
		 * move then they may get dropped in pass 2, which breaks the
		 * kallsyms rules.
		 */
		if ((s->addr == _etext && strcmp((char*)s->sym + offset, "_etext")) ||
		    (s->addr == _einittext && strcmp((char