Received-SPF: softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) client-ip=23.128.96.19;
From:   Stephen Brennan <stephen.s.brennan@oracle.com>
To:     David Howells <dhowells@redhat.com>, torvalds@linux-foundation.org
Cc:     stable@vger.kernel.org, Jarkko Sakkinen <jarkko@kernel.org>,
        Andrew Morton <akpm@linux-foundation.org>,
        keyrings@vger.kernel.org, dhowells@redhat.com,
        linux-kernel@vger.kernel.org
Subject: Re: [PATCH] assoc_array: Fix BUG_ON during garbage collect
In-Reply-To: <165295023086.3361286.8662079860706628540.stgit@warthog.procyon.org.uk>
References: <165295023086.3361286.8662079860706628540.stgit@warthog.procyon.org.uk>
Date:   Wed, 01 Jun 2022 14:59:47 -0700
Message-ID: <8735go11v0.fsf@stepbren-lnx.us.oracle.com>
Content-Type: text/plain
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?z7tigjCRxFvXy6prxpWWqzHdHlVZMDrKeiP1EOV239PjbEVM/oCsvBrPyOXY?=
 =?us-ascii?Q?yfhY79O2r/jg2knJ0X9sGdapmQ8U9whtuQIMiCPEGjE/iBZ/GCdSabyiBV36?=
 =?us-ascii?Q?WjuFVSbdg+Y2FuXXD54CHCST1tOQKtJfLKT70R9IiS8ZkTPikXaqMU87UYjE?=
 =?us-ascii?Q?w87VNhMUCHyxrkHV6e+EYla9/6lg8eILehQqqVcnBDEUQEblyMgaZxqs0yE4?=
 =?us-ascii?Q?X096DwY6jizQAbfBR3E/Zpc/GqNSXt3FdGG0mCUBAJwAseMhgSmGOcsOXOa+?=
 =?us-ascii?Q?lMMvPngzma/oyMORUJZ7vLzrQNmDPbYqCdA6sJ66Hx+MokpsGP+ELVxU8I9Z?=
 =?us-ascii?Q?GmQRIpGKG2GTsIjEQYAupxQy9m7+RMgnNfS9cwPhhBgdkPGLfk3TS56o9oE2?=
 =?us-ascii?Q?4kF8ZrK2OmEIHkScoPw8ICqQ23i0u+RpaICYGHcdEd1KXThq/u9oJCDSSXqq?=
 =?us-ascii?Q?1f0NKelRTqf3OFcEQgDTqmuF6Ywu8vMEOifiMKIS7SuT6Xiq4XFfEByG38HR?=
 =?us-ascii?Q?2i480bA7DLdZ3zo1hrSNpIq0nq9excGsiLZm3bt6KPdlXjcD/UkFnsAqLuJO?=
 =?us-ascii?Q?g4vOa3iFFxa/TE94NYLt0pHuMVIQrJ8OV2UIIaLPnjbNuQ/DijRzrtHEHQ2C?=
 =?us-ascii?Q?udueLNBFy2RSfp4xIU3Pd625j6wL3ymt15LHvQnLqVe1gOTL15C7RouqSD0w?=
 =?us-ascii?Q?hIxidCzQ/9tWEW07dcV20Q3PejRjOGsEIcrnkQLmafXyLShlHn20VlN0YLZ4?=
 =?us-ascii?Q?U52/8QaSvZFbMeqFQYp1EmNksN5kwIhKYT8VOAqePe7nvL/iXMIus0t9FkR0?=
 =?us-ascii?Q?sR+YZhmcnwlRLWzdRoS+/v2S1ahywtCJtrkJmVFhXAlpjtX+EuMOp0KAssuX?=
 =?us-ascii?Q?j4/hxlN6saCPR+B+/Nvx7pXpRTgnqLz7zxLKBScfzj4YKxtauuHmOwNyDkk0?=
 =?us-ascii?Q?9SGdL5RPp46nq2RzDCFUsr8+m26y4Mckeu7v8+wtFrB6YURQHtJKlC9Z7BPx?=
 =?us-ascii?Q?nUDPEF2hvhcdaeVjP10PSXoe1a/hcAKYRq20Q4PitdFRDpS2hTAzvAgaLIEN?=
 =?us-ascii?Q?dvH8M9vHrUawI0QzL9yfmwSTVPp/2MPkvtm5IClm4jFd0Wvh/c8joYyf4Xfe?=
 =?us-ascii?Q?ejSNsoJ08szSggs4qo9M59o1tHyhme9PXCq+J5Y/6G6gYxoSJQ3YDGh1Pp1E?=
 =?us-ascii?Q?jW8Dcx5qTeiX8SzdxUttVARV+lCQnwpDyLSzweJC9C1HmvBM883dxkHu4D7V?=
 =?us-ascii?Q?AC4tvk5bpm6eOHSwgllnJaaQaj/4/nwwBZn8vkoN9LOgXCwYmvjVxZ2CeeOU?=
 =?us-ascii?Q?3lGkgTiJ7VUfC3YAjyIta9fCEeaNKs7y+a7h7iUw8hHDPZQWl+d9ASl2gyuq?=
 =?us-ascii?Q?8VXHFIBgClWMYki+zZ3Xi9kQLh1V/wHIQ83Ugi2gyhEZGyIm8Ik71NlDEJFB?=
 =?us-ascii?Q?PQtIqaJNFgkzYIa4EstWWJW2HXPrb959QjuktyuzzcdbO6siYRzlja49Z8NA?=
 =?us-ascii?Q?dANYe2O+Nhwp6jv/YRO8rBPDCZy5BtzDKsDIqXCK26c08LmsdMx+tMDnUEwQ?=
 =?us-ascii?Q?6Bf6/0K5zJqEJoDbqbOtQJgm3+A65/UtG7kKqX3js3vGYNGJcW3yJuniPi37?=
 =?us-ascii?Q?DBnvPuHRLfZn4uonUGAZYJ54p4nozodUIspuNaFYY7m3+/8cqLLqQ58eVYOg?=
 =?us-ascii?Q?e62LN6OcItIs3fKX3mYcwPT1sl8vA/Sm7KfPoOmrP0ZyUsOmp7YulQymqUTC?=
 =?us-ascii?Q?UpfDKnvZY9UL5w8pdzx5uCgPFKCijEk=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 7444b9c1-bb33-4088-81fb-08da441a0cad
