Aligned blocks management: obsolete?

Aligned blocks management: obsolete?

[Dmitry Antipov]

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

Is it still required to maintain the cache of aligned blocks
to workaround poor malloc behavior? I believe an attached
example should perform well (i.e. allocate ~4K blocks without
~4K holes between them) on top of any non-ancient glibc (no
ideas about other system malloc implementations, BTW).

Dmitry

[-- Attachment #2: aligned-alloc.c --]
[-- Type: text/plain, Size: 745 bytes --]

#include <stdio.h>
#include <stdlib.h>

#define BLOCKSZ 4096

int
main (int argc, char *argv[])
{
  int i, j;
  void *p;

  /* make some chaos in the heap */
  for (i = 0; i < 1000; i++)
    for (j = 0; j < 1024; j++)
      {
	p = malloc (j);
	if (((i + j) & 7) == 0)
	  free (p);
      }

  /* test */
  for (i = 0; i < 16; i++)
    if (!posix_memalign (&p, BLOCKSZ, BLOCKSZ - sizeof (long)))
      printf ("%p\n", p);
  printf ("--\n");

  /* make even more chaos with larger chunks */
  for (i = 0; i < 1000; i++)
    {
      p = malloc (i * 1000);
      if ((i & 7) == 0)
	free (p);
    }

  /* test again */
  for (i = 0; i < 16; i++)
    if (!posix_memalign (&p, BLOCKSZ, BLOCKSZ - sizeof (long)))
      printf ("%p\n", p);

  return 0;
}

Re: Aligned blocks management: obsolete?

[Eli Zaretskii]

> Date: Mon, 12 Dec 2011 12:11:48 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> 
> Is it still required to maintain the cache of aligned blocks
> to workaround poor malloc behavior?

Can you please tell what you mean by that?  Are you alluding to
lisp_align_malloc and its subroutines, or to something else?

> I believe an attached
> example should perform well (i.e. allocate ~4K blocks without
> ~4K holes between them) on top of any non-ancient glibc (no
> ideas about other system malloc implementations, BTW).

I hope Emacs is not on its way to become a glibc-only project.  Quite
a few supported platforms don't use glibc: Cygwin, *BSD (AFAIK),
Windows.

Are platforms that use gmalloc.c, with or without ralloc.c, OK in this
regard?  If not, what feature(s) are missing that are present in
glibc?

Re: Aligned blocks management: obsolete?

[Dmitry Antipov]

On 12/12/2011 05:13 PM, Eli Zaretskii wrote:

> Can you please tell what you mean by that?  Are you alluding to
> lisp_align_malloc and its subroutines, or to something else?

Yes. I'm just curious about comment above lisp_align_malloc -
the comment references glibc-2.3.2, which was released ~8 years ago :-).

> I hope Emacs is not on its way to become a glibc-only project.  Quite
> a few supported platforms don't use glibc: Cygwin, *BSD (AFAIK),
> Windows.

That's why I'm asking for. I suppose that any non-ancient glibc malloc
doesn't require such a glitch in lisp_align_malloc any more - but
I have no ideas about malloc implementation on other supported systems.

Dmitry

Re: Aligned blocks management: obsolete?

[Eli Zaretskii]

> Date: Mon, 12 Dec 2011 18:07:15 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> 
> > Can you please tell what you mean by that?  Are you alluding to
> > lisp_align_malloc and its subroutines, or to something else?
> 
> Yes. I'm just curious about comment above lisp_align_malloc -
> the comment references glibc-2.3.2, which was released ~8 years ago :-).
> 
> > I hope Emacs is not on its way to become a glibc-only project.  Quite
> > a few supported platforms don't use glibc: Cygwin, *BSD (AFAIK),
> > Windows.
> 
> That's why I'm asking for. I suppose that any non-ancient glibc malloc
> doesn't require such a glitch in lisp_align_malloc any more - but
> I have no ideas about malloc implementation on other supported systems.

Can you formulate the misfeatures which lisp_align_malloc protects
against?  Then perhaps it would be possible to see whether gmalloc and
ralloc solve them.

TIA

Re: Aligned blocks management: obsolete?

[Paul Eggert]

On 12/12/11 06:07, Dmitry Antipov wrote:
> I suppose that any non-ancient glibc malloc
> doesn't require such a glitch in lisp_align_malloc any more

This sounds correct to me as well, though I can't cite
chapter and verse offhand.  Certainly the posix_memalign
implementation has mutated significantly since glibc 2.3.2
came out in 2003, and any performance measurements
based on 2.3.2 are suspect now.

