plibc/lib/malloc.c

#include "malloc.h"
#include "stdio.h"
#include "syscalls.h"
#include "utils.h"
#include <stdbool.h>
#include <stddef.h>

struct malloc_chunk
{
    size_t size;
    void *ptr;
    struct malloc_chunk *next;
    struct malloc_chunk *prev;
    bool free;
};

static struct malloc_chunk *head = NULL;
static struct malloc_chunk *tail = NULL;

static struct malloc_chunk *free_chunk_head = NULL;
static struct malloc_chunk *free_chunk_tail = NULL;
static size_t free_chunk_count = 0;

static void *init_mbrk = NULL;

static void
malloc_init ()
{
    init_mbrk = brk ();
}

static void *
unfree (struct malloc_chunk *chunk)
{
    if (chunk->prev != NULL)
        chunk->prev->next = chunk->next;

    if (chunk->next != NULL)
        chunk->next->prev = chunk->prev;

    if (chunk == head)
        head = chunk->next;

    if (chunk == tail)
        tail = chunk->prev;

    if (free_chunk_head == chunk)
        free_chunk_head = chunk->next;

    if (free_chunk_tail == chunk)
        free_chunk_tail = chunk->prev;

    if (chunk->free)
        free_chunk_count--;

    chunk->free = false;
    return chunk->ptr;
}

static void
reduce_brk ()
{
    if (free_chunk_count <= 3)
        return;

    struct malloc_chunk *chunk = free_chunk_tail;
    intptr_t lowest_brk = 0;
    void *b = brk ();

    while (chunk != NULL)
        {
            if (tail >= chunk || !chunk->free
                || (lowest_brk != 0 && lowest_brk < (intptr_t) chunk)
                || (intptr_t) b < (intptr_t) chunk)
                {
                    chunk = chunk->prev;
                    continue;
                }

            if (chunk->prev != NULL)
                chunk->prev->next = chunk->next;

            if (chunk->next != NULL)
                chunk->next->prev = chunk->prev;

            if (chunk == free_chunk_head)
                free_chunk_head = chunk->next;

            if (chunk == free_chunk_tail)
                free_chunk_tail = chunk->prev;

            struct malloc_chunk *prev = chunk->prev;
            lowest_brk = (intptr_t) chunk;
            chunk = prev;
        }

    if (lowest_brk == 0)
        return;

    if (sbrk ((intptr_t) lowest_brk) == (void *) -1)
        {
            printf ("reduce_brk(): sbrk failed\n");
            abort ();
        }
}

void *
malloc (size_t size)
{
    reduce_brk ();

    if (size == 0)
        return NULL;

    if (free_chunk_head != NULL && free_chunk_head->free
        && free_chunk_head->size >= size)
        return unfree (free_chunk_head);

    if (free_chunk_tail != NULL && free_chunk_tail->free
        && free_chunk_tail->size >= size)
        return unfree (free_chunk_tail);

    struct malloc_chunk *chunk = free_chunk_tail;

    while (chunk != NULL)
        {
            if (chunk->free && chunk->size >= size)
                return unfree (chunk);

            chunk = chunk->prev;
        }

    if (init_mbrk == NULL)
        malloc_init ();

    size_t mc_size = sizeof (struct malloc_chunk);
    void *b = brk ();
    intptr_t new_ptr = (intptr_t) (((unsigned char *) b) + size + mc_size);

    if (sbrk (new_ptr) == (void *) -1)
        return NULL;

    chunk = (struct malloc_chunk *) b;
    chunk->size = size;
    chunk->ptr = (void *) (((unsigned char *) b) + mc_size);
    chunk->next = NULL;
    chunk->prev = tail;
    chunk->free = false;

    tail = chunk;

    if (head == NULL)
        head = chunk;

    return chunk->ptr;
}

static void __noreturn
invalid_ptr (const char *func)
{
    printf ("%s(): invalid pointer\n", func);
    abort ();
}

