On Sun, Dec 17, 2017 at 01:47:21PM +0000, Wang, Wei W wrote:> On Saturday, December 16, 2017 3:22 AM, Matthew Wilcox wrote: > > On Fri, Dec 15, 2017 at 10:49:15AM -0800, Matthew Wilcox wrote: > > > Here's the API I'm looking at right now. The user need take no lock; > > > the locking (spinlock) is handled internally to the implementation. > > Another place I saw your comment " The xb_ API requires you to handle your own locking" which seems conflict with the above "the user need take no lock". > Doesn't the caller need a lock to avoid concurrent accesses to the ida bitmap?Yes, the xb_ implementation requires you to handle your own locking. The xbit_ API that I'm proposing will take care of the locking for you. There's also no preallocation in the API.> We'll change it to "bool xb_find_set(.., unsigned long *result)", returning false indicates no "1" bit is found.I put a replacement proposal in the next paragraph: bool xbit_find_set(struct xbitmap *, unsigned long *start, unsigned long max); Maybe 'start' is the wrong name for that parameter. Let's call it 'bit'. It's both "where to start" and "first bit found".> > - xbit_clear() can't return an error. Neither can xbit_zero(). > > I found the current xbit_clear implementation only returns 0, and there isn't an error to be returned from this function. In this case, is it better to make the function "void"?Yes, I think so. My only qualm is that I've been considering optimising the memory consumption when an entire 1024-bit chunk is full; instead of keeping a pointer to a 128-byte entry full of ones, store a special value in the radix tree which means "every bit is set". The downside is that we then have to pass GFP flags to xbit_clear() and xbit_zero(), and they can fail. It's not clear to me whether that's a good tradeoff.> Are you suggesting to rename the current xb_ APIs to the above xbit_ names (with parameter changes)? > > Why would we need xbit_alloc, which looks like ida_get_new, I think set/clear should be adequate to the current usages.I'm intending on replacing the xb_ and ida_ implementations with this one. It removes the preload API which makes it easier to use, and it handles the locking for you. But I need to get the XArray (which replaces the radix tree) finished first.
On 12/18/2017 06:18 AM, Matthew Wilcox wrote:> On Sun, Dec 17, 2017 at 01:47:21PM +0000, Wang, Wei W wrote: >> On Saturday, December 16, 2017 3:22 AM, Matthew Wilcox wrote: >>> On Fri, Dec 15, 2017 at 10:49:15AM -0800, Matthew Wilcox wrote: >>> - xbit_clear() can't return an error. Neither can xbit_zero(). >> I found the current xbit_clear implementation only returns 0, and there isn't an error to be returned from this function. In this case, is it better to make the function "void"? > Yes, I think so. > > My only qualm is that I've been considering optimising the memory > consumption when an entire 1024-bit chunk is full; instead of keeping a > pointer to a 128-byte entry full of ones, store a special value in the > radix tree which means "every bit is set". > > The downside is that we then have to pass GFP flags to xbit_clear() and > xbit_zero(), and they can fail. It's not clear to me whether that's a > good tradeoff.Yes, this will sacrifice performance. In many usages, users may set bits one by one, and each time when a bit is set, it needs to scan the whole ida_bitmap to see if all other bits are set, if so, it can free the ida_bitmap. I think this extra scanning of the ida_bitmap would add a lot overhead.> >> Are you suggesting to rename the current xb_ APIs to the above xbit_ names (with parameter changes)? >> >> Why would we need xbit_alloc, which looks like ida_get_new, I think set/clear should be adequate to the current usages. > I'm intending on replacing the xb_ and ida_ implementations with this one. > It removes the preload API which makes it easier to use, and it handles > the locking for you. > > But I need to get the XArray (which replaces the radix tree) finished first.OK. It seems the new implementation wouldn't be done shortly. Other parts of this patch series are close to the end of review, and we hope to make some progress soon. Would it be acceptable that we continue with the basic xb_ implementation (e.g. as xbitmap 1.0) for this patch series? and xbit_ implementation can come as xbitmap 2.0 in the future? Best, Wei
On Mon, Dec 18, 2017 at 10:33:00AM +0800, Wei Wang wrote:> > My only qualm is that I've been considering optimising the memory > > consumption when an entire 1024-bit chunk is full; instead of keeping a > > pointer to a 128-byte entry full of ones, store a special value in the > > radix tree which means "every bit is set". > > > > The downside is that we then have to pass GFP flags to xbit_clear() and > > xbit_zero(), and they can fail. It's not clear to me whether that's a > > good tradeoff. > > Yes, this will sacrifice performance. In many usages, users may set bits one > by one, and each time when a bit is set, it needs to scan the whole > ida_bitmap to see if all other bits are set, if so, it can free the > ida_bitmap. I think this extra scanning of the ida_bitmap would add a lot > overhead.Not a huge amount of overhead. An ida_bitmap is only two cachelines, and the loop is simply 'check each word against ~0ul', so up to 16 load/test/loop instructions. Plus we have to do that anyway to maintain the free tag for IDAs.> > But I need to get the XArray (which replaces the radix tree) finished first. > > OK. It seems the new implementation wouldn't be done shortly. > Other parts of this patch series are close to the end of review, and we hope > to make some progress soon. Would it be acceptable that we continue with the > basic xb_ implementation (e.g. as xbitmap 1.0) for this patch series? and > xbit_ implementation can come as xbitmap 2.0 in the future?Yes, absolutely, I don't want to hold you up behind the XArray.