[PATCH 0/1] slob: Fix list_head bug during allocation

[PATCH 0/1] slob: Fix list_head bug during allocation

[Tobin C. Harding]

Hi Andrew,

This patch is in response to an email from the 0day kernel test robot
subject:

  340d3d6178 ("mm/slob.c: respect list_head abstraction layer"):  kernel BUG at lib/list_debug.c:31!


This patch applies on top of linux-next tag: next-20190401

It fixes a patch that was merged recently into mm:

  The patch titled
       Subject: mm/slob.c: respect list_head abstraction layer
  has been added to the -mm tree.  Its filename is
       slob-respect-list_head-abstraction-layer.patch
  
  This patch should soon appear at
      http://ozlabs.org/~akpm/mmots/broken-out/slob-respect-list_head-abstraction-layer.patch
  and later at
      http://ozlabs.org/~akpm/mmotm/broken-out/slob-respect-list_head-abstraction-layer.patch


If reverting is easier than patching I can re-work this into another
version of the original (buggy) patch set which was the series:

  [PATCH 0/4] mm: Use slab_list list_head instead of lru

Please don't be afraid to give a firm response.  I'm new to mm and I'd
like to not be a nuisance if I can manage it ;)  I'd also like to fix
this in a way that makes your day as easy as possible.


The 0day kernel test robot found a bug in the slob allocator caused by a
patch from me recently merged into the mm tree.  This is the first time
the 0day has found a bug in already merged code of mine so I do not know
the exact protocol in regards to linking the fix with the report,
patching, reverting etc.

I was unable to reproduce the crash, I tried building with the config
attached to the email above but the kernel booted fine for me in Qemu.

So I re-worked the module originally used for testing, it can be found
here:

	https://github.com/tcharding/ktest/tree/master/list_head

From this I think the list.h code added prior to the buggy patch is
ok.

Next I tried to find the bug just using my eyes.  This patch is the
result.  Unfortunately I can not understand why this bug was not
triggered _before_ I originally patched it.  Perhaps I'm not juggling
all the state perfectly in my head.  Anyways, this patch stops and code
calling list manipulation functions if the slab_list page member has
been modified during allocation.

The code in question revolves around an optimisation aimed at preventing
fragmentation at the start of a slab due to the first fit nature of the
allocation algorithm.

Full explanation is in the commit log for the patch, the short version
is; skip optimisation if page list is modified, this only occurs when an
allocation completely fills the slab and in this case the optimisation
is unnecessary since we have not fragmented the slab by this allocation.

This is more than just a bug fix, it significantly reduces the
complexity of the function while still fixing the reason for originally
touching this code (violation of list_head abstraction).

The only testing I've done is to build and boot a kernel in Qemu (with
CONFIG_LIST_DEBUG and CONFIG_SLOB) enabled).  However, as mentioned,
this method of testing did _not_ reproduce the 0day crash so if there
are better suggestions on how I should test these I'm happy to do so.

thanks,
Tobin.


Tobin C. Harding (1):
  slob: Only use list functions when safe to do so

 mm/slob.c | 50 ++++++++++++++++++++++++++++++--------------------
 1 file changed, 30 insertions(+), 20 deletions(-)

-- 
2.21.0

[PATCH 1/1] slob: Only use list functions when safe to do so

[Tobin C. Harding]

Currently we call (indirectly) list_del() then we manually try to combat
the fact that the list may be in an undefined state by getting 'prev'
and 'next' pointers in a somewhat contrived manner.  It is hard to
verify that this works for all initial states of the list.  Clearly the
author (me) got it wrong the first time because the 0day kernel testing
robot managed to crash the kernel thanks to this code.

All this is done in order to do an optimisation aimed at preventing
fragmentation at the start of a slab.  We can just skip this
optimisation any time the list is put into an undefined state since this
only occurs when an allocation completely fills the slab and in this
case the optimisation is unnecessary since we have not fragmented the slab
by this allocation.

Change the page pointer passed to slob_alloc_page() to be a double
pointer so that we can set it to NULL to indicate that the page was
removed from the list.  Skip the optimisation if the page was removed.

