Logo Search packages:      
Sourcecode: parted version File versions

ext2_block_relocator.c

/*
    ext2_block_relocator.c -- ext2 block relocator
    Copyright (C) 1998-2000 Free Software Foundation, Inc.
  
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#include "config.h"

#ifndef DISCOVER_ONLY

#include <stdio.h>
#include <stdlib.h>
#include "ext2.h"



struct ext2_block_entry
{
      blk_t       num;
      blk_t       dest;
      blk_t       refblock;
      unsigned    refoffset:16;
      unsigned    isindirectblock:16;
};

struct ext2_block_relocator_state
{
      blk_t              newallocoffset;
      blk_t              allocentries;
      blk_t              usedentries;
      blk_t              resolvedentries;
      struct ext2_block_entry *block;

      struct {
            struct ext2_block_entry *dst;
            int                num;
      } start[4];
};



static int compare_block_entries(const void *x0, const void *x1)
{
      const struct ext2_block_entry *b0;
      const struct ext2_block_entry *b1;

      b0 = (const struct ext2_block_entry *)x0;
      b1 = (const struct ext2_block_entry *)x1;

      if (b0->num < b1->num)
            return -1;

      if (b0->num > b1->num)
            return 1;

      return 0;
}

static int compare_block_entries_ind(const void *x0, const void *x1)
{
      const struct ext2_block_entry *b0;
      const struct ext2_block_entry *b1;

      b0 = (const struct ext2_block_entry *)x0;
      b1 = (const struct ext2_block_entry *)x1;

      if (b0->isindirectblock > b1->isindirectblock)
            return -1;

      if (b0->isindirectblock < b1->isindirectblock)
            return 1;

      return 0;
}

static int compare_block_entries_ref(const void *x0, const void *x1)
{
      const struct ext2_block_entry *b0;
      const struct ext2_block_entry *b1;

      b0 = (const struct ext2_block_entry *)x0;
      b1 = (const struct ext2_block_entry *)x1;

      if (b0->refblock < b1->refblock)
            return -1;

      if (b0->refblock > b1->refblock)
            return 1;

      return 0;
}

struct ext2_block_entry *findit(struct ext2_block_relocator_state *state, blk_t block)
{
      int                min;
      int                max;
      struct ext2_block_entry *retv;
      int                t;
      blk_t              tval;

      max = state->usedentries - 1;
      min = 0;
      retv = NULL;

 repeat:
      if (min > max)
            goto out;

      t = (min + max) >> 1;
      tval = state->block[t].num;

      if (tval > block)
            max = t - 1;

      if (tval < block)
            min = t + 1;

      if (tval != block)
            goto repeat;

      retv = &state->block[t];

 out:
      return retv;
}

static int doblock(struct ext2_fs *fs,
               struct ext2_block_relocator_state *state,
               blk_t blk,
               blk_t refblock,
               off_t refoffset,
               int indirect)
{
      struct ext2_block_entry *ent;

      if ((ent = findit(state, blk)) == NULL)
            return 1;

      if (ent->refblock)
      {
            ped_exception_throw (PED_EXCEPTION_ERROR, PED_EXCEPTION_CANCEL,
                  _("Cross-linked blocks found! better go run e2fsck "
                    "first!"));
            return 0;
      }

      ent->refblock = refblock;
      ent->refoffset = refoffset;
      ent->isindirectblock = indirect;

      state->resolvedentries++;
      state->start[indirect].num++;

      return 1;
}

static int doindblock(struct ext2_fs *fs,
                  struct ext2_block_relocator_state *state,
                  blk_t blk,
                  blk_t refblock,
                  off_t refoffset)
{
      struct ext2_buffer_head *bh;
      int                i;
      uint32_t          *uptr;

      if (!doblock(fs, state, blk, refblock, refoffset, 1))
            return 0;

      bh = ext2_bread(fs, blk);
      if (!bh)
            return 0;
      uptr = (uint32_t *)bh->data;

      for (i=0;i<(fs->blocksize >> 2);i++)
            if (uptr[i])
                  if (!doblock(fs, state, PED_LE32_TO_CPU(uptr[i]), blk,
                             i<<2, 0))
                        return 0;

      if (!ext2_brelse(bh, 0))
            return 0;

      return 1;
}

static int dodindblock(struct ext2_fs *fs,
                   struct ext2_block_relocator_state *state,
                   blk_t blk,
                   blk_t refblock,
                   off_t refoffset)
{
      struct ext2_buffer_head *bh;
      int                i;
      uint32_t          *uptr;

      if (!doblock(fs, state, blk, refblock, refoffset, 2))
            return 0;

      bh = ext2_bread(fs, blk);
      if (!bh)
            return 0;
      uptr = (uint32_t *)bh->data;

      for (i=0;i<(fs->blocksize >> 2);i++)
            if (uptr[i])
                  if (!doindblock(fs, state, PED_LE32_TO_CPU(uptr[i]),
                              blk, i<<2))
                        return 0;

      if (!ext2_brelse(bh, 0))
            return 0;

      return 1;
}

static int dotindblock(struct ext2_fs *fs,
                   struct ext2_block_relocator_state *state,
                   blk_t blk,
                   blk_t refblock,
                   off_t refoffset)
{
      struct ext2_buffer_head *bh;
      int                i;
      uint32_t          *uptr;

      if (!doblock(fs, state, blk, refblock, refoffset, 3))
            return 0;

      bh = ext2_bread(fs, blk);
      if (!bh)
            return 0;
      uptr = (uint32_t *)bh->data;

      for (i=0;i<(fs->blocksize >> 2);i++)
            if (uptr[i])
                  if (!dodindblock(fs, state, PED_LE32_TO_CPU(uptr[i]),
                               blk, i<<2))
                        return 0;

      if (!ext2_brelse(bh, 0))
            return 0;

      return 1;
}



static int doinode(struct ext2_fs *fs, struct ext2_block_relocator_state *state, int inode)
{
      struct ext2_inode buf;

      if (!ext2_read_inode(fs, inode, &buf))
            return 0;

      if (EXT2_INODE_BLOCKS(buf))
      {
            blk_t blk;
            int   i;
            off_t inodeoffset;
            blk_t inodeblock;

            inodeoffset = ext2_get_inode_offset(fs, inode, &inodeblock);

            /* do Hurd block, if there is one... */
            if (EXT2_SUPER_CREATOR_OS(fs->sb) == EXT2_OS_HURD
                && EXT2_INODE_TRANSLATOR(buf)) {
                  if (!doblock(fs,
                             state,
                             EXT2_INODE_TRANSLATOR(buf),
                             inodeblock,
                             inodeoffset + offsetof(struct ext2_inode,
                                    osd1.hurd1.h_i_translator),
                             0))
                        return 0;
            }

            for (i=0;i<EXT2_NDIR_BLOCKS;i++)
                  if ((blk = EXT2_INODE_BLOCK(buf, i)) != 0)
                        if (!doblock(fs,
                                   state,
                                   blk,
                                   inodeblock,
                                   inodeoffset + offsetof(struct ext2_inode, i_block[i]),
                                   0))
                              return 0;

            if ((blk = EXT2_INODE_BLOCK(buf, EXT2_IND_BLOCK)) != 0)
                  if (!doindblock(fs,
                              state,
                              blk,
                              inodeblock,
                              inodeoffset + offsetof(struct ext2_inode, i_block[EXT2_IND_BLOCK])))
                        return 0;

            if ((blk = EXT2_INODE_BLOCK(buf, EXT2_DIND_BLOCK)) != 0)
                  if (!dodindblock(fs,
                               state,
                               blk,
                               inodeblock,
                               inodeoffset + offsetof(struct ext2_inode, i_block[EXT2_DIND_BLOCK])))
                        return 0;

            if ((blk = EXT2_INODE_BLOCK(buf, EXT2_TIND_BLOCK)) != 0)
                  if (!dotindblock(fs,
                               state,
                               blk,
                               inodeblock,
                               inodeoffset + offsetof(struct ext2_inode, i_block[EXT2_TIND_BLOCK])))
                        return 0;

      }

      return 1;
}

