mm: Use slab_list list_head instead of lru

Add function list_rotate_to_front() to rotate a list until the specified item is at the front of the list.

Currently if we wish to rotate a list until a specific item is at the front of the list we can call list_move_tail(head, list). Note that the arguments are the reverse way to the usual use of list_move_tail(list, head). This is a hack, it depends on the developer knowing how the list_head operates internally which violates the layer of abstraction offered by the list_head. Also, it is not intuitive so the next developer to come along must study list.h in order to fully understand what is meant by the call, while this is 'good for' the developer it makes reading the code harder. We should have an function appropriately named that does this if there are users for it intree.

By grep'ing the tree for list_move_tail() and list_tail() and attempting to guess the argument order from the names it seems there is only one place currently in the tree that does this - the slob allocatator.

Add function list_rotate_to_front() to rotate a list until the specified item is at the front of the list.

Signed-off-by Tobin C. Harding <[email protected]>

Currently we reach inside the list_head. This is a violation of the layer of abstraction provided by the list_head. It makes the code fragile. More importantly it makes the code wicked hard to understand.

Currently we reach inside the list_head. This is a violation of the layer of abstraction provided by the list_head. It makes the code fragile. More importantly it makes the code wicked hard to understand.

The code reaches into the list_head structure to counteract the fact that the list _may_ have been changed during slob_page_alloc(). Instead of this we can add a return parameter to slob_page_alloc() to signal that the list was modified (list_del() called with page->lru to remove page from the freelist).

This code is concerned with an optimisation that counters the tendency for first fit allocation algorithm to fragment memory into many small chunks at the front of the memory pool. Since the page is only removed from the list when an allocation uses _all_ the remaining memory in the page then in this special case fragmentation does not occur and we therefore do not need the optimisation.

Add a return parameter to slob_page_alloc() to signal that the allocation used up the whole page and that the page was removed from the free list. After calling slob_page_alloc() check the return value just added and only attempt optimisation if the page is still on the list.

Use list_head API instead of reaching into the list_head structure to check if sp is at the front of the list.

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slob.c | 51 +++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 37 insertions(+), 14 deletions(-)

mm/slob.c +6 -1

index 307c2c9feb44..07356e9feaaa 100644
@@ -213,13 +213,26 @@ static void slob_free_pages(void *b, int order)
 }
 
 /*
- * Allocate a slob block within a given slob_page sp.
+ * slob_page_alloc() - Allocate a slob block within a given slob_page sp.
+ * @sp: Page to look in.
+ * @size: Size of the allocation.
+ * @align: Allocation alignment.
+ * @page_removed_from_list: Return parameter.
+ *

mm/slob.c +23 -12

 {
 	slob_t *prev, *cur, *aligned = NULL;
 	int delta = 0, units = SLOB_UNITS(size);
 
+	*page_removed_from_list = false;
 	for (prev = NULL, cur = sp->freelist; ; prev = cur, cur = slob_next(cur)) {
 		slobidx_t avail = slob_units(cur);
 

@@ -254,8 +267,10 @@ static void *slob_page_alloc(struct page *sp, size_t size, int align)
 			}
 
 			sp->units -= units;
-			if (!sp->units)
+			if (!sp->units) {
 				clear_slob_page_free(sp);
+				*page_removed_from_list = true;
+			}
 			return cur;
 		}
 		if (slob_last(cur))

@@ -269,10 +284,10 @@ static void *slob_page_alloc(struct page *sp, size_t size, int align)
 static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 {
 	struct page *sp;
-	struct list_head *prev;
 	struct list_head *slob_list;
 	slob_t *b = NULL;
 	unsigned long flags;
+	bool _unused;
 
 	if (size < SLOB_BREAK1)
 		slob_list = &free_slob_small;

@@ -284,6 +299,7 @@ static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 	spin_lock_irqsave(&slob_lock, flags);
 	/* Iterate through each partially free page, try to find room */
 	list_for_each_entry(sp, slob_list, lru) {
+		bool page_removed_from_list = false;
 #ifdef CONFIG_NUMA
 		/*
 		 * If there's a node specification, search for a partial

@@ -296,18 +312,25 @@ static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 		if (sp->units < SLOB_UNITS(size))
 			continue;
 
-		/* Attempt to alloc */
-		prev = sp->lru.prev;
-		b = slob_page_alloc(sp, size, align);
+		b = slob_page_alloc(sp, size, align, &page_removed_from_list);
 		if (!b)
 			continue;
 
-		/* Improve fragment distribution and reduce our average
-		 * search time by starting our next search here. (see
-		 * Knuth vol 1, sec 2.5, pg 449) */
-		if (prev != slob_list->prev &&
-				slob_list->next != prev->next)
-			list_move_tail(slob_list, prev->next);
+		/*
+		 * If slob_page_alloc() removed sp from the list then we
+		 * cannot call list functions on sp.  If so allocation
+		 * did not fragment the page anyway so optimisation is
+		 * unnecessary.
+		 */
+		if (!page_removed_from_list) {
+			/*
+			 * Improve fragment distribution and reduce our average
+			 * search time by starting our next search here. (see
+			 * Knuth vol 1, sec 2.5, pg 449)
+			 */
+			if (!list_is_first(&sp->lru, slob_list))
+				list_rotate_to_front(&sp->lru, slob_list);
+		}
 		break;
 	}
 	spin_unlock_irqrestore(&slob_lock, flags);

