From patchwork Wed Oct 28 08:43:11 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Akinobu Mita X-Patchwork-Id: 37058 X-Patchwork-Delegate: davem@davemloft.net Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.176.167]) by ozlabs.org (Postfix) with ESMTP id 1EE75B7BFA for ; Wed, 28 Oct 2009 19:45:49 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932710AbZJ1Inc (ORCPT ); Wed, 28 Oct 2009 04:43:32 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S932727AbZJ1Inc (ORCPT ); Wed, 28 Oct 2009 04:43:32 -0400 Received: from mail-gx0-f216.google.com ([209.85.217.216]:39461 "EHLO mail-gx0-f216.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932696AbZJ1In2 (ORCPT ); Wed, 28 Oct 2009 04:43:28 -0400 Received: by gxk8 with SMTP id 8so588481gxk.1 for ; Wed, 28 Oct 2009 01:43:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:from:to:cc:subject:date :message-id:x-mailer; bh=M5OCLUWnIWEM8dx71TF0sFKSXcPlsKPEmGfyIHmawEw=; b=vVwyWV2vwqz5KEp4K6iIU1wOUfQAlwe3y/LGjnjatS63KzFmfWzpqDCMwU3dL8PFz0 2rOYrf6ihkAz5Gl/g9o1GJri7ecSpmpolKTpiu8plb6cfD3rokAYOo1YsxhZNRpW2C7a vgxEmB+MlZtuE788XuDYdDZ3nnrXBXZe3DgJo= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer; b=xyqv1JR5Tf62ShBSLYawVpVDJBByJZwe4HyQZSFMo71HH5HBl33HrrQhTiK3omxY0v JL0H+c01fg7MgdsK0s1juoqHhYG2RCAKkPQxn9CYx7anN1heU2lKCYy8Gnwfd2crtFci A3spgZhwHZdnNvBWpFKO7TxYCzaR5ChOpoAck= Received: by 10.90.149.6 with SMTP id w6mr501410agd.90.1256719412925; Wed, 28 Oct 2009 01:43:32 -0700 (PDT) Received: from localhost ([220.110.185.192]) by mx.google.com with ESMTPS id 35sm355575yxh.33.2009.10.28.01.43.30 (version=TLSv1/SSLv3 cipher=RC4-MD5); Wed, 28 Oct 2009 01:43:31 -0700 (PDT) From: Akinobu Mita To: linux-kernel@vger.kernel.org, akpm@linux-foundation.org Cc: Akinobu Mita , FUJITA Tomonori , "David S. Miller" , sparclinux@vger.kernel.org, Benjamin Herrenschmidt , Paul Mackerras , linuxppc-dev@ozlabs.org, Thomas Gleixner , Ingo Molnar , "H. Peter Anvin" , x86@kernel.org, Greg Kroah-Hartman , Lothar Wassmann , linux-usb@vger.kernel.org, Roland Dreier , Yevgeny Petrilin , netdev@vger.kernel.org, Tony Luck , Fenghua Yu , linux-ia64@vger.kernel.org, linux-altix@sgi.com, Joerg Roedel Subject: [PATCH 1/7] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area Date: Wed, 28 Oct 2009 17:43:11 +0900 Message-Id: <1256719397-4258-1-git-send-email-akinobu.mita@gmail.com> X-Mailer: git-send-email 1.6.5.1 Sender: sparclinux-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: sparclinux@vger.kernel.org This introduces new bitmap functions: bitmap_set: Set specified bit area bitmap_clear: Clear specified bit area bitmap_find_next_zero_area: Find free bit area These are mostly stolen from iommu helper. The differences are: - Use find_next_bit instead of doing test_bit for each bit - Rewrite bitmap_set and bitmap_clear Instead of setting or clearing for each bit. - Check the last bit of the limit iommu-helper doesn't want to find such area - The return value if there is no zero area find_next_zero_area in iommu helper: returns -1 bitmap_find_next_zero_area: return >= bitmap size Signed-off-by: Akinobu Mita Cc: FUJITA Tomonori Cc: "David S. Miller" Cc: sparclinux@vger.kernel.org Cc: Benjamin Herrenschmidt Cc: Paul Mackerras Cc: linuxppc-dev@ozlabs.org Cc: Thomas Gleixner Cc: Ingo Molnar Cc: "H. Peter Anvin" Cc: x86@kernel.org Cc: Greg Kroah-Hartman Cc: Lothar Wassmann Cc: linux-usb@vger.kernel.org Cc: Roland Dreier Cc: Yevgeny Petrilin Cc: netdev@vger.kernel.org Cc: Tony Luck Cc: Fenghua Yu Cc: linux-ia64@vger.kernel.org Cc: linux-altix@sgi.com Cc: Joerg Roedel --- include/linux/bitmap.h | 11 ++++++ lib/bitmap.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 92 insertions(+), 0 deletions(-) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 756d78b..daf8c48 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -42,6 +42,9 @@ * bitmap_empty(src, nbits) Are all bits zero in *src? * bitmap_full(src, nbits) Are all bits set in *src? * bitmap_weight(src, nbits) Hamming Weight: number set bits + * bitmap_set(dst, pos, nbits) Set specified bit area + * bitmap_clear(dst, pos, nbits) Clear specified bit area + * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area * bitmap_shift_right(dst, src, n, nbits) *dst = *src >> n * bitmap_shift_left(dst, src, n, nbits) *dst = *src << n * bitmap_remap(dst, src, old, new, nbits) *dst = map(old, new)(src) @@ -108,6 +111,14 @@ extern int __bitmap_subset(const unsigned long *bitmap1, const unsigned long *bitmap2, int bits); extern int __bitmap_weight(const unsigned long *bitmap, int bits); +extern void bitmap_set(unsigned long *map, int i, int len); +extern void bitmap_clear(unsigned long *map, int start, int nr); +extern unsigned long bitmap_find_next_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned int nr, + unsigned long align_mask); + extern int bitmap_scnprintf(char *buf, unsigned int len, const unsigned long *src, int nbits); extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user, diff --git a/lib/bitmap.c b/lib/bitmap.c index 7025658..11bf497 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -271,6 +271,87 @@ int __bitmap_weight(const unsigned long *bitmap, int bits) } EXPORT_SYMBOL(__bitmap_weight); +#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG)) + +void bitmap_set(unsigned long *map, int start, int nr) +{ + unsigned long *p = map + BIT_WORD(start); + const int size = start + nr; + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); + + while (nr - bits_to_set >= 0) { + *p |= mask_to_set; + nr -= bits_to_set; + bits_to_set = BITS_PER_LONG; + mask_to_set = ~0UL; + p++; + } + if (nr) { + mask_to_set &= BITMAP_LAST_WORD_MASK(size); + *p |= mask_to_set; + } +} +EXPORT_SYMBOL(bitmap_set); + +void bitmap_clear(unsigned long *map, int start, int nr) +{ + unsigned long *p = map + BIT_WORD(start); + const int size = start + nr; + int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start); + + while (nr - bits_to_clear >= 0) { + *p &= ~mask_to_clear; + nr -= bits_to_clear; + bits_to_clear = BITS_PER_LONG; + mask_to_clear = ~0UL; + p++; + } + if (nr) { + mask_to_clear &= BITMAP_LAST_WORD_MASK(size); + *p &= ~mask_to_clear; + } +} +EXPORT_SYMBOL(bitmap_clear); + +/* + * bitmap_find_next_zero_area - find a contiguous aligned zero area + * @map: The address to base the search on + * @size: The bitmap size in bits + * @start: The bitnumber to start searching at + * @nr: The number of zeroed bits we're looking for + * @align_mask: Alignment mask for zero area + * + * The @align_mask should be one less than a power of 2; the effect is that + * the bit offset of all zero areas this function finds is multiples of that + * power of 2. A @align_mask of 0 means no alignment is required. + */ +unsigned long bitmap_find_next_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned int nr, + unsigned long align_mask) +{ + unsigned long index, end, i; +again: + index = find_next_zero_bit(map, size, start); + + /* Align allocation */ + index = __ALIGN_MASK(index, align_mask); + + end = index + nr; + if (end > size) + return end; + i = find_next_bit(map, end, index); + if (i < end) { + start = i + 1; + goto again; + } + return index; +} +EXPORT_SYMBOL(bitmap_find_next_zero_area); + /* * Bitmap printing & parsing functions: first version by Bill Irwin, * second version by Paul Jackson, third by Joe Korty.