Skip to contentSkip to conversation

sscanf: implement basic character sets

PATCH Superseded Jessica Yu 4 participants 8 messages Feb 23, 2016 – Feb 24, 2016

Subsystems (2)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Jessica Yu

author
#0 lore raw

PATCH v3 1/1 sscanf: implement basic character sets

Implement basic character sets for the '%[]' conversion specifier.

The '%[]' conversion specifier matches a nonempty sequence of characters from the specified set of accepted (or with '^', rejected) characters between the brackets. The substring matched is to be made up of characters in (or not in) the set. This implementation differs from its glibc counterpart in that it does not support character ranges (e.g., 'a-z' or '0-9'), the hyphen '-' is *not* a special character, and the brackets themselves cannot be matched.

---

This patch adds support for the '%[' conversion specifier for sscanf(). This is useful in cases where we'd like to match substrings delimited by something other than spaces. The original motivation for this patch actually came from a livepatch discussion (See: https://lkml.org/lkml/2016/2/8/790),
where we were trying to come up with a clean way to parse symbol names with substrings delimited by periods and commas.

Patch based on linux-next-20160223.

v3:
- Fix memory leak in error path (kfree() before returning)
- Remove redundant condition in while loop
- Style fix (*op)() -> op()

v2:
- Use kstrndup() to copy the character set from fmt instead of using a statically allocated array

 lib/vsprintf.c | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
lib/vsprintf.c +41 -0
index 525c8e1..983358a 100644
@@ -2714,6 +2714,47 @@ int vsscanf(const char *buf, const char *fmt, va_list args)
 			num++;
 		}
 		continue;
+		case '[':
+		{
+			char *s = (char *)va_arg(args, char *);
+			char *set;
+			size_t (*op)(const char *str, const char *set);
+			size_t len = 0;
+			bool negate = (*(fmt) == '^');
+
+			if (field_width == -1)
+				field_width = SHRT_MAX;
+
+			op = negate ? &strcspn : &strspn;
+			if (negate)
+				fmt++;
+
+			len = strcspn(fmt, "]");
+			/* invalid format; stop here */
+			if (!len)
+				return num;
+
+			set = kstrndup(fmt, len, GFP_KERNEL);
+			if (!set)
+				return num;
+
+			/* advance fmt past ']' */
+			fmt += len + 1;
+
+			len = op(str, set);
+			/* no matches */
+			if (!len) {
+				kfree(set);
+				return num;
+			}
+
+			while (len-- && field_width--)
+				*s++ = *str++;
+			*s = '\0';
+			kfree(set);
+			num++;
+		}
+		continue;
 		case 'o':
 			base = 8;
 			break;
Signature · 1 line
2.4.3
Reviewed-by on v3 1/1
#1 lore raw
Quoted 11 lines · Jessica Yu

Implement basic character sets for the '%[]' conversion specifier.

The '%[]' conversion specifier matches a nonempty sequence of characters from the specified set of accepted (or with '^', rejected) characters between the brackets. The substring matched is to be made up of characters in (or not in) the set. This implementation differs from its glibc counterpart in that it does not support character ranges (e.g., 'a-z' or '0-9'), the hyphen '-' is *not* a special character, and the brackets themselves cannot be matched.

-Kees

Quoted 78 lines

---

This patch adds support for the '%[' conversion specifier for sscanf(). This is useful in cases where we'd like to match substrings delimited by something other than spaces. The original motivation for this patch actually came from a livepatch discussion (See: https://lkml.org/lkml/2016/2/8/790),
where we were trying to come up with a clean way to parse symbol names with substrings delimited by periods and commas.

Patch based on linux-next-20160223.

v3:
- Fix memory leak in error path (kfree() before returning)
- Remove redundant condition in while loop
- Style fix (*op)() -> op()

v2:
- Use kstrndup() to copy the character set from fmt instead of using a statically allocated array

 lib/vsprintf.c | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
lib/vsprintf.c +41 -1
index 525c8e1..983358a 100644
@@ -2714,6 +2714,47 @@ int vsscanf(const char *buf, const char *fmt, va_list args)
                        num++;
                }
                continue;
+               case '[':
+               {
+                       char *s = (char *)va_arg(args, char *);
+                       char *set;
+                       size_t (*op)(const char *str, const char *set);
+                       size_t len = 0;
+                       bool negate = (*(fmt) == '^');
+
+                       if (field_width == -1)
+                               field_width = SHRT_MAX;
+
+                       op = negate ? &strcspn : &strspn;
+                       if (negate)
+                               fmt++;
+
+                       len = strcspn(fmt, "]");
+                       /* invalid format; stop here */
+                       if (!len)
+                               return num;
+
+                       set = kstrndup(fmt, len, GFP_KERNEL);
+                       if (!set)
+                               return num;
+
+                       /* advance fmt past ']' */
+                       fmt += len + 1;
+
+                       len = op(str, set);
+                       /* no matches */
+                       if (!len) {
+                               kfree(set);
+                               return num;
+                       }
+
+                       while (len-- && field_width--)
+                               *s++ = *str++;
+                       *s = '\0';
+                       kfree(set);
+                       num++;
+               }
+               continue;
                case 'o':
                        base = 8;
                        break;
--

2.4.3

Signature · 2 lines
Kees Cook
Chrome OS & Brillo Security
maintainer
#2 lore raw
In reply to Jessica Yu
Quoted 11 lines · On Tue, 23 Feb 2016 15:38:22 -0500 Jessica Yu <[email protected]> wrote:

Implement basic character sets for the '%[]' conversion specifier.

The '%[]' conversion specifier matches a nonempty sequence of characters from the specified set of accepted (or with '^', rejected) characters between the brackets. The substring matched is to be made up of characters in (or not in) the set. This implementation differs from its glibc counterpart in that it does not support character ranges (e.g., 'a-z' or '0-9'), the hyphen '-' is *not* a special character, and the brackets themselves cannot be matched.

Quoted 8 lines

---

This patch adds support for the '%[' conversion specifier for sscanf(). This is useful in cases where we'd like to match substrings delimited by something other than spaces. The original motivation for this patch actually came from a livepatch discussion (See: https://lkml.org/lkml/2016/2/8/790),
where we were trying to come up with a clean way to parse symbol names with substrings delimited by periods and commas.

It would be better to include the justification right here in the changelog please. Not via some link-to-discussion and definitely not below the ^--- marker! It's very important.

The deviation from the glibc behaviour is a bit of a worry, particularly as it is done in a non-back-compat manner: code which assumes "-" is non-magic might break if someone later adds range support.

Presumably we can live with that - there won't be many callsites and they can be grepped for. But please, let's get a description of all these considerations into the code as a comment. Probably it would be helpful to include a little usage example in that comment.

Quoted 17 lines
lib/vsprintf.c +11 -0
@@ -2714,6 +2714,47 @@ int vsscanf(const char *buf, const char *fmt, va_list args)
 			num++;
 		}
 		continue;
+		case '[':
+		{
+			char *s = (char *)va_arg(args, char *);
+			char *set;
+			size_t (*op)(const char *str, const char *set);
+			size_t len = 0;
+			bool negate = (*(fmt) == '^');
+
+			if (field_width == -1)
+				field_width = SHRT_MAX;
+

lib/vsprintf.c int vsscanf(const char *buf, const char *fmt, va_list args) · line 2737

Quoted 10 lines
lib/vsprintf.c +10 -0
+			op = negate ? &strcspn : &strspn;
+			if (negate)
+				fmt++;
+
+			len = strcspn(fmt, "]");
+			/* invalid format; stop here */
+			if (!len)
+				return num;
+
+			set = kstrndup(fmt, len, GFP_KERNEL);

Embedding a GFP_KERNEL allocation into vsscanf is problematic - it limits the situations in which this functionality can be used.

afaict the allocation is there merely so we can null-terminate the string so we can use existing library functions (strcspn, strspn). Is that compromise really worth it? We could pretty easily convert strcspn() into

strcnspn(const char *s, const char *reject, size_t len)

and convert strcspn() to call that (ifndef __HAVE_ARCH_STRCSPN)

In fact I think we could still use strspn() and strcspn() on fmt' directly? We just need to check for the return value exceeding len' and if so, treat that as a no-match?

Quoted 23 lines
lib/vsprintf.c +20 -0
+			if (!set)
+				return num;
+
+			/* advance fmt past ']' */
+			fmt += len + 1;
+
+			len = op(str, set);
+			/* no matches */
+			if (!len) {
+				kfree(set);
+				return num;
+			}
+
+			while (len-- && field_width--)
+				*s++ = *str++;
+			*s = '\0';
+			kfree(set);
+			num++;
+		}
+		continue;
 		case 'o':
 			base = 8;
 			break;