More generally, if some cruft was put into alloc.c long ago
for performance reasons, and if we can no longer demonstrate
that the cruft improves performance significantly
on currently-used platforms, then surely it's OK to remove it
after the feature freeze is over.  Cruft like that has a real
maintenance cost, and there's no point keeping it
if it doesn't actually have a performance benefit.

Re: Aligned blocks management: obsolete?

[Dmitry Antipov]

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

[some stuff from old discussion below]

On 12/12/2011 10:27 PM, Paul Eggert wrote:

> On 12/12/11 06:07, Dmitry Antipov wrote:
>> I suppose that any non-ancient glibc malloc
>> doesn't require such a glitch in lisp_align_malloc any more
>
> This sounds correct to me as well, though I can't cite
> chapter and verse offhand.  Certainly the posix_memalign
> implementation has mutated significantly since glibc 2.3.2
> came out in 2003, and any performance measurements
> based on 2.3.2 are suspect now.
>
> More generally, if some cruft was put into alloc.c long ago
> for performance reasons, and if we can no longer demonstrate
> that the cruft improves performance significantly
> on currently-used platforms, then surely it's OK to remove it
> after the feature freeze is over.  Cruft like that has a real
> maintenance cost, and there's no point keeping it
> if it doesn't actually have a performance benefit.

I believe this becomes more and more actual because more and more
of ancient systems with poor malloc implementations falls into their
graves; this cleanup assumes that every malloc implementation
has reasonably efficient posix_memalign or memalign at least.

Dmitry

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

=== modified file 'src/alloc.c'
--- src/alloc.c	2012-06-16 12:24:15 +0000
+++ src/alloc.c	2012-06-19 16:46:26 +0000
@@ -309,9 +309,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
@@ -888,19 +885,37 @@
   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 void
+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)
 {
-  register void *val;
+  void *val;
 
   MALLOC_BLOCK_INPUT;
 
@@ -908,24 +923,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)
@@ -933,116 +957,33 @@
 #endif
 
   MALLOC_UNBLOCK_INPUT;
-  if (!val && nbytes)
-    memory_full (nbytes);
   return val;
 }
 
