Channels ▼
RSS

C/C++

Access Data Items In Ancestor Stack Frames Safely


Retain/recall semantics enable selected data on the call stack to be accessible from descendant frames.They are similar to dynamic scoping and the structural opposite of throw/catch. For many problems that developers currently use global data to address, retain/recall can be more convenient and flexible. The approach is safe for concurrent, recursive, and re-entrant code. In this article, I explain retain/recall and give an efficient implementation of the idea in C++ using the Posix and Win32 threading libraries.

Introducing Retain/Recall

In a typical modern programming language, information comes from:

  1. local (automatic) data
  2. passed (argument) data
  3. instance data if the code is part of an instance of an object.
  4. class (static) data if the code is part of a class, but not an instance.
  5. global data.

While global and class (static) data can be used from anywhere, they represent a shared resource that can break recursion, re-entrancy, and multithreading. Other items, though, have more limited accessibility, and a software engineer occasionally discovers that a program requires data to which there is no easy access.

For example, there may be a decoding library that was designed for internal algorithms, but now needs to have access to a system key store, which needs some kind of authorization context in order to open. At this point, the developer typically has two options (both with significant drawbacks):

  1. Rewrite the software or infrastructure so that the necessary data does get to that point (as instance or argument data). This may be impossible or create an unwieldy solution.
  2. Add global or class (static) data that is more universally accessible.

Error conditions used to suffer an analogous fate. Before throw/catch, a new error state could be handled in two ways:

  1. Return a new kind of error status to the caller, and upgrade the infrastructure so this potential error status traversed back to where it could be managed.
  2. Add global or class (static) data that recorded the error state. Hope that all the intervening code did not really break something before the error state was noticed and managed.

The throw/catch construct addresses this by allowing error conditions to safely work back through the call stack to a handler, even when the condition was not foreseen by the programmer who wrote the intervening text. In a sense, the throw/catch extends the visibility model so that exceptions (data about exceptional situations) can reach arbitrarily back in the call stack to address them.

This allows a third resolution to error handling; namely, throw an exception where it occurs and catch it (lower in the call stack) where you can handle it. This approach addresses the error handling problem without modifying infrastructure between the throw and catch frames or introducing global state. If there are more than one acceptable catch clauses for a given error, the latest one on the stack applies. Thus, nesting and recursion work fine and is there no global state to hinder re-entrance or multithreading.

If passing data from the current frame back in ancestral frames is such a good thing, what about accessing data from ancestral frames from code in the current frame? We call this kind of data visibility retained visibility because data values are retained (remembered) in a frame, which can then be recalled from any later frame. Figure 1 shows how throw/catch and retain/recall are related.

Retain/Recall
Figure 1: Comparing throw/catch (left) with retain/recall (right). The stack grows upward in the illustration.

In Figure 1, a throw unwinds the stack to the first matching catch, but the text for a recalled value executes in the current frame. Note that a thrown value is caught once, but a retained value can be recalled zero or more times. Note that, for throw/catch, text1 may rethrow a in order to activate text2(). Similarly, for retain/recall, a deepening recall would give access to a2, which is hidden from a simple recall by a1. Having retained visibility allows for a new solution to the data access problem: Retain a value where you know it; recall it (higher in the call stack) when you need it.

Retain/Recall Semantics

The semantics for retain/recall in a language that supports retained visibility are as follows:

  1. Retain a value for a type. This must be a statement within executable text. From the point of retention to the forget (explicit) or the end of the enclosing block/frame (implicit), we say that value is retained as that type, and structurally is a new block. It should be possible to retain any value derivable from the given type.
  2. Forget a value for a type. This must happen after a retain for the same type and value in the same block. It may be implicit at the end of the block containing a retain (but in the reverse order in the case of multiple retains).
  3. Retain a value for a type if a condition is true. Retain as above if the condition is true. A language may use a short-circuited evaluation of value in cases where the condition is false ( so the value is unused).
  4. Recall a value for a type. This must be an expression within executable text. A language may match this to a retain narrowly or broadly. A recall looks successively through each ancestral block/frame; the first block/frame that retained a value as the same type (narrow) or a derived type (broad) resolves the recalled value. Note that a given retain can resolve many recalls. If there is no matching retain, the recall fails.
  5. Deepening recall of a given type. There must be a mechanism for obtaining the sequence of retained values matching a given recall in frame deepening order.
  6. Failure. It must be possible to determine if a recall or the next step in a deepening recall will fail.

