@@ -128,6 +128,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 \
new file mode 100644
@@ -0,0 +1,314 @@
+/* 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>
+#include <odp_ring_internal.h> /* TOKENIZE and ARRAY_SIZE */
+
+#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...
+ * }
+ */
+#define METHOD_DECLARE(_return, _name, _impl, ...) \
+ _return (*_name)(struct _impl ## _bitmap_ ## iterator *this)
+
+typedef struct wapl_bitmap_iterator {
+ int _start, _next, _nbits;
+ wapl_bitmap_t _base;
+
+ METHOD_DECLARE(void, start, wapl);
+ METHOD_DECLARE(bool, has_next, wapl);
+ METHOD_DECLARE(unsigned int, next, wapl);
+} 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;
+
+ METHOD_DECLARE(void, start, sparse);
+ METHOD_DECLARE(bool, has_next, sparse);
+ METHOD_DECLARE(unsigned int, next, sparse);
+} 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
new file mode 100644
@@ -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 | 314 ++++++++++++++++++++ platform/linux-generic/odp_bitmap.c | 315 +++++++++++++++++++++ 3 files changed, 631 insertions(+) create mode 100644 platform/linux-generic/include/odp_bitmap_internal.h create mode 100644 platform/linux-generic/odp_bitmap.c -- 2.7.4