Skip to contentSkip to conversation

kernel-shark-qt: Add generic instruments for searching inside the trace data

RFC New Yordan Karadzhov (VMware) 1 participant 3 messages Jul 5, 2018

lore
Share & tools
lore
#0 lore raw

RFC 1/3 kernel-shark-qt: Add generic instruments for searching inside the trace data

This patch introduces the instrumentation for data extraction, used by the visualization model of the Qt-based KernelShark. The effectiveness of these instruments for searching has a dominant effect over the performance of the model, so let's spend some time and explain this in details.

The first type of instruments provides binary search inside a sorted in time arrays of kshark_entries or trace_records. The search returns the first element of the array, having timestamp bigger than a reference time value. The time complexity of these searches is log(n).

The second type of instruments provides searching for the first (in time) entry, satisfying an abstract Matching condition. Since the array is sorted in time, but we search for an abstract property, for this search the array is considered unsorted, thus we have to iterate and check all elements of the array one by one. If we search for a type of entries, which are well presented in the array, the time complexity of the search is constant, because no matter how big is the array the search only goes through small number of entries at the beginning of the array (or at the end, if we search backwards), before it finds the first match. However if we search for sparse, or even nonexistent entries, the time complexity becomes linear.

These explanations will start making more sense with the following patches.

---
 kernel-shark-qt/src/libkshark.c | 261 +++++++++++++++++++++++++++++++-
 kernel-shark-qt/src/libkshark.h |  76 +++++++++-
 2 files changed, 334 insertions(+), 3 deletions(-)