A broad matching of a recall to an ancestral retain would keep retain/recall in structural symmetry with throw/catch, since a catch will typically match a throw of a derived type value. However, this may not be in the best interest of the programmer. Allowing catch-alls is a convenience when trying to account for any number of error conditions, as might be the case nearer the root of the call tree. But recalls tend toward the branches of the call tree, where a recall of something specific is likely to be more useful. It also reduces the possibility of a hidden retention, where the desired value is retained, but a retention of a different (but derivable) type effectively hides it from recall (but not a deepening recall).

Implementing Retained Visibility in C++

Figure 2 illustrates how the retain of a given type can be implemented for a given thread. The structure has to be repeated for each thread and each type for which there are retained values.

Retain/Recall
Figure 2: Retained structure.

Each frame that has a retain for the given type is part of a linked list on the stack. s_current is a thread-local value that refers to the top most element in this list. Each retain keeps the address of the value it is retaining as. To recall a value, we only need to look at the m_as field of the s_current record. Retain-if records where the condition is false are skipped in the linked list.

For the sake of simplicity, consider the following retain class and recall function to support retained values of type T in a single-threaded environment. For the nonce, I have ignored template, access, and initialization notational details.

class retain
{
  static retain* s_current=0; // initial null/0 value
  retain* m_previous; // previous retained
  T* m_as; // what this retains as

  retain(T* as)
  {
      m_previous=s_current;
      s_current=this;
      m_as=as;
  }

  ~retain()
  {
      s_current=m_previous;
  }
};
bool retained() { return retain::s_current != 0; }
T* recall() { return retain::s_current->m_as; }

Now consider the following test of retain/recall (used as a template):

#include <assert.h>

#include "retain.hpp"

void inc() 
{ 
    int *p=recall<int>(); 
    ++(*p);
}

int main()
{
    int x=0,y=0;
    { 
        auto retain<int> as(&x);
        inc();
        assert(x == 1);
        {
            auto retain<int> as(&y);
            inc();
            assert(y == 1);
        }
        inc();
        assert(x == 2);
    }
    return 0;
      }

There is a static value, retain, for the address of the current retain record, and the construction of a new retain instance creates two pointer values: one that stores the previous retain record, and one pointer to what the record is retaining, as. Recalling is simply returning the as pointer from the retained static value. In the multithreaded case, the ideas are all the same, except that the static s_current value is kept in thread-local storage instead. The header file retain.hpp defines a thread-safe version of this idea as a template using Posix or Win32 thread-local storage. See the section on using the reference C++ Posix/Win32 implementation toward the end of this article for an explanation of the various APIs that are based on this approach.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Comments:

ubm_techweb_disqus_sso_-73a8c81d61777734d29ae22ecdab111f
2013-05-31T05:49:45

I don't see how the compiler could efficiently support caller->caller->x, but retain<int> as(&x) followed by (in some nested scope) recall<int>() is efficient.

caller->caller->x is very close to dynamic scoping. I don't think it holds up in C++ because it is inefficient, and because it is cumbersome.

By turning the picture to catch/throw by analogy, it would be like the throw clause had to explicitly unwind the stack, and find the exception hander by argument name instead of by type.


Permalink
ubm_techweb_disqus_sso_-8bba332cfa3860876462be05f9ac0cd9
2013-05-29T06:21:38

Hi Warren,

[ Let me move it up, it's too bad indentation.
Below i added how it could look like if supported by the language.
]

i first tried an own version with free functions and it ended up in ICE for gcc :-) ( http://gcc.gnu.org/bugzilla/sh... )

But that was my fault, because i used invalid C++ code.

But as you were asking for support for this in the programming language itself anyways, i tried again with function objects - presuming, that the requirements for those could be hidden in the language, if having 1) a this ptr for functions, 2) a parent/caller ptr for the invoking function, 3) public/private/(protected?) attributes in functions like in classes.

My result looks like this:



/*
* main.cpp
*
* Created on: May 24, 2013
* Author: frank
*/
#include <iostream>
struct Nop
{ };
template <class caller="">
struct Func
{
public:
CALLER * caller;
};
template <class caller="">
struct Func3 : public Func<caller>
{
public:
typedef Func3 type;
void exec (
CALLER * p_caller)
{
this->caller = p_caller;
std::cout << "Func3: entered" << std::endl;
std::cout << "caller->caller->x = " << this->caller->caller->x << std::endl;
}
};
template <class caller="">
struct Func2 : public Func<caller>
{
public:
typedef Func2 type;
void exec (
CALLER * p_caller)
{
this->caller = p_caller;
std::cout << "Func2: entered" << std::endl;
std::cout << "caller->x = " << this->caller->x << std::endl;
this->caller->x = 5;
Func3<type>().exec(this);
}
};
template <class caller="">
struct Func1 : public Func<caller>
{
public:
typedef Func1 type;
int x = 1;
void exec (
CALLER * p_caller)
{
this->caller = p_caller;
std::cout << "Func1: entered" << std::endl;
Func2<type>().exec(this);
std::cout << "this->x = " << this->x << std::endl;
}
};
int main(
int argc,
char ** argv)
{
Nop nop;
Func1<nop>().exec(&nop);
return 0;
}

