[RFC PATCH 0/3] Introduce kernel small arrays (KSA)

[RFC PATCH 0/3] Introduce kernel small arrays (KSA)

[Ilya Matveychikov]

Hi guys,

Please review the approach of using small fixed-sized arrays to improve
parsing of values like get_options() does.

This comes to me after fixing an overflow in get_options(). See the thread
for details: https://lkml.org/lkml/2017/5/22/581

If the approach is OK I’ll suggest to replace all of get_options() calls
to ksa_parse_ints() and remove get_options() at all.

Thank you.

[RFC PATCH 1/3] ksmall_array: introduce kernel small arrays

[Ilya Matveychikov]

Signed-off-by: Ilya V. Matveychikov <matvejchikov@gmail.com>
---
 include/linux/small_array.h | 35 +++++++++++++++++++++++++++++++++++
 lib/Makefile                |  2 +-
 lib/cmdline.c               |  4 +++-
 lib/ksmall_array.c          | 26 ++++++++++++++++++++++++++
 4 files changed, 65 insertions(+), 2 deletions(-)
 create mode 100644 include/linux/small_array.h
 create mode 100644 lib/ksmall_array.c

diff --git a/include/linux/small_array.h b/include/linux/small_array.h
new file mode 100644
index 0000000..c5ccbe4d
--- /dev/null
+++ b/include/linux/small_array.h
@@ -0,0 +1,35 @@
+#ifndef __SMALL_ARRAY_H__
+#define __SMALL_ARRAY_H__
+
+/*
+ * Kingdom of Small Arrays (KSA)
+ */
+
+#include <linux/build_bug.h>
+
+#define KSA_S_BITS		8
+#define KSA_N_BITS		12
+
+struct ksmall_array {
+	unsigned int s : KSA_S_BITS;	/* sizeof(item) */
+	unsigned int n : KSA_N_BITS;	/* number of items stored */
+	unsigned int m : KSA_N_BITS;	/* maximum number of items allowed */
+	unsigned char v[0];
+};
+
+#define KSA_DECLARE(name, type, count)				\
+	struct {						\
+		struct ksmall_array ksa;			\
+		type data[count];				\
+	} name = {{ .s = sizeof(type), .n = 0, .m = count }}
+
+#define KSA(p)			((struct ksmall_array *)(p))
+#define KSA_S(p)		KSA(p)->s
+#define KSA_N(p)		KSA(p)->n
+#define KSA_M(p)		KSA(p)->m
+#define KSA_V(p, t)		((t *)KSA(p)->v)
+#define KSA_GET(p, i, v)	((i < KSA_N(p)) ? (p)->data[i] : v)
+
+extern char *ksa_parse_ints(const char *str, struct ksmall_array *ksa);
+
+#endif /* __SMALL_ARRAY_H__ */
diff --git a/lib/Makefile b/lib/Makefile
index 40c1837..502f4b4 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -30,7 +30,7 @@ lib-$(CONFIG_SMP) += cpumask.o
 lib-$(CONFIG_DMA_NOOP_OPS) += dma-noop.o
 lib-$(CONFIG_DMA_VIRT_OPS) += dma-virt.o

-lib-y	+= kobject.o klist.o
+lib-y	+= kobject.o klist.o ksmall_array.o
 obj-y	+= lockref.o

 obj-y += bcd.o div64.o sort.o parser.o debug_locks.o random32.o \
diff --git a/lib/cmdline.c b/lib/cmdline.c
index 4c0888c..233c4eb 100644
--- a/lib/cmdline.c
+++ b/lib/cmdline.c
@@ -63,8 +63,10 @@ int get_option(char **str, int *pint)
 		(*str)++;
 		return 2;
 	}
-	if (**str == '-')
+	if (**str == '-') {
+		(*str)++;
 		return 3;
+	}

 	return 1;
 }
diff --git a/lib/ksmall_array.c b/lib/ksmall_array.c
new file mode 100644
index 0000000..ecc8403
--- /dev/null
+++ b/lib/ksmall_array.c
@@ -0,0 +1,26 @@
+#include <linux/small_array.h>
+#include <linux/bug.h>
+
+char *ksa_parse_ints(const char *str, struct ksmall_array *ksa)
+{
+	int res, a, b;
+
+	BUG_ON(ksa->s != sizeof(int));
+
+	while (ksa->n < ksa->m) {
+		res = get_option((char **)&str, &a); b = a;
+		if (res == 0) break;
+		if (res == 3) res = get_option((char **)&str, &b);
+		if (res == 0) break;
+		while (a <= b && (ksa->n < ksa->m))
+			KSA_V(ksa, int)[ksa->n++] = a++;
+	}
+
+	return (char *)str;
+}
+EXPORT_SYMBOL(ksa_parse_ints);
+
+static void __attribute__((unused)) ksa_build_check(void)
+{
+	BUILD_BUG_ON(sizeof(struct ksmall_array) != sizeof(unsigned int));
+}
--
2.7.4

