Re: [PATCH v3 1/8] repair: turn bad inode list into array

["Darrick J. Wong" <djwong@kernel.org>]

On Tue, Mar 30, 2021 at 10:25:24PM +0800, Gao Xiang wrote:
> From: Gao Xiang <hsiangkao@redhat.com>
> 
> 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.

> Signed-off-by: Gao Xiang <hsiangkao@redhat.com>
> ---
>  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

> +	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
>