# Dynamic memory allocation

## Contents

- Overview
- Maximum data size in a procedure
- 32-bit addressing
- Overview of memory usage
- The heap allocator
- The heap structure
- Growing and shrinking the heap
- Lost cells
- Internal fragmentation
- The OPL runtime interpreter and the heap
- Warning — peeking/poking the cell
- Reasons for using the heap allocator
- Using the heap allocator
- Example using the allocator

### Overview

For each running OPL program (or process) the operating system automatically allocates memory. There are no built-in memory limits and a module or application can use as much of the available memory as it requires.

### Maximum data size in a procedure

Although there is no built-in limit to the total amount of data in an OPL program, it is still not possible to declare variables in a procedure that use in total more than 65516 bytes. This allows the largest integer array in a procedure to have 32757 elements. This number decreases for any other variables, externals or for procedures called from the given procedure, as they all consume some of the procedure’s data space.

### 32-bit addressing

As described above, memory addresses outside the 64K address space need to be stored in long integers. Thus all keywords which support addresses take and return long integers. Note also that where `#` is used to specify the address of a variable that is listed in the syntax using `var`, the address is a long integer, so you would use `#address&`. See the ‘I/O functions and commands’ section above.

### Overview of memory usage

The actual memory used by an OPL program depends on the requirements of the process and is automatically grown or shrunk as necessary.

An OPL process contains several separate memory areas, but the only one of significant interest to the OPL programmer is the OPL heap, used to contain the OPL variables and dynamically allocated memory cells. The heaps of different processes are entirely separate - you need only concern yourself with the heap used in your own process.

### The heap allocator

The heap allocator keywords are used to allocate, resize and free variable length memory cells from the OPL heap. Cells typically range in size from tens of bytes to a few kilobytes. Allocated cells are referenced directly by their address; they do not move to compact free space left by freed cells.

Heap allocator keywords are:

- `ALLOC` allocates a cell of specified size, returning its address.
- `FREEALLOC` frees a previously allocated cell, which is returned to the heap.
- `REALLOC` changes the size of a cell, returning its new address.
- `ADJUSTALLOC` opens or closes a gap in the middle of a cell (useful for insertion or deletion of cell content), changing the size of the cell as appropriate.
- `LENALLOC` returns the size of a cell.

### The heap structure

Initially, the heap consists of a single free cell. After a number of calls to allocate and free cells, the heap typically consists of ranges of adjacent allocated cells separated by single free cells (which are linked). If a cell being freed is next to another free cell the two cells are automatically joined to make a single cell to prevent the free cell linked list from growing unnecessarily.

Writing beyond the end of a cell will corrupt the heap’s integrity. Such errors are difficult to debug because there is no immediate effect - the corruption is a "time bomb". It will eventually be detected, resulting in the process exiting prematurely by a subsequent allocator call such as `FREEALLOC`.

### Growing and shrinking the heap

The heap is not fixed in size. The operating system can grow the heap to satisfy allocation requests or shrink it to release memory back to the system.

Allocation of cells is based on "walking" the free space list to find the first free cell that is big enough to satisfy the request. If no free cell is big enough, the operating system will attempt to grow the data segment to add more free space at the end of the heap.

If there is no memory in the system to accommodate growth, the allocate request fails. There are few circumstances when an allocate request can be assumed to succeed and calls to `ALLOC`, `REALLOC` and `ADJUSTALLOC` should have error recovery code to handle a failure to allocate.

### Lost cells

There are cases in which programs allocate a sequence of cells which must either exist as a whole or not at all. If during the allocate sequence one of the later allocations fails, the previously allocated cells must be freed. If this is not done, the heap will contain unreferenced cells that consume memory to no purpose.

When designing multi-cell sequences of this kind, you should be mindful of the recovery code that must be written to free partially built multi-cell structures. The fewer the cells in such a structure, the simpler the recovery code is.

### Internal fragmentation

The free space in the heap is normally fragmented to some extent; the largest cell that can be allocated is substantially smaller than the total free space. Excessive fragmentation, where the free space is distributed over a large number of cells - and where, by implication, many of the free cells are small - should be avoided because it results in inefficient use of memory and reduces the speed with which cells are allocated and freed.

Practical design hints for limiting internal fragmentation are:

- Avoid using the heap for small, highly transient data structures for which ordinary variables are adequate. High frequency cycling through allocate and free pairs, "churns" the heap and leads to a long free space list.
- When you have a large number of variable length data structures - particularly when they are frequently resized, "granularise" them (i.e. round the allocation up to a multiple of some reasonable value) so that you decrease the chance of leaving small, unusable free space cells.

Although a small number of gaps are not too serious and should eventually disappear in most cases anyway, the new heap allocating keywords provide ample opportunity to fragment the heap. Provided that you create and free cells in a careful and structured way, where any task needing the allocator frees them tidily on completion, there should not be a problem.

### The OPL runtime interpreter and the heap

The OPL runtime interpreter uses two separate heaps: one for process management and one for user variables and allocated cells. `LOADM`, `CREATE`, `OPEN`, etc. use the process management heap. This ensures that the use of these keywords will not cause fragmentation. It is therefore not necessary for you to understand the interpreter’s use of the heap.

### Warning — peeking/poking the cell

Using the allocator is by no means simple in OPL since the data in an allocated cell usually has to be read or written in OPL using the `PEEK` and `POKE` set of keywords which are intrinsically subject to programming error. OPL does not provide good support for handling pointers (variables containing addresses), which are basic to heap usage, nor for complicated data structures, so that it is all too easy to make simple programming errors that have disastrous effects.

