linux 1.0 内核注解 linux/fs/ext2/ialloc.c

taozhijiangscu

/********************************************
*Created By: Prometheus
*Date        : 2009-5-29   
********************************************/
/*
*  linux/fs/ext2/ialloc.c
*
*  Copyright (C) 1992, 1993, 1994  Remy Card (
card@masi.ibp.fr
)
*                                  Laboratoire MASI - Institut Blaise Pascal
*                                  Universite Pierre et Marie Curie (Paris VI)
*
*  BSD ufs-inspired inode and directory allocation by
*  Stephen Tweedie (
sct@dcs.ed.ac.uk
), 1993
*/
/*
* ialloc.c contains the inodes allocation and deallocation routines
*/
/*
* The free inodes are managed by bitmaps.  A file system contains several
* blocks groups.  Each group contains 1 bitmap block for blocks, 1 bitmap
* block for inodes, N blocks for the inode table and data blocks.
* 一块的块位图、一块的i节点位图
* The file system contains group descriptors which are located after the
* super block.  Each descriptor contains the number of the bitmap block and
* the free blocks count in the block.  The descriptors are loaded in memory
* when a file system is mounted (see ext2_read_super).
*/
#include
#include
#include
#include
#include
#include
#include
static inline int find_first_zero_bit (unsigned long * addr, unsigned size)
{
int res;
if (!size)
  return 0;
__asm__("
  cld
  movl $-1,%%eax  //0xffffffff加载到eax中，如果相等就全部是满的，查找下一个
  repe; scasl  //需要注意的是这里size提供了参数表式扫描的字节数
  je 1f   //ZF==0表式扫描完了还没有找到
  subl $4,%%edi  //这里ZF没有置位，找到字节了，这里edi地址后退4个字节
  movl (%%edi),%%eax
  notl %%eax
  bsfl %%eax,%%edx //位扫描
  jmp 2f
1:  xorl %%edx,%%edx //edx=0x0
2:  subl %%ebx,%%edi //计算字节偏移量并将结果保存在edi中
  shll $3,%%edi  // *8 表式成比特位的偏移量。对于没有空闲的来说，edi-ebx=长度，再转换为比特信息，差不多就是size了
  addl %%edi,%%edx" //显示出位模式，0+edi
  : "=d" (res)     //输出
  : "c" ((size + 31) >> 5), "D" (addr), "b" (addr)//输入，size实际就是比特个数了，这里转换为4字节的单位的
  : "ax", "bx", "cx", "di");
return res;
}
//177 # define EXT2_BLOCKS_PER_GROUP(s)       ((s)->u.ext2_sb.s_blocks_per_group)
//178 # define EXT2_DESC_PER_BLOCK(s)         ((s)->u.ext2_sb.s_desc_per_block)
//179 # define EXT2_INODES_PER_GROUP(s)       ((s)->u.ext2_sb.s_inodes_per_group)
static struct ext2_group_desc * get_group_desc (struct super_block * sb,
      unsigned int block_group,
      struct buffer_head ** bh)
{
unsigned long group_desc;
unsigned long desc;
struct ext2_group_desc * gdp;
if (block_group >= sb->u.ext2_sb.s_groups_count) //快组号应该是从0开始编号的吧
  ext2_panic (sb, "get_group_desc",
       "block_group >= groups_count\n"
       "block_group = %d, groups_count = %lu",
       block_group, sb->u.ext2_sb.s_groups_count);
//group descriptors 是从 super block 后面的第一个 block 开始

//#define EXT2_MAX_GROUP_DESC     8
//struct buffer_head * s_group_desc[EXT2_MAX_GROUP_DESC];
//获得组描述符结构的
group_desc = block_group / EXT2_DESC_PER_BLOCK(sb); //==0？？
desc = block_group % EXT2_DESC_PER_BLOCK(sb);  //获得在块中的偏移量

if (!sb->u.ext2_sb.s_group_desc[group_desc])
  ext2_panic (sb, "get_group_desc",
       "Group descriptor not loaded\n"
       "block_group = %d, group_desc = %lu, desc = %lu",
        block_group, group_desc, desc);
gdp = (struct ext2_group_desc *)
  sb->u.ext2_sb.s_group_desc[group_desc]->b_data;
if (bh) //如果需要保存缓冲头指针
  *bh = sb->u.ext2_sb.s_group_desc[group_desc];
  
return gdp + desc;
}
//161 struct ext2_group_desc
//162 {
//163         unsigned long  bg_block_bitmap;         /* Blocks bitmap block */
//164         unsigned long  bg_inode_bitmap;         /* Inodes bitmap block */
//165         unsigned long  bg_inode_table;          /* Inodes table block */
//166         unsigned short bg_free_blocks_count;    /* Free blocks count */
//167         unsigned short bg_free_inodes_count;    /* Free inodes count */
//168         unsigned short bg_used_dirs_count;      /* Directories count */
//169         unsigned short bg_pad;
//170         unsigned long  bg_reserved[3];
//171 };
static void read_inode_bitmap (struct super_block * sb,
          unsigned long block_group,
          unsigned int bitmap_nr)   //bitmap_nr表式了在数组中的排位
{
struct ext2_group_desc * gdp;
struct buffer_head * bh;
gdp = get_group_desc (sb, block_group, NULL);   //得到组描述符指针
bh = bread (sb->s_dev, gdp->bg_inode_bitmap, sb->s_blocksize); //得到节点位图的块
if (!bh)
  ext2_panic (sb, "read_inode_bitmap", "Cannot read inode bitmap\n"
       "block_group = %lu, inode_bitmap = %lu",
       block_group, gdp->bg_inode_bitmap);
sb->u.ext2_sb.s_inode_bitmap_number[bitmap_nr] = block_group;
sb->u.ext2_sb.s_inode_bitmap[bitmap_nr] = bh;
}
/*
* load_inode_bitmap loads the inode bitmap for a blocks group
*
* It maintains a cache for the last bitmaps loaded.  This cache is managed
* with a LRU algorithm.
*
* Notes:
* 1/ There is one cache per mounted file system.
* 2/ If the file system contains less than EXT2_MAX_GROUP_LOADED groups,
*    this function reads the bitmap without maintaining a LRU cache.
*/
static int load_inode_bitmap (struct super_block * sb,
         unsigned int block_group)
{
int i, j;
unsigned long inode_bitmap_number;
struct buffer_head * inode_bitmap;
if (block_group >= sb->u.ext2_sb.s_groups_count)
  ext2_panic (sb, "load_inode_bitmap",
       "block_group >= groups_count\n"
       "block_group = %d, groups_count = %lu",
        block_group, sb->u.ext2_sb.s_groups_count);
        
//0号槽位总是上一次请求的块位图缓冲槽位，所以这里进行缓冲的高效检查
//这个应该是对于文件系统的组数大于8时候才有效的
if (sb->u.ext2_sb.s_loaded_inode_bitmaps > 0 &&
     sb->u.ext2_sb.s_inode_bitmap_number[0] == block_group)
  return 0;
  
if (sb->u.ext2_sb.s_groups_count u.ext2_sb.s_inode_bitmap[block_group]) {
   if (sb->u.ext2_sb.s_inode_bitmap_number[block_group] != block_group) //检测
    ext2_panic (sb, "load_inode_bitmap",
         "block_group != inode_bitmap_number");
   else
    return block_group;
  } else { //不存在，需要读取加载
   read_inode_bitmap (sb, block_group, block_group);
   return block_group;
  }
}
//这里说明了系统包含的组号多余了最多能加载的组数（8） 这就需要使用LRU进行交换了
for (i = 0; i u.ext2_sb.s_loaded_inode_bitmaps &&
      sb->u.ext2_sb.s_inode_bitmap_number != block_group;
      i++)
  ;
