From patchwork Mon Sep 30 18:54:36 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: James Simmons X-Patchwork-Id: 11167115 Return-Path: Received: from mail.kernel.org (pdx-korg-mail-1.web.codeaurora.org [172.30.200.123]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id CA9A516B1 for ; Mon, 30 Sep 2019 18:59:16 +0000 (UTC) Received: from pdx1-mailman02.dreamhost.com (pdx1-mailman02.dreamhost.com [64.90.62.194]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id B320F224D5 for ; Mon, 30 Sep 2019 18:59:16 +0000 (UTC) DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org B320F224D5 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=infradead.org Authentication-Results: mail.kernel.org; spf=none smtp.mailfrom=lustre-devel-bounces@lists.lustre.org Received: from pdx1-mailman02.dreamhost.com (localhost [IPv6:::1]) by pdx1-mailman02.dreamhost.com (Postfix) with ESMTP id ED9715C3B49; Mon, 30 Sep 2019 11:58:12 -0700 (PDT) X-Original-To: lustre-devel@lists.lustre.org Delivered-To: lustre-devel-lustre.org@pdx1-mailman02.dreamhost.com Received: from smtp4.ccs.ornl.gov (smtp4.ccs.ornl.gov [160.91.203.40]) by pdx1-mailman02.dreamhost.com (Postfix) with ESMTP id 848A05C340D for ; Mon, 30 Sep 2019 11:57:03 -0700 (PDT) Received: from star.ccs.ornl.gov (star.ccs.ornl.gov [160.91.202.134]) by smtp4.ccs.ornl.gov (Postfix) with ESMTP id 5709E1005395; Mon, 30 Sep 2019 14:56:56 -0400 (EDT) Received: by star.ccs.ornl.gov (Postfix, from userid 2004) id 557FABB; Mon, 30 Sep 2019 14:56:56 -0400 (EDT) From: James Simmons To: Andreas Dilger , Oleg Drokin , NeilBrown Date: Mon, 30 Sep 2019 14:54:36 -0400 Message-Id: <1569869810-23848-18-git-send-email-jsimmons@infradead.org> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1569869810-23848-1-git-send-email-jsimmons@infradead.org> References: <1569869810-23848-1-git-send-email-jsimmons@infradead.org> Subject: [lustre-devel] [PATCH 017/151] lustre: ldlm: Use interval tree to update kms X-BeenThere: lustre-devel@lists.lustre.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: "For discussing Lustre software development." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: Lustre Development List MIME-Version: 1.0 Errors-To: lustre-devel-bounces@lists.lustre.org Sender: "lustre-devel" From: Patrick Farrell Currently, ldlm_extent_shift_kms does a linear search of the list of granted locks on the resource when looking for the lock to use to update the kms. This can be avoided by using the interval trees which store the extents of granted locks. We change the interval tree to store locks in reverse order, with lowest end first, and highest end last. Then we can easily find the last lock-end that doesn't ignore kms, and use that to choose a new kms. NeilBrown: modified from original to work with linux interval-tree WC-bug-id: https://jira.whamcloud.com/browse/LU-8272 Lustre-commit: e7cf1b060ba3 ("LU-8272 ldlm: Use interval tree to update kms") Signed-off-by: Patrick Farrell Signed-off-by: NeilBrown Reviewed-on: https://review.whamcloud.com/20779 Reviewed-by: Vitaly Fertman Reviewed-by: Jinshan Xiong Reviewed-by: Oleg Drokin Signed-off-by: James Simmons --- fs/lustre/ldlm/ldlm_extent.c | 66 ++++++++++++++++++++++++++++++++++---------- 1 file changed, 51 insertions(+), 15 deletions(-) diff --git a/fs/lustre/ldlm/ldlm_extent.c b/fs/lustre/ldlm/ldlm_extent.c index 0695f7e..66616b0 100644 --- a/fs/lustre/ldlm/ldlm_extent.c +++ b/fs/lustre/ldlm/ldlm_extent.c @@ -55,13 +55,22 @@ #include "ldlm_internal.h" #include -#define START(node) ((node)->l_policy_data.l_extent.start) -#define LAST(node) ((node)->l_policy_data.l_extent.end) +/* We sort the interval tree in reverse order, because we sometimes + * and to find the interval with the highest end, and the first/next + * iteration only allows is to walk in increasing order of start. + */ +#define ISTART(end) (U64_MAX - (end)) +#define IEND(start) (U64_MAX - (start)) + +#define START(node) ISTART((node)->l_policy_data.l_extent.end) +#define LAST(node) IEND((node)->l_policy_data.l_extent.start) INTERVAL_TREE_DEFINE(struct ldlm_lock, l_rb, u64, __subtree_last, START, LAST, static, extent); /* When a lock is cancelled by a client, the KMS may undergo change if this - * is the "highest lock". This function returns the new KMS value. + * is the "highest lock". This function returns the new KMS value, updating + * it only if we were the highest lock. + * * Caller must hold lr_lock already. * * NB: A lock on [x,y] protects a KMS of up to y + 1 bytes! @@ -69,8 +78,11 @@ u64 ldlm_extent_shift_kms(struct ldlm_lock *lock, u64 old_kms) { struct ldlm_resource *res = lock->l_resource; + struct ldlm_interval_tree *tree; struct ldlm_lock *lck; u64 kms = 0; + int idx = 0; + bool complete; /* don't let another thread in ldlm_extent_shift_kms race in * just after we finish and take our lock into account in its @@ -78,20 +90,44 @@ u64 ldlm_extent_shift_kms(struct ldlm_lock *lock, u64 old_kms) */ ldlm_set_kms_ignore(lock); - list_for_each_entry(lck, &res->lr_granted, l_res_link) { - if (ldlm_is_kms_ignore(lck)) - continue; + /* We iterate over the lock trees, looking for the largest kms + * smaller than the current one. Note that each tree is + * iterated starting a largest end, because the interval tree + * is stored last-to-first order. + */ + for (idx = 0; idx < LCK_MODE_NUM; idx++) { + tree = &res->lr_itree[idx]; - if (lck->l_policy_data.l_extent.end >= old_kms) - return old_kms; + for (lck = extent_iter_first(&tree->lit_root, 0, U64_MAX); + lck; + lck = extent_iter_next(lck, 0, U64_MAX)) { + if (ldlm_is_kms_ignore(lck)) + continue; - /* This extent _has_ to be smaller than old_kms (checked above) - * so kms can only ever be smaller or the same as old_kms. + /* This is the last lock-end that doesn't ignore + * kms. + * If it has a greater or equal kms, we are not + * the highest lock (or we share that distinction + * with another lock), and don't need to update KMS. + * Record old_kms and stop looking. + */ + if (lck->l_policy_data.l_extent.end >= old_kms) { + kms = old_kms; + complete = true; + } else + kms = lck->l_policy_data.l_extent.end + 1; + break; + } + + /* this tells us we're not the highest lock, so we don't need + * to check the remaining trees */ - if (lck->l_policy_data.l_extent.end + 1 > kms) - kms = lck->l_policy_data.l_extent.end + 1; + if (complete) + break; } - LASSERTF(kms <= old_kms, "kms %llu old_kms %llu\n", kms, old_kms); + + LASSERTF(kms <= old_kms, "kms %llu old_kms %llu\n", kms, + old_kms); return kms; } @@ -197,9 +233,9 @@ void ldlm_extent_search(struct rb_root_cached *root, { struct ldlm_lock *lock; - for (lock = extent_iter_first(root, start, end); + for (lock = extent_iter_first(root, ISTART(end), IEND(start)); lock; - lock = extent_iter_next(lock, start, end)) + lock = extent_iter_next(lock, ISTART(end), IEND(start))) if (matches(lock, data)) break; }