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