Skip to contentSkip to conversation

slab: kmalloc_size_roundup() must not return 0 for non-zero size

PATCH In review David Laight 3 participants 5 messages Sep 6, 2023 – Sep 7, 2023

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 slab: kmalloc_size_roundup() must not return 0 for non-zero size

The typical use of kmalloc_size_roundup() is:

	ptr = kmalloc(sz = kmalloc_size_roundup(size), ...);
	if (!ptr) return -ENOMEM.

This means it is vitally important that the returned value isn't less than the argument even if the argument is insane. In particular if kmalloc_slab() fails or the value is above (MAX_ULONG - PAGE_SIZE) zero is returned and kmalloc() will return it's single zero-length buffer.

Fix by returning the input size on error or if the size exceeds a 'sanity' limit.
kmalloc() will then return NULL is the size really is too big.

Fixes 05a940656e1eb ("slab: Introduce kmalloc_size_roundup()")

---
The 'sanity limit' value doesn't really matter (even if too small) It could be 'MAX_ORDER + PAGE_SHIFT' but one ppc64 has MAX_ORDER 16 and I don't know if that also has large pages.
Maybe it could be 1ul << 30 on 64bit, but it really doesn't matter if it is too big.

The original patch also added kmalloc_size_roundup() to mm/slob.c that can also round up a value to zero - but has since been removed.

 mm/slab_common.c | 29 ++++++++++++++---------------
 1 file changed, 14 insertions(+), 15 deletions(-)
mm/slab_common.c +14 -15
index cd71f9581e67..8418eccda8cf 100644
@@ -747,22 +747,21 @@ size_t kmalloc_size_roundup(size_t size)
 {
 	struct kmem_cache *c;
 
-	/* Short-circuit the 0 size case. */
-	if (unlikely(size == 0))
-		return 0;
-	/* Short-circuit saturated "too-large" case. */
-	if (unlikely(size == SIZE_MAX))
-		return SIZE_MAX;
-	/* Above the smaller buckets, size is a multiple of page size. */
-	if (size > KMALLOC_MAX_CACHE_SIZE)
-		return PAGE_SIZE << get_order(size);
+	if (size && size <= KMALLOC_MAX_CACHE_SIZE) {
+		/*
+		 * The flags don't matter since size_index is common to all.
+		 * Neither does the caller for just getting ->object_size.
+		 */
+		c = kmalloc_slab(size, GFP_KERNEL, 0);
+		return likely(c) ? c->object_size : size;
+	}
 
-	/*
-	 * The flags don't matter since size_index is common to all.
-	 * Neither does the caller for just getting ->object_size.
-	 */
-	c = kmalloc_slab(size, GFP_KERNEL, 0);
-	return c ? c->object_size : 0;
+	/* Return 'size' for 0 and very large - kmalloc() may fail. */
+	if (unlikely((size - 1) >> (sizeof (long) == 8 ? 34 : 30)))
+		return size;
+
+	/* Above the smaller buckets, size is a multiple of page size. */
+	return PAGE_SIZE << get_order(size);
 }
 EXPORT_SYMBOL(kmalloc_size_roundup);
 
Signature · 5 lines
2.17.1

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)
#1 lore raw

Please Cc: also R: folks in MAINTAINERS, adding them now.

Quoted 13 lines · David Laight

The typical use of kmalloc_size_roundup() is:

	ptr = kmalloc(sz = kmalloc_size_roundup(size), ...);
	if (!ptr) return -ENOMEM.

This means it is vitally important that the returned value isn't less than the argument even if the argument is insane. In particular if kmalloc_slab() fails or the value is above (MAX_ULONG - PAGE_SIZE) zero is returned and kmalloc() will return it's single zero-length buffer.

Fix by returning the input size on error or if the size exceeds a 'sanity' limit.
kmalloc() will then return NULL is the size really is too big.

Quoted 6 lines
Fixes 05a940656e1eb ("slab: Introduce kmalloc_size_roundup()")

---
The 'sanity limit' value doesn't really matter (even if too small) It could be 'MAX_ORDER + PAGE_SHIFT' but one ppc64 has MAX_ORDER 16 and I don't know if that also has large pages.

Well we do have KMALLOC_MAX_SIZE, which is based on MAX_ORDER + PAGE_SHIFT (and no issues on ppc64 so I'd expect the combination of MAX_ORDER and PAGE_SHIFT should always be such that it doesn't overflow on the particular arch) so I think it would be the most straightforward to simply use that.

