Page 1 of 1

Microsoft : Taming The Heap Monster Rate Topic: -----

#1 Martyn.Rae   User is offline

  • The programming dinosaur
  • member icon

Reputation: 555
  • View blog
  • Posts: 1,436
  • Joined: 22-August 09

Posted 07 April 2011 - 02:19 PM

Microsoft : Taming The Heap Monster

Introduction

In the tutorial entitled Microsoft : Beware of the Heap Monster I discussed the very real problem of heap memory fragmentation. This is caused by the allocation and deallocation of heap memory, especially when the allocations are many, of different sizes and the order in which blocks are deallocated is random.

I am not very happy with the conclusion of that tutorial, as it offers little in the way of discussing solutions. This tutorial details a possible solution and, whilst not being elegant may help some of you out there struggling to tame the heap monster.

Program Phases

All programs follow the same fundamental phases of execution, namely initialization, run and termination.

Now, generally speaking, objects that are dynamically allocated during the initialization phase are permanent and only get deallocated in the termination phase. Placing items on the heap that are intended as a permanent feature during the lifetime of the application is not a problem and does not contribute to heap memory fragmentation.

Heap allocations that occur during the run phase however are where the big problem lies, as such items are for the most part transient. It is these allocations and deallocations we need to address.

Run Cycles

This is a term I have invented for progressing the tutorial. What I mean by a run cycle is a distinct logical block of processing that results from some input to produce some output - whether that be physical output in terms of writing data to a file or screen, or some logical output such as changing the state of the run. (A perfect example a run cycle would be the processing of a windows message received in the GetMessage(...)/DispatchMessage(...) loop).

Permanent And Temporary Heaps

An executable can create as many heaps as it requires, as each heap has a unique heap handle returned when the heap is created. We could allocate two distinctly separate heaps for the permanent and transient allocations, and rather than deallocate individual heap items (therefore undermining the whole purpose of overcoming heap fragmentation), simply delete and recreate the heap at the end of each run cycle. This approach would certainly remove heap fragmentation, but the solution needs to also address the inordinate amount of time applications spend in the heap trying to find a block that meets the allocation criteria, and deallocating the block once it has served it's purpose.

High-speed Allocations

Rather than use the operating system heap, we are going to write our own. Now this might sound like an inordinate amount of work to produce a result that could not possibly be as good as that which has been provided by the Microsoft Windows operating system. This is where you are wrong, as we are not interested in a heap in which we are going to deallocate items. There will be no need for such housekeeping as allocated heap block pointers and free space heap pointers. We just want a mechanism that will allocate a block of memory of any size from somewhere and return a pointer to it's address. At the end of the cycle, we throw the allocated memory away and start again.

We shall use the VirtualAlloc and VirtualFree operating system routines to allocate and deallocate virtual memory pages as and when we need them. To permit the heap to grow, we shall reserve a huge amount of memory. This reserves memory in the address space of the application, but does not actually allocate physical pages. Each page is 4096 bytes in length, so we will know when we need to commit new memory pages to permit the allocation to occur successfully.

The Code

I have chosen to implement a three heap allocation scheme, named permanent, semi-permanent and transient (you are free to add more of course).

memory_allocation.h
#pragma once

#define PERMANENT_BASE_SIZE 67108864
#define SEMI_PERMANENT_BASE_SIZE 67108864
#define TRANSIENT_BASE_SIZE 67108864

typedef enum { permanent, semi_permanent, transient } new_allocation_type;

void initialize_new(new_allocation_type mode);
void *__CRTDECL operator new(size_t size, new_allocation_type mode);



memory_allocation.cpp
#include <Windows.h>
#include "heapmemory.h"
#define MEMORY_FINALIZE // Comment this line if you are debugging

void * memory_base[3] = { NULL, NULL, NULL };
void * memory_current[3] = { NULL, NULL, NULL };
int memory_size[3] = { PERMANENT_BASE_SIZE, SEMI_PERMANENT_BASE_SIZE, TRANSIENT_BASE_SIZE };

