File: /usr/src/linux/scripts/mkdep.c
1 /*
2 * Originally by Linus Torvalds.
3 * Smart CONFIG_* processing by Werner Almesberger, Michael Chastain.
4 *
5 * Usage: mkdep cflags -- file ...
6 *
7 * Read source files and output makefile dependency lines for them.
8 * I make simple dependency lines for #include <*.h> and #include "*.h".
9 * I also find instances of CONFIG_FOO and generate dependencies
10 * like include/config/foo.h.
11 *
12 * 1 August 1999, Michael Elizabeth Chastain, <mec@shout.net>
13 * - Keith Owens reported a bug in smart config processing. There used
14 * to be an optimization for "#define CONFIG_FOO ... #ifdef CONFIG_FOO",
15 * so that the file would not depend on CONFIG_FOO because the file defines
16 * this symbol itself. But this optimization is bogus! Consider this code:
17 * "#if 0 \n #define CONFIG_FOO \n #endif ... #ifdef CONFIG_FOO". Here
18 * the definition is inactivated, but I still used it. It turns out this
19 * actually happens a few times in the kernel source. The simple way to
20 * fix this problem is to remove this particular optimization.
21 *
22 * 2.3.99-pre1, Andrew Morton <andrewm@uow.edu.au>
23 * - Changed so that 'filename.o' depends upon 'filename.[cS]'. This is so that
24 * missing source files are noticed, rather than silently ignored.
25 *
26 * 2.4.2-pre3, Keith Owens <kaos@ocs.com.au>
27 * - Accept cflags followed by '--' followed by filenames. mkdep extracts -I
28 * options from cflags and looks in the specified directories as well as the
29 * defaults. Only -I is supported, no attempt is made to handle -idirafter,
30 * -isystem, -I- etc.
31 */
32
33 #include <ctype.h>
34 #include <fcntl.h>
35 #include <limits.h>
36 #include <stdio.h>
37 #include <stdlib.h>
38 #include <string.h>
39 #include <unistd.h>
40
41 #include <sys/fcntl.h>
42 #include <sys/mman.h>
43 #include <sys/stat.h>
44 #include <sys/types.h>
45
46
47
48 char __depname[512] = "\n\t@touch ";
49 #define depname (__depname+9)
50 int hasdep;
51
52 struct path_struct {
53 int len;
54 char *buffer;
55 };
56 struct path_struct *path_array;
57 int paths;
58
59
60 /* Current input file */
61 static const char *g_filename;
62
63 /*
64 * This records all the configuration options seen.
65 * In perl this would be a hash, but here it's a long string
66 * of values separated by newlines. This is simple and
67 * extremely fast.
68 */
69 char * str_config = NULL;
70 int size_config = 0;
71 int len_config = 0;
72
73 static void
74 do_depname(void)
75 {
76 if (!hasdep) {
77 hasdep = 1;
78 printf("%s:", depname);
79 if (g_filename)
80 printf(" %s", g_filename);
81 }
82 }
83
84 /*
85 * Grow the configuration string to a desired length.
86 * Usually the first growth is plenty.
87 */
88 void grow_config(int len)
89 {
90 while (len_config + len > size_config) {
91 if (size_config == 0)
92 size_config = 2048;
93 str_config = realloc(str_config, size_config *= 2);
94 if (str_config == NULL)
95 { perror("malloc config"); exit(1); }
96 }
97 }
98
99
100
101 /*
102 * Lookup a value in the configuration string.
103 */
104 int is_defined_config(const char * name, int len)
105 {
106 const char * pconfig;
107 const char * plast = str_config + len_config - len;
108 for ( pconfig = str_config + 1; pconfig < plast; pconfig++ ) {
109 if (pconfig[ -1] == '\n'
110 && pconfig[len] == '\n'
111 && !memcmp(pconfig, name, len))
112 return 1;
113 }
114 return 0;
115 }
116
117
118
119 /*
120 * Add a new value to the configuration string.
121 */
122 void define_config(const char * name, int len)
123 {
124 grow_config(len + 1);
125
126 memcpy(str_config+len_config, name, len);
127 len_config += len;
128 str_config[len_config++] = '\n';
129 }
130
131
132
133 /*
134 * Clear the set of configuration strings.
135 */
136 void clear_config(void)
137 {
138 len_config = 0;
139 define_config("", 0);
140 }
141
142
143
144 /*
145 * This records all the precious .h filenames. No need for a hash,
146 * it's a long string of values enclosed in tab and newline.
147 */
148 char * str_precious = NULL;
149 int size_precious = 0;
150 int len_precious = 0;
151
152
153
154 /*
155 * Grow the precious string to a desired length.
156 * Usually the first growth is plenty.
157 */
158 void grow_precious(int len)
159 {
160 while (len_precious + len > size_precious) {
161 if (size_precious == 0)
162 size_precious = 2048;
163 str_precious = realloc(str_precious, size_precious *= 2);
164 if (str_precious == NULL)
165 { perror("malloc"); exit(1); }
166 }
167 }
168
169
170
171 /*
172 * Add a new value to the precious string.
173 */
174 void define_precious(const char * filename)
175 {
176 int len = strlen(filename);
177 grow_precious(len + 4);
178 *(str_precious+len_precious++) = '\t';
179 memcpy(str_precious+len_precious, filename, len);
180 len_precious += len;
181 memcpy(str_precious+len_precious, " \\\n", 3);
182 len_precious += 3;
183 }
184
185
186
187 /*
188 * Handle an #include line.
189 */
190 void handle_include(int start, const char * name, int len)
191 {
192 struct path_struct *path;
193 int i;
194
195 if (len == 14 && !memcmp(name, "linux/config.h", len))
196 return;
197
198 if (len >= 7 && !memcmp(name, "config/", 7))
199 define_config(name+7, len-7-2);
200
201 for (i = start, path = path_array+start; i < paths; ++i, ++path) {
202 memcpy(path->buffer+path->len, name, len);
203 path->buffer[path->len+len] = '\0';
204 if (access(path->buffer, F_OK) == 0) {
205 do_depname();
206 printf(" \\\n %s", path->buffer);
207 return;
208 }
209 }
210
211 }
212
213
214
215 /*
216 * Add a path to the list of include paths.
217 */
218 void add_path(const char * name)
219 {
220 struct path_struct *path;
221 char resolved_path[PATH_MAX+1];
222 const char *name2;
223
224 if (strcmp(name, ".")) {
225 name2 = realpath(name, resolved_path);
226 if (!name2) {
227 fprintf(stderr, "realpath(%s) failed, %m\n", name);
228 exit(1);
229 }
230 }
231 else {
232 name2 = "";
233 }
234
235 path_array = realloc(path_array, (++paths)*sizeof(*path_array));
236 if (!path_array) {
237 fprintf(stderr, "cannot expand path_arry\n");
238 exit(1);
239 }
240
241 path = path_array+paths-1;
242 path->len = strlen(name2);
243 path->buffer = malloc(path->len+1+256+1);
244 if (!path->buffer) {
245 fprintf(stderr, "cannot allocate path buffer\n");
246 exit(1);
247 }
248 strcpy(path->buffer, name2);
249 if (path->len && *(path->buffer+path->len-1) != '/') {
250 *(path->buffer+path->len) = '/';
251 *(path->buffer+(++(path->len))) = '\0';
252 }
253 }
254
255
256
257 /*
258 * Record the use of a CONFIG_* word.
259 */
260 void use_config(const char * name, int len)
261 {
262 char *pc;
263 int i;
264
265 pc = path_array[paths-1].buffer + path_array[paths-1].len;
266 memcpy(pc, "config/", 7);
267 pc += 7;
268
269 for (i = 0; i < len; i++) {
270 char c = name[i];
271 if (isupper(c)) c = tolower(c);
272 if (c == '_') c = '/';
273 pc[i] = c;
274 }
275 pc[len] = '\0';
276
277 if (is_defined_config(pc, len))
278 return;
279
280 define_config(pc, len);
281
282 do_depname();
283 printf(" \\\n $(wildcard %s.h)", path_array[paths-1].buffer);
284 }
285
286
287
288 /*
289 * Macros for stunningly fast map-based character access.
290 * __buf is a register which holds the current word of the input.
291 * Thus, there is one memory access per sizeof(unsigned long) characters.
292 */
293
294 #if defined(__alpha__) || defined(__i386__) || defined(__ia64__) || defined(__x86_64__) || defined(__MIPSEL__) \
295 || defined(__arm__)
296 #define LE_MACHINE
297 #endif
298
299 #ifdef LE_MACHINE
300 #define next_byte(x) (x >>= 8)
301 #define current ((unsigned char) __buf)
302 #else
303 #define next_byte(x) (x <<= 8)
304 #define current (__buf >> 8*(sizeof(unsigned long)-1))
305 #endif
306
307 #define GETNEXT { \
308 next_byte(__buf); \
309 if ((unsigned long) next % sizeof(unsigned long) == 0) { \
310 if (next >= end) \
311 break; \
312 __buf = * (unsigned long *) next; \
313 } \
314 next++; \
315 }
316
317 /*
318 * State machine macros.
319 */
320 #define CASE(c,label) if (current == c) goto label
321 #define NOTCASE(c,label) if (current != c) goto label
322
323 /*
324 * Yet another state machine speedup.
325 */
326 #define MAX2(a,b) ((a)>(b)?(a):(b))
327 #define MIN2(a,b) ((a)<(b)?(a):(b))
328 #define MAX5(a,b,c,d,e) (MAX2(a,MAX2(b,MAX2(c,MAX2(d,e)))))
329 #define MIN5(a,b,c,d,e) (MIN2(a,MIN2(b,MIN2(c,MIN2(d,e)))))
330
331
332
333 /*
334 * The state machine looks for (approximately) these Perl regular expressions:
335 *
336 * m|\/\*.*?\*\/|
337 * m|\/\/.*|
338 * m|'.*?'|
339 * m|".*?"|
340 * m|#\s*include\s*"(.*?)"|
341 * m|#\s*include\s*<(.*?>"|
342 * m|#\s*(?define|undef)\s*CONFIG_(\w*)|
343 * m|(?!\w)CONFIG_|
344 *
345 * About 98% of the CPU time is spent here, and most of that is in
346 * the 'start' paragraph. Because the current characters are
347 * in a register, the start loop usually eats 4 or 8 characters
348 * per memory read. The MAX5 and MIN5 tests dispose of most
349 * input characters with 1 or 2 comparisons.
350 */
351 void state_machine(const char * map, const char * end)
352 {
353 const char * next = map;
354 const char * map_dot;
355 unsigned long __buf = 0;
356
357 for (;;) {
358 start:
359 GETNEXT
360 __start:
361 if (current > MAX5('/','\'','"','#','C')) goto start;
362 if (current < MIN5('/','\'','"','#','C')) goto start;
363 CASE('/', slash);
364 CASE('\'', squote);
365 CASE('"', dquote);
366 CASE('#', pound);
367 CASE('C', cee);
368 goto start;
369
370 /* // */
371 slash_slash:
372 GETNEXT
373 CASE('\n', start);
374 NOTCASE('\\', slash_slash);
375 GETNEXT
376 goto slash_slash;
377
378 /* / */
379 slash:
380 GETNEXT
381 CASE('/', slash_slash);
382 NOTCASE('*', __start);
383 slash_star_dot_star:
384 GETNEXT
385 __slash_star_dot_star:
386 NOTCASE('*', slash_star_dot_star);
387 GETNEXT
388 NOTCASE('/', __slash_star_dot_star);
389 goto start;
390
391 /* '.*?' */
392 squote:
393 GETNEXT
394 CASE('\'', start);
395 NOTCASE('\\', squote);
396 GETNEXT
397 goto squote;
398
399 /* ".*?" */
400 dquote:
401 GETNEXT
402 CASE('"', start);
403 NOTCASE('\\', dquote);
404 GETNEXT
405 goto dquote;
406
407 /* #\s* */
408 pound:
409 GETNEXT
410 CASE(' ', pound);
411 CASE('\t', pound);
412 CASE('i', pound_i);
413 CASE('d', pound_d);
414 CASE('u', pound_u);
415 goto __start;
416
417 /* #\s*i */
418 pound_i:
419 GETNEXT NOTCASE('n', __start);
420 GETNEXT NOTCASE('c', __start);
421 GETNEXT NOTCASE('l', __start);
422 GETNEXT NOTCASE('u', __start);
423 GETNEXT NOTCASE('d', __start);
424 GETNEXT NOTCASE('e', __start);
425 goto pound_include;
426
427 /* #\s*include\s* */
428 pound_include:
429 GETNEXT
430 CASE(' ', pound_include);
431 CASE('\t', pound_include);
432 map_dot = next;
433 CASE('"', pound_include_dquote);
434 CASE('<', pound_include_langle);
435 goto __start;
436
437 /* #\s*include\s*"(.*)" */
438 pound_include_dquote:
439 GETNEXT
440 CASE('\n', start);
441 NOTCASE('"', pound_include_dquote);
442 handle_include(0, map_dot, next - map_dot - 1);
443 goto start;
444
445 /* #\s*include\s*<(.*)> */
446 pound_include_langle:
447 GETNEXT
448 CASE('\n', start);
449 NOTCASE('>', pound_include_langle);
450 handle_include(1, map_dot, next - map_dot - 1);
451 goto start;
452
453 /* #\s*d */
454 pound_d:
455 GETNEXT NOTCASE('e', __start);
456 GETNEXT NOTCASE('f', __start);
457 GETNEXT NOTCASE('i', __start);
458 GETNEXT NOTCASE('n', __start);
459 GETNEXT NOTCASE('e', __start);
460 goto pound_define_undef;
461
462 /* #\s*u */
463 pound_u:
464 GETNEXT NOTCASE('n', __start);
465 GETNEXT NOTCASE('d', __start);
466 GETNEXT NOTCASE('e', __start);
467 GETNEXT NOTCASE('f', __start);
468 goto pound_define_undef;
469
470 /*
471 * #\s*(define|undef)\s*CONFIG_(\w*)
472 *
473 * this does not define the word, because it could be inside another
474 * conditional (#if 0). But I do parse the word so that this instance
475 * does not count as a use. -- mec
476 */
477 pound_define_undef:
478 GETNEXT
479 CASE(' ', pound_define_undef);
480 CASE('\t', pound_define_undef);
481
482 NOTCASE('C', __start);
483 GETNEXT NOTCASE('O', __start);
484 GETNEXT NOTCASE('N', __start);
485 GETNEXT NOTCASE('F', __start);
486 GETNEXT NOTCASE('I', __start);
487 GETNEXT NOTCASE('G', __start);
488 GETNEXT NOTCASE('_', __start);
489
490 map_dot = next;
491 pound_define_undef_CONFIG_word:
492 GETNEXT
493 if (isalnum(current) || current == '_')
494 goto pound_define_undef_CONFIG_word;
495 goto __start;
496
497 /* \<CONFIG_(\w*) */
498 cee:
499 if (next >= map+2 && (isalnum(next[-2]) || next[-2] == '_'))
500 goto start;
501 GETNEXT NOTCASE('O', __start);
502 GETNEXT NOTCASE('N', __start);
503 GETNEXT NOTCASE('F', __start);
504 GETNEXT NOTCASE('I', __start);
505 GETNEXT NOTCASE('G', __start);
506 GETNEXT NOTCASE('_', __start);
507
508 map_dot = next;
509 cee_CONFIG_word:
510 GETNEXT
511 if (isalnum(current) || current == '_')
512 goto cee_CONFIG_word;
513 use_config(map_dot, next - map_dot - 1);
514 goto __start;
515 }
516 }
517
518
519
520 /*
521 * Generate dependencies for one file.
522 */
523 void do_depend(const char * filename, const char * command)
524 {
525 int mapsize;
526 int pagesizem1 = getpagesize()-1;
527 int fd;
528 struct stat st;
529 char * map;
530
531 fd = open(filename, O_RDONLY);
532 if (fd < 0) {
533 perror(filename);
534 return;
535 }
536
537 fstat(fd, &st);
538 if (st.st_size == 0) {
539 fprintf(stderr,"%s is empty\n",filename);
540 close(fd);
541 return;
542 }
543
544 mapsize = st.st_size;
545 mapsize = (mapsize+pagesizem1) & ~pagesizem1;
546 map = mmap(NULL, mapsize, PROT_READ, MAP_PRIVATE, fd, 0);
547 if ((long) map == -1) {
548 perror("mkdep: mmap");
549 close(fd);
550 return;
551 }
552 if ((unsigned long) map % sizeof(unsigned long) != 0)
553 {
554 fprintf(stderr, "do_depend: map not aligned\n");
555 exit(1);
556 }
557
558 hasdep = 0;
559 clear_config();
560 state_machine(map, map+st.st_size);
561 if (hasdep) {
562 puts(command);
563 if (*command)
564 define_precious(filename);
565 }
566
567 munmap(map, mapsize);
568 close(fd);
569 }
570
571
572
573 /*
574 * Generate dependencies for all files.
575 */
576 int main(int argc, char **argv)
577 {
578 int len;
579 const char *hpath;
580
581 hpath = getenv("HPATH");
582 if (!hpath) {
583 fputs("mkdep: HPATH not set in environment. "
584 "Don't bypass the top level Makefile.\n", stderr);
585 return 1;
586 }
587
588 add_path("."); /* for #include "..." */
589
590 while (++argv, --argc > 0) {
591 if (strncmp(*argv, "-I", 2) == 0) {
592 if (*((*argv)+2)) {
593 add_path((*argv)+2);
594 }
595 else {
596 ++argv;
597 --argc;
598 add_path(*argv);
599 }
600 }
601 else if (strcmp(*argv, "--") == 0) {
602 break;
603 }
604 }
605
606 add_path(hpath); /* must be last entry, for config files */
607
608 while (--argc > 0) {
609 const char * filename = *++argv;
610 const char * command = __depname;
611 g_filename = 0;
612 len = strlen(filename);
613 memcpy(depname, filename, len+1);
614 if (len > 2 && filename[len-2] == '.') {
615 if (filename[len-1] == 'c' || filename[len-1] == 'S') {
616 depname[len-1] = 'o';
617 g_filename = filename;
618 command = "";
619 }
620 }
621 do_depend(filename, command);
622 }
623 if (len_precious) {
624 *(str_precious+len_precious) = '\0';
625 printf(".PRECIOUS:%s\n", str_precious);
626 }
627 return 0;
628 }
629