NetBSD Problem Report #54979

From ad@netbsd.org  Mon Feb 17 22:24:36 2020
Return-Path: <ad@netbsd.org>
Received: from mail.netbsd.org (mail.netbsd.org [199.233.217.200])
	(using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
	(Client CN "mail.NetBSD.org", Issuer "mail.NetBSD.org CA" (not verified))
	by mollari.NetBSD.org (Postfix) with ESMTPS id 63CD31A9213
	for <gnats-bugs@gnats.NetBSD.org>; Mon, 17 Feb 2020 22:24:36 +0000 (UTC)
Message-Id: <20200217222436.27AAD84D55@mail.netbsd.org>
Date: Mon, 17 Feb 2020 22:24:36 +0000 (UTC)
From: ad@netbsd.org
Reply-To: ad@netbsd.org
To: gnats-bugs@NetBSD.org
Subject: radixtree might misbehave if ENOMEM
X-Send-Pr-Version: 3.95

>Number:         54979
>Category:       kern
>Synopsis:       radixtree might misbehave if ENOMEM
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    ad
>State:          closed
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Mon Feb 17 22:25:00 +0000 2020
>Closed-Date:    Fri Apr 10 23:45:29 +0000 2020
>Last-Modified:  Fri Apr 10 23:45:29 +0000 2020
>Originator:     Andrew Doran
>Release:        NetBSD-current
>Organization:
	The NetBSD Project
>Environment:
NetBSD
Architecture: x86_64
Machine: amd64
>Description:
	maxv@ indicates on tech-kern that radixtree might screw up
	on ENOMEM, which would tally with failures exposed by syzbot.
>How-To-Repeat:
	Code inspection, intuition, syzbot.
>Fix:
	Yes please - start by inspecting the failure path.

>Release-Note:

>Audit-Trail:

Responsible-Changed-From-To: kern-bug-people->ad
Responsible-Changed-By: ad@NetBSD.org
Responsible-Changed-When: Mon, 17 Feb 2020 22:28:06 +0000
Responsible-Changed-Why:
yoink


From: Andrew Doran <ad@netbsd.org>
To: gnats-bugs@netbsd.org
Cc: 
Subject: Re: kern/54979 (radixtree might misbehave if ENOMEM)
Date: Sun, 15 Mar 2020 19:56:01 +0000

 I see one possible failure path:

 Imagine radix_tree_grow() manages to insert >0 nodes to increase the height
 of the tree, but fails to allocate at least one node to complete the path,
 and returns ENOMEM.

 There is an assumption that the operation will be retried and a subsequent
 radix_tree_insert_node() will finish it off.

 That implies there will be a matching radix_tree_remove_node() later too, to
 remove the leaf node and collapse the height of the tree back down to zero.

 If the insertion was speculative that might not happen, so the the tree can
 be left in limbo.

 Now, radix_tree_grow() can't back out what it's done without sabotaging
 radix_tree_await_memory(), and a call to uvm_wait() in libkern would suck,
 so maybe another solution would be to back out the change and cache the
 already allocated nodes with struct radix_tree (with a catchall to free
 them in radix_tree_fini_tree()).  It's not very elegant though.

 Andrew

From: "Andrew Doran" <ad@netbsd.org>
To: gnats-bugs@gnats.NetBSD.org
Cc: 
Subject: PR/54979 CVS commit: src/common/lib/libc/gen
Date: Fri, 10 Apr 2020 23:43:05 +0000

 Module Name:	src
 Committed By:	ad
 Date:		Fri Apr 10 23:43:05 UTC 2020

 Modified Files:
 	src/common/lib/libc/gen: radixtree.c

 Log Message:
 PR kern/54979 (radixtree might misbehave if ENOMEM)

 - radix_tree_insert_node(): if the insert failed due to ENOMEM, roll back
   any updates made to the tree.

 - radix_tree_grow(): either succeed or fail, never make partial adjustments
   to the tree.

 - radix_tree_await_memory(): allocate & free the maximum possible number of
   nodes required by any insertion.


 To generate a diff of this commit:
 cvs rdiff -u -r1.24 -r1.25 src/common/lib/libc/gen/radixtree.c

 Please note that diffs are not public domain; they are subject to the
 copyright notices on the relevant files.

State-Changed-From-To: open->closed
State-Changed-By: ad@NetBSD.org
State-Changed-When: Fri, 10 Apr 2020 23:45:29 +0000
State-Changed-Why:
fixed


>Unformatted:

Home	PR Database Search