X-MS-Exchange-CrossTenant-AuthSource: MN2PR10MB4173.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 01 Jun 2022 21:59:50.1694
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: M/M7NH85RR9jYI6eXoiuUadwgyU3+5ziL3jkXnC7orVswUW68o6Nr5WZX8dYHbdj03H4Te1QtPM0GILjH90zPW9yYtD/hqCiZ695RbMtP/4=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY5PR10MB6012
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.517,18.0.874
 definitions=2022-06-01_08:2022-06-01,2022-06-01 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 spamscore=0 mlxlogscore=999
 phishscore=0 suspectscore=0 malwarescore=0 mlxscore=0 adultscore=0
 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2204290000 definitions=main-2206010087
X-Proofpoint-GUID: 5YlPiVfY1QwXo06vp1PmO9ZUv_GVlZ-h
X-Proofpoint-ORIG-GUID: 5YlPiVfY1QwXo06vp1PmO9ZUv_GVlZ-h
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,
	MAILING_LIST_MULTI,RDNS_NONE,SPF_HELO_NONE,T_SCC_BODY_TEXT_LINE
	autolearn=no autolearn_force=no version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
	lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

David Howells <dhowells@redhat.com> writes:
> From: Stephen Brennan <stephen.s.brennan@oracle.com>
>
> A rare BUG_ON triggered in assoc_array_gc:
>
>     [3430308.818153] kernel BUG at lib/assoc_array.c:1609!
>
> Which corresponded to the statement currently at line 1593 upstream:
>
>     BUG_ON(assoc_array_ptr_is_meta(p));
>
> Using the data from the core dump, I was able to generate a userspace
> reproducer[1] and determine the cause of the bug.
>
> [1]: https://github.com/brenns10/kernel_stuff/tree/master/assoc_array_gc
>
> After running the iterator on the entire branch, an internal tree node
> looked like the following:
>
>     NODE (nr_leaves_on_branch: 3)
>       SLOT [0] NODE (2 leaves)
>       SLOT [1] NODE (1 leaf)
>       SLOT [2..f] NODE (empty)
>
> In the userspace reproducer, the pr_devel output when compressing this
> node was:
>
>     -- compress node 0x5607cc089380 --
>     free=0, leaves=0
>     [0] retain node 2/1 [nx 0]
>     [1] fold node 1/1 [nx 0]
>     [2] fold node 0/1 [nx 2]
>     [3] fold node 0/2 [nx 2]
>     [4] fold node 0/3 [nx 2]
>     [5] fold node 0/4 [nx 2]
>     [6] fold node 0/5 [nx 2]
>     [7] fold node 0/6 [nx 2]
>     [8] fold node 0/7 [nx 2]
>     [9] fold node 0/8 [nx 2]
>     [10] fold node 0/9 [nx 2]
>     [11] fold node 0/10 [nx 2]
>     [12] fold node 0/11 [nx 2]
>     [13] fold node 0/12 [nx 2]
>     [14] fold node 0/13 [nx 2]
>     [15] fold node 0/14 [nx 2]
>     after: 3
>
> At slot 0, an internal node with 2 leaves could not be folded into the
> node, because there was only one available slot (slot 0). Thus, the
> internal node was retained. At slot 1, the node had one leaf, and was
> able to be folded in successfully. The remaining nodes had no leaves,
> and so were removed. By the end of the compression stage, there were 14
> free slots, and only 3 leaf nodes. The tree was ascended and then its
> parent node was compressed. When this node was seen, it could not be
> folded, due to the internal node it contained.
>
> The invariant for compression in this function is: whenever
> nr_leaves_on_branch < ASSOC_ARRAY_FAN_OUT, the node should contain all
> leaf nodes. The compression step currently cannot guarantee this, given
> the corner case shown above.
>
> To fix this issue, retry compression whenever we have retained a node,
> and yet nr_leaves_on_branch < ASSOC_ARRAY_FAN_OUT. This second
> compression will then allow the node in slot 1 to be folded in,
> satisfying the invariant. Below is the output of the reproducer once the
> fix is applied:
>
>     -- compress node 0x560e9c562380 --
>     free=0, leaves=0
>     [0] retain node 2/1 [nx 0]
>     [1] fold node 1/1 [nx 0]
>     [2] fold node 0/1 [nx 2]
>     [3] fold node 0/2 [nx 2]
>     [4] fold node 0/3 [nx 2]
>     [5] fold node 0/4 [nx 2]
>     [6] fold node 0/5 [nx 2]
>     [7] fold node 0/6 [nx 2]
>     [8] fold node 0/7 [nx 2]
>     [9] fold node 0/8 [nx 2]
>     [10] fold node 0/9 [nx 2]
>     [11] fold node 0/10 [nx 2]
>     [12] fold node 0/11 [nx 2]
>     [13] fold node 0/12 [nx 2]
>     [14] fold node 0/13 [nx 2]
>     [15] fold node 0/14 [nx 2]
>     internal nodes remain despite enough space, retrying
>     -- compress node 0x560e9c562380 --
>     free=14, leaves=1
>     [0] fold node 2/15 [nx 0]
>     after: 3
>
> Changes
> =======
> DH:
>  - Use false instead of 0.
>  - Reorder the inserted lines in a couple of places to put retained before
>    next_slot.
>
> ver #2)
>  - Fix typo in pr_devel, correct comparison to "<="
>
>
> Fixes: 3cb989501c26 ("Add a generic associative array implementation.")
> Cc: <stable@vger.kernel.org>
> Signed-off-by: Stephen Brennan <stephen.s.brennan@oracle.com>
> Signed-off-by: David Howells <dhowells@redhat.com>
> cc: Jarkko Sakkinen <jarkko@kernel.org>
> cc: Andrew Morton <akpm@linux-foundation.org>
> cc: keyrings@vger.kernel.org
> Link: https://lore.kernel.org/r/20220511225517.407935-1-stephen.s.brennan@oracle.com/ # v1
> Link: https://lore.kernel.org/r/20220512215045.489140-1-stephen.s.brennan@oracle.com/ # v2
> ---
>
>  lib/assoc_array.c |    8 ++++++++
>  1 file changed, 8 insertions(+)

