[PATCH] kernel-shark: Fixing the fix of ksmodel_shif_forward method()

[PATCH] kernel-shark: Fixing the fix of ksmodel_shif_forward method()

[Yordan Karadzhov]

As explaned in the change log of

e54616484 ("Do not copy the Upper Overflow bin when shifting forward"),

the lower edge of the Upper Overflow bin is unusual (shift + 1). Because
of this, the content of the Upper Overflow bin cannot be copied, when
shifting the visible area forward. It has to be recalculated instead.
However, this is not enough to fix the bug. The last bin of the old histo
cannot be copied as well. This is because its upper edge is shifted
too (+1).

Reported-by: Tzvetomir Stoyanov <tstoyanov@vmware.com>
Fixes: e54616484 ("Do not copy the Upper Overflow bin when shifting forward")
Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
---
 kernel-shark/src/libkshark-model.c | 17 ++++++++++++-----
 1 file changed, 12 insertions(+), 5 deletions(-)

diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
index b71a9b8..b80f71e 100644
--- a/kernel-shark/src/libkshark-model.c
+++ b/kernel-shark/src/libkshark-model.c
@@ -488,23 +488,30 @@ void ksmodel_shift_forward(struct kshark_trace_histo *histo, size_t n)
 	ksmodel_set_lower_edge(histo);
 
 	/*
-	 * Copy the the mapping indexes of all overlaping bins starting from
-	 * bin "0" of the new histo. Note that the number of overlaping bins
-	 * is histo->n_bins - n.
 	 * We will do a sanity check. ksmodel_set_lower_edge() sets map[0]
 	 * index of the new histo. This index should then be equal to map[n]
 	 * index of the old histo.
 	 */
 	assert (histo->map[0] == histo->map[n]);
+
+	/*
+	 * Copy the mapping indexes of all overlaping bins starting from
+	 * bin "0" of the new histo. Note that the number of overlaping bins
+	 * is histo->n_bins - n. However, the last bin of the models is
+	 * unusual. Its size has been increased by "1" in order make sure that
+	 * the last entry of the dataset will fall into it (see the comment in
+	 * ksmodel_set_next_bin_edge()). Because of this, we do not want to
+	 * copy the very last bin of the old histo. We are going to recalculate
+	 * its content instead. */
 	memmove(&histo->map[0], &histo->map[n],
-		sizeof(histo->map[0]) * (histo->n_bins - n));
+		sizeof(histo->map[0]) * (histo->n_bins - n - 1));
 
 	/*
 	 * Calculate only the content of the new (non-overlapping) bins.
 	 * Start from the last copied bin and set the edge of each consecutive
 	 * bin.
 	 */
-	bin = histo->n_bins - n - 1;
+	bin = histo->n_bins - n - 2;
 	for (; bin < histo->n_bins; ++bin) {
 		ksmodel_set_next_bin_edge(histo, bin, last_row);
 		if (histo->map[bin + 1] > 0)
-- 
2.17.1

Re: [PATCH] kernel-shark: Fixing the fix of ksmodel_shif_forward method()

[Steven Rostedt]

On Wed, 20 Feb 2019 11:16:10 +0200
Yordan Karadzhov <ykaradzhov@vmware.com> wrote:

> As explaned in the change log of
> 
> e54616484 ("Do not copy the Upper Overflow bin when shifting forward"),
> 
> the lower edge of the Upper Overflow bin is unusual (shift + 1). Because
> of this, the content of the Upper Overflow bin cannot be copied, when
> shifting the visible area forward. It has to be recalculated instead.
> However, this is not enough to fix the bug. The last bin of the old histo
> cannot be copied as well. This is because its upper edge is shifted
> too (+1).
> 
> Reported-by: Tzvetomir Stoyanov <tstoyanov@vmware.com>
> Fixes: e54616484 ("Do not copy the Upper Overflow bin when shifting forward")
> Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
> ---
>  kernel-shark/src/libkshark-model.c | 17 ++++++++++++-----
>  1 file changed, 12 insertions(+), 5 deletions(-)
> 
> diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
> index b71a9b8..b80f71e 100644
> --- a/kernel-shark/src/libkshark-model.c
> +++ b/kernel-shark/src/libkshark-model.c
> @@ -488,23 +488,30 @@ void ksmodel_shift_forward(struct kshark_trace_histo *histo, size_t n)
>  	ksmodel_set_lower_edge(histo);
>  
>  	/*
> -	 * Copy the the mapping indexes of all overlaping bins starting from
> -	 * bin "0" of the new histo. Note that the number of overlaping bins
> -	 * is histo->n_bins - n.
>  	 * We will do a sanity check. ksmodel_set_lower_edge() sets map[0]
>  	 * index of the new histo. This index should then be equal to map[n]
>  	 * index of the old histo.
>  	 */
>  	assert (histo->map[0] == histo->map[n]);
> +
> +	/*
> +	 * Copy the mapping indexes of all overlaping bins starting from
> +	 * bin "0" of the new histo. Note that the number of overlaping bins
> +	 * is histo->n_bins - n. However, the last bin of the models is
> +	 * unusual. Its size has been increased by "1" in order make sure that
> +	 * the last entry of the dataset will fall into it (see the comment in
> +	 * ksmodel_set_next_bin_edge()). Because of this, we do not want to
> +	 * copy the very last bin of the old histo. We are going to recalculate
> +	 * its content instead. */
>  	memmove(&histo->map[0], &histo->map[n],
> -		sizeof(histo->map[0]) * (histo->n_bins - n));
> +		sizeof(histo->map[0]) * (histo->n_bins - n - 1));
>  
>  	/*
>  	 * Calculate only the content of the new (non-overlapping) bins.
>  	 * Start from the last copied bin and set the edge of each consecutive
>  	 * bin.
>  	 */
> -	bin = histo->n_bins - n - 1;
> +	bin = histo->n_bins - n - 2;

