Changeset View
Standalone View
vm_reserv.c
Show First 20 Lines • Show All 1,263 Lines • ▼ Show 20 Lines | while ((rv = TAILQ_FIRST(&vm_rvq_partpop[domain])) != NULL) { | ||||
vm_reserv_reclaim(rv); | vm_reserv_reclaim(rv); | ||||
vm_reserv_unlock(rv); | vm_reserv_unlock(rv); | ||||
return (TRUE); | return (TRUE); | ||||
} | } | ||||
return (FALSE); | return (FALSE); | ||||
} | } | ||||
/* | /* | ||||
* Determine whether this reservation has free pages that satisfy the given | |||||
* request for contiguous physical memory. Start searching from the lower | |||||
* bound, defined by low_index. | |||||
* | |||||
* The free page queue lock must be held. | |||||
*/ | |||||
static bool | |||||
markj: You can just use `bool` in new code. | |||||
vm_reserv_test_contig(vm_reserv_t rv, vm_paddr_t size, vm_paddr_t high, | |||||
int low_index, u_long alignment, vm_paddr_t boundary) | |||||
{ | |||||
vm_paddr_t pa; | |||||
u_long changes; | |||||
int bitpos, i, hi, lo; | |||||
vm_reserv_assert_locked(rv); | |||||
i = low_index / NBPOPMAP; | |||||
changes = rv->popmap[i] | ((1UL << (low_index % NBPOPMAP)) - 1); | |||||
hi = lo = -1; | |||||
for (;;) { | |||||
/* | |||||
* "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] | |||||
* considered to be 1 if and only if lo == hi. The bits of | |||||
* popmap[-1] and popmap[NPOPMAP] are considered all 1s. | |||||
*/ | |||||
changes ^= (changes << 1) | (lo == hi); | |||||
while (changes != 0) { | |||||
/* | |||||
* If the next change marked begins a run of 0s, set | |||||
* lo to mark that position. Otherwise set hi and | |||||
* look for a satisfactory first page from lo up to hi. | |||||
*/ | |||||
bitpos = ffsl(changes) - 1; | |||||
changes ^= 1UL << bitpos; | |||||
if (lo == hi) { | |||||
lo = NBPOPMAP * i + bitpos; | |||||
continue; | |||||
} | |||||
hi = NBPOPMAP * i + bitpos; | |||||
pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); | |||||
/* Skip to next aligned page. */ | |||||
lo += (((pa - 1) | (alignment - 1)) + 1) >> PAGE_SHIFT; | |||||
Done Inline ActionsI can't see anything that prevents lo from being adjusted beyond hi to satisfy alignment and boundary constraints. Then, when we check (hi - lo) * PAGE_SIZE >= size below, a negative LHS would be promoted to an unsigned paddr_t, in which case we'd return true. markj: I can't see anything that prevents `lo` from being adjusted beyond `hi` to satisfy alignment… | |||||
Not Done Inline ActionsI think there's still a problem here in that lo is not guaranteed to be an index into the current reservation after an adjustment. markj: I think there's still a problem here in that `lo` is not guaranteed to be an index into the… | |||||
Done Inline ActionsI can see lo==NBPOPMAP happening. For lo to get any higher, I think you'd need a value of alignment or boundary that's too big for reservations to support. In any case, I'd say that hi-1 is guaranteed to be an index into the reservation, and if lo < hi, we're okay. If not, we're not guiding anyone to use lo to index anything. Unless you are worried about lo wrapping around to 0. Which I briefly considered, but decided was impossible. If I'm wrong, I could add checks to make sure that the changes to lo were not decreases. dougm: I can see lo==NBPOPMAP happening. For lo to get any higher, I think you'd need a value of… | |||||
Not Done Inline ActionsI don't see anything preventing a request for, say, a 2MB allocation with 16MB alignment. Granted, that would be a bit odd, but vm_reserv_reclaim_contig() excludes requests only based on their size, not their alignment or boundary constraints. markj: I don't see anything preventing a request for, say, a 2MB allocation with 16MB alignment. | |||||
Done Inline ActionsSo in that case, we compute pa rounded up to a multiple of 16MB, and shift that down by 12, so that we're rounding lo up to a multiple of 4k, and its definitely bigger than hi now. But it hasn't overflowed, and lo * PAGE_SIZE isn't going to overflow, and the test will fail, and we'll set lo to hi and keep iterating. Other than that I haven't optimized the 16MB alignment case, I'm still not seeing what's wrong. dougm: So in that case, we compute pa rounded up to a multiple of 16MB, and shift that down by 12, so… | |||||
Not Done Inline ActionsMy concern is that we're computing VM_PAGE_TO_PHYS(&rv->pages[lo]) without having verified that lo is a valid index. If the reservation corresponds to a chunk near the end of physical memory, I think we could index beyond the end of the vm_page array and get a garbage pa. markj: My concern is that we're computing `VM_PAGE_TO_PHYS(&rv->pages[lo])` without having verified… | |||||
pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); | |||||
if (((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) { | |||||
/* Skip to next boundary-matching page. */ | |||||
lo += (((pa - 1) | (boundary - 1)) + 1) >> | |||||
PAGE_SHIFT; | |||||
pa = VM_PAGE_TO_PHYS(&rv->pages[lo]); | |||||
} | |||||
if (pa + size > high) { | |||||
/* The rest of this reservation is too high. */ | |||||
return (FALSE); | |||||
markjUnsubmitted Not Done Inline ActionsThe return value here and below can use the C99 true and false. markj: The return value here and below can use the C99 `true` and `false`. | |||||
} | |||||
if (lo * PAGE_SIZE + size <= hi * PAGE_SIZE) | |||||
return (TRUE); | |||||
lo = hi; | |||||
} | |||||
if (++i < NPOPMAP) | |||||
changes = rv->popmap[i]; | |||||
else if (i == NPOPMAP) | |||||
changes = ~0UL; | |||||
else | |||||
return (FALSE); | |||||
} | |||||
} | |||||
/* | |||||
* 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. | ||||
* | * | ||||
* The free page queue lock must be held. | * The free page queue lock must be held. | ||||
Not Done Inline ActionsIs there a reason not to just write changes = rv->popmap[n] | (-1UL << bits_left)? markj: Is there a reason not to just write `changes = rv->popmap[n] | (-1UL << bits_left)`? | |||||
Done Inline ActionsThe case n==NPOPMAP. dougm: The case n==NPOPMAP. | |||||
*/ | */ | ||||
boolean_t | boolean_t | ||||
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) | ||||
{ | { | ||||
vm_paddr_t pa, size; | vm_paddr_t pa, size; | ||||
vm_reserv_t rv, rvn; | vm_reserv_t rv, rvn; | ||||
int hi, i, lo, low_index, next_free; | int low_index; | ||||
if (npages > VM_LEVEL_0_NPAGES - 1) | if (npages > VM_LEVEL_0_NPAGES - 1) | ||||
return (FALSE); | return (FALSE); | ||||
size = npages << PAGE_SHIFT; | size = npages << PAGE_SHIFT; | ||||
vm_reserv_domain_lock(domain); | vm_reserv_domain_lock(domain); | ||||
again: | again: | ||||
for (rv = TAILQ_FIRST(&vm_rvq_partpop[domain]); rv != NULL; rv = rvn) { | for (rv = TAILQ_FIRST(&vm_rvq_partpop[domain]); rv != NULL; rv = rvn) { | ||||
rvn = TAILQ_NEXT(rv, partpopq); | rvn = TAILQ_NEXT(rv, partpopq); | ||||
Show All 13 Lines | if (vm_reserv_trylock(rv) == 0) { | ||||
if (!rv->inpartpopq) { | if (!rv->inpartpopq) { | ||||
vm_reserv_domain_lock(domain); | vm_reserv_domain_lock(domain); | ||||
if (!rvn->inpartpopq) | if (!rvn->inpartpopq) | ||||
goto again; | goto again; | ||||
continue; | continue; | ||||
} | } | ||||
} else | } else | ||||
vm_reserv_domain_unlock(domain); | vm_reserv_domain_unlock(domain); | ||||
if (pa < low) { | low_index = (pa < low) ? | ||||
/* Start the search for free pages at "low". */ | ((low + PAGE_MASK - pa) >> PAGE_SHIFT) : 0; | ||||
low_index = (low + PAGE_MASK - pa) >> PAGE_SHIFT; | if (vm_reserv_test_contig(rv, size, high, low_index, | ||||
Not Done Inline ActionsWe don't use low_index except as a parameter to vm_reserv_test_contig(). Perhaps lift its computation into the subroutine? markj: We don't use `low_index` except as a parameter to `vm_reserv_test_contig()`. Perhaps lift its… | |||||
Done Inline ActionsIn case I misinterpret "lift" here, I'll consider both possible meanings. If I want to calculate low_index in vm_reserv_test_contig(), then I have to pass additional arguments low and pa, which wouldn't be used for anything else. If I want to avoid passing low_index to vm_reserv_test_contig, then I can pass 'i' and 'changes', or 'i' and something with value low_index%NBPOPMAP that is only used to compute an initial value of 'changes'. Either way, it means an additional argument to vm_reserv_test_contig, and I don't see the value of it. But if you have a preference, tell me. dougm: In case I misinterpret "lift" here, I'll consider both possible meanings.
If I want to… | |||||
Done Inline ActionsMaybe you want me to drop the variable low_index and just pass the value dougm: Maybe you want me to drop the variable low_index and just pass the value
(pa < low) ? ((low +… | |||||
Done Inline ActionsI meant calculating low_index in vm_reserv_test_contig(). pa could simply be re-fetched in vm_reserv_test_contig(); VM_PAGE_TO_PHYS(m) is just m->phys_addr. (And we could avoid accessing rv->pages[VM_LEVEL_0_NPAGES - 1] entirely by using VM_PAGE_TO_PHYS(&rv->pages[0]) + VM_LEVEL_0_SIZE instead.) I still slightly prefer having low_index be calculated in vm_reserv_test_contig() since a low parameter has a more obvious meaning than low_index, but I don't insist on it. markj: I meant calculating low_index in vm_reserv_test_contig(). `pa` could simply be re-fetched in… | |||||
i = low_index / NBPOPMAP; | alignment, boundary)) { | ||||
hi = low_index % NBPOPMAP; | |||||
} else | |||||
i = hi = 0; | |||||
do { | |||||
/* Find the next free page. */ | |||||
lo = ffsl(~(((1UL << hi) - 1) | rv->popmap[i])); | |||||
while (lo == 0 && ++i < NPOPMAP) | |||||
lo = ffsl(~rv->popmap[i]); | |||||
if (i == NPOPMAP) | |||||
break; | |||||
/* Convert from ffsl() to ordinary bit numbering. */ | |||||
lo--; | |||||
next_free = NBPOPMAP * i + lo; | |||||
pa = VM_PAGE_TO_PHYS(&rv->pages[next_free]); | |||||
KASSERT(pa >= low, | |||||
("vm_reserv_reclaim_contig: pa is too low")); | |||||
if (pa + size > high) { | |||||
/* The rest of this reservation is too high. */ | |||||
break; | |||||
} else if ((pa & (alignment - 1)) != 0 || | |||||
((pa ^ (pa + size - 1)) & ~(boundary - 1)) != 0) { | |||||
/* | |||||
* The current page doesn't meet the alignment | |||||
* and/or boundary requirements. Continue | |||||
* searching this reservation until the rest | |||||
* of its free pages are either excluded or | |||||
* exhausted. | |||||
*/ | |||||
hi = lo + 1; | |||||
if (hi >= NBPOPMAP) { | |||||
hi = 0; | |||||
i++; | |||||
} | |||||
continue; | |||||
} | |||||
/* Find the next used page. */ | |||||
hi = ffsl(rv->popmap[i] & ~((1UL << lo) - 1)); | |||||
while (hi == 0 && ++i < NPOPMAP) { | |||||
if ((NBPOPMAP * i - next_free) * PAGE_SIZE >= | |||||
size) { | |||||
vm_reserv_reclaim(rv); | vm_reserv_reclaim(rv); | ||||
vm_reserv_unlock(rv); | vm_reserv_unlock(rv); | ||||
return (TRUE); | return (TRUE); | ||||
} | } | ||||
hi = ffsl(rv->popmap[i]); | |||||
} | |||||
/* Convert from ffsl() to ordinary bit numbering. */ | |||||
if (i != NPOPMAP) | |||||
hi--; | |||||
if ((NBPOPMAP * i + hi - next_free) * PAGE_SIZE >= | |||||
size) { | |||||
vm_reserv_reclaim(rv); | |||||
vm_reserv_unlock(rv); | |||||
return (TRUE); | |||||
} | |||||
} while (i < NPOPMAP); | |||||
vm_reserv_unlock(rv); | vm_reserv_unlock(rv); | ||||
vm_reserv_domain_lock(domain); | vm_reserv_domain_lock(domain); | ||||
if (rvn != NULL && !rvn->inpartpopq) | if (rvn != NULL && !rvn->inpartpopq) | ||||
goto again; | goto again; | ||||
} | } | ||||
vm_reserv_domain_unlock(domain); | vm_reserv_domain_unlock(domain); | ||||
return (FALSE); | return (FALSE); | ||||
} | } | ||||
▲ Show 20 Lines • Show All 120 Lines • Show Last 20 Lines |
You can just use bool in new code.