On Tue, Mar 30, 2021 at 10:25:31PM +0800, Gao Xiang wrote:
> From: Dave Chinner <dchinner@xxxxxxxxxx>
>
> phase 6 on large directories is cpu bound on duplicate name checking
> due to the algorithm having effectively O(n^2) scalability. Hence
> when the duplicate name hash table size is far smaller than the
> number of directory entries, we end up with long hash chains that
> are searched linearly on every new entry that is found in the
> directory to do duplicate detection.
>
> The in-memory hash table size is limited to 64k entries. Hence when
> we have millions of entries in a directory, duplicate entry lookups
> on the hash table have substantial overhead. Scale this table out to
> larger sizes so that we keep the chain lengths short and hence the
> O(n^2) scalability impact is limited because N is always small.
>
> For a 10M entry directory consuming 400MB of directory data, the
> hash table now sizes at 6.4 million entries instead of ~64k - it is
> ~100x larger. While the hash table now consumes ~50MB of RAM, the
> xfs_repair footprint barely changes as it's using already consuming
> ~9GB of RAM at this point in time. IOWs, the incremental memory
> usage change is noise, but the directory checking time:
>
> Unpatched:
>
> 97.11% xfs_repair [.] dir_hash_add
> 0.38% xfs_repair [.] longform_dir2_entry_check_data
> 0.34% libc-2.31.so [.] __libc_calloc
> 0.32% xfs_repair [.] avl_ino_start
>
> Phase 6: 10/22 12:11:40 10/22 12:14:28 2 minutes, 48 seconds
>
> Patched:
>
> 46.74% xfs_repair [.] radix_tree_lookup
> 32.13% xfs_repair [.] dir_hash_see_all
> 7.70% xfs_repair [.] radix_tree_tag_get
> 3.92% xfs_repair [.] dir_hash_add
> 3.52% xfs_repair [.] radix_tree_tag_clear
> 2.43% xfs_repair [.] crc32c_le
>
> Phase 6: 10/22 13:11:01 10/22 13:11:18 17 seconds
>
> has been reduced by an order of magnitude.
>
> Signed-off-by: Dave Chinner <dchinner@xxxxxxxxxx>
> Signed-off-by: Gao Xiang <hsiangkao@xxxxxxxxxx>
> ---
> repair/phase6.c | 30 ++++++++++++++++++++++++------
> 1 file changed, 24 insertions(+), 6 deletions(-)
>
> diff --git a/repair/phase6.c b/repair/phase6.c
> index 063329636500..aa991bf76da6 100644
> --- a/repair/phase6.c
> +++ b/repair/phase6.c
> @@ -288,19 +288,37 @@ dir_hash_done(
> free(hashtab);
> }
>
> +/*
> + * Create a directory hash index structure based on the size of the directory we
> + * are about to try to repair. The size passed in is the size of the data
> + * segment of the directory in bytes, so we don't really know exactly how many
> + * entries are in it. Hence assume an entry size of around 64 bytes - that's a
> + * name length of 40+ bytes so should cover a most situations with large
> + * really directories.
"...with really large directories."
> + */
> static struct dir_hash_tab *
> dir_hash_init(
> xfs_fsize_t size)
> {
> - struct dir_hash_tab *hashtab;
> + struct dir_hash_tab *hashtab = NULL;
> int hsize;
>
> - hsize = size / (16 * 4);
> - if (hsize > 65536)
> - hsize = 63336;
> - else if (hsize < 16)
> + hsize = size / 64;
> + if (hsize < 16)
> hsize = 16;
> - if ((hashtab = calloc(DIR_HASH_TAB_SIZE(hsize), 1)) == NULL)
> +
> + /*
> + * Try to allocate as large a hash table as possible. Failure to
> + * allocate isn't fatal, it will just result in slower performance as we
> + * reduce the size of the table.
> + */
> + while (hsize >= 16) {
> + hashtab = calloc(DIR_HASH_TAB_SIZE(hsize), 1);
> + if (hashtab)
> + break;
> + hsize /= 2;
> + }
I still kinda wonder if the hash size ought to be some prime number,
though I suppose /finding/ a prime number isn't necessarily easy.
Hm, let's assume you had the maximal 32GB directory.
size = 34359738368
hsize = size/64 = 536870912
DIR_HASH_TAB_SIZE(hsize) =
(sizeof(dir_hash_tab_t) + (sizeof(dir_hash_ent_t *) * (hsize) * 2))
== 40 + (8 * 536870912 * 2) == 8589934632
That's ... kind of big? I guess the saving grace is that we halve hsize
if calloc fails and the address space isn't populated with memory pages
until we actually use them. It might turn out that users want a lower
cap than 8GB per 32GB directory, but I suppose we won't find /that/ out
until we try...
With the comment fixed,
Reviewed-by: Darrick J. Wong <djwong@xxxxxxxxxx>
--D
> + if (!hashtab)
> do_error(_("calloc failed in dir_hash_init\n"));
> hashtab->size = hsize;
> hashtab->byhash = (struct dir_hash_ent **)((char *)hashtab +
> --
> 2.20.1
>
