Introduce mallocarray() in the kernel

[kp]

Summary

Similar to calloc() the mallocarray() function checks for integer
overflows before allocating memory.
It does not zero memory, unless the M_ZERO flag is set.

[kp]

Removed incorrect __alloc_size attribute.

[vangyzen]

I would prefer calling it calloc, but mallocarray follows the OpenBSD precedent, which is fine. We could add a calloc wrapper any time.

Please add it to the malloc(9) man page.

sys/kern/kern_malloc.c

542 ↗

(On Diff #37515)

Suggestion: OpenBSD and jemalloc have an optimization to avoid the division. I think I prefer jemalloc's, since it avoids a branch.

sys/sys/malloc.h

181 ↗

(On Diff #37515)

Suggestion: calloc in <stdlib.h> has __alloc_size(1) __alloc_size(2). I don't know if that's correct. If it is, you could use it here. (If not, you could fix stdlib.h. :)

[imp]

I like this.

But please! Absolutely do not call it calloc. Please. We already have enough hassle with overloading malloc when code gets shared between the kernel and boot loaders.

[kp]

I have to admit I initially wanted to call it calloc(), but it turns out ZFS already has calloc(size_t, size_t) in sys/cddl/compat/opensolaris/sys/kmem.h, so that failed to build.

[kp]

sys/sys/malloc.h

181 ↗

(On Diff #37515)

I don't know if repeating it is correct. GCC has

__attribute__((alloc_size(1,2)))

, but we don't have the wrapper defines for a two-parameter variant, so I just removed it. It should be safe to not have it.

I'll what I can figure out later today.

[vangyzen]

In D13766#288178, @imp wrote:

But please! Absolutely do not call it calloc. Please. We already have enough hassle with overloading malloc when code gets shared between the kernel and boot loaders.

Ah, I hadn't thought of sharing code with boot loaders. Good point.

[vangyzen]

sys/sys/malloc.h

181 ↗

(On Diff #37515)

It could certainly wait for a later commit.

[kp]

Update malloc.9 man page.

[mjg]

Arguably in the kernel it is a programming error to pass such args to malloc in the first place. Even if the args happen to not overflow, resulting size can be extremely high and that was not intended. I.e. the real thing the code should do is sanity check first with some kind of upper cap.

That said, I don't have strong objections to the func, but I think it's a bad idea. Instead a magic macro should be provided which would take care of signed/unsigned and upper cap.

[pfg]

For the record: I never liked adding reallocarray to stdlib.h because it is a nonstandard funtion. In the case of the kernel, of course, I think it is not an issue.

sys/sys/malloc.h

181 ↗

(On Diff #37531)

__alloc_size(1) __alloc_size(2) would be correct: It should help the static checker. (plus I should know as I introduced the attribute ;) )

Also, when using this function try to make sure the first two arguments are unsigned.

[pfg]

sys/kern/kern_malloc.c

540 ↗

(On Diff #37531)

This doesn't look right: you should avoid the overflow altogether. Check for the overflow first, and do the multiplication last.

[kp]

sys/kern/kern_malloc.c

540 ↗

(On Diff #37531)

We don't actually use the value for anything other than making sure it didn't overflow, so that should be fine.
Every other implementation I've looked at actually does the multiplication to verify that it didn't overflow. Some have shortcuts to avoid doing the division in most cases, but all end up doing it as a last resort anyway.

For example, from contrib/jemalloc/src/jemalloc.c:

JEMALLOC_ALWAYS_INLINE bool
compute_size_with_overflow(bool may_overflow, dynamic_opts_t *dopts,
    size_t *size) {
        /*
         * This function is just num_items * item_size, except that we may have
         * to check for overflow.
         */

        if (!may_overflow) {
                assert(dopts->num_items == 1);
                *size = dopts->item_size;
                return false;
        }

        /* A size_t with its high-half bits all set to 1. */
        const static size_t high_bits = SIZE_T_MAX << (sizeof(size_t) * 8 / 2);

        *size = dopts->item_size * dopts->num_items;

        if (unlikely(*size == 0)) {
                return (dopts->num_items != 0 && dopts->item_size != 0);
        }

        /*
         * We got a non-zero size, but we don't know if we overflowed to get
         * there.  To avoid having to do a divide, we'll be clever and note that
         * if both A and B can be represented in N/2 bits, then their product
         * can be represented in N bits (without the possibility of overflow).
         */
        if (likely((high_bits & (dopts->num_items | dopts->item_size)) == 0)) {
                return false;
        }
        if (likely(*size / dopts->item_size == dopts->num_items)) {
                return false;
        }
        return true;
}

This is essentially the same, other than jemalloc trying hard to avoid the division.

sys/sys/malloc.h

181 ↗

(On Diff #37531)

Okay, I wasn't sure that repeating alloc_size() was valid, so I planned to change the macro so it could be used as alloc_size(1, 2). Now that you've confirmed that it is valid I'll just repeat it.

[kp]

Add __alloc_size attributes.

[pfg]

sys/kern/kern_malloc.c

540 ↗

(On Diff #37531)

I know you don't use the value but you still cause the operation to overflow innecessarily. Assigning values in the initalization section is also against style(9). Check the OpenBSD memalloc, it really can't be simpler.

src/sys/kern/kern_malloc.c

/*
 * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
 * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
 */
#define MUL_NO_OVERFLOW	(1UL << (sizeof(size_t) * 4))

void *
mallocarray(size_t nmemb, size_t size, int type, int flags)
{
	if ((nmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
	    nmemb > 0 && SIZE_MAX / nmemb < size) {
		if (flags & M_CANFAIL)
			return (NULL);
		panic("mallocarray: overflow %zu * %zu", nmemb, size);
	}
	return (malloc(size * nmemb, type, flags));
}

[kp]

Use the OpenBSD mallocarray implementation.

[pfg]

OK, thanks.

[erj]

Is this going to be MFC'd into stable/10 and/or stable/11?

[kp]

In D13766#290617, @erj wrote:

Is this going to be MFC'd into stable/10 and/or stable/11?

I have no immediate plans to, but if it is it should be done together with the changes to make it panic on overflow that have been added in head.