-/* Free BLOCK.  This must be called to free memory allocated with a
-   call to lisp_malloc.  */
-
-static void
-lisp_free (void *block)
-{
-  MALLOC_BLOCK_INPUT;
-  free (block);
-#if GC_MARK_STACK && !defined GC_MALLOC_CHECK
-  mem_delete (mem_find (block));
-#endif
-  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.  We assume that malloc implementation
+   provides posix_memalign or (obsolete) memalign at least.  */
 
 /* 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.  */
-#define BLOCK_PADDING 0
-#define BLOCK_BYTES \
-  (BLOCK_ALIGN - sizeof (struct ablocks *) - BLOCK_PADDING)
-
-/* Internal data structures and constants.  */
-
-#define ABLOCKS_SIZE 16
-
-/* An aligned block of memory.  */
-struct ablock
-{
-  union
-  {
-    char payload[BLOCK_BYTES];
-    struct ablock *next_free;
-  } x;
-  /* `abase' is the aligned base of the ablocks.  */
-  /* It is overloaded to hold the virtual `busy' field that counts
-     the number of used ablock in the parent ablocks.
-     The first ablock has the `busy' field, the others have the `abase'
-     field.  To tell the difference, we assume that pointers will have
-     integer values larger than 2 * ABLOCKS_SIZE.  The lowest bit of `busy'
-     is used to tell whether the real base of the parent ablocks is `abase'
-     (if not, the word before the first ablock holds a pointer to the
-     real base).  */
-  struct ablocks *abase;
-  /* The padding of all but the last ablock is unused.  The padding of
-     the last ablock in an ablocks is not allocated.  */
-#if BLOCK_PADDING
-  char padding[BLOCK_PADDING];
-#endif
-};
-
-/* A bunch of consecutive aligned blocks.  */
-struct ablocks
-{
-  struct ablock blocks[ABLOCKS_SIZE];
-};
-
-/* Size of the block requested from malloc or posix_memalign.  */
-#define ABLOCKS_BYTES (sizeof (struct ablocks) - BLOCK_PADDING)
-
-#define ABLOCK_ABASE(block) \
-  (((uintptr_t) (block)->abase) <= (1 + 2 * ABLOCKS_SIZE)	\
-   ? (struct ablocks *)(block)					\
-   : (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) \
-  (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.  */
+/* Padding to leave at the end of a malloc'd block.  This should help
+   the malloc implementation to allocate aligned blocks consecutively.
+   FIXME: tuned to fit glibc malloc, may be suboptimal for others.  */
+
+#define BLOCK_PADDING sizeof (long)
+
+/* Maximum amount of memory in aligned block.  */
+
+#define BLOCK_BYTES (BLOCK_ALIGN - BLOCK_PADDING)
+
+/* 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 *base, *val;
-  struct ablocks *abase;
+  void *val;
 
   eassert (nbytes <= BLOCK_BYTES);
 
@@ -1052,86 +993,40 @@
   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);
+  /* 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;
-      }
+#ifdef HAVE_POSIX_MEMALIGN
+  if (posix_memalign (&val, BLOCK_ALIGN, nbytes))
+    val = NULL;
 #else
-      base = malloc (ABLOCKS_BYTES);
-      abase = ALIGN (base, BLOCK_ALIGN);
+  val = memalign (BLOCK_ALIGN, nbytes);
 #endif
 
-      if (base == 0)
-	{
-	  MALLOC_UNBLOCK_INPUT;
-	  memory_full (ABLOCKS_BYTES);
-	}
-
-      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);
+  /* 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 (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++)
-	{
-	  abase->blocks[i].abase = abase;
-	  abase->blocks[i].x.next_free = free_ablock;
-	  free_ablock = &abase->blocks[i];
-	}
-      ABLOCKS_BUSY (abase) = (struct ablocks *) aligned;
-
-      eassert (0 == ((uintptr_t) abase) % BLOCK_ALIGN);
-      eassert (ABLOCK_ABASE (&abase->blocks[3]) == abase); /* 3 is arbitrary */
-      eassert (ABLOCK_ABASE (&abase->blocks[0]) == abase);
-      eassert (ABLOCKS_BASE (abase) == base);
-      eassert (aligned == (intptr_t) ABLOCKS_BUSY (abase));
+  if (type != MEM_TYPE_NON_LISP 
+      && !verify_address ((char *) val + nbytes - 1))
+    {
+      free (val);
+      MALLOC_UNBLOCK_INPUT;
+      memory_full (SIZE_MAX);
     }
-
-  abase = ABLOCK_ABASE (free_ablock);
-  ABLOCKS_BUSY (abase) =
-    (struct ablocks *) (2 + (intptr_t) ABLOCKS_BUSY (abase));
-  val = free_ablock;
-  free_ablock = free_ablock->x.next_free;
+#endif /* not USE_LSB_TAG */
 
 #if GC_MARK_STACK && !defined GC_MALLOC_CHECK
   if (type != MEM_TYPE_NON_LISP)
@@ -1139,51 +1034,21 @@
 #endif
 
   MALLOC_UNBLOCK_INPUT;
-
   eassert (0 == ((uintptr_t) val) % BLOCK_ALIGN);
   return val;
 }
 
+/* Free BLOCK.  This must be called to free memory allocated
+   with a call to lisp_malloc or lisp_align_malloc.  */
+
 static void
-lisp_align_free (void *block)
+lisp_free (void *block)
 {
-  struct ablock *ablock = block;
-  struct ablocks *abase = ABLOCK_ABASE (ablock);
-
   MALLOC_BLOCK_INPUT;
+  free (block);
 #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;
-  /* Update busy count.  */
-  ABLOCKS_BUSY (abase)
-    = (struct ablocks *) (-2 + (intptr_t) ABLOCKS_BUSY (abase));
-
-  if (2 > (intptr_t) ABLOCKS_BUSY (abase))
-    { /* All the blocks are free.  */
-      int i = 0, aligned = (intptr_t) ABLOCKS_BUSY (abase);
-      struct ablock **tem = &free_ablock;
-      struct ablock *atop = &abase->blocks[aligned ? ABLOCKS_SIZE : ABLOCKS_SIZE - 1];
-
-      while (*tem)
-	{
-	  if (*tem >= (struct ablock *) abase && *tem < atop)
-	    {
-	      i++;
-	      *tem = (*tem)->x.next_free;
-	    }
-	  else
-	    tem = &(*tem)->x.next_free;
-	}
-      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));
-    }
   MALLOC_UNBLOCK_INPUT;
 }
 
@@ -3757,7 +3622,7 @@
 	    if (i == 0)
 	      free (spare_memory[i]);
 	    else if (i >= 1 && i <= 4)
-	      lisp_align_free (spare_memory[i]);
+	      lisp_free (spare_memory[i]);
 	    else
 	      lisp_free (spare_memory[i]);
 	    spare_memory[i] = 0;
@@ -6292,7 +6157,7 @@
 	    *cprev = cblk->next;
 	    /* Unhook from the free list.  */
 	    cons_free_list = cblk->conses[0].u.chain;
