Differential D13155
Do not loop infinitely in vm_map_find(). Authored by kib on Nov 19 2017, 12:19 PM. Tags None Referenced Files
Details If we do not change the start address, there is no reason to retry when the previous attempt failed. I believe that the loop iterations there should not occur more that twice, but I prefer to check for the start modifications instead, to keep the loop structure for further changes.
Diff Detail
Event Timeline
Comment Actions I'm presuming that this change is motivated by something in the ALSR/ASR patch. Otherwise, in isolation, i.e., not looking at the ALSR/ASR patch, I don't really see the point of this change. There is nothing incorrect about the added explicit test, but I would characterize it as pessimizing the expected case. In other words, the expected case is that vm_map_insert() succeeds. Failures should be the exception and the run-time cost of a failure is not great. So, why introduce a test that will be false in the expected case? Comment Actions I think that the change to avoid dropping the lock is straightforward, i.e., it doesn't make the control flow any more convoluted. Index: vm/vm_map.c =================================================================== --- vm/vm_map.c (revision 326016) +++ vm/vm_map.c (working copy) @@ -1511,18 +1511,18 @@ vm_map_find(vm_map_t map, vm_object_t object, vm_o } else alignment = 0; initial_addr = *addr; + vm_map_lock(map); again: start = initial_addr; - vm_map_lock(map); do { if (find_space != VMFS_NO_SPACE) { if (vm_map_findspace(map, start, length, addr) || (max_addr != 0 && *addr + length > max_addr)) { - vm_map_unlock(map); if (find_space == VMFS_OPTIMAL_SPACE) { find_space = VMFS_ANY_SPACE; goto again; } + vm_map_unlock(map); return (KERN_NO_SPACE); } switch (find_space) { Comment Actions It came out of this bug report: https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=223732 In particular, the do-while loop's test doesn't really handle the case where find_space specifies an alignment. That change looks ok to me. Comment Actions Yes, I fixed this in a way which does not require complete rewrite of the ASR patch. I tried to note this in the revision annotation, in somewhat vague form. The relock elimination should be the next change, or you may commit it now, it looks fine. Comment Actions Hmm, the assumption was that when aligning a request, if the alignment moved the address such that it didn't fit, it would fail to insert and we would retry starting at the aligned address and progressively moving "farther" along in the address space until vm_findspace() failed. VMFS_SUPER_SPACE and VMFS_OPTIMAL_SPACE work the same way (pmap_align_superpage() just moves the address up). Do we know why vm_map_stack_locked() is failing in the looping case?
Comment Actions The request was made for large allocation with large alignment. [Removed nonsense]
Comment Actions I was more asking about which of the 'return (foo)' paths triggered in vm_map_stack_locked(), as the process of progressively walking the address space is used for VMFS_SUPER_SPACE and VMFS_OPTIMAL_SPACE (which is the default for mmap), not just for MAP_ALIGNED(). It's not clear to me why you couldn't get a similar hang if you used a large allocation with MAP_STACK with just VMFS_OPTIMAL_SPACE? The infinite loop in that case should result in never falling back to VMFS_ANY_SPACE?
Comment Actions Mmm, yes, in the case of the test program I have the issue is that KERN_NO_SPACE is returned for guard page size check failure, see D13186. So D13186, which returns a code different from KERN_NO_SPACE, would break the loop in this case. What I do not like is that this loop makes KERN_NO_SPACE only allowed when there is an intersection of the tried mapping and some existing map entry. We usually allow for more flexible interpretation of the error codes, not prohibiting error codes just because some place makes specific use of specific code. So I think that a check to avoid a stuck step for the loop in vm_map_find() is the good generic fix, while D13186 cover only very specific bug, there might be more just undetected. Comment Actions Should we have an explicit check for address wrap resulting from the various alignment options? On architectures where the kernel address space uses the upper portion of the virtual address space and we disallow the use of virtual page 0, I believe that we are inherently protected from all cases of address wrap within the user address space. However, should this code be implicitly relying on those assumptions? Comment Actions We can reserve the page at the top of the KVA to avoid the wrap, automatically and without the added checks. Comment Actions Yes, most of the time that approach will work, but what about the following scenario. Suppose that X is the requested alignment, and the specified address is greater than (unsigned)-X but less than the maximum possible address. Address wrap will occur before the first call to vm_map_insert(), so we also have to ensure that the kernel map never includes virtual page 0. Let's do this. Comment Actions Ok.
Could you, please, be more specific about 'this' ? What do you propose to do:
Comment Actions I would perhaps modify this patch to panic (maybe KASSERT()) in debug kernels as I think an infinite loop probably indicates a bug elsewhere, but I think it is fine for production kernels to fail with an error from mmap() rather than hanging. My guess response to your last question Konstantin from reading Alan's comments is 4), that Alan would like explicit checks. I think that is pretty simple to do as you would just cache '*addr' before the switch on find_space and check for '*addr < saved_addr' after the switch and fail with KERN_NO_SPACE if it is true. Comment Actions Follow John' explanations:
An issue with the patch is that prev_start is write-only in non-debugging kernels. Comment Actions Mmm, you'd have to put prev_start under #ifdef INVARIANTS I guess, either that or do this: if (result != KERN_SUCCESS && start <= prev_start) {
#ifdef INVARIANTS
panic("vm_map_findspace infinite loop");
#endif
vm_map_unlock(map);
return (KERN_NO_SPACE);
}Comment Actions Do we ever have a place where non-debugging kernel works (and perhaps returns an error to userspace), but panics in debugging config ? Note that this is not how normal assertion works: we do not detect a situation and then handle it for non-debug, we only detect it for panic, as an additional service for developer. Comment Actions We do not, I just wasn't sure how careful/paranoid we wanted to be. I think it's fine to just use an assert. Comment Actions Sorry, let me clarify my position. I don't think that #1 by itself solves address wrap problems resulting from the alignment code. I tried to describe why in the quoted text above. Instead, we would have to exclude address 0, i.e., implement #2. However, there are legitimate cases where we want to allow address 0 in the vm map, e.g., bhyve's guest physical address space. So, I see no other option besides #4, explicit checks. Comment Actions Set aside the proposed change for a moment. Suppose that find_space == VMFS_OPTIMAL_SPACE, that we are approaching the end of the address space, and that vm_map_findspace() succeeds. However, the address is not optimally aligned, so pmap_align_superpage() adjusts the address (upward). I believe that vm_map_insert() could return KERN_INVALID_ARGUMENT because the adjusted address plus length wraps, and as a result the loop terminates whereas it should have restarted after updating find_space. Comment Actions I decided to remove the reciprocally-nesting loops from vm_map_find(). By coalescing the place where VMFS_OPTIMAL_SPACE is converted into VMFS_ANY_SPACE attempt, it should solve the issue you pointed out.
Comment Actions The vm_map_find_min() comment looks ready for committing.
Comment Actions In both the unmodified and modified versions of this code, it appears to me that a call requesting alignment can fail returning KERN_INVALID_ADDRESS. This is a minor issue compared to the others that we've discussed, but I still think that this function should only return KERN_INVALID_ADDRESS when VMFS_NO_SPACE was specified. More generally, I've come to the conclusion that speculatively calling vm_map_insert() is more trouble than it's worth. I'm tinkering with an alternate implementation where the loop consists of two steps: (1) alignment and (2) vm_map_findspace(). The loop terminates when either step does not result in any change to the address, so the sanity check proposed here is a regular part of the control flow. This approach does introduce an additional call to vm_map_findspace(), that the speculative vm_map_insert() call avoided. However, in situations where the speculative vm_map_insert() call would have succeeded, the extra call to vm_map_findspace() will complete in constant time, because the map entry we are checking to verify that there is still sufficient space at the now aligned address is at the root of the tree. I'll post something shortly. Comment Actions I also considered doing vm_map_findspace() after the realignment, but decided that it pessimization for the common case. My feel is that it is rare to have tightly fragmented address space or to allocate from the fragmented part of the address space, so typically vm_map_insert() would just succeed. Adding one more vm_map_findspace() (we cannot remove the first one without seriously degrading the search) did not felt right. Comment Actions Here is what I have: if (find_space >> 8 != 0) {
KASSERT((find_space & 0xff) == 0, ("bad VMFS flags"));
alignment = (vm_offset_t)1 << (find_space >> 8);
} else
alignment = 0;
vm_map_lock(map);
if (find_space != VMFS_NO_SPACE) {
min_addr = *addr;
again:
if (vm_map_findspace(map, min_addr, length, addr) ||
(max_addr != 0 && *addr + length > max_addr)) {
rv = KERN_NO_SPACE;
goto done;
}
while (find_space != VMFS_ANY_SPACE) {
/*
* At the start of every iteration, the free space at
* address "*addr" is at least "length" bytes.
*/
orig_addr = *addr;
if (find_space == VMFS_SUPER_SPACE ||
find_space == VMFS_OPTIMAL_SPACE) {
pmap_align_superpage(object, offset, addr,
length);
} else if ((*addr & (alignment - 1)) != 0) {
*addr &= ~(alignment - 1);
*addr += alignment;
}
aligned_addr = *addr;
if (aligned_addr == orig_addr) {
/*
* Alignment did not change "*addr", so
* "*addr" must still provide sufficient
* free space.
*/
break;
}
/*
* Test for address wrap on "*addr". A wrapped
* "*addr" could be a valid address, in which case
* vm_map_findspace() cannot be relied upon to fail.
*/
if (aligned_addr < orig_addr ||
vm_map_findspace(map, aligned_addr, length,
addr) ||
(max_addr != 0 && *addr + length > max_addr)) {
if (find_space == VMFS_OPTIMAL_SPACE) {
find_space = VMFS_ANY_SPACE;
goto again;
}
rv = KERN_NO_SPACE;
goto done;
}
if (*addr == aligned_addr) {
/*
* If a successful call to vm_map_findspace()
* did not change "*addr", then "*addr" must
* still be aligned and provide sufficient
* free space.
*/
break;
}
}
}
if ((cow & (MAP_STACK_GROWS_DOWN | MAP_STACK_GROWS_UP)) != 0) {
rv = vm_map_stack_locked(map, *addr, length, sgrowsiz, prot,
max, cow);
} else {
rv = vm_map_insert(map, object, offset, *addr, *addr + length,
prot, max, cow);
}
done:
vm_map_unlock(map);
return (rv);Comment Actions Essentially, the "redundant" call to vm_map_findspace() provides the rest of the address wrap checks: /*
* Request must fit within min/max VM address and must avoid
* address wrap.
*/
if (start < map->min_offset)
start = map->min_offset;
if (start + length > map->max_offset || start + length < start)
return (1);
/* Empty tree means wide open address space. */
if (map->root == NULL) {
*addr = start;
return (0);
}
/*
* After splay, if start comes before root node, then there
* must be a gap from start to the root.
*/
map->root = vm_map_entry_splay(start, map->root);
if (start + length <= map->root->start) {
*addr = start;
return (0);
}And, even if alignment changed the address, as long as the free space preceding the root is sufficiently large, the redundant call completes in constant time. The splay is not going to restructure the tree. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||