README update

[LaFS.git] / inode.doc

Creating a file:
We create a file separately from creating a name.
We create an orphan entry to ensure that the
file gets cleanned up after a restart if no
name exists.

The commit for a file creation involves
 - writing an update block for the inode
The checkpoint for file creation involves
 - clearing the bit in the inode bitmap
 - recording the inode as an orphan
 - writing the inode block.

We need to allocate the inode number outside the 
checkpoint lock (do we?) but clear the bit inside.

To avoid races implicit in this (the threads allocate
a inum before either clear the bit) we keep track of the 
last allocated inode number to avoid quick reallocation.
We guarantee exclusion by flagging the inode when
we create it... or something. More later


Hmmm... this isn't inode specific but:
 The update block must be written, or scheduled
at least, in the same checkpoint which holds
the transaction.
The means we have to write the update inside 
a checkpoint lock... but how long can we wait?
Maybe we want a 'update-and-lock' operation..
No. just pre-allocate/lock/commit as with everything
else.
So we want to be able to pre-allocate log space.
How does that work?  We cannot block writes until
the space is used...  What are we really preallocating?

This is like locking a block.  We need to be sure there
is enough space in the log to write it. and we keep
that buffer between us and 'full' until the write happens.
If there are lots of concurrent reservations, that
decreases the free space we have to work with and
pushes checkpoints more often.
The 'reserve' will block until there is enough free
space to allow it, either because space has been returned,
or has been freed up by a clean/checkpoint.

Uhm... no.  Something wrong here.
Sometimes we want to lock a block and wait if there isn't
enough room. But we cannot wait while we have a checkpoint lock.
So we need to lock outside the checkpoint lock.  But currently
we don't think that is OK for data blocks.
Why? because they might be written to early?
Index blocks stay permantently locked while they have
a dirty or otherwise active child.  They get written iff
they are dirty.
Datablocks should stay locked until the refcount hits zero.
So we lock them outside the checkpoint, which reserves space
etc.  when a checkpoint happens it gets written if it is dirty.
So it goes like this:
  - lock the block getting all reservations needed
  - take checkpoint lock
  - wait for block to be clean or in this phase
  - update block
  - mark block dirty.

Block stays locked while there is a ref count.

See writeout.doc - I revised the above.

---------------------------------------------------
When is the in-core inode flushed into the datablock?
For regular file metadata (mode, owner etc) this probably
isn't important as there are no interdependancies.

For internal metadata such as
 - head for directory btree
 - start of directory free-list
 - size of inode map block
this is important and the related block changes much happen
in the same checkpoint.
I suspect we need a phase number that get set when
the inode is synced to the block.  This can be 0, 1
or unset.
When flushing causes an inode to be written, if the 
phase number is set to the next phase, we skip the
sync, otherwise we sync and clear the phase flag.

When we want to write something that has to be in this phase,
to first check the phase flag,  if it is set to the wrong phase,
we sync incore to block. Then we set the flag and update incore.

----------------
When ->write_inode is called, we only want to write non-structural info.
This is the section of file metadata from flags to atime.


So:
 mark_inode_dirty
   checks that the block is locked.  It must be
     as we only call this after something that has
     had a chance to lock, or fail.
   copies info into the buffer
   marks the block dirty

write_inode just writes a commit record if mark_inode_dirty has been called.
If a commit record cannot be allocated, force a checkpoint.

Checkpoint will write out the whole inode eventually.

Size updates use a different commit system.

Hmmmm... 
 If we are doing a checkpoint, and this inode hasn't been writen in the
 old phase yet, then we cannot copy data from inode to block.
 So we mark the inode as dirty. When phase flips, if it is dirty, we copy
 info
-----------------------------
Whenever we update metadata in an inode, we immediately
(via ->dirty_inode) sync it with the block buffer, unless
that is still in the old phase, in which case we flag the inode as
dirty so that after a phase change, it get's synced.


-----------------------------------------------

When an inode is deleted, we need to preserve the inode until
truncation is complete, then clean everything up.
This means that our destroy_inode should not actually destroy it,
but rather mark it so that when the InoIdx block goes away, the
inode is destroyed.
But we need to be careful of inode number reuse... 

So: when a file in finally deleted (lafs_delete_inode) we need to:
 - release all the data pages - this is really just updating lots of
   segment usage counts.
 - create a hole in the inode file
 - set the bit in the inode usage map
