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