@@ -326,7 +349,7 @@ static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 		INIT_LIST_HEAD(&sp->lru);
 		set_slob(b, SLOB_UNITS(PAGE_SIZE), b + SLOB_UNITS(PAGE_SIZE));
 		set_slob_page_free(sp, slob_list);
-		b = slob_page_alloc(sp, size, align);
+		b = slob_page_alloc(sp, size, align, &_unused);
 		BUG_ON(!b);
 		spin_unlock_irqrestore(&slob_lock, flags);
 	}

Signature · 1 line

2.21.0

Quoted 45 lines · Tobin C. Harding

Currently we reach inside the list_head. This is a violation of the layer of abstraction provided by the list_head. It makes the code fragile. More importantly it makes the code wicked hard to understand.

The code reaches into the list_head structure to counteract the fact that the list _may_ have been changed during slob_page_alloc(). Instead of this we can add a return parameter to slob_page_alloc() to signal that the list was modified (list_del() called with page->lru to remove page from the freelist).

This code is concerned with an optimisation that counters the tendency for first fit allocation algorithm to fragment memory into many small chunks at the front of the memory pool. Since the page is only removed from the list when an allocation uses _all_ the remaining memory in the page then in this special case fragmentation does not occur and we therefore do not need the optimisation.

Add a return parameter to slob_page_alloc() to signal that the allocation used up the whole page and that the page was removed from the free list. After calling slob_page_alloc() check the return value just added and only attempt optimisation if the page is still on the list.

Use list_head API instead of reaching into the list_head structure to check if sp is at the front of the list.

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slob.c | 51 +++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 37 insertions(+), 14 deletions(-)

mm/slob.c +6 -1

index 307c2c9feb44..07356e9feaaa 100644
@@ -213,13 +213,26 @@ static void slob_free_pages(void *b, int order)
 }
 
 /*
- * Allocate a slob block within a given slob_page sp.
+ * slob_page_alloc() - Allocate a slob block within a given slob_page sp.
+ * @sp: Page to look in.
+ * @size: Size of the allocation.
+ * @align: Allocation alignment.
+ * @page_removed_from_list: Return parameter.
+ *

mm/slob.c static void slob_free_pages(void *b, int order) · line 230

Quoted 10 lines

mm/slob.c +8 -1

+ * Tries to find a chunk of memory at least @size bytes big within @page.
+ *
+ * Return: Pointer to memory if allocated, %NULL otherwise.  If the
+ *         allocation fills up @page then the page is removed from the
+ *         freelist, in this case @page_removed_from_list will be set to
+ *         true (set to false otherwise).
  */
