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