From patchwork Fri Oct 9 08:29:15 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Akinobu Mita X-Patchwork-Id: 35584 Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from bilbo.ozlabs.org (localhost [127.0.0.1]) by ozlabs.org (Postfix) with ESMTP id 60F4EB841F for ; Fri, 9 Oct 2009 19:29:40 +1100 (EST) Received: by ozlabs.org (Postfix) id 7B2CDB7B9F; Fri, 9 Oct 2009 19:29:33 +1100 (EST) Delivered-To: linuxppc-dev@ozlabs.org Received: from mail-yw0-f181.google.com (mail-yw0-f181.google.com [209.85.211.181]) by ozlabs.org (Postfix) with ESMTP id A8817B7BA3 for ; Fri, 9 Oct 2009 19:29:32 +1100 (EST) Received: by ywh11 with SMTP id 11so3411724ywh.9 for ; Fri, 09 Oct 2009 01:29:31 -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:in-reply-to:references; bh=GFXyPczWIJEkNYvrI8ezV/eyM9JtuZOaf1lqrsMgz+o=; b=rAdHbX9rTPM9JDkZN3iCn/fOIJ9Skm/FNGzVgNs6KNIEz3bvuQOZkVT1V4cMJSNIAJ /+WuAQ8Dd2ygrMLGbq+Dw1wlfFGfOPyonxQV9hFaQoGAMHe23BiOzUQ1s49GrZ9MaNAk Cz4C6gltQy7m0s3JV7Kh608hoH5JX/8zT0Ho0= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=from:to:cc:subject:date:message-id:x-mailer:in-reply-to:references; b=dIaXb4T1k1d3LtsLQP+TUzaTa0PWNnMZ1M0DYrhLwVR6kb1SGccqLXbulD9UTtFvD5 br/6yF9YUrQEfNeQoSV8VkhEd9BmCr2HCFYPFSzYkZrkm72jr/tepMcLdVmZbOErq7mG 41DZgUQGf9yCeg61O202/iYLuV4e+FP9r7SfQ= Received: by 10.151.29.8 with SMTP id g8mr4193514ybj.250.1255076971198; Fri, 09 Oct 2009 01:29:31 -0700 (PDT) Received: from localhost ([220.110.185.192]) by mx.google.com with ESMTPS id 13sm401592gxk.13.2009.10.09.01.29.28 (version=TLSv1/SSLv3 cipher=RC4-MD5); Fri, 09 Oct 2009 01:29:29 -0700 (PDT) From: Akinobu Mita To: linux-kernel@vger.kernel.org, akpm@linux-foundation.org Subject: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area Date: Fri, 9 Oct 2009 17:29:15 +0900 Message-Id: <1255076961-21325-2-git-send-email-akinobu.mita@gmail.com> X-Mailer: git-send-email 1.5.4.3 In-Reply-To: <1255076961-21325-1-git-send-email-akinobu.mita@gmail.com> References: <> <1255076961-21325-1-git-send-email-akinobu.mita@gmail.com> Cc: Fenghua Yu , Greg Kroah-Hartman , linux-ia64@vger.kernel.org, Tony Luck , x86@kernel.org, netdev@vger.kernel.org, Akinobu Mita , linux-altix@sgi.com, Yevgeny Petrilin , FUJITA Tomonori , linuxppc-dev@ozlabs.org, Ingo Molnar , Paul Mackerras , "H. Peter Anvin" , sparclinux@vger.kernel.org, Thomas Gleixner , linux-usb@vger.kernel.org, "David S. Miller" , Lothar Wassmann X-BeenThere: linuxppc-dev@lists.ozlabs.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Linux on PowerPC Developers Mail List List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: linuxppc-dev-bounces+patchwork-incoming=ozlabs.org@lists.ozlabs.org Errors-To: linuxppc-dev-bounces+patchwork-incoming=ozlabs.org@lists.ozlabs.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 stolen from iommu helper. I changed the return value of bitmap_find_next_zero_area if there is no zero area. find_next_zero_area in iommu helper: returns -1 bitmap_find_next_zero_area: return >= bitmap size 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 Signed-off-by: Akinobu Mita --- include/linux/bitmap.h | 11 +++++++++++ lib/bitmap.c | 47 +++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 58 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..95070fa 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -271,6 +271,53 @@ int __bitmap_weight(const unsigned long *bitmap, int bits) } EXPORT_SYMBOL(__bitmap_weight); +void bitmap_set(unsigned long *map, int i, int len) +{ + int end = i + len; + + while (i < end) { + __set_bit(i, map); + i++; + } +} +EXPORT_SYMBOL(bitmap_set); + +void bitmap_clear(unsigned long *map, int start, int nr) +{ + int end = start + nr; + + while (start < end) { + __clear_bit(start, map); + start++; + } +} +EXPORT_SYMBOL(bitmap_clear); + +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 = (index + align_mask) & ~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.