[RFC 0/4] Object reclaim via the slab allocator V1

[RFC 0/4] Object reclaim via the slab allocator V1

[Christoph Lameter]

We currently have a set of problem with slab reclaim:

1. On a NUMA system there are excessive cross node accesses.
   Locks are taken remotely which leads to a significant slowdown
   if concurrent reclaim is performeed on the dcache/icache from
   a number of nodes.

2. We need to free an excessive number of elements from the LRU
   in order to reclaim enough pages from the slab.

3. After reclaim we have a large number of sparsely used slab
   objects.

The fundamental problem in the current reclaim approaches with the
icache/dcache is that the reclaim is LRU and object based. Multiple
objects can share the same slab. So removing one object from a slab
just removes some cache information that may have been useful later
but may not give us what we want: More free pages.

I propose that we replace the LRU based object management by using
the slab oriented lists in the slab allocator itself for reclaim.

The slab allocator already has references to all pages used by the
dcache and icache. It has awareness of which objects are located
in a certain slab and therefore would be able to free specific
objects that would make pages freeable if the slab knew
their state.

In order to allow the slab allocator to know about an objects
state we add another flag SLAB_RECLAIM. SLAB_RECLAIM means that
the following is true of a slab:

1. The object contains a reference counter of atomic_t as the
   first element that follows the following conventions:

   Counter = 0	-> Object is being freed or is free.
   Counter = 1  -> Object is not used and contains cache information.
   		   The object may be freed.

   Counter > 1	-> Object is in use and cannot be freed.

2. A destructor was provided during kmem_cache_create().
   If SLAB_DTOR_FREE is passed in the flags of the destructor
   then a best effort attempt will be made to free that object.


Memory can then be reclaimed from a slab by calling

kmem_cache_reclaim(kmem_cache_t *cachep, unsigned long page)

kmem_cache_reclaim returns an error code or the number of pages reclaimed.


The reclaim works by walking through the lists of full and partially
allocated slabs. We begin at the end of thet fully allocated slabs because
these slabs have been around for a long time (This basically preserves the LRU
lists to some extend).

For slab we check all the objects in the slab. If all object have
a refcount of one then we free all the objects and return the pages of the
object to the page allocator.

So we could just free all the truly freeable slabs and leave the rest alone
in order to preserve the cached information.

However, with that a single object with a higher reference count would prevent
the reclaim of all other unused objects in that slab. So we free a couple of
those unused elements in each slab that is fully allocated.

This leads to a slow circulation of unused elements in fully allocated slabs.
So over time it is likely that continually active elements accumulate in slabs
that are in long term use which increases the allocation density of the slab
objects.

The idea of how to do this reclaim was developed a couple of month ago in a
meeting of Nick Piggin, Dave Chinner and me in Melbourne.

Note that this patch is only at the idea stage for now. It has not been tested
and no slab uses the new reclaim functionality until now. In order for the new
scheme to be useful we need to remove the LRU lists from the dcache and icache
and replace their reclaim algorithm.

That in turn will allow a lot of reduction of complexity in both. However, I
am not that familiar with it and so I thought it may be best to first discuss
the idea and maybe get some help with either of those.

The approach could be extended to allow the freeing of slab pages with
one single object by allowing the use of SLAB_DTOR_FREE on objects with higher
refcount. If one thinks further along those lines then we will get the ability
to migrate slab objects.

The current patchset contains 4 patches (the first two could be reviewed
for kernel inclusion):

1. Freelist code consolidation
	We will need to drain freelists repeatedly so consolidate existing code.

2. Mon destructor removal.
	We will change the nature of destructors. USB MON uses an empty
	destructor. Get that out of the way.

3. Make destructors check for SLAB_DTOR_DESTROY
	Only run the existing destructors if SLAB_DTOR_DESTROY is specified.

4. The slab reclaim functionality

[RFC 1/4] slab freeing consolidation

[Christoph Lameter]

slab: consolidate code to free slabs from freelist

Code in __shrink_node() duplicates code in cache_reap()

Add a new function drop_freelist that removes slabs with objects
that are already free and use that in various places.

