Skip to contentSkip to conversation

Object reclaim via the slab allocator V1

RFC In review Christoph Lameter 5 participants 31 messages Jun 19, 2006 – Jul 4, 2006

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover Object reclaim via the slab allocator V1

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

#1 lore raw

RFC 1/4 slab freeing consolidation

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.

mm/slab.c +41 -62
Index: linux-2.6.17-rc6-mm2/mm/slab.c
===================================================================
@@ -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();
 	}
#2 lore raw

Re: [RFC 1/4] slab freeing consolidation

HI,

Quoted 2 lines · Christoph Lameter

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.

mm/slab.c static void drain_cpu_caches(struct kmem · line 2283

Quoted 9 lines
mm/slab.c +8 -1
-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'.

mm/slab.c static void drain_cpu_caches(struct kmem · line 2294

Quoted 9 lines
mm/slab.c +5 -3
+	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.

mm/slab.c static void drain_cpu_caches(struct kmem · line 2297

Quoted 3 lines
mm/slab.c +3 -0
+			spin_unlock_irq(&l3->list_lock);
+			return nr_freed;
+		}

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

Quoted 10 lines
mm/slab.c +3 -2
-		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

mm/slab.c static void drain_cpu_caches(struct kmem · line 2311

Quoted 10 lines
mm/slab.c +3 -4
+		 * 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.

mm/slab.c static void drain_cpu_caches(struct kmem · line 2312

Quoted 1 line
mm/slab.c +1 -0
+	};

Redundant semicolon.

mm/slab.c static void cache_reap(void *unused) · line 3796

Quoted 2 lines
mm/slab.c +2 -0
+		else {
+			int x;

nr_freed, would be better.

Quoted 8 lines
mm/slab.c +0 -7
-			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

mm/slab.c static void cache_reap(void *unused) · line 3800

Quoted 10 lines
mm/slab.c +3 -7
-			 * 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

#3 lore raw

Re: [RFC 1/4] slab freeing consolidation

Quoted 5 lines · Pekka J Enberg

Review

Quoted 2 lines
(quoted diff) +2 -0
+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.

mm/slab.c +42 -62
Index: linux-2.6.17/mm/slab.c
===================================================================
@@ -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();
 	}
#4 lore raw

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

In reply to Christoph Lameter

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

Remove destructor and call kmem_cache_create with NULL for the destructor.

drivers/usb/mon/mon_text.c +1 -6
Index: linux-2.6.17-rc6-mm2/drivers/usb/mon/mon_text.c
===================================================================
@@ -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)
-{
-	;
-}
#6 lore raw

RFC 3/4 Add checks to current destructor uses

In reply to 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.

arch/i386/mm/pgtable.c +5 -1
Index: linux-2.6.17-rc6-mm2/arch/i386/mm/pgtable.c
===================================================================
@@ -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;
include/linux/slab.h +3 -0
Index: linux-2.6.17-rc6-mm2/include/linux/slab.h
===================================================================
@@ -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 */
arch/frv/mm/pgalloc.c +4 -1
Index: linux-2.6.17-rc6-mm2/arch/frv/mm/pgalloc.c
===================================================================
@@ -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);
#7 lore raw

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

Quoted 4 lines · 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.

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

#8 lore raw

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

Quoted 9 lines · Pekka J Enberg
Quoted 4 lines · 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.

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.

arch/i386/mm/pgtable.c +5 -1
Index: linux-2.6.17/arch/i386/mm/pgtable.c
===================================================================
@@ -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;
include/linux/slab.h +3 -0
Index: linux-2.6.17/include/linux/slab.h
===================================================================
@@ -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 */
arch/frv/mm/pgalloc.c +4 -1
Index: linux-2.6.17/arch/frv/mm/pgalloc.c
===================================================================
@@ -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);
mm/slab.c +5 -3
Index: linux-2.6.17/mm/slab.c
===================================================================
@@ -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;
#9 lore raw

PATCH 4/4 Slab Reclaim logic

In reply to 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.

include/linux/slab.h +3 -0
Index: linux-2.6.17-rc6-mm2/include/linux/slab.h
===================================================================
@@ -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 */
Documentation/slab_reclaim new file +57 -0

57 lines not on this page · raw message

mm/slab.c +192 -6

242 lines not on this page · raw message

#11 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

In reply to Christoph Lameter
Quoted 8 lines · Christoph Lameter
mm/slab.c +2 -1
@@ -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]

mm/slab.c struct kmem_list3 { · line 303

Quoted 6 lines
mm/slab.c +1 -0
@@ -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

#12 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

Quoted 11 lines · Pekka J Enberg

mm/slab.c struct kmem_list3 { · line 303

Quoted 6 lines
mm/slab.c +1 -0
@@ -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.

#13 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

Quoted 6 lines · Pekka J Enberg
Quoted 6 lines
Quoted 6 lines
mm/slab.c +1 -0
@@ -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 */
 };
Quoted 8 lines · Christoph Lameter

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

#14 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

Quoted 2 lines · Pekka J Enberg

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.

#15 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

In reply to Christoph Lameter
Quoted 6 lines · 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)

Some coding style comments below.

Quoted 1 line

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

The parameter name is redundant.

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4260

Quoted 2 lines
mm/slab.c +2 -0
+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.

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4352

Quoted 2 lines
mm/slab.c +2 -0
+static int reclaim_scan(kmem_cache_t *cachep, struct kmem_list3 *l3,
+	int slabs_to_free, struct list_head *list, unsigned short marker)

Ditto.

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4354

Quoted 2 lines
mm/slab.c +2 -0
+{
+	int nr_freed = 0;

s/nr_freed/ret/

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4357

Quoted 3 lines
mm/slab.c +3 -0
+
+	while (nr_freed < slabs_to_free) {
+		int x;

s/x/nr_freed/

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4373

Quoted 12 lines
mm/slab.c +11 -0
+
+		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.

#16 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

Quoted 5 lines · Pekka J Enberg

Some coding style comments below.

Quoted 1 line

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

The parameter name is redundant.

Ok.

Quoted 6 lines

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4260

Quoted 3 lines
mm/slab.c +2 -0
+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.

Quoted 4 lines

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4354

Quoted 2 lines
mm/slab.c +2 -0
+{
+	int nr_freed = 0;

s/nr_freed/ret/

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

Quoted 4 lines

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4357

Quoted 2 lines
mm/slab.c +2 -0
+	while (nr_freed < slabs_to_free) {
+		int x;

s/x/nr_freed/

Would shadow variable.

#17 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

Quoted 11 lines · Christoph Lameter
Quoted 1 line

s/nr_freed/ret/

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

Quoted 4 lines

mm/slab.c void kmem_set_shrinker(kmem_cache_t *cac · line 4357

Quoted 2 lines
mm/slab.c +2 -0
+	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

#18 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

In reply to Christoph Lameter
Quoted 4 lines · Christoph Lameter
Quoted 2 lines

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

#19 lore raw

Re: [PATCH 4/4] Slab Reclaim logic

Quoted 7 lines · Pekka J Enberg
Quoted 4 lines · Christoph Lameter
Quoted 2 lines

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.

#20 lore raw
In reply to Christoph Lameter
Quoted 1 line · Christoph Lameter

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

#21 lore raw
In reply to Christoph Lameter
Quoted 40 lines · 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.

Quoted 6 lines

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.

Quoted 7 lines

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.

Quoted 8 lines

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.

#22 lore raw
Quoted 8 lines · Andrew Morton
Quoted 4 lines

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.

Quoted 7 lines
Quoted 3 lines

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.

Quoted 1 line

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.

Quoted 3 lines

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.

#23 lore raw
Quoted 7 lines · On Wed, 28 Jun 2006 17:47:17 -0700 (PDT) Christoph Lameter <[email protected]>…
Quoted 5 lines · Andrew Morton
Quoted 4 lines

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.

Quoted 5 lines
Quoted 3 lines

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.

Quoted 9 lines
Quoted 7 lines
Quoted 3 lines

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.

Quoted 7 lines

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

Quoted 1 line

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.

Quoted 8 lines
Quoted 3 lines

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?

#24 lore raw
Quoted 8 lines · Andrew Morton
Quoted 5 lines
Quoted 3 lines

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.

Quoted 4 lines
Quoted 2 lines

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.

Quoted 8 lines
Quoted 4 lines

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.

Quoted 2 lines

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.

#25 lore raw
Quoted 6 lines · Christoph Lameter
Quoted 4 lines · Andrew Morton
Quoted 4 lines
Quoted 3 lines

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.

Quoted 7 lines
Quoted 4 lines
Quoted 1 line

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).

Quoted 13 lines
Quoted 4 lines
Quoted 2 lines

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.

Quoted 5 lines
Quoted 4 lines

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.

Quoted 5 lines
Quoted 3 lines

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...

Quoted 10 lines
Quoted 2 lines

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.

#26 lore raw
Quoted 7 lines · Marcelo Tosatti
Quoted 5 lines
Quoted 2 lines

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.

Quoted 2 lines

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.

Quoted 7 lines
Quoted 5 lines
Quoted 3 lines

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.

Quoted 10 lines

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

(quoted diff) +6 -0
+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);
+};
Quoted 3 lines

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.

Quoted 2 lines

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.

Quoted 2 lines

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).

#27 lore raw
Quoted 8 lines · Christoph Lameter
Quoted 6 lines · Marcelo Tosatti
Quoted 5 lines
Quoted 2 lines

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.

Quoted 8 lines
Quoted 1 line

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 ?

Quoted 8 lines
Quoted 2 lines

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."

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines

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?

Quoted 8 lines
Quoted 3 lines
Quoted 1 line

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.

Quoted 2 lines

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

Right.

Quoted 11 lines
Quoted 11 lines

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

(quoted diff) +6 -0
+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);
+};
Quoted 6 lines
Quoted 3 lines

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.

Quoted 8 lines
Quoted 2 lines

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.

Quoted 6 lines
Quoted 2 lines

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.

Quoted 5 lines

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?

#28 lore raw
Quoted 8 lines · Marcelo Tosatti
Quoted 6 lines

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?

Quoted 8 lines
Quoted 5 lines

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.

Quoted 8 lines

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?

Quoted 5 lines

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.

Quoted 4 lines
Quoted 2 lines

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.

Quoted 8 lines
Quoted 5 lines

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.

#29 lore raw
Quoted 9 lines · Christoph Lameter
Quoted 7 lines · Marcelo Tosatti
Quoted 6 lines

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.

Quoted 4 lines
Quoted 1 line

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.

Quoted 17 lines
Quoted 8 lines
Quoted 5 lines

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.

Quoted 8 lines

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.

Quoted 8 lines

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...

Quoted 10 lines
Quoted 5 lines

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.

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

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.

Quoted 6 lines
Quoted 6 lines
Quoted 5 lines

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).

Quoted 7 lines
Quoted 2 lines

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?

#30 lore raw
Quoted 7 lines · Marcelo Tosatti
Quoted 5 lines

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?