Add visualization model for the Qt-based KernelShark
v3 cover Add visualization model for the Qt-based KernelShark
This series of patches introduces the second part of the C API used by the Qt-based version of KernelShark. This part of the API is responsible for the visual navigation and browsing inside the trace data.
This is the third version of this series of patches. Major changes from v2 are:
[old 1/7] The "Changes type of the fields" is now a separate patch and isn't part of this series.
[1/7] As suggested by Steven Rostedt, the binary search functions are modified in order to avoid the ambiguity of the returned value in the case when no kshark_entry has been found inside the range.
[2/7] The change above affects the logic in ksmodel_set_lower_edge(), ksmodel_set_upper_edge() and ksmodel_set_next_bin_edge().
[4/7] General revision (debugging and simplification) of the logic, responsible for mapping the primary data request into a list of collection-compatible data requests.
Yordan Karadzhov (VMware) (6):
kernel-shark-qt: Add generic instruments for searching inside the
trace data
kernel-shark-qt: Introduce the visualization model used by the
Qt-based KS
kernel-shark-qt: Add an example showing how to manipulate the Vis.
model.
kernel-shark-qt: Define Data collections
kernel-shark-qt: Make the Vis. model use Data collections.
kernel-shark-qt: Changed the KernelShark version identifier.
kernel-shark-qt/CMakeLists.txt | 2 +- kernel-shark-qt/examples/CMakeLists.txt | 4 + kernel-shark-qt/examples/datahisto.c | 159 +++ kernel-shark-qt/src/CMakeLists.txt | 4 +- kernel-shark-qt/src/libkshark-collection.c | 805 +++++++++++++ kernel-shark-qt/src/libkshark-model.c | 1223 ++++++++++++++++++++ kernel-shark-qt/src/libkshark-model.h | 159 +++ kernel-shark-qt/src/libkshark.c | 278 +++++ kernel-shark-qt/src/libkshark.h | 172 +++ 9 files changed, 2804 insertions(+), 2 deletions(-) create mode 100644 kernel-shark-qt/examples/datahisto.c create mode 100644 kernel-shark-qt/src/libkshark-collection.c create mode 100644 kernel-shark-qt/src/libkshark-model.c create mode 100644 kernel-shark-qt/src/libkshark-model.h
Signature · 1 line
2.17.1
PATCH v3 1/6 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 detail.
The first type of instruments provide 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 provide 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 | 262 ++++++++++++++++++++++++++++++++ kernel-shark-qt/src/libkshark.h | 93 ++++++++++++ 2 files changed, 355 insertions(+)
kernel-shark-qt/src/libkshark.c +262 -0
@@ -925,3 +925,265 @@ char* kshark_dump_entry(const 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: 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". +If all entries inside the range have timestamps greater than "time" +the function returns BSEARCH_ALL_GREATER (negative value). +If all entries inside the range have timestamps smaller than "time" +the function returns BSEARCH_ALL_SMALLER (negative value). +*/ +ssize_t kshark_find_entry_by_time (uint64_t time, +struct kshark_entry **data, +size_t l,size_t h) +{ +size_t mid; + +if (data[l]->ts > time) +return BSEARCH_ALL_GREATER ; + +if (data[h]->ts < time) +return BSEARCH_ALL_SMALLER ; + +/* +* After executing the BSEARCH macro, "l" will be the index of the last +* entry having timestamp < time and "h" will be the index of the first +* entry having timestamp >= time. +*/ +BSEARCH (h, l, data[mid]->ts < time); +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". +If all entries inside the range have timestamps greater than "time" +the function returns BSEARCH_ALL_GREATER (negative value). +If all entries inside the range have timestamps smaller than "time" +the function returns BSEARCH_ALL_SMALLER (negative value). +*/ +ssize_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 BSEARCH_ALL_GREATER ; + +if (data[h]->ts < time) +return BSEARCH_ALL_SMALLER ; + +/* +* After executing the BSEARCH macro, "l" will be the index of the last +* record having timestamp < time and "h" will be the index of the +* first record having timestamp >= time. +*/ +BSEARCH (h, l, data[mid]->ts < time); +return h; +} + +/** +* @brief Simple Pid matching function 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_match_pid (struct kshark_context *kshark_ctx, +struct kshark_entry *e,int pid) +{ +if (e->pid == pid) +return true; + +return false; +} + +/** +* @brief Simple Cpu matching function 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_match_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 request defines the properties of the +* requested kshark_entry. +* +* @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 function. +* @param val: Matching condition value, used by the Matching condition +* function. +* @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. +* The user is responsible for freeing the returned +* kshark_entry_request. +*/ +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 = { + .next =NULL , + .visible =0x00 , + .cpu =KS_FILTERED_BIN , + .pid =KS_FILTERED_BIN , + .event_id =-1 , + .offset =0 , + .ts =0 +}; + +static const struct kshark_entry * +get_entry (const struct kshark_entry_request *req, +struct kshark_entry **data, +ssize_t *index,size_t start,ssize_t end,int inc) +{ +struct kshark_context *kshark_ctx =NULL ; +const struct kshark_entry *e =NULL ; +ssize_t i; + +if (index) + *index =KS_EMPTY_BIN ; + +if (!kshark_instance (&kshark_ctx)) +return e; + +for (i = start; i != end; i += inc) { +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 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 conditionon +* success, or NULL on failure. +* In the special case when some entries, satisfying the Matching +* condition function 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) +{ +ssize_t end = req->first + req->n; + +return get_entry (req, data, index, req->first, end,+1 ); +} + +/** +* @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 conditionon +* success, or NULL on failure. +* In the special case when some entries, satisfying the Matching +* condition function 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) +{ +ssize_t end = req->first - req->n; + +if (end <0 ) + end =-1 ; + +return get_entry (req, data, index, req->first, end,-1 ); +}
kernel-shark-qt/src/libkshark.h +93 -0
99 lines not on this page · raw message
Signature · 1 line
2.17.1
PATCH v3 2/6 kernel-shark-qt: Introduce the visualization model used by the Qt-based KS
In reply to Yordan Karadzhov (VMware)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.
--- kernel-shark-qt/src/CMakeLists.txt | 3 +- kernel-shark-qt/src/libkshark-model.c | 1182 +++++++++++++++++++++++++ kernel-shark-qt/src/libkshark-model.h | 149 ++++ 3 files changed, 1333 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
@@ -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 +1182 -0
1,182 lines not on this page · raw message
kernel-shark-qt/src/libkshark-model.h new file +149 -0
149 lines not on this page · raw message
Signature · 1 line
2.17.1
Re: [PATCH v3 2/6] kernel-shark-qt: Introduce the visualization model used by the Qt-based KS
On Fri, 3 Aug 2018 17:29:33 +0300
"Yordan Karadzhov (VMware)" <[email protected]> wrote:
FYI, git warned me about bad whitespace in this patch:
.git/rebase-apply/patch:357: trailing whitespace.
.git/rebase-apply/patch:467: trailing whitespace.
.git/rebase-apply/patch:875: trailing whitespace.
And doing a git show I find:
Quoted 55 lines
Signed-off-by Yordan Karadzhov (VMware) <[email protected]>--- kernel-shark-qt/src/CMakeLists.txt | 3 +- kernel-shark-qt/src/libkshark-model.c | 1182 +++++++++++++++++++++++++ kernel-shark-qt/src/libkshark-model.h | 149 ++++ 3 files changed, 1333 insertions(+), 1 deletion(-) create mode 100644 kernel-shark-qt/src/libkshark-model.c create mode 100644 kernel-shark-qt/src/libkshark-model.hkernel-shark-qt/src/CMakeLists.txt +2
-1@@ -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 +25
-0+static void ksmodel_set_bin_counts (struct kshark_trace_histo *histo) +{ +int i =0 , prev_not_empty; + +memset (&histo->bin_count[0 ],0 , + (histo->n_bins) *sizeof (histo->bin_count[0 ])); +/* +* Find the first bin which contains data. Start by checking the +* Lower Overflow bin. +*/ +if (histo->map[LOB (histo)] !=KS_EMPTY_BIN ) { + prev_not_empty =LOB (histo); + }else { +/* Loop till the first non-empty bin. */ +while (histo->map[i] <0 ) { + ++i; + } + + prev_not_empty = i++; + } + +/* +* Starting from the first not empty bin, loop over all bins and fill +* in the bin_count array to hold the number of entries in each bin. +*/
kernel-shark-qt/src/libkshark-model.c line 329
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+for (; i < histo->n_bins; ++i) { +if (histo->map[i] !=KS_EMPTY_BIN ) { +/* The current bin is not empty, take its data row and +* subtract it from the data row of the previous not +* empty bin, which will give us the number of data +* rows in the "prev_not_empty" bin. +*/ + histo->bin_count[prev_not_empty] = + histo->map[i] - histo->map[prev_not_empty]; +
The above line has a superfluous tab.
Quoted 28 lines
kernel-shark-qt/src/libkshark-model.c new file +25
-0+ prev_not_empty = i; + } + } + +/* Check if the Upper Overflow bin contains data. */ +if (histo->map[UOB (histo)] ==KS_EMPTY_BIN ) { +/* +* The Upper Overflow bin is empty. Use the size of the +* dataset to calculate the content of the previouse not +* empty bin. +*/ + histo->bin_count[prev_not_empty] = histo->data_size - + histo->map[prev_not_empty]; + }else { +/* +* Use the index of the first entry inside the Upper Overflow +* bin to calculate the content of the previouse not empty +* bin. +*/ + histo->bin_count[prev_not_empty] = histo->map[UOB (histo)] - + histo->map[prev_not_empty]; + } +} +/** +* @brief Shift the time-window of the model forward. Recalculate the current
kernel-shark-qt/src/libkshark-model.c line 367
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+* state of the model. +* +* @param histo: Input location for the model descriptor. +* @param n: Number of bins to shift. +*/ +void ksmodel_shift_forward (struct kshark_trace_histo *histo,size_t n) +{ +size_t last_row =0 ; +int bin; +
Here too.
Quoted 24 lines
kernel-shark-qt/src/libkshark-model.c new file +21
-0+if (!histo->data_size) +return ; + +if (histo->map[UOB (histo)] ==KS_EMPTY_BIN ) { +/* +* The Upper Overflow bin is empty. This means that we are at +* the upper edge of the dataset already. Do nothing in this +* case. +*/ +return ; + } +/** +* @brief Get the index of the first entry from a given Task in a given bin. +* +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @param pid: Process Id of a task. +* +* @returns Index of the first entry from a given Task in this bin. +*/ +ssize_t ksmodel_first_index_at_pid(struct kshark_trace_histo *histo,
kernel-shark-qt/src/libkshark-model.c line 847
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ int bin, int pid) +{ + size_t i, n, first, not_found = KS_EMPTY_BIN; + + n =ksmodel_bin_count (histo, bin); +if (!n) +return not_found; + + first =ksmodel_first_index_at_bin (histo, bin); +
Here too.
Don't worry about fixing these unless you need to resend. I'll just fix them in my repo.
-- Steve
Quoted 12 lines
kernel-shark-qt/src/libkshark-model.c new file +12
-0+for (i = first; i < first + n; ++i) { +if (histo->data[i]->pid == pid) { +if (ksmodel_is_visible (histo->data[i])) +return i; +else + not_found =KS_FILTERED_BIN ; + } + } + +return not_found; +} +
Re: [PATCH v3 2/6] kernel-shark-qt: Introduce the visualization model used by the Qt-based KS
In reply to Yordan Karadzhov (VMware)Quoted 28 lines · On Fri, 3 Aug 2018 17:29:33 +0300 "Yordan Karadzhov (VMware)"…
kernel-shark-qt/src/libkshark-model.h new file +25
-0@@ -0,0 +1,149 @@ +/* SPDX-License-Identifier: LGPL-2.1 */ + +/* +* Copyright (C) 2017 VMware Inc, Yordan Karadzhov <[email protected]> +*/ + +/** +* @file libkshark-model.h +* @brief Visualization model for FTRACE (trace-cmd) data. +*/ + +#ifndef _LIB_KSHARK_MODEL_H +#define _LIB_KSHARK_MODEL_H + +// KernelShark +#include "libkshark.h" + +#ifdef __cplusplus +extern "C" { +#endif // __cplusplus + +/** + * Overflow Bin identifiers. The two overflow bins are used to hold the data + * outside the visualized range. + */
kernel-shark-qt/src/libkshark-model.h line 35
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.h new file +10
-0+enum OverflowBin { +/** +* Identifier of the Upper Overflow Bin. This bin is used to hold the data +* before (in time) the beginning of the visualized range. +*/ +UPPER_OVERFLOW_BIN =-1 , + +/** Identifier of the Lower Overflow Bin. This bin is used to hold the data +* after (in time) the end of the visualized range.*/ +LOWER_OVERFLOW_BIN =-2 ,
Wait, I thought the upper overflow bin was to store the data after the visualized range and the lower overnflow bin the time before?
Quoted 9 lines
kernel-shark-qt/src/libkshark-model.h new file +7
-0+}; + +/** Structure describing the current state of the visualization model. */ +static size_t ksmodel_set_lower_edge (struct kshark_trace_histo *histo) +{ +/* +* Find the index of the first entry inside
kernel-shark-qt/src/libkshark-model.h
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.h new file +10
-0+* the range (timestamp > min). +*/ +ssize_t row =kshark_find_entry_by_time (histo->min, + histo->data, +0 , + histo->data_size -1 ); + +assert (row !=BSEARCH_ALL_SMALLER ); + +if (row ==BSEARCH_ALL_GREATER || row ==0 ) {
LOB(hist) is set by the lower row (which is less in time isn't it?)
Quoted 44 lines
kernel-shark-qt/src/libkshark-model.h new file +44
-0+/* Lower Overflow bin is empty. */ + histo->map[LOB (histo)] =KS_EMPTY_BIN ; + histo->bin_count[LOB (histo)] =0 ; + row =0 ; + }else { +/* +* The first entry inside the range is not the first entry +* of the dataset. This means that the Lower Overflow bin +* contains data. +*/ + +/* Lower Overflow bin starts at "0". */ + histo->map[LOB (histo)] =0 ; + +/* +* The number of entries inside the Lower Overflow bin is +* equal to the index of the first entry inside the range. +*/ + histo->bin_count[LOB (histo)] = row; + } + +/* +* Now check if the first entry inside the range falls into the +* first bin. +*/ +if (histo->data[row]->ts < histo->min + histo->bin_size) { +/* +* It is inside the first bin. Set the beginning +* of the first bin. +*/ + histo->map[0 ] = row; + }else { +/* The first bin is empty. */ + histo->map[0 ] =KS_EMPTY_BIN ; + } + +return row; +} + +static size_t ksmodel_set_upper_edge (struct kshark_trace_histo *histo) +{ +/* +* Find the index of the first entry outside the range +* (timestamp > max). Remember that kshark_find_entry_by_time returns
kernel-shark-qt/src/libkshark-model.h
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.h new file +10
-0+* the first entry which is equal or greater than the reference time. +*/ +ssize_t row =kshark_find_entry_by_time (histo->max +1 , + histo->data, +0 , + histo->data_size -1 ); + +assert (row !=BSEARCH_ALL_GREATER ); + +if (row ==BSEARCH_ALL_SMALLER || row == histo->data_size -1 ) {
UOB(histo) is set by the highest row. Right?
-- Steve
Quoted 15 lines
kernel-shark-qt/src/libkshark-model.h new file +15
-0+/* Upper Overflow bin is empty. */ + histo->map[UOB (histo)] =KS_EMPTY_BIN ; + histo->bin_count[UOB (histo)] =0 ; + }else { +/* +* The Upper Overflow bin contains data. Set its beginning +* and the number of entries. +*/ + histo->map[UOB (histo)] = row; + histo->bin_count[UOB (histo)] = histo->data_size - row; + } + +return row; +} +
Re: [PATCH v3 2/6] kernel-shark-qt: Introduce the visualization model used by the Qt-based KS
Quoted 36 lines · Steven Rostedt
Quoted 33 lines · On Fri, 3 Aug 2018 17:29:33 +0300 "Yordan Karadzhov (VMware)"…
kernel-shark-qt/src/libkshark-model.h new file +30
-0@@ -0,0 +1,149 @@ +/* SPDX-License-Identifier: LGPL-2.1 */ + +/* +* Copyright (C) 2017 VMware Inc, Yordan Karadzhov <[email protected]> +*/ + +/** +* @file libkshark-model.h +* @brief Visualization model for FTRACE (trace-cmd) data. +*/ + +#ifndef _LIB_KSHARK_MODEL_H +#define _LIB_KSHARK_MODEL_H + +// KernelShark +#include "libkshark.h" + +#ifdef __cplusplus +extern "C" { +#endif // __cplusplus + +/** + * Overflow Bin identifiers. The two overflow bins are used to hold the data + * outside the visualized range. + */ +enum OverflowBin { + /** + * Identifier of the Upper Overflow Bin. This bin is used to hold the data + * before (in time) the beginning of the visualized range. + */
Quoted 9 lines
kernel-shark-qt/src/libkshark-model.h line 35
Quoted 5 lines
kernel-shark-qt/src/libkshark-model.h new file +5
-0+UPPER_OVERFLOW_BIN =-1 , + +/** Identifier of the Lower Overflow Bin. This bin is used to hold the data +* after (in time) the end of the visualized range.*/ + LOWER_OVERFLOW_BIN = -2,Wait, I thought the upper overflow bin was to store the data after the visualized range and the lower overnflow bin the time before?
Correct, I have to swap the tow descriptions.
Quoted 6 lines
Quoted 4 lines
kernel-shark-qt/src/libkshark-model.h new file +3
-0+}; + +/** Structure describing the current state of the visualization model. */
Quoted 6 lines
kernel-shark-qt/src/libkshark-model.h line 44
Quoted 6 lines
kernel-shark-qt/src/libkshark-model.h new file +6
-0+static size_t ksmodel_set_lower_edge (struct kshark_trace_histo *histo) +{ +/* +* Find the index of the first entry inside +* the range (timestamp > min). +*/
this comment contains a mistake as well. It has to be:
/*
* Find the index of the first entry inside
* the range (timestamp >= min). Note that the
* value of min is considered inside the range. */
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.h line 52
Quoted 8 lines
kernel-shark-qt/src/libkshark-model.h new file +8
-0+ssize_t row =kshark_find_entry_by_time (histo->min, + histo->data, +0 , + histo->data_size -1 ); + +assert (row !=BSEARCH_ALL_SMALLER ); + +if (row ==BSEARCH_ALL_GREATER || row ==0 ) {LOB(hist) is set by the lower row (which is less in time isn't it?)
If the data[0]->ts == histo->min, "row" will be equal to 0. If the data-sat starts after histo->min (in time) then "row" will be equal to BSEARCH_ALL_GREATER. In both cases the LOB is empty.
Quoted 39 lines
Quoted 39 lines
kernel-shark-qt/src/libkshark-model.h new file +38
-0+/* Lower Overflow bin is empty. */ + histo->map[LOB (histo)] =KS_EMPTY_BIN ; + histo->bin_count[LOB (histo)] =0 ; + row =0 ; + }else { +/* +* The first entry inside the range is not the first entry +* of the dataset. This means that the Lower Overflow bin +* contains data. +*/ + +/* Lower Overflow bin starts at "0". */ + histo->map[LOB (histo)] =0 ; + +/* +* The number of entries inside the Lower Overflow bin is +* equal to the index of the first entry inside the range. +*/ + histo->bin_count[LOB (histo)] = row; + } + +/* +* Now check if the first entry inside the range falls into the +* first bin. +*/ +if (histo->data[row]->ts < histo->min + histo->bin_size) { +/* +* It is inside the first bin. Set the beginning +* of the first bin. +*/ + histo->map[0 ] = row; + }else { +/* The first bin is empty. */ + histo->map[0 ] =KS_EMPTY_BIN ; + } + +return row; +}
Quoted 8 lines
kernel-shark-qt/src/libkshark-model.h line 98
Quoted 8 lines
kernel-shark-qt/src/libkshark-model.h new file +8
-0+ +static size_t ksmodel_set_upper_edge (struct kshark_trace_histo *histo) +{ +/* +* Find the index of the first entry outside the range +* (timestamp > max). Remember that kshark_find_entry_by_time returns +* the first entry which is equal or greater than the reference time. +*/
I will change this comment as well:
/*
* Find the index of the first entry outside the range
* (timestamp > max). Note that the value of max is considered
* inside the range. Remember that kshark_find_entry_by_time
* returns the first entry which is equal or greater than the
* reference time.
*/
Quoted 1 line
kernel-shark-qt/src/libkshark-model.h line 99
Quoted 1 line
kernel-shark-qt/src/libkshark-model.h new file +1
-0+ ssize_t row = kshark_find_entry_by_time(histo->max + 1,
Here we search for "histo->max + 1"
Quoted 8 lines
kernel-shark-qt/src/libkshark-model.h line 106
Quoted 7 lines
kernel-shark-qt/src/libkshark-model.h new file +7
-0+ histo->data, +0 , + histo->data_size - 1); + +assert (row !=BSEARCH_ALL_GREATER ); + +if (row ==BSEARCH_ALL_SMALLER || row == histo->data_size -1 ) {
And I have a bug here. it has to be:
if (row == BSEARCH_ALL_SMALLER) {I will send this patch again.
Thanks!
Yordan
Quoted 19 lines
UOB(histo) is set by the highest row. Right?
-- Steve
Quoted 15 lines
kernel-shark-qt/src/libkshark-model.h new file +15
-0+/* Upper Overflow bin is empty. */ + histo->map[UOB (histo)] =KS_EMPTY_BIN ; + histo->bin_count[UOB (histo)] =0 ; + }else { +/* +* The Upper Overflow bin contains data. Set its beginning +* and the number of entries. +*/ + histo->map[UOB (histo)] = row; + histo->bin_count[UOB (histo)] = histo->data_size - row; + } + +return row; +} +
PATCH v3 3/6 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
@@ -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
PATCH v3 4/6 kernel-shark-qt: Define Data collections
In reply to Yordan Karadzhov (VMware)Data collections are used to optimize the search for an entry having an abstract property, defined by a Matching condition function and a value. When a collection is processed, the data which is relevant for the collection is enclosed in "Data intervals", defined by pairs of "Resume" and "Break" points. It is guaranteed that the data outside of the intervals contains no entries satisfying the abstract matching condition. Once defined, the Data collection can be used when searching for an entry having the same abstract property. The collection allows to ignore the irrelevant data, thus it eliminates the linear worst-case time complexity of the search.
--- kernel-shark-qt/src/CMakeLists.txt | 3 +- kernel-shark-qt/src/libkshark-collection.c | 805 +++++++++++++++++++++ kernel-shark-qt/src/libkshark.c | 16 + kernel-shark-qt/src/libkshark.h | 79 ++ 4 files changed, 902 insertions(+), 1 deletion(-) create mode 100644 kernel-shark-qt/src/libkshark-collection.c
kernel-shark-qt/src/CMakeLists.txt +2 -1
@@ -2,7 +2,8 @@ message("\n src ...") message(STATUS "libkshark") add_library(kshark SHARED libkshark.c - libkshark-model.c) + libkshark-model.c + libkshark-collection.c) target_link_libraries(kshark ${CMAKE_DL_LIBS} ${TRACEEVENT_LIBRARY}
kernel-shark-qt/src/libkshark-collection.c new file +805 -0
805 lines not on this page · raw message
kernel-shark-qt/src/libkshark.c +16 -0
@@ -1067,6 +1067,7 @@ kshark_entry_request_alloc(size_t first, size_t n,return NULL ; } + req->next =NULL ; req->first = first; req->n = n; req->cond = cond;
@@ -1077,6 +1078,21 @@ kshark_entry_request_alloc(size_t first, size_t n,return req; } +/** +* @brief Free all Data requests in a given list. +* @param req: Intput location for the Data request list. +*/ +void kshark_free_entry_request (struct kshark_entry_request *req) +{ +struct kshark_entry_request *last; + +while (req) { + last = req; + req = req->next; +free (last); + } +} +/** Dummy entry, used to indicate the existence of filtered entries. */ const struct kshark_entry dummy_entry = { .next =NULL ,
kernel-shark-qt/src/libkshark.h +79 -0
103 lines not on this page · raw message
Signature · 1 line
2.17.1
Re: [PATCH v3 4/6] kernel-shark-qt: Define Data collections
Quoted 10 lines · On Fri, 3 Aug 2018 17:29:35 +0300 "Yordan Karadzhov (VMware)"…
Data collections are used to optimize the search for an entry having an abstract property, defined by a Matching condition function and a value. When a collection is processed, the data which is relevant for the collection is enclosed in "Data intervals", defined by pairs of "Resume" and "Break" points. It is guaranteed that the data outside of the intervals contains no entries satisfying the abstract matching condition. Once defined, the Data collection can be used when searching for an entry having the same abstract property. The collection allows to ignore the irrelevant data, thus it eliminates the linear worst-case time complexity of the search.
I think you may need to explain you algorithm a bit more. That is, how will it be used later. I have more questions below.
Does this mean the pairs of resume and break have only elements that match a condition?
Quoted 81 lines
Signed-off-by Yordan Karadzhov (VMware) <[email protected]>--- kernel-shark-qt/src/CMakeLists.txt | 3 +- kernel-shark-qt/src/libkshark-collection.c | 805 +++++++++++++++++++++ kernel-shark-qt/src/libkshark.c | 16 + kernel-shark-qt/src/libkshark.h | 79 ++ 4 files changed, 902 insertions(+), 1 deletion(-) create mode 100644 kernel-shark-qt/src/libkshark-collection.ckernel-shark-qt/src/CMakeLists.txt +2
-1@@ -2,7 +2,8 @@ message("\n src ...") message(STATUS "libkshark") add_library(kshark SHARED libkshark.c - libkshark-model.c) + libkshark-model.c + libkshark-collection.c) target_link_libraries(kshark ${CMAKE_DL_LIBS} ${TRACEEVENT_LIBRARY}kernel-shark-qt/src/libkshark-collection.c new file +51
-0@@ -0,0 +1,805 @@ +// SPDX-License-Identifier: LGPL-2.1 + +/* +* Copyright (C) 2018 VMware Inc, Yordan Karadzhov <[email protected]> +*/ + +/** +* @file libkshark-collection.c +* @brief Data Collections. +*/ + +//C +#include <stdbool.h> +#include <stdlib.h> +#include <assert.h> + +// KernelShark +#include "libkshark.h" + +/* Quiet warnings over documenting simple structures */ +//! @cond Doxygen_Suppress + +enum collection_point_type { +COLLECTION_IGNORE =0 , +COLLECTION_RESUME , +COLLECTION_BREAK , +}; + +#define LAST_BIN -3 + +struct entry_list { +struct entry_list *next; +size_t index; +uint8_t type; +}; + + +enum map_flags { +COLLECTION_BEFORE =-1 , +COLLECTION_INSIDE =0 , +COLLECTION_AFTER =1 , +}; + +//! @endcond + +static bool collection_add_entry (struct entry_list **list, +size_t i,uint8_t type) +{ +struct entry_list *entry = *list; + +if (entry->type !=COLLECTION_IGNORE ) {
kernel-shark-qt/src/libkshark-collection.c line 61
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ entry->next =malloc (sizeof (*entry)); +if (!entry->next) +return false; + + entry = entry->next; + *list = entry; + } + + entry->index = i; + entry->type = type;
This is an interesting "add to list" function. It basically is an update if type is IGNORE, otherwise add a new element. May want a comment before the function about what this is doing because it is not a normal "add to list" type of function.
kernel-shark-qt/src/libkshark-collection.c line 73
Quoted 12 lines
kernel-shark-qt/src/libkshark-collection.c new file +12
-0+ +return true; +} + +static struct kshark_entry_collection * +kshark_data_collection_alloc (struct kshark_context *kshark_ctx, +struct kshark_entry **data, +size_t first, +size_t n_rows, +matching_condition_func cond, +int val, +size_t margin)
What exactly is margin used for?
Quoted 22 lines
kernel-shark-qt/src/libkshark-collection.c new file +22
-0+{ +struct kshark_entry_collection *col_ptr =NULL ; +struct kshark_entry *last_vis_entry =NULL ; +struct entry_list *col_list, *temp; +size_t resume_count =0 , break_count =0 ; +size_t i, j, end, last_added =0 ; +bool good_data = false; + + col_list =malloc (sizeof (*col_list)); +if (!col_list) + goto fail; + + temp = col_list; + +if (margin !=0 ) { +/* +* If this collection includes margin data, add a margin data +* interval at the very beginning of the data-set. +*/ + temp->index = first; + temp->type =COLLECTION_RESUME ; + ++resume_count;
kernel-shark-qt/src/libkshark-collection.c line 105
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ +collection_add_entry (&temp, first + margin -1 , +COLLECTION_BREAK ); + ++break_count; + }else { + temp->type =COLLECTION_IGNORE ; + } + + end = first + n_rows - margin; +for (i = first + margin; i < end; ++i) {
So margin just ignores the first part and last part of the data?
Quoted 7 lines
kernel-shark-qt/src/libkshark-collection.c new file +7
-0+if (!cond (kshark_ctx, data[i], val)) { +/* +* The entry is irrelevant for this collection. +* Do nothing. +*/ +continue ; + }
kernel-shark-qt/src/libkshark-collection.c line 122
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ +/* The Matching condition is satisfed. */ +if (!good_data) { +/* +* Resume the collection here. Add some margin data +* in front of the data of interest. +*/ + good_data = true; +if (last_added ==0 || last_added < i - margin) { + collection_add_entry(&temp, i - margin,
OK, I'm confused at exactly what role margin is playing here. Why do we ignore data if it is not within a given margin?
kernel-shark-qt/src/libkshark-collection.c line 127
Quoted 5 lines
kernel-shark-qt/src/libkshark-collection.c new file +5
-0+ COLLECTION_RESUME); + ++resume_count; + }else { +/* +* Ignore the last collection Brack point.
"Brack point"? do you mean Break point?
kernel-shark-qt/src/libkshark-collection.c line 138
Quoted 11 lines
kernel-shark-qt/src/libkshark-collection.c new file +11
-0+* Continue extending the previous data +* interval. +*/ + temp->type =COLLECTION_IGNORE ; + --break_count; + } + }else if (good_data && + data[i]->next && + !cond (kshark_ctx, data[i]->next, val)) { +/* +* Brack the collection here. Add some margin data
Brack again?
kernel-shark-qt/src/libkshark-collection.c line 151
Quoted 13 lines
kernel-shark-qt/src/libkshark-collection.c new file +13
-0+* after the data of interest. +*/ + good_data = false; + last_vis_entry = data[i]; + +/* Keep adding entries until the "next" record. */ +for (j = i +1 ; + j != end && last_vis_entry->next != data[j]; + j++) + ; + +/* +* If the number of added entryes is smaller then the
"entries" "smaller than"
Quoted 129 lines
kernel-shark-qt/src/libkshark-collection.c new file +129
-0+* number of margin entries requested, keep adding +* until you fill the margin. +*/ +if (i + margin < j) + i = j; +else + i += margin; + + last_added = i; +collection_add_entry (&temp, i,COLLECTION_BREAK ); + ++break_count; + } + } + +if (good_data) { +collection_add_entry (&temp, end -1 ,COLLECTION_BREAK ); + ++break_count; + } + +if (margin !=0 ) { +/* +* If this collection includes margin data, add a margin data +* interval at the very end of the data-set. +*/ +collection_add_entry (&temp, first + n_rows - margin, +COLLECTION_RESUME ); + ++resume_count; + +collection_add_entry (&temp, first + n_rows -1 , +COLLECTION_BREAK ); + ++break_count; + } + +/* +* If everything is OK, we must have pairs of COLLECTION_RESUME +* and COLLECTION_BREAK points. +*/ +assert (break_count == resume_count); + +/* Create the collection. */ + col_ptr =malloc (sizeof (*col_ptr)); +if (!col_ptr) + goto fail; + + col_ptr->next =NULL ; + + col_ptr->resume_points =calloc (resume_count, +sizeof (*col_ptr->resume_points)); +if (!col_ptr->resume_points) + goto fail; + + col_ptr->break_points =calloc (break_count, +sizeof (*col_ptr->break_points)); +if (!col_ptr->break_points) { +free (col_ptr->resume_points); + goto fail; + } + + col_ptr->cond = cond; + col_ptr->val = val; + + col_ptr->size = resume_count; +for (i =0 ; i < col_ptr->size; ++i) { +assert (col_list->type ==COLLECTION_RESUME ); + col_ptr->resume_points[i] = col_list->index; + temp = col_list; + col_list = col_list->next; +free (temp); + +assert (col_list->type ==COLLECTION_BREAK ); + col_ptr->break_points[i] = col_list->index; + temp = col_list; + col_list = col_list->next; +free (temp); + } + +return col_ptr; + +fail: +fprintf (stderr,"Failed to allocate memory for Data collection.\n" ); + +free (col_ptr); +for (i =0 ; i < resume_count + break_count; ++i) { + temp = col_list; + col_list = col_list->next; +free (temp); + } + +return NULL ; +} + +/* +* This function provides mapping between the index inside the data-set and +* the index of the collection interval. Additional output flag is used to +* resolve the ambiguity of the mapping. If the value of the flag is +* COLLECTION_INSIDE, the "source_index" is inside the returned interval. If +* the value of the flag is COLLECTION_BEFORE, the "source_index" is inside +* the gap before the returned interval. If the value of the flag is +* COLLECTION_AFTER, the "source_index" is inside the gap after the returned +* interval. +*/ +static ssize_t +map_collection_index_from_source (const struct kshark_entry_collection *col, +size_t source_index,int *flag) +{ +size_t l, h, mid; + +if (!col->size) +return KS_EMPTY_BIN ; + + l =0 ; + h = col->size -1 ; + +if (source_index < col->resume_points[l]) { + *flag =COLLECTION_BEFORE ; +return l; + } + +if (source_index >= col->resume_points[h]) { +if (source_index < col->break_points[h]) + *flag =COLLECTION_INSIDE ; +else + *flag =COLLECTION_AFTER ; + +return h; + } + +BSEARCH (h, l, source_index > col->resume_points[mid]); +
kernel-shark-qt/src/libkshark-collection.c line 290
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+if (source_index <= col->break_points[l]) + *flag =COLLECTION_INSIDE ; +else + *flag =COLLECTION_AFTER ; + +return l; +} + +/* +* This finction uses the intervals of the Data collection to transform the
"function"
kernel-shark-qt/src/libkshark-collection.c line 292
Quoted 2 lines
kernel-shark-qt/src/libkshark-collection.c new file +2
-0+* inputted single data request into a list of data requests. The new list of +* request will ignore the data outside of the intervals of the collection.
"requests"
Quoted 7 lines
kernel-shark-qt/src/libkshark-collection.c new file +7
-0+*/ +static int +map_collection_back_request (const struct kshark_entry_collection *col, +struct kshark_entry_request **req) +{ +struct kshark_entry_request *req_tmp = *req; +int req_count, col_index_flag;
kernel-shark-qt/src/libkshark-collection.c line 309
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+size_t req_first, req_end; +ssize_t col_index; + +if (req_tmp->next || col->size ==0 ) { +fprintf (stderr,"Unexpected input in " ); +fprintf (stderr,"map_collection_front_request()\n" ); + goto do_nothing; + } + + req_end = req_tmp->first - req_tmp->n +1 ;
Perhaps we should add a comment that states that ->first is the last index of the array, and end is actually the first.
Quoted 89 lines
kernel-shark-qt/src/libkshark-collection.c new file +89
-0+ +/* +* Find the first Resume Point of the collection which is equal or +* greater than the first index of this request. +*/ + col_index =map_collection_index_from_source (col, + req_tmp->first, + &col_index_flag); + +/* +* The value of "col_index" is ambiguous. Use the "col_index_flag" to +* deal with all possible cases. +*/ +if (col_index ==KS_EMPTY_BIN ) { +/* Empty collection. */ + goto do_nothing; + } + +if (col_index_flag ==COLLECTION_AFTER ) { +/* +* This request starts after the end of interval "col_index". +*/ +if (req_end > col->break_points[col_index]) { +/* +* No overlap between the request and the collection. +* Do nothing. +*/ + goto do_nothing; + } + + req_tmp->first = col->break_points[col_index]; + } + +if (col_index_flag ==COLLECTION_BEFORE ) { +/* +* This request starts before the beginning of interval +* "col_index". +*/ +if (col_index ==0 || + req_end > col->break_points[col_index -1 ]) { +/* +* No overlap between the request and the collection. +* Do nothing. +*/ + goto do_nothing; + } + + req_tmp->first = col->break_points[col_index--]; + } + +/* +* Now loop over the intervals of the collection going backwords till +* the end of the inputted request and create a separate request for +* each of those interest. +*/ + req_count =1 ; +while (col_index >=0 && req_end <= col->break_points[col_index]) { +if (req_end >= col->resume_points[col_index]) { +/* +* The last entry of the original request is inside +* the "col_index" collection interval. Close the +* collection request here and return. +*/ + req_tmp->n = req_tmp->first - req_end +1 ; +break ; + } + +/* +* The last entry of the original request is outside of the +* "col_index" interval. Close the collection request at the +* end of this interval and move to the next one. Try to make +* another request there. +*/ + req_tmp->n = req_tmp->first - + col->resume_points[col_index] +1 ; + + --col_index; + +if (req_end > col->break_points[col_index]) { +/* +* The last entry of the original request comes before +* the next collection interval. Stop here. +*/ +break ; + } + +if (col_index >0 ) { +/* Make a new request. */ + req_first = col->break_points[col_index];
kernel-shark-qt/src/libkshark-collection.c line 408
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ + req_tmp->next = +kshark_entry_request_alloc (req_first, +0 , + req_tmp->cond, + req_tmp->val, + req_tmp->vis_only, + req_tmp->vis_mask); + + req_tmp = req_tmp->next;
Need to test if req_tmp is allocated (kshark_entry_request_alloc could fail).
Quoted 4 lines
kernel-shark-qt/src/libkshark-collection.c new file +4
-0+ ++req_count; + } + } +
kernel-shark-qt/src/libkshark-collection.c line 422
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+return req_count; + +do_nothing: +kshark_free_entry_request (*req); + *req =NULL ; +return 0 ; +} + +/* +* This finction uses the intervals of the Data collection to transform the
"function"
Quoted 121 lines
kernel-shark-qt/src/libkshark-collection.c new file +121
-0+* inputted single data request into a list of data requests. The new list of +* request will ignore the data outside of the intervals of the collection. +*/ +static int +map_collection_front_request (const struct kshark_entry_collection *col, +struct kshark_entry_request **req) +{ +struct kshark_entry_request *req_tmp = *req; +int req_count, col_index_flag; +size_t req_first, req_end; +ssize_t col_index; + +if (req_tmp->next || col->size ==0 ) { +fprintf (stderr,"Unexpected input in " ); +fprintf (stderr,"map_collection_front_request()\n" ); + goto do_nothing; + } + + req_end = req_tmp->first + req_tmp->n -1 ; + +/* +* Find the first Resume Point of the collection which is equal or +* greater than the first index of this request. +*/ + col_index =map_collection_index_from_source (col, + req_tmp->first, + &col_index_flag); + +/* +* The value of "col_index" is ambiguous. Use the "col_index_flag" to +* deal with all possible cases. +*/ +if (col_index ==KS_EMPTY_BIN ) { +/* Empty collection. */ + goto do_nothing; + } + +if (col_index_flag ==COLLECTION_AFTER ) { +/* +* This request starts after the end of interval "col_index". +*/ +if (col_index == col->size -1 || + req_end < col->resume_points[col_index +1 ]) { +/* +* No overlap between the request and the collection. +* Do nothing. +*/ + goto do_nothing; + } + + req_tmp->first = col->resume_points[col_index++]; + } + +if (col_index_flag ==COLLECTION_BEFORE ) { +/* +* This request starts before the beginning of interval +* "col_index". +*/ +if (req_end < col->resume_points[col_index]) { +/* +* No overlap between the request and the collection. +* Do nothing. +*/ + goto do_nothing; + } + + req_tmp->first = col->resume_points[col_index]; + } + +/* +* Now loop over the intervals of the collection going forwards till +* the end of the inputted request and create a separate request for +* each of those interest. +*/ + req_count =1 ; +while (col_index < col->size && + req_end >= col->resume_points[col_index]) { +if (req_end <= col->break_points[col_index]) { +/* +* The last entry of the original request is inside +* the "col_index" collection interval. +* Close the collection request here and return. +*/ + req_tmp->n = req_end - req_tmp->first +1 ; +break ; + } + +/* +* The last entry of the original request is outside this +* collection interval (col_index). Close the collection +* request at the end of the interval and move to the next +* interval. Try to make another request there. +*/ + req_tmp->n = col->break_points[col_index] - + req_tmp->first +1 ; + + ++col_index; + +if (req_end < col->resume_points[col_index]) { +/* +* The last entry of the original request comes before +* the beginning of next collection interval. Stop here. +*/ +break ; + } + +if (col_index < col->size) { +/* Make a new request. */ + req_first = col->resume_points[col_index]; + + req_tmp->next = +kshark_entry_request_alloc (req_first, +0 , + req_tmp->cond, + req_tmp->val, + req_tmp->vis_only, + req_tmp->vis_mask); + + req_tmp = req_tmp->next; + ++req_count; + }
kernel-shark-qt/src/libkshark-collection.c line 553
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ } + +return req_count; + +do_nothing: +kshark_free_entry_request (*req); + *req =NULL ; +return 0 ; +} +
You know what I'm going to suggest ;-) Can we combine the front and back versions of the above functions into a single routine with parameters that decide the difference ?
kernel-shark-qt/src/libkshark-collection.c line 561
Quoted 8 lines
kernel-shark-qt/src/libkshark-collection.c new file +8
-0+/** +* @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). +* The search is performed only inside the intervals, defined by +* the data collection. +* +* @param req: Input location for a single Data request. The imputed request
"inputted"
kernel-shark-qt/src/libkshark-collection.c line 565
Quoted 4 lines
kernel-shark-qt/src/libkshark-collection.c new file +4
-0+* will be transformed into a list of requests. This new list of +* requests will ignore the data outside of the intervals of the +* collection. +* @param data: Intput location for the trace data.
"Input"
kernel-shark-qt/src/libkshark-collection.c line 566
Quoted 1 line
kernel-shark-qt/src/libkshark-collection.c new file +1
-0+* @param col: Intput location for the Data collection.
"Input"
Quoted 47 lines
kernel-shark-qt/src/libkshark-collection.c new file +47
-0+* @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 on +* success, or NULL on failure. +* In the special case when some entries, satisfying the Matching +* condition function 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_collection_entry_front (struct kshark_entry_request **req, +struct kshark_entry **data, +const struct kshark_entry_collection *col, +ssize_t *index) +{ +const struct kshark_entry *entry =NULL ; +int req_count; + +/* +* Use the intervals of the Data collection to redefine the data +* request in a way which will ignore the data outside of the +* intervals of the collection. +*/ + req_count =map_collection_front_request (col, req); + +if (index && !req_count) + *index =KS_EMPTY_BIN ; + +/* +* Loop over the list of redefined requests and search until you find +* the first matching entry. +*/ +while (*req) { + entry =kshark_get_entry_front (*req, data, index); +if (entry) +break ; + + *req = (*req)->next; + } + +return entry; +} + +/** +* @brief Search for an entry satisfying the requirements of a given Data
kernel-shark-qt/src/libkshark-collection.c line 623
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+* request. Start from the position provided by the request and go +* searching in the direction of the decreasing timestamps (back). +* The search is performed only inside the intervals, defined by +* the data collection. +* +* @param req: Input location for Data request. The imputed request +* will be transformed into a list of requests. This new list of +* requests will ignore the data outside of the intervals of the +* collection. +* @param data: Intput location for the trace data.
"Input"
kernel-shark-qt/src/libkshark-collection.c line 624
Quoted 1 line
kernel-shark-qt/src/libkshark-collection.c new file +1
-0+* @param col: Intput location for the Data collection.
"Input"
Quoted 39 lines
kernel-shark-qt/src/libkshark-collection.c new file +39
-0+* @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 on +* success, or NULL on failure. +* In the special case when some entries, satisfying the Matching +* condition function 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_collection_entry_back (struct kshark_entry_request **req, +struct kshark_entry **data, +const struct kshark_entry_collection *col, +ssize_t *index) +{ +const struct kshark_entry *entry =NULL ; +int req_count; + +/* +* Use the intervals of the Data collection to redefine the data +* request in a way which will ignore the data outside of the +* intervals of the collection. +*/ + req_count =map_collection_back_request (col, req); +if (index && !req_count) + *index =KS_EMPTY_BIN ; + +/* +* Loop over the list of redefined requests and search until you find +* the first matching entry. +*/ +while (*req) { + entry =kshark_get_entry_back (*req, data, index); +if (entry) +break ; + + *req = (*req)->next;
kernel-shark-qt/src/libkshark-collection.c line 673
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ } + +return entry; +} + +/** +* @brief Search the list of Data collections and find the collection defined +* with a given Matching condition function and value. +* +* @param col: Intput location for the Data collection list.
"Input"
Quoted 15 lines
kernel-shark-qt/src/libkshark-collection.c new file +15
-0+* @param cond: Matching condition function. +* @param val: Matching condition value, used by the Matching condition +* function. +* +* @returns Pointer to a Data collections on success, or NULL on failure. +*/ +struct kshark_entry_collection * +kshark_find_data_collection (struct kshark_entry_collection *col, +matching_condition_func cond, +int val) +{ +while (col) { +if (col->cond == cond && col->val == val) +return col; +
kernel-shark-qt/src/libkshark-collection.c line 698
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ col = col->next; + } + +return NULL ; +} + +/** +* @brief Clear all data intervals of the given Data collection. +* +* @param col: Intput location for the Data collection.
"Input"
Quoted 9 lines
kernel-shark-qt/src/libkshark-collection.c new file +9
-0+*/ +void kshark_reset_data_collection (struct kshark_entry_collection *col) +{ +free (col->resume_points); + col->resume_points =NULL ; + +free (col->break_points); + col->break_points =NULL ; +
kernel-shark-qt/src/libkshark-collection.c line 717
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ col->size =0 ; +} + +static void kshark_free_data_collection (struct kshark_entry_collection *col) +{ +free (col->resume_points); +free (col->break_points); +free (col); +} +
OK, the rest looks good!
-- Steve
Quoted 1 line
Re: [PATCH v3 4/6] kernel-shark-qt: Define Data collections
Hi Steven,
Quoted 10 lines · Steven Rostedt
kernel-shark-qt/src/libkshark-collection.c line 73
Quoted 8 lines
kernel-shark-qt/src/libkshark-collection.c new file +8
-0+static struct kshark_entry_collection * +kshark_data_collection_alloc (struct kshark_context *kshark_ctx, +struct kshark_entry **data, +size_t first, +size_t n_rows, +matching_condition_func cond, +int val, +size_t margin)What exactly is margin used for?
The margin allows the user to inflate each of the interval, by appending additional data which do not satisfy the matching condition. This data is added to each interval at the beginning and at the end of the data which satisfies the condition, as well as at the beginning and at the end of data-set. The margin data can be useful in the case when the user wants to be able to see what is happening before and after the appearance of his data of interest.
Thanks!
Yordan
PATCH v3 5/6 kernel-shark-qt: Make the Vis. model use Data collections.
In reply to Yordan Karadzhov (VMware)This patch optimizes the search instruments of the model by adding the possibility of using Data collections.
--- kernel-shark-qt/examples/datahisto.c | 4 ++ kernel-shark-qt/src/libkshark-model.c | 57 +++++++++++++++++++++++---- kernel-shark-qt/src/libkshark-model.h | 14 ++++++- 3 files changed, 65 insertions(+), 10 deletions(-)
kernel-shark-qt/examples/datahisto.c +4 -0
@@ -27,18 +27,22 @@ void dump_bin(struct kshark_trace_histo *histo, int bin,if (strcmp (type,"cpu" ) ==0 ) { e_front =ksmodel_get_entry_front (histo, bin, true, kshark_match_cpu, val, +NULL , &i_front); e_back =ksmodel_get_entry_back (histo, bin, true, kshark_match_cpu, val, +NULL , &i_back); }else if (strcmp (type,"task" ) ==0 ) { e_front =ksmodel_get_entry_front (histo, bin, true, kshark_match_pid, val, +NULL , &i_front); e_back =ksmodel_get_entry_back (histo, bin, true, kshark_match_pid, val, +NULL , &i_back); }else { i_front =ksmodel_first_index_at_bin (histo, bin);
kernel-shark-qt/src/libkshark-model.c +49 -8
201 lines not on this page · raw message
kernel-shark-qt/src/libkshark-model.h +12 -2
@@ -100,35 +100,45 @@ const struct kshark_entry * ksmodel_get_entry_front(struct kshark_trace_histo *histo, int bin, bool vis_only, matching_condition_func func, int val, + struct kshark_entry_collection *col, ssize_t *index);const struct kshark_entry *ksmodel_get_entry_back (struct kshark_trace_histo *histo,int bin,bool vis_only,matching_condition_func func,int val, +struct kshark_entry_collection *col,ssize_t *index);int ksmodel_get_pid_front (struct kshark_trace_histo *histo,int bin,int cpu,bool vis_only, +struct kshark_entry_collection *col,ssize_t *index);int ksmodel_get_pid_back (struct kshark_trace_histo *histo,int bin,int cpu,bool vis_only, +struct kshark_entry_collection *col,ssize_t *index);int ksmodel_get_cpu_front (struct kshark_trace_histo *histo,int bin,int pid,bool vis_only, +struct kshark_entry_collection *col,ssize_t *index);int ksmodel_get_cpu_back (struct kshark_trace_histo *histo,int bin,int pid,bool vis_only, +struct kshark_entry_collection *col,ssize_t *index);bool ksmodel_cpu_visible_event_exist (struct kshark_trace_histo *histo, -int bin,int cpu,ssize_t *index); +int bin,int cpu, +struct kshark_entry_collection *col, +ssize_t *index);bool ksmodel_task_visible_event_exist (struct kshark_trace_histo *histo, -int bin,int pid,ssize_t *index); +int bin,int pid, +struct kshark_entry_collection *col, +ssize_t *index);static inline double ksmodel_bin_time (struct kshark_trace_histo *histo,int bin)
Signature · 1 line
2.17.1
PATCH v3 6/6 kernel-shark-qt: Changed the KernelShark version identifier.
In reply to Yordan Karadzhov (VMware)(Patch Id) ++
--- kernel-shark-qt/CMakeLists.txt | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel-shark-qt/CMakeLists.txt +1 -1
@@ -6,7 +6,7 @@ project(kernel-shark-qt) set(KS_VERSION_MAJOR 0) set(KS_VERSION_MINOR 7) -set(KS_VERSION_PATCH 0) +set(KS_VERSION_PATCH 1) set(KS_VERSION_STRING ${KS_VERSION_MAJOR}.${KS_VERSION_MINOR}.${KS_VERSION_PATCH}) message("\n project: Kernel Shark: (version: ${KS_VERSION_STRING})\n")
Signature · 1 line
2.17.1