Bad interaction between macro expansion and literal concatenation

In get_string_constant(), the code tried to reuse the storage for the string but only if the expansion of the string was not bigger than its unexpanded form. But this fail when the string constant is a sequence of adjacent string litterals (each being possibly shared, used elsewhere, isolated or in another order). The minimal exemple would be something like this:

#define P "\001"
const char a[] = P "a";
const char b[] = P "b";

The expansion for 'a' will produce a string which is smaller than
the unexpanded "\001" (2 instead of 4).
By trying to reuse the storage, all further occurrence of "\001"
(probably only from the same 'origin', here the macro P) will then be replaced by "\001a".

The fix is thus to not try to reuse the storage for the string if it consit of several adjacent litterals.

Quoted 10 lines · Luc Van Oostenryck

In get_string_constant(), the code tried to reuse the storage for the string but only if the expansion of the string was not bigger than its unexpanded form. But this fail when the string constant is a sequence of adjacent string litterals (each being possibly shared, used elsewhere, isolated or in another order). The minimal exemple would be something like this:

#define P "\001"
const char a[] = P "a";
const char b[] = P "b";

Quoted 8 lines

The expansion for 'a' will produce a string which is smaller than
the unexpanded "\001" (2 instead of 4).
By trying to reuse the storage, all further occurrence of "\001"
(probably only from the same 'origin', here the macro P) will then be replaced by "\001a".

The fix is thus to not try to reuse the storage for the string if it consit of several adjacent litterals.

Thanks, but there's still something wrong. Using your show-data feature on this:

===
#define BACKSLASH "\\"
#define LETTER_t "t"

static const char s1[] = BACKSLASH;
/* static const char s2[] = BACKSLASH; */ static const char s3[] = BACKSLASH LETTER_t; static const char s4[] = "a" BACKSLASH LETTER_t "b";
===

I get

symbol s1:

        char static const [toplevel] s1[0]
        bit_size = 16
        val = "\\"
symbol s3:
        char static const [toplevel] s3[0]
        bit_size = 24
        val = "\0t"
symbol s4:
        char static const [toplevel] s4[0]
        bit_size = 40
        val = "a\0tb"

Now if I do the same with s2 not commented out, I get

symbol s1:

        char static const [toplevel] s1[0]
        bit_size = 16
        val = "\0"
symbol s2:
        char static const [toplevel] s2[0]
        bit_size = 16
        val = "\0"
symbol s3:
        char static const [toplevel] s3[0]
        bit_size = 24
        val = "\0t"
symbol s4:
        char static const [toplevel] s4[0]
        bit_size = 40
        val = "a\0tb"

So the expansion of BACKSLASH changes depending on how often it is expanded...

The LETTER_t thing above is because I thought I had somehow provoked a double expansion, making BACKSLASH LETTER_t (or some variant) expand to a single-character string containing just a tab. But I can't seem to reproduce that particular behaviour, so maybe I'm imagining stuff. Anyway, the above is certainly real.

Thanks,
Rasmus
--

Now thinking about it, it's obvious that the string buffer can't be reused at all if there is any kind of expansion done on it, the adjacent strings concatenation make just the thing worse but are not the cause of it.

Quoted 58 lines · Rasmus Villemoes

Thanks, but there's still something wrong. Using your show-data feature on this:

===
#define BACKSLASH "\\"
#define LETTER_t "t"

static const char s1[] = BACKSLASH;
/* static const char s2[] = BACKSLASH; */ static const char s3[] = BACKSLASH LETTER_t; static const char s4[] = "a" BACKSLASH LETTER_t "b";
===

I get

symbol s1:

        char static const [toplevel] s1[0]
        bit_size = 16
        val = "\\"
symbol s3:
        char static const [toplevel] s3[0]
        bit_size = 24
        val = "\0t"
symbol s4:
        char static const [toplevel] s4[0]
        bit_size = 40
        val = "a\0tb"

Now if I do the same with s2 not commented out, I get

symbol s1:

        char static const [toplevel] s1[0]
        bit_size = 16
        val = "\0"
symbol s2:
        char static const [toplevel] s2[0]
        bit_size = 16
        val = "\0"
symbol s3:
        char static const [toplevel] s3[0]
        bit_size = 24
        val = "\0t"
symbol s4:
        char static const [toplevel] s4[0]
        bit_size = 40
        val = "a\0tb"

So the expansion of BACKSLASH changes depending on how often it is expanded...

The LETTER_t thing above is because I thought I had somehow provoked a double expansion, making BACKSLASH LETTER_t (or some variant) expand to a single-character string containing just a tab. But I can't seem to reproduce that particular behaviour, so maybe I'm imagining stuff. Anyway, the above is certainly real.

