Received: by 2002:ad5:474a:0:0:0:0:0 with SMTP id i10csp3874767imu; Mon, 7 Jan 2019 11:03:29 -0800 (PST) X-Google-Smtp-Source: ALg8bN6/cbDpH9T2bPgt0iSbLmfd+Q0RbiAeAmO9O3lwzSX3iX+VKLsqru9URv4W+/1mesBqeudQ X-Received: by 2002:a62:ae04:: with SMTP id q4mr36928452pff.126.1546887809221; Mon, 07 Jan 2019 11:03:29 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1546887809; cv=none; d=google.com; s=arc-20160816; b=WBqNyTLApeWO86qLgng9E0Q3ml5Quge5I+S0niQyvkDVv07V6fc1PpTtyClBoBkucd ROBOAWbqzmRJYZyNVN60hI0fEhlX0MQj0/J+RmF2VzPjLL1MTJeGjivuUV3eaImPW0Rb zf7zQVVMiLtk2E0aongFWchpiUOSbfvEn5PkCCymGkNkcrNsSKIx1tRemJHBD+n5oaRO 0sT3V/jQQ5R0gr9clpXwYYB3UhDPVk3AXVBHn74Ek1PcVjTD8hAfA5eK6e1KJg9DKKcN 3ydoAaXH1TwxXcknBO3a64XYmllH6jkO/hJvm1OwXnaXAC60+Mu1c9c9FteOQN9wLQVz K0eg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:sender:message-id:user-agent:in-reply-to :content-disposition:mime-version:references:reply-to:subject:cc:to :from:date; bh=aYDhQ4stdDkSZIgQQLfVB4hXtvqIvGLSKAgTSrcYgBk=; b=gndD5g2ZISau8Xu3UUq4QHxsUExZVpAdyGT/9HaMUwpkinplccsn7ZjBtSxaag8bug y47qUD8uEA3M2+FxweLHXqwA5Kn0xtyuMkO2aoFp9QkAX1CgGGs1dc/Gq4nUniZ9Z3Gr mdWaB3gSAZYe50U1TeARm1TkySieWHAWOStqVvfszpvSzq/KBcYQYeWq3XO/C8F3H+V9 I6NJHLxFPNqwUeNF+ckQZ/noYqkWYUvNbDeIc17SKsLvGQUlUOt+6DBmD5+4x70aRsdK khhOkCMePJYUOsMnVFBjidEeQVtKaTlw5A0r2qrIffyvBg2egLs9u5Klr10d8AKnb5fg 2AwA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=ibm.com Return-Path: Received: from vger.kernel.org (vger.kernel.org. [209.132.180.67]) by mx.google.com with ESMTP id d11si62572572pla.335.2019.01.07.11.03.13; Mon, 07 Jan 2019 11:03:29 -0800 (PST) Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67; Authentication-Results: mx.google.com; spf=pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=ibm.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1729170AbfAGTAf (ORCPT + 99 others); Mon, 7 Jan 2019 14:00:35 -0500 Received: from mx0a-001b2d01.pphosted.com ([148.163.156.1]:44848 "EHLO mx0a-001b2d01.pphosted.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728940AbfAGS7P (ORCPT ); Mon, 7 Jan 2019 13:59:15 -0500 Received: from pps.filterd (m0098393.ppops.net [127.0.0.1]) by mx0a-001b2d01.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id x07IoKSZ110302 for ; Mon, 7 Jan 2019 13:59:14 -0500 Received: from e11.ny.us.ibm.com (e11.ny.us.ibm.com [129.33.205.201]) by mx0a-001b2d01.pphosted.com with ESMTP id 2pvcd60d7v-1 (version=TLSv1.2 cipher=AES256-GCM-SHA384 bits=256 verify=NOT) for ; Mon, 07 Jan 2019 13:59:14 -0500 Received: from localhost by e11.ny.us.ibm.com with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted for from ; Mon, 7 Jan 2019 18:59:13 -0000 Received: from b01cxnp23032.gho.pok.ibm.com (9.57.198.27) by e11.ny.us.ibm.com (146.89.104.198) with IBM ESMTP SMTP Gateway: Authorized Use Only! Violators will be prosecuted; (version=TLSv1/SSLv3 cipher=AES256-GCM-SHA384 bits=256/256) Mon, 7 Jan 2019 18:59:09 -0000 Received: from b01ledav003.gho.pok.ibm.com (b01ledav003.gho.pok.ibm.com [9.57.199.108]) by b01cxnp23032.gho.pok.ibm.com (8.14.9/8.14.9/NCO v10.0) with ESMTP id x07Ix8QX23331038 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=FAIL); Mon, 7 Jan 2019 18:59:08 GMT Received: from b01ledav003.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 55019B2067; Mon, 7 Jan 2019 18:59:08 +0000 (GMT) Received: from b01ledav003.gho.pok.ibm.com (unknown [127.0.0.1]) by IMSVA (Postfix) with ESMTP id 37488B2064; Mon, 7 Jan 2019 18:59:08 +0000 (GMT) Received: from paulmck-ThinkPad-W541 (unknown [9.70.82.88]) by b01ledav003.gho.pok.ibm.com (Postfix) with ESMTP; Mon, 7 Jan 2019 18:59:08 +0000 (GMT) Received: by paulmck-ThinkPad-W541 (Postfix, from userid 1000) id E684A16C607B; Mon, 7 Jan 2019 10:59:31 -0800 (PST) Date: Mon, 7 Jan 2019 10:59:31 -0800 From: "Paul E. McKenney" To: He Zhe Cc: Catalin Marinas , josh@joshtriplett.org, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH] mm: kmemleak: Turn kmemleak_lock to spin lock and RCU primitives Reply-To: paulmck@linux.ibm.com References: <1546612153-451172-1-git-send-email-zhe.he@windriver.com> <20190104183715.GC187360@arrakis.emea.arm.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-GCONF: 00 x-cbid: 19010718-2213-0000-0000-00000337D062 X-IBM-SpamModules-Scores: X-IBM-SpamModules-Versions: BY=3.00010362; HX=3.00000242; KW=3.00000007; PH=3.00000004; SC=3.00000273; SDB=6.01143147; UDB=6.00595104; IPR=6.00923398; MB=3.00025019; MTD=3.00000008; XFM=3.00000015; UTC=2019-01-07 18:59:11 X-IBM-AV-DETECTION: SAVI=unused REMOTE=unused XFE=unused x-cbparentid: 19010718-2214-0000-0000-00005CE06EA4 Message-Id: <20190107185931.GE1215@linux.ibm.com> X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-01-07_08:,, signatures=0 X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 priorityscore=1501 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0 clxscore=1015 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1810050000 definitions=main-1901070159 Sender: linux-kernel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Mon, Jan 07, 2019 at 03:31:18PM +0800, He Zhe wrote: > > > On 1/5/19 2:37 AM, Catalin Marinas wrote: > > On Fri, Jan 04, 2019 at 10:29:13PM +0800, zhe.he@windriver.com wrote: > >> It's not necessary to keep consistency between readers and writers of > >> kmemleak_lock. RCU is more proper for this case. And in order to gain better > >> performance, we turn the reader locks to RCU read locks and writer locks to > >> normal spin locks. > > This won't work. > > > >> @@ -515,9 +515,7 @@ static struct kmemleak_object *find_and_get_object(unsigned long ptr, int alias) > >> struct kmemleak_object *object; > >> > >> rcu_read_lock(); > >> - read_lock_irqsave(&kmemleak_lock, flags); > >> object = lookup_object(ptr, alias); > >> - read_unlock_irqrestore(&kmemleak_lock, flags); > > The comment on lookup_object() states that the kmemleak_lock must be > > held. That's because we don't have an RCU-like mechanism for removing > > removing objects from the object_tree_root: > > > >> > >> /* check whether the object is still available */ > >> if (object && !get_object(object)) > >> @@ -537,13 +535,13 @@ static struct kmemleak_object *find_and_remove_object(unsigned long ptr, int ali > >> unsigned long flags; > >> struct kmemleak_object *object; > >> > >> - write_lock_irqsave(&kmemleak_lock, flags); > >> + spin_lock_irqsave(&kmemleak_lock, flags); > >> object = lookup_object(ptr, alias); > >> if (object) { > >> rb_erase(&object->rb_node, &object_tree_root); > >> list_del_rcu(&object->object_list); > >> } > >> - write_unlock_irqrestore(&kmemleak_lock, flags); > >> + spin_unlock_irqrestore(&kmemleak_lock, flags); > > So here, while list removal is RCU-safe, rb_erase() is not. > > > > If you have time to implement an rb_erase_rcu(), than we could reduce > > the locking in kmemleak. > > Thanks, I really neglected that rb_erase is not RCU-safe here. > > I'm not sure if it is practically possible to implement rb_erase_rcu. Here > is my concern: > In the code paths starting from rb_erase, the tree is tweaked at many > places, in both __rb_erase_augmented and ____rb_erase_color. To my > understanding, there are many intermediate versions of the tree > during the erasion. In some of the versions, the tree is incomplete, i.e. > some nodes(not the one to be deleted) are invisible to readers. I'm not > sure if this is acceptable as an RCU implementation. Does it mean we > need to form a rb_erase_rcu from scratch? > > And are there any other concerns about this attempt? > > Let me add RCU supporters Paul and Josh here. Your advice would be > highly appreciated. If updates and rebalancing are handled carefully, it can be made to work. The classic paper by Kung and Lehman covers the rebalancing issues: http://www.eecs.harvard.edu/~htk/publication/1980-tods-kung-lehman.pdf Thanx, Paul