This eliminates the __node_shrink() function and provides
the interrupt holdoff reduction from slab_free to code that
used to call __node_shrink.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.17-rc6-mm2/mm/slab.c
===================================================================
--- linux-2.6.17-rc6-mm2.orig/mm/slab.c	2006-06-16 11:48:52.882541096 -0700
+++ linux-2.6.17-rc6-mm2/mm/slab.c	2006-06-17 14:28:47.626589639 -0700
@@ -459,7 +459,7 @@ struct kmem_cache {
 #define	STATS_DEC_ACTIVE(x)	((x)->num_active--)
 #define	STATS_INC_ALLOCED(x)	((x)->num_allocations++)
 #define	STATS_INC_GROWN(x)	((x)->grown++)
-#define	STATS_INC_REAPED(x)	((x)->reaped++)
+#define	STATS_ADD_REAPED(x,y)	((x)->reaped += (y))
 #define	STATS_SET_HIGH(x)						\
 	do {								\
 		if ((x)->num_active > (x)->high_mark)			\
@@ -483,7 +483,7 @@ struct kmem_cache {
 #define	STATS_DEC_ACTIVE(x)	do { } while (0)
 #define	STATS_INC_ALLOCED(x)	do { } while (0)
 #define	STATS_INC_GROWN(x)	do { } while (0)
-#define	STATS_INC_REAPED(x)	do { } while (0)
+#define	STATS_ADD_REAPED(x,y)	do { } while (0)
 #define	STATS_SET_HIGH(x)	do { } while (0)
 #define	STATS_INC_ERR(x)	do { } while (0)
 #define	STATS_INC_NODEALLOCS(x)	do { } while (0)
@@ -707,7 +707,6 @@ static void free_block(struct kmem_cache
 			int node);
 static void enable_cpucache(struct kmem_cache *cachep);
 static void cache_reap(void *unused);
-static int __node_shrink(struct kmem_cache *cachep, int node);
 
 static inline struct array_cache *cpu_cache_get(struct kmem_cache *cachep)
 {
@@ -1246,10 +1245,7 @@ free_array_cache:
 			l3 = cachep->nodelists[node];
 			if (!l3)
 				continue;
-			spin_lock_irq(&l3->list_lock);
-			/* free slabs belonging to this node */
-			__node_shrink(cachep, node);
-			spin_unlock_irq(&l3->list_lock);
+			drain_freelist(cachep, l3, l3->free_objects);
 		}
 		mutex_unlock(&cache_chain_mutex);
 		break;
@@ -2277,34 +2273,47 @@ static void drain_cpu_caches(struct kmem
 	}
 }
 
-static int __node_shrink(struct kmem_cache *cachep, int node)
+/*
+ * Remove slabs from the list of free slabs.
+ * Specify the number of slabs to drain in tofree.
+ *
+ * Returns the actual number of slabs released.
+ */
+static int long drain_freelist(struct kmem_cache *cachep,
+		struct kmem_list3 *l3, int tofree)
 {
+	struct list_head *p;
+	int nr_freed;
 	struct slab *slabp;
-	struct kmem_list3 *l3 = cachep->nodelists[node];
-	int ret;
 
-	for (;;) {
-		struct list_head *p;
+	nr_freed = 0;
+	while (nr_freed < tofree && !list_empty(&l3->slabs_free)) {
 
-		p = l3->slabs_free.prev;
-		if (p == &l3->slabs_free)
-			break;
+		spin_lock_irq(&l3->list_lock);
+		p = l3->slabs_free.next;
+		if (p == &(l3->slabs_free)) {
+			spin_unlock_irq(&l3->list_lock);
+			return nr_freed;
+		}
 
-		slabp = list_entry(l3->slabs_free.prev, struct slab, list);
+		slabp = list_entry(p, struct slab, list);
 #if DEBUG
 		BUG_ON(slabp->inuse);
 #endif
 		list_del(&slabp->list);
-
+		/*
+		 * Safe to drop the lock. The slab is no longer linked
+		 * to the cache.
+		 */
 		l3->free_objects -= cachep->num;
 		spin_unlock_irq(&l3->list_lock);
 		slab_destroy(cachep, slabp);
-		spin_lock_irq(&l3->list_lock);
-	}
-	ret = !list_empty(&l3->slabs_full) || !list_empty(&l3->slabs_partial);
-	return ret;
+		nr_freed ++;
+	};
+	return nr_freed;
 }
 
+
 static int __cache_shrink(struct kmem_cache *cachep)
 {
 	int ret = 0, i = 0;
@@ -2315,11 +2324,10 @@ static int __cache_shrink(struct kmem_ca
 	check_irq_on();
 	for_each_online_node(i) {
 		l3 = cachep->nodelists[i];
-		if (l3) {
-			spin_lock_irq(&l3->list_lock);
-			ret += __node_shrink(cachep, i);
-			spin_unlock_irq(&l3->list_lock);
-		}
+		drain_freelist(cachep, l3, l3->free_objects);
+
+		ret += !list_empty(&l3->slabs_full) ||
+			!list_empty(&l3->slabs_partial);
 	}
 	return (ret ? 1 : 0);
 }
@@ -3757,9 +3765,6 @@ static void cache_reap(void *unused)
 	}
 
 	list_for_each_entry(searchp, &cache_chain, next) {
-		struct list_head *p;
-		int tofree;
-		struct slab *slabp;
 
 		check_irq_on();
 
@@ -3785,41 +3790,15 @@ static void cache_reap(void *unused)
 
 		drain_array(searchp, l3, l3->shared, 0, node);
 
-		if (l3->free_touched) {
+		if (l3->free_touched)
 			l3->free_touched = 0;
-			goto next;
-		}
-
-		tofree = (l3->free_limit + 5 * searchp->num - 1) /
-				(5 * searchp->num);
-		do {
-			/*
-			 * Do not lock if there are no free blocks.
-			 */
-			if (list_empty(&l3->slabs_free))
-				break;
-
-			spin_lock_irq(&l3->list_lock);
-			p = l3->slabs_free.next;
-			if (p == &(l3->slabs_free)) {
-				spin_unlock_irq(&l3->list_lock);
-				break;
-			}
+		else {
+			int x;
 
-			slabp = list_entry(p, struct slab, list);
-			BUG_ON(slabp->inuse);
-			list_del(&slabp->list);
-			STATS_INC_REAPED(searchp);
-
-			/*
-			 * Safe to drop the lock. The slab is no longer linked
-			 * to the cache. searchp cannot disappear, we hold
-			 * cache_chain_lock
-			 */
-			l3->free_objects -= searchp->num;
-			spin_unlock_irq(&l3->list_lock);
-			slab_destroy(searchp, slabp);
-		} while (--tofree > 0);
+			x = drain_freelist(searchp, l3, (l3->free_limit +
+				5 * searchp->num - 1) / (5 * searchp->num));
+			STATS_ADD_REAPED(searchp, x);
+		}
 next:
 		cond_resched();
 	}

Re: [RFC 1/4] slab freeing consolidation

[Pekka J Enberg]

HI,

On Mon, 19 Jun 2006, Christoph Lameter wrote:
> Add a new function drop_freelist that removes slabs with objects
> that are already free and use that in various places.

I think you mean drain_freelist().  Anyway, looks good.  Some 
minor comments below.

> -static int __node_shrink(struct kmem_cache *cachep, int node)
> +/*
> + * Remove slabs from the list of free slabs.
> + * Specify the number of slabs to drain in tofree.
> + *
> + * Returns the actual number of slabs released.
> + */
> +static int long drain_freelist(struct kmem_cache *cachep,
> +		struct kmem_list3 *l3, int tofree)

I have been trying to slowly kill the 'p' prefix so I'd appreciate if you 
could just call the parameter 'cache'.  Also, l3 could be 'lists'.

> +	nr_freed = 0;
> +	while (nr_freed < tofree && !list_empty(&l3->slabs_free)) {
>  
> -		p = l3->slabs_free.prev;
> -		if (p == &l3->slabs_free)
> -			break;
> +		spin_lock_irq(&l3->list_lock);
> +		p = l3->slabs_free.next;
> +		if (p == &(l3->slabs_free)) {

Please drop the redundant parenthesis.

> +			spin_unlock_irq(&l3->list_lock);
> +			return nr_freed;
> +		}

Goto to the bottom would be nicer than return here, maybe.

>  
> -		slabp = list_entry(l3->slabs_free.prev, struct slab, list);
> +		slabp = list_entry(p, struct slab, list);
>  #if DEBUG
>  		BUG_ON(slabp->inuse);
>  #endif
>  		list_del(&slabp->list);
> -
> +		/*
> +		 * Safe to drop the lock. The slab is no longer linked
> +		 * to the cache.
> +		 */
>  		l3->free_objects -= cachep->num;
>  		spin_unlock_irq(&l3->list_lock);
>  		slab_destroy(cachep, slabp);
> -		spin_lock_irq(&l3->list_lock);
> -	}
> -	ret = !list_empty(&l3->slabs_full) || !list_empty(&l3->slabs_partial);
> -	return ret;
> +		nr_freed ++;

Redundant whitespace.

> +	};

Redundant semicolon.

> +		else {
> +			int x;

nr_freed, would be better.

>  
> -			slabp = list_entry(p, struct slab, list);
> -			BUG_ON(slabp->inuse);
> -			list_del(&slabp->list);
> -			STATS_INC_REAPED(searchp);
> -
> -			/*
> -			 * Safe to drop the lock. The slab is no longer linked
> -			 * to the cache. searchp cannot disappear, we hold
> -			 * cache_chain_lock
> -			 */
> -			l3->free_objects -= searchp->num;
> -			spin_unlock_irq(&l3->list_lock);
> -			slab_destroy(searchp, slabp);
> -		} while (--tofree > 0);
> +			x = drain_freelist(searchp, l3, (l3->free_limit +
> +				5 * searchp->num - 1) / (5 * searchp->num));
> +			STATS_ADD_REAPED(searchp, x);

Maybe extract a local variable 'to_free' for readability.

						Pekka

Re: [RFC 1/4] slab freeing consolidation

[Christoph Lameter]

On Thu, 22 Jun 2006, Pekka J Enberg wrote:

> > +static int long drain_freelist(struct kmem_cache *cachep,
> > +		struct kmem_list3 *l3, int tofree)
> 
> I have been trying to slowly kill the 'p' prefix so I'd appreciate if you 
> could just call the parameter 'cache'.  Also, l3 could be 'lists'.

Cache is fine. But l3 needs to stay. l3 is always a pointer to a specific 
and important structure in the slab allcoator.

Fixed up patch:


slab: consolidate code to free slabs from freelist

Code in __shrink_node() duplicates code in cache_reap()

Add a new function drain_freelist that removes slabs with objects
that are already free and use that in various places.

This eliminates the __node_shrink() function and provides
the interrupt holdoff reduction from slab_free to code that
used to call __node_shrink.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.17/mm/slab.c
===================================================================
--- linux-2.6.17.orig/mm/slab.c	2006-06-17 18:49:35.000000000 -0700
+++ linux-2.6.17/mm/slab.c	2006-06-22 12:35:58.685386714 -0700
@@ -452,7 +452,7 @@ struct kmem_cache {
 #define	STATS_DEC_ACTIVE(x)	((x)->num_active--)
 #define	STATS_INC_ALLOCED(x)	((x)->num_allocations++)
 #define	STATS_INC_GROWN(x)	((x)->grown++)
-#define	STATS_INC_REAPED(x)	((x)->reaped++)
+#define	STATS_ADD_REAPED(x,y)	((x)->reaped += (y))
 #define	STATS_SET_HIGH(x)						\
 	do {								\
 		if ((x)->num_active > (x)->high_mark)			\
@@ -476,7 +476,7 @@ struct kmem_cache {
 #define	STATS_DEC_ACTIVE(x)	do { } while (0)
 #define	STATS_INC_ALLOCED(x)	do { } while (0)
 #define	STATS_INC_GROWN(x)	do { } while (0)
-#define	STATS_INC_REAPED(x)	do { } while (0)
+#define	STATS_ADD_REAPED(x,y)	do { } while (0)
 #define	STATS_SET_HIGH(x)	do { } while (0)
 #define	STATS_INC_ERR(x)	do { } while (0)
 #define	STATS_INC_NODEALLOCS(x)	do { } while (0)
@@ -709,7 +709,6 @@ static void free_block(struct kmem_cache
 			int node);
 static void enable_cpucache(struct kmem_cache *cachep);
 static void cache_reap(void *unused);
-static int __node_shrink(struct kmem_cache *cachep, int node);
 
 static inline struct array_cache *cpu_cache_get(struct kmem_cache *cachep)
 {
@@ -1207,10 +1206,7 @@ free_array_cache:
 			l3 = cachep->nodelists[node];
 			if (!l3)
 				continue;
-			spin_lock_irq(&l3->list_lock);
-			/* free slabs belonging to this node */
-			__node_shrink(cachep, node);
-			spin_unlock_irq(&l3->list_lock);
+			drain_freelist(cachep, l3, l3->free_objects);
 		}
 		mutex_unlock(&cache_chain_mutex);
 		break;
@@ -2210,34 +2206,48 @@ static void drain_cpu_caches(struct kmem
 	}
 }
 
-static int __node_shrink(struct kmem_cache *cachep, int node)
+/*
+ * Remove slabs from the list of free slabs.
+ * Specify the number of slabs to drain in tofree.
+ *
+ * Returns the actual number of slabs released.
+ */
+static int long drain_freelist(struct kmem_cache *cache,
+		struct kmem_list3 *l3, int tofree)
 {
+	struct list_head *p;
+	int nr_freed;
 	struct slab *slabp;
-	struct kmem_list3 *l3 = cachep->nodelists[node];
-	int ret;
 
-	for (;;) {
-		struct list_head *p;
+	nr_freed = 0;
+	while (nr_freed < tofree && !list_empty(&l3->slabs_free)) {
 
+		spin_lock_irq(&l3->list_lock);
 		p = l3->slabs_free.prev;
-		if (p == &l3->slabs_free)
-			break;
+		if (p == &l3->slabs_free) {
+			spin_unlock_irq(&l3->list_lock);
+			goto out;
+		}
 
-		slabp = list_entry(l3->slabs_free.prev, struct slab, list);
+		slabp = list_entry(p, struct slab, list);
 #if DEBUG
 		BUG_ON(slabp->inuse);
 #endif
 		list_del(&slabp->list);
-
-		l3->free_objects -= cachep->num;
+		/*
+		 * Safe to drop the lock. The slab is no longer linked
+		 * to the cache.
+		 */
+		l3->free_objects -= cache->num;
 		spin_unlock_irq(&l3->list_lock);
-		slab_destroy(cachep, slabp);
-		spin_lock_irq(&l3->list_lock);
+		slab_destroy(cache, slabp);
+		nr_freed++;
 	}
-	ret = !list_empty(&l3->slabs_full) || !list_empty(&l3->slabs_partial);
-	return ret;
+out:
+	return nr_freed;
 }
 
+
 static int __cache_shrink(struct kmem_cache *cachep)
 {
 	int ret = 0, i = 0;
@@ -2248,11 +2258,10 @@ static int __cache_shrink(struct kmem_ca
 	check_irq_on();
 	for_each_online_node(i) {
 		l3 = cachep->nodelists[i];
-		if (l3) {
-			spin_lock_irq(&l3->list_lock);
-			ret += __node_shrink(cachep, i);
-			spin_unlock_irq(&l3->list_lock);
-		}
+		drain_freelist(cachep, l3, l3->free_objects);
+
+		ret += !list_empty(&l3->slabs_full) ||
+			!list_empty(&l3->slabs_partial);
 	}
 	return (ret ? 1 : 0);
 }
@@ -3693,9 +3702,6 @@ static void cache_reap(void *unused)
 
 	list_for_each(walk, &cache_chain) {
 		struct kmem_cache *searchp;
-		struct list_head *p;
-		int tofree;
-		struct slab *slabp;
 
 		searchp = list_entry(walk, struct kmem_cache, next);
 		check_irq_on();
@@ -3722,41 +3728,15 @@ static void cache_reap(void *unused)
 
 		drain_array(searchp, l3, l3->shared, 0, node);
 
-		if (l3->free_touched) {
+		if (l3->free_touched)
 			l3->free_touched = 0;
-			goto next;
-		}
+		else {
+			int freed;
 
-		tofree = (l3->free_limit + 5 * searchp->num - 1) /
-				(5 * searchp->num);
-		do {
-			/*
-			 * Do not lock if there are no free blocks.
-			 */
-			if (list_empty(&l3->slabs_free))
-				break;
-
-			spin_lock_irq(&l3->list_lock);
-			p = l3->slabs_free.next;
-			if (p == &(l3->slabs_free)) {
-				spin_unlock_irq(&l3->list_lock);
-				break;
-			}
-
-			slabp = list_entry(p, struct slab, list);
-			BUG_ON(slabp->inuse);
-			list_del(&slabp->list);
-			STATS_INC_REAPED(searchp);
-
-			/*
-			 * Safe to drop the lock. The slab is no longer linked
-			 * to the cache. searchp cannot disappear, we hold
-			 * cache_chain_lock
-			 */
-			l3->free_objects -= searchp->num;
-			spin_unlock_irq(&l3->list_lock);
-			slab_destroy(searchp, slabp);
-		} while (--tofree > 0);
+			freed = drain_freelist(searchp, l3, (l3->free_limit +
+				5 * searchp->num - 1) / (5 * searchp->num));
+			STATS_ADD_REAPED(searchp, freed);
+		}
 next:
 		cond_resched();
 	}

[RFC 2/4] Remove empty destructor from drivers/usb/mon/mon_text.c

[Christoph Lameter]

Remove empty destructor from drivers/usb/mon/mon_text.c

Remove destructor and call kmem_cache_create with NULL for the destructor.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.17-rc6-mm2/drivers/usb/mon/mon_text.c
===================================================================
--- linux-2.6.17-rc6-mm2.orig/drivers/usb/mon/mon_text.c	2006-06-05 17:57:02.000000000 -0700
+++ linux-2.6.17-rc6-mm2/drivers/usb/mon/mon_text.c	2006-06-14 15:37:01.574356902 -0700
@@ -61,7 +61,6 @@ struct mon_reader_text {
 };
 
 static void mon_text_ctor(void *, kmem_cache_t *, unsigned long);
-static void mon_text_dtor(void *, kmem_cache_t *, unsigned long);
 
 /*
  * mon_text_submit
@@ -238,7 +237,7 @@ static int mon_text_open(struct inode *i
 	    (long)rp);
 	rp->e_slab = kmem_cache_create(rp->slab_name,
 	    sizeof(struct mon_event_text), sizeof(long), 0,
-	    mon_text_ctor, mon_text_dtor);
+	    mon_text_ctor, NULL);
 	if (rp->e_slab == NULL) {
 		rc = -ENOMEM;
 		goto err_slab;
@@ -429,7 +428,3 @@ static void mon_text_ctor(void *mem, kme
 	memset(mem, 0xe5, sizeof(struct mon_event_text));
 }
 
-static void mon_text_dtor(void *mem, kmem_cache_t *slab, unsigned long sflags)
-{
-	;
-}

Re: [RFC 2/4] Remove empty destructor from drivers/usb/mon/mon_text.c

[Pekka J Enberg]

On Mon, 19 Jun 2006, Christoph Lameter wrote:
> Remove empty destructor from drivers/usb/mon/mon_text.c
> 
> Remove destructor and call kmem_cache_create with NULL for the destructor.
> 
> Signed-off-by: Christoph Lameter <clameter@sgi.com>

Looks good.

Acked-by: Pekka Enberg <penberg@cs.helsinki.fi>

				Pekka

[RFC 3/4] Add checks to current destructor uses

[Christoph Lameter]

slab: Add checks to current destructor uses

We will be adding new destructor options soon. So insure that all
existing destructors only react to SLAB_DTOR_DESTROY.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.17-rc6-mm2/arch/i386/mm/pgtable.c
===================================================================
--- linux-2.6.17-rc6-mm2.orig/arch/i386/mm/pgtable.c	2006-06-16 11:48:44.229756909 -0700
+++ linux-2.6.17-rc6-mm2/arch/i386/mm/pgtable.c	2006-06-19 10:02:05.008801502 -0700
@@ -224,15 +224,19 @@ void pgd_ctor(void *pgd, kmem_cache_t *c
 }
 
 /* never called when PTRS_PER_PMD > 1 */
-void pgd_dtor(void *pgd, kmem_cache_t *cache, unsigned long unused)
+void pgd_dtor(void *pgd, kmem_cache_t *cache, unsigned long slab_flags)
 {
 	unsigned long flags; /* can be called from interrupt context */
 
+	if (!(slab_flags & SLAB_DTOR_DESTROY))
+		return;
+
 	spin_lock_irqsave(&pgd_lock, flags);
 	pgd_list_del(pgd);
 	spin_unlock_irqrestore(&pgd_lock, flags);
 }
 
+
 pgd_t *pgd_alloc(struct mm_struct *mm)
 {
 	int i;
Index: linux-2.6.17-rc6-mm2/include/linux/slab.h
===================================================================
--- linux-2.6.17-rc6-mm2.orig/include/linux/slab.h	2006-06-16 11:48:52.272227349 -0700
+++ linux-2.6.17-rc6-mm2/include/linux/slab.h	2006-06-19 10:00:33.951924377 -0700
@@ -52,6 +52,9 @@ typedef struct kmem_cache kmem_cache_t;
 #define SLAB_CTOR_ATOMIC	0x002UL		/* tell constructor it can't sleep */
 #define	SLAB_CTOR_VERIFY	0x004UL		/* tell constructor it's a verify call */
 
+/* flags passed to a constructor func */
+#define SLAB_DTOR_DESTROY	0x1000UL	/* Called during slab destruction */
+
 #ifndef CONFIG_SLOB
 
 /* prototypes */
Index: linux-2.6.17-rc6-mm2/arch/frv/mm/pgalloc.c
===================================================================
--- linux-2.6.17-rc6-mm2.orig/arch/frv/mm/pgalloc.c	2006-06-05 17:57:02.000000000 -0700
+++ linux-2.6.17-rc6-mm2/arch/frv/mm/pgalloc.c	2006-06-19 10:03:11.301582635 -0700
@@ -120,10 +120,13 @@ void pgd_ctor(void *pgd, kmem_cache_t *c
 }
 
 /* never called when PTRS_PER_PMD > 1 */
-void pgd_dtor(void *pgd, kmem_cache_t *cache, unsigned long unused)
+void pgd_dtor(void *pgd, kmem_cache_t *cache, unsigned long slab_flags)
 {
 	unsigned long flags; /* can be called from interrupt context */
 
+	if (!(slab_flags & SLAB_DTOR_DESTROY))
+		return;
+
 	spin_lock_irqsave(&pgd_lock, flags);
 	pgd_list_del(pgd);
 	spin_unlock_irqrestore(&pgd_lock, flags);

Re: [RFC 3/4] Add checks to current destructor uses

[Pekka J Enberg]

On Mon, 19 Jun 2006, Christoph Lameter wrote:
> slab: Add checks to current destructor uses
> 
> We will be adding new destructor options soon. So insure that all
> existing destructors only react to SLAB_DTOR_DESTROY.

Hmm, I don't see the slab allocator passing SLAB_DTOR_DESTROY anywhere in 
this patch?  Please don't introduce changesets that break the kernel.  
It's bad for stuff like git bisect.

					Pekka

Re: [RFC 3/4] Add checks to current destructor uses

[Christoph Lameter]

On Thu, 22 Jun 2006, Pekka J Enberg wrote:

> On Mon, 19 Jun 2006, Christoph Lameter wrote:
> > slab: Add checks to current destructor uses
> > 
> > We will be adding new destructor options soon. So insure that all
> > existing destructors only react to SLAB_DTOR_DESTROY.
> 
> Hmm, I don't see the slab allocator passing SLAB_DTOR_DESTROY anywhere in 
> this patch?  Please don't introduce changesets that break the kernel.  
> It's bad for stuff like git bisect.

Correct. Thanks.

Fixed up patch:

slab: Add checks to current destructor uses

We will be adding new destructor options soon. So insure that all
existing destructors only react to SLAB_DTOR_DESTROY.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.17/arch/i386/mm/pgtable.c
===================================================================
--- linux-2.6.17.orig/arch/i386/mm/pgtable.c	2006-06-17 18:49:35.000000000 -0700
+++ linux-2.6.17/arch/i386/mm/pgtable.c	2006-06-22 12:38:29.179955802 -0700
@@ -226,15 +226,19 @@ void pgd_ctor(void *pgd, kmem_cache_t *c
 }
 
 /* never called when PTRS_PER_PMD > 1 */
-void pgd_dtor(void *pgd, kmem_cache_t *cache, unsigned long unused)
+void pgd_dtor(void *pgd, kmem_cache_t *cache, unsigned long slab_flags)
 {
 	unsigned long flags; /* can be called from interrupt context */
 
+	if (!(slab_flags & SLAB_DTOR_DESTROY))
+		return;
+
 	spin_lock_irqsave(&pgd_lock, flags);
 	pgd_list_del(pgd);
 	spin_unlock_irqrestore(&pgd_lock, flags);
 }
 
+
 pgd_t *pgd_alloc(struct mm_struct *mm)
 {
 	int i;
Index: linux-2.6.17/include/linux/slab.h
===================================================================
--- linux-2.6.17.orig/include/linux/slab.h	2006-06-17 18:49:35.000000000 -0700
+++ linux-2.6.17/include/linux/slab.h	2006-06-22 12:38:29.180932304 -0700
@@ -53,6 +53,9 @@ typedef struct kmem_cache kmem_cache_t;
 #define SLAB_CTOR_ATOMIC	0x002UL		/* tell constructor it can't sleep */
 #define	SLAB_CTOR_VERIFY	0x004UL		/* tell constructor it's a verify call */
 
+/* flags passed to a constructor func */
+#define SLAB_DTOR_DESTROY	0x1000UL	/* Called during slab destruction */
+
 #ifndef CONFIG_SLOB
 
 /* prototypes */
Index: linux-2.6.17/arch/frv/mm/pgalloc.c
===================================================================
--- linux-2.6.17.orig/arch/frv/mm/pgalloc.c	2006-06-17 18:49:35.000000000 -0700
+++ linux-2.6.17/arch/frv/mm/pgalloc.c	2006-06-22 12:38:29.212180365 -0700
@@ -120,10 +120,13 @@ void pgd_ctor(void *pgd, kmem_cache_t *c
 }
 
 /* never called when PTRS_PER_PMD > 1 */
-void pgd_dtor(void *pgd, kmem_cache_t *cache, unsigned long unused)
+void pgd_dtor(void *pgd, kmem_cache_t *cache, unsigned long slab_flags)
 {
 	unsigned long flags; /* can be called from interrupt context */
 
+	if (!(slab_flags & SLAB_DTOR_DESTROY))
+		return;
+
 	spin_lock_irqsave(&pgd_lock, flags);
 	pgd_list_del(pgd);
 	spin_unlock_irqrestore(&pgd_lock, flags);
Index: linux-2.6.17/mm/slab.c
===================================================================
--- linux-2.6.17.orig/mm/slab.c	2006-06-22 12:35:58.685386714 -0700
+++ linux-2.6.17/mm/slab.c	2006-06-22 12:39:37.971586394 -0700
@@ -1689,7 +1689,8 @@ static void slab_destroy_objs(struct kme
 					   "was overwritten");
 		}
 		if (cachep->dtor && !(cachep->flags & SLAB_POISON))
-			(cachep->dtor) (objp + obj_offset(cachep), cachep, 0);
+			(cachep->dtor) (objp + obj_offset(cachep), cachep,
+				SLAB_DTOR_DESTROY);
 	}
 }
 #else
@@ -1699,7 +1700,7 @@ static void slab_destroy_objs(struct kme
 		int i;
 		for (i = 0; i < cachep->num; i++) {
 			void *objp = index_to_obj(cachep, slabp, i);
-			(cachep->dtor) (objp, cachep, 0);
+			(cachep->dtor) (objp, cachep, SLAB_DTOR_DESTROY);
 		}
 	}
 }
@@ -2661,7 +2662,8 @@ static void *cache_free_debugcheck(struc
 		/* we want to cache poison the object,
 		 * call the destruction callback
 		 */
-		cachep->dtor(objp + obj_offset(cachep), cachep, 0);
+		cachep->dtor(objp + obj_offset(cachep), cachep,
+			SLAB_DTOR_DESTROY);
 	}
 #ifdef CONFIG_DEBUG_SLAB_LEAK
 	slab_bufctl(slabp)[objnr] = BUFCTL_FREE;

[PATCH 4/4] Slab Reclaim logic

[Christoph Lameter]

Add kmem_cache_reclaim() function.

This patch adds the new slab reclaim functionalty. For that purpose we add a
new function:

long kmem_cache_reclaim(struct kmem_cache *cache, unsigned long nr_pages)

kmem_cache_reclaim attempts to reclaim nr_pages from the indicated cache.
It returns either the number of reclaimed pages or an error code.

If kmem_cache_reclaim is called on a cache without a destructor and without
the SLAB_RECLAIM flag set then kmem_cache_reclaim simply shrinks the caches
and freelists.

If SLAB_RECLAIM is set then it is assumed that the objects of the slab
have a refcnt as the first element in the object. That refcnt is then used
to guide a slab oriented form of reclaim. It is assummed that a refcount
of zero is designating a free item. A refcount of 1 is an object that
is currently unused.

Reclaim then processes all fully used and partially used slabs looking for
pages that only contain elements with refcount = 1. These are freed by
calling the destructor with the option SLAB_DTOR_FREE. The destructor
must make its best attempt to free the object using kmem_cache_free().

If slabs also contain objects with a higher refcount then a couple of
elements with refcount one will be removed. This done so that new
objects (with potentially higher refcount) can be added again to the
slab. That way slabs develop that are full of long term objects with
higher refcount.

Signed-off-by: Christoph Lameter <clameter@sgi.com>

Index: linux-2.6.17-rc6-mm2/include/linux/slab.h
===================================================================
--- linux-2.6.17-rc6-mm2.orig/include/linux/slab.h	2006-06-19 10:00:33.951924377 -0700
+++ linux-2.6.17-rc6-mm2/include/linux/slab.h	2006-06-19 10:17:49.941653443 -0700
@@ -37,6 +37,7 @@ typedef struct kmem_cache kmem_cache_t;
 #define	SLAB_DEBUG_INITIAL	0x00000200UL	/* Call constructor (as verifier) */
 #define	SLAB_RED_ZONE		0x00000400UL	/* Red zone objs in a cache */
 #define	SLAB_POISON		0x00000800UL	/* Poison objects */
+#define	SLAB_RECLAIM		0x00001000UL	/* Reclaim via destructor calls */
 #define	SLAB_HWCACHE_ALIGN	0x00002000UL	/* align objs on a h/w cache lines */
 #define SLAB_CACHE_DMA		0x00004000UL	/* use GFP_DMA memory */
 #define SLAB_MUST_HWCACHE_ALIGN	0x00008000UL	/* force alignment */
@@ -54,6 +55,7 @@ typedef struct kmem_cache kmem_cache_t;
 
 /* flags passed to a constructor func */
 #define SLAB_DTOR_DESTROY	0x1000UL	/* Called during slab destruction */
+#define SLAB_DTOR_FREE		0x2000UL	/* Called during reclaim */
 
 #ifndef CONFIG_SLOB
 
@@ -225,6 +227,7 @@ extern kmem_cache_t	*bio_cachep;
 
 extern atomic_t slab_reclaim_pages;
 
+extern long kmem_cache_reclaim(struct kmem_cache *, gfp_t flags, unsigned long);
 #endif	/* __KERNEL__ */
 
 #endif	/* _LINUX_SLAB_H */
Index: linux-2.6.17-rc6-mm2/Documentation/slab_reclaim
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6.17-rc6-mm2/Documentation/slab_reclaim	2006-06-19 11:17:19.303895253 -0700
@@ -0,0 +1,57 @@
+Slab Reclaim
+-----------
+
+A slab may use slab reclaim if
+
+1. An atomic_t refcounter is the first element of the objects.
+
+2. SLAB_RECLAIM was set when calling kmem_cache_create()
+
+3. A destructor function is provided that frees the object
+   (after some final checks that this is possible and removing
+   all links) by calling kmem_cache_free() on it.
+
+Slab reclaim establishes the state of an object through
+the refcount. It distinguises the following states:
+
+1. refcount = 0
+
+	In that case the object was freed
+	and may have been initialized with
+	a constructor. The object is on the free lists
+	of the allocator or marked free in the slab pages.
+
+2. refcount = 1
+
+	The objects is currently not used but set up with information
+	that may be useful in the future.
+	The entry could be disposed of if memory pressure builds up.
+
+3. refcount > 1
+
+	The object is in active use and cannot be
+	reclaimed.
+
+If slab reclaim attempt to reclaim an object then the destructor
+will be called with SLAB_DTOR_FREE set.
+
+A simple definition of a destructor:
+
+void dtor(kmem_cache_t *cachep, void *p, unsigned long flags)
+{
+	struct object *o = p;
+
+	if (!(flags & SLAB_DTOR_FREE))
+		/* Another type of destructor invocation */
+		return;
+
+	if (!atomic_dec_and_test(&o->refcount))
+		/* Already freed */
+		return;
+
+	remove_references(o);
+	free_attached_structures(o);
+	kmem_cache_free(cachep, o);
+}
+
+
Index: linux-2.6.17-rc6-mm2/mm/slab.c
===================================================================
--- linux-2.6.17-rc6-mm2.orig/mm/slab.c	2006-06-17 14:28:47.626589639 -0700
+++ linux-2.6.17-rc6-mm2/mm/slab.c	2006-06-19 11:23:43.960746537 -0700
@@ -173,12 +173,12 @@
 #if DEBUG
 # define CREATE_MASK	(SLAB_DEBUG_INITIAL | SLAB_RED_ZONE | \
 			 SLAB_POISON | SLAB_HWCACHE_ALIGN | \
-			 SLAB_CACHE_DMA | \
+			 SLAB_CACHE_DMA | SLAB_RECLAIM \
 			 SLAB_MUST_HWCACHE_ALIGN | SLAB_STORE_USER | \
 			 SLAB_RECLAIM_ACCOUNT | SLAB_PANIC | \
 			 SLAB_DESTROY_BY_RCU | SLAB_MEM_SPREAD)
 #else
-# define CREATE_MASK	(SLAB_HWCACHE_ALIGN | \
+# define CREATE_MASK	(SLAB_HWCACHE_ALIGN | SLAB_RECLAIM \
 			 SLAB_CACHE_DMA | SLAB_MUST_HWCACHE_ALIGN | \
 			 SLAB_RECLAIM_ACCOUNT | SLAB_PANIC | \
 			 SLAB_DESTROY_BY_RCU | SLAB_MEM_SPREAD)
@@ -221,8 +221,9 @@ struct slab {
 	unsigned long colouroff;
 	void *s_mem;		/* including colour offset */
 	unsigned int inuse;	/* num of objs active in slab */
-	kmem_bufctl_t free;
 	unsigned short nodeid;
+	unsigned short marker;
+	kmem_bufctl_t free;
 };
 
 /*
@@ -298,6 +299,7 @@ struct kmem_list3 {
 	struct array_cache **alien;	/* on other nodes */
 	unsigned long next_reap;	/* updated without locking */
 	int free_touched;		/* updated without locking */
+	atomic_t reclaim;			/* Reclaim in progress */
 };
 
 /*
@@ -396,7 +398,6 @@ struct kmem_cache {
 	unsigned int colour_off;	/* colour offset */
 	struct kmem_cache *slabp_cache;
 	unsigned int slab_size;
-	unsigned int dflags;		/* dynamic flags */
 
 	/* constructor func */
 	void (*ctor) (void *, struct kmem_cache *, unsigned long);
@@ -3103,7 +3104,12 @@ static void free_block(struct kmem_cache
 
 		/* fixup slab chains */
 		if (slabp->inuse == 0) {
-			if (l3->free_objects > l3->free_limit) {
+			/*
+			 * Destroy the object if we have too many of them
+			 * We cannot destroy during reclaim
+			 */
+			if (l3->free_objects > l3->free_limit &&
+					!atomic_read(&l3->reclaim)) {
 				l3->free_objects -= cachep->num;
 				/*
 				 * It is safe to drop the lock. The slab is
@@ -3792,7 +3798,7 @@ static void cache_reap(void *unused)
 
 		if (l3->free_touched)
 			l3->free_touched = 0;
-		else {
+		else if (!atomic_read(&l3->reclaim)) {
 			int x;
 
 			x = drain_freelist(searchp, l3, (l3->free_limit +
@@ -4242,3 +4248,183 @@ void kmem_set_shrinker(kmem_cache_t *cac
 	cachep->shrinker = shrinker;
 }
 EXPORT_SYMBOL(kmem_set_shrinker);
+
+/*
+ * Reclaim logic based on the per node slab lists.
+ */
+
+/*
+ * Reclaim from a single slab object.
+ */
+static int try_reclaim_one(kmem_cache_t *cachep, struct kmem_list3 *l3,
+	struct list_head *list, unsigned short marker)
+{
+	int max_refcnt;
+	int min_free;
+	struct slab *slabp;
+	struct list_head *p;
+	int i;
+
+	/* Retrieve the last slab under lock and then make the last slab
+	 * the first one so that the next call to try_to_reclaim one
+	 * will cycle through all slab objects.
+	 *
+	 * Note that no slabs will be destroyed and freed via the page
+	 * allocator since we have incremented reclaim. So we are guaranteed that
+	 * the slab will not vanish from under us even after we dropped the
+	 * list_lock.
+	 */
+	spin_lock_irq(&l3->list_lock);
+	p = list->prev;
+	if (unlikely(p == list)) {
+		/* Empty list */
+		spin_unlock_irq(&l3->list_lock);
+		return -1;
+	}
+
+	slabp = list_entry(p, struct slab, list);
+	if (unlikely(slabp->marker == marker)) {
+		/* We already did this one. Pass complete */
+		spin_unlock_irq(&l3->list_lock);
+		return -1;
+	}
+	list_move(p, list);
+	spin_unlock_irq(&l3->list_lock);
+
+	min_free = 0;
+	if (slabp->inuse == cachep->num) {
+		/*
+		 * Full slab object. Free some to bring together
+		 * objects with higher refcounts
+		 */
+		if (cachep->num > 16)
+			/* 1/16th of objects for large slabs */
+			min_free = cachep->num / 16;
+		else if (cachep->num > 3)
+			/* For a smaller object count free at least one */
+			min_free = 1;
+	}
+
+	/*
+	 * First pass over the slab: We free the first min_free objects
+	 * with refcnt one and establish the higest refcnt in the block.
+	 *
+	 * Clearing one or a few refcnt one (=unused) items means that
+	 * slabs will gradually fill up with objects with higher refcnts.
+	 * This means we will create a higher object density.
+	 */
+	max_refcnt = 0;
+	for (i = 0; i < cachep->num; i++) {
+		atomic_t *objp = index_to_obj(cachep, slabp, i);
+		int refcnt = atomic_read(objp);
+
+		if (refcnt == 1 && min_free > 0) {
+			min_free--;
+			cachep->dtor(objp, cachep, SLAB_DTOR_FREE);
+		}
+		max_refcnt = max(max_refcnt, refcnt);
+	}
+
+
+	if (max_refcnt > 1)
+		/* Cannot free the block */
+		return 0;
+
+	/*
+	 * The slab only contains objects with refcnt 1 (=unused)
+	 * this means that we can free the slab object completely
+	 * if we free all the objects.
+	 */
+	for (i = 0; i < cachep->num; i++) {
+		atomic_t *objp = index_to_obj(cachep, slabp, i);
+		int refcnt = atomic_read(objp);
+
+		if (refcnt == 1)
+			cachep->dtor(objp, cachep, SLAB_DTOR_FREE);
+	}
+	return 1;
+}
+
+/*
+ * Scan over a list of slabs and attempt to reclaim each.
+ */
+static int reclaim_scan(kmem_cache_t *cachep, struct kmem_list3 *l3,
+	int slabs_to_free, struct list_head *list, unsigned short marker)
+{
+	int nr_freed = 0;
+
+	while (nr_freed < slabs_to_free) {
+		int x;
+
+		x = try_reclaim_one(cachep, l3, list, marker);
+		if (x > 0)
+			nr_freed += x;
+		else
+			break;
+	}
+	return nr_freed;
+}
+
+/*
+ * Free pages from this nodes pages from the indicated slab. The thread
+ * calling this function must be pinned to this node.
+ */
+long kmem_cache_reclaim(kmem_cache_t *cachep, gfp_t flags, unsigned long pages)
+{
+	struct kmem_list3 *l3 = cachep->nodelists[numa_node_id()];
+	int nr_freed;
+	unsigned short marker = jiffies;	/* Just some unique bit pattern */
+	int slabs_to_free = (pages + ((1 << cachep->gfporder) -1)) >>
+							cachep->gfporder;
+
+	/*
+	 * Push cached objects into the lists. That way more pages may
+	 * be freeable.
+	 */
+	drain_cpu_caches(cachep);
+
+	/* First we reclaim from the freelists */
+	nr_freed = drain_freelist(cachep, l3, slabs_to_free);
+
+	/*
+	 * We can only do more in depth reclaim if we have
+	 * a destructor and the flags indicate that the refcnt
+	 * is the first element in the object.
+	 */
+	if (nr_freed >= slabs_to_free || !cachep->dtor ||
+		!(cachep->flags & SLAB_RECLAIM))
+		goto done;
+
+	/*
+	 * An increased reclaim count stops the freeing of slabs to the
+	 * page allocator. This allows us to inspect slabs without holding
+	 * the list lock.
+	 */
+	if (atomic_read(&l3->reclaim) > 1)
+		goto dec;
+
+	/* Try to free items from the full lists */
+	nr_freed += reclaim_scan(cachep, l3, slabs_to_free - nr_freed,
+					 &l3->slabs_full, marker);
+
+	if (nr_freed >= slabs_to_free)
+		goto dec;
+
+	/* Try to free items from the partial lists */
+	nr_freed += reclaim_scan(cachep, l3, slabs_to_free - nr_freed,
+					&l3->slabs_partial, marker);
+
+	/*
+	 * At this point we have freed all freeable slabs of the cache
+	 * and we have freed a mininum number of objects free for each slab
+	 */
+
+dec:
+	atomic_dec(&l3->reclaim);
+	/* Drop the large free lists that we may have build while scanning */
+	drain_freelist(cachep, l3, slabs_to_free);
+done:
+	return nr_freed << cachep->gfporder;
+
+}
+

Re: [PATCH 4/4] Slab Reclaim logic

[Christoph Lameter]

This should have been RFC 4/4. Sigh.

Re: [PATCH 4/4] Slab Reclaim logic

[Pekka J Enberg]

On Mon, 19 Jun 2006, Christoph Lameter wrote:
> @@ -221,8 +221,9 @@ struct slab {
>  	unsigned long colouroff;
>  	void *s_mem;		/* including colour offset */
>  	unsigned int inuse;	/* num of objs active in slab */
> -	kmem_bufctl_t free;
>  	unsigned short nodeid;
> +	unsigned short marker;
> +	kmem_bufctl_t free;

[snip]

> @@ -298,6 +299,7 @@ struct kmem_list3 {
>  	struct array_cache **alien;	/* on other nodes */
>  	unsigned long next_reap;	/* updated without locking */
>  	int free_touched;		/* updated without locking */
> +	atomic_t reclaim;			/* Reclaim in progress */
>  };

Hmm, we don't need 'marker' and 'reclaim' if SLAB_RECLAIM is not set, 
right?  I don't think we want to bloat struct slab and struct kmem_list3 
for everyone.  What's marker used for?  Why can't we just take the list 
lock instead of 'reclaim'?

				Pekka

Re: [PATCH 4/4] Slab Reclaim logic

[Christoph Lameter]

On Thu, 22 Jun 2006, Pekka J Enberg wrote:

> > @@ -298,6 +299,7 @@ struct kmem_list3 {
> >  	struct array_cache **alien;	/* on other nodes */
> >  	unsigned long next_reap;	/* updated without locking */
> >  	int free_touched;		/* updated without locking */
> > +	atomic_t reclaim;			/* Reclaim in progress */
> >  };
> 
> Hmm, we don't need 'marker' and 'reclaim' if SLAB_RECLAIM is not set, 
> right?  I don't think we want to bloat struct slab and struct kmem_list3 
> for everyone.  What's marker used for?  Why can't we just take the list 
> lock instead of 'reclaim'?

Yes we do not need those if SLAB_RECLAIM is not set.

We only take the list lock for getting at slab addresses. We want slab 
operations to continue wile reclaim is in progress.

The marker does not cost anything on ia64 due to structure alignment. We 
need to have some way (in the absense of taking the list lock) to know 
when we have reclaimed all slabs.

Re: [PATCH 4/4] Slab Reclaim logic

[Pekka J Enberg]

On Thu, 22 Jun 2006, Pekka J Enberg wrote:
> > > @@ -298,6 +299,7 @@ struct kmem_list3 {
> > >  	struct array_cache **alien;	/* on other nodes */
> > >  	unsigned long next_reap;	/* updated without locking */
> > >  	int free_touched;		/* updated without locking */
> > > +	atomic_t reclaim;			/* Reclaim in progress */
> > >  };

On Thu, 22 Jun 2006, Christoph Lameter wrote:
> Yes we do not need those if SLAB_RECLAIM is not set.
> 
> We only take the list lock for getting at slab addresses. We want slab 
> operations to continue wile reclaim is in progress.
> 
> The marker does not cost anything on ia64 due to structure alignment. We 
> need to have some way (in the absense of taking the list lock) to know 
> when we have reclaimed all slabs.

Not everyone is IA-64.  The slab allocator is already pretty memory 
hungry so lets try not to make it any worse, ok?

					Pekka

Re: [PATCH 4/4] Slab Reclaim logic

[Christoph Lameter]

On Thu, 22 Jun 2006, Pekka J Enberg wrote:

> Not everyone is IA-64.  The slab allocator is already pretty memory 
> hungry so lets try not to make it any worse, ok?

We have a huge memory problem with reclain. This is only a small 
sacrifice. Moreover even on 32 bit platforms this will not be significant 
for most caches that are cache aligned.

Re: [PATCH 4/4] Slab Reclaim logic

[Pekka J Enberg]

On Mon, 19 Jun 2006, Christoph Lameter wrote:
> Add kmem_cache_reclaim() function.
> 
> This patch adds the new slab reclaim functionalty. For that purpose we add a
> new function:
> 
> long kmem_cache_reclaim(struct kmem_cache *cache, unsigned long nr_pages)

Some coding style comments below.

> +extern long kmem_cache_reclaim(struct kmem_cache *, gfp_t flags, unsigned long);

The parameter name is redundant.

> +static int try_reclaim_one(kmem_cache_t *cachep, struct kmem_list3 *l3,
> +	struct list_head *list, unsigned short marker)

Please use struct kmem_cache instead of the typedef.  Better name for l3 
would be nice.

> +static int reclaim_scan(kmem_cache_t *cachep, struct kmem_list3 *l3,
> +	int slabs_to_free, struct list_head *list, unsigned short marker)

Ditto.

> +{
> +	int nr_freed = 0;

s/nr_freed/ret/

> +
> +	while (nr_freed < slabs_to_free) {
> +		int x;

s/x/nr_freed/

> +
> +		x = try_reclaim_one(cachep, l3, list, marker);
> +		if (x > 0)
> +			nr_freed += x;
> +		else
> +			break;
> +	}
> +	return nr_freed;
> +}

> +long kmem_cache_reclaim(kmem_cache_t *cachep, gfp_t flags, unsigned long pages)
> +{

Typedef.

Re: [PATCH 4/4] Slab Reclaim logic

[Christoph Lameter]

On Thu, 22 Jun 2006, Pekka J Enberg wrote:

> Some coding style comments below.
> 
> > +extern long kmem_cache_reclaim(struct kmem_cache *, gfp_t flags, unsigned long);
> 
> The parameter name is redundant.

Ok.
> 
> > +static int try_reclaim_one(kmem_cache_t *cachep, struct kmem_list3 *l3,
> > +	struct list_head *list, unsigned short marker)
> 
> Please use struct kmem_cache instead of the typedef.  Better name for l3 
> would be nice.

l3 is a very good name.

> > +{
> > +	int nr_freed = 0;
> 
> s/nr_freed/ret/

ret is non descriptive. nr_freed is describing what the purpose of the 
variable is.

> > +	while (nr_freed < slabs_to_free) {
> > +		int x;
> 
> s/x/nr_freed/

Would shadow variable.

Re: [PATCH 4/4] Slab Reclaim logic

[Pekka J Enberg]

On Thu, 22 Jun 2006, Christoph Lameter wrote:
> > s/nr_freed/ret/
> 
> ret is non descriptive. nr_freed is describing what the purpose of the 
> variable is.
> 
> > > +	while (nr_freed < slabs_to_free) {
> > > +		int x;
> > 
> > s/x/nr_freed/
> 
> Would shadow variable.

Which is why I suggested using ret for the return variable.  Not a biggie, 
though, obviously.

				Pekka

Re: [PATCH 4/4] Slab Reclaim logic

[Pekka J Enberg]

On Thu, 22 Jun 2006, Christoph Lameter wrote:
> > Please use struct kmem_cache instead of the typedef.  Better name for l3 
> > would be nice.
> 
> l3 is a very good name.

No, it's a terrible name :-). But I guess it's ok for this patch.

				Pekka

Re: [PATCH 4/4] Slab Reclaim logic

[Christoph Lameter]

On Thu, 22 Jun 2006, Pekka J Enberg wrote:

> On Thu, 22 Jun 2006, Christoph Lameter wrote:
> > > Please use struct kmem_cache instead of the typedef.  Better name for l3 
> > > would be nice.
> > 
> > l3 is a very good name.
> 
> No, it's a terrible name :-). But I guess it's ok for this patch.

Its a good name and you better come up with a another reason than 
"terrible name" before you change the established variable name in the 
slab allocator. Otherwise lots of us will have trouble reading the code.

Please make sure that all references to kmem_list3 are called consistently 
l3 thoughout the slab allocator.

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Andi Kleen]

On Monday 19 June 2006 20:46, Christoph Lameter wrote:
> We currently have a set of problem with slab reclaim:

[...] Very cool. We discussed something like that forever but
it's great that finally someone implements it.

-Andi

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Andrew Morton]

Christoph Lameter <clameter@sgi.com> wrote:
>
> We currently have a set of problem with slab reclaim:
> 
> 1. On a NUMA system there are excessive cross node accesses.
>    Locks are taken remotely which leads to a significant slowdown
>    if concurrent reclaim is performeed on the dcache/icache from
>    a number of nodes.
> 
> 2. We need to free an excessive number of elements from the LRU
>    in order to reclaim enough pages from the slab.
> 
> 3. After reclaim we have a large number of sparsely used slab
>    objects.
> 
> The fundamental problem in the current reclaim approaches with the
> icache/dcache is that the reclaim is LRU and object based. Multiple
> objects can share the same slab. So removing one object from a slab
> just removes some cache information that may have been useful later
> but may not give us what we want: More free pages.
> 
> I propose that we replace the LRU based object management by using
> the slab oriented lists in the slab allocator itself for reclaim.
> 
> The slab allocator already has references to all pages used by the
> dcache and icache. It has awareness of which objects are located
> in a certain slab and therefore would be able to free specific
> objects that would make pages freeable if the slab knew
> their state.
> 
> In order to allow the slab allocator to know about an objects
> state we add another flag SLAB_RECLAIM. SLAB_RECLAIM means that
> the following is true of a slab:
> 
> 1. The object contains a reference counter of atomic_t as the
>    first element that follows the following conventions:
> 
>    Counter = 0	-> Object is being freed or is free.
>    Counter = 1  -> Object is not used and contains cache information.
>    		   The object may be freed.
> 
>    Counter > 1	-> Object is in use and cannot be freed.
> 
> 2. A destructor was provided during kmem_cache_create().
>    If SLAB_DTOR_FREE is passed in the flags of the destructor
>    then a best effort attempt will be made to free that object.
> 

It would be better to make the higher-level code register callbacks for
this sort of thing.  That code knows how to determine if an object is
freeable, can manage aging info, etc.

> Memory can then be reclaimed from a slab by calling
> 
> kmem_cache_reclaim(kmem_cache_t *cachep, unsigned long page)
> 
> kmem_cache_reclaim returns an error code or the number of pages reclaimed.
> 
> 
> The reclaim works by walking through the lists of full and partially
> allocated slabs. We begin at the end of thet fully allocated slabs because
> these slabs have been around for a long time (This basically preserves the LRU
> lists to some extend).
> 
> For slab we check all the objects in the slab. If all object have
> a refcount of one then we free all the objects and return the pages of the
> object to the page allocator.

That seems like quite a drawback.  A single refcount=2 object on the page
means that nothing gets freed from that page at all.  It'd be easy
(especially with dcache) to do tons of work without achieving anything.

So it might be better to drop the freeable objects from the page even if
the page has non-freeable objects.  If only because this might make
directory dentries on _other_ pages reclaimable.

But that won't really help much, because the basic problem remains
unsolved: internal fragmentation.

The proposed approach doesn't really solve internal fragmentation.  To do
that we'd need to either:

a) compact dentries by copying them around or, perhaps,

b) make dentry reclaim be guided by the dcache tree: do a bottom-up
   reclaim, or a top-down reclaim when we hit a directory, etc.  Something
   which understands the graph rather than the plain global LRU.



I expect this patchset's approach will help, but I also expect there will
be pathological dcache internal fragmentation patterns (whch can occur
fairly easily) in which it won't help much at all.

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Christoph Lameter]

On Wed, 28 Jun 2006, Andrew Morton wrote:

> > 2. A destructor was provided during kmem_cache_create().
> >    If SLAB_DTOR_FREE is passed in the flags of the destructor
> >    then a best effort attempt will be made to free that object.
> > 
> 
> It would be better to make the higher-level code register callbacks for
> this sort of thing.  That code knows how to determine if an object is
> freeable, can manage aging info, etc.

The destructor is such a callback.

> > For slab we check all the objects in the slab. If all object have
> > a refcount of one then we free all the objects and return the pages of the
> > object to the page allocator.
> 
> That seems like quite a drawback.  A single refcount=2 object on the page
> means that nothing gets freed from that page at all.  It'd be easy
> (especially with dcache) to do tons of work without achieving anything.

We will always reclaim a few object from each page. See the patch.

Single refcount=2 objects could also be detected and we could try to free 
them.

> a) compact dentries by copying them around or, perhaps,

Since we free some dentries in each block they will be effectively be 
moved because they get reallocated in a current slab block.

> b) make dentry reclaim be guided by the dcache tree: do a bottom-up
>    reclaim, or a top-down reclaim when we hit a directory, etc.  Something
>    which understands the graph rather than the plain global LRU.

The callback can make that determination and could trigger these events.
The callback notifies the higher layers that it would be advantageous to 
free this element. The higher layers can then analyze the situation and 
either free or give up.

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Andrew Morton]

On Wed, 28 Jun 2006 17:47:17 -0700 (PDT)
Christoph Lameter <clameter@sgi.com> wrote:

> On Wed, 28 Jun 2006, Andrew Morton wrote:
> 
> > > 2. A destructor was provided during kmem_cache_create().
> > >    If SLAB_DTOR_FREE is passed in the flags of the destructor
> > >    then a best effort attempt will be made to free that object.
> > > 
> > 
> > It would be better to make the higher-level code register callbacks for
> > this sort of thing.  That code knows how to determine if an object is
> > freeable, can manage aging info, etc.
> 
> The destructor is such a callback.

I was, of course, referring to the unpleasant requirement that the object
layout start with an atomic_t.


> > > For slab we check all the objects in the slab. If all object have
> > > a refcount of one then we free all the objects and return the pages of the
> > > object to the page allocator.
> > 
> > That seems like quite a drawback.  A single refcount=2 object on the page
> > means that nothing gets freed from that page at all.  It'd be easy
> > (especially with dcache) to do tons of work without achieving anything.
> 
> We will always reclaim a few object from each page. See the patch.

I read the description.

> Single refcount=2 objects could also be detected and we could try to free 
> them.
> 
> > a) compact dentries by copying them around or, perhaps,
> 
> Since we free some dentries in each block they will be effectively be 
> moved because they get reallocated in a current slab block.

By performing a disk read.  That is not compaction - it is eviction.

> > b) make dentry reclaim be guided by the dcache tree: do a bottom-up
> >    reclaim, or a top-down reclaim when we hit a directory, etc.  Something
> >    which understands the graph rather than the plain global LRU.
> 
> The callback can make that determination and could trigger these events.
> The callback notifies the higher layers that it would be advantageous to 
> free this element. The higher layers can then analyze the situation and 
> either free or give up.

How do you propose handling the locking?  dcache is passed a bare pointer
and no locks are held, but it is guaranteed that the object won't be freed
while it's playing with it?

If so, take dcache_lock and then validate the object's current state in
some manner?

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Christoph Lameter]

