HP OpenVMS Systems Documentation

Content starts here

OpenVMS Programming Concepts Manual

Previous Contents Index

14.5 Allocating and Freeing Blocks

The run-time library heap management routines LIB$GET_VM and LIB$FREE_VM provide the mechanism for allocating and freeing blocks of memory.

The LIB$GET_VM and LIB$FREE_VM routines are fully reentrant, so they can be called either by code running at AST level or in an Ada multitasking environment. Several threads of execution can be allocating or freeing memory simultaneously either in the same zone or in different zones.

All memory allocated by LIB$GET_VM has user-mode read/write access, even if the call to LIB$GET_VM is made from a more privileged access mode.

The rules for using LIB$GET_VM and LIB$FREE_VM are as follows:

  • Any memory you free by calling LIB$FREE_VM must have been allocated by a previous call to LIB$GET_VM. You cannot allocate memory by calling SYS$EXPREG or SYS$CRETVA and then free it using LIB$FREE_VM.
  • When you free a block of memory by calling LIB$FREE_VM, you must use the same zone-id value as when you called LIB$GET_VM to allocate the block. If the block was allocated from the default zone, you must either specify a zone-id value of 0 or omit the zone-id argument when you call LIB$FREE_VM.
  • You cannot free part of a block that was allocated by a call to LIB$GET_VM; the whole block must be freed by a single call to LIB$FREE_VM.
  • You cannot combine contiguous blocks of memory that were allocated by several calls to LIB$GET_VM into one larger block that is freed by a single call to LIB$FREE_VM.
  • All memory allocated by LIB$GET_VM is aligned according to the alignment attribute for the zone; all memory freed by LIB$FREE_VM must have the correct alignment for the zone. An error status is returned if you attempt to free a block that is not aligned properly.

14.6 Allocation Algorithms

The run-time library heap management routines provide four algorithms, listed in Table 14-4, that are used to allocate and free memory and that are used to manage blocks of free memory.

Table 14-4 Allocation Algorithms
Code Symbol Description
2 LIB$K_VM_QUICK_FIT Quick Fit (maintains lookaside list)
3 LIB$K_VM_FREQ_SIZES Frequent Sizes (maintains lookaside list)
4 LIB$K_VM_FIXED Fixed Size Blocks

The Quick Fit and Frequent Sizes algorithms use lookaside lists to speed allocation and freeing for certain request sizes. A lookaside list is the software analog of a hardware cache. It takes less time to allocate or free a block that is on a lookaside list.

For each of the algorithms, LIB$GET_VM performs one or more of the following operations:

  • Tries to allocate a block from an appropriate lookaside list.
  • Scans the list of areas owned by the zone. For each area, it tries to allocate a block from the free list and then tries to allocate a block from the block of unallocated memory at the end of the area.
  • Adds a new area to the zone and allocates the block from that area.

For each of the algorithms, LIB$FREE_VM performs one or more of the following operations:

  • Places the block on a lookaside list associated with the zone if there is an appropriate list.
  • Locates the area that contains the block. If the zone has boundary tags, the tags encode the area; otherwise, it scans the list of areas owned by the zone to find the correct area.
  • Inserts the block on the area free list and checks for merges with adjacent free blocks.
    If the zone has boundary tags, LIB$FREE_VM checks the tags of adjacent blocks; if a merge does not occur, it inserts the block at the tail of the free list.
    If the zone does not have boundary tags, LIB$FREE_VM scans the sorted free list to find the correct insertion point. It also checks the preceding and following blocks for merges.

14.6.1 First Fit Algorithm

The First Fit algorithm (LIB$K_VM_FIRST_FIT) maintains a linked list of free blocks. If the zone does not have boundary tags, the free list is kept sorted in order of increasing memory address. An allocation request is satisfied by the first block on the free list that is large enough; if the first free block is larger than the request size, it is split and the fragment is kept on the free list. When a block is freed, it is inserted in the free list at the appropriate point; adjacent free blocks are merged to form larger free blocks.

14.6.2 Quick Fit Algorithm

The Quick Fit algorithm (LIB$K_VM_QUICK_FIT) maintains a set of lookaside lists indexed by request size for request sizes in a specified range. For request sizes that are not in the specified range, a First Fit list of free blocks is maintained. An allocation request is satisfied by removing a block from the appropriate lookaside list; if the lookaside list is empty, a First Fit allocation is done. When a block is freed, it is placed on either a lookaside list or the First Fit list according to its size.

