ext2_block_relocator.c revision 9663:ace9a2ac3683
1/* 2 ext2_block_relocator.c -- ext2 block relocator 3 Copyright (C) 1998-2000, 2007 Free Software Foundation, Inc. 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 3 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, 11 but WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 GNU General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program. If not, see <http://www.gnu.org/licenses/>. 17*/ 18 19#include <config.h> 20 21#ifndef DISCOVER_ONLY 22 23#include <stdio.h> 24#include <stdlib.h> 25#include "ext2.h" 26 27 28/* This struct describes a single block that will be relocated. The 29 * block's original location is "num", and its new location is "dest". 30 * The block is presumebly referred to by some other block in the file 31 * system, which is recorded as "refblock". (Only one reference to 32 * the block is allowed by the block relocator.) "refoffset" describes 33 * the location within the refblock in which the block is referenced. 34 * "isindirect" is 0 for direct, 1 for single-indirect, 2 for 35 * double-indirect, etc. 36 * 37 * The algorithms in the file fill the entries of this struct in this order: 38 * num, refblock/refoffset/isindirectblock, dest. 39 */ 40struct ext2_block_entry 41{ 42 blk_t num; 43 blk_t dest; 44 blk_t refblock; 45 unsigned refoffset:16; 46 unsigned isindirectblock:16; 47}; 48 49/* This struct contains all data structures relevant to the block relocator. 50 * - newallocoffset is the distance between the start of a block group, 51 * and the first data block in the group. This can change when a 52 * filesystem is resized, because the size of the group descriptors is 53 * proportional to the size of the filesystem. 54 * 55 * - allocentries is the size of the "block" array. It is a tuneable 56 * parameter that determines how many blocks can be moved in each 57 * pass. 58 * 59 * - usedentries says how many entries of the "block" array have been 60 * used. That is, how many blocks have been scheduled so far to 61 * be moved. 62 * 63 * - resolvedentries is the number of blocks whose referencing block 64 * has been found and recorded in block[.]->refblock, etc. 65 * 66 * - block is an array that records which blocks need to be moved, and 67 * where they will be moved to, etc. At some point in the algorithm, this 68 * array gets sorted (grep for qsort!) by indirectness. 69 * 70 * - start: each entry in this array corresponds to a level of 71 * indirectness (0-3). Each level has two items: dst and num. "num" 72 * is the number of blocks inside "block" of that level of indirectness. 73 * After doscan() is finished, and the level of indirectness of each 74 * block is known, "block" is sorted (see above). The "dst" pointer 75 * is a pointer inside "block" that indicates the start of the portion 76 * of the array containg blocks of that level of indirectness. 77 */ 78struct ext2_block_relocator_state 79{ 80 blk_t newallocoffset; 81 blk_t allocentries; 82 blk_t usedentries; 83 blk_t resolvedentries; 84 struct ext2_block_entry *block; 85 86 struct { 87 struct ext2_block_entry *dst; 88 int num; 89 } start[4]; 90}; 91 92 93 94static int compare_block_entries(const void *x0, const void *x1) 95{ 96 const struct ext2_block_entry *b0; 97 const struct ext2_block_entry *b1; 98 99 b0 = (const struct ext2_block_entry *)x0; 100 b1 = (const struct ext2_block_entry *)x1; 101 102 if (b0->num < b1->num) 103 return -1; 104 105 if (b0->num > b1->num) 106 return 1; 107 108 return 0; 109} 110 111static int compare_block_entries_ind(const void *x0, const void *x1) 112{ 113 const struct ext2_block_entry *b0; 114 const struct ext2_block_entry *b1; 115 116 b0 = (const struct ext2_block_entry *)x0; 117 b1 = (const struct ext2_block_entry *)x1; 118 119 if (b0->isindirectblock > b1->isindirectblock) 120 return -1; 121 122 if (b0->isindirectblock < b1->isindirectblock) 123 return 1; 124 125 return 0; 126} 127 128static int compare_block_entries_ref(const void *x0, const void *x1) 129{ 130 const struct ext2_block_entry *b0; 131 const struct ext2_block_entry *b1; 132 133 b0 = (const struct ext2_block_entry *)x0; 134 b1 = (const struct ext2_block_entry *)x1; 135 136 if (b0->refblock < b1->refblock) 137 return -1; 138 139 if (b0->refblock > b1->refblock) 140 return 1; 141 142 return 0; 143} 144 145struct ext2_block_entry *findit(struct ext2_block_relocator_state *state, blk_t block) 146{ 147 int min; 148 int max; 149 struct ext2_block_entry *retv; 150 int t; 151 blk_t tval; 152 153 max = state->usedentries - 1; 154 min = 0; 155 retv = NULL; 156 157 repeat: 158 if (min > max) 159 goto out; 160 161 t = (min + max) >> 1; 162 tval = state->block[t].num; 163 164 if (tval > block) 165 max = t - 1; 166 167 if (tval < block) 168 min = t + 1; 169 170 if (tval != block) 171 goto repeat; 172 173 retv = &state->block[t]; 174 175 out: 176 return retv; 177} 178 179/* This function adds records a reference to a block ("blk"), if that 180 * block is scheduled to be moved. 181 */ 182static int doblock(struct ext2_fs *fs, 183 struct ext2_block_relocator_state *state, 184 blk_t blk, 185 blk_t refblock, 186 off_t refoffset, 187 int indirect) 188{ 189 struct ext2_block_entry *ent; 190 191 if ((ent = findit(state, blk)) == NULL) 192 return 1; 193 194 if (ent->refblock) 195 { 196 ped_exception_throw (PED_EXCEPTION_ERROR, PED_EXCEPTION_CANCEL, 197 _("Cross-linked blocks found! Better go run e2fsck " 198 "first!")); 199 return 0; 200 } 201 202 ent->refblock = refblock; 203 ent->refoffset = refoffset; 204 ent->isindirectblock = indirect; 205 206 state->resolvedentries++; 207 state->start[indirect].num++; 208 209 return 1; 210} 211 212static int doindblock(struct ext2_fs *fs, 213 struct ext2_block_relocator_state *state, 214 blk_t blk, 215 blk_t refblock, 216 off_t refoffset) 217{ 218 struct ext2_buffer_head *bh; 219 int i; 220 uint32_t *uptr; 221 222 if (!doblock(fs, state, blk, refblock, refoffset, 1)) 223 return 0; 224 225 bh = ext2_bread(fs, blk); 226 if (!bh) 227 return 0; 228 uptr = (uint32_t *)bh->data; 229 230 for (i=0;i<(fs->blocksize >> 2);i++) 231 if (uptr[i]) 232 if (!doblock(fs, state, PED_LE32_TO_CPU(uptr[i]), blk, 233 i<<2, 0)) 234 return 0; 235 236 if (!ext2_brelse(bh, 0)) 237 return 0; 238 239 return 1; 240} 241 242static int dodindblock(struct ext2_fs *fs, 243 struct ext2_block_relocator_state *state, 244 blk_t blk, 245 blk_t refblock, 246 off_t refoffset) 247{ 248 struct ext2_buffer_head *bh; 249 int i; 250 uint32_t *uptr; 251 252 if (!doblock(fs, state, blk, refblock, refoffset, 2)) 253 return 0; 254 255 bh = ext2_bread(fs, blk); 256 if (!bh) 257 return 0; 258 uptr = (uint32_t *)bh->data; 259 260 for (i=0;i<(fs->blocksize >> 2);i++) 261 if (uptr[i]) 262 if (!doindblock(fs, state, PED_LE32_TO_CPU(uptr[i]), 263 blk, i<<2)) 264 return 0; 265 266 if (!ext2_brelse(bh, 0)) 267 return 0; 268 269 return 1; 270} 271 272static int dotindblock(struct ext2_fs *fs, 273 struct ext2_block_relocator_state *state, 274 blk_t blk, 275 blk_t refblock, 276 off_t refoffset) 277{ 278 struct ext2_buffer_head *bh; 279 int i; 280 uint32_t *uptr; 281 282 if (!doblock(fs, state, blk, refblock, refoffset, 3)) 283 return 0; 284 285 bh = ext2_bread(fs, blk); 286 if (!bh) 287 return 0; 288 uptr = (uint32_t *)bh->data; 289 290 for (i=0;i<(fs->blocksize >> 2);i++) 291 if (uptr[i]) 292 if (!dodindblock(fs, state, PED_LE32_TO_CPU(uptr[i]), 293 blk, i<<2)) 294 return 0; 295 296 if (!ext2_brelse(bh, 0)) 297 return 0; 298 299 return 1; 300} 301 302 303/* This function records any block references from an inode to blocks that are 304 * scheduled to be moved. 305 */ 306static int doinode(struct ext2_fs *fs, struct ext2_block_relocator_state *state, int inode) 307{ 308 struct ext2_inode buf; 309 310 if (!ext2_read_inode(fs, inode, &buf)) 311 return 0; 312 313 if (EXT2_INODE_BLOCKS(buf)) 314 { 315 blk_t blk; 316 int i; 317 off_t inodeoffset; 318 blk_t inodeblock; 319 320 inodeoffset = ext2_get_inode_offset(fs, inode, &inodeblock); 321 322 /* do Hurd block, if there is one... */ 323 if (EXT2_SUPER_CREATOR_OS(fs->sb) == EXT2_OS_HURD 324 && EXT2_INODE_TRANSLATOR(buf)) { 325 if (!doblock(fs, 326 state, 327 EXT2_INODE_TRANSLATOR(buf), 328 inodeblock, 329 inodeoffset + offsetof(struct ext2_inode, 330 osd1.hurd1.h_i_translator), 331 0)) 332 return 0; 333 } 334 335 for (i=0;i<EXT2_NDIR_BLOCKS;i++) 336 if ((blk = EXT2_INODE_BLOCK(buf, i)) != 0) 337 if (!doblock(fs, 338 state, 339 blk, 340 inodeblock, 341 inodeoffset + offsetof(struct ext2_inode, i_block[i]), 342 0)) 343 return 0; 344 345 if ((blk = EXT2_INODE_BLOCK(buf, EXT2_IND_BLOCK)) != 0) 346 if (!doindblock(fs, 347 state, 348 blk, 349 inodeblock, 350 inodeoffset + offsetof(struct ext2_inode, i_block[EXT2_IND_BLOCK]))) 351 return 0; 352 353 if ((blk = EXT2_INODE_BLOCK(buf, EXT2_DIND_BLOCK)) != 0) 354 if (!dodindblock(fs, 355 state, 356 blk, 357 inodeblock, 358 inodeoffset + offsetof(struct ext2_inode, i_block[EXT2_DIND_BLOCK]))) 359 return 0; 360 361 if ((blk = EXT2_INODE_BLOCK(buf, EXT2_TIND_BLOCK)) != 0) 362 if (!dotindblock(fs, 363 state, 364 blk, 365 inodeblock, 366 inodeoffset + offsetof(struct ext2_inode, i_block[EXT2_TIND_BLOCK]))) 367 return 0; 368 369 } 370 371 return 1; 372} 373 374/* This function scans the entire filesystem, to find all references to blocks 375 * that are scheduled to be moved. 376 */ 377static int doscan(struct ext2_fs *fs, struct ext2_block_relocator_state *state) 378{ 379 int i; 380 381 state->start[0].num = 0; 382 state->start[1].num = 0; 383 state->start[2].num = 0; 384 state->start[3].num = 0; 385 386 for (i=0;i<fs->numgroups;i++) 387 { 388 struct ext2_buffer_head *bh; 389 unsigned int j; 390 int offset; 391 392 if (fs->opt_verbose) 393 { 394 fprintf(stderr, " scanning group %i.... ", i); 395 fflush(stderr); 396 } 397 398 bh = ext2_bread(fs, EXT2_GROUP_INODE_BITMAP(fs->gd[i])); 399 if (!bh) 400 return 0; 401 offset = i * EXT2_SUPER_INODES_PER_GROUP(fs->sb) + 1; 402 403 for (j=0;j<EXT2_SUPER_INODES_PER_GROUP(fs->sb);j++) 404 if (bh->data[j>>3] & _bitmap[j&7]) 405 { 406 if (!doinode(fs, state, offset + j)) 407 { 408 ext2_brelse(bh, 0); 409 return 0; 410 } 411 412 if (state->resolvedentries == state->usedentries) 413 break; 414 } 415 416 ext2_brelse(bh, 0); 417 418 if (fs->opt_verbose) 419 { 420 fprintf(stderr, "%i/%i blocks resolved\r", 421 state->resolvedentries, 422 state->usedentries); 423 fflush(stderr); 424 } 425 426 if (state->resolvedentries == state->usedentries) 427 break; 428 } 429 430 if (fs->opt_verbose) 431 fputc('\n', stderr); 432 433 state->start[3].dst = state->block; 434 state->start[2].dst = state->start[3].dst + state->start[3].num; 435 state->start[1].dst = state->start[2].dst + state->start[2].num; 436 state->start[0].dst = state->start[1].dst + state->start[1].num; 437 438 return 1; 439} 440 441 442 443 444 445static int ext2_block_relocator_copy(struct ext2_fs *fs, struct ext2_block_relocator_state *state) 446{ 447 unsigned char *buf; 448 449 ped_exception_fetch_all(); 450 buf = (unsigned char *) ped_malloc(MAXCONT << fs->logsize); 451 if (buf) 452 { 453 int num; 454 int numleft; 455 struct ext2_block_entry *ptr; 456 457 ped_exception_leave_all(); 458 459 numleft = state->usedentries; 460 ptr = state->block; 461 while (numleft) 462 { 463 num = PED_MIN(numleft, MAXCONT); 464 while (num != 1) 465 { 466 if (ptr[0].num + num-1 == ptr[num-1].num && 467 ptr[0].dest + num-1 == ptr[num-1].dest) 468 break; 469 470 num >>= 1; 471 } 472 473 if (!ext2_bcache_flush_range(fs, ptr[0].num, num)) 474 goto error_free_buf; 475 if (!ext2_bcache_flush_range(fs, ptr[0].dest, num)) 476 goto error_free_buf; 477 478 if (!ext2_read_blocks(fs, buf, ptr[0].num, num)) 479 goto error_free_buf; 480 if (!ext2_write_blocks(fs, buf, ptr[0].dest, num)) 481 goto error_free_buf; 482 483 ptr += num; 484 numleft -= num; 485 486 if (fs->opt_verbose) 487 { 488 fprintf(stderr, "copied %i/%i blocks\r", 489 state->usedentries - numleft, 490 state->usedentries); 491 fflush(stderr); 492 } 493 } 494 495 ped_free(buf); 496 497 if (fs->opt_safe) 498 ext2_sync(fs); 499 500 if (fs->opt_verbose) 501 fputc('\n', stderr); 502 } 503 else 504 { 505 blk_t i; 506 507 ped_exception_catch(); 508 ped_exception_leave_all(); 509 510 for (i=0;i<state->usedentries;i++) 511 { 512 struct ext2_block_entry *block; 513 514 block = &state->block[i]; 515 if (!ext2_copy_block(fs, block->num, block->dest)) 516 goto error; 517 } 518 } 519 520 return 1; 521 522error_free_buf: 523 ped_free(buf); 524error: 525 return 0; 526} 527 528static int ext2_block_relocator_ref(struct ext2_fs *fs, struct ext2_block_relocator_state *state, struct ext2_block_entry *block) 529{ 530 struct ext2_buffer_head *bh; 531 static int numerrors = 0; 532 533 if (!(block->refblock || block->refoffset)) 534 { 535 ped_exception_throw (PED_EXCEPTION_BUG, PED_EXCEPTION_CANCEL, 536 _("Block %i has no reference? Weird."), 537 block->num); 538 return 0; 539 } 540 541 bh = ext2_bread(fs, block->refblock); 542 if (!bh) 543 return 0; 544 545 if (fs->opt_debug) 546 { 547 if (PED_LE32_TO_CPU(*((uint32_t *)(bh->data + block->refoffset))) 548 != block->num) { 549 fprintf(stderr, 550 "block %i ref error! (->%i {%i, %i})\n", 551 block->num, 552 block->dest, 553 block->refblock, 554 block->refoffset); 555 ext2_brelse(bh, 0); 556 557 if (numerrors++ < 4) 558 return 1; 559 560 fputs("all is not well!\n", stderr); 561 return 0; 562 } 563 } 564 565 *((uint32_t *)(bh->data + block->refoffset)) 566 = PED_LE32_TO_CPU(block->dest); 567 bh->dirty = 1; 568 ext2_brelse(bh, 0); 569 570 ext2_set_block_state(fs, block->dest, 1, 1); 571 ext2_set_block_state(fs, block->num, 0, 1); 572 573 if (block->isindirectblock) 574 { 575 struct ext2_block_entry *dst; 576 int i; 577 int num; 578 579 dst = state->start[block->isindirectblock-1].dst; 580 num = state->start[block->isindirectblock-1].num; 581 582 for (i=0;i<num;i++) 583 if (dst[i].refblock == block->num) 584 dst[i].refblock = block->dest; 585 } 586 587 return 1; 588} 589 590/* This function allocates new locations for blocks that are scheduled to move 591 * (inside state->blocks). 592 * 593 * FIXME: doesn't seem to handle sparse block groups. That is, there might be 594 * some free space that could be exploited in resizing that currently isn't... 595 * 596 * FIXME: should throw an exception if it fails to allocate blocks. 597 */ 598static int ext2_block_relocator_grab_blocks(struct ext2_fs *fs, struct ext2_block_relocator_state *state) 599{ 600 int i; 601 blk_t ptr; 602 603 ptr = 0; 604 605 for (i=0;i<fs->numgroups;i++) 606 if (EXT2_GROUP_FREE_BLOCKS_COUNT(fs->gd[i])) 607 { 608 struct ext2_buffer_head *bh; 609 unsigned int j; 610 int offset; 611 612 bh = ext2_bread(fs, EXT2_GROUP_BLOCK_BITMAP(fs->gd[i])); 613 offset = i * EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb) 614 + EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb); 615 616 for (j=state->newallocoffset; 617 j<EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb); 618 j++) 619 if (!(bh->data[j>>3] & _bitmap[j&7])) 620 { 621 state->block[ptr++].dest = offset + j; 622 623 if (ptr == state->usedentries) 624 { 625 ext2_brelse(bh, 0); 626 return 1; 627 } 628 } 629 630 ext2_brelse(bh, 0); 631 } 632 633 return 0; 634} 635 636static int ext2_block_relocator_flush(struct ext2_fs *fs, struct ext2_block_relocator_state *state) 637{ 638 int i; 639 640 if (!state->usedentries) 641 return 1; 642 643 if (fs->opt_verbose) 644 fputs("ext2_block_relocator_flush\n", stderr); 645 646 if (fs->opt_debug) 647 { 648 again: 649 650 for (i=0; (unsigned int) i < state->usedentries-1; i++) 651 if (state->block[i].num >= state->block[i+1].num) 652 { 653 fputs("ext2_block_relocator_flush: " 654 "blocks not in order!\n", stderr); 655 656 qsort(state->block, 657 state->usedentries, 658 sizeof(struct ext2_block_entry), 659 compare_block_entries); 660 goto again; 661 } 662 } 663 664 if (!doscan(fs, state)) 665 return 0; 666 667 if (!ext2_block_relocator_grab_blocks(fs, state)) 668 return 0; 669 670 if (!ext2_block_relocator_copy(fs, state)) 671 return 0; 672 673 qsort(state->block, 674 state->usedentries, 675 sizeof(struct ext2_block_entry), 676 compare_block_entries_ind); 677 678 for (i=3;i>=0;i--) 679 { 680 struct ext2_block_entry *dst; 681 int j; 682 int num; 683 684 dst = state->start[i].dst; 685 num = state->start[i].num; 686 687 if (!num) 688 continue; 689 690 if (fs->opt_verbose) 691 { 692 /* FIXXXME gross hack */ 693 fprintf(stderr, "relocating %s blocks", 694 ((char *[4]){"direct", 695 "singly indirect", 696 "doubly indirect", 697 "triply indirect"})[i]); 698 fflush(stderr); 699 } 700 701 qsort(dst, 702 num, 703 sizeof(struct ext2_block_entry), 704 compare_block_entries_ref); 705 706 for (j=0;j<num;j++) 707 if (!ext2_block_relocator_ref(fs, state, &dst[j])) 708 return 0; 709 710 if (fs->opt_safe) { 711 if (!ext2_sync(fs)) 712 return 0; 713 } 714 715 if (fs->opt_verbose) 716 fputc('\n', stderr); 717 } 718 719 state->usedentries = 0; 720 state->resolvedentries = 0; 721 722 return 1; 723} 724 725static int ext2_block_relocator_mark(struct ext2_fs *fs, struct ext2_block_relocator_state *state, blk_t block) 726{ 727 int i; 728 729 if (fs->opt_debug) 730 { 731 if (!ext2_get_block_state(fs, block) || 732 !ext2_is_data_block(fs, block)) 733 { 734 ped_exception_throw (PED_EXCEPTION_WARNING, 735 PED_EXCEPTION_IGNORE, 736 _("Block %i shouldn't have been marked " 737 "(%d, %d)!"), block, 738 ext2_get_block_state(fs, block), 739 ext2_is_data_block(fs, block)); 740 } 741 } 742 743 if (state->usedentries == state->allocentries - 1) 744 if (!ext2_block_relocator_flush(fs, state)) 745 return 0; 746 747 i = state->usedentries; 748 state->block[i].num = block; 749 state->block[i].dest = 0; 750 state->block[i].refblock = 0; 751 state->block[i].refoffset = 0; 752 753 state->usedentries++; 754 return 1; 755} 756 757static int ext2_block_relocate_grow(struct ext2_fs *fs, struct ext2_block_relocator_state *state, blk_t newsize) 758{ 759 blk_t newgdblocks; 760 blk_t newitoffset; 761 int i; 762 763 newgdblocks = ped_div_round_up (newsize 764 - EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb), 765 EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb)); 766 newgdblocks = ped_div_round_up (newgdblocks 767 * sizeof(struct ext2_group_desc), 768 fs->blocksize); 769 if (newgdblocks == fs->gdblocks) 770 return 1; 771 772 newitoffset = newgdblocks + 3; 773 state->newallocoffset = newitoffset + fs->inodeblocks; 774 775 for (i=0;i<fs->numgroups;i++) 776 { 777 struct ext2_buffer_head *bh; 778 blk_t diff; 779 blk_t j; 780 blk_t start; 781 int sparse; 782 783 bh = ext2_bread(fs, EXT2_GROUP_BLOCK_BITMAP(fs->gd[i])); 784 start = (i * EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb)) 785 + EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb); 786 sparse = ext2_is_group_sparse(fs, i); 787 788 if (EXT2_GROUP_INODE_TABLE(fs->gd[i]) < start + newitoffset 789 || (sparse && ((EXT2_GROUP_BLOCK_BITMAP(fs->gd[i]) 790 < start + newitoffset - 2) 791 || (EXT2_GROUP_INODE_BITMAP(fs->gd[i]) 792 < start + newitoffset - 1)))) 793 { 794 diff = newitoffset - (EXT2_GROUP_INODE_TABLE(fs->gd[i]) 795 - start); 796 797 for (j=0;j<diff;j++) 798 { 799 blk_t block; 800 blk_t k; 801 802 k = EXT2_GROUP_INODE_TABLE(fs->gd[i]) 803 + fs->inodeblocks + j; 804 block = k % EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb); 805 if (bh->data[block>>3] & _bitmap[block&7]) { 806 k += EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb); 807 if (!ext2_block_relocator_mark(fs, 808 state, k)) 809 { 810 ext2_brelse(bh, 0); 811 return 0; 812 } 813 } 814 } 815 } 816 817 ext2_brelse(bh, 0); 818 } 819 820 if (!ext2_block_relocator_flush(fs, state)) 821 return 0; 822 823 return 1; 824} 825 826static int ext2_block_relocate_shrink(struct ext2_fs *fs, struct ext2_block_relocator_state *state, blk_t newsize) 827{ 828 int diff; 829 int i; 830 831 diff = ped_div_round_up (newsize - EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb), 832 EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb)); 833 diff = ped_div_round_up (diff * sizeof(struct ext2_group_desc), 834 fs->blocksize); 835 diff = fs->gdblocks - diff; 836 837 state->newallocoffset = fs->itoffset + fs->inodeblocks; 838 839 for (i=0;i<fs->numgroups;i++) 840 { 841 struct ext2_buffer_head *bh; 842 blk_t groupsize; 843 blk_t j; 844 blk_t offset; 845 int sparse; 846 blk_t start; 847 int type; 848 849 offset = i * EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb) 850 + EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb); 851 sparse = ext2_is_group_sparse(fs, i); 852 853 if (newsize >= offset + EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb)) 854 continue; /* group will survive */ 855 856 bh = ext2_bread(fs, EXT2_GROUP_BLOCK_BITMAP(fs->gd[i])); 857 858 if (newsize <= offset) 859 type = 2; /* group is fully chopped off */ 860 else 861 type = 1; /* group is partly chopped off */ 862 863 if (!sparse && type == 2) 864 { 865 for (j=EXT2_GROUP_INODE_BITMAP(fs->gd[i])+1; 866 j<EXT2_GROUP_INODE_TABLE(fs->gd[i]); 867 j++) 868 { 869 blk_t k; 870 871 k = j - offset; 872 if (bh->data[k>>3] & _bitmap[k&7]) 873 if (!ext2_block_relocator_mark(fs, state, j)) 874 { 875 ext2_brelse(bh, 0); 876 return 0; 877 } 878 } 879 } 880 881 start = newsize; 882 if (type == 2) 883 start = EXT2_GROUP_INODE_TABLE(fs->gd[i]) 884 + fs->inodeblocks; 885 886 start -= offset; 887 888 groupsize = EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb); 889 if (offset + groupsize > EXT2_SUPER_BLOCKS_COUNT(fs->sb)) 890 groupsize = EXT2_SUPER_BLOCKS_COUNT(fs->sb) - offset; 891 892 for (j=start;j<groupsize;j++) 893 if (bh->data[j>>3] & _bitmap[j&7]) 894 if (!ext2_block_relocator_mark(fs, state, 895 offset + j)) 896 { 897 ext2_brelse(bh, 0); 898 return 0; 899 } 900 901 ext2_brelse(bh, 0); 902 } 903 904 return ext2_block_relocator_flush(fs, state); 905} 906 907int ext2_block_relocate(struct ext2_fs *fs, blk_t newsize) 908{ 909 struct ext2_block_relocator_state state; 910 911 if (fs->opt_verbose) 912 fputs("relocating blocks....\n", stderr); 913 914 state.newallocoffset = 0; 915 state.allocentries = (ext2_relocator_pool_size << 10) / 916 sizeof(struct ext2_block_entry); 917 state.usedentries = 0; 918 state.resolvedentries = 0; 919 state.block = (struct ext2_block_entry *)fs->relocator_pool; 920 921 if (newsize < EXT2_SUPER_BLOCKS_COUNT(fs->sb)) 922 return ext2_block_relocate_shrink(fs, &state, newsize); 923 924 return ext2_block_relocate_grow(fs, &state, newsize); 925} 926 927#endif /* !DISCOVER_ONLY */ 928