-	    lisp_align_free (cblk);
+	    lisp_free (cblk);
 	  }
 	else
 	  {
@@ -6338,7 +6203,7 @@
 	    *fprev = fblk->next;
 	    /* Unhook from the free list.  */
 	    float_free_list = fblk->floats[0].u.chain;
-	    lisp_align_free (fblk);
+	    lisp_free (fblk);
 	  }
 	else
 	  {
@@ -6671,9 +6536,6 @@
   pure_bytes_used_lisp = pure_bytes_used_non_lisp = 0;
   pure_bytes_used_before_overflow = 0;
 
-  /* Initialize the list of free aligned blocks.  */
-  free_ablock = NULL;
-
 #if GC_MARK_STACK || defined GC_MALLOC_CHECK
   mem_init ();
   Vdead = make_pure_string ("DEAD", 4, 4, 0);

Re: Aligned blocks management: obsolete?

[Eli Zaretskii]

> Date: Tue, 19 Jun 2012 20:51:08 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> Cc: Paul Eggert <eggert@cs.ucla.edu>
> 
> this cleanup assumes that every malloc implementation
> has reasonably efficient posix_memalign or memalign at least.

Does the implementation of these in gmalloc.c satisfy the "reasonably
efficient" requirement?  If not, platforms that use gmalloc.c will be
in trouble.

Re: Aligned blocks management: obsolete?

[Stefan Monnier]

> I believe this becomes more and more actual because more and more
> of ancient systems with poor malloc implementations falls into their
> graves; this cleanup assumes that every malloc implementation
> has reasonably efficient posix_memalign or memalign at least.

AFAIK, while posix_memalign might be useable in general, the old
memalign is not because it can't be free'd (it can with glibc's
memalign but not with all memaligns).

> Does the implementation of these in gmalloc.c satisfy the "reasonably
> efficient" requirement?  If not, platforms that use gmalloc.c will be
> in trouble.

I remember looking into it, back then, but I can't remember what I fount
out ;-)


        Stefan

Re: Aligned blocks management: obsolete?

[Dmitry Antipov]

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

This code tries to utilize system malloc features and falls back to legacy
aligned blocks management code if system malloc implementation is unknown,
broken, or lacks aligned allocation routines.

It will be great if someone can help to test this on Windows, OSX, old *BSD
and other non-GNU/Linux systems; in particular, I believe OSX should have
some specific aligned allocation stuff, which I'm not aware about.

Dmitry

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

=== modified file 'configure.in'
--- configure.in	2012-06-13 13:40:48 +0000
+++ configure.in	2012-06-20 05:59:43 +0000
@@ -2698,11 +2698,29 @@
 __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 \
 cfmakeraw cfsetspeed copysign __executable_start)
 
+dnl If there is no posix_memalign, check whether pointer 
+dnl returned by memalign can be passed to free.
+if test "$ac_cv_func_posix_memalign" != yes; then
+  if test "$ac_cv_func_memalign" = yes; then
+    AC_MSG_CHECKING([whether pointer returned by memalign can be passed to free])
+    AC_RUN_IFELSE([AC_LANG_SOURCE([[#include <malloc.h>
+main () { void *ptr = memalign (1024, 1024);
+if (!ptr) return 1; free (ptr); return 0; }
+]])], emacs_cv_working_memalign=yes, emacs_cv_working_memalign=no,
+    emacs_cv_working_memalign=no)
+    AC_MSG_RESULT($emacs_cv_working_memalign)
+    if test $emacs_cv_working_memalign = yes; then
+      AC_DEFINE(HAVE_WORKING_MEMALIGN, 1,
+        [Define to 1 if pointer returned by `memalign' can be passed to `free'.])
+    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-06-19 16:56:28 +0000
+++ src/alloc.c	2012-06-20 06:35:05 +0000
@@ -309,9 +309,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
@@ -888,19 +885,37 @@
   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 void
+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)
 {
-  register void *val;
+  void *val;
 
   MALLOC_BLOCK_INPUT;
 
@@ -908,24 +923,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)
@@ -933,13 +957,11 @@
 #endif
 
   MALLOC_UNBLOCK_INPUT;
-  if (!val && nbytes)
-    memory_full (nbytes);
   return val;
 }
 
-/* Free BLOCK.  This must be called to free memory allocated with a
-   call to lisp_malloc.  */
+/* Free BLOCK.  This must be called to free
+   memory allocated with a call to lisp_malloc.  */
 
 static void
 lisp_free (void *block)
@@ -952,30 +974,31 @@
   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.  On POSIX systems,