static int doscan(struct ext2_fs *fs, struct ext2_block_relocator_state *state)
{
      int i;

      state->start[0].num = 0;
      state->start[1].num = 0;
      state->start[2].num = 0;
      state->start[3].num = 0;

      for (i=0;i<fs->numgroups;i++)
      {
            struct ext2_buffer_head *bh;
            unsigned int             j;
            int                offset;

            if (fs->opt_verbose)
            {
                  fprintf(stderr, " scanning group %i.... ", i);
                  fflush(stderr);
            }

            bh = ext2_bread(fs, EXT2_GROUP_INODE_BITMAP(fs->gd[i]));
            if (!bh)
                  return 0;
            offset = i * EXT2_SUPER_INODES_PER_GROUP(fs->sb) + 1;

            for (j=0;j<EXT2_SUPER_INODES_PER_GROUP(fs->sb);j++)
                  if (bh->data[j>>3] & _bitmap[j&7])
                  {
                        if (!doinode(fs, state, offset + j))
                        {
                              ext2_brelse(bh, 0);
                              return 0;
                        }

                        if (state->resolvedentries == state->usedentries)
                              break;
                  }

            ext2_brelse(bh, 0);

            if (fs->opt_verbose)
            {
                  fprintf(stderr, "%i/%i blocks resolved\r",
                        state->resolvedentries,
                        state->usedentries);
                  fflush(stderr);
            }

            if (state->resolvedentries == state->usedentries)
                  break;
      }

      if (fs->opt_verbose)
            fprintf(stderr, "\n");

      state->start[3].dst = state->block;
      state->start[2].dst = state->start[3].dst + state->start[3].num;
      state->start[1].dst = state->start[2].dst + state->start[2].num;
      state->start[0].dst = state->start[1].dst + state->start[1].num;

      return 1;
}