static void __noreturn
double_free (void *ptr, size_t size)
{
    printf ("free(): double free detected: %p (block size %zu)\n", ptr, size);
    abort ();
}

void
free (void *ptr)
{
    reduce_brk ();

    size_t mc_size = sizeof (struct malloc_chunk);
    struct malloc_chunk *chunk
        = (struct malloc_chunk *) (((unsigned char *) ptr) - mc_size);

    if (chunk == NULL)
        invalid_ptr (__func__);

    if (chunk->ptr != ptr)
        invalid_ptr (__func__);

    if (chunk->free)
        double_free (chunk->ptr, chunk->size);

    free_chunk_count++;
    chunk->free = true;

    if (chunk->prev != NULL)
        chunk->prev->next = chunk->next;

    if (chunk->next != NULL)
        chunk->next->prev = chunk->prev;

    if (chunk == head)
        head = chunk->next;

    if (chunk == tail)
        tail = chunk->prev;

    if (free_chunk_head == NULL)
        {
            free_chunk_head = chunk;
            free_chunk_tail = chunk;
            chunk->next = NULL;
            chunk->prev = NULL;
        }
    else
        {
            free_chunk_tail->next = chunk;
            chunk->prev = free_chunk_tail;
            chunk->next = NULL;
            free_chunk_tail = chunk;
        }
}

void
bzero (void *ptr, size_t size)
{
    for (size_t i = 0; i < size; i++)
        ((unsigned char *) ptr)[i] = 0;
}

void *
calloc (size_t nmemb, size_t size)
{
    size_t total_size = nmemb * size;
    void *ptr = malloc (total_size);

    if (ptr == NULL)
        return NULL;

    bzero (ptr, total_size);
    return ptr;
}

void *
realloc (void *ptr, size_t size)
{
    if (ptr == NULL)
        return malloc (size);

    size_t mc_size = sizeof (struct malloc_chunk);
    struct malloc_chunk *chunk
        = (struct malloc_chunk *) (((unsigned char *) ptr) - mc_size);

    if (chunk == NULL)
        invalid_ptr (__func__);

    if (chunk->ptr != ptr)
        invalid_ptr (__func__);

    if (chunk->size >= size)
        return ptr;

    if (tail == chunk)
        {
            reduce_brk ();

            size_t new_size = size - chunk->size;
            void *b = brk ();
            intptr_t new_ptr = (intptr_t) (((unsigned char *) b) + new_size);

            if (sbrk (new_ptr) == (void *) -1)
                return NULL;

            chunk->size = size;
            return ptr;
        }

    void *new_ptr = malloc (size);

    if (new_ptr == NULL)
        return NULL;

    for (size_t i = 0; i < chunk->size; i++)
        ((unsigned char *) new_ptr)[i] = ((unsigned char *) ptr)[i];

    free (ptr);
    return new_ptr;
}

