Re: Old topic(s) again [was: Re: Aligned blocks management: obsolete?]

[Stefan Monnier]

> Likewise.

Similarly, I'm not convinced it's an improvement.
Overall, it doesn't seem to simplify the code and I don't see any
evidence that it will have a non-negligible effect on CPU/memory use.


        Stefan


> Dmitry
> === modified file 'configure.in'
> --- configure.in      2012-07-04 08:07:26 +0000
> +++ configure.in      2012-07-04 08:28:33 +0000
> @@ -2704,12 +2704,106 @@
>  __fpending strsignal setitimer \
>  sendto recvfrom getsockname getpeername getifaddrs freeifaddrs \
>  gai_strerror mkstemp getline getdelim fsync sync \
> -difftime posix_memalign \
> +difftime memalign posix_memalign \
>  getpwent endpwent getgrent endgrent \
>  touchlock \
>  strcasecmp strncasecmp \
>  cfmakeraw cfsetspeed copysign __executable_start)
 
> +dnl Check whether posix_memalign can allocate blocks consecutively.
> +if test "$ac_cv_func_posix_memalign" = yes; then
> +  AC_MSG_CHECKING([for block padding size to use with posix_memalign])
> +  AC_RUN_IFELSE([AC_LANG_SOURCE([[#include <stdlib.h>
> +int
> +main ()
> +{
> +  int i, bad;
> +  void *p, *prev;
> +  size_t padsz, blksz = 1024;
> +
> +  for (padsz = 0; padsz <= 64; padsz += sizeof (long))
> +    {
> +      bad = 0;
> +
> +      /* Test asks for BLKSZ - PADSZ bytes aligned at BLKSZ boundary.  */
> +      for (i = 0, prev = NULL; i < 16; i++)
> +        {
> +          if (posix_memalign (&p, blksz, blksz - padsz))
> +            bad++;
> +          else if (prev && p - prev > blksz)
> +            bad++;
> +          prev = p;
> +        }
> +
> +      /* Zero means posix_memalign looks good enough with this PADSZ.  */
> +      if (!bad)
> +        return padsz;
> +    }
> +
> +  /* No suitable PADSZ was found, posix_memalign isn't good enough for us.  
> */
> +  return 255;
> +}]])], emacs_cv_posix_memalign_pad=255, emacs_cv_posix_memalign_pad=$?,
> +  emacs_cv_posix_memalign_pad=255)
> +  if test $emacs_cv_posix_memalign_pad -le 64; then
> +      AC_MSG_RESULT($emacs_cv_posix_memalign_pad)
> +      AC_DEFINE(POSIX_MEMALIGN_WORKS, 1,
> +        [Define to 1 if you have good enough `posix_memalign' function.])
> +      AC_DEFINE_UNQUOTED(BLOCK_PADDING, $emacs_cv_posix_memalign_pad,
> +        [Block padding used to allocate aligned blocks.])
> +  else
> +      AC_MSG_RESULT([not detected, posix_memalign will not be used])
> +  fi
> +fi
> +
> +dnl If posix_memalign isn't available or tends to create holes
> +dnl between blocks, check whether memalign performs better.
> +if test "$emacs_cv_posix_memalign_pad" -gt 64; then
> +  if test "$ac_cv_func_memalign" = yes; then
> +    AC_MSG_CHECKING([for block padding size for memalign])
> +    AC_RUN_IFELSE([AC_LANG_SOURCE([[#include <malloc.h>
> +int
> +main ()
> +{
> +  int i, bad;
> +  void *p, *prev;
> +  size_t padsz, blksz = 1024;
> +
> +  for (padsz = 0; padsz <= 64; padsz += sizeof (long))
> +    {
> +      bad = 0;
> +
> +      /* Test asks for BLKSZ - PADSZ bytes aligned at BLKSZ boundary.  */
> +      for (i = 0, prev = NULL; i < 16; i++)
> +        {
> +          p = memalign (blksz, blksz - padsz);
> +          if (!p)
> +            bad++;
> +          else if (prev && p - prev > blksz)
> +            bad++;
> +          prev = p;
> +        }
> +  
> +      /* Zero means memalign looks good enough with this PADSZ.  */
> +      if (!bad)
> +        return padsz;
> +    }
> +
> +  /* No suitable PADSZ was found, memalign isn't good enough for us.  */
> +  return 255;
> +}]])], emacs_cv_memalign_pad=255, emacs_cv_memalign_pad=$?,
> +    emacs_cv_memalign_pad=255)
> +    if test $emacs_cv_memalign_pad -le 64; then
> +      AC_MSG_RESULT($emacs_cv_memalign_pad)
> +      AC_DEFINE(MEMALIGN_WORKS, 1,
> +        [Define to 1 if you have good enough `memalign' function.])
> +      AC_DEFINE_UNQUOTED(BLOCK_PADDING, $emacs_cv_memalign_pad,
> +        [Block padding used to allocate aligned blocks.])
> +    else
> +      AC_MSG_RESULT([not detected, memalign will not be used])
> +    fi
> +  fi
> +fi
> +
>  dnl Cannot use AC_CHECK_FUNCS
>  AC_CACHE_CHECK([for __builtin_unwind_init],
>              emacs_cv_func___builtin_unwind_init,

> === modified file 'src/alloc.c'
> --- src/alloc.c       2012-07-03 16:35:53 +0000
> +++ src/alloc.c       2012-07-04 08:33:52 +0000
> @@ -308,9 +308,6 @@
>    MEM_TYPE_VECTOR_BLOCK
>  };
 
> -static void *lisp_malloc (size_t, enum mem_type);
> -
> -
>  #if GC_MARK_STACK || defined GC_MALLOC_CHECK
 
>  #if GC_MARK_STACK == GC_USE_GCPROS_CHECK_ZOMBIES
> @@ -390,7 +387,6 @@
>  #define MEM_NIL &mem_z
 
>  static struct Lisp_Vector *allocate_vectorlike (ptrdiff_t);
> -static void lisp_free (void *);
>  static void mark_stack (void);
>  static int live_vector_p (struct mem_node *, void *);
>  static int live_buffer_p (struct mem_node *, void *);
> @@ -887,15 +883,33 @@
>    return Qnil;
>  }
 
> +#if ! USE_LSB_TAG
> +
> +/* Used to catch invalid address when debugging.  */
> +
> +void *lisp_malloc_loser EXTERNALLY_VISIBLE;
> +
> +/* Nonzero if the memory at ADDR can be
> +   addressed thru a Lisp object's pointer.  */
> +
> +static inline int
> +verify_address (char *addr)
> +{
> +  Lisp_Object obj;
> +
> +  XSETCONS (obj, addr);
> +  if ((char *) XCONS (obj) == addr)
> +    return 1;
> +  lisp_malloc_loser = addr;
> +  return 0;
> +}
> +
> +#endif /* not USE_LSB_TAG */
 
>  /* Like malloc but used for allocating Lisp data.  NBYTES is the
>     number of bytes to allocate, TYPE describes the intended use of the
>     allocated memory block (for strings, for conses, ...).  */
 
> -#if ! USE_LSB_TAG
> -void *lisp_malloc_loser EXTERNALLY_VISIBLE;
> -#endif
> -
>  static void *
>  lisp_malloc (size_t nbytes, enum mem_type type)
>  {
> @@ -907,24 +921,33 @@
>    allocated_mem_type = type;
>  #endif
 
> +#ifdef DOUG_LEA_MALLOC
> +  /* Prevent mmap'ing the chunk.  Lisp data may not be mmap'ed
> +     because mapped region contents are not preserved in
> +     a dumped Emacs.  */
> +  mallopt (M_MMAP_MAX, 0);
> +#endif
>    val = (void *) malloc (nbytes);
> +#ifdef DOUG_LEA_MALLOC
> +  /* Back to a reasonable maximum of mmap'ed areas.  */
> +  mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
> +#endif
> +
> +  if (!val && nbytes)
> +    {
> +      MALLOC_UNBLOCK_INPUT;
> +      memory_full (nbytes);
> +    }
 
>  #if ! USE_LSB_TAG
> -  /* If the memory just allocated cannot be addressed thru a Lisp
> -     object's pointer, and it needs to be,
> -     that's equivalent to running out of memory.  */
> -  if (val && type != MEM_TYPE_NON_LISP)
> +  if (val && type != MEM_TYPE_NON_LISP
> +      && !verify_address ((char *) val + nbytes - 1))
>      {
> -      Lisp_Object tem;
> -      XSETCONS (tem, (char *) val + nbytes - 1);
> -      if ((char *) XCONS (tem) != (char *) val + nbytes - 1)
> -     {
> -       lisp_malloc_loser = val;
> -       free (val);
> -       val = 0;
> -     }
> +      free (val);
> +      MALLOC_UNBLOCK_INPUT;
> +      memory_full (SIZE_MAX);
>      }
> -#endif
> +#endif /* not USE_LSB_TAG */
 
>  #if GC_MARK_STACK && !defined GC_MALLOC_CHECK
>    if (val && type != MEM_TYPE_NON_LISP)
> @@ -932,8 +955,6 @@
>  #endif
 
>    MALLOC_UNBLOCK_INPUT;
> -  if (!val && nbytes)
> -    memory_full (nbytes);
>    return val;
>  }
 
> @@ -951,30 +972,33 @@
>    MALLOC_UNBLOCK_INPUT;
>  }
 
