From nobody Tue Dec 2 02:51:15 2025 Received: from mail-pf1-f202.google.com (mail-pf1-f202.google.com [209.85.210.202]) (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 83EA034BA5B for ; Mon, 17 Nov 2025 22:47:17 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763419639; cv=none; b=jbBuOpgidhqv/FDwI0StLxHNfEynjueMGi7QQ11vhzTJedfvivAxzDKHq3tOZ+wUpo3jcndTkdhONNhgDG35tQGMrBNyklyLYBGyMsrlPBdYpIF66SrN04Q+q8ZRbKfoDsy/AGdmEkm7tljduT+4LMh4whiMV5Vid6EMqskABP0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763419639; c=relaxed/simple; bh=tfIrZCoJ3VIjC7+RLHtxfRRKbaNTL7uBfbInHHXOwE8=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=fVPIzBQaCJbd3f8a3OQ9BKYoxyHFVk/ccD4n5sasn5S3EWeeVDaSGWALocpK2/eum3RzvVwYiQH2cKZ2sfOYAntahLod1s50QM4FegSmnvFpcqVItLq8OaZdt1yUmlAoIOGmQRBVx3W19pQc2w2iaSyHndTxizbEJ493o3cjLU0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--ackerleytng.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=g7BTvmZO; arc=none smtp.client-ip=209.85.210.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--ackerleytng.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="g7BTvmZO" Received: by mail-pf1-f202.google.com with SMTP id d2e1a72fcca58-7b6b194cf71so6335761b3a.3 for ; Mon, 17 Nov 2025 14:47:17 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1763419637; x=1764024437; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=ZYrCejxRy7zqyBcb6FQMxX806Q+d7GZ40YGLARpuYbw=; b=g7BTvmZOI/LSZ+tuNi5YY1JLkZMh4ONfi18XrXYPP7djTk7BsfWZbQ05hBzn4+9EGa /RfRUQQmgi4BE+ZMkTSGzG07Q3EfqCejwn67KWf+aPXw3Ivj7ehMFFv1r3oTXDVPkCRn A7NbbJvnE5sp4LG2cEqtVC9eoG30CUh9orn1313aINsUKPwwwO0IXbb2ru7enpGaGd9h 9quVpRSRd/uTGDSvVaCck51sWWVqNFY40MmsTqbec5uUf2mrMWCfdXEpSzBaYwvk30D4 K1szaxXI2ps1mWvOm7Qgfme+7L4jIFTpUIwVps6NMvGlkuYm3pCOXeg5HR1uaYtmf31z iCSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763419637; x=1764024437; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=ZYrCejxRy7zqyBcb6FQMxX806Q+d7GZ40YGLARpuYbw=; b=XcY+GcBUHyTbbsH5B7n4KawBnO0jnNUf/QmvYvvuuImWItoKxtynAYJmSX9qQLT4rk EVUzXfitG0p8ktTkuRuy7PiIAblmkwzLmmBSq6jWNl99dSK/Ux5sBYL3sueiDU8CNYBO sBnHjwGNwY1F/iNXCowsOpBOovWTUxXj92sCs8T0ZbhPZSx0tB+wEHBDB/69YiLTyiM8 TGEgqnTWeymgnMNIq1VgDDfHaoKMjO+Al4u8qX3T4NoFaIroPosg0xnSzfXv6ZeN306R Wo7QI5mxOaM6W53w/bm+t5p3YrLLCYakBHGfYAJXrfg0XY5rsdvgmajqFlV2OEFKUVRP Pd5Q== X-Forwarded-Encrypted: i=1; AJvYcCV+zf4H3IcrnnH68zubCfqFnDjrIUPBAjBx/qrmf41MnJgEBNNgsiRtv+2IOOuoNqa8wzMl4MnzyMOXdCE=@vger.kernel.org X-Gm-Message-State: AOJu0YzaW0i/lU7yzkCM9hb3xSC9+JMZZuC7oTt9DN8Bcbwwa7bjrxh4 v8Pp9csaftRkgTnQPWMK+SOdsztiRxgoZ4ohU72VoLECTMEP7kABJL4vLW/o9Vu4hvo0/lvt6yP qkGzHz6Ao7LNpswBmFhEPZF3/OA== X-Google-Smtp-Source: AGHT+IF6X8M1O0ViseXJqknBCFgh9mD5b/95Oi6jmON/74K3wmmst3PfgAJtVAD5wgeUf0evNnb0s3MpsbBQZ/irZw== X-Received: from pgbfe13.prod.google.com ([2002:a05:6a02:288d:b0:bc8:cea8:200a]) (user=ackerleytng job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6a21:33a1:b0:344:8ef7:7a03 with SMTP id adf61e73a8af0-35ba2992e6dmr19087812637.56.1763419636821; Mon, 17 Nov 2025 14:47:16 -0800 (PST) Date: Mon, 17 Nov 2025 14:46:58 -0800 In-Reply-To: <20251117224701.1279139-1-ackerleytng@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251117224701.1279139-1-ackerleytng@google.com> X-Mailer: git-send-email 2.52.0.rc1.455.g30608eb744-goog Message-ID: <20251117224701.1279139-2-ackerleytng@google.com> Subject: [RFC PATCH 1/4] XArray: Initialize nodes while splitting instead of while allocating From: Ackerley Tng To: willy@infradead.org, akpm@linux-foundation.org, linux-fsdevel@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: david@redhat.com, michael.roth@amd.com, vannapurve@google.com, Ackerley Tng Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Currently, newly allocated nodes in xas_split_alloc are initialized immediately upon allocation. This occurs before the node's specific role, shift, and offset within the splitting hierarchy are determined. Move the call to __xas_init_node_for_split() from xas_split_alloc() to xas_split(). This removes any dependence on "entry" during node allocation, in preparation for extending xa_split* functions to support multi-level splits, where intermediate nodes need not have their slots initialized. Signed-off-by: Ackerley Tng --- After moving the call to __xas_init_node_for_split() from xas_split_alloc() to xas_split(), void *entry is unused and no longer needs to be passed to xas_split_alloc(). I would like to get feedback on moving initialization into xas_split() before making a full refactoring to remove void *entry as a parameter to xas_split_alloc(). lib/xarray.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/xarray.c b/lib/xarray.c index edb877c2d51c..636edcf014f1 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1060,7 +1060,6 @@ void xas_split_alloc(struct xa_state *xas, void *entr= y, unsigned int order, if (!node) goto nomem; - __xas_init_node_for_split(xas, node, entry); RCU_INIT_POINTER(node->parent, xas->xa_alloc); xas->xa_alloc =3D node; } while (sibs-- > 0); @@ -1103,6 +1102,7 @@ void xas_split(struct xa_state *xas, void *entry, uns= igned int order) struct xa_node *child =3D xas->xa_alloc; xas->xa_alloc =3D rcu_dereference_raw(child->parent); + __xas_init_node_for_split(xas, child, entry); child->shift =3D node->shift - XA_CHUNK_SHIFT; child->offset =3D offset; child->count =3D XA_CHUNK_SIZE; -- 2.52.0.rc1.455.g30608eb744-goog From nobody Tue Dec 2 02:51:15 2025 Received: from mail-pf1-f202.google.com (mail-pf1-f202.google.com [209.85.210.202]) (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 335B634DB55 for ; Mon, 17 Nov 2025 22:47:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.210.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763419642; cv=none; b=GDkKVujo49vGrgi2JJFr/3ujuHfuuh975RpZC+WzU/ucuU0OcP2b197FY8o0a+wgQuszkKgGd3EfuIz4kRa5K/9slhlX+wYFNDWc1nKxrmj2NVSbFF42wicMMPmWwQXJcw0lNJG3TXBew0iQ0ghKCho8gLSyomD/R72CitUVtaw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763419642; c=relaxed/simple; bh=bYbDG14TjwlkbMlXcK5doweq0ODCdogjsd0q8OtcKMw=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=rGTfzfipfQQSR481CMLnRTTFtxrrR2KTJptTOvBjpklZiABnc328nYa6M64M7hNr95omqrs6jIDUEym3EuJ5RM4pjHHupxaE+z5FLQ5ovI7q5ypHTfa0RJpi5YXpBEEMaNIuoQ7yA7uso89XZNhzcNZJxXTcLavg/lWFXMjzCa8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--ackerleytng.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=2gC/B1Hs; arc=none smtp.client-ip=209.85.210.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--ackerleytng.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="2gC/B1Hs" Received: by mail-pf1-f202.google.com with SMTP id d2e1a72fcca58-7b89ee2c1a4so6834195b3a.2 for ; Mon, 17 Nov 2025 14:47:18 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1763419638; x=1764024438; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=IgOprM20p142HerI0wr78gS0iVMLCiuLJeQSKJuE034=; b=2gC/B1HsjoJc2YS+TwlWHjtzvPYJ8fc26b4l2ukDVqoK76fkiFPLVBeu7gDe5ZlflW va83tswUTgZNJB70ITt+C+Wh3/4a30eHwqwXsXe/SbT/On/R79Oxj1GzBoDp6TA9jSv4 uTmj9vsHu4wHnQVCpvXNAxMmL4uG/enA3z3qkTKlT1RkWCGAqVXfC0/+UJcwLX4Q/vUd bocS0lmQ1oCcWscn7HRIYHBFg2wDoaIp9GZP+tYFWwqHKlomOMVyPfRye32xMu5dH5Al 64CDTPVJcpJjpsRG9VhqyEt1PzxroenjEuTKTZPTkNW0DB6m5Zk6V+lzf7F1RPb2SerQ UW+Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763419638; x=1764024438; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=IgOprM20p142HerI0wr78gS0iVMLCiuLJeQSKJuE034=; b=lvlE+qzK+lcfwG0g++UbrzxLU3lJqFodeOg2J8ISS/srTLr1qJ5JhOUnjA6ZDlGgfJ B651yWu1QBEtj6hXeKxz5sPVxg3pz8eTAzD3qGsHJvJ6ZFl895Z9iKWVt3daQoDBqbgj 2dlbuHfwsR7NdCRS5fK/TPmrft6Vre5gn8MJD6qMOmfFH34D1mbuXep3YQ5ePft0DR16 0SQ6l16mRAPWukoJ0+nAPXryqz6kXkpRKvUHhL6n8Qzt81aWphNnneOeIWRYzOwKoRMd STKCoSYa08vJ3GUznmS8v8ZGVq49ovwnWtBRGPzS0doZ78rJGTAd01m5mmkXRvYheNgV yKqQ== X-Forwarded-Encrypted: i=1; AJvYcCXfTgHr1rk2qjiDPskBf3B8YIPYlAwx+BufKE4Uxu7GKPK4s47XKTllC201eDeWbXUDgDCbigYnAAWQDkQ=@vger.kernel.org X-Gm-Message-State: AOJu0YyFDFxYEainadgV9MrkNbO1Kov1BBWlc7LKe7JnFxfMYoM6sKwk lBqC5YlEWRzgptedplR2VZB+s83WFkR8MlXfqg4tFXyKyyCxsTliX2ulSFQ4QudwtEjTgvcH4Lw Ba1D8ussTzywROAlbTrSWvcXMuQ== X-Google-Smtp-Source: AGHT+IFt4bVWCbvV/lEzgpQt0fY3yUVaqZMHxZy+py5k3Obvyp7sDCutsUiYmrIPPvg3OqxNSYChRny0dADI/4XOEw== X-Received: from pgcz6.prod.google.com ([2002:a63:7e06:0:b0:bbe:55e3:6800]) (user=ackerleytng job=prod-delivery.src-stubby-dispatcher) by 2002:a05:6a20:a10a:b0:344:97a7:8c5c with SMTP id adf61e73a8af0-35ba2692141mr16860636637.48.1763419638413; Mon, 17 Nov 2025 14:47:18 -0800 (PST) Date: Mon, 17 Nov 2025 14:46:59 -0800 In-Reply-To: <20251117224701.1279139-1-ackerleytng@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251117224701.1279139-1-ackerleytng@google.com> X-Mailer: git-send-email 2.52.0.rc1.455.g30608eb744-goog Message-ID: <20251117224701.1279139-3-ackerleytng@google.com> Subject: [RFC PATCH 2/4] XArray: Update xas_split_alloc() to allocate enough nodes to split large entries From: Ackerley Tng To: willy@infradead.org, akpm@linux-foundation.org, linux-fsdevel@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: david@redhat.com, michael.roth@amd.com, vannapurve@google.com, Ackerley Tng Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The xas_split_alloc() function was previously limited in its ability to handle splits for large entries, specifically those requiring the XArray's height to increase by more than one level. It contained a WARN_ON for such cases and only allocated nodes for a single level of the tree. Introduce a new helper function, __xas_alloc_nodes(), to centralize the node allocation logic. Update xas_split_alloc() to determine the total number of nodes required across all new levels, then use __xas_alloc_nodes() to allocate them. This change removes the previous limitation and allows xas_split_alloc() to allocate enough nodes to support splitting for arbitrarily large entries. Signed-off-by: Ackerley Tng --- lib/xarray.c | 52 ++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 36 insertions(+), 16 deletions(-) diff --git a/lib/xarray.c b/lib/xarray.c index 636edcf014f1..b7c44a75bb03 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1028,6 +1028,27 @@ static void __xas_init_node_for_split(struct xa_stat= e *xas, } } +static void __xas_alloc_nodes(struct xa_state *xas, unsigned int num_nodes= , gfp_t gfp) +{ + struct xa_node *node; + unsigned int i; + + for (i =3D 0; i < num_nodes; ++i) { + node =3D kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp); + if (!node) + goto nomem; + + RCU_INIT_POINTER(node->parent, xas->xa_alloc); + xas->xa_alloc =3D node; + } + + return; + +nomem: + xas_destroy(xas); + xas_set_err(xas, -ENOMEM); +} + /** * xas_split_alloc() - Allocate memory for splitting an entry. * @xas: XArray operation state. @@ -1046,28 +1067,27 @@ void xas_split_alloc(struct xa_state *xas, void *en= try, unsigned int order, gfp_t gfp) { unsigned int sibs =3D (1 << (order % XA_CHUNK_SHIFT)) - 1; + unsigned int shift =3D order - (order % XA_CHUNK_SHIFT); + unsigned int level_nodes; + unsigned int nodes =3D 0; - /* XXX: no support for splitting really large entries yet */ - if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT <=3D order)) - goto nomem; - if (xas->xa_shift + XA_CHUNK_SHIFT > order) + if (shift <=3D xas->xa_shift) return; - do { - struct xa_node *node; + shift -=3D XA_CHUNK_SHIFT; - node =3D kmem_cache_alloc_lru(radix_tree_node_cachep, xas->xa_lru, gfp); - if (!node) - goto nomem; + level_nodes =3D sibs + 1; + for (;;) { + nodes +=3D level_nodes; - RCU_INIT_POINTER(node->parent, xas->xa_alloc); - xas->xa_alloc =3D node; - } while (sibs-- > 0); + if (shift =3D=3D xas->xa_shift) + break; - return; -nomem: - xas_destroy(xas); - xas_set_err(xas, -ENOMEM); + nodes *=3D XA_CHUNK_SIZE; + shift -=3D XA_CHUNK_SHIFT; + } + + __xas_alloc_nodes(xas, nodes, gfp); } EXPORT_SYMBOL_GPL(xas_split_alloc); -- 2.52.0.rc1.455.g30608eb744-goog From nobody Tue Dec 2 02:51:15 2025 Received: from mail-pl1-f202.google.com (mail-pl1-f202.google.com [209.85.214.202]) (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 D80033446C4 for ; Mon, 17 Nov 2025 22:47:20 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763419643; cv=none; b=ZD6/egW0UxIdvVLRgLOfE1yAZJzFF+ksPwNf5L/Jwb6U0EZKIzkICilws2GyG04MIzShYyXk3AYdPqLsbPjqfF7uH+2OeEYCN6YlcRsw3x4kdMuUElhAM4YaeGsykzCiN47c8piC7SRFg81GBGXZyVnYIobjGOqWaQnAjOwEbZ0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763419643; c=relaxed/simple; bh=rm96RSIZb4LTBvdrh7YmVYysakvIeRYfKKwfcyCMsaM=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=squLeOYuzCc3QlDwpFzPBFDunrNpS+yBJoxys9MGsL2TZwCOF518Mlun8qEp6R8L3kFS84oFL8KSCppdmUCBBV1IpVowfl4KoNVQwH4OUTxXT/tp0xQEtlCZeWlioREnUFLt/Z9FGyi7Jp0jcrLNeaE0Gq6VTylrF0A5q4lEQOk= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--ackerleytng.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=c0Fotxn3; arc=none smtp.client-ip=209.85.214.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--ackerleytng.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="c0Fotxn3" Received: by mail-pl1-f202.google.com with SMTP id d9443c01a7336-2955555f73dso53331765ad.0 for ; Mon, 17 Nov 2025 14:47:20 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1763419640; x=1764024440; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=h49/4ez8nB53RwngFZBAQKZZnMeHtus1TaIAc+Tmfyk=; b=c0Fotxn336osBdfMC25aWx0+mzKseoAmoIBsxrkeZMfxrC/n8NnOVangr+fOi5K3F2 2E5CcegaucEoDd+htJcqn4nc/Tgh4pTqA24ecaNrOdi/xayAmbcKrxylx6u95ePkSJkO ucYYAxKJRFHhex2yKwUZeSqnsKs9KAXFCrrqR3w94YFAhOkRQkrOkhGcx8yG6YZUaNSy ujN6oulyt9LM3KDQHBkmUWbcpDp84/TBF4xxnuGTRwHUGWXMyTGW4avwHgaWl4dy5pi3 sphe1LP5e4mdP4DznX/wcKxAgFcD5ATuCmU50A3KogbEUvE0W2EBP2pExe1u41sOLlsM HBMw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763419640; x=1764024440; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=h49/4ez8nB53RwngFZBAQKZZnMeHtus1TaIAc+Tmfyk=; b=tpBfNuma9bwRk1a3/gKyT1SQimo2v8DaJmkoZ1aYYXM84H14HMG3Kwexvrn45Q8Qik ojh5Z9M51iT7zNSyek4pbuOmJEPecALwgnrjbYqs9OrFj6l0K8bn9Vt/PS0XE4oz7goz rJGxkhbT8ubngTY5Tq4Z7XIAaZZoZxeXqwWtUD6I5vpmKy7E3KF+nBfOwqaqLXLoyEVQ aMFf8/lIn/i9Q9lUyl65gZOeuJOV1icNS/b9pqc3Cy1rrYPY6Qa8AU6UTxGUFSaSEHNW F2OlTUVweWKVcoQxwx2dvcud9ssmLZLzzoLkYMVziJztueduz8LQBPXnuw33z304xIBK sWxA== X-Forwarded-Encrypted: i=1; AJvYcCVMgcvWF/JuN7iIl0fHJlEODb/kQjVzQTmXpzQMLtX/71/tKzOgM9Psivdr6WE0+IFvIOEXsjOSOetD8LM=@vger.kernel.org X-Gm-Message-State: AOJu0YzGlpipQYOeYHar/BwbqD9ereO3R6Aah6dHLuygqamKnLc9DXW1 o/idtzfybycTDfS5negsTvlKX4l6Wz8M+Ti1PJq0GXo5M9IGCh6WUv5dMsa96hNbDm4eX7rth6U TjBkil6YPaxz+IVYGF1tuiQM49w== X-Google-Smtp-Source: AGHT+IHWA3n4fRLuQQDbvqes2g4fdvBQx26NqKHJhSXAuqe2xxxf8ttHYK65SO+WREJuuBGajBPt+OclghSCG+uvxQ== X-Received: from plok14.prod.google.com ([2002:a17:903:3bce:b0:297:ecd0:777a]) (user=ackerleytng job=prod-delivery.src-stubby-dispatcher) by 2002:a17:902:f691:b0:295:6a9:cb62 with SMTP id d9443c01a7336-2986a73b4a7mr170440805ad.35.1763419639915; Mon, 17 Nov 2025 14:47:19 -0800 (PST) Date: Mon, 17 Nov 2025 14:47:00 -0800 In-Reply-To: <20251117224701.1279139-1-ackerleytng@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251117224701.1279139-1-ackerleytng@google.com> X-Mailer: git-send-email 2.52.0.rc1.455.g30608eb744-goog Message-ID: <20251117224701.1279139-4-ackerleytng@google.com> Subject: [RFC PATCH 3/4] XArray: Support splitting for arbitrarily large entries From: Ackerley Tng To: willy@infradead.org, akpm@linux-foundation.org, linux-fsdevel@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: david@redhat.com, michael.roth@amd.com, vannapurve@google.com, Ackerley Tng Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" The existing xas_split() function primarily supports splitting an entry into multiple siblings within the current node, or creating child nodes for one level below. It does not handle scenarios where the requested split order requires wiring up multiple levels of new intermediate nodes to form a deeper subtree. This limits the xas_split() from splitting arbitrarily large entries. This commit extends xas_split() to build subtrees of XArray nodes and then set these subtrees as children of the node where the split is requested. Signed-off-by: Ackerley Tng --- I had a recursive implementation which I believe was easier to understand, = but I went with a iterative implementation using a stack because I was concerned = about stack depths in the kernel. Let me know if the recursive implementation is preferred! Feedback is always appreciated, and I'd specifically like feedback on: + RCU-related handling + Handling of xas_update() calls + Use of node_set_marks() - can/should that be refactored to be node-focuse= d, rather than in some cases also updating the child? + Can/should xas_split_alloc() read entry using xas_load(), rather than rel= y on void *entry passed as an argument? lib/xarray.c | 158 +++++++++++++++++++++++++++++++++++++++------------ 1 file changed, 121 insertions(+), 37 deletions(-) diff --git a/lib/xarray.c b/lib/xarray.c index b7c44a75bb03..6fdace2e73df 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1105,52 +1105,136 @@ EXPORT_SYMBOL_GPL(xas_split_alloc); void xas_split(struct xa_state *xas, void *entry, unsigned int order) { unsigned int sibs =3D (1 << (order % XA_CHUNK_SHIFT)) - 1; - unsigned int offset, marks; + struct xa_node *node_to_split; + unsigned int offset_to_split; + struct xa_node *stack; struct xa_node *node; - void *curr =3D xas_load(xas); - int values =3D 0; + unsigned int offset; + unsigned int marks; + unsigned int i; + void *sibling; - node =3D xas->xa_node; - if (xas_top(node)) + xas_load(xas); + node_to_split =3D xas->xa_node; + if (xas_top(node_to_split)) return; - marks =3D node_get_marks(node, xas->xa_offset); + marks =3D node_get_marks(node_to_split, xas->xa_offset); - offset =3D xas->xa_offset + sibs; - do { - if (xas->xa_shift < node->shift) { - struct xa_node *child =3D xas->xa_alloc; - - xas->xa_alloc =3D rcu_dereference_raw(child->parent); - __xas_init_node_for_split(xas, child, entry); - child->shift =3D node->shift - XA_CHUNK_SHIFT; - child->offset =3D offset; - child->count =3D XA_CHUNK_SIZE; - child->nr_values =3D xa_is_value(entry) ? - XA_CHUNK_SIZE : 0; - RCU_INIT_POINTER(child->parent, node); - node_set_marks(node, offset, child, xas->xa_sibs, - marks); - rcu_assign_pointer(node->slots[offset], - xa_mk_node(child)); - if (xa_is_value(curr)) - values--; - xas_update(xas, child); + /* Horizontal split: just fill in values in existing node. */ + if (node_to_split->shift =3D=3D xas->xa_shift) { + offset =3D xas->xa_offset; + + for (i =3D offset; i < offset + sibs + 1; i++) { + if ((i & xas->xa_sibs) =3D=3D 0) { + node_set_marks(node_to_split, i, NULL, 0, marks); + rcu_assign_pointer(node_to_split->slots[i], entry); + + sibling =3D xa_mk_sibling(i); + } else { + rcu_assign_pointer(node_to_split->slots[i], sibling); + } + } + + xas_update(xas, node_to_split); + return; + } + + /* + * Vertical split: build tree bottom-up, so that on any RCU lookup (on + * the original tree), the tree is consistent. + */ + offset_to_split =3D get_offset(xas->xa_index, node_to_split); + stack =3D NULL; + offset =3D 0; + for (;;) { + unsigned int next_offset; + + if (stack && + stack->shift =3D=3D node_to_split->shift - XA_CHUNK_SHIFT && + stack->offset =3D=3D offset_to_split + sibs) + break; + + if (stack && stack->offset =3D=3D XA_CHUNK_SIZE - 1) { + unsigned int child_shift; + + node =3D xas->xa_alloc; + xas->xa_alloc =3D rcu_dereference_raw(node->parent); + + child_shift =3D stack->shift; + for (i =3D 0; i < XA_CHUNK_SIZE; i++) { + struct xa_node *child =3D stack; + + stack =3D child->parent; + + node_set_marks(node, child->offset, NULL, 0, marks); + + RCU_INIT_POINTER(child->parent, node); + RCU_INIT_POINTER(node->slots[child->offset], xa_mk_node(child)); + } + + node->array =3D xas->xa; + node->count =3D XA_CHUNK_SIZE; + node->nr_values =3D 0; + node->shift =3D child_shift + XA_CHUNK_SHIFT; + node->offset =3D 0; + if (node->shift =3D=3D node_to_split->shift - XA_CHUNK_SHIFT) + node->offset =3D offset_to_split; + if (stack && stack->shift =3D=3D node->shift) + node->offset =3D stack->offset + 1; + + next_offset =3D 0; + + xas_update(xas, node); } else { - unsigned int canon =3D offset - xas->xa_sibs; + node =3D xas->xa_alloc; + xas->xa_alloc =3D rcu_dereference_raw(node->parent); - node_set_marks(node, canon, NULL, 0, marks); - rcu_assign_pointer(node->slots[canon], entry); - while (offset > canon) - rcu_assign_pointer(node->slots[offset--], - xa_mk_sibling(canon)); - values +=3D (xa_is_value(entry) - xa_is_value(curr)) * - (xas->xa_sibs + 1); + for (i =3D 0; i < XA_CHUNK_SIZE; i++) { + if ((i & xas->xa_sibs) =3D=3D 0) { + node_set_marks(node, i, NULL, 0, marks); + RCU_INIT_POINTER(node->slots[i], entry); + + sibling =3D xa_mk_sibling(i); + } else { + RCU_INIT_POINTER(node->slots[i], sibling); + } + } + + node->array =3D xas->xa; + node->count =3D XA_CHUNK_SIZE; + node->nr_values =3D xa_is_value(entry) ? XA_CHUNK_SIZE : 0; + node->shift =3D xas->xa_shift; + node->offset =3D offset; + if (node->shift =3D=3D node_to_split->shift - XA_CHUNK_SHIFT) + node->offset =3D offset_to_split; + if (stack && stack->shift =3D=3D node->shift) + node->offset =3D stack->offset + 1; + + next_offset =3D offset + 1; } - } while (offset-- > xas->xa_offset); - node->nr_values +=3D values; - xas_update(xas, node); + node->parent =3D stack; + stack =3D node; + + offset =3D next_offset; + } + + /* Combine all the new nodes on the stack into node_to_split. */ + for (i =3D 0; i < sibs + 1; i++) { + node =3D stack; + stack =3D node->parent; + + node_set_marks(node_to_split, node->offset, NULL, 0, marks); + + rcu_assign_pointer(node->parent, node_to_split); + rcu_assign_pointer(node_to_split->slots[node->offset], xa_mk_node(node)); + } + + WARN_ON(stack); + + node_to_split->nr_values -=3D xa_is_value(entry) ? sibs + 1 : 0; + xas_update(xas, node_to_split); } EXPORT_SYMBOL_GPL(xas_split); -- 2.52.0.rc1.455.g30608eb744-goog From nobody Tue Dec 2 02:51:15 2025 Received: from mail-pl1-f201.google.com (mail-pl1-f201.google.com [209.85.214.201]) (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 2E51134E768 for ; Mon, 17 Nov 2025 22:47:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763419644; cv=none; b=EaR8x0xM3lCdV/NPHdLgIZfYi870WvkCcNUEjwxAE9WgKq8qULgF1YWiLb16g401VbbcIiy6ciy2MtKxON8nY1CW0Qa+3PPojFhyJepoF85tNBtgwLpcUZQmzpK0vgyDDt/TOhmLChN204ISSKCQtfTiXIVOjF12gOQT/DSA8Ac= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1763419644; c=relaxed/simple; bh=KTa8/7CrfmjBWMkUG3DA+uVzaVnpuiI3UNQUMiml6/A=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=BLrVb8S7aNk7sCCJ3oAdRhX3UZganzNjd6e2pmVcKr6cX9Zym/fzKhU1BqkTs5o2rxhEnC7erN3FRs9Yb4N57P+qPdwllajyz7KfTri9bfOmSO5vTnsxTUCLq9QBaVfJQRYgBI4WfRORs21xONDO/ettuHf9F50jHIF7io+0B0I= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--ackerleytng.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=0+3ItJq9; arc=none smtp.client-ip=209.85.214.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--ackerleytng.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="0+3ItJq9" Received: by mail-pl1-f201.google.com with SMTP id d9443c01a7336-2956cdcdc17so57527145ad.3 for ; Mon, 17 Nov 2025 14:47:21 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1763419641; x=1764024441; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=FFDZWRBWGeSJJ18PHJTmScz5mdF08U3XJWNOIdU9ii8=; b=0+3ItJq9FyJ60mFUfdaAHLFMZp4mUxXRmD9kDWZrsb50+QOry00z3s+siHs0Vt2hpj fgFRC3Q8+5Uxdj1zSk7cfr27JlZGGb63SDxJBNBv4UaQmzPAM/uXGT/Q5U0zUnvzWB81 BD65zN5NjxszyEuPJAVpHlxP3+rMENcdnScTd5ogAnKourgi0EXFAYRpmvBUsmIR+oWv KW1p7IscOEd+cs61raL7vQb6qsxYfrYLbb1Xfmegh2ia4eSjXndMVJtEFzFiA3htPRkF IkPc959Rhc55QTNMnmXf+1Jc8W+pS12R+6Y3bmSc55BcYsXKH8Kbg44XzpenbRe3Yn4B WnDg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1763419641; x=1764024441; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=FFDZWRBWGeSJJ18PHJTmScz5mdF08U3XJWNOIdU9ii8=; b=VHzWi7cMA6HChatSkzEGnMhVi8a1PgZp17tujUAfba132UyppwwR0j8PA8Gv5j78lE P55Yf9t3tRxbV/ipHVCf0rk6urZuyuPOi70YI5Q09FCH5cK16CQYbusp8eyiNzSA2iGw HAI8+Ta1dc5NnT5RicDv0hALqWHxdZzz+FFN5qMxmHzBVuMMYlTjBEbKOwmVYNoOzz7E dGGMiRcIwgXgLhzNgOVYq25NkLGCh50BqLaxhCJgMP3vvg8lPGTZTyVUEvBSSdeS28FD +WZjeEOquT+RXf46/B0GmpwvAx1c39ExZdaLn8ofadDjnszPACluvsJVxei6U/K36Fbd zl2Q== X-Forwarded-Encrypted: i=1; AJvYcCXrfT9/I+6EwhOSD5lymil7O0zzbA3085y7ElbiX4Y0OlYBOc7A/oNoTRXMSouIn7/DZdXMIR0uJ0yu+p4=@vger.kernel.org X-Gm-Message-State: AOJu0YwQeGuqY05Q0r3DCqjA5DhIui5Yl4JqccWBPqdijBGGjSFE8nGb CUYxTPYGZNCzSTyUm93JCdUflRoA5NSGqOhegc+zsk3RM6jM1CTg+Y1XGx+uDisOSgPbqLsLLvZ 8r3qgeOe3PhmIvEdniwIiSmH+iQ== X-Google-Smtp-Source: AGHT+IFUtNOkJGI+3slVxFGeNNElaZyayySLSHWAkJnaSwQ34c9nCY94UPN7a599kL2+pa7XbABtWWuQu1NQqX5/mw== X-Received: from plok14.prod.google.com ([2002:a17:903:3bce:b0:297:ecd0:777a]) (user=ackerleytng job=prod-delivery.src-stubby-dispatcher) by 2002:a17:902:f78c:b0:295:ceaf:8d76 with SMTP id d9443c01a7336-2986a75010cmr143554585ad.47.1763419641381; Mon, 17 Nov 2025 14:47:21 -0800 (PST) Date: Mon, 17 Nov 2025 14:47:01 -0800 In-Reply-To: <20251117224701.1279139-1-ackerleytng@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20251117224701.1279139-1-ackerleytng@google.com> X-Mailer: git-send-email 2.52.0.rc1.455.g30608eb744-goog Message-ID: <20251117224701.1279139-5-ackerleytng@google.com> Subject: [RFC PATCH 4/4] XArray: test: Increase split order test range in check_split() From: Ackerley Tng To: willy@infradead.org, akpm@linux-foundation.org, linux-fsdevel@vger.kernel.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: david@redhat.com, michael.roth@amd.com, vannapurve@google.com, Ackerley Tng Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" Expand the range of order values for check_split_1() from 2 * XA_CHUNK_SHIFT to 4 * XA_CHUNK_SHIFT to test splitting beyond 2 levels. Separate the loops for check_split_1() and check_split_2() calls, since xas_try_split() does not yet support splitting beyond 2 levels. Signed-off-by: Ackerley Tng --- lib/test_xarray.c | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 42626fb4dc0e..fbdf647e4ef8 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1905,12 +1905,16 @@ static noinline void check_split(struct xarray *xa) XA_BUG_ON(xa, !xa_empty(xa)); - for (order =3D 1; order < 2 * XA_CHUNK_SHIFT; order++) { + for (order =3D 1; order < 4 * XA_CHUNK_SHIFT; order++) { for (new_order =3D 0; new_order < order; new_order++) { check_split_1(xa, 0, order, new_order); check_split_1(xa, 1UL << order, order, new_order); check_split_1(xa, 3UL << order, order, new_order); + } + } + for (order =3D 1; order < 2 * XA_CHUNK_SHIFT; order++) { + for (new_order =3D 0; new_order < order; new_order++) { check_split_2(xa, 0, order, new_order); check_split_2(xa, 1UL << order, order, new_order); check_split_2(xa, 3UL << order, order, new_order); -- 2.52.0.rc1.455.g30608eb744-goog