lib/ext2fs/alloc.c

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