From patchwork Tue Jul 10 00:50:03 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Rientjes X-Patchwork-Id: 10516023 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 13DF16032C for ; Tue, 10 Jul 2018 00:50:09 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id ECA3F28CD8 for ; Tue, 10 Jul 2018 00:50:08 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id E02DA28CDE; Tue, 10 Jul 2018 00:50:08 +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=-10.5 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE, USER_IN_DEF_DKIM_WL 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 56C6B28CD8 for ; Tue, 10 Jul 2018 00:50:08 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 2A1B46B0005; Mon, 9 Jul 2018 20:50:07 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 2519B6B0006; Mon, 9 Jul 2018 20:50:07 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0F2726B000A; Mon, 9 Jul 2018 20:50:07 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pf0-f200.google.com (mail-pf0-f200.google.com [209.85.192.200]) by kanga.kvack.org (Postfix) with ESMTP id BF20E6B0005 for ; Mon, 9 Jul 2018 20:50:06 -0400 (EDT) Received: by mail-pf0-f200.google.com with SMTP id f9-v6so11655586pfn.22 for ; Mon, 09 Jul 2018 17:50:06 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:dkim-signature:date:from:to:cc:subject :message-id:user-agent:mime-version; bh=IqiUZ33GqRn3PXo40N7IwiYQfJSSTHFLTLMGHHlWO44=; b=kUJJd80peHT6pvbYfIoc0KlwtGatZ5j+pjd8oLVtbkYEqbxGaE0EbA6oHWCyoKD9lZ 8YOtnbN8uVJKSa03Ps7YZrQlW0yo5EHnz5DRVYHgnVryiNjqoecEwvMFAd7184dBcQQd e9LYFUlCKpBTwW0U3B33aUgE5lVTW8SKDqxIMn6qW4u/fCRNvvfMjNEDLTQDEWkZ3aWr kUWAgyxO4DLLGZiOoQvGGwV0C67uCYS3SuxlRFMJ0a7UL4gtUbeQYnGrz1KbTy1PxJiz tbdDZATGaq3P6S4rFRk9gUQj0tsnDfqCRjn849ILXU2aczUsjh7T9hoZ6qWjDO1XEIvV Oixw== X-Gm-Message-State: APt69E3Zo05YT6mu1q9BY1eJCl5vDUvFMG60Jjy/+fKi6MaCHD9+wVrT n0pG0XcGFHJ8cF2Za06jIDKtT6PciiIp08Gjj3y68j0MUYW1oVWM3TTC5Un4LJn2GnyZv14woHL S+Ivk2PJzWUwj8rImeRkxuBU8J1mKQCi87TBUoIFmgNAAZO0n5kfMuEpgKO3F4iTctXVt1NT9oa mvyfUsCh3/WIpNDt4Gm/GL5P15QjGF0dtzBwb5gQ5tp6NsDdtl1gz2XNwETAqGgHGosPIoS50X0 eoCPVks0lNI4rpGTqP5wJUfJ6/HeU0V4e81ZbKbK1IhnUu/0iCcekbTanm5MUqTfeL9JQsmlzC3 w8ZpXVXnB4uZ9WqkatS/kGaNEZjk+SnF8s6VYGldb+Rjwkq32pP8Zyk+8EjKITC59+/aO+gMn22 4 X-Received: by 2002:a17:902:7086:: with SMTP id z6-v6mr21278078plk.330.1531183806442; Mon, 09 Jul 2018 17:50:06 -0700 (PDT) X-Received: by 2002:a17:902:7086:: with SMTP id z6-v6mr21278052plk.330.1531183805652; Mon, 09 Jul 2018 17:50:05 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1531183805; cv=none; d=google.com; s=arc-20160816; b=XBTbaNBGwDis5zh8EB4ADONBJmzVKe9a1O+YkXAJZqYlJ0iG7IKkwxBcMiakvVKImB X0PE+uf2o/q2MYR+nErRvKbuSdjOuTSAGxMgxbBw/IQFNjCp6DHZ+JU7F9Lbhj9djM/8 WJyOLoeJ8OMHuz3ktBeiUMyLW1MF+uHmwZafFhfSM9LVkpYBy9PYJdPFu5mE9xoMqAjy a5o3/JMsJmsIKlGvrzu+WMSVEbv7F5HGGt3OJEjeIbJIggaTm/q8+OJMUIFWUMG+EDPB pi0P++wyme4UO2DIlkQqqHI91ZcO5lhDztWvXt1ZhHsn6HqnU+LHHi0WXfYQvFd+gQF1 LJhw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:user-agent:message-id:subject:cc:to:from:date :dkim-signature:arc-authentication-results; bh=IqiUZ33GqRn3PXo40N7IwiYQfJSSTHFLTLMGHHlWO44=; b=YV4/kVUKZKiJvKZWCvk8zNG9AuLviMeFvrrpI9//bmWMxY+1V1hMYrBut94AMw4AbG 8NE9T1oDPnvIgTtoNcSJ1AbZm4yxb+F32CTKW2x0XEAGNUJg4IfBkbA8jz27mO6KRilp 20DkNRi9Irw7TL8fwRRVAeqguOSQkb74jQMLyjVnrCAFqtdgxm6IbbHAIdwhtCX8MZAE NPA5jdwjeUk/jdTo6/qu/Q8VOAfP6BYfS2oEynnwRcM5Zbzzt3y1tXOY1Ljm/KYppVlW WBDMo9KtLGIGBguGfUh/JIMjVSDLHB9/LqQ+U40E99yLLTqAmWQZ07wBO7grORWOKq5D 9vYg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=YuttjFIc; spf=pass (google.com: domain of rientjes@google.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=rientjes@google.com; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com Received: from mail-sor-f65.google.com (mail-sor-f65.google.com. [209.85.220.65]) by mx.google.com with SMTPS id f34-v6sor5123347ple.122.2018.07.09.17.50.05 for (Google Transport Security); Mon, 09 Jul 2018 17:50:05 -0700 (PDT) Received-SPF: pass (google.com: domain of rientjes@google.com designates 209.85.220.65 as permitted sender) client-ip=209.85.220.65; Authentication-Results: mx.google.com; dkim=pass header.i=@google.com header.s=20161025 header.b=YuttjFIc; spf=pass (google.com: domain of rientjes@google.com designates 209.85.220.65 as permitted sender) smtp.mailfrom=rientjes@google.com; dmarc=pass (p=REJECT sp=REJECT dis=NONE) header.from=google.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=date:from:to:cc:subject:message-id:user-agent:mime-version; bh=IqiUZ33GqRn3PXo40N7IwiYQfJSSTHFLTLMGHHlWO44=; b=YuttjFIccqLY8XMptyXW8jvNCnucGhgxH4qMmrWBWiOb61/RLa9dX5g8UNEIWfK6ef yg6fb4wN+eWyNieEppWQCeSkVNbeNkinDE86oZzZYdkyD/LRdXKlrfWgtCciAtZ7c1nh yeIvzXfP62hMClIiY1c8G4j2xJAXwjeB3Bys++NlaiL184QbGJ5MDU+E3NQu9dL7eWCA FbaBZzO2AeI5Iak3iVKp15unbVtEm/drZV8yrPs79P1MsSgwzWlnZFuJdMXf5/+p3RNZ BRcEHns0JuzWew1pPTbofkprXX7mglQzdsCcsQGS5MECVWAA6CNqMqazhHK2SB+NA0yf JoqQ== X-Google-Smtp-Source: AAOMgpeWeCoaZooorww6LFD3rKy/LzATSWA4DGbNRBYDJCP/rIKdl9Ew/fsDC4bE3lfOufJuc0QqJw== X-Received: by 2002:a17:902:280b:: with SMTP id e11-v6mr22448704plb.298.1531183804945; Mon, 09 Jul 2018 17:50:04 -0700 (PDT) Received: from [2620:15c:17:3:3a5:23a7:5e32:4598] ([2620:15c:17:3:3a5:23a7:5e32:4598]) by smtp.gmail.com with ESMTPSA id s22-v6sm26642174pgs.34.2018.07.09.17.50.03 (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 09 Jul 2018 17:50:04 -0700 (PDT) Date: Mon, 9 Jul 2018 17:50:03 -0700 (PDT) From: David Rientjes X-X-Sender: rientjes@chino.kir.corp.google.com To: Andrew Morton cc: Linus Torvalds , Davidlohr Bueso , Alexey Dobriyan , linux-kernel@vger.kernel.org, linux-mm@kvack.org Subject: [patch] mm, vmacache: hash addresses based on pmd Message-ID: User-Agent: Alpine 2.21 (DEB 202 2017-01-01) MIME-Version: 1.0 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 perf profiling a wide variety of different workloads, it was found that vmacache_find() had higher than expected cost: up to 0.08% of cpu utilization in some cases. This was found to rival other core VM functions such as alloc_pages_vma() with thp enabled and default mempolicy, and the conditionals in __get_vma_policy(). VMACACHE_HASH() determines which of the four per-task_struct slots a vma is cached for a particular address. This currently depends on the pfn, so pfn 5212 occupies a different vmacache slot than its neighboring pfn 5213. vmacache_find() iterates through all four of current's vmacache slots when looking up an address. Hashing based on pfn, an address has ~1/VMACACHE_SIZE chance of being cached in the first vmacache slot, or about 25%, *if* the vma is cached. This patch hashes an address by its pmd instead of pte to optimize for workloads with good spatial locality. This results in a higher probability of vmas being cached in the first slot that is checked: normally ~70% on the same workloads instead of 25%. Signed-off-by: David Rientjes --- include/linux/vmacache.h | 6 ------ mm/vmacache.c | 32 ++++++++++++++++++++++---------- 2 files changed, 22 insertions(+), 16 deletions(-) diff --git a/include/linux/vmacache.h b/include/linux/vmacache.h --- a/include/linux/vmacache.h +++ b/include/linux/vmacache.h @@ -5,12 +5,6 @@ #include #include -/* - * Hash based on the page number. Provides a good hit rate for - * workloads with good locality and those with random accesses as well. - */ -#define VMACACHE_HASH(addr) ((addr >> PAGE_SHIFT) & VMACACHE_MASK) - static inline void vmacache_flush(struct task_struct *tsk) { memset(tsk->vmacache.vmas, 0, sizeof(tsk->vmacache.vmas)); diff --git a/mm/vmacache.c b/mm/vmacache.c --- a/mm/vmacache.c +++ b/mm/vmacache.c @@ -7,6 +7,12 @@ #include #include +/* + * Hash based on the pmd of addr. Provides a good hit rate for workloads with + * spatial locality. + */ +#define VMACACHE_HASH(addr) ((addr >> PMD_SHIFT) & VMACACHE_MASK) + /* * Flush vma caches for threads that share a given mm. * @@ -87,6 +93,7 @@ static bool vmacache_valid(struct mm_struct *mm) struct vm_area_struct *vmacache_find(struct mm_struct *mm, unsigned long addr) { + int idx = VMACACHE_HASH(addr); int i; count_vm_vmacache_event(VMACACHE_FIND_CALLS); @@ -95,16 +102,18 @@ struct vm_area_struct *vmacache_find(struct mm_struct *mm, unsigned long addr) return NULL; for (i = 0; i < VMACACHE_SIZE; i++) { - struct vm_area_struct *vma = current->vmacache.vmas[i]; - - if (!vma) - continue; - if (WARN_ON_ONCE(vma->vm_mm != mm)) - break; - if (vma->vm_start <= addr && vma->vm_end > addr) { - count_vm_vmacache_event(VMACACHE_FIND_HITS); - return vma; + struct vm_area_struct *vma = current->vmacache.vmas[idx]; + + if (vma) { + if (WARN_ON_ONCE(vma->vm_mm != mm)) + break; + if (vma->vm_start <= addr && vma->vm_end > addr) { + count_vm_vmacache_event(VMACACHE_FIND_HITS); + return vma; + } } + if (++idx == VMACACHE_SIZE) + idx = 0; } return NULL; @@ -115,6 +124,7 @@ struct vm_area_struct *vmacache_find_exact(struct mm_struct *mm, unsigned long start, unsigned long end) { + int idx = VMACACHE_HASH(addr); int i; count_vm_vmacache_event(VMACACHE_FIND_CALLS); @@ -123,12 +133,14 @@ struct vm_area_struct *vmacache_find_exact(struct mm_struct *mm, return NULL; for (i = 0; i < VMACACHE_SIZE; i++) { - struct vm_area_struct *vma = current->vmacache.vmas[i]; + struct vm_area_struct *vma = current->vmacache.vmas[idx]; if (vma && vma->vm_start == start && vma->vm_end == end) { count_vm_vmacache_event(VMACACHE_FIND_HITS); return vma; } + if (++idx == VMACACHE_SIZE) + idx = 0; } return NULL;