Linux-2.6.12-rc2
[linux-3.10.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
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 }