| Message ID | 1430152117-100558-25-git-send-email-pbonzini@redhat.com |
|---|---|
| State | New |
| Headers | show |
On Mon, 04/27 18:28, Paolo Bonzini wrote: > From: Stefan Hajnoczi <stefanha@redhat.com> > > The new bitmap_test_and_clear_atomic() function clears a range and > returns whether or not the bits were set. > > Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> > Message-Id: <1417519399-3166-3-git-send-email-stefanha@redhat.com> > [Test before xchg; then a full barrier is needed at the end just like > in the previous patch. The barrier can be avoided if we did at least > one xchg. - Paolo] > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> > --- > include/qemu/bitmap.h | 2 ++ > util/bitmap.c | 44 ++++++++++++++++++++++++++++++++++++++++++++ > 2 files changed, 46 insertions(+) > > diff --git a/include/qemu/bitmap.h b/include/qemu/bitmap.h > index 3e0a4f3..86dd9cd 100644 > --- a/include/qemu/bitmap.h > +++ b/include/qemu/bitmap.h > @@ -41,6 +41,7 @@ > * bitmap_set(dst, pos, nbits) Set specified bit area > * bitmap_set_atomic(dst, pos, nbits) Set specified bit area with atomic ops > * bitmap_clear(dst, pos, nbits) Clear specified bit area > + * bitmap_test_and_clear_atomic(dst, pos, nbits) Test and clear area > * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area > */ > > @@ -229,6 +230,7 @@ static inline int bitmap_intersects(const unsigned long *src1, > void bitmap_set(unsigned long *map, long i, long len); > void bitmap_set_atomic(unsigned long *map, long i, long len); > void bitmap_clear(unsigned long *map, long start, long nr); > +bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr); > unsigned long bitmap_find_next_zero_area(unsigned long *map, > unsigned long size, > unsigned long start, > diff --git a/util/bitmap.c b/util/bitmap.c > index 6838d49..d3e088d 100644 > --- a/util/bitmap.c > +++ b/util/bitmap.c > @@ -234,6 +234,50 @@ void bitmap_clear(unsigned long *map, long start, long nr) > } > } > > +bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr) > +{ > + unsigned long *p = map + BIT_WORD(start); > + const long size = start + nr; > + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); > + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); > + unsigned long dirty = 0; > + unsigned long old_bits; > + > + /* First word */ > + if (nr - bits_to_clear > 0) { > + old_bits = atomic_fetch_and(p, ~mask_to_clear); > + dirty |= old_bits & mask_to_clear; > + nr -= bits_to_clear; > + bits_to_clear = BITS_PER_LONG; > + mask_to_clear = ~0UL; > + p++; > + } > + It's broken if the clear range is the last part of first word: map = 0xFFFFFFFFFFFFFFFF, ... bitmap_test_and_clear_atomic(map, 60, 4): Expected result: 0xFFFFFFFFFFFFFFFF, ... Actual result: 0x0 Fam
On Tue, 05/26 20:27, Fam Zheng wrote: > On Mon, 04/27 18:28, Paolo Bonzini wrote: > > From: Stefan Hajnoczi <stefanha@redhat.com> > > > > The new bitmap_test_and_clear_atomic() function clears a range and > > returns whether or not the bits were set. > > > > Signed-off-by: Stefan Hajnoczi <stefanha@redhat.com> > > Message-Id: <1417519399-3166-3-git-send-email-stefanha@redhat.com> > > [Test before xchg; then a full barrier is needed at the end just like > > in the previous patch. The barrier can be avoided if we did at least > > one xchg. - Paolo] > > > > Signed-off-by: Paolo Bonzini <pbonzini@redhat.com> > > --- > > include/qemu/bitmap.h | 2 ++ > > util/bitmap.c | 44 ++++++++++++++++++++++++++++++++++++++++++++ > > 2 files changed, 46 insertions(+) > > > > diff --git a/include/qemu/bitmap.h b/include/qemu/bitmap.h > > index 3e0a4f3..86dd9cd 100644 > > --- a/include/qemu/bitmap.h > > +++ b/include/qemu/bitmap.h > > @@ -41,6 +41,7 @@ > > * bitmap_set(dst, pos, nbits) Set specified bit area > > * bitmap_set_atomic(dst, pos, nbits) Set specified bit area with atomic ops > > * bitmap_clear(dst, pos, nbits) Clear specified bit area > > + * bitmap_test_and_clear_atomic(dst, pos, nbits) Test and clear area > > * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area > > */ > > > > @@ -229,6 +230,7 @@ static inline int bitmap_intersects(const unsigned long *src1, > > void bitmap_set(unsigned long *map, long i, long len); > > void bitmap_set_atomic(unsigned long *map, long i, long len); > > void bitmap_clear(unsigned long *map, long start, long nr); > > +bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr); > > unsigned long bitmap_find_next_zero_area(unsigned long *map, > > unsigned long size, > > unsigned long start, > > diff --git a/util/bitmap.c b/util/bitmap.c > > index 6838d49..d3e088d 100644 > > --- a/util/bitmap.c > > +++ b/util/bitmap.c > > @@ -234,6 +234,50 @@ void bitmap_clear(unsigned long *map, long start, long nr) > > } > > } > > > > +bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr) > > +{ > > + unsigned long *p = map + BIT_WORD(start); > > + const long size = start + nr; > > + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); > > + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); > > + unsigned long dirty = 0; > > + unsigned long old_bits; > > + > > + /* First word */ > > + if (nr - bits_to_clear > 0) { > > + old_bits = atomic_fetch_and(p, ~mask_to_clear); > > + dirty |= old_bits & mask_to_clear; > > + nr -= bits_to_clear; > > + bits_to_clear = BITS_PER_LONG; > > + mask_to_clear = ~0UL; > > + p++; > > + } > > + > > It's broken if the clear range is the last part of first word: > > map = 0xFFFFFFFFFFFFFFFF, ... > > bitmap_test_and_clear_atomic(map, 60, 4): > > Expected result: > > 0xFFFFFFFFFFFFFFFF, ... Sorry, I meant 0xFFFFFFFFFFFFFFF (the highest 4 bits being cleared). > > Actual result: > > 0x0 > > Fam >
On 26/05/2015 14:27, Fam Zheng wrote: > It's broken if the clear range is the last part of first word: > > map = 0xFFFFFFFFFFFFFFFF, ... > > bitmap_test_and_clear_atomic(map, 60, 4): > > Expected result: > > 0xFFFFFFFFFFFFFFFF, ... > > Actual result: > > 0x0 You're right, this: /* Full words */ while (nr - bits_to_clear >= 0) { must be surrounded by an "if (mask_to_clear == ~0UL)" or "if (bits_to_clear == BITS_PER_LONG)." Patch 23 has the same problem. Paolo
diff --git a/include/qemu/bitmap.h b/include/qemu/bitmap.h index 3e0a4f3..86dd9cd 100644 --- a/include/qemu/bitmap.h +++ b/include/qemu/bitmap.h @@ -41,6 +41,7 @@ * bitmap_set(dst, pos, nbits) Set specified bit area * bitmap_set_atomic(dst, pos, nbits) Set specified bit area with atomic ops * bitmap_clear(dst, pos, nbits) Clear specified bit area + * bitmap_test_and_clear_atomic(dst, pos, nbits) Test and clear area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area */ @@ -229,6 +230,7 @@ static inline int bitmap_intersects(const unsigned long *src1, void bitmap_set(unsigned long *map, long i, long len); void bitmap_set_atomic(unsigned long *map, long i, long len); void bitmap_clear(unsigned long *map, long start, long nr); +bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr); unsigned long bitmap_find_next_zero_area(unsigned long *map, unsigned long size, unsigned long start, diff --git a/util/bitmap.c b/util/bitmap.c index 6838d49..d3e088d 100644 --- a/util/bitmap.c +++ b/util/bitmap.c @@ -234,6 +234,50 @@ void bitmap_clear(unsigned long *map, long start, long nr) } } +bool bitmap_test_and_clear_atomic(unsigned long *map, long start, long nr) +{ + unsigned long *p = map + BIT_WORD(start); + const long size = start + nr; + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); + unsigned long dirty = 0; + unsigned long old_bits; + + /* First word */ + if (nr - bits_to_clear > 0) { + old_bits = atomic_fetch_and(p, ~mask_to_clear); + dirty |= old_bits & mask_to_clear; + nr -= bits_to_clear; + bits_to_clear = BITS_PER_LONG; + mask_to_clear = ~0UL; + p++; + } + + /* Full words */ + while (nr - bits_to_clear >= 0) { + if (*p) { + old_bits = atomic_xchg(p, 0); + dirty |= old_bits; + } + nr -= bits_to_clear; + mask_to_clear = ~0UL; + p++; + } + + /* Last word */ + if (nr) { + mask_to_clear &= BITMAP_LAST_WORD_MASK(size); + old_bits = atomic_fetch_and(p, ~mask_to_clear); + dirty |= old_bits & mask_to_clear; + } else { + if (!dirty) { + smp_mb(); + } + } + + return dirty != 0; +} + #define ALIGN_MASK(x,mask) (((x)+(mask))&~(mask)) /**