Since 2.6.25-rc7, I've been seeing an occasional livelock on one

x86_64 machine, copying kernel trees to tmpfs, paging out to swap.
Signature: 6000 pages under writeback but never getting written;

most tasks of interest trying to reclaim, but each get_swap_bio

waiting for a bio in mempool_alloc's io_schedule_timeout(5*HZ);

every five seconds an atomic page allocation failure report from

kblockd failing to allocate a sense_buffer in __scsi_get_command.
__scsi_get_command has a (one item) free_list to protect against

this, but rc1's [SCSI] use dynamically allocated sense buffer

de25deb18016f66dcdede165d07654559bb332bc upset that slightly.

When it fails to allocate from the separate sense_slab, instead

of giving up, it must fall back to the command free_list, which

is sure to have a sense_buffer attached.
Either my earlier -rc testing missed this, or there's some recent

contributory factor.  One very significant factor is SLUB, which

merges slab caches when it can, and on 64-bit happens to merge

both bio cache and sense_slab cache into kmalloc's 128-byte cache:

so that under this swapping load, bios above are liable to gobble

up all the slots needed for scsi_cmnd sense_buffers below.
That's disturbing behaviour, and I tried a few things to fix it.

Adding a no-op constructor to the sense_slab inhibits SLUB from

merging it, and stops all the allocation failures I was seeing;

but it's rather a hack, and perhaps in different configurations

we have other caches on the swapout path which are ill-merged.
Another alternative is to revert the separate sense_slab, using

cache-line-aligned sense_buffer allocated beyond scsi_cmnd from

the one kmem_cache; but that might waste more memory, and is

only a way of diverting around the known problem.
While I don't like seeing the allocation failures, and hate the

idea of all those bios piled up above a scsi host working one by

one, it does seem to emerge fairly soon with the livelock fix.

So lacking better ideas, stick with that one clear fix...
[ message continues ]

A reliance on free slots that the slab allocator may provide? That is a

rather bad dependency since it is up to the slab allocator to implement

the storage layout for the objects and thus the availability of slots may

vary depending on the layout for the objects chosen by the allocator.
Looking at mempool_alloc: Mempools may be used to do atomic allocations

until they fail thereby exhausting reserves and available object in the

partial lists of slab caches?
In order to make this a significant factor we need to have already

exhausted reserves right? Thus we are already operating at the boundary of

what memory there is. Any non atomic alloc will then allocate a new page

with N elements in order to get one object. The mempool_allocs from the

atomic context will then gooble up the N-1 remaining objects? So the

nonatomic alloc will then have to hit the page allocator again...
--

I'm not sure that I understand you.  Yes, different slab allocators

may lay out slots differently.  But a significant departure from

existing behaviour may be a bad idea in some circumstances.
Mempools may be used for atomic allocations, but I think that's not

the case here.  swap_writepage's get_swap_bio says GFP_NOIO, which

allows (indeed is) __GFP_WAIT, and does not give access to __GFP_HIGH

reserves.
Whereas at the __scsi_get_command end, there are GFP_ATOMIC sense_slab

allocations, which do give access to __GFP_HIGH reserves.
My supposition is that once a page has been allocated from __GFP_HIGH

reserves to a scsi sense_slab, swap_writepages are liable to gobble up

the rest of the page with bio allocations which they wouldn't have had

access to traditionally (i.e. under SLAB).
So an unexpected behaviour emerges from SLUB's slab merging.
Though of course the same might happen in other circumstances, even

without slab merging: if some kmem_cache allocations are made with

GFP_ATOMIC, those can give access to reserves to non-__GFP_HIGH

allocations from the same kmem_cache.
Maybe PF_MEMALLOC and __GFP_NOMEMALLOC complicate the situation:

I've given little thought to mempool_alloc's fiddling with the
We need to have already exhausted reserves, yes: so this isn't an

issue hitting everyone all the time, and it may be nothing worse

than a surprising anomaly; but I'm pretty sure it's not how bio

and scsi command allocation is expected to interact.
What do you think a SLAB_NOMERGE flag?  The last time I suggested

