1 From 2af141bda3cd407abd4bedf615f9e45fe79518e2 Mon Sep 17 00:00:00 2001
2 From: Florian Weimer <fweimer@redhat.com>
3 Date: Thu, 10 Aug 2023 19:36:56 +0200
4 Subject: [PATCH 08/44] malloc: Remove bin scanning from memalign (bug 30723)
6 On the test workload (mpv --cache=yes with VP9 video decoding), the
7 bin scanning has a very poor success rate (less than 2%). The tcache
8 scanning has about 50% success rate, so keep that.
10 Update comments in malloc/tst-memalign-2 to indicate the purpose
11 of the tests. Even with the scanning removed, the additional
12 merging opportunities since commit 542b1105852568c3ebc712225ae78b
13 ("malloc: Enable merging of remainders in memalign (bug 30723)")
14 are sufficient to pass the existing large bins test.
16 Remove leftover variables from _int_free from refactoring in the
19 Reviewed-by: DJ Delorie <dj@redhat.com>
20 (cherry picked from commit 0dc7fc1cf094406a138e4d1bcf9553e59edcf89d)
23 malloc/malloc.c | 169 ++--------------------------------------
24 malloc/tst-memalign-2.c | 7 +-
25 3 files changed, 11 insertions(+), 166 deletions(-)
27 diff --git a/NEWS b/NEWS
28 index 872bc8907b..c339cb444e 100644
31 @@ -132,6 +132,7 @@ The following bugs are resolved with this release:
32 [30555] string: strerror can incorrectly return NULL
33 [30579] malloc: trim_threshold in realloc lead to high memory usage
34 [30662] nscd: Group and password cache use errno in place of errval
35 + [30723] posix_memalign repeatedly scans long bin lists
39 diff --git a/malloc/malloc.c b/malloc/malloc.c
40 index 948f9759af..d0bbbf3710 100644
43 @@ -4488,12 +4488,6 @@ _int_free (mstate av, mchunkptr p, int have_lock)
45 INTERNAL_SIZE_T size; /* its size */
46 mfastbinptr *fb; /* associated fastbin */
47 - mchunkptr nextchunk; /* next contiguous chunk */
48 - INTERNAL_SIZE_T nextsize; /* its size */
49 - int nextinuse; /* true if nextchunk is used */
50 - INTERNAL_SIZE_T prevsize; /* size of previous contiguous chunk */
51 - mchunkptr bck; /* misc temp for linking */
52 - mchunkptr fwd; /* misc temp for linking */
56 @@ -5032,42 +5026,6 @@ _int_realloc (mstate av, mchunkptr oldp, INTERNAL_SIZE_T oldsize,
57 ------------------------------ memalign ------------------------------
60 -/* Returns 0 if the chunk is not and does not contain the requested
61 - aligned sub-chunk, else returns the amount of "waste" from
62 - trimming. NB is the *chunk* byte size, not the user byte
65 -chunk_ok_for_memalign (mchunkptr p, size_t alignment, size_t nb)
67 - void *m = chunk2mem (p);
68 - INTERNAL_SIZE_T size = chunksize (p);
69 - void *aligned_m = m;
71 - if (__glibc_unlikely (misaligned_chunk (p)))
72 - malloc_printerr ("_int_memalign(): unaligned chunk detected");
74 - aligned_m = PTR_ALIGN_UP (m, alignment);
76 - INTERNAL_SIZE_T front_extra = (intptr_t) aligned_m - (intptr_t) m;
78 - /* We can't trim off the front as it's too small. */
79 - if (front_extra > 0 && front_extra < MINSIZE)
82 - /* If it's a perfect fit, it's an exception to the return value rule
83 - (we would return zero waste, which looks like "not usable"), so
84 - handle it here by returning a small non-zero value instead. */
85 - if (size == nb && front_extra == 0)
88 - /* If the block we need fits in the chunk, calculate total waste. */
89 - if (size > nb + front_extra)
92 - /* Can't use this chunk. */
96 /* BYTES is user requested bytes, not requested chunksize bytes. */
98 _int_memalign (mstate av, size_t alignment, size_t bytes)
99 @@ -5082,7 +5040,6 @@ _int_memalign (mstate av, size_t alignment, size_t bytes)
100 mchunkptr remainder; /* spare room at end to split off */
101 unsigned long remainder_size; /* its size */
102 INTERNAL_SIZE_T size;
105 nb = checked_request2size (bytes);
107 @@ -5101,129 +5058,13 @@ _int_memalign (mstate av, size_t alignment, size_t bytes)
108 we don't find anything in those bins, the common malloc code will
109 scan starting at 2x. */
111 - /* This will be set if we found a candidate chunk. */
114 - /* Fast bins are singly-linked, hard to remove a chunk from the middle
115 - and unlikely to meet our alignment requirements. We have not done
116 - any experimentation with searching for aligned fastbins. */
120 - int first_bin_index;
121 - int first_largebin_index;
122 - int last_bin_index;
124 - if (in_smallbin_range (nb))
125 - first_bin_index = smallbin_index (nb);
127 - first_bin_index = largebin_index (nb);
129 - if (in_smallbin_range (nb * 2))
130 - last_bin_index = smallbin_index (nb * 2);
132 - last_bin_index = largebin_index (nb * 2);
134 - first_largebin_index = largebin_index (MIN_LARGE_SIZE);
136 - int victim_index; /* its bin index */
138 - for (victim_index = first_bin_index;
139 - victim_index < last_bin_index;
144 - if (victim_index < first_largebin_index)
146 - /* Check small bins. Small bin chunks are doubly-linked despite
147 - being the same size. */
149 - mchunkptr fwd; /* misc temp for linking */
150 - mchunkptr bck; /* misc temp for linking */
152 - bck = bin_at (av, victim_index);
156 - if (chunk_ok_for_memalign (fwd, alignment, nb) > 0)
161 - victim->fd->bk = victim->bk;
162 - victim->bk->fd = victim->fd;
171 - /* Check large bins. */
172 - mchunkptr fwd; /* misc temp for linking */
173 - mchunkptr bck; /* misc temp for linking */
174 - mchunkptr best = NULL;
175 - size_t best_size = 0;
177 - bck = bin_at (av, victim_index);
179 + /* Call malloc with worst case padding to hit alignment. */
180 + m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
186 - if (chunksize (fwd) < nb)
188 - extra = chunk_ok_for_memalign (fwd, alignment, nb);
190 - && (extra <= best_size || best == NULL))
196 + return 0; /* propagate failure */
202 - if (victim != NULL)
204 - unlink_chunk (av, victim);
209 - if (victim != NULL)
214 - /* Strategy: find a spot within that chunk that meets the alignment
215 - request, and then possibly free the leading and trailing space.
216 - This strategy is incredibly costly and can lead to external
217 - fragmentation if header and footer chunks are unused. */
219 - if (victim != NULL)
224 - if (av != &main_arena)
225 - set_non_main_arena (p);
229 - /* Call malloc with worst case padding to hit alignment. */
231 - m = (char *) (_int_malloc (av, nb + alignment + MINSIZE));
234 - return 0; /* propagate failure */
240 if ((((unsigned long) (m)) % alignment) != 0) /* misaligned */
242 diff --git a/malloc/tst-memalign-2.c b/malloc/tst-memalign-2.c
243 index f229283dbf..ecd6fa249e 100644
244 --- a/malloc/tst-memalign-2.c
245 +++ b/malloc/tst-memalign-2.c
246 @@ -86,7 +86,8 @@ do_test (void)
247 TEST_VERIFY (tcache_allocs[i].ptr1 == tcache_allocs[i].ptr2);
250 - /* Test for non-head tcache hits. */
251 + /* Test for non-head tcache hits. This exercises the memalign
252 + scanning code to find matching allocations. */
253 for (i = 0; i < array_length (ptr); ++ i)
256 @@ -113,7 +114,9 @@ do_test (void)
258 TEST_VERIFY (count > 0);
260 - /* Large bins test. */
261 + /* Large bins test. This verifies that the over-allocated parts
262 + that memalign releases for future allocations can be reused by
263 + memalign itself at least in some cases. */
265 for (i = 0; i < LN; ++ i)