LWN: Comments on "The next steps for the maple tree"

The next steps for the maple tree

jedix — Tue, 28 May 2024 13:39:11 +0000

I think this isn't a concern as the guard would be included within the vma guards.

Also, for reference it seems what I was thinking of was for arm:
https://lore.kernel.org/all/Pine.LNX.4.61.0504070210430.2...

The next steps for the maple tree

david.hildenbrand — Tue, 28 May 2024 11:23:48 +0000

As raised, Jann Horn played with that idea and I remember he had a prototype, see https://lore.kernel.org/lkml/CAG48ez2NrQjB5T5++uJSZ8-id5-...

MADV_GUARD might be a more appropriate name.

I have a related project on my back burner to tackle optimize very sparse VMAs (raised in reply to Jann's mail), that I discussed in the bi-weekly MM meeting. While my initial idea was to similarly use PTE markers, I'm investigating using using something like sparse bitmaps instead. Other things keep interrupting me, so I did not yet have time to do more work on that. But the focus is a bit different than having only a handful of guard pages (MADV_GUARD might be more appropriate for that).

The next steps for the maple tree

jedix — Tue, 28 May 2024 02:31:52 +0000

One potential issue is that some platforms (I believe MIPS?) can have PTEs outside of the areas mapped by the VMAs. This is why, when we munmap, we use the start of the next VMA and the end of the previous VMA as the area being unmapped (and passed through to free_pgtables() in unmap_region()). If we have special PTEs mapped in that area for other uses, we would need to work around the free_pgtables() using the extended range beyond the VMAs to avoid including these new mappings when removing the next VMA. The arguments passed through to free_pgtables() is already a mess.

The next steps for the maple tree

vbabka — Mon, 27 May 2024 20:11:29 +0000

During the session I have proposed an alternative to guard VMAs (which AFAIU is a VMA with mprotect() set to PROT_NONE). What should be enough to catch the stray accesses before/after the VMA would be to have the respective entries in page tables (PTE) marked as such. But because we match protections on VMAs and PTEs, once userspace e.g. creates a larger VMA that includes the guard pages and then mprotect(PROT_NONE) the boundary pages, the kernel will split the VMA into 3.

Instead we could extend e.g. madvise() with two new modes (tentatively called MADV_POISON and MADV_REMEDY) that would only mark the PTE's into something that behaves like PROT_NONE, or undoes this. Since there would be no actual page mapped (pfn) for them, it could be implemented as a new special swap type (such as e.g. migration entries are) to avoid the hassle of distinguishing it from other PROT_NONE marked entries such as those used for NUMA balancing. The page fault handler would recognize this and cause a segfault. This would avoid the VMA splitting. Users could also do this to pages in the middle of a VMA, not just boundaries i.e. in a userspace malloc implementation to catch a use-after-free. In that sense MADV_POISON would extend MADV_DONTNEED in that the PTE is zapped before setting the special swap type.

Has something like that been tried before? Any obvious gotchas? It could be also done with userfaultfd but that adds its own overhead to all the page faults.

The next steps for the maple tree

jedix — Mon, 27 May 2024 20:07:12 +0000

"we end up in a situation that is both not empty and not usable" should read

"we end up in a situation that is both empty and not usable"

The next steps for the maple tree

jedix — Mon, 27 May 2024 18:32:45 +0000

For the guard areas, there are two issues:
1. guard VMAs are used to catch writes beyond a particular VMA
2. some VMAs that grow have unusable areas that are outside the range but are still unusable.

The first issue is primarily about the inflated memory use and counting towards the mm->map_count limit of a VMA.

The second issue is about how we track gaps. Since this area is considered fully usable from the trees point of view, we end up in a situation that is both not empty and not usable; an empty area can be found to place allocations but the search must continue for a place that is actually usable. This is a lot like the upper and lower bound issue, but not entirely the same as the area can more easily shift (annoyingly, upper and lower bounds can also shift).