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 fts_close(fts); 287 288 if (cflag) { 289 if (hflag) { 290 (void) prthumanval(howmany(savednumber, blocksize)); 291 (void) printf("\ttotal\n"); 292 } else { 293 (void) printf("%lld\ttotal\n", howmany(savednumber, blocksize)); 294 } 295 } 296 297 ignoreclean(); 298 exit(rval); 299 } 300 301 static int 302 linkchk(FTSENT *p) 303 { 304 struct links_entry { 305 struct links_entry *next; 306 struct links_entry *previous; 307 int links; 308 dev_t dev; 309 ino_t ino; 310 }; 311 312 static const size_t links_hash_initial_size = 8192; 313 static struct links_entry **buckets; 314 static struct links_entry *free_list; 315 static size_t number_buckets; 316 static unsigned long number_entries; 317 static char stop_allocating; 318 struct links_entry *le, **new_buckets; 319 struct stat *st; 320 size_t i, new_size; 321 int hash; 322 323 st = p->fts_statp; 324 325 /* If necessary, initialize the hash table. */ 326 if (buckets == NULL) { 327 number_buckets = links_hash_initial_size; 328 buckets = malloc(number_buckets * sizeof(buckets[0])); 329 if (buckets == NULL) 330 errx(1, "No memory for hardlink detection"); 331 for (i = 0; i < number_buckets; i++) 332 buckets[i] = NULL; 333 } 334 335 /* If the hash table is getting too full, enlarge it. */ 336 if (number_entries > number_buckets * 10 && !stop_allocating) { 337 new_size = number_buckets * 2; 338 new_buckets = malloc(new_size * sizeof(struct links_entry *)); 339 340 /* Try releasing the free list to see if that helps. */ 341 if (new_buckets == NULL && free_list != NULL) { 342 while (free_list != NULL) { 343 le = free_list; 344 free_list = le->next; 345 free(le); 346 } 347 new_buckets = malloc(new_size * sizeof(new_buckets[0])); 348 } 349 350 if (new_buckets == NULL) { 351 stop_allocating = 1; 352 warnx("No more memory for tracking hard links"); 353 } else { 354 memset(new_buckets, 0, new_size * sizeof(struct links_entry *)); 355 for (i = 0; i < number_buckets; i++) { 356 while (buckets[i] != NULL) { 357 /* Remove entry from old bucket. */ 358 le = buckets[i]; 359 buckets[i] = le->next; 360 361 /* Add entry to new bucket. */ 362 hash = (le->dev ^ le->ino) % new_size; 363 364 if (new_buckets[hash] != NULL) 365 new_buckets[hash]->previous = le; 366 le->next = new_buckets[hash]; 367 le->previous = NULL; 368 new_buckets[hash] = le; 369 } 370 } 371 free(buckets); 372 buckets = new_buckets; 373 number_buckets = new_size; 374 } 375 } 376 377 /* Try to locate this entry in the hash table. */ 378 hash = ( st->st_dev ^ st->st_ino ) % number_buckets; 379 for (le = buckets[hash]; le != NULL; le = le->next) { 380 if (le->dev == st->st_dev && le->ino == st->st_ino) { 381 /* 382 * Save memory by releasing an entry when we've seen 383 * all of it's links. 384 */ 385 if (--le->links <= 0) { 386 if (le->previous != NULL) 387 le->previous->next = le->next; 388 if (le->next != NULL) 389 le->next->previous = le->previous; 390 if (buckets[hash] == le) 391 buckets[hash] = le->next; 392 number_entries--; 393 /* Recycle this node through the free list */ 394 if (stop_allocating) { 395 free(le); 396 } else { 397 le->next = free_list; 398 free_list = le; 399 } 400 } 401 return (1); 402 } 403 } 404 405 if (stop_allocating) 406 return (0); 407 408 /* Add this entry to the links cache. */ 409 if (free_list != NULL) { 410 /* Pull a node from the free list if we can. */ 411 le = free_list; 412 free_list = le->next; 413 } else 414 /* Malloc one if we have to. */ 415 le = malloc(sizeof(struct links_entry)); 416 if (le == NULL) { 417 stop_allocating = 1; 418 warnx("No more memory for tracking hard links"); 419 return (0); 420 } 421 le->dev = st->st_dev; 422 le->ino = st->st_ino; 423 le->links = st->st_nlink - 1; 424 number_entries++; 425 le->next = buckets[hash]; 426 le->previous = NULL; 427 if (buckets[hash] != NULL) 428 buckets[hash]->previous = le; 429 buckets[hash] = le; 430 return (0); 431 } 432 433 void 434 prthumanval(int64_t bytes) 435 { 436 char buf[sizeof("999M")]; 437 438 bytes *= DEV_BSIZE; 439 440 humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE, 441 HN_B | HN_NOSPACE | HN_DECIMAL); 442 443 (void) printf("%4s", buf); 444 } 445 446 static void 447 usage(void) 448 { 449 (void)fprintf(stderr, 450 "usage: du [-H | -L | -P] [-a | -s | -d depth] [-c] [-h | -k] [-x] [-I mask] [file ...]\n"); 451 exit(EX_USAGE); 452 } 453 454 void 455 ignoreadd(const char *mask) 456 { 457 struct ignentry *ign; 458 459 ign = calloc(1, sizeof(*ign)); 460 if (ign == NULL) 461 errx(1, "cannot allocate memory"); 462 ign->mask = strdup(mask); 463 if (ign->mask == NULL) 464 errx(1, "cannot allocate memory"); 465 SLIST_INSERT_HEAD(&ignores, ign, next); 466 } 467 468 void 469 ignoreclean(void) 470 { 471 struct ignentry *ign; 472 473 while (!SLIST_EMPTY(&ignores)) { 474 ign = SLIST_FIRST(&ignores); 475 SLIST_REMOVE_HEAD(&ignores, next); 476 free(ign->mask); 477 free(ign); 478 } 479 } 480 481 int 482 ignorep(FTSENT *ent) 483 { 484 struct ignentry *ign; 485 486 SLIST_FOREACH(ign, &ignores, next) 487 if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH) 488 return 1; 489 return 0; 490 } 491