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 
  38 #define clear_block(addr) \
  39 __asm__("cld\n\t" \
  40         "rep\n\t" \
  41         "stosl" \
  42         ::"a" (0),"c" (BLOCK_SIZE/4),"D" ((long) (addr)):"cx","di")
  43 
  44 void ext_free_block(int dev, int block)
     /* [previous][next][first][last][top][bottom][index][help] */
  45 {
  46         struct super_block * sb;
  47         struct buffer_head * bh;
  48         struct ext_free_block * efb;
  49 
  50         if (!(sb = get_super(dev)))
  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(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 (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         free_super (sb);
  84         return;
  85 }
  86 
  87 int ext_new_block(int dev)
     /* [previous][next][first][last][top][bottom][index][help] */
  88 {
  89         struct buffer_head * bh;
  90         struct super_block * sb;
  91         struct ext_free_block * efb;
  92         int j;
  93 
  94         if (!(sb = get_super(dev)))
  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 (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(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         free_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         free_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                 memset(inode,0,sizeof(*inode));
 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                 free_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         free_super (inode->i_sb);
 231         memset(inode,0,sizeof(*inode));
 232 }
 233 
 234 struct inode * ext_new_inode(int dev)
     /* [previous][next][first][last][top][bottom][index][help] */
 235 {
 236         struct inode * inode;
 237         struct ext_free_inode * efi;
 238         unsigned long block;
 239         int j;
 240 
 241         if (!(inode=get_empty_inode()))
 242                 return NULL;
 243         if (!(inode->i_sb = get_super(dev))) {
 244                 printk("new_inode: unknown device\n");
 245                 iput(inode);
 246                 return NULL;
 247         }
 248         inode->i_flags = inode->i_sb->s_flags;
 249         if (!inode->i_sb->u.ext_sb.s_firstfreeinodeblock)
 250                 return 0;
 251         lock_super (inode->i_sb);
 252         efi = ((struct ext_free_inode *) inode->i_sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 253                 (inode->i_sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK;
 254         if (efi->count) {
 255                 j = efi->free[--efi->count];
 256                 inode->i_sb->u.ext_sb.s_firstfreeinodeblock->b_dirt = 1;
 257         } else {
 258 #ifdef EXTFS_DEBUG
 259 printk("ext_free_inode: inode empty, skipping to %d\n", efi->next);
 260 #endif
 261                 j = inode->i_sb->u.ext_sb.s_firstfreeinodenumber;
 262                 if (efi->next > inode->i_sb->u.ext_sb.s_ninodes) {
 263                         printk ("efi->next = %d\n", efi->next);
 264                         panic ("ext_new_inode: bad inode number in free list\n");
 265                 }
 266                 inode->i_sb->u.ext_sb.s_firstfreeinodenumber = efi->next;
 267                 block = 2 + (((unsigned long) efi->next) - 1) / EXT_INODES_PER_BLOCK;
 268                 brelse (inode->i_sb->u.ext_sb.s_firstfreeinodeblock);
 269                 if (!inode->i_sb->u.ext_sb.s_firstfreeinodenumber) {
 270                         inode->i_sb->u.ext_sb.s_firstfreeinodeblock = NULL;
 271                 } else {
 272                         if (!(inode->i_sb->u.ext_sb.s_firstfreeinodeblock = bread (dev, block, inode->i_sb->s_blocksize)))
 273                                 panic ("ext_new_inode: unable to read next free inode block\n");
 274                 }
 275         }
 276         inode->i_sb->u.ext_sb.s_freeinodescount --;
 277         inode->i_sb->s_dirt = 1;
 278         inode->i_count = 1;
 279         inode->i_nlink = 1;
 280         inode->i_dev = dev;
 281         inode->i_uid = current->euid;
 282         inode->i_gid = current->egid;
 283         inode->i_dirt = 1;
 284         inode->i_ino = j;
 285         inode->i_mtime = inode->i_atime = inode->i_ctime = CURRENT_TIME;
 286         inode->i_op = NULL;
 287         inode->i_blocks = inode->i_blksize = 0;
 288 #ifdef EXTFS_DEBUG
 289 printk("ext_new_inode : allocating inode %d\n", inode->i_ino);
 290 #endif
 291         free_super (inode->i_sb);
 292         return inode;
 293 }
 294 
 295 unsigned long ext_count_free_inodes(struct super_block *sb)
     /* [previous][next][first][last][top][bottom][index][help] */
 296 {
 297 #ifdef EXTFS_DEBUG
 298         struct buffer_head * bh;
 299         struct ext_free_inode * efi;
 300         unsigned long count, block, ino;
 301 
 302         lock_super (sb);
 303         if (!sb->u.ext_sb.s_firstfreeinodeblock)
 304                 count = 0;
 305         else {
 306                 efi = ((struct ext_free_inode *) sb->u.ext_sb.s_firstfreeinodeblock->b_data) +
 307                         ((sb->u.ext_sb.s_firstfreeinodenumber-1)%EXT_INODES_PER_BLOCK);
 308                 count = efi->count + 1;
 309                 ino = efi->next;
 310                 while (ino) {
 311                         if (ino < 1 || ino > sb->u.ext_sb.s_ninodes) {
 312                                 printk ("u.ext_sb.s_firstfreeinodenumber = %d, ino = %d\n", 
 313                                         (int) sb->u.ext_sb.s_firstfreeinodenumber,ino);
 314                                 panic ("ext_count_fre_inodes: bad inode number in free list\n");
 315                         }
 316                         block = 2 + ((ino - 1) / EXT_INODES_PER_BLOCK);
 317                         if (!(bh = bread (sb->s_dev, block, sb->s_blocksize))) {
 318                                 printk ("ext_count_free_inodes: error while reading free inodes list\n");
 319                                 block = 0;
 320                         } else {
 321                                 efi = ((struct ext_free_inode *) bh->b_data) +
 322                                         ((ino - 1) % EXT_INODES_PER_BLOCK);
 323                                 count += efi->count + 1;
 324                                 ino = efi->next;
 325                                 brelse (bh);
 326                         }
 327                 }
 328         }
 329 printk("ext_count_free_inodes: stored = %d, computed = %d\n",
 330         sb->u.ext_sb.s_freeinodescount, count);
 331         free_super (sb);
 332         return count;
 333 #else
 334         return sb->u.ext_sb.s_freeinodescount;
 335 #endif
 336 }

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