From patchwork Fri Aug 9 00:40:48 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: JaeJoon Jung X-Patchwork-Id: 13758263 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 5F1BEC3DA4A for ; Fri, 9 Aug 2024 00:41:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id CA1296B0089; Thu, 8 Aug 2024 20:41:12 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id C50246B008A; Thu, 8 Aug 2024 20:41:12 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id AF0A76B008C; Thu, 8 Aug 2024 20:41:12 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0015.hostedemail.com [216.40.44.15]) by kanga.kvack.org (Postfix) with ESMTP id 8CA456B0089 for ; Thu, 8 Aug 2024 20:41:12 -0400 (EDT) Received: from smtpin07.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id 2F0681404C3 for ; Fri, 9 Aug 2024 00:41:12 +0000 (UTC) X-FDA: 82430852784.07.B0DED93 Received: from mail-oo1-f54.google.com (mail-oo1-f54.google.com [209.85.161.54]) by imf17.hostedemail.com (Postfix) with ESMTP id 7CE814001B for ; Fri, 9 Aug 2024 00:41:10 +0000 (UTC) Authentication-Results: imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=RW7192pQ; spf=pass (imf17.hostedemail.com: domain of rgbi3307@gmail.com designates 209.85.161.54 as permitted sender) smtp.mailfrom=rgbi3307@gmail.com; dmarc=pass (policy=none) header.from=gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1723164005; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:content-type: content-transfer-encoding:in-reply-to:references:dkim-signature; bh=47tFDCUc6tXdpmSpkydMhn345YMpNq+/67xmcx53pO8=; b=tpShTx937aS3IApHG8OApuC8ljKklmx7uXBfKdCiSr/ZqIuyEbRDCcPovg5p0TlmTgZcHx 5/SMsb49V16jlyJ2evB8Er1jFijklDJp3iezGqf9NhW75nW7tkeWM8qJn5vH9LldVX42Oa zuYMHBI2OOfXVKRo6mWJDNwumJKqOTc= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1723164005; a=rsa-sha256; cv=none; b=XqLpTltZ6kxclihiokOtJLpXc5+664Eq3OSFLTVnxij9VoDjpUyD7z23oXh30R62f5nfM6 0qXpSJFUk+G2aTmI580D6cA7vyQ02beoWlag8VHOldEPOMNx29juaa0Bzpc0a37MY+PCk4 JmqocdeUjaUWTeevzNqExiMFsi+0MsI= ARC-Authentication-Results: i=1; imf17.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=RW7192pQ; spf=pass (imf17.hostedemail.com: domain of rgbi3307@gmail.com designates 209.85.161.54 as permitted sender) smtp.mailfrom=rgbi3307@gmail.com; dmarc=pass (policy=none) header.from=gmail.com Received: by mail-oo1-f54.google.com with SMTP id 006d021491bc7-5d5eec95a74so904298eaf.1 for ; Thu, 08 Aug 2024 17:41:10 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1723164069; x=1723768869; darn=kvack.org; h=message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=47tFDCUc6tXdpmSpkydMhn345YMpNq+/67xmcx53pO8=; b=RW7192pQ6KQpHobQn03erevD41Gna8UDG0eSn8EDZlg758W+Jf3g0YoE/Swp6/LmSI wSOBQxWzq3RdphBYAgt+HzJEUAAkBvOM5gGe4pMsNC2pL0JeNXjRAYDNtv12wY1PMXBn dfn39igz60kqeDv6be/44U6of9CHdcHcaZmpFyRfaC5ab8CrwVlMHAqtOCGM6ZNIbZ5V j4YykntvYNUjufvKDMLTMT/dbktS8pI+FB3W9WH3PRoxP6y3dBjp5tH1lGWPFkuNpWOI X1BlZLp45QUhaYXWsGgS3foy7w35Gd1yNAbKNrs7iq83/hzCEB2Mg9+qrluEsUaflzu4 Bj8Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723164069; x=1723768869; h=message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=47tFDCUc6tXdpmSpkydMhn345YMpNq+/67xmcx53pO8=; b=hP/QwZbMpxz7kN7GG6jdHGNxz4m8DjgucoRoN8dM2oBXw/9uPU2car2DarLjshdilg PAxjMjq0p2pHu3P198qxm+yVvxfgxuqTe//tbmuVF1O8LmjDibBSimVwo4o2dmeQ5jCB JThBE0usjWWpydgh1p8FgjedKwXiNkV4IkjgJ/z1yVh5g6If30zrGlAQIKrllH3QMlId b542z1CIWokKYWW6DioHCaiHqTShipgIJUvkHtbJbJn7efMwOXicBwtJkndKPaPnTnth EopDwCIi2Sn3eNdmNjA3p1gl7SC2PIlo5XhR/FfMMyndoAuyDP2IG4TQ4JUhGIDtzBRD b35g== X-Forwarded-Encrypted: i=1; AJvYcCVF8hhoDkQ58wVQNzId/bdI9/mK3x+T7hTap98PPHvS52dmV6pmxugO8AzEkRxVy5Leh3AXi90nMNU0zSXdzGPIe5Q= X-Gm-Message-State: AOJu0YwmYXKJetswojXIkCIgdgSdcNGJFrBvhg9wgDIu+KArCGIOLTAK RQg4N9mYBC/9ifY3Qc+96n+rZwnChrqGcyPsXEgTuAqUL23idb8S X-Google-Smtp-Source: AGHT+IFhIItUWWpk89Z4/39Ud304fq3N5qoG9HxVrrwiXghvj575kpBn/nstK7/CoFpyXqSjSvA38Q== X-Received: by 2002:a05:6358:6f06:b0:1ad:14ec:9ff7 with SMTP id e5c5f4694b2df-1b15cf882b4mr432011155d.16.1723164069185; Thu, 08 Aug 2024 17:41:09 -0700 (PDT) Received: from localhost.localdomain ([180.69.210.41]) by smtp.googlemail.com with ESMTPSA id 41be03b00d2f7-7b76346b394sm8779613a12.23.2024.08.08.17.41.05 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 08 Aug 2024 17:41:08 -0700 (PDT) From: JaeJoon Jung To: Linus Torvalds , Sasha Levin , "Liam R . Howlett" , Matthew Wilcox , Greg Kroah-Hartman Cc: JaeJoon Jung , linux-kernel@vger.kernel.org, linux-mm@kvack.org, maple-tree@lists.infradead.org, linux-fsdevel@vger.kernel.org Subject: [PATCH v3] lib/htree: Added get_cycles() to measure execution time Date: Fri, 9 Aug 2024 09:40:48 +0900 Message-Id: <20240809004048.19511-1-rgbi3307@gmail.com> X-Mailer: git-send-email 2.17.1 X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 7CE814001B X-Stat-Signature: cbi9b7p64kw79hypmx6xs7zwtqotb84o X-HE-Tag: 1723164070-592726 X-HE-Meta: U2FsdGVkX1+n6YGVtywPr28NROU+hwj5eTR2xwxAvPs6MtLJoYAK03eho0wpk6rjDPtv9/JcP6F8VpvsGBrLz2E5R4Y8oPRyWcp6yF1asqfoucTBqcaOjPeW8ypDFncpKUA0gugLLnhODU4tg3H9fpafo4rGvTe4EvpGQdNKE+QE5KnOzM3Nn6I8NEYOBJYIGe6TguR3MUOGOpdn6XZqyBsC0VQhLt9SA0/mglabXK2h6jPYtxf9H5JSZS329+3ex33mLCcdEYLeOxdtcYUEhxAUsB2yOX4Ja0NBm75WPTZoQBuH1i417IcUX15kG7NzKCNldccbs2HcbsO0lGHstjt35WMVt/QrLimU+3A4rpm8oLk1/2b8+2gY5vmQ9NGywkrRQEhzgfeyz5G11idMWBPE0SfcCQQAATBQSoaYPUspuKhETQoCPQ4ZiHe1u2pl+uJnKU/fFYyuh8wK6MZTneVQ+C+8LC/QxoHgS3myvL2w/5UHlfPtHXHCSRkp9XrZ9i0cqsmlr7TFoNY48HBWTEkxuFEL7VATWgG3xPxt5ilPwLjYRgE+JL1hRukgZXqEJn933WaZmLqHALuyCLeC79X+i3Nx+M3s26nipmLJhaaSHiE5oyw/xtvxx95a+6GGkwHQYLgRC90wtxAnRDcqIPkmhZyelm/0BuHaHtXxQHJDB2GPAEt6YQ9YRGZiMQ1ndfQCGwJZLJyo+txD6v0nR56z3AQOvHYTIIm+pxWiwPxkO+yPP7i3m5j66tg3jAw1Y6xp9IWiuVK8ZKfyzY4yqwuB2zlnAJ/OOcv6PNBBGXha6aD7yLdB33snNt1SB6Fh3SKjd1BTikAyfEo09S0NlrXSr7X0P0NA8BHp2UsufPpC27Ry9EaIpPxr3fUPnFl8JiMmhJPT4InLDIbX8weI/vGhmqnSjox34eKNIxuAkkKuTy6XTew7K6yyy0bR8ZklgpEIuTpqUb774Vtm8JE bAgnDWJv WGBzG0ZfPiePP3suw8M5btcDfhOATtMuiTEqC/2XLe0tLkGBY7BAPaYIvD8IZoxCy3tmBPej3WmS/FfN8jYBYUFSKnNcDwcjCUyU3owpLCUB4fjMNyPHTGLxLaKmKSrBGITTITjRc/jubbS/NhZA1MgwqOpVgnH59psvX7WU9AuwyXJKNfL2yKw/AkNkN/nIH9YOGHy4dh/XNQ8vUjveXUgy1bb+ykG6EEVdO+i2W3NVQT3eEtVG1nXrR/cjqNOTy/AjAX021I3vLFWaKSfji4PJR/P7+jUwb7a6LSwzw3kCExBeG2zx6VW64bClt3JqvSddTGGq7MP4MuZY6PXQXilXBMUqdflDp1i+vtOq8l6DhA2TTqcRJ4yPbT5ile4ZfaHzh 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: List-Subscribe: List-Unsubscribe: Added get_cycles() to measure execution time during insert, find, and erase operations. Added check_latency() in the lib/test_xarray.c and the lib/test_maple_tree.c Added likely/unlikely to improve if conditional code. check_latency() measures latency using get_cycles() with 1M indices(nr) on XArray and Maple Tree. The output of this can be used to make the performance comparison table like this: The numerical unit is cycle. performance insert find erase ------------------------------------------------ XArray 9 6 16 Maple Tree 11 7 27 Hash Tree 6 2 12 ------------------------------------------------ Full source of Hash Tree is also available in the following github link: https://github.com/kernel-bz/htree.git Signed-off-by: JaeJoon Jung --- lib/htree-test.c | 90 +++++++++++++++++++++++++++---------------- lib/htree.c | 26 ++++++------- lib/test_maple_tree.c | 32 +++++++++++++++ lib/test_xarray.c | 31 +++++++++++++++ 4 files changed, 132 insertions(+), 47 deletions(-) diff --git a/lib/htree-test.c b/lib/htree-test.c index 5bf862706ce2..07c6a144a1be 100644 --- a/lib/htree-test.c +++ b/lib/htree-test.c @@ -10,6 +10,7 @@ #include #include #include +#include #include @@ -44,8 +45,8 @@ */ -/* #define HTREE_DEBUG_INFO +/* #define HTREE_DEBUG_DETAIL */ @@ -277,7 +278,7 @@ static void htree_debug_hdata(struct htree_state *hts, struct hash_tree *hcurr, "htf_freed", }; - if (!hcurr) + if (unlikely(!hcurr)) return; dept = hts->dept; @@ -331,7 +332,7 @@ static void __htree_debug_walks_all(struct htree_state *hts, for (k = 0; k < anum; k++) { ncnt = ht_ncnt_get(htree[k].next); - if (ncnt > 0) { + if (likely(ncnt > 0)) { bits = ht_bits_from_depth(hts->sbit, hts->dept); pr_ht_debug("d:%u b:%u [%u] %p (%u): ", hts->dept, bits, k, &htree[k], ncnt); @@ -407,14 +408,14 @@ static void __htree_erase_all_lock(struct htree_state *hts, for (k = 0; k < anum; k++) { ncnt = ht_ncnt_get(htree[k].next); - if (ncnt > 0) { + if (likely(ncnt > 0)) { bits = ht_bits_from_depth(hts->sbit, hts->dept); hlist_for_each_entry_safe(pos, tmp, &htree[k].head, hnode) { hlist_del(&pos->hnode); udata = hlist_entry_safe(pos, struct data_struct, hdata); - if (udata) { + if (likely(udata)) { kfree(udata); (*erased)++; } @@ -478,17 +479,20 @@ static u64 _htree_insert_range(struct htree_state *hts, struct htree_root *root, { u64 index; u64 loop = 0, ins = 0, era = 0; + cycles_t time1, time2; + u64 latency; struct data_struct *udata; struct htree_data *rdata; pr_ht_info("[++++) inserting: [s:%llu ... e:%llu] (g:%llu)\n", start, end, gap); + time1 = get_cycles(); for (index = start; index <= end; index += gap) { udata = _htree_data_alloc(index); rdata = ht_insert_lock(hts, root, &udata->hdata, req); if (req == htf_erase && rdata) { udata = hlist_entry_safe(rdata, struct data_struct, hdata); - if (udata && rdata->index == index) { + if (likely((udata && rdata->index == index))) { kfree(udata); era++; } @@ -498,8 +502,10 @@ static u64 _htree_insert_range(struct htree_state *hts, struct htree_root *root, if (!(loop % HTREE_TEST_SCHED_CNT)) schedule(); } - pr_ht_info("(++++] done: loop:%llu, inserted:%llu, same erased:%llu\n\n", - loop, ins, era); + time2 = get_cycles(); + latency = div_u64(time2 - time1, loop); + pr_ht_info("(++++] done: loop:%llu, inserted:%llu, same erased:%llu, \ +latency:%llu cycles\n\n", loop, ins, era, latency); return ins - era; } @@ -517,16 +523,19 @@ static u64 _htree_find_range(struct htree_state *hts, struct htree_root *root, { u64 index; u64 loop = 0, found = 0; + cycles_t time1, time2; + u64 latency; struct data_struct *udata; struct htree_data *rdata; pr_ht_info("[****) finding: [s:%llu ... e:%llu] (g:%llu)\n", start, end, gap); + time1 = get_cycles(); for (index = start; index <= end; index += gap) { rdata = ht_find(hts, htree_first_rcu(root), index); if (rdata) { udata = hlist_entry_safe(rdata, struct data_struct, hdata); - if (udata && rdata->index == index) { + if (likely(udata && rdata->index == index)) { pr_ht_find("*todo: find:<%llu> %c %c %c\n", index, udata->a, (char)udata->b, (char)udata->c); found++; @@ -537,8 +546,10 @@ static u64 _htree_find_range(struct htree_state *hts, struct htree_root *root, if (!(loop % HTREE_TEST_SCHED_CNT)) schedule(); } - pr_ht_info("(****] done: loop:%llu, found:%llu, diff:%llu\n\n", - loop, found, loop - found); + time2 = get_cycles(); + latency = div_u64(time2 - time1, loop); + pr_ht_info("(****] done: loop:%llu, found:%llu, diff:%llu, \ +latency:%llu cycles\n\n", loop, found, loop - found, latency); return found; } @@ -555,18 +566,21 @@ static u64 _htree_erase_range(struct htree_state *hts, struct htree_root *root, { u64 index; u64 loop = 0, erased = 0; + cycles_t time1, time2; + u64 latency; struct hash_tree *htree; struct data_struct *udata; struct htree_data *rdata; pr_ht_info("[----) erasing: [s:%llu ... e:%llu] (g:%llu)\n", start, end, gap); + time1 = get_cycles(); for (index = start; index <= end; index += gap) { htree = htree_first_rcu(root); rdata = ht_erase_lock(hts, root, index); if (rdata) { udata = hlist_entry_safe(rdata, struct data_struct, hdata); - if (udata && rdata->index == index) { + if (likely(udata && rdata->index == index)) { pr_ht_erase("*todo: erase:<%llu> %c %c %c\n", index, udata->a, (char)udata->b, (char)udata->c); kfree(udata); @@ -582,8 +596,10 @@ static u64 _htree_erase_range(struct htree_state *hts, struct htree_root *root, if (!(loop % HTREE_TEST_SCHED_CNT)) schedule(); } - pr_ht_info("(----] done: loop:%llu, erased:%llu, diff:%llu\n\n", - loop, erased, loop - erased); + time2 = get_cycles(); + latency = div_u64(time2 - time1, loop); + pr_ht_info("(----] done: loop:%llu, erased:%llu, diff:%llu, \ +latency:%llu cycles\n\n", loop, erased, loop - erased, latency); return erased; } @@ -600,18 +616,21 @@ static u64 _htree_update_range(struct htree_state *hts, struct htree_root *root, { u64 index; u64 loop = 0, updated = 0; + cycles_t time1, time2; + u64 latency; struct hash_tree *htree; struct data_struct *udata; struct htree_data *rdata; pr_ht_info("[####) updating: [s:%llu ... e:%llu] (g:%llu)\n", start, end, gap); + time1 = get_cycles(); for (index = start; index <= end; index += gap) { htree = htree_first_rcu(root); rdata = ht_find(hts, htree, index); if (rdata) { udata = hlist_entry_safe(rdata, struct data_struct, hdata); - if (udata && rdata->index == index) { + if (likely(udata && rdata->index == index)) { pr_ht_update("*todo: update:<%llu> %c %c %c ", index, udata->a, (char)udata->b, (char)udata->c); /* todo: update user defined data */ @@ -633,8 +652,11 @@ static u64 _htree_update_range(struct htree_state *hts, struct htree_root *root, if (!(loop % HTREE_TEST_SCHED_CNT)) schedule(); } - pr_ht_info("(####] done: loop:%llu, updated:%llu, diff:%llu\n\n", - loop, updated, loop - updated); + time2 = get_cycles(); + latency = div_u64(time2 - time1, loop); + pr_ht_info("(####] done: loop:%llu, updated:%llu, diff:%llu, \ +latency: %llu cycles\n\n", + loop, updated, loop - updated, latency); return updated; } @@ -651,7 +673,7 @@ static void _htree_statis(struct htree_state *hts, struct htree_root *root) ht_statis(hts, htree_first_rcu(root), &acnt, &dcnt); - if (hts->dcnt == dcnt && hts->acnt == acnt) { + if (likely(hts->dcnt == dcnt && hts->acnt == acnt)) { pr_ht_info("[ OK ] statist: acnt:%d, dcnt:%llu ", acnt, dcnt); } else { pr_ht_info("[FAIL] statist: acnt:%d(%d), dcnt:%llu(%llu)\n", @@ -676,7 +698,7 @@ static void _htree_statis_info(struct htree_state *hts, struct htree_root *root) u64 dsum = (sizd * hts->dcnt) >> 10; u64 smem = hsum + dsum; - if (hts->asum == 0) + if (unlikely(hts->asum == 0)) _htree_statis(hts, root); pr_ht_stat("------------------------------------------\n"); @@ -711,7 +733,7 @@ static void _htree_get_most_index(struct htree_state *hts, struct htree_root *ro struct htree_data *hdata; hdata = ht_most_index(hts, htree_first_rcu(root)); - if (hdata) { + if (likely(hdata)) { if (hts->sort == HTREE_FLAG_ASCD) { pr_ht_stat("[MOST] smallest index:%llu\n\n", hdata->index); } else { @@ -730,13 +752,13 @@ static void _htree_remove_all(struct htree_state *hts, struct htree_root *root) { /* remove all udata */ hts->dcnt -= htree_erase_all_lock(hts, root); - if (hts->dcnt != 0) { + if (unlikely(hts->dcnt != 0)) { pr_ht_warn("[WARN] erase remained acnt:%d, dcnt:%llu\n\n", hts->acnt, hts->dcnt); } /* remove all hash trees */ - if (ht_destroy_lock(hts, root) == htf_ok) { + if (likely(ht_destroy_lock(hts, root) == htf_ok)) { pr_ht_stat("[ OK ] destroy remained acnt:%d, dcnt:%llu\n\n", hts->acnt, hts->dcnt); } else { @@ -761,7 +783,7 @@ static u64 _htree_test_index_loop(struct htree_state *hts, u64 start, u64 end) u64 inserted, found, erased, updated; u64 dcnt, slice; - if (start > end) + if (unlikely(start > end)) return 0; slice = (end - start) / 10 + 2; @@ -769,7 +791,7 @@ static u64 _htree_test_index_loop(struct htree_state *hts, u64 start, u64 end) htree_root_alloc(hts, &ht_root); inserted = _htree_insert_range(hts, &ht_root, start, end, 1, htf_ins); - if (inserted != hts->dcnt) { + if (unlikely(inserted != hts->dcnt)) { pr_ht_err("[FAIL] inserted:%llu, dcnt:%llu, diff:%lld\n\n", inserted, hts->dcnt, inserted - hts->dcnt); } @@ -778,7 +800,7 @@ static u64 _htree_test_index_loop(struct htree_state *hts, u64 start, u64 end) erased = _htree_erase_range(hts, &ht_root, start, end, slice); found = _htree_find_range(hts, &ht_root, start, end, slice); - if (found) { + if (unlikely(found)) { pr_ht_err("[FAIL] erased:%llu, found:%llu, diff:%lld\n\n", erased, found, erased - found); } @@ -787,7 +809,7 @@ static u64 _htree_test_index_loop(struct htree_state *hts, u64 start, u64 end) inserted = _htree_insert_range(hts, &ht_root, start, end, slice, htf_ins); updated = _htree_update_range(hts, &ht_root, start, end, slice); - if (inserted != updated) { + if (unlikely(inserted != updated)) { pr_ht_err("[FAIL] inserted:%llu, updated:%llu, diff:%lld\n\n", inserted, updated, inserted - updated); } @@ -916,7 +938,7 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) udata = _htree_data_alloc(index); rdata = ht_insert_lock(hts, &ht_root, &udata->hdata, htf_ins); - if (!rdata) + if (likely(!rdata)) inserted++; loop++; if (!(loop % HTREE_TEST_SCHED_CNT)) @@ -926,7 +948,7 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) _htree_statis(hts, &ht_root); rdata = ht_find(hts, htree_first_rcu(&ht_root), check_idx); - if (!rdata) { + if (unlikely(!rdata)) { pr_ht_err("[FAIL] NOT found check index:%llu\n\n", check_idx); } @@ -939,7 +961,7 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) rdata = ht_erase_lock(hts, &ht_root, index); if (rdata) { udata = hlist_entry_safe(rdata, struct data_struct, hdata); - if (udata && rdata->index == index) { + if (likely(udata && rdata->index == index)) { pr_ht_erase("*todo: erase:<%llu> %c %c %c\n", index, udata->a, (char)udata->b, (char)udata->c); kfree(udata); @@ -954,7 +976,7 @@ static void _htree_test_idx_random(u8 idx_type, u8 sort_type, u64 maxnr) _htree_statis(hts, &ht_root); rdata = ht_find(hts, htree_first_rcu(&ht_root), check_idx); - if (!rdata) { + if (unlikely(!rdata)) { pr_ht_info("[INFO] check index:%llu (erased)\n\n", check_idx); } @@ -1006,7 +1028,7 @@ static void _htree_test_index_same(u8 idx_type, u8 sort_type, u64 maxnr) pr_ht_stat("[loop) %llu: new index inserting(htf_ins)\n\n", maxnr); inserted = _htree_insert_range(hts, &ht_root, 0, maxnr, gap - 1, htf_ins); - if (inserted != hts->dcnt) { + if (unlikely(inserted != hts->dcnt)) { pr_ht_err("[FAIL] inserted:%llu, dcnt:%llu, diff:%lld\n\n", inserted, hts->dcnt, inserted - hts->dcnt); } @@ -1015,20 +1037,20 @@ static void _htree_test_index_same(u8 idx_type, u8 sort_type, u64 maxnr) pr_ht_stat("[loop) %llu: SAME index inserting(htf_erase)\n\n", maxnr); inserted = _htree_insert_range(hts, &ht_root, 1, maxnr, gap, htf_erase); - if (inserted != 0) { + if (unlikely(inserted != 0)) { pr_ht_err("[FAIL] inserted:%llu, dcnt:%llu, diff:%lld\n\n", inserted, hts->dcnt, inserted - hts->dcnt); } pr_ht_stat("[loop) %llu: SAME index inserting(htf_ins)\n\n", maxnr); inserted = _htree_insert_range(hts, &ht_root, 1, maxnr, gap, htf_ins); - if (inserted != (maxnr / gap)) { + if (unlikely(inserted != (maxnr / gap))) { pr_ht_err("[FAIL] inserted:%llu, dcnt:%llu, diff:%lld\n\n", inserted, hts->dcnt, inserted - hts->dcnt); } found = _htree_find_range(hts, &ht_root, 0, maxnr, gap - 1); - if (found != (hts->dcnt - inserted)) { + if (unlikely(found != (hts->dcnt - inserted))) { pr_ht_err("[FAIL] dcnt:%llu, inserted:%llu, found:%llu\n\n", hts->dcnt, inserted, found); } diff --git a/lib/htree.c b/lib/htree.c index 1fcdb8d69730..54e5e6c5f5d1 100644 --- a/lib/htree.c +++ b/lib/htree.c @@ -114,7 +114,7 @@ static enum ht_flags __ht_find(struct htree_state *hts, struct hash_tree *htree, _retry: *rtree = htree; ncnt = ht_ncnt_get(htree[hts->hkey].next); - if (ncnt == 0) + if (unlikely(ncnt == 0)) goto _next_step; hlist_for_each_entry(pos, &htree[hts->hkey].head, hnode) { @@ -180,7 +180,7 @@ struct htree_data *ht_find(struct htree_state *hts, struct htree_data *rdata = NULL; struct hash_tree *rtree; - if (!htree) + if (unlikely(!htree)) return NULL; if (_ht_find(hts, htree, index, &rdata, &rtree) == htf_find) @@ -232,7 +232,7 @@ static void _ht_move_to_next(struct htree_state *hts, struct htree_data *sdata, } ncnt = ht_ncnt_get(ntree[hkey].next); - if (ncnt == 0) { + if (unlikely(ncnt == 0)) { htree_add_head(ntree, &edata->hnode, hkey); goto _next; } @@ -292,7 +292,7 @@ static void _ht_insert(struct htree_state *hts, struct hash_tree *htree, hts->hkey = ht_get_hkey(index, hts->dept, bits, hts->idxt); ncnt = ht_ncnt_get(htree[hts->hkey].next); - if (ncnt == 0) { + if (unlikely(ncnt == 0)) { htree_add_head(htree, &hdata->hnode, hts->hkey); goto _finish; } @@ -348,7 +348,7 @@ struct htree_data *ht_insert(struct htree_state *hts, struct hash_tree *htree, struct hash_tree *rtree = NULL; enum ht_flags htf; - if (!htree) + if (unlikely(!htree)) return NULL; htf = _ht_find(hts, htree, hdata->index, &rdata, &rtree); @@ -379,7 +379,7 @@ static enum ht_flags ___ht_erase(struct htree_state *hts, if (htree[k].next) break; - if (k == anum) { + if (unlikely(k == anum)) { kfree(htree); hts->acnt--; hts->dept--; @@ -408,7 +408,7 @@ static int __ht_erase(struct htree_state *hts, struct hash_tree *htree, ncnt = ht_ncnt_get(htree[key].next); bits = ht_bits_from_depth(hts->sbit, hts->dept); - if (ncnt == 0) + if (unlikely(ncnt == 0)) goto _next_step; hlist_for_each_entry_safe(pos, tmp, &htree[key].head, hnode) { @@ -429,7 +429,7 @@ static int __ht_erase(struct htree_state *hts, struct hash_tree *htree, } } - if (ncnt == 0) + if (unlikely(ncnt == 0)) ret = ___ht_erase(hts, htree, bits); if (ret > htf_none) /* erased or freed */ @@ -444,7 +444,7 @@ static int __ht_erase(struct htree_state *hts, struct hash_tree *htree, /* must be recursive call */ ret = __ht_erase(hts, _next, rdata, index); - if (ret == htf_freed) { + if (unlikely(ret == htf_freed)) { WRITE_ONCE(htree[key].next, ht_ncnt_set(NULL, ncnt)); ret = htf_erase; } @@ -484,7 +484,7 @@ struct htree_data *ht_erase(struct htree_state *hts, { struct htree_data *rdata = NULL; - if (!htree) + if (unlikely(!htree)) return NULL; if (_ht_erase(hts, htree, &rdata, index) == htf_erase) @@ -558,7 +558,7 @@ enum ht_flags ht_destroy_lock(struct htree_state *hts, struct htree_root *root) return htf_ok; htree = htree_first_rcu(root); - if (!htree) + if (unlikely(!htree)) return htf_none; hts->dept = 0; @@ -598,7 +598,7 @@ static void __ht_statis(struct htree_state *hts, for (k = 0; k < anum; k++) { ncnt = ht_ncnt_get(htree[k].next); - if (ncnt > 0) { + if (likely(ncnt > 0)) { (*dcnt) += ncnt; } _next = ht_ncnt_pointer(htree[k].next); @@ -631,7 +631,7 @@ void ht_statis(struct htree_state *hts, hts->dept = 0; hts->dmax = 0; - if (!htree) + if (unlikely(!htree)) return; __ht_statis(hts, htree, acnt, dcnt); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 31561e0e1a0d..dbc332d15e9d 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -10,6 +10,7 @@ #include #include #include +#include #define MTREE_ALLOC_MAX 0x2000000000000Ul #define CONFIG_MAPLE_SEARCH @@ -3638,6 +3639,34 @@ static noinline void __init alloc_cyclic_testing(struct maple_tree *mt) MT_BUG_ON(mt, ret != 1); } +static noinline void check_latency(struct maple_tree *mt) +{ + MA_STATE(mas, mt, 25203307, 25203307); + cycles_t time1, time2; + void *val; + unsigned long i, cnt = 1 << 20; + + for (i = 0; i < cnt; i++) + mtree_store(mt, i, xa_mk_value(i), GFP_KERNEL); + + pr_info("\n*check_latency(): index nr:%lu\n", cnt); + + time1 = get_cycles(); + mtree_store(mt, cnt, xa_mk_value(cnt), GFP_KERNEL); + time2 = get_cycles(); + pr_info("mtree_store(): latency:%lu cycles\n", time2 - time1); + + time1 = get_cycles(); + val = mas_find(&mas, ULONG_MAX); + time2 = get_cycles(); + pr_info("mas_find(): latency:%lu cycles\n", time2 - time1); + + time1 = get_cycles(); + mtree_erase(mt, cnt); + time2 = get_cycles(); + pr_info("mtree_erase(): latency:%lu cycles\n", time2 - time1); +} + static DEFINE_MTREE(tree); static int __init maple_tree_seed(void) { @@ -3923,6 +3952,9 @@ static int __init maple_tree_seed(void) alloc_cyclic_testing(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + check_latency(&tree); + mtree_destroy(&tree); #if defined(BENCH) skip: diff --git a/lib/test_xarray.c b/lib/test_xarray.c index d5c5cbba33ed..02fa3c95428d 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -8,6 +8,7 @@ #include #include +#include static unsigned int tests_run; static unsigned int tests_passed; @@ -2125,6 +2126,34 @@ static noinline void check_destroy(struct xarray *xa) #endif } +static noinline void check_latency(struct xarray *xa) +{ + unsigned long i, index; + unsigned long cnt = 1 << 20; + cycles_t time1, time2; + + for (i = 0; i < cnt; i++) + xa_store(xa, i, xa_mk_index(i), GFP_KERNEL); + + pr_info("\n*check_latency: index nr:%lu\n", cnt); + index = 25203307; + + time1 = get_cycles(); + xa_store(xa, index, xa_mk_index(index), GFP_KERNEL); + time2 = get_cycles(); + pr_info("xa_store(): latency: %lu cycles\n", time2 - time1); + + time1 = get_cycles(); + xa_find(xa, &index, ULONG_MAX, XA_PRESENT); + time2 = get_cycles(); + pr_info("xa_find(): latency: %lu cycles\n", time2 - time1); + + time1 = get_cycles(); + xa_erase(xa, index); + time2 = get_cycles(); + pr_info("xa_erase(): latency: %lu cycles\n", time2 - time1); +} + static DEFINE_XARRAY(array); static int xarray_checks(void) @@ -2162,6 +2191,8 @@ static int xarray_checks(void) check_workingset(&array, 64); check_workingset(&array, 4096); + check_latency(&array); + printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); return (tests_run == tests_passed) ? 0 : -EINVAL; }