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