2 * Copyright (c) 1989, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
5 * This code is derived from software contributed to Berkeley by
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
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 $
37 #include <sys/param.h>
38 #include <sys/queue.h>
52 #define HASHSIZE 256 /* power of 2 only */
53 #define HASHMASK (HASHSIZE - 1)
55 #define STBLOCKS(statp) _stblocks(tflag, statp)
57 static SLIST_HEAD(ignhead
, ignentry
) ignores
;
60 SLIST_ENTRY(ignentry
) next
;
63 static int linkchk(FTSENT
*);
64 static void usage(void);
65 void prthumanval(int64_t);
66 void ignoreadd(const char *);
67 void ignoreclean(void);
68 int ignorep(FTSENT
*);
70 static char period
[] = ".";
72 typedef long long du_number_t
;
75 _stblocks(int tflag
, struct stat
*st
)
78 return (st
->st_size
+ 511) / 512;
84 main(int argc
, char **argv
)
89 du_number_t savednumber
= 0;
93 int Hflag
, Lflag
, Pflag
;
94 int aflag
, sflag
, dflag
, cflag
, hflag
, tflag
;
95 int ch
, notused
, rval
;
98 Hflag
= Lflag
= Pflag
= 0;
99 aflag
= sflag
= dflag
= cflag
= hflag
= tflag
= 0;
104 SLIST_INIT(&ignores
);
106 while ((ch
= getopt(argc
, argv
, "HI:LPastd:chkrx")) != -1)
136 depth
= atoi(optarg
);
137 if (errno
== ERANGE
|| depth
< 0) {
138 warnx("invalid argument to option d: %s", optarg
);
146 if (setenv("BLOCKSIZE", "512", 1) == -1)
147 warn("setenv: cannot set BLOCKSIZE=512");
152 if (setenv("BLOCKSIZE", "1024", 1) == -1)
153 warn("setenv: cannot set BLOCKSIZE=1024");
155 case 'r': /* Compatibility. */
158 ftsoptions
|= FTS_XDEV
;
170 * Because of the way that fts(3) works, logical walks will not count
171 * the blocks actually used by symbolic links. We rationalize this by
172 * noting that users computing logical sizes are likely to do logical
173 * copies, so not counting the links is correct. The real reason is
174 * that we'd have to re-implement the kernel's symbolic link traversing
175 * algorithm to get this right. If, for example, you have relative
176 * symbolic links referencing other relative symbolic links, it gets
177 * very nasty, very fast. The bottom line is that it's documented in
178 * the man page, so it's a feature.
181 if (Hflag
+ Lflag
+ Pflag
> 1)
184 if (Hflag
+ Lflag
+ Pflag
== 0)
185 Pflag
= 1; /* -P (physical) is default */
188 ftsoptions
|= FTS_COMFOLLOW
;
191 ftsoptions
|= FTS_LOGICAL
;
194 ftsoptions
|= FTS_PHYSICAL
;
214 (void) getbsize(¬used
, &blocksize
);
219 if ((fts
= fts_open(argv
, ftsoptions
, NULL
)) == NULL
)
222 while ((p
= fts_read(fts
)) != NULL
) {
223 switch (p
->fts_info
) {
224 case FTS_D
: /* Ignore. */
226 fts_set(fts
, p
, FTS_SKIP
);
232 if (p
->fts_pointer
== NULL
) {
233 p
->fts_pointer
= malloc(sizeof(du_number_t
));
234 *(du_number_t
*)p
->fts_pointer
= 0;
236 *(du_number_t
*)p
->fts_pointer
+= STBLOCKS(p
->fts_statp
);
238 if (p
->fts_parent
->fts_pointer
== NULL
) {
239 p
->fts_parent
->fts_pointer
= malloc(sizeof(du_number_t
));
240 *(du_number_t
*)p
->fts_parent
->fts_pointer
= 0;
242 *(du_number_t
*)p
->fts_parent
->fts_pointer
+= *(du_number_t
*)p
->fts_pointer
+= STBLOCKS(p
->fts_statp
);
244 if (p
->fts_level
<= depth
) {
246 (void) prthumanval(howmany(*(du_number_t
*)p
->fts_pointer
, blocksize
));
247 (void) printf("\t%s\n", p
->fts_path
);
249 (void) printf("%lld\t%s\n",
250 howmany(*(du_number_t
*)p
->fts_pointer
, blocksize
),
254 if (p
->fts_pointer
) {
255 free(p
->fts_pointer
);
256 p
->fts_pointer
= NULL
;
259 case FTS_DC
: /* Ignore. */
261 case FTS_DNR
: /* Warn, continue. */
264 warnx("%s: %s", p
->fts_path
, strerror(p
->fts_errno
));
271 if (p
->fts_statp
->st_nlink
> 1 && linkchk(p
))
274 if (listall
|| p
->fts_level
== 0) {
276 (void) prthumanval(howmany(STBLOCKS(p
->fts_statp
),
278 (void) printf("\t%s\n", p
->fts_path
);
280 (void) printf("%lld\t%s\n",
281 howmany((long long)STBLOCKS(p
->fts_statp
), blocksize
),
285 if (p
->fts_parent
->fts_pointer
== NULL
) {
286 p
->fts_parent
->fts_pointer
= malloc(sizeof(du_number_t
));
287 *(du_number_t
*)p
->fts_parent
->fts_pointer
= 0;
289 *(du_number_t
*)p
->fts_parent
->fts_pointer
+= STBLOCKS(p
->fts_statp
);
291 if (p
->fts_parent
->fts_pointer
)
292 savednumber
= *(du_number_t
*)p
->fts_parent
->fts_pointer
;
302 (void) prthumanval(howmany(savednumber
, blocksize
));
303 (void) printf("\ttotal\n");
305 (void) printf("%lld\ttotal\n", howmany(savednumber
, blocksize
));
317 struct links_entry
*next
;
318 struct links_entry
*previous
;
324 static const size_t links_hash_initial_size
= 8192;
325 static struct links_entry
**buckets
;
326 static struct links_entry
*free_list
;
327 static size_t number_buckets
;
328 static unsigned long number_entries
;
329 static char stop_allocating
;
330 struct links_entry
*le
, **new_buckets
;
337 /* If necessary, initialize the hash table. */
338 if (buckets
== NULL
) {
339 number_buckets
= links_hash_initial_size
;
340 buckets
= malloc(number_buckets
* sizeof(buckets
[0]));
342 errx(1, "No memory for hardlink detection");
343 for (i
= 0; i
< number_buckets
; i
++)
347 /* If the hash table is getting too full, enlarge it. */
348 if (number_entries
> number_buckets
* 10 && !stop_allocating
) {
349 new_size
= number_buckets
* 2;
350 new_buckets
= malloc(new_size
* sizeof(struct links_entry
*));
352 /* Try releasing the free list to see if that helps. */
353 if (new_buckets
== NULL
&& free_list
!= NULL
) {
354 while (free_list
!= NULL
) {
356 free_list
= le
->next
;
359 new_buckets
= malloc(new_size
* sizeof(new_buckets
[0]));
362 if (new_buckets
== NULL
) {
364 warnx("No more memory for tracking hard links");
366 memset(new_buckets
, 0, new_size
* sizeof(struct links_entry
*));
367 for (i
= 0; i
< number_buckets
; i
++) {
368 while (buckets
[i
] != NULL
) {
369 /* Remove entry from old bucket. */
371 buckets
[i
] = le
->next
;
373 /* Add entry to new bucket. */
374 hash
= (le
->dev
^ le
->ino
) % new_size
;
376 if (new_buckets
[hash
] != NULL
)
377 new_buckets
[hash
]->previous
= le
;
378 le
->next
= new_buckets
[hash
];
380 new_buckets
[hash
] = le
;
384 buckets
= new_buckets
;
385 number_buckets
= new_size
;
389 /* Try to locate this entry in the hash table. */
390 hash
= ( st
->st_dev
^ st
->st_ino
) % number_buckets
;
391 for (le
= buckets
[hash
]; le
!= NULL
; le
= le
->next
) {
392 if (le
->dev
== st
->st_dev
&& le
->ino
== st
->st_ino
) {
394 * Save memory by releasing an entry when we've seen
397 if (--le
->links
<= 0) {
398 if (le
->previous
!= NULL
)
399 le
->previous
->next
= le
->next
;
400 if (le
->next
!= NULL
)
401 le
->next
->previous
= le
->previous
;
402 if (buckets
[hash
] == le
)
403 buckets
[hash
] = le
->next
;
405 /* Recycle this node through the free list */
406 if (stop_allocating
) {
409 le
->next
= free_list
;
420 /* Add this entry to the links cache. */
421 if (free_list
!= NULL
) {
422 /* Pull a node from the free list if we can. */
424 free_list
= le
->next
;
426 /* Malloc one if we have to. */
427 le
= malloc(sizeof(struct links_entry
));
430 warnx("No more memory for tracking hard links");
433 le
->dev
= st
->st_dev
;
434 le
->ino
= st
->st_ino
;
435 le
->links
= st
->st_nlink
- 1;
437 le
->next
= buckets
[hash
];
439 if (buckets
[hash
] != NULL
)
440 buckets
[hash
]->previous
= le
;
446 prthumanval(int64_t bytes
)
448 char buf
[sizeof("999M")];
452 humanize_number(buf
, sizeof(buf
), bytes
, "", HN_AUTOSCALE
,
453 HN_B
| HN_NOSPACE
| HN_DECIMAL
);
455 (void) printf("%4s", buf
);
461 (void)fprintf(stderr
,
462 "usage: du [-H | -L | -P] [-a | -s | -d depth] [-c] [-h | -k] [-x] [-I mask] [file ...]\n");
467 ignoreadd(const char *mask
)
469 struct ignentry
*ign
;
471 ign
= calloc(1, sizeof(*ign
));
473 errx(1, "cannot allocate memory");
474 ign
->mask
= strdup(mask
);
475 if (ign
->mask
== NULL
)
476 errx(1, "cannot allocate memory");
477 SLIST_INSERT_HEAD(&ignores
, ign
, next
);
483 struct ignentry
*ign
;
485 while (!SLIST_EMPTY(&ignores
)) {
486 ign
= SLIST_FIRST(&ignores
);
487 SLIST_REMOVE_HEAD(&ignores
, next
);
496 struct ignentry
*ign
;
498 SLIST_FOREACH(ign
, &ignores
, next
)
499 if (fnmatch(ign
->mask
, ent
->fts_name
, 0) != FNM_NOMATCH
)