From patchwork Tue Nov 22 02:13:03 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Benjamin Herrenschmidt X-Patchwork-Id: 697493 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.ozlabs.org (lists.ozlabs.org [103.22.144.68]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3tN8Hs3nDXz9svs for ; Tue, 22 Nov 2016 13:17:29 +1100 (AEDT) Received: from lists.ozlabs.org (lists.ozlabs.org [IPv6:2401:3900:2:1::3]) by lists.ozlabs.org (Postfix) with ESMTP id 3tN8Hs2zFfzDwFj for ; Tue, 22 Nov 2016 13:17:29 +1100 (AEDT) X-Original-To: skiboot@lists.ozlabs.org Delivered-To: skiboot@lists.ozlabs.org Received: from gate.crashing.org (gate.crashing.org [63.228.1.57]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by lists.ozlabs.org (Postfix) with ESMTPS id 3tN8HZ42wxzDwFN for ; Tue, 22 Nov 2016 13:17:14 +1100 (AEDT) Received: from pasglop.ozlabs.ibm.com (localhost.localdomain [127.0.0.1]) by gate.crashing.org (8.14.1/8.13.8) with ESMTP id uAM2DZdB015261; Mon, 21 Nov 2016 20:13:36 -0600 From: Benjamin Herrenschmidt To: skiboot@lists.ozlabs.org Date: Tue, 22 Nov 2016 13:13:03 +1100 Message-Id: <1479780814-6162-1-git-send-email-benh@kernel.crashing.org> X-Mailer: git-send-email 2.7.4 Subject: [Skiboot] [PATCH 01/32] bitmap: Add basic bitmap ops X-BeenThere: skiboot@lists.ozlabs.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Mailing list for skiboot development List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: skiboot-bounces+incoming=patchwork.ozlabs.org@lists.ozlabs.org Sender: "Skiboot" Signed-off-by: Benjamin Herrenschmidt --- core/Makefile.inc | 2 +- core/bitmap.c | 41 +++++++++++++++++++++++++++++++++ include/bitmap.h | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 111 insertions(+), 1 deletion(-) create mode 100644 core/bitmap.c create mode 100644 include/bitmap.h diff --git a/core/Makefile.inc b/core/Makefile.inc index 9223af1..98bcb11 100644 --- a/core/Makefile.inc +++ b/core/Makefile.inc @@ -8,7 +8,7 @@ CORE_OBJS += pci-opal.o fast-reboot.o device.o exceptions.o trace.o affinity.o CORE_OBJS += vpd.o hostservices.o platform.o nvram.o nvram-format.o hmi.o CORE_OBJS += console-log.o ipmi.o time-utils.o pel.o pool.o errorlog.o CORE_OBJS += timer.o i2c.o rtc.o flash.o sensor.o ipmi-opal.o -CORE_OBJS += flash-subpartition.o +CORE_OBJS += flash-subpartition.o bitmap.o ifeq ($(SKIBOOT_GCOV),1) CORE_OBJS += gcov-profiling.o diff --git a/core/bitmap.c b/core/bitmap.c new file mode 100644 index 0000000..f07b6ab --- /dev/null +++ b/core/bitmap.c @@ -0,0 +1,41 @@ +#include "bitmap.h" + +static int __bitmap_find_bit(bitmap_t map, unsigned int start, unsigned int count, + bool value) +{ + unsigned int el, first_bit; + unsigned int end = start + count; + bitmap_elem_t e, ev; + int b; + + ev = value ? -1ul : 0; + el = BITMAP_ELEM(start); + first_bit = BITMAP_BIT(start); + + while (start < end) { + e = map[el] ^ ev; + e |= ((1ul << first_bit) - 1); + if (~e) + break; + start = (start + BITMAP_ELSZ) & ~(BITMAP_ELSZ - 1); + first_bit = 0; + el++; + } + for (b = first_bit; b < BITMAP_ELSZ && start < end; b++,start++) { + if ((e & (1ull << b)) == 0) + return start; + } + + return -1; +} + +int bitmap_find_zero_bit(bitmap_t map, unsigned int start, unsigned int count) +{ + return __bitmap_find_bit(map, start, count, false); +} + +int bitmap_find_one_bit(bitmap_t map, unsigned int start, unsigned int count) +{ + return __bitmap_find_bit(map, start, count, true); +} + diff --git a/include/bitmap.h b/include/bitmap.h new file mode 100644 index 0000000..12913ea --- /dev/null +++ b/include/bitmap.h @@ -0,0 +1,69 @@ +/* Copyright 2016 IBM Corp. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + * implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef __BITMAP_H +#define __BITMAP_H + +#include +#include + +typedef unsigned long bitmap_elem_t; +typedef bitmap_elem_t bitmap_t[]; + +#define BITMAP_ELSZ (sizeof(bitmap_elem_t) << 3) + +/* Number of elements for _n bits (rounded up) */ +#define BITMAP_ELEMS(_n) (((_n) + (BITMAP_ELSZ - 1)) / BITMAP_ELSZ) +/* Number of bytes for _n bits (rounded up) */ +#define BITMAP_BYTES(_n) (BITMAP_ELEMS(_n) * sizeof(bitmap_elem_t)) +/* Bit number within an elemnt for bit _n */ +#define BITMAP_BIT(_n) ((_n) & (BITMAP_ELSZ - 1)) +/* Corresponding mask */ +#define BITMAP_MASK(_n) (1ul << BITMAP_BIT(_n)) +/* Element number for bit _n */ +#define BITMAP_ELEM(_n) ((_n) / BITMAP_ELSZ) + +static inline void bitmap_set_bit(bitmap_t map, unsigned int bit) +{ + map[BITMAP_ELEM(bit)] |= BITMAP_MASK(bit); +} + +static inline void bitmap_clr_bit(bitmap_t map, unsigned int bit) +{ + map[BITMAP_ELEM(bit)] &= ~BITMAP_MASK(bit); +} + +static inline bool bitmap_tst_bit(bitmap_t map, unsigned int bit) +{ + return map[BITMAP_ELEM(bit)] & BITMAP_MASK(bit); +} + +extern int bitmap_find_zero_bit(bitmap_t map, unsigned int start, + unsigned int count); +extern int bitmap_find_one_bit(bitmap_t map, unsigned int start, + unsigned int count); + +#define bitmap_for_each_zero(map, size, bit) \ + for (bit = bitmap_find_zero_bit(map, 0, size); \ + bit >= 0; \ + bit = bitmap_find_zero_bit(map, bit + 1, size)) + +#define bitmap_for_each_one(map, size, bit) \ + for (bit = bitmap_find_one_bit(map, 0, size); \ + bit >= 0; \ + bit = bitmap_find_one_bit(map, bit + 1, size)) + +#endif /* __BITMAP_H */