search for: xb_

...> 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 t...

...> 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 t...

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 which bit it allocated? - What if xbit_find_set() is called on a completely empty

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 which bit it allocated? - What if xbit_find_set() is called on a completely empty

...s 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 p...

...tthew 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? > I looked at the API some more and found some flaws: > - how does xbit_alloc com...

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. So ... um ... there's no locking? > +void xb_clear_bit_ran...

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. So ... um ... there's no locking? > +void xb_clear_bit_ran...

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. The xb_ API >>> requires you to handle your own locking. But specifying GFP flags >>> here implies you can sleep. So ... um ... there's no...

...map) { >>>> + bitmap = this_cpu_xchg(ida_bitmap, NULL); >>>> + if (!bitmap) >>>> + return -ENOMEM; >>> I can't understand this. I can understand if it were >>> >>> BUG_ON(!bitmap); >>> >>> because you called xb_preload(). >>> >>> But >>> >>> /* >>> * Regular test 2 >>> * set bit 2000, 2001, 2040 >>> * Next 1 in [0, 2048) --> 2000 >>> * Next 1 in [2000, 2002) --> 2000 >>> * Next 1 in [2002, 2041) --> 2040 &...

...sertl(&head->btree, ~segment, ptr, > GFP_NOWAIT | __GFP_NOWARN)) > goto out3; > out3: > kfree(ptr->bitmap); > out2: > kfree(ptr); > out1: > return false; > } And what is the user supposed to do if this returns false? How do they make headway? The xb_ API is clear -- you call xb_prealloc and that ensures forward progress.

OK, here's a rewrite of xbitmap. Compared to the version you sent: - xb_find_set() is the rewrite I sent out yesterday. - xb_find_clear() is a new implementation. I use the IDR_FREE tag to find clear bits. This led to me finding a bug in radix_tree_for_each_tagged(). - xb_zero() is also a new implementation (replacing xb_clear_bit_range). It should also be mor...

...0+ */ +/* + * eXtensible Bitmaps + * Copyright (c) 2017 Microsoft Corporation + * Author: Matthew Wilcox <mawilcox at microsoft.com> + * + * eXtensible Bitmaps provide an unlimited-size sparse bitmap facility. + * All bits are initially zero. + * + * Locking is to be provided by the user. No xb_ function is safe to + * call concurrently with any other xb_ function. + */ + +#include <linux/idr.h> + +struct xb { + struct radix_tree_root xbrt; +}; + +#define XB_INIT { \ + .xbrt = RADIX_TREE_INIT(IDR_RT_MARKER | GFP_NOWAIT), \ +} +#define DEFINE_XB(name) struct xb name = XB_INIT...

...es in the 1st round. It is not concerned that the memory pages are used after they are given to the hypervisor as a hint of the free pages, because they will be tracked by the hypervisor and transferred in the next round if they are used and written. ChangeLog: v20 (RESEND)->v21: 1) patch 1: - xb_zero: fix the bug related to bitmap_clear; - testing/radix-tree/Makefile: removed the "$CC.." line; - added a test case for xbitmap_check_zero_bits; 2) patch 2: virtio-balloon - changed the usage of the xb_ related APIs v19->v20: 1) patch 1: xbitmap - add __rcu to "void **slot...

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 to help searching. Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox <mawilcox at microsoft.com> Cc: Andrew Morton <akpm...

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 to help searching. Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox <mawilcox at microsoft.com> Cc: Andrew Morton <akpm...

...a/images/hw/pioneer_c.png b/images/hw/pioneer_c.png new file mode 100644 index 0000000000000000000000000000000000000000..87db9d0f3f876f7c805a28a9180f793beb61bb95 GIT binary patch literal 3389 zcmV-D4Z`w?P)<h;3K|Lk000e1NJLTq0077U002G+0{{R3Sxuy<0001EP)t-sZ~y=S z1OW&F0TKcO8Uq3+1_luk5H|`58yg!XB_&@P87(X<Pbw%iH8qDOBSS+&b~rZ5EhcJ8 zNK;c&u01$mVq%t7Q*Ur?t8i_AfPUt9agmXZt(u*trlsMSl*!1(_4f014-&Kh0004W zQchC<K<3zH000b#Nkl<ZXx`OYi<aUj5EWE}Ac-xBm`SJO|9|CH70<lvp0l%OcdOM- zA|_nwbtyO;4u{_TrgR|1;lD2KfHK(TpAduZKP&#Go6-Z2&i*NB{tdyW!n08!e_H<O zo^Q%<aQY96il6HDM...

...free pages in the 1st round. It is not concerned that the memory pages are used after they are given to the hypervisor as a hint of the free pages, because they will be tracked by the hypervisor and transferred in the next round if they are used and written. ChangeLog: v18->v19: 1) patch 3: - xb_clear_bit_range and xb_find_next_bit will deal with range [start, end), where end is changed to be exclusive of the range. - add overflow checks at the end of xb_clear_bit_range and xb_find_next_bit - add overflow related test cases 2) patch 4: - change back to the previous add_one_sg meth...

...free pages in the 1st round. It is not concerned that the memory pages are used after they are given to the hypervisor as a hint of the free pages, because they will be tracked by the hypervisor and transferred in the next round if they are used and written. ChangeLog: v18->v19: 1) patch 3: - xb_clear_bit_range and xb_find_next_bit will deal with range [start, end), where end is changed to be exclusive of the range. - add overflow checks at the end of xb_clear_bit_range and xb_find_next_bit - add overflow related test cases 2) patch 4: - change back to the previous add_one_sg meth...

...e exceptional path. 2) patch 3: xbitmap - DeveloperNotes: add an item to comment that the current bit range related APIs operating on extremely large ranges (e.g. [0, ULONG_MAX)) will take too long time. This can be optimized in the future. - remove the exceptional path; - remove xb_preload_and_set(); - reimplement xb_clear_bit_range to make its usage close to bitmap_clear; - rename xb_find_next_set_bit to xb_find_set, and re-implement it in a style close to find_next_bit; - rename xb_find_next_zero_bit to xb_find_clear, and re-implement it in a stytle close to find...