Contents


Memory allocation mechanisms in AIX

Comments

An allocation policy refers to the set of data structures and algorithms used to represent and manage the heap in terms of implementing the memory management functions of allocating, freeing and reallocating memory dynamically.

AIX malloc subsystem supports the following allocation policies:

  • Default (Yorktown) allocation policy
  • Watson allocation policy
  • Malloc 3.1 allocation policy

Overview of default allocation policy

The default allocation policy in AIX is also called Yorktown policy. It maintains the free space in heap as nodes in a Cartesian binary search tree format.

The nodes are arranged left-to-right by address (increasing address to the right) and top-to-bottom by length (such that no child is larger than its parent).

Figure 1. Cartesian binary search tree for Yorktown policy
Yorktown diagram
Yorktown diagram

When to use Yorktown

  • Yorktown is enabled by default on AIX. It is the most widely used and most stable of all allocation policies, and therefore is suitable for almost all cases.
  • Since it is maintained as a tree with varying sized nodes, there are no limitations on the allocation block sizes.

To enable Yorktown, type the following command:

export MALLOCTYPE=Yorktown

It can be verified for enablement in two ways:

  1. Using DBX sub command malloc
  2. Running command echo $MALLOCTYPE

Yorktown allocation algorithm

Total memory allocated = roundup (n + prefix_size, alignment), where:

  • n equals number of bytes requested by the user
  • prefix_size equals metadata information

First, the node from the free tree with the lowest address (which is greater than or equal to the requested block size) is removed. If this is larger than what is wanted, it is broken into two pieces. The extra broken block is returned back to the tree and is inserted in the appropriate place in the free tree. The required block size is then returned back to the caller.

Yorktown free algorithm

Freeing of memory involves inserting the freed node back to the free tree. This follows the standard root insertion algorithm. Each node in the tree is searched in comparison to the node being freed, and if it adjoins any other node in terms of the address, it is joined to that node. This joining of adjacent nodes prevents fragmentation to some extent, because a lot of free nodes, even though they are adjacent with respect to addresses, would be scattered in the tree and will not be available for contiguous allocation.

Yorktown reallocation algorithm

If the size of the reallocated block turns out larger than the original block, the original block is returned to the free tree so that any possible joining can occur with the adjoining nodes. A new block of the requested size is then allocated. The data is moved from the original block to the new block, and the new block is returned to the caller. The old block is freed and is no longer valid. If the size of the reallocated block is smaller than the original block, the block is split and the extra block is returned to the free tree with the required size block being returned to the caller.

Overview of Watson allocation policy

The Watson allocation policy maintains free space in the heap as nodes in two separate "red-black trees":

  1. Sorted by address
  2. Sorted by size

Both trees have to be maintained properly for consistency and correctness.

Figure 2. Red-black tree used in Watson allocation policy based on "Sorted by Address"
Watson 1 diagram
Watson 1 diagram

Every node in the address tree will have lesser address nodes in its left subtree and higher address nodes in its right subtree.

Figure 3. Red-black tree used in Watson allocation policy based on "Sorted by Size"
Watson 2 diagram
Watson 2 diagram

Every node in the size tree will have lesser size nodes in its left subtree and greater size nodes in the right subtree.

When to use Watson

Since Watson maintains its space in a red-black tree, it provides more efficient tree operations like insertion and searching as compared to other policies.

To enable it, type the following command:

export MALLOCTYPE=Watson

Watson allocation algorithm

Similar to the Yorktown policy, Watson searches the size tree and finds the smallest possible block suitable for the request. If the block found in the size tree is exactly the required size, the block is removed from both the size and the address tree and then returned to the caller.

If a block of sufficient size is not found in the free tree, then the process heap is expanded using the sbrk() system call, a block of the expanded size is added to the size and address trees, and allocation continues as before.

Watson free algorithm

The node is returned to the address tree first at the root. The tree is traversed to check if the node adjoins any other node in the tree with respect to the address. If so, the freed node is joined with the node in the tree. Adjoining of nodes in this manner prevents fragmentation of memory in heap.

Watson reallocation algorithm

If the size of the reallocated block would be larger than the original block, the original block is returned to the free tree so that any possible coalescence can occur with the adjoining nodes. A new block of the requested size is then allocated, the data is moved from the original block to the new block, and the new block is returned to the caller. If the size of the reallocated block is smaller than the original block, the block is split and the remainder is returned to the free tree after sending the required amount to the caller.

Overview of malloc 3.1 allocation policy

In malloc 3.1, the heap memory is maintained as a hash bucket where each bucket points to a linked list having nodes or blocks of only a certain specific size. The size of the block is calculated using the following formula (i identifies the bucket number):

size = 2 ^ (i + 4)
Figure 4. Heap memory as a hash bucket in malloc 3.1
Malloc 3.1 diagram
Malloc 3.1 diagram

