[PATCH] readkey: shrink table of known escape sequences in size

[PATCH] readkey: shrink table of known escape sequences in size

[Ahmad Fatoum]

Instead of storing pointers to 4-byte strings, we could just store the
characters directly in the struct. Can save us up to 18 pointers worth
of space.

We could save 18 x 1 byte more of static storage by making the strings
3 bytes of length as the nul byte need not be stored explicitly for
strings of maximal length.

For clarity, this optimization is omitted for now. We still use strncmp,
instead of strcmp use runs risk of accidental out of bounds reads when
longer escape sequences are added. This can't occur with strncmp.

Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
---
v1 -> v2:
  - Maintain a nul delimiter always at the cost of 18 more bytes
    (Sascha)
---
 lib/readkey.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/lib/readkey.c b/lib/readkey.c
index c26e9d51aba9..6a4ddf14a99d 100644
--- a/lib/readkey.c
+++ b/lib/readkey.c
@@ -20,8 +20,10 @@
 #include <linux/ctype.h>
 #include <readkey.h>
 
+#define MAX_ESC_LEN 4
+
 struct esc_cmds {
-	const char *seq;
+	const char seq[MAX_ESC_LEN];
 	unsigned char val;
 };
 
@@ -49,7 +51,7 @@ static const struct esc_cmds esccmds[] = {
 int read_key(void)
 {
 	unsigned char c;
-	unsigned char esc[5];
+	unsigned char esc[MAX_ESC_LEN + 2];
 	c = getchar();
 
 	if (c == 27) {
@@ -67,7 +69,7 @@ int read_key(void)
 		}
 		esc[i] = 0;
 		for (i = 0; i < ARRAY_SIZE(esccmds); i++){
-			if (!strcmp(esc, esccmds[i].seq))
+			if (!strncmp(esc, esccmds[i].seq, MAX_ESC_LEN))
 				return esccmds[i].val;
 		}
 		return -1;
-- 
2.28.0


_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

Re: [PATCH] readkey: shrink table of known escape sequences in size

[Sascha Hauer]

On Mon, Sep 28, 2020 at 02:39:42PM +0200, Ahmad Fatoum wrote:
> Instead of storing pointers to 4-byte strings, we could just store the
> characters directly in the struct. Can save us up to 18 pointers worth
> of space.
> 
> We could save 18 x 1 byte more of static storage by making the strings
> 3 bytes of length as the nul byte need not be stored explicitly for
> strings of maximal length.
> 
> For clarity, this optimization is omitted for now. We still use strncmp,
> instead of strcmp use runs risk of accidental out of bounds reads when
> longer escape sequences are added. This can't occur with strncmp.
> 
> Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
> ---
> v1 -> v2:
>   - Maintain a nul delimiter always at the cost of 18 more bytes
>     (Sascha)
> ---
>  lib/readkey.c | 8 +++++---
>  1 file changed, 5 insertions(+), 3 deletions(-)
> 
> diff --git a/lib/readkey.c b/lib/readkey.c
> index c26e9d51aba9..6a4ddf14a99d 100644
> --- a/lib/readkey.c
> +++ b/lib/readkey.c
> @@ -20,8 +20,10 @@
>  #include <linux/ctype.h>
>  #include <readkey.h>
>  
> +#define MAX_ESC_LEN 4
> +
>  struct esc_cmds {
> -	const char *seq;
> +	const char seq[MAX_ESC_LEN];
>  	unsigned char val;
>  };
>  
> @@ -49,7 +51,7 @@ static const struct esc_cmds esccmds[] = {
>  int read_key(void)
>  {
>  	unsigned char c;
> -	unsigned char esc[5];
> +	unsigned char esc[MAX_ESC_LEN + 2];
>  	c = getchar();
>  
>  	if (c == 27) {
> @@ -67,7 +69,7 @@ int read_key(void)
>  		}
>  		esc[i] = 0;
>  		for (i = 0; i < ARRAY_SIZE(esccmds); i++){
> -			if (!strcmp(esc, esccmds[i].seq))
> +			if (!strncmp(esc, esccmds[i].seq, MAX_ESC_LEN))
>  				return esccmds[i].val;

strncmp() gives you undesired results when 'esc' is longer than
MAX_ESC_LEN. Please don't start proving me that this can't happen in the
current code. I still don't think that saving a few bytes is worth the
hassle.

Sascha


-- 
Pengutronix e.K.                           |                             |
Steuerwalder Str. 21                       | http://www.pengutronix.de/  |
31137 Hildesheim, Germany                  | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |

_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

Re: [PATCH] readkey: shrink table of known escape sequences in size

[Ahmad Fatoum]

Hi,

On 9/28/20 1:58 PM, Sascha Hauer wrote:
>>>>  	if (c == 27) {
>>>> @@ -67,7 +69,7 @@ int read_key(void)
>>>>  		}
>>>>  		esc[i] = 0;
>>>>  		for (i = 0; i < ARRAY_SIZE(esccmds); i++){
>>>> -			if (!strcmp(esc, esccmds[i].seq))
>>>> +			if (!strncmp(esc, esccmds[i].seq, MAX_ESC_LEN))
>>>>  				return esccmds[i].val;
>>>
>>> Anyway, I don't think we should play tricks with dropping string
>>> termination characters just to squeeze some bytes out of the binary.
>>
>> I can define #define MAX_ESC_LEN 4 if you prefer that, but I consider
>> it superfluous.
> 
> That would allow you to use strcmp and I really prefer that. strncmp
> doesn't give you the desired result when one string is longer than the
> length given in the third argument. Proving that this cannot happen here
> requires more brain time than parsing strcmp, at least in my brain ;)

I would still maintain the strncmp, because it's less error-prone:
If in future a new sequence is added, it will be truncated instead of
an out-of-bounds read.

v2 just sent out

> 
> Sascha
> 

-- 
Pengutronix e.K.                           |                             |
Steuerwalder Str. 21                       | http://www.pengutronix.de/  |
31137 Hildesheim, Germany                  | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |

_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

Re: [PATCH] readkey: shrink table of known escape sequences in size

[Sascha Hauer]

On Mon, Sep 28, 2020 at 01:51:22PM +0200, Ahmad Fatoum wrote:
> Hello Sascha,
> 
> On 9/28/20 11:31 AM, Sascha Hauer wrote:
> > On Mon, Sep 14, 2020 at 11:59:48AM +0200, Ahmad Fatoum wrote:
> >> Instead of storing pointers to 4-byte strings, we could just store the
> >> characters directly in the struct. Can save us up to 18 pointers worth
> >> of space. Additionally, the nul byte need not be stored explicitly for
> >> 3-byte strings, if we know those are the largest strings we have.
> >>
> >> The latter likely does not save us any space because of the usual
> >> alignment rules, but it will allow us to support sequences one byte
> >> bigger in future at no increase in size.
> >>
> >> Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
> >> ---
> >>  lib/readkey.c | 8 +++++---
> >>  1 file changed, 5 insertions(+), 3 deletions(-)
> >>
> >> diff --git a/lib/readkey.c b/lib/readkey.c
> >> index c26e9d51aba9..551296de3eb6 100644
> >> --- a/lib/readkey.c
> >> +++ b/lib/readkey.c
> >> @@ -20,8 +20,10 @@
> >>  #include <linux/ctype.h>
> >>  #include <readkey.h>
> >>  
> >> +#define MAX_ESC_LEN 3
> >> +
> >>  struct esc_cmds {
> >> -	const char *seq;
> >> +	const char seq[MAX_ESC_LEN];
> > 
> > I would have expected that when this array is initialized with a static
> > initializer, the compiler would add a \0 at the end. Apparently this is
> > not the case, initializing this 3 byte array with "[6~" is perfectly
> > fine for the compiler.
> 
> Initializers are padded with zeroes if they are too short.
> 
> >> @@ -49,7 +51,7 @@ static const struct esc_cmds esccmds[] = {
> >>  int read_key(void)
> >>  {
> >>  	unsigned char c;
> >> -	unsigned char esc[5];
> >> +	unsigned char esc[MAX_ESC_LEN + 2];
> >>  	c = getchar();
> >>  
> >>  	if (c == 27) {
> >> @@ -67,7 +69,7 @@ int read_key(void)
> >>  		}
> >>  		esc[i] = 0;
> >>  		for (i = 0; i < ARRAY_SIZE(esccmds); i++){
> >> -			if (!strcmp(esc, esccmds[i].seq))
> >> +			if (!strncmp(esc, esccmds[i].seq, MAX_ESC_LEN))
> >>  				return esccmds[i].val;
> > 
> > Anyway, I don't think we should play tricks with dropping string
> > termination characters just to squeeze some bytes out of the binary.
> 
> I can define #define MAX_ESC_LEN 4 if you prefer that, but I consider
> it superfluous.

That would allow you to use strcmp and I really prefer that. strncmp
doesn't give you the desired result when one string is longer than the
length given in the third argument. Proving that this cannot happen here
requires more brain time than parsing strcmp, at least in my brain ;)

Sascha

-- 
Pengutronix e.K.                           |                             |
Steuerwalder Str. 21                       | http://www.pengutronix.de/  |
31137 Hildesheim, Germany                  | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |

_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

Re: [PATCH] readkey: shrink table of known escape sequences in size

[Ahmad Fatoum]

Hello Sascha,

On 9/28/20 11:31 AM, Sascha Hauer wrote:
> On Mon, Sep 14, 2020 at 11:59:48AM +0200, Ahmad Fatoum wrote:
>> Instead of storing pointers to 4-byte strings, we could just store the
>> characters directly in the struct. Can save us up to 18 pointers worth
>> of space. Additionally, the nul byte need not be stored explicitly for
>> 3-byte strings, if we know those are the largest strings we have.
>>
>> The latter likely does not save us any space because of the usual
>> alignment rules, but it will allow us to support sequences one byte
>> bigger in future at no increase in size.
>>
>> Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
>> ---
>>  lib/readkey.c | 8 +++++---
>>  1 file changed, 5 insertions(+), 3 deletions(-)
>>
>> diff --git a/lib/readkey.c b/lib/readkey.c
>> index c26e9d51aba9..551296de3eb6 100644
>> --- a/lib/readkey.c
>> +++ b/lib/readkey.c
>> @@ -20,8 +20,10 @@
>>  #include <linux/ctype.h>
>>  #include <readkey.h>
>>  
>> +#define MAX_ESC_LEN 3
>> +
>>  struct esc_cmds {
>> -	const char *seq;
>> +	const char seq[MAX_ESC_LEN];
> 
> I would have expected that when this array is initialized with a static
> initializer, the compiler would add a \0 at the end. Apparently this is
> not the case, initializing this 3 byte array with "[6~" is perfectly
> fine for the compiler.

Initializers are padded with zeroes if they are too short.

>> @@ -49,7 +51,7 @@ static const struct esc_cmds esccmds[] = {
>>  int read_key(void)
>>  {
>>  	unsigned char c;
>> -	unsigned char esc[5];
>> +	unsigned char esc[MAX_ESC_LEN + 2];
>>  	c = getchar();
>>  
>>  	if (c == 27) {
>> @@ -67,7 +69,7 @@ int read_key(void)
>>  		}
>>  		esc[i] = 0;
>>  		for (i = 0; i < ARRAY_SIZE(esccmds); i++){
>> -			if (!strcmp(esc, esccmds[i].seq))
>> +			if (!strncmp(esc, esccmds[i].seq, MAX_ESC_LEN))
>>  				return esccmds[i].val;
> 
> Anyway, I don't think we should play tricks with dropping string
> termination characters just to squeeze some bytes out of the binary.

I can define #define MAX_ESC_LEN 4 if you prefer that, but I consider
it superfluous.

Cheers,
Ahmad

> 
> Sascha
> 

-- 
Pengutronix e.K.                           |                             |
Steuerwalder Str. 21                       | http://www.pengutronix.de/  |
31137 Hildesheim, Germany                  | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |

_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

Re: [PATCH] readkey: shrink table of known escape sequences in size

[Sascha Hauer]

On Mon, Sep 14, 2020 at 11:59:48AM +0200, Ahmad Fatoum wrote:
> Instead of storing pointers to 4-byte strings, we could just store the
> characters directly in the struct. Can save us up to 18 pointers worth
> of space. Additionally, the nul byte need not be stored explicitly for
> 3-byte strings, if we know those are the largest strings we have.
> 
> The latter likely does not save us any space because of the usual
> alignment rules, but it will allow us to support sequences one byte
> bigger in future at no increase in size.
> 
> Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
> ---
>  lib/readkey.c | 8 +++++---
>  1 file changed, 5 insertions(+), 3 deletions(-)
> 
> diff --git a/lib/readkey.c b/lib/readkey.c
> index c26e9d51aba9..551296de3eb6 100644
> --- a/lib/readkey.c
> +++ b/lib/readkey.c
> @@ -20,8 +20,10 @@
>  #include <linux/ctype.h>
>  #include <readkey.h>
>  
> +#define MAX_ESC_LEN 3
> +
>  struct esc_cmds {
> -	const char *seq;
> +	const char seq[MAX_ESC_LEN];

I would have expected that when this array is initialized with a static
initializer, the compiler would add a \0 at the end. Apparently this is
not the case, initializing this 3 byte array with "[6~" is perfectly
fine for the compiler.

> @@ -49,7 +51,7 @@ static const struct esc_cmds esccmds[] = {
>  int read_key(void)
>  {
>  	unsigned char c;
> -	unsigned char esc[5];
> +	unsigned char esc[MAX_ESC_LEN + 2];
>  	c = getchar();
>  
>  	if (c == 27) {
> @@ -67,7 +69,7 @@ int read_key(void)
>  		}
>  		esc[i] = 0;
>  		for (i = 0; i < ARRAY_SIZE(esccmds); i++){
> -			if (!strcmp(esc, esccmds[i].seq))
> +			if (!strncmp(esc, esccmds[i].seq, MAX_ESC_LEN))
>  				return esccmds[i].val;

Anyway, I don't think we should play tricks with dropping string
termination characters just to squeeze some bytes out of the binary.

Sascha

-- 
Pengutronix e.K.                           |                             |
Steuerwalder Str. 21                       | http://www.pengutronix.de/  |
31137 Hildesheim, Germany                  | Phone: +49-5121-206917-0    |
Amtsgericht Hildesheim, HRA 2686           | Fax:   +49-5121-206917-5555 |

_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox

[PATCH] readkey: shrink table of known escape sequences in size

[Ahmad Fatoum]

Instead of storing pointers to 4-byte strings, we could just store the
characters directly in the struct. Can save us up to 18 pointers worth
of space. Additionally, the nul byte need not be stored explicitly for
3-byte strings, if we know those are the largest strings we have.

The latter likely does not save us any space because of the usual
alignment rules, but it will allow us to support sequences one byte
bigger in future at no increase in size.

Signed-off-by: Ahmad Fatoum <a.fatoum@pengutronix.de>
---
 lib/readkey.c | 8 +++++---
 1 file changed, 5 insertions(+), 3 deletions(-)

diff --git a/lib/readkey.c b/lib/readkey.c
index c26e9d51aba9..551296de3eb6 100644
--- a/lib/readkey.c
+++ b/lib/readkey.c
@@ -20,8 +20,10 @@
 #include <linux/ctype.h>
 #include <readkey.h>
 
+#define MAX_ESC_LEN 3
+
 struct esc_cmds {
-	const char *seq;
+	const char seq[MAX_ESC_LEN];
 	unsigned char val;
 };
 
@@ -49,7 +51,7 @@ static const struct esc_cmds esccmds[] = {
 int read_key(void)
 {
 	unsigned char c;
-	unsigned char esc[5];
+	unsigned char esc[MAX_ESC_LEN + 2];
 	c = getchar();
 
 	if (c == 27) {
@@ -67,7 +69,7 @@ int read_key(void)
 		}
 		esc[i] = 0;
 		for (i = 0; i < ARRAY_SIZE(esccmds); i++){
-			if (!strcmp(esc, esccmds[i].seq))
+			if (!strncmp(esc, esccmds[i].seq, MAX_ESC_LEN))
 				return esccmds[i].val;
 		}
 		return -1;
-- 
2.28.0


_______________________________________________
barebox mailing list
barebox@lists.infradead.org
http://lists.infradead.org/mailman/listinfo/barebox