0

I want to cut down the size of my metadata struct for my own heap allocator. One field in my struct holds a pointer to the next instance of the struct:

typedef struct _metadata_entry_t {
   struct _metadata_entry_t* next_free_block;
   // signed int bytes_to_next_free_block;
} metadata;

Notice the last two fields are two ways for me to get to the next "free block". A pointer on my system (which is the only system I care about) is 8 bytes while a signed integer is 4 bytes. I think this is a good way of cutting down on the size of my struct (trading off instant access to a little bit of void pointer arithmetic). Are there any problems proceeding this way?

Additionally, since I can ensure that the addresses of these metadata structs are memory aligned to 8 bytes, maybe I can somehow truncate the address and store it in a smaller data type? Not too sure if that can be done.

trincot
  • 317,000
  • 35
  • 244
  • 286
Peabrain
  • 519
  • 2
  • 12
  • As far as C goes, arithmetic using pointers to different objects is invalid. – Weather Vane Mar 06 '21 at 20:40
  • How did you obtain the memory pool? With a single malloc()? – tstanisl Mar 06 '21 at 20:43
  • maybe I should clarify; I am using GCC to compile my code, which allows me to do void pointer arithmetic on addresses. Basically, I can take an address and increment it in bytes to whatever address I want. I know in general, this is not allowed, but again, I am using a GCC extension. https://stackoverflow.com/questions/3523145/pointer-arithmetic-for-void-pointer-in-c – Peabrain Mar 06 '21 at 20:45
  • @tstanisl, I am implementing my own version of malloc. Using sbrk and other system calls to obtain the memory pool. – Peabrain Mar 06 '21 at 20:46
  • @Peabrain: It does not matter which compiler you use. Actually with gcc optimising quite agressively at any level, the undefined behaviour can become even more of a problem. Please also note that with e.g. signed pointers and similar security features, the higher bits of 64 bit pointers might differ between pointers even into the same heap (not object!). So briefly: this is a very bad idea. – too honest for this site Mar 06 '21 at 22:12

1 Answers1

0

If the memory pool was allocated as a single object (like result of a single malloc() or a global array) then pointer arithmetics can be safely used.

bytes_to_next_free_block = (char*)ptr - (char*)pool_start;

However, I suggest using another trick.

Place _metadata_entry_t inside the actual empty block on the freelist. Whenever a block is freed you will place its metadata inside the first bytes of the freed chunk. When the block is allocated by a caller then remove block's metadata from the freelist, erase the record and return the chunk to the caller.

Either the block is owned by the allocator and it contains the metadata. Or the block is owned the library user and is filled with user's data.

This way the size of metadata virtually does not matter as long as minimal allocation is at least as large as the matadata (8 bytes in your case).

tstanisl
  • 13,520
  • 2
  • 25
  • 40
  • if I am interpreting this correctly, this means metadata objects should only exist inside free blocks? I have been approaching my algorithm as though I need a metadata object before each block (regardless if it is free or used). – Peabrain Mar 06 '21 at 21:04
  • Come to think of it, this makes sense as metadata wouldn't exactly be needed for blocks that are being currently used by the user... right? – Peabrain Mar 06 '21 at 21:04
  • @Peabrain, yes. You can still place some metadata *before* the user's block like a block size. It would simplify `free()`. However, there is no need place pointer there. This can be avoided by placing metadata in the first bytes of the memory page (4KB usually). The page address can be computed from user address by zeroing lower bits. All blocks from the same page would be the same size. – tstanisl Mar 06 '21 at 21:09
  • @Peabrain, it's still possible to get `free()` works without per-block-metadata. Keep the size of the block at the first bytes of the memory page. All blocks of allocated from the same page would be the same size. – tstanisl Mar 06 '21 at 21:24
  • however, even if I keep the size of the block a constant size, a user may malloc more than one block worth of data, then, I would still have to keep track the number of blocks I have to free, correct? – Peabrain Mar 06 '21 at 21:30
  • Also, just a thought, do you think the range of an int is enough to contain the difference of two addresses on the heap? In the worst case scenario, is it possible an int will not contain two very far apart addresses on the heap? – Peabrain Mar 06 '21 at 21:33
  • @Peabrain, blocks of other size would be taken from the different memory pages. You will have to maintain an array of freelist heads each for allocations of specific sizes. Whenever a given freelist is drained you simply allocate a new page and fills its first bytes with the size of a chunk. Large allocation (>=4KB) would be handled differently, however extra cost of metadata is less severe for large allocations. – tstanisl Mar 06 '21 at 21:46