www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - About some bugs

reply bearophile <bearophileHUGS lycos.com> writes:
I have studied more Linux bugs.

----------------

An example of bug (more than 14 like this fixed in few years):

-       memset(pp, 0, sizeof(pp));
+       memset(pp, 0, sizeof(*pp));

-       memcpy((caddr_t)TstSchedTbl, (caddr_t)&vcIndex,sizeof(TstSchedTbl));
+       memcpy((caddr_t)TstSchedTbl, (caddr_t)&vcIndex, sizeof(*TstSchedTbl));

Here the type system knows that pp is a pointer. sizeof(pp) is typically a
word, while the correct sizeof(*pp) is often larger. A simple way to avoid this
bug in D is to use a zerioing template function, something like (untested) (in
GNU C there is a way to write a similar macro, I don't know why they don't use
it, even if it's a bit less safe and much less nice looking):

void zeroit(T)(T* ptr) if (!IsPointer!T) {
    memset(ptr, 0, (*ptr).sizeof);
}

Standard safer wrappers for some C functions may help low-level D coding.

If you don't want to use a zeroit() then a type system able to catch such bugs
needs some nice annotations...

----------------

A common (> 12 cases in few years) example of redundant code:

        u32 da = new->da_start;
-       if (!obj || !new || !sgt) {...
+       if (!obj || !sgt) {...

If the first line is correct, then "new" can't be NULL, so there's no need to
test "|| !new".

In 13 similar cases the code is inside a branch where the NULL test of the
pointer is already done:

if (ptr != NULL) {
    if (!ptr) { ...
}

----------------

In 7 cases the result of malloc-like function was not tested for NULL:

        agp = kmalloc(sizeof(*agp), GFP_KERNEL);
+       if (!agp)
+               return NULL;

----------------

A very common case (20 cases in few years) are like this, where a pointer is
deferenced before the NULL test:

        block = bdev->bd_disk->private_data;
-       base = block->base;
        if (!block)
                return -ENODEV;
+       base = block->base;

----------------

2 cases like this (the pattern (!E && !E->fld) is nonsensical):

-               if (!slot->hotplug_slot && !slot->hotplug_slot->info) 
+               if (!slot->hotplug_slot || !slot->hotplug_slot->info)
                        continue;

----------------

There are 11 cases like this (alloc_bootmem never returns NULL and it always
sets the momory to zero):

    zero_page = alloc_bootmem_low_pages_node(NODE_DATA(0), PAGE_SIZE);
-   memset(zero_page, 0, PAGE_SIZE);

----------------

There are a lot of cases (34) of missing free:

+       kfree(iter);

----------------

Two cases need a wider NULL test:

-               if (fep != NULL) {
+               if (fep && fep->ops) {
                        (*fep->ops->free_bd)(ndev);
                        (*fep->ops->cleanup_data)(ndev);
                }

----------------

In this post I don't see any little rule worth adding to the D compiler. So to
bugzilla I will add only the !x&y thing.

But from what I have seen many bugs are NULL-related, and many of them are
avoidable with two features present at the same time in the language:

1) Nonnull pointer/reference tag (with it you don't miss some null tests, and
you avoid some redundant tests);

2) Plus a bit of inter-function (not intra, for that nonnull signatures are
enough) flow analysis to avoid bugs like:

base = block->base;
if (!block)
    return -ENODEV;

if (fep != NULL) {
    (*fep->ops->free_bd)(ndev);

(P.S.: integer overflow bugs happen in Linux kernel too.)

Bye,
bearophile
Jan 04 2011
next sibling parent reply "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Tue, 04 Jan 2011 14:34:15 +0200, bearophile <bearophileHUGS lycos.com>  
wrote:


 void zeroit(T)(T* ptr) if (!IsPointer!T) {
     memset(ptr, 0, (*ptr).sizeof);
 }

 Standard safer wrappers for some C functions may help low-level D coding.

 If you don't want to use a zeroit() then a type system able to catch  
 such bugs needs some nice annotations...


Doesn't D already solve this?
For value types: obj = typeof(obj).init;
For arrays: arr[] = typeof(arr[0]).init; // or just 0 or null or whatever  
.init is


 If the first line is correct, then "new" can't be NULL, so there's no  
 need to test "|| !new".


I think this is something that should be done by the optimizer.


 In 7 cases the result of malloc-like function was not tested for NULL:


This is rather specific. Application programmers would usually want an  
exception to be thrown on a failed allocation.


 A very common case (20 cases in few years) are like this, where a  
 pointer is deferenced before the NULL test:

         block = bdev->bd_disk->private_data;
 -       base = block->base;
         if (!block)
                 return -ENODEV;
 +       base = block->base;


Delphi compilers warn in cases when a condition is always true/false,  
because Delphi lacks metaprogramming so such cases are usually due to a  
bug.

-- 
Best regards,
  Vladimir                            mailto:vladimir thecybershadow.net
Jan 04 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Vladimir Panteleev:


 Doesn't D already solve this?


Yup.



         block = bdev->bd_disk->private_data;
 -       base = block->base;
         if (!block)
                 return -ENODEV;
 +       base = block->base;


 
 Delphi compilers warn in cases when a condition is always true/false,  
 because Delphi lacks metaprogramming so such cases are usually due to a  
 bug.


This is a different situation. You need a bit of flow analisys to catch this
bug (to give a state to a type).

Bye,
bearophile
Jan 04 2011
prev sibling next sibling parent reply spir <denis.spir gmail.com> writes:
On Tue, 04 Jan 2011 07:34:15 -0500
bearophile <bearophileHUGS lycos.com> wrote:


 An example of bug (more than 14 like this fixed in few years):
=20
 -       memset(pp, 0, sizeof(pp));
 +       memset(pp, 0, sizeof(*pp));
=20
 -       memcpy((caddr_t)TstSchedTbl, (caddr_t)&vcIndex,sizeof(TstSchedTbl=


));

 +       memcpy((caddr_t)TstSchedTbl, (caddr_t)&vcIndex, sizeof(*TstSchedT=


bl));

=20
 Here the type system knows that pp is a pointer. sizeof(pp) is typically =


a word, while the correct sizeof(*pp) is often larger. A simple way to avoi=
d this bug in D is to use a zerioing template function, something like (unt=
ested) (in GNU C there is a way to write a similar macro, I don't know why =
they don't use it, even if it's a bit less safe and much less nice looking):

=20
 void zeroit(T)(T* ptr) if (!IsPointer!T) {
     memset(ptr, 0, (*ptr).sizeof);
 }


Doesn't this in fact hide the error to the programmer (by silently correcti=
ng)? Why not instead for instance:

void zeroit(T)(T* ptr) if (!IsPointer!T) {
    throw new Exception("Type error: argument to <funcname> should be a poi=
nter.");
}

(And what if the memory to be actually memset is not ptr's target?)

About non-null thingies, I would be all for a mode in which is inserted
	if (p is null) throw ...;
before _every_ implicite or explicite deref of every implicite (pointer) or=
 implicite (class element) pointer. And even make this the default for non-=
release. (With line number in the message ;-)
Am I dreaming?


Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com
Jan 04 2011
parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
spir <denis.spir gmail.com> wrote:


 void zeroit(T)(T* ptr) if (!IsPointer!T) {
     memset(ptr, 0, (*ptr).sizeof);
 }


 Doesn't this in fact hide the error to the programmer (by silently  
 correcting)?


No. It ensures that the pointer and size are from the same pointer.
I would say it is somewhat analogous to D's arrays, which are a hell
of a lot better than free pointer/length pairs.



 Why not instead for instance:

 void zeroit(T)(T* ptr) if (!IsPointer!T) {
     throw new Exception("Type error: argument to <funcname> should be a  
 pointer.");
 }


I'm not sure this makes sense. The error message seems to indicate you
don't have a pointer, while that is exactly what you do.
The template constraint also say that this is not an overload of the
above function, making it simply a function that throws.



 (And what if the memory to be actually memset is not ptr's target?)


If people start throwing random pointers into functions, that is a
problem that's hard to work around. bearophile's zeroit function takes
memset and removes its main weak point, namely that it takes a free
pointer/length pair, rather than a structure containing the two.



 About non-null thingies, I would be all for a mode in which is inserted
 	if (p is null) throw ...;
 before _every_ implicite or explicite deref of every implicite (pointer)  
 or implicite (class element) pointer. And even make this the default for  
 non-release. (With line number in the message ;-)
 Am I dreaming?


Yeah. :P
Much more likely would be the idea that has been discussed, of opt-in
non-nullness, by disabling the default constructor for a struct that
wraps a pointer.

-- 
Simen
Jan 04 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Simen kjaeraas:


 Much more likely would be the idea that has been discussed, of opt-in
 non-nullness, by disabling the default constructor for a struct that
 wraps a pointer.


I am not sure that's enough.

Bye,
bearophile
Jan 04 2011
parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:


 Simen kjaeraas:


 Much more likely would be the idea that has been discussed, of opt-in
 non-nullness, by disabling the default constructor for a struct that
 wraps a pointer.


 I am not sure that's enough.


Could you please show a case where it isn't?

-- 
Simen
Jan 04 2011
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
bearophile wrote:

 I have studied more Linux bugs.
 
 ----------------
 
 An example of bug (more than 14 like this fixed in few years):
 
 -       memset(pp, 0, sizeof(pp)); +       memset(pp, 0, sizeof(*pp));
 
 -       memcpy((caddr_t)TstSchedTbl, (caddr_t)&vcIndex,sizeof(TstSchedTbl)); 
 +       memcpy((caddr_t)TstSchedTbl, (caddr_t)&vcIndex,
 sizeof(*TstSchedTbl));
 
 Here the type system knows that pp is a pointer. sizeof(pp) is typically a
 word, while the correct sizeof(*pp) is often larger. A simple way to avoid
 this bug in D is to use a zerioing template function, something like
 (untested) (in GNU C there is a way to write a similar macro, I don't know
 why they don't use it, even if it's a bit less safe and much less nice
 looking):
 
 void zeroit(T)(T* ptr) if (!IsPointer!T) { memset(ptr, 0, (*ptr).sizeof); }
 
 Standard safer wrappers for some C functions may help low-level D coding.
 
 If you don't want to use a zeroit() then a type system able to catch such
 bugs needs some nice annotations...


In D:
     pp[] = 0;
or:
     pp = typeof(pp).init;

etc.




 In this post I don't see any little rule worth adding to the D compiler.


Many of them are dealt with with D's scope guard, RIAA, and garbage collection 
support.
Jan 04 2011
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
bearophile wrote:

 I have studied more Linux bugs.


Is there a research paper that these came from?
Jan 04 2011
parent bearophile <bearophileHUGS lycos.com> writes:
Walter:


 bearophile wrote:

 I have studied more Linux bugs.


 
 Is there a research paper that these came from?


They are just part of the Linux bugs fixed in those few years.
I am sorry, but what I have written doesn't come from a paper. They partially
come from this page:
http://coccinelle.lip6.fr/impact_linux.php
Plus some exploration of the kernel bug repository.

With some more weeks of search and work a paper may be written :o)

Bye,
bearophile
Jan 04 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Simen kjaeraas:


 bearophile <bearophileHUGS lycos.com> wrote:
 

 Simen kjaeraas:


 Much more likely would be the idea that has been discussed, of opt-in
 non-nullness, by disabling the default constructor for a struct that
 wraps a pointer.


 I am not sure that's enough.


 
 Could you please show a case where it isn't?


We have discussed this a lot in past, I repeat because in this newsgroup I have
learnt that sometimes you need to repeat things many times before most people
start to notice.

First of all it's a matter of syntax. Attaching a " " to a reference/pointer
type to turn it into a nonnullable is not the same thing as using a special
struct:

class T {}
T nullable_reference;
T  nonnullable_reference = new T ();

struct S {}
S nullable_pointer;
S  nonnullable_pointer = new S ();

void foo(T  x) { ... }


A handy short syntax is able to turn something from a seldom used feature, to
an idiom most people in the community use. Python language designers have
understood this well.

Then, I was talking of two features present at the same time. The first is
nonnullable rerefence types, and the other is a bit of flow analysis that
essentially gives a possible-null / surely-not-null state to a type:

S s = new S;
...
if (s != null) {
    // here s is essentially a S 
}


It avoids bugs like:

static int rose_rebuild_header(struct sk_buff *skb)
{
    ...
    if (!rose_route_frame(skbn, NULL)) {
        kfree_skb(skbn);
        stats->tx_errors++;
        return 1;
    }
    stats->tx_packets++;
    stats->tx_bytes += skbn->len;
    ...
}

The bug here is that in some cases skbn the code calls free on skbn, so at the
end of the if{} yuou can't perform skbn->len in all cases. The type system has
to denote this as a possible bug.

Just disallowing standard constructors is useful, but it's not enough.

Bye,
bearophile
Jan 05 2011
parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:


 Simen kjaeraas:


 bearophile <bearophileHUGS lycos.com> wrote:


 Simen kjaeraas:


 Much more likely would be the idea that has been discussed, of opt-in
 non-nullness, by disabling the default constructor for a struct that
 wraps a pointer.


 I am not sure that's enough.


 Could you please show a case where it isn't?


 We have discussed this a lot in past, I repeat because in this newsgroup  
 I have learnt that sometimes you need to repeat things many times before  
 most people start to notice.

 First of all it's a matter of syntax. Attaching a " " to a  
 reference/pointer type to turn it into a nonnullable is not the same  
 thing as using a special struct:

 class T {}
 T nullable_reference;
 T  nonnullable_reference = new T ();

 struct S {}
 S nullable_pointer;
 S  nonnullable_pointer = new S ();

 void foo(T  x) { ... }


 A handy short syntax is able to turn something from a seldom used  
 feature, to an idiom most people in the community use. Python language  
 designers have understood this well.

 Then, I was talking of two features present at the same time. The first  
 is nonnullable rerefence types, and the other is a bit of flow analysis  
 that essentially gives a possible-null / surely-not-null state to a type:

 S s = new S;
 ...
 if (s != null) {
     // here s is essentially a S 
 }


 It avoids bugs like:

 static int rose_rebuild_header(struct sk_buff *skb)
 {
     ...
     if (!rose_route_frame(skbn, NULL)) {
         kfree_skb(skbn);
         stats->tx_errors++;
         return 1;
     }
     stats->tx_packets++;
     stats->tx_bytes += skbn->len;
     ...
 }

 The bug here is that in some cases skbn the code calls free on skbn, so  
 at the end of the if{} yuou can't perform skbn->len in all cases. The  
 type system has to denote this as a possible bug.

 Just disallowing standard constructors is useful, but it's not enough.


With the exception of your first example, these require quite a lot of
plumbing in the compiler, and are thus not an alternative for D2 and,
I would say, unlikely for D3. The wrapper struct with a disabled default
constructor is close to possible in D2.

Like with AAs, the sugar for non-null can easily be implemented atop a
library solution, if the language is powerful enough. D is, except in
the case of type states or the like. Sure, I would love for D to have
a perfect type system, but I believe type state does not bring enough
goods to the table that it's worth implementing yet. Perhaps in D3.

Having a solution that works (your last example shows how it's possible
to have invalid pointers in non-null pointers, but not null-pointers),
is a lot better than hoping for something in the far future, and I have
yet to be made aware of any serious shortcomings of the solution with a
disabled default constructor.

-- 
Simen
Jan 05 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
What I have written was meant for D3.

The example I've shown at the end is a bug found in the Linux kernel, they have
found many similar bugs, even in old code. Notnull types are usually not enough
to catch similar bugs.

The second part of my proposal was not a general typestate implementation, it's
specific, hard-coded, and only two or three states are present, for just
reference types, and only few built-in things change the state (if-then-else
branches, nullity assetions, nullable/notnull type annotations, and little
more).

In a language with gotos and asm your bit of flow analysis will produce some
false positives and some false negatives. This currently doesn't go well with D
Zen, but things may change.

Bye,
bearophile
Jan 05 2011
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
Simen kjaeraas:


 With the exception of your first example, these require quite a lot of
 plumbing in the compiler, and are thus not an alternative for D2 and,
 I would say, unlikely for D3. The wrapper struct with a disabled default
 constructor is close to possible in D2.


Some "plumbing" is needed even for the first half of the proposal, to correctly
manage partially initialized objects, it's explained here:
http://research.microsoft.com/pubs/67461/non-null.pdf

Some partial notes of mine on the topic are here:
http://d.puremagic.com/issues/show_bug.cgi?id=4571

Bye,
bearophile
Jan 05 2011
parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
bearophile <bearophileHUGS lycos.com> wrote:


 Simen kjaeraas:


 With the exception of your first example, these require quite a lot o=




f

 plumbing in the compiler, and are thus not an alternative for D2 and,=





 I would say, unlikely for D3. The wrapper struct with a disabled defa=




ult

 constructor is close to possible in D2.


 Some "plumbing" is needed even for the first half of the proposal, to =


 =


 correctly manage partially initialized objects, it's explained here:
 http://research.microsoft.com/pubs/67461/non-null.pdf

 Some partial notes of mine on the topic are here:
 http://d.puremagic.com/issues/show_bug.cgi?id=3D4571


Now this is what I wanted to see. As D does not have C++'s initializatio=
n
lists, the problem of half-initialized fields may require flow analysis.=

And yes, I remember this was discussed last time, but apparently I forgo=
t.

I see that this problem can also be thought of in the typestate paradigm=
:
a class is in the 'raw' state until constructors have finished running,
and in this state the invariants of members are not guaranteed to hold.

Hmm, the more I think about it, the more I believe you are right that
typestates are Awesome=E2=84=A2, and should be included in D3.


-- =

Simen
Jan 05 2011