On Wed, 28 Jun 2006, Andrew Morton wrote:

> > > It would be better to make the higher-level code register callbacks for
> > > this sort of thing.  That code knows how to determine if an object is
> > > freeable, can manage aging info, etc.
> > 
> > The destructor is such a callback.
> 
> I was, of course, referring to the unpleasant requirement that the object
> layout start with an atomic_t.

Is that such a problem? It reduces the amount of indirect function calls 
needed.

> > Since we free some dentries in each block they will be effectively be 
> > moved because they get reallocated in a current slab block.
> 
> By performing a disk read.  That is not compaction - it is eviction.

Right. If we could directly migrate objects then it would be faster. Think 
about this as swap migration. Later we can get more sophisticated.

> > The callback can make that determination and could trigger these events.
> > The callback notifies the higher layers that it would be advantageous to 
> > free this element. The higher layers can then analyze the situation and 
> > either free or give up.
> 
> How do you propose handling the locking?  dcache is passed a bare pointer
> and no locks are held, but it is guaranteed that the object won't be freed
> while it's playing with it?

The reference counter can be used to insure that the object is not freed.

> If so, take dcache_lock and then validate the object's current state in
> some manner?

Right. I am not clear on how exactly to do that. These actions would need 
to be particular to an object type. I just dealt with the slab 
side of things and I think this is the bare minimum to get us started 
along this road.

