lockless pagecache

RFC New Nick Piggin 17 participants 56 messages Jun 27, 2005 – Jul 5, 2005

Subsystems (11)

Memory management VFS Library code Memory technology devices (MTD) +7 more subsystems

lore

Share & tools

lore

Nick Piggin

author

2005-06-27 06:29 UTC #0 lore raw

Hi,

This is going to be a fairly long and probably incoherent post. The idea and implementation are not completely analysed for holes, and I wouldn't be surprised if some (even fatal ones) exist.

That said, I wanted something to talk about at Ottawa and I think this is a promising idea - it is at the stage where it would be good to have interested parties pick it apart. BTW. this is my main reason for the PageReserved removal patches, so if this falls apart then some good will have come from it! :)

OK, so my aim is to remove the requirement to take mapping->tree_lock when looking up pagecache pages (eg. for a read/write or nopage fault). Note that this does not deal with insertion and removal of pages from pagecache mappings - that is usually a slower path operation associated with IO or page reclaim or truncate. However if there was interest in making these paths more scalable, there are possibilities for that too.

What for? Well there are probably lots of reasons, but suppose you have a big app with lots of processes all mmaping and playing around with various parts of the same big file (say, a shared memory file), then you might start seeing problems if you want to scale this workload up to say 32+ CPUs.

Now the tree_lock was recently(ish) converted to an rwlock, precisely for such a workload and that was apparently very successful. However an rwlock is significantly heavier, and as machines get faster and bigger, rwlocks (and any locks) will tend to use more and more of Paul McKenney's toilet paper due to cacheline bouncing.

So in the interest of saving some trees, let's try it without any locks.

First I'll put up some numbers to get you interested - of a 64-way Altix with 64 processes each read-faulting in their own 512MB part of a 32GB file that is preloaded in pagecache (with the proper NUMA memory allocation).

[best of 5 runs]

plain 2.6.12-git4:
1 proc 0.65u 1.43s 2.09e 99%CPU
64 proc 0.75u 291.30s 4.92e 5927%CPU

64 proc prof:
3242763 total 0.5366
1269413 _read_unlock_irq 19834.5781

842042 do_no_page                               355.5921
779373 cond_resched                             3479.3438
100667 ia64_pal_call_static                     524.3073
 96469 _spin_lock                               1004.8854
 92857 default_idle                             241.8151

25572 filemap_nopage 15.6691
11981 ia64_load_scratch_fpregs 187.2031
11671 ia64_save_scratch_fpregs 182.3594
2566 page_fault 2.5867

It has slowed by a factor of 2.5x when going from serial to 64-way, and it is due to mapping->tree_lock. Serial is even at the disadvantage of reading from remote memory 62 times out of 64.

2.6.12-git4-lockless:

 1 proc    0.66u   1.38s 2.04e 99%CPU
64 proc    0.68u   1.42s 0.12e 1686%CPU

64 proc prof:
81934 total 0.0136
31108 ia64_pal_call_static 162.0208

 28394 default_idle                              73.9427
  3796 ia64_save_scratch_fpregs                  59.3125
  3736 ia64_load_scratch_fpregs                  58.3750
  2208 page_fault                                 2.2258
  1380 unmap_vmas                                 0.3292
  1298 __mod_page_state                           8.1125
  1089 do_no_page                                 0.4599
   830 find_get_page                              2.5938
   781 ia64_do_page_fault                         0.2805

So we have increased performance exactly 17x when going from 1 to 64 way, however if you look at the CPU utilisation figure and the elapsed time, you'll see my test didn't provide enough work to keep all CPUs busy, and for the amount of CPU time used, we appear to have perfect scalability. In fact, it is slightly superlinear probably due to remote memory access on the serial run.

I'll reply to this post with the series of commented patches which is probably the best way to explain how it is done. They are against 2.6.12-git4 + some future iteration of the PageReserved patches. I can provide the complete rollup privately on request.

Comments, flames, laughing me out of town, etc. are all very welcome.

Nick

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Nick Piggin

author

2005-06-27 06:32 UTC #1 lore raw

PATCH 1/1 mm: PG_free flag

Signature · 2 lines

-- 
SUSE Labs, Novell Inc.

In a future patch we can no longer rely on page_count being stable at any time, so we can no longer overload PagePrivate && page_count == 0 to mean the page is free and on the buddy lists.

include/linux/page-flags.h +6 -0

Index: linux-2.6/include/linux/page-flags.h
===================================================================
@@ -76,6 +76,8 @@
 #define PG_nosave_free		18	/* Free, should not be written */
 #define PG_uncached		19	/* Page has been mapped as uncached */
 
+#define PG_free			20	/* Page is on the free lists */
+
 /*
  * Global page accounting.  One instance per CPU.  Only unsigned longs are
  * allowed.

@@ -306,6 +308,10 @@ extern void __mod_page_state(unsigned lo
 #define SetPageUncached(page)	set_bit(PG_uncached, &(page)->flags)
 #define ClearPageUncached(page)	clear_bit(PG_uncached, &(page)->flags)
 
+#define PageFree(page)		test_bit(PG_free, &(page)->flags)
+#define __SetPageFree(page)	__set_bit(PG_free, &(page)->flags)
+#define __ClearPageFree(page)	__clear_bit(PG_free, &(page)->flags)
+
 struct page;	/* forward declaration */
 
 int test_clear_page_dirty(struct page *page);

mm/page_alloc.c +9 -8

Index: linux-2.6/mm/page_alloc.c
===================================================================
@@ -114,7 +114,8 @@ static void bad_page(const char *functio
 			1 << PG_slab    |
 			1 << PG_swapcache |
 			1 << PG_writeback |
-			1 << PG_reserved );
+			1 << PG_reserved |
+			1 << PG_free );
 	set_page_count(page, 0);
 	reset_page_mapcount(page);
 	page->mapping = NULL;

@@ -191,12 +192,12 @@ static inline unsigned long page_order(s
 
 static inline void set_page_order(struct page *page, int order) {
 	page->private = order;
-	__SetPagePrivate(page);
+	__SetPageFree(page);
 }
 
 static inline void rmv_page_order(struct page *page)
 {
-	__ClearPagePrivate(page);
+	__ClearPageFree(page);
 	page->private = 0;
 }

@@ -242,9 +243,7 @@ __find_combined_index(unsigned long page
  */
 static inline int page_is_buddy(struct page *page, int order)
 {
-       if (PagePrivate(page)           &&
-           (page_order(page) == order) &&
-            page_count(page) == 0)
+       if (PageFree(page) && (page_order(page) == order))
                return 1;
        return 0;
 }

@@ -327,7 +326,8 @@ static inline void free_pages_check(cons
 			1 << PG_slab	|
 			1 << PG_swapcache |
 			1 << PG_writeback |
-			1 << PG_reserved )))
+			1 << PG_reserved |
+			1 << PG_free )))
 		bad_page(function, page);
 	if (PageDirty(page))
 		__ClearPageDirty(page);

