ext2_block_relocator.c revision 7e7bd3dccbfe8f79e25e5c1554b5bc3a9aaca321
/*
ext2_block_relocator.c -- ext2 block relocator
Copyright (C) 1998-2000, 2007 Free Software Foundation, Inc.
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 3 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, see <http://www.gnu.org/licenses/>.
*/
#include <config.h>
#ifndef DISCOVER_ONLY
#include <stdio.h>
#include <stdlib.h>
#include "ext2.h"
/* This struct describes a single block that will be relocated. The
* block's original location is "num", and its new location is "dest".
* The block is presumebly referred to by some other block in the file
* system, which is recorded as "refblock". (Only one reference to
* the block is allowed by the block relocator.) "refoffset" describes
* the location within the refblock in which the block is referenced.
* "isindirect" is 0 for direct, 1 for single-indirect, 2 for
* double-indirect, etc.
*
* The algorithms in the file fill the entries of this struct in this order:
* num, refblock/refoffset/isindirectblock, dest.
*/
struct ext2_block_entry
{
unsigned refoffset:16;
unsigned isindirectblock:16;
};
/* This struct contains all data structures relevant to the block relocator.
* - newallocoffset is the distance between the start of a block group,
* and the first data block in the group. This can change when a
* filesystem is resized, because the size of the group descriptors is
* proportional to the size of the filesystem.
*
* - allocentries is the size of the "block" array. It is a tuneable
* parameter that determines how many blocks can be moved in each
* pass.
*
* - usedentries says how many entries of the "block" array have been
* used. That is, how many blocks have been scheduled so far to
* be moved.
*
* - resolvedentries is the number of blocks whose referencing block
* has been found and recorded in block[.]->refblock, etc.
*
* - block is an array that records which blocks need to be moved, and
* where they will be moved to, etc. At some point in the algorithm, this
* array gets sorted (grep for qsort!) by indirectness.
*
* - start: each entry in this array corresponds to a level of
* indirectness (0-3). Each level has two items: dst and num. "num"
* is the number of blocks inside "block" of that level of indirectness.
* After doscan() is finished, and the level of indirectness of each
* block is known, "block" is sorted (see above). The "dst" pointer
* is a pointer inside "block" that indicates the start of the portion
* of the array containg blocks of that level of indirectness.
*/
struct ext2_block_relocator_state
{
struct ext2_block_entry *block;
struct {
struct ext2_block_entry *dst;
int num;
} start[4];
};
{
const struct ext2_block_entry *b0;
const struct ext2_block_entry *b1;
return -1;
return 1;
return 0;
}
{
const struct ext2_block_entry *b0;
const struct ext2_block_entry *b1;
return -1;
return 1;
return 0;
}
{
const struct ext2_block_entry *b0;
const struct ext2_block_entry *b1;
return -1;
return 1;
return 0;
}
{
int min;
int max;
struct ext2_block_entry *retv;
int t;
min = 0;
goto out;
max = t - 1;
min = t + 1;
goto repeat;
out:
return retv;
}
/* This function adds records a reference to a block ("blk"), if that
* block is scheduled to be moved.
*/
struct ext2_block_relocator_state *state,
int indirect)
{
struct ext2_block_entry *ent;
return 1;
{
_("Cross-linked blocks found! Better go run e2fsck "
"first!"));
return 0;
}
state->resolvedentries++;
return 1;
}
struct ext2_block_relocator_state *state,
{
struct ext2_buffer_head *bh;
int i;
return 0;
if (!bh)
return 0;
if (uptr[i])
i<<2, 0))
return 0;
if (!ext2_brelse(bh, 0))
return 0;
return 1;
}
struct ext2_block_relocator_state *state,
{
struct ext2_buffer_head *bh;
int i;
return 0;
if (!bh)
return 0;
if (uptr[i])
blk, i<<2))
return 0;
if (!ext2_brelse(bh, 0))
return 0;
return 1;
}
struct ext2_block_relocator_state *state,
{
struct ext2_buffer_head *bh;
int i;
return 0;
if (!bh)
return 0;
if (uptr[i])
blk, i<<2))
return 0;
if (!ext2_brelse(bh, 0))
return 0;
return 1;
}
/* This function records any block references from an inode to blocks that are
* scheduled to be moved.
*/
{
struct ext2_inode buf;
return 0;
if (EXT2_INODE_BLOCKS(buf))
{
int i;
/* do Hurd block, if there is one... */
&& EXT2_INODE_TRANSLATOR(buf)) {
0))
return 0;
}
for (i=0;i<EXT2_NDIR_BLOCKS;i++)
blk,
0))
return 0;
if (!doindblock(fs,
blk,
return 0;
if (!dodindblock(fs,
blk,
return 0;
if (!dotindblock(fs,
blk,
return 0;
}
return 1;
}
/* This function scans the entire filesystem, to find all references to blocks
* that are scheduled to be moved.
*/
{
int i;
{
struct ext2_buffer_head *bh;
unsigned int j;
int offset;
if (fs->opt_verbose)
{
}
if (!bh)
return 0;
{
{
ext2_brelse(bh, 0);
return 0;
}
break;
}
ext2_brelse(bh, 0);
if (fs->opt_verbose)
{
state->usedentries);
}
break;
}
if (fs->opt_verbose)
return 1;
}
{
unsigned char *buf;
if (buf)
{
int num;
int numleft;
struct ext2_block_entry *ptr;
while (numleft)
{
while (num != 1)
{
break;
num >>= 1;
}
goto error_free_buf;
goto error_free_buf;
goto error_free_buf;
goto error_free_buf;
if (fs->opt_verbose)
{
state->usedentries);
}
}
if (fs->opt_verbose)
}
else
{
blk_t i;
for (i=0;i<state->usedentries;i++)
{
struct ext2_block_entry *block;
goto error;
}
}
return 1;
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;
{
_("Block %i has no reference? Weird."),
return 0;
}
if (!bh)
return 0;
{
"block %i ref error! (->%i {%i, %i})\n",
ext2_brelse(bh, 0);
if (numerrors++ < 4)
return 1;
return 0;
}
}
ext2_brelse(bh, 0);
if (block->isindirectblock)
{
struct ext2_block_entry *dst;
int i;
int num;
for (i=0;i<num;i++)
}
return 1;
}
/* This function allocates new locations for blocks that are scheduled to move
* (inside state->blocks).
*
* FIXME: doesn't seem to handle sparse block groups. That is, there might be
* some free space that could be exploited in resizing that currently isn't...
*
* FIXME: should throw an exception if it fails to allocate blocks.
*/
static int ext2_block_relocator_grab_blocks(struct ext2_fs *fs, struct ext2_block_relocator_state *state)
{
int i;
ptr = 0;
{
struct ext2_buffer_head *bh;
unsigned int j;
int offset;
for (j=state->newallocoffset;
j++)
{
{
ext2_brelse(bh, 0);
return 1;
}
}
ext2_brelse(bh, 0);
}
return 0;
}
{
int i;
if (!state->usedentries)
return 1;
if (fs->opt_verbose)
{
{
fputs("ext2_block_relocator_flush: "
"blocks not in order!\n", stderr);
sizeof(struct ext2_block_entry),
goto again;
}
}
return 0;
return 0;
return 0;
sizeof(struct ext2_block_entry),
for (i=3;i>=0;i--)
{
struct ext2_block_entry *dst;
int j;
int num;
if (!num)
continue;
if (fs->opt_verbose)
{
/* FIXXXME gross hack */
((char *[4]){"direct",
"singly indirect",
"doubly indirect",
"triply indirect"})[i]);
}
num,
sizeof(struct ext2_block_entry),
for (j=0;j<num;j++)
return 0;
return 0;
}
if (fs->opt_verbose)
}
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;
{
{
_("Block %i shouldn't have been marked "
"(%d, %d)!"), block,
}
}
return 0;
i = state->usedentries;
state->usedentries++;
return 1;
}
static int ext2_block_relocate_grow(struct ext2_fs *fs, struct ext2_block_relocator_state *state, blk_t newsize)
{
int i;
* sizeof(struct ext2_group_desc),
return 1;
{
struct ext2_buffer_head *bh;
blk_t j;
int sparse;
{
- start);
for (j=0;j<diff;j++)
{
blk_t k;
+ fs->inodeblocks + j;
if (!ext2_block_relocator_mark(fs,
state, k))
{
ext2_brelse(bh, 0);
return 0;
}
}
}
}
ext2_brelse(bh, 0);
}
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;
{
struct ext2_buffer_head *bh;
blk_t j;
int sparse;
int type;
continue; /* group will survive */
else
{
j++)
{
blk_t k;
k = j - offset;
{
ext2_brelse(bh, 0);
return 0;
}
}
}
if (type == 2)
+ fs->inodeblocks;
offset + j))
{
ext2_brelse(bh, 0);
return 0;
}
ext2_brelse(bh, 0);
}
}
{
struct ext2_block_relocator_state state;
if (fs->opt_verbose)
state.newallocoffset = 0;
sizeof(struct ext2_block_entry);
state.usedentries = 0;
state.resolvedentries = 0;
}
#endif /* !DISCOVER_ONLY */