Should Heap's Be Contracted?

[Creature]

I have a rather general question relating the heap. I wanted to know if there's any point to contracting the heap after you've expanded it. As far as I know, what's left of the memory (e.g. after you used a static memory address starting from the end of the kernel) is all memory usable by the heap, isn't it? So why would it be useful to contract the heap back to a smaller size if the last header is free for example?

[frank]

If a process allocates a gig of memory with malloc, uses it and then releases it, it would be nice if that gig of memory could be returned to the OS for use in other programs. I've read somewhere that some OSs do it by calling sbreak with a negative number to shrink the heap.

[JohnnyTheDon]

/agree

However sbrk is kind of limited in this regard, because if a program allocates 1 gig and then allocates 10 bytes that end up after that 1 gig the program's memory manager will not be able to release the 1 gig of memory back to the OS (lowering the brk would lose the 10 bytes). In this case garbage collection that allows the memory manager to move allocated memory around or a more sophisticated system of memory management on the OS's part would help.

[Brendan]

Hi,

However sbrk is kind of limited in this regard, because if a program allocates 1 gig and then allocates 10 bytes that end up after that 1 gig the program's memory manager will not be able to release the 1 gig of memory back to the OS (lowering the brk would lose the 10 bytes). In this case garbage collection that allows the memory manager to move allocated memory around or a more sophisticated system of memory management on the OS's part would help.

It's possible to have one physical page that's full of zeros, and then map this page as "read only" everywhere you like. If anyone tries to write to this special "read only" page then the page fault handler can replace it with a new read/write page. In this way you can have huge areas of space that look just like usable/allocated RAM without actually using a huge amount of RAM.

You could have a "fill these pages with zero" kernel function, which actually frees the pages and then replaces them with the special "read only" page full of zeros. A program's heap manager could use this function to release pages back to the OS, and wouldn't need to (explicitly) allocate the pages if they're needed again.

Also, if "sbrk()" is used to increase space, then the OS could fill the extra space with the special "read only" page full of zeros; and you could do the same for uninitialized data sections (e.g. the ".bss") when programs are started.

You could also have a special "read only" page table where every page table entry points to the same physical page full of zeros that is used for the special "read only" page. In this case you can have (for example, for plain 32-bit paging) 400 MiB of space that behaves like zeroed RAM and it won't cost any RAM at all until pages are modified. Without the special "read only" page table this would cost you 40 KiB of RAM (for 10 page tables).

Now imagine a program on a 64-bit OS that uses "sbrk()" to allocate 50 GiB of heap space as soon as it starts running. Why not?


Cheers,

Brendan

[Creature]

If a process allocates a gig of memory with malloc, uses it and then releases it, it would be nice if that gig of memory could be returned to the OS for use in other programs. I've read somewhere that some OSs do it by calling sbreak with a negative number to shrink the heap.

I understand your point of view, but I would just mark the header as free then, so the entire heap knows it's allocatable again, but why should I make the heap itself span over a smaller size (contract it), removing the entire block in the process? If I don't, and something smaller is needed, the block is simply split. If I do contract, I will need to re-allocate what I just contracted (if there isn't enough space in the heap).

[JohnnyTheDon]

If a process allocates a gig of memory with malloc, uses it and then releases it, it would be nice if that gig of memory could be returned to the OS for use in other programs. I've read somewhere that some OSs do it by calling sbreak with a negative number to shrink the heap.

I understand your point of view, but I would just mark the header as free then, so the entire heap knows it's allocatable again, but why should I make the heap itself span over a smaller size (contract it), removing the entire block in the process? If I don't, and something smaller is needed, the block is simply split. If I do contract, I will need to re-allocate what I just contracted (if there isn't enough space in the heap).

Yes, but from the perspective of the OS and any other programs on the system a full gigabyte of memory has just been leaked. It might be used in the future by the program, but its also a possibility that the program will run for another week without allocating more than a few megabytes. The best case in this situation is that the gigabyte of memory remains paged out (where it is still wasting a considerable amount of swap space) and the worst case is that there is no swap file and a gigabyte of memory is now being held by a process that isn't using it.

[yemista]

How would you know when you should shrink the heap though? The scenario Im thinking of is, lets say you are running two programs, and the heap is already full. Program A needs 5KB of memory, so you expand the heap by two pages. Program B needs 1GB, so you expand the heap again. Now, when program B exits, obviously youd want to reclaim that space rather than having it all hoarded out to the user heap, but when program A exits, would you really want to reclaim those two pages? Given the fact that you had to expand the heap, you could assume that maybe there is a big workload being put on the system, so there is a good chance you would need to expand again, but of course you dont want to expand too much as in the case of the 1GB request, and also, and extra 8KB of space on the heap doesnt seem like a big deal.

Maybe the heap should have a fixed size and expand as needed, but always contract as it can? But, if you were to do that, lets say we have the same scenario, this time program B requests its memory first, then program A, and program B exits. Now we have that 1GB free, but so long as program A is running, it needs its RAM, and assuming the RAM was allocated sequentially, you cant contract the heap in this instance because program A has already been told where its memory is, and it happens to be at the far end of the heap, you cant just move it backwards, but if you dont, you cant reclaim the memory that was used by program B

[JamesM]

How would you know when you should shrink the heap though? The scenario Im thinking of is, lets say you are running two programs, and the heap is already full. Program A needs 5KB of memory, so you expand the heap by two pages. Program B needs 1GB, so you expand the heap again. Now, when program B exits, obviously youd want to reclaim that space rather than having it all hoarded out to the user heap, but when program A exits, would you really want to reclaim those two pages? Given the fact that you had to expand the heap, you could assume that maybe there is a big workload being put on the system, so there is a good chance you would need to expand again, but of course you dont want to expand too much as in the case of the 1GB request, and also, and extra 8KB of space on the heap doesnt seem like a big deal.

Maybe the heap should have a fixed size and expand as needed, but always contract as it can? But, if you were to do that, lets say we have the same scenario, this time program B requests its memory first, then program A, and program B exits. Now we have that 1GB free, but so long as program A is running, it needs its RAM, and assuming the RAM was allocated sequentially, you cant contract the heap in this instance because program A has already been told where its memory is, and it happens to be at the far end of the heap, you cant just move it backwards, but if you dont, you cant reclaim the memory that was used by program B

You seem to be under the assumption that the user-mode heap has anything whatsoever to do with the kernel heap. It doesn't. As far as the OS is concerned every process runs in its own virtual address space. System calls allow a user program to request more memory be mapped into its address space - the OS merely finds a free physical page and maps it in.

The user heap is built on top of this. When a process exits, its entire VM image is destroyed, so all those physical pages are returned to the kernel for reallocation.

JohnnyTheDon's point is that while the process is active, those pages are used up - no other process can use them. If the process isn't using them any more, it seems normal to release them.

[Creature]

I think I understand better what falls under the category 'contracting' now; it's not just about 'making the heap smaller', but the more important part of the contraction is the 'releasing the pages' part, so other applications will have access to these pages when they need to allocate something as well.