Skip to contentSkip to conversation

ext4-locality-groups patch

RFC In review Alex Tomas 4 participants 13 messages Dec 1, 2006 – Dec 13, 2006

Subsystems (2)
lore
Share & tools
lore

Alex Tomas

author
#0 lore raw

RFC 1/1 ext4-locality-groups patch

this patch implements locality groups idea in a very simplified form. the policy is silly and ->sync_inodes() not very well tested on different workloads.

thanks, Alex

include/linux/ext4_fs_i.h +2 -0
Index: linux-2.6.19-rc6/include/linux/ext4_fs_i.h
===================================================================
@@ -150,6 +150,8 @@ struct ext4_inode_info {
 	 */
 	struct mutex truncate_mutex;
 	struct inode vfs_inode;
+	struct list_head i_lg_list;
+	struct ext4_locality_group *i_locality_group;
 
 	unsigned long i_ext_generation;
 	struct ext4_ext_cache i_cached_extent;
include/linux/ext4_fs.h +37 -0
Index: linux-2.6.19-rc6/include/linux/ext4_fs.h
===================================================================
@@ -727,6 +727,34 @@ struct dx_hash_info
 
 
 /*
+ * Locality group:
+ *   we try to group all related changes together
+ *   so that writeback can flush/allocate them together as well
+ */
+struct ext4_locality_group {
+	int			lg_parent;
+	int			lg_pgid;
+	int			lg_sid;
+	struct list_head	lg_hash;
+	spinlock_t		lg_lock;
+	int			lg_deleted;
+	atomic_t		lg_count;
+	atomic_t		lg_inodes_nr;
+
+	/* */
+	unsigned long		lg_flags;
+	struct list_head	lg_list;
+
+	/* inode lists for the group */
+	struct list_head	lg_inodes;	/* inodes in the group */
+	struct list_head	lg_dirty;	/* dirty inodes from s_dirty */
+	struct list_head	lg_io;		/* inodes scheduled for flush */
+
+	atomic_t		lg_dirty_pages;	/* pages to write */
+	atomic_t		lg_nonallocated;/* non-allocated pages */
+};
+
+/*
  * Describe an inode's exact location on disk and in memory
  */
 struct ext4_iloc
@@ -784,6 +812,15 @@ void ext4_get_group_no_and_offset(struct
 # define ATTRIB_NORET  __attribute__((noreturn))
 # define NORET_AND     noreturn,
 
+/* lg.c */
+extern void ext4_lg_init(struct super_block *sb);
+extern void ext4_lg_release(struct super_block *sb);
+extern void ext4_lg_inode_leave_group(struct inode *inode);
+extern void ext4_lg_page_enter_inode(struct inode *inode, struct page *page, int allocated);
+extern void ext4_lg_page_leave_inode(struct inode *inode, struct page *page, int allocated);
+extern void ext4_lg_sync_inodes(struct super_block *, struct writeback_control *);
+
+
 /* balloc.c */
 extern unsigned int ext4_block_group(struct super_block *sb,
 			ext4_fsblk_t blocknr);
include/linux/ext4_fs_sb.h +5 -0
Index: linux-2.6.19-rc6/include/linux/ext4_fs_sb.h
===================================================================
@@ -80,6 +80,11 @@ struct ext4_sb_info {
 	int s_jquota_fmt;			/* Format of quota to use */
 #endif
 
+	struct list_head s_locality_dirty;
+	struct list_head s_locality_io;
+	struct list_head s_locality_groups;
+	spinlock_t s_locality_lock;
+
 #ifdef EXTENTS_STATS
 	/* ext4 extents stats */
 	unsigned long s_ext_min;
fs/ext4/lg.c +533 -0

533 lines not on this page · raw message

fs/ext4/super.c +5 -0
Index: linux-2.6.19-rc6/fs/ext4/super.c
===================================================================
@@ -449,6 +449,7 @@ static void ext4_put_super (struct super
 		mark_buffer_dirty(sbi->s_sbh);
 		ext4_commit_super(sb, es, 1);
 	}
+	ext4_lg_release(sb);
 
 	for (i = 0; i < sbi->s_gdb_count; i++)
 		brelse(sbi->s_group_desc[i]);
@@ -498,6 +499,7 @@ static struct inode *ext4_alloc_inode(st
 	ei = kmem_cache_alloc(ext4_inode_cachep, SLAB_NOFS);
 	if (!ei)
 		return NULL;
+	ei->i_locality_group = NULL;
 #ifdef CONFIG_EXT4DEV_FS_POSIX_ACL
 	ei->i_acl = EXT4_ACL_NOT_CACHED;
 	ei->i_default_acl = EXT4_ACL_NOT_CACHED;
@@ -564,6 +566,7 @@ static void ext4_clear_inode(struct inod
 	EXT4_I(inode)->i_block_alloc_info = NULL;
 	if (unlikely(rsv))
 		kfree(rsv);
+	ext4_lg_inode_leave_group(inode);
 }
 
 static inline void ext4_show_quota_options(struct seq_file *seq, struct super_block *sb)
@@ -706,6 +709,7 @@ static struct super_operations ext4_sops
 	.remount_fs	= ext4_remount,
 	.clear_inode	= ext4_clear_inode,
 	.show_options	= ext4_show_options,
+	.sync_inodes	= ext4_lg_sync_inodes,
 #ifdef CONFIG_QUOTA
 	.quota_read	= ext4_quota_read,
 	.quota_write	= ext4_quota_write,
@@ -1860,6 +1864,7 @@ static int ext4_fill_super (struct super
 		test_opt(sb,DATA_FLAGS) == EXT4_MOUNT_ORDERED_DATA ? "ordered":
 		"writeback");
 
+	ext4_lg_init(sb);
 	ext4_ext_init(sb);
 
 	lock_kernel();
fs/ext4/Makefile +1 -1
Index: linux-2.6.19-rc6/fs/ext4/Makefile
===================================================================
@@ -5,7 +5,7 @@
 obj-$(CONFIG_EXT4DEV_FS) += ext4dev.o
 
 ext4dev-y	:= balloc.o bitmap.o dir.o file.o fsync.o ialloc.o inode.o \
-	   ioctl.o namei.o super.o symlink.o hash.o resize.o extents.o
+	   ioctl.o namei.o super.o symlink.o hash.o resize.o extents.o lg.o
 
 ext4dev-$(CONFIG_EXT4DEV_FS_XATTR)	+= xattr.o xattr_user.o xattr_trusted.o
 ext4dev-$(CONFIG_EXT4DEV_FS_POSIX_ACL)	+= acl.o
fs/fs-writeback.c +3 -5
Index: linux-2.6.19-rc6/fs/fs-writeback.c
===================================================================
@@ -149,8 +149,7 @@ static int write_inode(struct inode *ino
  *
  * Called under inode_lock.
  */
-static int
-__sync_single_inode(struct inode *inode, struct writeback_control *wbc)
+int __sync_single_inode(struct inode *inode, struct writeback_control *wbc)
 {
 	unsigned dirty;
 	struct address_space *mapping = inode->i_mapping;
@@ -240,8 +239,7 @@ __sync_single_inode(struct inode *inode,
  * caller has ref on the inode (either via __iget or via syscall against an fd)
  * or the inode has I_WILL_FREE set (via generic_forget_inode)
  */
-static int
-__writeback_single_inode(struct inode *inode, struct writeback_control *wbc)
+int __writeback_single_inode(struct inode *inode, struct writeback_control *wbc)
 {
 	wait_queue_head_t *wqh;
 
@@ -429,7 +427,7 @@ writeback_inodes(struct writeback_contro
 restart:
 	sb = sb_entry(super_blocks.prev);
 	for (; sb != sb_entry(&super_blocks); sb = sb_entry(sb->s_list.prev)) {
-		if (!list_empty(&sb->s_dirty) || !list_empty(&sb->s_io)) {
+		if (!list_empty(&sb->s_dirty) || !list_empty(&sb->s_io) || (sb->s_flags & 2048)) {
 			/* we're making our own get_super here */
 			sb->s_count++;
 			spin_unlock(&sb_lock);
#1 lore raw
Quoted 5 lines · Alex Tomas

this patch implements locality groups idea in a very simplified form. the policy is silly and ->sync_inodes() not very well tested on different workloads.

thanks, Alex

Hi Alex,
I applied your patches to a 2.6.19-rc6 kernel. After creating and mounting an ext4 filesystem with options extents,mballoc,delalloc, the system crashes while copying a file into the ext4 partition.
I set some kernel debugging options and rebuilt the kernel. Here is the oops I've got:

EXT4 FS on sdc1, internal journal
EXT4-fs: mounted filesystem with ordered data mode.
EXT4-fs: file extents enabled
EXT4-fs: mballoc enabled
EXT4-fs: delayed allocation enabled

BUG: spinlock bad magic on CPU#2, pdflush/264
Unable to handle kernel NULL pointer dereference at 00000000000001ac RIP:
 [<ffffffff80360011>] spin_bug+0x67/0xa5
PGD 27d97067 PUD 28370067 PMD 0
Oops: 0000 [1] SMP
CPU 2
Modules linked in: qla2xxx
Pid: 264, comm: pdflush Not tainted 2.6.19-rc6 #3
RIP: 0010:[<ffffffff80360011>]  [<ffffffff80360011>] spin_bug+0x67/0xa5
RSP: 0018:ffff81007d6a7db0  EFLAGS: 00010206
RAX: 0000000000000031 RBX: ffff810076630020 RCX: ffffffff806f48d8
RDX: ffffffff806f48d8 RSI: 0000000000000046 RDI: ffffffff806f48c0
RBP: 00000000000000a0 R08: 00000000ffffffff R09: 0000000000008000
R10: ffffffff808bfc78 R11: ffffffff808bfc78 R12: ffffffff805bfdc9
R13: ffff81002dbd0000 R14: ffff810076630000 R15: ffff81007d6a7e60
FS:  0000000000000000(0000) GS:ffff81007df14740(0000) knlGS:0000000000000000
CS:  0010 DS: 0018 ES: 0018 CR0: 000000008005003b
CR2: 00000000000001ac CR3: 00000000282cd000 CR4: 00000000000006e0
Process pdflush (pid: 264, threadinfo ffff81007d6a6000, task ffff81007db3b140)
Stack:  ffff810076630020 ffff81002daa4160 ffff810076630000 ffffffff803600ef
 ffff810076630020 ffffffff802f2bf4 ffff81007d6a7e60 ffff81002dbd0000
 ffff81002dbd0070 ffff81007d6a7e60 00000000fffffffc ffff81007df19d70
Call Trace:
 [<ffffffff803600ef>] _raw_spin_lock+0x19/0x7d
 [<ffffffff802f2bf4>] ext4_lg_sync_inodes+0xec/0x196
 [<ffffffff80245207>] keventd_create_kthread+0x0/0x64
 [<000000010004a823>]


Code: 44 8b 85 0c 01 00 00 8b 53 04 48 85 ed 48 8d 85 98 02 00 00
RIP  [<ffffffff80360011>] spin_bug+0x67/0xa5
 RSP <ffff81007d6a7db0>

CR2: 00000000000001ac

The crash occurs because ei->i_locality_group is not well initialized. The patch in attachment fixes the problem on my system (x86_64).

Valérie

fs/ext4/lg.c +1 -1
Index: linux-2.6.19-rc6/fs/ext4/lg.c
===================================================================
@@ -66,7 +66,7 @@ extern int __writeback_single_inode(stru
 struct ext4_locality_group *ext4_lg_find_group(struct super_block *sb)
 {
 	struct ext4_sb_info *sbi = EXT4_SB(sb);
-	struct ext4_locality_group *lg;
+	struct ext4_locality_group *lg = NULL;
 	struct list_head *cur;
 
 	rcu_read_lock();
author
#2 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Valerie Clement (VC) writes:

VC> The crash occurs because ei->i_locality_group is not well initialized. VC> The patch in attachment fixes the problem on my system (x86_64).

thanks!

strange that I didn't hit this on i386 ... and gcc doesn't warn.

thanks, Alex

#3 lore raw
In reply to Alex Tomas
Quoted 39 lines · Alex Tomas
fs/ext4/lg.c +39 -0
+/*
+ * entry function for inode syncing
+ * it's responsbility is to sort all inode out in their locality groups
+ */
+void ext4_lg_sync_inodes(struct super_block *sb, struct writeback_control *wbc)
+{
+	struct ext4_sb_info *sbi = EXT4_SB(sb);
+	struct ext4_locality_group *lg;
+
+	/* refill pending groups from s_dirty */
+	spin_lock(&inode_lock);
+	while (!list_empty(&sb->s_dirty)) {
+		struct inode *inode = list_entry(sb->s_dirty.prev,
+						struct inode, i_list);
+		struct ext4_inode_info *ei = EXT4_I(inode);
+
+		lg = ei->i_locality_group;
+		if (lg == NULL) {
+			if (S_ISDIR(inode->i_mode) || i_size_read(inode) == 0) {
+				if (atomic_read(&inode->i_count)) {
+					/*
+					 * The inode is clean, inuse
+					 */
+					list_move(&inode->i_list, &inode_in_use);
+				} else {
+					/*
+					 * The inode is clean, unused
+					 */
+					list_move(&inode->i_list, &inode_unused);
+				}
+				continue;
+			}
+			/* XXX: atime changed ? */
+			list_move(&inode->i_list, &inode_in_use);
+			continue;
+		}
+
+		/* move inode in proper locality group's dirty list */
+		spin_lock(&lg->lg_lock);

fs/ext4/lg.c line 502

Quoted 10 lines
fs/ext4/lg.c +10 -0
+		list_move_tail(&inode->i_list, &lg->lg_dirty);
+		spin_unlock(&lg->lg_lock);
+
+		if (!test_and_set_bit(EXT4_LG_DIRTY, &lg->lg_flags))
+			list_move(&lg->lg_list, &sbi->s_locality_dirty);
+	}
+	spin_unlock(&inode_lock);
+
+	ext4_lg_sync_groups(sb, wbc);
+}

Hi Alex,
I did the following test:

# mkfs /dev/sdc1
# mount -t ext4dev -o extents,mballoc,delalloc /dev/sdc1 /test
# dumpe2fs -h /dev/sdc1
# cp linux.tar /test
# tar xf /test/linux.tar
# dumpe2fs -h /dev/sdc1

The "Free blocks" and "Free inodes" counters in the dumpe2fs output did not change after running the cp and tar commands.

I think it misses a call to ext4_commit_super() at the end of the ext4_lg_sync_inodes function. Am I right ?

Valérie

author
#4 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Valerie Clement (VC) writes:

VC> Hi Alex,
VC> I did the following test:
VC> # mkfs /dev/sdc1
VC> # mount -t ext4dev -o extents,mballoc,delalloc /dev/sdc1 /test VC> # dumpe2fs -h /dev/sdc1
VC> # cp linux.tar /test
VC> # tar xf /test/linux.tar
VC> # dumpe2fs -h /dev/sdc1

VC> The "Free blocks" and "Free inodes" counters in the dumpe2fs output VC> did not change after running the cp and tar commands.

sync should help, I think.

VC> I think it misses a call to ext4_commit_super() at the end of the VC> ext4_lg_sync_inodes function.
VC> Am I right ?

what for? allocation was delayed, no blocks were allocated.

thanks, Alex

#5 lore raw
Quoted 11 lines · Alex Tomas
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Valerie Clement (VC) writes:

VC> Hi Alex,
VC> I did the following test:
VC> # mkfs /dev/sdc1
VC> # mount -t ext4dev -o extents,mballoc,delalloc /dev/sdc1 /test VC> # dumpe2fs -h /dev/sdc1
VC> # cp linux.tar /test
VC> # tar xf /test/linux.tar
VC> # dumpe2fs -h /dev/sdc1

Quoted 4 lines

VC> The "Free blocks" and "Free inodes" counters in the dumpe2fs output VC> did not change after running the cp and tar commands.

sync should help, I think.

No, I've just tried, it does not change anything.
Valérie

Quoted 9 lines

VC> I think it misses a call to ext4_commit_super() at the end of the VC> ext4_lg_sync_inodes function.
VC> Am I right ?

what for? allocation was delayed, no blocks were allocated.

thanks, Alex

author
#6 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Valerie Clement (VC) writes:

Quoted 2 lines · VC> Alex Tomas wrote:
Quoted 2 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Valerie Clement (VC) writes:

VC> Hi Alex,
VC> I did the following test:
VC> # mkfs /dev/sdc1
VC> # mount -t ext4dev -o extents,mballoc,delalloc /dev/sdc1 /test VC> # dumpe2fs -h /dev/sdc1
VC> # cp linux.tar /test
VC> # tar xf /test/linux.tar
VC> # dumpe2fs -h /dev/sdc1

Quoted 1 line
Quoted 1 line

VC> The "Free blocks" and "Free inodes" counters in the dumpe2fs output VC> did not change after running the cp and tar commands.

Quoted 2 lines
Quoted 2 lines

sync should help, I think.

VC> No, I've just tried, it does not change anything.
VC> Valérie

not sure ....

[root@tom ~]# mke2fs -m0 -j /dev/sda1 >&/dev/null
[root@tom ~]# mount -t ext4dev -o extents,mballoc,delalloc /dev/sda1 /test [root@tom ~]# dumpe2fs /dev/sda1 >/tmp/before
dumpe2fs 1.39.cfs1 (29-May-2006)
[root@tom ~]# dd if=/dev/zero of=/test/f bs=1M count=20
20+0 records in
20+0 records out
[root@tom ~]# dumpe2fs /dev/sda1 >/tmp/after1
dumpe2fs 1.39.cfs1 (29-May-2006)
[root@tom ~]# sync
[root@tom ~]# dumpe2fs /dev/sda1 >/tmp/after2
dumpe2fs 1.39.cfs1 (29-May-2006)
[root@tom ~]# diff -pu /tmp/before /tmp/after1

tmp/after1 2006-12-13 14:39:59.602086138 +0300 renamed from tmp/before 2006-12-13 14:39:42.541828787 +0300 +2 -2
@@ -45,9 +45,9 @@ Group 0: (Blocks 0-32767)
   Reserved GDT blocks at 2-245
   Block bitmap at 246 (+246), Inode bitmap at 247 (+247)
   Inode table at 248-752 (+248)
-  15607 free blocks, 16149 free inodes, 2 directories
+  15607 free blocks, 16148 free inodes, 2 directories
   Free blocks: 17161-32767
-  Free inodes: 12-16160
+  Free inodes: 13-16160
 Group 1: (Blocks 32768-65535)
   Backup superblock at 32768, Group descriptors at 32769-32769
   Reserved GDT blocks at 32770-33013

[root@tom ~]# diff -pu /tmp/after1 /tmp/after2

tmp/after2 2006-12-13 14:40:05.592176495 +0300 renamed from tmp/after1 2006-12-13 14:39:59.602086138 +0300 +2 -2
@@ -45,8 +45,8 @@ Group 0: (Blocks 0-32767)
   Reserved GDT blocks at 2-245
   Block bitmap at 246 (+246), Inode bitmap at 247 (+247)
   Inode table at 248-752 (+248)
-  15607 free blocks, 16148 free inodes, 2 directories
-  Free blocks: 17161-32767
+  10487 free blocks, 16148 free inodes, 2 directories
+  Free blocks: 17161-22527, 27648-32767
   Free inodes: 13-16160
 Group 1: (Blocks 32768-65535)
   Backup superblock at 32768, Group descriptors at 32769-32769

[root@tom ~]#

try to repeat with a single file?

thanks, Alex

author
#7 lore raw
In reply to Valerie Clement
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Valerie Clement (VC) writes:

Quoted 2 lines · VC> Alex Tomas wrote:
Quoted 2 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Valerie Clement (VC) writes:

VC> Hi Alex,
VC> I did the following test:
VC> # mkfs /dev/sdc1
VC> # mount -t ext4dev -o extents,mballoc,delalloc /dev/sdc1 /test VC> # dumpe2fs -h /dev/sdc1
VC> # cp linux.tar /test
VC> # tar xf /test/linux.tar
VC> # dumpe2fs -h /dev/sdc1

Quoted 1 line
Quoted 1 line

VC> The "Free blocks" and "Free inodes" counters in the dumpe2fs output VC> did not change after running the cp and tar commands.

Quoted 2 lines
Quoted 2 lines

sync should help, I think.

VC> No, I've just tried, it does not change anything.

ah, it's simple. you're looking at superblock counters. we don't update them every time. this was changed years ago. try the same with regular ext3

thanks, Alex

#8 lore raw
Quoted 4 lines · Alex Tomas

ah, it's simple. you're looking at superblock counters. we don't update them every time. this was changed years ago. try the same with regular ext3

Yes, sorry, I didn't know that and I didn't notice that before. And the per-group counters are right.

Thanks a lot for your clarification.
Valérie

#9 lore raw
Quoted 7 lines · Valerie Clement
Quoted 3 lines · Alex Tomas

ah, it's simple. you're looking at superblock counters. we don't update them every time. this was changed years ago. try the same with regular ext3

Yes, sorry, I didn't know that and I didn't notice that before. And the per-group counters are right.

It would be good, IMHO, to update the superblock counters periodically anyways (e.g. statfs already has done the calculation). Otherwise, e2fsck on a mounted-but-idle system always complains about them being incorrect.

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

#10 lore raw
In reply to Alex Tomas
Quoted 11 lines · Alex Tomas
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

Valerie Clement (VC) writes:

VC> Hi Alex,
VC> I did the following test:
VC> # mkfs /dev/sdc1
VC> # mount -t ext4dev -o extents,mballoc,delalloc /dev/sdc1 /test VC> # dumpe2fs -h /dev/sdc1
VC> # cp linux.tar /test
VC> # tar xf /test/linux.tar
VC> # dumpe2fs -h /dev/sdc1

Quoted 4 lines

VC> The "Free blocks" and "Free inodes" counters in the dumpe2fs output VC> did not change after running the cp and tar commands.

sync should help, I think.

This is probably a discrepancy that comes from reading the block device directly, right? Which is not necessarily in sync with the address space for the filesystem.

-Eric

#11 lore raw
Quoted 3 lines · Eric Sandeen

This is probably a discrepancy that comes from reading the block device directly, right? Which is not necessarily in sync with the address space for the filesystem.

In fact, the block device IS in sync with the filesystem address space, but only for metadata. The file data each has its own address space and is not coherent.

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.

#12 lore raw
Quoted 8 lines · Andreas Dilger
Quoted 3 lines · Eric Sandeen

This is probably a discrepancy that comes from reading the block device directly, right? Which is not necessarily in sync with the address space for the filesystem.

In fact, the block device IS in sync with the filesystem address space, but only for metadata. The file data each has its own address space and is not coherent.

Ah, thanks for the clarification.

-Eric