src/du.c

   1 /* du -- summarize disk usage
   2    Copyright (C) 1988, 1989, 1990, 1991 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., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 /* Differences from the Unix du:
  19    * Doesn't simply ignore the names of regular files given as arguments
  20      when -a is given.
  21    * Additional options:
  22    -l           Count the size of all files, even if they have appeared
  23                 already in another hard link.
  24    -x           Do not cross file-system boundaries during the recursion.
  25    -c           Write a grand total of all of the arguments after all
  26                 arguments have been processed.  This can be used to find
  27                 out the disk usage of a directory, with some files excluded.
  28    -k           Print sizes in kilobytes instead of 512 byte blocks
  29                 (the default required by POSIX).
  30    -b           Print sizes in bytes.
  31    -S           Count the size of each directory separately, not including
  32                 the sizes of subdirectories.
  33    -D           Dereference only symbolic links given on the command line.
  34    -L           Dereference all symbolic links.
  35
  36    By tege@sics.se, Torbjorn Granlund,
  37    and djm@ai.mit.edu, David MacKenzie.  */
  38
  39 #ifdef _AIX
  40  #pragma alloca
  41 #endif
  42
  43 #include <config.h>
  44 #include <stdio.h>
  45 #include <getopt.h>
  46 #include <sys/types.h>
  47 #include "system.h"
  48 #include "version.h"
  49 #include "safe-stat.h"
  50 #include "safe-lstat.h"
  51
  52 /* Initial number of entries in each hash table entry's table of inodes.  */
  53 #define INITIAL_HASH_MODULE 100
  54
  55 /* Initial number of entries in the inode hash table.  */
  56 #define INITIAL_ENTRY_TAB_SIZE 70
  57
  58 /* Initial size to allocate for `path'.  */
  59 #define INITIAL_PATH_SIZE 100
  60
  61 /* Hash structure for inode and device numbers.  The separate entry
  62    structure makes it easier to rehash "in place".  */
  63
  64 struct entry
  65 {
  66   ino_t ino;
  67   dev_t dev;
  68   struct entry *coll_link;
  69 };
  70
  71 /* Structure for a hash table for inode numbers. */
  72
  73 struct htab
  74 {
  75   unsigned modulus;             /* Size of the `hash' pointer vector.  */
  76   struct entry *entry_tab;      /* Pointer to dynamically growing vector.  */
  77   unsigned entry_tab_size;      /* Size of current `entry_tab' allocation.  */
  78   unsigned first_free_entry;    /* Index in `entry_tab'.  */
  79   struct entry *hash[1];        /* Vector of pointers in `entry_tab'.  */
  80 };
  81
  82
  83 /* Structure for dynamically resizable strings. */
  84
  85 typedef struct
  86 {
  87   unsigned alloc;               /* Size of allocation for the text.  */
  88   unsigned length;              /* Length of the text currently.  */
  89   char *text;                   /* Pointer to the text.  */
  90 } *string, stringstruct;
  91
  92 char *savedir ();
  93 #ifndef HAVE_FCHDIR
  94 char *xgetcwd ();
  95 #endif
  96 char *xmalloc ();
  97 char *xrealloc ();
  98 void error ();
  99
 100 static int hash_insert ();
 101 static int hash_insert2 ();
 102 static long count_entry ();
 103 static void du_files ();
 104 static void hash_init ();
 105 static void hash_reset ();
 106 static void str_concatc ();
 107 static void str_copyc ();
 108 static void str_init ();
 109 static void str_trunc ();
 110
 111 /* Name under which this program was invoked.  */
 112 char *program_name;
 113
 114 /* If nonzero, display only a total for each argument. */
 115 static int opt_summarize_only = 0;
 116
 117 /* If nonzero, display counts for all files, not just directories. */
 118 static int opt_all = 0;
 119
 120 /* If nonzero, count each hard link of files with multiple links. */
 121 static int opt_count_all = 0;
 122
 123 /* If nonzero, do not cross file-system boundaries. */
 124 static int opt_one_file_system = 0;
 125
 126 /* If nonzero, print a grand total at the end. */
 127 static int opt_combined_arguments = 0;
 128
 129 /* If nonzero, do not add sizes of subdirectories. */
 130 static int opt_separate_dirs = 0;
 131
 132 /* If nonzero, dereference symlinks that are command line arguments. */
 133 static int opt_dereference_arguments = 0;
 134
 135 enum output_size
 136 {
 137   size_blocks,                  /* 512-byte blocks. */
 138   size_kilobytes,               /* 1K blocks. */
 139   size_bytes                    /* 1-byte blocks. */
 140 };
 141
 142 /* The units to count in. */
 143 static enum output_size output_size;
 144
 145 /* Accumulated path for file or directory being processed.  */
 146 static string path;
 147
 148 /* Pointer to hash structure, used by the hash routines.  */
 149 static struct htab *htab;
 150
 151 /* Globally used stat buffer.  */
 152 static struct stat stat_buf;
 153
 154 /* A pointer to either lstat or stat, depending on whether
 155    dereferencing of all symbolic links is to be done. */
 156 static int (*xstat) ();
 157
 158 /* The exit status to use if we don't get any fatal errors. */
 159 static int exit_status;
 160
 161 /* If non-zero, display usage information and exit.  */
 162 static int show_help;
 163
 164 /* If non-zero, print the version on standard output and exit.  */
 165 static int show_version;
 166
 167 /* Grand total size of all args. */
 168 static long tot_size = 0L;
 169
 170 static struct option const long_options[] =
 171 {
 172   {"all", no_argument, &opt_all, 1},
 173   {"bytes", no_argument, NULL, 'b'},
 174   {"count-links", no_argument, &opt_count_all, 1},
 175   {"dereference", no_argument, NULL, 'L'},
 176   {"dereference-args", no_argument, &opt_dereference_arguments, 1},
 177   {"kilobytes", no_argument, NULL, 'k'},
 178   {"one-file-system", no_argument, &opt_one_file_system, 1},
 179   {"separate-dirs", no_argument, &opt_separate_dirs, 1},
 180   {"summarize", no_argument, &opt_summarize_only, 1},
 181   {"total", no_argument, &opt_combined_arguments, 1},
 182   {"help", no_argument, &show_help, 1},
 183   {"version", no_argument, &show_version, 1},
 184   {NULL, 0, NULL, 0}
 185 };
 186
 187 static void
 188 usage (status, reason)
 189      int status;
 190      char *reason;
 191 {
 192   if (reason != NULL)
 193     fprintf (status == 0 ? stdout : stderr, "%s: %s\n",
 194              program_name, reason);
 195
 196   if (status != 0)
 197     fprintf (stderr, "Try `%s --help' for more information.\n",
 198              program_name);
 199   else
 200     {
 201       printf ("Usage: %s [OPTION]... [PATH]...\n", program_name);
 202       printf ("\
 203 \n\
 204   -a, --all                write counts for all files, not just directories\n\
 205   -b, --bytes              print size in bytes\n\
 206   -c, --total              produce a grand total\n\
 207   -k, --kilobytes          use 1024 blocks, not 512 despite POSIXLY_CORRECT\n\
 208   -l, --count-links        count sizes many times if hard linked\n\
 209   -s, --summarize          display only a total for each argument\n\
 210   -x, --one-file-system    skip directories on different filesystems\n\
 211   -D, --dereference-args   dereference PATHs when symbolic link\n\
 212   -L, --dereference        dereference all symbolic links\n\
 213   -S, --separate-dirs      do not include size of subdirectories\n\
 214       --help               display this help and exit\n\
 215       --version            output version information and exit\n");
 216     }
 217   exit (status);
 218 }
 219 \f
 220 void
 221 main (argc, argv)
 222      int argc;
 223      char *argv[];
 224 {
 225   int c;
 226   char *cwd_only[2];
 227
 228   cwd_only[0] = ".";
 229   cwd_only[1] = NULL;
 230
 231   program_name = argv[0];
 232   xstat = safe_lstat;
 233   output_size = getenv ("POSIXLY_CORRECT") ? size_blocks : size_kilobytes;
 234
 235   while ((c = getopt_long (argc, argv, "abcklsxDLS", long_options, (int *) 0))
 236          != EOF)
 237     {
 238       switch (c)
 239         {
 240         case 0:                 /* Long option. */
 241           break;
 242
 243         case 'a':
 244           opt_all = 1;
 245           break;
 246
 247         case 'b':
 248           output_size = size_bytes;
 249           break;
 250
 251         case 'c':
 252           opt_combined_arguments = 1;
 253           break;
 254
 255         case 'k':
 256           output_size = size_kilobytes;
 257           break;
 258
 259         case 'l':
 260           opt_count_all = 1;
 261           break;
 262
 263         case 's':
 264           opt_summarize_only = 1;
 265           break;
 266
 267         case 'x':
 268           opt_one_file_system = 1;
 269           break;
 270
 271         case 'D':
 272           opt_dereference_arguments = 1;
 273           break;
 274
 275         case 'L':
 276           xstat = safe_stat;
 277           break;
 278
 279         case 'S':
 280           opt_separate_dirs = 1;
 281           break;
 282
 283         default:
 284           usage (2, (char *) 0);
 285         }
 286     }
 287
 288   if (show_version)
 289     {
 290       printf ("%s\n", version_string);
 291       exit (0);
 292     }
 293
 294   if (show_help)
 295     usage (0, NULL);
 296
 297   if (opt_all && opt_summarize_only)
 298     usage (2, "cannot both summarize and show all entries");
 299
 300   /* Initialize the hash structure for inode numbers.  */
 301   hash_init (INITIAL_HASH_MODULE, INITIAL_ENTRY_TAB_SIZE);
 302
 303   str_init (&path, INITIAL_PATH_SIZE);
 304
 305   du_files (optind == argc ? cwd_only : argv + optind);
 306
 307   exit (exit_status);
 308 }
 309 \f
 310 /* Recursively print the sizes of the directories (and, if selected, files)
 311    named in FILES, the last entry of which is NULL.  */
 312
 313 static void
 314 du_files (files)
 315      char **files;
 316 {
 317 #ifdef HAVE_FCHDIR
 318   int wd_desc;
 319 #else
 320   char *wd;
 321 #endif
 322   ino_t initial_ino;            /* Initial directory's inode. */
 323   dev_t initial_dev;            /* Initial directory's device. */
 324   int i;                        /* Index in FILES. */
 325
 326 #ifdef HAVE_FCHDIR
 327   wd_desc = open (".", O_RDONLY);
 328   if (wd_desc < 0)
 329     error (1, errno, "cannot open current directory");
 330 #else
 331   wd = xgetcwd ();
 332   if (wd == NULL)
 333     error (1, errno, "cannot get current directory");
 334 #endif
 335
 336   /* Remember the inode and device number of the current directory.  */
 337   if (SAFE_STAT (".", &stat_buf))
 338     error (1, errno, "current directory");
 339   initial_ino = stat_buf.st_ino;
 340   initial_dev = stat_buf.st_dev;
 341
 342   for (i = 0; files[i]; i++)
 343     {
 344       char *arg;
 345       int s;
 346
 347       arg = files[i];
 348
 349       /* Delete final slash in the argument, unless the slash is alone.  */
 350       s = strlen (arg) - 1;
 351       if (s != 0)
 352         {
 353           if (arg[s] == '/')
 354             arg[s] = 0;
 355
 356           str_copyc (path, arg);
 357         }
 358       else if (arg[0] == '/')
 359         str_trunc (path, 0);    /* Null path for root directory.  */
 360       else
 361         str_copyc (path, arg);
 362
 363       if (!opt_combined_arguments)
 364         hash_reset ();
 365
 366       count_entry (arg, 1, 0);
 367
 368       /* chdir if `count_entry' has changed the working directory.  */
 369       if (SAFE_STAT (".", &stat_buf))
 370         error (1, errno, ".");
 371       if ((stat_buf.st_ino != initial_ino || stat_buf.st_dev != initial_dev)
 372 #ifdef HAVE_FCHDIR
 373           && fchdir (wd_desc) < 0)
 374         error (1, errno, "cannot return to original directory");
 375 #else
 376           && chdir (wd) < 0)
 377         error (1, errno, "cannot change to directory %s", wd);
 378 #endif
 379     }
 380
 381   if (opt_combined_arguments)
 382     {
 383       printf ("%ld\ttotal\n", output_size == size_bytes ? tot_size
 384               : convert_blocks (tot_size, output_size == size_kilobytes));
 385       fflush (stdout);
 386     }
 387
 388 #ifndef HAVE_FCHDIR
 389   free (wd);
 390 #endif
 391 }
 392 \f
 393 /* Print (if appropriate) and return the size
 394    (in units determined by `output_size') of file or directory ENT.
 395    TOP is one for external calls, zero for recursive calls.
 396    LAST_DEV is the device that the parent directory of ENT is on.  */
 397
 398 static long
 399 count_entry (ent, top, last_dev)
 400      char *ent;
 401      int top;
 402      dev_t last_dev;
 403 {
 404   long size;
 405
 406   if (((top && opt_dereference_arguments)
 407        ? SAFE_STAT (ent, &stat_buf)
 408        : (*xstat) (ent, &stat_buf)) < 0)
 409     {
 410       error (0, errno, "%s", path->text);
 411       exit_status = 1;
 412       return 0;
 413     }
 414
 415   if (!opt_count_all
 416       && stat_buf.st_nlink > 1
 417       && hash_insert (stat_buf.st_ino, stat_buf.st_dev))
 418     return 0;                   /* Have counted this already.  */
 419
 420   if (output_size == size_bytes)
 421     size = stat_buf.st_size;
 422   else
 423     size = ST_NBLOCKS (stat_buf);
 424
 425   tot_size += size;
 426
 427   if (S_ISDIR (stat_buf.st_mode))
 428     {
 429       unsigned pathlen;
 430       dev_t dir_dev;
 431       char *name_space;
 432       char *namep;
 433
 434       dir_dev = stat_buf.st_dev;
 435
 436       if (opt_one_file_system && !top && last_dev != dir_dev)
 437         return 0;               /* Don't enter a new file system.  */
 438
 439       if (chdir (ent) < 0)
 440         {
 441           error (0, errno, "cannot change to directory %s", path->text);
 442           exit_status = 1;
 443           return 0;
 444         }
 445
 446       errno = 0;
 447       name_space = savedir (".", stat_buf.st_size);
 448       if (name_space == NULL)
 449         {
 450           if (errno)
 451             {
 452               error (0, errno, "%s", path->text);
 453               if (chdir ("..") < 0)     /* Try to return to previous dir.  */
 454                 error (1, errno, "cannot change to `..' from directory %s",
 455                        path->text);
 456               exit_status = 1;
 457               return 0;
 458             }
 459           else
 460             error (1, 0, "virtual memory exhausted");
 461         }
 462
 463       /* Remember the current path.  */
 464
 465       str_concatc (path, "/");
 466       pathlen = path->length;
 467
 468       namep = name_space;
 469       while (*namep != 0)
 470         {
 471           str_concatc (path, namep);
 472
 473           size += count_entry (namep, 0, dir_dev);
 474
 475           str_trunc (path, pathlen);
 476           namep += strlen (namep) + 1;
 477         }
 478       free (name_space);
 479       if (chdir ("..") < 0)
 480         error (1, errno, "cannot change to `..' from directory %s", path->text);
 481
 482       str_trunc (path, pathlen - 1); /* Remove the "/" we added.  */
 483       if (!opt_summarize_only || top)
 484         {
 485           printf ("%ld\t%s\n", output_size == size_bytes ? size
 486                   : convert_blocks (size, output_size == size_kilobytes),
 487                   path->length > 0 ? path->text : "/");
 488           fflush (stdout);
 489         }
 490       return opt_separate_dirs ? 0 : size;
 491     }
 492   else if (opt_all || top)
 493     {
 494       /* FIXME: make this an option.  */
 495       int print_only_dir_size = 0;
 496       if (!print_only_dir_size)
 497         {
 498           printf ("%ld\t%s\n", output_size == size_bytes ? size
 499                   : convert_blocks (size, output_size == size_kilobytes),
 500                   path->text);
 501           fflush (stdout);
 502         }
 503     }
 504
 505   return size;
 506 }
 507 \f
 508 /* Allocate space for the hash structures, and set the global
 509    variable `htab' to point to it.  The initial hash module is specified in
 510    MODULUS, and the number of entries are specified in ENTRY_TAB_SIZE.  (The
 511    hash structure will be rebuilt when ENTRY_TAB_SIZE entries have been
 512    inserted, and MODULUS and ENTRY_TAB_SIZE in the global `htab' will be
 513    doubled.)  */
 514
 515 static void
 516 hash_init (modulus, entry_tab_size)
 517      unsigned modulus;
 518      unsigned entry_tab_size;
 519 {
 520   struct htab *htab_r;
 521
 522   htab_r = (struct htab *)
 523     xmalloc (sizeof (struct htab) + sizeof (struct entry *) * modulus);
 524
 525   htab_r->entry_tab = (struct entry *)
 526     xmalloc (sizeof (struct entry) * entry_tab_size);
 527
 528   htab_r->modulus = modulus;
 529   htab_r->entry_tab_size = entry_tab_size;
 530   htab = htab_r;
 531
 532   hash_reset ();
 533 }
 534
 535 /* Reset the hash structure in the global variable `htab' to
 536    contain no entries.  */
 537
 538 static void
 539 hash_reset ()
 540 {
 541   int i;
 542   struct entry **p;
 543
 544   htab->first_free_entry = 0;
 545
 546   p = htab->hash;
 547   for (i = htab->modulus; i > 0; i--)
 548     *p++ = NULL;
 549 }
 550
 551 /* Insert an item (inode INO and device DEV) in the hash
 552    structure in the global variable `htab', if an entry with the same data
 553    was not found already.  Return zero if the item was inserted and non-zero
 554    if it wasn't.  */
 555
 556 static int
 557 hash_insert (ino, dev)
 558      ino_t ino;
 559      dev_t dev;
 560 {
 561   struct htab *htab_r = htab;   /* Initially a copy of the global `htab'.  */
 562
 563   if (htab_r->first_free_entry >= htab_r->entry_tab_size)
 564     {
 565       int i;
 566       struct entry *ep;
 567       unsigned modulus;
 568       unsigned entry_tab_size;
 569
 570       /* Increase the number of hash entries, and re-hash the data.
 571          The method of shrimping and increasing is made to compactify
 572          the heap.  If twice as much data would be allocated
 573          straightforwardly, we would never re-use a byte of memory.  */
 574
 575       /* Let `htab' shrimp.  Keep only the header, not the pointer vector.  */
 576
 577       htab_r = (struct htab *)
 578         xrealloc ((char *) htab_r, sizeof (struct htab));
 579
 580       modulus = 2 * htab_r->modulus;
 581       entry_tab_size = 2 * htab_r->entry_tab_size;
 582
 583       /* Increase the number of possible entries.  */
 584
 585       htab_r->entry_tab = (struct entry *)
 586         xrealloc ((char *) htab_r->entry_tab,
 587                  sizeof (struct entry) * entry_tab_size);
 588
 589       /* Increase the size of htab again.  */
 590
 591       htab_r = (struct htab *)
 592         xrealloc ((char *) htab_r,
 593                  sizeof (struct htab) + sizeof (struct entry *) * modulus);
 594
 595       htab_r->modulus = modulus;
 596       htab_r->entry_tab_size = entry_tab_size;
 597       htab = htab_r;
 598
 599       i = htab_r->first_free_entry;
 600
 601       /* Make the increased hash table empty.  The entries are still
 602          available in htab->entry_tab.  */
 603
 604       hash_reset ();
 605
 606       /* Go through the entries and install them in the pointer vector
 607          htab->hash.  The items are actually inserted in htab->entry_tab at
 608          the position where they already are.  The htab->coll_link need
 609          however be updated.  Could be made a little more efficient.  */
 610
 611       for (ep = htab_r->entry_tab; i > 0; i--)
 612         {
 613           hash_insert2 (htab_r, ep->ino, ep->dev);
 614           ep++;
 615         }
 616     }
 617
 618   return hash_insert2 (htab_r, ino, dev);
 619 }
 620
 621 /* Insert INO and DEV in the hash structure HTAB, if not
 622    already present.  Return zero if inserted and non-zero if it
 623    already existed.  */
 624
 625 static int
 626 hash_insert2 (htab, ino, dev)
 627      struct htab *htab;
 628      ino_t ino;
 629      dev_t dev;
 630 {
 631   struct entry **hp, *ep2, *ep;
 632   hp = &htab->hash[ino % htab->modulus];
 633   ep2 = *hp;
 634
 635   /* Collision?  */
 636
 637   if (ep2 != NULL)
 638     {
 639       ep = ep2;
 640
 641       /* Search for an entry with the same data.  */
 642
 643       do
 644         {
 645           if (ep->ino == ino && ep->dev == dev)
 646             return 1;           /* Found an entry with the same data.  */
 647           ep = ep->coll_link;
 648         }
 649       while (ep != NULL);
 650
 651       /* Did not find it.  */
 652
 653     }
 654
 655   ep = *hp = &htab->entry_tab[htab->first_free_entry++];
 656   ep->ino = ino;
 657   ep->dev = dev;
 658   ep->coll_link = ep2;          /* `ep2' is NULL if no collision.  */
 659
 660   return 0;
 661 }
 662 \f
 663 /* Initialize the struct string S1 for holding SIZE characters.  */
 664
 665 static void
 666 str_init (s1, size)
 667      string *s1;
 668      unsigned size;
 669 {
 670   string s;
 671
 672   s = (string) xmalloc (sizeof (stringstruct));
 673   s->text = xmalloc (size + 1);
 674
 675   s->alloc = size;
 676   *s1 = s;
 677 }
 678
 679 static void
 680 ensure_space (s, size)
 681      string s;
 682      unsigned size;
 683 {
 684   if (s->alloc < size)
 685     {
 686       s->text = xrealloc (s->text, size + 1);
 687       s->alloc = size;
 688     }
 689 }
 690
 691 /* Assign the null-terminated C-string CSTR to S1.  */
 692
 693 static void
 694 str_copyc (s1, cstr)
 695      string s1;
 696      char *cstr;
 697 {
 698   unsigned l = strlen (cstr);
 699   ensure_space (s1, l);
 700   strcpy (s1->text, cstr);
 701   s1->length = l;
 702 }
 703
 704 static void
 705 str_concatc (s1, cstr)
 706      string s1;
 707      char *cstr;
 708 {
 709   unsigned l1 = s1->length;
 710   unsigned l2 = strlen (cstr);
 711   unsigned l = l1 + l2;
 712
 713   ensure_space (s1, l);
 714   strcpy (s1->text + l1, cstr);
 715   s1->length = l;
 716 }
 717
 718 /* Truncate the string S1 to have length LENGTH.  */
 719
 720 static void
 721 str_trunc (s1, length)
 722      string s1;
 723      unsigned length;
 724 {
 725   if (s1->length > length)
 726     {
 727       s1->text[length] = 0;
 728       s1->length = length;
 729     }
 730 }