author
#3 lore raw

+++ Andrew Morton [23/02/16 14:05 -0800]:

Quoted 22 lines · On Tue, 23 Feb 2016 15:38:22 -0500 Jessica Yu <[email protected]> wrote:
Quoted 12 lines

Implement basic character sets for the '%[]' conversion specifier.

The '%[]' conversion specifier matches a nonempty sequence of characters from the specified set of accepted (or with '^', rejected) characters between the brackets. The substring matched is to be made up of characters in (or not in) the set. This implementation differs from its glibc counterpart in that it does not support character ranges (e.g., 'a-z' or '0-9'), the hyphen '-' is *not* a special character, and the brackets themselves cannot be matched.

Quoted 8 lines

---

This patch adds support for the '%[' conversion specifier for sscanf(). This is useful in cases where we'd like to match substrings delimited by something other than spaces. The original motivation for this patch actually came from a livepatch discussion (See: https://lkml.org/lkml/2016/2/8/790),
where we were trying to come up with a clean way to parse symbol names with substrings delimited by periods and commas.

Quoted 3 lines

It would be better to include the justification right here in the changelog please. Not via some link-to-discussion and definitely not below the ^--- marker! It's very important.

Thanks for the corrections Andrew. I am however slightly confused, are you suggesting that I should provide a much more thorough explanation about the motivation here in the changelog (below the ^--- marker), or would this be better suited for a (separate) cover letter?

Quoted 9 lines

The deviation from the glibc behaviour is a bit of a worry, particularly as it is done in a non-back-compat manner: code which assumes "-" is non-magic might break if someone later adds range support.

Presumably we can live with that - there won't be many callsites and they can be grepped for. But please, let's get a description of all these considerations into the code as a comment. Probably it would be helpful to include a little usage example in that comment.

Hm, that is a very good point. At the moment we can be sure there aren't any users of sscanf() using the %[ conversion specifier, as it doesn't exist yet :-) But yes, this behavior should be documented clearly in a comment, so future users will be aware..

Quoted 36 lines
Quoted 17 lines
lib/vsprintf.c +11 -0
@@ -2714,6 +2714,47 @@ int vsscanf(const char *buf, const char *fmt, va_list args)
 			num++;
 		}
 		continue;
+		case '[':
+		{
+			char *s = (char *)va_arg(args, char *);
+			char *set;
+			size_t (*op)(const char *str, const char *set);
+			size_t len = 0;
+			bool negate = (*(fmt) == '^');
+
+			if (field_width == -1)
+				field_width = SHRT_MAX;
+

lib/vsprintf.c int vsscanf(const char *buf, const char *fmt, va_list args) · line 2737

Quoted 10 lines
lib/vsprintf.c +10 -0
+			op = negate ? &strcspn : &strspn;
+			if (negate)
+				fmt++;
+
+			len = strcspn(fmt, "]");
+			/* invalid format; stop here */
+			if (!len)
+				return num;
+
+			set = kstrndup(fmt, len, GFP_KERNEL);

Embedding a GFP_KERNEL allocation into vsscanf is problematic - it limits the situations in which this functionality can be used.

afaict the allocation is there merely so we can null-terminate the string so we can use existing library functions (strcspn, strspn). Is that compromise really worth it? We could pretty easily convert strcspn() into

Quoted 8 lines

strcnspn(const char *s, const char *reject, size_t len)

and convert strcspn() to call that (ifndef __HAVE_ARCH_STRCSPN)

In fact I think we could still use strspn() and strcspn() on fmt' directly? We just need to check for the return value exceeding len' and if so, treat that as a no-match?

Perhaps we can use Rasmus' bitmap solution, as it avoids the allocation altogether and it doesn't need to use strspn()/strcspn().

Quoted 24 lines
Quoted 23 lines
lib/vsprintf.c +20 -0
+			if (!set)
+				return num;
+
+			/* advance fmt past ']' */
+			fmt += len + 1;
+
+			len = op(str, set);
+			/* no matches */
+			if (!len) {
+				kfree(set);
+				return num;
+			}
+
+			while (len-- && field_width--)
+				*s++ = *str++;
+			*s = '\0';
+			kfree(set);
+			num++;
+		}
+		continue;
 		case 'o':
 			base = 8;
 			break;
maintainer
#4 lore raw
Quoted 12 lines · On Wed, 24 Feb 2016 00:13:47 -0500 Jessica Yu <[email protected]> wrote:
Quoted 11 lines
Quoted 6 lines

This patch adds support for the '%[' conversion specifier for sscanf(). This is useful in cases where we'd like to match substrings delimited by something other than spaces. The original motivation for this patch actually came from a livepatch discussion (See: https://lkml.org/lkml/2016/2/8/790),
where we were trying to come up with a clean way to parse symbol names with substrings delimited by periods and commas.

It would be better to include the justification right here in the changelog please.
Not via some link-to-discussion and definitely not below the ^--- marker! It's very important.

Quoted 4 lines

Thanks for the corrections Andrew. I am however slightly confused, are you suggesting that I should provide a much more thorough explanation about the motivation here in the changelog (below the ^--- marker), or would this be better suited for a (separate) cover letter?

Just in the plain old changelog is good - if it was in [0/n] I'd only move it into the changelog anyway.

And 99.9% of the stuff people put below ^--- is useful so I always end up moving that into the changelog as well...

#5 lore raw
In reply to Jessica Yu
Quoted 48 lines · Jessica Yu

Implement basic character sets for the '%[]' conversion specifier.

 lib/vsprintf.c | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
lib/vsprintf.c +34 -0
index 525c8e1..983358a 100644
@@ -2714,6 +2714,47 @@ int vsscanf(const char *buf, const char *fmt, va_list args)
 			num++;
 		}
 		continue;
+		case '[':
+		{
+			char *s = (char *)va_arg(args, char *);
+			char *set;
+			size_t (*op)(const char *str, const char *set);
+			size_t len = 0;
+			bool negate = (*(fmt) == '^');
+
+			if (field_width == -1)
+				field_width = SHRT_MAX;
+
+			op = negate ? &strcspn : &strspn;
+			if (negate)
+				fmt++;
+
+			len = strcspn(fmt, "]");
+			/* invalid format; stop here */
+			if (!len)
+				return num;
+
+			set = kstrndup(fmt, len, GFP_KERNEL);
+			if (!set)
+				return num;
+
+			/* advance fmt past ']' */
+			fmt += len + 1;
+
+			len = op(str, set);
+			/* no matches */
+			if (!len) {
+				kfree(set);
+				return num;
+			}
+

lib/vsprintf.c int vsscanf(const char *buf, const char *fmt, va_list args) · line 2760

Quoted 10 lines
lib/vsprintf.c +7 -0
+			while (len-- && field_width--)
+				*s++ = *str++;
+			*s = '\0';
+			kfree(set);
+			num++;
+		}
+		continue;
 		case 'o':
 			base = 8;
 			break;

(1) How do we know that doing a memory allocation would be ok, and then with GFP_KERNEL? vsnprintf can be called from just about any context, so I don't think that would fly there. Sooner or later someone is going to be calling sscanf with a spinlock held, methinks.

