Skip to contentSkip to conversation

slab redzoning

PATCH William Lee Irwin III 2 participants 6 messages May 22, 2004 Memory management

lore
Share & tools
lore
#0 lore raw

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.

mm/slab.c +14 -1
Index: mm4-2.6.6/mm/slab.c
===================================================================
@@ -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
#1 lore raw

mm/slab.c line 1173

Quoted 3 lines · William Lee Irwin III
mm/slab.c +1 -1
-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.

mm/slab.c line 1175

Quoted 3 lines
mm/slab.c +2 -0
+			((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

#2 lore raw
Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
mm/slab.c +1 -1
-if ((size < 4096 || fls(size-1) == fls(size-1+3*BYTES_PER_WORD)))
+if (size + 3*BYTES_PER_WORD <= PAGE_SIZE ||
Quoted 2 lines · Manfred Spraul

I understand this change: objects between 4082 and 4095 bytes are redzoned and cause order==1 allocations, that's wrong.

Quoted 2 lines · William Lee Irwin III
Quoted 2 lines
mm/slab.c +2 -0
+			((size & (size - 1)) &&
+			(1 << fls(size)) - size > 3*BYTES_PER_WORD))
Quoted 3 lines · Manfred Spraul

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

#3 lore raw
Quoted 11 lines · William Lee Irwin III
Quoted 3 lines · Manfred Spraul

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

#4 lore raw
Quoted 3 lines · William Lee Irwin III
Quoted 3 lines

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.

Quoted 6 lines · Manfred Spraul

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

#5 lore raw
Quoted 12 lines · William Lee Irwin III
Quoted 5 lines · William Lee Irwin III
Quoted 5 lines

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:

Quoted 9 lines
Quoted 5 lines

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

#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;
}