From patchwork Fri Sep 20 15:15:27 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Steven Rostedt X-Patchwork-Id: 11154567 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 D482D195A for ; Fri, 20 Sep 2019 15:20:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id BCEFC208C3 for ; Fri, 20 Sep 2019 15:20:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2387520AbfITPU0 (ORCPT ); Fri, 20 Sep 2019 11:20:26 -0400 Received: from mail.kernel.org ([198.145.29.99]:37118 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2388766AbfITPU0 (ORCPT ); Fri, 20 Sep 2019 11:20:26 -0400 Received: from gandalf.local.home (cpe-66-24-58-225.stny.res.rr.com [66.24.58.225]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id 76B9B208C0; Fri, 20 Sep 2019 15:20:25 +0000 (UTC) Received: from rostedt by gandalf.local.home with local (Exim 4.92) (envelope-from ) id 1iBKhs-0003p4-MP; Fri, 20 Sep 2019 11:20:24 -0400 Message-Id: <20190920152024.567157833@goodmis.org> User-Agent: quilt/0.65 Date: Fri, 20 Sep 2019 11:15:27 -0400 From: Steven Rostedt To: linux-trace-devel@vger.kernel.org Cc: Yordan Karadzhov Subject: [PATCH 1/2] trace-cmd: Make a global tracecmd_quick_hash() instead of a local knuth_hash() References: <20190920151526.528126066@goodmis.org> MIME-Version: 1.0 Sender: linux-trace-devel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-trace-devel@vger.kernel.org From: "Steven Rostedt (VMware)" As the 32 bit Knuth algorith produces the same results as the small sizes[1], create a single algorithm that takes in a @bits parameter that will return a masked result. And replace the local version of knuth_hash() used by the trace-cmd filter code. This will also be used to remove other copies of knuth_hash(). [1] https://lore.kernel.org/r/20190829114913.5df4ced9@gandalf.local.home Signed-off-by: Steven Rostedt (VMware) --- include/trace-cmd/trace-filter-hash.h | 24 ++++++++++++++++++++++++ lib/trace-cmd/trace-filter-hash.c | 20 +++++--------------- 2 files changed, 29 insertions(+), 15 deletions(-) diff --git a/include/trace-cmd/trace-filter-hash.h b/include/trace-cmd/trace-filter-hash.h index e94bc87d1e1d..4111c41eeb2d 100644 --- a/include/trace-cmd/trace-filter-hash.h +++ b/include/trace-cmd/trace-filter-hash.h @@ -19,6 +19,30 @@ struct tracecmd_filter_id { int count; }; +/** + * tracecmd_quick_hash - A quick (non secured) hash alogirthm + * @val: The value to perform the hash on + * @bits: The size in bits you need to return + * + * This is a quick hashing function adapted from Donald E. Knuth's 32 + * bit multiplicative hash. See The Art of Computer Programming (TAOCP). + * Multiplication by the Prime number, closest to the golden ratio of + * 2^32. + * + * @bits is used to max the result for use cases that require + * a power of 2 return value that is less than 32 bits. Any value + * of @bits greater than 31 (or zero), will simply return the full hash on @val. + */ +static inline uint32_t tracecmd_quick_hash(uint32_t val, unsigned int bits) +{ + val *= UINT32_C(2654435761); + + if (!bits || bits > 31) + return val; + + return val & ((1 << bits) - 1); +} + struct tracecmd_filter_id_item * tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id); void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id); diff --git a/lib/trace-cmd/trace-filter-hash.c b/lib/trace-cmd/trace-filter-hash.c index 45ca68c2959e..f5f0fb09403b 100644 --- a/lib/trace-cmd/trace-filter-hash.c +++ b/lib/trace-cmd/trace-filter-hash.c @@ -12,23 +12,13 @@ #include "trace-filter-hash.h" -#define FILTER_HASH_SIZE 256 - -static inline uint8_t knuth_hash(uint32_t val) -{ - /* - * Small table hashing function adapted from Donald E. Knuth's 32 bit - * multiplicative hash. See The Art of Computer Programming (TAOCP). - * Multiplication by the Prime number, closest to the golden ratio of - * 2^8. - */ - return UINT8_C(val) * UINT8_C(157); -} +#define FILTER_HASH_BITS 8 +#define FILTER_HASH_SIZE (1 << FILTER_HASH_BITS) struct tracecmd_filter_id_item * tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id) { - int key = knuth_hash(id); + int key = tracecmd_quick_hash(id, FILTER_HASH_BITS); struct tracecmd_filter_id_item *item = hash->hash[key]; while (item) { @@ -42,7 +32,7 @@ tracecmd_filter_id_find(struct tracecmd_filter_id *hash, int id) void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id) { - int key = knuth_hash(id); + int key = tracecmd_quick_hash(id, FILTER_HASH_BITS); struct tracecmd_filter_id_item *item; item = calloc(1, sizeof(*item)); @@ -57,7 +47,7 @@ void tracecmd_filter_id_add(struct tracecmd_filter_id *hash, int id) void tracecmd_filter_id_remove(struct tracecmd_filter_id *hash, int id) { - int key = knuth_hash(id); + int key = tracecmd_quick_hash(id, FILTER_HASH_BITS); struct tracecmd_filter_id_item **next = &hash->hash[key]; struct tracecmd_filter_id_item *item; From patchwork Fri Sep 20 15:15:28 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Steven Rostedt X-Patchwork-Id: 11154569 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 0BD9115E6 for ; Fri, 20 Sep 2019 15:20:27 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id DE886208C3 for ; Fri, 20 Sep 2019 15:20:26 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S2388766AbfITPU0 (ORCPT ); Fri, 20 Sep 2019 11:20:26 -0400 Received: from mail.kernel.org ([198.145.29.99]:37124 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S2388863AbfITPU0 (ORCPT ); Fri, 20 Sep 2019 11:20:26 -0400 Received: from gandalf.local.home (cpe-66-24-58-225.stny.res.rr.com [66.24.58.225]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id A264D208C3; Fri, 20 Sep 2019 15:20:25 +0000 (UTC) Received: from rostedt by gandalf.local.home with local (Exim 4.92) (envelope-from ) id 1iBKhs-0003pe-RG; Fri, 20 Sep 2019 11:20:24 -0400 Message-Id: <20190920152024.729716704@goodmis.org> User-Agent: quilt/0.65 Date: Fri, 20 Sep 2019 11:15:28 -0400 From: Steven Rostedt To: linux-trace-devel@vger.kernel.org Cc: Yordan Karadzhov Subject: [PATCH 2/2] kernel-shark: Increase the size of the task hash References: <20190920151526.528126066@goodmis.org> MIME-Version: 1.0 Sender: linux-trace-devel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-trace-devel@vger.kernel.org From: "Steven Rostedt (VMware)" When loading a data file that contained 100,000s of tasks, using a 256 bucket size hash crippled it. By increasing the hash to 2^16 (65536) it solves the issue (still small enough not to waste too much memory). Also switched to the tracecmd_quick_hash() which is basically the same as the local knuth_hash() function in libkshark.c. Link: http://lore.kernel.org/linux-trace-devel/20190828140016.3ce1be4f@gandalf.local.home Signed-off-by: Steven Rostedt (VMware) Reviewed-by: Yordan Karadzhov (VMware) --- kernel-shark/src/libkshark.c | 18 ++++-------------- kernel-shark/src/libkshark.h | 3 ++- 2 files changed, 6 insertions(+), 15 deletions(-) diff --git a/kernel-shark/src/libkshark.c b/kernel-shark/src/libkshark.c index 4207ae6ffdb2..a36157835ce0 100644 --- a/kernel-shark/src/libkshark.c +++ b/kernel-shark/src/libkshark.c @@ -252,19 +252,8 @@ void kshark_free(struct kshark_context *kshark_ctx) free(kshark_ctx); } -static inline uint8_t knuth_hash(uint32_t val) -{ - /* - * Small table hashing function adapted from Donald E. Knuth's 32 bit - * multiplicative hash. See The Art of Computer Programming (TAOCP). - * Multiplication by the Prime number, closest to the golden ratio of - * 2^8. - */ - return UINT8_C(val) * UINT8_C(157); -} - static struct kshark_task_list * -kshark_find_task(struct kshark_context *kshark_ctx, uint8_t key, int pid) +kshark_find_task(struct kshark_context *kshark_ctx, uint32_t key, int pid) { struct kshark_task_list *list; @@ -280,9 +269,10 @@ static struct kshark_task_list * kshark_add_task(struct kshark_context *kshark_ctx, int pid) { struct kshark_task_list *list; - uint8_t key; + uint32_t key; + + key = tracecmd_quick_hash(pid, KS_TASK_HASH_SHIFT); - key = knuth_hash(pid); list = kshark_find_task(kshark_ctx, key, pid); if (list) return list; diff --git a/kernel-shark/src/libkshark.h b/kernel-shark/src/libkshark.h index 04e9cbfc71df..3407db197320 100644 --- a/kernel-shark/src/libkshark.h +++ b/kernel-shark/src/libkshark.h @@ -72,7 +72,8 @@ struct kshark_entry { }; /** Size of the task's hash table. */ -#define KS_TASK_HASH_SIZE 256 +#define KS_TASK_HASH_SHIFT 16 +#define KS_TASK_HASH_SIZE (1 << KS_TASK_HASH_SHIFT) /** Linked list of tasks. */ struct kshark_task_list {