![]() |
![]() |
![]() |
![]() |
![]() |
Allocating Dynamic Memory
Introduction
This section deals with the allocation and deallocation of dynamic memory.
This information is only valid when the Master Library is used. The OS integrations might have different strategies for memory allocation.
Information is provided about the following topics:
- Explanation about how dynamic memory is allocated and reused (deallocation and avail lists)
- How to estimate the total need of dynamic memory for an application.
Dynamic memory is used for a number of objects in a run-time model for applications generated by the Cadvanced/Cbasic SDL to C Compiler. These objects are:
- Process instances
- Signal and timer instances
- Procedure instances
- Charstring, Octet_string, Bit_string, and Object_identifer variables and variables of String, Bag, general Array, and general Powerset types.
- Variables of other user-defined data types, where the user has decided to use dynamic memory.
To help to estimate the need for memory for an application we will give information about the size of these objects and about how many of the objects are created. The size information given is true for generated applications, that is, ones that do not, for example, contain the monitor. The type definitions given are stripped of components that will not be part of an application. The full definitions may be found in the file scttypes.h.
Processes
Each process instance is represented by two structs that will be allocated on the heap. In scttypes.h the type xLocalPIdRec is defined and in generated code yVDef_ProcessName structs are defined:
typedef struct {xPrsNode PrsP;} xLocalPIdRec;typedef struct {xPrsNode Pre;xPrsNode Suc;int RestartAddress;xPrdNode ActivePrd;void (*RestartPAD) (xPrsNode VarP);#ifndef XNOUSEOFSERVICExSrvNode ActiveSrv;xSrvNode SrvList;#endifxPrsNode NextPrs;SDL_PId Self;xPrsIdNode NameNode;int State;xSignalNode Signal;xInputPortRec InputPort;SDL_PId Parent;SDL_PId Offspring;int BlockInstNumber;xSignalIdNode pREPLY_Waited_For;xSignalNode pREPLY_Signal;/* variables and formal parameters in theprocess */} yVDef_ProcessName;To calculate the size of the structs above it is necessary to know more about the components in the structs. The types xPrsNode, xPrdNode, xSignalNode, xPrsIdNode, xStateIdNode, and xSignalIdNode are all pointers, while SDL_PId is a struct containing an int and a pointer. The xInputPortRec is a struct with two pointers and one int.
This means that it is possible to calculate the size of the xLocalPIdRec and the xPrsRec struct using the following formulas, if the compiler does not use any strange alignment rules:
The size of xPrsRec can be reduced by 2 x sizeof (address) if the code is compiled with the XNOUSEOFSERVICE flag. Then, of course, the SDL concept service cannot be used. The size of yVDef_ProcessName is the size of the xPrsRec plus the size of the variables and parameters in the process. Any overhead introduced by the C system should also be added. The size of the formal parameter and variables is of course dependent on the declarations in the process. The translation rules for SDL types, both predefined and user defined, can be found in The Cadvanced/Cbasic SDL to C Compiler.
For each process instance set in the system the following number of structs of a different kind will be allocated:
- There will be one xLocalPIdRec for each process instance created. These structs will not be reused, as they serve as identification of process instances that have existed (see also optimizations below).
- There will be as many yVDef_ProcessName structs as the maximum concurrently executing process instances of the process instance set (maximum during the complete execution of the program).
The yVDef_ProcessName structs are reused by having an avail list where this struct is placed when the process instance it represents perform a stop action. There is one avail list for each process type. When a process instance should be created, the runtime library first looks at the avail list and reuses an item from the list. Only if the avail list is empty new memory is allocated.
Compilation switch XPRSOPT
If the compilation switch XPRSOPT is defined then:
- xLocalPIdRecs are reused together with the xPrsRecs.
- xLocalPIdRecs contain an additional int component.
Services
Services are handled very similar to processes. The following struct type are allocated for each service instance.
typedef struct xSrvStruct {xSrvNode NextSrv;xPrsNode ContainerPrs;int RestartAddress;xPrdNode ActivePrd;void (*RestartPAD) (xPrsNode VarP);xSrvIdNode NameNode;int State;XSIGTYPE pREPLY_Waited_For;xSignalNode pREPLY_Signal;} xSrvRec;The size of yVDef_ServiceName is the size of the xSrvRec plus the size of the variables in the service. yVDef_ServiceName struct are reused in the same way as for processes (see previous section).
Signals
Signals are handled in much the same way as processes. A signal instance is represented by one struct (in generated code generated).
typedef struct {xSignalNode Pre;xSignalNode Suc;int Prio;SDL_PId Receiver;SDL_PId Sender;xIdNode NameNode;/* Signal parameters */} yPDef_SignalName;This struct type contains one component for each signal parameter. The component types will be the translated version of the SDL types of the parameters.
This means that it is possible can calculate the size of a xSignalRec, which is the same as a struct for a signal without parameters, using the following formula:
The size of a yPDef_SignalName struct is thus equal to the size of the xSignalRec plus the size of the parameters. The translation rules for SDL types, both the predefined and user defined, can be found in The Cadvanced/Cbasic SDL to C Compiler.
For each signal type in the system the following number of data areas will be allocated:
- There will be as many yPDef_SignalName struct as the maximum number of signals (during the complete execution of the program) of the signal type that are sent but not yet received in an input operation.
The yPDef_SignalName struct is reused by having an avail list, where the struct is placed when the signal instance they represent is received. The exact point where the signal instance is returned to the avail list is when the transition caused by the signal instance is ended by a nextstate or stop action. There is one avail list for each signal type. When a signal instance should be created, for example during an output operation, the runtime library first looks at the avail list and reuses an item from this list. Only if the avail list is empty new memory is allocated.
There is one common avail list for all signals without parameters.
Timers
The memory needed for timers can be calculated in the same way as for signals with one exception, each timer contains an extra SDL_Time component, i.e. two extra 32-bit integers.
Procedures
Procedures and processes have much in common in terms of memory allocation. A procedure is, during the time it exists from call to return, represented by a struct; the yVDef_ProcedureName.
typedef struct {xPrdIdNode NameNode;xPrdNode StaticFather;xPrdNode DynamicFather;int RestartAddress;int (*RestartPRD) (xPrsNode VarP);xSignalNode pREPLY_Signal;int State;/* Formal parameters and variables */} yVDef_ProcedureName;The struct type contains one component for each formal parameter or variable. The component types will be the translated version of the SDL types of the parameters, except for an IN/OUT parameter which is represented as an address.
The size of the xPrdRec struct (which is the same as a procedure without variables and formal parameters) can be calculated using the following formula:
The size of a yVDef_ProcedureName struct is the size of the xPrdRec plus the size of the formal parameter and variables defined in the procedure. The translation rules for SDL types, both the predefined and user defined can be found in The Cadvanced/Cbasic SDL to C Compiler.
For each type of procedure in the system the following number of data areas will be allocated:
- There will be as many yVDef_ProcedureName structs as the maximum number of concurrent calls (during the complete execution of the program) of the procedure. Concurrent calls occur both when a procedure calls itself recursively within one process instance, and when several process instances of the same process type calls the same procedure during overlapping times.
The yVDef_ProcedureName struct is reused by having an avail list, where this two struct is placed when the procedure instance executes a return action. There is one avail list for each procedure type. When a procedure instance should be created, that is, at a call operation, the runtime library first looks at the avail list and reuses an item in the list. Only if the avail list is empty new memory is allocated.
Data types
The predefined SDL type charstring is implemented as char * in C and thus requires dynamic memory allocation. The predefined data types Bit_string, Octet_string, and Object_identifier are also implemented using dynamic memory.
The implementation of the SDL sorts Charstring, Bit_string, Octet_string, and Object_identifier is both flexible in length and all memory can be reused.
The mechanism used to release unused memory is to call the xFree function in the file sctos.c, which uses the standard function free to release the memory.
Charstrings, Bit_strings, Octet_strings, and Object_identifiers are also handled correctly if they are part of structs or arrays. When, for example, a new value is given to a struct having a charstring component, the old charstring value will be released. For all structured types containing any of these types there will also be a Free function that is utilized to release all dynamic memory in the structured variable.
Functions for Allocation and Deallocation
The allocation and deallocation of memory is handled by the functions xAlloc and xFree in the file sctos.c. The functions in this file are used for the adoption of the generated applications to the operating system or hardware. The sctos.c file is described in detail in The sctos.c File.
In generated code and in the run-time library the functions xAlloc and xFree are used in each situation where memory is needed or can be released. xAlloc receives as parameter a requested size in bytes and returns the address to a data area of the requested size. All bytes in the data area are set to zero. xFree takes the address of a pointer and returns the data area referenced by the pointer to the pool of free memory. It also sets the pointer to 0.
The xAlloc and xFree functions are usually implemented using some version of the C standard functions for allocation (malloc, calloc) and deallocation (free). Other implementations are of course possible as long as the interface described in the previous section is fulfilled. In a micro controller, for example, it is probably necessary to handle allocation and deallocation directly towards the physical memory.
To prevent memory fragmentation we have used our own avail lists in almost all circumstances. Memory fragmentation is phenomena occurring when a program allocates and de-allocates data areas (of different sizes) in some "random" order. Then small pieces of memory here and there are lost, since their sizes are to small to fit an allocation request. This can lead to a slowly increasing demand for memory for the application.
Note that deallocation of memory is only used for data types. More specific it is used for variables of type:
- Charstring
- Octet_string
- Bit_string
- Object_identifier
- Types created by String (not #STRING) and Bag generator
- Types created by Array generator, if the index type is such that an array in C cannot be used. (General array)
- Types created by Powerset generator, if the component type has the has property as for the index type in general arrays.
This means that if variables of the above mentioned types are not used and the user has not introduced the need for deallocation of memory himself, no memory deallocation will occur. In this case it is of course unnecessary to implement the xFree function.
It is easy to trace the need for dynamic memory. As all memory allocation is carried out through the xAlloc function and this function is available in source code (in sctos.c), it is only necessary to introduce whatever count statements or printout statements that are appropriate.
http://www.ibm.com/rational |
![]() |
![]() |
![]() |
![]() |