README sync

[LaFS.git] / README

So, let's try to write a kernel module that implements this filesystem.
It would be good to have a plan.

- Mount filesystem, providing empty root directory
   o parse mount options - DONE
   o find/load superblocks and stateblocks - DONE
   o present empty directory - DONE
   o Compile external module - DONE
   o test DONE

- Mount filesystem read-only with no roll-forward
   o IO address mapping
          sync_page_io or bread? - not bread I think
   o Index blocks management
   o search cluster-header for root inode
   o file read
   o Directory lookup/read
   o test

- Support roll-forward for blocks, orphans, whatever
   o manage segusage files
   o manage quota files

- Support writing
   o inode bitmap
   o cluster creation / block sorting

- Support Cleaning

- Interface for snapshots and other admin



------------------------
FIXME
 If a device is removed from the filesystem, we cannot reliably
 tell from the other devices or state that this is so.
 Maybe we need to update all devblocks with a new 'seq' number...
FIXME
 How do we specify mounting subordinate filesets?
 What superblock do they have?
 I suspect we do a -F lafs-sub mount from the original filesystem.

FIXME
 If mount fails, we seem to be leaving a super lying around,
 and sync_supers dies on it. - DONE

FIXME
  Umount appear to work, but a sync_supers dies. - DONE

FIXME
  subordinate supers aren't being locked as much - is that a problem?

FIXME
  index pages never get put on an LRU - how is this supposed to work?







--------------------------
Thoughts:
  Inodes live in an address-space, much like a file.  To load the
  first inode, we need an address-space, so may as well have an
  'struct inode' as we may want to expose it to user-space.

 Loading an inode, need
   fs (lafs filesystem structure)
   which subfs (maybe a lafs inode)
   which snapshot - this is implied by the subfs inode.
   and fs can be obtained from inode, so just inode, inum



UPTO
03nov2005
  review block_leaf_find and make_iblock
  need to do setparent and block_adopt next

10nov2005
  need to resolve locking for ->siblings list

24nov2005
  peer_find
  lock_phase
  lafs_refile
  
  I can read a file.....!!!!!
  Code review / tidy up.
     resolve locking buffer vs page

  Export on a web page somewhere??

16feb2006
 (I spent a while getting large-directories to work again in prototype..
  and some holidays).
 - Priority: clean mount and unmount
 - large directories
 - multiple devices.

  FIXME how do we record and handle write errors???

 The iput in lafs_release - which is needed - is oopsing
  at iput+0xe!

23feb2006
 Ok, I finally have a clean mount/unmount.
 .. not quite.  blocks being freed at unmount still have a refcnt, which is bad.

 Next:
  - make sure we can handle 'large' directories.
  - make sure we can handle files with indexes
  - handle filesystems that span devices.

02mar2006
  Hurray - clean unmounts!!!
  There is a nasty circular reference of the root inode which is stored in 
  a block that it manages.  Maybe this should not happen, rather than having to be
  explicitly broken - the root-block can live elsewhere, not in the inode.

  Next multi-level index blocks.

  But first, need to understand memory pressure and pageout.
   How are dirty pages found to be cleaned?
   How is pressure put on a filesystem to clean up?
   How are clean pages reaped?

  - call pagevec_lru_add{,_active)(pvec)  to put the page on an LRU
      lru_cache_add{,_active}(page) might be easier, but isn't exported.
  - call mark_page_accessed(page)  to keep the page 'active'.

09mar2006
  - make sure indexes work...


 lafs_load_block+0xf
  eax,bx,cx,dx,s1 all zero
from block_leaf_find 203

  ... OK, indexes seem to work.
   But 'lafs' have problems creating some large files. 
   Try 'tt'

   This is due to not handling error properly.. fix it later FIXME

16mar2006

  Must make sure the index address-space gets clearred up... I wonder
  how we find all the pages to free.  This might be one reason to keep them
  in a radix tree.  Though we should be able to walk our own data structures.


  Then work on mounting a 2-device filesystem.


  FIXME dir_next_ent always starts from the beginning rather than 
   remembering where it is up to... can this be fixed??


18mar2006 (Wedding anniversary, and Saturday ... during commonwealth games)

  Mounting snapshot needs a way to identify that it is a snapshotmount
  and which snapshot, and which filesystem.
  We could use a different filesystem type, but that isn't really needed

    mount -t lafs -o snapshot=name /original/mount/point /new

  This grabs the named snapshot of /original/mount/point and places it at 
      /new
  The 'snapshot=' option is the trigger.

  For a control FS, we
        mount -t lafs -o control /original/mount/point /new

  To grow a filesystem, we initialise a device (super/state blocks) and
        mount -t lafs -o remount,new=/dev/name whatever /original/mount/point

  as the dev_name isn't passed to remount

  So, mount options are:
        snapshot=name
        dev=/dev/device
        new=/dev/device
        control
    and various
          name=value 
    pairs matching what is exposed in the control filesystem

23mar2006
 - factored out super-block finding preparatory to finding snapshots.

 Thoughts:
    superblocks for snapshots and sub-ordinate filesystems do
    not get stored in the 'state'.  There is, however, a usage count so that
    the prime filesystem cannot be unmounted until all snaps and subs are gone.
    This should just refcount the prime_sb I suspect.

    So: a snapshot sb points to the 'struct fs' but doesn't .... what???

30mar2006
 - remove the super-block finding code by changing the layout to store
    superblock locations explicitly :-)

 - teach 'mount' to mount snapshots.

 - need to audit for bad use of ss[0]
 - need to find better way to map 'sb' to snapshot number.
 - need to make unmount work.

01apr2006 (no, really!!)
 - rewrite index to kmalloc index blocks and use a shrinker to free them.
   This means that indexblock no longer has a 'page', which makes sense.
   It also means they cannot live in highmem, which is sad, but could
   be fixed.

  Notes: superblocks and refcounts.
   Each device holding the filesystem gets a superblock.
    One of these (arbitrarily) is the 'prime' superblock and gets to
      manage the whole filesystem.
    Each snapshot also gets a superblock, as does each
      subordinate filesystem.  These are anon sbs - using anon dev.
    Each anon sb takes a reference to the 'struct fs', and also to the
      prime sb.... how about the reference relationship between fs and prime_sb???

    Need to ponder this,

   - problem with getting parent superblock due to semaphores...
   - when unmount, put_super isn't being called, so inode 0 isn't released!

13apr2006
  (Took a week off to play with rt2500 wireless cards)
  - Use different filesystem type for snapshots and subordinate filesystems.
    This removes the semaphore problem
  + OK, mount and unmount works for snapshots... what next?
     - review index block - worry about himem?
     - review ss[0] usage - OK
     - general code review

  FIXME - what should leaf_lookup/index_lookup return on format error?
      The currently return '0' which will quietly make an empty block.
      Many '-1' would be better to make an error block.
  FIXME check how other filesystem lock the setting of PagePrivate
     Maybe just need to lock_page
  FIXME combine find/load/wait into one operation
  Review dir, super, roll, link

  FIXME module refcount increases on failed mount!

18may2006
  I've been sick for too long, and not much has happened... However I think more than
  the above comment says.  I started looking at roll-forward and have the 
  basic block parsing in place so that it reports what it sees in the roll.
  Also, the format has been changes a little: the address in the state block
  is the CheckpointStart cluster, and we simply roll forward to the
  CheckpointEnd, and then keep going beyond there - there is no longer any
  walking back to find the start.

  Next step is to start incorporating rolled elements into the filesystem

   - data blocks: shouldn't be too hard.  Don't need to update the
           index pages just yet
   - inode updates: should be straight forward enough, but care is needed
           as the data might be in multiple places
   - directory updates: these are probably most interesting..


  Question: how are symlinks created?
    Currently we:
      log the inode creation
      commit the new inode
      log the directory update.
    This allows the 'value' stored in the inode to appear after the directory
    update.
    That might be OK for files (Which are created empty and then extended)
    but is bad for symlinks (which are created atomically).
    So, options include:
     - ensure inode is in a previous cluster to directory updates.
       This slows things down too much I think
     - log the content as well.  This is awkward if it is big, certainly if more
       than a block, which is possible.
     - directory updates could be dependant on the inode being valid.
       This is ugly.
     - log content if it is small, else write inode, flush, then create link.

    So the fast option is:
      log inode create, log content, log filename
    and the slow/safe option is
      log inode ceate, sync file, log filename

    So on roll-forward if we see the inode we just save the data.
    Saving the whole inode seems attractive, but we want minimal order
    dependance: an inode update in the same cluster as the new inode should
    still over-ride, even though it is earlier.

  Ok, rollforward is proceeding slowly.  I think I am now incorporating
  new blocks into the tree properly, though the code probably won't compile.
  It will be nice to test this and see the file have the right data.

  Next step would be to include the index incorporation code.
  Then
    - directory updates
    - segusage summary
    - quota
    - stuff..

08jun2006
 - what exactly should happen when rollforward finds a file with a linkcount of 0?
   Currently all updates get lost - I wonder if they are lost safely?
 - rollforward is getting the size right, but not the content
 - do I need to flag a block that ->phys is valid?

 : Ok, roll-forward picks up new blocks in a file OK,
  but umount has stopped working.
    Presumably because there are pages attached to the inode which aren't
    getting released.  What do we want to do here?
    Normally those pages, or their addresses need to be recorded before
    they are lost.  But on a read-only mount we don't care so much.

22jun2006    continuing above thought..

   When we roll-forward and pick up the pieces of a file, we don't
   want to allocate pages to hold those pieces (and definitely don't
   want to read them all).  We just want to attach the addresses
   to the parent for incorporation.  Similarly after writing
   dirty blocks in a file we want to be able to release them
   immediately rather than waiting for the addresses to be
   incorporated (as incorporation can be more efficient when delayed).

   We could just allow the page associated with a block to be released,
   except that the page provides the indexing to find a block.  We might
   be able to live without the indexing, and hunt down the indexblock tree,
   but living without the mutual-exclusion provided by block indexing would
   be more awkward.
   And the 'struct datablock' still contains a lot more than is needed.

   So maybe we should just have a completely separate structure attached to
   the indexblock which lists fileaddr/physaddr.  This could include
   extent information.  The trick would be guranteeing allocation.
   We could either allocate-late with a fallback of attaching the 'struct block'
   or performing an immediate incorporation, or allocate-early and block
   the dirtying of a page until there is space to record the new address.
   This last is bound to be easiest.

   So: what exactly do we use to store addresses?
    Probably a linked list of tables.
    Each table contains a link pointer and an array of
        fileaddr/physaddr/extentlen
    But we would need to allocate lots of these if there are hundreds of
      dirty pages, but possibly only end up using a few if they made
      extents very nicely.  That might be wasteful.

    Or we could allocate just one.  When it is full we perform an
     incorporation.  But if that causes a page split we are in trouble.
       We could have a spare page, split to it, write out one
        and wait for the spare page to be written and free.
        But we cannot just release the index page as it might still have
        children.

    (I think I've been here before).
    A worst-case scenario involves writing one block and that requires
      spliting every index up the tree to the inode.  This requires
      arbitrarily many pages to be allocated.  To accomodate this we either
      pre-allocate a spare page at every level of the tree down to the data
      block (a bit like storage space allocation) which seems very wasteful,
      or we make sure we can release one of the split pages, which seems impossible.

    I could decide not to worry about it.  Have a pool of index pages and hope
     it always works.  Afterall, most pages are data pages, and they can be 
     freed successfully.  We would only have a deadlock if all dirty memory were
     index pages, and that seems unbelievably unlikely.  If we trigger a 
     checkpoint when the count of locked-pages hits some limit we should be
     safe.

    So: Keep one table per index block.  Use simple append and sequential search.
     When table gets full, force an incorporation

     Do we allocate the table separately, or embed it in the indexblock??

     Probably embed it.  indexblocks that don't need it can be freed at any
     time so that space waste hopefully isn't significant.

     How big?
      If the file is written sequentially, then everything should gather into
      extents, and so it doesn't need to be enormous.
      If the file is written randomly then the index block can be expected to
      be 'indirect', so incorporation will be cheap.
     So 'small' seems ok in both cases.

     Let's say 8.

     But wait a minute.....
     On a checkpoint we can be getting phys updates for prev and next phases.
     next-phase updates cannot be incorporated until the indexblock has passed
     on to the next phase.  So in that case, I think we still keep a linked
     list of unincorporated blocks and live with the fact that we cannot
     free them until the phase change passes.  That shouldn't be a big problem
     as it is a limited time frame - especially for data blocks..

     But does this solve our initial problem??
     During roll-forward we want to keep the addresses but not the blocks,
     and we don't want to force incorporation. That means an arbitrary list
     of addresses attached to an index block.
     I guess we could possibly allow incorporation, but I would rather not
     as I want the fs to be able to be read-only nicely.
     So that means we need to have a list of address tables.
     Maybe the normal approach is 'add a table if possible, else incorporate'?

     OUCH... we may write a block a second time before incorporating the
     new address, so when adding an address to the table we need to check
     if it already exists.  That could be expensive.
     For index blocks might it even be a different address?  I think
     not but the vague possibility (in the future?) does complicate
     things somewhat.  Maybe we just keep thing in chron order and
     don't worry about duplicates until incorporate time, when we have to
     sort anyway.


     todo:
        lafs_find_block  DONE
        free_block must free tables DONE


     Unmounting still doesn't work.
     Problem is that an index block is holding a reference on parent,
     and parent references aren't getting cleaned up.
     On read-only unmount I guess we need to walk the list of leafs,
     discard any address info, and unlock the blocks.
     So that should be the first task for next time.

27jul2006
  Leafs are locked blocks which have no locked children.
  So any locked data block (non-inode) is a leaf
  Any locked index block with lockcnt[phase] 0 is a leaf.

  OK - fixed numerous bugs, but I can unmount now!!
  I can even rmmod and insmod and all is cool.


TODO:
 - review refile and get all the code in there from prototype
       DONE (I hope)
 - write a combined find/load/wait function and use it
       DONE
 - allocate inodes in single memcache and avoid generic_ip
       HALF DONE. (still using kmalloc, not doing initonce well)
 - review recording of new block addresses
    + make sure we lookup there on index lookup - YES
    + make sure ->uninc_next gets tranferred to table at phase change.
    + write incorporation code as it is tricky
 - review how directory updates can be incorporated into a RO filesystem.
    No, they cannot.  We need to update the directory.
 - write directory update code
 - write cluster construction code
 - make sure indexblocks with unincorporated addresses get on to inc_pending
    ?? or is locking them enough?


INCORPORATION - ARgggghhhhh.
 The current uninc_table doesn't really lend itself to building
  index block... though maybe....
 Question: what happens when an index block disappears? i.e. it has no
  addresses in it?
  We clearly need to remove it from the parent.  This should be trivial,
  a direct operation on the parent index block. etc some number to 0.
  Then the next incorporation pass with simply lose that entry.

 OK, that might be all well and good, but how do we sort unincorporated
  addresses so we can merge them?
 A linked-list merge sort is nice and open-ended, but does waste
  quite a bit of space in pointers.

 Or maybe I should just always do small-table incorporations.
 Is there a way that a bad ordering of writes could force very bad
  index layout in this case? i.e. cause a table split every time,
  but new blocks go in the first (full) table.
 OK Decision: always do small-table incorporation.
  i.e. not a list of blocks: just a table of addresses.

 FIXME check validity of index type when it is first read in,
   and reject early if it cannot be recognised.

24aug2006
 Took a break from incorporation.
 Looking at directories.
 Wrote dir.doc in module to sum lots of stuff up.
 Issue:
   dir blocks have an info structure attached.
   This included a counted reference to the parent.
   How long does this need to hang around for??

   - when there is any orphan issue happening, it must stay, via
     the 'pinned' flag.
   - when actually performing a dir op, we need to create and
     maintain this info.

   When last ref of a dir block is dropped, should drop
   the parent reference.


 Status:
    free list management mostly done.
    Next:
      create/delete prepare/commit/abort
      orphan handling
      dirty_block lock_block


 FIXME should dir_new_block zero out the block?
   How will commit_create know what to do with this block?

 NOTE another type of directory orphan is a free leaf block which
   is on the part-free list.

-------------------------------------------------------------
09spe2006 0 on the plane to Frankfurt
 Don't tell me I am rethinking preallocation again ???

 TODO 
   dirty_inode needs to record the phase it is dirty in
   inode_fillblock needs to check current phase and act accordingly.
     we inode.doc
   Make sure the B_Orphan flag is set and used - or discard it.

   How do we commit creating a symlink?
   If it is a full block in size we cannot make an update record.
    - maybe have two update records? We cannot guarantee they are in
      the same  cluster.
    ... but if we put the 'make dir entry' last it should work.

   Change 'struct descriptor' definition
   the 'block_type' aka 'length' 16 field becomes
      0x0000 -> 0x8000 -> datablock, possibly a hole - upto 32K.
      0x8001 -> 0xc000 -> miniblock upto 16K+
      0xffff           -> index block.

   Need to write IO routines which decrease pending-block-count in
     'wc'.


   Thinks.  a 1TB filesystem with 1K blocks and 4096 blocks/seg
     gives 4Meg segments. That would be 256K segments which at 2 bytes per segment
     - 512 segments per block - is 512 blocks in each seg usage file

12oct2006
 Need to write
 - lafs_lock_{d,}block  DONE
       Make sure the block has parents and allocation and set the locked
       flag and the phase.

 - lafs_flush
       Given a datablock, wait for it to be written out
       This is needed before updating a block that is still locked in the
       previous phase.
 - lafs_inode_init
       Used when creating a new object/inode
       Given a datablock which is to hold the inode
         and a type (Type*) and a mode,
       Fill in the data block with appropriate data so that
          when lafs_import_inode looks at it, the right stuff happens.
 - phase_flip
 - lafs_prealloc
 - lafs_seg_ref
 - lafs_lock_inode

lafs_dirty_dblock
lafs_cleaner_pause
lafs_dirty_inode
lafs_seg_flush_all
lafs_write_all_super
lafs_quota_flush
lafs_space_use
lafs_cluster_update_abort
lafs_cluster_update_commit_buf
lafs_cluster_update_commit
lafs_seg_apply_all
lafs_cluster_update_prepare
lafs_inode_phase_check
lafs_seg_dup
lafs_dirty_block
lafs_cluster_update_lock
lafs_checkpoint_unlock_wait
lafs_orphan_drop
lafs_free_get
lafs_find_next

2nov2006
 - I need to know if a block is undergoing write-io so that I can
   avoid modifying it in certain circumstances.  But I don't track
   this information.  Options:
    1/ track the info.  This means an extra field in the 'struct block'
        because I still need to know which wc has had a write.
    2/ For blocks that we care about copy the data on write...
        But we care about all inodes and directory blocks.  That is a waste.
   I think we put extra info in the block.
   We need to know which wc was used (0,1,2) and which pending cluster
   in there (0-3) which comes to 4 bits.
   But we only care about the block for wc=0. and we could include the
   which-pending in the b_end_io, or maybe put it all in low bits
   of the block pointer....  Need max 4 bits.  Can only be sure of 2...

   Maybe:
       'which' goes in bottom two bits of bi_private
       'wc' goes in ->flags


4apr2007  (What a long gap !!)

 - lafs_cluster_update_*
   How do we prepare for a cluster update?  How do we lock it.

   The important thing is that the update can be written.  That
   requires that there is space available.  So we need to preallocate
   space and then release it.
   It is possible that each update might go in a different cluster, so maybe
   we need to preallocate one block per update.  That sounds a little expensive.
   After all, we aren't preallocating a cluster block for every data block
   that is dirty.
   So: prepare does nothing
        lock preallocates the space - a full block.
        commit copies it in.
    For now at least.

24May2007

 - Can now create and delete lots of files.  This is cool.
  But:
    Orphan slots just grow and grow - never to be reclaimed - why?
    After rm f*, 7 files remain.  but rm f* again and the go.
         FIXED - readdir wasn't returning them
    Size of directory remains large.
    And sometimes, files become ghosts... (try just removing one after first rm f*).

  TODO - process those orphans to clean up the directory.

20June2007 (Happy Birthday Dad)

 - Creating lots of file and then deleting them leaves 5 orphan slots
   for the directory busy, and one for inode 0?? 

   Directory handling uses the following orphans:
    CREATE:
        A new index block is created by splitting.  This needs to be linked in.
    DELETE:
        The dirent block we are deleting from
           If it becomes empty, it needs to go on free list
        The index block we are deleting from
           If it has lots of free space it might need to be rebalanced.
     The inode that was deleted.

 
 - When a file is fully deleted, we need to drop any orphan info... DONE
 - Need to do orphan handling of free blocks in directory, and
   unmerged parents - but there doesn't seem much point as I am going to
   change the directory layout (again).

 So: writing to a file.
   We need prepare_write, commit_write, and writepage.
   Prepare loads and links the page and checks there is space.
   commit marks it as dirty so writeout is possible.
   writepage chooses a page to write out

25June2007 - HACK week, thanks Novell!!
 - write - DONE
 - sync
     Somewhat done.
     Need to revise the process whereby async completion
     clears PAgeWriteback,
     We need locking in there, and need to worry about
       'which' wrapping too soon.
     Need to not start IO before we set page writeback
 - chmod
     Maybe, but syncing to disk needs more thought.
 - 'df'
    Partly done, need actual content.
 - mkdir
    Can make directory, but creating first entry fails. - FIXED
 - symlink
 - readlink
 - new directory structure.

27Jun2007 - More HACK week :-)

 - new directory layout done - much easier!!
 - If I delete a file that was created, the blocks still have a ref-count
   and we crash.
 - mkdir doesn't increase link count on parent. - FIXED
 
 TODO:
   Orphan handling.
     Infrastructure to process orphans
     Handle specific cases
     flush orphans at key times.
     load orphans at roll-forward

   checkpoint
     Write out a checkpoint (when?)
     Make sure refcount goes back to zero on blocks I write.

  Check on inode_phase_check and checkpoint_unlock and inode_dirty
   in all directory operations.

 FIX: Writing a small file leaves something non-dirty but
    due to be written, and lafs_cluster_allocate complains.
  - seems to work now.

 FIX: dir_handle_orphan doesn't lock the orphan transaction required.

 FIX: rm a file with (small) content hang waiting in sync_page in truncate_inode_pages.

 FIX: lafs_allocate hasn't been written!!!

 FIX: before updating any block in a depth=0 file, we must first load
      and 'lock' block 0.

