find/find.c

   1 /* find -- search for files in a directory hierarchy
   2    Copyright (C) 1990, 91, 92, 93, 94, 2000, 2003 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 9 Temple Place - Suite 330, Boston, MA 02111-1307,
  17    USA.*/
  18
  19 /* GNU find was written by Eric Decker <cire@cisco.com>,
  20    with enhancements by David MacKenzie <djm@gnu.ai.mit.edu>,
  21    Jay Plett <jay@silence.princeton.nj.us>,
  22    and Tim Wood <axolotl!tim@toad.com>.
  23    The idea for -print0 and xargs -0 came from
  24    Dan Bernstein <brnstnd@kramden.acf.nyu.edu>.  */
  25
  26 #include "defs.h"
  27
  28 #ifdef HAVE_FCNTL_H
  29 #include <fcntl.h>
  30 #else
  31 #include <sys/file.h>
  32 #endif
  33 #include <human.h>
  34 #include <modetype.h>
  35 #include <savedir.h>
  36
  37 #ifdef HAVE_LOCALE_H
  38 #include <locale.h>
  39 #endif
  40
  41 #if ENABLE_NLS
  42 # include <libintl.h>
  43 # define _(Text) gettext (Text)
  44 #else
  45 # define _(Text) Text
  46 #define textdomain(Domain)
  47 #define bindtextdomain(Package, Directory)
  48 #endif
  49 #ifdef gettext_noop
  50 # define N_(String) gettext_noop (String)
  51 #else
  52 # define N_(String) (String)
  53 #endif
  54
  55 #define apply_predicate(pathname, stat_buf_ptr, node)   \
  56   (*(node)->pred_func)((pathname), (stat_buf_ptr), (node))
  57
  58 static void process_top_path PARAMS((char *pathname));
  59 static int process_path PARAMS((char *pathname, char *name, boolean leaf, char *parent));
  60 static void process_dir PARAMS((char *pathname, char *name, int pathlen, struct stat *statp, char *parent));
  61 static boolean no_side_effects PARAMS((struct predicate *pred));
  62 static boolean default_prints PARAMS((struct predicate *pred));
  63
  64 /* Name this program was run with. */
  65 char *program_name;
  66
  67 /* All predicates for each path to process. */
  68 struct predicate *predicates;
  69
  70 /* The last predicate allocated. */
  71 struct predicate *last_pred;
  72
  73 /* The root of the evaluation tree. */
  74 static struct predicate *eval_tree;
  75
  76 /* If true, process directory before contents.  True unless -depth given. */
  77 boolean do_dir_first;
  78
  79 /* If >=0, don't descend more than this many levels of subdirectories. */
  80 int maxdepth;
  81
  82 /* If >=0, don't process files above this level. */
  83 int mindepth;
  84
  85 /* Current depth; 0 means current path is a command line arg. */
  86 int curdepth;
  87
  88 /* Output block size.  */
  89 int output_block_size;
  90
  91 /* Time at start of execution.  */
  92 time_t start_time;
  93
  94 /* Seconds between 00:00 1/1/70 and either one day before now
  95    (the default), or the start of today (if -daystart is given). */
  96 time_t cur_day_start;
  97
  98 /* If true, cur_day_start has been adjusted to the start of the day. */
  99 boolean full_days;
 100
 101 /* If true, do not assume that files in directories with nlink == 2
 102    are non-directories. */
 103 boolean no_leaf_check;
 104
 105 /* If true, don't cross filesystem boundaries. */
 106 boolean stay_on_filesystem;
 107
 108 /* If true, don't descend past current directory.
 109    Can be set by -prune, -maxdepth, and -xdev/-mount. */
 110 boolean stop_at_current_level;
 111
 112 /* The full path of the initial working directory, or "." if
 113    STARTING_DESC is nonnegative.  */
 114 char const *starting_dir = ".";
 115
 116 /* A file descriptor open to the initial working directory.
 117    Doing it this way allows us to work when the i.w.d. has
 118    unreadable parents.  */
 119 int starting_desc;
 120
 121 /* The stat buffer of the initial working directory. */
 122 struct stat starting_stat_buf;
 123
 124 /* If true, we have called stat on the current path. */
 125 boolean have_stat;
 126
 127 /* The file being operated on, relative to the current directory.
 128    Used for stat, readlink, remove, and opendir.  */
 129 char *rel_pathname;
 130
 131 /* Length of current path. */
 132 int path_length;
 133
 134 /* true if following symlinks.  Should be consistent with xstat.  */
 135 boolean dereference;
 136
 137 /* Pointer to the function used to stat files. */
 138 int (*xstat) ();
 139
 140 /* Status value to return to system. */
 141 int exit_status;
 142
 143 /* If true, we ignore the problem where we find that a directory entry
 144  * no longer exists by the time we get around to processing it.
 145  */
 146 boolean ignore_readdir_race;
 147
 148
 149 #ifdef DEBUG_STAT
 150 static int
 151 debug_stat (file, bufp)
 152      char *file;
 153      struct stat *bufp;
 154 {
 155   fprintf (stderr, "debug_stat (%s)\n", file);
 156   return lstat (file, bufp);
 157 }
 158 #endif /* DEBUG_STAT */
 159 \f
 160 int
 161 main (int argc, char **argv)
 162 {
 163   int i;
 164   PFB parse_function;           /* Pointer to the function which parses. */
 165   struct predicate *cur_pred;
 166   char *predicate_name;         /* Name of predicate being parsed. */
 167
 168   program_name = argv[0];
 169
 170 #ifdef HAVE_SETLOCALE
 171   setlocale (LC_ALL, "");
 172 #endif
 173   bindtextdomain (PACKAGE, LOCALEDIR);
 174   textdomain (PACKAGE);
 175
 176   predicates = NULL;
 177   last_pred = NULL;
 178   do_dir_first = true;
 179   maxdepth = mindepth = -1;
 180   start_time = time (NULL);
 181   cur_day_start = start_time - DAYSECS;
 182   full_days = false;
 183   no_leaf_check = false;
 184   stay_on_filesystem = false;
 185   ignore_readdir_race = false;
 186   exit_status = 0;
 187   dereference = false;
 188 #ifdef DEBUG_STAT
 189   xstat = debug_stat;
 190 #else /* !DEBUG_STAT */
 191   xstat = lstat;
 192 #endif /* !DEBUG_STAT */
 193
 194 #if 0
 195   human_block_size (getenv ("FIND_BLOCK_SIZE"), 0, &output_block_size);
 196 #else
 197   if (getenv("POSIXLY_CORRECT"))
 198     output_block_size = 512;
 199   else
 200     output_block_size = 1024;
 201
 202   if (getenv("FIND_BLOCK_SIZE"))
 203     {
 204       error (1, errno, _("The environment variable FIND_BLOCK_SIZE is not supported, the only thing that affects the block size is the POSIXLY_CORRECT environment variable"));
 205     }
 206
 207 #endif
 208
 209 #ifdef DEBUG
 210   printf ("cur_day_start = %s", ctime (&cur_day_start));
 211 #endif /* DEBUG */
 212
 213   /* Find where in ARGV the predicates begin. */
 214   for (i = 1; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
 215     /* Do nothing. */ ;
 216
 217   /* Enclose the expression in `( ... )' so a default -print will
 218      apply to the whole expression. */
 219   parse_open (argv, &argc);
 220   /* Build the input order list. */
 221   while (i < argc)
 222     {
 223       if (strchr ("-!(),", argv[i][0]) == NULL)
 224         usage (_("paths must precede expression"));
 225       predicate_name = argv[i];
 226       parse_function = find_parser (predicate_name);
 227       if (parse_function == NULL)
 228         /* Command line option not recognized */
 229         error (1, 0, _("invalid predicate `%s'"), predicate_name);
 230       i++;
 231       if (!(*parse_function) (argv, &i))
 232         {
 233           if (argv[i] == NULL)
 234             /* Command line option requires an argument */
 235             error (1, 0, _("missing argument to `%s'"), predicate_name);
 236           else
 237             error (1, 0, _("invalid argument `%s' to `%s'"),
 238                    argv[i], predicate_name);
 239         }
 240     }
 241   if (predicates->pred_next == NULL)
 242     {
 243       /* No predicates that do something other than set a global variable
 244          were given; remove the unneeded initial `(' and add `-print'. */
 245       cur_pred = predicates;
 246       predicates = last_pred = predicates->pred_next;
 247       free ((char *) cur_pred);
 248       parse_print (argv, &argc);
 249     }
 250   else if (!default_prints (predicates->pred_next))
 251     {
 252       /* One or more predicates that produce output were given;
 253          remove the unneeded initial `('. */
 254       cur_pred = predicates;
 255       predicates = predicates->pred_next;
 256       free ((char *) cur_pred);
 257     }
 258   else
 259     {
 260       /* `( user-supplied-expression ) -print'. */
 261       parse_close (argv, &argc);
 262       parse_print (argv, &argc);
 263     }
 264
 265 #ifdef  DEBUG
 266   printf (_("Predicate List:\n"));
 267   print_list (predicates);
 268 #endif /* DEBUG */
 269
 270   /* Done parsing the predicates.  Build the evaluation tree. */
 271   cur_pred = predicates;
 272   eval_tree = get_expr (&cur_pred, NO_PREC);
 273
 274   /* Check if we have any left-over predicates (this fixes
 275    * Debian bug #185202).
 276    */
 277   if (cur_pred != NULL)
 278     {
 279       error (1, 0, _("unexpected extra predicate"));
 280     }
 281
 282 #ifdef  DEBUG
 283   printf (_("Eval Tree:\n"));
 284   print_tree (eval_tree, 0);
 285 #endif /* DEBUG */
 286
 287   /* Rearrange the eval tree in optimal-predicate order. */
 288   opt_expr (&eval_tree);
 289
 290   /* Determine the point, if any, at which to stat the file. */
 291   mark_stat (eval_tree);
 292
 293 #ifdef DEBUG
 294   printf (_("Optimized Eval Tree:\n"));
 295   print_tree (eval_tree, 0);
 296 #endif /* DEBUG */
 297
 298   starting_desc = open (".", O_RDONLY);
 299   if (0 <= starting_desc && fchdir (starting_desc) != 0)
 300     {
 301       close (starting_desc);
 302       starting_desc = -1;
 303     }
 304   if (starting_desc < 0)
 305     {
 306       starting_dir = xgetcwd ();
 307       if (! starting_dir)
 308         error (1, errno, _("cannot get current directory"));
 309     }
 310   if ((*xstat) (".", &starting_stat_buf) != 0)
 311     error (1, errno, _("cannot get current directory"));
 312
 313   /* If no paths are given, default to ".".  */
 314   for (i = 1; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
 315     process_top_path (argv[i]);
 316   if (i == 1)
 317     process_top_path (".");
 318
 319   exit (exit_status);
 320 }
 321 \f
 322 /* Safely go back to the starting directory. */
 323 static void
 324 chdir_back (void)
 325 {
 326   struct stat stat_buf;
 327
 328   if (starting_desc < 0)
 329     {
 330       if (chdir (starting_dir) != 0)
 331         error (1, errno, "%s", starting_dir);
 332       if ((*xstat) (".", &stat_buf) != 0)
 333         error (1, errno, "%s", starting_dir);
 334       if (stat_buf.st_dev != starting_stat_buf.st_dev ||
 335           stat_buf.st_ino != starting_stat_buf.st_ino)
 336         error (1, 0, _("%s changed during execution of %s"), starting_dir, program_name);
 337     }
 338   else
 339     {
 340       if (fchdir (starting_desc) != 0)
 341         error (1, errno, "%s", starting_dir);
 342     }
 343 }
 344 \f
 345 /* Descend PATHNAME, which is a command-line argument.  */
 346
 347 static void
 348 process_top_path (char *pathname)
 349 {
 350   struct stat stat_buf, cur_stat_buf;
 351
 352   curdepth = 0;
 353   path_length = strlen (pathname);
 354
 355   /* We stat each pathname given on the command-line twice --
 356      once here and once in process_path.  It's not too bad, though,
 357      since the kernel can read the stat information out of its inode
 358      cache the second time.  */
 359   if ((*xstat) (pathname, &stat_buf) == 0 && S_ISDIR (stat_buf.st_mode))
 360     {
 361       if (chdir (pathname) < 0)
 362         {
 363           if (!ignore_readdir_race || (errno != ENOENT) )
 364             {
 365               error (0, errno, "%s", pathname);
 366               exit_status = 1;
 367             }
 368           return;
 369         }
 370
 371       /* Check that we are where we should be. */
 372       if ((*xstat) (".", &cur_stat_buf) != 0)
 373         error (1, errno, "%s", pathname);
 374       if (cur_stat_buf.st_dev != stat_buf.st_dev ||
 375           cur_stat_buf.st_ino != stat_buf.st_ino)
 376         error (1, 0, _("%s changed during execution of %s"), pathname, program_name);
 377
 378       process_path (pathname, ".", false, ".");
 379       chdir_back ();
 380     }
 381   else
 382     process_path (pathname, pathname, false, ".");
 383 }
 384
 385 /* Info on each directory in the current tree branch, to avoid
 386    getting stuck in symbolic link loops.  */
 387 struct dir_id
 388 {
 389   ino_t ino;
 390   dev_t dev;
 391 };
 392 static struct dir_id *dir_ids = NULL;
 393 /* Entries allocated in `dir_ids'.  */
 394 static int dir_alloc = 0;
 395 /* Index in `dir_ids' of directory currently being searched.
 396    This is always the last valid entry.  */
 397 static int dir_curr = -1;
 398 /* (Arbitrary) number of entries to grow `dir_ids' by.  */
 399 #define DIR_ALLOC_STEP 32
 400
 401 /* Recursively descend path PATHNAME, applying the predicates.
 402    LEAF is true if PATHNAME is known to be in a directory that has no
 403    more unexamined subdirectories, and therefore it is not a directory.
 404    Knowing this allows us to avoid calling stat as long as possible for
 405    leaf files.
 406
 407    NAME is PATHNAME relative to the current directory.  We access NAME
 408    but print PATHNAME.
 409
 410    PARENT is the path of the parent of NAME, relative to find's
 411    starting directory.
 412
 413    Return nonzero iff PATHNAME is a directory. */
 414
 415 static int
 416 process_path (char *pathname, char *name, boolean leaf, char *parent)
 417 {
 418   struct stat stat_buf;
 419   static dev_t root_dev;        /* Device ID of current argument pathname. */
 420   int i;
 421   struct stat dir_buf;
 422   int parent_desc;
 423
 424   /* Assume it is a non-directory initially. */
 425   stat_buf.st_mode = 0;
 426
 427   rel_pathname = name;
 428
 429   if (leaf)
 430     have_stat = false;
 431   else
 432     {
 433       if ((*xstat) (name, &stat_buf) != 0)
 434         {
 435           if (!ignore_readdir_race || (errno != ENOENT) )
 436             {
 437               error (0, errno, "%s", pathname);
 438               exit_status = 1;
 439             }
 440           return 0;
 441         }
 442       have_stat = true;
 443     }
 444
 445   if (!S_ISDIR (stat_buf.st_mode))
 446     {
 447       if (curdepth >= mindepth)
 448         apply_predicate (pathname, &stat_buf, eval_tree);
 449       return 0;
 450     }
 451
 452   /* From here on, we're working on a directory.  */
 453
 454   stop_at_current_level = maxdepth >= 0 && curdepth >= maxdepth;
 455
 456   /* If we've already seen this directory on this branch,
 457      don't descend it again.  */
 458   for (i = 0; i <= dir_curr; i++)
 459     if (stat_buf.st_ino == dir_ids[i].ino &&
 460         stat_buf.st_dev == dir_ids[i].dev)
 461       stop_at_current_level = true;
 462
 463   if (dir_alloc <= ++dir_curr)
 464     {
 465       dir_alloc += DIR_ALLOC_STEP;
 466       dir_ids = (struct dir_id *)
 467         xrealloc ((char *) dir_ids, dir_alloc * sizeof (struct dir_id));
 468     }
 469   dir_ids[dir_curr].ino = stat_buf.st_ino;
 470   dir_ids[dir_curr].dev = stat_buf.st_dev;
 471
 472   if (stay_on_filesystem)
 473     {
 474       if (curdepth == 0)
 475         root_dev = stat_buf.st_dev;
 476       else if (stat_buf.st_dev != root_dev)
 477         stop_at_current_level = true;
 478     }
 479
 480   if (do_dir_first && curdepth >= mindepth)
 481     apply_predicate (pathname, &stat_buf, eval_tree);
 482
 483 #ifdef DEBUG
 484   fprintf(stderr, "pathname = %s, stop_at_current_level = %d\n",
 485           pathname, stop_at_current_level);
 486 #endif /* DEBUG */
 487
 488   if (stop_at_current_level == false)
 489     /* Scan directory on disk. */
 490     process_dir (pathname, name, strlen (pathname), &stat_buf, parent);
 491
 492   if (do_dir_first == false && curdepth >= mindepth)
 493     {
 494       rel_pathname = name;
 495       apply_predicate (pathname, &stat_buf, eval_tree);
 496     }
 497
 498   dir_curr--;
 499
 500   return 1;
 501 }
 502 \f
 503 /* Scan directory PATHNAME and recurse through process_path for each entry.
 504
 505    PATHLEN is the length of PATHNAME.
 506
 507    NAME is PATHNAME relative to the current directory.
 508
 509    STATP is the results of *xstat on it.
 510
 511    PARENT is the path of the parent of NAME, relative to find's
 512    starting directory.  */
 513
 514 static void
 515 process_dir (char *pathname, char *name, int pathlen, struct stat *statp, char *parent)
 516 {
 517   char *name_space;             /* Names of files in PATHNAME. */
 518   int subdirs_left;             /* Number of unexamined subdirs in PATHNAME. */
 519   struct stat stat_buf;
 520
 521   subdirs_left = statp->st_nlink - 2; /* Account for name and ".". */
 522
 523   errno = 0;
 524   name_space = savedir (name);
 525   if (name_space == NULL)
 526     {
 527       if (errno)
 528         {
 529           error (0, errno, "%s", pathname);
 530           exit_status = 1;
 531         }
 532       else
 533         error (1, 0, _("virtual memory exhausted"));
 534     }
 535   else
 536     {
 537       register char *namep;     /* Current point in `name_space'. */
 538       char *cur_path;           /* Full path of each file to process. */
 539       char *cur_name;           /* Base name of each file to process. */
 540       unsigned cur_path_size;   /* Bytes allocated for `cur_path'. */
 541       register unsigned file_len; /* Length of each path to process. */
 542       register unsigned pathname_len; /* PATHLEN plus trailing '/'. */
 543
 544       if (pathname[pathlen - 1] == '/')
 545         pathname_len = pathlen + 1; /* For '\0'; already have '/'. */
 546       else
 547         pathname_len = pathlen + 2; /* For '/' and '\0'. */
 548       cur_path_size = 0;
 549       cur_path = NULL;
 550
 551       if (strcmp (name, ".") && chdir (name) < 0)
 552         {
 553           error (0, errno, "%s", pathname);
 554           exit_status = 1;
 555           return;
 556         }
 557
 558       /* Check that we are where we should be. */
 559       if ((*xstat) (".", &stat_buf) != 0)
 560         error (1, errno, "%s", pathname);
 561       if (stat_buf.st_dev != dir_ids[dir_curr].dev ||
 562           stat_buf.st_ino != dir_ids[dir_curr].ino)
 563         error (1, 0, _("%s changed during execution of %s"), starting_dir, program_name);
 564
 565       for (namep = name_space; *namep; namep += file_len - pathname_len + 1)
 566         {
 567           /* Append this directory entry's name to the path being searched. */
 568           file_len = pathname_len + strlen (namep);
 569           if (file_len > cur_path_size)
 570             {
 571               while (file_len > cur_path_size)
 572                 cur_path_size += 1024;
 573               if (cur_path)
 574                 free (cur_path);
 575               cur_path = xmalloc (cur_path_size);
 576               strcpy (cur_path, pathname);
 577               cur_path[pathname_len - 2] = '/';
 578             }
 579           cur_name = cur_path + pathname_len - 1;
 580           strcpy (cur_name, namep);
 581
 582           curdepth++;
 583           if (!no_leaf_check)
 584             /* Normal case optimization.
 585                On normal Unix filesystems, a directory that has no
 586                subdirectories has two links: its name, and ".".  Any
 587                additional links are to the ".." entries of its
 588                subdirectories.  Once we have processed as many
 589                subdirectories as there are additional links, we know
 590                that the rest of the entries are non-directories --
 591                in other words, leaf files. */
 592             subdirs_left -= process_path (cur_path, cur_name,
 593                                           subdirs_left == 0, pathname);
 594           else
 595             /* There might be weird (e.g., CD-ROM or MS-DOS) filesystems
 596                mounted, which don't have Unix-like directory link counts. */
 597             process_path (cur_path, cur_name, false, pathname);
 598           curdepth--;
 599         }
 600
 601       if (strcmp (name, "."))
 602         {
 603           /* We could go back and do the next command-line arg
 604              instead, maybe using longjmp.  */
 605           char const *dir;
 606
 607           if (!dereference)
 608             dir = "..";
 609           else
 610             {
 611               chdir_back ();
 612               dir = parent;
 613             }
 614
 615           if (chdir (dir) != 0)
 616             error (1, errno, "%s", parent);
 617
 618           /* Check that we are where we should be. */
 619           if ((*xstat) (".", &stat_buf) != 0)
 620             error (1, errno, "%s", pathname);
 621           if (stat_buf.st_dev !=
 622               (dir_curr > 0 ? dir_ids[dir_curr-1].dev : starting_stat_buf.st_dev) ||
 623               stat_buf.st_ino !=
 624               (dir_curr > 0 ? dir_ids[dir_curr-1].ino : starting_stat_buf.st_ino))
 625             {
 626               if (dereference)
 627                 error (1, 0, _("%s changed during execution of %s"), parent, program_name);
 628               else
 629                 error (1, 0, _("%s/.. changed during execution of %s"), starting_dir, program_name);
 630             }
 631         }
 632
 633       if (cur_path)
 634         free (cur_path);
 635       free (name_space);
 636     }
 637 }
 638 \f
 639 /* Return true if there are no side effects in any of the predicates in
 640    predicate list PRED, false if there are any. */
 641
 642 static boolean
 643 no_side_effects (struct predicate *pred)
 644 {
 645   while (pred != NULL)
 646     {
 647       if (pred->side_effects)
 648         return (false);
 649       pred = pred->pred_next;
 650     }
 651   return (true);
 652 }
 653 \f
 654 /* Return true if there are no predicates with no_default_print in
 655    predicate list PRED, false if there are any.
 656    Returns true if default print should be performed */
 657
 658 static boolean
 659 default_prints (struct predicate *pred)
 660 {
 661   while (pred != NULL)
 662     {
 663       if (pred->no_default_print)
 664         return (false);
 665       pred = pred->pred_next;
 666     }
 667   return (true);
 668 }