usr/klibc/malloc.c

/*
 * malloc.c
 *
 * Very simple linked-list based malloc()/free().
 */

#include <stdlib.h>
#include <unistd.h>
#include <sys/mman.h>
#include <assert.h>
#include "malloc.h"

/* Both the arena list and the free memory list are double linked
   list with head node.  This the head node. Note that the arena list
   is sorted in order of address. */
static struct free_arena_header __malloc_head = {
	{
		ARENA_TYPE_HEAD,
		0,
		&__malloc_head,
		&__malloc_head,
	},
	&__malloc_head,
	&__malloc_head
};

static inline void mark_block_dead(struct free_arena_header *ah)
{
#ifdef DEBUG_MALLOC
	ah->a.type = ARENA_TYPE_DEAD;
#endif
}

static inline void remove_from_main_chain(struct free_arena_header *ah)
{
	struct free_arena_header *ap, *an;

	mark_block_dead(ah);

	ap = ah->a.prev;
	an = ah->a.next;
	ap->a.next = an;
	an->a.prev = ap;
}

static inline void remove_from_free_chain(struct free_arena_header *ah)
{
	struct free_arena_header *ap, *an;

	ap = ah->prev_free;
	an = ah->next_free;
	ap->next_free = an;
	an->prev_free = ap;
}

static inline void remove_from_chains(struct free_arena_header *ah)
{
	remove_from_free_chain(ah);
	remove_from_main_chain(ah);
}

static void *__malloc_from_block(struct free_arena_header *fp, size_t size)
{
	size_t fsize;
	struct free_arena_header *nfp, *na, *fpn, *fpp;

	fsize = fp->a.size;

	/* We need the 2* to account for the larger requirements of a
	   free block */
	if (fsize >= size + 2 * sizeof(struct arena_header)) {
		/* Bigger block than required -- split block */
		nfp = (struct free_arena_header *)((char *)fp + size);
		na = fp->a.next;

		nfp->a.type = ARENA_TYPE_FREE;
		nfp->a.size = fsize - size;
		fp->a.type = ARENA_TYPE_USED;
		fp->a.size = size;

		/* Insert into all-block chain */
		nfp->a.prev = fp;
		nfp->a.next = na;
		na->a.prev = nfp;
		fp->a.next = nfp;

		/* Replace current block on free chain */
		nfp->next_free = fpn = fp->next_free;
		nfp->prev_free = fpp = fp->prev_free;
		fpn->prev_free = nfp;
		fpp->next_free = nfp;
	} else {
		fp->a.type = ARENA_TYPE_USED; /* Allocate the whole block */
		remove_from_free_chain(fp);
	}

	return (void *)(&fp->a + 1);
}

static struct free_arena_header *__free_block(struct free_arena_header *ah)
{
	struct free_arena_header *pah, *nah;

	pah = ah->a.prev;
	nah = ah->a.next;
	if (pah->a.type == ARENA_TYPE_FREE &&
	    (char *)pah + pah->a.size == (char *)ah) {
		/* Coalesce into the previous block */
		pah->a.size += ah->a.size;
		pah->a.next = nah;
		nah->a.prev = pah;
		mark_block_dead(ah);

		ah = pah;
		pah = ah->a.prev;
	} else {
		/* Need to add this block to the free chain */
		ah->a.type = ARENA_TYPE_FREE;

		ah->next_free = __malloc_head.next_free;
		ah->prev_free = &__malloc_head;
		__malloc_head.next_free = ah;
		ah->next_free->prev_free = ah;
	}

	/* In either of the previous cases, we might be able to merge
	   with the subsequent block... */
	if (nah->a.type == ARENA_TYPE_FREE &&
	    (char *)ah + ah->a.size == (char *)nah) {
		ah->a.size += nah->a.size;

		/* Remove the old block from the chains */
		remove_from_chains(nah);
	}

	/* Return the block that contains the called block */
	return ah;
}

