Note: Descriptions are shown in the official language in which they were submitted.
CA9-94-005 1 21~ ~ 4 6 3
MECHANISM AND MET~OD FOR ALLOCATING ACTIVE
OBJECTS ON A PROCESSOR STACK
The present invention is directed to providing a basis for
issuing concurrent processing threads in a sequential object
oriented processing environment such as C++ where data
objects and data arrays are allocated from an operating
program on the same dynamic memory stack.
As discussed in Canadian Patent Application No. 2,097,542,
filed June 1, 1993, entitled "Linkage for Accessing Data
Objects in the Stack", two major types of object-oriented
language technologies have arisen since first introduction
of the concept through Simula1, pure object-oriented
languages such as SmallTalk2 developed to embrace the
object-oriented approach, and compiled object-oriented
languages such as C++3 that aim to optimize run-time in
object-oriented technology. The present invention is
directed to such compiled object-oriented language
technology as C+~.
Object oriente~ technology, in general, approaches the
computer simulated modelling of real-world processes and
modularization for building complex computer systems, by
focusing on representing physical objects and the
relationships between them, rather than on abstract
procedures as in conventional programming.
The computer simulated "objects" in object-oriented
technology are defined and maintained independently of each
other, the definition of an object including its "methods"
(what procedures or operations the object is capable of
performing) and its "variables" (its attributes, the values
Simula is a modular programming language developed in the late 1960's
at the Norwegian Computing Center.
SmallTalk was developed in the early 1970's at Xerox PARC (Palo Alto
Research Center), California, as a complete object-oriented language.
C++ was developed in the earl.y 1980's at AT&T's Bell Laboratories as a
CA9-94-005 2 21~ 3
of which can change over time). This independence in
definition or existence is felt to be more consistent with
the way in which humans view the world, and provides a
natural way of breaking down a problem to be solved, thus
facilitating the construction of very complex computer
systems and working models based on numerous components.
In object-oriented systems, objects are defined through
class definitions. A "class" is a template that defines the
methods and variables to be included in a particular type of
object. Classes can be defined in terms of other classes,
that is, the characteristics (methods and/or variables) of a
class (a "subclass") can be "inherited" from a superior,
more generalized class (a "base" class).
In addition to the methods and variables they inherit,
subclasses define their own methods and variables and this
may include characteristics permitting the override of
inherited characteristics, although the implementation of
such derived classes is visible only within the class to
prevent contamination of other class implementations.
An abstract class is a base class with no object members or
"instances", the sole purpose of which is to organize a
class hierarchy or define methods or variables that will
apply to a lower level inherited class.
Since inherited methods and variables can be more narrowly
defined, or even redefined in a derived class, base classes
are often described as "polymorphic", that is, having the
ability to hide different implementations behind a common
interface, simplifying the communication among objects.
Objects defined through this technology can be highly
specialized and can fit within a complex system of related,
but not identical, objects, and class hierarchies can
encompass many levels.
preprocessor enhancement, adding object-oriented features to the already
existing C language.
CA9-94-005 3
In many computer systems, static storage meçl~ "~ known as "class libraries" serve as repositories
for the class hierarchy and data, and when a class is called through a processor, channel the
appl op. iate data to the run-time memory.
Both the C l~ngll~ge and its object-oriented enhancement C++ (as well as other object-oriented
languages) require the allocation of dynamic storage from the operating system at run-time. This run-
time storage is allocated as two separate areas known as the "heap" and the "stack". Current data
objects and info- ...alion associated with only one activation within the compiled program are allocated
to the stack for the life of the particular activation. Objects cont~ining data that could be accessed
over more than one activation must be heap allocated or static for the duration of use during run-time.
Classes in C++ can fall into either data type, and are allocated in dynamic memory accordingly.
Because any data objects in a derived class declared on the stack are visible only from within the
object to which the stack belongs, a problem arises where a class library defines a base class that
needs to perform a task abstraction such as some action directly on an active object of a derived class
beyond the first level of inheritance.
In order to implement the direct action, the base class must be able to locate and access the active
object's variables declared on the stack. Where the base class is not itself called from the stack, the
only way for it to jump to the proper location in the stack is to locate the address or return address
stored in the first data object called after object creation, in order to return to the ori~in~tinf~ point
in the executing program, and means for pel fol--ling this linkage is the subject matter of C~n~ n
patent application no. 2,097,542 referred to above.
However, where the base class is allocated on the stack, the correct stack frame associated with the
most derived constructor must be located in order to send the original
A
3 ~ ~
CA9-94-005 4
thread back to the correct point in the original or calling program, and this is the subject of the
present invention.
In the presence of an arbitrary number of levels of inheritance between the base class and the derived
class called from the stack, the base class has no means of directly referencing the derived class
containing the return address and directly acce~in~ the location of the active data object in the stack.
One application in which this problem may arise is that of effecting concurrent threads of control
discussed in Canadian Patent Application No. 2,097,541, filed June 1, 1993, entitled "Controlling
Method Invocation Sequence through Virtual Functions in an Object-Oriented Class Library".
C++ is an inherently sequential object-oriented l~ng~lage without any provision for concurrent
processing of independent applications or threads of control in an application. Yet as concurrency
optimizes run-time, it would be a desirable feature in such a l~n~lage.
One approach to providing concurrency has been through the virtual class mechanism, adding a
special "Task" class in the class library whose function is to implement concurrent processing.
Class libraries such as Doeppner4, implement an "active object" abstraction based on a four-class
"tasking" package. In these types of applications, it is the job of the Task class to spin off an
independent thread of control for instances of any class for which the Task class is a base class.
When the new thread of control has been generated, the Task class directs the original thread to jump
to the point in the program (called the origin~ting point) which
Doeppner, T., Gebele, A., "C++ on a Parallel Machine", Technical Report
CS-87-26, Brown University Department of Computer Science, November 1987.
:;
CA9-94-005 5 2 1 1 5 ~ ~ 3
immediately follows the invocation of the constructors,
whlle the other thread continues executing the original task
invoked in the program.
Other proposals for specific abstract "task like" classes
are for directed purposes, as in U.S. Patent No. 5,142,674 -
Barker et al, relating to the use of an abstract class in an
object-oriented document or local library for constructing
application dependent indices to an object-oriented document
database for random object retrieval.
In the example of Doeppner, the problem of the Task class
not knowing where to look for for the address of the
originating point in the program is dealt with by limiting
the levels of inheritance to a known number. Similarly, in
Barker, the database parameters are known from the outset.
Other prior solution proposed to deal with this problem is
to abandon the use of a class library and to use an enhanced
compiler or language extensions, as described in more detail
in the above referenced copending Canadian application no.
2,097,541.
In the above referenced copending Canadian application no.
2,097,542, a solution was proposed for manipulating the
processor stack for allocation of active objects on the
dynamic memory heap. The present invention is directed to
the problem of manipulating the processor stack in the
situation where the active object is allocated on the
processor stack as well.
It is therefore an object of the present invention to
provide, in compiled object-oriented technologies such as
C~+ that use a standard non-extended compiler, a means for
relating object structures constructed on the stack with
stack processing in a consistent mannerj without regard to
the number of levels of class inheritance.
CS-87-26, Brown University Department of Computer Science, Nove~ber
1987.
I j
~ ~ " '""' ' ~
CA9-94-005 6 211~ 4 6 3
It is also an object of the present invention to provide a
means for racognising in which area of dynamic memory the
active object class structure is allocated in order to
~ ., , ~, . . .
correctly implement the method of the present invention or
that of copending Canadian application no. 2,097,542.
Where it has been determined that objects are constructed on
the stack, the present invention provides a method for
following the back chain of pointers along the stack frame
from the base constructor to the most derived constructor.
Accordingly, in one aspect, in a compiled object-oriented
language operating system having a processor with dynamic
memory including a stack and a heap, an operating program,
at least one activation record allocated on the stack for
said operating program, and means for allocating and
subsequently constructing a data object derived from a class
hierarchy called from the operating program in dynamic
memory, a mechanism for locating the original activation
record from a pre-selected base class for the data object
that includes means for generating an index to the original
activation record on allocation of the data object in
dynamic memory and means for accessing the index on
construction of the pre-selected base class in dynamic
memory.
Preferably, the means for accessing the index include means
for locating allocation and construction of the data object
in dynamic memory on the heap or on the stack, and the means
for accessing the index include means for locating
allocation and construction of the data object in one of
said stack frames constructed on the stack and means for
accessing a link record associated with the stack frame of
the data object through link records for later constructed
stack frames.
According to another aspect of the invention, in a compiled
C++ operating system having a program adapted to operate in
said system, a processor having dynamic memory including a
stack adapted to allocate at least one activation record to
said program for execution of an activation and a heap, and
CA9-94-005 7 ~ 4 ~ 3
having mean~ for allocating storage in dynamic memory to a
data object in a class hierarchy called in said program, a
mechanism for linking data objects allocated in said dynamic
storage with said at least one activation record is provided
that includes means for generating an index to said at least
one activation record in a data object on allocation of the
data object in dynamic memory and means for accessing the
index on construction in dynamic memory of a pre-selected
base class for the data object.
Preferably, the means for generating an index are the
allocation of link records on construction of multiple stack
frames on the stack, and the means for accessing the index
are means for accessing a link record associated with the
stack frame of the data object through link records for
later constructed stack frames.
The present invention also provides a method for linking a
base class in a class hierarchy constructed on a memory
stack with an activation record also allocated on the stack
for a program calling a derived data object in the class
hierarchy and operating in a compiled object-oriented
computer system. The metllod is the computer implemented
steps of allocating the derived data object in dynamic
memory as a data object allocation, determining the
allocation location of the data object on the heap or the
stack, generating an index accessible by the data object
allocation to the activation record, accessing the index on
construction of the base class in dynamic memory.
Embodiments of the invention will now be described in detail
in association with the accompanying drawings, in which:
Figure 1 is a flow diagram outlining the computer
implemented steps in accessing a stack allocated object from
an active object according to the invention; and
Figure 2 is a schematic representation of a stack allocated
object, according to the method of the invention illustrated
. ,~ . ,, . . " . . .
in Figure 1.
CA9-94-005 8 21~63
When an activation record on the stack issues a call to a
data object in a class library in an object-oriented
environment such as C++, the called data object and all its
superior or base classes are constructed or allocated in
dynamic memory in the following manner. Constructors in
each class in the class hierarchy point to and call (invoke)
the base class from which the object variables for the class
are derived, so that every time a data object is created, a
series of constructors is invoked for all classes in the
class hierarchy.
In normal implementations of constructor invocation in C++,
sufficient space for the newly allocated object, including
all its levels of inheritance in its class hierarchy, is
allocated, and its constructor is called. This will be the
constructor defined for the class having the deepest level
of inheritance (eg., level A).
C++ specifies that the class constructors for base classes
be executed before derived class constructors are executed.
Thus, before its own execution, the constructor at the
deepest level of inheritance (level A) will immediately call
the constructor for its base class (level B) at the second
deepest level of inheritance. The called base class (level
B) will in turn immediately call its own base constructor
(level C), and so on, until the constructor for the highest
abstract class (level T) is called. Once this constructor
for the highest abstract class (level T) finishes and
returns, the constructor that called it (level C or higher)
will perform its construction duties (which may involve
calling constructors for member objects), and will then
return to the constructor (level B) that called it. This
process continues until the first constructor (level A) is
allowed to do its construction. This process is referred to
as the invocation chain.
The invocation chain includes the creation of a record for
each base class of the class that called it to permit a
return to the calling class on completion of construction of
the called base class. However, this inter-class record is
restricted to a single level of inheritance; there is no
:~
CA9-94-005 9 211 ~ 4 6 3
mechanism for a base class to determine which class in the
hierarchy initiated the invocation chain and actually
contains a record of the location on the stack of the active
object. Effectively, this method of invocation prevents the
direct interaction between a base class and data objects
allocated on the stack for a derived class.
As discussed above, a problem arises when the class library
defines a base class in the hierarchy with a separate "task"
to perform in relation to the activation ongoing in the
stack outside of the invocation chain, such as performing
some action on a fully constructed data object that is not
immediately below it in the class hierarchy.
On completing construction for its separate "task", the
separate T class constructor in the base class must access
the active record on the stack in order to execute its
"task". In other words, the T class constructor must be
able to jump back to the originating point in the program
for executing its "task".
However, as discussed above, the task constructor has no
record of the originating point in the program nor any
return address for accessing the activation record in the
stack. This information is contained in the constructor for
the derived class called by the program from the stack.
If the number of levels of inheritance from the T level
class to the called derived class is arbitrary or unknown,
and if it is further unknown which levels constructed on the
heap define constructors and which do not (for tracing down
through the invocation chain), then the T class constructor
does not know where in the class hierarchy to look for the
address of the originating point in the program, and is
therefore unable to access the current activation record in
the stack.
As illustrated in Figure 2, activation records are created
on the stack 30 through allocation in stack frames 32. One
way in which this normally occurs is when a data object is
declared to be "active", that is, implemented in a operating
CA9-94-005 10 211~463
program. Activation records are added to the stack (the
stack is said to "grow") as needed to provide sufficient
short-term dynamic storage space to perform the calculations
and operations in implementing the activation. Stacks can
grow either up or down, depending on the system
specifications. In the present invention implemented in a
C++ programming environment, the stack is depicted as
growing up.
As the invocation chain is being processed, activation
records are allocated on the stack for each class
constructor, and a link area or record 34 is inserted
between each stack frame containing a variable pointing to
the previous stack frame. In some environments, the link
area 34 may consist of only a single item, the location or
address of the previous stack frame.
Allocation of the data object on the stack does not remove
the problem of locating the stack frame associated with the
most derived constructor; the T class constructor must still
locate the appropriate return address in the link record of
that stack frame in order to send the originating thread
back to the correct point in the creating or calling program
executing on the stack.
For a stack allocated data object, the technique of
manipulating the first register of word of the allocated
object discussed in copending Canadian application no.
2,097,542 is not used. Instead, by knowing that the object
is being allocated on the stack, the address of the object
(which i5 always allocated before the constructors are
called) can be accessed for locating the stack frame.
Therefore, as illustrated in Figure 1, after issuance of a
call to construct an object for an independent thread (block
1), the first step is to discover in the Task constructor
whether the construction is happening on an object based on
the stack or based on the heap. This is determined by
examining the address of the register in the constructor
containing the object pointer (block 2). In some computer
systems, a predetermined segment is associated with heap
CA9-94-005 11 211~ 4 6 3
based objects, and the determination of whether the object
is heap-based becomes a simple matter of examining whether
the address falls within the specified range. In other
multithreaded systems, the determination can be made by
examining the control structure associated with the thread
that is executing the calling program. This control
structure will contain, among other things, the address and
size (the parameters in dynamic memory) of the stack
allocation associated with the thread, and from this, the
Task constructor can determine in a straightforward manner
if the address of the pointer to the data object is located
within these stack parameters.
If it is determined that the object is being constructed on
the heap, then the method set forth in Canadian application
no. 2,097,542 is implemented by the computer (block 4).
However if the determination is made that the object is
being constructed on the stack, then the invention provides
that the chain of pointers (or indexes in consecutive stack
frames) is followed to lead to the correct stack frame
(blocks 6 to 16).
The structure of the stack followi.ng allocation and
construction of an "active" data object is illustrated in
Figure 2. The stack 30 is now made up of multiple stack
frames 32, each of which has an associated link record 34
that contains a pointer or a variable pointing to the
beginning of the immediately preceding stack frame. In the
present invention, the object is to locate the data object
allocation 36 somewhere on the stack, in order to spin off a
concurrent (independent) thread and then return the original
thread to resume processing of the calling program.
., . --
In more detail, the link record at the top of the stack 34'
(in a system where the stack grows upward) is located and is
referenced (block 6 in Figure 1). This will in turn contain
a pointer 38 giving access to the previous stack frame
(block 8 to 10), and this "backchain" of pointers can be
followed through the stack structure. As each new
(previous) stack frame is referenced, the address of the
last dereferenced stack frame is retained (block 12), and
CA9-94-005 12 2 ~1~ 4 6 3
the address of the referenced stack frame is compared with
the address of the object (block 14). This procedure is
repeated (simply discarding the address of the dereferenced
stack frame on each repetition before referencing the next
previous stack frame - block 18) until a pointer is located,
the address of which is numerically smaller than the address
of the most derived constructor sought. The link record
that contains this address is the link record associated
with the calling program.
Using the retained address (from block 12~, the last
dereferenced stack frame is referenced once again (block
20), and the object under construction is located in it
(block 22). A separate thread of control can then be
successfully spun off the located object, and the original
thread returned to the creating or calling program to resume
processing (blocks 24 and ~6).
In following the method of the invention relating to stack
allocated objects, stack-based arrays of active objects can
also be created. This is possible because in C++, for
example, the most derived default constructor for each
element of a stack-based array will be called. In each
case, the pointer chasing technique of the present invention
will be applied via the base constructor, and in each case a
new thread will be created and the original thread returned
to the creating program. For all but the last element in
the array, returning the original thread will simply cause
construction to begin on the next thread. (Following
construction of the thread for the last element in the array
will cause the original progr~m to resume normal processing,
as in the case of a single data element.)
The present invention has been particularly shown and
described in relation to the hardware recognized memory
mechanisms and operating system implementations of the C++
programming language. However, those skilled in the art
will appreciate obvious modifications to the proposed
invention for implementation in other compiled
object-oriented language environments, and such
CA9-94-005 13 211~ 4 6 3
modifications are intended to be covered by the appended
claims.
