Channels ▼
RSS

Parallel

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.
 

Video