[03/13] overflow.h: Add allocation size calculation helpers
diff mbox

Message ID 20180509004229.36341-4-keescook@chromium.org
State New
Headers show

Commit Message

Kees Cook May 9, 2018, 12:42 a.m. UTC
In preparation for replacing unchecked overflows for memory allocations,
this creates helpers for the 3 most common calculations:

array_size(a, b): 2-dimensional array
array3_size(a, b, c): 2-dimensional array
struct_size(ptr, member, n): struct followed by n-many trailing members

Each of these return SIZE_MAX on overflow instead of wrapping around.

(Additionally renames a variable named "array_size" to avoid future
collision.)

Co-developed-by: Matthew Wilcox <mawilcox@microsoft.com>
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 drivers/md/dm-table.c    | 10 +++---
 include/linux/overflow.h | 74 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 79 insertions(+), 5 deletions(-)

Comments

Rasmus Villemoes May 9, 2018, 6:27 p.m. UTC | #1
On 2018-05-09 02:42, Kees Cook wrote:
> In preparation for replacing unchecked overflows for memory allocations,
> this creates helpers for the 3 most common calculations:
> 
> array_size(a, b): 2-dimensional array
> array3_size(a, b, c): 2-dimensional array

yeah... complete confusion...

> +/**
> + * array_size() - Calculate size of 2-dimensional array.
> + *
> + * @a: dimension one
> + * @b: dimension two
> + *
> + * Calculates size of 2-dimensional array: @a * @b.
> + *
> + * Returns: number of bytes needed to represent the array or SIZE_MAX on
> + * overflow.
> + */
> +static inline __must_check size_t array_size(size_t a, size_t b)
> +{
> +	size_t bytes;
> +
> +	if (check_mul_overflow(a, b, &bytes))
> +		return SIZE_MAX;
> +
> +	return bytes;
> +}
> +
> +/**
> + * array3_size() - Calculate size of 3-dimensional array.
> + *

...IDGI. array_size is/will most often be used to calculate the size of
a one-dimensional array, count*elemsize, accessed as foo[i]. Won't a
three-factor product usually be dim1*dim2*elemsize, i.e. 2-dimensional,
accessed (because C is lame) as foo[i*dim2 + j]?

> +/**
> + * struct_size() - Calculate size of structure with trailing array.
> + * @p: Pointer to the structure.
> + * @member: Name of the array member.
> + * @n: Number of elements in the array.
> + *
> + * Calculates size of memory needed for structure @p followed by an
> + * array of @n @member elements.
> + *
> + * Return: number of bytes needed or SIZE_MAX on overflow.
> + */
> +#define struct_size(p, member, n)					\
> +	__ab_c_size(n,							\
> +		    sizeof(*(p)->member) + __must_be_array((p)->member),\
> +		    offsetof(typeof(*(p)), member))
> +
> +

struct s { int a; char b; char c[]; } has sizeof > offsetof(c), so for
small enough n, we end up allocating less than sizeof(struct s). And the
caller might reasonably do memset(s, 0, sizeof(*s)) to initialize all
members before c. In practice our allocators round up to a multiple of
8, so I don't think it's a big problem, but some sanitizer might
complain. But I do think you should make that addend sizeof() instead of
offsetof().

Rasmus
Kees Cook May 9, 2018, 6:49 p.m. UTC | #2
On Wed, May 9, 2018 at 11:27 AM, Rasmus Villemoes
<linux@rasmusvillemoes.dk> wrote:
> On 2018-05-09 02:42, Kees Cook wrote:
>> In preparation for replacing unchecked overflows for memory allocations,
>> this creates helpers for the 3 most common calculations:
>>
>> array_size(a, b): 2-dimensional array
>> array3_size(a, b, c): 2-dimensional array
>
> yeah... complete confusion...
>
>> +/**
>> + * array_size() - Calculate size of 2-dimensional array.
>> + *
>> + * @a: dimension one
>> + * @b: dimension two
>> + *
>> + * Calculates size of 2-dimensional array: @a * @b.
>> + *
>> + * Returns: number of bytes needed to represent the array or SIZE_MAX on
>> + * overflow.
>> + */
>> +static inline __must_check size_t array_size(size_t a, size_t b)
>> +{
>> +     size_t bytes;
>> +
>> +     if (check_mul_overflow(a, b, &bytes))
>> +             return SIZE_MAX;
>> +
>> +     return bytes;
>> +}
>> +
>> +/**
>> + * array3_size() - Calculate size of 3-dimensional array.
>> + *
>
> ...IDGI. array_size is/will most often be used to calculate the size of
> a one-dimensional array, count*elemsize, accessed as foo[i]. Won't a
> three-factor product usually be dim1*dim2*elemsize, i.e. 2-dimensional,
> accessed (because C is lame) as foo[i*dim2 + j]?

I was thinking of byte addressing, not object addressing. I can
rewrite this to be less confusing.

>> +/**
>> + * struct_size() - Calculate size of structure with trailing array.
>> + * @p: Pointer to the structure.
>> + * @member: Name of the array member.
>> + * @n: Number of elements in the array.
>> + *
>> + * Calculates size of memory needed for structure @p followed by an
>> + * array of @n @member elements.
>> + *
>> + * Return: number of bytes needed or SIZE_MAX on overflow.
>> + */
>> +#define struct_size(p, member, n)                                    \
>> +     __ab_c_size(n,                                                  \
>> +                 sizeof(*(p)->member) + __must_be_array((p)->member),\
>> +                 offsetof(typeof(*(p)), member))
>> +
>> +
>
> struct s { int a; char b; char c[]; } has sizeof > offsetof(c), so for
> small enough n, we end up allocating less than sizeof(struct s). And the
> caller might reasonably do memset(s, 0, sizeof(*s)) to initialize all
> members before c. In practice our allocators round up to a multiple of
> 8, so I don't think it's a big problem, but some sanitizer might
> complain. But I do think you should make that addend sizeof() instead of
> offsetof().

