| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Thu, 10 Oct 2013 16:46:23 +0200 (CEST)
From: Lukáš Czerner <lczerner@...hat.com>
To: "Darrick J. Wong" <darrick.wong@...cle.com>
cc: tytso@....edu, linux-ext4@...r.kernel.org
Subject: Re: [PATCH 17/31] libext2fs: Refactor u32-list to handle 32 and
64-bit data types
On Mon, 30 Sep 2013, Darrick J. Wong wrote:
> Date: Mon, 30 Sep 2013 18:28:31 -0700
> From: Darrick J. Wong <darrick.wong@...cle.com>
> To: tytso@....edu, darrick.wong@...cle.com
> Cc: linux-ext4@...r.kernel.org
> 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@...cle.com>
> ---
> 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.
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@...r.kernel.org
> 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@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists