1 /* $OpenBSD: du.c,v 1.32 2016/08/24 03:13:45 guenther 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 <limits.h> 44 #include <stdio.h> 45 #include <stdlib.h> 46 #include <string.h> 47 #include <sys/tree.h> 48 #include <unistd.h> 49 #include <util.h> 50 51 52 int linkchk(FTSENT *); 53 void prtout(int64_t, char *, int); 54 void usage(void); 55 56 int 57 main(int argc, char *argv[]) 58 { 59 FTS *fts; 60 FTSENT *p; 61 long blocksize; 62 int64_t totalblocks; 63 int ftsoptions, listfiles, maxdepth; 64 int Hflag, Lflag, cflag, hflag, kflag; 65 int ch, notused, rval; 66 char **save; 67 const char *errstr; 68 69 if (pledge("stdio rpath", NULL) == -1) 70 err(1, "pledge"); 71 72 save = argv; 73 Hflag = Lflag = cflag = hflag = kflag = listfiles = 0; 74 totalblocks = 0; 75 ftsoptions = FTS_PHYSICAL; 76 maxdepth = -1; 77 while ((ch = getopt(argc, argv, "HLPacd:hkrsx")) != -1) 78 switch (ch) { 79 case 'H': 80 Hflag = 1; 81 Lflag = 0; 82 break; 83 case 'L': 84 Lflag = 1; 85 Hflag = 0; 86 break; 87 case 'P': 88 Hflag = Lflag = 0; 89 break; 90 case 'a': 91 listfiles = 1; 92 break; 93 case 'c': 94 cflag = 1; 95 break; 96 case 'd': 97 maxdepth = strtonum(optarg, 0, INT_MAX, &errstr); 98 if (errstr) { 99 warnx("max depth %s: %s", optarg, errstr); 100 usage(); 101 } 102 break; 103 case 'h': 104 hflag = 1; 105 kflag = 0; 106 break; 107 case 'k': 108 kflag = 1; 109 hflag = 0; 110 break; 111 case 's': 112 maxdepth = 0; 113 break; 114 case 'r': 115 break; 116 case 'x': 117 ftsoptions |= FTS_XDEV; 118 break; 119 case '?': 120 default: 121 usage(); 122 } 123 argc -= optind; 124 argv += optind; 125 126 /* 127 * XXX 128 * Because of the way that fts(3) works, logical walks will not count 129 * the blocks actually used by symbolic links. We rationalize this by 130 * noting that users computing logical sizes are likely to do logical 131 * copies, so not counting the links is correct. The real reason is 132 * that we'd have to re-implement the kernel's symbolic link traversing 133 * algorithm to get this right. If, for example, you have relative 134 * symbolic links referencing other relative symbolic links, it gets 135 * very nasty, very fast. The bottom line is that it's documented in 136 * the man page, so it's a feature. 137 */ 138 if (Hflag) 139 ftsoptions |= FTS_COMFOLLOW; 140 if (Lflag) { 141 ftsoptions &= ~FTS_PHYSICAL; 142 ftsoptions |= FTS_LOGICAL; 143 } 144 145 if (maxdepth == -1) 146 maxdepth = INT_MAX; 147 148 if (!*argv) { 149 argv = save; 150 argv[0] = "."; 151 argv[1] = NULL; 152 } 153 154 if (hflag) 155 blocksize = 512; 156 else if (kflag) 157 blocksize = 1024; 158 else 159 (void)getbsize(¬used, &blocksize); 160 blocksize /= 512; 161 162 if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 163 err(1, "fts_open"); 164 165 for (rval = 0; (p = fts_read(fts)) != NULL;) 166 switch (p->fts_info) { 167 case FTS_D: /* Ignore. */ 168 break; 169 case FTS_DP: 170 p->fts_parent->fts_number += 171 p->fts_number += p->fts_statp->st_blocks; 172 if (cflag) 173 totalblocks += p->fts_statp->st_blocks; 174 /* 175 * If listing each directory, or not listing files 176 * or directories and this is post-order of the 177 * root of a traversal, display the total. 178 */ 179 if (p->fts_level <= maxdepth) 180 prtout(howmany(p->fts_number, 181 (unsigned long)blocksize), p->fts_path, 182 hflag); 183 break; 184 case FTS_DC: /* Ignore. */ 185 break; 186 case FTS_DNR: /* Warn, continue. */ 187 case FTS_ERR: 188 case FTS_NS: 189 warnc(p->fts_errno, "%s", p->fts_path); 190 rval = 1; 191 break; 192 default: 193 if (p->fts_statp->st_nlink > 1 && linkchk(p)) 194 break; 195 /* 196 * If listing each file, or a non-directory file was 197 * the root of a traversal, display the total. 198 */ 199 if ((listfiles && p->fts_level <= maxdepth) || 200 p->fts_level == FTS_ROOTLEVEL) 201 prtout(howmany(p->fts_statp->st_blocks, 202 blocksize), p->fts_path, hflag); 203 p->fts_parent->fts_number += p->fts_statp->st_blocks; 204 if (cflag) 205 totalblocks += p->fts_statp->st_blocks; 206 } 207 if (errno) 208 err(1, "fts_read"); 209 if (cflag) { 210 prtout(howmany(totalblocks, blocksize), "total", hflag); 211 } 212 fts_close(fts); 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 static int 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_STATIC(ltree, links_entry, entry, links_cmp); 241 242 243 int 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 304 prtout(int64_t size, char *path, int hflag) 305 { 306 if (!hflag) 307 (void)printf("%lld\t%s\n", size, path); 308 else { 309 char buf[FMT_SCALED_STRSIZE]; 310 311 if (fmt_scaled(size * 512, buf) == 0) 312 (void)printf("%s\t%s\n", buf, path); 313 else 314 (void)printf("%lld\t%s\n", size, path); 315 } 316 } 317 318 void 319 usage(void) 320 { 321 322 (void)fprintf(stderr, 323 "usage: du [-achkrsx] [-H | -L | -P] [-d depth] [file ...]\n"); 324 exit(1); 325 } 326