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 #define min(a, b) ((a) < (b) ? (a) : (b)) 30 31 #undef DEBUG 32 33 #ifdef DEBUG 34 # define dbg_printf(f, a...) do {printf(f, ## a); fflush(stdout); } while (0) 35 #else 36 # define dbg_printf(f, a...) 37 #endif 38 39 /* 40 * Clear the uninit block bitmap flag if necessary 41 */ 42 void ext2fs_clear_block_uninit(ext2_filsys fs, dgrp_t group) 43 { 44 if (group >= fs->group_desc_count || 45 !ext2fs_has_group_desc_csum(fs) || 46 !(ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT))) 47 return; 48 49 /* uninit block bitmaps are now initialized in read_bitmaps() */ 50 51 ext2fs_bg_flags_clear(fs, group, EXT2_BG_BLOCK_UNINIT); 52 ext2fs_group_desc_csum_set(fs, group); 53 ext2fs_mark_super_dirty(fs); 54 ext2fs_mark_bb_dirty(fs); 55 } 56 57 /* 58 * Check for uninit inode bitmaps and deal with them appropriately 59 */ 60 static void check_inode_uninit(ext2_filsys fs, ext2fs_inode_bitmap map, 61 dgrp_t group) 62 { 63 ext2_ino_t i, ino; 64 65 if (group >= fs->group_desc_count || 66 !ext2fs_has_group_desc_csum(fs) || 67 !(ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT))) 68 return; 69 70 ino = (group * fs->super->s_inodes_per_group) + 1; 71 for (i=0; i < fs->super->s_inodes_per_group; i++, ino++) 72 ext2fs_fast_unmark_inode_bitmap2(map, ino); 73 74 ext2fs_bg_flags_clear(fs, group, EXT2_BG_INODE_UNINIT); 75 /* Mimics what the kernel does */ 76 ext2fs_bg_flags_clear(fs, group, EXT2_BG_BLOCK_UNINIT); 77 ext2fs_group_desc_csum_set(fs, group); 78 ext2fs_mark_ib_dirty(fs); 79 ext2fs_mark_super_dirty(fs); 80 } 81 82 /* 83 * Right now, just search forward from the parent directory's block 84 * group to find the next free inode. 85 * 86 * Should have a special policy for directories. 87 */ 88 errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir, 89 int mode EXT2FS_ATTR((unused)), 90 ext2fs_inode_bitmap map, ext2_ino_t *ret) 91 { 92 ext2_ino_t start_inode = 0; 93 ext2_ino_t i, ino_in_group, upto, first_zero; 94 errcode_t retval; 95 dgrp_t group; 96 97 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 98 99 if (!map) 100 map = fs->inode_map; 101 if (!map) 102 return EXT2_ET_NO_INODE_BITMAP; 103 104 if (dir > 0) { 105 group = (dir - 1) / EXT2_INODES_PER_GROUP(fs->super); 106 start_inode = (group * EXT2_INODES_PER_GROUP(fs->super)) + 1; 107 } 108 if (start_inode < EXT2_FIRST_INODE(fs->super)) 109 start_inode = EXT2_FIRST_INODE(fs->super); 110 if (start_inode > fs->super->s_inodes_count) 111 return EXT2_ET_INODE_ALLOC_FAIL; 112 i = start_inode; 113 do { 114 ino_in_group = (i - 1) % EXT2_INODES_PER_GROUP(fs->super); 115 group = (i - 1) / EXT2_INODES_PER_GROUP(fs->super); 116 117 check_inode_uninit(fs, map, group); 118 upto = i + (EXT2_INODES_PER_GROUP(fs->super) - ino_in_group); 119 if (i < start_inode && upto >= start_inode) 120 upto = start_inode - 1; 121 if (upto > fs->super->s_inodes_count) 122 upto = fs->super->s_inodes_count; 123 124 retval = ext2fs_find_first_zero_inode_bitmap2(map, i, upto, 125 &first_zero); 126 if (retval == 0) { 127 i = first_zero; 128 break; 129 } 130 if (retval != ENOENT) 131 return EXT2_ET_INODE_ALLOC_FAIL; 132 i = upto + 1; 133 if (i > fs->super->s_inodes_count) 134 i = EXT2_FIRST_INODE(fs->super); 135 } while (i != start_inode); 136 137 if (ext2fs_test_inode_bitmap2(map, i)) 138 return EXT2_ET_INODE_ALLOC_FAIL; 139 *ret = i; 140 return 0; 141 } 142 143 /* 144 * Stupid algorithm --- we now just search forward starting from the 145 * goal. Should put in a smarter one someday.... 146 */ 147 errcode_t ext2fs_new_block3(ext2_filsys fs, blk64_t goal, 148 ext2fs_block_bitmap map, blk64_t *ret, 149 struct blk_alloc_ctx *ctx) 150 { 151 errcode_t retval; 152 blk64_t b = 0; 153 errcode_t (*gab)(ext2_filsys fs, blk64_t goal, blk64_t *ret); 154 errcode_t (*gab2)(ext2_filsys, blk64_t, blk64_t *, 155 struct blk_alloc_ctx *); 156 157 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 158 159 if (!map) { 160 /* 161 * In case there are clients out there whose get_alloc_block 162 * handlers call ext2fs_new_block2 with a NULL block map, 163 * temporarily swap out the function pointer so that we don't 164 * end up in an infinite loop. 165 */ 166 if (fs->get_alloc_block2) { 167 gab2 = fs->get_alloc_block2; 168 fs->get_alloc_block2 = NULL; 169 retval = gab2(fs, goal, &b, ctx); 170 fs->get_alloc_block2 = gab2; 171 goto allocated; 172 } else if (fs->get_alloc_block) { 173 gab = fs->get_alloc_block; 174 fs->get_alloc_block = NULL; 175 retval = gab(fs, goal, &b); 176 fs->get_alloc_block = gab; 177 goto allocated; 178 } 179 } 180 if (!map) 181 map = fs->block_map; 182 if (!map) 183 return EXT2_ET_NO_BLOCK_BITMAP; 184 if (!goal || (goal >= ext2fs_blocks_count(fs->super))) 185 goal = fs->super->s_first_data_block; 186 goal &= ~EXT2FS_CLUSTER_MASK(fs); 187 188 retval = ext2fs_find_first_zero_block_bitmap2(map, 189 goal, ext2fs_blocks_count(fs->super) - 1, &b); 190 if ((retval == ENOENT) && (goal != fs->super->s_first_data_block)) 191 retval = ext2fs_find_first_zero_block_bitmap2(map, 192 fs->super->s_first_data_block, goal - 1, &b); 193 allocated: 194 if (retval == ENOENT) 195 return EXT2_ET_BLOCK_ALLOC_FAIL; 196 if (retval) 197 return retval; 198 199 ext2fs_clear_block_uninit(fs, ext2fs_group_of_blk2(fs, b)); 200 *ret = b; 201 return 0; 202 } 203 204 errcode_t ext2fs_new_block2(ext2_filsys fs, blk64_t goal, 205 ext2fs_block_bitmap map, blk64_t *ret) 206 { 207 return ext2fs_new_block3(fs, goal, map, ret, NULL); 208 } 209 210 errcode_t ext2fs_new_block(ext2_filsys fs, blk_t goal, 211 ext2fs_block_bitmap map, blk_t *ret) 212 { 213 errcode_t retval; 214 blk64_t val; 215 retval = ext2fs_new_block2(fs, goal, map, &val); 216 if (!retval) 217 *ret = (blk_t) val; 218 return retval; 219 } 220 221 /* 222 * This function zeros out the allocated block, and updates all of the 223 * appropriate filesystem records. 224 */ 225 errcode_t ext2fs_alloc_block3(ext2_filsys fs, blk64_t goal, char *block_buf, 226 blk64_t *ret, struct blk_alloc_ctx *ctx) 227 { 228 errcode_t retval; 229 blk64_t block; 230 231 if (fs->get_alloc_block2) { 232 retval = (fs->get_alloc_block2)(fs, goal, &block, ctx); 233 if (retval) 234 goto fail; 235 } else if (fs->get_alloc_block) { 236 retval = (fs->get_alloc_block)(fs, goal, &block); 237 if (retval) 238 goto fail; 239 } else { 240 if (!fs->block_map) { 241 retval = ext2fs_read_block_bitmap(fs); 242 if (retval) 243 goto fail; 244 } 245 246 retval = ext2fs_new_block3(fs, goal, 0, &block, ctx); 247 if (retval) 248 goto fail; 249 } 250 251 if (block_buf) { 252 memset(block_buf, 0, fs->blocksize); 253 retval = io_channel_write_blk64(fs->io, block, 1, block_buf); 254 } else 255 retval = ext2fs_zero_blocks2(fs, block, 1, NULL, NULL); 256 if (retval) 257 goto fail; 258 259 ext2fs_block_alloc_stats2(fs, block, +1); 260 *ret = block; 261 262 fail: 263 return retval; 264 } 265 266 errcode_t ext2fs_alloc_block2(ext2_filsys fs, blk64_t goal, 267 char *block_buf, blk64_t *ret) 268 { 269 return ext2fs_alloc_block3(fs, goal, block_buf, ret, NULL); 270 } 271 272 errcode_t ext2fs_alloc_block(ext2_filsys fs, blk_t goal, 273 char *block_buf, blk_t *ret) 274 { 275 errcode_t retval; 276 blk64_t ret64, goal64 = goal; 277 retval = ext2fs_alloc_block3(fs, goal64, block_buf, &ret64, NULL); 278 if (!retval) 279 *ret = (blk_t)ret64; 280 return retval; 281 } 282 283 errcode_t ext2fs_get_free_blocks2(ext2_filsys fs, blk64_t start, blk64_t finish, 284 int num, ext2fs_block_bitmap map, blk64_t *ret) 285 { 286 blk64_t b = start; 287 int c_ratio; 288 289 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 290 291 if (!map) 292 map = fs->block_map; 293 if (!map) 294 return EXT2_ET_NO_BLOCK_BITMAP; 295 if (!b) 296 b = fs->super->s_first_data_block; 297 if (!finish) 298 finish = start; 299 if (!num) 300 num = 1; 301 c_ratio = 1 << ext2fs_get_bitmap_granularity(map); 302 b &= ~(c_ratio - 1); 303 finish &= ~(c_ratio -1); 304 do { 305 if (b + num - 1 >= ext2fs_blocks_count(fs->super)) { 306 if (finish > start) 307 return EXT2_ET_BLOCK_ALLOC_FAIL; 308 b = fs->super->s_first_data_block; 309 } 310 if (ext2fs_fast_test_block_bitmap_range2(map, b, num)) { 311 *ret = b; 312 return 0; 313 } 314 b += c_ratio; 315 } while (b != finish); 316 return EXT2_ET_BLOCK_ALLOC_FAIL; 317 } 318 319 errcode_t ext2fs_get_free_blocks(ext2_filsys fs, blk_t start, blk_t finish, 320 int num, ext2fs_block_bitmap map, blk_t *ret) 321 { 322 errcode_t retval; 323 blk64_t val; 324 retval = ext2fs_get_free_blocks2(fs, start, finish, num, map, &val); 325 if(!retval) 326 *ret = (blk_t) val; 327 return retval; 328 } 329 330 void ext2fs_set_alloc_block_callback(ext2_filsys fs, 331 errcode_t (*func)(ext2_filsys fs, 332 blk64_t goal, 333 blk64_t *ret), 334 errcode_t (**old)(ext2_filsys fs, 335 blk64_t goal, 336 blk64_t *ret)) 337 { 338 if (!fs || fs->magic != EXT2_ET_MAGIC_EXT2FS_FILSYS) 339 return; 340 341 if (old) 342 *old = fs->get_alloc_block; 343 344 fs->get_alloc_block = func; 345 } 346 347 blk64_t ext2fs_find_inode_goal(ext2_filsys fs, ext2_ino_t ino, 348 struct ext2_inode *inode, blk64_t lblk) 349 { 350 dgrp_t group; 351 __u8 log_flex; 352 struct ext2fs_extent extent; 353 ext2_extent_handle_t handle = NULL; 354 errcode_t err; 355 356 if (inode == NULL || ext2fs_inode_data_blocks2(fs, inode) == 0) 357 goto no_blocks; 358 359 if (inode->i_flags & EXT4_INLINE_DATA_FL) 360 goto no_blocks; 361 362 if (inode->i_flags & EXT4_EXTENTS_FL) { 363 err = ext2fs_extent_open2(fs, ino, inode, &handle); 364 if (err) 365 goto no_blocks; 366 err = ext2fs_extent_goto2(handle, 0, lblk); 367 if (err) 368 goto no_blocks; 369 err = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 370 if (err) 371 goto no_blocks; 372 ext2fs_extent_free(handle); 373 return extent.e_pblk + (lblk - extent.e_lblk); 374 } 375 376 /* block mapped file; see if block zero is mapped? */ 377 if (inode->i_block[0]) 378 return inode->i_block[0]; 379 380 no_blocks: 381 ext2fs_extent_free(handle); 382 log_flex = fs->super->s_log_groups_per_flex; 383 group = ext2fs_group_of_ino(fs, ino); 384 if (log_flex) 385 group = group & ~((1 << (log_flex)) - 1); 386 return ext2fs_group_first_block2(fs, group); 387 } 388 389 /* 390 * Starting at _goal_, scan around the filesystem to find a run of free blocks 391 * that's at least _len_ blocks long. Possible flags: 392 * - EXT2_NEWRANGE_EXACT_GOAL: The range of blocks must start at _goal_. 393 * - EXT2_NEWRANGE_MIN_LENGTH: do not return a allocation shorter than _len_. 394 * - EXT2_NEWRANGE_ZERO_BLOCKS: Zero blocks pblk to pblk+plen before returning. 395 * 396 * The starting block is returned in _pblk_ and the length is returned via 397 * _plen_. The blocks are not marked in the bitmap; the caller must mark 398 * however much of the returned run they actually use, hopefully via 399 * ext2fs_block_alloc_stats_range(). 400 * 401 * This function can return a range that is longer than what was requested. 402 */ 403 errcode_t ext2fs_new_range(ext2_filsys fs, int flags, blk64_t goal, 404 blk64_t len, ext2fs_block_bitmap map, blk64_t *pblk, 405 blk64_t *plen) 406 { 407 errcode_t retval; 408 blk64_t start, end, b; 409 int looped = 0; 410 blk64_t max_blocks = ext2fs_blocks_count(fs->super); 411 errcode_t (*nrf)(ext2_filsys fs, int flags, blk64_t goal, 412 blk64_t len, blk64_t *pblk, blk64_t *plen); 413 414 dbg_printf("%s: flags=0x%x goal=%llu len=%llu\n", __func__, flags, 415 goal, len); 416 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 417 if (len == 0 || (flags & ~EXT2_NEWRANGE_ALL_FLAGS)) 418 return EXT2_ET_INVALID_ARGUMENT; 419 420 if (!map && fs->new_range) { 421 /* 422 * In case there are clients out there whose new_range 423 * handlers call ext2fs_new_range with a NULL block map, 424 * temporarily swap out the function pointer so that we don't 425 * end up in an infinite loop. 426 */ 427 nrf = fs->new_range; 428 fs->new_range = NULL; 429 retval = nrf(fs, flags, goal, len, pblk, plen); 430 fs->new_range = nrf; 431 if (retval) 432 return retval; 433 start = *pblk; 434 end = *pblk + *plen; 435 goto allocated; 436 } 437 if (!map) 438 map = fs->block_map; 439 if (!map) 440 return EXT2_ET_NO_BLOCK_BITMAP; 441 if (!goal || goal >= ext2fs_blocks_count(fs->super)) 442 goal = fs->super->s_first_data_block; 443 444 start = goal; 445 while (!looped || start <= goal) { 446 retval = ext2fs_find_first_zero_block_bitmap2(map, start, 447 max_blocks - 1, 448 &start); 449 if (retval == ENOENT) { 450 /* 451 * If there are no free blocks beyond the starting 452 * point, try scanning the whole filesystem, unless the 453 * user told us only to allocate from _goal_, or if 454 * we're already scanning the whole filesystem. 455 */ 456 if (flags & EXT2_NEWRANGE_FIXED_GOAL || 457 start == fs->super->s_first_data_block) 458 goto fail; 459 start = fs->super->s_first_data_block; 460 continue; 461 } else if (retval) 462 goto errout; 463 464 if (flags & EXT2_NEWRANGE_FIXED_GOAL && start != goal) 465 goto fail; 466 467 b = min(start + len - 1, max_blocks - 1); 468 retval = ext2fs_find_first_set_block_bitmap2(map, start, b, 469 &end); 470 if (retval == ENOENT) 471 end = b + 1; 472 else if (retval) 473 goto errout; 474 475 if (!(flags & EXT2_NEWRANGE_MIN_LENGTH) || 476 (end - start) >= len) { 477 /* Success! */ 478 *pblk = start; 479 *plen = end - start; 480 dbg_printf("%s: new_range goal=%llu--%llu " 481 "blk=%llu--%llu %llu\n", 482 __func__, goal, goal + len - 1, 483 *pblk, *pblk + *plen - 1, *plen); 484 allocated: 485 for (b = start; b < end; 486 b += fs->super->s_blocks_per_group) 487 ext2fs_clear_block_uninit(fs, 488 ext2fs_group_of_blk2(fs, b)); 489 return 0; 490 } 491 492 if (flags & EXT2_NEWRANGE_FIXED_GOAL) 493 goto fail; 494 start = end; 495 if (start >= max_blocks) { 496 if (looped) 497 goto fail; 498 looped = 1; 499 start = fs->super->s_first_data_block; 500 } 501 } 502 503 fail: 504 retval = EXT2_ET_BLOCK_ALLOC_FAIL; 505 errout: 506 return retval; 507 } 508 509 void ext2fs_set_new_range_callback(ext2_filsys fs, 510 errcode_t (*func)(ext2_filsys fs, int flags, blk64_t goal, 511 blk64_t len, blk64_t *pblk, blk64_t *plen), 512 errcode_t (**old)(ext2_filsys fs, int flags, blk64_t goal, 513 blk64_t len, blk64_t *pblk, blk64_t *plen)) 514 { 515 if (!fs || fs->magic != EXT2_ET_MAGIC_EXT2FS_FILSYS) 516 return; 517 518 if (old) 519 *old = fs->new_range; 520 521 fs->new_range = func; 522 } 523 524 errcode_t ext2fs_alloc_range(ext2_filsys fs, int flags, blk64_t goal, 525 blk_t len, blk64_t *ret) 526 { 527 int newr_flags = EXT2_NEWRANGE_MIN_LENGTH; 528 errcode_t retval; 529 blk64_t plen; 530 531 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 532 if (len == 0 || (flags & ~EXT2_ALLOCRANGE_ALL_FLAGS)) 533 return EXT2_ET_INVALID_ARGUMENT; 534 535 if (flags & EXT2_ALLOCRANGE_FIXED_GOAL) 536 newr_flags |= EXT2_NEWRANGE_FIXED_GOAL; 537 538 retval = ext2fs_new_range(fs, newr_flags, goal, len, NULL, ret, &plen); 539 if (retval) 540 return retval; 541 542 if (plen < len) 543 return EXT2_ET_BLOCK_ALLOC_FAIL; 544 545 if (flags & EXT2_ALLOCRANGE_ZERO_BLOCKS) { 546 retval = ext2fs_zero_blocks2(fs, *ret, len, NULL, NULL); 547 if (retval) 548 return retval; 549 } 550 551 ext2fs_block_alloc_stats_range(fs, *ret, len, +1); 552 return retval; 553 } 554