Free blocks that are placed on a lookaside list are neither merged with adjacent free blocks nor split to satisfy a request for a smaller block.

14.6.3 Frequent Sizes Algorithm

The Frequent Sizes algorithm (LIB$K_VM_FREQ_SIZES) is similar to the Quick Fit algorithm in that it maintains a set of lookaside lists for some block sizes. You specify the number of lookaside lists when you create the zone; the sizes associated with those lists are determined by the actual sizes of blocks that are freed. An allocation request is satisfied by searching the lookaside lists for a matching size; if no match is found, a First Fit allocation is done. When a block is freed, the block is placed on a lookaside list with a matching size, on an empty lookaside list, or on the First Fit list if no lookaside list is available. As with the Quick Fit algorithm, free blocks on lookaside lists are not merged or split.

14.6.4 Fixed Size Algorithm

The Fixed Size algorithm (LIB$K_VM_FIXED) maintains a single queue of free blocks. There is no First Fit free list, and splitting or merging of blocks does not occur.

14.7 User-Defined Zones

When you create a zone by calling LIB$CREATE_VM_ZONE, you must select an allocation algorithm from the fixed set provided by the run-time library. You can tailor the characteristics of the zone by specifying various zone attributes. User-defined zones provide additional flexibility and control by letting you supply routines for the allocation and deallocation algorithms.

You create a user-defined zone by calling LIB$CREATE_USER_VM_ZONE. Instead of supplying values for a fixed set of zone attributes, you provide routines that perform the following operations for the zone:

  • Allocate a block of memory
  • Free a block of memory
  • Reset the zone
  • Delete the zone

Each time that one of the run-time library heap management routines (LIB$GET_VM, LIB$FREE_VM, LIB$RESET_VM_ZONE, LIB$DELETE_VM_ZONE) is called to perform an operation on a user-defined zone, the corresponding routine that you specified is called to perform the actual operation. You need not make any changes in the calling program to use user-defined zones; their use is transparent.

You do not need to provide routines for all four of the preceding operations if you know that your program will not perform certain operations. If you omit some of the operations and your program attempts to use them, an error status is returned.

Applications of user-defined zones include the following:

  • You can provide your own specialized allocation algorithms. These algorithms can in turn invoke LIB$GET_VM, LIB$GET_VM_PAGE, SYS$EXPREG, or other system services.
  • You can use a user-defined zone to monitor memory allocation operations. Example 14-1 shows a monitoring program that prints a record of each call to either allocate or free memory in a zone.

Example 14-1 Monitoring Heap Operations with a User-Defined Zone

C This is the main program that creates a zone and exercises it.
C Note that the main program simply calls LIB$GET_VM and LIB$FREE_VM.
C It contains no special coding for user-defined zones.



        CALL LIB$GET_VM(10, I1, ZONE)
        CALL LIB$GET_VM(20, I2, ZONE)
        CALL LIB$FREE_VM(10, I1, ZONE)

C This is the subroutine that creates a user-defined zone for monitoring.
C Each GET, FREE, or RESET prints a line of output on the terminal.
C Errors are signaled.


C Create the primary zone.  The primary zone supports
C the actual allocation and freeing of memory.


C Create a user-defined zone that monitors operations on REAL_ZONE.

        1       GET_RTN,
        1       FREE_RTN,
        1       RESET_RTN,
        1       LIB$DELETE_VM_ZONE)

C Return the zone-id of the user-defined zone to the caller to use.

        ZONE = USER_ZONE

C GET routine for user-defined zone.



        IF (.NOT. STATUS) THEN
                CALL LIB$SIGNAL(%VAL(STATUS))
                TYPE 10, SIZE, ADDR
10              FORMAT(' Allocated ',I4,' bytes at ',Z8)
        GET_RTN = STATUS

C FREE routine for user-defined zone.



        IF (.NOT. STATUS) THEN
                CALL LIB$SIGNAL(%VAL(STATUS))
                TYPE 20, SIZE, ADDR
20              FORMAT(' Freed ',I4,' bytes at ',Z8)

C RESET routine for user-defined zone.


        IF (.NOT. STATUS) THEN
                CALL LIB$SIGNAL(%VAL(STATUS))
                TYPE 30, ZONE
30              FORMAT(' Reset zone at ', Z8)


14.8 Debugging Programs That Use Virtual Memory Zones

This section discusses some methods and aids for debugging programs that use virtual memory zones. Note that this information is implementation dependent and may change at any time.

The following list offers some suggestions for discovering and tracking problems with memory zone usage:

  • Run the program with both free-fill-zero and free-fill-one set. The results from both executions of the program should be the same. If the results differ, this could mean that you are referencing a zone that is already deallocated. It could also mean that, after deallocating a zone, you created a new zone at the same location, so that you now have two pointers pointing to the same zone.
  • Call LIB$FIND_VM_ZONE at image termination. If a virtual memory zone is not deleted, LIB$FIND_VM_ZONE returns its zone identifier.
  • Use LIB$SHOW_VM_ZONE and LIB$VERIFY_VM_ZONE to print zone information and check for errors in the internal data structures. LIB$SHOW_VM_ZONE allows you to determine whether any linkage pointers for the virtual memory zones are corrupted. LIB$VERIFY_VM_ZONE allows you to request verification of the contents of the free blocks, so that if you call LIB$VERIFY_VM_ZONE with free-fill set, you can determine whether you are writing to any deallocated zones.
  • For zones created with the Fixed Size, Quick Fit, or Frequent Size algorithms, some types of errors cannot be detected. For example, in a zone that implements the Fixed Size algorithm (or in a Quick Fit or Frequent Size algorithm when the block is cached on a lookaside list), freeing a block more than once returns SS$_NORMAL, but the internal data structures are invalid. In this case, change the algorithm to First Fit. The First Fit algorithm checks whether you are freeing a block that is already on the free list and, if so, returns the error LIB$_BADBLOADR.

Chapter 15
Alignment on OpenVMS Alpha and VAX Systems

This chapter describes the importance and techniques of alignment for both OpenVMS VAX and OpenVMS Alpha systems.1 It contains the following subsections:

Section 15.1 describes alignment on OpenVMS VAX and OpenVMS Alpha systems.

Section 15.2 describes using compilers for alignment.

Section 15.3 describes using various tools to uncover unaligned data.


1 Reprinted from an article in the March/April 1993 issue of Digital Systems Journal, Volume 15, Number 2, titled "Alpha AXP(TM) Migration: Understanding Data Alignment on OpenVMS AXP Systems" by Eric M. LaFranchi and Kathleen D. Morse. Copyright 1993 by Cardinal Business Media, Inc., 101 Witmer Road, Horsham, PA 19044.

15.1 Alignment

Alignment is an aspect of a data item that refers to its placement in memory. The mixing of byte, word, longword, and quadword data types can lead to data that is not aligned on natural boundaries. A naturally aligned datum of size 2**N is stored in memory at a starting byte address that is a multiple of 2**N, that is, an address that has N low-order zero bits. Data is naturally aligned when its address is an integral multiple of the size of the data in bytes (for example, when the following occurs):

  • A byte is aligned at any address.
  • A word is aligned at any address that is a multiple of 2.
  • A longword is aligned at any address that is a multiple of 4.
  • A quadword is aligned at any address that is a multiple of 8.

Data that is not aligned is referred to as unaligned. Throughout this chapter, the term aligned is used instead of naturally aligned.

Table 15-1 shows examples of common data sizes, their alignment, the number of zero bits in an aligned address for that data, and a sample aligned address in hexadecimal.

Table 15-1 Aligned Data Sizes
Data Size Alignment Zero Bits Aligned Address Example
Byte Byte 0 10001, 10002, 10003, 10004
Word Word 1 10002, 10004, 10006, 10008
Longword Longword 2 10004, 10008, 1000C, 10010
Quadword Quadword 4 10008, 10010, 10018, 10020

An aligned structure has all its members aligned. An unaligned structure has one or more unaligned members. Figure 15-1 shows examples of aligned and unaligned structures.

Figure 15-1 Aligned and Unaligned Structures

15.1.1 Alignment and Performance

To achieve optimal performance, use aligned instruction sequence references and naturally aligned data. When unaligned data is referenced, more overhead is required than when referencing aligned data. This condition is true for both OpenVMS VAX and Alpha systems. On both VAX and Alpha systems, data need not be aligned to obtain correct processing results. Alignment is a concern for performance, not program correctness. Because natural alignment is not always possible, both OpenVMS VAX and Alpha systems provide help to manage the impact of unaligned data references.

