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 */
40 struct 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 */
78 struct 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
94 static 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
111 static 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
128 static 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
145 struct 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 */
182 static 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
212 static 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
242 static 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
272 static 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 */
306 static 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 */
377 static 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
445 static 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
522 error_free_buf:
523 ped_free(buf);
524 error:
525 return 0;
526 }
527
528 static 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 */
598 static 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
636 static 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
725 static 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
757 static 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
826 static 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
907 int 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 */