Quoted 3 lines

Thanks,
Rasmus
--

Yes, I see.

Now thinking about it, it's obvious that the string buffer can't be reused at all if there is any kind of expansion done on it, the adjacent strings concatenation make just the thing worse but are not the cause of it.

And I wasn't hallucinating, I was just overcomplicating things:

#define NOT_TAB "\\t"

static const char s1[] = NOT_TAB;
static const char s2[] = NOT_TAB;

indeed fails.

Quoted 7 lines · Rasmus Villemoes

And I wasn't hallucinating, I was just overcomplicating things:

#define NOT_TAB "\\t"

static const char s1[] = NOT_TAB;
static const char s2[] = NOT_TAB;

Quoted 1 line

indeed fails.

While we're collecting examples, let me also mention that __FILE__ doesn't work for files with backslash in their name. Sane people of course don't put backslashes in file names, but they are a rather normal occurence in path names on a certain operating system.

Quoted 11 lines · Rasmus Villemoes

Quoted 8 lines · Rasmus Villemoes

And I wasn't hallucinating, I was just overcomplicating things:

#define NOT_TAB "\\t"

static const char s1[] = NOT_TAB;
static const char s2[] = NOT_TAB;

indeed fails.

Quoted 4 lines

While we're collecting examples, let me also mention that __FILE__ doesn't work for files with backslash in their name. Sane people of course don't put backslashes in file names, but they are a rather normal occurence in path names on a certain operating system.

Can you submit a patch for adding the test case you found? I will include those into the the test suit.

Quoted 2 lines

Can you submit a patch for adding the test case you found? I will include those into the the test suit.

I'd like to, but I'm not sure how to write the test in terms of sparse's test frame work. How do I check that the string is as expected?

Quoted 5 lines · Rasmus Villemoes

Quoted 2 lines

Can you submit a patch for adding the test case you found? I will include those into the the test suit.

I'd like to, but I'm not sure how to write the test in terms of sparse's test frame work. How do I check that the string is as expected?

You can use ./test-parsing to evaluate the test file.

In get_string_constant(), the code tried to reuse the storage for the string but only if the expansion of the string was not bigger than its unexpanded form. But this string can be shared with other expressions and reusing the buffer will result in later corruption

A minimal exemple would be something like:
const char a[] = BACKSLASH;
const char b[] = BACKSLASH;

The expansion for 'a' will correctly produce the two-char string consisting of a backslash char followed by a null char.
But then the expansion of 'b' will expand this once more, producing the expansion of "\0": the two-char string: { '\0', '\0' }.

The fix is to not reuse the storage for the string if any king of expansion have been done.

Reported-by Rasmus Villemoes <[email protected]>

Signed-off-by Luc Van Oostenryck <[email protected]>

---
 char.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

char.c +0 -0

index 08ca2230..2e21bb77 100644

Quoted 10 lines · Luc Van Oostenryck

In get_string_constant(), the code tried to reuse the storage for the string but only if the expansion of the string was not bigger than its unexpanded form. But this string can be shared with other expressions and reusing the buffer will result in later corruption

A minimal exemple would be something like:
const char a[] = BACKSLASH;
const char b[] = BACKSLASH;

Quoted 4 lines

The expansion for 'a' will correctly produce the two-char string consisting of a backslash char followed by a null char.
But then the expansion of 'b' will expand this once more, producing the expansion of "\0": the two-char string: { '\0', '\0' }.

Are you sure about this behavior? You mean you see "b" has the string size as 2. I haven't understand how this can happen.

Quoted 2 lines

The fix is to not reuse the storage for the string if any king of expansion have been done.

That is a bit over kill. We only need to avoid reuse storage if the destination part of the string is come from a preprocessor macro. It is pretty common string contain escape sequence. We don't want to allocate extra memory copy if it is not part of a macro expansion.

Quoted 15 lines

Reported-by Rasmus Villemoes <[email protected]>

Signed-off-by Luc Van Oostenryck <[email protected]>

---
 char.c | 12 ++++++++----
 1 file changed, 8 insertions(+), 4 deletions(-)

char.c +0 -0

index 08ca2230..2e21bb77 100644
@@ -123,11 +123,15 @@ struct token *get_string_constant(struct token *token, struct expression *expr)
                len = MAX_STRING;
        }
 

char.c struct token *get_string_constant(struct token *token, struct expression *expr) · line 129

Quoted 5 lines

char.c +4 -1