static int ext2_block_relocator_copy(struct ext2_fs *fs, struct ext2_block_relocator_state *state)
{
      unsigned char *buf;

      ped_exception_fetch_all();
      buf = (unsigned char *) ped_malloc(MAXCONT << fs->logsize);
      if (buf)
      {
            int num;
            int numleft;
            struct ext2_block_entry *ptr;

            ped_exception_leave_all();

            numleft = state->usedentries;
            ptr = state->block;
            while (numleft)
            {
                  num = PED_MIN(numleft, MAXCONT);
                  while (num != 1)
                  {
                        if (ptr[0].num + num-1 == ptr[num-1].num &&
                            ptr[0].dest + num-1 == ptr[num-1].dest)
                              break;

                        num >>= 1;
                  }

                  if (!ext2_bcache_flush_range(fs, ptr[0].num, num))
                        goto error_free_buf;
                  if (!ext2_bcache_flush_range(fs, ptr[0].dest, num))
                        goto error_free_buf;

                  if (!ext2_read_blocks(fs, buf, ptr[0].num, num))
                        goto error_free_buf;
                  if (!ext2_write_blocks(fs, buf, ptr[0].dest, num))
                        goto error_free_buf;

                  ptr += num;
                  numleft -= num;

                  if (fs->opt_verbose)
                  {
                        fprintf(stderr, "copied %i/%i blocks\r",
                              state->usedentries - numleft,
                              state->usedentries);
                        fflush(stderr);
                  }
            }

            ped_free(buf);

            if (fs->opt_safe)
                  ext2_sync(fs);

            if (fs->opt_verbose)
                  fprintf(stderr, "\n");
      }
      else
      {
            blk_t i;

            ped_exception_catch();
            ped_exception_leave_all();

            for (i=0;i<state->usedentries;i++)
            {
                  struct ext2_block_entry *block;

                  block = &state->block[i];
                  if (!ext2_copy_block(fs, block->num, block->dest))
                        goto error;
            }
      }

      return 1;

error_free_buf:
      ped_free(buf);
error:
      return 0;
}

