On Fri, Aug 28, 2009 at 1:17 PM, Pharaoh . <pharaoh137@xxxxxxxxx> wrote: > > > On Thu, Aug 27, 2009 at 12:02 PM, Pharaoh . <pharaoh137@xxxxxxxxx> wrote: >> >> >> 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: >>> > >>> > >>> > 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 ecartis@xxxxxxxxxxxx Please read the FAQ at http://kernelnewbies.org/FAQ
