| Message ID | 1484121033-15354-4-git-send-email-yi.he@linaro.org |
|---|---|
| State | Accepted |
| Commit | ff30fcb8467467e4dd08dc1f72b852f5e0c903f1 |
| Headers | show |
On Wed, Jan 11, 2017 at 1:50 AM, Yi He <yi.he@linaro.org> wrote: > Add C++ template alike bitmap<size> to allow > instantiate bitmap data structure of any size, > and provide iterators to help walking through > the bitmap objects. > > Signed-off-by: Yi He <yi.he@linaro.org> > --- > platform/linux-generic/Makefile.am | 2 + > .../linux-generic/include/odp_bitmap_internal.h | 317 +++++++++++++++++++++ > platform/linux-generic/odp_bitmap.c | 315 ++++++++++++++++++++ > 3 files changed, 634 insertions(+) > create mode 100644 platform/linux-generic/include/odp_bitmap_internal.h > create mode 100644 platform/linux-generic/odp_bitmap.c > > diff --git a/platform/linux-generic/Makefile.am b/platform/linux-generic/Makefile.am > index 999a7f5..5b38c7b 100644 > --- a/platform/linux-generic/Makefile.am > +++ b/platform/linux-generic/Makefile.am > @@ -130,6 +130,7 @@ noinst_HEADERS = \ > ${srcdir}/include/odp_align_internal.h \ > ${srcdir}/include/odp_atomic_internal.h \ > ${srcdir}/include/odp_buffer_inlines.h \ > + ${srcdir}/include/odp_bitmap_internal.h \ > ${srcdir}/include/odp_buffer_internal.h \ > ${srcdir}/include/odp_classification_datamodel.h \ > ${srcdir}/include/odp_classification_inlines.h \ > @@ -173,6 +174,7 @@ __LIB__libodp_linux_la_SOURCES = \ > _ishmphy.c \ > odp_atomic.c \ > odp_barrier.c \ > + odp_bitmap.c \ > odp_buffer.c \ > odp_byteorder.c \ > odp_classification.c \ > diff --git a/platform/linux-generic/include/odp_bitmap_internal.h b/platform/linux-generic/include/odp_bitmap_internal.h > new file mode 100644 > index 0000000..1be4d02 > --- /dev/null > +++ b/platform/linux-generic/include/odp_bitmap_internal.h > @@ -0,0 +1,317 @@ > +/* Copyright (c) 2016, Linaro Limited > + * All rights reserved. > + * > + * SPDX-License-Identifier: BSD-3-Clause > + */ > + > +/** > + * @file > + * > + * ODP generic bitmap types and operations. > + */ > + > +#ifndef ODP_BITMAP_INTERNAL_H_ > +#define ODP_BITMAP_INTERNAL_H_ > + > +#ifdef __cplusplus > +extern "C" { > +#endif > + > +#include <stdint.h> > +#include <stdbool.h> > +#include <string.h> > +#include <odp/api/hints.h> > + > +/* Generate unique identifier for instantiated class */ > +#define TOKENIZE(template, line) \ > + template ## _ ## line ## _ ## __COUNTER__ > + > +/* Array size in general */ > +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) Checkpatch flags this with the following: --- WARNING: Prefer ARRAY_SIZE(array) #76: FILE: platform/linux-generic/include/odp_bitmap_internal.h:30: +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) total: 0 errors, 1 warnings, 0 checks, 646 lines checked NOTE: Ignored message types: BIT_MACRO COMPARISON_TO_NULL DEPRECATED_VARIABLE NEW_TYPEDEFS SPLIT_STRING SSCANF_TO_KSTRTO 0003-linux-gen-add-generic-bitmaps-and-iterators.patch has style problems, please review. --- I suspect that ARRAY_SIZE is a Linux internal macro, in which case our internal checkpatch rules may need updating. > + > +#define BITS_PER_BYTE (8) > +#define BITS_PER_LONG __WORDSIZE > +#define BYTES_PER_LONG (BITS_PER_LONG / BITS_PER_BYTE) > + > +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) > +#define BITS_TO_LONGS(nr) BIT_WORD(nr + BITS_PER_LONG - 1) > + > +#define BITMAP_FIRST_WORD_MASK(start) \ > + (~0UL << ((start) & (BITS_PER_LONG - 1))) > +#define BITMAP_LAST_WORD_MASK(nbits) \ > + (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) > + > +/* WAPL bitmap base class */ > +typedef struct { > + unsigned int nwords; > + unsigned int *pl; > + unsigned long *ul; > +} wapl_bitmap_t; > + > +/* > + * Word-Aligned Position List (WAPL) bitmap, which actually > + * is not a compression, but with an extra list of non-empty > + * word positions. > + * > + * WAPL accelerates bitwise operations and iterations by > + * applying only to non-empty positions instead of walking > + * through the whole bitmap. > + * > + * WAPL uses [1 ~ N] instead of [0 ~ N - 1] as position > + * values and an extra 0 as end indicator for position list. > + * This is the reason to allocate one extra room below. > + */ > +#define instantiate_wapl_bitmap(line, nbits) \ > + struct TOKENIZE(wapl_bitmap, line) { \ > + unsigned int pl[BITS_TO_LONGS(nbits) + 1]; \ > + unsigned long ul[BITS_TO_LONGS(nbits) + 1]; \ > + } > + > +#define WAPL_BITMAP(nbits) instantiate_wapl_bitmap(__LINE__, nbits) > + > +/* > + * Upcast any derived WAPL bitmap class to its base class > + */ > +#define __wapl_upcast(base, derived) \ > + do { \ > + __typeof__(derived) p = derived; \ > + base.pl = p->pl; \ > + base.ul = p->ul; \ > + base.nwords = ARRAY_SIZE(p->ul) - 1; \ > + } while (0) > + > +/* > + * WAPL base class bitmap operations > + */ > +void __wapl_bitmap_and(wapl_bitmap_t *dst, > + wapl_bitmap_t *src, wapl_bitmap_t *and); > + > +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or); > + > +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit); > + > +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit); > + > +/* > + * Generic WAPL bitmap operations > + */ > +#define wapl_bitmap_zero(map) \ > + ({ \ > + __typeof__(map) p = map; \ > + memset((void *)p, 0, sizeof(__typeof__(*p))); \ > + }) > + > +#define wapl_bitmap_copy(dst, src) \ > + ({ \ > + __typeof__(dst) d = dst; \ > + __typeof__(src) s = src; \ > + if (d != s) \ > + memcpy((void *)d, (void *)s, \ > + sizeof(__typeof__(*d))); \ > + }) > + > +#define wapl_bitmap_and(dst, src, and) \ > + ({ \ > + wapl_bitmap_t d, s, a; \ > + __wapl_upcast(d, dst); \ > + __wapl_upcast(s, src); \ > + __wapl_upcast(a, and); \ > + __wapl_bitmap_and(&d, &s, &a); \ > + }) > + > +#define wapl_bitmap_or(dst, src, or) \ > + ({ \ > + wapl_bitmap_t d, o; \ > + wapl_bitmap_copy(dst, src); \ > + __wapl_upcast(d, dst); \ > + __wapl_upcast(o, or); \ > + __wapl_bitmap_or(&d, &o); \ > + }) > + > +#define wapl_bitmap_set(map, bit) \ > + ({ \ > + wapl_bitmap_t b; \ > + __wapl_upcast(b, map); \ > + __wapl_bitmap_set(&b, bit); \ > + }) > + > +#define wapl_bitmap_clear(map, bit) \ > + ({ \ > + wapl_bitmap_t b; \ > + __wapl_upcast(b, map); \ > + __wapl_bitmap_clear(&b, bit); \ > + }) > + > +/* > + * Round robin iterator runs upon a WAPL bitmap: > + * > + * wapl_bitmap_iterator(iterator, WAPL bitmap); > + * for (iterator->start(); iterator->has_next(); ) { > + * unsigned int bit_index = iterator->next(); > + * ...operations on this bit index... > + * } > + */ > +typedef struct wapl_bitmap_iterator { > + int _start, _next, _nbits; > + wapl_bitmap_t _base; > + > + void (*start)(struct wapl_bitmap_iterator *this); > + bool (*has_next)(struct wapl_bitmap_iterator *this); > + unsigned int (*next)(struct wapl_bitmap_iterator *this); > +} wapl_bitmap_iterator_t; > + > +/* > + * WAPL bitmap iterator constructor > + */ > +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this); > + > +/* > + * Generic constructor accepts any derived WAPL bitmap class > + */ > +#define wapl_bitmap_iterator(iterator, map) \ > + ({ \ > + __typeof__(iterator) __it = iterator; \ > + __wapl_upcast(__it->_base, map); \ > + __wapl_bitmap_iterator(__it); \ > + }) > + > +/* Sparse bitmap base class */ > +typedef struct { > + unsigned int nbits; > + unsigned int *last, *pl, *il; > +} sparse_bitmap_t; > + > +/* > + * Sparse bitmap, lists all bit indexes directly as an array. > + * Expected to be significantly straightforward iteration. > + */ > +#define instantiate_sparse_bitmap(line, nbits) \ > + struct TOKENIZE(sparse_bitmap, line) { \ > + unsigned int last; \ > + unsigned int pl[nbits]; \ > + unsigned int il[nbits]; \ > + } > + > +#define SPARSE_BITMAP(nbits) instantiate_sparse_bitmap(__LINE__, nbits) > + > +/* > + * Upcast any derived sparse bitmap class to its base class > + */ > +#define __sparse_upcast(base, derived) \ > + do { \ > + __typeof__(derived) p = derived; \ > + base.pl = p->pl; \ > + base.il = p->il; \ > + base.last = &p->last; \ > + base.nbits = ARRAY_SIZE(p->il); \ > + } while (0) > + > +/* > + * Sparse base class bitmap operations > + */ > +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit); > + > +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit); > + > +/* > + * Generic sparse bitmap operations > + */ > +#define sparse_bitmap_zero(map) \ > + ({ \ > + __typeof__(map) p = map; \ > + memset((void *)p, 0, sizeof(__typeof__(*p))); \ > + }) > + > +#define sparse_bitmap_set(map, bit) \ > + ({ \ > + sparse_bitmap_t b; \ > + __sparse_upcast(b, map); \ > + __sparse_bitmap_set(&b, bit); \ > + }) > + > +#define sparse_bitmap_clear(map, bit) \ > + ({ \ > + sparse_bitmap_t b; \ > + __sparse_upcast(b, map); \ > + __sparse_bitmap_clear(&b, bit); \ > + }) > + > +/* > + * Round robin iterator runs upon a sparse bitmap: > + * > + * sparse_bitmap_iterator(iterator, SPARSE bitmap); > + * for (iterator->start(); iterator->has_next(); ) { > + * unsigned int bit_index = iterator->next(); > + * ...operations on this bit index... > + * } > + */ > +typedef struct sparse_bitmap_iterator { > + int _start, _next, _nbits; > + sparse_bitmap_t _base; > + > + void (*start)(struct sparse_bitmap_iterator *this); > + bool (*has_next)(struct sparse_bitmap_iterator *this); > + unsigned int (*next)(struct sparse_bitmap_iterator *this); > +} sparse_bitmap_iterator_t; > + > +/* > + * Sparse bitmap iterator constructor > + */ > +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this); > + > +/* > + * Generic constructor accepts any derived sparse bitmap class. > + */ > +#define sparse_bitmap_iterator(iterator, map) \ > + ({ \ > + __typeof__(iterator) __it = iterator; \ > + __sparse_upcast(__it->_base, map); \ > + __sparse_bitmap_iterator(__it); \ > + }) > + > +/* > + * Raw bitmap atomic set and clear. > + */ > +void raw_bitmap_set(unsigned long *map, unsigned int bit); > + > +void raw_bitmap_clear(unsigned long *map, unsigned int bit); > + > +/* > + * It will enter infinite loop incase that all bits are zero, > + * so please make sure the bitmap at least has one set. > + */ > +static inline int __bitmap_wraparound_next( > + unsigned long *addr, unsigned int nbits, int start) > +{ > + unsigned long tmp; > + > + if (start >= (int)nbits) > + start = 0; > + > + tmp = addr[BIT_WORD(start)]; > + > + /* Handle 1st word. */ > + tmp &= BITMAP_FIRST_WORD_MASK(start); > + start = start & ~(BITS_PER_LONG - 1); > + > + while (!tmp) { > + start += BITS_PER_LONG; > + if (start >= (int)nbits) > + start = 0; > + > + tmp = addr[BIT_WORD(start)]; > + } > + > + start += __builtin_ffsl(tmp) - 1; > + return start; > +} > + > +/** > + * @} > + */ > + > +#ifdef __cplusplus > +} > +#endif > + > +#endif > diff --git a/platform/linux-generic/odp_bitmap.c b/platform/linux-generic/odp_bitmap.c > new file mode 100644 > index 0000000..a29b9ef > --- /dev/null > +++ b/platform/linux-generic/odp_bitmap.c > @@ -0,0 +1,315 @@ > +/* Copyright (c) 2016, Linaro Limited > + * All rights reserved. > + * > + * SPDX-License-Identifier: BSD-3-Clause > + */ > + > +#include <string.h> > +#include <unistd.h> > +#include <odp/api/std_types.h> > +#include <odp/api/byteorder.h> > +#include <odp_bitmap_internal.h> > + > +/* > + * WAPL base class bitmap operations > + */ > +static inline void __wapl_add_pos( > + wapl_bitmap_t *map, unsigned int p) > +{ > + unsigned int s, k = 0; > + unsigned int *pl = map->pl; > + > + while (pl[k] && p > pl[k]) > + k++; > + > + if (p == pl[k]) > + return; > + > + /* sorted insertion */ > + for (; pl[k] && p < pl[k]; k++) { > + s = pl[k]; > + pl[k] = p; > + p = s; > + } > + > + if (k < map->nwords) > + pl[k++] = p; > + > + pl[k] = 0; > +} > + > +static inline void __wapl_remove_pos( > + wapl_bitmap_t *map, unsigned int p) > +{ > + unsigned int k = 0; > + unsigned int *pl = map->pl; > + > + while (pl[k] && p != pl[k]) > + k++; > + > + for (; pl[k]; k++) > + pl[k] = pl[k + 1]; > +} > + > +void __wapl_bitmap_and(wapl_bitmap_t *dst, > + wapl_bitmap_t *src, wapl_bitmap_t *and) > +{ > + unsigned int k = 0, p; > + unsigned int *pl = src->pl; > + > + while ((p = *pl++) != 0) { > + dst->ul[p] = src->ul[p] & and->ul[p]; > + if (dst->ul[p]) > + dst->pl[k++] = p; > + } > + > + dst->pl[k] = 0; > +} > + > +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or) > +{ > + unsigned int p; > + unsigned int *pl = or->pl; > + > + while ((p = *pl++) != 0) { > + if (dst->ul[p] == 0) > + __wapl_add_pos(dst, p); > + > + dst->ul[p] |= or->ul[p]; > + } > +} > + > +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit) > +{ > + unsigned int p = BIT_WORD(bit) + 1; > + unsigned long set = 1UL << (bit & (BITS_PER_LONG - 1)); > + > + if (p > map->nwords) > + return; > + > + if (map->ul[p] == 0) > + __wapl_add_pos(map, p); > + > + map->ul[p] |= set; > +} > + > +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit) > +{ > + unsigned int p = BIT_WORD(bit) + 1; > + unsigned long clear = 1UL << (bit & (BITS_PER_LONG - 1)); > + > + if (p > map->nwords) > + return; > + > + map->ul[p] &= ~clear; > + > + if (map->ul[p] == 0) > + __wapl_remove_pos(map, p); > +} > + > +/* > + * WAPL bitmap iterator implementation > + */ > +static void __wapl_iterator_start(wapl_bitmap_iterator_t *this) > +{ > + this->_nbits = this->_base.nwords * BITS_PER_LONG; > + > + /* Advance to next queue index to start this > + * new round iteration. > + */ > + if (this->_base.pl[0] == 0) > + this->_start = -1; > + else > + this->_start = __bitmap_wraparound_next( > + &this->_base.ul[1], this->_nbits, this->_start + 1); > + > + this->_next = this->_start; > +} > + > +static bool __wapl_iterator_has_next(wapl_bitmap_iterator_t *this) > +{ > + return (this->_next != -1); > +} > + > +static unsigned int __wapl_iterator_next(wapl_bitmap_iterator_t *this) > +{ > + int next = this->_next; > + > + this->_next = __bitmap_wraparound_next( > + &this->_base.ul[1], this->_nbits, this->_next + 1); > + > + if (this->_next == this->_start) > + this->_next = -1; > + > + return next; > +} > + > +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this) > +{ > + this->start = __wapl_iterator_start; > + this->has_next = __wapl_iterator_has_next; > + this->next = __wapl_iterator_next; > + > + this->_start = -1; > + this->_next = this->_start; > +} > + > +/* > + * Sparse base class bitmap operations > + */ > +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit) > +{ > + unsigned int last = *map->last; > + > + /* Index exceeds */ > + if (bit >= map->nbits) > + return; > + > + /* Full bitmap */ > + if (last >= map->nbits) > + return; > + > + /* Bit was not set previously, > + * also record where we set the bit > + */ > + if (!map->pl[bit]) { > + map->il[last++] = bit; > + map->pl[bit] = last; > + > + *map->last = last; > + } > +} > + > +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit) > +{ > + unsigned int p, i; > + unsigned int last = *map->last; > + > + /* Index exceeds */ > + if (bit >= map->nbits) > + return; > + > + /* Empty bitmap */ > + if (last == 0) > + return; > + > + /* Bit was set previously */ > + if (map->pl[bit]) { > + p = map->pl[bit] - 1; > + map->pl[bit] = 0; > + > + last--; > + *map->last = last; > + > + /* Fill the hole with the latest index */ > + if (p < last) { > + i = map->il[last]; > + map->pl[i] = p + 1; > + map->il[p] = i; > + } > + } > +} > + > +/* > + * Sparse bitmap iterator implementation > + */ > +static void __sparse_iterator_start(sparse_bitmap_iterator_t *this) > +{ > + this->_nbits = (int)*this->_base.last; > + > + /* Advance to next queue index to start this > + * new round iteration. > + */ > + if (this->_nbits == 0) > + this->_start = -1; > + else > + this->_start = (this->_start + 1) & (this->_nbits - 1); > + > + this->_next = this->_start; > +} > + > +static bool __sparse_iterator_has_next(sparse_bitmap_iterator_t *this) > +{ > + return (this->_next != -1); > +} > + > +static unsigned int __sparse_iterator_next(sparse_bitmap_iterator_t *this) > +{ > + int next = this->_next; > + > + this->_next = (this->_next + 1) & (this->_nbits - 1); > + if (this->_next == this->_start) > + this->_next = -1; > + > + return this->_base.il[next]; > +} > + > +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this) > +{ > + this->start = __sparse_iterator_start; > + this->has_next = __sparse_iterator_has_next; > + this->next = __sparse_iterator_next; > + > + this->_start = -1; > + this->_next = this->_start; > +} > + > +/* > + * Generic byte-width atomic set/clear > + */ > +static inline void atomic_byte_set( > + unsigned char *addr, unsigned int bit) > +{ > + unsigned char load, store; > + unsigned char set = 1 << (bit & (BITS_PER_BYTE - 1)); > + > + do { > + load = *addr; > + store = load | set; > + } while (!__atomic_compare_exchange_n(addr, &load, store, > + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); > +} > + > +static inline void atomic_byte_clear( > + unsigned char *addr, unsigned int bit) > +{ > + unsigned char load, store; > + unsigned char clear = 1 << (bit & (BITS_PER_BYTE - 1)); > + > + do { > + load = *addr; > + store = load & ~clear; > + } while (!__atomic_compare_exchange_n(addr, &load, store, > + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); > +} > + > +static inline unsigned char *__bit_byte( > + unsigned long *word, unsigned int bit) > +{ > + unsigned int i; > + unsigned char *b; > + > + b = (unsigned char *)word; > + > + i = bit & (BITS_PER_LONG - 1); > + i = i / BITS_PER_BYTE; > + > +#if (ODP_BYTE_ORDER == ODP_BIG_ENDIAN) > + i = BYTES_PER_LONG - 1 - i; > +#endif > + return &b[i]; > +} > + > +void raw_bitmap_set(unsigned long *map, unsigned int bit) > +{ > + unsigned long *p = map + BIT_WORD(bit); > + > + atomic_byte_set(__bit_byte(p, bit), bit); > +} > + > +void raw_bitmap_clear(unsigned long *map, unsigned int bit) > +{ > + unsigned long *p = map + BIT_WORD(bit); > + > + atomic_byte_clear(__bit_byte(p, bit), bit); > +} > -- > 2.7.4 >
Yes, ARRAY_SIZE is a kernel macro, I looked into the checkpatch.pl and see no flag to enable/disable this check, shall we comment it out or remove that piece of code? Best Regards, Yi On 12 January 2017 at 07:40, Bill Fischofer <bill.fischofer@linaro.org> wrote: > On Wed, Jan 11, 2017 at 1:50 AM, Yi He <yi.he@linaro.org> wrote: > > Add C++ template alike bitmap<size> to allow > > instantiate bitmap data structure of any size, > > and provide iterators to help walking through > > the bitmap objects. > > > > Signed-off-by: Yi He <yi.he@linaro.org> > > --- > > platform/linux-generic/Makefile.am | 2 + > > .../linux-generic/include/odp_bitmap_internal.h | 317 > +++++++++++++++++++++ > > platform/linux-generic/odp_bitmap.c | 315 > ++++++++++++++++++++ > > 3 files changed, 634 insertions(+) > > create mode 100644 platform/linux-generic/include/odp_bitmap_internal.h > > create mode 100644 platform/linux-generic/odp_bitmap.c > > > > diff --git a/platform/linux-generic/Makefile.am > b/platform/linux-generic/Makefile.am > > index 999a7f5..5b38c7b 100644 > > --- a/platform/linux-generic/Makefile.am > > +++ b/platform/linux-generic/Makefile.am > > @@ -130,6 +130,7 @@ noinst_HEADERS = \ > > ${srcdir}/include/odp_align_internal.h \ > > ${srcdir}/include/odp_atomic_internal.h \ > > ${srcdir}/include/odp_buffer_inlines.h \ > > + ${srcdir}/include/odp_bitmap_internal.h \ > > ${srcdir}/include/odp_buffer_internal.h \ > > ${srcdir}/include/odp_classification_datamodel.h \ > > ${srcdir}/include/odp_classification_inlines.h \ > > @@ -173,6 +174,7 @@ __LIB__libodp_linux_la_SOURCES = \ > > _ishmphy.c \ > > odp_atomic.c \ > > odp_barrier.c \ > > + odp_bitmap.c \ > > odp_buffer.c \ > > odp_byteorder.c \ > > odp_classification.c \ > > diff --git a/platform/linux-generic/include/odp_bitmap_internal.h > b/platform/linux-generic/include/odp_bitmap_internal.h > > new file mode 100644 > > index 0000000..1be4d02 > > --- /dev/null > > +++ b/platform/linux-generic/include/odp_bitmap_internal.h > > @@ -0,0 +1,317 @@ > > +/* Copyright (c) 2016, Linaro Limited > > + * All rights reserved. > > + * > > + * SPDX-License-Identifier: BSD-3-Clause > > + */ > > + > > +/** > > + * @file > > + * > > + * ODP generic bitmap types and operations. > > + */ > > + > > +#ifndef ODP_BITMAP_INTERNAL_H_ > > +#define ODP_BITMAP_INTERNAL_H_ > > + > > +#ifdef __cplusplus > > +extern "C" { > > +#endif > > + > > +#include <stdint.h> > > +#include <stdbool.h> > > +#include <string.h> > > +#include <odp/api/hints.h> > > + > > +/* Generate unique identifier for instantiated class */ > > +#define TOKENIZE(template, line) \ > > + template ## _ ## line ## _ ## __COUNTER__ > > + > > +/* Array size in general */ > > +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) > > Checkpatch flags this with the following: > --- > WARNING: Prefer ARRAY_SIZE(array) > #76: FILE: platform/linux-generic/include/odp_bitmap_internal.h:30: > +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) > > total: 0 errors, 1 warnings, 0 checks, 646 lines checked > > NOTE: Ignored message types: BIT_MACRO COMPARISON_TO_NULL > DEPRECATED_VARIABLE NEW_TYPEDEFS SPLIT_STRING SSCANF_TO_KSTRTO > > 0003-linux-gen-add-generic-bitmaps-and-iterators.patch has style > problems, please review. > --- > > I suspect that ARRAY_SIZE is a Linux internal macro, in which case our > internal checkpatch rules may need updating. > > + > > +#define BITS_PER_BYTE (8) > > +#define BITS_PER_LONG __WORDSIZE > > +#define BYTES_PER_LONG (BITS_PER_LONG / BITS_PER_BYTE) > > + > > +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) > > +#define BITS_TO_LONGS(nr) BIT_WORD(nr + BITS_PER_LONG - 1) > > + > > +#define BITMAP_FIRST_WORD_MASK(start) \ > > + (~0UL << ((start) & (BITS_PER_LONG - 1))) > > +#define BITMAP_LAST_WORD_MASK(nbits) \ > > + (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) > > + > > +/* WAPL bitmap base class */ > > +typedef struct { > > + unsigned int nwords; > > + unsigned int *pl; > > + unsigned long *ul; > > +} wapl_bitmap_t; > > + > > +/* > > + * Word-Aligned Position List (WAPL) bitmap, which actually > > + * is not a compression, but with an extra list of non-empty > > + * word positions. > > + * > > + * WAPL accelerates bitwise operations and iterations by > > + * applying only to non-empty positions instead of walking > > + * through the whole bitmap. > > + * > > + * WAPL uses [1 ~ N] instead of [0 ~ N - 1] as position > > + * values and an extra 0 as end indicator for position list. > > + * This is the reason to allocate one extra room below. > > + */ > > +#define instantiate_wapl_bitmap(line, nbits) \ > > + struct TOKENIZE(wapl_bitmap, line) { \ > > + unsigned int pl[BITS_TO_LONGS(nbits) + 1]; \ > > + unsigned long ul[BITS_TO_LONGS(nbits) + 1]; \ > > + } > > + > > +#define WAPL_BITMAP(nbits) instantiate_wapl_bitmap(__LINE__, nbits) > > + > > +/* > > + * Upcast any derived WAPL bitmap class to its base class > > + */ > > +#define __wapl_upcast(base, derived) \ > > + do { \ > > + __typeof__(derived) p = derived; \ > > + base.pl = p->pl; \ > > + base.ul = p->ul; \ > > + base.nwords = ARRAY_SIZE(p->ul) - 1; \ > > + } while (0) > > + > > +/* > > + * WAPL base class bitmap operations > > + */ > > +void __wapl_bitmap_and(wapl_bitmap_t *dst, > > + wapl_bitmap_t *src, wapl_bitmap_t *and); > > + > > +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or); > > + > > +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit); > > + > > +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit); > > + > > +/* > > + * Generic WAPL bitmap operations > > + */ > > +#define wapl_bitmap_zero(map) \ > > + ({ \ > > + __typeof__(map) p = map; \ > > + memset((void *)p, 0, sizeof(__typeof__(*p))); \ > > + }) > > + > > +#define wapl_bitmap_copy(dst, src) \ > > + ({ \ > > + __typeof__(dst) d = dst; \ > > + __typeof__(src) s = src; \ > > + if (d != s) \ > > + memcpy((void *)d, (void *)s, \ > > + sizeof(__typeof__(*d))); \ > > + }) > > + > > +#define wapl_bitmap_and(dst, src, and) \ > > + ({ \ > > + wapl_bitmap_t d, s, a; \ > > + __wapl_upcast(d, dst); \ > > + __wapl_upcast(s, src); \ > > + __wapl_upcast(a, and); \ > > + __wapl_bitmap_and(&d, &s, &a); \ > > + }) > > + > > +#define wapl_bitmap_or(dst, src, or) \ > > + ({ \ > > + wapl_bitmap_t d, o; \ > > + wapl_bitmap_copy(dst, src); \ > > + __wapl_upcast(d, dst); \ > > + __wapl_upcast(o, or); \ > > + __wapl_bitmap_or(&d, &o); \ > > + }) > > + > > +#define wapl_bitmap_set(map, bit) \ > > + ({ \ > > + wapl_bitmap_t b; \ > > + __wapl_upcast(b, map); \ > > + __wapl_bitmap_set(&b, bit); \ > > + }) > > + > > +#define wapl_bitmap_clear(map, bit) \ > > + ({ \ > > + wapl_bitmap_t b; \ > > + __wapl_upcast(b, map); \ > > + __wapl_bitmap_clear(&b, bit); \ > > + }) > > + > > +/* > > + * Round robin iterator runs upon a WAPL bitmap: > > + * > > + * wapl_bitmap_iterator(iterator, WAPL bitmap); > > + * for (iterator->start(); iterator->has_next(); ) { > > + * unsigned int bit_index = iterator->next(); > > + * ...operations on this bit index... > > + * } > > + */ > > +typedef struct wapl_bitmap_iterator { > > + int _start, _next, _nbits; > > + wapl_bitmap_t _base; > > + > > + void (*start)(struct wapl_bitmap_iterator *this); > > + bool (*has_next)(struct wapl_bitmap_iterator *this); > > + unsigned int (*next)(struct wapl_bitmap_iterator *this); > > +} wapl_bitmap_iterator_t; > > + > > +/* > > + * WAPL bitmap iterator constructor > > + */ > > +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this); > > + > > +/* > > + * Generic constructor accepts any derived WAPL bitmap class > > + */ > > +#define wapl_bitmap_iterator(iterator, map) \ > > + ({ \ > > + __typeof__(iterator) __it = iterator; \ > > + __wapl_upcast(__it->_base, map); \ > > + __wapl_bitmap_iterator(__it); \ > > + }) > > + > > +/* Sparse bitmap base class */ > > +typedef struct { > > + unsigned int nbits; > > + unsigned int *last, *pl, *il; > > +} sparse_bitmap_t; > > + > > +/* > > + * Sparse bitmap, lists all bit indexes directly as an array. > > + * Expected to be significantly straightforward iteration. > > + */ > > +#define instantiate_sparse_bitmap(line, nbits) \ > > + struct TOKENIZE(sparse_bitmap, line) { \ > > + unsigned int last; \ > > + unsigned int pl[nbits]; \ > > + unsigned int il[nbits]; \ > > + } > > + > > +#define SPARSE_BITMAP(nbits) instantiate_sparse_bitmap(__LINE__, nbits) > > + > > +/* > > + * Upcast any derived sparse bitmap class to its base class > > + */ > > +#define __sparse_upcast(base, derived) \ > > + do { \ > > + __typeof__(derived) p = derived; \ > > + base.pl = p->pl; \ > > + base.il = p->il; \ > > + base.last = &p->last; \ > > + base.nbits = ARRAY_SIZE(p->il); \ > > + } while (0) > > + > > +/* > > + * Sparse base class bitmap operations > > + */ > > +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit); > > + > > +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit); > > + > > +/* > > + * Generic sparse bitmap operations > > + */ > > +#define sparse_bitmap_zero(map) \ > > + ({ \ > > + __typeof__(map) p = map; \ > > + memset((void *)p, 0, sizeof(__typeof__(*p))); \ > > + }) > > + > > +#define sparse_bitmap_set(map, bit) \ > > + ({ \ > > + sparse_bitmap_t b; \ > > + __sparse_upcast(b, map); \ > > + __sparse_bitmap_set(&b, bit); \ > > + }) > > + > > +#define sparse_bitmap_clear(map, bit) \ > > + ({ \ > > + sparse_bitmap_t b; \ > > + __sparse_upcast(b, map); \ > > + __sparse_bitmap_clear(&b, bit); \ > > + }) > > + > > +/* > > + * Round robin iterator runs upon a sparse bitmap: > > + * > > + * sparse_bitmap_iterator(iterator, SPARSE bitmap); > > + * for (iterator->start(); iterator->has_next(); ) { > > + * unsigned int bit_index = iterator->next(); > > + * ...operations on this bit index... > > + * } > > + */ > > +typedef struct sparse_bitmap_iterator { > > + int _start, _next, _nbits; > > + sparse_bitmap_t _base; > > + > > + void (*start)(struct sparse_bitmap_iterator *this); > > + bool (*has_next)(struct sparse_bitmap_iterator *this); > > + unsigned int (*next)(struct sparse_bitmap_iterator *this); > > +} sparse_bitmap_iterator_t; > > + > > +/* > > + * Sparse bitmap iterator constructor > > + */ > > +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this); > > + > > +/* > > + * Generic constructor accepts any derived sparse bitmap class. > > + */ > > +#define sparse_bitmap_iterator(iterator, map) \ > > + ({ \ > > + __typeof__(iterator) __it = iterator; \ > > + __sparse_upcast(__it->_base, map); \ > > + __sparse_bitmap_iterator(__it); \ > > + }) > > + > > +/* > > + * Raw bitmap atomic set and clear. > > + */ > > +void raw_bitmap_set(unsigned long *map, unsigned int bit); > > + > > +void raw_bitmap_clear(unsigned long *map, unsigned int bit); > > + > > +/* > > + * It will enter infinite loop incase that all bits are zero, > > + * so please make sure the bitmap at least has one set. > > + */ > > +static inline int __bitmap_wraparound_next( > > + unsigned long *addr, unsigned int nbits, int start) > > +{ > > + unsigned long tmp; > > + > > + if (start >= (int)nbits) > > + start = 0; > > + > > + tmp = addr[BIT_WORD(start)]; > > + > > + /* Handle 1st word. */ > > + tmp &= BITMAP_FIRST_WORD_MASK(start); > > + start = start & ~(BITS_PER_LONG - 1); > > + > > + while (!tmp) { > > + start += BITS_PER_LONG; > > + if (start >= (int)nbits) > > + start = 0; > > + > > + tmp = addr[BIT_WORD(start)]; > > + } > > + > > + start += __builtin_ffsl(tmp) - 1; > > + return start; > > +} > > + > > +/** > > + * @} > > + */ > > + > > +#ifdef __cplusplus > > +} > > +#endif > > + > > +#endif > > diff --git a/platform/linux-generic/odp_bitmap.c > b/platform/linux-generic/odp_bitmap.c > > new file mode 100644 > > index 0000000..a29b9ef > > --- /dev/null > > +++ b/platform/linux-generic/odp_bitmap.c > > @@ -0,0 +1,315 @@ > > +/* Copyright (c) 2016, Linaro Limited > > + * All rights reserved. > > + * > > + * SPDX-License-Identifier: BSD-3-Clause > > + */ > > + > > +#include <string.h> > > +#include <unistd.h> > > +#include <odp/api/std_types.h> > > +#include <odp/api/byteorder.h> > > +#include <odp_bitmap_internal.h> > > + > > +/* > > + * WAPL base class bitmap operations > > + */ > > +static inline void __wapl_add_pos( > > + wapl_bitmap_t *map, unsigned int p) > > +{ > > + unsigned int s, k = 0; > > + unsigned int *pl = map->pl; > > + > > + while (pl[k] && p > pl[k]) > > + k++; > > + > > + if (p == pl[k]) > > + return; > > + > > + /* sorted insertion */ > > + for (; pl[k] && p < pl[k]; k++) { > > + s = pl[k]; > > + pl[k] = p; > > + p = s; > > + } > > + > > + if (k < map->nwords) > > + pl[k++] = p; > > + > > + pl[k] = 0; > > +} > > + > > +static inline void __wapl_remove_pos( > > + wapl_bitmap_t *map, unsigned int p) > > +{ > > + unsigned int k = 0; > > + unsigned int *pl = map->pl; > > + > > + while (pl[k] && p != pl[k]) > > + k++; > > + > > + for (; pl[k]; k++) > > + pl[k] = pl[k + 1]; > > +} > > + > > +void __wapl_bitmap_and(wapl_bitmap_t *dst, > > + wapl_bitmap_t *src, wapl_bitmap_t *and) > > +{ > > + unsigned int k = 0, p; > > + unsigned int *pl = src->pl; > > + > > + while ((p = *pl++) != 0) { > > + dst->ul[p] = src->ul[p] & and->ul[p]; > > + if (dst->ul[p]) > > + dst->pl[k++] = p; > > + } > > + > > + dst->pl[k] = 0; > > +} > > + > > +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or) > > +{ > > + unsigned int p; > > + unsigned int *pl = or->pl; > > + > > + while ((p = *pl++) != 0) { > > + if (dst->ul[p] == 0) > > + __wapl_add_pos(dst, p); > > + > > + dst->ul[p] |= or->ul[p]; > > + } > > +} > > + > > +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit) > > +{ > > + unsigned int p = BIT_WORD(bit) + 1; > > + unsigned long set = 1UL << (bit & (BITS_PER_LONG - 1)); > > + > > + if (p > map->nwords) > > + return; > > + > > + if (map->ul[p] == 0) > > + __wapl_add_pos(map, p); > > + > > + map->ul[p] |= set; > > +} > > + > > +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit) > > +{ > > + unsigned int p = BIT_WORD(bit) + 1; > > + unsigned long clear = 1UL << (bit & (BITS_PER_LONG - 1)); > > + > > + if (p > map->nwords) > > + return; > > + > > + map->ul[p] &= ~clear; > > + > > + if (map->ul[p] == 0) > > + __wapl_remove_pos(map, p); > > +} > > + > > +/* > > + * WAPL bitmap iterator implementation > > + */ > > +static void __wapl_iterator_start(wapl_bitmap_iterator_t *this) > > +{ > > + this->_nbits = this->_base.nwords * BITS_PER_LONG; > > + > > + /* Advance to next queue index to start this > > + * new round iteration. > > + */ > > + if (this->_base.pl[0] == 0) > > + this->_start = -1; > > + else > > + this->_start = __bitmap_wraparound_next( > > + &this->_base.ul[1], this->_nbits, this->_start + > 1); > > + > > + this->_next = this->_start; > > +} > > + > > +static bool __wapl_iterator_has_next(wapl_bitmap_iterator_t *this) > > +{ > > + return (this->_next != -1); > > +} > > + > > +static unsigned int __wapl_iterator_next(wapl_bitmap_iterator_t *this) > > +{ > > + int next = this->_next; > > + > > + this->_next = __bitmap_wraparound_next( > > + &this->_base.ul[1], this->_nbits, this->_next + > 1); > > + > > + if (this->_next == this->_start) > > + this->_next = -1; > > + > > + return next; > > +} > > + > > +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this) > > +{ > > + this->start = __wapl_iterator_start; > > + this->has_next = __wapl_iterator_has_next; > > + this->next = __wapl_iterator_next; > > + > > + this->_start = -1; > > + this->_next = this->_start; > > +} > > + > > +/* > > + * Sparse base class bitmap operations > > + */ > > +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit) > > +{ > > + unsigned int last = *map->last; > > + > > + /* Index exceeds */ > > + if (bit >= map->nbits) > > + return; > > + > > + /* Full bitmap */ > > + if (last >= map->nbits) > > + return; > > + > > + /* Bit was not set previously, > > + * also record where we set the bit > > + */ > > + if (!map->pl[bit]) { > > + map->il[last++] = bit; > > + map->pl[bit] = last; > > + > > + *map->last = last; > > + } > > +} > > + > > +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit) > > +{ > > + unsigned int p, i; > > + unsigned int last = *map->last; > > + > > + /* Index exceeds */ > > + if (bit >= map->nbits) > > + return; > > + > > + /* Empty bitmap */ > > + if (last == 0) > > + return; > > + > > + /* Bit was set previously */ > > + if (map->pl[bit]) { > > + p = map->pl[bit] - 1; > > + map->pl[bit] = 0; > > + > > + last--; > > + *map->last = last; > > + > > + /* Fill the hole with the latest index */ > > + if (p < last) { > > + i = map->il[last]; > > + map->pl[i] = p + 1; > > + map->il[p] = i; > > + } > > + } > > +} > > + > > +/* > > + * Sparse bitmap iterator implementation > > + */ > > +static void __sparse_iterator_start(sparse_bitmap_iterator_t *this) > > +{ > > + this->_nbits = (int)*this->_base.last; > > + > > + /* Advance to next queue index to start this > > + * new round iteration. > > + */ > > + if (this->_nbits == 0) > > + this->_start = -1; > > + else > > + this->_start = (this->_start + 1) & (this->_nbits - 1); > > + > > + this->_next = this->_start; > > +} > > + > > +static bool __sparse_iterator_has_next(sparse_bitmap_iterator_t *this) > > +{ > > + return (this->_next != -1); > > +} > > + > > +static unsigned int __sparse_iterator_next(sparse_bitmap_iterator_t > *this) > > +{ > > + int next = this->_next; > > + > > + this->_next = (this->_next + 1) & (this->_nbits - 1); > > + if (this->_next == this->_start) > > + this->_next = -1; > > + > > + return this->_base.il[next]; > > +} > > + > > +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this) > > +{ > > + this->start = __sparse_iterator_start; > > + this->has_next = __sparse_iterator_has_next; > > + this->next = __sparse_iterator_next; > > + > > + this->_start = -1; > > + this->_next = this->_start; > > +} > > + > > +/* > > + * Generic byte-width atomic set/clear > > + */ > > +static inline void atomic_byte_set( > > + unsigned char *addr, unsigned int bit) > > +{ > > + unsigned char load, store; > > + unsigned char set = 1 << (bit & (BITS_PER_BYTE - 1)); > > + > > + do { > > + load = *addr; > > + store = load | set; > > + } while (!__atomic_compare_exchange_n(addr, &load, store, > > + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); > > +} > > + > > +static inline void atomic_byte_clear( > > + unsigned char *addr, unsigned int bit) > > +{ > > + unsigned char load, store; > > + unsigned char clear = 1 << (bit & (BITS_PER_BYTE - 1)); > > + > > + do { > > + load = *addr; > > + store = load & ~clear; > > + } while (!__atomic_compare_exchange_n(addr, &load, store, > > + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); > > +} > > + > > +static inline unsigned char *__bit_byte( > > + unsigned long *word, unsigned int bit) > > +{ > > + unsigned int i; > > + unsigned char *b; > > + > > + b = (unsigned char *)word; > > + > > + i = bit & (BITS_PER_LONG - 1); > > + i = i / BITS_PER_BYTE; > > + > > +#if (ODP_BYTE_ORDER == ODP_BIG_ENDIAN) > > + i = BYTES_PER_LONG - 1 - i; > > +#endif > > + return &b[i]; > > +} > > + > > +void raw_bitmap_set(unsigned long *map, unsigned int bit) > > +{ > > + unsigned long *p = map + BIT_WORD(bit); > > + > > + atomic_byte_set(__bit_byte(p, bit), bit); > > +} > > + > > +void raw_bitmap_clear(unsigned long *map, unsigned int bit) > > +{ > > + unsigned long *p = map + BIT_WORD(bit); > > + > > + atomic_byte_clear(__bit_byte(p, bit), bit); > > +} > > -- > > 2.7.4 > > >
On 01/12/17 04:17, Yi He wrote: > Yes, ARRAY_SIZE is a kernel macro, I looked into the checkpatch.pl > <http://checkpatch.pl> and see no flag to enable/disable this check, > shall we comment it out or remove that piece of code? > > Best Regards, Yi yes, that warning is ok. Maxim. > > On 12 January 2017 at 07:40, Bill Fischofer <bill.fischofer@linaro.org > <mailto:bill.fischofer@linaro.org>> wrote: > > On Wed, Jan 11, 2017 at 1:50 AM, Yi He <yi.he@linaro.org > <mailto:yi.he@linaro.org>> wrote: > > Add C++ template alike bitmap<size> to allow > > instantiate bitmap data structure of any size, > > and provide iterators to help walking through > > the bitmap objects. > > > > Signed-off-by: Yi He <yi.he@linaro.org <mailto:yi.he@linaro.org>> > > --- > > platform/linux-generic/Makefile.am | 2 + > > .../linux-generic/include/odp_bitmap_internal.h | 317 > +++++++++++++++++++++ > > platform/linux-generic/odp_bitmap.c | 315 > ++++++++++++++++++++ > > 3 files changed, 634 insertions(+) > > create mode 100644 > platform/linux-generic/include/odp_bitmap_internal.h > > create mode 100644 platform/linux-generic/odp_bitmap.c > > > > diff --git a/platform/linux-generic/Makefile.am > b/platform/linux-generic/Makefile.am > > index 999a7f5..5b38c7b 100644 > > --- a/platform/linux-generic/Makefile.am > > +++ b/platform/linux-generic/Makefile.am > > @@ -130,6 +130,7 @@ noinst_HEADERS = \ > > ${srcdir}/include/odp_align_internal.h \ > > ${srcdir}/include/odp_atomic_internal.h \ > > ${srcdir}/include/odp_buffer_inlines.h \ > > + ${srcdir}/include/odp_bitmap_internal.h \ > > ${srcdir}/include/odp_buffer_internal.h \ > > ${srcdir}/include/odp_classification_datamodel.h \ > > ${srcdir}/include/odp_classification_inlines.h \ > > @@ -173,6 +174,7 @@ __LIB__libodp_linux_la_SOURCES = \ > > _ishmphy.c \ > > odp_atomic.c \ > > odp_barrier.c \ > > + odp_bitmap.c \ > > odp_buffer.c \ > > odp_byteorder.c \ > > odp_classification.c \ > > diff --git a/platform/linux-generic/include/odp_bitmap_internal.h > b/platform/linux-generic/include/odp_bitmap_internal.h > > new file mode 100644 > > index 0000000..1be4d02 > > --- /dev/null > > +++ b/platform/linux-generic/include/odp_bitmap_internal.h > > @@ -0,0 +1,317 @@ > > +/* Copyright (c) 2016, Linaro Limited > > + * All rights reserved. > > + * > > + * SPDX-License-Identifier: BSD-3-Clause > > + */ > > + > > +/** > > + * @file > > + * > > + * ODP generic bitmap types and operations. > > + */ > > + > > +#ifndef ODP_BITMAP_INTERNAL_H_ > > +#define ODP_BITMAP_INTERNAL_H_ > > + > > +#ifdef __cplusplus > > +extern "C" { > > +#endif > > + > > +#include <stdint.h> > > +#include <stdbool.h> > > +#include <string.h> > > +#include <odp/api/hints.h> > > + > > +/* Generate unique identifier for instantiated class */ > > +#define TOKENIZE(template, line) \ > > + template ## _ ## line ## _ ## __COUNTER__ > > + > > +/* Array size in general */ > > +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) > > Checkpatch flags this with the following: > --- > WARNING: Prefer ARRAY_SIZE(array) > #76: FILE: platform/linux-generic/include/odp_bitmap_internal.h:30: > +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) > > total: 0 errors, 1 warnings, 0 checks, 646 lines checked > > NOTE: Ignored message types: BIT_MACRO COMPARISON_TO_NULL > DEPRECATED_VARIABLE NEW_TYPEDEFS SPLIT_STRING SSCANF_TO_KSTRTO > > 0003-linux-gen-add-generic-bitmaps-and-iterators.patch has style > problems, please review. > --- > > I suspect that ARRAY_SIZE is a Linux internal macro, in which case our > internal checkpatch rules may need updating. > > + > > +#define BITS_PER_BYTE (8) > > +#define BITS_PER_LONG __WORDSIZE > > +#define BYTES_PER_LONG (BITS_PER_LONG / BITS_PER_BYTE) > > + > > +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) > > +#define BITS_TO_LONGS(nr) BIT_WORD(nr + BITS_PER_LONG - 1) > > + > > +#define BITMAP_FIRST_WORD_MASK(start) \ > > + (~0UL << ((start) & (BITS_PER_LONG - 1))) > > +#define BITMAP_LAST_WORD_MASK(nbits) \ > > + (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) > > + > > +/* WAPL bitmap base class */ > > +typedef struct { > > + unsigned int nwords; > > + unsigned int *pl; > > + unsigned long *ul; > > +} wapl_bitmap_t; > > + > > +/* > > + * Word-Aligned Position List (WAPL) bitmap, which actually > > + * is not a compression, but with an extra list of non-empty > > + * word positions. > > + * > > + * WAPL accelerates bitwise operations and iterations by > > + * applying only to non-empty positions instead of walking > > + * through the whole bitmap. > > + * > > + * WAPL uses [1 ~ N] instead of [0 ~ N - 1] as position > > + * values and an extra 0 as end indicator for position list. > > + * This is the reason to allocate one extra room below. > > + */ > > +#define instantiate_wapl_bitmap(line, nbits) \ > > + struct TOKENIZE(wapl_bitmap, line) { \ > > + unsigned int pl[BITS_TO_LONGS(nbits) + 1]; \ > > + unsigned long ul[BITS_TO_LONGS(nbits) + 1]; \ > > + } > > + > > +#define WAPL_BITMAP(nbits) instantiate_wapl_bitmap(__LINE__, nbits) > > + > > +/* > > + * Upcast any derived WAPL bitmap class to its base class > > + */ > > +#define __wapl_upcast(base, derived) \ > > + do { \ > > + __typeof__(derived) p = derived; \ > > + base.pl <http://base.pl> = p->pl; > \ > > + base.ul = p->ul; \ > > + base.nwords = ARRAY_SIZE(p->ul) - 1; \ > > + } while (0) > > + > > +/* > > + * WAPL base class bitmap operations > > + */ > > +void __wapl_bitmap_and(wapl_bitmap_t *dst, > > + wapl_bitmap_t *src, wapl_bitmap_t *and); > > + > > +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or); > > + > > +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit); > > + > > +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit); > > + > > +/* > > + * Generic WAPL bitmap operations > > + */ > > +#define wapl_bitmap_zero(map) \ > > + ({ \ > > + __typeof__(map) p = map; \ > > + memset((void *)p, 0, sizeof(__typeof__(*p))); \ > > + }) > > + > > +#define wapl_bitmap_copy(dst, src) \ > > + ({ \ > > + __typeof__(dst) d = dst; \ > > + __typeof__(src) s = src; \ > > + if (d != s) \ > > + memcpy((void *)d, (void *)s, \ > > + sizeof(__typeof__(*d))); \ > > + }) > > + > > +#define wapl_bitmap_and(dst, src, and) \ > > + ({ \ > > + wapl_bitmap_t d, s, a; \ > > + __wapl_upcast(d, dst); \ > > + __wapl_upcast(s, src); \ > > + __wapl_upcast(a, and); \ > > + __wapl_bitmap_and(&d, &s, &a); \ > > + }) > > + > > +#define wapl_bitmap_or(dst, src, or) \ > > + ({ \ > > + wapl_bitmap_t d, o; \ > > + wapl_bitmap_copy(dst, src); \ > > + __wapl_upcast(d, dst); \ > > + __wapl_upcast(o, or); \ > > + __wapl_bitmap_or(&d, &o); \ > > + }) > > + > > +#define wapl_bitmap_set(map, bit) \ > > + ({ \ > > + wapl_bitmap_t b; \ > > + __wapl_upcast(b, map); \ > > + __wapl_bitmap_set(&b, bit); \ > > + }) > > + > > +#define wapl_bitmap_clear(map, bit) \ > > + ({ \ > > + wapl_bitmap_t b; \ > > + __wapl_upcast(b, map); \ > > + __wapl_bitmap_clear(&b, bit); \ > > + }) > > + > > +/* > > + * Round robin iterator runs upon a WAPL bitmap: > > + * > > + * wapl_bitmap_iterator(iterator, WAPL bitmap); > > + * for (iterator->start(); iterator->has_next(); ) { > > + * unsigned int bit_index = iterator->next(); > > + * ...operations on this bit index... > > + * } > > + */ > > +typedef struct wapl_bitmap_iterator { > > + int _start, _next, _nbits; > > + wapl_bitmap_t _base; > > + > > + void (*start)(struct wapl_bitmap_iterator *this); > > + bool (*has_next)(struct wapl_bitmap_iterator *this); > > + unsigned int (*next)(struct wapl_bitmap_iterator *this); > > +} wapl_bitmap_iterator_t; > > + > > +/* > > + * WAPL bitmap iterator constructor > > + */ > > +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this); > > + > > +/* > > + * Generic constructor accepts any derived WAPL bitmap class > > + */ > > +#define wapl_bitmap_iterator(iterator, map) \ > > + ({ \ > > + __typeof__(iterator) __it = iterator; \ > > + __wapl_upcast(__it->_base, map); \ > > + __wapl_bitmap_iterator(__it); \ > > + }) > > + > > +/* Sparse bitmap base class */ > > +typedef struct { > > + unsigned int nbits; > > + unsigned int *last, *pl, *il; > > +} sparse_bitmap_t; > > + > > +/* > > + * Sparse bitmap, lists all bit indexes directly as an array. > > + * Expected to be significantly straightforward iteration. > > + */ > > +#define instantiate_sparse_bitmap(line, nbits) \ > > + struct TOKENIZE(sparse_bitmap, line) { \ > > + unsigned int last; \ > > + unsigned int pl[nbits]; \ > > + unsigned int il[nbits]; \ > > + } > > + > > +#define SPARSE_BITMAP(nbits) instantiate_sparse_bitmap(__LINE__, > nbits) > > + > > +/* > > + * Upcast any derived sparse bitmap class to its base class > > + */ > > +#define __sparse_upcast(base, derived) \ > > + do { \ > > + __typeof__(derived) p = derived; \ > > + base.pl <http://base.pl> = p->pl; > \ > > + base.il <http://base.il> = p->il; > \ > > + base.last = &p->last; \ > > + base.nbits = ARRAY_SIZE(p->il); \ > > + } while (0) > > + > > +/* > > + * Sparse base class bitmap operations > > + */ > > +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit); > > + > > +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit); > > + > > +/* > > + * Generic sparse bitmap operations > > + */ > > +#define sparse_bitmap_zero(map) > \ > > + ({ \ > > + __typeof__(map) p = map; \ > > + memset((void *)p, 0, sizeof(__typeof__(*p))); \ > > + }) > > + > > +#define sparse_bitmap_set(map, bit) \ > > + ({ \ > > + sparse_bitmap_t b; \ > > + __sparse_upcast(b, map); \ > > + __sparse_bitmap_set(&b, bit); \ > > + }) > > + > > +#define sparse_bitmap_clear(map, bit) \ > > + ({ \ > > + sparse_bitmap_t b; \ > > + __sparse_upcast(b, map); \ > > + __sparse_bitmap_clear(&b, bit); \ > > + }) > > + > > +/* > > + * Round robin iterator runs upon a sparse bitmap: > > + * > > + * sparse_bitmap_iterator(iterator, SPARSE bitmap); > > + * for (iterator->start(); iterator->has_next(); ) { > > + * unsigned int bit_index = iterator->next(); > > + * ...operations on this bit index... > > + * } > > + */ > > +typedef struct sparse_bitmap_iterator { > > + int _start, _next, _nbits; > > + sparse_bitmap_t _base; > > + > > + void (*start)(struct sparse_bitmap_iterator *this); > > + bool (*has_next)(struct sparse_bitmap_iterator *this); > > + unsigned int (*next)(struct sparse_bitmap_iterator *this); > > +} sparse_bitmap_iterator_t; > > + > > +/* > > + * Sparse bitmap iterator constructor > > + */ > > +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this); > > + > > +/* > > + * Generic constructor accepts any derived sparse bitmap class. > > + */ > > +#define sparse_bitmap_iterator(iterator, map) \ > > + ({ \ > > + __typeof__(iterator) __it = iterator; \ > > + __sparse_upcast(__it->_base, map); \ > > + __sparse_bitmap_iterator(__it); \ > > + }) > > + > > +/* > > + * Raw bitmap atomic set and clear. > > + */ > > +void raw_bitmap_set(unsigned long *map, unsigned int bit); > > + > > +void raw_bitmap_clear(unsigned long *map, unsigned int bit); > > + > > +/* > > + * It will enter infinite loop incase that all bits are zero, > > + * so please make sure the bitmap at least has one set. > > + */ > > +static inline int __bitmap_wraparound_next( > > + unsigned long *addr, unsigned int nbits, int start) > > +{ > > + unsigned long tmp; > > + > > + if (start >= (int)nbits) > > + start = 0; > > + > > + tmp = addr[BIT_WORD(start)]; > > + > > + /* Handle 1st word. */ > > + tmp &= BITMAP_FIRST_WORD_MASK(start); > > + start = start & ~(BITS_PER_LONG - 1); > > + > > + while (!tmp) { > > + start += BITS_PER_LONG; > > + if (start >= (int)nbits) > > + start = 0; > > + > > + tmp = addr[BIT_WORD(start)]; > > + } > > + > > + start += __builtin_ffsl(tmp) - 1; > > + return start; > > +} > > + > > +/** > > + * @} > > + */ > > + > > +#ifdef __cplusplus > > +} > > +#endif > > + > > +#endif > > diff --git a/platform/linux-generic/odp_bitmap.c > b/platform/linux-generic/odp_bitmap.c > > new file mode 100644 > > index 0000000..a29b9ef > > --- /dev/null > > +++ b/platform/linux-generic/odp_bitmap.c > > @@ -0,0 +1,315 @@ > > +/* Copyright (c) 2016, Linaro Limited > > + * All rights reserved. > > + * > > + * SPDX-License-Identifier: BSD-3-Clause > > + */ > > + > > +#include <string.h> > > +#include <unistd.h> > > +#include <odp/api/std_types.h> > > +#include <odp/api/byteorder.h> > > +#include <odp_bitmap_internal.h> > > + > > +/* > > + * WAPL base class bitmap operations > > + */ > > +static inline void __wapl_add_pos( > > + wapl_bitmap_t *map, unsigned int p) > > +{ > > + unsigned int s, k = 0; > > + unsigned int *pl = map->pl; > > + > > + while (pl[k] && p > pl[k]) > > + k++; > > + > > + if (p == pl[k]) > > + return; > > + > > + /* sorted insertion */ > > + for (; pl[k] && p < pl[k]; k++) { > > + s = pl[k]; > > + pl[k] = p; > > + p = s; > > + } > > + > > + if (k < map->nwords) > > + pl[k++] = p; > > + > > + pl[k] = 0; > > +} > > + > > +static inline void __wapl_remove_pos( > > + wapl_bitmap_t *map, unsigned int p) > > +{ > > + unsigned int k = 0; > > + unsigned int *pl = map->pl; > > + > > + while (pl[k] && p != pl[k]) > > + k++; > > + > > + for (; pl[k]; k++) > > + pl[k] = pl[k + 1]; > > +} > > + > > +void __wapl_bitmap_and(wapl_bitmap_t *dst, > > + wapl_bitmap_t *src, wapl_bitmap_t *and) > > +{ > > + unsigned int k = 0, p; > > + unsigned int *pl = src->pl; > > + > > + while ((p = *pl++) != 0) { > > + dst->ul[p] = src->ul[p] & and->ul[p]; > > + if (dst->ul[p]) > > + dst->pl[k++] = p; > > + } > > + > > + dst->pl[k] = 0; > > +} > > + > > +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or) > > +{ > > + unsigned int p; > > + unsigned int *pl = or->pl; > > + > > + while ((p = *pl++) != 0) { > > + if (dst->ul[p] == 0) > > + __wapl_add_pos(dst, p); > > + > > + dst->ul[p] |= or->ul[p]; > > + } > > +} > > + > > +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit) > > +{ > > + unsigned int p = BIT_WORD(bit) + 1; > > + unsigned long set = 1UL << (bit & (BITS_PER_LONG - 1)); > > + > > + if (p > map->nwords) > > + return; > > + > > + if (map->ul[p] == 0) > > + __wapl_add_pos(map, p); > > + > > + map->ul[p] |= set; > > +} > > + > > +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit) > > +{ > > + unsigned int p = BIT_WORD(bit) + 1; > > + unsigned long clear = 1UL << (bit & (BITS_PER_LONG - 1)); > > + > > + if (p > map->nwords) > > + return; > > + > > + map->ul[p] &= ~clear; > > + > > + if (map->ul[p] == 0) > > + __wapl_remove_pos(map, p); > > +} > > + > > +/* > > + * WAPL bitmap iterator implementation > > + */ > > +static void __wapl_iterator_start(wapl_bitmap_iterator_t *this) > > +{ > > + this->_nbits = this->_base.nwords * BITS_PER_LONG; > > + > > + /* Advance to next queue index to start this > > + * new round iteration. > > + */ > > + if (this->_base.pl <http://base.pl>[0] == 0) > > + this->_start = -1; > > + else > > + this->_start = __bitmap_wraparound_next( > > + &this->_base.ul[1], this->_nbits, > this->_start + 1); > > + > > + this->_next = this->_start; > > +} > > + > > +static bool __wapl_iterator_has_next(wapl_bitmap_iterator_t *this) > > +{ > > + return (this->_next != -1); > > +} > > + > > +static unsigned int __wapl_iterator_next(wapl_bitmap_iterator_t > *this) > > +{ > > + int next = this->_next; > > + > > + this->_next = __bitmap_wraparound_next( > > + &this->_base.ul[1], this->_nbits, > this->_next + 1); > > + > > + if (this->_next == this->_start) > > + this->_next = -1; > > + > > + return next; > > +} > > + > > +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this) > > +{ > > + this->start = __wapl_iterator_start; > > + this->has_next = __wapl_iterator_has_next; > > + this->next = __wapl_iterator_next; > > + > > + this->_start = -1; > > + this->_next = this->_start; > > +} > > + > > +/* > > + * Sparse base class bitmap operations > > + */ > > +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit) > > +{ > > + unsigned int last = *map->last; > > + > > + /* Index exceeds */ > > + if (bit >= map->nbits) > > + return; > > + > > + /* Full bitmap */ > > + if (last >= map->nbits) > > + return; > > + > > + /* Bit was not set previously, > > + * also record where we set the bit > > + */ > > + if (!map->pl[bit]) { > > + map->il[last++] = bit; > > + map->pl[bit] = last; > > + > > + *map->last = last; > > + } > > +} > > + > > +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit) > > +{ > > + unsigned int p, i; > > + unsigned int last = *map->last; > > + > > + /* Index exceeds */ > > + if (bit >= map->nbits) > > + return; > > + > > + /* Empty bitmap */ > > + if (last == 0) > > + return; > > + > > + /* Bit was set previously */ > > + if (map->pl[bit]) { > > + p = map->pl[bit] - 1; > > + map->pl[bit] = 0; > > + > > + last--; > > + *map->last = last; > > + > > + /* Fill the hole with the latest index */ > > + if (p < last) { > > + i = map->il[last]; > > + map->pl[i] = p + 1; > > + map->il[p] = i; > > + } > > + } > > +} > > + > > +/* > > + * Sparse bitmap iterator implementation > > + */ > > +static void __sparse_iterator_start(sparse_bitmap_iterator_t *this) > > +{ > > + this->_nbits = (int)*this->_base.last; > > + > > + /* Advance to next queue index to start this > > + * new round iteration. > > + */ > > + if (this->_nbits == 0) > > + this->_start = -1; > > + else > > + this->_start = (this->_start + 1) & (this->_nbits > - 1); > > + > > + this->_next = this->_start; > > +} > > + > > +static bool __sparse_iterator_has_next(sparse_bitmap_iterator_t > *this) > > +{ > > + return (this->_next != -1); > > +} > > + > > +static unsigned int > __sparse_iterator_next(sparse_bitmap_iterator_t *this) > > +{ > > + int next = this->_next; > > + > > + this->_next = (this->_next + 1) & (this->_nbits - 1); > > + if (this->_next == this->_start) > > + this->_next = -1; > > + > > + return this->_base.il <http://base.il>[next]; > > +} > > + > > +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this) > > +{ > > + this->start = __sparse_iterator_start; > > + this->has_next = __sparse_iterator_has_next; > > + this->next = __sparse_iterator_next; > > + > > + this->_start = -1; > > + this->_next = this->_start; > > +} > > + > > +/* > > + * Generic byte-width atomic set/clear > > + */ > > +static inline void atomic_byte_set( > > + unsigned char *addr, unsigned int bit) > > +{ > > + unsigned char load, store; > > + unsigned char set = 1 << (bit & (BITS_PER_BYTE - 1)); > > + > > + do { > > + load = *addr; > > + store = load | set; > > + } while (!__atomic_compare_exchange_n(addr, &load, store, > > + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); > > +} > > + > > +static inline void atomic_byte_clear( > > + unsigned char *addr, unsigned int bit) > > +{ > > + unsigned char load, store; > > + unsigned char clear = 1 << (bit & (BITS_PER_BYTE - 1)); > > + > > + do { > > + load = *addr; > > + store = load & ~clear; > > + } while (!__atomic_compare_exchange_n(addr, &load, store, > > + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); > > +} > > + > > +static inline unsigned char *__bit_byte( > > + unsigned long *word, unsigned int bit) > > +{ > > + unsigned int i; > > + unsigned char *b; > > + > > + b = (unsigned char *)word; > > + > > + i = bit & (BITS_PER_LONG - 1); > > + i = i / BITS_PER_BYTE; > > + > > +#if (ODP_BYTE_ORDER == ODP_BIG_ENDIAN) > > + i = BYTES_PER_LONG - 1 - i; > > +#endif > > + return &b[i]; > > +} > > + > > +void raw_bitmap_set(unsigned long *map, unsigned int bit) > > +{ > > + unsigned long *p = map + BIT_WORD(bit); > > + > > + atomic_byte_set(__bit_byte(p, bit), bit); > > +} > > + > > +void raw_bitmap_clear(unsigned long *map, unsigned int bit) > > +{ > > + unsigned long *p = map + BIT_WORD(bit); > > + > > + atomic_byte_clear(__bit_byte(p, bit), bit); > > +} > > -- > > 2.7.4 > > > >
diff --git a/platform/linux-generic/Makefile.am b/platform/linux-generic/Makefile.am index 999a7f5..5b38c7b 100644 --- a/platform/linux-generic/Makefile.am +++ b/platform/linux-generic/Makefile.am @@ -130,6 +130,7 @@ noinst_HEADERS = \ ${srcdir}/include/odp_align_internal.h \ ${srcdir}/include/odp_atomic_internal.h \ ${srcdir}/include/odp_buffer_inlines.h \ + ${srcdir}/include/odp_bitmap_internal.h \ ${srcdir}/include/odp_buffer_internal.h \ ${srcdir}/include/odp_classification_datamodel.h \ ${srcdir}/include/odp_classification_inlines.h \ @@ -173,6 +174,7 @@ __LIB__libodp_linux_la_SOURCES = \ _ishmphy.c \ odp_atomic.c \ odp_barrier.c \ + odp_bitmap.c \ odp_buffer.c \ odp_byteorder.c \ odp_classification.c \ diff --git a/platform/linux-generic/include/odp_bitmap_internal.h b/platform/linux-generic/include/odp_bitmap_internal.h new file mode 100644 index 0000000..1be4d02 --- /dev/null +++ b/platform/linux-generic/include/odp_bitmap_internal.h @@ -0,0 +1,317 @@ +/* Copyright (c) 2016, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +/** + * @file + * + * ODP generic bitmap types and operations. + */ + +#ifndef ODP_BITMAP_INTERNAL_H_ +#define ODP_BITMAP_INTERNAL_H_ + +#ifdef __cplusplus +extern "C" { +#endif + +#include <stdint.h> +#include <stdbool.h> +#include <string.h> +#include <odp/api/hints.h> + +/* Generate unique identifier for instantiated class */ +#define TOKENIZE(template, line) \ + template ## _ ## line ## _ ## __COUNTER__ + +/* Array size in general */ +#define ARRAY_SIZE(array) (sizeof(array) / sizeof(array[0])) + +#define BITS_PER_BYTE (8) +#define BITS_PER_LONG __WORDSIZE +#define BYTES_PER_LONG (BITS_PER_LONG / BITS_PER_BYTE) + +#define BIT_WORD(nr) ((nr) / BITS_PER_LONG) +#define BITS_TO_LONGS(nr) BIT_WORD(nr + BITS_PER_LONG - 1) + +#define BITMAP_FIRST_WORD_MASK(start) \ + (~0UL << ((start) & (BITS_PER_LONG - 1))) +#define BITMAP_LAST_WORD_MASK(nbits) \ + (~0UL >> (-(nbits) & (BITS_PER_LONG - 1))) + +/* WAPL bitmap base class */ +typedef struct { + unsigned int nwords; + unsigned int *pl; + unsigned long *ul; +} wapl_bitmap_t; + +/* + * Word-Aligned Position List (WAPL) bitmap, which actually + * is not a compression, but with an extra list of non-empty + * word positions. + * + * WAPL accelerates bitwise operations and iterations by + * applying only to non-empty positions instead of walking + * through the whole bitmap. + * + * WAPL uses [1 ~ N] instead of [0 ~ N - 1] as position + * values and an extra 0 as end indicator for position list. + * This is the reason to allocate one extra room below. + */ +#define instantiate_wapl_bitmap(line, nbits) \ + struct TOKENIZE(wapl_bitmap, line) { \ + unsigned int pl[BITS_TO_LONGS(nbits) + 1]; \ + unsigned long ul[BITS_TO_LONGS(nbits) + 1]; \ + } + +#define WAPL_BITMAP(nbits) instantiate_wapl_bitmap(__LINE__, nbits) + +/* + * Upcast any derived WAPL bitmap class to its base class + */ +#define __wapl_upcast(base, derived) \ + do { \ + __typeof__(derived) p = derived; \ + base.pl = p->pl; \ + base.ul = p->ul; \ + base.nwords = ARRAY_SIZE(p->ul) - 1; \ + } while (0) + +/* + * WAPL base class bitmap operations + */ +void __wapl_bitmap_and(wapl_bitmap_t *dst, + wapl_bitmap_t *src, wapl_bitmap_t *and); + +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or); + +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit); + +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit); + +/* + * Generic WAPL bitmap operations + */ +#define wapl_bitmap_zero(map) \ + ({ \ + __typeof__(map) p = map; \ + memset((void *)p, 0, sizeof(__typeof__(*p))); \ + }) + +#define wapl_bitmap_copy(dst, src) \ + ({ \ + __typeof__(dst) d = dst; \ + __typeof__(src) s = src; \ + if (d != s) \ + memcpy((void *)d, (void *)s, \ + sizeof(__typeof__(*d))); \ + }) + +#define wapl_bitmap_and(dst, src, and) \ + ({ \ + wapl_bitmap_t d, s, a; \ + __wapl_upcast(d, dst); \ + __wapl_upcast(s, src); \ + __wapl_upcast(a, and); \ + __wapl_bitmap_and(&d, &s, &a); \ + }) + +#define wapl_bitmap_or(dst, src, or) \ + ({ \ + wapl_bitmap_t d, o; \ + wapl_bitmap_copy(dst, src); \ + __wapl_upcast(d, dst); \ + __wapl_upcast(o, or); \ + __wapl_bitmap_or(&d, &o); \ + }) + +#define wapl_bitmap_set(map, bit) \ + ({ \ + wapl_bitmap_t b; \ + __wapl_upcast(b, map); \ + __wapl_bitmap_set(&b, bit); \ + }) + +#define wapl_bitmap_clear(map, bit) \ + ({ \ + wapl_bitmap_t b; \ + __wapl_upcast(b, map); \ + __wapl_bitmap_clear(&b, bit); \ + }) + +/* + * Round robin iterator runs upon a WAPL bitmap: + * + * wapl_bitmap_iterator(iterator, WAPL bitmap); + * for (iterator->start(); iterator->has_next(); ) { + * unsigned int bit_index = iterator->next(); + * ...operations on this bit index... + * } + */ +typedef struct wapl_bitmap_iterator { + int _start, _next, _nbits; + wapl_bitmap_t _base; + + void (*start)(struct wapl_bitmap_iterator *this); + bool (*has_next)(struct wapl_bitmap_iterator *this); + unsigned int (*next)(struct wapl_bitmap_iterator *this); +} wapl_bitmap_iterator_t; + +/* + * WAPL bitmap iterator constructor + */ +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this); + +/* + * Generic constructor accepts any derived WAPL bitmap class + */ +#define wapl_bitmap_iterator(iterator, map) \ + ({ \ + __typeof__(iterator) __it = iterator; \ + __wapl_upcast(__it->_base, map); \ + __wapl_bitmap_iterator(__it); \ + }) + +/* Sparse bitmap base class */ +typedef struct { + unsigned int nbits; + unsigned int *last, *pl, *il; +} sparse_bitmap_t; + +/* + * Sparse bitmap, lists all bit indexes directly as an array. + * Expected to be significantly straightforward iteration. + */ +#define instantiate_sparse_bitmap(line, nbits) \ + struct TOKENIZE(sparse_bitmap, line) { \ + unsigned int last; \ + unsigned int pl[nbits]; \ + unsigned int il[nbits]; \ + } + +#define SPARSE_BITMAP(nbits) instantiate_sparse_bitmap(__LINE__, nbits) + +/* + * Upcast any derived sparse bitmap class to its base class + */ +#define __sparse_upcast(base, derived) \ + do { \ + __typeof__(derived) p = derived; \ + base.pl = p->pl; \ + base.il = p->il; \ + base.last = &p->last; \ + base.nbits = ARRAY_SIZE(p->il); \ + } while (0) + +/* + * Sparse base class bitmap operations + */ +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit); + +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit); + +/* + * Generic sparse bitmap operations + */ +#define sparse_bitmap_zero(map) \ + ({ \ + __typeof__(map) p = map; \ + memset((void *)p, 0, sizeof(__typeof__(*p))); \ + }) + +#define sparse_bitmap_set(map, bit) \ + ({ \ + sparse_bitmap_t b; \ + __sparse_upcast(b, map); \ + __sparse_bitmap_set(&b, bit); \ + }) + +#define sparse_bitmap_clear(map, bit) \ + ({ \ + sparse_bitmap_t b; \ + __sparse_upcast(b, map); \ + __sparse_bitmap_clear(&b, bit); \ + }) + +/* + * Round robin iterator runs upon a sparse bitmap: + * + * sparse_bitmap_iterator(iterator, SPARSE bitmap); + * for (iterator->start(); iterator->has_next(); ) { + * unsigned int bit_index = iterator->next(); + * ...operations on this bit index... + * } + */ +typedef struct sparse_bitmap_iterator { + int _start, _next, _nbits; + sparse_bitmap_t _base; + + void (*start)(struct sparse_bitmap_iterator *this); + bool (*has_next)(struct sparse_bitmap_iterator *this); + unsigned int (*next)(struct sparse_bitmap_iterator *this); +} sparse_bitmap_iterator_t; + +/* + * Sparse bitmap iterator constructor + */ +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this); + +/* + * Generic constructor accepts any derived sparse bitmap class. + */ +#define sparse_bitmap_iterator(iterator, map) \ + ({ \ + __typeof__(iterator) __it = iterator; \ + __sparse_upcast(__it->_base, map); \ + __sparse_bitmap_iterator(__it); \ + }) + +/* + * Raw bitmap atomic set and clear. + */ +void raw_bitmap_set(unsigned long *map, unsigned int bit); + +void raw_bitmap_clear(unsigned long *map, unsigned int bit); + +/* + * It will enter infinite loop incase that all bits are zero, + * so please make sure the bitmap at least has one set. + */ +static inline int __bitmap_wraparound_next( + unsigned long *addr, unsigned int nbits, int start) +{ + unsigned long tmp; + + if (start >= (int)nbits) + start = 0; + + tmp = addr[BIT_WORD(start)]; + + /* Handle 1st word. */ + tmp &= BITMAP_FIRST_WORD_MASK(start); + start = start & ~(BITS_PER_LONG - 1); + + while (!tmp) { + start += BITS_PER_LONG; + if (start >= (int)nbits) + start = 0; + + tmp = addr[BIT_WORD(start)]; + } + + start += __builtin_ffsl(tmp) - 1; + return start; +} + +/** + * @} + */ + +#ifdef __cplusplus +} +#endif + +#endif diff --git a/platform/linux-generic/odp_bitmap.c b/platform/linux-generic/odp_bitmap.c new file mode 100644 index 0000000..a29b9ef --- /dev/null +++ b/platform/linux-generic/odp_bitmap.c @@ -0,0 +1,315 @@ +/* Copyright (c) 2016, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#include <string.h> +#include <unistd.h> +#include <odp/api/std_types.h> +#include <odp/api/byteorder.h> +#include <odp_bitmap_internal.h> + +/* + * WAPL base class bitmap operations + */ +static inline void __wapl_add_pos( + wapl_bitmap_t *map, unsigned int p) +{ + unsigned int s, k = 0; + unsigned int *pl = map->pl; + + while (pl[k] && p > pl[k]) + k++; + + if (p == pl[k]) + return; + + /* sorted insertion */ + for (; pl[k] && p < pl[k]; k++) { + s = pl[k]; + pl[k] = p; + p = s; + } + + if (k < map->nwords) + pl[k++] = p; + + pl[k] = 0; +} + +static inline void __wapl_remove_pos( + wapl_bitmap_t *map, unsigned int p) +{ + unsigned int k = 0; + unsigned int *pl = map->pl; + + while (pl[k] && p != pl[k]) + k++; + + for (; pl[k]; k++) + pl[k] = pl[k + 1]; +} + +void __wapl_bitmap_and(wapl_bitmap_t *dst, + wapl_bitmap_t *src, wapl_bitmap_t *and) +{ + unsigned int k = 0, p; + unsigned int *pl = src->pl; + + while ((p = *pl++) != 0) { + dst->ul[p] = src->ul[p] & and->ul[p]; + if (dst->ul[p]) + dst->pl[k++] = p; + } + + dst->pl[k] = 0; +} + +void __wapl_bitmap_or(wapl_bitmap_t *dst, wapl_bitmap_t *or) +{ + unsigned int p; + unsigned int *pl = or->pl; + + while ((p = *pl++) != 0) { + if (dst->ul[p] == 0) + __wapl_add_pos(dst, p); + + dst->ul[p] |= or->ul[p]; + } +} + +void __wapl_bitmap_set(wapl_bitmap_t *map, unsigned int bit) +{ + unsigned int p = BIT_WORD(bit) + 1; + unsigned long set = 1UL << (bit & (BITS_PER_LONG - 1)); + + if (p > map->nwords) + return; + + if (map->ul[p] == 0) + __wapl_add_pos(map, p); + + map->ul[p] |= set; +} + +void __wapl_bitmap_clear(wapl_bitmap_t *map, unsigned int bit) +{ + unsigned int p = BIT_WORD(bit) + 1; + unsigned long clear = 1UL << (bit & (BITS_PER_LONG - 1)); + + if (p > map->nwords) + return; + + map->ul[p] &= ~clear; + + if (map->ul[p] == 0) + __wapl_remove_pos(map, p); +} + +/* + * WAPL bitmap iterator implementation + */ +static void __wapl_iterator_start(wapl_bitmap_iterator_t *this) +{ + this->_nbits = this->_base.nwords * BITS_PER_LONG; + + /* Advance to next queue index to start this + * new round iteration. + */ + if (this->_base.pl[0] == 0) + this->_start = -1; + else + this->_start = __bitmap_wraparound_next( + &this->_base.ul[1], this->_nbits, this->_start + 1); + + this->_next = this->_start; +} + +static bool __wapl_iterator_has_next(wapl_bitmap_iterator_t *this) +{ + return (this->_next != -1); +} + +static unsigned int __wapl_iterator_next(wapl_bitmap_iterator_t *this) +{ + int next = this->_next; + + this->_next = __bitmap_wraparound_next( + &this->_base.ul[1], this->_nbits, this->_next + 1); + + if (this->_next == this->_start) + this->_next = -1; + + return next; +} + +void __wapl_bitmap_iterator(wapl_bitmap_iterator_t *this) +{ + this->start = __wapl_iterator_start; + this->has_next = __wapl_iterator_has_next; + this->next = __wapl_iterator_next; + + this->_start = -1; + this->_next = this->_start; +} + +/* + * Sparse base class bitmap operations + */ +void __sparse_bitmap_set(sparse_bitmap_t *map, unsigned int bit) +{ + unsigned int last = *map->last; + + /* Index exceeds */ + if (bit >= map->nbits) + return; + + /* Full bitmap */ + if (last >= map->nbits) + return; + + /* Bit was not set previously, + * also record where we set the bit + */ + if (!map->pl[bit]) { + map->il[last++] = bit; + map->pl[bit] = last; + + *map->last = last; + } +} + +void __sparse_bitmap_clear(sparse_bitmap_t *map, unsigned int bit) +{ + unsigned int p, i; + unsigned int last = *map->last; + + /* Index exceeds */ + if (bit >= map->nbits) + return; + + /* Empty bitmap */ + if (last == 0) + return; + + /* Bit was set previously */ + if (map->pl[bit]) { + p = map->pl[bit] - 1; + map->pl[bit] = 0; + + last--; + *map->last = last; + + /* Fill the hole with the latest index */ + if (p < last) { + i = map->il[last]; + map->pl[i] = p + 1; + map->il[p] = i; + } + } +} + +/* + * Sparse bitmap iterator implementation + */ +static void __sparse_iterator_start(sparse_bitmap_iterator_t *this) +{ + this->_nbits = (int)*this->_base.last; + + /* Advance to next queue index to start this + * new round iteration. + */ + if (this->_nbits == 0) + this->_start = -1; + else + this->_start = (this->_start + 1) & (this->_nbits - 1); + + this->_next = this->_start; +} + +static bool __sparse_iterator_has_next(sparse_bitmap_iterator_t *this) +{ + return (this->_next != -1); +} + +static unsigned int __sparse_iterator_next(sparse_bitmap_iterator_t *this) +{ + int next = this->_next; + + this->_next = (this->_next + 1) & (this->_nbits - 1); + if (this->_next == this->_start) + this->_next = -1; + + return this->_base.il[next]; +} + +void __sparse_bitmap_iterator(sparse_bitmap_iterator_t *this) +{ + this->start = __sparse_iterator_start; + this->has_next = __sparse_iterator_has_next; + this->next = __sparse_iterator_next; + + this->_start = -1; + this->_next = this->_start; +} + +/* + * Generic byte-width atomic set/clear + */ +static inline void atomic_byte_set( + unsigned char *addr, unsigned int bit) +{ + unsigned char load, store; + unsigned char set = 1 << (bit & (BITS_PER_BYTE - 1)); + + do { + load = *addr; + store = load | set; + } while (!__atomic_compare_exchange_n(addr, &load, store, + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); +} + +static inline void atomic_byte_clear( + unsigned char *addr, unsigned int bit) +{ + unsigned char load, store; + unsigned char clear = 1 << (bit & (BITS_PER_BYTE - 1)); + + do { + load = *addr; + store = load & ~clear; + } while (!__atomic_compare_exchange_n(addr, &load, store, + 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED)); +} + +static inline unsigned char *__bit_byte( + unsigned long *word, unsigned int bit) +{ + unsigned int i; + unsigned char *b; + + b = (unsigned char *)word; + + i = bit & (BITS_PER_LONG - 1); + i = i / BITS_PER_BYTE; + +#if (ODP_BYTE_ORDER == ODP_BIG_ENDIAN) + i = BYTES_PER_LONG - 1 - i; +#endif + return &b[i]; +} + +void raw_bitmap_set(unsigned long *map, unsigned int bit) +{ + unsigned long *p = map + BIT_WORD(bit); + + atomic_byte_set(__bit_byte(p, bit), bit); +} + +void raw_bitmap_clear(unsigned long *map, unsigned int bit) +{ + unsigned long *p = map + BIT_WORD(bit); + + atomic_byte_clear(__bit_byte(p, bit), bit); +}
Add C++ template alike bitmap<size> to allow instantiate bitmap data structure of any size, and provide iterators to help walking through the bitmap objects. Signed-off-by: Yi He <yi.he@linaro.org> --- platform/linux-generic/Makefile.am | 2 + .../linux-generic/include/odp_bitmap_internal.h | 317 +++++++++++++++++++++ platform/linux-generic/odp_bitmap.c | 315 ++++++++++++++++++++ 3 files changed, 634 insertions(+) create mode 100644 platform/linux-generic/include/odp_bitmap_internal.h create mode 100644 platform/linux-generic/odp_bitmap.c -- 2.7.4