[PATCH 0/6] reiser4: discard support: "precise discard" aka padding of extents to erase unit boundaries.

[PATCH 0/6] reiser4: discard support: "precise discard" aka padding of extents to erase unit boundaries.

[Ivan Shapovalov]

So, this patchset uses your algorithm of padding/gluing extents to be discarded.
I've added exact allocation primitives (is it what you've been talking about?),
made the discard procedure allocate blocks of all paddings it performs and
fixed an apparent bug in extent gluing which triggered the "edward-1635"
assertion.

Edward Shishkin (1):
  reiser4: iterate over extents in discard_atom

Ivan Shapovalov (5):
  reiser4: block_alloc: split block allocation accounting logic into separate functions for re-use.
  reiser4: block_alloc, plugin/space/bitmap: add a method for "exact" block allocation.
  reiser4: discard: don't be overly smart when gluing extents in discard_sorted_merged_extents().
  reiser4: blocknrlist: add operations blocknr_list_del() and blocknr_list_update_extent().
  reiser4: discard: allocate extent paddings.

 fs/reiser4/block_alloc.c                  | 175 +++++++++----
 fs/reiser4/block_alloc.h                  |   3 +
 fs/reiser4/blocknrlist.c                  |  38 +++
 fs/reiser4/discard.c                      | 410 +++++++++++++++++++++++++++---
 fs/reiser4/discard.h                      |   8 +-
 fs/reiser4/forward.h                      |   1 +
 fs/reiser4/init_super.c                   |   4 +
 fs/reiser4/plugin/space/bitmap.c          |  94 +++++--
 fs/reiser4/plugin/space/bitmap.h          |   3 +
 fs/reiser4/plugin/space/space_allocator.h |  10 +-
 fs/reiser4/super.h                        |   4 +
 fs/reiser4/txnmgr.h                       |   6 +
 12 files changed, 647 insertions(+), 109 deletions(-)

-- 
2.1.3

[PATCH 1/6] reiser4: block_alloc: split block allocation accounting logic into separate functions for re-use.

[Ivan Shapovalov]

This logic is also needed for the "exact" block allocation function which will
be added in the next commit.

Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
---
 fs/reiser4/block_alloc.c | 139 +++++++++++++++++++++++++++++------------------
 1 file changed, 87 insertions(+), 52 deletions(-)

diff --git a/fs/reiser4/block_alloc.c b/fs/reiser4/block_alloc.c
index 324b11c..be1a795 100644
--- a/fs/reiser4/block_alloc.c
+++ b/fs/reiser4/block_alloc.c
@@ -634,6 +634,76 @@ void get_blocknr_hint_default(reiser4_block_nr * result)
 	spin_unlock_reiser4_super(sbinfo);
 }
 
+static int reiser4_alloc_blocks_pre(reiser4_block_nr len,
+				    block_stage_t block_stage,
+				    reiser4_ba_flags_t flags)
+{
+	int ret = 0;
+
+	/* VITALY: allocator should grab this for internal/tx-lists/similar
+	   only. */
+/* VS-FIXME-HANS: why is this comment above addressed to vitaly (from vitaly)?*/
+	if (block_stage == BLOCK_NOT_COUNTED) {
+		ret = reiser4_grab_space_force(len, flags);
+	}
+
+	return ret;
+}
+
+static void reiser4_alloc_blocks_post_success(reiser4_block_nr blk,
+					      reiser4_block_nr len,
+					      block_stage_t block_stage,
+					      reiser4_ba_flags_t flags)
+{
+	reiser4_context *ctx;
+	reiser4_super_info_data *sbinfo;
+
+	ctx = get_current_context();
+	sbinfo = get_super_private(ctx->super);
+
+	assert("zam-680", blk < reiser4_block_count(ctx->super));
+	assert("zam-681", blk + len <= reiser4_block_count(ctx->super));
+
+	if (flags & BA_PERMANENT) {
+		/* we assume that current atom exists at this moment */
+		txn_atom *atom = get_current_atom_locked();
+		atom->nr_blocks_allocated += len;
+		spin_unlock_atom(atom);
+	}
+
+	switch (block_stage) {
+	case BLOCK_NOT_COUNTED:
+	case BLOCK_GRABBED:
+		grabbed2used(ctx, sbinfo, len);
+		break;
+	case BLOCK_UNALLOCATED:
+		fake_allocated2used(sbinfo, len, flags);
+		break;
+	case BLOCK_FLUSH_RESERVED:
+		{
+			txn_atom *atom = get_current_atom_locked();
+			flush_reserved2used(atom, len);
+			spin_unlock_atom(atom);
+		}
+		break;
+	default:
+		impossible("zam-531", "wrong block stage");
+	}
+}
+
+static void reiser4_alloc_blocks_post_failure(reiser4_block_nr len,
+					      block_stage_t block_stage)
+{
+	reiser4_context *ctx;
+	reiser4_super_info_data *sbinfo;
+
+	ctx = get_current_context();
+	sbinfo = get_super_private(ctx->super);
+
+	if (block_stage == BLOCK_NOT_COUNTED)
+		grabbed2free(ctx, sbinfo, len);
+}
+
 /* Allocate "real" disk blocks by calling a proper space allocation plugin
  * method. Blocks are allocated in one contiguous disk region. The plugin
  * independent part accounts blocks by subtracting allocated amount from grabbed
@@ -651,74 +721,39 @@ void get_blocknr_hint_default(reiser4_block_nr * result)
  *
  * @return -- 0 if success, error code otherwise.
  */
-int
-reiser4_alloc_blocks(reiser4_blocknr_hint * hint, reiser4_block_nr * blk,
-		     reiser4_block_nr * len, reiser4_ba_flags_t flags)
+int reiser4_alloc_blocks(reiser4_blocknr_hint * hint, reiser4_block_nr * blk,
+			 reiser4_block_nr * len, reiser4_ba_flags_t flags)
 {
-	__u64 needed = *len;
-	reiser4_context *ctx;
-	reiser4_super_info_data *sbinfo;
 	int ret;
+	reiser4_context *ctx;
 
 	assert("zam-986", hint != NULL);
+	assert("intelfx-68", blk != NULL);
+	assert("intelfx-69", len != NULL);
 
 	ctx = get_current_context();
-	sbinfo = get_super_private(ctx->super);
 
 	/* For write-optimized data we use default search start value, which is
 	 * close to last write location. */
 	if (flags & BA_USE_DEFAULT_SEARCH_START)
 		get_blocknr_hint_default(&hint->blk);
 
-	/* VITALY: allocator should grab this for internal/tx-lists/similar
-	   only. */
-/* VS-FIXME-HANS: why is this comment above addressed to vitaly (from vitaly)?*/
-	if (hint->block_stage == BLOCK_NOT_COUNTED) {
-		ret = reiser4_grab_space_force(*len, flags);
-		if (ret != 0)
-			return ret;
+	ret = reiser4_alloc_blocks_pre(*len, hint->block_stage, flags);
+
+	if (ret != 0) {
+		return ret;
 	}
 
-	ret =
-	    sa_alloc_blocks(reiser4_get_space_allocator(ctx->super),
-			    hint, (int)needed, blk, len);
+	ret = sa_alloc_blocks(reiser4_get_space_allocator(ctx->super),
+			      hint, (int)*len, blk, len);
 
-	if (!ret) {
-		assert("zam-680", *blk < reiser4_block_count(ctx->super));
-		assert("zam-681",
-		       *blk + *len <= reiser4_block_count(ctx->super));
-
-		if (flags & BA_PERMANENT) {
-			/* we assume that current atom exists at this moment */
-			txn_atom *atom = get_current_atom_locked();
-			atom->nr_blocks_allocated += *len;
-			spin_unlock_atom(atom);
-		}
-
-		switch (hint->block_stage) {
-		case BLOCK_NOT_COUNTED:
-		case BLOCK_GRABBED:
-			grabbed2used(ctx, sbinfo, *len);
-			break;
-		case BLOCK_UNALLOCATED:
-			fake_allocated2used(sbinfo, *len, flags);
-			break;
-		case BLOCK_FLUSH_RESERVED:
-			{
-				txn_atom *atom = get_current_atom_locked();
-				flush_reserved2used(atom, *len);
-				spin_unlock_atom(atom);
-			}
-			break;
-		default:
-			impossible("zam-531", "wrong block stage");
-		}
+	if (ret == 0) {
+		reiser4_alloc_blocks_post_success(*blk, *len, hint->block_stage,
+						  flags);
 	} else {
-		assert("zam-821",
-		       ergo(hint->max_dist == 0
-			    && !hint->backward, ret != -ENOSPC));
-		if (hint->block_stage == BLOCK_NOT_COUNTED)
-			grabbed2free(ctx, sbinfo, needed);
+		assert("zam-821", ergo(hint->max_dist == 0 && !hint->backward,
+				       ret != -ENOSPC));
+		reiser4_alloc_blocks_post_failure(*len, hint->block_stage);
 	}
 
 	return ret;
-- 
2.1.3

[PATCH 2/6] reiser4: block_alloc, plugin/space/bitmap: add a method for "exact" block allocation.

[Ivan Shapovalov]

This allows to allocate exact count of blocks at exact position.
In particular, 'precise discard' implementation will need this interface
to perform padding of the discard extents.

Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
---
 fs/reiser4/block_alloc.c                  | 36 ++++++++++++
 fs/reiser4/block_alloc.h                  |  3 +
 fs/reiser4/plugin/space/bitmap.c          | 94 +++++++++++++++++++++++--------
 fs/reiser4/plugin/space/bitmap.h          |  3 +
 fs/reiser4/plugin/space/space_allocator.h | 10 +++-
 5 files changed, 120 insertions(+), 26 deletions(-)

diff --git a/fs/reiser4/block_alloc.c b/fs/reiser4/block_alloc.c
index be1a795..fc4cf04 100644
--- a/fs/reiser4/block_alloc.c
+++ b/fs/reiser4/block_alloc.c
@@ -759,6 +759,42 @@ int reiser4_alloc_blocks(reiser4_blocknr_hint * hint, reiser4_block_nr * blk,
 	return ret;
 }
 
+/* This is a version of reiser4_alloc_blocks() for use in special conditions,
+ * where an allocation must have exact length and position.
+ *
+ * It does not use reiser4_blocknr_hint; instead, all parameters are passed
+ * directly.
+ */
+int reiser4_alloc_blocks_exact(const reiser4_block_nr * blk,
+			       const reiser4_block_nr * len,
+			       block_stage_t stage, reiser4_ba_flags_t flags)
+{
+	int ret;
+	reiser4_context *ctx;
+
+	assert("intelfx-70", blk != NULL);
+	assert("intelfx-71", len != NULL);
+
+	ctx = get_current_context();
+
+	ret = reiser4_alloc_blocks_pre(*len, stage, flags);
+
+	if (ret != 0) {
+		return ret;
+	}
+
+	ret = sa_alloc_blocks_exact(reiser4_get_space_allocator(ctx->super),
+				    blk, len);
+
+	if (ret == 0) {
+		reiser4_alloc_blocks_post_success(*blk, *len, stage, flags);
+	} else {
+		reiser4_alloc_blocks_post_failure(*len, stage);
+	}
+
+	return ret;
+}
+
 /**
  * ask block allocator for some unformatted blocks
  */
diff --git a/fs/reiser4/block_alloc.h b/fs/reiser4/block_alloc.h
index a4e98af..a09be1d 100644
--- a/fs/reiser4/block_alloc.h
+++ b/fs/reiser4/block_alloc.h
@@ -109,6 +109,9 @@ int reiser4_alloc_blocks(reiser4_blocknr_hint * hint,
 int reiser4_dealloc_blocks(const reiser4_block_nr *,
 			   const reiser4_block_nr *,
 			   block_stage_t, reiser4_ba_flags_t flags);
+int reiser4_alloc_blocks_exact(const reiser4_block_nr * start,
+			       const reiser4_block_nr * len,
+			       block_stage_t stage, reiser4_ba_flags_t flags);
 
 static inline int reiser4_alloc_block(reiser4_blocknr_hint * hint,
 				      reiser4_block_nr * start,
diff --git a/fs/reiser4/plugin/space/bitmap.c b/fs/reiser4/plugin/space/bitmap.c
index 3da3f6b..7d15619 100644
--- a/fs/reiser4/plugin/space/bitmap.c
+++ b/fs/reiser4/plugin/space/bitmap.c
@@ -1222,8 +1222,14 @@ void reiser4_dealloc_blocks_bitmap(reiser4_space_allocator * allocator,
 	release_and_unlock_bnode(bnode);
 }
 
+typedef enum {
+	CHECK_FREE,
+	CHECK_FREE_AND_ALLOC,
+	CHECK_BUSY
+} check_blocks_mode;
+
 static int check_blocks_one_bitmap(bmap_nr_t bmap, bmap_off_t start_offset,
-                                    bmap_off_t end_offset, int desired)
+				   bmap_off_t end_offset, check_blocks_mode mode)
 {
 	struct super_block *super = reiser4_get_current_sb();
 	struct bitmap_node *bnode = get_bnode(super, bmap);
@@ -1236,14 +1242,29 @@ static int check_blocks_one_bitmap(bmap_nr_t bmap, bmap_off_t start_offset,
 
 	assert("nikita-2216", jnode_is_loaded(bnode->wjnode));
 
-	if (desired) {
+	switch (mode) {
+	case CHECK_BUSY:
 		ret = reiser4_find_next_zero_bit(bnode_working_data(bnode),
-						  end_offset, start_offset)
-		      >= end_offset;
-	} else {
-		ret = reiser4_find_next_set_bit(bnode_working_data(bnode),
 						 end_offset, start_offset)
 		      >= end_offset;
+
+		break;
+
+	case CHECK_FREE:
+	case CHECK_FREE_AND_ALLOC:
+		ret = reiser4_find_next_set_bit(bnode_working_data(bnode),
+						end_offset, start_offset)
+		      >= end_offset;
+
+		if (mode == CHECK_FREE_AND_ALLOC && ret) {
+			reiser4_set_bits(bnode_working_data(bnode),
+					 start_offset, end_offset);
+		}
+
+		break;
+
+	default:
+		impossible("intelfx-67", "wrong block check/alloc mode: %d", mode);
 	}
 
 	release_and_unlock_bnode(bnode);
@@ -1251,9 +1272,8 @@ static int check_blocks_one_bitmap(bmap_nr_t bmap, bmap_off_t start_offset,
 	return ret;
 }
 
-/* plugin->u.space_allocator.check_blocks(). */
-int reiser4_check_blocks_bitmap(const reiser4_block_nr * start,
-				 const reiser4_block_nr * len, int desired)
+static int check_blocks_bitmap(reiser4_block_nr start, reiser4_block_nr len,
+			       check_blocks_mode mode)
 {
 	struct super_block *super = reiser4_get_current_sb();
 
@@ -1262,21 +1282,13 @@ int reiser4_check_blocks_bitmap(const reiser4_block_nr * start,
 	bmap_off_t offset, end_offset;
 	const bmap_off_t max_offset = bmap_bit_count(super->s_blocksize);
 
-	assert("intelfx-9", start != NULL);
-	assert("intelfx-10", ergo(len != NULL, *len > 0));
+	assert("intelfx-10", len > 0);
 
-	if (len != NULL) {
-		check_block_range(start, len);
-		end = *start + *len - 1;
-	} else {
-		/* on next line, end is used as temporary len for check_block_range() */
-		end = 1; check_block_range(start, &end);
-		end = *start;
-	}
+	check_block_range(&start, &len);
+	parse_blocknr(&start, &bmap, &offset);
 
-	parse_blocknr(start, &bmap, &offset);
-
-	if (end == *start) {
+	end = start + len - 1;
+	if (end == start) {
 		end_bmap = bmap;
 		end_offset = offset;
 	} else {
@@ -1288,11 +1300,45 @@ int reiser4_check_blocks_bitmap(const reiser4_block_nr * start,
 	assert("intelfx-5", ergo(end_bmap == bmap, end_offset >= offset));
 
 	for (; bmap < end_bmap; bmap++, offset = 0) {
-		if (!check_blocks_one_bitmap(bmap, offset, max_offset, desired)) {
+		if (!check_blocks_one_bitmap(bmap, offset, max_offset, mode)) {
 			return 0;
 		}
 	}
-	return check_blocks_one_bitmap(bmap, offset, end_offset, desired);
+	return check_blocks_one_bitmap(bmap, offset, end_offset, mode);
+}
+
+/* plugin->u.space_allocator.alloc_blocks_exact() */
+int reiser4_alloc_blocks_exact_bitmap(reiser4_space_allocator * allocator,
+				      const reiser4_block_nr * start,
+				      const reiser4_block_nr * len)
+{
+	int ret;
+
+	assert("intelfx-66", start != NULL);
+
+	if (len != NULL)
+		ret = check_blocks_bitmap(*start, *len, CHECK_FREE_AND_ALLOC);
+	else
+		ret = check_blocks_bitmap(*start, 1, CHECK_FREE_AND_ALLOC);
+
+	if (ret == 0)
+		return RETERR(-ENOSPC);
+	else
+		return 0;
+}
+
+/* plugin->u.space_allocator.check_blocks(). */
+int reiser4_check_blocks_bitmap(const reiser4_block_nr * start,
+				const reiser4_block_nr * len, int desired)
+{
+	check_blocks_mode mode = desired ? CHECK_BUSY : CHECK_FREE;
+
+	assert("intelfx-9", start != NULL);
+
+	if (len != NULL)
+		return check_blocks_bitmap (*start, *len, mode);
+	else
+		return check_blocks_bitmap (*start, 1, mode);
 }
 
 /* conditional insertion of @node into atom's overwrite set  if it was not there */
diff --git a/fs/reiser4/plugin/space/bitmap.h b/fs/reiser4/plugin/space/bitmap.h
index 4590498..9679f3c 100644
--- a/fs/reiser4/plugin/space/bitmap.h
+++ b/fs/reiser4/plugin/space/bitmap.h
@@ -19,6 +19,9 @@ extern int reiser4_alloc_blocks_bitmap(reiser4_space_allocator *,
 				       reiser4_blocknr_hint *, int needed,
 				       reiser4_block_nr * start,
 				       reiser4_block_nr * len);
+extern int reiser4_alloc_blocks_exact_bitmap(reiser4_space_allocator *,
+					     const reiser4_block_nr * start,
+					     const reiser4_block_nr * len);
 extern int reiser4_check_blocks_bitmap(const reiser4_block_nr *,
 					const reiser4_block_nr *, int);
 extern void reiser4_dealloc_blocks_bitmap(reiser4_space_allocator *,
diff --git a/fs/reiser4/plugin/space/space_allocator.h b/fs/reiser4/plugin/space/space_allocator.h
index 71bfd11..7567bda 100644
--- a/fs/reiser4/plugin/space/space_allocator.h
+++ b/fs/reiser4/plugin/space/space_allocator.h
@@ -29,9 +29,15 @@ static inline void sa_dealloc_blocks (reiser4_space_allocator * al, reiser4_bloc
 	reiser4_dealloc_blocks_##allocator (al, start, len);								\
 }															\
 															\
-static inline int sa_check_blocks (const reiser4_block_nr * start, const reiser4_block_nr * end, int desired) 		\
+static inline int sa_check_blocks (const reiser4_block_nr * start, const reiser4_block_nr * end, int desired)		\
 {															\
-	return reiser4_check_blocks_##allocator (start, end, desired);							        \
+	return reiser4_check_blocks_##allocator (start, end, desired);							\
+}															\
+															\
+static inline int sa_alloc_blocks_exact (reiser4_space_allocator * al, const reiser4_block_nr * start,			\
+					 const reiser4_block_nr * len)							\
+{															\
+	return reiser4_alloc_blocks_exact_##allocator (al, start, len);							\
 }															\
 															\
 static inline void sa_pre_commit_hook (void)										\
-- 
2.1.3

[PATCH 3/6] reiser4: iterate over extents in discard_atom

[Ivan Shapovalov]

From: Edward Shishkin <edward.shishkin@gmail.com>

. add discard_sorted_merged_extents();
. add mount options to specify erase unit and alignment;
. verify and set discard params to the super-block at mount time;
---
 fs/reiser4/blocknrlist.c |  10 ++
 fs/reiser4/discard.c     | 378 +++++++++++++++++++++++++++++++++++++++++++----
 fs/reiser4/discard.h     |   8 +-
 fs/reiser4/forward.h     |   1 +
 fs/reiser4/init_super.c  |   4 +
 fs/reiser4/super.h       |   4 +
 fs/reiser4/txnmgr.h      |   2 +
 7 files changed, 377 insertions(+), 30 deletions(-)

diff --git a/fs/reiser4/blocknrlist.c b/fs/reiser4/blocknrlist.c
index 39a4a9b..806c59d 100644
--- a/fs/reiser4/blocknrlist.c
+++ b/fs/reiser4/blocknrlist.c
@@ -26,6 +26,16 @@ struct blocknr_list_entry {
 
 #define blocknr_list_entry(ptr) list_entry(ptr, blocknr_list_entry, link)
 
+reiser4_block_nr blocknr_list_entry_start(struct list_head *ptr)
+{
+	return blocknr_list_entry(ptr)->start;
+}
+
+reiser4_block_nr blocknr_list_entry_len(struct list_head *ptr)
+{
+	return blocknr_list_entry(ptr)->len;
+}
+
 static void blocknr_list_entry_init(blocknr_list_entry *entry)
 {
 	assert("intelfx-11", entry != NULL);
diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
index 7a07afc..a8c5336 100644
--- a/fs/reiser4/discard.c
+++ b/fs/reiser4/discard.c
@@ -23,13 +23,6 @@
  * that have since been allocated again and issue discards for everything still
  * valid. This is what discard.[ch] is here for.
  *
- * However, simply iterating through the recorded extents is not enough:
- * - if a single extent is smaller than the erase unit, then this particular
- *   extent won't be discarded even if it is surrounded by enough free blocks
- *   to constitute a whole erase unit;
- * - we won't be able to merge small adjacent extents forming an extent long
- *   enough to be discarded.
- *
  * MECHANISM:
  *
  * During the transaction deallocated extents are recorded in atom's delete
@@ -58,10 +51,9 @@
  * any data. Thus we can avoid any checks for blocks directly present in the
  * discard set.
  *
- * For now, we don't perform "padding" of extents to erase unit boundaries.
- * This means if extents are not aligned with the device's erase unit lattice,
- * the partial erase units at head and tail of extents are truncated by kernel
- * (in blkdev_issue_discard()).
+ * However, we pad each extent from both sides to erase unit boundaries,
+ * and these paddings still have to be checked if they fall outside of initial
+ * extent.
  *
  * So, at commit time the following actions take place:
  * - delete sets are merged to form the discard set;
@@ -70,6 +62,7 @@
  * - for each extent, a single call to blkdev_issue_discard() is done.
  */
 
+#include "forward.h"
 #include "discard.h"
 #include "context.h"
 #include "debug.h"
@@ -79,37 +72,366 @@
 #include <linux/slab.h>
 #include <linux/fs.h>
 #include <linux/blkdev.h>
+#include <linux/lcm.h>
+
+/*
+ * For 1-dimension integer lattice (a,b) (a - offset, b - step)
+ * find its minimal sub-lattice which can be represented in the
+ * more coarse grained (scaled with factor r >= 1) coordinates.
+ * If representation is impossible, return 1. Otherwise return 0.
+ *
+ * @a - offset of the lattice in the initial coordinates;
+ * @b - step of the lattice in the initial coordinates;
+ * @x - offset of the sub-lattice in the scaled coordinates;
+ * @y - step of the sub-lattice in the scaled coordinates;
+ * @r - scale factor.
+ */
+static int convert_lattice_params(int *x, int *y, int a, int b, int r)
+{
+	assert("edward-1635", b != 0);
+	assert("edward-1636", r >= 1);
+
+	if (a % r)
+		return 1;
+	*x = a / r;
+	*y = lcm(b, r) / r;
+
+	/* normalize offset */
+	*x = *x % *y;
+	return 0;
+}
+
+#define MAX_DISCARD_UNIT_BYTES (1 << 20)
+
+/*
+ * Verify customer's or kernel's discard params
+ * at mount time. Re-calculate their values (to be
+ * in blocks) and store them in the superblock.
+ *
+ * Pre-conditions: superblock contains customer's
+ * discard params in bytes (if it was specified at
+ * mount time).
+ */
+void check_discard_params(struct super_block *sb)
+{
+	int ret;
+	reiser4_super_info_data *sbinfo;
+	discard_params *sb_discard;
+	struct queue_limits *limits;
+	int unit;
+	int offset;
+
+	if (!reiser4_is_set(sb, REISER4_DISCARD))
+		return;
+
+	sbinfo = get_super_private(sb);
+	limits = &bdev_get_queue(sb->s_bdev)->limits;
+	sb_discard = &sbinfo->discard;
+
+	if (sb_discard->unit) {
+		/*
+		 * discard params were specified by customer
+		 */
+		unit = sb_discard->unit;
+		offset = sb_discard->offset;
+	}
+	else {
+		/*
+		 * grab discard params from the kernel
+		 */
+		unit = limits->discard_granularity;
+		offset = bdev_discard_alignment(sb->s_bdev);
+	}
+	if (unit == 0)
+		goto disable;
+	if (unit > MAX_DISCARD_UNIT_BYTES) {
+		warning("", "%s: unsupported erase unit (%d)", sb->s_id, unit);
+		goto disable;
+	}
+	ret = convert_lattice_params(&sb_discard->offset,
+				     &sb_discard->unit,
+				     offset,
+				     unit,
+				     sb->s_blocksize);
+	if (ret) {
+		warning("", "%s: unsupported alignment (%d)", sb->s_id, offset);
+		goto disable;
+	}
+	if (sb_discard->unit > MAX_DISCARD_UNIT_BYTES / sb->s_blocksize) {
+		warning("", "%s: unsupported erase unit (%d)", sb->s_id, unit);
+		goto disable;
+	}
+	printk("reiser4: %s: enable discard support "
+	       "(erase unit %u blocks, alignment %u blocks)\n",
+	       sb->s_id, sb_discard->unit, sb_discard->offset);
+	return;
+disable:
+	warning("", "%s: disable discard support", sb->s_id);
+	clear_bit(REISER4_DISCARD, &sbinfo->fs_flags);
+	return;
+}
 
 static int __discard_extent(struct block_device *bdev, sector_t start,
                             sector_t len)
 {
 	assert("intelfx-21", bdev != NULL);
 
-	return blkdev_issue_discard(bdev, start, len, reiser4_ctx_gfp_mask_get(),
-	                            0);
+	return blkdev_issue_discard(bdev, start, len,
+				    reiser4_ctx_gfp_mask_get(), 0);
 }
 
-static int discard_extent(txn_atom *atom UNUSED_ARG,
-                          const reiser4_block_nr* start,
-                          const reiser4_block_nr* len,
-                          void *data UNUSED_ARG)
+/*
+ * Return size of head padding of an extent on a lattice
+ * with step @ulen and offset @uoff.
+ * @start - the start offset of the extent.
+ */
+static int extent_get_headp(reiser4_block_nr start, int uoff, int ulen)
 {
+	__u64 headp;
+	headp = ulen + start - uoff;
+	headp = do_div(headp, ulen);
+	return headp;
+}
+
+/*
+ * Return size of tail padding of an extent on a lattice
+ * with step @ulen and offset @uoff.
+ * @end - the end offset of the extent.
+ */
+static int extent_get_tailp(reiser4_block_nr end, int uoff, int ulen)
+{
+	__u64 tailp;
+	tailp = ulen + end - uoff;
+	tailp = do_div(tailp, ulen);
+	if (tailp)
+		tailp = ulen - tailp;
+	return tailp;
+}
+
+static inline struct list_head *get_next_at(struct list_head *pos,
+					    struct list_head *head)
+{
+	assert("edward-1631", pos != NULL);
+	assert("edward-1632", head != NULL);
+	assert("edward-1633", pos != head);
+
+	return pos->next == head ? NULL : pos->next;
+}
+
+static inline int check_free_blocks(const reiser4_block_nr start,
+				    const reiser4_block_nr len)
+{
+	return reiser4_check_blocks(&start, &len, 0);
+}
+
+/* Make sure that extents are sorted and merged */
+#if REISER4_DEBUG
+static inline void check_blocknr_list_at(struct list_head *pos,
+					 struct list_head *head)
+{
+	struct list_head *next;
+
+	if (pos == NULL)
+		return;
+	next = get_next_at(pos, head);
+	if (next == NULL)
+		return;
+	if (blocknr_list_entry_start(next) <=
+	    blocknr_list_entry_start(pos) + blocknr_list_entry_len(pos))
+		warning("edward-1634",
+			"discard bad pair of extents: (%llu,%llu), (%llu,%llu)",
+			(unsigned long long)blocknr_list_entry_start(pos),
+			(unsigned long long)blocknr_list_entry_len(pos),
+			(unsigned long long)blocknr_list_entry_start(next),
+			(unsigned long long)blocknr_list_entry_len(next));
+}
+#else
+#define check_blocknr_list_at(pos, head) noop
+#endif
+
+/*
+ * discard_sorted_merged_extents() - scan the list of sorted and
+ * merged extents and check head and tail paddings of each
+ * extent in the working space map. Try to "glue" the nearby
+ * extents. Discard the (glued) extents with padded (or cut)
+ * head and tail.
+ *
+ * Pre-conditions: @head points to the list of sorted and
+ * merged extents.
+ *
+ * Local variables:
+ *
+ * d_uni - discard unit size (in blocks);
+ * d_off - discard alignment (in blocks);
+ *
+ * start - offset of the first block of the extent;
+ * len - length of the extent;
+ * end - offset of the first block beyond extent;
+ *
+ * headp - size of head padding of the extent;
+ * tailp - size of tail padding of the extent;
+ *
+ * astart - actual start to discard (offset of the head padding);
+ * alen - actual length to discard (length of glued aligned and padded extents).
+ *
+ * Terminology in the comments:
+ *
+ * head - a part of extent at the beginning;
+ * tail - a part of extent at the end.
+ */
+
+static int discard_sorted_merged_extents(struct list_head *head)
+{
+	int ret;
 	struct super_block *sb = reiser4_get_current_sb();
-	struct block_device *bdev = sb->s_bdev;
+	int d_uni;
+	int d_off;
+	struct list_head *pos;
+	int headp_is_known_dirty = 0;
 
-	sector_t extent_start_sec, extent_len_sec;
+	d_off = get_super_private(sb)->discard.offset;
+	d_uni = get_super_private(sb)->discard.unit;
 
-	const int sec_per_blk = sb->s_blocksize >> 9;
+	for (pos = head->next; pos != head; pos = pos->next) {
+		int headp;
+		int tailp;
+		reiser4_block_nr start;
+		reiser4_block_nr len;
+		reiser4_block_nr end;
+		reiser4_block_nr astart; __s64 alen;
 
-	/* we assume block = N * sector */
-	assert("intelfx-7", sec_per_blk > 0);
+		check_blocknr_list_at(pos, head);
 
-	/* convert extent to sectors */
-	extent_start_sec = *start * sec_per_blk;
-	extent_len_sec = *len * sec_per_blk;
+		start = blocknr_list_entry_start(pos);
+		len = blocknr_list_entry_len(pos);
+		/*
+		 * Step I. Cut or pad the head of extent
+		 *
+		 * This extent wasn't glued
+		 */
+		headp = extent_get_headp(start, d_off, d_uni);
 
-	/* discard the extent, don't pad it to erase unit boundaries for now */
-	return __discard_extent(bdev, extent_start_sec, extent_len_sec);
+		if (headp == 0) {
+			/*
+			 * empty head padding
+			 */
+			assert("edward-1635", headp_is_known_dirty == 0);
+			astart = start;
+			alen = len;
+		} else if (!headp_is_known_dirty &&
+			   check_free_blocks(start - headp, headp)) {
+			/*
+			 * head padding is clean,
+			 * pad the head
+			 */
+			astart = start - headp;
+			alen = len + headp;
+		} else {
+			/*
+			 * head padding is dirty,
+			 * cut the head
+			 */
+			headp_is_known_dirty = 0;
+			astart = start + (d_uni - headp);
+			alen = len - (d_uni - headp);
+		}
+
+		/*
+		 * Step II. Try to glue all nearby extents to the tail
+		 *          Cut or pad the tail of the last extent.
+		 */
+		end = start + len;
+		tailp = extent_get_tailp(end, d_off, d_uni);
+
+		/*
+		 * This "gluing" loop updates @pos, @end, @tailp, @alen
+		 */
+		while (1) {
+			struct list_head *next;
+
+			next = get_next_at(pos, head);
+			check_blocknr_list_at(next, head);
+
+			if (next && (end + tailp >= blocknr_list_entry_start(next))) {
+				/*
+				 * try to glue the next extent
+				 */
+				reiser4_block_nr next_start;
+				reiser4_block_nr next_len;
+
+				next_start = blocknr_list_entry_start(next);
+				next_len = blocknr_list_entry_len(next);
+
+				if (check_free_blocks(end, next_start - end)) {
+					/*
+					 * jump to the glued extent
+					 */
+					if (end + tailp < next_start + next_len) {
+						/*
+						 * the glued extent doesn't
+						 * fit into the tail padding,
+						 * so update the last one
+						 */
+						tailp = extent_get_tailp(next_start + next_len,
+									 d_off, d_uni);
+						alen += (next_start + next_len - end);
+					}
+					pos = next;
+					end = next_start + next_len;
+					/*
+					 * try to glue more extents
+					 */
+					continue;
+				} else {
+					/*
+					 * gluing failed, cut the tail
+					 */
+					if (end + tailp > next_start)
+						headp_is_known_dirty = 1;
+
+					alen -= (d_uni - tailp);
+					break;
+				}
+
+			} else {
+				/*
+				 * nothing to glue:
+				 * this is the last extent, or the next
+				 * extent is too far. So just check the
+				 * rest of tail padding and finish with
+				 * the extent
+				 */
+				if (tailp == 0)
+					break;
+				else if (check_free_blocks(end, tailp))
+					/*
+					 * tail padding is clean,
+					 * pad the tail
+					 */
+					alen += tailp;
+				else
+					/*
+					 * tail padding is dirty,
+					 * cut the tail
+					 */
+					alen -= (d_uni - tailp);
+				break;
+			}
+		}
+
+		/*
+		 * Step III. Discard the result
+		 */
+		if (alen > 0) {
+			ret = __discard_extent(sb->s_bdev,
+					       astart * (sb->s_blocksize >> 9),
+					       alen * (sb->s_blocksize >> 9));
+			if (ret)
+				return ret;
+		}
+	}
+
+	return 0;
 }
 
 int discard_atom(txn_atom *atom, struct list_head *processed_set)
@@ -140,7 +462,7 @@ int discard_atom(txn_atom *atom, struct list_head *processed_set)
 	blocknr_list_sort_and_join(&discard_set);
 
 	/* Perform actual dirty work. */
-	ret = blocknr_list_iterator(NULL, &discard_set, &discard_extent, NULL, 0);
+	ret = discard_sorted_merged_extents(&discard_set);
 
 	/* Add processed extents to the temporary list. */
 	blocknr_list_merge(&discard_set, processed_set);
diff --git a/fs/reiser4/discard.h b/fs/reiser4/discard.h
index 5f0d0d8..6fb6756 100644
--- a/fs/reiser4/discard.h
+++ b/fs/reiser4/discard.h
@@ -6,8 +6,12 @@
 #if !defined(__FS_REISER4_DISCARD_H__)
 #define __FS_REISER4_DISCARD_H__
 
-#include "forward.h"
-#include "dformat.h"
+struct discard_params {
+	int offset; /* discard offset in blocks */
+	int unit; /* erase unit size in blocks */
+};
+
+extern void check_discard_params(struct super_block *sb);
 
 /**
  * Issue discard requests for all block extents recorded in @atom's delete sets,
diff --git a/fs/reiser4/forward.h b/fs/reiser4/forward.h
index 9170c2b..b0ae506 100644
--- a/fs/reiser4/forward.h
+++ b/fs/reiser4/forward.h
@@ -34,6 +34,7 @@ typedef struct reiser4_journal reiser4_journal;
 typedef struct txn_atom txn_atom;
 typedef struct txn_handle txn_handle;
 typedef struct txn_mgr txn_mgr;
+typedef struct discard_params discard_params;
 typedef struct reiser4_dir_entry_desc reiser4_dir_entry_desc;
 typedef struct reiser4_context reiser4_context;
 typedef struct carry_level carry_level;
diff --git a/fs/reiser4/init_super.c b/fs/reiser4/init_super.c
index 1ff8dad..c5da5d0 100644
--- a/fs/reiser4/init_super.c
+++ b/fs/reiser4/init_super.c
@@ -407,6 +407,9 @@ static noinline void push_sb_field_opts(struct opt_desc **p,
 	/* carry flags used for insert operations */
 	PUSH_SB_FIELD_OPT(tree.carry.insert_flags, "%u");
 
+	PUSH_SB_FIELD_OPT(discard.unit, "%u");
+	PUSH_SB_FIELD_OPT(discard.offset, "%u");
+
 #ifdef CONFIG_REISER4_BADBLOCKS
 	/*
 	 * Alternative master superblock location in case if it's original
@@ -573,6 +576,7 @@ int reiser4_init_super_data(struct super_block *super, char *opt_string)
 		warning("nikita-2497", "optimal_io_size is too small");
 		return RETERR(-EINVAL);
 	}
+	check_discard_params(super);
 	return result;
 }
 
diff --git a/fs/reiser4/super.h b/fs/reiser4/super.h
index 895c3f3..68d23fc 100644
--- a/fs/reiser4/super.h
+++ b/fs/reiser4/super.h
@@ -12,6 +12,7 @@
 #include "entd.h"
 #include "wander.h"
 #include "fsdata.h"
+#include "discard.h"
 #include "plugin/object.h"
 #include "plugin/space/space_allocator.h"
 
@@ -206,6 +207,9 @@ struct reiser4_super_info_data {
 	/* transaction manager */
 	txn_mgr tmgr;
 
+	/* discard params */
+	discard_params discard;
+
 	/* ent thread */
 	entd_context entd;
 
diff --git a/fs/reiser4/txnmgr.h b/fs/reiser4/txnmgr.h
index 72b84a2..0350e8f 100644
--- a/fs/reiser4/txnmgr.h
+++ b/fs/reiser4/txnmgr.h
@@ -509,6 +509,8 @@ extern void blocknr_list_init(struct list_head *blist);
 extern void blocknr_list_destroy(struct list_head *blist);
 extern void blocknr_list_merge(struct list_head *from, struct list_head *to);
 extern void blocknr_list_sort_and_join(struct list_head *blist);
+extern reiser4_block_nr blocknr_list_entry_start(struct list_head *blist);
+extern reiser4_block_nr blocknr_list_entry_len(struct list_head *blist);
 /**
  * The @atom should be locked.
  */
-- 
2.1.3

[PATCH 4/6] reiser4: discard: don't be overly smart when gluing extents in discard_sorted_merged_extents().

[Ivan Shapovalov]

@tailp, @alen and @end must be updated simultaneously because there are expressions
involving combinations of these variables.

Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
---
 fs/reiser4/discard.c | 12 ++----------
 1 file changed, 2 insertions(+), 10 deletions(-)

diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
index a8c5336..86ff6e4 100644
--- a/fs/reiser4/discard.c
+++ b/fs/reiser4/discard.c
@@ -366,18 +366,10 @@ static int discard_sorted_merged_extents(struct list_head *head)
 					/*
 					 * jump to the glued extent
 					 */
-					if (end + tailp < next_start + next_len) {
-						/*
-						 * the glued extent doesn't
-						 * fit into the tail padding,
-						 * so update the last one
-						 */
-						tailp = extent_get_tailp(next_start + next_len,
-									 d_off, d_uni);
-						alen += (next_start + next_len - end);
-					}
 					pos = next;
+					alen += (next_start + next_len - end);
 					end = next_start + next_len;
+					tailp = extent_get_tailp(end, d_off, d_uni);
 					/*
 					 * try to glue more extents
 					 */
-- 
2.1.3

[PATCH 5/6] reiser4: blocknrlist: add operations blocknr_list_del() and blocknr_list_update_extent().

[Ivan Shapovalov]

Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
---
 fs/reiser4/blocknrlist.c | 28 ++++++++++++++++++++++++++++
 fs/reiser4/txnmgr.h      |  4 ++++
 2 files changed, 32 insertions(+)

diff --git a/fs/reiser4/blocknrlist.c b/fs/reiser4/blocknrlist.c
index 806c59d..4f80a53 100644
--- a/fs/reiser4/blocknrlist.c
+++ b/fs/reiser4/blocknrlist.c
@@ -243,6 +243,17 @@ void blocknr_list_sort_and_join(struct list_head *blist)
 	}
 }
 
+void blocknr_list_del(struct list_head *blist)
+{
+	struct blocknr_list_entry *entry;
+
+	assert("intelfx-72", blist != NULL);
+
+	entry = blocknr_list_entry(blist);
+	list_del_init (blist);
+	blocknr_list_entry_free(entry);
+}
+
 int blocknr_list_add_extent(txn_atom *atom,
                             struct list_head *blist,
                             blocknr_list_entry **new_entry,
@@ -287,6 +298,23 @@ int blocknr_list_add_extent(txn_atom *atom,
 	return 0;
 }
 
+void blocknr_list_update_extent(struct list_head *blist,
+                                const reiser4_block_nr *start,
+                                const reiser4_block_nr *len)
+{
+	blocknr_list_entry *entry;
+
+	assert("intelfx-73", blist != NULL);
+
+	entry = blocknr_list_entry(blist);
+	if (start != NULL) {
+		entry->start = *start;
+	}
+	if (len != NULL) {
+		entry->len = *len;
+	}
+}
+
 int blocknr_list_iterator(txn_atom *atom,
                           struct list_head *blist,
                           blocknr_set_actor_f actor,
diff --git a/fs/reiser4/txnmgr.h b/fs/reiser4/txnmgr.h
index 0350e8f..d2b8e95 100644
--- a/fs/reiser4/txnmgr.h
+++ b/fs/reiser4/txnmgr.h
@@ -509,6 +509,7 @@ extern void blocknr_list_init(struct list_head *blist);
 extern void blocknr_list_destroy(struct list_head *blist);
 extern void blocknr_list_merge(struct list_head *from, struct list_head *to);
 extern void blocknr_list_sort_and_join(struct list_head *blist);
+extern void blocknr_list_del(struct list_head *blist);
 extern reiser4_block_nr blocknr_list_entry_start(struct list_head *blist);
 extern reiser4_block_nr blocknr_list_entry_len(struct list_head *blist);
 /**
@@ -519,6 +520,9 @@ extern int blocknr_list_add_extent(txn_atom *atom,
                                    blocknr_list_entry **new_entry,
                                    const reiser4_block_nr *start,
                                    const reiser4_block_nr *len);
+extern void blocknr_list_update_extent(struct list_head *blist,
+                                       const reiser4_block_nr *start,
+                                       const reiser4_block_nr *len);
 extern int blocknr_list_iterator(txn_atom *atom,
                                  struct list_head *blist,
                                  blocknr_set_actor_f actor,
-- 
2.1.3

[PATCH 6/6] reiser4: discard: allocate extent paddings.

[Ivan Shapovalov]

Subsequent deallocation of newly allocated padding blocks is ensured by
writing the actual discarded extents back to the discard set.

Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
---
 fs/reiser4/discard.c | 50 ++++++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 44 insertions(+), 6 deletions(-)

diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
index 86ff6e4..68865d2 100644
--- a/fs/reiser4/discard.c
+++ b/fs/reiser4/discard.c
@@ -221,7 +221,15 @@ static inline struct list_head *get_next_at(struct list_head *pos,
 static inline int check_free_blocks(const reiser4_block_nr start,
 				    const reiser4_block_nr len)
 {
-	return reiser4_check_blocks(&start, &len, 0);
+	/*
+	 * NOTE: we do not use BA_PERMANENT in out allocations
+	 * even though these blocks are later deallocated with BA_DEFER
+	 * (via updating the delete set with newly allocated blocks).
+	 * The discard code is ran after the pre-commit hook so deallocated block
+	 * accounting is already done.
+	 */
+	return reiser4_alloc_blocks_exact (&start, &len, BLOCK_NOT_COUNTED,
+					   BA_FORMATTED) == 0;
 }
 
 /* Make sure that extents are sorted and merged */
@@ -255,6 +263,8 @@ static inline void check_blocknr_list_at(struct list_head *pos,
  * extent in the working space map. Try to "glue" the nearby
  * extents. Discard the (glued) extents with padded (or cut)
  * head and tail.
+ * The paddings, if any, are allocated before discarding, and the list
+ * is updated to contain all new allocations.
  *
  * Pre-conditions: @head points to the list of sorted and
  * merged extents.
@@ -274,6 +284,9 @@ static inline void check_blocknr_list_at(struct list_head *pos,
  * astart - actual start to discard (offset of the head padding);
  * alen - actual length to discard (length of glued aligned and padded extents).
  *
+ * estart - start of extent to be written back to the list
+ * eend - end (last block + 1) of extent to be written back to the list
+ *
  * Terminology in the comments:
  *
  * head - a part of extent at the beginning;
@@ -299,11 +312,14 @@ static int discard_sorted_merged_extents(struct list_head *head)
 		reiser4_block_nr len;
 		reiser4_block_nr end;
 		reiser4_block_nr astart; __s64 alen;
+		reiser4_block_nr estart, eend;
 
 		check_blocknr_list_at(pos, head);
 
 		start = blocknr_list_entry_start(pos);
 		len = blocknr_list_entry_len(pos);
+		estart = start;
+
 		/*
 		 * Step I. Cut or pad the head of extent
 		 *
@@ -326,6 +342,7 @@ static int discard_sorted_merged_extents(struct list_head *head)
 			 */
 			astart = start - headp;
 			alen = len + headp;
+			estart -= headp;
 		} else {
 			/*
 			 * head padding is dirty,
@@ -341,10 +358,11 @@ static int discard_sorted_merged_extents(struct list_head *head)
 		 *          Cut or pad the tail of the last extent.
 		 */
 		end = start + len;
+		eend = end;
 		tailp = extent_get_tailp(end, d_off, d_uni);
 
 		/*
-		 * This "gluing" loop updates @pos, @end, @tailp, @alen
+		 * This "gluing" loop updates @end, @tailp, @alen, @eend
 		 */
 		while (1) {
 			struct list_head *next;
@@ -366,10 +384,17 @@ static int discard_sorted_merged_extents(struct list_head *head)
 					/*
 					 * jump to the glued extent
 					 */
-					pos = next;
 					alen += (next_start + next_len - end);
 					end = next_start + next_len;
 					tailp = extent_get_tailp(end, d_off, d_uni);
+					eend = end;
+					/*
+					 * remove the glued extent from the list
+					 *
+					 * (don't update pos, current next->next
+					 * will become pos->next)
+					 */
+					blocknr_list_del(next);
 					/*
 					 * try to glue more extents
 					 */
@@ -395,13 +420,14 @@ static int discard_sorted_merged_extents(struct list_head *head)
 				 */
 				if (tailp == 0)
 					break;
-				else if (check_free_blocks(end, tailp))
+				else if (check_free_blocks(end, tailp)) {
 					/*
 					 * tail padding is clean,
 					 * pad the tail
 					 */
 					alen += tailp;
-				else
+					eend += tailp;
+				} else
 					/*
 					 * tail padding is dirty,
 					 * cut the tail
@@ -415,6 +441,18 @@ static int discard_sorted_merged_extents(struct list_head *head)
 		 * Step III. Discard the result
 		 */
 		if (alen > 0) {
+			assert("intelfx-74", estart < eend);
+			assert("intelfx-75", estart <= start);
+			assert("intelfx-76", estart <= astart);
+			assert("intelfx-77", start + len <= eend);
+			assert("intelfx-78", astart + alen <= eend);
+
+			/* here @eend becomes length */
+			eend -= estart;
+			assert("intelfx-79",
+			       reiser4_check_blocks(&estart, &eend, 1));
+			blocknr_list_update_extent(pos, &estart, &eend);
+
 			ret = __discard_extent(sb->s_bdev,
 					       astart * (sb->s_blocksize >> 9),
 					       alen * (sb->s_blocksize >> 9));
@@ -453,7 +491,7 @@ int discard_atom(txn_atom *atom, struct list_head *processed_set)
 	/* Sort the discard list, joining adjacent and overlapping extents. */
 	blocknr_list_sort_and_join(&discard_set);
 
-	/* Perform actual dirty work. */
+	/* Perform actual dirty work. The discard set may change at this point. */
 	ret = discard_sorted_merged_extents(&discard_set);
 
 	/* Add processed extents to the temporary list. */
-- 
2.1.3

Re: [PATCH 0/6] reiser4: discard support: "precise discard" aka padding of extents to erase unit boundaries.

[Edward Shishkin]

On 12/12/2014 10:10 PM, Ivan Shapovalov wrote:
> So, this patchset uses your algorithm of padding/gluing extents to be discarded.
> I've added exact allocation primitives (is it what you've been talking about?


So, we found out that the old bitmap primitives don't allow us to implement
precise discard, and I asked for new ones. Also we wanted to implement the
general case, when precise discard works for any pair (offset, unit). 
Currently
it works only for ones determined by the function convert_lattice_params().
For some reasons (that I don't remember) I was sure, that the general case
should be obtained from this partial case by a small transformation of the
function discard_sorted_merged_extents().

Well, I'll try to dive into details and generalize things on the holidays.
If generalization is impossible, then we'll switch to non-precise 
discard every
time when convert_lattice_params() fails.

Thanks!
Edward.


> ),
> made the discard procedure allocate blocks of all paddings it performs and
> fixed an apparent bug in extent gluing which triggered the "edward-1635"
> assertion.
>
> Edward Shishkin (1):
>    reiser4: iterate over extents in discard_atom
>
> Ivan Shapovalov (5):
>    reiser4: block_alloc: split block allocation accounting logic into separate functions for re-use.
>    reiser4: block_alloc, plugin/space/bitmap: add a method for "exact" block allocation.
>    reiser4: discard: don't be overly smart when gluing extents in discard_sorted_merged_extents().
>    reiser4: blocknrlist: add operations blocknr_list_del() and blocknr_list_update_extent().
>    reiser4: discard: allocate extent paddings.
>
>   fs/reiser4/block_alloc.c                  | 175 +++++++++----
>   fs/reiser4/block_alloc.h                  |   3 +
>   fs/reiser4/blocknrlist.c                  |  38 +++
>   fs/reiser4/discard.c                      | 410 +++++++++++++++++++++++++++---
>   fs/reiser4/discard.h                      |   8 +-
>   fs/reiser4/forward.h                      |   1 +
>   fs/reiser4/init_super.c                   |   4 +
>   fs/reiser4/plugin/space/bitmap.c          |  94 +++++--
>   fs/reiser4/plugin/space/bitmap.h          |   3 +
>   fs/reiser4/plugin/space/space_allocator.h |  10 +-
>   fs/reiser4/super.h                        |   4 +
>   fs/reiser4/txnmgr.h                       |   6 +
>   12 files changed, 647 insertions(+), 109 deletions(-)
>

Re: [PATCH 0/6] reiser4: discard support: "precise discard" aka padding of extents to erase unit boundaries.

[Ivan Shapovalov]

[-- Attachment #1: Type: text/plain, Size: 1309 bytes --]

On Saturday 13 December 2014 at 23:38:02, Edward Shishkin wrote:	
> 
> On 12/12/2014 10:10 PM, Ivan Shapovalov wrote:
> > So, this patchset uses your algorithm of padding/gluing extents to be discarded.
> > I've added exact allocation primitives (is it what you've been talking about?
> 
> 
> So, we found out that the old bitmap primitives don't allow us to implement
> precise discard, and I asked for new ones. Also we wanted to implement the
> general case, when precise discard works for any pair (offset, unit). 
> Currently
> it works only for ones determined by the function convert_lattice_params().
> For some reasons (that I don't remember) I was sure, that the general case
> should be obtained from this partial case by a small transformation of the
> function discard_sorted_merged_extents().
> 
> Well, I'll try to dive into details and generalize things on the holidays.
> If generalization is impossible, then we'll switch to non-precise 
> discard every
> time when convert_lattice_params() fails.

I don't quite understand you here... Do you mean that some non-insane combinations
of discard unit, discard offset and blocksize are not handled (but worth
handling)?

TBH, convert_lattice_params() looks magic-ish to me...

Thanks,
-- 
Ivan Shapovalov / intelfx /

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 213 bytes --]

Re: [PATCH 0/6] reiser4: discard support: "precise discard" aka padding of extents to erase unit boundaries.

[Edward Shishkin]

On 12/14/2014 09:03 AM, Ivan Shapovalov wrote:
> On Saturday 13 December 2014 at 23:38:02, Edward Shishkin wrote:	
>> On 12/12/2014 10:10 PM, Ivan Shapovalov wrote:
>>> So, this patchset uses your algorithm of padding/gluing extents to be discarded.
>>> I've added exact allocation primitives (is it what you've been talking about?
>>
>> So, we found out that the old bitmap primitives don't allow us to implement
>> precise discard, and I asked for new ones. Also we wanted to implement the
>> general case, when precise discard works for any pair (offset, unit).
>> Currently
>> it works only for ones determined by the function convert_lattice_params().
>> For some reasons (that I don't remember) I was sure, that the general case
>> should be obtained from this partial case by a small transformation of the
>> function discard_sorted_merged_extents().
>>
>> Well, I'll try to dive into details and generalize things on the holidays.
>> If generalization is impossible, then we'll switch to non-precise
>> discard every
>> time when convert_lattice_params() fails.
> I don't quite understand you here... Do you mean that some non-insane combinations
> of discard unit, discard offset and blocksize are not handled (but worth
> handling)?


Yes. As you can see, if (discard_offset % block_size != 0), then we
don't issue discard requests. Neither precise, nor non-precise.
It is hard to implement the precise discard support in the generic case 
straight away.


>
> TBH, convert_lattice_params() looks magic-ish to me...


OK, I'll try to provide some background (geometric minimum).

Edward.

Re: [PATCH 2/6] reiser4: block_alloc, plugin/space/bitmap: add a method for "exact" block allocation.

[Edward Shishkin]

Yes, this is exactly what I wanted,
Thanks!
Edward.


On 12/12/2014 10:10 PM, Ivan Shapovalov wrote:
> This allows to allocate exact count of blocks at exact position.
> In particular, 'precise discard' implementation will need this interface
> to perform padding of the discard extents.
>
> Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
> ---
>   fs/reiser4/block_alloc.c                  | 36 ++++++++++++
>   fs/reiser4/block_alloc.h                  |  3 +
>   fs/reiser4/plugin/space/bitmap.c          | 94 +++++++++++++++++++++++--------
>   fs/reiser4/plugin/space/bitmap.h          |  3 +
>   fs/reiser4/plugin/space/space_allocator.h | 10 +++-
>   5 files changed, 120 insertions(+), 26 deletions(-)
>
> diff --git a/fs/reiser4/block_alloc.c b/fs/reiser4/block_alloc.c
> index be1a795..fc4cf04 100644
> --- a/fs/reiser4/block_alloc.c
> +++ b/fs/reiser4/block_alloc.c
> @@ -759,6 +759,42 @@ int reiser4_alloc_blocks(reiser4_blocknr_hint * hint, reiser4_block_nr * blk,
>   	return ret;
>   }
>   
> +/* This is a version of reiser4_alloc_blocks() for use in special conditions,
> + * where an allocation must have exact length and position.
> + *
> + * It does not use reiser4_blocknr_hint; instead, all parameters are passed
> + * directly.
> + */
> +int reiser4_alloc_blocks_exact(const reiser4_block_nr * blk,
> +			       const reiser4_block_nr * len,
> +			       block_stage_t stage, reiser4_ba_flags_t flags)
> +{
> +	int ret;
> +	reiser4_context *ctx;
> +
> +	assert("intelfx-70", blk != NULL);
> +	assert("intelfx-71", len != NULL);
> +
> +	ctx = get_current_context();
> +
> +	ret = reiser4_alloc_blocks_pre(*len, stage, flags);
> +
> +	if (ret != 0) {
> +		return ret;
> +	}
> +
> +	ret = sa_alloc_blocks_exact(reiser4_get_space_allocator(ctx->super),
> +				    blk, len);
> +
> +	if (ret == 0) {
> +		reiser4_alloc_blocks_post_success(*blk, *len, stage, flags);
> +	} else {
> +		reiser4_alloc_blocks_post_failure(*len, stage);
> +	}
> +
> +	return ret;
> +}
> +
>   /**
>    * ask block allocator for some unformatted blocks
>    */
> diff --git a/fs/reiser4/block_alloc.h b/fs/reiser4/block_alloc.h
> index a4e98af..a09be1d 100644
> --- a/fs/reiser4/block_alloc.h
> +++ b/fs/reiser4/block_alloc.h
> @@ -109,6 +109,9 @@ int reiser4_alloc_blocks(reiser4_blocknr_hint * hint,
>   int reiser4_dealloc_blocks(const reiser4_block_nr *,
>   			   const reiser4_block_nr *,
>   			   block_stage_t, reiser4_ba_flags_t flags);
> +int reiser4_alloc_blocks_exact(const reiser4_block_nr * start,
> +			       const reiser4_block_nr * len,
> +			       block_stage_t stage, reiser4_ba_flags_t flags);
>   
>   static inline int reiser4_alloc_block(reiser4_blocknr_hint * hint,
>   				      reiser4_block_nr * start,
> diff --git a/fs/reiser4/plugin/space/bitmap.c b/fs/reiser4/plugin/space/bitmap.c
> index 3da3f6b..7d15619 100644
> --- a/fs/reiser4/plugin/space/bitmap.c
> +++ b/fs/reiser4/plugin/space/bitmap.c
> @@ -1222,8 +1222,14 @@ void reiser4_dealloc_blocks_bitmap(reiser4_space_allocator * allocator,
>   	release_and_unlock_bnode(bnode);
>   }
>   
> +typedef enum {
> +	CHECK_FREE,
> +	CHECK_FREE_AND_ALLOC,
> +	CHECK_BUSY
> +} check_blocks_mode;
> +
>   static int check_blocks_one_bitmap(bmap_nr_t bmap, bmap_off_t start_offset,
> -                                    bmap_off_t end_offset, int desired)
> +				   bmap_off_t end_offset, check_blocks_mode mode)
>   {
>   	struct super_block *super = reiser4_get_current_sb();
>   	struct bitmap_node *bnode = get_bnode(super, bmap);
> @@ -1236,14 +1242,29 @@ static int check_blocks_one_bitmap(bmap_nr_t bmap, bmap_off_t start_offset,
>   
>   	assert("nikita-2216", jnode_is_loaded(bnode->wjnode));
>   
> -	if (desired) {
> +	switch (mode) {
> +	case CHECK_BUSY:
>   		ret = reiser4_find_next_zero_bit(bnode_working_data(bnode),
> -						  end_offset, start_offset)
> -		      >= end_offset;
> -	} else {
> -		ret = reiser4_find_next_set_bit(bnode_working_data(bnode),
>   						 end_offset, start_offset)
>   		      >= end_offset;
> +
> +		break;
> +
> +	case CHECK_FREE:
> +	case CHECK_FREE_AND_ALLOC:
> +		ret = reiser4_find_next_set_bit(bnode_working_data(bnode),
> +						end_offset, start_offset)
> +		      >= end_offset;
> +
> +		if (mode == CHECK_FREE_AND_ALLOC && ret) {
> +			reiser4_set_bits(bnode_working_data(bnode),
> +					 start_offset, end_offset);
> +		}
> +
> +		break;
> +
> +	default:
> +		impossible("intelfx-67", "wrong block check/alloc mode: %d", mode);
>   	}
>   
>   	release_and_unlock_bnode(bnode);
> @@ -1251,9 +1272,8 @@ static int check_blocks_one_bitmap(bmap_nr_t bmap, bmap_off_t start_offset,
>   	return ret;
>   }
>   
> -/* plugin->u.space_allocator.check_blocks(). */
> -int reiser4_check_blocks_bitmap(const reiser4_block_nr * start,
> -				 const reiser4_block_nr * len, int desired)
> +static int check_blocks_bitmap(reiser4_block_nr start, reiser4_block_nr len,
> +			       check_blocks_mode mode)
>   {
>   	struct super_block *super = reiser4_get_current_sb();
>   
> @@ -1262,21 +1282,13 @@ int reiser4_check_blocks_bitmap(const reiser4_block_nr * start,
>   	bmap_off_t offset, end_offset;
>   	const bmap_off_t max_offset = bmap_bit_count(super->s_blocksize);
>   
> -	assert("intelfx-9", start != NULL);
> -	assert("intelfx-10", ergo(len != NULL, *len > 0));
> +	assert("intelfx-10", len > 0);
>   
> -	if (len != NULL) {
> -		check_block_range(start, len);
> -		end = *start + *len - 1;
> -	} else {
> -		/* on next line, end is used as temporary len for check_block_range() */
> -		end = 1; check_block_range(start, &end);
> -		end = *start;
> -	}
> +	check_block_range(&start, &len);
> +	parse_blocknr(&start, &bmap, &offset);
>   
> -	parse_blocknr(start, &bmap, &offset);
> -
> -	if (end == *start) {
> +	end = start + len - 1;
> +	if (end == start) {
>   		end_bmap = bmap;
>   		end_offset = offset;
>   	} else {
> @@ -1288,11 +1300,45 @@ int reiser4_check_blocks_bitmap(const reiser4_block_nr * start,
>   	assert("intelfx-5", ergo(end_bmap == bmap, end_offset >= offset));
>   
>   	for (; bmap < end_bmap; bmap++, offset = 0) {
> -		if (!check_blocks_one_bitmap(bmap, offset, max_offset, desired)) {
> +		if (!check_blocks_one_bitmap(bmap, offset, max_offset, mode)) {
>   			return 0;
>   		}
>   	}
> -	return check_blocks_one_bitmap(bmap, offset, end_offset, desired);
> +	return check_blocks_one_bitmap(bmap, offset, end_offset, mode);
> +}
> +
> +/* plugin->u.space_allocator.alloc_blocks_exact() */
> +int reiser4_alloc_blocks_exact_bitmap(reiser4_space_allocator * allocator,
> +				      const reiser4_block_nr * start,
> +				      const reiser4_block_nr * len)
> +{
> +	int ret;
> +
> +	assert("intelfx-66", start != NULL);
> +
> +	if (len != NULL)
> +		ret = check_blocks_bitmap(*start, *len, CHECK_FREE_AND_ALLOC);
> +	else
> +		ret = check_blocks_bitmap(*start, 1, CHECK_FREE_AND_ALLOC);
> +
> +	if (ret == 0)
> +		return RETERR(-ENOSPC);
> +	else
> +		return 0;
> +}
> +
> +/* plugin->u.space_allocator.check_blocks(). */
> +int reiser4_check_blocks_bitmap(const reiser4_block_nr * start,
> +				const reiser4_block_nr * len, int desired)
> +{
> +	check_blocks_mode mode = desired ? CHECK_BUSY : CHECK_FREE;
> +
> +	assert("intelfx-9", start != NULL);
> +
> +	if (len != NULL)
> +		return check_blocks_bitmap (*start, *len, mode);
> +	else
> +		return check_blocks_bitmap (*start, 1, mode);
>   }
>   
>   /* conditional insertion of @node into atom's overwrite set  if it was not there */
> diff --git a/fs/reiser4/plugin/space/bitmap.h b/fs/reiser4/plugin/space/bitmap.h
> index 4590498..9679f3c 100644
> --- a/fs/reiser4/plugin/space/bitmap.h
> +++ b/fs/reiser4/plugin/space/bitmap.h
> @@ -19,6 +19,9 @@ extern int reiser4_alloc_blocks_bitmap(reiser4_space_allocator *,
>   				       reiser4_blocknr_hint *, int needed,
>   				       reiser4_block_nr * start,
>   				       reiser4_block_nr * len);
> +extern int reiser4_alloc_blocks_exact_bitmap(reiser4_space_allocator *,
> +					     const reiser4_block_nr * start,
> +					     const reiser4_block_nr * len);
>   extern int reiser4_check_blocks_bitmap(const reiser4_block_nr *,
>   					const reiser4_block_nr *, int);
>   extern void reiser4_dealloc_blocks_bitmap(reiser4_space_allocator *,
> diff --git a/fs/reiser4/plugin/space/space_allocator.h b/fs/reiser4/plugin/space/space_allocator.h
> index 71bfd11..7567bda 100644
> --- a/fs/reiser4/plugin/space/space_allocator.h
> +++ b/fs/reiser4/plugin/space/space_allocator.h
> @@ -29,9 +29,15 @@ static inline void sa_dealloc_blocks (reiser4_space_allocator * al, reiser4_bloc
>   	reiser4_dealloc_blocks_##allocator (al, start, len);								\
>   }															\
>   															\
> -static inline int sa_check_blocks (const reiser4_block_nr * start, const reiser4_block_nr * end, int desired) 		\
> +static inline int sa_check_blocks (const reiser4_block_nr * start, const reiser4_block_nr * end, int desired)		\
>   {															\
> -	return reiser4_check_blocks_##allocator (start, end, desired);							        \
> +	return reiser4_check_blocks_##allocator (start, end, desired);							\
> +}															\
> +															\
> +static inline int sa_alloc_blocks_exact (reiser4_space_allocator * al, const reiser4_block_nr * start,			\
> +					 const reiser4_block_nr * len)							\
> +{															\
> +	return reiser4_alloc_blocks_exact_##allocator (al, start, len);							\
>   }															\
>   															\
>   static inline void sa_pre_commit_hook (void)										\

Re: [PATCH 0/6] reiser4: discard support: "precise discard" aka padding of extents to erase unit boundaries.

[Edward Shishkin]

On 12/15/2014 08:30 PM, Edward Shishkin wrote:
> On 12/14/2014 09:03 AM, Ivan Shapovalov wrote:
>> On Saturday 13 December 2014 at 23:38:02, Edward Shishkin wrote:
>>> On 12/12/2014 10:10 PM, Ivan Shapovalov wrote:
>>>> So, this patchset uses your algorithm of padding/gluing extents to 
>>>> be discarded.
>>>> I've added exact allocation primitives (is it what you've been 
>>>> talking about?
>>>
>>> So, we found out that the old bitmap primitives don't allow us to 
>>> implement
>>> precise discard, and I asked for new ones. Also we wanted to 
>>> implement the
>>> general case, when precise discard works for any pair (offset, unit).
>>> Currently
>>> it works only for ones determined by the function 
>>> convert_lattice_params().
>>> For some reasons (that I don't remember) I was sure, that the 
>>> general case
>>> should be obtained from this partial case by a small transformation 
>>> of the
>>> function discard_sorted_merged_extents().
>>>
>>> Well, I'll try to dive into details and generalize things on the 
>>> holidays.
>>> If generalization is impossible, 


Hopefully this is possible,
I'll try to send the patch in short.

Edward.


>>> then we'll switch to non-precise
>>> discard every
>>> time when convert_lattice_params() fails.
>> I don't quite understand you here... Do you mean that some non-insane 
>> combinations
>> of discard unit, discard offset and blocksize are not handled (but worth
>> handling)?
>
>
> Yes. As you can see, if (discard_offset % block_size != 0), then we
> don't issue discard requests. Neither precise, nor non-precise.
> It is hard to implement the precise discard support in the generic 
> case straight away.
>
>
>>
>> TBH, convert_lattice_params() looks magic-ish to me...
>
>
> OK, I'll try to provide some background (geometric minimum).
>
> Edward.

Re: [PATCH 4/6] reiser4: discard: don't be overly smart when gluing extents in discard_sorted_merged_extents().

[Edward Shishkin]

Agreed.
This is absolutely not needed "if".

Thanks!
Edward.


On 12/12/2014 10:10 PM, Ivan Shapovalov wrote:
> @tailp, @alen and @end must be updated simultaneously because there are expressions
> involving combinations of these variables.
>
> Signed-off-by: Ivan Shapovalov <intelfx100@gmail.com>
> ---
>   fs/reiser4/discard.c | 12 ++----------
>   1 file changed, 2 insertions(+), 10 deletions(-)
>
> diff --git a/fs/reiser4/discard.c b/fs/reiser4/discard.c
> index a8c5336..86ff6e4 100644
> --- a/fs/reiser4/discard.c
> +++ b/fs/reiser4/discard.c
> @@ -366,18 +366,10 @@ static int discard_sorted_merged_extents(struct list_head *head)
>   					/*
>   					 * jump to the glued extent
>   					 */
> -					if (end + tailp < next_start + next_len) {
> -						/*
> -						 * the glued extent doesn't
> -						 * fit into the tail padding,
> -						 * so update the last one
> -						 */
> -						tailp = extent_get_tailp(next_start + next_len,
> -									 d_off, d_uni);
> -						alen += (next_start + next_len - end);
> -					}
>   					pos = next;
> +					alen += (next_start + next_len - end);
>   					end = next_start + next_len;
> +					tailp = extent_get_tailp(end, d_off, d_uni);
>   					/*
>   					 * try to glue more extents
>   					 */