du.c revision 321097 
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
34static 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
41static 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: stable/10/usr.bin/du/du.c 321097 2017-07-17 21:18:44Z ngie $");
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
63static SLIST_HEAD(ignhead, ignentry) ignores;
64struct ignentry {
65	char			*mask;
66	SLIST_ENTRY(ignentry)	next;
67};
68
69static int	linkchk(FTSENT *);
70static void	usage(void);
71static void	prthumanval(int64_t);
72static void	ignoreadd(const char *);
73static void	ignoreclean(void);
74static int	ignorep(FTSENT *);
75static void	siginfo(int __unused);
76
77static int	nodumpflag = 0;
78static int	Aflag;
79static long	blocksize, cblocksize;
80static volatile sig_atomic_t info;
81
82int
83main(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
342static int
343linkchk(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 = malloc(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 = malloc(new_size *
388			    sizeof(new_buckets[0]));
389		}
390
391		if (new_buckets == NULL) {
392			stop_allocating = 1;
393			warnx("No more memory for tracking hard links");
394		} else {
395			memset(new_buckets, 0,
396			    new_size * sizeof(struct links_entry *));
397			for (i = 0; i < number_buckets; i++) {
398				while (buckets[i] != NULL) {
399					/* Remove entry from old bucket. */
400					le = buckets[i];
401					buckets[i] = le->next;
402
403					/* Add entry to new bucket. */
404					hash = (le->dev ^ le->ino) % new_size;
405
406					if (new_buckets[hash] != NULL)
407						new_buckets[hash]->previous =
408						    le;
409					le->next = new_buckets[hash];
410					le->previous = NULL;
411					new_buckets[hash] = le;
412				}
413			}
414			free(buckets);
415			buckets = new_buckets;
416			number_buckets = new_size;
417		}
418	}
419
420	/* Try to locate this entry in the hash table. */
421	hash = ( st->st_dev ^ st->st_ino ) % number_buckets;
422	for (le = buckets[hash]; le != NULL; le = le->next) {
423		if (le->dev == st->st_dev && le->ino == st->st_ino) {
424			/*
425			 * Save memory by releasing an entry when we've seen
426			 * all of it's links.
427			 */
428			if (--le->links <= 0) {
429				if (le->previous != NULL)
430					le->previous->next = le->next;
431				if (le->next != NULL)
432					le->next->previous = le->previous;
433				if (buckets[hash] == le)
434					buckets[hash] = le->next;
435				number_entries--;
436				/* Recycle this node through the free list */
437				if (stop_allocating) {
438					free(le);
439				} else {
440					le->next = free_list;
441					free_list = le;
442				}
443			}
444			return (1);
445		}
446	}
447
448	if (stop_allocating)
449		return (0);
450
451	/* Add this entry to the links cache. */
452	if (free_list != NULL) {
453		/* Pull a node from the free list if we can. */
454		le = free_list;
455		free_list = le->next;
456	} else
457		/* Malloc one if we have to. */
458		le = malloc(sizeof(struct links_entry));
459	if (le == NULL) {
460		stop_allocating = 1;
461		warnx("No more memory for tracking hard links");
462		return (0);
463	}
464	le->dev = st->st_dev;
465	le->ino = st->st_ino;
466	le->links = st->st_nlink - 1;
467	number_entries++;
468	le->next = buckets[hash];
469	le->previous = NULL;
470	if (buckets[hash] != NULL)
471		buckets[hash]->previous = le;
472	buckets[hash] = le;
473	return (0);
474}
475
476static void
477prthumanval(int64_t bytes)
478{
479	char buf[5];
480
481	bytes *= cblocksize;
482	if (!Aflag)
483		bytes *= DEV_BSIZE;
484
485	humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE,
486	    HN_B | HN_NOSPACE | HN_DECIMAL);
487
488	(void)printf("%4s", buf);
489}
490
491static void
492usage(void)
493{
494	(void)fprintf(stderr,
495		"usage: du [-Aclnx] [-H | -L | -P] [-g | -h | -k | -m] "
496		"[-a | -s | -d depth] [-B blocksize] [-I mask] "
497		"[-t threshold] [file ...]\n");
498	exit(EX_USAGE);
499}
500
501static void
502ignoreadd(const char *mask)
503{
504	struct ignentry *ign;
505
506	ign = calloc(1, sizeof(*ign));
507	if (ign == NULL)
508		errx(1, "cannot allocate memory");
509	ign->mask = strdup(mask);
510	if (ign->mask == NULL)
511		errx(1, "cannot allocate memory");
512	SLIST_INSERT_HEAD(&ignores, ign, next);
513}
514
515static void
516ignoreclean(void)
517{
518	struct ignentry *ign;
519
520	while (!SLIST_EMPTY(&ignores)) {
521		ign = SLIST_FIRST(&ignores);
522		SLIST_REMOVE_HEAD(&ignores, next);
523		free(ign->mask);
524		free(ign);
525	}
526}
527
528static int
529ignorep(FTSENT *ent)
530{
531	struct ignentry *ign;
532
533	if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP))
534		return 1;
535	SLIST_FOREACH(ign, &ignores, next)
536		if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH)
537			return 1;
538	return 0;
539}
540
541static void
542siginfo(int sig __unused)
543{
544
545	info = 1;
546}
547