[PATCH RFC 00/14] Qgroup reserved space fixing framework

[PATCH RFC 00/14] Qgroup reserved space fixing framework

[Qu Wenruo]

!!!!!!WARNING START!!!!!!
These patch is just a WIP patchset, although it fixed a qgroup reserved
space leaking bug in normal COW case, it still lacks fix for other
corner case, like NODATACOW or prealloc case, and a lot of old
facilities are not cleaned up yet.

The reason to send the WIP patchset is to check if the patchset has some
deep structure bug, to avoid another rework after the whole patchset is
finished
!!!!!!WARNING END!!!!!!

Although we have already reworked btrfs qgroup accounting part in
v4.2-rc1, but qgroup reserve part still has a problem of leaking
reserved space.

[[BUG]]
One of the most common case to trigger the bug is the following method:
1) Enable quota
2) Limit excl of qgroup 5 to 16M
3) Write [0,2M) of a file inside subvol 5 10 times without sync

EQUOT will be triggered at about the 8th write.

[[CAUSE]]
The problem is caused by the fact that qgroup will reserve space even
the data space is already reserved.

In above reproducer, even time we buffered write [0,2M) qgroup will
reserve 2M space, but in fact, at the 1st time, we have already reserved
2M and from then on, we don't need to reserved any data space as we are
only writing [0,2M).

Also, the reserved space will only be freed *ONCE* when its backref is
run at commit_transaction() time.

That's causing the reserved space leaking.

[[FIX]]
The fix is not a simple one, as currently btrfs_qgroup_reserve() follow
the very bad btrfs space allocating principle:
  Allocate as much as you needed, even it's not fully used.

So in the patchset, we introduce a lot of facilities:
1) Per inode data rsv map
   Record which range of a file has already been reserved.
   Dirty range will be released when the range is written into disk.
   And for any request to reserve space on already reserved range, just
   skip it to avoid 

2) Delayed ref head qgroup members
   After a range of data is written into disk, we can't keep the dirty
   range in data rsv map or just release reserved space.

   If we keep dirty range in data rsv map, next write will consider
   there is no need to reserve space, but new write will be cowed, and
   cause another extent to take qgroup space.
   So if keep dirty range, it'll cause qgroup accounting to exceed
   limit.

   On the other hand, if just release and free the reserved space, we
   can still exceed the limit by allowing over-reserve.

   So here, we must only release the range, but keep the reserved space
   recorded in other place.
   With the new qgroup accounting framework, only delayed_ref_head is
   safe and will be run at the same time as btrfs qgroup accounting.

3) New delalloc_reserve_space/check_data_free_space facilities to
   support accurate reserve space.
   Unlike old implement, which consider it enough by only using
   num_bytes.
   New facilities all need a exact range [start, start + len) to reserve
   space.

More detailed info can be found in each commit message and source
commend.

Qu Wenruo (14):
  btrfs: qgroup: New function declaration for new reserve implement
  btrfs: qgroup: Implement data_rsv_map init/free functions
  btrfs: qgroup: Introduce new function to search most left reserve
    range
  btrfs: qgroup: Introduce function to insert non-overlap reserve range
  btrfs: qgroup: Introduce function to reserve data range per inode
  btrfs: qgroup: Introduce btrfs_qgroup_reserve_data function
  btrfs: qgroup: Introduce function to release reserved range
  btrfs: qgroup: Introduce function to release/free reserved data range
  btrfs: delayed_ref: Add new function to record reserved space into    
    delayed ref
  btrfs: delayed_ref: release and free qgroup reserved at proper timing
  btrfs: qgroup: Introduce new functions to reserve/free metadata
  btrfs: qgroup: Use new metadata reservation.
  btrfs: extent-tree: Add new verions of btrfs_check_data_free_space
  btrfs: Use new check_data_free_space for buffered write

 fs/btrfs/btrfs_inode.h |   6 +
 fs/btrfs/ctree.h       |   5 +
 fs/btrfs/delayed-ref.c |  29 +++
 fs/btrfs/delayed-ref.h |  14 ++
 fs/btrfs/disk-io.c     |   1 +
 fs/btrfs/extent-tree.c |  68 +++--
 fs/btrfs/file.c        |  22 +-
 fs/btrfs/inode.c       |  20 ++
 fs/btrfs/qgroup.c      | 658 ++++++++++++++++++++++++++++++++++++++++++++++++-
 fs/btrfs/qgroup.h      |  21 +-
 fs/btrfs/transaction.c |  34 +--
 fs/btrfs/transaction.h |   1 -
 12 files changed, 820 insertions(+), 59 deletions(-)

-- 
2.5.1

[PATCH RFC 01/14] btrfs: qgroup: New function declaration for new reserve implement

[Qu Wenruo]

Add new structures and functions for new qgroup reserve implement dirty
phase.
Which will focus on avoiding over-reserve as in that case, which means
for already reserved dirty space range, we won't reserve space again.

This patch adds the needed structure declaration and comments.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/btrfs_inode.h |  4 ++++
 fs/btrfs/qgroup.c      | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/qgroup.h      |  3 +++
 3 files changed, 65 insertions(+)

diff --git a/fs/btrfs/btrfs_inode.h b/fs/btrfs/btrfs_inode.h
index 0ef5cc1..6d799b8 100644
--- a/fs/btrfs/btrfs_inode.h
+++ b/fs/btrfs/btrfs_inode.h
@@ -24,6 +24,7 @@
 #include "extent_io.h"
 #include "ordered-data.h"
 #include "delayed-inode.h"
+#include "qgroup.h"
 
 /*
  * ordered_data_close is set by truncate when a file that used
@@ -193,6 +194,9 @@ struct btrfs_inode {
 	struct timespec i_otime;
 
 	struct inode vfs_inode;
+
+	/* qgroup dirty map for data space reserve */
+	struct btrfs_qgroup_data_rsv_map *qgroup_rsv_map;
 };
 
 extern unsigned char btrfs_filetype_table[];
diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 1667567..640106a 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -91,6 +91,64 @@ struct btrfs_qgroup {
 	u64 new_refcnt;
 };
 
+/*
+ * Record one range of reserved space.
+ */
+struct data_rsv_range {
+	struct rb_node node;
+	u64 start;
+	u64 len;
+};
+
+/*
+ * Record per inode reserved range.
+ * This is mainly used to resolve reserved space leaking problem.
+ * One of the cause is the mismatch with reserve and free.
+ *
+ * New qgroup will handle reserve in two phase.
+ * 1) Dirty phase.
+ *    Pages are just marked dirty, but not written to disk.
+ * 2) Flushed phase
+ *    Pages are written to disk, but transaction is not committed yet.
+ *
+ * At Diryt phase, we only need to focus on avoiding over-reserve.
+ *
+ * The idea is like below.
+ * 1) Write [0,8K)
+ * 0	4K	8K	12K	16K
+ * |////////////|
+ * Reserve +8K, total reserved: 8K
+ *
+ * 2) Write [0,4K)
+ * 0	4K	8K	12K	16K
+ * |////////////|
+ * Reserve 0, total reserved 8K
+ *
+ * 3) Write [12K,16K)
+ * 0	4K	8K	12K	16K
+ * |////////////|	|///////|
+ * Reserve +4K, tocal reserved 12K
+ *
+ * 4) Flush [0,8K)
+ * Can happen without commit transaction, like fallocate will trigger the
+ * write.
+ * 0	4K	8K	12K	16K
+ * 			|///////|
+ * Reserve 0, tocal reserved 12K
+ * As the extent is written to disk, not dirty any longer, the range get
+ * removed.
+ * But as its delayed_refs is not run, its reserved space will not be freed.
+ * And things continue to Flushed phase.
+ *
+ * By this method, we can avoid over-reserve, which will lead to reserved
+ * space leak.
+ */
+struct btrfs_qgroup_data_rsv_map {
+	struct rb_root root;
+	u64 reserved;
+	spinlock_t lock;
+};
+
 static void btrfs_qgroup_update_old_refcnt(struct btrfs_qgroup *qg, u64 seq,
 					   int mod)
 {
diff --git a/fs/btrfs/qgroup.h b/fs/btrfs/qgroup.h
index 6387dcf..2f863a4 100644
--- a/fs/btrfs/qgroup.h
+++ b/fs/btrfs/qgroup.h
@@ -33,6 +33,9 @@ struct btrfs_qgroup_extent_record {
 	struct ulist *old_roots;
 };
 
+/* For per-inode dirty range reserve */
+struct btrfs_qgroup_data_rsv_map;
+
 int btrfs_quota_enable(struct btrfs_trans_handle *trans,
 		       struct btrfs_fs_info *fs_info);
 int btrfs_quota_disable(struct btrfs_trans_handle *trans,
-- 
2.5.1

[PATCH RFC 02/14] btrfs: qgroup: Implement data_rsv_map init/free functions

[Qu Wenruo]

New functions btrfs_qgroup_init/free_data_rsv_map() to init/free data
reserve map.

Data reserve map is used to mark which range already holds reserved
space, to avoid current reserved space leak.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/btrfs_inode.h |  2 ++
 fs/btrfs/inode.c       | 10 +++++++
 fs/btrfs/qgroup.c      | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/qgroup.h      |  3 ++
 4 files changed, 95 insertions(+)

diff --git a/fs/btrfs/btrfs_inode.h b/fs/btrfs/btrfs_inode.h
index 6d799b8..c2da3a9 100644
--- a/fs/btrfs/btrfs_inode.h
+++ b/fs/btrfs/btrfs_inode.h
@@ -197,6 +197,8 @@ struct btrfs_inode {
 
 	/* qgroup dirty map for data space reserve */
 	struct btrfs_qgroup_data_rsv_map *qgroup_rsv_map;
+	/* lock to ensure rsv_map will only be initialized once */
+	spinlock_t qgroup_init_lock;
 };
 
 extern unsigned char btrfs_filetype_table[];
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index 855935f..763197f 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -8871,6 +8871,14 @@ struct inode *btrfs_alloc_inode(struct super_block *sb)
 	INIT_LIST_HEAD(&ei->delalloc_inodes);
 	RB_CLEAR_NODE(&ei->rb_node);
 
+	/*
+	 * Init qgroup info to empty, as they will be initialized at write
+	 * time.
+	 * This behavior is needed for enable quota later case.
+	 */
+	spin_lock_init(&ei->qgroup_init_lock);
+	ei->qgroup_rsv_map = NULL;
+
 	return inode;
 }
 
@@ -8928,6 +8936,8 @@ void btrfs_destroy_inode(struct inode *inode)
 			btrfs_put_ordered_extent(ordered);
 		}
 	}
