Skip to contentSkip to conversation

x86/uv/time: Replace one-element array and save heap space

PATCH Superseded Gustavo A. R. Silva 5 participants 8 messages May 18, 2020 – Sep 30, 2020

Subsystems (3)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 x86/uv/time: Replace one-element array and save heap space

The current codebase makes use of one-element arrays in the following form:

struct something {
    int length;
    u8 data[1];
};

struct something *instance;

instance = kmalloc(sizeof(*instance) + size, GFP_KERNEL); instance->length = size;
memcpy(instance->data, source, size);

but the preferred mechanism to declare variable-length types such as these ones is a flexible array member[1][2], introduced in C99:

struct foo {
        int stuff;
        struct boo array[];
};

By making use of the mechanism above, we will get a compiler warning in case the flexible array does not occur last in the structure, which will help us prevent some kind of undefined behavior bugs from being inadvertently introduced[3] to the codebase from now on. So, replace the one-element array with a flexible-array member.

Also, make use of the new struct_size() helper to properly calculate the total size needed to allocate dynamic memory for struct uv_rtc_timer_head. Notice that, due to the use of a one-element array, space for an extra struct cpu:

struct {

	int     lcpu;           /* systemwide logical cpu number */
	u64     expires;        /* next timer expiration for this cpu */

} cpu[1]

was being allocated at the moment of applying the sizeof operator to struct uv_rtc_timer_head in the call to kmalloc_node() at line 159:

159 head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
160 (uv_blade_nr_possible_cpus(bid) *
161 2 * sizeof(u64)),
162 GFP_KERNEL, nid);

but that extra cpu[] was never actually being accessed due to the following piece of code at line 168:

168 head->ncpus = uv_blade_nr_possible_cpus(bid);

and the piece of code at line 187:

187 for (c = 0; c < head->ncpus; c++) {
188 u64 exp = head->cpu[c].expires;
189 if (exp < lowest) {
190 bcpu = c;
191 lowest = exp;
192 }
193 }

so heap space was being wasted.

Another thing important to notice is that through the use of the struct_size() helper, code at line 161:

161 2 * sizeof(u64)),

is changed to now be the actual size of struct cpu; see sizeof(*(p)->member) at include/linux/overflow.h:314:

314 #define struct_size(p, member, n) \
315 __ab_c_size(n, \
316 sizeof(*(p)->member) + __must_be_array((p)->member),\
317 sizeof(*(p)))

As a side note, the original developer could have implemented code at line 161: 2 * sizeof(64) as follows:

sizeof(*head->cpu)

This issue has been out there since 2009.

This issue was found with the help of Coccinelle and fixed _manually_.

[1] https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
[2] https://github.com/KSPP/linux/issues/21
[3] commit 76497732932f ("cxgb3/l2t: Fix undefined behaviour")

---
 arch/x86/platform/uv/uv_time.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
arch/x86/platform/uv/uv_time.c +3 -4
index 7af31b245636..993a8ae6fdfb 100644
@@ -52,7 +52,7 @@ struct uv_rtc_timer_head {
 	struct {
 		int	lcpu;		/* systemwide logical cpu number */
 		u64	expires;	/* next timer expiration for this cpu */
-	} cpu[1];
+	} cpu[];
 };
 
 /*
@@ -156,9 +156,8 @@ static __init int uv_rtc_allocate_timers(void)
 		struct uv_rtc_timer_head *head = blade_info[bid];
 
 		if (!head) {
-			head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
-				(uv_blade_nr_possible_cpus(bid) *
-					2 * sizeof(u64)),
+			head = kmalloc_node(struct_size(head, cpu,
+				uv_blade_nr_possible_cpus(bid)),
 				GFP_KERNEL, nid);
 			if (!head) {
 				uv_rtc_deallocate_timers();
Signature · 1 line
2.26.2
#1 lore raw
Quoted 7 lines · Gustavo A. R. Silva

The current codebase makes use of one-element arrays in the following form:

struct something {
    int length;
    u8 data[1];
};

[]

Quoted 2 lines

This issue has been out there since 2009.
This issue was found with the help of Coccinelle and fixed _manually_.

[]

Quoted 14 lines
arch/x86/platform/uv/uv_time.c +1 -1
index 7af31b245636..993a8ae6fdfb 100644
@@ -52,7 +52,7 @@ struct uv_rtc_timer_head {
 	struct {
 		int	lcpu;		/* systemwide logical cpu number */
 		u64	expires;	/* next timer expiration for this cpu */
