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