IBM
Contents Index Previous Next



Own and ORef Generators


Introduction

A major problem to obtain fast applications generated from SDL is the data model, that requires copying of data in a number of places. In an interchange of a signal between two processes, the signal parameters are first copied from the sending process to the signal and then again copied from the signal to the receiver. If the two processes have access to common memory, it would be possible only to pass a reference to the data via the signal, and in that way there would be no need to perform the two copy actions.

The generator Ref can be used for this purpose (see The Ref Generator), but there is a number of important problems when using the Ref generator:

Basic Properties of the Own Generator

The purpose of the Own generator is to solve the situation described above, i.e. it should be possible to limit the number of copy operations that are needed, at the same time as the user should not need to worry about memory deallocation, and simultaneous access to the memory from several processes should not be possible.

The basic property of the Own generator that makes this possible is that only one Own pointer at a time can refer to the same memory. This variable (of Own type) is referred to as the owner of the memory. Ownership is passed to another variable by assignment.

Example 37 : Own variables

newtype Data struct 
  a, b integer;
endnewtype;

newtype Own_Data Own(Data)
endnewtype;

dcl
  v1 Own_Data,
  v2 Own_Data;

task v1 := v2;

This assignment is interpreted as follows:

By this scheme the basic properties of the Own generator is preserved, i.e. all memory no longer accessible is deallocated and there is only one reference to the data.

To handle more complex cases, the order in which these operations are performed is a bit more complicated. With the same types and variables as in the example above and the procedure P, taking three Own_Data parameters:

task v1 := P(v2, v1, v2);

we get the following execution:

Evaluation of the right-hand side is performed from left to right, i.e. starts with the first actual parameter of P. The first formal parameter of P is assigned the value of v2 and takes the ownership of this memory. The variable v2 is assigned the value Null. The same thing happens for the second formal parameter and the variable v1. The third formal parameter of P get the value Null as v2 is Null at this point.
Now the procedure P is called and its return value is obtained. Before assigning this value to the variable on the left hand side, i.e. to v1, the memory currently referred to by v1 is deallocated. In this case v1 is Null at this point as the second formal parameter of P already have taken the ownership of this memory. Last the variable v1 is assigned the value returned by P.

Ownership is, as can be seen in the example above, passed not only in assignments, but in every case where the reference is assigned to some other place. This happens for example in assignments, input, output, set, reset, procedure call, and create. The only places where ownership is not passed is:

Note that copy(v2) is a "deep" copy, i.e. any Own pointers in the copied data structure are also copied. Otherwise we would end up with several references to the same memory.

Definition of Own Generator

The Own generator is defined in SDL according to the following:

GENERATOR Own (TYPE Itemsort)
  LITERALS
     Null;
  OPERATORS
    "*>"  : Own, ItemSort -> Own;
    "*>"  : Own -> ItemSort;
    make! : ItemSort -> Own;
  DEFAULT Null;
ENDGENERATOR Own;

Basically the Own generator is a way to introduce pointers to allocated memory. The Null value is as usual interpreted as "a reference to nothing". The operators "*>" are the Extract! and Modify! operators, i.e. the way to reference or modify the memory referred to by the pointer. Using the type and variables in the previous example the following statements are correct:

task v1*>!a := 1;
task i := v2*>!b;
   /* integer assignment, i is integer variable */
task d := v2*>;
   /* struct level assignment, d is of type Data */

