From patchwork Mon Oct 25 07:43:23 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Huang, Ying" X-Patchwork-Id: 266462 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 o9P7k1Lj021896 for ; Mon, 25 Oct 2010 07:46:02 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752200Ab0JYHnj (ORCPT ); Mon, 25 Oct 2010 03:43:39 -0400 Received: from mga14.intel.com ([143.182.124.37]:36703 "EHLO mga14.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753588Ab0JYHni (ORCPT ); Mon, 25 Oct 2010 03:43:38 -0400 Received: from azsmga001.ch.intel.com ([10.2.17.19]) by azsmga102.ch.intel.com with ESMTP; 25 Oct 2010 00:43:37 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="4.58,235,1286175600"; d="scan'208";a="340009280" Received: from yhuang-dev.sh.intel.com ([10.239.13.2]) by azsmga001.ch.intel.com with ESMTP; 25 Oct 2010 00:43:36 -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 -v2 2/9] Add lock-less version of bitmap_set/clear Date: Mon, 25 Oct 2010 15:43:23 +0800 Message-Id: <1287992610-14996-3-git-send-email-ying.huang@intel.com> X-Mailer: git-send-email 1.7.1 In-Reply-To: <1287992610-14996-1-git-send-email-ying.huang@intel.com> References: <1287992610-14996-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]); Mon, 25 Oct 2010 07:46:02 +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