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