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., 59 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 #if 0
  63 static boolean no_side_effects PARAMS((struct predicate *pred));
  64 #endif
  65 static boolean default_prints PARAMS((struct predicate *pred));
  66
  67 /* Name this program was run with. */
  68 char *program_name;
  69
  70 /* All predicates for each path to process. */
  71 struct predicate *predicates;
  72
  73 /* The last predicate allocated. */
  74 struct predicate *last_pred;
  75
  76 /* The root of the evaluation tree. */
  77 static struct predicate *eval_tree;
  78
  79 /* If true, process directory before contents.  True unless -depth given. */
  80 boolean do_dir_first;
  81
  82 /* If >=0, don't descend more than this many levels of subdirectories. */
  83 int maxdepth;
  84
  85 /* If >=0, don't process files above this level. */
  86 int mindepth;
  87
  88 /* Current depth; 0 means current path is a command line arg. */
  89 int curdepth;
  90
  91 /* Output block size.  */
  92 int output_block_size;
  93
  94 /* Time at start of execution.  */
  95 time_t start_time;
  96
  97 /* Seconds between 00:00 1/1/70 and either one day before now
  98    (the default), or the start of today (if -daystart is given). */
  99 time_t cur_day_start;
 100
 101 /* If true, cur_day_start has been adjusted to the start of the day. */
 102 boolean full_days;
 103
 104 /* If true, do not assume that files in directories with nlink == 2
 105    are non-directories. */
 106 boolean no_leaf_check;
 107
 108 /* If true, don't cross filesystem boundaries. */
 109 boolean stay_on_filesystem;
 110
 111 /* If true, don't descend past current directory.
 112    Can be set by -prune, -maxdepth, and -xdev/-mount. */
 113 boolean stop_at_current_level;
 114
 115 /* The full path of the initial working directory, or "." if
 116    STARTING_DESC is nonnegative.  */
 117 char const *starting_dir = ".";
 118
 119 /* A file descriptor open to the initial working directory.
 120    Doing it this way allows us to work when the i.w.d. has
 121    unreadable parents.  */
 122 int starting_desc;
 123
 124 /* The stat buffer of the initial working directory. */
 125 struct stat starting_stat_buf;
 126
 127 /* If true, we have called stat on the current path. */
 128 boolean have_stat;
 129
 130 /* The file being operated on, relative to the current directory.
 131    Used for stat, readlink, remove, and opendir.  */
 132 char *rel_pathname;
 133
 134 /* Length of current path. */
 135 int path_length;
 136
 137 /* true if following symlinks.  Should be consistent with xstat.  */
 138 boolean dereference;
 139
 140 /* Pointer to the function used to stat files. */
 141 int (*xstat) ();
 142
 143 /* Status value to return to system. */
 144 int exit_status;
 145
 146 /* If true, we ignore the problem where we find that a directory entry
 147  * no longer exists by the time we get around to processing it.
 148  */
 149 boolean ignore_readdir_race;
 150
 151
 152 #ifdef DEBUG_STAT
 153 static int
 154 debug_stat (file, bufp)
 155      char *file;
 156      struct stat *bufp;
 157 {
 158   fprintf (stderr, "debug_stat (%s)\n", file);
 159   return lstat (file, bufp);
 160 }
 161 #endif /* DEBUG_STAT */
 162 \f
 163 int
 164 main (int argc, char **argv)
 165 {
 166   int i;
 167   PFB parse_function;           /* Pointer to the function which parses. */
 168   struct predicate *cur_pred;
 169   char *predicate_name;         /* Name of predicate being parsed. */
 170
 171   program_name = argv[0];
 172
 173 #ifdef HAVE_SETLOCALE
 174   setlocale (LC_ALL, "");
 175 #endif
 176   bindtextdomain (PACKAGE, LOCALEDIR);
 177   textdomain (PACKAGE);
 178
 179   predicates = NULL;
 180   last_pred = NULL;
 181   do_dir_first = true;
 182   maxdepth = mindepth = -1;
 183   start_time = time (NULL);
 184   cur_day_start = start_time - DAYSECS;
 185   full_days = false;
 186   no_leaf_check = false;
 187   stay_on_filesystem = false;
 188   ignore_readdir_race = false;
 189   exit_status = 0;
 190   dereference = false;
 191 #ifdef DEBUG_STAT
 192   xstat = debug_stat;
 193 #else /* !DEBUG_STAT */
 194   xstat = lstat;
 195 #endif /* !DEBUG_STAT */
 196
 197 #if 0
 198   human_block_size (getenv ("FIND_BLOCK_SIZE"), 0, &output_block_size);
 199 #else
 200   if (getenv("POSIXLY_CORRECT"))
 201     output_block_size = 512;
 202   else
 203     output_block_size = 1024;
 204
 205   if (getenv("FIND_BLOCK_SIZE"))
 206     {
 207       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"));
 208     }
 209
 210 #endif
 211
 212 #ifdef DEBUG
 213   printf ("cur_day_start = %s", ctime (&cur_day_start));
 214 #endif /* DEBUG */
 215
 216   /* Find where in ARGV the predicates begin. */
 217   for (i = 1; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
 218     /* Do nothing. */ ;
 219
 220   /* Enclose the expression in `( ... )' so a default -print will
 221      apply to the whole expression. */
 222   parse_open (argv, &argc);
 223   /* Build the input order list. */
 224   while (i < argc)
 225     {
 226       if (strchr ("-!(),", argv[i][0]) == NULL)
 227         usage (_("paths must precede expression"));
 228       predicate_name = argv[i];
 229       parse_function = find_parser (predicate_name);
 230       if (parse_function == NULL)
 231         /* Command line option not recognized */
 232         error (1, 0, _("invalid predicate `%s'"), predicate_name);
 233       i++;
 234       if (!(*parse_function) (argv, &i))
 235         {
 236           if (argv[i] == NULL)
 237             /* Command line option requires an argument */
 238             error (1, 0, _("missing argument to `%s'"), predicate_name);
 239           else
 240             error (1, 0, _("invalid argument `%s' to `%s'"),
 241                    argv[i], predicate_name);
 242         }
 243     }
 244   if (predicates->pred_next == NULL)
 245     {
 246       /* No predicates that do something other than set a global variable
 247          were given; remove the unneeded initial `(' and add `-print'. */
 248       cur_pred = predicates;
 249       predicates = last_pred = predicates->pred_next;
 250       free ((char *) cur_pred);
 251       parse_print (argv, &argc);
 252     }
 253   else if (!default_prints (predicates->pred_next))
 254     {
 255       /* One or more predicates that produce output were given;
 256          remove the unneeded initial `('. */
 257       cur_pred = predicates;
 258       predicates = predicates->pred_next;
 259       free ((char *) cur_pred);
 260     }
 261   else
 262     {
 263       /* `( user-supplied-expression ) -print'. */
 264       parse_close (argv, &argc);
 265       parse_print (argv, &argc);
 266     }
 267
 268 #ifdef  DEBUG
 269   printf (_("Predicate List:\n"));
 270   print_list (predicates);
 271 #endif /* DEBUG */
 272
 273   /* Done parsing the predicates.  Build the evaluation tree. */
 274   cur_pred = predicates;
 275   eval_tree = get_expr (&cur_pred, NO_PREC);
 276
 277   /* Check if we have any left-over predicates (this fixes
 278    * Debian bug #185202).
 279    */
 280   if (cur_pred != NULL)
 281     {
 282       error (1, 0, _("unexpected extra predicate"));
 283     }
 284
 285 #ifdef  DEBUG
 286   printf (_("Eval Tree:\n"));
 287   print_tree (eval_tree, 0);
 288 #endif /* DEBUG */
 289
 290   /* Rearrange the eval tree in optimal-predicate order. */
 291   opt_expr (&eval_tree);
 292
 293   /* Determine the point, if any, at which to stat the file. */
 294   mark_stat (eval_tree);
 295
 296 #ifdef DEBUG
 297   printf (_("Optimized Eval Tree:\n"));
 298   print_tree (eval_tree, 0);
 299 #endif /* DEBUG */
 300
 301   starting_desc = open (".", O_RDONLY);
 302   if (0 <= starting_desc && fchdir (starting_desc) != 0)
 303     {
 304       close (starting_desc);
 305       starting_desc = -1;
 306     }
 307   if (starting_desc < 0)
 308     {
 309       starting_dir = xgetcwd ();
 310       if (! starting_dir)
 311         error (1, errno, _("cannot get current directory"));
 312     }
 313   if ((*xstat) (".", &starting_stat_buf) != 0)
 314     error (1, errno, _("cannot get current directory"));
 315
 316   /* If no paths are given, default to ".".  */
 317   for (i = 1; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
 318     process_top_path (argv[i]);
 319   if (i == 1)
 320     process_top_path (".");
 321
 322   return exit_status;
 323 }
 324 \f
 325 /* Safely go back to the starting directory. */
 326 static void
 327 chdir_back (void)
 328 {
 329   struct stat stat_buf;
 330
 331   if (starting_desc < 0)
 332     {
 333       if (chdir (starting_dir) != 0)
 334         error (1, errno, "%s", starting_dir);
 335       if ((*xstat) (".", &stat_buf) != 0)
 336         error (1, errno, "%s", starting_dir);
 337       if (stat_buf.st_dev != starting_stat_buf.st_dev ||
 338           stat_buf.st_ino != starting_stat_buf.st_ino)
 339         error (1, 0, _("%s changed during execution of %s"), starting_dir, program_name);
 340     }
 341   else
 342     {
 343       if (fchdir (starting_desc) != 0)
 344         error (1, errno, "%s", starting_dir);
 345     }
 346 }
 347 \f
 348 /* Descend PATHNAME, which is a command-line argument.  */
 349
 350 static void
 351 process_top_path (char *pathname)
 352 {
 353   struct stat stat_buf, cur_stat_buf;
 354
 355   curdepth = 0;
 356   path_length = strlen (pathname);
 357
 358   /* We stat each pathname given on the command-line twice --
 359      once here and once in process_path.  It's not too bad, though,
 360      since the kernel can read the stat information out of its inode
 361      cache the second time.  */
 362   if ((*xstat) (pathname, &stat_buf) == 0 && S_ISDIR (stat_buf.st_mode))
 363     {
 364       if (chdir (pathname) < 0)
 365         {
 366           if (!ignore_readdir_race || (errno != ENOENT) )
 367             {
 368               error (0, errno, "%s", pathname);
 369               exit_status = 1;
 370             }
 371           return;
 372         }
 373
 374       /* Check that we are where we should be. */
 375       if ((*xstat) (".", &cur_stat_buf) != 0)
 376         error (1, errno, "%s", pathname);
 377       if (cur_stat_buf.st_dev != stat_buf.st_dev ||
 378           cur_stat_buf.st_ino != stat_buf.st_ino)
 379         error (1, 0, _("%s changed during execution of %s"), pathname, program_name);
 380
 381       process_path (pathname, ".", false, ".");
 382       chdir_back ();
 383     }
 384   else
 385     process_path (pathname, pathname, false, ".");
 386 }
 387
 388 /* Info on each directory in the current tree branch, to avoid
 389    getting stuck in symbolic link loops.  */
 390 struct dir_id
 391 {
 392   ino_t ino;
 393   dev_t dev;
 394 };
 395 static struct dir_id *dir_ids = NULL;
 396 /* Entries allocated in `dir_ids'.  */
 397 static int dir_alloc = 0;
 398 /* Index in `dir_ids' of directory currently being searched.
 399    This is always the last valid entry.  */
 400 static int dir_curr = -1;
 401 /* (Arbitrary) number of entries to grow `dir_ids' by.  */
 402 #define DIR_ALLOC_STEP 32
 403
 404 /* Recursively descend path PATHNAME, applying the predicates.
 405    LEAF is true if PATHNAME is known to be in a directory that has no
 406    more unexamined subdirectories, and therefore it is not a directory.
 407    Knowing this allows us to avoid calling stat as long as possible for
 408    leaf files.
 409
 410    NAME is PATHNAME relative to the current directory.  We access NAME
 411    but print PATHNAME.
 412
 413    PARENT is the path of the parent of NAME, relative to find's
 414    starting directory.
 415
 416    Return nonzero iff PATHNAME is a directory. */
 417
 418 static int
 419 process_path (char *pathname, char *name, boolean leaf, char *parent)
 420 {
 421   struct stat stat_buf;
 422   static dev_t root_dev;        /* Device ID of current argument pathname. */
 423   int i;
 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 #if 0
 641 /* Return true if there are no side effects in any of the predicates in
 642    predicate list PRED, false if there are any. */
 643
 644 static boolean
 645 no_side_effects (struct predicate *pred)
 646 {
 647   while (pred != NULL)
 648     {
 649       if (pred->side_effects)
 650         return (false);
 651       pred = pred->pred_next;
 652     }
 653   return (true);
 654 }
 655 #endif
 656 \f
 657 /* Return true if there are no predicates with no_default_print in
 658    predicate list PRED, false if there are any.
 659    Returns true if default print should be performed */
 660
 661 static boolean
 662 default_prints (struct predicate *pred)
 663 {
 664   while (pred != NULL)
 665     {
 666       if (pred->no_default_print)
 667         return (false);
 668       pred = pred->pred_next;
 669     }
 670   return (true);
 671 }