Page cache for memory mapped files
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 16 Jul 2010 20:13:02 +0000 (13:13 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:48 +0000 (17:35 -0700)
Ties the radix trees and page maps into the VFS, KFS, and mmap().  Still
lots of little corner cases, it can't block yet, and I bet we're
screwing something up with page refcounting (which will cause memory
leaks).

Big note: this breaks support for appserver-managed files.  It had to
happen sooner or later.  The memory mapping currently only works for
files through do_mmap, since processes don't know about files yet.

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

index 5a9d86a..b3bffb1 100644 (file)
@@ -116,7 +116,9 @@ don't have all of the same fields yet, and may be doing things slightly
 differently, but the basics are the same.  Together, the page_maps and the
 functions to manipulate them make up the Page Cache.  Every page frame that is
 in a page mapping can be traced back to its page_map, via pointers in the struct
-page.
+page.  Note the page_mapping is tracked twice for a file, the f_mapping and the
+i_mapping.  We really only need the i_mapping, but this saves a couple cache
+misses.  Might go away later.
 
 As a side note, Linux's "address_space" has a great example of the power of
 their linked lists.  Their struct has a private_list head.  Due to their list
@@ -136,8 +138,57 @@ the "address space" of the device, mapping from (file,index) -> page_frame.
 Still, calling it an address space just confuses things with the virtual memory
 address space.
 
-One of the reasons pages can be in the map without valid data is due to
+One of the reasons pages can be in the map without up-to-date data is due to
 concurrency issues and outstanding I/O requests.  When the page is first being
 filled up, the mapping exists but the data hasn't been brought in yet.  Other
 processes can be trying to access the same block/page/byte, and they need to
 block but to not try and schedule the operation.  
+
+So here's how a typical page fault (__handle_page_fault(), either on demand or
+populated) works on an mmap'd file at a high level.
+1. PF is on a virt address -> translated by the vm_region to a file/offset (page).
+1b. Weird permission issues?  See below!
+2. Look it up in the page_map.
+3. If the page is already there, and up-to-date, then great.  Skip to 6.  If
+there is one, but it's not up to date, skip to 5.
+4. If there is no page, get a free page, tie it (bidirectionally) to the inode
+in the page_map.
+5. Now there is a page, but it is not up to date, so call readpage().  This will
+usually block.
+6. Map that page (which has the current contents) into the address space of the
+calling process (with the appropriate permissions, RO (MAP_PRIVATE, CoW), or
+RW (MAP_SHARED).
+Below: Now if in step 1 you had a permissions issue, such as a RW fault on a CoW
+MAP_PRIVATE, you'll have to notice the type of error and the type of memory
+region, then go through a separate path: get a new page, copy the contents, and
+change the mapping.  Note, the page backing that mapping is not backed by the
+file - it's just sitting around in the virtual memory of the process.
+
+Also, if we want to use the PG_DIRTY flag, we'll need mark the regions as RO
+until we write fault, at which point we dirty the page and change it to RW.
+
+We could have multiple threads trying to fill a page in the page cache at once.
+This is handled in file_load_page().  All threads check the page cache.  If two
+threads try to add it to the page cache, only one will succeed, and the page
+will be locked (PG_LOCKED).  The one who succeeds will readpage().  The one that
+didn't will be like any other thread that is checking the page cache - it will
+see a page is there, and will check it the page is up to date.  If it isn't, it
+will try to lock the page so it can do the IO, with a few extra checks in case
+the page had been removed or was filled in while it slept.
+
+A big aspect of this is the use of lock_page() to block.  If the page is locked,
+you block until it is unlocked.  (implementation and other issues still
+pending).  Even the caller of readpage will lock after submitting the IO
+request.  This will cause the caller to sleep until the IO is done.  When the IO
+is done, that interrupt handler/thread will mark the page as up-to-date, and
+unlock the page, which will wake up any of the waiters.  The caller of
+readpage() may not be the first to wake up either.  This all means the IO system
+needs to know about marking pages as up-to-date and unlocking them.  This
+currently (Jul10) is just sitting in KFS, but can be done later either directly
+or with a callback made by
+whoever starts the IO.
+
+A note on refcnting.  When a page is added to the page cache, that's a stored
+reference.  When you lookup a page in the page cache, you get a refcnt'd
+reference back.  When you pull a page from the page cache, you also get a
+refcnt'd reference back - specifically it is the ref that was in the page map.
index fa08e41..0e9448c 100644 (file)
@@ -25,9 +25,9 @@ typedef LIST_HEAD(PageList, page) page_list_t;
 typedef LIST_ENTRY(page) page_list_entry_t;
 
 /* Per-page flag bits related to their state in the page cache */
-#define PG_LOCKED              0x01
-#define PG_VALID               0x02
-#define PG_DIRTY               0x04
+#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 */
 
 /* 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
@@ -66,6 +66,8 @@ size_t page_getref(page_t *SAFE page);
 void page_setref(page_t *SAFE page, size_t val);
 
 int page_is_free(size_t ppn);
+void lock_page(struct page *page);
+void unlock_page(struct page *page);
 
 #endif //PAGE_ALLOC_H
 
index ab3f451..dd1b2c5 100644 (file)
@@ -20,6 +20,7 @@
 #include <timing.h>
 #include <page_alloc.h>
 #include <mm.h>
+#include <radix.h>
 
 // TODO: temp typedefs, etc.  remove when we support this stuff.
 typedef int dev_t;
@@ -30,7 +31,6 @@ struct block_device   {int x;};
 struct io_writeback    {int x;};
 struct event_poll {int x;};
 struct poll_table_struct {int x;};
-struct radix_tree;
 // end temp typedefs
 
 struct page_map;       /* analagous to linux's address_space object */
@@ -102,8 +102,8 @@ struct nameidata {
  * It is a map, per object, from index to physical page frame. */
 struct page_map {
        struct inode                            *pm_host;               /* inode of the owner, if any */
-       struct radix_tree                       *pm_tree_root;  /* tracks present pages */
-       spinlock_t                                      pm_tree_lock;
+       struct radix_tree                       pm_tree;                /* tracks present pages */
+       spinlock_t                                      pm_tree_lock;   /* spinlock => we can't block */
        unsigned long                           pm_num_pages;   /* how many pages are present */
        struct page_map_operations      *pm_op;
        unsigned int                            pm_flags;
@@ -199,7 +199,7 @@ struct inode {
        struct file_operations          *i_fop;
        struct super_block                      *i_sb;
        struct page_map                         *i_mapping;             /* usually points to i_data */
-       struct page_map                         i_data;                 /* this inode's page cache */
+       struct page_map                         i_pm;                   /* this inode's page cache */
        union {
                struct pipe_inode_info          *i_pipe;
                struct block_device                     *i_bdev;
@@ -409,15 +409,25 @@ extern struct kmem_cache *dentry_kcache;
 extern struct kmem_cache *inode_kcache;
 extern struct kmem_cache *file_kcache;
 
-/* VFS Functions */
+/* Misc VFS functions */
 void vfs_init(void);
 void qstr_builder(struct dentry *dentry, char *l_name);
+
+/* Superblock functions */
 struct super_block *get_sb(void);
 void init_sb(struct super_block *sb, struct vfsmount *vmnt,
              struct dentry_operations *d_op, unsigned long root_ino,
              void *d_fs_info);
+
+/* Dentry Functions */
 struct dentry *get_dentry(struct super_block *sb, struct dentry *parent,
                           char *name);
 void dcache_put(struct dentry *dentry);
 
+/* Page cache functions */
+struct page *pm_find_page(struct page_map *pm, unsigned long index);
+int pm_insert_page(struct page_map *pm, unsigned long index, struct page *page);
+int pm_remove_page(struct page_map *pm, struct page *page);
+int file_load_page(struct file *file, unsigned long index, struct page **pp);
+
 #endif /* ROS_KERN_VFS_H */
index d1a8d13..85c5002 100644 (file)
@@ -30,6 +30,7 @@
 
 /* VFS required Functions */
 /* These structs are declared again and initialized farther down */
+struct page_map_operations kfs_pm_op;
 struct super_operations kfs_s_op;
 struct inode_operations kfs_i_op;
 struct dentry_operations kfs_d_op;
@@ -110,6 +111,28 @@ void kfs_kill_sb(struct super_block *sb)
 struct fs_type kfs_fs_type = {"KFS", 0, kfs_get_sb, kfs_kill_sb, {0, 0},
                TAILQ_HEAD_INITIALIZER(kfs_fs_type.fs_supers)};
 
+/* Page Map Operations */
+
+/* Fills page with its contents from its backing store file.  Note that we do
+ * the zero padding here, instead of higher in the VFS.  Might change in the
+ * future. */
+int kfs_readpage(struct file *file, struct page *page)
+{
+       struct kfs_i_info *k_i_info = (struct kfs_i_info*)file->f_inode->i_fs_info;
+       uintptr_t begin = (size_t)k_i_info->filestart + page->pg_index * PGSIZE;
+       /* Need to be careful we don't copy beyond the EOF, and that we zero out
+        * whatever is left over.  The memset is a noop when copy_amt == PGSIZE. */
+       size_t copy_amt = MIN(PGSIZE, file->f_inode->i_size - begin);
+       memcpy(page2kva(page), (void*)begin, copy_amt);
+       memset(page2kva(page) + copy_amt, 0, PGSIZE - copy_amt);
+       /* 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. */
+       page->pg_flags |= PG_UPTODATE;
+       unlock_page(page);
+       return 0;
+}
+
 /* Super Operations */
 
 /* creates and initializes a new inode.  generic fields are filled in.  specific
@@ -135,6 +158,13 @@ struct inode *kfs_alloc_inode(struct super_block *sb)
        inode->i_fs_info = kmem_cache_alloc(kfs_i_kcache, 0);
        TAILQ_INIT(&((struct kfs_i_info*)inode->i_fs_info)->children);
        ((struct kfs_i_info*)inode->i_fs_info)->filestart = 0;
+       /* Set up the page_map structures.  Default is to use the embedded one. */
+       inode->i_mapping = &inode->i_pm;
+       inode->i_mapping->pm_host = inode;
+       radix_tree_init(&inode->i_mapping->pm_tree);
+       spinlock_init(&inode->i_mapping->pm_tree_lock);
+       inode->i_mapping->pm_op = &kfs_pm_op;
+       inode->i_mapping->pm_flags = 0;
        return inode;
        /* caller sets i_ino, i_list set when applicable */
 }
@@ -175,8 +205,7 @@ void kfs_read_inode(struct inode *inode)
        } else {
                panic("Not implemented");
        }
-       /* TODO: unused: inode->i_hash add to hash (saves on disc reading)
-        * i_mapping, i_data, when they mean something */
+       /* TODO: unused: inode->i_hash add to hash (saves on disc reading) */
 }
 
 /* called when an inode in memory is modified (journalling FS's care) */
@@ -667,7 +696,7 @@ int kfs_open(struct inode *inode, struct file *file)
 //     struct event_poll_tailq         f_ep_links;
        spinlock_init(&file->f_ep_lock);
        file->f_fs_info = 0;
-//     struct page_map                         *f_mapping;             /* page cache mapping */
+       file->f_mapping = inode->i_mapping;
        return 0;
 }
 
@@ -727,6 +756,10 @@ int kfs_check_flags(int flags)
 }
 
 /* Redeclaration and initialization of the FS ops structures */
+struct page_map_operations kfs_pm_op = {
+       kfs_readpage,
+};
+
 struct super_operations kfs_s_op = {
        kfs_alloc_inode,
        kfs_destroy_inode,
index 2d17605..a49cc99 100644 (file)
@@ -499,15 +499,13 @@ int handle_page_fault(struct proc* p, uintptr_t va, int prot)
  * faulted for a different reason (was mprotected on another core), and the
  * shootdown is on its way.  Userspace should have waited for the mprotect to
  * return before trying to write (or whatever), so we don't care and will fault
- * them.
- *
- * We did away with mmapping too much of a file, and will map an entire page, if
- * that file is big enough.  The alternative is to zerofill the last bit if the
- * vmr had a lesser length.  This makes shared mappings and mappings backed by
- * the FS problematic. */
+ * them. */
 int __handle_page_fault(struct proc* p, uintptr_t va, int prot)
 {
        struct vm_region *vmr;
+       struct page *a_page;
+       unsigned int f_idx;     /* index of the missing page in the file */
+       int retval = 0;
        /* Check the vmr's protection */
        vmr = find_vmr(p, va);
        if (!vmr)                                                       /* not mapped at all */
@@ -529,35 +527,29 @@ int __handle_page_fault(struct proc* p, uintptr_t va, int prot)
                panic("Swapping not supported!");
                return 0;
        }
-       /* allocate a page; maybe zero-fill it */
-       bool zerofill = (vmr->vm_file == NULL);
-       page_t *a_page;
-       if (upage_alloc(p, &a_page, zerofill))
-               return -ENOMEM;
-       /* if this isn't a zero-filled page, read it in from file.  it is the FS's
-        * responsibility to zero out the end of the last page if the EOF is not at
-        * the end of the page.
-        *
-        * TODO: (BLK) doing this while holding the mem lock!  prob want to block
-        * and return to userspace if it's not in the buffer cache.  will want to
-        * set a flag in the vmr so that subsequent faults will know the work is in
-        * progress. */
-       if (!zerofill) {
-               int foffset = ROUNDDOWN(va, PGSIZE) - vmr->vm_base + vmr->vm_foff;
-               int read_len = file_read_page(vmr->vm_file, page2pa(a_page), foffset);
-               if (read_len < 0) {
-                       page_free(a_page);
-                       return read_len;                        /* pass out the error code, for now */
-               }
+       if (!vmr->vm_file) {
+               /* No file - just want anonymous memory */
+               if (upage_alloc(p, &a_page, TRUE))
+                       return -ENOMEM;
+       } else {
+               /* Load the file's page in the page cache.
+                * TODO: (BLK) Note, we are holding the mem lock!  We need to rewrite
+                * this stuff so we aren't hold the lock as excessively as we are, and
+                * such that we can block and resume later. */
+               f_idx = (va - vmr->vm_base + vmr->vm_foff) >> PGSHIFT;
+               retval = file_load_page(vmr->vm_file, f_idx, &a_page);
+               if (retval)
+                       return retval;
                /* if this is an executable page, we might have to flush the instruction
                 * cache if our HW requires it. */
                if (vmr->vm_prot & PROT_EXEC)
                        icache_flush_page((void*)va, page2kva(a_page));
        }
-       /* update the page table */
+       /* update the page table TODO: careful with MAP_PRIVATE etc.  might do this
+        * separately (file, no file) */
        int pte_prot = (vmr->vm_prot & PROT_WRITE) ? PTE_USER_RW :
                       (vmr->vm_prot & (PROT_READ|PROT_EXEC)) ? PTE_USER_RO : 0;
-       page_incref(a_page);
+       page_incref(a_page);    /* incref, since we manually insert in the pgdir */
        *pte = PTE(page2ppn(a_page), PTE_P | pte_prot);
        return 0;
 }
index 8a5f06f..c2a45b1 100644 (file)
@@ -338,3 +338,22 @@ size_t page_getref(page_t *page)
        return atomic_read(&page->pg_refcnt);
 }
 
+/* Attempts to get a lock on the page for IO operations.  If it is already
+ * locked, it will block the thread until it is unlocked. */
+void lock_page(struct page *page)
+{
+       /* TODO: (BLK) actually do something!  And this has a race!  Not a big deal
+        * right now, since the only users of this are serialized, but once we have
+        * any sort of real IO, this will be an issue. */
+       assert(!(page->pg_flags & PG_LOCKED));
+       page->pg_flags |= PG_LOCKED;
+}
+
+/* Unlocks the page, and wakes up whoever is waiting on the lock */
+void unlock_page(struct page *page)
+{
+       /* TODO: (BLK) actually do something!  However this unlock works, it will
+        * need to know who to unlock, and it will have to be called in response to
+        * a basic interrupt...  */
+       page->pg_flags &= ~PG_LOCKED;
+}
index adc3e2d..cb682bb 100644 (file)
@@ -234,3 +234,120 @@ void dcache_put(struct dentry *dentry)
        SLIST_INSERT_HEAD(&dcache, dentry, d_hash);
        spin_unlock(&dcache_lock);
 }
+
+/* Looks up the index'th page in the page map, returning an incref'd reference,
+ * or 0 if it was not in the map. */
+struct page *pm_find_page(struct page_map *pm, unsigned long index)
+{
+       spin_lock(&pm->pm_tree_lock);
+       struct page *page = (struct page*)radix_lookup(&pm->pm_tree, index);
+       if (page)
+               page_incref(page);
+       spin_unlock(&pm->pm_tree_lock);
+       return page;
+}
+
+/* Attempts to insert the page into the page_map, returns 0 for success, or an
+ * error code if there was one already (EEXIST) or we ran out of memory
+ * (ENOMEM).  On success, this will preemptively lock the page, and will also
+ * store a reference to the page in the pm. */
+int pm_insert_page(struct page_map *pm, unsigned long index, struct page *page)
+{
+       int error = 0;
+       spin_lock(&pm->pm_tree_lock);
+       error = radix_insert(&pm->pm_tree, index, page);
+       if (!error) {
+               page_incref(page);
+               page->pg_flags |= PG_LOCKED;
+               page->pg_mapping = pm;
+               page->pg_index = index;
+               pm->pm_num_pages++;
+       }
+       spin_unlock(&pm->pm_tree_lock);
+       return error;
+}
+
+/* Removes the page, including its reference.  Not sure yet what interface we
+ * want to this (pm and index or page), and this has never been used.  There are
+ * also issues with when you want to call this, since a page in the cache may be
+ * mmap'd by someone else. */
+int pm_remove_page(struct page_map *pm, struct page *page)
+{
+       void *retval;
+       warn("pm_remove_page() hasn't been thought through or tested.");
+       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;
+}
+
+/* Makes sure the index'th page from file is loaded in the page cache and
+ * returns its location via **pp.  Note this will give you a refcnt'd reference.
+ * This may block! TODO: (BLK) */
+int file_load_page(struct file *file, unsigned long index, struct page **pp)
+{
+       struct page_map *pm = file->f_mapping;
+       struct page *page;
+       int error;
+       bool page_was_mapped = TRUE;
+
+       page = pm_find_page(pm, index);
+       while (!page) {
+               /* kpage_alloc, since we want the page to persist after the proc
+                * dies (can be used by others, until the inode shuts down). */
+               if (kpage_alloc(&page))
+                       return -ENOMEM;
+               /* might want to initialize other things, perhaps in page_alloc() */
+               page->pg_flags = 0;
+               error = pm_insert_page(pm, index, page);
+               switch (error) {
+                       case 0:
+                               page_was_mapped = FALSE;
+                               break;
+                       case -EEXIST:
+                               /* the page was mapped already (benign race), just get rid of
+                                * our page and try again (the only case that uses the while) */
+                               page_decref(page);
+                               page = pm_find_page(pm, index);
+                               break;
+                       default:
+                               /* something is wrong, bail out! */
+                               page_decref(page);
+                               return error;
+               }
+       }
+       *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
+        * us, we skip this since we are the one doing the readpage(). */
+       if (page_was_mapped) {
+               /* is it already here and up to date?  if so, we're done */
+               if (page->pg_flags & PG_UPTODATE)
+                       return 0;
+               /* if not, try to lock the page (could BLOCK) */
+               lock_page(page);
+               /* we got it, is our page still in the cache?  check the mapping.  if
+                * not, start over, perhaps with EAGAIN and outside support */
+               if (!page->pg_mapping)
+                       panic("Page is not in the mapping!  Haven't implemented this!");
+               /* double check, are we up to date?  if so, we're done */
+               if (page->pg_flags & PG_UPTODATE) {
+                       unlock_page(page);
+                       return 0;
+               }
+       }
+       /* if we're here, the page is locked by us, and it needs to be read in */
+       assert(page->pg_mapping == pm);
+       error = pm->pm_op->readpage(file, page);
+       assert(!error);
+       /* Try to sleep on the IO.  The page will be unlocked when the IO is done */
+       lock_page(page);
+       unlock_page(page);
+       assert(page->pg_flags & PG_UPTODATE);
+       return 0;
+}