5

I made a really simple arena allocator in C and I was wondering one thing.

Here is my header file (by the way if this api does not seems right please tell me!).

#ifndef ARENA_H
#define ARENA_H

#include <stddef.h>

struct Arena;

/* Returns a new arena allocator with a capacity of SIZE */
struct Arena *arena_new(size_t size);
/* Allocates SIZE bytes of memory from ARENA aligned with a default alignment
   set to `__alignof__(max_align_t)`. */
void *arena_alloc(struct Arena *arena, size_t size);
/* Allocates SIZE bytes of memory from ARENA with no alignment */
void *arena_alloc_packed(struct Arena *arena, size_t size);
/* Allocates SIZE bytes of memory from ARENA aligned on ALIGN. */
void *arena_alloc_align(struct Arena *arena, size_t size, size_t align);
/* Free all memory allocated with ARENA */
void arena_free(struct Arena *arena);

#endif /* ARENA_H */

In the implementation of arena_alloc_align I use uintptr_t to cast the memory block pointer address to a type with which I can compute the address alignment.

void *arena_alloc_align(struct Arena *arena, size_t size, size_t align)
{
    assert((align & 1) == 0 && "aligment must be a power of two");

    uintptr_t curr_addr = (uintptr_t)arena->mem_block + arena->cursor;
    size_t padding = 0;

    if (align > 0 && !IS_ALIGNED(curr_addr, align))
        padding = align - (curr_addr & (align - 1));

    if(arena->cursor + padding + size > arena->capacity)
        return NULL;

    arena->cursor = padding + size;
    return (void *)curr_addr + padding;
}

Is this type (uintptr_t) ok to use? Like, is it portable? Because from what i read, this type is optional, does this mean that in some compiler implementation it can be not implemented?

If so, what type can I use to cast a pointer to a type that is big enough to hold any memory address?

I've found some other related questions, but people does not seems to give an alternative that is defined in standard and that is not optional. (I may have missed the answer I was looking for).

Improve this question
7
  • 7
    (align & 1) == 0 is not a proper test for a power of 2. Consider !(align && !(align & (align - 1))) Commented Mar 28 at 22:34
  • 1
    'Optional' means it is not portable. A compiler is not required to support it. Commented Mar 28 at 22:43
  • 1
    @WeatherVane i think the real question is if there is a c99+ compiler that does not support uintptr_t. Commented Mar 28 at 23:03
  • 1
    (void *)curr_addr + padding is not valid C. Use char *. Commented Mar 29 at 3:42
  • 2
    If you get this running, you might want to submit it to codereview.stackexchange.com. One thing in particular which I noticed was assert((align & 1) == 0 && "aligment must be a power of two");, which seems off. E.g. one is a power of two, but six isn't. Commented Apr 8 at 9:48

2 Answers 2

Reset to default
8

Is this type (uintptr_t) ok to use? Like, is it portable? Because from what i read, this type is optional

That is correct. According to §7.22.1.4 of the C23 standard, the data type uintptr_t is optional.

does this mean that in some compiler implementation it can be not implemented?

This means that a compiler is not required to support it, so it is theoretically possible for it to be not implemented in a certain compiler. However, I am unaware of any modern compiler which does not support it.

If a compiler decides not to support uintptr_t on a certain platform, it is probably a very old or exotic platform and there probably is a special technical reason not to support it.

For example, in the 1980s, it was common for CPUs to only support 16-bit arithmetic and only have a general register size of 16 bits. But with 16 bits, you can only address up to 64 KiB of memory. Therefore, in order for such a 16-bit CPUs to be able to address more than 64 KiB of memory, these CPUs had to use a segmented memory model instead of a flat memory model (which modern CPUs use), which means that several 16-bit registers had to be used in order to store an address.

In order to implement the integer data type uintptr_t on such a 16-bit platform with memory addresses larger than 16 bits, the compiler would need to implement an integer data type that is larger than 16 bits, despite such a data type not being directly supported by the CPU. The compiler could for example implement a 32-bit data type in software, by making this data type use two 16-bit CPU registers and by making arithmetic operations on this 32-bit data type internally use several 16-bit arithmetic operations.

