News for hackers. Stuff that matters.
Re:Three kinds of memory leaks by quietbritishjim on Tuesday May 01, 2018 @03:35AM (#16965219)
I'm surprised the article didn't point out that this applies to C and C++, considering that these are usually thought of as being more efficient than higher-level languages. On Unix-like operating systems (and Windows too I believe), all of a process's data is in a single contiguous block. You can grow or shrink that block by calling the brk() [1] system call, but this allows you to return memory to the operating system only if it's at the end of that block – there's no mechanism to free pages in the middle.

The big problem for these languages is that you can't move objects around in memory because other objects may have pointers to them, and there's not enough metadata at runtime to figure out where those pointers are and fix them up to a new location. This means that if you have an large amount of free memory and have just one little object allocated after it then there's no way, even in principle, to return that free memory to the operating system. In practice I don't think any C allocators even try to return memory to the OS.

There are a couple of mitigating factors to this though:

* If you allocate a huge amount of memory and then free it and don't use much afterwards, eventually the OS will move those unused virtual memory pages to disc in the page file. Your process will still appear to be using a lot of memory, but in practical terms the system will behave as if you had freed it.

* You can allocate memory allocated using memory-mapped files [2], a term which is distorted to include memory allocated by this mechanism but not necessarily backed by an actual file. These are not in the contiguous block of process data and their memory pages really are returned to the OS when the file is unmapped. This requires quite a lot of manual effort on the part of the developer, but for some applications it's worth it.

[1] https://en.wikipedia.org/wiki/Sbrk

[2] https://en.wikipedia.org/wiki/Memory-mapped_file

Re:Three kinds of memory leaks by gpderetta on Tuesday May 01, 2018 @05:13AM (#16965535)
Note that some allocators (including the standard glibc allocator) do use mmap internally for some allocation sizes. In this case the memory can be returned to the os when the whole block is freed.

Some allocators even use mmap exclusively.

Re:Three kinds of memory leaks by quietbritishjim on Tuesday May 01, 2018 @05:53AM (#16965697)
I didn't realise that. Thanks for the correction!
Re:Three kinds of memory leaks by dasyatidprime on Tuesday May 01, 2018 @05:13AM (#16965538)
So, the general point about fragmentation, non-moving memory management, and process heaps versus what can actually be returned to the OS is true and common, but your “single contiguous block” model is somewhat off:

On at least modern GNU/Linux, malloc can and does still use brk/sbrk, but will also use mmap for particularly large allocations, as can (on my system) be shown by stracing this C program:

  #define _GNU_SOURCE
  #include <stdio.h>
  #include <stdlib.h>
  int main(void)
  {
    printf("%p %p\n", malloc((size_t)1 << 14),
           malloc((size_t)1 << 20));
    return 0;
  }
On Windows, HeapAlloc is at least presumed to use VirtualAlloc-or-equivalent underneath, and there is no brk/sbrk.

Regarding the other two factors you mention: firstly, if you make a large number of allocations on a brk-based heap and then free most of them, a page from that heap can still only be paged out if none of the live allocations intersects it. (If you make a single large allocation, see above re automatic use of mmap.) If the heap is highly fragmented, you may not be able to page out many pages. If the heap is a brk-based heap and is not highly fragmented after the free phase, it's more likely there would be a bunch of space near the top, and then malloc could shrink the heap at the OS level too. One allocation pattern I can imagine where what you say would have a higher chance of happening, though, is “allocate many times for intermediary data during an operation, then allocate for the result, then free all the intermediary data”, in which case the result might well be stuck at the top of the heap with a bunch of dead pages underneath. But you still take lazy disk I/O doing the paging, and you still take a reservation across system virtual memory as a whole. On the whole I'm not all that convinced that this is a “mitigation” that's worth paying attention to from a developer perspective; it might be more useful from a sysadmin perspective.

For the second, terminology-wise, I've never heard “memory-mapped file” used to refer to anonymous mmap; I think I've only ever heard it called mmap in a Unixy context. On Windows, VirtualAlloc and MapViewOfFile are separate API functions, and VirtualAlloc is the equivalent of anonymous mmap.

Windows allows the creation of additional heaps for HeapAlloc such that a heap can be destroyed all at once, and I presume these use their own VirtualAlloc regions underneath. There are various C libraries that allow arena-based allocation on Unixy systems as well. These can even both reduce manual effort and increase performance if your memory usage patterns involve a large number of allocations for some operation followed by freeing everything, because then you don't have to free every block individually; you just throw away the entire arena, like an in-process equivalent of what exit() does to whole-process memory resources. Your main option in C if malloc is causing fragmentation/performance problems for you isn't usually to jump to raw mmap unless you're writing your own allocator on top of that; it's to jump to picking a more advanced malloc and maybe giving it some extra context about what you're doing with the memory.

Re:Three kinds of memory leaks by quietbritishjim on Tuesday May 01, 2018 @05:51AM (#16965687)
Thanks for correcting my misunderstandings, this is really interesting. There's quite a bit of subtlety in allocations compared to my (old) mental model of malloc calling brk().

I think you're right that I accidentally made up usage of "memory-mapped file" for mapped memory that doesn't correspond to any file. But it is possible to create them on Windows with MapViewOfFile; this function takes a handle returned from CreateFileMapping, which can accept a file handle of INVALID_HANDLE_VALUE [1]

[1] https://msdn.microsoft.com/en-gb/library/windows/desktop/aa3...