Re: [boost] portable precise garbage collector for C++

From: Achilleas Margaritis (axilmar_at_[hidden])
Date: 2007-09-21 13:45:02

O/H Larry Evans έγραψε:
> On 09/21/07 11:26, Achilleas Margaritis wrote:
>> O/H Larry Evans έγραψε:
>>> On 09/21/07 04:14, Achilleas Margaritis wrote:
>>>> O/H Kim Barrett έγραψε:
>>>>> At 2:06 AM +0300 9/21/07, Achilleas Margaritis wrote:
>>>>>> I thought std containers use the allocator::pointer type for their pointers.
>>>>> Unfortunately, not necessarily. They're permitted to bypass that and use
>>>>> T* directly. Ion Gaztañaga ran into this when trying to put containers
>>>>> into shared memory for boost.interprocess.
>>>>> _______________________________________________
>>>>> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>>>>>
>>>> The collector offers the possibility of customizing the scanning 
>>>> procedure (the procedure which scans a block for pointers) through the 
>>>> class gc_traits<T>. So if there is a data structure where gc_ptr<T> can 
>>>> not be used, a custom scan routine especially coded for the data 
>>>> structure in question can solve the problem.
>>> Given the following:
>>>
>>>    std::list<gc_ptr<Node> > node_list;
>>>
>>> where Node is defined in cppgc/src/main.cpp,
>>> then no gc_ptr's within node_list would be
>>> registered as root pointers; so, wouldn't
>>> any Nodes of the gc_ptr's pushed into node_list be
>>> collected?  I guess I don't understand how a customized
>>> scanner would help.  Sure, once it's known that
>>> node_list contains gc_ptr's, the scanner could be
>>> called, but the collector first needs to be notified
>>> of that fact.
>>>
>>> Am I missing something.
>> You have to define the appropriate allocator (in this case, 
>> gc_allocator<Node>) for the std::list to get its member pointers 
>> registered with the collector. gc_allocator<T> defines its pointer as 
> 
> I thought the user-defined scanner was supposed to overcome this
> limitation of the stl implementations.  At least that what I
> *thought* you were implying by:
> 
>  >>> The collector offers the possibility of customizing the scanning
>  >>> procedure (the procedure which scans a block for pointers) through the
>  >>> class gc_traits<T>. So if there is a data structure where gc_ptr<T> 
> can
>  >>> not be used, a custom scan routine especially coded for the data
>  >>> structure in question can solve the problem.
> 
> So... are you saying the UDS(User Defined Scanner) cannot overcome
> the "flawed" stl container use of raw pointer instead of 
> allocator<T>::pointer?

Yes, the user defined scanner can overcome the limitation, but someone 
has to write it, and each version must match the data structure layout 
of the STL container of the used STL library.

For example, if the std::vector is defined as:

template <class T> class vector {
     T *_first;
     T *_last;
};

Then the scanner routine should be:

void scan(void *p) {
    vector<T> *v = (vector<T> *)p;
    gc::scan(v->_first);
}

But it is not possible to automate scanning of STL data structures (C++ 
does not provide struct member metadata), so you have to scan the whole 
block:

void scan(void *p) {
    vector<T> *v = (vector<T> *)p;
    for(void **p = v; p < v + sizeof(vector<T>); ++p) {
        gc::scan(*p);
    }
}

But the above makes the collector not precise, which invalidates the 
whole effort.

If STL containers used allocator::pointer, then declaring a container on 
the stack would register the pointer members of the container as root 
pointers, and there would not be any issues.

> 
> 
>> gc_ptr<T>:
>>
>> std::list<gc_ptr<Node>, gc_allocator<gc_ptr<Node> > > node_list;
>>
>> Although I made the allocator, it does not work with the VC8 STL or the 
>> mingw STL, for the reason mentioned above (STL implementors choosing T* 
>> over allocator::pointer).
>>
>> Is there an STL implementation without this problem? perhaps STLPort? I 
>> have to try it myself, but if anyone knows, please tell me.
>>
> 
> Wouldn't it be pretty easy to modify the _list template in cppgc.hpp to
> take a new allocator template parameter and then modify the pointers in
> _list to use this instead of raw pointers?  That way you could easily
> test to see if future (the ones required to use allocator::pointer)
> stl containers could be used.  You could modify the main_stl I announced
> in my previous post to do this.

The _list template has been replaced with boost::intrusive::list. But 
what does it have to do with the STL anyway? _list was there in order to 
keep blocks around, as a faster alternative to std::list.