xref: /dragonfly/usr.bin/du/du.c (revision a9783bc6) 
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  * @(#) Copyright (c) 1989, 1993, 1994 The Regents of the University of California.  All rights reserved.
33  * @(#)du.c	8.5 (Berkeley) 5/4/95
34  * $FreeBSD: src/usr.bin/du/du.c,v 1.17.2.4 2002/12/12 16:29:39 trhodes Exp $
35  * $DragonFly: src/usr.bin/du/du.c,v 1.12 2008/08/12 03:35:35 y0netan1 Exp $
36  */
37 
38 #include <sys/param.h>
39 #include <sys/queue.h>
40 #include <sys/stat.h>
41 
42 #include <err.h>
43 #include <errno.h>
44 #include <fnmatch.h>
45 #include <fts.h>
46 #include <libutil.h>
47 #include <stdio.h>
48 #include <stdlib.h>
49 #include <string.h>
50 #include <sysexits.h>
51 #include <unistd.h>
52 
53 #define	HASHSIZE	256		/* power of 2 only */
54 #define HASHMASK	(HASHSIZE - 1)
55 
56 #define STBLOCKS(statp)	_stblocks(tflag, statp)
57 
58 SLIST_HEAD(ignhead, ignentry) ignores;
59 struct ignentry {
60 	char			*mask;
61 	SLIST_ENTRY(ignentry)	next;
62 };
63 
64 static int	linkchk(FTSENT *);
65 static void	usage(void);
66 void		prthumanval(int64_t);
67 void		ignoreadd(const char *);
68 void		ignoreclean(void);
69 int		ignorep(FTSENT *);
70 
71 static char period[] = ".";
72 
73 typedef long long	du_number_t;
74 
75 static blkcnt_t
76 _stblocks(int tflag, struct stat *st)
77 {
78 	if (tflag)
79 		return (st->st_size + 511) / 512;
80 	else
81 		return st->st_blocks;
82 }
83 
84 int
85 main(int argc, char **argv)
86 {
87 	FTS		*fts;
88 	FTSENT		*p;
89 	long		blocksize;
90 	du_number_t	savednumber = 0;
91 	int		ftsoptions;
92 	int		listall;
93 	int		depth;
94 	int		Hflag, Lflag, Pflag;
95 	int		aflag, sflag, dflag, cflag, hflag, tflag;
96 	int		ch, notused, rval;
97 	char 		**save;
98 
99 	Hflag = Lflag = Pflag = 0;
100 	aflag = sflag = dflag = cflag = hflag = tflag = 0;
101 
102 	save = argv;
103 	ftsoptions = 0;
104 	depth = INT_MAX;
105 	SLIST_INIT(&ignores);
106 
107 	while ((ch = getopt(argc, argv, "HI:LPastd:chkrx")) != -1)
108 		switch (ch) {
109 			case 'H':
110 				Hflag = 1;
111 				break;
112 			case 'I':
113 				ignoreadd(optarg);
114 				break;
115 			case 'L':
116 				if (Pflag)
117 					usage();
118 				Lflag = 1;
119 				break;
120 			case 'P':
121 				if (Lflag)
122 					usage();
123 				Pflag = 1;
124 				break;
125 			case 'a':
126 				aflag = 1;
127 				break;
128 			case 's':
129 				sflag = 1;
130 				break;
131 			case 't':
132 				tflag = 1;
133 				break;
134 			case 'd':
135 				dflag = 1;
136 				errno = 0;
137 				depth = atoi(optarg);
138 				if (errno == ERANGE || depth < 0) {
139 					warnx("invalid argument to option d: %s", optarg);
140 					usage();
141 				}
142 				break;
143 			case 'c':
144 				cflag = 1;
145 				break;
146 			case 'h':
147 				if (setenv("BLOCKSIZE", "512", 1) == -1)
148 					warn("setenv: cannot set BLOCKSIZE=512");
149 				hflag = 1;
150 				break;
151 			case 'k':
152 				hflag = 0;
153 				if (setenv("BLOCKSIZE", "1024", 1) == -1)
154 					warn("setenv: cannot set BLOCKSIZE=1024");
155 				break;
156 			case 'r':		 /* Compatibility. */
157 				break;
158 			case 'x':
159 				ftsoptions |= FTS_XDEV;
160 				break;
161 			case '?':
162 			default:
163 				usage();
164 		}
165 
166 	argc -= optind;
167 	argv += optind;
168 
169 	/*
170 	 * XXX
171 	 * Because of the way that fts(3) works, logical walks will not count
172 	 * the blocks actually used by symbolic links.  We rationalize this by
173 	 * noting that users computing logical sizes are likely to do logical
174 	 * copies, so not counting the links is correct.  The real reason is
175 	 * that we'd have to re-implement the kernel's symbolic link traversing
176 	 * algorithm to get this right.  If, for example, you have relative
177 	 * symbolic links referencing other relative symbolic links, it gets
178 	 * very nasty, very fast.  The bottom line is that it's documented in
179 	 * the man page, so it's a feature.
180 	 */
181 
182 	if (Hflag + Lflag + Pflag > 1)
183 		usage();
184 
185 	if (Hflag + Lflag + Pflag == 0)
186 		Pflag = 1;			/* -P (physical) is default */
187 
188 	if (Hflag)
189 		ftsoptions |= FTS_COMFOLLOW;
190 
191 	if (Lflag)
192 		ftsoptions |= FTS_LOGICAL;
193 
194 	if (Pflag)
195 		ftsoptions |= FTS_PHYSICAL;
196 
197 	listall = 0;
198 
199 	if (aflag) {
200 		if (sflag || dflag)
201 			usage();
202 		listall = 1;
203 	} else if (sflag) {
204 		if (dflag)
205 			usage();
206 		depth = 0;
207 	}
208 
209 	if (!*argv) {
210 		argv = save;
211 		argv[0] = period;
212 		argv[1] = NULL;
213 	}
214 
215 	(void) getbsize(&notused, &blocksize);
216 	blocksize /= 512;
217 
218 	rval = 0;
219 
220 	if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL)
221 		err(1, "fts_open");
222 
223 	while ((p = fts_read(fts)) != NULL) {
224 		switch (p->fts_info) {
225 			case FTS_D:			/* Ignore. */
226 				if (ignorep(p))
227 					fts_set(fts, p, FTS_SKIP);
228 				break;
229 			case FTS_DP:
230 				if (ignorep(p))
231 					break;
232 
233 				if (p->fts_pointer == NULL) {
234 					p->fts_pointer = malloc(sizeof(du_number_t));
235 					*(du_number_t *)p->fts_pointer = 0;
236 				}
237 				*(du_number_t *)p->fts_pointer += STBLOCKS(p->fts_statp);
238 
239 				if (p->fts_parent->fts_pointer == NULL) {
240 					p->fts_parent->fts_pointer = malloc(sizeof(du_number_t));
241 					*(du_number_t *)p->fts_parent->fts_pointer = 0;
242 				}
243 				*(du_number_t *)p->fts_parent->fts_pointer += *(du_number_t *)p->fts_pointer += STBLOCKS(p->fts_statp);
244 
245 				if (p->fts_level <= depth) {
246 					if (hflag) {
247 						(void) prthumanval(howmany(*(du_number_t *)p->fts_pointer, blocksize));
248 						(void) printf("\t%s\n", p->fts_path);
249 					} else {
250 					(void) printf("%lld\t%s\n",
251 					    howmany(*(du_number_t *)p->fts_pointer, blocksize),
252 					    p->fts_path);
253 					}
254 				}
255 				if (p->fts_pointer) {
256 					free(p->fts_pointer);
257 					p->fts_pointer = NULL;
258 				}
259 				break;
260 			case FTS_DC:			/* Ignore. */
261 				break;
262 			case FTS_DNR:			/* Warn, continue. */
263 			case FTS_ERR:
264 			case FTS_NS:
265 				warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
266 				rval = 1;
267 				break;
268 			default:
269 				if (ignorep(p))
270 					break;
271 
272 				if (p->fts_statp->st_nlink > 1 && linkchk(p))
273 					break;
274 
275 				if (listall || p->fts_level == 0) {
276 					if (hflag) {
277 						(void) prthumanval(howmany(STBLOCKS(p->fts_statp),
278 							blocksize));
279 						(void) printf("\t%s\n", p->fts_path);
280 					} else {
281 						(void) printf("%lld\t%s\n",
282 							howmany((long long)STBLOCKS(p->fts_statp), blocksize),
283 							p->fts_path);
284 					}
285 				}
286 				if (p->fts_parent->fts_pointer == NULL) {
287 					p->fts_parent->fts_pointer = malloc(sizeof(du_number_t));
288 					*(du_number_t *)p->fts_parent->fts_pointer = 0;
289 				}
290 				*(du_number_t *)p->fts_parent->fts_pointer += STBLOCKS(p->fts_statp);
291 		}
292 		if (p->fts_parent->fts_pointer)
293 			savednumber = *(du_number_t *)p->fts_parent->fts_pointer;
294 	}
295 
296 	if (errno)
297 		err(1, "fts_read");
298 
299 	fts_close(fts);
300 
301 	if (cflag) {
302 		if (hflag) {
303 			(void) prthumanval(howmany(savednumber, blocksize));
304 			(void) printf("\ttotal\n");
305 		} else {
306 			(void) printf("%lld\ttotal\n", howmany(savednumber, blocksize));
307 		}
308 	}
309 
310 	ignoreclean();
311 	exit(rval);
312 }
313 
314 static int
315 linkchk(FTSENT *p)
316 {
317 	struct links_entry {
318 		struct links_entry *next;
319 		struct links_entry *previous;
320 		int		links;
321 		dev_t		dev;
322 		ino_t		ino;
323 	};
324 
325 	static const size_t links_hash_initial_size = 8192;
326 	static struct links_entry **buckets;
327 	static struct links_entry *free_list;
328 	static size_t number_buckets;
329 	static unsigned long number_entries;
330 	static char stop_allocating;
331 	struct links_entry *le, **new_buckets;
332 	struct stat *st;
333 	size_t i, new_size;
334 	int hash;
335 
336 	st = p->fts_statp;
337 
338 	/* If necessary, initialize the hash table. */
339 	if (buckets == NULL) {
340 		number_buckets = links_hash_initial_size;
341 		buckets = malloc(number_buckets * sizeof(buckets[0]));
342 		if (buckets == NULL)
343 			errx(1, "No memory for hardlink detection");
344 		for (i = 0; i < number_buckets; i++)
345 			buckets[i] = NULL;
346 	}
347 
348 	/* If the hash table is getting too full, enlarge it. */
349 	if (number_entries > number_buckets * 10 && !stop_allocating) {
350 		new_size = number_buckets * 2;
351 		new_buckets = malloc(new_size * sizeof(struct links_entry *));
352 
353 		/* Try releasing the free list to see if that helps. */
354 		if (new_buckets == NULL && free_list != NULL) {
355 			while (free_list != NULL) {
356 				le = free_list;
357 				free_list = le->next;
358 				free(le);
359 			}
360 			new_buckets = malloc(new_size * sizeof(new_buckets[0]));
361 		}
362 
363 		if (new_buckets == NULL) {
364 			stop_allocating = 1;
365 			warnx("No more memory for tracking hard links");
366 		} else {
367 			memset(new_buckets, 0, new_size * sizeof(struct links_entry *));
368 			for (i = 0; i < number_buckets; i++) {
369 				while (buckets[i] != NULL) {
370 					/* Remove entry from old bucket. */
371 					le = buckets[i];
372 					buckets[i] = le->next;
373 
374 					/* Add entry to new bucket. */
375 					hash = (le->dev ^ le->ino) % new_size;
376 
377 					if (new_buckets[hash] != NULL)
378 						new_buckets[hash]->previous = le;
379 					le->next = new_buckets[hash];
380 					le->previous = NULL;
381 					new_buckets[hash] = le;
382 				}
383 			}
384 			free(buckets);
385 			buckets = new_buckets;
386 			number_buckets = new_size;
387 		}
388 	}
389 
390 	/* Try to locate this entry in the hash table. */
391 	hash = ( st->st_dev ^ st->st_ino ) % number_buckets;
392 	for (le = buckets[hash]; le != NULL; le = le->next) {
393 		if (le->dev == st->st_dev && le->ino == st->st_ino) {
394 			/*
395 			 * Save memory by releasing an entry when we've seen
396 			 * all of it's links.
397 			 */
398 			if (--le->links <= 0) {
399 				if (le->previous != NULL)
400 					le->previous->next = le->next;
401 				if (le->next != NULL)
402 					le->next->previous = le->previous;
403 				if (buckets[hash] == le)
404 					buckets[hash] = le->next;
405 				number_entries--;
406 				/* Recycle this node through the free list */
407 				if (stop_allocating) {
408 					free(le);
409 				} else {
410 					le->next = free_list;
411 					free_list = le;
412 				}
413 			}
414 			return (1);
415 		}
416 	}
417 
418 	if (stop_allocating)
419 		return (0);
420 
421 	/* Add this entry to the links cache. */
422 	if (free_list != NULL) {
423 		/* Pull a node from the free list if we can. */
424 		le = free_list;
425 		free_list = le->next;
426 	} else
427 		/* Malloc one if we have to. */
428 		le = malloc(sizeof(struct links_entry));
429 	if (le == NULL) {
430 		stop_allocating = 1;
431 		warnx("No more memory for tracking hard links");
432 		return (0);
433 	}
434 	le->dev = st->st_dev;
435 	le->ino = st->st_ino;
436 	le->links = st->st_nlink - 1;
437 	number_entries++;
438 	le->next = buckets[hash];
439 	le->previous = NULL;
440 	if (buckets[hash] != NULL)
441 		buckets[hash]->previous = le;
442 	buckets[hash] = le;
443 	return (0);
444 }
445 
446 void
447 prthumanval(int64_t bytes)
448 {
449 	char buf[sizeof("999M")];
450 
451 	bytes *= DEV_BSIZE;
452 
453 	humanize_number(buf, sizeof(buf), bytes, "", HN_AUTOSCALE,
454 			HN_B | HN_NOSPACE | HN_DECIMAL);
455 
456 	(void) printf("%4s", buf);
457 }
458 
459 static void
460 usage(void)
461 {
462 	(void)fprintf(stderr,
463 		"usage: du [-H | -L | -P] [-a | -s | -d depth] [-c] [-h | -k] [-x] [-I mask] [file ...]\n");
464 	exit(EX_USAGE);
465 }
466 
467 void
468 ignoreadd(const char *mask)
469 {
470 	struct ignentry *ign;
471 
472 	ign = calloc(1, sizeof(*ign));
473 	if (ign == NULL)
474 		errx(1, "cannot allocate memory");
475 	ign->mask = strdup(mask);
476 	if (ign->mask == NULL)
477 		errx(1, "cannot allocate memory");
478 	SLIST_INSERT_HEAD(&ignores, ign, next);
479 }
480 
481 void
482 ignoreclean(void)
483 {
484 	struct ignentry *ign;
485 
486 	while (!SLIST_EMPTY(&ignores)) {
487 		ign = SLIST_FIRST(&ignores);
488 		SLIST_REMOVE_HEAD(&ignores, next);
489 		free(ign->mask);
490 		free(ign);
491 	}
492 }
493 
494 int
495 ignorep(FTSENT *ent)
496 {
497 	struct ignentry *ign;
498 
499 	SLIST_FOREACH(ign, &ignores, next)
500 		if (fnmatch(ign->mask, ent->fts_name, 0) != FNM_NOMATCH)
501 			return 1;
502 	return 0;
503 }
504