Got an enhanced version of it here but this is all not ready for prime 
time and needs some more thought. Maybe we can talk about it in Ottawa.

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Marcelo Tosatti]

On Thu, Jun 29, 2006 at 10:20:52AM -0700, Christoph Lameter wrote:
> On Wed, 28 Jun 2006, Andrew Morton wrote:
> 
> > > > It would be better to make the higher-level code register callbacks for
> > > > this sort of thing.  That code knows how to determine if an object is
> > > > freeable, can manage aging info, etc.
> > > 
> > > The destructor is such a callback.
> > 
> > I was, of course, referring to the unpleasant requirement that the object
> > layout start with an atomic_t.
> 
> Is that such a problem? It reduces the amount of indirect function calls 
> needed.

Need to benchmark I guess.

In the worst case, you can define a per-slab cache freeing function
which inlines the callbacks.

I agree with Andrew, an atomic counter to indicate usage of the objects
is too simplistic (other than being unpleasant).

> > > Since we free some dentries in each block they will be effectively be 
> > > moved because they get reallocated in a current slab block.
> > 
> > By performing a disk read.  That is not compaction - it is eviction.
> 
> Right. If we could directly migrate objects then it would be faster. Think 
> about this as swap migration. Later we can get more sophisticated.
> 
> > > The callback can make that determination and could trigger these events.
> > > The callback notifies the higher layers that it would be advantageous to 
> > > free this element. The higher layers can then analyze the situation and 
> > > either free or give up.
> > 
> > How do you propose handling the locking?  dcache is passed a bare pointer
> > and no locks are held, but it is guaranteed that the object won't be freed
> > while it's playing with it?
> 
> The reference counter can be used to insure that the object is not freed.