Quoted 17 lines

Maybe it could be 1ul << 30 on 64bit, but it really doesn't matter if it is too big.

The original patch also added kmalloc_size_roundup() to mm/slob.c that can also round up a value to zero - but has since been removed.

 mm/slab_common.c | 29 ++++++++++++++---------------
 1 file changed, 14 insertions(+), 15 deletions(-)
mm/slab_common.c +0 -0
index cd71f9581e67..8418eccda8cf 100644
@@ -747,22 +747,21 @@ size_t kmalloc_size_roundup(size_t size)
 {
 	struct kmem_cache *c;
 

mm/slab_common.c size_t kmalloc_size_roundup(size_t size) · line 750

Quoted 10 lines
mm/slab_common.c +1 -9
-	/* Short-circuit the 0 size case. */
-	if (unlikely(size == 0))
-		return 0;
-	/* Short-circuit saturated "too-large" case. */
-	if (unlikely(size == SIZE_MAX))
-		return SIZE_MAX;
-	/* Above the smaller buckets, size is a multiple of page size. */
-	if (size > KMALLOC_MAX_CACHE_SIZE)
-		return PAGE_SIZE << get_order(size);
+	if (size && size <= KMALLOC_MAX_CACHE_SIZE) {

I guess the whole test could all be likely().

Also this patch could probably be just replacing the SIZE_MAX test with >= KMALLOC_MAX_SIZE, but since the majority is expected to be 0 < size <= KMALLOC_MAX_CACHE_SIZE, your reordering makes sense to me.

Quoted 6 lines
mm/slab_common.c +6 -0
+		/*
+		 * The flags don't matter since size_index is common to all.
+		 * Neither does the caller for just getting ->object_size.
+		 */
+		c = kmalloc_slab(size, GFP_KERNEL, 0);
+		return likely(c) ? c->object_size : size;

mm/slab_common.c size_t kmalloc_size_roundup(size_t size) · line 760

Quoted 10 lines
mm/slab_common.c +3 -6
+	}
 
-	/*
-	 * The flags don't matter since size_index is common to all.
-	 * Neither does the caller for just getting ->object_size.
-	 */
-	c = kmalloc_slab(size, GFP_KERNEL, 0);
-	return c ? c->object_size : 0;
+	/* Return 'size' for 0 and very large - kmalloc() may fail. */
+	if (unlikely((size - 1) >> (sizeof (long) == 8 ? 34 : 30)))

So I'd just test for size == 0 || size > KMALLOC_MAX_SIZE?

Quoted 7 lines
mm/slab_common.c +4 -0
+		return size;
+
+	/* Above the smaller buckets, size is a multiple of page size. */
+	return PAGE_SIZE << get_order(size);
 }
 EXPORT_SYMBOL(kmalloc_size_roundup);
 
#2 lore raw

From: Vlastimil Babka

Quoted 25 lines

Sent: 06 September 2023 09:48

Please Cc: also R: folks in MAINTAINERS, adding them now.

Quoted 13 lines · David Laight

The typical use of kmalloc_size_roundup() is:

	ptr = kmalloc(sz = kmalloc_size_roundup(size), ...);
	if (!ptr) return -ENOMEM.

This means it is vitally important that the returned value isn't less than the argument even if the argument is insane. In particular if kmalloc_slab() fails or the value is above (MAX_ULONG - PAGE_SIZE) zero is returned and kmalloc() will return it's single zero-length buffer.

Fix by returning the input size on error or if the size exceeds a 'sanity' limit.
kmalloc() will then return NULL is the size really is too big.

Quoted 6 lines
Fixes 05a940656e1eb ("slab: Introduce kmalloc_size_roundup()")

---
The 'sanity limit' value doesn't really matter (even if too small) It could be 'MAX_ORDER + PAGE_SHIFT' but one ppc64 has MAX_ORDER 16 and I don't know if that also has large pages.

Quoted 4 lines

Well we do have KMALLOC_MAX_SIZE, which is based on MAX_ORDER + PAGE_SHIFT (and no issues on ppc64 so I'd expect the combination of MAX_ORDER and PAGE_SHIFT should always be such that it doesn't overflow on the particular arch) so I think it would be the most straightforward to simply use that.

