1 /* $OpenBSD: du.c,v 1.33 2022/12/04 23:50:48 cheloha 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 default: 120 usage(); 121 } 122 argc -= optind; 123 argv += optind; 124 125 /* 126 * XXX 127 * Because of the way that fts(3) works, logical walks will not count 128 * the blocks actually used by symbolic links. We rationalize this by 129 * noting that users computing logical sizes are likely to do logical 130 * copies, so not counting the links is correct. The real reason is 131 * that we'd have to re-implement the kernel's symbolic link traversing 132 * algorithm to get this right. If, for example, you have relative 133 * symbolic links referencing other relative symbolic links, it gets 134 * very nasty, very fast. The bottom line is that it's documented in 135 * the man page, so it's a feature. 136 */ 137 if (Hflag) 138 ftsoptions |= FTS_COMFOLLOW; 139 if (Lflag) { 140 ftsoptions &= ~FTS_PHYSICAL; 141 ftsoptions |= FTS_LOGICAL; 142 } 143 144 if (maxdepth == -1) 145 maxdepth = INT_MAX; 146 147 if (!*argv) { 148 argv = save; 149 argv[0] = "."; 150 argv[1] = NULL; 151 } 152 153 if (hflag) 154 blocksize = 512; 155 else if (kflag) 156 blocksize = 1024; 157 else 158 (void)getbsize(¬used, &blocksize); 159 blocksize /= 512; 160 161 if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL) 162 err(1, "fts_open"); 163 164 for (rval = 0; (p = fts_read(fts)) != NULL;) 165 switch (p->fts_info) { 166 case FTS_D: /* Ignore. */ 167 break; 168 case FTS_DP: 169 p->fts_parent->fts_number += 170 p->fts_number += p->fts_statp->st_blocks; 171 if (cflag) 172 totalblocks += p->fts_statp->st_blocks; 173 /* 174 * If listing each directory, or not listing files 175 * or directories and this is post-order of the 176 * root of a traversal, display the total. 177 */ 178 if (p->fts_level <= maxdepth) 179 prtout(howmany(p->fts_number, 180 (unsigned long)blocksize), p->fts_path, 181 hflag); 182 break; 183 case FTS_DC: /* Ignore. */ 184 break; 185 case FTS_DNR: /* Warn, continue. */ 186 case FTS_ERR: 187 case FTS_NS: 188 warnc(p->fts_errno, "%s", p->fts_path); 189 rval = 1; 190 break; 191 default: 192 if (p->fts_statp->st_nlink > 1 && linkchk(p)) 193 break; 194 /* 195 * If listing each file, or a non-directory file was 196 * the root of a traversal, display the total. 197 */ 198 if ((listfiles && p->fts_level <= maxdepth) || 199 p->fts_level == FTS_ROOTLEVEL) 200 prtout(howmany(p->fts_statp->st_blocks, 201 blocksize), p->fts_path, hflag); 202 p->fts_parent->fts_number += p->fts_statp->st_blocks; 203 if (cflag) 204 totalblocks += p->fts_statp->st_blocks; 205 } 206 if (errno) 207 err(1, "fts_read"); 208 if (cflag) { 209 prtout(howmany(totalblocks, blocksize), "total", hflag); 210 } 211 fts_close(fts); 212 exit(rval); 213 } 214 215 216 struct links_entry { 217 RB_ENTRY(links_entry) entry; 218 struct links_entry *fnext; 219 int links; 220 dev_t dev; 221 ino_t ino; 222 }; 223 224 static int 225 links_cmp(struct links_entry *e1, struct links_entry *e2) 226 { 227 if (e1->dev == e2->dev) { 228 if (e1->ino == e2->ino) 229 return (0); 230 else 231 return (e1->ino < e2->ino ? -1 : 1); 232 } 233 else 234 return (e1->dev < e2->dev ? -1 : 1); 235 } 236 237 RB_HEAD(ltree, links_entry) links = RB_INITIALIZER(&links); 238 239 RB_GENERATE_STATIC(ltree, links_entry, entry, links_cmp); 240 241 242 int 243 linkchk(FTSENT *p) 244 { 245 static struct links_entry *free_list = NULL; 246 static int stop_allocating = 0; 247 struct links_entry ltmp, *le; 248 struct stat *st; 249 250 st = p->fts_statp; 251 252 ltmp.ino = st->st_ino; 253 ltmp.dev = st->st_dev; 254 255 le = RB_FIND(ltree, &links, <mp); 256 if (le != NULL) { 257 /* 258 * Save memory by releasing an entry when we've seen 259 * all of it's links. 260 */ 261 if (--le->links <= 0) { 262 RB_REMOVE(ltree, &links, le); 263 /* Recycle this node through the free list */ 264 if (stop_allocating) { 265 free(le); 266 } else { 267 le->fnext = free_list; 268 free_list = le; 269 } 270 } 271 return (1); 272 } 273 274 if (stop_allocating) 275 return (0); 276 277 /* Add this entry to the links cache. */ 278 if (free_list != NULL) { 279 /* Pull a node from the free list if we can. */ 280 le = free_list; 281 free_list = le->fnext; 282 } else 283 /* Malloc one if we have to. */ 284 le = malloc(sizeof(struct links_entry)); 285 286 if (le == NULL) { 287 stop_allocating = 1; 288 warnx("No more memory for tracking hard links"); 289 return (0); 290 } 291 292 le->dev = st->st_dev; 293 le->ino = st->st_ino; 294 le->links = st->st_nlink - 1; 295 le->fnext = NULL; 296 297 RB_INSERT(ltree, &links, le); 298 299 return (0); 300 } 301 302 void 303 prtout(int64_t size, char *path, int hflag) 304 { 305 if (!hflag) 306 (void)printf("%lld\t%s\n", size, path); 307 else { 308 char buf[FMT_SCALED_STRSIZE]; 309 310 if (fmt_scaled(size * 512, buf) == 0) 311 (void)printf("%s\t%s\n", buf, path); 312 else 313 (void)printf("%lld\t%s\n", size, path); 314 } 315 } 316 317 void 318 usage(void) 319 { 320 321 (void)fprintf(stderr, 322 "usage: du [-achkrsx] [-H | -L | -P] [-d depth] [file ...]\n"); 323 exit(1); 324 } 325