something like that (but I was thinking of debug), your comment

was "Ohh..", which left me in some doubt ;)
If we had a SLAB_NOMERGE flag, would we want to apply it to the

bio cache or to the scsi_sense_cache or to both?  My difficulty

in answering that makes me wonder whether such a flag is right.
Hugh

--

Looks like that one of the issues here is that swap_writepage()

does not perform enough reclaim? If it would free more pages then

__scsi_get_command would still have pages to allocate and not drain
Mempool_alloc()s use of the gfp_mask here suggests that it can potentially

drain all reserves and exhaust all available "slots" (partial slabs). Thus

it may regularly force any other user of the slab to hit the slow path

and potentially trigger reclaim. Could be a bit unfair.

--

Somewhere along the line of my swap over network patches I made

'robustified' SLAB to ensure these sorts of things could not happen - it

came at a cost though.
It would basically fail[*] allocations that had a higher low watermark

than what was used to allocate the current slab.
[*] - well, it would attempt to allocate a new slab to raise the current
My latest series ensures that SLABs allocated using PF_MEMALLOC will not

distribute objects to allocation contexts that are not entitled for as

long as the memory shortage lasts.
I'm not sure how applicable this is to the problem at hand, just letting
Relying on this is highly dubious, who is to say that first __GFP_HIGH

alloc came SCSI layer (there could be another merged slab).
Also, when one of these users is PF_MEMALLOC the other users will gobble
If this is critical to avoid memory deadlocks, I would suggest using

mempools (or my reserve framework).
--

Thanks, Peter: that sounds just right to me; but a larger change than

we'd want to jump into for this one particular issue - it might have
No, the critical part of it has been dealt with (small fix to scsi

free_list handling: which resembles a mempool, but done its own way).
What remains is about "unsightly" behaviour, the system having a

tendency to collapse briefly into far-from-efficient operation

when out of memory.
Hugh

--

Hi Hugh,
Although you weren't convinced by my arguments, I still have

difficulties understanding why this kind of bad behavior would be

acceptable in an embedded environment and why we don't need to fix it

for the SLOB case as well.
But you do bring up a good point of SLUB changing the behavior on OOM

situations for which SLAB_NOMERGE sounds like a good-enough stop-gap

measure for the short term. I would prefer some other fix even if it

means getting rid of slab merging competely (which would suck as it's

very nice for making memory footprint smaller).
		Pekka

--

I wonder if we can get away with a SLAB_IO flag that you can use to

annotate caches that participate in writeout and the allocator could

keep some spare pages around that can be handed out for them in case of

OOM...
		Pekka

--

If we do decide that it's seriously bad behaviour, then of course

it should be fixed in SLOB also.  I just meant that the fact that

SLOB's been merging slabs too doesn't give me great confidence that
Well, the work of keeping spares around to be handed out in case of

OOM was done in 2.5 with mempools.  They seem to be working well

(until you try swapping over network as Peter is pursuing),

I don't think we need to duplicate that.
I've the uncomfortable feeling that I'm making a big fuss over this

behaviour on the one hand, but utterly failing to justify that fuss

on the other.  It seems to come down to me wanting fewer backtraces

in my logs: I'd better find stronger reasons than that if we're to

pursue this.
Hugh

--

No, I do agree that it's a problem. I just don't like the proposed

no-merge fix ;-).
		Pekka

--

Actually, I don't think this is SLAB-specific, since there are potentially

the same issues for pages.
I suspect the right thing to do is not to mark them for "IO", but mark

them for "short-lived", and allow short-lived allocations that don't have

extended lifetimes to succeed even when a "real" allocation wouldn't.
When we are under memory pressure, a normal allocation generally needs to

clear up enough memory from elsewhere to succeed. But a short-lived

allocation without any long-term lifetimes would be known to release its

memory back to the pool, so it can be allowed to go ahead when a normal

memory allocation would not.
Examples of short-lived allocations:

 - IO requests

 - temporary network packets that don't get queued up (eg "ACK" packet) as

   opposed to those that do get queued (incoming _or_ outgoing queues)

 - things like the temporary buffers for "getname()/putname()" etc.
