mmap-alloc: Support the full Alloc API

[Dr-Emann]

We implement the usable_size function, which allows us to implement alloc/dealloc, and get correct implementations of alloc_excess, grow_in_place, and shrink_in_place for free.

Additionally, for linux, we implement realloc, grow_in_place, and shrink_in_place using mremap.

Fixes #9

Open Questions:

• When allocating with mmap, we check if mmap returns a null pointer, and handle that case. Currently, this implementation panics if mremap returns a null pointer. Should we handle this case?
  • As far as I can tell, the only way to recover is to to make another mmap, and memcpy (which may not even handle null pointers? we might be really fighting the optimizer no mater what we do), or try to pre-map a page at 0 manually beforehand).
  • Posix specifies for mmap, which seems to indicate mmap at least, should never return null (unless we ask for it), and we might want to assume the same applies to mremap?

    When the implementation selects a value for pa, it never places a mapping at address 0, nor does it replace any extant mapping`

[joshlf]

This looks fantastic! I'm looking through now and adding comments.

[joshlf]

When allocating with mmap, we check if mmap returns a null pointer, and handle that case. Currently, this implementation panics if mremap returns a null pointer. Should we handle this case?

I think we might be able to do something similar to what we do now for allocations, which is to unmap all but the first page, leaving the first page permanently mapped (even beyond when the allocator itself is gone), thus ensuring that no future call to mmap or mremap will ever place a mapping there. The logic will be a bit tricker with realloc than with alloc, but I expect that the same basic idea should work. What are your thoughts on that?

[joshlf]

Nitpick: You probably shouldn't use backticks in the commit message since commit messages are always rendered as raw text rather than markdown.

[Dr-Emann]

It should be possible. It seems we'd have to do the following:

1. mmap a new allocation
2. use inline asm to copy the value at 0 (llvm says dereferencing a null pointer is always UB. I'd expect that applies to memcpy as well)
3. memcpy the bytes from 1..pagesize
4. mremap from pagesize..full_size with MREMAP_FIXED into the new mmap allocation (pending verification that it's allowed to call mremap on a subset of a mapping)
5. Use mark_unused to mark the page at 0 as unused again

[joshlf]

2. use inline asm to copy the value at 0 (llvm says dereferencing a null pointer is always UB. I'd expect that applies to memcpy as well)

Ooph. And we'd have to do that separately for each ASM target. I wonder if there's a way around that using the syscalls available to us? I'm trying to figure out if we could get the kernel to do the copy for us so we wouldn't have to deal with the ASM.

[joshlf]

Actually, how about this: When doing realloc, we preemptively save the first byte of the allocation in a local variable in case we encounter the 0 page issue, and that way we've already got it and don't have to read it out of the address 0?

[Dr-Emann]

How should I handle the case where there isn't read permission on the original mapping? It would be unfortunate to have to run an mprotect to allow reading, then reset back on every remap, just in case we get null back.

Could we mremap the whole mapping over the new mmap'd section, then manually mmap a single page to 0? (I'm assuming if mremap is going to hand us a mapping starting at 0, we should be able to mmap (with MAP_FIXED) a new page at 0 as well)

[joshlf]

How should I handle the case where there isn't read permission on the original mapping? It would be unfortunate to have to run an mprotect to allow reading, then reset back on every remap, just in case we get null back.

Ah, that's a good point. Would it be possible to do the mprotect dance only when we get the null issue? That way we'd keep it out of the fast path.

EDIT: This also raises an interesting point about how this plays with the default implementation of realloc on platforms other than Linux.

Could we mremap the whole mapping over the new mmap'd section, then manually mmap a single page to 0?

I'm not sure I follow.

[joshlf]

The new version looks pretty good, but I still have a concern about the way we're copying data. If I'm not mistaken, if the new size is larger than the old size, the behavior of mremap is to extend the end of the allocation. This means that when we remap starting at the first (rather than 0th) page, we're going to end up with a new mapping whose first n - 1 pages have the same contents as the original mapping's last n - 1 pages, and whose last page is initialized to 0. Instead what we want is for its last n - 1 pages to have the same contents as the original mapping's last n - 1 pages, and then to memcpy the first page of the original mapping (the 0th page) to the first page of the new mapping.

[Dr-Emann]

The mremap call in fix_null should not be performing any resizing: only movement. It is supposed to move the last n - 1 pages into the last n - 1 pages of the new mapping (by using MREMAP_FIXED, with a target address of new_ptr + allocator.page_size). This should leave the first page of new_ptr zero-filled, which we then memcpy the page at NULL onto.

[joshlf]

Yeah, I realize that now - see my other comment inline in the code.

[joshlf]

Can you change allocator variables named allocator to be named alloc instead? That's the convention that's been used around the Alloc trait so far.

[DemiMarie]

I strongly recommend not mapping page 0. Many operating systems simply do not allow it, period. Linux only allows it if one has root privileges. Finally, the unmapped zero page is a critical security feature: it ensures that NULL pointer dereferences are merely denial of service.

[joshlf]

@DemiMarie I think you're misunderstanding how we use page 0. We never explicitly map it, but we do have to handle the case in which mmap (or VirtualAlloc on Windows) returns 0. In that case, we leave it mapped (to ensure that future mappings won't return 0, forcing us to go through the slow path again), but we set its permissions to PROT_NONE so that any future accesses will result in a segfault.

To be fair, we only do this on Linux and Mac, and we should do it on Windows as well. I'll open an issue for that.

[joshlf]

Opened; see #72.

[joshlf]

I realized we have a few bugs. Namely:

• If the allocation is 0-sized, we still read the 0th byte before reallocating
• If the allocation size is less than a page, we still memcpy the whole page.

[Dr-Emann]

I don't think linux allows 0 sized allocations for memory maps, so we should always have at least a byte available.

[joshlf]

Actually, it looks like we're allowed to have 0-sized allocation requests cause UB. From the Alloc trait docs:

many methods in the Alloc trait state that allocation requests must be non-zero size, or else undefined behavior can result.

[joshlf]

Hey, looks like I merged a bit prematurely. In testing some work I'm doing now, I'm hitting this assertion. What's the reasoning behind it?

[Dr-Emann]

I was hoping that resizing from big to small, then back to big would all be able to be done in place. But I suppose with other threads running tests, there's no way of guaranteeing that reallocation will happen in place.

[joshlf]

Hmm that's interesting. When I go back and test now, the tests consistently pass on master (ie, on the code in this PR) but that comparison fails in my PR even when run on its own (not in parallel with any other tests). Must have been something I added.