9 ms·

Does malloc lazily create the backing pages for an allocation on Linux? (2009)

38 points by tzhenghao 7y ago

zabzonk 7y ago
malloc() is a C (and C++) Standard Library function that you could write user-level code for yourself (in fact, there's an extended exercise in TCPL to do just that). It doesn't do the low-level handling of pages - that's down to the Linux kernel.
- acqq 7y ago
  But that malloc is implemented in C lib doesn’t mean that the question and the answers are wrong. Eventually system specific calls have to occur. The question is very specific, asking what happens in Linux when one makes a malloc call requesting a big allocation: “does it actually create 1 GiB worth of swap pages? Or does it mprotect the address range and create the pages when you actually touch them like mmap does?” And how it is implemented can be seen, as an example, here: https://sources.debian.org/src/glibc/2.28-10/malloc/malloc.c/ https://sources.debian.org/src/glibc/2.28-10/malloc/malloc.c... Note both mprotect and mmap references.
  - temac 7y ago
    The question is only semi-specific and the result depends on a ton of variables, like: which libc do you use; which kernel (maybe a patched linux kernel like on Android, don't know if they change anything regarding memory alloc though) kernel configuration do you use (esp. in regard with overcommit), do you have any other additional tuning, etc. > does it actually create 1 GiB worth of swap pages Create? No; probably never. > does it mprotect the address range and create the pages when you actually touch them like mmap does? Both mmap and mprotect are syscalls, and syscalls do not (directly) call other syscalls. So mmap does not do that. And malloc can't because it does not run anymore after it has returned. On top of all of that, malloc(insanely_big_value) can still fail immediately by returning NULL even if you have overcommit activated. Granted, 1GB is probably never an "insanely_big_value"? Not even sure on 32 bits systems though.
    - acqq 7y ago
      Asking "in Linux" obviously didn't mean "on Android" and also not "in Linux after I patch the kernel configuration." The question was clear, the answer on the site was clear, by the answer here to which I responded was by somebody who I suspect simply hasn't read what was written there.
  - saagarjha 7y ago
    You can write a malloc that performs no system calls and hands out chunks of the data segment you’ve set aside (e.g. by creating a large array in your program). But I think it’s clear in context that the question is talking about one of the standard Linux memory allocators, probably Glibc’s, which will brk/mmap from the OS and hand that out.
- chrisseaton 7y ago
  That is, very obviously, not what the question is asking.
blibble 7y ago
it'll call mmap (probably), which will then find 1GB(+ overhead) of contiguous address space mmap will go and create the page table mappings (entries) for that address space (~262144 of them with 4k pages) unless someone's been messing with overcommit: the physical memory allocation is normally lazy this is done by setting the "faulted" bit on the allocated page table entries when the application first reads/writes from a page not yet allocated: a fault will occur, the kernel will step in, (hopefully) find an unused physical 4kb of memory, update the page table entry to point to it, unmark the faulted bit, then return to the application (which will be blissfully unaware that anything happened)
- cesarb 7y ago
  > mmap will go and create the page table mappings (entries) for that address space (~262144 of them with 4k pages) I haven't looked at the mmap implementation in detail, but I believe it doesn't even do that: it just creates a new VMA (struct vm_area_struct in the kernel) for that address space range, and the page table is updated lazily.
- ajross 7y ago
  > mmap will go and create the page table mappings (entries) for that address space (~262144 of them with 4k pages) It does not, actually[1]. Page tables are a hardware datastructure with significant overhead. All the kernel does at mmap() time is create the a virtualized record of the mapping. It's not until the process takes a page fault to a mapped address that the hardware page tables are allocated and filled out. In practice this is a win because (especially with use cases like malloc) most processes tend to map large chunks of which they'll only use a subset in the short term. [1] By default. There is a MAP_POPULATE flag you can pass that will allocate the page tables and allocate/prefault all the mapped pages before the system call returns.
- dividuum 7y ago
  > it'll call mmap (probably), which will then find 1GB(+ overhead) of contiguous address space It does. Last time I dug into that I think there was a 128KB threshold. Smaller allocations would use sbrk while larger once would use mmap.
OskarS 7y ago
Suppose you WANT malloc to be eager (i.e. make sure all the pages are committed right away, so you don't pay a performance penalty for it later), what do you do? The obvious answer is just looping through it and setting it to zero would be replaced with a call to `calloc` by an optimizing compiler, and doesn't calloc also do some kind of similar "lazy" trick? So what do you do? Mark the pointer as volatile and loop through it and set all the memory to 0 (or some other value)? Call memset, I guess? EDIT: apparently malloc + memset compiles to calloc as well [0], so if you want to allocate, zero out memory, and make sure it's committed, using volatile seems like the best bet to me... [0]: https://godbolt.org/z/qhaaYc https://godbolt.org/z/qhaaYc
- deleted 7y ago
  [deleted]
- cma 7y ago
  mmap has some kind of option to immediately make resident.
  - OskarS 7y ago
    Yeah, but that's a much lower-level call compared to malloc. Also platform-dependent.
    - chrisseaton 7y ago
      You have to use low-level and platform-dependent calls to do low-level and platform-dependent things, yes. Seems reasonable to me? What do you want to do? Bake in the virtual memory semantics of the Intel architecture into C somehow? No, you need to use tools out of the scope of C for this and that’s how it should be.
- saagarjha 7y ago
  Maybe memset_s?
- htfy96 7y ago
  First of all, you only need to touch a single byte of each page to populate it. Besides, this approach doesn't ensure that the backing pages is allocated, for it's (technically) legal to only allocate one physical zero page after the calloc. Therefore, you must use OS-dependent primitives to force eager allocation. On linux this can be achieved by two flags for mmap: MAP_POPULATE initializes the page table entries eagerly (but doesn't guarantee a backing store allocation), and MAP_LOCKED for touching all pages (just like the calloc, but at kernel level and more deterministic). Note that MAP_LOCKED doesn't raise error for touching errors due to low memory, so you still need to touch it again at user-level.
lightedman 7y ago
Is this why when I create an encrypted RAM drive that Linux shits itself? I assume that it should not fill itself up yet it does almost instantly and brings the system, down to its knees.
- tedunangst 7y ago
  No.
  - lightedman 7y ago
    Prove it, please. Because I make an encrypted RAMDisk, set loopback, and it fucks itself when it should not. So, since you make it out to seem that you are an authoritative source, why?

38 points by tzhenghao 7y ago

malloc() is a C (and C++) Standard Library function that you could write user-level code for yourself (in fact, there's an extended exercise in TCPL to do just that). It doesn't do the low-level handling of pages - that's down to the Linux kernel.

acqq 7y ago
But that malloc is implemented in C lib doesn’t mean that the question and the answers are wrong. Eventually system specific calls have to occur. The question is very specific, asking what happens in Linux when one makes a malloc call requesting a big allocation: “does it actually create 1 GiB worth of swap pages? Or does it mprotect the address range and create the pages when you actually touch them like mmap does?” And how it is implemented can be seen, as an example, here: https://sources.debian.org/src/glibc/2.28-10/malloc/malloc.c/ https://sources.debian.org/src/glibc/2.28-10/malloc/malloc.c... Note both mprotect and mmap references.
- temac 7y ago
  The question is only semi-specific and the result depends on a ton of variables, like: which libc do you use; which kernel (maybe a patched linux kernel like on Android, don't know if they change anything regarding memory alloc though) kernel configuration do you use (esp. in regard with overcommit), do you have any other additional tuning, etc. > does it actually create 1 GiB worth of swap pages Create? No; probably never. > does it mprotect the address range and create the pages when you actually touch them like mmap does? Both mmap and mprotect are syscalls, and syscalls do not (directly) call other syscalls. So mmap does not do that. And malloc can't because it does not run anymore after it has returned. On top of all of that, malloc(insanely_big_value) can still fail immediately by returning NULL even if you have overcommit activated. Granted, 1GB is probably never an "insanely_big_value"? Not even sure on 32 bits systems though.
  - acqq 7y ago
    Asking "in Linux" obviously didn't mean "on Android" and also not "in Linux after I patch the kernel configuration." The question was clear, the answer on the site was clear, by the answer here to which I responded was by somebody who I suspect simply hasn't read what was written there.
- saagarjha 7y ago
  You can write a malloc that performs no system calls and hands out chunks of the data segment you’ve set aside (e.g. by creating a large array in your program). But I think it’s clear in context that the question is talking about one of the standard Linux memory allocators, probably Glibc’s, which will brk/mmap from the OS and hand that out.
chrisseaton 7y ago
That is, very obviously, not what the question is asking.

blibble 7y ago

it'll call mmap (probably), which will then find 1GB(+ overhead) of contiguous address space mmap will go and create the page table mappings (entries) for that address space (~262144 of them with 4k pages) unless someone's been messing with overcommit: the physical memory allocation is normally lazy this is done by setting the "faulted" bit on the allocated page table entries when the application first reads/writes from a page not yet allocated: a fault will occur, the kernel will step in, (hopefully) find an unused physical 4kb of memory, update the page table entry to point to it, unmark the faulted bit, then return to the application (which will be blissfully unaware that anything happened)

cesarb 7y ago
> mmap will go and create the page table mappings (entries) for that address space (~262144 of them with 4k pages) I haven't looked at the mmap implementation in detail, but I believe it doesn't even do that: it just creates a new VMA (struct vm_area_struct in the kernel) for that address space range, and the page table is updated lazily.
ajross 7y ago
> mmap will go and create the page table mappings (entries) for that address space (~262144 of them with 4k pages) It does not, actually[1]. Page tables are a hardware datastructure with significant overhead. All the kernel does at mmap() time is create the a virtualized record of the mapping. It's not until the process takes a page fault to a mapped address that the hardware page tables are allocated and filled out. In practice this is a win because (especially with use cases like malloc) most processes tend to map large chunks of which they'll only use a subset in the short term. [1] By default. There is a MAP_POPULATE flag you can pass that will allocate the page tables and allocate/prefault all the mapped pages before the system call returns.
dividuum 7y ago
> it'll call mmap (probably), which will then find 1GB(+ overhead) of contiguous address space It does. Last time I dug into that I think there was a 128KB threshold. Smaller allocations would use sbrk while larger once would use mmap.

OskarS 7y ago

Suppose you WANT malloc to be eager (i.e. make sure all the pages are committed right away, so you don't pay a performance penalty for it later), what do you do? The obvious answer is just looping through it and setting it to zero would be replaced with a call to `calloc` by an optimizing compiler, and doesn't calloc also do some kind of similar "lazy" trick? So what do you do? Mark the pointer as volatile and loop through it and set all the memory to 0 (or some other value)? Call memset, I guess? EDIT: apparently malloc + memset compiles to calloc as well [0], so if you want to allocate, zero out memory, and make sure it's committed, using volatile seems like the best bet to me... [0]: https://godbolt.org/z/qhaaYc https://godbolt.org/z/qhaaYc

deleted 7y ago
[deleted]
cma 7y ago
mmap has some kind of option to immediately make resident.
- OskarS 7y ago
  Yeah, but that's a much lower-level call compared to malloc. Also platform-dependent.
  - chrisseaton 7y ago
    You have to use low-level and platform-dependent calls to do low-level and platform-dependent things, yes. Seems reasonable to me? What do you want to do? Bake in the virtual memory semantics of the Intel architecture into C somehow? No, you need to use tools out of the scope of C for this and that’s how it should be.
saagarjha 7y ago
Maybe memset_s?
htfy96 7y ago
First of all, you only need to touch a single byte of each page to populate it. Besides, this approach doesn't ensure that the backing pages is allocated, for it's (technically) legal to only allocate one physical zero page after the calloc. Therefore, you must use OS-dependent primitives to force eager allocation. On linux this can be achieved by two flags for mmap: MAP_POPULATE initializes the page table entries eagerly (but doesn't guarantee a backing store allocation), and MAP_LOCKED for touching all pages (just like the calloc, but at kernel level and more deterministic). Note that MAP_LOCKED doesn't raise error for touching errors due to low memory, so you still need to touch it again at user-level.

lightedman 7y ago

Is this why when I create an encrypted RAM drive that Linux shits itself? I assume that it should not fill itself up yet it does almost instantly and brings the system, down to its knees.

tedunangst 7y ago
No.
- lightedman 7y ago
  Prove it, please. Because I make an encrypted RAMDisk, set loopback, and it fucks itself when it should not. So, since you make it out to seem that you are an authoritative source, why?