> -/*****  Allocation of aligned blocks of memory to store Lisp data.  *****/
> -
> -/* The entry point is lisp_align_malloc which returns blocks of at most
> -   BLOCK_BYTES and guarantees they are aligned on a BLOCK_ALIGN boundary.  */
> -
> -#if defined (HAVE_POSIX_MEMALIGN) && defined (SYSTEM_MALLOC)
> -#define USE_POSIX_MEMALIGN 1
> -#endif
> +/* Allocation of aligned blocks is somewhat tricky.  If posix_memalign is
> +   available, configure tries to determine the block padding value to help
> +   posix_memalign allocate blocks of (1024 - padding) bytes without holes
> +   between them.  If suitable padding is found, we define 
> POSIX_MEMALIGN_WORKS,
> +   BLOCK_PADDING to padding value and use posix_memalign and free.  Some
> +   systems lacks posix_memalign, but provides memalign; for such a system,
> +   configure performs similar check for memalign.  If suitable padding is
> +   found, we define MEMALIGN_WORKS, BLOCK_PADDING to padding value and use
> +   memalign and free.  If none of the above, we use internal_align_alloc and
> +   internal_align_free.  */
 
>  /* BLOCK_ALIGN has to be a power of 2.  */
> +
>  #define BLOCK_ALIGN (1 << 10)
 
