du.c revision 228356 
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: head/usr.bin/du/du.c 228356 2011-12-09 02:30:56Z gjb $");
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
64static SLIST_HEAD(ignhead, ignentry) ignores;
65struct ignentry {
66	char			*mask;
67	SLIST_ENTRY(ignentry)	next;
68};
69
70static int	linkchk(FTSENT *);
71static void	usage(void);
72static void	prthumanval(int64_t);
73static void	ignoreadd(const char *);
74static void	ignoreclean(void);
75static int	ignorep(FTSENT *);
76static void	siginfo(int __unused);
77
78static int	nodumpflag = 0;
79static int	Aflag;
80static long	blocksize, cblocksize;
81static volatile sig_atomic_t info;
82
83int
84main(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		depth;
92	int		Hflag, Lflag, Pflag, aflag, sflag, dflag, cflag;
93	int		hflag, lflag, ch, notused, rval;
94	char 		**save;
95	static char	dot[] = ".";
96
97	setlocale(LC_ALL, "");
98
99	Hflag = Lflag = Pflag = aflag = sflag = dflag = cflag = hflag =
100	    lflag = Aflag = 0;
101
102	save = argv;
103	ftsoptions = 0;
104	savednumber = 0;
105	threshold = 0;
106	threshold_sign = 1;
107	cblocksize = DEV_BSIZE;
108	blocksize = 0;
109	depth = INT_MAX;
110	SLIST_INIT(&ignores);
111
112	while ((ch = getopt(argc, argv, "AB:HI:LPasd:chklmnrt:x")) != -1)
113		switch (ch) {
114		case 'A':
115			Aflag = 1;
116			break;
117		case 'B':
118			errno = 0;
119			cblocksize = atoi(optarg);
120			if (errno == ERANGE || cblocksize <= 0) {
121				warnx("invalid argument to option B: %s",
122				    optarg);
123				usage();
124			}
125			break;
126		case 'H':
127			Hflag = 1;
128			break;
129		case 'I':
130			ignoreadd(optarg);
131			break;
132		case 'L':
133			if (Pflag)
134				usage();
135			Lflag = 1;
136			break;
137		case 'P':
138			if (Lflag)
139				usage();
140			Pflag = 1;
141			break;
142		case 'a':
143			aflag = 1;
144			break;
145		case 's':
146			sflag = 1;
147			break;
148		case 'd':
149			dflag = 1;
150			errno = 0;
151			depth = atoi(optarg);
152			if (errno == ERANGE || depth < 0) {
153				warnx("invalid argument to option d: %s",
154				    optarg);
155				usage();
156			}
157			break;
158		case 'c':
159			cflag = 1;
160			break;
161		case 'h':
162			hflag = 1;
163			break;
164		case 'k':
165			hflag = 0;
166			blocksize = 1024;
167			break;
168		case 'l':
169			lflag = 1;
170			break;
171		case 'm':
172			hflag = 0;
173			blocksize = 1048576;
174			break;
175		case 'n':
176			nodumpflag = 1;
177			break;
178		case 'r':		 /* Compatibility. */
179			break;
180		case 't' :
181			if (expand_number(optarg, &threshold) != 0 ||
182			    threshold == 0) {
183				warnx("invalid threshold: %s", optarg);
184				usage();
185			} else if (threshold < 0)
186				threshold_sign = -1;
187			break;
188		case 'x':
189			ftsoptions |= FTS_XDEV;
190			break;
191		case '?':
192		default:
193			usage();
194			/* NOTREACHED */
195		}
196
197	argc -= optind;
198	argv += optind;
199
200	/*
201	 * XXX
202	 * Because of the way that fts(3) works, logical walks will not count
203	 * the blocks actually used by symbolic links.  We rationalize this by
204	 * noting that users computing logical sizes are likely to do logical
205	 * copies, so not counting the links is correct.  The real reason is
206	 * that we'd have to re-implement the kernel's symbolic link traversing
207	 * algorithm to get this right.  If, for example, you have relative
208	 * symbolic links referencing other relative symbolic links, it gets
209	 * very nasty, very fast.  The bottom line is that it's documented in
210	 * the man page, so it's a feature.
211	 */
212
213	if (Hflag + Lflag + Pflag > 1)
214		usage();
215
216	if (Hflag + Lflag + Pflag == 0)
217		Pflag = 1;			/* -P (physical) is default */
218
219	if (Hflag)
220		ftsoptions |= FTS_COMFOLLOW;
221
222	if (Lflag)
223		ftsoptions |= FTS_LOGICAL;
224
225	if (Pflag)
226		ftsoptions |= FTS_PHYSICAL;
227
228	if (!Aflag && (cblocksize % DEV_BSIZE) != 0)
229		cblocksize = howmany(cblocksize, DEV_BSIZE) * DEV_BSIZE;
230
231	if (aflag + dflag + sflag > 1)
232		usage();
233	if (sflag)
234		depth = 0;
235
236	if (!*argv) {
237		argv = save;
238		argv[0] = dot;
239		argv[1] = NULL;
240	}
241
242	if (blocksize == 0)
243		(void)getbsize(&notused, &blocksize);
244
245	if (!Aflag) {
246		cblocksize /= DEV_BSIZE;
247		blocksize /= DEV_BSIZE;
248	}
249
250	if (threshold != 0)
251		threshold = howmany(threshold / DEV_BSIZE * cblocksize,
252		    blocksize);
253
254	rval = 0;
255
256	(void)signal(SIGINFO, siginfo);
257
258	if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL)
259		err(1, "fts_open");
260
261	while ((p = fts_read(fts)) != NULL) {
262		switch (p->fts_info) {
263		case FTS_D:			/* Ignore. */
264			if (ignorep(p))
265				fts_set(fts, p, FTS_SKIP);
266			break;
267		case FTS_DP:
268			if (ignorep(p))
269				break;
270
271			curblocks = Aflag ?
272			    howmany(p->fts_statp->st_size, cblocksize) :
273			    howmany(p->fts_statp->st_blocks, cblocksize);
274			p->fts_parent->fts_bignum += p->fts_bignum +=
275			    curblocks;
276
277			if (p->fts_level <= depth && threshold <=
278			    threshold_sign * howmany(p->fts_bignum *
279			    cblocksize, blocksize)) {
280				if (hflag) {
281					prthumanval(p->fts_bignum);
282					(void)printf("\t%s\n", p->fts_path);
283				} else {
284					(void)printf("%jd\t%s\n",
285					    (intmax_t)howmany(p->fts_bignum *
286					    cblocksize, blocksize),
287					    p->fts_path);
288				}
289			}
290			if (info) {
291				info = 0;
292				(void)printf("\t%s\n", p->fts_path);
293			}
294			break;
295		case FTS_DC:			/* Ignore. */
296			break;
297		case FTS_DNR:			/* Warn, continue. */
298		case FTS_ERR:
299		case FTS_NS:
300			warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
301			rval = 1;
302			break;
303		default:
304			if (ignorep(p))
305				break;
306
307			if (lflag == 0 && p->fts_statp->st_nlink > 1 &&
308			    linkchk(p))
309				break;
310
311			curblocks = Aflag ?
312			    howmany(p->fts_statp->st_size, cblocksize) :
313			    howmany(p->fts_statp->st_blocks, cblocksize);
314
315			if (aflag || p->fts_level == 0) {
316				if (hflag) {
317					prthumanval(curblocks);
318					(void)printf("\t%s\n", p->fts_path);
319				} else {
320					(void)printf("%jd\t%s\n",
321					    (intmax_t)howmany(curblocks *
322					    cblocksize, blocksize),
323					    p->fts_path);
324				}
325			}
326
327			p->fts_parent->fts_bignum += curblocks;
328		}
329		savednumber = p->fts_parent->fts_bignum;
330	}
331
332	if (errno)
333		err(1, "fts_read");
334
335	if (cflag) {
336		if (hflag) {
337			prthumanval(savednumber);
338			(void)printf("\ttotal\n");
339		} else {
340			(void)printf("%jd\ttotal\n", (intmax_t)howmany(
341			    savednumber * cblocksize, blocksize));
342		}
343	}
344
345	ignoreclean();
346	exit(rval);
347}
348
349static int
350linkchk(FTSENT *p)
351{
352	struct links_entry {
353		struct links_entry *next;
354		struct links_entry *previous;
355		int	 links;
356		dev_t	 dev;
357		ino_t	 ino;
358	};
359	static const size_t links_hash_initial_size = 8192;
360	static struct links_entry **buckets;
361	static struct links_entry *free_list;
362	static size_t number_buckets;
363	static unsigned long number_entries;
364	static char stop_allocating;
365	struct links_entry *le, **new_buckets;
366	struct stat *st;
367	size_t i, new_size;
368	int hash;
369
370	st = p->fts_statp;
371
372	/* If necessary, initialize the hash table. */
373	if (buckets == NULL) {
374		number_buckets = links_hash_initial_size;
375		buckets = malloc(number_buckets * sizeof(buckets[0]));
376		if (buckets == NULL)
377			errx(1, "No memory for hardlink detection");
378		for (i = 0; i < number_buckets; i++)
379			buckets[i] = NULL;
380	}
381
382	/* If the hash table is getting too full, enlarge it. */
383	if (number_entries > number_buckets * 10 && !stop_allocating) {
384		new_size = number_buckets * 2;
385		new_buckets = malloc(new_size * sizeof(struct links_entry *));
386
387		/* Try releasing the free list to see if that helps. */
388		if (new_buckets == NULL && free_list != NULL) {
389			while (free_list != NULL) {
390				le = free_list;
391				free_list = le->next;
392				free(le);
393			}
394			new_buckets = malloc(new_size *
395			    sizeof(new_buckets[0]));
396		}
397
398		if (new_buckets == NULL) {
399			stop_allocating = 1;
400			warnx("No more memory for tracking hard links");
401		} else {
402			memset(new_buckets, 0,
403			    new_size * sizeof(struct links_entry *));
404			for (i = 0; i < number_buckets; i++) {
405				while (buckets[i] != NULL) {
406					/* Remove entry from old bucket. */
407					le = buckets[i];
408					buckets[i] = le->next;
409
410					/* Add entry to new bucket. */
411					hash = (le->dev ^ le->ino) % new_size;
412
413					if (new_buckets[hash] != NULL)
414						new_buckets[hash]->previous =
415						    le;
416					le->next = new_buckets[hash];
417					le->previous = NULL;
418					new_buckets[hash] = le;
419				}
420			}
421			free(buckets);
422			buckets = new_buckets;
423			number_buckets = new_size;
424		}
425	}
426
427	/* Try to locate this entry in the hash table. */
428	hash = ( st->st_dev ^ st->st_ino ) % number_buckets;
429	for (le = buckets[hash]; le != NULL; le = le->next) {
430		if (le->dev == st->st_dev && le->ino == st->st_ino) {
431			/*
432			 * Save memory by releasing an entry when we've seen
433			 * all of it's links.
434			 */
435			if (--le->links <= 0) {
436				if (le->previous != NULL)
437					le->previous->next = le->next;
438				if (le->next != NULL)
439					le->next->previous = le->previous;
440				if (buckets[hash] == le)
441					buckets[hash] = le->next;
442				number_entries--;
443				/* Recycle this node through the free list */
444				if (stop_allocating) {
445					free(le);
446				} else {
447					le->next = free_list;
448					free_list = le;
449				}
450			}
451			return (1);
452		}
453	}
454
455	if (stop_allocating)
456		return (0);
457
458	/* Add this entry to the links cache. */
459	if (free_list != NULL) {
460		/* Pull a node from the free list if we can. */
461		le = free_list;
462		free_list = le->next;
463	} else
464		/* Malloc one if we have to. */
465		le = malloc(sizeof(struct links_entry));
466	if (le == NULL) {
467		stop_allocating = 1;
468		warnx("No more memory for tracking hard links");
469		return (0);
470	}
471	le->dev = st->st_dev;
472	le->ino = st->st_ino;
473	le->links = st->st_nlink - 1;
474	number_entries++;
475	le->next = buckets[hash];
476	le->previous = NULL;
477	if (buckets[hash] != NULL)
478		buckets[hash]->previous = le;
479	buckets[hash] = le;
480	return (0);
481}
482
483static void
484prthumanval(int64_t bytes)
485{
486	char buf[5];
487
488	bytes *= cblocksize;
489	if (!Aflag)
490		bytes *= DEV_BSIZE;
491
492	humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE,
493	    HN_B | HN_NOSPACE | HN_DECIMAL);
494
495	(void)printf("%4s", buf);
496}
497
498static void
499usage(void)
500{
501	(void)fprintf(stderr,
502		"usage: du [-Aclnx] [-H | -L | -P] [-h | -k | -m ] "
503		"[-a | -s | -d depth] [-B blocksize] [-I mask] "
504		"[-t threshold] [file ...]\n");
505	exit(EX_USAGE);
506}
507
508static void
509ignoreadd(const char *mask)
510{
511	struct ignentry *ign;
512
513	ign = calloc(1, sizeof(*ign));
514	if (ign == NULL)
515		errx(1, "cannot allocate memory");
516	ign->mask = strdup(mask);
517	if (ign->mask == NULL)
518		errx(1, "cannot allocate memory");
519	SLIST_INSERT_HEAD(&ignores, ign, next);
520}
521
522static void
523ignoreclean(void)
524{
525	struct ignentry *ign;
526
527	while (!SLIST_EMPTY(&ignores)) {
528		ign = SLIST_FIRST(&ignores);
529		SLIST_REMOVE_HEAD(&ignores, next);
530		free(ign->mask);
531		free(ign);
532	}
533}
534
535static int
536ignorep(FTSENT *ent)
537{
538	struct ignentry *ign;
539
540	if (nodumpflag && (ent->fts_statp->st_flags & UF_NODUMP))
541		return 1;
542	SLIST_FOREACH(ign, &ignores, next)
543		if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH)
544			return 1;
545	return 0;
546}
547
548static void
549siginfo(int sig __unused)
550{
551
552	info = 1;
553}
554