I was going through an article on linux kernel radix tree implementation, link of article is mentioned below:
http://lwn.net/Articles/175432/
In this article it mentions that radix_tree_preload allocates sufficient memory so that the subsequent insertion in tree will not fail. Although it allocates the structures on per-CPU basis and hence the function returns with preemption disabled. It is the reponsibility of the caller to call radix_tree_preload_end in order to enable the preemption.
My question is:
1) Why radix_tree_preload allocates the structure on per-CPU basis?
2) When is the user supposed to call radix_tree_preload_end? Is it immediately after radix_tree_insert?
3) Does it not affect the performance as the radix trees are used for page cache operations and hence any insertion will cause the preemption to be disabled? Correct me if my understanding is wrong.
(1) To ensure that your request is executed as demanded, one CPU will handle the whole insertion sequence. If you move your process to a different CPU before the structure is fully initialized, the other CPU will work from its own per-CPU copy (for advantages of per-CPU variables, see also, eg, here) which will be different if some of the work was done on the initial CPU already.
(2) So you want to set aside enough memory, disable preemption, insert/delete, and then re-enable preemption, all in the context that originally started the sequence. This means that, yes, you _preload, _insert, then _preload_end right after to have your system benefit again from preemption as soon as possible.
(3) There is a small performance hit, but to ensure data integrity, if you choose per-CPU variables, this is hard (impossible) to avoid. The kernel developers must judge the benefits more important than the drawbacks, and they are generally right.