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