Changeset View
Standalone View
sys/vm/vm_reserv.c
Show First 20 Lines • Show All 1,227 Lines • ▼ Show 20 Lines | if (rv != NULL) { | ||||
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 ppn_align, int ppn_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__)); | ||||
alc: Don't use `__FUNCTION__`. It was a gcc extension. Use `__func__`. It is standard C. | |||||
lo = (pa < low) ? | KASSERT(ppn_bound <= VM_LEVEL_0_NPAGES, | ||||
((low + PAGE_MASK - pa) >> PAGE_SHIFT) : 0; | ("%s: Too big a boundary for reservation size", __func__)); | ||||
KASSERT(npages <= ppn_bound, | |||||
("%s: Too many pages for given boundary", __func__)); | |||||
KASSERT(ppn_align != 0 && powerof2(ppn_align), | |||||
("ppn_align is not a positive power of 2")); | |||||
KASSERT(ppn_bound != 0 && powerof2(ppn_bound), | |||||
("ppn_bound is not a positive power of 2")); | |||||
Not Done Inline Actionsalignment and boundary are frequently zero. alc: `alignment` and `boundary` are frequently zero. | |||||
i = lo / NBPOPMAP; | i = lo / NBPOPMAP; | ||||
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, ppn_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, ppn_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, ppn_bound)) { | ||||
/* Skip to next boundary-matching page. */ | /* Skip to next boundary-matching page. */ | ||||
lo += (((pa - 1) | (boundary - 1)) + 1) >> | lo = roundup2(lo, ppn_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, ppn_align, ppn_bound; | |||||
KASSERT(npages > 0, ("npages is 0")); | |||||
KASSERT(powerof2(alignment), ("alignment is not a power of 2")); | |||||
KASSERT(powerof2(boundary), ("boundary is not a power of 2")); | |||||
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… | |||||
if (npages > VM_LEVEL_0_NPAGES - 1) | if (npages > VM_LEVEL_0_NPAGES - 1) | ||||
return (false); | return (false); | ||||
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. | |||||
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; | /* | ||||
* Compute shifted alignment, boundary values for page-based | |||||
* calculations. Constrain to range [1, VM_LEVEL_0_NPAGES] to | |||||
* avoid overflow. | |||||
*/ | |||||
ppn_align = (int)(ulmin(ulmax(PAGE_SIZE, alignment), | |||||
VM_LEVEL_0_SIZE) >> PAGE_SHIFT); | |||||
Done Inline ActionsExtra whitespace after >>. markj: Extra whitespace after `>>`. | |||||
ppn_bound = (int)(MIN(MAX(PAGE_SIZE, boundary), | |||||
Done Inline Actionsalc (vocally): dougm: alc (vocally):
use MIN, MAX macros here since sizeof(boundary) > sizeof(u_long) for some… | |||||
VM_LEVEL_0_SIZE) >> PAGE_SHIFT); | |||||
vm_reserv_domain_scan_lock(domain); | vm_reserv_domain_scan_lock(domain); | ||||
vm_reserv_domain_lock(domain); | vm_reserv_domain_lock(domain); | ||||
TAILQ_FOREACH_SAFE(rv, queue, partpopq, rvn) { | TAILQ_FOREACH_SAFE(rv, queue, partpopq, rvn) { | ||||
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) { | ||||
/* This entire reservation is too low; go to next. */ | /* This entire reservation is too low; go to next. */ | ||||
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); | ||||
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… | |||||
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); | |||||
posn = vm_reserv_find_contig(rv, (int)npages, lo, hi, | |||||
ppn_align, ppn_bound); | |||||
if (posn >= 0) { | |||||
pa = VM_PAGE_TO_PHYS(&rv->pages[posn]); | |||||
Done Inline ActionsDeindent this. alc: Deindent this. | |||||
KASSERT((pa & (alignment - 1)) == 0, | |||||
Done Inline ActionsDrop the outermost ()'s. alc: Drop the outermost ()'s. | |||||
("%s: adjusted address does not align to %lx", | |||||
__func__, alignment)); | |||||
Done Inline ActionsDeindent this. alc: Deindent this. | |||||
KASSERT(((pa ^ (pa + size - 1)) & -boundary) == 0, | |||||
("%s: adjusted address spans boundary to %lx", | |||||
__func__, boundary)); | |||||
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 133 Lines • Show Last 20 Lines |
Don't use __FUNCTION__. It was a gcc extension. Use __func__. It is standard C.