du.c revision 184733
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 38static 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 45static 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: head/usr.bin/du/du.c 184733 2008-11-06 16:30:38Z mlaier $"); 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 68SLIST_HEAD(ignhead, ignentry) ignores; 69struct ignentry { 70 char *mask; 71 SLIST_ENTRY(ignentry) next; 72}; 73 74static int linkchk(FTSENT *); 75static void usage(void); 76static void prthumanval(int64_t); 77static void ignoreadd(const char *); 78static void ignoreclean(void); 79static int ignorep(FTSENT *); 80 81static int nodumpflag = 0; 82static int Aflag; 83static long blocksize, cblocksize; 84 85int 86main(int argc, char *argv[]) 87{ 88 FTS *fts; 89 FTSENT *p; 90 off_t savednumber, curblocks; 91 int ftsoptions; 92 int listall; 93 int depth; 94 int Hflag, Lflag, Pflag, aflag, sflag, dflag, cflag; 95 int hflag, lflag, ch, notused, rval; 96 char **save; 97 static char dot[] = "."; 98 99 setlocale(LC_ALL, ""); 100 101 Hflag = Lflag = Pflag = aflag = sflag = dflag = cflag = hflag = 102 lflag = Aflag = 0; 103 104 save = argv; 105 ftsoptions = 0; 106 savednumber = 0; 107 cblocksize = DEV_BSIZE; 108 blocksize = 0; 109 depth = INT_MAX; 110 SLIST_INIT(&ignores); 111 112 while ((ch = getopt(argc, argv, "AB:HI:LPasd:chklmnrx")) != -1) 113 switch (ch) { 114 case 'A': 115 Aflag = 1; 116 break; 117 case 'B': 118 errno = 0; 119 cblocksize = atoi(optarg); 120 if (errno == ERANGE || cblocksize <= 0) { 121 warnx("invalid argument to option B: %s", 122 optarg); 123 usage(); 124 } 125 break; 126 case 'H': 127 Hflag = 1; 128 break; 129 case 'I': 130 ignoreadd(optarg); 131 break; 132 case 'L': 133 if (Pflag) 134 usage(); 135 Lflag = 1; 136 break; 137 case 'P': 138 if (Lflag) 139 usage(); 140 Pflag = 1; 141 break; 142 case 'a': 143 aflag = 1; 144 break; 145 case 's': 146 sflag = 1; 147 break; 148 case 'd': 149 dflag = 1; 150 errno = 0; 151 depth = atoi(optarg); 152 if (errno == ERANGE || depth < 0) { 153 warnx("invalid argument to option d: %s", 154 optarg); 155 usage(); 156 } 157 break; 158 case 'c': 159 cflag = 1; 160 break; 161 case 'h': 162 hflag = 1; 163 break; 164 case 'k': 165 hflag = 0; 166 blocksize = 1024; 167 break; 168 case 'l': 169 lflag = 1; 170 break; 171 case 'm': 172 hflag = 0; 173 blocksize = 1048576; 174 break; 175 case 'n': 176 nodumpflag = 1; 177 break; 178 case 'r': /* Compatibility. */ 179 break; 180 case 'x': 181 ftsoptions |= FTS_XDEV; 182 break; 183 case '?': 184 default: 185 usage(); 186 /* NOTREACHED */ 187 } 188 189 argc -= optind; 190 argv += optind; 191 192 /* 193 * XXX 194 * Because of the way that fts(3) works, logical walks will not count 195 * the blocks actually used by symbolic links. We rationalize this by 196 * noting that users computing logical sizes are likely to do logical 197 * copies, so not counting the links is correct. The real reason is 198 * that we'd have to re-implement the kernel's symbolic link traversing 199 * algorithm to get this right. If, for example, you have relative 200 * symbolic links referencing other relative symbolic links, it gets 201 * very nasty, very fast. The bottom line is that it's documented in 202 * the man page, so it's a feature. 203 */ 204 205 if (Hflag + Lflag + Pflag > 1) 206 usage(); 207 208 if (Hflag + Lflag + Pflag == 0) 209 Pflag = 1; /* -P (physical) is default */ 210 211 if (Hflag) 212 ftsoptions |= FTS_COMFOLLOW; 213 214 if (Lflag) 215 ftsoptions |= FTS_LOGICAL; 216 217 if (Pflag) 218 ftsoptions |= FTS_PHYSICAL; 219 220 if (!Aflag && (cblocksize % DEV_BSIZE) != 0) 221 cblocksize = howmany(cblocksize, DEV_BSIZE) * DEV_BSIZE; 222 223 listall = 0; 224 225 if (aflag) { 226 if (sflag || dflag) 227 usage(); 228 listall = 1; 229 } else if (sflag) { 230 if (dflag) 231 usage(); 232 depth = 0; 233 } 234 235 if (!*argv) { 236 argv = save; 237 argv[0] = dot; 238 argv[1] = NULL; 239 } 240 241 if (blocksize == 0) 242 (void)getbsize(¬used, &blocksize); 243 244 if (!Aflag) { 245 cblocksize /= DEV_BSIZE; 246 blocksize /= DEV_BSIZE; 247 } 248 249 rval = 0; 250 251 if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 252 err(1, "fts_open"); 253 254 while ((p = fts_read(fts)) != NULL) { 255 switch (p->fts_info) { 256 case FTS_D: /* Ignore. */ 257 if (ignorep(p)) 258 fts_set(fts, p, FTS_SKIP); 259 break; 260 case FTS_DP: 261 if (ignorep(p)) 262 break; 263 264 curblocks = Aflag ? 265 howmany(p->fts_statp->st_size, cblocksize) : 266 howmany(p->fts_statp->st_blocks, cblocksize); 267 p->fts_parent->fts_bignum += p->fts_bignum += 268 curblocks; 269 270 if (p->fts_level <= depth) { 271 if (hflag) { 272 prthumanval(p->fts_bignum); 273 (void)printf("\t%s\n", p->fts_path); 274 } else { 275 (void)printf("%jd\t%s\n", 276 howmany(p->fts_bignum * cblocksize, 277 blocksize), p->fts_path); 278 } 279 } 280 break; 281 case FTS_DC: /* Ignore. */ 282 break; 283 case FTS_DNR: /* Warn, continue. */ 284 case FTS_ERR: 285 case FTS_NS: 286 warnx("%s: %s", p->fts_path, strerror(p->fts_errno)); 287 rval = 1; 288 break; 289 default: 290 if (ignorep(p)) 291 break; 292 293 if (lflag == 0 && p->fts_statp->st_nlink > 1 && 294 linkchk(p)) 295 break; 296 297 curblocks = Aflag ? 298 howmany(p->fts_statp->st_size, cblocksize) : 299 howmany(p->fts_statp->st_blocks, cblocksize); 300 301 if (listall || p->fts_level == 0) { 302 if (hflag) { 303 prthumanval(curblocks); 304 (void)printf("\t%s\n", p->fts_path); 305 } else { 306 (void)printf("%jd\t%s\n", 307 howmany(curblocks * cblocksize, 308 blocksize), p->fts_path); 309 } 310 } 311 312 p->fts_parent->fts_bignum += curblocks; 313 } 314 savednumber = p->fts_parent->fts_bignum; 315 } 316 317 if (errno) 318 err(1, "fts_read"); 319 320 if (cflag) { 321 if (hflag) { 322 prthumanval(savednumber); 323 (void)printf("\ttotal\n"); 324 } else { 325 (void)printf("%jd\ttotal\n", (intmax_t)howmany( 326 savednumber * cblocksize, blocksize)); 327 } 328 } 329 330 ignoreclean(); 331 exit(rval); 332} 333 334static int 335linkchk(FTSENT *p) 336{ 337 struct links_entry { 338 struct links_entry *next; 339 struct links_entry *previous; 340 int links; 341 dev_t dev; 342 ino_t ino; 343 }; 344 static const size_t links_hash_initial_size = 8192; 345 static struct links_entry **buckets; 346 static struct links_entry *free_list; 347 static size_t number_buckets; 348 static unsigned long number_entries; 349 static char stop_allocating; 350 struct links_entry *le, **new_buckets; 351 struct stat *st; 352 size_t i, new_size; 353 int hash; 354 355 st = p->fts_statp; 356 357 /* If necessary, initialize the hash table. */ 358 if (buckets == NULL) { 359 number_buckets = links_hash_initial_size; 360 buckets = malloc(number_buckets * sizeof(buckets[0])); 361 if (buckets == NULL) 362 errx(1, "No memory for hardlink detection"); 363 for (i = 0; i < number_buckets; i++) 364 buckets[i] = NULL; 365 } 366 367 /* If the hash table is getting too full, enlarge it. */ 368 if (number_entries > number_buckets * 10 && !stop_allocating) { 369 new_size = number_buckets * 2; 370 new_buckets = malloc(new_size * sizeof(struct links_entry *)); 371 372 /* Try releasing the free list to see if that helps. */ 373 if (new_buckets == NULL && free_list != NULL) { 374 while (free_list != NULL) { 375 le = free_list; 376 free_list = le->next; 377 free(le); 378 } 379 new_buckets = malloc(new_size * 380 sizeof(new_buckets[0])); 381 } 382 383 if (new_buckets == NULL) { 384 stop_allocating = 1; 385 warnx("No more memory for tracking hard links"); 386 } else { 387 memset(new_buckets, 0, 388 new_size * sizeof(struct links_entry *)); 389 for (i = 0; i < number_buckets; i++) { 390 while (buckets[i] != NULL) { 391 /* Remove entry from old bucket. */ 392 le = buckets[i]; 393 buckets[i] = le->next; 394 395 /* Add entry to new bucket. */ 396 hash = (le->dev ^ le->ino) % new_size; 397 398 if (new_buckets[hash] != NULL) 399 new_buckets[hash]->previous = 400 le; 401 le->next = new_buckets[hash]; 402 le->previous = NULL; 403 new_buckets[hash] = le; 404 } 405 } 406 free(buckets); 407 buckets = new_buckets; 408 number_buckets = new_size; 409 } 410 } 411 412 /* Try to locate this entry in the hash table. */ 413 hash = ( st->st_dev ^ st->st_ino ) % number_buckets; 414 for (le = buckets[hash]; le != NULL; le = le->next) { 415 if (le->dev == st->st_dev && le->ino == st->st_ino) { 416 /* 417 * Save memory by releasing an entry when we've seen 418 * all of it's links. 419 */ 420 if (--le->links <= 0) { 421 if (le->previous != NULL) 422 le->previous->next = le->next; 423 if (le->next != NULL) 424 le->next->previous = le->previous; 425 if (buckets[hash] == le) 426 buckets[hash] = le->next; 427 number_entries--; 428 /* Recycle this node through the free list */ 429 if (stop_allocating) { 430 free(le); 431 } else { 432 le->next = free_list; 433 free_list = le; 434 } 435 } 436 return (1); 437 } 438 } 439 440 if (stop_allocating) 441 return (0); 442 443 /* Add this entry to the links cache. */ 444 if (free_list != NULL) { 445 /* Pull a node from the free list if we can. */ 446 le = free_list; 447 free_list = le->next; 448 } else 449 /* Malloc one if we have to. */ 450 le = malloc(sizeof(struct links_entry)); 451 if (le == NULL) { 452 stop_allocating = 1; 453 warnx("No more memory for tracking hard links"); 454 return (0); 455 } 456 le->dev = st->st_dev; 457 le->ino = st->st_ino; 458 le->links = st->st_nlink - 1; 459 number_entries++; 460 le->next = buckets[hash]; 461 le->previous = NULL; 462 if (buckets[hash] != NULL) 463 buckets[hash]->previous = le; 464 buckets[hash] = le; 465 return (0); 466} 467 468static void 469prthumanval(int64_t bytes) 470{ 471 char buf[5]; 472 473 bytes *= cblocksize; 474 if (!Aflag) 475 bytes *= DEV_BSIZE; 476 477 humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE, 478 HN_B | HN_NOSPACE | HN_DECIMAL); 479 480 (void)printf("%4s", buf); 481} 482 483static void 484usage(void) 485{ 486 (void)fprintf(stderr, 487 "usage: du [-A] [-H | -L | -P] [-a | -s | -d depth] [-c] " 488 "[-l] [-h | -k | -m | -B bsize] [-n] [-x] [-I mask] " 489 "[file ...]\n"); 490 exit(EX_USAGE); 491} 492 493static void 494ignoreadd(const char *mask) 495{ 496 struct ignentry *ign; 497 498 ign = calloc(1, sizeof(*ign)); 499 if (ign == NULL) 500 errx(1, "cannot allocate memory"); 501 ign->mask = strdup(mask); 502 if (ign->mask == NULL) 503 errx(1, "cannot allocate memory"); 504 SLIST_INSERT_HEAD(&ignores, ign, next); 505} 506 507static void 508ignoreclean(void) 509{ 510 struct ignentry *ign; 511 512 while (!SLIST_EMPTY(&ignores)) { 513 ign = SLIST_FIRST(&ignores); 514 SLIST_REMOVE_HEAD(&ignores, next); 515 free(ign->mask); 516 free(ign); 517 } 518} 519 520static int 521ignorep(FTSENT *ent) 522{ 523 struct ignentry *ign; 524 525 if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP)) 526 return 1; 527 SLIST_FOREACH(ign, &ignores, next) 528 if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH) 529 return 1; 530 return 0; 531} 532