kernel-shark-qt/src/libkshark.c +260 -1
index 13d7e6d..ebd096a 100644
@@ -761,7 +761,7 @@ static const char *kshark_get_info(struct pevent *pe,
  * @returns The returned string contains a semicolon-separated list of data
  *	    fields.
  */
-char* kshark_dump_entry(struct kshark_entry *entry)
+char* kshark_dump_entry(const struct kshark_entry *entry)
 {
 	const char *event_name, *task, *lat, *info;
 	struct kshark_context *kshark_ctx;
@@ -808,3 +808,262 @@ char* kshark_dump_entry(struct kshark_entry *entry)
 
 	return NULL;
 }
+
+/**
+ * @brief Binary search inside a time-sorted array of kshark_entries.
+ * @param time: The value of time to search for.
+ * @param data_rows: Input location for the trace data.
+ * @param l: Array index specifying the lower edge of the range to search in.
+ * @param h: Array index specifying the upper edge of the range to search in.
+ * @returns On success, the first kshark_entry inside the range, having a
+	    timestamp equal or bigger than "time". In the case when no
+	    kshark_entry has been found inside the range, the function will
+	    return the value of "l" or "h".
+ */
+size_t kshark_find_entry_by_time(uint64_t time,
+				 struct kshark_entry **data_rows,
+				 size_t l, size_t h)
+{
+	size_t mid;
+
+	if (data_rows[l]->ts >= time)
+		return l;
+
+	if (data_rows[h]->ts < time)
+		return h;
+
+	while (h - l > 1) {
+		mid = (l + h) / 2;
+		if (data_rows[mid]->ts < time)
+			l = mid;
+		else
+			h = mid;
+	}
+
+	return h;
+}
+
+/**
+ * @brief Binary search inside a time-sorted array of pevent_records.
+ * @param time: The value of time to search for.
+ * @param data: Input location for the trace data.
+ * @param l: Array index specifying the lower edge of the range to search in.
+ * @param h: Array index specifying the upper edge of the range to search in.
+ * @returns On success, the first pevent_record inside the range, having a
+	    timestamp equal or bigger than "time". In the case when no
+	    pevent_record has been found inside the range, the function will
+	    return the value of "l" or "h".
+ */
+size_t kshark_find_record_by_time(uint64_t time,
+				  struct pevent_record **data,
+				  size_t l, size_t h)
+{
+	size_t mid;
+
+	if (data[l]->ts >= time)
+		return l;
+
+	if (data[h]->ts < time)
+		return h;
+
+	while (h - l > 1) {
+		mid = (l + h) / 2;
+		if (data[mid]->ts < time)
+			l = mid;
+		else
+			h = mid;
+	}
+
+	return h;
+}
+
+/**
+ * @brief Simple Pid matching finction to be user for data requests.
+ * @param kshark_ctx: Input location for the session context pointer.
+ * @param e: kshark_entry to be checked.
+ * @param pid: Matching condition value.
+ * @returns True if the Pid of the entry matches the value of "pid".
+ *	    Else false.
+ */
+bool kshark_check_pid(struct kshark_context *kshark_ctx,
+		      struct kshark_entry *e, int pid)
+{
+	if (e->pid == pid)
+		return true;
+
+	return false;
+}
+
+/**
+ * @brief Simple Cpu matching finction to be user for data requests.
+ * @param kshark_ctx: Input location for the session context pointer.
+ * @param e: kshark_entry to be checked.
+ * @param cpu: Matching condition value.
+ * @returns True if the Cpu of the entry matches the value of "cpu".
+ *	    Else false.
+ */
+bool kshark_check_cpu(struct kshark_context *kshark_ctx,
+		      struct kshark_entry *e, int cpu)
+{
+	if (e->cpu == cpu)
+		return true;
+
+	return false;
+}
+
+/**
+ * @brief Create Data request. The user has to free the returned
+ *	  kshark_entry_request.
+ * @param first: Array index specifying the position inside the array from
+ *		 where the search starts.
+ * @param n: Number of array elements to search in.
+ * @param cond: Matching condition finction.
+ * @param val: Matching condition value, used by the Matching condition
+ *	       finction.
+ * @param vis_only: If true, a visible entry is requested.
+ * @param vis_mask: If "vis_only" is true, use this mask to specify the level
+ *		    of visibility of the requested entry
+ * @returns Pointer to kshark_entry_request on success, or NULL on failure.
+ */
+struct kshark_entry_request *
+kshark_entry_request_alloc(size_t first, size_t n,
+			   matching_condition_func cond, int val,
+			   bool vis_only, int vis_mask)
+{
+	struct kshark_entry_request *req = malloc(sizeof(*req));
+
+	if (!req) {
+		fprintf(stderr,
+			"Failed to allocate memory for entry request.\n");
+		return NULL;
+	}
+
+	req->first = first;
+	req->n = n;
+	req->cond = cond;
+	req->val = val;
+	req->vis_only = vis_only;
+	req->vis_mask = vis_mask;
+
+	return req;
+}
+
+/** Dummy entry, used to indicate the existence of filtered entries. */
+const struct kshark_entry dummy_entry = {/* visible */ 0x00,
+					 /* cpu */ KS_FILTERED_BIN,
+					 /* pid */ KS_FILTERED_BIN,
+					 /* event_id */ -1,
+					 /* offset */ 0,
+					 /* ts */ 0,
+					 /* next */ NULL};
+
+/**
+ * @brief Search for an entry satisfying the requirements of a given Data
+ *	  request. Start from the position provided by the request and go
+ *	  searching in the direction of the increasing timestamps (front).
+ * @param req: Input location for Data request.
+ * @param data: Input location for the trace data.
+ * @param index: Optional output location for the index of the returned
+ *		 entry inside the array.
+ * @returns Pointer to the first entry satisfying the matching condition.
+ *	    In the special case when some entries, satisfying the Matching
+ *	    condition finction have been found, but all these entries have
+ *	    been discarded because of the visibility criteria (filtered
+ *	    entries), the function returns a pointer to a special
+ *	    "Dummy entry".
+ */
+const struct kshark_entry *
+kshark_get_entry_front(const struct kshark_entry_request *req,
+		       struct kshark_entry **data,
+		       ssize_t *index)
+{
+	struct kshark_context *kshark_ctx = NULL;
+	const struct kshark_entry *e = NULL;
+	size_t i, last;
+
+	if (!kshark_instance(&kshark_ctx))
+		return e;
+
+	last = req->first + req->n;
+	for (i = req->first; i < last; ++i) {
+		if (req->cond(kshark_ctx, data[i], req->val)) {
+			/*
+			 * Data satisfying the condition has been found.
+			 */
+			if (req->vis_only &&
+			    !(data[i]->visible & req->vis_mask)) {
+				/* This data entry has been filtered. */
+				e = &dummy_entry;
+			} else {
+				e = data[i];
+				break;
+			}
+		}
+	}
+
+	if (index) {
+		if (e)
+			*index = (e->event_id >= 0)? i : KS_FILTERED_BIN;
+		else
+			*index = KS_EMPTY_BIN;
+	}
+
+	return e;
+}
+
+/**
+ * @brief Search for an entry satisfying the requirements of a given Data
+ *	  request. Start from the position provided by the request and go
+ *	  searching in the direction of the decreasing timestamps (back).
+ * @param req: Input location for Data request.
+ * @param data: Input location for the trace data.
+ * @param index: Optional output location for the index of the returned
+ *		 entry inside the array.
+ * @returns Pointer to the first entry satisfying the matching condition.
+ *	    In the special case when some entries, satisfying the Matching
+ *	    condition finction , have been found, but all these entries have
+ *	    been discarded because of the visibility criteria (filtered
+ *	    entries), the function returns a pointer to a special
+ *	    "Dummy entry".
+ */
+const struct kshark_entry *
+kshark_get_entry_back(const struct kshark_entry_request *req,
+		      struct kshark_entry **data,
+		      ssize_t *index)
+{
+	struct kshark_context *kshark_ctx = NULL;
+	const struct kshark_entry *e = NULL;
+	ssize_t i, last;
+
+	if (!kshark_instance(&kshark_ctx))
+		return e;
+
+	last = req->first - req->n + 1;
+	if (last < 0)
+		last = 0;
+
+	for (i = req->first; i >= last; --i) {
+		if (req->cond(kshark_ctx, data[i], req->val)) {
+			/*
+			 * Data satisfying the condition has been found.
+			 */
+			if (req->vis_only &&
+			    !(data[i]->visible & req->vis_mask)) {
+				/* This data entry has been filtered. */
+				e = &dummy_entry;
+			} else {
+				e = data[i];
+				break;
+			}
+		}
+	}
+
+	if (index) {
+		if (e)
+			*index = (e->event_id >= 0)? i : KS_FILTERED_BIN;
+		else
+			*index = KS_EMPTY_BIN;
+	}
+
+	return e;
+}
kernel-shark-qt/src/libkshark.h +74 -2

94 lines not on this page · raw message

Signature · 1 line
2.17.1
#1 lore raw

RFC 2/3 kernel-shark-qt: Introduce the visualization model used by the Qt-based KS

The model, used by the Qt-based KernelShark for visualization of trace data is build over the concept of "Data Bins". When visualizing a large data-set of trace records, we are limited by the number of screen pixels available for drawing. The model divides the data-set into data-units, also called Bins. The Bin has to be defined in such a way that the entire content of one Bin can be summarized and visualized by a single graphical element. This model uses the timestamp of the trace records, as a criteria for forming Bins. When the Model has to visualize all records inside a given time-window, it divides this time-window into N smaller, uniformly sized subintervals and then defines that one Bin contains all trace records, having timestamps falling into one of this subintervals. Because the model operates over an array of trace records, sorted in time, the content of each Bin can be retrieved by simply knowing the index of the first element inside this Bin and the index of the first element of the next Bin. This means that knowing the index of the first element in each Bin is enough to determine the State of the model.

The State of the model can be modified by its five basic operations: Zoon-In, Zoom-Out, Shift-Forward, Shift-Backward and Jump-To. After each of these operations, the new State of the model is retrieved, by using binary search to find the index of the first element in each Bin. This means that each one of the five basic operations of the model has log(n) time complexity (see previous change log).

In order to keep the visualization of the new state of the model as efficient as possible, the model needs a way to summarize and visualize the content of the Bins in constant time. This is achieved by limiting ourself to only checking the content of the records at the beginning and at the end of the Bin. As explaned in the previous change log, this approach has the very counter-intuitive effect of making the update of the sparse (or empty) Graphs much slower. The problem of the Sparse Graphs will be addressed in another patch, where "Data Collections" will be introduced.

The following patch will introduces a simple example, demonstrating the usage of the API of the Model.

---
 kernel-shark-qt/src/CMakeLists.txt    |    3 +-
 kernel-shark-qt/src/libkshark-model.c | 1131 +++++++++++++++++++++++++
 kernel-shark-qt/src/libkshark-model.h |  138 +++
 3 files changed, 1271 insertions(+), 1 deletion(-)
 create mode 100644 kernel-shark-qt/src/libkshark-model.c
 create mode 100644 kernel-shark-qt/src/libkshark-model.h
kernel-shark-qt/src/CMakeLists.txt +2 -1
index ed3c60e..ec22f63 100644
@@ -1,7 +1,8 @@
 message("\n src ...")
 
 message(STATUS "libkshark")
-add_library(kshark SHARED libkshark.c)
+add_library(kshark SHARED libkshark.c
+                          libkshark-model.c)
 
 target_link_libraries(kshark ${CMAKE_DL_LIBS}
                              ${TRACEEVENT_LIBRARY}
kernel-shark-qt/src/libkshark-model.c new file +1131 -0

1,131 lines not on this page · raw message

kernel-shark-qt/src/libkshark-model.h new file +138 -0

138 lines not on this page · raw message

Signature · 1 line
2.17.1
#2 lore raw

RFC 3/3 kernel-shark-qt: Add an example showing how to manipulate the Vis. model.

In reply to Yordan Karadzhov (VMware)

This patch introduces a basic example, showing how to initialize the Visualization model and to use the API to perform some of the basic operations.

---
 kernel-shark-qt/examples/CMakeLists.txt |   4 +
 kernel-shark-qt/examples/datahisto.c    | 155 ++++++++++++++++++++++++
 2 files changed, 159 insertions(+)
 create mode 100644 kernel-shark-qt/examples/datahisto.c
kernel-shark-qt/examples/CMakeLists.txt +4 -0
index 009fd1e..6906eba 100644
@@ -7,3 +7,7 @@ target_link_libraries(dload   kshark)
 message(STATUS "datafilter")
 add_executable(dfilter          datafilter.c)
 target_link_libraries(dfilter   kshark)
+
+message(STATUS "datahisto")
+add_executable(dhisto          datahisto.c)
+target_link_libraries(dhisto   kshark)
kernel-shark-qt/examples/datahisto.c new file +155 -0

155 lines not on this page · raw message

Signature · 1 line
2.17.1