Found thanks to the kernel test robot, email subject:

	340d3d6178 ("mm/slob.c: respect list_head abstraction layer"):  kernel BUG at lib/list_debug.c:31!

Reported-by: kernel test robot <lkp@intel.com>
Signed-off-by: Tobin C. Harding <tobin@kernel.org>
---
 mm/slob.c | 50 ++++++++++++++++++++++++++++++--------------------
 1 file changed, 30 insertions(+), 20 deletions(-)

diff --git a/mm/slob.c b/mm/slob.c
index 21af3fdb457a..c543da10df45 100644
--- a/mm/slob.c
+++ b/mm/slob.c
@@ -213,10 +213,18 @@ 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.
+ * @spp: Page to look in, return parameter.
+ * @size: Size of the allocation.
+ * @align: Allocation alignment.
+ *
+ * Tries to find a chunk of memory at least @size within page.  If the
+ * allocation fills up page then page is removed from list, in this case
+ * *spp will be set to %NULL to signal that list removal occurred.
  */
-static void *slob_page_alloc(struct page *sp, size_t size, int align)
+static void *slob_page_alloc(struct page **spp, size_t size, int align)
 {
+	struct page *sp = *spp;
 	slob_t *prev, *cur, *aligned = NULL;
 	int delta = 0, units = SLOB_UNITS(size);
 
@@ -254,8 +262,11 @@ 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);
+				/* Signal that page was removed from list. */
+				*spp = NULL;
+			}
 			return cur;
 		}
 		if (slob_last(cur))
@@ -268,7 +279,7 @@ 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, *prev, *next;
+	struct page *sp;
 	struct list_head *slob_list;
 	slob_t *b = NULL;
 	unsigned long flags;