For these reasons, you are recommended to use the heap accessing keywords only when strictly necessary (which should not be very often) and to take extreme care when you do use them. On the other hand, for programmers with previous experience of dynamic memory allocation, the heap allocation keywords will often prove most useful.

### Reasons for using the heap allocator

A few common instances where the allocator might be used are:

- when the amount of data to be stored is variable or cannot be determined at the time of writing the program. Without using the allocator, you would have to declare a large array to hold the data always even when it turns out that only a few bytes are needed in a particular case. Using the allocator allows you to grow the cell containing your data as and when required.
- the amount of data may be specified in a file or by the user of the program. Once again, you would need to declare a possibly unnecessarily large array to cope with all allowed cases.
- a system of library procedures might use a common cell, usually called a control block, to store common data. You could have one procedure creating the cell and initialising data in it, other procedures in the system could be passed the address of the cell, using and possibly updating the data in it, and finally a further procedure could free the cell.
- This concept will be familiar to you if you have used handles for the I/O keywords, where the handle references a cell used internally by the I/O system.
- If you did not use the allocator in this case, you would probably need to declare a global array in the procedure calling the library procedures, with the disadvantages that the name and size of the array would need to be fixed for all time even when a better alternative mechanism has been devised for the library code with different data requirements.
- ADJUSTALLOC allows you to insert or remove data at the start or in the middle of data that has previously been set up. With an array, you would need to copy each element to the next or previous element to make or close a gap.

### Using the heap allocator

#### ALLOC and associated heap keywords

`ALLOC`, `REALLOC` and `ADJUSTALLOC` allocate cells that have lengths that are the smallest multiple of four greater than the size requested. All of these raise errors if the cell address argument is not in the range known by the heap. The same address checking is done for peeking and poking.

`ALLOC`, `REALLOC` and `ADJUSTALLOC` return a long integer value, so that a request can be made to allocate a cell of any length within memory constraints.

#### Allocating a cell

Use `pcell&=ALLOC(size&)` to allocate a cell on the heap of a specified size returning the pointer to the cell or zero if there is not enough memory. The new cell is uninitialised — you cannot assume that it is zeroed.

#### Freeing an allocated cell

Use `FREEALLOC pcell&` to free a previously allocated cell at `pcell&` as returned, for example, by ALLOC. Does nothing if `pcell&` is zero.

#### Changing a cell’s size

Use `pcelln&=REALLOC(pcell&,size&)` to change the size of a previously allocated cell at address `pcell&` to `size&`, returning the new cell address or zero if there is not enough memory. If out of memory, the old cell at `pcell&` is left as it was.

If successful, `pcelln&` will not be the same as `pcell&` on return only if the size increases and there is no free cell following the cell being grown which is large enough to accommodate the extra amount.

#### Inserting or deleting data in cell

Use `pcelln&=ADJUSTALLOC(pcell&,offset&,amount&)` to open or close a gap at `offset&` within the allocated cell `pcell&` returning the new cell address or zero if there is not enough memory. `offset&` is 0 for the first byte in the cell. Opens a gap if `amount&` is positive and closes it if negative. The data in the cell is automatically copied to the new position.

If successful, `pcelln&` will not be the same as `pcell&` on return only if `amount&` is positive and there is no free cell following the cell being adjusted which is large enough to accommodate the extra amount.

#### Finding out the cell length

Use `len&=LENALLOC(pcell&)` to get the length of the previously allocated cell at `pcell&`.

### Example using the allocator

This example illustrates the careful error checking which is essential when using the allocator. `RAISE` is used to jump to the error recovery code.

If you cannot understand this example it would be wise to avoid using the allocator altogether.

        LOCAL pcell&                         REM pointer to cell
        LOCAL pcelln&                      REM new pointer to cell
        LOCAL p&                         REM general pointer
        LOCAL n%                         REM general integer
        ONERR e1
        pcell&=ALLOC(2+2*8)             REM holds an integer and 2
                                            REM 8-byte floats initially
        IF pcell&=0
              RAISE -10                   REM out of memory; go to e1::
        ENDIF
        POKEW pcell&,2                      REM store integer 2 at start of cell
                                            REM i.e. no. of floats
        POKEF UADD(pcell&,2),2.72               REM store float 2.72
        POKEF UADD(pcell&,10),3.14              REM store float 3.14 ...
        pcelln&=REALLOC(pcell&,2+3*8)       REM space for 3rd float
        IF pcelln&=0
              RAISE -10                           REM out of memory
        ENDIF
        pcell&=pcelln&                          REM use new cell address
        n%=PEEKW(pcell&)                         REM no. of floats in cell
        POKEF UADD(pcell&,2+n%*8),1.0       REM 1.0 after 3.14
        POKEW pcell&,n%+1                   REM one more float in cell ...
        pcelln&=ADJUSTALLOC(pcell&,2,8)       REM open gap before 2.72
        IF pcelln&=0
              RAISE -10                         REM out of memory
        ENDIF
        pcell&=pcelln&                        REM use new cell address
        POKEF UADD(pcell&,2),1.0             REM store 1.0 before 2.72
        POKEW pcell&,4                        REM 4 floats in cell now ...
        p&=UADD(pcell&,LENALLOC(pcell&))       REM byte after cell end
        p&=USUB(p&,8)                         REM address of final float
        POKEF p&,90000.1                        REM overwrite with 90000.1
        RAISE 0                                  REM clear ERR value
        e1::
        FREEALLOC pcell&                        REM free any cell created
        IF err<>0
              ...                                   REM display error message etc.
        ENDIF
        RETURN ERR