5
\$\begingroup\$

In my last post about the allocator, I received some comments about unit-tests:

The code looks correct on the majority of the cases, I will suggest run valgrind or define a good set of unit tests that exercise your code. @camp0

Valgrind detect things when they are executed, so if your unit tests covers the majority of the code then is fine, if not you should create unit tests for hit that part of the code that is not been executed. @camp0

So here they are:

/* NOTE: Use TEST_ASSERT() for unrelated functions. Say malloc() calls, or 
 *       calls to arena_new() when testing arena_alloc(). Else use TEST_CHECK().
 */
#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L
    #define HAVE_STDALIGN_H
    #include <stdalign.h>
#endif

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

/* The testing library doesn't define these. Define them here instead of modif-
 * -ying the header. These are needed to compile cleanly with -std=c.. flag.
 * These are needed for the declaration of clock_gettime() to be visible in 
 * Oracle Solaris. These defines cause compilation to fail with weird missing
 * types errors on MacOS, hence they're guarded. */
#if defined(__sun) && defined(__SVR4)
    #define _POSIX_C_SOURCE 200819L
    #define _XOPEN_SOURCE 700
#endif

#include "acutest.h"

#include "arena.c"

/* *INDENT-OFF* */
/* In C2X/C23 or later, nullptr is a keyword. */
/* Patch up C18 (__STDC_VERSION__ == 201710L) and earlier versions.  */
#if !defined(__STDC_VERSION__) || __STDC_VERSION__ <= 201710L
    #define nullptr ((void *)0)
#endif
/* *INDENT-ON* */

static inline bool is_aligned(const void *ptr, size_t byte_count)
{
    return (uintptr_t) ptr % byte_count == 0;
}

static void test_arena_new(void)
{
    TEST_CHECK(arena_new(stderr, 0) == nullptr);

    Arena *const arena = arena_new(nullptr, 100);

    TEST_CHECK(arena);
    arena_destroy(arena);

    uint8_t *const backing_storage1 = malloc(100 * (size_t) 1024);

    TEST_ASSERT(backing_storage1);

    Arena *const heap_arena = arena_new(backing_storage1, 100 * (size_t) 1024);

    TEST_CHECK(heap_arena);
    arena_destroy(heap_arena);
    free(backing_storage1);

#ifdef HAVE_STDALIGN_H
    static uint8_t alignas (max_align_t) backing_storage2[BUFSIZ];
    Arena *const static_arena =
        arena_new(backing_storage2, sizeof backing_storage2);
    TEST_CHECK(static_arena);
    arena_destroy(static_arena);

    uint8_t alignas (max_align_t) backing_storage3[BUFSIZ];
    Arena *const thread_local_arena =
        arena_new(backing_storage3, sizeof backing_storage3);
    TEST_CHECK(thread_local_arena);
    arena_destroy(thread_local_arena);
#endif
}

static void test_arena_destroy(void)
{
    Arena *const arena = arena_new(nullptr, 100);

    TEST_ASSERT(arena);
    arena_destroy(arena);
}

static void test_arena_reset(void)
{
    Arena *const arena = arena_new(nullptr, 100);

    TEST_ASSERT(arena);
    arena_reset(arena);

    for (size_t i = 0; i < arena->count; ++i) {
        TEST_CHECK(arena->pools[i]->offset == 0);
    }

    TEST_CHECK(arena->current == 1);
    arena_destroy(arena);
}

static void test_arena_alloc(void)
{
    Arena *const arena = arena_new(nullptr, 100);

    TEST_ASSERT(arena);

    TEST_CHECK(arena_alloc(arena, 1, 112) == nullptr);
    TEST_CHECK(arena_alloc(arena, 0, 1) == nullptr);
    TEST_CHECK(arena_alloc(arena, 1, 0) == nullptr);
    TEST_CHECK(arena_alloc(arena, 2, 5) == nullptr);
    TEST_CHECK(arena_alloc(arena, 3, 5) == nullptr);

    TEST_CHECK(arena_alloc(arena, 1, 95));
    uint8_t *const curr_pool = arena->pools[0]->buf;

    TEST_CHECK(curr_pool[96] == 0xA5 && curr_pool[97] == 0xA5
        && curr_pool[98] == 0xA5 && curr_pool[99] == 0xA5);

    arena_reset(arena);

#ifdef HAVE_STDALIGN_H
    const int *const a = arena_alloc(arena, alignof (int), 5 * sizeof *a);
    const double *const b = arena_alloc(arena, alignof (double), 2 * sizeof *b);
    const char *const c = arena_alloc(arena, 1, 10);
    const short *const d = arena_alloc(arena, alignof (short), 5 * sizeof *d);

    TEST_CHECK(a && is_aligned(a, alignof (int)));
    TEST_CHECK(b && is_aligned(b, alignof (double)));
    TEST_CHECK(c && is_aligned(c, 1));
    TEST_CHECK(d && is_aligned(d, alignof (short)));
#endif
    arena_destroy(arena);
}

