On Thu, Oct 10, 2013 at 04:46:23PM +0200, Lukáš Czerner wrote:
> On Mon, 30 Sep 2013, Darrick J. Wong wrote:
>
> > Date: Mon, 30 Sep 2013 18:28:31 -0700
> > From: Darrick J. Wong <darrick.wong@xxxxxxxxxx>
> > To: tytso@xxxxxxx, darrick.wong@xxxxxxxxxx
> > Cc: linux-ext4@xxxxxxxxxxxxxxx
> > Subject: [PATCH 17/31] libext2fs: Refactor u32-list to handle 32 and 64-bit
> > data types
> >
> > The curernt ext2_u32_list implementation manages a sorted sparse list of 32-bit
> > numbers. This is currently used to collect directory inodes for rehashing in
> > e2fsck, and creating a list of bad blocks for mkfs. However, block numbers are
> > now 64-bit, so we need to refactor the sparse list to be able to handle both 32
> > and 64-bit numbers.
> >
> > Signed-off-by: Darrick J. Wong <darrick.wong@xxxxxxxxxx>
> > ---
> > lib/ext2fs/badblocks.c | 271 +++++++++++++++++++++++++++++++++++++-----------
> > lib/ext2fs/ext2fs.h | 23 +++-
> > lib/ext2fs/ext2fsP.h | 13 +-
> > lib/ext2fs/inode.c | 12 +-
> > 4 files changed, 237 insertions(+), 82 deletions(-)
> >
>
> -- snip --
>
> >
> > @@ -105,64 +129,107 @@ errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src,
> > /*
> > * This procedure adds a block to a badblocks list.
> > */
> > -errcode_t ext2fs_u32_list_add(ext2_u32_list bb, __u32 blk)
> > +static int compare32(const void *a, const void *b)
> > +{
> > + __u32 i, j;
> > + i = *(__u32 *)a;
> > + j = *(__u32 *)b;
> > +
> > + return i - j;
> > +}
> > +
> > +static int compare64(const void *a, const void *b)
> > +{
> > + __u64 i, j;
> > + i = *(__u64 *)a;
> > + j = *(__u64 *)b;
> > +
> > + return i - j;
>
> Hmm this does not seem right. What if:
>
> i = 4294967296
> j = 8589934592
>
> then you would return 0 even though the two block numbers differs.
> The problem here is that even though you compare __u64 you return
> int.
Oops. :/
I think Ted would rather not deal with 64bit badblocks, so I think I'm
withdrawing patches 17-19 anyway.
--D
>
> Thanks!
> -Lukas
>
> > +}
> > +
> > +static errcode_t sparse_list_add(struct ext2_sparse_list *bb, void *item)
> > {
> > errcode_t retval;
> > - int i, j;
> > + int i, j, k;
> > unsigned long old_size;
> > + int (*cmp) (const void *a, const void *b);
> >
> > EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST);
> >
> > if (bb->num >= bb->size) {
> > - old_size = bb->size * sizeof(__u32);
> > + old_size = bb->size * bb->item_size;
> > bb->size += 100;
> > - retval = ext2fs_resize_mem(old_size, bb->size * sizeof(__u32),
> > + retval = ext2fs_resize_mem(old_size, bb->size * bb->item_size,
> > &bb->list);
> > if (retval) {
> > bb->size -= 100;
> > return retval;
> > }
> > }
> > -
> > + if (bb->item_size == sizeof(__u32))
> > + cmp = compare32;
> > + else if (bb->item_size == sizeof(__u64))
> > + cmp = compare64;
> > + else
> > + return EXT2_ET_INVALID_ARGUMENT;
> > /*
> > * Add special case code for appending to the end of the list
> > */
> > i = bb->num-1;
> > - if ((bb->num != 0) && (bb->list[i] == blk))
> > + if ((bb->num != 0) && cmp(LIST_ITEM(bb, i), item) == 0)
> > return 0;
> > - if ((bb->num == 0) || (bb->list[i] < blk)) {
> > - bb->list[bb->num++] = blk;
> > + if ((bb->num == 0) || cmp(LIST_ITEM(bb, i), item) < 0) {
> > + memcpy(LIST_ITEM(bb, bb->num++), item, bb->item_size);
> > return 0;
> > }
> >
> > j = bb->num;
> > for (i=0; i < bb->num; i++) {
> > - if (bb->list[i] == blk)
> > + k = cmp(LIST_ITEM(bb, i), item);
> > + if (k == 0)
> > return 0;
> > - if (bb->list[i] > blk) {
> > + if (k > 0) {
>
> Since you're possibly comparing 64bit numbers and return int this
> would not work very well at all.
>
> > j = i;
> > break;
> > }
> > }
> > - for (i=bb->num; i > j; i--)
> > - bb->list[i] = bb->list[i-1];
> > - bb->list[j] = blk;
> > + memmove(LIST_ITEM(bb, i + 1), LIST_ITEM(bb, i),
> > + (bb->num - j) * bb->item_size);
> > + memcpy(LIST_ITEM(bb, j), item, bb->item_size);
>
> What is the difference between j and i here ? I've got the feeling
> that both should be the same ?
>
> Thanks!
> -Lukas
>
> > bb->num++;
> > return 0;
> > }
> >
> > +errcode_t ext2fs_u32_list_add(ext2_u32_list bb, __u32 blk)
> > +{
> > + return sparse_list_add(bb, &blk);
> > +}
> > +
> > +errcode_t ext2fs_badblocks_list_add2(ext2_badblocks_list bb, blk64_t blk)
> > +{
> > + return sparse_list_add(bb, &blk);
> > +}
> > +
> > errcode_t ext2fs_badblocks_list_add(ext2_badblocks_list bb, blk_t blk)
> > {
> > - return ext2fs_u32_list_add((ext2_u32_list) bb, (__u32) blk);
> > + return ext2fs_badblocks_list_add2(bb, blk);
> > }
> >
> > /*
> > * This procedure finds a particular block is on a badblocks
> > * list.
> > */
> > -int ext2fs_u32_list_find(ext2_u32_list bb, __u32 blk)
> > +static int sparse_list_find(struct ext2_sparse_list *bb, void *item)
> > {
> > - int low, high, mid;
> > + int low, high, mid, k;
> > + int (*cmp) (const void *a, const void *b);
> > +
> > + if (bb->item_size == sizeof(__u32))
> > + cmp = compare32;
> > + else if (bb->item_size == sizeof(__u64))
> > + cmp = compare64;
> > + else
> > + return EXT2_ET_INVALID_ARGUMENT;
> >
> > if (bb->magic != EXT2_ET_MAGIC_BADBLOCKS_LIST)
> > return -1;
> > @@ -172,18 +239,19 @@ int ext2fs_u32_list_find(ext2_u32_list bb, __u32 blk)
> >
> > low = 0;
> > high = bb->num-1;
> > - if (blk == bb->list[low])
> > + if (cmp(LIST_ITEM(bb, low), item) == 0)
> > return low;
> > - if (blk == bb->list[high])
> > + if (cmp(LIST_ITEM(bb, high), item) == 0)
> > return high;
> >
> > while (low < high) {
> > mid = ((unsigned)low + (unsigned)high)/2;
> > if (mid == low || mid == high)
> > break;
> > - if (blk == bb->list[mid])
> > + k = cmp(item, LIST_ITEM(bb, mid));
> > + if (k == 0)
> > return mid;
> > - if (blk < bb->list[mid])
> > + if (k < 0)
> > high = mid;
> > else
> > low = mid;
> > @@ -191,13 +259,26 @@ int ext2fs_u32_list_find(ext2_u32_list bb, __u32 blk)
> > return -1;
> > }
> >
> > +int ext2fs_u32_list_find(ext2_u32_list bb, __u32 blk)
> > +{
> > + return sparse_list_find(bb, &blk);
> > +}
> > +
> > /*
> > * This procedure tests to see if a particular block is on a badblocks
> > * list.
> > */
> > int ext2fs_u32_list_test(ext2_u32_list bb, __u32 blk)
> > {
> > - if (ext2fs_u32_list_find(bb, blk) < 0)
> > + if (sparse_list_find(bb, &blk) < 0)
> > + return 0;
> > + else
> > + return 1;
> > +}
> > +
> > +int ext2fs_badblocks_list_test2(ext2_badblocks_list bb, blk64_t blk)
> > +{
> > + if (sparse_list_find(bb, &blk) < 0)
> > return 0;
> > else
> > return 1;
> > @@ -205,65 +286,83 @@ int ext2fs_u32_list_test(ext2_u32_list bb, __u32 blk)
> >
> > int ext2fs_badblocks_list_test(ext2_badblocks_list bb, blk_t blk)
> > {
> > - return ext2fs_u32_list_test((ext2_u32_list) bb, (__u32) blk);
> > + return ext2fs_badblocks_list_test2(bb, blk);
> > }
> >
> >
> > /*
> > * Remove a block from the badblock list
> > */
> > -int ext2fs_u32_list_del(ext2_u32_list bb, __u32 blk)
> > +static int sparse_list_del(struct ext2_sparse_list *bb, void *item)
> > {
> > - int remloc, i;
> > + int remloc;
> >
> > if (bb->num == 0)
> > return -1;
> >
> > - remloc = ext2fs_u32_list_find(bb, blk);
> > + remloc = sparse_list_find(bb, item);
> > if (remloc < 0)
> > return -1;
> >
> > - for (i = remloc ; i < bb->num-1; i++)
> > - bb->list[i] = bb->list[i+1];
> > + memmove(LIST_ITEM(bb, remloc), LIST_ITEM(bb, remloc + 1),
> > + (bb->num - remloc - 1) * bb->item_size);
> > bb->num--;
> > return 0;
> > }
> >
> > +int ext2fs_u32_list_del(ext2_u32_list bb, __u32 blk)
> > +{
> > + return sparse_list_del(bb, &blk);
> > +}
> > +
> > +void ext2fs_badblocks_list_del2(ext2_u32_list bb, blk64_t blk)
> > +{
> > + sparse_list_del(bb, &blk);
> > +}
> > +
> > void ext2fs_badblocks_list_del(ext2_u32_list bb, __u32 blk)
> > {
> > - ext2fs_u32_list_del(bb, blk);
> > + ext2fs_badblocks_list_del(bb, blk);
> > }
> >
> > -errcode_t ext2fs_u32_list_iterate_begin(ext2_u32_list bb,
> > - ext2_u32_iterate *ret)
> > +static errcode_t sparse_list_iterate_begin(struct ext2_sparse_list *bb,
> > + struct ext2_sparse_list_iterate **r)
> > {
> > - ext2_u32_iterate iter;
> > + struct ext2_sparse_list_iterate *iter;
> > errcode_t retval;
> >
> > EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST);
> >
> > - retval = ext2fs_get_mem(sizeof(struct ext2_struct_u32_iterate), &iter);
> > + retval = ext2fs_get_mem(sizeof(struct ext2_sparse_list_iterate),
> > + &iter);
> > if (retval)
> > return retval;
> >
> > iter->magic = EXT2_ET_MAGIC_BADBLOCKS_ITERATE;
> > iter->bb = bb;
> > iter->ptr = 0;
> > - *ret = iter;
> > + *r = iter;
> > return 0;
> > }
> >
> > +errcode_t ext2fs_u32_list_iterate_begin(ext2_u32_list bb,
> > + ext2_u32_iterate *ret)
> > +{
> > + return sparse_list_iterate_begin(bb, ret);
> > +}
> > +
> > errcode_t ext2fs_badblocks_list_iterate_begin(ext2_badblocks_list bb,
> > ext2_badblocks_iterate *ret)
> > {
> > - return ext2fs_u32_list_iterate_begin((ext2_u32_list) bb,
> > - (ext2_u32_iterate *) ret);
> > + return sparse_list_iterate_begin((ext2_u32_list) bb,
> > + (ext2_u32_iterate *) ret);
> > }
> >
> >
> > -int ext2fs_u32_list_iterate(ext2_u32_iterate iter, __u32 *blk)
> > +static int sparse_list_iterate(struct ext2_sparse_list_iterate *iter,
> > + void *item)
> > {
> > - ext2_u32_list bb;
> > + struct ext2_sparse_list *bb;
> >
> > if (iter->magic != EXT2_ET_MAGIC_BADBLOCKS_ITERATE)
> > return 0;
> > @@ -274,21 +373,35 @@ int ext2fs_u32_list_iterate(ext2_u32_iterate iter, __u32 *blk)
> > return 0;
> >
> > if (iter->ptr < bb->num) {
> > - *blk = bb->list[iter->ptr++];
> > + memcpy(item, LIST_ITEM(bb, iter->ptr++), bb->item_size);
> > return 1;
> > }
> > - *blk = 0;
> > + memset(item, 0, bb->item_size);
> > return 0;
> > }
> >
> > +int ext2fs_u32_list_iterate(ext2_u32_iterate iter, __u32 *blk)
> > +{
> > + return sparse_list_iterate(iter, blk);
> > +}
> > +
> > +int ext2fs_badblocks_list_iterate2(ext2_badblocks_iterate iter, blk64_t *blk)
> > +{
> > + return sparse_list_iterate(iter, blk);
> > +}
> > +
> > int ext2fs_badblocks_list_iterate(ext2_badblocks_iterate iter, blk_t *blk)
> > {
> > - return ext2fs_u32_list_iterate((ext2_u32_iterate) iter,
> > - (__u32 *) blk);
> > + blk64_t x;
> > + int ret;
> > +
> > + ret = ext2fs_badblocks_list_iterate2(iter, &x);
> > + *blk = x;
> > + return ret;
> > }
> >
> >
> > -void ext2fs_u32_list_iterate_end(ext2_u32_iterate iter)
> > +static void sparse_list_iterate_end(struct ext2_sparse_list_iterate *iter)
> > {
> > if (!iter || (iter->magic != EXT2_ET_MAGIC_BADBLOCKS_ITERATE))
> > return;
> > @@ -297,13 +410,19 @@ void ext2fs_u32_list_iterate_end(ext2_u32_iterate iter)
> > ext2fs_free_mem(&iter);
> > }
> >
> > +void ext2fs_u32_list_iterate_end(ext2_u32_iterate iter)
> > +{
> > + sparse_list_iterate_end(iter);
> > +}
> > +
> > void ext2fs_badblocks_list_iterate_end(ext2_badblocks_iterate iter)
> > {
> > - ext2fs_u32_list_iterate_end((ext2_u32_iterate) iter);
> > + sparse_list_iterate_end(iter);
> > }
> >
> >
> > -int ext2fs_u32_list_equal(ext2_u32_list bb1, ext2_u32_list bb2)
> > +static int sparse_list_equal(struct ext2_sparse_list *bb1,
> > + struct ext2_sparse_list *bb2)
> > {
> > EXT2_CHECK_MAGIC(bb1, EXT2_ET_MAGIC_BADBLOCKS_LIST);
> > EXT2_CHECK_MAGIC(bb2, EXT2_ET_MAGIC_BADBLOCKS_LIST);
> > @@ -311,18 +430,46 @@ int ext2fs_u32_list_equal(ext2_u32_list bb1, ext2_u32_list bb2)
> > if (bb1->num != bb2->num)
> > return 0;
> >
> > - if (memcmp(bb1->list, bb2->list, bb1->num * sizeof(blk_t)) != 0)
> > + if (bb1->item_size != bb2->item_size)
> > + return 0;
> > +
> > + if (memcmp(bb1->list, bb2->list, bb1->num * bb1->item_size) != 0)
> > return 0;
> > return 1;
> > }
> >
> > +int ext2fs_u32_list_equal(ext2_u32_list bb1, ext2_u32_list bb2)
> > +{
> > + return sparse_list_equal(bb1, bb2);
> > +}
> > +
> > int ext2fs_badblocks_equal(ext2_badblocks_list bb1, ext2_badblocks_list bb2)
> > {
> > - return ext2fs_u32_list_equal((ext2_u32_list) bb1,
> > - (ext2_u32_list) bb2);
> > + return sparse_list_equal(bb1, bb2);
> > }
> >
> > -int ext2fs_u32_list_count(ext2_u32_list bb)
> > +static unsigned int sparse_list_count(struct ext2_sparse_list *bb)
> > {
> > + EXT2_CHECK_MAGIC(bb, EXT2_ET_MAGIC_BADBLOCKS_LIST);
> > return bb->num;
> > }
> > +
> > +int ext2fs_u32_list_count(ext2_u32_list bb)
> > +{
> > + return sparse_list_count(bb);
> > +}
> > +
> > +unsigned int ext2fs_badblocks_count(ext2_badblocks_list bb)
> > +{
> > + return sparse_list_count(bb);
> > +}
> > +
> > +blk64_t ext2fs_badblocks_get(ext2_badblocks_list bb, unsigned int i)
> > +{
> > + blk64_t x;
> > +
> > + if (i < 0 || i >= bb->num)
> > + return 0;
> > + memcpy(&x, LIST_ITEM(bb, i), bb->item_size);
> > + return x;
> > +}
> > diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
> > index d5d8d03..b4ba421 100644
> > --- a/lib/ext2fs/ext2fs.h
> > +++ b/lib/ext2fs/ext2fs.h
> > @@ -111,15 +111,15 @@ typedef struct ext2fs_struct_generic_bitmap *ext2fs_block_bitmap;
> > * Badblocks list definitions
> > */
> >
> > -typedef struct ext2_struct_u32_list *ext2_badblocks_list;
> > -typedef struct ext2_struct_u32_iterate *ext2_badblocks_iterate;
> > +typedef struct ext2_sparse_list *ext2_badblocks_list;
> > +typedef struct ext2_sparse_list_iterate *ext2_badblocks_iterate;
> >
> > -typedef struct ext2_struct_u32_list *ext2_u32_list;
> > -typedef struct ext2_struct_u32_iterate *ext2_u32_iterate;
> > +typedef struct ext2_sparse_list *ext2_u32_list;
> > +typedef struct ext2_sparse_list_iterate *ext2_u32_iterate;
> >
> > /* old */
> > -typedef struct ext2_struct_u32_list *badblocks_list;
> > -typedef struct ext2_struct_u32_iterate *badblocks_iterate;
> > +typedef struct ext2_sparse_list *badblocks_list;
> > +typedef struct ext2_sparse_list_iterate *badblocks_iterate;
> >
> > #define BADBLOCKS_FLAG_DIRTY 1
> >
> > @@ -702,6 +702,8 @@ extern int ext2fs_u32_list_iterate(ext2_u32_iterate iter, blk_t *blk);
> > extern void ext2fs_u32_list_iterate_end(ext2_u32_iterate iter);
> > extern errcode_t ext2fs_u32_copy(ext2_u32_list src, ext2_u32_list *dest);
> > extern int ext2fs_u32_list_equal(ext2_u32_list bb1, ext2_u32_list bb2);
> > +extern int ext2fs_u32_list_del(ext2_u32_list bb, __u32 blk);
> > +extern int ext2fs_u32_list_count(ext2_u32_list bb);
> >
> > extern errcode_t ext2fs_badblocks_list_create(ext2_badblocks_list *ret,
> > int size);
> > @@ -709,7 +711,6 @@ extern errcode_t ext2fs_badblocks_list_add(ext2_badblocks_list bb,
> > blk_t blk);
> > extern int ext2fs_badblocks_list_test(ext2_badblocks_list bb,
> > blk_t blk);
> > -extern int ext2fs_u32_list_del(ext2_u32_list bb, __u32 blk);
> > extern void ext2fs_badblocks_list_del(ext2_u32_list bb, __u32 blk);
> > extern errcode_t
> > ext2fs_badblocks_list_iterate_begin(ext2_badblocks_list bb,
> > @@ -721,7 +722,13 @@ extern errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src,
> > ext2_badblocks_list *dest);
> > extern int ext2fs_badblocks_equal(ext2_badblocks_list bb1,
> > ext2_badblocks_list bb2);
> > -extern int ext2fs_u32_list_count(ext2_u32_list bb);
> > +extern errcode_t ext2fs_badblocks_list_add2(ext2_badblocks_list bb,
> > + blk64_t blk);
> > +extern int ext2fs_badblocks_list_test2(ext2_badblocks_list bb, blk64_t blk);
> > +extern void ext2fs_badblocks_list_del2(ext2_u32_list bb, blk64_t blk);
> > +extern int ext2fs_badblocks_list_iterate2(ext2_badblocks_iterate iter,
> > + blk64_t *blk);
> > +extern blk64_t ext2fs_badblocks_get(ext2_badblocks_list bb, unsigned int i);
> >
> > /* bb_compat */
> > extern errcode_t badblocks_list_create(badblocks_list *ret, int size);
> > diff --git a/lib/ext2fs/ext2fsP.h b/lib/ext2fs/ext2fsP.h
> > index 80d2d0a..592527c 100644
> > --- a/lib/ext2fs/ext2fsP.h
> > +++ b/lib/ext2fs/ext2fsP.h
> > @@ -16,17 +16,18 @@
> > /*
> > * Badblocks list
> > */
> > -struct ext2_struct_u32_list {
> > +struct ext2_sparse_list {
> > int magic;
> > - int num;
> > - int size;
> > - __u32 *list;
> > + unsigned int num;
> > + unsigned int size;
> > + unsigned int item_size;
> > + void *list;
> > int badblocks_flags;
> > };
> >
> > -struct ext2_struct_u32_iterate {
> > +struct ext2_sparse_list_iterate {
> > int magic;
> > - ext2_u32_list bb;
> > + struct ext2_sparse_list *bb;
> > int ptr;
> > };
> >
> > diff --git a/lib/ext2fs/inode.c b/lib/ext2fs/inode.c
> > index 46c1c58..6579512 100644
> > --- a/lib/ext2fs/inode.c
> > +++ b/lib/ext2fs/inode.c
> > @@ -313,8 +313,8 @@ static errcode_t check_for_inode_bad_blocks(ext2_inode_scan scan,
> > * is no longer the case. If we run out of bad blocks, then
> > * we don't need to do any more checking!
> > */
> > - while (blk > bb->list[scan->bad_block_ptr]) {
> > - if (++scan->bad_block_ptr >= bb->num) {
> > + while (blk > ext2fs_badblocks_get(bb, scan->bad_block_ptr)) {
> > + if (++scan->bad_block_ptr >= ext2fs_badblocks_count(bb)) {
> > scan->scan_flags &= ~EXT2_SF_CHK_BADBLOCKS;
> > return 0;
> > }
> > @@ -328,10 +328,10 @@ static errcode_t check_for_inode_bad_blocks(ext2_inode_scan scan,
> > * expense of a huge expense of code complexity, and for an
> > * uncommon case at that.)
> > */
> > - if (blk == bb->list[scan->bad_block_ptr]) {
> > + if (blk == ext2fs_badblocks_get(bb, scan->bad_block_ptr)) {
> > scan->scan_flags |= EXT2_SF_BAD_INODE_BLK;
> > *num_blocks = 1;
> > - if (++scan->bad_block_ptr >= bb->num)
> > + if (++scan->bad_block_ptr >= ext2fs_badblocks_count(bb))
> > scan->scan_flags &= ~EXT2_SF_CHK_BADBLOCKS;
> > return 0;
> > }
> > @@ -342,8 +342,8 @@ static errcode_t check_for_inode_bad_blocks(ext2_inode_scan scan,
> > * don't read in the bad block. (Then the next block to read
> > * will be the bad block, which is handled in the above case.)
> > */
> > - if ((blk + *num_blocks) > bb->list[scan->bad_block_ptr])
> > - *num_blocks = (int) (bb->list[scan->bad_block_ptr] - blk);
> > + if ((blk + *num_blocks) > ext2fs_badblocks_get(bb, scan->bad_block_ptr))
> > + *num_blocks = (int)(ext2fs_badblocks_get(bb, scan->bad_block_ptr) - blk);
> >
> > return 0;
> > }
> >
> > --
> > To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> > the body of a message to majordomo@xxxxxxxxxxxxxxx
> > More majordomo info at http://vger.kernel.org/majordomo-info.html
> >
> --
> To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