if (i u.ext2_sb.s_loaded_inode_bitmaps &&
       sb->u.ext2_sb.s_inode_bitmap_number == block_group) {
  inode_bitmap_number = sb->u.ext2_sb.s_inode_bitmap_number;
  inode_bitmap = sb->u.ext2_sb.s_inode_bitmap;
  for (j = i; j > 0; j--) { //将数组整体后移，并将原先舍弃，实际就是将存在的移动到最前一位
   sb->u.ext2_sb.s_inode_bitmap_number[j] =
    sb->u.ext2_sb.s_inode_bitmap_number[j - 1];
   sb->u.ext2_sb.s_inode_bitmap[j] =
    sb->u.ext2_sb.s_inode_bitmap[j - 1];
  }  //加载到第一位，表式最新使用了
  sb->u.ext2_sb.s_inode_bitmap_number[0] = inode_bitmap_number;
  sb->u.ext2_sb.s_inode_bitmap[0] = inode_bitmap;
} else {
  if (sb->u.ext2_sb.s_loaded_inode_bitmaps u.ext2_sb.s_loaded_inode_bitmaps++; //说明还有空位
  else
   brelse (sb->u.ext2_sb.s_inode_bitmap[EXT2_MAX_GROUP_LOADED - 1]); //否则释放最后的一块
  for (j = sb->u.ext2_sb.s_loaded_inode_bitmaps - 1; j > 0; j--) {
   sb->u.ext2_sb.s_inode_bitmap_number[j] =
    sb->u.ext2_sb.s_inode_bitmap_number[j - 1];
   sb->u.ext2_sb.s_inode_bitmap[j] =
    sb->u.ext2_sb.s_inode_bitmap[j - 1];
  }
  read_inode_bitmap (sb, block_group, 0);  //加载进来
}
return 0;
}
/*
* This function sets the deletion time for the inode
*
* This may be used one day by an 'undelete' program
*/
static void set_inode_dtime (struct inode * inode,
        struct ext2_group_desc * gdp)
{
unsigned long inode_block;
struct buffer_head * bh;
struct ext2_inode * raw_inode;
inode_block = gdp->bg_inode_table + (((inode->i_ino - 1) % //节点号是从1开始编号的，所以这里剪一个
   EXT2_INODES_PER_GROUP(inode->i_sb)) /  //取余表式是在快组中的第几个节点
   EXT2_INODES_PER_BLOCK(inode->i_sb) );  //然后再映射到块号
bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
if (!bh)
  ext2_panic (inode->i_sb, "set_inode_dtime",
       "Cannot load inode table block\n"
       "inode=%lu, inode_block=%lu",
       inode->i_ino, inode_block);
raw_inode = ((struct ext2_inode *) bh->b_data) +
   (((inode->i_ino - 1) %
   EXT2_INODES_PER_GROUP(inode->i_sb)) %  
   EXT2_INODES_PER_BLOCK(inode->i_sb));
raw_inode->i_links_count = 0;
raw_inode->i_dtime = CURRENT_TIME; //Deletion Time
bh->b_dirt = 1;
if (IS_SYNC(inode)) {  ///* writes are synced at once */，是否立即更新
  ll_rw_block (WRITE, 1, &bh);
  wait_on_buffer (bh);
}
brelse (bh);
}
void ext2_free_inode (struct inode * inode)
{
struct super_block * sb;
struct buffer_head * bh;
struct buffer_head * bh2;
unsigned long block_group;
unsigned long bit;
int bitmap_nr;
struct ext2_group_desc * gdp;
struct ext2_super_block * es;
if (!inode)
  return;
if (!inode->i_dev) {
  printk ("ext2_free_inode: inode has no device\n");
  return;
}
if (inode->i_count > 1) {
  printk ("ext2_free_inode: inode has count=%d\n",
   inode->i_count);
  return;
}
if (inode->i_nlink) {
  printk ("ext2_free_inode: inode has nlink=%d\n",
   inode->i_nlink);
  return;
}
if (!inode->i_sb) {
  printk("ext2_free_inode: inode on nonexistent device\n");
  return;
}
ext2_debug ("freeing inode %lu\n", inode->i_ino);
sb = inode->i_sb;
lock_super (sb);
if (inode->i_ino i_ino > sb->u.ext2_sb.s_es->s_inodes_count) {
  ext2_error (sb, "free_inode",
       "reserved inode or nonexistent inode");
  unlock_super (sb);
  return;
}
es = sb->u.ext2_sb.s_es;  /* Pointer to the super block in the buffer */
block_group = (inode->i_ino - 1) / EXT2_INODES_PER_GROUP(sb); //商表示了快组号，而余数表示了组中的节点序号
         //（一定要注意的是这里的节点号是全局性质的）
bit = (inode->i_ino - 1) % EXT2_INODES_PER_GROUP(sb);
bitmap_nr = load_inode_bitmap (sb, block_group); //对于节点位图，每一个快组是只有一个的
bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr];  //缓冲头