-	} cpu[1];
+	} cpu[];
 };
 
 /*

arch/x86/platform/uv/uv_time.c static __init int uv_rtc_allocate_timers(void) · line 160

Quoted 8 lines
arch/x86/platform/uv/uv_time.c +2 -3
@@ -156,9 +156,8 @@ static __init int uv_rtc_allocate_timers(void)
 		struct uv_rtc_timer_head *head = blade_info[bid];
 
 		if (!head) {
-			head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
-				(uv_blade_nr_possible_cpus(bid) *
-					2 * sizeof(u64)),
+			head = kmalloc_node(struct_size(head, cpu,
+				uv_blade_nr_possible_cpus(bid)),

It's probably safer to use kzalloc_node here as well.

Quoted 3 lines
arch/x86/platform/uv/uv_time.c +0 -0
 				GFP_KERNEL, nid);
 			if (!head) {
 				uv_rtc_deallocate_timers();
#2 lore raw
Quoted 28 lines · Joe Perches
Quoted 7 lines · Gustavo A. R. Silva

The current codebase makes use of one-element arrays in the following form:

struct something {
    int length;
    u8 data[1];
};

[]

Quoted 2 lines

This issue has been out there since 2009.
This issue was found with the help of Coccinelle and fixed _manually_.

[]

Quoted 16 lines
arch/x86/platform/uv/uv_time.c +1 -1
index 7af31b245636..993a8ae6fdfb 100644
@@ -52,7 +52,7 @@ struct uv_rtc_timer_head {
 	struct {
 		int	lcpu;		/* systemwide logical cpu number */
 		u64	expires;	/* next timer expiration for this cpu */
-	} cpu[1];
+	} cpu[];
 };
 
 /*
@@ -156,9 +156,8 @@ static __init int uv_rtc_allocate_timers(void)
 		struct uv_rtc_timer_head *head = blade_info[bid];
 
Quoted 9 lines

arch/x86/platform/uv/uv_time.c static __init int uv_rtc_allocate_timers(void) · line 160

Quoted 6 lines
arch/x86/platform/uv/uv_time.c +2 -3
 		if (!head) {
-			head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
-				(uv_blade_nr_possible_cpus(bid) *
-					2 * sizeof(u64)),
+			head = kmalloc_node(struct_size(head, cpu,
+				uv_blade_nr_possible_cpus(bid)),

It's probably safer to use kzalloc_node here as well.

Thanks for your feedback, Joe. I'll wait for comments from the maintainers on this and the rest of the patch.

Thanks
--
Gustavo

Quoted 4 lines
Quoted 3 lines
arch/x86/platform/uv/uv_time.c +0 -0
 				GFP_KERNEL, nid);
 			if (!head) {
 				uv_rtc_deallocate_timers();
Reviewed-by
#3 lore raw
In reply to Joe Perches
Quoted 28 lines · Joe Perches
Quoted 7 lines · Gustavo A. R. Silva

The current codebase makes use of one-element arrays in the following form:

struct something {
    int length;
    u8 data[1];
};

[]

Quoted 2 lines

This issue has been out there since 2009.
This issue was found with the help of Coccinelle and fixed _manually_.

[]

Quoted 16 lines
arch/x86/platform/uv/uv_time.c +1 -1
index 7af31b245636..993a8ae6fdfb 100644
@@ -52,7 +52,7 @@ struct uv_rtc_timer_head {
 	struct {
 		int	lcpu;		/* systemwide logical cpu number */
 		u64	expires;	/* next timer expiration for this cpu */
