xref: /freebsd/usr.bin/du/du.c (revision d93a896ef95946b0bf1219866fcb324b78543444)
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. 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 #include <err.h>
51 #include <errno.h>
52 #include <fnmatch.h>
53 #include <fts.h>
54 #include <libutil.h>
55 #include <locale.h>
56 #include <stdint.h>
57 #include <stdio.h>
58 #include <stdlib.h>
59 #include <string.h>
60 #include <sysexits.h>
61 #include <unistd.h>
62 
63 static SLIST_HEAD(ignhead, ignentry) ignores;
64 struct ignentry {
65 	char			*mask;
66 	SLIST_ENTRY(ignentry)	next;
67 };
68 
69 static int	linkchk(FTSENT *);
70 static void	usage(void);
71 static void	prthumanval(int64_t);
72 static void	ignoreadd(const char *);
73 static void	ignoreclean(void);
74 static int	ignorep(FTSENT *);
75 static void	siginfo(int __unused);
76 
77 static int	nodumpflag = 0;
78 static int	Aflag;
79 static long	blocksize, cblocksize;
80 static volatile sig_atomic_t info;
81 
82 int
83 main(int argc, char *argv[])
84 {
85 	FTS		*fts;
86 	FTSENT		*p;
87 	off_t		savednumber, curblocks;
88 	off_t		threshold, threshold_sign;
89 	int		ftsoptions;
90 	int		depth;
91 	int		Hflag, Lflag, aflag, sflag, dflag, cflag;
92 	int		hflag, lflag, ch, notused, rval;
93 	char 		**save;
94 	static char	dot[] = ".";
95 
96 	setlocale(LC_ALL, "");
97 
98 	Hflag = Lflag = aflag = sflag = dflag = cflag = hflag =
99 	    lflag = Aflag = 0;
100 
101 	save = argv;
102 	ftsoptions = FTS_PHYSICAL;
103 	savednumber = 0;
104 	threshold = 0;
105 	threshold_sign = 1;
106 	cblocksize = DEV_BSIZE;
107 	blocksize = 0;
108 	depth = INT_MAX;
109 	SLIST_INIT(&ignores);
110 
111 	while ((ch = getopt(argc, argv, "AB:HI:LPasd:cghklmnrt:x")) != -1)
112 		switch (ch) {
113 		case 'A':
114 			Aflag = 1;
115 			break;
116 		case 'B':
117 			errno = 0;
118 			cblocksize = atoi(optarg);
119 			if (errno == ERANGE || cblocksize <= 0) {
120 				warnx("invalid argument to option B: %s",
121 				    optarg);
122 				usage();
123 			}
124 			break;
125 		case 'H':
126 			Hflag = 1;
127 			Lflag = 0;
128 			break;
129 		case 'I':
130 			ignoreadd(optarg);
131 			break;
132 		case 'L':
133 			Lflag = 1;
134 			Hflag = 0;
135 			break;
136 		case 'P':
137 			Hflag = Lflag = 0;
138 			break;
139 		case 'a':
140 			aflag = 1;
141 			break;
142 		case 's':
143 			sflag = 1;
144 			break;
145 		case 'd':
146 			dflag = 1;
147 			errno = 0;
148 			depth = atoi(optarg);
149 			if (errno == ERANGE || depth < 0) {
150 				warnx("invalid argument to option d: %s",
151 				    optarg);
152 				usage();
153 			}
154 			break;
155 		case 'c':
156 			cflag = 1;
157 			break;
158 		case 'g':
159 			hflag = 0;
160 			blocksize = 1073741824;
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)
215 		ftsoptions |= FTS_COMFOLLOW;
216 	if (Lflag) {
217 		ftsoptions &= ~FTS_PHYSICAL;
218 		ftsoptions |= FTS_LOGICAL;
219 	}
220 
221 	if (!Aflag && (cblocksize % DEV_BSIZE) != 0)
222 		cblocksize = howmany(cblocksize, DEV_BSIZE) * DEV_BSIZE;
223 
224 	if (aflag + dflag + sflag > 1)
225 		usage();
226 	if (sflag)
227 		depth = 0;
228 
229 	if (!*argv) {
230 		argv = save;
231 		argv[0] = dot;
232 		argv[1] = NULL;
233 	}
234 
235 	if (blocksize == 0)
236 		(void)getbsize(&notused, &blocksize);
237 
238 	if (!Aflag) {
239 		cblocksize /= DEV_BSIZE;
240 		blocksize /= DEV_BSIZE;
241 	}
242 
243 	if (threshold != 0)
244 		threshold = howmany(threshold / DEV_BSIZE * cblocksize,
245 		    blocksize);
246 
247 	rval = 0;
248 
249 	(void)signal(SIGINFO, siginfo);
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 && threshold <=
271 			    threshold_sign * howmany(p->fts_bignum *
272 			    cblocksize, blocksize)) {
273 				if (hflag) {
274 					prthumanval(p->fts_bignum);
275 					(void)printf("\t%s\n", p->fts_path);
276 				} else {
277 					(void)printf("%jd\t%s\n",
278 					    (intmax_t)howmany(p->fts_bignum *
279 					    cblocksize, blocksize),
280 					    p->fts_path);
281 				}
282 			}
283 			if (info) {
284 				info = 0;
285 				(void)printf("\t%s\n", p->fts_path);
286 			}
287 			break;
288 		case FTS_DC:			/* Ignore. */
289 			break;
290 		case FTS_DNR:			/* Warn, continue. */
291 		case FTS_ERR:
292 		case FTS_NS:
293 			warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
294 			rval = 1;
295 			break;
296 		default:
297 			if (ignorep(p))
298 				break;
299 
300 			if (lflag == 0 && p->fts_statp->st_nlink > 1 &&
301 			    linkchk(p))
302 				break;
303 
304 			curblocks = Aflag ?
305 			    howmany(p->fts_statp->st_size, cblocksize) :
306 			    howmany(p->fts_statp->st_blocks, cblocksize);
307 
308 			if (aflag || p->fts_level == 0) {
309 				if (hflag) {
310 					prthumanval(curblocks);
311 					(void)printf("\t%s\n", p->fts_path);
312 				} else {
313 					(void)printf("%jd\t%s\n",
314 					    (intmax_t)howmany(curblocks *
315 					    cblocksize, blocksize),
316 					    p->fts_path);
317 				}
318 			}
319 
320 			p->fts_parent->fts_bignum += curblocks;
321 		}
322 		savednumber = p->fts_parent->fts_bignum;
323 	}
324 
325 	if (errno)
326 		err(1, "fts_read");
327 
328 	if (cflag) {
329 		if (hflag) {
330 			prthumanval(savednumber);
331 			(void)printf("\ttotal\n");
332 		} else {
333 			(void)printf("%jd\ttotal\n", (intmax_t)howmany(
334 			    savednumber * cblocksize, blocksize));
335 		}
336 	}
337 
338 	ignoreclean();
339 	exit(rval);
340 }
341 
342 static int
343 linkchk(FTSENT *p)
344 {
345 	struct links_entry {
346 		struct links_entry *next;
347 		struct links_entry *previous;
348 		int	 links;
349 		dev_t	 dev;
350 		ino_t	 ino;
351 	};
352 	static const size_t links_hash_initial_size = 8192;
353 	static struct links_entry **buckets;
354 	static struct links_entry *free_list;
355 	static size_t number_buckets;
356 	static unsigned long number_entries;
357 	static char stop_allocating;
358 	struct links_entry *le, **new_buckets;
359 	struct stat *st;
360 	size_t i, new_size;
361 	int hash;
362 
363 	st = p->fts_statp;
364 
365 	/* If necessary, initialize the hash table. */
366 	if (buckets == NULL) {
367 		number_buckets = links_hash_initial_size;
368 		buckets = malloc(number_buckets * sizeof(buckets[0]));
369 		if (buckets == NULL)
370 			errx(1, "No memory for hardlink detection");
371 		for (i = 0; i < number_buckets; i++)
372 			buckets[i] = NULL;
373 	}
374 
375 	/* If the hash table is getting too full, enlarge it. */
376 	if (number_entries > number_buckets * 10 && !stop_allocating) {
377 		new_size = number_buckets * 2;
378 		new_buckets = calloc(new_size, sizeof(struct links_entry *));
379 
380 		/* Try releasing the free list to see if that helps. */
381 		if (new_buckets == NULL && free_list != NULL) {
382 			while (free_list != NULL) {
383 				le = free_list;
384 				free_list = le->next;
385 				free(le);
386 			}
387 			new_buckets = calloc(new_size, sizeof(new_buckets[0]));
388 		}
389 
390 		if (new_buckets == NULL) {
391 			stop_allocating = 1;
392 			warnx("No more memory for tracking hard links");
393 		} else {
394 			for (i = 0; i < number_buckets; i++) {
395 				while (buckets[i] != NULL) {
396 					/* Remove entry from old bucket. */
397 					le = buckets[i];
398 					buckets[i] = le->next;
399 
400 					/* Add entry to new bucket. */
401 					hash = (le->dev ^ le->ino) % new_size;
402 
403 					if (new_buckets[hash] != NULL)
404 						new_buckets[hash]->previous =
405 						    le;
406 					le->next = new_buckets[hash];
407 					le->previous = NULL;
408 					new_buckets[hash] = le;
409 				}
410 			}
411 			free(buckets);
412 			buckets = new_buckets;
413 			number_buckets = new_size;
414 		}
415 	}
416 
417 	/* Try to locate this entry in the hash table. */
418 	hash = ( st->st_dev ^ st->st_ino ) % number_buckets;
419 	for (le = buckets[hash]; le != NULL; le = le->next) {
420 		if (le->dev == st->st_dev && le->ino == st->st_ino) {
421 			/*
422 			 * Save memory by releasing an entry when we've seen
423 			 * all of its links.
424 			 */
425 			if (--le->links <= 0) {
426 				if (le->previous != NULL)
427 					le->previous->next = le->next;
428 				if (le->next != NULL)
429 					le->next->previous = le->previous;
430 				if (buckets[hash] == le)
431 					buckets[hash] = le->next;
432 				number_entries--;
433 				/* Recycle this node through the free list */
434 				if (stop_allocating) {
435 					free(le);
436 				} else {
437 					le->next = free_list;
438 					free_list = le;
439 				}
440 			}
441 			return (1);
442 		}
443 	}
444 
445 	if (stop_allocating)
446 		return (0);
447 
448 	/* Add this entry to the links cache. */
449 	if (free_list != NULL) {
450 		/* Pull a node from the free list if we can. */
451 		le = free_list;
452 		free_list = le->next;
453 	} else
454 		/* Malloc one if we have to. */
455 		le = malloc(sizeof(struct links_entry));
456 	if (le == NULL) {
457 		stop_allocating = 1;
458 		warnx("No more memory for tracking hard links");
459 		return (0);
460 	}
461 	le->dev = st->st_dev;
462 	le->ino = st->st_ino;
463 	le->links = st->st_nlink - 1;
464 	number_entries++;
465 	le->next = buckets[hash];
466 	le->previous = NULL;
467 	if (buckets[hash] != NULL)
468 		buckets[hash]->previous = le;
469 	buckets[hash] = le;
470 	return (0);
471 }
472 
473 static void
474 prthumanval(int64_t bytes)
475 {
476 	char buf[5];
477 
478 	bytes *= cblocksize;
479 	if (!Aflag)
480 		bytes *= DEV_BSIZE;
481 
482 	humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE,
483 	    HN_B | HN_NOSPACE | HN_DECIMAL);
484 
485 	(void)printf("%4s", buf);
486 }
487 
488 static void
489 usage(void)
490 {
491 	(void)fprintf(stderr,
492 		"usage: du [-Aclnx] [-H | -L | -P] [-g | -h | -k | -m] "
493 		"[-a | -s | -d depth] [-B blocksize] [-I mask] "
494 		"[-t threshold] [file ...]\n");
495 	exit(EX_USAGE);
496 }
497 
498 static void
499 ignoreadd(const char *mask)
500 {
501 	struct ignentry *ign;
502 
503 	ign = calloc(1, sizeof(*ign));
504 	if (ign == NULL)
505 		errx(1, "cannot allocate memory");
506 	ign->mask = strdup(mask);
507 	if (ign->mask == NULL)
508 		errx(1, "cannot allocate memory");
509 	SLIST_INSERT_HEAD(&ignores, ign, next);
510 }
511 
512 static void
513 ignoreclean(void)
514 {
515 	struct ignentry *ign;
516 
517 	while (!SLIST_EMPTY(&ignores)) {
518 		ign = SLIST_FIRST(&ignores);
519 		SLIST_REMOVE_HEAD(&ignores, next);
520 		free(ign->mask);
521 		free(ign);
522 	}
523 }
524 
525 static int
526 ignorep(FTSENT *ent)
527 {
528 	struct ignentry *ign;
529 
530 	if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP))
531 		return 1;
532 	SLIST_FOREACH(ign, &ignores, next)
533 		if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH)
534 			return 1;
535 	return 0;
536 }
537 
538 static void
539 siginfo(int sig __unused)
540 {
541 
542 	info = 1;
543 }
544