if (!clear_bit (bit, bh->b_data)) //空闲的节点
  ext2_warning (sb, "ext2_free_inode",
         "bit already cleared for inode %lu", inode->i_ino);
else {  //进行释放
  gdp = get_group_desc (sb, block_group, &bh2);
  gdp->bg_free_inodes_count++;
  if (S_ISDIR(inode->i_mode))
   gdp->bg_used_dirs_count--; //目录计数
  bh2->b_dirt = 1;
  es->s_free_inodes_count++;
  sb->u.ext2_sb.s_sbh->b_dirt = 1; /* Buffer containing the super block */
  set_inode_dtime (inode, gdp);  //节点删除（释放）时间
}
bh->b_dirt = 1;
if (sb->s_flags & MS_SYNC) {
  ll_rw_block (WRITE, 1, &bh);
  wait_on_buffer (bh);
}
sb->s_dirt = 1;
clear_inode (inode);
unlock_super (sb);
}
/*
* This function increments the inode version number
*
* This may be used one day by the NFS server
*/
static void inc_inode_version (struct inode * inode,
          struct ext2_group_desc *gdp,
          int mode)
{
unsigned long inode_block;
struct buffer_head * bh;
struct ext2_inode * raw_inode;

//获得节点的方法同上面是一样的，先得到在组中的节点号，再映射到具体的块中去
inode_block = gdp->bg_inode_table + (((inode->i_ino - 1) %
   EXT2_INODES_PER_GROUP(inode->i_sb)) /
   EXT2_INODES_PER_BLOCK(inode->i_sb));
bh = bread (inode->i_sb->s_dev, inode_block, inode->i_sb->s_blocksize);
if (!bh) {
  ext2_error (inode->i_sb, "inc_inode_version",
       "Cannot load inode table block"
       "inode=%lu, inode_block=%lu\n",
       inode->i_ino, inode_block);
  inode->u.ext2_i.i_version = 1;
  return;
}
raw_inode = ((struct ext2_inode *) bh->b_data) +
   (((inode->i_ino - 1) %
   EXT2_INODES_PER_GROUP(inode->i_sb)) %
   EXT2_INODES_PER_BLOCK(inode->i_sb));
raw_inode->i_version++;  //自增一次（是不是版本增加的意思啊？）
inode->u.ext2_i.i_version = raw_inode->i_version; //有必要吗？、
bh->b_dirt = 1;
brelse (bh);
}
/*
* There are two policies for allocating an inode.  If the new inode is
* a directory, then a forward search is made for a block group with both
* free space and a low directory-to-inode ratio; if that fails, then of
* the groups with above-average free space, that group with the fewest
* directories already is chosen.
*
* For other inodes, search forward from the parent directory\'s block
* group to find a free inode.
*/
struct inode * ext2_new_inode (const struct inode * dir, int mode)
{
struct super_block * sb;
struct buffer_head * bh;
struct buffer_head * bh2;
int i, j, avefreei;
struct inode * inode;
int bitmap_nr;
struct ext2_group_desc * gdp;
struct ext2_group_desc * tmp;
struct ext2_super_block * es;
if (!dir || !(inode = get_empty_inode ()))
  return NULL;
sb = dir->i_sb;
inode->i_sb = sb;
inode->i_flags = sb->s_flags;
lock_super (sb);
es = sb->u.ext2_sb.s_es;
repeat:
gdp = NULL; i=0;

if (S_ISDIR(mode)) {
  avefreei = es->s_free_inodes_count /
   sb->u.ext2_sb.s_groups_count;  //呵呵，平均空闲节点数
/* I am not yet convinced that this next bit is necessary.
  i = dir->u.ext2_i.i_block_group;
  for (j = 0; j u.ext2_sb.s_groups_count; j++) {
   tmp = get_group_desc (sb, i, &bh2);
   if ((tmp->bg_used_dirs_count bg_free_inodes_count) {
    gdp = tmp;
    break;
   }
   else
   i = ++i % sb->u.ext2_sb.s_groups_count;
  }
*/
  //这些其实是对目录的优化算法，选举了所有快组中具有空闲节点数最多的快组
  //其实长远开始这是很重要也是很有效的哦！！！
  if (!gdp) {
   for (j = 0; j u.ext2_sb.s_groups_count; j++) {
    tmp = get_group_desc (sb, j, &bh2);
    if (tmp->bg_free_inodes_count &&
     tmp->bg_free_inodes_count >= avefreei) {
     if (!gdp ||
         (tmp->bg_free_blocks_count >
          gdp->bg_free_blocks_count)) {
      i = j;
      gdp = tmp;
     }
    }
   }
  }
}
else  //非目录操作，将节点放置到父目录中
{
  /*
   * Try to place the inode in it's parent directory
   */
  i = dir->u.ext2_i.i_block_group; //inode所在组号
  tmp = get_group_desc (sb, i, &bh2);
  if (tmp->bg_free_inodes_count)  //块组中有空闲的节点
   gdp = tmp;
  else
  {
   /* //二次的，这里的ju.ext2_sb.s_groups_count; j = sb->u.ext2_sb.s_groups_count)
     i -= sb->u.ext2_sb.s_groups_count; //回卷
    tmp = get_group_desc (sb, i, &bh2);
    if (tmp->bg_free_inodes_count)  //get it
    {
     gdp = tmp;
     break;
    }
   }
  }
  if (!gdp) { //上面没有快组具有空闲的节点，这里进行线性的收索
   /*
    * That failed: try linear search for a free inode
    */
   i = dir->u.ext2_i.i_block_group + 1; //后面一个开始进行检查，本组一开始就检查过了，没有
   for (j = 2; j u.ext2_sb.s_groups_count; j++) { //感觉这里是不是少了一次啊？
    if (++i >= sb->u.ext2_sb.s_groups_count)
     i = 0;
    tmp = get_group_desc (sb, i, &bh2);
    if (tmp->bg_free_inodes_count) {
     gdp = tmp;
     break;
    }
   }
  }
}
if (!gdp) {
  unlock_super (sb);
  iput(inode);
  return NULL;
}
bitmap_nr = load_inode_bitmap (sb, i);  //i 组号
bh = sb->u.ext2_sb.s_inode_bitmap[bitmap_nr]; //在节点位图中选择空闲的位

if ((j = find_first_zero_bit ((unsigned long *) bh->b_data,
          EXT2_INODES_PER_GROUP(sb))) b_data)) {
   ext2_warning (sb, "ext2_new_inode",
          "bit already set for inode %d", j);
   goto repeat;
  }
  bh->b_dirt = 1;
  if (sb->s_flags & MS_SYNC) {
   ll_rw_block (WRITE, 1, &bh);
   wait_on_buffer (bh);
  }
} else { //这里对整个节点位图快进行检查后发现没有空的，这里说明出问题了
  if (gdp->bg_free_inodes_count != 0) {
   ext2_error (sb, "ext2_new_inode",
        "Free inodes count corrupted in group %d",
        i);
   unlock_super (sb);
   iput (inode);
   return NULL;
  }
  goto repeat;
}

