root/fs/ext/freelists.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. ext_free_block
  2. ext_new_block
  3. ext_count_free_blocks
  4. ext_free_inode
  5. ext_new_inode
  6. 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 void ext_free_block(struct super_block * sb, int block)
     /* [previous][next][first][last][top][bottom][index][help] */
  41 {
  42         struct buffer_head * bh;
  43         struct ext_free_block * efb;
  44 
  45         if (!sb) {
  46                 printk("trying to free block on non-existent device\n");
  47                 return;
  48         }
  49         lock_super (sb);
  50         if (block < sb->u.ext_sb.s_firstdatazone ||
  51             block >= sb->u.ext_sb.s_nzones) {
  52                 printk("trying to free block not in datazone\n");
  53                 return;
  54         }
  55         bh = get_hash_table(sb->s_dev, block, sb->s_blocksize);
  56         if (bh)
  57                 bh->b_dirt=0;
  58         brelse(bh);
  59         if (sb->u.ext_sb.s_firstfreeblock)
  60                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  61         if (!sb->u.ext_sb.s_firstfreeblock || efb->count == 254) {
  62 #ifdef EXTFS_DEBUG
  63 printk("ext_free_block: block full, skipping to %d\n", block);
  64 #endif
  65                 if (sb->u.ext_sb.s_firstfreeblock)
  66                         brelse (sb->u.ext_sb.s_firstfreeblock);
  67                 if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
  68                         block, sb->s_blocksize)))
  69                         panic ("ext_free_block: unable to read block to free\n");
  70                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  71                 efb->next = sb->u.ext_sb.s_firstfreeblocknumber;
  72                 efb->count = 0;
  73                 sb->u.ext_sb.s_firstfreeblocknumber = block;
  74         } else {
  75                 efb->free[efb->count++] = block;
  76         }
  77         sb->u.ext_sb.s_freeblockscount ++;
  78         sb->s_dirt = 1;
  79         mark_buffer_dirty(sb->u.ext_sb.s_firstfreeblock, 1);
  80         unlock_super (sb);
  81         return;
  82 }
  83 
  84 int ext_new_block(struct super_block * sb)
     /* [previous][next][first][last][top][bottom][index][help] */
  85 {
  86         struct buffer_head * bh;
  87         struct ext_free_block * efb;
  88         int j;
  89 
  90         if (!sb) {
  91                 printk("trying to get new block from non-existent device\n");
  92                 return 0;
  93         }
  94         if (!sb->u.ext_sb.s_firstfreeblock)
  95                 return 0;
  96         lock_super (sb);
  97         efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  98         if (efb->count) {
  99                 j = efb->free[--efb->count];
 100                 mark_buffer_dirty(sb->u.ext_sb.s_firstfreeblock, 1);
 101         } else {
 102 #ifdef EXTFS_DEBUG
 103 printk("ext_new_block: block empty, skipping to %d\n", efb->next);
 104 #endif
 105                 j = sb->u.ext_sb.s_firstfreeblocknumber;
 106                 sb->u.ext_sb.s_firstfreeblocknumber = efb->next;
 107                 brelse (sb->u.ext_sb.s_firstfreeblock);
 108                 if (!sb->u.ext_sb.s_firstfreeblocknumber) {
 109                         sb->u.ext_sb.s_firstfreeblock = NULL;
 110                 } else {
 111                         if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
 112                                 sb->u.ext_sb.s_firstfreeblocknumber,
 113                                 sb->s_blocksize)))
 114                                 panic ("ext_new_block: unable to read next free block\n");
 115                 }
 116         }
 117         if (j < sb->u.ext_sb.s_firstdatazone || j > sb->u.ext_sb.s_nzones) {
 118                 printk ("ext_new_block: blk = %d\n", j);
 119                 printk("allocating block not in data zone\n");
 120                 return 0;
 121         }
 122         sb->u.ext_sb.s_freeblockscount --;
 123         sb->s_dirt = 1;
 124 
 125         if (!(bh=getblk(sb->s_dev, j, sb->s_blocksize))) {
 126                 printk("new_block: cannot get block");
 127                 return 0;
 128         }
 129         memset(bh->b_data, 0, BLOCK_SIZE);
 130         bh->b_uptodate = 1;
 131         mark_buffer_dirty(bh, 1);
 132         brelse(bh);
 133 #ifdef EXTFS_DEBUG
 134 printk("ext_new_block: allocating block %d\n", j);
 135 #endif
 136         unlock_super (sb);
 137         return j;
 138 }
 139 
 140 unsigned long ext_count_free_blocks(struct super_block *sb)
     /* [previous][next][first][last][top][bottom][index][help] */
 141 {
 142 #ifdef EXTFS_DEBUG
 143         struct buffer_head * bh;
 144         struct ext_free_block * efb;
 145         unsigned long count, block;
 146 
 147         lock_super (sb);
 148         if (!sb->u.ext_sb.s_firstfreeblock)
 149                 count = 0;
 150         else {
 151                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
 152                 count = efb->count + 1;
 153                 block = efb->next;
 154                 while (block) {
 155                         if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
 156                                 printk ("ext_count_free: error while reading free blocks list\n");
 157                                 block = 0;
 158                         } else {
 159                                 efb = (struct ext_free_block *) bh->b_data;
 160                                 count += efb->count + 1;
 161                                 block = efb->next;
 162                                 brelse (bh);
 163                         }
 164                 }
 165         }
 166 printk("ext_count_free_blocks: stored = %d, computed = %d\n",
 167         sb->u.ext_sb.s_freeblockscount, count);
 168         unlock_super (sb);
 169         return count;
 170 #else
 171         return sb->u.ext_sb.s_freeblockscount;
 172 #endif
 173 }
 174 
 175 void ext_free_inode(struct inode * inode)
     /* [previous][next][first][last][top][bottom][index][help] */
 176 {
 177         struct buffer_head * bh;
 178         struct ext_free_inode * efi;
 179         struct super_block * sb;
 180         unsigned long block;
 181         unsigned long ino;
 182         dev_t dev;
 183 
 184         if (!inode)
 185                 return;
 186         if (!inode->i_dev) {
 187                 printk("free_inode: inode has no device\n");
 188                 return;
 189         }
 190         if (inode->i_count != 1) {
 191                 printk("free_inode: inode has count=%d\n",inode->i_count);
 192                 return;
 193         }
 194         if (inode->i_nlink) {
 195                 printk("free_inode: inode has nlink=%d\n",inode->i_nlink);
 196                 return;
 197         }
 198         if (!inode->i_sb) {
 199                 printk("free_inode: inode on non-existent device\n");
 200                 return;
 201         }
 202         sb = inode->i_sb;
 203         ino = inode->i_ino;
 204         dev = inode->i_dev;
 205         clear_inode(inode);
 206         lock_super (sb);
 207         if (ino < 1 || ino > sb->u.ext_sb.s_ninodes) {
 208                 printk("free_inode: inode 0 or non-existent inode\n");
 209                 unlock_super (sb);
 210                 return;
 211         }
 212         if (sb->u.ext_sb.s_firstfreeinodeblock)
 213                 efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 214                         (sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
 215         if (!sb->u.ext_sb.s_firstfreeinodeblock || efi->count == 14) {
 216 #ifdef EXTFS_DEBUG
 217 printk("ext_free_inode: inode full, skipping to %d\n", ino);
 218 #endif
 219                 if (sb->u.ext_sb.s_firstfreeinodeblock)
 220                         brelse (sb->u.ext_sb.s_firstfreeinodeblock);
 221                 block = 2 + (ino - 1) / EXT_INODES_PER_BLOCK;
 222                 if (!(bh = bread(dev, block, sb->s_blocksize)))
 223                         panic("ext_free_inode: unable to read inode block\n");
 224                 efi = ((struct ext_free_inode *) bh->b_data) +
 225                         (ino - 1) % EXT_INODES_PER_BLOCK;
 226                 efi->next = sb->u.ext_sb.s_firstfreeinodenumber;
 227                 efi->count = 0;
 228                 sb->u.ext_sb.s_firstfreeinodenumber = ino;
 229                 sb->u.ext_sb.s_firstfreeinodeblock = bh;
 230         } else {
 231                 efi->free[efi->count++] = ino;
 232         }
 233         sb->u.ext_sb.s_freeinodescount ++;
 234         sb->s_dirt = 1;
 235         mark_buffer_dirty(sb->u.ext_sb.s_firstfreeinodeblock, 1);
 236         unlock_super (sb);
 237 }
 238 
 239 struct inode * ext_new_inode(const struct inode * dir)
     /* [previous][next][first][last][top][bottom][index][help] */
 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                 mark_buffer_dirty(sb->u.ext_sb.s_firstfreeinodeblock, 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 = %ld\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->fsuid;
 286         inode->i_gid = (dir->i_mode & S_ISGID) ? dir->i_gid : current->fsgid;
 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         insert_inode_hash(inode);
 293 #ifdef EXTFS_DEBUG
 294 printk("ext_new_inode : allocating inode %d\n", inode->i_ino);
 295 #endif
 296         unlock_super (sb);
 297         return inode;
 298 }
 299 
 300 unsigned long ext_count_free_inodes(struct super_block *sb)
     /* [previous][next][first][last][top][bottom][index][help] */
 301 {
 302 #ifdef EXTFS_DEBUG
 303         struct buffer_head * bh;
 304         struct ext_free_inode * efi;
 305         unsigned long count, block, ino;
 306 
 307         lock_super (sb);
 308         if (!sb->u.ext_sb.s_firstfreeinodeblock)
 309                 count = 0;
 310         else {
 311                 efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 312                         ((sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK);
 313                 count = efi->count + 1;
 314                 ino = efi->next;
 315                 while (ino) {
 316                         if (ino < 1 || ino > sb->u.ext_sb.s_ninodes) {
 317                                 printk ("u.ext_sb.s_firstfreeinodenumber = %d, ino = %d\n", 
 318                                         (int) sb->u.ext_sb.s_firstfreeinodenumber,ino);
 319                                 panic ("ext_count_fre_inodes: bad inode number in free list\n");
 320                         }
 321                         block = 2 + ((ino - 1) / EXT_INODES_PER_BLOCK);
 322                         if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
 323                                 printk ("ext_count_free_inodes: error while reading free inodes list\n");
 324                                 block = 0;
 325                         } else {
 326                                 efi = ((struct ext_free_inode *) bh->b_data) +
 327                                         ((ino - 1) % EXT_INODES_PER_BLOCK);
 328                                 count += efi->count + 1;
 329                                 ino = efi->next;
 330                                 brelse (bh);
 331                         }
 332                 }
 333         }
 334 printk("ext_count_free_inodes: stored = %d, computed = %d\n",
 335         sb->u.ext_sb.s_freeinodescount, count);
 336         unlock_super (sb);
 337         return count;
 338 #else
 339         return sb->u.ext_sb.s_freeinodescount;
 340 #endif
 341 }

/* [previous][next][first][last][top][bottom][index][help] */