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 #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)
     /* [previous][next][first][last][top][bottom][index][help] */
  47 {
  48         struct buffer_head * bh;
  49         struct ext_free_block * efb;
  50 
  51         if (!sb)
  52                 panic("trying to free block on nonexistent device");
  53         lock_super (sb);
  54         if (block < sb->u.ext_sb.s_firstdatazone ||
  55             block >= sb->u.ext_sb.s_nzones) {
  56                 printk("trying to free block not in datazone\n");
  57                 return;
  58         }
  59         bh = get_hash_table(sb->s_dev, block, sb->s_blocksize);
  60         if (bh)
  61                 bh->b_dirt=0;
  62         brelse(bh);
  63         if (sb->u.ext_sb.s_firstfreeblock)
  64                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  65         if (!sb->u.ext_sb.s_firstfreeblock || efb->count == 254) {
  66 #ifdef EXTFS_DEBUG
  67 printk("ext_free_block: block full, skipping to %d\n", block);
  68 #endif
  69                 if (sb->u.ext_sb.s_firstfreeblock)
  70                         brelse (sb->u.ext_sb.s_firstfreeblock);
  71                 if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
  72                         block, sb->s_blocksize)))
  73                         panic ("ext_free_block: unable to read block to free\n");
  74                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
  75                 efb->next = sb->u.ext_sb.s_firstfreeblocknumber;
  76                 efb->count = 0;
  77                 sb->u.ext_sb.s_firstfreeblocknumber = block;
  78         } else {
  79                 efb->free[efb->count++] = block;
  80         }
  81         sb->u.ext_sb.s_freeblockscount ++;
  82         sb->s_dirt = 1;
  83         sb->u.ext_sb.s_firstfreeblock->b_dirt = 1;
  84         unlock_super (sb);
  85         return;
  86 }
  87 
  88 int ext_new_block(struct super_block * sb)
     /* [previous][next][first][last][top][bottom][index][help] */
  89 {
  90         struct buffer_head * bh;
  91         struct ext_free_block * efb;
  92         int j;
  93 
  94         if (!sb)
  95                 panic("trying to get new block from nonexistant device");
  96         if (!sb->u.ext_sb.s_firstfreeblock)
  97                 return 0;
  98         lock_super (sb);
  99         efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
 100         if (efb->count) {
 101                 j = efb->free[--efb->count];
 102                 sb->u.ext_sb.s_firstfreeblock->b_dirt = 1;
 103         } else {
 104 #ifdef EXTFS_DEBUG
 105 printk("ext_new_block: block empty, skipping to %d\n", efb->next);
 106 #endif
 107                 j = sb->u.ext_sb.s_firstfreeblocknumber;
 108                 sb->u.ext_sb.s_firstfreeblocknumber = efb->next;
 109                 brelse (sb->u.ext_sb.s_firstfreeblock);
 110                 if (!sb->u.ext_sb.s_firstfreeblocknumber) {
 111                         sb->u.ext_sb.s_firstfreeblock = NULL;
 112                 } else {
 113                         if (!(sb->u.ext_sb.s_firstfreeblock = bread (sb->s_dev,
 114                                 sb->u.ext_sb.s_firstfreeblocknumber,
 115                                 sb->s_blocksize)))
 116                                 panic ("ext_new_block: unable to read next free block\n");
 117                 }
 118         }
 119         if (j < sb->u.ext_sb.s_firstdatazone || j > sb->u.ext_sb.s_nzones) {
 120                 printk ("ext_new_block: blk = %d\n", j);
 121                 panic ("allocating block not in data zone\n");
 122         }
 123         sb->u.ext_sb.s_freeblockscount --;
 124         sb->s_dirt = 1;
 125 
 126         if (!(bh=getblk(sb->s_dev, j, sb->s_blocksize)))
 127                 panic("new_block: cannot get block");
 128         if (bh->b_count != 1)
 129                 panic("new block: count is != 1");
 130         clear_block(bh->b_data);
 131         bh->b_uptodate = 1;
 132         bh->b_dirt = 1;
 133         brelse(bh);
 134 #ifdef EXTFS_DEBUG
 135 printk("ext_new_block: allocating block %d\n", j);
 136 #endif
 137         unlock_super (sb);
 138         return j;
 139 }
 140 
 141 unsigned long ext_count_free_blocks(struct super_block *sb)
     /* [previous][next][first][last][top][bottom][index][help] */
 142 {
 143 #ifdef EXTFS_DEBUG
 144         struct buffer_head * bh;
 145         struct ext_free_block * efb;
 146         unsigned long count, block;
 147 
 148         lock_super (sb);
 149         if (!sb->u.ext_sb.s_firstfreeblock)
 150                 count = 0;
 151         else {
 152                 efb = (struct ext_free_block *) sb->u.ext_sb.s_firstfreeblock->b_data;
 153                 count = efb->count + 1;
 154                 block = efb->next;
 155                 while (block) {
 156                         if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
 157                                 printk ("ext_count_free: error while reading free blocks list\n");
 158                                 block = 0;
 159                         } else {
 160                                 efb = (struct ext_free_block *) bh->b_data;
 161                                 count += efb->count + 1;
 162                                 block = efb->next;
 163                                 brelse (bh);
 164                         }
 165                 }
 166         }
 167 printk("ext_count_free_blocks: stored = %d, computed = %d\n",
 168         sb->u.ext_sb.s_freeblockscount, count);
 169         unlock_super (sb);
 170         return count;
 171 #else
 172         return sb->u.ext_sb.s_freeblockscount;
 173 #endif
 174 }
 175 
 176 void ext_free_inode(struct inode * inode)
     /* [previous][next][first][last][top][bottom][index][help] */
 177 {
 178         struct buffer_head * bh;
 179         struct ext_free_inode * efi;
 180         unsigned long block;
 181 
 182         if (!inode)
 183                 return;
 184         if (!inode->i_dev) {
 185                 printk("free_inode: inode has no device\n");
 186                 return;
 187         }
 188         if (inode->i_count != 1) {
 189                 printk("free_inode: inode has count=%d\n",inode->i_count);
 190                 return;
 191         }
 192         if (inode->i_nlink) {
 193                 printk("free_inode: inode has nlink=%d\n",inode->i_nlink);
 194                 return;
 195         }
 196         if (!inode->i_sb) {
 197                 printk("free_inode: inode on nonexistent device\n");
 198                 return;
 199         }
 200         lock_super (inode->i_sb);
 201         if (inode->i_ino < 1 || inode->i_ino > inode->i_sb->u.ext_sb.s_ninodes) {
 202                 printk("free_inode: inode 0 or nonexistent inode\n");
 203                 unlock_super (inode->i_sb);
 204                 return;
 205         }
 206         if (inode->i_sb->u.ext_sb.s_firstfreeinodeblock)
 207                 efi = ((struct ext_free_inode *) inode->i_sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 208                         (inode->i_sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
 209         if (!inode->i_sb->u.ext_sb.s_firstfreeinodeblock || efi->count == 14) {
 210 #ifdef EXTFS_DEBUG
 211 printk("ext_free_inode: inode full, skipping to %d\n", inode->i_ino);
 212 #endif
 213                 if (inode->i_sb->u.ext_sb.s_firstfreeinodeblock)
 214                         brelse (inode->i_sb->u.ext_sb.s_firstfreeinodeblock);
 215                 block = 2 + (inode->i_ino - 1) / EXT_INODES_PER_BLOCK;
 216                 if (!(bh = bread(inode->i_dev, block, inode->i_sb->s_blocksize)))
 217                         panic("ext_free_inode: unable to read inode block\n");
 218                 efi = ((struct ext_free_inode *) bh->b_data) +
 219                         (inode->i_ino - 1) % EXT_INODES_PER_BLOCK;
 220                 efi->next = inode->i_sb->u.ext_sb.s_firstfreeinodenumber;
 221                 efi->count = 0;
 222                 inode->i_sb->u.ext_sb.s_firstfreeinodenumber = inode->i_ino;
 223                 inode->i_sb->u.ext_sb.s_firstfreeinodeblock = bh;
 224         } else {
 225                 efi->free[efi->count++] = inode->i_ino;
 226         }
 227         inode->i_sb->u.ext_sb.s_freeinodescount ++;
 228         inode->i_sb->s_dirt = 1;
 229         inode->i_sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
 230         unlock_super (inode->i_sb);
 231         clear_inode(inode);
 232 }
 233 
 234 struct inode * ext_new_inode(const struct inode * dir)
     /* [previous][next][first][last][top][bottom][index][help] */
 235 {
 236         struct super_block * sb;
 237         struct inode * inode;
 238         struct ext_free_inode * efi;
 239         unsigned long block;
 240         int j;
 241 
 242         if (!dir || !(inode=get_empty_inode()))
 243                 return NULL;
 244         sb = dir->i_sb;
 245         inode->i_sb = sb;
 246         inode->i_flags = sb->s_flags;
 247         if (!sb->u.ext_sb.s_firstfreeinodeblock)
 248                 return 0;
 249         lock_super (sb);
 250         efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 251                 (sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
 252         if (efi->count) {
 253                 j = efi->free[--efi->count];
 254                 sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
 255         } else {
 256 #ifdef EXTFS_DEBUG
 257 printk("ext_free_inode: inode empty, skipping to %d\n", efi->next);
 258 #endif
 259                 j = sb->u.ext_sb.s_firstfreeinodenumber;
 260                 if (efi->next > sb->u.ext_sb.s_ninodes) {
 261                         printk ("efi->next = %d\n", efi->next);
 262                         panic ("ext_new_inode: bad inode number in free list\n");
 263                 }
 264                 sb->u.ext_sb.s_firstfreeinodenumber = efi->next;
 265                 block = 2 + (((unsigned long) efi->next) - 1) / EXT_INODES_PER_BLOCK;
 266                 brelse (sb->u.ext_sb.s_firstfreeinodeblock);
 267                 if (!sb->u.ext_sb.s_firstfreeinodenumber) {
 268                         sb->u.ext_sb.s_firstfreeinodeblock = NULL;
 269                 } else {
 270                         if (!(sb->u.ext_sb.s_firstfreeinodeblock =
 271                             bread(sb->s_dev, block, sb->s_blocksize)))
 272                                 panic ("ext_new_inode: unable to read next free inode block\n");
 273                 }
 274         }
 275         sb->u.ext_sb.s_freeinodescount --;
 276         sb->s_dirt = 1;
 277         inode->i_count = 1;
 278         inode->i_nlink = 1;
 279         inode->i_dev = sb->s_dev;
 280         inode->i_uid = current->euid;
 281         inode->i_gid = (dir->i_mode & S_ISGID) ? dir->i_gid : current->egid;
 282         inode->i_dirt = 1;
 283         inode->i_ino = j;
 284         inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
 285         inode->i_op = NULL;
 286         inode->i_blocks = inode->i_blksize = 0;
 287 #ifdef EXTFS_DEBUG
 288 printk("ext_new_inode : allocating inode %d\n", inode->i_ino);
 289 #endif
 290         unlock_super (sb);
 291         return inode;
 292 }
 293 
 294 unsigned long ext_count_free_inodes(struct super_block *sb)
     /* [previous][next][first][last][top][bottom][index][help] */
 295 {
 296 #ifdef EXTFS_DEBUG
 297         struct buffer_head * bh;
 298         struct ext_free_inode * efi;
 299         unsigned long count, block, ino;
 300 
 301         lock_super (sb);
 302         if (!sb->u.ext_sb.s_firstfreeinodeblock)
 303                 count = 0;
 304         else {
 305                 efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 306                         ((sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK);
 307                 count = efi->count + 1;
 308                 ino = efi->next;
 309                 while (ino) {
 310                         if (ino < 1 || ino > sb->u.ext_sb.s_ninodes) {
 311                                 printk ("u.ext_sb.s_firstfreeinodenumber = %d, ino = %d\n", 
 312                                         (int) sb->u.ext_sb.s_firstfreeinodenumber,ino);
 313                                 panic ("ext_count_fre_inodes: bad inode number in free list\n");
 314                         }
 315                         block = 2 + ((ino - 1) / EXT_INODES_PER_BLOCK);
 316                         if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
 317                                 printk ("ext_count_free_inodes: error while reading free inodes list\n");
 318                                 block = 0;
 319                         } else {
 320                                 efi = ((struct ext_free_inode *) bh->b_data) +
 321                                         ((ino - 1) % EXT_INODES_PER_BLOCK);
 322                                 count += efi->count + 1;
 323                                 ino = efi->next;
 324                                 brelse (bh);
 325                         }
 326                 }
 327         }
 328 printk("ext_count_free_inodes: stored = %d, computed = %d\n",
 329         sb->u.ext_sb.s_freeinodescount, count);
 330         unlock_super (sb);
 331         return count;
 332 #else
 333         return sb->u.ext_sb.s_freeinodescount;
 334 #endif
 335 }

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