3 #include <HashVector.h>
5 #define LARGE_HEAP_SIZE (1048576)
7 #define CEILX(V,D) ((int)(((V)+(D)-1)/(D)))
8 #define CEIL(V,D) (CEILX(V,D)*(D))
10 extern EFI_BOOT_SERVICES *boot_services;
12 static void *real_malloc(size_t size) {
13 size_t pages = CEILX( size, EFI_PAGE_SIZE );
14 EFI_PHYSICAL_ADDRESS p = 0;
15 if ( boot_services->AllocatePages(
16 AllocateAnyPages, EfiLoaderData, pages, &p ) != EFI_SUCCESS ) {
22 static void real_free(void *p,size_t size) {
23 size_t pages = CEILX( size, EFI_PAGE_SIZE );
24 (void) boot_services->FreePages( (EFI_PHYSICAL_ADDRESS) p, pages );
27 static void memclear(char *p,size_t size) {
34 typedef struct ChunkHead {
36 struct ChunkHead *data;
39 static ChunkHead *free_chunks;
41 void* malloc(size_t size) {
42 // Adjust allocation size to include a preceding size count
43 size_t asize = CEIL( size + sizeof( size_t ), sizeof( ChunkHead ) );
44 if ( asize >= LARGE_HEAP_SIZE ) {
45 // Managed without subdivision
46 ChunkHead *p = real_malloc( asize );
48 return (void*) &p->data;
50 // Cut out a chunk by subdivision adjusted to an even number of
52 ChunkHead *this = free_chunks;
54 for ( ; this ; prev = this, this = this->data ) {
55 if ( this->size < asize ) {
58 // Cut out an allocation chunk here,
59 size_t rest = this->size - asize;
60 ChunkHead *next = this->data;
61 if ( rest >= sizeof( ChunkHead ) ) {
62 next = (ChunkHead *) (((char*)this) + asize);
63 next->data = this->data;
71 memclear( (char*) this, sizeof( ChunkHead ) );
73 return (void*) ((char*)this) + sizeof( size_t );
75 // No subdivision available; add a new subdivision page and try
76 // again. Note that this contains its own ChunkHead.
77 this = (ChunkHead *) real_malloc( LARGE_HEAP_SIZE );
78 memclear( (char*) this, LARGE_HEAP_SIZE );
79 this->size = LARGE_HEAP_SIZE;
80 this->data = free_chunks;
82 return malloc( size );
89 ChunkHead *chp = (ChunkHead *) ( ((char*) p) - sizeof( size_t ) );
90 if ( chp->size >= LARGE_HEAP_SIZE ) {
91 real_free( p, chp->size );
94 // find nearest ChunkHead in the free_chunks list.
95 ChunkHead *this = free_chunks;
97 for ( ; this; prev = this, this = this->data ) {
98 if ( (void*) this >= p ) {
104 this->data = free_chunks;
107 this->data = prev->data;
109 if ( ((char*)prev->data) + prev->size == (char*)this ) {
110 // collapse into single area
111 prev->size += this->size;
114 // Maybe this emptied a subdivision block, except the last?
115 if ( this->data && ((char*)this) + this->size == (char*)(this->data) ) {
116 this->size += this->data->size;
118 // Yes. That should also be freed
119 if ( this->size == LARGE_HEAP_SIZE || this->data ) {
122 for ( ; this; prev = this, this = this->data ) {
125 prev->data = this->data;
127 free_chunks = this->data;
129 real_free( this, this->size );