Is it possible that we could have histo->n_bins == n - 1?

-- Steve

>  	for (; bin < histo->n_bins; ++bin) {
>  		ksmodel_set_next_bin_edge(histo, bin, last_row);
>  		if (histo->map[bin + 1] > 0)

Re: [PATCH] kernel-shark: Fixing the fix of ksmodel_shif_forward method()

[Yordan Karadzhov (VMware)]

On 20.02.19 г. 16:51 ч., Steven Rostedt wrote:
> On Wed, 20 Feb 2019 11:16:10 +0200
> Yordan Karadzhov <ykaradzhov@vmware.com> wrote:
> 
>> As explaned in the change log of
>>
>> e54616484 ("Do not copy the Upper Overflow bin when shifting forward"),
>>
>> the lower edge of the Upper Overflow bin is unusual (shift + 1). Because
>> of this, the content of the Upper Overflow bin cannot be copied, when
>> shifting the visible area forward. It has to be recalculated instead.
>> However, this is not enough to fix the bug. The last bin of the old histo
>> cannot be copied as well. This is because its upper edge is shifted
>> too (+1).
>>
>> Reported-by: Tzvetomir Stoyanov <tstoyanov@vmware.com>
>> Fixes: e54616484 ("Do not copy the Upper Overflow bin when shifting forward")
>> Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
>> ---
>>   kernel-shark/src/libkshark-model.c | 17 ++++++++++++-----
>>   1 file changed, 12 insertions(+), 5 deletions(-)
>>
>> diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
>> index b71a9b8..b80f71e 100644
>> --- a/kernel-shark/src/libkshark-model.c
>> +++ b/kernel-shark/src/libkshark-model.c
>> @@ -488,23 +488,30 @@ void ksmodel_shift_forward(struct kshark_trace_histo *histo, size_t n)
>>   	ksmodel_set_lower_edge(histo);
>>   
>>   	/*
>> -	 * Copy the the mapping indexes of all overlaping bins starting from
>> -	 * bin "0" of the new histo. Note that the number of overlaping bins
>> -	 * is histo->n_bins - n.
>>   	 * We will do a sanity check. ksmodel_set_lower_edge() sets map[0]
>>   	 * index of the new histo. This index should then be equal to map[n]
>>   	 * index of the old histo.
>>   	 */
>>   	assert (histo->map[0] == histo->map[n]);
>> +
>> +	/*
>> +	 * Copy the mapping indexes of all overlaping bins starting from
>> +	 * bin "0" of the new histo. Note that the number of overlaping bins
>> +	 * is histo->n_bins - n. However, the last bin of the models is
>> +	 * unusual. Its size has been increased by "1" in order make sure that
>> +	 * the last entry of the dataset will fall into it (see the comment in
>> +	 * ksmodel_set_next_bin_edge()). Because of this, we do not want to
>> +	 * copy the very last bin of the old histo. We are going to recalculate
>> +	 * its content instead. */
>>   	memmove(&histo->map[0], &histo->map[n],
>> -		sizeof(histo->map[0]) * (histo->n_bins - n));
>> +		sizeof(histo->map[0]) * (histo->n_bins - n - 1));
>>   
>>   	/*
>>   	 * Calculate only the content of the new (non-overlapping) bins.
>>   	 * Start from the last copied bin and set the edge of each consecutive
>>   	 * bin.
>>   	 */
>> -	bin = histo->n_bins - n - 1;
>> +	bin = histo->n_bins - n - 2;
> 
> Is it possible that we could have histo->n_bins == n - 1?

This is not possible.
Several lines above in the code we have


	if (n >= histo->n_bins) {
		/*
		 * No overlap between the new and the old ranges. Recalculate
		 * all bins from scratch. First calculate the new range.
		 */
		ksmodel_set_bining(histo, histo->n_bins, histo->min,
							 histo->max);

		ksmodel_fill(histo, histo->data, histo->data_size);
		return;
	}

Thanks!
Yordan

> 
> -- Steve
> 
>>   	for (; bin < histo->n_bins; ++bin) {
>>   		ksmodel_set_next_bin_edge(histo, bin, last_row);
>>   		if (histo->map[bin + 1] > 0)
> 

Re: [PATCH] kernel-shark: Fixing the fix of ksmodel_shif_forward method()

[Steven Rostedt]

On Wed, 20 Feb 2019 17:29:34 +0200
"Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:

> On 20.02.19 г. 16:51 ч., Steven Rostedt wrote:
> > On Wed, 20 Feb 2019 11:16:10 +0200
> > Yordan Karadzhov <ykaradzhov@vmware.com> wrote:
> >   
> >> As explaned in the change log of
> >>
> >> e54616484 ("Do not copy the Upper Overflow bin when shifting forward"),
> >>
> >> the lower edge of the Upper Overflow bin is unusual (shift + 1). Because
> >> of this, the content of the Upper Overflow bin cannot be copied, when
> >> shifting the visible area forward. It has to be recalculated instead.
> >> However, this is not enough to fix the bug. The last bin of the old histo
> >> cannot be copied as well. This is because its upper edge is shifted
> >> too (+1).
> >>
> >> Reported-by: Tzvetomir Stoyanov <tstoyanov@vmware.com>
> >> Fixes: e54616484 ("Do not copy the Upper Overflow bin when shifting forward")
> >> Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
> >> ---
> >>   kernel-shark/src/libkshark-model.c | 17 ++++++++++++-----
> >>   1 file changed, 12 insertions(+), 5 deletions(-)
> >>
> >> diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
> >> index b71a9b8..b80f71e 100644
> >> --- a/kernel-shark/src/libkshark-model.c
> >> +++ b/kernel-shark/src/libkshark-model.c
> >> @@ -488,23 +488,30 @@ void ksmodel_shift_forward(struct kshark_trace_histo *histo, size_t n)
> >>   	ksmodel_set_lower_edge(histo);
> >>   
> >>   	/*
> >> -	 * Copy the the mapping indexes of all overlaping bins starting from
> >> -	 * bin "0" of the new histo. Note that the number of overlaping bins
> >> -	 * is histo->n_bins - n.
> >>   	 * We will do a sanity check. ksmodel_set_lower_edge() sets map[0]
> >>   	 * index of the new histo. This index should then be equal to map[n]
> >>   	 * index of the old histo.
> >>   	 */
> >>   	assert (histo->map[0] == histo->map[n]);
> >> +
> >> +	/*
> >> +	 * Copy the mapping indexes of all overlaping bins starting from
> >> +	 * bin "0" of the new histo. Note that the number of overlaping bins
> >> +	 * is histo->n_bins - n. However, the last bin of the models is
> >> +	 * unusual. Its size has been increased by "1" in order make sure that
> >> +	 * the last entry of the dataset will fall into it (see the comment in
> >> +	 * ksmodel_set_next_bin_edge()). Because of this, we do not want to
> >> +	 * copy the very last bin of the old histo. We are going to recalculate
> >> +	 * its content instead. */
> >>   	memmove(&histo->map[0], &histo->map[n],
> >> -		sizeof(histo->map[0]) * (histo->n_bins - n));
> >> +		sizeof(histo->map[0]) * (histo->n_bins - n - 1));
> >>   
> >>   	/*
> >>   	 * Calculate only the content of the new (non-overlapping) bins.
> >>   	 * Start from the last copied bin and set the edge of each consecutive
> >>   	 * bin.
> >>   	 */
> >> -	bin = histo->n_bins - n - 1;
> >> +	bin = histo->n_bins - n - 2;  
> > 
> > Is it possible that we could have histo->n_bins == n - 1?  

Sorry, I meant n + 1.

histo->n_bins = 5, n = 4.

	bin = (5) - (4) - 2 = -1.

-- Steve

> 
> This is not possible.
> Several lines above in the code we have
> 
> 
> 	if (n >= histo->n_bins) {
> 		/*
> 		 * No overlap between the new and the old ranges. Recalculate
> 		 * all bins from scratch. First calculate the new range.
> 		 */
> 		ksmodel_set_bining(histo, histo->n_bins, histo->min,
> 							 histo->max);
> 
> 		ksmodel_fill(histo, histo->data, histo->data_size);
> 		return;
> 	}

Re: [PATCH] kernel-shark: Fixing the fix of ksmodel_shif_forward method()

[Yordan Karadzhov (VMware)]