29Jun2007 - still HACK week.
  Summary of how incorporation works.

  Each index block has a small table for unicorporated changes. i.e. 
  blocks number and their addresses.
  This supports efficient storage of extents, and is extensible by allocating
  more tables.  This last is done rarely.

  When a block gets a new address, this is added to the table or, if
  there is a phase missmatch, it is added to a list until a phase change
  happens (so the whole block is pinned pending the phase change).

  If the table is full then:
   - if the filesystem is read-only (including during roll-forward),
     a new table is allocated (else rollforward fails).
   - otherwise we incorporate the table into the block, then add the new
     address to the (now empty) table.

  If incorporation requires that we split the index block we allocate one
   from a pool.  If there are none in the pool, we wait.

  As the table is much smaller than a block, the incorporation into
  two block will always succeed.
  The 'uninc_next' and 'children' lists will then need to be shared
  between the two blocks before the new address is added to whichever
  table is appropriate.

  When looking for a block address, we must always check the table and
  then children lists.  We do not need to check uninc_next as they will always
  be children.

  How to ensure that the pool always has sufficient index blocks and we don't
  deadlock?
  We have two halves of the table, one for each phase.  Before we allow
  a block to be dirty in a phase, we ensure that the pool has adequate 
  index blocks for that phase.  e.g. twice the depth of the block.  If it
  doesn't we block the dirtying until space becomes available.
  For syscall writes, this is easy as we catch in prepare_write.
  When we perform a phase change, we must be sure there are enough index
  blocks for the deepest bloc that will stay dirty.  If there aren't, we need
  to flush all dirty block, and unmap all writable mappings before
  starting the checkpoint.


 FIX: need to work out life time rules so that inodes hang around while they have blocks.
    currently have an igrab that is never put.

 FIX: Dirty isn't cleared until 'flush', but do_checkpoints requires 'alloc' to clear it.

3Jul2007
 Checkpoint flushing is getting close.
 Current problem.
   InoIdx blocks are not changing phase.
   Phase change should happen when all children have been incorporated, and
    then the write has been triggered marking us clean.
  For InoIdx blocks, we need to be marked clean when the data block
   completes.

5jul2007 - a week off
 Checkpoint flushing seems to work !!!!
 FIX: what should filesize of symlink be?  
     other filesystems use len, but still zero-terminate for vfs.

 Problem.  A chmod is followed immediately by an unlink then a checkpoint.
   The chmod update gets into the checkpoint cluster, but the unlink completes
   before the checkpoint is finished so the new superblock sees the file
   as gone.  Roll-forward find the update and want to update a missing file.

   This isn't a big problem, but with slightly different details, it could be.

   One option is to ignore updates that preceed the updated block.  That might
   be awkward with e.g. directory updates and checkpoints that cross multiple
   segments.

   Another option might be to prohibit updates once a checkpoint has started
   unless they are known to be after the phase change.

 FIX: unlink isn't punching a hole in the inode file.
      Inode usage map isn't being updated. - FIXED (For create, not unlink).

 FIX: roll forward does not pick up inodes, only data blocks.
    But tiny files are synced to inode, so they might not be picked up.
    So we must process a level=0 inode like a data block.

6July2007
 Time for lots of clean up.

DONE 1/ Index blocks to fill with 0 - use phys=0 to imply invalid.
DONE 2/ rename 'lock' -> 'pin'
 3/ Review and fix up all locking/refcounts.  See locking.doc
DONE 3a/ Make sure cluster_allocate can be call concurrently. e.g. check
         B_Alloc inside the semaphore
       Also lock inode when copying in block 0 and probably
       when calling lafs_inode_fillblock (??)
DONE 3b/ lafs_incorporate must take a copy of the table under a lock so
         more allocations can come in at any time.
NotYet 3c/ cluster_flush should start all writes before calling _allocate
         as _allocate might block on incorporation/splitting.
       No.  We really want _allocate to not block, but to queue...
        I think this is too hard to get perfect just now, so I will leave it.
DONE  3d/ introduce PinPending for data blocks.  remove fs->phase_depth.
LATER 3e/ Index needs a clean-lru on each filesystem, and a list of filesystems
     so that locking of lru doesn't have to be too global
DONE 3f/ change wc[]->hlhead to be a regular listhead as it is part of the
       lru system.
DONE 3g/ revise refile lru handling based on new understanding
 3h/ Utilise WritePhase bit, to be cleared when write completes.
     In particular, find when to wait for Alloc to be cleared if
      WritePhase doesn't match Phase.
       - when about to perform an incorporation.
 3i/ make sure we don't re-cluster_allocate until old-phase address has
     be recorded for incorporation.
 3j/ Check that index blocks cannot race when getting locked....
  k/ Check what locking is needed to set PagePrivate exclusively.
DONE  l/ cluster_done needs to call refile, but is called in interrupt context.
     We need to get it done in process context I think and lock
      ->waiting access with fs->lock after changing it to ->lru
DONE  m/ Need to know which blocks in a page are in writeback so we can clear writeback
        only when *all* have finished.
DONE  n/ on phase change, uninc_next blocks need to be shared out.
NO 3o/ Make sure lafs_refile can be called from irq context.
 3p/   lock all lru accesses.
 3q/ Lock those index blocks!!!
 3r/ Can inode data block be on leafs while index isn't, what happens if we
       try to write it out...
 FIXED Why are extent entries only grouped in 4s? 
 If InoIdx doesn't exist, then write_inode must write the data block.
 4/ resolve length of symlink
   FIXED - long symlink followed by 'sync' crashes.
   FIXED - rollforward isn't calling 'allocated' on blocks, or something
   FIXED - I cannot find 'bfile'. (inode isn't written)
   SEEMS OK...- Must flush final segment of a cluster properly...
 5/ Review what does, and does not need to be initialised in a new datablock
 6/ document and review all guards against dirtying a block from a previous phase
    that is not yet safe on storage.
          See lafs_dirty_dblock.
 7/ check for proper handling of error conditions
     a/ checkpoint_start might fail to start a thread!
     b/ if lafs_seg_dup fails in do_checkpoint, we need to abort the snapshot.
 8/ review checkpoint loop.
       Should anything be explicit, or will refile do whatever is needed?
 9/ Waiting.
       What should checkpoint_unlock_wait wait for?
       When do we need to wait for blocks the change state. And how?
DONE 10/ rebase on 2.6.current
DONE     - use s_blocksize / s_blocksize_bits rather than fs->

 11/ load/dirty block0 before dirtying any other block in depth=0 file
 12/ Add writecluster flag for old-phase updates.
     Why is this needed?  updates should always go in the new phase???
 13/ use kmem_cache for 'struct datablock'
 14/ indexblock allocation.
        use kmem_cache
        allocate the 'data' buffer late for InoIdx block.
        trigger flushing when space is tight
        Understand exactly when make_iblock should be called, and make it so.
 15/ use a mempool for skippoints in cluster.c
 16/ Review seg addressing code in cluster.c and make sure comments are good.
DONE 17/ Make sure create inherits uid etc from process.
 18/ consider ranges of holes in pending_addr.

DONE 20/ Implement rest of "incorporate"
DONE 21/ Implement staged truncate
DONE         use for setattr and delete_inode
DONE 22/ block usage counts.
 23/ review segment usage /youth handling and make a todo list.
      a/ Understand ref counting on segments and get it right.
 24/ Choose when to use VerifyNull and when to use VerifyNext2.
 25/ Store accesstime in separate (non-logged) file.
 26/ quotas.
        make sure files are released on unmount.

 30/ cleaner.
       Support 'peer' lists and peer_find. etc
 31/ subordinate filesystems:
     a/ ss[]->rootdir needs to be an array or list.
     b/ lafs_iget_fs need to understand these.
 32/ review snapshots.
      How to create
      how they can fail / how to abort
      How to destroy
 33/ review unmount
      - need to clean up checkpoint thread cleanly - be sure it has fully exited.
 34/ review roll-forward
      - make sure files with nlink=0 are handled well.
      - sanity check various values before trusting clusters.

 34/ Configure index block hash_table at run time base on memory size??
 35/ striped layout.
         Review everything that needs to handle laying out at cluster
         aligned for striping.

 36/ consider how to handle IO errors in detail, and implement it.
 37/ consider how to handle data corruption in indexing and directories and
     other metadata and guard against problems (lot of -EIO I suspect).

 - check all uninc_table accesses are locked if needed.

And more:
  1/ fs->pending_orphans and inode->orphans are largely unused!
  2/ If a datablock is memory mapped writeable, then when we write it out,
     we need to with fill up it's credits again, or unmap it.
  3/ Need to handly orphans asynchonously.

---------
22nov2007
Free index block are on two lists, both protected by the global
hash_lock.
  1/ The per-inode free_index, so they can be destroyed with the inode
  2/ The global freelist so they can be freed by memory pressure.

11feb2008.   Where was I up to again?
   reviewing phase_flip and lafs_refile.

  UPTO
     Reading through modify.c, at 'add_indirect'.  Plan to fix all this code.
     Need to thnik about how index block really change.  How old blocks get 
      dis-counted from segment usage, and what optimisation are really good
      for re-incorporating index blocks.
        Operations to consider are:
              i)Append new block, ii)truncate, iii)over-write, iv)fill-hole.
          i/ leaf block splits, index block gets new entry at end, and replacement
                  for other entry.  Easy to handle
         ii/ trailing entries are zeroed.  Should be easy, but isn't yet.
        iii/ probably caught in leafs.  May cause internal split so we add new
             index address, which is easily handled if there is space.
         iv/ same as iii, though split more likely.

       What about merging index blocks.  That just makes addresses disappear, which
        we handle the slow way.
       Do we ever re-target index blocks?  Would need to be careful about that.
       Make it look like a split where one block ends up empty as a hole.
     Need to write
           grow_index_tree (DONE - untested)
                  ib is a leaf inode that is getting full.  Copy addresses
                  into 'new', and make 'ib' an index block pointing at new.

           add_index/walk index (DONE - untested)
          
           end of do_incorporate (DONE - untested)
                new contains the early addresses.  Some remain in ib
                 and/or ui.
                the buffers much be swapped, so ib has the early address.
                ui needs to be attached to new
                return 2; - then new uninc needs to be split

           lafs_incorporate
                case 2 - horizontal split
                case 3 - vertical split
  12feb2008
   Bother - uninc_table is a problem (again).
   We can currently add at any time with just a spinlock.
   So when we split a block horizontally, 


   Still need to
          share out children and uninc_table in do_incorporate
          share out credits in do_incorporate

14feb2008
   Still need to do incorporate as above but took a break to...

   Counting allocated blocks now works - stat show right info, hopefully
     storage is correct too. - DONE

   next: truncate?  orphan thread? 
      Then segment usage and the cleaner.


   thoughts:
    truncate - removing blocks doesn't need to erase them...
    - nothing forces a cluster_flush promptly!!!  We need a timeout
         or at least we need a flush before truncate_inode_pages...

    - in lafs_truncate we need to make the block an orphan an pin in 
      all in a checkpoint.

21Feb2008 (Research morning)
   Discard checkpoint thread created on demand in favour of a cleaner
   thread that runs all the time.  It cleans and checkpoints and
   orphans and scans.

     want to:
        do segment scan and get a real list of free segments and
        free-space info!

25Feb2008
 - segment usage scanning to count free blocks
 - fix up re-reading of erased blocks
 - FIX truncate can still block waiting for writeback to complete.
 - FIX allocations aren't failing when we run out of free space
 - FIX df doesn't agree with du.

 problem:
   Truncate when an index block has addresses in uninc_table.
     The summary for the new address has already been performed.
     We need to deallocate the new without disturbing the old.
     However a simple allocation may not be possible.
     I guess we can prune them all to zero, then incorporation
      can proceed.

 TOFIX: when truncating a recently created file, it is still depth=0 so
    nothing happens.
    We really need to increase the depth to 1 as soon as we dirty
    any block, then reset back to 0 if it fits.

26Feb2008
  We have a file that we have written to, and the data blocks have been
  written out and the addresses stuck in uninc_table.
  We then truncate the file.  Who releases the usage of those blocks?
  And who removes them from uninc_table?

  OK, 'rm' returns all the blocks back now so 'df' is almost the same as 'du'.
  I really should make sure that inodes are getting freed properly and the
  inode map is clean and everything.

  BIG QUESTION
    Do we reserve segment-usage blocks.
     We cannot do it naively as we get infinite recursion.
     But we need it to be allowed to dirty the segment block.
     But we cannot pin them to this phase as we want to write them out
     after this phase
     This still needs more thought.  I avoided the recursion by setting SegRef
     before getting the ref.  But that isn't safe.

28Feb2008
  The table of cleanable segments is not working out.  Each segment appears multiple
  times which wastes space and adds confusion.
  We really want to be able to lookup by dev/seg and also find the least.
  'Find least' sounds like we want a heap but then we cannot discard the bottom half.

  We could have a skiplist for dev/segment lookup and do a merge-sort on
  a different link when we want to find the best segment.
  We then remember the best number found since a sort, and re-sort if the top
  is worse than the best.

  We keep all this in a fixed size table.  Each entry has
   seg,dev,usage,weight,weight-sort-link,addr-sort-link and possibly some
      addr-sort-skip links.
   This is 32+32+16+16+16+16 bits, or 16 bytes or bigger.
   Say 16bytes, 24bytes, or 32 bytes. (depth 8, which is plenty).
   One page of 16byte entries (256 of them)
   2/3 page of 24byte entries, 1/3 of 32byte entries.
   Total 2 pages, and 256+113+43 = 412 entries.

  But deleting random elements is awkward... but not too awkward.  We can delete
  lots of entries by marking them as old, then performing a single pass of the skip
  list deleting them.

  We should keep free segments here too, on a separate list.

  So how about:
   2 pages of 16byte entries
   1 page of 24
   1 page of 32

  free list randomly threads through all.

  When using from 24 or 32, randomly choose height of 2-5 or 2-9
  Two lists run through the skiplist entries.  One for cleanable, one for free.
  Remember the nth element for some small n (10, but it decreases as we pull
  things off the front) and if we add something less than that, we trigger a
  mergesort on the next time we want to clean.... maybe.

  Remember end of free list and add to there.  Maybe merge-sort the free list
  by addr occasionally.

  Quesitions:
    When can we clean, when can we free wrt checkpoints?
      - we an clean a segment as soon as we have a checkpoint after it.
        So we record the youth of the segment holding the (start of the)
        checkpoint, and can clean any segment with a lower youth.
      - we can free a segment after the checkpoint after itfs usage has reached
        zero.  So if usage is zero and youth....
        We could offset the usage by one (say - for the first cluster header..)
        then when we find a segment with usage of '1', we schedule an update to
        0 in the next checkpoint...
    Have about segments with different sizes - they get different weights.
       Need to divide by segment size:  usage * youth / size.

  TOFIX
   - It seems I sometimes fall off the end of the last segment !!! - FIXED (locking)
   - We seem to switch to a new segment when still 83 blocks remaining? - FIXED (delete did flush)

   - Lots of 'creates' makes lots of little clusters - need to optimise!
        Or it could be deletes as we currently cluster_flush for each
        delete.
         - I think this is fixed