The "*>" operator have the same properties as the `*' in C, i.e. "v1*>" has the same meaning as "*v1" in C. To make the syntax a bit easier there is a possibility to let the SDL Analyzer implicitly insert the "*>" in the expressions where it is needed. The example above would then become:

task v1!a := 1;
task i := v2!b;
   /* integer assignment, i is integer variable */
task d := v2;  
   /* struct level assignment, d is of type Data */

which is a bit easier to read. More details about the implicit type conversions can be found in Implicit Type Conversions.

Before it is possible to start working with components in the data referenced by the Own pointer, the Own pointer must be initialized with a complete value (default is Null as can be seen in the definition). The Make! operator is a suitable way to initialize a variable. As usual the concrete syntax for Make! is "(. x .)", where x should be replaced by a value of the ItemSort for the current Own pointer.

Example of intializations using the data definitions in the examples above:

dcl v1 Own_Data := (. (. 1, 2 .) .);
task v1 := (. (. 5, 5 .) .);

The inner "(. .)" is for the constructing the struct value and the outer "(. .)" is for the Own make! function. It is, however, possible to avoid the double parentheses as there is an implicit type conversion from a type T to Own(T), by implicitly inserting "(. .)" around a value of type T. So the examples above could (and probably should) be written as

dcl v1 Own_Data := (. 1, 2 .);
task v1 := (. 5, 5 .);

Again, please see Implicit Type Conversions. The other operations available for own pointers, apart from "*>" and make!, are assignment, test for equality, and copy. The assign operator has already been described above. Test for equality (`=' and "/=") does NOT test for pointer equality as two Own pointers cannot be equal. Instead equality is "deep" equality, i.e. the values referred to by the Own pointers are compared.

An implicit copy operator has been inserted for every type. It takes a value and returns a copy of that value. For all types that are not Own pointers or contain Own pointers, this operator is meaningless as it just returns the same value. For Own pointers or for structured values containing Own pointers, the copy function, however, copies the values referenced by the Own pointers.

The ORef Generator

The ORef generator is intended to be used together with the Own generator to provide a way to temporary refer to owned data during some algorithm, without affecting the ownership of the memory. If, for example, Own pointers is used to create a linked list and we would like to write a procedure that calculates the length of the list, then we need a temporary pointer going through the list. If that pointer was a Own pointer the list would be destroyed while we traverse the list, as there may be only one Own pointer referring to the same memory.

Example 38 : Own and ORef

newtype ListElem struct
  Data MyType;
  Next ListOwn;
endnewtype;

newtype ListOwn Own(ListElem)
endnewtype;
newtype ListRef ORef(ListElem)
endnewtype;

procedure ListLength; fpar Head ListRef; 
returns integer;
dcl
  Temp ListRef,
  Len  Integer;
start;
  task Len := 0, Temp := Head;
  again :
  decision Temp /= null;
  (true) :
    task Len := Len+1, Temp := Temp!Next;
    join again;
  (false) :
  enddecision;
  return Len;
endprocedure;

dcl
  MyList ListOwn,
  L integer;

task L := call ListLength(MyList);

Note the use of the ListRef type both in the formal parameter Head and in the local variable Temp. If Head would be of ListOwn type, the variable MyList would be null after the call of ListLength, which is not what we intended. If ListOwn was used as type for the variable Temp, as the statement Temp := Temp!Next would unlink the complete list.

Another example of a typical application of ORef, is to introduce backward pointer in a linked list, to make it doubly linked. If the forward pointers are Own pointers then the backward pointers cannot be Own pointers as then we would have two Own pointers on the same object.

The ORef generator is defined as:

GENERATOR ORef (TYPE Itemsort)
  LITERALS
     Null;
  OPERATORS
    "*>"  : ORef, ItemSort -> ORef;
    "*>"  : ORef -> ItemSort;
    "&"   : ItemSort -> ORef;
    "="   : ORef, ItemSort -> Boolean;
    "="   : ItemSort, ORef -> Boolean;
    "/="  : ORef, ItemSort -> Boolean;
    "/="  : ItemSort, ORef -> Boolean;
  DEFAULT Null;
ENDGENERATOR;