j += i * EXT2_INODES_PER_GROUP(sb) + 1;  //调整为全局的节点号（1开始计数的），然后进行检测
if (j  es->s_inodes_count) {
  ext2_error (sb, "ext2_new_inode",
       "reserved inode or inode > inodes count\n"
       "block_group = %d,inode=%d", i, j);
  unlock_super (sb);
  iput (inode);
  return NULL;
}
gdp->bg_free_inodes_count--;
if (S_ISDIR(mode))
  gdp->bg_used_dirs_count++;
bh2->b_dirt = 1;
es->s_free_inodes_count--;
sb->u.ext2_sb.s_sbh->b_dirt = 1;
sb->s_dirt = 1;
inode->i_mode = mode;
inode->i_sb = sb;
inode->i_count = 1;
inode->i_nlink = 1;
inode->i_dev = sb->s_dev;
inode->i_uid = current->euid;
if (test_opt (sb, GRPID)) //检测挂在选项，这个是带参数的宏，可以看看
  inode->i_gid = dir->i_gid;
else if (dir->i_mode & S_ISGID) { //设置了粘滞位，但是节点就不能设置成egid了
  inode->i_gid = dir->i_gid;
  if (S_ISDIR(mode))
   mode |= S_ISGID;
} else
  inode->i_gid = current->egid;
