On Thu, Aug 27, 2009 at 12:34 AM, Mulyadi Santosa <mulyadi.sant...@gmail.com > wrote:
> On Wed, Aug 26, 2009 at 11:06 PM, Pharaoh .<pharaoh...@gmail.com> 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. > > > > > > -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.