Changeset View
Changeset View
Standalone View
Standalone View
sys/kern/subr_vmem.c
Show First 20 Lines • Show All 260 Lines • ▼ Show 20 Lines | bt_isfree(bt_t *bt) | ||||
return (bt->bt_type == BT_TYPE_FREE); | return (bt->bt_type == BT_TYPE_FREE); | ||||
} | } | ||||
/* | /* | ||||
* Fill the vmem's boundary tag cache. We guarantee that boundary tag | * Fill the vmem's boundary tag cache. We guarantee that boundary tag | ||||
* allocation will not fail once bt_fill() passes. To do so we cache | * allocation will not fail once bt_fill() passes. To do so we cache | ||||
* at least the maximum possible tag allocations in the arena. | * at least the maximum possible tag allocations in the arena. | ||||
*/ | */ | ||||
static int | static __noinline int | ||||
bt_fill(vmem_t *vm, int flags) | _bt_fill(vmem_t *vm, int flags) | ||||
{ | { | ||||
bt_t *bt; | bt_t *bt; | ||||
VMEM_ASSERT_LOCKED(vm); | VMEM_ASSERT_LOCKED(vm); | ||||
/* | /* | ||||
* Only allow the kernel arena and arenas derived from kernel arena to | * Only allow the kernel arena and arenas derived from kernel arena to | ||||
* dip into reserve tags. They are where new tags come from. | * dip into reserve tags. They are where new tags come from. | ||||
Show All 23 Lines | _bt_fill(vmem_t *vm, int flags) | ||||
} | } | ||||
if (vm->vm_nfreetags < BT_MAXALLOC) | if (vm->vm_nfreetags < BT_MAXALLOC) | ||||
return ENOMEM; | return ENOMEM; | ||||
return 0; | return 0; | ||||
} | } | ||||
static inline int | |||||
bt_fill(vmem_t *vm, int flags) | |||||
{ | |||||
if (vm->vm_nfreetags >= BT_MAXALLOC) | |||||
return (0); | |||||
return (_bt_fill(vm, flags)); | |||||
} | |||||
/* | /* | ||||
* Pop a tag off of the freetag stack. | * Pop a tag off of the freetag stack. | ||||
*/ | */ | ||||
static bt_t * | static bt_t * | ||||
bt_alloc(vmem_t *vm) | bt_alloc(vmem_t *vm) | ||||
{ | { | ||||
bt_t *bt; | bt_t *bt; | ||||
▲ Show 20 Lines • Show All 781 Lines • ▼ Show 20 Lines | vmem_xalloc_nextfit(vmem_t *vm, const vmem_size_t size, vmem_size_t align, | ||||
int error; | int error; | ||||
error = ENOMEM; | error = ENOMEM; | ||||
VMEM_LOCK(vm); | VMEM_LOCK(vm); | ||||
retry: | retry: | ||||
/* | /* | ||||
* Make sure we have enough tags to complete the operation. | * Make sure we have enough tags to complete the operation. | ||||
*/ | */ | ||||
if (vm->vm_nfreetags < BT_MAXALLOC && bt_fill(vm, flags) != 0) | if (bt_fill(vm, flags) != 0) | ||||
goto out; | goto out; | ||||
/* | /* | ||||
* Find the next free tag meeting our constraints. If one is found, | * Find the next free tag meeting our constraints. If one is found, | ||||
* perform the allocation. | * perform the allocation. | ||||
*/ | */ | ||||
for (cursor = &vm->vm_cursor, bt = TAILQ_NEXT(cursor, bt_seglist); | for (cursor = &vm->vm_cursor, bt = TAILQ_NEXT(cursor, bt_seglist); | ||||
bt != cursor; bt = TAILQ_NEXT(bt, bt_seglist)) { | bt != cursor; bt = TAILQ_NEXT(bt, bt_seglist)) { | ||||
▲ Show 20 Lines • Show All 265 Lines • ▼ Show 20 Lines | vmem_xalloc(vmem_t *vm, const vmem_size_t size0, vmem_size_t align, | ||||
* choose a free block from which we allocate. | * choose a free block from which we allocate. | ||||
*/ | */ | ||||
first = bt_freehead_toalloc(vm, size, strat); | first = bt_freehead_toalloc(vm, size, strat); | ||||
VMEM_LOCK(vm); | VMEM_LOCK(vm); | ||||
for (;;) { | for (;;) { | ||||
/* | /* | ||||
* Make sure we have enough tags to complete the | * Make sure we have enough tags to complete the | ||||
* operation. | * operation. | ||||
*/ | */ | ||||
if (vm->vm_nfreetags < BT_MAXALLOC && | error = bt_fill(vm, flags); | ||||
bt_fill(vm, flags) != 0) { | if (error != 0) | ||||
error = ENOMEM; | |||||
break; | break; | ||||
} | |||||
alcUnsubmitted Done Inline Actionsalc: ```
error = bt_fill(vm, flags);
if (error != 0)
break;
``` | |||||
/* | /* | ||||
* Scan freelists looking for a tag that satisfies the | * Scan freelists looking for a tag that satisfies the | ||||
* allocation. If we're doing BESTFIT we may encounter | * allocation. If we're doing BESTFIT we may encounter | ||||
* sizes below the request. If we're doing FIRSTFIT we | * sizes below the request. If we're doing FIRSTFIT we | ||||
* inspect only the first element from each list. | * inspect only the first element from each list. | ||||
*/ | */ | ||||
for (list = first; list < end; list++) { | for (list = first; list < end; list++) { | ||||
LIST_FOREACH(bt, list, bt_freelist) { | LIST_FOREACH(bt, list, bt_freelist) { | ||||
if (bt->bt_size >= size) { | if (bt->bt_size >= size) { | ||||
error = vmem_fit(bt, size, align, phase, | error = vmem_fit(bt, size, align, phase, | ||||
nocross, minaddr, maxaddr, addrp); | nocross, minaddr, maxaddr, addrp); | ||||
if (error == 0) { | if (error == 0) { | ||||
vmem_clip(vm, bt, *addrp, size); | vmem_clip(vm, bt, *addrp, size); | ||||
goto out; | goto out; | ||||
} | } | ||||
} | } | ||||
Not Done Inline ActionsAs an "oh, by the way," this code does not really implement "best fit". It selects the first available tag that is sufficiently large, not the best fit. The NetBSD version acknowledges this in a comment that didn't get brought over to FreeBSD: /* * we assume that, for space efficiency, it's better to * allocate from a smaller block. thus we will start searching * from the lower-order list than VM_INSTANTFIT. * however, don't bother to find the smallest block in a free * list because the list can be very long. we can revisit it * if/when it turns out to be a problem. * * note that the 'first' list can contain blocks smaller than * the requested size. thus we need to check bt_size. */ When I first noticed this, I also looked at the old OpenSolaris sources. As per the earlier vmem paper, their implicit default is "instant fit", which behaves like our "first fit". Alternatively, you can explicitly request "first fit", which behaves like our "best fit", or "best fit", which we don't have. The earlier vmem paper didn't mention a "first fit" policy. alc: As an "oh, by the way," this code does not really implement "best fit". It selects the first… | |||||
/* FIRST skips to the next list. */ | /* FIRST skips to the next list. */ | ||||
if (strat == M_FIRSTFIT) | if (strat == M_FIRSTFIT) | ||||
break; | break; | ||||
} | } | ||||
} | } | ||||
/* | /* | ||||
* Retry if the fast algorithm failed. | * Retry if the fast algorithm failed. | ||||
▲ Show 20 Lines • Show All 84 Lines • ▼ Show 20 Lines | |||||
/* | /* | ||||
* vmem_add: | * vmem_add: | ||||
* | * | ||||
*/ | */ | ||||
int | int | ||||
vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, int flags) | vmem_add(vmem_t *vm, vmem_addr_t addr, vmem_size_t size, int flags) | ||||
{ | { | ||||
int error; | int error; | ||||
error = 0; | |||||
flags &= VMEM_FLAGS; | flags &= VMEM_FLAGS; | ||||
Done Inline ActionsThis assignment is now redundant. alc: This assignment is now redundant. | |||||
VMEM_LOCK(vm); | VMEM_LOCK(vm); | ||||
if (vm->vm_nfreetags >= BT_MAXALLOC || bt_fill(vm, flags) == 0) | error = bt_fill(vm, flags); | ||||
if (error == 0) | |||||
Done Inline ActionsThis function can be further simplified: error = bt_fill(vm, flags); if (error == 0) alc: This function can be further simplified:
```
error = bt_fill(vm, flags);
if (error == 0)
``` | |||||
vmem_add1(vm, addr, size, BT_TYPE_SPAN_STATIC); | vmem_add1(vm, addr, size, BT_TYPE_SPAN_STATIC); | ||||
else | |||||
error = ENOMEM; | |||||
VMEM_UNLOCK(vm); | VMEM_UNLOCK(vm); | ||||
return (error); | return (error); | ||||
} | } | ||||
/* | /* | ||||
* vmem_size: information about arenas size | * vmem_size: information about arenas size | ||||
*/ | */ | ||||
▲ Show 20 Lines • Show All 281 Lines • Show Last 20 Lines |