488941 - Non-null type check

Status: RESOLVED WONTFIX

(Developer Infrastructure :: Source Code Analysis, defect)

Description

[Jason Orendorff [:jorendorff]]

I would like a static analysis that detects possible null derefs.

Ideally the annotations would attach to types, so I could do things like,

  typedef JSContext * JS_NOTNULL JSContextPtr;
  typedef JSObject * JS_NOTNULL JSObjectPtr;

  jsval JS_GetEmptyStringValue(JSContextPtr cx);
  typedef JSBool (*JSEnumerateOp)(JSContextPtr cx, JSObjectPtr obj);

I can imagine some translation units might add JS_NOTNULL annotations throughout and would want a thorough type-based guarantee that null derefs can't happen; whereas others might only see JS_NOTNULL in APIs and would only want an error if they actually do pass or assign a NULL where they shouldn't.

Comment 1

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Two initial thoughts:

  (1) This looks like a reasonably straightforward flow-insensitive analysis, except that we will need a precondition-type declaration for "external" pointers.  See bug 488945.

  (2) Another way to do this is to use pork/porky to rewrite all these T* types into T&, and typedef T& to something else if desired.  At API boundaries, the code can deref T*'s and pass them as T& to the rest of the implementation.  A null T* will simply cause a crash.  And we could extend the deprecated API checker to ensure that T* isn't used in *monkey.

Comment 2

[Jason Orendorff [:jorendorff]]

I don't understand what approach 2 would gain us.  Null pointer dereferences already crash.

(But note that even if approach 2 produced a full static guarantee against null pointer dereferences, the API confusion alone would probably make it a non-starter.)

Comment 3

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

(In reply to comment #2)
> I don't understand what approach 2 would gain us.  Null pointer dereferences
> already crash.
> 

Neither case can prevent NULL arguments being passed to the JS API.  The question is what to do with them at the API boundary.  We had discussed using an |abort()| or other noreturn function for (1), which is essentially a crash.  A pointer dereference is another mechanism; at the API boundary, "converting" the pointer to a reference statically guarantees internal JS code (inside the API boundary) has a non-NULL pointer.  Otherwise, the deref immediately crashes, at the API boundary.

I don't really care how NULL pointers are handled at the API boundary.  Either approach I mentioned above will work for (1) or (2).  The mechanism just needs to make it clear to the analysis that the code "dies" if the pointer is NULL (i.e., |assumes()| non-NULL).

Comment 4

[(dormant account)]

yeah i like the idea of using references too. Ie using proper compiler features.

Comment 5

[Brendan Eich [:brendan]]

References are great for locals. For parameters, Andreas and I at least are more in favor of explicit unary-& on the actual parameter, to show readers (even those who know the code) where the out parameters are. But we use references for in and in-out params in jstracer.cpp already, so we're flexible.

For heap to heap data members, references are less useful. Either you have a single ownership relation, in which case try to fuse the allocation as an inline data member; or you have some modularity reason not to fuse; or there can be many owners, but then initialization to non-null from birth is often hard.

/be

Comment 6

[Jason Orendorff [:jorendorff]]

(comment 3)
> Neither case can prevent NULL arguments being passed to the JS API.

What makes the JSAPI any different from internal APIs?  We should make nullability part of the parameter type.  As a side benefit, if the API user wants to check their code (Gecko might), they can just use the same analysis.

> yeah i like the idea of using references too. Ie using proper compiler
> features.

I don't blame you for not wanting to hack any GCC more than is strictly necessary, but I don't think this can really work.

One, it's super ugly at the language level to use references to mean "not null" -- once you notice that a variable or parameter is never null, you have to modify every line of code that uses it in order to get the analysis to work, instead of just adding JS_NOTNULL to its type.  Later when you want to pass null, you have to change it all back.  How you use a JSObject * argument would differ from function to function, out of proportion (IMO) to the importance of nullability.

Two, I think we would get this done and then it wouldn't be sufficient, because we would find out there are a few cases where we have an assignable pointer (maybe a struct field or array element) that can't be null.

Comment 7

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Attachment: Prototype analysis, for backup purposes

The usage is relatively simple: given a pointer type "T *", one does the following:

  (1) Define typedef soemething like 
    typedef Tnonnull T* __attribute__((user("nonnull")));

  (2) Define a "trusted cast" function, which takes a T* and returns a non-null Tnonnull.  This function is expected to die if its argument is NULL (but this is not checked).
    Tnonnull Trusted_Cast(T* t) __attribute__((user("nonnull cast")));

  (3) Use the T* type for parameters to public API functions, Tnonnull on non-public functions.  Use the |Trusted_Cast()| at API boundaries.

The analysis enforces non-null safety through a vanilla type checking pass.  This type check ensures that T* is never assigned to Tnonnull (outside of |Trusted_Cast()|).

First issue: the attached analysis is correct in the sense of being sound (modulo the trusted "nonnull cast" annotation).  However, there are several cases where gcc/dehydra drop necessary typedef information.  This is a matter of fixing bugs there, however, and they will be spun off from this bug as found.

Second issue: this implementation assumes that all "extern" functions (non-static) are exported, public API symbols.  This probably isn't universally the case.  There should be another annotation marking APIs as public (I understand jsapi already has something we can use).

Third issue: it will take some work to rewrite |T*| into |Tnonnull|.  This /should/ be a relatively straightforward porky.py task.  We'll soon see.

Comment 8

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

After talking with Taras, I'm going to recast this analysis as a treehydra script.  treehydra may be preserving more accurate type information, and the bugs listed above may go away.

Comment 9

[(dormant account)]

(In reply to comment #8)
> After talking with Taras, I'm going to recast this analysis as a treehydra
> script.  treehydra may be preserving more accurate type information, and the
> bugs listed above may go away.

I would appreciate testcases filed in a dehydra bug on this. This should work as well in dehydra as in treehydra.

Comment 10

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Attachment: Improved treehydra version

Moving to treehydra fixed deficiencies in the previous analysis.  However, gcc still loses precise type info for temporary variables (it drops typedefs).  This means I had to put in a hack that has the unfortunate side effect of making this type check unsound (!!!).  The pass could be made sound, but it's probably easier to just fix gcc here.

That said, I think I have a better solution to this problem than extending C++'s type system.  Post soon to follow.

Comment 11

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

I think a non-null smart pointer with appropriate operators (that ensure a raw pointer can't accidentally be converted to it) is the best way to go.  A simple enough implementation will get completely optimized away (probably).  Something like:

template<T>
class NonnullPtr
{
public:
    explicit NonnullPtr(T* p)
    {
        assert(p);
        p_ = p;
    }
    
    NonnullPtr(const NonnullPtr& np) :
        p_(np.p_) { }

    NonnullPtr& operator=(const NonnullPtr& np)
    {
        p_ = np.p_;
        return *this;
    }

    T* operator->() const { return get(); }
    operator T*() const { return get(); }

    T* get() { return p_; }

private:
    T* p_;
    static void* operator new(size_t);
    static void* operator delete(void*);
};

I didn't even try to compile this, but I think it conveys the idea.

Comment 12

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

I consider this bug essentially fixed.  Spidermonkey can solve this problem with either the extra type checking pass or the smart pointer.  Let me know which you prefer and I'll close out this bug.  The type checking pass requires more work to integrate into static-analysis builds.

Comment 13

[Jason Orendorff [:jorendorff]]

Extra type checking pass, I think.

Smart pointers are the right answer in theory.  For now I'd rather have plain old pointers in gdb, because the extra object there is just a pointless roadblock.