-	} cpu[1];
+	} cpu[];
 };
 
 /*
@@ -156,9 +156,8 @@ static __init int uv_rtc_allocate_timers(void)
 		struct uv_rtc_timer_head *head = blade_info[bid];
 
Quoted 8 lines

arch/x86/platform/uv/uv_time.c static __init int uv_rtc_allocate_timers(void) · line 160

Quoted 6 lines
arch/x86/platform/uv/uv_time.c +2 -3
 		if (!head) {
-			head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
-				(uv_blade_nr_possible_cpus(bid) *
-					2 * sizeof(u64)),
+			head = kmalloc_node(struct_size(head, cpu,
+				uv_blade_nr_possible_cpus(bid)),

It's probably safer to use kzalloc_node here as well.

Hm, I think it's not actually needed here. All three members are immediately initialized and it doesn't look to ever be copied to userspace.

Quoted 5 lines

arch/x86/platform/uv/uv_time.c static __init int uv_rtc_allocate_timers(void) · line 163

Quoted 4 lines
arch/x86/platform/uv/uv_time.c +0 -0
 				GFP_KERNEL, nid);
 			if (!head) {
 				uv_rtc_deallocate_timers();

FWIW, I think this change is good as-is. Always nice to get back a little memory. ;)

Signature · 1 line
Kees Cook
#4 lore raw
Quoted 9 lines · Kees Cook
Quoted 8 lines · Joe Perches
Quoted 7 lines · Gustavo A. R. Silva

The current codebase makes use of one-element arrays in the following form:

struct something {
    int length;
    u8 data[1];
};
Quoted 5 lines
Quoted 5 lines

[]

Quoted 2 lines

This issue has been out there since 2009.
This issue was found with the help of Coccinelle and fixed _manually_.

[]

arch/x86/platform/uv/uv_time.c

Quoted 1 line
arch/x86/platform/uv/uv_time.c +0 -0

[]

Quoted 12 lines
Quoted 11 lines

arch/x86/platform/uv/uv_time.c static __init int uv_rtc_allocate_timers(void) · line 160

Quoted 9 lines
arch/x86/platform/uv/uv_time.c +2 -3
@@ -156,9 +156,8 @@ static __init int uv_rtc_allocate_timers(void)
 		struct uv_rtc_timer_head *head = blade_info[bid];
 
 		if (!head) {
-			head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
-				(uv_blade_nr_possible_cpus(bid) *
-					2 * sizeof(u64)),
+			head = kmalloc_node(struct_size(head, cpu,
+				uv_blade_nr_possible_cpus(bid)),

It's probably safer to use kzalloc_node here as well.

Quoted 1 line

Hm, I think it's not actually needed here.

Right. Turns out it's not needed.

Quoted 3 lines

All three members are
immediately initialized and it doesn't look to ever be copied to userspace.

It's more that the reader doesn't have to lookup the struct to know all the members are initialized.

It's also not a fast path so any extra time to zero is not significant.

Quoted 6 lines
Quoted 3 lines

arch/x86/platform/uv/uv_time.c static __init int uv_rtc_allocate_timers(void) · line 163

Quoted 3 lines
arch/x86/platform/uv/uv_time.c +0 -0
 				GFP_KERNEL, nid);
 			if (!head) {
 				uv_rtc_deallocate_timers();

FWIW, I think this change is good as-is. Always nice to get back a little memory. ;)

Saving space, 0 to 4 bytes at a time,
depending on the heap sizes...

Using the struct_size is clearer though, so that's good too.

cheers, Joe

author Reviewed-by Kees Cook on v1 1/1
#5 lore raw
In reply to Gustavo A. R. Silva

[+CC John Stultz <[email protected]> and +Kees' Reviewed-by tag]

Quoted 122 lines · Gustavo A. R. Silva

The current codebase makes use of one-element arrays in the following form:

struct something {
    int length;
    u8 data[1];
};

struct something *instance;

instance = kmalloc(sizeof(*instance) + size, GFP_KERNEL); instance->length = size;
memcpy(instance->data, source, size);

but the preferred mechanism to declare variable-length types such as these ones is a flexible array member[1][2], introduced in C99:

struct foo {
        int stuff;
        struct boo array[];
};

By making use of the mechanism above, we will get a compiler warning in case the flexible array does not occur last in the structure, which will help us prevent some kind of undefined behavior bugs from being inadvertently introduced[3] to the codebase from now on. So, replace the one-element array with a flexible-array member.

Also, make use of the new struct_size() helper to properly calculate the total size needed to allocate dynamic memory for struct uv_rtc_timer_head. Notice that, due to the use of a one-element array, space for an extra struct cpu:

struct {

	int     lcpu;           /* systemwide logical cpu number */
	u64     expires;        /* next timer expiration for this cpu */

} cpu[1]

was being allocated at the moment of applying the sizeof operator to struct uv_rtc_timer_head in the call to kmalloc_node() at line 159:

159 head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
160 (uv_blade_nr_possible_cpus(bid) *
161 2 * sizeof(u64)),
162 GFP_KERNEL, nid);

but that extra cpu[] was never actually being accessed due to the following piece of code at line 168:

168 head->ncpus = uv_blade_nr_possible_cpus(bid);

