vmem: change allocation strategy from instant-fit to best-fit
MODIFY
sys/kern/vmem.c
sys/kern/vmem.c
@@ -73,7 +73,7 @@ typedef struct bt {
static POOL_DEFINE(P_VMEM, "vmem", sizeof(vmem_t));
static POOL_DEFINE(P_BT, "vmem boundary tag", sizeof(bt_t));
-static vmem_freelist_t *bt_freehead_tofree(vmem_t *vm, vmem_size_t size) {
+static vmem_freelist_t *bt_freehead(vmem_t *vm, vmem_size_t size) {
vmem_size_t qsize = size >> vm->vm_quantum_shift;
assert(size != 0 && qsize != 0);
int idx = SIZE2ORDER(qsize);
@@ -81,18 +81,6 @@ static vmem_freelist_t *bt_freehead_tofree(vmem_t *vm, vmem_size_t size) {
return &vm->vm_freelist[idx];
}
-/* Returns the freelist in which any block is large enough for allocation */
-static vmem_freelist_t *bt_freehead_toalloc(vmem_t *vm, vmem_size_t size) {
- assert(is_aligned(size, vm->vm_quantum));
- vmem_size_t qsize = size >> vm->vm_quantum_shift;
- assert(size != 0 && qsize != 0);
- int idx = SIZE2ORDER(qsize);
- if (ORDER2SIZE(idx) != qsize)
- idx++;
- assert(idx >= 0 && idx < VMEM_MAXORDER);
- return &vm->vm_freelist[idx];
-}
-
static void vmem_lock(vmem_t *vm) {
mtx_lock(&vm->vm_lock);
}
@@ -117,7 +105,7 @@ static vmem_hashlist_t *bt_hashhead(vmem_t *vm, vmem_addr_t addr) {
static void bt_insfree(vmem_t *vm, bt_t *bt) {
assert(mtx_owned(&vm->vm_lock));
assert(bt->bt_type == BT_TYPE_FREE);
- vmem_freelist_t *list = bt_freehead_tofree(vm, bt->bt_size);
+ vmem_freelist_t *list = bt_freehead(vm, bt->bt_size);
LIST_INSERT_HEAD(list, bt, bt_freelink);
}
@@ -145,6 +133,23 @@ static void bt_insbusy(vmem_t *vm, bt_t *bt) {
vm->vm_inuse += bt->bt_size;
}
+static bt_t *bt_find_freeseg(vmem_t *vm, vmem_size_t size) {
+ assert(mtx_owned(&vm->vm_lock));
+
+ vmem_freelist_t *first = bt_freehead(vm, size);
+ vmem_freelist_t *end = &vm->vm_freelist[VMEM_MAXORDER];
+
+ for (vmem_freelist_t *list = first; list < end; list++) {
+ bt_t *bt;
+ LIST_FOREACH (bt, list, bt_freelink) {
+ if (bt->bt_size >= size) {
+ return bt;
+ }
+ }
+ }
+ return NULL;
+}
+
static void vmem_check_sanity(vmem_t *vm) {
assert(mtx_owned(&vm->vm_lock));
@@ -229,26 +234,12 @@ int vmem_alloc(vmem_t *vm, vmem_size_t size, vmem_addr_t *addrp) {
/* Allocate new boundary tag before acquiring the vmem lock */
bt_t *btnew = pool_alloc(P_BT, PF_ZERO);
- vmem_freelist_t *first = bt_freehead_toalloc(vm, size);
- vmem_freelist_t *end = &vm->vm_freelist[VMEM_MAXORDER];
-
vmem_lock(vm);
vmem_check_sanity(vm);
- bt_t *bt;
- bool found = false;
- for (vmem_freelist_t *list = first; list < end; list++) {
- bt = LIST_FIRST(list);
- if (bt != NULL) {
- /* This is instant-fit strategy, we know that any segment found on these
- * lists is large enough. */
- assert(bt->bt_size >= size);
- found = true;
- break;
- }
- }
+ bt_t *bt = bt_find_freeseg(vm, size);
- if (!found) {
+ if (bt == NULL) {
vmem_unlock(vm);
pool_free(P_BT, btnew);
klog("%s: block of %lu bytes not found in '%s'", __func__, size,

MODIFY
sys/tests/vmem.c
sys/tests/vmem.c
@@ -32,8 +32,8 @@ static int test_vmem(void) {
rc = vmem_add(vm, span2.addr, span2.size);
assert(rc == 0);
- /* alloc 16 quantums, should return addr from span #2 */
- size = 16 * quantum;
+ /* alloc 17 quantums, should return addr from span #2 */
+ size = 17 * quantum;
rc = vmem_alloc(vm, size, &addr);
assert(rc == 0);
assert_addr_is_in_span(addr, size, &span2);

vmem: change allocation strategy from instant-fit to best-fit (#600)