文章大部分内容参考《操作系统:设计与实现》。整个文件系统结构如图所示:
当普通文件或目录文件需要扩充的时候,需要为其分配新块,那么就会调用new_block()函数。此函数位于/src/fs/write.c中。
此函数如下所示:
PUBLIC struct buf *new_block(rip, position)
register struct inode *rip; /* pointer to inode */
off_t position; /* file pointer */
{
/* Acquire a new block and return a pointer to it. Doing so may require
* allocating a complete zone, and then returning the initial block.
* On the other hand, the current zone may still have some unused blocks.
*/
register struct buf *bp;
block_t b, base_block;
zone_t z;
zone_t zone_size;
int scale, r;
struct super_block *sp;
/* Is another block available in the current zone?
* 根据文件位置去读已经分配了的区段,看看区段中是否未分配的数据块。一个区段包含1,2,4,8
*个数据块,具体包含几个要看文件系统的设计,这一版本应该是包含一个数据块。如果已分配的
*区段中没有数据块,则分配一个新的区段。
*/
if ( (b = read_map(rip, position)) == NO_BLOCK) {
/* Choose first zone if possible. */
/* Lose if the file is nonempty but the first zone number is NO_ZONE
* corresponding to a zone full of zeros. It would be better to
* search near the last real zone.
*/
if (rip->i_zone[0] == NO_ZONE) {/*如果文件从未分配区段,则从超级块中标识的第一块开始*/
sp = rip->i_sp;
z = sp->s_firstdatazone;
} else {
z = rip->i_zone[0]; /* hunt near first zone,以第一个分配的区段为参考 */
}
if ( (z = alloc_zone(rip->i_dev, z)) == NO_ZONE) return(NIL_BUF);/*分配区段*/
if ( (r = write_map(rip, position, z)) != OK) {/*将新分配的区段写入目录*/
free_zone(rip->i_dev, z);
err_code = r;
return(NIL_BUF);
}
/* If we are not writing at EOF, clear the zone, just to be safe.
* 根据区段和文件偏移求的其数据块块号
*/
if ( position != rip->i_size) clear_zone(rip, position, 1);
scale = rip->i_sp->s_log_zone_size;
base_block = (block_t) z << scale;
zone_size = (zone_t) BLOCK_SIZE << scale;
b = base_block + (block_t)((position % zone_size)/BLOCK_SIZE);
}
bp = get_block(rip->i_dev, b, NO_READ);/*取得数据块*/
zero_block(bp);
return(bp);/*返回内存中的数据块缓冲区指针,用户接下来这数据块进行存储等操作*/
}
分配一个新的区段通过调用函数alloc_zone()完成,具体如下:
PUBLIC zone_t alloc_zone(dev, z)
dev_t dev; /* device where zone wanted */
zone_t z; /* try to allocate new zone near this one */
{
/* Allocate a new zone on the indicated device and return its number. */
int major, minor;
bit_t b, bit;
struct super_block *sp;
/* Note that the routine alloc_bit() returns 1 for the lowest possible
* zone, which corresponds to sp->s_firstdatazone. To convert a value
* between the bit number, 'b', used by alloc_bit() and the zone number, 'z',
* stored in the inode, use the formula:
* z = b + sp->s_firstdatazone - 1
* Alloc_bit() never returns 0, since this is used for NO_BIT (failure).
*/
sp = get_super(dev); /* find the super_block for this device */
/* If z is 0, skip initial part of the map known to be fully in use. */
if (z == sp->s_firstdatazone) {
bit = sp->s_zsearch; /*使用超级块指向的第一个未分配的区段位图*/
} else {/*使用当前文件的第一个区段与超级块所指向的第一个未分配区段 之间的偏移*/
bit = (bit_t) z - (sp->s_firstdatazone - 1);
}
b = alloc_bit(sp, ZMAP, bit);/*此函数主要通过调用alloc_bit()函数来完成*/
if (b == NO_BIT) {
err_code = ENOSPC;
major = (int) (sp->s_dev >> MAJOR) & BYTE;
minor = (int) (sp->s_dev >> MINOR) & BYTE;
printf("No space on %sdevice %d/%d\n",
sp->s_dev == ROOT_DEV ? "root " : "", major, minor);
return(NO_ZONE);
}
if (z == sp->s_firstdatazone) sp->s_zsearch = b; /* for next time */
return(sp->s_firstdatazone - 1 + (zone_t) b);/*通过查找到的位图 返回区段号*/
}
alloc_bit()函数如下所示:
PUBLIC bit_t alloc_bit(sp, map, origin)
struct super_block *sp; /* the filesystem to allocate from */
int map; /* IMAP (inode map) or ZMAP (zone map) */
bit_t origin; /* number of bit to start searching at */
{
/* Allocate a bit from a bit map and return its bit number. */
block_t start_block; /* first bit block */
bit_t map_bits; /* how many bits are there in the bit map? */
unsigned bit_blocks; /* how many blocks are there in the bit map? */
unsigned block, word, bcount, wcount;
struct buf *bp;
bitchunk_t *wptr, *wlim, k;
bit_t i, b;
if (sp->s_rd_only)
panic("can't allocate bit on read-only filesys.", NO_NUM);
if (map == IMAP) {/*分配 i 节点位图*/
start_block = SUPER_BLOCK + 1;
map_bits = sp->s_ninodes + 1;
bit_blocks = sp->s_imap_blocks;
} else {/*分配区段位图*/
start_block = SUPER_BLOCK + 1 + sp->s_imap_blocks;/*区段位图起始数据块*/
map_bits = sp->s_zones - (sp->s_firstdatazone - 1);/*目前还剩的区段位图个数*/
bit_blocks = sp->s_zmap_blocks;/*区段位图所占用的数据块数*/
}
/* Figure out where to start the bit search (depends on 'origin'). */
if (origin >= map_bits) origin = 0; /* for robustness */
/* Locate the starting place. */
block = origin / BITS_PER_BLOCK;
word = (origin % BITS_PER_BLOCK) / BITCHUNK_BITS;
/* Iterate over all blocks plus one, because we start in the middle. */
bcount = bit_blocks + 1;
do {/*循环查找空闲位*/
bp = get_block(sp->s_dev, start_block + block, NORMAL);
wlim = &bp->b_bitmap[BITMAP_CHUNKS];
/* Iterate over the words in block. */
for (wptr = &bp->b_bitmap[word]; wptr < wlim; wptr++) {
/* Does this word contain a free bit? */
if (*wptr == (bitchunk_t) ~0) continue;
/* Find and allocate the free bit. */
k = conv2(sp->s_native, (int) *wptr);
for (i = 0; (k & (1 << i)) != 0; ++i) {}
/* Bit number from the start of the bit map. */
b = ((bit_t) block * BITS_PER_BLOCK)
+ (wptr - &bp->b_bitmap[0]) * BITCHUNK_BITS
+ i;
/* Don't allocate bits beyond the end of the map. */
if (b >= map_bits) break;
/* Allocate and return bit number.分配空闲并合法的位 */
k |= 1 << i;
*wptr = conv2(sp->s_native, (int) k);
bp->b_dirt = DIRTY;
put_block(bp, MAP_BLOCK);
return(b);/*返回分配的位的索引值*/
}
put_block(bp, MAP_BLOCK);
if (++block >= bit_blocks) block = 0; /* last block, wrap around */
word = 0;
} while (--bcount > 0);
return(NO_BIT); /* no bit could be allocated */
}
将新分配的区段插入目录,调用函数write_map(),插入目录时,如果当前目录所使用的目录条目已经用完,则也需要为其分配新的目录块,即数据块。该函数如下,这里就不注释了:
PRIVATE int write_map(rip, position, new_zone)
register struct inode *rip; /* pointer to inode to be changed */
off_t position; /* file address to be mapped */
zone_t new_zone; /* zone # to be inserted */
{
/* Write a new zone into an inode. */
int scale, ind_ex, new_ind, new_dbl, zones, nr_indirects, single, zindex, ex;
zone_t z, z1;
register block_t b;
long excess, zone;
struct buf *bp;
rip->i_dirt = DIRTY; /* inode will be changed */
bp = NIL_BUF;
scale = rip->i_sp->s_log_zone_size; /* for zone-block conversion */
zone = (position/BLOCK_SIZE) >> scale; /* relative zone # to insert */
zones = rip->i_ndzones; /* # direct zones in the inode */
nr_indirects = rip->i_nindirs;/* # indirect zones per indirect block */
/* Is 'position' to be found in the inode itself? */
if (zone < zones) {
zindex = (int) zone; /* we need an integer here */
rip->i_zone[zindex] = new_zone;
return(OK);
}
/* It is not in the inode, so it must be single or double indirect. */
excess = zone - zones; /* first Vx_NR_DZONES don't count */
new_ind = FALSE;
new_dbl = FALSE;
if (excess < nr_indirects) {
/* 'position' can be located via the single indirect block. */
z1 = rip->i_zone[zones]; /* single indirect zone */
single = TRUE;
} else {
/* 'position' can be located via the double indirect block. */
if ( (z = rip->i_zone[zones+1]) == NO_ZONE) {
/* Create the double indirect block. */
if ( (z = alloc_zone(rip->i_dev, rip->i_zone[0])) == NO_ZONE)
return(err_code);
rip->i_zone[zones+1] = z;
new_dbl = TRUE; /* set flag for later */
}
/* Either way, 'z' is zone number for double indirect block. */
excess -= nr_indirects; /* single indirect doesn't count */
ind_ex = (int) (excess / nr_indirects);
excess = excess % nr_indirects;
if (ind_ex >= nr_indirects) return(EFBIG);
b = (block_t) z << scale;
bp = get_block(rip->i_dev, b, (new_dbl ? NO_READ : NORMAL));
if (new_dbl) zero_block(bp);
z1 = rd_indir(bp, ind_ex);
single = FALSE;
}
/* z1 is now single indirect zone; 'excess' is index. */
if (z1 == NO_ZONE) {
/* Create indirect block and store zone # in inode or dbl indir blk. */
z1 = alloc_zone(rip->i_dev, rip->i_zone[0]);
if (single)
rip->i_zone[zones] = z1; /* update inode */
else
wr_indir(bp, ind_ex, z1); /* update dbl indir */
new_ind = TRUE;
if (bp != NIL_BUF) bp->b_dirt = DIRTY; /* if double ind, it is dirty*/
if (z1 == NO_ZONE) {
put_block(bp, INDIRECT_BLOCK); /* release dbl indirect blk */
return(err_code); /* couldn't create single ind */
}
}
put_block(bp, INDIRECT_BLOCK); /* release double indirect blk */
/* z1 is indirect block's zone number. */
b = (block_t) z1 << scale;
bp = get_block(rip->i_dev, b, (new_ind ? NO_READ : NORMAL) );
if (new_ind) zero_block(bp);
ex = (int) excess; /* we need an int here */
wr_indir(bp, ex, new_zone);
bp->b_dirt = DIRTY;
put_block(bp, INDIRECT_BLOCK);
return(OK);
}