-static void *slob_page_alloc(struct page *sp, size_t size, int align)
+static void *slob_page_alloc(struct page *sp, size_t size, int align,
+			     bool *page_removed_from_list)

Hi Tobin!

Isn't it better to make slob_page_alloc() return a bool value? Then it's easier to ignore the returned value, no need to introduce "_unused".

Quoted 59 lines · Roman Gushchin

Quoted 45 lines · Tobin C. Harding

Currently we reach inside the list_head. This is a violation of the layer of abstraction provided by the list_head. It makes the code fragile. More importantly it makes the code wicked hard to understand.

The code reaches into the list_head structure to counteract the fact that the list _may_ have been changed during slob_page_alloc(). Instead of this we can add a return parameter to slob_page_alloc() to signal that the list was modified (list_del() called with page->lru to remove page from the freelist).

This code is concerned with an optimisation that counters the tendency for first fit allocation algorithm to fragment memory into many small chunks at the front of the memory pool. Since the page is only removed from the list when an allocation uses _all_ the remaining memory in the page then in this special case fragmentation does not occur and we therefore do not need the optimisation.

Add a return parameter to slob_page_alloc() to signal that the allocation used up the whole page and that the page was removed from the free list. After calling slob_page_alloc() check the return value just added and only attempt optimisation if the page is still on the list.

Use list_head API instead of reaching into the list_head structure to check if sp is at the front of the list.

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slob.c | 51 +++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 37 insertions(+), 14 deletions(-)

mm/slob.c +6 -1

index 307c2c9feb44..07356e9feaaa 100644
@@ -213,13 +213,26 @@ static void slob_free_pages(void *b, int order)
 }
 
 /*
- * Allocate a slob block within a given slob_page sp.
+ * slob_page_alloc() - Allocate a slob block within a given slob_page sp.
+ * @sp: Page to look in.
+ * @size: Size of the allocation.
+ * @align: Allocation alignment.
+ * @page_removed_from_list: Return parameter.
+ *

mm/slob.c static void slob_free_pages(void *b, int order) · line 230

Quoted 10 lines

mm/slob.c +8 -1

+ * Tries to find a chunk of memory at least @size bytes big within @page.
+ *
+ * Return: Pointer to memory if allocated, %NULL otherwise.  If the
+ *         allocation fills up @page then the page is removed from the
+ *         freelist, in this case @page_removed_from_list will be set to
+ *         true (set to false otherwise).
  */
-static void *slob_page_alloc(struct page *sp, size_t size, int align)
+static void *slob_page_alloc(struct page *sp, size_t size, int align,
+			     bool *page_removed_from_list)

Hi Tobin!

Quoted 2 lines

Isn't it better to make slob_page_alloc() return a bool value? Then it's easier to ignore the returned value, no need to introduce "_unused".

We need a pointer to the memory allocated also so AFAICS its either a return parameter for the memory pointer or a return parameter to indicate the boolean value? Open to any other ideas I'm missing.

In a previous crack at this I used a double pointer to the page struct then set that to null to indicate the boolean value. I think the explicit boolean parameter is cleaner.

Quoted 67 lines · Tobin C. Harding

Quoted 59 lines · Roman Gushchin

Quoted 45 lines · Tobin C. Harding

Currently we reach inside the list_head. This is a violation of the layer of abstraction provided by the list_head. It makes the code fragile. More importantly it makes the code wicked hard to understand.

The code reaches into the list_head structure to counteract the fact that the list _may_ have been changed during slob_page_alloc(). Instead of this we can add a return parameter to slob_page_alloc() to signal that the list was modified (list_del() called with page->lru to remove page from the freelist).

