oprofile per-cpu buffer overrun
PATCH 1/1 oprofile per-cpu buffer overrun
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
oprofile/cpu_buffer.c +2 -2
@@ -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 ; }
Quoted 5 lines · Philippe Elie
Hi Andrew,
In a ring buffer controlled by a read and write positions we can't use
buffer_sizebut onlybuffer_size- 1 entry,
you can, actually.
Quoted 10 lines
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.9cpu_buffer.c
oprofile/cpu_buffer.c static unsigned long nr_available_slots( · line 92
Quoted 9 lines
oprofile/cpu_buffer.c +2
-2@@ -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.
Quoted 3 lines
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)
blrQuoted 3 lines · Andrew Morton
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.
Quoted 2 lines
- 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
Signature · 2 lines
Khendon's Law: If the same point is made twice by the same person, the thread is over.
Quoted 11 lines · John Levon
Quoted 4 lines · Andrew Morton
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.
Quoted 8 lines
Quoted 3 lines
- 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 ;)
Quoted 6 lines · John Levon
Quoted 3 lines · Andrew Morton
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!
Quoted 1 line
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