4 ms·

> Yes, the memory->tag mapping has to be stored somewhere, but that's true even for a segmented system, right? You need some place to store the segment offset a

by DSMan195276 9y ago

> Yes, the memory->tag mapping has to be stored somewhere, but that's true even for a segmented system, right? You need some place to store the segment offset and length: either some dedicated registers if you only allow a few of them, or some in-memory tables for more general schemes, right? Not if your segments/tags are static and defined beforehand, which is what I thought that were going for (Since that doesn't require any extra memory). But obviously that approach is pretty limited, which was my thinking. > Yeah they don't really get into how the shadow memory is managed. If you only had limited or no hardware support, it seems like it would be tricky, especially when you are arbitrarily mapping various chunks of the address space. The ideal for performance is that there is some straightforward relationship between a pointed-to region and the associated tag bits, e.g., just shift the pointer down by lg(TG) bits and then index into a single contiguous region which stores the tag bits, pointed to by some global. This is exactly what I'm thinking as well. If the platform has paging support, in theory this is cheaper then it seems because (besides using up tons of virtual memory) the array can be sparsely allocated, with only the regions actually in used taking up physical memory. But 64bytes is still really coarse, it might be necessary to use a multi-level approach to make the size a bit saner. But since it is just virtual memory, depending on the architecture it may not matter. Storing it in the page table mappings themselves is an interesting idea. Of course, some architectures have more 'free' space in there then others. And at that point you're talking about likely 4K granularity, not 64 bytes. Still better then nothing of course, but it would definitely decrease the effectiveness for smaller objects. > I didn't see much about kernel-side checks in the paper? Maybe I missed it. The kernel already checks that user pointers are valid in the context of the process that provided them, but of course that is a very coarse check (can the user process as a whole read/write here?), and could still violate semantic memory safety of the process depending on what was passed. Someone else asked about this as well, it seems I was led astray. The paper has this line about ASAN: Does not currently detect when the kernel accesses invalid user-space memory From reading that, I thought they were then going to use their memory tagging system to do such checking (And in theory you could do it as long as the kernel knew about the mappings). But they never actually bring this up again in the paper.

BeeOnRope 9y ago
> This is exactly what I'm thinking as well. If the platform has paging support, in theory this is cheaper then it seems because (besides using up tons of virtual memory) the array can be sparsely allocated, with only the regions actually in used taking up physical memory. Yes exactly. The worse case still seems like a doubling of (actual) memory use though: imagine a very sparsely accessed region of memory: even today each access would bring in a whole 4K page (on x86, for example), but now you'd bring in a whole 4K shadow page as well (yes, the access has to be really sparse to get this 1:1 ratio). > And at that point you're talking about likely 4K granularity, not 64 bytes. Still better then nothing of course, but it would definitely decrease the effectiveness for smaller objects. I think a 4K granularity is next to useless - you already get that from the hardware/OS paging support. If you want to detect problems on a 4K level, you only need to change your allocator to mmap in a page at a time, which you can even already do on some with tunable ones.
- DSMan195276 9y ago
  > Yes exactly. The worse case still seems like a doubling of (actual) memory use though: imagine a very sparsely accessed region of memory: even today each access would bring in a whole 4K page (on x86, for example), but now you'd bring in a whole 4K shadow page as well (yes, the access has to be really sparse to get this 1:1 ratio). In theory you should be partially saved by the allocator, just because it is going to try and place as much stuff as it can into every page it allocates, as well as allocate multiple pages at once (So they all end-up in a row). An allocator that was aware of the 'shadow' pages should be able to allocate chunks of pages at once that correspond to a single 'shadow' page, ensuring you avoid creating tons of them. The higher alignment requirements mean more wasted memory though, meaning you need to allocate more pages and need then need more 'shadow' pages overall. The paper suggests anywhere between 14% and 18% RAM overhead (discounting Android apps, which had a range from 6% to 42%) for 64 byte granularity, and that it actually goes down if you choose a smaller granularity like 16, due to the lower alignment requirement. And of course, you're also talking about doubling memory accesses as well, assuming this is done in software. Every access has to first check the 'shadow' page. Unfortunately both of their implementations are at least partially hardware assisted, so I'm not sure you can use those numbers to just a pure CPU implementation, but they suggest around a 2x slowdown. > I think a 4K granularity is next to useless - you already get that from the hardware/OS paging support. If you want to detect problems on a 4K level, you only need to change your allocator to mmap in a page at a time, which you can even already do on some with tunable ones. I would agree. The tagging system can prevent a higher percentage of OOB accesses at the page level in theory, but considering the size of the address-space vs the number of allocations (assuming a 64-bit/48-bit address space) I think the likelihood of an OOB access actually hitting another separate allocation (assuming a mostly random placement) is already pretty low, so the tagging system would make it lower (You now have to hit a random allocation with the correct tag) but not significantly lower then before, and at the cost of performance.

BeeOnRope 9y ago

> This is exactly what I'm thinking as well. If the platform has paging support, in theory this is cheaper then it seems because (besides using up tons of virtual memory) the array can be sparsely allocated, with only the regions actually in used taking up physical memory. Yes exactly. The worse case still seems like a doubling of (actual) memory use though: imagine a very sparsely accessed region of memory: even today each access would bring in a whole 4K page (on x86, for example), but now you'd bring in a whole 4K shadow page as well (yes, the access has to be really sparse to get this 1:1 ratio). > And at that point you're talking about likely 4K granularity, not 64 bytes. Still better then nothing of course, but it would definitely decrease the effectiveness for smaller objects. I think a 4K granularity is next to useless - you already get that from the hardware/OS paging support. If you want to detect problems on a 4K level, you only need to change your allocator to mmap in a page at a time, which you can even already do on some with tunable ones.

DSMan195276 9y ago
> Yes exactly. The worse case still seems like a doubling of (actual) memory use though: imagine a very sparsely accessed region of memory: even today each access would bring in a whole 4K page (on x86, for example), but now you'd bring in a whole 4K shadow page as well (yes, the access has to be really sparse to get this 1:1 ratio). In theory you should be partially saved by the allocator, just because it is going to try and place as much stuff as it can into every page it allocates, as well as allocate multiple pages at once (So they all end-up in a row). An allocator that was aware of the 'shadow' pages should be able to allocate chunks of pages at once that correspond to a single 'shadow' page, ensuring you avoid creating tons of them. The higher alignment requirements mean more wasted memory though, meaning you need to allocate more pages and need then need more 'shadow' pages overall. The paper suggests anywhere between 14% and 18% RAM overhead (discounting Android apps, which had a range from 6% to 42%) for 64 byte granularity, and that it actually goes down if you choose a smaller granularity like 16, due to the lower alignment requirement. And of course, you're also talking about doubling memory accesses as well, assuming this is done in software. Every access has to first check the 'shadow' page. Unfortunately both of their implementations are at least partially hardware assisted, so I'm not sure you can use those numbers to just a pure CPU implementation, but they suggest around a 2x slowdown. > I think a 4K granularity is next to useless - you already get that from the hardware/OS paging support. If you want to detect problems on a 4K level, you only need to change your allocator to mmap in a page at a time, which you can even already do on some with tunable ones. I would agree. The tagging system can prevent a higher percentage of OOB accesses at the page level in theory, but considering the size of the address-space vs the number of allocations (assuming a 64-bit/48-bit address space) I think the likelihood of an OOB access actually hitting another separate allocation (assuming a mostly random placement) is already pretty low, so the tagging system would make it lower (You now have to hit a random allocation with the correct tag) but not significantly lower then before, and at the cost of performance.