This should be done without waiting in lafs_delete_inode, which means
that lafs_destroy_inode should not free the inode if it is being deleted.
The truncation will happen from the 'orphan handler' thread.
We need an I_Flag for "Deleting".  If set, destroy won't free it but
instead will set I_Destroyed.
When the hole is created and the datablock is freed, we clear
Deleting and then if Destroyed is set, we free.


Deleting an inode is committed by the unlink that removes the last link.
This makes it an orphan.  It stays an orphan until truncate finishes with it.
So lafs_delete_inode just starts the truncate process.
It sets trunc_next to 0.  Then trunc_next become MAX we can tear down
the index tree, set the inode_map bit, and set the data block to be a Hole.

EEKK delete needs lots of thought/work.

As the inode has just been changed, it might be dirty etc.  We need to
wait for the index block to naturally get clean up before throwing it
away and creating the hole etc...
So: how do the data block, then index blocks, get dealt with.
Need to understand both nondelete and delete dropping of an inode.

inode holds a reference on the dblock.  It needs to be able to drop
that when it is clean etc...

The key issue here is blocks disappearing from the index tree.
 - Datablocks are removed when their refcount becomes 0, and they are clean.
   truncate_pages should achieve this easiy.
 - Index blocks are removed as they too become clean.  This should also
   happen promptly, though the truncate operation will need to find all
   of them eventually.
 - The InoIdx block is referenced from the inode so won't go away in a hurry.
   But really, the reference from the inode should not stop the parent link
   from going away.  Maybe that reference should be counted differently.
   Maybe the iblock/dblock references shouldn't be counted at all.
   When the inode is dropped, we drop the reference from the dblock
   When the dblock is dropped, we clear the reference from the inode.
   ->my_inode->dblock
   InoIdx: ->inode->iblock are loops.

So flushing or checkpointing after truncation should result in all index
blocks being allocated, found empty and a Hole Punched.
So for Index blocks, we run incorporation and if it is empty, we might punch
a Hole.  For the InoIdx block we only punch the real hole if I_Deleting.

butbutbut can we drop ->dblock?   A: only when the inode is clean and not pinned.
So: how does deletion work?
  We mark the inode as an orphan (Should already have happened), set
  the "trunc_next" pointer to the start of the file and schedule the
  orphan handler. This ultimately allocates some 0s to the InoIdx block
  in which incorporation makes it dirty.
  This needs to be detected in incorporate and instead of the inode being
  written out, we punch a hole in the inode file and set the inode-available bit.

  We write out the inode map update in the same checkpoint that the
  delete starts.  Until the delete completes, the inode will have B_Claimed set
  so that others won't try to use the same inode number.


--------------------------------------------------

The duplicity of the inode index block and data block is becoming a bore.
We need to often update them both which is awkward.
And getting from one to the other is awkward.
But we need them to be different because:
  1/ they contain different sorts of information
  2/ When an indexing tree grows, we need a new InoIdx block but not new data
  3/ ...
Maybe we just need clearer rules on what gets updated when.
Currenty uglinesses include:

  cluster_allocate
        skip data block if InoIdx is pending
        use datablock when trying to do indexblock
  
  cluster_done
        clear B_Alloc on InoIdx when clearing on data

  cluster_flush
        clear Dirty on InoIdx when clear  on data

  lafs_refile
        don't clear Pinned on data when InoIdx is pinned
        only put date on phase_leafs when index not pinned
      ??Destroy inode when data block gets freed (need better test)

  inode_fill
        need to dirty both blocks

  pin_iblock
        also pins dblock for an inode

  phase_flip
        also flips dblock phase
  make_iblock
        copy Dirty flag across


An issue is that we need to keep the flags correct so that 'Pinned' and 'parent'
etc hang around as required.

An ugliness is that normally data blocks don't flip-phase. The just drop out and
maybe get pinned again in the next phase.
But inode datablocks seem to need to.  Maybe they shouldn't.
Maybe the InoIdx being pinned should be enough.  While it is pinned it holds
a reference on the data block(??) and when we want to force a write, we pass
credits over to data block.. We could set Alloc and clear Dirty on InoIdx then
start processing the data block.

HMmm... maybe just tidyup the code, and leave the functionality as it is.

----------
When a file is small, the data is in the inode.
The InoIdx block is still an index block though, and there is a separate
data block which the data gets copied into.
So the one data block is a child of the InoIdx block which is a twin of the
inode data block.
When the file grows and the inode must contain real information, we simply update
the content of the inode to be index info and make sure to write out the
new data block.
When the file grows again, the InoIdx block must be demoted to a regular
Index block, and a new InoIdx block created to parent that Index block.
As the InoIdx block doesn't have it's own buffer, it must steal the buffer from
the new block that will become the new InoIdx block.