This is how it could look like if supported by the language:


/*
* main.cpp
*
* Created on: May 24, 2013
* Author: frank
*/
#include <iostream>
void func3(void)
{
std::cout << "func3: entered" << std::endl;
std::cout << "caller->caller->x = " << caller->caller->x << std::endl;
};
void func2(void)
{
std::cout << "func2: entered" << std::endl;
std::cout << "caller->x = " << caller->x << std::endl;
caller->x = 5;
func3();
}
void func1(void)
{
public:
int x = 1;
std::cout << "func1: entered" << std::endl;
func2();
std::cout << "x = " << x << std::endl;
}
int main(
int argc,
char ** argv)
{
func1()
return 0;
}


Permalink
ubm_techweb_disqus_sso_-8bba332cfa3860876462be05f9ac0cd9
2013-05-28T14:08:51

<sorry for wrong post - you can delete this>


Permalink
ubm_techweb_disqus_sso_-73a8c81d61777734d29ae22ecdab111f
2013-05-26T15:13:50

Sorry, I don't see how retain/recall and closures or nested functions are related. They certainly could be used together, but they seem like a wrench and a hammer to me; just different tools.


Permalink
ubm_techweb_disqus_sso_-8d269ba47634f0aff4fdd7c9d87dd808
2013-05-26T07:14:57

So use different names already!


Permalink
ubm_techweb_disqus_sso_-8d269ba47634f0aff4fdd7c9d87dd808
2013-05-26T07:14:23

Wouldn't most of the problems this feature solves be solved better by using a language that allows nested subprograms?


Permalink
ubm_techweb_disqus_sso_-73a8c81d61777734d29ae22ecdab111f
2013-05-25T14:05:24

Yes, it really does let you look back through nested scopes. The checkpoint example shows this, since working through commits and rollbacks does not have to be related to a function call.


Permalink
ubm_techweb_disqus_sso_-8bba332cfa3860876462be05f9ac0cd9
2013-05-25T06:50:20

Hi Warren,
I think this technique applies not only for stack frames along a call hierarchy, but also for nested scopes. Isn't it another way to break the 'scope hiding' problem?

int x; // outer x
{
int x; // inner x
// no chance to access outer x as 'x' here anymore
}

Maybe you can make another example for that in the article.
Of couse, you can also use an alias (reference) with different name to pass something from outside to inside to handle this. But i think your way is better if supported by the language. E.g. parent->x or caller->x. Also caller->caller->x for #3 levels.
With such we could stop thinking in black-or-white manner about 'local' and 'global', and start to ruminate over 'nearby' :-)


Permalink
ubm_techweb_disqus_sso_-73a8c81d61777734d29ae22ecdab111f
2013-05-25T04:27:27

Thanks and agree. It is there only to emphase that retains should live in a stack frame.


Permalink
mttd
2013-05-24T23:46:45

Note that the way you're using "auto" (i.e., as the automatic storage duration specifier) is not future-proof, since this use has been deprecated in C++11: http://en.cppreference.com/w/c...


Permalink
ubm_techweb_disqus_sso_-73a8c81d61777734d29ae22ecdab111f
2013-05-24T18:36:17

Updating to function objects would be modifying infrastructure, which isn't always possible. Furthermore, the use of function objects does not match well to the implementation patters in the article; you would be replicating a version of retain/recall for many of these problems (the lang parameter could be a function object, but it would still become an object you would either end up making global or peppering everywhere). In the end, even with function objects in place in an application, you can get into the same situations retain/recall is designed to help address.


Permalink
ubm_techweb_disqus_sso_-8bba332cfa3860876462be05f9ac0cd9
2013-05-24T12:00:32

Very interesting vertical extension of "scope" along a call hierarchy. And it offers the option to poll (specific) instead of push (all).
But why not dropping free functions and switching to function objects or alike (closure) for this? Those can have context, can still provide a generic interface to access this context, but e.g. also *specific* getters and setters(!). This also supports contracts ("function" can only be called by another "function" which provides some required property - well, touching the area of dependency inversion). All you need is to pass a *caller ptr (a kind of counterpart to the *this ptr) and you can model your expectations.


Permalink

Video