Skip to contentSkip to conversation

Block reservation for ext3

RFC PATCH In review Jan Kara 5 participants 13 messages Oct 9, 2010 – Oct 14, 2010 1 message not in the archive VFS

lore
Share & tools
lore

Jan Kara

author reviewer
#0 lore raw

cover Block reservation for ext3

Hi,

currently, when mmapped write is done to a file backed by ext3, the
filesystem does nothing to make sure blocks will be available when we need to write them out. This has two nasty consequences:
1) When flusher thread does writeback of the mmapped data, allocation happens in the context of flusher thread (i.e., as root). Thus user can effectively arbitrarily exceed quota limits or use space reserved only for sysadmin.
2) When a filesystem runs out of space, we just silently drop data on the floor (the same happens when writeout is performed in the context of the user and he hits his quota limit).

I think these problems are serious enough (especially (1) about which I was
notified lately) so that we try to fix them in ext3. The trouble is that the fix in non-trivial. We have to basically implement delayed allocation for ext3
- block reservation happens on page_mkwrite() time and we convert the reservation into a real allocation during writeout. Note: Of course, we could use a much simpler solution and just do block allocation directly at page_mkwrite() time but that really cripples performance for loads that do random writes via mmap - I've tried that some time ago.
The patches in this series (against 2.6.26-rc7) implement this. They
survived some testing with fsx-linux, I'll do more and also some performance testing.
So I'd like to hear what other people think about this. Reviews or
testing are welcome ;)

Honza

author reviewer
#1 lore raw

PATCH 1/3 vfs: Unmap underlying metadata of new data buffers only when buffer is mapped

When we do delayed allocation of some buffer, we want to signal to VFS that the buffer is new (set buffer_new) so that it properly zeros out everything. But we don't have the buffer mapped yet so we cannot really unmap underlying metadata in this state. Make VFS avoid doing unmapping of metadata when the buffer is not yet mapped.

---
 fs/buffer.c |   12 +++++++-----
 1 files changed, 7 insertions(+), 5 deletions(-)
fs/buffer.c +7 -5
index 3e7dca2..0f2ba29 100644
@@ -1688,8 +1688,9 @@ static int __block_write_full_page(struct inode *inode, struct page *page,
 			if (buffer_new(bh)) {
 				/* blockdev mappings never come here */
 				clear_buffer_new(bh);
-				unmap_underlying_metadata(bh->b_bdev,
-							bh->b_blocknr);
+				if (buffer_mapped(bh))
+					unmap_underlying_metadata(bh->b_bdev,
+						bh->b_blocknr);
 			}
 		}
 		bh = bh->b_this_page;
