On Fri, Aug 28, 2009 at 1:17 PM, Pharaoh . wrote:
>
>
> On Thu, Aug 27, 2009 at 12:02 PM, Pharaoh . wrote:
>>
>>
>> On Thu, Aug 27, 2009 at 12:34 AM, Mulyadi Santosa
>> wrote:
>>>
>>> On Wed, Aug 26, 2009 at 11:06 PM, Pharaoh . wrote:
>>> >
>>> >
>>> > Hi list,
>>> >
>>> > 1. A cpu can access its own per cpu data atomically but if it has to
>>> > access
>>> > other cpus per cpu data
>>> > it might not be atomically accessed. Is this correct?
>>>
>>> IMO, assuming your per CPU data is something simple like word length
>>> (4 byte in x86 32 bit), then yes local access to per CPU data is
>>> atomic. But it can not be atomic if it's accessing complex data
>>> structure.
>>>
>>> And IIRC, per CPU API are written to store and retrieve simple type of
>>> data.
>>>
>>> If you're accessing other CPU data, I guess it still might done
>>> "atomically" by doing lock (e.g spinlock). But yes, without lock, you
>>> have to careful about race condition
>>>
>>> >If my driver makes
>>> > sure that no cpu accesses
>>> > other cpu's per cpu data my code can be entirely lockless? Correct?
>>>
>>> IMO yes. Just make sure you use provided per CPU API. IIRC, when
>>> you're accessing per CPU data using the APIs, it will also disable
>>> preemption..thus preventing your code to be migrated to other
>>> core/CPU.
>>>
>>> > 2. Can I have a rather complex data structure like a radix tree as a
>>> > per cpu
>>> > data structure?
>>>
>>> Ehm, I don't think so. Well, theoritically you can but IIRC the kernel
>>> doesn't provide such API to store and retrieve such data structure by
>>> default.
>>>
>>> > 3. Is it guaranteed that all the accesses happening to this tree from a
>>> > cpu
>>> > which allocated it are atomic?
>>> > I think they are atomic since the per cpu data access functions disable
>>> > preemption.
>>> >
>>> >
>>> > My main objective is to have a radix tree which will be accessed on
>>> > multiple
>>> > cores, I want to avoid the
>>> > locking overhead of keeping a central lock for accessing this tree. I
>>> > have
>>> > just started investigating the
>>> > possibilities.
Hi,
I was reading about lockless pagecache and seems it tries to do what
you want. You can have a look at its code. See the link
ftp://ftp.kernel.org/pub/linux/kernel/people/npiggin/patches/lockless/2.6.16-rc5/radix-intro.pdf
. Also search google for "lockless pagecache protocol"
Thanks -
Manish
>>> >
>>> >
>>> > -pharaoh.
>>> >
>>>
>>>
>>>
>>>
>>> --
>>> regards,
>>>
>>> Mulyadi Santosa
>>> Freelance Linux trainer
>>> blog: the-hydra.blogspot.com
>>
>>
>> More generically put, how is a highly concurrent data structure designed
>> in kernel space?
>>
>> If I keep a central lock for accessing the radix tree, wont it cause too
>> much latency?
>> I am sure there must be some other way which I am not aware of. Using
>> read/write locks
>> might be better idea so that atleast reads can happen concurrently.
>>
>> E.g. userspace concurrent programs have a concept of thread local storage,
>> so each thread acccesses
>> its own copy.
>>
>> If Linux is able to run on hundreds of cores, I am sure there must be a
>> way to an optimal way to access
>> these concurrent data structures.
>>
>>
>> -pharaoh.
>>
>
> How about RCU mechanism?
>
> I think using this I can design an efficient concurrently accessible rb
> tree.
> Any thoughts?
>
> -phraoh.
>
--
Thanks -
Manish
--
To unsubscribe from this list: send an email with
"unsubscribe kernelnewbies" to ecar...@nl.linux.org
Please read the FAQ at http://kernelnewbies.org/FAQ
