Printable View
Have any of you created a program that can determine the state of the Heap. In other words, is there a lot of holes from freed memory in between allocated memory ?
I guess the term for this is Heap Compaction, and I am interested in how this is achieved.
Yes, I've done this kind of thing many times. Essentially, what you need to do is find documentation on the O/S's memory manager. Because what you are trying to do is to walk the memory manager tables/structs/pointer-lists for your heapzone.
Trap Calls
Structures
Block Lists (Master Pointers)
Block Headers
Zone Headers
---
Understand that Windows does not use Heap Compaction. In truth, it considers you to have a 4GB virtual RAM space. It deals with fragmentation by creating a master pointer to a list of addresses where indiscriminant RAMchunks are located. It uses said list to "glue" the fragmented RAM together in one block. It's a good idea, albeit slow to implement due to overhead.
Most other systems rely on the compaction method to maintain big chunks of freed RAM. This is done also with master pointers, but handled in a different way.
No matter which way you choose, there are some underlying principles to understand about Memory Management that most people never delve into, or even realize.
I'm going to cant my discussion towards Compactible RAM, since that's what you want to learn about.
Rule #1-- Even your computer has to use RAM to keep track of where RAM blocks are.
Usually, on every RAMblock allocated for any purpose, whether or not it's a Heap Zone, or a malloc()'d block, there will be about 12 bytes of header information on the block.
So, when you say the following:
The memory manager does this:Code:char *myPointer;
myPointer = nil;
myPointer = (char*)malloc(100L); /* grab 100 bytes */
if(myPointer)
{
...
};
...
######## <-- 12-byte block header
########
----------------
######## <-- myPointer points here
########
########
########
########
########
########
To reference the block header, it simply accesses the same pointer you use (that's how it keeps track of the block) and offsets negative 12 bytes from there. Then it can look at it's own information about the block.
Such information might include whether the block is unmovable or movable (like for a true handle), the address of the last byte in the block or the block's size (I've seen it both ways), as well as other various flags and information pertinent to the Memory Manager.
Likewise, when an application starts to run, one of the loader processes is to allocate a heapzone out of available raw RAM.
To do this, a block like the one above is allocated, but at the same time, it is attached to another structure called a 'zone header block'. This is maintained in a linked list. Each heap is described by a ZoneHeader.
By knowing the total RAM available to the machine, walking the zoneheader list, and then walking each heap's blockheader list, you can tell all about RAM for the system, as well as for each heap. The addresses and sizes when accounted and calculated will tell you where and how much RAM is in use and free.
---
One thing to bear in mind. The main difference between windows and many memory manager schemes is that under windows, blocks are not movable. The address you have for a specific allocation never changes once allocated. That's why windows instead employs an expensive scheme to "glue" any-sized available chunks together until enough is "glued" together to meet the request. What makes this difficult is that computer programs expect RAM to be consecutively addressable. That means that under windows, there are 2 (TWO) layers of memory management. A low level, which glues random blocks together to fit specific requests, and a high-level memory manager which presents said "glueblocks" to applications as consecutively addressed RAMblocks. In other words, memory mapping.
This means compaction is not necessary because if you really do run out of RAM, you're really out-- atleast that's the theory behind their scheme. It also means pointers only become invalid if stepped on.
On the other hand, compactable memory schemes, instead of creating a second layer of transparent memory management, instead simply create another layer of indirection (a middle layer of pointers you're not aware of).
This gives you the ability to allocate pointers (nonmovable blocks) down low in the heap, and handles (movable blocks) way high in the heap.
A 'handle', which is not Microsoft's idea of a handle, is actually just another pointer. However, instead of pointing at a RAMblock, it points to another pointer, called a Master Pointer. The Master Pointer, in turn, actually points at the RAMblock.
Like so:
Code:
typedef char* Ptr;
typedef Ptr* Handle;
Handle myHandle;
myHandle = nil;
myHandle = (Handle)halloc(100L); /* grab 100 bytes */
if(myHandle)
{
...
};
...
######## <-- 12-byte block header
########
----------------
######## <-- Master Pointer points here <-- Handle points here
########
########
########
########
########
########
The reason it is done this way, is because your application only sees the handle. The memory manager only looks at the master pointer. In this way, it can move or "float" the bock itself around anywhere it likes, invalidating its own pointer as often as it likes, without invalidating yours. Nothing breaks.
---
When an operating system is called to Compact a Heap, what it tries to do is, dispose of all disposable RAM, move blocks until they are contiguous (it can't move nonmovable pointer blocks), and unload unused segments (back in the days of segment loading).
Perhaps this will give you a start...
enjoy.
Yes, I've done this kind of thing many times. Essentially, what you need to do is find documentation on the O/S's memory manager. Because what you are trying to do is to walk the memory manager tables/structs/pointer-lists for your heapzone.
Trap Calls
Structures
Block Lists (Master Pointers)
Block Headers
Zone Headers
---
Understand that Windows does not use Heap Compaction. In truth, it considers you to have a 4GB virtual RAM space. It deals with fragmentation by creating a master pointer to a list of addresses where indiscriminant RAMchunks are located. It uses said list to "glue" the fragmented RAM together in one block. It's a good idea, albeit slow to implement due to overhead.
Most other systems rely on the compaction method to maintain big chunks of freed RAM. This is done also with master pointers, but handled in a different way.
No matter which way you choose, there are some underlying principles to understand about Memory Management that most people never delve into, or even realize.
I'm going to cant my discussion towards Compactible RAM, since that's what you want to learn about.
Rule #1-- Even your computer has to use RAM to keep track of where RAM blocks are.
Usually, on every RAMblock allocated for any purpose, whether or not it's a Heap Zone, or a malloc()'d block, there will be about 12 bytes of header information on the block.
So, when you say the following:
The memory manager does this:Code:char *myPointer;
myPointer = nil;
myPointer = (char*)malloc(100L); /* grab 100 bytes */
if(myPointer)
{
...
};
...
######## <-- 12-byte block header
########
----------------
######## <-- myPointer points here
########
########
########
########
########
########
To reference the block header, it simply accesses the same pointer you use (that's how it keeps track of the block) and offsets negative 12 bytes from there. Then it can look at it's own information about the block.
Such information might include whether the block is unmovable or movable (like for a true handle), the address of the last byte in the block or the block's size (I've seen it both ways), as well as other various flags and information pertinent to the Memory Manager.
Likewise, when an application starts to run, one of the loader processes is to allocate a heapzone out of available raw RAM.
To do this, a block like the one above is allocated, but at the same time, it is attached to another structure called a 'zone header block'. This is maintained in a linked list. Each heap is described by a ZoneHeader.
By knowing the total RAM available to the machine, walking the zoneheader list, and then walking each heap's blockheader list, you can tell all about RAM for the system, as well as for each heap. The addresses and sizes when accounted and calculated will tell you where and how much RAM is in use and free.
---
One thing to bear in mind. The main difference between windows and many memory manager schemes is that under windows, blocks are not movable. The address you have for a specific allocation never changes once allocated. That's why windows instead employs an expensive scheme to "glue" any-sized available chunks together until enough is "glued" together to meet the request. What makes this difficult is that computer programs expect RAM to be consecutively addressable. That means that under windows, there are 2 (TWO) layers of memory management. A low level, which glues random blocks together to fit specific requests, and a high-level memory manager which presents said "glueblocks" to applications as consecutively addressed RAMblocks. In other words, memory mapping.
This means compaction is not necessary because if you really do run out of RAM, you're really out-- atleast that's the theory behind their scheme. It also means pointers only become invalid if stepped on.
On the other hand, compactable memory schemes, instead of creating a second layer of transparent memory management, instead simply create another layer of indirection (a middle layer of pointers you're not aware of).
This gives you the ability to allocate pointers (nonmovable blocks) down low in the heap, and handles (movable blocks) way high in the heap.
A 'handle', which is not Microsoft's idea of a handle, is actually just another pointer. However, instead of pointing at a RAMblock, it points to another pointer, called a Master Pointer. The Master Pointer, in turn, actually points at the RAMblock.
Like so:
Code:
typedef char* Ptr;
typedef Ptr* Handle;
Handle myHandle;
myHandle = nil;
myHandle = (Handle)halloc(100L); /* grab 100 bytes */
if(myHandle)
{
...
};
...
######## <-- 12-byte block header
########
----------------
######## <-- Master Pointer points here <-- Handle points here
########
########
########
########
########
########
The reason it is done this way, is because your application only sees the handle. The memory manager only looks at the master pointer. In this way, it can move or "float" the bock itself around anywhere it likes, invalidating its own pointer as often as it likes, without invalidating yours. Nothing breaks.
---
When an operating system is called to Compact a Heap, what it tries to do is, dispose of all disposable RAM, move blocks until they are contiguous (it can't move nonmovable pointer blocks), and unload unused segments (back in the days of segment loading).
Perhaps this will give you a start...
enjoy.
Thank you for all of this helpful information, this is much appreciated. :)