FS-Cache: Generic filesystem caching facility

This series of patches does four things:

(1) Adds a generic intermediary (FS-Cache) by which filesystems may call on

     local caching capabilities, and by which local caching backends may make
     caches available:

	+---------+
	|         |                        +-----------+
	|   NFS   |--+                     |           |
	|         |  |                 +-->|  CacheFS  |
	+---------+  |   +----------+  |   | /dev/hda5 |
	             |   |          |  |   +-----------+
	+---------+  +-->|          |  |
	|         |      |          |--+   +-------------+
	|   AFS   |----->| FS-Cache |      |             |
	|         |      |          |----->| Cache Files |
	+---------+  +-->|          |      | /var/cache  |
	             |   |          |--+   +-------------+
	+---------+  |   +----------+  |
	|         |  |                 |   +-------------+
	|  ISOFS  |--+                 |   |             |
	|         |                    +-->| ReiserCache |
	+---------+                        | /           |
	                                   +-------------+

(2) Adds a quasi-filesystem (CacheFS) that can turn block devices into a local caches.

(3) Modifies the kAFS network filesystem to be able to read through this cache.

(4) Documents the netfs interface and the cache backend interface.

Other backends may be added to the system, and other netfs's may be modified to use caching.

There are a number of reasons why I'm not using i_mapping to do this. These have been discussed a lot on the LKML and CacheFS mailing lists, but to summarise the basics:

(1) Most filesystems don't do hole reportage. Holes in files are treated as blocks of zeros and can't be distinguished otherwise, making it difficult to distinguish blocks that have been read from the network and cached from those that haven't.

(2) The backing inode must be fully populated before being exposed to userspace through the main inode because the VM/VFS goes directly to the backing inode and does not interrogate the front inode on VM ops.

Therefore:

(a) The backing inode must fit entirely within the cache.

(b) All backed files currently open must fit entirely within the cache at the same time.

(c) A working set of files in total larger than the cache may not be cached.

(d) A file may not grow larger than the available space in the cache.

(e) A file that's open and cached, and remotely grows larger than the cache is potentially stuffed.

(3) Writes go to the backing filesystem, and can only be transferred to the network when the file is closed.

(4) There's no record of what changes have been made, so the whole file must be written back.

(5) The pages belong to the backing filesystem, and all metadata associated with that page are relevant only to the backing filesystem, and not anything stacked atop it.

David

The attached patch makes i386's find_first_bit() use an unsigned integer as a counter to avoid getting warnings when -Wsign-compare is given.

---
warthog>diffstat -p1 asm-i386-bitops-2614mm2.diff

 include/asm-i386/bitops.h |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff -uNrp linux-2.6.14-mm2/include/asm-i386/bitops.h linux-2.6.14-mm2-cachefs/include/asm-i386/bitops.h
@@ -332,9 +332,9 @@ static inline unsigned long __ffs(unsign
  * Returns the bit-number of the first set bit, not the number of the byte
  * containing a bit.
  */
-static inline int find_first_bit(const unsigned long *addr, unsigned size)
+static inline unsigned find_first_bit(const unsigned long *addr, unsigned size)
 {
-	int x = 0;
+	unsigned x = 0;
 
 	while (x < size) {
 		unsigned long val = *addr++;

The attached patch makes it possible to include linux/pagevec.h multiple times without incurring errors due to duplicate definitions.

---
warthog>diffstat -p1 pagevec-hdr-ifndef-2614mm2.diff

 include/linux/pagevec.h |    5 +++++
 1 files changed, 5 insertions(+)

diff -uNrp linux-2.6.14-mm2/include/linux/pagevec.h linux-2.6.14-mm2-cachefs/include/linux/pagevec.h
@@ -5,6 +5,9 @@
  * pages.  A pagevec is a multipage container which is used for that.
  */
 
+#ifndef _LINUX_PAGEVEC_H
+#define _LINUX_PAGEVEC_H
+
 /* 14 pointers + two long's align the pagevec structure to a power of two */
 #define PAGEVEC_SIZE	14
 

@@ -83,3 +86,5 @@ static inline void pagevec_lru_add(struc
 	if (pagevec_count(pvec))
 		__pagevec_lru_add(pvec);
 }
+
+#endif /* _LINUX_PAGEVEC_H */

The attached patch adds list_for_each_entry_safe_reverse() to linux/list.h

---
warthog>diffstat -p1 list-foreach-saferev-2614mm2.diff

 include/linux/list.h |   14 ++++++++++++++
 1 files changed, 14 insertions(+)

diff -uNrp linux-2.6.14-mm2/include/linux/list.h linux-2.6.14-mm2-cachefs/include/linux/list.h
@@ -450,6 +450,20 @@ static inline void list_splice_init(stru
 	     pos = n, n = list_entry(n->member.next, typeof(*n), member))
 
 /**
+ * list_for_each_entry_safe_reverse - iterate backwards over list of given type safe against
+ *				      removal of list entry
+ * @pos:	the type * to use as a loop counter.
+ * @n:		another type * to use as temporary storage
+ * @head:	the head for your list.
+ * @member:	the name of the list_struct within the struct.
+ */
+#define list_for_each_entry_safe_reverse(pos, n, head, member)		\
+	for (pos = list_entry((head)->prev, typeof(*pos), member),	\
+		n = list_entry(pos->member.prev, typeof(*pos), member);	\
+	     &pos->member != (head); 					\
+	     pos = n, n = list_entry(n->member.prev, typeof(*n), member))
+
+/**
  * list_for_each_rcu	-	iterate over an rcu-protected list
  * @pos:	the &struct list_head to use as a loop counter.
  * @head:	the head for your list.

The attached patch permits advance allocation of radix-tree nodes on a per-task basis to make sure that ENOMEM doesn't crop up at an inconvenient moment in CacheFS.

---
warthog>diffstat -p1 radix-cache-2614mm2.diff

 include/linux/radix-tree.h |   14 ++++
 include/linux/sched.h      |    2 
 kernel/exit.c              |    1 
 kernel/fork.c              |    2 
 lib/radix-tree.c           |  134 ++++++++++++++++++++++++++++++++++-----------
 5 files changed, 122 insertions(+), 31 deletions(-)

diff -uNrp linux-2.6.14-mm2/include/linux/radix-tree.h linux-2.6.14-mm2-cachefs/include/linux/radix-tree.h
@@ -51,7 +51,6 @@ 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);
-int radix_tree_preload(gfp_t gfp_mask);
 void radix_tree_init(void);
 void *radix_tree_tag_set(struct radix_tree_root *root,
 			unsigned long index, int tag);

@@ -64,6 +63,19 @@ radix_tree_gang_lookup_tag(struct radix_
 		unsigned long first_index, unsigned int max_items, int tag);
 int radix_tree_tagged(struct radix_tree_root *root, int tag);
 
+/*
+ * radix tree advance loading
+ */
+struct radix_tree_preload {
+	int count;
+	struct radix_tree_node *nodes;
+};
+
+int radix_tree_preload(unsigned int gfp_mask);
+
+extern int radix_tree_preload_task(unsigned int gfp_mask, int nitems);
+extern void radix_tree_preload_drain_task(void);
+
 static inline void radix_tree_preload_end(void)
 {
 	preempt_enable();

diff -uNrp linux-2.6.14-mm2/include/linux/sched.h linux-2.6.14-mm2-cachefs/include/linux/sched.h
@@ -35,6 +35,7 @@
 #include <linux/topology.h>
 #include <linux/seccomp.h>
 #include <linux/rcupdate.h>
+#include <linux/radix-tree.h>
 
 #include <linux/auxvec.h>	/* For AT_VECTOR_SIZE */
 

@@ -863,6 +864,7 @@ struct task_struct {
 
 /* VM state */
 	struct reclaim_state *reclaim_state;
+	struct radix_tree_preload radix_preload;
 
 	struct dentry *proc_dentry;
 	struct backing_dev_info *backing_dev_info;

diff -uNrp linux-2.6.14-mm2/kernel/exit.c linux-2.6.14-mm2-cachefs/kernel/exit.c
@@ -64,6 +64,7 @@ void release_task(struct task_struct * p
 	struct dentry *proc_dentry;
 
 repeat: 
+	radix_tree_preload_drain_task();
 	atomic_dec(&p->user->processes);
 	spin_lock(&p->proc_lock);
 	proc_dentry = proc_pid_unhash(p);

diff -uNrp linux-2.6.14-mm2/kernel/fork.c linux-2.6.14-mm2-cachefs/kernel/fork.c
@@ -122,6 +122,7 @@ void __put_task_struct(struct task_struc
 	if (!profile_handoff_task(tsk))
 		free_task(tsk);
 }
+EXPORT_SYMBOL(__put_task_struct);
 
 void __init fork_init(unsigned long mempages)
 {

@@ -940,6 +941,7 @@ static task_t *copy_process(unsigned lon
 			goto bad_fork_cleanup;
 
 	p->proc_dentry = NULL;
+	memset(&p->radix_preload, 0, sizeof(p->radix_preload));
 
 	INIT_LIST_HEAD(&p->children);
 	INIT_LIST_HEAD(&p->sibling);

The attached patch causes read_cache_pages() to release page-private data on a page for which add_to_page_cache() fails or the filler function fails. This permits pages with caching references associated with them to be cleaned up.

---
warthog>diffstat -p1 readahead-release-private-2614mm2.diff

 mm/readahead.c |   16 ++++++++++++++++
 1 files changed, 16 insertions(+)

diff -uNrp linux-2.6.14-mm2/mm/readahead.c linux-2.6.14-mm2-cachefs/mm/readahead.c
@@ -131,6 +131,12 @@ int read_cache_pages(struct address_spac
 		page = list_to_page(pages);
 		list_del(&page->lru);
 		if (add_to_page_cache(page, mapping, page->index, GFP_KERNEL)) {
+			if (PagePrivate(page) && mapping->a_ops->releasepage) {
+				page->mapping = mapping;
+				mapping->a_ops->releasepage(page, GFP_KERNEL);
+				page->mapping = NULL;
+			}
+				
 			page_cache_release(page);
 			continue;
 		}

@@ -143,6 +149,16 @@ int read_cache_pages(struct address_spac
 
 				victim = list_to_page(pages);
 				list_del(&victim->lru);
+
+				if (PagePrivate(victim) &&
+				    mapping->a_ops->releasepage
+				    ) {
+					victim->mapping = mapping;
+					mapping->a_ops->releasepage(
+						victim, GFP_KERNEL);
+					victim->mapping = NULL;
+				}
+
 				page_cache_release(victim);
 			}
 			break;

The attached patch adds a function by which an existing page in the pagecache may be traded for a new one at the same location without having to allocate or free any radix tree nodes.

This permits CacheFS to write to start making a new version of a disk block in memory for which the old version has not yet been written and journalled.

---
warthog>diffstat -p1 replace-in-pagecache-2614mm2.diff

 include/linux/pagemap.h |    3 +++
 mm/filemap.c            |   33 +++++++++++++++++++++++++++++++++
 2 files changed, 36 insertions(+)

diff -uNrp linux-2.6.14-mm2/include/linux/pagemap.h linux-2.6.14-mm2-cachefs/include/linux/pagemap.h
@@ -96,6 +96,9 @@ int add_to_page_cache(struct page *page,
 				unsigned long index, gfp_t gfp_mask);
 int add_to_page_cache_lru(struct page *page, struct address_space *mapping,
 				unsigned long index, gfp_t gfp_mask);
+extern struct page *replace_in_page_cache(struct page *page,
+					  struct address_space *mapping,
+					  pgoff_t offset);
 extern void remove_from_page_cache(struct page *page);
 extern void __remove_from_page_cache(struct page *page);
 

diff -uNrp linux-2.6.14-mm2/mm/filemap.c linux-2.6.14-mm2-cachefs/mm/filemap.c
@@ -427,6 +427,39 @@ int add_to_page_cache_lru(struct page *p
 EXPORT_SYMBOL(add_to_page_cache_lru);
 
 /*
+ * This function replaces a page already in the page cache for a particular
+ * index with another, but only if there is already such a page in the page
+ * cache
+ */
+struct page *replace_in_page_cache(struct page *page,
+				   struct address_space *mapping,
+				   pgoff_t offset)
+{
+	struct page *old;
+	void **slot;
+
+	write_lock_irq(&mapping->tree_lock);
+
+	slot = radix_tree_lookup_slot(&mapping->page_tree, offset);
+	old = NULL;
+	if (slot) {
+		old = *slot;
+		*slot = page;
+		page_cache_get(page);
+		SetPageLocked(page);
+		page->mapping = mapping;
+		page->index = offset;
+		if (old)
+			old->mapping = NULL;
+	}
+
+	write_unlock_irq(&mapping->tree_lock);
+	return old;
+}
+
+EXPORT_SYMBOL(replace_in_page_cache);
+
+/*
  * In order to wait for pages to become available there must be
  * waitqueues associated with pages. By using a hash table of
  * waitqueues where the bucket discipline is to maintain all

The attached patch exports a couple of VM functions needed by CacheFS.

---
warthog>diffstat -p1 exports-2614mm2.diff

 mm/page-writeback.c |    1 +
 mm/swap.c           |    2 ++
 2 files changed, 3 insertions(+)

diff -uNrp linux-2.6.14-mm2/mm/page-writeback.c linux-2.6.14-mm2-cachefs/mm/page-writeback.c
@@ -750,6 +750,7 @@ int clear_page_dirty_for_io(struct page 
 	}
 	return TestClearPageDirty(page);
 }
+EXPORT_SYMBOL_GPL(clear_page_dirty_for_io);
 
 int test_clear_page_writeback(struct page *page)
 {

diff -uNrp linux-2.6.14-mm2/mm/swap.c linux-2.6.14-mm2-cachefs/mm/swap.c
@@ -149,6 +149,8 @@ void fastcall lru_cache_add(struct page 
 	put_cpu_var(lru_add_pvecs);
 }
 
+EXPORT_SYMBOL_GPL(lru_cache_add);
+
 void fastcall lru_cache_add_active(struct page *page)
 {
 	struct pagevec *pvec = &get_cpu_var(lru_add_active_pvecs);

The attached patch adds a generic core to which both networking filesystems and caches may bind. It transfers requests from networking filesystems to appropriate caches if possible, or else gracefully denies them.

It also:

(*) Adds a facility by which tags can be used to refer to caches, even if
they're not mounted yet.

(*) Keeps track of indexes.

(*) Permits caches to be added and removed dynamically.

(*) Permits network filesystems to annotate cache nodes that belong to them.

(*) Permits cache nodes to be pinned and reservations to be made.

If this facility is disabled in the kernel configuration, then all its operations will be trivially reducible to nothing by the compiler.

---
warthog>diffstat -p1 fscache-core-2614mm2.diff

 fs/Kconfig                    |   13 
 fs/Makefile                   |    1 
 fs/fscache/Makefile           |   13 
 fs/fscache/cookie.c           | 1030 ++++++++++++++++++++++++++++++++++++++++++
 fs/fscache/fscache-int.h      |   71 ++
 fs/fscache/fsdef.c            |  113 ++++
 fs/fscache/main.c             |  112 ++++
 fs/fscache/page.c             |  521 +++++++++++++++++++++
 include/linux/fscache-cache.h |  216 ++++++++
 include/linux/fscache.h       |  484 +++++++++++++++++++
 10 files changed, 2574 insertions(+)

diff -uNrp linux-2.6.14-mm2/fs/Kconfig linux-2.6.14-mm2-cachefs/fs/Kconfig
@@ -511,6 +511,19 @@ config FUSE_FS
 	  If you want to develop a userspace FS, or if you want to use
 	  a filesystem based on FUSE, answer Y or M.
 
+menu "Caches"
+
+config FSCACHE
+	tristate "General filesystem cache manager"
+	depends on EXPERIMENTAL
+	help
+	  This option enables a generic filesystem caching manager that can be
+	  used by various network and other filesystems to cache data
+	  locally. Different sorts of caches can be plugged in, depending on the
+	  resources available.
+
+	  See Documentation/filesystems/caching/fscache.txt for more information.
+
 menu "CD-ROM/DVD Filesystems"
 
 config ISO9660_FS

diff -uNrp linux-2.6.14-mm2/fs/Makefile linux-2.6.14-mm2-cachefs/fs/Makefile
@@ -50,6 +50,7 @@ obj-y				+= devpts/
 obj-$(CONFIG_PROFILING)		+= dcookies.o
  
 # Do not add any filesystems before this line
+obj-$(CONFIG_FSCACHE)		+= fscache/
 obj-$(CONFIG_REISERFS_FS)	+= reiserfs/
 obj-$(CONFIG_REISER4_FS)	+= reiser4/
 obj-$(CONFIG_EXT3_FS)		+= ext3/ # Before ext2 so root fs can be ext3

diff -uNrp linux-2.6.14-mm2/fs/fscache/Makefile linux-2.6.14-mm2-cachefs/fs/fscache/Makefile
@@ -0,0 +1,13 @@
+#
+# Makefile for general filesystem caching code
+#
+
+#CFLAGS += -finstrument-functions
+
+fscache-objs := \
+	cookie.o \
+	fsdef.o \
+	main.o \
+	page.o
+
+obj-$(CONFIG_FSCACHE) := fscache.o

The attached patch adds documentation for FS-Cache in general and its network filesystem and cache-backend interfaces specifically.

---
warthog>diffstat -p1 fscache-docs-2614mm2.diff

 Documentation/filesystems/caching/backend-api.txt |  334 ++++++++++
 Documentation/filesystems/caching/fscache.txt     |  150 ++++
 Documentation/filesystems/caching/netfs-api.txt   |  726 ++++++++++++++++++++++
 3 files changed, 1210 insertions(+)

diff -uNrp linux-2.6.14-mm2/Documentation/filesystems/caching/fscache.txt linux-2.6.14-mm2-cachefs/Documentation/filesystems/caching/fscache.txt
@@ -0,0 +1,150 @@
+			  ==========================
+			  General Filesystem Caching
+			  ==========================
+
+========
+OVERVIEW
+========
+
+This facility is a general purpose cache for network filesystems, though it
+could be used for caching other things such as ISO9660 filesystems too.
+
+FS-Cache mediates between cache backends (such as CacheFS) and network
+filesystems:
+
+	+---------+
+	|         |                        +-----------+
+	|   NFS   |--+                     |           |
+	|         |  |                 +-->|  CacheFS  |
+	+---------+  |   +----------+  |   | /dev/hda5 |
+	             |   |          |  |   +-----------+
+	+---------+  +-->|          |  |
+	|         |      |          |--+   +-------------+
+	|   AFS   |----->| FS-Cache |      |             |
+	|         |      |          |----->| Cache Files |
+	+---------+  +-->|          |      | /var/cache  |
+	             |   |          |--+   +-------------+
+	+---------+  |   +----------+  |
+	|         |  |                 |   +-------------+
+	|  ISOFS  |--+                 |   |             |
+	|         |                    +-->| ReiserCache |
+	+---------+                        | /           |
+	                                   +-------------+
+
+FS-Cache does not follow the idea of completely loading every netfs file
+opened in its entirety into a cache before permitting it to be accessed and
+then serving the pages out of that cache rather than the netfs inode because:
+
+ (1) It must be practical to operate without a cache.
+
+ (2) The size of any accessible file must not be limited to the size of the
+     cache.
+
+ (3) The combined size of all opened files (this includes mapped libraries)
+     must not be limited to the size of the cache.
+
+ (4) The user should not be forced to download an entire file just to do a
+     one-off access of a small portion of it (such as might be done with the
+     "file" program).
+
+It instead serves the cache out in PAGE_SIZE chunks as and when requested by
+the netfs('s) using it.
+
+
+FS-Cache provides the following facilities:
+
+ (1) More than one cache can be used at once. Caches can be selected explicitly
+     by use of tags.
+
+ (2) Caches can be added / removed at any time.
+
+ (3) The netfs is provided with an interface that allows either party to
+     withdraw caching facilities from a file (required for (2)).
+
+ (4) The interface to the netfs returns as few errors as possible, preferring
+     rather to let the netfs remain oblivious.
+
+ (5) Cookies are used to represent indexes, files and other objects to the
+     netfs. The simplest cookie is just a NULL pointer - indicating nothing
+     cached there.
+
+ (6) The netfs is allowed to propose - dynamically - any index hierarchy it
+     desires, though it must be aware that the index search function is
+     recursive, stack space is limited, and indexes can only be children of
+     indexes.
+
+ (7) Data I/O is done direct to and from the netfs's pages. The netfs indicates
+     that page A is at index B of the data-file represented by cookie C, and
+     that it should be read or written. The cache backend may or may not start
+     I/O on that page, but if it does, a netfs callback will be invoked to
+     indicate completion. The I/O may be either synchronous or asynchronous.
+
+ (8) Cookies can be "retired" upon release. At this point FS-Cache will mark
+     them as obsolete and the index hierarchy rooted at that point will get
+     recycled.
+
+ (9) The netfs provides a "match" function for index searches. In addition to
+     saying whether a match was made or not, this can also specify that an
+     entry should be updated or deleted.
+
+
+FS-Cache maintains a virtual indexing tree in which all indexes, files, objects
+and pages are kept. Bits of this tree may actually reside in one or more
+caches.
+
+                                           FSDEF
+                                             |
+                        +------------------------------------+
+                        |                                    |
+                       NFS                                  AFS
+                        |                                    |
+           +--------------------------+                +-----------+
+           |                          |                |           |
+        homedir                     mirror          afs.org   redhat.com
+           |                          |                            |
+     +------------+           +---------------+              +----------+
+     |            |           |               |              |          |
+   00001        00002       00007           00125        vol00001   vol00002
+     |            |           |               |                         |
+ +---+---+     +-----+      +---+      +------+------+            +-----+----+
+ |   |   |     |     |      |   |      |      |      |            |     |    |
+PG0 PG1 PG2   PG0  XATTR   PG0 PG1   DIRENT DIRENT DIRENT        R/W   R/O  Bak
+                     |                                            |
+                    PG0                                       +-------+
+                                                              |       |
+                                                            00001   00003
+                                                              |
+                                                          +---+---+
+                                                          |   |   |
+                                                         PG0 PG1 PG2
+
+In the example above, you can see two netfs's being backed: NFS and AFS. These
+have different index hierarchies:
+
+ (*) The NFS primary index contains per-server indexes. Each server index is
+     indexed by NFS file handles to get data file objects. Each data file
+     objects can have an array of pages, but may also have further child
+     objects, such as extended attributes and directory entries. Extended
+     attribute objects themselves have page-array contents.
+
+ (*) The AFS primary index contains per-cell indexes. Each cell index contains
+     per-logical-volume indexes. Each of volume index contains up to three
+     indexes for the read-write, read-only and backup mirrors of those
+     volumes. Each of these contains vnode data file objects, each of which
+     contains an array of pages.
+
+The very top index is the FS-Cache master index in which individual netfs's
+have entries.
+
+Any index object may reside in more than one cache, provided it only has index
+children. Any index with non-index object children will be assumed to only
+reside in one cache.
+
+
+The netfs API to FS-Cache can be found in:
+
+	Documentation/filesystems/caching/netfs-api.txt
+
+The cache backend API to FS-Cache can be found in:
+
+	Documentation/filesystems/caching/backend-api.txt

The attached patch makes the kAFS filesystem in fs/afs/ use FS-Cache, and through it any attached caches.

---
warthog>diffstat -p1 fscache-afs-2614mm2.diff

 fs/Kconfig         |    7 +
 fs/afs/cache.h     |   27 -----
 fs/afs/cell.c      |  109 +++++++++++++----------
 fs/afs/cell.h      |   16 ---
 fs/afs/cmservice.c |    2 
 fs/afs/dir.c       |   15 +--
 fs/afs/file.c      |  224 ++++++++++++++++++++++++++++++++---------------
 fs/afs/fsclient.c  |    4 
 fs/afs/inode.c     |   43 ++++++---
 fs/afs/internal.h  |   24 +----
 fs/afs/main.c      |   24 ++---
 fs/afs/mntpt.c     |   12 +-
 fs/afs/proc.c      |    1 
 fs/afs/server.c    |    3 
 fs/afs/vlocation.c |  185 ++++++++++++++++++++++++---------------
 fs/afs/vnode.c     |  249 +++++++++++++++++++++++++++++++++++++++++++----------
 fs/afs/vnode.h     |   10 +-
 fs/afs/volume.c    |   78 ++++++----------
 fs/afs/volume.h    |   28 +----
 19 files changed, 655 insertions(+), 406 deletions(-)

diff -uNrp linux-2.6.14-mm2/fs/Kconfig linux-2.6.14-mm2-cachefs/fs/Kconfig
@@ -1880,6 +1880,13 @@ config AFS_FS
 
 	  If unsure, say N.
 
+config AFS_FSCACHE
+	bool "Provide AFS client caching support"
+	depends on AFS_FS && FSCACHE && EXPERIMENTAL
+	help
+	  Say Y here if you want AFS data to be cached locally on through the
+	  generic filesystem cache manager
+
 config RXRPC
 	tristate
 

diff -uNrp linux-2.6.14-mm2/fs/afs/cache.h linux-2.6.14-mm2-cachefs/fs/afs/cache.h
@@ -1,27 +0,0 @@
-/* cache.h: AFS local cache management interface
- *
- * Copyright (C) 2002 Red Hat, Inc. All Rights Reserved.
- * Written by David Howells ([email protected])
- *
- * This program is free software; you can redistribute it and/or
- * modify it under the terms of the GNU General Public License
- * as published by the Free Software Foundation; either version
- * 2 of the License, or (at your option) any later version.
- */
-
-#ifndef _LINUX_AFS_CACHE_H
-#define _LINUX_AFS_CACHE_H
-
-#undef AFS_CACHING_SUPPORT
-
-#include <linux/mm.h>
-#ifdef AFS_CACHING_SUPPORT
-#include <linux/cachefs.h>
-#endif
-#include "types.h"
-
-#ifdef __KERNEL__
-
-#endif /* __KERNEL__ */
-
-#endif /* _LINUX_AFS_CACHE_H */

diff -uNrp linux-2.6.14-mm2/fs/afs/cell.h linux-2.6.14-mm2-cachefs/fs/afs/cell.h
@@ -13,7 +13,7 @@
 #define _LINUX_AFS_CELL_H
 
 #include "types.h"
-#include "cache.h"
+#include <linux/fscache.h>
 
 #define AFS_CELL_MAX_ADDRS 15
 

@@ -21,16 +21,6 @@ extern volatile int afs_cells_being_purg
 
 /*****************************************************************************/
 /*
- * entry in the cached cell catalogue
- */
-struct afs_cache_cell
-{
-	char			name[64];	/* cell name (padded with NULs) */
-	struct in_addr		vl_servers[15];	/* cached cell VL servers */
-};
-
-/*****************************************************************************/
-/*
  * AFS cell record
  */
 struct afs_cell

@@ -39,8 +29,8 @@ struct afs_cell
 	struct list_head	link;		/* main cell list link */
 	struct list_head	proc_link;	/* /proc cell list link */
 	struct proc_dir_entry	*proc_dir;	/* /proc dir for this cell */
-#ifdef AFS_CACHING_SUPPORT
-	struct cachefs_cookie	*cache;		/* caching cookie */
+#ifdef CONFIG_AFS_FSCACHE
+	struct fscache_cookie	*cache;		/* caching cookie */
 #endif
 
 	/* server record management */

diff -uNrp linux-2.6.14-mm2/fs/afs/cmservice.c linux-2.6.14-mm2-cachefs/fs/afs/cmservice.c
@@ -24,7 +24,7 @@
 #include "internal.h"
 
 static unsigned afscm_usage;		/* AFS cache manager usage count */
-static struct rw_semaphore afscm_sem;	/* AFS cache manager start/stop semaphore */
+static DECLARE_RWSEM(afscm_sem);	/* AFS cache manager start/stop semaphore */
 
 static int afscm_new_call(struct rxrpc_call *call);
 static void afscm_attention(struct rxrpc_call *call);

diff -uNrp linux-2.6.14-mm2/fs/afs/dir.c linux-2.6.14-mm2-cachefs/fs/afs/dir.c
@@ -145,7 +145,7 @@ static inline void afs_dir_check_page(st
 	qty /= sizeof(union afs_dir_block);
 
 	/* check them */
-	dbuf = page_address(page);
+	dbuf = kmap_atomic(page, KM_USER0);
 	for (tmp = 0; tmp < qty; tmp++) {
 		if (dbuf->blocks[tmp].pagehdr.magic != AFS_DIR_MAGIC) {
 			printk("kAFS: %s(%lu): bad magic %d/%d is %04hx\n",

@@ -154,12 +154,12 @@ static inline void afs_dir_check_page(st
 			goto error;
 		}
 	}
+	kunmap_atomic(dbuf, KM_USER0);
 
-	SetPageChecked(page);
 	return;
 
  error:
-	SetPageChecked(page);
+	kunmap_atomic(dbuf, KM_USER0);
 	SetPageError(page);
 
 } /* end afs_dir_check_page() */

@@ -170,7 +170,6 @@ static inline void afs_dir_check_page(st
  */
 static inline void afs_dir_put_page(struct page *page)
 {
-	kunmap(page);
 	page_cache_release(page);
 
 } /* end afs_dir_put_page() */

@@ -190,11 +189,9 @@ static struct page *afs_dir_get_page(str
 			       NULL);
 	if (!IS_ERR(page)) {
 		wait_on_page_locked(page);
-		kmap(page);
 		if (!PageUptodate(page))
 			goto fail;
-		if (!PageChecked(page))
-			afs_dir_check_page(dir, page);
+		afs_dir_check_page(dir, page);
 		if (PageError(page))
 			goto fail;
 	}

@@ -359,7 +356,7 @@ static int afs_dir_iterate(struct inode 
 
 		limit = blkoff & ~(PAGE_SIZE - 1);
 
-		dbuf = page_address(page);
+		dbuf = kmap_atomic(page, KM_USER0);
 
 		/* deal with the individual blocks stashed on this page */
 		do {

@@ -368,6 +365,7 @@ static int afs_dir_iterate(struct inode 
 			ret = afs_dir_iterate_block(fpos, dblock, blkoff,
 						    cookie, filldir);
 			if (ret != 1) {
+				kunmap_atomic(dbuf, KM_USER0);
 				afs_dir_put_page(page);
 				goto out;
 			}

@@ -376,6 +374,7 @@ static int afs_dir_iterate(struct inode 
 
 		} while (*fpos < dir->i_size && blkoff < limit);
 
+		kunmap_atomic(dbuf, KM_USER0);
 		afs_dir_put_page(page);
 		ret = 0;
 	}

diff -uNrp linux-2.6.14-mm2/fs/afs/fsclient.c linux-2.6.14-mm2-cachefs/fs/afs/fsclient.c
@@ -398,6 +398,8 @@ int afs_rxfs_fetch_file_status(struct af
 		bp++; /* spare6 */
 	}
 
+	_debug("Data Version %llx\n", vnode->status.version);
+
 	/* success */
 	ret = 0;
 

@@ -408,7 +410,7 @@ int afs_rxfs_fetch_file_status(struct af
  out_put_conn:
 	afs_server_release_callslot(server, &callslot);
  out:
-	_leave("");
+	_leave(" = %d", ret);
 	return ret;
 
  abort:

diff -uNrp linux-2.6.14-mm2/fs/afs/internal.h linux-2.6.14-mm2-cachefs/fs/afs/internal.h
@@ -16,15 +16,17 @@
 #include <linux/kernel.h>
 #include <linux/fs.h>
 #include <linux/pagemap.h>
+#include <linux/fscache.h>
 
 /*
  * debug tracing
  */
-#define kenter(FMT, a...)	printk("==> %s("FMT")\n",__FUNCTION__ , ## a)
-#define kleave(FMT, a...)	printk("<== %s()"FMT"\n",__FUNCTION__ , ## a)
-#define kdebug(FMT, a...)	printk(FMT"\n" , ## a)
-#define kproto(FMT, a...)	printk("### "FMT"\n" , ## a)
-#define knet(FMT, a...)		printk(FMT"\n" , ## a)
+#define __kdbg(FMT, a...)	printk("[%05d] "FMT"\n", current->pid , ## a)
+#define kenter(FMT, a...)	__kdbg("==> %s("FMT")", __FUNCTION__ , ## a)
+#define kleave(FMT, a...)	__kdbg("<== %s()"FMT, __FUNCTION__ , ## a)
+#define kdebug(FMT, a...)	__kdbg(FMT , ## a)
+#define kproto(FMT, a...)	__kdbg("### "FMT , ## a)
+#define knet(FMT, a...)		__kdbg(FMT , ## a)
 
 #ifdef __KDEBUG
 #define _enter(FMT, a...)	kenter(FMT , ## a)

@@ -56,9 +58,6 @@ static inline void afs_discard_my_signal
  */
 extern struct rw_semaphore afs_proc_cells_sem;
 extern struct list_head afs_proc_cells;
-#ifdef AFS_CACHING_SUPPORT
-extern struct cachefs_index_def afs_cache_cell_index_def;
-#endif
 
 /*
  * dir.c

@@ -72,11 +71,6 @@ extern struct file_operations afs_dir_fi
 extern struct address_space_operations afs_fs_aops;
 extern struct inode_operations afs_file_inode_operations;
 
-#ifdef AFS_CACHING_SUPPORT
-extern int afs_cache_get_page_cookie(struct page *page,
-				     struct cachefs_page **_page_cookie);
-#endif
-
 /*
  * inode.c
  */

@@ -97,8 +91,8 @@ extern void afs_key_unregister(void);
 /*
  * main.c
  */
-#ifdef AFS_CACHING_SUPPORT
-extern struct cachefs_netfs afs_cache_netfs;
+#ifdef CONFIG_AFS_FSCACHE
+extern struct fscache_netfs afs_cache_netfs;
 #endif
 
 /*

diff -uNrp linux-2.6.14-mm2/fs/afs/main.c linux-2.6.14-mm2-cachefs/fs/afs/main.c
@@ -1,6 +1,6 @@
 /* main.c: AFS client file system
  *
- * Copyright (C) 2002 Red Hat, Inc. All Rights Reserved.
+ * Copyright (C) 2002,5 Red Hat, Inc. All Rights Reserved.
  * Written by David Howells ([email protected])
  *
  * This program is free software; you can redistribute it and/or

@@ -14,11 +14,11 @@
 #include <linux/init.h>
 #include <linux/sched.h>
 #include <linux/completion.h>
+#include <linux/fscache.h>
 #include <rxrpc/rxrpc.h>
 #include <rxrpc/transport.h>
 #include <rxrpc/call.h>
 #include <rxrpc/peer.h>
-#include "cache.h"
 #include "cell.h"
 #include "server.h"
 #include "fsclient.h"

@@ -51,12 +51,11 @@ static struct rxrpc_peer_ops afs_peer_op
 struct list_head afs_cb_hash_tbl[AFS_CB_HASH_COUNT];
 DEFINE_SPINLOCK(afs_cb_hash_lock);
 
-#ifdef AFS_CACHING_SUPPORT
-static struct cachefs_netfs_operations afs_cache_ops = {
-	.get_page_cookie	= afs_cache_get_page_cookie,
+#ifdef CONFIG_AFS_FSCACHE
+static struct fscache_netfs_operations afs_cache_ops = {
 };
 
-struct cachefs_netfs afs_cache_netfs = {
+struct fscache_netfs afs_cache_netfs = {
 	.name			= "afs",
 	.version		= 0,
 	.ops			= &afs_cache_ops,

@@ -83,10 +82,9 @@ static int __init afs_init(void)
 	if (ret < 0)
 		return ret;
 
-#ifdef AFS_CACHING_SUPPORT
+#ifdef CONFIG_AFS_FSCACHE
 	/* we want to be able to cache */
-	ret = cachefs_register_netfs(&afs_cache_netfs,
-				     &afs_cache_cell_index_def);
+	ret = fscache_register_netfs(&afs_cache_netfs);
 	if (ret < 0)
 		goto error;
 #endif

@@ -137,8 +135,8 @@ static int __init afs_init(void)
 	afs_key_unregister();
  error_cache:
 #endif
-#ifdef AFS_CACHING_SUPPORT
-	cachefs_unregister_netfs(&afs_cache_netfs);
+#ifdef CONFIG_AFS_FSCACHE
+	fscache_unregister_netfs(&afs_cache_netfs);
  error:
 #endif
 	afs_cell_purge();

@@ -167,8 +165,8 @@ static void __exit afs_exit(void)
 #ifdef CONFIG_KEYS_TURNED_OFF
 	afs_key_unregister();
 #endif
-#ifdef AFS_CACHING_SUPPORT
-	cachefs_unregister_netfs(&afs_cache_netfs);
+#ifdef CONFIG_AFS_FSCACHE
+	fscache_unregister_netfs(&afs_cache_netfs);
 #endif
 	afs_proc_cleanup();
 

diff -uNrp linux-2.6.14-mm2/fs/afs/mntpt.c linux-2.6.14-mm2-cachefs/fs/afs/mntpt.c
@@ -82,7 +82,7 @@ int afs_mntpt_check_symlink(struct afs_v
 
 	ret = -EIO;
 	wait_on_page_locked(page);
-	buf = kmap(page);
+	buf = kmap_atomic(page, KM_USER0);
 	if (!PageUptodate(page))
 		goto out_free;
 	if (PageError(page))

@@ -105,7 +105,7 @@ int afs_mntpt_check_symlink(struct afs_v
 	ret = 0;
 
  out_free:
-	kunmap(page);
+	kunmap_atomic(buf, KM_USER0);
 	page_cache_release(page);
  out:
 	_leave(" = %d", ret);

@@ -195,9 +195,9 @@ static struct vfsmount *afs_mntpt_do_aut
 	if (!PageUptodate(page) || PageError(page))
 		goto error;
 
-	buf = kmap(page);
+	buf = kmap_atomic(page, KM_USER0);
 	memcpy(devname, buf, size);
-	kunmap(page);
+	kunmap_atomic(buf, KM_USER0);
 	page_cache_release(page);
 	page = NULL;
 

@@ -276,12 +276,12 @@ static void *afs_mntpt_follow_link(struc
  */
 static void afs_mntpt_expiry_timed_out(struct afs_timer *timer)
 {
-	kenter("");
+//	kenter("");
 
 	mark_mounts_for_expiry(&afs_vfsmounts);
 
 	afs_kafstimod_add_timer(&afs_mntpt_expiry_timer,
 				afs_mntpt_expiry_timeout * HZ);
 
-	kleave("");
+//	kleave("");
 } /* end afs_mntpt_expiry_timed_out() */

diff -uNrp linux-2.6.14-mm2/fs/afs/proc.c linux-2.6.14-mm2-cachefs/fs/afs/proc.c
@@ -177,6 +177,7 @@ int afs_proc_init(void)
  */
 void afs_proc_cleanup(void)
 {
+	remove_proc_entry("rootcell", proc_afs);
 	remove_proc_entry("cells", proc_afs);
 
 	remove_proc_entry("fs/afs", NULL);

diff -uNrp linux-2.6.14-mm2/fs/afs/server.c linux-2.6.14-mm2-cachefs/fs/afs/server.c
@@ -377,7 +377,6 @@ int afs_server_request_callslot(struct a
 	else if (list_empty(&server->fs_callq)) {
 		/* no one waiting */
 		server->fs_conn_cnt[nconn]++;
-		spin_unlock(&server->fs_lock);
 	}
 	else {
 		/* someone's waiting - dequeue them and wake them up */

@@ -395,9 +394,9 @@ int afs_server_request_callslot(struct a
 		}
 		pcallslot->ready = 1;
 		wake_up_process(pcallslot->task);
-		spin_unlock(&server->fs_lock);
 	}
 
+	spin_unlock(&server->fs_lock);
 	rxrpc_put_connection(callslot->conn);
 	callslot->conn = NULL;
 

diff -uNrp linux-2.6.14-mm2/fs/afs/vnode.h linux-2.6.14-mm2-cachefs/fs/afs/vnode.h
@@ -13,9 +13,9 @@
 #define _LINUX_AFS_VNODE_H
 
 #include <linux/fs.h>
+#include <linux/fscache.h>
 #include "server.h"
 #include "kafstimod.h"
-#include "cache.h"
 
 #ifdef __KERNEL__
 

@@ -32,8 +32,8 @@ struct afs_cache_vnode
 	afs_dataversion_t	data_version;	/* data version */
 };
 
-#ifdef AFS_CACHING_SUPPORT
-extern struct cachefs_index_def afs_vnode_cache_index_def;
+#ifdef CONFIG_AFS_FSCACHE
+extern struct fscache_cookie_def afs_vnode_cache_index_def;
 #endif
 
 /*****************************************************************************/

@@ -47,8 +47,8 @@ struct afs_vnode
 	struct afs_volume	*volume;	/* volume on which vnode resides */
 	struct afs_fid		fid;		/* the file identifier for this inode */
 	struct afs_file_status	status;		/* AFS status info for this file */
-#ifdef AFS_CACHING_SUPPORT
-	struct cachefs_cookie	*cache;		/* caching cookie */
+#ifdef CONFIG_AFS_FSCACHE
+	struct fscache_cookie	*cache;		/* caching cookie */
 #endif
 
 	wait_queue_head_t	update_waitq;	/* status fetch waitqueue */

diff -uNrp linux-2.6.14-mm2/fs/afs/volume.h linux-2.6.14-mm2-cachefs/fs/afs/volume.h
@@ -12,11 +12,11 @@
 #ifndef _LINUX_AFS_VOLUME_H
 #define _LINUX_AFS_VOLUME_H
 
+#include <linux/fscache.h>
 #include "types.h"
 #include "fsclient.h"
 #include "kafstimod.h"
 #include "kafsasyncd.h"
-#include "cache.h"
 
 #define __packed __attribute__((packed))
 

@@ -47,24 +47,6 @@ struct afs_cache_vlocation
 	time_t			rtime;		/* last retrieval time */
 };
 
-#ifdef AFS_CACHING_SUPPORT
-extern struct cachefs_index_def afs_vlocation_cache_index_def;
-#endif
-
-/*****************************************************************************/
-/*
- * volume -> vnode hash table entry
- */
-struct afs_cache_vhash
-{
-	afs_voltype_t		vtype;		/* which volume variation */
-	uint8_t			hash_bucket;	/* which hash bucket this represents */
-} __attribute__((packed));
-
-#ifdef AFS_CACHING_SUPPORT
-extern struct cachefs_index_def afs_volume_cache_index_def;
-#endif
-
 /*****************************************************************************/
 /*
  * AFS volume location record

@@ -75,8 +57,8 @@ struct afs_vlocation
 	struct list_head	link;		/* link in cell volume location list */
 	struct afs_timer	timeout;	/* decaching timer */
 	struct afs_cell		*cell;		/* cell to which volume belongs */
-#ifdef AFS_CACHING_SUPPORT
-	struct cachefs_cookie	*cache;		/* caching cookie */
+#ifdef CONFIG_AFS_FSCACHE
+	struct fscache_cookie	*cache;		/* caching cookie */
 #endif
 	struct afs_cache_vlocation vldb;	/* volume information DB record */
 	struct afs_volume	*vols[3];	/* volume access record pointer (index by type) */

@@ -111,8 +93,8 @@ struct afs_volume
 	atomic_t		usage;
 	struct afs_cell		*cell;		/* cell to which belongs (unrefd ptr) */
 	struct afs_vlocation	*vlocation;	/* volume location */
-#ifdef AFS_CACHING_SUPPORT
-	struct cachefs_cookie	*cache;		/* caching cookie */
+#ifdef CONFIG_AFS_FSCACHE
+	struct fscache_cookie	*cache;		/* caching cookie */
 #endif
 	afs_volid_t		vid;		/* volume ID */
 	afs_voltype_t __packed	type;		/* type of volume */

The attached patch adds CacheFS, a caching facility that uses a block device as the cache by mounting a quasi-filesystem on it that provides caching facilities rather than the usual file interface.

CacheFS stores its metadata in a wandering tree. Anything in the current tree is (more or less) immutable. Changes in the block holding the root of the tree and the block allocation lists are tracked by a journal. The journal does not store any specific information about changes to the content or the structure of the tree.

CacheFS creates an internal inode to cover the entire block device. Metadata blocks on disk are attached to this as pages. Pages are migrated from one backing block to another as the blocks become part of the metadata tree and thus immutable, hence the need for the per-task radix-tree pre-allocation for several pages in one go: insertion may have to fan out part of the tree. What we want to do is to keep the same page for as long as possible; and just change the page->index as the block migrates on disk.

CacheFS is not quite complete. Certain things need to be added or completed:

(*) Metadata readahead needs to be added.

(*) Tree scanning needs to be speeded up, probably with readahead.

(*) Tree scanning needs to build a culling list (currently disabled).

(*) Tree culling needs to be reworked (currently disabled).

(*) There needs to be a culling policy created.

(*) Some bugs need squashing still.

---
warthog>diffstat -p1 fscache-cachefs-2614mm2.diff

 fs/Kconfig                      |   21 
 fs/Makefile                     |    1 
 fs/cachefs/Makefile             |   37 
 fs/cachefs/allocator.c          | 1382 +++++++++++++++++++++++++++++++++
 fs/cachefs/cachefs-debug.h      |  132 +++
 fs/cachefs/cachefs-inode.h      |   64 +
 fs/cachefs/cachefs-int.h        |  739 +++++++++++++++++
 fs/cachefs/cachefs-layout.h     |  312 +++++++
 fs/cachefs/inode.c              |  224 +++++
 fs/cachefs/interface.c          |  724 +++++++++++++++++
 fs/cachefs/journal-replay.c     |  485 +++++++++++
 fs/cachefs/journal.c            |  483 +++++++++++
 fs/cachefs/kcachefsd.c          |  278 ++++++
 fs/cachefs/main.c               |  224 +++++
 fs/cachefs/meta-aops.c          |  794 +++++++++++++++++++
 fs/cachefs/meta-misc.c          |  348 ++++++++
 fs/cachefs/operation.c          |  571 +++++++++++++
 fs/cachefs/reaper.c             |  120 ++
 fs/cachefs/recycling.c          |  966 +++++++++++++++++++++++
 fs/cachefs/rootdir.c            |  146 +++
 fs/cachefs/status.c             |  234 +++++
 fs/cachefs/super.c              | 1345 ++++++++++++++++++++++++++++++++
 fs/cachefs/tree-cull.c          |   19 
 fs/cachefs/tree-data.c          | 1669 ++++++++++++++++++++++++++++++++++++++++
 fs/cachefs/tree-delete.c        |  597 ++++++++++++++
 fs/cachefs/tree-insert-fanout.c | 1126 ++++++++++++++++++++++++++
 fs/cachefs/tree-insert.c        |  675 ++++++++++++++++
 fs/cachefs/tree-keys.c          |  587 ++++++++++++++
 fs/cachefs/tree-list.c          |  544 +++++++++++++
 fs/cachefs/tree-lookup.c        |  598 ++++++++++++++
 fs/cachefs/tree-misc.c          |  346 ++++++++
 fs/cachefs/tree-move.c          |  299 +++++++
 fs/cachefs/tree-node.c          |  284 ++++++
 fs/cachefs/tree-scan.c          |  972 +++++++++++++++++++++++
 fs/cachefs/tree-update.c        |  175 ++++
 35 files changed, 17521 insertions(+)

diff -uNrp linux-2.6.14-mm2/fs/Kconfig linux-2.6.14-mm2-cachefs/fs/Kconfig
@@ -524,6 +524,27 @@ config FUSE_FS
 
 	  See Documentation/filesystems/caching/fscache.txt for more information.
 
+config CACHEFS
+	tristate "Filesystem caching filesystem"
+	depends on FSCACHE
+	help
+	  This filesystem acts as a cache for other filesystems - primarily
+	  networking filesystems - rather than thus allowing fast local disc to
+	  enhance the speed of slower devices.
+
+	  It is a filesystem so that raw block devices can be made use of more
+	  efficiently, without suffering any overhead from intermediary
+	  filesystems. This does not, however, preclude files being used as
+	  cache devices; this is possible by making use of the loopback block
+	  device driver.
+
+	  The cache can be journalled so that the cache contents aren't
+	  destroyed in the event of a power failure.
+
+	  See Documentation/filesystems/caching/cachefs.txt for more information.
+
+endmenu
+
 menu "CD-ROM/DVD Filesystems"
 
 config ISO9660_FS

diff -uNrp linux-2.6.14-mm2/fs/Makefile linux-2.6.14-mm2-cachefs/fs/Makefile
@@ -103,6 +103,7 @@ obj-$(CONFIG_AFS_FS)		+= afs/
 obj-$(CONFIG_BEFS_FS)		+= befs/
 obj-$(CONFIG_HOSTFS)		+= hostfs/
 obj-$(CONFIG_HPPFS)		+= hppfs/
+obj-$(CONFIG_CACHEFS)		+= cachefs/
 obj-$(CONFIG_DEBUG_FS)		+= debugfs/
 obj-$(CONFIG_CONFIGFS_FS)	+= configfs/
 obj-$(CONFIG_OCFS2_FS)		+= ocfs2/

diff -uNrp linux-2.6.14-mm2/fs/cachefs/Makefile linux-2.6.14-mm2-cachefs/fs/cachefs/Makefile

diff -uNrp linux-2.6.14-mm2/fs/cachefs/tree-cull.c linux-2.6.14-mm2-cachefs/fs/cachefs/tree-cull.c

Part of the diff is not shown here. View the raw message.

The attached patch adds documentation for CacheFS.

---
warthog>diffstat -p1 fscache-cachefs-docs-2614mm2.diff

 Documentation/filesystems/caching/cachefs.txt |  375 ++++++++++++++++++++++++++
 1 files changed, 375 insertions(+)

diff -uNrp linux-2.6.14-mm2/Documentation/filesystems/caching/cachefs.txt linux-2.6.14-mm2-cachefs/Documentation/filesystems/caching/cachefs.txt
@@ -0,0 +1,375 @@
+			  ===========================
+			  CacheFS: Caching Filesystem
+			  ===========================
+
+========
+OVERVIEW
+========
+
+CacheFS is a backend for the general filesystem cache facility.
+
+CacheFS uses a block device directly rather than a bunch of files under an
+already mounted filesystem. For why this is so, see further on. If necessary,
+however, a file can be loopback mounted as a cache.
+
+CacheFS is based on a wandering tree approach. This means that data already on
+the disk are not changed (more or less), only replaced. This means that
+CacheFS provides both metadata integrity and data integrity. There is a small,
+simple journal that tracks the state of the tree and the block allocation
+management. Should the power be cut to a computer, or should it crash, all
+changes made to the cache since the last time the journal was cranked will be
+lost; but a valid tree will remain, albeit slightly out of date.
+
+
+========
+MOUNTING
+========
+
+Since CacheFS is actually a quasi-filesystem, it requires a block device behind
+it. The way to give it one is to mount it as cachefs type on a directory
+somewhere. The mounted filesystem will then present the user with a single file
+describing the current cache management status.
+
+There are a number of mount options that can be provided when the cache is
+mounted:
+
+ (*) -o tag=<name>
+
+     This tells FS-Cache the name by which netfs's will refer to the cache.
+     This is not strictly a necessity; if it's not given, a tag will be
+     invented based on the major and minor numbers of the block device. If the
+     netfs doesn't give FS-Cache any specific instructions, the first cache in
+     the list will be picked by default.
+
+ (*) -o wander=<n>
+
+     Set the wander timer so that CacheFS will commit the journal that long
+     after a change is made if nothing else causes the tree to wander.
+
+     n may be in the range 0 to 3600. If n is 0 then automatic wandering will
+     be disabled, otherwise it's a number of seconds. The tree is also forced
+     to wander by allocator underrun, sync and unmounting the cache.
+
+     A smaller number means that the cache will be more up to date if the power
+     fails, but that the allocator will cycle faster and blocks will be
+     replaced more often, lowering performance.
+
+ (*) -o autodel
+
+     All files should be deleted when the last reference to them is dropped.
+     This is primarily for debugging purposes.
+
+For instance, the cache might by mounted thusly:
+
+	root>mount -t cachefs /dev/hdg9 /cache-hdg9 -o tag=mycache
+	root>ls -1 /cache-hdg9
+	status
+
+However, a block device that's going to be used for a cache must be prepared
+before it can be mounted initially. This is done very simply by:
+
+	echo "cachefs___" >/dev/hdg9
+
+During the initial mount, the basic structure will be written into the cache
+and then the journal will be replayed as during a normal mount.
+
+Note that trying to mount a cache read only will result in an error.
+
+
+=============================================
+WHY A BLOCK DEVICE? WHY NOT A BUNCH OF FILES?
+=============================================
+
+CacheFS is backed by a block device rather than being backed by a bunch of
+files on a filesystem. This confers several advantages:
+
+ (1) Performance.
+
+     Going directly to a block device means that we can DMA directly to/from
+     the the netfs's pages. If another filesystem was managing the backing
+     store, everything would have to be copied between pages. Whilst DirectIO
+     does exist, it doesn't appear easy to make use of in this situation.
+
+     New address space or file operations could be added to make it possible to
+     persuade a backing diskfs to generate block I/O directly to/from disk
+     blocks under its control, but that then means the diskfs has to keep track
+     of I/O requests to pages not under its control.
+
+     Furthermore, we only have to do one lot of readahead calculations, not
+     two; in the diskfs backing case, the netfs would do one and the diskfs
+     would also do one.
+
+ (2) Memory.
+
+     Using a block device means that we have a lower memory usage - all data
+     pages belong to the netfs we're backing. If we used a filesystem, we would
+     have twice as many pages at certain points - one from the netfs and one
+     from the backing diskfs. In the backing diskfs model, under situations of
+     memory pressure, we'd have to allocate or keep around a diskfs page to be
+     able to write out a netfs page; or else we'd need to be able to punch a
+     hole in the backing file.
+
+     Furthermore, whilst we have to keep a certain amount of memory around for
+     every netfs inode we're backing, a backing diskfs would have to keep the
+     inode, dentry and possibly a file struct, in addition to FS-specific
+     stuff, thus adding to the burden.
+
+ (3) Holes.
+
+     The cache uses holes in files to indicate to the netfs that it hasn't yet
+     downloaded the data for that page.
+
+     Since CacheFS is its own filesystem, it can support holes in files
+     trivially. Running on top of another diskfs would limit us to using ones
+     that can support holes.
+
+     Furthermore, it would have to be made possible to detect holes in a diskfs
+     file, rather than just seeing zero filled blocks.
+
+ (4) Integrity
+
+     CacheFS maintains filesystem integrity through its use of a wandering
+     tree. It (for the most part) replaces blocks that need updating rather
+     than overwriting them in place. That said, certain non-structural changes
+     - such as the updating of atimes - are done in place.
+
+     CacheFS gets data integrity for free - more or less - by treating the
+     data exactly as it treats the metadata. Data blocks that need changing
+     are simply replaced. Whilst this does mean that the meta data pointing to
+     it also needs updating, quite often these changes elide between journal
+     updates.
+
+     Knowing that your cache is in a good state is vitally important if you,
+     say, put /usr on AFS. Some organisations put everything barring /etc,
+     /sbin, /lib and /var on AFS and have an enormous cache on every
+     computer. Imagine if the power goes out and renders every cache
+     inconsistent, requiring all the computers to re-initialise their caches
+     when the power comes back on...
+
+ (5) Disk Space.
+
+     Whilst the block device does set a hard ceiling on the amount of space
+     available, CacheFS can guarantee that all that space will be available to
+     the cache. On a diskfs-backed cache, the administrator would probably want
+     to set a cache size limit, but the system wouldn't be able guarantee that
+     all that space would be available to the cache - not unless that cache was
+     on a partition of its own.
+
+     Furthermore, with a diskfs-backed cache, if the recycler starts to reclaim
+     cache files to make space, the freed blocks may just be eaten directly by
+     userspace programs, potentially resulting in the entire cache being
+     consumed. Alternatively, netfs operations may end up being held up because
+     the cache can't get blocks on which to store the data.
+
+ (6) Users.
+
+     Users can't so easily go into CacheFS and run amok. The worst they can do
+     is cause bits of the cache to be recycled early. With a diskfs-backed
+     cache, they can do all sorts of bad things to the files belonging to the
+     cache, and they can do this quite by accident.
+
+
+On the other hand, there would be some advantages to using a file-based cache
+rather than a blockdev-based cache:
+
+ (1) Having to copy to a diskfs's page would mean that a netfs could just make
+     the copy and then assume its own page is ready to go.
+
+ (2) Backing onto a diskfs wouldn't require a committed block device. You would
+     just nominate a directory and go from there. With CacheFS you have to
+     repartition or install an extra drive to make use of it in an existing
+     system (though the loopback device offers a way out).
+
+ (3) You could easily make your cache bigger if the diskfs has plenty of space,
+     you could even go across multiple mountpoints. This last isn't so much of
+     a problem as you can have multiple caches.
+
+
+======================
+CACHEFS ON-DISK LAYOUT
+======================
+
+The filesystem is divided into a number of parts:
+
+  0	+---------------------------+
+	|        Superblock         |
+  1	+---------------------------+
+	|         Journal           |
+  17	+---------------------------+
+	|                           |
+	|           Data            |
+	|                           |
+ END	+---------------------------+
+
+The superblock contains the filesystem ID tags and pointers to all the other
+regions. All blocks are PAGE_SIZE in size and the blocks are numbered, starting
+with the superblock as 0. Using 32-bit block pointers, a maximum number of
+0xffffffff blocks can be accessed, meaning that the maximum cache size is ~16TB
+for 4KB pages.
+
+CachefS will use the endianness and block size details from the kernel that
+created a cache, and it will not permit the cache to be mounted if these
+details differ from what was written on disk.
+
+The journal consists of a set of entries of sector size that keep track of the
+current root block of the tree and the various recycling and allocation lists.
+
+The journal scanned on mounting to find the most recent fully committed tree
+root, and that will be used. Any changes that were made but not connected to
+the tree rooted in the latest journal entry will be lost.
+
+The data region holds a number of things:
+
+  (1) The Metadata Tree
+
+      As previously mentioned, CacheFS is tree based. The journal points to the
+      current committed root of the tree. The structure of this tree is
+      discussed below:
+
+  (2) Data Blocks
+
+      These are fragments of files that are cached on the behalf of network
+      filesystems.
+
+  (4) Allocation, Recycling and Reclamation Stacks and Free Blocks
+
+      The free blocks of the filesystem are kept in either the two allocation
+      stacks if they're laundered and ready to be used, or the reclamation
+      stack if they'll be ready once the journal has ticked over. Note that
+      stacks are used in order that committed stack nodes don't have to be
+      changed - we can just add another block on the front and change the stack
+      top pointer in the journal.
+
+      There are also two stacks associated with recycling trees of data blocks
+      from deleted nodes. These are processed in the background by kcachefsd
+      and their components all get transferred to the reclamation stacks and
+      thence to the allocation stacks.
+
+
+============================
+CACHEFS METADATA NODE LAYOUT
+============================
+
+The CacheFS metadata tree has its layout based around the filesystem block size
+(PAGE_SIZE) and the sector size of the underlying device (512 bytes normally).
+
+Each "node" in the tree is mapped onto a single block and contains a number of
+slots of sector size, aligned on sector boundaries:
+
+	+-------+----------+
+	|	|  SLOT 0  |
+	|	+----------+
+	|	|  SLOT 1  |
+	|	+----------+
+	|	|  SLOT 2  |
+	|	+----------+
+	|	|  SLOT 3  |
+	| NODE	+----------+
+	|	|  SLOT 4  |
+	|	+----------+
+	|	|  SLOT 5  |
+	|	+----------+
+	|	|  SLOT 6  |
+	|	+----------+
+	|	|  SLOT 7  |
+	+-------+----------+
+
+Each slot can either be empty or it can hold a "leaf". There are a number of
+types of leaves:
+
+ (1) Index Object Leaf.
+ (2) Data File Object Leaf.
+ (3) Other Object Leaf.
+
+     These three all look exactly the same on disk. They have the following
+     attributes:
+
+	- The object type.
+	- A unique object ID.
+	- The parent's object ID.
+	- A netfs key and key length.
+	- A digest of the netfs key, parent object ID and netfs key length.
+	- Netfs auxilliary data.
+	- The inode maximum size.
+	- The last time this object was accessed.
+	- The netfs's name for the class of this object.
+	- A tree of data pages, the depth of that tree and the number of blocks
+ 	  it contains.
+
+     In general, any type of object can have data or child objects; however,
+     indexes aren't permitted data and non-indexes aren't permitted indexes as
+     children.
+
+ (4) Pointer Leaf.
+
+     This is simply a leaf that is entirely given over to pointers to other
+     blocks (it can also contain null pointers).
+
+ (5) Shortcut Leaf.
+
+     This is a leaf that permits a chunk of keyspace to be skipped, allowing
+     the path through the tree to be shortened in some extreme cases.
+
+Note that pointer leaves can be distinguished from other leaf types by the
+second pointer slot in the leaf. If this points into the journal, then it
+actually indicates the type of one of the other types of leaf.
+
+
+===============================
+CACHEFS METADATA TREE STRUCTURE
+===============================
+
+The CacheFS metadata tree is navigated by rigidly partitioned key space. For a
+4KB page size, each step along the path of the tree consumes 10 bits of the key
+(a "subkey"), assuming bit 0 of byte 0 to be the first bit of the key:
+
+	LEVEL 0		LEVEL 1		LEVEL 2		LEVEL 3		LEVEL 4
+
+	+-------+	+-------+	+-------+	+-------+	+-------+
+	| PTR	|------>| PTR	|------>| PTR	|------>| PTR	|------>| LEAF	|
+	| LEAF	|	|	|	|	|	| PTR	|---+	| LEAF	|
+	| PTR	|	|	|	|	|	|	|   |	| LEAF	|
+	+-------+	+-------+	+-------+	+-------+   |	+-------+
+								    |
+								    |	+-------+
+								    +-->| LEAF	|
+									|	|
+									|	|
+									+-------+
+
+Whilst this would seem to be horribly inefficient, there are a number of
+optimisations that help to make the scheme much more efficient:
+
+ (1) No path is longer than it has to be. A node can hold more than one leaf,
+     so we don't bother fanning out a node that isn't full to overflowing.
+
+	+-------+	+-------+	+-------+	+-------+	+-------+
+	| PTR	|------>| PTR	|------>| PTR	|------>| PTR	|------>| LEAF	|
+	| LEAF	|	|	|	|	|	| LEAF	|	| LEAF	|
+	| PTR	|	|	|	|	|	|	|	| LEAF	|
+	+-------+	+-------+	+-------+	+-------+	+-------+
+
+ (2) If a path to the point at which a number of nodes can be distinguished is
+     made up of a line of nodes, each of which contains one pointer, then part
+     of the path can be made up of a shortcut leaf pointing to a node. The
+     shortcut represents several adjacent nodes.
+
+	+-------+	+-------+	+-------+
+	| SHORT	|------>| PTR	|------>| LEAF	|
+	| LEAF	|	| LEAF	|	| LEAF	|
+	| PTR	|	|	|	| LEAF	|
+	+-------+	+-------+	+-------+
+
+ (3) With a digest function that produces a reasonably even distibution based
+     on the key set presented, you get, for the most part, the shortest paths
+     everywhere.
+
+ (4) With a digest function that produces a certain amount of clumping bits of
+     the tree wind up staying in memory longer because they're referred to more
+     often. Also with a certain amount of clumping the tree ends up being less
+     sparse and thus occupies less disk space.
+
+ (5) It is assumed that if a node has a non-null pointer in a pointer leaf at
+     the location indexed by the subkey for that level of the key you're
+     looking for, then the leaf must lie behind that pointer, if it exists.
+     Otherwise you just have to look in the current node and no further.

Ok, interesting, and I like most of what I see.. But why do you have that horrible "FSCACHE_NEGATIVE_COOKIE" thing?

We normally call that thing "NULL", and we test for it with code like "if (!cookie)" instead of making up really nasty (and apparently misleading) names.

The reason I say "misleading" is that a real negative cache entry doesn't mean that the entry isn't cached, it means that it positively does not exist. Which is something different from what you seem to be saying if I read the patch right. From my quick reading, it looks like you use that "NEGATIVE" not as a negative cache, but as a "I don't have this cached" cache. Which is not negative at all.

(The difference is like the difference between a "hole" in a file and a "don't know what this page is". One is real knowledge - and in UNIX means that it's filled with zero - and the other one means that you have to go look what the contents are).

And if it _is_ properly named (ie it really does mean "this entry positively does not exist") then it shouldn't have the same representation as NULL, because NULL really is traditionally used for "unknown" rather than "known to not exist".

So depending on which it is, I really think you should either have

- just use NULL for "don't know"

or

- use #define FSCACHE_NEGATIVE_COOKIE ((struct fscache_cookie *)-1) for "this is known to not exist".

(and quite often, you might well want to have both).

True negative caches are fairly unusual, but the "file hole" thing is one example, and a negative dentry (dentry->d_inode = NULL) is another. It's a very useful concept, and it's very distinct from "not in the cache".

Linus

Less impressed. It (still) adds a very large amount of tricksy code which pokes around in core pagecache functions, slows down the radix-tree hotpath, exports mysterious symbols. And that's on a 60-second scan.

It'll be a sizeable job going through it in detail. Not as sizeable as writing it though ;)

All of this for an undisclosed speedup of AFS!

I think we need an NFS implementation and some numbers which make it interesting. Or at least, some AFS numbers, some explanation as to why they can be extrapolated to NFS and some degree of interest from the NFS
guys. Ditto CIFS.

Because it _is_ a lot of code.

There is a lot of interest from the HPC community for this sort of thing on NFS. Basically, it will help server scalability for projects that have large numbers of read-only files accessed by large numbers of clients.

AFAIK, Steve Dickson ([email protected]) is working on the NFS hooks for FS-Cache.

Cheers,
Trond

Here is a NFS patch that incorporates the FS-Cache hooks. The caching is done on a per filesystem bases using the new -o fsc mount flag (i.e mount -o fsc server:/export /mnt/export)

Note: the util-linux rpm that support this option are currently available at people.redhat.com/steved/cachefs/util-linux but will also be available in the upcoming Fedora Core release

Note2: FSCACHE_WRITE_SUPPORT is not defined which means, for now, only read side caching is support. This does NOT means filesystems have to be mounted read only. What it does mean is only reads will be cached locally, writes will not.

---------------------------------------------

@@ -64,6 +64,8 @@
 
 #include "delegation.h"
 
+#include "nfs-fscache.h"
+
 #define NFSDBG_FACILITY		NFSDBG_PAGECACHE
 
 #define MIN_POOL_WRITE		(32)

@@ -123,6 +125,9 @@ static void nfs_grow_file(struct page *p
 	if (i_size >= end)
 		return;
 	i_size_write(inode, end);
+#ifdef FSCACHE_WRITE_SUPPORT
+	nfs_set_fscsize(NFS_SERVER(inode), NFS_I(inode), end);
+#endif
 }
 
 /* We can set the PG_uptodate flag if we see that a write request

@@ -255,6 +260,47 @@ static int wb_priority(struct writeback_
 }
 
 /*
+ * store an updated page in fscache
+ */
+#ifdef CONFIG_NFS_FSCACHE
+static void
+nfs_writepage_to_fscache_complete(struct page *page, void *data, int error)
+{
+	/* really need to synchronise the end of writeback, probably using a page flag */
+}
+static inline void
+nfs_writepage_to_fscache(struct inode *inode, struct page *page)
+{
+	int ret; 
+
+	if (!(NFS_SERVER(inode)->flags & NFS_MOUNT_FSCACHE))
+		return;
+
+	if (PagePrivate(page)) {
+		dfprintk(FSCACHE,
+			"NFS: writepage_to_fscache (0x%p/0x%p/0x%p)\n",
+			NFS_I(inode)->fscache, page, inode);
+
+		ret = fscache_write_page(NFS_I(inode)->fscache, page,
+					 nfs_writepage_to_fscache_complete,
+					 NULL, GFP_KERNEL);
+		if (ret != 0) {
+			dfprintk(FSCACHE,
+				"NFS:    fscache_write_page error %d\n", ret);
+				fscache_uncache_page(NFS_I(inode)->fscache, 
+				page);
+		}
+	}
+}
+#else
+static inline void
+nfs_writepage_to_fscache(struct inode *inode, struct page *page)
+{
+	BUG_ON(PagePrivate(page));
+}
+#endif
+
+/*
  * Write an mmapped page to the server.
  */
 int nfs_writepage(struct page *page, struct writeback_control *wbc)

@@ -299,6 +345,9 @@ do_it:
 		err = -EBADF;
 		goto out;
 	}
+#ifdef FSCACHE_WRITE_SUPPORT
+	nfs_writepage_to_fscache(inode, page);
+#endif
 	lock_kernel();
 	if (!IS_SYNC(inode) && inode_referenced) {
 		err = nfs_writepage_async(ctx, inode, page, 0, offset);

@@ -27,9 +27,11 @@
 #include <linux/slab.h>
 #include <linux/pagemap.h>
 #include <linux/smp_lock.h>
+#include <linux/buffer_head.h>
 
 #include <asm/uaccess.h>
 #include <asm/system.h>
+#include "nfs-fscache.h"
 
 #include "delegation.h"
 

@@ -252,6 +254,19 @@ nfs_file_sendfile(struct file *filp, lof
 	return res;
 }
 
+#ifdef CONFIG_NFS_FSCACHE
+static int nfs_file_page_mkwrite(struct vm_area_struct *vma, struct page *page)
+{
+	wait_on_page_fs_misc(page);
+	return 0;
+}
+static struct vm_operations_struct nfs_fs_vm_operations = {
+	.nopage			= filemap_nopage,
+	.populate		= filemap_populate,
+	.page_mkwrite   = nfs_file_page_mkwrite,
+};
+#endif
+
 static int
 nfs_file_mmap(struct file * file, struct vm_area_struct * vma)
 {

@@ -265,6 +280,12 @@ nfs_file_mmap(struct file * file, struct
 	status = nfs_revalidate_file(inode, file);
 	if (!status)
 		status = generic_file_mmap(file, vma);
+
+#ifdef CONFIG_NFS_FSCACHE
+	if (NFS_I(inode)->fscache != NULL)
+		vma->vm_ops = &nfs_fs_vm_operations;
+#endif
+
 	return status;
 }
 

@@ -316,6 +337,11 @@ static int nfs_commit_write(struct file 
 	return status;
 }
 
+/*
+ * since we use page->private for our own nefarious purposes when using fscache, we have to
+ * override extra address space ops to prevent fs/buffer.c from getting confused, even though we
+ * may not have asked its opinion
+ */
 struct address_space_operations nfs_file_aops = {
 	.readpage = nfs_readpage,
 	.readpages = nfs_readpages,

@@ -327,6 +353,11 @@ struct address_space_operations nfs_file
 #ifdef CONFIG_NFS_DIRECTIO
 	.direct_IO = nfs_direct_IO,
 #endif
+#ifdef CONFIG_NFS_FSCACHE
+	.sync_page	= block_sync_page,
+	.releasepage	= nfs_releasepage,
+	.invalidatepage	= nfs_invalidatepage,
+#endif
 };
 
 /* 

@@ -13,4 +13,5 @@ nfs-$(CONFIG_NFS_V4)	+= nfs4proc.o nfs4x
 			   delegation.o idmap.o \
 			   callback.o callback_xdr.o callback_proc.o
 nfs-$(CONFIG_NFS_DIRECTIO) += direct.o
+nfs-$(CONFIG_NFS_FSCACHE) += nfs-fscache.o
 nfs-objs		:= $(nfs-y)

@@ -1492,6 +1492,13 @@ config NFS_V4
 
 	  If unsure, say N.
 
+config NFS_FSCACHE
+	bool "Provide NFS client caching support (EXPERIMENTAL)"
+	depends on NFS_FS && FSCACHE && EXPERIMENTAL
+	help
+	  Say Y here if you want NFS data to be cached locally on disc through
+	  the general filesystem cache manager
+
 config NFS_DIRECTIO
 	bool "Allow direct I/O on NFS files (EXPERIMENTAL)"
 	depends on NFS_FS && EXPERIMENTAL

@@ -3,6 +3,7 @@
 
 #include <linux/list.h>
 #include <linux/backing-dev.h>
+#include <linux/fscache.h>
 
 /*
  * NFS client parameters stored in the superblock.

@@ -47,6 +48,10 @@ struct nfs_server {
 						   that are supported on this
 						   filesystem */
 #endif
+
+#ifdef CONFIG_NFS_FSCACHE
+	struct fscache_cookie	*fscache;	/* cache cookie */
+#endif
 };
 
 /* Server capabilities */

@@ -61,6 +61,7 @@ struct nfs_mount_data {
 #define NFS_MOUNT_NOACL		0x0800	/* 4 */
 #define NFS_MOUNT_STRICTLOCK	0x1000	/* reserved for NFSv4 */
 #define NFS_MOUNT_SECFLAVOUR	0x2000	/* 5 */
+#define NFS_MOUNT_FSCACHE	0x4000
 #define NFS_MOUNT_FLAGMASK	0xFFFF
 
 #endif

@@ -65,6 +65,7 @@ struct nfs4_mount_data {
 #define NFS4_MOUNT_NOCTO	0x0010	/* 1 */
 #define NFS4_MOUNT_NOAC		0x0020	/* 1 */
 #define NFS4_MOUNT_STRICTLOCK	0x1000	/* 1 */
+#define NFS4_MOUNT_FSCACHE	0x2000	/* 1 */
 #define NFS4_MOUNT_FLAGMASK	0xFFFF
 
 #endif

@@ -29,6 +29,7 @@
 #include <linux/nfs_xdr.h>
 #include <linux/rwsem.h>
 #include <linux/mempool.h>
+#include <linux/fscache.h>
 
 /*
  * Enable debugging support for nfs client.

@@ -188,6 +189,9 @@ struct nfs_inode {
 	int			 delegation_state;
 	struct rw_semaphore	rwsem;
 #endif /* CONFIG_NFS_V4*/
+#ifdef CONFIG_NFS_FSCACHE
+	struct fscache_cookie	*fscache;
+#endif
 	struct inode		vfs_inode;
 };
 

@@ -587,6 +591,7 @@ extern void * nfs_root_data(void);
 #define NFSDBG_FILE		0x0040
 #define NFSDBG_ROOT		0x0080
 #define NFSDBG_CALLBACK		0x0100
+#define NFSDBG_FSCACHE		0x0200
 #define NFSDBG_ALL		0xFFFF
 
 #ifdef __KERNEL__

_______________________________________________
NFSv4 mailing list
[email protected]
http://linux-nfs.org/cgi-bin/mailman/listinfo/nfsv4

OK, thanks. What's the maturity of this patch?

Are you in a position to publish performance testing results?

Well its as mature as the can be as this point. The patch has followed along with David's cachefs patches since 2.6.10 (I believe) and I've take a number of percussions and did quite bit of testing to ensure there are not any regressions when the -o fsc mount is not used.

Not really... or at least I haven't... maybe David has some...

We've be mostly working on stability and data integrity, in our copious spare time of course ;-) . And to be quite honest there are still some stability issue to iron out... But we both felt, at this point, the best thing to do is get more eyeballs on the code so we can ensure it moves in the right direction....

steved.

Well, I'm not in the HPC community, but I have a lot of interest in seeing cachefs + nfs working in the upstream kernel.

Jeff, misses cachefs from the Solaris days

Missing patch 11/12 here. Can you post a link or try resending?

SUSE Labs, Novell Inc.

Send instant messages to your online friends http://au.messenger.yahoo.com 

The patches are available from:

http://people.redhat.com/~dhowells/cachefs/

There's a patch-list.txt file in there with the patch descriptions and patch names in order as well.

Also in there is dump-cachefs.c which can be used to peer into the depths of a block device that has had cachefs mounted on it to see what's what.

David

Not exactly. Whilst it is a case of what you want is not in the cache (or was discarded when examined), I'm also refusing to add it to the cache for some reason or other (ENOMEM, no cache, I/O error on cache, insufficient available space, etc).

If it was not in the cache, but I am going to let you cache it then I'll return a cookie instead. All reads on that cookie will return ENODATA until at such time data has been stored in the cache and can then be retrieved.

All attempts to perform accesses using the "negative" cookie will then fail gracefully. A "negative" cookie will not be instantiated. You have to get a new cookie.

But UNIX normally allows you to subsequently go and fill a hole (subject to space constraints, etc)...

It isn't a "don't know" exactly. It's a "no".

Hmmm... Which is possibly less efficient because CPUs generally are better at determining 0 than -1.

I don't think I have a need for both. Either I give you a cookie (for which there may be nothing in the cache); or I give you the "negative" cookie for which there's definitely nothing in the cache, and gracefully refuse to service it.

So, would you still rather I used NULL? If so, I can change it easily enough.

David

"Forbidden
You don't have permission to access /~dhowells/cachefs/patch-list.txt on this server."

--b.

That should be fixed now.

David

You mean like:

? :)

-- Jamie

The _dentry_ is negative, and it is not NULL. It has an explicit flag saying that it's negative.

We do not have negative inode caches.

Linus

Yes, if you don't have real negative cookies, then just use NULL.

Think of malloc(). It doesn't return MALLOC_OUT_OF_MEMORY_COOKIE when it won't give you any more memory. It returns NULL.

The advantage of NULL is that people know what it is, and that the C language _defines_ that you can do "if (xyzzy)" to test for non-NULL. Conversely, the disadvantage of using a special cookie (that just happens to be NULL) is that the test for NULL still _works_, so now you have two ways of doing something and the compiler will never warn.

So in a very real sense, NULL _always_ exists. You can't make it go away by defining it to another name, and by using another name you just confuse things (if they are in fact the same).

Linus

What I'm trying to do is actually fairly simple in concept:

(1) Have a metadata inode (imeta) that covers the block device.

(2) Metadata pages are attached to imeta at page indexes corresponding to the block indexes on disk.

(3) Metadata blocks on disk are to be considered invariant[*] once attached to the on-disk metadata tree rooted in the journal.

[*] atimes and netfs metadata can be updated in place. They fit into a
single sector, and so we assume changing them is atomic.

(4) A new metadata tree is constructed by replacing the disk blocks that need to be modified with newly allocated blocks, then attaching the old unchanged branches to that new block. Think of RCU or LISP.

The data then needs to be copied from the old block to the new, and the old block discarded when the journal is advanced.

(5) If a copy of the old block is resident on a page in memory and is up to date with respect to the old block on disk, then we really don't want to have to copy it to another page in memory. This would require allocation of an extra page, as well as requiring a full-page copy, thus thrashing the data cache.

What we do is to detach the page from imeta at the old block index and reattach it at the new block index (having allocated a new block first).

However, this means that we potentially have to allocate new radix tree bits, and so we're subject to ENOMEM. But once we've allocated a new block, we don't want to have to try and roll the allocation back or recycle the block because that would potentially incur ENOMEM also...

In fact, we don't want to take any errors at all (EIO we can deal with because that means the blockdev is screwed).

So we pre-allocate sufficient radix tree bits and attach them to the task so that we can (a) sleep and (b) evade ENOMEM between allocating a new block and attaching it to the tree's superstructure.

Using buffer heads doesn't help, and using the blockdev's inode to hold pages doesn't help. This way, I can keep my metadata in the pagecache and the VM will schedule it to be written out. I also want to avoid bufferheads because they use up a big additional chunk of memory I'd prefer to avoid having to pin.

What I wanted was to be able to supply sufficient radix tree nodes in advance that I wouldn't incur ENOMEM from that source, but I also needed to be able to sleep after having loaded the cache, which meant I couldn't just shove the extra in the per-CPU cache.

Admittedly, this is going to slow things down, and there's not a lot I can do about that without adding full rollback support, which would be a lot of work, particularly coping with the case of there being insufficient memory for the cause.

Another way to deal with this would be to provide alternate add_to_page_cache*() and radix_tree_preload() or radix_tree_insert() functions that could be given a cache from which to allocate radix tree nodes.

I could also separate out the two sorts of cache. I changed the form of the radix tree cache to a linked list with a counter instead of an array. This uses less memory at the head (which we want for adding to task_struct), but may well be slower when dequeuing elements as the dcache can't help. I could revert the per-CPU cache to the original form, whilst keeping the per-task cache in the less-intrusive form.

I could even remove the metadata from the pagecache entirely. I'd rather not do that, though. Using the page cache has a lot of advantages, and they mostly outweigh its disadvantages. Probably the biggest advantage is that I can leave a metadata block I'm not using at the moment lying around in the pagecache; the VM can discard it if it likes, but if not, it'll be there when I need it again.

(*) clear_page_dirty_for_io()

Used in mpage.c, mpage_writepages() which I have a very simplified version of.

(*) lru_cache_add()

Normally called indirectly via add_to_page_cache_lru(), but I wanted to call add_to_page_cache(), and sometimes use it for multiple pages with pagevec_lru_add() which is exported, and sometimes on a single page, which means using lru_cache_add().

:-)

What about NFS?

I'll generate some, at least for AFS.

Yes, I noticed that too:-)

David

Can you remind me again why it requires a blockdev rather than a regular file?

coz people are just going to go and use a loopback mount to get their blockdev, which is a bit sad.

FS-Cache != CacheFS, although the names are a bit confusing. FS-Cache is a generic cache frontend for filesystems, while CacheFS is a provider backend that uses a block define internally. You could _also_ use cache files. If you look at the [0/12] in the list, you can see a diagram explaining this all in detail.

Cheers,
Kyle Moffett

--
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.
-- C.A.R. Hoare

That's the third time you've asked:-) You should be able to find the previous conversations in LKML archives.

I presume directing you to go and look at the CacheFS documentation in patch 12/12 would be out of the question? Particularly the section entitled "Why a block device? Why not a bunch of files?"...

Look also at Documentation/filesystem/caching/fscache.txt provided by patch 9/12 for the constraints I've set, in particular:

(1) It must be practical to operate without a cache.

(2) The size of any accessible file must not be limited to the size of the cache.

(3) The combined size of all opened files (this includes mapped libraries) must not be limited to the size of the cache.

(4) The user should not be forced to download an entire file just to do a one-off access of a small portion of it (such as might be done with the "file" program).

To which I wish to add:

(5) The netfs pages must remain owned by the netfs, so that there is no difference between the netfs operating with a cache and it operating without a cache. This means I/O must be done to/from the netfs pages directly from/to the cache.

I have a start of a cache-on-files facility (called, most imaginatively, CacheFiles) which works as another backend to FS-Cache. Of the underlying filesystem, it requires:

(*) O_DIRECT

(*) Reads and writes on arbitrary kernel pages

(*) Reads on holes must return short or ENODATA. This requires an extra
O_XXXX flag to be supplied when opening a file or the struct file or inode to be flagged appropriately.

(*) The ability to issue FS operations such as rename, open, setxattr, mkdir
from kernel space.

This facility isn't well advanced yet, and will initially only be available on EXT2/3. It will also require a userspace component to clean up dead nodes.

Are you willing to at least carry the FS-Cache core and the AFS usage of it? They haven't changed for a long time, and hopefully shouldn't need to:

(*) Subject: [PATCH 8/12] FS-Cache: Add generic filesystem cache core module

     Patch: fscache-core-2614mm2.diff

(*) Subject: [PATCH 9/12] FS-Cache: Add documentation for FS-Cache and its interfaces

     Patch: fscache-docs-2614mm2.diff

(*) Subject: [PATCH 10/12] FS-Cache: Make kAFS use FS-Cache

     Patch: fscache-afs-2614mm2.diff

Once I've updated them for Linus's comments, that is...

All the other patches have to do with CacheFS.

David

Maybe on the fourth or fifth time it'll occur you to put it into the changelog.

None of that appears to be relevant.

A blockdev is just a big, fixed-sized file. Why cannot it be backed by a big, fixed-sized file?

<looks>

OK, it's doing submit_bio() directly.

I'd have thought that a decent intermediate step would be cache-on-single-file using a_ops.direct_IO, as you're implying above. Then all the direct-to-blockdev code can go away. It'll take some tweaking of the core direct-io code, but nothing terribly serious.

fs-cache won't do anything without a backing store such as cachefs will it?

Those names are rather confusing, btw.

But that's not what's changed.

So if/when I produce a CacheFiles patch as well, you'll expect a critique of why that's better than everything else in the changelog for that?

It rules out the use of i_mapping...

Using a big fixed-sized file also means that you've got two layout managers and two transaction managers and two metadata managers on top of each other.

That's really the worst of both worlds. If you can access files, then you're best of doing so on a one cache-file per netfs-file basis, *if* you can get notification of completion on an asynchronous operation.

If you try to do this, the caching backend will try to lay the blocks out in a manner that will then be undone because the underlying filesystem will then put the blocks or parts thereof where *it* wishes.

Furthermore, it would seem that whilst undertaking direct I/O on an inode, that inode is locked against other direct I/O operations. This could end up serialising all I/O operations on the cache (see dio_complete() in fs/direct-io.c).

The direct-to-blockdev code should get you better performance than going through a single file on a filesystem: with your suggestion, you end up adding the latency of the cache-to-single-file to that of the underlying filesystem.

There are five main problems that need solving for cachefiles that I can see:

(1) Reading of holes must return ENODATA or a short write. I have a patch to do this for O_DIRECT (attached).

(2) It must be possible to do O_DIRECT reads/writes directly to/from kernel pages. This may possible without modification, but I'm not certain of that; looking at dio_refill_pages() it may not be - that accesses the current->mm to get more pages.

(3) It must be possible to do these reads and writes asynchronously and to get notification of their completion. I'm not sure how easy this is, but it looks like it should be possible, perhaps using a kiocb. The routines in fs/direct-io.c don't seem to be able to do asynchronicity, except through AIO.

(4) It must be possible to maintain structural integrity in the cache. This should be possible simply be relying on the underlying filesystem.

(5) It must be possible to maintain a certain level of data integrity in the cache. We really don't want to have to blow the entire cache away if the power goes out or the cache isn't laid to rest correctly.

It may end up being necessary to have a parallel to fs/direct-io.c for doing I/O asynchronously to/from kernel pages.

Also, fs/direct-io.c seems to assume the filesystem on which it's running uses buffer_heads - but not all of them do.

David

diff -uNr linux-2.6.12-rc2-mm1/fs/direct-io.c linux-2.6.12-rc2-mm1-cachefs/fs/direct-io.c
@@ -790,7 +790,7 @@
 	struct page *page;
 	unsigned block_in_page;
 	struct buffer_head *map_bh = &dio->map_bh;
-	int ret = 0;
+	int ret = 0, sent = 0;
 
 	/* The I/O can start at any block offset within the first page */
 	block_in_page = dio->first_block_in_page;

@@ -861,6 +861,14 @@
 					page_cache_release(page);
 					return -ENOTBLK;
 				}
+				else if (dio->iocb->ki_filp->f_flags &
+					 O_NOREADHOLE
+					 ) {
+					page_cache_release(page);
+					if (sent)
+						return 0;
+					return -ENODATA;
+				}
 
 				if (dio->block_in_file >=
 					i_size_read(dio->inode)>>blkbits) {

@@ -907,6 +915,7 @@
 				page_cache_release(page);
 				goto out;
 			}
+			sent = 1;
 			dio->next_block_for_io += this_chunk_blocks;
 
 			dio->block_in_file += this_chunk_blocks;

diff -uNr linux-2.6.12-rc2-mm1/include/asm-i386/fcntl.h linux-2.6.12-rc2-mm1-cachefs/include/asm-i386/fcntl.h
@@ -21,6 +21,7 @@
 #define O_DIRECTORY	0200000	/* must be a directory */
 #define O_NOFOLLOW	0400000 /* don't follow links */
 #define O_NOATIME	01000000
+#define O_NOREADHOLE	02000000 /* give short read or ENODATA on a hole */
 
 #define F_DUPFD		0	/* dup */
 #define F_GETFD		1	/* get close_on_exec */

It's an FAQ and it's an obvious shortcoming of the entire proposal. It should be covered in the overall description.

That's a choice users can make. Right now, they'll use loopback, which is worse. But perhaps acceptably.

The same will happen with a loopback mount, no?

No, direct-io has (almost) complete parallelism for readers and writers. We use locking in there to protect certain filesystem metadata operations but the locks can be dropped prior to performing the bulk IO.

hmm? direct-io to a file is only a few percent slower than direct-io to blockdev iirc.

Should we be exposing O_NOREADHOLE to userspace like this?

No, we'll need to modify direct-io.

My suggestion would be to modify address_space_operations.direct_IO so that it no longer takes a zillion arguments - instead, pass in a new `struct direct_io_cb' thing which has all the args, pass that up and down the stack.

Within blockdev_direct_IO, stick that direct_io_cb* into struct dio.

Add sufficient fields in direct_io_cb so that dio_refill_pages() can populate dio->pages with kernel pages rather than using get_user_pages(), if it was called for in-kernel direct-io.

Harder. Yes, perhaps we could use AIO infrastructure.

Nope, buffer_heads are only in there because it happens to be the container in which the get_block[s]() callback returns the file offset -> block number mapping information.

Just a guess - perhaps the following clarifies this point of confusion:

The "changelog" isn't so much for what you've changed, relative to the previous version of that patch. It is for what will go into the Linux change history for this patch, when accepted.

To quote Documentation/SubmittingPatches, which calls this the "explanation body":

The explanation body will be committed to the permanent source changelog, so should make sense to a competent reader who has long since forgotten the immediate details of the discussion that might have led to this patch.

                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <[email protected]> 1.925.600.0401

I'm currently running a root filesystem for a cluster using the OpenAFS client for precisely this reason.

And in regards to (other) comments about code size, if you think this is big, take a look at the OpenAFS kernel module.