Searching all the consta
nts gets hard :-)

Quoted 31 lines
Quoted 18 lines

Maybe it could be 1ul << 30 on 64bit, but it really doesn't matter if it is too big.

The original patch also added kmalloc_size_roundup() to mm/slob.c that can also round up a value to zero - but has since been removed.

 mm/slab_common.c | 29 ++++++++++++++---------------
 1 file changed, 14 insertions(+), 15 deletions(-)
mm/slab_common.c +0 -0
index cd71f9581e67..8418eccda8cf 100644
@@ -747,22 +747,21 @@ size_t kmalloc_size_roundup(size_t size)
 {
 	struct kmem_cache *c;
 

mm/slab_common.c size_t kmalloc_size_roundup(size_t size) · line 750

Quoted 10 lines
mm/slab_common.c +1 -9
-	/* Short-circuit the 0 size case. */
-	if (unlikely(size == 0))
-		return 0;
-	/* Short-circuit saturated "too-large" case. */
-	if (unlikely(size == SIZE_MAX))
-		return SIZE_MAX;
-	/* Above the smaller buckets, size is a multiple of page size. */
-	if (size > KMALLOC_MAX_CACHE_SIZE)
-		return PAGE_SIZE << get_order(size);
+	if (size && size <= KMALLOC_MAX_CACHE_SIZE) {

I guess the whole test could all be likely().

Quoted 3 lines

Also this patch could probably be just replacing the SIZE_MAX test with >= KMALLOC_MAX_SIZE, but since the majority is expected to be 0 < size <= KMALLOC_MAX_CACHE_SIZE, your reordering makes sense to me.

I re-ordered it because there are three cases and it didn't make any sense to have two of them inside the first conditional.
In particular it made the comments easier to write!

Optimising for 'size == 0' (the unlikely() makes little difference) is completely insane.
The compiler optimises 'if (size && size <= constant)' to 'if ((size - 1) < constant)' so you lose a conditional branch in the hot paths

Quoted 8 lines
Quoted 8 lines
mm/slab_common.c +7 -0
+		/*
+		 * The flags don't matter since size_index is common to all.
+		 * Neither does the caller for just getting ->object_size.
+		 */
+		c = kmalloc_slab(size, GFP_KERNEL, 0);
+		return likely(c) ? c->object_size : size;
+	}
 
Quoted 10 lines

mm/slab_common.c size_t kmalloc_size_roundup(size_t size) · line 760

Quoted 8 lines
mm/slab_common.c +2 -6
-	/*
-	 * The flags don't matter since size_index is common to all.
-	 * Neither does the caller for just getting ->object_size.
-	 */
-	c = kmalloc_slab(size, GFP_KERNEL, 0);
-	return c ? c->object_size : 0;
+	/* Return 'size' for 0 and very large - kmalloc() may fail. */
+	if (unlikely((size - 1) >> (sizeof (long) == 8 ? 34 : 30)))

So I'd just test for size == 0 || size > KMALLOC_MAX_SIZE?

That does generate better code, but on some arch adding 1 might make the constant (eg) 0x400000 not 0x3fffff and easier to generate.

Actually, for consistency, it might be best to invert the second compare as well.

I'll edit the patch to generate a v2 later.

David

Quoted 8 lines

mm/slab_common.c size_t kmalloc_size_roundup(size_t size) · line 767

Quoted 8 lines
mm/slab_common.c +4 -0
+		return size;
+
+	/* Above the smaller buckets, size is a multiple of page size. */
+	return PAGE_SIZE << get_order(size);
 }
 EXPORT_SYMBOL(kmalloc_size_roundup);
 

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)

#3 lore raw
In reply to David Laight
Quoted 13 lines · David Laight

The typical use of kmalloc_size_roundup() is:

	ptr = kmalloc(sz = kmalloc_size_roundup(size), ...);
	if (!ptr) return -ENOMEM.

This means it is vitally important that the returned value isn't less than the argument even if the argument is insane. In particular if kmalloc_slab() fails or the value is above (MAX_ULONG - PAGE_SIZE) zero is returned and kmalloc() will return it's single zero-length buffer.

Fix by returning the input size on error or if the size exceeds a 'sanity' limit.
kmalloc() will then return NULL is the size really is too big.

