[RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[Tetsuo Handa]

[RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

kmalloc() and friends are sometimes used in a way

	struct foo *ptr = kmalloc(size + sizeof(struct foo), GFP_KERNEL);
	if (!ptr)
		return -ENOMEM;
	ptr->size = size;
	...
	return 0;

Everybody should check for ptr != NULL, and most callers are actually checking
for ptr != NULL. But nobody is checking for ptr != ZERO_SIZE_PTR.

If caller passed 0 as size argument by error (e.g. integer overflow bug),
the caller will start writing against address starting from ZERO_SIZE_PTR
because the caller assumes that "size + sizeof(struct foo)" bytes of memory is
successfully allocated. (kstrdup() is an example, although it will be
impossible to pass s where strlen(s) == (size_t) -1 .)

Yes, this is the fault of caller. But ZERO_SIZE_PTR is too small value to
distinguish "NULL pointer dereference" and "ZERO_SIZE_PTR dereference" because
address printed by oops message can easily exceed ZERO_SIZE_PTR when
"struct foo" is large.

Therefore, at the cost of being unable to distinguish "NULL pointer
dereference" and "ZERO_SIZE_PTR dereference" in some cases, removing
ZERO_SIZE_PTR could reduce the risk of "ZERO_SIZE_PTR dereference" in many
cases.

Signed-off-by: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
---
 include/linux/slab.h     |   12 ------------
 include/linux/slab_def.h |    4 ++--
 include/linux/slub_def.h |    4 ++--
 mm/slab.c                |   12 +++++-------
 mm/slob.c                |    8 +++-----
 mm/slub.c                |   15 ++++++---------
 mm/util.c                |    6 +++---
 7 files changed, 21 insertions(+), 40 deletions(-)

--- linux-2.6.33.orig/include/linux/slab.h
+++ linux-2.6.33/include/linux/slab.h
@@ -74,18 +74,6 @@
 /* The following flags affect the page allocator grouping pages by mobility */
 #define SLAB_RECLAIM_ACCOUNT	0x00020000UL		/* Objects are reclaimable */
 #define SLAB_TEMPORARY		SLAB_RECLAIM_ACCOUNT	/* Objects are short-lived */
-/*
- * ZERO_SIZE_PTR will be returned for zero sized kmalloc requests.
- *
- * Dereferencing ZERO_SIZE_PTR will lead to a distinct access fault.
- *
- * ZERO_SIZE_PTR can be passed to kfree though in the same way that NULL can.
- * Both make kfree a no-op.
- */
-#define ZERO_SIZE_PTR ((void *)16)
-
-#define ZERO_OR_NULL_PTR(x) ((unsigned long)(x) <= \
-				(unsigned long)ZERO_SIZE_PTR)
 
 /*
  * struct kmem_cache related prototypes
--- linux-2.6.33.orig/include/linux/slab_def.h
+++ linux-2.6.33/include/linux/slab_def.h
@@ -134,7 +134,7 @@ static __always_inline void *kmalloc(siz
 		int i = 0;
 
 		if (!size)
-			return ZERO_SIZE_PTR;
+			return NULL;
 
 #define CACHE(x) \
 		if (size <= x) \
@@ -189,7 +189,7 @@ static __always_inline void *kmalloc_nod
 		int i = 0;
 
 		if (!size)
-			return ZERO_SIZE_PTR;
+			return NULL;
 
 #define CACHE(x) \
 		if (size <= x) \
--- linux-2.6.33.orig/include/linux/slub_def.h
+++ linux-2.6.33/include/linux/slub_def.h
@@ -250,7 +250,7 @@ static __always_inline void *kmalloc(siz
 			struct kmem_cache *s = kmalloc_slab(size);
 
 			if (!s)
-				return ZERO_SIZE_PTR;
+				return NULL;
 
 			ret = kmem_cache_alloc_notrace(s, flags);
 
@@ -289,7 +289,7 @@ static __always_inline void *kmalloc_nod
 			struct kmem_cache *s = kmalloc_slab(size);
 
 		if (!s)
-			return ZERO_SIZE_PTR;
+			return NULL;
 
 		ret = kmem_cache_alloc_node_notrace(s, flags, node);
 
--- linux-2.6.33.orig/mm/slab.c
+++ linux-2.6.33/mm/slab.c
@@ -717,7 +717,7 @@ static inline struct kmem_cache *__find_
 	BUG_ON(malloc_sizes[INDEX_AC].cs_cachep == NULL);
 #endif
 	if (!size)
-		return ZERO_SIZE_PTR;
+		return NULL;
 
 	while (size > csizep->cs_size)
 		csizep++;
@@ -2346,7 +2346,7 @@ kmem_cache_create (const char *name, siz
 		 * this should not happen at all.
 		 * But leave a BUG_ON for some lucky dude.
 		 */
-		BUG_ON(ZERO_OR_NULL_PTR(cachep->slabp_cache));
+		BUG_ON(!cachep->slabp_cache);
 	}
 	cachep->ctor = ctor;
 	cachep->name = name;
