usr.bin/du/du.c

   1 /*      $NetBSD: du.c,v 1.35 2011/09/01 13:37:33 joerg Exp $    */
   2
   3 /*
   4  * Copyright (c) 1989, 1993, 1994
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Chris Newcomb.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  */
  34
  35 #include <sys/cdefs.h>
  36 #ifndef lint
  37 __COPYRIGHT("@(#) Copyright (c) 1989, 1993, 1994\
  38  The Regents of the University of California.  All rights reserved.");
  39 #endif /* not lint */
  40
  41 #ifndef lint
  42 #if 0
  43 static char sccsid[] = "@(#)du.c        8.5 (Berkeley) 5/4/95";
  44 #else
  45 __RCSID("$NetBSD: du.c,v 1.35 2011/09/01 13:37:33 joerg Exp $");
  46 #endif
  47 #endif /* not lint */
  48
  49 #include <sys/param.h>
  50 #include <sys/types.h>
  51 #include <sys/stat.h>
  52
  53 #include <dirent.h>
  54 #include <err.h>
  55 #include <errno.h>
  56 #include <fts.h>
  57 #include <util.h>
  58 #include <stdio.h>
  59 #include <stdlib.h>
  60 #include <string.h>
  61 #include <unistd.h>
  62 #include <limits.h>
  63
  64 static int      linkchk(dev_t, ino_t);
  65 static void     prstat(const char *, int64_t);
  66 __dead static void      usage(void);
  67
  68 static int hflag;
  69 static long blocksize;
  70
  71 int
  72 main(int argc, char *argv[])
  73 {
  74         FTS *fts;
  75         FTSENT *p;
  76         int64_t totalblocks;
  77         int ftsoptions, listfiles;
  78         int depth;
  79         int Hflag, Lflag, aflag, ch, cflag, dflag, gkmflag, nflag, rval, sflag;
  80         const char *noargv[2];
  81
  82         Hflag = Lflag = aflag = cflag = dflag = gkmflag = nflag = sflag = 0;
  83         totalblocks = 0;
  84         ftsoptions = FTS_PHYSICAL;
  85         depth = INT_MAX;
  86         while ((ch = getopt(argc, argv, "HLPacd:ghkmnrsx")) != -1)
  87                 switch (ch) {
  88                 case 'H':
  89                         Hflag = 1;
  90                         Lflag = 0;
  91                         break;
  92                 case 'L':
  93                         Lflag = 1;
  94                         Hflag = 0;
  95                         break;
  96                 case 'P':
  97                         Hflag = Lflag = 0;
  98                         break;
  99                 case 'a':
 100                         aflag = 1;
 101                         break;
 102                 case 'c':
 103                         cflag = 1;
 104                         break;
 105                 case 'd':
 106                         dflag = 1;
 107                         depth = atoi(optarg);
 108                         if (depth < 0 || depth > SHRT_MAX) {
 109                                 warnx("invalid argument to option d: %s",
 110                                         optarg);
 111                                 usage();
 112                         }
 113                         break;
 114                 case 'g':
 115                         blocksize = 1024 * 1024 * 1024;
 116                         gkmflag = 1;
 117                         break;
 118                 case 'h':
 119                         hflag = 1;
 120                         break;
 121                 case 'k':
 122                         blocksize = 1024;
 123                         gkmflag = 1;
 124                         break;
 125                 case 'm':
 126                         blocksize = 1024 * 1024;
 127                         gkmflag = 1;
 128                         break;
 129                 case 'n':
 130                         nflag = 1;
 131                         break;
 132                 case 'r':
 133                         break;
 134                 case 's':
 135                         sflag = 1;
 136                         break;
 137                 case 'x':
 138                         ftsoptions |= FTS_XDEV;
 139                         break;
 140                 case '?':
 141                 default:
 142                         usage();
 143                 }
 144         argc -= optind;
 145         argv += optind;
 146
 147         /*
 148          * XXX
 149          * Because of the way that fts(3) works, logical walks will not count
 150          * the blocks actually used by symbolic links.  We rationalize this by
 151          * noting that users computing logical sizes are likely to do logical
 152          * copies, so not counting the links is correct.  The real reason is
 153          * that we'd have to re-implement the kernel's symbolic link traversing
 154          * algorithm to get this right.  If, for example, you have relative
 155          * symbolic links referencing other relative symbolic links, it gets
 156          * very nasty, very fast.  The bottom line is that it's documented in
 157          * the man page, so it's a feature.
 158          */
 159         if (Hflag)
 160                 ftsoptions |= FTS_COMFOLLOW;
 161         if (Lflag) {
 162                 ftsoptions &= ~FTS_PHYSICAL;
 163                 ftsoptions |= FTS_LOGICAL;
 164         }
 165
 166         listfiles = 0;
 167         if (aflag) {
 168                 if (sflag || dflag)
 169                         usage();
 170                 listfiles = 1;
 171         } else if (sflag) {
 172                 if (dflag)
 173                         usage();
 174                 depth = 0;
 175         }
 176
 177         if (!*argv) {
 178                 noargv[0] = ".";
 179                 noargv[1] = NULL;
 180                 argv = __UNCONST(noargv);
 181         }
 182
 183         if (!gkmflag)
 184                 (void)getbsize(NULL, &blocksize);
 185         blocksize /= 512;
 186
 187         if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL)
 188                 err(1, "fts_open `%s'", *argv);
 189
 190         for (rval = 0; (p = fts_read(fts)) != NULL;) {
 191                 if (nflag) {
 192                         switch (p->fts_info) {
 193                         case FTS_NS:
 194                         case FTS_SLNONE:
 195                                 /* nothing */
 196                                 break;
 197                         default:
 198                                 if (p->fts_statp->st_flags & UF_NODUMP) {
 199                                         fts_set(fts, p, FTS_SKIP);
 200                                         continue;
 201                                 }
 202                         }
 203                 }
 204                 switch (p->fts_info) {
 205                 case FTS_D:                     /* Ignore. */
 206                         break;
 207                 case FTS_DP:
 208                         p->fts_parent->fts_number +=
 209                             p->fts_number += p->fts_statp->st_blocks;
 210                         if (cflag)
 211                                 totalblocks += p->fts_statp->st_blocks;
 212                         /*
 213                          * If listing each directory, or not listing files
 214                          * or directories and this is post-order of the
 215                          * root of a traversal, display the total.
 216                          */
 217                         if (p->fts_level <= depth
 218                             || (!listfiles && !p->fts_level))
 219                                 prstat(p->fts_path, p->fts_number);
 220                         break;
 221                 case FTS_DC:                    /* Ignore. */
 222                         break;
 223                 case FTS_DNR:                   /* Warn, continue. */
 224                 case FTS_ERR:
 225                 case FTS_NS:
 226                         warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
 227                         rval = 1;
 228                         break;
 229                 default:
 230                         if (p->fts_statp->st_nlink > 1 &&
 231                             linkchk(p->fts_statp->st_dev, p->fts_statp->st_ino))
 232                                 break;
 233                         /*
 234                          * If listing each file, or a non-directory file was
 235                          * the root of a traversal, display the total.
 236                          */
 237                         if (listfiles || !p->fts_level)
 238                                 prstat(p->fts_path, p->fts_statp->st_blocks);
 239                         p->fts_parent->fts_number += p->fts_statp->st_blocks;
 240                         if (cflag)
 241                                 totalblocks += p->fts_statp->st_blocks;
 242                 }
 243         }
 244         if (errno)
 245                 err(1, "fts_read");
 246         if (cflag)
 247                 prstat("total", totalblocks);
 248         exit(rval);
 249 }
 250
 251 static void
 252 prstat(const char *fname, int64_t blocks)
 253 {
 254         if (hflag) {
 255                 char buf[5];
 256                 int64_t sz = blocks * 512;
 257
 258                 humanize_number(buf, sizeof(buf), sz, "", HN_AUTOSCALE,
 259                     HN_B | HN_NOSPACE | HN_DECIMAL);
 260
 261                 (void)printf("%s\t%s\n", buf, fname);
 262         } else
 263                 (void)printf("%lld\t%s\n",
 264                     (long long)howmany(blocks, (int64_t)blocksize),
 265                     fname);
 266 }
 267
 268 static int
 269 linkchk(dev_t dev, ino_t ino)
 270 {
 271         static struct entry {
 272                 dev_t   dev;
 273                 ino_t   ino;
 274         } *htable;
 275         static int htshift;  /* log(allocated size) */
 276         static int htmask;   /* allocated size - 1 */
 277         static int htused;   /* 2*number of insertions */
 278         static int sawzero;  /* Whether zero is in table or not */
 279         int h, h2;
 280         uint64_t tmp;
 281         /* this constant is (1<<64)/((1+sqrt(5))/2)
 282          * aka (word size)/(golden ratio)
 283          */
 284         const uint64_t HTCONST = 11400714819323198485ULL;
 285         const int HTBITS = CHAR_BIT * sizeof(tmp);
 286
 287         /* Never store zero in hashtable */
 288         if (dev == 0 && ino == 0) {
 289                 h = sawzero;
 290                 sawzero = 1;
 291                 return h;
 292         }
 293
 294         /* Extend hash table if necessary, keep load under 0.5 */
 295         if (htused<<1 >= htmask) {
 296                 struct entry *ohtable;
 297
 298                 if (!htable)
 299                         htshift = 10;   /* starting hashtable size */
 300                 else
 301                         htshift++;   /* exponential hashtable growth */
 302
 303                 htmask  = (1 << htshift) - 1;
 304                 htused = 0;
 305
 306                 ohtable = htable;
 307                 htable = calloc(htmask+1, sizeof(*htable));
 308                 if (!htable)
 309                         err(1, "calloc");
 310
 311                 /* populate newly allocated hashtable */
 312                 if (ohtable) {
 313                         int i;
 314                         for (i = 0; i <= htmask>>1; i++)
 315                                 if (ohtable[i].ino || ohtable[i].dev)
 316                                         linkchk(ohtable[i].dev, ohtable[i].ino);
 317                         free(ohtable);
 318                 }
 319         }
 320
 321         /* multiplicative hashing */
 322         tmp = dev;
 323         tmp <<= HTBITS>>1;
 324         tmp |=  ino;
 325         tmp *= HTCONST;
 326         h  = tmp >> (HTBITS - htshift);
 327         h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
 328
 329         /* open address hashtable search with double hash probing */
 330         while (htable[h].ino || htable[h].dev) {
 331                 if ((htable[h].ino == ino) && (htable[h].dev == dev))
 332                         return 1;
 333                 h = (h + h2) & htmask;
 334         }
 335
 336         /* Insert the current entry into hashtable */
 337         htable[h].dev = dev;
 338         htable[h].ino = ino;
 339         htused++;
 340         return 0;
 341 }
 342
 343 static void
 344 usage(void)
 345 {
 346
 347         (void)fprintf(stderr,
 348                 "usage: du [-H | -L | -P] [-a | -d depth | -s] [-cghkmnrx] [file ...]\n");
 349         exit(1);
 350 }