Rethinking Experiments: from `unstable` to `StackValue(*)`

As a C program with a lot of mutable state, the interpreter is in constant danger of bugs due to stale pointers.

For instance: the "data stack" can have any of its pointers moved, whenever stack values are pushed or popped. You can create problems as easily as this:

 Value(*) item = TOP;  // top of data stack...right now
 if (IS_WORD(item)) {
      Init_Integer(PUSH(), 1);  // *may* need to relocate entire stack
      printf("Pushed a 1 after seeing %s\n", VAL_WORD_UTF8(item));  // !!! BAD
 }

The problem is that after you did a push, the previous item pointer might be bad. It usually isn't, because the stack doesn't need to expand on most pushes. But things that happen "only sometimes" are the most pernicious sorts of bugs.

It would seem that these stack pointers need to be a fundamentally different type...something that encodes the fact that they go invalid.

Weird First Idea: Use volatile

An odd thought I had some time ago was to leverage the volatile attribute. This is a feature that operates a bit like const, but it signals that a memory address might change outside of the compiler's awareness...so it can't use caching or registers to optimize around it. The memory has to be fetched each time.

Using volatile to mark pointers to stack locations would make it more obvious where the unstable pointers were. And then, if you had a routine that took unstable pointers or had them around on the stack, you'd know that you couldn't do stack pushes or pops. You also couldn't call the evaluator (because arbitrary evaluation can potentially call routines that do pushes and pops).

What seemed nice about this is that volatile--like const--could push its compile time checking transitively through the call graph. If you have a normal pointer, you can pass it to a routine that accepts either volatile or non-volatile pointers. But if you have a volatile pointer, you can only pass it to routines that accept volatile pointers. It would ferret out all the places that shouldn't call the evaluator...

But one drawback is that since this isn't what volatile is actually for, it has the unintended side-effect of making the pointer accesses slow. So this couldn't be used in the main build, hence volatile would have to have an alias that could be defined to nothing. I chose unstable:

#ifdef DEBUG_CHECK_UNSTABLE_POINTERS
    #define unstable volatile
#else
    #define unstable  // nothing in unchecked builds
#endif

As clever as this idea was, it made a big mess. In particular, it suffered from the problem that C has no particularly good way of letting you build this routine pattern:

  Type1 some_function(Type2 arg, ...)

  unstable Type1 some_function(unstable Type2 arg, ...)

You want the code to be exactly the same, you just don't want it to drop the annotation on the floor...because that defeats the purpose. There are ways to do it, but they're very ugly.

...and after all that mess, there's no bug alerts to fire off.

All this does is make it possible for you to visually inspect a routine and have a little bit more information. It doesn't intrinsically catch any bugs.

Taking Another Tactic: A Smart Pointer Class

So I ripped out all the unstable stuff, and looked at it again. What if in the C++ build, the pointers were actual smart pointer classes, that participated in a global count of how many such pointers were extant? So the result of operations like TOP would be a class... that would +1 the count on construction, and -1 the count on destruction. An assert would trigger if you tried to push or pop the stack with any non-zero number of these outstanding.

 StackValue(*) item = TOP;  // result held in pointer class, extant count + 1
 if (IS_WORD(item)) {
      Init_Integer(PUSH(), 1);  // asserts since a stack pointer is extant
      printf("Pushed a 1 after seeing %s\n", VAL_WORD_UTF8(item));  // unreached
 }

The interesting thing about such classes is that they can implicitly coerce themselves to Value(*)...and also, that C++ is willing to hold an instance live for as long as a callsite runs. That means that if a function take a value-by-pointer, you can pass it a temporarily constructed stackvalue-by-value:

Init_Integer(PUSH(), 1);  // generated stackval destructed after Init_Integer()

So ergonomically, it can act very much like it's returning Value(*). But to get the benefit, you just have to avoid directly storing the result of TOP or PUSH() in a Value(*) variable. Always put them in one of these smart pointers. (There's no particular good way to enforce this -and- be ergonomic, so it just has to be a policy developers making the core have to know about.)