+	/* free and check data rsv map */
+	btrfs_qgroup_free_data_rsv_map(inode);
 	inode_tree_del(inode);
 	btrfs_drop_extent_cache(inode, 0, (u64)-1, 0);
 free:
diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 640106a..2e9a93f 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2511,3 +2511,83 @@ btrfs_qgroup_rescan_resume(struct btrfs_fs_info *fs_info)
 		btrfs_queue_work(fs_info->qgroup_rescan_workers,
 				 &fs_info->qgroup_rescan_work);
 }
+
+/*
+ * Init data_rsv_map for a given inode.
+ *
+ * This is needed at write time as quota can be disabled and then enabled
+ */
+int btrfs_qgroup_init_data_rsv_map(struct inode *inode)
+{
+	struct btrfs_inode *binode = BTRFS_I(inode);
+	struct btrfs_root *root = binode->root;
+	struct btrfs_qgroup_data_rsv_map *dirty_map;
+
+	if (!root->fs_info->quota_enabled || !is_fstree(root->objectid))
+		return 0;
+
+	spin_lock(&binode->qgroup_init_lock);
+	/* Quick route for init */
+	if (likely(binode->qgroup_rsv_map))
+		goto out;
+	spin_unlock(&binode->qgroup_init_lock);
+
+	/*
+	 * Slow allocation route
+	 *
+	 * TODO: Use kmem_cache to speedup allocation
+	 */
+	dirty_map = kmalloc(sizeof(*dirty_map), GFP_NOFS);
+	if (!dirty_map)
+		return -ENOMEM;
+
+	dirty_map->reserved = 0;
+	dirty_map->root = RB_ROOT;
+	spin_lock_init(&dirty_map->lock);
+
+	/* Lock again to ensure no one has already init it before */
+	spin_lock(&binode->qgroup_init_lock);
+	if (binode->qgroup_rsv_map) {
+		spin_unlock(&binode->qgroup_init_lock);
+		kfree(dirty_map);
+		return 0;
+	}
+	binode->qgroup_rsv_map = dirty_map;
+out:
+	spin_unlock(&binode->qgroup_init_lock);
+	return 0;
+}
+
+void btrfs_qgroup_free_data_rsv_map(struct inode *inode)
+{
+	struct btrfs_inode *binode = BTRFS_I(inode);
+	struct btrfs_root *root = binode->root;
+	struct btrfs_qgroup_data_rsv_map *dirty_map = binode->qgroup_rsv_map;
+	struct rb_node *node;
+
+	/*
+	 * this function is called at inode destroy routine, so no concurrency
+	 * will happen, no need to get the lock.
+	 */
+	if (!dirty_map)
+		return;
+
+	/* insanity check */
+	WARN_ON(!root->fs_info->quota_enabled || !is_fstree(root->objectid));
+
+	/* Did we leak some space? */
+	WARN_ON(dirty_map->reserved || !RB_EMPTY_ROOT(&dirty_map->root));
+
+	btrfs_qgroup_free(root, dirty_map->reserved);
+	spin_lock(&dirty_map->lock);
+	while ((node = rb_first(&dirty_map->root)) != NULL) {
+		struct data_rsv_range *range;
+
+		range = rb_entry(node, struct data_rsv_range, node);
+		rb_erase(node, &dirty_map->root);
+		kfree(range);
+	}
+	spin_unlock(&dirty_map->lock);
+	kfree(dirty_map);
+	binode->qgroup_rsv_map = NULL;
+}
diff --git a/fs/btrfs/qgroup.h b/fs/btrfs/qgroup.h
index 2f863a4..c87b7dc 100644
--- a/fs/btrfs/qgroup.h
+++ b/fs/btrfs/qgroup.h
@@ -84,4 +84,7 @@ int btrfs_verify_qgroup_counts(struct btrfs_fs_info *fs_info, u64 qgroupid,
 			       u64 rfer, u64 excl);
 #endif
 
+/* for qgroup reserve */
+int btrfs_qgroup_init_data_rsv_map(struct inode *inode);
+void btrfs_qgroup_free_data_rsv_map(struct inode *inode);
 #endif /* __BTRFS_QGROUP__ */
-- 
2.5.1

[PATCH RFC 03/14] btrfs: qgroup: Introduce new function to search most left reserve range

[Qu Wenruo]

Introduce the new function to search the most left reserve range in a
reserve map.

