From patchwork Thu Nov 9 13:26:55 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Christoph Hellwig X-Patchwork-Id: 10050921 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 AC85B603FF for ; Thu, 9 Nov 2017 13:27:25 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 986142ABD5 for ; Thu, 9 Nov 2017 13:27:25 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 8D5702AC5E; Thu, 9 Nov 2017 13:27:25 +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=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID 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 2E6CF2AC3C for ; Thu, 9 Nov 2017 13:27:25 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754684AbdKIN1X (ORCPT ); Thu, 9 Nov 2017 08:27:23 -0500 Received: from bombadil.infradead.org ([65.50.211.133]:54859 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754690AbdKIN1R (ORCPT ); Thu, 9 Nov 2017 08:27:17 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=References:In-Reply-To:Message-Id: Date:Subject:Cc:To:From:Sender:Reply-To:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=YkfCwdn01iCb/5alCL2hgX2eRYIYrzCOpy5Z9cL8yHc=; b=E1SVj/i7/uzlhSrBf5oIuuFxv oxUhvM1Hgp8YSXtueh8JAWNouj9C/GG+TKij1rydYRra/ULG0YzWT8FO562cX6VclF9D/+B0nvnxu n22PQri59vqNFDtlYOpbZTn4YwhfQqLRPZI69CDIKSP+Sr67dZAi3a4FldnnQbrYjWBYyi2gqAzbb 6sbABpw8h03ApTB+TBdn1M0ZTa3YFks9a0UxKHjlzO/HfqcPF1wOhatJp6PIpQ1wpc5foIq84om4a 1FtAUFqq68GQM0qNir72kJK+IuxYoKmjFNyMtqmx5hW/HTOjQgZ8yEJU3tpI4YHDaD4/YhA4OMtWd EBY08O30Q==; Received: from 80-109-164-210.cable.dynamic.surfer.at ([80.109.164.210] helo=localhost) by bombadil.infradead.org with esmtpsa (Exim 4.87 #1 (Red Hat Linux)) id 1eCmrV-0002ZI-AT; Thu, 09 Nov 2017 13:27:17 +0000 From: Christoph Hellwig To: linux-xfs@vger.kernel.org Cc: bfoster@redhat.com Subject: [PATCH 5/6] xfs: add comments documenting the rebalance algorithm Date: Thu, 9 Nov 2017 14:26:55 +0100 Message-Id: <20171109132656.1649-6-hch@lst.de> X-Mailer: git-send-email 2.14.2 In-Reply-To: <20171109132656.1649-1-hch@lst.de> References: <20171109132656.1649-1-hch@lst.de> X-SRS-Rewrite: SMTP reverse-path rewritten from by bombadil.infradead.org. See http://www.infradead.org/rpr.html 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 Reported-by: Brian Foster Signed-off-by: Christoph Hellwig --- fs/xfs/libxfs/xfs_iext_tree.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/fs/xfs/libxfs/xfs_iext_tree.c b/fs/xfs/libxfs/xfs_iext_tree.c index 3974989b0929..81e0480822d8 100644 --- a/fs/xfs/libxfs/xfs_iext_tree.c +++ b/fs/xfs/libxfs/xfs_iext_tree.c @@ -672,6 +672,11 @@ xfs_iext_rebalance_node( struct xfs_iext_node *node, int nr_entries) { + /* + * If the neighbouring nodes are completely full, or have different + * parents, we might never be able to merge our node, and will only + * delete it once the number of entries hits zero. + */ if (nr_entries == 0) return node; @@ -693,6 +698,11 @@ xfs_iext_rebalance_node( int nr_next = xfs_iext_node_nr_entries(next, 0), i; if (nr_entries + nr_next <= KEYS_PER_NODE) { + /* + * Merge the next node into this node so that we don't + * have to do an additional update of the keys in the + * higher levels. + */ for (i = 0; i < nr_next; i++) { node->keys[nr_entries + i] = next->keys[i]; node->ptrs[nr_entries + i] = next->ptrs[i]; @@ -741,6 +751,11 @@ xfs_iext_remove_node( return; if (level < ifp->if_height) { + /* + * If we aren't at the root yet try to find a neighbour node to + * merge with (or delete the node if it is empty), and then + * recurse up to the next level. + */ level++; parent = xfs_iext_find_level(ifp, offset, level); pos = xfs_iext_node_pos(parent, offset); @@ -755,6 +770,10 @@ xfs_iext_remove_node( goto again; } } else if (nr_entries == 1) { + /* + * If we are at the root and only one entry is left we can just + * free this node and update the root pointer. + */ ASSERT(node == ifp->if_u1.if_root); ifp->if_u1.if_root = node->ptrs[0]; ifp->if_height--; @@ -789,6 +808,11 @@ xfs_iext_rebalance_leaf( int nr_next = xfs_iext_leaf_nr_entries(ifp, leaf->next, 0), i; if (fill + nr_next <= RECS_PER_LEAF) { + /* + * Merge the next node into this node so that we don't + * have to do an additional update of the keys in the + * higher levels. + */ for (i = 0; i < nr_next; i++) leaf->recs[fill + i] = leaf->next->recs[i];