static void test_arena_resize(void)
{
    Arena *arena = arena_new(nullptr, 1000);

    TEST_ASSERT(arena);

    TEST_CHECK(arena_resize(arena, stderr, 0) == nullptr);

    arena = arena_resize(arena, nullptr, 10000);
    TEST_CHECK(arena);
    TEST_CHECK(arena->current == 2 && arena->count == 2);

    const char *c = arena_alloc(arena, 1, 10000);

    TEST_ASSERT(c);

    arena_reset(arena);
    TEST_CHECK(arena->current == 1 && arena->count == 2);
    arena_destroy(arena);
}

static void test_arena_allocarray(void)
{
    Arena *const arena = arena_new(nullptr, 100);

    TEST_ASSERT(arena);

#ifdef HAVE_STDALIGN_H
    const int *const nums =
        arena_allocarray(arena, alignof (int), 10, sizeof *nums);
    TEST_CHECK(nums);
#endif

    TEST_CHECK(arena_allocarray(arena, 0, 10, 20) == nullptr);
    TEST_CHECK(arena_allocarray(arena, 10, 0, 20) == nullptr);
    TEST_CHECK(arena_allocarray(arena, 10, 20, 0) == nullptr);
    TEST_CHECK(arena_allocarray(arena, 2, 10, SIZE_MAX) == nullptr);

    arena_destroy(arena);
}

static void test_arena_realloc(void)
{
    Arena *const arena = arena_new(nullptr, 100);

    TEST_ASSERT(arena);

    TEST_ASSERT(arena_alloc(arena, 1, 10));
    TEST_CHECK(arena->pools[0]->offset == 10 && arena->last_alloc_size == 10);

    /* Test expansion. */
    TEST_CHECK(arena_realloc(arena, 20));
    TEST_CHECK(arena->pools[0]->offset == 20 && arena->last_alloc_size == 20);

    /* Test shrinking. */
    TEST_CHECK(arena_realloc(arena, 15));
    TEST_CHECK(arena->pools[0]->offset == 15 && arena->last_alloc_size == 15);

    /* Test deletion. */
    TEST_CHECK(arena_realloc(arena, 0));
    TEST_CHECK(arena->pools[0]->offset == 0 && arena->last_alloc_size == 0);
    arena_destroy(arena);
}

static void test_arena_pool_capacity(void)
{
    Arena *const arena = arena_new(nullptr, 100);

    TEST_ASSERT(arena);
    TEST_ASSERT(arena_alloc(arena, 1, 40));
    TEST_CHECK(arena_pool_capacity(arena) == 60);

    TEST_ASSERT(arena_alloc(arena, 1, 49));
    TEST_CHECK(arena_pool_capacity(arena) == 11);

    TEST_ASSERT(arena_alloc(arena, 1, 11));
    TEST_CHECK(arena_pool_capacity(arena) == 0);
    arena_destroy(arena);
}

static void test_arena_allocated_bytes(void)
{
    Arena *arena = arena_new(nullptr, 100);

    TEST_ASSERT(arena);
    arena = arena_resize(arena, nullptr, 10002);
    TEST_ASSERT(arena);
    TEST_CHECK(arena_allocated_bytes(arena) == 10102);
    arena_destroy(arena);
}

static void test_arena_allocated_bytes_including_metadata(void)
{
    Arena *arena = arena_new(nullptr, 100);

    TEST_ASSERT(arena);
    arena = arena_resize(arena, nullptr, 10002);
    TEST_CHECK(arena_allocated_bytes_including_metadata(arena) == 10102
        + offsetof(Arena, pools)
        + sizeof arena->pools[0] * arena->capacity);
    arena_destroy(arena);
}

/* *INDENT-OFF* */
TEST_LIST = {
    { "arena_new", test_arena_new },
    { "arena_destroy", test_arena_destroy },
    { "arena_reset", test_arena_reset },
    { "arena_alloc", test_arena_alloc },
    { "arena_resize", test_arena_resize },
    { "arena_allocarray", test_arena_allocarray },
    { "arena_realloc", test_arena_realloc },
    { "arena_pool_capacity", test_arena_pool_capacity},
    { "arena_allocated_bytes", test_arena_allocated_bytes },
    { "arena_allocated_bytes_including_metadata", test_arena_allocated_bytes_including_metadata },
    { nullptr, nullptr }
};
/* *INDENT-ON* */

I am using this header-only library: acutest.

And this is the API I am testing:

#ifndef ARENA_H
#define ARENA_H 1

