Initial page cache structures
authorBarret Rhoden <brho@cs.berkeley.edu>
Fri, 9 Jul 2010 22:59:15 +0000 (15:59 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:35:48 +0000 (17:35 -0700)
Also changed a few things with the struct page and some of its
functions, including making it use atomics (albeit poorly).  For now,
don't trust page_incref() and page_decref() to work concurrently.

Documentation/vfs.txt
kern/arch/i686/page_alloc.c
kern/arch/i686/pmap.c
kern/arch/sparc/page_alloc.c
kern/include/colored_page_alloc.h
kern/include/page_alloc.h
kern/include/vfs.h
kern/src/kfs.c
kern/src/page_alloc.c
kern/src/testing.c

index abb14c8..5a9d86a 100644 (file)
@@ -106,3 +106,38 @@ memory from creation time.   Yeah, this means we have chunks of metadata for
 files we aren't using sitting around in RAM.  We also have the *files* sitting
 around in RAM too.  Not that concerned, for now.  Plus, I don't want to reparse
 the CPIO backing store to figure out inode fields, directory names, etc.
+
+Page Cache:
+-------------------------------------------
+Every object that has pages, like an inode or the swap (or even direct block
+devices) has a page_map tracking which of its pages are currently in memory.
+This is called a struct address_space in linux, which is a confusing name.  We
+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.
+
+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
+implementation, they are able to have a generic list head for a list of any
+type (it's a struct list_head), and don't need to declare in a generic object
+(like the page_map) a specific list type (that would get used by specific
+FS's).
+
+Just because a page is in a page_map, it doesn't mean it actually has the
+data from the disc in it.  It just means that there is a physical frame
+dedicated/mapped to be a page_map's holder for a specific page of an object
+(usually a file on disc).  readpage() is called to fill that page in with what
+it is supposed to have from its backing store.
+
+This interpretation makes the meaning of "address space" make more sense.  It's
+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
+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.  
index 0ab6c1c..03ee4dc 100644 (file)
@@ -2,8 +2,8 @@
  * See the COPYRIGHT files at the top of this source tree for full 
  * license information.
  * 
- * Kevin Klues <klueska@cs.berkeley.edu>    
- */
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * Kevin Klues <klueska@cs.berkeley.edu> */
 
 #ifdef __SHARC__
 #pragma nosharc
@@ -61,38 +61,38 @@ void page_alloc_init()
        extern char (SNT RO end)[];
        physaddr_t physaddr_after_kernel = PADDR(PTRROUNDUP(boot_freemem, PGSIZE));
 
-       pages[0].page_ref = 1;
+       atomic_set(&pages[0].pg_refcnt, 1);
        // alloc the second page, since we will need it later to init the other cores
        // probably need to be smarter about what page we use (make this dynamic) TODO
-       pages[1].page_ref = 1;
+       atomic_set(&pages[1].pg_refcnt, 1);
        for (i = 2; i < LA2PPN(IOPHYSMEM); i++) {
-               pages[i].page_ref = 0;
+               pages[i].pg_refcnt = 0;
                LIST_INSERT_HEAD(
                   &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), 
                                                               llc_cache)]),
                   &pages[i],
-                  page_link
+                  pg_link
                );
        }
        for (i = LA2PPN(IOPHYSMEM); i < LA2PPN(EXTPHYSMEM); i++) {
-               pages[i].page_ref = 1;
+               atomic_set(&pages[i].pg_refcnt, 1);
        }
        for (i = LA2PPN(EXTPHYSMEM); i < LA2PPN(physaddr_after_kernel); i++) {
-               pages[i].page_ref = 1;
+               atomic_set(&pages[i].pg_refcnt, 1);
        }
        for (i = LA2PPN(physaddr_after_kernel); i < LA2PPN(maxaddrpa); i++) {
-               pages[i].page_ref = 0;
+               atomic_set(&pages[i].pg_refcnt, 0);
                LIST_INSERT_HEAD(
                   &(colored_page_free_list[get_page_color(page2ppn(&pages[i]), 
                                                               llc_cache)]),
                   &pages[i],
-                  page_link
+                  pg_link
                );
        }
        // this block out all memory above maxaddrpa.  will need another mechanism
        // to allocate and map these into the kernel address space
        for (i = LA2PPN(maxaddrpa); i < npages; i++) {
-               pages[i].page_ref = 1;
+               atomic_set(&pages[i].pg_refcnt, 1);
        }
        printk("Page alloc init successful\n");
 }
index 2f96baa..6509d35 100644 (file)
@@ -700,13 +700,13 @@ page_check(void)
        }
        assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
        assert(check_va2pa(boot_pgdir, 0x0) == page2pa(pp1));
-       assert(pp1->page_ref == 1);
-       assert(pp0->page_ref == 1);
+       assert(atomic_read(&pp1->pg_refcnt) == 1);
+       assert(atomic_read(&pp0->pg_refcnt) == 1);
 
        // should be able to map pp2 at PGSIZE because pp0 is already allocated for page table
        assert(page_insert(boot_pgdir, pp2, (void*SNT) PGSIZE, 0) == 0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
-       assert(pp2->page_ref == 1);
+       assert(atomic_read(&pp2->pg_refcnt) == 1);
 
        // Make sure that pgdir_walk returns a pointer to the pte and
        // not the table or some other garbage
@@ -721,7 +721,7 @@ page_check(void)
        // should be able to map pp2 at PGSIZE because it's already there
        assert(page_insert(boot_pgdir, pp2, (void*SNT) PGSIZE, PTE_U) == 0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp2));
-       assert(pp2->page_ref == 1);
+       assert(atomic_read(&pp2->pg_refcnt) == 1);
 
        // Make sure that we actually changed the permission on pp2 when we re-mapped it
        {
@@ -743,8 +743,8 @@ page_check(void)
        assert(check_va2pa(boot_pgdir, 0) == page2pa(pp1));
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
        // ... and ref counts should reflect this
-       assert(pp1->page_ref == 2);
-       assert(pp2->page_ref == 0);
+       assert(atomic_read(&pp1->pg_refcnt) == 2);
+       assert(atomic_read(&pp2->pg_refcnt) == 0);
 
        // pp2 should be returned by page_alloc
        assert(kpage_alloc(&pp) == 0 && pp == pp2);
@@ -754,15 +754,15 @@ page_check(void)
        page_remove(boot_pgdir, 0x0);
        assert(check_va2pa(boot_pgdir, 0x0) == ~0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == page2pa(pp1));
-       assert(pp1->page_ref == 1);
-       assert(pp2->page_ref == 0);
+       assert(atomic_read(&pp1->pg_refcnt) == 1);
+       assert(atomic_read(&pp2->pg_refcnt) == 0);
 
        // unmapping pp1 at PGSIZE should free it
        page_remove(boot_pgdir, (void*SNT) PGSIZE);
        assert(check_va2pa(boot_pgdir, 0x0) == ~0);
        assert(check_va2pa(boot_pgdir, PGSIZE) == ~0);
-       assert(pp1->page_ref == 0);
-       assert(pp2->page_ref == 0);
+       assert(atomic_read(&pp1->pg_refcnt) == 0);
+       assert(atomic_read(&pp2->pg_refcnt) == 0);
 
        // so it should be returned by page_alloc
        assert(kpage_alloc(&pp) == 0 && pp == pp1);
@@ -774,8 +774,8 @@ page_check(void)
        // forcibly take pp0 back
        assert(PTE_ADDR(boot_pgdir[0]) == page2pa(pp0));
        boot_pgdir[0] = 0;
-       assert(pp0->page_ref == 1);
-       pp0->page_ref = 0;
+       assert(atomic_read(&pp0->pg_refcnt) == 1);
+       atomic_set(&pp0->pg_refcnt, 0);
 
        // Catch invalid pointer addition in pgdir_walk - i.e. pgdir + PDX(va)
        {
@@ -789,7 +789,7 @@ page_check(void)
 
          // Clean up again
          boot_pgdir[PDX(va)] = 0;
-         pp0->page_ref = 0;
+         atomic_set(&pp0->pg_refcnt, 0);
        }
 
        // give free list back
index 7518d81..cadce1f 100644 (file)
@@ -64,20 +64,20 @@ void page_alloc_init()
 
        // mark [0, physaddr_after_kernel) as in-use
        for(i = 0; i < LA2PPN(physaddr_after_kernel); i++)
-               pages[i].page_ref = 1;
+               pages[i].pg_refcnt = 1;
 
        // mark [physaddr_after_kernel, maxaddrpa) as free
        for(i = LA2PPN(physaddr_after_kernel); i < LA2PPN(maxaddrpa); i++)
        {
-               pages[i].page_ref = 0;
+               pages[i].pg_refcnt = 0;
                 LIST_INSERT_HEAD(
                    &(colored_page_free_list[get_page_color(i,llc_cache)]),
                    &pages[i],
-                   page_link
+                   pg_link
                 );
        }
 
        // mark [maxaddrpa, ...) as in-use (as they are invalid)
        for(i = LA2PPN(maxaddrpa); i < npages; i++)
-               pages[i].page_ref = 1;
+               pages[i].pg_refcnt = 1;
 }
index 5cbed43..82d761e 100644 (file)
@@ -15,7 +15,7 @@
 #include <stdio.h>
        
 #define DECLARE_CACHE_COLORED_PAGE_LINK(_cache)                               \
-       page_list_entry_t _cache##_cache_colored_page_link;
+       page_list_entry_t _cache##_cache_colored_pg_link;
        
 #define DECLARE_CACHE_COLORED_PAGE_FREE_LIST(_cache)                          \
        uint8_t _cache##_num_colors = 0;                                          \
@@ -55,7 +55,7 @@ error_t _cache##_page_alloc(page_t** page, size_t color)                      \
 
 #define REMOVE_CACHE_COLORING_PAGE_FROM_FREE_LIST(_page, _cache)              \
        if(available_caches._cache == TRUE)                                       \
-               LIST_REMOVE(*(_page), _cache##_cache_colored_page_link);
+               LIST_REMOVE(*(_page), _cache##_cache_colored_pg_link);
 
 
 #define INSERT_CACHE_COLORING_PAGE_ONTO_FREE_LIST(_page, _cache)              \
@@ -64,7 +64,7 @@ error_t _cache##_page_alloc(page_t** page, size_t color)                      \
                   &(_cache##_cache_colored_page_list                                 \
                         [get_page_color(page2ppn((_page)), &(_cache))]),             \
                   (_page),                                                           \
-                  _cache##_cache_colored_page_link                                   \
+                  _cache##_cache_colored_pg_link                                   \
                );                                                                    \
        }
 
index e6d7abe..fa08e41 100644 (file)
@@ -1,9 +1,9 @@
-/* Copyright (c) 2009 The Regents of the University  of California. 
+/* Copyright (c) 2009, 2010 The Regents of the University  of California. 
  * See the COPYRIGHT files at the top of this source tree for full 
  * license information.
  * 
  * Kevin Klues <klueska@cs.berkeley.edu>    
- */
+ * Barret Rhoden <brho@cs.berkeley.edu> */
  
 #ifndef PAGE_ALLOC_H
 #define PAGE_ALLOC_H
@@ -15,6 +15,8 @@
 #include <colored_page_alloc.h>
 #include <process.h>
 
+struct page_map;               /* preprocessor games */
+
 /****************** Page Structures *********************/
 struct page;
 typedef size_t ppn_t;
@@ -22,15 +24,22 @@ typedef struct page page_t;
 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
+
 /* 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
  * reference counting and atomic operations. */
 struct page {
-       page_list_entry_t LCKD(&colored_page_free_list_lock)page_link;
-    size_t page_ref;
+       LIST_ENTRY(page)                        pg_link;        /* membership in various lists */
+       atomic_t                                        pg_refcnt;
+       unsigned int                            pg_flags;
+       struct page_map                         *pg_mapping;
+       unsigned long                           pg_index;
 };
 
-
 /******** Externally visible global variables ************/
 extern uint8_t* global_cache_colors_map;
 extern spinlock_t colored_page_free_list_lock;
index 8beb857..ab3f451 100644 (file)
@@ -30,8 +30,11 @@ 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 */
+struct page_map_operations;
 struct super_block;
 struct super_operations;
 struct dentry;
@@ -94,6 +97,37 @@ struct nameidata {
        int                                                     intent;                 /* access type for the file */
 };
 
+/* Every object that has pages, like an inode or the swap (or even direct block
+ * devices) has a page_map, tracking which of its pages are currently in memory.
+ * 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;
+       unsigned long                           pm_num_pages;   /* how many pages are present */
+       struct page_map_operations      *pm_op;
+       unsigned int                            pm_flags;
+       /*... and private lists, backing block dev info, other mappings, etc. */
+};
+
+/* Operations performed on a page_map.  These are usually FS specific, which
+ * get assigned when the inode is created.
+ * Will fill these in as they are created/needed/used. */
+struct page_map_operations {
+       int (*readpage) (struct file *, struct page *); /* read from backing store*/
+/*     readpages: read a list of pages
+       writepage: write from a page to its backing store
+       writepages: write a list of pages
+       sync_page: start the IO of already scheduled ops
+       set_page_dirty: mark the given page dirty
+       prepare_write: prepare to write (disk backed pages)
+       commit_write: complete a write (disk backed pages)
+       bmap: get a logical block number from a file block index
+       invalidate page: invalidate, part of truncating
+       release page: prepare to release 
+       direct_io: bypass the page cache */
+};
+
 /* Superblock: Specific instance of a mounted filesystem.  All synchronization
  * is done with the one spinlock. */
 
@@ -164,8 +198,8 @@ struct inode {
        struct inode_operations         *i_op;
        struct file_operations          *i_fop;
        struct super_block                      *i_sb;
-       //struct address_space          *i_mapping;             /* linux mapping structs */
-       //struct address_space          i_data;                 /* rel page caches */
+       struct page_map                         *i_mapping;             /* usually points to i_data */
+       struct page_map                         i_data;                 /* this inode's page cache */
        union {
                struct pipe_inode_info          *i_pipe;
                struct block_device                     *i_bdev;
@@ -260,7 +294,7 @@ struct file {
        struct event_poll_tailq         f_ep_links;
        spinlock_t                                      f_ep_lock;
        void                                            *f_fs_info;             /* tty driver hook */
-       //struct address_space          *f_mapping;             /* page cache mapping */
+       struct page_map                         *f_mapping;             /* page cache mapping */
 
        /* Ghetto appserver support */
        int fd; // all it contains is an appserver fd (for pid 0, aka kernel)
index 76a1720..d1a8d13 100644 (file)
@@ -630,8 +630,11 @@ int kfs_readdir(struct file *dir, struct dirent *dirent)
        return 1;                                                       /* normal success for readdir */
 }
 
-/* Sets up a memory mapping of the file into the vm_region, based on the
- * parameters in the vmr. */
+/* This is called when a VMR is mapping a particular file.  The FS needs to do
+ * whatever it needs so that faults can be handled by read_page(), and handle all
+ * of the cases of MAP_SHARED, MAP_PRIVATE, whatever.  It also needs to ensure
+ * the file is not being mmaped in a way that conflicts with the manner in which
+ * the file was opened. */
 int kfs_mmap(struct file *file, struct vm_region *vmr)
 {
        /* the file is not page-aligned yet, so we need to copy it to fresh pages.
@@ -664,7 +667,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 address_space            *f_mapping;             /* page cache mapping */
+//     struct page_map                         *f_mapping;             /* page cache mapping */
        return 0;
 }
 
@@ -1032,7 +1035,7 @@ void print_dir_tree(struct dentry *dentry, int depth)
                print_dir_tree(d_i, depth + 1);
        }
        TAILQ_FOREACH(d_i, &k_i_info->children, d_subdirs_link) {
-               printk("%sDir %s has child file: %s", buf, dentry->d_name.name,
+               printk("%sDir %s has child file: %s ", buf, dentry->d_name.name,
                       d_i->d_name.name);
                printk("file starts at: %p\n",
                       ((struct kfs_i_info*)d_i->d_inode->i_fs_info)->filestart);
index 508fe05..8a5f06f 100644 (file)
@@ -1,9 +1,9 @@
-/* Copyright (c) 2009 The Regents of the University  of California. 
+/* Copyright (c) 2009, 2010 The Regents of the University  of California. 
  * See the COPYRIGHT files at the top of this source tree for full 
  * license information.
  * 
  * Kevin Klues <klueska@cs.berkeley.edu>    
- */
+ * Barret Rhoden <brho@cs.berkeley.edu> */
 
 #ifdef __SHARC__
 #pragma nosharc
@@ -67,7 +67,7 @@ static void __page_clear(page_t *SAFE page)
        /* Allocate a page from that color */                                   \
        if(i < (base_color+range)) {                                            \
                *page = LIST_FIRST(&colored_page_free_list[i]);                     \
-               LIST_REMOVE(*page, page_link);                                      \
+               LIST_REMOVE(*page, pg_link);                                      \
                __page_clear(*page);                                                \
                return i;                                                           \
        }                                                                       \
@@ -102,10 +102,10 @@ static ssize_t __colored_page_alloc(uint8_t* map, page_t** page,
 static error_t __page_alloc_specific(page_t** page, size_t ppn)
 {
        page_t* sp_page = ppn2page(ppn);
-       if( sp_page->page_ref != 0 )
+       if (atomic_read(&sp_page->pg_refcnt) != 0)
                return -ENOMEM;
        *page = sp_page;
-       LIST_REMOVE(*page, page_link);
+       LIST_REMOVE(*page, pg_link);
 
        __page_clear(*page);
        return 0;
@@ -245,7 +245,7 @@ error_t kpage_alloc_specific(page_t** page, size_t ppn)
 
 /*
  * Return a page to the free list.
- * (This function should only be called when pp->page_ref reaches 0.)
+ * (This function should only be called when pp->pg_refcnt reaches 0.)
  * You must hold the page_free list lock before calling this.
  */
 static error_t __page_free(page_t* page) 
@@ -255,7 +255,7 @@ static error_t __page_free(page_t* page)
        LIST_INSERT_HEAD(
           &(colored_page_free_list[get_page_color(page2ppn(page), llc_cache)]),
           page,
-          page_link
+          pg_link
        );
 
        return ESUCCESS;
@@ -275,7 +275,7 @@ error_t page_free(page_t *SAFE page)
  */
 int page_is_free(size_t ppn) {
        page_t* page = ppn2page(ppn);
-       if( page->page_ref == 0 )
+       if (atomic_read(&page->pg_refcnt) == 0)
                return TRUE;
        return FALSE;
 }
@@ -288,9 +288,10 @@ void page_incref(page_t *page)
        __page_incref(page);
 }
 
+/* TODO: (REF) poor refcnting */
 void __page_incref(page_t *page)
 {
-       page->page_ref++;
+       atomic_inc(&page->pg_refcnt);
 }
 
 /*
@@ -307,14 +308,17 @@ void page_decref(page_t *page)
 /*
  * Decrement the reference count on a page,
  * freeing it if there are no more refs.
+ *
+ * TODO: (REF) this is insufficient protection (poor use of atomics, etc).
  */
 static void __page_decref(page_t *page)
 {
-       if (page->page_ref == 0) {
+       if (atomic_read(&page->pg_refcnt) == 0) {
                panic("Trying to Free already freed page: %d...\n", page2ppn(page));
                return;
        }
-       if (--page->page_ref == 0)
+       atomic_dec(&page->pg_refcnt);
+       if (atomic_read(&page->pg_refcnt) == 0)
                __page_free(page);
 }
 
@@ -323,7 +327,7 @@ static void __page_decref(page_t *page)
  */
 void page_setref(page_t *page, size_t val)
 {
-       page->page_ref = val;
+       atomic_set(&page->pg_refcnt, val);
 }
 
 /*
@@ -331,6 +335,6 @@ void page_setref(page_t *page, size_t val)
  */
 size_t page_getref(page_t *page)
 {
-       return page->page_ref;
+       return atomic_read(&page->pg_refcnt);
 }
 
index 1903168..f0834f2 100644 (file)
@@ -137,7 +137,7 @@ void test_page_coloring(void)
        cprintf("Contents of the page free list:\n");
        for(int i=0; i<llc_cache->num_colors; i++) {
                cprintf("  COLOR %d:\n", i);
-               LIST_FOREACH(page, &colored_page_free_list[i], page_link) {
+               LIST_FOREACH(page, &colored_page_free_list[i], pg_link) {
                        cprintf("    Page: %d\n", page2ppn(page));
                }
        }