du.c revision 184742
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 184742 2008-11-06 23:55:28Z 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); 76184656Smlaierstatic void prthumanval(int64_t); 77184656Smlaierstatic void ignoreadd(const char *); 78184656Smlaierstatic void ignoreclean(void); 79184656Smlaierstatic int ignorep(FTSENT *); 801590Srgrimes 81184656Smlaierstatic int nodumpflag = 0; 82184733Smlaierstatic int Aflag; 83184733Smlaierstatic long blocksize, cblocksize; 84158339Smaxim 851590Srgrimesint 86100822Sdwmalonemain(int argc, char *argv[]) 871590Srgrimes{ 8832097Sjkh FTS *fts; 8932097Sjkh FTSENT *p; 90184733Smlaier off_t savednumber, curblocks; 9132097Sjkh int ftsoptions; 9232097Sjkh int listall; 9332097Sjkh int depth; 94176561Skeramida int Hflag, Lflag, Pflag, aflag, sflag, dflag, cflag; 95176561Skeramida int hflag, lflag, ch, notused, rval; 9632097Sjkh char **save; 9787216Smarkm static char dot[] = "."; 981590Srgrimes 99132201Stjr setlocale(LC_ALL, ""); 100132201Stjr 101176561Skeramida Hflag = Lflag = Pflag = aflag = sflag = dflag = cflag = hflag = 102184733Smlaier lflag = Aflag = 0; 103128772Skientzle 1041590Srgrimes save = argv; 10532097Sjkh ftsoptions = 0; 106184654Smlaier savednumber = 0; 107184733Smlaier cblocksize = DEV_BSIZE; 108184733Smlaier blocksize = 0; 10919120Sscrappy depth = INT_MAX; 11078158Sroam SLIST_INIT(&ignores); 111128772Skientzle 112184733Smlaier while ((ch = getopt(argc, argv, "AB:HI:LPasd:chklmnrx")) != -1) 1131590Srgrimes switch (ch) { 114184733Smlaier case 'A': 115184733Smlaier Aflag = 1; 116184733Smlaier break; 117184733Smlaier case 'B': 118184733Smlaier errno = 0; 119184733Smlaier cblocksize = atoi(optarg); 120184733Smlaier if (errno == ERANGE || cblocksize <= 0) { 121184733Smlaier warnx("invalid argument to option B: %s", 122184733Smlaier optarg); 123184733Smlaier usage(); 124184733Smlaier } 125184733Smlaier break; 126184654Smlaier case 'H': 127184654Smlaier Hflag = 1; 128184654Smlaier break; 129184654Smlaier case 'I': 130184654Smlaier ignoreadd(optarg); 131184654Smlaier break; 132184654Smlaier case 'L': 133184654Smlaier if (Pflag) 13419120Sscrappy usage(); 135184654Smlaier Lflag = 1; 136184654Smlaier break; 137184654Smlaier case 'P': 138184654Smlaier if (Lflag) 139184654Smlaier usage(); 140184654Smlaier Pflag = 1; 141184654Smlaier break; 142184654Smlaier case 'a': 143184654Smlaier aflag = 1; 144184654Smlaier break; 145184654Smlaier case 's': 146184654Smlaier sflag = 1; 147184654Smlaier break; 148184654Smlaier case 'd': 149184654Smlaier dflag = 1; 150184654Smlaier errno = 0; 151184654Smlaier depth = atoi(optarg); 152184654Smlaier if (errno == ERANGE || depth < 0) { 153184654Smlaier warnx("invalid argument to option d: %s", 154184654Smlaier optarg); 155184654Smlaier usage(); 156184654Smlaier } 157184654Smlaier break; 158184654Smlaier case 'c': 159184654Smlaier cflag = 1; 160184654Smlaier break; 161184654Smlaier case 'h': 162184654Smlaier hflag = 1; 163184654Smlaier break; 164184654Smlaier case 'k': 165184654Smlaier hflag = 0; 166184733Smlaier blocksize = 1024; 167184654Smlaier break; 168184654Smlaier case 'l': 169184654Smlaier lflag = 1; 170184654Smlaier break; 171184654Smlaier case 'm': 172184654Smlaier hflag = 0; 173184733Smlaier blocksize = 1048576; 174184654Smlaier break; 175184654Smlaier case 'n': 176184654Smlaier nodumpflag = 1; 177184654Smlaier break; 178184654Smlaier case 'r': /* Compatibility. */ 179184654Smlaier break; 180184654Smlaier case 'x': 181184654Smlaier ftsoptions |= FTS_XDEV; 182184654Smlaier break; 183184654Smlaier case '?': 184184654Smlaier default: 185184654Smlaier usage(); 186184654Smlaier /* NOTREACHED */ 1871590Srgrimes } 18832097Sjkh 1891590Srgrimes argc -= optind; 1901590Srgrimes argv += optind; 1911590Srgrimes 1921590Srgrimes /* 1931590Srgrimes * XXX 1941590Srgrimes * Because of the way that fts(3) works, logical walks will not count 1951590Srgrimes * the blocks actually used by symbolic links. We rationalize this by 1961590Srgrimes * noting that users computing logical sizes are likely to do logical 1971590Srgrimes * copies, so not counting the links is correct. The real reason is 1981590Srgrimes * that we'd have to re-implement the kernel's symbolic link traversing 1991590Srgrimes * algorithm to get this right. If, for example, you have relative 2001590Srgrimes * symbolic links referencing other relative symbolic links, it gets 2011590Srgrimes * very nasty, very fast. The bottom line is that it's documented in 2021590Srgrimes * the man page, so it's a feature. 2031590Srgrimes */ 20432097Sjkh 20532097Sjkh if (Hflag + Lflag + Pflag > 1) 20632097Sjkh usage(); 20732097Sjkh 20832097Sjkh if (Hflag + Lflag + Pflag == 0) 20932097Sjkh Pflag = 1; /* -P (physical) is default */ 21032097Sjkh 2111590Srgrimes if (Hflag) 2121590Srgrimes ftsoptions |= FTS_COMFOLLOW; 21332097Sjkh 21432097Sjkh if (Lflag) 2151590Srgrimes ftsoptions |= FTS_LOGICAL; 2161590Srgrimes 21732097Sjkh if (Pflag) 21832097Sjkh ftsoptions |= FTS_PHYSICAL; 21932097Sjkh 220184733Smlaier if (!Aflag && (cblocksize % DEV_BSIZE) != 0) 221184733Smlaier cblocksize = howmany(cblocksize, DEV_BSIZE) * DEV_BSIZE; 222184733Smlaier 22332097Sjkh listall = 0; 22432097Sjkh 2251590Srgrimes if (aflag) { 22619120Sscrappy if (sflag || dflag) 2271590Srgrimes usage(); 22832097Sjkh listall = 1; 22919120Sscrappy } else if (sflag) { 23019120Sscrappy if (dflag) 23119120Sscrappy usage(); 23232097Sjkh depth = 0; 2331590Srgrimes } 2341590Srgrimes 2351590Srgrimes if (!*argv) { 2361590Srgrimes argv = save; 23787216Smarkm argv[0] = dot; 2381590Srgrimes argv[1] = NULL; 2391590Srgrimes } 2401590Srgrimes 241184733Smlaier if (blocksize == 0) 242184733Smlaier (void)getbsize(¬used, &blocksize); 2431590Srgrimes 244184733Smlaier if (!Aflag) { 245184733Smlaier cblocksize /= DEV_BSIZE; 246184733Smlaier blocksize /= DEV_BSIZE; 247184733Smlaier } 248184733Smlaier 24932097Sjkh rval = 0; 250128772Skientzle 2511590Srgrimes if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 25232097Sjkh err(1, "fts_open"); 2531590Srgrimes 25432097Sjkh while ((p = fts_read(fts)) != NULL) { 2551590Srgrimes switch (p->fts_info) { 256184654Smlaier case FTS_D: /* Ignore. */ 257184654Smlaier if (ignorep(p)) 258184654Smlaier fts_set(fts, p, FTS_SKIP); 259184654Smlaier break; 260184654Smlaier case FTS_DP: 261184654Smlaier if (ignorep(p)) 2621590Srgrimes break; 26378158Sroam 264184733Smlaier curblocks = Aflag ? 265184733Smlaier howmany(p->fts_statp->st_size, cblocksize) : 266184733Smlaier howmany(p->fts_statp->st_blocks, cblocksize); 267184654Smlaier p->fts_parent->fts_bignum += p->fts_bignum += 268184733Smlaier curblocks; 269128772Skientzle 270184654Smlaier if (p->fts_level <= depth) { 271184654Smlaier if (hflag) { 272184733Smlaier prthumanval(p->fts_bignum); 273184654Smlaier (void)printf("\t%s\n", p->fts_path); 274184654Smlaier } else { 275184654Smlaier (void)printf("%jd\t%s\n", 276184742Smlaier (intmax_t)howmany(p->fts_bignum * 277184742Smlaier cblocksize, blocksize), 278184742Smlaier p->fts_path); 27958601Scharnier } 280184654Smlaier } 281184654Smlaier break; 282184654Smlaier case FTS_DC: /* Ignore. */ 283184654Smlaier break; 284184654Smlaier case FTS_DNR: /* Warn, continue. */ 285184654Smlaier case FTS_ERR: 286184654Smlaier case FTS_NS: 287184654Smlaier warnx("%s: %s", p->fts_path, strerror(p->fts_errno)); 288184654Smlaier rval = 1; 289184654Smlaier break; 290184654Smlaier default: 291184654Smlaier if (ignorep(p)) 29232097Sjkh break; 293184654Smlaier 294184654Smlaier if (lflag == 0 && p->fts_statp->st_nlink > 1 && 295184654Smlaier linkchk(p)) 29632097Sjkh break; 29778158Sroam 298184733Smlaier curblocks = Aflag ? 299184733Smlaier howmany(p->fts_statp->st_size, cblocksize) : 300184733Smlaier howmany(p->fts_statp->st_blocks, cblocksize); 301184733Smlaier 302184654Smlaier if (listall || p->fts_level == 0) { 303184654Smlaier if (hflag) { 304184733Smlaier prthumanval(curblocks); 305184654Smlaier (void)printf("\t%s\n", p->fts_path); 306184654Smlaier } else { 307184654Smlaier (void)printf("%jd\t%s\n", 308184742Smlaier (intmax_t)howmany(curblocks * 309184742Smlaier cblocksize, blocksize), 310184742Smlaier p->fts_path); 31158601Scharnier } 312184654Smlaier } 31332097Sjkh 314184733Smlaier p->fts_parent->fts_bignum += curblocks; 3151590Srgrimes } 316139813Spjd savednumber = p->fts_parent->fts_bignum; 31732097Sjkh } 31832097Sjkh 3191590Srgrimes if (errno) 3201590Srgrimes err(1, "fts_read"); 32132097Sjkh 32258601Scharnier if (cflag) { 32356597Smharo if (hflag) { 324184733Smlaier prthumanval(savednumber); 325184654Smlaier (void)printf("\ttotal\n"); 32656597Smharo } else { 327184654Smlaier (void)printf("%jd\ttotal\n", (intmax_t)howmany( 328184733Smlaier savednumber * cblocksize, blocksize)); 32956597Smharo } 33058601Scharnier } 33132097Sjkh 33278158Sroam ignoreclean(); 33328891Swosch exit(rval); 3341590Srgrimes} 3351590Srgrimes 336128772Skientzlestatic int 337128772Skientzlelinkchk(FTSENT *p) 338128772Skientzle{ 339128772Skientzle struct links_entry { 340128806Skientzle struct links_entry *next; 341128806Skientzle struct links_entry *previous; 342128806Skientzle int links; 343128806Skientzle dev_t dev; 344128806Skientzle ino_t ino; 345128772Skientzle }; 346128806Skientzle static const size_t links_hash_initial_size = 8192; 347128806Skientzle static struct links_entry **buckets; 348128806Skientzle static struct links_entry *free_list; 349128806Skientzle static size_t number_buckets; 350128806Skientzle static unsigned long number_entries; 351128806Skientzle static char stop_allocating; 352128806Skientzle struct links_entry *le, **new_buckets; 353128806Skientzle struct stat *st; 354128806Skientzle size_t i, new_size; 355144840Sstefanf int hash; 35632097Sjkh 357128772Skientzle st = p->fts_statp; 35832097Sjkh 359128772Skientzle /* If necessary, initialize the hash table. */ 360128772Skientzle if (buckets == NULL) { 361128772Skientzle number_buckets = links_hash_initial_size; 362128772Skientzle buckets = malloc(number_buckets * sizeof(buckets[0])); 363128772Skientzle if (buckets == NULL) 364128834Skientzle errx(1, "No memory for hardlink detection"); 365128772Skientzle for (i = 0; i < number_buckets; i++) 366128772Skientzle buckets[i] = NULL; 367128772Skientzle } 3681590Srgrimes 369128772Skientzle /* If the hash table is getting too full, enlarge it. */ 370128772Skientzle if (number_entries > number_buckets * 10 && !stop_allocating) { 371128772Skientzle new_size = number_buckets * 2; 372128772Skientzle new_buckets = malloc(new_size * sizeof(struct links_entry *)); 373128772Skientzle 374128772Skientzle /* Try releasing the free list to see if that helps. */ 375128772Skientzle if (new_buckets == NULL && free_list != NULL) { 376128772Skientzle while (free_list != NULL) { 377128772Skientzle le = free_list; 378128772Skientzle free_list = le->next; 379128772Skientzle free(le); 380128772Skientzle } 381184654Smlaier new_buckets = malloc(new_size * 382184654Smlaier sizeof(new_buckets[0])); 383128772Skientzle } 384128772Skientzle 385128772Skientzle if (new_buckets == NULL) { 386128772Skientzle stop_allocating = 1; 387128834Skientzle warnx("No more memory for tracking hard links"); 388128772Skientzle } else { 389128772Skientzle memset(new_buckets, 0, 390128772Skientzle new_size * sizeof(struct links_entry *)); 391128772Skientzle for (i = 0; i < number_buckets; i++) { 392128772Skientzle while (buckets[i] != NULL) { 393128772Skientzle /* Remove entry from old bucket. */ 394128772Skientzle le = buckets[i]; 395128772Skientzle buckets[i] = le->next; 396128772Skientzle 397128772Skientzle /* Add entry to new bucket. */ 398128772Skientzle hash = (le->dev ^ le->ino) % new_size; 399128772Skientzle 400128772Skientzle if (new_buckets[hash] != NULL) 401128772Skientzle new_buckets[hash]->previous = 402128772Skientzle le; 403128772Skientzle le->next = new_buckets[hash]; 404128772Skientzle le->previous = NULL; 405128772Skientzle new_buckets[hash] = le; 406128772Skientzle } 407128772Skientzle } 408128772Skientzle free(buckets); 409128772Skientzle buckets = new_buckets; 410128772Skientzle number_buckets = new_size; 411128772Skientzle } 412128772Skientzle } 413128772Skientzle 414128772Skientzle /* Try to locate this entry in the hash table. */ 415128772Skientzle hash = ( st->st_dev ^ st->st_ino ) % number_buckets; 416128772Skientzle for (le = buckets[hash]; le != NULL; le = le->next) { 417128772Skientzle if (le->dev == st->st_dev && le->ino == st->st_ino) { 418128772Skientzle /* 419128772Skientzle * Save memory by releasing an entry when we've seen 420128772Skientzle * all of it's links. 421128772Skientzle */ 422128772Skientzle if (--le->links <= 0) { 423128772Skientzle if (le->previous != NULL) 424128772Skientzle le->previous->next = le->next; 425128772Skientzle if (le->next != NULL) 426128772Skientzle le->next->previous = le->previous; 427128772Skientzle if (buckets[hash] == le) 428128772Skientzle buckets[hash] = le->next; 429128772Skientzle number_entries--; 430128772Skientzle /* Recycle this node through the free list */ 431128772Skientzle if (stop_allocating) { 432128772Skientzle free(le); 433128772Skientzle } else { 434128772Skientzle le->next = free_list; 435128772Skientzle free_list = le; 436128772Skientzle } 437128772Skientzle } 438128772Skientzle return (1); 439128772Skientzle } 440128772Skientzle } 441128772Skientzle 442128772Skientzle if (stop_allocating) 443128772Skientzle return (0); 444128772Skientzle 445128772Skientzle /* Add this entry to the links cache. */ 446128772Skientzle if (free_list != NULL) { 447128772Skientzle /* Pull a node from the free list if we can. */ 448128772Skientzle le = free_list; 449128772Skientzle free_list = le->next; 450128772Skientzle } else 451128772Skientzle /* Malloc one if we have to. */ 452128772Skientzle le = malloc(sizeof(struct links_entry)); 453128772Skientzle if (le == NULL) { 454128772Skientzle stop_allocating = 1; 455128834Skientzle warnx("No more memory for tracking hard links"); 456128772Skientzle return (0); 457128772Skientzle } 458128772Skientzle le->dev = st->st_dev; 459128772Skientzle le->ino = st->st_ino; 460128772Skientzle le->links = st->st_nlink - 1; 461128772Skientzle number_entries++; 462128772Skientzle le->next = buckets[hash]; 463128772Skientzle le->previous = NULL; 464128772Skientzle if (buckets[hash] != NULL) 465128772Skientzle buckets[hash]->previous = le; 466128772Skientzle buckets[hash] = le; 4671590Srgrimes return (0); 4681590Srgrimes} 4691590Srgrimes 470184656Smlaierstatic void 471129678Spjdprthumanval(int64_t bytes) 47256597Smharo{ 473129678Spjd char buf[5]; 47456597Smharo 475184733Smlaier bytes *= cblocksize; 476184733Smlaier if (!Aflag) 477184733Smlaier bytes *= DEV_BSIZE; 47856597Smharo 479129678Spjd humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE, 480129678Spjd HN_B | HN_NOSPACE | HN_DECIMAL); 48156597Smharo 482129678Spjd (void)printf("%4s", buf); 48356597Smharo} 48456597Smharo 48527099Scharnierstatic void 486100822Sdwmaloneusage(void) 4871590Srgrimes{ 4881590Srgrimes (void)fprintf(stderr, 489184733Smlaier "usage: du [-A] [-H | -L | -P] [-a | -s | -d depth] [-c] " 490184733Smlaier "[-l] [-h | -k | -m | -B bsize] [-n] [-x] [-I mask] " 491184733Smlaier "[file ...]\n"); 49256597Smharo exit(EX_USAGE); 4931590Srgrimes} 49478158Sroam 495184656Smlaierstatic void 496100822Sdwmaloneignoreadd(const char *mask) 49778158Sroam{ 49878158Sroam struct ignentry *ign; 49978158Sroam 50078158Sroam ign = calloc(1, sizeof(*ign)); 50178158Sroam if (ign == NULL) 50278158Sroam errx(1, "cannot allocate memory"); 50378158Sroam ign->mask = strdup(mask); 50478158Sroam if (ign->mask == NULL) 50578158Sroam errx(1, "cannot allocate memory"); 50678158Sroam SLIST_INSERT_HEAD(&ignores, ign, next); 50778158Sroam} 50878158Sroam 509184656Smlaierstatic void 510100822Sdwmaloneignoreclean(void) 51178158Sroam{ 51278158Sroam struct ignentry *ign; 51378158Sroam 51478158Sroam while (!SLIST_EMPTY(&ignores)) { 51578158Sroam ign = SLIST_FIRST(&ignores); 51678158Sroam SLIST_REMOVE_HEAD(&ignores, next); 51778158Sroam free(ign->mask); 51878158Sroam free(ign); 51978158Sroam } 52078158Sroam} 52178158Sroam 522184656Smlaierstatic int 523100822Sdwmaloneignorep(FTSENT *ent) 52478158Sroam{ 52578158Sroam struct ignentry *ign; 52678158Sroam 527158339Smaxim if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP)) 528158339Smaxim return 1; 52978158Sroam SLIST_FOREACH(ign, &ignores, next) 53078158Sroam if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH) 53178158Sroam return 1; 53278158Sroam return 0; 53378158Sroam} 534