1 /* $OpenBSD: du.c,v 1.18 2005/04/17 12:27:23 jmc Exp $ */
2 /* $NetBSD: du.c,v 1.11 1996/10/18 07:20:35 thorpej Exp $ */
3
4 /*
5 * Copyright (c) 1989, 1993, 1994
6 * The Regents of the University of California. All rights reserved.
7 *
8 * This code is derived from software contributed to Berkeley by
9 * Chris Newcomb.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the University nor the names of its contributors
20 * may be used to endorse or promote products derived from this software
21 * without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36 #ifndef lint
37 static char copyright[] =
38 "@(#) Copyright (c) 1989, 1993, 1994\n\
39 The Regents of the University of California. All rights reserved.\n";
40 #endif /* not lint */
41
42 #ifndef lint
43 #if 0
44 static char sccsid[] = "@(#)du.c 8.5 (Berkeley) 5/4/95";
45 #else
46 static char rcsid[] = "$OpenBSD: du.c,v 1.18 2005/04/17 12:27:23 jmc Exp $";
47 #endif
48 #endif /* not lint */
49
50 #include <sys/types.h>
51 #include <sys/stat.h>
52
53 #include <dirent.h>
54 #include <err.h>
55 #include <errno.h>
56 #include <fts.h>
57 #include <stdio.h>
58 #include <stdlib.h>
59 #include <string.h>
60 #include <sys/tree.h>
61 #include <unistd.h>
62 #include <util.h>
63
64
65 int linkchk(FTSENT *);
66 void prtout(quad_t, char *);
67 void usage(void);
68
69 int
main(int argc,char * argv[])70 main(int argc, char *argv[])
71 {
72 FTS *fts;
73 FTSENT *p;
74 long blocksize;
75 quad_t totalblocks;
76 int ftsoptions, listdirs, listfiles;
77 int Hflag, Lflag, Pflag, aflag, cflag, kflag, sflag;
78 int ch, notused, rval;
79 char **save;
80
81 save = argv;
82 Hflag = Lflag = Pflag = aflag = cflag = kflag = sflag = 0;
83 totalblocks = 0;
84 ftsoptions = FTS_PHYSICAL;
85 while ((ch = getopt(argc, argv, "HLPacksxr")) != -1)
86 switch (ch) {
87 case 'H':
88 Hflag = 1;
89 Lflag = Pflag = 0;
90 break;
91 case 'L':
92 Lflag = 1;
93 Hflag = Pflag = 0;
94 break;
95 case 'P':
96 Pflag = 1;
97 Hflag = Lflag = 0;
98 break;
99 case 'a':
100 aflag = 1;
101 break;
102 case 'c':
103 cflag = 1;
104 break;
105 case 'k':
106 kflag = 1;
107 break;
108 case 's':
109 sflag = 1;
110 break;
111 case 'r':
112 break;
113 case 'x':
114 ftsoptions |= FTS_XDEV;
115 break;
116 case '?':
117 default:
118 usage();
119 }
120 argc -= optind;
121 argv += optind;
122
123 /*
124 * XXX
125 * Because of the way that fts(3) works, logical walks will not count
126 * the blocks actually used by symbolic links. We rationalize this by
127 * noting that users computing logical sizes are likely to do logical
128 * copies, so not counting the links is correct. The real reason is
129 * that we'd have to re-implement the kernel's symbolic link traversing
130 * algorithm to get this right. If, for example, you have relative
131 * symbolic links referencing other relative symbolic links, it gets
132 * very nasty, very fast. The bottom line is that it's documented in
133 * the man page, so it's a feature.
134 */
135 if (Hflag)
136 ftsoptions |= FTS_COMFOLLOW;
137 if (Lflag) {
138 ftsoptions &= ~FTS_PHYSICAL;
139 ftsoptions |= FTS_LOGICAL;
140 }
141
142 if (aflag) {
143 if (sflag)
144 usage();
145 listdirs = listfiles = 1;
146 } else if (sflag)
147 listdirs = listfiles = 0;
148 else {
149 listfiles = 0;
150 listdirs = 1;
151 }
152
153 if (!*argv) {
154 argv = save;
155 argv[0] = ".";
156 argv[1] = NULL;
157 }
158
159 if (kflag)
160 blocksize = 1024;
161 else
162 (void)getbsize(¬used, &blocksize);
163 blocksize /= 512;
164
165 if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL)
166 err(1, "fts_open");
167
168 for (rval = 0; (p = fts_read(fts)) != NULL;)
169 switch (p->fts_info) {
170 case FTS_D: /* Ignore. */
171 break;
172 case FTS_DP:
173 p->fts_parent->fts_number +=
174 p->fts_number += p->fts_statp->st_blocks;
175 if (cflag)
176 totalblocks += p->fts_statp->st_blocks;
177 /*
178 * If listing each directory, or not listing files
179 * or directories and this is post-order of the
180 * root of a traversal, display the total.
181 */
182 if (listdirs || (!listfiles && !p->fts_level))
183 prtout((quad_t)howmany(p->fts_number, blocksize),
184 p->fts_path);
185 break;
186 case FTS_DC: /* Ignore. */
187 break;
188 case FTS_DNR: /* Warn, continue. */
189 case FTS_ERR:
190 case FTS_NS:
191 warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
192 rval = 1;
193 break;
194 default:
195 if (p->fts_statp->st_nlink > 1 && linkchk(p))
196 break;
197 /*
198 * If listing each file, or a non-directory file was
199 * the root of a traversal, display the total.
200 */
201 if (listfiles || !p->fts_level)
202 prtout(howmany(p->fts_statp->st_blocks, blocksize),
203 p->fts_path);
204 p->fts_parent->fts_number += p->fts_statp->st_blocks;
205 if (cflag)
206 totalblocks += p->fts_statp->st_blocks;
207 }
208 if (errno)
209 err(1, "fts_read");
210 if (cflag) {
211 prtout((quad_t)howmany(totalblocks, blocksize), "total");
212 }
213 exit(rval);
214 }
215
216
217 struct links_entry {
218 RB_ENTRY(links_entry) entry;
219 struct links_entry *fnext;
220 int links;
221 dev_t dev;
222 ino_t ino;
223 };
224
225 int
links_cmp(struct links_entry * e1,struct links_entry * e2)226 links_cmp(struct links_entry *e1, struct links_entry *e2)
227 {
228 if (e1->dev == e2->dev) {
229 if (e1->ino == e2->ino)
230 return (0);
231 else
232 return (e1->ino < e2->ino ? -1 : 1);
233 }
234 else
235 return (e1->dev < e2->dev ? -1 : 1);
236 }
237
238 RB_HEAD(ltree, links_entry) links = RB_INITIALIZER(&links);
239
240 RB_GENERATE(ltree, links_entry, entry, links_cmp);
241
242
243 int
linkchk(FTSENT * p)244 linkchk(FTSENT *p)
245 {
246 static struct links_entry *free_list = NULL;
247 static int stop_allocating = 0;
248 struct links_entry ltmp, *le;
249 struct stat *st;
250
251 st = p->fts_statp;
252
253 ltmp.ino = st->st_ino;
254 ltmp.dev = st->st_dev;
255
256 le = RB_FIND(ltree, &links, <mp);
257 if (le != NULL) {
258 /*
259 * Save memory by releasing an entry when we've seen
260 * all of it's links.
261 */
262 if (--le->links <= 0) {
263 RB_REMOVE(ltree, &links, le);
264 /* Recycle this node through the free list */
265 if (stop_allocating) {
266 free(le);
267 } else {
268 le->fnext = free_list;
269 free_list = le;
270 }
271 }
272 return (1);
273 }
274
275 if (stop_allocating)
276 return (0);
277
278 /* Add this entry to the links cache. */
279 if (free_list != NULL) {
280 /* Pull a node from the free list if we can. */
281 le = free_list;
282 free_list = le->fnext;
283 } else
284 /* Malloc one if we have to. */
285 le = malloc(sizeof(struct links_entry));
286
287 if (le == NULL) {
288 stop_allocating = 1;
289 warnx("No more memory for tracking hard links");
290 return (0);
291 }
292
293 le->dev = st->st_dev;
294 le->ino = st->st_ino;
295 le->links = st->st_nlink - 1;
296 le->fnext = NULL;
297
298 RB_INSERT(ltree, &links, le);
299
300 return (0);
301 }
302
303 void
prtout(quad_t size,char * path)304 prtout(quad_t size, char *path)
305 {
306 (void)printf("%lld\t%s\n", (long long)size, path);
307 }
308
309 void
usage(void)310 usage(void)
311 {
312
313 (void)fprintf(stderr,
314 "usage: du [-a | -s] [-ckrx] [-H | -L | -P] [file ...]\n");
315 exit(1);
316 }
317