+   HAVE_POSIX_MEMALIGN is defined, so we can use posix_memalign and free.
+   Some systems lacks posix_memalign, but provides memalign; for such a
+   systems, we're checking whether pointer returned by memalign can be
+   passed to free.  If this is so, we define HAVE_WORKING_MEMALIGN and
+   use memalign and free.  For native Windows build with MSVC, we use
+   _aligned_malloc and _aligned_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 ! HAVE_POSIX_MEMALIGN && ! HAVE_WORKING_MEMALIGN && ! _MSC_VER
+
+/* 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.  */
@@ -983,6 +1006,7 @@
 #define ABLOCKS_SIZE 16
 
 /* An aligned block of memory.  */
+
 struct ablock
 {
   union
@@ -1008,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) \
@@ -1022,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++)
@@ -1133,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;
@@ -1179,11 +1142,110 @@
 	}
       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 /* ! HAVE_POSIX_MEMALIGN && ! HAVE_WORKING_MEMALIGN && ! _MSC_VER */
+
+/* Here we assume malloc implementation with posix_memalign,
+   or malloc implementation with working memalign, or MSVC.  */
+
+/* Padding to leave at the end of a malloc'd block.  This should help
+   the malloc implementation to allocate aligned blocks consecutively.
+   FIXME: tuned to fit glibc malloc, may be suboptimal for others.  */
+
+#define BLOCK_PADDING sizeof (long)
+
+/* Maximum amount of memory in aligned block.  */
+
+#define BLOCK_BYTES (BLOCK_ALIGN - BLOCK_PADDING)
+
+#endif /* ! HAVE_POSIX_MEMALIGN && ! HAVE_WORKING_MEMALIGN && ! _MSC_VER */
+
+/* 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 HAVE_POSIX_MEMALIGN
+  if (posix_memalign (&val, BLOCK_ALIGN, nbytes))
+    val = NULL;
+#elif HAVE_WORKING_MEMALIGN
+  val = memalign (BLOCK_ALIGN, nbytes);
+#elif _MSC_VER
+  /* Yes, the order of arguments is correct.  */
+  val = _aligned_malloc (nbytes, BLOCK_ALIGN);
+#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 HAVE_POSIX_MEMALIGN || HAVE_WORKING_MEMALIGN
+  free (block);
+#elif _MSC_VER
+  _aligned_free (block);
+#else
+  internal_align_free (block);
+#endif
   MALLOC_UNBLOCK_INPUT;
 }
 
@@ -6671,8 +6733,10 @@
   pure_bytes_used_lisp = pure_bytes_used_non_lisp = 0;
   pure_bytes_used_before_overflow = 0;
 
+#if ! HAVE_POSIX_MEMALIGN && ! HAVE_WORKING_MEMALIGN && ! _MSC_VER
   /* Initialize the list of free aligned blocks.  */
   free_ablock = NULL;
+#endif
 
 #if GC_MARK_STACK || defined GC_MALLOC_CHECK
   mem_init ();

Re: Aligned blocks management: obsolete?

[Stefan Monnier]

> It will be great if someone can help to test this on Windows, OSX, old *BSD
> and other non-GNU/Linux systems; in particular, I believe OSX should have
> some specific aligned allocation stuff, which I'm not aware about.

I'm not completely sure the test is sufficiently thorough to catch all
problems, and more importantly it doesn't test the efficiency
of memalign.


        Stefan

Re: Aligned blocks management: obsolete?

[Dmitry Antipov]

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

On 06/20/2012 04:48 PM, Stefan Monnier wrote:

> I'm not completely sure the test is sufficiently thorough to catch all
> problems, and more importantly it doesn't test the efficiency
> of memalign.

If it's just a matter of configure test, different methods may be used.
For example, attached code checks whether memalign tends to create holes
while allocating (1024 - 8) blocks aligned at 1024-bytes boundary; optimal
pad (BLOCK_PADDING in current code) may be detected with the similar way.

Dmitry