static int ext2_block_relocator_ref(struct ext2_fs *fs, struct ext2_block_relocator_state *state, struct ext2_block_entry *block)
{
      struct ext2_buffer_head *bh;
      static int numerrors = 0;

      if (!(block->refblock || block->refoffset))
      {
            ped_exception_throw (PED_EXCEPTION_BUG, PED_EXCEPTION_CANCEL,
                             _("Block %i has no reference?  Weird"),
                             block->num);
            return 0;
      }

      bh = ext2_bread(fs, block->refblock);
      if (!bh)
            return 0;

      if (fs->opt_debug)
      {
            if (PED_LE32_TO_CPU(*((uint32_t *)(bh->data + block->refoffset)))
                        != block->num) {
                  fprintf(stderr,
                        "block %i ref error! (->%i {%i, %i})\n",
                        block->num,
                        block->dest,
                        block->refblock,
                        block->refoffset);
                  ext2_brelse(bh, 0);

                  if (numerrors++ < 4)
                        return 1;

                  fprintf(stderr, "all is not well!\n");
                  return 0;
            }
      }

      *((uint32_t *)(bh->data + block->refoffset))
            = PED_LE32_TO_CPU(block->dest);
      bh->dirty = 1;
      ext2_brelse(bh, 0);

      ext2_set_block_state(fs, block->dest, 1, 1);
      ext2_set_block_state(fs, block->num, 0, 1);

      if (block->isindirectblock)
      {
            struct ext2_block_entry *dst;
            int                i;
            int                num;

            dst = state->start[block->isindirectblock-1].dst;
            num = state->start[block->isindirectblock-1].num;

            for (i=0;i<num;i++)
                  if (dst[i].refblock == block->num)
                        dst[i].refblock = block->dest;
      }

      return 1;
}

static int ext2_block_relocator_grab_blocks(struct ext2_fs *fs, struct ext2_block_relocator_state *state)
{
      int i;
      blk_t ptr;

      ptr = 0;

      for (i=0;i<fs->numgroups;i++)
            if (EXT2_GROUP_FREE_BLOCKS_COUNT(fs->gd[i]))
            {
                  struct ext2_buffer_head *bh;
                  unsigned int j;
                  int offset;

                  bh = ext2_bread(fs, EXT2_GROUP_BLOCK_BITMAP(fs->gd[i]));
                  offset = i * EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb)
                         + EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb);

                  for (j=state->newallocoffset;
                       j<EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb);
                       j++)
                        if (!(bh->data[j>>3] & _bitmap[j&7]))
                        {
                              state->block[ptr++].dest = offset + j;

                              if (ptr == state->usedentries)
                              {
                                    ext2_brelse(bh, 0);
                                    return 1;
                              }
                        }

                  ext2_brelse(bh, 0);
            }

      return 0;
}

