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;
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);
if (ret < IDA_BITMAP_BITS)
return ret + ida_start;
} else if (!bitmap && !set) {
return bit + IDA_BITMAP_BITS * idx;
}
bit = 0;
}
return end;
}
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 exception path after minimum version is merged.
This series is too difficult for me to close corner cases.
That exception path is claimed to save memory, and I don't have a strong
reason to remove that part.
Matthew, could we get your feedback on this?
+/**
+ * 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?
Best,
Wei