Hi,

Just wanted to check on this patch as the 5.19 window closes. David, are
you planning on taking this through a particular tree, or is the ask for
Linus to pick it directly?

Thanks,
Stephen

>
> diff --git a/lib/assoc_array.c b/lib/assoc_array.c
> index 079c72e26493..ca0b4f360c1a 100644
> --- a/lib/assoc_array.c
> +++ b/lib/assoc_array.c
> @@ -1461,6 +1461,7 @@ int assoc_array_gc(struct assoc_array *array,
>  	struct assoc_array_ptr *cursor, *ptr;
>  	struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp;
>  	unsigned long nr_leaves_on_tree;
> +	bool retained;
>  	int keylen, slot, nr_free, next_slot, i;
>  
>  	pr_devel("-->%s()\n", __func__);
> @@ -1536,6 +1537,7 @@ int assoc_array_gc(struct assoc_array *array,
>  		goto descend;
>  	}
>  
> +retry_compress:
>  	pr_devel("-- compress node %p --\n", new_n);
>  
>  	/* Count up the number of empty slots in this node and work out the
> @@ -1553,6 +1555,7 @@ int assoc_array_gc(struct assoc_array *array,
>  	pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
>  
>  	/* See what we can fold in */
> +	retained = false;
>  	next_slot = 0;
>  	for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
>  		struct assoc_array_shortcut *s;
> @@ -1602,9 +1605,14 @@ int assoc_array_gc(struct assoc_array *array,
>  			pr_devel("[%d] retain node %lu/%d [nx %d]\n",
>  				 slot, child->nr_leaves_on_branch, nr_free + 1,
>  				 next_slot);
> +			retained = true;
>  		}
>  	}
>  
> +	if (retained && new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
> +		pr_devel("internal nodes remain despite enough space, retrying\n");
> +		goto retry_compress;
> +	}
>  	pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
>  
>  	nr_leaves_on_tree = new_n->nr_leaves_on_branch;