From: Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups: fa.linux.kernel
Subject: Re: [RFC] [PATCH] cpuset operations causes Badness at mm/slab.c:777
Date: Fri, 01 Jun 2007 23:01:00 UTC
Message-ID: <fa.cyWFCn4s94/awsLMjkr2hpaUsl8@ifi.uio.no>

On Fri, 1 Jun 2007, Christoph Lameter wrote:
>
> Right it could catch a lot of other bugs as well.

I'd actually prefer "malloc(0)" to _not_ return NULL, but some known
(non-NULL) bogus pointer.

Why?

Because it's quite sane to have simple logic like

	ptr = malloc(size);
	if (!ptr)
		return -ENOMEM;

and writing it as

	if (size && !ptr)
		return -ENOMEM;

is just annoying.

Also, NULL is _special_. There are absolutely tons of code in the kernel
(and elsewhere) that just does something *different* from NULL pointers,
and that totally breaks the whole notion of "you can allocate a zero-sized
allocation, you just must not dereference it". If people special-case
NULL as something else, they won't even go through the normal code-path.

So for *both* of the above reasons, it's actually stupid to return NULL
for a zero-sized allocation. It would be much better to return another
pointer that will trap on access. A good candidate might be to return

	#define BADPTR ((void *)16)

which is a portable-enough (where "portable-enough" is "against strict
ANSI C rules, but works in practice on all architectures") way to return
something that will cause the same page fault behaviour as NULL, but will
_not_ trigger the "NULL is special" code.

(Of course, you then need to teach "kfree()" to accept it as another
pointer to be ignored, that's fine).

I bet you'd find *more* problems that way than by returning NULL, and
you'd also avoid the whole problem with "if (!ptr) return -ENOMEM".

		Linus

From: Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups: fa.linux.kernel
Subject: Re: SLUB: Return ZERO_SIZE_PTR for kmalloc(0)
Date: Mon, 04 Jun 2007 16:27:24 UTC
Message-ID: <fa.nBHITnh6vVPBTzF5ongKcDdIOJs@ifi.uio.no>

On Mon, 4 Jun 2007, Pekka Enberg wrote:
>
> Ok, makes sense. I guess I might as well throw my suggestion in the
> mix. Lets create a new kmalloc cache for zero-length objects where
> object size is zero but there are regular red-zones on both sides.

Well, the red-zones won't catch readers, and more importantly, even for
writers they are *really* inconvenient, because it will just tell you
something bad happened, it won't tell you *where* it happened.

Since comparing the addresses of two zero-sized allocations is insane and
not done _anyway_, it's just much better to return an invalid address.

The thing is, why *should* we care about comparing addresses? We'll give
the right result (you got many perfectly separate allocations, they're
just zero bytes apart, exactly like you asked for!). The fact that C++ has
some semantics for it is not a good argument - C++ is a broken language,
and it's not the language we use for the kernel anyway.

		Linus

From: Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups: fa.linux.kernel
Subject: Re: SLUB: Return ZERO_SIZE_PTR for kmalloc(0)
Date: Mon, 04 Jun 2007 16:49:03 UTC
Message-ID: <fa.RUZswUN4/mtv3+b8ONMWJKqzUjE@ifi.uio.no>

On Mon, 4 Jun 2007, Pekka Enberg wrote:
>
> Then we might as well return your regular NULL pointer for zero-length
> allocations as you can't do anything sane with ZERO_SIZE_PTR either.


No. NULL really _is_ special.

We use NULL in tons of places for saying "we haven't allocated anything at
all".

That's *not* the same as saying "we have initialized this pointer, it just
happens to point to a zero-sized object".

Two *totally* different things. I don't understand why people mix them up.

We literally have code that tests pointers for NULL to determine if the
subsystem has been initialized.

In other words: YOU MUST NOT RETURN NULL FOR A "SUCCESSFUL POINTER
ALLOCATION", regardless of the size.

Yeah, yeah, I realize that the C library traditionally allows it, and user
space is used to it, but it's still wrong and stupid. We can do so much
better.

When malloc() returns NULL, it means that it failed.

When a pointer is NULL, it means that it doesn't exist.

And ZERO_SIZE_PTR is _neither_ of those cases!

		Linus

From: Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups: fa.linux.kernel
Subject: Re: SLUB: Return ZERO_SIZE_PTR for kmalloc(0)
Date: Mon, 04 Jun 2007 17:51:22 UTC
Message-ID: <fa.jzj+2GZAeEjHPgsmLy6yyyhfVAA@ifi.uio.no>

On Mon, 4 Jun 2007, Alan Cox wrote:

> > The thing is, why *should* we care about comparing addresses? We'll give
>
> Because people use it to tell objects apart. All over the kernel we do
> things like
>
> 	if (inode1 == inode2)

But that only makes sense if your objects have meaning, which is not
possible with a zero-sized object.

Let's take an example: one of the few reasons to check for equality (or
inequality) is for locking order.

So on UP, the lock goes away, and let's say that you (insanely) only have
a spinlock in the structure in question, so you have a zero-sized
structure that you want to test ordering on because you want to avoid
ABBA deadlocks.

So you write your code as

   double_lock()
   {
	if (ptr1 == ptr2) {
		lock(ptr1->lock);
		return;
	}
	if (ptr1 < ptr2) {
		lock(ptr1->lock);
		lock(ptr2->lock);
		return;
	}
	lock(ptr2->lock);
	lock(ptr1->lock);
    }

and the interesting thing is that this actually *works* even for the case
where the lock has gone away: even though ptr1/ptr2 are always equal.

In other words, the only _valid_ reasons to compare pointers like this end
up degenerating into working cases even for a zero-sized pointer.

The exception is if you use the memory allocator as a "ID allocator", but
quite frankly, if you use a size of zero, it's your own damn problem.
Insane code is not an argument for insane behaviour.

If people can't be bothered to create a "random ID generator" themselves,
they had damn well better use "kmalloc(1)" rather than "kmalloc(0)" to get
a unique cookie. Asking the allocator to do something idiotic because some
idiot thinks a memory allocator is a cookie allocator is just crazy.

I can understand that things like user-level libraries have to take crazy
people into account, but the kernel internal libraries definitely do not.

(Right now we warn once for zero-sized allocations anyway, and all the
cases we've found so far are either bugs that would have been found with
ZERO_ALLOC_PTR or would have been perfectly fine with it, so I don't think
anybody really _is_ that insane in the kernel)

		Linus

From: Linus Torvalds <torvalds@linux-foundation.org>
Newsgroups: fa.linux.kernel
Subject: Re: SLUB: Return ZERO_SIZE_PTR for kmalloc(0)
Date: Mon, 04 Jun 2007 18:47:49 UTC
Message-ID: <fa.I5XxzbRLAlwrieZbKIIIvSaJO64@ifi.uio.no>

On Fri, 1 Jun 2007, Christoph Lameter wrote:
>
> Instead of returning the smallest available object return ZERO_SIZE_PTR.

Ok, I just noticed that this still has a bug: not just kfree(), but
krealloc() needs to treat ZERO_SIZE_PTR properly.

Your patch introduces two bugs in mm/slub.c:krealloc():

 - The

	if (unlikely(!p))
		return kmalloc(new_size, flags);

   test needs to be for NULL or ZERO_SIZE_PTR. Otherwise it will oops in
   ksize(p), I think.

 - And the

	if (unlikely(!new_size)) {
		kfree(p);
		return NULL;
	}

   thing should logically return ZERO_SIZE_PTR instead of NULL.

So basically

	krealloc(kmalloc(0), n, flags);

must work, and

	krealloc(old, 0, flags)

should return a zero-sized allocation.

I'd forgotten about krealloc(), because that whole concept is fairly new.

		Linus