1N/A/*
1N/A ext2_inode_relocator.c -- ext2 inode relocator
1N/A Copyright (C) 1998-2000, 2007, 2009-2010 Free Software Foundation,
1N/A Inc.
1N/A
1N/A This program is free software; you can redistribute it and/or modify
1N/A it under the terms of the GNU General Public License as published by
1N/A the Free Software Foundation; either version 3 of the License, or
1N/A (at your option) any later version.
1N/A
1N/A This program is distributed in the hope that it will be useful,
1N/A but WITHOUT ANY WARRANTY; without even the implied warranty of
1N/A MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1N/A GNU General Public License for more details.
1N/A
1N/A You should have received a copy of the GNU General Public License
1N/A along with this program. If not, see <http://www.gnu.org/licenses/>.
1N/A*/
1N/A
1N/A#include <config.h>
1N/A
1N/A#ifndef DISCOVER_ONLY
1N/A
1N/A#include <stdio.h>
1N/A#include <stdlib.h>
1N/A#include <sys/stat.h> /* for S_ISDIR */
1N/A#include "ext2.h"
1N/A
1N/A
1N/A
1N/A
1N/A
1N/A
1N/Astruct ext2_reference
1N/A{
1N/A blk_t block;
1N/A off_t offset;
1N/A};
1N/A
1N/Astruct ext2_inode_entry
1N/A{
1N/A ino_t num;
1N/A ino_t dest;
1N/A unsigned numreferences:16;
1N/A unsigned isdir:1;
1N/A struct ext2_reference *ref;
1N/A};
1N/A
1N/Astruct ext2_inode_relocator_state
1N/A{
1N/A int usedentries;
1N/A int resolvedentries;
1N/A struct ext2_inode_entry *inode;
1N/A struct ext2_reference *last;
1N/A};
1N/A
1N/A
1N/A
1N/A
1N/A
1N/Astatic struct ext2_inode_entry *findit(struct ext2_inode_relocator_state *state, ino_t inode)
1N/A{
1N/A int min;
1N/A int max;
1N/A struct ext2_inode_entry *retv;
1N/A int t;
1N/A blk_t tval;
1N/A
1N/A max = state->usedentries - 1;
1N/A min = 0;
1N/A retv = NULL;
1N/A
1N/A repeat:
1N/A if (min > max)
1N/A goto out;
1N/A
1N/A t = (min + max) >> 1;
1N/A tval = state->inode[t].num;
1N/A
1N/A t--;
1N/A if (tval > inode)
1N/A max = t;
1N/A
1N/A t += 2;
1N/A if (tval < inode)
1N/A min = t;
1N/A
1N/A t--;
1N/A
1N/A if (tval != inode)
1N/A goto repeat;
1N/A
1N/A retv = &state->inode[t];
1N/A
1N/A out:
1N/A return retv;
1N/A}
1N/A
1N/Astatic int addref(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, ino_t inode, blk_t block, off_t offset)
1N/A{
1N/A struct ext2_inode_entry *ent;
1N/A int i;
1N/A
1N/A if ((ent = findit(state, inode)) == NULL)
1N/A return 1;
1N/A
1N/A for (i=0;i<ent->numreferences;i++)
1N/A if (!ent->ref[i].block)
1N/A break;
1N/A
1N/A if (i == ent->numreferences)
1N/A {
1N/A ped_exception_throw (PED_EXCEPTION_ERROR, PED_EXCEPTION_CANCEL,
1N/A _("Found an inode with a incorrect link count. "
1N/A "Better go run e2fsck first!"));
1N/A return 0;
1N/A }
1N/A
1N/A if (i == ent->numreferences - 1)
1N/A state->resolvedentries++;
1N/A
1N/A ent->ref[i].block = block;
1N/A ent->ref[i].offset = offset;
1N/A
1N/A return 1;
1N/A}
1N/A
1N/Astatic int doblock(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, blk_t blockno)
1N/A{
1N/A struct ext2_buffer_head *bh;
1N/A off_t offset;
1N/A
1N/A bh = ext2_bread(fs, blockno);
1N/A if (!bh)
1N/A return 0;
1N/A
1N/A offset = 0;
1N/A do
1N/A {
1N/A struct ext2_dir_entry_2 *ptr;
1N/A
1N/A ptr = (struct ext2_dir_entry_2 *)(bh->data + offset);
1N/A
1N/A if (ptr->name_len)
1N/A if (!addref(fs, state, EXT2_DIRENT_INODE(*ptr), blockno,
1N/A offset))
1N/A return 0;
1N/A
1N/A PED_ASSERT (ptr->rec_len > 0, return 0);
1N/A offset += EXT2_DIRENT_REC_LEN (*ptr);
1N/A } while (offset < fs->blocksize);
1N/A
1N/A ext2_brelse(bh, 0);
1N/A return 1;
1N/A}
1N/A
1N/Astatic int doindblock(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, blk_t blockno)
1N/A{
1N/A struct ext2_buffer_head *bh;
1N/A blk_t blk;
1N/A int i;
1N/A
1N/A bh = ext2_bread(fs, blockno);
1N/A
1N/A for (i=0;i<(fs->blocksize>>2);i++)
1N/A if ((blk = PED_LE32_TO_CPU(((uint32_t *)bh->data)[i])) != 0)
1N/A if (!doblock(fs, state, blk))
1N/A return 0;
1N/A
1N/A ext2_brelse(bh, 0);
1N/A return 1;
1N/A}
1N/A
1N/Astatic int dodindblock(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, blk_t blockno)
1N/A{
1N/A struct ext2_buffer_head *bh;
1N/A blk_t blk;
1N/A int i;
1N/A
1N/A bh = ext2_bread(fs, blockno);
1N/A if (!bh)
1N/A return 0;
1N/A
1N/A for (i=0;i<(fs->blocksize>>2);i++)
1N/A if ((blk = PED_LE32_TO_CPU(((uint32_t *)bh->data)[i])) != 0)
1N/A if (!doindblock(fs, state, blk))
1N/A return 0;
1N/A
1N/A ext2_brelse(bh, 0);
1N/A return 1;
1N/A}
1N/A
1N/Astatic int dotindblock(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, blk_t blockno)
1N/A{
1N/A struct ext2_buffer_head *bh;
1N/A blk_t blk;
1N/A int i;
1N/A
1N/A bh = ext2_bread(fs, blockno);
1N/A if (!bh)
1N/A return 0;
1N/A
1N/A for (i=0;i<(fs->blocksize>>2);i++)
1N/A if ((blk = PED_LE32_TO_CPU(((uint32_t *)bh->data)[i])) != 0)
1N/A if (!dodindblock(fs, state, blk))
1N/A return 0;
1N/A
1N/A ext2_brelse(bh, 0);
1N/A return 1;
1N/A}
1N/A
1N/Astatic int doinode(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, ino_t inode)
1N/A{
1N/A struct ext2_inode buf;
1N/A int i;
1N/A
1N/A if (!ext2_read_inode(fs, inode, &buf))
1N/A return 0;
1N/A if (S_ISDIR(EXT2_INODE_MODE(buf)))
1N/A {
1N/A blk_t blk;
1N/A
1N/A for (i=0;i<EXT2_NDIR_BLOCKS;i++)
1N/A if ((blk = EXT2_INODE_BLOCK(buf, i)) != 0)
1N/A if (!doblock(fs, state, blk))
1N/A return 0;
1N/A
1N/A if ((blk = EXT2_INODE_BLOCK(buf, EXT2_IND_BLOCK)) != 0)
1N/A if (!doindblock(fs, state, blk))
1N/A return 0;
1N/A
1N/A if ((blk = EXT2_INODE_BLOCK(buf, EXT2_DIND_BLOCK)) != 0)
1N/A if (!dodindblock(fs, state, blk))
1N/A return 0;
1N/A
1N/A if ((blk = EXT2_INODE_BLOCK(buf, EXT2_TIND_BLOCK)) != 0)
1N/A if (!dotindblock(fs, state, blk))
1N/A return 0;
1N/A }
1N/A
1N/A return 1;
1N/A}
1N/A
1N/Astatic int doscangroup(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, int group)
1N/A{
1N/A struct ext2_buffer_head *bh;
1N/A unsigned int i;
1N/A int offset;
1N/A
1N/A if (fs->opt_verbose)
1N/A fprintf(stderr, " scanning group %i.... ", group);
1N/A
1N/A bh = ext2_bread(fs, EXT2_GROUP_INODE_BITMAP(fs->gd[group]));
1N/A offset = group * EXT2_SUPER_INODES_PER_GROUP(fs->sb) + 1;
1N/A
1N/A for (i=0;i<EXT2_SUPER_INODES_PER_GROUP(fs->sb);i++)
1N/A if (bh->data[i>>3] & _bitmap[i&7])
1N/A {
1N/A if (!doinode(fs, state, offset + i))
1N/A {
1N/A ext2_brelse(bh, 0);
1N/A return 0;
1N/A }
1N/A
1N/A if (state->resolvedentries == state->usedentries)
1N/A break;
1N/A }
1N/A
1N/A ext2_brelse(bh, 0);
1N/A
1N/A if (fs->opt_verbose)
1N/A fprintf(stderr,
1N/A "%i/%i inodes resolved\r",
1N/A state->resolvedentries,
1N/A state->usedentries);
1N/A
1N/A return 1;
1N/A}
1N/A
1N/A/* basically: this builds a dependency graph of the inodes in the entire file
1N/A * system. inodes are only referenced by the directory tree (or the magic
1N/A * ones implicitly, like the bad blocks inode), so we just walk the directory
1N/A * tree adding references.
1N/A */
1N/Astatic int doscan(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
1N/A{
1N/A int i;
1N/A
1N/A /* while the journal will usually be inode 8 (and therefore will never
1N/A * need to be moved), we don't have any guarantee (grrr). So, we
1N/A * need to be prepared to move it... (and update the reference in the
1N/A * super block)
1N/A */
1N/A if (fs->has_internal_journal)
1N/A addref(fs, state, EXT2_SUPER_JOURNAL_INUM(fs->sb),
1N/A 1, offsetof(struct ext2_super_block, s_journal_inum));
1N/A
1N/A if (!doscangroup(fs, state, 0))
1N/A return 0;
1N/A
1N/A if (state->resolvedentries != state->usedentries)
1N/A for (i=fs->numgroups-1;i>0;i--)
1N/A {
1N/A if (!doscangroup(fs, state, i))
1N/A return 0;
1N/A
1N/A if (state->resolvedentries == state->usedentries)
1N/A break;
1N/A }
1N/A
1N/A if (fs->opt_verbose)
1N/A fputc ('\n', stderr);
1N/A
1N/A return 1;
1N/A}
1N/A
1N/A
1N/A
1N/A
1N/A
1N/A
1N/A
1N/Astatic int ext2_inode_relocator_copy(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
1N/A{
1N/A int i;
1N/A
1N/A for (i=0;i<state->usedentries;i++)
1N/A {
1N/A struct ext2_inode buf;
1N/A struct ext2_inode_entry *entry;
1N/A
1N/A entry = &state->inode[i];
1N/A
1N/A if (fs->opt_debug)
1N/A if (!ext2_get_inode_state(fs, entry->num) ||
1N/A ext2_get_inode_state(fs, entry->dest))
1N/A fputs ("inodebitmaperror\n", stderr);
1N/A
1N/A if (!ext2_read_inode(fs, entry->num, &buf))
1N/A return 0;
1N/A if (!ext2_write_inode(fs, entry->dest, &buf))
1N/A return 0;
1N/A
1N/A entry->isdir = S_ISDIR(EXT2_INODE_MODE(buf))?1:0;
1N/A }
1N/A
1N/A if (fs->opt_safe)
1N/A if (!ext2_sync(fs))
1N/A return 0;
1N/A return 1;
1N/A}
1N/A
1N/Astatic int ext2_inode_relocator_finish(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
1N/A{
1N/A int i;
1N/A
1N/A for (i=0;i<state->usedentries;i++)
1N/A {
1N/A struct ext2_inode_entry *entry;
1N/A
1N/A entry = &state->inode[i];
1N/A ext2_set_inode_state(fs, entry->dest, 1, 1);
1N/A ext2_set_inode_state(fs, entry->num, 0, 1);
1N/A ext2_zero_inode(fs, entry->num);
1N/A }
1N/A
1N/A if (fs->opt_safe)
1N/A if (!ext2_sync(fs))
1N/A return 0;
1N/A return 1;
1N/A}
1N/A
1N/Astatic int ext2_inode_relocator_ref(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
1N/A{
1N/A int i;
1N/A static int numerrors = 0;
1N/A
1N/A for (i=0;i<state->usedentries;i++)
1N/A {
1N/A struct ext2_inode_entry *entry;
1N/A int j;
1N/A uint32_t t;
1N/A
1N/A entry = &state->inode[i];
1N/A t = entry->dest;
1N/A
1N/A for (j=0;j<entry->numreferences;j++)
1N/A {
1N/A struct ext2_buffer_head *bh;
1N/A
1N/A bh = ext2_bread(fs, entry->ref[j].block);
1N/A if (!bh)
1N/A return 0;
1N/A
1N/A if (fs->opt_debug)
1N/A {
1N/A if (PED_LE32_TO_CPU((*((uint32_t *)(bh->data + entry->ref[j].offset)))) != entry->num)
1N/A {
1N/A fprintf(stderr,
1N/A "inode %li ref error! (->%li, [%i]={%i, %i})\n",
1N/A (long) entry->num,
1N/A (long) entry->dest,
1N/A j,
1N/A entry->ref[j].block,
1N/A (int) entry->ref[j].offset);
1N/A ext2_brelse(bh, 0);
1N/A
1N/A if (numerrors++ < 4)
1N/A continue;
1N/A
1N/A fputs ("all is not well!\n", stderr);
1N/A return 0;
1N/A }
1N/A }
1N/A
1N/A *((uint32_t *)(bh->data + entry->ref[j].offset))
1N/A = PED_CPU_TO_LE32(t);
1N/A bh->dirty = 1;
1N/A
1N/A ext2_brelse(bh, 0);
1N/A }
1N/A
1N/A if (entry->isdir)
1N/A {
1N/A int oldgroup;
1N/A int newgroup;
1N/A
1N/A oldgroup = (entry->num - 1)
1N/A / EXT2_SUPER_INODES_PER_GROUP(fs->sb);
1N/A newgroup = (entry->dest - 1)
1N/A / EXT2_SUPER_INODES_PER_GROUP(fs->sb);
1N/A
1N/A fs->gd[oldgroup].bg_used_dirs_count = PED_CPU_TO_LE16 (
1N/A EXT2_GROUP_USED_DIRS_COUNT(fs->gd[oldgroup])
1N/A - 1);
1N/A fs->gd[newgroup].bg_used_dirs_count = PED_CPU_TO_LE16 (
1N/A EXT2_GROUP_USED_DIRS_COUNT(fs->gd[newgroup])
1N/A + 1);
1N/A
1N/A fs->metadirty = EXT2_META_GD;
1N/A }
1N/A }
1N/A
1N/A if (fs->opt_safe)
1N/A if (!ext2_sync(fs))
1N/A return 0;
1N/A
1N/A return 1;
1N/A}
1N/A
1N/Astatic int ext2_inode_relocator_grab_inodes(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
1N/A{
1N/A int i;
1N/A int ptr;
1N/A
1N/A ptr = 0;
1N/A
1N/A for (i=0;i<fs->numgroups;i++)
1N/A if (EXT2_GROUP_FREE_INODES_COUNT(fs->gd[i]))
1N/A {
1N/A struct ext2_buffer_head *bh;
1N/A unsigned int j;
1N/A int offset;
1N/A
1N/A bh = ext2_bread(fs, EXT2_GROUP_INODE_BITMAP(fs->gd[i]));
1N/A if (!bh)
1N/A return 0;
1N/A offset = i * EXT2_SUPER_INODES_PER_GROUP(fs->sb) + 1;
1N/A
1N/A j = i ? 0 : 13;
1N/A for (;j<EXT2_SUPER_INODES_PER_GROUP(fs->sb);j++)
1N/A if (!(bh->data[j>>3] & _bitmap[j&7]))
1N/A {
1N/A state->inode[ptr++].dest = offset + j;
1N/A
1N/A if (ptr == state->usedentries)
1N/A {
1N/A ext2_brelse(bh, 0);
1N/A return 1;
1N/A }
1N/A }
1N/A
1N/A ext2_brelse(bh, 0);
1N/A }
1N/A
1N/A ped_exception_throw (PED_EXCEPTION_ERROR, PED_EXCEPTION_CANCEL,
1N/A _("Not enough free inodes!"));
1N/A return 0;
1N/A}
1N/A
1N/Astatic int ext2_inode_relocator_flush(struct ext2_fs *fs, struct ext2_inode_relocator_state *state)
1N/A{
1N/A if (!state->usedentries)
1N/A return 1;
1N/A
1N/A if (!doscan(fs, state))
1N/A return 0;
1N/A
1N/A if (!ext2_inode_relocator_grab_inodes(fs, state))
1N/A return 0;
1N/A
1N/A if (!ext2_inode_relocator_copy(fs, state))
1N/A return 0;
1N/A
1N/A if (!ext2_inode_relocator_ref(fs, state))
1N/A return 0;
1N/A
1N/A if (!ext2_inode_relocator_finish(fs, state))
1N/A return 0;
1N/A
1N/A state->usedentries = 0;
1N/A state->resolvedentries = 0;
1N/A state->last = (struct ext2_reference *)fs->relocator_pool_end;
1N/A
1N/A if (fs->opt_safe)
1N/A if (!ext2_sync(fs))
1N/A return 0;
1N/A
1N/A return 1;
1N/A}
1N/A
1N/Astatic int ext2_inode_relocator_mark(struct ext2_fs *fs, struct ext2_inode_relocator_state *state, ino_t inode)
1N/A{
1N/A struct ext2_inode buf;
1N/A struct ext2_inode_entry *ent;
1N/A int i;
1N/A
1N/A if (!ext2_read_inode(fs, inode, &buf))
1N/A return 0;
1N/A
1N/A {
1N/A register void *adv;
1N/A register void *rec;
1N/A
1N/A adv = state->inode + state->usedentries + 1;
1N/A rec = state->last - EXT2_INODE_LINKS_COUNT(buf);
1N/A
1N/A if (adv >= rec)
1N/A ext2_inode_relocator_flush(fs, state);
1N/A }
1N/A
1N/A state->last -= EXT2_INODE_LINKS_COUNT(buf);
1N/A
1N/A ent = &state->inode[state->usedentries];
1N/A ent->num = inode;
1N/A ent->dest = 0;
1N/A ent->numreferences = EXT2_INODE_LINKS_COUNT(buf);
1N/A ent->ref = state->last;
1N/A
1N/A for (i=0;i<ent->numreferences;i++)
1N/A {
1N/A ent->ref[i].block = 0;
1N/A ent->ref[i].offset = 0;
1N/A }
1N/A
1N/A state->usedentries++;
1N/A
1N/A return 1;
1N/A}
1N/A
1N/A
1N/Aint ext2_inode_relocate(struct ext2_fs *fs, int newgroups)
1N/A{
1N/A int i;
1N/A struct ext2_inode_relocator_state state;
1N/A
1N/A if (fs->opt_verbose)
1N/A fputs ("ext2_inode_relocate\n", stderr);
1N/A
1N/A state.usedentries = 0;
1N/A state.resolvedentries = 0;
1N/A state.inode = (struct ext2_inode_entry *)fs->relocator_pool;
1N/A state.last = (struct ext2_reference *)fs->relocator_pool_end;
1N/A
1N/A for (i=newgroups;i<fs->numgroups;i++)
1N/A {
1N/A struct ext2_buffer_head *bh;
1N/A unsigned int j;
1N/A int offset;
1N/A
1N/A bh = ext2_bread(fs, EXT2_GROUP_INODE_BITMAP(fs->gd[i]));
1N/A if (!bh)
1N/A return 0;
1N/A offset = i * EXT2_SUPER_INODES_PER_GROUP(fs->sb) + 1;
1N/A
1N/A for (j=0;j<EXT2_SUPER_INODES_PER_GROUP(fs->sb);j++)
1N/A if (bh->data[j>>3] & _bitmap[j&7])
1N/A ext2_inode_relocator_mark(fs, &state,
1N/A offset + j);
1N/A
1N/A ext2_brelse(bh, 0);
1N/A }
1N/A
1N/A if (!ext2_inode_relocator_flush(fs, &state))
1N/A return 0;
1N/A
1N/A return 1;
1N/A}
1N/A#endif /* !DISCOVER_ONLY */