i386/linux/linux-0.99/fs/ext/freelists.c

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