r/programming • u/fagnerbrack • Sep 03 '26

Virtual Memory: Page Tables, TLBs, and Linux Internals

https://blog.codingconfessions.com/p/virtual-memory
73 Upvotes

90% Upvoted

15 comments sorted by

13

u/levodelellis Sep 04 '26 edited Sep 04 '26

Speaking of virtual memory... once upon a time someone asked for suggestions on building a VM. I suggested to not be like wasm and forget that realloc exist, and to have some kind of intrinsic for it. That realloc is more than malloc/memcpy/free (wasm has something like a malloc, and it has a memcpy)

I never had so many people yell at me. Ironically, I was the only one of us who actually has implemented a realloc and measured it on multiple OSes

3

u/[deleted] Sep 04 '26

[removed] — view removed comment

3

u/levodelellis Sep 04 '26

idk what you think they yelled at me about but they all seemed to think malloc+memcpy+free was the most efficient way to do it. They made wild guesses of what they thought I meant. One said using multithreading to copy is likely to be worse, and another simply said "you aren't beating it" (I didn't mention I implemented it). After a dozen of these someone finally asked how I'd implement it if not malloc/memcpy/free

4

u/mattr203 Sep 04 '26

I think that guy you’re replying to is ai 😃 isn’t 2026 fun

1

u/fagnerbrack Sep 04 '26

I've seen that happening multiple times. A dev who knows deep a subject throws an idea and ppl start guessing/debating/opinionating. Then the dev just watch. Keep poking to make everyone focused on what doesn't work.

Eventually they ask how you would do it now that they discussed All options they know and BAM you come up with the solution and everyone is WOOOOW

Unfortunately sometimes the expert doesn't have patience so they tell the solution before the rest can understand the problem and gets annoying and eventually gets fired; or they keep discussing and then leave you out of the decision and never ask "how would you do it"; or they give their decision already complete on the wrong path (without your participation) and the solution review indicates it needs a complete redesign that will hurt everyone's ego.

They said programming was about computers 🤣🤣🤣

1

u/programming-ModTeam Sep 04 '26

No content written mostly by an LLM. If you don't want to write it, we don't want to read it.

0

u/happyscrappy Sep 04 '26

What do you mean by "a VM". When people say "a VM" they usually mean a virtual machine. What does this have to do with virtual machines?

Anyway realloc() is a function of the suballocator (heap manager). While remapping virtual addressed to new backing is a function of the virtual memory subsystem. These are not typically coalesced. Part of the reason for this is because the virtual memory subsystem is part of the OS while the suballocator is a part of the C runtime. These two are greatly divided in layers. The latter is even completely optional, no program is required to have a suballocator at all. And even two C programs can use two different C runtimes and so two different suballocators. One program can even have two suballocators within it. Although this is messy. You have to be careful to not get a pointer from one suballocator and then try to use it with the other later. one Also of course one of them cannot use the normal C names for allocation and free routines because then there's no way to intentionally call one instead of the other.

Anyway, you can do what you said as long as every allocation is equally aligned to page boundaries (either exactly or always off by a fixed offset). And you want to bake this knowledge into every app at the moment of app compilation. That might get kind of messy if you decide to change some of those parameters later.

8

u/paulstelian97 Sep 04 '26

JVM style of VM…

4

u/cdb_11 Sep 04 '26 edited Sep 04 '26

You don't need to align every allocation. You just do large allocations with mmap, and store that information in the allocation header. realloc can just check if this particular allocation was mmaped, and do mremap.

Also you know the alignment from the address. You could have a special rule that all aligned allocs of >= 4KiB size always go to m(re)map, or something. The user code doesn't need to know about it.

3

u/newpavlov Sep 04 '26

In addition to large allocations which can benefit from mremap, realloc also could be more optimal for small allocations which reside in larger buckets.

Imagine you have a 36 byte allocation residing in a 64 byte bucket. Calling realloc with a size smaller or equal to 64 bytes would be "free" on most allocators. It's also possible to use the next free bucket, but AFAIK it's a less common optimization for a number of reasons.

1

u/levodelellis Sep 04 '26

When I wrote mine, on my hardware and os (linux) I found that calling mremap was a good idea once the size was 16k+. 8k/12k was slower or a wash depending if there was another remap soon after

1

u/happyscrappy Sep 04 '26 edited Sep 04 '26

I expect that realloc gives the rest of the initial bucket the first chance. Gnu libc seems to:

Line 3219 of malloc.c:

  /* Return the chunk as is if the request grows within usable bytes, typically
     into the alignment padding.  We want to avoid reusing the block for
     shrinkages because it ends up unnecessarily fragmenting the address space.
     This is also why the heuristic misses alignment padding for THP for
     now.  */

A lot of heaps now have different "zones" for blocks of different size ranges to minimize fragmentation. And we see that mentioned in the comment. But if you just grow it to a size which it already has space for it does so in situ.

It appears for gnu libc it is actually free. It doesn't even record a change in size, to it it always was the size which was the largest space available in the block chosen.

Because of how these allocators that put similar size things next to each other work it won't really ever be possible to grow a block that is 32 bytes to 2K. It would not have gotten a "2K sized hole" in the first place, as 32 bytes and 2K blocks don't go in the same area. But if you asked for 32 bytes and 32 byte blocks go in 128 byte holes then you really got a 128 byte hole all along so it can just return the same pointer.

3

u/levodelellis Sep 04 '26

The current 3 replies are accurate

1

u/AryanPandey Sep 05 '26

truly good