On the other hand, the compiler could simply decide not to support such a 32-bit data type at all, and only support up to 16-bit data types (which are directly supported by the CPU). In that case, the compiler would not define the data type uintptr_t, and the compiler would still be complying with the C standard.

This example from the 1980s is maybe not a good example, because the data type uintptr_t was only introduced to the language C in the C99 standard (which is from the year 1999), and this standard also introduced the data type long long int, which is required to have a width of at least 64 bits. Nevertheless, this historical example does demonstrate that there may be technical reasons why a compiler would not want to be required to implement the data type uintptr_t, which is probably why the standards committee decided to make this data type optional.

If so, what type can I use to cast a pointer to a type that is big enough to hold any memory address?

If the compiler decides not to support the data type uintptr_t, then as described above, this probably means that there is a special technical reason why it is not trivial to convert a pointer to an integer. In such situations, it is highly unlikely that you will be able to solve the problem by simply using another data type which the compiler implements. Instead, you will likely have to determine the reason why the data type uintptr_t is not supported on this particular platform, and then act accordingly.

On the other hand, if the only reason you want to use the data type uintptr_t is for determining alignment, then using a smaller data type such as unsigned int may be sufficient. But it is worth noting that even when using the data type uintptr_t, the C standard does not guarantee that an even number represents a memory address with an alignment of 2 (even if this probably is a generally safe assumption). The only guarantee that the standard provides is that uintptr_t is an "unsigned integer type" (which means that arithmetic operations may be performed on this data type) and that converting a void * value to uintptr_t and back will yield a pointer value that compares equal to the original pointer value.

However, as already stated above, all of this is unlikely to be a problem in practice, except on very old or exotic platforms.

The C23 standard introduced the new function memalignment, which allows you to determine at run-time whether a pointer is aligned.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Thanks, that helped me out! I just need to clarify one more thing, you said that "the C standard does not guarantee that an even number represents a memory address with an alignment of 2 (even if this probably is a generally safe assumption)", do you known a way that I can guarantee that? Something like malloc which guarantee that the pointer returned is aligned for objects of any type.
@user30097526: As stated in my answer, the C standard does not provide any such guarantees for uintptr_t. However, if you allocate your arena with malloc or aligned_alloc, then the C standard provides alignment guarantees for the pointer value which points to the start of the arena. If you subtract a char * which points inside the arena from a char * which points to the start of the arena, you will get an integer of type ptrdiff_t which represents the offset in bytes. This information will allow you to infer alignment guarantees for the char * that points inside the arena.
@user30097526: Meanwhile, I have noticed that the C23 standard introduced the new function memalignment, which appears to be exactly what you are looking for.
5

Is this type (uintptr_t) ok to use?

Yes.

Like, is it portable?

No. Yes.

Because from what i read, this type is optional, does this mean that in some compiler implementation it can be not implemented?

Yes.

If so, what type can I use to cast a pointer to a type that is big enough to hold any memory address?

Use uintptr_t.

There is no fully portable way to write a general memory allocator in C; it must use prerequisites beyond what the C standard provides, in regard to address manipulation, pointer conversions, type aliasing, and more. Using uintptr_t is a very modest requirement.

A general memory allocator must support allocating spaces for objects of different sizes and alignment requirements. The C standard does not adequately provide fully portable ways to test and manage alignment. (Something crude, and inadequate, might be done by defining the memory pool as a large character array with a maximal alignment requirement, and then alignments can be managed as offsets within that array. However, if an array is defined with a character element type, then using it for other types, as clients of the allocator will, violates the aliasing rules in C 2024 6.5.)

Some strictly limited memory allocator that handles only predetermined types might be possible in strictly conforming code. Aside from that, any memory allocator will rely on implementation features. Using uintptr_t is a reasonable choice because it is widely provided, and, if it is not, it can generally be defined to be the largest unsigned integer type. And there is no better alternative.

Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.