[-- Attachment #2: test-memalign.c --]
[-- Type: text/plain, Size: 1122 bytes --]

/* Simple check whether memalign tends to waste some space.  */

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

int
main (int argc, char *argv[])
{
  int i, j, bad = 0;
  const size_t blksz = 1024, padsz = 8;
  void *p, *prev;

  /* make some chaos in the heap */
  for (i = 0; i <= 1000; i++)
    for (j = 8; j <= 1024; j += 8)
      {
	p = malloc (j);
	if (((i + j) & 7) == 0)
	  free (p);
      }

  /* 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;
    }

  /* make even more chaos with larger chunks */
  for (i = 0; i <= 1000; i++)
    for (j = 8; j <= 1024; j += 8)
      {
	p = malloc (j * 16);
	if (((i + j) & 15) == 0)
	  free (p);
      }

  /* test again */
  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 */
  return bad;
}

Re: Aligned blocks management: obsolete?

[Stefan Monnier]

>> I'm not completely sure the test is sufficiently thorough to catch all
>> problems, and more importantly it doesn't test the efficiency
>> of memalign.
> If it's just a matter of configure test, different methods may be used.
> For example, attached code checks whether memalign tends to create holes
> while allocating (1024 - 8) blocks aligned at 1024-bytes boundary;

You want to mix those allocations with a few others of different sizes,
since some of the problems show up in those cases (e.g.
"memalign(1024); malloc(10); memalign(1024)" might end up wasting 1KB
between the malloc and the second memalign).

> optimal pad (BLOCK_PADDING in current code) may be detected with the
> similar way.

That would be good.


        Stefan

Re: Aligned blocks management: obsolete?

[Eli Zaretskii]

> Date: Wed, 20 Jun 2012 17:54:38 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Paul Eggert <eggert@cs.ucla.edu>, Eli Zaretskii <eliz@gnu.org>, 
>  Emacs development discussions <emacs-devel@gnu.org>
> 
> For example, attached code checks whether memalign tends to create holes
> while allocating (1024 - 8) blocks aligned at 1024-bytes boundary; optimal
> pad (BLOCK_PADDING in current code) may be detected with the similar way.

Is it possible to incorporate such tests into Emacs, and write some
Lisp to execute the tests and report the results?

I'm asking because it's hard to use this test as-is on MS-Windows,
since all of the related functions used by the Windows build are
reimplemented by Emacs sources, they are not in any system library,
and so linking a stand-alone test program is not easy.

TIA

P.S. If memory fragmentation is what you worry about, then doesn't
ralloc.c free us from this, on platforms that use it?

Re: Aligned blocks management: obsolete?

[Dmitry Antipov]

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

On 06/20/2012 09:10 PM, Eli Zaretskii wrote:

>> From: Dmitry Antipov <dmantipov@yandex.ru>
>> CC: Paul Eggert <eggert@cs.ucla.edu>, Eli Zaretskii <eliz@gnu.org>,
>>   Emacs development discussions <emacs-devel@gnu.org>
>>
>> For example, attached code checks whether memalign tends to create holes
>> while allocating (1024 - 8) blocks aligned at 1024-bytes boundary; optimal
>> pad (BLOCK_PADDING in current code) may be detected with the similar way.
>
> Is it possible to incorporate such tests into Emacs, and write some
> Lisp to execute the tests and report the results?

Such a test can be embedded into configure script.  Moreover, I believe
it might be applicable outside of Emacs; IMHO, it would be nice to have
such a test as a part of gnulib.

> I'm asking because it's hard to use this test as-is on MS-Windows,
> since all of the related functions used by the Windows build are
> reimplemented by Emacs sources, they are not in any system library,
> and so linking a stand-alone test program is not easy.

Previous discussions shows my incompetence in Windows-related areas of
Emacs development, so I have no ideas.

> P.S. If memory fragmentation is what you worry about, then doesn't
> ralloc.c free us from this, on platforms that use it?

I don't know how ralloc.c works.  In general, I believe moving/compacting
GC is the only way to reduce fragmentation; since current design makes it
impossible to move/compact Lisp objects, any underlying allocator can't
really help to reduce fragmentation.

As for the lisp_align_{malloc,free}, this cleanup was designed just because
I have some experimental mmap stuff and want to make some simplifications
before introducing even more complexities :-).

Dmitry

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

=== modified file 'configure.in'
--- configure.in	2012-06-13 13:40:48 +0000
+++ configure.in	2012-06-21 04:25:01 +0000
@@ -2698,11 +2698,125 @@
 __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 \
 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, j, bad;
