1 /* $OpenBSD: du.c,v 1.22 2009/10/27 23:59:37 deraadt 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 #include <sys/types.h> 37 #include <sys/stat.h> 38 39 #include <dirent.h> 40 #include <err.h> 41 #include <errno.h> 42 #include <fts.h> 43 #include <stdio.h> 44 #include <stdlib.h> 45 #include <string.h> 46 #include <sys/tree.h> 47 #include <unistd.h> 48 #include <util.h> 49 50 51 int linkchk(FTSENT *); 52 void prtout(quad_t, char *, int); 53 void usage(void); 54 55 int 56 main(int argc, char *argv[]) 57 { 58 FTS *fts; 59 FTSENT *p; 60 long blocksize; 61 quad_t totalblocks; 62 int ftsoptions, listdirs, listfiles; 63 int Hflag, Lflag, aflag, cflag, hflag, kflag, sflag; 64 int ch, notused, rval; 65 char **save; 66 67 save = argv; 68 Hflag = Lflag = aflag = cflag = hflag = kflag = sflag = 0; 69 totalblocks = 0; 70 ftsoptions = FTS_PHYSICAL; 71 while ((ch = getopt(argc, argv, "HLPachksxr")) != -1) 72 switch (ch) { 73 case 'H': 74 Hflag = 1; 75 Lflag = 0; 76 break; 77 case 'L': 78 Lflag = 1; 79 Hflag = 0; 80 break; 81 case 'P': 82 Hflag = Lflag = 0; 83 break; 84 case 'a': 85 aflag = 1; 86 break; 87 case 'c': 88 cflag = 1; 89 break; 90 case 'h': 91 hflag = 1; 92 kflag = 0; 93 break; 94 case 'k': 95 kflag = 1; 96 hflag = 0; 97 break; 98 case 's': 99 sflag = 1; 100 break; 101 case 'r': 102 break; 103 case 'x': 104 ftsoptions |= FTS_XDEV; 105 break; 106 case '?': 107 default: 108 usage(); 109 } 110 argc -= optind; 111 argv += optind; 112 113 /* 114 * XXX 115 * Because of the way that fts(3) works, logical walks will not count 116 * the blocks actually used by symbolic links. We rationalize this by 117 * noting that users computing logical sizes are likely to do logical 118 * copies, so not counting the links is correct. The real reason is 119 * that we'd have to re-implement the kernel's symbolic link traversing 120 * algorithm to get this right. If, for example, you have relative 121 * symbolic links referencing other relative symbolic links, it gets 122 * very nasty, very fast. The bottom line is that it's documented in 123 * the man page, so it's a feature. 124 */ 125 if (Hflag) 126 ftsoptions |= FTS_COMFOLLOW; 127 if (Lflag) { 128 ftsoptions &= ~FTS_PHYSICAL; 129 ftsoptions |= FTS_LOGICAL; 130 } 131 132 if (aflag) { 133 if (sflag) 134 usage(); 135 listdirs = listfiles = 1; 136 } else if (sflag) 137 listdirs = listfiles = 0; 138 else { 139 listfiles = 0; 140 listdirs = 1; 141 } 142 143 if (!*argv) { 144 argv = save; 145 argv[0] = "."; 146 argv[1] = NULL; 147 } 148 149 if (hflag) 150 blocksize = 512; 151 else if (kflag) 152 blocksize = 1024; 153 else 154 (void)getbsize(¬used, &blocksize); 155 blocksize /= 512; 156 157 if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 158 err(1, "fts_open"); 159 160 for (rval = 0; (p = fts_read(fts)) != NULL;) 161 switch (p->fts_info) { 162 case FTS_D: /* Ignore. */ 163 break; 164 case FTS_DP: 165 p->fts_parent->fts_number += 166 p->fts_number += p->fts_statp->st_blocks; 167 if (cflag) 168 totalblocks += p->fts_statp->st_blocks; 169 /* 170 * If listing each directory, or not listing files 171 * or directories and this is post-order of the 172 * root of a traversal, display the total. 173 */ 174 if (listdirs || 175 (!listfiles && p->fts_level == FTS_ROOTLEVEL)) { 176 prtout((quad_t)howmany(p->fts_number, blocksize), 177 p->fts_path, hflag); 178 } 179 break; 180 case FTS_DC: /* Ignore. */ 181 break; 182 case FTS_DNR: /* Warn, continue. */ 183 case FTS_ERR: 184 case FTS_NS: 185 warnx("%s: %s", p->fts_path, strerror(p->fts_errno)); 186 rval = 1; 187 break; 188 default: 189 if (p->fts_statp->st_nlink > 1 && linkchk(p)) 190 break; 191 /* 192 * If listing each file, or a non-directory file was 193 * the root of a traversal, display the total. 194 */ 195 if (listfiles || p->fts_level == FTS_ROOTLEVEL) 196 prtout(howmany(p->fts_statp->st_blocks, blocksize), 197 p->fts_path, hflag); 198 p->fts_parent->fts_number += p->fts_statp->st_blocks; 199 if (cflag) 200 totalblocks += p->fts_statp->st_blocks; 201 } 202 if (errno) 203 err(1, "fts_read"); 204 if (cflag) { 205 prtout((quad_t)howmany(totalblocks, blocksize), "total", hflag); 206 } 207 exit(rval); 208 } 209 210 211 struct links_entry { 212 RB_ENTRY(links_entry) entry; 213 struct links_entry *fnext; 214 int links; 215 dev_t dev; 216 ino_t ino; 217 }; 218 219 int 220 links_cmp(struct links_entry *e1, struct links_entry *e2) 221 { 222 if (e1->dev == e2->dev) { 223 if (e1->ino == e2->ino) 224 return (0); 225 else 226 return (e1->ino < e2->ino ? -1 : 1); 227 } 228 else 229 return (e1->dev < e2->dev ? -1 : 1); 230 } 231 232 RB_HEAD(ltree, links_entry) links = RB_INITIALIZER(&links); 233 234 RB_GENERATE(ltree, links_entry, entry, links_cmp); 235 236 237 int 238 linkchk(FTSENT *p) 239 { 240 static struct links_entry *free_list = NULL; 241 static int stop_allocating = 0; 242 struct links_entry ltmp, *le; 243 struct stat *st; 244 245 st = p->fts_statp; 246 247 ltmp.ino = st->st_ino; 248 ltmp.dev = st->st_dev; 249 250 le = RB_FIND(ltree, &links, <mp); 251 if (le != NULL) { 252 /* 253 * Save memory by releasing an entry when we've seen 254 * all of it's links. 255 */ 256 if (--le->links <= 0) { 257 RB_REMOVE(ltree, &links, le); 258 /* Recycle this node through the free list */ 259 if (stop_allocating) { 260 free(le); 261 } else { 262 le->fnext = free_list; 263 free_list = le; 264 } 265 } 266 return (1); 267 } 268 269 if (stop_allocating) 270 return (0); 271 272 /* Add this entry to the links cache. */ 273 if (free_list != NULL) { 274 /* Pull a node from the free list if we can. */ 275 le = free_list; 276 free_list = le->fnext; 277 } else 278 /* Malloc one if we have to. */ 279 le = malloc(sizeof(struct links_entry)); 280 281 if (le == NULL) { 282 stop_allocating = 1; 283 warnx("No more memory for tracking hard links"); 284 return (0); 285 } 286 287 le->dev = st->st_dev; 288 le->ino = st->st_ino; 289 le->links = st->st_nlink - 1; 290 le->fnext = NULL; 291 292 RB_INSERT(ltree, &links, le); 293 294 return (0); 295 } 296 297 void 298 prtout(quad_t size, char *path, int hflag) 299 { 300 if (!hflag) 301 (void)printf("%lld\t%s\n", (long long)size, path); 302 else { 303 char buf[FMT_SCALED_STRSIZE]; 304 305 if (fmt_scaled(size * 512, buf) == 0) 306 (void)printf("%s\t%s\n", buf, path); 307 else 308 (void)printf("%lld\t%s\n", (long long)size, path); 309 } 310 } 311 312 void 313 usage(void) 314 { 315 316 (void)fprintf(stderr, 317 "usage: du [-a | -s] [-chkrx] [-H | -L | -P] [file ...]\n"); 318 exit(1); 319 } 320