29Feb2008
  Started looking at the cleaner.
  Need to understand how much to clean each checkpoint
  Need to track free-space-in-active-sectors while scanning.

3Mar2008
  TOFIX
    - the cluster head is currently limited to one page.  This is not good.

    - Should the cleaner start before the scan is complete after a checkpoint?
      Probably it can, but while the scan is still happening it might be best
      to be cautious ??

  STATE:
    try_clean is taking shape and has a few FIXMEs.
    need to write async find_block code and get it to watch for
       block in a cleaning segment.

28Mar2008
  - where can padding appear in a cluster? between miniblocks? at
    end of device blocks?
  - need to track phys block while parsing headers for cleaning.. why?
  - determine rules for avoiding block lookup during cleaning
    based on youth/snapshot age, and truncate generation.
     We need to load the inode from each snapshot
    Can we optimise based on snapshot age?
    only if we know the block is newer than the snapshot.
    So when we relocate blocks (cleaning) they must go in a segment
    that is marked as being old. we cannot really guarentee that.
    I guess blocks that are marked as 'new' can safely be skipped if
     segment is newer than snapshot. This 'age' is not the youth, but
    is the cluster_head->seq which is stored in creation_age.

 - Store the rootdir for a filesystem in the metadata for the root inode.
   Then 'struct snapshot' doesn't need rootdir.  It can have a root

30Jun2008
  Looking at lafs_find_block_async.
     Needs async flag to make_iblock. 
        Check that.  Can we block_adopt if there was an error?
             iblock will exist.
     setparent has async flag.
     lafs_leaf_find has async flag
     lafs_wait_block_async

  FIXME I wakeup the cleaner every time an IO completes. 
  Do I really want that?  Maybe only when number of async IOs hits
  half the recent maximum??

  FIXME need to ensure that lafs_pin_dblock flushed committed
    B_Realloc blocks.

  FIXME when we incorporate a dirty (non-realloc) address to an index block,
    we need to clear B_Realloc on the indexblock.

  FIXME in lafs_incorporate we lafs_dirty_iblock 'new' without 
    giving it any credits.  Where should they come from?

  We don't seem to scan for free/cleanable segments often enough.

  FIXME we shouldn't start a checkpoint while cleaning is happening.

  FIXME need to be careful when cleaning about finding inodes that
    don't exist any more.

  FIXME give credits to realloc blocks.

  FIXME think about/document transitions between realloc and dirty,
    and what locking is needed.

2Jul2008
  Allowing for the FIXMEs above, the cleaner is now identifying
  blocks that need to be cleaned and marking them B_Realloc (I think).
  We now need to gather these into a write cluster and write them.
  They will all be on the clean_leafs list, so we can iterate that
   allocating or incorporating as needed.  This will be similar to
   do_checkpoint.
  Important question is: when?
   Ideally we would have some auto-flush mechanism.  The cleaner just
   keeps finding blocks to clean and when we start running out of
   resources we flush the cleaning queue.
   However we will still want to flush the cleaner always before a 
   checkpoint, so for now we cna implement that bit and wait for a
   need for the other to arise.


  FIXME: cleaner lookup of 0/0/0 has interesting consequences as we
      don't record that location the same way.. how to handle?
     Should check that 'adopt' doesn't do the wrong thing with this block.


  Realloc blocks need to be pinned.  That makes sense.  Only that way
    will they get onto the clean_leafs list.
  When checkpointing we should probably examine clean_leafs to be
   on the safe side.
  

  Realloc and Dirty:

     Both of these hold a Credit.
     Both can be set at the same time.
     Cleaner ignores Dirty and sets Realloc anytime the block is in
      the wrong segment.  It also Pins the block.
     When the cleaner is flushing to the cleaning segment, it
      ignores Dirty blocks.  They get their Realloc cleared, but
      the remain pinned.  So they will get moved at the next checkpoint.
     How do we know whether an indexblock should be Dirty or Realloc?
      The Dirty/Realloc bit is cleared before we get to incorporation.
      Maybe we lafs_dirty_iblock the parent of any block we write
       out.  Then after incorporation, we set Realloc if it is not
       dirty.

STATUS:
  I think I'm pinning cleaner blocks now.
  Need to make sure the dirty ones are dropped. DONE
  Need to make sure the usage is transferred
  Need to get free segments back into use
  Need some more 'dump' options.  Maybe youth/usage files.
      Maybe tree.
  Need to make sure scan etc are triggered often enough.

  FIXME lafs_prealloc walks up ->parent without locking
    I think we want i_mapping->private_lock like lafs_pin_iblock.

TODO:
  1/ a 'dump' option that triggers a scan and prints everything out.
  2/ scan must mark freeable as such, then subsequently free them.
  3/ Look at code that decreases usage of old segments.
  4/ Review lafs_cluster_wait_all and decide exactly how long we need
     to wait.
  5/ Review 'FIXME that is gross' HZ/10 thing.
  6/ Review 'wait for checkpoint to flush' msleep(500);
           Maybe remove that altogether.

  FIXME BUG_ON in grow_index_tree fires. sync - writepages - flush
  FIXME BUG in lafs_allocated_block fired.
            from lafs_erase_dblock from invalidate_page from .. vmtruncate
             from lafs_setattr

  Current problem:
    An inode data block is dirty and pinned, but the inoidx is no longer
       pinned.  Presumably it isn't dirty.
     Recheck what 'dirty' means on the two blocks and see how this can happen.

10july2008
  Tree gets very big!  Lots of 'Realloc' blocks that should
   be long gone.

  WE are spinning in cleaner again, and not in try_clean.

  Is it a problem that 'Pinned' is used for Realloc and dirty blocks?
  In general it shouldn't be.  The flush_cleaner process will remove
   the Realloc bits so the blocks fall off clean_leafs.  They then either
   go onto phase_leafs or get unpinned.
  But I currently have a problem with InoIdx/data.
  The Pin is transferred to the Data block, but it doesn't go from the
   InoIdx block because it has a pincnt.  Now that is probably a bug, but
   what if it weren't?  What if, while we were cleaning, a block got dirtied.
   That would pin the whole tree. 
  I guess the rule about not allocating an inodedata block while the
   InoIdx is pinned needs to be revised.  If the inodedata block is 
   Realloc (and not Dirty) while the InoIdx is not Realloc, we
   can go ahead (in a cleaning segment).

 FIXME to check:
   adir/big1 is garbage.... big1 was removed, so why is it even there?
              FIXED.
   echo tre > dump  # still too much stuff.



 Put cond_sched in checkpoint loops!


 Thoughts about cleaning and pinning.

  When cleaning we need to know how many dependant blocks are being cleaned
  so that we know when *this* block can be written - i.e. when the could hits 0.
  We cannot use the pincnt for this phase because there may be dependant blocks
  which are dirty.  They, and therefore this, may get flushed at next checkpoint,
  but they may not.  If we could be certain they would, we could just write
  to the clean-segment blocks which can become unpinned.  However if there
  is an index block being cleaned, and no dependant is being cleaned, but some
  are dirty but not pinned, then the checkpoint can go past without the block
  being moved.... but maybe we can detect that.

  Try this:
    We set B_Realloc precisely on blocks found in segments being cleaned.
    We pin these blocks and leafs which are Realloc go in clean_leafs.
    If a block is both Realloc and Dirty we clear Realloc but leave pinned.
       That way it gets written at end of checkpoint, but to main cluster.
    When we incorporate Realloc blocks into an index block, it gets marked
       Realloc.  When we incorp dirty blocks, mark dirty.  Then see above.
    On a checkpoint, we process both phase_leafs and clean_leafs


 FIXME do inode reads async better when cleaning...

 FIXME if a realloc inode has been allocated to a cluster when we try
     to dirty it, confusion can ensue as the writeout won't mark it
     clean, but will use up the credits.
     Maybe we need something similar to phasewait to not set PinPending...
      But normal dirtying doesn't phasewait.   I think we just need to
      detect this case and wait for the clean-cluster to flush.
      Messy...

 FIXME make sure incorporate is doing the right thing with credits.

 FIXME lafs_write_inode. We need to be careful about clearing Dirty
           when making an update.  Need some sort of locking.
           Need to review all inode dirty stuff and make sure we do
           write thing no matter when it is called.

 FIXME when blocks are attached to uninc_next, they don't have 'dirty'
        anymore so we don't know how to flag the index block.

2008jul13
 UPTO: unlink etc don't prealloc the inode that will be modified.
    And a warnon inode.c:579 is very noisy.

2008jul22
 FIXME: lafs_reserve_block uses CleanSpace if Realloc is set,
     but it doesn't get set until AFTER lafs_reserve_block is called.

 Here I am...
   Cleaning cleans an InoIdx block which schedules the data block.
    Subsequent the InoIdx block gets pinned again.
    Now when we go to write the data block, we cannot because InoIdx is pinned
     in same phase.
     Maybe given that data block is pinned, we write it anyway...

 FIXME: when we realloc an block embedded in the inode, don't pluck it out
        and put it back in again.  Just realloc the inode.

 FIXME: when cleaning a directory that has shrunk, we think we have
     blocks that don't exist any more. FIXED - we thought '0' was in 
     segment '0'.

2008jul23
  FIXME: lafs_dirty_iblock called from lafs_allocated_block in cluster
     flush finds no credit. for InoIdx block of 8501

  FIXME: do we do SEGREF on all the index blocks? do we need to?


2008jul24
  FIXME: seg usage for segment 0/5 isn't dropping to zero.
    Part of a file got moved off, but count is still there.
    FIXED - seg_move wasn't being called.
  FIXME: segusage file has inconsistent extents:
      Extent entries:
       0 -> 694 for 2
       1 -> 1291 for 1
       1 -> 15 for 1
   FIXED several bugs in walk_extent

  FIXME qphase:  any locking between that changing and lafs_seg_move??
    I don't think so.  Just that seg_apply_all must be called after qphase is set.

  FIXME make sure we don't try to clean the current segment!!

  FIXME 'Available' goes negative!
      Creating large file doesn't instantly reduce 'Used'.
      Deleting files plus sync doesn't increase Avail?
 
  FIXME a segment is in the table but doesn't print out!

  FIXME we don't cope with running out of free segments (not that we ever should).

  FIXME check all Credit usage and make sure credits are returned when
    ->parent is dropped.
    provide visibilty into credit counts.
    Make sure we are keeping enough space for cleaning.  We should always
     have a few segments unallocatable.

2008jul25
  FIXME cannot do io completion in cleaner thread as it can block on
     a i_mutex which might be waiting for completion. FIXED (keventd).

  FIXME as ->iblock isn't refcounted we need to be careful accessing it.
            If we 'know' we have a reference, e.g. a child with a ->parent
            link, we can access it without locking.
       So:
           lafs_make_iblock should return a counted reference.

       If we own an (indirect?) reference to iblock, we can access
        both iblock and dblock for free... but iblock can change???
       If not, we need to get a reference to on or other under a lock.

  FIXME block->inode should be a counted reference?

lafs_make_iblock OK
  lafs_leaf_find OK
    lafs_inode_handle_orphan OK
      inode_handle_orphan_loop FIXED
    __lafs_find_next OK
    find_block FIXED
  __lafs_find_next OK
    lafs_find_next FIXED
      dir_lookup_blk
      dir_handle_orphan
      lafs_readdir
      lafs_inode_handle_orphan
      choose_free_inum
  find_block - FIXED

 FIXME root->iblock should always be refcounted.  Is it?
 FIXME walking siblings - what lock?

2008jul28
 FIXME several times we clean PinPending without refiling, in dir.c in particular.
    that looks wrong. FIXED

  Maybe  lafs_new_inode should return a reference to the dblock
    Or pin it. or something. FIXED  And pinned (when needed).

 FIXME lafs_inode_dblock might return a block without valid data...
   Need to get valid data, then load block 0 in find_block rather than
       load_block.  FIXED

 FIXME we really should own a reference to ->dblock before calling
    lafs_pin_inode.  We don't want IO during a pin request.
    FIXED

 FIXME review use of PhysValid FIXED

 lafs_orphan_abort - what if lafs_orphan_pin not called?
   or if 'b' is NULL.  FIXED

 Do I Need to clean PinPending when retrying??
   Well, we need to be phase-locked when we set PinPending, so
    it must be Pinned to the current phase.
    So when we unpin a datablock, we must clear PinPending.
  FIXED we now clear PinPending in do_checkpoint.

 Does phase_wait do the right thing when pinning an inoidx block
   for an inode? FIXED


Pending
  Need to understand and document the lifetime of a page with datablocks.
    who hold what refcount, and when can it be freed?
   Then fix up locking in lafs_refile, __putref.

 FIXME how keep what refcount on orphan blocks/inodes??
 FIXME should dirty/pinned/etc hold a refcount?  they don't.


Later:
 FIXME make use a failed (-EAGAIN) pinning triggers a checkpoint (eventually)

 FIXME make sure empty files have depth of 1.

 FIXME Truncate proceeds lazily. All data blocks need to be gone

26aug2008
 If I call lafs_erase_dblock while a write is underway, we have a problem.
  We need to wait potentially for a checkpoint to let go of the block and
   a write to complete.
    This should be done with waiting for PG_writeback on the page to disappear.
  Check this out.

  When end_page_writeback is called, we must have dropped all references to the
   page.
  When we commit to writing a block, we have to set PG_writeback on the page
   so that truncate et al can wait for it.  Before we have committed, truncate
   can just remove the page.  Internally we differentiate by B_Alloc.
  So before setting B_Allocated we need to test_set_page_writeback(page).
  Be careful of races.
  I don't think we can ensure all references are dropped.  After all, that is
  the point of refcounts.  So dblock array must exist without page!
  But we need to ensure that we don't start a writeout after truncate
  has done wait_on_page_writeback.
  This is done with the page locked so when we want to write a page
    in a checkpoint, we need to lock the page first.  Once we have the lock,
    we check if the page is still dirty.  If it has been truncated it 
    will be clean.
   But how do we safely reference the page if b->page can be cleared?
    How about:
      When we clear PagePrivate, we take a counted reference to the page
      for db->page.  This is dropped when the page is freed by lafs_refile.
      But while it is held, it is still safe for db->page to be dereferenced.
    So before we commence writeout we have to lock the page and set
     PG_writeback.  After locking, we need to test if writeback is still 
     appropriate. 

  Maybe not.  I think we can submit blocks for writeout without setting the
  page to writeback.  If we do, then we need to be sure those writes
  finish before invalidatepage calls releasepage (block_invalidatepage
  calls discard_buffer which calls lock_buffer which waits).
  In our case invalidatepage need to make sure that no new write commenses.
  Maybe we should lafs_iolock_block before we allocate to a cluster and check
  again if the block is dirty.

  So:
    lafs_cluster_allocate does:
       lafs_iolock_block
       check if still dirty.  If not, unlock and return
       set allocate flag
       allocate and write
       when write completes, allocate is cleared.
                    unlock block

    invalidatepage does
       lafs_iolock_block
       clear Valid,Dirty,Realloc
       lafs_iounlock_block



2008 aug 28 - happy birthday.
FIXME segsum_find calls lafs_reserve_block without a checkpoint lock.
lafs_prealloc complains.

  mark_cleaning does too, but cleaning only happens well away from a checkpoint
  lock.
segsum_find is being called to reference a new segment when we flush a cluster.
 segment usage blocks are special.  Their index information doesn't
need to be written out in the current checkpoint.  We can do that, but
the backstop is to write just the data block in the tail of the
checkpoint and write indexing information later.

2008sep10
 unlink is getting "No space left on device".  This is when trying to
 pin the directoory block, the physaddr is 0, so it looks like we want
 NewSpace.  But we should even be trying to prealloc in that case becase
 there should already be a prealloc on the block.  i.e. there should be
 credits.
 Hmmm. after multiple 'syncs' how can the block not be written out.
 Maybe it is embedded in the inode?
 When we pin a block that was embedded in the inode it isn't clear what to
 do.  If we might grow the file so it doesn't fit any more, we need to
 allocate NewSpace.  If we know it won't grow. we use Release.
  This still needs a proper fix.

 Cleaning seems to be working nicely.  However we don't get all the space
 back that we should because lots of blocks still have credits that
 aren't being returned.

 So when should credits be returned?
 They are set when a block is pinned.  It then gets dirtied which
 consumes a credit.  Then gets unpinned.  I guess if it isn't pinned,
 then it doesn't need any credits.


 It seems that cluster_flush is not always writing things in the correct
  order.  Root gets written before some other things below it.
   Maybe they are temporarily out of the loop??
 No.  There are dirty blocks which one checkpoint doesn't pick up, but
  they aren't holding the index block pinned. so they lose allocation.

 But they must hold the indexblock pinned, even though they aren't pinned
 themselves.  We maybe do this just with the refcnt... maybe.  That will cause
 it to phase-flip rather than drop pinning, which I think is right.

 So: too many credits remain allocated.  Where are they?  There are 1464
   outstanding credits. 290 are in the tree so 1200 or so are elsewhere??
   But things removed from the tree have credits removed.



FIXME roll forward ignores inodes.  But what about an inode that contains
   data.  Should that be ignored?  I think not.
FIXME delete adir/big2 then delete adir and it cannot release:
  Cannot release [cee29000]74/0(0)r1:Pinned,Phase0,Valid,Dirty,SegRef,UninCredit,PhysValid,Prealloc
 presumably there is orphan processing or something to complete???
FIXME when files are deleted, the space isn't returned!
   This seems to be mostly fixed - need to test.
FIXME when I "rm [b-z]*" it waits for writeback on something???
   zfile again!!!  OK, I think that is fixed.


12sep2008
  Current problem:
    seg_apply_all dirties dblocks.  When should they be reserved?
    The originally get reserved by a lafs_reserve_block call in
    segsum_find called from e.g. lafs_seg_ref which is called by lafs_reserve_block.
    However: that block might get written before *and* after a checkpoint.
    So we need N* Credits.  These are usually only used for Index blocks.
    We can set these easily enough if inode type is TypeSegmentMap.
    We move them across to Credit in seg_apply_all.
    But when to we clear them if they aren't needed?  I guess
     when we drop the last segref.  Yes, we already do that.
    FIXME need to make sure these get flushed on next checkpoint
     if we cannot allocate new credits after a checkpoint.

  New Problem.  The 'cleanable' table reports a size of 3, but it is empty!
    Think that is fixed.

  Some problems.
    1/ see above:  rm x/y; rmdir x -> BUG - FIXED
    2/ Spins on 'CURRENT=1' ??
    3/ if alloc_space gives EAGAIN while deleting, we don't survive.
    4/ When I create/delete a file, ablocks_used increments by one.
        The inode hasn't been allocated yet, so it seems the deallocation
         isn't adjusting ablocks_used??
    5/ open_namei (for dd) got caught on a mutex_lock.
    6/ When a large file is shrunk we don't reduct the level of the InoIdx block
       I'm not sure where we should and am not thinking very clearly.
       Will fudge something in flush_data_to_inode for now, but it MUST be fixed.
    7/ unlink (at least) can get stuck in iolock_block.  Who could be holding
       the lock?  Writeout that hasn't completed?
       Yes.  writepage calls lafs_allocated_block without calling flush.
       So the block could be sitting waiting for a flush.  How long do we
       wait??
    8/ It seems that some datablock can need NCredits.  Make sure these
       are handled properly re flush-or-refill after checkpoint and
       flip_phase rather than unpin.
    9/ Maybe after lafs_writepage cluster_flush isn't getting called soon
       enough, and we lock up (see 7).  Need to flush the first block
       straight away, and the next one as soon as the first finishes, etc.
       Or something like that.  Then remove the comment from lafs_writepage.

8th December 2008

  I seem to be getting only 4 blocks to a cluster at the moment.
   This is good as it motivates the code to handle block splitting in
   the Btree.   But it shouldn't happen.

  ....
  Block spliting might work - it doesn't crash at least.
  But
  After deleting all files, the tree is full of stuff.
  Lots of inode data/InoIdx blocks.
  Many but not all a Pinned.  The others are OnFree
  The Pinned ones have outstanding references.
  Others

  ....
  Problem with the block splitting, when adding an index block.
  The index block is initially empty - we need to find things by looking
  at children.  But we don't.  We BUG_ON the iphys==0.
  In general, when we add a block below and index block and before we incorporate,
  the block must be found by finding the first indexed block and looking to
  see if there is a 'next' block that contains the address we need.
  FIXED

  But if we truncate a file while an index block is pinned and dirty,
  we spin on trying to incorporate it, which should make it empty.

11th December 2008
  deadlock.
  sync is trying to get lock in lafs_cluster_flush
  pdflush holds the lock and is stuck in cluster_flush_0xa40
    some wait_event I expect.
    Maybe we need an unplug ??

 - checkpoint/seg_apply_all/dirty_dblock doesn't have the credits.
   This is in clean_free.  We try to update the 'youth' to mark
   the segment as free, and we don't have a reservation to do it.
   Maybe just reserve it there and then.