This code is concerned with an optimisation that counters the tendency for first fit allocation algorithm to fragment memory into many small chunks at the front of the memory pool. Since the page is only removed from the list when an allocation uses _all_ the remaining memory in the page then in this special case fragmentation does not occur and we therefore do not need the optimisation.

Add a return parameter to slob_page_alloc() to signal that the allocation used up the whole page and that the page was removed from the free list. After calling slob_page_alloc() check the return value just added and only attempt optimisation if the page is still on the list.

Use list_head API instead of reaching into the list_head structure to check if sp is at the front of the list.

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slob.c | 51 +++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 37 insertions(+), 14 deletions(-)

mm/slob.c +6 -1

index 307c2c9feb44..07356e9feaaa 100644
@@ -213,13 +213,26 @@ static void slob_free_pages(void *b, int order)
 }
 
 /*
- * Allocate a slob block within a given slob_page sp.
+ * slob_page_alloc() - Allocate a slob block within a given slob_page sp.
+ * @sp: Page to look in.
+ * @size: Size of the allocation.
+ * @align: Allocation alignment.
+ * @page_removed_from_list: Return parameter.
+ *

mm/slob.c static void slob_free_pages(void *b, int order) · line 230

Quoted 10 lines

mm/slob.c +8 -1

+ * Tries to find a chunk of memory at least @size bytes big within @page.
+ *
+ * Return: Pointer to memory if allocated, %NULL otherwise.  If the
+ *         allocation fills up @page then the page is removed from the
+ *         freelist, in this case @page_removed_from_list will be set to
+ *         true (set to false otherwise).
  */
-static void *slob_page_alloc(struct page *sp, size_t size, int align)
+static void *slob_page_alloc(struct page *sp, size_t size, int align,
+			     bool *page_removed_from_list)

Hi Tobin!

Quoted 2 lines

Isn't it better to make slob_page_alloc() return a bool value? Then it's easier to ignore the returned value, no need to introduce "_unused".

We need a pointer to the memory allocated also so AFAICS its either a return parameter for the memory pointer or a return parameter to indicate the boolean value? Open to any other ideas I'm missing.

Quoted 3 lines

In a previous crack at this I used a double pointer to the page struct then set that to null to indicate the boolean value. I think the explicit boolean parameter is cleaner.

Yeah, sorry, it's my fault. Please, ignore this comment. Bool* argument is perfectly fine here.

Quoted 45 lines · Tobin C. Harding

Currently we reach inside the list_head. This is a violation of the layer of abstraction provided by the list_head. It makes the code fragile. More importantly it makes the code wicked hard to understand.

The code reaches into the list_head structure to counteract the fact that the list _may_ have been changed during slob_page_alloc(). Instead of this we can add a return parameter to slob_page_alloc() to signal that the list was modified (list_del() called with page->lru to remove page from the freelist).

This code is concerned with an optimisation that counters the tendency for first fit allocation algorithm to fragment memory into many small chunks at the front of the memory pool. Since the page is only removed from the list when an allocation uses _all_ the remaining memory in the page then in this special case fragmentation does not occur and we therefore do not need the optimisation.

Add a return parameter to slob_page_alloc() to signal that the allocation used up the whole page and that the page was removed from the free list. After calling slob_page_alloc() check the return value just added and only attempt optimisation if the page is still on the list.

Use list_head API instead of reaching into the list_head structure to check if sp is at the front of the list.

Signed-off-by Tobin C. Harding <[email protected]>

---
 mm/slob.c | 51 +++++++++++++++++++++++++++++++++++++--------------
 1 file changed, 37 insertions(+), 14 deletions(-)

mm/slob.c +6 -1