and the piece of code at line 187:

187 for (c = 0; c < head->ncpus; c++) {
188 u64 exp = head->cpu[c].expires;
189 if (exp < lowest) {
190 bcpu = c;
191 lowest = exp;
192 }
193 }

so heap space was being wasted.

Another thing important to notice is that through the use of the struct_size() helper, code at line 161:

161 2 * sizeof(u64)),

is changed to now be the actual size of struct cpu; see sizeof(*(p)->member) at include/linux/overflow.h:314:

314 #define struct_size(p, member, n) \
315 __ab_c_size(n, \
316 sizeof(*(p)->member) + __must_be_array((p)->member),\
317 sizeof(*(p)))

As a side note, the original developer could have implemented code at line 161: 2 * sizeof(64) as follows:

sizeof(*head->cpu)

This issue has been out there since 2009.

This issue was found with the help of Coccinelle and fixed _manually_.

[1] https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
[2] https://github.com/KSPP/linux/issues/21
[3] commit 76497732932f ("cxgb3/l2t: Fix undefined behaviour")

---
 arch/x86/platform/uv/uv_time.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
arch/x86/platform/uv/uv_time.c +3 -4
index 7af31b245636..993a8ae6fdfb 100644
@@ -52,7 +52,7 @@ struct uv_rtc_timer_head {
 	struct {
 		int	lcpu;		/* systemwide logical cpu number */
 		u64	expires;	/* next timer expiration for this cpu */
-	} cpu[1];
+	} cpu[];
 };
 
 /*
@@ -156,9 +156,8 @@ static __init int uv_rtc_allocate_timers(void)
 		struct uv_rtc_timer_head *head = blade_info[bid];
 
 		if (!head) {
-			head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
-				(uv_blade_nr_possible_cpus(bid) *
-					2 * sizeof(u64)),
+			head = kmalloc_node(struct_size(head, cpu,
+				uv_blade_nr_possible_cpus(bid)),
 				GFP_KERNEL, nid);
 			if (!head) {
 				uv_rtc_deallocate_timers();
Signature · 1 line
2.26.2
#6 lore raw

Hi all,

Who can take this?

Thanks
--
Gustavo

Quoted 127 lines · Gustavo A. R. Silva

[+CC John Stultz <[email protected]> and +Kees' Reviewed-by tag]

Quoted 122 lines · Gustavo A. R. Silva

The current codebase makes use of one-element arrays in the following form:

struct something {
    int length;
    u8 data[1];
};

struct something *instance;

instance = kmalloc(sizeof(*instance) + size, GFP_KERNEL); instance->length = size;
memcpy(instance->data, source, size);

but the preferred mechanism to declare variable-length types such as these ones is a flexible array member[1][2], introduced in C99:

struct foo {
        int stuff;
        struct boo array[];
};

By making use of the mechanism above, we will get a compiler warning in case the flexible array does not occur last in the structure, which will help us prevent some kind of undefined behavior bugs from being inadvertently introduced[3] to the codebase from now on. So, replace the one-element array with a flexible-array member.

Also, make use of the new struct_size() helper to properly calculate the total size needed to allocate dynamic memory for struct uv_rtc_timer_head. Notice that, due to the use of a one-element array, space for an extra struct cpu:

struct {

	int     lcpu;           /* systemwide logical cpu number */
	u64     expires;        /* next timer expiration for this cpu */

} cpu[1]

was being allocated at the moment of applying the sizeof operator to struct uv_rtc_timer_head in the call to kmalloc_node() at line 159:

159 head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
160 (uv_blade_nr_possible_cpus(bid) *
161 2 * sizeof(u64)),
162 GFP_KERNEL, nid);

but that extra cpu[] was never actually being accessed due to the following piece of code at line 168:

168 head->ncpus = uv_blade_nr_possible_cpus(bid);

and the piece of code at line 187:

187 for (c = 0; c < head->ncpus; c++) {
188 u64 exp = head->cpu[c].expires;
189 if (exp < lowest) {
190 bcpu = c;
191 lowest = exp;
192 }
193 }

so heap space was being wasted.

Another thing important to notice is that through the use of the struct_size() helper, code at line 161:

161 2 * sizeof(u64)),

is changed to now be the actual size of struct cpu; see sizeof(*(p)->member) at include/linux/overflow.h:314:

314 #define struct_size(p, member, n) \
315 __ab_c_size(n, \
316 sizeof(*(p)->member) + __must_be_array((p)->member),\
317 sizeof(*(p)))

As a side note, the original developer could have implemented code at line 161: 2 * sizeof(64) as follows:

sizeof(*head->cpu)

This issue has been out there since 2009.

This issue was found with the help of Coccinelle and fixed _manually_.

[1] https://gcc.gnu.org/onlinedocs/gcc/Zero-Length.html
[2] https://github.com/KSPP/linux/issues/21
[3] commit 76497732932f ("cxgb3/l2t: Fix undefined behaviour")

---
 arch/x86/platform/uv/uv_time.c | 7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
arch/x86/platform/uv/uv_time.c +3 -4
index 7af31b245636..993a8ae6fdfb 100644
@@ -52,7 +52,7 @@ struct uv_rtc_timer_head {
 	struct {
 		int	lcpu;		/* systemwide logical cpu number */
 		u64	expires;	/* next timer expiration for this cpu */
-	} cpu[1];
+	} cpu[];
 };
 
 /*
@@ -156,9 +156,8 @@ static __init int uv_rtc_allocate_timers(void)
 		struct uv_rtc_timer_head *head = blade_info[bid];
 
 		if (!head) {
-			head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
-				(uv_blade_nr_possible_cpus(bid) *
-					2 * sizeof(u64)),
+			head = kmalloc_node(struct_size(head, cpu,
+				uv_blade_nr_possible_cpus(bid)),
 				GFP_KERNEL, nid);
 			if (!head) {
 				uv_rtc_deallocate_timers();
Signature · 1 line
2.26.2
#7 lore raw
In reply to Gustavo A. R. Silva
Quoted 76 lines · Gustavo A. R. Silva

The current codebase makes use of one-element arrays in the following form:

struct something {
    int length;
    u8 data[1];
};

struct something *instance;

instance = kmalloc(sizeof(*instance) + size, GFP_KERNEL); instance->length = size;
memcpy(instance->data, source, size);

but the preferred mechanism to declare variable-length types such as these ones is a flexible array member[1][2], introduced in C99:

struct foo {
        int stuff;
        struct boo array[];
};

By making use of the mechanism above, we will get a compiler warning in case the flexible array does not occur last in the structure, which will help us prevent some kind of undefined behavior bugs from being inadvertently introduced[3] to the codebase from now on. So, replace the one-element array with a flexible-array member.

Also, make use of the new struct_size() helper to properly calculate the total size needed to allocate dynamic memory for struct uv_rtc_timer_head. Notice that, due to the use of a one-element array, space for an extra struct cpu:

struct {

	int     lcpu;           /* systemwide logical cpu number */
	u64     expires;        /* next timer expiration for this cpu */

} cpu[1]

was being allocated at the moment of applying the sizeof operator to struct uv_rtc_timer_head in the call to kmalloc_node() at line 159:

159 head = kmalloc_node(sizeof(struct uv_rtc_timer_head) +
160 (uv_blade_nr_possible_cpus(bid) *
161 2 * sizeof(u64)),
162 GFP_KERNEL, nid);

but that extra cpu[] was never actually being accessed due to the following piece of code at line 168:

168 head->ncpus = uv_blade_nr_possible_cpus(bid);

and the piece of code at line 187:

187 for (c = 0; c < head->ncpus; c++) {
188 u64 exp = head->cpu[c].expires;
189 if (exp < lowest) {
190 bcpu = c;
191 lowest = exp;
192 }
193 }

so heap space was being wasted.

Another thing important to notice is that through the use of the struct_size() helper, code at line 161:

161 2 * sizeof(u64)),

is changed to now be the actual size of struct cpu; see sizeof(*(p)->member) at include/linux/overflow.h:314:

314 #define struct_size(p, member, n) \
315 __ab_c_size(n, \
316 sizeof(*(p)->member) + __must_be_array((p)->member),\
317 sizeof(*(p)))

Quoted 4 lines

As a side note, the original developer could have implemented code at line 161: 2 * sizeof(64) as follows:

sizeof(*head->cpu)

This changelog is an unparseable pile of word salad wasting brain heap space.

The gist is:

Variable sized arrays at the end of a struct should be defined as unsized array foo[] not as foo[1].

struct uv_rtc_timer_head contains a sized array cpu[1].

Switch it to an unsized array and use the struct_size() helper to calculate the allocation size.

Thanks,

tglx