[2.4 patch] fix O(N^2) dquot sync behaviour

[Stephen C. Tweedie]

Hi,

On Thu, 2004-04-22 at 16:18, Jan Kara wrote:

>   when there are lots of dirty dquots the vfs_quota_sync() is too slow
> (it has O(N^2) behaviour). Attached patch implements list of dirty
> dquots for each superblock and quota type. Using this lists sync is
> trivially linear. Attached patch is against 2.6.5 with journalled quota
> and previous patch for hash table size. Please apply.

The O(N^2) behaviour is present on 2.4 too, but fortunately there's a
simple way to bring that down to O(N) without the complexity of adding
new lists and locking.  This patch simply rotates the dquot list-head
after each dquot write, so that the next scan walks the list starting
after the entry just processed.

For 40,000 dirty dquots, this brings sync time from 7 minutes and 50
seconds down to 0.8 seconds. :-)  On 2.4, we have BKL while doing this
list manipulation.  Jan Kara has acked this; please apply.

Cheers,
 Stephen

--- linux-2.4/fs/dquot.c.=K0000=.orig
+++ linux-2.4/fs/dquot.c
@@ -397,6 +397,10 @@ restart:
 			wait_on_dquot(dquot);
 		if (dquot_dirty(dquot))
 			sb->dq_op->write_dquot(dquot);
+		/* Move the inuse_list head pointer to just after the
+		 * current dquot, so that we'll restart the list walk
+		 * after this point on the next pass. */
+		list_move(&inuse_list, &dquot->dq_inuse);
 		dqput(dquot);
 		goto restart;
 	}