@@ -1875,8 +1876,9 @@ int block_prepare_write(struct page *page, unsigned from, unsigned to,
 			if (err)
 				break;
 			if (buffer_new(bh)) {
-				unmap_underlying_metadata(bh->b_bdev,
-							bh->b_blocknr);
+				if (buffer_mapped(bh))
+					unmap_underlying_metadata(bh->b_bdev,
+						bh->b_blocknr);
 				if (PageUptodate(page)) {
 					clear_buffer_new(bh);
 					set_buffer_uptodate(bh);
@@ -2514,7 +2516,7 @@ int nobh_write_begin(struct address_space *mapping,
 			goto failed;
 		if (!buffer_mapped(bh))
 			is_mapped_to_disk = 0;
-		if (buffer_new(bh))
+		if (buffer_new(bh) && buffer_mapped(bh))
 			unmap_underlying_metadata(bh->b_bdev, bh->b_blocknr);
 		if (PageUptodate(page)) {
 			set_buffer_uptodate(bh);
Signature · 1 line
1.6.4.2
author reviewer
#2 lore raw

PATCH 2/3 vfs: Implement generic per-cpu counters for delayed allocation

In reply to Jan Kara

Implement free blocks and reserved blocks counters for delayed allocation. These counters are reliable in the sence that when they return success, the subsequent conversion from reserved to allocated blocks always succeeds (see comments in the code for details). This is useful for ext3 filesystem to implement delayed allocation in particular for allocation in page_mkwrite.

---
 fs/Kconfig                       |    4 ++
 fs/Makefile                      |    1 +
 fs/delalloc_counter.c            |  109 ++++++++++++++++++++++++++++++++++++++
 fs/ext3/Kconfig                  |    1 +
 include/linux/delalloc_counter.h |   73 +++++++++++++++++++++++++
 5 files changed, 188 insertions(+), 0 deletions(-)
 create mode 100644 fs/delalloc_counter.c
 create mode 100644 include/linux/delalloc_counter.h
fs/Kconfig +4 -0
index 3d18530..4432d53 100644
@@ -19,6 +19,10 @@ config FS_XIP
 source "fs/jbd/Kconfig"
 source "fs/jbd2/Kconfig"
 
+config DELALLOC_COUNTER
+	bool
+	default n
+
 config FS_MBCACHE
 # Meta block cache for Extended Attributes (ext2/ext3/ext4)
 	tristate
fs/Makefile +1 -0
index e6ec1d3..31b22e9 100644
@@ -19,6 +19,7 @@ else
 obj-y +=	no-block.o
 endif
 
+obj-$(CONFIG_DELALLOC_COUNTER)	+= delalloc_counter.o
 obj-$(CONFIG_BLK_DEV_INTEGRITY) += bio-integrity.o
 obj-y				+= notify/
 obj-$(CONFIG_EPOLL)		+= eventpoll.o
fs/delalloc_counter.c new file +109 -0

109 lines not on this page · raw message

fs/ext3/Kconfig +1 -0
index e8c6ba0..20418f3 100644
@@ -1,6 +1,7 @@
 config EXT3_FS
 	tristate "Ext3 journalling file system support"
 	select JBD
+	select DELALLOC_COUNTER
 	help
 	  This is the journalling version of the Second extended file system
 	  (often called ext3), the de facto standard Linux file system
include/linux/delalloc_counter.h new file +73 -0

73 lines not on this page · raw message

Signature · 1 line
1.6.4.2
#3 lore raw

Re: [PATCH 2/3] vfs: Implement generic per-cpu counters for delayed allocation

Quoted 5 lines · Jan Kara

Implement free blocks and reserved blocks counters for delayed allocation. These counters are reliable in the sence that when they return success, the subsequent conversion from reserved to allocated blocks always succeeds (see comments in the code for details). This is useful for ext3 filesystem to implement delayed allocation in particular for allocation in page_mkwrite.

This doesn't really look like generic code that should go into the core kernel. I'd just add it to ext3 directly.

author reviewer
#4 lore raw

PATCH 3/3 ext3: Implement delayed allocation on page_mkwrite time

In reply to Jan Kara

We don't want to really allocate blocks on page_mkwrite() time because for random writes via mmap it results is much more fragmented files. So just reserve enough free blocks in page_mkwrite() and do the real allocation from writepage().

It's however not so simple because we do not want to overestimate necessary number of indirect blocks too badly in presence of lots of delayed allocated buffers. Thus we track which indirect blocks have already reservation pending and do not reserve space for them again.

---
 fs/ext3/balloc.c           |  103 +++++++++-----
 fs/ext3/file.c             |   19 +++-
 fs/ext3/ialloc.c           |    2 +-
 fs/ext3/inode.c            |  346 +++++++++++++++++++++++++++++++++++++++++---
 fs/ext3/resize.c           |    2 +-
 fs/ext3/super.c            |   23 +++-
 include/linux/ext3_fs.h    |    5 +-
 include/linux/ext3_fs_i.h  |   20 +++
 include/linux/ext3_fs_sb.h |    3 +-
 9 files changed, 458 insertions(+), 65 deletions(-)
fs/ext3/balloc.c +68 -35
index 4a32511..bf3f607 100644
@@ -20,6 +20,8 @@
 #include <linux/ext3_jbd.h>
 #include <linux/quotaops.h>
 #include <linux/buffer_head.h>
+#include <linux/delalloc_counter.h>
+#include <linux/writeback.h>
 
 /*
  * balloc.c contains the blocks allocation and deallocation routines
@@ -633,7 +635,7 @@ do_more:
 	spin_lock(sb_bgl_lock(sbi, block_group));
 	le16_add_cpu(&desc->bg_free_blocks_count, group_freed);
 	spin_unlock(sb_bgl_lock(sbi, block_group));
-	percpu_counter_add(&sbi->s_freeblocks_counter, count);
+	dac_free(&sbi->s_alloc_counter, count);
 
 	/* We dirtied the bitmap block */
 	BUFFER_TRACE(bitmap_bh, "dirtied bitmap block");
@@ -1411,23 +1413,19 @@ out:
 }
 
 /**
- * ext3_has_free_blocks()
- * @sbi:		in-core super block structure.
+ * ext3_free_blocks_limit()
+ * @sb:			super block
  *
  * Check if filesystem has at least 1 free block available for allocation.
  */
-static int ext3_has_free_blocks(struct ext3_sb_info *sbi)
+ext3_fsblk_t ext3_free_blocks_limit(struct super_block *sb)
 {
-	ext3_fsblk_t free_blocks, root_blocks;
+	struct ext3_sb_info *sbi = EXT3_SB(sb);
 
-	free_blocks = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
-	root_blocks = le32_to_cpu(sbi->s_es->s_r_blocks_count);
-	if (free_blocks < root_blocks + 1 && !capable(CAP_SYS_RESOURCE) &&
-		sbi->s_resuid != current_fsuid() &&
-		(sbi->s_resgid == 0 || !in_group_p (sbi->s_resgid))) {
-		return 0;
-	}
-	return 1;
+	if (!capable(CAP_SYS_RESOURCE) && sbi->s_resuid != current_fsuid() &&
+	    (sbi->s_resgid == 0 || !in_group_p(sbi->s_resgid)))
+		return le32_to_cpu(sbi->s_es->s_r_blocks_count) + 1;
+	return 0;
 }
 
 /**
@@ -1444,12 +1442,21 @@ static int ext3_has_free_blocks(struct ext3_sb_info *sbi)
  */
 int ext3_should_retry_alloc(struct super_block *sb, int *retries)
 {
-	if (!ext3_has_free_blocks(EXT3_SB(sb)) || (*retries)++ > 3)
+	struct ext3_sb_info *sbi = EXT3_SB(sb);
+	ext3_fsblk_t limit;
+
+	limit = ext3_free_blocks_limit(sb);
+	if (dac_get_free(&sbi->s_alloc_counter) < limit || (*retries)++ > 3)
 		return 0;
 
 	jbd_debug(1, "%s: retrying operation after ENOSPC\n", sb->s_id);
-
-	return journal_force_commit_nested(EXT3_SB(sb)->s_journal);
+	/*
+	 * There's a chance commit will free some blocks and writeback can
+	 * write delayed blocks so that excessive reservation gets released.
+	 */
+	if (dac_get_reserved(&sbi->s_alloc_counter))
+		writeback_inodes_sb_if_idle(sb);
+	return journal_force_commit_nested(sbi->s_journal);
 }
 
 /**
@@ -1458,6 +1465,7 @@ int ext3_should_retry_alloc(struct super_block *sb, int *retries)
  * @inode:		file inode
  * @goal:		given target block(filesystem wide)
  * @count:		target number of blocks to allocate
+ * @reserved:		number of reserved blocks
  * @errp:		error code
  *
  * ext3_new_blocks uses a goal block to assist allocation.  It tries to
@@ -1465,9 +1473,13 @@ int ext3_should_retry_alloc(struct super_block *sb, int *retries)
  * fails, it will try to allocate block(s) from other block groups without
  * any specific goal block.
  *
+ * If there is some number of blocks reserved for the allocation, we first
+ * allocate non-reserved blocks and only when we have enough of them, we start
+ * using the reserved ones.
  */
 ext3_fsblk_t ext3_new_blocks(handle_t *handle, struct inode *inode,
-			ext3_fsblk_t goal, unsigned long *count, int *errp)
+			ext3_fsblk_t goal, unsigned long *count,
+			unsigned int reserved, int *errp)
 {
 	struct buffer_head *bitmap_bh = NULL;
 	struct buffer_head *gdp_bh;
@@ -1478,7 +1490,7 @@ ext3_fsblk_t ext3_new_blocks(handle_t *handle, struct inode *inode,
 	ext3_fsblk_t ret_block;		/* filesyetem-wide allocated block */
 	int bgi;			/* blockgroup iteration index */
 	int fatal = 0, err;
-	int performed_allocation = 0;
+	int got_quota = 0, got_space = 0;
 	ext3_grpblk_t free_blocks;	/* number of free blocks in a group */
 	struct super_block *sb;
 	struct ext3_group_desc *gdp;
@@ -1499,17 +1511,28 @@ ext3_fsblk_t ext3_new_blocks(handle_t *handle, struct inode *inode,
 		printk("ext3_new_block: nonexistent device");
 		return 0;
 	}
+	sbi = EXT3_SB(sb);
 
 	/*
 	 * Check quota for allocation of this block.
 	 */
-	err = dquot_alloc_block(inode, num);
-	if (err) {
-		*errp = err;
-		return 0;
+	if (dquot_alloc_block(inode, num - reserved)) {
+		*errp = -EDQUOT;
+		goto out;
 	}
+	got_quota = 1;
+	/*
+	 * We need not succeed in allocating all these blocks but we have to
+	 * check & update delalloc counter before allocating blocks. That
+	 * guarantees that reserved blocks are always possible to allocate...
+	 */
+	if (dac_alloc(&sbi->s_alloc_counter, num - reserved,
+		      ext3_free_blocks_limit(sb)) < 0) {
+		*errp = -ENOSPC;
+		goto out;
+	}
+	got_space = 1;
 
-	sbi = EXT3_SB(sb);
 	es = EXT3_SB(sb)->s_es;
 	ext3_debug("goal=%lu.\n", goal);
 	/*
@@ -1524,11 +1547,6 @@ ext3_fsblk_t ext3_new_blocks(handle_t *handle, struct inode *inode,
 	if (block_i && ((windowsz = block_i->rsv_window_node.rsv_goal_size) > 0))
 		my_rsv = &block_i->rsv_window_node;
 
-	if (!ext3_has_free_blocks(sbi)) {
-		*errp = -ENOSPC;
-		goto out;
-	}
-
 	/*
 	 * First, test whether the goal block is free.
 	 */
@@ -1658,8 +1676,6 @@ allocated:
 		goto retry_alloc;
 	}
 
-	performed_allocation = 1;
-
 #ifdef CONFIG_JBD_DEBUG
 	{
 		struct buffer_head *debug_bh;
@@ -1709,7 +1725,6 @@ allocated:
 	spin_lock(sb_bgl_lock(sbi, group_no));
 	le16_add_cpu(&gdp->bg_free_blocks_count, -num);
 	spin_unlock(sb_bgl_lock(sbi, group_no));
-	percpu_counter_sub(&sbi->s_freeblocks_counter, num);
 
 	BUFFER_TRACE(gdp_bh, "journal_dirty_metadata for group descriptor");
 	err = ext3_journal_dirty_metadata(handle, gdp_bh);
@@ -1721,7 +1736,23 @@ allocated:
 
 	*errp = 0;
 	brelse(bitmap_bh);
-	dquot_free_block(inode, *count-num);
+	/* Used some of the reserved blocks? */
+	if (*count - reserved < num) {
+		unsigned int used_rsv = num - (*count - reserved);
+
+		dac_alloc_reserved(&sbi->s_alloc_counter, used_rsv);
+		dquot_claim_block(inode, used_rsv);
+	} else {
+		unsigned int missing_blocks = *count - reserved - num;
+
+		/*
+		 * We didn't succeed in allocating all non-reserved blocks.
+		 * Update counters to fix overestimation we did at the
+		 * beginning of this function
+		 */
+		dac_free(&sbi->s_alloc_counter, missing_blocks);
+		dquot_free_block(inode, missing_blocks);
+	}
 	*count = num;
 	return ret_block;
 
@@ -1735,8 +1766,10 @@ out:
 	/*
 	 * Undo the block allocation
 	 */
-	if (!performed_allocation)
-		dquot_free_block(inode, *count);
+	if (got_quota)
+		dquot_free_block(inode, *count - reserved);
+	if (got_space)
+		dac_free(&sbi->s_alloc_counter, *count - reserved);
 	brelse(bitmap_bh);
 	return 0;
 }
@@ -1746,7 +1779,7 @@ ext3_fsblk_t ext3_new_block(handle_t *handle, struct inode *inode,
 {
 	unsigned long count = 1;
 
-	return ext3_new_blocks(handle, inode, goal, &count, errp);
+	return ext3_new_blocks(handle, inode, goal, &count, 0, errp);
 }
 
 /**
fs/ext3/file.c +18 -1
index f55df0e..249597d 100644
@@ -52,6 +52,23 @@ static int ext3_release_file (struct inode * inode, struct file * filp)
 	return 0;
 }
 
+static const struct vm_operations_struct ext3_file_vm_ops = {
+	.fault		= filemap_fault,
+	.page_mkwrite	= ext3_page_mkwrite,
+};
+
+static int ext3_file_mmap(struct file *file, struct vm_area_struct *vma)
+{
+	struct address_space *mapping = file->f_mapping;
+
+	if (!mapping->a_ops->readpage)
+		return -ENOEXEC;
+	file_accessed(file);
+	vma->vm_ops = &ext3_file_vm_ops;
+	vma->vm_flags |= VM_CAN_NONLINEAR;
+	return 0;
+}
+
 const struct file_operations ext3_file_operations = {
 	.llseek		= generic_file_llseek,
 	.read		= do_sync_read,
@@ -62,7 +79,7 @@ const struct file_operations ext3_file_operations = {
 #ifdef CONFIG_COMPAT
 	.compat_ioctl	= ext3_compat_ioctl,
 #endif
-	.mmap		= generic_file_mmap,
+	.mmap		= ext3_file_mmap,
 	.open		= dquot_file_open,
 	.release	= ext3_release_file,
 	.fsync		= ext3_sync_file,
fs/ext3/ialloc.c +1 -1
index 4ab72db..481f63c 100644
@@ -257,7 +257,7 @@ static int find_group_orlov(struct super_block *sb, struct inode *parent)
 
 	freei = percpu_counter_read_positive(&sbi->s_freeinodes_counter);
 	avefreei = freei / ngroups;
-	freeb = percpu_counter_read_positive(&sbi->s_freeblocks_counter);
+	freeb = dac_get_avail(&sbi->s_alloc_counter);
 	avefreeb = freeb / ngroups;
 	ndirs = percpu_counter_read_positive(&sbi->s_dirs_counter);
 
fs/ext3/inode.c +326 -20

489 lines not on this page · raw message

fs/ext3/resize.c +1 -1
index 0ccd7b1..91d1ae1 100644
@@ -929,7 +929,7 @@ int ext3_group_add(struct super_block *sb, struct ext3_new_group_data *input)
 	le32_add_cpu(&es->s_r_blocks_count, input->reserved_blocks);
 
 	/* Update the free space counts */
-	percpu_counter_add(&sbi->s_freeblocks_counter,
+	percpu_counter_add(&sbi->s_alloc_counter.free,
 			   input->free_blocks_count);
 	percpu_counter_add(&sbi->s_freeinodes_counter,
 			   EXT3_INODES_PER_GROUP(sb));
fs/ext3/super.c +18 -5
index 5dbf4db..c5b7f39 100644
@@ -431,7 +431,7 @@ static void ext3_put_super (struct super_block * sb)
 	for (i = 0; i < sbi->s_gdb_count; i++)
 		brelse(sbi->s_group_desc[i]);
 	kfree(sbi->s_group_desc);
-	percpu_counter_destroy(&sbi->s_freeblocks_counter);
+	dac_destroy(&sbi->s_alloc_counter);
 	percpu_counter_destroy(&sbi->s_freeinodes_counter);
 	percpu_counter_destroy(&sbi->s_dirs_counter);
 	brelse(sbi->s_sbh);
@@ -482,6 +482,11 @@ static struct inode *ext3_alloc_inode(struct super_block *sb)
 	ei->vfs_inode.i_version = 1;
 	atomic_set(&ei->i_datasync_tid, 0);
 	atomic_set(&ei->i_sync_tid, 0);
+#ifdef CONFIG_QUOTA
+	ei->i_reserved_quota = 0;
+#endif
+	ei->i_da_indirect = RB_ROOT;
+
 	return &ei->vfs_inode;
 }
 
@@ -742,8 +747,17 @@ static ssize_t ext3_quota_read(struct super_block *sb, int type, char *data,
 			       size_t len, loff_t off);
 static ssize_t ext3_quota_write(struct super_block *sb, int type,
 				const char *data, size_t len, loff_t off);
+#ifdef CONFIG_QUOTA
+qsize_t *ext3_get_reserved_space(struct inode *inode)
+{
+	return &EXT3_I(inode)->i_reserved_quota;
+}
+#endif
 
 static const struct dquot_operations ext3_quota_operations = {
+#ifdef CONFIG_QUOTA
+	.get_reserved_space = ext3_get_reserved_space,
+#endif
 	.write_dquot	= ext3_write_dquot,
 	.acquire_dquot	= ext3_acquire_dquot,
 	.release_dquot	= ext3_release_dquot,
@@ -1946,8 +1960,7 @@ static int ext3_fill_super (struct super_block *sb, void *data, int silent)
 				"mounting ext3 over ext2?");
 		goto failed_mount2;
 	}
-	err = percpu_counter_init(&sbi->s_freeblocks_counter,
-			ext3_count_free_blocks(sb));
+	err = dac_init(&sbi->s_alloc_counter, ext3_count_free_blocks(sb));
 	if (!err) {
 		err = percpu_counter_init(&sbi->s_freeinodes_counter,
 				ext3_count_free_inodes(sb));
@@ -2036,7 +2049,7 @@ cantfind_ext3:
 	goto failed_mount;
 
 failed_mount3:
-	percpu_counter_destroy(&sbi->s_freeblocks_counter);
+	dac_destroy(&sbi->s_alloc_counter);
 	percpu_counter_destroy(&sbi->s_freeinodes_counter);
 	percpu_counter_destroy(&sbi->s_dirs_counter);
 	journal_destroy(sbi->s_journal);
@@ -2723,7 +2736,7 @@ static int ext3_statfs (struct dentry * dentry, struct kstatfs * buf)
 	buf->f_type = EXT3_SUPER_MAGIC;
 	buf->f_bsize = sb->s_blocksize;
 	buf->f_blocks = le32_to_cpu(es->s_blocks_count) - sbi->s_overhead_last;
-	buf->f_bfree = percpu_counter_sum_positive(&sbi->s_freeblocks_counter);
+	buf->f_bfree = dac_get_avail_sum(&sbi->s_alloc_counter);
 	buf->f_bavail = buf->f_bfree - le32_to_cpu(es->s_r_blocks_count);
 	if (buf->f_bfree < le32_to_cpu(es->s_r_blocks_count))
 		buf->f_bavail = 0;
include/linux/ext3_fs.h +4 -1
index 6ce1bca..e24a355 100644
@@ -837,12 +837,14 @@ ext3_group_first_block_no(struct super_block *sb, unsigned long group_no)
 # define NORET_AND     noreturn,
 
 /* balloc.c */
+extern ext3_fsblk_t ext3_free_blocks_limit(struct super_block *sb);
 extern int ext3_bg_has_super(struct super_block *sb, int group);
 extern unsigned long ext3_bg_num_gdb(struct super_block *sb, int group);
 extern ext3_fsblk_t ext3_new_block (handle_t *handle, struct inode *inode,
 			ext3_fsblk_t goal, int *errp);
 extern ext3_fsblk_t ext3_new_blocks (handle_t *handle, struct inode *inode,
-			ext3_fsblk_t goal, unsigned long *count, int *errp);
+			ext3_fsblk_t goal, unsigned long *count,
+			unsigned int reserved, int *errp);
 extern void ext3_free_blocks (handle_t *handle, struct inode *inode,
 			ext3_fsblk_t block, unsigned long count);
 extern void ext3_free_blocks_sb (handle_t *handle, struct super_block *sb,
@@ -908,6 +910,7 @@ extern void ext3_get_inode_flags(struct ext3_inode_info *);
 extern void ext3_set_aops(struct inode *inode);
 extern int ext3_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
 		       u64 start, u64 len);
+extern int ext3_page_mkwrite(struct vm_area_struct *vma, struct vm_fault *vmf);
 
 /* ioctl.c */
 extern long ext3_ioctl(struct file *, unsigned int, unsigned long);
include/linux/ext3_fs_i.h +20 -0
index f42c098..10e7703 100644
@@ -64,6 +64,20 @@ struct ext3_block_alloc_info {
 #define rsv_start rsv_window._rsv_start
 #define rsv_end rsv_window._rsv_end
 
+
+#define EXT3_DA_ALLOC_FL 0x0001	/* Indirect block is allocated */
+/*
+ * Structure recording information about indirect block with delayed allocated
+ * data blocks beneath.
+ */
+struct ext3_da_indirect {
+	struct rb_node node;
+	__u32 offset;			/* Offset of indirect block */
+	unsigned short data_blocks;	/* Number of delayed allocated data
+					 * blocks below this indirect block */
+	unsigned short flags;
+};
+
 /*
  * third extended file system inode data in memory
  */
@@ -92,6 +106,9 @@ struct ext3_inode_info {
 	/* block reservation info */
 	struct ext3_block_alloc_info *i_block_alloc_info;
 
+	/* RB-tree with information about delayed-allocated indirect blocks */
+	struct rb_root i_da_indirect;
+
 	__u32	i_dir_start_lookup;
 #ifdef CONFIG_EXT3_FS_XATTR
 	/*
@@ -125,6 +142,9 @@ struct ext3_inode_info {
 
 	/* on-disk additional length */
 	__u16 i_extra_isize;
+#ifdef CONFIG_QUOTA
+	qsize_t i_reserved_quota;
+#endif
 
 	/*
 	 * truncate_mutex is for serialising ext3_truncate() against
include/linux/ext3_fs_sb.h +2 -1
index 258088a..54909d0 100644
@@ -21,6 +21,7 @@
 #include <linux/wait.h>
 #include <linux/blockgroup_lock.h>
 #include <linux/percpu_counter.h>
+#include <linux/delalloc_counter.h>
 #endif
 #include <linux/rbtree.h>
 
@@ -58,7 +59,7 @@ struct ext3_sb_info {
 	u32 s_hash_seed[4];
 	int s_def_hash_version;
 	int s_hash_unsigned;	/* 3 if hash should be signed, 0 if not */
-	struct percpu_counter s_freeblocks_counter;
+	struct delalloc_counter s_alloc_counter;
 	struct percpu_counter s_freeinodes_counter;
 	struct percpu_counter s_dirs_counter;
 	struct blockgroup_lock *s_blockgroup_lock;
Signature · 1 line
1.6.4.2
#5 lore raw
In reply to Jan Kara
Quoted 4 lines · Jan Kara

currently, when mmapped write is done to a file backed by ext3, the
filesystem does nothing to make sure blocks will be available when we need to write them out.

Hmm, you've done all of this work already, so this isn't the best time to suggest this, but I wonder if we've explored all of the alternatives that might allow for a less drastic set of changes to ext3, just out of stability's sake.

How often do legitimate workloads mmap a sparse file then write into it? As I recall, the original POSIX.1 spec didn't allow mmap beyond the end of the file; this I believe was lifted later on (at least I don't see it in SUSv3 spec).

If it's not all that common, then other options are:

1) Fail an mmap with EINVAL if there is an attempt to map a file region which is either sparse or extends beyond the end of a file. This is probably not a great alternative, but it's a possibility.

2) Allocate all of the pages that are not allocated at mmap time. Since ext3 doesn't have space for an uninitialized bit, we'd have to either (2a) forcing a disk write out for all of the newly initialized pages, or (2b) keep track of the allocated disk blocks in memory, but don't actually write the block mappings to the indirect blocks until the blocks are actually written out. (This last might be just as complex, alas).

3) Keep a global counter of sparse blocks which are mapped at mmap() time, and update it as blocks are allocated, or when the region is freed at munmap() time.

#3 might be much simpler, at the end of the day. Note that there are some Japanese customers that really freaked with ext4 just because it was *different*, and begged a distribution not to ship ext4 because it might destablize their customers. Not that I think we are obliged to listen to some of the more extremely conservative customers, but there was something nice about telling people (well, if you want something which is nice and stable and conservative, you can pick ext3).

Do really have legitimate and common workloads which are allocating blocks by writing into an mmapped region? I wasn't aware of such beasts, but maybe they are out there...

- Ted

author reviewer
#6 lore raw
Quoted 10 lines · Ted Ts'o
Quoted 4 lines · Jan Kara

currently, when mmapped write is done to a file backed by ext3, the
filesystem does nothing to make sure blocks will be available when we need to write them out.

Hmm, you've done all of this work already, so this isn't the best time to suggest this, but I wonder if we've explored all of the alternatives that might allow for a less drastic set of changes to ext3, just out of stability's sake.

Yeah, I understand that and I've been also thinking for some time whether
I cannot avoid implementing block reservation but I haven't come up with anything really acceptable. Moreover, unless we write via mmap to a sparse file, the code paths taken are changed only a little (only when and how we account for allocated blocks)...

Quoted 4 lines

How often do legitimate workloads mmap a sparse file then write into it? As I recall, the original POSIX.1 spec didn't allow mmap beyond the end of the file; this I believe was lifted later on (at least I don't see it in SUSv3 spec).

Well, mmap beyond EOF is still undefined AFAIK (although Linux
traditionally supports it) but mmap of sparse files was always supposed to work. My favorite user of sparse-file mmap is Berkeley DB, some torrent clients do that as well and I believe there are others. So it's not the most common thing but it happens often enough.

Quoted 5 lines

If it's not all that common, then other options are:

1) Fail an mmap with EINVAL if there is an attempt to map a file region which is either sparse or extends beyond the end of a file. This is probably not a great alternative, but it's a possibility.

This is no-go IMHO. We would surely get lots of users complaining...

Quoted 7 lines

2) Allocate all of the pages that are not allocated at mmap time. Since ext3 doesn't have space for an uninitialized bit, we'd have to either (2a) forcing a disk write out for all of the newly initialized pages, or (2b) keep track of the allocated disk blocks in memory, but don't actually write the block mappings to the indirect blocks until the blocks are actually written out. (This last might be just as complex, alas).

