1 /*
2 ext2_inode_relocator.c -- ext2 inode 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 <sys/stat.h> /* for S_ISDIR */
26 #include "ext2.h"
27
28
29
30
31
32
33 struct ext2_reference
34 {
35 blk_t block;
36 off_t offset;
37 };
38
39 struct ext2_inode_entry
40 {
41 ino_t num;
42 ino_t dest;
43 unsigned numreferences:16;
44 unsigned isdir:1;
45 struct ext2_reference *ref;
46 };
47
48 struct ext2_inode_relocator_state
49 {
50 int usedentries;
51 int resolvedentries;
52 struct ext2_inode_entry *inode;
53 struct ext2_reference *last;
54 };
55
56
57
58
59
60 static struct ext2_inode_entry *findit(struct ext2_inode_relocator_state *state, ino_t inode)
61 {
62 int min;
63 int max;
64 struct ext2_inode_entry *retv;
65 int t;
66 blk_t tval;
67
68 max = state->usedentries - 1;
69 min = 0;
70 retv = NULL;
71
72 repeat:
73 if (min > max)
74 goto out;
75
76 t = (min + max) >> 1;
77 tval = state->inode[t].num;
78
79 t--;
80 if (tval > inode)
81 max = t;
82
83 t += 2;
84 if (tval < inode)
85 min = t;
86
87 t--;
88
89 if (tval != inode)
90 goto repeat;
91
92 retv = &state->inode[t];
93
94 out:
95 return retv;
96 }
97
98 static int addref(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, ino_t inode, blk_t block, off_t offset)
99 {
100 struct ext2_inode_entry *ent;
101 int i;
102
103 if ((ent = findit(state, inode)) == NULL)
104 return 1;
105
106 for (i=0;i<ent->numreferences;i++)
107 if (!ent->ref[i].block)
108 break;
109
110 if (i == ent->numreferences)
111 {
112 ped_exception_throw (PED_EXCEPTION_ERROR, PED_EXCEPTION_CANCEL,
113 _("Found an inode with a incorrect link count. "
114 "Better go run e2fsck first!"));
115 return 0;
116 }
117
118 if (i == ent->numreferences - 1)
119 state->resolvedentries++;
120
121 ent->ref[i].block = block;
122 ent->ref[i].offset = offset;
123
124 return 1;
125 }
126
127 static int doblock(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, blk_t blockno)
128 {
129 struct ext2_buffer_head *bh;
130 off_t offset;
131
132 bh = ext2_bread(fs, blockno);
133 if (!bh)
134 return 0;
135
136 offset = 0;
137 do
138 {
139 struct ext2_dir_entry_2 *ptr;
140
141 ptr = (struct ext2_dir_entry_2 *)(bh->data + offset);
142
143 if (ptr->name_len)
144 if (!addref(fs, state, EXT2_DIRENT_INODE(*ptr), blockno,
145 offset))
146 return 0;
147
148 PED_ASSERT (ptr->rec_len > 0, return 0);
149 offset += EXT2_DIRENT_REC_LEN (*ptr);
150 } while (offset < fs->blocksize);
151
152 ext2_brelse(bh, 0);
153 return 1;
154 }
155
156 static int doindblock(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, blk_t blockno)
157 {
158 struct ext2_buffer_head *bh;
159 blk_t blk;
160 int i;
161
162 bh = ext2_bread(fs, blockno);
163
164 for (i=0;i<(fs->blocksize>>2);i++)
165 if ((blk = PED_LE32_TO_CPU(((uint32_t *)bh->data)[i])) != 0)
166 if (!doblock(fs, state, blk))
167 return 0;
168
169 ext2_brelse(bh, 0);
170 return 1;
171 }
172
173 static int dodindblock(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, blk_t blockno)
174 {
175 struct ext2_buffer_head *bh;
176 blk_t blk;
177 int i;
178
179 bh = ext2_bread(fs, blockno);
180 if (!bh)
181 return 0;
182
183 for (i=0;i<(fs->blocksize>>2);i++)
184 if ((blk = PED_LE32_TO_CPU(((uint32_t *)bh->data)[i])) != 0)
185 if (!doindblock(fs, state, blk))
186 return 0;
187
188 ext2_brelse(bh, 0);
189 return 1;
190 }
191
192 static int dotindblock(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, blk_t blockno)
193 {
194 struct ext2_buffer_head *bh;
195 blk_t blk;
196 int i;
197
198 bh = ext2_bread(fs, blockno);
199 if (!bh)
200 return 0;
201
202 for (i=0;i<(fs->blocksize>>2);i++)
203 if ((blk = PED_LE32_TO_CPU(((uint32_t *)bh->data)[i])) != 0)
204 if (!dodindblock(fs, state, blk))
205 return 0;
206
207 ext2_brelse(bh, 0);
208 return 1;
209 }
210
211 static int doinode(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, ino_t inode)
212 {
213 struct ext2_inode buf;
214 int i;
215
216 if (!ext2_read_inode(fs, inode, &buf))
217 return 0;
218 if (S_ISDIR(EXT2_INODE_MODE(buf)))
219 {
220 blk_t blk;
221
222 for (i=0;i<EXT2_NDIR_BLOCKS;i++)
223 if ((blk = EXT2_INODE_BLOCK(buf, i)) != 0)
224 if (!doblock(fs, state, blk))
225 return 0;
226
227 if ((blk = EXT2_INODE_BLOCK(buf, EXT2_IND_BLOCK)) != 0)
228 if (!doindblock(fs, state, blk))
229 return 0;
230
231 if ((blk = EXT2_INODE_BLOCK(buf, EXT2_DIND_BLOCK)) != 0)
232 if (!dodindblock(fs, state, blk))
233 return 0;
234
235 if ((blk = EXT2_INODE_BLOCK(buf, EXT2_TIND_BLOCK)) != 0)
236 if (!dotindblock(fs, state, blk))
237 return 0;
238 }
239
240 return 1;
241 }
242
243 static int doscangroup(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, int group)
244 {
245 struct ext2_buffer_head *bh;
246 unsigned int i;
247 int offset;
248
249 if (fs->opt_verbose)
250 fprintf(stderr, " scanning group %i.... ", group);
251
252 bh = ext2_bread(fs, EXT2_GROUP_INODE_BITMAP(fs->gd[group]));
253 offset = group * EXT2_SUPER_INODES_PER_GROUP(fs->sb) + 1;
254
255 for (i=0;i<EXT2_SUPER_INODES_PER_GROUP(fs->sb);i++)
256 if (bh->data[i>>3] & _bitmap[i&7])
257 {
258 if (!doinode(fs, state, offset + i))
259 {
260 ext2_brelse(bh, 0);
261 return 0;
262 }
263
264 if (state->resolvedentries == state->usedentries)
265 break;
266 }
267
268 ext2_brelse(bh, 0);
269
270 if (fs->opt_verbose)
271 fprintf(stderr,
272 "%i/%i inodes resolved\r",
273 state->resolvedentries,
274 state->usedentries);
275
276 return 1;
277 }
278
279 /* basically: this builds a dependency graph of the inodes in the entire file
280 * system. inodes are only referenced by the directory tree (or the magic
281 * ones implicitly, like the bad blocks inode), so we just walk the directory
282 * tree adding references.
283 */
284 static int doscan(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
285 {
286 int i;
287
288 /* while the journal will usually be inode 8 (and therefore will never
289 * need to be moved), we don't have any guarantee (grrr). So, we
290 * need to be prepared to move it... (and update the reference in the
291 * super block)
292 */
293 if (fs->has_internal_journal)
294 addref(fs, state, EXT2_SUPER_JOURNAL_INUM(fs->sb),
295 1, offsetof(struct ext2_super_block, s_journal_inum));
296
297 if (!doscangroup(fs, state, 0))
298 return 0;
299
300 if (state->resolvedentries != state->usedentries)
301 for (i=fs->numgroups-1;i>0;i--)
302 {
303 if (!doscangroup(fs, state, i))
304 return 0;
305
306 if (state->resolvedentries == state->usedentries)
307 break;
308 }
309
310 if (fs->opt_verbose)
311 fputc ('\n', stderr);
312
313 return 1;
314 }
315
316
317
318
319
320
321
322 static int ext2_inode_relocator_copy(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
323 {
324 int i;
325
326 for (i=0;i<state->usedentries;i++)
327 {
328 struct ext2_inode buf;
329 struct ext2_inode_entry *entry;
330
331 entry = &state->inode[i];
332
333 if (fs->opt_debug)
334 if (!ext2_get_inode_state(fs, entry->num) ||
335 ext2_get_inode_state(fs, entry->dest))
336 fputs ("inodebitmaperror\n", stderr);
337
338 if (!ext2_read_inode(fs, entry->num, &buf))
339 return 0;
340 if (!ext2_write_inode(fs, entry->dest, &buf))
341 return 0;
342
343 entry->isdir = S_ISDIR(EXT2_INODE_MODE(buf))?1:0;
344 }
345
346 if (fs->opt_safe)
347 if (!ext2_sync(fs))
348 return 0;
349 return 1;
350 }
351
352 static int ext2_inode_relocator_finish(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
353 {
354 int i;
355
356 for (i=0;i<state->usedentries;i++)
357 {
358 struct ext2_inode_entry *entry;
359
360 entry = &state->inode[i];
361 ext2_set_inode_state(fs, entry->dest, 1, 1);
362 ext2_set_inode_state(fs, entry->num, 0, 1);
363 ext2_zero_inode(fs, entry->num);
364 }
365
366 if (fs->opt_safe)
367 if (!ext2_sync(fs))
368 return 0;
369 return 1;
370 }
371
372 static int ext2_inode_relocator_ref(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
373 {
374 int i;
375 static int numerrors = 0;
376
377 for (i=0;i<state->usedentries;i++)
378 {
379 struct ext2_inode_entry *entry;
380 int j;
381 uint32_t t;
382
383 entry = &state->inode[i];
384 t = entry->dest;
385
386 for (j=0;j<entry->numreferences;j++)
387 {
388 struct ext2_buffer_head *bh;
389
390 bh = ext2_bread(fs, entry->ref[j].block);
391 if (!bh)
392 return 0;
393
394 if (fs->opt_debug)
395 {
396 if (PED_LE32_TO_CPU((*((uint32_t *)(bh->data + entry->ref[j].offset)))) != entry->num)
397 {
398 fprintf(stderr,
399 "inode %li ref error! (->%li, [%i]={%i, %i})\n",
400 (long) entry->num,
401 (long) entry->dest,
402 j,
403 entry->ref[j].block,
404 (int) entry->ref[j].offset);
405 ext2_brelse(bh, 0);
406
407 if (numerrors++ < 4)
408 continue;
409
410 fputs ("all is not well!\n", stderr);
411 return 0;
412 }
413 }
414
415 *((uint32_t *)(bh->data + entry->ref[j].offset))
416 = PED_CPU_TO_LE32(t);
417 bh->dirty = 1;
418
419 ext2_brelse(bh, 0);
420 }
421
422 if (entry->isdir)
423 {
424 int oldgroup;
425 int newgroup;
426
427 oldgroup = (entry->num - 1)
428 / EXT2_SUPER_INODES_PER_GROUP(fs->sb);
429 newgroup = (entry->dest - 1)
430 / EXT2_SUPER_INODES_PER_GROUP(fs->sb);
431
432 fs->gd[oldgroup].bg_used_dirs_count = PED_CPU_TO_LE16 (
433 EXT2_GROUP_USED_DIRS_COUNT(fs->gd[oldgroup])
434 - 1);
435 fs->gd[newgroup].bg_used_dirs_count = PED_CPU_TO_LE16 (
436 EXT2_GROUP_USED_DIRS_COUNT(fs->gd[newgroup])
437 + 1);
438
439 fs->metadirty = EXT2_META_GD;
440 }
441 }
442
443 if (fs->opt_safe)
444 if (!ext2_sync(fs))
445 return 0;
446
447 return 1;
448 }
449
450 static int ext2_inode_relocator_grab_inodes(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
451 {
452 int i;
453 int ptr;
454
455 ptr = 0;
456
457 for (i=0;i<fs->numgroups;i++)
458 if (EXT2_GROUP_FREE_INODES_COUNT(fs->gd[i]))
459 {
460 struct ext2_buffer_head *bh;
461 unsigned int j;
462 int offset;
463
464 bh = ext2_bread(fs, EXT2_GROUP_INODE_BITMAP(fs->gd[i]));
465 if (!bh)
466 return 0;
467 offset = i * EXT2_SUPER_INODES_PER_GROUP(fs->sb) + 1;
468
469 j = i ? 0 : 13;
470 for (;j<EXT2_SUPER_INODES_PER_GROUP(fs->sb);j++)
471 if (!(bh->data[j>>3] & _bitmap[j&7]))
472 {
473 state->inode[ptr++].dest = offset + j;
474
475 if (ptr == state->usedentries)
476 {
477 ext2_brelse(bh, 0);
478 return 1;
479 }
480 }
481
482 ext2_brelse(bh, 0);
483 }
484
485 ped_exception_throw (PED_EXCEPTION_ERROR, PED_EXCEPTION_CANCEL,
486 _("Not enough free inodes!"));
487 return 0;
488 }
489
490 static int ext2_inode_relocator_flush(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
491 {
492 if (!state->usedentries)
493 return 1;
494
495 if (!doscan(fs, state))
496 return 0;
497
498 if (!ext2_inode_relocator_grab_inodes(fs, state))
499 return 0;
500
501 if (!ext2_inode_relocator_copy(fs, state))
502 return 0;
503
504 if (!ext2_inode_relocator_ref(fs, state))
505 return 0;
506
507 if (!ext2_inode_relocator_finish(fs, state))
508 return 0;
509
510 state->usedentries = 0;
511 state->resolvedentries = 0;
512 state->last = (struct ext2_reference *)fs->relocator_pool_end;
513
514 if (fs->opt_safe)
515 if (!ext2_sync(fs))
516 return 0;
517
518 return 1;
519 }
520
521 static int ext2_inode_relocator_mark(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, ino_t inode)
522 {
523 struct ext2_inode buf;
524 struct ext2_inode_entry *ent;
525 int i;
526
527 if (!ext2_read_inode(fs, inode, &buf))
528 return 0;
529
530 {
531 register void *adv;
532 register void *rec;
533
534 adv = state->inode + state->usedentries + 1;
535 rec = state->last - EXT2_INODE_LINKS_COUNT(buf);
536
537 if (adv >= rec)
538 ext2_inode_relocator_flush(fs, state);
539 }
540
541 state->last -= EXT2_INODE_LINKS_COUNT(buf);
542
543 ent = &state->inode[state->usedentries];
544 ent->num = inode;
545 ent->dest = 0;
546 ent->numreferences = EXT2_INODE_LINKS_COUNT(buf);
547 ent->ref = state->last;
548
549 for (i=0;i<ent->numreferences;i++)
550 {
551 ent->ref[i].block = 0;
552 ent->ref[i].offset = 0;
553 }
554
555 state->usedentries++;
556
557 return 1;
558 }
559
560
561 int ext2_inode_relocate(struct ext2_fs *fs, int newgroups)
562 {
563 int i;
564 struct ext2_inode_relocator_state state;
565
566 if (fs->opt_verbose)
567 fputs ("ext2_inode_relocate\n", stderr);
568
569 state.usedentries = 0;
570 state.resolvedentries = 0;
571 state.inode = (struct ext2_inode_entry *)fs->relocator_pool;
572 state.last = (struct ext2_reference *)fs->relocator_pool_end;
573
574 for (i=newgroups;i<fs->numgroups;i++)
575 {
576 struct ext2_buffer_head *bh;
577 unsigned int j;
578 int offset;
579
580 bh = ext2_bread(fs, EXT2_GROUP_INODE_BITMAP(fs->gd[i]));
581 if (!bh)
582 return 0;
583 offset = i * EXT2_SUPER_INODES_PER_GROUP(fs->sb) + 1;
584
585 for (j=0;j<EXT2_SUPER_INODES_PER_GROUP(fs->sb);j++)
586 if (bh->data[j>>3] & _bitmap[j&7])
587 ext2_inode_relocator_mark(fs, &state,
588 offset + j);
589
590 ext2_brelse(bh, 0);
591 }
592
593 if (!ext2_inode_relocator_flush(fs, &state))
594 return 0;
595
596 return 1;
597 }
598 #endif /* !DISCOVER_ONLY */
599