Erg. Yeah, I think we'd best "round up". Besides the "< sizeof()" vs
memset() case you mention, another pattern I've seen is doing stuff
like:

array = (array_type *)(thing + 1);

So if padding somehow caused us to under-allocate, we'll get it wrong there too.

I'll change this to be strictly sizeof(*(p)).

(Though it might be nice to enforce that "member" is at the end of the
structure, though, otherwise this could be misused for struct s { int
a; char c[2]; char b[]; } ... )

-Kees

Patch
diff mbox

diff --git a/drivers/md/dm-table.c b/drivers/md/dm-table.c
index 0589a4da12bb..caa51dd351b6 100644
--- a/drivers/md/dm-table.c
+++ b/drivers/md/dm-table.c
@@ -548,14 +548,14 @@  static int adjoin(struct dm_table *table, struct dm_target *ti)
  * On the other hand, dm-switch needs to process bulk data using messages and
  * excessive use of GFP_NOIO could cause trouble.
  */
-static char **realloc_argv(unsigned *array_size, char **old_argv)
+static char **realloc_argv(unsigned *size, char **old_argv)
 {
 	char **argv;
 	unsigned new_size;
 	gfp_t gfp;
 
-	if (*array_size) {
-		new_size = *array_size * 2;
+	if (*size) {
+		new_size = *size * 2;
 		gfp = GFP_KERNEL;
 	} else {
 		new_size = 8;
@@ -563,8 +563,8 @@  static char **realloc_argv(unsigned *array_size, char **old_argv)
 	}
 	argv = kmalloc(new_size * sizeof(*argv), gfp);
 	if (argv) {
-		memcpy(argv, old_argv, *array_size * sizeof(*argv));
-		*array_size = new_size;
+		memcpy(argv, old_argv, *size * sizeof(*argv));
+		*size = new_size;
 	}
 
 	kfree(old_argv);
diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index c8890ec358a7..76ff298e97b7 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -202,4 +202,78 @@ 
 
 #endif /* COMPILER_HAS_GENERIC_BUILTIN_OVERFLOW */
 
+/**
+ * array_size() - Calculate size of 2-dimensional array.
+ *
+ * @a: dimension one
+ * @b: dimension two
+ *
+ * Calculates size of 2-dimensional array: @a * @b.
+ *
+ * Returns: number of bytes needed to represent the array or SIZE_MAX on
+ * overflow.
+ */
+static inline __must_check size_t array_size(size_t a, size_t b)
+{
+	size_t bytes;
+
+	if (check_mul_overflow(a, b, &bytes))
+		return SIZE_MAX;
+
+	return bytes;
+}
+
+/**
+ * array3_size() - Calculate size of 3-dimensional array.
+ *
+ * @a: dimension one
+ * @b: dimension two
+ * @c: dimension three
+ *
+ * Calculates size of 3-dimensional array: @a * @b * @c.
+ *
+ * Returns: number of bytes needed to represent the array or SIZE_MAX on
+ * overflow.
+ */
+static inline __must_check size_t array3_size(size_t a, size_t b, size_t c)
+{
+	size_t bytes;
+
+	if (check_mul_overflow(a, b, &bytes))
+		return SIZE_MAX;
+	if (check_mul_overflow(bytes, c, &bytes))
+		return SIZE_MAX;
+
+	return bytes;
+}
+
+static inline __must_check size_t __ab_c_size(size_t n, size_t size, size_t c)
+{
+	size_t bytes;
+
+	if (check_mul_overflow(n, size, &bytes))
+		return SIZE_MAX;
+	if (check_add_overflow(bytes, c, &bytes))
+		return SIZE_MAX;
+
+	return bytes;
+}
+
+/**
+ * struct_size() - Calculate size of structure with trailing array.
+ * @p: Pointer to the structure.
+ * @member: Name of the array member.
+ * @n: Number of elements in the array.
+ *
+ * Calculates size of memory needed for structure @p followed by an
+ * array of @n @member elements.
+ *
+ * Return: number of bytes needed or SIZE_MAX on overflow.
+ */
+#define struct_size(p, member, n)					\
+	__ab_c_size(n,							\
+		    sizeof(*(p)->member) + __must_be_array((p)->member),\
+		    offsetof(typeof(*(p)), member))
+
+
 #endif /* __LINUX_OVERFLOW_H */