void
__plibc_heap_reset (void)
{
    if (init_mbrk == NULL)
        return;

    if (sbrk ((intptr_t) init_mbrk) == (void *) -1)
        {
            printf ("__plibc_heap_reset(): sbrk failed\n");
            abort ();
        }

    head = NULL;
    tail = NULL;
    free_chunk_head = NULL;
    free_chunk_tail = NULL;
    free_chunk_count = 0;
}
1	rakinar2	47	#include "malloc.h"
2			#include "stdio.h"
3			#include "syscalls.h"
4			#include "utils.h"
5			#include <stdbool.h>
6			#include <stddef.h>
7
8			struct malloc_chunk
9			{
10			size_t size;
11			void *ptr;
12			struct malloc_chunk *next;
13			struct malloc_chunk *prev;
14			bool free;
15			};
16
17			static struct malloc_chunk *head = NULL;
18			static struct malloc_chunk *tail = NULL;
19
20			static struct malloc_chunk *free_chunk_head = NULL;
21			static struct malloc_chunk *free_chunk_tail = NULL;
22			static size_t free_chunk_count = 0;
23
24			static void *init_mbrk = NULL;
25
26			static void
27			malloc_init ()
28			{
29			init_mbrk = brk ();
30			}
31
32			static void *
33			unfree (struct malloc_chunk *chunk)
34			{
35			if (chunk->prev != NULL)
36			chunk->prev->next = chunk->next;
37
38			if (chunk->next != NULL)
39			chunk->next->prev = chunk->prev;
40
41			if (chunk == head)
42			head = chunk->next;
43
44			if (chunk == tail)
45			tail = chunk->prev;
46
47			if (free_chunk_head == chunk)
48			free_chunk_head = chunk->next;
49
50			if (free_chunk_tail == chunk)
51			free_chunk_tail = chunk->prev;
52
53			if (chunk->free)
54			free_chunk_count--;
55
56			chunk->free = false;
57			return chunk->ptr;
58			}
59
60			static void
61			reduce_brk ()
62			{
63			if (free_chunk_count <= 3)
64			return;
65
66			struct malloc_chunk *chunk = free_chunk_tail;
67			intptr_t lowest_brk = 0;
68			void *b = brk ();
69
70			while (chunk != NULL)
71			{
72			if (tail >= chunk \|\| !chunk->free
73			\|\| (lowest_brk != 0 && lowest_brk < (intptr_t) chunk)
74			\|\| (intptr_t) b < (intptr_t) chunk)
75			{
76			chunk = chunk->prev;
77			continue;
78			}
79
80			if (chunk->prev != NULL)
81			chunk->prev->next = chunk->next;
82
83			if (chunk->next != NULL)
84			chunk->next->prev = chunk->prev;
85
86			if (chunk == free_chunk_head)
87			free_chunk_head = chunk->next;
88
89			if (chunk == free_chunk_tail)
90			free_chunk_tail = chunk->prev;
91
92			struct malloc_chunk *prev = chunk->prev;
93			lowest_brk = (intptr_t) chunk;
94			chunk = prev;
95			}
96
97			if (lowest_brk == 0)
98			return;
99
100			if (sbrk ((intptr_t) lowest_brk) == (void *) -1)
101			{
102			printf ("reduce_brk(): sbrk failed\n");
103			abort ();
104			}
105			}
106
107			void *
108			malloc (size_t size)
109			{
110			reduce_brk ();
111
112			if (size == 0)
113			return NULL;
114
115			if (free_chunk_head != NULL && free_chunk_head->free
116			&& free_chunk_head->size >= size)
117			return unfree (free_chunk_head);
118
119			if (free_chunk_tail != NULL && free_chunk_tail->free
120			&& free_chunk_tail->size >= size)
121			return unfree (free_chunk_tail);
122
123			struct malloc_chunk *chunk = free_chunk_tail;
124
125			while (chunk != NULL)
126			{
127			if (chunk->free && chunk->size >= size)
128			return unfree (chunk);
129
130			chunk = chunk->prev;
131			}
132
133			if (init_mbrk == NULL)
134			malloc_init ();
135
136			size_t mc_size = sizeof (struct malloc_chunk);
137			void *b = brk ();
138			intptr_t new_ptr = (intptr_t) (((unsigned char *) b) + size + mc_size);
139
140			if (sbrk (new_ptr) == (void *) -1)
141			return NULL;
142
143			chunk = (struct malloc_chunk *) b;
144			chunk->size = size;
145			chunk->ptr = (void ) (((unsigned char ) b) + mc_size);
146			chunk->next = NULL;
147			chunk->prev = tail;
148			chunk->free = false;
149
150			tail = chunk;
151
152			if (head == NULL)
153			head = chunk;
154
155			return chunk->ptr;
156			}
157
158			static void __noreturn
159			invalid_ptr (const char *func)
160			{
161			printf ("%s(): invalid pointer\n", func);
162			abort ();
163			}
164
165			static void __noreturn
166			double_free (void *ptr, size_t size)
167			{
168			printf ("free(): double free detected: %p (block size %zu)\n", ptr, size);
169			abort ();
170			}
171
172			void
173			free (void *ptr)
174			{
175			reduce_brk ();
176
177			size_t mc_size = sizeof (struct malloc_chunk);
178			struct malloc_chunk *chunk
179			= (struct malloc_chunk ) (((unsigned char ) ptr) - mc_size);
180
181			if (chunk == NULL)
182			invalid_ptr (__func__);
183
184			if (chunk->ptr != ptr)
185			invalid_ptr (__func__);
186
187			if (chunk->free)
188			double_free (chunk->ptr, chunk->size);
189
190			free_chunk_count++;
191			chunk->free = true;
192
193			if (chunk->prev != NULL)
194			chunk->prev->next = chunk->next;
195
196			if (chunk->next != NULL)
197			chunk->next->prev = chunk->prev;
198
199			if (chunk == head)
200			head = chunk->next;
201
202			if (chunk == tail)
203			tail = chunk->prev;
204
205			if (free_chunk_head == NULL)
206			{
207			free_chunk_head = chunk;
208			free_chunk_tail = chunk;
209			chunk->next = NULL;
210			chunk->prev = NULL;
211			}
212			else
213			{
214			free_chunk_tail->next = chunk;
215			chunk->prev = free_chunk_tail;
216			chunk->next = NULL;
217			free_chunk_tail = chunk;
218			}
219			}
220
221			void
222			bzero (void *ptr, size_t size)
223			{
224			for (size_t i = 0; i < size; i++)
225			((unsigned char *) ptr)[i] = 0;
226			}
227
228			void *
229			calloc (size_t nmemb, size_t size)
230			{
231			size_t total_size = nmemb * size;
232			void *ptr = malloc (total_size);
233
234			if (ptr == NULL)
235			return NULL;
236
237			bzero (ptr, total_size);
238			return ptr;
239			}
240
241			void *
242			realloc (void *ptr, size_t size)
243			{
244			if (ptr == NULL)
245			return malloc (size);
246
247			size_t mc_size = sizeof (struct malloc_chunk);
248			struct malloc_chunk *chunk
249			= (struct malloc_chunk ) (((unsigned char ) ptr) - mc_size);
250
251			if (chunk == NULL)
252			invalid_ptr (__func__);
253
254			if (chunk->ptr != ptr)
255			invalid_ptr (__func__);
256
257			if (chunk->size >= size)
258			return ptr;
259
260			if (tail == chunk)
261			{
262			reduce_brk ();
263
264			size_t new_size = size - chunk->size;
265			void *b = brk ();
266			intptr_t new_ptr = (intptr_t) (((unsigned char *) b) + new_size);
267
268			if (sbrk (new_ptr) == (void *) -1)
269			return NULL;
270
271			chunk->size = size;
272			return ptr;
273			}
274
275			void *new_ptr = malloc (size);
276
277			if (new_ptr == NULL)
278			return NULL;
279
280			for (size_t i = 0; i < chunk->size; i++)
281			((unsigned char ) new_ptr)[i] = ((unsigned char ) ptr)[i];
282
283			free (ptr);
284			return new_ptr;
285			}
286
287			void
288			__plibc_heap_reset (void)
289			{
290			if (init_mbrk == NULL)
291			return;
292
293			if (sbrk ((intptr_t) init_mbrk) == (void *) -1)
294			{
295			printf ("__plibc_heap_reset(): sbrk failed\n");
296			abort ();
297			}
298
299			head = NULL;
300			tail = NULL;
301			free_chunk_head = NULL;
302			free_chunk_tail = NULL;
303			free_chunk_count = 0;
304			}