From patchwork Wed Jan 11 07:50:32 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yi He X-Patchwork-Id: 90823 Delivered-To: patch@linaro.org Received: by 10.140.20.99 with SMTP id 90csp1003433qgi; Tue, 10 Jan 2017 23:53:10 -0800 (PST) X-Received: by 10.237.32.68 with SMTP id 62mr6432769qta.231.1484121190554; Tue, 10 Jan 2017 23:53:10 -0800 (PST) Return-Path: Received: from lists.linaro.org (lists.linaro.org. [54.225.227.206]) by mx.google.com with ESMTP id p132si3217340qka.274.2017.01.10.23.53.10; Tue, 10 Jan 2017 23:53:10 -0800 (PST) Received-SPF: pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.225.227.206 as permitted sender) client-ip=54.225.227.206; Authentication-Results: mx.google.com; spf=pass (google.com: domain of lng-odp-bounces@lists.linaro.org designates 54.225.227.206 as permitted sender) smtp.mailfrom=lng-odp-bounces@lists.linaro.org; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id 3A97160A21; Wed, 11 Jan 2017 07:53:10 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on ip-10-142-244-252 X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, URIBL_BLOCKED autolearn=disabled version=3.4.0 Received: from [127.0.0.1] (localhost [127.0.0.1]) by lists.linaro.org (Postfix) with ESMTP id C4EDF60D91; Wed, 11 Jan 2017 07:51:26 +0000 (UTC) X-Original-To: lng-odp@lists.linaro.org Delivered-To: lng-odp@lists.linaro.org Received: by lists.linaro.org (Postfix, from userid 109) id 452E2609A5; Wed, 11 Jan 2017 07:51:01 +0000 (UTC) Received: from mail-pf0-f176.google.com (mail-pf0-f176.google.com [209.85.192.176]) by lists.linaro.org (Postfix) with ESMTPS id 3F47E60508 for ; Wed, 11 Jan 2017 07:50:58 +0000 (UTC) Received: by mail-pf0-f176.google.com with SMTP id f144so50900834pfa.2 for ; Tue, 10 Jan 2017 23:50:58 -0800 (PST) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references; bh=biXr3zMFnUlIatGAfT2nwm/AdgH5YRyZ8Ij+3AOnWNU=; b=pb249shgjtvaAFe/2a0WUNT9EhaKDHqUiDubElej7U5NKVc1tYzMauYHM+opsK0o1i Ze4cjNDDAbr6AUgGwPMH8IiOlWVLxBEUoXP2vR4+24SUVjwxZdYWr+htOfFS8rdpose9 qr0kqpcb9N+rqyF+HyoJ4GzBUEbUc+vuJJp7E2huj/kYaX6qA7z8XC5nUkl7KR41i/R+ ZajEY4rtr0TevB71iVXvjqyuE6sXXt68LE0A5nj414YmlwP+QxxRCK2bGJl4CbTn74gs E3SsaMMTjQ0f3U6R6aS3grO0744NFtoZPwnrH/SeY99jo53uTYg0SPah6oEvjCqTCZLV 0wQg== X-Gm-Message-State: AIkVDXKFgyoK4MWDFaBdwF+K2JfexHllfuoPkyVSWvHOfrXnnXM8Pise1eKdurggqay8G/KZ11g= X-Received: by 10.99.230.83 with SMTP id p19mr8981568pgj.138.1484121057344; Tue, 10 Jan 2017 23:50:57 -0800 (PST) Received: from ubuntu.heyii.co (ubuntu.heyii.co. [45.32.66.203]) by smtp.googlemail.com with ESMTPSA id l12sm3543001pfj.37.2017.01.10.23.50.56 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 10 Jan 2017 23:50:56 -0800 (PST) From: Yi He To: bill.fischofer@linaro.org, maxim.uvarov@linaro.org, lng-odp@lists.linaro.org Date: Wed, 11 Jan 2017 07:50:32 +0000 Message-Id: <1484121033-15354-4-git-send-email-yi.he@linaro.org> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1484121033-15354-1-git-send-email-yi.he@linaro.org> References: <1484121033-15354-1-git-send-email-yi.he@linaro.org> Subject: [lng-odp] [API-NEXT PATCHv3 3/4] linux-gen: add generic bitmaps and iterators X-BeenThere: lng-odp@lists.linaro.org X-Mailman-Version: 2.1.16 Precedence: list List-Id: "The OpenDataPlane \(ODP\) List" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: lng-odp-bounces@lists.linaro.org Sender: "lng-odp" Add C++ template alike bitmap to allow instantiate bitmap data structure of any size, and provide iterators to help walking through the bitmap objects. Signed-off-by: Yi He --- 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 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 +#include +#include +#include + +/* 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 +#include +#include +#include +#include + +/* + * 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); +}