> -/* Padding to leave at the end of a malloc'd block.  This is to give
> -   malloc a chance to minimize the amount of memory wasted to alignment.
> -   It should be tuned to the particular malloc library used.
> -   On glibc-2.3.2, malloc never tries to align, so a padding of 0 is best.
> -   posix_memalign on the other hand would ideally prefer a value of 4
> -   because otherwise, there's 1020 bytes wasted between each ablocks.
> -   In Emacs, testing shows that those 1020 can most of the time be
> -   efficiently used by malloc to place other objects, so a value of 0 can
> -   still preferable unless you have a lot of aligned blocks and virtually
> -   nothing else.  */
> +#if ! POSIX_MEMALIGN_WORKS && ! MEMALIGN_WORKS
> +
> +/* Here we assume that malloc implementation has
> +   nothing about aligned blocks management.  */
> +
> +/* Padding to leave at the end of a malloc'd block.  */
> +
>  #define BLOCK_PADDING 0
> -#define BLOCK_BYTES \
> +
> +/* Maximum amount of memory in aligned block.  */
> +
> +#define BLOCK_BYTES                                          \
>    (BLOCK_ALIGN - sizeof (struct ablocks *) - BLOCK_PADDING)
 
>  /* Internal data structures and constants.  */
> @@ -982,6 +1006,7 @@
>  #define ABLOCKS_SIZE 16
 
>  /* An aligned block of memory.  */
> +
>  struct ablock
>  {
>    union
> @@ -1007,12 +1032,14 @@
>  };
 
>  /* A bunch of consecutive aligned blocks.  */
> +
>  struct ablocks
>  {
>    struct ablock blocks[ABLOCKS_SIZE];
>  };
 
> -/* Size of the block requested from malloc or posix_memalign.  */
> +/* Size of the block requested from underlying malloc.  */
> +
>  #define ABLOCKS_BYTES (sizeof (struct ablocks) - BLOCK_PADDING)
 
>  #define ABLOCK_ABASE(block) \
> @@ -1021,94 +1048,43 @@
>     : (block)->abase)
 
>  /* Virtual `busy' field.  */
> +
>  #define ABLOCKS_BUSY(abase) ((abase)->blocks[0].abase)
 