-       if (len >= string->length)      /* can't cannibalize */
+       /* The input string can be shared with other expression and so
+        * its storage can't be reused if any kind of expansion have been done on it.
+        */
+       if ((len != string->length) || memcmp(buffer, string->data, len)) {

I don' think this check take into account the preprocessor macro has been used or not. In other words, any general "hello world\n" which contain the escape character will produce a different buffer, there for, a new copy of the string. Which is not necessary. That is a pretty common case.

I am working on patch to address it in the preprocessor macro. The idea is that just mark the string as immutable if it is part of the macro expansion. I will see how it goes.

Chris
--

Quoted 2 lines

Are you sure about this behavior? You mean you see "b" has the string size as 2. I haven't understand how this can happen.

But if the macro is used several times:
===
#define BACKSLASH "\\"
const char a[] = BACKSLASH;
const char b[] = BACKSLASH;
const char c[] = "<" BACKSLASH ">";
===

the, we get:
===
symbol a:

        char const [addressable] [toplevel] a[0]
        bit_size = 16
        val = "\0"

symbol b:
char const [addressable] [toplevel] b[0]
bit_size = 16

Is it only with macros that the string structure is so shared?

And have we a way to test if the string is coming from a macro?

A simpler and safer way would be to directly do the string expansion just after a string token is recognized, or even better in the lexer itself.
So the string buffer, macro or not, will always directly contain the right values. But maybe there was good reasons to not do it this way.

When the lexer process the escape char, you did not know the string is wide char or not. That can be changed after the macro expansion.

Quoted 3 lines · Christopher Li

When the lexer process the escape char, you did not know the string is wide char or not. That can be changed after the macro expansion.

With that in mind, we can't actually perform the escape char substitution before the pre-processor stage.

Here is an untested patch adding the immutable string to macro body. I need to double check if the macro arguments needs it as well.

Can you guys try it on the test case you have?

Thanks

Chris

Working perfectly here.

Quoted 3 lines · Luc Van Oostenryck

Working perfectly here.

Any update of the string test case?

I commit a review version of the immutable string fix in review-immutable-string branch. Compare to the last patch, it take into account that string can come from
macro arguments rather than macro body.

It also avoid the string copy if there is no change, that is pretty common as well.

Care to give this version a try?

https://git.kernel.org/cgit/devel/sparse/chrisl/sparse.git/commit/?h=review-immutable-string&id=de1fa7e60d3d179a1b67c47a0429b2d0ac4e4842

Quoted 15 lines · Luc Van Oostenryck

Quoted 2 lines

Are you sure about this behavior? You mean you see "b" has the string size as 2. I haven't understand how this can happen.

But if the macro is used several times:
===
#define BACKSLASH "\\"
const char a[] = BACKSLASH;
const char b[] = BACKSLASH;
const char c[] = "<" BACKSLASH ">";
===

the, we get:
===
symbol a:

Quoted 6 lines

        char const [addressable] [toplevel] a[0]
        bit_size = 16
        val = "\0"

symbol b:
char const [addressable] [toplevel] b[0]
bit_size = 16

The value buffer is corrupted. But the bit_size is still 16, which is correct. I just think that in your example it shouldn't corrupt the size. Your test case seems confirm that.

Quoted 1 line

Is it only with macros that the string structure is so shared?

That is right. I haven't see it can happen any other way. The tokenizer always construct new token and string structure from the C source file.

It is the preprocessor using macro expand which copy and duplicate the token list. The token has a pointer point to the string which is shared across different invocation of macro.

Quoted 1 line

And have we a way to test if the string is coming from a macro?

Not right now. But we can add it.

Quoted 5 lines

A simpler and safer way would be to directly do the string expansion just after a string token is recognized, or even better in the lexer itself.
So the string buffer, macro or not, will always directly contain the right values. But maybe there was good reasons to not do it this way.

I have an counter example that will not work. Let say

#define b(a, d) a##d
wchar_t s[] = b(L, "\xabcdabc");

When the lexer process the escape char, you did not know the string is wide char or not. That can be changed after the macro expansion.

Chris

KERN_DEBUG "%s: Reset: current Rx mode %d.\n"

KERN_DEBUG ultimately expands to "\001" "7". When I print the corresponding ->string->data, I get

^A6%s7%s: Reset: current Rx mode %d.

The purpose of show_data() is to visualize data, more or less

Quoted 1 line · Luc Van Oostenryck

The purpose of show_data() is to visualize data, more or less

I think show_data() is a bad name. Data is very generic term, it has not specific meaning what exactly is that data.

What you really want to show is the initializer expression. Make the function name reflect that.

linearize.c

Quoted 1 line

linearize.c +0 -0

Why is this function belongs to linearize.c?
It has nothing to do with linearization instruction. It has every thing to do with the AST structure.

I suggest that move this code to show-parse.c. There are many functions showing internal of the AST there.