Vcb free block counter

[oneilljos]

vcb will know how many free blocks it has

[bhelabhav]

Update:
We want this because in vfs_write we want to be able to quickly check if we have enough space for the file. Currently we are reading the next data block (1 disk access) from disk and writing a data block there (another disk access). If we run out of space in this process we end up rolling back and rewriting the free block (another disk access). If there were N free blocks available and M data blocks that need to be written and M > N, then we do 3N disk accesses just to say we don't have space.

At a minimum, if we did have enough space, so M <= N, we have 2 * M disk accesses.

Let's consider the possible scenarios and how our current implementation (CI) vs. the free block counter implementation (FBI) would fare. We only consider the functions that would add free blocks or delete them.

1. Many file creations. CI performs the same as FBI.

   CI: reads vcb (1 disk access). We write an inode block to that block num (0 or 1 disk accesses,
   depending on if there is another free block), and update the vcb block next free blocknum (1 disk
   access).
   Worst case: 3 disk accesses

   FBI: reads vcb (1 disk access). We write an inode block to that block num (0 or 1 disk accesses,
   depending on if there is another free block), and update the vcb block next free blocknum and
   decrement free block counter by 1 (1 disk access).
   Worst case: 3 disk accesses

2. Many file deletions. CI performs the same as or worse than FBI.

   CI: Determine if a file exists. (X disk accesses; varies if we have a cache)
   If it does, we rewrite the inode block and all associated data blocks as free blocks. (Y disk
   accesses).
   Determine if we have enough space. (3N disk accesses if we don't or 2M disk accesses if we do)
   Update vcb. (SHOULD only be once but I believe it is Y disk accesses; there may be another
   optimization if we are always updating the vcb for each block we free; we could, technically, only
   update it once with the last block we free.)
   Worst case (if there is enough space): X + 2Y + 2M
   Worst case (if not enough space): X + 2Y + 2M + 3N

   With the addition vcb optimization:
   Worst case (if there is enough space): X + Y + 2M + 1
   Worst case (if not enough space): X + 2M + 2

   FBI: Determine if a file exists. (X disk accesses; varies if we have a cache)
   If it does, we rewrite the inode block and all associated data blocks as free blocks. (Y disk
   accesses)
   Determine if we have enough space. (1 disk access if we don't or 2M disk accesses if we do)
   Update vcb. (SHOULD only be once but I believe it is Y disk accesses; there may be another
   optimization if we are always updating the vcb for each block we free; we could, technically, only
   update it once with the last block we free.)
   Worst case (if there is enough space): X + 2Y + 2M
   Worst case (if not enough space): or X + 2Y + 2M + 1

   With the addition vcb optimization:
   Worst case (if there is enough space): X + Y + 2M + 1
   Worst case (if not enough space): or X + 2M + 2

3. Many file writes. CI performs the same as FBI.

   We already update the VCB. (so we just update the count at the same time)

4. Many file truncations. CI performs the same as FBI.

   We already update the VCB. (so we just update the count at the same time)

For all of these optimizations we need weight the level effort it will require and how much effort we can dedicate. Make the better optimizations first.

Of course before making any of these optimization we should first ensure our solution is correct (i.e. we should write more malicious test cases).