radix-tree pagecache for 2.5

@@ -483,10 +483,10 @@ static int shrink_cache(int nr_pages, zo
 		 * This is the non-racy check for busy page.
 		 */
 		if (mapping) {
-			read_lock(&mapping->page_lock);
+			write_lock(&mapping->page_lock);
 			if (is_page_cache_freeable(page))
 				goto page_freeable;
-			read_unlock(&mapping->page_lock);
+			write_unlock(&mapping->page_lock);
 		}
 		UnlockPage(page);
 page_mapped:

@@ -507,7 +507,7 @@ page_freeable:
 		 * the page is freeable* so not in use by anybody.
 		 */
 		if (PageDirty(page)) {
-			read_unlock(&mapping->page_lock);
+			write_unlock(&mapping->page_lock);
 			UnlockPage(page);
 			continue;
 		}

@@ -515,12 +515,12 @@ page_freeable:
 		/* point of no return */
 		if (likely(!PageSwapCache(page))) {
 			__remove_inode_page(page);
-			read_unlock(&mapping->page_lock);
+			write_unlock(&mapping->page_lock);
 		} else {
 			swp_entry_t swap;
 			swap.val = page->index;
 			__delete_from_swap_cache(page);
-			read_unlock(&mapping->page_lock);
+			write_unlock(&mapping->page_lock);
 			swap_free(swap);
 		}
 

@@ -59,7 +59,7 @@ spinlock_t pagemap_lru_lock __cacheline_
 /*
  * Remove a page from the page cache and free it. Caller has to make
  * sure the page is locked and that nobody else uses it - or that usage
- * is safe.
+ * is safe.  The caller must hold a write_lock on the mapping's page_lock.
  */
 void __remove_inode_page(struct page *page)
 {

@@ -574,6 +574,7 @@ int filemap_fdatawait(struct address_spa
 /*
  * This adds a page to the page cache, starting out as locked,
  * owned by us, but unreferenced, not uptodate and with no errors.
+ * The caller must hold a write_lock on the mapping->page_lock.
  */
 static int __add_to_page_cache(struct page *page,
 		struct address_space *mapping, unsigned long offset)

@@ -874,19 +875,19 @@ struct page * find_or_create_page(struct
 	if (!page) {
 		struct page *newpage = alloc_page(gfp_mask);
 		if (newpage) {
-			read_lock(&mapping->page_lock);
+			write_lock(&mapping->page_lock);
 			page = __find_lock_page(mapping, index);
 			if (likely(!page)) {
 				page = newpage;
 				if (__add_to_page_cache(page, mapping, index)) {
-					read_unlock(&mapping->page_lock);
+					write_unlock(&mapping->page_lock);
 					page_cache_release(page);
 					page = NULL;
 					goto out;
 				}
 				newpage = NULL;
 			}
-			read_unlock(&mapping->page_lock);
+			write_unlock(&mapping->page_lock);
 			if (newpage == NULL)
 				lru_cache_add(page);
 			else 

@@ -1280,13 +1281,13 @@ void do_generic_file_read(struct file * 
 		 * Try to find the data in the page cache..
 		 */
 
-		read_lock(&mapping->page_lock);
+		write_lock(&mapping->page_lock);
 		page = radix_tree_lookup(&mapping->page_tree, index);
 		if (!page)
 			goto no_cached_page;
 found_page:
 		page_cache_get(page);
-		read_unlock(&mapping->page_lock);
+		write_unlock(&mapping->page_lock);
 
 		if (!Page_Uptodate(page))
 			goto page_not_up_to_date;

@@ -1380,7 +1381,7 @@ no_cached_page:
 		 * We get here with the page cache lock held.
 		 */
 		if (!cached_page) {
-			read_unlock(&mapping->page_lock);
+			write_unlock(&mapping->page_lock);
 			cached_page = page_cache_alloc(mapping);
 			if (!cached_page) {
 				desc->error = -ENOMEM;

@@ -1391,7 +1392,7 @@ no_cached_page:
 			 * Somebody may have added the page while we
 			 * dropped the page cache lock. Check for that.
 			 */
-			read_lock(&mapping->page_lock);
+			write_lock(&mapping->page_lock);
 			page = radix_tree_lookup(&mapping->page_tree, index);
 			if (page)
 				goto found_page;

@@ -1401,12 +1402,12 @@ no_cached_page:
 		 * Ok, add the new page to the hash-queues...
 		 */
 		if (__add_to_page_cache(cached_page, mapping, index) < 0) {
-			read_unlock(&mapping->page_lock);
+			write_unlock(&mapping->page_lock);
 			desc->error = -ENOMEM;
 			break;
 		}
 		page = cached_page;
-		read_unlock(&mapping->page_lock);
+		write_unlock(&mapping->page_lock);
 		lru_cache_add(page);		
 		cached_page = NULL;
--

@@ -156,7 +156,6 @@ static int rd_blkdev_pagecache_IO(int rw
 
 	do {
 		int count;
-		struct page ** hash;
 		struct page * page;
 		char * src, * dst;
 		int unlock = 0;

@@ -166,8 +165,7 @@ static int rd_blkdev_pagecache_IO(int rw
 			count = size;
 		size -= count;
 
-		hash = page_hash(mapping, index);
-		page = __find_get_page(mapping, index, hash);
+		page = find_get_page(mapping, index);
 		if (!page) {
 			page = grab_cache_page(mapping, index);
 			err = -ENOMEM;

@@ -143,6 +143,8 @@ void inode_init_once(struct inode *inode
 	INIT_LIST_HEAD(&inode->i_dirty_data_buffers);
 	INIT_LIST_HEAD(&inode->i_devices);
 	sema_init(&inode->i_sem, 1);
+	INIT_RADIX_TREE(&inode->i_data.page_tree, GFP_ATOMIC);
+	rwlock_init(&inode->i_data.page_lock);
 	spin_lock_init(&inode->i_data.i_shared_lock);
 	INIT_LIST_HEAD(&inode->i_data.i_mmap);
 	INIT_LIST_HEAD(&inode->i_data.i_mmap_shared);

@@ -21,6 +21,7 @@
 #include <linux/cache.h>
 #include <linux/stddef.h>
 #include <linux/string.h>
+#include <linux/radix-tree.h>
 
 #include <asm/atomic.h>
 #include <asm/bitops.h>

@@ -370,6 +371,8 @@ struct address_space_operations {
 };
 
 struct address_space {
+	struct radix_tree_root	page_tree;	/* radix tree of all pages */
+	rwlock_t		page_lock;	/* and rwlock protecting it */
 	struct list_head	clean_pages;	/* list of clean pages */
 	struct list_head	dirty_pages;	/* list of dirty pages */
 	struct list_head	locked_pages;	/* list of locked pages */

@@ -149,14 +149,11 @@ typedef struct page {
 	struct list_head list;		/* ->mapping has some page lists. */
 	struct address_space *mapping;	/* The inode (or ...) we belong to. */
 	unsigned long index;		/* Our offset within mapping. */
-	struct page *next_hash;		/* Next page sharing our hash bucket in
-					   the pagecache hash table. */
 	atomic_t count;			/* Usage count, see below. */
 	unsigned long flags;		/* atomic flags, some possibly
 					   updated asynchronously */
 	struct list_head lru;		/* Pageout list, eg. active_list;
 					   protected by pagemap_lru_lock !! */
-	struct page **pprev_hash;	/* Complement to *next_hash. */
 	struct buffer_head * buffers;	/* Buffer maps us to a disk block. */
 
 	/*

@@ -236,9 +233,8 @@ typedef struct page {
  * using the page->list list_head. These fields are also used for
  * freelist managemet (when page->count==0).
  *
- * There is also a hash table mapping (mapping,index) to the page
- * in memory if present. The lists for this hash table use the fields
- * page->next_hash and page->pprev_hash.
+ * There is also a per-mapping radix tree mapping index to the page
+ * in memory if present. The tree is rooted at mapping->root.  
  *
  * All process pages can do I/O:
  * - inode pages may need to be read from disk,

89 lines not on this page · raw message

49 lines not on this page · raw message

@@ -109,7 +109,7 @@ extern void __remove_inode_page(struct p
 struct task_struct;
 struct vm_area_struct;
 struct sysinfo;
-
+struct address_space;
 struct zone_t;
 
 /* linux/mm/swap.c */

@@ -139,6 +139,9 @@ extern void show_swap_cache_info(void);
 extern int add_to_swap_cache(struct page *, swp_entry_t);
 extern void __delete_from_swap_cache(struct page *page);
 extern void delete_from_swap_cache(struct page *page);
+extern int move_to_swap_cache(struct page *page, swp_entry_t entry);
+extern int move_from_swap_cache(struct page *page, unsigned long index,
+		struct address_space *mapping);
 extern void free_page_and_swap_cache(struct page *page);
 extern struct page * lookup_swap_cache(swp_entry_t);
 extern struct page * read_swap_cache_async(swp_entry_t);

@@ -69,6 +69,7 @@ extern void sbus_init(void);
 extern void sysctl_init(void);
 extern void signals_init(void);
 
+extern void radix_tree_init(void);
 extern void free_initmem(void);
 
 #ifdef CONFIG_TC

@@ -392,7 +393,7 @@ asmlinkage void __init start_kernel(void
 	proc_caches_init();
 	vfs_caches_init(mempages);
 	buffer_init(mempages);
-	page_cache_init(mempages);
+	radix_tree_init();
 #if defined(CONFIG_ARCH_S390)
 	ccwcache_init();
 #endif

@@ -224,8 +224,6 @@ EXPORT_SYMBOL(generic_file_write);
 EXPORT_SYMBOL(generic_file_mmap);
 EXPORT_SYMBOL(generic_ro_fops);
 EXPORT_SYMBOL(generic_buffer_fdatasync);
-EXPORT_SYMBOL(page_hash_bits);
-EXPORT_SYMBOL(page_hash_table);
 EXPORT_SYMBOL(file_lock_list);
 EXPORT_SYMBOL(locks_init_lock);
 EXPORT_SYMBOL(locks_copy_lock);

@@ -266,8 +264,8 @@ EXPORT_SYMBOL(no_llseek);
 EXPORT_SYMBOL(__pollwait);
 EXPORT_SYMBOL(poll_freewait);
 EXPORT_SYMBOL(ROOT_DEV);
-EXPORT_SYMBOL(__find_get_page);
-EXPORT_SYMBOL(__find_lock_page);
+EXPORT_SYMBOL(find_get_page);
+EXPORT_SYMBOL(find_lock_page);
 EXPORT_SYMBOL(grab_cache_page);
 EXPORT_SYMBOL(grab_cache_page_nowait);
 EXPORT_SYMBOL(read_cache_page);

296 lines not on this page · raw message

878 lines not on this page · raw message

@@ -27,9 +27,9 @@ static unsigned char mincore_page(struct
 {
 	unsigned char present = 0;
 	struct address_space * as = vma->vm_file->f_dentry->d_inode->i_mapping;
-	struct page * page, ** hash = page_hash(as, pgoff);
+	struct page * page;
 
-	page = __find_get_page(as, pgoff, hash);
+	page = find_get_page(as, pgoff);
 	if (page) {
 		present = Page_Uptodate(page);
 		page_cache_release(page);

146 lines not on this page · raw message

@@ -239,10 +239,10 @@ static int exclusive_swap_page(struct pa
 		/* Is the only swap cache user the cache itself? */
 		if (p->swap_map[SWP_OFFSET(entry)] == 1) {
 			/* Recheck the page count with the pagecache lock held.. */
-			spin_lock(&pagecache_lock);
+			read_lock(&swapper_space.page_lock);
 			if (page_count(page) - !!page->buffers == 2)
 				retval = 1;
-			spin_unlock(&pagecache_lock);
+			read_unlock(&swapper_space.page_lock);
 		}
 		swap_info_put(p);
 	}

@@ -307,13 +307,13 @@ int remove_exclusive_swap_page(struct pa
 	retval = 0;
 	if (p->swap_map[SWP_OFFSET(entry)] == 1) {
 		/* Recheck the page count with the pagecache lock held.. */
-		spin_lock(&pagecache_lock);
+		read_lock(&swapper_space.page_lock);
 		if (page_count(page) - !!page->buffers == 2) {
 			__delete_from_swap_cache(page);
 			SetPageDirty(page);
 			retval = 1;
 		}
-		spin_unlock(&pagecache_lock);
+		read_unlock(&swapper_space.page_lock);
 	}
 	swap_info_put(p);
 

156 lines not on this page · raw message

116 lines not on this page · raw message