@@ -456,7 +456,8 @@ static void prep_new_page(struct page *p
 			1 << PG_slab    |
 			1 << PG_swapcache |
 			1 << PG_writeback |
-			1 << PG_reserved )))
+			1 << PG_reserved |
+			1 << PG_free )))
 		bad_page(__FUNCTION__, page);
 
 	page->flags &= ~(1 << PG_uptodate | 1 << PG_error |

Nick Piggin

author

2005-06-27 06:32 UTC #2 lore raw

PATCH 1/1 mm: speculative get_page

Signature · 2 lines

-- 
SUSE Labs, Novell Inc.

If we can be sure that elevating the page_count on a pagecache page will pin it, we can speculatively run this operation, and subsequently check to see if we hit the right page rather than relying on holding a lock or otherwise pinning a reference to the page.

This can be done if get_page/put_page behaves in the same manner throughout the whole tree (ie. if we "get" the page after it has been used for something else, we must be able to free it with a put_page).

There needs to be some careful logic for freed pages so they aren't freed again, and also some careful logic for pages in the process of being removed from pagecache.

include/linux/page-flags.h +6 -0

Index: linux-2.6/include/linux/page-flags.h
===================================================================
@@ -77,6 +77,7 @@
 #define PG_uncached		19	/* Page has been mapped as uncached */
 
 #define PG_free			20	/* Page is on the free lists */
+#define PG_freeing		21	/* PG_refcount about to be freed */
 
 /*
  * Global page accounting.  One instance per CPU.  Only unsigned longs are

@@ -312,6 +313,11 @@ extern void __mod_page_state(unsigned lo
 #define __SetPageFree(page)	__set_bit(PG_free, &(page)->flags)
 #define __ClearPageFree(page)	__clear_bit(PG_free, &(page)->flags)
 
+#define PageFreeing(page)	test_bit(PG_freeing, &(page)->flags)
+#define SetPageFreeing(page)	set_bit(PG_freeing, &(page)->flags)
+#define ClearPageFreeing(page)	clear_bit(PG_freeing, &(page)->flags)
+#define __ClearPageFreeing(page) __clear_bit(PG_freeing, &(page)->flags)
+
 struct page;	/* forward declaration */
 
 int test_clear_page_dirty(struct page *page);

include/linux/pagemap.h +36 -0

Index: linux-2.6/include/linux/pagemap.h
===================================================================
@@ -50,6 +50,42 @@ static inline void mapping_set_gfp_mask(
 #define page_cache_release(page)	put_page(page)
 void release_pages(struct page **pages, int nr, int cold);
 
+static inline struct page *page_cache_get_speculative(struct page **pagep)
+{
+	struct page *page;
+
+	preempt_disable();
+	page = *pagep;
+	if (!page)
+		goto out_failed;
+
+	if (unlikely(get_page_testone(page))) {
+		/* Picked up a freed page */
+		__put_page(page);
+		goto out_failed;
+	}
+	/*
+	 * preempt can really be enabled here (only needs to be disabled
+	 * because page allocation can spin on the elevated refcount, but
+	 * we don't want to hold a reference on an unrelated page for too
+	 * long, so keep preempt off until we know we have the right page
+	 */
+
+	if (unlikely(PageFreeing(page)) ||
+			unlikely(page != *pagep)) {
+		/* Picked up a page being freed, or one that's been reused */
+		put_page(page);
+		goto out_failed;
+	}
+	preempt_enable();
+
+	return page;
+
+out_failed:
+	preempt_enable();
+	return NULL;
+}
+
 static inline struct page *page_cache_alloc(struct address_space *x)
 {
 	return alloc_pages(mapping_gfp_mask(x)|__GFP_NORECLAIM, 0);

mm/page_alloc.c +8 -5

Index: linux-2.6/mm/page_alloc.c
===================================================================
@@ -116,7 +116,6 @@ static void bad_page(const char *functio
 			1 << PG_writeback |
 			1 << PG_reserved |
 			1 << PG_free );
-	set_page_count(page, 0);
 	reset_page_mapcount(page);
 	page->mapping = NULL;
 	tainted |= TAINT_BAD_PAGE;

@@ -316,7 +315,6 @@ static inline void free_pages_check(cons
 {
 	if (	page_mapcount(page) ||
 		page->mapping != NULL ||
-		page_count(page) != 0 ||
 		(page->flags & (
 			1 << PG_lru	|
 			1 << PG_private |

@@ -424,7 +422,7 @@ expand(struct zone *zone, struct page *p
 void set_page_refs(struct page *page, int order)
 {
 #ifdef CONFIG_MMU
-	set_page_count(page, 1);
+	get_page(page);
 #else
 	int i;

@@ -434,7 +432,7 @@ void set_page_refs(struct page *page, in
 	 * - eg: access_process_vm()
 	 */
 	for (i = 0; i < (1 << order); i++)
-		set_page_count(page + i, 1);
+		get_page(page + i);
 #endif /* CONFIG_MMU */
 }

@@ -445,7 +443,6 @@ static void prep_new_page(struct page *p
 {
 	if (	page_mapcount(page) ||
 		page->mapping != NULL ||
-		page_count(page) != 0 ||
 		(page->flags & (
 			1 << PG_lru	|
 			1 << PG_private	|

@@ -464,7 +461,13 @@ static void prep_new_page(struct page *p
 			1 << PG_referenced | 1 << PG_arch_1 |
 			1 << PG_checked | 1 << PG_mappedtodisk);
 	page->private = 0;
+
 	set_page_refs(page, order);
+	smp_mb();
+	/* Wait for speculative get_page after count has been elevated. */
+	while (unlikely(page_count(page) > 1))
+		cpu_relax();
+
 	kernel_map_pages(page, 1 << order, 1);
 }

mm/vmscan.c +3 -0

Index: linux-2.6/mm/vmscan.c
===================================================================
@@ -504,6 +504,7 @@ static int shrink_list(struct list_head 
 		if (!mapping)
 			goto keep_locked;	/* truncate got there first */
 
+		SetPageFreeing(page);
 		write_lock_irq(&mapping->tree_lock);
 
 		/*

@@ -513,6 +514,7 @@ static int shrink_list(struct list_head 
 		 */
 		if (page_count(page) != 2 || PageDirty(page)) {
 			write_unlock_irq(&mapping->tree_lock);
+			ClearPageFreeing(page);
 			goto keep_locked;
 		}

@@ -533,6 +535,7 @@ static int shrink_list(struct list_head 
 
 free_it:
 		unlock_page(page);
+		__ClearPageFreeing(page);
 		reclaimed++;
 		if (!pagevec_add(&freed_pvec, page))
 			__pagevec_release_nonlru(&freed_pvec);

mm/bootmem.c +8 -5

Index: linux-2.6/mm/bootmem.c
===================================================================
@@ -278,17 +278,19 @@ static unsigned long __init free_all_boo
 		if (gofast && v == ~0UL) {
 			int j, order;
 
+			prefetchw(page);
 			count += BITS_PER_LONG;
-			__ClearPageReserved(page);
+
 			order = ffs(BITS_PER_LONG) - 1;
-			set_page_refs(page, order);
-			for (j = 1; j < BITS_PER_LONG; j++) {
-				if (j + 16 < BITS_PER_LONG)
-					prefetchw(page + j + 16);
+			for (j = 0; j < BITS_PER_LONG; j++) {
+				if (j + 1 < BITS_PER_LONG)
+					prefetchw(page + j + 1);
 				__ClearPageReserved(page + j);
 				set_page_count(page + j, 0);
 			}
+			set_page_refs(page, order);
 			__free_pages(page, order);
+
 			i += BITS_PER_LONG;
 			page += BITS_PER_LONG;
 		} else if (v) {

@@ -297,6 +299,7 @@ static unsigned long __init free_all_boo
 				if (v & m) {
 					count++;
 					__ClearPageReserved(page);
+					set_page_count(page, 0);
 					set_page_refs(page, 0);
 					__free_page(page);
 				}

Nick Piggin

author

2005-06-27 06:33 UTC #3 lore raw

PATCH 1/1 radix tree: lookup_slot

Signature · 2 lines

-- 
SUSE Labs, Novell Inc.

From: Hans Reiser <[email protected]>

Reiser4 uses radix trees to solve a trouble reiser4_readdir has serving nfs requests.

Unfortunately, radix tree api lacks an operation suitable for modifying existing entry. This patch adds radix_tree_lookup_slot which returns pointer to found item within the tree. That location can be then updated.

Signed-off-by Andrew Morton <[email protected]>

include/linux/radix-tree.h +1 -0

Index: linux-2.6/include/linux/radix-tree.h
===================================================================
@@ -46,6 +46,7 @@ do {									\
 
 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_delete(struct radix_tree_root *, unsigned long);
 unsigned int
 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,

lib/radix-tree.c +32 -9

53 lines not on this page · raw message

Nick Piggin

author

2005-06-27 06:34 UTC #4 lore raw

PATCH 1/1 radix tree: lockless readside

Signature · 2 lines

-- 
SUSE Labs, Novell Inc.

Make radix tree lookups safe to be performed without locks.

Also introduce a lockfree gang_lookup_slot which will be used by a future patch.

lib/radix-tree.c +76 ~~-22~~

Index: linux-2.6/lib/radix-tree.c
===================================================================
@@ -45,6 +45,7 @@
 	((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
 
 struct radix_tree_node {
+	unsigned int	height;		/* Height from the bottom */
 	unsigned int	count;
 	void		*slots[RADIX_TREE_MAP_SIZE];
 	unsigned long	tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS];

@@ -196,6 +197,7 @@ static int radix_tree_extend(struct radi
 	}
 
 	do {
+		unsigned int newheight;
 		if (!(node = radix_tree_node_alloc(root)))
 			return -ENOMEM;

@@ -208,9 +210,13 @@ static int radix_tree_extend(struct radi
 				tag_set(node, tag, 0);
 		}
 
+		newheight = root->height+1;
+		node->height = newheight;
 		node->count = 1;
+		/* Make ->height visible before node visible via ->rnode */
+		smp_wmb();
 		root->rnode = node;
-		root->height++;
+		root->height = newheight;
 	} while (height > root->height);
 out:
 	return 0;

@@ -250,6 +256,9 @@ int radix_tree_insert(struct radix_tree_
 			/* Have to add a child node.  */
 			if (!(tmp = radix_tree_node_alloc(root)))
 				return -ENOMEM;
+			tmp->height = height;
+			/* Make ->height visible before node visible via slot */
+			smp_wmb();
 			*slot = tmp;
 			if (node)
 				node->count++;

@@ -282,12 +291,14 @@ static inline void **__lookup_slot(struc
 	unsigned int height, shift;
 	struct radix_tree_node **slot;
 
-	height = root->height;
+	if (root->rnode == NULL)
+		return NULL;
+	slot = &root->rnode;
+	height = (*slot)->height;
 	if (index > radix_tree_maxindex(height))
 		return NULL;
 
 	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
-	slot = &root->rnode;
 
 	while (height > 0) {
 		if (*slot == NULL)

@@ -491,21 +502,24 @@ EXPORT_SYMBOL(radix_tree_tag_get);
 #endif
 
 static unsigned int
-__lookup(struct radix_tree_root *root, void **results, unsigned long index,
+__lookup(struct radix_tree_root *root, void ***results, unsigned long index,
 	unsigned int max_items, unsigned long *next_index)
 {
+	unsigned long i;
 	unsigned int nr_found = 0;
 	unsigned int shift;
-	unsigned int height = root->height;
+	unsigned int height;
 	struct radix_tree_node *slot;
 
-	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 	slot = root->rnode;
+	if (!slot)
+		goto out;
+	height = slot->height;
+	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
 
-	while (height > 0) {
-		unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;
-
-		for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
+	for (;;) {
+		for (i = (index >> shift) & RADIX_TREE_MAP_MASK;
+						i < RADIX_TREE_MAP_SIZE; i++) {
 			if (slot->slots[i] != NULL)
 				break;
 			index &= ~((1UL << shift) - 1);

@@ -516,21 +530,23 @@ __lookup(struct radix_tree_root *root, v
 		if (i == RADIX_TREE_MAP_SIZE)
 			goto out;
 		height--;
-		if (height == 0) {	/* Bottom level: grab some items */
-			unsigned long j = index & RADIX_TREE_MAP_MASK;
-
-			for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
-				index++;
-				if (slot->slots[j]) {
-					results[nr_found++] = slot->slots[j];
-					if (nr_found == max_items)
-						goto out;
-				}
-			}
+		if (height == 0) {
+			/* Bottom level: grab some items */
+			break;
 		}
 		shift -= RADIX_TREE_MAP_SHIFT;
 		slot = slot->slots[i];
 	}
+
+	for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
+		index++;
+		if (slot->slots[i]) {
+			results[nr_found++] = &(slot->slots[i]);
+			if (nr_found == max_items)
+				goto out;
+		}
+	}
+
 out:
 	*next_index = index;
 	return nr_found;

@@ -558,6 +574,43 @@ radix_tree_gang_lookup(struct radix_tree
 	unsigned int ret = 0;
 
 	while (ret < max_items) {
+		unsigned int nr_found, i;
+		unsigned long next_index;	/* Index of next search */
+
+		if (cur_index > max_index)
+			break;
+		nr_found = __lookup(root, (void ***)results + ret, cur_index,
+					max_items - ret, &next_index);
+		for (i = 0; i < nr_found; i++)
+			results[ret + i] = *(((void ***)results)[ret + i]);
+		ret += nr_found;
+		if (next_index == 0)
+			break;
+		cur_index = next_index;
+	}
+	return ret;
+}
+EXPORT_SYMBOL(radix_tree_gang_lookup);
+
+/**
+ *	radix_tree_gang_lookup_slot - perform multiple lookup on a radix tree
+ *	@root:		radix tree root
+ *	@results:	where the results of the lookup are placed
+ *	@first_index:	start the lookup from this key
+ *	@max_items:	place up to this many items at *results
+ *
+ *	Same as radix_tree_gang_lookup, but returns an array of pointers
+ *	(slots) to the stored items instead of the items themselves.
+ */
+unsigned int
+radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
+			unsigned long first_index, unsigned int max_items)
+{
+	const unsigned long max_index = radix_tree_maxindex(root->height);
+	unsigned long cur_index = first_index;
+	unsigned int ret = 0;
+
+	while (ret < max_items) {
 		unsigned int nr_found;
 		unsigned long next_index;	/* Index of next search */

@@ -572,7 +625,8 @@ radix_tree_gang_lookup(struct radix_tree
 	}
 	return ret;
 }
-EXPORT_SYMBOL(radix_tree_gang_lookup);
+EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
+
 
 /*
  * FIXME: the two tag_get()s here should use find_next_bit() instead of

include/linux/radix-tree.h +3 -0

Index: linux-2.6/include/linux/radix-tree.h
===================================================================
@@ -51,6 +51,9 @@ void *radix_tree_delete(struct radix_tre
 unsigned int
 radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
 			unsigned long first_index, unsigned int max_items);
+unsigned int
+radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
+			unsigned long first_index, unsigned int max_items);
 int radix_tree_preload(int gfp_mask);
 void radix_tree_init(void);
 void *radix_tree_tag_set(struct radix_tree_root *root,

Nick Piggin

author

2005-06-27 06:34 UTC #5 lore raw

PATCH 1/1 mm: lockless pagecache lookups

Signature · 2 lines

-- 
SUSE Labs, Novell Inc.

Use the speculative get_page and the lockless radix tree lookups to introduce lockless page cache lookups (ie. no mapping->tree_lock).

The only atomicity changes this should introduce is the use of a non atomic pagevec lookup for truncate, however what atomicity guarantees there were are probably not too useful anyway.

mm/filemap.c +66 ~~-31~~

Index: linux-2.6/mm/filemap.c
===================================================================
@@ -378,18 +378,25 @@ int add_to_page_cache(struct page *page,
 	int error = radix_tree_preload(gfp_mask & ~__GFP_HIGHMEM);
 
 	if (error == 0) {
+		page_cache_get(page);
+		__SetPageLocked(page);
+		page->mapping = mapping;
+		page->index = offset;
+
 		write_lock_irq(&mapping->tree_lock);
 		error = radix_tree_insert(&mapping->page_tree, offset, page);
 		if (!error) {
-			page_cache_get(page);
-			SetPageLocked(page);
-			page->mapping = mapping;
-			page->index = offset;
 			mapping->nrpages++;
 			pagecache_acct(1);
 		}
 		write_unlock_irq(&mapping->tree_lock);
 		radix_tree_preload_end();
+
+		if (error) {
+			page->mapping = NULL;
+			__put_page(page);
+			__ClearPageLocked(page);
+		}
 	}
 	return error;
 }

@@ -499,13 +506,13 @@ EXPORT_SYMBOL(__lock_page);
  */
 struct page * find_get_page(struct address_space *mapping, unsigned long offset)
 {
-	struct page *page;
+	struct page **pagep;
+	struct page *page = NULL;
 
-	read_lock_irq(&mapping->tree_lock);
-	page = radix_tree_lookup(&mapping->page_tree, offset);
-	if (page)
-		page_cache_get(page);
-	read_unlock_irq(&mapping->tree_lock);
+	pagep = (struct page **)radix_tree_lookup_slot(&mapping->page_tree,
+									offset);
+	if (pagep)
+		page = page_cache_get_speculative(pagep);
 	return page;
 }

@@ -518,12 +525,24 @@ struct page *find_trylock_page(struct ad
 {
 	struct page *page;
 
-	read_lock_irq(&mapping->tree_lock);
-	page = radix_tree_lookup(&mapping->page_tree, offset);
-	if (page && TestSetPageLocked(page))
-		page = NULL;
-	read_unlock_irq(&mapping->tree_lock);
-	return page;
+	page = find_get_page(mapping, offset);
+	if (page) {
+		if (TestSetPageLocked(page))
+			goto out_failed;
+		/* Has the page been truncated before being locked? */
+		if (page->mapping != mapping || page->index != offset) {
+			unlock_page(page);
+			goto out_failed;
+		}
+
+		/* Silly interface requires us to drop the refcount */
+		__put_page(page);
+		return page;
+
+out_failed:
+		page_cache_release(page);
+	}
+	return NULL;
 }
 
 EXPORT_SYMBOL(find_trylock_page);

@@ -544,25 +563,17 @@ struct page *find_lock_page(struct addre
 {
 	struct page *page;
 
-	read_lock_irq(&mapping->tree_lock);
 repeat:
-	page = radix_tree_lookup(&mapping->page_tree, offset);
+	page = find_get_page(mapping, offset);
 	if (page) {
-		page_cache_get(page);
-		if (TestSetPageLocked(page)) {
-			read_unlock_irq(&mapping->tree_lock);
-			lock_page(page);
-			read_lock_irq(&mapping->tree_lock);
-
-			/* Has the page been truncated while we slept? */
-			if (page->mapping != mapping || page->index != offset) {
-				unlock_page(page);
-				page_cache_release(page);
-				goto repeat;
-			}
+		lock_page(page);
+		/* Has the page been truncated before being locked? */
+		if (page->mapping != mapping || page->index != offset) {
+			unlock_page(page);
+			page_cache_release(page);
+			goto repeat;
 		}
 	}
-	read_unlock_irq(&mapping->tree_lock);
 	return page;
 }

@@ -645,6 +656,30 @@ unsigned find_get_pages(struct address_s
 	return ret;
 }
 
+unsigned find_get_pages_nonatomic(struct address_space *mapping, pgoff_t start,
+			    unsigned int nr_pages, struct page **pages)
+{
+	unsigned int i;
+	unsigned int ret;
+	unsigned int ret2;
+
+	/*
+	 * We do some unsightly casting to use the array first for storing
+	 * pointers to the page pointers, and then for the pointers to
+	 * the pages themselves that the caller wants.
+	 */
+	ret = radix_tree_gang_lookup_slot(&mapping->page_tree,
+				(void ***)pages, start, nr_pages);
+	ret2 = 0;
+	for (i = 0; i < ret; i++) {
+		struct page *page;
+		page = page_cache_get_speculative(((struct page ***)pages)[i]);
+		if (page)
+			pages[ret2++] = page;
+	}
+	return ret2;
+}
+
 /*
  * Like find_get_pages, except we only return pages which are tagged with
  * `tag'.   We update *index to index the next page for the traversal.

mm/readahead.c +1 -4

Index: linux-2.6/mm/readahead.c
===================================================================
@@ -272,27 +272,24 @@ __do_page_cache_readahead(struct address
 	/*
 	 * Preallocate as many pages as we will need.
 	 */
-	read_lock_irq(&mapping->tree_lock);
 	for (page_idx = 0; page_idx < nr_to_read; page_idx++) {
 		unsigned long page_offset = offset + page_idx;
 		
 		if (page_offset > end_index)
 			break;
 
+		/* Don't need mapping->tree_lock - lookup can be racy */
 		page = radix_tree_lookup(&mapping->page_tree, page_offset);
 		if (page)
 			continue;
 
-		read_unlock_irq(&mapping->tree_lock);
 		page = page_cache_alloc_cold(mapping);
-		read_lock_irq(&mapping->tree_lock);
 		if (!page)
 			break;
 		page->index = page_offset;
 		list_add(&page->lru, &page_pool);
 		ret++;
 	}
-	read_unlock_irq(&mapping->tree_lock);
 
 	/*
 	 * Now start the IO.  We ignore I/O errors - if the page is not

mm/swap_state.c +11 -4

Index: linux-2.6/mm/swap_state.c
===================================================================
@@ -76,19 +76,26 @@ static int __add_to_swap_cache(struct pa
 	BUG_ON(PagePrivate(page));
 	error = radix_tree_preload(gfp_mask);
 	if (!error) {
+		page_cache_get(page);
+		SetPageLocked(page);
+		SetPageSwapCache(page);
+		page->private = entry.val;
+
 		write_lock_irq(&swapper_space.tree_lock);
 		error = radix_tree_insert(&swapper_space.page_tree,
 						entry.val, page);
 		if (!error) {
-			page_cache_get(page);
-			SetPageLocked(page);
-			SetPageSwapCache(page);
-			page->private = entry.val;
 			total_swapcache_pages++;
 			pagecache_acct(1);
 		}
 		write_unlock_irq(&swapper_space.tree_lock);
 		radix_tree_preload_end();
+
+		if (error) {
+			__put_page(page);
+			ClearPageLocked(page);
+			ClearPageSwapCache(page);
+		}
 	}
 	return error;
 }

include/linux/page-flags.h +7 ~~-10~~

Index: linux-2.6/include/linux/page-flags.h
===================================================================
@@ -167,16 +167,13 @@ extern void __mod_page_state(unsigned lo
 /*
  * Manipulation of page state flags
  */
-#define PageLocked(page)		\
-		test_bit(PG_locked, &(page)->flags)
-#define SetPageLocked(page)		\
-		set_bit(PG_locked, &(page)->flags)
-#define TestSetPageLocked(page)		\
-		test_and_set_bit(PG_locked, &(page)->flags)
-#define ClearPageLocked(page)		\
-		clear_bit(PG_locked, &(page)->flags)
-#define TestClearPageLocked(page)	\
-		test_and_clear_bit(PG_locked, &(page)->flags)
+#define PageLocked(page)	test_bit(PG_locked, &(page)->flags)
+#define SetPageLocked(page)	set_bit(PG_locked, &(page)->flags)
+#define __SetPageLocked(page)	__set_bit(PG_locked, &(page)->flags)
+#define TestSetPageLocked(page)	test_and_set_bit(PG_locked, &(page)->flags)
+#define ClearPageLocked(page)	clear_bit(PG_locked, &(page)->flags)
+#define __ClearPageLocked(page)	__clear_bit(PG_locked, &(page)->flags)
+#define TestClearPageLocked(page) test_and_clear_bit(PG_locked, &(page)->flags)
 
 #define PageError(page)		test_bit(PG_error, &(page)->flags)
 #define SetPageError(page)	set_bit(PG_error, &(page)->flags)

include/linux/pagemap.h +2 -0

Index: linux-2.6/include/linux/pagemap.h
===================================================================
@@ -108,6 +108,8 @@ extern struct page * find_or_create_page
 				unsigned long index, unsigned int gfp_mask);
 unsigned find_get_pages(struct address_space *mapping, pgoff_t start,
 			unsigned int nr_pages, struct page **pages);
+unsigned find_get_pages_nonatomic(struct address_space *mapping, pgoff_t start,
+			unsigned int nr_pages, struct page **pages);
 unsigned find_get_pages_tag(struct address_space *mapping, pgoff_t *index,
 			int tag, unsigned int nr_pages, struct page **pages);

include/linux/pagevec.h +2 -0

Index: linux-2.6/include/linux/pagevec.h
===================================================================
@@ -25,6 +25,8 @@ void __pagevec_lru_add_active(struct pag
 void pagevec_strip(struct pagevec *pvec);
 unsigned pagevec_lookup(struct pagevec *pvec, struct address_space *mapping,
 		pgoff_t start, unsigned nr_pages);
+unsigned pagevec_lookup_nonatomic(struct pagevec *pvec,
+	struct address_space *mapping, pgoff_t start, unsigned nr_pages);
 unsigned pagevec_lookup_tag(struct pagevec *pvec,
 		struct address_space *mapping, pgoff_t *index, int tag,
 		unsigned nr_pages);

mm/swap.c +13 -0

Index: linux-2.6/mm/swap.c
===================================================================
@@ -380,6 +380,19 @@ unsigned pagevec_lookup(struct pagevec *
 	return pagevec_count(pvec);
 }
 
+/**
+ * pagevec_lookup_nonatomic - non atomic pagevec_lookup
+ *
+ * This routine is non-atomic in that it may return blah.
+ */
+unsigned pagevec_lookup_nonatomic(struct pagevec *pvec,
+		struct address_space *mapping, pgoff_t start, unsigned nr_pages)
+{
+	pvec->nr = find_get_pages_nonatomic(mapping, start,
+					nr_pages, pvec->pages);
+	return pagevec_count(pvec);
+}
+
 unsigned pagevec_lookup_tag(struct pagevec *pvec, struct address_space *mapping,
 		pgoff_t *index, int tag, unsigned nr_pages)
 {

mm/truncate.c +3 -3

Index: linux-2.6/mm/truncate.c
===================================================================
@@ -126,7 +126,7 @@ void truncate_inode_pages(struct address
 
 	pagevec_init(&pvec, 0);
 	next = start;
-	while (pagevec_lookup(&pvec, mapping, next, PAGEVEC_SIZE)) {
+	while (pagevec_lookup_nonatomic(&pvec, mapping, next, PAGEVEC_SIZE)) {
 		for (i = 0; i < pagevec_count(&pvec); i++) {
 			struct page *page = pvec.pages[i];
 			pgoff_t page_index = page->index;

@@ -160,7 +160,7 @@ void truncate_inode_pages(struct address
 	next = start;
 	for ( ; ; ) {
 		cond_resched();
-		if (!pagevec_lookup(&pvec, mapping, next, PAGEVEC_SIZE)) {
+		if (!pagevec_lookup_nonatomic(&pvec, mapping, next, PAGEVEC_SIZE)) {
 			if (next == start)
 				break;
 			next = start;

@@ -206,7 +206,7 @@ unsigned long invalidate_mapping_pages(s
 
 	pagevec_init(&pvec, 0);
 	while (next <= end &&
-			pagevec_lookup(&pvec, mapping, next, PAGEVEC_SIZE)) {
+		pagevec_lookup_nonatomic(&pvec, mapping, next, PAGEVEC_SIZE)) {
 		for (i = 0; i < pagevec_count(&pvec); i++) {
 			struct page *page = pvec.pages[i];

mm/page-writeback.c +1 -0

Index: linux-2.6/mm/page-writeback.c
===================================================================
@@ -811,6 +811,7 @@ int mapping_tagged(struct address_space 
 	unsigned long flags;
 	int ret;
 
+	/* XXX: radix_tree_tagged is safe to run without the lock */
 	read_lock_irqsave(&mapping->tree_lock, flags);
 	ret = radix_tree_tagged(&mapping->page_tree, tag);
 	read_unlock_irqrestore(&mapping->tree_lock, flags);

mm/swapfile.c +2 -0

Index: linux-2.6/mm/swapfile.c
===================================================================
@@ -338,6 +338,7 @@ int remove_exclusive_swap_page(struct pa
 	retval = 0;
 	if (p->swap_map[swp_offset(entry)] == 1) {
 		/* Recheck the page count with the swapcache lock held.. */
+		SetPageFreeing(page);
 		write_lock_irq(&swapper_space.tree_lock);
 		if ((page_count(page) == 2) && !PageWriteback(page)) {
 			__delete_from_swap_cache(page);

@@ -345,6 +346,7 @@ int remove_exclusive_swap_page(struct pa
 			retval = 1;
 		}
 		write_unlock_irq(&swapper_space.tree_lock);
+		ClearPageFreeing(page);
 	}
 	swap_info_put(p);

Nick Piggin

author

2005-06-27 06:35 UTC #6 lore raw

PATCH 1/1 mm: spinlock tree_lock

Signature · 2 lines

-- 
SUSE Labs, Novell Inc.

With practially all the read locks gone from mapping->tree_lock, convert the lock from an rwlock back to a spinlock.

The remaining locks including the read locks mainly deal with IO submission and not the lookup fastpaths.

fs/buffer.c +2 -2

Index: linux-2.6/fs/buffer.c
===================================================================
@@ -875,7 +875,7 @@ int __set_page_dirty_buffers(struct page
 	spin_unlock(&mapping->private_lock);
 
 	if (!TestSetPageDirty(page)) {
-		write_lock_irq(&mapping->tree_lock);
+		spin_lock_irq(&mapping->tree_lock);
 		if (page->mapping) {	/* Race with truncate? */
 			if (mapping_cap_account_dirty(mapping))
 				inc_page_state(nr_dirty);

@@ -883,7 +883,7 @@ int __set_page_dirty_buffers(struct page
 						page_index(page),
 						PAGECACHE_TAG_DIRTY);
 		}
-		write_unlock_irq(&mapping->tree_lock);
+		spin_unlock_irq(&mapping->tree_lock);
 		__mark_inode_dirty(mapping->host, I_DIRTY_PAGES);
 	}

fs/inode.c +1 -1

Index: linux-2.6/fs/inode.c
===================================================================
@@ -194,7 +194,7 @@ void inode_init_once(struct inode *inode
 	sema_init(&inode->i_sem, 1);
 	init_rwsem(&inode->i_alloc_sem);
 	INIT_RADIX_TREE(&inode->i_data.page_tree, GFP_ATOMIC);
-	rwlock_init(&inode->i_data.tree_lock);
+	spin_lock_init(&inode->i_data.tree_lock);
 	spin_lock_init(&inode->i_data.i_mmap_lock);
 	INIT_LIST_HEAD(&inode->i_data.private_list);
 	spin_lock_init(&inode->i_data.private_lock);

include/linux/fs.h +1 -1

Index: linux-2.6/include/linux/fs.h
===================================================================
@@ -336,7 +336,7 @@ struct backing_dev_info;
 struct address_space {
 	struct inode		*host;		/* owner: inode, block_device */
 	struct radix_tree_root	page_tree;	/* radix tree of all pages */
-	rwlock_t		tree_lock;	/* and rwlock protecting it */
+	spinlock_t		tree_lock;	/* and lock protecting it */
 	unsigned int		i_mmap_writable;/* count VM_SHARED mappings */
 	struct prio_tree_root	i_mmap;		/* tree of private and shared mappings */
 	struct list_head	i_mmap_nonlinear;/*list VM_NONLINEAR mappings */

mm/filemap.c +8 -8

Index: linux-2.6/mm/filemap.c
===================================================================
@@ -120,9 +120,9 @@ void remove_from_page_cache(struct page 
 
 	BUG_ON(!PageLocked(page));
 
-	write_lock_irq(&mapping->tree_lock);
+	spin_lock_irq(&mapping->tree_lock);
 	__remove_from_page_cache(page);
-	write_unlock_irq(&mapping->tree_lock);
+	spin_unlock_irq(&mapping->tree_lock);
 }
 
 static int sync_page(void *word)

@@ -383,13 +383,13 @@ int add_to_page_cache(struct page *page,
 		page->mapping = mapping;
 		page->index = offset;
 
-		write_lock_irq(&mapping->tree_lock);
+		spin_lock_irq(&mapping->tree_lock);
 		error = radix_tree_insert(&mapping->page_tree, offset, page);
 		if (!error) {
 			mapping->nrpages++;
 			pagecache_acct(1);
 		}
-		write_unlock_irq(&mapping->tree_lock);
+		spin_unlock_irq(&mapping->tree_lock);
 		radix_tree_preload_end();
 
 		if (error) {

@@ -647,12 +647,12 @@ unsigned find_get_pages(struct address_s
 	unsigned int i;
 	unsigned int ret;
 
-	read_lock_irq(&mapping->tree_lock);
+	spin_lock_irq(&mapping->tree_lock);
 	ret = radix_tree_gang_lookup(&mapping->page_tree,
 				(void **)pages, start, nr_pages);
 	for (i = 0; i < ret; i++)
 		page_cache_get(pages[i]);
-	read_unlock_irq(&mapping->tree_lock);
+	spin_unlock_irq(&mapping->tree_lock);
 	return ret;
 }

@@ -690,14 +690,14 @@ unsigned find_get_pages_tag(struct addre
 	unsigned int i;
 	unsigned int ret;
 
-	read_lock_irq(&mapping->tree_lock);
+	spin_lock_irq(&mapping->tree_lock);
 	ret = radix_tree_gang_lookup_tag(&mapping->page_tree,
 				(void **)pages, *index, nr_pages, tag);
 	for (i = 0; i < ret; i++)
 		page_cache_get(pages[i]);
 	if (ret)
 		*index = pages[ret - 1]->index + 1;
-	read_unlock_irq(&mapping->tree_lock);
+	spin_unlock_irq(&mapping->tree_lock);
 	return ret;
 }

mm/swap_state.c +5 -5

Index: linux-2.6/mm/swap_state.c
===================================================================
@@ -35,7 +35,7 @@ static struct backing_dev_info swap_back
 
 struct address_space swapper_space = {
 	.page_tree	= RADIX_TREE_INIT(GFP_ATOMIC|__GFP_NOWARN),
-	.tree_lock	= RW_LOCK_UNLOCKED,
+	.tree_lock	= SPIN_LOCK_UNLOCKED,
 	.a_ops		= &swap_aops,
 	.i_mmap_nonlinear = LIST_HEAD_INIT(swapper_space.i_mmap_nonlinear),
 	.backing_dev_info = &swap_backing_dev_info,

@@ -81,14 +81,14 @@ static int __add_to_swap_cache(struct pa
 		SetPageSwapCache(page);
 		page->private = entry.val;
 
-		write_lock_irq(&swapper_space.tree_lock);
+		spin_lock_irq(&swapper_space.tree_lock);
 		error = radix_tree_insert(&swapper_space.page_tree,
 						entry.val, page);
 		if (!error) {
 			total_swapcache_pages++;
 			pagecache_acct(1);
 		}
-		write_unlock_irq(&swapper_space.tree_lock);
+		spin_unlock_irq(&swapper_space.tree_lock);
 		radix_tree_preload_end();
 
 		if (error) {

@@ -210,9 +210,9 @@ void delete_from_swap_cache(struct page 
   
 	entry.val = page->private;
 
-	write_lock_irq(&swapper_space.tree_lock);
+	spin_lock_irq(&swapper_space.tree_lock);
 	__delete_from_swap_cache(page);
-	write_unlock_irq(&swapper_space.tree_lock);
+	spin_unlock_irq(&swapper_space.tree_lock);
 
 	swap_free(entry);
 	page_cache_release(page);

mm/swapfile.c +2 -2

Index: linux-2.6/mm/swapfile.c
===================================================================
@@ -339,13 +339,13 @@ int remove_exclusive_swap_page(struct pa
 	if (p->swap_map[swp_offset(entry)] == 1) {
 		/* Recheck the page count with the swapcache lock held.. */
 		SetPageFreeing(page);
-		write_lock_irq(&swapper_space.tree_lock);
+		spin_lock_irq(&swapper_space.tree_lock);
 		if ((page_count(page) == 2) && !PageWriteback(page)) {
 			__delete_from_swap_cache(page);
 			SetPageDirty(page);
 			retval = 1;
 		}
-		write_unlock_irq(&swapper_space.tree_lock);
+		spin_unlock_irq(&swapper_space.tree_lock);
 		ClearPageFreeing(page);
 	}
 	swap_info_put(p);

mm/truncate.c +3 -3

Index: linux-2.6/mm/truncate.c
===================================================================
@@ -76,15 +76,15 @@ invalidate_complete_page(struct address_
 	if (PagePrivate(page) && !try_to_release_page(page, 0))
 		return 0;
 
-	write_lock_irq(&mapping->tree_lock);
+	spin_lock_irq(&mapping->tree_lock);
 	if (PageDirty(page)) {
-		write_unlock_irq(&mapping->tree_lock);
+		spin_unlock_irq(&mapping->tree_lock);
 		return 0;
 	}
 
 	BUG_ON(PagePrivate(page));
 	__remove_from_page_cache(page);
-	write_unlock_irq(&mapping->tree_lock);
+	spin_unlock_irq(&mapping->tree_lock);
 	ClearPageUptodate(page);
 	page_cache_release(page);	/* pagecache ref */
 	return 1;

mm/vmscan.c +4 -4

Index: linux-2.6/mm/vmscan.c
===================================================================
@@ -505,7 +505,7 @@ static int shrink_list(struct list_head 
 			goto keep_locked;	/* truncate got there first */
 
 		SetPageFreeing(page);
-		write_lock_irq(&mapping->tree_lock);
+		spin_lock_irq(&mapping->tree_lock);
 
 		/*
 		 * The non-racy check for busy page.  It is critical to check

@@ -513,7 +513,7 @@ static int shrink_list(struct list_head 
 		 * not in use by anybody. 	(pagecache + us == 2)
 		 */
 		if (page_count(page) != 2 || PageDirty(page)) {
-			write_unlock_irq(&mapping->tree_lock);
+			spin_unlock_irq(&mapping->tree_lock);
 			ClearPageFreeing(page);
 			goto keep_locked;
 		}

@@ -522,7 +522,7 @@ static int shrink_list(struct list_head 
 		if (PageSwapCache(page)) {
 			swp_entry_t swap = { .val = page->private };
 			__delete_from_swap_cache(page);
-			write_unlock_irq(&mapping->tree_lock);
+			spin_unlock_irq(&mapping->tree_lock);
 			swap_free(swap);
 			__put_page(page);	/* The pagecache ref */
 			goto free_it;

@@ -530,7 +530,7 @@ static int shrink_list(struct list_head 
 #endif /* CONFIG_SWAP */
 
 		__remove_from_page_cache(page);
-		write_unlock_irq(&mapping->tree_lock);
+		spin_unlock_irq(&mapping->tree_lock);
 		__put_page(page);
 
 free_it:

mm/page-writeback.c +11 ~~-11~~

Index: linux-2.6/mm/page-writeback.c
===================================================================
@@ -623,7 +623,7 @@ int __set_page_dirty_nobuffers(struct pa
 		struct address_space *mapping2;
 
 		if (mapping) {
-			write_lock_irq(&mapping->tree_lock);
+			spin_lock_irq(&mapping->tree_lock);
 			mapping2 = page_mapping(page);
 			if (mapping2) { /* Race with truncate? */
 				BUG_ON(mapping2 != mapping);

@@ -632,7 +632,7 @@ int __set_page_dirty_nobuffers(struct pa
 				radix_tree_tag_set(&mapping->page_tree,
 					page_index(page), PAGECACHE_TAG_DIRTY);
 			}
-			write_unlock_irq(&mapping->tree_lock);
+			spin_unlock_irq(&mapping->tree_lock);
 			if (mapping->host) {
 				/* !PageAnon && !swapper_space */
 				__mark_inode_dirty(mapping->host,

@@ -707,17 +707,17 @@ int test_clear_page_dirty(struct page *p
 	unsigned long flags;
 
 	if (mapping) {
-		write_lock_irqsave(&mapping->tree_lock, flags);
+		spin_lock_irqsave(&mapping->tree_lock, flags);
 		if (TestClearPageDirty(page)) {
 			radix_tree_tag_clear(&mapping->page_tree,
 						page_index(page),
 						PAGECACHE_TAG_DIRTY);
-			write_unlock_irqrestore(&mapping->tree_lock, flags);
+			spin_unlock_irqrestore(&mapping->tree_lock, flags);
 			if (mapping_cap_account_dirty(mapping))
 				dec_page_state(nr_dirty);
 			return 1;
 		}
-		write_unlock_irqrestore(&mapping->tree_lock, flags);
+		spin_unlock_irqrestore(&mapping->tree_lock, flags);
 		return 0;
 	}
 	return TestClearPageDirty(page);

@@ -762,13 +762,13 @@ int test_clear_page_writeback(struct pag
 	if (mapping) {
 		unsigned long flags;
 
-		write_lock_irqsave(&mapping->tree_lock, flags);
+		spin_lock_irqsave(&mapping->tree_lock, flags);
 		ret = TestClearPageWriteback(page);
 		if (ret)
 			radix_tree_tag_clear(&mapping->page_tree,
 						page_index(page),
 						PAGECACHE_TAG_WRITEBACK);
-		write_unlock_irqrestore(&mapping->tree_lock, flags);
+		spin_unlock_irqrestore(&mapping->tree_lock, flags);
 	} else {
 		ret = TestClearPageWriteback(page);
 	}

@@ -783,7 +783,7 @@ int test_set_page_writeback(struct page 
 	if (mapping) {
 		unsigned long flags;
 
-		write_lock_irqsave(&mapping->tree_lock, flags);
+		spin_lock_irqsave(&mapping->tree_lock, flags);
 		ret = TestSetPageWriteback(page);
 		if (!ret)
 			radix_tree_tag_set(&mapping->page_tree,

@@ -793,7 +793,7 @@ int test_set_page_writeback(struct page 
 			radix_tree_tag_clear(&mapping->page_tree,
 						page_index(page),
 						PAGECACHE_TAG_DIRTY);
-		write_unlock_irqrestore(&mapping->tree_lock, flags);
+		spin_unlock_irqrestore(&mapping->tree_lock, flags);
 	} else {
 		ret = TestSetPageWriteback(page);
 	}

@@ -812,9 +812,9 @@ int mapping_tagged(struct address_space 
 	int ret;
 
 	/* XXX: radix_tree_tagged is safe to run without the lock */
-	read_lock_irqsave(&mapping->tree_lock, flags);
+	spin_lock_irqsave(&mapping->tree_lock, flags);
 	ret = radix_tree_tagged(&mapping->page_tree, tag);
-	read_unlock_irqrestore(&mapping->tree_lock, flags);
+	spin_unlock_irqrestore(&mapping->tree_lock, flags);
 	return ret;
 }
 EXPORT_SYMBOL(mapping_tagged);

drivers/mtd/devices/block2mtd.c +4 -4

Index: linux-2.6/drivers/mtd/devices/block2mtd.c
===================================================================
@@ -59,7 +59,7 @@ void cache_readahead(struct address_spac
 
 	end_index = ((isize - 1) >> PAGE_CACHE_SHIFT);
 
-	read_lock_irq(&mapping->tree_lock);
+	spin_lock_irq(&mapping->tree_lock);
 	for (i = 0; i < PAGE_READAHEAD; i++) {
 		pagei = index + i;
 		if (pagei > end_index) {

@@ -71,16 +71,16 @@ void cache_readahead(struct address_spac
 			break;
 		if (page)
 			continue;
-		read_unlock_irq(&mapping->tree_lock);
+		spin_unlock_irq(&mapping->tree_lock);
 		page = page_cache_alloc_cold(mapping);
-		read_lock_irq(&mapping->tree_lock);
+		spin_lock_irq(&mapping->tree_lock);
 		if (!page)
 			break;
 		page->index = pagei;
 		list_add(&page->lru, &page_pool);
 		ret++;
 	}
-	read_unlock_irq(&mapping->tree_lock);
+	spin_unlock_irq(&mapping->tree_lock);
 	if (ret)
 		read_cache_pages(mapping, &page_pool, filler, NULL);
 }

include/asm-arm/cacheflush.h +2 -2

Index: linux-2.6/include/asm-arm/cacheflush.h
===================================================================
@@ -315,9 +315,9 @@ flush_cache_page(struct vm_area_struct *
 extern void flush_dcache_page(struct page *);
 
 #define flush_dcache_mmap_lock(mapping) \
-	write_lock_irq(&(mapping)->tree_lock)
+	spin_lock_irq(&(mapping)->tree_lock)
 #define flush_dcache_mmap_unlock(mapping) \
-	write_unlock_irq(&(mapping)->tree_lock)
+	spin_unlock_irq(&(mapping)->tree_lock)
 
 #define flush_icache_user_range(vma,page,addr,len) \
 	flush_dcache_page(page)

include/asm-parisc/cacheflush.h +2 -2

Index: linux-2.6/include/asm-parisc/cacheflush.h
===================================================================
@@ -57,9 +57,9 @@ flush_user_icache_range(unsigned long st
 extern void flush_dcache_page(struct page *page);
 
 #define flush_dcache_mmap_lock(mapping) \
-	write_lock_irq(&(mapping)->tree_lock)
+	spin_lock_irq(&(mapping)->tree_lock)
 #define flush_dcache_mmap_unlock(mapping) \
-	write_unlock_irq(&(mapping)->tree_lock)
+	spin_unlock_irq(&(mapping)->tree_lock)
 
 #define flush_icache_page(vma,page)	do { flush_kernel_dcache_page(page_address(page)); flush_kernel_icache_page(page_address(page)); } while (0)

William Lee Irwin III

2005-06-27 14:12 UTC #7 lore raw

Re: [patch 2] mm: speculative get_page

In reply to Nick Piggin

Quoted 4 lines · Nick Piggin

include/linux/pagemap.h +4 -0

+static inline struct page *page_cache_get_speculative(struct page **pagep)
+{
+	struct page *page;
+

include/linux/pagemap.h static inline void mapping_set_gfp_mask( · line 66

Quoted 10 lines

include/linux/pagemap.h +10 -0

+	preempt_disable();
+	page = *pagep;
+	if (!page)
+		goto out_failed;
+
+	if (unlikely(get_page_testone(page))) {
+		/* Picked up a freed page */
+		__put_page(page);
+		goto out_failed;
+	}

So you pick up 0->1 refcount transitions.

include/linux/pagemap.h static inline void mapping_set_gfp_mask( · line 74

Quoted 8 lines · Nick Piggin

include/linux/pagemap.h +8 -0

+	/*
+	 * preempt can really be enabled here (only needs to be disabled
+	 * because page allocation can spin on the elevated refcount, but
+	 * we don't want to hold a reference on an unrelated page for too
+	 * long, so keep preempt off until we know we have the right page
+	 */
+
+	if (unlikely(PageFreeing(page)) ||

SetPageFreeing is only done in shrink_list(), so other pages in the buddy bitmaps and/or pagecache pages freed by other methods may not be found by this. There's also likely trouble with higher-order pages.

include/linux/pagemap.h static inline void mapping_set_gfp_mask( · line 87

Quoted 13 lines · Nick Piggin

include/linux/pagemap.h +13 -0

+			unlikely(page != *pagep)) {
+		/* Picked up a page being freed, or one that's been reused */
+		put_page(page);
+		goto out_failed;
+	}
+	preempt_enable();
+
+	return page;
+
+out_failed:
+	preempt_enable();
+	return NULL;
+}

page != *pagep won't be reliably tripped unless the pagecache modification has the appropriate memory barriers.

The lockless radix tree lookups are a harder problem than this, and the implementation didn't look promising. I have other problems to deal with so I'm not going to go very far into this.

While I agree that locklessness is the right direction for the pagecache to go, this RFC seems to have too far to go to use it to conclude anything about the subject.

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

Nick Piggin

author

2005-06-28 00:03 UTC #8 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 11 lines · William Lee Irwin III

Quoted 9 lines · Nick Piggin

include/linux/pagemap.h +9 -0

+static inline struct page *page_cache_get_speculative(struct page **pagep)
+{
+	struct page *page;
+
+	preempt_disable();
+	page = *pagep;
+	if (!page)
+		goto out_failed;
+

Quoted 9 lines

include/linux/pagemap.h static inline void mapping_set_gfp_mask( · line 66
Quoted 5 lines
include/linux/pagemap.h +5 -0
+	if (unlikely(get_page_testone(page))) {
+		/* Picked up a freed page */
+		__put_page(page);
+		goto out_failed;
+	}
So you pick up 0->1 refcount transitions.

Yep ie. a page that's freed or being freed.

Quoted 15 lines · Nick Piggin

include/linux/pagemap.h static inline void mapping_set_gfp_mask( · line 74
Quoted 9 lines
include/linux/pagemap.h +8 -0
+	/*
+	 * preempt can really be enabled here (only needs to be disabled
+	 * because page allocation can spin on the elevated refcount, but
+	 * we don't want to hold a reference on an unrelated page for too
+	 * long, so keep preempt off until we know we have the right page
+	 */
+
+	if (unlikely(PageFreeing(page)) ||
SetPageFreeing is only done in shrink_list(), so other pages in the buddy bitmaps and/or pagecache pages freed by other methods may not

It is also done by remove_exclusive_swap_page, although that hunk leaked into a later patch (#5), sorry.

Other methods (eg truncate) don't seem to have an atomicity guarantee anyway - ie. it is valid to pick up a reference on a page that is just about to get truncated. PageFreeing is only used when some code is making an assumption about the number of users of the page.

Quoted 2 lines

be found by this. There's also likely trouble with higher-order pages.

There isn't because higher order pages aren't used for pagecache.

Quoted 12 lines · Nick Piggin

Quoted 10 lines

include/linux/pagemap.h +9 -0

+			unlikely(page != *pagep)) {
+		/* Picked up a page being freed, or one that's been reused */
+		put_page(page);
+		goto out_failed;
+	}
+	preempt_enable();
+
+	return page;
+

Quoted 9 lines

include/linux/pagemap.h static inline void mapping_set_gfp_mask( · line 87
Quoted 4 lines
include/linux/pagemap.h +4 -0
+out_failed:
+	preempt_enable();
+	return NULL;
+}
page != *pagep won't be reliably tripped unless the pagecache modification has the appropriate memory barriers.

There are appropriate memory barriers: the radix tree is modified uner the rwlock/spinlock, and this function has a memory barrier before testing page != *pagep.

Quoted 4 lines

The lockless radix tree lookups are a harder problem than this, and the implementation didn't look promising. I have other problems to deal with so I'm not going to go very far into this.

What's wrong with the lockless radix tree lookups?

Quoted 4 lines

While I agree that locklessness is the right direction for the pagecache to go, this RFC seems to have too far to go to use it to conclude anything about the subject.

You don't seem to have looked enough to conclude anything about it.

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Nick Piggin

author

2005-06-28 00:56 UTC #9 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 25 lines · Nick Piggin

Quoted 13 lines · William Lee Irwin III
Quoted 11 lines · Nick Piggin
+static inline struct page *page_cache_get_speculative(struct page **pagep)
include/linux/pagemap.h +9 -0
+{
+    struct page *page;
+
+    preempt_disable();
+    page = *pagep;
+    if (!page)
+        goto out_failed;
+
+    if (unlikely(get_page_testone(page))) {
Quoted 9 lines
include/linux/pagemap.h static inline void mapping_set_gfp_mask( · line 66
Quoted 4 lines
include/linux/pagemap.h +4 -0
+        /* Picked up a freed page */
+        __put_page(page);
+        goto out_failed;
+    }
So you pick up 0->1 refcount transitions.

Quoted 2 lines

Yep ie. a page that's freed or being freed.

Oh, one thing it does need is a check for PageFree(), so it also picks up 1->2 and other transitions without freeing the free page if the put()s are done out of order. Maybe that's what you were alluding to.

I'll add that.

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

William Lee Irwin III

2005-06-28 01:22 UTC #10 lore raw

Re: [patch 2] mm: speculative get_page

In reply to Nick Piggin

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines
SetPageFreeing is only done in shrink_list(), so other pages in the buddy bitmaps and/or pagecache pages freed by other methods may not

Quoted 6 lines · Nick Piggin

It is also done by remove_exclusive_swap_page, although that hunk leaked into a later patch (#5), sorry.
Other methods (eg truncate) don't seem to have an atomicity guarantee anyway - ie. it is valid to pick up a reference on a page that is just about to get truncated. PageFreeing is only used when some code is making an assumption about the number of users of the page.

tmpfs

Quoted 1 line · William Lee Irwin III

Quoted 1 line
be found by this. There's also likely trouble with higher-order pages.

Quoted 1 line · Nick Piggin

There isn't because higher order pages aren't used for pagecache.

hugetlbfs

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines
page != *pagep won't be reliably tripped unless the pagecache modification has the appropriate memory barriers.

Quoted 3 lines · Nick Piggin

There are appropriate memory barriers: the radix tree is modified uner the rwlock/spinlock, and this function has a memory barrier before testing page != *pagep.

Someone else deal with this (paulus? anton? other arch maintainers?).

Quoted 3 lines · William Lee Irwin III

Quoted 3 lines
The lockless radix tree lookups are a harder problem than this, and the implementation didn't look promising. I have other problems to deal with so I'm not going to go very far into this.

Quoted 1 line · Nick Piggin

What's wrong with the lockless radix tree lookups?

The above is as much as I wanted to go into it. I need to direct my capacity for the grunt work of devising adversary arguments elsewhere.

Quoted 3 lines · William Lee Irwin III

Quoted 3 lines
While I agree that locklessness is the right direction for the pagecache to go, this RFC seems to have too far to go to use it to conclude anything about the subject.

Quoted 1 line · Nick Piggin

You don't seem to have looked enough to conclude anything about it.

You requested comments. I made some.

Anyhow, my review has not been comprehensive. I stopped after the first few things I found that needed fixing. If others could deal with the rest of this, I'd be much obliged.

Nick Piggin

author

2005-06-28 01:42 UTC #11 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 16 lines · William Lee Irwin III

Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
SetPageFreeing is only done in shrink_list(), so other pages in the buddy bitmaps and/or pagecache pages freed by other methods may not
Quoted 6 lines · Nick Piggin
It is also done by remove_exclusive_swap_page, although that hunk leaked into a later patch (#5), sorry.
Other methods (eg truncate) don't seem to have an atomicity guarantee anyway - ie. it is valid to pick up a reference on a page that is just about to get truncated. PageFreeing is only used when some code is making an assumption about the number of users of the page.

Quoted 2 lines

tmpfs

Well it switches between page and swap cache, but it seems to just use the normal pagecache / swapcache functions for that. It could be that I've got a big hole somewhere, but so far I don't think you've pointed oen out.

Quoted 6 lines

Quoted 1 line · William Lee Irwin III
Quoted 1 line
be found by this. There's also likely trouble with higher-order pages.

Quoted 7 lines

Quoted 1 line · Nick Piggin
There isn't because higher order pages aren't used for pagecache.
hugetlbfs

Well what's the trouble with it?

Quoted 7 lines

Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
page != *pagep won't be reliably tripped unless the pagecache modification has the appropriate memory barriers.

Quoted 9 lines

Quoted 3 lines · Nick Piggin
There are appropriate memory barriers: the radix tree is modified uner the rwlock/spinlock, and this function has a memory barrier before testing page != *pagep.
Someone else deal with this (paulus? anton? other arch maintainers?).

I know what a memory barrier is and does, so you said the necessary memory barriers aren't in place, so can you deal with it?

Quoted 8 lines

Quoted 3 lines · William Lee Irwin III
Quoted 3 lines
The lockless radix tree lookups are a harder problem than this, and the implementation didn't look promising. I have other problems to deal with so I'm not going to go very far into this.

Quoted 8 lines

Quoted 1 line · Nick Piggin
What's wrong with the lockless radix tree lookups?
The above is as much as I wanted to go into it. I need to direct my capacity for the grunt work of devising adversary arguments elsewhere.

I don't think there is anything wrong with it. I would be very keen to see real adversary arguments elsewhere though.

Quoted 8 lines

Quoted 3 lines · William Lee Irwin III
Quoted 3 lines
While I agree that locklessness is the right direction for the pagecache to go, this RFC seems to have too far to go to use it to conclude anything about the subject.

Quoted 7 lines

Quoted 1 line · Nick Piggin
You don't seem to have looked enough to conclude anything about it.
You requested comments. I made some.

Well yeah thanks, you did point out a thinko I made, and that was very helpful and I value any time you spend looking at it. But just saying "this is wrong, that won't work, that's crap, ergo the concept is useless" without finding anything specifically wrong is not very constructive.

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

William Lee Irwin III

2005-06-28 04:06 UTC #12 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 1 line · William Lee Irwin III

Quoted 1 line
tmpfs

Quoted 4 lines · Nick Piggin

Well it switches between page and swap cache, but it seems to just use the normal pagecache / swapcache functions for that. It could be that I've got a big hole somewhere, but so far I don't think you've pointed oen out.

Its radix tree movement bypasses the page allocator.

Quoted 1 line · William Lee Irwin III

Quoted 1 line
hugetlbfs

Quoted 1 line · Nick Piggin

Well what's the trouble with it?

hugetlb reallocation doesn't go through the page allocator either.

Quoted 1 line · William Lee Irwin III

Quoted 1 line
Someone else deal with this (paulus? anton? other arch maintainers?).

Quoted 3 lines · Nick Piggin

I know what a memory barrier is and does, so you said the necessary memory barriers aren't in place, so can you deal with it?

spin_unlock() does not imply a memory barrier.

Quoted 2 lines · William Lee Irwin III

Quoted 2 lines
The above is as much as I wanted to go into it. I need to direct my capacity for the grunt work of devising adversary arguments elsewhere.

Quoted 2 lines · Nick Piggin

I don't think there is anything wrong with it. I would be very keen to see real adversary arguments elsewhere though.

They take time to construct.

Quoted 1 line · William Lee Irwin III

Quoted 1 line
You requested comments. I made some.

Quoted 5 lines · Nick Piggin

Well yeah thanks, you did point out a thinko I made, and that was very helpful and I value any time you spend looking at it. But just saying "this is wrong, that won't work, that's crap, ergo the concept is useless" without finding anything specifically wrong is not very constructive.

I said nothing of that kind, and I did point out specific things.

The limitation of time/effort is directly related to the nature of the responses.

Nick Piggin

author

2005-06-28 04:50 UTC #13 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 11 lines · William Lee Irwin III

Quoted 5 lines · Nick Piggin
Well it switches between page and swap cache, but it seems to just use the normal pagecache / swapcache functions for that. It could be that I've got a big hole somewhere, but so far I don't think you've pointed oen out.
Its radix tree movement bypasses the page allocator.

That should be fine. Net result is the page has been looked up. What kind of atomicity did you imagine the locked find_get_page provides that I haven't?

Quoted 9 lines · Nick Piggin

Quoted 3 lines
Well what's the trouble with it?
hugetlb reallocation doesn't go through the page allocator either.

Ditto. Net result is that the page has been looked up. The speculative get page will recheck that it is in the radix tree after taking a reference, and if so then it assumes that reference to be valid.

What is the hangup with the page allocator?

Quoted 10 lines · Nick Piggin

Quoted 5 lines
I know what a memory barrier is and does, so you said the necessary memory barriers aren't in place, so can you deal with it?
spin_unlock() does not imply a memory barrier.

Intriguing...

Quoted 7 lines

Quoted 3 lines · William Lee Irwin III
Quoted 3 lines
The above is as much as I wanted to go into it. I need to direct my capacity for the grunt work of devising adversary arguments elsewhere.

Quoted 9 lines

Quoted 3 lines · Nick Piggin
I don't think there is anything wrong with it. I would be very keen to see real adversary arguments elsewhere though.
They take time to construct.

I can imagine. I don't think I've seen one yet.

Quoted 8 lines

Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
You requested comments. I made some.
On Tue, Jun 28, 2005 at 11:42:16AM +1000, Nick Piggin wrote:

Quoted 10 lines

Quoted 6 lines
Well yeah thanks, you did point out a thinko I made, and that was very helpful and I value any time you spend looking at it. But just saying "this is wrong, that won't work, that's crap, ergo the concept is useless" without finding anything specifically wrong is not very constructive.
I said nothing of that kind, and I did point out specific things.

You said "this RFC seems to have too far to go to use it to conclude anything about the subject", after failing to find any holes in the actual implementation.

And (parahprasing) "this needs memory barriers but I won't say where or why, somebody else deal with it" doesn't count as a specific thing.

Send instant messages to your online friends http://au.messenger.yahoo.com -- 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>

David S. Miller

2005-06-28 05:08 UTC #14 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 8 lines

Quoted 4 lines · William Lee Irwin III
On Tue, Jun 28, 2005 at 11:42:16AM +1000, Nick Piggin wrote:
spin_unlock() does not imply a memory barrier.
Intriguing...

BTW, I disagree with this assertion. spin_unlock() does imply a memory barrier.

All memory operations before the release of the lock must execute before the lock release memory operation is globally visible. --
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>

Nick Piggin

author

2005-06-28 05:34 UTC #15 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 13 lines · David S. Miller

From: Nick Piggin <[email protected]>
Subject: Re: [patch 2] mm: speculative get_page
Date: Tue, 28 Jun 2005 14:50:31 +1000
Quoted 8 lines
Quoted 5 lines · William Lee Irwin III
On Tue, Jun 28, 2005 at 11:42:16AM +1000, Nick Piggin wrote:
spin_unlock() does not imply a memory barrier.

Quoted 9 lines

Quoted 2 lines
Intriguing...
BTW, I disagree with this assertion. spin_unlock() does imply a memory barrier.
All memory operations before the release of the lock must execute before the lock release memory operation is globally visible.

Yes, it appears that way from looking at a sample set of arch code too (ie. those without strictly ordered stores put an explicit barrier there).

I've always understood spin_unlock to imply a barrier.

William Lee Irwin III

2005-06-28 14:19 UTC #16 lore raw

Re: [patch 2] mm: speculative get_page

In reply to David S. Miller

Quoted 4 lines · David S. Miller

BTW, I disagree with this assertion. spin_unlock() does imply a memory barrier.
All memory operations before the release of the lock must execute before the lock release memory operation is globally visible.

The affected architectures have only recently changed in this regard. ppc64 was the most notable case, where it had a barrier for MMIO (eieio) but not a general memory barrier. PA-RISC likewise formerly had no such barrier and was a more normal case, with no barrier whatsoever.

Both have since been altered, ppc64 acquiring a heavyweight sync (arch nomenclature), and PA-RISC acquiring 2 memory barriers.

Nick Piggin

author

2005-06-28 15:43 UTC #17 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 8 lines · William Lee Irwin III

Quoted 4 lines · David S. Miller
BTW, I disagree with this assertion. spin_unlock() does imply a memory barrier.
All memory operations before the release of the lock must execute before the lock release memory operation is globally visible.

Quoted 8 lines

The affected architectures have only recently changed in this regard. ppc64 was the most notable case, where it had a barrier for MMIO (eieio) but not a general memory barrier. PA-RISC likewise formerly had no such barrier and was a more normal case, with no barrier whatsoever.
Both have since been altered, ppc64 acquiring a heavyweight sync (arch nomenclature), and PA-RISC acquiring 2 memory barriers.

Parisc looks like it's doing the extra memory barrier to "be safe" :P

Re the ppc64 chageset: It looks to me like lwsync is the lightweight sync, and eieio is just referred to as the lightER (than sync) weight sync. What's more, it looks like eieio does order stores to system memory and is not just an MMIO barrier.

But nit picking aside, is it true that we need a load barrier before unlock? (store barrier I agree with) The ppc64 changeset in question indicates yes, but I can't quite work out why. There are noises in the archives about this, but I didn't pinpoint a conclusion...

Christoph Lameter

2005-06-28 17:01 UTC #18 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 4 lines · Nick Piggin

But nit picking aside, is it true that we need a load barrier before unlock? (store barrier I agree with) The ppc64 changeset in question indicates yes, but I can't quite work out why. There are noises in the archives about this, but I didn't pinpoint a conclusion...

A spinlock may be used to read a consistent set of variables. If load operations would be moved below the spin_unlock then one may get values that have been updated after another process acquired the spinlock.

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

Nick Piggin

author

2005-06-28 23:10 UTC #19 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 9 lines · Christoph Lameter

Quoted 4 lines · Nick Piggin
But nit picking aside, is it true that we need a load barrier before unlock? (store barrier I agree with) The ppc64 changeset in question indicates yes, but I can't quite work out why. There are noises in the archives about this, but I didn't pinpoint a conclusion...

Quoted 5 lines

A spinlock may be used to read a consistent set of variables. If load operations would be moved below the spin_unlock then one may get values that have been updated after another process acquired the spinlock.

Of course, thanks. I was only thinking of the case where loads were moved from the unlocked into the locked section.

Jesse Barnes

2005-06-28 21:32 UTC #20 lore raw

Re: [patch 2] mm: speculative get_page

In reply to David S. Miller

Quoted 9 lines · David S. Miller

From: Nick Piggin <[email protected]>
Subject: Re: [patch 2] mm: speculative get_page
Date: Tue, 28 Jun 2005 14:50:31 +1000
Quoted 5 lines
Quoted 3 lines · William Lee Irwin III
On Tue, Jun 28, 2005 at 11:42:16AM +1000, Nick Piggin wrote:
spin_unlock() does not imply a memory barrier.

Quoted 7 lines

Quoted 1 line
Intriguing...
BTW, I disagree with this assertion. spin_unlock() does imply a memory barrier.
All memory operations before the release of the lock must execute before the lock release memory operation is globally visible.

On ia64 at least, the unlock is only a one way barrier. The store to realease the lock uses release semantics (since the lock is declared volatile), which implies that prior stores are visible before the unlock occurs, but subsequent accesses can 'float up' above the unlock. See http://www.gelato.unsw.edu.au/linux-ia64/0304/5122.html for some more details.

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

Christoph Lameter

2005-06-28 22:17 UTC #21 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 6 lines · Jesse Barnes

On ia64 at least, the unlock is only a one way barrier. The store to realease the lock uses release semantics (since the lock is declared volatile), which implies that prior stores are visible before the unlock occurs, but subsequent accesses can 'float up' above the unlock. See http://www.gelato.unsw.edu.au/linux-ia64/0304/5122.html for some more details.

The manual talks about "accesses" not stores. So this applies to loads and stores. Subsequent accesses can float up but only accesses prior to the instruction with release semantics (like an unlock) are guaranteed to be visible.
--
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>

Andy Whitcroft

2005-06-28 12:45 UTC #22 lore raw

Re: [patch 2] mm: speculative get_page

In reply to Nick Piggin

Quoted 2 lines · Nick Piggin

#define PG_free 20 /* Page is on the free lists */
+#define PG_freeing 21 /* PG_refcount about to be freed */

Wow this needs two new page bits. That might be a problem ongoing. There are only 24 of these puppies and this takes us to just two remaining. Do we really need _two_ to track free?

One obvious area of overlap might be the PG_nosave_free which seems to be set on free pages for software suspend. Perhaps that and PG_free will be equivalent in intent (though maintained differently) and allow us to recover a bit?

There are a couple of bits which imply ownership such as PG_slab, PG_swapcache and PG_reserved which to my mind are all exclusive. Perhaps those plus the PG_free could be combined into a owner field. I am unsure if the PG_freeing can be 'backed out' if not it may also combine?

Mumble ...

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

Nick Piggin

author

2005-06-28 13:16 UTC #23 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 11 lines · Andy Whitcroft

Quoted 2 lines · Nick Piggin
#define PG_free 20 /* Page is on the free lists */
+#define PG_freeing 21 /* PG_refcount about to be freed */
Wow this needs two new page bits. That might be a problem ongoing. There are only 24 of these puppies and this takes us to just two remaining. Do we really need _two_ to track free?

Yeah they are kind of different. PG_freeing isn't a really good description for it. Basically it is set to guarantee a page won't gain any more references (real, not speculative) than what page_count returns.

I'm in the process of recovering one of those with an earlier set of patches (PG_reserved).

Quoted 5 lines

One obvious area of overlap might be the PG_nosave_free which seems to be set on free pages for software suspend. Perhaps that and PG_free will be equivalent in intent (though maintained differently) and allow us to recover a bit?

PG_free can't be shared with anything else, unfortunately. It doesn't need to be an atomic flag though, so it can be an "impossible" combination of flags.

Quoted 5 lines

There are a couple of bits which imply ownership such as PG_slab, PG_swapcache and PG_reserved which to my mind are all exclusive. Perhaps those plus the PG_free could be combined into a owner field. I am unsure if the PG_freeing can be 'backed out' if not it may also combine?

I think there are a a few ways that bits can be reclaimed if we start digging. swsusp uses 2 which seems excessive though may be fully justified. Can PG_private be replaced by (!page->private)? Can filesystems easily stop using PG_checked?

OK, I'll cut the hand-waving: PG_free used to be derived from PG_private && page_count == 0, so it could instead be PG_active && !PG_lru quite easily AFAIKS. If this patchset ever looks like being merged you can take me up on it ;)

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Dave Hansen

2005-06-28 16:03 UTC #24 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 3 lines · Nick Piggin

I think there are a a few ways that bits can be reclaimed if we start digging. swsusp uses 2 which seems excessive though may be fully justified.

They (swsusp) actually don't need the bits at all until suspend-time, at all. Somebody coded up a "dynamic page flags" patch that let them kill the page->flags use, but it didn't really go anywhere. Might be nice if someone dug it up. I probably have a copy somewhere.

-- Dave

Pavel Machek

2005-06-29 16:31 UTC #25 lore raw

Re: [patch 2] mm: speculative get_page

Hi!

Quoted 8 lines

Quoted 3 lines
I think there are a a few ways that bits can be reclaimed if we start digging. swsusp uses 2 which seems excessive though may be fully justified.
They (swsusp) actually don't need the bits at all until suspend-time, at all. Somebody coded up a "dynamic page flags" patch that let them kill the page->flags use, but it didn't really go anywhere. Might be nice if someone dug it up. I probably have a copy somewhere.

Unfortunately that patch was rather ugly :-(.
Pavel

Signature · 6 lines

teflon -- maybe it is a trademark, but it should not be.
--
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>

Dave Hansen

2005-06-29 18:43 UTC #26 lore raw

Re: [patch 2] mm: speculative get_page

Quoted 10 lines · Pavel Machek

Quoted 8 lines
Quoted 3 lines
I think there are a a few ways that bits can be reclaimed if we start digging. swsusp uses 2 which seems excessive though may be fully justified.
They (swsusp) actually don't need the bits at all until suspend-time, at all. Somebody coded up a "dynamic page flags" patch that let them kill the page->flags use, but it didn't really go anywhere. Might be nice if someone dug it up. I probably have a copy somewhere.
Unfortunately that patch was rather ugly :-(.

Do you think the idea was ugly, or just the implementation? Is there something that you'd rather see?

-- Dave

Pavel Machek

2005-06-29 21:22 UTC #27 lore raw

Re: [patch 2] mm: speculative get_page

Hi!

Quoted 9 lines

Quoted 9 lines
Quoted 8 lines
Quoted 3 lines
I think there are a a few ways that bits can be reclaimed if we start digging. swsusp uses 2 which seems excessive though may be fully justified.
They (swsusp) actually don't need the bits at all until suspend-time, at all. Somebody coded up a "dynamic page flags" patch that let them kill the page->flags use, but it didn't really go anywhere. Might be nice if someone dug it up. I probably have a copy somewhere.

Quoted 4 lines

Quoted 1 line
Unfortunately that patch was rather ugly :-(.
Do you think the idea was ugly, or just the implementation? Is there something that you'd rather see?

Well, implementation was ugly and idea was unneccesary because we still had bits left.

We could spare bits for swsusp by defining "PageReserved | PageLocked => PageNosave" etc.... simply by choosing some otherwise unused combinations. swsusp is not performance critical...
Pavel

Signature · 6 lines

Boycott Kodak -- for their patent abuse against Java.
--
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>

Pavel Machek

2005-06-29 16:31 UTC #28 lore raw

Re: [patch 2] mm: speculative get_page

In reply to Nick Piggin

Hi!

Quoted 9 lines

Quoted 4 lines
There are a couple of bits which imply ownership such as PG_slab, PG_swapcache and PG_reserved which to my mind are all exclusive. Perhaps those plus the PG_free could be combined into a owner field. I am unsure if the PG_freeing can be 'backed out' if not it may also combine?
I think there are a a few ways that bits can be reclaimed if we start digging. swsusp uses 2 which seems excessive though may be fully justified. Can PG_private be replaced by (!page->private)? Can filesystems easily stop using PG_checked?

It is possible that swsusp could reduce its bit usage... Current stuff works, but probably does not need strong atomicity guarantees, and could use some bit combination...
Pavel

Signature · 6 lines

teflon -- maybe it is a trademark, but it should not be.
--
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>

Nick Piggin

author

2005-06-27 06:43 UTC #29 lore raw

VFS scalability (was: [rfc] lockless pagecache)

In reply to Nick Piggin

Just an interesting aside, when first testing the patch I was using read(2) instead of nopage faults. I ran into some surprising results there which I don't have the time to follow up at the moment - it might be worth investigating if someone has the time, regardless the state of the lockless pagecache work.

For the parallel workload as described in the parent post (but read instead of fault), the vanilla kernel profile looks like this:

74453 total 0.0121
25839 update_atime 44.8594
19595 _read_unlock_irq 306.1719
13025 do_generic_mapping_read 5.5758
9374 rw_verify_area 29.2937

  1739 ia64_pal_call_static                       9.0573
  1567 default_idle                               4.0807
  1114 __copy_user                                0.4704
   848 _spin_lock                                 8.8333
   786 ia64_spinlock_contention                   8.1875
   246 ia64_save_scratch_fpregs                   3.8438
   187 ia64_load_scratch_fpregs                   2.9219
    16 file_read_actor                            0.0263
    15 fsys_bubble_down                           0.0586
    12 vfs_read                                   0.0170

This is with the filesystem mounted as noatime, so I can't work out why update_atime is so high on the list. I suspect maybe a false sharing issue with some other fields.

Signature · 6 lines

SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Andi Kleen

2005-06-27 07:13 UTC #30 lore raw

Re: VFS scalability (was: [rfc] lockless pagecache)

Quoted 3 lines · Nick Piggin

This is with the filesystem mounted as noatime, so I can't work out why update_atime is so high on the list. I suspect maybe a false sharing issue with some other fields.

Did all the 64CPUs write to the same file?

Then update_atime was just the messenger - it is the first function to read the inode so it eats the cache miss overhead.

Maybe adding a prefetch for it at the beginning of sys_read() might help, but then with 64CPUs writing to parts of the inode it will always thrash no matter how many prefetches.

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

Nick Piggin

author

2005-06-27 07:33 UTC #31 lore raw

Re: VFS scalability

Quoted 10 lines · Andi Kleen

Quoted 3 lines · Nick Piggin
This is with the filesystem mounted as noatime, so I can't work out why update_atime is so high on the list. I suspect maybe a false sharing issue with some other fields.
Did all the 64CPUs write to the same file?

Yes.

Quoted 3 lines

Then update_atime was just the messenger - it is the first function to read the inode so it eats the cache miss overhead.

I agree.

Quoted 3 lines

Maybe adding a prefetch for it at the beginning of sys_read() might help, but then with 64CPUs writing to parts of the inode it will always thrash no matter how many prefetches.

True. I'm just not sure what is causing the bouncing - I guess ->f_count due to get_file()?

rw_verify_area is another that is taking a lot of hits - probably due to the same cacheline(s) as update_atime.

Unless I'm mistaken, the big difference between the read fault and the read(2) cases is that mmap holds a reference on the file, while open(2) doesn't?

I guess if anyone really cares about that, they could hack up a flag to tell the file to remain pinned.

Signature · 6 lines

SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Andi Kleen

2005-06-27 07:44 UTC #32 lore raw

Re: VFS scalability

Quoted 7 lines · Nick Piggin

Quoted 4 lines
Maybe adding a prefetch for it at the beginning of sys_read() might help, but then with 64CPUs writing to parts of the inode it will always thrash no matter how many prefetches.
True. I'm just not sure what is causing the bouncing - I guess ->f_count due to get_file()?

That's in the file, not in the inode. It must be some inode field. I don't know which one.

There is probably some oprofile/perfmon event that could tell you which function dirties the cacheline.

-Andi

Nick Piggin

author

2005-06-27 08:03 UTC #33 lore raw

Re: VFS scalability

Quoted 6 lines · Andi Kleen

Quoted 4 lines · Nick Piggin
Quoted 3 lines
Maybe adding a prefetch for it at the beginning of sys_read() might help, but then with 64CPUs writing to parts of the inode it will always thrash no matter how many prefetches.

Quoted 7 lines

Quoted 2 lines
True. I'm just not sure what is causing the bouncing - I guess ->f_count due to get_file()?
That's in the file, not in the inode. It must be some inode field. I don't know which one.

Oh yes, my mistake.

Quoted 3 lines

There is probably some oprofile/perfmon event that could tell you which function dirties the cacheline.

I'll see if I can work it out. Thanks.

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Andrew Morton

2005-06-27 07:46 UTC #34 lore raw

In reply to Nick Piggin

Quoted 5 lines · Nick Piggin

First I'll put up some numbers to get you interested - of a 64-way Altix
with 64 processes each read-faulting in their own 512MB part of a 32GB file that is preloaded in pagecache (with the proper NUMA memory allocation).

I bet you can get a 5x to 10x reduction in ->tree_lock traffic by doing 16-page faultahead.

Nick Piggin

author

2005-06-27 08:02 UTC #35 lore raw

Quoted 12 lines · Andrew Morton

Quoted 4 lines · Nick Piggin
First I'll put up some numbers to get you interested - of a 64-way Altix with 64 processes each read-faulting in their own 512MB part of a 32GB file that is preloaded in pagecache (with the proper NUMA memory allocation).
I bet you can get a 5x to 10x reduction in ->tree_lock traffic by doing 16-page faultahead.

Definitely, for the microbenchmark I was testing with.

However I think for Oracle and others that use shared memory like this, they are probably not doing linear access, so that would be a net loss. I'm not completely sure (I don't have access to real loads at the moment), but I would have thought those guys would have looked into fault ahead if it were a possibility.

Also, the memory usage regression cases that fault ahead brings makes it a bit contentious.

I like that the lockless patch completely removes the problem at its source and even makes the serial path lighter. The other things is, the speculative get_page may be useful for more code than just pagecache lookups. But it is fairly tricky I'll give you that.

Anyway it is obviously not something that can go in tomorrow. At the very least the PageReserved patches need to go in first, and even they will need a lot of testing out of tree.

Perhaps it can be discussed at KS and we can think about what to do with it after that - that kind of time frame. No rush.

Oh yeah, and obviously it would be nice if it provided real improvements on real workloads too ;)

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Andrew Morton

2005-06-27 08:15 UTC #36 lore raw

Quoted 3 lines · Nick Piggin

Also, the memory usage regression cases that fault ahead brings makes it
a bit contentious.

faultahead consumes no more memory: if the page is present then point a pte at it. It'll make reclaim work a bit harder in some situations.

Quoted 4 lines

I like that the lockless patch completely removes the problem at its source and even makes the serial path lighter. The other things is, the speculative get_page may be useful for more code than just pagecache lookups. But it is fairly tricky I'll give you that.

Yes, it's scary-looking stuff.

Quoted 9 lines

Anyway it is obviously not something that can go in tomorrow. At the very least the PageReserved patches need to go in first, and even they will need a lot of testing out of tree.
Perhaps it can be discussed at KS and we can think about what to do with it after that - that kind of time frame. No rush.
Oh yeah, and obviously it would be nice if it provided real improvements on real workloads too ;)

umm, yes.
--
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>

Nick Piggin

author

2005-06-27 08:28 UTC #37 lore raw

Quoted 9 lines · Andrew Morton

Quoted 2 lines · Nick Piggin
Also, the memory usage regression cases that fault ahead brings makes it a bit contentious.
faultahead consumes no more memory: if the page is present then point a pte at it. It'll make reclaim work a bit harder in some situations.

Oh OK we'll call that faultahead and Christoph's thing prefault then.

I suspect it may still be a net loss for those that are running into tree_lock contention, but we'll see.

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Lincoln Dale

2005-06-27 08:56 UTC #38 lore raw

In reply to Nick Piggin

Nick Piggin wrote:
[..]

Quoted 5 lines

However I think for Oracle and others that use shared memory like this, they are probably not doing linear access, so that would be a net loss. I'm not completely sure (I don't have access to real loads at the moment), but I would have thought those guys would have looked into fault ahead if it were a possibility.

i thought those guys used O_DIRECT - in which case, wouldn't the page cache not be used?

cheers,

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

Nick Piggin

author

2005-06-27 09:04 UTC #39 lore raw

Quoted 12 lines · Lincoln Dale

Nick Piggin wrote:
[..]
Quoted 5 lines
However I think for Oracle and others that use shared memory like this, they are probably not doing linear access, so that would be a net loss. I'm not completely sure (I don't have access to real loads at the moment), but I would have thought those guys would have looked into fault ahead if it were a possibility.
i thought those guys used O_DIRECT - in which case, wouldn't the page cache not be used?

Well I think they do use O_DIRECT for their IO, but they need to use the Linux pagecache for their shared memory - that shared memory being the basis for their page cache. I think. Whatever the setup I believe they have issues with the tree_lock, which is why it was changed to an rwlock.

Signature · 8 lines

SUSE Labs, Novell Inc.


Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Chen, Kenneth W

2005-06-27 18:14 UTC #40 lore raw

Nick Piggin wrote on Monday, June 27, 2005 2:04 AM

Quoted 11 lines

Quoted 10 lines
Quoted 5 lines
However I think for Oracle and others that use shared memory like this, they are probably not doing linear access, so that would be a net loss. I'm not completely sure (I don't have access to real loads at the moment), but I would have thought those guys would have looked into fault ahead if it were a possibility.
i thought those guys used O_DIRECT - in which case, wouldn't the page cache not be used?

Quoted 5 lines

Well I think they do use O_DIRECT for their IO, but they need to use the Linux pagecache for their shared memory - that shared memory being the basis for their page cache. I think. Whatever the setup I believe they have issues with the tree_lock, which is why it was changed to an rwlock.

Typically shared memory is used as db buffer cache, and O_DIRECT is performed on these buffer cache (hence O_DIRECT on the shared memory). You must be thinking some other workload. Nevertheless, for OLTP type of db workload, tree_lock hasn't been a problem so far.

- Ken

Badari Pulavarty

2005-06-27 18:51 UTC #41 lore raw

Quoted 18 lines · Kenneth W

Nick Piggin wrote on Monday, June 27, 2005 2:04 AM
Quoted 11 lines
Quoted 10 lines
Quoted 5 lines
However I think for Oracle and others that use shared memory like this, they are probably not doing linear access, so that would be a net loss. I'm not completely sure (I don't have access to real loads at the moment), but I would have thought those guys would have looked into fault ahead if it were a possibility.
i thought those guys used O_DIRECT - in which case, wouldn't the page cache not be used?
Quoted 5 lines
Well I think they do use O_DIRECT for their IO, but they need to use the Linux pagecache for their shared memory - that shared memory being the basis for their page cache. I think. Whatever the setup I believe they have issues with the tree_lock, which is why it was changed to an rwlock.

Quoted 4 lines

Typically shared memory is used as db buffer cache, and O_DIRECT is performed on these buffer cache (hence O_DIRECT on the shared memory). You must be thinking some other workload. Nevertheless, for OLTP type of db workload, tree_lock hasn't been a problem so far.

What about DSS ? I need to go back and verify some of the profiles we have.

Thanks,
Badari

Chen, Kenneth W

2005-06-27 19:05 UTC #42 lore raw

Badari Pulavarty wrote on Monday, June 27, 2005 11:51 AM

Quoted 8 lines · Kenneth W

Quoted 4 lines
Typically shared memory is used as db buffer cache, and O_DIRECT is performed on these buffer cache (hence O_DIRECT on the shared memory). You must be thinking some other workload. Nevertheless, for OLTP type of db workload, tree_lock hasn't been a problem so far.
What about DSS ? I need to go back and verify some of the profiles we have.

I don't recall seeing tree_lock to be a problem for DSS workload either.

Christoph Lameter

2005-06-27 19:22 UTC #43 lore raw

Quoted 1 line · Kenneth W

I don't recall seeing tree_lock to be a problem for DSS workload either.

I have seen the tree_lock being a problem a number of times with large scale NUMA type workloads.

Chen, Kenneth W

2005-06-27 19:42 UTC #44 lore raw

Christoph Lameter wrote on Monday, June 27, 2005 12:23 PM

Quoted 5 lines · Kenneth W

Quoted 1 line
I don't recall seeing tree_lock to be a problem for DSS workload either.
I have seen the tree_lock being a problem a number of times with large scale NUMA type workloads.

I totally agree! My earlier posts are strictly referring to industry standard db workloads (OLTP, DSS). I'm not saying it's not a problem for everyone :-) Obviously you just outlined a few ....

- Ken

Sonny Rao

2005-07-05 15:11 UTC #45 lore raw

Quoted 10 lines · Kenneth W

Christoph Lameter wrote on Monday, June 27, 2005 12:23 PM
Quoted 5 lines · Kenneth W
Quoted 1 line
I don't recall seeing tree_lock to be a problem for DSS workload either.
I have seen the tree_lock being a problem a number of times with large scale NUMA type workloads.
I totally agree! My earlier posts are strictly referring to industry standard db workloads (OLTP, DSS). I'm not saying it's not a problem for everyone :-) Obviously you just outlined a few ....

I'm a bit late to the party here (was gone on vacation), but I do have profiles from DSS workloads using page-cache rather than O_DIRECT and I do see spin_lock_irq() in the profiles which I'm pretty certain are locks spinning for access to the radix_tree. I'll talk about it a bit more up in Ottawa but here's the top 5 on my profile (sorry don't have the number of ticks at the momement):

1. dedicated_idle (waiting for I/O)
2. __copy_tofrom_user
3. radix_tree_delete
4. _spin_lock_irq
5. __find_get_block

So, yes, if the page-cache is used in a DSS workload then one will see the tree-lock. BTW, this was on a PPC64 machine w/ a fairly small NUMA factor.

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

Martin J. Bligh

2005-07-05 15:31 UTC #46 lore raw

Quoted 23 lines

Quoted 9 lines
Quoted 5 lines · Kenneth W
Quoted 1 line
I don't recall seeing tree_lock to be a problem for DSS workload either.
I have seen the tree_lock being a problem a number of times with large scale NUMA type workloads.
I totally agree! My earlier posts are strictly referring to industry standard db workloads (OLTP, DSS). I'm not saying it's not a problem for everyone :-) Obviously you just outlined a few ....
I'm a bit late to the party here (was gone on vacation), but I do have profiles from DSS workloads using page-cache rather than O_DIRECT and I do see spin_lock_irq() in the profiles which I'm pretty certain are locks spinning for access to the radix_tree. I'll talk about it a bit more up in Ottawa but here's the top 5 on my profile (sorry don't have the number of ticks at the momement):
1. dedicated_idle (waiting for I/O)
2. __copy_tofrom_user
3. radix_tree_delete
4. _spin_lock_irq
5. __find_get_block

Quoted 3 lines

So, yes, if the page-cache is used in a DSS workload then one will see the tree-lock. BTW, this was on a PPC64 machine w/ a fairly small NUMA factor.

The easiest way to confirm the spin-lock thing is to recompile with CONFIG_SPINLINE, and take a new profile, then diff the two ...

Sonny Rao

2005-07-05 15:37 UTC #47 lore raw

Quoted 23 lines · Martin J. Bligh

Quoted 23 lines
Quoted 9 lines
Quoted 5 lines · Kenneth W
Quoted 1 line
I don't recall seeing tree_lock to be a problem for DSS workload either.
I have seen the tree_lock being a problem a number of times with large scale NUMA type workloads.
I totally agree! My earlier posts are strictly referring to industry standard db workloads (OLTP, DSS). I'm not saying it's not a problem for everyone :-) Obviously you just outlined a few ....
I'm a bit late to the party here (was gone on vacation), but I do have profiles from DSS workloads using page-cache rather than O_DIRECT and I do see spin_lock_irq() in the profiles which I'm pretty certain are locks spinning for access to the radix_tree. I'll talk about it a bit more up in Ottawa but here's the top 5 on my profile (sorry don't have the number of ticks at the momement):
1. dedicated_idle (waiting for I/O)
2. __copy_tofrom_user
3. radix_tree_delete
4. _spin_lock_irq
5. __find_get_block

Quoted 6 lines

Quoted 3 lines
So, yes, if the page-cache is used in a DSS workload then one will see the tree-lock. BTW, this was on a PPC64 machine w/ a fairly small NUMA factor.
The easiest way to confirm the spin-lock thing is to recompile with CONFIG_SPINLINE, and take a new profile, then diff the two ...

Yep...

Unfortunately, this is broken in PPC64 since 2.6.9-rc2 or something like that, I never had a chance to track down what the issue was exactly. IIRC, there was a lot of churn in the spinlocking code around that time.

Benjamin LaHaise

2005-06-27 13:17 UTC #48 lore raw

In reply to Nick Piggin

Quoted 5 lines · Nick Piggin

However I think for Oracle and others that use shared memory like this, they are probably not doing linear access, so that would be a net loss. I'm not completely sure (I don't have access to real loads at the moment), but I would have thought those guys would have looked into fault ahead if it were a possibility.

Shared memory overhead doesn't show up on any of the database benchmarks I've seen, as they tend to use huge pages that are locked in memory, and thus don't tend to access the page cache at all after ramp up.

-ben

Signature · 6 lines

"Time is what keeps everything from happening all at once." -- John Wheeler
--
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>

Nick Piggin

author

2005-06-28 00:32 UTC #49 lore raw

Quoted 11 lines · Benjamin LaHaise

Quoted 5 lines · Nick Piggin
However I think for Oracle and others that use shared memory like this, they are probably not doing linear access, so that would be a net loss. I'm not completely sure (I don't have access to real loads at the moment), but I would have thought those guys would have looked into fault ahead if it were a possibility.
Shared memory overhead doesn't show up on any of the database benchmarks I've seen, as they tend to use huge pages that are locked in memory, and thus don't tend to access the page cache at all after ramp up.

To be quite honest I don't have any real workloads here that stress it, however I was told that it is a problem for oracle database. If there is anyone else who has problems then I'd be interested to hear them as well.

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

William Lee Irwin III

2005-06-28 01:26 UTC #50 lore raw

Quoted 3 lines · Benjamin LaHaise

Quoted 3 lines
Shared memory overhead doesn't show up on any of the database benchmarks I've seen, as they tend to use huge pages that are locked in memory, and thus don't tend to access the page cache at all after ramp up.

Quoted 4 lines · Nick Piggin

To be quite honest I don't have any real workloads here that stress it, however I was told that it is a problem for oracle database. If there is anyone else who has problems then I'd be interested to hear them as well.

It's vlm-specific.

Martin J. Bligh

2005-06-27 14:08 UTC #51 lore raw

In reply to Andrew Morton

--Andrew Morton <[email protected]> wrote (on Monday, June 27, 2005 00:46:24 -0700):

Quoted 9 lines

Quoted 5 lines · Nick Piggin
First I'll put up some numbers to get you interested - of a 64-way Altix
with 64 processes each read-faulting in their own 512MB part of a 32GB file that is preloaded in pagecache (with the proper NUMA memory allocation).
I bet you can get a 5x to 10x reduction in ->tree_lock traffic by doing 16-page faultahead.

Maybe true, but when we last tried that, faultahead sucked for performance in a more general sense. All the extra setup and teardown cost for unnecessary PTEs kills you, even if it's only 4 pages or so.

Christoph Lameter

2005-06-27 17:49 UTC #52 lore raw

In reply to Andrew Morton

Quoted 9 lines · Andrew Morton

Quoted 5 lines · Nick Piggin
First I'll put up some numbers to get you interested - of a 64-way Altix
with 64 processes each read-faulting in their own 512MB part of a 32GB file that is preloaded in pagecache (with the proper NUMA memory allocation).
I bet you can get a 5x to 10x reduction in ->tree_lock traffic by doing 16-page faultahead.

Could be working into the prefault patch.... Good idea.

Hirokazu Takahashi

2005-06-29 10:49 UTC #53 lore raw

In reply to Nick Piggin

Hi Nick,

Your patches improve the performance if lots of processes are accessing the same file at the same time, right?

If so, I think we can introduce multiple radix-trees instead, which enhance each inode to be able to have two or more radix-trees in it to avoid the race condition traversing the trees. Some decision mechanism is needed which radix-tree each page should be in, how many radix-tree should be prepared.

It seems to be simple and effective.

What do you think?

Quoted 6 lines

Now the tree_lock was recently(ish) converted to an rwlock, precisely for such a workload and that was apparently very successful. However an rwlock is significantly heavier, and as machines get faster and bigger, rwlocks (and any locks) will tend to use more and more of Paul McKenney's toilet paper due to cacheline bouncing.

Quoted 6 lines

So in the interest of saving some trees, let's try it without any locks.
First I'll put up some numbers to get you interested - of a 64-way Altix with 64 processes each read-faulting in their own 512MB part of a 32GB file that is preloaded in pagecache (with the proper NUMA memory allocation).

Thanks,
Hirokazu Takahashi.

Nick Piggin

author

2005-06-29 11:38 UTC #54 lore raw

Quoted 2 lines · Hirokazu Takahashi

Hi Nick,

Hi,

Quoted 3 lines

Your patches improve the performance if lots of processes are accessing the same file at the same time, right?

Yes.

Quoted 10 lines

If so, I think we can introduce multiple radix-trees instead, which enhance each inode to be able to have two or more radix-trees in it to avoid the race condition traversing the trees. Some decision mechanism is needed which radix-tree each page should be in, how many radix-tree should be prepared.
It seems to be simple and effective.
What do you think?

Sure it is a possibility.

I don't think you could call it effective like a completely lockless version is effective. You might take more locks during gang lookups, you may have a lot of ugly and not-always-working heuristics (hey, my app goes really fast if it spreads accesses over a 1GB file, but falls on its face with a 10MB one). You might get increased cache footprints for common operations.

I mainly did the patches for a bit of fun rather than to address a particular problem with a real workload and as such I won't be pushing to get them in the kernel for the time being.

Signature · 7 lines

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com --
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>

Hirokazu Takahashi

2005-06-30 03:32 UTC #55 lore raw

Hi,

Quoted 17 lines

Quoted 3 lines
Your patches improve the performance if lots of processes are accessing the same file at the same time, right?
Yes.
Quoted 10 lines
If so, I think we can introduce multiple radix-trees instead, which enhance each inode to be able to have two or more radix-trees in it to avoid the race condition traversing the trees. Some decision mechanism is needed which radix-tree each page should be in, how many radix-tree should be prepared.
It seems to be simple and effective.
What do you think?

Quoted 8 lines

Sure it is a possibility.
I don't think you could call it effective like a completely lockless version is effective. You might take more locks during gang lookups, you may have a lot of ugly and not-always-working heuristics (hey, my app goes really fast if it spreads accesses over a 1GB file, but falls on its face with a 10MB one). You might get increased cache footprints for common operations.

I guess it would be enough to split a huge file into the same size pieces simply and put each of them in its associated radix-tree in most cases for practical use.

And I also feel your approach is interesting.

Quoted 3 lines

I mainly did the patches for a bit of fun rather than to address a particular problem with a real workload and as such I won't be pushing to get them in the kernel for the time being.

I see.

I propose another idea if you don't mind, seqlock seems to make your code much simpler though I'm not sure whether it works well under heavy load. It would become stable without the tricks, which makes VM hard to be enhanced in the future.

Thanks,
Hirokazu Takahashi.
--
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>