It provides the basis for later reserve map implement.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 2e9a93f..e19fe6a 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2513,6 +2513,42 @@ btrfs_qgroup_rescan_resume(struct btrfs_fs_info *fs_info)
 }
 
 /*
+ * Return the nearest left range of given start
+ * No ensure about the range will cover start.
+ */
+static struct data_rsv_range *
+find_reserve_range(struct btrfs_qgroup_data_rsv_map *map, u64 start)
+{
+	struct rb_node **p = &map->root.rb_node;
+	struct rb_node *parent = NULL;
+	struct rb_node *prev = NULL;
+	struct data_rsv_range *range = NULL;
+
+	while (*p) {
+		parent = *p;
+		range = rb_entry(parent, struct data_rsv_range, node);
+		if (range->start < start)
+			p = &(*p)->rb_right;
+		else if (range->start > start)
+			p = &(*p)->rb_left;
+		else
+			return range;
+	}
+
+	/* empty tree */
+	if (!parent)
+		return NULL;
+	if (range->start <= start)
+		return range;
+
+	prev = rb_prev(parent);
+	/* Already most left one */
+	if (!prev)
+		return range;
+	return rb_entry(prev, struct data_rsv_range, node);
+}
+
+/*
  * Init data_rsv_map for a given inode.
  *
  * This is needed at write time as quota can be disabled and then enabled
-- 
2.5.1

[PATCH RFC 04/14] btrfs: qgroup: Introduce function to insert non-overlap reserve range

[Qu Wenruo]

New function insert_data_ranges() will insert non-overlap reserve ranges
into reserve map.

It provides the basis for later qgroup reserve map implement.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 123 insertions(+)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index e19fe6a..90f5c4b 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2549,6 +2549,129 @@ find_reserve_range(struct btrfs_qgroup_data_rsv_map *map, u64 start)
 }
 
 /*
+ * Insert one data range
+ * [start,len) here won't overflap with each other.
+ *
+ * Return 0 if range is inserted and tmp is not used.
+ * Return > 0 if range is inserted and tmp is used.
+ * No catchable error case. Only possible error will cause BUG_ON() as
+ * that's logical error.
+ */
+static int insert_data_range(struct btrfs_qgroup_data_rsv_map *map,
+			     struct data_rsv_range *tmp,
+			     u64 start, u64 len)
+{
+	struct rb_node **p = &map->root.rb_node;
+	struct rb_node *parent = NULL;
+	struct rb_node *tmp_node = NULL;
+	struct data_rsv_range *range = NULL;
+	struct data_rsv_range *prev_range = NULL;
+	struct data_rsv_range *next_range = NULL;
+	int prev_merged = 0;
+	int next_merged = 0;
+	int ret = 0;
+
+	while (*p) {
+		parent = *p;
+		range = rb_entry(parent, struct data_rsv_range, node);
+		if (range->start < start)
+			p = &(*p)->rb_right;
+		else if (range->start > start)
+			p = &(*p)->rb_left;
+		else
+			BUG_ON(1);
+	}
+
+	/* Empty tree, goto isolated case */
+	if (!range)
+		goto insert_isolated;
+
+	/* get adjusted ranges */
+	if (range->start < start) {
+		prev_range = range;
+		tmp_node = rb_next(parent);
+		if (tmp)
+			next_range = rb_entry(tmp_node, struct data_rsv_range,
+					      node);
+	} else {
+		next_range = range;
+		tmp_node = rb_prev(parent);
+		if (tmp)
+			prev_range = rb_entry(tmp_node, struct data_rsv_range,
+					      node);
+	}
+
+	/* try to merge with previous and next ranges */
+	if (prev_range) {
+		if (prev_range->start + prev_range->len == start) {
+			prev_range->len += len;
+			prev_merged = 1;
+		}
+	}
+	if (next_range) {
+		/* prev and next with start,len can be merged */
+		if (prev_merged && start + len == next_range->start) {
+			prev_range->len += next_range->len;
+			next_merged = 1;
+		} else if (start + len == next_range->start) {
+			next_range->start = start;
+			next_range->len += len;
+			rb_erase(&next_range->node, &map->root);
+			kfree(next_range);
+			next_merged = 1;
+		}
+	}
+
+insert_isolated:
+	/* isolated case, need to insert range now */
+	if (!next_merged && !prev_merged) {
+		BUG_ON(!tmp);
+
+		tmp->start = start;
+		tmp->len = len;
+		rb_link_node(&tmp->node, parent, p);
+		rb_insert_color(&tmp->node, &map->root);
+		ret = 1;
+	}
+	return ret;
+}
+
+/*
+ * insert reserve range and merge them if possible
+ *
+ * Return 0 if all inserted and tmp not used
+ * Return > 0 if all inserted and tmp used
+ * No catchable error return value.
+ */
+static int insert_data_ranges(struct btrfs_qgroup_data_rsv_map *map,
+			      struct data_rsv_range *tmp,
+			      struct ulist *insert_list)
+{
+	struct ulist_node *unode;
+	struct ulist_iterator uiter;
+	int tmp_used = 0;
+	int ret = 0;
+
+	ULIST_ITER_INIT(&uiter);
+	while ((unode = ulist_next(insert_list, &uiter))) {
+		ret = insert_data_range(map, tmp, unode->val, unode->aux);
+
+		/*
+		 * insert_data_range() won't return error return value,
+		 * no need to hanle <0 case.
+		 *
+		 * Also tmp should be used at most one time, so clear it to
+		 * NULL to cooperate with sanity check in insert_data_range().
+		 */
+		if (ret > 0) {
+			tmp_used = 1;
+			tmp = NULL;
+		}
+	}
+	return tmp_used;
+}
+
+/*
  * Init data_rsv_map for a given inode.
  *
  * This is needed at write time as quota can be disabled and then enabled
-- 
2.5.1

Re: [PATCH RFC 00/14] Qgroup reserved space fixing framework

[Qu Wenruo]

Again, later patches are blocked by the Exchange mail server.....

I'll send it again using another mailbox(quwenruo.btrfs@gmx.com).

Thanks,
Qu

Qu Wenruo wrote on 2015/09/01 15:21 +0800:
> !!!!!!WARNING START!!!!!!
> These patch is just a WIP patchset, although it fixed a qgroup reserved
> space leaking bug in normal COW case, it still lacks fix for other
> corner case, like NODATACOW or prealloc case, and a lot of old
> facilities are not cleaned up yet.
>
> The reason to send the WIP patchset is to check if the patchset has some
> deep structure bug, to avoid another rework after the whole patchset is
> finished
> !!!!!!WARNING END!!!!!!
>
> Although we have already reworked btrfs qgroup accounting part in
> v4.2-rc1, but qgroup reserve part still has a problem of leaking
> reserved space.
>
> [[BUG]]
> One of the most common case to trigger the bug is the following method:
> 1) Enable quota
> 2) Limit excl of qgroup 5 to 16M
> 3) Write [0,2M) of a file inside subvol 5 10 times without sync
>
> EQUOT will be triggered at about the 8th write.
>
> [[CAUSE]]
> The problem is caused by the fact that qgroup will reserve space even
> the data space is already reserved.
>
> In above reproducer, even time we buffered write [0,2M) qgroup will
> reserve 2M space, but in fact, at the 1st time, we have already reserved
> 2M and from then on, we don't need to reserved any data space as we are
> only writing [0,2M).
>
> Also, the reserved space will only be freed *ONCE* when its backref is
> run at commit_transaction() time.
>
> That's causing the reserved space leaking.
>
> [[FIX]]
> The fix is not a simple one, as currently btrfs_qgroup_reserve() follow
> the very bad btrfs space allocating principle:
>    Allocate as much as you needed, even it's not fully used.
>
> So in the patchset, we introduce a lot of facilities:
> 1) Per inode data rsv map
>     Record which range of a file has already been reserved.
>     Dirty range will be released when the range is written into disk.
>     And for any request to reserve space on already reserved range, just
>     skip it to avoid
>
> 2) Delayed ref head qgroup members
>     After a range of data is written into disk, we can't keep the dirty
>     range in data rsv map or just release reserved space.
>
>     If we keep dirty range in data rsv map, next write will consider
>     there is no need to reserve space, but new write will be cowed, and
>     cause another extent to take qgroup space.
>     So if keep dirty range, it'll cause qgroup accounting to exceed
>     limit.
>
>     On the other hand, if just release and free the reserved space, we
>     can still exceed the limit by allowing over-reserve.
>
>     So here, we must only release the range, but keep the reserved space
>     recorded in other place.
>     With the new qgroup accounting framework, only delayed_ref_head is
>     safe and will be run at the same time as btrfs qgroup accounting.
>
> 3) New delalloc_reserve_space/check_data_free_space facilities to
>     support accurate reserve space.
>     Unlike old implement, which consider it enough by only using
>     num_bytes.
>     New facilities all need a exact range [start, start + len) to reserve
>     space.
>
> More detailed info can be found in each commit message and source
> commend.
>
> Qu Wenruo (14):
>    btrfs: qgroup: New function declaration for new reserve implement
>    btrfs: qgroup: Implement data_rsv_map init/free functions
>    btrfs: qgroup: Introduce new function to search most left reserve
>      range
>    btrfs: qgroup: Introduce function to insert non-overlap reserve range
>    btrfs: qgroup: Introduce function to reserve data range per inode
>    btrfs: qgroup: Introduce btrfs_qgroup_reserve_data function
>    btrfs: qgroup: Introduce function to release reserved range
>    btrfs: qgroup: Introduce function to release/free reserved data range
>    btrfs: delayed_ref: Add new function to record reserved space into
>      delayed ref
>    btrfs: delayed_ref: release and free qgroup reserved at proper timing
>    btrfs: qgroup: Introduce new functions to reserve/free metadata
>    btrfs: qgroup: Use new metadata reservation.
>    btrfs: extent-tree: Add new verions of btrfs_check_data_free_space
>    btrfs: Use new check_data_free_space for buffered write
>
>   fs/btrfs/btrfs_inode.h |   6 +
>   fs/btrfs/ctree.h       |   5 +
>   fs/btrfs/delayed-ref.c |  29 +++
>   fs/btrfs/delayed-ref.h |  14 ++
>   fs/btrfs/disk-io.c     |   1 +
>   fs/btrfs/extent-tree.c |  68 +++--
>   fs/btrfs/file.c        |  22 +-
>   fs/btrfs/inode.c       |  20 ++
>   fs/btrfs/qgroup.c      | 658 ++++++++++++++++++++++++++++++++++++++++++++++++-
>   fs/btrfs/qgroup.h      |  21 +-
>   fs/btrfs/transaction.c |  34 +--
>   fs/btrfs/transaction.h |   1 -
>   12 files changed, 820 insertions(+), 59 deletions(-)
>

[PATCH RFC 05/14] btrfs: qgroup: Introduce function to reserve data range per inode

[Qu Wenruo]

Introduce new function reserve_data_range().
This function will find non-overlap range and to insert it into reserve
map using previously introduced funtions.

This provides the basis for later per inode reserve map implement.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 92 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 92 insertions(+)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 90f5c4b..3948882 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2672,6 +2672,98 @@ static int insert_data_ranges(struct btrfs_qgroup_data_rsv_map *map,
 }
 
 /*
+ * Check qgroup limit and insert dirty range into reserve_map.
+ *
+ * Must be called with map->lock hold
+ */
+static int reserve_data_range(struct btrfs_root *root,
+			      struct btrfs_qgroup_data_rsv_map *map,
+			      struct data_rsv_range *tmp,
+			      struct ulist *insert_list, u64 start, u64 len)
+{
+	struct data_rsv_range *range;
+	u64 cur_start = 0;
+	u64 cur_len = 0;
+	u64 reserve = 0;
+	int ret = 0;
+
+	range = find_reserve_range(map, start);
+	/* empty tree, insert the whole range */
+	if (!range) {
+		reserve = len;
+		ret = ulist_add(insert_list, start, len, GFP_ATOMIC);
+		if (ret < 0)
+			return ret;
+		goto insert;
+	}
+
+	/* For case range is covering the leading part */
+	if (range->start <= start && range->start + range->len > start)
+		cur_start = range->start + range->len;
+	else
+		cur_start = start;
+
+	/*
+	 * iterate until the end of the range.
+	 * Like the following:
+	 *
+	 * 	|<--------desired---------------------->|
+	 *|//1//|	|////2///|	|///3///|	<- exists
+	 * Then we will need to insert the following
+	 * 	|\\\4\\\|	 |\\\5\\|	|\\\6\\\|
+	 * And only add qgroup->reserved for rang 4,5,6.
+	 */
+	while (cur_start < start + len) {
+		struct rb_node *next_node;
+		u64 next_start;
+
+		if (range->start + range->len <= cur_start) {
+			/*
+			 * Move to next range if current range is before
+			 * cur_start
+			 * e.g range is 1, cur_start is the end of range 1.
+			 */
+			next_node = rb_next(&range->node);
+			if (!next_node) {
+				/*
+				 * no next range, fill the rest
+				 * e.g range is 3, cur_start is end of range 3.
+				 */
+				cur_len = start + len - cur_start;
+				next_start = start + len;
+			} else {
+				range = rb_entry(next_node,
+						 struct data_rsv_range, node);
+				cur_len = min(range->start, start + len) -
+					  cur_start;
+				next_start = range->start + range->len;
+			}
+		} else {
+			/*
+			 * current range is already after cur_start
+			 * e.g range is 2, cur_start is end of range 1.
+			 */
+			cur_len = range->start - cur_len;
+			next_start = range->start + range->len;
+		}
+		reserve += cur_len;
+		ret = ulist_add(insert_list, cur_start, cur_len, GFP_ATOMIC);
+		if (ret < 0)
+			return ret;
+
+		cur_start = next_start;
+	}
+insert:
+	ret = btrfs_qgroup_reserve(root, reserve);
+	if (ret < 0)
+		return ret;
+	/* ranges must be inserted after we are sure it has enough space */
+	ret = insert_data_ranges(map, tmp, insert_list);
+	map->reserved += reserve;
+	return ret;
+}
+
+/*
  * Init data_rsv_map for a given inode.
  *
  * This is needed at write time as quota can be disabled and then enabled
-- 
2.5.1

[PATCH RFC 06/14] btrfs: qgroup: Introduce btrfs_qgroup_reserve_data function

[Qu Wenruo]

This new function will do all the hard work to reserve precious space
for a write.

The overall work flow will be the following.

File A already has some dirty pages:

0	4K	8K	12K	16K
|///////|	|///////|

And then, someone want to write some data into range [4K, 16K).
	|<------desired-------->|

Unlike the old and wrong implement, which reserve 12K, this function
will only reserve space for newly dirty part:
	|\\\\\\\|	|\\\\\\\|
Which only takes 8K reserve space, as other part has already allocated
their own reserve space.

So the final reserve map will be:
|///////////////////////////////|

This provides the basis to resolve the long existing qgroup limit bug.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/qgroup.h |  1 +
 2 files changed, 49 insertions(+)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 3948882..31ddc6d 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2764,6 +2764,54 @@ insert:
 }
 
 /*
+ * TODO: to handle nocow case, like NODATACOW or write into prealloc space
+ * along with other mixed case.
+ * Like write 2M, first 1M can be nocowed, but next 1M is on hole and need COW.
+ */
+int btrfs_qgroup_reserve_data(struct inode *inode, u64 start, u64 len)
+{
+	struct btrfs_inode *binode = BTRFS_I(inode);
+	struct btrfs_root *root = binode->root;
+	struct btrfs_qgroup_data_rsv_map *reserve_map;
+	struct data_rsv_range *tmp = NULL;
+	struct ulist *insert_list;
+	int ret;
+
+	if (!root->fs_info->quota_enabled || !is_fstree(root->objectid) ||
+	    len == 0)
+		return 0;
+
+	if (!binode->qgroup_rsv_map) {
+		ret = btrfs_qgroup_init_data_rsv_map(inode);
+		if (ret < 0)
+			return ret;
+	}
+	reserve_map = binode->qgroup_rsv_map;
+	insert_list = ulist_alloc(GFP_NOFS);
+	if (!insert_list)
+		return -ENOMEM;
+	tmp = kzalloc(sizeof(*tmp), GFP_NOFS);
+	if (!tmp) {
+		ulist_free(insert_list);
+		return -ENOMEM;
+	}
+
+	spin_lock(&reserve_map->lock);
+	ret = reserve_data_range(root, reserve_map, tmp, insert_list, start,
+				 len);
+	if (ret < 0) {
+		kfree(tmp);
+		goto out;
+	}
+	if (ret == 0)
+		kfree(tmp);
+out:
+	spin_unlock(&reserve_map->lock);
+	ulist_free(insert_list);
+	return ret;
+}
+
+/*
  * Init data_rsv_map for a given inode.
  *
  * This is needed at write time as quota can be disabled and then enabled
diff --git a/fs/btrfs/qgroup.h b/fs/btrfs/qgroup.h
index c87b7dc..366b853 100644
--- a/fs/btrfs/qgroup.h
+++ b/fs/btrfs/qgroup.h
@@ -87,4 +87,5 @@ int btrfs_verify_qgroup_counts(struct btrfs_fs_info *fs_info, u64 qgroupid,
 /* for qgroup reserve */
 int btrfs_qgroup_init_data_rsv_map(struct inode *inode);
 void btrfs_qgroup_free_data_rsv_map(struct inode *inode);
