alloc.c revision c1a1e7fc24d6e37f931bbb8eeb29c90243f0a55d
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 Library 8 * General Public License, version 2. 9 * %End-Header% 10 */ 11 12#include "config.h" 13#include <stdio.h> 14#if HAVE_UNISTD_H 15#include <unistd.h> 16#endif 17#include <time.h> 18#include <string.h> 19#if HAVE_SYS_STAT_H 20#include <sys/stat.h> 21#endif 22#if HAVE_SYS_TYPES_H 23#include <sys/types.h> 24#endif 25 26#include "ext2_fs.h" 27#include "ext2fs.h" 28 29/* 30 * Check for uninit block bitmaps and deal with them appropriately 31 */ 32static void check_block_uninit(ext2_filsys fs, ext2fs_block_bitmap map, 33 dgrp_t group) 34{ 35 blk_t i; 36 blk64_t blk, super_blk, old_desc_blk, new_desc_blk; 37 int old_desc_blocks; 38 39 if (!(EXT2_HAS_RO_COMPAT_FEATURE(fs->super, 40 EXT4_FEATURE_RO_COMPAT_GDT_CSUM)) || 41 !(ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT))) 42 return; 43 44 blk = (group * fs->super->s_blocks_per_group) + 45 fs->super->s_first_data_block; 46 47 ext2fs_super_and_bgd_loc2(fs, group, &super_blk, 48 &old_desc_blk, &new_desc_blk, 0); 49 50 if (fs->super->s_feature_incompat & 51 EXT2_FEATURE_INCOMPAT_META_BG) 52 old_desc_blocks = fs->super->s_first_meta_bg; 53 else 54 old_desc_blocks = fs->desc_blocks + fs->super->s_reserved_gdt_blocks; 55 56 for (i=0; i < fs->super->s_blocks_per_group; i++, blk++) 57 ext2fs_fast_unmark_block_bitmap2(map, blk); 58 59 blk = (group * fs->super->s_blocks_per_group) + 60 fs->super->s_first_data_block; 61 for (i=0; i < fs->super->s_blocks_per_group; i++, blk++) { 62 if ((blk == super_blk) || 63 (old_desc_blk && old_desc_blocks && 64 (blk >= old_desc_blk) && 65 (blk < old_desc_blk + old_desc_blocks)) || 66 (new_desc_blk && (blk == new_desc_blk)) || 67 (blk == ext2fs_block_bitmap_loc(fs, group)) || 68 (blk == ext2fs_inode_bitmap_loc(fs, group)) || 69 (blk >= ext2fs_inode_table_loc(fs, group) && 70 (blk < ext2fs_inode_table_loc(fs, group) 71 + fs->inode_blocks_per_group))) 72 ext2fs_fast_mark_block_bitmap2(map, blk); 73 } 74 ext2fs_bg_flags_clear(fs, group, EXT2_BG_BLOCK_UNINIT); 75 ext2fs_group_desc_csum_set(fs, group); 76} 77 78/* 79 * Check for uninit inode bitmaps and deal with them appropriately 80 */ 81static void check_inode_uninit(ext2_filsys fs, ext2fs_inode_bitmap map, 82 dgrp_t group) 83{ 84 ext2_ino_t i, ino; 85 86 if (!(EXT2_HAS_RO_COMPAT_FEATURE(fs->super, 87 EXT4_FEATURE_RO_COMPAT_GDT_CSUM)) || 88 !(ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT))) 89 return; 90 91 ino = (group * fs->super->s_inodes_per_group) + 1; 92 for (i=0; i < fs->super->s_inodes_per_group; i++, ino++) 93 ext2fs_fast_unmark_inode_bitmap2(map, ino); 94 95 ext2fs_bg_flags_clear(fs, group, EXT2_BG_INODE_UNINIT); 96 check_block_uninit(fs, fs->block_map, group); 97} 98 99/* 100 * Right now, just search forward from the parent directory's block 101 * group to find the next free inode. 102 * 103 * Should have a special policy for directories. 104 */ 105errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir, 106 int mode EXT2FS_ATTR((unused)), 107 ext2fs_inode_bitmap map, ext2_ino_t *ret) 108{ 109 ext2_ino_t start_inode = 0; 110 ext2_ino_t i, ino_in_group, upto, first_zero; 111 errcode_t retval; 112 dgrp_t group; 113 114 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 115 116 if (!map) 117 map = fs->inode_map; 118 if (!map) 119 return EXT2_ET_NO_INODE_BITMAP; 120 121 if (dir > 0) { 122 group = (dir - 1) / EXT2_INODES_PER_GROUP(fs->super); 123 start_inode = (group * EXT2_INODES_PER_GROUP(fs->super)) + 1; 124 } 125 if (start_inode < EXT2_FIRST_INODE(fs->super)) 126 start_inode = EXT2_FIRST_INODE(fs->super); 127 if (start_inode > fs->super->s_inodes_count) 128 return EXT2_ET_INODE_ALLOC_FAIL; 129 i = start_inode; 130 do { 131 ino_in_group = (i - 1) % EXT2_INODES_PER_GROUP(fs->super); 132 group = (i - 1) / EXT2_INODES_PER_GROUP(fs->super); 133 134 check_inode_uninit(fs, map, group); 135 upto = i + (EXT2_INODES_PER_GROUP(fs->super) - ino_in_group); 136 if (i < start_inode && upto >= start_inode) 137 upto = start_inode - 1; 138 if (upto > fs->super->s_inodes_count) 139 upto = fs->super->s_inodes_count; 140 141 retval = ext2fs_find_first_zero_inode_bitmap2(map, i, upto, 142 &first_zero); 143 if (retval == 0) { 144 i = first_zero; 145 break; 146 } 147 if (retval != ENOENT) 148 return EXT2_ET_INODE_ALLOC_FAIL; 149 i = upto + 1; 150 if (i > fs->super->s_inodes_count) 151 i = EXT2_FIRST_INODE(fs->super); 152 } while (i != start_inode); 153 154 if (ext2fs_test_inode_bitmap2(map, i)) 155 return EXT2_ET_INODE_ALLOC_FAIL; 156 *ret = i; 157 return 0; 158} 159 160/* 161 * Stupid algorithm --- we now just search forward starting from the 162 * goal. Should put in a smarter one someday.... 163 */ 164errcode_t ext2fs_new_block2(ext2_filsys fs, blk64_t goal, 165 ext2fs_block_bitmap map, blk64_t *ret) 166{ 167 blk64_t i; 168 int c_ratio; 169 170 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 171 172 if (!map) 173 map = fs->block_map; 174 if (!map) 175 return EXT2_ET_NO_BLOCK_BITMAP; 176 if (!goal || (goal >= ext2fs_blocks_count(fs->super))) 177 goal = fs->super->s_first_data_block; 178 i = goal; 179 c_ratio = 1 << ext2fs_get_bitmap_granularity(map); 180 if (c_ratio > 1) 181 goal &= ~EXT2FS_CLUSTER_MASK(fs); 182 check_block_uninit(fs, map, 183 (i - fs->super->s_first_data_block) / 184 EXT2_BLOCKS_PER_GROUP(fs->super)); 185 do { 186 if (((i - fs->super->s_first_data_block) % 187 EXT2_BLOCKS_PER_GROUP(fs->super)) == 0) 188 check_block_uninit(fs, map, 189 (i - fs->super->s_first_data_block) / 190 EXT2_BLOCKS_PER_GROUP(fs->super)); 191 192 if (!ext2fs_fast_test_block_bitmap2(map, i)) { 193 *ret = i; 194 return 0; 195 } 196 i = (i + c_ratio) & ~(c_ratio - 1); 197 if (i >= ext2fs_blocks_count(fs->super)) 198 i = fs->super->s_first_data_block; 199 } while (i != goal); 200 return EXT2_ET_BLOCK_ALLOC_FAIL; 201} 202 203errcode_t ext2fs_new_block(ext2_filsys fs, blk_t goal, 204 ext2fs_block_bitmap map, blk_t *ret) 205{ 206 errcode_t retval; 207 blk64_t val; 208 retval = ext2fs_new_block2(fs, goal, map, &val); 209 if (!retval) 210 *ret = (blk_t) val; 211 return retval; 212} 213 214/* 215 * This function zeros out the allocated block, and updates all of the 216 * appropriate filesystem records. 217 */ 218errcode_t ext2fs_alloc_block2(ext2_filsys fs, blk64_t goal, 219 char *block_buf, blk64_t *ret) 220{ 221 errcode_t retval; 222 blk64_t block; 223 char *buf = 0; 224 225 if (!block_buf) { 226 retval = ext2fs_get_mem(fs->blocksize, &buf); 227 if (retval) 228 return retval; 229 block_buf = buf; 230 } 231 memset(block_buf, 0, fs->blocksize); 232 233 if (fs->get_alloc_block) { 234 retval = (fs->get_alloc_block)(fs, goal, &block); 235 if (retval) 236 goto fail; 237 } else { 238 if (!fs->block_map) { 239 retval = ext2fs_read_block_bitmap(fs); 240 if (retval) 241 goto fail; 242 } 243 244 retval = ext2fs_new_block2(fs, goal, 0, &block); 245 if (retval) 246 goto fail; 247 } 248 249 retval = io_channel_write_blk64(fs->io, block, 1, block_buf); 250 if (retval) 251 goto fail; 252 253 ext2fs_block_alloc_stats2(fs, block, +1); 254 *ret = block; 255 256fail: 257 if (buf) 258 ext2fs_free_mem(&buf); 259 return retval; 260} 261 262errcode_t ext2fs_alloc_block(ext2_filsys fs, blk_t goal, 263 char *block_buf, blk_t *ret) 264{ 265 errcode_t retval; 266 blk64_t val; 267 retval = ext2fs_alloc_block2(fs, goal, block_buf, &val); 268 if (!retval) 269 *ret = (blk_t) val; 270 return retval; 271} 272 273errcode_t ext2fs_get_free_blocks2(ext2_filsys fs, blk64_t start, blk64_t finish, 274 int num, ext2fs_block_bitmap map, blk64_t *ret) 275{ 276 blk64_t b = start; 277 int c_ratio; 278 279 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 280 281 if (!map) 282 map = fs->block_map; 283 if (!map) 284 return EXT2_ET_NO_BLOCK_BITMAP; 285 if (!b) 286 b = fs->super->s_first_data_block; 287 if (!finish) 288 finish = start; 289 if (!num) 290 num = 1; 291 c_ratio = 1 << ext2fs_get_bitmap_granularity(map); 292 b &= ~(c_ratio - 1); 293 finish &= ~(c_ratio -1); 294 do { 295 if (b+num-1 > ext2fs_blocks_count(fs->super)) 296 b = fs->super->s_first_data_block; 297 if (ext2fs_fast_test_block_bitmap_range2(map, b, num)) { 298 *ret = b; 299 return 0; 300 } 301 b += c_ratio; 302 } while (b != finish); 303 return EXT2_ET_BLOCK_ALLOC_FAIL; 304} 305 306errcode_t ext2fs_get_free_blocks(ext2_filsys fs, blk_t start, blk_t finish, 307 int num, ext2fs_block_bitmap map, blk_t *ret) 308{ 309 errcode_t retval; 310 blk64_t val; 311 retval = ext2fs_get_free_blocks2(fs, start, finish, num, map, &val); 312 if(!retval) 313 *ret = (blk_t) val; 314 return retval; 315} 316 317void ext2fs_set_alloc_block_callback(ext2_filsys fs, 318 errcode_t (*func)(ext2_filsys fs, 319 blk64_t goal, 320 blk64_t *ret), 321 errcode_t (**old)(ext2_filsys fs, 322 blk64_t goal, 323 blk64_t *ret)) 324{ 325 if (!fs || fs->magic != EXT2_ET_MAGIC_EXT2FS_FILSYS) 326 return; 327 328 if (old) 329 *old = fs->get_alloc_block; 330 331 fs->get_alloc_block = func; 332} 333