Doing allocation at mmap time does not really work - on each mmap we
would have to map blocks for the whole file which would make mmap really expensive operation. Doing it at page-fault as you suggest in (2a) works (that's the second plausible option IMO) but the increased fragmentation and thus loss of performance is rather noticeable. I don't have current numbers but when I tried that last year Berkeley DB was like two or three times slower.
In your (2b) suggestion, I don't see how we would avoid leaking allocated
blocks when we crash before writing allocation to indirect block. Also the fragmentation problem which seems to be the main source of performance issues would stay the same.

Quoted 3 lines

3) Keep a global counter of sparse blocks which are mapped at mmap() time, and update it as blocks are allocated, or when the region is freed at munmap() time.

Here again I see the problem that mapping all file blocks at mmap time
is rather expensive and so does not seem viable to me. Also the overestimation of needed blocks could be rather huge.

Quoted 7 lines

#3 might be much simpler, at the end of the day. Note that there are some Japanese customers that really freaked with ext4 just because it was *different*, and begged a distribution not to ship ext4 because it might destablize their customers. Not that I think we are obliged to listen to some of the more extremely conservative customers, but there was something nice about telling people (well, if you want something which is nice and stable and conservative, you can pick ext3).

I'm aware of this. Actually, the user observable differences should be
rather minimal. The only one I'm aware of is that you can get SIGSEGV at page fault time because the filesystem runs out of disk space (or out of disk quota) which seems better than throwing away the data later. Also I don't think anybody serious runs systems close to ENOSPC regularly and if that happens accidentally, manual intervention is usually needed anyway...
Thanks for your ideas!

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
#7 lore raw
Quoted 6 lines · On Mon, 11 Oct 2010 16:28:13 +0200 Jan Kara <[email protected]> wrote:
Quoted 5 lines · Ted Ts'o
Quoted 4 lines · Jan Kara

