From patchwork Mon Apr 27 16:28:31 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Paolo Bonzini X-Patchwork-Id: 465135 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id F3118140082 for ; Tue, 28 Apr 2015 02:44:28 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=fail reason="verification failed; unprotected key" header.d=gmail.com header.i=@gmail.com header.b=EKaiO1j3; dkim-adsp=none (unprotected policy); dkim-atps=neutral Received: from localhost ([::1]:56413 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ymm8x-0002Ij-4v for incoming@patchwork.ozlabs.org; Mon, 27 Apr 2015 12:44:27 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:34908) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ymlvr-0002Sd-ME for qemu-devel@nongnu.org; Mon, 27 Apr 2015 12:30:56 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ymlvp-0003Ko-9S for qemu-devel@nongnu.org; Mon, 27 Apr 2015 12:30:55 -0400 Received: from mail-wi0-x22b.google.com ([2a00:1450:400c:c05::22b]:35180) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ymlvo-0003KN-WE for qemu-devel@nongnu.org; Mon, 27 Apr 2015 12:30:53 -0400 Received: by widdi4 with SMTP id di4so106413413wid.0 for ; Mon, 27 Apr 2015 09:30:52 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references; bh=Ah6M7MQDsTDWUeAy78UTeoC9ZTT0mHxRRP6m7HGmIFo=; b=EKaiO1j3GL4caiEdJuYBb+InNskzz6FGA9/NnDdg2aphSmLPvyy1OzSCEUywqEYztc aPMmY/hpfUkebEigxHRj2r/lNB0cAs0Re/9KF1OF4EIIIdvE4AVKhSM70tTxR4VdUbhC ogogFPYz4h3mptFNYPxGxD3ZD6eedWwPnpMxsCBut/ceBxQJPCME1u/ZNVeJ/nHHkchS I4prNXMeD7lfXrSQexAcVLglUfP4rRlMO2WjjFBdctgEnZWF9Z7aQb78EggXmEqYyG5L 3niMDeZs/xDeLY6HtuSQCxhUsnuOuPR2j8KrzaA4vnFveOaEBuxVJnFNUq4FswI7mer2 02iw== X-Received: by 10.180.9.5 with SMTP id v5mr21803690wia.93.1430152252405; Mon, 27 Apr 2015 09:30:52 -0700 (PDT) Received: from 640k.localdomain (net-37-116-199-255.cust.vodafonedsl.it. [37.116.199.255]) by mx.google.com with ESMTPSA id dz4sm12300651wib.17.2015.04.27.09.30.50 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 27 Apr 2015 09:30:51 -0700 (PDT) From: Paolo Bonzini To: qemu-devel@nongnu.org Date: Mon, 27 Apr 2015 18:28:31 +0200 Message-Id: <1430152117-100558-24-git-send-email-pbonzini@redhat.com> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1430152117-100558-1-git-send-email-pbonzini@redhat.com> References: <1430152117-100558-1-git-send-email-pbonzini@redhat.com> X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:400c:c05::22b Cc: famz@redhat.com, stefanha@redhat.com, mst@redhat.com Subject: [Qemu-devel] [PATCH 23/29] bitmap: add atomic set functions X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org From: Stefan Hajnoczi Use atomic_or() for atomic bitmaps where several threads may set bits at the same time. This avoids the race condition between threads loading an element, bitwise ORing, and then storing the element. When setting all bits in a word we can avoid atomic ops and instead just use an smp_mb() at the end. Most bitmap users don't need atomicity so introduce new functions. Signed-off-by: Stefan Hajnoczi Message-Id: <1417519399-3166-2-git-send-email-stefanha@redhat.com> [Avoid barrier in the single word case, use full barrier instead of write. - Paolo] Signed-off-by: Paolo Bonzini Reviewed-by: Fam Zheng --- include/qemu/bitmap.h | 2 ++ include/qemu/bitops.h | 14 ++++++++++++++ util/bitmap.c | 37 +++++++++++++++++++++++++++++++++++++ 3 files changed, 53 insertions(+) diff --git a/include/qemu/bitmap.h b/include/qemu/bitmap.h index f0273c9..3e0a4f3 100644 --- a/include/qemu/bitmap.h +++ b/include/qemu/bitmap.h @@ -39,6 +39,7 @@ * bitmap_empty(src, nbits) Are all bits zero in *src? * bitmap_full(src, nbits) Are all bits set in *src? * bitmap_set(dst, pos, nbits) Set specified bit area + * bitmap_set_atomic(dst, pos, nbits) Set specified bit area with atomic ops * bitmap_clear(dst, pos, nbits) Clear specified bit area * bitmap_find_next_zero_area(buf, len, pos, n, mask) Find bit free area */ @@ -226,6 +227,7 @@ static inline int bitmap_intersects(const unsigned long *src1, } void bitmap_set(unsigned long *map, long i, long len); +void bitmap_set_atomic(unsigned long *map, long i, long len); void bitmap_clear(unsigned long *map, long start, long nr); unsigned long bitmap_find_next_zero_area(unsigned long *map, unsigned long size, diff --git a/include/qemu/bitops.h b/include/qemu/bitops.h index 90ca8df..95f98fb 100644 --- a/include/qemu/bitops.h +++ b/include/qemu/bitops.h @@ -16,6 +16,7 @@ #include #include "host-utils.h" +#include "atomic.h" #define BITS_PER_BYTE CHAR_BIT #define BITS_PER_LONG (sizeof (unsigned long) * BITS_PER_BYTE) @@ -39,6 +40,19 @@ static inline void set_bit(long nr, unsigned long *addr) } /** + * set_bit_atomic - Set a bit in memory atomically + * @nr: the bit to set + * @addr: the address to start counting from + */ +static inline void set_bit_atomic(long nr, unsigned long *addr) +{ + unsigned long mask = BIT_MASK(nr); + unsigned long *p = addr + BIT_WORD(nr); + + atomic_or(p, mask); +} + +/** * clear_bit - Clears a bit in memory * @nr: Bit to clear * @addr: Address to start counting from diff --git a/util/bitmap.c b/util/bitmap.c index 9c6bb52..6838d49 100644 --- a/util/bitmap.c +++ b/util/bitmap.c @@ -11,6 +11,7 @@ #include "qemu/bitops.h" #include "qemu/bitmap.h" +#include "qemu/atomic.h" /* * bitmaps provide an array of bits, implemented using an an @@ -177,6 +178,42 @@ void bitmap_set(unsigned long *map, long start, long nr) } } +void bitmap_set_atomic(unsigned long *map, long start, long nr) +{ + unsigned long *p = map + BIT_WORD(start); + const long size = start + nr; + int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG); + unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start); + + /* First word */ + if (nr - bits_to_set > 0) { + atomic_or(p, mask_to_set); + nr -= bits_to_set; + bits_to_set = BITS_PER_LONG; + mask_to_set = ~0UL; + p++; + } + + /* Full words */ + while (nr - bits_to_set >= 0) { + *p = ~0UL; + nr -= bits_to_set; + mask_to_set = ~0UL; + p++; + } + + /* Last word */ + if (nr) { + mask_to_set &= BITMAP_LAST_WORD_MASK(size); + atomic_or(p, mask_to_set); + } else { + /* If we avoided the full barrier in atomic_or(), issue a + * barrier to account for the assignments in the while loop. + */ + smp_mb(); + } +} + void bitmap_clear(unsigned long *map, long start, long nr) { unsigned long *p = map + BIT_WORD(start);