0

I have a memory pool which is a set size and is split into segments of a given size. When I delete some data it flags the segments that data was using as free. Next time I try to allocate memory but don't have space, I realign the memory by shifting all the data down (e.g. First 2 segments are cleared, move all data down by 2 blocks). This all works fine but my issue is my pointers to that data don't change and I am not sure how I can go about doing this.

I allocate memory from my pool by returning a void* to the space in memory, lets assume my pool is the size to hold 2*sizeof(Data).

Data* poolTest = new(pool->GetMemory(sizeof(Data))) Data(5, 5, 5);

So the pool has no reference to the pointer poolTest.

So now if I do this:

pool->Free(poolTest);
Data* poolTest2 = new(pool->GetMemory(sizeof(Data))) Data(4, 5, 5);
Data* poolTest3 = new(pool->GetMemory(sizeof(Data))) Data(3, 5, 5);

The creation of poolTest3 triggers a realignment of memory and now poolTest2 points to the same address as poolTest3 and poolTest1 points to the address that poolTest2 should point to.

I might just be missing something, or my structure is screwed up but I am really stuck on this.

Calum McManus
  • 250
  • 1
  • 9
  • Why realign the memory rather than just having the allocation mechanism return the freed memory directly? Manually compacting memory on *every* allocation after free is going to kill performance (and as you note, invalidates existing pointers unless you go to quite a bit of trouble to either fix them up or have them operate through an additional layer of indirection). – ShadowRanger Nov 08 '18 at 02:48
  • It is to maximise available space. It is possible to pass in any data type, so you could pass in a struct that takes up 2.5 segments. So if I request some data that needs more than the available segments, then I realign it to make at least 3 aligned segments (if available), I don't realign every time I allocate. If I don't do this I could end up with entire segments that are wasted as I can use them. – Calum McManus Nov 08 '18 at 02:55
  • Also I move the data using memmove on a char* which is only O(n) (n being the number of segments after the deleted segments) so it is actually quite efficient and wouldn't need to be called that often. – Calum McManus Nov 08 '18 at 03:02
  • Typical allocators handle the wasted fragments issue by simply holding off on using them until an allocation comes in that is small enough to use it (and if a newly freed block is adjacent to another freed block, joining them). `O(n)` work where `n` is the size of any reasonably sized memory segment is a pretty high cost actually; traversing a free list is only `O(n)` in number of *blocks* on the free list (and in practice you rarely have to traverse very far), where the `memmove` is `O(n)` in terms of segment size (and average case involves moving half your data). – ShadowRanger Nov 08 '18 at 03:12
  • Now, I do see that realignment is only occurring if your fixed size heap is actually *out* of memory, so if you have a free list and you're actually reusing memory first, and only realigning if fragmentation has made all remaining memory unusable, you might not be realigning as often as I think. But it's still going to be hard to handle properly; as long as raw, unmanaged pointers are allowed, it's [basically impossible to defragment a heap](https://stackoverflow.com/a/17009023/364696). You need a much more sophisticated memory management system to allow it. – ShadowRanger Nov 08 '18 at 03:19
  • A thought which I will try out tomorrow is if it possible to store a references to void pointers in an array and then decrement them when I need, but no idea if this is possible or if it will work. – Calum McManus Nov 08 '18 at 03:33

1 Answers1

2

To rephrase your question:

I want to move data around in memory to make room for new allocations. How to I make sure existing pointers still point to the right places?

You can't, unless you keep track of all the pointers, say, by using an array, and instead of accessing your data like this:

*direct_ptr

you now have to do this:

*ptr_map[indirect_ptr]

Every time you move things around, you need to modify ptr_map accordingly.

The array should behave like a stack. You could maybe write a pointer wrapper class that increments some global/static index in the constructor and decrements it in the destructor.

It may save a little space but is quite inefficient for the computer and messy for the programmer.

If you want to do your own memory management, make sure you check out:

https://en.wikipedia.org/wiki/Buddy_memory_allocation

https://en.wikipedia.org/wiki/Slab_allocation

And a good overview of existing techniques:

http://pages.cs.wisc.edu/~remzi/OSTEP/vm-freespace.pdf

Thinking Torus
  • 168
  • 6
  • The [LMAX disruptor](https://github.com/LMAX-Exchange/disruptor) may also be an alternative, They have lots of code to show why it works too. – Ted Lyngmo Nov 08 '18 at 04:00