3 ms·

Ironically, if you weren't using huge pages, the operating system was already doing this for you anyway, and your contiguous segments weren't contiguous. This

Ironically, if you weren't using huge pages, the operating system was already doing this for you anyway, and your contiguous segments weren't contiguous. This does suggest functionality that the OS should provide: let the program remap memory somewhere else in its address space to obtain a larger contiguous chunk of addresses without copying data. This wouldn't help much if you have direct pointers, but I think e.g. Java has a layer of indirection that would let it benefit from remapping to grow ArrayLists. I don't know if things already work this way. It should make speculative fetches easier for the processor since now it understands what you're doing via the memory map. Edit: taking this idea a little further is actually fascinating: use the type system to separate objects into pools based on type, and instead of pointers, use indexes into your pool. You can move the pool for free to grow/shrink it. I think you could even do this with pointers and full hardware acceleration today if you used the high bits to tag pointers with their types and used remapping at the hypervisor level to move the pools (so the address in the application level doesn't change). You could do some crazy stuff if the application could coordinate multiple levels of virtual memory.

pencilguin 4y ago
OSes do already provide this ability: mmap.
- ndriscoll 4y ago
  Maybe I'm just not seeing it, but I don't see how mmap let's you remap an existing address to a new one? Looks like there is a mremap on Linux in any case.
  - pencilguin 4y ago
    Or, you can map new space onto the end of an existing mapping, at a slightly greater cost of keeping track. Mremap is usually better.
  - comex 4y ago
    If you want to stick to mmap, you can do it by creating a file which doesn’t have any actual disk backing (one way to do this is with POSIX shm_open), and handling all memory allocations by mmapping parts of that file rather than mapping true anonymous memory. Then, ‘remapping’ an address to a new one is a matter of calling mmap again with the same file offset. Unlike mremap, this allows mapping the same memory at different addresses simultaneously, which can be useful for some purposes.
    - pencilguin 4y ago
      /dev/hugepages/ is a good place to put this if you have enough control over the host.
- kabdib 4y ago
  That sounds like a lot of work unless you absolutely have to have a contiguous allocation of every element. If you don't need that, you can get "O(1.1)" access and nice heap behavior with an indirection or two, and the implementation is likely to be lots more portable and standards-friendly than if you also dragged in a bunch of OS mmap() semantics (which tend to have exciting, platform-dependent misfeatures). Also, I would have to reach for the mmap() man page. I have malloc() right in front of me. :-)
kabdib 4y ago
Right, the ability to relocate a chunk of memory to a new virtual address (with more capacity at the end) without doing a physical copy would be an interesting way to solve the problem. I don't know if anyone has done research on integrating data structures and OS functionality in this way. Interesting idea. We needed to get things running again rather quickly, though :-)
- cyber_kinetist 4y ago
  Some game engine developers have certainly used this idea, to prevent any reallocations when the dynamic array needs to be resized. Such as: https://ruby0x1.github.io/machinery_blog_archive/post/virtual-memory-tricks/index.html https://ruby0x1.github.io/machinery_blog_archive/post/virtua... Some ECS implementations use this to reduce the overhead of dynamic arrays, as well as ensuring pointer stability of the items stored. For example entt: https://skypjack.github.io/2021-06-12-ecs-baf-part-11/ https://skypjack.github.io/2021-06-12-ecs-baf-part-11/ And here's a library implementing a resizable, pointer-stable vector using virtual memory functionality from the OS: https://github.com/mknejp/vmcontainer https://github.com/mknejp/vmcontainer
  - ultrahax 4y ago
    End of page allocation has been a real life-saver. I have it rigged up to the core allocators of the game engine I work with, so you can switch it with a cmdline switch; if you suspect an overwrite, you switch on the EOP allocator ( using more memory temporarily ), and bang, you get a segfault where you went off the end / used-after-free.
comex 4y ago
Linux has mremap() for this. macOS has vm_remap(). Not sure about other operating systems.
amluto 4y ago
You can certainly allocate memory at controlled addresses using mmap or VirtualAlloc. But you should not play virtual memory games at runtime in an application that you expect to be scalable. Unmapping memory or changing its permissions requires propagating the change to all threads in the process. On x86, the performance impact is dramatic. On ARM64, it’s not as bad but it’s still there. Also, even 64 bits can go fast when you start using high bits, separate pools for different purposes, etc.
bee_rider 4y ago
I somehow misread your comment the first time through and thought you were suggesting the ability to ask the OS: "Hey, I'm a pointer, is there anything in front of my block of memory, if so can you move it elsewhere so that I can expand?" This would of course be a pretty silly idea but it would be funny to give the OS folks a whole new class of use-after bugs to worry about. Edit: Let's call it "memoveouttamyway"
- FeepingCreature 4y ago
  Isn't that `realloc`? At the allocator level rather than OS level, but still.
