lib/ext2fs/alloc_tables.c

   1 /*
   2  * alloc_tables.c --- Allocate tables for a newly initialized
   3  * filesystem.  Used by mke2fs when initializing a filesystem
   4  *
   5  * Copyright (C) 1996 Theodore Ts'o.
   6  *
   7  * %Begin-Header%
   8  * This file may be redistributed under the terms of the GNU Library
   9  * General Public License, version 2.
  10  * %End-Header%
  11  */
  12
  13 #include "config.h"
  14 #include <stdio.h>
  15 #include <string.h>
  16 #if HAVE_UNISTD_H
  17 #include <unistd.h>
  18 #endif
  19 #include <fcntl.h>
  20 #include <time.h>
  21 #if HAVE_SYS_STAT_H
  22 #include <sys/stat.h>
  23 #endif
  24 #if HAVE_SYS_TYPES_H
  25 #include <sys/types.h>
  26 #endif
  27
  28 #include "ext2_fs.h"
  29 #include "ext2fs.h"
  30 #include "ext2fsP.h"
  31
  32 /*
  33  * This routine searches for free blocks that can allocate a full
  34  * group of bitmaps or inode tables for a flexbg group.  Returns the
  35  * block number with a correct offset were the bitmaps and inode
  36  * tables can be allocated continously and in order.
  37  */
  38 static blk64_t flexbg_offset(ext2_filsys fs, dgrp_t group, blk64_t start_blk,
  39                              ext2fs_block_bitmap bmap, int rem_grp,
  40                              int elem_size)
  41 {
  42         int             flexbg, flexbg_size, size;
  43         blk64_t         last_blk, first_free = 0;
  44         dgrp_t          last_grp;
  45
  46         flexbg_size = 1 << fs->super->s_log_groups_per_flex;
  47         flexbg = group / flexbg_size;
  48         size = rem_grp * elem_size;
  49
  50         if (size > (int) (fs->super->s_blocks_per_group / 8))
  51                 size = (int) fs->super->s_blocks_per_group / 8;
  52
  53         /*
  54          * Don't do a long search if the previous block
  55          * search is still valid.
  56          */
  57         if (start_blk && ext2fs_test_block_bitmap_range2(bmap, start_blk,
  58                                                          elem_size))
  59                 return start_blk;
  60
  61         start_blk = ext2fs_group_first_block2(fs, flexbg_size * flexbg);
  62         last_grp = group | (flexbg_size - 1);
  63         if (last_grp > fs->group_desc_count-1)
  64                 last_grp = fs->group_desc_count-1;
  65         last_blk = ext2fs_group_last_block2(fs, last_grp);
  66
  67         /* Find the first available block */
  68         if (ext2fs_get_free_blocks2(fs, start_blk, last_blk, size,
  69                                     bmap, &first_free) == 0)
  70                 return first_free;
  71
  72         if (ext2fs_get_free_blocks2(fs, start_blk, last_blk, elem_size,
  73                                    bmap, &first_free) == 0)
  74                 return first_free;
  75
  76         if (ext2fs_get_free_blocks2(fs, 0, last_blk, elem_size, bmap,
  77                                     &first_free) == 0)
  78                 return first_free;
  79
  80         return first_free;
  81 }
  82
  83 errcode_t ext2fs_allocate_group_table(ext2_filsys fs, dgrp_t group,
  84                                       ext2fs_block_bitmap bmap)
  85 {
  86         unsigned int    j;
  87         errcode_t       retval;
  88         blk64_t         group_blk, start_blk, last_blk, new_blk, blk;
  89         dgrp_t          last_grp = 0;
  90         int             rem_grps = 0, flexbg_size = 0;
  91
  92         group_blk = ext2fs_group_first_block2(fs, group);
  93         last_blk = ext2fs_group_last_block2(fs, group);
  94
  95         if (!bmap)
  96                 bmap = fs->block_map;
  97
  98         if (EXT2_HAS_INCOMPAT_FEATURE(fs->super,
  99                                       EXT4_FEATURE_INCOMPAT_FLEX_BG) &&
 100             fs->super->s_log_groups_per_flex) {
 101                 flexbg_size = 1 << fs->super->s_log_groups_per_flex;
 102                 last_grp = group | (flexbg_size - 1);
 103                 if (last_grp > fs->group_desc_count-1)
 104                         last_grp = fs->group_desc_count-1;
 105                 rem_grps = last_grp - group + 1;
 106         }
 107
 108         /*
 109          * Allocate the block and inode bitmaps, if necessary
 110          */
 111         if (fs->stride) {
 112                 retval = ext2fs_get_free_blocks2(fs, group_blk, last_blk,
 113                                                  1, bmap, &start_blk);
 114                 if (retval)
 115                         return retval;
 116                 start_blk += fs->inode_blocks_per_group;
 117                 start_blk += ((fs->stride * group) %
 118                               (last_blk - start_blk + 1));
 119                 if (start_blk >= last_blk)
 120                         start_blk = group_blk;
 121         } else
 122                 start_blk = group_blk;
 123
 124         if (flexbg_size) {
 125                 blk64_t prev_block = 0;
 126
 127                 if (group % flexbg_size)
 128                         prev_block = ext2fs_block_bitmap_loc(fs, group - 1) + 1;
 129                 start_blk = flexbg_offset(fs, group, prev_block, bmap,
 130                                           rem_grps, 1);
 131                 last_blk = ext2fs_group_last_block2(fs, last_grp);
 132         }
 133
 134         if (!ext2fs_block_bitmap_loc(fs, group)) {
 135                 retval = ext2fs_get_free_blocks2(fs, start_blk, last_blk,
 136                                                  1, bmap, &new_blk);
 137                 if (retval == EXT2_ET_BLOCK_ALLOC_FAIL)
 138                         retval = ext2fs_get_free_blocks2(fs, group_blk,
 139                                         last_blk, 1, bmap, &new_blk);
 140                 if (retval)
 141                         return retval;
 142                 ext2fs_mark_block_bitmap2(bmap, new_blk);
 143                 ext2fs_block_bitmap_loc_set(fs, group, new_blk);
 144                 if (flexbg_size) {
 145                         dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk);
 146                         ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1);
 147                         ext2fs_free_blocks_count_add(fs->super, -1);
 148                         ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT);
 149                         ext2fs_group_desc_csum_set(fs, gr);
 150                 }
 151         }
 152
 153         if (flexbg_size) {
 154                 blk64_t prev_block = 0;
 155                 if (group % flexbg_size)
 156                         prev_block = ext2fs_inode_bitmap_loc(fs, group - 1) + 1;
 157                 else
 158                         prev_block = ext2fs_block_bitmap_loc(fs, group) +
 159                                 flexbg_size;
 160                 start_blk = flexbg_offset(fs, group, prev_block, bmap,
 161                                           rem_grps, 1);
 162                 last_blk = ext2fs_group_last_block2(fs, last_grp);
 163         }
 164
 165         if (!ext2fs_inode_bitmap_loc(fs, group)) {
 166                 retval = ext2fs_get_free_blocks2(fs, start_blk, last_blk,
 167                                                  1, bmap, &new_blk);
 168                 if (retval == EXT2_ET_BLOCK_ALLOC_FAIL)
 169                         retval = ext2fs_get_free_blocks2(fs, group_blk,
 170                                          last_blk, 1, bmap, &new_blk);
 171                 if (retval)
 172                         return retval;
 173                 ext2fs_mark_block_bitmap2(bmap, new_blk);
 174                 ext2fs_inode_bitmap_loc_set(fs, group, new_blk);
 175                 if (flexbg_size) {
 176                         dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk);
 177                         ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1);
 178                         ext2fs_free_blocks_count_add(fs->super, -1);
 179                         ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT);
 180                         ext2fs_group_desc_csum_set(fs, gr);
 181                 }
 182         }
 183
 184         /*
 185          * Allocate the inode table
 186          */
 187         if (flexbg_size) {
 188                 blk64_t prev_block = 0;
 189
 190                 if (group % flexbg_size)
 191                         prev_block = ext2fs_inode_table_loc(fs, group - 1) +
 192                                 fs->inode_blocks_per_group;
 193                 else
 194                         prev_block = ext2fs_inode_bitmap_loc(fs, group) +
 195                                 flexbg_size;
 196
 197                 group_blk = flexbg_offset(fs, group, prev_block, bmap,
 198                                           rem_grps, fs->inode_blocks_per_group);
 199                 last_blk = ext2fs_group_last_block2(fs, last_grp);
 200         }
 201
 202         if (!ext2fs_inode_table_loc(fs, group)) {
 203                 retval = ext2fs_get_free_blocks2(fs, group_blk, last_blk,
 204                                                 fs->inode_blocks_per_group,
 205                                                 bmap, &new_blk);
 206                 if (retval)
 207                         return retval;
 208                 for (j=0, blk = new_blk;
 209                      j < fs->inode_blocks_per_group;
 210                      j++, blk++) {
 211                         ext2fs_mark_block_bitmap2(bmap, blk);
 212                         if (flexbg_size) {
 213                                 dgrp_t gr = ext2fs_group_of_blk2(fs, blk);
 214                                 ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1);
 215                                 ext2fs_free_blocks_count_add(fs->super, -1);
 216                                 ext2fs_bg_flags_clear(fs, gr,
 217                                                      EXT2_BG_BLOCK_UNINIT);
 218                                 ext2fs_group_desc_csum_set(fs, gr);
 219                         }
 220                 }
 221                 ext2fs_inode_table_loc_set(fs, group, new_blk);
 222         }
 223         ext2fs_group_desc_csum_set(fs, group);
 224         return 0;
 225 }
 226
 227 errcode_t ext2fs_allocate_tables(ext2_filsys fs)
 228 {
 229         errcode_t       retval;
 230         dgrp_t          i;
 231         struct ext2fs_numeric_progress_struct progress;
 232
 233         ext2fs_numeric_progress_init(fs, &progress, NULL,
 234                                      fs->group_desc_count);
 235
 236         for (i = 0; i < fs->group_desc_count; i++) {
 237                 ext2fs_numeric_progress_update(fs, &progress, i);
 238                 retval = ext2fs_allocate_group_table(fs, i, fs->block_map);
 239                 if (retval)
 240                         return retval;
 241         }
 242         ext2fs_numeric_progress_close(fs, &progress, NULL);
 243         return 0;
 244 }
 245