static int ext2_block_relocator_flush(struct ext2_fs *fs, struct ext2_block_relocator_state *state)
{
      int i;

      if (!state->usedentries)
            return 1;

      if (fs->opt_verbose)
            fprintf(stderr, "ext2_block_relocator_flush\n");

      if (fs->opt_debug)
      {
      again:

            for (i=0; (unsigned int) i < state->usedentries-1; i++)
                  if (state->block[i].num >= state->block[i+1].num)
                  {
                        fprintf(stderr,
                              "ext2_block_relocator_flush: "
                              "blocks not in order!\n");

                        qsort(state->block,
                              state->usedentries,
                              sizeof(struct ext2_block_entry),
                              compare_block_entries);
                        goto again;
                  }
      }

      if (!doscan(fs, state))
            return 0;

      if (!ext2_block_relocator_grab_blocks(fs, state))
            return 0;

      if (!ext2_block_relocator_copy(fs, state))
            return 0;

      qsort(state->block,
            state->usedentries,
            sizeof(struct ext2_block_entry),
            compare_block_entries_ind);

      for (i=3;i>=0;i--)
      {
            struct ext2_block_entry *dst;
            int                j;
            int                num;

            dst = state->start[i].dst;
            num = state->start[i].num;

            if (!num)
                  continue;

            if (fs->opt_verbose)
            {
                  /* FIXXXME gross hack */
                  fprintf(stderr, "relocating %s blocks",
                        ((char *[4]){"direct",
                                         "singly indirect",
                                         "doubly indirect",
                                         "triply indirect"})[i]);
                  fflush(stderr);
            }

            qsort(dst,
                  num,
                  sizeof(struct ext2_block_entry),
                  compare_block_entries_ref);

            for (j=0;j<num;j++)
                  if (!ext2_block_relocator_ref(fs, state, &dst[j]))
                        return 0;

            if (fs->opt_safe) {
                  if (!ext2_sync(fs))
                        return 0;
            }

            if (fs->opt_verbose)
                  fprintf(stderr, "\n");
      }

      state->usedentries = 0;
      state->resolvedentries = 0;

      return 1;
}

static int ext2_block_relocator_mark(struct ext2_fs *fs, struct ext2_block_relocator_state *state, blk_t block)
{
      int i;

      if (fs->opt_debug)
      {
            if (!ext2_get_block_state(fs, block) ||
                !ext2_is_data_block(fs, block))
            {
                  ped_exception_throw (PED_EXCEPTION_BUG,
                        PED_EXCEPTION_CANCEL,
                        _("Block %i shouldn't have been marked!"),
                        block);
                  return 0;
            }
      }

      if (state->usedentries == state->allocentries - 1)
            if (!ext2_block_relocator_flush(fs, state))
                  return 0;

      i = state->usedentries;
      state->block[i].num = block;
      state->block[i].dest = 0;
      state->block[i].refblock = 0;
      state->block[i].refoffset = 0;

      state->usedentries++;
      return 1;
}

static int ext2_block_relocate_grow(struct ext2_fs *fs, struct ext2_block_relocator_state *state, blk_t newsize)
{
      blk_t newgdblocks;
      blk_t newitoffset;
      int   i;

      newgdblocks = howmany(newsize - EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb),
                        EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb));
      newgdblocks = howmany(newgdblocks * sizeof(struct ext2_group_desc),
                        fs->blocksize);
      if (newgdblocks == fs->gdblocks)
            return 1;

      newitoffset = newgdblocks + 3;
      state->newallocoffset = newitoffset + fs->inodeblocks;

      for (i=0;i<fs->numgroups;i++)
      {
            struct ext2_buffer_head *bh;
            blk_t              diff;
            blk_t              j;
            blk_t              start;
            int                sparse;

            bh = ext2_bread(fs, EXT2_GROUP_BLOCK_BITMAP(fs->gd[i]));
            start = (i * EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb))
                  + EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb);
            sparse = ext2_is_group_sparse(fs, i);

            if (EXT2_GROUP_INODE_TABLE(fs->gd[i]) < start + newitoffset
                || (sparse && ((EXT2_GROUP_BLOCK_BITMAP(fs->gd[i])
                                    < start + newitoffset - 2)
                         || (EXT2_GROUP_INODE_BITMAP(fs->gd[i])
                                    < start + newitoffset - 1))))
            {
                  diff = newitoffset - (EXT2_GROUP_INODE_TABLE(fs->gd[i])
                                    - start);

                  for (j=0;j<diff;j++)
                  {
                        blk_t k;

                        k = fs->itoffset + fs->inodeblocks + j;
                        if (bh->data[k>>3] & _bitmap[k&7])
                              if (!ext2_block_relocator_mark(fs,
                                              state, start + k))
                              {
                                    ext2_brelse(bh, 0);
                                    return 0;
                              }
                  }
            }

            ext2_brelse(bh, 0);
      }

      if (!ext2_block_relocator_flush(fs, state))
            return 0;

      return 1;
}