+int btrfs_qgroup_reserve_data(struct inode *inode, u64 start, u64 len);
 #endif /* __BTRFS_QGROUP__ */
-- 
2.5.1

[PATCH RFC 07/14] btrfs: qgroup: Introduce function to release reserved range

[Qu Wenruo]

Introduce new function release_data_range() to release reserved ranges.
It will iterate through all existing ranges and remove/shrink them.

Note this function will not free reserved space, as the range can be
released in the following conditions:
1) The dirty range gets written to disk.
   In this case, reserved range will be released but reserved bytes
   will not be freed until the delayed_ref is run.

2) Truncate
   In this case, dirty ranges will be released and reserved bytes will
   also be freed.

So the new function won't free reserved space, but record them into
parameter if called needs.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 130 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 130 insertions(+)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 31ddc6d..eee07c2 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2811,6 +2811,136 @@ out:
 	return ret;
 }
 
+/* Small helper used in release_data_range() to update rsv map */
+static inline void __update_rsv(struct btrfs_qgroup_data_rsv_map *map,
+				u64 *reserved, u64 cur_rsv)
+{
+	if (reserved)
+		*reserved += cur_rsv;
+	if (WARN_ON(map->reserved < cur_rsv))
+		map->reserved = 0;
+	else
+		map->reserved -= cur_rsv;
+}
+
+/*
+ * Release the range [start, start + len) from rsv map.
+ *
+ * The behavior should be much like reserve_data_range().
+ * @tmp: the allocated memory for case which need to split existing
+ *       range into two.
+ * @reserved: the number of bytes that may need to free
+ * Return > 0 if 'tmp' memory is used and release range successfully
+ * Return 0 if 'tmp' memory is not used and release range successfully
+ * Return < 0 for error
+ */
+static int release_data_range(struct btrfs_qgroup_data_rsv_map *map,
+			      struct data_rsv_range *tmp,
+			      u64 start, u64 len, u64 *reserved)
+{
+	struct data_rsv_range *range;
+	u64 cur_rsv;
+	int ret = 0;
+
+	range = find_reserve_range(map, start);
+	/* empty tree, just return */
+	if (!range)
+		return 0;
+	/*
+	 * For split case
+	 * 		|<----desired---->|
+	 * |////////////////////////////////////////////|
+	 * In this case, we need to insert one new range.
+	 */
+	if (range->start < start && range->start + range->len > start + len) {
+		u64 new_start = start + len;
+		u64 new_len = range->start + range->len - start - len;
+
+		cur_rsv = len;
+		if (reserved)
+			*reserved += cur_rsv;
+		map->reserved -= cur_rsv;
+
+		range->len = start - range->start;
+		ret = insert_data_range(map, tmp, new_start, new_len);
+		WARN_ON(ret <= 0);
+		return 1;
+	}
+
+	/*
+	 * Iterate until the end of the range and free release all
+	 * reserved data from map.
+	 * We iterate by existing range, as that will makes codes a
+	 * little more clean.
+	 *
+	 * 	|<---------desired------------------------>|
+	 * |//1//|	|//2//|		|//3//|		|//4//|
+	 */
+	while (range->start < start + len) {
+		struct rb_node *next = NULL;
+
+		/*
+		 * 		|<---desired---->|
+		 * |///////|
+		 */
+		if (unlikely(range->start + range->len <= start))
+			goto next;
+
+		/*
+		 * 	|<----desired---->|
+		 * |///////|
+		 */
+		if (range->start < start &&
+		    range->start + range->len > start) {
+			cur_rsv = range->start + range->len - start;
+			__update_rsv(map, reserved, cur_rsv);
+
+			range->len = start - range->start;
+			goto next;
+		}
+
+		/*
+		 * 	|<--desired-->|
+		 * 	   |/////|
+		 * Including same start/end case, so other case don't need
+		 * to check start/end equal case and don't need bother
+		 * deleting range.
+		 */
+		if (range->start >= start &&
+		    range->start + range->len <= start + len) {
+			cur_rsv = range->len;
+			__update_rsv(map, reserved, cur_rsv);
+
+			next = rb_next(&range->node);
+			rb_erase(&range->node, &map->root);
+			kfree(range);
+			goto next;
+
+		}
+
+		/*
+		 * 	|<--desired-->|
+		 * 		|///////|
+		 */
+		if (range->start < start + len &&
+		    range->start + range->len > start + len) {
+			cur_rsv = start + len - range->start;
+			__update_rsv(map, reserved, cur_rsv);
+
+			range->start = start + len;
+			range->len = range->start + range->len - start - len;
+			goto next;
+		}
+next:
+		if (!next)
+			next = rb_next(&range->node);
+		if (!next)
+			break;
+		range = rb_entry(next, struct data_rsv_range, node);
+	}
+	return 0;
+}
+
 /*
  * Init data_rsv_map for a given inode.
  *
-- 
2.5.1

[PATCH RFC 08/14] btrfs: qgroup: Introduce function to release/free reserved data range

[Qu Wenruo]

Introduce functions btrfs_qgroup_release/free_data() to release/free
reserved data range.

Release means, just remove the data range from data rsv map, but doesn't
free the reserved space.
Free means not only remove data range, but also free reserved space.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/qgroup.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/qgroup.h |  2 ++
 2 files changed, 48 insertions(+)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index eee07c2..7ccbd4c 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2941,6 +2941,52 @@ next:
 	return 0;
 }
 
+static int __btrfs_qgroup_release_data(struct inode *inode, u64 start, u64 len,
+				       int free_reserved)
+{
+	struct data_rsv_range *tmp;
+	struct btrfs_qgroup_data_rsv_map *map;
+	u64 reserved = 0;
+	int ret;
+
+	spin_lock(&BTRFS_I(inode)->qgroup_init_lock);
+	map = BTRFS_I(inode)->qgroup_rsv_map;
+	spin_unlock(&BTRFS_I(inode)->qgroup_init_lock);
+	if (!map)
+		return 0;
+
+	tmp = kmalloc(sizeof(*tmp), GFP_NOFS);
+	if (!tmp)
+		return -ENOMEM;
+	ret = release_data_range(map, tmp, start, len, &reserved);
+	/* release_data_range() won't fail only check if memory is used */
+	if (ret == 0)
+		kfree(tmp);
+	if (free_reserved)
+		btrfs_qgroup_free(BTRFS_I(inode)->root, reserved);
+	return 0;
+}
+
+/*
+ * Caller should be truncate/invalidate_page.
+ * As it will release the reserved data.
+ */
+int btrfs_qgroup_free_data(struct inode *inode, u64 start, u64 len)
+{
+	return __btrfs_qgroup_release_data(inode, start, len, 1);
+}
+
+/*
+ * Caller should be finish_ordered_io
+ * As qgroup accouting happens at commit time, for data written to disk
+ * its reserved space should not be freed until commit.
+ * Or we may beyond the limit.
+ */
+int btrfs_qgroup_release_data(struct inode *inode, u64 start, u64 len)
+{
+	return __btrfs_qgroup_release_data(inode, start, len, 0);
+}
+
 /*
  * Init data_rsv_map for a given inode.
  *
diff --git a/fs/btrfs/qgroup.h b/fs/btrfs/qgroup.h
index 366b853..8e69dc1 100644
--- a/fs/btrfs/qgroup.h
+++ b/fs/btrfs/qgroup.h
@@ -88,4 +88,6 @@ int btrfs_verify_qgroup_counts(struct btrfs_fs_info *fs_info, u64 qgroupid,
 int btrfs_qgroup_init_data_rsv_map(struct inode *inode);
 void btrfs_qgroup_free_data_rsv_map(struct inode *inode);
 int btrfs_qgroup_reserve_data(struct inode *inode, u64 start, u64 len);
+int btrfs_qgroup_release_data(struct inode *inode, u64 start, u64 len);
+int btrfs_qgroup_free_data(struct inode *inode, u64 start, u64 len);
 #endif /* __BTRFS_QGROUP__ */
