Add visualization model for the Qt-based KernelShark
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.
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 | 719 ++++++++++++ kernel-shark-qt/src/libkshark-model.c | 1180 ++++++++++++++++++++ kernel-shark-qt/src/libkshark-model.h | 147 +++ kernel-shark-qt/src/libkshark.c | 285 ++++- kernel-shark-qt/src/libkshark.h | 155 ++- 9 files changed, 2650 insertions(+), 5 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 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 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 | 269 +++++++++++++++++++++++++++++++- kernel-shark-qt/src/libkshark.h | 76 ++++++++- 2 files changed, 342 insertions(+), 3 deletions(-)
kernel-shark-qt/src/libkshark.c +268 -1
@@ -861,7 +861,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;
@@ -908,3 +908,270 @@ 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 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_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 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_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 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. +*/ +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 }; + +/** +* @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) +{ +struct kshark_context *kshark_ctx =NULL ; +const struct kshark_entry *e =NULL ; +size_t i, last; + +if (index) + *index =KS_EMPTY_BIN ; + +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 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) +{ +struct kshark_context *kshark_ctx =NULL ; +const struct kshark_entry *e =NULL ; +ssize_t i, last; + +if (index) + *index =KS_EMPTY_BIN ; + +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
Re: [PATCH 1/6] kernel-shark-qt: Add generic instruments for searching inside the trace data
Quoted 1 line · On Wed, 11 Jul 2018 16:38:09 +0300 "Yordan Karadzhov (VMware)"…
This patch introduces the instrumentation for data extraction, used by the
No need for the comma.
Quoted 3 lines
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.
"in detail."
Quoted 2 lines
The first type of instruments provides binary search inside a sorted in time
either "first type of instrument provides" or
"first type of instruments provide"
Quoted 5 lines
arrays of
kshark_entriesortrace_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)
Same here for the "second type ..."
Quoted 94 lines
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.
Signed-off-by Yordan Karadzhov (VMware) <[email protected]>--- kernel-shark-qt/src/libkshark.c | 269 +++++++++++++++++++++++++++++++- kernel-shark-qt/src/libkshark.h | 76 ++++++++- 2 files changed, 342 insertions(+), 3 deletions(-)kernel-shark-qt/src/libkshark.c +60
-1@@ -861,7 +861,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;@@ -908,3 +908,270 @@ 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 ) {
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 979
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+ mid = (l + h) /2 ; +if (data[mid]->ts < time) + l = mid; +else + h = mid; + } + +return h; +} +
I don't like the duplication of code, but we can wait till later to see if we can combine this. Once I get a good idea of how the code is being used then we can restructure this. But for now, we'll keep this as is.
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 986
Quoted 7 lines
kernel-shark-qt/src/libkshark.c +7
-0+/** +* @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.
Is this going to be extended in the future? Why the kshark_ctx?
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+*/ +bool kshark_check_pid (struct kshark_context *kshark_ctx, +struct kshark_entry *e,int pid) +{ +if (e->pid == pid) +return true; + +return false; +} +
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 1006
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+/** +* @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_check_cpu (struct kshark_context *kshark_ctx, +struct kshark_entry *e,int cpu)
Same here.
And since kshark_entry is defined in the header, why not make these inlined functions?
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 1016
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+{ +if (e->cpu == cpu) +return true; + +return false; +} + +/** +* @brief Create Data request. The user has to free the returned +* kshark_entry_request.
Information about freeing should usually be in the @returns, or is this different with Doxygen?
But the description should say something about what to create a request for.
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 1026
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+* @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.
Like adding: "The pointer must be freed by the user.", also it should explain what function to use to free it.
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 1037
Quoted 11 lines
kernel-shark-qt/src/libkshark.c +11
-0+*/ +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" );
This should use warning(). But that can be done later.
Quoted 11 lines
kernel-shark-qt/src/libkshark.c +11
-0+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;
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 1058
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+} + +/** 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 };
BTW, C99 allows you to do this:
= {
.next = NULL,
.visible = 0x00,
.cpu = KS_FILTERED_BIN,
.pid = KS_FILTERED_BIN,
.event_id = -1,
.offset = 0,
.ts = 0
};And then you don't need to worry about keeping the values in order of the structure.
Quoted 32 lines
kernel-shark-qt/src/libkshark.c +32
-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). +* @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) +{ +struct kshark_context *kshark_ctx =NULL ; +const struct kshark_entry *e =NULL ; +size_t i, last; + +if (index) + *index =KS_EMPTY_BIN ; + +if (!kshark_instance (&kshark_ctx)) +return e; +
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 1100
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+ 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;
I'm thinking that you don't need the dummy entry, but instead do:
#define INVALID_KSHARK_ENTRY ((struct kshark_entry *)-1UL)
e = INVALID_KSHARK_ENTRY;
And then have a macro to test the result:
#define VALID_KSHARK_ENTRY(e) ((e) != INVALID_KSHARK_ENTRY)
This is common to do in Linux.
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 1110
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+ }else { + e = data[i]; +break ; + } + } + } + +if (index) { +if (e) + *index = (e->event_id >=0 )? i :KS_FILTERED_BIN ;
Then this would be:
*index = VALID_KSHARK_ENTRY(e) ? i : KS_FILTERED_BIN;
Quoted 57 lines
kernel-shark-qt/src/libkshark.c +57
-0+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 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) +{ +struct kshark_context *kshark_ctx =NULL ; +const struct kshark_entry *e =NULL ; +ssize_t i, last; + +if (index) + *index =KS_EMPTY_BIN ; + +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 ; + } + } + }
kernel-shark-qt/src/libkshark.c char* kshark_dump_entry(struct kshark_entry *entry) · line 1177
Quoted 10 lines
kernel-shark-qt/src/libkshark.c +10
-0+ +if (index) { +if (e) + *index = (e->event_id >=0 )? i :KS_FILTERED_BIN ; +else + *index =KS_EMPTY_BIN ; + } + +return e; +}
I think you can combine the above two functions:
static const struct kshark_entry *
get_entry(const struct kshark_entry_request *req,
struct kshark_entry **data,
ssize_t *index, ssize_t start, ssize_t last, 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;
last = req->first + req->n;
for (i = start; i != last; 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;
}const struct kshark_entry * kshark_get_entry_front(const struct kshark_entry_request *req,
struct kshark_entry **data, ssize_t *index)
{
return get_entry(req, data, index, req->first,
req->first + req->n, 1);
}kshark_get_entry_back(const struct kshark_entry_request *req,
struct kshark_entry **data, ssize_t *index)
{
return get_entry(req, data, index, req->first,
req->first - req->n, -1);
}I haven't really checked it, so it may be buggy. But you get the idea.
kernel-shark-qt/src/libkshark.h struct kshark_entry { · line 48
Quoted 10 lines
kernel-shark-qt/src/libkshark.h +1
-1@@ -45,7 +45,7 @@ struct kshark_entry {uint8_t visible;/** The CPU core of the record. */ -uint8_t cpu; +int8_t cpu;
This should be a separate patch.
-- Steve
Quoted 91 lines
kernel-shark-qt/src/libkshark.h +73
-1/** The PID of the task the record was generated. */ int16_t pid;@@ -133,7 +133,7 @@ void kshark_close(struct kshark_context *kshark_ctx);void kshark_free (struct kshark_context *kshark_ctx); -char *kshark_dump_entry (struct kshark_entry *entry); +char *kshark_dump_entry (const struct kshark_entry *entry);/** Bit masks used to control the visibility of the entry after filtering. */ enum kshark_filter_masks {@@ -190,6 +190,78 @@ void kshark_filter_entries(struct kshark_context *kshark_ctx,struct kshark_entry **data, size_t n_entries); +size_t kshark_find_entry_by_time (uint64_t time, +struct kshark_entry **data_rows, +size_t l,size_t h); + +size_t kshark_find_record_by_time (uint64_t time, +struct pevent_record **data_rows, +size_t l,size_t h); + +bool kshark_check_pid (struct kshark_context *kshark_ctx, +struct kshark_entry *e,int pid); + +bool kshark_check_cpu (struct kshark_context *kshark_ctx, +struct kshark_entry *e,int cpu); + +/** Empty bin identifier. */ +#define KS_EMPTY_BIN -1 + +/** Filtered bin identifier. */ +#define KS_FILTERED_BIN -2 + +/** Matching condition function type. To be user for data requests */ +typedef bool (matching_condition_func )(struct kshark_context *, +struct kshark_entry *, +int ); + +/** +* Data request structure, defining the properties of the required +* kshark_entry. +*/ +struct kshark_entry_request { +/** +* Array index specifying the position inside the array from where +* the search starts. +*/ +size_t first; + +/** Number of array elements to search in. */ +size_t n; + +/** Matching condition function. */ +matching_condition_func *cond; + +/** +* Matching condition value, used by the Matching condition function. +*/ +int val; + +/** If true, a visible entry is requested. */ +bool vis_only; + +/** +* If "vis_only" is true, use this mask to specify the level of +* visibility of the requested entry. +*/ +uint8_t vis_mask; +}; + +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); + +const struct kshark_entry * +kshark_get_entry_front (const struct kshark_entry_request *req, +struct kshark_entry **data, +ssize_t *index); + +const struct kshark_entry * +kshark_get_entry_back (const struct kshark_entry_request *req, +struct kshark_entry **data, +ssize_t *index); + #ifdef __cplusplus }#endif
Re: [PATCH 1/6] kernel-shark-qt: Add generic instruments for searching inside the trace data
Quoted 9 lines · Steven Rostedt
Quoted 7 lines
+/**
+ * @brief Simple Pid matching function to be user for data requests.
+ * @paramkshark_ctx: Input location for the session context pointer.
+ * @param e:kshark_entryto be checked.
+ * @param pid: Matching condition value.
+ * @returns True if the Pid of the entry matches the value of "pid".
+ * Else false.Is this going to be extended in the future? Why the
kshark_ctx?
Yes, this is something we need to discuss.
in the header we have
/** Matching condition function type. To be user for data requests */ typedef bool (matching_condition_func)(struct kshark_context*,
struct kshark_entry*, int);
I wanted the type of the abstract condition function to be such that it can accommodate complicated logic in the future. What do you think?
Thanks!
Yordan
Quoted 10 lines
Quoted 10 lines
+ */
kernel-shark-qt/src/libkshark.c +9
-0+bool kshark_check_pid (struct kshark_context *kshark_ctx, +struct kshark_entry *e,int pid) +{ +if (e->pid == pid) +return true; + +return false; +} +
Re: [PATCH 1/6] kernel-shark-qt: Add generic instruments for searching inside the trace data
Quoted 15 lines · On Thu, 12 Jul 2018 15:49:33 +0300 "Yordan Karadzhov (VMware)"…
Quoted 9 lines · Steven Rostedt
Quoted 7 lines
+/**
+ * @brief Simple Pid matching function to be user for data requests.
+ * @paramkshark_ctx: Input location for the session context pointer.
+ * @param e:kshark_entryto be checked.
+ * @param pid: Matching condition value.
+ * @returns True if the Pid of the entry matches the value of "pid".
+ * Else false.Is this going to be extended in the future? Why the
kshark_ctx?Yes, this is something we need to discuss.
in the header we have
Quoted 9 lines
/** Matching condition function type. To be user for data requests */ typedef bool (matching_condition_func)(struct kshark_context*,
struct kshark_entry*, int);I wanted the type of the abstract condition function to be such that it can accommodate complicated logic in the future.
What do you think?
Makes sense. I just didn't realize that the kshark_check_pid is one of the matching functions. Hmm, perhaps we should rename it to:
kshark_match_pid() ?
-- Steve
PATCH 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.
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 | 1133 +++++++++++++++++++++++++ kernel-shark-qt/src/libkshark-model.h | 138 +++ 3 files changed, 1273 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 +1133 -0
1,133 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
Re: [PATCH 2/6] kernel-shark-qt: Introduce the visualization model used by the Qt-based KS
Quoted 33 lines · On Wed, 11 Jul 2018 16:38:10 +0300 "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.
Quoted 2 lines
The following patch will introduces a simple example, demonstrating the usage of the API of the Model.
The last paragraph above can be removed from the change log. It doesn't add value to this change.
Quoted 73 lines
Signed-off-by Yordan Karadzhov (VMware) <[email protected]>--- kernel-shark-qt/src/CMakeLists.txt | 3 +- kernel-shark-qt/src/libkshark-model.c | 1133 +++++++++++++++++++++++++ kernel-shark-qt/src/libkshark-model.h | 138 +++ 3 files changed, 1273 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 +43
-0@@ -0,0 +1,1133 @@ +// SPDX-License-Identifier: LGPL-2.1 + +/* +* Copyright (C) 2017 VMware Inc, Yordan Karadzhov <[email protected]> +*/ + +/** +* @file libkshark.c +* @brief Visualization model for FTRACE (trace-cmd) data. +*/ + +// C +#include <stdlib.h> + +// KernelShark +#include "libkshark-model.h" + +/** +* @brief Initialize the Visualization model. +* @param histo: Input location for the model descriptor. +*/ +void ksmodel_init (struct kshark_trace_histo *histo) +{ +/* +* Initialize an empty histo. The histo will have no bins and will +* contain no data. +*/ + histo->bin_size =0 ; + histo->min =0 ; + histo->max =0 ; + histo->n_bins =0 ; + + histo->bin_count =NULL ; + histo->map =NULL ; +} + +/** +* @brief Clear (reset) the Visualization model. +* @param histo: Input location for the model descriptor. +*/ +void ksmodel_clear (struct kshark_trace_histo *histo) +{ +/* Reset the histo. It will have no bins and will contain no data. */
kernel-shark-qt/src/libkshark-model.c line 53
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ histo->bin_size =0 ; + histo->min =0 ; + histo->max =0 ; + histo->n_bins =0 ; + +free (histo->map); + histo->map =NULL ; + +free (histo->bin_count); + histo->bin_count =NULL ;
The above can be shortened to:
{
free(histo->map);
free(histo->bin_count);
ksmodel_init(histo);
}kernel-shark-qt/src/libkshark-model.c line 65
Quoted 12 lines
kernel-shark-qt/src/libkshark-model.c new file +12
-0+} + +static void ksmodel_reset_bins (struct kshark_trace_histo *histo, +size_t first,size_t last) +{ +size_t i; + +/* Reset the content of the bins. */ +for (i = first; i <= last; ++i) { + histo->map[i] =KS_EMPTY_BIN ; + histo->bin_count[i] =0 ; + }
Hmm, could we do:
memset(&histo->map[first], KS_EMPTY_BIN, (last - first + 1) * sizeof(histo->map[0])); memset(&histo->bin_count[first], 0, (last - fist + 1) * sizeof(histo->bin_count[0]));
As KS_EMPTY_BIN is -1, filling map with 0xff should work fine.
But we need to make a comment by KS_EMPTY_BIN that it must be -1 and no other value (with the exception of zero).
Quoted 4 lines
kernel-shark-qt/src/libkshark-model.c new file +4
-0+} + +static void ksmodel_histo_alloc (struct kshark_trace_histo *histo,size_t n) +{
kernel-shark-qt/src/libkshark-model.c line 79
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+free (histo->bin_count); +free (histo->map); + +/* Create bins. Two overflow bins are added. */ + histo->map =calloc (n +2 ,sizeof (*histo->map)); + histo->bin_count =calloc (n +2 ,sizeof (*histo->bin_count)); + +if (!histo->map || !histo->bin_count) { +ksmodel_clear (histo); +fprintf (stderr,"Failed to allocate memory for a histo.\n" );
I believe that this should return success or failure.
Quoted 13 lines
kernel-shark-qt/src/libkshark-model.c new file +13
-0+return ; + } + + histo->n_bins = n; +} + +static void ksmodel_set_in_range_bining (struct kshark_trace_histo *histo, +size_t n,uint64_t min,uint64_t max, +bool force_in_range) +{ +uint64_t corrected_range, delta_range, range = max - min; +struct kshark_entry *last; +
kernel-shark-qt/src/libkshark-model.c line 102
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+/* The size of the bin must be >= 1, hence the range must be >= n. */ +if (n ==0 || range < n) +return ; + +/* +* If the number of bins changes, allocate memory for the descriptor +* of the model. +*/ +if (n != histo->n_bins) { +ksmodel_histo_alloc (histo, n);
And if we fail to allocate, the histo->n_bins is zero.
kernel-shark-qt/src/libkshark-model.c line 108
Quoted 6 lines
kernel-shark-qt/src/libkshark-model.c new file +6
-0+ } + +/* Reset the content of all bins (including overflow bins) to zero. */ +ksmodel_reset_bins (histo,0 , histo->n_bins +1 ); + +if (range % n ==0 ) {
Note, if we failed to allocate, n != histo->n_bins.
kernel-shark-qt/src/libkshark-model.c line 121
Quoted 13 lines
kernel-shark-qt/src/libkshark-model.c new file +13
-0+/* +* The range is multiple of the number of bin and needs no +* adjustment. This is very unlikely to happen but still ... +*/ + histo->min = min; + histo->max = max; + histo->bin_size = range / n; + }else { +/* +* The range needs adjustment. The new range will be slightly +* bigger, compared to the requested one. +*/ + histo->bin_size = range / n +1 ;
Probably could do the following:
histo->bin_size = (range + n - 1) / n; histo->min = min; histo->max = max; corrected_range = histo->bin_size * n; /* Check if we don't need to do any adjustments */ if (corrected_range == range) return;
Then do the correction below.
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ corrected_range = histo->bin_size * n; + delta_range = corrected_range - range; + histo->min = min - delta_range /2 ; + histo->max = histo->min + corrected_range; + +if (!force_in_range) +return ; + +/* +* Make sure that the new range doesn't go outside of the time
kernel-shark-qt/src/libkshark-model.c line 141
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+* interval of the dataset. +*/ + last = histo->data[histo->data_size -1 ]; +if (histo->min < histo->data[0 ]->ts) { + histo->min = histo->data[0 ]->ts; + histo->max = histo->min + corrected_range; + }else if (histo->max > last->ts) { + histo->max = last->ts; + histo->min = histo->max - corrected_range; + }
Isn't it possible that the range could be outside of min and max?
I haven't looked at exactly how this is used, so it may not be. But a comment should be added to why that is so.
Quoted 26 lines
kernel-shark-qt/src/libkshark-model.c new file +26
-0+ } +} + +/** +* @brief Prepare the bining of the Visualization model. +* @param histo: Input location for the model descriptor. +* @param n: Number of bins. +* @param min: Lower edge of the time-window to be visualized. +* @param max: Upper edge of the time-window to be visualized. +*/ +void ksmodel_set_bining (struct kshark_trace_histo *histo, +size_t n,uint64_t min,uint64_t max) +{ +ksmodel_set_in_range_bining (histo, n, min, max, false); +} + +static size_t ksmodel_set_lower_edge (struct kshark_trace_histo *histo) +{ +/* +* Find the index of the first entry inside +* the range (timestamp > min). +*/ +size_t row =kshark_find_entry_by_time (histo->min, + histo->data, +0 , + histo->data_size -1 );
kernel-shark-qt/src/libkshark-model.c line 177
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ +if (row !=0 ) { +/* +* 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[histo->n_bins +1 ] =0 ;
To keep from doing off by one errors, I think we should possibly have a:
hist->upper_overflow_bin and hist->lower_overflow_bin
Then you can do:
histo->map[hist->lower_overflow_bin] = 0; histo->bin_count[hist->lower_overflow_bin] = row;
Quoted 12 lines
kernel-shark-qt/src/libkshark-model.c new file +12
-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[histo->n_bins +1 ] = row; + }else { +/* +* Lower Overflow bin is empty. The number of entries is +* already set to "0". +*/ + histo->map[histo->n_bins +1 ] =KS_EMPTY_BIN ;
kernel-shark-qt/src/libkshark-model.c line 199
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ } + +/* +* 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 fisrs bin. Set the beginning +* of the fisrs bin.
What's the "fisrs bin"?
Quoted 26 lines
kernel-shark-qt/src/libkshark-model.c new file +26
-0+*/ + histo->map[0 ] = row; + }else { +/* The fisrs 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). +*/ +size_t row =kshark_find_entry_by_time (histo->max, + histo->data, +0 , + histo->data_size -1 ); + +if (row < histo->data_size -1 || + (row == histo->data_size -1 && + histo->data[histo->data_size -1 ]->ts > histo->max)) { +/* +* The Upper Overflow bin contains data. Set its beginning
kernel-shark-qt/src/libkshark-model.c line 235
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+* and the number of entries. +*/ + histo->map[histo->n_bins] = row; + histo->bin_count[histo->n_bins] = histo->data_size - row; + }else { +/* +* Upper Overflow bin is empty. The number of entries is +* already set to "0". +*/ + histo->map[histo->n_bins] =KS_EMPTY_BIN ;
And here use: histo->map[histo->upper_overflow_bin]
Quoted 8 lines
kernel-shark-qt/src/libkshark-model.c new file +8
-0+ } + +return row; +} + +static void ksmodel_set_next_bin_edge (struct kshark_trace_histo *histo, +size_t bin) +{
kernel-shark-qt/src/libkshark-model.c line 253
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+size_t time, row, next_bin = bin +1 ; + +/* Calculate the beginning of the next bin. */ + time = histo->min + next_bin * histo->bin_size; + +/* +* Find the index of the first entry inside +* the next bin (timestamp > time). +*/ + row = kshark_find_entry_by_time(time,histo->data, 0,
Space after comma: "time, histo"
kernel-shark-qt/src/libkshark-model.c line 266
Quoted 13 lines
kernel-shark-qt/src/libkshark-model.c new file +13
-0+ histo->data_size - 1); + +/* +* The timestamp of the very last entry of the dataset can be exactly +* equal to the value of the upper edge of the range. This is very +* likely to happen when we use ksmodel_set_in_range_bining(). In this +* case we have to increase the size of the very last bin in order to +* make sure that the last entry of the dataset will fall into it. +*/ +if (next_bin == histo->n_bins -1 ) + ++time; + +if (histo->data[row]->ts >= time + histo->bin_size) {
Remove one of the two spaces between "ts >="
Quoted 5 lines
kernel-shark-qt/src/libkshark-model.c new file +5
-0+/* The bin is empty. */ + histo->map[next_bin] =KS_EMPTY_BIN ; +return ; + } +
kernel-shark-qt/src/libkshark-model.c line 281
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+/* Set the index of the first entry. */ + histo->map[next_bin] = row; +} + +static void ksmodel_set_bin_counts (struct kshark_trace_histo *histo) +{ +size_t i =0 , prev_not_empty; + +/* +* Find the first bin which contain data. Start by checking the
"which contains data"
kernel-shark-qt/src/libkshark-model.c line 284
Quoted 3 lines
kernel-shark-qt/src/libkshark-model.c new file +3
-0+* Lower Overflow bin. +*/ +if (histo->map[histo->n_bins +1 ] !=KS_EMPTY_BIN ) {
This is where having "lower_overflow_bin" and "upper_overflow_bin" will come in handy. One does not need to remember which is which.
kernel-shark-qt/src/libkshark-model.c line 296
Quoted 12 lines
kernel-shark-qt/src/libkshark-model.c new file +12
-0+ prev_not_empty = histo->n_bins +1 ; + }else { +while (histo->map[i] <0 ) { + ++i; + } + + prev_not_empty = i++; + } + +/* +* Starting from the first not empty bin, loop over all bins and +* calculate the number of entries.
I would reword the above. ", loop over all bins and fill in the bin_count array to hold the number of empty bins after each one.."
Quoted 4 lines
kernel-shark-qt/src/libkshark-model.c new file +4
-0+*/ +while (i < histo->n_bins) { +if (histo->map[i] !=KS_EMPTY_BIN ) { + histo->bin_count[prev_not_empty] =
kernel-shark-qt/src/libkshark-model.c line 310
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ histo->map[i] - histo->map[prev_not_empty]; + + prev_not_empty = i; + } + + ++i; + } + +/* Check if the Upper Overflow bin contains data. */ +if (histo->map[histo->n_bins] ==KS_EMPTY_BIN ) {
if (histo->map[histo->upper_overflow_bin] == KS_EMPTY_BIN) {;-)
Does the lower and upper overflow bins even need to be in the map array?
Quoted 50 lines
kernel-shark-qt/src/libkshark-model.c new file +50
-0+/* +* 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[histo->n_bins] - + histo->map[prev_not_empty]; + } +} + +/** +* @brief Provide the Visualization model with data. Calculate the current +* state of the model. +* @param histo: Input location for the model descriptor. +* @param data: Input location for the trace data. +* @param n: Number of bins. +*/ +void ksmodel_fill (struct kshark_trace_histo *histo, +struct kshark_entry **data,size_t n) +{ +size_t bin; + + histo->data_size = n; + histo->data = data; + +if (histo->n_bins ==0 || + histo->bin_size ==0 || + histo->data_size ==0 ) { +/* +* Something is wrong with this histo. +* Most likely the binning is not set. +*/ +ksmodel_clear (histo); +fprintf (stderr, +"Unable to fill the model with data.\n" ); +fprintf (stderr, +"Try to set the bining of the model first.\n" ); + +return ; + } + +/* Set the Lower Overflow bin */
kernel-shark-qt/src/libkshark-model.c line 370
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ksmodel_set_lower_edge (histo); + +/* +* Loop over the dataset and set the beginning of all individual bins. +*/ + bin =0 ; +while (bin < histo->n_bins) { +ksmodel_set_next_bin_edge (histo, bin); + ++bin; + }
The above should be a for loop.
for (bin = 0; bin < histo->n_bins; bin++) ksmodel_set_next_bin_edge(histo, bin);
BTW, when we have a single line after a for, while or if statement, we don't need the brackets '{' '}'
Quoted 7 lines
kernel-shark-qt/src/libkshark-model.c new file +7
-0+ +/* Set the Upper Overflow bin. */ +ksmodel_set_upper_edge (histo); + +/* Calculate the number of entries in each bin. */ +ksmodel_set_bin_counts (histo); +}
kernel-shark-qt/src/libkshark-model.c line 387
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ +/** +* @brief Get the total number of entries in a given bin. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @returns The number of entries in this bin. +*/ +size_t ksmodel_bin_count (struct kshark_trace_histo *histo,int bin) +{ +if (bin >=0 && bin < (int ) histo->n_bins)
Why is bin "int" and not ssize_t? If you need a cast above, that means we can have issues if histo->n_bins is greater than 2 gig.
Quoted 51 lines
kernel-shark-qt/src/libkshark-model.c new file +51
-0+return histo->bin_count[bin]; + +if (bin ==UPPER_OVERFLOW_BIN ) +return histo->bin_count[histo->n_bins]; + +if (bin ==LOWER_OVERFLOW_BIN ) +return histo->bin_count[histo->n_bins +1 ]; + +return 0 ; +} + +/** +* @brief Shift the time-window of the model forward. Recalculate the current +* 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 bin; + +if (!histo->data_size) +return ; + +if (ksmodel_bin_count (histo,UPPER_OVERFLOW_BIN ) ==0 ) { +/* +* 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 ; + } + +if (n >= histo->n_bins) { +/* +* No overlap between the new and the old ranges. Recalculate +* all bins from scratch. First calculate the new range. +*/ + histo->min += n * histo->bin_size; + histo->max += n * histo->bin_size; + +ksmodel_set_bining (histo, histo->n_bins, histo->min, + histo->max); + +ksmodel_fill (histo, histo->data, histo->data_size); +return ; + } + +/* Set the new Lower Overflow bin */ +ksmodel_set_lower_edge (histo); +
kernel-shark-qt/src/libkshark-model.c line 448
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+/* +* Copy the content of all overlaping bins starting from bin "0" +* of the new histo. +*/ + bin =0 ; +while (bin < histo->n_bins - n) { + histo->map[bin] = histo->map[bin + n]; + histo->bin_count[bin] = histo->bin_count[bin + n]; + ++bin; + }
Replace the above with:
memmove(&histo->map[bin + n], &histo->map[bin], sizeof(histo->map[0]) * n); memmove(&histo->bin_count[bin + n], &histo->bin_count[bin], sizeof(histo->bin_count[0]) * n); bin += n;
kernel-shark-qt/src/libkshark-model.c line 455
Quoted 7 lines
kernel-shark-qt/src/libkshark-model.c new file +7
-0+ + histo->map[bin] = histo->map[bin + n]; + histo->bin_count[bin] =0 ; + +/* Calculate only the content of the new (non-overlapping) bins. */ +ksmodel_reset_bins (histo, bin +1 , histo->n_bins); +while (bin < histo->n_bins) {
Make this a for loop:
for (; bin < histo->n_bins; bin++)
Quoted 45 lines
kernel-shark-qt/src/libkshark-model.c new file +45
-0+ksmodel_set_next_bin_edge (histo, bin); + ++bin; + } + +/* +* Set the new Upper Overflow bin and calculate the number of entries +* in each bin. +*/ +ksmodel_set_upper_edge (histo); +ksmodel_set_bin_counts (histo); +} + +/** +* @brief Shift the time-window of the model backward. Recalculate the current +* state of the model. +* @param histo: Input location for the model descriptor. +* @param n: Number of bins to shift. +*/ +void ksmodel_shift_backward (struct kshark_trace_histo *histo,size_t n) +{ +size_t bin; + +if (!histo->data_size) +return ; + +if (ksmodel_bin_count (histo,LOWER_OVERFLOW_BIN ) ==0 ) { +/* +* The Lower Overflow bin is empty. This means that we are at +* the Lower edge of the dataset already. Do nothing in this +* case. +*/ +return ; + } + +if (n >= histo->n_bins) { +/* +* No overlap between the new and the old range. Recalculate +* all bins from scratch. First calculate the new range. +*/ + histo->min -= n * histo->bin_size; + histo->max -= n * histo->bin_size; + +ksmodel_set_bining (histo, histo->n_bins, histo->min, + histo->max); +
kernel-shark-qt/src/libkshark-model.c line 510
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ksmodel_fill (histo, histo->data, histo->data_size); +return ; + } + +/* +* Copy the content of all overlaping bins starting from the last bin +* of the new histo. +*/ + bin = histo->n_bins -1 ; +while (1 ) {
I don't really understand the below if.
Quoted 4 lines
kernel-shark-qt/src/libkshark-model.c new file +4
-0+if (bin > histo->n_bins - n && histo->map[bin] >=0 ) { + histo->map[histo->n_bins] = histo->map[bin]; + histo->bin_count[histo->n_bins] += + histo->bin_count[bin];
kernel-shark-qt/src/libkshark-model.c line 524
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ } + + histo->map[bin] = histo->map[bin-n]; + histo->bin_count[bin] = histo->bin_count[bin-n]; + +if (bin == n) +break ; + + --bin; + }
But we can replace the copy again with memmove:
memmove(&histo->map[bin], &histo->map[bin - n], sizeof(histo->map[0]) * n); memmove(&histo->bin_count[bin], &histo->bin_count[bin - n], sizeof(histo->bin_count[0]) * n);
kernel-shark-qt/src/libkshark-model.c line 535
Quoted 11 lines
kernel-shark-qt/src/libkshark-model.c new file +11
-0+ +/* Reset all new bins, including overflow bins. */ +ksmodel_reset_bins (histo,0 , bin); +ksmodel_reset_bins (histo, histo->n_bins, histo->n_bins +1 ); + +/* Set the new Lower Overflow bin */ +ksmodel_set_lower_edge (histo); + +/* Calculate only the content of the new (non-overlapping) bins. */ + bin =0 ; +while (bin < n) {
Again this should be a for loop.
kernel-shark-qt/src/libkshark-model.c line 465
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ksmodel_set_next_bin_edge (histo, bin); + ++bin; + } + +/* +* Set the new Upper Overflow bin and calculate the number of entries +* in each bin. +*/ +ksmodel_set_upper_edge (histo); +ksmodel_set_bin_counts (histo);
Hmm, perhaps replace the ending of this function and the shift forward with a helper function that removes the duplicate code.
Quoted 39 lines
kernel-shark-qt/src/libkshark-model.c new file +39
-0+} + +/** +* @brief Move the time-window of the model to a given location. Recalculate +* the current state of the model. +* @param histo: Input location for the model descriptor. +* @param ts: position in time to be visualized. +*/ +void ksmodel_jump_to (struct kshark_trace_histo *histo,size_t ts) +{ +size_t min, max, range_min; + +if (ts > histo->min && ts < histo->max) { +/* +* The new position is already inside the range. +* Do nothing in this case. +*/ +return ; + } + +/* +* Calculate the new range without changing the size and the number +* of bins. +*/ + min = ts - histo->n_bins * histo->bin_size /2 ; + +/* Make sure that the range does not go outside of the dataset. */ +if (min < histo->data[0 ]->ts) + min = histo->data[0 ]->ts; + + range_min = histo->data[histo->data_size -1 ]->ts - + histo->n_bins * histo->bin_size; + +if (min > range_min) + min = range_min; + + max = min + histo->n_bins * histo->bin_size; + +/* Use the new range to recalculate all bins from scratch. */
kernel-shark-qt/src/libkshark-model.c line 594
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+ksmodel_set_bining (histo, histo->n_bins, min, max); +ksmodel_fill (histo, histo->data, histo->data_size); +} + +/** +* @brief Extend the time-window of the model. Recalculate the current state +* of the model. +* @param histo: Input location for the model descriptor. +* @param r: Scale factor of the zoom-out. +* @param mark: Focus point of the zoom-out.
Comment here that mark < 0 means to zoom in the middle.
Quoted 250 lines
kernel-shark-qt/src/libkshark-model.c new file +250
-0+*/ +void ksmodel_zoom_out (struct kshark_trace_histo *histo, +double r,int mark) +{ +size_t range, min, max, delta_min; +double delta_tot; + +if (!histo->data_size) +return ; + +/* +* If the marker is not set, assume that the focal point of the zoom +* is the center of the range. +*/ +if (mark <0 ) + mark = histo->n_bins /2 ; + +/* +* Calculate the new range of the histo. Use the bin of the marker +* as a focal point for the zoomout. With this the maker will stay +* inside the same bin in the new histo. +*/ + range = histo->max - histo->min; + delta_tot = range * r; + delta_min = delta_tot * mark / histo->n_bins; + + min = histo->min - delta_min; + max = histo->max + (size_t ) delta_tot - delta_min; + +/* Make sure the new range doesn't go outside of the dataset. */ +if (min < histo->data[0 ]->ts) + min = histo->data[0 ]->ts; + +if (max > histo->data[histo->data_size -1 ]->ts) + max = histo->data[histo->data_size -1 ]->ts; + +/* +* Use the new range to recalculate all bins from scratch. Enforce +* "In Range" adjustment of the range of the model, in order to avoid +* slowly drifting outside of the data-set in the case when the very +* first or the very last entry is used as a focal point. +*/ +ksmodel_set_in_range_bining (histo, histo->n_bins, min, max, true); +ksmodel_fill (histo, histo->data, histo->data_size); +} + +/** +* @brief Shrink the time-window of the model. Recalculate the current state +* of the model. +* @param histo: Input location for the model descriptor. +* @param r: Scale factor of the zoom-in. +* @param mark: Focus point of the zoom-in. +*/ +void ksmodel_zoom_in (struct kshark_trace_histo *histo, +double r,int mark) +{ +size_t range, min, max, delta_min; +double delta_tot; + +if (!histo->data_size) +return ; + +/* +* If the marker is not set, assume that the focal point of the zoom +* is the center of the range. +*/ +if (mark <0 ) + mark = histo->n_bins /2 ; + + range = histo->max - histo->min; + +/* Avoid overzooming. */ +if (range < histo->n_bins *4 ) +return ; + +/* +* Calculate the new range of the histo. Use the bin of the marker +* as a focal point for the zoomin. With this the maker will stay +* inside the same bin in the new histo. +*/ + delta_tot = range * r; +if (mark == (int )histo->n_bins -1 ) + delta_min = delta_tot; +else if (mark ==0 ) + delta_min =0 ; +else + delta_min = delta_tot * mark / histo->n_bins; + + min = histo->min + delta_min; + max = histo->max - (size_t ) delta_tot + delta_min; + +/* +* Use the new range to recalculate all bins from scratch. Enforce +* "In Range" adjustment of the range of the model, in order to avoid +* slowly drifting outside of the data-set in the case when the very +* first or the very last entry is used as a focal point. +*/ +ksmodel_set_in_range_bining (histo, histo->n_bins, min, max, true); +ksmodel_fill (histo, histo->data, histo->data_size); +} + +/** +* @brief Get the index of the first entry in a given bin. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @returns Index of the first entry in this bin. If the bin is empty the +* function returns negative error identifier (KS_EMPTY_BIN). +*/ +ssize_t ksmodel_first_index_at_bin (struct kshark_trace_histo *histo,int bin) +{ +if (bin >=0 && bin < (int ) histo->n_bins) +return histo->map[bin]; + +if (bin ==UPPER_OVERFLOW_BIN ) +return histo->map[histo->n_bins]; + +if (bin ==LOWER_OVERFLOW_BIN ) +return histo->map[histo->n_bins +1 ]; + +return KS_EMPTY_BIN ; +} + +/** +* @brief Get the index of the last entry in a given bin. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @returns Index of the last entry in this bin. If the bin is empty the +* function returns negative error identifier (KS_EMPTY_BIN). +*/ +ssize_t ksmodel_last_index_at_bin (struct kshark_trace_histo *histo,int bin) +{ +ssize_t index =ksmodel_first_index_at_bin (histo, bin); +size_t count =ksmodel_bin_count (histo, bin); + +if (index >=0 && count) + index += count -1 ; + +return index; +} + +static bool ksmodel_is_visible (struct kshark_entry *e) +{ +if ((e->visible &KS_GRAPH_VIEW_FILTER_MASK ) && + (e->visible &KS_EVENT_VIEW_FILTER_MASK )) +return true; + +return false; +} + +static struct kshark_entry_request * +ksmodel_entry_front_request_alloc (struct kshark_trace_histo *histo, +int bin,bool vis_only, +matching_condition_func func,int val) +{ +struct kshark_entry_request *req; +size_t first, n; + +/* Get the number of entries in this bin. */ + n =ksmodel_bin_count (histo, bin); +if (!n) +return NULL ; + + first =ksmodel_first_index_at_bin (histo, bin); + + req =kshark_entry_request_alloc (first, n, + func, val, + vis_only,KS_GRAPH_VIEW_FILTER_MASK ); + +return req; +} + +static struct kshark_entry_request * +ksmodel_entry_back_request_alloc (struct kshark_trace_histo *histo, +int bin,bool vis_only, +matching_condition_func func,int val) +{ +struct kshark_entry_request *req; +size_t first, n; + +/* Get the number of entries in this bin. */ + n =ksmodel_bin_count (histo, bin); +if (!n) +return NULL ; + + first =ksmodel_last_index_at_bin (histo, bin); + + req =kshark_entry_request_alloc (first, n, + func, val, + vis_only,KS_GRAPH_VIEW_FILTER_MASK ); + +return req; +} + +/** +* @brief Get the index of the first entry from a given Cpu in a given bin. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @param cpu: Cpu Id. +* @returns Index of the first entry from a given Cpu in this bin. +*/ +ssize_t ksmodel_first_index_at_cpu (struct kshark_trace_histo *histo, +int bin,int cpu) +{ +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); + +for (i = first; i < first + n; ++i) { +if (histo->data[i]->cpu == cpu) { +if (ksmodel_is_visible (histo->data[i])) +return i; +else + not_found =KS_FILTERED_BIN ; + } + } + +return not_found; +} + +/** +* @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, +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); + +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 ; + } + } +
kernel-shark-qt/src/libkshark-model.c line 854
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+return not_found; +} + +/** +* @brief In a given bin, start from the front end of the bin and go towards +* the back end, searching for an entry satisfying the Matching +* condition defined by a Matching condition function. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @param vis_only: If true, a visible entry is requested.
So if vis_only is true, and the next entry that matches the condition is not visible, we simply return the dummy?
Quoted 28 lines
kernel-shark-qt/src/libkshark-model.c new file +28
-0+* @param func: Matching condition function. +* @param val: Matching condition value, used by the Matching condition +* function. +* @param index: Optional output location for the index of the requested +* entry inside the array. +* @returns Pointer ot a kshark_entry, if an entry has been found. Else NULL. +*/ +const struct kshark_entry * +ksmodel_get_entry_front (struct kshark_trace_histo *histo, +int bin,bool vis_only, +matching_condition_func func,int val, +ssize_t *index) +{ +struct kshark_entry_request *req; +const struct kshark_entry *entry; + +if (index) + *index =KS_EMPTY_BIN ; + +/* Set the position at the beginning of the bin and go forward. */ + req =ksmodel_entry_front_request_alloc (histo, bin, vis_only, + func, val); +if (!req) +return NULL ; + + entry =kshark_get_entry_front (req, histo->data, index); +free (req); +
kernel-shark-qt/src/libkshark-model.c line 892
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+return entry; +} + +/** +* @brief In a given bin, start from the back end of the bin and go towards +* the front end, searching for an entry satisfying the Matching +* condition defined by a Matching condition function. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @param vis_only: If true, a visible entry is requested.
Same here?
kernel-shark-qt/src/libkshark-model.c line 860
Quoted 6 lines
kernel-shark-qt/src/libkshark-model.c new file +6
-0+* @param func: Matching condition function. +* @param val: Matching condition value, used by the Matching condition +* function. +* @param index: Optional output location for the index of the requested +* entry inside the array. +* @returns Pointer ot a kshark_entry, if an entry has been found. Else NULL.
Should document about the dummy. And that NULL can be a warning.
Quoted 23 lines
kernel-shark-qt/src/libkshark-model.c new file +23
-0+*/ +const struct kshark_entry * +ksmodel_get_entry_back (struct kshark_trace_histo *histo, +int bin,bool vis_only, +matching_condition_func func,int val, +ssize_t *index) +{ +struct kshark_entry_request *req; +const struct kshark_entry *entry; + +if (index) + *index =KS_EMPTY_BIN ; + +/* Set the position at the end of the bin and go backwards. */ + req =ksmodel_entry_back_request_alloc (histo, bin, vis_only, + func, val); +if (!req) +return NULL ; + + entry =kshark_get_entry_back (req, histo->data, index); +free (req); + +return entry;
kernel-shark-qt/src/libkshark-model.c line 931
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+} + +static int ksmodel_get_entry_pid (const struct kshark_entry *entry) +{ +if (!entry) { +/* No data has been found. */ +return KS_EMPTY_BIN ; + } + +if (!entry->visible) {
As so you have to return a dummy, not (-1), because this can be the dummy.
OK, that's all the review I can do today. I skimmed the rest of the patch but didn't see anything that stood out, but I didn't look in too much detail. I'll try to do more tomorrow.
-- Steve
Quoted 346 lines
kernel-shark-qt/src/libkshark-model.c new file +202
-0+/* Some data has been found, but it is filtered-out. */ +return KS_FILTERED_BIN ; + } + +return entry->pid; +} + +/** +* @brief In a given bin, start from the front end of the bin and go towards +* the back end, searching for an entry from a given Cpu. Return +* the Process Id of the task of the entry found. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @param cpu: Cpu Id. +* @param vis_only: If true, a visible entry is requested. +* @param index: Optional output location for the index of the requested +* entry inside the array. +* @returns Process Id of the task if an entry has been found. Else a negative +* Identifier (KS_EMPTY_BIN or KS_FILTERED_BIN). +*/ +int ksmodel_get_pid_front (struct kshark_trace_histo *histo, +int bin,int cpu,bool vis_only, +ssize_t *index) +{ +const struct kshark_entry *entry; + + entry =ksmodel_get_entry_front (histo, bin, vis_only, + kshark_check_cpu, cpu, + index); +return ksmodel_get_entry_pid (entry); +} + +/** +* @brief In a given bin, start from the back end of the bin and go towards +* the front end, searching for an entry from a given Cpu. Return +* the Process Id of the task of the entry found. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @param cpu: Cpu Id. +* @param vis_only: If true, a visible entry is requested. +* @param index: Optional output location for the index of the requested +* entry inside the array. +* @returns Process Id of the task if an entry has been found. Else a negative +* Identifier (KS_EMPTY_BIN or KS_FILTERED_BIN). +*/ +int ksmodel_get_pid_back (struct kshark_trace_histo *histo, +int bin,int cpu,bool vis_only, +ssize_t *index) +{ +const struct kshark_entry *entry; + + entry =ksmodel_get_entry_back (histo, bin, vis_only, + kshark_check_cpu, cpu, + index); + +return ksmodel_get_entry_pid (entry); +} + +static int ksmodel_get_entry_cpu (const struct kshark_entry *entry) +{ +if (!entry) { +/* No data has been found. */ +return KS_EMPTY_BIN ; + } + +if (!entry->visible) { +/* Some data has been found, but it is filtered-out. */ +return KS_FILTERED_BIN ; + } + +return entry->cpu; +} + +/** +* @brief Get the Cpu Id 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. +* @param vis_only: If true, a visible entry is requested. +* @param index: Optional output location for the index of the requested +* entry inside the array. +* @returns Cpu Id of the first entry from a given Task in this bin. +*/ +int ksmodel_get_cpu (struct kshark_trace_histo *histo, +int bin,int pid,bool vis_only, +ssize_t *index) +{ +struct kshark_entry_request *req; +const struct kshark_entry *entry; +size_t n; + +if (index) + *index =KS_EMPTY_BIN ; + +/* Get the number of entries in this bin. */ + n =ksmodel_bin_count (histo, bin); +if (!n) +return KS_EMPTY_BIN ; + +/* Create an entry request but keep the starting position unset. */ + req =kshark_entry_request_alloc (0 , n, + kshark_check_pid, pid, + vis_only,KS_GRAPH_VIEW_FILTER_MASK ); + +if (bin ==UPPER_OVERFLOW_BIN ) { +/* +* Set the position at the end of the Lower Overflow bin and +* go backwards. +*/ + req->first =ksmodel_bin_count (histo, bin) -1 ; + entry =kshark_get_entry_back (req, histo->data, index); + }else { +/* +* Set the position at the beginning of the bin and go +* forward. +*/ + req->first =ksmodel_first_index_at_bin (histo, bin); + entry =kshark_get_entry_front (req, histo->data, index); + } + +free (req); + +return ksmodel_get_entry_cpu (entry); +} + +/** +* @brief Check if a visible entry from a given Cpu exist in this bin. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @param cpu: Cpu Id. +* @param index: Optional output location for the index of the requested +* entry inside the array. +* @returns True, if a visible entry from the Cpu exists in this bin. +* Else false. +*/ +bool ksmodel_cpu_visible_event_exist (struct kshark_trace_histo *histo, +int bin,int cpu,ssize_t *index) +{ +struct kshark_entry_request *req; +const struct kshark_entry *entry; + +if (index) + *index =KS_EMPTY_BIN ; + +/* Set the position at the beginning of the bin and go forward. */ + req =ksmodel_entry_front_request_alloc (histo, + bin, true, + kshark_check_cpu, cpu); +if (!req) +return false; + + req->vis_mask =KS_EVENT_VIEW_FILTER_MASK ; + + entry =kshark_get_entry_front (req, histo->data, index); +free (req); + +if (!entry || !entry->visible) { +/* No visible entry has been found. */ +return false; + } + +return true; +} + +/** +* @brief Check if a visible entry from a given Task exist in this bin. +* @param histo: Input location for the model descriptor. +* @param bin: Bin id. +* @param pid: Process Id of the task. +* @param index: Optional output location for the index of the requested +* entry inside the array. +* @returns True, if a visible entry from the task exists in this bin. +* Else false. +*/ +bool ksmodel_task_visible_event_exist (struct kshark_trace_histo *histo, +int bin,int pid,ssize_t *index) +{ +struct kshark_entry_request *req; +const struct kshark_entry *entry; + +if (index) + *index =KS_EMPTY_BIN ; + +/* Set the position at the beginning of the bin and go forward. */ + req =ksmodel_entry_front_request_alloc (histo, + bin, true, + kshark_check_pid, pid); +if (!req) +return false; + + req->vis_mask =KS_EVENT_VIEW_FILTER_MASK ; + + entry =kshark_get_entry_front (req, histo->data, index); +free (req); + +if (!entry || !entry->visible) { +/* No visible entry has been found. */ +return false; + } + +return true; +}kernel-shark-qt/src/libkshark-model.h new file +138
-0@@ -0,0 +1,138 @@ +/* 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. */ +enum OverflowBin { +/** Identifier of the Upper Overflow Bin. */ +UPPER_OVERFLOW_BIN =-1 , + +/** Identifier of the Lower Overflow Bin. */ +LOWER_OVERFLOW_BIN =-2 , +}; + +/** Structure describing the current state of the visualization model. */ +struct kshark_trace_histo { +/** Trace data. */ +struct kshark_entry **data; + +/** The size of the data. */ +size_t data_size; + +/** The index of the first entry in each bin. */ +ssize_t *map; + +/** Number of entries in each bin. */ +size_t *bin_count; + +/** Lower edge of the time-window to be visualized. */ +uint64_t min; + +/** Upper edge of the time-window to be visualized. */ +uint64_t max; + +/** The size of the bins. */ +uint64_t bin_size; + +/** Number of bins. */ +size_t n_bins; +}; + +void ksmodel_init (struct kshark_trace_histo *histo); + +void ksmodel_clear (struct kshark_trace_histo *histo); + +void ksmodel_set_bining (struct kshark_trace_histo *histo, +size_t n,uint64_t min,uint64_t max); + +void ksmodel_fill (struct kshark_trace_histo *histo, +struct kshark_entry **data,size_t n); + +size_t ksmodel_bin_count (struct kshark_trace_histo *histo,int bin); + +void ksmodel_shift_forward (struct kshark_trace_histo *histo,size_t n); + +void ksmodel_shift_backward (struct kshark_trace_histo *histo,size_t n); + +void ksmodel_jump_to (struct kshark_trace_histo *histo,size_t ts); + +void ksmodel_zoom_out (struct kshark_trace_histo *histo, +double r,int mark); + +void ksmodel_zoom_in (struct kshark_trace_histo *histo, +double r,int mark); + +ssize_t ksmodel_first_index_at_bin (struct kshark_trace_histo *histo,int bin); + +ssize_t ksmodel_last_index_at_bin (struct kshark_trace_histo *histo,int bin); + +ssize_t ksmodel_first_index_at_cpu (struct kshark_trace_histo *histo, +int bin,int cpu); + +ssize_t ksmodel_first_index_at_pid (struct kshark_trace_histo *histo, +int bin,int pid); + +const struct kshark_entry * +ksmodel_get_entry_front (struct kshark_trace_histo *histo, +int bin,bool vis_only, +matching_condition_func func,int val, +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, +ssize_t *index); + +int ksmodel_get_pid_front (struct kshark_trace_histo *histo, +int bin,int cpu,bool vis_only, +ssize_t *index); + +int ksmodel_get_pid_back (struct kshark_trace_histo *histo, +int bin,int cpu,bool vis_only, +ssize_t *index); + +int ksmodel_get_cpu (struct kshark_trace_histo *histo, +int bin,int pid,bool vis_only, +ssize_t *index); + +bool ksmodel_cpu_visible_event_exist (struct kshark_trace_histo *histo, +int bin,int cpu,ssize_t *index); + +bool ksmodel_task_visible_event_exist (struct kshark_trace_histo *histo, +int bin,int pid,ssize_t *index); + +static inline double ksmodel_bin_time (struct kshark_trace_histo *histo, +int bin) +{ +return (histo->min + bin*histo->bin_size) *1e-9 ; +} + +static inline uint64_t ksmodel_bin_ts (struct kshark_trace_histo *histo, +int bin) +{ +return (histo->min + bin*histo->bin_size); +} + +#ifdef __cplusplus +} +#endif // __cplusplus + +#endif
Re: [PATCH 2/6] kernel-shark-qt: Introduce the visualization model used by the Qt-based KS
In reply to Yordan Karadzhov (VMware)On Wed, 11 Jul 2018 16:38:10 +0300
"Yordan Karadzhov (VMware)" <[email protected]> wrote:
I just noticed these helper functions:
kernel-shark-qt/src/libkshark-model.h line 133
Quoted 12 lines
kernel-shark-qt/src/libkshark-model.h new file +12
-0+static inline double ksmodel_bin_time (struct kshark_trace_histo *histo, +int bin) +{ +return (histo->min + bin*histo->bin_size) *1e-9 ; +} + +static inline uint64_t ksmodel_bin_ts (struct kshark_trace_histo *histo, +int bin) +{ +return (histo->min + bin*histo->bin_size); +} +
Also, add a space around the '*' between 'bin' and 'histo'.
Quoted 29 lines
kernel-shark-qt/src/libkshark-model.c new file +29
-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). +*/ +size_t row =kshark_find_entry_by_time (histo->min, + histo->data, +0 , + histo->data_size -1 ); + +if (row !=0 ) { +/* +* 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[histo->n_bins +1 ] =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[histo->n_bins +1 ] = row; + }else { +/* +* Lower Overflow bin is empty. The number of entries is
kernel-shark-qt/src/libkshark-model.c line 196
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+* already set to "0". +*/ + histo->map[histo->n_bins +1 ] =KS_EMPTY_BIN ; + } + +/* +* Now check if the first entry inside the range falls into the +* first bin. +*/ +if (histo->data[row]->ts < histo->min + histo->bin_size) {
Why not:
if (histo->data[row]->ts < ksmodel_bin_ts(histo, 1)) {Quoted 41 lines
kernel-shark-qt/src/libkshark-model.c new file +41
-0+/* +* It is inside the fisrs bin. Set the beginning +* of the fisrs bin. +*/ + histo->map[0 ] = row; + }else { +/* The fisrs 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). +*/ +size_t row =kshark_find_entry_by_time (histo->max, + histo->data, +0 , + histo->data_size -1 ); + +if (row < histo->data_size -1 || + (row == histo->data_size -1 && + histo->data[histo->data_size -1 ]->ts > histo->max)) { +/* +* The Upper Overflow bin contains data. Set its beginning +* and the number of entries. +*/ + histo->map[histo->n_bins] = row; + histo->bin_count[histo->n_bins] = histo->data_size - row; + }else { +/* +* Upper Overflow bin is empty. The number of entries is +* already set to "0". +*/ + histo->map[histo->n_bins] =KS_EMPTY_BIN ; + } +
kernel-shark-qt/src/libkshark-model.c line 247
Quoted 10 lines
kernel-shark-qt/src/libkshark-model.c new file +10
-0+return row; +} + +static void ksmodel_set_next_bin_edge (struct kshark_trace_histo *histo, +size_t bin) +{ +size_t time, row, next_bin = bin +1 ; + +/* Calculate the beginning of the next bin. */ + time = histo->min + next_bin * histo->bin_size;
time = ksmodel_bin_ts(histo, next_bin);
-- Steve
Quoted 28 lines
kernel-shark-qt/src/libkshark-model.c new file +28
-0+ +/* +* Find the index of the first entry inside +* the next bin (timestamp > time). +*/ + row =kshark_find_entry_by_time (time,histo->data,0 , + histo->data_size -1 ); + +/* +* The timestamp of the very last entry of the dataset can be exactly +* equal to the value of the upper edge of the range. This is very +* likely to happen when we use ksmodel_set_in_range_bining(). In this +* case we have to increase the size of the very last bin in order to +* make sure that the last entry of the dataset will fall into it. +*/ +if (next_bin == histo->n_bins -1 ) + ++time; + +if (histo->data[row]->ts >= time + histo->bin_size) { +/* The bin is empty. */ + histo->map[next_bin] =KS_EMPTY_BIN ; +return ; + } + +/* Set the index of the first entry. */ + histo->map[next_bin] = row; +} +
PATCH 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
Re: [PATCH 3/6] kernel-shark-qt: Add an example showing how to manipulate the Vis. model.
Quoted 60 lines · On Wed, 11 Jul 2018 16:38:11 +0300 "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.
Signed-off-by Yordan Karadzhov (VMware) <[email protected]>--- 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.ckernel-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 +31
-0@@ -0,0 +1,155 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Copyright (C) 2018 VMware Inc, Yordan Karadzhov <[email protected]> +*/ + +// C +#include <stdio.h> +#include <stdlib.h> + +// KernelShark +#include "libkshark.h" +#include "libkshark-model.h" + +#define N_BINS 5 + +const char *default_file ="trace.dat" ; + +void dump_bin (struct kshark_trace_histo *histo,int bin, +const char *type,int val) +{ +const struct kshark_entry *e_front, *e_back; +char *entry_str; +ssize_t i_front, i_back; + +printf ("bin %i {\n" , bin); +if (strcmp (type,"cpu" ) ==0 ) { + e_front =ksmodel_get_entry_front (histo, bin, true, + kshark_check_cpu, val, + &i_front); +
kernel-shark-qt/examples/datahisto.c line 41
Quoted 10 lines
kernel-shark-qt/examples/datahisto.c new file +10
-0+ e_back =ksmodel_get_entry_back (histo, bin, true, + kshark_check_cpu, val, + &i_back); + }else if (strcmp (type,"task" ) ==0 ) { + e_front =ksmodel_get_entry_front (histo, bin, true, + kshark_check_pid, val, + &i_front); + + e_back = ksmodel_get_entry_back(histo, bin, true, + kshark_check_pid, val,
Yeah, I think we need to rename the functions to:
kshark_match_cpu() and kshark_match_pid()
Quoted 30 lines
kernel-shark-qt/examples/datahisto.c new file +30
-0+ &i_back); + }else { + i_front =ksmodel_first_index_at_bin (histo, bin); + e_front = histo->data[i_front]; + + i_back =ksmodel_last_index_at_bin (histo, bin); + e_back = histo->data[i_back]; + } + +if (i_front ==KS_EMPTY_BIN ) { +puts ("EMPTY BIN" ); + }else { + entry_str =kshark_dump_entry (e_front); +printf ("%li -> %s\n" , i_front, entry_str); +free (entry_str); + + entry_str =kshark_dump_entry (e_back); +printf ("%li -> %s\n" , i_back, entry_str); +free (entry_str); + } + +puts ("}\n" ); +} + +void dump_histo (struct kshark_trace_histo *histo,const char *type,int val) +{ +size_t bin; + +for (bin =0 ; bin < histo->n_bins; ++bin) +dump_bin (histo, bin, type, val);
kernel-shark-qt/examples/datahisto.c line 81
Quoted 10 lines
kernel-shark-qt/examples/datahisto.c new file +10
-0+} + +int main (int argc,char **argv) +{ +struct kshark_context *kshark_ctx; +struct kshark_entry **data =NULL ; +struct kshark_trace_histo histo; +size_t i, n_rows, n_tasks; +bool status; +int *pids;
See how nice the upside-down-xmas tree format looks :-)
The rest of this patch looks fine.
-- Steve
Quoted 74 lines
kernel-shark-qt/examples/datahisto.c new file +74
-0+ +/* Create a new kshark session. */ + kshark_ctx =NULL ; +if (!kshark_instance (&kshark_ctx)) +return 1 ; + +/* Open a trace data file produced by trace-cmd. */ +if (argc >1 ) + status =kshark_open (kshark_ctx, argv[1 ]); +else + status =kshark_open (kshark_ctx, default_file); + +if (!status) { +kshark_free (kshark_ctx); +return 1 ; + } + +/* Load the content of the file into an array of entries. */ + n_rows =kshark_load_data_entries (kshark_ctx, &data); + +/* Get a list of all tasks. */ + n_tasks =kshark_get_task_pids (kshark_ctx, &pids); + +/* Initialize the Visualization Model. */ +ksmodel_init (&histo); +ksmodel_set_bining (&histo,N_BINS , data[0 ]->ts, + data[n_rows -1 ]->ts); + +/* Fill the model with data and calculate its state. */ +ksmodel_fill (&histo, data, n_rows); + +/* Dump the raw bins. */ +dump_histo (&histo,"" ,0 ); + +puts ("\n...\n\n" ); + +/* +* Change the state of the model. Do 50% Zoom-In and dump only CPU 0. +*/ +ksmodel_zoom_in (&histo,.50 ,-1 ); +dump_histo (&histo,"cpu" ,0 ); + +puts ("\n...\n\n" ); + +/* Shift forward by two bins and this time dump only CPU 1. */ +ksmodel_shift_forward (&histo,2 ); +dump_histo (&histo,"cpu" ,1 ); + +puts ("\n...\n\n" ); + +/* +* Do 10% Zoom-Out, using the last bin as a focal point. Dump the last +* Task. +*/ +ksmodel_zoom_out (&histo,.10 ,N_BINS -1 ); +dump_histo (&histo,"task" , pids[n_tasks -1 ]); + +/* Reset (clear) the model. */ +ksmodel_clear (&histo); + +/* Free the memory. */ +for (i =0 ; i < n_rows; ++i) +free (data[i]); + +free (data); + +/* Close the file. */ +kshark_close (kshark_ctx); + +/* Close the session. */ +kshark_free (kshark_ctx); + +return 0 ; +}
PATCH 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 | 719 +++++++++++++++++++++ kernel-shark-qt/src/libkshark.c | 16 + kernel-shark-qt/src/libkshark.h | 79 +++ 4 files changed, 816 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 +719 -0
719 lines not on this page · raw message
kernel-shark-qt/src/libkshark.c +16 -0
@@ -1038,6 +1038,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;
@@ -1048,6 +1049,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 ,/* visible */ 0x00 ,
kernel-shark-qt/src/libkshark.h +79 -0
103 lines not on this page · raw message
Signature · 1 line
2.17.1
Re: [PATCH 4/6] kernel-shark-qt: Define Data collections
Quoted 10 lines · On Wed, 11 Jul 2018 16:38:12 +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.
Hmm, I'm going to have to come back and break that up a bit. What you wrote is good, but it also is written in a point of view of someone that is very deep in what is being done. I'll come back and try to make it a bit more understandable for the layman.
Quoted 46 lines
Signed-off-by Yordan Karadzhov (VMware) <[email protected]>--- kernel-shark-qt/src/CMakeLists.txt | 3 +- kernel-shark-qt/src/libkshark-collection.c | 719 +++++++++++++++++++++ kernel-shark-qt/src/libkshark.c | 16 + kernel-shark-qt/src/libkshark.h | 79 +++ 4 files changed, 816 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 +16
-0@@ -0,0 +1,719 @@ +// 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> +
kernel-shark-qt/src/libkshark-collection.c line 26
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+// KernelShark +#include "libkshark.h" + +/* Quiet warnings over documenting simple structures */ +//! @cond Doxygen_Suppress + +enum collection_point_type { +COLLECTION_RESUME , +COLLECTION_BREAK , +COLLECTION_IGNORE ,
I would make COLLECTION_IGNORE be the first one. As that would make it zero. I'm guessing a zero value for IGNORE could allow the compiler to optimize it. And to make it a point that IGNORE is zero, do:
enum collection_point_type {
COLLECTION_IGNORE = 0,
COLLECTION_RESUME,
COLLECTION_BREAK,
};
As checking for zero or not zero is usually faster than checking for 2 or not 2 (Shakespeare is slow ;-)
Quoted 8 lines
kernel-shark-qt/src/libkshark-collection.c new file +8
-0+}; + +#define LAST_BIN -3 + +struct entry_list { +struct entry_list *next; +size_t index; +uint8_t type;
kernel-shark-qt/src/libkshark-collection.c line 44
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+}; + +//! @endcond + +static void collection_add_entry (struct entry_list **list, +size_t i,uint8_t type) +{ +if ((*list)->type !=COLLECTION_IGNORE ) { + (*list)->next =malloc (sizeof (**list)); +assert ((*list)->next !=NULL );
Hmm, I don't like asserts. have this function return success or fail. Of course the callers will need to test the result.
kernel-shark-qt/src/libkshark-collection.c line 49
Quoted 5 lines
kernel-shark-qt/src/libkshark-collection.c new file +5
-0+ *list = (*list)->next; + } + + (*list)->index = i; + (*list)->type = type;
Hmm, I think it would make the function a bit more readable by adding a helper variable.
struct entry_list *entry = *list;
if (entry->type != COLLECTION_IGNORE) {
entry->next = malloc(sizeof(*entry));
if (!entry->next)
return false;
entry = entry->next;
*list = entry;
}
entry->index = i;
entry->type = type;
return true;kernel-shark-qt/src/libkshark-collection.c line 61
Quoted 12 lines
kernel-shark-qt/src/libkshark-collection.c new file +12
-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) +{ +struct entry_list *col_list =malloc (sizeof (*col_list));
Need to test if this succeeds.
Quoted 4 lines
kernel-shark-qt/src/libkshark-collection.c new file +4
-0+struct kshark_entry *last_vis_entry =NULL ; +struct kshark_entry_collection *col_ptr; +struct entry_list *temp = col_list; +size_t resume_count =0 , break_count =0 ;
kernel-shark-qt/src/libkshark-collection.c line 75
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+size_t i, j, end, last_added =0 ; +bool good = false; + +if (margin !=0 ) { + temp->index = first; + temp->type =COLLECTION_RESUME ; + ++resume_count; + +collection_add_entry (&temp, first + margin -1 ,COLLECTION_BREAK ); + ++break_count;
The above definitely needs some comments about what is happening. I have no clue.
Quoted 23 lines
kernel-shark-qt/src/libkshark-collection.c new file +23
-0+ }else { + temp->type =COLLECTION_IGNORE ; + } + + end = first + n_rows - margin; +for (i = first + margin; i < end; ++i) { +if (!good && !cond (kshark_ctx, data[i], val)) { +/* +* The entry is irrelevant for this collection. +* Do nothing. +*/ +continue ; + } + +if (!good &&cond (kshark_ctx, data[i], val)) { +/* +* Resume the collection here. Add some margin data +* in front of the data of interest. +*/ + good = true; +if (last_added ==0 || last_added < i - margin) { +collection_add_entry (&temp, i - margin, +COLLECTION_RESUME );
kernel-shark-qt/src/libkshark-collection.c line 108
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ ++resume_count; + }else { +/* Ignore the last collection Brack point. */ + temp->type =COLLECTION_IGNORE ; + --break_count; + } + }else if (good && +cond (kshark_ctx, data[i], val) && + data[i]->next && + !cond (kshark_ctx, data[i]->next, val)) {
The above three conditionals show that cond(kshark_ctx, data[i], val) is always called. And if it fails, we do nothing. Let's change the above to:
if (!cond(kshark_ctx, data[i], val))
continue;
if (!good) {
good = true;
[...]
} else if (data[i]->next &&
!cond(kshark_ctx, data[i]->next, val)) {
[...]Makes the code cleaner and more efficient as we only call the cond() function once.
Quoted 4 lines
kernel-shark-qt/src/libkshark-collection.c new file +4
-0+/* +* Brack the collection here. Add some margin data +* after the data of interest. +*/
kernel-shark-qt/src/libkshark-collection.c line 122
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ good = false; + last_vis_entry = data[i]; + +/* Keep adding entries until the "next" record. */ + j = i; +do { + ++j; +if (j == end) +break ; + }while (last_vis_entry->next != data[j]);
Hmm, the above could be converted into:
for (j = i + 1; j != end && last_vis_entry->next != data[j]; j++) ;
kernel-shark-qt/src/libkshark-collection.c line 125
Quoted 3 lines
kernel-shark-qt/src/libkshark-collection.c new file +3
-0+ +/* +* If the number of added entryes is smaller then the
entries is smaller than
Quoted 23 lines
kernel-shark-qt/src/libkshark-collection.c new file +23
-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) { +collection_add_entry (&temp, i,COLLECTION_BREAK ); + ++break_count; + } + +if (margin !=0 ) { +collection_add_entry (&temp, first + n_rows - margin, +COLLECTION_RESUME ); +
kernel-shark-qt/src/libkshark-collection.c line 158
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ ++resume_count; + +collection_add_entry (&temp, first + n_rows, +COLLECTION_BREAK ); + + ++break_count; + } + +/* Create the collection. */ + col_ptr =malloc (sizeof (*col_ptr));
Need to check if col_ptr succeeds in allocation.
kernel-shark-qt/src/libkshark-collection.c line 166
Quoted 8 lines
kernel-shark-qt/src/libkshark-collection.c new file +8
-0+ col_ptr->next =NULL ; + + col_ptr->resume_points =calloc (resume_count, +sizeof (*col_ptr->resume_points)); + + col_ptr->break_points =calloc (break_count, +sizeof (*col_ptr->break_points)); +
As well as these.
kernel-shark-qt/src/libkshark-collection.c line 174
Quoted 8 lines
kernel-shark-qt/src/libkshark-collection.c new file +8
-0+ col_ptr->cond = cond; + col_ptr->val = val; + +/* +* If everything is OK, we must have pairs of COLLECTION_RESUME +* and COLLECTION_BREAK points. +*/ +assert (break_count == resume_count);
I guess this assert is OK.
Quoted 32 lines
kernel-shark-qt/src/libkshark-collection.c new file +32
-0+ 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; +} + +static ssize_t +map_collection_index_from_source (const struct kshark_entry_collection *col, +size_t source_index) +{ +size_t l, h, mid; + +if (!col->size || source_index > col->break_points[col->size -1 ]) +return KS_EMPTY_BIN ; + + l =0 ; + h = col->size -1 ; +if (source_index < col->resume_points[0 ]) +return l; +
kernel-shark-qt/src/libkshark-collection.c line 216
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+if (source_index > col->resume_points[col->size -1 ]) +return LAST_BIN ; + +while (h - l >1 ) { + mid = (l + h) /2 ; +if (source_index > col->resume_points[mid]) + l = mid; +else + h = mid; + }
Since we do a binary search a lot, perhaps we should have a macro:
#define BSEARCH(h, l, cond) \
({ \
size_t mid; \
\
while (h - l > 1) { \
mid = (l + h) / 2; \
if (cond) \
l = mid; \
else \
h = mid; \
} \
h; \
})Then you can replace all of them with:
h = BSEARCH(h, l, source_index > col->resume_points[mid]);
And not repeat doing this.
kernel-shark-qt/src/libkshark-collection.c line 223
Quoted 7 lines
kernel-shark-qt/src/libkshark-collection.c new file +7
-0+ +return h; +} + +static int +map_collection_back_request (const struct kshark_entry_collection *col, +struct kshark_entry_request **req)
Even though this is a static function, it would be good to have a comment explaining what it is doing. It doesn't need to be in doxygen format. But a comment before the function that explains what the relation of the requests to the collection is and what is happening here. Because it's not obvious.
Quoted 73 lines
kernel-shark-qt/src/libkshark-collection.c new file +73
-0+{ +struct kshark_entry_request *req_tmp = *req; +size_t req_end = req_tmp->first - req_tmp->n +1 ; +ssize_t col_index; +int req_count; + +/* +* 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); + +/* +* The value of "col_index" is ambiguous. Deal with all possible +* cases. +*/ +if (col_index ==KS_EMPTY_BIN ) { +/* +* No overlap between the request and the collection. +* Do nothing. +*/ +kshark_free_entry_request (*req); + *req =NULL ; +return 0 ; + } + +if (col_index ==0 ) { +if (req_tmp->first == col->resume_points[col_index]) { +/* +* This is a special case. Because this is Back +* Request, if the beginning of this request is at +* the Resume Point of the interval, then there is +* only one possible entry, to look into. +*/ + req_tmp->n =1 ; +return 1 ; + } + +/* +* No overlap between the request and the collection. +* Do nothing. +*/ +kshark_free_entry_request (*req); + *req =NULL ; +return 0 ; + }else if (col_index >0 ) { +/* +* This is Back Request, so the "col_index" interval of the +* collection is guaranteed to be outside the requested data, +* except in one special case. +*/ +if (req_tmp->first == col->resume_points[col_index]) { +/* +* We still have to check the very first entry of the +* "col_index" interval. +*/ +if (req_end > col->break_points[col_index -1 ]) { +/* +* There is only one possible entry, to look +* into. +*/ + req_tmp->n =1 ; +return 1 ; + } + }else { +/* Move to the previous interval of the collection. */ + --col_index; + +if (req_tmp->first > col->break_points[col_index]) { + req_tmp->first = col->break_points[col_index]; + } + } + }else if (col_index ==LAST_BIN ) {
kernel-shark-qt/src/libkshark-collection.c line 306
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ col_index = col->size -1 ; + } + +/* +* Now loop over the intervals of the collection going backwords +* and create a separate request for each of those interest. +*/ + req_count =1 ; +while (req_end <= col->break_points[col_index] && + col_index >=0 ) {
The col_index >= 0 should be the first condition, otherwise it is possible that we reference bad memory with indirection in the condition before it.
Quoted 14 lines
kernel-shark-qt/src/libkshark-collection.c new file +14
-0+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 this +* collection interval (col_index). Close the collection +* request at the end of the interval and move to the next
kernel-shark-qt/src/libkshark-collection.c line 330
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+* interval. 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 berofe
before
Quoted 93 lines
kernel-shark-qt/src/libkshark-collection.c new file +93
-0+* the next collection interval. Stop here. +*/ +break ; + } + +if (col_index >0 ) { +/* Make a new request. */ + req_tmp->next =malloc (sizeof (*req_tmp->next)); + req_tmp = req_tmp->next; + req_tmp->next =NULL ; + req_tmp->first = col->break_points[col_index]; + ++req_count; + } + } + +return req_count; +} + +static int +map_collection_front_request (const struct kshark_entry_collection *col, +struct kshark_entry_request **req) +{ +struct kshark_entry_request *req_tmp = *req; +size_t req_first, req_end; +ssize_t col_index; +int req_count; + +/* +* Find the first Resume Point of the collection which is equal or +* greater than the first index of this request. +*/ + req_end = req_tmp->first + req_tmp->n -1 ; + col_index =map_collection_index_from_source (col, req_tmp->first); + +/* +* The value of "col_index" is ambiguous. Deal with all possible +* cases. +*/ +if (col_index ==KS_EMPTY_BIN ) { +/* +* No overlap between the request and the collection. +* Do nothing. +*/ +kshark_free_entry_request (*req); + *req =NULL ; +return 0 ; + } + +if (col_index ==0 ) { +if (col->resume_points[col_index] > req_end) { +/* +* No overlap between the request and the collection. +* Do nothing. +*/ +kshark_free_entry_request (*req); + *req =NULL ; +return 0 ; + } + +/* +* The request overlaps with the "col_index" interval of the +* collection. Start from here, using the Resume Point of +* the interval as begining of the request. +*/ + req_tmp->first = col->resume_points[col_index]; + }else if (col_index >0 ) { +if (req_end < col->resume_points[col_index] && + req_tmp->first > col->break_points[col_index -1 ]) { +/* +* No overlap between the request and the collection. +* Do nothing. +*/ +kshark_free_entry_request (*req); + *req =NULL ; +return 0 ; + } + +if (req_tmp->first <= col->break_points[col_index -1 ]) { +/* +* The begining of this request is inside the previous +* interval of the collection. Start from there and +* keep the original begining point. +*/ + --col_index; + }else { +/* +* The request overlaps with the "col_index" interval +* of the collection. Start from here, using the Resume +* Point of the interval as begining of the request. +*/ + req_tmp->first = col->resume_points[col_index]; + } + }else if (col_index ==LAST_BIN ) {
kernel-shark-qt/src/libkshark-collection.c line 433
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ col_index = col->size -1 ; + } + +/* +* Now loop over the intervals of the collection going forwards +* and create a separate request for each of those interest. +*/ + req_count =1 ; +while (req_end >= col->resume_points[col_index] && + col_index < col->size) {
Again, the "col_index < col->size" needs to be first.
Quoted 14 lines
kernel-shark-qt/src/libkshark-collection.c new file +14
-0+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
kernel-shark-qt/src/libkshark-collection.c line 457
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+* 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 berofe
cut and pasted "berofe"
Quoted 22 lines
kernel-shark-qt/src/libkshark-collection.c new file +22
-0+* the begining 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 489
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+return req_count; +} + +/** +* @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 Data request.
req appears to be modified by this function. This should be documented here to what is happening.
Quoted 43 lines
kernel-shark-qt/src/libkshark-collection.c new file +43
-0+* @param data: Intput location for the trace data. +* @param col: Intput location for the Data collection. +* @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; + } +
kernel-shark-qt/src/libkshark-collection.c line 542
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+return entry; +} + +/** +* @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). +* The search is performed only inside the intervals, defined by +* the data collection. +* @param req: Input location for Data request.
Same here.
Quoted 80 lines
kernel-shark-qt/src/libkshark-collection.c new file +80
-0+* @param data: Intput location for the trace data. +* @param col: Intput location for the Data collection. +* @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; + } + +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. +* @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; + + col = col->next; + } + +return NULL ; +} + +/** +* @brief Clear all data intervals of the given Data collection. +* @param col: Intput location for the Data collection. +*/ +void kshark_reset_data_collection (struct kshark_entry_collection *col) +{ +free (col->resume_points); + col->resume_points =NULL ; + +free (col->break_points);
kernel-shark-qt/src/libkshark-collection.c line 632
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+ col->break_points =NULL ; + + col->size =0 ; +} + +static void kshark_free_data_collection (struct kshark_entry_collection *col) +{ +if (col->size) { +free (col->resume_points); +free (col->break_points);
Can col->resume_points or col->break_points be anything other than NULL or allocated memory that needs to be freed? If not, then we don't need the size check. Just free them. free() is a nop when passed NULL.
kernel-shark-qt/src/libkshark-collection.c line 638
Quoted 6 lines
kernel-shark-qt/src/libkshark-collection.c new file +6
-0+ } + +free (col); +} + +/**
On a styling point. I realized that reading the doxygen output I find more difficult than kerneldoc. But then I realized it can be better if we add spacing. By putting in a blank comment line after @brief, and after the last @param, I think it is easier to read. For example:
kernel-shark-qt/src/libkshark-collection.c line 641
Quoted 3 lines
kernel-shark-qt/src/libkshark-collection.c new file +3
-0+* @brief Allocate and process data collection, defined with a given Matching +* condition function and value. Add this collection to the list of +* collections used by the session.
+ *
Quoted 4 lines
kernel-shark-qt/src/libkshark-collection.c new file +4
-0+* @param kshark_ctx: Input location for the session context pointer. +* @param data: Input location for the trace data. +* @param n_rows: The size of the inputted data. +* @param cond: Matching condition function for the collection to be
kernel-shark-qt/src/libkshark-collection.c line 654
Quoted 10 lines
kernel-shark-qt/src/libkshark-collection.c new file +10
-0+* registered. +* @param val: Matching condition value of for collection to be registered. +* @param margin: The size of the additional (margin) data which do not +* satisfying the data condition, but is added at the beginning +* and at the end of each interval of the collection. If "0", +* no margin data is added. +* +* @returns Pointer to the registered Data collections on success, or NULL +* on failure. +*/
What do you think?
-- Steve
Quoted 210 lines
kernel-shark-qt/src/libkshark-collection.c new file +65
-0+struct kshark_entry_collection * +kshark_register_data_collection (struct kshark_context *kshark_ctx, +struct kshark_entry **data, +size_t n_rows, +matching_condition_func cond, +int val, +size_t margin) +{ +struct kshark_entry_collection *col; + + col =kshark_data_collection_alloc (kshark_ctx, data, +0 , n_rows, + cond, val, + margin); +if (!col) +return NULL ; + + col->next = kshark_ctx->collections; + kshark_ctx->collections = col; + +return col; +} + +/** +* @brief Search the list of Data collections for a collection defined +* with a given Matching condition function and value. If such a +* collection exists, unregister (remove and free) this collection +* from the list. +* @param col: Intput location for the Data collection list. +* @param cond: Matching condition function of the collection to be +* unregistered. +* @param val: Matching condition value of the collection to be unregistered. +*/ +void kshark_unregister_data_collection (struct kshark_entry_collection **col, +matching_condition_func cond, +int val) +{ +struct kshark_entry_collection **last = col; +struct kshark_entry_collection *list; + +for (list = *col; list; list = list->next) { +if (list->cond == cond && list->val == val) { + *last = list->next; +kshark_free_data_collection (list); +return ; + } + + last = &list->next; + } +} + +/** +* @brief Free all Data collections in a given list. +* @param col: Intput location for the Data collection list. +*/ +void kshark_free_collection_list (struct kshark_entry_collection *col) +{ +struct kshark_entry_collection *last; + +while (col) { + last = col; + col = col->next; +kshark_free_data_collection (last); + } +}kernel-shark-qt/src/libkshark.c +16
-0@@ -1038,6 +1038,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;@@ -1048,6 +1049,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 ,/* visible */ 0x00 ,kernel-shark-qt/src/libkshark.h +79
-0@@ -115,6 +115,9 @@ struct kshark_context {* the event. */ struct event_filter *advanced_event_filter; + +/** List of Data collections. */ +struct kshark_entry_collection *collections; };bool kshark_instance (struct kshark_context **kshark_ctx);@@ -220,6 +223,9 @@ typedef bool (matching_condition_func)(struct kshark_context*,* kshark_entry. */ struct kshark_entry_request { +/** Pointer to the next Data request. */ +struct kshark_entry_request *next; +/** * Array index specifying the position inside the array from where * the search starts. @@ -252,6 +258,8 @@ kshark_entry_request_alloc(size_t first, size_t n, matching_condition_func cond, int val, bool vis_only, int vis_mask); +void kshark_free_entry_request (struct kshark_entry_request *req); +const struct kshark_entry * kshark_get_entry_front(const struct kshark_entry_request *req, struct kshark_entry **data,@@ -262,6 +270,77 @@ kshark_get_entry_back(const struct kshark_entry_request *req,struct kshark_entry **data, ssize_t *index); +/** +* 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. +*/ +struct kshark_entry_collection { +/** Pointer to the next Data collection. */ +struct kshark_entry_collection *next; + +/** Matching condition function, used to define the collections. */ +matching_condition_func *cond; + +/** +* Matching condition value, used by the Matching condition finction +* to define the collections. +*/ +int val; + +/** +* Array of indexes defining the beginning of each individual data +* interval. +*/ +size_t *resume_points; + +/** +* Array of indexes defining the end of each individual data interval. +*/ +size_t *break_points; + +/** Number of data intervals in this collection. */ +size_t size; +}; + +struct kshark_entry_collection * +kshark_register_data_collection (struct kshark_context *kshark_ctx, +struct kshark_entry **data,size_t n_rows, +matching_condition_func cond,int val, +size_t margin); + +void kshark_unregister_data_collection (struct kshark_entry_collection **col, +matching_condition_func cond, +int val); + +struct kshark_entry_collection * +kshark_find_data_collection (struct kshark_entry_collection *col, +matching_condition_func cond, +int val); + +void kshark_reset_data_collection (struct kshark_entry_collection *col); + +void kshark_free_collection_list (struct kshark_entry_collection *col); + +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 * +kshark_get_collection_entry_back (struct kshark_entry_request **req, +struct kshark_entry **data, +const struct kshark_entry_collection *col, +ssize_t *index); + #ifdef __cplusplus }#endif
Re: [PATCH 4/6] kernel-shark-qt: Define Data collections
Hi Steven,
Quoted 24 lines · Steven Rostedt
On a styling point. I realized that reading the doxygen output I find more difficult than kerneldoc. But then I realized it can be better if we add spacing. By putting in a blank comment line after @brief, and after the last @param, I think it is easier to read. For example:
Quoted 3 lines
+ * @brief Allocate and process data collection, defined with a given Matching
+ * condition function and value. Add this collection to the list of
+ * collections used by the session.+ *
Quoted 7 lines
+ * @param
kshark_ctx: Input location for the session context pointer.
+ * @param data: Input location for the trace data.
+ * @paramn_rows: The size of the inputted data.
+ * @param cond: Matching condition function for the collection to be
+ * registered.
+ * @param val: Matching condition value of for collection to be registered.
+ * @param margin: The size of the additional (margin) data which do notQuoted 7 lines
+ * satisfying the data condition, but is added at the beginning + * and at the end of each interval of the collection. If "0", + * no margin data is added.+ *
+ * @returns Pointer to the registered Data collections on success, or NULL
+ * on failure.
+ */
Quoted 1 line
What do you think?
Do you mean that it makes it easy to read in the source file? I can make this change in a separate patch.
Thanks!
Yordan
Re: [PATCH 4/6] kernel-shark-qt: Define Data collections
Quoted 27 lines · On Tue, 31 Jul 2018 16:50:47 +0300 "Yordan Karadzhov (VMware)"…
Hi Steven,
Quoted 24 lines · Steven Rostedt
On a styling point. I realized that reading the doxygen output I find more difficult than kerneldoc. But then I realized it can be better if we add spacing. By putting in a blank comment line after @brief, and after the last @param, I think it is easier to read. For example:
Quoted 3 lines
+ * @brief Allocate and process data collection, defined with a given Matching
+ * condition function and value. Add this collection to the list of
+ * collections used by the session.+ *
Quoted 14 lines
+ * @param
kshark_ctx: Input location for the session context pointer.
+ * @param data: Input location for the trace data.
+ * @paramn_rows: The size of the inputted data.
+ * @param cond: Matching condition function for the collection to be
+ * registered.
+ * @param val: Matching condition value of for collection to be registered.
+ * @param margin: The size of the additional (margin) data which do not+ * satisfying the data condition, but is added at the beginning + * and at the end of each interval of the collection. If "0", + * no margin data is added.+ *
+ * @returns Pointer to the registered Data collections on success, or NULL
+ * on failure.
+ */
Quoted 6 lines
Quoted 1 line
What do you think?
Do you mean that it makes it easy to read in the source file? I can make this change in a separate patch.
Yes, thanks!
-- Steve
PATCH 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 | 67 +++++++++++++++++++++++---- kernel-shark-qt/src/libkshark-model.h | 13 +++++- 3 files changed, 72 insertions(+), 12 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_check_cpu, val, +NULL , &i_front); e_back =ksmodel_get_entry_back (histo, bin, true, kshark_check_cpu, val, +NULL , &i_back); }else if (strcmp (type,"task" ) ==0 ) { e_front =ksmodel_get_entry_front (histo, bin, true, kshark_check_pid, val, +NULL , &i_front); e_back =ksmodel_get_entry_back (histo, bin, true, kshark_check_pid, val, +NULL , &i_back); }else { i_front =ksmodel_first_index_at_bin (histo, bin);
kernel-shark-qt/src/libkshark-model.c +57 -10
199 lines not on this page · raw message
kernel-shark-qt/src/libkshark-model.h +11 -2
@@ -93,31 +93,40 @@ 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 (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 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