To enable malloc, use the following command:

export MALLOCTYPE=3.1 for 32 bit programs 
export MALLOCTYPE=3.1_64BIT for 64 bit programs

Malloc 3.1 allocation algorithm

A block is allocated from the free pool by first converting the requested bytes to an index in the bucket array, using the following equation:

needed = requested + 8
If needed <= 16,
then
bucket = 0
If needed  >16,
then
bucket = (log(needed)/log(2) rounded down to the nearest integer) - 3

The size of each block in the linked list pointed by the bucket is block size = 2 ^ (bucket + 4). If the list in the bucket is null, memory is allocated using the sbrk() subroutine to add blocks to the list. If the free list is not empty, the block at the head of the list is returned to the caller. The next block on the list then becomes the new head.

Malloc 3.1 Free algorithm

When a block of memory is returned to the free pool, the bucket index is calculated just like it is done with allocation. The block to be freed is then added to the head of the free list for that bucket.

Malloc 3.1 reallocation algorithm

During reallocation, the requested size is compared against the existing size of the allocated block. Because of the wide difference among the sizes handled by each bucket, the new block size can fall into the same bucket as that of the original block. In such cases, the same block is returned. If the needed size happens to be greater than the existing block, the block is freed, a new block is allocated from a new bucket, and the data is moved from the old block to the new block.

Malloc 3.1 limitations

The malloc allocation policy is less efficient than the default, and it is not recommended for use in most cases. This policy rounds off the size of the allocation request to the next highest available block. Therefore, we can be allocated more memory than we want.

Sometimes application programs may depend unknowingly on the side effects of the malloc 3.1 allocation policy. For example, let's assume that there is a program which incorrectly overwrites the number of bytes it has been allocated by malloc. It may function correctly when using the malloc 3.1 policy because, in essence, 3.1 may have allocated more memory than it requested. The same program can and should fail when it runs with different allocation policy.

However, in some cases, 3.1 may perform better than the other allocation algorithms by reducing the overhead of data movement during a reallocation, because it have been initially allocated more memory than it actually requested.

Additional malloc options

Some additional malloc options are:

  • Malloc multiheap
  • Pool allocation
  • Malloc buckets

Malloc multiheap

By default, the malloc subsystem treats the entire process heap as a single entity. In multithreaded enviornments multiple threads access the same heap. In this scenario using a single heap is not very efficient, because when one thread is being serviced and has taken the heap lock, the other threads will have to wait for their turn to access the heap. In such cases, this option can be useful.

To enable the multiheap option, use the following:

MALLOCOPTIONS=[multiheap:n] | [considersize]

The options are as described:

  • multiheap:n
    The maximum number of heaps available to malloc multiheap is 32. You can specify "n" number of heaps between 1 to 32 for malloc to use.
  • considersize
    By default, malloc multiheap selects the next available heap. If the considersize option is specified, malloc multiheap will use a different algorithm and select the heap which has enough free space to handle the request.

Malloc multiheap limitations

  • Since a single heap is actually divided into many heaps (up to 32), unnecessary enabling of malloc multiheap can cause severe fragmentation. It can also result in a situation where the system will seem to have run out of memory, because the available memory is fragmented and is not available contiguously.
  • Since the considersize option requires some extra processing, using this option may slow down the process to some extent.
  • Multiheap option is not supported for malloc 3.1 and user defined allocation policies.

Pool allocation

When memory size is less than or equal to 512 bytes, AIX malloc provides a more efficient frontend to the actual backend functions of malloc. Pool allocation creates for each thread its own malloc pool which avoids lock contention with other threads. At present, the maximum pool size per process for this allocator is limited to 512MB.

To enable pool allocation, use the following:

MALLOCOPTIONS=pool<:max_size>

This basically creates a fixed number of pools with increasing size. There can be 128 pools for a 32-bit application and 64 pools for a 64-bit application.

Pool allocation does not work effectively if one thread of the application allocates memory and other thread frees the memory.

Malloc buckets

Malloc buckets is an extension to the Yorktown allocation policy. When an application requires a large number of small allocation requests, malloc buckets is more commonly used. It can be used only along with Yorktown malloc policy.

To enable malloc buckets, use the following:

MALLOCOPTIONS=buckets,number_of_buckets:n

Only allocation requests up to 512 bytes can be serviced by the bucket allocator, and any greater requests are automatically forwarded to the Yorktown malloc.

Conclusion

This article covers the essence of the various AIX memory allocation schemes and their salient features. Having an overall idea about the various allocation schemes can help you decide on the allocation scheme that best suits your application at hand in terms of execution efficiency and performance.


Downloadable resources


Related topics


Comments

Sign in or register to add and subscribe to comments.

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=AIX and UNIX
ArticleID=524926
ArticleTitle=Memory allocation mechanisms in AIX
publish-date=09212010