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 }