xref: /freebsd/usr.bin/du/du.c (revision 6472ac3d8a86336899b6cfb789a4cd9897e3fab5)
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  * 4. Neither the name of the University nor the names of its contributors
17  *    may be used to endorse or promote products derived from this software
18  *    without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30  * SUCH DAMAGE.
31  */
32 
33 #ifndef lint
34 static const char copyright[] =
35 "@(#) Copyright (c) 1989, 1993, 1994\n\
36 	The Regents of the University of California.  All rights reserved.\n";
37 #endif /* not lint */
38 
39 #ifndef lint
40 #if 0
41 static const char sccsid[] = "@(#)du.c	8.5 (Berkeley) 5/4/95";
42 #endif
43 #endif /* not lint */
44 #include <sys/cdefs.h>
45 __FBSDID("$FreeBSD$");
46 
47 #include <sys/param.h>
48 #include <sys/queue.h>
49 #include <sys/stat.h>
50 
51 #include <err.h>
52 #include <errno.h>
53 #include <fnmatch.h>
54 #include <fts.h>
55 #include <libutil.h>
56 #include <locale.h>
57 #include <stdint.h>
58 #include <stdio.h>
59 #include <stdlib.h>
60 #include <string.h>
61 #include <sysexits.h>
62 #include <unistd.h>
63 
64 static SLIST_HEAD(ignhead, ignentry) ignores;
65 struct ignentry {
66 	char			*mask;
67 	SLIST_ENTRY(ignentry)	next;
68 };
69 
70 static int	linkchk(FTSENT *);
71 static void	usage(void);
72 static void	prthumanval(int64_t);
73 static void	ignoreadd(const char *);
74 static void	ignoreclean(void);
75 static int	ignorep(FTSENT *);
76 static void	siginfo(int __unused);
77 
78 static int	nodumpflag = 0;
79 static int	Aflag;
80 static long	blocksize, cblocksize;
81 static volatile sig_atomic_t info;
82 
83 int
84 main(int argc, char *argv[])
85 {
86 	FTS		*fts;
87 	FTSENT		*p;
88 	off_t		savednumber, curblocks;
89 	off_t		threshold, threshold_sign;
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 = Aflag = 0;
102 
103 	save = argv;
104 	ftsoptions = 0;
105 	savednumber = 0;
106 	threshold = 0;
107 	threshold_sign = 1;
108 	cblocksize = DEV_BSIZE;
109 	blocksize = 0;
110 	depth = INT_MAX;
111 	SLIST_INIT(&ignores);
112 
113 	while ((ch = getopt(argc, argv, "AB:HI:LPasd:chklmnrt:x")) != -1)
114 		switch (ch) {
115 		case 'A':
116 			Aflag = 1;
117 			break;
118 		case 'B':
119 			errno = 0;
120 			cblocksize = atoi(optarg);
121 			if (errno == ERANGE || cblocksize <= 0) {
122 				warnx("invalid argument to option B: %s",
123 				    optarg);
124 				usage();
125 			}
126 			break;
127 		case 'H':
128 			Hflag = 1;
129 			break;
130 		case 'I':
131 			ignoreadd(optarg);
132 			break;
133 		case 'L':
134 			if (Pflag)
135 				usage();
136 			Lflag = 1;
137 			break;
138 		case 'P':
139 			if (Lflag)
140 				usage();
141 			Pflag = 1;
142 			break;
143 		case 'a':
144 			aflag = 1;
145 			break;
146 		case 's':
147 			sflag = 1;
148 			break;
149 		case 'd':
150 			dflag = 1;
151 			errno = 0;
152 			depth = atoi(optarg);
153 			if (errno == ERANGE || depth < 0) {
154 				warnx("invalid argument to option d: %s",
155 				    optarg);
156 				usage();
157 			}
158 			break;
159 		case 'c':
160 			cflag = 1;
161 			break;
162 		case 'h':
163 			hflag = 1;
164 			break;
165 		case 'k':
166 			hflag = 0;
167 			blocksize = 1024;
168 			break;
169 		case 'l':
170 			lflag = 1;
171 			break;
172 		case 'm':
173 			hflag = 0;
174 			blocksize = 1048576;
175 			break;
176 		case 'n':
177 			nodumpflag = 1;
178 			break;
179 		case 'r':		 /* Compatibility. */
180 			break;
181 		case 't' :
182 			if (expand_number(optarg, &threshold) != 0 ||
183 			    threshold == 0) {
184 				warnx("invalid threshold: %s", optarg);
185 				usage();
186 			} else if (threshold < 0)
187 				threshold_sign = -1;
188 			break;
189 		case 'x':
190 			ftsoptions |= FTS_XDEV;
191 			break;
192 		case '?':
193 		default:
194 			usage();
195 			/* NOTREACHED */
196 		}
197 
198 	argc -= optind;
199 	argv += optind;
200 
201 	/*
202 	 * XXX
203 	 * Because of the way that fts(3) works, logical walks will not count
204 	 * the blocks actually used by symbolic links.  We rationalize this by
205 	 * noting that users computing logical sizes are likely to do logical
206 	 * copies, so not counting the links is correct.  The real reason is
207 	 * that we'd have to re-implement the kernel's symbolic link traversing
208 	 * algorithm to get this right.  If, for example, you have relative
209 	 * symbolic links referencing other relative symbolic links, it gets
210 	 * very nasty, very fast.  The bottom line is that it's documented in
211 	 * the man page, so it's a feature.
212 	 */
213 
214 	if (Hflag + Lflag + Pflag > 1)
215 		usage();
216 
217 	if (Hflag + Lflag + Pflag == 0)
218 		Pflag = 1;			/* -P (physical) is default */
219 
220 	if (Hflag)
221 		ftsoptions |= FTS_COMFOLLOW;
222 
223 	if (Lflag)
224 		ftsoptions |= FTS_LOGICAL;
225 
226 	if (Pflag)
227 		ftsoptions |= FTS_PHYSICAL;
228 
229 	if (!Aflag && (cblocksize % DEV_BSIZE) != 0)
230 		cblocksize = howmany(cblocksize, DEV_BSIZE) * DEV_BSIZE;
231 
232 	listall = 0;
233 
234 	if (aflag) {
235 		if (sflag || dflag)
236 			usage();
237 		listall = 1;
238 	} else if (sflag) {
239 		if (dflag)
240 			usage();
241 		depth = 0;
242 	}
243 
244 	if (!*argv) {
245 		argv = save;
246 		argv[0] = dot;
247 		argv[1] = NULL;
248 	}
249 
250 	if (blocksize == 0)
251 		(void)getbsize(&notused, &blocksize);
252 
253 	if (!Aflag) {
254 		cblocksize /= DEV_BSIZE;
255 		blocksize /= DEV_BSIZE;
256 	}
257 
258 	if (threshold != 0)
259 		threshold = howmany(threshold / DEV_BSIZE * cblocksize,
260 		    blocksize);
261 
262 	rval = 0;
263 
264 	(void)signal(SIGINFO, siginfo);
265 
266 	if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL)
267 		err(1, "fts_open");
268 
269 	while ((p = fts_read(fts)) != NULL) {
270 		switch (p->fts_info) {
271 		case FTS_D:			/* Ignore. */
272 			if (ignorep(p))
273 				fts_set(fts, p, FTS_SKIP);
274 			break;
275 		case FTS_DP:
276 			if (ignorep(p))
277 				break;
278 
279 			curblocks = Aflag ?
280 			    howmany(p->fts_statp->st_size, cblocksize) :
281 			    howmany(p->fts_statp->st_blocks, cblocksize);
282 			p->fts_parent->fts_bignum += p->fts_bignum +=
283 			    curblocks;
284 
285 			if (p->fts_level <= depth && threshold <=
286 			    threshold_sign * howmany(p->fts_bignum *
287 			    cblocksize, blocksize)) {
288 				if (hflag) {
289 					prthumanval(p->fts_bignum);
290 					(void)printf("\t%s\n", p->fts_path);
291 				} else {
292 					(void)printf("%jd\t%s\n",
293 					    (intmax_t)howmany(p->fts_bignum *
294 					    cblocksize, blocksize),
295 					    p->fts_path);
296 				}
297 			}
298 			if (info) {
299 				info = 0;
300 				(void)printf("\t%s\n", p->fts_path);
301 			}
302 			break;
303 		case FTS_DC:			/* Ignore. */
304 			break;
305 		case FTS_DNR:			/* Warn, continue. */
306 		case FTS_ERR:
307 		case FTS_NS:
308 			warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
309 			rval = 1;
310 			break;
311 		default:
312 			if (ignorep(p))
313 				break;
314 
315 			if (lflag == 0 && p->fts_statp->st_nlink > 1 &&
316 			    linkchk(p))
317 				break;
318 
319 			curblocks = Aflag ?
320 			    howmany(p->fts_statp->st_size, cblocksize) :
321 			    howmany(p->fts_statp->st_blocks, cblocksize);
322 
323 			if (listall || p->fts_level == 0) {
324 				if (hflag) {
325 					prthumanval(curblocks);
326 					(void)printf("\t%s\n", p->fts_path);
327 				} else {
328 					(void)printf("%jd\t%s\n",
329 					    (intmax_t)howmany(curblocks *
330 					    cblocksize, blocksize),
331 					    p->fts_path);
332 				}
333 			}
334 
335 			p->fts_parent->fts_bignum += curblocks;
336 		}
337 		savednumber = p->fts_parent->fts_bignum;
338 	}
339 
340 	if (errno)
341 		err(1, "fts_read");
342 
343 	if (cflag) {
344 		if (hflag) {
345 			prthumanval(savednumber);
346 			(void)printf("\ttotal\n");
347 		} else {
348 			(void)printf("%jd\ttotal\n", (intmax_t)howmany(
349 			    savednumber * cblocksize, blocksize));
350 		}
351 	}
352 
353 	ignoreclean();
354 	exit(rval);
355 }
356 
357 static int
358 linkchk(FTSENT *p)
359 {
360 	struct links_entry {
361 		struct links_entry *next;
362 		struct links_entry *previous;
363 		int	 links;
364 		dev_t	 dev;
365 		ino_t	 ino;
366 	};
367 	static const size_t links_hash_initial_size = 8192;
368 	static struct links_entry **buckets;
369 	static struct links_entry *free_list;
370 	static size_t number_buckets;
371 	static unsigned long number_entries;
372 	static char stop_allocating;
373 	struct links_entry *le, **new_buckets;
374 	struct stat *st;
375 	size_t i, new_size;
376 	int hash;
377 
378 	st = p->fts_statp;
379 
380 	/* If necessary, initialize the hash table. */
381 	if (buckets == NULL) {
382 		number_buckets = links_hash_initial_size;
383 		buckets = malloc(number_buckets * sizeof(buckets[0]));
384 		if (buckets == NULL)
385 			errx(1, "No memory for hardlink detection");
386 		for (i = 0; i < number_buckets; i++)
387 			buckets[i] = NULL;
388 	}
389 
390 	/* If the hash table is getting too full, enlarge it. */
391 	if (number_entries > number_buckets * 10 && !stop_allocating) {
392 		new_size = number_buckets * 2;
393 		new_buckets = malloc(new_size * sizeof(struct links_entry *));
394 
395 		/* Try releasing the free list to see if that helps. */
396 		if (new_buckets == NULL && free_list != NULL) {
397 			while (free_list != NULL) {
398 				le = free_list;
399 				free_list = le->next;
400 				free(le);
401 			}
402 			new_buckets = malloc(new_size *
403 			    sizeof(new_buckets[0]));
404 		}
405 
406 		if (new_buckets == NULL) {
407 			stop_allocating = 1;
408 			warnx("No more memory for tracking hard links");
409 		} else {
410 			memset(new_buckets, 0,
411 			    new_size * sizeof(struct links_entry *));
412 			for (i = 0; i < number_buckets; i++) {
413 				while (buckets[i] != NULL) {
414 					/* Remove entry from old bucket. */
415 					le = buckets[i];
416 					buckets[i] = le->next;
417 
418 					/* Add entry to new bucket. */
419 					hash = (le->dev ^ le->ino) % new_size;
420 
421 					if (new_buckets[hash] != NULL)
422 						new_buckets[hash]->previous =
423 						    le;
424 					le->next = new_buckets[hash];
425 					le->previous = NULL;
426 					new_buckets[hash] = le;
427 				}
428 			}
429 			free(buckets);
430 			buckets = new_buckets;
431 			number_buckets = new_size;
432 		}
433 	}
434 
435 	/* Try to locate this entry in the hash table. */
436 	hash = ( st->st_dev ^ st->st_ino ) % number_buckets;
437 	for (le = buckets[hash]; le != NULL; le = le->next) {
438 		if (le->dev == st->st_dev && le->ino == st->st_ino) {
439 			/*
440 			 * Save memory by releasing an entry when we've seen
441 			 * all of it's links.
442 			 */
443 			if (--le->links <= 0) {
444 				if (le->previous != NULL)
445 					le->previous->next = le->next;
446 				if (le->next != NULL)
447 					le->next->previous = le->previous;
448 				if (buckets[hash] == le)
449 					buckets[hash] = le->next;
450 				number_entries--;
451 				/* Recycle this node through the free list */
452 				if (stop_allocating) {
453 					free(le);
454 				} else {
455 					le->next = free_list;
456 					free_list = le;
457 				}
458 			}
459 			return (1);
460 		}
461 	}
462 
463 	if (stop_allocating)
464 		return (0);
465 
466 	/* Add this entry to the links cache. */
467 	if (free_list != NULL) {
468 		/* Pull a node from the free list if we can. */
469 		le = free_list;
470 		free_list = le->next;
471 	} else
472 		/* Malloc one if we have to. */
473 		le = malloc(sizeof(struct links_entry));
474 	if (le == NULL) {
475 		stop_allocating = 1;
476 		warnx("No more memory for tracking hard links");
477 		return (0);
478 	}
479 	le->dev = st->st_dev;
480 	le->ino = st->st_ino;
481 	le->links = st->st_nlink - 1;
482 	number_entries++;
483 	le->next = buckets[hash];
484 	le->previous = NULL;
485 	if (buckets[hash] != NULL)
486 		buckets[hash]->previous = le;
487 	buckets[hash] = le;
488 	return (0);
489 }
490 
491 static void
492 prthumanval(int64_t bytes)
493 {
494 	char buf[5];
495 
496 	bytes *= cblocksize;
497 	if (!Aflag)
498 		bytes *= DEV_BSIZE;
499 
500 	humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE,
501 	    HN_B | HN_NOSPACE | HN_DECIMAL);
502 
503 	(void)printf("%4s", buf);
504 }
505 
506 static void
507 usage(void)
508 {
509 	(void)fprintf(stderr,
510 		"usage: du [-A] [-H | -L | -P] [-a | -s | -d depth] [-c] "
511 		"[-l] [-h | -k | -m | -B bsize] [-n] [-x] [-I mask] "
512 		"[file ...]\n");
513 	exit(EX_USAGE);
514 }
515 
516 static void
517 ignoreadd(const char *mask)
518 {
519 	struct ignentry *ign;
520 
521 	ign = calloc(1, sizeof(*ign));
522 	if (ign == NULL)
523 		errx(1, "cannot allocate memory");
524 	ign->mask = strdup(mask);
525 	if (ign->mask == NULL)
526 		errx(1, "cannot allocate memory");
527 	SLIST_INSERT_HEAD(&ignores, ign, next);
528 }
529 
530 static void
531 ignoreclean(void)
532 {
533 	struct ignentry *ign;
534 
535 	while (!SLIST_EMPTY(&ignores)) {
536 		ign = SLIST_FIRST(&ignores);
537 		SLIST_REMOVE_HEAD(&ignores, next);
538 		free(ign->mask);
539 		free(ign);
540 	}
541 }
542 
543 static int
544 ignorep(FTSENT *ent)
545 {
546 	struct ignentry *ign;
547 
548 	if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP))
549 		return 1;
550 	SLIST_FOREACH(ign, &ignores, next)
551 		if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH)
552 			return 1;
553 	return 0;
554 }
555 
556 static void
557 siginfo(int sig __unused)
558 {
559 
560 	info = 1;
561 }
562