File and directory content is stored in disk blocks, which must be allocated from a free
pool. xv6s block allocator has a bitmap block on disk. It contains one bit per block. ’0’
bit indicates that the corresponding data block is free whereas ’1’ bit indicates that it is
in use. The bits corresponding to the boot sector, superblock, inode blocks, and bitmap
blocks are always set to ’1’. [12]. The current block allocator in xv6 file mechanism uses
two functions: The first one is balloc it is used to allocate a new data block on disk,
and second one is bfree which is used to free a data block. Balloc calls readsb to read
the superblock from the disk or buffer cache into sb. balloc calculates which blocks in
filesystem contains datablocks considering the size of boot sector, the superblock and the
inodes. This is found by macro BBLOCK. Then it finds out the new potential block that
can be used for allocation. This is achieved by finding out the data block entry from
bitmap block whose bit is set to ’0’. If it finds such a block, it updates the bitmap and
returns the block. The issue of contention arising from two processes trying to access
same block on disk is resolved by buffer cache mechanism. It is required for any process
to acquire filesystem lock before accessing disk. So at a time only on block can access
the disk. Similaraly when a file is deleted or truncated Bfree find the right entry in the
bitmap block and clears the bit.
The original ondisk inode structure struct dinode contains a size and an array of block
numbers. The inode data is found in the blocks listed in the dinodes address array. The
first NDIRECT blocks of data is found at the blocks whose block number is mentioned
in first NDIRECT entries of that array. These blocks are called direct blocks. The next
blocks of data are not listed in the inode but in a data block whose address is stored in
another block called as Indirect block. The last entry in the address array gives the
address of such indirect block for xv6 filesystem. Thus the first 6 kB (NDIRECTBSIZE)
bytes of a file are stored in the blocks listed dinode address array in the inode, while the
next 64kB (NINDIRECTBSIZE) bytes are stored only after direct blocks are completely
filled.
So while changing the current structure, in extension to the current data block struc-
ture we have added one more NDINDIRECT block to current inode structure. Each entry
in this block represents block address of another block. Each entry of such blocks gives
address of another block which actually stores data. Now the main task is to allocate
blocks from this entry. This is handled by modified block allocation strategy explained
in following section. See Appendix F for further detail.
The function bmap manages the representation of the on-disk filesystem and it’s inmemory counterpart. So that higher-level routines such as readi and writei can interact with in memory inode structure. Bmap returns the disk block number of the data block for the inode I. If I does not have such a block yet, bmap allocates one. The function bmap begins by allocating the first NDIRECT blocks are listed in the inode itself. The next data blocks are listed in the indirect block at I.addrs[NDIRECT] entry in that inode’s memory structure. Bmap finds out the indirect block and then reads a block number from within the block. If the block number is not below NDIRECT+NINDIRECT, because of new changes in filesystem now it will track that data block in I.addr[NDINDIRECT].. Hence it gives filesystem wider length. See Appendix F for inode structure.