From nobody Tue Dec 2 03:00:11 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