[ltt-dev] [PATCH RFC] Seek fix

[ltt-dev] [PATCH RFC] Seek fix

[Matthew Khouzam]

I am including an example to better illustrace my fix.
the current binary search has a case where high can be lower then low.
An example: 51 blocks, the element is somewhere in the 12th block.
trace of before :
  low : 0, high 51 , block_num -1
  low : 0, high 24 , block_num 25
  low : 13, high 24 , block_num 12
  low : 13, high 17 , block_num 18
  low : 13, high 14 , block_num 15
  low : 13, high 12 , block_num 13
This will assert and fail.
The trace after will produce the following walkthrough
  low : 0, high 51 , block_num -1
  low : 0, high 24 , block_num 25
  low : 0, high 24 , block_num 12
  Found!


-------------- next part --------------
A non-text attachment was scrubbed...
Name: seek_fix.patch
Type: text/x-patch
Size: 757 bytes
Desc: not available
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20101103/f76b1641/attachment-0002.bin>

[ltt-dev] [PATCH RFC] Seek fix

[Matthew Khouzam]

I am including an example to better illustrace my fix.
the current binary search has a case where high can be lower then low.
An example: 51 blocks, the element is somewhere in the 12th block.
trace of before :
  low : 0, high 51 , block_num -1
  low : 0, high 24 , block_num 25
  low : 13, high 24 , block_num 12
  low : 13, high 17 , block_num 18
  low : 13, high 14 , block_num 15
  low : 13, high 12 , block_num 13
This will assert and fail.
The trace after will produce the following walkthrough
  low : 0, high 51 , block_num -1
  low : 0, high 24 , block_num 25
  low : 0, high 24 , block_num 12
  Found!


-------------- next part --------------
A non-text attachment was scrubbed...
Name: seek_fix.patch
Type: text/x-patch
Size: 757 bytes
Desc: not available
URL: <http://lists.casi.polymtl.ca/pipermail/ltt-dev/attachments/20101103/f76b1641/attachment.bin>

[ltt-dev] [PATCH RFC] Seek fix

[Matthew Khouzam]

I am including an example to better illustrace my fix.
the current binary search has a case where high can be lower then low.
An example: 51 blocks, the element is somewhere in the 12th block.
trace of before :
  low : 0, high 51 , block_num -1
  low : 0, high 24 , block_num 25
  low : 13, high 24 , block_num 12
  low : 13, high 17 , block_num 18
  low : 13, high 14 , block_num 15
  low : 13, high 12 , block_num 13
This will assert and fail.
The trace after will produce the following walkthrough
  low : 0, high 51 , block_num -1
  low : 0, high 24 , block_num 25
  low : 0, high 24 , block_num 12
  Found!


-------------- next part --------------
A non-text attachment was scrubbed...
Name: seek_fix.patch
Type: text/x-patch
Size: 757 bytes
Desc: not available
URL: <http://lists.casi.polymtl.ca/pipermail/lttng-dev/attachments/20101103/f76b1641/attachment-0003.bin>

[ltt-dev] [PATCH RFC] Seek fix

[Mathieu Desnoyers]

* Matthew Khouzam (matthew.khouzam at ericsson.com) wrote:
> I am including an example to better illustrace my fix.
> the current binary search has a case where high can be lower then low.
> An example: 51 blocks, the element is somewhere in the 12th block.
> trace of before :
>  low : 0, high 51 , block_num -1
>  low : 0, high 24 , block_num 25
>  low : 13, high 24 , block_num 12
>  low : 13, high 17 , block_num 18
>  low : 13, high 14 , block_num 15
>  low : 13, high 12 , block_num 13
> This will assert and fail.
> The trace after will produce the following walkthrough
>  low : 0, high 51 , block_num -1
>  low : 0, high 24 , block_num 25
>  low : 0, high 24 , block_num 12
>  Found!

Fix committed and pushed. I had to rewrite the patch, because it did not
apply (line wrapping problems, and usually patches should be inlined
into the email body).

See SubmittingPatches in the Linux kernel Documentation directory.

Thanks,

Mathieu

>
>

> 
> Made the tracefile.c seek more robust. Fixes a rare crash where high can be lower than low in a seek. 
> 
> 
> Signed-off-by : Matthew Khouzam matthew.khouzam at ericsson.com
> 
> diff --git a/ltt/tracefile.c b/ltt/tracefile.c
> index 0d8a248..d9aba27 100644
> --- a/ltt/tracefile.c
> +++ b/ltt/tracefile.c
> @@ -1095,7 +1095,7 @@ int ltt_tracefile_seek_time(LttTracefile *tf, 
> LttTime time)
> 
>       } else if(ltt_time_compare(time, tf->buffer.begin.timestamp) < 0) {
>         /* go to lower part */
> -      high = block_num - 1;
> +      high = block_num; // you don't want block_num - 1 since block_num 
> can equal low , in which case high < low.
>       } else if(ltt_time_compare(time, tf->buffer.end.timestamp) > 0) {
>         /* go to higher part */
>         low = block_num + 1;
> 

> _______________________________________________
> ltt-dev mailing list
> ltt-dev at lists.casi.polymtl.ca
> http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com