Although alignment is not required on VAX systems for stack, data, or instruction stream references, Alpha systems require that the stack and instructions be longword aligned. Alignment on OpenVMS VAX (VAX Only)

On VAX systems, memory references that are not longword aligned result in a transparent performance degradation. The full effect of unaligned memory references is hidden by microcode, which detects the unaligned reference and generates a microtrap to handle the alignment correction. This fix of alignment is done entirely in microcode. Aligned references, on the other hand, avoid the microtraps to handle fixes. Even with this microcode fix, an unaligned reference can take up to four times longer than an aligned reference. Alignment on OpenVMS Alpha (Alpha Only)

On Alpha systems, you can check and correct alignment the following three ways:

  • Allow privileged architecture library code (PALcode) to fix the alignment faults for you.
  • Use directives to the compiler.
  • Fix the data yourself to make sure data is aligned.

Though Alpha systems do not use microcode to automatically handle unaligned references, PALcode traps the faults and corrects unaligned references as the data is processed. If you use the shorter load/store instruction sequences and your data in unaligned, then you incur an alignment fault PALcode fixup. The use of PALcode to correct alignment faults results in the slowest of the three ways to process your data.

By using directives to the compiler, you can tell your compiler to create a safe set of instructions. If it is unaligned, the compiler uses a set of unaligned load/store instructions. These unaligned load/store instructions are called safe sequences because they never generate unaligned data exceptions. Code sequences that use the unaligned load/store instructions are longer than the aligned load/store instruction sequences. By using unaligned load/store instructions and longer instruction sequences, you can obtain the desired results without incurring an alignment trap. This technique allows you to avoid the significant performance impact of a trap and subsequent data fixes.

By fixing the data yourself so that it is aligned, you can use a short instruction stream. This results in the fastest way to process your data. When aligning data, the following recommendations are suggested:

  • If references to the data must be made atomic, then the data must be aligned. Otherwise, an unaligned fault causes a fatal reserved operand fault in this case.
  • If you fix alignment problems in public interfaces, then you could break existing programs.

To detect unaligned reference information, you can use utilities such as the OpenVMS Debugger and Performance and Coverage Analyzer (PCA). You can also use the OpenVMS Alpha handler to generate optional informational exceptions for process space references. This allows condition handlers to track unaligned references. Alignment fault system services allow you to enable and disable the delivery of these informational exceptions. Section 15.3.3 discusses system services that you can use to report both image and systemwide alignment problems.

15.2 Using Compilers for Alignment (Alpha Only)

On Alpha systems, compilers automatically align data by default. If alignment problems are not resolved, they are at least flagged. The following sections present how the compilers for Compaq C, BLISS, Compaq Fortran, and MACRO-32 deal with alignment.

15.2.1 The Compaq C Compiler (Alpha Only)

On Alpha systems, the Compaq C compiler naturally aligns all explicitly declared data, including the elements of data structures. The pragmas member_alignment and nomember_alignment allow data structures to be aligned or packed (putting the next piece of data on the next byte boundary) in the same manner as the VAX C compiler. Additional pragmas of member_alignment save and member_alignment restore exist to save and restore the state of member alignment. These prevent alignment assumptions in one include file from affecting other source code. The following program examples show the use of these pragmas:

        #pragma member_alignment save   (1)
        #pragma nomember_alignment      (2)

          char  byte;
          short word;
          long  longword;
        } mystruct;
        #pragma member_alignment restore  (3)

  1. Saves the current alignment setting.
  2. Sets nomember_alignment, which means that the data is to be packed in the structure mystruct.
  3. Resets the alignment setting for the code that follows.

The base alignment of a data structure is set to be the alignment of the largest member in the structure. If the largest element of a data structure is a longword, for example, then the base alignment of the data structure is longword alignment.

The malloc() function of the Compaq C Run-Time Library retrieves pointers that are at least quadword aligned. Because it is the exception rather than the rule to encounter unaligned data in C programs, the compiler assumes most data references are aligned. Pointers, for example, are always assumed to be aligned; only data structures declared with the pragma nomember_alignment are assumed to contain unaligned data. If the Compaq C compiler believes the data might be unaligned, it generates the safe instruction sequences; that is, it uses the unaligned load/store instructions. Also, you can use the /WARNING=ALIGNMENT compiler qualifier to turn on alignment checking by the compiler. This results in a compiler warning for unaligned data references.

Previous Next Contents Index