>  /* Pointer to the (not necessarily aligned) malloc block.  */
> -#ifdef USE_POSIX_MEMALIGN
> -#define ABLOCKS_BASE(abase) (abase)
> -#else
> -#define ABLOCKS_BASE(abase) \
> +
> +#define ABLOCKS_BASE(abase)                                          \
>    (1 & (intptr_t) ABLOCKS_BUSY (abase) ? abase : ((void**)abase)[-1])
> -#endif
 
>  /* The list of free ablock.   */
> +
>  static struct ablock *free_ablock;
 
> -/* Allocate an aligned block of nbytes.
> -   Alignment is on a multiple of BLOCK_ALIGN and `nbytes' has to be
> -   smaller or equal to BLOCK_BYTES.  */
> +/* Allocate an aligned block of NBYTES.  */
> +
>  static void *
> -lisp_align_malloc (size_t nbytes, enum mem_type type)
> +internal_align_alloc (size_t nbytes)
>  {
>    void *base, *val;
>    struct ablocks *abase;
 
>    eassert (nbytes <= BLOCK_BYTES);
 
> -  MALLOC_BLOCK_INPUT;
> -
> -#ifdef GC_MALLOC_CHECK
> -  allocated_mem_type = type;
> -#endif
> -
>    if (!free_ablock)
>      {
>        int i;
>        intptr_t aligned; /* int gets warning casting to 64-bit pointer.  */
 
> -#ifdef DOUG_LEA_MALLOC
> -      /* Prevent mmap'ing the chunk.  Lisp data may not be mmap'ed
> -      because mapped region contents are not preserved in
> -      a dumped Emacs.  */
> -      mallopt (M_MMAP_MAX, 0);
> -#endif
> -
> -#ifdef USE_POSIX_MEMALIGN
> -      {
> -     int err = posix_memalign (&base, BLOCK_ALIGN, ABLOCKS_BYTES);
> -     if (err)
> -       base = NULL;
> -     abase = base;
> -      }
> -#else
>        base = malloc (ABLOCKS_BYTES);
>        abase = ALIGN (base, BLOCK_ALIGN);
> -#endif
 
> -      if (base == 0)
> -     {
> -       MALLOC_UNBLOCK_INPUT;
> -       memory_full (ABLOCKS_BYTES);
> -     }
> +      if (base == NULL)
> +     return base;
 
>        aligned = (base == abase);
>        if (!aligned)
>       ((void**)abase)[-1] = base;
 
> -#ifdef DOUG_LEA_MALLOC
> -      /* Back to a reasonable maximum of mmap'ed areas.  */
> -      mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
> -#endif
> -
> -#if ! USE_LSB_TAG
> -      /* If the memory just allocated cannot be addressed thru a Lisp
> -      object's pointer, and it needs to be, that's equivalent to
> -      running out of memory.  */
> -      if (type != MEM_TYPE_NON_LISP)
> -     {
> -       Lisp_Object tem;
> -       char *end = (char *) base + ABLOCKS_BYTES - 1;
> -       XSETCONS (tem, end);
> -       if ((char *) XCONS (tem) != end)
> -         {
> -           lisp_malloc_loser = base;
> -           free (base);
> -           MALLOC_UNBLOCK_INPUT;
> -           memory_full (SIZE_MAX);
> -         }
> -     }
> -#endif
> -
>        /* Initialize the blocks and put them on the free list.
>        If `base' was not properly aligned, we can't use the last block.  */
>        for (i = 0; i < (aligned ? ABLOCKS_SIZE : ABLOCKS_SIZE - 1); i++)
> @@ -1132,27 +1108,15 @@
>    val = free_ablock;
>    free_ablock = free_ablock->x.next_free;
 
> -#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
> -  if (type != MEM_TYPE_NON_LISP)
> -    mem_insert (val, (char *) val + nbytes, type);
> -#endif
> -
> -  MALLOC_UNBLOCK_INPUT;
> -
> -  eassert (0 == ((uintptr_t) val) % BLOCK_ALIGN);
>    return val;
>  }
 
>  static void
> -lisp_align_free (void *block)
> +internal_align_free (void *block)
>  {
>    struct ablock *ablock = block;
>    struct ablocks *abase = ABLOCK_ABASE (ablock);
 
> -  MALLOC_BLOCK_INPUT;
> -#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
> -  mem_delete (mem_find (block));
> -#endif
>    /* Put on free list.  */
ablock-> x.next_free = free_ablock;
>    free_ablock = ablock;
> @@ -1178,11 +1142,103 @@
>       }
>        eassert ((aligned & 1) == aligned);
>        eassert (i == (aligned ? ABLOCKS_SIZE : ABLOCKS_SIZE - 1));
> -#ifdef USE_POSIX_MEMALIGN
> -      eassert ((uintptr_t) ABLOCKS_BASE (abase) % BLOCK_ALIGN == 0);
> -#endif
>        free (ABLOCKS_BASE (abase));
>      }
> +}
> +
> +#else /* ! POSIX_MEMALIGN_WORKS && ! MEMALIGN_WORKS */
> +
> +/* Here we assume that malloc implementation has either posix_memalign or
> +   memalign, and suitable BLOCK_PADDING value was detected by configure.  */
> +
> +#ifndef BLOCK_PADDING
> +#error "unknown BLOCK_PADDING"
> +#endif
> +
> +/* Maximum amount of memory in aligned block.  */
> +
> +#define BLOCK_BYTES (BLOCK_ALIGN - BLOCK_PADDING)
> +
> +#endif /* ! POSIX_MEMALIGN_WORKS && ! MEMALIGN_WORKS */
> +
> +/* Like lisp_malloc, but allocates aligned block of at
> +   most BLOCK_BYTES aligned on a BLOCK_ALIGN boundary.  */
> +
> +static void *
> +lisp_align_malloc (size_t nbytes, enum mem_type type)
> +{
> +  void *val;
> +
> +  eassert (nbytes <= BLOCK_BYTES);
> +
> +  MALLOC_BLOCK_INPUT;
> +
> +#ifdef GC_MALLOC_CHECK
> +  allocated_mem_type = type;
> +#endif
> +
> +#ifdef DOUG_LEA_MALLOC
> +  /* Prevent mmap'ing the chunk.  Lisp data may not be mmap'ed
> +     because mapped region contents are not preserved in
> +     a dumped Emacs.  */
> +  mallopt (M_MMAP_MAX, 0);
> +#endif
> +
> +#ifdef POSIX_MEMALIGN_WORKS
> +  if (posix_memalign (&val, BLOCK_ALIGN, nbytes))
> +    val = NULL;
> +#elif MEMALIGN_WORKS
> +  val = memalign (BLOCK_ALIGN, nbytes);
> +#else
> +  val = internal_align_alloc (nbytes);
> +#endif
> +
> +#ifdef DOUG_LEA_MALLOC
> +  /* Back to a reasonable maximum of mmap'ed areas.  */
> +  mallopt (M_MMAP_MAX, MMAP_MAX_AREAS);
> +#endif
> +
> +  if (!val && nbytes)
> +    {
> +      MALLOC_UNBLOCK_INPUT;
> +      memory_full (nbytes);
> +    }
> +
> +#if ! USE_LSB_TAG
> +  if (type != MEM_TYPE_NON_LISP 
> +      && !verify_address ((char *) val + nbytes - 1))
> +    {
> +      free (val);
> +      MALLOC_UNBLOCK_INPUT;
> +      memory_full (SIZE_MAX);
> +    }
> +#endif /* not USE_LSB_TAG */
> +
> +#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
> +  if (type != MEM_TYPE_NON_LISP)
> +    mem_insert (val, (char *) val + nbytes, type);
> +#endif
> +
> +  MALLOC_UNBLOCK_INPUT;
> +  eassert (0 == ((uintptr_t) val) % BLOCK_ALIGN);
> +  return val;
> +}
> +
> +/* Free aligned BLOCK.  This must be called to free
> +   memory allocated with a call to lisp_align_malloc.  */
> +
> +static void
> +lisp_align_free (void *block)
> +{
> +  MALLOC_BLOCK_INPUT;
> +#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
> +  mem_delete (mem_find (block));
> +#endif
> +#if POSIX_MEMALIGN_WORKS || MEMALIGN_WORKS
> +  free (block);
> +#else
> +  internal_align_free (block);
> +#endif
>    MALLOC_UNBLOCK_INPUT;
>  }
 
> @@ -6661,8 +6717,10 @@
>    pure_bytes_used_lisp = pure_bytes_used_non_lisp = 0;
>    pure_bytes_used_before_overflow = 0;
 
> +#if ! POSIX_MEMALIGN_WORKS && ! MEMALIGN_WORKS
>    /* Initialize the list of free aligned blocks.  */
>    free_ablock = NULL;
> +#endif
 
>  #if GC_MARK_STACK || defined GC_MALLOC_CHECK
>    mem_init ();