Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-18 Thread Wei Wang
On 12/17/2017 11:16 PM, Tetsuo Handa wrote: Wang, Wei W wrote: Wei Wang wrote: But passing GFP_NOWAIT means that we can handle allocation failure. There is no need to use preload approach when we can handle allocation failure. I think the reason we need xb_preload is because radix tree

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-17 Thread Matthew Wilcox
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

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-17 Thread Wei Wang
On 12/18/2017 06:18 AM, Matthew Wilcox wrote: On Sun, Dec 17, 2017 at 01:47:21PM +, 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

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-17 Thread Matthew Wilcox
On Sun, Dec 17, 2017 at 01:47:21PM +, 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)

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-17 Thread Tetsuo Handa
Wang, Wei W wrote: > > Wei Wang wrote: > > > > But passing GFP_NOWAIT means that we can handle allocation failure. > > > > There is no need to use preload approach when we can handle allocation > > > > failure. > > > > > > I think the reason we need xb_preload is because radix tree insertion > >

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-17 Thread Wang, Wei W
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

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-17 Thread Wang, Wei W
> -Original Message- > From: Tetsuo Handa [mailto:penguin-ker...@i-love.sakura.ne.jp] > Sent: Sunday, December 17, 2017 6:22 PM > To: Wang, Wei W ; wi...@infradead.org > Cc: virtio-...@lists.oasis-open.org; linux-ker...@vger.kernel.org; qemu- > de...@nongnu.org;

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-17 Thread Tetsuo Handa
Wei Wang wrote: > > But passing GFP_NOWAIT means that we can handle allocation failure. There is > > no need to use preload approach when we can handle allocation failure. > > I think the reason we need xb_preload is because radix tree insertion > needs the memory being preallocated already (it

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-16 Thread Wei Wang
On 12/16/2017 07:28 PM, Tetsuo Handa wrote: Wei Wang wrote: On 12/16/2017 02:42 AM, Matthew Wilcox wrote: On Tue, Dec 12, 2017 at 07:55:55PM +0800, Wei Wang wrote: +int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp); I'm struggling to understand when one would use this.

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-16 Thread Tetsuo Handa
Wei Wang wrote: > On 12/16/2017 02:42 AM, Matthew Wilcox wrote: > > On Tue, Dec 12, 2017 at 07:55:55PM +0800, Wei Wang wrote: > >> +int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp); > > I'm struggling to understand when one would use this. The xb_ API > > requires you to

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-16 Thread Wei Wang
On 12/15/2017 12:29 AM, Tetsuo Handa wrote: Wei Wang wrote: I used the example of xb_clear_bit_range(), and xb_find_next_bit() is the same fundamentally. Please let me know if anywhere still looks fuzzy. I don't think it is the same for xb_find_next_bit() with set == 0. + if

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-16 Thread Wei Wang
On 12/16/2017 02:42 AM, Matthew Wilcox wrote: On Tue, Dec 12, 2017 at 07:55:55PM +0800, Wei Wang wrote: +int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp); I'm struggling to understand when one would use this. The xb_ API requires you to handle your own locking. But

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-15 Thread Tetsuo Handa
Matthew Wilcox wrote: > On Sat, Dec 16, 2017 at 01:31:24PM +0900, Tetsuo Handa wrote: > > Michael S. Tsirkin wrote: > > > On Sat, Dec 16, 2017 at 01:21:52AM +0900, Tetsuo Handa wrote: > > > > My understanding is that virtio-balloon wants to handle sparsely > > > > spreaded > > > > unsigned long

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-15 Thread Matthew Wilcox
On Sat, Dec 16, 2017 at 01:31:24PM +0900, Tetsuo Handa wrote: > Michael S. Tsirkin wrote: > > On Sat, Dec 16, 2017 at 01:21:52AM +0900, Tetsuo Handa wrote: > > > My understanding is that virtio-balloon wants to handle sparsely spreaded > > > unsigned long values (which is PATCH 4/7) and wants to

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-15 Thread Tetsuo Handa
Michael S. Tsirkin wrote: > On Sat, Dec 16, 2017 at 01:21:52AM +0900, Tetsuo Handa wrote: > > My understanding is that virtio-balloon wants to handle sparsely spreaded > > unsigned long values (which is PATCH 4/7) and wants to find all chunks of > > consecutive "1" bits efficiently. Therefore, I

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-15 Thread Matthew Wilcox
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. I looked at the API some more and found some flaws: - how does xbit_alloc communicate back

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-15 Thread Matthew Wilcox
On Sat, Dec 16, 2017 at 01:21:52AM +0900, Tetsuo Handa wrote: > My understanding is that virtio-balloon wants to handle sparsely spreaded > unsigned long values (which is PATCH 4/7) and wants to find all chunks of > consecutive "1" bits efficiently. Therefore, I guess that holding the values > in

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-15 Thread Matthew Wilcox
On Tue, Dec 12, 2017 at 07:55:55PM +0800, Wei Wang wrote: > +int xb_preload_and_set_bit(struct xb *xb, unsigned long bit, gfp_t gfp); I'm struggling to understand when one would use this. The xb_ API requires you to handle your own locking. But specifying GFP flags here implies you can sleep.

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-15 Thread Michael S. Tsirkin
On Sat, Dec 16, 2017 at 01:21:52AM +0900, Tetsuo Handa wrote: > My understanding is that virtio-balloon wants to handle sparsely spreaded > unsigned long values (which is PATCH 4/7) and wants to find all chunks of > consecutive "1" bits efficiently. Therefore, I guess that holding the values > in

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-15 Thread Tetsuo Handa
Matthew Wilcox wrote: > On Fri, Dec 15, 2017 at 01:29:45AM +0900, Tetsuo Handa wrote: > > > > Also, one more thing you need to check. Have you checked how long does > > > > xb_find_next_set_bit(xb, 0, ULONG_MAX) on an empty xbitmap takes? > > > > If it causes soft lockup warning, should we add

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-14 Thread Matthew Wilcox
On Fri, Dec 15, 2017 at 01:29:45AM +0900, Tetsuo Handa wrote: > > > Also, one more thing you need to check. Have you checked how long does > > > xb_find_next_set_bit(xb, 0, ULONG_MAX) on an empty xbitmap takes? > > > If it causes soft lockup warning, should we add cond_resched() ? > > > If yes,

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-14 Thread Tetsuo Handa
Wei Wang wrote: > I used the example of xb_clear_bit_range(), and xb_find_next_bit() is > the same fundamentally. Please let me know if anywhere still looks fuzzy. I don't think it is the same for xb_find_next_bit() with set == 0. + if (radix_tree_exception(bmap)) { +

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-14 Thread Matthew Wilcox
On Wed, Dec 13, 2017 at 08:26:06PM +0800, Wei Wang wrote: > On 12/12/2017 09:20 PM, Tetsuo Handa wrote: > > Can you eliminate exception path and fold all xbitmap patches into one, and > > post only one xbitmap patch without virtio-baloon changes? If exception path > > is valuable, you can add

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-13 Thread Wei Wang
On 12/13/2017 10:16 PM, Tetsuo Handa wrote: Wei Wang wrote: On 12/12/2017 09:20 PM, Tetsuo Handa wrote: Wei Wang wrote: +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) +{ + struct radix_tree_root *root = >xbrt; + struct radix_tree_node *node; +

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-13 Thread Tetsuo Handa
Wei Wang wrote: > On 12/12/2017 09:20 PM, Tetsuo Handa wrote: > > Wei Wang wrote: > >> +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long > >> end) > >> +{ > >> + struct radix_tree_root *root = >xbrt; > >> + struct radix_tree_node *node; > >> + void **slot; > >> +

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-13 Thread Wei Wang
On 12/12/2017 09:20 PM, Tetsuo Handa wrote: Wei Wang wrote: +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) +{ + struct radix_tree_root *root = >xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; +

Re: [Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-12 Thread Tetsuo Handa
Wei Wang wrote: > +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long > end) > +{ > + struct radix_tree_root *root = >xbrt; > + struct radix_tree_node *node; > + void **slot; > + struct ida_bitmap *bitmap; > + unsigned int nbits; > + > + for (; start

[Qemu-devel] [PATCH v19 3/7] xbitmap: add more operations

2017-12-12 Thread Wei Wang
This patch adds support to find next 1 or 0 bit in a xbmitmap range and clear a range of bits. More possible optimizations to add in the future: 1) xb_set_bit_range: set a range of bits. 2) when searching a bit, if the bit is not found in the slot, move on to the next slot directly. 3) add tags