18103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall/*	$NetBSD: du.c,v 1.33 2008/07/30 22:03:40 dsl Exp $	*/
28103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
38103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall/*
48103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * Copyright (c) 1989, 1993, 1994
58103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *	The Regents of the University of California.  All rights reserved.
68103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *
78103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * This code is derived from software contributed to Berkeley by
88103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * Chris Newcomb.
98103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *
108103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * Redistribution and use in source and binary forms, with or without
118103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * modification, are permitted provided that the following conditions
128103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * are met:
138103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * 1. Redistributions of source code must retain the above copyright
148103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *    notice, this list of conditions and the following disclaimer.
158103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * 2. Redistributions in binary form must reproduce the above copyright
168103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *    notice, this list of conditions and the following disclaimer in the
178103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *    documentation and/or other materials provided with the distribution.
188103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * 3. Neither the name of the University nor the names of its contributors
198103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *    may be used to endorse or promote products derived from this software
208103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *    without specific prior written permission.
218103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall *
228103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
238103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
248103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
258103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
268103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
278103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
288103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
298103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
308103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
318103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
328103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall * SUCH DAMAGE.
338103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall */
348103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
358103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <sys/cdefs.h>
368103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#ifndef lint
378103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall__COPYRIGHT("@(#) Copyright (c) 1989, 1993, 1994\
388103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall The Regents of the University of California.  All rights reserved.");
398103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#endif /* not lint */
408103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
418103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#ifndef lint
428103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#if 0
438103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallstatic char sccsid[] = "@(#)du.c	8.5 (Berkeley) 5/4/95";
448103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#else
458103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall__RCSID("$NetBSD: du.c,v 1.33 2008/07/30 22:03:40 dsl Exp $");
468103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#endif
478103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#endif /* not lint */
488103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
498103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <sys/types.h>
508103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <sys/stat.h>
518103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
528103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <dirent.h>
538103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <err.h>
548103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <errno.h>
558103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <fts.h>
568103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <util.h>
578103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <stdio.h>
588103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <stdlib.h>
598103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <string.h>
608103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <unistd.h>
618103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#include <limits.h>
628103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
638103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallint	linkchk(dev_t, ino_t);
648103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallvoid	prstat(const char *, int64_t);
658103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallvoid	usage(void);
668103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
678103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumralllong blocksize;
688103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
698103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall#define howmany(x, y)   (((x)+((y)-1))/(y))
708103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
718103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallint
728103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumralldu_main(int argc, char *argv[])
738103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall{
748103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	FTS *fts;
758103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	FTSENT *p;
768103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	int64_t totalblocks;
778103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	int ftsoptions, listfiles;
788103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	int depth;
798103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	int Hflag, Lflag, aflag, ch, cflag, dflag, gkmflag, nflag, rval, sflag;
808103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	const char *noargv[2];
818103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
828103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	Hflag = Lflag = aflag = cflag = dflag = gkmflag = sflag = 0;
838103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	totalblocks = 0;
848103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	ftsoptions = FTS_PHYSICAL;
858103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	depth = INT_MAX;
868103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	while ((ch = getopt(argc, argv, "HLPacd:ghkmnrsx")) != -1)
878103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		switch (ch) {
888103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'H':
898103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			Hflag = 1;
908103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			Lflag = 0;
918103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
928103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'L':
938103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			Lflag = 1;
948103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			Hflag = 0;
958103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
968103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'P':
978103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			Hflag = Lflag = 0;
988103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
998103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'a':
1008103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			aflag = 1;
1018103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1028103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'c':
1038103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			cflag = 1;
1048103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1058103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'd':
1068103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			dflag = 1;
1078103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			depth = atoi(optarg);
1088103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			if (depth < 0 || depth > SHRT_MAX) {
1098103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall				warnx("invalid argument to option d: %s",
1108103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall					optarg);
1118103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall				usage();
1128103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			}
1138103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1148103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'g':
1158103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			blocksize = 1024 * 1024 * 1024;
1168103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			gkmflag = 1;
1178103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1188103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'k':
1198103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			blocksize = 1024;
1208103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			gkmflag = 1;
1218103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1228103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'm':
1238103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			blocksize = 1024 * 1024;
1248103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			gkmflag = 1;
1258103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1268103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'r':
1278103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1288103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 's':
1298103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			sflag = 1;
1308103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1318103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case 'x':
1328103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			ftsoptions |= FTS_XDEV;
1338103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1348103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case '?':
1358103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		default:
1368103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			usage();
1378103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		}
1388103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	argc -= optind;
1398103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	argv += optind;
1408103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
1418103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	/*
1428103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * XXX
1438103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * Because of the way that fts(3) works, logical walks will not count
1448103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * the blocks actually used by symbolic links.  We rationalize this by
1458103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * noting that users computing logical sizes are likely to do logical
1468103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * copies, so not counting the links is correct.  The real reason is
1478103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * that we'd have to re-implement the kernel's symbolic link traversing
1488103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * algorithm to get this right.  If, for example, you have relative
1498103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * symbolic links referencing other relative symbolic links, it gets
1508103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * very nasty, very fast.  The bottom line is that it's documented in
1518103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * the man page, so it's a feature.
1528103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 */
1538103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (Hflag)
1548103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		ftsoptions |= FTS_COMFOLLOW;
1558103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (Lflag) {
1568103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		ftsoptions &= ~FTS_PHYSICAL;
1578103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		ftsoptions |= FTS_LOGICAL;
1588103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	}
1598103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
1608103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	listfiles = 0;
1618103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (aflag) {
1628103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		if (sflag || dflag)
1638103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			usage();
1648103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		listfiles = 1;
1658103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	} else if (sflag) {
1668103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		if (dflag)
1678103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			usage();
1688103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		depth = 0;
1698103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	}
1708103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
1718103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (!*argv) {
1728103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		noargv[0] = ".";
1738103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		noargv[1] = NULL;
1748103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		argv = __UNCONST(noargv);
1758103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	}
1768103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
1778103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (!gkmflag)
1788103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		blocksize = 512;
1798103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	blocksize /= 512;
1808103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
1818103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if ((fts = fts_open(argv, ftsoptions, NULL)) == NULL)
1828103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		err(1, "fts_open `%s'", *argv);
1838103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
1848103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	for (rval = 0; (p = fts_read(fts)) != NULL;) {
1858103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		switch (p->fts_info) {
1868103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case FTS_D:			/* Ignore. */
1878103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
1888103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case FTS_DP:
1898103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			p->fts_parent->fts_number +=
1908103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			    p->fts_number += p->fts_statp->st_blocks;
1918103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			if (cflag)
1928103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall				totalblocks += p->fts_statp->st_blocks;
1938103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			/*
1948103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			 * If listing each directory, or not listing files
1958103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			 * or directories and this is post-order of the
1968103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			 * root of a traversal, display the total.
1978103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			 */
1988103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			if (p->fts_level <= depth
1998103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			    || (!listfiles && !p->fts_level))
2008103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall				prstat(p->fts_path, p->fts_number);
2018103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
2028103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case FTS_DC:			/* Ignore. */
2038103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
2048103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case FTS_DNR:			/* Warn, continue. */
2058103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case FTS_ERR:
2068103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		case FTS_NS:
2078103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			warnx("%s: %s", p->fts_path, strerror(p->fts_errno));
2088103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			rval = 1;
2098103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			break;
2108103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		default:
2118103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			if (p->fts_statp->st_nlink > 1 &&
2128103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			    linkchk(p->fts_statp->st_dev, p->fts_statp->st_ino))
2138103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall				break;
2148103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			/*
2158103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			 * If listing each file, or a non-directory file was
2168103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			 * the root of a traversal, display the total.
2178103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			 */
2188103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			if (listfiles || !p->fts_level)
2198103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall				prstat(p->fts_path, p->fts_statp->st_blocks);
2208103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			p->fts_parent->fts_number += p->fts_statp->st_blocks;
2218103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			if (cflag)
2228103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall				totalblocks += p->fts_statp->st_blocks;
2238103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		}
2248103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	}
2258103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (errno)
2268103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		err(1, "fts_read");
2278103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (cflag)
2288103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		prstat("total", totalblocks);
2298103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	exit(rval);
2308103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall}
2318103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2328103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallvoid
2338103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallprstat(const char *fname, int64_t blocks)
2348103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall{
2358103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	(void)printf("%lld\t%s\n",
2368103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	    (long long)howmany(blocks, (int64_t)blocksize),
2378103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	    fname);
2388103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall}
2398103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2408103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallint
2418103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumralllinkchk(dev_t dev, ino_t ino)
2428103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall{
2438103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	static struct entry {
2448103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		dev_t	dev;
2458103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		ino_t	ino;
2468103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	} *htable;
2478103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	static int htshift;  /* log(allocated size) */
2488103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	static int htmask;   /* allocated size - 1 */
2498103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	static int htused;   /* 2*number of insertions */
2508103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	static int sawzero;  /* Whether zero is in table or not */
2518103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	int h, h2;
2528103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	uint64_t tmp;
2538103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	/* this constant is (1<<64)/((1+sqrt(5))/2)
2548103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 * aka (word size)/(golden ratio)
2558103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	 */
2568103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	const uint64_t HTCONST = 11400714819323198485ULL;
2578103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	const int HTBITS = CHAR_BIT * sizeof(tmp);
2588103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2598103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	/* Never store zero in hashtable */
2608103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (dev == 0 && ino == 0) {
2618103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		h = sawzero;
2628103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		sawzero = 1;
2638103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		return h;
2648103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	}
2658103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2668103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	/* Extend hash table if necessary, keep load under 0.5 */
2678103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	if (htused<<1 >= htmask) {
2688103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		struct entry *ohtable;
2698103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2708103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		if (!htable)
2718103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			htshift = 10;   /* starting hashtable size */
2728103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		else
2738103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			htshift++;   /* exponential hashtable growth */
2748103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2758103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		htmask  = (1 << htshift) - 1;
2768103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		htused = 0;
2778103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2788103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		ohtable = htable;
2798103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		htable = calloc(htmask+1, sizeof(*htable));
2808103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		if (!htable)
2818103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			err(1, "calloc");
2828103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2838103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		/* populate newly allocated hashtable */
2848103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		if (ohtable) {
2858103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			int i;
2868103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			for (i = 0; i <= htmask>>1; i++)
2878103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall				if (ohtable[i].ino || ohtable[i].dev)
2888103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall					linkchk(ohtable[i].dev, ohtable[i].ino);
2898103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			free(ohtable);
2908103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		}
2918103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	}
2928103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
2938103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	/* multiplicative hashing */
2948103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	tmp = dev;
2958103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	tmp <<= HTBITS>>1;
2968103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	tmp |=  ino;
2978103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	tmp *= HTCONST;
2988103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	h  = tmp >> (HTBITS - htshift);
2998103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	h2 = 1 | ( tmp >> (HTBITS - (htshift<<1) - 1)); /* must be odd */
3008103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
3018103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	/* open address hashtable search with double hash probing */
3028103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	while (htable[h].ino || htable[h].dev) {
3038103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		if ((htable[h].ino == ino) && (htable[h].dev == dev))
3048103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall			return 1;
3058103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		h = (h + h2) & htmask;
3068103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	}
3078103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
3088103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	/* Insert the current entry into hashtable */
3098103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	htable[h].dev = dev;
3108103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	htable[h].ino = ino;
3118103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	htused++;
3128103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	return 0;
3138103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall}
3148103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
3158103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallvoid
3168103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrallusage(void)
3178103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall{
3188103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall
3198103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	(void)fprintf(stderr,
3208103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall		"usage: du [-H | -L | -P] [-a | -d depth | -s] [-cgkmrx] [file ...]\n");
3218103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall	exit(1);
3228103e9148378fb8879e3bc7d8504d267c2d9daa9Ken Sumrall}
323