1 /* Generate kernel symbol version hashes. 2 Copyright 1996, 1997 Linux International. 3 4 New implementation contributed by Richard Henderson <rth@tamu.edu> 5 Based on original work by Bjorn Ekwall <bj0rn@blox.se> 6 7 This file was part of the Linux modutils 2.4.22: moved back into the 8 kernel sources by Rusty Russell/Kai Germaschewski. 9 10 This program is free software; you can redistribute it and/or modify it 11 under the terms of the GNU General Public License as published by the 12 Free Software Foundation; either version 2 of the License, or (at your 13 option) any later version. 14 15 This program is distributed in the hope that it will be useful, but 16 WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 18 General Public License for more details. 19 20 You should have received a copy of the GNU General Public License 21 along with this program; if not, write to the Free Software Foundation, 22 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 23 24 #include <stdio.h> 25 #include <string.h> 26 #include <stdlib.h> 27 #include <unistd.h> 28 #include <assert.h> 29 #include <stdarg.h> 30 #ifdef __GNU_LIBRARY__ 31 #include <getopt.h> 32 #endif /* __GNU_LIBRARY__ */ 33 34 #include "genksyms.h" 35 /*----------------------------------------------------------------------*/ 36 37 #define HASH_BUCKETS 4096 38 39 static struct symbol *symtab[HASH_BUCKETS]; 40 static FILE *debugfile; 41 42 int cur_line = 1; 43 char *cur_filename; 44 45 static int flag_debug, flag_dump_defs, flag_dump_types, flag_warnings; 46 static const char *arch = ""; 47 static const char *mod_prefix = ""; 48 49 static int errors; 50 static int nsyms; 51 52 static struct symbol *expansion_trail; 53 static struct symbol *visited_symbols; 54 55 static const char *const symbol_type_name[] = { 56 "normal", "typedef", "enum", "struct", "union" 57 }; 58 59 static int equal_list(struct string_list *a, struct string_list *b); 60 static void print_list(FILE * f, struct string_list *list); 61 62 /*----------------------------------------------------------------------*/ 63 64 static const unsigned int crctab32[] = { 65 0x00000000U, 0x77073096U, 0xee0e612cU, 0x990951baU, 0x076dc419U, 66 0x706af48fU, 0xe963a535U, 0x9e6495a3U, 0x0edb8832U, 0x79dcb8a4U, 67 0xe0d5e91eU, 0x97d2d988U, 0x09b64c2bU, 0x7eb17cbdU, 0xe7b82d07U, 68 0x90bf1d91U, 0x1db71064U, 0x6ab020f2U, 0xf3b97148U, 0x84be41deU, 69 0x1adad47dU, 0x6ddde4ebU, 0xf4d4b551U, 0x83d385c7U, 0x136c9856U, 70 0x646ba8c0U, 0xfd62f97aU, 0x8a65c9ecU, 0x14015c4fU, 0x63066cd9U, 71 0xfa0f3d63U, 0x8d080df5U, 0x3b6e20c8U, 0x4c69105eU, 0xd56041e4U, 72 0xa2677172U, 0x3c03e4d1U, 0x4b04d447U, 0xd20d85fdU, 0xa50ab56bU, 73 0x35b5a8faU, 0x42b2986cU, 0xdbbbc9d6U, 0xacbcf940U, 0x32d86ce3U, 74 0x45df5c75U, 0xdcd60dcfU, 0xabd13d59U, 0x26d930acU, 0x51de003aU, 75 0xc8d75180U, 0xbfd06116U, 0x21b4f4b5U, 0x56b3c423U, 0xcfba9599U, 76 0xb8bda50fU, 0x2802b89eU, 0x5f058808U, 0xc60cd9b2U, 0xb10be924U, 77 0x2f6f7c87U, 0x58684c11U, 0xc1611dabU, 0xb6662d3dU, 0x76dc4190U, 78 0x01db7106U, 0x98d220bcU, 0xefd5102aU, 0x71b18589U, 0x06b6b51fU, 79 0x9fbfe4a5U, 0xe8b8d433U, 0x7807c9a2U, 0x0f00f934U, 0x9609a88eU, 80 0xe10e9818U, 0x7f6a0dbbU, 0x086d3d2dU, 0x91646c97U, 0xe6635c01U, 81 0x6b6b51f4U, 0x1c6c6162U, 0x856530d8U, 0xf262004eU, 0x6c0695edU, 82 0x1b01a57bU, 0x8208f4c1U, 0xf50fc457U, 0x65b0d9c6U, 0x12b7e950U, 83 0x8bbeb8eaU, 0xfcb9887cU, 0x62dd1ddfU, 0x15da2d49U, 0x8cd37cf3U, 84 0xfbd44c65U, 0x4db26158U, 0x3ab551ceU, 0xa3bc0074U, 0xd4bb30e2U, 85 0x4adfa541U, 0x3dd895d7U, 0xa4d1c46dU, 0xd3d6f4fbU, 0x4369e96aU, 86 0x346ed9fcU, 0xad678846U, 0xda60b8d0U, 0x44042d73U, 0x33031de5U, 87 0xaa0a4c5fU, 0xdd0d7cc9U, 0x5005713cU, 0x270241aaU, 0xbe0b1010U, 88 0xc90c2086U, 0x5768b525U, 0x206f85b3U, 0xb966d409U, 0xce61e49fU, 89 0x5edef90eU, 0x29d9c998U, 0xb0d09822U, 0xc7d7a8b4U, 0x59b33d17U, 90 0x2eb40d81U, 0xb7bd5c3bU, 0xc0ba6cadU, 0xedb88320U, 0x9abfb3b6U, 91 0x03b6e20cU, 0x74b1d29aU, 0xead54739U, 0x9dd277afU, 0x04db2615U, 92 0x73dc1683U, 0xe3630b12U, 0x94643b84U, 0x0d6d6a3eU, 0x7a6a5aa8U, 93 0xe40ecf0bU, 0x9309ff9dU, 0x0a00ae27U, 0x7d079eb1U, 0xf00f9344U, 94 0x8708a3d2U, 0x1e01f268U, 0x6906c2feU, 0xf762575dU, 0x806567cbU, 95 0x196c3671U, 0x6e6b06e7U, 0xfed41b76U, 0x89d32be0U, 0x10da7a5aU, 96 0x67dd4accU, 0xf9b9df6fU, 0x8ebeeff9U, 0x17b7be43U, 0x60b08ed5U, 97 0xd6d6a3e8U, 0xa1d1937eU, 0x38d8c2c4U, 0x4fdff252U, 0xd1bb67f1U, 98 0xa6bc5767U, 0x3fb506ddU, 0x48b2364bU, 0xd80d2bdaU, 0xaf0a1b4cU, 99 0x36034af6U, 0x41047a60U, 0xdf60efc3U, 0xa867df55U, 0x316e8eefU, 100 0x4669be79U, 0xcb61b38cU, 0xbc66831aU, 0x256fd2a0U, 0x5268e236U, 101 0xcc0c7795U, 0xbb0b4703U, 0x220216b9U, 0x5505262fU, 0xc5ba3bbeU, 102 0xb2bd0b28U, 0x2bb45a92U, 0x5cb36a04U, 0xc2d7ffa7U, 0xb5d0cf31U, 103 0x2cd99e8bU, 0x5bdeae1dU, 0x9b64c2b0U, 0xec63f226U, 0x756aa39cU, 104 0x026d930aU, 0x9c0906a9U, 0xeb0e363fU, 0x72076785U, 0x05005713U, 105 0x95bf4a82U, 0xe2b87a14U, 0x7bb12baeU, 0x0cb61b38U, 0x92d28e9bU, 106 0xe5d5be0dU, 0x7cdcefb7U, 0x0bdbdf21U, 0x86d3d2d4U, 0xf1d4e242U, 107 0x68ddb3f8U, 0x1fda836eU, 0x81be16cdU, 0xf6b9265bU, 0x6fb077e1U, 108 0x18b74777U, 0x88085ae6U, 0xff0f6a70U, 0x66063bcaU, 0x11010b5cU, 109 0x8f659effU, 0xf862ae69U, 0x616bffd3U, 0x166ccf45U, 0xa00ae278U, 110 0xd70dd2eeU, 0x4e048354U, 0x3903b3c2U, 0xa7672661U, 0xd06016f7U, 111 0x4969474dU, 0x3e6e77dbU, 0xaed16a4aU, 0xd9d65adcU, 0x40df0b66U, 112 0x37d83bf0U, 0xa9bcae53U, 0xdebb9ec5U, 0x47b2cf7fU, 0x30b5ffe9U, 113 0xbdbdf21cU, 0xcabac28aU, 0x53b39330U, 0x24b4a3a6U, 0xbad03605U, 114 0xcdd70693U, 0x54de5729U, 0x23d967bfU, 0xb3667a2eU, 0xc4614ab8U, 115 0x5d681b02U, 0x2a6f2b94U, 0xb40bbe37U, 0xc30c8ea1U, 0x5a05df1bU, 116 0x2d02ef8dU 117 }; 118 119 static unsigned long partial_crc32_one(unsigned char c, unsigned long crc) 120 { 121 return crctab32[(crc ^ c) & 0xff] ^ (crc >> 8); 122 } 123 124 static unsigned long partial_crc32(const char *s, unsigned long crc) 125 { 126 while (*s) 127 crc = partial_crc32_one(*s++, crc); 128 return crc; 129 } 130 131 static unsigned long crc32(const char *s) 132 { 133 return partial_crc32(s, 0xffffffff) ^ 0xffffffff; 134 } 135 136 /*----------------------------------------------------------------------*/ 137 138 static enum symbol_type map_to_ns(enum symbol_type t) 139 { 140 if (t == SYM_TYPEDEF) 141 t = SYM_NORMAL; 142 else if (t == SYM_UNION) 143 t = SYM_STRUCT; 144 return t; 145 } 146 147 struct symbol *find_symbol(const char *name, enum symbol_type ns) 148 { 149 unsigned long h = crc32(name) % HASH_BUCKETS; 150 struct symbol *sym; 151 152 for (sym = symtab[h]; sym; sym = sym->hash_next) 153 if (map_to_ns(sym->type) == map_to_ns(ns) && 154 strcmp(name, sym->name) == 0) 155 break; 156 157 return sym; 158 } 159 160 struct symbol *add_symbol(const char *name, enum symbol_type type, 161 struct string_list *defn, int is_extern) 162 { 163 unsigned long h = crc32(name) % HASH_BUCKETS; 164 struct symbol *sym; 165 166 for (sym = symtab[h]; sym; sym = sym->hash_next) { 167 if (map_to_ns(sym->type) == map_to_ns(type) 168 && strcmp(name, sym->name) == 0) { 169 if (!equal_list(sym->defn, defn)) 170 error_with_pos("redefinition of %s", name); 171 return sym; 172 } 173 } 174 175 sym = xmalloc(sizeof(*sym)); 176 sym->name = name; 177 sym->type = type; 178 sym->defn = defn; 179 sym->expansion_trail = NULL; 180 sym->visited = NULL; 181 sym->is_extern = is_extern; 182 183 sym->hash_next = symtab[h]; 184 symtab[h] = sym; 185 186 if (flag_debug) { 187 fprintf(debugfile, "Defn for %s %s == <", 188 symbol_type_name[type], name); 189 if (is_extern) 190 fputs("extern ", debugfile); 191 print_list(debugfile, defn); 192 fputs(">\n", debugfile); 193 } 194 195 ++nsyms; 196 return sym; 197 } 198 199 /*----------------------------------------------------------------------*/ 200 201 void free_node(struct string_list *node) 202 { 203 free(node->string); 204 free(node); 205 } 206 207 void free_list(struct string_list *s, struct string_list *e) 208 { 209 while (s != e) { 210 struct string_list *next = s->next; 211 free_node(s); 212 s = next; 213 } 214 } 215 216 struct string_list *copy_node(struct string_list *node) 217 { 218 struct string_list *newnode; 219 220 newnode = xmalloc(sizeof(*newnode)); 221 newnode->string = xstrdup(node->string); 222 newnode->tag = node->tag; 223 224 return newnode; 225 } 226 227 static int equal_list(struct string_list *a, struct string_list *b) 228 { 229 while (a && b) { 230 if (a->tag != b->tag || strcmp(a->string, b->string)) 231 return 0; 232 a = a->next; 233 b = b->next; 234 } 235 236 return !a && !b; 237 } 238 239 static void print_node(FILE * f, struct string_list *list) 240 { 241 if (list->tag != SYM_NORMAL) { 242 putc(symbol_type_name[list->tag][0], f); 243 putc('#', f); 244 } 245 fputs(list->string, f); 246 } 247 248 static void print_list(FILE * f, struct string_list *list) 249 { 250 struct string_list **e, **b; 251 struct string_list *tmp, **tmp2; 252 int elem = 1; 253 254 if (list == NULL) { 255 fputs("(nil)", f); 256 return; 257 } 258 259 tmp = list; 260 while ((tmp = tmp->next) != NULL) 261 elem++; 262 263 b = alloca(elem * sizeof(*e)); 264 e = b + elem; 265 tmp2 = e - 1; 266 267 (*tmp2--) = list; 268 while ((list = list->next) != NULL) 269 *(tmp2--) = list; 270 271 while (b != e) { 272 print_node(f, *b++); 273 putc(' ', f); 274 } 275 } 276 277 static unsigned long expand_and_crc_sym(struct symbol *sym, unsigned long crc) 278 { 279 struct string_list *list = sym->defn; 280 struct string_list **e, **b; 281 struct string_list *tmp, **tmp2; 282 int elem = 1; 283 284 if (!list) 285 return crc; 286 287 tmp = list; 288 while ((tmp = tmp->next) != NULL) 289 elem++; 290 291 b = alloca(elem * sizeof(*e)); 292 e = b + elem; 293 tmp2 = e - 1; 294 295 *(tmp2--) = list; 296 while ((list = list->next) != NULL) 297 *(tmp2--) = list; 298 299 while (b != e) { 300 struct string_list *cur; 301 struct symbol *subsym; 302 303 cur = *(b++); 304 switch (cur->tag) { 305 case SYM_NORMAL: 306 if (flag_dump_defs) 307 fprintf(debugfile, "%s ", cur->string); 308 crc = partial_crc32(cur->string, crc); 309 crc = partial_crc32_one(' ', crc); 310 break; 311 312 case SYM_TYPEDEF: 313 subsym = find_symbol(cur->string, cur->tag); 314 if (subsym->expansion_trail) { 315 if (flag_dump_defs) 316 fprintf(debugfile, "%s ", cur->string); 317 crc = partial_crc32(cur->string, crc); 318 crc = partial_crc32_one(' ', crc); 319 } else { 320 subsym->expansion_trail = expansion_trail; 321 expansion_trail = subsym; 322 crc = expand_and_crc_sym(subsym, crc); 323 } 324 break; 325 326 case SYM_STRUCT: 327 case SYM_UNION: 328 case SYM_ENUM: 329 subsym = find_symbol(cur->string, cur->tag); 330 if (!subsym) { 331 struct string_list *n, *t = NULL; 332 333 error_with_pos("expand undefined %s %s", 334 symbol_type_name[cur->tag], 335 cur->string); 336 337 n = xmalloc(sizeof(*n)); 338 n->string = xstrdup(symbol_type_name[cur->tag]); 339 n->tag = SYM_NORMAL; 340 n->next = t; 341 t = n; 342 343 n = xmalloc(sizeof(*n)); 344 n->string = xstrdup(cur->string); 345 n->tag = SYM_NORMAL; 346 n->next = t; 347 t = n; 348 349 n = xmalloc(sizeof(*n)); 350 n->string = xstrdup("{ UNKNOWN }"); 351 n->tag = SYM_NORMAL; 352 n->next = t; 353 354 subsym = 355 add_symbol(cur->string, cur->tag, n, 0); 356 } 357 if (subsym->expansion_trail) { 358 if (flag_dump_defs) { 359 fprintf(debugfile, "%s %s ", 360 symbol_type_name[cur->tag], 361 cur->string); 362 } 363 364 crc = partial_crc32(symbol_type_name[cur->tag], 365 crc); 366 crc = partial_crc32_one(' ', crc); 367 crc = partial_crc32(cur->string, crc); 368 crc = partial_crc32_one(' ', crc); 369 } else { 370 subsym->expansion_trail = expansion_trail; 371 expansion_trail = subsym; 372 crc = expand_and_crc_sym(subsym, crc); 373 } 374 break; 375 } 376 } 377 378 { 379 static struct symbol **end = &visited_symbols; 380 381 if (!sym->visited) { 382 *end = sym; 383 end = &sym->visited; 384 sym->visited = (struct symbol *)-1L; 385 } 386 } 387 388 return crc; 389 } 390 391 void export_symbol(const char *name) 392 { 393 struct symbol *sym; 394 395 sym = find_symbol(name, SYM_NORMAL); 396 if (!sym) 397 error_with_pos("export undefined symbol %s", name); 398 else { 399 unsigned long crc; 400 401 if (flag_dump_defs) 402 fprintf(debugfile, "Export %s == <", name); 403 404 expansion_trail = (struct symbol *)-1L; 405 406 crc = expand_and_crc_sym(sym, 0xffffffff) ^ 0xffffffff; 407 408 sym = expansion_trail; 409 while (sym != (struct symbol *)-1L) { 410 struct symbol *n = sym->expansion_trail; 411 sym->expansion_trail = 0; 412 sym = n; 413 } 414 415 if (flag_dump_defs) 416 fputs(">\n", debugfile); 417 418 /* Used as a linker script. */ 419 printf("%s__crc_%s = 0x%08lx ;\n", mod_prefix, name, crc); 420 } 421 } 422 423 /*----------------------------------------------------------------------*/ 424 void error_with_pos(const char *fmt, ...) 425 { 426 va_list args; 427 428 if (flag_warnings) { 429 fprintf(stderr, "%s:%d: ", cur_filename ? : "<stdin>", 430 cur_line); 431 432 va_start(args, fmt); 433 vfprintf(stderr, fmt, args); 434 va_end(args); 435 putc('\n', stderr); 436 437 errors++; 438 } 439 } 440 441 static void genksyms_usage(void) 442 { 443 fputs("Usage:\n" "genksyms [-adDTwqhV] > /path/to/.tmp_obj.ver\n" "\n" 444 #ifdef __GNU_LIBRARY__ 445 " -a, --arch Select architecture\n" 446 " -d, --debug Increment the debug level (repeatable)\n" 447 " -D, --dump Dump expanded symbol defs (for debugging only)\n" 448 " -T, --dump-types file Dump expanded types into file (for debugging only)\n" 449 " -w, --warnings Enable warnings\n" 450 " -q, --quiet Disable warnings (default)\n" 451 " -h, --help Print this message\n" 452 " -V, --version Print the release version\n" 453 #else /* __GNU_LIBRARY__ */ 454 " -a Select architecture\n" 455 " -d Increment the debug level (repeatable)\n" 456 " -D Dump expanded symbol defs (for debugging only)\n" 457 " -T file Dump expanded types into file (for debugging only)\n" 458 " -w Enable warnings\n" 459 " -q Disable warnings (default)\n" 460 " -h Print this message\n" 461 " -V Print the release version\n" 462 #endif /* __GNU_LIBRARY__ */ 463 , stderr); 464 } 465 466 int main(int argc, char **argv) 467 { 468 FILE *dumpfile = NULL; 469 int o; 470 471 #ifdef __GNU_LIBRARY__ 472 struct option long_opts[] = { 473 {"arch", 1, 0, 'a'}, 474 {"debug", 0, 0, 'd'}, 475 {"warnings", 0, 0, 'w'}, 476 {"quiet", 0, 0, 'q'}, 477 {"dump", 0, 0, 'D'}, 478 {"dump-types", 1, 0, 'T'}, 479 {"version", 0, 0, 'V'}, 480 {"help", 0, 0, 'h'}, 481 {0, 0, 0, 0} 482 }; 483 484 while ((o = getopt_long(argc, argv, "a:dwqVDT:h", 485 &long_opts[0], NULL)) != EOF) 486 #else /* __GNU_LIBRARY__ */ 487 while ((o = getopt(argc, argv, "a:dwqVDT:h")) != EOF) 488 #endif /* __GNU_LIBRARY__ */ 489 switch (o) { 490 case 'a': 491 arch = optarg; 492 break; 493 case 'd': 494 flag_debug++; 495 break; 496 case 'w': 497 flag_warnings = 1; 498 break; 499 case 'q': 500 flag_warnings = 0; 501 break; 502 case 'V': 503 fputs("genksyms version 2.5.60\n", stderr); 504 break; 505 case 'D': 506 flag_dump_defs = 1; 507 break; 508 case 'T': 509 flag_dump_types = 1; 510 dumpfile = fopen(optarg, "w"); 511 if (!dumpfile) { 512 perror(optarg); 513 return 1; 514 } 515 break; 516 case 'h': 517 genksyms_usage(); 518 return 0; 519 default: 520 genksyms_usage(); 521 return 1; 522 } 523 if ((strcmp(arch, "h8300") == 0) || (strcmp(arch, "blackfin") == 0)) 524 mod_prefix = "_"; 525 { 526 extern int yydebug; 527 extern int yy_flex_debug; 528 529 yydebug = (flag_debug > 1); 530 yy_flex_debug = (flag_debug > 2); 531 532 debugfile = stderr; 533 /* setlinebuf(debugfile); */ 534 } 535 536 yyparse(); 537 538 if (flag_dump_types && visited_symbols) { 539 while (visited_symbols != (struct symbol *)-1L) { 540 struct symbol *sym = visited_symbols; 541 542 if (sym->type != SYM_NORMAL) { 543 putc(symbol_type_name[sym->type][0], dumpfile); 544 putc('#', dumpfile); 545 } 546 fputs(sym->name, dumpfile); 547 putc(' ', dumpfile); 548 if (sym->is_extern) 549 fputs("extern ", dumpfile); 550 print_list(dumpfile, sym->defn); 551 putc('\n', dumpfile); 552 553 visited_symbols = sym->visited; 554 sym->visited = NULL; 555 } 556 } 557 558 if (flag_debug) { 559 fprintf(debugfile, "Hash table occupancy %d/%d = %g\n", 560 nsyms, HASH_BUCKETS, 561 (double)nsyms / (double)HASH_BUCKETS); 562 } 563 564 return errors != 0; 565 } 566