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

[Dmitry Antipov <dmantipov@yandex.ru>]

[-- Attachment #1: Type: text/plain, Size: 18 bytes --]

Likewise.

Dmitry

[-- Attachment #2: lisp_alloc.patch --]
[-- Type: text/plain, Size: 15523 bytes --]

=== 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 ();