Geometry Boost List: Re: [geometry] Crash in rtree after growing shared memory, VS2012 x64, Boost 1.55

Subject: Re: [geometry] Crash in rtree after growing shared memory, VS2012 x64, Boost 1.55
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-07-26 07:08:33

Hi Tim,

Tim Finer wrote:
>> On Jul 25, 2014, at 6:16 PM, Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]> wrote:
>>
>> In order to work the way you want the rtree requires an allocator which will be able to increase the size of shared memory if needed.
>> I'm not sure if this is possible in general and/or with Interprocess.
>> I'll try to play with it in my free time.
>> If you were able to come up with something before me, please let me know.
> Some other options I'm looking at are:
>
> 1 Scanning all the data first (it isn't in a convenient format, so I'll need to store it in another mapped file), then allocating enough space for the rtree.

FYI, the packing algorithm done in the constructor (when you're creating 
the rtree from e.g. a pair of iterators) should construct an rtree 
having nodes "packed" as tightly as possible, you could actually predict 
what'll be the actual number of nodes created. At least for currently 
used algorithm. If you're curious see line 109 of 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/pack_create.hpp.
So maybe it'd be a good idea to first load the objects to a vector, 
calculate their size, then create a shared memory and construct an rtree 
using pack-create.
Though I fear that if the memory could be fragmented this might not work 
in all cases.

> 2. Read up on allocators and trap the exception down at a lower level, and possibly do the resize there.  There are no guarantees about the newly allocated pointer's location after growing.
AFAIU this is what I was thinking about, an allocator catching the 
exception in allocate(), growing the memory block and recreating itself. 
I thought about storing shared_ptr to a struct holding unique_ptrs to 
shared memory and original allocator. The purpose is to have only one 
allocator and modify a pointer to it from any of the rebound allocators. 
Then in allocate() of any of rebound allocators this original allocator 
would be always rebound to the current one.

As you said this won't work, the rtree would have to be reconstructed 
after grow and in that time the algorithm would be somewhere in the 
middle of traversal, holding old/invalid pointers, etc.
>        
> 3. Monitor the capacity of the shared file and proactively resize given a threshold (say 90%).  I just thought of this one and I like it because it sidesteps the entire exception problem altogether.  The more I think about it, the more I like this one.

Yes, this is also worth trying.
It seems that there is a get_free_memory() method in 
managed_shared_memory so the amount of free space could be easily returned.
In case if the memory could be fragmented you could try to allocate some 
bigger block and see if it succeeds. Then resize the memory if necessary.
When the exception is thrown get_free_memory() returns 968 in my test 
and I'm starting from 1024 * 64.
The author of Boost.Interprocess could probably give us some pointers 
about how big the threshold should be and if the fragmentation should be 
taken into account.

Regards,
Adam