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.

Update comments in malloc/tst-memalign-2 to indicate the purpose
of the tests.  Even with the scanning removed, the additional
merging opportunities since commit 542b1105852568c3ebc712225ae78b
("malloc: Enable merging of remainders in memalign (bug 30723)")
are sufficient to pass the existing large bins test.

Remove leftover variables from _int_free from refactoring in the
same commit.

Reviewed-by: DJ Delorie <dj@redhat.com>

Previously, calling _int_free from _int_memalign could put remainders
into the tcache or into fastbins, where they are invisible to the
low-level allocator.  This results in missed merge opportunities
because once these freed chunks become available to the low-level
allocator, further memalign allocations (even of the same size are)
likely obstructing merges.

Furthermore, during forwards merging in _int_memalign, do not
completely give up when the remainder is too small to serve as a
chunk on its own.  We can still give it back if it can be merged
with the following unused chunk.  This makes it more likely that
memalign calls in a loop achieve a compact memory layout,
independently of initial heap layout.

Drop some useless (unsigned long) casts along the way, and tweak
the style to more closely match GNU on changed lines.

Reviewed-by: DJ Delorie <dj@redhat.com>

The trim_threshold is too aggressive a heuristic to decide if chunk
reuse is OK for reallocated memory; for repeated small, shrinking
allocations it leads to internal fragmentation and for repeated larger
allocations that fragmentation may blow up even worse due to the dynamic
nature of the threshold.

Limit reuse only when it is within the alignment padding, which is 2 *
size_t for heap allocations and a page size for mmapped allocations.
There's the added wrinkle of THP, but this fix ignores it for now,
pessimizing that case in favor of keeping fragmentation low.

This resolves BZ #30579.

Signed-off-by: Siddhesh Poyarekar <siddhesh@sourceware.org>
Reported-by: Nicolas Dusart <nicolas@freedelity.be>
Reported-by: Aurelien Jarno <aurelien@aurel32.net>
Reviewed-by: Aurelien Jarno <aurelien@aurel32.net>
Tested-by: Aurelien Jarno <aurelien@aurel32.net>

This patch adds the strict checking for power-of-two alignments
in aligned_alloc(), and updates the manual accordingly.

Reviewed-by: Carlos O'Donell <carlos@redhat.com>

Based on these comments in malloc.c:

   size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
   from a non-main arena.  This is only set immediately before handing
   the chunk to the user, if necessary.

   The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
   does not have to be taken into account in size comparisons.

When we pull a chunk off the unsorted list (or any list) we need to
make sure that flag is set properly before returning the chunk.

Use the rounded-up size for chunk_ok_for_memalign()

Do not scan the arena for reusable chunks if there's no arena.

Account for chunk overhead when determining if a chunk is a reuse
candidate.

mcheck interferes with memalign, so skip mcheck variants of
memalign tests.

Reviewed-by: Carlos O'Donell <carlos@redhat.com>
Tested-by: Carlos O'Donell <carlos@redhat.com>

This patch adds a chunk scanning algorithm to the _int_memalign code
path that reduces heap fragmentation by reusing already aligned chunks
instead of always looking for chunks of larger sizes and splitting
them.  The tcache macros are extended to allow removing a chunk from
the middle of the list.

The goal is to fix the pathological use cases where heaps grow
continuously in workloads that are heavy users of memalign.

Note that tst-memalign-2 checks for tcache operation, which
malloc-check bypasses.

Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

And make always supported.  The configure option was added on glibc 2.25
and some features require it (such as hwcap mask, huge pages support, and
lock elisition tuning).  It also simplifies the build permutations.

Changes from v1:
 * Remove glibc.rtld.dynamic_sort changes, it is orthogonal and needs
   more discussion.
 * Cleanup more code.
Reviewed-by: Siddhesh Poyarekar <siddhesh@sourceware.org>

git commit 0849eed45daa ("malloc: Move MORECORE fallback mmap to
sysmalloc_mmap_fallback") moved a block of code from sysmalloc to a
new helper function sysmalloc_mmap_fallback(), but 'pagesize' is used
for the 'minsize' argument and 'MMAP_AS_MORECORE_SIZE' for the
'pagesize' argument.

Fixes: 0849eed45daa ("malloc: Move MORECORE fallback mmap to sysmalloc_mmap_fallback")
Signed-off-by: Robert Morell <rmorell@nvidia.com>
Reviewed-by: Adhemerval Zanella  <adhemerval.zanella@linaro.org>

* malloc/malloc.c (_int_malloc): remove redundant check of
  unsorted bin corruption

With commit "b90ddd08f6dd688e651df9ee89ca3a69ff88cd0c"
(malloc: Additional checks for unsorted bin integrity),
same check of (bck->fd != victim) is added before checking of unsorted
chunk corruption, which was added in "bdc3009b8ff0effdbbfb05eb6b10966753cbf9b8"
(Added check before removing from unsorted list).

..
3773           if (__glibc_unlikely (bck->fd != victim)
3774               || __glibc_unlikely (victim->fd != unsorted_chunks (av)))
3775             malloc_printerr ("malloc(): unsorted double linked list corrupted");
..
..
3815           /* remove from unsorted list */
3816          if (__glibc_unlikely (bck->fd != victim))
3817            malloc_printerr ("malloc(): corrupted unsorted chunks 3");
3818          unsorted_chunks (av)->bk = bck;
..

So this extra check can be removed.

Signed-off-by: Maninder Singh <maninder1.s@samsung.com>
Signed-off-by: Ayush Mittal <ayush.m@samsung.com>
Reviewed-by: DJ Delorie <dj@redhat.com>