Where "*>" is used for dereferencing and `&' is an address operator.

Run-Time Errors

There are four situations, concerning Own and ORef, that can lead to a run-time error. These situations are:

These problems are all found during simulation and validation, except that if an ORef pointer refers to a data area that is first deallocated and then allocated again, the ORef pointer is no longer invalid.

Examples of run-time error situations assuming the data types in the previous section.

dcl
  L1, L2 ListOwn,
  R1, R2 ListRef,
  I      Integer;

task
  L1 := null,
  R1 := null,
  L1!Data := 1,
    /* ERROR: Dereferencing of Null pointer */
  I := R1!Data;
    /* ERROR: Dereferencing of Null pointer */

task
  L1 := (. 1, null .),
  R1 := L1,
  L1 := null,
  I := R1!Data;
    /* ERROR: Reference to deallocated memory */

task
  L1 := (. 1, null .),
  R1 := L1;
output S(L1) to sender;
task
  I := R1!Data;
    /* ERROR: Reference to memory not owned by
       this process */

task
  L1 := (. 1, null .),
  L1!Next := (. 2, null .),
  L1!Next!Next := L1;
    /* ERROR: Loop of own pointers created */

Implicit Type Conversions

Note:

Implicit type conversions are by default off in the SDL Analyzer. It can be turned on in the Analyze dialog in the Organizer. Implicit type conversions will, however, influence the time needed for semantic analysis. The more complex an expression is, the more effect on time the implicit type conversions will have, as the number of possibilities increases (often exponentially) with the length of the expression.

The purpose of the implicit type conversions is to simplify the use of the Own generator. The code that operate on data structures should be the same if you use a data structure T or if you use a own pointer to T, own(T). The only thing that a user has to think about is if ownership should be passed or if a copy should be made, when passing data to somewhere else.

The implicit conversions never change the type of, for example, an assignment. If there is an assignment:

task R1 := L1;

no implicit type conversions are applied on R1, as that would change the type of the assignment. Type conversions might be applied on L1 in the right hand side, to obtain the correct type. In an assignment:

task Q(a) := ...;

the implicit type conversions might also be applied to the index expression, i.e. to a.

In a test for equality and in similar situations, e.g. in:

L1 = R1

implicit type conversions are first applied to the left expression, i.e. to L1. If that yields a correct interpretation, that one is selected. Otherwise implicit type conversions are tried on the right expression, i.e. to R1.

Assume a type T and a two generator instantiations Own_T = Own(T) and ORef_T = ORef(T). Assume also the variables:

dcl
  t1 T,
  v1 Own_T,
  r1 ORef_T;

Then the following implicit type conversions are possible:

1. Own_T  -> T,       by v1 -> v1*>
2. T      -> Own_T,   by t1 -> (. t1 .)
3. Own_T  -> ORef_T,  by v1 -> demote(v1)
4. ORef_T -> Own_T,   by r1 -> (. r1*> .)
5. T      -> ORef_T,  by t1 -> &t1
6. ORef_T -> T,       by r1 -> r1*>

Type conversions 1 and 6 make it possible to exclude "*>" in component selections. Instead of writing

a*>!b*>(10)*>!c

it is possible to write

a!b(10)!c

This possibility also exists for ordinary Ref pointers.

Type conversion 2 makes it possible to assign an Own pointer a new value of the Own pointer component type. If A is a Own pointer to a struct containing two integers, then it is possible to write:

 A := (. 1, 2 .);

which means the same as

 A := (. (. 1, 2 .) .);

where the inner "(. .)" is the make! function for the struct and the outer "(. .)" is the make! function for the Own pointer.

This possibility also exists for ordinary Ref pointers.

Type conversion 3 makes it possible to assign an ORef pointer to an Own pointer. This is already used in the examples above, but is not directly possible, as an ORef and an Own pointer are two distinct types. The demote operator converts a Own pointer to the corresponding ORef pointer. (Corresponding means the first ORef with the same component type in the same scope unit as the Own pointer type is defined).

Type conversion 4 makes it possible to construct a new Own value, starting from a ORef value. The conversion is performed in two steps, first going from ORef_T to T by applying conversion 6, and then from T to Own_T by applying conversion 2.

Type conversion 5 makes it possible to let a ORef_T pointer refer to a DCL variable by writing:

 task r1 := t1;

which means the same thing as

 task r1 := &t1;

where `&' is the address operator (as in C).


http://www.ibm.com/rational
Contents Index Previous Next