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 [-dDwqhV] > /path/to/.tmp_obj.ver\n" "\n" 444 #ifdef __GNU_LIBRARY__ 445 " -d, --debug Increment the debug level (repeatable)\n" 446 " -D, --dump Dump expanded symbol defs (for debugging only)\n" 447 " -w, --warnings Enable warnings\n" 448 " -q, --quiet Disable warnings (default)\n" 449 " -h, --help Print this message\n" 450 " -V, --version Print the release version\n" 451 #else /* __GNU_LIBRARY__ */ 452 " -d Increment the debug level (repeatable)\n" 453 " -D Dump expanded symbol defs (for debugging only)\n" 454 " -w Enable warnings\n" 455 " -q Disable warnings (default)\n" 456 " -h Print this message\n" 457 " -V Print the release version\n" 458 #endif /* __GNU_LIBRARY__ */ 459 , stderr); 460 } 461 462 int main(int argc, char **argv) 463 { 464 FILE *dumpfile = NULL; 465 int o; 466 467 #ifdef __GNU_LIBRARY__ 468 struct option long_opts[] = { 469 {"arch", 1, 0, 'a'}, 470 {"debug", 0, 0, 'd'}, 471 {"warnings", 0, 0, 'w'}, 472 {"quiet", 0, 0, 'q'}, 473 {"dump", 0, 0, 'D'}, 474 {"dump-types", 1, 0, 'T'}, 475 {"version", 0, 0, 'V'}, 476 {"help", 0, 0, 'h'}, 477 {0, 0, 0, 0} 478 }; 479 480 while ((o = getopt_long(argc, argv, "a:dwqVDT:k:p:", 481 &long_opts[0], NULL)) != EOF) 482 #else /* __GNU_LIBRARY__ */ 483 while ((o = getopt(argc, argv, "a:dwqVDT:k:p:")) != EOF) 484 #endif /* __GNU_LIBRARY__ */ 485 switch (o) { 486 case 'a': 487 arch = optarg; 488 break; 489 case 'd': 490 flag_debug++; 491 break; 492 case 'w': 493 flag_warnings = 1; 494 break; 495 case 'q': 496 flag_warnings = 0; 497 break; 498 case 'V': 499 fputs("genksyms version 2.5.60\n", stderr); 500 break; 501 case 'D': 502 flag_dump_defs = 1; 503 break; 504 case 'T': 505 flag_dump_types = 1; 506 dumpfile = fopen(optarg, "w"); 507 if (!dumpfile) { 508 perror(optarg); 509 return 1; 510 } 511 break; 512 case 'h': 513 genksyms_usage(); 514 return 0; 515 default: 516 genksyms_usage(); 517 return 1; 518 } 519 if ((strcmp(arch, "v850") == 0) || (strcmp(arch, "h8300") == 0)) 520 mod_prefix = "_"; 521 { 522 extern int yydebug; 523 extern int yy_flex_debug; 524 525 yydebug = (flag_debug > 1); 526 yy_flex_debug = (flag_debug > 2); 527 528 debugfile = stderr; 529 /* setlinebuf(debugfile); */ 530 } 531 532 yyparse(); 533 534 if (flag_dump_types && visited_symbols) { 535 while (visited_symbols != (struct symbol *)-1L) { 536 struct symbol *sym = visited_symbols; 537 538 if (sym->type != SYM_NORMAL) { 539 putc(symbol_type_name[sym->type][0], dumpfile); 540 putc('#', dumpfile); 541 } 542 fputs(sym->name, dumpfile); 543 putc(' ', dumpfile); 544 print_list(dumpfile, sym->defn); 545 putc('\n', dumpfile); 546 547 visited_symbols = sym->visited; 548 sym->visited = NULL; 549 } 550 } 551 552 if (flag_debug) { 553 fprintf(debugfile, "Hash table occupancy %d/%d = %g\n", 554 nsyms, HASH_BUCKETS, 555 (double)nsyms / (double)HASH_BUCKETS); 556 } 557 558 return errors != 0; 559 } 560