Re: [PATCH v6 1/1] memalign: Support scanning for aligned chunks.

[Carlos O'Donell <carlos@redhat.com>]

On 4/12/23 21:52, DJ Delorie via Libc-alpha wrote:
> Xi Ruoyao <xry111@xry111.site> writes:
>> Then we test ar_ptr != NULL in the if statement.
> 
> I haven't reproduce the tcache fail (it might be unrelated) but this
> should fix the ar_ptr case (most of the malloc.c patch just indents a
> bunch of code, to make it conditional).  We don't want to just fail on
> ar_ptr==NULL because that prevents us from calling sysmalloc() to get
> more plain heap.

DJ and I sat down to review v6 in detail.

We need a v7 for three reasons:

(a) chunk_ok_for_memalign() is commented as taking *user* bytes but you pass
    chunksize in this change and the comment needs adjusting. You might as
    well change `size_t bytes` to `size_t nb` to be consistent.

(b) If we are now passing chunksize then the second line of the function which
    computes size, should use, not memsize(p), but chunksize(p), to correctly
    account for the header bytes (otherwise we're conservative).

(c) We need to exclude the test from mcheck runs via tests-exclude-mcheck since
    the expected chunk results won't work when mcheck is in effect.

	FAIL: malloc/tst-memalign-2-mcheck
	FAIL: malloc/tst-memalign-3-mcheck

> From 250e31ff15d92d20e6c66689e34baeab8daa034d Mon Sep 17 00:00:00 2001
> From: DJ Delorie <dj@redhat.com>
> Date: Mon, 3 Apr 2023 17:33:03 -0400
> Subject: malloc: set NON_MAIN_ARENA flag for reclaimed memalign chunk (BZ
>  #30101)
> 
> 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.
> 
> diff --git a/malloc/Makefile b/malloc/Makefile
> index f49675845e..e66247ed01 100644
> --- a/malloc/Makefile
> +++ b/malloc/Makefile
> @@ -43,7 +43,8 @@ tests := mallocbug tst-malloc tst-valloc tst-calloc tst-obstack \
>  	 tst-tcfree1 tst-tcfree2 tst-tcfree3 \
>  	 tst-safe-linking \
>  	 tst-mallocalign1 \
> -	 tst-memalign-2
> +	 tst-memalign-2 \
> +	 tst-memalign-3

OK. Adds a new test.

>  
>  tests-static := \
>  	 tst-interpose-static-nothread \
> @@ -71,7 +72,7 @@ test-srcs = tst-mtrace
>  # with MALLOC_CHECK_=3 because they expect a specific failure.
>  tests-exclude-malloc-check = tst-malloc-check tst-malloc-usable \
>  	tst-mxfast tst-safe-linking \
> -	tst-compathooks-off tst-compathooks-on tst-memalign-2
> +	tst-compathooks-off tst-compathooks-on tst-memalign-2 tst-memalign-3

OK. Adds a new test.

>  
>  # Run all tests with MALLOC_CHECK_=3
>  tests-malloc-check = $(filter-out $(tests-exclude-malloc-check) \
> diff --git a/malloc/malloc.c b/malloc/malloc.c
> index 0315ac5d16..7afc02a759 100644
> --- a/malloc/malloc.c
> +++ b/malloc/malloc.c
> @@ -5048,95 +5048,98 @@ _int_memalign (mstate av, size_t alignment, size_t bytes)
>       and unlikely to meet our alignment requirements.  We have not done
>       any experimentation with searching for aligned fastbins.  */
>  
> -  int first_bin_index;
> -  int first_largebin_index;
> -  int last_bin_index;
> +  if (av != NULL)

OK. If we don't have an arena, then fall through (discovered issue).

> +    {
> +      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))
> +	first_bin_index = smallbin_index (nb);
> +      else
> +	first_bin_index = largebin_index (nb);

OK.

>  
> -  if (in_smallbin_range (nb * 2))
> -    last_bin_index = smallbin_index (nb * 2);
> -  else
> -    last_bin_index = largebin_index (nb * 2);
> +      if (in_smallbin_range (nb * 2))
> +	last_bin_index = smallbin_index (nb * 2);
> +      else
> +	last_bin_index = largebin_index (nb * 2);

OK.

>  
> -  first_largebin_index = largebin_index (MIN_LARGE_SIZE);
> +      first_largebin_index = largebin_index (MIN_LARGE_SIZE);
>  
> -  int victim_index;                 /* its bin index */
> +      int victim_index;                 /* its bin index */
>  
> -  for (victim_index = first_bin_index;
> -       victim_index < last_bin_index;
> -       victim_index ++)
> -    {
> -      victim = NULL;
> +      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.  */
> +	  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 */
> +	      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, bytes) > 0)
> -	    {
> -	      victim = fwd;
> +	      bck = bin_at (av, victim_index);
> +	      fwd = bck->fd;
> +	      while (fwd != bck)
> +		{
> +		  if (chunk_ok_for_memalign (fwd, alignment, nb) > 0)

OK, but needs a follow-up change.

The function chunk_ok_for_memalign() needs to be adjusted to take chunksize.

> +		    {
> +		      victim = fwd;
>  
> -	      /* Unlink it */
> -	      victim->fd->bk = victim->bk;
> -	      victim->bk->fd = victim->fd;
> -	      break;
> +		      /* 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;
>  
> -	  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;
>  
> -      bck = bin_at (av, victim_index);
> -      fwd = bck->fd;
> +	      while (fwd != bck)
> +		{
> +		  int extra;
>  
> -      while (fwd != bck)
> -	{
> -	  int extra;
> +		  if (chunksize (fwd) < nb)
> +		    break;
> +		  extra = chunk_ok_for_memalign (fwd, alignment, nb);

OK.

> +		  if (extra > 0
> +		      && (extra <= best_size || best == NULL))
> +		    {
> +		      best = fwd;
> +		      best_size = extra;
> +		    }
>  
> -	  if (chunksize (fwd) < nb)
> -	      break;
> -	  extra = chunk_ok_for_memalign (fwd, alignment, bytes);
> -	  if (extra > 0
> -	      && (extra <= best_size || best == NULL))
> -	    {
> -	      best = fwd;
> -	      best_size = extra;
> -	    }
> +		  fwd = fwd->fd;
> +		}
> +	      victim = best;
>  
> -	  fwd = fwd->fd;
> -	}
> -      victim = best;
> +	      if (victim != NULL)
> +		{
> +		  unlink_chunk (av, victim);
> +		  break;
> +		}
> +	    }
>  
> -      if (victim != NULL)
> -	{
> -	  unlink_chunk (av, victim);
> -	  break;
> +	  if (victim != NULL)
> +	    break;
>  	}
>      }
>  
> -      if (victim != NULL)
> -	break;
> -    }

OK.

> -
>    /* 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
> @@ -5147,6 +5150,8 @@ _int_memalign (mstate av, size_t alignment, size_t bytes)
>        p = victim;
>        m = chunk2mem (p);
>        set_inuse (p);
> +      if (av != &main_arena)
> +	set_non_main_arena (p);

OK. Set the non-main-arena bit as expected (the original bug).

>      }
>    else
>      {
> diff --git a/malloc/tst-memalign-2.c b/malloc/tst-memalign-2.c
> index 4996578e9f..f229283dbf 100644
> --- a/malloc/tst-memalign-2.c
> +++ b/malloc/tst-memalign-2.c
> @@ -33,9 +33,10 @@ typedef struct TestCase {
>  } TestCase;
>  
>  static TestCase tcache_allocs[] = {
> -  { 24, 8, NULL, NULL },
> -  { 24, 16, NULL, NULL },
> -  { 128, 32, NULL, NULL }
> +  { 24, 32, NULL, NULL },
> +  { 24, 64, NULL, NULL },
> +  { 128, 128, NULL, NULL },
> +  { 500, 128, NULL, NULL }

OK. Raised alignments for testing.

>  };
>  #define TN array_length (tcache_allocs)
>  
> @@ -70,11 +71,15 @@ do_test (void)
>  
>    for (i = 0; i < TN; ++ i)
>      {
> +      size_t sz2;
> +
>        tcache_allocs[i].ptr1 = memalign (tcache_allocs[i].alignment, tcache_allocs[i].size);
>        CHECK (tcache_allocs[i].ptr1, tcache_allocs[i].alignment);
> +      sz2 = malloc_usable_size (tcache_allocs[i].ptr1);
>        free (tcache_allocs[i].ptr1);
> +
>        /* This should return the same chunk as was just free'd.  */
> -      tcache_allocs[i].ptr2 = memalign (tcache_allocs[i].alignment, tcache_allocs[i].size);
> +      tcache_allocs[i].ptr2 = memalign (tcache_allocs[i].alignment, sz2);
>        CHECK (tcache_allocs[i].ptr2, tcache_allocs[i].alignment);
>        free (tcache_allocs[i].ptr2);
>  
> diff --git a/malloc/tst-memalign-3.c b/malloc/tst-memalign-3.c
> new file mode 100644
> index 0000000000..ab90d6ca9b
> --- /dev/null
> +++ b/malloc/tst-memalign-3.c
> @@ -0,0 +1,173 @@
> +/* Test for memalign chunk reuse.

OK. Heuristic test for reuse of aligned chunks.

> +   Copyright (C) 2022 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library is distributed in the hope that it will be useful,
> +   but WITHOUT ANY WARRANTY; without even the implied warranty of
> +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library; if not, see
> +   <https://www.gnu.org/licenses/>.  */
> +
> +#include <errno.h>
> +#include <malloc.h>
> +#include <stdio.h>
> +#include <pthread.h>
> +#include <string.h>
> +#include <unistd.h>
> +#include <array_length.h>
> +#include <libc-pointer-arith.h>
> +#include <support/check.h>
> +#include <support/xthread.h>
> +
> +
> +typedef struct TestCase {
> +  size_t size;
> +  size_t alignment;
> +  void *ptr1;
> +  void *ptr2;
> +} TestCase;
> +
> +static TestCase tcache_allocs[] = {
> +  { 24, 32, NULL, NULL },
> +  { 24, 64, NULL, NULL },
> +  { 128, 128, NULL, NULL },
> +  { 500, 128, NULL, NULL }

OK.

> +};
> +#define TN array_length (tcache_allocs)
> +
> +static TestCase large_allocs[] = {
> +  { 23450, 64, NULL, NULL },
> +  { 23450, 64, NULL, NULL },
> +  { 23550, 64, NULL, NULL },
> +  { 23550, 64, NULL, NULL },
> +  { 23650, 64, NULL, NULL },
> +  { 23650, 64, NULL, NULL },
> +  { 33650, 64, NULL, NULL },
> +  { 33650, 64, NULL, NULL }

OK.

> +};
> +#define LN array_length (large_allocs)
> +
> +void *p;
> +
> +/* Sanity checks, ancillary to the actual test.  */
> +#define CHECK(p,a) \
> +  if (p == NULL || !PTR_IS_ALIGNED (p, a)) \
> +    FAIL_EXIT1 ("NULL or misaligned memory detected.\n");
> +
> +static void *
> +mem_test (void *closure)
> +{
> +  int i;
> +  int j;
> +  int count;
> +  void *ptr[10];
> +  void *p;
> +
> +  /* TCache test.  */
> +  for (i = 0; i < TN; ++ i)
> +    {
> +      size_t sz2;
> +
> +      tcache_allocs[i].ptr1 = memalign (tcache_allocs[i].alignment, tcache_allocs[i].size);
> +      CHECK (tcache_allocs[i].ptr1, tcache_allocs[i].alignment);
> +      sz2 = malloc_usable_size (tcache_allocs[i].ptr1);
> +      free (tcache_allocs[i].ptr1);
> +
> +      /* This should return the same chunk as was just free'd.  */
> +      tcache_allocs[i].ptr2 = memalign (tcache_allocs[i].alignment, sz2);
> +      CHECK (tcache_allocs[i].ptr2, tcache_allocs[i].alignment);
> +      free (tcache_allocs[i].ptr2);
> +
> +      TEST_VERIFY (tcache_allocs[i].ptr1 == tcache_allocs[i].ptr2);

Works only for non-mcheck case.

> +    }
> +
> +  /* Test for non-head tcache hits.  */
> +  for (i = 0; i < array_length (ptr); ++ i)
> +    {
> +      if (i == 4)
> +	{
> +	  ptr[i] = memalign (64, 256);
> +	  CHECK (ptr[i], 64);
> +	}
> +      else
> +	{
> +	  ptr[i] = malloc (256);
> +	  CHECK (ptr[i], 4);
> +	}
> +    }
> +  for (i = 0; i < array_length (ptr); ++ i)
> +    free (ptr[i]);
> +
> +  p = memalign (64, 256);
> +  CHECK (p, 64);
> +
> +  count = 0;
> +  for (i = 0; i < 10; ++ i)
> +    if (ptr[i] == p)
> +      ++ count;
> +  free (p);
> +  TEST_VERIFY (count > 0);
> +
> +  /* Large bins test.  */
> +
> +  for (i = 0; i < LN; ++ i)
> +    {
> +      large_allocs[i].ptr1 = memalign (large_allocs[i].alignment, large_allocs[i].size);
> +      CHECK (large_allocs[i].ptr1, large_allocs[i].alignment);
> +      /* Keep chunks from combining by fragmenting the heap.  */
> +      p = malloc (512);
> +      CHECK (p, 4);
> +    }
> +
> +  for (i = 0; i < LN; ++ i)
> +    free (large_allocs[i].ptr1);
> +
> +  /* Force the unsorted bins to be scanned and moved to small/large
> +     bins.  */
> +  p = malloc (60000);
> +
> +  for (i = 0; i < LN; ++ i)
> +    {
> +      large_allocs[i].ptr2 = memalign (large_allocs[i].alignment, large_allocs[i].size);
> +      CHECK (large_allocs[i].ptr2, large_allocs[i].alignment);
> +    }
> +
> +  count = 0;
> +  for (i = 0; i < LN; ++ i)
> +    {
> +      int ok = 0;
> +      for (j = 0; j < LN; ++ j)
> +	if (large_allocs[i].ptr1 == large_allocs[j].ptr2)
> +	  ok = 1;
> +      if (ok == 1)
> +	count ++;
> +    }
> +
> +  /* The allocation algorithm is complicated outside of the memalign
> +     logic, so just make sure it's working for most of the
> +     allocations.  This avoids possible boundary conditions with
> +     empty/full heaps.  */
> +  TEST_VERIFY (count > LN / 2);
> +
> +  return 0;
> +}
> +
> +static int
> +do_test (void)
> +{
> +  pthread_t p;
> +
> +  p = xpthread_create (NULL, mem_test, NULL);
> +  xpthread_join (p);
> +  return 0;
> +}
> +
> +#include <support/test-driver.c>
> 

-- 
Cheers,
Carlos.