[PATCH] oprofile per-cpu buffer overrun

[PATCH] oprofile per-cpu buffer overrun

[Philippe Elie]

Hi Andrew,

In a ring buffer controlled by a read and write positions we
can't use buffer_size but only buffer_size - 1 entry, the last
free entry act as a guard to avoid write pos overrun. This bug
was hidden because the writer, oprofile_add_sample(), request
one more entry than really needed.

regards,
Phil

Index: drivers/oprofile/cpu_buffer.c
===================================================================
RCS file: /usr/local/cvsroot/linux-2.5/drivers/oprofile/cpu_buffer.c,v
retrieving revision 1.9
diff -u -p -r1.9 cpu_buffer.c
--- drivers/oprofile/cpu_buffer.c	26 May 2003 04:42:54 -0000	1.9
+++ drivers/oprofile/cpu_buffer.c	24 Jan 2004 21:07:03 -0000
@@ -86,9 +86,9 @@ static unsigned long nr_available_slots(
 	unsigned long tail = b->tail_pos;
 
 	if (tail > head)
-		return tail - head;
+		return (tail - head) - 1;
 
-	return tail + (b->buffer_size - head);
+	return tail + (b->buffer_size - head) - 1;
 }
 
 

Re: [PATCH] oprofile per-cpu buffer overrun

[Andrew Morton]

Philippe Elie <phil.el@wanadoo.fr> wrote:
>
> Hi Andrew,
> 
> In a ring buffer controlled by a read and write positions we
> can't use buffer_size but only buffer_size - 1 entry,

you can, actually.

> the last
> free entry act as a guard to avoid write pos overrun. This bug
> was hidden because the writer, oprofile_add_sample(), request
> one more entry than really needed.
> 
>...
> diff -u -p -r1.9 cpu_buffer.c
> --- drivers/oprofile/cpu_buffer.c	26 May 2003 04:42:54 -0000	1.9
> +++ drivers/oprofile/cpu_buffer.c	24 Jan 2004 21:07:03 -0000
> @@ -86,9 +86,9 @@ static unsigned long nr_available_slots(
>  	unsigned long tail = b->tail_pos;
>  
>  	if (tail > head)
> -		return tail - head;
> +		return (tail - head) - 1;
>  
> -	return tail + (b->buffer_size - head);
> +	return tail + (b->buffer_size - head) - 1;
>  }

When implementing a circular buffer it is better to not constrain the head
and tail indices - just let them grow and wrap without bound.  You only need
to bring them in-bounds when you actually use them to index the buffer.

This way,

- head-tail is always the amount of used space, no need to futz around
  handling the case where one has wrapped and the other hasn't.

- you get to use all of the buffer, because the cases head-tail == 0
  (empty) and head-tail == bufsize (full) are now distinguishable.

  It helps if the buffer size is a power of two, of course, but integer
  modulus is pretty quick.

All the net drivers and the printk log buffer implement their ring buffers
in this way; it works nicely.

Re: [PATCH] oprofile per-cpu buffer overrun

[Anton Blanchard]

 
>   It helps if the buffer size is a power of two, of course, but integer
>   modulus is pretty quick.

If its something thats hit real hard, the way the modulus is done can
make a difference. We've seen it in various places (eg disabling tigon 1
support in the acenic changes the driver from using a variable to a
compile time constant and you can actually see it in the profile):

quickest == power of 2 compile time constant (results in a mask)
quickish == compile time constant (results in the multiplication by
		an inverse trick)
slow == run time (results in a divide)

Of course you can do like the printk stuff and use a variable but
enforce a power of 2 value and & it.

Anton

--

unsigned long i, j, k;

int quickest()
{
        j = i % 2;
}

int quickish()
{
        j = i % 3;
}

int slow()
{
        j = i % k;
}

--

quickest:
        lis 9,i@ha
        lwz 0,i@l(9)
        lis 9,j@ha
        rlwinm 0,0,0,31,31
        stw 0,j@l(9)
        blr
quickish:
        lis 9,i@ha
        lis 0,0xaaaa
        lwz 11,i@l(9)
        ori 0,0,43691
        lis 9,j@ha
        mulhwu 0,11,0
        srwi 0,0,1
        mulli 0,0,3
        subf 11,0,11
        stw 11,j@l(9)
        blr
slow:
        lis 9,i@ha
        lis 11,k@ha
        lwz 10,i@l(9)
        lwz 9,k@l(11)
        divwu 0,10,9
        mullw 0,0,9
        lis 9,j@ha
        subf 10,0,10
        stw 10,j@l(9)
        blr

Re: [PATCH] oprofile per-cpu buffer overrun

[John Levon]

On Sun, Jan 25, 2004 at 08:07:01PM -0800, Andrew Morton wrote:

> When implementing a circular buffer it is better to not constrain the head
> and tail indices - just let them grow and wrap without bound.  You only need
> to bring them in-bounds when you actually use them to index the buffer.

I'm not sure why that's better.

> - head-tail is always the amount of used space, no need to futz around
>   handling the case where one has wrapped and the other hasn't.

I admit I have a hangover, but it seems to me it would actually be more
complicated to make damn sure that the integer overflow case is
definitely handled properly.

I clearly can't write functioning ring buffers :), so I'd prefer it to
stay as simple as possible.

regards,
john
-- 
Khendon's Law:
If the same point is made twice by the same person, the thread is over.

Re: [PATCH] oprofile per-cpu buffer overrun

[Nick Piggin]

John Levon wrote:

>On Sun, Jan 25, 2004 at 08:07:01PM -0800, Andrew Morton wrote:
>
>
>>When implementing a circular buffer it is better to not constrain the head
>>and tail indices - just let them grow and wrap without bound.  You only need
>>to bring them in-bounds when you actually use them to index the buffer.
>>
>
>I'm not sure why that's better.
>
>
>>- head-tail is always the amount of used space, no need to futz around
>>  handling the case where one has wrapped and the other hasn't.
>>
>
>I admit I have a hangover, but it seems to me it would actually be more
>complicated to make damn sure that the integer overflow case is
>definitely handled properly.
>

You needn't worry about integer overflow - it is handled properly ;)

Re: [PATCH] oprofile per-cpu buffer overrun

[Philippe Elie]

John Levon wrote:
> On Sun, Jan 25, 2004 at 08:07:01PM -0800, Andrew Morton wrote:
> 
> 
>>When implementing a circular buffer it is better to not constrain the head
>>and tail indices - just let them grow and wrap without bound.  You only need
>>to bring them in-bounds when you actually use them to index the buffer.

neat!

> I'm not sure why that's better.

We win in increment_head/increment_tail:

static void increment_head(struct oprofile_cpu_buffer * b)
{
- 
unsigned long new_head = b->head_pos + 1;
	wmb();
- 
if (new_head < (b->buffer_size))
- 
	b->head_pos = new_head;
- 
else
- 
	b->head_pos = 0;
+ 
b->head_pos++;
}

for this added cost when accessing the buffer:

b->buffer[b->head & b->buffer_size_mask];

Modulo use is not worth but with buffer_size a power of 2
it's probably a win, I'll try and measure this later, not
urgent since the problem is fixed, I added it in our todo.

regards,
Phil