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