[PATCH 0/3] KernelShark visualization model fixes

[PATCH 0/3] KernelShark visualization model fixes

[Yordan Karadzhov]

This patch set fixes three distinct, but strongly entangled bugs in the
visualization model of KernelShark. Most of the time those bugs have no
effect, but in some very rare cases may cause some of the sanity checks
of the model to fail.


Yordan Karadzhov (3):
  kernel-shark: Fix a bug in ksmodel_shift_backward()
  kernel-shark: Fix a bug in shift_XXX methods of the visualization
    model
  kernel-shark: Fix a bug in ksmodel_set_next_bin_edge()

 kernel-shark/src/libkshark-model.c | 28 ++++++++++++++--------------
 1 file changed, 14 insertions(+), 14 deletions(-)

-- 
2.17.1

[PATCH 1/3] kernel-shark: Fix a bug in ksmodel_shift_backward()

[Yordan Karadzhov]

Bin 0 of the new model has to be set after copying the overlaping bins
from the old model. Otherwise the new content of Bin 0 will be copied
into Bin "n". This bug has no effect because ksmodel_shift_backward()
has a second bug in the loop over the non-overlapping bins. The second
bug will be fixed in the following patch.

Fixes: f97e31f00 ("kernel-shark-qt: Introduce the visualization model ..")
Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
---
 kernel-shark/src/libkshark-model.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
index b71a9b8..a185d6b 100644
--- a/kernel-shark/src/libkshark-model.c
+++ b/kernel-shark/src/libkshark-model.c
@@ -557,17 +557,18 @@ void ksmodel_shift_backward(struct kshark_trace_histo *histo, size_t n)
 		ksmodel_fill(histo, histo->data, histo->data_size);
 		return;
 	}
-	/* Set the new Lower Overflow bin. */
-	ksmodel_set_lower_edge(histo);
 
 	/*
-	 * Copy the the mapping indexes of all overlaping bins starting from
+	 * Copy the mapping indexes of all overlaping bins starting from
 	 * bin "0" of the old histo. Note that the number of overlaping bins
 	 * is histo->n_bins - n.
 	 */
 	memmove(&histo->map[n], &histo->map[0],
 		sizeof(histo->map[0]) * (histo->n_bins - n));
 
