Changeset View
Standalone View
sys/vm/vm_reserv.c
Show First 20 Lines • Show All 991 Lines • ▼ Show 20 Lines | |||||
return (true); | return (true); | ||||
} | } | ||||
return (false); | return (false); | ||||
} | } | ||||
/* | /* | ||||
* Determine whether this reservation has free pages that satisfy the given | * Determine whether this reservation has free pages that satisfy the given | ||||
* request for contiguous physical memory. Start searching from the lower | * request for contiguous physical memory. Start searching from the lower | ||||
* bound, defined by low_index. | * bound, defined by lo, and stop at the upper bound, hi. Return the index | ||||
* of the first satisfactory free page, or -1 if none is found. | |||||
*/ | */ | ||||
static bool | static int | ||||
vm_reserv_test_contig(vm_reserv_t rv, u_long npages, vm_paddr_t low, | vm_reserv_find_contig(vm_reserv_t rv, int npages, int lo, | ||||
vm_paddr_t high, u_long alignment, vm_paddr_t boundary) | int hi, int page_align, int page_bound) | ||||
{ | { | ||||
vm_paddr_t pa, size; | |||||
u_long changes; | u_long changes; | ||||
int bitpos, bits_left, i, hi, lo, n; | int bitpos, bits_left, i, n; | ||||
vm_reserv_assert_locked(rv); | vm_reserv_assert_locked(rv); | ||||
size = npages << PAGE_SHIFT; | KASSERT(npages <= VM_LEVEL_0_NPAGES - 1, | ||||
pa = VM_PAGE_TO_PHYS(&rv->pages[0]); | ("%s: Too many pages", __func__)); | ||||
lo = (pa < low) ? | KASSERT(page_bound <= VM_LEVEL_0_NPAGES, | ||||
((low + PAGE_MASK - pa) >> PAGE_SHIFT) : 0; | ("%s: Too big a boundary for reservation size", __func__)); | ||||
KASSERT(npages <= page_bound, | |||||
("%s: Too many pages for given boundary", __func__)); | |||||
/* | |||||
* Ensure that rounding up to a alignment-multiple | |||||
* doesn't jump beyond the end of the reservation. | |||||
*/ | |||||
alc: `alignment` and `boundary` are frequently zero. | |||||
if (page_align > VM_LEVEL_0_NPAGES) | |||||
page_align = VM_LEVEL_0_NPAGES; | |||||
i = lo / NBPOPMAP; | i = lo / NBPOPMAP; | ||||
Done Inline ActionsDon't use __FUNCTION__. It was a gcc extension. Use __func__. It is standard C. alc: Don't use `__FUNCTION__`. It was a gcc extension. Use `__func__`. It is standard C. | |||||
changes = rv->popmap[i] | ((1UL << (lo % NBPOPMAP)) - 1); | changes = rv->popmap[i] | ((1UL << (lo % NBPOPMAP)) - 1); | ||||
hi = (pa + VM_LEVEL_0_SIZE > high) ? | |||||
((high + PAGE_MASK - pa) >> PAGE_SHIFT) : VM_LEVEL_0_NPAGES; | |||||
n = hi / NBPOPMAP; | n = hi / NBPOPMAP; | ||||
bits_left = hi % NBPOPMAP; | bits_left = hi % NBPOPMAP; | ||||
hi = lo = -1; | hi = lo = -1; | ||||
for (;;) { | for (;;) { | ||||
/* | /* | ||||
* "changes" is a bitmask that marks where a new sequence of | * "changes" is a bitmask that marks where a new sequence of | ||||
* 0s or 1s begins in popmap[i], with last bit in popmap[i-1] | * 0s or 1s begins in popmap[i], with last bit in popmap[i-1] | ||||
* considered to be 1 if and only if lo == hi. The bits of | * considered to be 1 if and only if lo == hi. The bits of | ||||
* popmap[-1] and popmap[NPOPMAP] are considered all 1s. | * popmap[-1] and popmap[NPOPMAP] are considered all 1s. | ||||
*/ | */ | ||||
changes ^= (changes << 1) | (lo == hi); | changes ^= (changes << 1) | (lo == hi); | ||||
while (changes != 0) { | while (changes != 0) { | ||||
/* | /* | ||||
* If the next change marked begins a run of 0s, set | * If the next change marked begins a run of 0s, set | ||||
* lo to mark that position. Otherwise set hi and | * lo to mark that position. Otherwise set hi and | ||||
* look for a satisfactory first page from lo up to hi. | * look for a satisfactory first page from lo up to hi. | ||||
*/ | */ | ||||
bitpos = ffsl(changes) - 1; | bitpos = ffsl(changes) - 1; | ||||
changes ^= 1UL << bitpos; | changes ^= 1UL << bitpos; | ||||
if (lo == hi) { | if (lo == hi) { | ||||
lo = NBPOPMAP * i + bitpos; | lo = NBPOPMAP * i + bitpos; | ||||
continue; | continue; | ||||
} | } | ||||
hi = NBPOPMAP * i + bitpos; | hi = NBPOPMAP * i + bitpos; | ||||
pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); | if (lo < roundup2(lo, page_align)) { | ||||
Done Inline ActionsWhat happens if ppn_align is 2^31, and, thus, a negative value since lo is a signed int? To be clear, we will probably never see such a value passed in our lifetimes, but a static analyzer might still flag this. alc: What happens if ppn_align is 2^31, and, thus, a negative value since lo is a signed int? To be… | |||||
Done Inline ActionsI have made a change to ensure that ppn_align and ppn_bound are in [1, VM_LEVEL_0_NPAGES]. dougm: I have made a change to ensure that ppn_align and ppn_bound are in [1, VM_LEVEL_0_NPAGES]. | |||||
if ((pa & (alignment - 1)) != 0) { | |||||
/* Skip to next aligned page. */ | /* Skip to next aligned page. */ | ||||
lo += (((pa - 1) | (alignment - 1)) + 1) >> | lo = roundup2(lo, page_align); | ||||
PAGE_SHIFT; | |||||
if (lo >= VM_LEVEL_0_NPAGES) | if (lo >= VM_LEVEL_0_NPAGES) | ||||
return (false); | return (-1); | ||||
pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); | |||||
} | } | ||||
if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) { | if (lo + npages > roundup2(lo, page_bound)) { | ||||
/* Skip to next boundary-matching page. */ | /* Skip to next boundary-matching page. */ | ||||
lo += (((pa - 1) | (boundary - 1)) + 1) >> | lo = roundup2(lo, page_bound); | ||||
PAGE_SHIFT; | |||||
if (lo >= VM_LEVEL_0_NPAGES) | if (lo >= VM_LEVEL_0_NPAGES) | ||||
return (false); | return (-1); | ||||
pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); | |||||
} | } | ||||
if (lo * PAGE_SIZE + size <= hi * PAGE_SIZE) | if (lo + npages <= hi) | ||||
return (true); | return (lo); | ||||
lo = hi; | lo = hi; | ||||
} | } | ||||
if (++i < n) | if (++i < n) | ||||
changes = rv->popmap[i]; | changes = rv->popmap[i]; | ||||
else if (i == n) | else if (i == n) | ||||
changes = bits_left == 0 ? -1UL : | changes = bits_left == 0 ? -1UL : | ||||
(rv->popmap[n] | (-1UL << bits_left)); | (rv->popmap[n] | (-1UL << bits_left)); | ||||
else | else | ||||
return (false); | return (-1); | ||||
} | } | ||||
} | } | ||||
/* | /* | ||||
* Searches the partially populated reservation queue for the least recently | * Searches the partially populated reservation queue for the least recently | ||||
* changed reservation with free pages that satisfy the given request for | * changed reservation with free pages that satisfy the given request for | ||||
* contiguous physical memory. If a satisfactory reservation is found, it is | * contiguous physical memory. If a satisfactory reservation is found, it is | ||||
* broken. Returns true if a reservation is broken and false otherwise. | * broken. Returns true if a reservation is broken and false otherwise. | ||||
*/ | */ | ||||
bool | bool | ||||
vm_reserv_reclaim_contig(int domain, u_long npages, vm_paddr_t low, | vm_reserv_reclaim_contig(int domain, u_long npages, vm_paddr_t low, | ||||
vm_paddr_t high, u_long alignment, vm_paddr_t boundary) | vm_paddr_t high, u_long alignment, vm_paddr_t boundary) | ||||
{ | { | ||||
struct vm_reserv_queue *queue; | struct vm_reserv_queue *queue; | ||||
vm_paddr_t pa, size; | vm_paddr_t pa, size; | ||||
vm_reserv_t marker, rv, rvn; | vm_reserv_t marker, rv, rvn; | ||||
int hi, lo, posn; | |||||
if (npages > VM_LEVEL_0_NPAGES - 1) | if (npages > VM_LEVEL_0_NPAGES - 1) | ||||
return (false); | return (false); | ||||
/* | |||||
* Ensure that rounding up to a boundary-multiple | |||||
* doesn't jump beyond the end of the reservation. | |||||
*/ | |||||
if (boundary > VM_LEVEL_0_SIZE) | |||||
boundary = VM_LEVEL_0_SIZE; | |||||
size = npages << PAGE_SHIFT; | |||||
/* | |||||
* Ensure that a free range starting at a boundary-multiple | |||||
* doesn't include a boundary-multiple within it. Otherwise, | |||||
* no boundary-constrained allocation is possible. | |||||
*/ | |||||
if (size > boundary) | |||||
return (false); | |||||
marker = &vm_rvd[domain].marker; | marker = &vm_rvd[domain].marker; | ||||
queue = &vm_rvd[domain].partpop; | queue = &vm_rvd[domain].partpop; | ||||
size = npages << PAGE_SHIFT; | |||||
vm_reserv_domain_scan_lock(domain); | vm_reserv_domain_scan_lock(domain); | ||||
Done Inline ActionsUnless this is needed for correctness, which I don't think it is, I don't see the point of this check. It amounts to an optimization for the unexpected case. alc: Unless this is needed for correctness, which I don't think it is, I don't see the point of this… | |||||
Done Inline ActionsIn the patch at present, when we find that the prospective range spans a multiple of boundary, we move the range start to the next multiple of boundary, and assume that the boundary constraint is satisfied. However, if the size is bigger than boundary, the boundary constraint cannot be satisfied and the code may return true anyway. So I can ignore size>boundary and just be wrong in that case, or assert size<= boundary, or keep the code as is. dougm: In the patch at present, when we find that the prospective range spans a multiple of boundary… | |||||
vm_reserv_domain_lock(domain); | vm_reserv_domain_lock(domain); | ||||
TAILQ_FOREACH_SAFE(rv, queue, partpopq, rvn) { | TAILQ_FOREACH_SAFE(rv, queue, partpopq, rvn) { | ||||
Done Inline ActionsThis is incorrect. The units for boundary are bytes, not pages. alc: This is incorrect. The units for boundary are bytes, not pages. | |||||
pa = VM_PAGE_TO_PHYS(&rv->pages[0]); | pa = VM_PAGE_TO_PHYS(&rv->pages[0]); | ||||
if (pa + VM_LEVEL_0_SIZE - size < low) { | if (pa + VM_LEVEL_0_SIZE - size < low) { | ||||
Done Inline ActionsExtra whitespace after >>. markj: Extra whitespace after `>>`. | |||||
/* This entire reservation is too low; go to next. */ | /* This entire reservation is too low; go to next. */ | ||||
Done Inline Actionsalc (vocally): dougm: alc (vocally):
use MIN, MAX macros here since sizeof(boundary) > sizeof(u_long) for some… | |||||
continue; | continue; | ||||
} | } | ||||
if (pa + size > high) { | if (pa + size > high) { | ||||
/* This entire reservation is too high; go to next. */ | /* This entire reservation is too high; go to next. */ | ||||
continue; | continue; | ||||
} | } | ||||
if ((pa & (alignment - 1)) != 0) { | |||||
/* This entire reservation is unaligned; go to next. */ | |||||
continue; | |||||
} | |||||
if (vm_reserv_trylock(rv) == 0) { | if (vm_reserv_trylock(rv) == 0) { | ||||
TAILQ_INSERT_AFTER(queue, rv, marker, partpopq); | TAILQ_INSERT_AFTER(queue, rv, marker, partpopq); | ||||
vm_reserv_domain_unlock(domain); | vm_reserv_domain_unlock(domain); | ||||
vm_reserv_lock(rv); | vm_reserv_lock(rv); | ||||
if (TAILQ_PREV(marker, vm_reserv_queue, partpopq) != | if (TAILQ_PREV(marker, vm_reserv_queue, partpopq) != | ||||
rv) { | rv) { | ||||
vm_reserv_unlock(rv); | vm_reserv_unlock(rv); | ||||
vm_reserv_domain_lock(domain); | vm_reserv_domain_lock(domain); | ||||
rvn = TAILQ_NEXT(marker, partpopq); | rvn = TAILQ_NEXT(marker, partpopq); | ||||
TAILQ_REMOVE(queue, marker, partpopq); | TAILQ_REMOVE(queue, marker, partpopq); | ||||
continue; | continue; | ||||
} | } | ||||
vm_reserv_domain_lock(domain); | vm_reserv_domain_lock(domain); | ||||
TAILQ_REMOVE(queue, marker, partpopq); | TAILQ_REMOVE(queue, marker, partpopq); | ||||
} | } | ||||
vm_reserv_domain_unlock(domain); | vm_reserv_domain_unlock(domain); | ||||
if (vm_reserv_test_contig(rv, npages, low, high, | lo = (pa >= low) ? 0 : | ||||
alignment, boundary)) { | (int)((low + PAGE_MASK - pa) >> PAGE_SHIFT); | ||||
hi = (pa + VM_LEVEL_0_SIZE <= high) ? VM_LEVEL_0_NPAGES : | |||||
(int)((high - pa) >> PAGE_SHIFT); | |||||
Done Inline ActionsRemove + PAGE_MASK. You want to round down, not up, here. Otherwise, the allocated memory could go beyond high. alc: Remove `+ PAGE_MASK`. You want to round down, not up, here. Otherwise, the allocated memory… | |||||
posn = vm_reserv_find_contig(rv, (int)npages, lo, hi, | |||||
(int)(alignment >> PAGE_SHIFT), | |||||
(int)(boundary >> PAGE_SHIFT)); | |||||
if (posn >= 0) { | |||||
pa = VM_PAGE_TO_PHYS(&rv->pages[posn]); | |||||
KASSERT((pa & (alignment - 1)) == 0, | |||||
("%s: adjusted address does not align to %lx", | |||||
__func__, alignment)); | |||||
Done Inline ActionsDeindent this. alc: Deindent this. | |||||
KASSERT((((pa ^ (pa + size - 1)) & -boundary) == 0), | |||||
alcUnsubmitted Done Inline ActionsDrop the outermost ()'s. alc: Drop the outermost ()'s. | |||||
("%s: adjusted address spans boundary to %lx", | |||||
__func__, boundary)); | |||||
Done Inline ActionsDeindent this. alc: Deindent this. | |||||
vm_reserv_domain_scan_unlock(domain); | vm_reserv_domain_scan_unlock(domain); | ||||
vm_reserv_reclaim(rv); | vm_reserv_reclaim(rv); | ||||
vm_reserv_unlock(rv); | vm_reserv_unlock(rv); | ||||
return (true); | return (true); | ||||
} | } | ||||
vm_reserv_domain_lock(domain); | vm_reserv_domain_lock(domain); | ||||
rvn = TAILQ_NEXT(rv, partpopq); | rvn = TAILQ_NEXT(rv, partpopq); | ||||
vm_reserv_unlock(rv); | vm_reserv_unlock(rv); | ||||
▲ Show 20 Lines • Show All 106 Lines • ▼ Show 20 Lines | |||||
bzero(vm_reserv_array, size); | bzero(vm_reserv_array, size); | ||||
/* | /* | ||||
* Return the next available physical address. | * Return the next available physical address. | ||||
*/ | */ | ||||
return (new_end); | return (new_end); | ||||
} | } | ||||
/* | |||||
* XXX | |||||
*/ | |||||
static vm_object_t | |||||
debug_vm_reserv_reclaim_contig_pre(void) | |||||
{ | |||||
vm_object_t object; | |||||
int i; | |||||
object = vm_object_allocate(OBJT_DEFAULT, 512); | |||||
object->flags |= OBJ_COLORED; | |||||
object->pg_color = 0; | |||||
/* | |||||
* Change the set of vm_page_alloc() calls to vary the allocated versus | |||||
* free pattern that vm_reserv_reclaim_contig() has to handle. | |||||
*/ | |||||
VM_OBJECT_WLOCK(object); | |||||
for (i = 0; i < 512; i += 17) | |||||
(void)vm_page_alloc(object, i, VM_ALLOC_NORMAL | VM_ALLOC_NOBUSY); | |||||
VM_OBJECT_WUNLOCK(object); | |||||
return (object); | |||||
} | |||||
/* | |||||
* XXX | |||||
*/ | |||||
static uint64_t | |||||
debug_vm_reserv_reclaim_contig_test(vm_object_t object) | |||||
{ | |||||
vm_reserv_t rv; | |||||
rv = LIST_FIRST(&object->rvq); | |||||
vm_reserv_lock(rv); | |||||
if (rv->object != object) { | |||||
vm_reserv_unlock(rv); | |||||
return (~(uint64_t)0); | |||||
} | |||||
vm_reserv_domain_lock(rv->domain); | |||||
if (rv->inpartpopq) { | |||||
TAILQ_REMOVE(&vm_rvd[rv->domain].partpop, rv, partpopq); | |||||
rv->inpartpopq = FALSE; | |||||
} | |||||
vm_reserv_domain_unlock(rv->domain); | |||||
uint64_t tsc = rdtscp(); | |||||
vm_reserv_reclaim_contig(rv->domain, 16, 0, 0x80000000, 0x10000, 1); | |||||
tsc = rdtscp() - tsc; | |||||
vm_reserv_unlock(rv); | |||||
return (tsc); | |||||
} | |||||
#define NOBJECTS 997 | |||||
/* | |||||
* To run a test, use the command: sysctl debug.vm_reserv_reclaim_contig=1 | |||||
*/ | |||||
static int | |||||
debug_vm_reserv_reclaim_contig(SYSCTL_HANDLER_ARGS) | |||||
{ | |||||
vm_object_t object[NOBJECTS]; | |||||
uint64_t total_tsc; | |||||
int error, i, j; | |||||
i = 0; | |||||
error = sysctl_handle_int(oidp, &i, 0, req); | |||||
if (error != 0) | |||||
return (error); | |||||
if (i != 0) { | |||||
for (j = 0; j < NOBJECTS; j++) | |||||
object[j] = debug_vm_reserv_reclaim_contig_pre(); | |||||
total_tsc = 0; | |||||
for (j = 0; j < NOBJECTS; j++) | |||||
total_tsc += debug_vm_reserv_reclaim_contig_test(object[j]); | |||||
uprintf("\ncycles/break: %lu\n", total_tsc / NOBJECTS); | |||||
for (j = 0; j < NOBJECTS; j++) | |||||
vm_object_deallocate(object[j]); | |||||
} | |||||
return (0); | |||||
} | |||||
SYSCTL_PROC(_debug, OID_AUTO, vm_reserv_reclaim_contig, CTLTYPE_INT | CTLFLAG_RW, 0, 0, | |||||
debug_vm_reserv_reclaim_contig, "I", "set to trigger vm_reserv_reclaim_contig event"); | |||||
/* | /* | ||||
* Returns the superpage containing the given page. | * Returns the superpage containing the given page. | ||||
*/ | */ | ||||
vm_page_t | vm_page_t | ||||
vm_reserv_to_superpage(vm_page_t m) | vm_reserv_to_superpage(vm_page_t m) | ||||
{ | { | ||||
vm_reserv_t rv; | vm_reserv_t rv; | ||||
Show All 11 Lines |
alignment and boundary are frequently zero.