Re: RFC: C++0x memory model and parallel shift

On Sep 6, 8:28 pm, Mathias Gaunard <loufo...@gmail.com> wrote:


I have made a lock-free memory reclaimator that works and is not
patented. Nor do I really care to patent it--there is no way I am
going to reclaim the patent fee's for something like this.
It is composed of four pieces:
1. Allocator
2. intrusive reference counter + version field
3. isolated_ptr that obtains pointer suitable for dereferencing (like
a shared_ptr)
4. mutual_ptr that is lock-free, but not dereferenceable (like a
weak_ptr), that also support CAS

You use it like so:
struct A:
enable_mutual_ptr<A>//allocator and intrusive ref counter
{
    int a;
    int b;
};

mutual_ptr<A> global;//multiple threads can access atomically
void threadfunc(void*){
   isolated_ptr<A> read;
   isolated_ptr<A> update;
    do{
        read=global;
        if(read){
           update.reset(new A(*read));//copy
           update->a=read->a+1011;//modify, etc
         }else{
           update.reset(new A);
          //more stuff
        }
    }while(global.CAS(read,update));
}

The allocator serves a few purposes:
1. That only A's are allocated, since fields may be accessed after
return to the allocator (a standard allocator does not allow this)
2. I used DCAS internally, however special allocator would allow for
pointer compression if DCAS is undesirable
3. it is also lock-free

The basics of the guts are this:

When an A is constructed, a version is stored inside the object next
to the reference count. a 0 value for version is special.
The mutual_ptr stores both the pointer and the version
The release method checks both the reference count and the version. If
the versions match AND the refcount is 0, then the version is also set
to 0. (i.e. if refcount is 1 and version is X, set (version,refcount)-


//part of "enable_mutual_ptr"
friend void mutual_ptr_release(T const* p){
//storage_type is pair of refcount and version(tag)
do{
    storage_type oldval(p->m_refs.get_data(),p->m_refs.get_tag());//tag
and count
    unsigned new_tag=oldval.get_tag();
    if(new_tag==0)return;
    unsigned cnt=oldval.get_data();
    if(cnt==1)new_tag=0;
    storage_type newval(cnt-1,new_tag);
    if(p->m_refs.CAS(oldval,newval)){
        if(cnt==1) delete const_cast<T*>(p);
        return;
    }
}while(true);

}
Now, the tricky part comes in when making an isolated_ptr from a
mutual_ptr -- it is possible that mutual_ptr contains a stale pointer.
So instead of the traditional refcount increment, we do this

//part of "enable_mutual_ptr"
freind unsigned mutual_ptr_add_ref(T const* p, unsigned version){
   //storage_type is pair of refcount and version
   unsigned ret=0;
   do{
    storage_type oldval(p->m_refs.get_version(),p->m_refs.get_tag());//
tag and count
    if(oldval.get_tag()!=tag)return 0;
    ret=oldval.get_data()+1;
    storage_type newval(ret,tag);
    if(p->m_refs.CAS(oldval,newval))break;
    }while(true);
    return ret;
}
When the pointer is isolated, the traditional "increment the reference
count" can be done.
Now when making the copy, we must try a repeatable read (some will
argue that a repeatable read is not strictly lock-free, since is it
possible that no thread makes progress. However, it woould have the
obstruction free property--if I compressed the pointer, it would be
lock free)
template<class Y>
isolated_ptr(mutual_ptr<Y> const & mutual_rhs)
{
//m_p is member which is pair of pointer and version
do{
    m_p=mutual_rhs.m_p;//pointer and version
    if(!m_p.CAS(mutual_rhs.m_p,mutual_rhs.m_p))//not sliced
            continue;
    T* lcl=m_p.get_data();
    if(lcl==0)return;
    unsigned cnt = mutual_ptr_add_ref(lcl,m_p.get_tag());
    if(cnt >0)//not a zombie
        return;
    else{
        sched_yield();//backoff
    }
    //eventually mutual_rhs will either have a live value or a 0
}while(true);
}

These are basically the highlights. I use this inside some market data
servers (those things that takes all those stock market ticks and does
stuff with them --typically 100K msg per second with <1ms latency)

So there you have it. A lockfree pointer that has no patents (and not
even a copyright). I suppose a newsgroup is evidence enough of prior-
art is someone did try to patent it.
Lance

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]