12th December 2008
  When doing a lookup in an index block, we need to check the unincorp
  address list.  It isn't enough to look for unincorp blocks as they
  might have disappeared.
  For INDIRECT and EXTENT this is easy enough as full information is in
  'uninc'.
  For INDEX it is a little tricky as we need to look at the full set of
   addresses to know where a particular address fits.
   We could force and incorporate first, but that has awkward implications
    if it requires a split.
   Maybe if we get from the lookup "start+range"....
     That is not enough as the 'start' might get zeroed by an update.


   rm adir/* doen't work as readdir doesn't get all the entries
    for some reason.
   Reason is that they are being put in the wrong block.
   lafs_find_next doesn't correctly find the 'next' block if it 
   hasn't been incorporated yet.
   Block can be:
     in index tree -- easy to find
     in uninc_table -- not too hard
     in only in the ->children list, or attached to a page.
   It would be nice to use find_get_pages but that isn't exported so try
    something else for now.
   For index blocks
        Look in index block for 'next

15th December 2008
   FIXME when we split an index block, we need to hold a reference to
   the original so it doesn't disappear until the split-off copy is
   written.  This is because we search from an index block to find
   split-off copies.
   [ note from Feb09.  This should be OK now. Both will need
   incorporation, and we now hold on to blocks until they are
   incorporated.]
   


23rd February 2009
  - index block.  What changes are allowed exactly.
     - splitting certainly makes sense.
     - merging two adjacent blocks is fine, of which a special case
       is finding that a block is empty and so removing it.
     - What about a 2->3 split which would require removing a block
        and adding another at the same time?
       or noticing that the first blocks addressed are all missing, so
       moving the index forward?
       In each case, searching down by indexes will find a block that
       has been replaced by a later address.  We could manage that as
       long as the new block is attached after the replaced block.
       So we cannot move a block.  We must delete and replace.

  - unincorporated index blocks..
    unincorporated data blocks are not pinned in memory.  Once they have
    been written out, they can be freed.  Their address is stored in the
    uninc-table.  This means we can delay incorporation while many
    extents are written out and freed.  When we come to incorporated, we
    may have many hundred of address in a few extents that can be incorporated
    efficiently without holding all that data pinned in memory.
    The same scale doesn't apply to index blocks.  An index block can
    reference only 102 blocks (for 1K block size).  And the uninc table can
    hold far fewer so we will naturally incorporate more often.
    So keeping index/indirect/extent blocks pinned until they are incorporated
    is reasonable.  And it makes lookup a lot easier, as we have
    guarantees about ordering of block in the children list that we
    don't have in the uninc table.

    Incorporation could have some atomicity issues.  There is no
    concern about bad stuff appearing on disk as the phase-change
    process handles that.  In memory it might be awkward if we split
    an index block before incorporating a block what would span them.
    That could conceivably happen if we only incorporate 8 blocks
    (size of uninc table) at a time.
    So maybe we should incorporate a full uninc list (not table) at
    a time.
    This means quite different code paths for incorporating leaf
    and internal index blocks....


  - uninc_table lists are a real problem.
    They can only be created during roll-forward so they hardly ever
    happen.
    But if the block is split while processing earlier things on the
    list, then splitting an uninc table would be very messy.
    Is there any way around this?
    Why not just do incorporation during roll-forward?
    We only need to incorporate leafs, not internal blocks because we
    don't use uninc_table for internal blocks any more.
    So during roll forward, all index blocks that are touched need to
    be held in cache...
    I think we live with that.  If it every becomes a problem, we will
    need to perform the roll-forward twice.  The first time collects
    the usage information so that we know where we can start writing,
    then the second just applies all the changes. to the rest of the
    filesystem.


   So:
     uninc table only used for leaves, and has no linked list
     unincorporated index block are stored on a list, which we
     sort before applying.
     All uninc index blocks are therefore kept in the index tree.
     Their order on the children list allows us to find the correct
     index. Each block for which the fileaddr is in the parent is
     followed by any blocks that have been split off and end after
     this one starts.  Blocks that have been emptied are Hole and are
     skipped over when looking for a block.

     When we split an internal block, the remaining uninc blocks
     must not start with a Hole.

   FIXME: what locking do I need around lafs_incorporate?
      i_mutex?? i_alloc_sem??
      i_alloc_sem is imposed by truncate (inode_setattr) and
         direct_io possibly.  So it is really about adding/removing
         blocks.  Not updating internals.
         Maybe our own mutex.  Could even be per-index-block !!
      Whatever it is, we need to protect walking ->children too.


24th February 2008
  "rm -r" problem from 12/dec/2008 fixed now.
  incorporate code got a make-over and is probably much better.

  New problems:  After test runs, cannot create files due to no space
     on devices!!  But directory tree is empty.
  I can see:

    free_blocks=3256 allocated=1425 max_seg=512 clean_reserved=0

  The problem is that we think 1425 has been allocated to data that
  might still need to be written, leaving not enough room for more.
  Index Dump shows
  ====================414 credits ==============================
  which doesn't explain everything, but does explain a lot.  There
  really should be nothing in the Index tree (except fs-root and
  tree-root)
  There is also:
  Some inodes which are OnFree and hold no credits.
    0 DATA (1)  52 [0]ESegRef,Claimed,PhysValid
    52    1 (0)   0 [2564]{0,00000000}L on free Index(1),InoIdx,OnFree,PhysValid

  Some other inodes which are pinned with lots of credits and are
    on the phase_leaf list
    0 DATA (1) 299 [0]ESegRef,C,CI,Claimed,PhysValid
   299    1 (1)   0 [0]{0,00000000} [0, 0]L Leaf1(40) Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid,Prealloc

  And that is about it.  some are not Valid, some are...
  checkpoint just wants to 'flip' them.
  They mostly have a refcnt of 1... I wonder who is holding that....
  The reference of on the dblock is held by the iblock.
  But what is the iblock remaining?  Who holds that reference?

  I restored some code to clean iblock, and now:
  free_blocks=3229 allocated=1277 max_seg=512 clean_reserved=0
  ====================244 credits ==============================
  which saved 130 credits.  That helps.
  There seem to be many fewer of the many-credits blocks
  Lot of index blocks in tree are 'OnFree' and have a
  0 refcnt, but haven't been removed.  Why?
  It seems that the have ->parent == NULL, so lafs_refile never
  bothers to remove them.  I guess it should...
  OK, lots of InoIdx block have gone now with their DATA blocks.

  So, remaining blocks are pinned to their phase with lots of Credits,
    have not pincnt, mostly have physaddr==0.
   It is just the stray refcnt that keeps them there..
   inums are 40, 56, 62-73, 275-278, 280
    40 is f22
    56 is first adir
    63-69 are directories 2/3/4/5/6/7/8/9
    70-73 are looooong symlinks
    275 is cfile
    276 is dfile - same as cfile but truncated.
      Then some nbfile-X that were big enough.

   So: what do they have in common:
     Several only use the in-inode data block, but
       probably not all

    Can it be that it is refcounted on the Leaf list, and so
    cannot get off??  Yes, I think so!
    We only unpin things that have a zero refcount.

    So: what to do?
      checkpoint takes it off the list, then flips the phase and puts it
      on the other list with refile.  During that time it has a refcount
      it doesn't lose the pinning.
      Do we want to:
        1/ Not have it on the list despite being pinned.
        2/ Drop the PIN despite the refcnt.
        3/ have refile do the phase_flip so it has a chance to
           notice the refcount has hit zero.

      2 isn't really an option.  We need PIN to persist whenver we have
       a reference.  We could possibly use PinPending for index blocks too,
       but that would require a lot of thinking.
      1 requires another criterea for being on the list.  I suspect that would
       get messy fast.
      3 we used to do I think... But refile is in a big lock, and we
        cannot really do a phase_flip under that.. and phase flip calls
         refile anyway so we would get recursion.
      So:4 - get lafs_phase_flip to notice and de-pin rather than flip.

      FIXME use kzalloc where appropriate.

      FIXME Maybe test refcnt-!listempty in refile and de-pin if that is zero.

25th February 2009
  Good progress.
  Only 54 credits in Index Tree now.
  Inodes 1 2 8 16 are present. (fsroot, dirroot, inodemap, segusage)
  plus '74', which seems to be schedules for deletion - root has uninc_table.
   ... and 'sync' got rid of that and left 44 credits.
  Also have data blocks for inode 50 55 72 73 74 with 2 credits of 74.
    50  link
    55  zfile
    72  long84
    73  long85
    74  adir
  These seem to be the files that used data-in-the-inode
  They still have a refcnt of 1 (or 2 for adir).
  ... OK, that's gone now.  I fould a refcount leak.

  So now:  42 Credits in Index Dump.   No stray files.

  df: tot=4608 free=4597 avail=3045(4130-1085) cb=8 pb=0 ab=3
  So we still seem to have 1085 blocks allocated.  42 are accounted
  for, so 1043 still missing... either we lost the count, or lost the tree.

  create a finy file, remove, and sync, now
  df: tot=4608 free=4597 avail=3018(4118-1100) cb=8 pb=0 ab=3

  so I lost 15, b ut now 48 are in tree.  Lets try again...
  df: tot=4608 free=4597 avail=3006(4108-1102) cb=8 pb=0 ab=3
  and 44 in tree
  and again:
  df: tot=4608 free=4597 avail=2986(4098-1112) cb=8 pb=0 ab=3

  Definitely losing more thant the difference in the tree.

  Try creating empty files...
df: tot=4608 free=4597 avail=2986(4098-1112) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2974(4088-1114) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2954(4078-1124) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2942(4068-1126) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2922(4058-1136) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2910(4048-1138) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2890(4038-1148) cb=8 pb=0 ab=3

 very strong pattern there.
 What about 2 files at a time.
df: tot=4608 free=4597 avail=2879(4028-1149) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2860(4018-1158) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2849(4008-1159) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2830(3998-1168) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2819(3988-1169) cb=8 pb=0 ab=3

  Slightly different pattern - not as bad.
  Have to try 4 now.
df: tot=4608 free=4597 avail=2802(3978-1176) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2793(3968-1175) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2776(3958-1182) cb=8 pb=0 ab=3
df: tot=4608 free=4597 avail=2767(3948-1181) cb=8 pb=0 ab=3

  Strange, isn't it....

  Making sure we clear UnincCredit... result looks worse.

26th February 2009
  I fixed up the credit accounting 'incorporate' and then fixed a couple
  more little bugs.  And now:



====================48 credits ==============================
df: tot=4608 free=4597 avail=3172(3940-768) cb=10 pb=0 ab=1

So we still have 720 allocated credits that aren't accounted for.
But we are nicely under 100...

.... and now


====================76 credits ==============================
df: tot=4608 free=4256 avail=2160(2402-242) cb=350 pb=0 ab=2

That is different.  The count of missing blocks is way down,
but there is some extra cruft in the index tree.
Quite a few like
    0 DATA (1) 303 [0]L Leaf1(13) SegRef,Claimed,PhysValid
    0 DATA (1) 302 [0]L Leaf1(14) SegRef,Claimed,PhysValid
and even one
    0 DATA (2) 330 [0]L Leaf1(1) SegRef,C,CI,Claimed,PhysValid
   330    1 (1)   0 [0]{0,00000000} [0, 0]L Leaf1(0) Index(1),Pinned,Phase1,InoIdx,SegRef,C,CI,CN,CNI,PhysValid,Prealloc
Time for a commit though....

and now
====================46 credits ==============================
df: tot=4608 free=4257 avail=4253(4458-205) cb=350 pb=0 ab=1

so the strays in The index tree are gone. but still have 159 outstanding
credits.
Now change but now
====================36 credits ==============================
df: tot=4608 free=4256 avail=3787(3885-98) cb=350 pb=0 ab=2


That is a little weird...
Hmmm. back to 
====================48 credits ==============================
df: tot=4608 free=4257 avail=4247(4458-211) cb=350 pb=0 ab=1

Oh well.
====================34 credits ==============================
df: tot=4608 free=4257 avail=3176(3373-197) cb=350 pb=0 ab=1

It seems that the unaccounted blocks are (or can be) created by
writing to a file then removing the file without a sync.
..but why is cb (cblocks_used) so high?

27th February 2009

 Got onto a bit of a tangent...
 What happens if we truncate a block while it is on a list to
 be cleaned?  Clearly we want to cleaner to drop it ASAP.
 But what if invalidate_page wants to drop it *now*
 Hopefully it is either still on clean_leafs and we can remove it,
 or it is now iolocked and we can wait for it.  So should be OK.

 I keep getting caught in "looping on..."
 We are truncating an inode and some index block which is now empty
 is not getting removed from the tree because there is an outstanding
 reference.... 327/0 depth=1.  I guess I turn on the tracing.

 ... and it seems that it is in the process of checkpointing.
 I guess I need to lock against that ... maybe with the iolock.

Credits = -1, rv=2
ib = [ce814e40]328/0(2552)r3:Index(1),Pinned,Phase1,Valid,Dirty,CI,CN,CNI,UninCredit,PhysValid,Uninc{0,0}[0]
------------[ cut here ]------------
kernel BUG at /home/neilb/work/nfsbrick/fs/module/segments.c:371!

 -------
 Every time I create/delete a file, I get an extra 'ab' which disappears
 on 'sync'.
   ablocks_used is:
     decremented when +ve summary_update on non-index
     increased on lafs_summary_allocate... should not be done for index blocks.

 OK:  after test run, filesystem is empty, but cblocks_used is around 360.
  cblocks_used:
        is loaded at mount time
        collects pblocks_used on a phase flip
        is updated in lafs_summary_update (unless pblocks is)
   So we must be missing a lafs_summary_update when phys->0


 Lots of problem:
   truncating big (multi-level index) seems to be bad
     Leaves 'pb-338 !!! and cb+689, even after sync.
   still 'looping on' occasionally
   Haven't found cblocks_used leak yet.
   Occasionally non-B_Valid blocks are actted on.
     I think I need to improve io locking.

---------------
1st March 2009
  Need some improvements to iolock locking.
  We use this lock to wait for a block to be written out (if that is happening)
   before we allow lafs_invalidate_page to complete.n
   It is also use in lafs_erase_{d,i}block (Similar purpose)
  We take the lock in lafs_cluster_allocate, and then make sure the block is
   still dirty.

  Also lock in lafs_new_inode as initing the inode is a form of IO ??
  load_block takes the lock
  We only clear_bit(B_Valid, ) under this lock.

  So the issue is this:
    A block that is going to be written is passed to lafs_cluster_allocate.
    This happens either after taking it of a _leafs list, or when 
    lafs_writepage requests the write.

    lafs_invalidate_page needs to be able to release the page, so there needs to
    be no transient references.  In particular, once the block has been
    removed from a _leafs list it must already be iolocked.
    Invalidate_page can then either remove from that list and erase the block,
    or use io_lock_block to wait for the IO to complete.
  So when a datablock comes out of get_flushable it must be iolocked, and must
  remain iolocked until after Dirty and Alloc are clear
  Index blocks belong entirely to the fs, so we can be more relaxed with them.
  If get_flushable finds the block already iolocked, it is either being invalidated
  or already has IO pending, so it can be dropped.


16th Match 2009

  FIXME  When we sync a small file, we just write out the inode.
     rollforward currently ignores data in inodes I think.
     Thanks needs to be fixed to ensure this data is safe.

 - stop iblock from disappearing so much.

 - I think...
    While cleaning a file, I truncate it.  This makes it appear
    to fit in the inode but it is very big and we get confused.
   We cannot allocate block 0 until all the others have been
   allocated to 0 and forgotten.
   But what if we truncate a file to 10 bytes, then fsync?
    We need to write the data promptly, but we like doing truncate
    in the background.
   When we extend a file we already need to wait for truncation
    to complete (FIXME do we do that?)  We could wait on fsync too.
   We cannot just delay block0 as it might be part of a checkpoint
    that has to complete promptly while truncation can take a long time.
   i.e. we have a very large file.  We update the first byte, then
    truncate to 2 bytes.... we don't need to write until fsync which will wait...
    Directory?? delete lots of entries so it shrinks to one block?
       There is no delayed truncate there.
   ?? Never clean an I_Trunc file.  
   If we try to allocate a file with other indexes:
     clear Realloc
     if Dirty and Pinned, just do normal alloc
     if Dirty and not pinned, skip.


  Sometimes I run out of credits while truncating a file.
  I need credits - maybe only briefly - to dirty the index blocks.
     -- FIXED I think.

  An indexblock remains pinned while the refcount is non-zero.
  A pinned index block can be on a _leaf lru
  The _leaf lru holds a refcount.
  This is an awkward referential loop.
  We break it at checkpoint time with special code in phase-flip.
  But there are other awkward times such as truncate.

  We cannot use PinPending like we do with data blocks because there
  could be multiple pending Pins (from different children).

  We could possibly treat checkpoint_lock like pinpending, but that 
  might be racy.

  We could not count the _leaf lru, but that might just make the race
  harder to find.

  I think we want to explicitly drop the pin when we truncate a block.
  Normally, once we Pin an index block is will become dirty so we don't
  want to de-pin before a checkpoint anyway...

  Just to clarify: an index block gets dePinned:
   - during checkpoint on a phase_flip if it is no longer dirty etc
   - on truncation when we erase it
   - during pre-emptive write-out which is a bit like an early phase_flip
           not sure that we implement that one yet.

17th March 2009
 Deadlock?
   - checkpoint calls incorporate call erase_iblock calls iolock_block
   - rm calls orphan_pin calls phase_wait
 The problem is in lafs_incorporate.  It expects the block to be iolocked,
  but can call erase_iblock which try to get an iolock itself...
 ...fixed that and it still happens.
 checkpoint calls phase_flip calls allocated_block (on uninc list) calls
    iolock_block before calling incorporate
 Maybe all of these should assume an IO lock.

 FIXME truncate assume truncate-to-zero.  We need proper ftruncate support.

 It nearly works....
  Things to do:
    - sort out individual patches and review DONE
    - allow compilation without refcount tracking DONE
    - don't hold a 'leaf' reference. NO
    - clean up *ref calls - differentiate those that can be called when zero DONE
    - use enum for B_* DONE
    - support truncate to non-zero offset DONE
    - "looping on" found an 'OnFree' block!
    - clean out lot of debugging

 Hmmm.... deadlock.
  rmdir is holding i_mutex and waiting for a phase change to pin a dblock.
  checkpoint is also holding i_mutex.. or is trying to get one in lafs_cluster_allocate.
  Not cool.  i_mutex must not be taken by checkpoint
 Fixed that, though it is a bit of a hack....

 New deadlock:  checkpoint calls phase_flip which calls allocate_block,
    to move the uninc_next across, and that tries to iolock the parent to
    perform a partial incorporation.  But that seems to be iolocked.
    Generally that is ugly as ->uninc_next might be very long and require
    multiple splits, and direct-driving that from phase_flip is bad.
    I should just move the list across


19th March 2009
  Spent too long trying to remove refcount help by *_leaf lists.
  This leaves InoIdx block with zero refcount so Data block can get
  lost and bad things happen.
  I might be able to fix it up, but it is probably better to try the
  checkpoint_lock approach if I can only remember what that is.

Locking:
  Available locks:

   Spin:

    lafs_hash_lock
        Used in:
           lafs_shrinker
           lafs_refile ???
        Protects:
           ib->hash
           ->lru when on freelist 

    i_data.private_lock
        Used in:
           lafs_shrinker
        Protects:
           ->iblock / refcnt
           ->dblock / my_inode
           ->children / ->parent within an inode
           setting ->private

    fs->alloc_lock
        fs->allocate_blocks

    fs->stable_lock
        segsum hash table
        segsummary counters (in blocks)

    fs->lock
        _leafs lru
        ->pending_blocks lru - should this be wc->lock ??.. not in 'bh'
        Pinned consistent with lru
        ->checkpointing / ->phase_locked
        fs->pending_orphans
        ->uninc and ->chain ??  Should use parent->B_IOLock ??
        uninc_table - should use B_IOLock
        free list / clean list segtrack

   Mutex:

    fs->wc->lock 
      wc[0] .. something in prepare_checkpoint
       ->remaining etc
      cluster_flush
      mini blocks

    i_mutex
      inode_map
      orphans

   Other:

    B_IOLock
       erase_block
       incorporate
       cluster_allocate
       allocated_block
       IO
       Phase flip
       Initialising new inode
    B_IOLockLock
         IOLock across a page


--------------------
This is a list from 18 months ago, with updates

 - Understand how superblock 'version' should be used.

 -  Review and fix up all locking/refcounts.  See locking.doc
       Also lock inode when copying in block 0 and probably
       when calling lafs_inode_fillblock (??)
 -  lafs_incorporate must take a copy of the table under a lock so
         more allocations can come in at any time.

 - We don't want _allocated to block during cluster flush.  So have
   a no-block version and queue blocks on ->uninc if we cannot
   allocate quickly.  Find some way to process those ->uninc blocks.

 - Use above for phase_flip so that we don't need to _allocated there.

 - Utilise WritePhase bit, to be cleared when write completes.
     In particular, find when to wait for Alloc to be cleared if
      WritePhase doesn't match Phase.
       - when about to perform an incorporation.
 - make sure we don't re-cluster_allocate until old-phase address has
     be recorded for incorporation.

 - allocate multiple WAIT_QUEUE_HEADS for 'block_wait'

 - Can inode data block be on leafs while index isn't, what happens if we
       try to write it out...

 -  If InoIdx doesn't exist, then write_inode must write the data block.

 - document and review all guards against dirtying a block from a previous phase
    that is not yet safe on storage.
          See lafs_dirty_dblock.
 - check for proper handling of error conditions
     b/ if lafs_seg_dup fails in do_checkpoint, we need to abort the snapshot.
 - review checkpoint loop.
       Should anything be explicit, or will refile do whatever is needed?
 - Waiting.
       What should checkpoint_unlock_wait wait for?
       When do we need to wait for blocks the change state. And how?

 - load/dirty block0 before dirtying any other block in depth=0 file

 - use kmem_cache for 'struct datablock'
 - indexblock allocation.
        use kmem_cache
        allocate the 'data' buffer late for InoIdx block.
        trigger flushing when space is tight
        Understand exactly when make_iblock should be called, and make it so.
 - use a mempool for skippoints in cluster.c
 - Review seg addressing code in cluster.c and make sure comments are good.
 - consider ranges of holes in pending_addr.

 - review correct placement of state block given issues with stripes.

 - review segment usage /youth handling and make a todo list.
      a/ Understand ref counting on segments and get it right.
 - Choose when to use VerifyNull and when to use VerifyNext2.
 - implement non-logged files
 - Store accesstime in separate (non-logged) file.
 - quotas.
        make sure files are released on unmount.

 - cleaner.
       Support 'peer' lists and peer_find. etc
 - subordinate filesystems:
     a/ ss[]->rootdir needs to be an array or list.
     b/ lafs_iget_fs need to understand these.
 - review snapshots.
      How to create
      how they can fail / how to abort
      How to destroy
 - review unmount
      - need to clean up checkpoint thread cleanly - be sure it has fully exited.
 - review roll-forward
      - make sure files with nlink=0 are handled well.
      - sanity check various values before trusting clusters.

 - Configure index block hash_table at run time base on memory size??
 - striped layout.
         Review everything that needs to handle laying out at cluster
         aligned for striping.

 - consider how to handle IO errors in detail, and implement it.
 - consider how to handle data corruption in indexing and directories and
     other metadata and guard against problems (lot of -EIO I suspect).

 - check all uninc_table accesses are locked if needed.

 - If a datablock is memory mapped writeable, then when we write it out,
     we need to with fill up it's credits again, or unmap it.
 - Need to handle orphans asynchonously.

 - support 'remount'
 - implement 'write_super' ??

 - pin_all_children has horrible gotos - remove them.

 - perform consistency check on all metadata blocks read from disk
   e.g. don't assume index blocks are type 1 or 2.

23rd March 2009
 + looking at cleanup for unmount.
 - various more refcounts fixed up
 - B_SegRef is never dropped!  and we take a ref on a segment when
   we start a cluster on it, but never drop that reference.
  THIS is next thing - review all setting and clearing of B_SegRef.

30th March 2009
 - SegRef and lafs_reserve_block...
   There is room for recursion here, I need to be careful.
   To dirty a data block, all parent index blocks must be Pinned and must
   be able to be written.  That means their segusage blocks must be
   available for update.  And Pinning a segusage block for update requires
   all its parents.  So the segment for the block, the indexes, and the
   segusage and indexes and so-on must all be pinned.
   When we pin a block, we do it from the root down to avoid recursion.
   We probably wany whatever reserve_block calls, to return an unreserved
   block rather than call reserve_block itself.

  When do we clear SegRef?? We set it when Pinning, so I guess we
    clear it when unpinning.
   pin_dblock, mark_cleaning, prepare_write, truncate
   seg_move clean_free
  We it is really when Pinning, or Dirtying or Reallocing.
  So we clear when unpinning, or when a dblock gets written...
  Maybe just when we lose ->parent

6th April 2009
 - sometimes sugsum counter goes zero for random data block
     Something is going wrong in roll-forward.  The block looks transiently valid
     so doesn't get read, but has no good data in it.
 - After deleting a directory, the block might still have incorporation
   to happen, but is not marked dirty
 - at unmount, there are various blocks that are still dirty.
 - sometimes hit BUG_ON(credits==0) line 1196 in cluster.c(cluster_flush)

12th April 2009
 - that rollforward problem above:
    When rolling the checkpoint, if we find segusage blocks we want to include
    them directly into file.  But by pinning the block we might preread a
    segusage block.. but we must be sure not to update it.
    So during the early stages of rollforward while still in the checkpoint,
    seg_inc must be called with in_phase == 0.
    so seg_move is called with phase != qphase.
    ditto for summary update.
    So the block must be pinned to the previous phase...
    Normally 'phase' changes at checkpoint-start,
             qphase changes at checkpoint-end
    So we probably want to start with qphase being 0 and phase being 1.
    When we reach the end of the checkpoint, we flip qphase to 1.

 - blocks still in phase_leafs at unmount:
    After we force a final checkpoint we still have Pinned:
        root InoIdx
        ino==8 InoIdx due to Dirty block0
        ino=16 InoIdx due to dirty block0
     and dirty:
        inode block 1,  inode usage map
                    2,  root directory
                    8,  orphan
                   16   seg usage
     Problems:
        inode blocks dirty but not pinned?  No InoIdx...
        Segusage dirty - probably by seg_apply_all - disable that at umount
        orphan dirty ??... but not pinned!
           This is possible - we don't pin for clearing entries, just for setting.
        The inode problem stems from the datablock being dirty while the
         InoIdx block isn't.  That is, at best, confusing.

13th April 2009
   segusage blocks aren't being pinned
   They need to be pinned  whenever dirty.
   and youth blocks aren't even made dirty some times.  They need to be
    pre-pinned in many cases.

   So: segusage gets changed when we write out a cluster, and when we
      delete/relocate blocks.
      In the first case we pin the block when it becomes part of the free list,
      and need to keep it pinned across checkpoint changes.
      In the second, we pin when the block is dirtied and again must keep it pinned.
      Youth gets changed when a segment becomes free and again when we allocate
      a segment to it.

      Keeping a datablock pinned across checkpoints is awkward - we currently need
      to repin for each dirty... I guess we can re-pin for each checkpoint
      in lafs_seg_apply_all.  That might work for segusage, but not for youth!
      If segsnum for ssnum==0 held a reference to the youth block, that might
      help.  Segstat on 'clean' or 'free' would imply a reference to that segsum.

      Is it OK to keep all youth/usage blocks for free/clean blocks
      pinned?  We can currently have 810 entries.  Only half will be clean/free.
      For each entry there can be two blocks, youth and usage.  So that could be
      810 blocks. 1Meg?  Normally much less.  If it became a problem we could
      reduce the number dynamically I guess.

      maybe segusage blocks need to get phase_flipped, as other blocks do
      depend on them,   pin_all_children wouldn't be able to find them though..

    1/ Any address on 'clean' or 'free' segtrack implies a refcount on the
      Youth block.
      
14th April 2009
   I think I want to link dirty block to the space in free segments that we
   actually know about.  Each of those segments has youth and usage blocks
   pinned (at least parent pointer is active).  So we have everything we need
   to write everything that is dirty.  So 'free' or 'clean' implies
   a segsum reference which holds youth block.

   When we get low on space, we wait for cleaning/finding to progress.
   This would limit us to  400 segments, say 16Meg each, so 6Gig of dirty
   memory.  I guess that we need to scale the 'free' list based on available
   memory (FIXME).

   When cleaning needs a segment, it needs to load the usage blocks for other
   snapshots too.

   When cleaning in the presence of snapshot we need to be careful never to
   duplicate a block that is shared.  To allow for v.many snapshots, we don't
   even want to duplicate in memory.
   So we need to choose a 'primary' copy - probably first one found - and
   follow the peers link when possible...

18th April 2009
   (continuing).

   So clean and free segments in the list carry a SegRef.  But it could be
   excessive if all of them did - we shouldn't be required to pin more
   data than we need.
   So for segments with a usage of 0, we use the score to record if a
   segref is held.  0 means 'no', 1 means 'yes'.
   When space_alloc wants more space we need to find an entry and
   segref it.  Maybe we want free lists - reffed and not-reffed.

   Then again, SegRefs are fairly cheap as they are heavily shared.
   maybe 512 to a block.  If we hold 400 refs they could easily all be
   in one block.  We could possibly encourage this by sorting the list
   and discarding from one end if it is too full.
   Sorting is a good idea definitely.  It keeps youth/usage updates
   together.

   Just check the numbers.
   a 1TB device with 1K blocks might have 32M segments of which there
   would be 32768.  512 per block means 64 blocks or 16 pages (64K).
   So total segusage files is 128K plus snapshots.  Not worth worrying
   about surely.
   For 16TB, that is 2Meg plus snapshots.

   So
    - keep a SegRef for all free and clean blocks.
      This must include a youthblk reference.
    - sort the free list when 'clean' is merged or when a pass
          finishes.
        sort clean list
        fix youth value
        merge as many as fit into free
        sort 

   How is the code flow...
      add_cleanable is called during the periodic scan.  It could hold
               a SegRef easily.
      add_cleanable calls add_clean as does lafs_get_cleanable during
          clean.  That might block getting a segref, might even
          deadlock?
      add_free is also called by seg_scan

      So seg_scan should get a segref and leave it with everything!

    BUT.....
    A SegRef implies a 'struct segsum' for each segment.  We don't
    want to allocated one of these for every segment in the table.
    We only want a reference to the youth and segusage block, which
    are heavily shared.

    But these blocks need to be Pinned and SegReffed etc so we can
    write them at any time.

20th July 2009
  The refcount held by the 'leaf' lru is a problem.
  While it holds a count we do not unpin an index block, so it cannot
  be removed from the list.
  Thus we can only remove from the leaf lru on a phase change.....
  Or when doing lru based flushing... Maybe we can remove from the
  lru while holding the checkpoint lock.
  This happens when truncating..

  No, that is just too messy as it is too easy to get put back on the list.

  Maybe the leaf lru should not imply a reference count ... or maybe
  we need to split the refcount:  'inuse' and 'active'.....
  How about we test refcnt against list_empty(->lru)...

  ....

  During truncate, we need each index block to get unpinned so they can
  all be cleaned up.
  But the InoIdx block is held pinned by by the inode block being dirty.
  In this particular case, the InoIdx block is Invalid as the file is empty.
  But.... InoIdx should always be valid until after Inode is destroyed??


 umount
 I need to stop the cleaner and flush everything before trying to
 clean up.

 This is awkward though.
 The 'sync' of umount is done by kill_block_super, but I call
 that rather late, after checking that the tree is empty.
 There are pinned/dirty bits left after sync that we want to magically
  clean.
 We have:
   - segusage/youth blocks.  Maybe if we don't seg_apply_all...
   - orphan block.  Maybe don't mark it dirty when we remove things?
   - inode map?? why is that dirty

   - root directory is dirty still??  But it has been erased.
     InoIdx is valid-but-empty.  Inode Data is dirty
        Data block 0 is Dirty at block 0.

  ......
 Ahh... need to mark page dirty when block is marked dirty !!

 The seg usage blocks are now flushed out but not incorporated.
 I feel that might be correct - we don't want to care about
 incorporation as we will never use it.
 For this, segusage and quota are very special cases.

 Inode map is no longer dirty, but is pinned
 Orphan does have a dirty block still
    The orphan table contains the root directory.
 root is now clean and gone

 Segusage doesn't get incorporated after last checkpoint now
 so that is better.
 But now we have a circular reference for SegRef.  This should not
 be surprising given the circular problems we had setting SegRef.
 I guess we just erase the references in the segsum table...

22nd July 2009
 Hurray!!! I can unmount without crashing!
 Now I need to sort through all the fixes required to achieve that
 and make discrete patches, and be sure it is all OK.

DONE - (block.c) lafs_get_block should not have to lock that page just to do a lookup.
DONE - (block.c) Mark page dirty when block becomes dirty
DONE - (checkpoint.c) print orphan_slot with Orphan flag
DONE - Don't incorporate segcount etc after final checkpoint
DONE - Don't apply seg changes after final checkpoint.
DONE - Don't start opportunistic checkpoint after final.
DONE - (checkpoint) if InoIdx isn't dirty but InodeData is, then still allocate
DONE - (checkpoint) when waiting, wait for checkpointneeded to get cleared
DONE - (cluster) be more flexible about credit usage when flushing InoIdx
DONE - (dir) do add_orphan when we abort as well as on success
DONE - use inode_dec_link_count, not i_nlink--
DONE - (file.c) lafs_writepage: remove from leafs when we cluster_allocate
DONE - change %d/%d to strblk
DONE - (index.c) refile: IF B_IOLOCK, the it isn't on LRU
DONE - (index) refile: when unpinning, remove from lru
 - lafs_refile: ->iblock can be non-null for inode 0.
DONE - Make sure I_Deleting gets cleared when deleting finished.
DONE - phase_flip should have something separate to call, not lafs_allocated_block
 - inode.c: lafs_dirty_inode: getref_lock used to get dblock
NONO - ?? getref_locked allowed if PagePrivate
DONE - segment: lafs_seg_put_all needed at unmount
DONE - segdelete_all: need to put intable references
DONE - lafs_free_get: put the intable references
DONE - lafs_get_cleanable: put the intable references
DONE - fix sort splitting in add_cleanable
DONE - add lafs_empty_segment_table for unmount
DONE - lafs_release: flush all dirty blocks
DONE - lafs_release: force a final checkpoint
DONE - lafs_release: move kill_block_super before final check
DONE - lafs_put_super: release orphans and segsum files.
DONE - lafs_destroy_inode: putref should be 'iblock'
 - lafs_destroy_inode: allow for iblock to be present but no ref held....
DONE - can roll forward call lafs_allocated_block without dirty???

27th July 2009.
 - I've re-arranged lafs_release so that the flush is all done in
   generic_shutdown_super.  However it calls invalidate_inodes, and that has
   problems with pinned inodes.  So we need for fsync_super to checkpoint
   out all inodes that we don't hold our own reference to.  
   If we do hold a reference, then invalidate_inodes will skip them,
   and ->put_super can be used to drop the references and perform the final
   checkpoint.
   fsync_super calls ->sync_fs. after syncing call files.  Maybe I can
   do some sort of checkpoint there...
   There almost is a checkpoint in there.... But only when called without
   'wait'....
   I need to understand 's_dirt'.
   This is controlled entirely by the filesystem, common code only examines it.
   If it is set:
          file_fsync (the generic 'fsync' method) will call ->write_super
          fsync_super will call write_super
          generic_shutdown_super will call write_super
          sync_supers will call write_super
          sync_filesystems(0) will call ->sync_fs
   sync_fs is called:
        twice from 'sync', once with '0', once with '1' for 'wait'.
             (though in emergency_sync, both are '0').
        once from unmount and remount with 'wait' set to '1'.
        We don't want two checkpoints for a 'sync', but we want to start
        on 'wait=0'.
        Maybe if we get called with '0', we set a flag and treat the '1'
        differently..  There is no locking to make this really safe, but
        it will probably be OK...  I could take a process_id, but then
        parallel 'sync's could race.
        write_super is called before the syncs.  So it could start the checkpoint,
        and sync could wait for it.
        write_super is called multiple times at shutdown,  We really need 
        to utilise sb_dirt to avoid some of these.
        We set sb_dirty to 0 when we set CheckpointNeeded, and set it to 1:
            - when we pin a dblock or dirty a this-phase iblock.

29jul2009
  at unmount, we iput the root inode which de-references the dblock
  before clearing ->iblock, which fails an assertion ... why?
   Apart from the shinker, ->iblock is only set to NULL in refile
   when we find an I_Destroyed inode... I guess the root block isn't
   getting Destroyed...
 The protocol for freeing iblocks is bad.  Should be:
   - it only gets freed by the shrinker
   - when inode dies, set ->inode to NULL
   - when InoIdx iblock dies, set ->iblock to NULL
   ...???
30Jul2009
  So, what exactly is the protocol?
    - index blocks live either in the parent/sibling tree, or
      on the inode's free_index list
    - when refcnt is 0, they live on 'freelist.lru'.  When refcount
      is elevated they stay on lru until they need to be 
      added to some other lru (leafs or cluster)
    - when shrinker finds block on freelist.lru with non-zero refcnt,
      it just removes from lru
    - when shrinker finds free block, it removes from free_index and discards
      the block FIXME can refcnt=0 still have Pinned,Uninc,Realloc,Dirty ??
        I think not as such would either have children or be on an lru
    - When we destroy an inode, all index blocks get disconnected from the
      inode and freed.  This must include the ->iblock
    - When an index block becomes free due to index tree shrinkage,
      we set the ->depth to -1 so that it cannot be found by mistake,
      and leave it for shrinker or inode destruction.

   Confused about inode<->dblock dependence.
   We don't want the inode to refcnt the dblock as that wastes space.
   We don't want the dblock to refcnt the inode as that stops it from being freed.
   So each must disconnect from other when freed.
   What locking?
   inode takes private_lock, then checks dblock
   dblock cannot take private_lock before checking ->my_inode..
   Maybe: destroy_inode takes ref on dblock, thensets I_Destroyed, then
     drops ref

1Aug2009.
  Tracking down the 'credit' count and making sure it stays correct.
  It seems that I have a Dirty InoIdx block which is not pinned.
  Due to this it has no refcount and so the data block disappears so
  the InoIdx block is not visible in the tree.  This isn't a definite bug
  but it means I cannot count credits properly.
  And surely Dirty index blocks must always be pinned!!??

  When as small file is flushed to the inode we were dirtying the
  iblock.  That seems wrong - should dirty the dblock?  Need to 
  check that is valid

  I got a hang in 'rm adir/4'.
  rm is in lafs_cluster_update_commit_both
       getting a mutex.
  cleaner is in lafs_do_checkpoint+0xe4
  pdflush is in writepage/lafs_cluster_flush waiting on a lock
  so I guess cleaner is holding a mutex and waiting for something
   that wont happen?


  Hang again at 'seq 1 200' in 'cd /mnt/1/adir'.
   cleaner is at some point, holding a mutex to stop 'sh'.
  0e4 == 228

  ahh.. prepare checkpoint holds wc[0].lock while waiting for checkpoint
   to be allowed.
  So when something locks the checkpoint and needs to flush, we have problems....


  I seem to have fixed the above.  Now:
    Free space is a real problem.  When I remount after the successful unmount,
    we find a usage pattern like:
CLEANABLE: 0/0 y=10 u=34179
CLEANABLE: 0/1 y=0 u=65144
CLEANABLE: 0/2 y=0 u=65535
CLEANABLE: 0/3 y=32773 u=32910
CLEANABLE: 0/4 y=32772 u=149
CLEANABLE: 0/5 y=0 u=0
CLEANABLE: 0/6 y=32770 u=16529
CLEANABLE: 0/7 y=32769 u=35084
CLEANABLE: 0/8 y=32768 u=31877

    Which is ridiculous. 
   Better fix up what I have first...

 ...
 In rm /mnt/1/nbfile* we hang.. 
   rm is in lafs_phase_Wait from pin_dblock in unlink
wait for [ce5c2d20]277/0(0)r2F:Index(1),Pinned,Phase0,InoIdx,Valid,Dirty,CN,CNI,UninCredit,PhysValid{0,0}[8] pindb(1) leaf(1)

   cleaner is in lafs_iolock_block from add_block_address in phase_flip
iowait for [ce5c33b0]286/0(0)r6E:Index(1),Pinned,Phase1,WPhase0,InoIdx,Valid,Dirty,CN,CNI,UninCredit,IOLock,PhysValid{0,0}[1] child(5) leaf(1)

 So cleaner is probably deadlocking against itself via iolock_block.
  This is taken:
    - in lafs_invalidate_page just to wait for any io - it isn't held long
    - in lafs_erase_dblock while we erase and 'allocated_block'
    - in lafs_get_flushable to protect blocks being checkpointed
    - in lafs_writepage to call cluster_allocate (which releases), both for
             data block or for inode when data was flushed there.
    - lafs_add_block_address to process pending incorporations to make room.
         This is what is trapping the cleaner.
    - lafs_inode_handle_orphan when truncate finishes to erase_iblock
    - lafs_inode_handle_orphan again to incorporate all removal
    - and again to erase_iblock
    - and for partial truncate to incorporate some removals
    - and again....
    - lafs_new_inode to keep it from being cleaned while being created
    - roll_block to add addresses
    - lafs_load_block during IO

  So: who holds it?.... let's use the code to find out...
  And the answer is : lafs_get_flushable.
   So get_flushable iolocks the block then calls phase_flip which tries to
   incorporate other-phase children which try to iolock the block.  Deadlock.
   Do we need to hold iolock during phase_flip ??.  Not for all of it..

02August2009
   FIXME When erasing a block, do I need an uninc credit?  I usually don't
    have one and the need certainly isn't as great...

  Now... let's try to get free space accounting right.
   Observed problems:
     - unlink sometimes failed with ENOSPC
     - usage scan shows segmetns with enormous usage - 23039!!

  no credits: [ce9a55cc]16/1(2651)r11E:Pinned,Phase1,WPhase1,Valid,Dirty,SegRef,C,CI,CN,CNI,UninCredit,IOLock,PhysValid intable(7) ss(3) cluster(1)
  no credits: [cfb695cc]16/1(1840)r12E:Pinned,Phase0,WPhase0,Valid,Dirty,SegRef,C,CI,CN,CNI,UninCredit,IOLock,PhysValid intable(7) ss(4) cluster(1)

  no uninc credit [cfb695cc]16/1(2019)r13F:Pinned,Phase0,WPhase0,Valid,Dirty,SegRef,C,CI,CN,CNI,IOLock,PhysValid intable(7) ss(5) cluster(1)


  after umount/remount df says "4608 7 1544" but cannot
   create anything.
df: tot=4608 free=4601 avail=1544(1564-20) cb=7 pb=0 ab=0
============= Cleanable table (7) =================
pos: dev/seg  usage score
  0:   0/0        1 0
  1:   0/5        1 64
  2:   0/6        6 384
  3:   0/7        2 128
  4:   0/8        3 192
  5:   0/3        1 64
  6:   0/2        2 128
...sorted....
  0:   0/0        1 0
  1:   0/3        1 64
  2:   0/5        1 64
  3:   0/2        2 128
  4:   0/7        2 128
  5:   0/8        3 192
  6:   0/6        6 384
--------------- Free table (1) ---------------
12290:   0/4        0 0
--------------- Clean table (0) ---------------
CLEANABLE: 0/0 y=10 u=1
CLEANABLE: 0/1 y=32775 u=3
CLEANABLE: 0/2 y=32774 u=2
CLEANABLE: 0/3 y=32773 u=1
CLEANABLE: 0/4 y=0 u=0
CLEANABLE: 0/5 y=32771 u=1
CLEANABLE: 0/6 y=32770 u=6
CLEANABLE: 0/7 y=32769 u=2
CLEANABLE: 0/8 y=32768 u=3


03Aug2009
 Current issues:
FIXED 1/ Data 16/1 is being Reallocated, but is Dirty, not Realloc
Gone,presume FIXED 2/ Data 16/1 has no uninc credit in cluster_flush
 3/ in cleaner, ->dblock is uninitialised.... actually inode has been free.
 4/ invalidate_page find Realloc set, even after iolock ..
     This is during umount  in generic_shutdown/lafs_put_super/iput
 5/ 


 Thoughts:
   If we flag a block for Realloc then Dirty before it is allocated,
     then all is fine.
   But if we have already allocated to a cleaning cluster... what happens?
    We need to treat this like it was dirties after being written, so
    it gets written to a regular cluster as well.
    As we only have one uninc bit for both Dirty and Realloc, we need
    to *not* incorporate the Realloc update if the block is still dirty.
   So:
        - block gets chosen for cleaning and allocated to a clean-cluster
        - block gets marked dirty.  This must not clear Realloc
        - cluster is flushed, block is dirty, so don't call lafs_allocated_block
        - Return the Realloc credit, but keep dirty and Uninc.
     Is there a race if Dirty is set after we enter lafs_allocated_block?
      As long as the index block gets marked Dirty, not Realloc we might
       be safe... though it gets awkward if the Dirty writeout falls in to
       the next phase.  But reserve_block will have provided NCredits for that.
     So:
        1/ don't clear Realloc when setting Dirty
        2/ do clear Realloc if cleaner finds the block is Dirty
        3/ avoid calling lafs_allocate_block when cleaning a dirty block.
                   This is an optimisation.

    Almost...  A B_Realloc block no longer has B_Credit so B_Dirty cannot be
       set.


  Thoughts3.
     When cleaning blocks we hold no reference to the inode and it can disappear.
     We don't want to hold the inode active, but need a reference much like
      the truncate code has.
     I think we need a subordinate refcount for both cleaning and truncate.
      These hold inode present but not active.
     Maybe every block->inode should be counted like this.
     And this might simplify the my_inode->dblock inter-relationship.
     For later..
       We need to ensure that if a new iget is called on an inode that still
       exists, we don't allocate a new one but just reuse the old.
       But that won't work as we cannot add an inode back into the hash table.
     So I think when cleaning a block we need to ref the inode.
      i.e. B_Realloc implies an i_grab

05aug2009
 So I have a problem with the cleaner wanting to hold and inode that
 the VFS is destroying.
 I don't want the cleaner to hold i_count as that delays truncate etc.
 So we need a second counter subordinate to i_count.
 This is held by the cleaner and by delayed truncate, and by i_count.
 Possibly ->my_inode holds this, which means it can be a single bit...

 When a lookup wants an inode, we need to load the inode data block and
 see if it has my_inode.  If it does, we insert that inode in to the
 hash table.  If not we fall back to regular inode creation....

 On reflection, that is too complicated and hard and error prone.
 When relocating a file we need the data so it had best be in the page
 cache so the filesystem really needs to know that the inode is still
 active.
 So cleaning needs to keep a reference to the inode.
 The cost of this is that if an inode is being deleted while it is
 being cleaned the truncate cannot happen until the cleaning
 completes.  This means that space usage will be wrong.
 When nlink becomes zero we can drop the cleaner reference.  When
 the inode is dropped/destroyed we can tie the cleaning in with the
 delayed truncate so that the final destruction doesn't happen until
 the cleaner has let go.

 So: how to track that the cleaner has a reference to the inode?
 Maybe every B_Realloc block owns a ref on the inode.... but dropping
 those references when i_nlink hits zero would be difficult.
 They could hold a secondary refcount which, if non-zero, implies a
 ref on the inode.

 So:
  - Set B_Cleaning when we look at a block for cleaning, and clear
    it when we find Realloc clear and ....????
  - Whenever a block has B_Cleaning set, it holds a counted reference
    on LAFSI(b->inode)->cleaner_ref
  - When cleaner_ref is non-zero and I_Deleting is not set, we hold
    a reference on the inode (i_grab).
  - when i_nlink hits zero, set I_Deleting and drop any reference
    held by the cleaner.
 DONE - cleaner must be careful not to process any block that has been
    truncated, or file that is dead.
 DONE - Make sure the cleaner doesn't start up after the FinalCheckpoint.
  - What about filesystem inode... how do they fit in??


  Question. When are the index blocks for an inode flushed?
  We need to have them gone when the inode disappears.
  For deleted inodes, this happens in background truncate.
  For memory-pressure inodes it will hopefully happen well in advance,
  but we need to make sure in destroy_inode that everything is
  written. - FIXME


  Thinking again about B_Cleaning, any B_Realloc block will hold a
  reference through to InoIdx and so dblock will be present and the
  inode won't be freed.  So we only need an extra reference during
  the first little phase of cleaning when we are collecting blocks.
  After that a reference can be useful as it will delay flushing so it
  can be more efficient...

  Maybe this is all much simpler than I thought.
  If we hold a ref on the inode whenever the InoIdx block is Pinned
  and i_nlink is non-zero, then we won't be forgotten until all
  index blocks are written.  We may still be deleted, but as that
  is one-way we can hold on to the inode at little cost.

  getting/putting that ref at exactly those times turns out to be
  messy.
  It might be best to have a flag to say "We hold an extra ref".
  Then we occasionally call a function that validates the setting.
  It is most important to drop the count at the right time, so
  after unlink/rmdir/rename and when B_Pinned is dropped.

  B_Pinned is set in:
     set_phase which is called from:
          lafs_cluster_allocated when moving 'pin' across to data block
              so don't need checkpin
          lafs_pin_block_ph
              only need check_pin if dropping spinlock
          pin_all_children
              only pins data blocks (Index are already pinned if relevant).
          grow_index_tree
              where "inoidx block pinning" doesn't change
          do_incorporate_leaf
              No InoIdx involved
          do_incorporate_internal
              ditto
   So only need check in lafs_pin_block_ph and maybe pin_all_children...

08Aug2009
  - credits get out of sync from
      lafs_incorporate->refile->space_return from checkpoint.
      counter is one more than we can find.
      returning space on 
         i [cfb9aaf0]327/0(2261)r1E:Index(1),Valid,PhysValid[0] NP
       Note it in an Index but not InoIdx.  The parent is still in the tree.
     This that is FIXED

  - and out by 8! at
      delete_inode -> truncate -> invalidate_page->erase_dblock->space_return
    FIXED that.

  - BUG credits<0 in space_return from lafs_incorporate from add_block_address
     from phase_flip
Just Grew [cfbb5c70]331/0(NoPhysAddr)r2E:Index(2),Pinned,Phase1,InoIdx,Valid,Dirty,UninCredit{0,1}[0] child(1) inc(1)
     from [cfbb5a40]331/0(0)r205F:Index(1),Pinned,Phase1,WPhase0,Valid,Dirty,CN,CNI,UninCredit,IOLock,PhysValid{0,0}[0] child(203) leaf(2)
msg: (1,3,1)(1,1,-1)
Credits = -1, rv=1
ib = [cfbb5a40]331/0(0)r205F:Index(1),Pinned,Phase1,WPhase0,Valid,Dirty,CN,CNI,UninCredit,IOLock,PhysValid{0,0}[0] child(203) leaf(2)

    This is a predicted but not handled problem.
    The answer is that not all blocks need ICredit/UnincCredit.
    The purpose of this credit is to allow for a split in the parent.
    pre-existing index blocks can never split the parent themselves
    If an index block becomes full, it will split and this might split
    the parent.
    If an index block has free space, then it will only over flow if it
    gets multiple child updates and this will provide multiple credits.
    So an index block with space for 3 or more new addresses does not need
    and ICredit/UnincCredit.  So when we split we don't need to provide an
    uninc credit.
    In particular.
    When we have a fully InoIdx block and a single new child with 1 UnincCredit,
    each block already is either 'Dirty' or has a 'Credit', and the InoIdx has 
    an ICredit, then create a new intermediate such that
        InoIdx is Dirty and has an ICredit
        New Index is Dirty with no ICredit - it used the UnincCredit
        New child looses its UnincCredit
    When another block in the new index arrives, it's unincredit is used to
    provide an ICredit

    When a leaf block cannot fit a single address it will have ICredit.
    The block is split so that each has 3 spaces and so do not need ICredit,
    but as soon as ICredit is available, they take it.

    Worst case is that every ancestor is full and the leaf is split
    We then get two full branches, each block half empty so not needing ICredit.


  Then...
    free data being used in lafs_refile from cleaner.
    b->inode->i_sb is 0x6b6b6b6b, so inode has been freed before cleaner frees it.
    Answer: lafs_refile was derefering ->inode when it wasn't safe.
     Need to at least have a parent before it is safe.

  Hang:
     soft lockup cleaner->lafs_iget->ifind_fast ....
    Then (may be caused)
Oh dear: [cfb63670]284/0(0)r1E:IOLock,PhysValid cleaning(1)
.......: [cfb2ad20]284/0(2198)r2F:Index(1),Pinned,Phase1,InoIdx,Valid,PhysValid{0,0}[0] child(1) leaf(1)
Why have I no credits? [cfb2ad20]284/0(2198)r2F:Index(1),Pinned,Phase1,InoIdx,Valid,Dirty,PhysValid{0,0}[0] child(1) leaf(1)
------------[ cut here ]------------
kernel BUG at /home/neilb/work/nfsbrick/fs/module/block.c:656!

    It seems the cleaner gets confused and goes spinning.


  So: space problems:
    After the run, we have -14 used and 2055 available (of 4608), and
    cannot create anything.
    4 segments ar free, one is cleanable.
   free_blocks=2103 allocated=56 max_seg=512 clean_reserved=0
or
   free_blocks=1722 allocated=64 max_seg=512 clean_reserved=0
or
   df: tot=4608 free=4630 avail=977(1033-56) cb=10 pb=0 ab=-32
   free_blocks=1033 allocated=56 max_seg=512 clean_reserved=0
   and very little free

  ablocks_used is going negative - why?
   Probably we erase a dblock without clearing Prealloc.
   Then when Prealloc later gets cleared, ablocks_used is
   wrongly decremented.... no...


10aug2009  (don't forget above problems)
  Another problem.
   read->touch_atime->dirty_inode->inode_fillblock->dirty_dblock
     getiref_lock triggers BUG.
   This is presumably because I have just fixed it to get the correct
     iblock and not the iblock of the filesystem.

  FIXME I hacked around this but I'm not sure the result is right.
    The question is about when the InoIdx should be dirty and when
    the inode data block should be dirty.
   In this particular case we are writing a page of a small file.
     cluster_allocate calls flush_data_to_inode which tried to dirty
     the inode dblock but finds that iblock is not pinned...
     When we dirty a data page we aren't pinning the parent!
   That might be OK - we only need to count and reserve the parent.
    We don't need to pin it until it becomes dirty.

   Still need to resolve when which block gets to be dirty, and also
    exactly when an index block needs to be pinned.  And how does that
    related to holding a ref on the inode when the inoidx is pinned.
    Maybe it should be when the inoidx is referenced.
   FIXME

11aug2009
   Another problem. unlink->handle_orphans->erase_dblock->allocated_block
    and get a zero from lafs_add_block_address but parent is not pinned.
  And... One unmount, orphan file still has pinned blocks so the inode
    isn't free.
  And ... root still old phase after lots of 'rm' then sync.
    Inode 244 has pinned inode block held by writepage0 and writepage
         this is adir/170

13aug2009
  - lots of bugs introduced by change to marking inode blocks dirty:
     writepage/cluster_allocate wants to Dirty inode data block with no credits.
         because I put credit in iblock!

  - ohhh.... The phase contour is broken.  When a block is added to a
    cluster for allocation it isn't in the phaseleafs any more, but prevents
    it's parent from joining.  So we cannot assume that if dblock is on
    list then iblock or a child will be too.
    So when we find dblock we do need to remove it.... done that.

  - root not changing because Data 1/0 is Pinned and IOPending
     and held by writepage!!
     Problem is that IOPending blocks aren't put back on lru.
     But that should only be blocks on the cluster list.....
     But that is where I am putting it.
     Maybe I need exclusion between checkpointing and any other
       code that writes to checkpoint so checkpoint can wait
       for that ... can we use wc->lock??  That doesn't lock
       against cleaner, but that isn't a problem...
   But now 0/228 is still pinned and in writepage and IOPending
    So there is more to it than that.
    When checkpoint finds an IOLocked block, it might be about to
     join a cluster, in which case we don't really want to wait, or it
     might be undergoing incorporation in which case we want to wait.
     or it could be being erased, so wait..
     Maybe I wait until it appears on some list.... yes.

14aug2009
    At unmount Index 8/0 with child and leaf is still pinned
  This was pinned: [cfb29810]8/0(9)r3F:Index(1),Pinned,Phase0,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1)

  and..

  A problem is that something goes wrong in the erase process.
  We find new children after we erase the inoidx block!

  This was pinned: [cfb3d810]8/0(9)r284016F:Index(1),Pinned,Phase0,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(284014)

  When/how do we erase indexblock and particularly inoidx blocks?
  Does and inValid InoIdx simply mean there is no indexing and does not
  reflect on the Data block?

.xlooping on [cfbe28c0]331/0(0)r2F:Index(1),Pinned,Phase1,InoIdx,Valid,Dirty,SegRef,C,CI,CN,CNI,UninCredit,PhysValid{0,0}[0] inode_handle_orphan(1) leaf(1)

 Orphan problem:
nextfree = 0
reserved = 0
VFS: Busy inodes after unmount of hdb. Self-destruct in 5 seconds.  Have a nice day...
This was pinned: [cfb2ad20]0/0(13)r5F:Index(1),Pinned,Phase1,InoIdx,Valid,Root,C,CI,CN,CNI,PhysValid{0,0}[0] NP release(1) child(3) leaf(1)
[cfb2ad20]0/0(13)r5F:Index(1),Pinned,Phase1,InoIdx,Valid,Root,C,CI,CN,CNI,PhysValid{0,0}[0] NP release(1) child(3) leaf(1) Leaf1(0) 
  [cfa5374c]0/1(772)r0E:Valid,Dirty,UninCredit,PhysValid
  [cfb54430]0/8(775)r0E:Valid,Dirty,SegRef,UninCredit,PhysValid
  [cfb54c90]0/16(777)r0E:Valid,Dirty,SegRef,C,CI,UninCredit,PhysValid

nextfree = 1
reserved = 0
  0: 1 0 0 304
VFS: Busy inodes after unmount of hdb. Self-destruct in 5 seconds.  Have a nice day...
This was pinned: [cfb273b0]8/0(9)r3F:Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1)
[cfb273b0]8/0(9)r3F:Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1) Leaf1(0) 
  [cfb74c90]8/0(2404)r1E:Valid,SegRef,CN,PhysValid orphan(1)
badcnt 0 0 [cfb268c0]0/0(13)r4E:Index(1),Pinned,Phase1,InoIdx,Valid,Root,C,CI,CN,CNI,PhysValid{0,1}[0] NP child(4)


erase Inoidx [ce5ab3b0]172/0(402)r1F:Index(1),InoIdx,Valid,IOLock,OnFree,PhysValid[0] inode_handle_orphan(1)
erase Inoidx [ce5ab5e0]74/0(0)r2F:Index(1),Pinned,Phase0,WPhase0,InoIdx,Valid,Dirty,SegRef,C,CI,CN,CNI,UninCredit,IOLock,PhysValid{0,0}[0] child(1) leaf(1)
------------[ cut here ]------------
WARNING: at /home/neilb/work/nfsbrick/fs/module/block.c:579 lafs_erase_iblock+0x
unlink/orphan/erase_dblock_allocated_block
---[ end trace 61b8bd59512ea4da ]---
zz [ce50d6a8]74/1059005010(0)r1E:SegRef,C,CI,UninCredit,IOLock,PhysValid,Orphan(0) orphan(1)
   [ce5ab5e0]74/0(0)r1E:Index(1),InoIdx,SegRef,C,CI,CN,CNI,UninCredit,PhysValid[0] child(1)
   [ce5ab5e0]74/0(0)r1E:Index(1),InoIdx,SegRef,C,CI,CN,CNI,UninCredit,PhysValid[0] child(1)
------------[ cut here ]------------
kernel BUG at /home/neilb/work/nfsbrick/fs/module/index.c:1955!

BINGO.  When we remove last entry from directory we erase the InoIdx block,
 then when we add entries, we hit problems.


nextfree = 3
reserved = 0
  0: 1 0 0 306
  1: 1 0 0 307
  2: 1 0 0 74
VFS: Busy inodes after unmount of hdb. Self-destruct in 5 seconds.  Have a nice day...

This was pinned: [cfb2caf0]16/0(10)r3F:Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1)
[cfb2caf0]16/0(10)r3F:Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1) Leaf1(0) 
  [ce9794f0]16/0(2200)r1E:Valid,SegRef,CN,CNI,PhysValid cleaning(1)

This was pinned: [cfb2d3b0]8/0(9)r3F:Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1)
[cfb2d3b0]8/0(9)r3F:Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1) Leaf1(0) 
  [ce968c90]8/0(2175)r3E:Valid,SegRef,C,CI,CN,CNI,PhysValid orphan(3)

This was pinned: [cfb2d180]1/0(8)r3F:Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1)
[cfb2d180]1/0(8)r3F:Index(1),Pinned,Phase1,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1) Leaf1(0) 
  [ce968430]1/0(2174)r1E:Valid,SegRef,C,CI,PhysValid cleaning(1)

We have stray 'cleaning' references.
It is taken -
   on a data block that was in a to-clean segment
     at which point we igrab the inode
     the block is put on the ->cleaning list.
It is put:
   when we get an error finding the block
   when we find that it isn't in the segment
   when an error occurs loading the block-to-be-relocated
   and when we mark that block for cleaning.
  i.e. always unless we got EAGAIN or some space error.
   If we still hold some blocks, try_clean returns 0.

VFS: Busy inodes after unmount of hdb. Self-destruct in 5 seconds.  Have a nice day...
This was pinned: [cfb253b0]0/0(13)r5F:Index(1),Pinned,Phase1,InoIdx,Valid,Root,C,CI,CN,CNI,PhysValid{0,0}[0] NP release(1) child(3) leaf(1)
[cfb253b0]0/0(13)r5F:Index(1),Pinned,Phase1,InoIdx,Valid,Root,C,CI,CN,CNI,PhysValid{0,0}[0] NP release(1) child(3) leaf(1) Leaf1(0) 
  [cfa57b7c]0/1(2228)r0E:Valid,Dirty,UninCredit,PhysValid
  [ce5a4430]0/8(2231)r0E:Valid,Dirty,UninCredit,PhysValid
  [ce5a4c90]0/16(1028)r0E:Valid,Dirty,SegRef,C,CI,UninCredit,PhysValid

NOTE these inode data blocks are not pinned and so did not get written!!

FIXME I should wait for the checkpoint to finish
nextfree = 1
reserved = 0
  0: 1 0 0 301
VFS: Busy inodes after unmount of hdb. Self-destruct in 5 seconds.  Have a nice day...
This was pinned: [cfb27810]8/0(9)r3F:Index(1),Pinned,Phase0,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1)
[cfb27810]8/0(9)r3F:Index(1),Pinned,Phase0,InoIdx,Valid,SegRef,C,CI,CN,CNI,PhysValid{0,0}[0] release(1) child(1) leaf(1) Leaf0(0) 
  [ce564c90]8/0(3983)r1E:Valid,SegRef,PhysValid orphan(1)

16Aug2009
  When I clean and find an inode that is already deleted, I need to be
  very careful not to resurrect anything.. I wonder if I am.... Yes, I seem
  to be.  lafs_delete_inode gets called a lot, but mostly for dead inodes.

  BUGS:
FIXED orphans don't get cleaned up.  It seems a 'create' fails and leaves
      and orphan block un-released.
   - sometimes inodes 1,8,16 didn't get written out as they were dirty but not pinned
   - Not sure that we handle complete truncation, then adding blocks properly.
     - what should the state of the InoIdx block be?
   - On remount, the filesystem contains rubbish.
   - create fails even when there should be free space.
   - sometimes BUG in checkpoint.c - not finishing checkpoint properly...
   - iblock not valid for in 327 under cluster_flush/lafs_allocated_block
          and 74 has similar issue
     327 = adir/big1   74=adir


17Aug2009
  Segusage blocks aren't always Pinned when we make them dirty.
  Yes. That is correct.  They are not forced out by phase change but by
  lafs_seg_flush_all at the end of a checkpoint.  So they need to be
  preallocated, but not Pinned.
  But, once we have finished the last checkpoint we don't want to
  dirty Segusage blocks any more.. I wonder if we are.
  No, but we were Pinning inodes without PinPending and they
  lost the pinning straight away!

  OK, other annoyance.
   InoIdx block and similar are getting erased at the wrong
   time.
   We can only safely erase them when they have no children.
   I guess what we really want is the incorporation leaves them
   existing but empty, and when we go to write them out, if they
   are empty we register an address of 0.
   When we drop the ->parent pointer of an Index block it 
   just goes away...
   So:
    When incorporate or truncate produces and empty index block
     it simply clears B_Valid.
    When incorporate want to add to an index block, we set B_Valid
    When cluster_allocate gets a non-Valid index block it call
    block_allocated with phys of 0.

    Yes, that seems to work.  Mostly

18Aug2009
  On remount, check_credits dies: 16/20-0
    In pin_dblock/reserve/seg_ref/prealloc/space_return ?? in lafs_mount.

19Aug2009
  OK, this index block clearing is a mess.  There must be a neat model I can
  follow that will make it "just work".
  The key seems to be children.  If an index block has children, then it
  really must exist.  If it has no children and no content, then it can
  be discarded, in which case it needs to be unlinked from its sibling list.
  What locking do we use here?  Probably IOLock on the parent index block.
  So we need iolock while looking in a parent for children, and we take
  IOLock while incorporating or pruning.
  Once the empty index block has dropped out it will never be found again.
  When we incorporate the zero address, the index block becomes invisible
  unless it is shortly after it's predecessor in the sibling list.  But
  that is hard to ensure, especially if the first child is the one that
  is being erased.  So if an index block is erased, then it must be
  discarded quickly and any children need to be relocated...
  Or maybe not.... maybe if there are children, we just write and empty block?

22Aug2009
  We need better locking of the index information.
  It seems best to use IOLock as that is already held during incorporation.
  So any code that accesses or updates and index block must hold IOLock.
  This might be a bit of a restriction if we try to do a lookup while
  writeout is happening.... Maybe we need a separate writeback flag for that.
  But I think it is good to use IOLock for now.
  Places we need this are:
     flush_data_to_inode needs to lock the InoIdx block
       - DONE
     lafs_leaf_find as it recurses down.  This should return a locked leaf.
       - DONE
     callers of clear_index
         erase_dblock for depth=0??
       - DONE
     incorporate should lock new blocks for consistency 
       - DONE

   Locking dependency rule is that if we hold a lock, we are allowed to
   lock a child index block, but not a parent.  IF we hold a data block,
   we are allowed to lock the an index block.


  The read/write completion seems all wrong.  It unlocks if the page was locked,
   and that isn't really safe, because it might not have been locked for read..
   We need to flag block0 to say if lock or writeback need to be cleared.
   Given that, I don't need IOPending any more:
    Read: We submit all reads, then set 'do_unlock', then check if we should unlock.
    Write: We queue all writes, then set 'do_clear_writeback', then check.

  Now... can we use a writeback flag to avoid waiting to read while writeout
  is happening?  We would need:
     set writeback in cluster_allocate
     wait_writeback after some lock_block
     clear_writeback when writeout finishes.
     Extra checks where we already check for IOLock


24aug2009
 Lots of progress but....
   cluster_flush calls cluster_done calls refile call iput call
    drop_inode call write_inode_now calls writepage calls cluster_flush
  and we get a locking loop.
   I think we need the run that cluster_done from a different thread.


 We seem to have a refcnt problem with segsum.

25aug2009
 Lots more progress but.....

  orphan_release is finding that the orphan block has no credits.
  We can allocate credits and simply not do the update if they
  are not available:  having an extra entry in the orphan file isn't
  a problem.  However we need some mechanism to clean up other than
  waiting for a remount..
  I think we leave that until we redo orphan handling.

 and: adir sometimes loses one block so it and the contents don't get
   deleted.

 and: it seems we sometimes try to clean the segment being written
   to.  We must avoid that.

 (long ago I wrote::
  FIXME When pin fails, we need to remove PinPending from everything!!!
 and never followed up ... I wonder?
 )

25Aug2009
 Orphan handling.
  Every orphan block goes on a per-fs list and gets removed only
  if the B_Orphan bit is clear.
  There are two times when we want to expedite orphan handling.
  1/ on rmdir we need to know if the directory is really empty.
     This requires that we expedite the orphan handling of all
     blocks.  As soon as we find a non-orphan, we can give up.
     Then we need to make sure the index tree has collapsed.  WE
     can borrow that code from truncate.

  2/ When writing past Trunc_next.  We just pass the block to
     special orphan handling.

  This requires that orphan handling is re-entrant.
  For dir, that is protected by i_mutex, but rmdir needs to come
   in under the radar.
  For trunc, the iolock on the index blocks should be enough.
  I wonder if IOLock can be used on dir as well... allowing
  parallel orphan handling in the one dir even!!.

  We need to ensure exclusion of orphan handling, including:
      - only one orphan handler at a time
      - don't run orphan handler while still processing action
        that makes it an orphan.
  Maybe if we just use IOLock for that?  Does that work?  Maybe
  but it gets messy for directories (on first attempt anyway).
  For directories we can just use i_mutex.
  Maybe i_mutex for files as well?

27Aug2009
  Orphan handling is going well... but not perfect.
  I'm using IOLock to ensure exclusion for orphan handling.
  However:
    I'm not really implementing that on directories
    Inodes go bad because lafs_erase_dblock needs the lock too.
    The call from rmdir will always faile because we hold i_mutex.

  Bigger problem.  I'm IOLocking inodes across checkpoints to preserve
   Orphan status.  But that might stop the checkpoint proceeding.
   .. so use i_mutex, not IOLock - find.

  Now... it seems I've confused myself.  Orphans don't get handled
  immediately.  In particular, inodes should not be handled until
  they final delete_inode.  So setting the B_Orphan flag and putting
  on the list are two separate events.  The flag must come first,
  but the list may come much later.  So some of that mucking around
  with i_mutex is pointless.
  So:
    make_orphan makes sure it is in orphan file, sets bit, and removes
      from list (if present).
    add_orphan puts it on the list for handling.
 
    For inodes: lafs_new_inode sets the bit and delete_inode puts on queue,
        as does any unlink/rmdir/rename that fails.

    For directories: put it on list in commit/abort.


  And...
    I hit the BUG where find_leaf wants and address of 0.
      If an index block gets cleaned out it doesn't disappear
      immediately.. there is no leaf to find in that direction.
      We probably need to avoid non-Valid blocks or something...
  And...
    Orphans 0/299 to 0/329 and  0/280 are still on the list
     but are not orphans.
     Maybe I need to catch mutex_unlock to run the orphans??
  And...
    We underflow a segment through orphans are unmount.
      We are cleaning and truncating at the same time.
      The same block gets allocated to 0 and to 1225
      in quick succession.
      Problem is that we apply new address while in writeback
      so a new lafs_allocated_block

29Aug2009

  Review of inodes in orphan list:
    lafs_new_inode makes are orphan for a non-existant inode.
    If the inode cannot be created, orphan_release is called.
    If it can, a 'struct inode' is filled in with valid type
    and nlink==1 (!!) and attached.  The inode will only be
    detached when the refcnt hits 0, and the orphan list implies
    a refcount, so if we ever find something on the orphan list
    with a NULL my_inode, it must be very new and can be ignored.

    When we find an inode block with a my_inode there are a few options:
      if I_Trunc is set, we must progress truncation providing we can
            get the i_mutex
      else if I_Deleting we must delete the inode
      else if nlink is 0, we remove from the list
      else nlink > 0 and we must remove orphan status.
    This means that if nlink is elevated, we need to be holding the mutex...
    So don't elevate nlink any more...

    When nlink becomes non-zero the block need to be put back on the
    orphan list (it must already be an orphan).  Also when we set
    I_Deleting or I_Trunc it must go on the list.
   .. OK, I think I have all of that.


30Aug2009.
   I have some wierdness that seems to be caused by the orphan stuff,
   probably due to it all being async now.
   - A deleted inode clears I_Trunc and then sets it again.  The only
     explanation seem to be that delete_inode is being called again,
     so I must be igrabing it again, maybe from cleaning.
   - bits of directories aren't getting deleted.  Sometimes single
     blocks, though the referred files are deleted.  Sometimes
     the whole directory... More interestingly, those blocks then
     don't get cleaned, so something about them means that they
     don't get deleted and don't get cleaned either.

   Even weird... I just had a case where file 331 had a different
   index block for every 4 data blocks...


   FIXME:
    - What stops pinned blocks from being flushed by bdflush in middle
      of operation and so losing allocation?  Must make sure to set
      them dirty very late.
    - orphan_release can fail, so much make sure we can always call
      it, even if my_inode is NULL.... but how?


    - make_orphan could fail due to lack of space, which is not OK.
      I made it loop, but I'm not 100% sure that is right... it isn't.
      I need to pass down the 'I'm freeing space' flag, and I need to
      not require Credit of Dirty is set, etc.


    - I seem to have a deadlock and unmount.
       umount is waiting for lafs_checkpoint_lock_wait in
          lafs_put_super
       pdflush is in down_read in sync_supers
       lafs_cleaner is iget_locked/ifind_fast/inode_wait
                This is waiting for I_LOCK to be clear.
      

31Aug2009
  - When a file shrinks and becomes level-0, make sure
    old addresses get deallocated.  I seem to have
    a directory where they didn't.

  - Due to the fact that we over-preallocate, we really shouldn't
    return ENOSPC until we have flushed dirty data and performed
    a checkpoint??


  - When I removed the last index from an inode
    (Indirect type) it seems that I didn't write
    out the corrected block..??

1sep2009
 I ran my simple test run repeatedly overnight.
 It ran 208 times before I stopped it.
 There are 3 possible failure modes:
   1/ didn't completed within 500 seconds
   2/ triggered a BUG
   3/ appeared to complete, the number of blocks
      in use was not the correct '7'.

 74 (35%) did not fail!
 31 () did not complete
 40 () triggered a BUG
 2 did not complete but did not trigger a bug

 94 of those that failed did not have a BUG
 92 actually completed.  Of these:
      1 final blocks 1
      1 final blocks 110
      1 final blocks 23
      2 final blocks 12
      5 final blocks 0
      6 final blocks 10
     11 final blocks 8
     21 final blocks 11
     44 final blocks 9

 of the BUGs,
       1 BUG: sleeping function called from invalid context at kernel/nsproxy.c:217
      1 BUG: spinlock lockup on CPU#0, rm/1330, cfb2dae4
      1 kernel BUG at /home/neilb/work/nfsbrick/fs/module/block.c:485!
      1 kernel BUG at /home/neilb/work/nfsbrick/fs/module/cluster.c:1219!
      1 kernel BUG at /home/neilb/work/nfsbrick/fs/module/inode.c:821!
      2 BUG: soft lockup - CPU#0 stuck for 61s! [lafs_cleaner:1177]
      3 kernel BUG at /home/neilb/work/nfsbrick/fs/module/segments.c:1028!
      3 kernel BUG at /home/neilb/work/nfsbrick/fs/module/segments.c:351!
      5 kernel BUG at /home/neilb/work/nfsbrick/fs/module/lafs.h:276!
      6 kernel BUG at /home/neilb/work/nfsbrick/fs/module/block.c:529!
      7 BUG: unable to handle kernel paging request at 6b6b6bfb
     11 kernel BUG at /home/neilb/work/nfsbrick/fs/module/super.c:655!


 super.c:655 is "block is still pinned" at unmount time.
  The block was always an InoIdx with a child.
  Either inode 0 or 16.
  child is held by various things:
      [cfb555cc]16/1(2098)r131E:Valid,Async,SegRef,CN,CNI,UninCredit,PhysValid async(1) clean2(130)
      [cfb554f0]16/0(1050)r25E:Valid,SegRef,CN,CNI,PhysValid clean2(25)
      [cfa57c58]0/2(3676)r0E:Valid,Dirty,UninCredit,PhysValid
      [cfa5bc58]0/2(3110)r0E:Valid,Dirty,UninCredit,PhysValid
      [ce5b94f0]16/0(519)r1E:Valid,Async,SegRef,CN,CNI,PhysValid async(1)
      [cfb4d4f0]16/0(4249)r1E:Valid,Async,SegRef,CN,CNI,PhysValid async(1)
      [ce5ad4f0]16/0(612)r1E:Valid,Async,SegRef,CN,CNI,PhysValid async(1)
      [ce5c2fc8]0/74(0)r129E:SegRef,C,Claimed,PhysValid clean2(129)
      [cfa57c58]0/2(1895)r0E:Valid,Dirty,UninCredit,PhysValid
      [cfb4d5cc]16/1(4543)r105E:Valid,SegRef,CN,CNI,UninCredit,PhysValid clean2(105)
      [ce5754f0]16/0(1290)r178E:Valid,SegRef,CN,CNI,PhysValid clean2(178)

 The "unable to handle kernel paging request" is always in
 umount.
     invalidate_inode_buffers(26/46)/lock_acquire


 block.c:529
    This is iblock valid when erasing a block
    The block we are erasing is always 0/327 or 0/328.  It is
    an orphan we are handling, iolocked but not always pinned

 lafs.h:276
    Map an iblock which is not IOLocked
       always in lafs_clear_index for the InoIdx block for a directory
       which is in Writeback.
       Call is in lafs_allocated_block from cluster_flush.

 segments.c:351
    seg_inc reduces seg usage below 0
      - lots of blocks (inode 327) that were cleaned, where then erased twice.
      - 2 block (inode 328) were erased twice, both from prune
      - ditto

 segments.c: 1028
     The free list is empty.... odd as only first segment is currently
     in use.

 soft lockup:
     Still orphan: 0/328  Index(1) is in Writeback and Dirty
       again inode_handle_orphan2 is in Writeback

 inode.c:821
     inode_handle_orphan are end, child list is not empty.
       The children seem to be in Realloc - cleaner need to let go.

 cluster.c:1219
     my_inode is null while cluster_flush an inode and want to set
        WritePhase.


 block.c:485
     no ICredit for unincredit in dirty_dblock from dir_delete_commit
     from lafs_unlock.


 spinlock lockup in subsequent to real bug
 ditto for sleeping function.

 Of the '44' which claimed final blocks of 9, 14 really had 7, and 4
 appear to have other strange values....

 A select '9' has two extra block for the directory '74'.
 But that directory is long gone.
 These dir blocks are currently fully populated with numbers.
 This seems to be the pattern with all non-7 blocks.


 02Sep2009
  Found a problem, possibly related to the dir blocks not being
  cleaned up.
  When lafs_incorporate sets ->depth to 1 it doesn't dirty the inode,
  so that fact is never copied in to the datablock.
  On further exploration, the I_Dirty bit is set but never used, which
  isn't good.
  So: exactly when do we copy inode into datablock, and what do we do
  when dirty_inode is call (if anything).
  We could just set I_Dirty when dirty_inode is called, checking that
  the block is Pinned which it usually will be.
  Then we copy inode to data just before writing data block.
  However that defeats transactional properties.  We to copy in the
  same transaction, and that means either straight away, or when
  the data block's phase changes.
  So dirty_inode either copies to the block, or sets I_Dirty.
  When lafs_refile unpins an inode data block, it need to check
  I_Dirty and possibly re-dirty it.

  To redirty it we must steal the NCredits.  Any further dirty attempt
  will have to allocate more.
  The stealing is done automatically by dirty_dblock, so we just flip
  the phase and call dirty_inode ... making sure it doesn't try to
  prealloc too hard.

  Need to review when inodes get dirtied.
    - commit_write only sets I_Dirty !

    We call lafs_dirty_inode:
      dir_create_commit - a child of inode is PinPending
      lafs_create - ditto
      lafs_link - before dir_create_commit
      lafs_unlink, lafs_rmdir - data block is pinned
      lafs_symlink - before create_commit
      lafs_mkdir - before create_commit, or block pinned
      lafs_mknod - before create_commit
      lafs_rename - (moved to) before create_commit/update_commit
                     or data block is pinned
      lafs_dir_handle_orphan - (assured that) child is pinned.
      choose_free_inum - child is pinned
      lafs_incorporate - block is pinned

    So either the data block is pinned, or the index block is pinned.
    In either case it is OK to set something to Dirty.

    (the new) lafs_dirty_vfs_inode gets called by mark_dirty_inode{,_sync}
    this is called from:
        inode_inc_link_count
        inode_dec_link_count
        ..various quota ops...
        inode_setattr
        __set_page_dirty (Which we don't use)
        other buffer stuff
        other quota stuff we won't use
        touch_atime
        file_update_time
        page_symlink

    only the time updates are interesting.  Others we have locking
    for.
    file_update_time is called from generic_file_aio_write_nlock etc
    before ->prepare_write/->commit_write.  So they can pick up the
    change.
    Similarly before set_page_dirty is called.
    touch_atime is called from do_follow_link and readlink and
    file_accessed which is called all over the place.

    So what to do?
    If block is pinned, then dirty it to ensure writeout.
    If not, don't.  But copy data in any case.


4sep2009

    OK, I've decided that I don't like clearing B_Valid when an index
    block contains no indexes.  The final straw was that I seemed
    to need to initialise the index block when I didn't hold IOLock.
    That was probably fixable, but I'm sure more problems were coming.

    So: what to do instead?
    One issue that must be resolved is that an index block can still
    have valid children even when it become empty.
    This can happen if we erase blocks from a file, then add them back
    after a checkpoint, and so in the next phase.
    The checkpoint writeout could need to show an empty index block,
    but the next phase will see real addresses.
    We cannot easily avoid this, so we must handle it.
    This interact badly with the index lookup algorithm that finds
    the best index block currently in the parent, and then scans
    the children.  If there is no index block in the parent, we
    cannot find any children.
    This could be handled by responding to an empty index block by
    scanning all children.  But that isn't a full solution as if
    just one index block got erased, it's unincorporated siblings
    would still be lost.
    We could treat empty index blocks like orphans.  i.e. don't
    discard them immediately but leave them with possibly real
    addresses.  Then when they have no children we allocate the
    0.
    But we still need to ensure that index blocks off which siblings
    have been split but not yet incorporated remain present in the
    tree to mark the place for their siblings.
    There is another problem.  A horizontal split could leave the
    new block with no addresses and everything in the uninc list.
    Nothing can be found in there.

    So maybe we need to revise the lookup mechanism.
    The goal is to find an index block that starts at or before
    the target and contains an address at or after the target.
    Then out search can stop.
    In rare cases.....

7sep2009
    I thought about this more over the weekend and think I have an answer.
    We need to treat internal and leaf index blocks somewhat differently.

    An internal index block must never be empty (while unlocked).
    Any child block which has not had it's address incorporated must be 
    attached (simply in the sibling list) to a block which has been
    incorporated.  This will be the block that it was split off.
    The uninc block needs to hold a reference so that the primary isn't
    released.
    When a 'primary' becomes empty it cannot be discarded, so the
    addresses in the first dependent index block must be copied
    across.  This is awkward for indirect blocks so they might be
    allowed to be empty (they aren't internal so don't violate the
    above).
    When a horizontal split break a sequence of dependent blocks
    between two parents, the second parent must be incorporated
    immediately so that the first block in the second half of the
    sequence is incorporated.
    If an internal index block does become empty and it has no
    dependent blocks to fill from, it must be invalidated immediately.
    It cannot have any children - even in next phase - as at least one
    would have to be incorporated and so the block would not be empty.
    Invaliding involves allocating to address 0.
    If index lookup finds a block with PhysValid address of 0, it
    must look to the previous index block.  If there was none .... it
    gets a bit complex.

    Leaf index blocks can become empty, but we try to avoid it.
    If a leaf has blocks which have been created in the next phase,
    and others which have been deleted in this phase, it can be empty
    but still have children.  In this case we just treat it as a real
    index block that doesn't actually have any addresses.  We still
    write it out even though that is a waste of space.

    We have been working on the assumption that every address always
    has a corresponding leaf index block.  It is the leaf with the
    highest index at or below the target address.
    However this requires the every internal index block has a child
    with the same address as the parent.
    Preserving this requirement when the first child of an internal
    become empty requires either:
       - loading the 'next' child and reassigning this to the start
       - changing the address of the parent to match the first child.
    The former requires possibly reading a block from storage.
    The latter only involves modifying blocks that are due to be
    written out anyway, but makes block look up slightly interesting.
    When lookup finds an invalid block that is 'first', it needs to
    start again from the top.
    When incorporation creates an invalid block that is first, it
    needs to walk down from the top and any index block at the same
    address needs to be relocated/rehashed.  If the block is
    incorporated, the incorporated address needs to be updated.
    So:
     - flag for unincorporated index blocks which implies a reference
       on primary
     - after split, immediately incorporate second block
     - change lookup to retry when finding invalid block
     - When internal block becomes empty, either merge with
       first dependent or invalidate.  If first in parent,
       update address and parent and recurse.
       Need some 'clever' locking here.
       Before unlocking the invalidated block, we take i_alloc_sem,
       then walk up the ->parent tree locking blocks as
       required.
       The index lookup, when it finds an invalid block will take
       i_alloc_sem, then drop it, then start again.
       Or maybe some other lock than i_alloc_sem...
     - When leaf becomes empty, invalidate only if it has no children.
       When internal leaf becomes unpinned, check if empty.

21sep2009
   That locking doesn't look like it will work, and we can never 'merge
   with first dependant' as it is not valid to have a index block
   where the first child is at a different address.
   And we cannot always change the parent address, particularly if it
   is zero - increasing it then cannot work.
   And there is no need to load a block if we are just going to change
   its start address (not internal index blocks anyway).
   Let's drop the idea of relocating the parent.
   If an internal index block becomes empty:
     If it is last in parent, no loss, just discard
       If parent would be empty, need to recurse up.
     If it is not last relocate the next sibling to this location,
      rehashing it and updating the parent.
   If a leaf index block becomes empty we cannot just delegate to
      next as it might be indirect... not a problem if address is
      stored.  But that requires a format change... now might be a
      good time!
   
   
   So:
     If we hold an index block locked and it becomes empty and we choose
     to invalidate it, we need to ensure that doing so does not
     break any indexing paths.
     So we take a separate lock (i_alloc_sem??) and flag the block as invalid
     by setting physaddr to 0 while PhysValid is set, and unlock the block. 
     Any lookup that finds such a block must take and release i_alloc_sem,
     and then restart from the top.
     - If the block was not incorporated, we just remove from sibling list
          and all is done - the space in implicitly included in
          previous block.
     - If the block has a different fileaddr than the parent then update
          the parent directly, either removing the entry, or changing it to
          point to the first unincorporated sibling (if there is one).
          This requires taking the lock on the parent of course.  That is 
          why we dropped the lock on the child.
          Then all done.
     - If the block has the same address as the parent we need to find
          a 'next block' to relocate to the start of the parent.
          It is either the first unincorporated sibling, or the next
          block in the index block, or nothing, meaning the parent is
          about to become empty. 
        We lock the parent (still holding i_alloc_sem), and rehash the
          chosen child.  If it doesn't exist, or is not dirty, we need
          to update the phys address directly in the 
          accordingly, erasing or replacing the first address.
          Then we need to rehash the index block, but we need to lock
          the parent for that.
          So set a 'busy' flag on the block, unlock it, lock parent,
          rehash, clear busy flag, and repeat.
      - We can never relocate a block with fileaddr of zero, as the
          InoIdx block cannot be relocated.  So leaf index block 0
          must never be erased unless the file is empty.  So 

28sep2009
  New idea.
  We store the start address of an indirect block in the block.
  These means that the meaning of any index block is completely
  independent of the location of the block, so we can change the location
  easily and without touching the block.
  So if a block becomes empty, we simply move the next block back to
  fill the gap.
  i.e. when an index block becomes truely empty (i.e. no children)
   - if it wasn't incorporated, simply remove it
   - if it was,
       - if there is a dependent block, rehash it to take my address
       - if there is a next block that is dirty, rehash it
       - if there is a next block that is not dirty,
          update parent to merge my entry with next, and rehash next
          if it exists
       - if there is no next block but we are not first, just update
          parent
       - if no next block and we are first, parent becomes empty,
          recurse upwards.

12Oct2009
 - too long, I've forgotten what I was up to..
   + I've changed the format of indirect blocks to store an address.
   + I've handled incorporation of an empty block
   So now internal index blocks can never be empty - they get immediately
   unlinked if they are.
   Leaf index blocks can be empty while they have children.  We don't
   flag them as empty, but rather wait until another child gets incorporated.
   But I don't think I really like that.  It is an external ugliness based
   entirely on internal implementation details.  Empty index blocks should
   not get written out.  We need some way to reliably find an empty index
   block.  The address won't appear in the parent so a lookup will find the
   previous block which we cannot link to now as it may not exist yet.
   Worse - if first index block goes empty, we can only unlink it by moving
   the parent to start at the next block.  That would make this index block
   totally unfindable.
   So I think we have to stick with writing out empty index blocks very
   rarely.  So we need to be sure they disappear properly.
   The difficult case is if an index block becomes empty while it has some
   children which don't end up getting dirtied. e.g. an update aborts.
   We need to leave the block with enough credits to be written out.
   I guess the Ncredit should be enough...
   Maybe worry about that later.

 - what about InoIdx blocks when they become empty?  It would be helpful
   to flag them so that inode deletion can check....
   Maybe just set depth to 0..

 ARRGGG... I've completely lost it.  In need another ITO week.
  I just got a bug in summary.c:71!!

7 Jun 2010
 - summary.c:71.
   ablocks_used has hit zero too soon.
   This should be the count of blocks for which space has been allocated
   (B_Prealloc is set) but have not been given a phys address yet - at which
   point the usage count is moved to cblocks_used or pblocks_used.
   The last block (which may not be the cause of the problem) does not have
   B_Prealloc set, yet physaddr == 0.
   The block is 0/1, so the inode for the inode usage map.  This should have
   physaddr 8 !!
   We did find 8, then change to 73, but then changed to 0!
  Ahhh... recent fix exposed a subtle bug ... fixed.

 Now cluster.c:619: [ce9233f8]0/282(0)r2F:Pinned,Phase1,PinPending,CN,CNI,Claimed,PhysValid iblock(1) leaf(1)
     cluster.c:619: [ce570a18]0/286(0)r2F:Pinned,Phase1,PinPending,SegRef,CN,CNI,Claimed,PhysValid iblock(1) leaf(1)
   We are allocating an InoIdx block, but data block is not valid??