BSA - Bad Segregated (fits) Allocator

BSA is an allocator of segregated fits family. Paul R. Wilson in Dynamic storage allocation: a survey and critical review describes it as:

Segregated fits.
This variant [of Segregated free lists] uses an array of free lists, with each array holding free blocks within a size class. When servicing a request for a particular size, the free list for the corresponding size class is searched for a block at least large enough to hold it. The search is typically a sequential fits search, and many significant variations are possible.
Typically first fit or next fit is used. It is often pointed out that the use of multiple free lists makes the implementation faster than searching a single free list. What is sometimes not appreciated is that this also affects the placement in a very important way - the use of segregated lists excludes blocks of very different sizes, meaning good fits are usually found - the policy therefore embodies a good fit or even best fit strategy, despite the fact that it's often described as a variation on first fit. If there is not a free block in the appropriate free list, segregated fits algorithms try to find a larger block and split it to satisfy the request. This usually proceeds by looking in the list for the next larger size class if it is empty, the lists for larger and larger sizes are searched until a fit is found. If this search fails, more memory is obtained from the operating system to satisfy the request. For most systems using size classes, this is a logarithmic-time search in the worst case. (For example for powers-of-two size classes, the total number of lists is equal to the logarithm of the maximum block size. For a somewhat more refined series, it is still generally logarithmic, but with a larger constant factor.)
In terms of policy, this search order means that smaller blocks are used in preference to larger ones, as with best fit. In some cases, however, the details of the size class system and the searching of size-class lists may cause deviations from the best fit policy. Note that in a segregated fits scheme, coalescing may increase search times. When blocks of a given size are freed, they may be coalesced and put on dif- ferent free lists (for the resulting larger sizes) when the program requests more objects of that size, it may have to find the larger block and split it, rather than still having the same small blocks on the appropriate free list. (Deferred coalescing can reduce the extent of this problem, and the use of multiple free lists makes segregated fits a particularly natural context for deferred coalescing.) Segregated fits schemes fall into three general categories:
  1. Exact Lists. In exact lists systems, where there is (conceptually) a separate free list for each possible block size. This can result in a very large number of free lists, but the "array" of free lists can be represented sparsely. Standish and Tadman's "Fast Fits" scheme uses an array of free lists for small size classes, plus a binary tree of free lists for larger sizes (but only the ones that actually occur).
  2. Strict Size Classes with Rounding. When sizes are grouped into size classes (e.g., powers of two), one approach is to maintain an invariant that all blocks on a size list are exactly of the same size. This can be done by rounding up requested sizes to one of the sizes in the size class series, at some cost in internal fragmentation. In this case, it is also necessary to ensure that the size class series is carefully designed so that split blocks always result in a size that is also in the series otherwise blocks will result that aren't the right size for any free list.
  3. Size Classes with Range Lists. The most common way of dealing with the ranges of sizes that fall into size classes is to allow the lists to conain blocks of slightly different sizes, and search the size lists sequentially, using the classic best fit, first fit, or next fit technique (The choice affects the policy implemented, of course, though probably much less than in the case of a single free list.) This could introduce a linear component to search times, though this does not seem likely to be a common problem in practice, at least if size classes are closely spaced. If it is, then exact list schemes are preferable.
An effcient segregated fits scheme with general coalescing (using boundary tags) was described and shown to perform well in 1971 PSC71, but it did not become well-known Standish and Tadman's ap- parently better scheme was published (but only in a textbook) in 1980, and similarly did not become par- ticularly well known, even to the present. Our impres- sion is that these techniques have received too little attention, while considerably more attention has been given to techniques that are inferior in terms of scala- bility (sequential fits) or generality (buddy systems). Apparently, too few researchers realized the full significance of Knuth's invention of boundary tags for a wide variety of allocation schemes - boundary tags can support fast and general splitting and coa- lescing, independently of the basic indexing scheme used by the allocator. This frees the designer to use more sophisticated higher-level mechanisms and policies to implement almost any desired strategy. (It seems likely that the original version of boundary tags was initially viewed as too costly in space, in a time when memory was a very scarce resource, and the footer optimization simply never became well- known.).


BSA puts a lookup table at the beginning of heap. It is used in order to index all free blocks. This image shows you as it's implemented:
BSA heap
Every block can be in two states:
  1. free: inserted in only one list, with in its head (of its space) a pointer to the next free block of the list and in its tail a pointer to its head (needed for coalescing).
  2. used: not inserted in any list
The status of the block is written with bit stealing tecnique applied to the header of block (that contains the size of block and the status of the previous block). So a free block has this structure:
BSA block
When a block is freed, it is coalesced with the next block on the heap (if it's free) and/or with previous block (if it's free). During an allocation request, if BSA doesn't find a block of the exact size, it searches for a bigger block and it splits the residual space into a new free block.


BSA implements these policies: Optionally with these two policies you can decide to set also an address order fit. For our project we use BSA only with first fit policy (no address order).


BSA can be configured in order to enable or disable some features:


Actually BSA designed only for single-threaded load.

Source code

Get BSA/BSA++ here.

Return to main page