Locking is pretty tricky...

> > If so, take dcache_lock and then validate the object's current state in
> > some manner?
> 
> Right. I am not clear on how exactly to do that. These actions would need 
> to be particular to an object type. I just dealt with the slab 
> side of things and I think this is the bare minimum to get us started 
> along this road.
> 
> Got an enhanced version of it here but this is all not ready for prime 
> time and needs some more thought. Maybe we can talk about it in Ottawa.

Guys, I've tried something similar in the past

http://marc2.theaimsgroup.com/?l=linux-mm&m=112996161416875&w=2

What it does is to create a small set callbacks to invoke higher-level
code:

+struct slab_reclaim_ops {
+	int (*objp_is_freeable)(void *objp);
+	int (*objp_release)(void *objp);
+	int (*objp_lock)(void *objp);
+	int (*objp_unlock)(void *objp);
+};

Which are used by generic SLAB code to check for, and release, fully
freeable pages (you've seen it before, from last year). It contains a
dcache implementation.

You really need cache specific information, such as the tree nature of
dentry references.

Christoph, I'm afraid that not using the LRU information can be harmful
to certain workloads... 

But yeah, the current SLAB reclaim scheme is very dumb, lots of room for
improvement.

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Christoph Lameter]

On Sun, 2 Jul 2006, Marcelo Tosatti wrote:

> > > I was, of course, referring to the unpleasant requirement that the object
> > > layout start with an atomic_t.
> > 
> > Is that such a problem? It reduces the amount of indirect function calls 
> > needed.
> 
> Need to benchmark I guess.

I think is pretty obvious. With atomic refcounters you can simply scan
a slab for unused objects without any callbacks. Needing a callback for 
every single object is a waste of resources and will limit reclaim 
efficiency. You would have to do 120 callbacks on some slabs just to 
figure out that it is worth trying to free objects in that 
particular slab block.
 
> I agree with Andrew, an atomic counter to indicate usage of the objects
> is too simplistic (other than being unpleasant).

Cannot see a valid reason so far to draw that conclusion. With the right 
convention the atomic refcounter can be used as an indicator that the 
object is being freed (refcnt = 0), not in use (refcnt = 1) or in active 
use (refcnt=2). The easy and efficient access to this kind of knowledge 
about an object is essential for reclaim.

> > > How do you propose handling the locking?  dcache is passed a bare pointer
> > > and no locks are held, but it is guaranteed that the object won't be freed
> > > while it's playing with it?
> > 
> > The reference counter can be used to insure that the object is not freed.
> 
> Locking is pretty tricky...

Not at all. You do an atomic_inc_if_not_zero from the destructor and then 
either will hold the object to good or you were unable to increment the 
refcount and therefore you can give up and return because the object 
is already being freed.