-------------------------------
Block usage.

The Inode on disk records 'data_blocks' and 'index_blocks' which record
how many blocks are in the index tree below the inode.

The in-memory inode records:
   cblocks.  This counts the number of blocks of the inode we flushed out
        now.  It includes all blocks stored plus any that have been allocated
        to disk as new blocks in the current phase.
        It is also reduced when "holes" are registered for incorporation.
        They are "committed" blocks.
   pblocks.  This counts changes that have been registered for incorporation in
        the *next* phase.  On a phase change, pblocks is added to
        cblocks, and zeroed.
        They are "phased" blocks.
   ablocks.  This counts new blocks that have been dirtied but have not yet
        been registered for incorporation - i.e. they haven't been written
        to storage.
        They are "allocated" blocks.
        We add to ablocks when we set B_Prealloc on a data block with physaddr==0
        we remove from ablock when we clear B_Prealloc on such a block
        we also remove when we set physaddr - prealloc must be set

So:
   'cblocks' is loaded from the inode, and written out.
   When a block which didn't have an address is "lafs_allocated_block"
   with an address, then we increment 'cblocks' or 'pblocks' depending
   on whether the index block is in-phase with the inode.
   We also decrement 'ablocks'.
   When we dirty a block with no physical address, we increment 'allocated'.
   When we remove a block (lafs_allocated_block with phys==0) or otherwise
   in truncate, we decrement 'cblocks' or 'pblocks', and also 'ablocks'
   if the block was dirty but had phys=0 already.


   For index blocks, we similarly have ciblocks and piblocks.
   No aiblocks is needed as we don't pre-allocate index blocks.

   The value returned for getattr is the sum of cblocks, pblocks, ablocks.
   I wonder if ciblocks and piblocks should be added.
   The counters are protected by .... i_lock

   We need to implement this in:
      lafs_allocated_block
      lafs_dirty_dblock
      hole handling
      truncate

---------------------------------------
InoIdx and Data - when is which dirty?

Currently when we try to dirty an inode data block, we actually
  dirty the InoIdx block instead if it exists.  And is pinned.
  But I'm not sure that is correct.
 In cluster_allocated we don't handle a non-pinned inode data block
   if the InoIdx block is Pinned  to the same phase... which doesn't
   make sense because the data block isn't pinned.
 but when the InoIdx block is ready, we pin the data block which allows
 it to be written...

 There are two times when we want to write an inode block.
  1/ when writepage writes an embedded page 0.  In this case there are
   no other index blocks to be pinning the InoIdx.  So when the data
   block is successfully allocated we should immediately allocate
   the inoidx and thus the data, clearing all the 'Dirty' bits.
  2/ when a checkpoint gets to it.  The InoIdx will be pinned but the 
   data block not.  Once we allocate the InoIdx, that will 'pin' the
   data block so it will then be processed.

  If we perform metadata operations on an inode while no inoidx is present
  (as no data is being accessed) we want to Pin the data block to ensure it
  gets written... Or we could just write it and ensure roll-forward picks up
  the right bits.
  In that case an inode block is just like any data block.  We make changes
  and dirty it.  Eventually it gets written.  It can be pinned if we want,
  but there is no point pinning it if the InoIdx is pinned to the same phase.
  Roll-forward must pick up all content except index information.

  Mark_inode_dirty is called for atime, ctime, size...
  Most of those we can control and see, just not atime.
  So only really write the inode if we know of an important change...

So:
  An inode-data-block can be dirtied:
   - in flush_data_to_inode when we copy from block 0
   - in lafs_cluster_allocate when the index block is being allocated
   - in lafs_inode_init
   - in lafs_inode_fillblock
   - in inode_map_new_commit ???  No needed, init does it already.
  An InoIdx block can be dirtied:
   - in lafs_dirty_dblock when dirtying the data block - don't do this!
   - prior to incorporating changes or adding addresses
          i.e. before lafs_add_block_address

  If a db is pinned while the ib is pinned to the same phase, drop
   that pinning, it isn't needed.
  When an ib is allocated, pin the db and make sure it is dirty.

  Writepage on an inodefile page should fail if any inodes have pinned
  InoIdx.  Otherwise it can succeed.