From patchwork Fri Nov 2 19:38:00 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Omar Sandoval X-Patchwork-Id: 10666075 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 3663215E9 for ; Fri, 2 Nov 2018 19:38:21 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 18FE42C2FB for ; Fri, 2 Nov 2018 19:38:21 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 0A7BA2C3AD; Fri, 2 Nov 2018 19:38:21 +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=-7.9 required=2.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,MAILING_LIST_MULTI,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id EC3222C2FB for ; Fri, 2 Nov 2018 19:38:19 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1726083AbeKCEqq (ORCPT ); Sat, 3 Nov 2018 00:46:46 -0400 Received: from mail-it1-f194.google.com ([209.85.166.194]:35739 "EHLO mail-it1-f194.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1726051AbeKCEqp (ORCPT ); Sat, 3 Nov 2018 00:46:45 -0400 Received: by mail-it1-f194.google.com with SMTP id p64-v6so4712104itp.0 for ; Fri, 02 Nov 2018 12:38:18 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=osandov-com.20150623.gappssmtp.com; s=20150623; h=from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=jOg/CObFhwytfz1lmhB0K7QBqs9dht/T7GlAXZ83TEQ=; b=YvwwstJ68dT/ysy2mCjRo20SzyGMyv2+dW79tLhpDmTrSV+DTVmSvQzhpeeAeoCb6d GVPr5uZt4+hShN5CO/sVHg34Lm/jSOH63aesHzcnGiAF1iHJfkYEnCg+sSi1E/6ET7BQ IeSH862rbgWX2qJIWXO/MorVQnLHEZnbVwciGoPA41ng0/jMxLdXTxrwiP0WU2KfAi3s YQ+cvO2xbWR4vpAO0hj6y6/XBkySH+Z6uKzjIBb33gvy/BfaZMp0UUG8jLwcgzFzR2f3 UIda3o0ukI9WIkRUEt5dkxptgb4q6AyZVKLUoAfjGadymY8V+DQ4LeEGJsznsfNSYpUp 3rJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:to:cc:subject:date:message-id:mime-version :content-transfer-encoding; bh=jOg/CObFhwytfz1lmhB0K7QBqs9dht/T7GlAXZ83TEQ=; b=kSq2Zd9soOroYs7P0cAB5pin8VjAwXGbNQKElpucyq2nY49pOvHABvVWKD8hfXIs9j XTBcikvpWPlGZ1iwCbZrXvUgrLiTQhQEezvFPzl/kpf7pqQaolu/1ykgXCS3kNVRZpcX LYwjiOGQJ3F5vYIzxbtyyUyFaDcyToW+XEuClQ2JCgR3QdWafMNeSB66d677ehlqVLn5 NLQH6uea4mlFcfx1wOhAelrD/NH14c+1inuxGF7QuTM4lCxNLy75bc0WbozShbt0aM+5 8Wan9RDFIvRnbVY7zfPHi4NWiw+g5TE9QmnP/WSi8L4mCM0CpXpFF/sDNGpessUDzJwJ Po4w== X-Gm-Message-State: AGRZ1gK9RA78m7YzcG7Ep5Gwz43YkReYKx+HSxiBDR0JpSLHivyjOOaN RpehdlsByqkHJq6t4TZYdhzgvXN+a/A= X-Google-Smtp-Source: AJdET5cKiXElbY9btLnzyRvftIJIHouEj91H1e8lLGTSch31baxzVCfzeiiP5FkvJA7dM1ZIAkQ+gA== X-Received: by 2002:a24:a10:: with SMTP id 16-v6mr147870itw.145.1541187497651; Fri, 02 Nov 2018 12:38:17 -0700 (PDT) Received: from vader.thefacebook.com ([2620:10d:c090:200::4:e24f]) by smtp.gmail.com with ESMTPSA id y7-v6sm16606747itb.40.2018.11.02.12.38.16 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 02 Nov 2018 12:38:17 -0700 (PDT) From: Omar Sandoval To: linux-xfs@vger.kernel.org Cc: kernel-team@fb.com Subject: [PATCH] xfs: cache minimum realtime summary level Date: Fri, 2 Nov 2018 12:38:00 -0700 Message-Id: <74441433f31eeb7f0c9fb49a04173ac2417d349a.1541187228.git.osandov@fb.com> X-Mailer: git-send-email 2.19.1 MIME-Version: 1.0 Sender: linux-xfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Omar Sandoval The realtime summary is a two-dimensional array on disk, effectively: u32 rsum[log2(number of realtime extents) + 1][number of blocks in the bitmap] rsum[log][bbno] is the number of extents of size 2**log which start in bitmap block bbno. xfs_rtallocate_extent_near() uses xfs_rtany_summary() to check whether rsum[log][bbno] != 0 for any log level. However, the summary array is stored in row-major order (i.e., like an array in C), so all of these entries are not adjacent, but rather spread across the entire summary file. In the worst case (a full bitmap block), xfs_rtany_summary() has to check every level. This means that on a moderately-used realtime device, an allocation will waste a lot of time finding, reading, and releasing buffers for the realtime summary. In particular, one of our storage services (which runs on servers with 8 very slow CPUs and 15 8 TB XFS realtime filesystems) spends almost 5% of its CPU cycles in xfs_rtbuf_get() and xfs_trans_brelse() called from xfs_rtany_summary(). One solution would be to swap the dimensions of the summary array so that different sizes on the same bitmap block are adjacent. However, this would require a disk format change to a very old component of XFS, and it would slow down xfs_rtallocate_extent_size(). Instead, we can cache the minimum size which contains any extents. We do so lazily; rather than guaranteeing that the cache contains the precise minimum, it always contains a loose lower bound which we tighten when we read or update a summary block. This only uses a few kilobytes of memory and is already serialized via the realtime bitmap and summary inode locks, so the cost is minimal. With this change, the same workload only spends 0.2% of its CPU cycles in the realtime allocator. Signed-off-by: Omar Sandoval --- This patch is based on Linus' current master branch. fs/xfs/libxfs/xfs_rtbitmap.c | 4 ++++ fs/xfs/xfs_mount.h | 6 ++++++ fs/xfs/xfs_rtalloc.c | 27 +++++++++++++++++++++++---- 3 files changed, 33 insertions(+), 4 deletions(-) diff --git a/fs/xfs/libxfs/xfs_rtbitmap.c b/fs/xfs/libxfs/xfs_rtbitmap.c index b228c821bae6..6d4990717cee 100644 --- a/fs/xfs/libxfs/xfs_rtbitmap.c +++ b/fs/xfs/libxfs/xfs_rtbitmap.c @@ -505,6 +505,10 @@ xfs_rtmodify_summary_int( uint first = (uint)((char *)sp - (char *)bp->b_addr); *sp += delta; + if (*sp == 0 && log == mp->m_rsum_cache[bbno]) + mp->m_rsum_cache[bbno]++; + if (*sp != 0 && log < mp->m_rsum_cache[bbno]) + mp->m_rsum_cache[bbno] = log; xfs_trans_log_buf(tp, bp, first, first + sizeof(*sp) - 1); } if (sum) diff --git a/fs/xfs/xfs_mount.h b/fs/xfs/xfs_mount.h index 7964513c3128..2b626a4b4824 100644 --- a/fs/xfs/xfs_mount.h +++ b/fs/xfs/xfs_mount.h @@ -89,6 +89,12 @@ typedef struct xfs_mount { int m_logbsize; /* size of each log buffer */ uint m_rsumlevels; /* rt summary levels */ uint m_rsumsize; /* size of rt summary, bytes */ + /* + * Cache of rt summary level per bitmap block with the invariant that + * m_rsum_cache[bbno] <= the minimum i for which rsum[i][bbno] != 0. + * Reads and writes are serialized by the rsumip inode lock. + */ + uint8_t *m_rsum_cache; struct xfs_inode *m_rbmip; /* pointer to bitmap inode */ struct xfs_inode *m_rsumip; /* pointer to summary inode */ struct xfs_inode *m_rootip; /* pointer to root directory */ diff --git a/fs/xfs/xfs_rtalloc.c b/fs/xfs/xfs_rtalloc.c index 926ed314ffba..351bdc6a84cb 100644 --- a/fs/xfs/xfs_rtalloc.c +++ b/fs/xfs/xfs_rtalloc.c @@ -64,8 +64,12 @@ xfs_rtany_summary( int log; /* loop counter, log2 of ext. size */ xfs_suminfo_t sum; /* summary data */ + /* There are no extents at levels < m_rsum_cache[bbno]. */ + if (low < mp->m_rsum_cache[bbno]) + low = mp->m_rsum_cache[bbno]; + /* - * Loop over logs of extent sizes. Order is irrelevant. + * Loop over logs of extent sizes. */ for (log = low; log <= high; log++) { /* @@ -80,13 +84,17 @@ xfs_rtany_summary( */ if (sum) { *stat = 1; - return 0; + goto out; } } /* * Found nothing, return failure. */ *stat = 0; +out: + /* There were no extents at levels < log. */ + if (log > mp->m_rsum_cache[bbno]) + mp->m_rsum_cache[bbno] = log; return 0; } @@ -1187,8 +1195,8 @@ xfs_rtmount_init( } /* - * Get the bitmap and summary inodes into the mount structure - * at mount time. + * Get the bitmap and summary inodes and the summary cache into the mount + * structure at mount time. */ int /* error */ xfs_rtmount_inodes( @@ -1211,6 +1219,16 @@ xfs_rtmount_inodes( return error; } ASSERT(mp->m_rsumip != NULL); + /* + * The rsum cache is initialized to all zeroes, which trivially + * satisfies the invariant. + */ + mp->m_rsum_cache = kvzalloc(sbp->sb_rbmblocks, GFP_KERNEL); + if (!mp->m_rsum_cache) { + xfs_irele(mp->m_rbmip); + xfs_irele(mp->m_rsumip); + return -ENOMEM; + } return 0; } @@ -1218,6 +1236,7 @@ void xfs_rtunmount_inodes( struct xfs_mount *mp) { + kvfree(mp->m_rsum_cache); if (mp->m_rbmip) xfs_irele(mp->m_rbmip); if (mp->m_rsumip)