From patchwork Sun Dec 15 15:26:24 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lee Beckermeyer X-Patchwork-Id: 13908795 Received: from mail-io1-f48.google.com (mail-io1-f48.google.com [209.85.166.48]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 8609918CC13 for ; Sun, 15 Dec 2024 15:27:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.48 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276455; cv=none; b=XKagQl9FHrvwceElnfqTjslayeJhR6md+OdUMVx6YkEhV597jnq/4BQK/mdQT3CL6aJ33n8KxUuQh415ivqyjONVMLvpZD607o27H4ymWFW6qnreHG7rcLBKQrfOBBpuC2RI5X6Ss1tKekVoE7v5GsUFZUljsrvZg2346WFoMNo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276455; c=relaxed/simple; bh=rMq8ZDKVTymRphMHn4rWAax0sOLBl/3+7bu9W6eyass=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=XuNnh1oxA2Nr7ybTa+2HoF4j7k0Yp+Agj8emGstmiwtGmEvlsWNobo5vpZ+UqVUqfTeRxiw9Qr2gA13dCrapU3ezjEurN/juu6Ug9y3XEXSn6CeUXseEsQLtKwg49FEiOYk6kAo35gbSySakjACjOLGjAzl4uKVLzEFX4D0ju/E= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=WF1BiWEi; arc=none smtp.client-ip=209.85.166.48 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="WF1BiWEi" Received: by mail-io1-f48.google.com with SMTP id ca18e2360f4ac-844dac0a8f4so259209939f.2 for ; Sun, 15 Dec 2024 07:27:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1734276452; x=1734881252; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=1gSeBZ8/Uq7ekf8xRKF5gqqRjbIGnCkAnvwd2y0iYAE=; b=WF1BiWEinJSsiv/UWoATPIK0qrwwy0S+LeWCvF8StfV+Ranf9pD0knNN8rz79cUYu1 mJwy2/U/04/tzUCovlVVbSoEv+qEU4swnIch1aAcfNu2dDDxW7nO2WNi4hZ8/F0OkJG7 WCWY5gYRCGzzoVnN7FKuimFTm007s2wxLp8u5EqIPG6c9/htwfSRMEw6AheKoN+5ZoeA NkxkRv4dSO1CqQuaRNustXIrUd1HKg8UI03haNopPbSCWhBTn3AzWstI4oQo9yDNbSVC LDJB6Mo3jn7BwBLAnAaO32tvclh+X91Q2bTszDIRXkhnGlyRxuN2blCZ6/1iTEHZntW6 XyfA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1734276452; x=1734881252; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=1gSeBZ8/Uq7ekf8xRKF5gqqRjbIGnCkAnvwd2y0iYAE=; b=mi3wQ69Bx5T8SH9LnWf/U2SnaKSD4baxykMm2KxZ18g3m+lZHncd+vYkaQtR9hGnVY RM/7R5CxTk9ZwZaaB5lCgD9f4r1FS33JbYhQT2bVhhx+e5hFxhvTgJlGBd9MCSjU4/p0 7Sm0IFGjSqwrglZ4uRHb8JT6zW2J6C+BaOCaocGtF9PZFJTirirAatSXfj0jlVuZiVW/ vjhSN3jB94Em0ttWGp9VP/XkPnuvqNP4EktajZD7ICVShbPJB2nHuPMMN8djfrqQkwSx XUMm9kCV1sKLMZ/gcrMJLMfB8cIKJ5fV8uR/gv3PCBBGoiqNyS6oaJvD5WFekQk2YtJn xnUA== X-Gm-Message-State: AOJu0YzfEf6ADmSXiOY6GLsRchl/kUORoRYqhXGsD+Nz7tx7b/bCiyP/ P+q4Ee2myVznGq1w8HAyOgQGNYIYg9/LsE4krZRdMen9m6KrxuMD3K2x2i07 X-Gm-Gg: ASbGncs7AtMQ7uNtUxQn0jmqJJO1OAqZ5q5iTqgElZN7TulEMM7D8ZjeExr6w/LXenf vGF7XhStbljFaPY+ttewwuhqaWPiXRw3nFIM+o4f3Eab+G+R3g+Swccl8rDjtwP9cNkIrG0dREy gmRaVwj90s4sV1E4sexJ7csXpWso/3tKeHFMDMkl0d1fStSjBatKqvb3358oP/WzhMGN90+d2hn niYyC29v+r1iLcQQtTVqxfeTPgcby4kFNPINT0Mx1BID+nzkkNFeoz7QSOF1+jHeA== X-Google-Smtp-Source: AGHT+IGNPBqG5D/4xfoNouKr1/aX76yvh/kMbQWeUHLKFy5qiNPMZmFWaLZ2f8qCXx1w0oLs6SOdJg== X-Received: by 2002:a05:6602:492:b0:835:3ffe:fe31 with SMTP id ca18e2360f4ac-844e88489f9mr1001631539f.8.1734276452229; Sun, 15 Dec 2024 07:27:32 -0800 (PST) Received: from LeeDev.lee.dev ([2600:8804:1a84:2a00:be24:11ff:fe2b:2474]) by smtp.gmail.com with ESMTPSA id 8926c6da1cb9f-4e5e37817e7sm773846173.114.2024.12.15.07.27.30 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 15 Dec 2024 07:27:31 -0800 (PST) From: "Roger L. Beckermeyer III" To: linux-btrfs@vger.kernel.org Cc: "Roger L. Beckermeyer III" , Josef Bacik , Peter Zijlstra Subject: [PATCH v2 1/6] rbtree: add rb_find_add_cached() to rbtree.h Date: Sun, 15 Dec 2024 09:26:24 -0600 Message-ID: <477606e7878ec261878d6e5f6573496d19670887.1734108739.git.beckerlee3@gmail.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Adds rb_find_add_cached() as a helper function for use with red-black trees. Used in btrfs to reduce boilerplate code. Suggested-by: Josef Bacik Signed-off-by: Roger L. Beckermeyer III Acked-by: Peter Zijlstra (Intel) --- include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index 7c173aa64e1e..0d4444c0cfb3 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree, rb_insert_color(node, tree); } +/** + * rb_find_add_cached() - find equivalent @node in @tree, or add @node + * @node: node to look-for / insert + * @tree: tree to search / modify + * @cmp: operator defining the node order + * + * Returns the rb_node matching @node, or NULL when no match is found and @node + * is inserted. + */ +static __always_inline struct rb_node * +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree, + int (*cmp)(struct rb_node *, const struct rb_node *)) +{ + bool leftmost = true; + struct rb_node **link = &tree->rb_root.rb_node; + struct rb_node *parent = NULL; + int c; + + while (*link) { + parent = *link; + c = cmp(node, parent); + + if (c < 0) { + link = &parent->rb_left; + } else if (c > 0) { + link = &parent->rb_right; + leftmost = false; + } else { + return parent; + } + } + + rb_link_node(node, parent, link); + rb_insert_color_cached(node, tree, leftmost); + return NULL; +} + /** * rb_find_add() - find equivalent @node in @tree, or add @node * @node: node to look-for / insert From patchwork Sun Dec 15 15:26:25 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lee Beckermeyer X-Patchwork-Id: 13908796 Received: from mail-io1-f43.google.com (mail-io1-f43.google.com [209.85.166.43]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B93821917F0 for ; Sun, 15 Dec 2024 15:27:35 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.43 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276457; cv=none; b=jD8aY5pUp9T1Xy2HSM5zuztzLDsEvUwYE8hj7TW2OjsHEGCVw769Lkyf4uzQioJHAwjeZhLyLi2paC2IRZkhoWFjxdNKDzEjXCaw//75vpqapOHwrARw/caPzaxpY0rTyb94ImELQL5DmwFLTOmwy7q6R272XciK5C40ZM2nHtw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276457; c=relaxed/simple; bh=YwO42G2oq+KUZyS468HRqz6bQgTi4n+qu7siRhposnk=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=Vg8ZSkZjZQ5Mlrta5iKW3CmNkRXXvV4e6Am+vwKeRG2j7rI/ftn4zUmSe6kzvY9thu8rf/trjVP1uPvKxO97VAYMFNqski9uk0/px/uvTIh8Ix0WvzbyD7Xon/r5zwY6UcIh++6RMDot7edAGw8phnCBFFrD94x1OqXEpBtIv9E= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=Q/sF0eop; arc=none smtp.client-ip=209.85.166.43 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="Q/sF0eop" Received: by mail-io1-f43.google.com with SMTP id ca18e2360f4ac-844e9b7e50dso208118639f.3 for ; Sun, 15 Dec 2024 07:27:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1734276454; x=1734881254; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=TlzuCIv0NjdXnzAT2fw9ny9uemDQRQ/7ztmhsOYboYQ=; b=Q/sF0eopfqpFmqXa0nf2kQCI2oXEx7vGbUSjnufv6foOIWCg3ouC1hMkIULmMoygmQ 1cSXt4tS2/P+YTFf+Kk7pNKc/0WgHjt6HdM1wY0/FcfGyrctPICvL/CJ14pxiHOXm+tP pzkPhzthkk6NmyOsAcgwFvsyn3o4yTYSoOP/xQicAWolCpi6RcgVsBhvAGZBD6jeTJQT W9ng0ig2Kx/Iy5qx9ZmPzl3e7Qi5zJ+FY5G4ZWCCtt92VUHxA/wdnib6TSJj3Vxsk7jL hBr/fqTx1uguEj8MDpaGC9YC5rgym04BNQ4vmARl1UfzdklmCw2m/2uMPPKwMDaFZNPf az7Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1734276454; x=1734881254; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=TlzuCIv0NjdXnzAT2fw9ny9uemDQRQ/7ztmhsOYboYQ=; b=FWetwbkgkQEY7jtN60021QPm0GvITEFy+9ExFnnVBIefISwxmNQz2J5gh4L1VJMGMw Jw/6BR7CnkgGSnOkpjL5ciAAhjQvU9aFvt8hcRPh0EpftvEhAWcXvgP+ja3q+PjP1aO6 PuhPsdML/9OOKrSVSaKj5Wmj1FL9+5SJaUL8+l4JcduokfkaIP3JeimyxyBA0mnejkbd y+lU6aNDYX6vrX/jNqZGETMLT0r9jQkyb4U2baZN/2j//CDF5YyD/u4tiSbU3mJOPEQ+ qednse2/Hha214E7hUUow8R1YnaW1ISUesFiA52iagkeuLjLUE8ZvNYUarbZzc+1WN/P I+SQ== X-Gm-Message-State: AOJu0YyCIULtweFbOOI0PvcKfqLWEkciF0pWnJHuglAAsHE9Y3GvYe/A /aqcSnaid3jYXbtVeloUMYJx7KXVqe9Gx9nMm+WbTl0TEu5a9IGUF0mETw== X-Gm-Gg: ASbGncuB9XicrUcs7gqJe/93xrNWBTXdNWbBMJivYNJCdWUJvv5qZW5jv854lJakd7U vrKxnm+ilEMj/zG/Z4ODo5WSRxCNoZJoeJUAfRXH3kPYZuTQRdYll7Pg+GjOMv/hqdI4BgH74b8 5Qsx0cp6Qvtl9D9G/Rp8jT+d13yuBfSc8s603jqPqZkof7rqXG55vrS4cvb6TvDeYq/8afhAQtB aiphMB+SC3wS3KUhjt+EA3NaPPiCMTbDglQnV2lBYRQX+F4VHIyjRJ7EEbQiJOXiQ== X-Google-Smtp-Source: AGHT+IHCB6M26kAy+J6h1uaP58KItg3OKpHof+pKoGQ1b859Lq4dL8eueRDSuVyMiwcVRqVbPz9bCg== X-Received: by 2002:a05:6e02:1a8b:b0:3a7:44d9:c7dd with SMTP id e9e14a558f8ab-3aff50b2ff0mr126014955ab.6.1734276454506; Sun, 15 Dec 2024 07:27:34 -0800 (PST) Received: from LeeDev.lee.dev ([2600:8804:1a84:2a00:be24:11ff:fe2b:2474]) by smtp.gmail.com with ESMTPSA id 8926c6da1cb9f-4e5e37817e7sm773846173.114.2024.12.15.07.27.32 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 15 Dec 2024 07:27:33 -0800 (PST) From: "Roger L. Beckermeyer III" To: linux-btrfs@vger.kernel.org Cc: "Roger L. Beckermeyer III" , Josef Bacik Subject: [PATCH v2 2/6] btrfs: update btrfs_add_block_group_cache() to use rb helper Date: Sun, 15 Dec 2024 09:26:25 -0600 Message-ID: X-Mailer: git-send-email 2.45.2 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 update fs/btrfs/block-group.c to use rb_find_add_cached(), also implements btrfs_bg_start_cmp() for use with rb_find_add_cached(). Suggested-by: Josef Bacik Signed-off-by: Roger L. Beckermeyer III --- fs/btrfs/block-group.c | 41 ++++++++++++++++++----------------------- 1 file changed, 18 insertions(+), 23 deletions(-) diff --git a/fs/btrfs/block-group.c b/fs/btrfs/block-group.c index 5be029734cfa..a8d51023f7a4 100644 --- a/fs/btrfs/block-group.c +++ b/fs/btrfs/block-group.c @@ -173,40 +173,35 @@ void btrfs_put_block_group(struct btrfs_block_group *cache) } } +static int btrfs_bg_start_cmp(struct rb_node *new, const struct rb_node *exist) +{ + struct btrfs_block_group *cmp1 = rb_entry(new, struct btrfs_block_group, cache_node); + const struct btrfs_block_group *cmp2 = rb_entry(exist, struct btrfs_block_group, cache_node); + + if (cmp1->start < cmp2->start) + return -1; + if (cmp1->start > cmp2->start) + return 1; + return 0; +} + /* * This adds the block group to the fs_info rb tree for the block group cache */ static int btrfs_add_block_group_cache(struct btrfs_fs_info *info, struct btrfs_block_group *block_group) { - struct rb_node **p; - struct rb_node *parent = NULL; - struct btrfs_block_group *cache; - bool leftmost = true; + struct rb_node *exist; ASSERT(block_group->length != 0); write_lock(&info->block_group_cache_lock); - p = &info->block_group_cache_tree.rb_root.rb_node; - - while (*p) { - parent = *p; - cache = rb_entry(parent, struct btrfs_block_group, cache_node); - if (block_group->start < cache->start) { - p = &(*p)->rb_left; - } else if (block_group->start > cache->start) { - p = &(*p)->rb_right; - leftmost = false; - } else { - write_unlock(&info->block_group_cache_lock); - return -EEXIST; - } - } - - rb_link_node(&block_group->cache_node, parent, p); - rb_insert_color_cached(&block_group->cache_node, - &info->block_group_cache_tree, leftmost); + exist = rb_find_add_cached(&block_group->cache_node, + &info->block_group_cache_tree, btrfs_bg_start_cmp); + if (exist) + write_unlock(&info->block_group_cache_lock); + return -EEXIST; write_unlock(&info->block_group_cache_lock); return 0; From patchwork Sun Dec 15 15:26:26 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lee Beckermeyer X-Patchwork-Id: 13908797 Received: from mail-io1-f46.google.com (mail-io1-f46.google.com [209.85.166.46]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 955C51922E9 for ; Sun, 15 Dec 2024 15:27:37 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.46 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276459; cv=none; b=ueBMeFwtdm8OytFSmmflOPX6yFUZ+eZu5COiB6yMiAxfbFVM83iRZr10a6lshb9CXsEpNeaODGr8pHhWu/mnwCw5p3q7+usw//3j/f+IyFINRr9SvJrC5d5zbFtw29eyWdr9RhPW9XmMNA5gCGOArcaGIYaNq3WIh1VmRl0V/UM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276459; c=relaxed/simple; bh=haN17d5VlCoDpqqbZzb7oe3Pqu488YHYg4n2f2UgjX4=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=jMtwMeBxH+L+7RddJ3HEGIpLAe59MmZKXtDTjj/iTPmWa+qTC5K+ghggZTY/FhtbKkWx/QyvFao9Cn8jNsh5ROuPpcnYDvSd8fhwsiFJ2xNbjrKGmqe0/6DWgslIBTGT9nBUTZ+IN3gpfX++UGHaKfnsd8sGHFFUxdSZRtnviqk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=e4Tyt3jD; arc=none smtp.client-ip=209.85.166.46 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="e4Tyt3jD" Received: by mail-io1-f46.google.com with SMTP id ca18e2360f4ac-844ce6d0716so259866139f.1 for ; Sun, 15 Dec 2024 07:27:37 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1734276456; x=1734881256; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=A6AGBEEbL3KEc1Z39BabQVoPtwwwqcya0HUExFb0a4o=; b=e4Tyt3jDyDQjSoKUeoVLvSF4AIDRquU9cKdGLaSQS7dMcqedeYB49MA6sls4JcCauP HCN7SIhcPnysjc/v8r6U1VJ1ppRG7gQ8ViH3SkndAj1d+i2FEZ+oZuClxWk9sP6Mc2Gj zRljJ5flOGGcsGb6cJPsZskwCAWSwkf8S3IhnuNTWZ/bj9oCr5LRCmR7he8SaMXZr+qF yKLcA1uZbpBosEI/MezWUznoHMTE1Hxx2A7mlmeTeS8koKFb52rKjiIanFhA3cGP+2i7 grdTwffcLBcbiDSWZ8Cirt1ohLUaQWas4rYrvNfi/OhQhdVxxLjnadnLxQrfdTE7ycOz hTxQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1734276456; x=1734881256; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=A6AGBEEbL3KEc1Z39BabQVoPtwwwqcya0HUExFb0a4o=; b=alFNSF17wZktpqTvfeI661VGeeOY/iytswp4POnXiCUFKGYj2C7trf/y0p465BzknA myfFlsZVPIfugj/nsaL8WO6Bg9pWJJ5e+NuuzxNQBief3pOsAqxJIx/XQcVlEplJmQeh nBCiMjPSKSE4Q9cuHRo34QkgJnifAFQH9qLKe2yj+I2PfAIkqZDQL2HBW2ZWXbf0ueIk RQIWkrptF/qhdR7gqL5qAjB5ywk29NP2Ny435na9XyD5kwjcTgcOtGWXeczEBOUXKCDV 3DeKQ+g9OkLm31kKxMzrf5THlVppQmk7fz16Dub9w+gctHgpP6AXVSDoTIB+4hiCRmYU y5Mw== X-Gm-Message-State: AOJu0YzibduOnyApM99OPLGO5bY5wAPOF+Z3zjMDqptmg7AgFVhe/g1E ifdYziYUC9LVhw35NaPS9V2pZHaAfTMe5HbJFzdWyxkowb3E9LzxdctbkQ== X-Gm-Gg: ASbGncsVJSU8qtgQaYR2B+qhFYCDoi/rzehL9ZVDNOCxZ0viPWg3fPw10HTrihDdQFT RAxb4wU0Dr2G3VZDyql8BY8KG4+5AGaD01SXyawg0etLK7zNdmApb5p/Bpea5K4d2KLqPM6e+W9 A8dzdthWjdDHfy3MItWmFBP1eRSp2eoBp7aO7H2STVHEijv1IcumRlud9WgsLbzvdA9nsydUUru hN2fvpYtCOXfKPvMvEzdy4RTcNobmRrhdbf84qAZ20q9QJnbn1vHRK+dWdBsaZtlw== X-Google-Smtp-Source: AGHT+IG4EzIDV83bFxfMqTokiE2rLV2ivH3xAGrNKdataL4fTNu4q8KlJySWgYw93ggAGABFxSqjhw== X-Received: by 2002:a05:6602:60cb:b0:844:c76a:354d with SMTP id ca18e2360f4ac-844e87b05a9mr1205381139f.2.1734276455961; Sun, 15 Dec 2024 07:27:35 -0800 (PST) Received: from LeeDev.lee.dev ([2600:8804:1a84:2a00:be24:11ff:fe2b:2474]) by smtp.gmail.com with ESMTPSA id 8926c6da1cb9f-4e5e37817e7sm773846173.114.2024.12.15.07.27.34 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 15 Dec 2024 07:27:34 -0800 (PST) From: "Roger L. Beckermeyer III" To: linux-btrfs@vger.kernel.org Cc: "Roger L. Beckermeyer III" Subject: [PATCH v2 3/6] btrfs: update prelim_ref_insert() to use rb helpers Date: Sun, 15 Dec 2024 09:26:26 -0600 Message-ID: X-Mailer: git-send-email 2.45.2 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 update prelim_ref_insert() to use rb_find_add_cached() adds prelim_ref_cmp for use with rb_find_add_cached() Signed-off-by: Roger L. Beckermeyer III --- fs/btrfs/backref.c | 71 +++++++++++++++++++++++----------------------- 1 file changed, 36 insertions(+), 35 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 6d9f39c1d89c..1326872f172e 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -250,6 +250,17 @@ static int prelim_ref_compare(const struct prelim_ref *ref1, return 0; } +static int prelim_ref_cmp(struct rb_node *node, const struct rb_node *exist) +{ + int result; + struct prelim_ref *ref1 = rb_entry(node, struct prelim_ref, rbnode); + struct prelim_ref *ref2 = rb_entry(exist, struct prelim_ref, rbnode); + + result = prelim_ref_compare(ref1, ref2); + + return result; +} + static void update_share_count(struct share_check *sc, int oldcount, int newcount, const struct prelim_ref *newref) { @@ -281,52 +292,42 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info, struct rb_node **p; struct rb_node *parent = NULL; struct prelim_ref *ref; - int result; - bool leftmost = true; + struct rb_node *exist; root = &preftree->root; p = &root->rb_root.rb_node; + parent = *p; + ref = rb_entry(parent, struct prelim_ref, rbnode); - while (*p) { - parent = *p; - ref = rb_entry(parent, struct prelim_ref, rbnode); - result = prelim_ref_compare(ref, newref); - if (result < 0) { - p = &(*p)->rb_left; - } else if (result > 0) { - p = &(*p)->rb_right; - leftmost = false; - } else { - /* Identical refs, merge them and free @newref */ - struct extent_inode_elem *eie = ref->inode_list; + exist = rb_find_add_cached(&newref->rbnode, root, prelim_ref_cmp); + if (exist) { + /* Identical refs, merge them and free @newref */ + struct extent_inode_elem *eie = ref->inode_list; - while (eie && eie->next) - eie = eie->next; + while (eie && eie->next) + eie = eie->next; - if (!eie) - ref->inode_list = newref->inode_list; - else - eie->next = newref->inode_list; - trace_btrfs_prelim_ref_merge(fs_info, ref, newref, - preftree->count); - /* - * A delayed ref can have newref->count < 0. - * The ref->count is updated to follow any - * BTRFS_[ADD|DROP]_DELAYED_REF actions. - */ - update_share_count(sc, ref->count, - ref->count + newref->count, newref); - ref->count += newref->count; - free_pref(newref); - return; - } + if (!eie) + ref->inode_list = newref->inode_list; + else + eie->next = newref->inode_list; + trace_btrfs_prelim_ref_merge(fs_info, ref, newref, + preftree->count); + /* + * A delayed ref can have newref->count < 0. + * The ref->count is updated to follow any + * BTRFS_[ADD|DROP]_DELAYED_REF actions. + */ + update_share_count(sc, ref->count, + ref->count + newref->count, newref); + ref->count += newref->count; + free_pref(newref); + return; } update_share_count(sc, 0, newref->count, newref); preftree->count++; trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count); - rb_link_node(&newref->rbnode, parent, p); - rb_insert_color_cached(&newref->rbnode, root, leftmost); } /* From patchwork Sun Dec 15 15:26:27 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lee Beckermeyer X-Patchwork-Id: 13908798 Received: from mail-il1-f173.google.com (mail-il1-f173.google.com [209.85.166.173]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EA1DB18C03E for ; Sun, 15 Dec 2024 15:27:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.173 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276460; cv=none; b=HmcFUMl4sSUfDU9MKjoMUZaRz/yq4gAUoG+BxRhjaBdHKFR5GMkZ9YnbvTZRankB9a6z/gLrCPVvCk8djOLPcEYx/Gqq7s518J0ONhPu+wvvgWJonRku5af0FEm6c1VfKW0gq4ZxHfKDPJ7HvPVWaD2nFKy58+iLHksiM9cklAs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276460; c=relaxed/simple; bh=TL2P4Opeqi3tnSxRhznIo0tgiQ9L/P8B4TFiPWtWnx0=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=eQ7eLvAYKtJWkL0X0tONmzuo+s/45ZM1b7mKGTHFKovS3R/iEal0K/yJpPE88T8gzju7PEMncRkg6gekldd0X6kBETbudXm1PA/CrLQTOXGkVxViflFyEeNsrX9kFSCDc7rDGMsfN9429FcBlabobeoHOQUy7Y556IoKkG4LoCk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=T+qUg/KF; arc=none smtp.client-ip=209.85.166.173 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="T+qUg/KF" Received: by mail-il1-f173.google.com with SMTP id e9e14a558f8ab-3a9cee9d741so28954335ab.3 for ; Sun, 15 Dec 2024 07:27:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1734276457; x=1734881257; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=2hKZyhAXipAmnDzSZ6XL4Y/mK7U7fiGkYAKbiVZMpAI=; b=T+qUg/KFBH8bbQhHCz3cEnbfd1Gcgghc5SWyzpQJnSoDG4eYGpSORqtz/7MWGXCFNX id4KIT9tvpnr559Bafu7BgpIPL1CCbgeCkrFPH+5F7jQV64/ghILQEiPovQSYODL2VTx Gz51x5Z8uPkB7KCfMcnfXS7d7UFUZXtJgqvLzhB7Wh54pcXJJEf/+MwBr6uE3oZJ/5Bl m7wzixzwZvJ0LKFdT8CfyNMVMXtuVAOjqSPdkiq+lu398A1FRR8ShklmM2AjfbWEsM/5 zpMCqczqwpQRGiyF7mZFB+XzC/bguAUmZjNxPRSQXhgLo7jq7mpxpafWhEDJgisCaXwJ QDXw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1734276457; x=1734881257; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=2hKZyhAXipAmnDzSZ6XL4Y/mK7U7fiGkYAKbiVZMpAI=; b=udcT4r4OL5dR0BupjBc3z6dtTcFtAhp5JzyK2s6lIcee1AEgtzMOzCKDLHhkv6quer uaH2cLVGno2ym+OX2Yt4+u5GEdMk1lolHcIo5l7R+rqEtKANJm4hOutDuXNaWLjSvUVl MglZg09AiKYr/t6j1Q/5wlcaNtqX//DzefvUJw/td4ycyVa52GR8GwbGLhjjohft8k9A QC2OjNYuOm3D6qnHUV/sQ/1o2PbTekmREXBH2YEqWd0vxbl1+OJqZzi59zkx6D5z2FzQ LYhTFLkD/2QSZYOatv3BIIiJMhjcAgEn2tx6x0p4FuW7cZhiHLBEW1NVXFXVisO8IxXV GhtA== X-Gm-Message-State: AOJu0YwUOwfdYlWwkIzbADBQ6F92kjweLMLYrt5eUy1voZ/wKds1x9s6 opXrd1d7Cnq/S2nwc/FcrVdZkCwisUJKlVw56uKzD+BbZdzC94k0vZ9Bhw== X-Gm-Gg: ASbGncviVTvsuCaYoYflWEvNGoEFbzsfuE9LTAY8fsT4w27tVJusOug71jlBvPagEpN Q9uOPqJ1brNqT50xqkoZ6ABCfv2E2KiJH+F7Ko+DD3AIZbimd+TIpPrXBlrN/x6a5QsfFfer5dp avG4AchnvzM2c/S4up9dseaPU8kZWeAfnVU7Qc0Q3vwgFCnv1nmThETXJ0loV6dkcE+HBatnHgG tYRRd9iGFccq4mj0TxXesRjDZ/YbzQvVU/r/Hdkx0MJb0eeFrDzjTMMH9n5DP5egg== X-Google-Smtp-Source: AGHT+IEEVDg99A+0721vDLyfGAitoGJ+1Sise7icPOI2sQwrjtu45XNNlboEAremMvmVsYZY/14Uzg== X-Received: by 2002:a05:6e02:2169:b0:3a7:7d26:4ce4 with SMTP id e9e14a558f8ab-3afee2d0367mr94731505ab.9.1734276457458; Sun, 15 Dec 2024 07:27:37 -0800 (PST) Received: from LeeDev.lee.dev ([2600:8804:1a84:2a00:be24:11ff:fe2b:2474]) by smtp.gmail.com with ESMTPSA id 8926c6da1cb9f-4e5e37817e7sm773846173.114.2024.12.15.07.27.36 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 15 Dec 2024 07:27:36 -0800 (PST) From: "Roger L. Beckermeyer III" To: linux-btrfs@vger.kernel.org Cc: "Roger L. Beckermeyer III" Subject: [PATCH v2 4/6] btrfs: update __btrfs_add_delayed_item() to use rb helper Date: Sun, 15 Dec 2024 09:26:27 -0600 Message-ID: <7952094105650aa5a596cf5d6cc2a58520c14dee.1734108739.git.beckerlee3@gmail.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 update __btrfs_add_delayed_item() to use rb_find_add_cached() add btrfs_delayed_item_cmp() to use with rb_find_add_cached() Signed-off-by: Roger L. Beckermeyer III --- fs/btrfs/delayed-inode.c | 40 ++++++++++++++++------------------------ 1 file changed, 16 insertions(+), 24 deletions(-) diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c index 508bdbae29a0..4bd02e566ab2 100644 --- a/fs/btrfs/delayed-inode.c +++ b/fs/btrfs/delayed-inode.c @@ -366,40 +366,32 @@ static struct btrfs_delayed_item *__btrfs_lookup_delayed_item( return NULL; } +static int btrfs_delayed_item_cmp(struct rb_node *rb_node, const struct rb_node *exist_node) +{ + struct btrfs_delayed_item *item = rb_entry(rb_node, struct btrfs_delayed_item, rb_node); + const struct btrfs_delayed_item *exist = rb_entry(exist_node, struct btrfs_delayed_item, rb_node); + + if (item->index < exist->index) + return -1; + if (item->index > exist->index) + return 1; + return 0; +} + static int __btrfs_add_delayed_item(struct btrfs_delayed_node *delayed_node, struct btrfs_delayed_item *ins) { - struct rb_node **p, *node; - struct rb_node *parent_node = NULL; struct rb_root_cached *root; - struct btrfs_delayed_item *item; - bool leftmost = true; + struct rb_node *exist; if (ins->type == BTRFS_DELAYED_INSERTION_ITEM) root = &delayed_node->ins_root; else root = &delayed_node->del_root; - p = &root->rb_root.rb_node; - node = &ins->rb_node; - - while (*p) { - parent_node = *p; - item = rb_entry(parent_node, struct btrfs_delayed_item, - rb_node); - - if (item->index < ins->index) { - p = &(*p)->rb_right; - leftmost = false; - } else if (item->index > ins->index) { - p = &(*p)->rb_left; - } else { - return -EEXIST; - } - } - - rb_link_node(node, parent_node, p); - rb_insert_color_cached(node, root, leftmost); + exist = rb_find_add_cached(&ins->rb_node, root, btrfs_delayed_item_cmp); + if (exist) + return -EEXIST; if (ins->type == BTRFS_DELAYED_INSERTION_ITEM && ins->index >= delayed_node->index_cnt) From patchwork Sun Dec 15 15:26:28 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lee Beckermeyer X-Patchwork-Id: 13908799 Received: from mail-io1-f54.google.com (mail-io1-f54.google.com [209.85.166.54]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 3ADC11925BF for ; Sun, 15 Dec 2024 15:27:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.54 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276462; cv=none; b=A68ynwL7mhWU/3xJYIo0lHSGZPjM5VmhIIh2HjYzAPbuKIpeKl15apzkTjCxKHtbeEXde5HgD4KdZ0hW9G5TkQRpXBJMzefEZfP/PjMe+P7Bj1JtD8rOCFkjM5a1+9Ga6lfVW7O99fE7wONhEKvMO0cr9edhacYf2qNnKmW6Gy0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276462; c=relaxed/simple; bh=9b9YTj2xnHIEzes/Vr5Ux4+osSi8HavPDgrLuL9LjvQ=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=eZktThptpwmo7A8BDBjbvqjISJMxlmma7d4IBvrg74XdJowvUJXIz65Bcnrlrl0DzC6pg62T0ePcEKFiG4D302v+7pcGS6qyzmuVbGJf6nTR0jc11iO2aNNZE6/Ikv3lfTkpauRadzOrREQwspB/pJsSfc0SKohnUM1/0/8mVyE= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=VRP1pAqa; arc=none smtp.client-ip=209.85.166.54 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="VRP1pAqa" Received: by mail-io1-f54.google.com with SMTP id ca18e2360f4ac-844dac0a8f4so259214039f.2 for ; Sun, 15 Dec 2024 07:27:41 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1734276459; x=1734881259; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=b0aR2sgw+Yd4htpY5BB3Zi6WNHIYiaERlucEqL79HRw=; b=VRP1pAqa58q2TeQB01YVZ/Pxd4T6MjjroxdyxV6hWbOO7zCApIsKpKzIPMvyJ00uBP gwZEJi98mF4TGPRSTggpP6Y/RYdfL+2INbRB2QmkjF8W4p10Dd1EJiNs9Gqsgryc0VcB Sb4VWKsdew8gB+jWjDlzCQshf4R2Q6kdn/6pN1rwjVdVpJFElEhhz2oqiMw772qVR2Ns 7lmZqWkqywNyYLU8fqrsSABu1ELKXsv+ECQ35EINXvplGC37ddFO0c4q8/msTGfna+br eG/IbAWKas4pVp21LjK4WcWcr8C0JcJyoP98OtfxgagxJ5XQEBgZE3BWqFKQOHa0mAER bBVA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1734276459; x=1734881259; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=b0aR2sgw+Yd4htpY5BB3Zi6WNHIYiaERlucEqL79HRw=; b=WP5pmbIoS2wbg3Uvr6Y5hIeB5dduqAUJjqV3PEt4pysnU23djs7oXGuFDII6K+GxID NdkJKyBhwlALnWQxdLmcouW0v0ilbiUv/+8i04++Z7FJ7iGzVBybGVdKeKYRtfT4R27N ZkZ8a1PxBsdRoqiGpHj1Xiyq6B+ru0mLUV2ETJza8pp3IUg/t2G1S/mCCHIOydLepdFZ b9jf/x0eCL9+0Q80aqV+llRGgM1UsikFBgVXFoVE3QYK2zBVXDtRZXWLQif0XjNRsk5n meckB5za0QzE5OrqHFzdJAkQL3JP9DsgshSwizzB73rJ4GJiwMZbBEsbSPNE5c+3aURX Qa1g== X-Gm-Message-State: AOJu0YxAmi0+C86jOMBrD9Di0o6U8rliN4ditSDxDMZiUpjNDxXyu+4Y lUo7dzTn6nXpoY/GxKDusIjpds6+Y5D2NAfOPywm8ve7S5Mz6FbOh0bDHA== X-Gm-Gg: ASbGncvYPWkiJknFS9HCjzacLg6qZxg2II6eb4V1xg29pRJHz84hfXi5Xq5L7pIptFx Y8lxC2iW5UE2I+wPMOExdsHN+ogNvWHcHZvD/Lef02rMAWYKq3aFeY7VsnVOOC6tUIFJq5swd9e d1tsGI3djEaazpvqRR0qdmXuIDV4PQhnzgVYUP19iPljhtKYFoiKzuYbsE7GQmO6yjwBG30mzEx ztiIbol3g97+Qz5T0qG3GYXfXRQ/gUVM74b8V7ehMvY+cRqZLtjfMYZzG+Aia4wGg== X-Google-Smtp-Source: AGHT+IG/nvI5+CkxMa1XgAhYFTCYzwwC+ORgy5PRv0limqykxZX/c6yZ0OIut4WIppb0K/oOio+yrA== X-Received: by 2002:a05:6602:60cb:b0:844:c76a:354d with SMTP id ca18e2360f4ac-844e87b05a9mr1205394639f.2.1734276459638; Sun, 15 Dec 2024 07:27:39 -0800 (PST) Received: from LeeDev.lee.dev ([2600:8804:1a84:2a00:be24:11ff:fe2b:2474]) by smtp.gmail.com with ESMTPSA id 8926c6da1cb9f-4e5e37817e7sm773846173.114.2024.12.15.07.27.37 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 15 Dec 2024 07:27:38 -0800 (PST) From: "Roger L. Beckermeyer III" To: linux-btrfs@vger.kernel.org Cc: "Roger L. Beckermeyer III" Subject: [PATCH v2 5/6] btrfs: update btrfs_add_chunk_map() to use rb helpers Date: Sun, 15 Dec 2024 09:26:28 -0600 Message-ID: <189d8684f80c95a89d162f8aaa2bb676cad77d65.1734108739.git.beckerlee3@gmail.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 update btrfs_add_chunk_map() to use rb_find_add_cached(). add btrfs_chunk_map_cmp to use with rb_find_add_cached(). Signed-off-by: Roger L. Beckermeyer III --- fs/btrfs/volumes.c | 39 ++++++++++++++++++--------------------- 1 file changed, 18 insertions(+), 21 deletions(-) diff --git a/fs/btrfs/volumes.c b/fs/btrfs/volumes.c index 1cccaf9c2b0d..d51badec5520 100644 --- a/fs/btrfs/volumes.c +++ b/fs/btrfs/volumes.c @@ -5513,33 +5513,30 @@ void btrfs_remove_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_ma btrfs_free_chunk_map(map); } +static int btrfs_chunk_map_cmp(struct rb_node *rb_node, const struct rb_node *exist_node) +{ + struct btrfs_chunk_map *map = rb_entry(rb_node, struct btrfs_chunk_map, rb_node); + const struct btrfs_chunk_map *exist = rb_entry(exist_node, struct btrfs_chunk_map, rb_node); + + if (map->start == exist->start) + return 0; + if (map->start < exist->start) + return -1; + return 1; +} + EXPORT_FOR_TESTS int btrfs_add_chunk_map(struct btrfs_fs_info *fs_info, struct btrfs_chunk_map *map) { - struct rb_node **p; - struct rb_node *parent = NULL; - bool leftmost = true; + struct rb_node *exist; write_lock(&fs_info->mapping_tree_lock); - p = &fs_info->mapping_tree.rb_root.rb_node; - while (*p) { - struct btrfs_chunk_map *entry; - - parent = *p; - entry = rb_entry(parent, struct btrfs_chunk_map, rb_node); - - if (map->start < entry->start) { - p = &(*p)->rb_left; - } else if (map->start > entry->start) { - p = &(*p)->rb_right; - leftmost = false; - } else { - write_unlock(&fs_info->mapping_tree_lock); - return -EEXIST; - } + exist = rb_find_add_cached(&map->rb_node, &fs_info->mapping_tree, btrfs_chunk_map_cmp); + + if (exist) { + write_unlock(&fs_info->mapping_tree_lock); + return -EEXIST; } - rb_link_node(&map->rb_node, parent, p); - rb_insert_color_cached(&map->rb_node, &fs_info->mapping_tree, leftmost); chunk_map_device_set_bits(map, CHUNK_ALLOCATED); chunk_map_device_clear_bits(map, CHUNK_TRIMMED); write_unlock(&fs_info->mapping_tree_lock); From patchwork Sun Dec 15 15:26:29 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Lee Beckermeyer X-Patchwork-Id: 13908800 Received: from mail-il1-f182.google.com (mail-il1-f182.google.com [209.85.166.182]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4D05718C03E for ; Sun, 15 Dec 2024 15:27:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.166.182 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276463; cv=none; b=muobCo18c2Ydn/WIhO8frKYy+RJi4tM+tBfAxclDAFqi92gXPBxTxX+KhO2LdItxxV/Y3ZE863I0Olx8a2a6rjcx947fEs28pCSW+iXDtaC9nkcMs3zLUMmJtu05aMzczLr22p1nAuIF219agCPoId/k+mUtfHE6pzKzNVk/e4U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1734276463; c=relaxed/simple; bh=S9q/gqoCGQSTBJaL/XPR7RBgfsM9yk6zCIMob2X5U4U=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=PgaoHFaZ9NZ3JxxcMSA26aF/tULetFnNva38wHm49hZjLYTYc4GjGlQ1d+/Pkcznb5QnIxHkTwRmcOVp1g7ms70hAtoI2l3+VAxf+/eqHMgeMqiDmDEomVX0c4tqnZ+d1FIy/wl8P6XA4KC/xPyZ+Nqst282zgh3+pBMGeRXT8Y= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=d+e6hfIv; arc=none smtp.client-ip=209.85.166.182 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="d+e6hfIv" Received: by mail-il1-f182.google.com with SMTP id e9e14a558f8ab-3a813899384so11003255ab.1 for ; Sun, 15 Dec 2024 07:27:42 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1734276461; x=1734881261; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=rH2YDzE9BzkjH6aaDCpwyy/gxU5Y5o0kfARs9T4CMNE=; b=d+e6hfIvhCHpljzyKhgzHUnUQYtnz3yy9pXbW3uD1DiT6DC3xiK2rpdS3yZVOUStXr C/G2oOvMMBlvhNx6uj+neAlg16qZYkePaDc95i/MYv9TYqnfL2fGU+g0KFgfK29D2C+k 4cBPk8T29cs23xry3r+GJbXyJ2MX5kRZUJbv/9kpQJw6ewmdHgtsXO1+ut+ONliBlOMb rvn/9bnZjUvZxzNAeiJZFaVdJiEam4Ecircr6NICqCjLfnTOhzVuuR8wPHI4TEFSZ1f2 wEJ21YimmPBwPLW3HWNXcjDpSzaPm2uWxLq+mso7LUOmx/x0DxwlR6atTELEj86bD/5R XEaQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1734276461; x=1734881261; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=rH2YDzE9BzkjH6aaDCpwyy/gxU5Y5o0kfARs9T4CMNE=; b=V8Ym21S1UaqsvevjVVvbvkUMvcN48CF7jZ7Y6zZF4ZlYgu0mtETRbUlo7sOU9lR/R3 +hyJbrzVMp7xjZVQdvuwGopFlu+qVuPZifLP/Y+bhmZgs0YyDah+207fbQa2JkUh0j9A s5qjJ+xcUCZgbrKt3hDkZSwoLeutsi8fuMrHzo4TDHaLfnxGxS9sKb6rSE64nANBe1Jl Hf57mM1gCN6Jym3CbdwcJ8/a54r3v4CkKf2glRMovt2XLr9XkgI3Fm+AfKYcxwgFlHAX lkQXLg0y+GRdrpcTiJYokCu8yZmLcZgsou9KAKLHRTrJ9oxBZbntEIrAqyZVkjKim3QB dbkA== X-Gm-Message-State: AOJu0Yzvia1mF2SLtmS501fz81U6pPqBoeV/7Wg78vLimPQSKMGjLyMW wcHQE6229RqRBrxWbxwQONLBVgw0p3rJ015+QTXeq3buvbpT9hfnjpcQ0A== X-Gm-Gg: ASbGncuxikpUt0xLWGefIQoL8uGUzSKFWL+dzeyZ175ZDkEEE6qnaxjdCkn0N5blQ0Z G4z+VtnaMDEZ9Bu1diOYdLGt43qKHYLnYFtgjvhm8Wlxqq4Y0pOEOBX06W4/D+vX20FzkUpYNh4 BoJd0Gbd8rClqzwy/EqCu0WCOhCA57SYLn2ccYWXDjDQSgr8/uAGgtJo+QXXr3Qsmgus/oByZM4 CLihGW6XKINAoMSo18EmUB5Xvc3+R47tSaBk3aqpe79TFuHf5jxt5hfixNkj2lXAg== X-Google-Smtp-Source: AGHT+IHIi4mEakLdanagl/CcFFc4aAZNSK4nx1lzOZIMMZAVUaqZu7xz3k4v1/fCa4LeXEb/KA1Rxg== X-Received: by 2002:a05:6e02:190f:b0:3a7:e800:7d26 with SMTP id e9e14a558f8ab-3aff6eada72mr105154235ab.8.1734276461100; Sun, 15 Dec 2024 07:27:41 -0800 (PST) Received: from LeeDev.lee.dev ([2600:8804:1a84:2a00:be24:11ff:fe2b:2474]) by smtp.gmail.com with ESMTPSA id 8926c6da1cb9f-4e5e37817e7sm773846173.114.2024.12.15.07.27.39 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 15 Dec 2024 07:27:40 -0800 (PST) From: "Roger L. Beckermeyer III" To: linux-btrfs@vger.kernel.org Cc: "Roger L. Beckermeyer III" Subject: [PATCH v2 6/6] btrfs: update tree_insert() to use rb helpers Date: Sun, 15 Dec 2024 09:26:29 -0600 Message-ID: <2fca678bb30eee8390f90575736461da28fc0c75.1734108739.git.beckerlee3@gmail.com> X-Mailer: git-send-email 2.45.2 In-Reply-To: References: Precedence: bulk X-Mailing-List: linux-btrfs@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 update tree_insert() to use rb_find_add_cached(). add cmp_refs_node in rb_find_add_cached() to compare. Signed-off-by: Roger L. Beckermeyer III --- fs/btrfs/delayed-ref.c | 39 ++++++++++++++++----------------------- 1 file changed, 16 insertions(+), 23 deletions(-) diff --git a/fs/btrfs/delayed-ref.c b/fs/btrfs/delayed-ref.c index 30f7079fa28e..dcacce2c2096 100644 --- a/fs/btrfs/delayed-ref.c +++ b/fs/btrfs/delayed-ref.c @@ -317,34 +317,27 @@ static int comp_refs(struct btrfs_delayed_ref_node *ref1, return 0; } +static int cmp_refs_node(struct rb_node *node, const struct rb_node *node2) +{ + struct btrfs_delayed_ref_node *ref1; + struct btrfs_delayed_ref_node *ref2; + bool check_seq = true; + + ref1 = rb_entry(node, struct btrfs_delayed_ref_node, ref_node); + ref2 = rb_entry(node2, struct btrfs_delayed_ref_node, ref_node); + + return comp_refs(ref1, ref2, check_seq); +} + static struct btrfs_delayed_ref_node* tree_insert(struct rb_root_cached *root, struct btrfs_delayed_ref_node *ins) { - struct rb_node **p = &root->rb_root.rb_node; struct rb_node *node = &ins->ref_node; - struct rb_node *parent_node = NULL; - struct btrfs_delayed_ref_node *entry; - bool leftmost = true; - - while (*p) { - int comp; - - parent_node = *p; - entry = rb_entry(parent_node, struct btrfs_delayed_ref_node, - ref_node); - comp = comp_refs(ins, entry, true); - if (comp < 0) { - p = &(*p)->rb_left; - } else if (comp > 0) { - p = &(*p)->rb_right; - leftmost = false; - } else { - return entry; - } - } + struct rb_node *exist; - rb_link_node(node, parent_node, p); - rb_insert_color_cached(node, root, leftmost); + exist = rb_find_add_cached(node, root, cmp_refs_node); + if (exist) + return rb_entry(exist, struct btrfs_delayed_ref_node, ref_node); return NULL; }