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