And the C build just defines StackValue(*) as Value(*) and is none the wiser.

There's a bit of a technical problem in that this relies on StackValue(*) having constructor and destructor behavior... e.g. the destructor is where the count gets decremented. But since the interpreter uses longjmp() when a fail() happens, this can cut across the destructor, generating undefined behavior. While that can mean "anything" what it generally means is "your destructor does not run", which is fine because we enforce the extant count as zero at each evaluation. Hence unwinding a frame can just reset the count to zero. It's reliable enough for a debug feature.

And It Caught Bugs, Right Away!

As expected, there were some instances of potential movability of stacks. The cases were surprising; not things I would have suspected would be problems, but they were.

It's good to have this category of bugs have a reliable device for catching them. All while still remaining compilable as plain old C...

I'm not sure exactly what the moral of this story is. But maybe it's that compile-time checking may be great in theory, but you need to have a pretty good ratio of source-contamination-to-bugs-findable. If you can come up with a good way to catch the majority of things at runtime with a bit of localized code, that may be a better investment.

3 Likes

Strange unstable Concept, For The Record

The trick might be useful for something else down the road, but not this.

Here was the definition and some comments that were ripped out:

//=//// "UNSTABLE" TYPE CHECKING TRICK ////////////////////////////////////=//
//
// Some cells in Ren-C will potentially move if an evaluation is run.  This
// includes cells on the stack, or in arrays that are controlled by the user.
//
// Code should not be holding onto such cells across an evaluation, as they
// will become invalid.  To help make it clearer, this is an annotation put
// on any cell with an "unstable" address.  It's given to cells on the data
// stack, and pessimistically by any value accessed in an array with ARR_AT().
//
// In order to give the annotation some checking power, a debug mode will
// match it to the C qualifier `volatile`.  As with `const` there is some
// transitive power in the check...since a volatile can only be passed to
// a parameter that also accepts a volatile.
//
// A FUNCTION THAT TAKES AN `UNSTABLE` INPUT IS THEREFORE EFFECTIVELY
// PROMISING THAT IT WILL NOT CALL INTO THE EVALUATOR.
//
// Keeping the volatile setting on at run-time would have performance
// implications, as it disables optimizations.  So this is purely a type
// checking construct.  It should be disabled in other situations.
//
// TERMINOLOGY NOTE: Originally this was called `movable` and `FIXED()` was
// used to annotate places where it would be okay to pass the movable pointer.
// However, Windows API uses "FIXED" and movable means other things.  The
// somewhat more foreboding name of "unstable" is a little jarring, but,
// maybe it should be...you can't call evaluation or DS_PUSH() so long as
// you expect these values to stay good!
//
#define DEBUG_UNSTABLE_CELLS
#ifdef DEBUG_UNSTABLE_CELLS
    #define unstable volatile
    #define unstable_ok  // help annotate that there's a movable version

    template<typename T>
    inline static typename std::remove_volatile<T>::type* STABLE(T* v) {
        static_assert(
            std::is_volatile<T>::value,
            "you should only use STABLE() on unstable pointers"
        );
        return const_cast<typename std::remove_volatile<T>::type*>(v);
    }

    // When you are done with an unstable value, trash its contents before
    // calling into the evaluator.  This makes that clear.
    //
    #define FORGET(v) UNUSED(v)

    // !!! There are parts in the code where a cell in a usermode array is
    // held onto while arbitrary evaluation code is allowed to run.  This
    // must ultimately make sure that array has at least a temporary hold
    // on it, to avoid problems (this is what `unstable` is there to catch!)
    // But since the codebase is being gradually improved, some parts don't
    // do this yet.  Review these locations.
    //
    #define STABLE_HACK(v) STABLE(v)
#else
    #define unstable
    #define unstable_ok
    #define FORGET(v) UNUSED(v)
    #define STABLE(v) (v)
    #define STABLE_HACK(v) (v)
#endif
1 Like