1 /*- 2 * SPDX-License-Identifier: BSD-3-Clause 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 #ifndef lint 36 static const char copyright[] = 37 "@(#) Copyright (c) 1989, 1993, 1994\n\ 38 The Regents of the University of California. All rights reserved.\n"; 39 #endif /* not lint */ 40 41 #ifndef lint 42 #if 0 43 static const char sccsid[] = "@(#)du.c 8.5 (Berkeley) 5/4/95"; 44 #endif 45 #endif /* not lint */ 46 #include <sys/cdefs.h> 47 #include <sys/param.h> 48 #include <sys/queue.h> 49 #include <sys/stat.h> 50 #include <err.h> 51 #include <errno.h> 52 #include <fnmatch.h> 53 #include <fts.h> 54 #include <getopt.h> 55 #include <libutil.h> 56 #include <locale.h> 57 #include <stdint.h> 58 #include <stdio.h> 59 #include <stdlib.h> 60 #include <string.h> 61 #include <sysexits.h> 62 #include <unistd.h> 63 64 #define SI_OPT (CHAR_MAX + 1) 65 66 #define UNITS_2 1 67 #define UNITS_SI 2 68 69 static SLIST_HEAD(ignhead, ignentry) ignores; 70 struct ignentry { 71 char *mask; 72 SLIST_ENTRY(ignentry) next; 73 }; 74 75 static int linkchk(FTSENT *); 76 static void usage(void); 77 static void prthumanval(int64_t); 78 static void ignoreadd(const char *); 79 static void ignoreclean(void); 80 static int ignorep(FTSENT *); 81 static void siginfo(int __unused); 82 83 static int nodumpflag = 0; 84 static int Aflag, hflag; 85 static long blocksize, cblocksize; 86 static volatile sig_atomic_t info; 87 88 static const struct option long_options[] = 89 { 90 { "si", no_argument, NULL, SI_OPT }, 91 { NULL, no_argument, NULL, 0 }, 92 }; 93 94 int 95 main(int argc, char *argv[]) 96 { 97 FTS *fts; 98 FTSENT *p; 99 off_t savednumber, curblocks; 100 off_t threshold, threshold_sign; 101 int ftsoptions; 102 int depth; 103 int Hflag, Lflag, aflag, sflag, dflag, cflag; 104 int lflag, ch, notused, rval; 105 char **save; 106 static char dot[] = "."; 107 108 setlocale(LC_ALL, ""); 109 110 Hflag = Lflag = aflag = sflag = dflag = cflag = lflag = Aflag = 0; 111 112 save = argv; 113 ftsoptions = FTS_PHYSICAL; 114 savednumber = 0; 115 threshold = 0; 116 threshold_sign = 1; 117 cblocksize = DEV_BSIZE; 118 blocksize = 0; 119 depth = INT_MAX; 120 SLIST_INIT(&ignores); 121 122 while ((ch = getopt_long(argc, argv, "+AB:HI:LPasd:cghklmnrt:x", 123 long_options, NULL)) != -1) 124 switch (ch) { 125 case 'A': 126 Aflag = 1; 127 break; 128 case 'B': 129 errno = 0; 130 cblocksize = atoi(optarg); 131 if (errno == ERANGE || cblocksize <= 0) { 132 warnx("invalid argument to option B: %s", 133 optarg); 134 usage(); 135 } 136 break; 137 case 'H': 138 Hflag = 1; 139 Lflag = 0; 140 break; 141 case 'I': 142 ignoreadd(optarg); 143 break; 144 case 'L': 145 Lflag = 1; 146 Hflag = 0; 147 break; 148 case 'P': 149 Hflag = Lflag = 0; 150 break; 151 case 'a': 152 aflag = 1; 153 break; 154 case 's': 155 sflag = 1; 156 break; 157 case 'd': 158 dflag = 1; 159 errno = 0; 160 depth = atoi(optarg); 161 if (errno == ERANGE || depth < 0) { 162 warnx("invalid argument to option d: %s", 163 optarg); 164 usage(); 165 } 166 break; 167 case 'c': 168 cflag = 1; 169 break; 170 case 'g': 171 hflag = 0; 172 blocksize = 1073741824; 173 break; 174 case 'h': 175 hflag = UNITS_2; 176 break; 177 case 'k': 178 hflag = 0; 179 blocksize = 1024; 180 break; 181 case 'l': 182 lflag = 1; 183 break; 184 case 'm': 185 hflag = 0; 186 blocksize = 1048576; 187 break; 188 case 'n': 189 nodumpflag = 1; 190 break; 191 case 'r': /* Compatibility. */ 192 break; 193 case 't' : 194 if (expand_number(optarg, &threshold) != 0 || 195 threshold == 0) { 196 warnx("invalid threshold: %s", optarg); 197 usage(); 198 } else if (threshold < 0) 199 threshold_sign = -1; 200 break; 201 case 'x': 202 ftsoptions |= FTS_XDEV; 203 break; 204 case SI_OPT: 205 hflag = UNITS_SI; 206 break; 207 case '?': 208 default: 209 usage(); 210 /* NOTREACHED */ 211 } 212 213 argc -= optind; 214 argv += optind; 215 216 /* 217 * XXX 218 * Because of the way that fts(3) works, logical walks will not count 219 * the blocks actually used by symbolic links. We rationalize this by 220 * noting that users computing logical sizes are likely to do logical 221 * copies, so not counting the links is correct. The real reason is 222 * that we'd have to re-implement the kernel's symbolic link traversing 223 * algorithm to get this right. If, for example, you have relative 224 * symbolic links referencing other relative symbolic links, it gets 225 * very nasty, very fast. The bottom line is that it's documented in 226 * the man page, so it's a feature. 227 */ 228 229 if (Hflag) 230 ftsoptions |= FTS_COMFOLLOW; 231 if (Lflag) { 232 ftsoptions &= ~FTS_PHYSICAL; 233 ftsoptions |= FTS_LOGICAL; 234 } 235 236 if (!Aflag && (cblocksize % DEV_BSIZE) != 0) 237 cblocksize = howmany(cblocksize, DEV_BSIZE) * DEV_BSIZE; 238 239 if (aflag + dflag + sflag > 1) 240 usage(); 241 if (sflag) 242 depth = 0; 243 244 if (!*argv) { 245 argv = save; 246 argv[0] = dot; 247 argv[1] = NULL; 248 } 249 250 if (blocksize == 0) 251 (void)getbsize(¬used, &blocksize); 252 253 if (!Aflag) { 254 cblocksize /= DEV_BSIZE; 255 blocksize /= DEV_BSIZE; 256 } 257 258 if (threshold != 0) 259 threshold = howmany(threshold / DEV_BSIZE * cblocksize, 260 blocksize); 261 262 rval = 0; 263 264 (void)signal(SIGINFO, siginfo); 265 266 if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 267 err(1, "fts_open"); 268 269 while (errno = 0, (p = fts_read(fts)) != NULL) { 270 switch (p->fts_info) { 271 case FTS_D: /* Ignore. */ 272 if (ignorep(p)) 273 fts_set(fts, p, FTS_SKIP); 274 break; 275 case FTS_DP: 276 if (ignorep(p)) 277 break; 278 279 curblocks = Aflag ? 280 howmany(p->fts_statp->st_size, cblocksize) : 281 howmany(p->fts_statp->st_blocks, cblocksize); 282 p->fts_parent->fts_bignum += p->fts_bignum += 283 curblocks; 284 285 if (p->fts_level <= depth && threshold <= 286 threshold_sign * howmany(p->fts_bignum * 287 cblocksize, blocksize)) { 288 if (hflag > 0) { 289 prthumanval(p->fts_bignum); 290 (void)printf("\t%s\n", p->fts_path); 291 } else { 292 (void)printf("%jd\t%s\n", 293 (intmax_t)howmany(p->fts_bignum * 294 cblocksize, blocksize), 295 p->fts_path); 296 } 297 } 298 if (info) { 299 info = 0; 300 (void)printf("\t%s\n", p->fts_path); 301 } 302 break; 303 case FTS_DC: /* Ignore. */ 304 break; 305 case FTS_DNR: /* Warn, continue. */ 306 case FTS_ERR: 307 case FTS_NS: 308 warnx("%s: %s", p->fts_path, strerror(p->fts_errno)); 309 rval = 1; 310 break; 311 default: 312 if (ignorep(p)) 313 break; 314 315 if (lflag == 0 && p->fts_statp->st_nlink > 1 && 316 linkchk(p)) 317 break; 318 319 curblocks = Aflag ? 320 howmany(p->fts_statp->st_size, cblocksize) : 321 howmany(p->fts_statp->st_blocks, cblocksize); 322 323 if (aflag || p->fts_level == 0) { 324 if (hflag > 0) { 325 prthumanval(curblocks); 326 (void)printf("\t%s\n", p->fts_path); 327 } else { 328 (void)printf("%jd\t%s\n", 329 (intmax_t)howmany(curblocks * 330 cblocksize, blocksize), 331 p->fts_path); 332 } 333 } 334 335 p->fts_parent->fts_bignum += curblocks; 336 } 337 savednumber = p->fts_parent->fts_bignum; 338 } 339 340 if (errno) 341 err(1, "fts_read"); 342 343 if (cflag) { 344 if (hflag > 0) { 345 prthumanval(savednumber); 346 (void)printf("\ttotal\n"); 347 } else { 348 (void)printf("%jd\ttotal\n", (intmax_t)howmany( 349 savednumber * cblocksize, blocksize)); 350 } 351 } 352 353 ignoreclean(); 354 exit(rval); 355 } 356 357 static int 358 linkchk(FTSENT *p) 359 { 360 struct links_entry { 361 struct links_entry *next; 362 struct links_entry *previous; 363 int links; 364 dev_t dev; 365 ino_t ino; 366 }; 367 static const size_t links_hash_initial_size = 8192; 368 static struct links_entry **buckets; 369 static struct links_entry *free_list; 370 static size_t number_buckets; 371 static unsigned long number_entries; 372 static char stop_allocating; 373 struct links_entry *le, **new_buckets; 374 struct stat *st; 375 size_t i, new_size; 376 int hash; 377 378 st = p->fts_statp; 379 380 /* If necessary, initialize the hash table. */ 381 if (buckets == NULL) { 382 number_buckets = links_hash_initial_size; 383 buckets = malloc(number_buckets * sizeof(buckets[0])); 384 if (buckets == NULL) 385 errx(1, "No memory for hardlink detection"); 386 for (i = 0; i < number_buckets; i++) 387 buckets[i] = NULL; 388 } 389 390 /* If the hash table is getting too full, enlarge it. */ 391 if (number_entries > number_buckets * 10 && !stop_allocating) { 392 new_size = number_buckets * 2; 393 new_buckets = calloc(new_size, sizeof(struct links_entry *)); 394 395 /* Try releasing the free list to see if that helps. */ 396 if (new_buckets == NULL && free_list != NULL) { 397 while (free_list != NULL) { 398 le = free_list; 399 free_list = le->next; 400 free(le); 401 } 402 new_buckets = calloc(new_size, sizeof(new_buckets[0])); 403 } 404 405 if (new_buckets == NULL) { 406 stop_allocating = 1; 407 warnx("No more memory for tracking hard links"); 408 } else { 409 for (i = 0; i < number_buckets; i++) { 410 while (buckets[i] != NULL) { 411 /* Remove entry from old bucket. */ 412 le = buckets[i]; 413 buckets[i] = le->next; 414 415 /* Add entry to new bucket. */ 416 hash = (le->dev ^ le->ino) % new_size; 417 418 if (new_buckets[hash] != NULL) 419 new_buckets[hash]->previous = 420 le; 421 le->next = new_buckets[hash]; 422 le->previous = NULL; 423 new_buckets[hash] = le; 424 } 425 } 426 free(buckets); 427 buckets = new_buckets; 428 number_buckets = new_size; 429 } 430 } 431 432 /* Try to locate this entry in the hash table. */ 433 hash = ( st->st_dev ^ st->st_ino ) % number_buckets; 434 for (le = buckets[hash]; le != NULL; le = le->next) { 435 if (le->dev == st->st_dev && le->ino == st->st_ino) { 436 /* 437 * Save memory by releasing an entry when we've seen 438 * all of its links. 439 */ 440 if (--le->links <= 0) { 441 if (le->previous != NULL) 442 le->previous->next = le->next; 443 if (le->next != NULL) 444 le->next->previous = le->previous; 445 if (buckets[hash] == le) 446 buckets[hash] = le->next; 447 number_entries--; 448 /* Recycle this node through the free list */ 449 if (stop_allocating) { 450 free(le); 451 } else { 452 le->next = free_list; 453 free_list = le; 454 } 455 } 456 return (1); 457 } 458 } 459 460 if (stop_allocating) 461 return (0); 462 463 /* Add this entry to the links cache. */ 464 if (free_list != NULL) { 465 /* Pull a node from the free list if we can. */ 466 le = free_list; 467 free_list = le->next; 468 } else 469 /* Malloc one if we have to. */ 470 le = malloc(sizeof(struct links_entry)); 471 if (le == NULL) { 472 stop_allocating = 1; 473 warnx("No more memory for tracking hard links"); 474 return (0); 475 } 476 le->dev = st->st_dev; 477 le->ino = st->st_ino; 478 le->links = st->st_nlink - 1; 479 number_entries++; 480 le->next = buckets[hash]; 481 le->previous = NULL; 482 if (buckets[hash] != NULL) 483 buckets[hash]->previous = le; 484 buckets[hash] = le; 485 return (0); 486 } 487 488 static void 489 prthumanval(int64_t bytes) 490 { 491 char buf[5]; 492 int flags; 493 494 bytes *= cblocksize; 495 flags = HN_B | HN_NOSPACE | HN_DECIMAL; 496 if (!Aflag) 497 bytes *= DEV_BSIZE; 498 if (hflag == UNITS_SI) 499 flags |= HN_DIVISOR_1000; 500 501 humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE, flags); 502 503 (void)printf("%4s", buf); 504 } 505 506 static void 507 usage(void) 508 { 509 (void)fprintf(stderr, 510 "usage: du [-Aclnx] [-H | -L | -P] [-g | -h | -k | -m] " 511 "[-a | -s | -d depth] [-B blocksize] [-I mask] " 512 "[-t threshold] [file ...]\n"); 513 exit(EX_USAGE); 514 } 515 516 static void 517 ignoreadd(const char *mask) 518 { 519 struct ignentry *ign; 520 521 ign = calloc(1, sizeof(*ign)); 522 if (ign == NULL) 523 errx(1, "cannot allocate memory"); 524 ign->mask = strdup(mask); 525 if (ign->mask == NULL) 526 errx(1, "cannot allocate memory"); 527 SLIST_INSERT_HEAD(&ignores, ign, next); 528 } 529 530 static void 531 ignoreclean(void) 532 { 533 struct ignentry *ign; 534 535 while (!SLIST_EMPTY(&ignores)) { 536 ign = SLIST_FIRST(&ignores); 537 SLIST_REMOVE_HEAD(&ignores, next); 538 free(ign->mask); 539 free(ign); 540 } 541 } 542 543 static int 544 ignorep(FTSENT *ent) 545 { 546 struct ignentry *ign; 547 548 if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP)) 549 return 1; 550 SLIST_FOREACH(ign, &ignores, next) 551 if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH) 552 return 1; 553 return 0; 554 } 555 556 static void 557 siginfo(int sig __unused) 558 { 559 560 info = 1; 561 } 562