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

From: Larry Evans (cppljevans_at_[hidden])
Date: 2007-09-21 14:07:35

On 09/21/07 12:45, Achilleas Margaritis wrote:
> 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.

Yes, I understand, but the scanner, as you've shown above, doesn't do 
this (it doesn't register the root pointer) so, it can't overcome the
problem which I thought we were talking about, how to register
the root pointer.  I'm not concerned, at this point, about precision,
I'm only concerned about somehow registering the root pointers.

The above scan(void *P) doesn't help at all in doing this.  Right?

> 
>>
>>> 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.
> 

I'm not saying modify _list in the collector, I'm only saying you could
modify it to use:

    Allocator<T>::pointer _list<T>::_begin;

instead of:

    T* _list<T>::_begin;

where, in the case of _list used in your collector, it would default
to what it is now, but for the _list used in GCBench (as defined
in main_stl.cpp) it would be Allocator::<T>::pointer which
would be:

   gc_ptr<T>

So you'd be reusing the _list code as part of the collector
implementation; yet, also to demonstrate how std::list could
be modified so that it would work with your collector.