From: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
To: wei.w.wang@intel.com
Cc: virtio-dev@lists.oasis-open.org, linux-kernel@vger.kernel.org,
qemu-devel@nongnu.org, virtualization@lists.linux-foundation.org,
kvm@vger.kernel.org, linux-mm@kvack.org, mst@redhat.com,
mhocko@kernel.org, akpm@linux-foundation.org,
mawilcox@microsoft.com, david@redhat.com,
cornelia.huck@de.ibm.com, mgorman@techsingularity.net,
aarcange@redhat.com, amit.shah@redhat.com, pbonzini@redhat.com,
willy@infradead.org, liliang.opensource@gmail.com,
yang.zhang.wz@gmail.com, quan.xu@aliyun.com, nilal@redhat.com,
riel@redhat.com
Subject: Re: [PATCH v19 3/7] xbitmap: add more operations
Date: Wed, 13 Dec 2017 23:16:56 +0900 [thread overview]
Message-ID: <201712132316.EJJ57332.MFOSJHOFFVLtQO@I-love.SAKURA.ne.jp> (raw)
In-Reply-To: <5A311C5E.7000304@intel.com>
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 = &xb->xbrt;
> >> + struct radix_tree_node *node;
> >> + void **slot;
> >> + struct ida_bitmap *bitmap;
> >> + unsigned int nbits;
> >> +
> >> + for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) {
> >> + unsigned long index = start / IDA_BITMAP_BITS;
> >> + unsigned long bit = start % IDA_BITMAP_BITS;
> >> +
> >> + bitmap = __radix_tree_lookup(root, index, &node, &slot);
> >> + if (radix_tree_exception(bitmap)) {
> >> + unsigned long ebit = bit + 2;
> >> + unsigned long tmp = (unsigned long)bitmap;
> >> +
> >> + nbits = min(end - start + 1, BITS_PER_LONG - ebit);
> >> +
> >> + if (ebit >= BITS_PER_LONG)
> > What happens if we hit this "continue;" when "index == ULONG_MAX / IDA_BITMAP_BITS" ?
>
> Thanks. I also improved the test case for this. I plan to change the
> implementation a little bit to avoid such overflow (has passed the test
> case that I have, just post out for another set of eyes):
>
> {
> ...
> unsigned long idx = start / IDA_BITMAP_BITS;
> unsigned long bit = start % IDA_BITMAP_BITS;
> unsigned long idx_end = end / IDA_BITMAP_BITS;
> unsigned long ret;
>
> for (idx = start / IDA_BITMAP_BITS; idx <= idx_end; idx++) {
> unsigned long ida_start = idx * IDA_BITMAP_BITS;
>
> bitmap = __radix_tree_lookup(root, idx, &node, &slot);
> if (radix_tree_exception(bitmap)) {
> unsigned long tmp = (unsigned long)bitmap;
> unsigned long ebit = bit + 2;
>
> if (ebit >= BITS_PER_LONG)
> continue;
Will you please please do eliminate exception path?
I can't interpret what "ebit >= BITS_PER_LONG" means.
The reason you "continue;" is that all bits beyond are "0", isn't it?
Then, it would make sense to "continue;" when finding next "1" because
all bits beyond are "0". But how does it make sense to "continue;" when
finding next "0" despite all bits beyond are "0"?
> if (set)
> ret = find_next_bit(&tmp,
> BITS_PER_LONG, ebit);
> else
> ret = find_next_zero_bit(&tmp,
> BITS_PER_LONG,
> ebit);
> if (ret < BITS_PER_LONG)
> return ret - 2 + ida_start;
> } else if (bitmap) {
> if (set)
> ret = find_next_bit(bitmap->bitmap,
> IDA_BITMAP_BITS, bit);
> else
> ret = find_next_zero_bit(bitmap->bitmap,
> IDA_BITMAP_BITS, bit);
"bit" may not be 0 for the first round and "bit" is always 0 afterwords.
But where is the guaranteed that "end" is a multiple of IDA_BITMAP_BITS ?
Please explain why it is correct to use IDA_BITMAP_BITS unconditionally
for the last round.
> if (ret < IDA_BITMAP_BITS)
> return ret + ida_start;
> } else if (!bitmap && !set) {
At this point bitmap == NULL is guaranteed. Thus, "!bitmap && " is pointless.
> return bit + IDA_BITMAP_BITS * idx;
> }
> bit = 0;
> }
>
> return end;
> }
>
>
> >
> >> +/**
> >> + * xb_find_next_set_bit - find the next set bit in a range
> >> + * @xb: the xbitmap to search
> >> + * @start: the start of the range, inclusive
> >> + * @end: the end of the range, exclusive
> >> + *
> >> + * Returns: the index of the found bit, or @end + 1 if no such bit is found.
> >> + */
> >> +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start,
> >> + unsigned long end)
> >> +{
> >> + return xb_find_next_bit(xb, start, end, 1);
> >> +}
> > Won't "exclusive" loose ability to handle ULONG_MAX ? Since this is a
> > library module, missing ability to handle ULONG_MAX sounds like an omission.
> > Shouldn't we pass (or return) whether "found or not" flag (e.g. strtoul() in
> > C library function)?
> >
> > bool xb_find_next_set_bit(struct xb *xb, unsigned long start, unsigned long end, unsigned long *result);
> > unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, unsigned long end, bool *found);
>
> Yes, ULONG_MAX needs to be tested by xb_test_bit(). Compared to checking
> the return value, would it be the same to let the caller check for the
> ULONG_MAX boundary?
>
Why the caller needs to care about whether it is ULONG_MAX or not?
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, you have to document that this API might sleep. If no, you
have to document that the caller of this API is responsible for
not to pass such a large value range.
next prev parent reply other threads:[~2017-12-13 14:17 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-12-12 11:55 [PATCH v19 0/7] Virtio-balloon Enhancement Wei Wang
2017-12-12 11:55 ` [PATCH v19 1/7] xbitmap: Introduce xbitmap Wei Wang
2017-12-12 12:53 ` Philippe Ombredanne
2017-12-15 11:05 ` kbuild test robot
2017-12-15 13:24 ` Matthew Wilcox
2017-12-16 10:10 ` Wei Wang
2017-12-12 11:55 ` [PATCH v19 2/7] xbitmap: potential improvement Wei Wang
2017-12-15 3:07 ` kbuild test robot
2017-12-12 11:55 ` [PATCH v19 3/7] xbitmap: add more operations Wei Wang
2017-12-12 13:20 ` Tetsuo Handa
2017-12-13 12:26 ` Wei Wang
2017-12-13 14:16 ` Tetsuo Handa [this message]
2017-12-14 3:47 ` Wei Wang
2017-12-14 11:47 ` [virtio-dev] " Wei Wang
2017-12-14 16:29 ` Tetsuo Handa
2017-12-14 18:12 ` Matthew Wilcox
2017-12-15 16:21 ` Tetsuo Handa
2017-12-15 18:26 ` Michael S. Tsirkin
2017-12-16 4:31 ` Tetsuo Handa
2017-12-16 5:05 ` Matthew Wilcox
2017-12-16 5:57 ` Tetsuo Handa
2017-12-15 18:49 ` Matthew Wilcox
2017-12-15 19:22 ` Matthew Wilcox
2017-12-17 13:47 ` Wang, Wei W
2017-12-17 22:18 ` Matthew Wilcox
2017-12-18 2:33 ` Wei Wang
2017-12-18 2:59 ` Matthew Wilcox
2017-12-16 10:14 ` Wei Wang
2017-12-14 12:37 ` Matthew Wilcox
2017-12-15 18:42 ` Matthew Wilcox
2017-12-16 10:12 ` Wei Wang
2017-12-16 11:28 ` Tetsuo Handa
2017-12-17 5:24 ` Wei Wang
2017-12-17 10:21 ` Tetsuo Handa
2017-12-17 11:50 ` Wang, Wei W
2017-12-17 15:16 ` Tetsuo Handa
2017-12-18 8:05 ` Wei Wang
2017-12-12 11:55 ` [PATCH v19 4/7] virtio-balloon: VIRTIO_BALLOON_F_SG Wei Wang
2017-12-12 11:55 ` [PATCH v19 5/7] mm: support reporting free page blocks Wei Wang
2017-12-12 11:55 ` [PATCH v19 6/7] virtio-balloon: VIRTIO_BALLOON_F_FREE_PAGE_VQ Wei Wang
2017-12-12 11:55 ` [PATCH v19 7/7] virtio-balloon: don't report free pages when page poisoning is enabled Wei Wang
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=201712132316.EJJ57332.MFOSJHOFFVLtQO@I-love.SAKURA.ne.jp \
--to=penguin-kernel@i-love.sakura.ne.jp \
--cc=aarcange@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=amit.shah@redhat.com \
--cc=cornelia.huck@de.ibm.com \
--cc=david@redhat.com \
--cc=kvm@vger.kernel.org \
--cc=liliang.opensource@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=mawilcox@microsoft.com \
--cc=mgorman@techsingularity.net \
--cc=mhocko@kernel.org \
--cc=mst@redhat.com \
--cc=nilal@redhat.com \
--cc=pbonzini@redhat.com \
--cc=qemu-devel@nongnu.org \
--cc=quan.xu@aliyun.com \
--cc=riel@redhat.com \
--cc=virtio-dev@lists.oasis-open.org \
--cc=virtualization@lists.linux-foundation.org \
--cc=wei.w.wang@intel.com \
--cc=willy@infradead.org \
--cc=yang.zhang.wz@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).