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