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

From: Stephen C. Tweedie
Date: Fri Apr 23 2004 - 13:38:58 EST


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.


--- linux-2.4/fs/dquot.c.=K0000=.orig
+++ linux-2.4/fs/dquot.c
@@ -397,6 +397,10 @@ restart:
if (dquot_dirty(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);
goto restart;