lib/ext2fs/alloc.c

   1 /*
   2  * alloc.c --- allocate new inodes, blocks for ext2fs
   3  *
   4  * Copyright (C) 1993 Theodore Ts'o.  This file may be redistributed
   5  * under the terms of the GNU Public License.
   6  */
   7
   8 #include <stdio.h>
   9 #include <unistd.h>
  10 #include <stdlib.h>
  11 #include <time.h>
  12 #include <sys/stat.h>
  13 #include <sys/types.h>
  14 #if HAVE_ERRNO_H
  15 #include <errno.h>
  16 #endif
  17
  18 #include <linux/ext2_fs.h>
  19
  20 #include "ext2fs.h"
  21
  22 /*
  23  * Right now, just search forward from the parent directory's block
  24  * group to find the next free inode.
  25  *
  26  * Should have a special policy for directories.
  27  */
  28 errcode_t ext2fs_new_inode(ext2_filsys fs, ino_t dir, int mode,
  29                            ext2fs_inode_bitmap map, ino_t *ret)
  30 {
  31         int     dir_group = 0;
  32         ino_t   i;
  33         ino_t   start_inode;
  34
  35         EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
  36
  37         if (!map)
  38                 map = fs->inode_map;
  39         if (!map)
  40                 return EXT2_ET_NO_INODE_BITMAP;
  41
  42         if (dir > 0)
  43                 dir_group = (dir - 1) / EXT2_INODES_PER_GROUP(fs->super);
  44
  45         start_inode = (dir_group * EXT2_INODES_PER_GROUP(fs->super)) + 1;
  46         if (start_inode < EXT2_FIRST_INODE(fs->super))
  47                 start_inode = EXT2_FIRST_INODE(fs->super);
  48         i = start_inode;
  49
  50         do {
  51                 if (!ext2fs_test_inode_bitmap(map, i))
  52                         break;
  53                 i++;
  54                 if (i > fs->super->s_inodes_count)
  55                         i = EXT2_FIRST_INODE(fs->super);
  56         } while (i != start_inode);
  57
  58         if (ext2fs_test_inode_bitmap(map, i))
  59                 return ENOSPC;
  60         *ret = i;
  61         return 0;
  62 }
  63
  64 /*
  65  * Stupid algorithm --- we now just search forward starting from the
  66  * goal.  Should put in a smarter one someday....
  67  */
  68 errcode_t ext2fs_new_block(ext2_filsys fs, blk_t goal,
  69                            ext2fs_block_bitmap map, blk_t *ret)
  70 {
  71         blk_t   i = goal;
  72
  73         EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
  74
  75         if (!map)
  76                 map = fs->block_map;
  77         if (!map)
  78                 return EXT2_ET_NO_BLOCK_BITMAP;
  79         if (!i)
  80                 i = fs->super->s_first_data_block;
  81         do {
  82                 if (!ext2fs_test_block_bitmap(map, i)) {
  83                         *ret = i;
  84                         return 0;
  85                 }
  86                 i++;
  87                 if (i > fs->super->s_blocks_count)
  88                         i = fs->super->s_first_data_block;
  89         } while (i != goal);
  90         return ENOSPC;
  91 }
  92
  93 static int check_blocks_free(ext2_filsys fs, ext2fs_block_bitmap map,
  94                              blk_t blk, int num)
  95 {
  96         int     i;
  97
  98         for (i=0; i < num; i++) {
  99                 if ((blk+i) > fs->super->s_blocks_count)
 100                         return 0;
 101                 if (ext2fs_test_block_bitmap(map, blk+i))
 102                         return 0;
 103         }
 104         return 1;
 105 }
 106
 107 errcode_t ext2fs_get_free_blocks(ext2_filsys fs, blk_t start, blk_t finish,
 108                                  int num, ext2fs_block_bitmap map, blk_t *ret)
 109 {
 110         blk_t   b = start;
 111
 112         EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
 113
 114         if (!map)
 115                 map = fs->block_map;
 116         if (!map)
 117                 return EXT2_ET_NO_BLOCK_BITMAP;
 118         if (!b)
 119                 b = fs->super->s_first_data_block;
 120         if (!finish)
 121                 finish = start;
 122         if (!num)
 123                 num = 1;
 124         do {
 125                 if (check_blocks_free(fs, map, b, num)) {
 126                         *ret = b;
 127                         return 0;
 128                 }
 129                 b++;
 130                 if (b > fs->super->s_blocks_count)
 131                         b = fs->super->s_first_data_block;
 132         } while (b != finish);
 133         return ENOSPC;
 134 }
 135