static int ext2_block_relocate_shrink(struct ext2_fs *fs, struct ext2_block_relocator_state *state, blk_t newsize)
{
      int diff;
      int i;

      diff = howmany(newsize - EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb),
                   EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb));
      diff = howmany(diff * sizeof(struct ext2_group_desc), fs->blocksize);
      diff = fs->gdblocks - diff;

      state->newallocoffset = fs->itoffset + fs->inodeblocks;

      for (i=0;i<fs->numgroups;i++)
      {
            struct ext2_buffer_head *bh;
            blk_t              groupsize;
            blk_t              j;
            blk_t              offset;
            int                sparse;
            blk_t              start;
            int                type;

            offset = i * EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb)
                   + EXT2_SUPER_FIRST_DATA_BLOCK(fs->sb);
            sparse = ext2_is_group_sparse(fs, i);

            if (newsize >= offset + EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb))
                  continue;         /* group will survive */

            bh = ext2_bread(fs, EXT2_GROUP_BLOCK_BITMAP(fs->gd[i]));

            if (newsize <= offset)
                  type = 2;         /* group is fully chopped off */
            else
                  type = 1;         /* group is partly chopped off */

            if (!sparse && type == 2)
            {
                  for (j=EXT2_GROUP_INODE_BITMAP(fs->gd[i])+1;
                       j<EXT2_GROUP_INODE_TABLE(fs->gd[i]);
                       j++)
                  {
                        blk_t k;

                        k = j - offset;
                        if (bh->data[k>>3] & _bitmap[k&7])
                              if (!ext2_block_relocator_mark(fs, state, j))
                              {
                                    ext2_brelse(bh, 0);
                                    return 0;
                              }
                  }
            }

            start = newsize;
            if (type == 2)
                  start = EXT2_GROUP_INODE_TABLE(fs->gd[i])
                        + fs->inodeblocks;

            start -= offset;

            groupsize = EXT2_SUPER_BLOCKS_PER_GROUP(fs->sb);
            if (offset + groupsize > EXT2_SUPER_BLOCKS_COUNT(fs->sb))
                  groupsize = EXT2_SUPER_BLOCKS_COUNT(fs->sb) - offset;

            for (j=start;j<groupsize;j++)
                  if (bh->data[j>>3] & _bitmap[j&7])
                        if (!ext2_block_relocator_mark(fs, state,
                                                 offset + j))
                        {
                              ext2_brelse(bh, 0);
                              return 0;
                        }

            ext2_brelse(bh, 0);
      }

      return ext2_block_relocator_flush(fs, state);
}

int ext2_block_relocate(struct ext2_fs *fs, blk_t newsize)
{
      struct ext2_block_relocator_state state;

      if (fs->opt_verbose)
            fprintf(stderr, "relocating blocks....\n");

      state.newallocoffset = 0;
      state.allocentries = (ext2_relocator_pool_size << 10) /
            sizeof(struct ext2_block_entry);
      state.usedentries = 0;
      state.resolvedentries = 0;
      state.block = (struct ext2_block_entry *)fs->relocator_pool;

      if (newsize < EXT2_SUPER_BLOCKS_COUNT(fs->sb))
            return ext2_block_relocate_shrink(fs, &state, newsize);

      return ext2_block_relocate_grow(fs, &state, newsize);
}

#endif /* !DISCOVER_ONLY */

Generated by  Doxygen 1.6.0   Back to index