>Number:         23725
>Category:       bin
>Synopsis:       possible quotacheck enhancement
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    bin-bug-people
>State:          open
>Class:          change-request
>Submitter-Id:   net
>Arrival-Date:   Fri Dec 12 12:14:00 UTC 2003
>Closed-Date:
>Last-Modified:
>Originator:     Robert Elz
>Release:        NetBSD 1.6X   (sources -current as of yesterday)
>Organization:
	Prince of Songkla University
>Environment:
System: NetBSD jade.coe.psu.ac.th 1.6X NetBSD 1.6X (JADE) #17: Wed Sep 24 20:25:35 ICT 2003 kre@jade.coe.psu.ac.th:/usr/src/real-sys/arch/i386/compile/JADE i386
Architecture: i386
Machine: i386
>Description:
	quotacheck can run very slowly (take a long time, an extremely
	long time) if run on a filesystem that happens to have a file
	allocated to a uid (or gid if using group quotas) that is large.

	I believe (from past experience) that the principle cause of this
	is its habit of doing a seek forward, of one dqblk size, for every
	record it does not need to write (seek, to preserve holes in the
	quota file, is certainly correct, but one seek per irrelevant uid
	gets very costly, very quickly).

	When I have fixed this previously, I've simply remembered a seek
	is needed, and done an appropriate seek before the next write.

	This time I got ambitious.

>How-To-Repeat:
	Add (user or group) quotas to a filesystem.  Create a file on
	the filesystem (give it a few blocks for run, though this isn't
	strictly needed)
		chown 10000000 filename
	(use chgrp of course if using group quotas).

	Run quotacheck, and wait, and wait...   (run it in background).

	When you get very bored, bring it to foreground, and do a SIGINFO
	from the keyboard (have ^T or something set for that) - notice
	that quotacheck says nothing, though the man page promises it
	will.

