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/kernel.h>
  36 #include <linux/string.h>
  37 #include <linux/locks.h>
  38 
  39 #define clear_block(addr) \
  40 __asm__("cld\n\t" \
  41         "rep\n\t" \
  42         "stosl" \
  43         ::"a" (0),"c" (BLOCK_SIZE/4),"D" ((long) (addr)):"cx","di")
  44 
  45 void ext_free_block(struct super_block * sb, int block)
     /* [previous][next][first][last][top][bottom][index][help] */
  46 {
  47         struct buffer_head * bh;
  48         struct ext_free_block * efb;
  49 
  50         if (!sb)
  51                 panic("trying to free block on nonexistent device");
  52         lock_super (sb);
  53         if (block < sb->u.ext_sb.s_firstdatazone ||
  54             block >= sb->u.ext_sb.s_nzones) {
  55                 printk("trying to free block not in datazone\n");
  56                 return;
  57         }
  58         bh = get_hash_table(sb->s_dev, block, sb->s_blocksize);
  59         if (bh)
  60                 bh->b_dirt=0;
  61         brelse(bh);
  62         if (sb->u.ext_sb.s_firstfreeblock)
  63                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  64         if (!sb->u.ext_sb.s_firstfreeblock || efb->count == 254) {
  65 #ifdef EXTFS_DEBUG
  66 printk("ext_free_block: block full, skipping to %d\n", block);
  67 #endif
  68                 if (sb->u.ext_sb.s_firstfreeblock)
  69                         brelse (sb->u.ext_sb.s_firstfreeblock);
  70                 if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
  71                         block, sb->s_blocksize)))
  72                         panic ("ext_free_block: unable to read block to free\n");
  73                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  74                 efb->next = sb->u.ext_sb.s_firstfreeblocknumber;
  75                 efb->count = 0;
  76                 sb->u.ext_sb.s_firstfreeblocknumber = block;
  77         } else {
  78                 efb->free[efb->count++] = block;
  79         }
  80         sb->u.ext_sb.s_freeblockscount ++;
  81         sb->s_dirt = 1;
  82         sb->u.ext_sb.s_firstfreeblock->b_dirt = 1;
  83         unlock_super (sb);
  84         return;
  85 }
  86 
  87 int ext_new_block(struct super_block * sb)
     /* [previous][next][first][last][top][bottom][index][help] */
  88 {
  89         struct buffer_head * bh;
  90         struct ext_free_block * efb;
  91         int j;
  92 
  93         if (!sb)
  94                 panic("trying to get new block from nonexistant device");
  95         if (!sb->u.ext_sb.s_firstfreeblock)
  96                 return 0;
  97         lock_super (sb);
  98         efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  99         if (efb->count) {
 100                 j = efb->free[--efb->count];
 101                 sb->u.ext_sb.s_firstfreeblock->b_dirt = 1;
 102         } else {
 103 #ifdef EXTFS_DEBUG
 104 printk("ext_new_block: block empty, skipping to %d\n", efb->next);
 105 #endif
 106                 j = sb->u.ext_sb.s_firstfreeblocknumber;
 107                 sb->u.ext_sb.s_firstfreeblocknumber = efb->next;
 108                 brelse (sb->u.ext_sb.s_firstfreeblock);
 109                 if (!sb->u.ext_sb.s_firstfreeblocknumber) {
 110                         sb->u.ext_sb.s_firstfreeblock = NULL;
 111                 } else {
 112                         if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
 113                                 sb->u.ext_sb.s_firstfreeblocknumber,
 114                                 sb->s_blocksize)))
 115                                 panic ("ext_new_block: unable to read next free block\n");
 116                 }
 117         }
 118         if (j < sb->u.ext_sb.s_firstdatazone || j > sb->u.ext_sb.s_nzones) {
 119                 printk ("ext_new_block: blk = %d\n", j);
 120                 panic ("allocating block not in data zone\n");
 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                 panic("new_block: cannot get block");
 127         if (bh->b_count != 1)
 128                 panic("new block: count is != 1");
 129         clear_block(bh->b_data);
 130         bh->b_uptodate = 1;
 131         bh->b_dirt = 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         unsigned long block;
 180 
 181         if (!inode)
 182                 return;
 183         if (!inode->i_dev) {
 184                 memset(inode,0,sizeof(*inode));
 185                 return;
 186         }
 187         if (inode->i_count>1) {
 188                 printk("free_inode: inode has count=%d\n",inode->i_count);
 189                 return;
 190         }
 191         if (inode->i_nlink) {
 192                 printk("free_inode: inode has nlink=%d\n",inode->i_nlink);
 193                 return;
 194         }
 195         if (!inode->i_sb) {
 196                 printk("free_inode: inode on nonexistent device\n");
 197                 return;
 198         }
 199         lock_super (inode->i_sb);
 200         if (inode->i_ino < 1 || inode->i_ino > inode->i_sb->u.ext_sb.s_ninodes) {
 201                 printk("free_inode: inode 0 or nonexistent inode\n");
 202                 unlock_super (inode->i_sb);
 203                 return;
 204         }
 205         if (inode->i_sb->u.ext_sb.s_firstfreeinodeblock)
 206                 efi = ((struct ext_free_inode *) inode->i_sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 207                         (inode->i_sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
 208         if (!inode->i_sb->u.ext_sb.s_firstfreeinodeblock || efi->count == 14) {
 209 #ifdef EXTFS_DEBUG
 210 printk("ext_free_inode: inode full, skipping to %d\n", inode->i_ino);
 211 #endif
 212                 if (inode->i_sb->u.ext_sb.s_firstfreeinodeblock)
 213                         brelse (inode->i_sb->u.ext_sb.s_firstfreeinodeblock);
 214                 block = 2 + (inode->i_ino - 1) / EXT_INODES_PER_BLOCK;
 215                 if (!(bh = bread(inode->i_dev, block, inode->i_sb->s_blocksize)))
 216                         panic("ext_free_inode: unable to read inode block\n");
 217                 efi = ((struct ext_free_inode *) bh->b_data) +
 218                         (inode->i_ino - 1) % EXT_INODES_PER_BLOCK;
 219                 efi->next = inode->i_sb->u.ext_sb.s_firstfreeinodenumber;
 220                 efi->count = 0;
 221                 inode->i_sb->u.ext_sb.s_firstfreeinodenumber = inode->i_ino;
 222                 inode->i_sb->u.ext_sb.s_firstfreeinodeblock = bh;
 223         } else {
 224                 efi->free[efi->count++] = inode->i_ino;
 225         }
 226         inode->i_sb->u.ext_sb.s_freeinodescount ++;
 227         inode->i_sb->s_dirt = 1;
 228         inode->i_sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
 229         unlock_super (inode->i_sb);
 230         memset(inode,0,sizeof(*inode));
 231 }
 232 
 233 struct inode * ext_new_inode(struct super_block * sb)
     /* [previous][next][first][last][top][bottom][index][help] */
 234 {
 235         struct inode * inode;
 236         struct ext_free_inode * efi;
 237         unsigned long block;
 238         int j;
 239 
 240         if (!sb || !(inode=get_empty_inode()))
 241                 return NULL;
 242         inode->i_sb = sb;
 243         inode->i_flags = sb->s_flags;
 244         if (!sb->u.ext_sb.s_firstfreeinodeblock)
 245                 return 0;
 246         lock_super (sb);
 247         efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 248                 (sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
 249         if (efi->count) {
 250                 j = efi->free[--efi->count];
 251                 sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
 252         } else {
 253 #ifdef EXTFS_DEBUG
 254 printk("ext_free_inode: inode empty, skipping to %d\n", efi->next);
 255 #endif
 256                 j = sb->u.ext_sb.s_firstfreeinodenumber;
 257                 if (efi->next > sb->u.ext_sb.s_ninodes) {
 258                         printk ("efi->next = %d\n", efi->next);
 259                         panic ("ext_new_inode: bad inode number in free list\n");
 260                 }
 261                 sb->u.ext_sb.s_firstfreeinodenumber = efi->next;
 262                 block = 2 + (((unsigned long) efi->next) - 1) / EXT_INODES_PER_BLOCK;
 263                 brelse (sb->u.ext_sb.s_firstfreeinodeblock);
 264                 if (!sb->u.ext_sb.s_firstfreeinodenumber) {
 265                         sb->u.ext_sb.s_firstfreeinodeblock = NULL;
 266                 } else {
 267                         if (!(sb->u.ext_sb.s_firstfreeinodeblock =
 268                             bread(sb->s_dev, block, sb->s_blocksize)))
 269                                 panic ("ext_new_inode: unable to read next free inode block\n");
 270                 }
 271         }
 272         sb->u.ext_sb.s_freeinodescount --;
 273         sb->s_dirt = 1;
 274         inode->i_count = 1;
 275         inode->i_nlink = 1;
 276         inode->i_dev = sb->s_dev;
 277         inode->i_uid = current->euid;
 278         inode->i_gid = current->egid;
 279         inode->i_dirt = 1;
 280         inode->i_ino = j;
 281         inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
 282         inode->i_op = NULL;
 283         inode->i_blocks = inode->i_blksize = 0;
 284 #ifdef EXTFS_DEBUG
 285 printk("ext_new_inode : allocating inode %d\n", inode->i_ino);
 286 #endif
 287         unlock_super (sb);
 288         return inode;
 289 }
 290 
 291 unsigned long ext_count_free_inodes(struct super_block *sb)
     /* [previous][next][first][last][top][bottom][index][help] */
 292 {
 293 #ifdef EXTFS_DEBUG
 294         struct buffer_head * bh;
 295         struct ext_free_inode * efi;
 296         unsigned long count, block, ino;
 297 
 298         lock_super (sb);
 299         if (!sb->u.ext_sb.s_firstfreeinodeblock)
 300                 count = 0;
 301         else {
 302                 efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 303                         ((sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK);
 304                 count = efi->count + 1;
 305                 ino = efi->next;
 306                 while (ino) {
 307                         if (ino < 1 || ino > sb->u.ext_sb.s_ninodes) {
 308                                 printk ("u.ext_sb.s_firstfreeinodenumber = %d, ino = %d\n", 
 309                                         (int) sb->u.ext_sb.s_firstfreeinodenumber,ino);
 310                                 panic ("ext_count_fre_inodes: bad inode number in free list\n");
 311                         }
 312                         block = 2 + ((ino - 1) / EXT_INODES_PER_BLOCK);
 313                         if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
 314                                 printk ("ext_count_free_inodes: error while reading free inodes list\n");
 315                                 block = 0;
 316                         } else {
 317                                 efi = ((struct ext_free_inode *) bh->b_data) +
 318                                         ((ino - 1) % EXT_INODES_PER_BLOCK);
 319                                 count += efi->count + 1;
 320                                 ino = efi->next;
 321                                 brelse (bh);
 322                         }
 323                 }
 324         }
 325 printk("ext_count_free_inodes: stored = %d, computed = %d\n",
 326         sb->u.ext_sb.s_freeinodescount, count);
 327         unlock_super (sb);
 328         return count;
 329 #else
 330         return sb->u.ext_sb.s_freeinodescount;
 331 #endif
 332 }

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