du.c revision 184654
11590Srgrimes/* 21590Srgrimes * Copyright (c) 1989, 1993, 1994 31590Srgrimes * The Regents of the University of California. All rights reserved. 41590Srgrimes * 51590Srgrimes * This code is derived from software contributed to Berkeley by 61590Srgrimes * Chris Newcomb. 71590Srgrimes * 81590Srgrimes * Redistribution and use in source and binary forms, with or without 91590Srgrimes * modification, are permitted provided that the following conditions 101590Srgrimes * are met: 111590Srgrimes * 1. Redistributions of source code must retain the above copyright 121590Srgrimes * notice, this list of conditions and the following disclaimer. 131590Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 141590Srgrimes * notice, this list of conditions and the following disclaimer in the 151590Srgrimes * documentation and/or other materials provided with the distribution. 161590Srgrimes * 3. All advertising materials mentioning features or use of this software 171590Srgrimes * must display the following acknowledgement: 181590Srgrimes * This product includes software developed by the University of 191590Srgrimes * California, Berkeley and its contributors. 201590Srgrimes * 4. Neither the name of the University nor the names of its contributors 211590Srgrimes * may be used to endorse or promote products derived from this software 221590Srgrimes * without specific prior written permission. 231590Srgrimes * 241590Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 251590Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 261590Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 271590Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 281590Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 291590Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 301590Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 311590Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 321590Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 331590Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 341590Srgrimes * SUCH DAMAGE. 351590Srgrimes */ 361590Srgrimes 371590Srgrimes#ifndef lint 3841568Sarchiestatic const char copyright[] = 391590Srgrimes"@(#) Copyright (c) 1989, 1993, 1994\n\ 401590Srgrimes The Regents of the University of California. All rights reserved.\n"; 411590Srgrimes#endif /* not lint */ 421590Srgrimes 431590Srgrimes#ifndef lint 4456597Smharo#if 0 4541568Sarchiestatic const char sccsid[] = "@(#)du.c 8.5 (Berkeley) 5/4/95"; 4656597Smharo#endif 471590Srgrimes#endif /* not lint */ 4899112Sobrien#include <sys/cdefs.h> 4999112Sobrien__FBSDID("$FreeBSD: head/usr.bin/du/du.c 184654 2008-11-04 19:17:32Z mlaier $"); 501590Srgrimes 511590Srgrimes#include <sys/param.h> 5278158Sroam#include <sys/queue.h> 531590Srgrimes#include <sys/stat.h> 541590Srgrimes 551590Srgrimes#include <err.h> 561590Srgrimes#include <errno.h> 5778158Sroam#include <fnmatch.h> 581590Srgrimes#include <fts.h> 59129678Spjd#include <libutil.h> 60132201Stjr#include <locale.h> 61139813Spjd#include <stdint.h> 621590Srgrimes#include <stdio.h> 631590Srgrimes#include <stdlib.h> 641590Srgrimes#include <string.h> 6556597Smharo#include <sysexits.h> 6623693Speter#include <unistd.h> 671590Srgrimes 6878158SroamSLIST_HEAD(ignhead, ignentry) ignores; 6978158Sroamstruct ignentry { 7078158Sroam char *mask; 7178158Sroam SLIST_ENTRY(ignentry) next; 7278158Sroam}; 7378158Sroam 74128772Skientzlestatic int linkchk(FTSENT *); 7592920Simpstatic void usage(void); 76129678Spjdvoid prthumanval(int64_t); 7792920Simpvoid ignoreadd(const char *); 7892920Simpvoid ignoreclean(void); 7992920Simpint ignorep(FTSENT *); 801590Srgrimes 81158339Smaximint nodumpflag = 0; 82158339Smaxim 831590Srgrimesint 84100822Sdwmalonemain(int argc, char *argv[]) 851590Srgrimes{ 8632097Sjkh FTS *fts; 8732097Sjkh FTSENT *p; 88184654Smlaier off_t savednumber; 89139813Spjd long blocksize; 9032097Sjkh int ftsoptions; 9132097Sjkh int listall; 9232097Sjkh int depth; 93176561Skeramida int Hflag, Lflag, Pflag, aflag, sflag, dflag, cflag; 94176561Skeramida int hflag, lflag, ch, notused, rval; 9532097Sjkh char **save; 9687216Smarkm static char dot[] = "."; 971590Srgrimes 98132201Stjr setlocale(LC_ALL, ""); 99132201Stjr 100176561Skeramida Hflag = Lflag = Pflag = aflag = sflag = dflag = cflag = hflag = 101176561Skeramida lflag = 0; 102128772Skientzle 1031590Srgrimes save = argv; 10432097Sjkh ftsoptions = 0; 105184654Smlaier savednumber = 0; 10619120Sscrappy depth = INT_MAX; 10778158Sroam SLIST_INIT(&ignores); 108128772Skientzle 109176561Skeramida while ((ch = getopt(argc, argv, "HI:LPasd:chklmnrx")) != -1) 1101590Srgrimes switch (ch) { 111184654Smlaier case 'H': 112184654Smlaier Hflag = 1; 113184654Smlaier break; 114184654Smlaier case 'I': 115184654Smlaier ignoreadd(optarg); 116184654Smlaier break; 117184654Smlaier case 'L': 118184654Smlaier if (Pflag) 11919120Sscrappy usage(); 120184654Smlaier Lflag = 1; 121184654Smlaier break; 122184654Smlaier case 'P': 123184654Smlaier if (Lflag) 124184654Smlaier usage(); 125184654Smlaier Pflag = 1; 126184654Smlaier break; 127184654Smlaier case 'a': 128184654Smlaier aflag = 1; 129184654Smlaier break; 130184654Smlaier case 's': 131184654Smlaier sflag = 1; 132184654Smlaier break; 133184654Smlaier case 'd': 134184654Smlaier dflag = 1; 135184654Smlaier errno = 0; 136184654Smlaier depth = atoi(optarg); 137184654Smlaier if (errno == ERANGE || depth < 0) { 138184654Smlaier warnx("invalid argument to option d: %s", 139184654Smlaier optarg); 140184654Smlaier usage(); 141184654Smlaier } 142184654Smlaier break; 143184654Smlaier case 'c': 144184654Smlaier cflag = 1; 145184654Smlaier break; 146184654Smlaier case 'h': 147184654Smlaier if (setenv("BLOCKSIZE", "512", 1) == -1) 148184654Smlaier warn("setenv: cannot set BLOCKSIZE=512"); 149184654Smlaier hflag = 1; 150184654Smlaier break; 151184654Smlaier case 'k': 152184654Smlaier hflag = 0; 153184654Smlaier if (setenv("BLOCKSIZE", "1024", 1) == -1) 154184654Smlaier warn("setenv: cannot set BLOCKSIZE=1024"); 155184654Smlaier break; 156184654Smlaier case 'l': 157184654Smlaier lflag = 1; 158184654Smlaier break; 159184654Smlaier case 'm': 160184654Smlaier hflag = 0; 161184654Smlaier if (setenv("BLOCKSIZE", "1048576", 1) == -1) 162184654Smlaier warn("setenv: cannot set BLOCKSIZE=1048576"); 163184654Smlaier break; 164184654Smlaier case 'n': 165184654Smlaier nodumpflag = 1; 166184654Smlaier break; 167184654Smlaier case 'r': /* Compatibility. */ 168184654Smlaier break; 169184654Smlaier case 'x': 170184654Smlaier ftsoptions |= FTS_XDEV; 171184654Smlaier break; 172184654Smlaier case '?': 173184654Smlaier default: 174184654Smlaier usage(); 175184654Smlaier /* NOTREACHED */ 1761590Srgrimes } 17732097Sjkh 1781590Srgrimes argc -= optind; 1791590Srgrimes argv += optind; 1801590Srgrimes 1811590Srgrimes /* 1821590Srgrimes * XXX 1831590Srgrimes * Because of the way that fts(3) works, logical walks will not count 1841590Srgrimes * the blocks actually used by symbolic links. We rationalize this by 1851590Srgrimes * noting that users computing logical sizes are likely to do logical 1861590Srgrimes * copies, so not counting the links is correct. The real reason is 1871590Srgrimes * that we'd have to re-implement the kernel's symbolic link traversing 1881590Srgrimes * algorithm to get this right. If, for example, you have relative 1891590Srgrimes * symbolic links referencing other relative symbolic links, it gets 1901590Srgrimes * very nasty, very fast. The bottom line is that it's documented in 1911590Srgrimes * the man page, so it's a feature. 1921590Srgrimes */ 19332097Sjkh 19432097Sjkh if (Hflag + Lflag + Pflag > 1) 19532097Sjkh usage(); 19632097Sjkh 19732097Sjkh if (Hflag + Lflag + Pflag == 0) 19832097Sjkh Pflag = 1; /* -P (physical) is default */ 19932097Sjkh 2001590Srgrimes if (Hflag) 2011590Srgrimes ftsoptions |= FTS_COMFOLLOW; 20232097Sjkh 20332097Sjkh if (Lflag) 2041590Srgrimes ftsoptions |= FTS_LOGICAL; 2051590Srgrimes 20632097Sjkh if (Pflag) 20732097Sjkh ftsoptions |= FTS_PHYSICAL; 20832097Sjkh 20932097Sjkh listall = 0; 21032097Sjkh 2111590Srgrimes if (aflag) { 21219120Sscrappy if (sflag || dflag) 2131590Srgrimes usage(); 21432097Sjkh listall = 1; 21519120Sscrappy } else if (sflag) { 21619120Sscrappy if (dflag) 21719120Sscrappy usage(); 21832097Sjkh depth = 0; 2191590Srgrimes } 2201590Srgrimes 2211590Srgrimes if (!*argv) { 2221590Srgrimes argv = save; 22387216Smarkm argv[0] = dot; 2241590Srgrimes argv[1] = NULL; 2251590Srgrimes } 2261590Srgrimes 227184654Smlaier (void)getbsize(¬used, &blocksize); 2281590Srgrimes blocksize /= 512; 2291590Srgrimes 23032097Sjkh rval = 0; 231128772Skientzle 2321590Srgrimes if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 23332097Sjkh err(1, "fts_open"); 2341590Srgrimes 23532097Sjkh while ((p = fts_read(fts)) != NULL) { 2361590Srgrimes switch (p->fts_info) { 237184654Smlaier case FTS_D: /* Ignore. */ 238184654Smlaier if (ignorep(p)) 239184654Smlaier fts_set(fts, p, FTS_SKIP); 240184654Smlaier break; 241184654Smlaier case FTS_DP: 242184654Smlaier if (ignorep(p)) 2431590Srgrimes break; 24478158Sroam 245184654Smlaier p->fts_parent->fts_bignum += p->fts_bignum += 246184654Smlaier p->fts_statp->st_blocks; 247128772Skientzle 248184654Smlaier if (p->fts_level <= depth) { 249184654Smlaier if (hflag) { 250184654Smlaier prthumanval(howmany(p->fts_bignum, 251184654Smlaier blocksize)); 252184654Smlaier (void)printf("\t%s\n", p->fts_path); 253184654Smlaier } else { 254184654Smlaier (void)printf("%jd\t%s\n", 255184654Smlaier (intmax_t)howmany(p->fts_bignum, 256184654Smlaier blocksize), p->fts_path); 25758601Scharnier } 258184654Smlaier } 259184654Smlaier break; 260184654Smlaier case FTS_DC: /* Ignore. */ 261184654Smlaier break; 262184654Smlaier case FTS_DNR: /* Warn, continue. */ 263184654Smlaier case FTS_ERR: 264184654Smlaier case FTS_NS: 265184654Smlaier warnx("%s: %s", p->fts_path, strerror(p->fts_errno)); 266184654Smlaier rval = 1; 267184654Smlaier break; 268184654Smlaier default: 269184654Smlaier if (ignorep(p)) 27032097Sjkh break; 271184654Smlaier 272184654Smlaier if (lflag == 0 && p->fts_statp->st_nlink > 1 && 273184654Smlaier linkchk(p)) 27432097Sjkh break; 27578158Sroam 276184654Smlaier if (listall || p->fts_level == 0) { 277184654Smlaier if (hflag) { 278184654Smlaier prthumanval(howmany( 279184654Smlaier p->fts_statp->st_blocks, 280184654Smlaier blocksize)); 281184654Smlaier (void)printf("\t%s\n", p->fts_path); 282184654Smlaier } else { 283184654Smlaier (void)printf("%jd\t%s\n", 284184654Smlaier (intmax_t)howmany( 285184654Smlaier p->fts_statp->st_blocks, 286184654Smlaier blocksize), p->fts_path); 28758601Scharnier } 288184654Smlaier } 28932097Sjkh 290184654Smlaier p->fts_parent->fts_bignum += p->fts_statp->st_blocks; 2911590Srgrimes } 292139813Spjd savednumber = p->fts_parent->fts_bignum; 29332097Sjkh } 29432097Sjkh 2951590Srgrimes if (errno) 2961590Srgrimes err(1, "fts_read"); 29732097Sjkh 29858601Scharnier if (cflag) { 29956597Smharo if (hflag) { 300184654Smlaier prthumanval(howmany(savednumber, blocksize)); 301184654Smlaier (void)printf("\ttotal\n"); 30256597Smharo } else { 303184654Smlaier (void)printf("%jd\ttotal\n", (intmax_t)howmany( 304184654Smlaier savednumber, blocksize)); 30556597Smharo } 30658601Scharnier } 30732097Sjkh 30878158Sroam ignoreclean(); 30928891Swosch exit(rval); 3101590Srgrimes} 3111590Srgrimes 312128772Skientzlestatic int 313128772Skientzlelinkchk(FTSENT *p) 314128772Skientzle{ 315128772Skientzle struct links_entry { 316128806Skientzle struct links_entry *next; 317128806Skientzle struct links_entry *previous; 318128806Skientzle int links; 319128806Skientzle dev_t dev; 320128806Skientzle ino_t ino; 321128772Skientzle }; 322128806Skientzle static const size_t links_hash_initial_size = 8192; 323128806Skientzle static struct links_entry **buckets; 324128806Skientzle static struct links_entry *free_list; 325128806Skientzle static size_t number_buckets; 326128806Skientzle static unsigned long number_entries; 327128806Skientzle static char stop_allocating; 328128806Skientzle struct links_entry *le, **new_buckets; 329128806Skientzle struct stat *st; 330128806Skientzle size_t i, new_size; 331144840Sstefanf int hash; 33232097Sjkh 333128772Skientzle st = p->fts_statp; 33432097Sjkh 335128772Skientzle /* If necessary, initialize the hash table. */ 336128772Skientzle if (buckets == NULL) { 337128772Skientzle number_buckets = links_hash_initial_size; 338128772Skientzle buckets = malloc(number_buckets * sizeof(buckets[0])); 339128772Skientzle if (buckets == NULL) 340128834Skientzle errx(1, "No memory for hardlink detection"); 341128772Skientzle for (i = 0; i < number_buckets; i++) 342128772Skientzle buckets[i] = NULL; 343128772Skientzle } 3441590Srgrimes 345128772Skientzle /* If the hash table is getting too full, enlarge it. */ 346128772Skientzle if (number_entries > number_buckets * 10 && !stop_allocating) { 347128772Skientzle new_size = number_buckets * 2; 348128772Skientzle new_buckets = malloc(new_size * sizeof(struct links_entry *)); 349128772Skientzle 350128772Skientzle /* Try releasing the free list to see if that helps. */ 351128772Skientzle if (new_buckets == NULL && free_list != NULL) { 352128772Skientzle while (free_list != NULL) { 353128772Skientzle le = free_list; 354128772Skientzle free_list = le->next; 355128772Skientzle free(le); 356128772Skientzle } 357184654Smlaier new_buckets = malloc(new_size * 358184654Smlaier sizeof(new_buckets[0])); 359128772Skientzle } 360128772Skientzle 361128772Skientzle if (new_buckets == NULL) { 362128772Skientzle stop_allocating = 1; 363128834Skientzle warnx("No more memory for tracking hard links"); 364128772Skientzle } else { 365128772Skientzle memset(new_buckets, 0, 366128772Skientzle new_size * sizeof(struct links_entry *)); 367128772Skientzle for (i = 0; i < number_buckets; i++) { 368128772Skientzle while (buckets[i] != NULL) { 369128772Skientzle /* Remove entry from old bucket. */ 370128772Skientzle le = buckets[i]; 371128772Skientzle buckets[i] = le->next; 372128772Skientzle 373128772Skientzle /* Add entry to new bucket. */ 374128772Skientzle hash = (le->dev ^ le->ino) % new_size; 375128772Skientzle 376128772Skientzle if (new_buckets[hash] != NULL) 377128772Skientzle new_buckets[hash]->previous = 378128772Skientzle le; 379128772Skientzle le->next = new_buckets[hash]; 380128772Skientzle le->previous = NULL; 381128772Skientzle new_buckets[hash] = le; 382128772Skientzle } 383128772Skientzle } 384128772Skientzle free(buckets); 385128772Skientzle buckets = new_buckets; 386128772Skientzle number_buckets = new_size; 387128772Skientzle } 388128772Skientzle } 389128772Skientzle 390128772Skientzle /* Try to locate this entry in the hash table. */ 391128772Skientzle hash = ( st->st_dev ^ st->st_ino ) % number_buckets; 392128772Skientzle for (le = buckets[hash]; le != NULL; le = le->next) { 393128772Skientzle if (le->dev == st->st_dev && le->ino == st->st_ino) { 394128772Skientzle /* 395128772Skientzle * Save memory by releasing an entry when we've seen 396128772Skientzle * all of it's links. 397128772Skientzle */ 398128772Skientzle if (--le->links <= 0) { 399128772Skientzle if (le->previous != NULL) 400128772Skientzle le->previous->next = le->next; 401128772Skientzle if (le->next != NULL) 402128772Skientzle le->next->previous = le->previous; 403128772Skientzle if (buckets[hash] == le) 404128772Skientzle buckets[hash] = le->next; 405128772Skientzle number_entries--; 406128772Skientzle /* Recycle this node through the free list */ 407128772Skientzle if (stop_allocating) { 408128772Skientzle free(le); 409128772Skientzle } else { 410128772Skientzle le->next = free_list; 411128772Skientzle free_list = le; 412128772Skientzle } 413128772Skientzle } 414128772Skientzle return (1); 415128772Skientzle } 416128772Skientzle } 417128772Skientzle 418128772Skientzle if (stop_allocating) 419128772Skientzle return (0); 420128772Skientzle 421128772Skientzle /* Add this entry to the links cache. */ 422128772Skientzle if (free_list != NULL) { 423128772Skientzle /* Pull a node from the free list if we can. */ 424128772Skientzle le = free_list; 425128772Skientzle free_list = le->next; 426128772Skientzle } else 427128772Skientzle /* Malloc one if we have to. */ 428128772Skientzle le = malloc(sizeof(struct links_entry)); 429128772Skientzle if (le == NULL) { 430128772Skientzle stop_allocating = 1; 431128834Skientzle warnx("No more memory for tracking hard links"); 432128772Skientzle return (0); 433128772Skientzle } 434128772Skientzle le->dev = st->st_dev; 435128772Skientzle le->ino = st->st_ino; 436128772Skientzle le->links = st->st_nlink - 1; 437128772Skientzle number_entries++; 438128772Skientzle le->next = buckets[hash]; 439128772Skientzle le->previous = NULL; 440128772Skientzle if (buckets[hash] != NULL) 441128772Skientzle buckets[hash]->previous = le; 442128772Skientzle buckets[hash] = le; 4431590Srgrimes return (0); 4441590Srgrimes} 4451590Srgrimes 446129678Spjdvoid 447129678Spjdprthumanval(int64_t bytes) 44856597Smharo{ 449129678Spjd char buf[5]; 45056597Smharo 451129678Spjd bytes *= DEV_BSIZE; 45256597Smharo 453129678Spjd humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE, 454129678Spjd HN_B | HN_NOSPACE | HN_DECIMAL); 45556597Smharo 456129678Spjd (void)printf("%4s", buf); 45756597Smharo} 45856597Smharo 45927099Scharnierstatic void 460100822Sdwmaloneusage(void) 4611590Srgrimes{ 4621590Srgrimes (void)fprintf(stderr, 463176561Skeramida "usage: du [-H | -L | -P] [-a | -s | -d depth] [-c] " 464176561Skeramida "[-l] [-h | -k | -m] [-n] [-x] [-I mask] [file ...]\n"); 46556597Smharo exit(EX_USAGE); 4661590Srgrimes} 46778158Sroam 46878158Sroamvoid 469100822Sdwmaloneignoreadd(const char *mask) 47078158Sroam{ 47178158Sroam struct ignentry *ign; 47278158Sroam 47378158Sroam ign = calloc(1, sizeof(*ign)); 47478158Sroam if (ign == NULL) 47578158Sroam errx(1, "cannot allocate memory"); 47678158Sroam ign->mask = strdup(mask); 47778158Sroam if (ign->mask == NULL) 47878158Sroam errx(1, "cannot allocate memory"); 47978158Sroam SLIST_INSERT_HEAD(&ignores, ign, next); 48078158Sroam} 48178158Sroam 48278158Sroamvoid 483100822Sdwmaloneignoreclean(void) 48478158Sroam{ 48578158Sroam struct ignentry *ign; 48678158Sroam 48778158Sroam while (!SLIST_EMPTY(&ignores)) { 48878158Sroam ign = SLIST_FIRST(&ignores); 48978158Sroam SLIST_REMOVE_HEAD(&ignores, next); 49078158Sroam free(ign->mask); 49178158Sroam free(ign); 49278158Sroam } 49378158Sroam} 49478158Sroam 49578158Sroamint 496100822Sdwmaloneignorep(FTSENT *ent) 49778158Sroam{ 49878158Sroam struct ignentry *ign; 49978158Sroam 500158339Smaxim if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP)) 501158339Smaxim return 1; 50278158Sroam SLIST_FOREACH(ign, &ignores, next) 50378158Sroam if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH) 50478158Sroam return 1; 50578158Sroam return 0; 50678158Sroam} 507