tux3: Try to create directories in less congested block groups

Try to create directories in less congested block groups. Choose a congestion
threshold based on directory depth (in root or not) and volume fullness. For
deeper directories and fuller volumes, accept fuller groups for the inode
number goal. Check a limited number of groups to find a good fit, otherwise
just use the extrapolated inum goal.

Signed-off-by: Daniel Phillips <d.phillips@partner.samsung.com>
Signed-off-by: OGAWA Hirofumi <hirofumi@mail.parknet.co.jp>

4 files changed, 81 insertions, 14 deletions

diff --git a/fs/tux3/Makefile b/fs/tux3/Makefile
index f5ceaea8dbf6ee..36233d8c309bf7 100644
--- a/fs/tux3/Makefile
+++ b/fs/tux3/Makefile
@@ -8,8 +8,8 @@ clean:
 else
 obj-$(CONFIG_TUX3) += tux3.o
 tux3-objs += balloc.o btree.o buffer.o commit.o dir.o dleaf.o \
-	filemap.o iattr.o ileaf.o inode.o log.o namei.o orphan.o replay.o \
-	super.o utility.o writeback.o xattr.o
+	filemap.o iattr.o ileaf.o inode.o log.o namei.o orphan.o policy.o \
+	replay.o super.o utility.o writeback.o xattr.o
 EXTRA_CFLAGS += -Werror -std=gnu99 -Wno-declaration-after-statement
 #EXTRA_CFLAGS += -DTUX3_FLUSHER=TUX3_FLUSHER_SYNC
 #EXTRA_CFLAGS += -DTUX3_FLUSHER=TUX3_FLUSHER_ASYNC_OWN
diff --git a/fs/tux3/dir.c b/fs/tux3/dir.c
index dc8133c83e8f9d..0000bbd7df3b38 100644
--- a/fs/tux3/dir.c
+++ b/fs/tux3/dir.c
@@ -222,18 +222,7 @@ int tux_create_dirent(struct inode *dir, const struct qstr *qstr,
 	entry = bufdata(buffer) + (where & sb->blockmask);
 
 	if (inum == TUX_INVALID_INO) {
-		enum { guess_filesize = 1 << 13, guess_dirsize = 50 * guess_filesize };
-		enum { guess_dirent_size = 24, cluster = 32 };
-		enum { file_factor = guess_filesize / guess_dirent_size };
-		enum { dir_factor = guess_dirsize / guess_dirent_size };
-
-		int is_dir = S_ISDIR(inode->i_mode);
-		unsigned factor = is_dir ? dir_factor : file_factor;
-		inum_t next = sb->nextinum; /* FIXME: racy */
-		inum_t base = max(tux_inode(dir)->inum + 1, (inum_t)TUX_NORMAL_INO);
-		inum_t guess = base + ((factor * where) >> sb->blockbits);
-		inum_t goal = (is_dir || abs64(next - guess) > cluster) ? guess : next;
-		trace("'%.*s' base = 0x%Lx, guess = 0x%Lx, goal = 0x%Lx", len, name, base, guess, goal);
+		inum_t goal = policy_inum(dir, where, inode);
 
 		err = tux_assign_inum(inode, goal);
 		if (err)
diff --git a/fs/tux3/policy.c b/fs/tux3/policy.c
new file mode 100644
index 00000000000000..0e146c4c57b192
--- /dev/null
+++ b/fs/tux3/policy.c
@@ -0,0 +1,75 @@
+/*
+ * Allocation policy of inum and block
+ */
+
+#include "tux3.h"
+
+//#define POLICY_LINEAR
+
+#ifndef POLICY_LINEAR
+/*
+ * Want to spread out directories more at top level. How much more is
+ * a wild guess. When parent is root, put each in a completely empty
+ * block group. Flaw: top level mount point dirs are normally empty
+ * so no other dirs will be created in that group. So relax this when
+ * volume is more than XX used.
+ */
+static unsigned policy_mkdir_ideal(struct sb *sb, unsigned depth)
+{
+	unsigned groupsize = 1 << sb->groupbits;
+	block_t used = sb->volblocks - sb->freeblocks;
+	int age = (used >= (1 << 15)) + (used >= (1 << 18));
+	unsigned ideal[3][2] = {
+		{ 0, groupsize / 8 },
+		{ groupsize / 16, groupsize / 2 },
+		{ groupsize, groupsize },
+	};
+
+	return ideal[age][depth];
+}
+
+/*
+ * Policy to choice inum for creating directory entry.
+ */
+inum_t policy_inum(struct inode *dir, loff_t where, struct inode *inode)
+{
+	enum { guess_filesize = 1 << 13, guess_dirsize = 50 * guess_filesize };
+	enum { guess_dirent_size = 24, cluster = 32 };
+	enum { file_factor = guess_filesize / guess_dirent_size };
+	enum { dir_factor = guess_dirsize / guess_dirent_size };
+
+	struct sb *sb = tux_sb(dir->i_sb);
+	int is_dir = S_ISDIR(inode->i_mode);
+	unsigned factor = is_dir ? dir_factor : file_factor;
+	inum_t next = sb->nextinum; /* FIXME: racy */
+	inum_t parent = tux_inode(dir)->inum;
+	inum_t base = max(parent + 1, (inum_t)TUX_NORMAL_INO);
+	inum_t guess = base + ((factor * where) >> sb->blockbits);
+	inum_t goal = (is_dir || abs64(next - guess) > cluster) ? guess : next;
+
+	if (is_dir) {
+		enum { policy_mkdir_range = 10 };
+		unsigned depth = parent != TUX_ROOTDIR_INO;
+		unsigned ideal = policy_mkdir_ideal(sb, depth);
+		unsigned groupbits = sb->groupbits;
+		block_t group = goal >> groupbits;
+		if (countmap_used(sb, group) > ideal) {
+			block_t top = sb->volblocks >> groupbits;
+			block_t limit = min(group + policy_mkdir_range, top);
+			for (++group; group < limit; group++) {
+				if (countmap_used(sb, group) <= ideal) {
+					goal = group << sb->groupbits;
+					break;
+				}
+			}
+		}
+	}
+
+	return goal;
+}
+#else /* POLICY_LINEAR */
+inum_t policy_inum(struct inode *dir, loff_t where, struct inode *inode)
+{
+	return tux_sb(dir->i_sb)->nextinum;
+}
+#endif /* POLICY_LINEAR */
diff --git a/fs/tux3/tux3.h b/fs/tux3/tux3.h
index b235b383a74729..08f1021178d74e 100644
--- a/fs/tux3/tux3.h
+++ b/fs/tux3/tux3.h
@@ -928,6 +928,9 @@ int replay_load_orphan_inodes(struct replay *rp);
 /* super.c */
 struct replay *tux3_init_fs(struct sb *sbi);
 
+/* policy.c */
+inum_t policy_inum(struct inode *dir, loff_t where, struct inode *inode);
+
 /* replay.c */
 struct replay *replay_stage1(struct sb *sb);
 int replay_stage2(struct replay *rp);