That said, even a lot of temporary allocations can at times have issues.

If your IO layer is dead, your IO request queues that _should_ have been

very temporary may end up staying around for a long time. But I do think

that it makes sense to prioritize allocations that are known to be short-

lived.
(It might also allows us to allocate them from different pools and just

generally have other heuristics for cache behaviour - short-lived

allocations simply have different behaviour)
			Linus

--

Hi Linus,
Yeah, makes sense. We do have GFP_TEMPORARY so we could associate this

new semantics with that. But the real problem here is how to do the

"allocate harder" part which, btw, sounds very similar to what Peter's

kmalloc reserve patches try to do...
		Pekka

--

Actually, a trivial way to implement that is to have a few "emergency

kmalloc" caches say for sizes 64, 128, 256, and 512 that have some

pre-allocated pages into which these GFP_TEMPORARY allocations are

allowed to dip into on OOM and OOM only.
		Pekka

--

So something like the following (totally untested) patch modulo the

pre-allocation bits.
		Pekka
diff --git a/mm/slub.c b/mm/slub.c

index acc975f..e8f7cf3 100644

--- a/mm/slub.c

+++ b/mm/slub.c

@@ -264,6 +264,67 @@ static inline void stat(struct kmem_cache_cpu *c, enum stat_item si)

 #endif

 }
+/*

+ * Emergency caches are for GFP_TEMPORARY allocations to dip into when we're

+ * OOM to make sure we can make some progress for writeback.

+ */

+

+#define MIN_EMERGENCY_SIZE 32

+#define NR_EMERGENCY_CACHES 4

+

+struct kmem_cache *emergency_caches[NR_EMERGENCY_CACHES];

+

+static void init_emergency_caches(void)

+{

+	unsigned long size = MIN_EMERGENCY_SIZE;

+	int i;

+

+	for (i = 0; i < NR_EMERGENCY_CACHES; i++) {

+		struct kmem_cache *cache;

+		char *name;

+

+		name = kasprintf(GFP_KERNEL, "kmalloc-%d", 1 << i);

+		BUG_ON(!name);

+

+		cache = kmem_cache_create(name, size, 0, 0, NULL);

+		BUG_ON(!cache);

+		kfree(name);

+

+		emergency_caches[i] = cache;

+

+		size *= 2;

+	}

+}

+

+static struct kmem_cache *lookup_emergency_cache(unsigned long size)

+{

+	unsigned long cache_size = MIN_EMERGENCY_SIZE;

+	int i;

+

+	for (i = 0; i < NR_EMERGENCY_CACHES; i++) {

+		if (size < cache_size)

+			return emergency_caches[i];

+

+		cache_size *= 2;

+	}

+	return NULL;

+}

+

+static void *emergency_alloc(struct kmem_cache *cache, gfp_t gfp)

+{

+	struct kmem_cache *emergency_cache;

+	void *p;

+

+	emergency_cache = lookup_emergency_cache(cache->objsize);

+	if (!emergency_cache)

+		return NULL;

+

+	p = kmem_cache_alloc(emergency_cache, gfp);

+	if (p && cache->ctor)

+		cache->ctor(cache, p);

+	return p;

+}

+

 /********************************************************************

  * 			Core slab cache functions

  *******************************************************************/

@@ -1528,6 +1589,9 @@ new_slab:

 		goto load_freelist;

 	}
+	if ((gfpflags & GFP_TEMPORARY) == GFP_TEMPORARY)

+		return emergency_alloc(s, gfpf...
[ message continues ]

Hmm. I didn't check, but won't this cause problems on the freeing path

when we call kmem_cache_free() on the result but with the wrong "struct

kmem_cache" pointer?
		Linus

--

So something like this fugly patch on top of the SLUB variable order

patches that let the allocator fall-back to smaller page orders. Survives

OOM in my testing and the box seems to be bit more responsive even under X

with this.
		Pekka
---

 mm/slub.c |   93 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

 1 file changed, 92 insertions(+), 1 deletion(-)
Index: slab-2.6/mm/slub.c

===================================================================

--- slab-2.6.orig/mm/slub.c	2008-04-08 22:52:02.000000000 +0300

+++ slab-2.6/mm/slub.c	2008-04-08 23:27:27.000000000 +0300

@@ -1549,6 +1549,88 @@

 }
 /*

+ * Emergency caches are reserved for GFP_TEMPORARY allocations on OOM.

+ */