+  void *p, *prev;
+  size_t padsz, blksz = 1024;
+
+  for (padsz = 0; padsz <= 64; padsz += sizeof (long))
+    {
+      bad = 0;
+      /* make some chaos in the heap */
+      for (i = 0; i <= 1000; i++)
+	for (j = 8; j <= 1024; j += 8)
+	  {
+	    p = malloc (j);
+	    if (!p)
+	      return 255;
+	    if (((i + j) & 7) == 0)
+	      free (p);
+	  }
+
+      /* 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 looks poor */
+  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, j, bad;
+  void *p, *prev;
+  size_t padsz, blksz = 1024;
+
+  for (padsz = 0; padsz <= 64; padsz += sizeof (long))
+    {
+      bad = 0;
+      /* make some chaos in the heap */
+      for (i = 0; i <= 1000; i++)
+	for (j = 8; j <= 1024; j += 8)
+	  {
+	    p = malloc (j);
+	    if (!p)
+	      return 255;
+	    if (((i + j) & 7) == 0)
+	      free (p);
+	  }
+
+      /* 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 looks poor */
+  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-06-19 16:56:28 +0000
+++ src/alloc.c	2012-06-21 04:24:33 +0000
@@ -309,9 +309,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
@@ -888,19 +885,37 @@
   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)
 {
-  register void *val;
+  void *val;
 
   MALLOC_BLOCK_INPUT;
 
@@ -908,24 +923,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)
@@ -933,13 +957,11 @@
 #endif
 
   MALLOC_UNBLOCK_INPUT;
-  if (!val && nbytes)
-    memory_full (nbytes);
   return val;
 }
 
-/* Free BLOCK.  This must be called to free memory allocated with a
-   call to lisp_malloc.  */
+/* Free BLOCK.  This must be called to free
+   memory allocated with a call to lisp_malloc.  */
 
 static void
 lisp_free (void *block)
@@ -952,30 +974,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.  */
@@ -983,6 +1008,7 @@
 #define ABLOCKS_SIZE 16
 
 /* An aligned block of memory.  */
+
 struct ablock
 {
   union
@@ -1008,12 +1034,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) \
@@ -1022,94 +1050,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++)
@@ -1133,27 +1110,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;
@@ -1179,11 +1144,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;
 }
 
@@ -6671,8 +6728,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 ();

Re: Aligned blocks management: obsolete?

[Eli Zaretskii]

> Date: Thu, 21 Jun 2012 08:27:14 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: monnier@iro.umontreal.ca, eggert@cs.ucla.edu, emacs-devel@gnu.org
> 
> > P.S. If memory fragmentation is what you worry about, then doesn't
> > ralloc.c free us from this, on platforms that use it?
> 
> I don't know how ralloc.c works.

It hooks into sbrk, and when malloc asks for more memory by calling
sbrk, ralloc.c relocates buffer text trying to free a bug enough
chunk, before it lets the call to sbrk to proceed.

> In general, I believe moving/compacting GC is the only way to reduce
> fragmentation; since current design makes it impossible to
> move/compact Lisp objects, any underlying allocator can't really
> help to reduce fragmentation.

Maybe I don't understand what you mean by move/compact, but aren't
buffer text and data of a Lisp string already designed to support such
moving/compacting?  The pointer to the text is obtained by a second
dereference, so the Lisp object representing buffer and string stays
unmodified when the text is relocated.

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

[Dmitry Antipov]

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

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

Re: Aligned blocks management: obsolete?

[Richard Stallman]

It is desirable to avoid runtime tests in the configure script
for the sake of cross-compilation.

-- 
Dr Richard Stallman
President, Free Software Foundation
51 Franklin St
Boston MA 02110
USA
www.fsf.org  www.gnu.org
Skype: No way! That's nonfree (freedom-denying) software.
  Use Ekiga or an ordinary phone call

Re: Aligned blocks management: obsolete?

[Eli Zaretskii]

> Date: Wed, 20 Jun 2012 10:47:08 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: Emacs development discussions <emacs-devel@gnu.org>
> 
> This code tries to utilize system malloc features and falls back to legacy
> aligned blocks management code if system malloc implementation is unknown,
> broken, or lacks aligned allocation routines.
> 
> It will be great if someone can help to test this on Windows, OSX, old *BSD
> and other non-GNU/Linux systems

What exactly would you like us to test, beyond the fact that the
patched sources compile?

Anyway, I don't understand the motivation for the changes you've done
relative to the previous version.  In particular:

> +#if ! HAVE_POSIX_MEMALIGN && ! HAVE_WORKING_MEMALIGN && ! _MSC_VER

Why only _MSC_VER is being tested here?  This will only catch the MSVC
build of Emacs, but will miss the MinGW (GCC-based) Windows build and
the MS-DOS build.  If you wanted to catch all of them, you should test
DOS_NT instead.

> +#ifdef HAVE_POSIX_MEMALIGN
> +  if (posix_memalign (&val, BLOCK_ALIGN, nbytes))
> +    val = NULL;
> +#elif HAVE_WORKING_MEMALIGN
> +  val = memalign (BLOCK_ALIGN, nbytes);
> +#elif _MSC_VER
> +  /* Yes, the order of arguments is correct.  */
> +  val = _aligned_malloc (nbytes, BLOCK_ALIGN);
> +#else
> +  val = internal_align_alloc (nbytes);
> +#endif

