Skip to contentSkip to conversation

concurrent radix tree - getting rid of the writelock too.

RFC New Peter Zijlstra 1 participant 1 message Jun 21, 2006

Subsystems (2)
Memory management Kbuild
lore
Share & tools
lore

Peter Zijlstra

author
#0 lore raw

RFC 1/1 concurrent radix tree - getting rid of the writelock too.

Hi

Its work in progress, although it does seem to finish both tests successfully, still need to write more.

The approach is rather simple, add a lock to each node and ladder lock downwards. The funny parts are where you also need to go up again, here the shortest possible tree path is kept locked. With larger trees the top levels should be unlocked quite easily which will allow modification on other sub-trees.

Patch against Nick's latest RCU enhanced rtth package (dunno if its public).

Comments?

linux/radix-tree.h +5 -1
diff -Naurp -x '*.o' -x '*~' -x '*.sw?' -x tags -x threaded -x main rtth/linux/radix-tree.h rtth-peterz/linux/radix-tree.h
@@ -24,6 +24,7 @@
 #include <linux/types.h>
 #include <linux/kernel.h>
 #include <linux/rcupdate.h>
+#include <linux/spinlock.h>
 
 #define RADIX_TREE_MAX_TAGS 2
 

@@ -32,12 +33,14 @@ struct radix_tree_root {
 	unsigned int		height;
 	gfp_t			gfp_mask;
 	struct radix_tree_node	*rnode;
+	spinlock_t		lock;
 };
 
 #define RADIX_TREE_INIT(mask)	{					\
 	.height = 0,							\
 	.gfp_mask = (mask),						\
 	.rnode = NULL,							\
+	.lock = SPIN_LOCK_UNLOCKED,					\
 }
 
 #define RADIX_TREE(name, mask) \

@@ -48,6 +51,7 @@ do {									\
 	(root)->height = 0;						\
 	(root)->gfp_mask = (mask);					\
 	(root)->rnode = NULL;						\
+	spin_lock_init(&(root)->lock);					\
 } while (0)
 
 #define RADIX_TREE_DIRECT_PTR	1

@@ -83,7 +87,7 @@ static inline void radix_tree_replace_sl
 
 int radix_tree_insert(struct radix_tree_root *, unsigned long, void *);
 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
-void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
+void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long, spinlock_t **);
 void *radix_tree_delete(struct radix_tree_root *, unsigned long);
 unsigned int
 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
linux/rcupdate.h +1 -2
diff -Naurp -x '*.o' -x '*~' -x '*.sw?' -x tags -x threaded -x main rtth/linux/rcupdate.h rtth-peterz/linux/rcupdate.h
@@ -3,8 +3,7 @@
 
 #include <linux/list.h>
 
-#define smp_wmb()       __asm__ __volatile__ ("eieio" : : : "memory")
-#define smp_mb()       __asm__ __volatile__ ("sync" : : : "memory")
+#define smp_wmb()       __asm__ __volatile__ ("" : : : "memory")
 
 void rcu_init(void);
 void rcu_exit(void);
linux/slab.h +3 -1
diff -Naurp -x '*.o' -x '*~' -x '*.sw?' -x tags -x threaded -x main rtth/linux/slab.h rtth-peterz/linux/slab.h
@@ -5,8 +5,10 @@
 #define SLAB_HWCACHE_ALIGN 1
 #define SLAB_PANIC 2
 
