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