>Number:         5269
>Category:       lib
>Synopsis:       bug in memalign(3) (gnumalloc)
>Confidential:   no
>Severity:       non-critical
>Priority:       low
>Responsible:    lib-bug-people (Library Bug People)
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Wed Apr  8 15:50:00 1998
>Last-Modified:
>Originator:     Jochen Pohl
>Organization:
EasternGraphics GmbH
>Release:        1.3.1
>Environment:
System: NetBSD ariadne.EasternGraphics.com 1.3.1 NetBSD 1.3.1 (ARIADNE_DISKLESS) #0: Thu Apr 2 23:06:37 MEST 1998 root@ariadne.EasternGraphics.com:/usr/src/sys/arch/i386/compile/ARIADNE_DISKLESS i386

>Description:
The current implementation of memalign() in gnumalloc has two serious
errors which make it totally useless.

The first error is in the calculation of the size of the memory block
allocated with malloc(): the size is rounded up to a multiple of the
requested alignment. A size which is already a multiple of the alignment
is not changed. If malloc() returns a block which is not properly aligned
there is no extra space available to return an aligned pointer which is
followed by the requested amount of free memory.

The item in the list of aligned blocks is prepended to the list even if
it has not been allocated during this call of memalign(). This results
in a cycle in the list and in lost list entries. It should either
be prepended only if it is newly allocated or it should be removed from
it's old position in the list.

>How-To-Repeat:
Run the following program. It should core dump with the current
implementation.

#include <stdlib.h>

void *memalign(size_t, size_t);

int
main(int argc, char *argv[])
{
	struct {
		void	*ptr;
		size_t	size;
		unsigned pattern;
	} *allocated;
	unsigned maxalloc, totalloc, slot, alignment;
	unsigned pattern, *p, *pe;

	maxalloc = 100;
	allocated = calloc(maxalloc, sizeof (struct alloc));
	totalloc = 0;
	while (totalloc < 1000) {
		slot = rand() % maxalloc;
		if (allocated[slot].ptr != NULL) {
			pattern = allocated[slot].pattern;
			p = allocated[slot].ptr;
			pe = (void *)((char *)p + allocated[slot].size);
			while (p < pe && *p == pattern)
				p++;
			if (p != pe)
				abort();
			free(allocated[slot].ptr);
			allocated[slot].ptr = NULL;
		} else {
			allocated[slot].size = (rand() & 0xffff) << 4;
			allocated[slot].size ^= rand() & 0xfffc;
			allocated[slot].pattern = pattern =
			    (rand() << 16) ^ rand();
			alignment = 2 << (rand() & 0xf);
			p = allocated[slot].ptr = memalign(
			    alignment, allocated[slot].size);
			if (p == NULL)
				abort();
			if (((long)p & (alignment - 1)) != 0)
				abort();
			pe = (void *)((char *)p + allocated[slot].size);
			while (p < pe)
				*p++ = pattern;
			totalloc++;
		}
	}

	return (0);
}

>Fix:

--- .%%memalign.c%%	Wed Apr  8 21:34:44 1998
+++ memalign.c	Wed Apr  8 23:06:43 1998
@@ -26,16 +26,21 @@
      size_t size;
 {
   __ptr_t result;
-  unsigned long int adj;
+  __ptr_t aligned;
 
-  size = ((size + alignment - 1) / alignment) * alignment;
+  /* In the worst case we waste alignment - 1 bytes */
+  size = size + alignment - 1;
 
   result = malloc (size);
   if (result == NULL)
     return NULL;
-  adj = (unsigned long int) ((unsigned long int) ((char *) result -
-						(char *) NULL)) % alignment;
-  if (adj != 0)
+
+  /*
+   * Round pointer up to aligned address. Alignment is expected to
+   * be a power of two, so we don't need to use %.
+   */
+  aligned = (__ptr_t)(((long)result + alignment - 1) & ~(alignment - 1));
+  if (result != aligned)
     {
       struct alignlist *l;
       for (l = _aligned_blocks; l != NULL; l = l->next)
@@ -50,11 +55,11 @@
 	      free (result);
 	      return NULL;
 	    }
+          l->next = _aligned_blocks;
+          _aligned_blocks = l;
 	}
       l->exact = result;
-      result = l->aligned = (char *) result + alignment - adj;
-      l->next = _aligned_blocks;
-      _aligned_blocks = l;
+      result = l->aligned = aligned;
     }
 
   return result;
>Audit-Trail:
>Unformatted: