What precautions should I take to make a memory pool that does not invoke undefined behavior?

Question

My initial problem is that I have, on a project, several objects which share a lifetime (i.e., once I free one of them, I'll free them all), then I wanted to allocate a single block of memory. I have arrays of three different object types, struct foo, void *, and char. At first I wanted to malloc() a block like this:

// +---------------+---------+-----------+---------+---------+
// | struct foo[n] | padding | void *[m] | padding | char[o] |
// +---------------+---------+-----------+---------+---------+

But then... how could I accomplish this without invoking undefined behavior? I.e., respecting type aliasing rules, aligment... How to properly calculate the memory block size, declare the memory block (with its effective type), and how to properly get pointers to all three sections within it portably?

(I do understand I could malloc() 3 blocks, which would result in three free(), but I'd like to know how to do it with a single block while still well-behaved.)

I'd like to extend my problem to a more general question: what precautions should one take to implement a memory pool for objects with arbitrary sizes and alignment while keeping the program well-behaved? (Assuming it is possible to implement it without invoking undefined behavior.)

Answer 1

However hard you try, it's not possible to implement malloc in pure C.

You always end up violating strict aliasing at some point. For the avoidance of doubt, using a char buffer that doesn't have dynamic storage duration will also violate strict aliasing rules. You would also have to make sure that any pointer returned has an appropriate alignment.

If you're happy to tie yourself down to a particular platform then you may as well turn to that particular implementation of malloc for inspiration.

But why not consider writing a stub function which calls malloc and also builds up a table of other allocated objects? You could even implement some kind of observer / notify framework. Another starting point could be well-known garbage collectors that have been written in C.

Answer 2

As said in another answer, you can't reimplement malloc within C itself. The reason is that you can't generate objects that don't have an effective type without malloc.

But for your application you don't need this, you can use malloc or similar, see below, to have one large block of memory without problems.

If you have such a large block you must know how to place the objects inside this block. The major problem here is alignment, you have to place all your objects on boundaries that correspond to their minimal alignment requirements.

Since C11, the alignment of types can be obtained with the _Alignof operator, and overaligned memory can be requested with aligned_alloc.

Put all this together this reads:

• compute the lcm of all alignments of your types
• with aligned_alloc request enough memory that is aligned at that value
• place all your objects on multiples of that alignment

Aliasing then isn't a problem if your are starting with a typeless object that you receive through a void* pointer. Each part of that large object has the effective type of with which you have written into, see my recent blog entry.

The relevant part of the C standard is 6.5 p6:

The effective type of an object for an access to its stored value is the declared type of the object, if any.87) If a value is stored into an object having no declared type through an lvalue having a type that is not a character type, then the type of the lvalue becomes the effective type of the object for that access and for subsequent accesses that do not modify the stored value. If a value is copied into an object having no declared type using memcpy or memmove, or is copied as an array of character type, then the effective type of the modified object for that access and for subsequent accesses that do not modify the value is the effective type of the object from which the value is copied, if it has one. For all other accesses to an object having no declared type, the effective type of the object is simply the type of the lvalue used for the access.

Here the "object with no declared type" is an object (or subobject) allocated by malloc or similar. It clearly says that such objects can be written to with any type at any time and that this than changes the effective type to the desired.

Answer 3

By knowing the size of the union of the 3 types a more efficient allocation can occur.

union common {
  struct foo f;
  void * ptr;
  char ch;
};

void *allocate3(struct foo **f, size_t m, void **ptr, size_t n, char **ch,
    size_t o) {
  size_t u_sz = sizeof (union common);
  size_t f_sz = sizeof *f * m;
  size_t f_cnt = (f_sz + u_sz - 1)/u_sz;
  size_t p_sz = sizeof *ptr * n;
  size_t p_cnt = (p_sz + u_sz - 1)/u_sz;
  size_t c_sz = sizeof *ch * o;
  size_t c_cnt = (c_sz + u_sz - 1)/u_sz;
  size_t sum = f_cnt + p_cnt + c_cnt;
  union common *u = malloc(sum * u_sz);
  if (u) {
    *f = &u[0].f;
    *ptr = &u[f_cnt].ptr;
    *ch = &u[f_cnt + c_cnt].ch;
  }
  return u;
}

This way, each of the 3 array begin on a union boundary , so alignment issues are met. By adjusting the space of each array to be a multiple of size of the union, less wasted space than first answer yet meets OP posted goals.

A tad wasteful is struct foo is large, yet o is small. Could use following as further improvement. There is no need for padding after the last array.

malloc((f_cnt + p_cnt) * u_sz + c_cz);

---

Further thought on squeezing the allocation. Each subsequent "count-of-union elements" can use a different union that omits the earlier types and so on. When reaching the end - that is the gist of the idea just above, the last array only needs to depend on the last type. This makes code more complicated (prone to error) yet does gain increased space efficiency without aliments issues, etc. Some coding ideas follow

union common_last2 {
  // struct foo f;
  void * ptr;
  char ch;
};

size_t u2_sz = sizeof (union common_last2);
size_t p_cnt = (p_sz + u2_sz - 1)/u2_sz;

... malloc(f_cnt*usz + p_cnt*u2_sz + c_cz);

*ch = tbd;

Answer 4

First off, be sure to use -fno-strict-aliasing or whatever the equivalent is on your compiler. Otherwise even if all alignments are satisfied a compiler may use aliasing rules to overlap different uses of the same memory block.

I doubt this is consistent with the intention of the Standard's authors, but given optimizers can be so aggressive that the only way to implement type-agnostic memory pools safely is to disable type-based aliasing analysis. The authors of the Standard wanted to avoid branding as non-compliant some compilers that used type-based aliasing. Further, they figured they could defer to compiler writers' judgment about how to recognize and handle cases where aliasing was likely. They identified cases where compiler writers might not think it was necessary to recognize aliasing (e.g. between signed and unsigned types) but otherwise expected compiler writers to exercise reasonable judgment. I see no evidence that they intended their list of allowable cases to be regarded as exhaustive even on platforms where other forms of aliasing would be useful.

Further, no matter how carefully one abides by the Standard, there's no guarantee that compilers apply breaking "optimizations" anyway. At least as of gcc 6.2 there are aliasing bugs that will break code that uses storage as type X, writes it as Y, reads it as Y, writes that same value as X, and reads the storage as X--behavior which is 100% defined under the Standard.

If aliasing is taken care of (e.g. using the indicated flag), and you know the worst-case alignment requirement for your system, defining storage for the pool is easy:

union
{
   char [POOL_BLOCK_SIZE] dat;
   TYPE_WITH_WORST_ALIGNMENT align;
} memory_pool[POOL_BLOCK_COUNT];

Unfortunately, the Standard provides no way to avoid type-based aliasing problems even if all platform-dependent alignment issues are taken care of.

Answer 5

To answer one of OP's questions

how could I accomplish this (wanted to malloc() a block like this) without invoking undefined behavior?

A space inefficient approach. Allocate a union of the types. Reasonable if the size needed of the smaller types is not too large.

union common {
  struct foo f;
  void * ptr;
  char ch;
};

void *allocate3(struct foo **f, size_t m, void **ptr, size_t n, char **ch,
    size_t o) {
  size_t sum = m + n + o;
  union common *u = malloc(sizeof *u * sum);
  if (u) {
    *f = &u[0].f;
    *ptr = &u[m].ptr;
    *ch = &u[m + n].ch;
  }
  return u;
}

void sample() {
  struct foo *f;
  void *ptr;
  char *ch;
  size_t m, n, o;
  void *base = allocate3(&f, m, &ptr, n, &ch, o);
  if (base) {
    // use data
  }
  free(base);
}