2.5.39 kmem_cache bug

2.5.39 kmem_cache bug

[John Levon]

kmem_cache_destroy() is falsely reporting
"kmem_cache_destroy: Can't free all objects" in 2.5.39. I have
verified my code was freeing all allocated items correctly.

Reverting this chunk :

-                       list_add(&slabp->list, &cachep->slabs_free);
+/*                     list_add(&slabp->list, &cachep->slabs_free);            */
+                       if (unlikely(list_empty(&cachep->slabs_partial)))
+                               list_add(&slabp->list, &cachep->slabs_partial);
+                       else
+                               kmem_slab_destroy(cachep, slabp);

and the problem goes away. I haven't investigated why.

This is with CONFIG_SMP, !CONFIG_PREEMPT

regards
john

-- 
"When your name is Winner, that's it. You don't need a nickname."
	- Loser Lane

Re: 2.5.39 kmem_cache bug

[Andrew Morton]

John Levon wrote:
> 
> kmem_cache_destroy() is falsely reporting
> "kmem_cache_destroy: Can't free all objects" in 2.5.39. I have
> verified my code was freeing all allocated items correctly.
> 
> Reverting this chunk :
> 
> -                       list_add(&slabp->list, &cachep->slabs_free);
> +/*                     list_add(&slabp->list, &cachep->slabs_free);            */
> +                       if (unlikely(list_empty(&cachep->slabs_partial)))
> +                               list_add(&slabp->list, &cachep->slabs_partial);
> +                       else
> +                               kmem_slab_destroy(cachep, slabp);
> 
> and the problem goes away. I haven't investigated why.
> 

Thanks.  That's the code which leaves one empty page available
for new allocations rather than freeing it immediately.

It's temporary.  Ed, I think we can just do

	if (list_empty(&cachep->slabs_free))
		list_add(&slabp->list, &cachep->slabs_free);
	else
		kmem_slab_destroy(cachep, slabp);

there?

Re: 2.5.39 kmem_cache bug

[Manfred Spraul]

Andrew Morton wrote:
> John Levon wrote:
> 
>>kmem_cache_destroy() is falsely reporting
>>"kmem_cache_destroy: Can't free all objects" in 2.5.39. I have
>>verified my code was freeing all allocated items correctly.
>>
>>Reverting this chunk :
>>
>>-                       list_add(&slabp->list, &cachep->slabs_free);
>>+/*                     list_add(&slabp->list, &cachep->slabs_free);            */
>>+                       if (unlikely(list_empty(&cachep->slabs_partial)))
>>+                               list_add(&slabp->list, &cachep->slabs_partial);
>>+                       else
>>+                               kmem_slab_destroy(cachep, slabp);
>>
>>and the problem goes away. I haven't investigated why.
>>
> 
> 
> Thanks.  That's the code which leaves one empty page available
> for new allocations rather than freeing it immediately.
> 
> It's temporary.  Ed, I think we can just do
> 
> 	if (list_empty(&cachep->slabs_free))
> 		list_add(&slabp->list, &cachep->slabs_free);
> 	else
> 		kmem_slab_destroy(cachep, slabp);
> 
> there?

Look correct.
If you apply it, then reenable the BUG check in s_show() if a slab with 
0 allocations is found on the partial list, too.

--
	Manfred

Re: 2.5.39 kmem_cache bug

[John Levon]

On Sat, Sep 28, 2002 at 01:56:55PM -0700, Andrew Morton wrote:

> 	if (list_empty(&cachep->slabs_free))
> 		list_add(&slabp->list, &cachep->slabs_free);
> 	else
> 		kmem_slab_destroy(cachep, slabp);

This seems to work for me on a quick test.

thanks
john

-- 
"When your name is Winner, that's it. You don't need a nickname."
	- Loser Lane

Re: 2.5.39 kmem_cache bug

[Andrew Morton]

John Levon wrote:
> 
> On Sat, Sep 28, 2002 at 01:56:55PM -0700, Andrew Morton wrote:
> 
> >       if (list_empty(&cachep->slabs_free))
> >               list_add(&slabp->list, &cachep->slabs_free);
> >       else
> >               kmem_slab_destroy(cachep, slabp);
> 
> This seems to work for me on a quick test.
> 

Thanks.    I'll send the below patch.




Slab currently has a policy of buffering a single spare page per slab. 
We're putting that on the partially-full list, which confuses
kmem_cache_destroy().

So put it on cachep->slabs_free, which is where empty pages go.




 mm/slab.c |    9 ++++-----
 1 files changed, 4 insertions(+), 5 deletions(-)

