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

DEFINITIONS
