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
36 * @(#) Copyright (c) 1989, 1993, 1994 The Regents of the University of California. All rights reserved.
37 * @(#)du.c 8.5 (Berkeley) 5/4/95
38 * $FreeBSD: src/usr.bin/du/du.c,v 1.17.2.4 2002/12/12 16:29:39 trhodes Exp $
39 * $DragonFly: src/usr.bin/du/du.c,v 1.10 2008/07/13 03:37:43 dillon Exp $
42 #include <sys/param.h>
43 #include <sys/queue.h>
57 #define KILO_SZ(n) (n)
58 #define MEGA_SZ(n) ((n) * (n))
59 #define GIGA_SZ(n) ((n) * (n) * (n))
60 #define TERA_SZ(n) ((n) * (n) * (n) * (n))
61 #define PETA_SZ(n) ((n) * (n) * (n) * (n) * (n))
63 #define KILO_2_SZ (KILO_SZ(1024ULL))
64 #define MEGA_2_SZ (MEGA_SZ(1024ULL))
65 #define GIGA_2_SZ (GIGA_SZ(1024ULL))
66 #define TERA_2_SZ (TERA_SZ(1024ULL))
67 #define PETA_2_SZ (PETA_SZ(1024ULL))
69 #define KILO_SI_SZ (KILO_SZ(1000ULL))
70 #define MEGA_SI_SZ (MEGA_SZ(1000ULL))
71 #define GIGA_SI_SZ (GIGA_SZ(1000ULL))
72 #define TERA_SI_SZ (TERA_SZ(1000ULL))
73 #define PETA_SI_SZ (PETA_SZ(1000ULL))
75 #define HASHSIZE 256 /* power of 2 only */
76 #define HASHMASK (HASHSIZE - 1)
78 unsigned long long vals_si
[] = {1, KILO_SI_SZ
, MEGA_SI_SZ
, GIGA_SI_SZ
, TERA_SI_SZ
, PETA_SI_SZ
};
79 unsigned long long vals_base2
[] = {1, KILO_2_SZ
, MEGA_2_SZ
, GIGA_2_SZ
, TERA_2_SZ
, PETA_2_SZ
};
80 unsigned long long *valp
;
82 typedef enum { NONE
, KILO
, MEGA
, GIGA
, TERA
, PETA
, UNIT_MAX
} unit_t
;
84 int unitp
[] = { NONE
, KILO
, MEGA
, GIGA
, TERA
, PETA
};
86 SLIST_HEAD(ignhead
, ignentry
) ignores
;
89 SLIST_ENTRY(ignentry
) next
;
92 static int linkchk(FTSENT
*);
93 static void usage(void);
94 void prthumanval(double);
95 unit_t
unit_adjust(double *);
96 void ignoreadd(const char *);
97 void ignoreclean(void);
98 int ignorep(FTSENT
*);
100 static char period
[] = ".";
102 typedef long long du_number_t
;
105 main(int argc
, char **argv
)
110 du_number_t savednumber
= 0;
114 int Hflag
, Lflag
, Pflag
, aflag
, sflag
, dflag
, cflag
, hflag
, ch
, notused
, rval
;
117 Hflag
= Lflag
= Pflag
= aflag
= sflag
= dflag
= cflag
= hflag
= 0;
122 SLIST_INIT(&ignores
);
124 while ((ch
= getopt(argc
, argv
, "HI:LPasd:chkrx")) != -1)
151 depth
= atoi(optarg
);
152 if (errno
== ERANGE
|| depth
< 0) {
153 warnx("invalid argument to option d: %s", optarg
);
161 if (putenv("BLOCKSIZE=512") == -1)
162 warn("putenv: cannot set BLOCKSIZE=512");
168 if (putenv("BLOCKSIZE=1024") == -1)
169 warn("putenv: cannot set BLOCKSIZE=1024");
171 case 'r': /* Compatibility. */
174 ftsoptions
|= FTS_XDEV
;
186 * Because of the way that fts(3) works, logical walks will not count
187 * the blocks actually used by symbolic links. We rationalize this by
188 * noting that users computing logical sizes are likely to do logical
189 * copies, so not counting the links is correct. The real reason is
190 * that we'd have to re-implement the kernel's symbolic link traversing
191 * algorithm to get this right. If, for example, you have relative
192 * symbolic links referencing other relative symbolic links, it gets
193 * very nasty, very fast. The bottom line is that it's documented in
194 * the man page, so it's a feature.
197 if (Hflag
+ Lflag
+ Pflag
> 1)
200 if (Hflag
+ Lflag
+ Pflag
== 0)
201 Pflag
= 1; /* -P (physical) is default */
204 ftsoptions
|= FTS_COMFOLLOW
;
207 ftsoptions
|= FTS_LOGICAL
;
210 ftsoptions
|= FTS_PHYSICAL
;
230 (void) getbsize(¬used
, &blocksize
);
235 if ((fts
= fts_open(argv
, ftsoptions
, NULL
)) == NULL
)
238 while ((p
= fts_read(fts
)) != NULL
) {
239 switch (p
->fts_info
) {
240 case FTS_D
: /* Ignore. */
242 fts_set(fts
, p
, FTS_SKIP
);
248 if (p
->fts_pointer
== NULL
) {
249 p
->fts_pointer
= malloc(sizeof(du_number_t
));
250 *(du_number_t
*)p
->fts_pointer
= 0;
252 *(du_number_t
*)p
->fts_pointer
+= p
->fts_statp
->st_blocks
;
254 if (p
->fts_parent
->fts_pointer
== NULL
) {
255 p
->fts_parent
->fts_pointer
= malloc(sizeof(du_number_t
));
256 *(du_number_t
*)p
->fts_parent
->fts_pointer
= 0;
258 *(du_number_t
*)p
->fts_parent
->fts_pointer
+= *(du_number_t
*)p
->fts_pointer
+= p
->fts_statp
->st_blocks
;
260 if (p
->fts_level
<= depth
) {
262 (void) prthumanval(howmany(*(du_number_t
*)p
->fts_pointer
, blocksize
));
263 (void) printf("\t%s\n", p
->fts_path
);
265 (void) printf("%lld\t%s\n",
266 howmany(*(du_number_t
*)p
->fts_pointer
, blocksize
),
270 if (p
->fts_pointer
) {
271 free(p
->fts_pointer
);
272 p
->fts_pointer
= NULL
;
275 case FTS_DC
: /* Ignore. */
277 case FTS_DNR
: /* Warn, continue. */
280 warnx("%s: %s", p
->fts_path
, strerror(p
->fts_errno
));
287 if (p
->fts_statp
->st_nlink
> 1 && linkchk(p
))
290 if (listall
|| p
->fts_level
== 0) {
292 (void) prthumanval(howmany(p
->fts_statp
->st_blocks
,
294 (void) printf("\t%s\n", p
->fts_path
);
296 (void) printf("%lld\t%s\n",
297 howmany((long long)p
->fts_statp
->st_blocks
, blocksize
),
301 if (p
->fts_parent
->fts_pointer
== NULL
) {
302 p
->fts_parent
->fts_pointer
= malloc(sizeof(du_number_t
));
303 *(du_number_t
*)p
->fts_parent
->fts_pointer
= 0;
305 *(du_number_t
*)p
->fts_parent
->fts_pointer
+= p
->fts_statp
->st_blocks
;
307 if (p
->fts_parent
->fts_pointer
)
308 savednumber
= *(du_number_t
*)p
->fts_parent
->fts_pointer
;
316 (void) prthumanval(howmany(savednumber
, blocksize
));
317 (void) printf("\ttotal\n");
319 (void) printf("%lld\ttotal\n", howmany(savednumber
, blocksize
));
331 struct links_entry
*next
;
332 struct links_entry
*previous
;
338 static const size_t links_hash_initial_size
= 8192;
339 static struct links_entry
**buckets
;
340 static struct links_entry
*free_list
;
341 static size_t number_buckets
;
342 static unsigned long number_entries
;
343 static char stop_allocating
;
344 struct links_entry
*le
, **new_buckets
;
351 /* If necessary, initialize the hash table. */
352 if (buckets
== NULL
) {
353 number_buckets
= links_hash_initial_size
;
354 buckets
= malloc(number_buckets
* sizeof(buckets
[0]));
356 errx(1, "No memory for hardlink detection");
357 for (i
= 0; i
< number_buckets
; i
++)
361 /* If the hash table is getting too full, enlarge it. */
362 if (number_entries
> number_buckets
* 10 && !stop_allocating
) {
363 new_size
= number_buckets
* 2;
364 new_buckets
= malloc(new_size
* sizeof(struct links_entry
*));
366 /* Try releasing the free list to see if that helps. */
367 if (new_buckets
== NULL
&& free_list
!= NULL
) {
368 while (free_list
!= NULL
) {
370 free_list
= le
->next
;
373 new_buckets
= malloc(new_size
* sizeof(new_buckets
[0]));
376 if (new_buckets
== NULL
) {
378 warnx("No more memory for tracking hard links");
380 memset(new_buckets
, 0, new_size
* sizeof(struct links_entry
*));
381 for (i
= 0; i
< number_buckets
; i
++) {
382 while (buckets
[i
] != NULL
) {
383 /* Remove entry from old bucket. */
385 buckets
[i
] = le
->next
;
387 /* Add entry to new bucket. */
388 hash
= (le
->dev
^ le
->ino
) % new_size
;
390 if (new_buckets
[hash
] != NULL
)
391 new_buckets
[hash
]->previous
= le
;
392 le
->next
= new_buckets
[hash
];
394 new_buckets
[hash
] = le
;
398 buckets
= new_buckets
;
399 number_buckets
= new_size
;
403 /* Try to locate this entry in the hash table. */
404 hash
= ( st
->st_dev
^ st
->st_ino
) % number_buckets
;
405 for (le
= buckets
[hash
]; le
!= NULL
; le
= le
->next
) {
406 if (le
->dev
== st
->st_dev
&& le
->ino
== st
->st_ino
) {
408 * Save memory by releasing an entry when we've seen
411 if (--le
->links
<= 0) {
412 if (le
->previous
!= NULL
)
413 le
->previous
->next
= le
->next
;
414 if (le
->next
!= NULL
)
415 le
->next
->previous
= le
->previous
;
416 if (buckets
[hash
] == le
)
417 buckets
[hash
] = le
->next
;
419 /* Recycle this node through the free list */
420 if (stop_allocating
) {
423 le
->next
= free_list
;
434 /* Add this entry to the links cache. */
435 if (free_list
!= NULL
) {
436 /* Pull a node from the free list if we can. */
438 free_list
= le
->next
;
440 /* Malloc one if we have to. */
441 le
= malloc(sizeof(struct links_entry
));
444 warnx("No more memory for tracking hard links");
447 le
->dev
= st
->st_dev
;
448 le
->ino
= st
->st_ino
;
449 le
->links
= st
->st_nlink
- 1;
451 le
->next
= buckets
[hash
];
453 if (buckets
[hash
] != NULL
)
454 buckets
[hash
]->previous
= le
;
460 * Output in "human-readable" format. Uses 3 digits max and puts
461 * unit suffixes at the end. Makes output compact and easy to read,
462 * especially on huge disks.
466 unit_adjust(double *val
)
470 unsigned int unit_sz
;
474 unit_sz
= abval
? ilogb(abval
) / 10 : 0;
476 if (unit_sz
>= UNIT_MAX
) {
479 unit
= unitp
[unit_sz
];
480 *val
/= (double)valp
[unit_sz
];
487 prthumanval(double bytes
)
492 unit
= unit_adjust(&bytes
);
497 (void)printf("%3.0f%c", bytes
, "BKMGTPE"[unit
]);
499 (void)printf("%3.1f%c", bytes
, "BKMGTPE"[unit
]);
505 (void)fprintf(stderr
,
506 "usage: du [-H | -L | -P] [-a | -s | -d depth] [-c] [-h | -k] [-x] [-I mask] [file ...]\n");
511 ignoreadd(const char *mask
)
513 struct ignentry
*ign
;
515 ign
= calloc(1, sizeof(*ign
));
517 errx(1, "cannot allocate memory");
518 ign
->mask
= strdup(mask
);
519 if (ign
->mask
== NULL
)
520 errx(1, "cannot allocate memory");
521 SLIST_INSERT_HEAD(&ignores
, ign
, next
);
527 struct ignentry
*ign
;
529 while (!SLIST_EMPTY(&ignores
)) {
530 ign
= SLIST_FIRST(&ignores
);
531 SLIST_REMOVE_HEAD(&ignores
, next
);
540 struct ignentry
*ign
;
542 SLIST_FOREACH(ign
, &ignores
, next
)
543 if (fnmatch(ign
->mask
, ent
->fts_name
, 0) != FNM_NOMATCH
)