Quoted 8 lines
Fixes 05a940656e1eb ("slab: Introduce kmalloc_size_roundup()")

---
The 'sanity limit' value doesn't really matter (even if too small) It could be 'MAX_ORDER + PAGE_SHIFT' but one ppc64 has MAX_ORDER 16 and I don't know if that also has large pages.
Maybe it could be 1ul << 30 on 64bit, but it really doesn't matter if it is too big.

I agree that returning 0 for an (impossible to reach) non-zero is wrong, but the problem seen in netdev was that a truncation happened for a value returned by kmalloc_size_roundup().

So, for the first, it shouldn't be possible for "c" to ever be NULL here:

	c = kmalloc_slab(size, GFP_KERNEL, 0);
	return c ? c->object_size : 0;

But sure, we can return KMALLOC_MAX_SIZE for that.

The pathological case was this:

	unsigned int truncated;
	size_t fullsize = UINT_MAX + 1;

ptr = kmalloc(truncated = kmalloc_size_roundup(fullsize), ...);

Should the logic be changed to return KMALLOC_MAX_SIZE for anything larger than KMALLOC_MAX_SIZE? This seems like a different kind of foot-gun.

Everything else in the allocator sanity checking (e.g. struct_size(), etc) uses SIZE_MAX as the saturation value, which is why kmalloc_size_roundup() did too.

Signature · 1 line
Kees Cook
#4 lore raw

From: Kees Cook

Quoted 25 lines

Sent: 06 September 2023 19:17

Quoted 13 lines · David Laight

The typical use of kmalloc_size_roundup() is:

	ptr = kmalloc(sz = kmalloc_size_roundup(size), ...);
	if (!ptr) return -ENOMEM.

This means it is vitally important that the returned value isn't less than the argument even if the argument is insane. In particular if kmalloc_slab() fails or the value is above (MAX_ULONG - PAGE_SIZE) zero is returned and kmalloc() will return it's single zero-length buffer.

Fix by returning the input size on error or if the size exceeds a 'sanity' limit.
kmalloc() will then return NULL is the size really is too big.

Quoted 8 lines
Fixes 05a940656e1eb ("slab: Introduce kmalloc_size_roundup()")

---
The 'sanity limit' value doesn't really matter (even if too small) It could be 'MAX_ORDER + PAGE_SHIFT' but one ppc64 has MAX_ORDER 16 and I don't know if that also has large pages.
Maybe it could be 1ul << 30 on 64bit, but it really doesn't matter if it is too big.

Quoted 5 lines

I agree that returning 0 for an (impossible to reach) non-zero is wrong, but the problem seen in netdev was that a truncation happened for a value returned by kmalloc_size_roundup().

So, for the first, it shouldn't be possible for "c" to ever be NULL here:

If it isn't possible there is no need to check :-)

Quoted 5 lines
	c = kmalloc_slab(size, GFP_KERNEL, 0);
	return c ? c->object_size : 0;

But sure, we can return KMALLOC_MAX_SIZE for that.

Isn't KMALLOC_MAX_SIZE actually valid? - so would be wrong. Returning 'size' is always valid, the later kmalloc() will almost certainly fail, but it is also ok if it suceeds.

Quoted 1 line

The pathological case was this:

s/pathological/failing/

Quoted 5 lines
	unsigned int truncated;
	size_t fullsize = UINT_MAX + 1;

ptr = kmalloc(truncated = kmalloc_size_roundup(fullsize), ...);

The actual pathological case is:

	kmalloc(kmalloc_size_roundup(~0ULL - PAGESIZE/2), ...)

which is kmalloc(0, ...) and suceeds.

Quoted 7 lines

Should the logic be changed to return KMALLOC_MAX_SIZE for anything larger than KMALLOC_MAX_SIZE? This seems like a different kind of foot-gun.

Everything else in the allocator sanity checking (e.g. struct_size(), etc) uses SIZE_MAX as the saturation value, which is why kmalloc_size_roundup() did too.

SIZE_MAX (aka ~0ull) seems far too large for sanity checking lengths. (Even without the issue of having no headroom.)

A limit related to an upper bound for vmalloc() would probably be more appropriate, or maybe just a limit based on kernel VA. So for 32bit 2^30 is way too large for any kind of allocate. For 64bit you can go higher (even if the allocators can't support the values), maybe 2^48?

David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK Registration No: 1397386 (Wales)