-- 
2.5.1

[PATCH RFC 09/14] btrfs: delayed_ref: Add new function to record reserved space into delayed ref

[Qu Wenruo]

Add new function btrfs_add_delayed_qgroup_reserve() function to record
how much space is reserved for that extent.

As btrfs only accounts qgroup at run_delayed_refs() time, so newly
allocated extent should keep the reserved space until then.

So add needed function with related members to do it.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/delayed-ref.c | 29 +++++++++++++++++++++++++++++
 fs/btrfs/delayed-ref.h | 14 ++++++++++++++
 2 files changed, 43 insertions(+)

diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c
index ac3e81d..bd9b63b 100644
--- a/fs/btrfs/delayed-ref.c
+++ b/fs/btrfs/delayed-ref.c
@@ -476,6 +476,8 @@ add_delayed_ref_head(struct btrfs_fs_info *fs_info,
 	INIT_LIST_HEAD(&head_ref->ref_list);
 	head_ref->processing = 0;
 	head_ref->total_ref_mod = count_mod;
+	head_ref->qgroup_reserved = 0;
+	head_ref->qgroup_ref_root = 0;
 
 	/* Record qgroup extent info if provided */
 	if (qrecord) {
@@ -746,6 +748,33 @@ int btrfs_add_delayed_data_ref(struct btrfs_fs_info *fs_info,
 	return 0;
 }
 
+int btrfs_add_delayed_qgroup_reserve(struct btrfs_fs_info *fs_info,
+				     struct btrfs_trans_handle *trans,
+				     u64 ref_root, u64 bytenr, u64 num_bytes)
+{
+	struct btrfs_delayed_ref_root *delayed_refs;
+	struct btrfs_delayed_ref_head *ref_head;
+	int ret = 0;
+
+	if (!fs_info->quota_enabled || !is_fstree(ref_root))
+		return 0;
+
+	delayed_refs = &trans->transaction->delayed_refs;
+
+	spin_lock(&delayed_refs->lock);
+	ref_head = find_ref_head(&delayed_refs->href_root, bytenr, 0);
+	if (!ref_head) {
+		ret = -ENOENT;
+		goto out;
+	}
+	WARN_ON(ref_head->qgroup_reserved || ref_head->qgroup_ref_root);
+	ref_head->qgroup_ref_root = ref_root;
+	ref_head->qgroup_reserved = num_bytes;
+out:
+	spin_unlock(&delayed_refs->lock);
+	return ret;
+}
+
 int btrfs_add_delayed_extent_op(struct btrfs_fs_info *fs_info,
 				struct btrfs_trans_handle *trans,
 				u64 bytenr, u64 num_bytes,
diff --git a/fs/btrfs/delayed-ref.h b/fs/btrfs/delayed-ref.h
index 13fb5e6..d4c41e2 100644
--- a/fs/btrfs/delayed-ref.h
+++ b/fs/btrfs/delayed-ref.h
@@ -113,6 +113,17 @@ struct btrfs_delayed_ref_head {
 	int total_ref_mod;
 
 	/*
+	 * For qgroup reserved space freeing.
+	 *
+	 * ref_root and reserved will be recorded after
+	 * BTRFS_ADD_DELAYED_EXTENT is called.
+	 * And will be used to free reserved qgroup space at
+	 * run_delayed_refs() time.
+	 */
+	u64 qgroup_ref_root;
+	u64 qgroup_reserved;
+
+	/*
 	 * when a new extent is allocated, it is just reserved in memory
 	 * The actual extent isn't inserted into the extent allocation tree
 	 * until the delayed ref is processed.  must_insert_reserved is
@@ -242,6 +253,9 @@ int btrfs_add_delayed_data_ref(struct btrfs_fs_info *fs_info,
 			       u64 owner, u64 offset, int action,
 			       struct btrfs_delayed_extent_op *extent_op,
 			       int no_quota);
+int btrfs_add_delayed_qgroup_reserve(struct btrfs_fs_info *fs_info,
+				     struct btrfs_trans_handle *trans,
+				     u64 ref_root, u64 bytenr, u64 num_bytes);
 int btrfs_add_delayed_extent_op(struct btrfs_fs_info *fs_info,
 				struct btrfs_trans_handle *trans,
 				u64 bytenr, u64 num_bytes,
-- 
2.5.1

[PATCH RFC 10/14] btrfs: delayed_ref: release and free qgroup reserved at proper timing

[Qu Wenruo]

Qgroup reserved space needs to be released from inode dirty map and get
freed at different timing:

1) Release when the metadata is written into tree
After corresponding metadata is written into tree, any newer write will
be COWed(don't include NOCOW case yet).
So we must release its range from inode dirty range map, or we will
forget to reserve needed range, causing accounting exceeding the limit.

2) Free reserved bytes when delayed ref is run
When delayed refs are run, qgroup accounting will follow soon and turn
the reserved bytes into rfer/excl numbers.
As run_delayed_refs and qgroup accounting are all done at
commit_transaction() time, we are safe to free reserved space in
run_delayed_ref time().

With these timing to release/free reserved space, we should be able to
resolve the long existing qgroup reserve space leak problem.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c |  4 ++++
 fs/btrfs/inode.c       | 10 ++++++++++
 fs/btrfs/qgroup.c      |  5 ++---
 fs/btrfs/qgroup.h      |  8 +++++++-
 4 files changed, 23 insertions(+), 4 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 38b76cc..4d9b01b 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -2277,6 +2277,10 @@ static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
 						      node->num_bytes);
 			}
 		}
+
+		/* Also free its reserved qgroup space */
+		btrfs_qgroup_free_refroot(root->fs_info, head->qgroup_ref_root,
+					  head->qgroup_reserved);
 		return ret;
 	}
 
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index 763197f..37e45d5 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -2112,6 +2112,16 @@ static int insert_reserved_file_extent(struct btrfs_trans_handle *trans,
 	ret = btrfs_alloc_reserved_file_extent(trans, root,
 					root->root_key.objectid,
 					btrfs_ino(inode), file_pos, &ins);
+	if (ret < 0)
+		goto out;
+	/*
+	 * Release the reserved range from inode dirty range map, and
+	 * move it to delayed ref codes, as now accounting only happens at
+	 * commit_transaction() time.
+	 */
+	btrfs_qgroup_release_data(inode, file_pos, ram_bytes);
+	ret = btrfs_add_delayed_qgroup_reserve(root->fs_info, trans,
+			root->objectid, disk_bytenr, ram_bytes);
 out:
 	btrfs_free_path(path);
 
diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 7ccbd4c..4ac2f84 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -2141,14 +2141,13 @@ out:
 	return ret;
 }
 
-void btrfs_qgroup_free(struct btrfs_root *root, u64 num_bytes)
+void btrfs_qgroup_free_refroot(struct btrfs_fs_info *fs_info,
+			       u64 ref_root, u64 num_bytes)
 {
 	struct btrfs_root *quota_root;
 	struct btrfs_qgroup *qgroup;
-	struct btrfs_fs_info *fs_info = root->fs_info;
 	struct ulist_node *unode;
 	struct ulist_iterator uiter;
-	u64 ref_root = root->root_key.objectid;
 	int ret = 0;
 
 	if (!is_fstree(ref_root))
diff --git a/fs/btrfs/qgroup.h b/fs/btrfs/qgroup.h
index 8e69dc1..49fa15e 100644
--- a/fs/btrfs/qgroup.h
+++ b/fs/btrfs/qgroup.h
@@ -75,7 +75,13 @@ int btrfs_qgroup_inherit(struct btrfs_trans_handle *trans,
 			 struct btrfs_fs_info *fs_info, u64 srcid, u64 objectid,
 			 struct btrfs_qgroup_inherit *inherit);
 int btrfs_qgroup_reserve(struct btrfs_root *root, u64 num_bytes);
-void btrfs_qgroup_free(struct btrfs_root *root, u64 num_bytes);
+void btrfs_qgroup_free_refroot(struct btrfs_fs_info *fs_info,
+			       u64 ref_root, u64 num_bytes);
+static inline void btrfs_qgroup_free(struct btrfs_root *root, u64 num_bytes)
+{
+	return btrfs_qgroup_free_refroot(root->fs_info, root->objectid,
+					 num_bytes);
+}
 
 void assert_qgroups_uptodate(struct btrfs_trans_handle *trans);
 
-- 
2.5.1

[PATCH RFC 11/14] btrfs: qgroup: Introduce new functions to reserve/free metadata

[Qu Wenruo]

Introduce new functions btrfs_qgroup_reserve/free_meta() to reserve/free
metadata reserved space.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/ctree.h   |  3 +++
 fs/btrfs/disk-io.c |  1 +
 fs/btrfs/qgroup.c  | 40 ++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/qgroup.h  |  4 ++++
 4 files changed, 48 insertions(+)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 80a9aef..9ce0df1 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -1948,6 +1948,9 @@ struct btrfs_root {
 	int send_in_progress;
 	struct btrfs_subvolume_writers *subv_writers;
 	atomic_t will_be_snapshoted;
+
+	/* For qgroup metadata space reserve */
+	atomic_t qgroup_meta_rsv;
 };
 
 struct btrfs_ioctl_defrag_range_args {
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 3f43bfea..b60a4ec 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -1259,6 +1259,7 @@ static void __setup_root(u32 nodesize, u32 sectorsize, u32 stripesize,
 	atomic_set(&root->orphan_inodes, 0);
 	atomic_set(&root->refs, 1);
 	atomic_set(&root->will_be_snapshoted, 0);
+	atomic_set(&root->qgroup_meta_rsv, 0);
 	root->log_transid = 0;
 	root->log_transid_committed = -1;
 	root->last_log_commit = 0;
diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 4ac2f84..f3a1047 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -3065,3 +3065,43 @@ void btrfs_qgroup_free_data_rsv_map(struct inode *inode)
 	kfree(dirty_map);
 	binode->qgroup_rsv_map = NULL;
 }
+
+int btrfs_qgroup_reserve_meta(struct btrfs_root *root, int num_bytes)
+{
+	int ret;
+
+	if (!root->fs_info->quota_enabled || !is_fstree(root->objectid) ||
+	    num_bytes == 0)
+		return 0;
+
+	BUG_ON(num_bytes != round_down(num_bytes, root->nodesize));
+	ret = btrfs_qgroup_reserve(root, num_bytes);
+	if (ret < 0)
+		return ret;
+	atomic_add(num_bytes, &root->qgroup_meta_rsv);
+	return ret;
+}
+
+void btrfs_qgroup_free_meta_all(struct btrfs_root *root)
+{
+	int reserved;
+
+	if (!root->fs_info->quota_enabled || !is_fstree(root->objectid))
+		return;
+
+	reserved = atomic_xchg(&root->qgroup_meta_rsv, 0);
+	if (reserved == 0)
+		return;
+	btrfs_qgroup_free(root, reserved);
+}
+
+void btrfs_qgroup_free_meta(struct btrfs_root *root, int num_bytes)
+{
+	if (!root->fs_info->quota_enabled || !is_fstree(root->objectid))
+		return;
+
+	BUG_ON(num_bytes != round_down(num_bytes, root->nodesize));
+	WARN_ON(atomic_read(&root->qgroup_meta_rsv) < num_bytes);
+	atomic_sub(num_bytes, &root->qgroup_meta_rsv);
+	btrfs_qgroup_free(root, num_bytes);
+}
diff --git a/fs/btrfs/qgroup.h b/fs/btrfs/qgroup.h
index 49fa15e..2d507c8 100644
--- a/fs/btrfs/qgroup.h
+++ b/fs/btrfs/qgroup.h
@@ -96,4 +96,8 @@ void btrfs_qgroup_free_data_rsv_map(struct inode *inode);
 int btrfs_qgroup_reserve_data(struct inode *inode, u64 start, u64 len);
 int btrfs_qgroup_release_data(struct inode *inode, u64 start, u64 len);
 int btrfs_qgroup_free_data(struct inode *inode, u64 start, u64 len);
+
+int btrfs_qgroup_reserve_meta(struct btrfs_root *root, int num_bytes);
+void btrfs_qgroup_free_meta_all(struct btrfs_root *root);
+void btrfs_qgroup_free_meta(struct btrfs_root *root, int num_bytes);
 #endif /* __BTRFS_QGROUP__ */
-- 
2.5.1

[PATCH RFC 12/14] btrfs: qgroup: Use new metadata reservation.

[Qu Wenruo]

As we have the new metadata reservation functions, use them to replace
the old btrfs_qgroup_reserve() call for metadata.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/extent-tree.c | 14 ++++++--------
 fs/btrfs/transaction.c | 34 ++++++----------------------------
 fs/btrfs/transaction.h |  1 -
 3 files changed, 12 insertions(+), 37 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 4d9b01b..ce78410 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -5244,7 +5244,7 @@ int btrfs_subvolume_reserve_metadata(struct btrfs_root *root,
 	if (root->fs_info->quota_enabled) {
 		/* One for parent inode, two for dir entries */
 		num_bytes = 3 * root->nodesize;
-		ret = btrfs_qgroup_reserve(root, num_bytes);
+		ret = btrfs_qgroup_reserve_meta(root, num_bytes);
 		if (ret)
 			return ret;
 	} else {
@@ -5262,10 +5262,8 @@ int btrfs_subvolume_reserve_metadata(struct btrfs_root *root,
 	if (ret == -ENOSPC && use_global_rsv)
 		ret = btrfs_block_rsv_migrate(global_rsv, rsv, num_bytes);
 
-	if (ret) {
-		if (*qgroup_reserved)
-			btrfs_qgroup_free(root, *qgroup_reserved);
-	}
+	if (ret && *qgroup_reserved)
+		btrfs_qgroup_free_meta(root, *qgroup_reserved);
 
 	return ret;
 }
@@ -5426,15 +5424,15 @@ int btrfs_delalloc_reserve_metadata(struct inode *inode, u64 num_bytes)
 	spin_unlock(&BTRFS_I(inode)->lock);
 
 	if (root->fs_info->quota_enabled) {
-		ret = btrfs_qgroup_reserve(root, nr_extents * root->nodesize);
+		ret = btrfs_qgroup_reserve_meta(root,
+				nr_extents * root->nodesize);
 		if (ret)
 			goto out_fail;
 	}
 
 	ret = reserve_metadata_bytes(root, block_rsv, to_reserve, flush);
 	if (unlikely(ret)) {
-		if (root->fs_info->quota_enabled)
-			btrfs_qgroup_free(root, nr_extents * root->nodesize);
+		btrfs_qgroup_free_meta(root, nr_extents * root->nodesize);
 		goto out_fail;
 	}
 
diff --git a/fs/btrfs/transaction.c b/fs/btrfs/transaction.c
index c0f18e7..e9656b4 100644
--- a/fs/btrfs/transaction.c
+++ b/fs/btrfs/transaction.c
@@ -444,13 +444,10 @@ start_transaction(struct btrfs_root *root, u64 num_items, unsigned int type,
 	 * the appropriate flushing if need be.
 	 */
 	if (num_items > 0 && root != root->fs_info->chunk_root) {
-		if (root->fs_info->quota_enabled &&
-		    is_fstree(root->root_key.objectid)) {
-			qgroup_reserved = num_items * root->nodesize;
-			ret = btrfs_qgroup_reserve(root, qgroup_reserved);
-			if (ret)
-				return ERR_PTR(ret);
-		}
+		qgroup_reserved = num_items * root->nodesize;
+		ret = btrfs_qgroup_reserve_meta(root, qgroup_reserved);
+		if (ret)
+			return ERR_PTR(ret);
 
 		num_bytes = btrfs_calc_trans_metadata_size(root, num_items);
 		/*
@@ -519,7 +516,6 @@ again:
 	h->block_rsv = NULL;
 	h->orig_rsv = NULL;
 	h->aborted = 0;
-	h->qgroup_reserved = 0;
 	h->delayed_ref_elem.seq = 0;
 	h->type = type;
 	h->allocating_chunk = false;
@@ -544,7 +540,6 @@ again:
 		h->bytes_reserved = num_bytes;
 		h->reloc_reserved = reloc_reserved;
 	}
-	h->qgroup_reserved = qgroup_reserved;
 
 got_it:
 	btrfs_record_root_in_trans(h, root);
@@ -562,8 +557,7 @@ alloc_fail:
 		btrfs_block_rsv_release(root, &root->fs_info->trans_block_rsv,
 					num_bytes);
 reserve_fail:
-	if (qgroup_reserved)
-		btrfs_qgroup_free(root, qgroup_reserved);
+	btrfs_qgroup_free_meta(root, qgroup_reserved);
 	return ERR_PTR(ret);
 }
 
@@ -780,15 +774,6 @@ static int __btrfs_end_transaction(struct btrfs_trans_handle *trans,
 			must_run_delayed_refs = 2;
 	}
 
-	if (trans->qgroup_reserved) {
-		/*
-		 * the same root has to be passed here between start_transaction
-		 * and end_transaction. Subvolume quota depends on this.
-		 */
-		btrfs_qgroup_free(trans->root, trans->qgroup_reserved);
-		trans->qgroup_reserved = 0;
-	}
-
 	btrfs_trans_release_metadata(trans, root);
 	trans->block_rsv = NULL;
 
@@ -1203,6 +1188,7 @@ static noinline int commit_fs_roots(struct btrfs_trans_handle *trans,
 			spin_lock(&fs_info->fs_roots_radix_lock);
 			if (err)
 				break;
+			btrfs_qgroup_free_meta_all(root);
 		}
 	}
 	spin_unlock(&fs_info->fs_roots_radix_lock);
@@ -1811,10 +1797,6 @@ int btrfs_commit_transaction(struct btrfs_trans_handle *trans,
 
 	btrfs_trans_release_metadata(trans, root);
 	trans->block_rsv = NULL;
-	if (trans->qgroup_reserved) {
-		btrfs_qgroup_free(root, trans->qgroup_reserved);
-		trans->qgroup_reserved = 0;
-	}
 
 	cur_trans = trans->transaction;
 
@@ -2163,10 +2145,6 @@ cleanup_transaction:
 	btrfs_trans_release_metadata(trans, root);
 	btrfs_trans_release_chunk_metadata(trans);
 	trans->block_rsv = NULL;
-	if (trans->qgroup_reserved) {
-		btrfs_qgroup_free(root, trans->qgroup_reserved);
-		trans->qgroup_reserved = 0;
-	}
 	btrfs_warn(root->fs_info, "Skipping commit of aborted transaction.");
 	if (current->journal_info == trans)
 		current->journal_info = NULL;
diff --git a/fs/btrfs/transaction.h b/fs/btrfs/transaction.h
index eb09c20..f46e311 100644
--- a/fs/btrfs/transaction.h
+++ b/fs/btrfs/transaction.h
@@ -103,7 +103,6 @@ struct btrfs_trans_handle {
 	u64 transid;
 	u64 bytes_reserved;
 	u64 chunk_bytes_reserved;
-	u64 qgroup_reserved;
 	unsigned long use_count;
 	unsigned long blocks_reserved;
 	unsigned long blocks_used;
-- 
2.5.1

[PATCH RFC 13/14] btrfs: extent-tree: Add new verions of btrfs_check_data_free_space

[Qu Wenruo]

Add new function __btrfs_check_data_free_space() to do precious space
reservation.

The new function will replace old btrfs_check_data_free_space(), but
until all the change is done, let's just use the new name.

Also, export internal use function btrfs_alloc_data_chunk_ondemand(), as
now qgroup reserve requires precious bytes, which can only be got in
later loop(like fallocate).
But data space info check and data chunk allocate doesn't need to be
that accurate, and can be called at the beginning.

So export it for later operations.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/ctree.h       |  2 ++
 fs/btrfs/extent-tree.c | 50 +++++++++++++++++++++++++++++++++++++++++---------
 2 files changed, 43 insertions(+), 9 deletions(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 9ce0df1..cf5de9c 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -3456,6 +3456,8 @@ enum btrfs_reserve_flush_enum {
 };
 
 int btrfs_check_data_free_space(struct inode *inode, u64 bytes, u64 write_bytes);
+int __btrfs_check_data_free_space(struct inode *inode, u64 start, u64 len);
+int btrfs_alloc_data_chunk_ondemand(struct inode *inode, u64 bytes);
 void btrfs_free_reserved_data_space(struct inode *inode, u64 bytes);
 void btrfs_trans_release_metadata(struct btrfs_trans_handle *trans,
 				struct btrfs_root *root);
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index ce78410..14c4135 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -3826,11 +3826,7 @@ u64 btrfs_get_alloc_profile(struct btrfs_root *root, int data)
 	return ret;
 }
 
-/*
- * This will check the space that the inode allocates from to make sure we have
- * enough space for bytes.
- */
-int btrfs_check_data_free_space(struct inode *inode, u64 bytes, u64 write_bytes)
+int btrfs_alloc_data_chunk_ondemand(struct inode *inode, u64 bytes)
 {
 	struct btrfs_space_info *data_sinfo;
 	struct btrfs_root *root = BTRFS_I(inode)->root;
@@ -3951,19 +3947,55 @@ commit_trans:
 					      data_sinfo->flags, bytes, 1);
 		return -ENOSPC;
 	}
-	ret = btrfs_qgroup_reserve(root, write_bytes);
-	if (ret)
-		goto out;
 	data_sinfo->bytes_may_use += bytes;
 	trace_btrfs_space_reservation(root->fs_info, "space_info",
 				      data_sinfo->flags, bytes, 1);
-out:
 	spin_unlock(&data_sinfo->lock);
 
 	return ret;
 }
 
 /*
+ * This will check the space that the inode allocates from to make sure we have
+ * enough space for bytes.
+ */
+int btrfs_check_data_free_space(struct inode *inode, u64 bytes, u64 write_bytes)
+{
+	struct btrfs_root *root = BTRFS_I(inode)->root;
+	int ret;
+
+	ret = btrfs_alloc_data_chunk_ondemand(inode, bytes);
+	if (ret < 0)
+		return ret;
+	ret = btrfs_qgroup_reserve(root, write_bytes);
+	return ret;
+}
+
+/*
+ * New check_data_free_space() with ability for precious data reserveation
+ * Will replace old btrfs_check_data_free_space(), but for patch split,
+ * add a new function first and then replace it.
+ */
+int __btrfs_check_data_free_space(struct inode *inode, u64 start, u64 len)
+{
+	struct btrfs_root *root = BTRFS_I(inode)->root;
+	int ret;
+
+	/* align the range */
+	len = round_up(start + len, root->sectorsize) -
+	      round_down(start, root->sectorsize);
+	start = round_down(start, root->sectorsize);
+
+	ret = btrfs_alloc_data_chunk_ondemand(inode, len);
+	if (ret < 0)
+		return ret;
+
+	/* Use new btrfs_qgroup_reserve_data to reserve precious data space */
+	ret = btrfs_qgroup_reserve_data(inode, start, len);
+	return ret;
+}
+
+/*
  * Called if we need to clear a data reservation for this inode.
  */
 void btrfs_free_reserved_data_space(struct inode *inode, u64 bytes)
-- 
2.5.1

[PATCH RFC 14/14] btrfs: Use new check_data_free_space for buffered write

[Qu Wenruo]

Use new check_data_free_space for buffered write.

Because nodatacow write won't increase quota account, so unlike only
behavior which does reserve before check nocow, here we check nocow
first and then only reserve data if we can't do nocow write.

Signed-off-by: Qu Wenruo <quwenruo@cn.fujitsu.com>
---
 fs/btrfs/file.c | 22 +++++++++++++---------
 1 file changed, 13 insertions(+), 9 deletions(-)

diff --git a/fs/btrfs/file.c b/fs/btrfs/file.c
index b823fac..c1eec4f 100644
--- a/fs/btrfs/file.c
+++ b/fs/btrfs/file.c
@@ -1510,12 +1510,17 @@ static noinline ssize_t __btrfs_buffered_write(struct file *file,
 		}
 
 		reserve_bytes = num_pages << PAGE_CACHE_SHIFT;
-		ret = btrfs_check_data_free_space(inode, reserve_bytes, write_bytes);
-		if (ret == -ENOSPC &&
-		    (BTRFS_I(inode)->flags & (BTRFS_INODE_NODATACOW |
-					      BTRFS_INODE_PREALLOC))) {
+
+		if (BTRFS_I(inode)->flags & (BTRFS_INODE_NODATACOW |
+					     BTRFS_INODE_PREALLOC)) {
 			ret = check_can_nocow(inode, pos, &write_bytes);
+			if (ret < 0)
+				break;
 			if (ret > 0) {
+				/*
+				 * For nodata cow case, no need to reserve
+				 * data space.
+				 */
 				only_release_metadata = true;
 				/*
 				 * our prealloc extent may be smaller than
@@ -1524,15 +1529,14 @@ static noinline ssize_t __btrfs_buffered_write(struct file *file,
 				num_pages = DIV_ROUND_UP(write_bytes + offset,
 							 PAGE_CACHE_SIZE);
 				reserve_bytes = num_pages << PAGE_CACHE_SHIFT;
-				ret = 0;
-			} else {
-				ret = -ENOSPC;
+				goto reserve_metadata;
 			}
 		}
-
-		if (ret)
+		ret = __btrfs_check_data_free_space(inode, pos, write_bytes);
+		if (ret < 0)
 			break;
 
+reserve_metadata:
 		ret = btrfs_delalloc_reserve_metadata(inode, reserve_bytes);
 		if (ret) {
 			if (!only_release_metadata)
-- 
2.5.1

[PATCH RFC 00/14] Qgroup reserved space fixing framework

[Qu Wenruo]

From: Qu Wenruo <quwenruo@cn.fujitsu.com>

!!!!!!WARNING START!!!!!!
These patch is just a WIP patchset, although it fixed a qgroup reserved
space leaking bug in normal COW case, it still lacks fix for other
corner case, like NODATACOW or prealloc case, and a lot of old
facilities are not cleaned up yet.

The reason to send the WIP patchset is to check if the patchset has some
deep structure bug, to avoid another rework after the whole patchset is
finished
!!!!!!WARNING END!!!!!!

Although we have already reworked btrfs qgroup accounting part in
v4.2-rc1, but qgroup reserve part still has a problem of leaking
reserved space.

[[BUG]]
One of the most common case to trigger the bug is the following method:
1) Enable quota
2) Limit excl of qgroup 5 to 16M
3) Write [0,2M) of a file inside subvol 5 10 times without sync

EQUOT will be triggered at about the 8th write.

[[CAUSE]]
The problem is caused by the fact that qgroup will reserve space even
the data space is already reserved.

In above reproducer, even time we buffered write [0,2M) qgroup will
reserve 2M space, but in fact, at the 1st time, we have already reserved
2M and from then on, we don't need to reserved any data space as we are
only writing [0,2M).

Also, the reserved space will only be freed *ONCE* when its backref is
run at commit_transaction() time.

That's causing the reserved space leaking.

[[FIX]]
The fix is not a simple one, as currently btrfs_qgroup_reserve() follow
the very bad btrfs space allocating principle:
  Allocate as much as you needed, even it's not fully used.

So in the patchset, we introduce a lot of facilities:
1) Per inode data rsv map
   Record which range of a file has already been reserved.
   Dirty range will be released when the range is written into disk.
   And for any request to reserve space on already reserved range, just
   skip it to avoid 

2) Delayed ref head qgroup members
   After a range of data is written into disk, we can't keep the dirty
   range in data rsv map or just release reserved space.

   If we keep dirty range in data rsv map, next write will consider
   there is no need to reserve space, but new write will be cowed, and
   cause another extent to take qgroup space.
   So if keep dirty range, it'll cause qgroup accounting to exceed
   limit.

   On the other hand, if just release and free the reserved space, we
   can still exceed the limit by allowing over-reserve.

   So here, we must only release the range, but keep the reserved space
   recorded in other place.
   With the new qgroup accounting framework, only delayed_ref_head is
   safe and will be run at the same time as btrfs qgroup accounting.

3) New delalloc_reserve_space/check_data_free_space facilities to
   support accurate reserve space.
   Unlike old implement, which consider it enough by only using
   num_bytes.
   New facilities all need a exact range [start, start + len) to reserve
   space.

More detailed info can be found in each commit message and source
commend.

Qu Wenruo (14):
  btrfs: qgroup: New function declaration for new reserve implement
  btrfs: qgroup: Implement data_rsv_map init/free functions
  btrfs: qgroup: Introduce new function to search most left reserve
    range
  btrfs: qgroup: Introduce function to insert non-overlap reserve range
  btrfs: qgroup: Introduce function to reserve data range per inode
  btrfs: qgroup: Introduce btrfs_qgroup_reserve_data function
  btrfs: qgroup: Introduce function to release reserved range
  btrfs: qgroup: Introduce function to release/free reserved data range
  btrfs: delayed_ref: Add new function to record reserved space into    
    delayed ref
  btrfs: delayed_ref: release and free qgroup reserved at proper timing
  btrfs: qgroup: Introduce new functions to reserve/free metadata
  btrfs: qgroup: Use new metadata reservation.
  btrfs: extent-tree: Add new verions of btrfs_check_data_free_space
  btrfs: Use new check_data_free_space for buffered write

 fs/btrfs/btrfs_inode.h |   6 +
 fs/btrfs/ctree.h       |   5 +
 fs/btrfs/delayed-ref.c |  29 +++
 fs/btrfs/delayed-ref.h |  14 ++
 fs/btrfs/disk-io.c     |   1 +
 fs/btrfs/extent-tree.c |  68 +++--
 fs/btrfs/file.c        |  22 +-
 fs/btrfs/inode.c       |  20 ++
 fs/btrfs/qgroup.c      | 658 ++++++++++++++++++++++++++++++++++++++++++++++++-
 fs/btrfs/qgroup.h      |  21 +-
 fs/btrfs/transaction.c |  34 +--
 fs/btrfs/transaction.h |   1 -
 12 files changed, 820 insertions(+), 59 deletions(-)

-- 
2.5.1

[PATCH RFC 00/14] Qgroup reserved space fixing framework

[Qu Wenruo]

!!!!!!WARNING START!!!!!!
These patch is just a WIP patchset, although it fixed a qgroup reserved
space leaking bug in normal COW case, it still lacks fix for other
corner case, like NODATACOW or prealloc case.
And may still cause reserved space to overflow to minus.

The reason to send the WIP patchset is to check if the patchset has some
deep structure bug, to avoid another rework after the whole patchset is
finished
!!!!!!WARNING END!!!!!!

Although we have already reworked btrfs qgroup accounting part in
v4.2-rc1, but qgroup reserve part still has a problem of leaking
reserved space.

[[BUG]]
One of the most common case to trigger the bug is the following method:
1) Enable quota
2) Limit excl of qgroup 5 to 16M
3) Write [0,2M) of a file inside subvol 5 10 times without sync

EQUOT will be triggered at about the 8th write.

[[CAUSE]]
The problem is caused by the fact that qgroup will reserve space even
the data space is already reserved.

In above reproducer, even time we buffered write [0,2M) qgroup will
reserve 2M space, but in fact, at the 1st time, we have already reserved
2M and from then on, we don't need to reserved any data space as we are
only writing [0,2M).

Also, the reserved space will only be freed *ONCE* when its backref is
run at commit_transaction() time.

That's causing the reserved space leaking.

[[FIX]]
The fix is not a simple one, as currently btrfs_qgroup_reserve() follow
the very bad btrfs space allocating principle:
  Allocate as much as you needed, even it's not fully used.

So in the patchset, we introduce a lot of facilities:
1) Per inode data rsv map
   Record which range of a file has already been reserved.
   Dirty range will be released when the range is written into disk.
   And for any request to reserve space on already reserved range, just
   skip it to avoid 

2) Delayed ref head qgroup members
   After a range of data is written into disk, we can't keep the dirty
   range in data rsv map or just release reserved space.

   If we keep dirty range in data rsv map, next write will consider
   there is no need to reserve space, but new write will be cowed, and
   cause another extent to take qgroup space.
   So if keep dirty range, it'll cause qgroup accounting to exceed
   limit.

   On the other hand, if just release and free the reserved space, we
   can still exceed the limit by allowing over-reserve.

   So here, we must only release the range, but keep the reserved space
   recorded in other place.
   With the new qgroup accounting framework, only delayed_ref_head is
   safe and will be run at the same time as btrfs qgroup accounting.

3) New delalloc_reserve_space/check_data_free_space facilities to
   support accurate reserve space.
   Unlike old implement, which consider it enough by only using
   num_bytes.
   New facilities all need a exact range [start, start + len) to reserve
   space.

More detailed info can be found in each commit message and source
commend.

Qu Wenruo (14):
  btrfs: qgroup: New function declaration for new reserve implement
  btrfs: qgroup: Implement data_rsv_map init/free functions
  btrfs: qgroup: Introduce new function to search most left reserve
    range
  btrfs: qgroup: Introduce function to insert non-overlap reserve range
  btrfs: qgroup: Introduce function to reserve data range per inode
  btrfs: qgroup: Introduce btrfs_qgroup_reserve_data function
  btrfs: qgroup: Introduce function to release reserved range
  btrfs: qgroup: Introduce function to release/free reserved data range
  btrfs: delayed_ref: Add new function to record reserved space into    
    delayed ref
  btrfs: delayed_ref: release and free qgroup reserved at proper timing
  btrfs: qgroup: Introduce new functions to reserve/free metadata
  btrfs: qgroup: Use new metadata reservation.
  btrfs: extent-tree: Add new verions of btrfs_check_data_free_space
  btrfs: Use new check_data_free_space for buffered write

 fs/btrfs/btrfs_inode.h |   6 +
 fs/btrfs/ctree.h       |   5 +
 fs/btrfs/delayed-ref.c |  29 +++
 fs/btrfs/delayed-ref.h |  14 ++
 fs/btrfs/disk-io.c     |   1 +
 fs/btrfs/extent-tree.c |  68 +++--
 fs/btrfs/file.c        |  22 +-
 fs/btrfs/inode.c       |  20 ++
 fs/btrfs/qgroup.c      | 658 ++++++++++++++++++++++++++++++++++++++++++++++++-
 fs/btrfs/qgroup.h      |  21 +-
 fs/btrfs/transaction.c |  15 +-
 11 files changed, 820 insertions(+), 39 deletions(-)

-- 
2.5.0

[PATCH RFC 00/14] Qgroup reserved space fixing framework

[Qu Wenruo]

!!!!!!WARNING START!!!!!!
These patch is just a WIP patchset, although it fixed a qgroup reserved
space leaking bug in normal COW case, it still lacks fix for other
corner case, like NODATACOW or prealloc case.
And may still cause reserved space to overflow to minus.

The reason to send the WIP patchset is to check if the patchset has some
deep structure bug, to avoid another rework after the whole patchset is
finished
!!!!!!WARNING END!!!!!!

Although we have already reworked btrfs qgroup accounting part in
v4.2-rc1, but qgroup reserve part still has a problem of leaking
reserved space.

[[BUG]]
One of the most common case to trigger the bug is the following method:
1) Enable quota
2) Limit excl of qgroup 5 to 16M
3) Write [0,2M) of a file inside subvol 5 10 times without sync

EQUOT will be triggered at about the 8th write.

[[CAUSE]]
The problem is caused by the fact that qgroup will reserve space even
the data space is already reserved.

In above reproducer, even time we buffered write [0,2M) qgroup will
reserve 2M space, but in fact, at the 1st time, we have already reserved
2M and from then on, we don't need to reserved any data space as we are
only writing [0,2M).

Also, the reserved space will only be freed *ONCE* when its backref is
run at commit_transaction() time.

That's causing the reserved space leaking.

[[FIX]]
The fix is not a simple one, as currently btrfs_qgroup_reserve() follow
the very bad btrfs space allocating principle:
  Allocate as much as you needed, even it's not fully used.

So in the patchset, we introduce a lot of facilities:
1) Per inode data rsv map
   Record which range of a file has already been reserved.
   Dirty range will be released when the range is written into disk.
   And for any request to reserve space on already reserved range, just
   skip it to avoid 

2) Delayed ref head qgroup members
   After a range of data is written into disk, we can't keep the dirty
   range in data rsv map or just release reserved space.

   If we keep dirty range in data rsv map, next write will consider
   there is no need to reserve space, but new write will be cowed, and
   cause another extent to take qgroup space.
   So if keep dirty range, it'll cause qgroup accounting to exceed
   limit.

   On the other hand, if just release and free the reserved space, we
   can still exceed the limit by allowing over-reserve.

   So here, we must only release the range, but keep the reserved space
   recorded in other place.
   With the new qgroup accounting framework, only delayed_ref_head is
   safe and will be run at the same time as btrfs qgroup accounting.

3) New delalloc_reserve_space/check_data_free_space facilities to
   support accurate reserve space.
   Unlike old implement, which consider it enough by only using
   num_bytes.
   New facilities all need a exact range [start, start + len) to reserve
   space.

More detailed info can be found in each commit message and source
commend.

Qu Wenruo (14):
  btrfs: qgroup: New function declaration for new reserve implement
  btrfs: qgroup: Implement data_rsv_map init/free functions
  btrfs: qgroup: Introduce new function to search most left reserve
    range
  btrfs: qgroup: Introduce function to insert non-overlap reserve range
  btrfs: qgroup: Introduce function to reserve data range per inode
  btrfs: qgroup: Introduce btrfs_qgroup_reserve_data function
  btrfs: qgroup: Introduce function to release reserved range
  btrfs: qgroup: Introduce function to release/free reserved data range
  btrfs: delayed_ref: Add new function to record reserved space into    
    delayed ref
  btrfs: delayed_ref: release and free qgroup reserved at proper timing
  btrfs: qgroup: Introduce new functions to reserve/free metadata
  btrfs: qgroup: Use new metadata reservation.
  btrfs: extent-tree: Add new verions of btrfs_check_data_free_space
  btrfs: Use new check_data_free_space for buffered write

 fs/btrfs/btrfs_inode.h |   6 +
 fs/btrfs/ctree.h       |   5 +
 fs/btrfs/delayed-ref.c |  29 +++
 fs/btrfs/delayed-ref.h |  14 ++
 fs/btrfs/disk-io.c     |   1 +
 fs/btrfs/extent-tree.c |  68 +++--
 fs/btrfs/file.c        |  22 +-
 fs/btrfs/inode.c       |  20 ++
 fs/btrfs/qgroup.c      | 658 ++++++++++++++++++++++++++++++++++++++++++++++++-
 fs/btrfs/qgroup.h      |  21 +-
 fs/btrfs/transaction.c |  15 +-
 11 files changed, 820 insertions(+), 39 deletions(-)

-- 
2.5.0