+	/* Set the new Lower Overflow bin. */
+	ksmodel_set_lower_edge(histo);
+
 	/* Calculate only the content of the new (non-overlapping) bins. */
 	for (bin = 0; bin < n; ++bin) {
 		ksmodel_set_next_bin_edge(histo, bin, last_row);
-- 
2.17.1

[PATCH 2/3] kernel-shark: Fix a bug in shift_XXX methods of the visualization model

[Yordan Karadzhov]

In ksmodel_shift_forward() and ksmodel_shift_backward() we are supposed
to recalculate only the content of the new (non-overlapping) Bins. However
the loop does not take into account that the static function used to do
the job actually calculates next Bin (bin + 1). The result is this
misunderstanding is that we recalculate also the first overlapping
Bin (n). This wipes up the effect of the bug fixed by the previous patch.

Fixes: f97e31f00 ("kernel-shark-qt: Introduce the visualization model ..")
Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
---
 kernel-shark/src/libkshark-model.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
index a185d6b..b6d3612 100644
--- a/kernel-shark/src/libkshark-model.c
+++ b/kernel-shark/src/libkshark-model.c
@@ -505,7 +505,11 @@ void ksmodel_shift_forward(struct kshark_trace_histo *histo, size_t n)
 	 * bin.
 	 */
 	bin = histo->n_bins - n - 1;
-	for (; bin < histo->n_bins; ++bin) {
+	for (; bin < histo->n_bins - 1; ++bin) {
+		/*
+		 * Note that this function will set the bin having index
+		 * "bin + 1".
+		 */
 		ksmodel_set_next_bin_edge(histo, bin, last_row);
 		if (histo->map[bin + 1] > 0)
 			last_row = histo->map[bin + 1];
@@ -570,7 +574,11 @@ void ksmodel_shift_backward(struct kshark_trace_histo *histo, size_t n)
 	ksmodel_set_lower_edge(histo);
 
 	/* Calculate only the content of the new (non-overlapping) bins. */
-	for (bin = 0; bin < n; ++bin) {
+	for (bin = 0; bin < n - 1; ++bin) {
+		/*
+		 * Note that this function will set the bin having index
+		 * "bin + 1".
+		 */
 		ksmodel_set_next_bin_edge(histo, bin, last_row);
 		if (histo->map[bin + 1] > 0)
 			last_row = histo->map[bin + 1];
-- 
2.17.1

[PATCH 3/3] kernel-shark: Fix a bug in ksmodel_set_next_bin_edge()

[Yordan Karadzhov]

The modification of the last bin of the model makes no sense (this is
my mistake). The comment above the code that is doing this modification
is partially correct, however it speaks about increasing the size of
the last bin, while the code below the comment changes the lower edge
of this bin. The actual increase of the size of the last bin is done in
ksmodel_set_upper_edge() where the lower edge of the Upper Overflow bin
gets shifted (max + 1). This effectively increases the size of the last bin.

Reported-by: Tzvetomir Stoyanov <tstoyanov@vmware.com>
Fixes: f97e31f00 ("kernel-shark-qt: Introduce the visualization model ..")
Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
---
 kernel-shark/src/libkshark-model.c | 9 ---------
 1 file changed, 9 deletions(-)

diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
index b6d3612..4bd1e2c 100644
--- a/kernel-shark/src/libkshark-model.c
+++ b/kernel-shark/src/libkshark-model.c
@@ -266,15 +266,6 @@ static void ksmodel_set_next_bin_edge(struct kshark_trace_histo *histo,
 	/* Calculate the beginning of the next bin. */
 	time = histo->min + next_bin * histo->bin_size;
 
-	/*
-	 * 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;
 	/*
 	 * Find the index of the first entry inside
 	 * the next bin (timestamp > time).
-- 
2.17.1

Re: [PATCH 3/3] kernel-shark: Fix a bug in ksmodel_set_next_bin_edge()

[Slavomir Kaslev]

On Thu, Feb 21, 2019 at 02:42:05PM +0200, Yordan Karadzhov wrote:
> The modification of the last bin of the model makes no sense (this is
> my mistake). The comment above the code that is doing this modification
> is partially correct, however it speaks about increasing the size of
> the last bin, while the code below the comment changes the lower edge
> of this bin. The actual increase of the size of the last bin is done in
> ksmodel_set_upper_edge() where the lower edge of the Upper Overflow bin
> gets shifted (max + 1). This effectively increases the size of the last bin.
> 
> Reported-by: Tzvetomir Stoyanov <tstoyanov@vmware.com>
> Fixes: f97e31f00 ("kernel-shark-qt: Introduce the visualization model ..")
> Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
> ---
>  kernel-shark/src/libkshark-model.c | 9 ---------
>  1 file changed, 9 deletions(-)
> 
> diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
> index b6d3612..4bd1e2c 100644
> --- a/kernel-shark/src/libkshark-model.c
> +++ b/kernel-shark/src/libkshark-model.c
> @@ -266,15 +266,6 @@ static void ksmodel_set_next_bin_edge(struct kshark_trace_histo *histo,
>  	/* Calculate the beginning of the next bin. */
>  	time = histo->min + next_bin * histo->bin_size;
>  
> -	/*
> -	 * 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;
>  	/*
>  	 * Find the index of the first entry inside
>  	 * the next bin (timestamp > time).
> -- 
> 2.17.1
> 

Patches 1, 2 and 3 look good to me.

Acked-by: Slavomir Kaslev <kaslevs@vmware.com>

Side note: ksmodel_shift_backward/ksmodel_shift_forward look pretty similar. Can
they be generalized to an either-directional ksmodel_shift taking the shift
parameter as signed? If ksmodel_shift_backward/ksmodel_shift_forward need to be
kept for backward compatibility, they can call ksmodel_shift (with a flipped
sign in the backward case).

Thank you,

-- Slavi

Re: [PATCH 3/3] kernel-shark: Fix a bug in ksmodel_set_next_bin_edge()

[Yordan Karadzhov]

On 21.02.19 г. 18:15 ч., Slavomir Kaslev wrote:
> On Thu, Feb 21, 2019 at 02:42:05PM +0200, Yordan Karadzhov wrote:
>> The modification of the last bin of the model makes no sense (this is
>> my mistake). The comment above the code that is doing this modification
>> is partially correct, however it speaks about increasing the size of
>> the last bin, while the code below the comment changes the lower edge
>> of this bin. The actual increase of the size of the last bin is done in
>> ksmodel_set_upper_edge() where the lower edge of the Upper Overflow bin
>> gets shifted (max + 1). This effectively increases the size of the last bin.
>>
>> Reported-by: Tzvetomir Stoyanov <tstoyanov@vmware.com>
>> Fixes: f97e31f00 ("kernel-shark-qt: Introduce the visualization model ..")
>> Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
>> ---
>>   kernel-shark/src/libkshark-model.c | 9 ---------
>>   1 file changed, 9 deletions(-)
>>
>> diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
>> index b6d3612..4bd1e2c 100644
>> --- a/kernel-shark/src/libkshark-model.c
>> +++ b/kernel-shark/src/libkshark-model.c
>> @@ -266,15 +266,6 @@ static void ksmodel_set_next_bin_edge(struct kshark_trace_histo *histo,
>>   	/* Calculate the beginning of the next bin. */
>>   	time = histo->min + next_bin * histo->bin_size;
>>   
>> -	/*
>> -	 * 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;
>>   	/*
>>   	 * Find the index of the first entry inside
>>   	 * the next bin (timestamp > time).
>> -- 
>> 2.17.1
>>
> 
> Patches 1, 2 and 3 look good to me.
> 
> Acked-by: Slavomir Kaslev <kaslevs@vmware.com>
> 
> Side note: ksmodel_shift_backward/ksmodel_shift_forward look pretty similar. Can
> they be generalized to an either-directional ksmodel_shift taking the shift
> parameter as signed? If ksmodel_shift_backward/ksmodel_shift_forward need to be
> kept for backward compatibility, they can call ksmodel_shift (with a flipped
> sign in the backward case).
> 
Thanks for the comment!
You are right. I think this can be done, but in a separate patch.

Yordan


> Thank you,
> 
> -- Slavi
> 

Re: [PATCH 3/3] kernel-shark: Fix a bug in ksmodel_set_next_bin_edge()

[Steven Rostedt]

On Thu, 21 Feb 2019 16:38:29 +0000
Yordan Karadzhov <ykaradzhov@vmware.com> wrote:

> > Acked-by: Slavomir Kaslev <kaslevs@vmware.com>

Thanks for reviewing Slavomir!

> > 
> > Side note: ksmodel_shift_backward/ksmodel_shift_forward look pretty similar. Can
> > they be generalized to an either-directional ksmodel_shift taking the shift
> > parameter as signed? If ksmodel_shift_backward/ksmodel_shift_forward need to be
> > kept for backward compatibility, they can call ksmodel_shift (with a flipped
> > sign in the backward case).
> >   
> Thanks for the comment!
> You are right. I think this can be done, but in a separate patch.

I agree on both accounts.

-- Steve

Re: [PATCH 3/3] kernel-shark: Fix a bug in ksmodel_set_next_bin_edge()

[Steven Rostedt]

On Thu, 21 Feb 2019 18:15:32 +0200
Slavomir Kaslev <kaslevs@vmware.com> wrote:

> Patches 1, 2 and 3 look good to me.
> 
> Acked-by: Slavomir Kaslev <kaslevs@vmware.com>

Slavomir, is it OK that I put "Reviewed-by" instead of "Acked-by". A
reviewed-by caries a bit more weight and states that you did a review.
An ack is more of "yeah, I looked it over and I'm OK with the idea",
but doesn't actually mean you reviewed it.

-- Steve

Re: [PATCH 3/3] kernel-shark: Fix a bug in ksmodel_set_next_bin_edge()

[Slavomir Kaslev]

On Fri, Feb 22, 2019 at 9:34 PM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> On Thu, 21 Feb 2019 18:15:32 +0200
> Slavomir Kaslev <kaslevs@vmware.com> wrote:
>
> > Patches 1, 2 and 3 look good to me.
> >
> > Acked-by: Slavomir Kaslev <kaslevs@vmware.com>
>
> Slavomir, is it OK that I put "Reviewed-by" instead of "Acked-by". A
> reviewed-by caries a bit more weight and states that you did a review.
> An ack is more of "yeah, I looked it over and I'm OK with the idea",
> but doesn't actually mean you reviewed it.

Thanks for pointing it out. My bad, I didn't realize there was a difference[1].

Reviewed-by: Slavomir Kaslev <kaslevs@vmware.com>

[1]https://www.kernel.org/doc/html/v4.20/process/submitting-patches.html#reviewer-s-statement-of-oversight