On Thu, Aug 27, 2009 at 12:02 PM, Pharaoh . <pharaoh137@xxxxxxxxx> wrote:
More generically put, how is a highly concurrent data structure designed in kernel space?On Thu, Aug 27, 2009 at 12:34 AM, Mulyadi Santosa <mulyadi.santosa@xxxxxxxxx> wrote:
On Wed, Aug 26, 2009 at 11:06 PM, Pharaoh .<pharaoh137@xxxxxxxxx> wrote:IMO, assuming your per CPU data is something simple like word length
>
>
> 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?
(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
IMO yes. Just make sure you use provided per CPU API. IIRC, when
>If my driver makes
> sure that no cpu accesses
> other cpu's per cpu data my code can be entirely lockless? Correct?
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.
Ehm, I don't think so. Well, theoritically you can but IIRC the kernel
> 2. Can I have a rather complex data structure like a radix tree as a per cpu
> data structure?
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.
>
>
> -pharaoh.
>
--
regards,
Mulyadi Santosa
Freelance Linux trainer
blog: the-hydra.blogspot.com
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.
