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 #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, "v850") == 0) || (strcmp(arch, "h8300") == 0)
 524             || (strcmp(arch, "blackfin") == 0))
 525                 mod_prefix = "_";
 526         {
 527                 extern int yydebug;
 528                 extern int yy_flex_debug;
 529
 530                 yydebug = (flag_debug > 1);
 531                 yy_flex_debug = (flag_debug > 2);
 532
 533                 debugfile = stderr;
 534                 /* setlinebuf(debugfile); */
 535         }
 536
 537         yyparse();
 538
 539         if (flag_dump_types && visited_symbols) {
 540                 while (visited_symbols != (struct symbol *)-1L) {
 541                         struct symbol *sym = visited_symbols;
 542
 543                         if (sym->type != SYM_NORMAL) {
 544                                 putc(symbol_type_name[sym->type][0], dumpfile);
 545                                 putc('#', dumpfile);
 546                         }
 547                         fputs(sym->name, dumpfile);
 548                         putc(' ', dumpfile);
 549                         print_list(dumpfile, sym->defn);
 550                         putc('\n', dumpfile);
 551
 552                         visited_symbols = sym->visited;
 553                         sym->visited = NULL;
 554                 }
 555         }
 556
 557         if (flag_debug) {
 558                 fprintf(debugfile, "Hash table occupancy %d/%d = %g\n",
 559                         nsyms, HASH_BUCKETS,
 560                         (double)nsyms / (double)HASH_BUCKETS);
 561         }
 562
 563         return errors != 0;
 564 }