On 20.02.19 г. 18:37 ч., Steven Rostedt wrote:
> On Wed, 20 Feb 2019 17:29:34 +0200
> "Yordan Karadzhov (VMware)" <y.karadz@gmail.com> wrote:
> 
>> On 20.02.19 г. 16:51 ч., Steven Rostedt wrote:
>>> On Wed, 20 Feb 2019 11:16:10 +0200
>>> Yordan Karadzhov <ykaradzhov@vmware.com> wrote:
>>>    
>>>> As explaned in the change log of
>>>>
>>>> e54616484 ("Do not copy the Upper Overflow bin when shifting forward"),
>>>>
>>>> the lower edge of the Upper Overflow bin is unusual (shift + 1). Because
>>>> of this, the content of the Upper Overflow bin cannot be copied, when
>>>> shifting the visible area forward. It has to be recalculated instead.
>>>> However, this is not enough to fix the bug. The last bin of the old histo
>>>> cannot be copied as well. This is because its upper edge is shifted
>>>> too (+1).
>>>>
>>>> Reported-by: Tzvetomir Stoyanov <tstoyanov@vmware.com>
>>>> Fixes: e54616484 ("Do not copy the Upper Overflow bin when shifting forward")
>>>> Signed-off-by: Yordan Karadzhov <ykaradzhov@vmware.com>
>>>> ---
>>>>    kernel-shark/src/libkshark-model.c | 17 ++++++++++++-----
>>>>    1 file changed, 12 insertions(+), 5 deletions(-)
>>>>
>>>> diff --git a/kernel-shark/src/libkshark-model.c b/kernel-shark/src/libkshark-model.c
>>>> index b71a9b8..b80f71e 100644
>>>> --- a/kernel-shark/src/libkshark-model.c
>>>> +++ b/kernel-shark/src/libkshark-model.c
>>>> @@ -488,23 +488,30 @@ void ksmodel_shift_forward(struct kshark_trace_histo *histo, size_t n)
>>>>    	ksmodel_set_lower_edge(histo);
>>>>    
>>>>    	/*
>>>> -	 * Copy the the mapping indexes of all overlaping bins starting from
>>>> -	 * bin "0" of the new histo. Note that the number of overlaping bins
>>>> -	 * is histo->n_bins - n.
>>>>    	 * We will do a sanity check. ksmodel_set_lower_edge() sets map[0]
>>>>    	 * index of the new histo. This index should then be equal to map[n]
>>>>    	 * index of the old histo.
>>>>    	 */
>>>>    	assert (histo->map[0] == histo->map[n]);
>>>> +
>>>> +	/*
>>>> +	 * Copy the mapping indexes of all overlaping bins starting from
>>>> +	 * bin "0" of the new histo. Note that the number of overlaping bins
>>>> +	 * is histo->n_bins - n. However, the last bin of the models is
>>>> +	 * unusual. Its size has been increased by "1" in order make sure that
>>>> +	 * the last entry of the dataset will fall into it (see the comment in
>>>> +	 * ksmodel_set_next_bin_edge()). Because of this, we do not want to
>>>> +	 * copy the very last bin of the old histo. We are going to recalculate
>>>> +	 * its content instead. */
>>>>    	memmove(&histo->map[0], &histo->map[n],
>>>> -		sizeof(histo->map[0]) * (histo->n_bins - n));
>>>> +		sizeof(histo->map[0]) * (histo->n_bins - n - 1));
>>>>    
>>>>    	/*
>>>>    	 * Calculate only the content of the new (non-overlapping) bins.
>>>>    	 * Start from the last copied bin and set the edge of each consecutive
>>>>    	 * bin.
>>>>    	 */
>>>> -	bin = histo->n_bins - n - 1;
>>>> +	bin = histo->n_bins - n - 2;
>>>
>>> Is it possible that we could have histo->n_bins == n - 1?
> 
> Sorry, I meant n + 1.
> 
> histo->n_bins = 5, n = 4.
> 
> 	bin = (5) - (4) - 2 = -1.
>

Hi Steven,

Sometimes I am just lucky ;)
I am glad that you found this mistake because in fact the whole patch is 
crap.
I misinterpreted the symptoms of the problem, reported by Ceco.
Alternative solution (patches) are coming.

Thanks a lot!
Yordan

> -- Steve
> 
>>
>> This is not possible.
>> Several lines above in the code we have
>>
>>
>> 	if (n >= histo->n_bins) {
>> 		/*
>> 		 * No overlap between the new and the old ranges. Recalculate
>> 		 * all bins from scratch. First calculate the new range.
>> 		 */
>> 		ksmodel_set_bining(histo, histo->n_bins, histo->min,
>> 							 histo->max);
>>
>> 		ksmodel_fill(histo, histo->data, histo->data_size);
>> 		return;
>> 	}