| Message ID | 20090202073018.GB28946@ZenIV.linux.org.uk (mailing list archive) |
|---|---|
| State | Mainlined, archived |
| Headers | show |
On Sun, Feb 1, 2009 at 11:30 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > There are several interesting problems caused by the fact that > we create a separate symbol for each declaration of given function. Thanks for the patch. That is great. This is actually one of the two hard problem in sparse. I haven't able to solved them. (BTW, the other one was running out of modifier bits.) You patch seems base on Josh's tree. In my tree the context change has been back out, so the validation/context-named.c is gone. Other than that, the patch seems apply fine. I will take a closer look at it and get back to you. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Feb 02, 2009 at 12:17:06PM -0800, Christopher Li wrote: > On Sun, Feb 1, 2009 at 11:30 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > > There are several interesting problems caused by the fact that > > we create a separate symbol for each declaration of given function. > > Thanks for the patch. That is great. This is actually one of the two > hard problem in > sparse. I haven't able to solved them. (BTW, the other one was running > out of modifier bits.) Modifier bits are going to get easier - I have a patch series that takes a bunch out (basically, to hell with everything in MOD_SPECIFIER - the only hard part is on the parser side and I've got a saner way to deal with that). -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Feb 2, 2009 at 12:58 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > Modifier bits are going to get easier - I have a patch series that > takes a bunch out (basically, to hell with everything in MOD_SPECIFIER - > the only hard part is on the parser side and I've got a saner way to > deal with that). That sounds like an interesting patch. Cared to shared it? Even it is not quite ready, I would like to take a look and maybe I can learn some thing. I want to store more than a few bits attribute information. So I was hacking a patch to make an separate structure for extended attributes. Only the symbol that use those extended attribute will have it. The address space and context will move to the extend attributes as well. Most of the symbol don't have special attribute, so it will save up some space overall. Does it sound like some thing sane to do? Any way, I haven't able to get it to work. The big messy part is when sparse propagate those attributes, some times it need to keep a separate copy of the extended attributes, because this extended attribute is option for symbols. Maybe I should try it again. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Sun, Feb 1, 2009 at 11:30 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > Anyway, proposed patch for (1) follows: I read the patch, seems reasonable. It is only solve the inline case though. The more generic problem still exist, symbol look up between partial prototype declare and the real declare will get symbol with partial information. It would be great if we can apply the definition to the first symbol. But I can haven't find a clean way to do it yet. Most likely I will apply your patch until we find a better way to do it. > @@ -2282,6 +2295,7 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis > } > } > } else if (base_type && base_type->type == SYM_FN) { > + if (decl->next_id && decl->next_id->scope == decl->scope) Not sure what this is trying to do. Shouldn't the next line to be indented if I read it correctly? Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Feb 02, 2009 at 07:07:24PM -0800, Christopher Li wrote: > On Sun, Feb 1, 2009 at 11:30 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > > Anyway, proposed patch for (1) follows: > > I read the patch, seems reasonable. It is only solve the inline case though. > The more generic problem still exist, symbol look up between partial > prototype declare and the real declare will get symbol with partial > information. ... and unfortunately, that's what we _have_ to do. Reason: behaviour of typeof(). Example: extern int a[]; int a[__builtin_types_compatible_p(typeof(a),int [3]) + 3]; /* 4 */ int b[__builtin_types_compatible_p(typeof(a),int [3]) + 3]; /* 3 */ Similar for extern int a[]; /* a is int [] */ typedef typeof(a) A; /* A is int [] _AND_ _WILL_ _REMAIN_ _SO_ */ int a[10]; /* a is int [10] now */ A b; /* int [] */ int b[1]; /* no problem */ Similar applies for functions getting pointers to functions, etc. - having the type refined by subsequent declaration is not retroactive. Mind you, we are not doing composite types in any useful way and _that_ is where we ought to change things. Subsequent declarations should pick the additional type information; we do propagate the inline definition back to the call sites, provided that we had the function declared inline before those. However, the type information should _not_ be spread back. And it's not just due to typeof (I suspect that honest attempt to define its semantics in presense of back-propagation like that will end up to be Turing-complete, but even if it is decidable it's prohibitively hard). Note that we do have similar effects in standard C - e.g. extern int a[]; void f(void) { extern int a[24]; memset(a, 0, sizeof(a)); /* OK */ } void g(void) { memset(a, 0, sizeof(a)); /* error - sizeof(a) is hidden from us here */ } doesn't involve any extensions and having it barf on the second memset call there is certainly intended behaviour. -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Feb 02, 2009 at 07:07:24PM -0800, Christopher Li wrote: > > } else if (base_type && base_type->type == SYM_FN) { > > + if (decl->next_id && decl->next_id->scope == decl->scope) > > Not sure what this is trying to do. Shouldn't the next line to be indented > if I read it correctly? Yuck. That's a leftover that hadn't been caught since it affects only K&R definitions. Kill that line... ObDeclarationParsing: I'm sorely (_very_ sorely) tempted to claim that gcc folks are violating GPL. Proof: gcc/c-parse.in, around productions for declspecs_*. Of course, they can say that this _is_ the preferred form for making modifications, but having such admission made in public would be worth it... Trying to sort out the __attribute__ handling in there just plain hurts ;-/ -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello, * Al Viro wrote on Tue, Feb 03, 2009 at 05:41:56AM CET: > ObDeclarationParsing: I'm sorely (_very_ sorely) tempted to claim that > gcc folks are violating GPL. Proof: gcc/c-parse.in, around productions > for declspecs_*. Of course, they can say that this _is_ the preferred > form for making modifications, [...] FWIW, that has since been rewritten. Quoting gcc/ChangeLog-2005: | 2005-02-25 Joseph S. Myers <joseph@codesourcery.com> | | * c-parser.c: New file. | * c-parse.in: Remove. [...] Cheers, Ralf -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Mon, Feb 2, 2009 at 8:13 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: >> I read the patch, seems reasonable. It is only solve the inline case though. >> The more generic problem still exist, symbol look up between partial >> prototype declare and the real declare will get symbol with partial >> information. > > ... and unfortunately, that's what we _have_ to do. Reason: behaviour > of typeof(). Example: > > extern int a[]; > int a[__builtin_types_compatible_p(typeof(a),int [3]) + 3]; /* 4 */ > int b[__builtin_types_compatible_p(typeof(a),int [3]) + 3]; /* 3 */ > > Similar for > extern int a[]; /* a is int [] */ > typedef typeof(a) A; /* A is int [] _AND_ _WILL_ _REMAIN_ _SO_ */ > int a[10]; /* a is int [10] now */ > A b; /* int [] */ > int b[1]; /* no problem */ > > Similar applies for functions getting pointers to functions, etc. - having > the type refined by subsequent declaration is not retroactive. I see. So the subsequent declaration for the same symbol should inherent previous declaration attributes, but no the other way around. > Mind you, we are not doing composite types in any useful way and _that_ is > where we ought to change things. Subsequent declarations should pick > the additional type information; we do propagate the inline definition > back to the call sites, provided that we had the function declared inline > before those. However, the type information should _not_ be spread back. Right. I think currently sparse treat the subsequent declaration like a new one. It check the type is compatible with previous declaration. But it does not merge the previous declaration information. > doesn't involve any extensions and having it barf on the second memset call > there is certainly intended behaviour. That is good to know. I will keep that in mind. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Christopher, > Right. I think currently sparse treat the subsequent declaration like a new > one. It check the type is compatible with previous declaration. But it does > not merge the previous declaration information. Sparse needs to generate composite types: http://c0x.coding-guidelines.com/6.2.7.html
On Mon, Feb 2, 2009 at 8:41 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > Yuck. That's a leftover that hadn't been caught since it affects only > K&R definitions. Kill that line... Apply and pushed. Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Feb 05, 2009 at 06:47:17PM +0000, Derek M Jones wrote: > Christopher, > >> Right. I think currently sparse treat the subsequent declaration like a new >> one. It check the type is compatible with previous declaration. But it does >> not merge the previous declaration information. > > Sparse needs to generate composite types: > http://c0x.coding-guidelines.com/6.2.7.html Of course it does need that (and it's not C0X news, obviously). We still have the type handling messed up in a lot of areas, so the plan is to sort out the declaration parsing, then get rid of the warts in type representation and handling, then deal with composites. IMO the right way to look at that crap is: * any declaration gives a new struct symbol, with type being the composite of that given by declaration and that of previously seen one (which, in turn, has gathered all earlier stuff) * type nodes should be treated as expressions, with on-demand evaluation and referential transparency (i.e. any rewrite replaces with equal). We are not that far from such state. * composite type is built by unifying two trees, with evaluation driven by comparisons. * we should _NOT_ do update-in-place from e.g. int[] to int[3] - it's guaranteed to mess e.g. typedef handling, not to mention making the VLA implementation hard as hell. We are not referentially transparent for e.g. struct expression and we'd paid a _lot_ for that. Note that even check for type compatibility is fscked up for function types - as it is, we treat void() and void(int) as incompatible types. So yes, the composite type handling is certainly needed. We also have deeply fscked treatment of declarations, mostly thanks to fallout from trying to be compatible with gcc in attribute handling ;-/ BTW, typedef treatment in declarators is also b0rken: witness sparse barfing on typedef int T; extern void f(int); void g(int x) { int (T); T = x; f(T); } which is a valid C (we have T redeclared in the function scope as int, with declarator -> direct-declarator -> ( declarator ) -> ( identifier ) as derivation). sparse mistakes int (T) for typename, does *NOT* notice that typename has no business whatsoever being there and silently proceeds to T = ..., without having redeclared T as object of type int. It sees typedef-name <something>, decides that it's a beginning of external-definition and vomits on the following =. IOW, the rule in direct_declarator() for distinguishing between function and non-function is broken... -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Feb 05, 2009 at 08:28:11PM +0000, Al Viro wrote: > typedef int T; > extern void f(int); > void g(int x) > { > int (T); > T = x; > f(T); > } > > which is a valid C (we have T redeclared in the function scope as int, > with declarator -> direct-declarator -> ( declarator ) -> ( identifier ) > as derivation). sparse mistakes int (T) for typename, does *NOT* notice > that typename has no business whatsoever being there and silently proceeds > to T = ..., without having redeclared T as object of type int. It sees > typedef-name <something>, decides that it's a beginning of external-definition > and vomits on the following =. > > IOW, the rule in direct_declarator() for distinguishing between function > and non-function is broken... PS: note that C grammar has an ambiguity, resolved in constraints (6.7.5.3p11). We have 3 different cases: * typename * normal declaration * parameter declaration In the first case, int (T) is "function that takes T and returns int"; we can have no identifiers in nested abstract-declarator, so there's no problem. In the second case, int (T) is "declare X as object of type int"; we can't have parameter-type-list or identifier-list without having seen an identifier. Again, no problem. In the third case, though, we can have both parameter-declaration -> declaration-specifiers declarator and parameter-declaration -> declaration-specifiers abstract-declarator with the former going through direct-declarator -> ( declarator ) -> ( identifier ) and the latter - direct-abstract-declarator -> direct-abstract-declarator? ( parameter-type-list) -> ( parameter-type-list ) -> ( identifier ) It is resolved by "an identifier that can be interpreted either as a typedef name or as a parameter name shall be taken as a typedef name". IOW, direct_declarator() (which doubles for direct-abstract-declarator) should have more than one-bit indication of which case we've got. Right now it's done by "have we passed a non-NULL ident ** to store the identifier being declared"; that's not enough. What we need is explicit 'is that a part of parameter declaration' flag; then the rule turns into if (p && *p) fn = 1; /* we'd seen identifier already, can't be nested */ else if match_op(next, ')') fn = 1; /* empty list can't be direct-declarator or * direct-abstract-declarator */ else fn = (in_parameter && lookup_type(next)); We also need to barf on lack of identifier in definition, unless it has no storage class specifiers and the type has been struct/union/enum, straight from the input - not a typedef or typeof resolving to such, but that's a separate story. -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Feb 5, 2009 at 12:28 PM, Al Viro <viro@zeniv.linux.org.uk> wrote: > > Of course it does need that (and it's not C0X news, obviously). We still > have the type handling messed up in a lot of areas, so the plan is to > sort out the declaration parsing, then get rid of the warts in type > representation and handling, then deal with composites. > > IMO the right way to look at that crap is: > * any declaration gives a new struct symbol, with type being the > composite of that given by declaration and that of previously seen one > (which, in turn, has gathered all earlier stuff) > * type nodes should be treated as expressions, with on-demand > evaluation and referential transparency (i.e. any rewrite replaces with > equal). We are not that far from such state. Can you elaborate the referential transparency? I currently have a vague idea of what you are trying to do. Where should I start if I am going to turn the idea into code. Should we delay the detail of type information until evaluate stage? Chris -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
On Thu, Feb 05, 2009 at 02:41:00PM -0800, Christopher Li wrote: > Can you elaborate the referential transparency? I currently have a vague > idea of what you are trying to do. Where should I start if I am going > to turn the idea into code. Should we delay the detail of type > information until evaluate stage? Basically, "replace equal with equal". I.e. whatever we do with struct symbol that might be visible to somebody, we should not change the interpretation of type for *any* struct symbol, including ones that might refer to that one. Take a look at uninlining for a nice example of the fallout you get when that property doesn't hold. We cannibalize struct expression during evaluation a _lot_, so we have to be bloody careful about what we share and what we must copy. For struct expression we do that in a lot of places and it's probably worth to keep doing due to memory footprint concerns. For types we can avoid that. As for the laziness - yes, that's what classify_type() et.al. is about. We want to do exactly as little as possible; basically, *all* type node evaluation (aka examining) should be demand-driven. It mostly holds, but we definitely could be lazier, e.g. in qualifier-related stuff. I'll do a more complete braindump (ideally - along with the declaration-parsing patchset, so that this work could really start) once I dig myself from under the !@#!@#!@# patch and mail piles elsewhere a bit. Al, terminally annoyed by the size of backlog ;-/ -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
diff --git a/evaluate.c b/evaluate.c index f976645..5ed31a9 100644 --- a/evaluate.c +++ b/evaluate.c @@ -2747,6 +2747,10 @@ static int evaluate_symbol_call(struct expression *expr) if (ctype->ctype.modifiers & MOD_INLINE) { int ret; struct symbol *curr = current_fn; + + if (ctype->definition) + ctype = ctype->definition; + current_fn = ctype->ctype.base_type; ret = inline_function(expr, ctype); @@ -3052,6 +3056,9 @@ static struct symbol *evaluate_symbol(struct symbol *sym) if (base_type->type == SYM_FN) { struct symbol *curr = current_fn; + if (sym->definition && sym->definition != sym) + return evaluate_symbol(sym->definition); + current_fn = base_type; examine_fn_arguments(base_type); diff --git a/parse.c b/parse.c index eb31871..3cdcf63 100644 --- a/parse.c +++ b/parse.c @@ -2105,6 +2105,7 @@ static struct token *parse_function_body(struct token *token, struct symbol *dec struct symbol_list **old_symbol_list; struct symbol *base_type = decl->ctype.base_type; struct statement *stmt, **p; + struct symbol *prev; struct symbol *arg; old_symbol_list = function_symbol_list; @@ -2138,6 +2139,18 @@ static struct token *parse_function_body(struct token *token, struct symbol *dec if (!(decl->ctype.modifiers & MOD_INLINE)) add_symbol(list, decl); check_declaration(decl); + decl->definition = decl; + prev = decl->same_symbol; + if (prev && prev->definition) { + warning(decl->pos, "multiple definitions for function '%s'", + show_ident(decl->ident)); + info(prev->definition->pos, " the previous one is here"); + } else { + while (prev) { + prev->definition = decl; + prev = prev->same_symbol; + } + } function_symbol_list = old_symbol_list; if (function_computed_goto_list) { if (!function_computed_target_list) @@ -2282,6 +2295,7 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis } } } else if (base_type && base_type->type == SYM_FN) { + if (decl->next_id && decl->next_id->scope == decl->scope) /* K&R argument declaration? */ if (lookup_type(token)) return parse_k_r_arguments(token, decl, list); @@ -2309,6 +2323,8 @@ struct token *external_declaration(struct token *token, struct symbol_list **lis } } check_declaration(decl); + if (decl->same_symbol) + decl->definition = decl->same_symbol->definition; if (!match_op(token, ',')) break; diff --git a/symbol.h b/symbol.h index c4d7f28..e5369d2 100644 --- a/symbol.h +++ b/symbol.h @@ -155,6 +155,7 @@ struct symbol { struct expression *initializer; struct entrypoint *ep; long long value; /* Initial value */ + struct symbol *definition; }; }; union /* backend */ { diff --git a/validation/context-named.c b/validation/context-named.c index 58310e9..a896621 100644 --- a/validation/context-named.c +++ b/validation/context-named.c @@ -501,6 +501,8 @@ static void good_mixed_with_if(void) * check-name: Check -Wcontext with lock names * * check-error-start +context-named.c:417:13: warning: multiple definitions for function 'good_fn2' +context-named.c:408:13: the previous one is here context-named.c:86:3: warning: context imbalance in 'warn_lock1': wrong count at exit context-named.c:86:3: context 'TEST': wanted 0, got 1 context-named.c:93:3: warning: context imbalance in 'warn_lock2': wrong count at exit diff --git a/validation/definitions.c b/validation/definitions.c new file mode 100644 index 0000000..fce7393 --- /dev/null +++ b/validation/definitions.c @@ -0,0 +1,12 @@ +static inline int f(void); +static int g(void) +{ + return f(); +} +static inline int f(void) +{ + return 0; +} +/* + * check-name: finding definitions + */
There are several interesting problems caused by the fact that we create a separate symbol for each declaration of given function. 1) static inline int f(void); static int g(void) { return f(); } static inline int f(void) { return 0; } gives an error, since the instance of f in g is not associated with anything useful. Needless to say, this is a perfectly valid C. Moreover, static inline int f(void) { return 0; } static inline int f(void); static int g(void) { return f(); } will step on the same thing. Currently we get the former case all over the place in the kernel, thanks to the way DEFINE_SYSCALLx() is done. I have a kinda-sorta fix for that (basically, add a reference to external definition to struct symbol and update it correctly - it's not hard). However, that doesn't cover *another* weirdness in the same area - gccisms around extern inline. There we can have inline and external definitions in the same translation unit (and they can be different, to make the things even more interesting). Anyway, that's a separate story - as it is, we don't even have a way to tell 'extern inline ...' from 'inline ...' 2) More fun in the same area: checks for SYM_FN in external_declaration() do not take into account the possibility of void f(int); typeof(f) g; Ergo, we get linkage-less function declarations. Fun, innit? No patch. 3) Better yet, sparse does _NOT_ reject typeof(f) g { ... } which is obviously a Bloody Bad Idea(tm) (just think what that does to argument list). Similar crap is triggerable with typedef. IMO, we really ought to reject _that_ - not only 6.9.1(2) explicitly requires that, but there's no even remotely sane way to deal with arguments. 4) static void f(void); ... void f(void); triggers "warning: symbol 'f' was not declared. Should it be static?" which is at least very confusing - it *is* declared and it *is* static. IOW, we do not collect the linkage information sanely. (2) will make fixing that one very interesting. Anyway, proposed patch for (1) follows: Subject: [PATCH] Handle mix of declarations and definitions Signed-off-by: Al Viro <viro@zeniv.linux.org.uk> --- evaluate.c | 7 +++++++ parse.c | 16 ++++++++++++++++ symbol.h | 1 + validation/context-named.c | 2 ++ validation/definitions.c | 12 ++++++++++++ 5 files changed, 38 insertions(+), 0 deletions(-) create mode 100644 validation/definitions.c