The _MSC_VER part is not right, IMO.  The Windows build, whether MinGW
or MSVC, uses gmalloc.c for its malloc implementation, with sbrk
(implemented in w32heap.c) that calls directly into the VM allocation
APIs, and is thus similar to mmap-based memory allocation on Posix
hosts, in that it doesn't suffer from fragmentation.

By contrast, _aligned_malloc is most probably a very thin wrapper
around MS runtime implementation of malloc (MS documentation says
"_aligned_malloc is based on malloc"), and we certainly don't want to
use that malloc in Emacs, because it will be definitely prone to
severe fragmentation problems.

So, unless I'm missing something, the MS-Windows build (and also the
MS-DOS one) should defined HAVE_POSIX_MEMALIGN and use its
implementation provided by gmalloc.c.  Unless, that is, you think that
gmalloc's implementation of posix_memalign is not good enough, in
which case we will be much better off improving it than switching to
MS's malloc.

Re: Aligned blocks management: obsolete?

[Dmitry Antipov]

On 06/20/2012 09:06 PM, Eli Zaretskii wrote:

> So, unless I'm missing something, the MS-Windows build (and also the
> MS-DOS one) should defined HAVE_POSIX_MEMALIGN and use its
> implementation provided by gmalloc.c.  Unless, that is, you think that
> gmalloc's implementation of posix_memalign is not good enough, in
> which case we will be much better off improving it than switching to
> MS's malloc.

Oops, I was pretty sure that native MSVC build uses MS malloc :-(.

BTW, is it possible to cross-compile Emacs for MS-Windows with mingw?

Dmitry

Re: Aligned blocks management: obsolete?

[Eli Zaretskii]

> Date: Thu, 21 Jun 2012 07:30:49 +0400
> From: Dmitry Antipov <dmantipov@yandex.ru>
> CC: emacs-devel@gnu.org
> 
> BTW, is it possible to cross-compile Emacs for MS-Windows with mingw?

You mean, on a Posix host?  I doubt that, since the configure script
does not support the MinGW target, and the various Makefile.in files
were never tested to DTRT for MinGW.  Volunteers to fix that are
welcome.

Re: Aligned blocks management: obsolete?

[Wolfgang Jenkner]

On Wed, Jun 20 2012, Dmitry Antipov wrote:

> This code tries to utilize system malloc features and falls back to legacy
> aligned blocks management code if system malloc implementation is unknown,
> broken, or lacks aligned allocation routines.

I think the following trivial fix is needed (relative to your patch):

Wolfgang

diff --git a/src/alloc.c b/src/alloc.c
index 15cefb5..4cd3a32 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -894,7 +894,7 @@ void *lisp_malloc_loser EXTERNALLY_VISIBLE;
 /* Nonzero if the memory at ADDR can be
    addressed thru a Lisp object's pointer.  */
 
-static inline void
+static inline int
 verify_address (char *addr)
 {
   Lisp_Object obj;

Re: Aligned blocks management: obsolete?

[Dmitry Antipov]

On 06/20/2012 09:59 PM, Wolfgang Jenkner wrote:

> I think the following trivial fix is needed (relative to your patch):

Argh, sure. Thanks.

Dmitry

Re: Aligned blocks management: obsolete?

[Paul Eggert]

On 06/19/2012 09:51 AM, Dmitry Antipov wrote:
> this cleanup assumes that every malloc implementation
> has reasonably efficient posix_memalign or memalign at least.

memalign might be dicey, as Stefan noted.
The gnulib documentation
<www.gnu.org/software/gnulib/manual/html_node/posix_005fmemalign.html>
says posix_memalign is missing on some plausible Emacs porting targets,
and the gnulib implementation of pagealign_alloc says that
posix_memalign often wastes an entire memory page per call
(don't know the details about that).

Re: Aligned blocks management: obsolete?

[Stefan Monnier]

> Is it still required to maintain the cache of aligned blocks
> to workaround poor malloc behavior? I believe an attached
> example should perform well (i.e. allocate ~4K blocks without
> ~4K holes between them) on top of any non-ancient glibc (no
> ideas about other system malloc implementations, BTW).

I'm not sure exactly what you're suggesting we change.
If you're talking about BLOCK_PADDING (which we don't actually use
right now since it defaults to 0), then we could probably just remove
it, but I'm not sure what would be the benefit (other than the handful
of source lines it removes, of course).


        Stefan