[RFC PATCH 2/3] net/dev/core.c: use ksa_parse_ints instead of get_options

[Ilya Matveychikov]

Signed-off-by: Ilya V. Matveychikov <matvejchikov@gmail.com>
---
 net/core/dev.c | 20 ++++++++------------
 1 file changed, 8 insertions(+), 12 deletions(-)

diff --git a/net/core/dev.c b/net/core/dev.c
index 8515f8f..acda9ac 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -144,6 +144,7 @@
 #include <linux/netfilter_ingress.h>
 #include <linux/crash_dump.h>
 #include <linux/sctp.h>
+#include <linux/small_array.h>

 #include "net-sysfs.h"

@@ -645,23 +646,18 @@ unsigned long netdev_boot_base(const char *prefix, int unit)
  */
 int __init netdev_boot_setup(char *str)
 {
-	int ints[5];
-	struct ifmap map;
+	struct ifmap map = { 0 };
+	KSA_DECLARE(ints, int, 4);

-	str = get_options(str, ARRAY_SIZE(ints), ints);
+	str = ksa_parse_ints(str, KSA(&ints));
 	if (!str || !*str)
 		return 0;

 	/* Save settings */
-	memset(&map, 0, sizeof(map));
-	if (ints[0] > 0)
-		map.irq = ints[1];
-	if (ints[0] > 1)
-		map.base_addr = ints[2];
-	if (ints[0] > 2)
-		map.mem_start = ints[3];
-	if (ints[0] > 3)
-		map.mem_end = ints[4];
+	map.irq = KSA_GET(&ints, 0, 0);
+	map.base_addr = KSA_GET(&ints, 1, 0);
+	map.mem_start = KSA_GET(&ints, 2, 0);
+	map.mem_end = KSA_GET(&ints, 3, 0);

 	/* Add new entry to the list */
 	return netdev_boot_setup_add(str, &map);
--
2.7.4

Re: [RFC PATCH 0/3] Introduce kernel small arrays (KSA)

[Ben Hutchings]

On Tue, 2017-09-19 at 12:30 +0400, Ilya Matveychikov wrote:
> Hi guys,
> 
> Please review the approach of using small fixed-sized arrays to improve
> parsing of values like get_options() does.
> 
> This comes to me after fixing an overflow in get_options(). See the thread
> for details: https://lkml.org/lkml/2017/5/22/581
> 
> If the approach is OK I’ll suggest to replace all of get_options() calls
> to ksa_parse_ints() and remove get_options() at all.

You didn't cc the patches to me, and I can't find patch 3/3 at all.

I don't think the KSA() macro should be casting its argument.  Where the
cast is necessary, it ought to be explicit in the caller.

Similarly I think the BUILD_BUG_ON() in ksa_build_check() doesn't belong
there, but in whichever caller of ksa_parse_ints() requires struct
ksmall_array to have the same layout as a simple array of unsigned int.

Ben.

-- 
Ben Hutchings
Software Developer, Codethink Ltd.

Re: [RFC PATCH 0/3] Introduce kernel small arrays (KSA)

[Ilya Matveychikov]

> On Oct 4, 2017, at 7:22 PM, Ben Hutchings <ben.hutchings@codethink.co.uk> wrote:
> 
> On Tue, 2017-09-19 at 12:30 +0400, Ilya Matveychikov wrote:
>> Hi guys,
>> 
>> Please review the approach of using small fixed-sized arrays to improve
>> parsing of values like get_options() does.
>> 
>> This comes to me after fixing an overflow in get_options(). See the thread
>> for details: https://lkml.org/lkml/2017/5/22/581
>> 
>> If the approach is OK I’ll suggest to replace all of get_options() calls
>> to ksa_parse_ints() and remove get_options() at all.
> 
> You didn't cc the patches to me, and I can't find patch 3/3 at all.

Thanks for you answer. I posted them on list, except the last one as what I
wanted is to get the feedback first. I CC’d you as you found a problem with
my patch for get_options() before (read out of bounds).

> 
>  don't think the KSA() macro should be casting its argument.  Where the
> cast is necessary, it ought to be explicit in the caller.

KSA(x) it’s just a simple way to cast from custom-defined small array
to generic one. Do you think that it’s better to use explicit casting:

ksa_parse_foo(..., (struct ksmall_array *)&my_custom_ksa)

Instead of:

ksa_parse_foo(..., KSA(&my_custom_ksa))

Not sure...

> 
> Similarly I think the BUILD_BUG_ON() in ksa_build_check() doesn't belong
> there, but in whichever caller of ksa_parse_ints() requires struct
> ksmall_array to have the same layout as a simple array of unsigned int.

Not sure that I understand your point. The purpose of ksa_build_check() as
I wrote it is to to do compile-time check for sizeof(struct ksmall_array)
to fit sizeof(unsigned int). Note that ksmall_array{} is the header for any
possible “small” array build by using the KSA_DECLARE() macro.