From: Maxim Kuvyrkov <maxim.kuvyrkov@linaro.org>
To: Florian Weimer <fweimer@redhat.com>
Cc: Libc-alpha <libc-alpha@sourceware.org>,
DJ Delorie <dj@redhat.com>,
Christophe Lyon <christophe.lyon@linaro.org>
Subject: Re: [PATCH] malloc: Remove bin scanning from memalign (bug 30723)
Date: Fri, 11 Aug 2023 12:54:33 +0400 [thread overview]
Message-ID: <1E6B680E-A3C7-4647-BBB2-4B68D1796817@linaro.org> (raw)
In-Reply-To: <87pm3uajev.fsf@oldenburg.str.redhat.com>
Hi Florian,
This fails testing on aarch64-linux-gnu:
FAIL: malloc/tst-memalign-2-malloc-hugetlb1
original exit status 1
error: tst-memalign-2.c:155: not true: count > LN / 2
error: 1 test failures
FAIL: malloc/tst-memalign-2-malloc-hugetlb2
original exit status 1
error: tst-memalign-2.c:155: not true: count > LN / 2
error: 1 test failures
FAIL: malloc/tst-memalign-2
original exit status 1
error: tst-memalign-2.c:155: not true: count > LN / 2
error: 1 test failures
Let me know if you need any assistance in reproducing this.
Thanks!
--
Maxim Kuvyrkov
https://www.linaro.org
> On Aug 10, 2023, at 21:36, Florian Weimer via Libc-alpha <libc-alpha@sourceware.org> wrote:
>
> On the test workload (mpv --cache=yes with VP9 video decoding), the
> bin scanning has a very poor success rate (less than 2%). The tcache
> scanning has about 50% success rate, so keep that.
>
> ---
> DJ, this is on top of my other patch. Given that the chunk scanning
> code has such a small hit rate on the workload, I have just removed it.
>
> I think we need better data structures before we can bring this back,
> otherwise most workloads with a high number of memalign calls suffer too
> much. Typical heaps have hundreds, if not thousands, of free list
> entries. I had not considered the impact of that on repeated memalign
> calls.
>
> What do you think?
>
> Tested x86_64-linux-gnu.
>
> Thanks,
> Florian
>
> malloc/malloc.c | 127 +++-----------------------------------------------------
> 1 file changed, 5 insertions(+), 122 deletions(-)
>
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 948f9759af..9c2cab7a59 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -5082,7 +5082,6 @@ _int_memalign (mstate av, size_t alignment, size_t bytes)
> mchunkptr remainder; /* spare room at end to split off */
> unsigned long remainder_size; /* its size */
> INTERNAL_SIZE_T size;
> - mchunkptr victim;
>
> nb = checked_request2size (bytes);
> if (nb == 0)
> @@ -5101,129 +5100,13 @@ _int_memalign (mstate av, size_t alignment, size_t bytes)
> we don't find anything in those bins, the common malloc code will
> scan starting at 2x. */
>
> - /* This will be set if we found a candidate chunk. */
> - victim = NULL;
> + /* Call malloc with worst case padding to hit alignment. */
> + m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
>
> - /* Fast bins are singly-linked, hard to remove a chunk from the middle
> - and unlikely to meet our alignment requirements. We have not done
> - any experimentation with searching for aligned fastbins. */
> + if (m == 0)
> + return 0; /* propagate failure */
>
> - if (av != NULL)
> - {
> - int first_bin_index;
> - int first_largebin_index;
> - int last_bin_index;
> -
> - if (in_smallbin_range (nb))
> - first_bin_index = smallbin_index (nb);
> - else
> - first_bin_index = largebin_index (nb);
> -
> - if (in_smallbin_range (nb * 2))
> - last_bin_index = smallbin_index (nb * 2);
> - else
> - last_bin_index = largebin_index (nb * 2);
> -
> - first_largebin_index = largebin_index (MIN_LARGE_SIZE);
> -
> - int victim_index; /* its bin index */
> -
> - for (victim_index = first_bin_index;
> - victim_index < last_bin_index;
> - victim_index ++)
> - {
> - victim = NULL;
> -
> - if (victim_index < first_largebin_index)
> - {
> - /* Check small bins. Small bin chunks are doubly-linked despite
> - being the same size. */
> -
> - mchunkptr fwd; /* misc temp for linking */
> - mchunkptr bck; /* misc temp for linking */
> -
> - bck = bin_at (av, victim_index);
> - fwd = bck->fd;
> - while (fwd != bck)
> - {
> - if (chunk_ok_for_memalign (fwd, alignment, nb) > 0)
> - {
> - victim = fwd;
> -
> - /* Unlink it */
> - victim->fd->bk = victim->bk;
> - victim->bk->fd = victim->fd;
> - break;
> - }
> -
> - fwd = fwd->fd;
> - }
> - }
> - else
> - {
> - /* Check large bins. */
> - mchunkptr fwd; /* misc temp for linking */
> - mchunkptr bck; /* misc temp for linking */
> - mchunkptr best = NULL;
> - size_t best_size = 0;
> -
> - bck = bin_at (av, victim_index);
> - fwd = bck->fd;
> -
> - while (fwd != bck)
> - {
> - int extra;
> -
> - if (chunksize (fwd) < nb)
> - break;
> - extra = chunk_ok_for_memalign (fwd, alignment, nb);
> - if (extra > 0
> - && (extra <= best_size || best == NULL))
> - {
> - best = fwd;
> - best_size = extra;
> - }
> -
> - fwd = fwd->fd;
> - }
> - victim = best;
> -
> - if (victim != NULL)
> - {
> - unlink_chunk (av, victim);
> - break;
> - }
> - }
> -
> - if (victim != NULL)
> - break;
> - }
> - }
> -
> - /* Strategy: find a spot within that chunk that meets the alignment
> - request, and then possibly free the leading and trailing space.
> - This strategy is incredibly costly and can lead to external
> - fragmentation if header and footer chunks are unused. */
> -
> - if (victim != NULL)
> - {
> - p = victim;
> - m = chunk2mem (p);
> - set_inuse (p);
> - if (av != &main_arena)
> - set_non_main_arena (p);
> - }
> - else
> - {
> - /* Call malloc with worst case padding to hit alignment. */
> -
> - m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
> -
> - if (m == 0)
> - return 0; /* propagate failure */
> -
> - p = mem2chunk (m);
> - }
> + p = mem2chunk (m);
>
> if ((((unsigned long) (m)) % alignment) != 0) /* misaligned */
> {
>
> base-commit: e02ce52fd890d3b5197f78cf25096faa9446fa3d
>
next prev parent reply other threads:[~2023-08-11 8:54 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-08-10 17:36 Florian Weimer
2023-08-10 18:04 ` DJ Delorie
2023-08-11 7:20 ` Florian Weimer
2023-08-11 23:14 ` DJ Delorie
2023-08-21 14:01 ` Sam James
2023-08-21 14:45 ` Florian Weimer
2023-08-11 8:54 ` Maxim Kuvyrkov [this message]
2023-08-11 9:14 ` Florian Weimer
2023-08-11 14:52 ` Florian Weimer
2023-08-12 6:52 ` Andreas Schwab
2023-08-12 13:23 ` Florian Weimer
2023-08-12 13:33 ` Florian Weimer
2023-08-12 14:50 ` Andreas Schwab
2023-08-14 2:14 ` Xi Ruoyao
2023-08-14 9:16 ` Florian Weimer
2023-08-15 11:58 ` Adhemerval Zanella Netto
2023-08-14 9:42 Florian Weimer
2023-08-14 20:49 ` DJ Delorie
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1E6B680E-A3C7-4647-BBB2-4B68D1796817@linaro.org \
--to=maxim.kuvyrkov@linaro.org \
--cc=christophe.lyon@linaro.org \
--cc=dj@redhat.com \
--cc=fweimer@redhat.com \
--cc=libc-alpha@sourceware.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).