inode->i_dirt = 1;
inode->i_ino = j;
inode->i_blksize = sb->s_blocksize;
inode->i_blocks = 0;
inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
inode->u.ext2_i.i_flags = dir->u.ext2_i.i_flags;
inode->u.ext2_i.i_faddr = 0;
inode->u.ext2_i.i_frag = 0;
inode->u.ext2_i.i_fsize = 0;
inode->u.ext2_i.i_file_acl = 0;
inode->u.ext2_i.i_dir_acl = 0;
inode->u.ext2_i.i_dtime = 0;
inode->u.ext2_i.i_block_group = i;
inode->i_op = NULL;
if (inode->u.ext2_i.i_flags & EXT2_SYNC_FL)
  inode->i_flags |= MS_SYNC;
insert_inode_hash(inode);
inc_inode_version (inode, gdp, mode);  //why？
ext2_debug ("allocating inode %lu\n", inode->i_ino);
unlock_super (sb);
return inode;
}
unsigned long ext2_count_free_inodes (struct super_block * sb)
{
#ifdef EXT2FS_DEBUG
struct ext2_super_block * es;
unsigned long desc_count, bitmap_count, x;
int bitmap_nr;
struct ext2_group_desc * gdp;
int i;
lock_super (sb);
es = sb->u.ext2_sb.s_es;
desc_count = 0;
bitmap_count = 0;
gdp = NULL;
for (i = 0; i u.ext2_sb.s_groups_count; i++)
{
  gdp = get_group_desc (sb, i, NULL);
  desc_count += gdp->bg_free_inodes_count;
  bitmap_nr = load_inode_bitmap (sb, i);
  x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
         EXT2_INODES_PER_GROUP(sb) / 8);
  printk ("group %d: stored = %d, counted = %lu\n",
   i, gdp->bg_free_inodes_count, x);
  bitmap_count += x;
}
printk("ext2_count_free_inodes: stored = %lu, computed = %lu, %lu\n",
  es->s_free_inodes_count, desc_count, bitmap_count);
