1 module tagion.betterC.utils.Malloc; 2 3 extern (C) { 4 void set_memory(void* ptr, size_t size) { 5 free_block_list_head = cast(FreeBlock*)(ptr); 6 (*free_block_list_head).size = size - FreeBlock.sizeof; 7 8 // (size-FreeBlock.sizeof, cast(FreeBlock*)ptr); 9 FreeBlock* end_of_memory = free_block_list_head - FreeBlock.sizeof; 10 *end_of_memory = FreeBlock.init; 11 } 12 } 13 14 @nogc nothrow { 15 16 struct FreeBlock { 17 size_t size; 18 FreeBlock* next; 19 } 20 21 FreeBlock* free_block_list_head; 22 enum overhead = size_t.sizeof; 23 enum align_to = size_t.sizeof * 2; 24 25 void* malloc(size_t size) { 26 size = (size + size_t.sizeof + (align_to - 1)) & ~(align_to - 1); 27 FreeBlock* prev_block = free_block_list_head; 28 // scope(success) { 29 // } 30 for (FreeBlock* block = free_block_list_head; block !is null; block = block.next) { 31 // FreeBlock* block = free_block_list_head.next; 32 // FreeBlock** head = &(free_block_list_head.next); 33 // while (block !is null) { 34 // writefln("Block size before %d", block.size); 35 if (block.size >= size) { 36 void* result = cast(void*) block + overhead; 37 // scope(exit) { 38 39 // } 40 if (block.size > size) { 41 FreeBlock* rest = cast(FreeBlock*)(cast(void*) block + size + overhead); 42 // (*head).next = rest; 43 rest.size = block.size - size - overhead; 44 rest.next = block.next; 45 block.size = size; 46 block.next = rest; 47 // if (block is free_block_list_head) { 48 // free_block_list_head = block.next; 49 // } 50 // else { 51 // prev_block.next = block.next; 52 // } 53 // writefln("block.size=%d", block.size); 54 // writefln("size=%d rest.size=%d", size, rest.size); 55 } 56 // else { 57 if (block is free_block_list_head) { 58 free_block_list_head = block.next; 59 } 60 else { 61 prev_block.next = block.next; 62 } 63 // (*head) = block.next; 64 // } 65 // void* result=block + overhead; 66 (cast(size_t*) result)[0 .. size / size_t.sizeof] = 0; 67 return result; 68 } 69 prev_block = block; 70 // head = &(block.next); 71 // block = block.next; 72 } 73 // block = (free_block*)sbrk(size); 74 // block->size = size; 75 76 // return ((char*)block) + sizeof(size_t); 77 78 assert(0, "Out of memory"); 79 } 80 81 void* calloc(size_t nmemb, size_t size) { 82 return malloc(nmemb * size); 83 } 84 85 void* realloc(void* ptr, size_t size) { 86 FreeBlock* block = cast(FreeBlock*)(ptr - overhead); 87 if (size <= block.size) { 88 return ptr; 89 } 90 auto result = malloc(size); 91 scope (exit) { 92 free(ptr); 93 } 94 (cast(size_t*) result)[0 .. block.size / size_t.sizeof] = 95 (cast(size_t*) ptr)[0 .. block.size / size_t.sizeof]; 96 return result; 97 } 98 99 void free(void* ptr) { 100 FreeBlock* block = cast(FreeBlock*)(ptr - overhead); 101 assert(free_block_list_head !is ptr, "Double free"); 102 block.next = free_block_list_head; 103 free_block_list_head = block; 104 } 105 106 bool isFree(void* ptr) { 107 FreeBlock* search_ptr = cast(FreeBlock*)(ptr - overhead); 108 for (FreeBlock* block = free_block_list_head; block !is null; block = block.next) { 109 if (search_ptr is block) { 110 return true; 111 } 112 } 113 return false; 114 } 115 116 size_t sizeOf(void* ptr) { 117 FreeBlock* block = cast(FreeBlock*)(ptr - overhead); 118 return block.size; 119 } 120 121 size_t avail() { 122 size_t result; 123 for (FreeBlock* block = free_block_list_head; block !is null; block = block.next) { 124 result += block.size; 125 } 126 return result; 127 } 128 129 size_t bigest() { 130 import std.algorithm.comparison : max; 131 132 size_t result; 133 for (FreeBlock* block = free_block_list_head; block !is null; block = block.next) { 134 result = max(result, block.size); 135 } 136 return result; 137 } 138 } 139 140 unittest { 141 import std.stdio; 142 143 void dump() { 144 for (FreeBlock* block = free_block_list_head; block !is null; block = block.next) { 145 writefln("%s : %2d 0x%02x", block, block.size, block.size); 146 } 147 } 148 // writeln("------------- ---------------"); 149 const mem_size = FreeBlock.sizeof * 32; 150 auto mem = new ubyte[mem_size]; 151 set_memory(mem.ptr, mem_size); 152 153 // writefln("%s", *free_block_list_head); 154 // writefln("free_block_list_head.size=%s", free_block_list_head.size); 155 auto _avail = avail; 156 // writefln("%s", avail); 157 158 auto ptr1 = malloc(33); 159 assert(!isFree(ptr1)); 160 // writefln("%s", *free_block_list_head); 161 // writefln("ptr1=%s %s", ptr1, ptr1.sizeOf); 162 // writefln("avail=%d _avail=%d %d %d", avail, _avail, ptr1.sizeOf,overhead); 163 _avail -= ptr1.sizeOf + overhead; 164 165 assert(avail == _avail); 166 167 // writefln("%s", *free_block_list_head); 168 auto ptr2 = malloc(100); 169 assert(!isFree(ptr2)); 170 // writefln("ptr2=%s %s", ptr2, ptr2.sizeOf); 171 // writefln("%s", *free_block_list_head); 172 _avail -= ptr2.sizeOf + overhead; 173 174 assert(avail == _avail); 175 176 // writefln("%s", *free_block_list_head); 177 // writefln("avail=%s", avail); 178 auto ptr3 = malloc(48); 179 assert(!isFree(ptr3)); 180 // writefln("ptr3=%s %s", ptr3, ptr3.sizeOf); 181 // writefln("%s", *free_block_list_head); 182 // writefln("%s", avail); 183 _avail -= ptr3.sizeOf + overhead; 184 185 assert(avail == _avail); 186 187 auto ptr4 = malloc(48); 188 assert(!isFree(ptr4)); 189 // writefln("ptr3=%s %s", ptr3, ptr3.sizeOf); 190 // writefln("%s", *free_block_list_head); 191 // writefln("%s", avail); 192 _avail -= ptr4.sizeOf + overhead; 193 194 assert(avail == _avail); 195 _avail += ptr3.sizeOf; 196 // dump; 197 198 // writefln("Before free avail=%d ptr3.sizeOf=%d", avail, ptr3.sizeOf); 199 free(ptr3); 200 assert(isFree(ptr3)); 201 // writefln("%s", *free_block_list_head); 202 // writefln("%s", avail); 203 // writefln("avail=%d _avail=%d", avail, _avail); 204 assert(avail == _avail); 205 // dump; 206 207 auto ptr5 = malloc(58); 208 assert(!isFree(ptr5)); 209 _avail -= ptr5.sizeOf + overhead; 210 // writefln("ptr5 avail=%d _avail=%d", avail, _avail); 211 // dump; 212 assert(avail == _avail); 213 214 auto ptr6 = malloc(70); 215 assert(!ptr6.isFree); 216 _avail -= ptr6.sizeOf + overhead; 217 // writefln("ptr6 avail=%d _avail=%d", avail, _avail); 218 assert(avail == _avail); 219 _avail += ptr5.sizeOf; 220 221 free(ptr5); 222 assert(ptr5.isFree); 223 // writefln("avail=%d _avail=%d", avail, _avail); 224 assert(avail == _avail); 225 // foreach(i;0..4) { 226 // malloc(20); 227 // } 228 229 // writefln("ptr5 %s ", ptr5); 230 // dump; 231 auto ptr7 = malloc(52); 232 assert(!ptr7.isFree); 233 _avail -= ptr7.sizeOf + overhead; 234 235 // writefln("avail=%d _avail=%d", avail, _avail); 236 237 // dump; 238 auto ptr8 = malloc(30); 239 _avail -= ptr8.sizeOf + overhead; 240 // writefln("avail=%d _avail=%d", avail, _avail); 241 242 // dump; 243 244 // Reuse ptr2 245 246 // auto ptr4 = malloc(54); 247 // writefln("avail=%d ptr4.sizeOf=%d", avail, ptr4.sizeOf); 248 // writefln("ptr2=%s ptr4=%s", ptr2, ptr4); 249 250 } 251 252 unittest { /// calloc 253 import std.stdio; 254 255 const mem_size = FreeBlock.sizeof * 32; 256 auto mem = new ubyte[mem_size]; 257 set_memory(mem.ptr, mem_size); 258 259 auto ptr1 = malloc(64); 260 auto array_ptr1 = cast(byte*) ptr1; 261 array_ptr1[0] = -42; 262 array_ptr1[63] = 42; 263 264 // writefln("%d", ptr1.sizeOf); 265 assert(ptr1.sizeOf == 80); 266 267 auto ptr2 = realloc(ptr1, 100); 268 // writefln("%d", ptr2.sizeOf); 269 // writefln("%s", isFree(ptr1)); 270 auto array_ptr2 = cast(byte*) ptr2; 271 272 assert(ptr1.isFree); 273 assert(!ptr2.isFree); 274 assert(ptr2.sizeOf == 112); 275 assert(array_ptr2[0] == -42); 276 assert(array_ptr2[63] == 42); 277 }