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	niro	532	/*
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	niro	815	#include <assert.h>
11	niro	532	#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			}