[bind10-dev] use of boost offset_ptr for in-memory data structure

[JINMEI Tatuya / 神明達哉]

Although this is not a topic for the soonest development goals,
assuming we'll work on the "in-memory scalability" feature not far
from now...

I played with the boost offset_ptr
http://www.boost.org/doc/libs/1_35_0/doc/html/interprocess/offset_ptr.html
and found that it can be used in a pretty intuitive way (i.e., mostly
just like bare pointers).  So, even if our initial version doesn't use
sexy shared-memory type of trick, I propose we use it in the internal
representation from the beginning.

Here's (a snippet of) some quick example.  A simple single-linked list
entry can be defined as follows:

struct Entry;
typedef offset_ptr<Entry> EntryPtr;

struct Entry {
    EntryPtr next;
    const int value;
};

and we can traverse a list of these entries like this:
void
traverseList(EntryPtr head) {
    for (EntryPtr ep = head; ep; ep = ep->next) {
        cout << ep->value << endl;
    }
}

In fact, this is compatible with an implementation that uses the bare
pointers.  Memory allocation and deallocation will be less
straightforward than this, but I think it's acceptable with some
proper wrappers.  Then, when we are ready, it can be more easily
switched to a shared-memory or memory-mapped based implementation.

One possibly controversial point is that the issues discussed here:
http://stackoverflow.com/questions/3196395/is-boostinterprocess-ready-for-prime-time?answertab=votes#tab-top
personally we can live with it if we carefully add assertion checks in
the code.

I've copied fully workable example code below.  It supports three
different modes:
- If compiled with USE_SHMEM, it uses shared memory and offset_ptr to
  deal with relative pointer values.
- If compiled with USE_MMAP, it uses shared memory and offset_ptr to
  deal with relative pointer values (and the resulting mapped file is
  "loadable")
- If compiled with USE_BAREPTR, it doesn't use offset_ptr at all.
  This shows we can initially use bare pointers while keeping the code
  compatible with offset_ptr versions.
- By default, it uses offset_ptr but no shared-memory type of trick is
  used.  This is another possibility for the initial implementation.

---
JINMEI, Tatuya

#include <boost/interprocess/offset_ptr.hpp>
#include <boost/interprocess/managed_shared_memory.hpp>
#include <boost/interprocess/managed_mapped_file.hpp>
#include <iostream>
#include <string>
#include <cassert>

using namespace std;
using namespace boost::interprocess;

struct Entry;
#ifdef USE_BAREPTR
typedef Entry* EntryPtr;
#else
typedef offset_ptr<Entry> EntryPtr;
#endif

struct Entry {
    EntryPtr next;
    const int value;

    Entry(int val) : next(NULL), value(val) {}
    template <typename SegmentType>
    static Entry* allocate(SegmentType& segment, int i);
    template <typename SegmentType>
    static void deallocate(SegmentType& segment, EntryPtr ep);
};

#ifndef USE_BAREPTR
template <typename SegmentType>
void
Entry::deallocate(SegmentType& segment, EntryPtr ep) {
    segment.destroy_ptr(ep.get());
}
#endif

template <typename SegmentType>
void
addListEntry(SegmentType& segment, EntryPtr* list_head, int i) {
    EntryPtr* prev = list_head;
    while (*prev) {
        prev = &(*prev)->next;
    }
    *prev = Entry::allocate(segment, i);
}

template <typename SegmentType>
void
removeListEntry(SegmentType& segment, EntryPtr* list_head, int i) {
    EntryPtr* prev = list_head;
    for (EntryPtr ep = *list_head; ep; ep = ep->next) {
        if (ep->value == i) {
            *prev = ep->next;
            Entry::deallocate(segment, ep);
            return;
        }
        prev = &(*prev)->next;
    }
}

// 'head' can be of '(const) EntryPtr&', too.
void
traverseList(EntryPtr head) {
    for (EntryPtr ep = head; ep; ep = ep->next) {
        cout << ep->value << endl;
    }
}

