fs/ext/freelists.c

/* */
This source file includes following definitions.
ext_free_block
ext_new_block
ext_count_free_blocks
ext_free_inode
ext_new_inode
ext_count_free_inodes
   1 /*
   2  *  linux/fs/ext/freelists.c
   3  *
   4  *  Copyright (C) 1992  Remy Card (card@masi.ibp.fr)
   5  *
   6  */
   7 
   8 /* freelists.c contains the code that handles the inode and block free lists */
   9 
  10 
  11 /*
  12 
  13    The free blocks are managed by a linked list. The super block contains the
  14    number of the first free block. This block contains 254 numbers of other
  15    free blocks and the number of the next block in the list.
  16 
  17    When an ext fs is mounted, the number of the first free block is stored
  18    in s->u.ext_sb.s_firstfreeblocknumber and the block header is stored in
  19    s->u.ext_sb.s_firstfreeblock. u.ext_sb.s_freeblockscount contains the count
  20    of free blocks.
  21 
  22    The free inodes are also managed by a linked list in a similar way. The
  23    super block contains the number of the first free inode. This inode contains
  24    14 numbers of other free inodes and the number of the next inode in the list.
  25    
  26    The number of the first free inode is stored in
  27    s->u.ext_sb.s_firstfreeinodenumber and the header of the block containing
  28    the inode is stored in s->u.ext_sb.s_firstfreeinodeblock.
  29    u.ext_sb.s_freeinodescount contains the count of free inodes.
  30 
  31 */
  32 
  33 #include <linux/sched.h>
  34 #include <linux/ext_fs.h>
  35 #include <linux/stat.h>
  36 #include <linux/kernel.h>
  37 #include <linux/string.h>
  38 #include <linux/locks.h>
  39 
  40 #define clear_block(addr) \
  41 __asm__("cld\n\t" \
  42         "rep\n\t" \
  43         "stosl" \
  44         ::"a" (0),"c" (BLOCK_SIZE/4),"D" ((long) (addr)):"cx","di")
  45 
  46 void ext_free_block(struct super_block * sb, int block)
     /*  */
  47 {
  48         struct buffer_head * bh;
  49         struct ext_free_block * efb;
  50 
  51         if (!sb) {
  52                 printk("trying to free block on non-existent device\n");
  53                 return;
  54         }
  55         lock_super (sb);
  56         if (block < sb->u.ext_sb.s_firstdatazone ||
  57             block >= sb->u.ext_sb.s_nzones) {
  58                 printk("trying to free block not in datazone\n");
  59                 return;
  60         }
  61         bh = get_hash_table(sb->s_dev, block, sb->s_blocksize);
  62         if (bh)
  63                 bh->b_dirt=0;
  64         brelse(bh);
  65         if (sb->u.ext_sb.s_firstfreeblock)
  66                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  67         if (!sb->u.ext_sb.s_firstfreeblock || efb->count == 254) {
  68 #ifdef EXTFS_DEBUG
  69 printk("ext_free_block: block full, skipping to %d\n", block);
  70 #endif
  71                 if (sb->u.ext_sb.s_firstfreeblock)
  72                         brelse (sb->u.ext_sb.s_firstfreeblock);
  73                 if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
  74                         block, sb->s_blocksize)))
  75                         panic ("ext_free_block: unable to read block to free\n");
  76                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  77                 efb->next = sb->u.ext_sb.s_firstfreeblocknumber;
  78                 efb->count = 0;
  79                 sb->u.ext_sb.s_firstfreeblocknumber = block;
  80         } else {
  81                 efb->free[efb->count++] = block;
  82         }
  83         sb->u.ext_sb.s_freeblockscount ++;
  84         sb->s_dirt = 1;
  85         sb->u.ext_sb.s_firstfreeblock->b_dirt = 1;
  86         unlock_super (sb);
  87         return;
  88 }
  89 
  90 int ext_new_block(struct super_block * sb)
     /*  */
  91 {
  92         struct buffer_head * bh;
  93         struct ext_free_block * efb;
  94         int j;
  95 
  96         if (!sb) {
  97                 printk("trying to get new block from non-existent device\n");
  98                 return 0;
  99         }
 100         if (!sb->u.ext_sb.s_firstfreeblock)
 101                 return 0;
 102         lock_super (sb);
 103         efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
 104         if (efb->count) {
 105                 j = efb->free[--efb->count];
 106                 sb->u.ext_sb.s_firstfreeblock->b_dirt = 1;
 107         } else {
 108 #ifdef EXTFS_DEBUG
 109 printk("ext_new_block: block empty, skipping to %d\n", efb->next);
 110 #endif
 111                 j = sb->u.ext_sb.s_firstfreeblocknumber;
 112                 sb->u.ext_sb.s_firstfreeblocknumber = efb->next;
 113                 brelse (sb->u.ext_sb.s_firstfreeblock);
 114                 if (!sb->u.ext_sb.s_firstfreeblocknumber) {
 115                         sb->u.ext_sb.s_firstfreeblock = NULL;
 116                 } else {
 117                         if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
 118                                 sb->u.ext_sb.s_firstfreeblocknumber,
 119                                 sb->s_blocksize)))
 120                                 panic ("ext_new_block: unable to read next free block\n");
 121                 }
 122         }
 123         if (j < sb->u.ext_sb.s_firstdatazone || j > sb->u.ext_sb.s_nzones) {
 124                 printk ("ext_new_block: blk = %d\n", j);
 125                 printk("allocating block not in data zone\n");
 126                 return 0;
 127         }
 128         sb->u.ext_sb.s_freeblockscount --;
 129         sb->s_dirt = 1;
 130 
 131         if (!(bh=getblk(sb->s_dev, j, sb->s_blocksize))) {
 132                 printk("new_block: cannot get block");
 133                 return 0;
 134         }
 135         clear_block(bh->b_data);
 136         bh->b_uptodate = 1;
 137         bh->b_dirt = 1;
 138         brelse(bh);
 139 #ifdef EXTFS_DEBUG
 140 printk("ext_new_block: allocating block %d\n", j);
 141 #endif
 142         unlock_super (sb);
 143         return j;
 144 }
 145 
 146 unsigned long ext_count_free_blocks(struct super_block *sb)
     /*  */
 147 {
 148 #ifdef EXTFS_DEBUG
 149         struct buffer_head * bh;
 150         struct ext_free_block * efb;
 151         unsigned long count, block;
 152 
 153         lock_super (sb);
 154         if (!sb->u.ext_sb.s_firstfreeblock)
 155                 count = 0;
 156         else {
 157                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
 158                 count = efb->count + 1;
 159                 block = efb->next;
 160                 while (block) {
 161                         if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
 162                                 printk ("ext_count_free: error while reading free blocks list\n");
 163                                 block = 0;
 164                         } else {
 165                                 efb = (struct ext_free_block *) bh->b_data;
 166                                 count += efb->count + 1;
 167                                 block = efb->next;
 168                                 brelse (bh);
 169                         }
 170                 }
 171         }
 172 printk("ext_count_free_blocks: stored = %d, computed = %d\n",
 173         sb->u.ext_sb.s_freeblockscount, count);
 174         unlock_super (sb);
 175         return count;
 176 #else
 177         return sb->u.ext_sb.s_freeblockscount;
 178 #endif
 179 }
 180 
 181 void ext_free_inode(struct inode * inode)
     /*  */
 182 {
 183         struct buffer_head * bh;
 184         struct ext_free_inode * efi;
 185         unsigned long block;
 186 
 187         if (!inode)
 188                 return;
 189         if (!inode->i_dev) {
 190                 printk("free_inode: inode has no device\n");
 191                 return;
 192         }
 193         if (inode->i_count != 1) {
 194                 printk("free_inode: inode has count=%d\n",inode->i_count);
 195                 return;
 196         }
 197         if (inode->i_nlink) {
 198                 printk("free_inode: inode has nlink=%d\n",inode->i_nlink);
 199                 return;
 200         }
 201         if (!inode->i_sb) {
 202                 printk("free_inode: inode on non-existent device\n");
 203                 return;
 204         }
 205         lock_super (inode->i_sb);
 206         if (inode->i_ino < 1 || inode->i_ino > inode->i_sb->u.ext_sb.s_ninodes) {
 207                 printk("free_inode: inode 0 or non-existent inode\n");
 208                 unlock_super (inode->i_sb);
 209                 return;
 210         }
 211         if (inode->i_sb->u.ext_sb.s_firstfreeinodeblock)
 212                 efi = ((struct ext_free_inode *) inode->i_sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 213                         (inode->i_sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
 214         if (!inode->i_sb->u.ext_sb.s_firstfreeinodeblock || efi->count == 14) {
 215 #ifdef EXTFS_DEBUG
 216 printk("ext_free_inode: inode full, skipping to %d\n", inode->i_ino);
 217 #endif
 218                 if (inode->i_sb->u.ext_sb.s_firstfreeinodeblock)
 219                         brelse (inode->i_sb->u.ext_sb.s_firstfreeinodeblock);
 220                 block = 2 + (inode->i_ino - 1) / EXT_INODES_PER_BLOCK;
 221                 if (!(bh = bread(inode->i_dev, block, inode->i_sb->s_blocksize)))
 222                         panic("ext_free_inode: unable to read inode block\n");
 223                 efi = ((struct ext_free_inode *) bh->b_data) +
 224                         (inode->i_ino - 1) % EXT_INODES_PER_BLOCK;
 225                 efi->next = inode->i_sb->u.ext_sb.s_firstfreeinodenumber;
 226                 efi->count = 0;
 227                 inode->i_sb->u.ext_sb.s_firstfreeinodenumber = inode->i_ino;
 228                 inode->i_sb->u.ext_sb.s_firstfreeinodeblock = bh;
 229         } else {
 230                 efi->free[efi->count++] = inode->i_ino;
 231         }
 232         inode->i_sb->u.ext_sb.s_freeinodescount ++;
 233         inode->i_sb->s_dirt = 1;
 234         inode->i_sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
 235         unlock_super (inode->i_sb);
 236         clear_inode(inode);
 237 }
 238 
 239 struct inode * ext_new_inode(const struct inode * dir)
     /*  */
 240 {
 241         struct super_block * sb;
 242         struct inode * inode;
 243         struct ext_free_inode * efi;
 244         unsigned long block;
 245         int j;
 246 
 247         if (!dir || !(inode=get_empty_inode()))
 248                 return NULL;
 249         sb = dir->i_sb;
 250         inode->i_sb = sb;
 251         inode->i_flags = sb->s_flags;
 252         if (!sb->u.ext_sb.s_firstfreeinodeblock)
 253                 return 0;
 254         lock_super (sb);
 255         efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 256                 (sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
 257         if (efi->count) {
 258                 j = efi->free[--efi->count];
 259                 sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
 260         } else {
 261 #ifdef EXTFS_DEBUG
 262 printk("ext_free_inode: inode empty, skipping to %d\n", efi->next);
 263 #endif
 264                 j = sb->u.ext_sb.s_firstfreeinodenumber;
 265                 if (efi->next > sb->u.ext_sb.s_ninodes) {
 266                         printk ("efi->next = %d\n", efi->next);
 267                         panic ("ext_new_inode: bad inode number in free list\n");
 268                 }
 269                 sb->u.ext_sb.s_firstfreeinodenumber = efi->next;
 270                 block = 2 + (((unsigned long) efi->next) - 1) / EXT_INODES_PER_BLOCK;
 271                 brelse (sb->u.ext_sb.s_firstfreeinodeblock);
 272                 if (!sb->u.ext_sb.s_firstfreeinodenumber) {
 273                         sb->u.ext_sb.s_firstfreeinodeblock = NULL;
 274                 } else {
 275                         if (!(sb->u.ext_sb.s_firstfreeinodeblock =
 276                             bread(sb->s_dev, block, sb->s_blocksize)))
 277                                 panic ("ext_new_inode: unable to read next free inode block\n");
 278                 }
 279         }
 280         sb->u.ext_sb.s_freeinodescount --;
 281         sb->s_dirt = 1;
 282         inode->i_count = 1;
 283         inode->i_nlink = 1;
 284         inode->i_dev = sb->s_dev;
 285         inode->i_uid = current->euid;
 286         inode->i_gid = (dir->i_mode & S_ISGID) ? dir->i_gid : current->egid;
 287         inode->i_dirt = 1;
 288         inode->i_ino = j;
 289         inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
 290         inode->i_op = NULL;
 291         inode->i_blocks = inode->i_blksize = 0;
 292 #ifdef EXTFS_DEBUG
 293 printk("ext_new_inode : allocating inode %d\n", inode->i_ino);
 294 #endif
 295         unlock_super (sb);
 296         return inode;
 297 }
 298 
 299 unsigned long ext_count_free_inodes(struct super_block *sb)
     /*  */
 300 {
 301 #ifdef EXTFS_DEBUG
 302         struct buffer_head * bh;
 303         struct ext_free_inode * efi;
 304         unsigned long count, block, ino;
 305 
 306         lock_super (sb);
 307         if (!sb->u.ext_sb.s_firstfreeinodeblock)
 308                 count = 0;
 309         else {
 310                 efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 311                         ((sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK);
 312                 count = efi->count + 1;
 313                 ino = efi->next;
 314                 while (ino) {
 315                         if (ino < 1 || ino > sb->u.ext_sb.s_ninodes) {
 316                                 printk ("u.ext_sb.s_firstfreeinodenumber = %d, ino = %d\n", 
 317                                         (int) sb->u.ext_sb.s_firstfreeinodenumber,ino);
 318                                 panic ("ext_count_fre_inodes: bad inode number in free list\n");
 319                         }
 320                         block = 2 + ((ino - 1) / EXT_INODES_PER_BLOCK);
 321                         if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
 322                                 printk ("ext_count_free_inodes: error while reading free inodes list\n");
 323                                 block = 0;
 324                         } else {
 325                                 efi = ((struct ext_free_inode *) bh->b_data) +
 326                                         ((ino - 1) % EXT_INODES_PER_BLOCK);
 327                                 count += efi->count + 1;
 328                                 ino = efi->next;
 329                                 brelse (bh);
 330                         }
 331                 }
 332         }
 333 printk("ext_count_free_inodes: stored = %d, computed = %d\n",
 334         sb->u.ext_sb.s_freeinodescount, count);
 335         unlock_super (sb);
 336         return count;
 337 #else
 338         return sb->u.ext_sb.s_freeinodescount;
 339 #endif
 340 }
/* */
root/fs/ext/freelists.c

DEFINITIONS
