4
\$\begingroup\$

Although C11 introduced aligned_alloc( alignment, size ), there is no support for aligned reallocation (AFAIK). The memory_resource structure that follows and its related functions provide such functionality.

I wanted to provide something with as little overhead as possible, which is why there's close to no error checking done. I envisioned this structure being wrapped in another structure that does do safety checks if that is required. Is this reasonable design?

memory_resource features:

  • Support for over-aligned dynamic allocation.
  • Can be resized.
  • Can be realigned.

memory_resource_xxx function family pre-conditions:

  • Pointer to struct memory_resource arguments shall not be NULL or modified outside of these functions.
  • Alignment arguments shall be powers of 2.

Note: My library does not have aligned_alloc( alignment, size ).

Sample usage:

#include <stdio.h>
#include <stdint.h>
#include <assert.h>

int main()
{
    struct memory_resource mr;
    size_t align = 32;
    size_t size = 4000;

    if ( memory_resource_initialize( &mr, align, size ) )
        fprintf( stderr, "unable to allocate memory." );

    assert( (uintptr_t)mr.aligned_ptr % align == 0 );
    assert( mr.size == size );

    if ( memory_resource_resize( &mr, size * 2 ) )
        fprintf( stderr, "unable to allocate memory." );

    assert( (uintptr_t)mr.aligned_ptr % align == 0 );
    assert( mr.size == size * 2 );

    align = 64;
    if ( memory_resource_realign( &mr, align ) )
        fprintf( stderr, "unable to allocate memory." );

    assert( (uintptr_t)mr.aligned_ptr % align == 0 );

    if ( memory_resource_resize( &mr, 1024 ) )
        fprintf( stderr, "strange" );

    assert( (uintptr_t)mr.size == 1024 );
    assert( (uintptr_t)mr.aligned_ptr % align == 0 );
    memory_resource_free( &mr );
}

memory_resource.h

#ifndef MEMORY_RESOURCE_20160823_H
#define MEMORY_RESOURCE_20160823_H

#include <stddef.h>

/**
 * @struct an aligned, dynamically allocated memory resource
 */
struct memory_resource
{
    void* block;
    void* aligned_ptr;
    size_t align;
    size_t size;
    size_t extra_block_size;
};

/**
 * @brief initializes the specified memory resource to the specified alignment and size
 * @param dst: pointer to the memory resource to be initialized
 * @param align: alignment boundary of the memory resource
 * @param size: size, in bytes, of the memory resource
 * @return 0 if the memory resource was allocated successfully, 1 otherwise.
 */
int memory_resource_initialize( struct memory_resource* dst,
    size_t const align, size_t const size );

/**
 * @brief frees the specified memory resource
 * @param dst: pointer to the memory resource to be freed
 */
void memory_resource_free( struct memory_resource* dst );

/**
 * @brief resizes a memory resource
 * @param dst: pointer to the memory resource to be resized
 * @param size: new size of the memory resource
 * @return 0 if the memory resource was resized, 1 otherwise
 */
int memory_resource_resize( struct memory_resource* dst, size_t const size );

/**
 * @brief realigns a memory resource; might require reallocation in order
          to maintain proper alignment when align > ( *dst ).align
 * @param dst: pointer to the memory resource to be realigned
 * @param align: new alignment boundary of the memory resource
 * @return 0 if the memory resource was realigned, 1 if the memory resource
 *         is unable to allocate enough space to be properly aligned
 */
int memory_resource_realign( struct memory_resource* dst, size_t const align );

#endif // MEMORY_RESOURCE_20160823_H

memory_resource.c

#include "memory_resource.h"
#include <stdlib.h>
#include <stdint.h>

// source: http://stackoverflow.com/a/9194117/2296177
#define make_aligned( block, align )\
(void*)( ( (uintptr_t)block + align - 1 ) & ~( align - 1 ) )

typedef struct
{
    void* aligned_ptr;
    size_t padding;
} align_calc_t;

static align_calc_t alignment_calculation( void* block, size_t const align )
{
    align_calc_t result;
    result.aligned_ptr = make_aligned( block, align );
    result.padding = (uintptr_t)result.aligned_ptr - (uintptr_t)block;
    return result;
}

int memory_resource_initialize( struct memory_resource* dst,
    size_t const align, size_t const size )
{
    void* block = malloc( align + size );
    if ( block )
    {
        dst->block = block;
        dst->aligned_ptr = make_aligned( block, align );
        dst->align = align;
        dst->size = size;
        dst->extra_block_size = align;
        return 0;
    }
    return 1;
}

