On 07/09/2014 02:40 PM, Ivan Shapovalov wrote:
On Monday 07 July 2014 at 01:47:41, Edward Shishkin wrote:
On 06/22/2014 12:48 PM, Ivan Shapovalov wrote:
[...]
[...]
+ * - 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;
Why not to discard the aligned and padded extent, which coincides
with the whole erase unit?
With a number of whole erase units.
+ * - we won't be able to merge small adjacent extents forming an extent long
+ * enough to be discarded.
At this point we have already sorted and merged everything.
So may be it makes sense just to check the head and tail of every resulted
extent and discard the aligned and padded one?
"Head and tail" is not sufficient. We may check the whole extent with a single
bitmap request, but such algorithm will be very inefficient: it will miss many
possibilities for discarding.
Consider many-block extent, from which one block has been allocated again.
In this case we miss (all-1) blocks to be discarded (if granularity = 1 block).
Please, consider such possibility. Iterating over erase units in
discard_extent()
looks suboptimal.
Yes, it's costly... but I don't see any other ways to do the task efficiently.
How about this function? (the attached patch is against v6-series).
Total number of bitmap checks is in [N+1, 2N], where N is number of
extents in the list. At the same time we don't leave any non-discarded
"garbage"...
Edward.
P.S. I tested it, but not enough.
---
fs/reiser4/blocknrlist.c | 10 +
fs/reiser4/discard.c | 249 ++++++++++++++++++++++++++++++++++++++++++++++-
fs/reiser4/txnmgr.h | 2
3 files changed, 259 insertions(+), 2 deletions(-)
--- a/fs/reiser4/discard.c
+++ b/fs/reiser4/discard.c
@@ -167,6 +167,249 @@ static int discard_extent(txn_atom *atom
return 0;
}
+/*
+ * 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 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;
+
+ 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)",
+ blocknr_list_entry_start(pos),
+ blocknr_list_entry_len(pos),
+ blocknr_list_entry_start(next),
+ blocknr_list_entry_len(next));
+}
+#else
+#define check_blocknr_list_at(pos, head) noop
+#endif
+
+/*
+ * discard_sorted_extents() - iterate through 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_extents(struct list_head *head)
+{
+ int ret;
+ struct super_block *sb = reiser4_get_current_sb();
+ struct queue_limits *limits = &bdev_get_queue(sb->s_bdev)->limits;
+
+ int d_uni;
+ int d_off;
+ struct list_head *pos;
+
+ d_uni = limits->discard_granularity / sb->s_blocksize;
+ if (d_uni == 0)
+ d_uni = 1;
+ d_off = (bdev_discard_alignment(sb->s_bdev) / sb->s_blocksize) % d_uni;
+
+ for (pos = head->next; pos != head; pos = pos->next) {
+ int headp;
+ int tailp;
+ int headp_is_known_dirty = 0;
+ reiser4_block_nr start;
+ reiser4_block_nr len;
+ reiser4_block_nr end;
+ reiser4_block_nr astart; __s64 alen;
+
+ check_blocknr_list_at(pos, head);
+
+ 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);
+
+ if (headp && !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 empty or 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
+ */
+ if (tailp && check_free_blocks(end, tailp))
+ /*
+ * tail padding is clean,
+ * pad the tail
+ */
+ alen += tailp;
+ else
+ /*
+ * empty or dirty tail padding,
+ * 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)
{
int ret;
@@ -195,11 +438,13 @@ int discard_atom(txn_atom *atom)
blocknr_list_sort_and_join(&discard_set);
/* Perform actual dirty work. */
- ret = blocknr_list_iterator(NULL, &discard_set, &discard_extent, NULL, 1);
+
+ //ret = blocknr_list_iterator(NULL, &discard_set, &discard_extent, NULL, 1);
+
+ ret = discard_sorted_extents(&discard_set);
if (ret != 0) {
return ret;
}
-
/* Let's do this again for any new extents in the atom's discard set. */
return -E_REPEAT;
}
--- 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);
--- a/fs/reiser4/txnmgr.h
+++ b/fs/reiser4/txnmgr.h
@@ -507,6 +507,8 @@ extern int blocknr_set_iterator(txn_atom
/* This is the block list interface (see blocknrlist.c) */
extern int blocknr_list_init_static(void);
extern void blocknr_list_done_static(void);
+extern reiser4_block_nr blocknr_list_entry_start(struct list_head *blist);
+extern reiser4_block_nr blocknr_list_entry_len(struct list_head *blist);
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);
