c fixed memory pool implementation

Question

I'm trying to implement a fixed memory pool (first-fit free list) my struct is:

struct mempool {
    void* data;
    int offset;
};

data is divided into 8byte blocks, 4 bytes pointing to next offset and 4 bytes data. offset points to the first free block. I'm trying to understand why accessing the first block is done by:

int* address = (int*)((int)&pool->data + pool->offset);

especially the (int)&pool->data part. Isn't pool->data already a pointer? why do I need its address to perform arithmetic and shift to the offset?

If *you're* implementing it, then how is it that you have code that you do not understand? — John Bollinger, Mar 26 '19 at 14:21
The data field in pool is a pointer, yes, but the pool itself isn't, if you've implemented it somehow like struct mempool pool; — elasticman, Mar 26 '19 at 14:21
I didn't know how to proceed, was given the answer, and now trying to understand why is it so. — susdu, Mar 26 '19 at 14:23
Does this code work? `pool->data` is a field of type `void*`, and `&pool->data` is an address of this field. `(int)&pool->data` if this address cast to `int` which is undefined behavior, because `int` in not guarantee to be able to contain address. — Mikhail Vladimirov, Mar 26 '19 at 14:24
You cannot do pointer arithmetics on a *`void *`* pointer. And AFAIK an int offset and a pointer can be related, but they are not the same animal. Your struct declares an integer offset, while your question speaks of a pointer. — Serge Ballesta, Mar 26 '19 at 14:25
@SergeBallesta: gcc extension allows pointer arithmetic on `void*`. — Joshua, Mar 26 '19 at 14:28
There is no arithmetic on `void *`. Type case has higher precedence than addition. — Mikhail Vladimirov, Mar 26 '19 at 14:29
@Joshua My cat also allows pointer arithmetic on `void*`, but that doesn't mean that we should do it or that it even makes sense in the first place. In particular it doesn't mean that we should teach it to beginners. gcc without `-std=cxx` is to be regarded as a playground for experimental language features for experienced C programmers to play with. — Lundin, Mar 26 '19 at 14:35
@Lundin But closures are so quality of life even in C where you can't return them. — Joshua, Mar 26 '19 at 14:38
There is a lot of low-level junk here that you'd need to ignore/port, but you might be able to borrow from some of my kernel code. Don't worry, its all C compliant: https://github.com/NTDLS/TediOS/blob/master/Kernel/Source/Drivers/CMemory.cpp — NTDLS, Mar 27 '19 at 01:30

John Bollinger · Answer 1 · 2019-03-27T01:21:17.337

I'm trying to understand why accessing the first block is done by:
int* address = (int*)((int)&pool->data + pool->offset);
especially the (int)&pool->data part. Isn't pool->data already a pointer?

Yes, pool->data is a pointer. And one can obtain the address of a pointer, so there's nothing inherently wrong with that. The result in this case has type void **.

Moreover, given that data is the first member of struct mempool, &pool would point to the same address. Although the latter has a different type (struct mempool *), that's probably mooted by the fact that the code performs a conversion to type int.

why do I need its address to perform arithmetic and shift to the offset?

The effect is to compute an address relative to the location of the data pointer itself, rather than relative to its target. Furthermore, the cast to type int suggests that the offset is measured in bytes. That aspect of it is a bit unsafe, however, because it is not guaranteed that type int is large enough to support round-trip conversion from pointer to int to pointer.

This all seems consistent with your characterization of the pool having metadata adjacent to the data, but it remains unclear what purpose the data pointers serve.

Overall, although I'm not convinced of the correctness or efficacy of the minimal code presented. If it in fact serves the purpose for which it is intended, relative to the structure definition presented, then this variation should do so better and more clearly:

int* address = (int*)((char *)&pool + pool->offset);

That avoids the question of an integer type that can represent pointers (although there is one in the form of intptr_t). The cast to char * accounts for the fact that pointer arithmetic is performed in units the size of the pointed-to type, and the offset seems to be expressed in one-byte units.

It looks like the code in the question was (partially) taken from http://www.pinksquirrellabs.com/blog/2018/01/31/-fixed-memory-pool-design/. You can see that a pointer to the pool was passed. — elasticman, Mar 26 '19 at 15:27
Agree with the second form making use of the struct property that the address of the struct is also the address of its first member. — David C. Rankin, Mar 27 '19 at 11:14

score 1 · Accepted Answer · answered Mar 26 '19 at 14:27

1

You code does not seem correct. You are adding pool->offset to the address of pool->data field rather that to the address stored in pool->data field. I would suggest fixing like this:

int* address = (int *)pool->data + pool->offset;

in case your offset is in 4-byte chunks, or like this:

int* address = (int *)((char *)pool->data + pool->offset);

in case your offset is in bytes.

answered Mar 26 '19 at 14:27

Mikhail Vladimirov

13,572
1
38
40

There's no telling what offset contains though. Could be the number of bytes or items. – Lundin Mar 26 '19 at 14:30
That's why I suggested two variants. – Mikhail Vladimirov Mar 26 '19 at 14:31
offset was supposed to hold the address (in number of bytes) of the next block. I now realize that storing addresses in ints is unsafe. – susdu Mar 26 '19 at 14:36

Lundin · Answer 3 · 2019-03-26T14:43:49.327

1

pool->data + pool->offset wouldn't be possible because you can't do pointer arithmetic on void pointers - that isn't valid C. Pointer arithmetic also assumes that the underlying type of this all is an array.

&pool->data gives the address of the pointer itself, which happens to be the address of the struct. The type void**. You can't do arithmetic on that either.

Therefore the naive, bad solution here is to cast the pointer to an int and then do simple addition. That doesn't work either, because int is not guaranteed to be able to hold the contents of a pointer. uintptr_t should have been used instead of int.

And finally, accessing that chunk of memory through int* then de-referencing it is only possible if what's stored there is already regarded as type int by the compiler. If not, it invokes undefined behavior, What is the strict aliasing rule?.

Summary: this is quite questionable code and there's many better ways to implement it.

edited Mar 26 '19 at 14:43

answered Mar 26 '19 at 14:29

Lundin

195,001
40
254
396

can you refer me to a good implementation of a fixed memory pool with fixed block size? – susdu Mar 26 '19 at 14:36
@susdu No, because that depends on the requirements. Such as, (how) should it handle freeing data, how should it handle segmentation, is it ok to store segment sizes and so on. – Lundin Mar 26 '19 at 14:38
Thanks for the help, I guess I'll have to rethink my approach. – susdu Mar 27 '19 at 16:06

c fixed memory pool implementation

3 Answers3