Skip to contentSkip to conversation

btrfs: Optimise space flushing machinery

PATCH In review Nikolay Borisov 3 participants 6 messages Mar 10, 2020 – Mar 12, 2020 Btrfs file system

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 btrfs: Optimise space flushing machinery

Instead of iterating all pending tickets on the normal/priority list to sum their total size the cost can be amortized across ticket addition/ removal. This turns O(n) + O(m) (where n is the size of the normal list and m of the priority list) into O(1). This will mostly have effect in workloads that experience heavy flushing.

---
 fs/btrfs/space-info.c | 13 ++++++++-----
 fs/btrfs/space-info.h |  4 ++++
 2 files changed, 12 insertions(+), 5 deletions(-)
fs/btrfs/space-info.c +8 -5
index 9cb511d8cd9d..316a724dc990 100644
@@ -389,6 +389,8 @@ void btrfs_try_granting_tickets(struct btrfs_fs_info *fs_info,
 							      space_info,
 							      ticket->bytes);
 			list_del_init(&ticket->list);
+			ASSERT(space_info->reclaim_size >= ticket->bytes);
+			space_info->reclaim_size -= ticket->bytes;
 			ticket->bytes = 0;
 			space_info->tickets_id++;
 			wake_up(&ticket->wait);
@@ -784,16 +786,15 @@ static inline u64
 btrfs_calc_reclaim_metadata_size(struct btrfs_fs_info *fs_info,
 				 struct btrfs_space_info *space_info)
 {
-	struct reserve_ticket *ticket;
 	u64 used;
 	u64 avail;
 	u64 expected;
 	u64 to_reclaim = 0;
 
-	list_for_each_entry(ticket, &space_info->tickets, list)
-		to_reclaim += ticket->bytes;
-	list_for_each_entry(ticket, &space_info->priority_tickets, list)
-		to_reclaim += ticket->bytes;
+	lockdep_assert_held(&space_info->lock);
+
+	if (space_info->reclaim_size)
+		return space_info->reclaim_size;
 
 	avail = calc_available_free_space(fs_info, space_info,
 					  BTRFS_RESERVE_FLUSH_ALL);
@@ -1192,8 +1193,10 @@ static int __reserve_metadata_bytes(struct btrfs_fs_info *fs_info,
 	 * the list and we will do our own flushing further down.
 	 */
 	if (ret && flush != BTRFS_RESERVE_NO_FLUSH) {
+		ASSERT(space_info->reclaim_size >= 0);
 		ticket.bytes = orig_bytes;
 		ticket.error = 0;
+		space_info->reclaim_size += ticket.bytes;
 		init_waitqueue_head(&ticket.wait);
 		if (flush == BTRFS_RESERVE_FLUSH_ALL) {
 			list_add_tail(&ticket.list, &space_info->tickets);
fs/btrfs/space-info.h +4 -0
index 24514cd2c6c1..0e68a6dd2a79 100644
@@ -54,6 +54,10 @@ struct btrfs_space_info {
 	struct list_head ro_bgs;
 	struct list_head priority_tickets;
 	struct list_head tickets;
+
+	u64 reclaim_size; /* Size of space that needs to be reclaimed in order
+			     to satisfy pending tickets */
+
 	/*
 	 * tickets_id just indicates the next ticket will be handled, so note
 	 * it's not stored per ticket.

--
2.17.1

#1 lore raw
Quoted 7 lines · Nikolay Borisov

Instead of iterating all pending tickets on the normal/priority list to sum their total size the cost can be amortized across ticket addition/ removal. This turns O(n) + O(m) (where n is the size of the normal list and m of the priority list) into O(1). This will mostly have effect in workloads that experience heavy flushing.

Added to misc-next, thanks.

Quoted 23 lines
---
 fs/btrfs/space-info.c | 13 ++++++++-----
 fs/btrfs/space-info.h |  4 ++++
 2 files changed, 12 insertions(+), 5 deletions(-)
fs/btrfs/space-info.c +2 -1
index 9cb511d8cd9d..316a724dc990 100644
@@ -389,6 +389,8 @@ void btrfs_try_granting_tickets(struct btrfs_fs_info *fs_info,
 							      space_info,
 							      ticket->bytes);
 			list_del_init(&ticket->list);
+			ASSERT(space_info->reclaim_size >= ticket->bytes);
+			space_info->reclaim_size -= ticket->bytes;
 			ticket->bytes = 0;
 			space_info->tickets_id++;
 			wake_up(&ticket->wait);
@@ -784,16 +786,15 @@ static inline u64
 btrfs_calc_reclaim_metadata_size(struct btrfs_fs_info *fs_info,
 				 struct btrfs_space_info *space_info)
 {
-	struct reserve_ticket *ticket;

fs/btrfs/space-info.c static inline u64 · line 794

Quoted 10 lines
fs/btrfs/space-info.c +1 -4
 	u64 used;
 	u64 avail;
 	u64 expected;
 	u64 to_reclaim = 0;
 
-	list_for_each_entry(ticket, &space_info->tickets, list)
-		to_reclaim += ticket->bytes;
-	list_for_each_entry(ticket, &space_info->priority_tickets, list)
-		to_reclaim += ticket->bytes;
+	lockdep_assert_held(&space_info->lock);

This can potentially save cachelines when the list traversal is avoided as we're interested in just the sum of some data and the tickets are not touched anywhere in this function callgraph.

Quoted 22 lines
fs/btrfs/space-info.c +5 -0
+
+	if (space_info->reclaim_size)
+		return space_info->reclaim_size;
 
 	avail = calc_available_free_space(fs_info, space_info,
 					  BTRFS_RESERVE_FLUSH_ALL);
@@ -1192,8 +1193,10 @@ static int __reserve_metadata_bytes(struct btrfs_fs_info *fs_info,
 	 * the list and we will do our own flushing further down.
 	 */
 	if (ret && flush != BTRFS_RESERVE_NO_FLUSH) {
+		ASSERT(space_info->reclaim_size >= 0);
 		ticket.bytes = orig_bytes;
 		ticket.error = 0;
+		space_info->reclaim_size += ticket.bytes;
 		init_waitqueue_head(&ticket.wait);
 		if (flush == BTRFS_RESERVE_FLUSH_ALL) {
 			list_add_tail(&ticket.list, &space_info->tickets);
fs/btrfs/space-info.h +0 -0
index 24514cd2c6c1..0e68a6dd2a79 100644

fs/btrfs/space-info.h struct btrfs_space_info { · line 59

Quoted 6 lines
fs/btrfs/space-info.h +3 -0
@@ -54,6 +54,10 @@ struct btrfs_space_info {
 	struct list_head ro_bgs;
 	struct list_head priority_tickets;
 	struct list_head tickets;
+
+	u64 reclaim_size; /* Size of space that needs to be reclaimed in order
+			     to satisfy pending tickets */

Please use comment-before-member format.

#2 lore raw
In reply to Nikolay Borisov
Quoted 33 lines · Nikolay Borisov

Instead of iterating all pending tickets on the normal/priority list to sum their total size the cost can be amortized across ticket addition/ removal. This turns O(n) + O(m) (where n is the size of the normal list and m of the priority list) into O(1). This will mostly have effect in workloads that experience heavy flushing.

---
  fs/btrfs/space-info.c | 13 ++++++++-----
  fs/btrfs/space-info.h |  4 ++++
  2 files changed, 12 insertions(+), 5 deletions(-)
fs/btrfs/space-info.c +2 -1
index 9cb511d8cd9d..316a724dc990 100644
@@ -389,6 +389,8 @@ void btrfs_try_granting_tickets(struct btrfs_fs_info *fs_info,
  							      space_info,
  							      ticket->bytes);
  			list_del_init(&ticket->list);
+			ASSERT(space_info->reclaim_size >= ticket->bytes);
+			space_info->reclaim_size -= ticket->bytes;
  			ticket->bytes = 0;
  			space_info->tickets_id++;
  			wake_up(&ticket->wait);
@@ -784,16 +786,15 @@ static inline u64
  btrfs_calc_reclaim_metadata_size(struct btrfs_fs_info *fs_info,
  				 struct btrfs_space_info *space_info)
  {
-	struct reserve_ticket *ticket;
  	u64 used;
  	u64 avail;
  	u64 expected;

fs/btrfs/space-info.c static inline u64 · line 797

Quoted 10 lines
fs/btrfs/space-info.c +4 -4
  	u64 to_reclaim = 0;
 
-	list_for_each_entry(ticket, &space_info->tickets, list)
-		to_reclaim += ticket->bytes;
-	list_for_each_entry(ticket, &space_info->priority_tickets, list)
-		to_reclaim += ticket->bytes;
+	lockdep_assert_held(&space_info->lock);
+
+	if (space_info->reclaim_size)
+		return space_info->reclaim_size;

This undoes the fix that I put up making sure we include any space we can no longer overcommit. Thanks,

Josef

#3 lore raw
Quoted 38 lines · Josef Bacik
Quoted 37 lines · Nikolay Borisov

Instead of iterating all pending tickets on the normal/priority list to sum their total size the cost can be amortized across ticket addition/ removal. This turns O(n) + O(m) (where n is the size of the normal list and m of the priority list) into O(1). This will mostly have effect in workloads
that experience heavy flushing.

---
  fs/btrfs/space-info.c | 13 ++++++++-----
  fs/btrfs/space-info.h |  4 ++++

  2 files changed, 12 insertions(+), 5 deletions(-)
fs/btrfs/space-info.c +2 -0
index 9cb511d8cd9d..316a724dc990 100644
@@ -389,6 +389,8 @@ void btrfs_try_granting_tickets(struct
 btrfs_fs_info *fs_info,
                                     space_info,
                                     ticket->bytes);
               list_del_init(&ticket->list);
+            ASSERT(space_info->reclaim_size >= ticket->bytes);
+            space_info->reclaim_size -= ticket->bytes;
               ticket->bytes = 0;
               space_info->tickets_id++;

              wake_up(&ticket->wait);

fs/btrfs/space-info.c +0 -1
@@ -784,16 +786,15 @@ static inline u64
   btrfs_calc_reclaim_metadata_size(struct btrfs_fs_info *fs_info,
                    struct btrfs_space_info *space_info)
   {
-    struct reserve_ticket *ticket;
       u64 used;
       u64 avail;
       u64 expected;
       u64 to_reclaim = 0;
 
Quoted 11 lines

fs/btrfs/space-info.c static inline u64 · line 797

Quoted 8 lines
fs/btrfs/space-info.c +4 -4
-    list_for_each_entry(ticket, &space_info->tickets, list)
-        to_reclaim += ticket->bytes;
-    list_for_each_entry(ticket, &space_info->priority_tickets, list)
-        to_reclaim += ticket->bytes;
+    lockdep_assert_held(&space_info->lock);
+
+    if (space_info->reclaim_size)
+        return space_info->reclaim_size;

This undoes the fix that I put up making sure we include any space we can no longer overcommit.  Thanks,

Which fix is that?

Quoted 2 lines

Josef

#4 lore raw
Quoted 53 lines · Nikolay Borisov
Quoted 38 lines · Josef Bacik
Quoted 37 lines · Nikolay Borisov

Instead of iterating all pending tickets on the normal/priority list to sum their total size the cost can be amortized across ticket addition/ removal. This turns O(n) + O(m) (where n is the size of the normal list and m of the priority list) into O(1). This will mostly have effect in workloads
that experience heavy flushing.

---
   fs/btrfs/space-info.c | 13 ++++++++-----
   fs/btrfs/space-info.h |  4 ++++
   2 files changed, 12 insertions(+), 5 deletions(-)
fs/btrfs/space-info.c +2 -0
index 9cb511d8cd9d..316a724dc990 100644
@@ -389,6 +389,8 @@ void btrfs_try_granting_tickets(struct
 btrfs_fs_info *fs_info,
                                     space_info,
                                     ticket->bytes);
               list_del_init(&ticket->list);
+            ASSERT(space_info->reclaim_size >= ticket->bytes);
+            space_info->reclaim_size -= ticket->bytes;
               ticket->bytes = 0;
               space_info->tickets_id++;

              wake_up(&ticket->wait);

fs/btrfs/space-info.c +0 -1
@@ -784,16 +786,15 @@ static inline u64
   btrfs_calc_reclaim_metadata_size(struct btrfs_fs_info *fs_info,
                    struct btrfs_space_info *space_info)
   {
-    struct reserve_ticket *ticket;
       u64 used;
       u64 avail;
       u64 expected;
       u64 to_reclaim = 0;
 
Quoted 11 lines

fs/btrfs/space-info.c static inline u64 · line 797

Quoted 8 lines
fs/btrfs/space-info.c +4 -4
-    list_for_each_entry(ticket, &space_info->tickets, list)
-        to_reclaim += ticket->bytes;
-    list_for_each_entry(ticket, &space_info->priority_tickets, list)
-        to_reclaim += ticket->bytes;
+    lockdep_assert_held(&space_info->lock);
+
+    if (space_info->reclaim_size)
+        return space_info->reclaim_size;

This undoes the fix that I put up making sure we include any space we can no longer overcommit.  Thanks,

Quoted 1 line

Which fix is that?

https://github.com/kdave/btrfs-devel/commit/593212a6137ff3c5674609b4233f8ecec459dc45

Thanks,

Josef

#5 lore raw
Quoted 11 lines · Josef Bacik
Quoted 11 lines
Quoted 11 lines
Quoted 10 lines

      u64 to_reclaim = 0;

-    list_for_each_entry(ticket, &space_info->tickets, list) -        to_reclaim += ticket->bytes;
-    list_for_each_entry(ticket, &space_info->priority_tickets, list) -        to_reclaim += ticket->bytes;
+    lockdep_assert_held(&space_info->lock);
+
+    if (space_info->reclaim_size)
+        return space_info->reclaim_size;

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

This undoes the fix that I put up making sure we include any space we can no longer overcommit.  Thanks,

Which fix is that?

https://github.com/kdave/btrfs-devel/commit/593212a6137ff3c5674609b4233f8ecec459dc45

Nik sent me a fixup, now folded to the patch.

fs/btrfs/space-info.c +1 -4
index 9c36397b733c..0884dac883b5 100644
@@ -792,13 +792,10 @@ btrfs_calc_reclaim_metadata_size(struct btrfs_fs_info *fs_info,
        u64 used;
        u64 avail;
        u64 expected;
-       u64 to_reclaim = 0;
+       u64 to_reclaim = space_info->reclaim_size;
 
        lockdep_assert_held(&space_info->lock);
 
-       if (space_info->reclaim_size)
-               return space_info->reclaim_size;
-
        avail = calc_available_free_space(fs_info, space_info,
                                          BTRFS_RESERVE_FLUSH_