The tricky locking part comes later when the destructor has to establish 
the locks to get all links to the object released.

> What it does is to create a small set callbacks to invoke higher-level
> code:
> 
> +struct slab_reclaim_ops {
> +	int (*objp_is_freeable)(void *objp);
> +	int (*objp_release)(void *objp);
> +	int (*objp_lock)(void *objp);
> +	int (*objp_unlock)(void *objp);
> +};
> 
> Which are used by generic SLAB code to check for, and release, fully
> freeable pages (you've seen it before, from last year). It contains a
> dcache implementation.

Ok. I will have a look at that. But these callbacks are too heavy for my 
taste. A refcounter could avoid all of that.

> You really need cache specific information, such as the tree nature of
> dentry references.

Only the cache knows that. The cache provides a destructo. In that 
destructor the tree nature of the dentries can be considered. The 
destructor knows about the tree nature of the slab and that can navigate 
through the dependency structures that the object may be a part of.

> Christoph, I'm afraid that not using the LRU information can be harmful
> to certain workloads... 

It can be very beneficial too since removing the LRU will avoid locking in 
certain situations and it will shrink the objects. We already have lists 
of all the objects in the slab. The LRU is redundant in some way.

Of course there is the challenge of preserving the LRU like behavior using 
the slab lists. But I think it may be sufficiently approximated by the 
LRU ness of the used slab list and the push back to the partial lists 
whenever we touch a slab during reclaim (we free some objects so the slab 
has to move).

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Marcelo Tosatti]

On Mon, Jul 03, 2006 at 11:10:15AM -0700, Christoph Lameter wrote:
> On Sun, 2 Jul 2006, Marcelo Tosatti wrote:
> 
> > > > I was, of course, referring to the unpleasant requirement that the object
> > > > layout start with an atomic_t.
> > > 
> > > Is that such a problem? It reduces the amount of indirect function calls 
> > > needed.
> > 
> > Need to benchmark I guess.
> 
> I think is pretty obvious. With atomic refcounters you can simply scan
> a slab for unused objects without any callbacks. Needing a callback for 
> every single object is a waste of resources and will limit reclaim 
> efficiency. You would have to do 120 callbacks on some slabs just to 
> figure out that it is worth trying to free objects in that 
> particular slab block.