(2) I think a field width should be mandatory (so %[ should simply be regarded as malformed - it should be %*[ or %n[ for some explicit decimal n). That will allow the compiler or other static analyzers to do sanity checking, and we'll probably be saved from a few buffer overflows down the line.

It's a bit sad that the C standard doesn't include the terminating '\0' in the field width, so one would sometimes have to write '(int)sizeof(buf)-1', but there's not much to do about that. On that note, it seems that your field width handling is off-by-one.

To get rid of the allocation, why not use a small bitmap? Something like

{
char *s = (char *)va_arg(args, char *);
DECLARE_BITMAP(map, 256) = {0};
bool negate = false;

/* a field width is required, and must provide room for at least a '\0' */ if (field_width <= 0)

    return num;
  if (*fmt == '^') {
    negate = true;
    ++fmt;
  }
  for ( ; *fmt && *fmt != ']'; ++fmt)
    set_bit((u8)*fmt, map);
  if (!*fmt) // no ], so malformed input
    return num;
  ++fmt;
  if (negate) {
    bitmap_complement(map, map, 256);
    clear_bit(0, map); // this avoids testing *str != '\0' below
  }

if (!test_bit((u8)*str, map)) // match must be non-empty

    return num;
  while (test_bit((u8)*str, map) && --field_width) {
    *s++ = *str++;

}
*s = '\0';
++num;
}

Rasmus

#6 lore raw
Quoted 1 line · Rasmus Villemoes

On that note, it seems that your field width handling is off-by-one.

Sorry about that, it's me who's off-by-one.

Rasmus

Quoted 11 lines

To get rid of the allocation, why not use a small bitmap? Something like

{
char *s = (char *)va_arg(args, char *);
DECLARE_BITMAP(map, 256) = {0};
bool negate = false;

/* a field width is required, and must provide room for at least a '\0' */ if (field_width <= 0)

    return num;

should be

/* a field width is required */
if (field_width < 0)

and

Quoted 1 line
  while (test_bit((u8)*str, map) && --field_width) {

should be field_width--, exactly as in your code.

author
#7 lore raw
In reply to Rasmus Villemoes

+++ Rasmus Villemoes [23/02/16 23:47 +0100]:

Quoted 102 lines · Jessica Yu
Quoted 49 lines

Implement basic character sets for the '%[]' conversion specifier.

 lib/vsprintf.c | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
lib/vsprintf.c +34 -0
index 525c8e1..983358a 100644
@@ -2714,6 +2714,47 @@ int vsscanf(const char *buf, const char *fmt, va_list args)
 			num++;
 		}
 		continue;
+		case '[':
+		{
+			char *s = (char *)va_arg(args, char *);
+			char *set;
+			size_t (*op)(const char *str, const char *set);
+			size_t len = 0;
+			bool negate = (*(fmt) == '^');
+
+			if (field_width == -1)
+				field_width = SHRT_MAX;
+
+			op = negate ? &strcspn : &strspn;
+			if (negate)
+				fmt++;
+
+			len = strcspn(fmt, "]");
+			/* invalid format; stop here */
+			if (!len)
+				return num;
+
+			set = kstrndup(fmt, len, GFP_KERNEL);
+			if (!set)
+				return num;
+
+			/* advance fmt past ']' */
+			fmt += len + 1;
+
+			len = op(str, set);
+			/* no matches */
+			if (!len) {
+				kfree(set);
+				return num;
+			}
+

lib/vsprintf.c int vsscanf(const char *buf, const char *fmt, va_list args) · line 2760

Quoted 10 lines
lib/vsprintf.c +7 -0
+			while (len-- && field_width--)
+				*s++ = *str++;
+			*s = '\0';
+			kfree(set);
+			num++;
+		}
+		continue;
 		case 'o':
 			base = 8;
 			break;

(1) How do we know that doing a memory allocation would be ok, and then with GFP_KERNEL? vsnprintf can be called from just about any context, so I don't think that would fly there. Sooner or later someone is going to be calling sscanf with a spinlock held, methinks.

(2) I think a field width should be mandatory (so %[ should simply be regarded as malformed - it should be %*[ or %n[ for some explicit decimal n). That will allow the compiler or other static analyzers to do sanity checking, and we'll probably be saved from a few buffer overflows down the line.

It's a bit sad that the C standard doesn't include the terminating '\0' in the field width, so one would sometimes have to write '(int)sizeof(buf)-1', but there's not much to do about that. On that note, it seems that your field width handling is off-by-one.

To get rid of the allocation, why not use a small bitmap? Something like

{
char *s = (char *)va_arg(args, char *);
DECLARE_BITMAP(map, 256) = {0};
bool negate = false;

/* a field width is required, and must provide room for at least a '\0' */ if (field_width <= 0)
return num;

 if (*fmt == '^') {
   negate = true;
   ++fmt;
 }
 for ( ; *fmt && *fmt != ']'; ++fmt)
   set_bit((u8)*fmt, map);
 if (!*fmt) // no ], so malformed input
   return num;
 ++fmt;
 if (negate) {
   bitmap_complement(map, map, 256);
   clear_bit(0, map); // this avoids testing *str != '\0' below

}

Quoted 8 lines

if (!test_bit((u8)*str, map)) // match must be non-empty
return num;

 while (test_bit((u8)*str, map) && --field_width) {
   *s++ = *str++;

}
*s = '\0';
++num;
}

I quite like this idea, as it avoids allocations and doesn't need strcspn/strspn. What do other people think?