/* *INDENT-OFF* */
#if defined(__GNUC__) || defined(__clang__) || defined(__INTEL_LLVM_COMPILER)
    #define ATTRIB_CONST            __attribute__((const))
    #define ATTRIB_PURE             __attribute__((pure))
    #define ATTRIB_MALLOC           __attribute__((malloc))
    #define ATTRIB_NONNULL          __attribute__((nonnull))
    #define ATTRIB_NONNULLEX(...)   __attribute__((nonnull(__VA_ARGS__)))
    #define ATTRIB_INLINE           __attribute__((always_inline))
#else
    #define ATTRIB_CONST            /**/
    #define ATTRIB_MALLOC           /**/
    #define ATTRIB_NONNULL          /**/
    #define ATTRIB_NONNULLEX(...)   /**/
    #define ATTRIB_INLINE           /**/
#endif
/* *INDENT-ON* */

#define DEFAULT_BUF_CAP     256 * (size_t)1024

#include <stdbool.h>
#include <stddef.h>

/* Bump allocator arena. */
typedef struct arena Arena;

/* Returns a new arena with the specified `capacity`.
 * If `capacity` is 0, a default size of `DEFAULT_BUF_CAP` is used.
 * 
 * On allocation failure, or if `buf` is a non-null pointer and `capacity` is 0,
 * returns `nullptr`. 
 *
 * Passing a `buf` that is smaller than the specified `capacity` would invoke
 * undefined behavior. */
Arena *arena_new(void *buf, size_t capacity);

/* Destroys `arena`, freeing all the memory associated with it.
 *
 * Any pointer allocated by this arena is invalidated after this call. */
void arena_destroy(Arena *arena) ATTRIB_NONNULL;

/* Resets `arena`, invalidating all existing allocations.
 *
 * Whilst existing pointers allocated by this arena are valid after this call 
 * as far as the language is concerned, they should be considered invalid as 
 * using them * would invoke Undefined Behavior. */
void arena_reset(Arena *arena) ATTRIB_NONNULL;

/* Allocates a pointer from `arena`.
 *
 * The allocated pointer is at least aligned to `alignment`.
 *
 * `alignment` must be a power of 2.
 * 
 * `size` must be a multiple of `alignment`.
 *
 * If a request can not be entertained, i.e. would overflow, or `arena` is full,
 * the function returns `nullptr`. The function also returns a `nullptr` if the 
 * requested `size` or `alignment` is 0 or if `alignment` is not a power of 2, 
 * or if `size` is not a multiple of `alignment`.
 *
 * Any allocations made prior to this call are not freed on failure, and remain 
 * valid until the arena is either reset or destroyed.
 */
void *arena_alloc(Arena *arena, size_t alignment, size_t size)
    ATTRIB_MALLOC ATTRIB_NONNULL;

/* Adds a new memory pool to the existing arena `arena`.
 * If `capacity` is 0, a default size of `DEFAULT_BUF_CAP` is used.
 *
 * On allocation failure, or if `buf` is a non-null pointer and `capacity` is 0,
 * returns `nullptr`. 
 *
 * Any allocations made prior to this call are not freed on failure, and remain 
 * valid until the arena is either reset or destroyed.

 * Passing a `buf` that is smaller than the specified `capacity`, or passing an 
 * `arena` that was not returned by `arena_new()` would invoke Undefined Behavior. */
Arena *arena_resize(Arena *restrict arena, void *restrict buf, size_t capacity) 
    ATTRIB_NONNULLEX(1);

/* Allocates a pointer from `arena` large enough for an array of `nmemb` 
 * elements, each of which is `size` bytes.  It is equivalent to the call:
 *
 *              arena_alloc(arena, alignment, nmemb * size);
 * 
 * However, unlike that `arena_alloc()` call, `arena_allocarray()` fails safely 
 * in the case where the multiplication would overflow. If such an overflow 
 * occurs, `arena_allocarray()` returns `nullptr`. 
 *
 * Has the same requirements for `size` and `alignment` as `arena_alloc()`, and 
 * returns `nullptr` for all the cases `arena_alloc()` does.
 *
 * Any allocations made prior to this call are not freed on failure, and remain 
 * valid until the arena is either reset or destroyed.
 */
void *arena_allocarray(Arena *arena, 
                       size_t alignment, 
                       size_t nmemb,
                       size_t size) ATTRIB_MALLOC ATTRIB_NONNULL;

/* Extends the last allocation in place.
 *
 * If `size` is 0, the last allocation is deleted. Else if it is less than the
 * last allocated size, it is shrinked to `size`. Else, it is expanded to `size`
 * bytes.
 *
 * Returns `false` if the request can not be entertained, i.e out of memory.
 * Else it returns `true`.
 */
bool arena_realloc(Arena *arena, size_t size) ATTRIB_NONNULL;

