From mboxrd@z Thu Jan 1 00:00:00 1970 From: Tejun Heo Date: Wed, 19 Jun 2013 01:18:32 -0700 Subject: [Cluster-devel] [PATCH 10/10] idr: Rework idr_preload() In-Reply-To: <1371600150-23557-11-git-send-email-koverstreet@google.com> References: <1371600150-23557-1-git-send-email-koverstreet@google.com> <1371600150-23557-11-git-send-email-koverstreet@google.com> Message-ID: <20130619081832.GC30681@mtj.dyndns.org> List-Id: To: cluster-devel.redhat.com MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Hello, Kent. On Tue, Jun 18, 2013 at 05:02:30PM -0700, Kent Overstreet wrote: > With the new ida implementation, that doesn't work anymore - the new ida > code grows its bitmap tree by reallocating the entire thing in power of > two increments. Doh. So, I'm not sure about the single contiguous array implementation. It introduces some nasty characteristics such as possibly too large contiguous allocation, bursty CPU usages, and loss of the ability to handle ID allocations clustered in high areas - sure, the old ida wasn't great on that part either but this can be much worse. In addition, I'm not sure what this single contiguous allocation buys us. Let's say each leaf node size is 4k. Even with in-array tree implementation, it should be able to serve 2k IDs per-page, which would be enough for most use cases and with a bit of caching it can easily achieve both the performance benefits of array implementation and the flexibility of allocating each leaf separately. Even without caching, the tree depth would normally be much lower than the current implementation and the performance should be better. If you're bothered by having to implement another radix tree for it, it should be possible to just implement the leaf node logic and use the existing radix tree for internal nodes, right? > So we need a slightly different trick. Note that if all allocations from > an idr start by calling idr_prealloc() and disabling premption, at > most nr_cpus() allocations can happen before someone calls > idr_prealloc() again. But we allow mixing preloaded and normal allocations and users are allowed to allocate as many IDs they want after preloading. It should guarantee that the first allocation after preloading follows the stronger allocation flag, and the above approach can't guarantee that. You can declare that if preload is to work, all allocators of the ida should preload and enforce it but that restriction arises only because you're using this single array implementation. It's another drawback of this particular approach. There seem to be a lot of cons and I can't really see what the pros are. Thanks. -- tejun