Bogus sparse warning?

Bogus sparse warning?

[Anton Altaparmakov]

Hi,

Using latest code from git://git.kernel.org/pub/scm/linux/kernel/git/ 
josh/sparse.git

When I run:  make CHECKFLAGS="-D__CHECK_ENDIAN__" C=2 modules

I get this warning:

   CHECK   fs/ntfs/file.c
fs/ntfs/file.c:2241:5: warning: incorrect type in argument 8  
(different signedness)
fs/ntfs/file.c:2241:5:    expected int [signed] ( [signed] [usertype]  
get_block )( ... )
fs/ntfs/file.c:2241:5:    got int [signed] ( static [toplevel]  
*<noident> )( ... )

The relevant code to reproduce this is:

 From <include/linux/fs.h>:

typedef int (get_block_t)(struct inode *inode, sector_t iblock,
                         struct buffer_head *bh_result, int create);

static inline ssize_t blockdev_direct_IO(int rw, struct kiocb *iocb,
         struct inode *inode, struct block_device *bdev, const struct  
iovec *iov,
         loff_t offset, unsigned long nr_segs, get_block_t get_block,
         dio_iodone_t end_io)
{
}

In my current <fs/ntfs/file.c>:

static int ntfs_get_block_for_direct_IO_write(struct inode *vi,  
sector_t blk,
                 struct buffer_head *bh, int create)
{
}

And later (this is line 2240 from the error message):

                 written = blockdev_direct_IO(WRITE, iocb, vi, vi- 
 >i_sb->s_bdev,
                                 iov, pos, *nr_segs,
                                 ntfs_get_block_for_direct_IO_write,  
NULL);

Why is sparse complaining?  And perhaps more importantly how do I  
make the warning go away?

Thanks a lot in advance!

Best regards,

	Anton
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/

Re: Bogus sparse warning?

[Linus Torvalds]

On Mon, 12 Feb 2007, Anton Altaparmakov wrote:
> 
> Using latest code from
> git://git.kernel.org/pub/scm/linux/kernel/git/josh/sparse.git
> 
> When I run:  make CHECKFLAGS="-D__CHECK_ENDIAN__" C=2 modules
> 
> I get this warning:
> 
>  CHECK   fs/ntfs/file.c
> fs/ntfs/file.c:2241:5: warning: incorrect type in argument 8 (different
> signedness)
> fs/ntfs/file.c:2241:5:    expected int [signed] ( [signed] [usertype] get_block )( ... )
> fs/ntfs/file.c:2241:5:    got int [signed] ( static [toplevel] *<noident> )( ... )

Ok, that does seem like a sparse bug. I _think_ that the trigger here is 
the fact that we make "get_block_t" be the *function* type, rather than a 
"pointer to function" type, and then we screw up somewhere when we do the 
don't do the implicit pointer conversion, and we also thus don't move the 
type attributes around properly (notice how "get_block" is marked as being 
a "signed usertype", _not_ a pointer).

So we should really have converted the function type in the declaration to 
a "pointer to function", but since this is such an unusual thing to have, 
nobody noticed.

Does the warning go away if you make "get_block_t" explicitly a pointer to 
a function, ie you add the "*" to the typedef:

> From <include/linux/fs.h>:
> 
> typedef int (get_block_t)(struct inode *inode, sector_t iblock,
>                        struct buffer_head *bh_result, int create);

so that it looks like

	typedef int (*get_block_t)(...)

instead?

(It is perfectly proper to have a typedef that is actually of a function 
type, so this looks like a sparse bug regardless, it looks just as if we 
don't turn a function type into a function pointer type when we see it as 
an argument in the declaration).

Has this been there for a long time, or was it something recent in sparse 
that seemed to trigger it (like the recent ctype conversion changes due to 
attribute parsing?)

			Linus

Re: Bogus sparse warning?

[Christopher Li]

On Mon, Feb 12, 2007 at 10:28:19AM -0800, Linus Torvalds wrote:
> 
> 
> > From <include/linux/fs.h>:
> > 
> > typedef int (get_block_t)(struct inode *inode, sector_t iblock,
> >                        struct buffer_head *bh_result, int create);
> 
> so that it looks like
> 
> 	typedef int (*get_block_t)(...)
> 
> instead?
> 
> (It is perfectly proper to have a typedef that is actually of a function 
> type, so this looks like a sparse bug regardless, it looks just as if we 
> don't turn a function type into a function pointer type when we see it as 
> an argument in the declaration).

Yes, we does, in examine_fn_arguments(). But not correctly inherent the attribute bits.

> 
> Has this been there for a long time, or was it something recent in sparse 
> that seemed to trigger it (like the recent ctype conversion changes due to 
> attribute parsing?)

I think this patch should fix it, I haven't try it myself on this bug yet.
It works on a different test case "function vs function ptr".
It has been posted to the list before. It is in my series as well.

Chris