/* Gets the remaining capacity in the current pool (in bytes). */
size_t arena_pool_capacity(Arena *arena) ATTRIB_PURE;

/* Calculates the number of bytes currently allocated across all chunks in `arena`.
 *
 * If you allocate types of different alignments or types with larger-than-typical 
 * alignment in the same arena, some padding bytes might get allocated in the 
 * arena. Those padding bytes will add to this function's resulting sum. The 
 * allocated bytes do not include the size of this arena's metadata. */
size_t arena_allocated_bytes(Arena *arena) ATTRIB_PURE;

/* Calculates the number of bytes requested from the C allocator for this arena. 
 * This number is equal to the allocated_bytes() plus the size of the arena 
 * metadata. */
size_t arena_allocated_bytes_including_metadata(Arena *arena) ATTRIB_PURE;

#endif                          /* ARENA_H */

The source code can be found at arena. Though that's not what is to be reviewed (I don't mind finding new bugs albeit).

The code builds and the tests pass on all of the following operating systems:

  • Windows (10, 11).
  • Linux (Ubuntu, Linux Mint).
  • MacOS.
  • Oracle Solaris 11.4.
  • OmniOS.
  • FreeBSD 14.0 (x86_64, arm64).
  • OpenBSD 7.4 (x86_64, arm64).
  • NetBSD 9.3 (x86_64).

Review Request:

Missing test cases, unclear API documentation, style et cetera.

\$\endgroup\$
1
  • \$\begingroup\$ I have also used Valgrind, Address Sanitizer, and Static Analyzer. They did not report anything. \$\endgroup\$
    – Harith
    Commented May 11 at 12:10

1 Answer 1

6
\$\begingroup\$

Here's something that's not well-defined:

static inline bool is_aligned(const void *ptr, size_t byte_count)
{
    return (uintptr_t) ptr % byte_count == 0;
}

Any kind of object pointer can be converted to uintptr_t, but arithmetic on this integer is unspecified. This test might work on your platform, but there are systems (notably, ia32 segmented memory architectures) where it's likely to be incorrect.


Comparison against nullptr is unnecessary - all pointers convert implicitly to bool.


Arena *const arena = arena_new(nullptr, 100);

The header doesn't say whether passing a null pointer to this function is valid or not. So we can't write any useful tests for this case.


for (size_t i = 0; i < arena->count; ++i) {
    TEST_CHECK(arena->pools[i]->offset == 0);
}

Here, we seem to be relying on the unspecified internals of Arena. That's bad, as we should be able to refactor the implementation without needing to modify the tests - in fact, that's pretty much the definition of refactoring.

Perhaps the Arena needs an accessor we could use to test whether it's empty (or perhaps even to report how much memory it has allocated). We could make this accessor conditionally available (e.g. only if if ARENA_TEST is defined before including its header, or as a separate "arena-test.h" header - or even as a function not mentioned in headers) so as not to make it part of the public interface.

There's more testing of internals here - and it's not at all clear what the magic numbers mean:

uint8_t *const curr_pool = arena->pools[0]->buf;

TEST_CHECK(curr_pool[96] == 0xA5 && curr_pool[97] == 0xA5
    && curr_pool[98] == 0xA5 && curr_pool[99] == 0xA5);
\$\endgroup\$
7
  • \$\begingroup\$ "Any kind of object pointer can be converted to uintptr_t..." ==> That's new to me. Do you have an alternate solution? \$\endgroup\$
    – Harith
    Commented May 11 at 19:00
  • \$\begingroup\$ "Comparison against nullptr is unnecessary - all pointers convert implicitly to bool." ==> Indeed, but chux and Lundin suggest being explicit about the comparison, so I added them. I believe Jonathan Leffer and you're in accord. :) \$\endgroup\$
    – Harith
    Commented May 11 at 19:01
  • \$\begingroup\$ "The header doesn't say whether passing a null pointer to this function is valid or not." ==> Oops. Good point. I added the information about the permissibility of a nullptr in the README.md, but forgot to do it here. \$\endgroup\$
    – Harith
    Commented May 11 at 19:04
  • \$\begingroup\$ "Here, we seem to be relying on the unspecified internals of Arena." ==> True, but Arena is an opaque type, and I didn't know of a way to test its internals without defining the type in the header and making it public. Though accessors can be defined, but then they would be public too, no? And clients should have no business messing around with the internals. Or are we talking about defining static accessors and including "arena.c" like I currently am? \$\endgroup\$
    – Harith
    Commented May 11 at 19:05
  • \$\begingroup\$ "There's more testing of internals here - and it's not at all clear what the magic numbers mean." ==> Yes, I should add a comment. The allocator sets all remaining bytes after an allocation to the magic value 0xA5 in debug mode. \$\endgroup\$
    – Harith
    Commented May 11 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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