index 307c2c9feb44..07356e9feaaa 100644
@@ -213,13 +213,26 @@ static void slob_free_pages(void *b, int order)
 }
 
 /*
- * Allocate a slob block within a given slob_page sp.
+ * slob_page_alloc() - Allocate a slob block within a given slob_page sp.
+ * @sp: Page to look in.
+ * @size: Size of the allocation.
+ * @align: Allocation alignment.
+ * @page_removed_from_list: Return parameter.
+ *

mm/slob.c static void slob_free_pages(void *b, int order) · line 230

Quoted 10 lines

mm/slob.c +8 -1

+ * Tries to find a chunk of memory at least @size bytes big within @page.
+ *
+ * Return: Pointer to memory if allocated, %NULL otherwise.  If the
+ *         allocation fills up @page then the page is removed from the
+ *         freelist, in this case @page_removed_from_list will be set to
+ *         true (set to false otherwise).
  */
-static void *slob_page_alloc(struct page *sp, size_t size, int align)
+static void *slob_page_alloc(struct page *sp, size_t size, int align,
+			     bool *page_removed_from_list)

Hi Tobin!

Isn't it better to make slob_page_alloc() return a bool value? Then it's easier to ignore the returned value, no need to introduce "_unused".

Thanks!

Quoted 63 lines

mm/slob.c +13 -11

 {
 	slob_t *prev, *cur, *aligned = NULL;
 	int delta = 0, units = SLOB_UNITS(size);
 
+	*page_removed_from_list = false;
 	for (prev = NULL, cur = sp->freelist; ; prev = cur, cur = slob_next(cur)) {
 		slobidx_t avail = slob_units(cur);
 

@@ -254,8 +267,10 @@ static void *slob_page_alloc(struct page *sp, size_t size, int align)
 			}
 
 			sp->units -= units;
-			if (!sp->units)
+			if (!sp->units) {
 				clear_slob_page_free(sp);
+				*page_removed_from_list = true;
+			}
 			return cur;
 		}
 		if (slob_last(cur))