void memory_resource_free( struct memory_resource* dst )
{
    free( dst->block );
}

int memory_resource_resize( struct memory_resource* dst, size_t const size )
{
    void* block = realloc( dst->block, size + dst->align );
    if ( block )
    {
        if ( block != dst->block )
        {
            dst->block = block;
            dst->aligned_ptr = make_aligned( block, dst->align );
        }
        dst->size = size;
        return 0;
    }
    return 1;
}

int memory_resource_realign( struct memory_resource* dst, size_t const align )
{
    if ( align < dst->align )
    {
        dst->align = align;
        return 0;
    }
    else if ( align > dst->align )
    {
        align_calc_t ac = alignment_calculation( dst->block, align );
        if ( ac.padding > dst->extra_block_size )
        {
            void* block = realloc( dst->block, align + dst->size );
            if ( block )
            {
                dst->block = block;
                dst->aligned_ptr = make_aligned( block, align );
                dst->align = align;
                dst->extra_block_size = align;
                return 0;
            }
            return 1;
        }
        else
        {
            dst->aligned_ptr = ac.aligned_ptr;
            return 0;
        }
    }
    return 1;
}
\$\endgroup\$
1
\$\begingroup\$
  • Bug

    The padding between block and aligned_ptr depends on how well block was aligned. There is no guarantee that the padding after original malloc is the same as the padding after realloc, so memory_resource_resize may copy the client data to a misaligned location, and therefore the aligned_ptr will not point the start of client data.

  • Realignment

    Consider the scenario:

    memory_resource_initialize(&mr, 32, ...);
    memory_resource_realign(&mr, 4);
    memory_resource_realign(&mr, 8);
    

    Since the first realignment is a no-op, the resource is still happily aligned on a 32-byte boundary. The second realignment doesn't need to do anything, but reallocation will still occur.

  • Interface

    • make_aligned assumes that align is a power of 2, which imposes an extra burden to the client. I recommend you change it to exponent, that is align 5 shall requests a 32-byte boundary.

    • I don't think it is a good idea to expose a memory_resource type to the client at all. I recommend you reuse the "wasted" space for bookkeeping. Consider:

      void * aligned_malloc(size_t const size, size_t const align)
      {
          void * memory = malloc(size + align);
          void * data = make_aligned(memory, align);
          if (memory == data) {
              data = ((char *) memory) + align;
          }
      
          // Now you have enough bytes in front of data to accommodate the
          // larges scalar, and it is aligned nicely. Store the
          // metadata here.
      
          size_t * prefix = (size_t *) (((char *) data - sizeof(size));
          * prefix = (char *) data - (char *) memory;
          return data;
      }
      

    Now given the pointer returned by aligned_malloc, other functions (e.g. aligned_realloc and aligned_free) may easily recover the memory pointer, and safely free or realloc it.

  • Portability

    The Standard guarantees that if you convert a void pointer to uintptr_t, and convert it back to void pointer, the result will compare equal to the original. Unfortunately, nothing else is guaranteed. It is not defined what uintptr_t is converted to once it has undergone arithmetic operations.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I'm not sure I quite understand what you mean by "re-use the wasted space", since that is not constant. It depends on required alignment and the integral value of the pointer returned by malloc(). \$\endgroup\$ – user2296177 Aug 24 '16 at 2:11
  • \$\begingroup\$ The resource was not meant to deal with memcpy() like behavior which is why it's missing where it would be needed. The issue you've brought up about realigning is very important, thank you. \$\endgroup\$ – user2296177 Aug 24 '16 at 5:39
  • \$\begingroup\$ 1) size_t * prefix = (size_t *) (((char *) data - sizeof(size)); relies on sizeof(size) >= align which may not be true. 2) Pedantic: size + align may overflow. \$\endgroup\$ – chux - Reinstate Monica Aug 24 '16 at 22:57
1
\$\begingroup\$

On design

The original intent was unclear:

  1. A memory resource does not worry itself about data that might exist in its buffer; it is up to the user to ensure proper data copying behaviour.
  2. Due to the previous point, a memory resource will cause memory leaks on resize and realignment. Since it can't know whether data is in its buffer, it cannot free the data.
  3. A new simple structure that manages a memory resource is ideal (I might say required), but I've not provided it in this post.

Due to 2., this is what proper use looks like:

void memcpy_resize_example( struct memory_resource* dst, size_t const size )
{
    void* old_block = dst->block;
    void* old_aligned_ptr = dst->aligned_ptr;
    size_t const old_size = dst->size;
    if ( memory_resource_resize( dst, size ) )
    {
        /* error handling */
    }
    memcpy( dst->aligned_ptr, old_aligned_ptr, old_size );
    free( old_block );
}