-typedef struct {
+typedef struct __kmem_cache_t {
 	int size;
+	void (*ctor)(void*, struct __kmem_cache_t*, unsigned long);
+	void (*dtor)(void*, struct __kmem_cache_t*, unsigned long);
 } kmem_cache_t;
 
 void *kmem_cache_alloc(kmem_cache_t *cachep, int flags);
linux/spinlock.h +15 -0
diff -Naurp -x '*.o' -x '*~' -x '*.sw?' -x tags -x threaded -x main rtth/linux/spinlock.h rtth-peterz/linux/spinlock.h
@@ -0,0 +1,15 @@
+#ifndef __SPINLOCK_H__
+#define __SPINLOCK_H__
+
+#include <pthread.h>
+
+typedef pthread_spinlock_t spinlock_t;
+
+#define spin_lock_init(lock) pthread_spin_init(lock, 0)
+#define spin_lock(lock) pthread_spin_lock(lock)
+#define spin_trylock(lock) pthread_spin_trylock(lock)
+#define spin_unlock(lock) pthread_spin_unlock(lock)
+
+#define SPIN_LOCK_UNLOCKED 1
+
+#endif /* __SPINLOCK_H__ */
linux.c +3 -0
diff -Naurp -x '*.o' -x '*~' -x '*.sw?' -x tags -x threaded -x main rtth/linux.c rtth-peterz/linux.c
@@ -36,6 +36,8 @@ void *kmem_cache_alloc(kmem_cache_t *cac
 {
 	void *ret = malloc(cachep->size);
 	memset(ret, 0, cachep->size);
+	if (cachep->ctor)
+		cachep->ctor(ret, cachep, flags);
 	nr_allocated++;
 	return ret;
 }

@@ -56,5 +58,6 @@ kmem_cache_create(const char *name, size
 	kmem_cache_t *ret = malloc(sizeof(*ret));
 
 	ret->size = size;
+	ret->ctor = ctor;
 	return ret;
 }
Makefile +3 -2
diff -Naurp -x '*.o' -x '*~' -x '*.sw?' -x tags -x threaded -x main rtth/Makefile rtth-peterz/Makefile
@@ -1,5 +1,6 @@
 
-CFLAGS += -I. -O3 -fno-strict-aliasing -Wall -D_THREAD_SAFE
+#CFLAGS += -I. -O3 -fno-strict-aliasing -Wall -D_THREAD_SAFE -D_GNU_SOURCE
+CFLAGS += -I. -ggdb3 -fno-strict-aliasing -Wall -D_THREAD_SAFE -D_GNU_SOURCE
 
 OFILES = radix-tree.o linux.o test.o tag_check.o rcupdate.o
 

@@ -7,7 +8,7 @@ threaded: threaded.o $(OFILES)
 	$(CC) $(CFLAGS) -lpthread threaded.o $(OFILES) -o threaded
 
 main:	main.o $(OFILES)
-	$(CC) $(CFLAGS) main.o $(OFILES) -o main
+	$(CC) $(CFLAGS) -lpthread main.o $(OFILES) -o main
 
 clean:
 	$(RM) -f $(TARGETS) *.o main threaded
radix-tree.c +206 -63

479 lines not on this page · raw message

test.c +13 -4
diff -Naurp -x '*.o' -x '*~' -x '*.sw?' -x tags -x threaded -x main rtth/test.c rtth-peterz/test.c
@@ -3,6 +3,7 @@
 #include <stdio.h>
 
 #include <linux/rcupdate.h>
+#include <linux/spinlock.h>
 
 #include "test.h"
 

@@ -73,25 +74,30 @@ struct item *item_create(unsigned long i
 void item_check_present(struct radix_tree_root *root, unsigned long index)
 {
 	struct item *item, **itemp;
+	spinlock_t *lock;
 
 	item = radix_tree_lookup(root, index);
 	assert(item != 0);
 	assert(item->index == index);
 
-	itemp = (struct item **)radix_tree_lookup_slot(root, index);
+	itemp = (struct item **)radix_tree_lookup_slot(root, index, &lock);
 	assert((item == NULL && itemp == NULL)
 			|| item == radix_tree_deref_slot(itemp));
+	if (lock)
+		spin_unlock(lock);
 }
 
 struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
 {
 	struct item *item, **itemp;
+	spinlock_t *lock;
 
 	item = radix_tree_lookup(root, index);
-	itemp = (struct item **)radix_tree_lookup_slot(root, index);
+	itemp = (struct item **)radix_tree_lookup_slot(root, index, &lock);
 	assert((item == NULL && itemp == NULL)
 			|| item == radix_tree_deref_slot(itemp));
-
+	if (lock)
+		spin_unlock(lock);
 	return item;
 }
 

@@ -103,13 +109,16 @@ struct item *item_lookup_rcu(struct radi
 void item_check_absent(struct radix_tree_root *root, unsigned long index)
 {
 	struct item *item, **itemp;
+	spinlock_t *lock;
 
 	item = radix_tree_lookup(root, index);
 	assert(item == 0);
 
-	itemp = (struct item **)radix_tree_lookup_slot(root, index);
+	itemp = (struct item **)radix_tree_lookup_slot(root, index, &lock);
 	assert((item == NULL && itemp == NULL)
 			|| item == radix_tree_deref_slot(itemp));
+	if (lock)
+		spin_unlock(lock);
 }
 
 /*
threaded.c +10 -3
diff -Naurp -x '*.o' -x '*~' -x '*.sw?' -x tags -x threaded -x main rtth/threaded.c rtth-peterz/threaded.c
@@ -50,8 +50,6 @@ static void *random_updater(void *arg)
 			item_delete(&tree, idx);
 		}
 	}
-	item_kill_tree(&tree);
-	printk("after random_updater %d allocated\n", nr_allocated);
 
 	return NULL;
 }

@@ -247,6 +245,7 @@ int main()
 {
 	int i, t = 0;
 	pthread_t readers[4];
+	pthread_t writers[4];
 
 	srandom(10);
 

@@ -259,7 +258,15 @@ int main()
 	pthread_create(&readers[t++], NULL, &zeroone_reader, NULL);
 
 	simple_updater(NULL);
-	random_updater(NULL);
+
+	for (i=0; i<4; ++i)
+		pthread_create(&writers[i], NULL, &random_updater, NULL);
+	for (i=0; i<4; ++i)
+		pthread_join(writers[i], NULL);
+
+	item_kill_tree(&tree);
+	printk("after random_updater %d allocated\n", nr_allocated);
+
 	height_change_updater(NULL);
 	direct_change_updater(NULL);
 	direct_updater(NULL);

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>