1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* Generate kernel symbol version hashes.
3 Copyright 1996, 1997 Linux International.
5 New implementation contributed by Richard Henderson <rth@tamu.edu>
6 Based on original work by Bjorn Ekwall <bj0rn@blox.se>
8 This file was part of the Linux modutils 2.4.22: moved back into the
9 kernel sources by Rusty Russell/Kai Germaschewski.
22 /*----------------------------------------------------------------------*/
24 #define HASH_BUCKETS 4096
26 static struct symbol *symtab[HASH_BUCKETS];
27 static FILE *debugfile;
33 static int flag_debug, flag_dump_defs, flag_reference, flag_dump_types,
34 flag_preserve, flag_warnings;
39 static struct symbol *expansion_trail;
40 static struct symbol *visited_symbols;
46 [SYM_NORMAL] = { 0, NULL},
47 [SYM_TYPEDEF] = {'t', "typedef"},
48 [SYM_ENUM] = {'e', "enum"},
49 [SYM_STRUCT] = {'s', "struct"},
50 [SYM_UNION] = {'u', "union"},
51 [SYM_ENUM_CONST] = {'E', "enum constant"},
54 static int equal_list(struct string_list *a, struct string_list *b);
55 static void print_list(FILE * f, struct string_list *list);
56 static struct string_list *concat_list(struct string_list *start, ...);
57 static struct string_list *mk_node(const char *string);
58 static void print_location(void);
59 static void print_type_name(enum symbol_type type, const char *name);
61 /*----------------------------------------------------------------------*/
63 static const unsigned int crctab32[] = {
64 0x00000000U, 0x77073096U, 0xee0e612cU, 0x990951baU, 0x076dc419U,
65 0x706af48fU, 0xe963a535U, 0x9e6495a3U, 0x0edb8832U, 0x79dcb8a4U,
66 0xe0d5e91eU, 0x97d2d988U, 0x09b64c2bU, 0x7eb17cbdU, 0xe7b82d07U,
67 0x90bf1d91U, 0x1db71064U, 0x6ab020f2U, 0xf3b97148U, 0x84be41deU,
68 0x1adad47dU, 0x6ddde4ebU, 0xf4d4b551U, 0x83d385c7U, 0x136c9856U,
69 0x646ba8c0U, 0xfd62f97aU, 0x8a65c9ecU, 0x14015c4fU, 0x63066cd9U,
70 0xfa0f3d63U, 0x8d080df5U, 0x3b6e20c8U, 0x4c69105eU, 0xd56041e4U,
71 0xa2677172U, 0x3c03e4d1U, 0x4b04d447U, 0xd20d85fdU, 0xa50ab56bU,
72 0x35b5a8faU, 0x42b2986cU, 0xdbbbc9d6U, 0xacbcf940U, 0x32d86ce3U,
73 0x45df5c75U, 0xdcd60dcfU, 0xabd13d59U, 0x26d930acU, 0x51de003aU,
74 0xc8d75180U, 0xbfd06116U, 0x21b4f4b5U, 0x56b3c423U, 0xcfba9599U,
75 0xb8bda50fU, 0x2802b89eU, 0x5f058808U, 0xc60cd9b2U, 0xb10be924U,
76 0x2f6f7c87U, 0x58684c11U, 0xc1611dabU, 0xb6662d3dU, 0x76dc4190U,
77 0x01db7106U, 0x98d220bcU, 0xefd5102aU, 0x71b18589U, 0x06b6b51fU,
78 0x9fbfe4a5U, 0xe8b8d433U, 0x7807c9a2U, 0x0f00f934U, 0x9609a88eU,
79 0xe10e9818U, 0x7f6a0dbbU, 0x086d3d2dU, 0x91646c97U, 0xe6635c01U,
80 0x6b6b51f4U, 0x1c6c6162U, 0x856530d8U, 0xf262004eU, 0x6c0695edU,
81 0x1b01a57bU, 0x8208f4c1U, 0xf50fc457U, 0x65b0d9c6U, 0x12b7e950U,
82 0x8bbeb8eaU, 0xfcb9887cU, 0x62dd1ddfU, 0x15da2d49U, 0x8cd37cf3U,
83 0xfbd44c65U, 0x4db26158U, 0x3ab551ceU, 0xa3bc0074U, 0xd4bb30e2U,
84 0x4adfa541U, 0x3dd895d7U, 0xa4d1c46dU, 0xd3d6f4fbU, 0x4369e96aU,
85 0x346ed9fcU, 0xad678846U, 0xda60b8d0U, 0x44042d73U, 0x33031de5U,
86 0xaa0a4c5fU, 0xdd0d7cc9U, 0x5005713cU, 0x270241aaU, 0xbe0b1010U,
87 0xc90c2086U, 0x5768b525U, 0x206f85b3U, 0xb966d409U, 0xce61e49fU,
88 0x5edef90eU, 0x29d9c998U, 0xb0d09822U, 0xc7d7a8b4U, 0x59b33d17U,
89 0x2eb40d81U, 0xb7bd5c3bU, 0xc0ba6cadU, 0xedb88320U, 0x9abfb3b6U,
90 0x03b6e20cU, 0x74b1d29aU, 0xead54739U, 0x9dd277afU, 0x04db2615U,
91 0x73dc1683U, 0xe3630b12U, 0x94643b84U, 0x0d6d6a3eU, 0x7a6a5aa8U,
92 0xe40ecf0bU, 0x9309ff9dU, 0x0a00ae27U, 0x7d079eb1U, 0xf00f9344U,
93 0x8708a3d2U, 0x1e01f268U, 0x6906c2feU, 0xf762575dU, 0x806567cbU,
94 0x196c3671U, 0x6e6b06e7U, 0xfed41b76U, 0x89d32be0U, 0x10da7a5aU,
95 0x67dd4accU, 0xf9b9df6fU, 0x8ebeeff9U, 0x17b7be43U, 0x60b08ed5U,
96 0xd6d6a3e8U, 0xa1d1937eU, 0x38d8c2c4U, 0x4fdff252U, 0xd1bb67f1U,
97 0xa6bc5767U, 0x3fb506ddU, 0x48b2364bU, 0xd80d2bdaU, 0xaf0a1b4cU,
98 0x36034af6U, 0x41047a60U, 0xdf60efc3U, 0xa867df55U, 0x316e8eefU,
99 0x4669be79U, 0xcb61b38cU, 0xbc66831aU, 0x256fd2a0U, 0x5268e236U,
100 0xcc0c7795U, 0xbb0b4703U, 0x220216b9U, 0x5505262fU, 0xc5ba3bbeU,
101 0xb2bd0b28U, 0x2bb45a92U, 0x5cb36a04U, 0xc2d7ffa7U, 0xb5d0cf31U,
102 0x2cd99e8bU, 0x5bdeae1dU, 0x9b64c2b0U, 0xec63f226U, 0x756aa39cU,
103 0x026d930aU, 0x9c0906a9U, 0xeb0e363fU, 0x72076785U, 0x05005713U,
104 0x95bf4a82U, 0xe2b87a14U, 0x7bb12baeU, 0x0cb61b38U, 0x92d28e9bU,
105 0xe5d5be0dU, 0x7cdcefb7U, 0x0bdbdf21U, 0x86d3d2d4U, 0xf1d4e242U,
106 0x68ddb3f8U, 0x1fda836eU, 0x81be16cdU, 0xf6b9265bU, 0x6fb077e1U,
107 0x18b74777U, 0x88085ae6U, 0xff0f6a70U, 0x66063bcaU, 0x11010b5cU,
108 0x8f659effU, 0xf862ae69U, 0x616bffd3U, 0x166ccf45U, 0xa00ae278U,
109 0xd70dd2eeU, 0x4e048354U, 0x3903b3c2U, 0xa7672661U, 0xd06016f7U,
110 0x4969474dU, 0x3e6e77dbU, 0xaed16a4aU, 0xd9d65adcU, 0x40df0b66U,
111 0x37d83bf0U, 0xa9bcae53U, 0xdebb9ec5U, 0x47b2cf7fU, 0x30b5ffe9U,
112 0xbdbdf21cU, 0xcabac28aU, 0x53b39330U, 0x24b4a3a6U, 0xbad03605U,
113 0xcdd70693U, 0x54de5729U, 0x23d967bfU, 0xb3667a2eU, 0xc4614ab8U,
114 0x5d681b02U, 0x2a6f2b94U, 0xb40bbe37U, 0xc30c8ea1U, 0x5a05df1bU,
118 static unsigned long partial_crc32_one(unsigned char c, unsigned long crc)
120 return crctab32[(crc ^ c) & 0xff] ^ (crc >> 8);
123 static unsigned long partial_crc32(const char *s, unsigned long crc)
126 crc = partial_crc32_one(*s++, crc);
130 static unsigned long crc32(const char *s)
132 return partial_crc32(s, 0xffffffff) ^ 0xffffffff;
135 /*----------------------------------------------------------------------*/
137 static enum symbol_type map_to_ns(enum symbol_type t)
152 struct symbol *find_symbol(const char *name, enum symbol_type ns, int exact)
154 unsigned long h = crc32(name) % HASH_BUCKETS;
157 for (sym = symtab[h]; sym; sym = sym->hash_next)
158 if (map_to_ns(sym->type) == map_to_ns(ns) &&
159 strcmp(name, sym->name) == 0 &&
163 if (exact && sym && sym->type != ns)
168 static int is_unknown_symbol(struct symbol *sym)
170 struct string_list *defn;
172 return ((sym->type == SYM_STRUCT ||
173 sym->type == SYM_UNION ||
174 sym->type == SYM_ENUM) &&
175 (defn = sym->defn) && defn->tag == SYM_NORMAL &&
176 strcmp(defn->string, "}") == 0 &&
177 (defn = defn->next) && defn->tag == SYM_NORMAL &&
178 strcmp(defn->string, "UNKNOWN") == 0 &&
179 (defn = defn->next) && defn->tag == SYM_NORMAL &&
180 strcmp(defn->string, "{") == 0);
183 static struct symbol *__add_symbol(const char *name, enum symbol_type type,
184 struct string_list *defn, int is_extern,
189 enum symbol_status status = STATUS_UNCHANGED;
190 /* The parser adds symbols in the order their declaration completes,
191 * so it is safe to store the value of the previous enum constant in
194 static int enum_counter;
195 static struct string_list *last_enum_expr;
197 if (type == SYM_ENUM_CONST) {
199 free_list(last_enum_expr, NULL);
200 last_enum_expr = copy_list_range(defn, NULL);
203 struct string_list *expr;
206 snprintf(buf, sizeof(buf), "%d", enum_counter++);
207 if (last_enum_expr) {
208 expr = copy_list_range(last_enum_expr, NULL);
209 defn = concat_list(mk_node("("),
218 } else if (type == SYM_ENUM) {
219 free_list(last_enum_expr, NULL);
220 last_enum_expr = NULL;
223 /* Anonymous enum definition, nothing more to do */
227 h = crc32(name) % HASH_BUCKETS;
228 for (sym = symtab[h]; sym; sym = sym->hash_next) {
229 if (map_to_ns(sym->type) == map_to_ns(type) &&
230 strcmp(name, sym->name) == 0) {
233 else if (sym->type == type &&
234 equal_list(sym->defn, defn)) {
235 if (!sym->is_declared && sym->is_override) {
237 print_type_name(type, name);
238 fprintf(stderr, " modversion is "
241 sym->is_declared = 1;
243 } else if (!sym->is_declared) {
244 if (sym->is_override && flag_preserve) {
246 fprintf(stderr, "ignoring ");
247 print_type_name(type, name);
248 fprintf(stderr, " modversion change\n");
249 sym->is_declared = 1;
252 status = is_unknown_symbol(sym) ?
253 STATUS_DEFINED : STATUS_MODIFIED;
256 error_with_pos("redefinition of %s", name);
264 struct symbol **psym;
266 for (psym = &symtab[h]; *psym; psym = &(*psym)->hash_next) {
268 *psym = sym->hash_next;
275 sym = xmalloc(sizeof(*sym));
279 sym->expansion_trail = NULL;
281 sym->is_extern = is_extern;
283 sym->hash_next = symtab[h];
286 sym->is_declared = !is_reference;
287 sym->status = status;
288 sym->is_override = 0;
291 if (symbol_types[type].name)
292 fprintf(debugfile, "Defn for %s %s == <",
293 symbol_types[type].name, name);
295 fprintf(debugfile, "Defn for type%d %s == <",
298 fputs("extern ", debugfile);
299 print_list(debugfile, defn);
300 fputs(">\n", debugfile);
307 struct symbol *add_symbol(const char *name, enum symbol_type type,
308 struct string_list *defn, int is_extern)
310 return __add_symbol(name, type, defn, is_extern, 0);
313 static struct symbol *add_reference_symbol(const char *name, enum symbol_type type,
314 struct string_list *defn, int is_extern)
316 return __add_symbol(name, type, defn, is_extern, 1);
319 /*----------------------------------------------------------------------*/
321 void free_node(struct string_list *node)
327 void free_list(struct string_list *s, struct string_list *e)
330 struct string_list *next = s->next;
336 static struct string_list *mk_node(const char *string)
338 struct string_list *newnode;
340 newnode = xmalloc(sizeof(*newnode));
341 newnode->string = xstrdup(string);
342 newnode->tag = SYM_NORMAL;
343 newnode->next = NULL;
348 static struct string_list *concat_list(struct string_list *start, ...)
351 struct string_list *n, *n2;
355 for (va_start(ap, start); (n = va_arg(ap, struct string_list *));) {
356 for (n2 = n; n2->next; n2 = n2->next)
365 struct string_list *copy_node(struct string_list *node)
367 struct string_list *newnode;
369 newnode = xmalloc(sizeof(*newnode));
370 newnode->string = xstrdup(node->string);
371 newnode->tag = node->tag;
376 struct string_list *copy_list_range(struct string_list *start,
377 struct string_list *end)
379 struct string_list *res, *n;
383 n = res = copy_node(start);
384 for (start = start->next; start != end; start = start->next) {
385 n->next = copy_node(start);
392 static int equal_list(struct string_list *a, struct string_list *b)
395 if (a->tag != b->tag || strcmp(a->string, b->string))
404 #define ARRAY_SIZE(arr) (sizeof(arr) / sizeof((arr)[0]))
406 static struct string_list *read_node(FILE *f)
409 struct string_list node = {
412 int c, in_string = 0;
414 while ((c = fgetc(f)) != EOF) {
415 if (!in_string && c == ' ') {
416 if (node.string == buffer)
419 } else if (c == '"') {
420 in_string = !in_string;
421 } else if (c == '\n') {
422 if (node.string == buffer)
427 if (node.string >= buffer + sizeof(buffer) - 1) {
428 fprintf(stderr, "Token too long\n");
433 if (node.string == buffer)
436 node.string = buffer;
438 if (node.string[1] == '#') {
441 for (n = 0; n < ARRAY_SIZE(symbol_types); n++) {
442 if (node.string[0] == symbol_types[n].n) {
445 return copy_node(&node);
448 fprintf(stderr, "Unknown type %c\n", node.string[0]);
451 return copy_node(&node);
454 static void read_reference(FILE *f)
457 struct string_list *defn = NULL;
458 struct string_list *sym, *def;
459 int is_extern = 0, is_override = 0;
460 struct symbol *subsym;
463 if (sym && sym->tag == SYM_NORMAL &&
464 !strcmp(sym->string, "override")) {
472 if (def && def->tag == SYM_NORMAL &&
473 !strcmp(def->string, "extern")) {
483 subsym = add_reference_symbol(xstrdup(sym->string), sym->tag,
485 subsym->is_override = is_override;
490 static void print_node(FILE * f, struct string_list *list)
492 if (symbol_types[list->tag].n) {
493 putc(symbol_types[list->tag].n, f);
496 fputs(list->string, f);
499 static void print_list(FILE * f, struct string_list *list)
501 struct string_list **e, **b;
502 struct string_list *tmp, **tmp2;
511 while ((tmp = tmp->next) != NULL)
514 b = alloca(elem * sizeof(*e));
519 while ((list = list->next) != NULL)
528 static unsigned long expand_and_crc_sym(struct symbol *sym, unsigned long crc)
530 struct string_list *list = sym->defn;
531 struct string_list **e, **b;
532 struct string_list *tmp, **tmp2;
539 while ((tmp = tmp->next) != NULL)
542 b = alloca(elem * sizeof(*e));
547 while ((list = list->next) != NULL)
551 struct string_list *cur;
552 struct symbol *subsym;
558 fprintf(debugfile, "%s ", cur->string);
559 crc = partial_crc32(cur->string, crc);
560 crc = partial_crc32_one(' ', crc);
565 subsym = find_symbol(cur->string, cur->tag, 0);
566 /* FIXME: Bad reference files can segfault here. */
567 if (subsym->expansion_trail) {
569 fprintf(debugfile, "%s ", cur->string);
570 crc = partial_crc32(cur->string, crc);
571 crc = partial_crc32_one(' ', crc);
573 subsym->expansion_trail = expansion_trail;
574 expansion_trail = subsym;
575 crc = expand_and_crc_sym(subsym, crc);
582 subsym = find_symbol(cur->string, cur->tag, 0);
584 struct string_list *n;
586 error_with_pos("expand undefined %s %s",
587 symbol_types[cur->tag].name,
589 n = concat_list(mk_node
590 (symbol_types[cur->tag].name),
591 mk_node(cur->string),
596 add_symbol(cur->string, cur->tag, n, 0);
598 if (subsym->expansion_trail) {
599 if (flag_dump_defs) {
600 fprintf(debugfile, "%s %s ",
601 symbol_types[cur->tag].name,
605 crc = partial_crc32(symbol_types[cur->tag].name,
607 crc = partial_crc32_one(' ', crc);
608 crc = partial_crc32(cur->string, crc);
609 crc = partial_crc32_one(' ', crc);
611 subsym->expansion_trail = expansion_trail;
612 expansion_trail = subsym;
613 crc = expand_and_crc_sym(subsym, crc);
620 static struct symbol **end = &visited_symbols;
625 sym->visited = (struct symbol *)-1L;
632 void export_symbol(const char *name)
636 sym = find_symbol(name, SYM_NORMAL, 0);
638 error_with_pos("export undefined symbol %s", name);
644 fprintf(debugfile, "Export %s == <", name);
646 expansion_trail = (struct symbol *)-1L;
648 sym->expansion_trail = expansion_trail;
649 expansion_trail = sym;
650 crc = expand_and_crc_sym(sym, 0xffffffff) ^ 0xffffffff;
652 sym = expansion_trail;
653 while (sym != (struct symbol *)-1L) {
654 struct symbol *n = sym->expansion_trail;
656 if (sym->status != STATUS_UNCHANGED) {
659 fprintf(stderr, "%s: %s: modversion "
660 "changed because of changes "
661 "in ", flag_preserve ? "error" :
664 fprintf(stderr, ", ");
665 print_type_name(sym->type, sym->name);
666 if (sym->status == STATUS_DEFINED)
667 fprintf(stderr, " (became defined)");
672 sym->expansion_trail = 0;
676 fprintf(stderr, "\n");
679 fputs(">\n", debugfile);
681 printf("#SYMVER %s 0x%08lx\n", name, crc);
685 /*----------------------------------------------------------------------*/
687 static void print_location(void)
689 fprintf(stderr, "%s:%d: ", cur_filename ? : "<stdin>", cur_line);
692 static void print_type_name(enum symbol_type type, const char *name)
694 if (symbol_types[type].name)
695 fprintf(stderr, "%s %s", symbol_types[type].name, name);
697 fprintf(stderr, "%s", name);
700 void error_with_pos(const char *fmt, ...)
708 vfprintf(stderr, fmt, args);
716 static void genksyms_usage(void)
718 fputs("Usage:\n" "genksyms [-adDTwqhVR] > /path/to/.tmp_obj.ver\n" "\n"
719 " -d, --debug Increment the debug level (repeatable)\n"
720 " -D, --dump Dump expanded symbol defs (for debugging only)\n"
721 " -r, --reference file Read reference symbols from a file\n"
722 " -T, --dump-types file Dump expanded types into file\n"
723 " -p, --preserve Preserve reference modversions or fail\n"
724 " -w, --warnings Enable warnings\n"
725 " -q, --quiet Disable warnings (default)\n"
726 " -h, --help Print this message\n"
727 " -V, --version Print the release version\n"
731 int main(int argc, char **argv)
733 FILE *dumpfile = NULL, *ref_file = NULL;
736 struct option long_opts[] = {
737 {"debug", 0, 0, 'd'},
738 {"warnings", 0, 0, 'w'},
739 {"quiet", 0, 0, 'q'},
741 {"reference", 1, 0, 'r'},
742 {"dump-types", 1, 0, 'T'},
743 {"preserve", 0, 0, 'p'},
744 {"version", 0, 0, 'V'},
749 while ((o = getopt_long(argc, argv, "dwqVDr:T:ph",
750 &long_opts[0], NULL)) != EOF)
762 fputs("genksyms version 2.5.60\n", stderr);
769 ref_file = fopen(optarg, "r");
777 dumpfile = fopen(optarg, "w");
795 extern int yy_flex_debug;
797 yydebug = (flag_debug > 1);
798 yy_flex_debug = (flag_debug > 2);
801 /* setlinebuf(debugfile); */
804 if (flag_reference) {
805 read_reference(ref_file);
811 if (flag_dump_types && visited_symbols) {
812 while (visited_symbols != (struct symbol *)-1L) {
813 struct symbol *sym = visited_symbols;
815 if (sym->is_override)
816 fputs("override ", dumpfile);
817 if (symbol_types[sym->type].n) {
818 putc(symbol_types[sym->type].n, dumpfile);
821 fputs(sym->name, dumpfile);
824 fputs("extern ", dumpfile);
825 print_list(dumpfile, sym->defn);
826 putc('\n', dumpfile);
828 visited_symbols = sym->visited;
834 fprintf(debugfile, "Hash table occupancy %d/%d = %g\n",
836 (double)nsyms / (double)HASH_BUCKETS);