du.c revision 139813
16412SN/A/* 26412SN/A * Copyright (c) 1989, 1993, 1994 36412SN/A * The Regents of the University of California. All rights reserved. 46412SN/A * 56412SN/A * This code is derived from software contributed to Berkeley by 66412SN/A * Chris Newcomb. 76412SN/A * 86412SN/A * Redistribution and use in source and binary forms, with or without 96412SN/A * modification, are permitted provided that the following conditions 106412SN/A * are met: 116412SN/A * 1. Redistributions of source code must retain the above copyright 126412SN/A * notice, this list of conditions and the following disclaimer. 136412SN/A * 2. Redistributions in binary form must reproduce the above copyright 146412SN/A * notice, this list of conditions and the following disclaimer in the 156412SN/A * documentation and/or other materials provided with the distribution. 166412SN/A * 3. All advertising materials mentioning features or use of this software 176412SN/A * must display the following acknowledgement: 186412SN/A * This product includes software developed by the University of 196412SN/A * California, Berkeley and its contributors. 206412SN/A * 4. Neither the name of the University nor the names of its contributors 216412SN/A * may be used to endorse or promote products derived from this software 226412SN/A * without specific prior written permission. 236412SN/A * 246412SN/A * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 256412SN/A * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 266412SN/A * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 276412SN/A * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 286412SN/A * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 296412SN/A * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 306412SN/A * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 316412SN/A * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 326412SN/A * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 336412SN/A * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 346412SN/A * SUCH DAMAGE. 356412SN/A */ 366412SN/A 3712812Sdl#ifndef lint 3815698Sdlstatic const char copyright[] = 3915698Sdl"@(#) Copyright (c) 1989, 1993, 1994\n\ 4015698Sdl The Regents of the University of California. All rights reserved.\n"; 416412SN/A#endif /* not lint */ 426412SN/A 436412SN/A#ifndef lint 446412SN/A#if 0 456412SN/Astatic const char sccsid[] = "@(#)du.c 8.5 (Berkeley) 5/4/95"; 466412SN/A#endif 476412SN/A#endif /* not lint */ 486412SN/A#include <sys/cdefs.h> 496412SN/A__FBSDID("$FreeBSD: head/usr.bin/du/du.c 139813 2005-01-07 00:12:24Z pjd $"); 506412SN/A 516412SN/A#include <sys/param.h> 526412SN/A#include <sys/queue.h> 536412SN/A#include <sys/stat.h> 546412SN/A 556412SN/A#include <err.h> 566412SN/A#include <errno.h> 576412SN/A#include <fnmatch.h> 586412SN/A#include <fts.h> 596412SN/A#include <libutil.h> 606412SN/A#include <locale.h> 616412SN/A#include <stdint.h> 626412SN/A#include <stdio.h> 636412SN/A#include <stdlib.h> 646412SN/A#include <string.h> 656412SN/A#include <sysexits.h> 666412SN/A#include <unistd.h> 676412SN/A 686412SN/ASLIST_HEAD(ignhead, ignentry) ignores; 696412SN/Astruct ignentry { 706412SN/A char *mask; 716412SN/A SLIST_ENTRY(ignentry) next; 727574SN/A}; 736412SN/A 746412SN/Astatic int linkchk(FTSENT *); 756412SN/Astatic void usage(void); 766412SN/Avoid prthumanval(int64_t); 776412SN/Avoid ignoreadd(const char *); 786412SN/Avoid ignoreclean(void); 796412SN/Aint ignorep(FTSENT *); 806412SN/A 816412SN/Aint 826412SN/Amain(int argc, char *argv[]) 836412SN/A{ 846412SN/A FTS *fts; 856412SN/A FTSENT *p; 866412SN/A off_t savednumber = 0; 876412SN/A long blocksize; 886412SN/A int ftsoptions; 896412SN/A int listall; 906412SN/A int depth; 917574SN/A int Hflag, Lflag, Pflag, aflag, sflag, dflag, cflag, hflag, ch, notused, rval; 927574SN/A char **save; 936412SN/A static char dot[] = "."; 946412SN/A 956412SN/A setlocale(LC_ALL, ""); 966412SN/A 9715698Sdl Hflag = Lflag = Pflag = aflag = sflag = dflag = cflag = hflag = 0; 986412SN/A 996412SN/A save = argv; 1006412SN/A ftsoptions = 0; 1016412SN/A depth = INT_MAX; 1026412SN/A SLIST_INIT(&ignores); 1036412SN/A 1046412SN/A while ((ch = getopt(argc, argv, "HI:LPasd:chkmrx")) != -1) 1056412SN/A switch (ch) { 1066412SN/A case 'H': 10715698Sdl Hflag = 1; 10815698Sdl break; 10915698Sdl case 'I': 11015698Sdl ignoreadd(optarg); 1116412SN/A break; 11215698Sdl case 'L': 11315698Sdl if (Pflag) 11415698Sdl usage(); 11515698Sdl Lflag = 1; 11615698Sdl break; 11715698Sdl case 'P': 11815698Sdl if (Lflag) 11915698Sdl usage(); 1206412SN/A Pflag = 1; 1216412SN/A break; 1226412SN/A case 'a': 1236412SN/A aflag = 1; 1246412SN/A break; 1256412SN/A case 's': 1266412SN/A sflag = 1; 1276412SN/A break; 1286412SN/A case 'd': 1296412SN/A dflag = 1; 1306412SN/A errno = 0; 1316412SN/A depth = atoi(optarg); 1326412SN/A if (errno == ERANGE || depth < 0) { 1336412SN/A warnx("invalid argument to option d: %s", optarg); 13412812Sdl usage(); 13515698Sdl } 1366412SN/A break; 13712812Sdl case 'c': 13812812Sdl cflag = 1; 1396649SN/A break; 14015698Sdl case 'h': 1416412SN/A putenv("BLOCKSIZE=512"); 1426412SN/A hflag = 1; 1436412SN/A break; 1446412SN/A case 'k': 1456412SN/A hflag = 0; 1466412SN/A putenv("BLOCKSIZE=1024"); 1476412SN/A break; 1486412SN/A case 'm': 1496412SN/A hflag = 0; 1506412SN/A putenv("BLOCKSIZE=1048576"); 1516412SN/A break; 1526412SN/A case 'r': /* Compatibility. */ 1536412SN/A break; 15412812Sdl case 'x': 1556412SN/A ftsoptions |= FTS_XDEV; 1566412SN/A break; 15712812Sdl case '?': 15812812Sdl default: 15912812Sdl usage(); 1606412SN/A } 1616412SN/A 1626412SN/A argc -= optind; 1636412SN/A argv += optind; 1646412SN/A 1656412SN/A /* 1666412SN/A * XXX 1676412SN/A * Because of the way that fts(3) works, logical walks will not count 1686412SN/A * the blocks actually used by symbolic links. We rationalize this by 1696412SN/A * noting that users computing logical sizes are likely to do logical 1706412SN/A * copies, so not counting the links is correct. The real reason is 1716412SN/A * that we'd have to re-implement the kernel's symbolic link traversing 1726412SN/A * algorithm to get this right. If, for example, you have relative 1736412SN/A * symbolic links referencing other relative symbolic links, it gets 17412812Sdl * very nasty, very fast. The bottom line is that it's documented in 17515698Sdl * the man page, so it's a feature. 1766412SN/A */ 1776412SN/A 17812812Sdl if (Hflag + Lflag + Pflag > 1) 17912812Sdl usage(); 18015698Sdl 18112812Sdl if (Hflag + Lflag + Pflag == 0) 1826649SN/A Pflag = 1; /* -P (physical) is default */ 1836412SN/A 1846412SN/A if (Hflag) 1856412SN/A ftsoptions |= FTS_COMFOLLOW; 1866412SN/A 1876412SN/A if (Lflag) 1886412SN/A ftsoptions |= FTS_LOGICAL; 1896412SN/A 1906412SN/A if (Pflag) 1916412SN/A ftsoptions |= FTS_PHYSICAL; 1926412SN/A 1936412SN/A listall = 0; 1946412SN/A 1956412SN/A if (aflag) { 1966412SN/A if (sflag || dflag) 1976412SN/A usage(); 1986412SN/A listall = 1; 1996412SN/A } else if (sflag) { 2006412SN/A if (dflag) 2016412SN/A usage(); 2026412SN/A depth = 0; 2036412SN/A } 2046412SN/A 2056412SN/A if (!*argv) { 2066412SN/A argv = save; 2076412SN/A argv[0] = dot; 2086412SN/A argv[1] = NULL; 2096412SN/A } 2106412SN/A 2116412SN/A (void) getbsize(¬used, &blocksize); 2126412SN/A blocksize /= 512; 2136412SN/A 2146412SN/A rval = 0; 2156412SN/A 2166412SN/A if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 2176412SN/A err(1, "fts_open"); 2186412SN/A 2196412SN/A while ((p = fts_read(fts)) != NULL) { 2206412SN/A switch (p->fts_info) { 2216412SN/A case FTS_D: /* Ignore. */ 2226412SN/A if (ignorep(p)) 2236412SN/A fts_set(fts, p, FTS_SKIP); 2246412SN/A break; 2256412SN/A case FTS_DP: 2266412SN/A if (ignorep(p)) 2276412SN/A break; 2286412SN/A 2296412SN/A p->fts_parent->fts_bignum += 2308643SN/A p->fts_bignum += p->fts_statp->st_blocks; 2318643SN/A 2328643SN/A if (p->fts_level <= depth) { 2338643SN/A if (hflag) { 2348643SN/A (void) prthumanval(howmany(p->fts_bignum, blocksize)); 2358643SN/A (void) printf("\t%s\n", p->fts_path); 2368643SN/A } else { 2378643SN/A (void) printf("%jd\t%s\n", 2388643SN/A (intmax_t)howmany(p->fts_bignum, blocksize), 2398643SN/A p->fts_path); 2408643SN/A } 2418643SN/A } 2428643SN/A break; 24312812Sdl case FTS_DC: /* Ignore. */ 2448643SN/A break; 2458643SN/A case FTS_DNR: /* Warn, continue. */ 2468643SN/A case FTS_ERR: 2478643SN/A case FTS_NS: 2488643SN/A warnx("%s: %s", p->fts_path, strerror(p->fts_errno)); 24912812Sdl rval = 1; 2508643SN/A break; 25112812Sdl default: 25212812Sdl if (ignorep(p)) 25312812Sdl break; 2548643SN/A 2558643SN/A if (p->fts_statp->st_nlink > 1 && linkchk(p)) 2568643SN/A break; 2578643SN/A 25812812Sdl if (listall || p->fts_level == 0) { 25912812Sdl if (hflag) { 26012812Sdl (void) prthumanval(howmany(p->fts_statp->st_blocks, 26112812Sdl blocksize)); 26212812Sdl (void) printf("\t%s\n", p->fts_path); 26312812Sdl } else { 2648643SN/A (void) printf("%jd\t%s\n", 2658643SN/A (intmax_t)howmany(p->fts_statp->st_blocks, blocksize), 2668643SN/A p->fts_path); 2678643SN/A } 2688643SN/A } 2698643SN/A 2708643SN/A p->fts_parent->fts_bignum += p->fts_statp->st_blocks; 27112812Sdl } 2728643SN/A savednumber = p->fts_parent->fts_bignum; 2738643SN/A } 27415698Sdl 2758643SN/A if (errno) 27615698Sdl err(1, "fts_read"); 2778643SN/A 2788643SN/A if (cflag) { 2796412SN/A if (hflag) { 2806412SN/A (void) prthumanval(howmany(savednumber, blocksize)); 2818643SN/A (void) printf("\ttotal\n"); 2828643SN/A } else { 2838643SN/A (void) printf("%jd\ttotal\n", (intmax_t)howmany(savednumber, blocksize)); 2848643SN/A } 2858643SN/A } 2868643SN/A 2878643SN/A ignoreclean(); 2888643SN/A exit(rval); 2898643SN/A} 2908643SN/A 29112812Sdlstatic int 2928643SN/Alinkchk(FTSENT *p) 2938643SN/A{ 2948643SN/A struct links_entry { 2958643SN/A struct links_entry *next; 2968643SN/A struct links_entry *previous; 2978643SN/A int links; 2986412SN/A dev_t dev; 2998643SN/A ino_t ino; 3008643SN/A }; 3016412SN/A static const size_t links_hash_initial_size = 8192; 3026412SN/A static struct links_entry **buckets; 3036412SN/A static struct links_entry *free_list; 304 static size_t number_buckets; 305 static unsigned long number_entries; 306 static char stop_allocating; 307 struct links_entry *le, **new_buckets; 308 struct stat *st; 309 size_t i, new_size; 310 int count, hash; 311 312 st = p->fts_statp; 313 314 /* If necessary, initialize the hash table. */ 315 if (buckets == NULL) { 316 number_buckets = links_hash_initial_size; 317 buckets = malloc(number_buckets * sizeof(buckets[0])); 318 if (buckets == NULL) 319 errx(1, "No memory for hardlink detection"); 320 for (i = 0; i < number_buckets; i++) 321 buckets[i] = NULL; 322 } 323 324 /* If the hash table is getting too full, enlarge it. */ 325 if (number_entries > number_buckets * 10 && !stop_allocating) { 326 new_size = number_buckets * 2; 327 new_buckets = malloc(new_size * sizeof(struct links_entry *)); 328 count = 0; 329 330 /* Try releasing the free list to see if that helps. */ 331 if (new_buckets == NULL && free_list != NULL) { 332 while (free_list != NULL) { 333 le = free_list; 334 free_list = le->next; 335 free(le); 336 } 337 new_buckets = malloc(new_size * sizeof(new_buckets[0])); 338 } 339 340 if (new_buckets == NULL) { 341 stop_allocating = 1; 342 warnx("No more memory for tracking hard links"); 343 } else { 344 memset(new_buckets, 0, 345 new_size * sizeof(struct links_entry *)); 346 for (i = 0; i < number_buckets; i++) { 347 while (buckets[i] != NULL) { 348 /* Remove entry from old bucket. */ 349 le = buckets[i]; 350 buckets[i] = le->next; 351 352 /* Add entry to new bucket. */ 353 hash = (le->dev ^ le->ino) % new_size; 354 355 if (new_buckets[hash] != NULL) 356 new_buckets[hash]->previous = 357 le; 358 le->next = new_buckets[hash]; 359 le->previous = NULL; 360 new_buckets[hash] = le; 361 } 362 } 363 free(buckets); 364 buckets = new_buckets; 365 number_buckets = new_size; 366 } 367 } 368 369 /* Try to locate this entry in the hash table. */ 370 hash = ( st->st_dev ^ st->st_ino ) % number_buckets; 371 for (le = buckets[hash]; le != NULL; le = le->next) { 372 if (le->dev == st->st_dev && le->ino == st->st_ino) { 373 /* 374 * Save memory by releasing an entry when we've seen 375 * all of it's links. 376 */ 377 if (--le->links <= 0) { 378 if (le->previous != NULL) 379 le->previous->next = le->next; 380 if (le->next != NULL) 381 le->next->previous = le->previous; 382 if (buckets[hash] == le) 383 buckets[hash] = le->next; 384 number_entries--; 385 /* Recycle this node through the free list */ 386 if (stop_allocating) { 387 free(le); 388 } else { 389 le->next = free_list; 390 free_list = le; 391 } 392 } 393 return (1); 394 } 395 } 396 397 if (stop_allocating) 398 return (0); 399 400 /* Add this entry to the links cache. */ 401 if (free_list != NULL) { 402 /* Pull a node from the free list if we can. */ 403 le = free_list; 404 free_list = le->next; 405 } else 406 /* Malloc one if we have to. */ 407 le = malloc(sizeof(struct links_entry)); 408 if (le == NULL) { 409 stop_allocating = 1; 410 warnx("No more memory for tracking hard links"); 411 return (0); 412 } 413 le->dev = st->st_dev; 414 le->ino = st->st_ino; 415 le->links = st->st_nlink - 1; 416 number_entries++; 417 le->next = buckets[hash]; 418 le->previous = NULL; 419 if (buckets[hash] != NULL) 420 buckets[hash]->previous = le; 421 buckets[hash] = le; 422 return (0); 423} 424 425void 426prthumanval(int64_t bytes) 427{ 428 char buf[5]; 429 430 bytes *= DEV_BSIZE; 431 432 humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE, 433 HN_B | HN_NOSPACE | HN_DECIMAL); 434 435 (void)printf("%4s", buf); 436} 437 438static void 439usage(void) 440{ 441 (void)fprintf(stderr, 442 "usage: du [-H | -L | -P] [-a | -s | -d depth] [-c] [-h | -k | -m] [-x] [-I mask] [file ...]\n"); 443 exit(EX_USAGE); 444} 445 446void 447ignoreadd(const char *mask) 448{ 449 struct ignentry *ign; 450 451 ign = calloc(1, sizeof(*ign)); 452 if (ign == NULL) 453 errx(1, "cannot allocate memory"); 454 ign->mask = strdup(mask); 455 if (ign->mask == NULL) 456 errx(1, "cannot allocate memory"); 457 SLIST_INSERT_HEAD(&ignores, ign, next); 458} 459 460void 461ignoreclean(void) 462{ 463 struct ignentry *ign; 464 465 while (!SLIST_EMPTY(&ignores)) { 466 ign = SLIST_FIRST(&ignores); 467 SLIST_REMOVE_HEAD(&ignores, next); 468 free(ign->mask); 469 free(ign); 470 } 471} 472 473int 474ignorep(FTSENT *ent) 475{ 476 struct ignentry *ign; 477 478 SLIST_FOREACH(ign, &ignores, next) 479 if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH) 480 return 1; 481 return 0; 482} 483