#ifdef USE_SHMEM
template <>
Entry*
Entry::allocate<managed_shared_memory>(managed_shared_memory& segment, int i) 
{
    return (segment.construct<Entry>(anonymous_instance)(i));
}

int
main(int argc, char* argv[]) {
    if (argc == 1) {
        // parent process: create a shared memory region and build
        // a linked list there.
        shared_memory_object::remove("TestSharedMemory");
        managed_shared_memory segment(open_or_create, "TestSharedMemory",
                                      4096);
        EntryPtr* list_head =
            segment.construct<EntryPtr>("head")(static_cast<Entry*>(NULL));
        for (int i = 0; i < 10; ++i) {
            addListEntry(segment, list_head, i);
        }
        system((string(argv[0]) + " child").c_str());
    } else {
        // child process: open the created shared memory and iterate over
        // the linked list stored there.
        managed_shared_memory segment(open_only, "TestSharedMemory");
        EntryPtr* list_head = segment.find<EntryPtr>("head").first;
        assert(list_head != NULL);
        traverseList(*list_head);
        for (int i = 0; i < 10; ++i) {
            removeListEntry(segment, list_head, i);
        }
        segment.destroy_ptr(list_head);
        assert(segment.all_memory_deallocated());
    }
}
#elif defined USE_MMAP
template <>
Entry*
Entry::allocate<managed_mapped_file>(managed_mapped_file& segment, int i) { 
    return (segment.construct<Entry>(anonymous_instance)(i));
}

int
main(int argc, char**) {
    if (true) {
        file_mapping::remove("TestMappedFile");
        managed_mapped_file segment(open_or_create, "TestMappedFile", 4096);
        EntryPtr* list_head =
            segment.construct<EntryPtr>("head")(static_cast<Entry*>(NULL));
        for (int i = 0; i < 10; ++i) {
            addListEntry(segment, list_head, i);
        }
        segment.flush();
    }

    // (re)map the file to memory, and examine it.
    managed_mapped_file segment = managed_mapped_file(open_only,
                                                      "TestMappedFile");
    EntryPtr* list_head = segment.find<EntryPtr>("head").first;
    assert(list_head != NULL);
    traverseList(*list_head);
    for (int i = 0; i < 10; ++i) {
        removeListEntry(segment, list_head, i);
    }
    segment.destroy_ptr(list_head);
    assert(segment.all_memory_deallocated());
}
#else  // normal memory mode
class NormalMemorySegment {
public:
    NormalMemorySegment() : allocated_(0) {}
    template <typename PointedType>
    void destroy_ptr(PointedType* ptr) {
        assert(allocated_ >= sizeof(PointedType));
        delete ptr;
        allocated_ -= sizeof(PointedType);
    }
    bool all_memory_deallocated() const { return (allocated_ == 0); }
    void addAllocated(size_t allocated_size) {
        allocated_ += allocated_size;
    }
private:
    size_t allocated_;
};

template <>
Entry*
Entry::allocate<NormalMemorySegment>(NormalMemorySegment& segment, int i) {
    Entry* ptr = new Entry(i);
    segment.addAllocated(sizeof(Entry));
    return (ptr);
}
#ifdef USE_BAREPTR
template <>
void
Entry::deallocate<NormalMemorySegment>(NormalMemorySegment& segment,
                                       EntryPtr ep)
{
    segment.destroy_ptr(ep);
}
#endif

int
main() {
    NormalMemorySegment segment;

    EntryPtr* list_head = new EntryPtr(NULL);
    for (int i = 0; i < 10; ++i) {
        addListEntry(segment, list_head, i);
    }
    traverseList(*list_head);
    for (int i = 0; i < 10; ++i) {
        removeListEntry(segment, list_head, i);
    }
    delete list_head;
    assert(segment.all_memory_deallocated());
}
#endif