+

+#define MIN_EMERGENCY_SIZE 32

+#define NR_EMERGENCY_CACHES 4

+

+struct kmem_cache *emergency_caches[NR_EMERGENCY_CACHES];

+

+static void pre_alloc_cpu_slabs(struct kmem_cache *s)

+{

+	int cpu;

+

+	/*

+	 * FIXME: CPU hot-plug, stats, debug?

+	 */

+	for_each_online_cpu(cpu) {

+		struct kmem_cache_cpu *c;

+		struct page *new;

+		void **object;

+		int node;

+

+		c = get_cpu_slab(s, cpu);

+		node = cpu_to_node(cpu);

+

+		new = new_slab(s, GFP_KERNEL, node);

+		BUG_ON(!new);

+

+		slab_lock(new);

+		SetSlabFrozen(new);

+		c->page = new;

+		object = c->page->freelist;

+		c->freelist = object[c->offset];

+		c->page->inuse = c->page->objects;

+		c->page->freelist = NULL;

+		c->node = page_to_nid(c->page);

+		slab_unlock(c->page);

+	}

+}

+

+static void init_emergency_caches(void)

+{

+	unsigned long size = MIN_EMERGENCY_SIZE;

+	int i;

+

+	for (i = 0; i < NR_EMERGENCY_CACHES; i++) {

+		struct kmem_cache *cache;

+		char *name;

+

+		name = kasprintf(GFP_KERNEL, "kmalloc-%d", 1 << i);

+		BUG_ON(!name);

+

+		cache = kmem_cache_create(name, size, 0, 0, NULL);

+		BUG_ON(!cache);

+		kfree(name);

+

+		pre_alloc_cpu_slabs(cache);

+		emergency_caches[i] = cache;

+

+		size *= 2;

+	}

+}

+

+static void *emergency...
[ message continues ]

Hmmmm... Peter has the most experience with these issues. Maybe the best

would be to have this sort of logic in a more general way in the page

allocator? Similar issues surely exist with the page allocator and a fix

there would fix it for all users.
--

This needs some support in the slab allocator anyway. Keep in mind that

the patch is specifically addressing writeback in OOM conditions so we

must (1) prioritize GFP_TEMPORARY allocations over everyone else (which

just get NULL) and (2) use the remaining available memory as efficiently

as possible for _all_ GFP_TEMPORARY allocations.
Peter is, however, bringing up a good point that my patch doesn't

actually _guarantee_ anything so I'm still wondering if this approach

makes any sense... But I sure do like Linus' ideas of marking

short-lived allocations and trying harder for them in OOM.
			Pekka

--

Also, this scheme so far does not provide for a means to detect the end

of pressure situation.
I need both triggers, enter pressure and exit pressure. Enter pressure

is easy enough, that's when normal allocations start failing. Exit

pressure however is more difficult - that is basically when allocations

start succeeding again. You'll see that my patches basically always

attempt a regular allocation as long as we're in the emergency state.
Also, the requirement for usage of emergency memory (GFP_MEMALLOC,

PF_MEMALLOC) is that it will be freed without external conditions. So

while it might be delayed for a while (it might sit in the fragment

assembly cache for a while) it doesn't need any external input to get

freed again:

  - it will either get reclaimed from this cache;

  - it will exit the cache as a full packet and:

    - get dropped, or

    - get processed.
--

...uh-oh hand over the paper bag. I have no GFP_TEMPORARY allocations

going on...

--

Aah, yes. I was thinking of kmalloc() here for which it works as

expected because kfree() will return the page to the proper cache. But

