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. 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.
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
37 #include <sys/cdefs.h>
39 __used
static const char copyright
[] =
40 "@(#) Copyright (c) 1989, 1993, 1994\n\
41 The Regents of the University of California. All rights reserved.\n";
46 static const char sccsid
[] = "@(#)du.c 8.5 (Berkeley) 5/4/95";
49 #include <sys/cdefs.h>
50 __FBSDID("$FreeBSD: src/usr.bin/du/du.c,v 1.38 2005/04/09 14:31:40 stefanf Exp $");
52 #include <sys/mount.h>
53 #include <sys/param.h>
54 #include <sys/queue.h>
72 #include <get_compat.h>
73 #include <sys/sysctl.h>
75 #define COMPAT_MODE(func, mode) (1)
78 #define KILO_SZ(n) (n)
79 #define MEGA_SZ(n) ((n) * (n))
80 #define GIGA_SZ(n) ((n) * (n) * (n))
81 #define TERA_SZ(n) ((n) * (n) * (n) * (n))
82 #define PETA_SZ(n) ((n) * (n) * (n) * (n) * (n))
84 #define KILO_2_SZ (KILO_SZ(1024ULL))
85 #define MEGA_2_SZ (MEGA_SZ(1024ULL))
86 #define GIGA_2_SZ (GIGA_SZ(1024ULL))
87 #define TERA_2_SZ (TERA_SZ(1024ULL))
88 #define PETA_2_SZ (PETA_SZ(1024ULL))
90 #define KILO_SI_SZ (KILO_SZ(1000ULL))
91 #define MEGA_SI_SZ (MEGA_SZ(1000ULL))
92 #define GIGA_SI_SZ (GIGA_SZ(1000ULL))
93 #define TERA_SI_SZ (TERA_SZ(1000ULL))
94 #define PETA_SI_SZ (PETA_SZ(1000ULL))
96 unsigned long long vals_si
[] = {1, KILO_SI_SZ
, MEGA_SI_SZ
, GIGA_SI_SZ
, TERA_SI_SZ
, PETA_SI_SZ
};
97 unsigned long long vals_base2
[] = {1, KILO_2_SZ
, MEGA_2_SZ
, GIGA_2_SZ
, TERA_2_SZ
, PETA_2_SZ
};
98 unsigned long long *valp
;
100 typedef enum { NONE
, KILO
, MEGA
, GIGA
, TERA
, PETA
, UNIT_MAX
} unit_t
;
102 int unitp
[] = { NONE
, KILO
, MEGA
, GIGA
, TERA
, PETA
};
104 SLIST_HEAD(ignhead
, ignentry
) ignores
;
107 SLIST_ENTRY(ignentry
) next
;
110 static int linkchk(FTSENT
*);
111 static int dirlinkchk(FTSENT
*);
112 static void usage(void);
113 void prthumanval(double);
114 unit_t
unit_adjust(double *);
115 void ignoreadd(const char *);
116 void ignoreclean(void);
117 int ignorep(FTSENT
*);
120 main(int argc
, char *argv
[])
124 off_t savednumber
= 0;
129 int Hflag
, Lflag
, Pflag
, aflag
, sflag
, dflag
, cflag
, hflag
, ch
, notused
, rval
;
131 static char dot
[] = ".";
132 off_t
*ftsnum
, *ftsparnum
;
134 setlocale(LC_ALL
, "");
136 Hflag
= Lflag
= Pflag
= aflag
= sflag
= dflag
= cflag
= hflag
= 0;
139 ftsoptions
= FTS_NOCHDIR
;
141 SLIST_INIT(&ignores
);
143 while ((ch
= getopt(argc
, argv
, "HI:LPasd:cghkmrx")) != -1)
169 depth
= atoi(optarg
);
170 if (errno
== ERANGE
|| depth
< 0) {
171 warnx("invalid argument to option d: %s", optarg
);
179 putenv("BLOCKSIZE=512");
185 putenv("BLOCKSIZE=1024");
189 putenv("BLOCKSIZE=1048576");
193 putenv("BLOCKSIZE=1g");
195 case 'r': /* Compatibility. */
198 ftsoptions
|= FTS_XDEV
;
210 * Because of the way that fts(3) works, logical walks will not count
211 * the blocks actually used by symbolic links. We rationalize this by
212 * noting that users computing logical sizes are likely to do logical
213 * copies, so not counting the links is correct. The real reason is
214 * that we'd have to re-implement the kernel's symbolic link traversing
215 * algorithm to get this right. If, for example, you have relative
216 * symbolic links referencing other relative symbolic links, it gets
217 * very nasty, very fast. The bottom line is that it's documented in
218 * the man page, so it's a feature.
221 if (Hflag
+ Lflag
+ Pflag
> 1)
224 if (Hflag
+ Lflag
+ Pflag
== 0)
225 Pflag
= 1; /* -P (physical) is default */
228 ftsoptions
|= FTS_COMFOLLOW
;
231 ftsoptions
|= FTS_LOGICAL
;
234 ftsoptions
|= FTS_PHYSICAL
;
254 (void) getbsize(¬used
, &blocksize
);
258 // "du" should not have any side effect on disk usage,
259 // so prevent materializing dataless directories upon traversal
261 (void) sysctlbyname("vfs.nspace.prevent_materialization", NULL
, NULL
, &rval
, sizeof(rval
));
262 #endif /* __APPLE__ */
266 if ((fts
= fts_open(argv
, ftsoptions
, NULL
)) == NULL
)
269 while ((p
= fts_read(fts
)) != NULL
) {
270 switch (p
->fts_info
) {
272 if (ignorep(p
) || dirlinkchk(p
))
273 fts_set(fts
, p
, FTS_SKIP
);
279 ftsparnum
= (off_t
*)&p
->fts_parent
->fts_number
;
280 ftsnum
= (off_t
*)&p
->fts_number
;
281 ftsparnum
[0] += ftsnum
[0] += p
->fts_statp
->st_blocks
;
283 if (p
->fts_level
<= depth
) {
285 (void) prthumanval(howmany(*ftsnum
, blocksize
));
286 (void) printf("\t%s\n", p
->fts_path
);
288 (void) printf("%jd\t%s\n",
289 (intmax_t)howmany(*ftsnum
, blocksize
),
294 case FTS_DC
: /* Ignore. */
295 if (COMPAT_MODE("bin/du", "unix2003")) {
296 errx(1, "Can't follow symlink cycle from %s to %s", p
->fts_path
, p
->fts_cycle
->fts_path
);
299 case FTS_DNR
: /* Warn, continue. */
302 warnx("%s: %s", p
->fts_path
, strerror(p
->fts_errno
));
306 if (COMPAT_MODE("bin/du", "unix2003")) {
308 int rc
= stat(p
->fts_path
, &sb
);
309 if (rc
< 0 && errno
== ELOOP
) {
310 errx(1, "Too many symlinks at %s", p
->fts_path
);
317 if (p
->fts_statp
->st_nlink
> 1 && linkchk(p
))
320 if (listall
|| p
->fts_level
== 0) {
322 (void) prthumanval(howmany(p
->fts_statp
->st_blocks
,
324 (void) printf("\t%s\n", p
->fts_path
);
326 (void) printf("%jd\t%s\n",
327 (intmax_t)howmany(p
->fts_statp
->st_blocks
, blocksize
),
332 ftsparnum
= (off_t
*)&p
->fts_parent
->fts_number
;
333 ftsparnum
[0] += p
->fts_statp
->st_blocks
;
335 savednumber
= ((off_t
*)&p
->fts_parent
->fts_number
)[0];
343 (void) prthumanval(howmany(savednumber
, blocksize
));
344 (void) printf("\ttotal\n");
346 (void) printf("%jd\ttotal\n", (intmax_t)howmany(savednumber
, blocksize
));
358 struct links_entry
*next
;
359 struct links_entry
*previous
;
364 static const size_t links_hash_initial_size
= 8192;
365 static struct links_entry
**buckets
;
366 static struct links_entry
*free_list
;
367 static size_t number_buckets
;
368 static unsigned long number_entries
;
369 static char stop_allocating
;
370 struct links_entry
*le
, **new_buckets
;
377 /* If necessary, initialize the hash table. */
378 if (buckets
== NULL
) {
379 number_buckets
= links_hash_initial_size
;
380 buckets
= malloc(number_buckets
* sizeof(buckets
[0]));
382 errx(1, "No memory for hardlink detection");
383 for (i
= 0; i
< number_buckets
; i
++)
387 /* If the hash table is getting too full, enlarge it. */
388 if (number_entries
> number_buckets
* 10 && !stop_allocating
) {
389 new_size
= number_buckets
* 2;
390 new_buckets
= malloc(new_size
* sizeof(struct links_entry
*));
392 /* Try releasing the free list to see if that helps. */
393 if (new_buckets
== NULL
&& free_list
!= NULL
) {
394 while (free_list
!= NULL
) {
396 free_list
= le
->next
;
399 new_buckets
= malloc(new_size
* sizeof(new_buckets
[0]));
402 if (new_buckets
== NULL
) {
404 warnx("No more memory for tracking hard links");
406 memset(new_buckets
, 0,
407 new_size
* sizeof(struct links_entry
*));
408 for (i
= 0; i
< number_buckets
; i
++) {
409 while (buckets
[i
] != NULL
) {
410 /* Remove entry from old bucket. */
412 buckets
[i
] = le
->next
;
414 /* Add entry to new bucket. */
415 hash
= (le
->dev
^ le
->ino
) % new_size
;
417 if (new_buckets
[hash
] != NULL
)
418 new_buckets
[hash
]->previous
=
420 le
->next
= new_buckets
[hash
];
422 new_buckets
[hash
] = le
;
426 buckets
= new_buckets
;
427 number_buckets
= new_size
;
431 /* Try to locate this entry in the hash table. */
432 hash
= ( st
->st_dev
^ st
->st_ino
) % number_buckets
;
433 for (le
= buckets
[hash
]; le
!= NULL
; le
= le
->next
) {
434 if (le
->dev
== st
->st_dev
&& le
->ino
== st
->st_ino
) {
436 * Save memory by releasing an entry when we've seen
439 if (--le
->links
<= 0) {
440 if (le
->previous
!= NULL
)
441 le
->previous
->next
= le
->next
;
442 if (le
->next
!= NULL
)
443 le
->next
->previous
= le
->previous
;
444 if (buckets
[hash
] == le
)
445 buckets
[hash
] = le
->next
;
447 /* Recycle this node through the free list */
448 if (stop_allocating
) {
451 le
->next
= free_list
;
462 /* Add this entry to the links cache. */
463 if (free_list
!= NULL
) {
464 /* Pull a node from the free list if we can. */
466 free_list
= le
->next
;
468 /* Malloc one if we have to. */
469 le
= malloc(sizeof(struct links_entry
));
472 warnx("No more memory for tracking hard links");
475 le
->dev
= st
->st_dev
;
476 le
->ino
= st
->st_ino
;
477 le
->links
= st
->st_nlink
- 1;
479 le
->next
= buckets
[hash
];
481 if (buckets
[hash
] != NULL
)
482 buckets
[hash
]->previous
= le
;
488 dirlinkchk(FTSENT
*p
)
491 struct links_entry
*next
;
492 struct links_entry
*previous
;
497 static const size_t links_hash_initial_size
= 8192;
498 static struct links_entry
**buckets
;
499 static struct links_entry
*free_list
;
500 static size_t number_buckets
;
501 static unsigned long number_entries
;
502 static char stop_allocating
;
503 struct links_entry
*le
, **new_buckets
;
511 struct attrlist attrList
;
513 memset(&attrList
, 0, sizeof(attrList
));
514 attrList
.bitmapcount
= ATTR_BIT_MAP_COUNT
;
515 attrList
.dirattr
= ATTR_DIR_LINKCOUNT
;
516 if (-1 == getattrlist(p
->fts_path
, &attrList
, &buf
, sizeof(buf
), 0))
518 if (buf
.linkcount
== 1)
522 /* If necessary, initialize the hash table. */
523 if (buckets
== NULL
) {
524 number_buckets
= links_hash_initial_size
;
525 buckets
= malloc(number_buckets
* sizeof(buckets
[0]));
527 errx(1, "No memory for directory hardlink detection");
528 for (i
= 0; i
< number_buckets
; i
++)
532 /* If the hash table is getting too full, enlarge it. */
533 if (number_entries
> number_buckets
* 10 && !stop_allocating
) {
534 new_size
= number_buckets
* 2;
535 new_buckets
= malloc(new_size
* sizeof(struct links_entry
*));
537 /* Try releasing the free list to see if that helps. */
538 if (new_buckets
== NULL
&& free_list
!= NULL
) {
539 while (free_list
!= NULL
) {
541 free_list
= le
->next
;
544 new_buckets
= malloc(new_size
* sizeof(new_buckets
[0]));
547 if (new_buckets
== NULL
) {
549 warnx("No more memory for tracking directory hard links");
551 memset(new_buckets
, 0,
552 new_size
* sizeof(struct links_entry
*));
553 for (i
= 0; i
< number_buckets
; i
++) {
554 while (buckets
[i
] != NULL
) {
555 /* Remove entry from old bucket. */
557 buckets
[i
] = le
->next
;
559 /* Add entry to new bucket. */
560 hash
= (le
->dev
^ le
->ino
) % new_size
;
562 if (new_buckets
[hash
] != NULL
)
563 new_buckets
[hash
]->previous
=
565 le
->next
= new_buckets
[hash
];
567 new_buckets
[hash
] = le
;
571 buckets
= new_buckets
;
572 number_buckets
= new_size
;
576 /* Try to locate this entry in the hash table. */
577 hash
= ( st
->st_dev
^ st
->st_ino
) % number_buckets
;
578 for (le
= buckets
[hash
]; le
!= NULL
; le
= le
->next
) {
579 if (le
->dev
== st
->st_dev
&& le
->ino
== st
->st_ino
) {
581 * Save memory by releasing an entry when we've seen
584 if (--le
->links
<= 0) {
585 if (le
->previous
!= NULL
)
586 le
->previous
->next
= le
->next
;
587 if (le
->next
!= NULL
)
588 le
->next
->previous
= le
->previous
;
589 if (buckets
[hash
] == le
)
590 buckets
[hash
] = le
->next
;
592 /* Recycle this node through the free list */
593 if (stop_allocating
) {
596 le
->next
= free_list
;
606 /* Add this entry to the links cache. */
607 if (free_list
!= NULL
) {
608 /* Pull a node from the free list if we can. */
610 free_list
= le
->next
;
612 /* Malloc one if we have to. */
613 le
= malloc(sizeof(struct links_entry
));
616 warnx("No more memory for tracking hard links");
619 le
->dev
= st
->st_dev
;
620 le
->ino
= st
->st_ino
;
621 le
->links
= buf
.linkcount
- 1;
623 le
->next
= buckets
[hash
];
625 if (buckets
[hash
] != NULL
)
626 buckets
[hash
]->previous
= le
;
632 * Output in "human-readable" format. Uses 3 digits max and puts
633 * unit suffixes at the end. Makes output compact and easy to read,
634 * especially on huge disks.
638 unit_adjust(double *val
)
642 unsigned int unit_sz
;
646 unit_sz
= abval ?
ilogb(abval
) / 10 : 0;
648 if (unit_sz
>= UNIT_MAX
) {
651 unit
= unitp
[unit_sz
];
652 *val
/= (double)valp
[unit_sz
];
659 prthumanval(double bytes
)
664 unit
= unit_adjust(&bytes
);
669 (void)printf("%3.0f%c", bytes
, "BKMGTPE"[unit
]);
671 (void)printf("%3.1f%c", bytes
, "BKMGTPE"[unit
]);
677 (void)fprintf(stderr
,
678 "usage: du [-H | -L | -P] [-a | -s | -d depth] [-c] [-h | -k | -m | -g] [-x] [-I mask] [file ...]\n");
683 ignoreadd(const char *mask
)
685 struct ignentry
*ign
;
687 ign
= calloc(1, sizeof(*ign
));
689 errx(1, "cannot allocate memory");
690 ign
->mask
= strdup(mask
);
691 if (ign
->mask
== NULL
)
692 errx(1, "cannot allocate memory");
693 SLIST_INSERT_HEAD(&ignores
, ign
, next
);
699 struct ignentry
*ign
;
701 while (!SLIST_EMPTY(&ignores
)) {
702 ign
= SLIST_FIRST(&ignores
);
703 SLIST_REMOVE_HEAD(&ignores
, next
);
712 struct ignentry
*ign
;
715 if (S_ISDIR(ent
->fts_statp
->st_mode
) && !strcmp("fd", ent
->fts_name
)) {
717 int rc
= statfs(ent
->fts_accpath
, &sfsb
);
718 if (rc
>= 0 && !strcmp("devfs", sfsb
.f_fstypename
)) {
719 /* Don't cd into /dev/fd/N since one of those is likely to be
720 the cwd as of the start of du which causes all manner of
721 unpleasant surprises */
725 #endif /* __APPLE__ */
726 SLIST_FOREACH(ign
, &ignores
, next
)
727 if (fnmatch(ign
->mask
, ent
->fts_name
, 0) != FNM_NOMATCH
)