Index: sparse/symbol.h
===================================================================
--- sparse.orig/symbol.h	2007-02-04 23:46:07.000000000 -0800
+++ sparse/symbol.h	2007-02-05 12:18:30.000000000 -0800
@@ -191,6 +191,7 @@ struct symbol {
 #define MOD_SIZE	(MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG)
 #define MOD_IGNORE (MOD_TOPLEVEL | MOD_STORAGE | MOD_ADDRESSABLE |	\
 	MOD_ASSIGNED | MOD_USERTYPE | MOD_FORCE | MOD_ACCESSED | MOD_EXPLICITLY_SIGNED)
+#define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_NODEREF | MOD_STORAGE)
 
 
 /* Current parsing/evaluation function */
Index: sparse/evaluate.c
===================================================================
--- sparse.orig/evaluate.c	2007-02-04 00:47:46.000000000 -0800
+++ sparse/evaluate.c	2007-02-05 12:20:08.000000000 -0800
@@ -1282,7 +1282,7 @@ static void examine_fn_arguments(struct 
 				else
 					ptr->ctype.base_type = arg;
 				ptr->ctype.as |= s->ctype.as;
-				ptr->ctype.modifiers |= s->ctype.modifiers;
+				ptr->ctype.modifiers |= s->ctype.modifiers & MOD_PTRINHERIT;
 
 				s->ctype.base_type = ptr;
 				s->ctype.as = 0;
@@ -1313,8 +1313,6 @@ static struct symbol *convert_to_as_mod(
 	return sym;
 }
 
-#define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_NODEREF | MOD_STORAGE)
-
 static struct symbol *create_pointer(struct expression *expr, struct symbol *sym, int degenerate)
 {
 	struct symbol *node = alloc_symbol(expr->pos, SYM_NODE);

Re: Bogus sparse warning?

[Linus Torvalds]

On Mon, 12 Feb 2007, Christopher Li wrote:
>
> On Mon, Feb 12, 2007 at 10:28:19AM -0800, Linus Torvalds wrote:
> >
> > (It is perfectly proper to have a typedef that is actually of a function 
> > type, so this looks like a sparse bug regardless, it looks just as if we 
> > don't turn a function type into a function pointer type when we see it as 
> > an argument in the declaration).
> 
> Yes, we does, in examine_fn_arguments(). But not correctly inherent the attribute bits.

Ahh. 

> I think this patch should fix it, I haven't try it myself on this bug yet.
> It works on a different test case "function vs function ptr".
> It has been posted to the list before. It is in my series as well.

This looks good. Ack.  Josh?

The only thing that I reacted to is that maybe we should change the

	s->ctype.modifiers = 0;

a few lines down into a

	s->ctype.modifiers &= ~MOD_PTRINHERIT;

or something? Although the normal "create_pointer()" function just leaves 
it entirely alone. So I don't know what the correct thing to do is. I 
wonder why I did that in the first place (that code is _old_).

		Linus

Re: Bogus sparse warning?

[Josh Triplett]

[-- Attachment #1: Type: text/plain, Size: 1159 bytes --]

Linus Torvalds wrote:
> On Mon, 12 Feb 2007, Christopher Li wrote:
>> On Mon, Feb 12, 2007 at 10:28:19AM -0800, Linus Torvalds wrote:
>>> (It is perfectly proper to have a typedef that is actually of a function 
>>> type, so this looks like a sparse bug regardless, it looks just as if we 
>>> don't turn a function type into a function pointer type when we see it as 
>>> an argument in the declaration).
>> Yes, we does, in examine_fn_arguments(). But not correctly inherent the attribute bits.
> 
> Ahh. 
> 
>> I think this patch should fix it, I haven't try it myself on this bug yet.
>> It works on a different test case "function vs function ptr".
>> It has been posted to the list before. It is in my series as well.
> 
> This looks good. Ack.  Josh?

See my response to Christopher later in the thread; his revised patch appears
to solve the problem fully.

> The only thing that I reacted to is that maybe we should change the
> 
> 	s->ctype.modifiers = 0;
> 
> a few lines down into a
> 
> 	s->ctype.modifiers &= ~MOD_PTRINHERIT;
> 
> or something?

Christopher's revised patch does exactly that.

- Josh Triplett


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: Bogus sparse warning?

[Anton Altaparmakov]

Hi,

On Mon, 12 Feb 2007, Christopher Li wrote:
> On Mon, Feb 12, 2007 at 10:28:19AM -0800, Linus Torvalds wrote:
> > 
> > 
> > > From <include/linux/fs.h>:
> > > 
> > > typedef int (get_block_t)(struct inode *inode, sector_t iblock,
> > >                        struct buffer_head *bh_result, int create);
> > 
> > so that it looks like
> > 
> > 	typedef int (*get_block_t)(...)
> > 
> > instead?
> > 
> > (It is perfectly proper to have a typedef that is actually of a function 
> > type, so this looks like a sparse bug regardless, it looks just as if we 
> > don't turn a function type into a function pointer type when we see it as 
> > an argument in the declaration).
> 
> Yes, we does, in examine_fn_arguments(). But not correctly inherent the attribute bits.
> 
> > 
> > Has this been there for a long time, or was it something recent in sparse 
> > that seemed to trigger it (like the recent ctype conversion changes due to 
> > attribute parsing?)
> 
> I think this patch should fix it, I haven't try it myself on this bug yet.
> It works on a different test case "function vs function ptr".
> It has been posted to the list before. It is in my series as well.

I applied this patch to the current spares git code and reran my test and 
now we have two warnings:

  CHECK   fs/ntfs/file.c
fs/ntfs/file.c:2241:5: warning: incorrect type in argument 8 (different 
signedness)
fs/ntfs/file.c:2241:5:    expected int [signed] ( [signed] [usertype] 
get_block )( ... )
fs/ntfs/file.c:2241:5:    got int [signed] ( static [toplevel] *<noident> 
)( ... )
include/linux/fs.h:1791:14: warning: incorrect type in argument 8 
(different signedness)
include/linux/fs.h:1791:14:    expected int [signed] ( [signed] [usertype] 
get_block )( ... )
include/linux/fs.h:1791:14:    got int [signed] ( *get_block )( ... )

Best regards,

	Anton

> 
> Chris
> 
> Index: sparse/symbol.h
> ===================================================================
> --- sparse.orig/symbol.h	2007-02-04 23:46:07.000000000 -0800
> +++ sparse/symbol.h	2007-02-05 12:18:30.000000000 -0800
> @@ -191,6 +191,7 @@ struct symbol {
>  #define MOD_SIZE	(MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG)
>  #define MOD_IGNORE (MOD_TOPLEVEL | MOD_STORAGE | MOD_ADDRESSABLE |	\
>  	MOD_ASSIGNED | MOD_USERTYPE | MOD_FORCE | MOD_ACCESSED | MOD_EXPLICITLY_SIGNED)
> +#define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_NODEREF | MOD_STORAGE)
>  
>  
>  /* Current parsing/evaluation function */
> Index: sparse/evaluate.c
> ===================================================================
> --- sparse.orig/evaluate.c	2007-02-04 00:47:46.000000000 -0800
> +++ sparse/evaluate.c	2007-02-05 12:20:08.000000000 -0800
> @@ -1282,7 +1282,7 @@ static void examine_fn_arguments(struct 
>  				else
>  					ptr->ctype.base_type = arg;
>  				ptr->ctype.as |= s->ctype.as;
> -				ptr->ctype.modifiers |= s->ctype.modifiers;
> +				ptr->ctype.modifiers |= s->ctype.modifiers & MOD_PTRINHERIT;
>  
>  				s->ctype.base_type = ptr;
>  				s->ctype.as = 0;
> @@ -1313,8 +1313,6 @@ static struct symbol *convert_to_as_mod(
>  	return sym;
>  }
>  
> -#define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_NODEREF | MOD_STORAGE)
> -
>  static struct symbol *create_pointer(struct expression *expr, struct symbol *sym, int degenerate)
>  {
>  	struct symbol *node = alloc_symbol(expr->pos, SYM_NODE);
> 
> 

-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/

Re: Bogus sparse warning?

[Christopher Li]

On Tue, Feb 13, 2007 at 12:15:56AM +0000, Anton Altaparmakov wrote:
> 
> I applied this patch to the current spares git code and reran my test and 
> now we have two warnings:
> 
>   CHECK   fs/ntfs/file.c
> fs/ntfs/file.c:2241:5: warning: incorrect type in argument 8 (different 
> signedness)
> fs/ntfs/file.c:2241:5:    expected int [signed] ( [signed] [usertype] 
> get_block )( ... )
> fs/ntfs/file.c:2241:5:    got int [signed] ( static [toplevel] *<noident> 
> )( ... )
> include/linux/fs.h:1791:14: warning: incorrect type in argument 8 
> (different signedness)
> include/linux/fs.h:1791:14:    expected int [signed] ( [signed] [usertype] 
> get_block )( ... )
> include/linux/fs.h:1791:14:    got int [signed] ( *get_block )( ... )
> 
> Best regards,
>

I see. In evaluate_call().
evaluate_arguments() is called before target function arguments
are converted into pointers.

Can you please try this patch instead?

Chris

Index: sparse/symbol.h
===================================================================
--- sparse.orig/symbol.h	2007-02-12 18:10:01.000000000 -0800
+++ sparse/symbol.h	2007-02-12 18:10:06.000000000 -0800
@@ -191,6 +191,7 @@ struct symbol {
 #define MOD_SIZE	(MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG)
 #define MOD_IGNORE (MOD_TOPLEVEL | MOD_STORAGE | MOD_ADDRESSABLE |	\
 	MOD_ASSIGNED | MOD_USERTYPE | MOD_FORCE | MOD_ACCESSED | MOD_EXPLICITLY_SIGNED)
+#define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_NODEREF | MOD_STORAGE)
 
 
 /* Current parsing/evaluation function */
Index: sparse/evaluate.c
===================================================================
--- sparse.orig/evaluate.c	2007-02-12 18:10:01.000000000 -0800
+++ sparse/evaluate.c	2007-02-12 18:10:48.000000000 -0800
@@ -1282,11 +1282,11 @@ static void examine_fn_arguments(struct 
 				else
 					ptr->ctype.base_type = arg;
 				ptr->ctype.as |= s->ctype.as;
-				ptr->ctype.modifiers |= s->ctype.modifiers;
+				ptr->ctype.modifiers |= s->ctype.modifiers & MOD_PTRINHERIT;
 
 				s->ctype.base_type = ptr;
 				s->ctype.as = 0;
-				s->ctype.modifiers = 0;
+				s->ctype.modifiers &= ~MOD_PTRINHERIT;
 				s->bit_size = 0;
 				s->examined = 0;
 				examine_symbol_type(s);
@@ -1313,8 +1313,6 @@ static struct symbol *convert_to_as_mod(
 	return sym;
 }
 
-#define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_NODEREF | MOD_STORAGE)
-
 static struct symbol *create_pointer(struct expression *expr, struct symbol *sym, int degenerate)
 {
 	struct symbol *node = alloc_symbol(expr->pos, SYM_NODE);
@@ -2309,7 +2307,6 @@ static int evaluate_symbol_call(struct e
 		int ret;
 		struct symbol *curr = current_fn;
 		current_fn = ctype->ctype.base_type;
-		examine_fn_arguments(current_fn);
 
 		ret = inline_function(expr, ctype);
 
@@ -2336,6 +2333,7 @@ static struct symbol *evaluate_call(stru
 	if (ctype->type == SYM_PTR || ctype->type == SYM_ARRAY)
 		ctype = get_base_type(ctype);
 
+	examine_fn_arguments(ctype);
         if (sym->type == SYM_NODE && fn->type == EXPR_PREOP &&
 	    sym->op && sym->op->args) {
 		if (!sym->op->args(expr))

 

Re: Bogus sparse warning?

[Josh Triplett]

[-- Attachment #1: Type: text/plain, Size: 1571 bytes --]

Christopher Li wrote:
> On Tue, Feb 13, 2007 at 12:15:56AM +0000, Anton Altaparmakov wrote:
>> I applied this patch to the current spares git code and reran my test and 
>> now we have two warnings:
>>
>>   CHECK   fs/ntfs/file.c
>> fs/ntfs/file.c:2241:5: warning: incorrect type in argument 8 (different 
>> signedness)
>> fs/ntfs/file.c:2241:5:    expected int [signed] ( [signed] [usertype] 
>> get_block )( ... )
>> fs/ntfs/file.c:2241:5:    got int [signed] ( static [toplevel] *<noident> 
>> )( ... )
>> include/linux/fs.h:1791:14: warning: incorrect type in argument 8 
>> (different signedness)
>> include/linux/fs.h:1791:14:    expected int [signed] ( [signed] [usertype] 
>> get_block )( ... )
>> include/linux/fs.h:1791:14:    got int [signed] ( *get_block )( ... )
>>
>> Best regards,
>>
> 
> I see. In evaluate_call().
> evaluate_arguments() is called before target function arguments
> are converted into pointers.
> 
> Can you please try this patch instead?

Anton reported success with this revision of your patch, so I'd like to apply
it to the sparse tree; could you please supply a Signed-off-by so I can do so?

The same goes for several of the patches in your -cl2 tree, which I would
eagerly like to apply.  Your patches look quite excellent, and greatly advance
the capabilities of Sparse in directions I've wanted to see it progress in.
I'd prefer to pull your patches in as a block, to avoid inconveniencing you by
pulling them in piecemeal and forcing you to rebase the remaining patches.

- Josh Triplett


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: Bogus sparse warning?

[Josh Triplett]

[-- Attachment #1: Type: text/plain, Size: 1186 bytes --]

Christopher Li wrote:
> On Tue, Feb 13, 2007 at 12:22:44AM -0800, Josh Triplett wrote:
>> Anton reported success with this revision of your patch, so I'd like to apply
>> it to the sparse tree; could you please supply a Signed-off-by so I can do so?
> 
> Bug fix in pointer modifiers inherent at function degeneration.
> 
> In reply to Randy's email:
> 
> The following case cause warning about different signedness of pointer.
> The pointer should not have signedness at all.
> 
> struct sk_buff;
> struct sock;
> 
> extern int skb_append_datato_frags(struct sock *sk, struct sk_buff *skb,
> 			int getfrag(void *from, char *to, int offset,
> 			int len,int odd, struct sk_buff *skb),
> 			void *from, int length);
> 
> int skb_append_datato_frags(struct sock *sk, struct sk_buff *skb,
> 			int (*getfrag)(void *from, char *to, int offset,
> 			int len,int odd, struct sk_buff *skb),
> 			void *from, int length)
> 
> {
> 	return 0;
> }
> 
> Singed-Off-By: Christopher Li <sparse@chrisli.org>
> Acked-By: Linus Torvalds <torvalds@linux-foundation.org>

Applied.  I also added this test case to the validation directory.

Thanks.

- Josh Triplett


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]

Re: Bogus sparse warning?

[Anton Altaparmakov]

Hi,

On 13 Feb 2007, at 01:46, Christopher Li wrote:
> I see. In evaluate_call().
> evaluate_arguments() is called before target function arguments
> are converted into pointers.
>
> Can you please try this patch instead?

This one works!  (-:

I put it in and now it does not matter whether the linux/fs.h  
get_bloc_t typedef has the "*" or not, both times it does not give a  
warning at all:

   CHECK   fs/ntfs/file.c
   CC [M]  fs/ntfs/file.o

Best regards,

	Anton


>
> Chris
>
> Index: sparse/symbol.h
> ===================================================================
> --- sparse.orig/symbol.h	2007-02-12 18:10:01.000000000 -0800
> +++ sparse/symbol.h	2007-02-12 18:10:06.000000000 -0800
> @@ -191,6 +191,7 @@ struct symbol {
>  #define MOD_SIZE	(MOD_CHAR | MOD_SHORT | MOD_LONG | MOD_LONGLONG)
>  #define MOD_IGNORE (MOD_TOPLEVEL | MOD_STORAGE | MOD_ADDRESSABLE |	\
>  	MOD_ASSIGNED | MOD_USERTYPE | MOD_FORCE | MOD_ACCESSED |  
> MOD_EXPLICITLY_SIGNED)
> +#define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_NODEREF |  
> MOD_STORAGE)
>
>
>  /* Current parsing/evaluation function */
> Index: sparse/evaluate.c
> ===================================================================
> --- sparse.orig/evaluate.c	2007-02-12 18:10:01.000000000 -0800
> +++ sparse/evaluate.c	2007-02-12 18:10:48.000000000 -0800
> @@ -1282,11 +1282,11 @@ static void examine_fn_arguments(struct
>  				else
>  					ptr->ctype.base_type = arg;
>  				ptr->ctype.as |= s->ctype.as;
> -				ptr->ctype.modifiers |= s->ctype.modifiers;
> +				ptr->ctype.modifiers |= s->ctype.modifiers & MOD_PTRINHERIT;
>
>  				s->ctype.base_type = ptr;
>  				s->ctype.as = 0;
> -				s->ctype.modifiers = 0;
> +				s->ctype.modifiers &= ~MOD_PTRINHERIT;
>  				s->bit_size = 0;
>  				s->examined = 0;
>  				examine_symbol_type(s);
> @@ -1313,8 +1313,6 @@ static struct symbol *convert_to_as_mod(
>  	return sym;
>  }
>
> -#define MOD_PTRINHERIT (MOD_VOLATILE | MOD_CONST | MOD_NODEREF |  
> MOD_STORAGE)
> -
>  static struct symbol *create_pointer(struct expression *expr,  
> struct symbol *sym, int degenerate)
>  {
>  	struct symbol *node = alloc_symbol(expr->pos, SYM_NODE);
> @@ -2309,7 +2307,6 @@ static int evaluate_symbol_call(struct e
>  		int ret;
>  		struct symbol *curr = current_fn;
>  		current_fn = ctype->ctype.base_type;
> -		examine_fn_arguments(current_fn);
>
>  		ret = inline_function(expr, ctype);
>
> @@ -2336,6 +2333,7 @@ static struct symbol *evaluate_call(stru
>  	if (ctype->type == SYM_PTR || ctype->type == SYM_ARRAY)
>  		ctype = get_base_type(ctype);
>
> +	examine_fn_arguments(ctype);
>          if (sym->type == SYM_NODE && fn->type == EXPR_PREOP &&
>  	    sym->op && sym->op->args) {
>  		if (!sym->op->args(expr))
>
>

Best regards,

	Anton
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/

Re: Bogus sparse warning?

[Anton Altaparmakov]

On Mon, 12 Feb 2007, Linus Torvalds wrote:
> On Mon, 12 Feb 2007, Anton Altaparmakov wrote:
> > Using latest code from
> > git://git.kernel.org/pub/scm/linux/kernel/git/josh/sparse.git
> > 
> > When I run:  make CHECKFLAGS="-D__CHECK_ENDIAN__" C=2 modules
> > 
> > I get this warning:
> > 
> >  CHECK   fs/ntfs/file.c
> > fs/ntfs/file.c:2241:5: warning: incorrect type in argument 8 (different
> > signedness)
> > fs/ntfs/file.c:2241:5:    expected int [signed] ( [signed] [usertype] get_block )( ... )
> > fs/ntfs/file.c:2241:5:    got int [signed] ( static [toplevel] *<noident> )( ... )
> 
> Ok, that does seem like a sparse bug. I _think_ that the trigger here is 
> the fact that we make "get_block_t" be the *function* type, rather than a 
> "pointer to function" type, and then we screw up somewhere when we do the 
> don't do the implicit pointer conversion, and we also thus don't move the 
> type attributes around properly (notice how "get_block" is marked as being 
> a "signed usertype", _not_ a pointer).
> 
> So we should really have converted the function type in the declaration to 
> a "pointer to function", but since this is such an unusual thing to have, 
> nobody noticed.
> 
> Does the warning go away if you make "get_block_t" explicitly a pointer to 
> a function, ie you add the "*" to the typedef:
> 
> > From <include/linux/fs.h>:
> > 
> > typedef int (get_block_t)(struct inode *inode, sector_t iblock,
> >                        struct buffer_head *bh_result, int create);
> 
> so that it looks like
> 
> 	typedef int (*get_block_t)(...)
> 
> instead?

I have Christopher Li's patch applied and with that and changing to the 
(*get_block_t) in linux/fs.h it now produces no warnings:

  CHECK   fs/ntfs/file.c
  CC [M]  fs/ntfs/file.o

> (It is perfectly proper to have a typedef that is actually of a function 
> type, so this looks like a sparse bug regardless, it looks just as if we 
> don't turn a function type into a function pointer type when we see it as 
> an argument in the declaration).
> 
> Has this been there for a long time, or was it something recent in sparse 
> that seemed to trigger it (like the recent ctype conversion changes due to 
> attribute parsing?)

I am afraid I have no idea.  Until yesterday I used to run:

make CHECKFLAGS="-Wbitwise" C=2 modules

And also I kept pulling from your sparse repository and wondering why 
there have not been any changes in so long!  Only yesterday did I spot an 
actual endianness bug in NTFS which caused me to investigate why sparse 
was not picking it up and in the process I discovered that the sparse 
repository had moved and that "-Wbitwise" no longer was the correct 
option...  I then pulled the new sparse repository and changed from 
-Wbitwise to -D__CHECK_ENDIAN__ and then got tons of warnings that did not 
use to be there before.  I managed to fix all except the two I reported on 
the mailing list yesterday (and one more that I have not looked at yet - 
in fs/ntfs/runlist.c I get 18 warnings like this:
 
fs/ntfs/runlist.c:1549:18: warning: potentially expensive pointer subtraction

I have not had a chance to investigate what those mean yet)...

Best regards,

	Anton
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/

Re: Bogus sparse warning?

[Linus Torvalds]

On Tue, 13 Feb 2007, Anton Altaparmakov wrote:
> 
> I have Christopher Li's patch applied and with that and changing to the 
> (*get_block_t) in linux/fs.h it now produces no warnings:

I suspect that even without Chris' patch, you wouldn't get a warning with 
the explicit "pointer" conversion in <linux/fs.h>. But I didn't test.

> > Has this been there for a long time, or was it something recent in sparse 
> > that seemed to trigger it (like the recent ctype conversion changes due to 
> > attribute parsing?)
> 
> I am afraid I have no idea.  Until yesterday I used to run:
> 
> make CHECKFLAGS="-Wbitwise" C=2 modules
> 
> And also I kept pulling from your sparse repository and wondering why 
> there have not been any changes in so long!  Only yesterday did I spot an 
> actual endianness bug in NTFS which caused me to investigate why sparse 
> was not picking it up and in the process I discovered that the sparse 
> repository had moved and that "-Wbitwise" no longer was the correct 
> option...

Heh.

> I then pulled the new sparse repository and changed from -Wbitwise to 
> -D__CHECK_ENDIAN__ and then got tons of warnings that did not use to be 
> there before.  I managed to fix all except the two I reported on the 
> mailing list yesterday (and one more that I have not looked at yet - in 
> fs/ntfs/runlist.c I get 18 warnings like this:
>  
> fs/ntfs/runlist.c:1549:18: warning: potentially expensive pointer subtraction

Ok. That happens for code like

	struct some_struct *p, *q;
	int i;

	i = p - q;

because not everybody realizes that this simple subtraction can actually 
generate tons of instructions. It basically becomes

	i = ((unsigned long)p - (unsigned long)q) / sizeof(some_struct);

which is a potentially 64-bit divide with an awkward (but constant) 
divisor.

If the sizeof is a power-of-two, we don't care, because then it's 
obviously a normal shift. But depending on compiler and architecture and 
exact size of the struct, it can actually be tens of instructions and lots 
of cycles (gcc often tries to turn divisions by constants into a fancy 
code-sequence, which explains the "tens of instructions" part).

So the "potentially expensive" warning is not something really bad, but it 
can be a sign of "maybe you didn't realize that this can be quite 
expensive".

We had some code-sequences in the kernel where we could just rewrite the 
subtraction to something else entirely, and get rid of code.

		Linus

Re: Bogus sparse warning?

[Anton Altaparmakov]

On 13 Feb 2007, at 00:42, Linus Torvalds wrote:
> On Tue, 13 Feb 2007, Anton Altaparmakov wrote:
>> I have Christopher Li's patch applied and with that and changing  
>> to the
>> (*get_block_t) in linux/fs.h it now produces no warnings:
>
> I suspect that even without Chris' patch, you wouldn't get a  
> warning with
> the explicit "pointer" conversion in <linux/fs.h>. But I didn't test.

I did't either.  The good news is that Chris' second patch fixes the  
warning both with the explicit "pointer" conversion and without.

>> I then pulled the new sparse repository and changed from -Wbitwise to
>> -D__CHECK_ENDIAN__ and then got tons of warnings that did not use  
>> to be
>> there before.  I managed to fix all except the two I reported on the
>> mailing list yesterday (and one more that I have not looked at yet  
>> - in
>> fs/ntfs/runlist.c I get 18 warnings like this:
>>
>> fs/ntfs/runlist.c:1549:18: warning: potentially expensive pointer  
>> subtraction
>
> Ok. That happens for code like
>
> 	struct some_struct *p, *q;
> 	int i;
>
> 	i = p - q;
>
> because not everybody realizes that this simple subtraction can  
> actually
> generate tons of instructions. It basically becomes
>
> 	i = ((unsigned long)p - (unsigned long)q) / sizeof(some_struct);
>
> which is a potentially 64-bit divide with an awkward (but constant)
> divisor.
>
> If the sizeof is a power-of-two, we don't care, because then it's
> obviously a normal shift. But depending on compiler and  
> architecture and
> exact size of the struct, it can actually be tens of instructions  
> and lots
> of cycles (gcc often tries to turn divisions by constants into a fancy
> code-sequence, which explains the "tens of instructions" part).
>
> So the "potentially expensive" warning is not something really bad,  
> but it
> can be a sign of "maybe you didn't realize that this can be quite
> expensive".
>
> We had some code-sequences in the kernel where we could just  
> rewrite the
> subtraction to something else entirely, and get rid of code.

Yes you are quite right in what it is flagging up.  But I would have  
assumed that my current code is more efficient than alternatives.   
Here is the code from the first warning:

                 /* Determine the runlist size. */
                 trl = rl + 1;
                 while (likely(trl->length))
                         trl++;
                 old_size = trl - runlist->rl + 1;

Note "rl" and "trl" are "structs" of size 24 bytes (i.e. not a power  
of 2).  What we are dealing with here is an array of those "structs"  
which is terminated by a "struct" where its "->length" is zero.  And  
I do the above loop to get the size, i.e. I look for the last element  
and then subtract the first element from the last element and add one  
to get the number of elements in the array.

Is this not more efficient than say doing it using an index like so:

	for (old_size = 0; rl[old_size].length; old_size++)
		;
	old_size++;

My assumption has always been that using the rl[index] would generate  
larger and slower instructions because of the non-constant offset  
from pointer base.

Have I been going wrong all those years and in fact that is better?   
Or is there yet another way of doing the above more efficiently?

(Yes I know that keeping the size of the array in the array header  
would be most efficient but that is not how the code works at the  
moment.  It is my long term goal to switch to code that does make use  
of the array size and in fact in my OSX NTFS driver I have done this  
and plan to backport the changes to the Linux driver once I have it  
working there...)

Best regards,

	Anton
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/

Re: Bogus sparse warning?

[Linus Torvalds]

On Tue, 13 Feb 2007, Anton Altaparmakov wrote:
> 
> Yes you are quite right in what it is flagging up.  But I would have assumed
> that my current code is more efficient than alternatives.  Here is the code
> from the first warning:
> 
>                /* Determine the runlist size. */
>                trl = rl + 1;
>                while (likely(trl->length))
>                        trl++;
>                old_size = trl - runlist->rl + 1;
> 
> Note "rl" and "trl" are "structs" of size 24 bytes (i.e. not a power of 2).
> What we are dealing with here is an array of those "structs" which is
> terminated by a "struct" where its "->length" is zero.  And I do the above
> loop to get the size, i.e. I look for the last element and then subtract the
> first element from the last element and add one to get the number of elements
> in the array.
> 
> Is this not more efficient than say doing it using an index like so:
> 
> 	for (old_size = 0; rl[old_size].length; old_size++)
> 		;
> 	old_size++;
> 
> My assumption has always been that using the rl[index] would generate larger
> and slower instructions because of the non-constant offset from pointer base.

I actually think that the second one is the much faster one (although they 
differ in where they start - your first code sequence starts at "rl+1", 
while the second one starts at "rl[0]". The compiler is quite possibly 
also able to avoid the "rl[index]" calculation in the loop, by rewriting 
it as

	for (old_size = 1; rl->length; old_size++)
		rl++;

which you could obviously have done manually too (this assumes that you 
don't care about the original value of "rl" - use a temporary if you do.

> Have I been going wrong all those years and in fact that is better?  Or is
> there yet another way of doing the above more efficiently?

It partly depends on how slow division is. The above "fastest" version 
uses two registers instead of one, and has two additions in the loop. It 
has two  downsides: slightly higher register pressure and just the extra 
addition. However, on most archiectures the extra addition will be 
basically free (the "old_size" update doesn't depend on anything else than 
its previous iteration), and the register pressure will depend on how many 
registers you have.

More importantly, it depends on whether the division is slow (which is a 
big "if" - the cost of a division like that can range from anything 
between 4 cycles to 50+ cycles) and how many iterations you normally go 
through. Is the common length small? Big?

So I don't think there is any final answer on this. On _many_ 
architectures, division is fairly slow. On something like Core 2 or the 
Opteron, I think most small values are just 4 cycles to divide. On the 
other hand, the addition inside the loop will likely end up entirely free, 
since it would be a reg-reg ALU operation in a loop where there are likely 
cycles to schedule it. 

Probably not a big deal in this case anyway. We added the warning when Al 
Viro found some really expensive stuff in the VM layer in some hot-paths. 
I doubt it matters for you.

			Linus

Re: Bogus sparse warning?

[Anton Altaparmakov]

On 13 Feb 2007, at 16:10, Linus Torvalds wrote:
> On Tue, 13 Feb 2007, Anton Altaparmakov wrote:
>> Yes you are quite right in what it is flagging up.  But I would  
>> have assumed
>> that my current code is more efficient than alternatives.  Here is  
>> the code
>> from the first warning:
>>
>>                /* Determine the runlist size. */
>>                trl = rl + 1;
>>                while (likely(trl->length))
>>                        trl++;
>>                old_size = trl - runlist->rl + 1;
>>
>> Note "rl" and "trl" are "structs" of size 24 bytes (i.e. not a  
>> power of 2).
>> What we are dealing with here is an array of those "structs" which is
>> terminated by a "struct" where its "->length" is zero.  And I do  
>> the above
>> loop to get the size, i.e. I look for the last element and then  
>> subtract the
>> first element from the last element and add one to get the number  
>> of elements
>> in the array.
>>
>> Is this not more efficient than say doing it using an index like so:
>>
>> 	for (old_size = 0; rl[old_size].length; old_size++)
>> 		;
>> 	old_size++;
>>
>> My assumption has always been that using the rl[index] would  
>> generate larger
>> and slower instructions because of the non-constant offset from  
>> pointer base.
>
> I actually think that the second one is the much faster one  
> (although they
> differ in where they start - your first code sequence starts at "rl 
> +1",
> while the second one starts at "rl[0]".

Yes, sorry, that was just me being silly.  I can just make it start  
with "old_size = 1"...

> The compiler is quite possibly
> also able to avoid the "rl[index]" calculation in the loop, by  
> rewriting
> it as
>
> 	for (old_size = 1; rl->length; old_size++)
> 		rl++;
>
> which you could obviously have done manually too (this assumes that  
> you
> don't care about the original value of "rl" - use a temporary if  
> you do.

Hm, good point!  Yes, even I can see that that version would be  
faster...  I will switch the loops to doing this and see how many of  
the warnings I can get rid of that way...  Thanks for the suggestion!

>> Have I been going wrong all those years and in fact that is  
>> better?  Or is
>> there yet another way of doing the above more efficiently?
>
> It partly depends on how slow division is. The above "fastest" version
> uses two registers instead of one, and has two additions in the  
> loop. It
> has two  downsides: slightly higher register pressure and just the  
> extra
> addition. However, on most archiectures the extra addition will be
> basically free (the "old_size" update doesn't depend on anything  
> else than
> its previous iteration), and the register pressure will depend on  
> how many
> registers you have.
>
> More importantly, it depends on whether the division is slow (which  
> is a
> big "if" - the cost of a division like that can range from anything
> between 4 cycles to 50+ cycles) and how many iterations you  
> normally go
> through. Is the common length small? Big?

Common should be very small.  The "runlist" is basically an array of  
extents describing where the (meta)data of an inode is located on  
disk.  So in an ideal world where there is no fragmentation on the  
disk at all, all runlists would contain only two elements, one to  
state "logical block 0 corresponds to physical block X and the number  
of blocks in this extent is Y" and one to terminate the array which  
would have a length of zero.

In reality there will be fragmentation so the number of extents will  
increase.

As to how many there can be: A long time ago, the NTFS driver used to  
crash when accessing some files.  It turned out I was using kmalloc()  
to allocate the array of extents and the array was so big for some  
files that we tried to allocate more than kmalloc() allows (64kiB  
IIRC or was it 128kiB?) so assuming the maximum is 64kiB (the  
observations were on i386) that would mean that there are files out  
there that have more than 2^16 / 24 = 2740 entries in the array...   
Nowadays I allocate the array in multiples of PAGE_SIZE and if it is  
less than or equal to a page we I kmalloc() and otherwise I use  
vmalloc() which seems to work very well.

> So I don't think there is any final answer on this. On _many_
> architectures, division is fairly slow. On something like Core 2 or  
> the
> Opteron, I think most small values are just 4 cycles to divide. On the
> other hand, the addition inside the loop will likely end up  
> entirely free,
> since it would be a reg-reg ALU operation in a loop where there are  
> likely
> cycles to schedule it.

Yes, that makes perfect sense.  On modern pipelined CPUs it literally  
should be totally free.

> Probably not a big deal in this case anyway. We added the warning  
> when Al
> Viro found some really expensive stuff in the VM layer in some hot- 
> paths.
> I doubt it matters for you.

It can be at least somewhat of a deal because this is the extent map  
so it can be a very frequently traversed structure (e.g. in direct i/ 
o where we do not cache the on-disk location in buffers attached to  
page cache pages...).

But in any case having sparse spew over 20 warnings is annoying  
enough that I want to improve the code so the number of warnings at  
least goes down.  (-:

Thanks a lot for your advice!

Best regards,

	Anton
-- 
Anton Altaparmakov <aia21 at cam.ac.uk> (replace at with @)
Unix Support, Computing Service, University of Cambridge, CB2 3QH, UK
Linux NTFS maintainer, http://www.linux-ntfs.org/