From patchwork Thu Feb 28 02:18:28 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832461 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 E98C113B5 for ; Thu, 28 Feb 2019 02:18:48 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D6E2E2E90C for ; Thu, 28 Feb 2019 02:18:48 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id CAC772E91E; Thu, 28 Feb 2019 02:18:48 +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 6FCC72E90C for ; Thu, 28 Feb 2019 02:18:48 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 688EB8E0005; Wed, 27 Feb 2019 21:18:46 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 636738E0001; Wed, 27 Feb 2019 21:18:46 -0500 (EST) 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 54E868E0005; Wed, 27 Feb 2019 21:18:46 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) by kanga.kvack.org (Postfix) with ESMTP id 2B8618E0001 for ; Wed, 27 Feb 2019 21:18:46 -0500 (EST) Received: by mail-qt1-f198.google.com with SMTP id q17so17102892qta.17 for ; Wed, 27 Feb 2019 18:18:46 -0800 (PST) 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=ap32u9J2DjTEbnwK8tlI9EaVEAe0C092XmNehyAz4/8=; b=YPzHxIZBfDm54FIvs3XaSnxjdXtakf0bYHNhOC+yPKxhJtklFMQhdIUMixplAhX17h Gpr01Q48ljg9ZI7hts2W9U6y4Rg4ET6AyEQDyPCSWbyan7/89i35afxuRmoZvtU8Z1HO TJ4MpPkZerEKanuNxpE71SRYehw2qzzfb8pnYNETzZ2lJilUoWxM8gIaiyy8timBrsZu SZgQhhbTtgZzbx7Fp4fvRhXHq9mlRcQIVGqzsAhpiJ0OiitlvoWE6NZdgCWgShYUkBiK PEcVlfivLCBr1lTVO68ssPodY8WesxYXtk5/VUR7lqQq/orHUwYnEXR1Kyr+aw0AxfOl x92g== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: AHQUAuY6KCBwMecTJ27LUIpXLUcqHjZjLpYu8et7FTA26JzrXV8jaP0e EW75xSY0n7sT2hSxCnpL4oSXPDTnTF1iCKA1IyYmdFPiJ43DmVD3Y5HCA7oyRa2BbOKr7yMhFVB vEDWrTUAkEQ8M+sPcHqtLun26LlF10vQ9OIIh4nevfYKsbYdafwdf1C12HuPo9Ts7tSsltk1z// 39IEmerUY7A5aXl2p0JJZtNr4KFttFkVWNWxFBH+B7Am7riFp6LXxn9OgRKvYPPlxV86k9rVVDt KcYspnROjtovA6zS2gsP7Ij/8EQmkFl85bYWBYI3QtR0lYK8vKYkUUJF7ve9h/b1RZ3knFbt0Ju aAHc7eM0753zf8JPWB0T6VVnLh0DiKwYYkXBmf47SMRAzlijK4unHtj+PwuuXBxDodtuxoUvZg= = X-Received: by 2002:ac8:f76:: with SMTP id l51mr4306194qtk.248.1551320325928; Wed, 27 Feb 2019 18:18:45 -0800 (PST) X-Received: by 2002:ac8:f76:: with SMTP id l51mr4306170qtk.248.1551320325262; Wed, 27 Feb 2019 18:18:45 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320325; cv=none; d=google.com; s=arc-20160816; b=CBTY2Vfi+AikBk6jCjNT2kgjEuPRBzFuKC+OXhKBQdngO1ME3SifzlM/6ef35CEyyy n0Tlc9uu4vzTrT5u/swBBxyVEyqe2YQ5nuB0M0EYqQgAjFnabP8zhdrf7Basx0OWE9b3 lEnBjPUC6U5d430xx1qx3POK3JyqdnxeQ/x2ThomhKggJE9zzo5SSc38YG0eTUOLbP5/ 7/5YlH1GCoJ2Ioi9vQI3s0lyNcw1uKSSf1/vikYzmxd8dxt/MymfOJQ0AWjnxYvpRdsH x6X37xSwE+X+CeX3kfYFWFrjy429Z403HZftOYCAh/0jpqtImp/n0BGGoT3o9l9YryWH Cj3Q== 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=ap32u9J2DjTEbnwK8tlI9EaVEAe0C092XmNehyAz4/8=; b=QpkN+RUpjFhssCDlkNT3jB4X2ICdVGPd76C614AeO4XfXUHCo4Li0OOOAQWqFTd/fI IgGKd9jLdM6LD0USEIEyfuBSXqs8v7jpvA9TtEKnbdgf7zqFAfW+gc1Qd0sgFF46EgSs bOOvshDt0mafTHF+5FECa3LqvTKf3b1LW3pvoW3+hi29NE+ADFjsuHI+Ik0f0+WlNol4 D4Eux5Rvq/NW0krMGK85d4pNwvZpWIkrXnmtBeEL6sVBF9jwmp9gjZKA27iUcAh0VBwQ yoCeKUhBMYcJxXy5KW4n9UGc4V84o45u/aOemgZb1f4QmEem3l31kHw2mufM8lscG/JG Y0Tw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id i5sor9786587qkg.4.2019.02.27.18.18.45 for (Google Transport Security); Wed, 27 Feb 2019 18:18:45 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: AHgI3Ib9npUsIiyGRCnSbW0Gjjezvhtl8EJKNhNK6/9zB6/aj4x+e7X7Rv/8FH7Vb9liQTh/0R1Mrw== X-Received: by 2002:a37:61d3:: with SMTP id v202mr4658157qkb.217.1551320325029; Wed, 27 Feb 2019 18:18:45 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.43 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:43 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 01/12] percpu: update free path with correct new free region Date: Wed, 27 Feb 2019 21:18:28 -0500 Message-Id: <20190228021839.55779-2-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 When updating the chunk's contig_hint on the free path of a hint that does not touch the page boundaries, it was incorrectly using the starting offset of the free region and the block's contig_hint. This could lead to incorrect assumptions about fit given a size and better alignment of the start. Fix this by using (end - start) as this is only called when updating a hint within a block. Signed-off-by: Dennis Zhou Reviewed-by: Peng Fan --- mm/percpu.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/mm/percpu.c b/mm/percpu.c index db86282fd024..53bd79a617b1 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -871,7 +871,7 @@ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, pcpu_chunk_refresh_hint(chunk); else pcpu_chunk_update(chunk, pcpu_block_off_to_off(s_index, start), - s_block->contig_hint); + end - start); } /** From patchwork Thu Feb 28 02:18:29 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832463 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 4C56C17E9 for ; Thu, 28 Feb 2019 02:18:52 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 3C0F42E93E for ; Thu, 28 Feb 2019 02:18:52 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 302C82E966; Thu, 28 Feb 2019 02:18:52 +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 AB98A2E947 for ; Thu, 28 Feb 2019 02:18:50 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CA4EC8E0006; Wed, 27 Feb 2019 21:18:47 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id C517C8E0001; Wed, 27 Feb 2019 21:18:47 -0500 (EST) 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 B46848E0006; Wed, 27 Feb 2019 21:18:47 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by kanga.kvack.org (Postfix) with ESMTP id 7DDE88E0001 for ; Wed, 27 Feb 2019 21:18:47 -0500 (EST) Received: by mail-qt1-f199.google.com with SMTP id o56so15826358qto.9 for ; Wed, 27 Feb 2019 18:18:47 -0800 (PST) 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=Vx2VZtOceXx/muNOFvOTUbvq8L4C1gUYQ/k1Qg6oF3M=; b=ilLpnEZKKCEGgxW/kt2AJVU3UBDhM4KqIeMzU86HP4FZfGPw179WB2UErcDH2u/Pfi ygR95G4fbPKMS0DQS9RiindYZ1vYyoHsa+7qf9sHInHX4u5MRiZ9s5x5GMyBALkKjoeZ 99D9mVNyrhO63jeAAk2VfgrNe94dsgFCKk2XZAxI19zID8YGp6PBxAM1qvwJ/s2GpIH2 NpXuYf0/goET0X64CLoqA2soXUUHnQ0QkFM38wxV+8lTBFfZAFOkqnxq3JfgcNuDxYcH N2SfdqYKUyQsMOFdZpLwcJRMk6e9wCS5XPx34euS+V5cDpR2MbqqAMNswxuEFVvGEpwY J3eg== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: AHQUAuZ0ONPm0u2m5UDQSZrnVCqRDYz2No0gA5lBGW2pfAZpOlrCprBY oB83duvxFuK2uZUg7X6bOi4bh+D7UNcp7CWKmgJyBUtCep2zUs6i7tfTKUDVadp8wimhOxGu/Ti bQpsT+gEbS/M44QQKMXNkPUCddy9SyhKWKPBqkwZ3AtluonhnVSESb6I+f4qQijY/aH0jh2Afir 0Mnusw89XMl7FCkScUmeuke7tyhHMFJNBqMUDLKzvU1NXz8ng9XbxY2O4cQ/LRefNcDHcL5xg+/ mGv+dZcuoDTIiQHCYuhkBqdWtF0rQtwgizZXRTWJ3wWQmDkz+GmikjzxYO9pHyXkmTuaiI3tEJG Xxq6TEc1GgKF1DeYdi0d7S6QyFJ/W678uikMxPM+4oJFNdtdfAg9/qxvWXn99dsN/Uats2GV8A= = X-Received: by 2002:ac8:803:: with SMTP id u3mr4323047qth.108.1551320327296; Wed, 27 Feb 2019 18:18:47 -0800 (PST) X-Received: by 2002:ac8:803:: with SMTP id u3mr4323026qth.108.1551320326657; Wed, 27 Feb 2019 18:18:46 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320326; cv=none; d=google.com; s=arc-20160816; b=kKk7g4/SLk2O9tBHGeUBnxDF0HIbdAAxQJSeIA+0tlxCpN9lPeEsPJMttJH3HkcDVV 1jRX5GuT5DcuAdcSeHiJY3URmdf9yz+nwnoEUyXjsYrSyvOuxRphmne3zoJ3ssrmWVaf Effny2/6lbIjk2KJzCidpa18wG5FVcr3DnCSbeHLjWgLjZXwqK1DRAZ7tMQKxQi68R1e ddZl/NSAE7ITW0pKRTtWGWVIdUnYFwUnwl33frsJnXf5l94uVUH1ctMdDmcGby06AvDP yMmtzR0Jk/d5GVTpH1CJPawDk6tp+uy7v/6jqys9bGyYOLKCl34dxoE+k0MMXSrDRAc4 +Y7g== 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=Vx2VZtOceXx/muNOFvOTUbvq8L4C1gUYQ/k1Qg6oF3M=; b=HmSw/Z2wuiquOZ4VouYY34RgboISwLm36mxXV7B/hixaRsXTI/gPXqbkCv8bK7lPF+ soumVBH/TlZdU9wPsjYXTyurTFg/c2ileJZwLrgECcdv6hjmKL2U/rEEktK6S0UlfyVP TJaMnfOdFqWJNsZcz//SFJ2ehfFBhdZ9UFf9ifOB/iT9XOrJkr2B51tUkuT8b8ObSMV6 7LmEKnxl87r9UISg5roZe4RAnnawrXwdVm6vI5jFh+TpsdXef7TII8vwI1xHRGtU7WV9 r3hDMfVIuO/QV10OJDwcSRCbC8Kavr3BWsz8n1DBl2wRD2D+i4nAhBK0JCZMIfOtmetC aydw== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id x27sor20016451qvf.7.2019.02.27.18.18.46 for (Google Transport Security); Wed, 27 Feb 2019 18:18:46 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: APXvYqxT0Zazm3tmjv5xoUKZeesy8YEfKuPUZhr6x6oWUxafL1uMoGMXcNEnHEANX5YFiSEYe6MK5A== X-Received: by 2002:a0c:b311:: with SMTP id s17mr4441198qve.69.1551320326433; Wed, 27 Feb 2019 18:18:46 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.45 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:45 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 02/12] percpu: do not search past bitmap when allocating an area Date: Wed, 27 Feb 2019 21:18:29 -0500 Message-Id: <20190228021839.55779-3-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 pcpu_find_block_fit() guarantees that a fit is found within PCPU_BITMAP_BLOCK_BITS. Iteration is used to determine the first fit as it compares against the block's contig_hint. This can lead to incorrectly scanning past the end of the bitmap. The behavior was okay given the check after for bit_off >= end and the correctness of the hints from pcpu_find_block_fit(). This patch fixes this by bounding the end offset by the number of bits in a chunk. Signed-off-by: Dennis Zhou Reviewed-by: Peng Fan --- mm/percpu.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/mm/percpu.c b/mm/percpu.c index 53bd79a617b1..69ca51d238b5 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -988,7 +988,8 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits, /* * Search to find a fit. */ - end = start + alloc_bits + PCPU_BITMAP_BLOCK_BITS; + end = min_t(int, start + alloc_bits + PCPU_BITMAP_BLOCK_BITS, + pcpu_chunk_map_bits(chunk)); bit_off = bitmap_find_next_zero_area(chunk->alloc_map, end, start, alloc_bits, align_mask); if (bit_off >= end) From patchwork Thu Feb 28 02:18:30 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832465 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 9F5B817E9 for ; Thu, 28 Feb 2019 02:18:53 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 85F1F2E93E for ; Thu, 28 Feb 2019 02:18:53 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7A0512E967; Thu, 28 Feb 2019 02:18:53 +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 0E53B2E93E for ; Thu, 28 Feb 2019 02:18:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BBB198E0007; Wed, 27 Feb 2019 21:18:49 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id B46C78E0001; Wed, 27 Feb 2019 21:18:49 -0500 (EST) 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 972EE8E0007; Wed, 27 Feb 2019 21:18:49 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by kanga.kvack.org (Postfix) with ESMTP id 67AC68E0001 for ; Wed, 27 Feb 2019 21:18:49 -0500 (EST) Received: by mail-qk1-f197.google.com with SMTP id a11so14785166qkk.10 for ; Wed, 27 Feb 2019 18:18:49 -0800 (PST) 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=Zob00SAWeBYh4oEQ8sirU3S+Sks7fCNmhlxQAAwLhMs=; b=D0a2B8b8aATx2MfMXdDyBeJ57zE8q8zG04gsbKYrPlz5hc7nexA5KRAM8YHyjFyCtM at3sgyNvHTbzJ4fuWL+1JhPa/zUS0a8AJgTSfc2r25SniOzDVMJX+551vLSs1VYe5ut0 mJ1RS9myOYrwmdfNoLy21JFh997DULoHarcNj85wmDyNtvwBpYEfIKwu365jxluFJk4J fgsQ0OP321O3Mxh4U8936JFqUKPjPe3GHAPLTKv+wLFL8sGmTBsx16gLchjEgqWxh/Jc ok9b8QM+88Dnl9WcT5Xz6ny92NWmAQKc1oazo+Rp5JrfD7jW4/wk5dAZpefmPNa1qBps YqMA== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: AHQUAuY95ps6Hjwt9PFJM9K5PnKPqufQZ2p8cMAjzXC58HsvMJrJ7Csm k+/f9cEVvKvLvJTjC30ljU5COQehrb7QT9NSU5rgMvqTr8mK6qAwrTHjZCMTHAfxXcw8A6xtG7l ntqJBu9alShMTcFs3MJohyMWimf+YVLtOyJmB4HsLM5RpGZc1lAnrlXTodAOqGn8qez4wouwfSf nUpqFukNlPi2oicFe1P5BPpKJjKIYo91IGizI1BeM2iLefvGsj5xDQKX6SYN/6qfAe1/LX6Qjnl gNQOukTLJ78GYI0+gZwTxtmwUsUKS2jfZanpW4IoYIaFmPcdbvJytQ6q9Jdff7il0qYe3er9iWe kgdU0Om4zw+HELyCv2I/wnF8gLzTML7Bkg7Tz0om9v5qlBjffQjl7PJKV3GwameKQWCeSWy5aQ= = X-Received: by 2002:a37:a42:: with SMTP id 63mr4673599qkk.269.1551320329170; Wed, 27 Feb 2019 18:18:49 -0800 (PST) X-Received: by 2002:a37:a42:: with SMTP id 63mr4673577qkk.269.1551320328457; Wed, 27 Feb 2019 18:18:48 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320328; cv=none; d=google.com; s=arc-20160816; b=ic7BZCwO7eDcZZI2JLfzEnQZw/46Uyj2E3aOvooVL0aHxblLri0d2yTVNH8yTaIs0k hbf8hKZn55cRnUsHG+JVvuGtjA1+caBqetY4zAJXsTBI8AKuqa8Q9WZkymbVrTJFMHZi zfU9Q3A4zx2fjEvg78IPQgoUgLyRdjXSp/9RtUWjDWrdS6MIjBwb44PWTt9FRv7w+xpK 8GD9KwgPgYcgW6hL1Kug7eNz4yG2KiVa7dDwAJhPFrTYxrZtzYyiz9gxIpYE0vsy5jmZ 45PVGhte4SOx2/6O1DIBncDC63on3oM+rNOtsPj0waMIWer5N422jf3pSrCztt4ZwFYW 6RKA== 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=Zob00SAWeBYh4oEQ8sirU3S+Sks7fCNmhlxQAAwLhMs=; b=apN1RFpeEUEAzwpCZdzTnLkiPMNWamANnQfKshUrH4wGWZIIB2UshcWSwqQMz2fNzh uALtPxdGEuMAXES4EIN+6oPEchVhg2h5cSzp7JPK2UMF8xqwWXwAdfLf6k1EBcB3+WM9 xL8F4boiPv/XpM/nxGNRuNo8fUDEGnvabbn3SthMaXoQLQzsHPXy+ImNItPRbfaKZwkx vGFMvLdzJahkacjisXOkr65jjSJL5qaXIalUyeQNrEi+AGHZ3LekK0xQ0ySTfZHEcJXM QrB6K6+2Y61JT5c8lIvWpqvUOjcyXrt3QSB+SfhN66ILnJ9jSWh8DpB2C9FveEHQLoZ4 xdXg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id a71sor5619271qkj.43.2019.02.27.18.18.48 for (Google Transport Security); Wed, 27 Feb 2019 18:18:48 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: APXvYqxz8+gxkBV2tfV0g1NRbjVNK+SA9NVlrl0RNozpYzGlY83nUOmtsMtX9iAm89FyNgTCaf4oQg== X-Received: by 2002:a37:4701:: with SMTP id u1mr4545594qka.357.1551320328211; Wed, 27 Feb 2019 18:18:48 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.46 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:47 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 03/12] percpu: introduce helper to determine if two regions overlap Date: Wed, 27 Feb 2019 21:18:30 -0500 Message-Id: <20190228021839.55779-4-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 While block hints were always accurate, it's possible when spanning across blocks that we miss updating the chunk's contig_hint. Rather than rely on correctness of the boundaries of hints, do a full overlap comparison. Signed-off-by: Dennis Zhou --- mm/percpu.c | 31 +++++++++++++++++++++++++++---- 1 file changed, 27 insertions(+), 4 deletions(-) diff --git a/mm/percpu.c b/mm/percpu.c index 69ca51d238b5..b40112b2fc59 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -546,6 +546,24 @@ static inline int pcpu_cnt_pop_pages(struct pcpu_chunk *chunk, int bit_off, bitmap_weight(chunk->populated, page_start); } +/* + * pcpu_region_overlap - determines if two regions overlap + * @a: start of first region, inclusive + * @b: end of first region, exclusive + * @x: start of second region, inclusive + * @y: end of second region, exclusive + * + * This is used to determine if the hint region [a, b) overlaps with the + * allocated region [x, y). + */ +static inline bool pcpu_region_overlap(int a, int b, int x, int y) +{ + if ((x >= a && x < b) || (y > a && y <= b) || + (x <= a && y >= b)) + return true; + return false; +} + /** * pcpu_chunk_update - updates the chunk metadata given a free area * @chunk: chunk of interest @@ -710,8 +728,11 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, PCPU_BITMAP_BLOCK_BITS, s_off + bits); - if (s_off >= s_block->contig_hint_start && - s_off < s_block->contig_hint_start + s_block->contig_hint) { + if (pcpu_region_overlap(s_block->contig_hint_start, + s_block->contig_hint_start + + s_block->contig_hint, + s_off, + s_off + bits)) { /* block contig hint is broken - scan to fix it */ pcpu_block_refresh_hint(chunk, s_index); } else { @@ -764,8 +785,10 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, * contig hint is broken. Otherwise, it means a smaller space * was used and therefore the chunk contig hint is still correct. */ - if (bit_off >= chunk->contig_bits_start && - bit_off < chunk->contig_bits_start + chunk->contig_bits) + if (pcpu_region_overlap(chunk->contig_bits_start, + chunk->contig_bits_start + chunk->contig_bits, + bit_off, + bit_off + bits)) pcpu_chunk_refresh_hint(chunk); } From patchwork Thu Feb 28 02:18:31 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832467 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 67DC013B5 for ; Thu, 28 Feb 2019 02:18:56 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 1F0A6297CF for ; Thu, 28 Feb 2019 02:18:56 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 108EE2D96C; Thu, 28 Feb 2019 02:18:56 +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 95FFE2E947 for ; Thu, 28 Feb 2019 02:18:55 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 9E49E8E0008; Wed, 27 Feb 2019 21:18:51 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 943FB8E0001; Wed, 27 Feb 2019 21:18:51 -0500 (EST) 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 85BDB8E0008; Wed, 27 Feb 2019 21:18:51 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by kanga.kvack.org (Postfix) with ESMTP id 586748E0001 for ; Wed, 27 Feb 2019 21:18:51 -0500 (EST) Received: by mail-qt1-f199.google.com with SMTP id k1so17385493qta.2 for ; Wed, 27 Feb 2019 18:18:51 -0800 (PST) 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=k81wrdCLr8miUfd7ykySbkmm4/3UN7J8vKeD0uvtXrQ=; b=X+FA7StT2C6iwOSuqF4nOaSAE9U2ak3VDwnwgoPqK1uRBY7l1v8agPnXt2OoCC+01g ldx29oYIDbGOVp+1wsOPxeqVtN8BPikzdALWxIycbJ+J5roV2ooGKNqlhX0ledAh5AdR 6fHpJLYxQ9w0LXMyMig9YOjo1OY2/ick+fLvlCcNKsTvk05d9jXnZOgkTjYBtWs8AB1N mVLVaa+dx8revQEsFaHhm/P6IKngCTl78bh9p5XZvjDZH+7EL1zMOhlt0Vvl17RVy5Ut 3WpeEXZZWRxTsQBWwjVLcBjfDGUqBsw9a3PeiNMf5ZYgBRIqOnwAyUIFOJZceAER2cl2 iX/Q== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: APjAAAXAvhRPq1V8VOPdBWtdfK3UvT0nFXpzfk7CpRUpyDlLqHKL5028 HqcQim/vzpCdebXGTYdflViBTHNMWqPkJ6K6vFYPFN/3Uuwh+SOv0YvL6ttK2nMiRtophcVjYjy LTCnR+VpjrXnalKo4m3iYP8I8+skp4jsPy8gUVFFYjk01yU+5iBRDPnUeeC0xITn9NIz0/XU+eW O2TiHDcaEUxvoONOV6Yx6P23eed64ISwAO8mDCuJ0IV82rU1OEqwOu5P305loCYpKBa3yarzYjX 1+TcyotEnK+uoaXgtgfAU8F2yzhEvXPsqDa8nFmracNmyDPPv1Nkr3gpKnQhtSRWK55kXoFyoH5 1XfmtdsPw6dE7HXyUVDp82dtWfFYFox6U85qb57DSU4GGRCxKsOhv2kV8StZ9xJWu30TQ0OrmQ= = X-Received: by 2002:aed:3b13:: with SMTP id p19mr4477578qte.128.1551320331147; Wed, 27 Feb 2019 18:18:51 -0800 (PST) X-Received: by 2002:aed:3b13:: with SMTP id p19mr4477528qte.128.1551320329959; Wed, 27 Feb 2019 18:18:49 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320329; cv=none; d=google.com; s=arc-20160816; b=A2+HlmvqzvcWObvblMNG+pwExGnvP7XUEaioOnu5Rv6nhwz0HQOXiiAw5ZhS7BM0kW oJVvlTEi1OjFw6mCLWUol59uv7v6xxgD3unUSVPqyVO6fuFRXdHcsp67ae343iUQdvjl 16ujBnpjDFqYivha3BLCOBXZWGqtQGLP2BvpUtInnoRCtMIKA63FtozzxQMz4DPVJBfl v+3e+EULOuSlkPCgzhxcGoWTa/uQPK24czF4hNi6bCXMIoguJPZuLfvkTi0d2uYd31BJ 1XlhatFZIH+qpav9nhzdra0oJuypIgLIZI0y0J/+X/nbSlxlUv14fidSWhc9JWU9Hk3T RLaQ== 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=k81wrdCLr8miUfd7ykySbkmm4/3UN7J8vKeD0uvtXrQ=; b=sACfi5a28gTRNw3OCvk7EMwMHTw4YSSSUf0eGXI4pvzGN70yAQGzShCca1tuH6oUF7 wFTO4I5oZkhC+dojhhacuXHmCf/csd6VfFCjoysOfzQBamrRpXX5REjXpJ59rSVOsn7d 60hxFXn40HLl7D6kee6lPg8CAAfK87lnf/FFbPsqethAsDu3pl4StbUPf/r4fZBA2w46 jMbGruAR2zf0jmA5DIQkqlVsHEDlgZKaPZjdF1gfQZUonimNXKeOR0YZgq6x+HSFmWT3 hMpAURMWWCJHpo+HoxQczwPp1mIzKN0IbKZ5aoWztj2UPqOfLwCfdf9uR2Vccz3/22SO 7yTg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id e10sor10735730qka.48.2019.02.27.18.18.49 for (Google Transport Security); Wed, 27 Feb 2019 18:18:49 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: AHgI3IaWHXCkHr163XI+GDm51zWvCsu6nT3A6974OMkRlq4SeFTjwbzw7uDMT4aauozctk1ouUES3A== X-Received: by 2002:a37:e40f:: with SMTP id y15mr4725411qkf.230.1551320329706; Wed, 27 Feb 2019 18:18:49 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.48 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:48 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 04/12] percpu: manage chunks based on contig_bits instead of free_bytes Date: Wed, 27 Feb 2019 21:18:31 -0500 Message-Id: <20190228021839.55779-5-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 When a chunk becomes fragmented, it can end up having a large number of small allocation areas free. The free_bytes sorting of chunks leads to unnecessary checking of chunks that cannot satisfy the allocation. Switch to contig_bits sorting to prevent scanning chunks that may not be able to service the allocation request. Signed-off-by: Dennis Zhou Reviewed-by: Peng Fan --- mm/percpu.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/mm/percpu.c b/mm/percpu.c index b40112b2fc59..c996bcffbb2a 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -234,7 +234,7 @@ static int pcpu_chunk_slot(const struct pcpu_chunk *chunk) if (chunk->free_bytes < PCPU_MIN_ALLOC_SIZE || chunk->contig_bits == 0) return 0; - return pcpu_size_to_slot(chunk->free_bytes); + return pcpu_size_to_slot(chunk->contig_bits * PCPU_MIN_ALLOC_SIZE); } /* set the pointer to a chunk in a page struct */ From patchwork Thu Feb 28 02:18:32 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832469 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 042CE17E9 for ; Thu, 28 Feb 2019 02:18:59 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E540B2DE2C for ; Thu, 28 Feb 2019 02:18:58 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id D6BBE2DEE1; Thu, 28 Feb 2019 02:18:58 +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 591852DE2C for ; Thu, 28 Feb 2019 02:18:58 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 1D2508E0009; Wed, 27 Feb 2019 21:18:53 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 12D818E0001; Wed, 27 Feb 2019 21:18:53 -0500 (EST) 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 0442E8E0009; Wed, 27 Feb 2019 21:18:53 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qk1-f197.google.com (mail-qk1-f197.google.com [209.85.222.197]) by kanga.kvack.org (Postfix) with ESMTP id CF1DD8E0001 for ; Wed, 27 Feb 2019 21:18:52 -0500 (EST) Received: by mail-qk1-f197.google.com with SMTP id b6so14910405qkg.4 for ; Wed, 27 Feb 2019 18:18:52 -0800 (PST) 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=O/uMqMX1RLXk35wATf5Bntd/FX1DZTwSKmJPgUmEjAI=; b=gtisTRX61DG8wJ1sKNqWFwVy/zd0/5PMRSbkmkRxlZPf5z43JHfZXGVmPiekr/DIxy plWJ66+XbloBQ+9W1CbLRVzGk22sExQQsYFH8YCBOmmmL8i2ToDpjbym2d0iiCiIcmW5 F4T2WwrsKrPxRrcoSDMDW1HsMH8Ibm44zb9sQEBNQ3AATJSo3R7QUpw7iYStwmGiRRM7 mjSMEkBkdIm/hgJlFpe8XOp0JfKkeCIBoADTVb6SySqKMqoakfK1KhljhnzJQXW8aIVM AY0FoJJX9rgKRAJ63qNrRGGGtrMmwEUFdRlPcuYqceVtc5kQIPhC0jVyRitFtALCKv5M Zo/A== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: APjAAAWnTFm2LDE/+Qugj3KBaKkolXqsQz+o2e2TnNAEkMUtzfGl3xo4 4fM+oUy8sCsnuvQieveoAm9gjjqK5GqxaHVB+A05y6c+qLdZUppol6HnQoK1usWEQbbm6EVtHU2 QVZRifDGY9LtsvsWGiXbWQaCZuyDhZ8M18E8aMCKEOVXr0u2Lc1RFm9pP+dW/RmOcuVgJq2OLId 3NQxIDZbOmreGwyHzZWnbyn/CMJZGfCNdRjbAkDqVESxJuKwyBma3z68GmIFBnMarliz/aLh4uk +9BuoHZi5ar2RCv/z34EMP9orrJ9IUnacN4pjhsuJTxBkKf9efYvAWaXdTllf3BJ1b+Zf6CgwJI S9JS6WfZUlUVY6nV9+w1H7k+4vcs+MVltIPFuSzM+XlVHEN3HgNyyXxSAX2eyQa43OliTk7SJw= = X-Received: by 2002:a0c:94cf:: with SMTP id k15mr4534148qvk.55.1551320332607; Wed, 27 Feb 2019 18:18:52 -0800 (PST) X-Received: by 2002:a0c:94cf:: with SMTP id k15mr4534100qvk.55.1551320331465; Wed, 27 Feb 2019 18:18:51 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320331; cv=none; d=google.com; s=arc-20160816; b=kFSneJFsAWT2nrtqekpsefiP1XMI5ExRewzVIzNkgIh/jhSSoK088vVVUXVFV4k5Q+ NmKyr8XA9kmwSlTaKjsKaaipH2W8ZXekjbmphRaC4MBCk/kqDinfKb9TihzyIS1GFQGk +Ox3sID+PDd2//IEB37b7Ew4wDXbBoL+sMDtGdPS+y6fn2nFgUT6h9lS5F8PpjTE9yEA iryFv//EDqxtkLSIO3Uk/j14QxOz0RPLc85R8GHuSETuYitcYnE/wXN7sDtw7NVhRx+i gWKheJ5XFD9fq6L5/egtZuf1seD+AfMoWDDOPNjTL5rrB1hO7B0Ogt5khsYvfaYWffyI Rb7w== 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=O/uMqMX1RLXk35wATf5Bntd/FX1DZTwSKmJPgUmEjAI=; b=Yp+dTE1PhNmgQKndnxjuHTSL2GA/sKw1pbDV23WeHwiXXhbtiZH0AgpUSWD2LzPCVg TMVXKLUXxlwZqVTGMd58E9lW8mbf7oyEcO8U70OatTFZlgELer+fifEikBqMovTwB/rN BYD+A2OyoLOqGNhJNDI7jk2MtQT2sxC60wK2TVZoJR5QCLyibhbsgs6JYLiTkUcNaUTu YgSACefFUJKEdcEmEsqWF5OnesoUaKl9VWHsjwLsbonJlm+Nn+34k2+hVSwpdayT9ML6 jKFGdE4UcOhMKppHzkxJuxhOzjc8zlkzqhLl6Hk8KPJr+p91RuREDveiDQrYuSlBfIPo W+Mg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id n4sor6235267qki.21.2019.02.27.18.18.51 for (Google Transport Security); Wed, 27 Feb 2019 18:18:51 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: AHgI3IYECaM0BaxRf5kUox7pcWekLOEUD4uDb49QmaHf/LLer2jiYKA1I5O2KDyJ1YPW/ofrNvgcaQ== X-Received: by 2002:a37:d6c6:: with SMTP id p67mr4570900qkl.329.1551320331211; Wed, 27 Feb 2019 18:18:51 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.49 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:50 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 05/12] percpu: relegate chunks unusable when failing small allocations Date: Wed, 27 Feb 2019 21:18:32 -0500 Message-Id: <20190228021839.55779-6-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 In certain cases, requestors of percpu memory may want specific alignments. However, it is possible to end up in situations where the contig_hint matches, but the alignment does not. This causes excess scanning of chunks that will fail. To prevent this, if a small allocation fails (< 32B), the chunk is moved to the empty list. Once an allocation is freed from that chunk, it is placed back into rotation. Signed-off-by: Dennis Zhou --- mm/percpu.c | 35 ++++++++++++++++++++++++++--------- 1 file changed, 26 insertions(+), 9 deletions(-) diff --git a/mm/percpu.c b/mm/percpu.c index c996bcffbb2a..3d7deece9556 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -94,6 +94,8 @@ /* the slots are sorted by free bytes left, 1-31 bytes share the same slot */ #define PCPU_SLOT_BASE_SHIFT 5 +/* chunks in slots below this are subject to being sidelined on failed alloc */ +#define PCPU_SLOT_FAIL_THRESHOLD 3 #define PCPU_EMPTY_POP_PAGES_LOW 2 #define PCPU_EMPTY_POP_PAGES_HIGH 4 @@ -488,6 +490,22 @@ static void pcpu_mem_free(void *ptr) kvfree(ptr); } +static void __pcpu_chunk_move(struct pcpu_chunk *chunk, int slot, + bool move_front) +{ + if (chunk != pcpu_reserved_chunk) { + if (move_front) + list_move(&chunk->list, &pcpu_slot[slot]); + else + list_move_tail(&chunk->list, &pcpu_slot[slot]); + } +} + +static void pcpu_chunk_move(struct pcpu_chunk *chunk, int slot) +{ + __pcpu_chunk_move(chunk, slot, true); +} + /** * pcpu_chunk_relocate - put chunk in the appropriate chunk slot * @chunk: chunk of interest @@ -505,12 +523,8 @@ static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot) { int nslot = pcpu_chunk_slot(chunk); - if (chunk != pcpu_reserved_chunk && oslot != nslot) { - if (oslot < nslot) - list_move(&chunk->list, &pcpu_slot[nslot]); - else - list_move_tail(&chunk->list, &pcpu_slot[nslot]); - } + if (oslot != nslot) + __pcpu_chunk_move(chunk, nslot, oslot < nslot); } /** @@ -1381,7 +1395,7 @@ static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved, bool is_atomic = (gfp & GFP_KERNEL) != GFP_KERNEL; bool do_warn = !(gfp & __GFP_NOWARN); static int warn_limit = 10; - struct pcpu_chunk *chunk; + struct pcpu_chunk *chunk, *next; const char *err; int slot, off, cpu, ret; unsigned long flags; @@ -1443,11 +1457,14 @@ static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved, restart: /* search through normal chunks */ for (slot = pcpu_size_to_slot(size); slot < pcpu_nr_slots; slot++) { - list_for_each_entry(chunk, &pcpu_slot[slot], list) { + list_for_each_entry_safe(chunk, next, &pcpu_slot[slot], list) { off = pcpu_find_block_fit(chunk, bits, bit_align, is_atomic); - if (off < 0) + if (off < 0) { + if (slot < PCPU_SLOT_FAIL_THRESHOLD) + pcpu_chunk_move(chunk, 0); continue; + } off = pcpu_alloc_area(chunk, bits, bit_align, off); if (off >= 0) From patchwork Thu Feb 28 02:18:33 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832471 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 82A8A17E9 for ; Thu, 28 Feb 2019 02:19:02 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 6DA422C7F1 for ; Thu, 28 Feb 2019 02:19:02 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 619A22CB5A; Thu, 28 Feb 2019 02:19:02 +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 60EE72C7F1 for ; Thu, 28 Feb 2019 02:19:01 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 330A78E000A; Wed, 27 Feb 2019 21:18:55 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 2DE228E0001; Wed, 27 Feb 2019 21:18:55 -0500 (EST) 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 1F6408E000A; Wed, 27 Feb 2019 21:18:55 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) by kanga.kvack.org (Postfix) with ESMTP id E087A8E0001 for ; Wed, 27 Feb 2019 21:18:54 -0500 (EST) Received: by mail-qt1-f197.google.com with SMTP id k1so17385605qta.2 for ; Wed, 27 Feb 2019 18:18:54 -0800 (PST) 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=2UFbqY461brc1FjkureY/Gfr31p0F1luW2ekNOMU524=; b=Zq02QsUaqYLmDvGA4eUyMiQYSde9Pe7pWXYWXyLqEoATK63ucMNC+IddQnPJ/7FOX+ eyqB3cjQw3ZqK1Z07+bhx+maHDRBYU4iIkqU9eXTfgoHJdeD+1S89GlFpF9A/8GhWIX/ UZgDLZbMc6f+cG495j1mA89gBGPxRMUOmF8H9M23imF6DWw5AZWUc/60yg5dKcIv4KLF uyLmjdOpQgfmMZrmDVfRxfdZmyaaX30DWtCP2mlrg69VIpw3hteoX4vi6IeXOgL4cLns w9Uy3ENYKVsjqPkNQ8hM+KNdPzGbSK0rczbSnU+/qQKexJ0G90xYFNvkcCNM70iLXOa0 L82A== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: APjAAAW66J3h0TnxoKRxTB/djVhAQem6OS3dvhMZT9Qx5teqZk7VwJwD CefMMK927wz64ISnZF3lQC7mSq5iDuhcPLXNG3H7rjls0nk3Tui64Am+byqOEjo3ss+jBGg5LHa t/jz2SyWzOL+35xm6yihWh3RyUCtNlZ1WnJZ5iyP5jUy7AdECwxbB6r8OSe6D2TZmoV6Qv2/IIe aIzP5s+gbXAmTdoi5B0Y/DcMthXBsTYDrGI7w3sdXYryDzi6UCqqQN37J07XN/bK+7Bc6P1/qXX n0ziCRuFekf0cm4KazTgv+USE4BenjIujcrwXaanNW9sqTRO/seCHxHEe/+L11jHP6+vqKFu+f0 d82szE1iua6J44UsNkAGoJgT1nXs76hQ9HYWtAKPe1pT0CVMiYwRobh/mUC1xW6CwO6wR78fvg= = X-Received: by 2002:a37:2d82:: with SMTP id t124mr4423883qkh.189.1551320334648; Wed, 27 Feb 2019 18:18:54 -0800 (PST) X-Received: by 2002:a37:2d82:: with SMTP id t124mr4423845qkh.189.1551320333211; Wed, 27 Feb 2019 18:18:53 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320333; cv=none; d=google.com; s=arc-20160816; b=KdkJq3EnVWcwRTog4ea3v10/FAFqauHTaIomjNashQsAVq4g+Ur4ZJsuns/rBXxcZN 5VLmASY/L3BIIY6dIZznBP9CmWa4FZrbPNRQxzVRwJ69PFkLDKhpNmM+jEzkwAR4CtOz cvpB/prw6tIYmixPiytqQLybCNaiZ3Uzdkl/8XJpGnH/W/kT2/WMAGrt1sfNC9GGh7Vb 0OSzV8ZPAyf+MPbUwqsVsu3OYYXAzMJCUQonNSgrjB1lzaE61gTIgPxYADKfXgzFe6QB 7rBSAiAkmEo7JsiXsu2xvu2TM4xH7XMxi+DUmjkRyXKPTghR1ZO9QjzW3gt91Ajlyr5W zA1Q== 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=2UFbqY461brc1FjkureY/Gfr31p0F1luW2ekNOMU524=; b=tdintd97NY+wdlHHudGJYuEba85kKnKcIGib29G3FkKkfDxHCbfMhDgXAuZFIhvV6V 4ROCLfzhNL6XoENoTXpHvxYEAvkNmrCmavstfATaDtAT1DaG/rycT0sb/01bzs8B9MWv I+Y9V6MRYYfv5nywU3cl2vo3Ullu/VkPKQ8+wU00OEG7Q4t4KuUbzCt92ZxJS0d9ydQf c0OHaSXlM6sOrUT3xejTR9fCoM3o0QGxuPdhPsQJhFDAwJmlrm1Co00knACWP1ZtyAFf ydHnr2P70BTzZAUd4Hyh3wpxOdEFGT+jgDcY21Sh/Rz0F8Y+im3pfJ+Is1iRynXubcgk wz1Q== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id m34sor13959730qtc.49.2019.02.27.18.18.53 for (Google Transport Security); Wed, 27 Feb 2019 18:18:53 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: APXvYqy7SfzqTS2eC6N4NJPS3aEmzBOCrx29EFkHxyf98XFxuUO5ukJK8ov1LOZtSqC2rkGFcsVCeg== X-Received: by 2002:ac8:34ae:: with SMTP id w43mr4467741qtb.145.1551320332727; Wed, 27 Feb 2019 18:18:52 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.51 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:51 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 06/12] percpu: set PCPU_BITMAP_BLOCK_SIZE to PAGE_SIZE Date: Wed, 27 Feb 2019 21:18:33 -0500 Message-Id: <20190228021839.55779-7-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 Previously, block size was flexible based on the constraint that the GCD(PCPU_BITMAP_BLOCK_SIZE, PAGE_SIZE) > 1. However, this carried the overhead that keeping a floating number of populated free pages required scanning over the free regions of a chunk. Setting the block size to be fixed at PAGE_SIZE lets us know when an empty page becomes used as we will break a full contig_hint of a block. This means we no longer have to scan the whole chunk upon breaking a contig_hint which empty page management piggybacks off. A later patch takes advantage of this to optimize the allocation path by only scanning forward using the scan_hint introduced later too. Signed-off-by: Dennis Zhou Reviewed-by: Peng Fan --- include/linux/percpu.h | 12 ++--- mm/percpu-km.c | 2 +- mm/percpu.c | 111 +++++++++++++++++------------------------ 3 files changed, 49 insertions(+), 76 deletions(-) diff --git a/include/linux/percpu.h b/include/linux/percpu.h index 70b7123f38c7..9909dc0e273a 100644 --- a/include/linux/percpu.h +++ b/include/linux/percpu.h @@ -26,16 +26,10 @@ #define PCPU_MIN_ALLOC_SHIFT 2 #define PCPU_MIN_ALLOC_SIZE (1 << PCPU_MIN_ALLOC_SHIFT) -/* number of bits per page, used to trigger a scan if blocks are > PAGE_SIZE */ -#define PCPU_BITS_PER_PAGE (PAGE_SIZE >> PCPU_MIN_ALLOC_SHIFT) - /* - * This determines the size of each metadata block. There are several subtle - * constraints around this constant. The reserved region must be a multiple of - * PCPU_BITMAP_BLOCK_SIZE. Additionally, PCPU_BITMAP_BLOCK_SIZE must be a - * multiple of PAGE_SIZE or PAGE_SIZE must be a multiple of - * PCPU_BITMAP_BLOCK_SIZE to align with the populated page map. The unit_size - * also has to be a multiple of PCPU_BITMAP_BLOCK_SIZE to ensure full blocks. + * The PCPU_BITMAP_BLOCK_SIZE must be the same size as PAGE_SIZE as the + * updating of hints is used to manage the nr_empty_pop_pages in both + * the chunk and globally. */ #define PCPU_BITMAP_BLOCK_SIZE PAGE_SIZE #define PCPU_BITMAP_BLOCK_BITS (PCPU_BITMAP_BLOCK_SIZE >> \ diff --git a/mm/percpu-km.c b/mm/percpu-km.c index 0f643dc2dc65..c10bf7466596 100644 --- a/mm/percpu-km.c +++ b/mm/percpu-km.c @@ -70,7 +70,7 @@ static struct pcpu_chunk *pcpu_create_chunk(gfp_t gfp) chunk->base_addr = page_address(pages) - pcpu_group_offsets[0]; spin_lock_irqsave(&pcpu_lock, flags); - pcpu_chunk_populated(chunk, 0, nr_pages, false); + pcpu_chunk_populated(chunk, 0, nr_pages); spin_unlock_irqrestore(&pcpu_lock, flags); pcpu_stats_chunk_alloc(); diff --git a/mm/percpu.c b/mm/percpu.c index 3d7deece9556..967c9cc3a928 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -527,37 +527,21 @@ static void pcpu_chunk_relocate(struct pcpu_chunk *chunk, int oslot) __pcpu_chunk_move(chunk, nslot, oslot < nslot); } -/** - * pcpu_cnt_pop_pages- counts populated backing pages in range +/* + * pcpu_update_empty_pages - update empty page counters * @chunk: chunk of interest - * @bit_off: start offset - * @bits: size of area to check + * @nr: nr of empty pages * - * Calculates the number of populated pages in the region - * [page_start, page_end). This keeps track of how many empty populated - * pages are available and decide if async work should be scheduled. - * - * RETURNS: - * The nr of populated pages. + * This is used to keep track of the empty pages now based on the premise + * a pcpu_block_md covers a page. The hint update functions recognize if + * a block is made full or broken to calculate deltas for keeping track of + * free pages. */ -static inline int pcpu_cnt_pop_pages(struct pcpu_chunk *chunk, int bit_off, - int bits) +static inline void pcpu_update_empty_pages(struct pcpu_chunk *chunk, int nr) { - int page_start = PFN_UP(bit_off * PCPU_MIN_ALLOC_SIZE); - int page_end = PFN_DOWN((bit_off + bits) * PCPU_MIN_ALLOC_SIZE); - - if (page_start >= page_end) - return 0; - - /* - * bitmap_weight counts the number of bits set in a bitmap up to - * the specified number of bits. This is counting the populated - * pages up to page_end and then subtracting the populated pages - * up to page_start to count the populated pages in - * [page_start, page_end). - */ - return bitmap_weight(chunk->populated, page_end) - - bitmap_weight(chunk->populated, page_start); + chunk->nr_empty_pop_pages += nr; + if (chunk != pcpu_reserved_chunk) + pcpu_nr_empty_pop_pages += nr; } /* @@ -611,36 +595,19 @@ static void pcpu_chunk_update(struct pcpu_chunk *chunk, int bit_off, int bits) * Updates: * chunk->contig_bits * chunk->contig_bits_start - * nr_empty_pop_pages (chunk and global) */ static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk) { - int bit_off, bits, nr_empty_pop_pages; + int bit_off, bits; /* clear metadata */ chunk->contig_bits = 0; bit_off = chunk->first_bit; - bits = nr_empty_pop_pages = 0; + bits = 0; pcpu_for_each_md_free_region(chunk, bit_off, bits) { pcpu_chunk_update(chunk, bit_off, bits); - - nr_empty_pop_pages += pcpu_cnt_pop_pages(chunk, bit_off, bits); } - - /* - * Keep track of nr_empty_pop_pages. - * - * The chunk maintains the previous number of free pages it held, - * so the delta is used to update the global counter. The reserved - * chunk is not part of the free page count as they are populated - * at init and are special to serving reserved allocations. - */ - if (chunk != pcpu_reserved_chunk) - pcpu_nr_empty_pop_pages += - (nr_empty_pop_pages - chunk->nr_empty_pop_pages); - - chunk->nr_empty_pop_pages = nr_empty_pop_pages; } /** @@ -712,6 +679,7 @@ static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index) static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, int bits) { + int nr_empty_pages = 0; struct pcpu_block_md *s_block, *e_block, *block; int s_index, e_index; /* block indexes of the freed allocation */ int s_off, e_off; /* block offsets of the freed allocation */ @@ -736,6 +704,9 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, * If the allocation breaks the contig_hint, a scan is required to * restore this hint. */ + if (s_block->contig_hint == PCPU_BITMAP_BLOCK_BITS) + nr_empty_pages++; + if (s_off == s_block->first_free) s_block->first_free = find_next_zero_bit( pcpu_index_alloc_map(chunk, s_index), @@ -763,6 +734,9 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, * Update e_block. */ if (s_index != e_index) { + if (e_block->contig_hint == PCPU_BITMAP_BLOCK_BITS) + nr_empty_pages++; + /* * When the allocation is across blocks, the end is along * the left part of the e_block. @@ -787,6 +761,7 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, } /* update in-between md_blocks */ + nr_empty_pages += (e_index - s_index - 1); for (block = s_block + 1; block < e_block; block++) { block->contig_hint = 0; block->left_free = 0; @@ -794,6 +769,9 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, } } + if (nr_empty_pages) + pcpu_update_empty_pages(chunk, -1 * nr_empty_pages); + /* * The only time a full chunk scan is required is if the chunk * contig hint is broken. Otherwise, it means a smaller space @@ -826,6 +804,7 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, int bits) { + int nr_empty_pages = 0; struct pcpu_block_md *s_block, *e_block, *block; int s_index, e_index; /* block indexes of the freed allocation */ int s_off, e_off; /* block offsets of the freed allocation */ @@ -879,14 +858,19 @@ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, /* update s_block */ e_off = (s_index == e_index) ? end : PCPU_BITMAP_BLOCK_BITS; + if (!start && e_off == PCPU_BITMAP_BLOCK_BITS) + nr_empty_pages++; pcpu_block_update(s_block, start, e_off); /* freeing in the same block */ if (s_index != e_index) { /* update e_block */ + if (end == PCPU_BITMAP_BLOCK_BITS) + nr_empty_pages++; pcpu_block_update(e_block, 0, end); /* reset md_blocks in the middle */ + nr_empty_pages += (e_index - s_index - 1); for (block = s_block + 1; block < e_block; block++) { block->first_free = 0; block->contig_hint_start = 0; @@ -896,15 +880,16 @@ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, } } + if (nr_empty_pages) + pcpu_update_empty_pages(chunk, nr_empty_pages); + /* - * Refresh chunk metadata when the free makes a page free, a block - * free, or spans across blocks. The contig hint may be off by up to - * a page, but if the hint is contained in a block, it will be accurate - * with the else condition below. + * Refresh chunk metadata when the free makes a block free or spans + * across blocks. The contig_hint may be off by up to a page, but if + * the contig_hint is contained in a block, it will be accurate with + * the else condition below. */ - if ((ALIGN_DOWN(end, min(PCPU_BITS_PER_PAGE, PCPU_BITMAP_BLOCK_BITS)) > - ALIGN(start, min(PCPU_BITS_PER_PAGE, PCPU_BITMAP_BLOCK_BITS))) || - s_index != e_index) + if (((end - start) >= PCPU_BITMAP_BLOCK_BITS) || s_index != e_index) pcpu_chunk_refresh_hint(chunk); else pcpu_chunk_update(chunk, pcpu_block_off_to_off(s_index, start), @@ -1164,9 +1149,7 @@ static struct pcpu_chunk * __init pcpu_alloc_first_chunk(unsigned long tmp_addr, chunk->immutable = true; bitmap_fill(chunk->populated, chunk->nr_pages); chunk->nr_populated = chunk->nr_pages; - chunk->nr_empty_pop_pages = - pcpu_cnt_pop_pages(chunk, start_offset / PCPU_MIN_ALLOC_SIZE, - map_size / PCPU_MIN_ALLOC_SIZE); + chunk->nr_empty_pop_pages = chunk->nr_pages; chunk->contig_bits = map_size / PCPU_MIN_ALLOC_SIZE; chunk->free_bytes = map_size; @@ -1261,7 +1244,6 @@ static void pcpu_free_chunk(struct pcpu_chunk *chunk) * @chunk: pcpu_chunk which got populated * @page_start: the start page * @page_end: the end page - * @for_alloc: if this is to populate for allocation * * Pages in [@page_start,@page_end) have been populated to @chunk. Update * the bookkeeping information accordingly. Must be called after each @@ -1271,7 +1253,7 @@ static void pcpu_free_chunk(struct pcpu_chunk *chunk) * is to serve an allocation in that area. */ static void pcpu_chunk_populated(struct pcpu_chunk *chunk, int page_start, - int page_end, bool for_alloc) + int page_end) { int nr = page_end - page_start; @@ -1281,10 +1263,7 @@ static void pcpu_chunk_populated(struct pcpu_chunk *chunk, int page_start, chunk->nr_populated += nr; pcpu_nr_populated += nr; - if (!for_alloc) { - chunk->nr_empty_pop_pages += nr; - pcpu_nr_empty_pop_pages += nr; - } + pcpu_update_empty_pages(chunk, nr); } /** @@ -1306,9 +1285,9 @@ static void pcpu_chunk_depopulated(struct pcpu_chunk *chunk, bitmap_clear(chunk->populated, page_start, nr); chunk->nr_populated -= nr; - chunk->nr_empty_pop_pages -= nr; - pcpu_nr_empty_pop_pages -= nr; pcpu_nr_populated -= nr; + + pcpu_update_empty_pages(chunk, -1 * nr); } /* @@ -1523,7 +1502,7 @@ static void __percpu *pcpu_alloc(size_t size, size_t align, bool reserved, err = "failed to populate"; goto fail_unlock; } - pcpu_chunk_populated(chunk, rs, re, true); + pcpu_chunk_populated(chunk, rs, re); spin_unlock_irqrestore(&pcpu_lock, flags); } @@ -1722,7 +1701,7 @@ static void pcpu_balance_workfn(struct work_struct *work) if (!ret) { nr_to_pop -= nr; spin_lock_irq(&pcpu_lock); - pcpu_chunk_populated(chunk, rs, rs + nr, false); + pcpu_chunk_populated(chunk, rs, rs + nr); spin_unlock_irq(&pcpu_lock); } else { nr_to_pop = 0; From patchwork Thu Feb 28 02:18:34 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832473 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 1444913B5 for ; Thu, 28 Feb 2019 02:19:05 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id EE0A62C7F1 for ; Thu, 28 Feb 2019 02:19:04 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id DCB222CB5A; Thu, 28 Feb 2019 02:19:04 +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 2781E2C7F1 for ; Thu, 28 Feb 2019 02:19:04 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2B6F28E000B; Wed, 27 Feb 2019 21:18:56 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 26A4C8E0001; Wed, 27 Feb 2019 21:18:56 -0500 (EST) 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 157D28E000B; Wed, 27 Feb 2019 21:18:56 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt1-f198.google.com (mail-qt1-f198.google.com [209.85.160.198]) by kanga.kvack.org (Postfix) with ESMTP id DDE1A8E0001 for ; Wed, 27 Feb 2019 21:18:55 -0500 (EST) Received: by mail-qt1-f198.google.com with SMTP id b40so17404551qte.1 for ; Wed, 27 Feb 2019 18:18:55 -0800 (PST) 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=OJpWsbdBIyGG6Z7ONuMnLcPyaANJkTqPOgPDMD+CsEE=; b=QiIGyvRwjpD4a7WQaaMg9ASMs704FYXRhoDgcFd2rrmrQOBVWVZxusv7PF9rHq1IJC hTBW3u+lsDq7UCX8ne95E+fjB3UJWU/ieTjz9hrUw/1FaygU/U3E2tBupik5IT6+d+iY kTJNd4CLH5T+qMShh+YwYwoHSPTnF7xSIP7CbENXoHtd4Gf7uw95jnFqDNsTimPkXLI4 V9nBTZHKCglRnwEGKUZKI40GO25cqGmcX2aEBHYMYxt9aXR5dDy1pg8cSwstNV+UJFMl r/H99VZiDTEGdO1zPgui+KDrfuH6bM2aKWY8uLGw7MnRtE0fFWmFdVBElseESMQQdcJQ NALw== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: AHQUAubmTwfDcFqmtuPVQoTIT73WxxzlwfUxZHgF+Ri3aYcdff8pbNgJ UnOpTrgkJOd7Q3ocaNwJQm/qkVyB7zodEMnAxlL3HhKG/JmIPYH9vC/Dt7YXOoAFeCJeqwfoozi Mx0tCtX0FjqnhITTJQESUcHQbgOJlGZK59RhEcK0sE0am4j0l4Yflt+IoyiW6IjMfX3ZGFDAtL8 0XkJwrSRqwqUCPzY8MTgmq4XHORgwisfIWWEcILP4bwmomrMH99F0xPAEX1NbJz/eVQi9qaSfmm JbhKgU1mhMxQH8dd3opOxr6mMcguhoNaxzYNnieoaUwgSG88Jl6mymboR8XXj2pN/20xQ3FIWXq zxgJIK6CWkplrGPvQsdhXTIqdD2bpwqDAfv6K3uQB87OxvdQxAkDJxVG3eQUjEwV9YoaQHWwog= = X-Received: by 2002:ac8:803:: with SMTP id u3mr4323354qth.108.1551320335653; Wed, 27 Feb 2019 18:18:55 -0800 (PST) X-Received: by 2002:ac8:803:: with SMTP id u3mr4323322qth.108.1551320334697; Wed, 27 Feb 2019 18:18:54 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320334; cv=none; d=google.com; s=arc-20160816; b=fv0V1K14Tpqvs8flq5CLMtRSIzVQVjCo0YyG5Z+3DBmblBJzHifU86p5+WatrbI+j8 NsKfpVMlpc2z4LbVKtRDzMEaw2fWPVuPFYNM973lYiEdz4wyZwRZGx6qdw5kbQBqj/nC 8DDyehytyLa5LT7P9jquDIlMP1NbsXSaSssCGFSVpKXtZ+kce2YyxvVpIR7y8AuuReIG GLMHPvBtoatyiczN73l5E9H1sMCT3OKOs3wEhbsIHfm1yGLaEuOvnwQ7TdX5TDNeE1lW j4yjcrFtHWhEfjYeiNNq+1NWlGjU6WSVEfBQrwG0RmI0bvtMEgPiGs5d1TQWDedRe1Lo iIEw== 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=OJpWsbdBIyGG6Z7ONuMnLcPyaANJkTqPOgPDMD+CsEE=; b=fuYO+5NyahreVpTDsays2xa9LQYSbbQmVBxEoEYVLp8MOtbevHrxJjSPydLdRqmh2p pg/BkiuOqQwh+kMl1wt3S0/wMxElyCNJxT/odlsFSPRIbInuk30vsJzLo8fq8B+MPzLs 820KPFZT8hZ3Dv9bG1e7JomrbpT19fmTcscaNZKRvKte84drhK7Mw5GRFAul90G1k1km kqxDTtq20gOh0qKpuWCx5HBg5PkYfD++2kDh7vZmDdXMCDwylpEQpAstk/Rsk0lCWCDd lTWqsJTDLU1RERum1I/JdOMHXBVl5IcIZGO8H4UN7v1LKDAeGviNmigD5INLdKDTtjy2 gAbA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id 39sor20029930qvk.54.2019.02.27.18.18.54 for (Google Transport Security); Wed, 27 Feb 2019 18:18:54 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: APXvYqxEf9YG/zZ2e72+bT/axnwcoZq+Gcmlr3nYUbo4CauEC6c/+4TlIkIgc9rbYfwL02WxjTt1hg== X-Received: by 2002:a0c:d0b6:: with SMTP id z51mr4431252qvg.20.1551320334375; Wed, 27 Feb 2019 18:18:54 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.52 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:53 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 07/12] percpu: add block level scan_hint Date: Wed, 27 Feb 2019 21:18:34 -0500 Message-Id: <20190228021839.55779-8-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 Fragmentation can cause both blocks and chunks to have an early first_firee bit available, but only able to satisfy allocations much later on. This patch introduces a scan_hint to help mitigate some unnecessary scanning. The scan_hint remembers the largest area prior to the contig_hint. If the contig_hint == scan_hint, then scan_hint_start > contig_hint_start. This is necessary for scan_hint discovery when refreshing a block. Signed-off-by: Dennis Zhou Reviewed-by: Peng Fan --- mm/percpu-internal.h | 9 ++++ mm/percpu.c | 101 ++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 103 insertions(+), 7 deletions(-) diff --git a/mm/percpu-internal.h b/mm/percpu-internal.h index b1739dc06b73..ec58b244545d 100644 --- a/mm/percpu-internal.h +++ b/mm/percpu-internal.h @@ -9,8 +9,17 @@ * pcpu_block_md is the metadata block struct. * Each chunk's bitmap is split into a number of full blocks. * All units are in terms of bits. + * + * The scan hint is the largest known contiguous area before the contig hint. + * It is not necessarily the actual largest contig hint though. There is an + * invariant that the scan_hint_start > contig_hint_start iff + * scan_hint == contig_hint. This is necessary because when scanning forward, + * we don't know if a new contig hint would be better than the current one. */ struct pcpu_block_md { + int scan_hint; /* scan hint for block */ + int scan_hint_start; /* block relative starting + position of the scan hint */ int contig_hint; /* contig hint for block */ int contig_hint_start; /* block relative starting position of the contig hint */ diff --git a/mm/percpu.c b/mm/percpu.c index 967c9cc3a928..df1aacf58ac8 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -320,6 +320,34 @@ static unsigned long pcpu_block_off_to_off(int index, int off) return index * PCPU_BITMAP_BLOCK_BITS + off; } +/* + * pcpu_next_hint - determine which hint to use + * @block: block of interest + * @alloc_bits: size of allocation + * + * This determines if we should scan based on the scan_hint or first_free. + * In general, we want to scan from first_free to fulfill allocations by + * first fit. However, if we know a scan_hint at position scan_hint_start + * cannot fulfill an allocation, we can begin scanning from there knowing + * the contig_hint will be our fallback. + */ +static int pcpu_next_hint(struct pcpu_block_md *block, int alloc_bits) +{ + /* + * The three conditions below determine if we can skip past the + * scan_hint. First, does the scan hint exist. Second, is the + * contig_hint after the scan_hint (possibly not true iff + * contig_hint == scan_hint). Third, is the allocation request + * larger than the scan_hint. + */ + if (block->scan_hint && + block->contig_hint_start > block->scan_hint_start && + alloc_bits > block->scan_hint) + return block->scan_hint_start + block->scan_hint; + + return block->first_free; +} + /** * pcpu_next_md_free_region - finds the next hint free area * @chunk: chunk of interest @@ -415,9 +443,11 @@ static void pcpu_next_fit_region(struct pcpu_chunk *chunk, int alloc_bits, if (block->contig_hint && block->contig_hint_start >= block_off && block->contig_hint >= *bits + alloc_bits) { + int start = pcpu_next_hint(block, alloc_bits); + *bits += alloc_bits + block->contig_hint_start - - block->first_free; - *bit_off = pcpu_block_off_to_off(i, block->first_free); + start; + *bit_off = pcpu_block_off_to_off(i, start); return; } /* reset to satisfy the second predicate above */ @@ -632,12 +662,57 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) block->right_free = contig; if (contig > block->contig_hint) { + /* promote the old contig_hint to be the new scan_hint */ + if (start > block->contig_hint_start) { + if (block->contig_hint > block->scan_hint) { + block->scan_hint_start = + block->contig_hint_start; + block->scan_hint = block->contig_hint; + } else if (start < block->scan_hint_start) { + /* + * The old contig_hint == scan_hint. But, the + * new contig is larger so hold the invariant + * scan_hint_start < contig_hint_start. + */ + block->scan_hint = 0; + } + } else { + block->scan_hint = 0; + } block->contig_hint_start = start; block->contig_hint = contig; - } else if (block->contig_hint_start && contig == block->contig_hint && - (!start || __ffs(start) > __ffs(block->contig_hint_start))) { - /* use the start with the best alignment */ - block->contig_hint_start = start; + } else if (contig == block->contig_hint) { + if (block->contig_hint_start && + (!start || + __ffs(start) > __ffs(block->contig_hint_start))) { + /* start has a better alignment so use it */ + block->contig_hint_start = start; + if (start < block->scan_hint_start && + block->contig_hint > block->scan_hint) + block->scan_hint = 0; + } else if (start > block->scan_hint_start || + block->contig_hint > block->scan_hint) { + /* + * Knowing contig == contig_hint, update the scan_hint + * if it is farther than or larger than the current + * scan_hint. + */ + block->scan_hint_start = start; + block->scan_hint = contig; + } + } else { + /* + * The region is smaller than the contig_hint. So only update + * the scan_hint if it is larger than or equal and farther than + * the current scan_hint. + */ + if ((start < block->contig_hint_start && + (contig > block->scan_hint || + (contig == block->scan_hint && + start > block->scan_hint_start)))) { + block->scan_hint_start = start; + block->scan_hint = contig; + } } } @@ -656,7 +731,7 @@ static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index) int rs, re; /* region start, region end */ /* clear hints */ - block->contig_hint = 0; + block->contig_hint = block->scan_hint = 0; block->left_free = block->right_free = 0; /* iterate over free areas and update the contig hints */ @@ -713,6 +788,12 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, PCPU_BITMAP_BLOCK_BITS, s_off + bits); + if (pcpu_region_overlap(s_block->scan_hint_start, + s_block->scan_hint_start + s_block->scan_hint, + s_off, + s_off + bits)) + s_block->scan_hint = 0; + if (pcpu_region_overlap(s_block->contig_hint_start, s_block->contig_hint_start + s_block->contig_hint, @@ -749,6 +830,9 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, /* reset the block */ e_block++; } else { + if (e_off > e_block->scan_hint_start) + e_block->scan_hint = 0; + if (e_off > e_block->contig_hint_start) { /* contig hint is broken - scan to fix it */ pcpu_block_refresh_hint(chunk, e_index); @@ -763,6 +847,7 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, /* update in-between md_blocks */ nr_empty_pages += (e_index - s_index - 1); for (block = s_block + 1; block < e_block; block++) { + block->scan_hint = 0; block->contig_hint = 0; block->left_free = 0; block->right_free = 0; @@ -873,6 +958,7 @@ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, nr_empty_pages += (e_index - s_index - 1); for (block = s_block + 1; block < e_block; block++) { block->first_free = 0; + block->scan_hint = 0; block->contig_hint_start = 0; block->contig_hint = PCPU_BITMAP_BLOCK_BITS; block->left_free = PCPU_BITMAP_BLOCK_BITS; @@ -1084,6 +1170,7 @@ static void pcpu_init_md_blocks(struct pcpu_chunk *chunk) for (md_block = chunk->md_blocks; md_block != chunk->md_blocks + pcpu_chunk_nr_blocks(chunk); md_block++) { + md_block->scan_hint = 0; md_block->contig_hint = PCPU_BITMAP_BLOCK_BITS; md_block->left_free = PCPU_BITMAP_BLOCK_BITS; md_block->right_free = PCPU_BITMAP_BLOCK_BITS; From patchwork Thu Feb 28 02:18:35 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832475 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 062F217E9 for ; Thu, 28 Feb 2019 02:19:08 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id E7F1F2C7F1 for ; Thu, 28 Feb 2019 02:19:07 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id DB2312CB5A; Thu, 28 Feb 2019 02:19:07 +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 3D9292C7F1 for ; Thu, 28 Feb 2019 02:19:07 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id BBB7C8E0003; Wed, 27 Feb 2019 21:18:57 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id B3F5D8E0001; Wed, 27 Feb 2019 21:18:57 -0500 (EST) 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 A34238E0003; Wed, 27 Feb 2019 21:18:57 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by kanga.kvack.org (Postfix) with ESMTP id 719AF8E0001 for ; Wed, 27 Feb 2019 21:18:57 -0500 (EST) Received: by mail-qk1-f199.google.com with SMTP id n197so14918923qke.0 for ; Wed, 27 Feb 2019 18:18:57 -0800 (PST) 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=oDNiSsuPdsF/XOcfjzvj8LVYLn1xaHI/O2WR5uD3c+0=; b=M8XvkKiozDKde098DTMUNR1fr5dDnebJH+Xv9aiysM0Qvf5f8lQBpdLrZIkIgGp6zL dlgdT1xWAkNm11I/uPjpq7TVbs6vOCw4c9c2fNjO7mZ9MC5UzTT8o+SLedUFXSGtqERX jVkkGAlJ3Tf5oZrR9umNehKEY9DCw4H5onSzoPNPsqaV+2dLa5ac1dyn91ybTry22C7S EsnAWFFgfzOy/a4I9eBASCnA5YXKz7J6DyLnj+VFUrSc8eY2vNo7ys0dxB+JwtTmq9jW LnKVsfApArXf/2v2SmDVZVQaWpgYLypnhlfPdHfUlwAN8CYkbULVukq00WYqI3NlAJQF yMww== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: AHQUAubjvBq1EKXbg4qUrCYJjhzRkduXW+mIW/gNYMfzbI+Gim9CxLRC Paud+moh2VasytnmEhhAIOawHr9vfsS3LzdJjx2U57t/iF/ejVBWfmBqXw4eIIVuWIOz6ijSimd rNi59VP7fJfNVsVH0T+dGYHpegMLFDY0E6s5PWsgluCnpjbWjl+nwe7yGFWTkOIWedz7WevPwlF 8C8uFyRAivb2SUQrbU5WYLhx5UO1cRalz+fkhSVTrZGL89/G8feeXNaa17aEH8bvru+RpEbUJxr 7FvdmHmtifUzmpv7O5Q4jcIZ4fFwUlHs53Dn37Z72Yfr9o61PY6HqmxJZQcQ3QQHj7Cikh9ahCl l08UeeKB+Q45YL8uJ4+R4pf03qEZgRb8eqau1/pTP7B6zSpGB0LzmRx2aTcPO5TS08kpZsCD4w= = X-Received: by 2002:a37:b12:: with SMTP id 18mr4644401qkl.125.1551320337148; Wed, 27 Feb 2019 18:18:57 -0800 (PST) X-Received: by 2002:a37:b12:: with SMTP id 18mr4644373qkl.125.1551320336241; Wed, 27 Feb 2019 18:18:56 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320336; cv=none; d=google.com; s=arc-20160816; b=ltMP9A26zUpDUfurW9U/Ycx+yGkd257QuvnCkImG6fnXX14/sINK9LF67hNIcoi6e3 Hbol83ujtKxbieQlVpakw2SX81px4+btNeOgrnqAULHhyRC837oAjr2M5SRT1kfXhDcA v0Y3rFzoQNOYz6z71DbZ/0NPt86WJ78Pi9bSE+10fpaLYf9TBEG4T7+DeGHR/wcfMo/2 xdP4PWF88QqapBZT+snRvNRw53VNh6puDDQ0+fP4VjTIBWKLyaz5B64whwaQl7VOC2wp 3dVUmGEnGAd3POsMsrZHOj3mng7ZJW91hoP/j9p3teUaFGqejk9dol1TDZZ+EPAYdkwi /ARg== 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=oDNiSsuPdsF/XOcfjzvj8LVYLn1xaHI/O2WR5uD3c+0=; b=nGKU8iJTRg3tGFjSSQJRdQ1hhr8zi2pWypSlpevdFQNWbqHsCCB2blYTRx7Kzya6np ii7rWtItE0Wg+0ssVPiTariQda92QIPFzipi0+TuurlB4+f1nmVl8FW7MEk+sAgMYYF6 YBPqNcNtOyB1E4V2GFUMArJgOQMk24GSGcmTaE23KEyNXF5wunrEXvD2tb8l6FFLeMK7 8IER4MTgwdaE1a7Y9ljdya4QlZhh9JFnSdHydbGhedvFQdH00fOLs5CCHKPlh+Wu6Yae NEXU3i+SWYGWEGIVO47XrFi4ZxWo3AU9in10ISOLsPl71cyA6jacdI+SV7UbqIOXcGvh 4yYg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id q23sor10846020qkc.142.2019.02.27.18.18.56 for (Google Transport Security); Wed, 27 Feb 2019 18:18:56 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: APXvYqyYBVI/T7ds+Dzo/USUVcDodJI0nlbspO0X1XTek/TSd9ZKWp/VHGFig0uB1cuf3Gy8qdZb3A== X-Received: by 2002:a37:c097:: with SMTP id v23mr4655782qkv.62.1551320335886; Wed, 27 Feb 2019 18:18:55 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.54 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:55 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 08/12] percpu: remember largest area skipped during allocation Date: Wed, 27 Feb 2019 21:18:35 -0500 Message-Id: <20190228021839.55779-9-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 Percpu allocations attempt to do first fit by scanning forward from the first_free of a block. However, fragmentation from allocation requests can cause holes not seen by block hint update functions. To address this, create a local version of bitmap_find_next_zero_area_off() that remembers the largest area skipped over. The caveat is that it only sees regions skipped over due to not fitting, not regions skipped due to alignment. Prior to updating the scan_hint, a scan backwards is done to try and recover free bits skipped due to alignment. While this can cause scanning to miss earlier possible free areas, smaller allocations will eventually fill those holes. Signed-off-by: Dennis Zhou --- mm/percpu.c | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 99 insertions(+), 2 deletions(-) diff --git a/mm/percpu.c b/mm/percpu.c index df1aacf58ac8..dac18968d79f 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -716,6 +716,43 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) } } +/* + * pcpu_block_update_scan - update a block given a free area from a scan + * @chunk: chunk of interest + * @bit_off: chunk offset + * @bits: size of free area + * + * Finding the final allocation spot first goes through pcpu_find_block_fit() + * to find a block that can hold the allocation and then pcpu_alloc_area() + * where a scan is used. When allocations require specific alignments, + * we can inadvertently create holes which will not be seen in the alloc + * or free paths. + * + * This takes a given free area hole and updates a block as it may change the + * scan_hint. We need to scan backwards to ensure we don't miss free bits + * from alignment. + */ +static void pcpu_block_update_scan(struct pcpu_chunk *chunk, int bit_off, + int bits) +{ + int s_off = pcpu_off_to_block_off(bit_off); + int e_off = s_off + bits; + int s_index, l_bit; + struct pcpu_block_md *block; + + if (e_off > PCPU_BITMAP_BLOCK_BITS) + return; + + s_index = pcpu_off_to_block_index(bit_off); + block = chunk->md_blocks + s_index; + + /* scan backwards in case of alignment skipping free bits */ + l_bit = find_last_bit(pcpu_index_alloc_map(chunk, s_index), s_off); + s_off = (s_off == l_bit) ? 0 : l_bit + 1; + + pcpu_block_update(block, s_off, e_off); +} + /** * pcpu_block_refresh_hint * @chunk: chunk of interest @@ -1064,6 +1101,62 @@ static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int alloc_bits, return bit_off; } +/* + * pcpu_find_zero_area - modified from bitmap_find_next_zero_area_off + * @map: the address to base the search on + * @size: the bitmap size in bits + * @start: the bitnumber to start searching at + * @nr: the number of zeroed bits we're looking for + * @align_mask: alignment mask for zero area + * @largest_off: offset of the largest area skipped + * @largest_bits: size of the largest area skipped + * + * The @align_mask should be one less than a power of 2. + * + * This is a modified version of bitmap_find_next_zero_area_off() to remember + * the largest area that was skipped. This is imperfect, but in general is + * good enough. The largest remembered region is the largest failed region + * seen. This does not include anything we possibly skipped due to alignment. + * pcpu_block_update_scan() does scan backwards to try and recover what was + * lost to alignment. While this can cause scanning to miss earlier possible + * free areas, smaller allocations will eventually fill those holes. + */ +static unsigned long pcpu_find_zero_area(unsigned long *map, + unsigned long size, + unsigned long start, + unsigned long nr, + unsigned long align_mask, + unsigned long *largest_off, + unsigned long *largest_bits) +{ + unsigned long index, end, i, area_off, area_bits; +again: + index = find_next_zero_bit(map, size, start); + + /* Align allocation */ + index = __ALIGN_MASK(index, align_mask); + area_off = index; + + end = index + nr; + if (end > size) + return end; + i = find_next_bit(map, end, index); + if (i < end) { + area_bits = i - area_off; + /* remember largest unused area with best alignment */ + if (area_bits > *largest_bits || + (area_bits == *largest_bits && *largest_off && + (!area_off || __ffs(area_off) > __ffs(*largest_off)))) { + *largest_off = area_off; + *largest_bits = area_bits; + } + + start = i + 1; + goto again; + } + return index; +} + /** * pcpu_alloc_area - allocates an area from a pcpu_chunk * @chunk: chunk of interest @@ -1087,6 +1180,7 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits, size_t align, int start) { size_t align_mask = (align) ? (align - 1) : 0; + unsigned long area_off = 0, area_bits = 0; int bit_off, end, oslot; lockdep_assert_held(&pcpu_lock); @@ -1098,11 +1192,14 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits, */ end = min_t(int, start + alloc_bits + PCPU_BITMAP_BLOCK_BITS, pcpu_chunk_map_bits(chunk)); - bit_off = bitmap_find_next_zero_area(chunk->alloc_map, end, start, - alloc_bits, align_mask); + bit_off = pcpu_find_zero_area(chunk->alloc_map, end, start, alloc_bits, + align_mask, &area_off, &area_bits); if (bit_off >= end) return -1; + if (area_bits) + pcpu_block_update_scan(chunk, area_off, area_bits); + /* update alloc map */ bitmap_set(chunk->alloc_map, bit_off, alloc_bits); From patchwork Thu Feb 28 02:18:36 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832477 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 C8DDA17E9 for ; Thu, 28 Feb 2019 02:19:10 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B3B122DE2E for ; Thu, 28 Feb 2019 02:19:10 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A81492DF4E; Thu, 28 Feb 2019 02:19:10 +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 3895E2DE2E for ; Thu, 28 Feb 2019 02:19:10 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id AA63E8E000C; Wed, 27 Feb 2019 21:18:58 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id A31C28E0001; Wed, 27 Feb 2019 21:18:58 -0500 (EST) 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 922678E000C; Wed, 27 Feb 2019 21:18:58 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qk1-f199.google.com (mail-qk1-f199.google.com [209.85.222.199]) by kanga.kvack.org (Postfix) with ESMTP id 592C68E0001 for ; Wed, 27 Feb 2019 21:18:58 -0500 (EST) Received: by mail-qk1-f199.google.com with SMTP id z123so851683qka.20 for ; Wed, 27 Feb 2019 18:18:58 -0800 (PST) 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=sHVgXKJ/dpov8r/5Fytj2IJVQNeHCHiREVwJuyicgyI=; b=V3ocTyXyH57guqwyRas/QCwcsLyh52Dp/mbeSraYht9Z71FsooCP1Uz9PSHqqGEO+4 26+WvXi5JHcVKImd/H0WVt4iLdxd7IvVLWD62Sb22/NEhhQqz/SOxLPlae7vnU+ZxcbF WYrs/uavIgOybv+W6vF1iSXiA+j4AsHxxX3eTrmuIG4Qddod9RPHtKOno1wpCjQdJjjd p/gvTojU6nok/EJNYABUU2b6GcOIycBcYWShweyflD668MgqTRtSih0fPtEBRIiFukse NhmDCP9v3HfIT0PsD4A530iCQ7gqxq4d/XL6XygY6I3aM4FokIOro1S9hG5Ia/bueR/0 qf7w== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: APjAAAU9XtIEQA9tuhG6ERBrPKllpJEdqxOH0a1BbAPVK9ksCl8jUiPo J4TIvTeV2Hna498YmptXtflvytlK1cJpnwE1BV+kVJD9LRHIXfpCCfBKEG6luiVPiigqmn6XbSj X86OJXn5IEljN1Z3QFk0hjS195F/cjCevNlD+LGSw8Uj/IvoQQmEWjIscV1y9W9Oog6BYL80Jg3 5AT7fJnKYyAxyRCHWIYBOTBH+cH54CjXB0td+4KbpNxlcH/ceYpMMP0XINVDrhYbpUAYkMWxTdA wuuEIPoGaj1b5/erIE+ySADwMY/h4gEGLsT5+1X/yuHh1mU8Oc4rzcQYDVyJRmy2XTjV5c5nkIP wB0AejPX6Z6ceYwQJewbCiXN2hqAFyPjsR15JGf8PAhQ5v5tdheM244LEpYwBd98IXn/dCY1NA= = X-Received: by 2002:a0c:e64f:: with SMTP id c15mr4580319qvn.16.1551320338151; Wed, 27 Feb 2019 18:18:58 -0800 (PST) X-Received: by 2002:a0c:e64f:: with SMTP id c15mr4580292qvn.16.1551320337433; Wed, 27 Feb 2019 18:18:57 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320337; cv=none; d=google.com; s=arc-20160816; b=d/ucq2ScAFqNK9rnV4mpNC5okd5m1r/C3GDURs6VfGV+MzIKtNJd/pNw7f64BqcAjy ins/ntFgB9X5P82vNBjLhLUUJZGNjKBVMslKy9gU3kh+ZZTppD4Dfwtb2y4UpyTTyikD XqnE9O2cdU8tMPwub1m/BqP4bOTOEoSpVX9tEmQ4nmAOnrrOR2y1j0YSS4LQaD5HyRTj iAKKuHhyFieDAjRDQdCh+8MrNL3y/BiDOOH9ACEQVIZLY4sAdJwwZKD4q72/NHXsL5eb H+Sc8yFX6Rq8tZBUpbaI5mWpniICRck1RLZvCBbc+6AECNPUMz+Z5r+xifm0lUTecMGM 7loQ== 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=sHVgXKJ/dpov8r/5Fytj2IJVQNeHCHiREVwJuyicgyI=; b=B6+4eRjW1tk2TG3hsjsW/uOvrX1tg8VVQtV+A2Tg7Za0AGVElkQ0sc0mE19Vb+zRLF jvxkd5AAWSVLewiXxni5ogSmk0UpHhjKGV31xkC47PhUrGHU4OoWSAEJipgJS8N1WJ7O +PYjwJfVFbN3AegEmCOR4q3wMuwPYL2I6kasnADDQ1x+6nX/+YAdmTDkAZG2AZMeN3/8 hah2c7V4Jw2ELpLV5bJMbdyuwtLOquyUTGSn6Lf87Vi+U3DrsSV3isLRcBj6uAkubvbL yaxpp4w7KILijxUpi3uqZ+yHdZSMu4tZtQ6fQ2m+Z7TxtONfm/vla44rLwc9vXXDHrFV 39KQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id n123sor9929881qkf.76.2019.02.27.18.18.57 for (Google Transport Security); Wed, 27 Feb 2019 18:18:57 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: APXvYqwo0bo97d7l1mZByOoZbYpzKXCP3xYjF3Kj+XUDGx0YrEYUpXA0XMb+iahfYNEOWMBz/mI7Pg== X-Received: by 2002:a37:4d52:: with SMTP id a79mr4678440qkb.75.1551320337168; Wed, 27 Feb 2019 18:18:57 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.55 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:56 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 09/12] percpu: use block scan_hint to only scan forward Date: Wed, 27 Feb 2019 21:18:36 -0500 Message-Id: <20190228021839.55779-10-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 Blocks now remember the latest scan_hint. This can be used on the allocation path as when a contig_hint is broken, we can promote the scan_hint to the contig_hint and scan forward from there. This works because pcpu_block_refresh_hint() is only called on the allocation path while block free regions are updated manually in pcpu_block_update_hint_free(). Signed-off-by: Dennis Zhou --- mm/percpu.c | 23 +++++++++++++++++------ 1 file changed, 17 insertions(+), 6 deletions(-) diff --git a/mm/percpu.c b/mm/percpu.c index dac18968d79f..e51c151ed692 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -765,14 +765,23 @@ static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index) { struct pcpu_block_md *block = chunk->md_blocks + index; unsigned long *alloc_map = pcpu_index_alloc_map(chunk, index); - int rs, re; /* region start, region end */ + int rs, re, start; /* region start, region end */ + + /* promote scan_hint to contig_hint */ + if (block->scan_hint) { + start = block->scan_hint_start + block->scan_hint; + block->contig_hint_start = block->scan_hint_start; + block->contig_hint = block->scan_hint; + block->scan_hint = 0; + } else { + start = block->first_free; + block->contig_hint = 0; + } - /* clear hints */ - block->contig_hint = block->scan_hint = 0; - block->left_free = block->right_free = 0; + block->right_free = 0; /* iterate over free areas and update the contig hints */ - pcpu_for_each_unpop_region(alloc_map, rs, re, block->first_free, + pcpu_for_each_unpop_region(alloc_map, rs, re, start, PCPU_BITMAP_BLOCK_BITS) { pcpu_block_update(block, rs, re); } @@ -837,6 +846,8 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, s_off, s_off + bits)) { /* block contig hint is broken - scan to fix it */ + if (!s_off) + s_block->left_free = 0; pcpu_block_refresh_hint(chunk, s_index); } else { /* update left and right contig manually */ @@ -870,11 +881,11 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, if (e_off > e_block->scan_hint_start) e_block->scan_hint = 0; + e_block->left_free = 0; if (e_off > e_block->contig_hint_start) { /* contig hint is broken - scan to fix it */ pcpu_block_refresh_hint(chunk, e_index); } else { - e_block->left_free = 0; e_block->right_free = min_t(int, e_block->right_free, PCPU_BITMAP_BLOCK_BITS - e_off); From patchwork Thu Feb 28 02:18:37 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832479 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 C44E813B5 for ; Thu, 28 Feb 2019 02:19:13 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id B2F4B2DE2E for ; Thu, 28 Feb 2019 02:19:13 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id A6CE12DF4E; Thu, 28 Feb 2019 02:19:13 +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 3A6772DE2E for ; Thu, 28 Feb 2019 02:19:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 4B0FC8E000D; Wed, 27 Feb 2019 21:19:00 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 462188E0001; Wed, 27 Feb 2019 21:19:00 -0500 (EST) 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 380708E000D; Wed, 27 Feb 2019 21:19:00 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt1-f199.google.com (mail-qt1-f199.google.com [209.85.160.199]) by kanga.kvack.org (Postfix) with ESMTP id 0865A8E0001 for ; Wed, 27 Feb 2019 21:19:00 -0500 (EST) Received: by mail-qt1-f199.google.com with SMTP id c9so17119350qte.11 for ; Wed, 27 Feb 2019 18:19:00 -0800 (PST) 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=a1MxtiVBC/R1K9jFEg6/xTwsmtYqOsSXFAxjGkPQwuE=; b=bxIST4VLQNHspPLzpg5/bBW4qhquhDoEkazIHdfcQmgdeJSxwgGNckdadQDXxb9us5 rAU/FjedKTHzYnH86OiOx/cuBQ+bnZCpviIXAH9r+khzfm3Ti4vfHy5blZA5eR2os/aq hr2qkijyLLrAloYjCKnrviljztwqsw/iEdzqpAyHMTLTGsFAl2lEByVVARDYADwGtCkH gv2ckXzy6dgLHM8ACqYqkp7wuMwcpRC2boXeRo7wGHkrcGXYJd5/AyGkCR4LE6BfBYHe lFJPybruQ/GkRp86iZvzaMzyY/QIALDiq7qxZaAu6jb+urJ5HYbJts7rz0lKdWWdU9EE K/8w== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: APjAAAWsnXbA4P8PILFQ9p/U6lOnLuNqEr37vTkDzawIb9x/OYrlvmF8 2+Fct0kol1tPa5gGus1TzigZpirKgNioEXiO0kklwLeXPGpLPSYhoIlqAuJonn+vVTy3g8R+kZi xNhCM1n/vcAXuMy1ZAGtHiQt4S0KxWgYY02RSVF4kCj8dzuwCDf5as0dipD2e6+kIzFbDmE3l2+ 0mwzj/k6SvvS1me+jUQdvhb58kSMD3Cyq27snT9jeuK4CLbnnhLWitMwiZWHtkBLz/noECl8ubg P4XbOFBYbugMBHwScDP2WcTg2zBX9DNZL6/uyQp8R937eD1vWoClWdWm59Fsl/4rHvLtGiT3wzg E8WaV7ItrJErVv6ip0PJI4uXccgKdFka8eWkDDpknyuol/kwqcNyj0pdFfUdpNmCy1bA0qFSAg= = X-Received: by 2002:a0c:b98f:: with SMTP id v15mr4504072qvf.60.1551320339806; Wed, 27 Feb 2019 18:18:59 -0800 (PST) X-Received: by 2002:a0c:b98f:: with SMTP id v15mr4504040qvf.60.1551320339036; Wed, 27 Feb 2019 18:18:59 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320339; cv=none; d=google.com; s=arc-20160816; b=0MMqXX1dPmyzC+yFn4gMKPrDUXiLD11KDlYvGjvqrirPJB0GLD0skMwypv2omAyvYv 9UJRqhlChl5q1t4CWhQwQXvxYHJM6K5Q7aNfE1e8NgIwMZeCdoSbBTmgA+G9p4hiGoLX GTSagkkFZqhKjFGPT6JU+r+wjk+qQnvY3YRuxuBK7qA8qDAteZN3/xoTkwlC2uaikOQ4 +SihiNteoidKPPDuwoxYSdHcnqSORNektQegp8ioKqopBcvEx+AypQXKm7hGYKkawIZK tgyxeh/LWlQyzbsNOQOTZ9PpDz9gkL8DfEJJcBWC7Xf9qHDo6ykMKDBx3M2/MrwiCD+N FK9g== 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=a1MxtiVBC/R1K9jFEg6/xTwsmtYqOsSXFAxjGkPQwuE=; b=Wy4TNsEFjpNV156aMnRQfPt2SjsOYlORwUNdI+/6VrMlb+djoEri+hVCaKtuZtPL3z 9FQQ7SCBLuQvadaq4rAHGL6xnaoRhuKyisMI1xqVrEmlp3UmTMrNm8NRvws51P1CUJkk u2lvRlr+3lcU58mNDyKGvGnWyQbraMCrlYKubDDmzW4hYWW70TD1YkWqGwHUHBMN3nZA fqXZqetgJoHKztOQzgK0sXsyDpbVvEQzbvCHuU7QNutIc718jMvJmEDheMG+HOTWi/XP R/DFgrTyQH1V0UjG7qswQ11iIHwnlWVrcSFJwJUrlaMdIaBcDlUztFiSolnglQ/hGEvk 7CuA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id g66sor3153231qkb.134.2019.02.27.18.18.59 for (Google Transport Security); Wed, 27 Feb 2019 18:18:59 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: APXvYqwPqhzmoh6GEfoGzQtsXP/iOmZeY0a+Lec5XpOorPIszYP54avqBFyXUbatJXA0jjRU7OtQYg== X-Received: by 2002:a37:e30b:: with SMTP id y11mr4833349qki.25.1551320338781; Wed, 27 Feb 2019 18:18:58 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.57 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:57 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 10/12] percpu: make pcpu_block_md generic Date: Wed, 27 Feb 2019 21:18:37 -0500 Message-Id: <20190228021839.55779-11-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 In reality, a chunk is just a block covering a larger number of bits. The hints themselves are one in the same. Rather than maintaining the hints separately, first introduce nr_bits to genericize pcpu_block_update() to correctly maintain block->right_free. The next patch will convert chunk hints to be managed as a pcpu_block_md. Signed-off-by: Dennis Zhou Reviewed-by: Peng Fan --- mm/percpu-internal.h | 1 + mm/percpu.c | 20 +++++++++++++------- 2 files changed, 14 insertions(+), 7 deletions(-) diff --git a/mm/percpu-internal.h b/mm/percpu-internal.h index ec58b244545d..119bd1119aa7 100644 --- a/mm/percpu-internal.h +++ b/mm/percpu-internal.h @@ -28,6 +28,7 @@ struct pcpu_block_md { int right_free; /* size of free space along the right side of the block */ int first_free; /* block position of first free */ + int nr_bits; /* total bits responsible for */ }; struct pcpu_chunk { diff --git a/mm/percpu.c b/mm/percpu.c index e51c151ed692..7cdf14c242de 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -658,7 +658,7 @@ static void pcpu_block_update(struct pcpu_block_md *block, int start, int end) if (start == 0) block->left_free = contig; - if (end == PCPU_BITMAP_BLOCK_BITS) + if (end == block->nr_bits) block->right_free = contig; if (contig > block->contig_hint) { @@ -1271,18 +1271,24 @@ static void pcpu_free_area(struct pcpu_chunk *chunk, int off) pcpu_chunk_relocate(chunk, oslot); } +static void pcpu_init_md_block(struct pcpu_block_md *block, int nr_bits) +{ + block->scan_hint = 0; + block->contig_hint = nr_bits; + block->left_free = nr_bits; + block->right_free = nr_bits; + block->first_free = 0; + block->nr_bits = nr_bits; +} + static void pcpu_init_md_blocks(struct pcpu_chunk *chunk) { struct pcpu_block_md *md_block; for (md_block = chunk->md_blocks; md_block != chunk->md_blocks + pcpu_chunk_nr_blocks(chunk); - md_block++) { - md_block->scan_hint = 0; - md_block->contig_hint = PCPU_BITMAP_BLOCK_BITS; - md_block->left_free = PCPU_BITMAP_BLOCK_BITS; - md_block->right_free = PCPU_BITMAP_BLOCK_BITS; - } + md_block++) + pcpu_init_md_block(md_block, PCPU_BITMAP_BLOCK_BITS); } /** From patchwork Thu Feb 28 02:18:38 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832481 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 3D7BE13B5 for ; Thu, 28 Feb 2019 02:19:17 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 2B7FC2DF4E for ; Thu, 28 Feb 2019 02:19:17 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 1F4D22DF6C; Thu, 28 Feb 2019 02:19:17 +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 31CE02DF4E for ; Thu, 28 Feb 2019 02:19:16 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 3EEC58E000E; Wed, 27 Feb 2019 21:19:02 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 3C5A18E0001; Wed, 27 Feb 2019 21:19:02 -0500 (EST) 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 28DAA8E000E; Wed, 27 Feb 2019 21:19:02 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) by kanga.kvack.org (Postfix) with ESMTP id F2FA28E0001 for ; Wed, 27 Feb 2019 21:19:01 -0500 (EST) Received: by mail-qt1-f197.google.com with SMTP id c9so17119422qte.11 for ; Wed, 27 Feb 2019 18:19:01 -0800 (PST) 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=g2ENlk1zX6grjv7br7W/r2m1obArXEgzzB0drAyc/OA=; b=T9rhIkZ5Le5VNN+3TY1nKvRq33MI2UJ2Zp4rajJq+AxxFuVoGolNRf59yj5YyJ4U50 8KLl+75ooonRUEG5Lq8/BOx234/blQ3ArJnJSSIVYoSGbphDZEwQvgvoK0y2A3br6M22 c43EWKRpml0yTOt7sivYApyMosiprw2fGFjQsELlr+k2mLbZN0ynYaw/WMf/+5P7lf2P F+5z1E8iObpPEGQvzDoVivudBXdSs02G0XKiFA05gPIC1UrO43YA9yzd3bXQpftXqsZy N++2tYbsHpsef1r1LwNpeO22xPLEM7J1kNlBqR5VbujNMv7YtHArpVkqHiZejrGg2ToK 3vrg== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: AHQUAuaaQzMZo+ugiIZmnZIVen7fERCksOtR1b+jEvqc91xCRIJyHoGi +MK6OU+WC7JhWk/Trdfb6iYQC8n4UYM/aJpCGzUxfN5GlaRqTu4wLDQUjQWNs1/xEHjkNEmU9Me IFw/Cw0Xtl1i4UoiS8UMQYjocmfyeiI+gi+Cai8WrBEaJaXjUFgKiXiicaE6jT9dq04P8pwPR65 Sev0y/gmOybmXMSNmqGiXjWku7bcjYbd4RlH+JsOZnncKkCqCD62gGohVLlzExBb91LZaOzBffz mU2hH8b0BB/0fzgGpuKnHwVFlngWAqOnusQ4Mz5DjLRpv22vTcwpjCKrHo9/Ug1Xl6e9OVEjrkC Q3v8xdH/3XwRrGRBblUClMBw/BtwkwGC4C68S0ixdIN30K7ShlmTX7I8FaUgAEg8LaeDHsF6yw= = X-Received: by 2002:ac8:2c92:: with SMTP id 18mr4250022qtw.269.1551320341722; Wed, 27 Feb 2019 18:19:01 -0800 (PST) X-Received: by 2002:ac8:2c92:: with SMTP id 18mr4249980qtw.269.1551320340708; Wed, 27 Feb 2019 18:19:00 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320340; cv=none; d=google.com; s=arc-20160816; b=DY13jEiBTRoRyhLeVNSGRsWj97Dlmu5PP8BSXKL8rUrwCPyM4Ra7JHDY+X+brYmWeD XoHieCtuyUzsCN4PQQnP0I6oEat+nQM9EkdGwh8ubN/kXIwUN4pXFDjyw/qIlBjzPJNF UzkqPc2tOocyeS2JxsuLiM8ka0Ie8WSQxcTiCpP871km6A+EJV7kEhYrfyx841ysBxOz rptmNlmP8vB1mCJMlERo1YZaR1vIvnmUirBYE2r5pnZhYQQjkyAobY+EYsdtw6KELUqB lEnJ2bEgr2qCbsPvo+3WO6MESfmtMD3h4YWnBuJm8jwEc/95A4hrL5PY0/7NCdaH4HM1 jrmw== 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=g2ENlk1zX6grjv7br7W/r2m1obArXEgzzB0drAyc/OA=; b=dmGPEznTskJQbTfMU/DMwH/rnS0jEB3pFGQvEQAICe9sy+irDYv4izUzT26tImKzjA IC7GyzE6R9TPCM5nyZPWJYF6FbsAfrJc+L/UvUCK05AnNCqVBoA+Si99iMDZcJABdUo2 chNeCa1sr91wyyQwpgpuFpVSut9yNAYMEsKLxYdOZb5kwaPLKn5mLvw9GW5P8b0jCPjS MYyu52svCBqZrTOXULXrmJNLGuchgmq/Ut++e5r7FKcIRC503+Ci28B1oyNc5XfdjCxr 5jrsowWgN3cokdpweV8ui/KYh9MLBohReab7XT14GZWobUOSUpmtyNPdoHL3zA7lFVZP 4geQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id n52sor21890925qtk.39.2019.02.27.18.19.00 for (Google Transport Security); Wed, 27 Feb 2019 18:19:00 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: AHgI3IbHe/rxuVJiXM41Enka/t5RwmbfAtxTtVZrOy0xH8T/DXgOeiB+iYMvA8kh0Qu3zNT+r1GO5A== X-Received: by 2002:ac8:1a56:: with SMTP id q22mr4290404qtk.59.1551320340377; Wed, 27 Feb 2019 18:19:00 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.18.58 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:18:59 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 11/12] percpu: convert chunk hints to be based on pcpu_block_md Date: Wed, 27 Feb 2019 21:18:38 -0500 Message-Id: <20190228021839.55779-12-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 As mentioned in the last patch, a chunk's hints are no different than a block just responsible for more bits. This converts chunk level hints to use a pcpu_block_md to maintain them. This lets us reuse the same hint helper functions as a block. The left_free and right_free are unused by the chunk's pcpu_block_md. Signed-off-by: Dennis Zhou Reviewed-by: Peng Fan --- mm/percpu-internal.h | 5 +- mm/percpu-stats.c | 5 +- mm/percpu.c | 120 +++++++++++++++++++------------------------ 3 files changed, 57 insertions(+), 73 deletions(-) diff --git a/mm/percpu-internal.h b/mm/percpu-internal.h index 119bd1119aa7..0468ba500bd4 100644 --- a/mm/percpu-internal.h +++ b/mm/percpu-internal.h @@ -39,9 +39,7 @@ struct pcpu_chunk { struct list_head list; /* linked to pcpu_slot lists */ int free_bytes; /* free bytes in the chunk */ - int contig_bits; /* max contiguous size hint */ - int contig_bits_start; /* contig_bits starting - offset */ + struct pcpu_block_md chunk_md; void *base_addr; /* base address of this chunk */ unsigned long *alloc_map; /* allocation map */ @@ -49,7 +47,6 @@ struct pcpu_chunk { struct pcpu_block_md *md_blocks; /* metadata blocks */ void *data; /* chunk data */ - int first_bit; /* no free below this */ bool immutable; /* no [de]population allowed */ int start_offset; /* the overlap with the previous region to have a page aligned diff --git a/mm/percpu-stats.c b/mm/percpu-stats.c index b5fdd43b60c9..ef5034a0464e 100644 --- a/mm/percpu-stats.c +++ b/mm/percpu-stats.c @@ -53,6 +53,7 @@ static int find_max_nr_alloc(void) static void chunk_map_stats(struct seq_file *m, struct pcpu_chunk *chunk, int *buffer) { + struct pcpu_block_md *chunk_md = &chunk->chunk_md; int i, last_alloc, as_len, start, end; int *alloc_sizes, *p; /* statistics */ @@ -121,9 +122,9 @@ static void chunk_map_stats(struct seq_file *m, struct pcpu_chunk *chunk, P("nr_alloc", chunk->nr_alloc); P("max_alloc_size", chunk->max_alloc_size); P("empty_pop_pages", chunk->nr_empty_pop_pages); - P("first_bit", chunk->first_bit); + P("first_bit", chunk_md->first_free); P("free_bytes", chunk->free_bytes); - P("contig_bytes", chunk->contig_bits * PCPU_MIN_ALLOC_SIZE); + P("contig_bytes", chunk_md->contig_hint * PCPU_MIN_ALLOC_SIZE); P("sum_frag", sum_frag); P("max_frag", max_frag); P("cur_min_alloc", cur_min_alloc); diff --git a/mm/percpu.c b/mm/percpu.c index 7cdf14c242de..197479f2c489 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -233,10 +233,13 @@ static int pcpu_size_to_slot(int size) static int pcpu_chunk_slot(const struct pcpu_chunk *chunk) { - if (chunk->free_bytes < PCPU_MIN_ALLOC_SIZE || chunk->contig_bits == 0) + const struct pcpu_block_md *chunk_md = &chunk->chunk_md; + + if (chunk->free_bytes < PCPU_MIN_ALLOC_SIZE || + chunk_md->contig_hint == 0) return 0; - return pcpu_size_to_slot(chunk->contig_bits * PCPU_MIN_ALLOC_SIZE); + return pcpu_size_to_slot(chunk_md->contig_hint * PCPU_MIN_ALLOC_SIZE); } /* set the pointer to a chunk in a page struct */ @@ -592,54 +595,6 @@ static inline bool pcpu_region_overlap(int a, int b, int x, int y) return false; } -/** - * pcpu_chunk_update - updates the chunk metadata given a free area - * @chunk: chunk of interest - * @bit_off: chunk offset - * @bits: size of free area - * - * This updates the chunk's contig hint and starting offset given a free area. - * Choose the best starting offset if the contig hint is equal. - */ -static void pcpu_chunk_update(struct pcpu_chunk *chunk, int bit_off, int bits) -{ - if (bits > chunk->contig_bits) { - chunk->contig_bits_start = bit_off; - chunk->contig_bits = bits; - } else if (bits == chunk->contig_bits && chunk->contig_bits_start && - (!bit_off || - __ffs(bit_off) > __ffs(chunk->contig_bits_start))) { - /* use the start with the best alignment */ - chunk->contig_bits_start = bit_off; - } -} - -/** - * pcpu_chunk_refresh_hint - updates metadata about a chunk - * @chunk: chunk of interest - * - * Iterates over the metadata blocks to find the largest contig area. - * It also counts the populated pages and uses the delta to update the - * global count. - * - * Updates: - * chunk->contig_bits - * chunk->contig_bits_start - */ -static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk) -{ - int bit_off, bits; - - /* clear metadata */ - chunk->contig_bits = 0; - - bit_off = chunk->first_bit; - bits = 0; - pcpu_for_each_md_free_region(chunk, bit_off, bits) { - pcpu_chunk_update(chunk, bit_off, bits); - } -} - /** * pcpu_block_update - updates a block given a free area * @block: block of interest @@ -753,6 +708,29 @@ static void pcpu_block_update_scan(struct pcpu_chunk *chunk, int bit_off, pcpu_block_update(block, s_off, e_off); } +/** + * pcpu_chunk_refresh_hint - updates metadata about a chunk + * @chunk: chunk of interest + * + * Iterates over the metadata blocks to find the largest contig area. + * It also counts the populated pages and uses the delta to update the + * global count. + */ +static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk) +{ + struct pcpu_block_md *chunk_md = &chunk->chunk_md; + int bit_off, bits; + + /* clear metadata */ + chunk_md->contig_hint = 0; + + bit_off = chunk_md->first_free; + bits = 0; + pcpu_for_each_md_free_region(chunk, bit_off, bits) { + pcpu_block_update(chunk_md, bit_off, bit_off + bits); + } +} + /** * pcpu_block_refresh_hint * @chunk: chunk of interest @@ -800,6 +778,7 @@ static void pcpu_block_refresh_hint(struct pcpu_chunk *chunk, int index) static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, int bits) { + struct pcpu_block_md *chunk_md = &chunk->chunk_md; int nr_empty_pages = 0; struct pcpu_block_md *s_block, *e_block, *block; int s_index, e_index; /* block indexes of the freed allocation */ @@ -910,8 +889,9 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, * contig hint is broken. Otherwise, it means a smaller space * was used and therefore the chunk contig hint is still correct. */ - if (pcpu_region_overlap(chunk->contig_bits_start, - chunk->contig_bits_start + chunk->contig_bits, + if (pcpu_region_overlap(chunk_md->contig_hint_start, + chunk_md->contig_hint_start + + chunk_md->contig_hint, bit_off, bit_off + bits)) pcpu_chunk_refresh_hint(chunk); @@ -930,9 +910,10 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, * * A chunk update is triggered if a page becomes free, a block becomes free, * or the free spans across blocks. This tradeoff is to minimize iterating - * over the block metadata to update chunk->contig_bits. chunk->contig_bits - * may be off by up to a page, but it will never be more than the available - * space. If the contig hint is contained in one block, it will be accurate. + * over the block metadata to update chunk_md->contig_hint. + * chunk_md->contig_hint may be off by up to a page, but it will never be more + * than the available space. If the contig hint is contained in one block, it + * will be accurate. */ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, int bits) @@ -1026,8 +1007,9 @@ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, if (((end - start) >= PCPU_BITMAP_BLOCK_BITS) || s_index != e_index) pcpu_chunk_refresh_hint(chunk); else - pcpu_chunk_update(chunk, pcpu_block_off_to_off(s_index, start), - end - start); + pcpu_block_update(&chunk->chunk_md, + pcpu_block_off_to_off(s_index, start), + end); } /** @@ -1082,6 +1064,7 @@ static bool pcpu_is_populated(struct pcpu_chunk *chunk, int bit_off, int bits, static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int alloc_bits, size_t align, bool pop_only) { + struct pcpu_block_md *chunk_md = &chunk->chunk_md; int bit_off, bits, next_off; /* @@ -1090,12 +1073,12 @@ static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int alloc_bits, * cannot fit in the global hint, there is memory pressure and creating * a new chunk would happen soon. */ - bit_off = ALIGN(chunk->contig_bits_start, align) - - chunk->contig_bits_start; - if (bit_off + alloc_bits > chunk->contig_bits) + bit_off = ALIGN(chunk_md->contig_hint_start, align) - + chunk_md->contig_hint_start; + if (bit_off + alloc_bits > chunk_md->contig_hint) return -1; - bit_off = chunk->first_bit; + bit_off = chunk_md->first_free; bits = 0; pcpu_for_each_fit_region(chunk, alloc_bits, align, bit_off, bits) { if (!pop_only || pcpu_is_populated(chunk, bit_off, bits, @@ -1190,6 +1173,7 @@ static unsigned long pcpu_find_zero_area(unsigned long *map, static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits, size_t align, int start) { + struct pcpu_block_md *chunk_md = &chunk->chunk_md; size_t align_mask = (align) ? (align - 1) : 0; unsigned long area_off = 0, area_bits = 0; int bit_off, end, oslot; @@ -1222,8 +1206,8 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits, chunk->free_bytes -= alloc_bits * PCPU_MIN_ALLOC_SIZE; /* update first free bit */ - if (bit_off == chunk->first_bit) - chunk->first_bit = find_next_zero_bit( + if (bit_off == chunk_md->first_free) + chunk_md->first_free = find_next_zero_bit( chunk->alloc_map, pcpu_chunk_map_bits(chunk), bit_off + alloc_bits); @@ -1245,6 +1229,7 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int alloc_bits, */ static void pcpu_free_area(struct pcpu_chunk *chunk, int off) { + struct pcpu_block_md *chunk_md = &chunk->chunk_md; int bit_off, bits, end, oslot; lockdep_assert_held(&pcpu_lock); @@ -1264,7 +1249,7 @@ static void pcpu_free_area(struct pcpu_chunk *chunk, int off) chunk->free_bytes += bits * PCPU_MIN_ALLOC_SIZE; /* update first free bit */ - chunk->first_bit = min(chunk->first_bit, bit_off); + chunk_md->first_free = min(chunk_md->first_free, bit_off); pcpu_block_update_hint_free(chunk, bit_off, bits); @@ -1285,6 +1270,9 @@ static void pcpu_init_md_blocks(struct pcpu_chunk *chunk) { struct pcpu_block_md *md_block; + /* init the chunk's block */ + pcpu_init_md_block(&chunk->chunk_md, pcpu_chunk_map_bits(chunk)); + for (md_block = chunk->md_blocks; md_block != chunk->md_blocks + pcpu_chunk_nr_blocks(chunk); md_block++) @@ -1352,7 +1340,6 @@ static struct pcpu_chunk * __init pcpu_alloc_first_chunk(unsigned long tmp_addr, chunk->nr_populated = chunk->nr_pages; chunk->nr_empty_pop_pages = chunk->nr_pages; - chunk->contig_bits = map_size / PCPU_MIN_ALLOC_SIZE; chunk->free_bytes = map_size; if (chunk->start_offset) { @@ -1362,7 +1349,7 @@ static struct pcpu_chunk * __init pcpu_alloc_first_chunk(unsigned long tmp_addr, set_bit(0, chunk->bound_map); set_bit(offset_bits, chunk->bound_map); - chunk->first_bit = offset_bits; + chunk->chunk_md.first_free = offset_bits; pcpu_block_update_hint_alloc(chunk, 0, offset_bits); } @@ -1415,7 +1402,6 @@ static struct pcpu_chunk *pcpu_alloc_chunk(gfp_t gfp) pcpu_init_md_blocks(chunk); /* init metadata */ - chunk->contig_bits = region_bits; chunk->free_bytes = chunk->nr_pages * PAGE_SIZE; return chunk; From patchwork Thu Feb 28 02:18:39 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Dennis Zhou X-Patchwork-Id: 10832483 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 ED66F17E9 for ; Thu, 28 Feb 2019 02:19:19 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id DA8782DF6C for ; Thu, 28 Feb 2019 02:19:19 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id CEDAB2DF73; Thu, 28 Feb 2019 02:19:19 +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 5E0272DF6C for ; Thu, 28 Feb 2019 02:19:19 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 612858E000F; Wed, 27 Feb 2019 21:19:03 -0500 (EST) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 59B968E0001; Wed, 27 Feb 2019 21:19:03 -0500 (EST) 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 4638A8E000F; Wed, 27 Feb 2019 21:19:03 -0500 (EST) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-qt1-f197.google.com (mail-qt1-f197.google.com [209.85.160.197]) by kanga.kvack.org (Postfix) with ESMTP id 1C46D8E0001 for ; Wed, 27 Feb 2019 21:19:03 -0500 (EST) Received: by mail-qt1-f197.google.com with SMTP id s8so17060142qth.18 for ; Wed, 27 Feb 2019 18:19:03 -0800 (PST) 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=qImDKhW66AzCuoNyqvyprY/jSnw+rPbm4Fv7bWHuvuA=; b=A7LQh0rBRT0k1bCKZ0DRXwkyzUJ8sh2q/BnXnbNLZqiXIDauuUUcr+NwIubY763kKV pYi0fSyw6HVZELgk2uYLG67o0GyXfkJKfRMAm4ne9s1p3P3fVEug3EKekDcxlBJnOCjc wCiR8REH8A537TC/MW8CSzphADqD6to6pF0EWcZFW08u23rX9lRyAsBis/JUlp9nI5AV Eb4wKZjtz3LcIt7aoZlzlPJCB8BSOfwg2LTPqpkLutmg9rxgO1BKpT6wsd27NGRdXJT3 iPjBGhwGVZ8kwwFgqCCDuJ7f+vK7fcse7zXl6XXKWXzMFR9JJoVZ5PdMFnjBLHIlBxoI Jryw== X-Original-Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Gm-Message-State: AHQUAubKwTbIm+dUeYA6XeFRoVc10/Np10Z/o8L3Je38kzmG91tYZ4bZ 8Ehi2X7jXE3Y01FAHmH6yMI3AKU6W83hTTyIm2ZuyPVUdsTgQlDBnS5SbTHEJM/SYmHieEVJql/ H8vaewbsoxky9Xt8QdhOwUcZY6dpUCeGOp/4FTUvHNM98ca4HBP7fK8LR/dmA+XlRn47bcrpRv9 AMg4Z50+EfZcyML38tOPNDq3uZ2hirQHt8KvjJNlAGVYrNO3OkVHaMbXUwJvLLUlCL718IKpNNx YRJYzAFbZgcvVWuxxGI8SVKUiuTJ/iV3IZGMD2Ycqk4Tkqi8Ot1zVF7H6H5Nl0u1AMc8fCIhX2q +B5xwrRl4AZHsVlLnSqBZNpk1xs30+MtOOp9d4E1SHkanVWLi0UARbdGlGwzczu8kOv8uwfYJg= = X-Received: by 2002:ac8:2286:: with SMTP id f6mr4429338qta.68.1551320342886; Wed, 27 Feb 2019 18:19:02 -0800 (PST) X-Received: by 2002:ac8:2286:: with SMTP id f6mr4429314qta.68.1551320342147; Wed, 27 Feb 2019 18:19:02 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1551320342; cv=none; d=google.com; s=arc-20160816; b=o9VQ4qr57DyfmqWjEnAQmhusvvvqPqwghnN0wRF+2CSzbk84j6l3QK1G542+ALw5wN 6w6+qyT1YzdqKtg9JuJWtd/kvfxnQI4kAsPmzCbTRJQL9wox07dRQiUXwAwj4tVIYepo t1Dvn9lent5Vni2whtYnrqZ24BIeswKQmnmD6K2E/qH3StNq6kBiBvCUpB/nwir6GPyr p4IM80GgKF/cx5LPZIK9h5SOf+rAFmxUj5nAKZhiHoiQBGlI10UIHs4h9BzkWKVgAi/p /1n+iv47xJ8Zx+U+M+17dbm5ZvxM4GoUzgApde0HJ7NBWheSHiIzMKfPPjZDZ9n6AieQ oqbA== 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=qImDKhW66AzCuoNyqvyprY/jSnw+rPbm4Fv7bWHuvuA=; b=cZPbgi31q4JgNWj0f2CwezPnFrxDwQIYwhfx2iqp/5volDQTUUAxXqRelltB1JXCnb cxh3VjL2l76m6SgLPSSIlrEJDGan0sg+U0pnM5NFpzFdXnSVxyb5MGkLrihBAXqj/4ps DTi0dbQdDRg2zC0uevQUYGBoSnXPDMjyRO2DvwmRU4xpxBAh3O2wPxSsmXPOqMnct1WE T8Jz9q8cvdXCCWoQ1/lhU80GaYclzD04/GB5P4TgWQTFK7fqn1CsAsw5RH8ZAdNraOfa ZN+FOCtJWndXmZ8Vpa+Quj7hcrp3Q5GRja/9fVcj5Oe5/pBfakkSAWMM4ZLiJKS9uQU8 2t+Q== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id i69sor10945361qke.5.2019.02.27.18.19.02 for (Google Transport Security); Wed, 27 Feb 2019 18:19:02 -0800 (PST) Received-SPF: pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; spf=pass (google.com: domain of dennisszhou@gmail.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=dennisszhou@gmail.com; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=kernel.org X-Google-Smtp-Source: AHgI3IYgGWL916vz2qCJL6FgtJg1g1UrnDtKTf9mK0j3zPUUdDEHBIlwVWx5ZLs8juhi27ZLZhRLpg== X-Received: by 2002:a37:4e97:: with SMTP id c145mr4659307qkb.85.1551320341809; Wed, 27 Feb 2019 18:19:01 -0800 (PST) Received: from localhost.localdomain (cpe-98-13-254-243.nyc.res.rr.com. [98.13.254.243]) by smtp.gmail.com with ESMTPSA id y21sm12048357qth.90.2019.02.27.18.19.00 (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 27 Feb 2019 18:19:00 -0800 (PST) From: Dennis Zhou To: Dennis Zhou , Tejun Heo , Christoph Lameter Cc: Vlad Buslov , kernel-team@fb.com, linux-mm@kvack.org, linux-kernel@vger.kernel.org Subject: [PATCH 12/12] percpu: use chunk scan_hint to skip some scanning Date: Wed, 27 Feb 2019 21:18:39 -0500 Message-Id: <20190228021839.55779-13-dennis@kernel.org> X-Mailer: git-send-email 2.13.5 In-Reply-To: <20190228021839.55779-1-dennis@kernel.org> References: <20190228021839.55779-1-dennis@kernel.org> 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 Just like blocks, chunks now maintain a scan_hint. This can be used to skip some scanning by promoting the scan_hint to be the contig_hint. The chunk's scan_hint is primarily updated on the backside and relies on full scanning when a block becomes free or the free region spans across blocks. Signed-off-by: Dennis Zhou Reviewed-by: Peng Fan --- mm/percpu.c | 36 +++++++++++++++++++++++++++--------- 1 file changed, 27 insertions(+), 9 deletions(-) diff --git a/mm/percpu.c b/mm/percpu.c index 197479f2c489..40d49d7fb286 100644 --- a/mm/percpu.c +++ b/mm/percpu.c @@ -711,20 +711,31 @@ static void pcpu_block_update_scan(struct pcpu_chunk *chunk, int bit_off, /** * pcpu_chunk_refresh_hint - updates metadata about a chunk * @chunk: chunk of interest + * @full_scan: if we should scan from the beginning * * Iterates over the metadata blocks to find the largest contig area. - * It also counts the populated pages and uses the delta to update the - * global count. + * A full scan can be avoided on the allocation path as this is triggered + * if we broke the contig_hint. In doing so, the scan_hint will be before + * the contig_hint or after if the scan_hint == contig_hint. This cannot + * be prevented on freeing as we want to find the largest area possibly + * spanning blocks. */ -static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk) +static void pcpu_chunk_refresh_hint(struct pcpu_chunk *chunk, bool full_scan) { struct pcpu_block_md *chunk_md = &chunk->chunk_md; int bit_off, bits; - /* clear metadata */ - chunk_md->contig_hint = 0; + /* promote scan_hint to contig_hint */ + if (!full_scan && chunk_md->scan_hint) { + bit_off = chunk_md->scan_hint_start + chunk_md->scan_hint; + chunk_md->contig_hint_start = chunk_md->scan_hint_start; + chunk_md->contig_hint = chunk_md->scan_hint; + chunk_md->scan_hint = 0; + } else { + bit_off = chunk_md->first_free; + chunk_md->contig_hint = 0; + } - bit_off = chunk_md->first_free; bits = 0; pcpu_for_each_md_free_region(chunk, bit_off, bits) { pcpu_block_update(chunk_md, bit_off, bit_off + bits); @@ -884,6 +895,13 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, if (nr_empty_pages) pcpu_update_empty_pages(chunk, -1 * nr_empty_pages); + if (pcpu_region_overlap(chunk_md->scan_hint_start, + chunk_md->scan_hint_start + + chunk_md->scan_hint, + bit_off, + bit_off + bits)) + chunk_md->scan_hint = 0; + /* * The only time a full chunk scan is required is if the chunk * contig hint is broken. Otherwise, it means a smaller space @@ -894,7 +912,7 @@ static void pcpu_block_update_hint_alloc(struct pcpu_chunk *chunk, int bit_off, chunk_md->contig_hint, bit_off, bit_off + bits)) - pcpu_chunk_refresh_hint(chunk); + pcpu_chunk_refresh_hint(chunk, false); } /** @@ -1005,7 +1023,7 @@ static void pcpu_block_update_hint_free(struct pcpu_chunk *chunk, int bit_off, * the else condition below. */ if (((end - start) >= PCPU_BITMAP_BLOCK_BITS) || s_index != e_index) - pcpu_chunk_refresh_hint(chunk); + pcpu_chunk_refresh_hint(chunk, true); else pcpu_block_update(&chunk->chunk_md, pcpu_block_off_to_off(s_index, start), @@ -1078,7 +1096,7 @@ static int pcpu_find_block_fit(struct pcpu_chunk *chunk, int alloc_bits, if (bit_off + alloc_bits > chunk_md->contig_hint) return -1; - bit_off = chunk_md->first_free; + bit_off = pcpu_next_hint(chunk_md, alloc_bits); bits = 0; pcpu_for_each_fit_region(chunk, alloc_bits, align, bit_off, bits) { if (!pop_only || pcpu_is_populated(chunk, bit_off, bits,