currently, when mmapped write is done to a file backed by ext3, the
filesystem does nothing to make sure blocks will be available when we need to write them out.

I thought we'd actually fixed this. I guess we didn't. I think what we did do was to ensure that a subsequent fsync()/msync() would reliably report the data loss (has anyone tested this in the past few years??). This is something, but it's quite lame.

Quoted 14 lines
Quoted 4 lines

Hmm, you've done all of this work already, so this isn't the best time to suggest this, but I wonder if we've explored all of the alternatives that might allow for a less drastic set of changes to ext3, just out of stability's sake.

Yeah, I understand that and I've been also thinking for some time whether
I cannot avoid implementing block reservation but I haven't come up with anything really acceptable. Moreover, unless we write via mmap to a sparse file, the code paths taken are changed only a little (only when and how we account for allocated blocks)...

Quoted 4 lines

How often do legitimate workloads mmap a sparse file then write into it? As I recall, the original POSIX.1 spec didn't allow mmap beyond the end of the file; this I believe was lifted later on (at least I don't see it in SUSv3 spec).

Quoted 5 lines

Well, mmap beyond EOF is still undefined AFAIK (although Linux
traditionally supports it) but mmap of sparse files was always supposed to work. My favorite user of sparse-file mmap is Berkeley DB, some torrent clients do that as well and I believe there are others. So it's not the most common thing but it happens often enough.

