C++ memory pool on shared memory implementation: Is this method of allocation and deallocation correct?

Question

May I request that I any responder consider only "pure" C/C++ (whatever that means)? STL is ok. Boost is not.

I am writing my own C++ memory pool class (on a Linux system) for allocating and deallocating C++ objects in shared memory. I need this for access to the same objects over multiple processes. I will control access to memory pool object manipulation using POSIX semaphores, but I had a basic allocation/deallocation question. My code will only work for objects of the same size being allocated from the same pool. For the moment, we can ignore issues related to growth and shrinking of the pool dynamically.

Consider that I have a shared memory segment defined for a total of MAXFOOOBJECTS Foo objects. I define the shared memory segment in the following manner:

int shmid = shmget (somekey, ((sizeof(Foo) + 4) * MAXFOOOBJECTS) + 4, correctFlags);
void* sMem = shmat (shmid, (void*)0, 0);

By all the processes using this shared memory, the memory will be interpreted like so:

struct SharedMemStructure
{
   int numberOfFooObjectsInPool;
   Foo* ptrArray [MAXFOOOBJECTS]; // Pointers to all the objects in the array below
   Foo objects [MAXFOOOBJECTS]; // Same as the value in the shmget call
};

Let us say I have an object Foo defined like so:

<Foo.h> 
class Foo
{
   public:
     Foo ();
     ~Foo ();
     void* operator new (); // Will allocate from shared memory
     void operator delete (void* ptr); // Will deallocate from shared memory
   private:
     static void* sharedMem; // Set this up to be a POSIX shared memory that accesses
                      // the shared region in memory
     static int shmid;
}

<Foo.cpp>
int Foo::shmid = shmget (somekey, ((sizeof(Foo) + 4) * MAXFOOOBJECTS) + 4, correctFlags);
void* Foo::sharedMem = shmat (shmid, (void*)0, 0);

void* Foo::operator new ()
{
   void* thisObject = NULL;
   sem_wait (sem); // Implementation of these is not shown
   // Pick up the start of a chunk from sharedMem (will make sure this
   // chunk has unused memory...

   thisObject = (sharedMem + 4 + 4 * MAXFOOOBJECTS + 
                (sizeof (Foo) * sharedMem->numberOfFooObjectsInPool);
   sharedMem->ptrArray[numberOfFooObjectsInPool] = thisObject;
   sharedMem->numberOfFooObjectsInPool ++;
   sem_post (sem);
   return thisObject;
}

void Foo::operator delete (void* ptr)
{
   int index = 0;
   sem_wait (sem); // Implementation of these is not shown
   // Swap the deleted item and the last item in the ptrArray;
   index = (ptr - (sharedMem + 4 + (4*MAXFOOOBJECTS)))/(sizeof(Foo));
   ptrArray[index] == ptrArray[numberOfFooObjectsInPool - 1];
   numberOfFooObjectsInPool --;
   sem_post (sem);
}

Now, my questions are:

1. Does the aforementioned scheme seem OK to you folks (O (1) for each of new and delete) or am I missing something utterly important? One problem I see immediately is that if the Foo object array is interpreted as a min heap, for example, I kill the heap property everytime I do the new and delete.
2. If I guarantee that this pool won't be used for min heap (say, as needed by Timer management techniques), do we have any issues with the aforementioned scheme?
3. On the flip side, I could manage the Foo array in the shared memory as a min or max heap (i.e., during new-ing and delete-ing) and incur O (lg n) worst case for each new or delete. Any comments?
4. Any other method that is preferable?

Answer 1

I find your idea ok, but your pointer arithmetic a bit cumbersome... and non portable also. Generally speaking you should never access members of a struct adding the sizes of the previous members, as this is totally non portable (and quite ugly). Remember that the compiler may have alignment restrictions for the members of the struct, so it may insert padding bytes wherever it sees fit.

It is easier to use the struct SharedMemStructure that you presented:

int shmid = shmget (somekey, sizeof(SharedMemStructure), correctFlags);
SharedMemStructure* sharedMem = static_cast<SharedMemStructure*>(shmat (shmid, (void*)0, 0));

Then in the operator new:

//...
thisObject = &sharedMem[sharedMem->numberOfFooObjectsInPool];
//...

About your questions:

1. Of course, constant allocation complexity is incompatible with the heap properties. I think that O(log n) is the best you can get.
2. I see the scheme fine, but the details are in what these Foo class contains. As long as it does not have virtual functions, virtual base classes, pointers, references or any other C++ish construct you should be fine.
3. Yes, you can, why not?
4. If you don't need the heap property, a usual and easy optimization is to get rid of the ptrArray member and build a list of free slots using the first bytes of each free slot to point to the next free one.

Answer 2

Replace all the literal 4's with sizeof(int) and sizeof(Foo *) both for portability and readability. Or better yet, actually use the SharedMemStructure you have defined.

Scratch that, change the SharedMemStructure and then start using it. Your algorithm for tracking which slots are used is flawed. Once one item has been deleted, and the pointer list has been adjusted, there is no way to know which slots have been used without walking the entire list. A simple bool array would work, it will still require walking the list.

If you are really concerned about O(n), you need to maintain used and free linked lists. This can be done with a single fixed size array of int's.

size_t indices[MAXFOOOBJECTS];
size_t firstUsedIndex;
size_t firstFreeIndex;

Initialize firstUsedIndex to MAXFOOOBJECTS and firstFreeIndex to 0. indices gets initialized to 1 through MAXFOOOBJECTS. This way you can treat each entry in indices as a linked list where the contents is the "next" value and MAXFOOOBJECTS is your list terminator. Allocations can be done in constant time because you can grab the front node of the list. Deallocations will be linear since you have to find the node in the used list. You can find the node quickly with (ptr - poolStart) / sizeof(Foo) but you still need to find the previous node.

If you want to eliminate the reallocation costs as well, double the size of indices and treat it like a doubly linked list. The code is similar, but now you can do everything in constant time.

Answer 3

This looks like a problem:

int main() {
  Foo* a = new Foo; // a == &sharedMem->objects[0]
  Foo* b = new Foo; // b == &sharedMem->objects[1]
  // sharedMem->ptrArray: {a, b, ...}
  delete a;
  // sharedMem->ptrArray: {b, ...}
  Foo* c = new Foo; // c == &sharedMem->objects[1] == b!
}