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.fischo...@linaro.org > <mailto:bill.fischo...@linaro.org>> wrote: > > On Wed, Jan 11, 2017 at 1:50 AM, Yi He <yi...@linaro.org > <mailto:yi...@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...@linaro.org <mailto:yi...@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 > > > >
