Objects in container: creation and deletion details
Michael Podolsky
I have relatively specific design requirements that I have found
hard to fullfil by myself, yet I consider that my problems are
relatively
common for unexperienced multithread programmer.
So I turn to this forum searching for correct and sound solutions.
1) I have associative container protected with read-write lock
where objects are registered using identifiers. The central function
Object *new_old(Identifier id)
is supposed to search container and return existing registered object
by its identifyer or, if not found, create new object and insert it
into container, associating it (object) with supplied identifyer.
2) Objects by themselves are reference counted, so that last
release (refcount decrement) removes them from container. 'new_old'
function increments refcount before returning object pointer to
caller.
3) Object construction process takes relatively long time so I have
found appropriate to divide its construction in two stage - first
stage (C++ constructor) is done before object inserted into container
(while write lock is locked) then (after insertion) second (long)
stage of object creation cames.
The things I found relatively problematic to cope with are:
1) what to do if new_old function finds object that is passing in
another thread its last 'release'. Should I wait (and how to do it)
until the object will be removed from container, then insert the new
object (with the same ID), or smth. else
2) more hard for me -- even if I find the object in container, I can't
promise its creation process is finished (remember, the second part of
creation process is done after object is inserted), so I need to
provide some mechanics to signal object full creation for this case.
On the other side, I would not like to waste kernel syncronization
object per every new my Object instance -- that type of syncronisation
is rare and (what is more important) is done once only - at the time
of object creation.
The work is done in Win32 API (sorry about it) so I would prefer a
solution that is not based on conditional variables.
I attach my current code prototype. What I need is to know
1) If I cope correct and properly with a case when old dying object is
found in container.
2) How to implement functions Object::SetCreationFinished() and
Object::WaitCreationFinished() in a proper way. Or may be I do not
need them at all and you know a better way to do syncronisation for
object creation? (again, no conditional variables, just Win32 API)
Regards, Michael
Object * new_or_old(ID id)
{
Object *found=0;
// first - search old if present
rwlock.read_lock(); // protects the container
found = container.findObject(id);
if(found)
if(found->WeakAddRef() == 0) // increments object refcount
// but 'Weak' will not increment it when recount==0
// i.e. when object is dying
found = 0;
rwlock.read_unlock();
if(!found)
{ // second - create and insert new
Object *justConstructed = new Object(id);
justConstructed->AddRef(); // just put refcount to one
rwlock.write_lock();
once_more:
found = container.registerObject(justConstructed, id);
// registerObject returns pointer to new registered object
// or (if old found) will not do anything and return pointer
// to old object
if(found!=justConstructed)
{ // we have suddenly get old registered object
if(found->WeakAddRef() == 0)
{
container.unregisterObject(id);
found = 0;
goto once_more;
}
}
rwlock.write_unlock();
if(found == justConstructed)
{ // j.e. new object was inserted into container
justConstructed->PostCreationStage(); // takes long time
so put
// outside of rwlock
justConstructed.SetCreationFinished();
return justConstucted;
}
else
{ // old living object was found
delete justConstructed; // no need for this guy
}
} // finish of if(!found)
found->WaitCreationFinished();
return found;
}
void Object::Release()
{
if( ref_counter.decrement() == 0 )
{
rwlock.write_lock();
container.unregisterObject(id);
rwlock.write_unlock();
PreDestructionStage();
delete this;
}
}
Alexander Terekhov
Michael Podolsky wrote:
[...]
> Object *new_old(Identifier id)
I'd rather do it this way [pretty simple]:
void locateOrAdd( /* some 'id'/'key' stuff */, some_smart_ptr< Object >& )
Once created/added, the reference count should be set to ONE
(don't count the ref. that you keep in your 'registry'). One
single lock should be associated with BOTH ALL-ref.counts AND
your registry/ref.collection [SHOULD BE THE SAME ONE SINGLE
LOCK]. Unless you addref/unref like crazy, contention should
NOT be the problem, at all. Your unref() should REMOVE the
object from registry (when ref.count reaches the ZERO and
return 'delete me' indicator -- smart_ptr d-tor would then
delete the referenced object[1]).
Or am I just missing something?
BTW, that 'might' be a good candidate for UPGRADEABLE[2]
read-write locking 'strategy' (but I'd rather 'begin with'
rather simple mutex and FAST/INEXPENSIVE search mechanism,
though).
Well, you could also have much more finer grained locking
[with separate locks protecting each ref.count (and perhaps
it's object... if they are MUTABLE ones), for example]. Your
'final' unref [when the count reaches the ZERO] would have
to:
[...]
- unlock the count/object
- lock the registry
- re-lock the count/object
- check the count again (whether it's still ZERO)
IFF it's still ZERO:
- remove object from registry
- unlock object and registry
- delete object
ELSE [>>NOT ZERO<<]
- unlock object and registry
Inside your 'locateOrAdd'-sort-of-factory you should NOT
unlock the registry *prior to incrementing the ref.count
[or creating the new object]*.
regards,
alexander.
[1] http://groups.google.com/groups?threadm=3CF8C9B2.FBD02BF%40web.de
[2] http://groups.google.com/groups?threadm=ijnd7a.3pb.ln%40tux.localdomain
P.S. I did not quite get your 'PostCreationStage(); // takes long time'
stuff/ideas [perhaps you need to apply the MONITOR 'pattern' w.r.t.
it... but that would definitely require CONDVAR(S). ;-)] Anyway,
click here: http://sources.redhat.com/pthreads-win32
Michael Podolsky
> Once created/added, the reference count should be set to ONE
> (don't count the ref. that you keep in your 'registry').
Yes, of course. BTW, another sort of functionality I find problematic
to impelemt is to proceed with object unregistering some time after
last external unref.
In this case I will probably need the container to initially addref my
object too (i.e. beginning with refcount==2).
> One single lock should be associated with BOTH ALL-ref.counts AND
> your registry/ref.collection [SHOULD BE THE SAME ONE SINGLE
> LOCK]. Unless you addref/unref like crazy, contention should
> NOT be the problem, at all. Your unref() should REMOVE the
> object from registry (when ref.count reaches the ZERO and
> return 'delete me' indicator -- smart_ptr d-tor would then
> delete the referenced object[1]).
Well, I would rather tend to separate the protection of container and
protection of objects. Besides, I use atomic functions to
modify/access counters (Interlocked... stuff of Win32 API). So lets
proceed to second variation of your solution. (BTW, why do you prefer
to delete object by smart_ptr destructor and not by object unref
function? )
> BTW, that 'might' be a good candidate for UPGRADEABLE[2]
> read-write locking 'strategy' (but I'd rather 'begin with'
> rather simple mutex and FAST/INEXPENSIVE search mechanism,
> though).
Hmm... Only one thread can actually gain upgradeable access to rwlock,
so I don't see any profit of upgadeable rwlock in this case. Or if you
mean just release read lock and then gain write lock??? (I don't think
you mean it really when you talk about UPGRADEABLE.
> Well, you could also have much more finer grained locking
> [with separate locks protecting each ref.count (and perhaps
> it's object... if they are MUTABLE ones), for example]. Your
> 'final' unref [when the count reaches the ZERO] would have
> to:
>
> [...]
> 1: - unlock the count/object
> 2: - lock the registry
> 3: - re-lock the count/object
> 4: - check the count again (whether it's still ZERO)
> 5: IFF it's still ZERO:
> - remove object from registry
> - unlock object and registry
> - delete object
> ELSE [>>NOT ZERO<<]
> - unlock object and registry
>
> Inside your 'locateOrAdd'-sort-of-factory you should NOT
> unlock the registry *prior to incrementing the ref.count
> [or creating the new object]*.
Your solution differs from mine because yours "reincarnates" dying
object (i.e refcount can reach zero and then be incremented again),
while mine does not.
Inintially I was amazed, but after a while... it seems to me that
yours is NOT correct.
Let us suppose we have final unref and our thread is about entering
line #2 (locking the registry), while refcount is zero. At the same
time another thread could call 'locateOrAdd' function (that will
increment refcount, reincarnating the object), then same second thread
will call 'unref' (again, final unref) that will unregister and delete
object. Now returning to first thread, it locks the register and goes
to lock and test counter of UNEXISTING object. RIP.
> I did not quite get your 'PostCreationStage(); // takes long time'
> stuff/ideas
My Object creation takes a long time (includes net communication). So
I make first part of creation (C++ constructor), then register the
object, then (having container rwlock released) proceed with main and
havy part of object initialization. At the same time another threads
may try to find an object with the same ID and will find my not fully
initialized object. So they should wait until its full construction.
> [perhaps you need to apply the MONITOR 'pattern' w.r.t.
> it... but that would definitely require CONDVAR(S). ;-)] Anyway,
> click here: http://sources.redhat.com/pthreads-win32
Well, congratulations upon new implementation of condvars inside
pthreads-win32. I did not knew that until yesterday.
Actually, I am ready to see and discuss the solution with condvars as
far, still prefering a soultion without them.
Regards, Michael
PS: Yeah, and of course, sorry for MOY poor english. )))
Alexander Terekhov
Michael Podolsky wrote:
>
> Alexander Terekhov wrote:
>
> > Once created/added, the reference count should be set to ONE
> > (don't count the ref. that you keep in your 'registry').
>
> Yes, of course. BTW, another sort of functionality I find problematic
> to impelemt is to proceed with object unregistering some time after
> last external unref.
> In this case I will probably need the container to initially addref my
> object too (i.e. beginning with refcount==2).
Well, please see below.
> > One single lock should be associated with BOTH ALL-ref.counts AND
> > your registry/ref.collection [SHOULD BE THE SAME ONE SINGLE
> > LOCK]. Unless you addref/unref like crazy, contention should
> > NOT be the problem, at all. Your unref() should REMOVE the
> > object from registry (when ref.count reaches the ZERO and
> > return 'delete me' indicator -- smart_ptr d-tor would then
> > delete the referenced object[1]).
>
> Well, I would rather tend to separate the protection of container and
> protection of objects. Besides, I use atomic functions to
> modify/access counters (Interlocked... stuff of Win32 API). So lets
> proceed to second variation of your solution. (BTW, why do you prefer
> to delete object by smart_ptr destructor and not by object unref
> function? )
Please see below.
> > BTW, that 'might' be a good candidate for UPGRADEABLE[2]
> > read-write locking 'strategy' (but I'd rather 'begin with'
> > rather simple mutex and FAST/INEXPENSIVE search mechanism,
> > though).
>
> Hmm... Only one thread can actually gain upgradeable access to rwlock,
> so I don't see any profit of upgadeable rwlock in this case. Or if you
> mean just release read lock and then gain write lock???
Sort of.
> (I don't think you mean it really when you talk about UPGRADEABLE.
Check out that referenced thread on upgradeable read-write locking.
> > Well, you could also have much more finer grained locking
> > [with separate locks protecting each ref.count (and perhaps
> > it's object... if they are MUTABLE ones), for example]. Your
> > 'final' unref [when the count reaches the ZERO] would have
> > to:
> >
> > [...]
> > 1: - unlock the count/object
> > 2: - lock the registry
> > 3: - re-lock the count/object
> > 4: - check the count again (whether it's still ZERO)
> > 5: IFF it's still ZERO:
> > - remove object from registry
> > - unlock object and registry
> > - delete object
> > ELSE [>>NOT ZERO<<]
> > - unlock object and registry
> >
> > Inside your 'locateOrAdd'-sort-of-factory you should NOT
> > unlock the registry *prior to incrementing the ref.count
> > [or creating the new object]*.
>
> Your solution differs from mine because yours "reincarnates" dying
> object (i.e refcount can reach zero and then be incremented again),
> while mine does not.
> Inintially I was amazed, but after a while... it seems to me that
> yours is NOT correct.
Correct. ;-)
> Let us suppose we have final unref and our thread is about entering
> line #2 (locking the registry), while refcount is zero. At the same
> time another thread could call 'locateOrAdd' function (that will
> increment refcount, reincarnating the object), then same second thread
> will call 'unref' (again, final unref) that will unregister and delete
> object. Now returning to first thread, it locks the register and goes
> to lock and test counter of UNEXISTING object. RIP.
Yup; you are right. My fault. Sorry. Thanks.
Well, partly, the reason why I've made that mistake is
that I 'usually' use b*-trees for indexing/collections
of ptrs/refs... for REMOVE operation we first have to
LOCATE the element (node and position within it; setup
'cursor' pointing to the existing element -- obj.ptr),
so the logic/'pseudo-code' would then roughly do the
following:
~ChunkPtr() throw() // smart 'thread shared object' ptr
{
Chunk::ZombieKeyHolder zkHolder; // uninitialized storage
// Wanna 'kill yet another zombie'?! ;-)
if ( m_pChunk->unref( zkHolder ) ) {
// Destroy zombie (kill'm if he's still 'alive' and NOT 'in use' ;-))
delete Chunk::s_registry.removeZombie( zkHolder.key() );
// Zombie's key cleanup
zkHolder.key().~Key();
}
}
bool Chunk::unref( Chunk::ZombieKeyHolder& zkHolder ) throw()
{
Guard guard( m_mutex );
// Let's strictly follow 4.10-rules... ;-)
if ( 0 != --m_count )
return false;
// Save zombie's key -- should better NOT throw! ;-)
new( &zkHolder.key() ) Key( m_key,zkHolder );
// Return 'zombie' status
return true;
}
Chunk* Chunk::Registry::removeZombie( const Chunk::Key& key ) throw()
{
Guard guard1( m_mutex );
// Is our 'zombie' still 'alive'?
if ( !m_coll.locateElementWithKey( key,m_cursor ) )
return 0; // Schade [both ger. && eng.] :-(
Chunk* pZombie = m_cursor.element();
// 'Swap' semantics -- now guard1 'owns' the zombie's lock
Guard guard2( guard1,pZombie->m_mutex );
// Is it really 'zombie'?
if ( 0 != pZombie->m_count )
return 0; // God rules -- I just wish to have the same 'resurrection' fate! ;-)
// Unregister zombie
m_coll.removeElementAt( m_cursor );
// Unlock registry FIRST and afterwards unlock zombie
return pZombi;
}
Are there any 'bugs' [races, etc.] and/or some things to 'improve', folks?
> > I did not quite get your 'PostCreationStage(); // takes long time'
> > stuff/ideas
>
> My Object creation takes a long time (includes net communication). So
> I make first part of creation (C++ constructor), then register the
> object, then (having container rwlock released) proceed with main and
> havy part of object initialization. At the same time another threads
> may try to find an object with the same ID and will find my not fully
> initialized object. So they should wait until its full construction.
Looks like MONITOR-'thing'.
> > [perhaps you need to apply the MONITOR 'pattern' w.r.t.
> > it... but that would definitely require CONDVAR(S). ;-)] Anyway,
> > click here: http://sources.redhat.com/pthreads-win32
>
> Well, congratulations upon new implementation of condvars inside
> pthreads-win32. I did not knew that until yesterday.
> Actually, I am ready to see and discuss the solution with condvars as
> far, still prefering a soultion without them.
Monitors? Without CONDVAR(S)?! No way!!
> Regards, Michael
>
> PS: Yeah, and of course, sorry for MOY poor english. )))
;-)
regards,
alexander.
Michael Podolsky
> > (I don't think you mean it really when you talk about UPGRADEABLE.
>
> Check out that referenced thread on upgradeable read-write locking.
Yeah, I've got a point finally.
What about making a mutex that have 'reacquire' operation (trying to
relock mutex after unlock have been done, while it is tested that
nobody else owned the mutex when it was free)? :-))
> Well, partly, the reason why I've made that mistake is
> that I 'usually' use b*-trees for indexing/collections
> of ptrs/refs... for REMOVE operation we first have to
> LOCATE the element (node and position within it; setup
> 'cursor' pointing to the existing element -- obj.ptr),
Well, seems like this code will really reincarnate objects.
> > My Object creation takes a long time (includes net communication). So
> > I make first part of creation (C++ constructor), then register the
> > object, then (having container rwlock released) proceed with main and
> > havy part of object initialization. At the same time another threads
> > may try to find an object with the same ID and will find my not fully
> > initialized object. So they should wait until its full construction.
>
> Looks like MONITOR-'thing'.
Yes, of course. But the idea is to make each object constructed
concurrently (so I need separate monitor for each object), not to
waste mutex+condvar in case nobody is trying to wait and what is most
important - destroy mutex+condvar as soon as everybody has finished
waiting so sync objects that were necessary on creation stage will not
be wasted.
Well, I guess, I could implement such a thing by myself but I supposed
that my problem is relatively standard so I hoped that there exist
appropriate sync. pattern (may be some variation of double checking
locking pattern but together with sync objects disposing? Still, the
situation is differ because thread knows exactly if it waits for full
construction or does construct and signal).
> > Well, congratulations upon new implementation of condvars inside
> > pthreads-win32. I did not knew that until yesterday.
> > Actually, I am ready to see and discuss the solution with condvars as
> > far, still prefering a soultion without them.
>
> Monitors? Without CONDVAR(S)?! No way!!
How could you conclude I mean this?
Surely, monitor == mutex + condvars
Regards,
Michael
Alexander Terekhov
Michael Podolsky wrote:
[...]
> But the idea is to make each object constructed
> concurrently (so I need separate monitor for each object), not to
> waste mutex+condvar in case nobody is trying to wait and what is most
> important - destroy mutex+condvar as soon as everybody has finished
> waiting so sync objects that were necessary on creation stage will not
> be wasted.
Well, for such newly created objects with subsequent 'post' construction
'slow' init-phase I'd probably simply allocate [done by the first 'waiter']
ONE SINGLE CONDVAR (bind it to the mutex associated with the object or even
your 'global' *registry*; if your objects are IMMUTABLE and you'll really
use [non-portable] atomic '++' and '--' for ref.counting) per object and
simply broadcast *and destroy* it upon the completion of that 'slow' init-
phase. Note that boost::threads win32-condvars have a broken destructor
that can't really handle such 'signal/broadcast&destroy' semantics[1]. Linux
threads seemed to have a similar problem the last time I've looked at it...
regards,
alexander.
[1] http://www.opengroup.org/onlinepubs/007904975/functions/pthread_cond_destroy.html
"....
It shall be safe to destroy an initialized condition variable upon which
no threads are currently blocked.
....
The following sections are informative.
EXAMPLES
A condition variable can be destroyed immediately after all the threads
that are blocked on it are awakened. For example, consider the following
code:
struct list {
pthread_mutex_t lm;
...
}
struct elt {
key k;
int busy;
pthread_cond_t notbusy;
...
}
/* Find a list element and reserve it. */
struct elt *
list_find(struct list *lp, key k)
{
struct elt *ep;
pthread_mutex_lock(&lp->lm);
while ((ep = find_elt(l, k) != NULL) && ep->busy)
pthread_cond_wait(&ep->notbusy, &lp->lm);
if (ep != NULL)
ep->busy = 1;
pthread_mutex_unlock(&lp->lm);
return(ep);
}
delete_elt(struct list *lp, struct elt *ep)
{
pthread_mutex_lock(&lp->lm);
assert(ep->busy);
... remove ep from list ...
ep->busy = 0; /* Paranoid. */
(A) pthread_cond_broadcast(&ep->notbusy);
pthread_mutex_unlock(&lp->lm);
(B) pthread_cond_destroy(&rp->notbusy);
free(ep);
}
In this example, the condition variable and its list element may be
freed (line B) immediately after all threads waiting for it are awakened
(line A), since the mutex and the code ensure that no other thread can
touch the element to be deleted.
...."