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 v8 11/44] kernel-shark: Introduce libkshark-hash
Date: Mon, 4 Jan 2021 19:46:51 +0200 [thread overview]
Message-ID: <20210104174724.70404-12-y.karadz@gmail.com> (raw)
In-Reply-To: <20210104174724.70404-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 ecd448c..e1a4b5f 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -4,6 +4,7 @@ set(KS_INCLUDS_DESTINATION "${_INSTALL_PREFIX}/include/${KS_APP_NAME}")
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 0000000..89c021b
--- /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 f279d16..e34a32f 100644
--- a/src/libkshark.h
+++ b/src/libkshark.h
@@ -75,6 +75,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
next prev parent reply other threads:[~2021-01-04 17:49 UTC|newest]
Thread overview: 46+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-01-04 17:46 [PATCH v8 00/44] Start KernelShark v2 transformation Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 01/44] kernel-shark: Adopt trace-cmd API changes Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 02/44] kernel-shark: Use libtraceevent and libtracefs Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 03/44] kernel-shark: Add license information Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 04/44] kernel-shark: Change the CMake minimum version required Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 05/44] kernel-shark: Change default libraries install location Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 06/44] kernel-shark: Split the installation in two components Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 07/44] kernel-shark: Update README Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 08/44] kernel-shark: Define build target for JSONC Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 09/44] kernel-shark: Use only signed types in kshark_entry Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 10/44] kernel-shark: Add stream_id to kshark_entry Yordan Karadzhov (VMware)
2021-01-04 17:46 ` Yordan Karadzhov (VMware) [this message]
2021-01-04 17:46 ` [PATCH v8 12/44] kernel-shark: Introduce Data streams Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 13/44] kernel-shark: Rename static methods in libkshark Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 14/44] kernel-shark: Add basic methods for Data streams Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 15/44] kernel-shark: Housekeeping before implementing stream interface Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 16/44] kernel-shark: Add stream interface for trace-cmd data Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 17/44] kernel-shark: Start introducing KernelShark 2.0 Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 18/44] kernel-shark: Start using data streams Yordan Karadzhov (VMware)
2021-01-04 17:46 ` [PATCH v8 19/44] kernel-shark: Remove dead code Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 20/44] kernel-shark: Redesign the plugin interface Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 21/44] kernel-shark: Complete the stream integration Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 22/44] kernel-shark: Provide merging of multiple data streams Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 23/44] kernel-shark: Integrate the stream definitions with data model Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 24/44] kernel-shark: Use only signed types for model defs Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 25/44] kernel-shark: Add ksmodel_get_bin() Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 26/44] kernel-shark: Protect ksmodel_set_in_range_bining() Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 27/44] kernel-shark: Add methods for time calibration Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 28/44] kernel-shark: Integrate streams with libkshark-configio Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 29/44] kernel-shark: Add support for drawing text Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 30/44] kernel-shark: Make GLUT optional dependency Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 31/44] kernel-shark: Add ksplot_draw_polyline() Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 32/44] kernel-shark: Optimize ksplot_draw_polygon() Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 33/44] kernel-shark: Add basic infrastructure for testing Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 34/44] kernel-shark: Add "github Actions" workflow Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 35/44] kernel-shark: Integrate streams with KsPlotTools Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 36/44] kernel-shark: Add getStreamColorTable() Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 37/44] kernel-shark: Redefine the args of KsPlot::getColor() Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 38/44] kernel-shark: Add TextBox class to KsPlot namespace Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 39/44] kernel-shark: Consistent method naming in KsPlotTools Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 40/44] kernel-shark: Make the label part of the graph Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 41/44] kernel-shark: Remove the hard-coded Idle PID Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 42/44] kernel-shark: Add class Polyline to KsPlot namespace Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 43/44] kernel-shark: Add VirtBridge and VirtGap classes Yordan Karadzhov (VMware)
2021-01-04 17:47 ` [PATCH v8 44/44] kernel-shark: Add double click interface to PlotObject Yordan Karadzhov (VMware)
2021-01-05 0:27 ` [PATCH v8 00/44] Start KernelShark v2 transformation 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=20210104174724.70404-12-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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).