>Fix:
	****** WARNING *******

	This fix has been compiled, but tested only on my kre model virtual
	processor (model psycho 7), using the revolutionary new virtual
	filestore... (loses data all the time unfortunately)

	****** WARNING *******

	The patch below does several things.   It implements the
	seek no more than once per write enhancement.   It avoids
	looping over (perhaps 2^32 uids, when only 2 or 3 (or 2 or
	3 hundred perhaps) are actually in use (but they just happen
	to be 0, and 2^32 - 1)   A new option ('q') is added, that
	will cause quotacheck to skip reading the parts of the quota
	file that it has no reason to believe should exist (user not
	in passwd file (group not in group file) and owns no files
	on the filesystem) - however this does mean that if the quota
	file believes that this user (group) which owns nothing, and
	has no name, is listed as owning something, then with -q that
	will not be corrected (without -q the entire quota file needs
	to be read, to locate any entries that record usage when they
	shouldn't).   It also implements SIGINFO handling in the slow
	part of quotacheck - actually updating the quota file (reading
	the filesystem takes usually minutes at most, doing the calculations
	happens in parallel, but is only going to be seconds - updating
	the quota file can take hours...)

	This patch is for use only by someone willing to wreck their
	quota file (so dump it to text before trying this) with the
	aim of helping to produce a better system - unfortunately, I
	have no current systems using quotas to try it on (and am much
	too lazy to set one up).

	I believe it has one bug - bad things are likely if uid 2^32-1
	actually owns files (or exists in the password file).  (same for
	groups) (assuming long is 32 bits, on a LP64 system, all should
	be OK, as uids, and gids, don't ever get near 2^64-1 there).

	If someone decides to test this, please let me know how you get on.

--- quotacheck.c	2003-08-07 23:24:53.000000000 +0700
+++ quotacheck-new.c	2003-12-12 18:44:56.000000000 +0700
@@ -115,8 +115,9 @@
 static int	aflag;		/* all file systems */
 static int	gflag;		/* check group quotas */
 static int	uflag;		/* check user quotas */
 static int	vflag;		/* verbose */
+static int	qflag;		/* quick but untidy mode */
 static int	fi;		/* open disk file descriptor */
 static u_long	highid[MAXQUOTAS];/* highest addid()'ed identifier per type */
 static int needswap;	/* FS is in swapped order */
 static int got_siginfo = 0; /* got a siginfo signal */
@@ -128,13 +129,15 @@
 static void *needchk __P((struct fstab *));
 static int chkquota __P((const char *, const char *, const char *, void *,
     pid_t *));
 static int update __P((const char *, const char *, int));
+static u_long skipforward __P((u_long, u_long, FILE *));
 static int oneof __P((const char *, char *[], int));
 static int getquotagid __P((void));
 static int hasquota __P((struct fstab *, int, char **));
 static struct fileusage *lookup __P((u_long, int));
 static struct fileusage *addid __P((u_long, int, const char *));
+static u_long subsequent __P((u_long, int)); 
 static union dinode *getnextinode __P((ino_t));
 static void setinodebuf __P((ino_t));
 static void freeinodebuf __P((void));
 static void bread __P((daddr_t, char *, long));
@@ -157,9 +160,9 @@
 	const char *name;
 	int ch;
 
 	errs = maxrun = 0;
-	while ((ch = getopt(argc, argv, "aguvdl:")) != -1) {
+	while ((ch = getopt(argc, argv, "aguvqdl:")) != -1) {
 		switch(ch) {
 		case 'a':
 			aflag++;
 			break;
@@ -171,8 +174,11 @@
 			break;
 		case 'u':
 			uflag++;
 			break;
+		case 'q':
+			qflag++;
+			break;
 		case 'v':
 			vflag++;
 			break;
 		case 'l':
@@ -416,9 +422,10 @@
 	int type;
 {
 	struct fileusage *fup;
 	FILE *qfi, *qfo;
-	u_long id, lastid;
+	u_long id, lastid, nextid;
+	int need_seek;
 	struct dqblk dqbuf;
 	static int warned = 0;
 	static struct dqblk zerodqbuf;
 	static struct fileusage zerofileusage;
@@ -449,18 +456,33 @@
 		warned++;
 		(void)printf("*** Warning: %s\n",
 		    "Quotas are not compiled into this kernel");
 	}
-	for (lastid = highid[type], id = 0; id <= lastid; id++) {
+	need_seek = 1;
+	for (lastid = highid[type], id = 0; id <= lastid; id = nextid) {
 		if (fread((char *)&dqbuf, sizeof(struct dqblk), 1, qfi) == 0)
 			dqbuf = zerodqbuf;
 		if ((fup = lookup(id, type)) == 0)
 			fup = &zerofileusage;
+
+		nextid = subsequent(id, type);
+		if (nextid != id + 1)
+			nextid = skipforward(id, nextid, qfi);
+
+		if (got_siginfo) {
+			fprintf(stderr,
+			    "%s: updating %s quotas for id=%ld (%s)\n", fsname,
+			    qfextension[type < MAXQUOTAS ? type : MAXQUOTAS],
+			    id, fup->fu_name);
+			got_siginfo = 0;
+		}
 		if (dqbuf.dqb_curinodes == fup->fu_curinodes &&
 		    dqbuf.dqb_curblocks == fup->fu_curblocks) {
+#if 0		/** Why? **/
 			fup->fu_curinodes = 0;
 			fup->fu_curblocks = 0;
-			(void) fseek(qfo, (long)sizeof(struct dqblk), 1);
+#endif
+			need_seek = 1;
 			continue;
 		}
 		if (vflag) {
 			if (aflag)
@@ -487,13 +509,23 @@
 		    fup->fu_curblocks >= dqbuf.dqb_isoftlimit)
 			dqbuf.dqb_itime = 0;
 		dqbuf.dqb_curinodes = fup->fu_curinodes;
 		dqbuf.dqb_curblocks = fup->fu_curblocks;
+
+		if (need_seek) {
+			(void) fseeko(qfo, (off_t)id * sizeof(struct dqblk),
+			    SEEK_SET);
+			need_seek = 0;
+		}
 		(void) fwrite((char *)&dqbuf, sizeof(struct dqblk), 1, qfo);
+
 		(void) quotactl(fsname, QCMD(Q_SETUSE, type), id,
 		    (caddr_t)&dqbuf);
+
+#if 0		/** Why? **/
 		fup->fu_curinodes = 0;
 		fup->fu_curblocks = 0;
+#endif
 	}
 	(void) fclose(qfi);
 	(void) fflush(qfo);
 	(void) ftruncate(fileno(qfo),
@@ -501,8 +533,40 @@
 	(void) fclose(qfo);
 	return (0);
 }
 
+u_long
+skipforward(cur, to, qfi)
+	u_long cur, to;
+	FILE *qfi;
+{
+	struct dqblk dqbuf;
+
+	if (qflag) {
+		(void) fseeko(qfi, (off_t)to * sizeof(struct dqblk), SEEK_SET);
+		return (to);
+	}
+
+	while (++cur < to) {
+		/*
+		 * if EOF occurs, nothing left to read, we're done
+		 */
+		if (fread((char *)&dqbuf, sizeof(struct dqblk), 1, qfi) == 0)
+			return (to);
+
+		/*
+		 * If we find an entry that shows usage, before the next
+		 * id that has actual usage, we have to stop here, so the
+		 * incorrect entry can be corrected in the file
+		 */
+		if (dqbuf.dqb_curinodes != 0 || dqbuf.dqb_curblocks != 0) {
+			(void)fseek(qfi, -(long)sizeof(struct dqblk), SEEK_CUR);
+			return (cur);
+		}
+	}
+	return (to);
+}
+
 /*
  * Check to see if target appears in list of size cnt.
  */
 static int
@@ -624,8 +688,34 @@
 		(void)sprintf(fup->fu_name, "%lu", id);
 	return (fup);
 }
 
+static u_long
+subsequent(id, type)
+	u_long id;
+	int type;
+{
+	struct fileusage *fup, **iup, **cup;
+	u_long next, offset;
+
+	next = highid[type] + 1;
+	offset = 0;
+	cup = iup = &fuhead[type][id & (FUHASH-1)];
+	do {
+		++offset;
+		if (++cup >= &fuhead[type][FUHASH])
+			cup = &fuhead[type][0];
+		for (fup = *cup; fup != 0; fup = fup->fu_next) {
+			if (fup->fu_id > id && fup->fu_id <= id + offset)
+				return (fup->fu_id);
+			if (fup->fu_id > id && fup->fu_id < next)
+				next = fup->fu_id;
+		}
+	} while (cup != iup);
+
+	return next;
+}
+
 /*
  * Special purpose version of ginode used to optimize first pass
  * over all the inodes in numerical order.
  */
@@ -755,5 +845,4 @@
 infohandler(int sig)
 {
 	got_siginfo = 1;
 } 
-
--- quotacheck.8	2003-08-07 23:24:52.000000000 +0700
+++ quotacheck-new.8	2003-12-12 18:38:24.000000000 +0700
@@ -41,13 +41,15 @@
 .Sh SYNOPSIS
 .Nm
 .Op Fl g
 .Op Fl u
+.Op Fl q
 .Op Fl v
 .Ar filesystem Ar ...
 .Nm
 .Op Fl g
 .Op Fl u
+.Op Fl q
 .Op Fl v
 .Fl a
 .Sh DESCRIPTION
 .Nm
@@ -81,11 +83,20 @@
 .It Fl u
 Only user quotas listed in
 .Pa /etc/fstab
 are to be checked.
+.It Fl q
+.Nm
+runs more quickly,
+particularly on systems with sparse user id usage,
+but fails to correct quotas for users [groups]
+not in the system user [group] database,
+and owning no files on the filesystem,
+if the quota file incorrectly believes that they do.
 .It Fl v
 .Nm
-reports discrepancies between the
+is more verbose,
+and reports corrected discrepancies between the
 calculated and recorded disk quotas.
 .El
 .Pp
 Specifying both
>Release-Note:
>Audit-Trail:
>Unformatted: