sys_unlink()
[akaros.git] / Documentation / vfs.txt
index abb14c8..108b17a 100644 (file)
@@ -106,3 +106,176 @@ 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.  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
+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 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.
+
+Files with Holes
+--------------------------
+If a file has a hole, we'll still try to look up the page in the page cache.
+When that doesn't happen, we'll create and add a page, then call readpage().
+Readpage will realize there is no page on disk/backing store for that part of
+the file (since it was a hole) and just memset the page to 0.  In the future, we
+can consider getting a CoW 0-page, but that's a bit premature and a bookkeeping
+pain.
+
+This also applies to trying to write to a block beyond the EOF.  If the request
+hits the page cache and readpage(), it's because it was already checked and
+cleared in another part of the VFS, such as in generic_file_write().
+
+Kref, Dentries, Inodes, and Files (or "I don't see why it's like X, but..."
+--------------------------
+There are multiple dentries pointing to an inode.  The dentries are (or will be)
+cached too, but that is irrelevant.  The dentries pin the inodes in memory.
+However, files pin inodes in memory (or they did) briefly.  After running around
+in circles a bit, I asked, why doesn't the file pin the dentry instead of the
+inode?  The answer: it is supposed to.  Linux does that, and I didn't because
+pinning the inode made more sense at the time.
+
+The heart of the issue is about understanding what files are and how they
+relate to the rest of the VFS.  A 'file' in the OS is a structure to track an
+open FS-disk-file, which is managed by the inode.  Given this, it makes sense
+that a dentry (which is a name on a path) would be pinned by the corresponding
+inode, and the file would pin the inode.  It doesn't, but it is believable.  In
+reality, there are many names (dentries) for a given disk file, and the OS file
+that you open corresponds to *one* of those names, and thus a dentry, and not to
+the inode/specific file.  You need to go through the dentry to pin the inode.
+
+In short, it's not: file -> inode -> dentry -> parent_dentry -> ...
+It's file -> dentry -> parent_dentry ->
+             |-> inode      |-> parent_inode
+Another dentry and file (both OS and disk) can point to the same inode.  If you
+don't do it this way, you can't pin up past the multi-dentry-point in the inode,
+and your system doesn't really make sense.
+
+So here is how it works: files pin dentries.  Dentries can pin other dentries,
+on up the directory hierarchy.  Independently of the files, dentries pin their
+inode.  There are many dentries per inode (or can be).  Since each dentry
+doesn't know if it is the last dentry to decref the inode, we use a kref on
+i_kref.  The inodes are storing references to the dentries, but they are the
+kref "internal" / weak references.  Even if we did decref them, we don't trigger
+anything with it.
+
+The moral of the story is that if you don't fully understand something, you are
+not in as good of a position to recommend changes or criticize as if you did
+your homework.  Not that you can't, just that you should 'do your homework.'
+
+Musings on path_lookup()
+--------------------------
+Things can get tricky with path lookup, especially with ., .., and symlinks.
+When doing a LOOKUP_PARENT on a . or .., we give the parent of whatever the path
+would have resolved too.  So /dir1/dir2/dir3/.'s parent is dir2.
+/dir1/dir2/dir3/..'s parent is dir1.  I don't think Linux does this (note the
+parent lookup is for internal kernel stuff, like when you want to edit
+metadata).  When you try to make a . or .. file, you should get some sort of
+error anyways.  We'll see how this works out.
+
+Symlinks can be a bit tricky.  We handle ours a bit differently too, especially
+regarding PARENT lookups.  Ultimately, you can do the same things in ROS that
+you can do in Linux - if you try to create a file that is a dangling symlink,
+you'll correctly create the destination file.  We handle this in
+link_path_walk().  It will return the PARENT of whatever you would resolve to -
+instead of trying to handle this in do_file_open() (which I think linux does).
+
+Also, our handling of symlinks differs a bit from linux.  Eventually, it has
+become clear we're going to need to manually port ext2, and we do some things
+differently in our core VFS already.  Might as well do more thing differently -
+like getting rid of follow_link and put_link from the FS specific sections.  Our
+FSs just need to know how to return a char* for a symname - and not do any of
+the actual link following.  Or any of the other stuff they do.  We'll see if
+that turns out to be an issue or not...
+
+Unlinking
+-------------------------
+Unlinking is just disconnecting a dentry-inode pair from the directory tree, and
+decreasing the inode's i_nlink.  Nothing else happens yet, since we need to keep
+the FS-file (controlled by the dentry/inode) so long as any OS-files have it
+open.  They have it opened via open or mmap - any way that there is a reference
+to a file, which then pins the dentry and inode.  When the OS-files close,
+eventually the dentry's refcnt hits 0.  When it does, it normally would be up
+for caching, but we can check nlinks and just drop it.  When that happens, it
+releases the inode, which will see its nlinks is 0.  That will trigger the
+underlying FS to clear out the FS-file.