Linux-Trace-Devel Archive on lore.kernel.org
 help / color / Atom feed
From: "Yordan Karadzhov (VMware)" <y.karadz@gmail.com>
To: rostedt@goodmis.org
Cc: linux-trace-devel@vger.kernel.org,
	"Yordan Karadzhov (VMware)" <y.karadz@gmail.com>
Subject: [PATCH v2 03/20] kernel-shark: Introduce libkshark-hash
Date: Mon, 12 Oct 2020 16:35:06 +0300
Message-ID: <20201012133523.469040-4-y.karadz@gmail.com> (raw)
In-Reply-To: <20201012133523.469040-1-y.karadz@gmail.com>

So far KernelShark have been using an implementation of a hash table
from trace-cmd/include/trace-cmd/trace-filter-hash.h. However it turns
that KernelShark is the only user of trace-filter-hash, which means
that it make more sense to make this implementation of the hash table
part of KernelShark. In this patch we adapt the original trace-cmd
implementation and change the naming convention used.

Signed-off-by: Yordan Karadzhov (VMware) <y.karadz@gmail.com>
---
 src/CMakeLists.txt   |   1 +
 src/libkshark-hash.c | 239 +++++++++++++++++++++++++++++++++++++++++++
 src/libkshark.h      |  46 +++++++++
 3 files changed, 286 insertions(+)
 create mode 100644 src/libkshark-hash.c

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index 2e092b2e..39c4dcf0 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -2,6 +2,7 @@ message("\n src ...")
 
 message(STATUS "libkshark")
 add_library(kshark SHARED libkshark.c
+                          libkshark-hash.c
 #                           libkshark-model.c
                           libkshark-plugin.c
 #                           libkshark-configio.c
diff --git a/src/libkshark-hash.c b/src/libkshark-hash.c
new file mode 100644
index 00000000..89c021ba
--- /dev/null
+++ b/src/libkshark-hash.c
@@ -0,0 +1,239 @@
+// SPDX-License-Identifier: LGPL-2.1
+
+/*
+ * Copyright (C) 2009, Steven Rostedt <srostedt@redhat.com>
+ * Copyright (C) 2018 VMware Inc, Steven Rostedt <rostedt@goodmis.org>
+ */
+
+/**
+ *  @file    libkshark-hash.c
+ *  @brief   Hash table of integer Id numbers.
+ */
+
+// C
+#include <stdio.h>
+#include <stdlib.h>
+#include <assert.h>
+
+// KernelShark
+#include "libkshark.h"
+
+/**
+ * @brief: quick_hash - A quick (non secured) hash alogirthm
+ * @param val: The value to perform the hash on
+ * @param 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 quick_hash(uint32_t val, unsigned int bits)
+{
+	val *= UINT32_C(2654435761);
+
+	if (!bits || bits > 31)
+		return val;
+
+	return val & ((1 << bits) - 1);
+}
+
+static size_t hash_size(struct kshark_hash_id *hash)
+{
+	return (1 << hash->n_bits);
+}
+
+/**
+ * Create new hash table of Ids.
+ */
+struct kshark_hash_id *kshark_hash_id_alloc(size_t n_bits)
+{
+	struct kshark_hash_id *hash;
+	size_t size;
+
+	hash = calloc(1, sizeof(*hash));
+	if (!hash)
+		goto fail;
+
+	hash->n_bits = n_bits;
+	hash->count = 0;
+
+	size = hash_size(hash);
+	hash->hash = calloc(size, sizeof(*hash->hash));
+	if (!hash->hash)
+		goto fail;
+
+	return hash;
+
+ fail:
+	fprintf(stderr, "Failed to allocate memory for hash table.\n");
+	kshark_hash_id_free(hash);
+	return NULL;
+}
+
+/** Free the hash table of Ids. */
+void kshark_hash_id_free(struct kshark_hash_id *hash)
+{
+	if (!hash)
+		return;
+
+	if (hash->hash) {
+		kshark_hash_id_clear(hash);
+		free(hash->hash);
+	}
+
+	free(hash);
+}
+
+/**
+ * @brief Check if an Id with a given value exists in this hash table.
+ */
+bool kshark_hash_id_find(struct kshark_hash_id *hash, int id)
+{
+	uint32_t key = quick_hash(id, hash->n_bits);
+	struct kshark_hash_id_item *item;
+
+	for (item = hash->hash[key]; item; item = item->next)
+		if (item->id == id)
+			break;
+
+	return !!(unsigned long) item;
+}
+
+/**
+ * @brief Add Id to the hash table.
+ *
+ * @param hash: The hash table to add to.
+ * @param id: The Id number to be added.
+ *
+ * @returns Zero if the Id already exists in the table, one if the Id has been
+ *	    added and negative errno code on failure.
+ */
+int kshark_hash_id_add(struct kshark_hash_id *hash, int id)
+{
+	uint32_t key = quick_hash(id, hash->n_bits);
+	struct kshark_hash_id_item *item;
+
+	if (kshark_hash_id_find(hash, id))
+		return 0;
+
+	item = calloc(1, sizeof(*item));
+	if (!item) {
+		fprintf(stderr,
+			"Failed to allocate memory for hash table item.\n");
+		return -ENOMEM;
+	}
+
+	item->id = id;
+	item->next = hash->hash[key];
+	hash->hash[key] = item;
+	hash->count++;
+
+	return 1;
+}
+
+/**
+ * @brief Remove Id from the hash table.
+ */
+void kshark_hash_id_remove(struct kshark_hash_id *hash, int id)
+{
+	struct kshark_hash_id_item *item, **next;
+	int key = quick_hash(id, hash->n_bits);
+
+	next = &hash->hash[key];
+	while (*next) {
+		if ((*next)->id == id)
+			break;
+		next = &(*next)->next;
+	}
+
+	if (!*next)
+		return;
+
+	assert(hash->count);
+
+	hash->count--;
+	item = *next;
+	*next = item->next;
+
+	free(item);
+}
+
+/** Remove (free) all Ids (items) from this hash table. */
+void kshark_hash_id_clear(struct kshark_hash_id *hash)
+{
+	struct kshark_hash_id_item *item, *next;
+	size_t size;
+	int i;
+
+	if (!hash || ! hash->hash)
+		return;
+
+	size = hash_size(hash);
+	for (i = 0; i < size; i++) {
+		next = hash->hash[i];
+		if (!next)
+			continue;
+
+		hash->hash[i] = NULL;
+		while (next) {
+			item = next;
+			next = item->next;
+			free(item);
+		}
+	}
+
+	hash->count = 0;
+}
+
+static int compare_ids(const void* a, const void* b)
+{
+	int arg1 = *(const int*)a;
+	int arg2 = *(const int*)b;
+
+	if (arg1 < arg2)
+		return -1;
+
+	if (arg1 > arg2)
+		return 1;
+
+	return 0;
+}
+
+/**
+ * @brief Get a sorted array containing all Ids of this hash table.
+ */
+int *kshark_hash_ids(struct kshark_hash_id *hash)
+{
+	struct kshark_hash_id_item *item;
+	size_t size = hash_size(hash);
+	int count = 0, i;
+	int *ids;
+
+	if (!hash->count)
+		return NULL;
+
+	ids = calloc(hash->count, sizeof(*ids));
+	if (!ids) {
+		fprintf(stderr,
+			"Failed to allocate memory for Id array.\n");
+		return NULL;
+	}
+
+	for (i = 0; i < size; i++) {
+		item = hash->hash[i];
+		while (item) {
+			ids[count++] = item->id;
+			item = item->next;
+		}
+	}
+
+	qsort(ids, hash->count, sizeof(*ids), compare_ids);
+
+	return ids;
+}
diff --git a/src/libkshark.h b/src/libkshark.h
index 9eecc2d0..0182cf6d 100644
--- a/src/libkshark.h
+++ b/src/libkshark.h
@@ -72,6 +72,52 @@ struct kshark_entry {
 	int64_t		ts;
 };
 
+/** Size of the hash table of PIDs in terms of bits being used by the key. */
+#define KS_TASK_HASH_NBITS	16
+
+/** Size of the hash table of Ids in terms of bits being used by the key. */
+#define KS_FILTER_HASH_NBITS	8
+
+/** A bucket for the hash table of integer Id numbers (kshark_hash_id). */
+struct kshark_hash_id_item {
+	/** Pointer to the Id in this bucket. */
+	struct kshark_hash_id_item	*next;
+
+	/** The Id value. */
+	int				id;
+};
+
+/**
+ * Hash table of integer Id numbers. To be used for fast filter of trace
+ * entries.
+ */
+struct kshark_hash_id {
+	/** Array of buckets. */
+	struct kshark_hash_id_item	**hash;
+
+	/** The number of Ids in the table. */
+	size_t	count;
+
+	/**
+	 * The number of bits used by the hashing function.
+	 * Note that the number of buckets in the table if given by
+	 * 1 << n_bits.
+	 */
+	size_t	n_bits;
+};
+
+bool kshark_hash_id_find(struct kshark_hash_id *hash, int id);
+
+int kshark_hash_id_add(struct kshark_hash_id *hash, int id);
+
+void kshark_hash_id_clear(struct kshark_hash_id *hash);
+
+struct kshark_hash_id *kshark_hash_id_alloc(size_t n_bits);
+
+void kshark_hash_id_free(struct kshark_hash_id *hash);
+
+int *kshark_hash_ids(struct kshark_hash_id *hash);
+
 /** Size of the task's hash table. */
 #define KS_TASK_HASH_SHIFT 16
 #define KS_TASK_HASH_SIZE (1 << KS_TASK_HASH_SHIFT)
-- 
2.25.1


  parent reply index

Thread overview: 47+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-10-12 13:35 [PATCH v2 00/20] Start KernelShark v2 transformation Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 01/20] kernel-shark: Start introducing KernelShark 2.0 Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 02/20] kernel-shark: Use only signed types in kshark_entry Yordan Karadzhov (VMware)
2020-10-12 13:35 ` Yordan Karadzhov (VMware) [this message]
2020-10-12 14:05   ` [PATCH v2 03/20] kernel-shark: Introduce libkshark-hash Steven Rostedt
2020-10-12 14:05     ` Steven Rostedt
2020-10-12 14:18       ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 04/20] kernel-shark: Introduce Data streams Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 05/20] kernel-shark: Add stream_id to kshark_entry Yordan Karadzhov (VMware)
2020-10-13  0:05   ` Steven Rostedt
2020-10-29 10:08     ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 06/20] kernel-shark: Rename static methods in libkshark Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 07/20] kernel-shark: Add basic methods for Data streams Yordan Karadzhov (VMware)
2020-10-13  0:18   ` Steven Rostedt
2020-10-29 10:10     ` Yordan Karadzhov (VMware)
2020-10-29 14:04       ` Steven Rostedt
2020-10-29 14:49         ` Yordan Karadzhov (VMware)
2020-10-30  1:57           ` Steven Rostedt
2020-11-03 13:38             ` Yordan Karadzhov (VMware)
2020-11-04 15:41               ` Steven Rostedt
2020-11-05 14:35                 ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 08/20] kernel-shark: Housekeeping before implementing stream interface Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 09/20] kernel-shark: Add stream interface for trace-cmd data Yordan Karadzhov (VMware)
2020-10-13  0:44   ` Steven Rostedt
2020-10-29 11:16     ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 10/20] kernel-shark: Start using data streams Yordan Karadzhov (VMware)
2020-10-14 18:56   ` Steven Rostedt
2020-11-05 14:58     ` Yordan Karadzhov (VMware)
2020-11-05 18:17       ` Steven Rostedt
2020-11-06 14:31         ` Yordan Karadzhov (VMware)
2020-11-06 15:18           ` Steven Rostedt
2020-11-09 14:49             ` Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 11/20] kernel-shark: Remove dead code Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 12/20] kernel-shark: Redesign the plugin interface Yordan Karadzhov (VMware)
2020-10-14 21:09   ` Steven Rostedt
2020-10-12 13:35 ` [PATCH v2 13/20] kernel-shark: Complete the stream integration Yordan Karadzhov (VMware)
2020-10-14 23:52   ` Steven Rostedt
2020-10-12 13:35 ` [PATCH v2 14/20] kernel-shark: Provide merging of multiple data streams Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 15/20] kernel-shark: Integrate the stream definitions with data model Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 16/20] kernel-shark: Use only signed types for model defs Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 17/20] kernel-shark: Add ksmodel_get_bin() Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 18/20] kernel-shark: Protect ksmodel_set_in_range_bining() Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 19/20] kernel-shark: Add methods for time calibration Yordan Karadzhov (VMware)
2020-10-12 13:35 ` [PATCH v2 20/20] kernel-shark: Integrate streams with libkshark-configio Yordan Karadzhov (VMware)
2020-11-05 19:22   ` Steven Rostedt
2020-11-09 14:55     ` Yordan Karadzhov (VMware)
2020-11-09 15:28       ` Steven Rostedt

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20201012133523.469040-4-y.karadz@gmail.com \
    --to=y.karadz@gmail.com \
    --cc=linux-trace-devel@vger.kernel.org \
    --cc=rostedt@goodmis.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Linux-Trace-Devel Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/linux-trace-devel/0 linux-trace-devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 linux-trace-devel linux-trace-devel/ https://lore.kernel.org/linux-trace-devel \
		linux-trace-devel@vger.kernel.org
	public-inbox-index linux-trace-devel

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-trace-devel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git