Inline the callbacks into a per-cache kmem_cache_reclaim ?

> > I agree with Andrew, an atomic counter to indicate usage of the objects
> > is too simplistic (other than being unpleasant).
> 
> Cannot see a valid reason so far to draw that conclusion. With the right 
> convention the atomic refcounter can be used as an indicator that the 
> object is being freed (refcnt = 0), not in use (refcnt = 1) or in active 
> use (refcnt=2). The easy and efficient access to this kind of knowledge 
> about an object is essential for reclaim.

But the assumption that "refcnt = 1 implies unused object" is too weak.

For example, 

struct dentry {
        atomic_t d_count;
        unsigned int d_flags;           /* protected by d_lock */

d_count can be higher than one _and_ the object freeable. Think of
workloads operating on a large number of directories.

Andrew mentioned:

"That seems like quite a drawback. A single refcount=2 object on the
page means that nothing gets freed from that page at all. It'd be easy
(especially with dcache) to do tons of work without achieving anything."

> > > > How do you propose handling the locking?  dcache is passed a bare pointer
> > > > and no locks are held, but it is guaranteed that the object won't be freed
> > > > while it's playing with it?
> > > 
> > > The reference counter can be used to insure that the object is not freed.
> > 
> > Locking is pretty tricky...
> 
> Not at all. You do an atomic_inc_if_not_zero from the destructor and then 
> either will hold the object to good or you were unable to increment the 
> refcount and therefore you can give up and return because the object 
> is already being freed.

And might need locking too.

> The tricky locking part comes later when the destructor has to establish 
> the locks to get all links to the object released.

Right.

> 
> > What it does is to create a small set callbacks to invoke higher-level
> > code:
> > 
> > +struct slab_reclaim_ops {
> > +	int (*objp_is_freeable)(void *objp);
> > +	int (*objp_release)(void *objp);
> > +	int (*objp_lock)(void *objp);
> > +	int (*objp_unlock)(void *objp);
> > +};
> > 
> > Which are used by generic SLAB code to check for, and release, fully
> > freeable pages (you've seen it before, from last year). It contains a
> > dcache implementation.
> 
> Ok. I will have a look at that. But these callbacks are too heavy for my 
> taste. A refcounter could avoid all of that.

Inline them.

> > You really need cache specific information, such as the tree nature of
> > dentry references.
> 
> Only the cache knows that. The cache provides a destructo. In that 
> destructor the tree nature of the dentries can be considered. The 
> destructor knows about the tree nature of the slab and that can navigate 
> through the dependency structures that the object may be a part of.
> 
> > Christoph, I'm afraid that not using the LRU information can be harmful
> > to certain workloads... 
> 
> It can be very beneficial too since removing the LRU will avoid locking in 
> certain situations and it will shrink the objects. We already have lists 
> of all the objects in the slab. The LRU is redundant in some way.

Its likely that the logic should consider hints about recent object
usage, for example DCACHE_REFERENCED for dentries. The "callbacks" are
interesting for that purpose too.

> Of course there is the challenge of preserving the LRU like behavior using 
> the slab lists. But I think it may be sufficiently approximated by the 
> LRU ness of the used slab list and the push back to the partial lists 
> whenever we touch a slab during reclaim (we free some objects so the slab 
> has to move).

Well, individual object usage is not reflected at all in the slab lists,
is it?

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Christoph Lameter]

On Mon, 3 Jul 2006, Marcelo Tosatti wrote:

> > I think is pretty obvious. With atomic refcounters you can simply scan
> > a slab for unused objects without any callbacks. Needing a callback for 
> > every single object is a waste of resources and will limit reclaim 
> > efficiency. You would have to do 120 callbacks on some slabs just to 
> > figure out that it is worth trying to free objects in that 
> > particular slab block.
> 
> Inline the callbacks into a per-cache kmem_cache_reclaim ?

You mean the user writes the check functions? Can you give an example how 
inlining is supposed to work here?

> > Cannot see a valid reason so far to draw that conclusion. With the right 
> > convention the atomic refcounter can be used as an indicator that the 
> > object is being freed (refcnt = 0), not in use (refcnt = 1) or in active 
> > use (refcnt=2). The easy and efficient access to this kind of knowledge 
> > about an object is essential for reclaim.
> 
> But the assumption that "refcnt = 1 implies unused object" is too weak.
> 
> For example, 
> 
> struct dentry {
>         atomic_t d_count;
>         unsigned int d_flags;           /* protected by d_lock */
> 
> d_count can be higher than one _and_ the object freeable. Think of
> workloads operating on a large number of directories.

The scheme that I proposed implies that the refcount handling is changed.
It must be uniform for all object types that use reclaim.

If used for the dcache then dentry handling must be changed so that the 
refcount at the beginnDing of the slab is 1 if the object is reclaimable 
and the higher refcount needs to be an indicator that the object is in 
use. I am not saying that existing use gets us there. Maybe we need to 
call this a reclaim flag instead of a refcount?

> Andrew mentioned:
> 
> "That seems like quite a drawback. A single refcount=2 object on the
> page means that nothing gets freed from that page at all. It'd be easy
> (especially with dcache) to do tons of work without achieving anything."

We can check for a single high count object in a slab and then call
the destructor if we feel that is warranted. The refcount is an 
indicator to the slab of the reclaim status of the object.

> > Ok. I will have a look at that. But these callbacks are too heavy for my 
> > taste. A refcounter could avoid all of that.
> 
> Inline them.

"Inline" seem to be way to say that the user has to provide the function.

> > Of course there is the challenge of preserving the LRU like behavior using 
> > the slab lists. But I think it may be sufficiently approximated by the 
> > LRU ness of the used slab list and the push back to the partial lists 
> > whenever we touch a slab during reclaim (we free some objects so the slab 
> > has to move).
> 
> Well, individual object usage is not reflected at all in the slab lists,
> is it?

Correct. We would have to treat objects in a slab all the same. We could 
just kick out some if we find the slab at the end of the list and see how 
things develop. Pretty bare hacky LRU but it may be better than going 
through huge lists of small objects on a LRU lists.

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Marcelo Tosatti]

On Mon, Jul 03, 2006 at 06:46:55PM -0700, Christoph Lameter wrote:
> On Mon, 3 Jul 2006, Marcelo Tosatti wrote:
> 
> > > I think is pretty obvious. With atomic refcounters you can simply scan
> > > a slab for unused objects without any callbacks. Needing a callback for 
> > > every single object is a waste of resources and will limit reclaim 
> > > efficiency. You would have to do 120 callbacks on some slabs just to 
> > > figure out that it is worth trying to free objects in that 
> > > particular slab block.
> > 
> > Inline the callbacks into a per-cache kmem_cache_reclaim ?
> 
> You mean the user writes the check functions? Can you give an example how 
> inlining is supposed to work here?

I meant per-cache kmem_cache_reclaim (user-provided function). "Inline"
is confusing, sorry.

> > > Cannot see a valid reason so far to draw that conclusion. With the right 
> > > convention the atomic refcounter can be used as an indicator that the 
> > > object is being freed (refcnt = 0), not in use (refcnt = 1) or in active 
> > > use (refcnt=2). The easy and efficient access to this kind of knowledge 
> > > about an object is essential for reclaim.
> > 
> > But the assumption that "refcnt = 1 implies unused object" is too weak.
> > 
> > For example, 
> > 
> > struct dentry {
> >         atomic_t d_count;
> >         unsigned int d_flags;           /* protected by d_lock */
> > 
> > d_count can be higher than one _and_ the object freeable. Think of
> > workloads operating on a large number of directories.
> 
> The scheme that I proposed implies that the refcount handling is changed.
> It must be uniform for all object types that use reclaim. 
>
> If used for the dcache then dentry handling must be changed so that the 
> refcount at the beginnDing of the slab is 1 if the object is reclaimable 
> and the higher refcount needs to be an indicator that the object is in 
> use. I am not saying that existing use gets us there. Maybe we need to 
> call this a reclaim flag instead of a refcount?

I think the cache has to decide...

> > Andrew mentioned:
> > 
> > "That seems like quite a drawback. A single refcount=2 object on the
> > page means that nothing gets freed from that page at all. It'd be easy
> > (especially with dcache) to do tons of work without achieving anything."
> 
> We can check for a single high count object in a slab and then call
> the destructor if we feel that is warranted. The refcount is an 
> indicator to the slab of the reclaim status of the object.
> 
> > > Ok. I will have a look at that. But these callbacks are too heavy for my 
> > > taste. A refcounter could avoid all of that.
> > 
> > Inline them.
> 
> "Inline" seem to be way to say that the user has to provide the function.

Yes.

> > > Of course there is the challenge of preserving the LRU like behavior using 
> > > the slab lists. But I think it may be sufficiently approximated by the 
> > > LRU ness of the used slab list and the push back to the partial lists 
> > > whenever we touch a slab during reclaim (we free some objects so the slab 
> > > has to move).
> > 
> > Well, individual object usage is not reflected at all in the slab lists,
> > is it?
> 
> Correct. We would have to treat objects in a slab all the same. We could 
> just kick out some if we find the slab at the end of the list and see how 
> things develop. Pretty bare hacky LRU but it may be better than going 
> through huge lists of small objects on a LRU lists.

Yep... Did you try this?

Re: [RFC 0/4] Object reclaim via the slab allocator V1

[Christoph Lameter]

On Mon, 3 Jul 2006, Marcelo Tosatti wrote:

> > If used for the dcache then dentry handling must be changed so that the 
> > refcount at the beginnDing of the slab is 1 if the object is reclaimable 
> > and the higher refcount needs to be an indicator that the object is in 
> > use. I am not saying that existing use gets us there. Maybe we need to 
> > call this a reclaim flag instead of a refcount?
> 
> I think the cache has to decide...

The cache decides by setting the refcount/reclaim flag.

I doubt that I get to revising this in the next week. Can we have a slab 
reclaim meeting in Ottawa?