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 /* Make sure data stored in inode->i_block is neither fast symlink nor 357 * inline data. 358 */ 359 if (inode == NULL || ext2fs_is_fast_symlink(inode) || 360 inode->i_flags & EXT4_INLINE_DATA_FL) 361 goto no_blocks; 362 363 if (inode->i_flags & EXT4_EXTENTS_FL) { 364 err = ext2fs_extent_open2(fs, ino, inode, &handle); 365 if (err) 366 goto no_blocks; 367 err = ext2fs_extent_goto2(handle, 0, lblk); 368 if (err) 369 goto no_blocks; 370 err = ext2fs_extent_get(handle, EXT2_EXTENT_CURRENT, &extent); 371 if (err) 372 goto no_blocks; 373 ext2fs_extent_free(handle); 374 return extent.e_pblk + (lblk - extent.e_lblk); 375 } 376 377 /* block mapped file; see if block zero is mapped? */ 378 if (inode->i_block[0]) 379 return inode->i_block[0]; 380 381 no_blocks: 382 ext2fs_extent_free(handle); 383 log_flex = fs->super->s_log_groups_per_flex; 384 group = ext2fs_group_of_ino(fs, ino); 385 if (log_flex) 386 group = group & ~((1 << (log_flex)) - 1); 387 return ext2fs_group_first_block2(fs, group); 388 } 389 390 /* 391 * Starting at _goal_, scan around the filesystem to find a run of free blocks 392 * that's at least _len_ blocks long. Possible flags: 393 * - EXT2_NEWRANGE_EXACT_GOAL: The range of blocks must start at _goal_. 394 * - EXT2_NEWRANGE_MIN_LENGTH: do not return a allocation shorter than _len_. 395 * - EXT2_NEWRANGE_ZERO_BLOCKS: Zero blocks pblk to pblk+plen before returning. 396 * 397 * The starting block is returned in _pblk_ and the length is returned via 398 * _plen_. The blocks are not marked in the bitmap; the caller must mark 399 * however much of the returned run they actually use, hopefully via 400 * ext2fs_block_alloc_stats_range(). 401 * 402 * This function can return a range that is longer than what was requested. 403 */ 404 errcode_t ext2fs_new_range(ext2_filsys fs, int flags, blk64_t goal, 405 blk64_t len, ext2fs_block_bitmap map, blk64_t *pblk, 406 blk64_t *plen) 407 { 408 errcode_t retval; 409 blk64_t start, end, b; 410 int looped = 0; 411 blk64_t max_blocks = ext2fs_blocks_count(fs->super); 412 errcode_t (*nrf)(ext2_filsys fs, int flags, blk64_t goal, 413 blk64_t len, blk64_t *pblk, blk64_t *plen); 414 415 dbg_printf("%s: flags=0x%x goal=%llu len=%llu\n", __func__, flags, 416 goal, len); 417 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 418 if (len == 0 || (flags & ~EXT2_NEWRANGE_ALL_FLAGS)) 419 return EXT2_ET_INVALID_ARGUMENT; 420 421 if (!map && fs->new_range) { 422 /* 423 * In case there are clients out there whose new_range 424 * handlers call ext2fs_new_range with a NULL block map, 425 * temporarily swap out the function pointer so that we don't 426 * end up in an infinite loop. 427 */ 428 nrf = fs->new_range; 429 fs->new_range = NULL; 430 retval = nrf(fs, flags, goal, len, pblk, plen); 431 fs->new_range = nrf; 432 if (retval) 433 return retval; 434 start = *pblk; 435 end = *pblk + *plen; 436 goto allocated; 437 } 438 if (!map) 439 map = fs->block_map; 440 if (!map) 441 return EXT2_ET_NO_BLOCK_BITMAP; 442 if (!goal || goal >= ext2fs_blocks_count(fs->super)) 443 goal = fs->super->s_first_data_block; 444 445 start = goal; 446 while (!looped || start <= goal) { 447 retval = ext2fs_find_first_zero_block_bitmap2(map, start, 448 max_blocks - 1, 449 &start); 450 if (retval == ENOENT) { 451 /* 452 * If there are no free blocks beyond the starting 453 * point, try scanning the whole filesystem, unless the 454 * user told us only to allocate from _goal_, or if 455 * we're already scanning the whole filesystem. 456 */ 457 if (flags & EXT2_NEWRANGE_FIXED_GOAL || 458 start == fs->super->s_first_data_block) 459 goto fail; 460 start = fs->super->s_first_data_block; 461 continue; 462 } else if (retval) 463 goto errout; 464 465 if (flags & EXT2_NEWRANGE_FIXED_GOAL && start != goal) 466 goto fail; 467 468 b = min(start + len - 1, max_blocks - 1); 469 retval = ext2fs_find_first_set_block_bitmap2(map, start, b, 470 &end); 471 if (retval == ENOENT) 472 end = b + 1; 473 else if (retval) 474 goto errout; 475 476 if (!(flags & EXT2_NEWRANGE_MIN_LENGTH) || 477 (end - start) >= len) { 478 /* Success! */ 479 *pblk = start; 480 *plen = end - start; 481 dbg_printf("%s: new_range goal=%llu--%llu " 482 "blk=%llu--%llu %llu\n", 483 __func__, goal, goal + len - 1, 484 *pblk, *pblk + *plen - 1, *plen); 485 allocated: 486 for (b = start; b < end; 487 b += fs->super->s_blocks_per_group) 488 ext2fs_clear_block_uninit(fs, 489 ext2fs_group_of_blk2(fs, b)); 490 return 0; 491 } 492 493 if (flags & EXT2_NEWRANGE_FIXED_GOAL) 494 goto fail; 495 start = end; 496 if (start >= max_blocks) { 497 if (looped) 498 goto fail; 499 looped = 1; 500 start = fs->super->s_first_data_block; 501 } 502 } 503 504 fail: 505 retval = EXT2_ET_BLOCK_ALLOC_FAIL; 506 errout: 507 return retval; 508 } 509 510 void ext2fs_set_new_range_callback(ext2_filsys fs, 511 errcode_t (*func)(ext2_filsys fs, int flags, blk64_t goal, 512 blk64_t len, blk64_t *pblk, blk64_t *plen), 513 errcode_t (**old)(ext2_filsys fs, int flags, blk64_t goal, 514 blk64_t len, blk64_t *pblk, blk64_t *plen)) 515 { 516 if (!fs || fs->magic != EXT2_ET_MAGIC_EXT2FS_FILSYS) 517 return; 518 519 if (old) 520 *old = fs->new_range; 521 522 fs->new_range = func; 523 } 524 525 errcode_t ext2fs_alloc_range(ext2_filsys fs, int flags, blk64_t goal, 526 blk_t len, blk64_t *ret) 527 { 528 int newr_flags = EXT2_NEWRANGE_MIN_LENGTH; 529 errcode_t retval; 530 blk64_t plen; 531 532 EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS); 533 if (len == 0 || (flags & ~EXT2_ALLOCRANGE_ALL_FLAGS)) 534 return EXT2_ET_INVALID_ARGUMENT; 535 536 if (flags & EXT2_ALLOCRANGE_FIXED_GOAL) 537 newr_flags |= EXT2_NEWRANGE_FIXED_GOAL; 538 539 retval = ext2fs_new_range(fs, newr_flags, goal, len, NULL, ret, &plen); 540 if (retval) 541 return retval; 542 543 if (plen < len) 544 return EXT2_ET_BLOCK_ALLOC_FAIL; 545 546 if (flags & EXT2_ALLOCRANGE_ZERO_BLOCKS) { 547 retval = ext2fs_zero_blocks2(fs, *ret, len, NULL, NULL); 548 if (retval) 549 return retval; 550 } 551 552 ext2fs_block_alloc_stats_range(fs, *ret, len, +1); 553 return retval; 554 } 555
