From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from smtp.kernel.org (aws-us-west-2-korg-mail-alma10-1.taild15c8.ts.net [100.103.45.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 722DE37AA9A; Fri, 7 Aug 2026 15:00:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=100.103.45.18 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786114832; cv=none; b=I6O8L++o/B5s5N7F+8wpvbFYL/wLyA7cQ3d0rz7gl15eGBQNzlZ+RhTUXyL/COn2b8KLYOR2cfxO4RtmvP6Kvxu8c4YNU1fQ3TR1/FYKfcoGGqoltaBoSUls47FJ9jF3BCh8g6zAEdj/nAj097bc63zTlme/HB3RwUx0j2MrcOQ= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1786114832; c=relaxed/simple; bh=xKTkBTospZmyRwgOxzuyD/xNLqEqMoMFzknhCns3rz8=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version; b=HcGPeiLKty8h5H4xTpF6nLJ7H8mXQ7AhMa9R5kLZRvrVHsqbRR3LiaLu6El5WS6HGr2mc9tWSyjWc+IjLxWBrbo3ZNKwmN0mPLCLAe5GlCtf307acShOVpU59zg4a+Zw2qyWiriAZ0c7JyO+ZGsCTYkUorGu16L/lnPYgqujySk= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linuxfoundation.org header.i=@linuxfoundation.org header.b=AD+8aRIQ; arc=none smtp.client-ip=100.103.45.18 Authentication-Results: smtp.subspace.kernel.org; dkim=pass (1024-bit key) header.d=linuxfoundation.org header.i=@linuxfoundation.org header.b="AD+8aRIQ" Received: by smtp.kernel.org (Postfix) with ESMTPSA id C23191F000E9; Fri, 7 Aug 2026 15:00:30 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=linuxfoundation.org; s=korg; t=1786114831; bh=geDS6vaCSk/5w//Wt4QAHmSsVtc493+xBeZCXKh6drM=; h=From:To:Cc:Subject:Date:In-Reply-To:References; b=AD+8aRIQaTbAHfa28pLwAtvjdiclyP38WCx7dtoznXD/XPFGF4ubY8IZ4QnoiwURr NcaaSd7zs4UVy9xXSt49BLZ8S94SjN4D7+5zSrdKS6jIe17m66PqvR+U5viFpWle5U jrlGD2NxFsatLAEfgW4wZb+akRD65y/rOrzR3UuY= From: Greg Kroah-Hartman To: stable@vger.kernel.org Cc: Greg Kroah-Hartman , patches@lists.linux.dev, Michael Bommarito , Jarkko Sakkinen , Sasha Levin Subject: [PATCH 6.18 046/396] assoc_array: trim the final shortcut word using the current chunk end Date: Fri, 7 Aug 2026 16:33:26 +0200 Message-ID: <20260807143425.260442627@linuxfoundation.org> X-Mailer: git-send-email 2.55.0 In-Reply-To: <20260807143424.272339768@linuxfoundation.org> References: <20260807143424.272339768@linuxfoundation.org> User-Agent: quilt/0.69 X-stable: review X-Patchwork-Hint: ignore Precedence: bulk X-Mailing-List: patches@lists.linux.dev List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: 8bit 6.18-stable review patch. If anyone has any objections, please let me know. ------------------ From: Michael Bommarito [ Upstream commit a82c8a05e86f3f84e09698f65b4515b5d04633f6 ] assoc_array_walk() masks off the bits past shortcut->skip_to_level in the word that contains skip_to_level, gated on round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > skip_to_level. That guard is wrong in two opposite ways: - When sc_level is word-aligned (every word after the first) round_up() is a no-op, so the guard is sc_level > skip_to_level and never fires for the word that holds skip_to_level. A shortcut that spans more than one word and ends in the middle of its last word leaves that word untrimmed, and its stale high bits leak into the dissimilarity word and can steer the walk down the wrong descendant. - When sc_level is unaligned (the first word) and skip_to_level sits on the next chunk boundary, sc_level + CHUNK would exceed skip_to_level and fire the trim with shift = skip_to_level & CHUNK_MASK == 0, which clears the whole dissimilarity word and makes a differing shortcut compare equal. Use the end of the chunk that contains sc_level instead: skip_to_level < round_down(sc_level, CHUNK) + CHUNK For an aligned sc_level whose word holds skip_to_level this now fires (the first bug); for an unaligned sc_level with skip_to_level on the following boundary it does not, so shift is never 0 when the branch runs and the trim never clears the whole word. Fixes: 3cb989501c26 ("Add a generic associative array implementation.") Assisted-by: Claude:claude-opus-4-8 Signed-off-by: Michael Bommarito Reviewed-by: Jarkko Sakkinen Tested-by: Jarkko Sakkinen Link: https://lore.kernel.org/r/20260719161505.2423935-4-michael.bommarito@gmail.com Signed-off-by: Jarkko Sakkinen Signed-off-by: Sasha Levin --- lib/assoc_array.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/lib/assoc_array.c b/lib/assoc_array.c index 388e656ac9743..01619e88a52c9 100644 --- a/lib/assoc_array.c +++ b/lib/assoc_array.c @@ -255,7 +255,8 @@ assoc_array_walk(const struct assoc_array *array, sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT]; dissimilarity = segments ^ sc_segments; - if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) { + if (shortcut->skip_to_level < round_down(sc_level, + ASSOC_ARRAY_KEY_CHUNK_SIZE) + ASSOC_ARRAY_KEY_CHUNK_SIZE) { /* Trim segments that are beyond the shortcut */ int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK; dissimilarity &= ~(ULONG_MAX << shift); -- 2.53.0