Yes, people do this. With a 64-bit address space they create a gargantuan mmap of the entire database and just populate teeny bits of it simply with CPU stores. They'd be unhappy if the kernel started instantiating every block within the mmap()!

Quoted 14 lines
Quoted 5 lines

If it's not all that common, then other options are:

1) Fail an mmap with EINVAL if there is an attempt to map a file region which is either sparse or extends beyond the end of a file. This is probably not a great alternative, but it's a possibility.

This is no-go IMHO. We would surely get lots of users complaining...

Quoted 7 lines

2) Allocate all of the pages that are not allocated at mmap time. Since ext3 doesn't have space for an uninitialized bit, we'd have to either (2a) forcing a disk write out for all of the newly initialized pages, or (2b) keep track of the allocated disk blocks in memory, but don't actually write the block mappings to the indirect blocks until the blocks are actually written out. (This last might be just as complex, alas).

Quoted 7 lines

Doing allocation at mmap time does not really work - on each mmap we
would have to map blocks for the whole file which would make mmap really expensive operation. Doing it at page-fault as you suggest in (2a) works (that's the second plausible option IMO) but the increased fragmentation and thus loss of performance is rather noticeable. I don't have current numbers but when I tried that last year Berkeley DB was like two or three times slower.

ouch.

Can we fix the layout problem? Are reservation windows of no use here?

Quoted 11 lines

In your (2b) suggestion, I don't see how we would avoid leaking allocated
blocks when we crash before writing allocation to indirect block. Also the fragmentation problem which seems to be the main source of performance issues would stay the same.

Quoted 3 lines

3) Keep a global counter of sparse blocks which are mapped at mmap() time, and update it as blocks are allocated, or when the region is freed at munmap() time.

Here again I see the problem that mapping all file blocks at mmap time
is rather expensive and so does not seem viable to me. Also the overestimation of needed blocks could be rather huge.

When I did ext2 delayed allocation back in, err, 2001 I had considerable trouble working out how many blocks to actually reserve for a file block, because it also had to reserve the indirect blocks. One file block allocation can result in reserving four disk blocks! And iirc it was not possible with existing in-core data structures to work out whether all four blocks needed reserving until the actual block allocation had occurred. So I ended up reserving the worst-case number of indirects, based upon the file offset. If the disk ran out of "space" I'd do a forced writeback to empty all the reservations and would then take a look to see if the disk was _really_ out of space.

Is all of this an issue with this work? If so, what approach did you take?

Quoted 7 lines
Quoted 7 lines

#3 might be much simpler, at the end of the day. Note that there are some Japanese customers that really freaked with ext4 just because it was *different*, and begged a distribution not to ship ext4 because it might destablize their customers. Not that I think we are obliged to listen to some of the more extremely conservative customers, but there was something nice about telling people (well, if you want something which is nice and stable and conservative, you can pick ext3).

Quoted 6 lines

I'm aware of this. Actually, the user observable differences should be
rather minimal. The only one I'm aware of is that you can get SIGSEGV at page fault time because the filesystem runs out of disk space (or out of disk quota) which seems better than throwing away the data later. Also I don't think anybody serious runs systems close to ENOSPC regularly and if that happens accidentally, manual intervention is usually needed anyway...

Gee. I remember people having issues with forcing the SEGV at pagefault time. It _is_ a behaviour change: the application might be about to free up some disk space, so the msync() would have succeeded anyway.

iirc another issue was that the standards (posix?) don't anticipate getting a SEGV in response to ENOSPC. There might have been other concerns - it's all foggy now.

Our general answer to this overall problem is: "run msync() and check the result". That's a bit weaselly, but it's not a _bad_ answer. After all, there might be an EIO as well! So a good application should be checking for both ENOSPC and EIO. Your patches only address the ENOSPC.

author reviewer
#8 lore raw
Quoted 6 lines · Andrew Morton
Quoted 3 lines · On Mon, 11 Oct 2010 16:28:13 +0200 Jan Kara <[email protected]> wrote:
Quoted 2 lines · Ted Ts'o
Quoted 1 line · Jan Kara
Quoted 8 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

currently, when mmapped write is done to a file backed by ext3, the
filesystem does nothing to make sure blocks will be available when we need to write them out.

I thought we'd actually fixed this. I guess we didn't. I think what we did do was to ensure that a subsequent fsync()/msync() would reliably report the data loss (has anyone tested this in the past few years??). This is something, but it's quite lame.

Yes, that's what we do these days - we set bit in address space in
generic_writepages() and the nearest syncing function (in fact the first caller of filemap_fdatawait()) will get the error. It's kind of suboptimal, that if e.g. sys_sync() runs before you manage to call fsync(), you've just lost the chance to see possible error. So I agree the current interface is lame (but not that I would know better at least for EIO handling)...

Quoted 15 lines
Quoted 7 lines
Quoted 7 lines

2) Allocate all of the pages that are not allocated at mmap time. Since ext3 doesn't have space for an uninitialized bit, we'd have to either (2a) forcing a disk write out for all of the newly initialized pages, or (2b) keep track of the allocated disk blocks in memory, but don't actually write the block mappings to the indirect blocks until the blocks are actually written out. (This last might be just as complex, alas).

Quoted 7 lines

Doing allocation at mmap time does not really work - on each mmap we
would have to map blocks for the whole file which would make mmap really expensive operation. Doing it at page-fault as you suggest in (2a) works (that's the second plausible option IMO) but the increased fragmentation and thus loss of performance is rather noticeable. I don't have current numbers but when I tried that last year Berkeley DB was like two or three times slower.

Quoted 3 lines

ouch.

Can we fix the layout problem? Are reservation windows of no use here?

Reservation windows do not work for this load. The reason is that the
page-fault order is completely random so we just spend time creating and removing tiny reservation windows because the next page fault doing allocation is scarcely close enough to fall into the small window.
The logic in ext3_find_goal() ends up picking blocks close together for
blocks belonging to the same indirect block if we are lucky but they definitely won't be sequentially ordered. For Berkeley DB the situation is made worse by the fact that there are several database files and their blocks end up interleaved.
So we could improve the layout but we'd have to tweak the reservation
logic and allocator and it's not completely clear to me how.
One thing to note is that currently, ext3 *is* in fact doing delayed
allocation for writes via mmap. We just never called it like that and never bothered to do proper space estimation...

Quoted 18 lines
Quoted 6 lines
Quoted 3 lines

3) Keep a global counter of sparse blocks which are mapped at mmap() time, and update it as blocks are allocated, or when the region is freed at munmap() time.

Here again I see the problem that mapping all file blocks at mmap time
is rather expensive and so does not seem viable to me. Also the overestimation of needed blocks could be rather huge.

When I did ext2 delayed allocation back in, err, 2001 I had considerable trouble working out how many blocks to actually reserve for a file block, because it also had to reserve the indirect blocks. One file block allocation can result in reserving four disk blocks! And iirc it was not possible with existing in-core data structures to work out whether all four blocks needed reserving until the actual block allocation had occurred. So I ended up reserving the worst-case number of indirects, based upon the file offset. If the disk ran out of "space" I'd do a forced writeback to empty all the reservations and would then take a look to see if the disk was _really_ out of space.

