slab redzoning

slab redzoning

[William Lee Irwin III]

The code does not appear to match the intent for slab redzoning sizing.
It wants to ignore size increases when order 0 allocations are involved,
and otherwise to allow the size increase except when it would make the
size cross a power of 2 boundary.

This actually came under scrutiny during a discussion of fls() usage,
but there appears to be little that can be done there.

The following patch attempts to correct this variation of code from
intent and to document the intent in more detail. Untested.

One thing that could happen is to change or clarify what's trying to
be done to be something other than what I've arranged this to do. The
important point is that the current code doesn't match the intent.


Index: mm4-2.6.6/mm/slab.c
===================================================================
--- mm4-2.6.6.orig/mm/slab.c	2004-05-21 14:30:17.000000000 -0700
+++ mm4-2.6.6/mm/slab.c	2004-05-21 20:13:07.892507000 -0700
@@ -1158,8 +1158,21 @@
 	 * large objects, if the increased size would increase the object size
 	 * above the next power of two: caches with object sizes just above a
 	 * power of two have a significant amount of internal fragmentation.
+	 *
+	 * The situation we're trying to avoid is there being a power of 2,
+	 * 2**n for some n, where size < 2**n <= size + 3*BYTES_PER_WORD,
+	 * but excepting anything smaller than a page.
+	 * PAGE_SIZE >= 1024 and 3*BYTES_PER_WORD <= 24 so ignore the
+	 * case where size would more than double from redzone overhead
+	 * in this check; it's taken care of by checking for <= PAGE_SIZE.
+	 * 1 << fls(size) is the next power of 2 above size, so then
+	 * this checks that size is more than 3*BYTES_PER_WORD below it.
+	 * This also special cases the case where size is a power of 2,
+	 * where fragmentation would be increased greatly.
 	 */
-	if ((size < 4096 || fls(size-1) == fls(size-1+3*BYTES_PER_WORD)))
+	if (size + 3*BYTES_PER_WORD <= PAGE_SIZE ||
+				((size & (size - 1)) &&
+				(1 << fls(size)) - size > 3*BYTES_PER_WORD))
 		flags |= SLAB_RED_ZONE|SLAB_STORE_USER;
 	flags |= SLAB_POISON;
 #endif

Re: slab redzoning

[Manfred Spraul]

William Lee Irwin III wrote:

>-if ((size < 4096 || fls(size-1) == fls(size-1+3*BYTES_PER_WORD)))
>+if (size + 3*BYTES_PER_WORD <= PAGE_SIZE ||
>
I understand this change: objects between 4082 and 4095 bytes are 
redzoned and cause order==1 allocations, that's wrong.

>+			((size & (size - 1)) &&
>+			(1 << fls(size)) - size > 3*BYTES_PER_WORD))
>
Why this change? I've tested my fls(size-1)==fls(size-1-3*4) approach 
and it always returned the right result: No redzoning between 8181 and 
8192 bytes, between 16373 and 16384, etc.

--
    Manfred

Re: slab redzoning

[William Lee Irwin III]

William Lee Irwin III wrote:
>>-if ((size < 4096 || fls(size-1) == fls(size-1+3*BYTES_PER_WORD)))
>>+if (size + 3*BYTES_PER_WORD <= PAGE_SIZE ||

On Sat, May 22, 2004 at 10:02:25AM +0200, Manfred Spraul wrote:
> I understand this change: objects between 4082 and 4095 bytes are 
> redzoned and cause order==1 allocations, that's wrong.

William Lee Irwin III wrote:
> >+			((size & (size - 1)) &&
> >+			(1 << fls(size)) - size > 3*BYTES_PER_WORD))

On Sat, May 22, 2004 at 10:02:25AM +0200, Manfred Spraul wrote:
> Why this change? I've tested my fls(size-1)==fls(size-1-3*4) approach 
> and it always returned the right result: No redzoning between 8181 and 
> 8192 bytes, between 16373 and 16384, etc.

It returns a false positive when size + 3*BYTES_PER_WORD == 2**n, e.g.
size == 16373. Here, fls(size - 1) == 13, but fls(size - 1 + 12) == 13
while size - 1 + 12 == 16384, where we'd want the check to fail. Or so
my analysis of it goes.

-- wli

Re: slab redzoning

[Manfred Spraul]

William Lee Irwin III wrote:

>On Sat, May 22, 2004 at 10:02:25AM +0200, Manfred Spraul wrote:
>  
>
>>Why this change? I've tested my fls(size-1)==fls(size-1-3*4) approach 
>>and it always returned the right result: No redzoning between 8181 and 
>>8192 bytes, between 16373 and 16384, etc.
>>    
>>
>
>It returns a false positive when size + 3*BYTES_PER_WORD == 2**n, e.g.
>size == 16373. Here, fls(size - 1) == 13, but fls(size - 1 + 12) == 13
>while size - 1 + 12 == 16384, where we'd want the check to fail.
>
No, 16373 must fail: After adding 12 bytes the object size would be 
16385, which would mean an order==3 allocation.
And 16372 must succeed: 16384 is still an order==2 allocation.

The idea is that there shouldn't be an allocation order increase due to 
redzoning, and afaics that doesn't happen, except between 4082 and 4095 
bytes.

--
    Manfred

Re: slab redzoning

[William Lee Irwin III]

William Lee Irwin III wrote:
>> It returns a false positive when size + 3*BYTES_PER_WORD == 2**n, e.g.
>> size == 16373. Here, fls(size - 1) == 13, but fls(size - 1 + 12) == 13
>> while size - 1 + 12 == 16384, where we'd want the check to fail.

On Sat, May 22, 2004 at 10:43:47AM +0200, Manfred Spraul wrote:
> No, 16373 must fail: After adding 12 bytes the object size would be 
> 16385, which would mean an order==3 allocation.
> And 16372 must succeed: 16384 is still an order==2 allocation.
> The idea is that there shouldn't be an allocation order increase due to 
> redzoning, and afaics that doesn't happen, except between 4082 and 4095 
> bytes.

Yes. While you've corrected the one-offs in my post (arithmetic is boring,
we have machines to do that for us now), 16372 remains in question as
far as I can tell.


-- wli

Re: slab redzoning

[Manfred Spraul]

[-- Attachment #1: Type: text/plain, Size: 1078 bytes --]

William Lee Irwin III wrote:

>William Lee Irwin III wrote:
>  
>
>>>It returns a false positive when size + 3*BYTES_PER_WORD == 2**n, e.g.
>>>size == 16373. Here, fls(size - 1) == 13, but fls(size - 1 + 12) == 13
>>>while size - 1 + 12 == 16384, where we'd want the check to fail.
>>>      
>>>
>
>On Sat, May 22, 2004 at 10:43:47AM +0200, Manfred Spraul wrote:
>  
>
>>No, 16373 must fail: After adding 12 bytes the object size would be 
>>16385, which would mean an order==3 allocation.
>>And 16372 must succeed: 16384 is still an order==2 allocation.
>>The idea is that there shouldn't be an allocation order increase due to 
>>redzoning, and afaics that doesn't happen, except between 4082 and 4095 
>>bytes.
>>    
>>
>
>Yes. While you've corrected the one-offs in my post (arithmetic is boring,
>we have machines to do that for us now)
>
I admit, I'm cheating:
I'd copied the test to user space and then tested all values between 32 
and 131072. 16372 passes:
fls(16371) == fls(16383).

I'll send a patch to Andrew to fix the range between 4084 and 4095.

--
    Manfred

[-- Attachment #2: test.c --]
[-- Type: text/x-csrc, Size: 714 bytes --]

#include <stdio.h>

#define BYTES_PER_WORD	4
#define PAGE_SIZE 4096

/*
 * fls: find last bit set.
 */

static int fls(int x)
{
	int r = 32;

	if (!x)
		return 0;
	if (!(x & 0xffff0000u)) {
		x <<= 16;
		r -= 16;
	}
	if (!(x & 0xff000000u)) {
		x <<= 8;
		r -= 8;
	}
	if (!(x & 0xf0000000u)) {
		x <<= 4;
		r -= 4;
	}
	if (!(x & 0xc0000000u)) {
		x <<= 2;
		r -= 2;
	}
	if (!(x & 0x80000000u)) {
		x <<= 1;
		r -= 1;
	}
	return r;
}

int main(void)
{
	int size;

	for (size=32;size<131073;size++) {
		if ((size <= PAGE_SIZE-3*BYTES_PER_WORD || fls(size-1) == fls(size-1+3*BYTES_PER_WORD))) {
			/* printf("%6d: no order change \n", size); */
		} else {
			printf("%6d: order change \n", size);
		}
	}
	return 0;
}