* Copyright (c) 1998 Matthew Dillon. All Rights Reserved.
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
* 4. Neither the name of the University nor the names of its contributors
* may be used to endorse or promote products derived from this software
* without specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
* OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
* DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
* GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
* NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
* BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting
*
* This module implements a general bitmap allocator/deallocator. The
* allocator eats around 2 bits per 'block'. The module does not
* try to interpret the meaning of a 'block' other then to return
* SWAPBLK_NONE on an allocation failure.
*
* A radix tree is used to maintain the bitmap. Two radix constants are
* involved: One for the bitmaps contained in the leaf nodes (typically
* 32), and one for the meta nodes (typically 16). Both meta and leaf
* nodes have a hint field. This field gives us a hint as to the largest
* free contiguous range of blocks under the node. It may contain a
* value that is too high, but will never contain a value that is too
* low. When the radix tree is searched, allocation failures in subtrees
* update the hint.
*
* The radix tree also implements two collapsed states for meta nodes:
* the ALL-ALLOCATED state and the ALL-FREE state. If a meta node is
* in either of these two states, all information contained underneath
* the node is considered stale. These states are used to optimize
* allocation and freeing operations.
*
* The hinting greatly increases code efficiency for allocations while
* the general radix structure optimizes both allocations and frees. The
* radix tree should be able to operate well no matter how much
* fragmentation there is and no matter how large a bitmap is used.
*
* Unlike the rlist code, the blist code wires all necessary memory at
* creation time. Neither allocations nor frees require interaction with
* the memory subsystem. In contrast, the rlist code may allocate memory
* on an rlist_free() call. The non-blocking features of the blist code
* are used to great advantage in the swap code (vm/nswap_pager.c). The
* rlist code uses a little less overall memory then the blist code (but
* due to swap interleaving not all that much less), but the blist code
* scales much, much better.
*
* LAYOUT: The radix tree is layed out recursively using a
* linear array. Each meta node is immediately followed (layed out
* sequentially in memory) by BLIST_META_RADIX lower level nodes. This
* is a recursive structure but one that can be easily scanned through
* a very simple 'skip' calculation. In order to support large radixes,
* portions of the tree may reside outside our memory allocation. We
* handle this with an early-termination optimization (when bighint is
* set to -1) on the scan. The memory allocation is only large enough
* to cover the number of blocks requested at creation time even if it
* must be encompassed in larger root-node radix.
*
* NOTE: the allocator cannot currently allocate more then
* BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too
* large' if you try. This is an area that could use improvement. The
* radix is large enough that this restriction does not effect the swap
* system, though. Currently only the allocation code is effected by
* this algorithmic unfeature. The freeing code can handle arbitrary
* ranges.
*
* This code can be compiled stand-alone for debugging.
*/
* NOTE: a few modifications is made in the orginal FreeBSD code:
* 1. change the name of some variables/constants
* 2. discard the code handling ALL_FREE and ALL_ALLOCATED state
* 3. allocate more than 32 slots won't lead to kernel panic
* 4. remove all the code for debugging
*
* Zhao Shuai
* upczhsh@163.com
*/
#include <stdlib.h>
#include <util/RadixBitmap.h>
#define TERMINATOR -1
static uint32
radix_bitmap_init(radix_node *node, uint32 radix, uint32 skip, uint32 slots)
{
uint32 index = 0;
int32 big_hint = radix < slots ? radix : slots;
if (radix == BITMAP_RADIX) {
if (node) {
node->big_hint = big_hint;
if (big_hint == BITMAP_RADIX)
node->u.bitmap = 0;
else
node->u.bitmap = (bitmap_t)-1 << big_hint;
}
return index;
}
if (node) {
node->big_hint = big_hint;
node->u.available = big_hint;
}
radix /= NODE_RADIX;
uint32 next_skip = skip / NODE_RADIX;
uint32 i;
for (i = 1; i <= skip; i += next_skip) {
if (slots >= radix) {
index = i + radix_bitmap_init(node ? &node[i] : NULL,
radix, next_skip - 1, radix);
slots -= radix;
} else if (slots > 0) {
index = i + radix_bitmap_init(node ? &node[i] : NULL,
radix, next_skip - 1, slots);
slots = 0;
} else {
if (node)
node[i].big_hint = TERMINATOR;
break;
}
}
if (index < i)
index = i;
return index;
}
radix_bitmap *
radix_bitmap_create(uint32 slots)
{
uint32 radix = BITMAP_RADIX;
uint32 skip = 0;
while (radix < slots) {
radix *= NODE_RADIX;
skip = (skip + 1) * NODE_RADIX;
}
radix_bitmap *bmp = (radix_bitmap *)malloc(sizeof(radix_bitmap));
if (bmp == NULL)
return NULL;
bmp->radix = radix;
bmp->skip = skip;
bmp->free_slots = slots;
bmp->root_size = 1 + radix_bitmap_init(NULL, radix, skip, slots);
bmp->root = (radix_node *)malloc(bmp->root_size * sizeof(radix_node));
if (bmp->root == NULL) {
free(bmp);
return NULL;
}
radix_bitmap_init(bmp->root, radix, skip, slots);
return bmp;
}
void
radix_bitmap_destroy(radix_bitmap *bmp)
{
free(bmp->root);
free(bmp);
}
static radix_slot_t
radix_leaf_alloc(radix_node *leaf, radix_slot_t slotIndex, int32 count)
{
if (count <= (int32)BITMAP_RADIX) {
bitmap_t bitmap = ~leaf->u.bitmap;
uint32 n = BITMAP_RADIX - count;
bitmap_t mask = (bitmap_t)-1 >> n;
for (uint32 j = 0; j <= n; j++) {
if ((bitmap & mask) == mask) {
leaf->u.bitmap |= mask;
return (slotIndex + j);
}
mask <<= 1;
}
}
if (leaf->big_hint >= count)
leaf->big_hint = count - 1;
return RADIX_SLOT_NONE;
}
static radix_slot_t
radix_node_alloc(radix_node *node, radix_slot_t slotIndex, int32 count,
uint32 radix, uint32 skip)
{
uint32 next_skip = skip / NODE_RADIX;
radix /= NODE_RADIX;
for (uint32 i = 1; i <= skip; i += next_skip) {
if (node[i].big_hint == TERMINATOR)
break;
if (count <= node[i].big_hint) {
radix_slot_t addr = RADIX_SLOT_NONE;
if (next_skip == 1)
addr = radix_leaf_alloc(&node[i], slotIndex, count);
else
addr = radix_node_alloc(&node[i], slotIndex, count, radix,
next_skip - 1);
if (addr != RADIX_SLOT_NONE) {
node->u.available -= count;
if (node->big_hint > node->u.available)
node->big_hint = node->u.available;
return addr;
}
}
slotIndex += radix;
}
if (node->big_hint >= count)
node->big_hint = count - 1;
return RADIX_SLOT_NONE;
}
radix_slot_t
radix_bitmap_alloc(radix_bitmap *bmp, uint32 count)
{
radix_slot_t addr = RADIX_SLOT_NONE;
if (bmp->radix == BITMAP_RADIX)
addr = radix_leaf_alloc(bmp->root, 0, count);
else
addr = radix_node_alloc(bmp->root, 0, count, bmp->radix, bmp->skip);
if (addr != RADIX_SLOT_NONE)
bmp->free_slots -= count;
return addr;
}
static void
radix_leaf_dealloc(radix_node *leaf, radix_slot_t slotIndex, uint32 count)
{
uint32 n = slotIndex & (BITMAP_RADIX - 1);
bitmap_t mask = ((bitmap_t)-1 >> (BITMAP_RADIX - count - n))
& ((bitmap_t)-1 << n);
leaf->u.bitmap &= ~mask;
leaf->big_hint = BITMAP_RADIX;
}
static void
radix_node_dealloc(radix_node *node, radix_slot_t slotIndex, uint32 count,
uint32 radix, uint32 skip, radix_slot_t index)
{
node->u.available += count;
uint32 next_skip = skip / NODE_RADIX;
radix /= NODE_RADIX;
uint32 i = (slotIndex - index) / radix;
index += i * radix;
i = i * next_skip + 1;
while (i <= skip && index < slotIndex + count) {
uint32 v = index + radix - slotIndex;
if (v > count)
v = count;
if (next_skip == 1)
radix_leaf_dealloc(&node[i], slotIndex, v);
else
radix_node_dealloc(&node[i], slotIndex, v, radix,
next_skip - 1, index);
if (node->big_hint < node[i].big_hint)
node->big_hint = node[i].big_hint;
count -= v;
slotIndex += v;
index += radix;
i += next_skip;
}
}
void
radix_bitmap_dealloc(radix_bitmap *bmp, radix_slot_t slotIndex, uint32 count)
{
if (bmp->radix == BITMAP_RADIX)
radix_leaf_dealloc(bmp->root, slotIndex, count);
else
radix_node_dealloc(bmp->root, slotIndex, count, bmp->radix,
bmp->skip, 0);
bmp->free_slots += count;
}
