On Sat, May 23, 2015 at 12:28 PM, Theo Buehler <t...@math.ethz.ch> wrote:
> This set of three patches adds overflow checking to ksh in the spirit
> of the malloc(A*B) -> reallocarray(NULL, A, B) conversions that were
> ongoing since last summer. I've been running these patches on my main
> laptop since January on amd64/CURRENT and didn't notice any issues.
>
> ksh has its own memory management functions and only calls malloc and
> realloc in the functions alloc() and aresize() in alloc.c. There the
> `size' arguments have the form
>
> sizeof(struct link) + size
>
> where struct link is defined as
>
> struct link {
> struct link *prev;
> struct link *next;
> };
>
> In order to ensure that this doesn't overflow if `size' is a product of
> two numbers, wrap alloc() and aresize() into two functions which take
> the two factors as arguments and take care of the overflow checking:
>
> void *allocarray(size_t nmemb, size_t size, Area *ap);
> void *aresizearray(void *ptr, size_t nmemb, size_t size, Area *ap);
>
> The mathematically optimal check would test whether at least one of
> `size' and `nmemb' exceeds `sqrt(SIZE_MAX - sizeof(nmemb))' before
> proceeding. I went for something which is easier to compute.
>
> This first patch introduces the two wrappers and adds the overflow
> checking.
>
> The other two patches consist of purely mechanical conversions:
>
> Expand the macro
>
> #define sizeofN(type, n) (sizeof(type) * n)
>
> and take care of all explicit multiplications.
>
Hi, Please don't forget to include Otto's license to the code, that
you modified.
>
> Index: alloc.c
> ===================================================================
> RCS file: /cvs/src/bin/ksh/alloc.c,v
> retrieving revision 1.8
> diff -u -p -r1.8 alloc.c
> --- alloc.c 21 Jul 2008 17:30:08 -0000 1.8
> +++ alloc.c 23 May 2015 11:58:27 -0000
> @@ -74,6 +74,33 @@ alloc(size_t size, Area *ap)
> return L2P(l);
> }
>
> +/*
> + * 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 ((size_t)1 << (sizeof(size_t) * 4))
> +/*
> + * Generous upper bound for sqrt(sizeof(struct link)).
> + */
> +#define SQRT_SIZ_STR_LINK (sizeof(struct link) / 2)
> +
> +void *
> +allocarray(size_t nmemb, size_t size, Area *ap)
> +{
> + /*
> + * Ensure that `sizeof(struct link) + size * nmemb' doesn't overflow.
> + * If overflow occurs, at least one of `size' and `nmemb' must be
> + * larger than sqrt(SIZE_MAX - sizeof(struct link)).
> + * Note: sqrt(a - b) > sqrt(a) - sqrt(b) for a > b.
> + */
> + if ((nmemb >= MUL_NO_OVERFLOW - SQRT_SIZ_STR_LINK ||
> + size >= MUL_NO_OVERFLOW - SQRT_SIZ_STR_LINK) &&
> + nmemb > 0 && (SIZE_MAX - sizeof(struct link)) / nmemb < size)
> + internal_errorf(1, "unable to allocate memory");
> +
> + return (alloc(size * nmemb, ap));
> +}
> +
> void *
> aresize(void *ptr, size_t size, Area *ap)
> {
> @@ -97,6 +124,18 @@ aresize(void *ptr, size_t size, Area *ap
> lnext->prev = l2;
>
> return L2P(l2);
> +}
> +
> +void *
> +aresizearray(void *ptr, size_t nmemb, size_t size, Area *ap)
> +{
> + /* Ensure that `sizeof(struct link) + size * nmemb' doesn't overflow.
> */
> + if ((size >= MUL_NO_OVERFLOW - SQRT_SIZ_STR_LINK ||
> + nmemb >= MUL_NO_OVERFLOW - SQRT_SIZ_STR_LINK) &&
> + nmemb > 0 && (SIZE_MAX - sizeof(struct link)) / nmemb < size)
> + internal_errorf(1, "unable to allocate memory");
> +
> + return (aresize(ptr, size * nmemb, ap));
> }
>
> void
> Index: proto.h
> ===================================================================
> RCS file: /cvs/src/bin/ksh/proto.h,v
> retrieving revision 1.35
> diff -u -p -r1.35 proto.h
> --- proto.h 4 Sep 2013 15:49:19 -0000 1.35
> +++ proto.h 23 May 2015 11:58:27 -0000
> @@ -10,7 +10,9 @@
> Area * ainit(Area *);
> void afreeall(Area *);
> void * alloc(size_t, Area *);
> +void * allocarray(size_t, size_t, Area *);
> void * aresize(void *, size_t, Area *);
> +void * aresizearray(void *, size_t, size_t, Area *);
> void afree(void *, Area *);
> /* c_ksh.c */
> int c_hash(char **);
> Index: sh.h
> ===================================================================
> RCS file: /cvs/src/bin/ksh/sh.h,v
> retrieving revision 1.33
> diff -u -p -r1.33 sh.h
> --- sh.h 18 Dec 2013 13:53:12 -0000 1.33
> +++ sh.h 23 May 2015 11:58:27 -0000
> @@ -15,6 +15,7 @@
> #include <setjmp.h>
> #include <stdbool.h>
> #include <stddef.h>
> +#include <stdint.h>
> #include <stdlib.h>
> #include <unistd.h>
> #include <string.h>
>
