What is the most reliable / portable way to allocate memory at low addresses on 64-bit systems?

Question

I need to allocate large blocks of memory (to be used by my custom allocator) that fall within the first 32GB of virtual address space.

I imagine that if I needed, say, 1MB blocks, I could iterate using mmap and MAP_FIXED_NOREPLACE (or VirtualAlloc) from low addresses onwards in increments of, say, 1MB, until the call succeeds. Continue from the last successful block for the next one.

This sounds clumsy, but at least it will be somewhat robust against OS address space layout changes, and ASLR algorithm changes. From my understanding of current OS layouts, there should be plenty of memory available in the first 32GB this way, but maybe I am missing something?

Is there anything in Windows, Linux, OS X, iOS or Android that would defeat this scheme? Is there a better way?

Just in case you're wondering, this is for the implementation of a VM for a programming language where fitting all pointers in a 32-bit value on a 64-bit system could give huge memory usage advantages and even speed gains. Since all objects are at least 8-byte aligned, the lower 3 bits can be shifted out, expanding the pointer range from 4GB to 32GB.

MS-Window you can query the page table, this might take some of the trial and error out of VirtualAlloc see: https://msdn.microsoft.com/en-us/library/windows/desktop/aa366902(v=vs.85).aspx — Richard Critten, May 19 '18 at 20:59
Does the language have an equivalent of `char` and `char *`? If so, are all `char` objects also 8-byte aligned? — Angew is no longer proud of SO, May 19 '18 at 21:01
Would you be open to an alternative solution that avoids the restriction on virtual addresses? — 1201ProgramAlarm, May 19 '18 at 21:12
@Angew: it has strings that are 8-byte aligned, no naked char * sub-strings — Aardappel, May 20 '18 at 01:11
@1201ProgramAlarm: Sure.. you mean using a base address? That's a bit more expensive though, especially since that now also requires a special case for de-compressing a null pointer. — Aardappel, May 20 '18 at 01:11
@Aardappel A base address was what I was thinking. You could take that even further, though, and use something similar to page tables. Then you wouldn't need one big chunk of memory, and could allocate memory as it was needed rather than all in one go. — 1201ProgramAlarm, May 20 '18 at 03:05
A 32 bits offset will do, no need for a 32 bit pointer. Store the base address. — MSalters, May 20 '18 at 09:03
@1201ProgramAlarm It is kind of important for pointer access to be efficient to be competitive with naked pointers. My current decompression code (in release mode) amounts to: `(T *)(((size_t)compr_ptr) << 3)`, with a base address, that becomes: `compr_ptr ? (T *)((((size_t)compr_ptr) << 3) + base_ptr) : nullptr`. With a software page table it becomes even more involved, having to split the `compr_ptr` into a page table index and page index first. So I'd like to see if the no base address version can work first. — Aardappel, May 20 '18 at 15:01
@MSalters: see my previous comment for why a base address is relatively expensive. I know a base address is a possible solution, this question specifically asks if I can reliably do without. If the answer is no, I'd love to hear (possibly platform-specific) reasons :) — Aardappel, May 20 '18 at 15:04
@Aardappel: The reason why I think it's no big deal is that both ARM and Intel can do the "multiply and add" efficiently since the multiplier is a small power of two. As for the branch, I'd try to see if `static_cast(compr_ptr<<3) + (compr_ptr ? base__ptr : nullptr)` would work. The reason is that the shift is now unconditional and can run in parallel with the conditional add, which probably just takes a `CMOV` (and on ARM, anything can be conditional including adds) — MSalters, May 20 '18 at 20:32
@MSalters good point, it is worth benchmarking if that becomes cheap enough rather than making assumptions it will be expensive :) — Aardappel, May 20 '18 at 20:54
in windows we can control allocated address (fit to same mask) by *ZeroBits* parameter of [`NtAllocateVirtualMemory`](https://learn.microsoft.com/en-us/windows-hardware/drivers/ddi/content/ntifs/nf-ntifs-ntallocatevirtualmemory) . but documentation here, about *ZeroBits* not correct. *ZeroBits* can be used as mask - say we can set `ZeroBits = 3FFFFFFFF` and allocated address will be in range `[0, 3FFFFFFFF]`. or say `ZeroBits = 7FFFFF` -> address in range `[0, 7FFFF]`. or if `ZeroBits < 32` - high `ZeroBits + 32` bits of address will be 0. `ZeroBits=7` -> addr in range `[0,1FF0000]` — RbMm, May 27 '18 at 10:58
@RbMm that sounds like it will do exactly what I want on Windows. Bit worried that it doesn't seem to be an officially exposed function, and the documentation is certainly confusing. Your explanation is helpful, thanks! — Aardappel, May 27 '18 at 14:56
@Aardappel - if want, i can post answer with example code. `NtAllocateVirtualMemory` documented api for use in user mode code. `ZeroBits` in msdn wrong documented, but documented in wrk — RbMm, May 27 '18 at 15:06
It is very operating system specific, and in general you should not bother at what address is some memory allocated! Think of [ASLR](https://en.wikipedia.org/wiki/Address_space_layout_randomization) — Basile Starynkevitch, May 27 '18 at 15:31
@BasileStarynkevitch - here nothing common with ASLR. question not in allocate constant address, but in restrict allocation range — RbMm, May 27 '18 at 15:52
The x86_64 processor has a built-in addressing mode to do this for you, seems like a waste to not take advantage of it. https://stackoverflow.com/q/27936196/17034 — Hans Passant, May 29 '18 at 11:35
@HansPassant: yes, that was already discussed with MSalters above. Maybe the compiler will always use this addressing mode, maybe it will will always do a CMOV for the null case, maybe it will always be able to keep the base address in a register thuout the entire codebase and maybe the the effects on register pressure for the rest of the code won't be so bad, and maybe it will do that on both x86 and arm. That's a lot of maybe's. I know using a base address is my fallback, this question is specifically asking if I can do without. — Aardappel, May 29 '18 at 15:41

score 16 · Accepted Answer · edited Aug 04 '23 at 12:39

For restricting the allocated memory range in Windows, we can use the NtAllocateVirtualMemory function. This API is available for use in both user and kernel mode. In user mode it exported by ntdll.dll (use ntdll.lib or ntdllp.lib from WDK). This function has a parameter called ZeroBits - The number of high-order address bits that must be zero in the base address of the section view. But in the msdn link above, the next few details about ZeroBits are incorrect. Here's a correct description:

ZeroBits

Supplies the number of high order address bits that must be zero in the base address of the section view. The value of this argument must be less than or equal to the maximum number of zero bits and is only used when memory management determines where to allocate the view (i.e. when BaseAddress is null).

If ZeroBits is zero, then no zero bit constraints are applied.

If ZeroBits is greater than 0 and less than 32, then it is the number of leading zero bits from bit 31. Bits 63:32 are also required to be zero. This retains compatibility with 32-bit systems. If ZeroBits is greater than 32, then it is considered as a mask and then number of leading zero are counted out in the mask. This then becomes the zero bits argument.

So really we can use ZeroBits as mask. This is its most powerful usage. But it can also be used as a zero bit count from the 31st bit. In this case, 63-32 bits will always be equal to 0 due to allocation granularity. Therefore a valid value for ZeroBits in bits-number mode would be any number from 1 to 15 (=31-16). To better understand how this parameter works, look at the example code below. For the sake of this demo, I will be using MEM_TOP_DOWN as the AllocationType:

MEM_TOP_DOWN

The specified region should be created at the highest virtual address possible based on ZeroBits.

PVOID BaseAddress;
ULONG_PTR ZeroBits;
SIZE_T RegionSize = 1;
NTSTATUS status;

for (ZeroBits = 0xFFFFFFFFFFFFFFFF;;)
{
    if (0 <= (status = NtAllocateVirtualMemory(NtCurrentProcess(), &(BaseAddress = 0), 
        ZeroBits, &RegionSize, MEM_RESERVE|MEM_TOP_DOWN, PAGE_NOACCESS)))
    {
        DbgPrint("%p:%p\n", ZeroBits, BaseAddress);
        NtFreeVirtualMemory(NtCurrentProcess(), &BaseAddress, &RegionSize, MEM_RELEASE);

        ZeroBits >>= 1;
    }
    else
    {
        DbgPrint("%x\n", status);
        break;
    }
}

for(ZeroBits = 0;;) 
{
    if (0 <= (status = NtAllocateVirtualMemory(NtCurrentProcess(), &(BaseAddress = 0), 
        ZeroBits, &RegionSize, MEM_RESERVE|MEM_TOP_DOWN, PAGE_NOACCESS)))
    {
        DbgPrint("%x:%p\n", ZeroBits++, BaseAddress);
        NtFreeVirtualMemory(NtCurrentProcess(), &BaseAddress, &RegionSize, MEM_RELEASE);
    }
    else
    {
        DbgPrint("%x\n", status);
        break;
    }
}

Output:

FFFFFFFFFFFFFFFF:00007FF735B40000
7FFFFFFFFFFFFFFF:00007FF735B40000
3FFFFFFFFFFFFFFF:00007FF735B40000
1FFFFFFFFFFFFFFF:00007FF735B40000
0FFFFFFFFFFFFFFF:00007FF735B40000
07FFFFFFFFFFFFFF:00007FF735B40000
03FFFFFFFFFFFFFF:00007FF735B40000
01FFFFFFFFFFFFFF:00007FF735B40000
00FFFFFFFFFFFFFF:00007FF735B40000
007FFFFFFFFFFFFF:00007FF735B40000
003FFFFFFFFFFFFF:00007FF735B40000
001FFFFFFFFFFFFF:00007FF735B40000
000FFFFFFFFFFFFF:00007FF735B40000
0007FFFFFFFFFFFF:00007FF735B40000
0003FFFFFFFFFFFF:00007FF735B40000
0001FFFFFFFFFFFF:00007FF735B40000
0000FFFFFFFFFFFF:00007FF735B40000
00007FFFFFFFFFFF:00007FF735B40000
00003FFFFFFFFFFF:00003FFFFFFF0000
00001FFFFFFFFFFF:00001FFFFFFF0000
00000FFFFFFFFFFF:00000FFFFFFF0000
000007FFFFFFFFFF:000007FFFFFF0000
000003FFFFFFFFFF:000003FFFFFF0000
000001FFFFFFFFFF:000001FFFFFF0000
000000FFFFFFFFFF:000000FFFFFF0000
0000007FFFFFFFFF:0000007FFFFF0000
0000003FFFFFFFFF:0000003FFFFF0000
0000001FFFFFFFFF:0000001FFFFF0000
0000000FFFFFFFFF:0000000FFFFF0000
00000007FFFFFFFF:00000007FFFF0000
00000003FFFFFFFF:00000003FFFF0000
00000001FFFFFFFF:00000001FFFF0000
00000000FFFFFFFF:00000000FFFF0000
000000007FFFFFFF:000000007FFF0000
000000003FFFFFFF:000000003FFF0000
000000001FFFFFFF:000000001FFF0000
000000000FFFFFFF:000000000FFF0000
0000000007FFFFFF:0000000007FF0000
0000000003FFFFFF:0000000003FF0000
0000000001FFFFFF:0000000001FF0000
0000000000FFFFFF:0000000000FF0000
00000000007FFFFF:00000000007F0000
00000000003FFFFF:00000000003F0000
00000000001FFFFF:00000000001F0000
00000000000FFFFF:00000000000F0000
000000000007FFFF:0000000000070000
000000000003FFFF:0000000000030000
000000000001FFFF:0000000000010000
c0000017
0:00007FF735B40000
1:000000007FFF0000
2:000000003FFF0000
3:000000001FFF0000
4:000000000FFF0000
5:0000000007FF0000
6:0000000003FF0000
7:0000000001FF0000
8:0000000000FF0000
9:00000000007F0000
a:00000000003F0000
b:00000000001F0000
c:00000000000F0000
d:0000000000070000
e:0000000000030000
f:0000000000010000
c0000017

So if we want to restrict memory allocation to 32Gb (0x800000000), we can use ZeroBits = 0x800000000 - 1:

NtAllocateVirtualMemory(NtCurrentProcess(), &(BaseAddress = 0), 
            0x800000000 - 1, &RegionSize, MEM_RESERVE|MEM_TOP_DOWN, PAGE_NOACCESS);

This will allocate memory in the range [0, 7FFFFFFFF]. (Actually, the range will be [0, 7FFFF0000]. Because of allocation granularity, the low 16 bits of an address are always 0.)

You can then create a heap object in the allocated region using RtlCreateHeap and allocate memory from this heap. (Note - this API is also available in user mode. Use ntdll[p].lib for linker input.)

PVOID BaseAddress = 0;
SIZE_T RegionSize = 0x10000000;// reserve 256Mb
if (0 <= NtAllocateVirtualMemory(NtCurrentProcess(), &BaseAddress, 
    0x800000000 - 1, &RegionSize, MEM_RESERVE, PAGE_READWRITE))
{
    if (PVOID hHeap = RtlCreateHeap(0, BaseAddress, RegionSize, 0, 0, 0))
    {
        HeapAlloc(hHeap, 0, <somesize>);
        RtlDestroyHeap(hHeap);
    }

    VirtualFree(BaseAddress, 0, MEM_RELEASE);
}

Thanks, this is a fantastic answer for the Windows case that does exactly what I want. I appreciate the example code. Was also hoping for some hints on how to accomplish the same on other OS-es though. — Aardappel, May 27 '18 at 19:08
@Aardappel - unfortunately my answer is only for windows case. i have no any knowledge about another os. — RbMm, May 27 '18 at 20:16
ok, I'll accept your answer in a few days unless someone manages to do better. — Aardappel, May 27 '18 at 23:28

What is the most reliable / portable way to allocate memory at low addresses on 64-bit systems?

1 Answers1

Linked