Set-and-test vs. a lock
Unknown
but that I wasn't taught in school and so had taken for granted. It's
a set-and-test (as opposed to the bad test-and-set that creates
races). I think it can synchronize access to a shared resource
without a lock as long as operations are in the right order (set
before test), there are memory barriers after the sets, and at least
one of the threads can always fail to acquire the resource.
For instance, here's a case where thread_a is responsible for
processing the requests received by a module and thread_b is
responsible for shutting down the module in preparation for unloading
it:
thread_a:
atomic_increment(in_use) (implies memory barrier)
if shutting_down then
atomic_decrement(in_use)
fail
else
<process next request>
if atomic_decrement(in_use) == 0 then
set event go_shutdown
endif
endif
thread_b:
clear event go_shutdown
shutting_down = true (with memory barrier)
if in_use > 0 then
wait on event go_shutdown
endif
<do thread_b shutdown business>
The idea is that "in_use" is a reference count for the module, and the
module can't be unloaded while it is still referenced. Once a
shutdown begins, new attempts to reference the module will begin
failing, and when there are no more references then the shutdown will
proceed.
Is this useful because it eliminates the overhead of a lock or
confusing because of the need for an explicit memory barrier? Is
there a reason to prefer the way with locks:
thread_a:
acquire inuse_lock
if shutting_down then
error = true
else
in_use++
endif
release inuse_lock
if error then
fail
else
<process next request>
acquire inuse_lock
in_use--
in_use == 0 then
set event go_shutdown
endif
release inuse_lock
endif
thread_b:
clear event go_shutdown
acquire inuse_lock
shutting_down = true
in_use_peek = in_use
release inuse_lock
if in_use_peek > 0 then
wait on event go_shutdown
endif
<do thread_b shutdown business>
?
Joe Seigh
> I recently noticed a paradigm for synchronization that might be common
> but that I wasn't taught in school and so had taken for granted. It's
> a set-and-test (as opposed to the bad test-and-set that creates
> races). I think it can synchronize access to a shared resource
> without a lock as long as operations are in the right order (set
> before test), there are memory barriers after the sets, and at least
> one of the threads can always fail to acquire the resource.
>
> The idea is that "in_use" is a reference count for the module, and the
> module can't be unloaded while it is still referenced. Once a
> shutdown begins, new attempts to reference the module will begin
> failing, and when there are no more references then the shutdown will
> proceed.
>
> Is this useful because it eliminates the overhead of a lock or
> confusing because of the need for an explicit memory barrier? Is
> there a reason to prefer the way with locks:
I don't know how common it is but what you are describing is basically a
lock-free reader/writer solutions where the readers don't have to
use locks. The writers may or may not be lock-free.
Basically these solutions use some form of PDR (PCOW (partial copy on write)
deferred reclaimation) to safely deallocate objects that are no longer referenced.
Forms of PDR can include GC, RCU, SMR hazard pointers, RCU+SMR, VZOOM, proxy
collectors and atomically thread-safe reference counting (which can include
PDR based refcounting like rcuref in the Linux kernel).
The Linux kernel uses rcuref to safely increment use counts for unloadable
modules and avoid race conditions.
Memory barriers are the usual acquire and release semantics on pointer
loads and unloads.
See http://atomic-ptr-plus.sourceforge.net/ for some
experimental implementations.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software.
Unknown
wrote:
I don't know all the terminology, but what I see in the Linux module
unload looks like the second way I mentioned, with a lock.
try_module_get() looks like what I called thread_a. It disables
preemption (what I called acquiring the lock) while it tests
mod->state (what I called shutting_down) and increments
module->ref[...].count (what I called in_use).
sys_delete_module() looks like what I called thread_b. It calls
try_stop_module(), which disables preemption on every CPU (what I
called acquiring the lock) and sets mod->state (what I called
shutting_down). It then calls wait_for_zero_refcount(), which tests
mod->ref[...].count (what I called in_use) and waits for it to reach 0
(what I called waiting on go_shutdown).
I guess I didn't really need to capture in_use_peek inside the lock,
but this second way wasn't what I really found interesting, and the
disabling of preemption is even less concurrency than the normal way
that I expected with a lock.
I was excited to see how common the first way was. Is there some
other part of the kernel that might do it?
Joe Seigh
Joe Seigh
There was some discussion elsewhere that RCU was used to safely
handle module use counts but maybe not. See the references on
atomic_ptr_plus site for more information. Or google lock-free.
(ignore the prior premature response. It's sort of a Firefox problem.)
Unknown
wrote:
>See http://atomic-ptr-plus.sourceforge.net/ for some
>experimental implementations.
I just noticed. Patents on these cool algorithms? Dude, patents
aren't cool. The coolest thing to do is to create something really
good while maintaining as much anonymity as possible, with little
praise or money. When one becomes nothing, one becomes everything.
Joe Seigh
The patents I did were way back before patents became controversial.
There was one algorithm I deliberately didn't play up so it wouldn't
get classified as something to patent, because it was too cool to
patent. Turned out to not be as useful as the others maybe. Most
of the patents listed are by others because most companies require
you to disclose and patent anything you come up with. The whole
patent situations has gone beyond anything you can deal rationally with,
so basically I'm just ignoring patents. I just list them for
informational purposes. Forbes lists the world's richest people,
i.e. the people who own the world. I'm listing the lock-free patents,
i.e. the companies who own multi-threaded programming.
Markus Elfring
> but that I wasn't taught in school and so had taken for granted. It's
> a set-and-test (as opposed to the bad test-and-set that creates races).
Why do you think that there are problematic race conditions in this use case?
http://en.wikipedia.org/wiki/Test-and-set
Regards,
Markus
av
what is "race condition"?
Bin Chen
Unknown
>I guess I didn't really need to capture in_use_peek inside the lock,
>but this second way wasn't what I really found interesting, and the
>disabling of preemption is even less concurrency than the normal way
>that I expected with a lock.
I didn't say that right. A spin lock may have been appropriate for
this situation because the wait is so short, and a spin lock would
have disabled preemption too, except it would have done it on every
CPU that was trying to get a reference to the module. I think I see
the cool trick that's done in try_module_get() is to only disable
preemption on the current CPU and update a corresponding reference
count, so the price of disabling preemption on every CPU is only paid
when the module is unloaded, which should happen less often than it
being referenced.
Okay, so it's an efficient lock, but it's still a lock in software (as
opposed to raw atomic operations in hardware).
Unknown
I was referring to a non-atomic test-and-set, where the test and set
are separate operations, at least two separate CPU instructions that
could have other intervening instructions between them.
A non-atomic test-and-set can have up to two winners (bad).
An atomic test-and-set can only have one winner (good).
A non-atomic set-and-test can have up to two losers (good, sometimes).
An atomic set-and-test can only have one winner (good).
Chris Thomasson
<BubbaGump> wrote in message
news:ogp0o2t6do3ha4sps...@4ax.com...
I patented my memory allocator and vZOOM algorithm so I could actually use
them in commercial products. I wanted something to assert that my work is
owned be me.
I don't see ANYTHING wrong with that.
Ben Pfaff
> I patented my memory allocator and vZOOM algorithm so I could actually use
> them in commercial products. I wanted something to assert that my work is
> owned be me.
A patent does not allow you to use an invention. It only allows
you to prevent others from using that invention.
--
Ben Pfaff
email: b...@cs.stanford.edu
web: http://benpfaff.org
Chris Thomasson
news:871wn1f...@blp.benpfaff.org...
> "Chris Thomasson" <cri...@comcast.net> writes:
>
>> I patented my memory allocator and vZOOM algorithm so I could actually
>> use
>> them in commercial products. I wanted something to assert that my work is
>> owned be me.
>
> A patent does not allow you to use an invention. It only allows
> you to prevent others from using that invention.
Its good to be in control of your inventions.
Steve Watt
Ben Pfaff <b...@cs.stanford.edu> wrote:
>"Chris Thomasson" <cri...@comcast.net> writes:
>
>> I patented my memory allocator and vZOOM algorithm so I could actually use
>> them in commercial products. I wanted something to assert that my work is
>> owned be me.
>
>A patent does not allow you to use an invention. It only allows
>you to prevent others from using that invention.
It does both, indirectly.
If you use your invention in a place where it's visible, and someone else sees
how it works and decides to patent it when you hadn't, you've suddenly lost
the ability to use it. The USPTO is entirely too willing to grant patents on
"inventions" that have decades-old prior art or are obvious to a practitioner
in the field.
--
Steve Watt KD6GGD PP-ASEL-IA ICBM: 121W 56' 57.5" / 37N 20' 15.3"
Internet: steve @ Watt.COM Whois: SW32-ARIN
Free time? There's no such thing. It just comes in varying prices...
Ben Pfaff
> In article <871wn1f...@blp.benpfaff.org>,
> Ben Pfaff <b...@cs.stanford.edu> wrote:
>>"Chris Thomasson" <cri...@comcast.net> writes:
>>
>>> I patented my memory allocator and vZOOM algorithm so I could actually use
>>> them in commercial products. I wanted something to assert that my work is
>>> owned be me.
>>
>>A patent does not allow you to use an invention. It only allows
>>you to prevent others from using that invention.
>
> It does both, indirectly.
If an implementation of your patented invention infringes on
someone else's patent, you don't have the right to use your
invention without a license for that patent. But you can still
prevent others from using your invention.
Hence, what I said above.
> If you use your invention in a place where it's visible, and someone else sees
> how it works and decides to patent it when you hadn't, you've suddenly lost
> the ability to use it.
It's a crime to attempt to patent something that you didn't
invent.
Steve Watt
Ben Pfaff <b...@cs.stanford.edu> wrote:
>Steve Watt <steve.re...@Watt.COM> writes:
>
>> In article <871wn1f...@blp.benpfaff.org>,
>> Ben Pfaff <b...@cs.stanford.edu> wrote:
>>>"Chris Thomasson" <cri...@comcast.net> writes:
>>>
>>>> I patented my memory allocator and vZOOM algorithm so I could actually use
>>>> them in commercial products. I wanted something to assert that my work is
>>>> owned be me.
>>>
>>>A patent does not allow you to use an invention. It only allows
>>>you to prevent others from using that invention.
>>
>> It does both, indirectly.
>
>If an implementation of your patented invention infringes on
>someone else's patent, you don't have the right to use your
>invention without a license for that patent. But you can still
>prevent others from using your invention.
>
>Hence, what I said above.
Thanks for the clarification; what you said makes more sense.
>> If you use your invention in a place where it's visible, and someone else sees
>> how it works and decides to patent it when you hadn't, you've suddenly lost
>> the ability to use it.
>
>It's a crime to attempt to patent something that you didn't
>invent.
True 'nuff. Speeding's a crime, too. Speeding occurs much more
frequently than fraudulent patent applications, but I know both
happen...
av
>In article <871wn1f...@blp.benpfaff.org>,
>Ben Pfaff <b...@cs.stanford.edu> wrote:
>>"Chris Thomasson" <cri...@comcast.net> writes:
>>
>>> I patented my memory allocator and vZOOM algorithm so I could actually use
>>> them in commercial products. I wanted something to assert that my work is
>>> owned be me.
>>
>>A patent does not allow you to use an invention. It only allows
>>you to prevent others from using that invention.
>
>It does both, indirectly.
>
>If you use your invention in a place where it's visible, and someone else sees
>how it works and decides to patent it when you hadn't, you've suddenly lost
>the ability to use it.
excuse me, but it should be impossible to patent something inveted
first in the time, from some other