colanderman 4y ago
glibc realloc(3) does this on Linux, by way of mremap(2) with MREMAP_MAYMOVE [1]. (Just confirmed on my local machine using strace(1).) Unfortunately, libstdc++ does not (to my knowledge) use realloc(3) or mremap(2) for vector resize, nor could it in many situations due to the semantics of C++. [1] https://github.com/bminor/glibc/blob/15a94e6668a6d7c5697e805d8d67f1d102d0d52e/malloc/malloc.c#L3071-L3072 https://github.com/bminor/glibc/blob/15a94e6668a6d7c5697e805...

pencilguin 4y ago

OSes do already provide this ability: mmap.

ndriscoll 4y ago
Maybe I'm just not seeing it, but I don't see how mmap let's you remap an existing address to a new one? Looks like there is a mremap on Linux in any case.
- pencilguin 4y ago
  Or, you can map new space onto the end of an existing mapping, at a slightly greater cost of keeping track. Mremap is usually better.
- comex 4y ago
  If you want to stick to mmap, you can do it by creating a file which doesn’t have any actual disk backing (one way to do this is with POSIX shm_open), and handling all memory allocations by mmapping parts of that file rather than mapping true anonymous memory. Then, ‘remapping’ an address to a new one is a matter of calling mmap again with the same file offset. Unlike mremap, this allows mapping the same memory at different addresses simultaneously, which can be useful for some purposes.
  - pencilguin 4y ago
    /dev/hugepages/ is a good place to put this if you have enough control over the host.
kabdib 4y ago
That sounds like a lot of work unless you absolutely have to have a contiguous allocation of every element. If you don't need that, you can get "O(1.1)" access and nice heap behavior with an indirection or two, and the implementation is likely to be lots more portable and standards-friendly than if you also dragged in a bunch of OS mmap() semantics (which tend to have exciting, platform-dependent misfeatures). Also, I would have to reach for the mmap() man page. I have malloc() right in front of me. :-)

kabdib 4y ago

Right, the ability to relocate a chunk of memory to a new virtual address (with more capacity at the end) without doing a physical copy would be an interesting way to solve the problem. I don't know if anyone has done research on integrating data structures and OS functionality in this way. Interesting idea. We needed to get things running again rather quickly, though :-)

cyber_kinetist 4y ago
Some game engine developers have certainly used this idea, to prevent any reallocations when the dynamic array needs to be resized. Such as: https://ruby0x1.github.io/machinery_blog_archive/post/virtual-memory-tricks/index.html https://ruby0x1.github.io/machinery_blog_archive/post/virtua... Some ECS implementations use this to reduce the overhead of dynamic arrays, as well as ensuring pointer stability of the items stored. For example entt: https://skypjack.github.io/2021-06-12-ecs-baf-part-11/ https://skypjack.github.io/2021-06-12-ecs-baf-part-11/ And here's a library implementing a resizable, pointer-stable vector using virtual memory functionality from the OS: https://github.com/mknejp/vmcontainer https://github.com/mknejp/vmcontainer
- ultrahax 4y ago
  End of page allocation has been a real life-saver. I have it rigged up to the core allocators of the game engine I work with, so you can switch it with a cmdline switch; if you suspect an overwrite, you switch on the EOP allocator ( using more memory temporarily ), and bang, you get a segfault where you went off the end / used-after-free.

comex 4y ago

Linux has mremap() for this. macOS has vm_remap(). Not sure about other operating systems.

amluto 4y ago

You can certainly allocate memory at controlled addresses using mmap or VirtualAlloc. But you should not play virtual memory games at runtime in an application that you expect to be scalable. Unmapping memory or changing its permissions requires propagating the change to all threads in the process. On x86, the performance impact is dramatic. On ARM64, it’s not as bad but it’s still there. Also, even 64 bits can go fast when you start using high bits, separate pools for different purposes, etc.

bee_rider 4y ago

I somehow misread your comment the first time through and thought you were suggesting the ability to ask the OS: "Hey, I'm a pointer, is there anything in front of my block of memory, if so can you move it elsewhere so that I can expand?" This would of course be a pretty silly idea but it would be funny to give the OS folks a whole new class of use-after bugs to worry about. Edit: Let's call it "memoveouttamyway"

FeepingCreature 4y ago
Isn't that `realloc`? At the allocator level rather than OS level, but still.

colanderman 4y ago

glibc realloc(3) does this on Linux, by way of mremap(2) with MREMAP_MAYMOVE [1]. (Just confirmed on my local machine using strace(1).) Unfortunately, libstdc++ does not (to my knowledge) use realloc(3) or mremap(2) for vector resize, nor could it in many situations due to the semantics of C++. [1] https://github.com/bminor/glibc/blob/15a94e6668a6d7c5697e805d8d67f1d102d0d52e/malloc/malloc.c#L3071-L3072 https://github.com/bminor/glibc/blob/15a94e6668a6d7c5697e805...