@@ -3661,7 +3661,7 @@ __do_kmalloc_node(size_t size, gfp_t fla
 	void *ret;
 
 	cachep = kmem_find_general_cachep(size, flags);
-	if (unlikely(ZERO_OR_NULL_PTR(cachep)))
+	if (unlikely(!cachep))
 		return cachep;
 	ret = kmem_cache_alloc_node_notrace(cachep, flags, node);
 
@@ -3712,7 +3712,7 @@ static __always_inline void *__do_kmallo
 	 * functions.
 	 */
 	cachep = __find_general_cachep(size, flags);
-	if (unlikely(ZERO_OR_NULL_PTR(cachep)))
+	if (unlikely(!cachep))
 		return cachep;
 	ret = __cache_alloc(cachep, flags, caller);
 
@@ -3783,7 +3783,7 @@ void kfree(const void *objp)
 
 	trace_kfree(_RET_IP_, objp);
 
-	if (unlikely(ZERO_OR_NULL_PTR(objp)))
+	if (unlikely(!objp))
 		return;
 	local_irq_save(flags);
 	kfree_debugcheck(objp);
@@ -4519,8 +4519,6 @@ module_init(slab_proc_init);
 size_t ksize(const void *objp)
 {
 	BUG_ON(!objp);
-	if (unlikely(objp == ZERO_SIZE_PTR))
-		return 0;
 
 	return obj_size(virt_to_cache(objp));
 }
--- linux-2.6.33.orig/mm/slob.c
+++ linux-2.6.33/mm/slob.c
@@ -395,7 +395,7 @@ static void slob_free(void *block, int s
 	slobidx_t units;
 	unsigned long flags;
 
-	if (unlikely(ZERO_OR_NULL_PTR(block)))
+	if (unlikely(!block))
 		return;
 	BUG_ON(!size);
 
@@ -485,7 +485,7 @@ void *__kmalloc_node(size_t size, gfp_t 
 
 	if (size < PAGE_SIZE - align) {
 		if (!size)
-			return ZERO_SIZE_PTR;
+			return NULL;
 
 		m = slob_alloc(size + align, gfp, align, node);
 
@@ -521,7 +521,7 @@ void kfree(const void *block)
 
 	trace_kfree(_RET_IP_, block);
 
-	if (unlikely(ZERO_OR_NULL_PTR(block)))
+	if (unlikely(!block))
 		return;
 	kmemleak_free(block);
 
@@ -541,8 +541,6 @@ size_t ksize(const void *block)
 	struct slob_page *sp;
 
 	BUG_ON(!block);
-	if (unlikely(block == ZERO_SIZE_PTR))
-		return 0;
 
 	sp = slob_page(block);
 	if (is_slob_page(sp)) {
--- linux-2.6.33.orig/mm/slub.c
+++ linux-2.6.33/mm/slub.c
@@ -2836,7 +2836,7 @@ static struct kmem_cache *get_slab(size_
 
 	if (size <= 192) {
 		if (!size)
-			return ZERO_SIZE_PTR;
+			return NULL;
 
 		index = size_index[size_index_elem(size)];
 	} else
@@ -2860,7 +2860,7 @@ void *__kmalloc(size_t size, gfp_t flags
 
 	s = get_slab(size, flags);
 
-	if (unlikely(ZERO_OR_NULL_PTR(s)))
+	if (unlikely(!s))
 		return s;
 
 	ret = slab_alloc(s, flags, -1, _RET_IP_);
@@ -2903,7 +2903,7 @@ void *__kmalloc_node(size_t size, gfp_t 
 
 	s = get_slab(size, flags);
 
-	if (unlikely(ZERO_OR_NULL_PTR(s)))
+	if (unlikely(!s))
 		return s;
 
 	ret = slab_alloc(s, flags, node, _RET_IP_);
@@ -2920,9 +2920,6 @@ size_t ksize(const void *object)
 	struct page *page;
 	struct kmem_cache *s;
 
-	if (unlikely(object == ZERO_SIZE_PTR))
-		return 0;
-
 	page = virt_to_head_page(object);
 
 	if (unlikely(!PageSlab(page))) {
@@ -2961,7 +2958,7 @@ void kfree(const void *x)
 
 	trace_kfree(_RET_IP_, x);
 
-	if (unlikely(ZERO_OR_NULL_PTR(x)))
+	if (unlikely(!x))
 		return;
 
 	page = virt_to_head_page(x);
@@ -3468,7 +3465,7 @@ void *__kmalloc_track_caller(size_t size
 
 	s = get_slab(size, gfpflags);
 
-	if (unlikely(ZERO_OR_NULL_PTR(s)))
+	if (unlikely(!s))
 		return s;
 
 	ret = slab_alloc(s, gfpflags, -1, caller);
@@ -3490,7 +3487,7 @@ void *__kmalloc_node_track_caller(size_t
 
 	s = get_slab(size, gfpflags);
 
-	if (unlikely(ZERO_OR_NULL_PTR(s)))
+	if (unlikely(!s))
 		return s;
 
 	ret = slab_alloc(s, gfpflags, node, caller);
--- linux-2.6.33.orig/mm/util.c
+++ linux-2.6.33/mm/util.c
@@ -118,7 +118,7 @@ void *__krealloc(const void *p, size_t n
 	size_t ks = 0;
 
 	if (unlikely(!new_size))
-		return ZERO_SIZE_PTR;
+		return NULL;
 
 	if (p)
 		ks = ksize(p);
@@ -151,7 +151,7 @@ void *krealloc(const void *p, size_t new
 
 	if (unlikely(!new_size)) {
 		kfree(p);
-		return ZERO_SIZE_PTR;
+		return NULL;
 	}
 
 	ret = __krealloc(p, new_size, flags);
@@ -178,7 +178,7 @@ void kzfree(const void *p)
 	size_t ks;
 	void *mem = (void *)p;
 
-	if (unlikely(ZERO_OR_NULL_PTR(mem)))
+	if (unlikely(!mem))
 		return;
 	ks = ksize(mem);
 	memset(mem, 0, ks);

Re: [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[KOSAKI Motohiro]

> [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.
> 
> kmalloc() and friends are sometimes used in a way
> 
> 	struct foo *ptr = kmalloc(size + sizeof(struct foo), GFP_KERNEL);
> 	if (!ptr)
> 		return -ENOMEM;
> 	ptr->size = size;
> 	...
> 	return 0;
> 
> Everybody should check for ptr != NULL, and most callers are actually checking
> for ptr != NULL. But nobody is checking for ptr != ZERO_SIZE_PTR.
> 
> If caller passed 0 as size argument by error (e.g. integer overflow bug),
> the caller will start writing against address starting from ZERO_SIZE_PTR
> because the caller assumes that "size + sizeof(struct foo)" bytes of memory is
> successfully allocated. (kstrdup() is an example, although it will be
> impossible to pass s where strlen(s) == (size_t) -1 .)
> 
> Yes, this is the fault of caller. But ZERO_SIZE_PTR is too small value to
> distinguish "NULL pointer dereference" and "ZERO_SIZE_PTR dereference" because
> address printed by oops message can easily exceed ZERO_SIZE_PTR when
> "struct foo" is large.
> 
> Therefore, at the cost of being unable to distinguish "NULL pointer
> dereference" and "ZERO_SIZE_PTR dereference" in some cases, removing
> ZERO_SIZE_PTR could reduce the risk of "ZERO_SIZE_PTR dereference" in many
> cases.

NAK. yes, it could. but it is no worth. nobody want slower kernel.

Re: [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[David Wagner]

Tetsuo Handa  wrote:
>[RFC][PATCH] mm: Remove ZERO_SIZE_PTR.
>
>kmalloc() and friends are sometimes used in a way
>
>	struct foo *ptr = kmalloc(size + sizeof(struct foo), GFP_KERNEL);
>	if (!ptr)
>		return -ENOMEM;
>	ptr->size = size;
>	...
>	return 0;
>
>Everybody should check for ptr != NULL, and most callers are actually checking
>for ptr != NULL. But nobody is checking for ptr != ZERO_SIZE_PTR.
>
>If caller passed 0 as size argument by error (e.g. integer overflow bug),
>the caller will start writing against address starting from ZERO_SIZE_PTR
>because the caller assumes that "size + sizeof(struct foo)" bytes of memory is
>successfully allocated. (kstrdup() is an example, although it will be
>impossible to pass s where strlen(s) == (size_t) -1 .)

I don't see how your patch solves the problem.

Case 1: As you point out, if size = -sizeof(struct foo), then we'll have
an integer overflow and allocate a 0-byte object.  Later operations will
likely write past the bounds of the allocated object.

Case 2: It's also true that if size = -sizeof(struct foo) + 1, that
will also trigger an integer overflow and will allocate a 1-byte object.
Consequently later operations will likely write past the bounds of the
allocated object.

Changing the behavior of kmalloc(0, .) does nothing about the
second case.  Any code that is vulnerable to Case 1 is also vulnerable
to Case 2.  The consequence of the two cases is identical: in both
cases, there is an out-of-bounds write (which might pose, for
instance, a security risk, or might trigger a crash).

I don't see the point of trying to address Case 1 without doing
anything about Case 2.  Is there something that would make Case 1
significantly more likely to occur by chance than Case 2?

So what should the kernel do about the risk of this kind of integer
overflow bugs?  I can see three possible strategies:

Strategy 1: Be really careful.  Don't introduce any code that has
this kind of integer overflow bug.  (Downside: Nobody is perfect.
It's easy to introduce an integer overflow bug without realizing it.)

Strategy 2: Try to modify kmalloc() to detect these bugs.
However, it's not clear that there is any good robust strategy
here.  I certainly don't have a concrete proposal.
(For instance, one thing that I'm told MS Visual C does is to
make malloc() a macro that checks the processor overflow/carry
flag on its length argument at runtime -- this doesn't catch all
integer overflow bugs but might catch some of them.  But it's a
bit of a hack.)

Strategy 3: Build static or runtime analysis tools to detect
these kinds of bugs.  The problem is that static analysis tools
generally find it difficult to reason about integer overflow,
without either missing many bugs or introducing many false
positives.  Sophisticated runtime tools might be in a better
position to detect these bugs (for instance, I've done some
research on tools for detecting integer overflow bugs using
symbolic execution and smart fuzzing), but they are non-trivial
to build.

Re: [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[Tetsuo Handa]

KOSAKI Motohiro wrote:
> > Therefore, at the cost of being unable to distinguish "NULL pointer
> > dereference" and "ZERO_SIZE_PTR dereference" in some cases, removing
> > ZERO_SIZE_PTR could reduce the risk of "ZERO_SIZE_PTR dereference" in many
> > cases.
> 
> NAK. yes, it could. but it is no worth. nobody want slower kernel.
> 
This patch simplifies error checks of both callers/callees from

	((unsigned long)(x) <= (unsigned long) 16)

to

	!(x)

. Why this patch makes the kernel slower?

Re: [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[KOSAKI Motohiro]

> KOSAKI Motohiro wrote:
> > > Therefore, at the cost of being unable to distinguish "NULL pointer
> > > dereference" and "ZERO_SIZE_PTR dereference" in some cases, removing
> > > ZERO_SIZE_PTR could reduce the risk of "ZERO_SIZE_PTR dereference" in many
> > > cases.
> > 
> > NAK. yes, it could. but it is no worth. nobody want slower kernel.
> > 
> This patch simplifies error checks of both callers/callees from
> 
> 	((unsigned long)(x) <= (unsigned long) 16)
> 
> to
> 
> 	!(x)
> 
> . Why this patch makes the kernel slower?

You misunderstand your patch's effect. you try to change kmalloc
semantics. currently kmalloc(0) is valid and allowed. but you want
to change invalid. then, we need additional check into the caller of
using kmalloc(0). there is in real world.

IOW, your patch is broken and introduce incompatibility.

Re: [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[Christoph Lameter]

On Fri, 26 Feb 2010, Tetsuo Handa wrote:

> Everybody should check for ptr != NULL, and most callers are actually checking
> for ptr != NULL. But nobody is checking for ptr != ZERO_SIZE_PTR.

That is so intentionally because some kernel subsystem can do a zero size
allocation.

> If caller passed 0 as size argument by error (e.g. integer overflow bug),
> the caller will start writing against address starting from ZERO_SIZE_PTR
> because the caller assumes that "size + sizeof(struct foo)" bytes of memory is
> successfully allocated. (kstrdup() is an example, although it will be
> impossible to pass s where strlen(s) == (size_t) -1 .)

Therefore you will get a NULL deference error since ZERO_SIZE_PTR points
to the NULL page.

> Yes, this is the fault of caller. But ZERO_SIZE_PTR is too small value to
> distinguish "NULL pointer dereference" and "ZERO_SIZE_PTR dereference" because
> address printed by oops message can easily exceed ZERO_SIZE_PTR when
> "struct foo" is large.

Correct.

But you can check for <= ZERO_SIZE_PTR to check for NULL or ZERO_SIZE_PTR
in the same comparison if necessary.

Re: [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[David Wagner]

Tetsuo Handa  wrote:
>This patch simplifies error checks of both callers/callees from
>
>	((unsigned long)(x) <= (unsigned long) 16)
>
>to
>
>	!(x)

I don't follow.  If you want to avoid integer overflow, the caller
of kmalloc() must check to make sure that the arithmetic operations
it performs do not overflow.  That's true whether or not your patch
is accepted.  An integer overflow in an arithmetic operation can yield
a non-zero value, so checking "!(x)" does not guarantee that there was
no integer overflow involved in the computation of x.

Re: [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[Tetsuo Handa]

Christoph Lameter wrote:
> On Fri, 26 Feb 2010, Tetsuo Handa wrote:
> 
> > Everybody should check for ptr != NULL, and most callers are actually checking
> > for ptr != NULL. But nobody is checking for ptr != ZERO_SIZE_PTR.
> 
> That is so intentionally because some kernel subsystem can do a zero size
> allocation.
> 
So, not only users *can* do zero size allocation,
but also there *are* users who are intentionally doing zero size allocation.
Then, we can't remove ZERO_SIZE_PTR.

> > Yes, this is the fault of caller. But ZERO_SIZE_PTR is too small value to
> > distinguish "NULL pointer dereference" and "ZERO_SIZE_PTR dereference" because
> > address printed by oops message can easily exceed ZERO_SIZE_PTR when
> > "struct foo" is large.
> 
> Correct.

Maybe PAGE_SIZE / 2 is better than 16?

Thanks.

Re: [RFC][PATCH] mm: Remove ZERO_SIZE_PTR.

[Pavel Machek]

Hi!

> > > Everybody should check for ptr != NULL, and most callers are actually checking
> > > for ptr != NULL. But nobody is checking for ptr != ZERO_SIZE_PTR.
> > 
> > That is so intentionally because some kernel subsystem can do a zero size
> > allocation.
> > 
> So, not only users *can* do zero size allocation,
> but also there *are* users who are intentionally doing zero size allocation.
> Then, we can't remove ZERO_SIZE_PTR.
> 
> > > Yes, this is the fault of caller. But ZERO_SIZE_PTR is too small value to
> > > distinguish "NULL pointer dereference" and "ZERO_SIZE_PTR dereference" because
> > > address printed by oops message can easily exceed ZERO_SIZE_PTR when
> > > "struct foo" is large.
> > 
> > Correct.
> 
> Maybe PAGE_SIZE / 2 is better than 16?

Actually maybe 1 is better than 16?

It is 'nicer' number, and <= ZERO_SIZE_PTR will actually be correct.

Accessing field it struct will also be easy to differentiate from NULL
pointer -- as most members are word aligned...

-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html