From patchwork Tue Sep 11 05:36:10 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Aaron Lu X-Patchwork-Id: 10595065 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 395A8921 for ; Tue, 11 Sep 2018 05:36:34 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 27D83292AD for ; Tue, 11 Sep 2018 05:36:34 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 1B29D292BB; Tue, 11 Sep 2018 05:36:34 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-2.9 required=2.0 tests=BAYES_00,MAILING_LIST_MULTI, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 821A1292AD for ; Tue, 11 Sep 2018 05:36:33 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9750F8E0006; Tue, 11 Sep 2018 01:36:30 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 927188E0001; Tue, 11 Sep 2018 01:36:30 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 83B708E0006; Tue, 11 Sep 2018 01:36:30 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pf1-f198.google.com (mail-pf1-f198.google.com [209.85.210.198]) by kanga.kvack.org (Postfix) with ESMTP id 445848E0001 for ; Tue, 11 Sep 2018 01:36:30 -0400 (EDT) Received: by mail-pf1-f198.google.com with SMTP id x85-v6so12373114pfe.13 for ; Mon, 10 Sep 2018 22:36:30 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-original-authentication-results:x-gm-message-state:from:to:cc :subject:date:message-id:in-reply-to:references; bh=bzauRD9o+W09eWXP1DarQ026TVo0Oh5DmnYxjFzEkFI=; b=IQPOvJiBuCCpp7EZ6p8NX+lF3mqC/wZZAUpaRQ/5xLD5ByizysMAsWtpnr+N9Ldf5W LK07YrlZFI2NkCQC1CArG3RGTJ/Y214uqG/sD/w+8+3URRB3OWRZQcyPXbizDguDuMIX tzZej5iZdMxD/R8yiyTVQozfEctoEj+8flrZ841wJWUElaZnb937jtdAyvG4kx3dM6Rz EH88gFO8VR2aCge5X8LXRUw6zfq+Yl+jgTLWpYvWy/DxY5hbK8fYcuRKLvF8DC1T+tfM mBIHhnFhO/NULFXXO0fQcjSfbI9jP9vRo4hSe3XM8aaWPELQSobs02zx3PLUCjTPMj81 2UOA== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of aaron.lu@intel.com designates 192.55.52.93 as permitted sender) smtp.mailfrom=aaron.lu@intel.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com X-Gm-Message-State: APzg51DoL31T0rlXYgBjZdl57n5523pnj2hn32hbqrB8FzeN82ZdI7Px M+X9J0T6tsqKGjHQhQ7qBXsyDm/nin5hNzDDo2cQYJUTQQrSDcLOV/tCkVrfRsCZyTTKdiHGlgK oI51EzaebPDFinIg/NIL/V4rVHxBgOgnHOcVK8g87EKuJ1f5o3r4xmns5snvQ1w44zw== X-Received: by 2002:a63:7d48:: with SMTP id m8-v6mr26755738pgn.0.1536644189949; Mon, 10 Sep 2018 22:36:29 -0700 (PDT) X-Google-Smtp-Source: ANB0VdbqV/BTaM5OWOZcDka1hFHcIpP9p62r/M8HKAFkKZgcSC9F9f3hZcrYXDcpFjxTCATk/SYi X-Received: by 2002:a63:7d48:: with SMTP id m8-v6mr26755668pgn.0.1536644188822; Mon, 10 Sep 2018 22:36:28 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1536644188; cv=none; d=google.com; s=arc-20160816; b=0DwSqIEjh0h7G0dkEeWY74NGBpOKJypWAThZf+6MXwBryXexJZlKzNm4KjHBIuNKE6 Mudr3buA339TKbndpxznBESCav6fY1I+QNHtoDdDQz6m2u/8nKRUHbVTyiO4kM00kDeO tB5ccb70i4ykKBuoHOv2gXEL1y8JCUlRe/lVK6AU5wRfesz43xXaX/vrxkMmkWjbj4X8 NpVV8gRktGl9+1uhkydqLLCWC2sYm47Q4JHYWjfDNW35bRI12kCUpJgX+N5yY2KlhxC0 Ly01dEyh6Vn/pozfFs+g1hAl1RUOneZCwbS8n8+0uWPAGBMWR6cAQcIg34wzOUSprH2G etVw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:cc:to:from; bh=bzauRD9o+W09eWXP1DarQ026TVo0Oh5DmnYxjFzEkFI=; b=W3sp04ukX9TEpJVQ4U+il0dV4hErups8qAF0ry22S0S7dZwkbmNZ2spZgTHar4vJz2 syzmjnf7BB8iNQUPhe2oXlqtpXQDWNAPpb1svehn3u7r+sgZi5TCCBaphW1shB4bFij8 UTeJiUDX4I7qxhTkWhnIXuAMorD5efhFTlzgq8b5ZVQhjgaYVhIj7Mhsi6b2/YxI0M1O 1kjgeIJGjsOEMoX+8zJ7OmC3pJikiWXJbRlqs1YBRjixC4+UaX6caMstvqsqWVqnKqaL sW0TgO71e5r3J6Koufpw1IBDFvw8j7Z9QcrQfTB33W8wW2RRb0G8U9q5Bvsh38PJ8+u9 dPGw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of aaron.lu@intel.com designates 192.55.52.93 as permitted sender) smtp.mailfrom=aaron.lu@intel.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com Received: from mga11.intel.com (mga11.intel.com. [192.55.52.93]) by mx.google.com with ESMTPS id c19-v6si20646945pfc.18.2018.09.10.22.36.28 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 10 Sep 2018 22:36:28 -0700 (PDT) Received-SPF: pass (google.com: domain of aaron.lu@intel.com designates 192.55.52.93 as permitted sender) client-ip=192.55.52.93; Authentication-Results: mx.google.com; spf=pass (google.com: domain of aaron.lu@intel.com designates 192.55.52.93 as permitted sender) smtp.mailfrom=aaron.lu@intel.com; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=intel.com X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga006.fm.intel.com ([10.253.24.20]) by fmsmga102.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 10 Sep 2018 22:36:28 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.53,359,1531810800"; d="scan'208";a="262426326" Received: from aaronlu.sh.intel.com ([10.239.159.44]) by fmsmga006.fm.intel.com with ESMTP; 10 Sep 2018 22:36:26 -0700 From: Aaron Lu To: linux-mm@kvack.org, linux-kernel@vger.kernel.org Cc: Andrew Morton , Dave Hansen , Michal Hocko , Vlastimil Babka , Mel Gorman , Matthew Wilcox , Daniel Jordan , Tariq Toukan , Yosef Lev , Jesper Dangaard Brouer Subject: [RFC PATCH 3/9] mm: introduce smp_list_splice to prepare for concurrent LRU adds Date: Tue, 11 Sep 2018 13:36:10 +0800 Message-Id: <20180911053616.6894-4-aaron.lu@intel.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20180911053616.6894-1-aaron.lu@intel.com> References: <20180911053616.6894-1-aaron.lu@intel.com> X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: X-Virus-Scanned: ClamAV using ClamSMTP From: Daniel Jordan Now that we splice a local list onto the LRU, prepare for multiple tasks doing this concurrently by adding a variant of the kernel's list splicing API, list_splice, that's designed to work with multiple tasks. Although there is naturally less parallelism to be gained from locking the LRU head this way, the main benefit of doing this is to allow removals to happen concurrently. The way lru_lock is today, an add needlessly blocks removal of any page but the first in the LRU. For now, hold lru_lock as writer to serialize the adds to ensure the function is correct for a single thread at a time. Yosef Lev came up with this algorithm. [aaronlu: drop LRU related code, keep only list related code] Suggested-by: Yosef Lev Signed-off-by: Daniel Jordan --- include/linux/list.h | 1 + lib/list.c | 60 ++++++++++++++++++++++++++++++++++++++------ 2 files changed, 54 insertions(+), 7 deletions(-) diff --git a/include/linux/list.h b/include/linux/list.h index 0fd9c87dd14b..5f203fb55939 100644 --- a/include/linux/list.h +++ b/include/linux/list.h @@ -48,6 +48,7 @@ static inline bool __list_del_entry_valid(struct list_head *entry) #endif extern void smp_list_del(struct list_head *entry); +extern void smp_list_splice(struct list_head *list, struct list_head *head); /* * Insert a new entry between two known consecutive entries. diff --git a/lib/list.c b/lib/list.c index 4d0949ea1a09..104faa144abf 100644 --- a/lib/list.c +++ b/lib/list.c @@ -10,17 +10,18 @@ #include /* - * smp_list_del is a variant of list_del that allows concurrent list removals - * under certain assumptions. The idea is to get away from overly coarse - * synchronization, such as using a lock to guard an entire list, which - * serializes all operations even though those operations might be happening on - * disjoint parts. + * smp_list_del and smp_list_splice are variants of list_del and list_splice, + * respectively, that allow concurrent list operations under certain + * assumptions. The idea is to get away from overly coarse synchronization, + * such as using a lock to guard an entire list, which serializes all + * operations even though those operations might be happening on disjoint + * parts. * * If you want to use other functions from the list API concurrently, * additional synchronization may be necessary. For example, you could use a * rwlock as a two-mode lock, where readers use the lock in shared mode and are - * allowed to call smp_list_del concurrently, and writers use the lock in - * exclusive mode and are allowed to use all list operations. + * allowed to call smp_list_* functions concurrently, and writers use the lock + * in exclusive mode and are allowed to use all list operations. */ /** @@ -156,3 +157,48 @@ void smp_list_del(struct list_head *entry) entry->next = LIST_POISON1; entry->prev = LIST_POISON2; } + +/** + * smp_list_splice - thread-safe splice of two lists + * @list: the new list to add + * @head: the place to add it in the first list + * + * Safely handles concurrent smp_list_splice operations onto the same list head + * and concurrent smp_list_del operations of any list entry except @head. + * Assumes that @head cannot be removed. + */ +void smp_list_splice(struct list_head *list, struct list_head *head) +{ + struct list_head *first = list->next; + struct list_head *last = list->prev; + struct list_head *succ; + + /* + * Lock the front of @head by replacing its next pointer with NULL. + * Should another thread be adding to the front, wait until it's done. + */ + succ = READ_ONCE(head->next); + while (succ == NULL || cmpxchg(&head->next, succ, NULL) != succ) { + cpu_relax(); + succ = READ_ONCE(head->next); + } + + first->prev = head; + last->next = succ; + + /* + * It is safe to write to succ, head's successor, because locking head + * prevents succ from being removed in smp_list_del. + */ + succ->prev = last; + + /* + * Pairs with the implied full barrier before the cmpxchg above. + * Ensures the write that unlocks the head is seen last to avoid list + * corruption. + */ + smp_wmb(); + + /* Simultaneously complete the splice and unlock the head node. */ + WRITE_ONCE(head->next, first); +}