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