void *malloc(size_t size)
{
	struct free_arena_header *fp;
	struct free_arena_header *pah;
	size_t fsize;

	if (size == 0)
		return NULL;

	/* Add the obligatory arena header, and round up */
	size = (size + 2 * sizeof(struct arena_header) - 1) & ARENA_SIZE_MASK;

	for (fp = __malloc_head.next_free; fp->a.type != ARENA_TYPE_HEAD;
	     fp = fp->next_free) {
		if (fp->a.size >= size) {
			/* Found fit -- allocate out of this block */
			return __malloc_from_block(fp, size);
		}
	}

	/* Nothing found... need to request a block from the kernel */
	fsize = (size + MALLOC_CHUNK_MASK) & ~MALLOC_CHUNK_MASK;

#if _KLIBC_MALLOC_USES_SBRK
	fp = (struct free_arena_header *)sbrk(fsize);
#else
	fp = (struct free_arena_header *)
	    mmap(NULL, fsize, PROT_READ | PROT_WRITE,
		 MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
#endif

	if (fp == (struct free_arena_header *)MAP_FAILED) {
		return NULL;	/* Failed to get a block */
	}

	/* Insert the block into the management chains.  We need to set
	   up the size and the main block list pointer, the rest of
	   the work is logically identical to free(). */
	fp->a.type = ARENA_TYPE_FREE;
	fp->a.size = fsize;

	/* We need to insert this into the main block list in the proper
	   place -- this list is required to be sorted.  Since we most likely
	   get memory assignments in ascending order, search backwards for
	   the proper place. */
	for (pah = __malloc_head.a.prev; pah->a.type != ARENA_TYPE_HEAD;
	     pah = pah->a.prev) {
		if (pah < fp)
			break;
	}

	/* Now pah points to the node that should be the predecessor of
	   the new node */
	fp->a.next = pah->a.next;
	fp->a.prev = pah;
	pah->a.next = fp;
	fp->a.next->a.prev = fp;

	/* Insert into the free chain and coalesce with adjacent blocks */
	fp = __free_block(fp);

	/* Now we can allocate from this block */
	return __malloc_from_block(fp, size);
}

void free(void *ptr)
{
	struct free_arena_header *ah;

	if (!ptr)
		return;

	ah = (struct free_arena_header *)
	    ((struct arena_header *)ptr - 1);

#ifdef DEBUG_MALLOC
	assert(ah->a.type == ARENA_TYPE_USED);
#endif

	/* Merge into adjacent free blocks */
	ah = __free_block(ah);

	/* See if it makes sense to return memory to the system */
#if _KLIBC_MALLOC_USES_SBRK
	if (ah->a.size >= _KLIBC_MALLOC_CHUNK_SIZE &&
	    (char *)ah + ah->a.size == __current_brk) {
		remove_from_chains(ah);
		brk(ah);
	}
#else
	{
		size_t page_size = getpagesize();
		size_t page_mask = page_size - 1;
		size_t head_portion = -(size_t)ah & page_mask;
		size_t tail_portion = ((size_t)ah + ah->a.size) & page_mask;
		size_t adj_size;

		/* Careful here... an individual chunk of memory must have
		   a minimum size if it exists at all, so if either the
		   head or the tail is below the minimum, then extend
		   that chunk by a page. */

		if (head_portion &&
		    head_portion < 2*sizeof(struct arena_header))
			head_portion += page_size;

		if (tail_portion &&
		    tail_portion < 2*sizeof(struct arena_header))
			tail_portion += page_size;

		adj_size = ah->a.size - head_portion - tail_portion;

		/* Worth it?  This is written the way it is to guard
		   against overflows... */
		if (ah->a.size >= head_portion+tail_portion+
		    _KLIBC_MALLOC_CHUNK_SIZE) {
			struct free_arena_header *tah, *tan, *tap;

			if (tail_portion) {
				/* Make a new header, and insert into chains
				   immediately after the current block */
				tah = (struct free_arena_header *)
					((char *)ah + head_portion + adj_size);
				tah->a.type = ARENA_TYPE_FREE;
				tah->a.size = tail_portion;
				tah->a.next = tan = ah->a.next;
				tan->a.prev = tah;
				tah->a.prev = ah;
				ah->a.next = tah;
				tah->prev_free = tap = ah->prev_free;
				tap->next_free = tah;
				tah->next_free = ah;
				ah->prev_free = tah;
			}

			if (head_portion)
				ah->a.size = head_portion;
			else
				remove_from_chains(ah);

			munmap((char *)ah + head_portion, adj_size);
		}
	}
#endif
}
1	/*
2	* malloc.c
3	*
4	* Very simple linked-list based malloc()/free().
5	*/
6
7	#include <stdlib.h>
8	#include <unistd.h>
9	#include <sys/mman.h>
10	#include <assert.h>
11	#include "malloc.h"
12
13	/* Both the arena list and the free memory list are double linked
14	list with head node. This the head node. Note that the arena list
15	is sorted in order of address. */
16	static struct free_arena_header __malloc_head = {
17	{
18	ARENA_TYPE_HEAD,
19	0,
20	&__malloc_head,
21	&__malloc_head,
22	},
23	&__malloc_head,
24	&__malloc_head
25	};
26
27	static inline void mark_block_dead(struct free_arena_header *ah)
28	{
29	#ifdef DEBUG_MALLOC
30	ah->a.type = ARENA_TYPE_DEAD;
31	#endif
32	}
33
34	static inline void remove_from_main_chain(struct free_arena_header *ah)
35	{
36	struct free_arena_header ap, an;
37
38	mark_block_dead(ah);
39
40	ap = ah->a.prev;
41	an = ah->a.next;
42	ap->a.next = an;
43	an->a.prev = ap;
44	}
45
46	static inline void remove_from_free_chain(struct free_arena_header *ah)
47	{
48	struct free_arena_header ap, an;
49
50	ap = ah->prev_free;
51	an = ah->next_free;
52	ap->next_free = an;
53	an->prev_free = ap;
54	}
55
56	static inline void remove_from_chains(struct free_arena_header *ah)
57	{
58	remove_from_free_chain(ah);
59	remove_from_main_chain(ah);
60	}
61
62	static void __malloc_from_block(struct free_arena_header fp, size_t size)
63	{
64	size_t fsize;
65	struct free_arena_header nfp, na, fpn, fpp;
66
67	fsize = fp->a.size;
68
69	/* We need the 2* to account for the larger requirements of a
70	free block */
71	if (fsize >= size + 2 * sizeof(struct arena_header)) {
72	/* Bigger block than required -- split block */
73	nfp = (struct free_arena_header )((char )fp + size);
74	na = fp->a.next;
75
76	nfp->a.type = ARENA_TYPE_FREE;
77	nfp->a.size = fsize - size;
78	fp->a.type = ARENA_TYPE_USED;
79	fp->a.size = size;
80
81	/* Insert into all-block chain */
82	nfp->a.prev = fp;
83	nfp->a.next = na;
84	na->a.prev = nfp;
85	fp->a.next = nfp;
86
87	/* Replace current block on free chain */
88	nfp->next_free = fpn = fp->next_free;
89	nfp->prev_free = fpp = fp->prev_free;
90	fpn->prev_free = nfp;
91	fpp->next_free = nfp;
92	} else {
93	fp->a.type = ARENA_TYPE_USED; /* Allocate the whole block */
94	remove_from_free_chain(fp);
95	}
96
97	return (void *)(&fp->a + 1);
98	}
99
100	static struct free_arena_header __free_block(struct free_arena_header ah)
101	{
102	struct free_arena_header pah, nah;
103
104	pah = ah->a.prev;
105	nah = ah->a.next;
106	if (pah->a.type == ARENA_TYPE_FREE &&
107	(char )pah + pah->a.size == (char )ah) {
108	/* Coalesce into the previous block */
109	pah->a.size += ah->a.size;
110	pah->a.next = nah;
111	nah->a.prev = pah;
112	mark_block_dead(ah);
113
114	ah = pah;
115	pah = ah->a.prev;
116	} else {
117	/* Need to add this block to the free chain */
118	ah->a.type = ARENA_TYPE_FREE;
119
120	ah->next_free = __malloc_head.next_free;
121	ah->prev_free = &__malloc_head;
122	__malloc_head.next_free = ah;
123	ah->next_free->prev_free = ah;
124	}
125
126	/* In either of the previous cases, we might be able to merge
127	with the subsequent block... */
128	if (nah->a.type == ARENA_TYPE_FREE &&
129	(char )ah + ah->a.size == (char )nah) {
130	ah->a.size += nah->a.size;
131
132	/* Remove the old block from the chains */
133	remove_from_chains(nah);
134	}
135
136	/* Return the block that contains the called block */
137	return ah;
138	}
139
140	void *malloc(size_t size)
141	{
142	struct free_arena_header *fp;
143	struct free_arena_header *pah;
144	size_t fsize;
145
146	if (size == 0)
147	return NULL;
148
149	/* Add the obligatory arena header, and round up */
150	size = (size + 2 * sizeof(struct arena_header) - 1) & ARENA_SIZE_MASK;
151
152	for (fp = __malloc_head.next_free; fp->a.type != ARENA_TYPE_HEAD;
153	fp = fp->next_free) {
154	if (fp->a.size >= size) {
155	/* Found fit -- allocate out of this block */
156	return __malloc_from_block(fp, size);
157	}
158	}
159
160	/* Nothing found... need to request a block from the kernel */
161	fsize = (size + MALLOC_CHUNK_MASK) & ~MALLOC_CHUNK_MASK;
162
163	#if _KLIBC_MALLOC_USES_SBRK
164	fp = (struct free_arena_header *)sbrk(fsize);
165	#else
166	fp = (struct free_arena_header *)
167	mmap(NULL, fsize, PROT_READ \| PROT_WRITE,
168	MAP_PRIVATE \| MAP_ANONYMOUS, 0, 0);
169	#endif
170
171	if (fp == (struct free_arena_header *)MAP_FAILED) {
172	return NULL; /* Failed to get a block */
173	}
174
175	/* Insert the block into the management chains. We need to set
176	up the size and the main block list pointer, the rest of
177	the work is logically identical to free(). */
178	fp->a.type = ARENA_TYPE_FREE;
179	fp->a.size = fsize;
180
181	/* We need to insert this into the main block list in the proper
182	place -- this list is required to be sorted. Since we most likely
183	get memory assignments in ascending order, search backwards for
184	the proper place. */
185	for (pah = __malloc_head.a.prev; pah->a.type != ARENA_TYPE_HEAD;
186	pah = pah->a.prev) {
187	if (pah < fp)
188	break;
189	}
190
191	/* Now pah points to the node that should be the predecessor of
192	the new node */
193	fp->a.next = pah->a.next;
194	fp->a.prev = pah;
195	pah->a.next = fp;
196	fp->a.next->a.prev = fp;
197
198	/* Insert into the free chain and coalesce with adjacent blocks */
199	fp = __free_block(fp);
200
201	/* Now we can allocate from this block */
202	return __malloc_from_block(fp, size);
203	}
204
205	void free(void *ptr)
206	{
207	struct free_arena_header *ah;
208
209	if (!ptr)
210	return;
211
212	ah = (struct free_arena_header *)
213	((struct arena_header *)ptr - 1);
214
215	#ifdef DEBUG_MALLOC
216	assert(ah->a.type == ARENA_TYPE_USED);
217	#endif
218
219	/* Merge into adjacent free blocks */
220	ah = __free_block(ah);
221
222	/* See if it makes sense to return memory to the system */
223	#if _KLIBC_MALLOC_USES_SBRK
224	if (ah->a.size >= _KLIBC_MALLOC_CHUNK_SIZE &&
225	(char *)ah + ah->a.size == __current_brk) {
226	remove_from_chains(ah);
227	brk(ah);
228	}
229	#else
230	{
231	size_t page_size = getpagesize();
232	size_t page_mask = page_size - 1;
233	size_t head_portion = -(size_t)ah & page_mask;
234	size_t tail_portion = ((size_t)ah + ah->a.size) & page_mask;
235	size_t adj_size;
236
237	/* Careful here... an individual chunk of memory must have
238	a minimum size if it exists at all, so if either the
239	head or the tail is below the minimum, then extend
240	that chunk by a page. */
241
242	if (head_portion &&
243	head_portion < 2*sizeof(struct arena_header))
244	head_portion += page_size;
245
246	if (tail_portion &&
247	tail_portion < 2*sizeof(struct arena_header))
248	tail_portion += page_size;
249
250	adj_size = ah->a.size - head_portion - tail_portion;
251
252	/* Worth it? This is written the way it is to guard
253	against overflows... */
254	if (ah->a.size >= head_portion+tail_portion+
255	_KLIBC_MALLOC_CHUNK_SIZE) {
256	struct free_arena_header tah, tan, *tap;
257
258	if (tail_portion) {
259	/* Make a new header, and insert into chains
260	immediately after the current block */
261	tah = (struct free_arena_header *)
262	((char *)ah + head_portion + adj_size);
263	tah->a.type = ARENA_TYPE_FREE;
264	tah->a.size = tail_portion;
265	tah->a.next = tan = ah->a.next;
266	tan->a.prev = tah;
267	tah->a.prev = ah;
268	ah->a.next = tah;
269	tah->prev_free = tap = ah->prev_free;
270	tap->next_free = tah;
271	tah->next_free = ah;
272	ah->prev_free = tah;
273	}
274
275	if (head_portion)
276	ah->a.size = head_portion;
277	else
278	remove_from_chains(ah);
279
280	munmap((char *)ah + head_portion, adj_size);
281	}
282	}
283	#endif
284	}