Buffer heads to track page mappings -> block num
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 24 Sep 2010 19:55:31 +0000 (12:55 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:54 +0000 (17:35 -0700)
Just for the page mapping so far (no other IO uses it).

Documentation/vfs.txt
kern/include/blockdev.h
kern/include/page_alloc.h
kern/src/blockdev.c
kern/src/kfs.c
kern/src/page_alloc.c
kern/src/vfs.c

index 569753f..d56db1e 100644 (file)
@@ -381,3 +381,214 @@ gets decref'd.  All we'll do is add a DENTRY_DYING flag, and dentry_release()
 will avoid LRU and unusing it.  The dcache can continue to assume that negative
 entries are unused/LRU/dentry_freeable/ref==0, and not worry about calling
 kref_put().
+
+X: Buffer Cache, Page Cache, Buffer Heads, WTH?
+-------------------------------
+X.1: Page vs Buffer Cache
+--------------------
+So we discussed the page cache, but as described, it does not satisfy all of
+our disk caching needs.  Traditionally, there would also be a 'buffer cache.'
+Buffers usually refer to memory used to hold data from the disk (or network).
+I can think of a couple different ways someone could think of the buffer
+cache, and to understand them, we first need to understand what we need to be
+caching.
+
+There are two main types of FS data: file data and metadata.  This metadata
+is FS-specific data accessed by the VFS to get to a file's contents.  For
+example, the superblock, inodes, inode indirect blocks, and to a certain
+extent the directory's contents are all metadata.  There isn't an FS file (not
+to be confused with an OS file) that corresponds to this data, but it needs to
+be read in and cached.  Furthermore, this cache needs to be managed and
+written back when dirty.
+
+A very simple buffer cache would include anything *ever* read from disk.  It
+would then get copied into the page cache in PGSIZE chunks for the page cache.
+This would suck, since we now have two or three copies.
+
+Another buffer cache would be to cache only the disk blocks needed for
+metadata.  I think this is what Linux did before it unified its buffer and
+page caches (implied in UTLK).  The main issue with this is that you have two
+different systems for managing essentially similar data - we only want to deal
+with flushing, syncing, and writebacks of one subsystem, not in multiple
+different systems.
+
+The solution is to use the page cache to cache the metadata block operations.
+We do this by having the block device be mapped in PGSIZE chunks through its
+own struct page_mapping (a.k.a. struct address_space in Linux).  This way,
+both files and the block device are mapped in PGSIZE chunks via the same
+page_mapping structure, and will be managed by the same code.
+
+X.2: Mapping Blockdev Data vs File Data
+--------------------
+An important distinction between file data (as managed by an inode) and the
+bdev is that PGSIZE chunks of data for the bdev *must* be made of contiguous
+disk blocks.  Ideally, file data is also contiguous/sequential, but that is
+not always the case - hence the need for the inode's block pointers.  This
+means that the chunk at the bottom of the page_mapping radix tree is a page,
+and on that page there may be several buffers, holding the data of
+nonsequential disk blocks - but that not all pages are like this.  The bdev
+pages are made up of sequential blocks due to the very nature of what we are
+mapping; there's no inode abstraction in between.
+
+There are a couple ways we could handle this.  We adopt the Linux approach of
+using something called a buffer head (BH), which describes the mapping from
+in-memory buffer to block device / block number.  These are slab-allocated,
+and exist for each buffer of a page.  The page itself points to the first of
+its BHs, all of which exist in a circular LL.  The maximum number of them is
+determined by PGSIZE / blocksize.  Whenever there is a page in the page cache
+(meaning, in a page_mapping), that is up to date, it will have a BH.
+
+Another way would be to not have BHs at all, and just figure out (at
+operation-time) what the n blocks on disk are for any given page, and submit
+the IO operations for those blocks.  The BHs serve as a cache of that info.
+They also serve as a location to store data about the mapping, such as whether
+it is dirty or not, whether the data is up to date or not (has it been read
+in), etc.  The caching ought to be rather beneficial, since it means we do not
+need to access the disk-inode and indirect blocks whenever we want to perform
+an operation (which may be frequent - imagine the periodic writeback of an
+mmap'd file undergoing writes).  The per-buffer dirty tracking will also help:
+no need to write unrelated blocks if only one is edited (though this will not
+help with mmap(), since we don't usually know which part of the page is
+written).
+
+X.4: Do we always need BHs?
+------------------
+But what about those pages made up of contiguous blocks?  We don't have a
+bunch of independent, non-sequential blocks that we need to map.  Do we need a
+bunch of BHs for that?  Do we need any?  It really seems excessive to break it
+up into separate buffers for no reason.  At the other extreme, we could get by
+without having a BH at all, though this gets back to the other issue of
+caching.  What we do (or will do) is have one BH for the entire page of
+contiguous blocks.  If the page is a "buffer page," in Linux terms (meaning it
+has separate buffers), it will have n BHs in a circular LL.  Either way, we'll
+always have the mapping handy.  We wouldn't need to re-verify the contiguous
+nature of the blocks anyways, since the fact that the page was up to date and
+didn't need a BH would mean it was contiguous.  Further benefits to using the
+one BH include: 1) we are likely to make BHs be the unit of IO *submission*,
+and having one handy will simplify that code. 2) some code paths within the
+VFS may get BHs as a return value, which they can then dirty.  Always having a
+BH makes this easier (no need to find out if it's a buffer page, then decide
+how to dirty it).
+
+Another compliation with this is certain code will want a block in the middle
+of a page (very common for metadata).  That code will get the BH for the
+entire page back.  It will need to determine the starting block and then the
+offset of the block it wants.  Note, this usage of the BHs is finding the
+buffer corresponding to a block number.  The BH is a bidirectional mapping
+between buffers and blockdev:blocknum.  These calculations are a minor
+complication, but easy enough to do, and will probably be worth it.  The
+tradeoff is against having multiple BHs, which would mean multiple block IO
+requests for writing a single page (and writing the whole page may be a common
+operation).
+
+X.3: What about opening a blockdev?
+--------------------
+All of this means we are using the page cache to cache metadata blocks from
+the block device.  But what about the other blocks?  Those are "file" blocks,
+which are in the page mapping of the inode.  But what about when the block
+device is opened as if it was a file?  And then if we were to access the file
+blocks in this manner?  Yeah, that would screw things up - you will get
+inconsistencies, under the current plan.  There is one easy way to avoid this:
+don't open a bdev file if a file system is mounted on top of it.  If you do,
+don't be surprised about inconsistencies.  Ideally, the FS will never leave
+the actual disk in an inconsistent state, but the bdev's page cache could read
+things at different times and get some weird results.  Just don't do this (for
+now - not like I plan to make this possible any time soon).
+
+Could we use the same buffers for both the blockdev-file page mapping and the
+inode-file page mapping?  No - because the inode-file has the inode
+indirection in between, which means a PGSIZE chunk of the file might not be
+contiguous (as mentioned above).
+
+We could have tried to avoid this bdev file problem by having the page mapping
+radix trees point to a set of BHs that describes that page worth of buffers,
+so that the bdev and an inode pointing to the same data will use the same
+buffers and BHs.  That won't work, since the files buffers/blocks aren't in
+the same order as they are on disk within a page.  Instead, we'd need to have
+the page mapping go down to the FS's blocksize granularity, not to PGSIZE, so
+that we could have independent leaves point to wherever they want.  This would
+push the specific block device's blocksize into the VFS (which I don't like).
+
+But the blocksize-infecting-the-VFS alone isn't too bad.  The real issue is
+what is at the end of the page mapping.  Is it a page or a buffer/BH?  We want
+pages for two related reasons: higher levels of the kernel's IO systems deal
+with pages:
+1. mmap().  Good old mmap() requires at least a page of contiguous block
+buffers, so that the physical page frame can be mapped directly into a
+process's address space.
+2. Fast IO.  We want to use page remapping for fast IO.  This means that IO
+has to be in PGSIZE chunks - not blocksize chunks.
+
+x.4: Managing Dirty Buffers
+--------------------
+Many (some/all?) of the block functions will return a BH to describe the
+mapping.  One reason for doing this (mentioned above) is to allow the caller
+to manage if a buffer is dirty or not.  The tracking of dirty pages is done by
+the page cache.  The dirtying is done by the caller; it can simply mark the BH
+dirty and forget about it.  The writeback is handled usually by the page cache
+or is triggered by an FS event.  Eventually, we'll have a kernel thread that
+periodically writes dirty buffers back to disk.  Processes can also do this by
+calling fsync.  FSs themselves will trigger syncs of metadata.  This will come
+from having dirty SBs and inodes in the VFS.
+
+Note, the issue of whether or not we pin metadata blocks, such as the inode's
+indirect blocks (or other related blocks), in the page cache is independent of
+all these issues.  If they are not cached / pinned, we would just have to
+block and reread the inode's structures back into memory and proceed (for
+instance, we'd do this when identifying blocks for a page mapping on a file
+read).  The reason we wouldn't want to pin them is to save memory.
+
+x.5: Reference Counting BHs and Pages
+--------------------
+So we talk about passing around BHs, both when submitting IO ops and when
+returning from things like read_block() (note: this may return pages, not
+BHs).  However, we do not kref or reference count BHs in any way.  Instead, we
+kref pages.  We do this (for now) for a couple reasons:
+1) Pages are the unit of memory management in the kernel.  Higher levels of
+the kernel will pin/incref the page (such as in an mmap()).
+2) BHs hang off of a page, but exist only to be expressive about the
+management of the buffers on the page.  It's not like how a file hangs off a
+dentry, where the dentry doesn't know (or care) about the file.
+3) We already refcount pages.  While we could do the same for the BHs, it is a
+bit redundant.  Any place that would be kreffing the BH can just kref the
+whole page.
+
+When a page is in the page cache, we give it one kref.  Whenever a function or
+subsystem is using one of these pages (IO, using the data, etc), there needs
+to be a kref.  When it is time to remove the page from the page mapping, the
+code needs to remove it from the radix tree, then kref_put it.  When the final
+user is done with it (ideally, there is none, but we need to handle the case)
+the release function will clean up the page - including freeing its BHs.
+
+This does suck in that we could be removing an item from the page cache while
+it is being used, violating some LRU policy.  The actual decision to remove it
+should use those policies (when possible); the kreffing is simply to avoid
+issues from race conditions.  (A reader starts using a page right before it is
+ripped from the mapping).
+
+One issue with this is that dirty pages/buffers will need to be written back.
+If someone tries to read while the page is removed from the page_mapping, but
+before it is written back, they could get an old version if the read happens
+before the write.  This is only an issue if the page is dirty.  One option
+would be to writeback the page/buffer, then later remove it from the page
+cache when it is read.  There's issues with concurrent writers, though if that
+happens, we probably don't really want to remove it (it was LRU).  Note this
+is an issue regardless of whether or not BHs are refcounted.
+
+Also note that writeback of pages will happen regardless of eviction plans
+(fsync, every n sec, etc).
+
+This refcounting pattern is very similar to unlinking, where you can continue
+to access a file once it is removed from the directory.  The difference here
+is that future requests will get the same object (the page), unlike in the FS,
+where you get ENOENT.  The page mapping is a cache, and you need to get the
+same old data that was in there before the eviction.
+
+A final issue is when the VFS aggressively pins blockdev (metadata)
+pages/buffers.  Ideally, we'd like to be able to expel pages/buffers even if
+they are refcnt'd.  The subsystems will always want to keep stuff in RAM.
+This also/especially applies to mmap().  One solution would be to keep them in
+RAM, but have the BH keep track of who is holding its reference.  Then we
+could unmap the page, which would need to get read back in on its next access.
+We'd need (or ought to have) some sort of callbacks.  This will get solved
+later when we deal with unmapping mmap'd files.
index 6ab2adf..1742026 100644 (file)
@@ -25,7 +25,7 @@
 struct block_device {
        int                                                     b_id;
        unsigned int                            b_sector_size;          /* HW sector size */
-       unsigned int                            b_num_sectors;          /* Total sectors on dev */
+       unsigned long                           b_num_sectors;          /* Total sectors on dev */
        struct kref                                     b_kref;
        void                                            *b_data;                        /* dev-specific use */
        char                                            b_name[BDEV_INLINE_NAME];
@@ -35,6 +35,24 @@ struct block_device {
        // callbacks for completion
 };
 
+/* Not sure which of these we'll need, if any */
+#define BH_LOCKED              0x001   /* involved in an IO op */
+#define BH_UPTODATE            0x002   /* buffer is filled with file data */
+#define BH_DIRTY               0x004   /* buffer is dirty */
+
+/* This maps to and from a buffer within a page to a block(s) on a bdev.  Some
+ * of it might not be needed later, etc (page, numblock). */
+struct buffer_head {
+       struct page                                     *bh_page;                       /* redundant with buffer */
+       void                                            *bh_buffer;
+       unsigned int                            bh_flags;
+       struct buffer_head                      *bh_next;                       /* circular LL of BHs */
+       struct block_device                     *bh_bdev;
+       unsigned long                           bh_blocknum;
+       unsigned int                            bh_numblock;            /* length (in blocks) */
+};
+struct kmem_cache *bh_kcache;
+
 /* This encapsulates the work of a request (instead of having a variety of
  * slightly-different functions for things like read/write and scatter-gather
  * ops).  Reads and writes are essentially the same, so all we need is a flag to
@@ -57,6 +75,7 @@ struct kmem_cache *breq_kcache;       /* for the block requests */
 
 void block_init(void);
 struct block_device *get_bdev(char *path);
+void free_bhs(struct page *page);
 /* This function will probably be the one that blocks */
 int make_request(struct block_device *bdev, struct block_request *req);
 
index dea207d..3f94282 100644 (file)
@@ -29,6 +29,7 @@ typedef LIST_ENTRY(page) page_list_entry_t;
 #define PG_LOCKED              0x001   /* involved in an IO op */
 #define PG_UPTODATE            0x002   /* page map, filled with file data */
 #define PG_DIRTY               0x004   /* page map, data is dirty */
+#define PG_BUFFER              0x008   /* is a buffer page, has BHs */
 
 /* TODO: this struct is not protected from concurrent operations in any
  * function.  We may want a lock, but a better thing would be a good use of
@@ -39,6 +40,7 @@ struct page {
        unsigned int                            pg_flags;
        struct page_map                         *pg_mapping;
        unsigned long                           pg_index;
+       void                                            *pg_private;    /* type depends on page usage */
 };
 
 /******** Externally visible global variables ************/
index f5014c9..d98cd02 100644 (file)
@@ -8,6 +8,7 @@
 #include <blockdev.h>
 #include <kmalloc.h>
 #include <slab.h>
+#include <page_alloc.h>
 
 struct file_operations block_f_op;
 struct kmem_cache *breq_kcache;
@@ -16,6 +17,8 @@ void block_init(void)
 {
        breq_kcache = kmem_cache_create("block_reqs", sizeof(struct block_request),
                                        __alignof__(struct block_request), 0, 0, 0);
+       bh_kcache = kmem_cache_create("buffer_heads", sizeof(struct buffer_head),
+                                     __alignof__(struct buffer_head), 0, 0, 0);
 
        #ifdef __CONFIG_EXT2FS__
        /* Now probe for and init the block device for the ext2 ram disk */
@@ -52,6 +55,22 @@ struct block_device *get_bdev(char *path)
        return bdev;
 }
 
+/* Frees all the BHs associated with page.  There could be 0, to deal with one
+ * that wasn't UPTODATE.  Don't call this on a page that isn't a PG_BUFFER */
+void free_bhs(struct page *page)
+{
+       struct buffer_head *bh, *next;
+       assert(page->pg_flags & PG_BUFFER);
+       bh = (struct buffer_head*)page->pg_private;
+       while (bh) {
+               next = bh->bh_next;
+               bh->bh_next = 0;
+               kmem_cache_free(bh_kcache, bh);
+               bh = next;
+       }
+       page->pg_private = 0;           /* catch bugs */
+}
+
 /* This ultimately will handle the actual request processing, all the way down
  * to the driver, and will deal with blocking.  For now, we just fulfill the
  * request right away. */
index 208c438..9c7e3e1 100644 (file)
@@ -136,6 +136,20 @@ int kfs_readpage(struct file *file, struct page *page)
                memcpy(page2kva(page), (void*)begin, copy_amt);
                memset(page2kva(page) + copy_amt, 0, PGSIZE - copy_amt);
        }
+       struct buffer_head *bh = kmem_cache_alloc(bh_kcache, 0);
+       if (!bh) {
+               unlock_page(page);
+               return -1;                      /* untested, un-thought-through */
+       }
+       /* KFS does a 1:1 BH to page mapping */
+       bh->bh_page = page;                                                             /* weak ref */
+       bh->bh_buffer = page2kva(page);
+       bh->bh_flags = 0;                                                               /* whatever... */
+       bh->bh_next = 0;                                                                /* only one BH needed */
+       bh->bh_bdev = file->f_dentry->d_sb->s_bdev;             /* uncounted */
+       bh->bh_blocknum = page->pg_index;
+       bh->bh_numblock = 1;
+       page->pg_private = bh;
        /* This is supposed to be done in the IO system when the operation is
         * complete.  Since we aren't doing a real IO request, and it is already
         * done, we can do it here. */
index 657f0c7..539993c 100644 (file)
@@ -15,6 +15,7 @@
 #include <pmap.h>
 #include <string.h>
 #include <kmalloc.h>
+#include <blockdev.h>
 
 #define l1 (available_caches.l1)
 #define l2 (available_caches.l2)
@@ -277,6 +278,8 @@ static void page_release(struct kref *kref)
 {
        struct page *page = container_of(kref, struct page, pg_kref);
 
+       if (page->pg_flags & PG_BUFFER)
+               free_bhs(page);
        /* Probably issues with this, get rid of it on a future review */
        __page_clear(page);
        /* Give our page back to the free list.  The protections for this are that
index 4a188a6..a040caa 100644 (file)
@@ -1044,6 +1044,7 @@ void inode_release(struct kref *kref)
        /* Either way, we dealloc the in-memory version */
        inode->i_sb->s_op->dealloc_inode(inode);        /* FS-specific clean-up */
        kref_put(&inode->i_sb->s_kref);
+       /* TODO: clean this up */
        assert(inode->i_mapping == &inode->i_pm);
        kmem_cache_free(inode_kcache, inode);
        /* TODO: (BDEV) */
@@ -1729,7 +1730,7 @@ int pm_insert_page(struct page_map *pm, unsigned long index, struct page *page)
        error = radix_insert(&pm->pm_tree, index, page);
        if (!error) {
                page_incref(page);
-               page->pg_flags |= PG_LOCKED;
+               page->pg_flags |= PG_LOCKED | PG_BUFFER;
                page->pg_mapping = pm;
                page->pg_index = index;
                pm->pm_num_pages++;
@@ -1746,13 +1747,13 @@ int pm_remove_page(struct page_map *pm, struct page *page)
 {
        void *retval;
        warn("pm_remove_page() hasn't been thought through or tested.");
+       /* TODO: check for dirty pages, don't let them be removed right away.  Need
+        * to schedule them for writeback, and then remove them later (callback). */
        spin_lock(&pm->pm_tree_lock);
        retval = radix_delete(&pm->pm_tree, page->pg_index);
        spin_unlock(&pm->pm_tree_lock);
        assert(retval == (void*)page);
        page_decref(page);
-       page->pg_mapping = 0;
-       page->pg_index = 0;
        pm->pm_num_pages--;
        return 0;
 }
@@ -1792,6 +1793,9 @@ int file_load_page(struct file *file, unsigned long index, struct page **pp)
                                return error;
                }
        }
+       /* At this point, page is a refcnt'd page, and we return the reference.
+        * Also, there's an unlikely race where we're not in the page cache anymore,
+        * and this all is useless work. */
        *pp = page;
        /* if the page was in the map, we need to do some checks, and might have to
         * read in the page later.  If the page was freshly inserted to the pm by