[libcxxabi] Fix alignment of pointers returned by fallback_malloc

[simon_tatham]

Summary

This aligns the `heap[] array in fallback_malloc.cpp` to ensure
that it can be safely cast to `heap_node*`, and also adjusts the
allocation algorithm to ensure that every allocated block has the
alignment requested by `__attribute__((aligned))`, by putting the
block's `heap_node` header 4 bytes before an aligned address.

Patch originally by Eric Fiselier: this is an updated version of
D12669, which was never landed.

[simon_tatham]

CI fix: tell test_fallback_malloc_pass.cpp not to try to run in C++03 mode, which won't work now that the library source file it includes uses alignof.

[miyuki]

libcxxabi/src/fallback_malloc.cpp

105

(A + sizeof(heap_node)) % RequiredAlignment

[simon_tatham]

Corrected that comment.

[miyuki]

The patch LGTM, but since this is libc++abi, we need approval from the code owners.

[simon_tatham]

Ping. Can someone in the libc++abi blocking reviewer group take a look at this patch, please?

[jroelofs]

@EricWF @ldionne ping

[simon_tatham]

Ping again. If I'm reading the libc++ group members page right, this patch needs to be looked at by at least one of: @EricWF @erik.pilkington @ldionne @mclow.lists @phosek @compnerd @urnathan . Is there somewhere else I should be asking, to bring it to the attention of the right people?

libcxxabi/src/fallback_malloc.cpp

 
 #include <__threading_support>
 #ifndef _LIBCXXABI_HAS_NO_THREADS
 #if defined(__ELF__) && defined(_LIBCXXABI_LINK_PTHREAD_LIB)
 #pragma comment(lib, "pthread")
 #endif
 #endif
 
+#include <assert.h>
 #include <stdlib.h> // for malloc, calloc, free
 #include <string.h> // for memset
 #include <new> // for std::__libcpp_aligned_{alloc,free}
 
 //  A small, simple heap manager based (loosely) on
 //  the startup heap manager from FreeBSD, optimized for space.
 //
 //  Manages a fixed-size memory pool, supports malloc and free only.

 };
 
 static const size_t HEAP_SIZE = 512;
 char heap[HEAP_SIZE] __attribute__((aligned));
 
 typedef unsigned short heap_offset;
 typedef unsigned short heap_size;
 
+// On both 64 and 32 bit targets heap_node should have the following properties
+// Size: 4
+// Alignment: 2
 struct heap_node {
   heap_offset next_node; // offset into heap
   heap_size len;         // size in units of "sizeof(heap_node)"
 };
 
+// All pointers returned by fallback_malloc must be at least aligned
+// as RequiredAligned. Note that RequiredAlignment can be greater than
+// alignof(std::max_align_t) on 64 bit systems compiling 32 bit code.
+struct FallbackMaxAlignType {
+} __attribute__((aligned));
+const size_t RequiredAlignment = alignof(FallbackMaxAlignType);
+
+static_assert(alignof(FallbackMaxAlignType) % sizeof(heap_node) == 0,
+              "The required alignment must be evenly divisible by the sizeof(heap_node)");
+
+// The number of heap_node's that can fit in a chunk of memory with the size
+// of the RequiredAlignment. On 64 bit targets NodesPerAlignment should be 4.
+const size_t NodesPerAlignment = alignof(FallbackMaxAlignType) / sizeof(heap_node);
+
 static const heap_node* list_end =
     (heap_node*)(&heap[HEAP_SIZE]); // one past the end of the heap
 static heap_node* freelist = NULL;
 
 heap_node* node_from_offset(const heap_offset offset) {
   return (heap_node*)(heap + (offset * sizeof(heap_node)));
 }
 
 heap_offset offset_from_node(const heap_node* ptr) {
   return static_cast<heap_offset>(
       static_cast<size_t>(reinterpret_cast<const char*>(ptr) - heap) /
       sizeof(heap_node));
 }
 
+// Return a pointer to the first address, 'A', in `heap` that can actually be
+// used to represent a heap_node. 'A' must be aligned so that
+// '(A + sizeof(heap_node)) % RequiredAlignment == 0'. On 64 bit systems this
+// address should be 12 bytes after the first 16 byte boundary.
+heap_node* getFirstAlignedNodeInHeap() {
+  heap_node* node = (heap_node*)heap;
+  const size_t alignNBytesAfterBoundary = RequiredAlignment - sizeof(heap_node);
+  size_t boundaryOffset = reinterpret_cast<size_t>(node) % RequiredAlignment;
+  size_t requiredOffset = alignNBytesAfterBoundary - boundaryOffset;
+  size_t NElemOffset = requiredOffset / sizeof(heap_node);
+  return node + NElemOffset;
+}
+
 void init_heap() {
-  freelist = (heap_node*)heap;
+  freelist = getFirstAlignedNodeInHeap();
   freelist->next_node = offset_from_node(list_end);
-  freelist->len = HEAP_SIZE / sizeof(heap_node);
+  freelist->len = static_cast<heap_size>(list_end - freelist);
 }
 
 //  How big a chunk we allocate
 size_t alloc_size(size_t len) {
   return (len + sizeof(heap_node) - 1) / sizeof(heap_node) + 1;
 }
 
 bool is_fallback_ptr(void* ptr) {
   return ptr >= heap && ptr < (heap + HEAP_SIZE);
 }
 
 void* fallback_malloc(size_t len) {
   heap_node *p, *prev;
   const size_t nelems = alloc_size(len);
   mutexor mtx(&heap_mutex);
 
   if (NULL == freelist)
     init_heap();
 
   //  Walk the free list, looking for a "big enough" chunk
   for (p = freelist, prev = 0; p && p != list_end;
        prev = p, p = node_from_offset(p->next_node)) {
 
-    if (p->len > nelems) { //  chunk is larger, shorten, and return the tail
+    // Check the invariant that all heap_nodes pointers 'p' are aligned
+    // so that 'p + 1' has an alignment of at least RequiredAlignment
+    assert(reinterpret_cast<size_t>(p + 1) % RequiredAlignment == 0);
+
+    // Calculate the number of extra padding elements needed in order
+    // to split 'p' and create a properly aligned heap_node from the tail
+    // of 'p'. We calculate aligned_nelems such that 'p->len - aligned_nelems'
+    // will be a multiple of NodesPerAlignment.
+    size_t aligned_nelems = nelems;
+    if (p->len > nelems) {
+      heap_size remaining_len = static_cast<heap_size>(p->len - nelems);
+      aligned_nelems += remaining_len % NodesPerAlignment;
+    }
+
+    // chunk is larger and we can create a properly aligned heap_node
+    // from the tail. In this case we shorten 'p' and return the tail.
+    if (p->len > aligned_nelems) {
       heap_node* q;
-
-      p->len = static_cast<heap_size>(p->len - nelems);
+      p->len = static_cast<heap_size>(p->len - aligned_nelems);
       q = p + p->len;
       q->next_node = 0;
-      q->len = static_cast<heap_size>(nelems);
-      return (void*)(q + 1);
+      q->len = static_cast<heap_size>(aligned_nelems);
+      void* ptr = q + 1;
+      assert(reinterpret_cast<size_t>(ptr) % RequiredAlignment == 0);
+      return ptr;
     }
 
-    if (p->len == nelems) { // exact size match
+    // The chunk is the exact size or the chunk is larger but not large
+    // enough to split due to alignment constraints.
+    if (p->len >= nelems) {
       if (prev == 0)
         freelist = node_from_offset(p->next_node);
       else
         prev->next_node = p->next_node;
       p->next_node = 0;
-      return (void*)(p + 1);
+      void* ptr = p + 1;
+      assert(reinterpret_cast<size_t>(ptr) % RequiredAlignment == 0);
+      return ptr;
     }
   }
   return NULL; // couldn't find a spot big enough
 }
 
 //  Return the start of the next block
 heap_node* after(struct heap_node* p) { return p + p->len; }
 

libcxxabi/test/test_fallback_malloc.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include <cstdio>
 #include <deque>
+#include <cassert>
 
 #include <__threading_support>
 
+// UNSUPPORTED: c++03
 // UNSUPPORTED: modules-build && no-threads
 
 // Necessary because we include a private source file of libc++abi, which
 // only understands _LIBCXXABI_HAS_NO_THREADS.
 #include "test_macros.h"
 #ifdef TEST_HAS_NO_THREADS
 # define _LIBCXXABI_HAS_NO_THREADS
 #endif
 
 typedef std::deque<void *> container;
 
 // #define  DEBUG_FALLBACK_MALLOC
 #define INSTRUMENT_FALLBACK_MALLOC
 #include "../src/fallback_malloc.cpp"
 
+void assertAlignment(void* ptr) { assert(reinterpret_cast<size_t>(ptr) % alignof(FallbackMaxAlignType) == 0); }
+
 container alloc_series ( size_t sz ) {
     container ptrs;
     void *p;
 
-    while ( NULL != ( p = fallback_malloc ( sz )))
-        ptrs.push_back ( p );
+    while (NULL != (p = fallback_malloc(sz))) {
+      assertAlignment(p);
+      ptrs.push_back(p);
+    }
     return ptrs;
 }
 
 container alloc_series ( size_t sz, float growth ) {
     container ptrs;
     void *p;
 
     while ( NULL != ( p = fallback_malloc ( sz ))) {
-        ptrs.push_back ( p );
-        sz *= growth;
+      assertAlignment(p);
+      ptrs.push_back(p);
     }
 
     return ptrs;
 }
 
 container alloc_series ( const size_t *first, size_t len ) {
     container ptrs;
     const size_t *last = first + len;
     void * p;
 
     for ( const size_t *iter = first; iter != last; ++iter ) {
         if ( NULL == (p = fallback_malloc ( *iter )))
             break;
+        assertAlignment(p);
         ptrs.push_back ( p );
     }
 
     return ptrs;
 }
 
 void *pop ( container &c, bool from_end ) {
     void *ptr;