void initialize_new(new_allocation_type mode) {
#ifdef MEMORY_FINALIZE
	if ( memory_base[mode] != NULL ) VirtualFree(memory_base[mode], memory_size[mode], MEM_DECOMMIT);
	memory_base[mode] = memory_current[mode] = VirtualAlloc(NULL, memory_size[mode], MEM_RESERVE, PAGE_READWRITE);
	VirtualAlloc(memory_base[mode], 4096, MEM_COMMIT, PAGE_READWRITE);
#endif
	return;
}

void *__CRTDECL operator new(size_t size, new_allocation_type mode) {
#ifdef MEMORY_FINALIZE
	void * the_allocation, *work_pointer;
	the_allocation = work_pointer = memory_current[mode];
	while ( (((int)work_pointer)>>12) != ((((int)the_allocation)+size)>>12) ) {
		VirtualAlloc((LPVOID)(((((int)work_pointer)>>12)<<12) + 4096), 4096, MEM_COMMIT, PAGE_READWRITE);
		work_pointer = (LPVOID)(((((int)work_pointer)>>12)<<12) + 4096);
	}
	memory_current[mode] = (LPVOID)(((int)the_allocation)+size);
	return the_allocation;
#else
	return ::operator new(size);
#endif
};



It should be noted that to free any allocations once the initialize_new routine has been called, simply call the initialize_new routine again.

Also, please note that this mechanism does not recognize writing outside of the area requested for allocation. I have included a flag (MEMORY_FINALIZE) which if not defined causes the routines to revert to the default heap management system. Only when you are satisfied that the code is working, should you define the flag.

Is This A Good Question/Topic? 2
  • +

Replies To: Microsoft : Taming The Heap Monster

#2 David W   User is offline

  • DIC supporter
  • member icon

Reputation: 298
  • View blog
  • Posts: 1,839
  • Joined: 20-September 08

Posted 10 April 2011 - 06:09 PM

It was good that you included a link to your first tutorial on the 'MS heap monster'...

http://www.dreaminco...e-heap-monster/

I think you did a really good job there of shedding some light on your 'heap monster' :)

This post has been edited by David W: 10 April 2011 - 06:11 PM

Was This Post Helpful? 0
  • +
  • -

#3 smohd   User is offline

  • Critical Section
  • member icon


Reputation: 1825
  • View blog
  • Posts: 4,627
  • Joined: 14-March 10

Posted 11 April 2011 - 02:10 PM

View PostDavid W, on 11 April 2011 - 06:54 AM, said:

It was good that you included a link to your first tutorial on the 'MS heap monster'...

http://www.dreaminco...e-heap-monster/

He included it, look at the first line!
Was This Post Helpful? 0
  • +
  • -

#4 David W   User is offline

  • DIC supporter
  • member icon

Reputation: 298
  • View blog
  • Posts: 1,839
  • Joined: 20-September 08

Posted 11 April 2011 - 03:30 PM

View Postsmohd, on 11 April 2011 - 05:10 PM, said:

View PostDavid W, on 11 April 2011 - 06:54 AM, said:

It was good that you included a link to your first tutorial on the 'MS heap monster'...

http://www.dreaminco...e-heap-monster/

He included it, look at the first line!

Yes ... that was what I said ... it WAS good that the link WAS included... So it seems that we both agree ... that the first article was really quite very good :)
Was This Post Helpful? 0
  • +
  • -

#5 Martyn.Rae   User is offline

  • The programming dinosaur
  • member icon

Reputation: 555
  • View blog
  • Posts: 1,436
  • Joined: 22-August 09

Posted 14 January 2019 - 09:20 PM

For those that read this article, please note that the allocation page size is assumed to be 4096. This used to be the case, but with x64 processing being more normal, the page size has been increased significantly. The safest way to obtain this value is to call GetSystemInfo that takes the address of a SYSTEM_INFO structure in which you will find a field dwAllocationGranularity that contains the page allocation size.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1