Re: [PATCH v3 1/8] repair: turn bad inode list into array
From: "Darrick J. Wong" <djwong@kernel.org>
Date: 2021-03-30 18:47:09
On Tue, Mar 30, 2021 at 10:25:24PM +0800, Gao Xiang wrote:
From: Gao Xiang <redacted> Just use array and reallocate one-by-one here (not sure if bulk allocation is more effective or not.)
I'm not sure either. The list of bad directories is likely to be sparse, so perhaps the libfrog bitmap isn't going to beat a realloc array for space efficiency... and reusing the slab array might be overkill for an array-backed bitmap? Eh, you know what? I don't think the bad directory bitmap is hot enough to justify broadening this into an algorithmic review of data structures. Incremental space efficiency is good enough for me.
quoted hunk ↗ jump to hunk
Signed-off-by: Gao Xiang <redacted> --- repair/dir2.c | 34 +++++++++++++++++----------------- repair/dir2.h | 2 +- 2 files changed, 18 insertions(+), 18 deletions(-)diff --git a/repair/dir2.c b/repair/dir2.c index eabdb4f2d497..b6a8a5c40ae4 100644 --- a/repair/dir2.c +++ b/repair/dir2.c@@ -20,40 +20,40 @@ * Known bad inode list. These are seen when the leaf and node * block linkages are incorrect. */ -typedef struct dir2_bad { - xfs_ino_t ino; - struct dir2_bad *next; -} dir2_bad_t; +struct dir2_bad { + unsigned int nr;
We could have more than 4 billion bad directories.
+ xfs_ino_t *itab;
+};
-static dir2_bad_t *dir2_bad_list;
+static struct dir2_bad dir2_bad;
static void
dir2_add_badlist(
xfs_ino_t ino)
{
- dir2_bad_t *l;
+ xfs_ino_t *itab;
- if ((l = malloc(sizeof(dir2_bad_t))) == NULL) {
+ itab = realloc(dir2_bad.itab, (dir2_bad.nr + 1) * sizeof(xfs_ino_t));Minor quibble: you could improve the efficiency of this by tracking both the array size and fill count so that you only have to expand the array by powers of two at a time. The glibc heap is faster than it once was, but you could help it along by only asking for memory in MMAP_THRESHOLD chunks. Or possibly even pagesize chunks. --D
quoted hunk ↗ jump to hunk
+ if (!itab) { do_error( _("malloc failed (%zu bytes) dir2_add_badlist:ino %" PRIu64 "\n"), - sizeof(dir2_bad_t), ino); + sizeof(xfs_ino_t), ino); exit(1); } - l->next = dir2_bad_list; - dir2_bad_list = l; - l->ino = ino; + itab[dir2_bad.nr++] = ino; + dir2_bad.itab = itab; } -int +bool dir2_is_badino( xfs_ino_t ino) { - dir2_bad_t *l; + unsigned int i; - for (l = dir2_bad_list; l; l = l->next) - if (l->ino == ino) - return 1; - return 0; + for (i = 0; i < dir2_bad.nr; ++i) + if (dir2_bad.itab[i] == ino) + return true; + return false; } /*diff --git a/repair/dir2.h b/repair/dir2.h index 5795aac5eaab..af4cfb1da329 100644 --- a/repair/dir2.h +++ b/repair/dir2.h@@ -27,7 +27,7 @@ process_sf_dir2_fixi8( struct xfs_dir2_sf_hdr *sfp, xfs_dir2_sf_entry_t **next_sfep); -int +bool dir2_is_badino( xfs_ino_t ino);-- 2.20.1