scripts/genksyms/genksyms.c

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