From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mailout3.rbg.tum.de (mailout3.rbg.tum.de [131.159.0.8]) by sourceware.org (Postfix) with ESMTPS id 8AB21385AE4F for ; Mon, 12 Sep 2022 18:03:37 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8AB21385AE4F Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=in.tum.de Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=in.tum.de Received: from mailrelay1.rbg.tum.de (mailrelay1.in.tum.de [131.159.254.14]) by mailout3.rbg.tum.de (Postfix) with ESMTPS id 12F5F100245; Mon, 12 Sep 2022 20:03:36 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=in.tum.de; s=20220209; t=1663005816; bh=r2zXvSLpqQaBBleabMrXU5Yn8wkE3Qg0VSXXqAYgn2c=; h=Date:Subject:To:Cc:References:From:In-Reply-To:From; b=K2spUEJjXP34cYkKySGhSLG4Qqe1Zm8GVH4aNOirc2n9nB3sybEVGImhspHkUPJc+ WTsQjuMnc2rH40Mu+0WUN4SaCvS36WpeEjnCUu6P+o2NC4nDsVTixMl1eHyAKaacvz tS1P+5uY3wMovwoP/ooucQHhRAMLmxSd/z9sJgsi4jixD+PQlowaiTvxZJiMCDtGj3 cnAHqVpAJhDOwkOhF16uQtgbL65r391pV0uN1OOnVnenxWlNKSzYuPpdu6Pm6XwNNP Nr/l+CgvnCc3I6NewNXZ1KbbZXTCH3RaV/cS7eijqaKTLVLSIU4JqgMXp6x3bDSdg0 xT+GCak8W+sBA== Received: by mailrelay1.rbg.tum.de (Postfix, from userid 112) id 0F87D542; Mon, 12 Sep 2022 20:03:36 +0200 (CEST) Received: from mailrelay1.rbg.tum.de (localhost [127.0.0.1]) by mailrelay1.rbg.tum.de (Postfix) with ESMTP id D931F135; Mon, 12 Sep 2022 20:03:35 +0200 (CEST) Received: from mail.in.tum.de (mailproxy.in.tum.de [IPv6:2a09:80c0::78]) by mailrelay1.rbg.tum.de (Postfix) with ESMTPS id D657422; Mon, 12 Sep 2022 20:03:35 +0200 (CEST) Received: by mail.in.tum.de (Postfix, from userid 112) id D342E4A0226; Mon, 12 Sep 2022 20:03:35 +0200 (CEST) Received: (Authenticated sender: neumann) by mail.in.tum.de (Postfix) with ESMTPSA id 813A74A010F; Mon, 12 Sep 2022 20:03:35 +0200 (CEST) (Extended-Queue-bit xtech_dr@fff.in.tum.de) Message-ID: <3740268a-c99f-c395-9445-15cf33e3555f@in.tum.de> Date: Mon, 12 Sep 2022 20:03:35 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.11.0 Subject: Re: [PATCH v3] eliminate mutex in fast path of __register_frame Content-Language: en-US To: Jason Merrill , gcc-patches@gcc.gnu.org Cc: Florian Weimer , Jakub Jelinek , Jonathan Wakely , Thomas Rodgers References: <21a63ae5-1f97-e084-afeb-c74e5cba137d@in.tum.de> From: Thomas Neumann In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-4.5 required=5.0 tests=BAYES_00,BODY_8BITS,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,NICE_REPLY_A,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: Thanks for your feedback, I will update the patch in the next few days, addressing the comments and reorganizing classify_object_over_fdes. Concerning your question: >> + >> +restart: >> +  struct btree_node *iter; >> +  uintptr_t lock; >> +  { >> +    // Accessing the root node requires defending against concurrent >> pointer >> +    // changes Thus we couple rootLock -> lock on root node -> >> validate rootLock > > Can you elaborate a bit more in the comment on why it's necessary and > sufficient to validate the containing node after "locking" the child node? > >> +    if (!version_lock_lock_optimistic (&(t->root_lock), &lock)) >> +      goto restart; >> +    iter = RLOAD (t->root); >> +    if (!version_lock_validate (&(t->root_lock), lock)) >> +      goto restart; >> +    if (!iter) >> +      return NULL; >> +    uintptr_t child_lock; >> +    if ((!btree_node_lock_optimistic (iter, &child_lock)) >> +    || (!version_lock_validate (&(t->root_lock), lock))) >> +      goto restart; >> +    lock = child_lock; >> +  } >> + >> +  // Now we can walk down towards the right leaf node We are reading here without explicit locks, i.e., memory can change behind our back at any time. Thus, before we act on a value that we have read, we must check if that value is still valid. The invariants that we rely upon are: I1) a node pointer will always be either a nullptr or point to a b-tree node. The node might have been logically deleted, but the memory will always remain valid due to our free list. I2) The root pointer is only modified by a thread that holds an exclusive lock on root_lock. I3) valide calls fail if a) somebody else currently holds the lock, or b) if the version value has changed since locking, which happens when somebody releases an exlusive lock. Using that, the code does the following steps 1. We lock root_lock optimistic. In case of an exclusive lock we restart immediately, otherwise we remember the current version 2. We load the root pointer and store it in iter. iter might contain arbitrary garbage due to races 3. We validate the root_lock, and restart in case of errors. Now we know that a) nobody has locked the root exclusively or modified it since step 1 (I3), and b) iter indeed points to the node that corresponds the to the version that we have read in step 1 (due to I2) At this point we now that iter is indeed the right root pointer. If it is a nullptr we stop here. Otherwise we continue with 4. We lock the root node itself (iter), storing the validated version in child_lock. We need that lock to detect changes to the content of the root, the root_lock only protects the pointer to the root. Loading the lock is safe due to I1. As our tree can change at any point in time, we need another valide call on root_lock to make sure that we still have the right root pointer. At this point we have both a pointer to the root node and an optimistic lock that allows us to detect changes to the content of the root. Thus, we can safely navigate down, any changes to the b-tree that could affect us, like, e.g., node splits in the root, will be detected when validating the lock. I hope that answered both the necessary and sufficient part. As a general rule, you must always use the pair relax-atomic-read + validate to avoid data races. Acting on any value that you have not validated is unsafe, as you could get races. Best Thomas