From patchwork Wed Oct 20 01:36:53 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Huang, Ying" X-Patchwork-Id: 267121 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter1.kernel.org (8.14.4/8.14.3) with ESMTP id o9K1dYke011613 for ; Wed, 20 Oct 2010 01:39:34 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1756328Ab0JTBjB (ORCPT ); Tue, 19 Oct 2010 21:39:01 -0400 Received: from mga09.intel.com ([134.134.136.24]:19948 "EHLO mga09.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1756550Ab0JTBhJ (ORCPT ); Tue, 19 Oct 2010 21:37:09 -0400 Received: from orsmga002.jf.intel.com ([10.7.209.21]) by orsmga102.jf.intel.com with ESMTP; 19 Oct 2010 18:37:09 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="4.57,353,1283756400"; d="scan'208";a="565620627" Received: from yhuang-dev.sh.intel.com ([10.239.13.2]) by orsmga002.jf.intel.com with ESMTP; 19 Oct 2010 18:37:07 -0700 From: Huang Ying To: Len Brown Cc: linux-kernel@vger.kernel.org, Andi Kleen , ying.huang@intel.com, linux-acpi@vger.kernel.org Subject: [PATCH 2/9] Add lock-less version of bitmap_set/clear Date: Wed, 20 Oct 2010 09:36:53 +0800 Message-Id: <1287538620-7442-3-git-send-email-ying.huang@intel.com> X-Mailer: git-send-email 1.7.1 In-Reply-To: <1287538620-7442-1-git-send-email-ying.huang@intel.com> References: <1287538620-7442-1-git-send-email-ying.huang@intel.com> Sender: linux-acpi-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-acpi@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.3 (demeter1.kernel.org [140.211.167.41]); Wed, 20 Oct 2010 01:39:35 +0000 (UTC) --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -44,6 +44,8 @@ * 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_set_ll(dst, pos, nbits) Set specified bit area, lock-less version + * bitmap_clear_ll(dst, pos, nbits) Clear specified bit area, lock-less version * 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 @@ -113,6 +115,8 @@ extern int __bitmap_weight(const unsigne extern void bitmap_set(unsigned long *map, int i, int len); extern void bitmap_clear(unsigned long *map, int start, int nr); +extern int bitmap_set_ll(unsigned long *map, int i, int len); +extern int bitmap_clear_ll(unsigned long *map, int start, int nr); extern unsigned long bitmap_find_next_zero_area(unsigned long *map, unsigned long size, unsigned long start, --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -315,6 +315,107 @@ void bitmap_clear(unsigned long *map, in } EXPORT_SYMBOL(bitmap_clear); +static inline int set_bits_ll(unsigned long *addr, unsigned long mask_to_set) +{ + unsigned long val, nval; + + nval = *addr; + do { + val = nval; + if (val & mask_to_set) + return -EBUSY; + } while ((nval = cmpxchg(addr, val, val | mask_to_set)) != val); + + return 0; +} + +static inline int clear_bits_ll(unsigned long *addr, + unsigned long mask_to_clear) +{ + unsigned long val, nval; + + nval = *addr; + do { + val = nval; + if ((val & mask_to_clear) != mask_to_clear) + return -EBUSY; + } while ((nval = cmpxchg(addr, val, val & ~mask_to_clear)) != val); + + return 0; +} + +/** + * bitmap_set_ll - set the specified number of bits at the specified position + * @map: pointer to a bitmap + * @start: a bit position in @map + * @nr: number of bits to set + * + * Set @nr bits start from @start in @map lock-lessly. Several users + * can set/clear the same bitmap simultaneously without lock. If two + * users set the same bit, one user will return remain bits, otherwise + * return 0. + */ +int bitmap_set_ll(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) { + if (set_bits_ll(p, mask_to_set)) + return nr; + 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); + if (set_bits_ll(p, mask_to_set)) + return nr; + } + + return 0; +} +EXPORT_SYMBOL(bitmap_set_ll); + +/** + * bitmap_clear_ll - clear the specified number of bits at the specified position + * @map: pointer to a bitmap + * @start: a bit position in @map + * @nr: number of bits to set + * + * Clear @nr bits start from @start in @map lock-lessly. Several users + * can set/clear the same bitmap simultaneously without lock. If two + * users clear the same bit, one user will return remain bits, + * otherwise return 0. + */ +int bitmap_clear_ll(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) { + if (clear_bits_ll(p, mask_to_clear)) + return nr; + 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); + if (clear_bits_ll(p, mask_to_clear)) + return nr; + } + + return 0; +} +EXPORT_SYMBOL(bitmap_clear_ll); + /* * bitmap_find_next_zero_area - find a contiguous aligned zero area * @map: The address to base the search on