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