[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.programming.threads

Questions on SMR

Matt Taylor

8/5/2004 8:24:00 PM

So, I've read a bit of the information that was posted in my last
question -- many thanks to all who replied! I was looking at SMR,
particularly because the guarantees it makes are attractive and because the
performance is good. I pulled up a paper by Maged M. Michael on SMR ("Hazard
Pointers: Safe Memory Reclamation for Lock-Free Objects") and have a
rudimentary understanding of how it works now.

SMR cannot ever free hazard pointer structures, right? If I hit a degenerate
case and have to allocate a large number of these, then they are permanently
locked in.

Also, perhaps my understanding is flawed, but does SMR put no bound on the
amount of time before memory is reclaimed in the absense of thread failures?
What I mean is that it seems that an object may be marked for deletion and
still not deleted even if all hazard pointers to it are released. If hazard
pointers still point to the object when it is marked for deletion, then it
is only queued for deletion. Until the thread that marked it for deletion
returns to re-evaluate the object, it will not be deleted. If the thread
does not return to re-evaluate the object for deletion, then its deletion
may be postponed indefinitely, even though the maximum number of objects for
which this can occur is bounded.

-Matt
17 Answers

Joe Seigh

8/5/2004 9:39:00 PM

0



Matt Taylor wrote:
>
> So, I've read a bit of the information that was posted in my last
> question -- many thanks to all who replied! I was looking at SMR,
> particularly because the guarantees it makes are attractive and because the
> performance is good. I pulled up a paper by Maged M. Michael on SMR ("Hazard
> Pointers: Safe Memory Reclamation for Lock-Free Objects") and have a
> rudimentary understanding of how it works now.
>
> SMR cannot ever free hazard pointer structures, right? If I hit a degenerate
> case and have to allocate a large number of these, then they are permanently
> locked in.
>
No, there's no reason you cannot deallocate them if no threads are going to
use them any more. Whether you have a mechanism to do it and whether it's
worth it is another matter. It would depend on your implementation.


> Also, perhaps my understanding is flawed, but does SMR put no bound on the
> amount of time before memory is reclaimed in the absense of thread failures?
> What I mean is that it seems that an object may be marked for deletion and
> still not deleted even if all hazard pointers to it are released. If hazard
> pointers still point to the object when it is marked for deletion, then it
> is only queued for deletion. Until the thread that marked it for deletion
> returns to re-evaluate the object, it will not be deleted. If the thread
> does not return to re-evaluate the object for deletion, then its deletion
> may be postponed indefinitely, even though the maximum number of objects for
> which this can occur is bounded.
>

Just for that object. You have the same problem with Boehm GC. That's not
considered a big problem. It is a problem for proxy GC schemes like RCU
which has various schemes to deal with it.

Joe Seigh

Mouse

8/6/2004 12:57:00 AM

0

> No, there's no reason you cannot deallocate them if no threads are going
to
> use them any more. Whether you have a mechanism to do it and whether it's
> worth it is another matter. It would depend on your implementation.

If you delete a hazard pointer record, a thread could crash. This is only
true if you use the HelpScan function the paper describes.

Multiple threads can be iterating the global lock-free list of hazards. The
list is suppose to be lock-free ( for the HelpScan function ), so locks are
out of the question... you could protect the list with a lock-free proxy gc,
or atomic_ptr each of the hazard pointer records.

Joe Seigh

8/6/2004 1:40:00 AM

0



SenderX wrote:
>
> > No, there's no reason you cannot deallocate them if no threads are going
> to
> > use them any more. Whether you have a mechanism to do it and whether it's
> > worth it is another matter. It would depend on your implementation.
>
> If you delete a hazard pointer record, a thread could crash. This is only
> true if you use the HelpScan function the paper describes.
>
> Multiple threads can be iterating the global lock-free list of hazards. The
> list is suppose to be lock-free ( for the HelpScan function ), so locks are
> out of the question... you could protect the list with a lock-free proxy gc,
> or atomic_ptr each of the hazard pointer records.

I'm not sure what Michael does in his implementation but you can coordinate
the hazard pointers any way you want. Just register the hazard pointers
before you use them and unregister them when you are finished. Normal locking
will work. I'm refering to the structures that the threads store their
references in so the GC routine knows what's being referenced, not the potential
references themselves.

Joe Seigh

Matt Taylor

8/6/2004 4:02:00 PM

0

"Joe Seigh" <jseigh_01@xemaps.com> wrote in message
news:4112AB12.CCADFC10@xemaps.com...
>
>
> Matt Taylor wrote:
> >
> > So, I've read a bit of the information that was posted in my last
> > question -- many thanks to all who replied! I was looking at SMR,
> > particularly because the guarantees it makes are attractive and because
the
> > performance is good. I pulled up a paper by Maged M. Michael on SMR
("Hazard
> > Pointers: Safe Memory Reclamation for Lock-Free Objects") and have a
> > rudimentary understanding of how it works now.
> >
> > SMR cannot ever free hazard pointer structures, right? If I hit a
degenerate
> > case and have to allocate a large number of these, then they are
permanently
> > locked in.
> >
> No, there's no reason you cannot deallocate them if no threads are going
to
> use them any more. Whether you have a mechanism to do it and whether it's
> worth it is another matter. It would depend on your implementation.

Wouldn't that run into the same memory management problems that plague
lockless structures in general? Either one would have to lock the hazard
list or use a scheme like RCU.

> > Also, perhaps my understanding is flawed, but does SMR put no bound on
the
> > amount of time before memory is reclaimed in the absense of thread
failures?
> > What I mean is that it seems that an object may be marked for deletion
and
> > still not deleted even if all hazard pointers to it are released. If
hazard
> > pointers still point to the object when it is marked for deletion, then
it
> > is only queued for deletion. Until the thread that marked it for
deletion
> > returns to re-evaluate the object, it will not be deleted. If the thread
> > does not return to re-evaluate the object for deletion, then its
deletion
> > may be postponed indefinitely, even though the maximum number of objects
for
> > which this can occur is bounded.
> >
>
> Just for that object. You have the same problem with Boehm GC. That's
not
> considered a big problem. It is a problem for proxy GC schemes like RCU
> which has various schemes to deal with it.

I know it is not considered a big problem; however, it would be desirable to
collect objects when they are freed and not delay (possibly infinitely).
This is especially true for me since each object may be quite large. The
structures holds per-thread data for a debugger that is similar to valgrind
in function, except it is completely threaded. The per-thread structure
holds an instruction backtrace cache of user configurable size. (I typically
set this to 1 million which is 44MB *per* thread.) There are some other
structures which are managed in a similar fashion and can grow quite large.
Thus it is rather important to me to free these in a timely manner lest I
exhaust memory.

This is also why I asked about the inability to free HPs. If HPs can be
freed, then I can simply allocate a few as part of my thread structure and
free them when the thread cleans itself up. This element is not as
important: since HPs are small, it is of minor consequence if they stick
around. I only need to protect thread creation/deletions, so unless the app
is something akin to a fork() bomb, I shouldn't need many HPs.

I am thinking that there should exist some method of extension to SMR with
R=1 that, in the absense of thread delays/crashes, would guarantee bounded
time before an object is considered available for reuse. Have none been
documented? I have a rough idea of how it might be done.

-Matt

Joe Seigh

8/6/2004 4:31:00 PM

0



Matt Taylor wrote:
>
> "Joe Seigh" <jseigh_01@xemaps.com> wrote in message
> news:4112AB12.CCADFC10@xemaps.com...
> >
> >
> > No, there's no reason you cannot deallocate them if no threads are going
> to
> > use them any more. Whether you have a mechanism to do it and whether it's
> > worth it is another matter. It would depend on your implementation.
>
> Wouldn't that run into the same memory management problems that plague
> lockless structures in general? Either one would have to lock the hazard
> list or use a scheme like RCU.

I'm not sure what everyone thinks is the problem here. There's nothing that
says you can't use locks as part of an SMR implementation. I use locks
in my RCU implementations to manage a list of per thread data structures.
The locks aren't used in RCU read critical regions so there is no performance
issues because of them.

....

> > Just for that object. You have the same problem with Boehm GC. That's
> not
> > considered a big problem. It is a problem for proxy GC schemes like RCU
> > which has various schemes to deal with it.
>
> I know it is not considered a big problem; however, it would be desirable to
> collect objects when they are freed and not delay (possibly infinitely).

With time sliced threading you have that problem with any scheme that allows
a thread to get suspended while accessing a resource. There are various schemes
that have been used to try to deal with it like priority inheritance for locks
or disabling interrupts.

You don't notice the problem with conventional locking because what happens is that
if most of the threads end up blocking on the lock, it's more likely the thread
holding the lock will get dispatched again simply because there are no other threads
for the dispatcher to run.

RCU in the kernel doesn't have this problem since for the most part, RCU quiescent
states happen quite frequently. There are some kernel threads that run longer than
they should but I believe they are working on voluntary preemption to help deal with
that since it causes other problems for the kernel.

There are other ways of dealing with the problem but it would probably require
modifications to the kernel.

Joe Seigh

Ronald Landheer-Cieslak

8/6/2004 8:36:00 PM

0

Joe Seigh wrote:

>
> SenderX wrote:
>
>>>No, there's no reason you cannot deallocate them if no threads are going
>>
>>to
>>
>>>use them any more. Whether you have a mechanism to do it and whether it's
>>>worth it is another matter. It would depend on your implementation.
>>
>>If you delete a hazard pointer record, a thread could crash. This is only
>>true if you use the HelpScan function the paper describes.
>>
>>Multiple threads can be iterating the global lock-free list of hazards. The
>>list is suppose to be lock-free ( for the HelpScan function ), so locks are
>>out of the question... you could protect the list with a lock-free proxy gc,
>>or atomic_ptr each of the hazard pointer records.
>
>
> I'm not sure what Michael does in his implementation but you can coordinate
> the hazard pointers any way you want. Just register the hazard pointers
> before you use them and unregister them when you are finished. Normal locking
> will work. I'm refering to the structures that the threads store their
> references in so the GC routine knows what's being referenced, not the potential
> references themselves.
IIRC, MM Micheal has a static amount of hazard pointers - bound to the
maximal number of threads he will use.

My implementation (libmemory, CVS at
http://cvs.sourceforge.net/viewcvs.py/jail-ust/...) uses a
singly-linked list of hazard pointer-containing structures (one
structure per thread, a fixed number of hazard pointers per structure -
the number to use is passed as an argument to the library initialisation
routine)

Also, on thread death, my implementation will try to delete every
remaining queued deletion. I'm actually not sure that that's a good
idea, but I guess it seemed so at the time ;)

rlc

Ronald Landheer-Cieslak

8/6/2004 8:47:00 PM

0

Matt Taylor wrote:

> So, I've read a bit of the information that was posted in my last
> question -- many thanks to all who replied! I was looking at SMR,
> particularly because the guarantees it makes are attractive and because the
> performance is good. I pulled up a paper by Maged M. Michael on SMR ("Hazard
> Pointers: Safe Memory Reclamation for Lock-Free Objects") and have a
> rudimentary understanding of how it works now.
>
> SMR cannot ever free hazard pointer structures, right? If I hit a degenerate
> case and have to allocate a large number of these, then they are permanently
> locked in.
The per-thread hazard pointers can be deleted when the thread dies (when
there is no longer any need for them) - though that depends on how you
implement them. In MM Micheal's proposed implementation, IIRC, they're
in a static array, so their life-time would be the same as the process'

As for whatever those pointers point to - as long as there are hazardous
references to an object, the object's memory can not be freed.

> Also, perhaps my understanding is flawed, but does SMR put no bound on the
> amount of time before memory is reclaimed in the absense of thread failures?
> What I mean is that it seems that an object may be marked for deletion and
> still not deleted even if all hazard pointers to it are released. If hazard
> pointers still point to the object when it is marked for deletion, then it
> is only queued for deletion. Until the thread that marked it for deletion
> returns to re-evaluate the object, it will not be deleted. If the thread
> does not return to re-evaluate the object for deletion, then its deletion
> may be postponed indefinitely, even though the maximum number of objects for
> which this can occur is bounded.
The only way you could "fix" this is by allowing other threads to access
the same dlist - i.e. make it a single, global list. It's possible, but
it presents a chicken-and-egg problem if you want that list to be
dynamic and non-blocking.. (I.e. how are you going to handle its memory
- with SMR?)

Of course, you could use an rw-lock on the global dlist and w-lock it
only when you resize it - e.g. for starting a new thread, which would
allocate new hptrs.

Or, you could do what I do in my smr implementation for the local lists
- i.e. check their size when they fill up and swap for a new one - it
should be rather trivial to change that to doing it on a global list.
I.e., if you want, you can write the patch and I'll write you a GPL
waiver :)

rlc

Matt Taylor

8/8/2004 10:49:00 PM

0

"Ronald Landheer-Cieslak" <ronald@landheer.com> wrote in message
news:2ni98gF18vknU1@uni-berlin.de...
> Matt Taylor wrote:
>
> > So, I've read a bit of the information that was posted in my last
> > question -- many thanks to all who replied! I was looking at SMR,
> > particularly because the guarantees it makes are attractive and because
the
> > performance is good. I pulled up a paper by Maged M. Michael on SMR
("Hazard
> > Pointers: Safe Memory Reclamation for Lock-Free Objects") and have a
> > rudimentary understanding of how it works now.
> >
> > SMR cannot ever free hazard pointer structures, right? If I hit a
degenerate
> > case and have to allocate a large number of these, then they are
permanently
> > locked in.
> The per-thread hazard pointers can be deleted when the thread dies (when
> there is no longer any need for them) - though that depends on how you
> implement them. In MM Micheal's proposed implementation, IIRC, they're
> in a static array, so their life-time would be the same as the process'

He also mentions a linked list extension but gives no information with
regard to freeing the HPs in the list. His pseudocode only allocates and
releases them; it never frees.

So in your libmemory, the relevant functions are hptr_register and
hptr_free? What would happen if a thread were exiting as other threads were
traversing the HP list? Seems to me that it's possible to crash if a thread
was switched out while traversing the HP list and another thread exited.

> As for whatever those pointers point to - as long as there are hazardous
> references to an object, the object's memory can not be freed.
>
> > Also, perhaps my understanding is flawed, but does SMR put no bound on
the
> > amount of time before memory is reclaimed in the absense of thread
failures?
> > What I mean is that it seems that an object may be marked for deletion
and
> > still not deleted even if all hazard pointers to it are released. If
hazard
> > pointers still point to the object when it is marked for deletion, then
it
> > is only queued for deletion. Until the thread that marked it for
deletion
> > returns to re-evaluate the object, it will not be deleted. If the thread
> > does not return to re-evaluate the object for deletion, then its
deletion
> > may be postponed indefinitely, even though the maximum number of objects
for
> > which this can occur is bounded.
> The only way you could "fix" this is by allowing other threads to access
> the same dlist - i.e. make it a single, global list. It's possible, but
> it presents a chicken-and-egg problem if you want that list to be
> dynamic and non-blocking.. (I.e. how are you going to handle its memory
> - with SMR?)
[...]

What I was thinking was to have threads pass off responsibility for the
object. HPs would be extended with an ownership tag. If the tag is set, the
thread that owns the HP has to execute a scan on the object when the HP is
cleared. The maximum time complexity for deletion of one object is linear --
it is equal to the length of the HP list at the time the object was marked
for deletion.

Upon finding an HP that referenced an object pending deletion, the thread
would test-and-set its ownership tag and then verify that the HP was still
active. If not, then the ownership tag is checked to see whether or not the
other thread saw the test-and-set before it freed the HP. If still set, then
the search continues as the HP has been freed and the object has not. In the
other two cases, the responsibility of deleting the object has been
successfully passed to the thread that owns the HP.

While I have talked of test-and-set and an ownership flag, I suspect a
working implementation would need to use CAS or possibly a double-width CAS
in order to prevent race conditions on the hand-off. The problem is, of
course, that an object can be passed off to an HP that is in the middle of
being recycled (though not yet seen by the thread). I have a few ideas on
alternate ways to implement this (perhaps an auxillary pointer that is set
to point to the object to indicate possession), but as of yet none that
would actually work.

-Matt

Joe Seigh

8/9/2004 12:11:00 PM

0



Matt Taylor wrote:
>
> "Ronald Landheer-Cieslak" <ronald@landheer.com> wrote in message
> news:2ni98gF18vknU1@uni-berlin.de...
> > The per-thread hazard pointers can be deleted when the thread dies (when
> > there is no longer any need for them) - though that depends on how you
> > implement them. In MM Micheal's proposed implementation, IIRC, they're
> > in a static array, so their life-time would be the same as the process'
>
> He also mentions a linked list extension but gives no information with
> regard to freeing the HPs in the list. His pseudocode only allocates and
> releases them; it never frees.
>
> So in your libmemory, the relevant functions are hptr_register and
> hptr_free? What would happen if a thread were exiting as other threads were
> traversing the HP list? Seems to me that it's possible to crash if a thread
> was switched out while traversing the HP list and another thread exited.
>


You'd need two hazard pointers per thread for scanning the hazard pointer
list. These hazard pointers could themselves never be deleted.

Other than those two special hazard pointers, you can't have any other
hazard pointers set when you scan the list as you would risk deadlock.

Joe Seigh

Joe Seigh

8/9/2004 4:48:00 PM

0




> You'd need two hazard pointers per thread for scanning the hazard pointer
> list. These hazard pointers could themselves never be deleted.
>
> Other than those two special hazard pointers, you can't have any other
> hazard pointers set when you scan the list as you would risk deadlock.
>

It would be easier to set up the permannent hazard pointers in a separate
list. You wouldn't need hazard pointers to scan that list.

I don't think it's worth all that trouble. Just don't decallocate hazard
pointers ever. End of problem.

Joe Seigh