@@ -283,6 +294,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, slab_list) {
+		struct page **spp = &sp;
 #ifdef CONFIG_NUMA
 		/*
 		 * If there's a node specification, search for a partial
@@ -295,27 +307,25 @@ static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 		if (sp->units < SLOB_UNITS(size))
 			continue;
 
-		/*
-		 * Cache previous entry because slob_page_alloc() may
-		 * remove sp from slob_list.
-		 */
-		prev = list_prev_entry(sp, slab_list);
-
 		/* Attempt to alloc */
-		b = slob_page_alloc(sp, size, align);
+		b = slob_page_alloc(spp, size, align);
 		if (!b)
 			continue;
 
-		next = list_next_entry(prev, slab_list); /* This may or may not be sp */
-
 		/*
-		 * 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 slob_page_alloc() removed sp from the list then we
+		 * cannot call list functions on sp.  Just bail, don't
+		 * worry about the optimisation below.
 		 */
-		if (!list_is_first(&next->slab_list, slob_list))
-			list_rotate_to_front(&next->slab_list, slob_list);
-
+		if (*spp) {
+			/*
+			 * 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->slab_list, slob_list))
+				list_rotate_to_front(&sp->slab_list, slob_list);
+		}
 		break;
 	}
 	spin_unlock_irqrestore(&slob_lock, flags);
@@ -334,7 +344,7 @@ static void *slob_alloc(size_t size, gfp_t gfp, int align, int node)
 		INIT_LIST_HEAD(&sp->slab_list);
 		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);
 		BUG_ON(!b);
 		spin_unlock_irqrestore(&slob_lock, flags);
 	}
-- 
2.21.0

Re: [PATCH 1/1] slob: Only use list functions when safe to do so

[Andrew Morton]

On Tue,  2 Apr 2019 14:29:57 +1100 "Tobin C. Harding" <tobin@kernel.org> wrote:

> Currently we call (indirectly) list_del() then we manually try to combat
> the fact that the list may be in an undefined state by getting 'prev'
> and 'next' pointers in a somewhat contrived manner.  It is hard to
> verify that this works for all initial states of the list.  Clearly the
> author (me) got it wrong the first time because the 0day kernel testing
> robot managed to crash the kernel thanks to this code.
> 
> All this is done in order to do an optimisation aimed at preventing
> fragmentation at the start of a slab.  We can just skip this
> optimisation any time the list is put into an undefined state since this
> only occurs when an allocation completely fills the slab and in this
> case the optimisation is unnecessary since we have not fragmented the slab
> by this allocation.
> 
> Change the page pointer passed to slob_alloc_page() to be a double
> pointer so that we can set it to NULL to indicate that the page was
> removed from the list.  Skip the optimisation if the page was removed.
> 
> Found thanks to the kernel test robot, email subject:
> 
> 	340d3d6178 ("mm/slob.c: respect list_head abstraction layer"):  kernel BUG at lib/list_debug.c:31!
> 

It's regrettable that this fixes
slob-respect-list_head-abstraction-layer.patch but doesn't apply to
that patch - slob-use-slab_list-instead-of-lru.patch gets in the way. 
So we end up with a patch series which introduces a bug and later
fixes it.

I guess we can live with that but if the need comes to respin this
series, please do simply fix
slob-respect-list_head-abstraction-layer.patch so we get a clean
series.

Re: [PATCH 1/1] slob: Only use list functions when safe to do so

[Tobin C. Harding]

On Mon, Apr 01, 2019 at 09:41:28PM -0700, Andrew Morton wrote:
> On Tue,  2 Apr 2019 14:29:57 +1100 "Tobin C. Harding" <tobin@kernel.org> wrote:
> 
> > Currently we call (indirectly) list_del() then we manually try to combat
> > the fact that the list may be in an undefined state by getting 'prev'
> > and 'next' pointers in a somewhat contrived manner.  It is hard to
> > verify that this works for all initial states of the list.  Clearly the
> > author (me) got it wrong the first time because the 0day kernel testing
> > robot managed to crash the kernel thanks to this code.
> > 
> > All this is done in order to do an optimisation aimed at preventing
> > fragmentation at the start of a slab.  We can just skip this
> > optimisation any time the list is put into an undefined state since this
> > only occurs when an allocation completely fills the slab and in this
> > case the optimisation is unnecessary since we have not fragmented the slab
> > by this allocation.
> > 
> > Change the page pointer passed to slob_alloc_page() to be a double
> > pointer so that we can set it to NULL to indicate that the page was
> > removed from the list.  Skip the optimisation if the page was removed.
> > 
> > Found thanks to the kernel test robot, email subject:
> > 
> > 	340d3d6178 ("mm/slob.c: respect list_head abstraction layer"):  kernel BUG at lib/list_debug.c:31!
> > 
> 
> It's regrettable that this fixes
> slob-respect-list_head-abstraction-layer.patch but doesn't apply to
> that patch - slob-use-slab_list-instead-of-lru.patch gets in the way. 
> So we end up with a patch series which introduces a bug and later
> fixes it.

Yes I thought that also.  Do you rebase the mm tree?  Did you apply this
right after slob-use-slab_list-instead-of-lru or to the current tip?  If
it is applied to the tip does this effect the ability to later bisect in
between these two commits (if the need arises for some unrelated reason)?

> I guess we can live with that but if the need comes to respin this
> series, please do simply fix
> slob-respect-list_head-abstraction-layer.patch so we get a clean
> series.

If its not too much work for you to apply the new series I'll do another
version just to get this right.

	Tobin.

Re: [PATCH 1/1] slob: Only use list functions when safe to do so

[Andrew Morton]

On Wed, 3 Apr 2019 06:05:38 +1100 "Tobin C. Harding" <me@tobin.cc> wrote:

> > It's regrettable that this fixes
> > slob-respect-list_head-abstraction-layer.patch but doesn't apply to
> > that patch - slob-use-slab_list-instead-of-lru.patch gets in the way. 
> > So we end up with a patch series which introduces a bug and later
> > fixes it.
> 
> Yes I thought that also.  Do you rebase the mm tree?  Did you apply this
> right after slob-use-slab_list-instead-of-lru or to the current tip?

After slob-use-slab_list-instead-of-lru.patch

>  If
> it is applied to the tip does this effect the ability to later bisect in
> between these two commits (if the need arises for some unrelated reason)?

There is a bisection hole but it is short and the bug is hardish to
hit.

> > I guess we can live with that but if the need comes to respin this
> > series, please do simply fix
> > slob-respect-list_head-abstraction-layer.patch so we get a clean
> > series.
> 
> If its not too much work for you to apply the new series I'll do another
> version just to get this right.

I guess that would be best, thanks.