@@ -269,10 +284,10 @@ static void *slob_page_alloc(struct page *sp, size_t size, int align)
 static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 {
 	struct page *sp;
-	struct list_head *prev;
 	struct list_head *slob_list;
 	slob_t *b = NULL;
 	unsigned long flags;
+	bool _unused;
 
 	if (size < SLOB_BREAK1)
 		slob_list = &free_slob_small;

@@ -284,6 +299,7 @@ static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 	spin_lock_irqsave(&slob_lock, flags);
 	/* Iterate through each partially free page, try to find room */
 	list_for_each_entry(sp, slob_list, lru) {
+		bool page_removed_from_list = false;
 #ifdef CONFIG_NUMA
 		/*
 		 * If there's a node specification, search for a partial

@@ -296,18 +312,25 @@ static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 		if (sp->units < SLOB_UNITS(size))
 			continue;
 
-		/* Attempt to alloc */
-		prev = sp->lru.prev;
-		b = slob_page_alloc(sp, size, align);
+		b = slob_page_alloc(sp, size, align, &page_removed_from_list);
 		if (!b)
 			continue;
 
-		/* Improve fragment distribution and reduce our average
-		 * search time by starting our next search here. (see
-		 * Knuth vol 1, sec 2.5, pg 449) */
-		if (prev != slob_list->prev &&
-				slob_list->next != prev->next)
-			list_move_tail(slob_list, prev->next);
+		/*
+		 * If slob_page_alloc() removed sp from the list then we
+		 * cannot call list functions on sp.  If so allocation
+		 * did not fragment the page anyway so optimisation is
+		 * unnecessary.
+		 */

mm/slob.c static void *slob_alloc(size_t size, gfp_t gfp, int align, int node) · line 332

Quoted 8 lines

mm/slob.c +8 -0

+		if (!page_removed_from_list) {
+			/*
+			 * Improve fragment distribution and reduce our average
+			 * search time by starting our next search here. (see
+			 * Knuth vol 1, sec 2.5, pg 449)
+			 */
+			if (!list_is_first(&sp->lru, slob_list))
+				list_rotate_to_front(&sp->lru, slob_list);

According to 0day test robot this is triggering an error from CHECK_DATA_CORRUPTION when the kernel is built with CONFIG_DEBUG_LIST.

I think this is because list_rotate_to_front() puts the list into an invalid state before it calls __list_add(). The thing that has me stumped is why this was not happening before this patch series was applied? ATM I'm not able to get my test module to trigger this but I'm going to try a bit harder today. If I'm right one solution is to modify list_rotate_to_front() to _not_ call __list_add() but do it manually, this solution doesn't sit well with me though.

So, summing up, I think the patch is correct in that it does the correct thing but I think the debugging code doesn't like it because we are violating typical usage - so the patch is wrong :)

thanks,
Tobin.

Quoted 2 lines · Tobin C. Harding

According to 0day test robot this is triggering an error from CHECK_DATA_CORRUPTION when the kernel is built with CONFIG_DEBUG_LIST.

FWIW, that report [1] was for commit 15c8410c67adef from next-20190401. I've checked and it's still the v4 version, although the report came after you submitted v5 (it wasn't testing the patches from mailing list, but mmotm). I don't see any report for the v5 version so I'd expect it to be indeed fixed by the new approach that adds boolean return parameter to slob_page_alloc().

Vlastimil

Quoted 11 lines · Vlastimil Babka

Quoted 2 lines · Tobin C. Harding

According to 0day test robot this is triggering an error from CHECK_DATA_CORRUPTION when the kernel is built with CONFIG_DEBUG_LIST.

FWIW, that report [1] was for commit 15c8410c67adef from next-20190401. I've checked and it's still the v4 version, although the report came after you submitted v5 (it wasn't testing the patches from mailing list, but mmotm). I don't see any report for the v5 version so I'd expect it to be indeed fixed by the new approach that adds boolean return parameter to slob_page_alloc().

Quoted 1 line

Vlastimil

Oh man thanks! That is super cool, thanks for letting me know Vlastimil.

SLUB allocator makes heavy use of ifdef/endif pre-processor macros. The pairing of these statements is at times hard to follow e.g. if the pair are further than a screen apart or if there are nested pairs. We can reduce cognitive load by adding a comment to the endif statement of form

       #ifdef CONFIG_FOO
       ...
       #endif /* CONFIG_FOO */

Add comments to endif pre-processor macros if ifdef/endif pair is not immediately apparent.

Acked-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

Currently we use the page->lru list for maintaining lists of slabs. We have a list in the page structure (slab_list) that can be used for this purpose. Doing so makes the code cleaner since we are not overloading the lru list.

Use the slab_list instead of the lru list for maintaining lists of slabs.

Acked-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

Currently we use the page->lru list for maintaining lists of slabs. We have a list in the page structure (slab_list) that can be used for this purpose. Doing so makes the code cleaner since we are not overloading the lru list.

Use the slab_list instead of the lru list for maintaining lists of slabs.

Signed-off-by Tobin C. Harding <[email protected]>

We now use the slab_list list_head instead of the lru list_head. This comment has become stale.

Remove stale comment from page struct slab_list list_head.

Acked-by Christoph Lameter <[email protected]>

Signed-off-by Tobin C. Harding <[email protected]>

Tobin C. Harding (7):
list: Add function list_rotate_to_front()
slob: Respect list_head abstraction layer
slob: Use slab_list instead of lru
slub: Add comments to endif pre-processor macros
slub: Use slab_list instead of lru
slab: Use slab_list instead of lru
mm: Remove stale comment from page struct

 include/linux/list.h     | 18 ++++++++++++
 include/linux/mm_types.h |  2 +-
 mm/slab.c                | 49 ++++++++++++++++----------------
 mm/slob.c                | 59 +++++++++++++++++++++++++++------------
 mm/slub.c                | 60 ++++++++++++++++++++--------------------
 5 files changed, 115 insertions(+), 73 deletions(-)