--- 2.5.39/mm/slab.c~slab-fix	Sat Sep 28 14:20:52 2002
+++ 2.5.39-akpm/mm/slab.c	Sat Sep 28 14:23:50 2002
@@ -1499,9 +1499,9 @@ static inline void kmem_cache_free_one(k
 		if (unlikely(!--slabp->inuse)) {
 			/* Was partial or full, now empty. */
 			list_del(&slabp->list);
-/*			list_add(&slabp->list, &cachep->slabs_free); 		*/
-			if (unlikely(list_empty(&cachep->slabs_partial)))
-				list_add(&slabp->list, &cachep->slabs_partial);
+			/* We only buffer a single page */
+			if (list_empty(&cachep->slabs_free))
+				list_add(&slabp->list, &cachep->slabs_free);
 			else
 				kmem_slab_destroy(cachep, slabp);
 		} else if (unlikely(inuse == cachep->num)) {
@@ -1977,8 +1977,7 @@ static int s_show(struct seq_file *m, vo
 	}
 	list_for_each(q,&cachep->slabs_partial) {
 		slabp = list_entry(q, slab_t, list);
-		if (slabp->inuse == cachep->num)
-			BUG();
+		BUG_ON(slabp->inuse == cachep->num || !slabp->inuse);
 		active_objs += slabp->inuse;
 		active_slabs++;
 	}

.

Re: 2.5.39 kmem_cache bug

[Ed Tomlinson]

On September 28, 2002 04:56 pm, Andrew Morton wrote:
> John Levon wrote:
> > kmem_cache_destroy() is falsely reporting
> > "kmem_cache_destroy: Can't free all objects" in 2.5.39. I have
> > verified my code was freeing all allocated items correctly.
> >
> > Reverting this chunk :
> >
> > -                       list_add(&slabp->list, &cachep->slabs_free);
> > +/*                     list_add(&slabp->list, &cachep->slabs_free);     
> >       */ +                       if
> > (unlikely(list_empty(&cachep->slabs_partial))) +                         
> >      list_add(&slabp->list, &cachep->slabs_partial); +                   
> >    else
> > +                               kmem_slab_destroy(cachep, slabp);
> >
> > and the problem goes away. I haven't investigated why.
>kmem_cache_destroy
> Thanks.  That's the code which leaves one empty page available
> for new allocations rather than freeing it immediately.
>
> It's temporary.  Ed, I think we can just do
>
> 	if (list_empty(&cachep->slabs_free))
> 		list_add(&slabp->list, &cachep->slabs_free);
> 	else
> 		kmem_slab_destroy(cachep, slabp);
>
> there?

Yes we can do this.  I would rather fix kmem_cache_destroy though.  Think that, if 
we play our cards right, we can get rid of the cachep->slabs_free list with out too
much pain.

Ed

Re: 2.5.39 kmem_cache bug

[Manfred Spraul]

Ed Tomlinson wrote:
> 
> Yes we can do this.  I would rather fix kmem_cache_destroy though.  Think that, if 
> we play our cards right, we can get rid of the cachep->slabs_free list with out too
> much pain.
> 
Please - lets check first if the free list is actually a problem, before 
deciding to kill it.

If you remove the free list, it becomes impossible to find the freeable 
slab, if another (partial) slab is added to the partial list afterwards.

And I'm definitively against locking up one slab in each cache - it 
coudl be a order=5 allocation. It would be possible to hack around that 
(if alloc is high-order, then partial slabs do not exist), but that's 
too ugly to think about.

--
	Manfred

Re: 2.5.39 kmem_cache bug

[Ed Tomlinson]

On September 28, 2002 04:56 pm, Andrew Morton wrote:
> John Levon wrote:
> > kmem_cache_destroy() is falsely reporting
> > "kmem_cache_destroy: Can't free all objects" in 2.5.39. I have
> > verified my code was freeing all allocated items correctly.
> >
> > Reverting this chunk :
> >
> > -                       list_add(&slabp->list, &cachep->slabs_free);
> > +/*                     list_add(&slabp->list, &cachep->slabs_free);     
> >       */ +                       if
> > (unlikely(list_empty(&cachep->slabs_partial))) +                         
> >      list_add(&slabp->list, &cachep->slabs_partial); +                   
> >    else
> > +                               kmem_slab_destroy(cachep, slabp);
> >
> > and the problem goes away. I haven't investigated why.
>
> Thanks.  That's the code which leaves one empty page available
> for new allocations rather than freeing it immediately.
>
> It's temporary.  Ed, I think we can just do
>
> 	if (list_empty(&cachep->slabs_free))
> 		list_add(&slabp->list, &cachep->slabs_free);
> 	else
> 		kmem_slab_destroy(cachep, slabp);
>
> there?

How about this (untested) instead.  If we can avoid using cachep->slabs_free its 
a good thing.  Why use three lists when two can do the job?  I use a loop to clean 
the partial list since its possible that for some caches we may want to have more
than one slabp of buffer.

Thoughts?
Ed

---------
diff -Nru a/mm/slab.c b/mm/slab.c
--- a/mm/slab.c	Sun Sep 29 09:08:53 2002
+++ b/mm/slab.c	Sun Sep 29 09:08:53 2002
@@ -1036,7 +1036,26 @@
 	list_del(&cachep->next);
 	up(&cache_chain_sem);
 
-	if (__kmem_cache_shrink(cachep)) {
+	/* remove any empty partial pages */
+	spin_lock_irq(&cachep->spinlock);
+	while (!cachep->growing) {
+		struct list_head *p;
+		slab_t *slabp;
+
+		p = cachep->slabs_partial.prev;
+		if (p == &cachep->slabs_partial)
+			break;
+
+		slabp = list_entry(cachep->slabs_partial.prev, slab_t, list);
+		if (slabp->inuse)
+			break;
+
+		list_del(&slabp->list);
+
+	}
+	spin_unlock_irq(&cachep->spinlock);
+
+	if (!list_empty(&cachep->slabs_full) || !list_empty(&cachep->slabs_partial)) {
 		printk(KERN_ERR "kmem_cache_destroy: Can't free all objects %p\n",
 		       cachep);
 		down(&cache_chain_sem);

---------

Re: 2.5.39 kmem_cache bug

[Manfred Spraul]

Ed Tomlinson wrote:
>  
> -	if (__kmem_cache_shrink(cachep)) {
> +	/* remove any empty partial pages */
> +	spin_lock_irq(&cachep->spinlock);
> +	while (!cachep->growing) {
> +		struct list_head *p;
> +		slab_t *slabp;
> +

growing is guaranteed to be false - loop is not necessary.

Actually growing can be removed completely, it's never necessary, 
neither with nor without kmem_cache_reap().

Ed, there are far more cleanups possible in slab.c than just going from 
3 to 2 lists, but IMHO it's far to early to make the design decision for 
2 lists.

Or wait: You want 2 lists? Ok, agreed.

free and partial ;-)

The full list is unnecessary, it's possible to replace it with a 
counter. It also saves several cacheline accesses for the list_del() and 
list_add() into the full list...

--
	Manfred

Re: 2.5.39 kmem_cache bug

[John Levon]

On Sun, Sep 29, 2002 at 09:15:52AM -0400, Ed Tomlinson wrote:

> How about this (untested) instead.  If we can avoid using cachep->slabs_free its 
> a good thing.  Why use three lists when two can do the job?  I use a loop to clean 
> the partial list since its possible that for some caches we may want to have more
> than one slabp of buffer.

This patch seems to work for me too (though I have tested it only
lightly)

At least it fixes the false kmem_cache_destroy() report vs. 2.5.39

regards
john

-- 
"When your name is Winner, that's it. You don't need a nickname."
	- Loser Lane

Re: 2.5.39 kmem_cache bug

[Ed Tomlinson]

On September 29, 2002 12:19 pm, Manfred Spraul wrote:
> Ed Tomlinson wrote:
> > On September 29, 2002 09:52 am, Manfred Spraul wrote:
> >>Ed Tomlinson wrote:
> >>>-	if (__kmem_cache_shrink(cachep)) {
> >>>+	/* remove any empty partial pages */
> >>>+	spin_lock_irq(&cachep->spinlock);
> >>>+	while (!cachep->growing) {
> >>>+		struct list_head *p;
> >>>+		slab_t *slabp;
> >>>+
> >>
> >>growing is guaranteed to be false - loop is not necessary.
> >
> > Sort of.  Guess since the lock is not dropped if we see !growing
> > it will stay that way as long as we stay locked.  So we do need
> > to test growing but only once.  Have I understood this correctly?
>
> No. Much simpler:
> There is no synchonization between kmem_cache_destroy and
> kmem_cache_{alloc,free}. The caller must do that.
>
> Both
> 	x = kmem_cache_create();
> 	kmem_cache_destroy(x);
> 	kmem_cache_alloc(x);
>
> and all variante where kmem_cache_alloc runs at the same time as
> kmem_cache_destroy [smp, or just sleeping in gfp] are illegal.

So if growing is set something is seriously wrong...

> > We do seem to agree on most issues.  Lets work with this and hopefully we
> > can end up with a firsst class slab implementation that works hand in
> > hand with the vm and helps the whole system perform effectivily.
>
> Yes, lets work together. Implementing & debugging slab is simple [if it
> boots, then it's correct], the design is difficult.
>
> The first problem is the per-cpu array draining. It's needed, too many
> objects can sit in the per-cpu arrays.
> < 2.5.39, the per-cpu arrays can cause more list operations than no
> batching, this is something that must be avoided.
>
> Do you see an alternative to a timer/callback/hook? What's the simplest
> approach to ensure that the callback runs on all cpus? I know Redhat has
> a scalable timer patch, that one would fix the timer to the cpu that
> called add_timer.

Maybe.  If we treat the per cpu data as special form of cache we could
use the shrinker callbacks to track how much we have to trim.  When the value
exceeds a threshold (set when we setup the callback) we trim.  We could
do the test in freeing path in slab.   

> My proposal would be a 1 (or 2, or 5) seconds callback, that frees
> 0.2*cc->limit, if there were no allocations from the slab during the
> last interval.

Using the above logic would tie the trimming to vm scanning pressure,
which is probably a good idea.  

The patch add shrinker callbacks was posted to linux-mm Sunday and
to lkml on Thursday.

My schedule lets me read and answer a little mail in the mornings (7-8am 
EDT).  When I get home from work (5pm EDT) I usually have a few hours to 
code etc.

Ed

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: 2.5.39 kmem_cache bug

[Manfred Spraul]

Ed Tomlinson wrote:
>
>>The first problem is the per-cpu array draining. It's needed, too many
>>objects can sit in the per-cpu arrays.
>>< 2.5.39, the per-cpu arrays can cause more list operations than no
>>batching, this is something that must be avoided.
>>
>>Do you see an alternative to a timer/callback/hook? What's the simplest
>>approach to ensure that the callback runs on all cpus? I know Redhat has
>>a scalable timer patch, that one would fix the timer to the cpu that
>>called add_timer.
> 
> 
> Maybe.  If we treat the per cpu data as special form of cache we could
> use the shrinker callbacks to track how much we have to trim.  When the value
> exceeds a threshold (set when we setup the callback) we trim.  We could
> do the test in freeing path in slab.   
>
2 problems:
* What if a cache falls completely idle? If there is freeing activity on 
the cache, then the cache is active, thus there is no need to flush.
* I don't think it's a good idea to add logic into the path that's 
executed for every kfree/kmem_cache_free. A timer might not be very 
pretty, but is definitively more efficient.

> The patch add shrinker callbacks was posted to linux-mm Sunday and
> to lkml on Thursday.
> 
I'll read them.
Is it guaranteed that the shrinker callbacks are called on all cpus, or 
could some cpu binding happen?

--
	Manfred

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: 2.5.39 kmem_cache bug

[Ed Tomlinson]

On September 30, 2002 01:55 am, Manfred Spraul wrote:
> Ed Tomlinson wrote:
> >>The first problem is the per-cpu array draining. It's needed, too many
> >>objects can sit in the per-cpu arrays.
> >>< 2.5.39, the per-cpu arrays can cause more list operations than no
> >>batching, this is something that must be avoided.
> >>
> >>Do you see an alternative to a timer/callback/hook? What's the simplest
> >>approach to ensure that the callback runs on all cpus? I know Redhat has
> >>a scalable timer patch, that one would fix the timer to the cpu that
> >>called add_timer.
> >
> > Maybe.  If we treat the per cpu data as special form of cache we could
> > use the shrinker callbacks to track how much we have to trim.  When the
> > value exceeds a threshold (set when we setup the callback) we trim.  We
> > could do the test in freeing path in slab.
>
> 2 problems:
> * What if a cache falls completely idle? If there is freeing activity on
> the cache, then the cache is active, thus there is no need to flush
> * I don't think it's a good idea to add logic into the path that's
> executed for every kfree/kmem_cache_free. A timer might not be very
> pretty, but is definitively more efficient.
> > The patch add shrinker callbacks was posted to linux-mm Sunday and
> > to lkml on Thursday.
>
> I'll read them.
> Is it guaranteed that the shrinker callbacks are called on all cpus, or
> could some cpu binding happen?

There is no guarantee.  The best we could use them for is to link the 'pressure'
on the percpu stuff to vm pressure.   From the above is does look like timers
are the way to go.

Ed

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/

Re: 2.5.39 kmem_cache bug

[Manfred Spraul]

What's the optimal number of free objects in the partial/free lists of 
an active cache?

I'd say a few times the batchcount, otherwise a cpu won't be able to 
perform a complete refill. [during refill, at most one grow happens - 
I've assumed that swallowing 30 pages with GFP_ATOMIC in an interrupt 
handler is not nice from the system perspective]

What about this logic:
- if there were no recent allocations performed by a cpu, then return 
cc->limit/5 objects from the cpu array to the node lists.

- If a slab becomes a free slab, and there are more than 
3*cc->batchcount*NR_CPUS/NR_NODES objects in the partial or free lists, 
then return the slab immediately to the gfp.

- If noone accessed the free list recently, then a few slabs are 
returned to gfp. [<worst case number of free slabs that can exist>/5]

The constants could be updated by vm pressure callbacks.

--
	Manfred

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/