Quoted 2 lines

Is all of this an issue with this work? If so, what approach did you take?

Yeah, I've spotted exactly the same problem. How I decided to solve it in
the end is that in memory we keep track of each indirect block that has delay-allocated buffer under it. This allows us to reserve space for each indirect block at most once (I didn't bother with making the accounting precise for double or triple indirect blocks so when I need to reserve space for indirect block, I reserve the whole path just to be sure). This pushes the error in estimation to rather acceptable range for reasonably common workloads - the error can still be 50% for workloads which use just one data block in each indirect block but even in this case the absolute number of blocks falsely reserved is small.
The cost is of course increased complexity of the code, the memory
spent for tracking those indirect blocks (32 bytes per indirect block), and some time for lookups in the RB-tree of the structures. At least the nice thing is that when there are no delay-allocated blocks, there isn't any overhead (tree is empty).

Quoted 23 lines
Quoted 7 lines
Quoted 7 lines

#3 might be much simpler, at the end of the day. Note that there are some Japanese customers that really freaked with ext4 just because it was *different*, and begged a distribution not to ship ext4 because it might destablize their customers. Not that I think we are obliged to listen to some of the more extremely conservative customers, but there was something nice about telling people (well, if you want something which is nice and stable and conservative, you can pick ext3).

Quoted 6 lines

I'm aware of this. Actually, the user observable differences should be
rather minimal. The only one I'm aware of is that you can get SIGSEGV at page fault time because the filesystem runs out of disk space (or out of disk quota) which seems better than throwing away the data later. Also I don't think anybody serious runs systems close to ENOSPC regularly and if that happens accidentally, manual intervention is usually needed anyway...

Gee. I remember people having issues with forcing the SEGV at pagefault time. It _is_ a behaviour change: the application might be about to free up some disk space, so the msync() would have succeeded anyway.

iirc another issue was that the standards (posix?) don't anticipate getting a SEGV in response to ENOSPC. There might have been other concerns - it's all foggy now.

Quoted 5 lines

Our general answer to this overall problem is: "run msync() and check the result". That's a bit weaselly, but it's not a _bad_ answer. After all, there might be an EIO as well! So a good application should be checking for both ENOSPC and EIO. Your patches only address the ENOSPC.

Yes, here my main concern is that the patch set is not only about ENOSPC
(I can imagine we could live with that when we lived with that upto now) but also about the quota problem. To reiterate - if the allocation happens during writeback, we don't know who originally did the write and thus whether he was allowed to exceed quota limit or not. Currently, since flusher threads run as root, we always ignore quota limits and thus user can write arbirary amount of data by writing via mmap. Sysadmins don't like that... BTW the same problem happens with checking reserved space for root in ext? filesystems.
I don't see a different solution than to check quotas at page fault
because that is the only moment when we know the identity of the writer and if quota check fails we have to refuse the fault - SIGSEGV is the only option I know about. And when I have to do all the reservation because of quotas, ENOSPC handling is a nice bonus.

IMHO there are three separate questions:
a) Do we want to fix the quota problem?
- I'm convinced that yes.
b) Can we solve it without behavior change of sending SIGSEGV on error?
- I don't see how but maybe you have some bright idea...
c) When we decide some reservation scheme is unavoidable, there is question how to estimate amount of indirect blocks. My scheme is one possibility, but there is a wider variety of tradeoffs between complexity and accuracy. A special low effort, low impact possibility here might be to just ignore the ENOSPC problem as we did so far, reserve only quota for data block on page fault, and rely on the fact that there isn't going to be that much metadata so user cannot exceed his quota limit by too much... But when we already have the interface change, it seems a bit stupid not to fix it properly and also handle ENOSPC with it.

Honza

Signature · 2 lines
Jan Kara <[email protected]>
SUSE Labs, CR
#9 lore raw
Quoted 9 lines · Jan Kara

c) When we decide some reservation scheme is unavoidable, there is question how to estimate amount of indirect blocks. My scheme is one possibility, but there is a wider variety of tradeoffs between complexity and accuracy. A special low effort, low impact possibility here might be to just ignore the ENOSPC problem as we did so far, reserve only quota for data block on page fault, and rely on the fact that there isn't going to be that much metadata so user cannot exceed his quota limit by too much... But when we already have the interface change, it seems a bit stupid not to fix it properly and also handle ENOSPC with it.

We ultimately decided to do two different things for ENOSPC versus EDQUOTA in ext4. For quota overflow we just assume that the number of metadata blocks won't be that many, and just allow them to go over quota. For ENOSPC, we would force writeback to see if it would free space, and ultimately we would drop out of delayed allocation mode when we were close to running out of space (and for non-root users we would depend on the 5% blocks reserved for root).

Yeah, that means if root application mmap's a huge 100GB sparse region, and we only have 2GB free in the file system, and then the application proceeds to write to all 100GB of mmap'ed region, there's a chance data might get silently lost when we drop out of delalloc mode and we then really do completely run out of memory. But really, what we are we supposed do? Unless you have the kernel break out in hysterical laughter and reject the mmap at allocation time, I suppose the only other thing we could do, if silently dropping data is unacceptable, is we can send the SEGV early even though we might have a few blocks left. That way the data loss isn't silent (the application will probably drop core and die instead), so it's no longer our problem. :-)

- Ted

A message that is not in the archive (sent off-list or not yet received): [email protected]

#11 lore raw

---------- Forwarded message ----------
From: Amir Goldstein <[email protected]>
Date: Wed, Oct 13, 2010 at 10:44 AM
Subject: Re: [PATCH RFC 0/3] Block reservation for ext3
To: Jan Kara <[email protected]>
Cc: Andrew Morton <[email protected]>, Ted Ts'o <[email protected]>, [email protected]

Quoted 50 lines · Jan Kara
Quoted 10 lines · Andrew Morton
Quoted 7 lines · On Mon, 11 Oct 2010 16:28:13 +0200 Jan Kara <[email protected]> wrote:

  Doing allocation at mmap time does not really work - on each mmap we would have to map blocks for the whole file which would make mmap really expensive operation. Doing it at page-fault as you suggest in (2a) works (that's the second plausible option IMO) but the increased fragmentation and thus loss of performance is rather noticeable. I don't have current numbers but when I tried that last year Berkeley DB was like two or three times slower.

Quoted 3 lines

ouch.

Can we fix the layout problem?  Are reservation windows of no use here?

 Reservation windows do not work for this load. The reason is that the page-fault order is completely random so we just spend time creating and removing tiny reservation windows because the next page fault doing allocation is scarcely close enough to fall into the small window. The logic in ext3_find_goal() ends up picking blocks close together for blocks belonging to the same indirect block if we are lucky but they definitely won't be sequentially ordered. For Berkeley DB the situation is made worse by the fact that there are several database files and their blocks end up interleaved.
 So we could improve the layout but we'd have to tweak the reservation logic and allocator and it's not completely clear to me how. One thing to note is that currently, ext3 *is* in fact doing delayed allocation for writes via mmap. We just never called it like that and never bothered to do proper space estimation...

Quoted 18 lines
Quoted 6 lines
Quoted 3 lines

3) Keep a global counter of sparse blocks which are mapped at mmap() time, and update it as blocks are allocated, or when the region is freed at munmap() time.

  Here again I see the problem that mapping all file blocks at mmap time is rather expensive and so does not seem viable to me. Also the overestimation of needed blocks could be rather huge.

When I did ext2 delayed allocation back in, err, 2001 I had considerable trouble working out how many blocks to actually reserve for a file block, because it also had to reserve the indirect blocks. One file block allocation can result in reserving four disk blocks! And iirc it was not possible with existing in-core data structures to work out whether all four blocks needed reserving until the actual block allocation had occurred.  So I ended up reserving the worst-case number of indirects, based upon the file offset.  If the disk ran out of "space" I'd do a forced writeback to empty all the reservations and would then take a look to see if the disk was _really_ out of space.

Quoted 2 lines

Is all of this an issue with this work?  If so, what approach did you take?