Similar steps must be taken for realignment, which is why I classify 3. as required.

Taking advantage of max_align_t

From http://en.cppreference.com/w/c/types/max_align_t:

Pointers returned by allocation functions such as malloc are suitably aligned for any object, which means they are aligned at least as strict as max_align_t.

For an alignment a, there's no need to allocate extra memory if a <= alignof(max_align_t). All functions except for memory_resource_free( dst ) must be modified.

Key points:

  • All usage of realloc( block, size ) has been removed. It should now be clear that no memcpy( dst, src, size ) ever takes place. It is clear that copying falls on the user, as struct memory_resource cannot know whether its buffer contains actual data or not.
  • It makes no sense to ever align below alignof( max_align_t ).
  • Extra space is only required for alignments greater than alignof( max_align_t ).
  • I posted this question too early/without the necessary self-examination.

The following is added to memory_resource.c:

#include <stdalign.h>
#define MALLOC_MIN_ALIGN alignof( max_align_t )

Modified memory_resource_initialize( dst, align, size )

Copying of members can be done a number of ways. I asked a question about this issue here: https://stackoverflow.com/q/39137029/2296177. I've chosen to simply write everything out.

int memory_resource_initialize( struct memory_resource* dst,
    size_t const align, size_t const size )
{
    if ( align > MALLOC_MIN_ALIGN )
    {
        void* block = malloc( align + size );
        if ( block )
        {
            dst->block = block;
            dst->aligned_ptr = make_aligned( block, align );
            dst->align = align;
            dst->extra_block_size = align;
            dst->size = size;
            return 0;
        }
        return 1;
    }
    else
    {
        void* block = malloc( size );
        if ( block )
        {
            dst->block = block;
            dst->aligned_ptr = block;
            dst->align = MALLOC_MIN_ALIGN;
            dst->extra_block_size = 0;
            dst->size = size;
            return 0;
        }
        return 1;
    }
}

Modified memory_resource_resize( dst, size )

dst->align > MALLOC_MIN_ALIGN has already been computed by memory_resource_initialize( dst, align, size ). Adding another member to manage would add needless complexity and it would be a really bad case of premature optimization.

int memory_resource_resize( struct memory_resource* dst, size_t const size )
{
    if ( dst->align > MALLOC_MIN_ALIGN )
    {
        void* new_block = malloc( size + dst->align );
        if ( new_block )
        {
            dst->block = new_block;
            dst->aligned_ptr = memcpy(
                make_aligned( new_block, dst->align ), dst->aligned_ptr, dst->size );
            dst->size = size;
            return 0;
        }
        return 1;
    }
    else
    {
        void* new_block = malloc( size );
        if ( new_block )
        {
            dst->block = new_block;
            dst->aligned_ptr = memcpy( new_block, dst->aligned_ptr, dst->size );
            dst->size = size;
            return 0;
        }
        return 1;
    }
}

Modified memory_resource_realign( dst, align )

This new scheme will not ever realign to an alignment that is less strict. This implies that there will be space wasted (not much) if some user reuses an over-aligned struct memory_resource. The previous use case should be rare; it might be prudent to provide some sort of force_realign( dst, align ) function, however.

The following function is not a general purpose public API force realign; it is for use by the existing realign function (its declaration and definition is in memory_resource.c).

static int memory_resource_forced_realign( struct memory_resource* dst, size_t const align )
{
    void* new_block = malloc( align + dst->size );
    if ( new_block )
    {
        dst->block = new_block;
        dst->aligned_ptr = make_aligned( new_block, align );
        dst->align = align;
        dst->extra_block_size = align;
        return 0;
    }
    return 1;
}

In addition, it makes more sense to return 0 (success) even if realignment turns out to be a no-op with this change (debatable?), so that users know (by testing the return) that the memory resource is aligned to their liking.

int memory_resource_realign( struct memory_resource* dst, size_t const align )
{
    if ( align > dst->align )
    {
        if ( dst->extra_block_size != 0 )
        {
            align_calc_t ac = alignment_calculation( dst->block, align );
            if ( ac.padding > dst->extra_block_size )
            {
                return memory_resource_forced_realign( dst, align );
            }
            else
            {
                dst->aligned_ptr = ac.aligned_ptr;
                dst->align = align;
                return 0;
            }
        }
        else
        {
            return memory_resource_forced_realign( dst, align );
        }
    }
    return 0;
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.