plibc/lib/malloc.c

#include "malloc.h"
#include "stddef.h"
#include "stdio.h"
#include "unistd.h"
#include "utils.h"
#include <stdbool.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	#include "malloc.h"
2	#include "stddef.h"
3	#include "stdio.h"
4	#include "unistd.h"
5	#include "utils.h"
6	#include <stdbool.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	}