Quoted 16 lines

 Yeah, I've spotted exactly the same problem. How I decided to solve it in the end is that in memory we keep track of each indirect block that has delay-allocated buffer under it. This allows us to reserve space for each indirect block at most once (I didn't bother with making the accounting precise for double or triple indirect blocks so when I need to reserve space for indirect block, I reserve the whole path just to be sure). This pushes the error in estimation to rather acceptable range for reasonably common workloads - the error can still be 50% for workloads which use just one data block in each indirect block but even in this case the absolute number of blocks falsely reserved is small.
 The cost is of course increased complexity of the code, the memory spent for tracking those indirect blocks (32 bytes per indirect block), and some time for lookups in the RB-tree of the structures. At least the nice thing is that when there are no delay-allocated blocks, there isn't any overhead (tree is empty).

How about allocating *only* the indirect blocks on page fault. IMHO it seems like a fair mixture of high quota accuracy, low complexity of the accounting code and low file fragmentation (only indirect may be a bit further away from data).

In my snapshot patches I use the @create arg to get_blocks_handle() to pass commands just like "allocate only indirect blocks". The patch is rather simple. I can prepare it for ext3 if you like.

Amir.
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#12 lore raw
Quoted 73 lines · Amir G.
Quoted 50 lines · Jan Kara
Quoted 10 lines · Andrew Morton
Quoted 7 lines · On Mon, 11 Oct 2010 16:28:13 +0200 Jan Kara <[email protected]> wrote:

  Doing allocation at mmap time does not really work - on each mmap we would have to map blocks for the whole file which would make mmap really expensive operation. Doing it at page-fault as you suggest in (2a) works (that's the second plausible option IMO) but the increased fragmentation and thus loss of performance is rather noticeable. I don't have current numbers but when I tried that last year Berkeley DB was like two or three times slower.

Quoted 3 lines

ouch.

Can we fix the layout problem?  Are reservation windows of no use here?

 Reservation windows do not work for this load. The reason is that the page-fault order is completely random so we just spend time creating and removing tiny reservation windows because the next page fault doing allocation is scarcely close enough to fall into the small window. The logic in ext3_find_goal() ends up picking blocks close together for blocks belonging to the same indirect block if we are lucky but they definitely won't be sequentially ordered. For Berkeley DB the situation is made worse by the fact that there are several database files and their blocks end up interleaved.
 So we could improve the layout but we'd have to tweak the reservation logic and allocator and it's not completely clear to me how. One thing to note is that currently, ext3 *is* in fact doing delayed allocation for writes via mmap. We just never called it like that and never bothered to do proper space estimation...

Quoted 18 lines
Quoted 6 lines
Quoted 3 lines

3) Keep a global counter of sparse blocks which are mapped at mmap() time, and update it as blocks are allocated, or when the region is freed at munmap() time.

  Here again I see the problem that mapping all file blocks at mmap time is rather expensive and so does not seem viable to me. Also the overestimation of needed blocks could be rather huge.

When I did ext2 delayed allocation back in, err, 2001 I had considerable trouble working out how many blocks to actually reserve for a file block, because it also had to reserve the indirect blocks. One file block allocation can result in reserving four disk blocks! And iirc it was not possible with existing in-core data structures to work out whether all four blocks needed reserving until the actual block allocation had occurred.  So I ended up reserving the worst-case number of indirects, based upon the file offset.  If the disk ran out of "space" I'd do a forced writeback to empty all the reservations and would then take a look to see if the disk was _really_ out of space.

Quoted 2 lines

Is all of this an issue with this work?  If so, what approach did you take?

Quoted 16 lines

 Yeah, I've spotted exactly the same problem. How I decided to solve it in the end is that in memory we keep track of each indirect block that has delay-allocated buffer under it. This allows us to reserve space for each indirect block at most once (I didn't bother with making the accounting precise for double or triple indirect blocks so when I need to reserve space for indirect block, I reserve the whole path just to be sure). This pushes the error in estimation to rather acceptable range for reasonably common workloads - the error can still be 50% for workloads which use just one data block in each indirect block but even in this case the absolute number of blocks falsely reserved is small.
 The cost is of course increased complexity of the code, the memory spent for tracking those indirect blocks (32 bytes per indirect block), and some time for lookups in the RB-tree of the structures. At least the nice thing is that when there are no delay-allocated blocks, there isn't any overhead (tree is empty).

How about allocating *only* the indirect blocks on page fault. IMHO it seems like a fair mixture of high quota accuracy, low complexity of the accounting code and low file fragmentation (only indirect may be a bit further away from data).

Quoted 6 lines

In my snapshot patches I use the @create arg to get_blocks_handle() to pass commands just like "allocate only indirect blocks". The patch is rather simple. I can prepare it for ext3 if you like.

Amir.

Here is the indirect allocation patch.
The following debugfs dump shows the difference between a 1G file allocated by dd (indirect interleaved with data) and by mmap (indirect sequential before data).
(I did not test performance and I ignored SIGBUS at the end of mmap file allocation)

debugfs:  stat dd.1G
Inode: 15   Type: regular    Mode:  0644   Flags: 0x0
Generation: 4035748347    Version: 0x00000000
User:     0   Group:     0   Size: 1073741824
File ACL: 0    Directory ACL: 0
Links: 1   Blockcount: 2099208
Fragment:  Address: 0    Number: 0    Size: 0
ctime: 0x4cb5d1a9 -- Wed Oct 13 17:35:05 2010
atime: 0x4cb5d199 -- Wed Oct 13 17:34:49 2010
mtime: 0x4cb5d1a9 -- Wed Oct 13 17:35:05 2010
Size of extra inode fields: 4

BLOCKS:
(0-11):16384-16395, (IND):16396, (12-134):16397-16519, (135-641):17037-17543, (642-1035):17792-18185, (DIND):18186, (IND):18187, (10
36-1279):18188-18431, (1280-1284):1311235-1311239, (1285-2059):1334197-1334971, (IND):1334972, (2060-3083):1334973-1335996, (IND):13
35997, (3084-4107):1335998-1337021, (IND):1337022, (4108-5131):1337023-1338046, (IND):1338047, (5132-6155):1338048-1339071, (IND):13
39072, (6156-7179):1339073-1340096, (IND):1340097, (7180-8203):1340098-1341121, (IND):1341122, (8204-9227):1341123-1342146, (IND):13
42147, (9228-10251):1342148-1343171, (IND):1343172, (10252-10566):1343173-1343487, (10567-11275):1344008-1344716, (IND):1344717, (11
276-12299):1344718-1345741, (IND):1345742, (12300-13323):1345743-1346766, (IND):1346767, (13324-14347):1346768-1347791, (IND):134779
2, (14348-15371):1347793-1348816, (IND):1348817, (15372-16395):1348818-1349841, (IND):1349842, (16396-17419):1349843-1350866, (IND):
...
debugfs:

debugfs:  stat mmap.1G
Inode: 14   Type: regular    Mode:  0644   Flags: 0x0
Generation: 1442185090    Version: 0x00000000
User:     0   Group:     0   Size: 1073741824
File ACL: 0    Directory ACL: 0
Links: 1   Blockcount: 1968016
Fragment:  Address: 0    Number: 0    Size: 0
ctime: 0x4cb5d044 -- Wed Oct 13 17:29:08 2010
atime: 0x4cb5bf81 -- Wed Oct 13 16:17:37 2010
mtime: 0x4cb5d025 -- Wed Oct 13 17:28:37 2010
Size of extra inode fields: 4

