4 ms·

Reading it again, I guess I missed the "shadow memory" concept they talked about, but they only mention it 5 times and none of those mentions are in the actuall

by DSMan195276 9y ago

Reading it again, I guess I missed the "shadow memory" concept they talked about, but they only mention it 5 times and none of those mentions are in the actually explanation of how they do the memory tagging. They do mention it one more time in the AArch64 implementation though, so it does look like you're correct on this. I don't understand why they didn't really make this detail much more clear though, since like you've pointed out it changes a lot about how things work. Now, if that is the case it complicates the setup a fair amount, since now you do need a global 'page-table' like structure holding this information that the allocator configures. And from reading the paper, don't they intended for the kernel to do this checking as well on userspace pointers, indicating the kernel also needs access to this information? It's doable, and better overall, but more complicated.

convolvatron 9y ago
I dont understand the implication of why the kernel needs to be aware of the checking. the tag bits are architecturally ignored. you can remove the restriction on the number of the colors by using valid upper virtual memory bits to denote type (bibop), as long as you know that the kernel hasnt put anything else there. maybe thats the kernel interaction you were thinking of?
- DSMan195276 9y ago
  I suppose that's what I get for skimming, this paper is a bit weird. I thought they were going to have the kernel check the tags of userspace pointers that are passed to it, because it includes this line in regards to ASAN: Does not currently detect when the kernel accesses invalid user-space memory But after reading the paper again it looks like they never bring this up again so ¯\_(ツ)_/¯
  - BeeOnRope 9y ago
    Yeah they aren't clear about it, but I guess the idea is in a hardware supported model with memory tagging you'd presumably get kernel (and more generally "cross process") checking kind of for free since the checks would be pervasive and hardware enforced. With the software only solution, it's essentially just a variation on ASAN: with the trick that you use some pointer bits to additionally detect some cases that ASAN can't (because ASAN doesn't care about the origin/formation of the pointer: only whether the access is allowed).
BeeOnRope 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? 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. That avoids the need to have any kind of page-table like structure, but it would waste a lot of virtual address space if the range of the pointers was very large or very sparse. If you had hardware support though, maybe this problem goes away: the hardware could store the bits in "holes" right alongside the actual memory, as how ECC works (they suggest SPARC is doing this), or they could include the information in the TLB alongside the regular mappings (I guess this would need kernel support too). 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.
- 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.

convolvatron 9y ago

I dont understand the implication of why the kernel needs to be aware of the checking. the tag bits are architecturally ignored. you can remove the restriction on the number of the colors by using valid upper virtual memory bits to denote type (bibop), as long as you know that the kernel hasnt put anything else there. maybe thats the kernel interaction you were thinking of?

DSMan195276 9y ago
I suppose that's what I get for skimming, this paper is a bit weird. I thought they were going to have the kernel check the tags of userspace pointers that are passed to it, because it includes this line in regards to ASAN: Does not currently detect when the kernel accesses invalid user-space memory But after reading the paper again it looks like they never bring this up again so ¯\_(ツ)_/¯
- BeeOnRope 9y ago
  Yeah they aren't clear about it, but I guess the idea is in a hardware supported model with memory tagging you'd presumably get kernel (and more generally "cross process") checking kind of for free since the checks would be pervasive and hardware enforced. With the software only solution, it's essentially just a variation on ASAN: with the trick that you use some pointer bits to additionally detect some cases that ASAN can't (because ASAN doesn't care about the origin/formation of the pointer: only whether the access is allowed).

BeeOnRope 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? 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. That avoids the need to have any kind of page-table like structure, but it would waste a lot of virtual address space if the range of the pointers was very large or very sparse. If you had hardware support though, maybe this problem goes away: the hardware could store the bits in "holes" right alongside the actual memory, as how ECC works (they suggest SPARC is doing this), or they could include the information in the TLB alongside the regular mappings (I guess this would need kernel support too). 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.

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.