du.c revision 158339
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 158339 2006-05-06 22:04:59Z maxim $"); 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; 88139813Spjd off_t savednumber = 0; 89139813Spjd long blocksize; 9032097Sjkh int ftsoptions; 9132097Sjkh int listall; 9232097Sjkh int depth; 93108453Smike int Hflag, Lflag, Pflag, aflag, sflag, dflag, cflag, hflag, ch, notused, rval; 9432097Sjkh char **save; 9587216Smarkm static char dot[] = "."; 961590Srgrimes 97132201Stjr setlocale(LC_ALL, ""); 98132201Stjr 9956597Smharo Hflag = Lflag = Pflag = aflag = sflag = dflag = cflag = hflag = 0; 100128772Skientzle 1011590Srgrimes save = argv; 10232097Sjkh ftsoptions = 0; 10319120Sscrappy depth = INT_MAX; 10478158Sroam SLIST_INIT(&ignores); 105128772Skientzle 106158339Smaxim while ((ch = getopt(argc, argv, "HI:LPasd:chkmnrx")) != -1) 1071590Srgrimes switch (ch) { 10832097Sjkh case 'H': 10932097Sjkh Hflag = 1; 11032097Sjkh break; 11178158Sroam case 'I': 11278158Sroam ignoreadd(optarg); 11378158Sroam break; 11432097Sjkh case 'L': 11532097Sjkh if (Pflag) 11632097Sjkh usage(); 11732097Sjkh Lflag = 1; 11832097Sjkh break; 11932097Sjkh case 'P': 12032097Sjkh if (Lflag) 12132097Sjkh usage(); 12232097Sjkh Pflag = 1; 12332097Sjkh break; 12432097Sjkh case 'a': 12532097Sjkh aflag = 1; 12632097Sjkh break; 12732097Sjkh case 's': 12832097Sjkh sflag = 1; 12932097Sjkh break; 13032097Sjkh case 'd': 13132097Sjkh dflag = 1; 13232097Sjkh errno = 0; 13332097Sjkh depth = atoi(optarg); 13432097Sjkh if (errno == ERANGE || depth < 0) { 13558601Scharnier warnx("invalid argument to option d: %s", optarg); 13632097Sjkh usage(); 13732097Sjkh } 13832097Sjkh break; 13932097Sjkh case 'c': 14032097Sjkh cflag = 1; 14132097Sjkh break; 14256597Smharo case 'h': 14356597Smharo putenv("BLOCKSIZE=512"); 14456597Smharo hflag = 1; 14556597Smharo break; 14656597Smharo case 'k': 147112855Sobrien hflag = 0; 148112855Sobrien putenv("BLOCKSIZE=1024"); 14956597Smharo break; 150129986Sphk case 'm': 151129986Sphk hflag = 0; 152129986Sphk putenv("BLOCKSIZE=1048576"); 153129986Sphk break; 154158339Smaxim case 'n': 155158339Smaxim nodumpflag = 1; 156158339Smaxim break; 15756597Smharo case 'r': /* Compatibility. */ 15856597Smharo break; 15956597Smharo case 'x': 16056597Smharo ftsoptions |= FTS_XDEV; 16156597Smharo break; 16232097Sjkh case '?': 16332097Sjkh default: 16419120Sscrappy usage(); 1651590Srgrimes } 16632097Sjkh 1671590Srgrimes argc -= optind; 1681590Srgrimes argv += optind; 1691590Srgrimes 1701590Srgrimes /* 1711590Srgrimes * XXX 1721590Srgrimes * Because of the way that fts(3) works, logical walks will not count 1731590Srgrimes * the blocks actually used by symbolic links. We rationalize this by 1741590Srgrimes * noting that users computing logical sizes are likely to do logical 1751590Srgrimes * copies, so not counting the links is correct. The real reason is 1761590Srgrimes * that we'd have to re-implement the kernel's symbolic link traversing 1771590Srgrimes * algorithm to get this right. If, for example, you have relative 1781590Srgrimes * symbolic links referencing other relative symbolic links, it gets 1791590Srgrimes * very nasty, very fast. The bottom line is that it's documented in 1801590Srgrimes * the man page, so it's a feature. 1811590Srgrimes */ 18232097Sjkh 18332097Sjkh if (Hflag + Lflag + Pflag > 1) 18432097Sjkh usage(); 18532097Sjkh 18632097Sjkh if (Hflag + Lflag + Pflag == 0) 18732097Sjkh Pflag = 1; /* -P (physical) is default */ 18832097Sjkh 1891590Srgrimes if (Hflag) 1901590Srgrimes ftsoptions |= FTS_COMFOLLOW; 19132097Sjkh 19232097Sjkh if (Lflag) 1931590Srgrimes ftsoptions |= FTS_LOGICAL; 1941590Srgrimes 19532097Sjkh if (Pflag) 19632097Sjkh ftsoptions |= FTS_PHYSICAL; 19732097Sjkh 19832097Sjkh listall = 0; 19932097Sjkh 2001590Srgrimes if (aflag) { 20119120Sscrappy if (sflag || dflag) 2021590Srgrimes usage(); 20332097Sjkh listall = 1; 20419120Sscrappy } else if (sflag) { 20519120Sscrappy if (dflag) 20619120Sscrappy usage(); 20732097Sjkh depth = 0; 2081590Srgrimes } 2091590Srgrimes 2101590Srgrimes if (!*argv) { 2111590Srgrimes argv = save; 21287216Smarkm argv[0] = dot; 2131590Srgrimes argv[1] = NULL; 2141590Srgrimes } 2151590Srgrimes 21632097Sjkh (void) getbsize(¬used, &blocksize); 2171590Srgrimes blocksize /= 512; 2181590Srgrimes 21932097Sjkh rval = 0; 220128772Skientzle 2211590Srgrimes if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 22232097Sjkh err(1, "fts_open"); 2231590Srgrimes 22432097Sjkh while ((p = fts_read(fts)) != NULL) { 2251590Srgrimes switch (p->fts_info) { 22632097Sjkh case FTS_D: /* Ignore. */ 22778158Sroam if (ignorep(p)) 22878158Sroam fts_set(fts, p, FTS_SKIP); 2291590Srgrimes break; 23032097Sjkh case FTS_DP: 23178158Sroam if (ignorep(p)) 23278158Sroam break; 23378158Sroam 234139813Spjd p->fts_parent->fts_bignum += 235139813Spjd p->fts_bignum += p->fts_statp->st_blocks; 236128772Skientzle 23758601Scharnier if (p->fts_level <= depth) { 23856597Smharo if (hflag) { 239139813Spjd (void) prthumanval(howmany(p->fts_bignum, blocksize)); 24056597Smharo (void) printf("\t%s\n", p->fts_path); 24156597Smharo } else { 242139813Spjd (void) printf("%jd\t%s\n", 243139813Spjd (intmax_t)howmany(p->fts_bignum, blocksize), 24432097Sjkh p->fts_path); 24556597Smharo } 24658601Scharnier } 24732097Sjkh break; 24832097Sjkh case FTS_DC: /* Ignore. */ 24932097Sjkh break; 25032097Sjkh case FTS_DNR: /* Warn, continue. */ 25132097Sjkh case FTS_ERR: 25232097Sjkh case FTS_NS: 25332097Sjkh warnx("%s: %s", p->fts_path, strerror(p->fts_errno)); 25432097Sjkh rval = 1; 25532097Sjkh break; 25632097Sjkh default: 25778158Sroam if (ignorep(p)) 25878158Sroam break; 25978158Sroam 26032097Sjkh if (p->fts_statp->st_nlink > 1 && linkchk(p)) 26132097Sjkh break; 262128772Skientzle 26358601Scharnier if (listall || p->fts_level == 0) { 26456597Smharo if (hflag) { 26556597Smharo (void) prthumanval(howmany(p->fts_statp->st_blocks, 26656597Smharo blocksize)); 26756597Smharo (void) printf("\t%s\n", p->fts_path); 26856597Smharo } else { 269139813Spjd (void) printf("%jd\t%s\n", 270139813Spjd (intmax_t)howmany(p->fts_statp->st_blocks, blocksize), 27156597Smharo p->fts_path); 27256597Smharo } 27358601Scharnier } 27432097Sjkh 275139813Spjd p->fts_parent->fts_bignum += p->fts_statp->st_blocks; 2761590Srgrimes } 277139813Spjd savednumber = p->fts_parent->fts_bignum; 27832097Sjkh } 27932097Sjkh 2801590Srgrimes if (errno) 2811590Srgrimes err(1, "fts_read"); 28232097Sjkh 28358601Scharnier if (cflag) { 28456597Smharo if (hflag) { 28556597Smharo (void) prthumanval(howmany(savednumber, blocksize)); 28656597Smharo (void) printf("\ttotal\n"); 28756597Smharo } else { 288139813Spjd (void) printf("%jd\ttotal\n", (intmax_t)howmany(savednumber, blocksize)); 28956597Smharo } 29058601Scharnier } 29132097Sjkh 29278158Sroam ignoreclean(); 29328891Swosch exit(rval); 2941590Srgrimes} 2951590Srgrimes 296128772Skientzlestatic int 297128772Skientzlelinkchk(FTSENT *p) 298128772Skientzle{ 299128772Skientzle struct links_entry { 300128806Skientzle struct links_entry *next; 301128806Skientzle struct links_entry *previous; 302128806Skientzle int links; 303128806Skientzle dev_t dev; 304128806Skientzle ino_t ino; 305128772Skientzle }; 306128806Skientzle static const size_t links_hash_initial_size = 8192; 307128806Skientzle static struct links_entry **buckets; 308128806Skientzle static struct links_entry *free_list; 309128806Skientzle static size_t number_buckets; 310128806Skientzle static unsigned long number_entries; 311128806Skientzle static char stop_allocating; 312128806Skientzle struct links_entry *le, **new_buckets; 313128806Skientzle struct stat *st; 314128806Skientzle size_t i, new_size; 315144840Sstefanf int hash; 31632097Sjkh 317128772Skientzle st = p->fts_statp; 31832097Sjkh 319128772Skientzle /* If necessary, initialize the hash table. */ 320128772Skientzle if (buckets == NULL) { 321128772Skientzle number_buckets = links_hash_initial_size; 322128772Skientzle buckets = malloc(number_buckets * sizeof(buckets[0])); 323128772Skientzle if (buckets == NULL) 324128834Skientzle errx(1, "No memory for hardlink detection"); 325128772Skientzle for (i = 0; i < number_buckets; i++) 326128772Skientzle buckets[i] = NULL; 327128772Skientzle } 3281590Srgrimes 329128772Skientzle /* If the hash table is getting too full, enlarge it. */ 330128772Skientzle if (number_entries > number_buckets * 10 && !stop_allocating) { 331128772Skientzle new_size = number_buckets * 2; 332128772Skientzle new_buckets = malloc(new_size * sizeof(struct links_entry *)); 333128772Skientzle 334128772Skientzle /* Try releasing the free list to see if that helps. */ 335128772Skientzle if (new_buckets == NULL && free_list != NULL) { 336128772Skientzle while (free_list != NULL) { 337128772Skientzle le = free_list; 338128772Skientzle free_list = le->next; 339128772Skientzle free(le); 340128772Skientzle } 341128772Skientzle new_buckets = malloc(new_size * sizeof(new_buckets[0])); 342128772Skientzle } 343128772Skientzle 344128772Skientzle if (new_buckets == NULL) { 345128772Skientzle stop_allocating = 1; 346128834Skientzle warnx("No more memory for tracking hard links"); 347128772Skientzle } else { 348128772Skientzle memset(new_buckets, 0, 349128772Skientzle new_size * sizeof(struct links_entry *)); 350128772Skientzle for (i = 0; i < number_buckets; i++) { 351128772Skientzle while (buckets[i] != NULL) { 352128772Skientzle /* Remove entry from old bucket. */ 353128772Skientzle le = buckets[i]; 354128772Skientzle buckets[i] = le->next; 355128772Skientzle 356128772Skientzle /* Add entry to new bucket. */ 357128772Skientzle hash = (le->dev ^ le->ino) % new_size; 358128772Skientzle 359128772Skientzle if (new_buckets[hash] != NULL) 360128772Skientzle new_buckets[hash]->previous = 361128772Skientzle le; 362128772Skientzle le->next = new_buckets[hash]; 363128772Skientzle le->previous = NULL; 364128772Skientzle new_buckets[hash] = le; 365128772Skientzle } 366128772Skientzle } 367128772Skientzle free(buckets); 368128772Skientzle buckets = new_buckets; 369128772Skientzle number_buckets = new_size; 370128772Skientzle } 371128772Skientzle } 372128772Skientzle 373128772Skientzle /* Try to locate this entry in the hash table. */ 374128772Skientzle hash = ( st->st_dev ^ st->st_ino ) % number_buckets; 375128772Skientzle for (le = buckets[hash]; le != NULL; le = le->next) { 376128772Skientzle if (le->dev == st->st_dev && le->ino == st->st_ino) { 377128772Skientzle /* 378128772Skientzle * Save memory by releasing an entry when we've seen 379128772Skientzle * all of it's links. 380128772Skientzle */ 381128772Skientzle if (--le->links <= 0) { 382128772Skientzle if (le->previous != NULL) 383128772Skientzle le->previous->next = le->next; 384128772Skientzle if (le->next != NULL) 385128772Skientzle le->next->previous = le->previous; 386128772Skientzle if (buckets[hash] == le) 387128772Skientzle buckets[hash] = le->next; 388128772Skientzle number_entries--; 389128772Skientzle /* Recycle this node through the free list */ 390128772Skientzle if (stop_allocating) { 391128772Skientzle free(le); 392128772Skientzle } else { 393128772Skientzle le->next = free_list; 394128772Skientzle free_list = le; 395128772Skientzle } 396128772Skientzle } 397128772Skientzle return (1); 398128772Skientzle } 399128772Skientzle } 400128772Skientzle 401128772Skientzle if (stop_allocating) 402128772Skientzle return (0); 403128772Skientzle 404128772Skientzle /* Add this entry to the links cache. */ 405128772Skientzle if (free_list != NULL) { 406128772Skientzle /* Pull a node from the free list if we can. */ 407128772Skientzle le = free_list; 408128772Skientzle free_list = le->next; 409128772Skientzle } else 410128772Skientzle /* Malloc one if we have to. */ 411128772Skientzle le = malloc(sizeof(struct links_entry)); 412128772Skientzle if (le == NULL) { 413128772Skientzle stop_allocating = 1; 414128834Skientzle warnx("No more memory for tracking hard links"); 415128772Skientzle return (0); 416128772Skientzle } 417128772Skientzle le->dev = st->st_dev; 418128772Skientzle le->ino = st->st_ino; 419128772Skientzle le->links = st->st_nlink - 1; 420128772Skientzle number_entries++; 421128772Skientzle le->next = buckets[hash]; 422128772Skientzle le->previous = NULL; 423128772Skientzle if (buckets[hash] != NULL) 424128772Skientzle buckets[hash]->previous = le; 425128772Skientzle buckets[hash] = le; 4261590Srgrimes return (0); 4271590Srgrimes} 4281590Srgrimes 429129678Spjdvoid 430129678Spjdprthumanval(int64_t bytes) 43156597Smharo{ 432129678Spjd char buf[5]; 43356597Smharo 434129678Spjd bytes *= DEV_BSIZE; 43556597Smharo 436129678Spjd humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE, 437129678Spjd HN_B | HN_NOSPACE | HN_DECIMAL); 43856597Smharo 439129678Spjd (void)printf("%4s", buf); 44056597Smharo} 44156597Smharo 44227099Scharnierstatic void 443100822Sdwmaloneusage(void) 4441590Srgrimes{ 4451590Srgrimes (void)fprintf(stderr, 446158339Smaxim "usage: du [-H | -L | -P] [-a | -s | -d depth] [-c] [-h | -k | -m] [-n] [-x] [-I mask] [file ...]\n"); 44756597Smharo exit(EX_USAGE); 4481590Srgrimes} 44978158Sroam 45078158Sroamvoid 451100822Sdwmaloneignoreadd(const char *mask) 45278158Sroam{ 45378158Sroam struct ignentry *ign; 45478158Sroam 45578158Sroam ign = calloc(1, sizeof(*ign)); 45678158Sroam if (ign == NULL) 45778158Sroam errx(1, "cannot allocate memory"); 45878158Sroam ign->mask = strdup(mask); 45978158Sroam if (ign->mask == NULL) 46078158Sroam errx(1, "cannot allocate memory"); 46178158Sroam SLIST_INSERT_HEAD(&ignores, ign, next); 46278158Sroam} 46378158Sroam 46478158Sroamvoid 465100822Sdwmaloneignoreclean(void) 46678158Sroam{ 46778158Sroam struct ignentry *ign; 46878158Sroam 46978158Sroam while (!SLIST_EMPTY(&ignores)) { 47078158Sroam ign = SLIST_FIRST(&ignores); 47178158Sroam SLIST_REMOVE_HEAD(&ignores, next); 47278158Sroam free(ign->mask); 47378158Sroam free(ign); 47478158Sroam } 47578158Sroam} 47678158Sroam 47778158Sroamint 478100822Sdwmaloneignorep(FTSENT *ent) 47978158Sroam{ 48078158Sroam struct ignentry *ign; 48178158Sroam 482158339Smaxim if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP)) 483158339Smaxim return 1; 48478158Sroam SLIST_FOREACH(ign, &ignores, next) 48578158Sroam if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH) 48678158Sroam return 1; 48778158Sroam return 0; 48878158Sroam} 489