we can relax the rules of kmem_cache_free() a bit to make this work (but

perhaps add a WARN_ON() there if cache doesn't match page->slab).
			Pekka

--

Right, but I doubt we'd ever get something like that merged though -

esp. as it will basically destroy the SLUB fast-path.
SLAB allocation fairness:

  http://lkml.org/lkml/2007/1/16/61
I abandoned this approach because it was too expensive; it was reduced

to the ALLOC_NO_WATERMARKS state transition. Which is much more unlikely

to happen and it's generally accepted we're in a slow path once we

really dive so low into the reserves.
The latest posting:

  http://lkml.org/lkml/2008/3/20/214
--

On Sun, 6 Apr 2008 23:56:57 +0100 (BST)
Reverting the separate sense_slab is fine for now but we need the

separation shortly anyway. We need to support larger sense buffer (260

bytes). The current 96 byte sense buffer works for the majority of us,
As you and James agreed, the patch in scsi-misc looks good to me.
Thanks for finding this bug.

--

No, it's brought attention to this interesting slab merge issue;
I don't believe you _need_ a separate sense_slab even for that:

what I meant was that you just need something like

	pool->cmd_slab = kmem_cache_create(pool->cmd_name,

					   cache_line_align(

					   sizeof(struct scsi_cmnd)) +

					   max_scsi_sense_buffersize,

					   0, pool->slab_flags, NULL);

then point cmd->sense_buffer to (unsigned char *) cmd +

			cache_line_align(sizeof(struct scsi_cmnd));

where cache_line_align and max_scsi_sense_buffersize are preferably

determined at runtime.
Now, it may well be that over the different configurations, at least

some would waste significant memory by putting it all in the one big

buffer, and you're better off with the separate slabs: so I didn't

want to interfere with your direction on that.
Hugh

--

On Mon, 7 Apr 2008 19:07:56 +0100 (BST)
Yeah, seems that it led to an interesting discussion (using cache

behavior like ephemeral sounds useful, I think) though surely this is
Yes, if we have only 96 and 260 bytes sense buffers, it would be a

solution. Well, evne if we have various length sense buffers, we can

have a pool per driver (or device, scsi_host, etc).
Another reason why we separated them is that we could allocate a sense

buffer only when it's necessary (though I'm not sure we will do it
Yes, this was about wasting memory (with the one big buffer)

vs. overheads due to allocating two buffers. After some performance

tests, we chose the latter but we might change this again in the

future.

--

This was sort of accidentally fixed in scsi-misc by commit 
commit c5f73260b289cb974928eac05f2d84e58ddfc020

Author: James Bottomley <James.Bottomley@HansenPartnership.com>

Date:   Thu Mar 13 11:16:33 2008 -0500
    [SCSI] consolidate command allocation in a single place
Could you check that:
master.kernel.org:/pub/scm/linux/kernel/git/jejb/scsi-misc-2.6.git
and see if it alleviates the problem? ... if so, we can work out which

pieces to backport.
Thanks,
James
--

Precisely that patch seems appropriate to 2.6.25-rc8-git, so I'm now

running the test with just that applied to 2.6.25-rc8 (plus cfq rcu

fix).  Not quite what you asked, but...
Strictly speaking, it'd take a couple of days to be reasonably sure

that the livelock is gone (it appeared to reproduce quicker once I

moved to -rc8 plus cfq rcu fix; but I'm not entirely convinced that

wasn't just coincidence).  But if nothing bad appears overnight,

let's assume your patch is the one to push: I'll report tomorrow.
Hugh
--

Right, as expected, that seems to run fine: I've seen no problem with

it in 17 hours - beyond, of course, all the page allocation failures

which will plague such tests until something else is changed.
Somewhat irrelevant since Linus put my patch into 2.6.25-rc8-git

(probably worth it for the various issues noted in the comment);

but reassuring for 2.6.26.
I'll stop that test now and put it to work on something else.
Hugh

--

Well ... just remember that to merge scsi-misc with what Linus has now

done, I'm effectively reversing your patch, so testing current scsi-misc

is very valuable if you want the problem not to recur in 2.6.26 ...
James
--

Exactly.
Hugh

--