5 ms·

> After skimming the paper, I think it's actually closer to segmentation. They just split the address space into X number of segments. The allocator then ensure

> After skimming the paper, I think it's actually closer to segmentation. They just split the address space into X number of segments. The allocator then ensures every allocation lies completely within one of these segments and attaches that segment's ID to the returned pointer. It's sort of the other way around. Replacing "tags" with "colors" since somehow it seems a bit more intuitive, the allocator itself just "colors" different allocations with a different color, rather than splitting up the address space beforehand. The returned pointers are also colored and a fault occurs if any pointer is used to access memory of a different color. > Obviously, that doesn't even cover a full 4K page of data. So I presume the segments must repeat. Definitely - every color will be used many times, so they only probabilistically catch any fault, based on mostly the total number of colors (as long as the colors were randomized from run to run it seems like any fault would be quickly caught with a high probability). They mention in in the paper improvements such as ensuring that adjacent regions always have different colors so that linear overruns are caught with 100% probability. > I would assume objects larger then 64 bytes would have to be untagged, since normally you would access them via offsetting from the same base pointer, and that base pointer would always have the same tag. Not at all. The 64-bytes is only the granularity of the colors (actually they suggest 16 bytes is a better option): but an arbitrarily large region can have the same color. Most of the rest of your post follows I think from that misunderstanding: there is no need to change the color every 16 or 64 bytes (they call this quantity TG) - you color the whole region with the same color. The TG value is just the granularity at which it can change, so it's a tradeoff between overhead for small allocations (favoring smaller TG) and total tag storage cost (favoring larger TG).

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

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.