unlock_super (sb);
return desc_count;
#else
return sb->u.ext2_sb.s_es->s_free_inodes_count;
#endif
}
//功能就是对节点位图进行空闲节点位图统计核实
void ext2_check_inodes_bitmap (struct super_block * sb)
{
struct ext2_super_block * es;
unsigned long desc_count, bitmap_count, x;
int bitmap_nr;
struct ext2_group_desc * gdp;
int i;
lock_super (sb);
es = sb->u.ext2_sb.s_es;
desc_count = 0;
bitmap_count = 0;
gdp = NULL;

for (i = 0; i u.ext2_sb.s_groups_count; i++)
{
  gdp = get_group_desc (sb, i, NULL);
  desc_count += gdp->bg_free_inodes_count;
  bitmap_nr = load_inode_bitmap (sb, i);
  x = ext2_count_free (sb->u.ext2_sb.s_inode_bitmap[bitmap_nr],
         EXT2_INODES_PER_GROUP(sb) / 8);
  if (gdp->bg_free_inodes_count != x)  //单个组中的空闲数目
   ext2_error (sb, "ext2_check_inodes_bitmap",
        "Wrong free inodes count in group %d, "
        "stored = %d, counted = %lu", i,
        gdp->bg_free_inodes_count, x);
  bitmap_count += x;
}
if (es->s_free_inodes_count != bitmap_count)  //超级快中统计的总空闲数目
  ext2_error (sb, "ext2_check_inodes_bitmap",
       "Wrong free inodes count in super block, "
       "stored = %lu, counted = %lu",
       es->s_free_inodes_count, bitmap_count);
unlock_super (sb);
}

文档地址：
http://blogimg.chinaunix.net/blog/upfile2/090529182258.pdf


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/90306/showart_1947670.html