From: "Darrick J. Wong" Subject: [PATCH 17/31] libext2fs: Refactor u32-list to handle 32 and 64-bit data types Date: Mon, 30 Sep 2013 18:28:31 -0700 Message-ID: <20131001012831.28415.54890.stgit@birch.djwong.org> References: <20131001012642.28415.89353.stgit@birch.djwong.org> Mime-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Cc: linux-ext4@vger.kernel.org To: tytso@mit.edu, darrick.wong@oracle.com Return-path: Received: from aserp1040.oracle.com ([141.146.126.69]:22629 "EHLO aserp1040.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755105Ab3JAB2f (ORCPT ); Mon, 30 Sep 2013 21:28:35 -0400 In-Reply-To: <20131001012642.28415.89353.stgit@birch.djwong.org> Sender: linux-ext4-owner@vger.kernel.org List-ID: 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 --- 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(-) diff --git a/lib/ext2fs/badblocks.c b/lib/ext2fs/badblocks.c index 0f23983..4512243 100644 --- a/lib/ext2fs/badblocks.c +++ b/lib/ext2fs/badblocks.c @@ -27,42 +27,58 @@ #include "ext2_fs.h" #include "ext2fsP.h" +static void *LIST_ITEM(struct ext2_sparse_list *bb, unsigned int i) +{ + return bb->list + (i * bb->item_size); +} + /* * Helper function for making a badblocks list */ -static errcode_t make_u32_list(int size, int num, __u32 *list, - ext2_u32_list *ret) +static errcode_t sparse_list_make(unsigned int size, unsigned int num, + unsigned int item_size, + struct ext2_sparse_list *list, + struct ext2_sparse_list **ret) { - ext2_u32_list bb; + struct ext2_sparse_list *bb; errcode_t retval; - retval = ext2fs_get_mem(sizeof(struct ext2_struct_u32_list), &bb); + if (list && (list->magic != EXT2_ET_MAGIC_BADBLOCKS_LIST || + list->item_size != item_size)) { + return EXT2_ET_INVALID_ARGUMENT; + } + + /* For now we only support 32 and 64bit unsigned */ + if (item_size != sizeof(__u32) && item_size != sizeof(__u64)) + return EXT2_ET_INVALID_ARGUMENT; + + retval = ext2fs_get_mem(sizeof(struct ext2_sparse_list), &bb); if (retval) return retval; - memset(bb, 0, sizeof(struct ext2_struct_u32_list)); + memset(bb, 0, sizeof(struct ext2_sparse_list)); bb->magic = EXT2_ET_MAGIC_BADBLOCKS_LIST; bb->size = size ? size : 10; bb->num = num; - retval = ext2fs_get_array(bb->size, sizeof(blk_t), &bb->list); + bb->item_size = item_size; + retval = ext2fs_get_array(bb->size, bb->item_size, &bb->list); if (retval) { ext2fs_free_mem(&bb); return retval; } if (list) - memcpy(bb->list, list, bb->size * sizeof(blk_t)); + memcpy(bb->list, list->list, bb->size * bb->item_size); else - memset(bb->list, 0, bb->size * sizeof(blk_t)); + memset(bb->list, 0, bb->size * bb->item_size); *ret = bb; return 0; } - /* * This procedure creates an empty u32 list. */ errcode_t ext2fs_u32_list_create(ext2_u32_list *ret, int size) { - return make_u32_list(size, 0, 0, ret); + return sparse_list_make(size, 0, sizeof(__u32), NULL, ret); } /* @@ -70,28 +86,36 @@ errcode_t ext2fs_u32_list_create(ext2_u32_list *ret, int size) */ errcode_t ext2fs_badblocks_list_create(ext2_badblocks_list *ret, int size) { - return make_u32_list(size, 0, 0, (ext2_badblocks_list *) ret); + return sparse_list_make(size, 0, sizeof(blk64_t), NULL, + (ext2_badblocks_list *) ret); } /* * This procedure copies a badblocks list */ -errcode_t ext2fs_u32_copy(ext2_u32_list src, ext2_u32_list *dest) +static errcode_t sparse_list_copy(struct ext2_sparse_list *src, + struct ext2_sparse_list **dest) { errcode_t retval; - retval = make_u32_list(src->size, src->num, src->list, dest); + retval = sparse_list_make(src->size, src->num, src->item_size, src, + dest); if (retval) return retval; (*dest)->badblocks_flags = src->badblocks_flags; return 0; } +errcode_t ext2fs_u32_copy(ext2_u32_list src, ext2_u32_list *dest) +{ + return sparse_list_copy(src, dest); +} + errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src, ext2_badblocks_list *dest) { - return ext2fs_u32_copy((ext2_u32_list) src, + return sparse_list_copy((ext2_u32_list) src, (ext2_u32_list *) dest); } @@ -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; +} + +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) { 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); 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; }