BLOCKS:
(DIND):14336, (IND):14337, (16384-16395):14360-14371, (IND):14338, (16396-16481):14372-14457, (16482-17153):14600-15271, (17154-1741 9):16520-16785, (IND):14339, (17420-17670):16786-17036, (17671-17675):1081859-1081863, (17676-18443):1086089-1086856, (IND):14340, (
18444-19467):1086857-1087880, (IND):14341, (19468-20491):1087881-1088904, (IND):14342, (20492-21515):1088905-1089928, (IND):14343, ( 21516-22539):1089929-1090952, (IND):14344, (22540-23563):1090953-1091976, (IND):14345, (23564-24587):1091977-1093000, (IND):14346, ( 24588-25611):1093001-1094024, (IND):14347, (25612-26635):1094025-1095048, (IND):14348, (26636-27659):1095049-1096072, (IND):14349, ( 27660-28683):1096073-1097096, (IND):14472, (28684-29707):1097097-1098120, (IND):15496, (29708-30731):1098121-1099144, (IND):17544, ( 30732-31755):1099145-1100168, (IND):17545, (31756-32779):1100169-1101192, (IND):17546, (32780-33803):1101193-1102216, (IND):17547, (
...
debugfs:

Allocate file indirect blocks on page_mkwrite().

This is a sample patch to be merged with Jan Kara's ext3 delayed allocation patches. Some of the code was taken from Jan's patches for testing only. This patch is for kernel 2.6.35.6.

On page_mkwrite(), we allocate indirect blocks if needed and leave the data blocks unallocated. Jan's patches take care of reserving space for the data.

--------------------------------------------------------------------------------

fs/buffer.c +6 -4
diff -Nuarp a/fs/buffer.c b/fs/buffer.c
@@ -1687,8 +1687,9 @@ static int __block_write_full_page(struc
 			if (buffer_new(bh)) {
 				/* blockdev mappings never come here */
 				clear_buffer_new(bh);
-				unmap_underlying_metadata(bh->b_bdev,
-							bh->b_blocknr);
+				if (buffer_mapped(bh))
+					unmap_underlying_metadata(bh->b_bdev,
+								bh->b_blocknr);
 			}
 		}
 		bh = bh->b_this_page;
@@ -1873,7 +1874,8 @@ static int __block_prepare_write(struct
 			if (err)
 				break;
 			if (buffer_new(bh)) {
-				unmap_underlying_metadata(bh->b_bdev,
+				if (buffer_mapped(bh))
+					unmap_underlying_metadata(bh->b_bdev,
 							bh->b_blocknr);
 				if (PageUptodate(page)) {
 					clear_buffer_new(bh);
@@ -2592,7 +2594,7 @@ int nobh_write_begin_newtrunc(struct fil
 			goto failed;
 		if (!buffer_mapped(bh))
 			is_mapped_to_disk = 0;
-		if (buffer_new(bh))
+		if (buffer_new(bh) && buffer_mapped(bh))
 			unmap_underlying_metadata(bh->b_bdev, bh->b_blocknr);
 		if (PageUptodate(page)) {
 			set_buffer_uptodate(bh);
fs/ext3/file.c +18 -1
diff -Nuarp a/fs/ext3/file.c b/fs/ext3/file.c
@@ -52,6 +52,23 @@ static int ext3_release_file (struct ino
 	return 0;
 }
 
+static const struct vm_operations_struct ext3_file_vm_ops = {
+	.fault          = filemap_fault,
+	.page_mkwrite   = ext3_page_mkwrite,
+};
+
+static int ext3_file_mmap(struct file *file, struct vm_area_struct *vma)
+{
+	struct address_space *mapping = file->f_mapping;
+
+	if (!mapping->a_ops->readpage)
+		return -ENOEXEC;
+	file_accessed(file);
+	vma->vm_ops = &ext3_file_vm_ops;
+	vma->vm_flags |= VM_CAN_NONLINEAR;
+	return 0;
+}
+
 const struct file_operations ext3_file_operations = {
 	.llseek		= generic_file_llseek,
 	.read		= do_sync_read,
@@ -62,7 +79,7 @@ const struct file_operations ext3_file_o
 #ifdef CONFIG_COMPAT
 	.compat_ioctl	= ext3_compat_ioctl,
 #endif
-	.mmap		= generic_file_mmap,
+	.mmap		= ext3_file_mmap,
 	.open		= dquot_file_open,
 	.release	= ext3_release_file,
 	.fsync		= ext3_sync_file,
fs/ext3/inode.c +64 -5

126 lines not on this page · raw message

include/linux/ext3_fs.h +1 -0
diff -Nuarp a/include/linux/ext3_fs.h b/include/linux/ext3_fs.h
@@ -909,6 +909,7 @@ extern void ext3_get_inode_flags(struct
 extern void ext3_set_aops(struct inode *inode);
 extern int ext3_fiemap(struct inode *inode, struct fiemap_extent_info *fieinfo,
 		       u64 start, u64 len);
+extern int ext3_page_mkwrite(struct vm_area_struct *vma, struct vm_fault *vmf);
 
 /* ioctl.c */
 extern long ext3_ioctl(struct file *, unsigned int, unsigned long);

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

author reviewer
#13 lore raw
Quoted 48 lines · Amir G.
Quoted 31 lines · Amir G.
Quoted 13 lines · Jan Kara
Quoted 11 lines

When I did ext2 delayed allocation back in, err, 2001 I had considerable trouble working out how many blocks to actually reserve for a file block, because it also had to reserve the indirect blocks. One file block allocation can result in reserving four disk blocks! And iirc it was not possible with existing in-core data structures to work out whether all four blocks needed reserving until the actual block allocation had occurred.  So I ended up reserving the worst-case number of indirects, based upon the file offset.  If the disk ran out of "space" I'd do a forced writeback to empty all the reservations and would then take a look to see if the disk was _really_ out of space.

Quoted 2 lines

Is all of this an issue with this work?  If so, what approach did you take?

Quoted 16 lines

 Yeah, I've spotted exactly the same problem. How I decided to solve it in the end is that in memory we keep track of each indirect block that has delay-allocated buffer under it. This allows us to reserve space for each indirect block at most once (I didn't bother with making the accounting precise for double or triple indirect blocks so when I need to reserve space for indirect block, I reserve the whole path just to be sure). This pushes the error in estimation to rather acceptable range for reasonably common workloads - the error can still be 50% for workloads which use just one data block in each indirect block but even in this case the absolute number of blocks falsely reserved is small.
 The cost is of course increased complexity of the code, the memory spent for tracking those indirect blocks (32 bytes per indirect block), and some time for lookups in the RB-tree of the structures. At least the nice thing is that when there are no delay-allocated blocks, there isn't any overhead (tree is empty).

Quoted 8 lines

How about allocating *only* the indirect blocks on page fault. IMHO it seems like a fair mixture of high quota accuracy, low complexity of the accounting code and low file fragmentation (only indirect may be a bit further away from data).

In my snapshot patches I use the @create arg to get_blocks_handle() to pass commands just like "allocate only indirect blocks". The patch is rather simple. I can prepare it for ext3 if you like.

Here is the indirect allocation patch.
The following debugfs dump shows the difference between a 1G file allocated by dd (indirect interleaved with data) and by mmap (indirect sequential before data).
(I did not test performance and I ignored SIGBUS at the end of mmap file allocation)

...

Quoted 9 lines

Allocate file indirect blocks on page_mkwrite().

This is a sample patch to be merged with Jan Kara's ext3 delayed allocation patches. Some of the code was taken from Jan's patches for testing only. This patch is for kernel 2.6.35.6.

On page_mkwrite(), we allocate indirect blocks if needed and leave the data blocks unallocated. Jan's patches take care of reserving space for the data.

Thanks for the idea and the patch.

Yes, this is one of the trade-off options. But it's not that simple.
There's a problem with with truncate coming after page_mkwrite but before the allocation happens. See:

ext3_page_mkwrite() for page index 70
-> allocates the indirect block (or just sees that it's allocated
and does nothing)
- marks buffer as delayed
...
truncate to index 80
- sees indirect block has no more blocks allocated and removes it

ext3_writepage() for index 70
- would like to allocate block for index 70 but indirect block does not exist. Bugger.

So you have to somehow track that indirect block has some delayed
allocation pending - and that is the most complex part of my patch. The rest is rather simple...
Actually, there are also other ways to track that indirect block has the
delayed allocation pending. For example if we could do a disk format change, we could simply reserve say block number 1 or -1 to indicate delayed allocated block and everything would be much simpler. But I don't think we really can (it would be an incompatible disk format change).
Hmm, using radix tree dirty tag could also work for that -- when the
range covered by an indirect block has some dirty pages we know that we shouldn't delete it because it's going to be used soon. But it's subtle because we rely on the fact that radix tree dirty tag is cleared only in set_page_writeback() which is after the get_block() call while page dirty flag is already cleared before the writepage() (and thus get_block()) call -- I originally discared this idea because I forgot about this tag handling subtlety.

Honza

Signature · 6 lines
Jan Kara <[email protected]>
SUSE Labs, CR
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html