On Thu, Aug 27, 2009 at 12:02 PM, Pharaoh . <[email protected]> wrote:
> > > On Thu, Aug 27, 2009 at 12:34 AM, Mulyadi Santosa < > [email protected]> wrote: > >> On Wed, Aug 26, 2009 at 11:06 PM, Pharaoh .<[email protected]> 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. > > How about RCU mechanism? I think using this I can design an efficient concurrently accessible rb tree. Any thoughts? -phraoh.
