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