From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752261AbdK3NyH (ORCPT ); Thu, 30 Nov 2017 08:54:07 -0500 Received: from mx1.redhat.com ([209.132.183.28]:55694 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1750964AbdK3NyF (ORCPT ); Thu, 30 Nov 2017 08:54:05 -0500 Subject: Re: [PATCH] list_lru: Prefetch neighboring list entries before acquiring lock To: Dave Chinner , Andrew Morton Cc: Vladimir Davydov , Johannes Weiner , linux-kernel@vger.kernel.org, linux-mm@kvack.org References: <1511965054-6328-1-git-send-email-longman@redhat.com> <20171129135319.ab078fbed566be8fc90c92ec@linux-foundation.org> <20171130004252.GR4094@dastard> From: Waiman Long Organization: Red Hat Message-ID: <209d1aea-2951-9d4f-5638-8bc037a6676c@redhat.com> Date: Thu, 30 Nov 2017 08:54:04 -0500 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.2.0 MIME-Version: 1.0 In-Reply-To: <20171130004252.GR4094@dastard> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit Content-Language: en-US X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.29]); Thu, 30 Nov 2017 13:54:05 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On 11/29/2017 07:42 PM, Dave Chinner wrote: > On Wed, Nov 29, 2017 at 01:53:19PM -0800, Andrew Morton wrote: >> On Wed, 29 Nov 2017 09:17:34 -0500 Waiman Long wrote: >> >>> The list_lru_del() function removes the given item from the LRU list. >>> The operation looks simple, but it involves writing into the cachelines >>> of the two neighboring list entries in order to get the deletion done. >>> That can take a while if the cachelines aren't there yet, thus >>> prolonging the lock hold time. >>> >>> To reduce the lock hold time, the cachelines of the two neighboring >>> list entries are now prefetched before acquiring the list_lru_node's >>> lock. >>> >>> Using a multi-threaded test program that created a large number >>> of dentries and then killed them, the execution time was reduced >>> from 38.5s to 36.6s after applying the patch on a 2-socket 36-core >>> 72-thread x86-64 system. >> Patch looks good. >> >> Can someone (Dave?) please explain why list_lru_del() supports deletion >> of an already list_empty(item)? >> This seems a rather dangerous thing to >> encourage. Use cases I can think of are: >> >> a) item is already reliably deleted, so why the heck was the caller >> calling list_lru_del() and > Higher level operations can race. e.g. caller looks up an object, > finds it on the LRU, takes a reference. Then calls list_lru_del() > to remove it from the LRU. It blocks 'cause it can't get the list > lock as.... > > ... Meanwhile, the list shrinker is running, sees the object on the > LRU list, sees it has a valid reference count, does lazy LRU cleanup > by runnning list_lru_isolate() on the object which removes it from > the LRU list. Eventually it drops the list lock, and .... > > ... the original thread gets the lock in list_lru_del() and sees the > object has already been removed from the LRU.... > > IOWs, this sort of boilerplate code is potentially dangerous if > list_lru_del() can't handle items that have already been removed > from the list: > > if (!list_empty(&obj->lru)) > list_lru_del(&obj->lru); > > Because this: > > if (!list_empty(&obj->lru)) > > > list_lru_del(&obj->lru); > > > Would result in bad things happening.... > > And, from that perspective, the racy shortcut in the proposed patch > is wrong, too. Prefetch is fine, but in general shortcutting list > empty checks outside the internal lock isn't. For the record, I add one more list_empty() check at the beginning of list_lru_del() in the patch for 2 purpose: 1. it allows the code to bail out early. 2. It make sure the cacheline of the list_head entry itself is loaded. Other than that, I only add a likely() qualifier to the existing list_empty() check within the lock critical region. Cheers, Longman