shheap.c@ 2376

Last change on this file since 2376 was 2308, checked in by bird, 16 years ago
kash: Fixed wrong assumption in sh_free.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 15.2 KB

Line
1	/* $Id: shheap.c 2308 2009-03-01 10:01:02Z bird $ */
2	/** @file
3	* The shell memory heap methods.
4	*/
5
6	/*
7	* Copyright (c) 2009 knut st. osmundsen <[email protected]>
8	*
9	*
10	* This file is part of kBuild.
11	*
12	* kBuild is free software; you can redistribute it and/or modify
13	* it under the terms of the GNU General Public License as published by
14	* the Free Software Foundation; either version 2 of the License, or
15	* (at your option) any later version.
16	*
17	* kBuild is distributed in the hope that it will be useful,
18	* but WITHOUT ANY WARRANTY; without even the implied warranty of
19	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20	* GNU General Public License for more details.
21	*
22	* You should have received a copy of the GNU General Public License
23	* along with kBuild; if not, write to the Free Software
24	* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25	*
26	*/
27
28	/*******************************************************************************
29	* Header Files *
30	*******************************************************************************/
31	#include "shheap.h"
32	#include <string.h>
33	#include <stdlib.h>
34	#include <assert.h>
35	#include "shinstance.h"
36
37	#if K_OS == K_OS_WINDOWS
38	# define SHHEAP_IN_USE
39	#endif
40
41	#ifdef SHHEAP_IN_USE
42	# if K_OS == K_OS_WINDOWS
43	# include <Windows.h>
44	# else
45	# include <unistd.h>
46	# endif
47	#endif
48
49
50	/*******************************************************************************
51	* Structures and Typedefs *
52	*******************************************************************************/
53	#ifdef SHHEAP_IN_USE
54	/**
55	* heap memory block header.
56	*/
57	typedef struct shmemhdr
58	{
59	size_t magic; /*< Magic value /
60	size_t size; /*< The block size /
61	struct shmemhdr next; /< Forward pointer. /
62	struct shmemhdr prev; /< Backward pointer. /
63	struct shmemhdr next2; /< Free/Shell list forward. /
64	struct shmemhdr prev2; /< Free/Shell list backward. /
65	struct shinstance psh; /< The shell who allocated it. /
66	struct shmemchunk chunk; /< The chunk who owns this. /
67	} shmemhdr;
68
69	/** Free block magic (shmemhdr::magic) */
70	#define SHMEMHDR_MAGIC_FREE 0xbeeff00d
71	/** Used block magic (shmemhdr::magic) */
72	#define SHMEMHDR_MAGIC_USED 0xfeedface
73
74	typedef struct shmemchunk
75	{
76	struct shmemhdr head; /< Head of the block list. /
77	struct shmemhdr free_head; /< Head of the free list. /
78	struct shmemchunk next; /< The next block. /
79	struct shmemchunk prev; /< The previous block. /
80	size_t size; /*< Chunk size. /
81	size_t magic; /*< Magic value. /
82	size_t padding0;
83	size_t padding1;
84	} shmemchunk;
85
86	/** shmemchunk::magic */
87	#define SHMEMCHUNK_MAGIC 0x12345678
88
89	#endif /* K_OS_WINDOWS */
90
91
92	/*******************************************************************************
93	* Defined Constants And Macros *
94	*******************************************************************************/
95	#define SHHEAP_ALIGN(sz) (((sz) + 31) & ~(size_t)31)
96	#define SHHEAP_CHUNK_ALIGN(sz) (((sz) + 0xffff) & ~(size_t)0xffff)
97	#define SHHEAP_MIN_CHUNK 0x10000 //(1024*1024)
98	#ifdef NDEBUG
99	# define SHHEAP_CHECK() do { } while (0)
100	# define SHHEAP_CHECK_2() do { } while (0)
101	# define SHHEAP_ASSERT(expr) do { } while (0)
102	# define SHHEAP_POISON_PSH(p,v) (p)
103	# define SHHEAP_POISON_NULL(v) NULL
104	#else
105	# define SHHEAP_CHECK() shheap_check()
106	# define SHHEAP_CHECK_2() shheap_check()
107	# define SHHEAP_ASSERT(expr) assert(expr)
108	# define SHHEAP_POISON_PSH(p,v) ((shinstance *)(v))
109	# define SHHEAP_POISON_NULL(v) ((void *)(v))
110	#endif
111
112
113	/*******************************************************************************
114	* Global Variables *
115	*******************************************************************************/
116	#ifdef SHHEAP_IN_USE
117	/** The heap lock. */
118	static shmtx g_sh_heap_mtx;
119	/** The heap.
120	* This is a list of chunks. */
121	static shmemchunk *g_sh_heap;
122	#endif
123
124
125	int shheap_init(void)
126	{
127	int rc;
128	#ifdef SHHEAP_IN_USE
129	SHHEAP_ASSERT(SHHEAP_ALIGN(sizeof(shmemhdr)) == sizeof(shmemhdr));
130	rc = shmtx_init(&g_sh_heap_mtx);
131	#else
132	rc = 0;
133	#endif
134	return rc;
135	}
136
137	#ifdef SHHEAP_IN_USE
138
139	# if K_OS == K_OS_WINDOWS
140	/**
141	* Copies the heap into the child process.
142	*
143	* @returns 0 on success, -1 and errno on failure.
144	* @param hChild Handle to the child process.
145	*/
146	int shheap_fork_copy_to_child(void *hChild)
147	{
148	shmemchunk *chunk;
149	shmtxtmp tmp;
150	int err = 0;
151
152	shmtx_enter(&g_sh_heap_mtx, &tmp);
153
154	for (chunk = g_sh_heap; chunk; chunk = chunk->next)
155	{
156	void *chld_chnk;
157
158	chld_chnk = (shmemchunk *)VirtualAllocEx(hChild, chunk, chunk->size,
159	MEM_COMMIT \| MEM_RESERVE, PAGE_EXECUTE_READWRITE);
160	if (chld_chnk != chunk)
161	{
162	err = GetLastError();
163	fprintf(stderr, "shfork: VirtualAllocEx(,%p,%p,) -> %d\n", chunk, chunk->size, err);
164	break;
165	}
166
167	if (!WriteProcessMemory(hChild, chunk, chunk, chunk->size, NULL /* pNumberOfBytesWritten */))
168	{
169	err = GetLastError();
170	fprintf(stderr, "shfork: WriteProcessMemory(,%p,,%p,) -> %d\n", chunk, chunk->size, err);
171	break;
172	}
173	}
174
175	shmtx_leave(&g_sh_heap_mtx, &tmp);
176
177	if (!err)
178	return 0;
179	errno = EINVAL;
180	return -1;
181	}
182	# endif
183
184
185	/**
186	* Checks a heap chunk.
187	* @param chunk The chunk to check.
188	*/
189	static void shheap_check_chunk(shmemchunk *chunk)
190	{
191	size_t free_count;
192	struct shmemhdr *mem;
193	struct shmemhdr *prev;
194
195	SHHEAP_ASSERT(chunk->magic == SHMEMCHUNK_MAGIC);
196	SHHEAP_ASSERT(chunk->head);
197	SHHEAP_ASSERT(chunk->size == SHHEAP_CHUNK_ALIGN(chunk->size));
198
199	free_count = 0;
200	prev = NULL;
201	for (mem = chunk->head; mem; mem = mem->next)
202	{
203	size_t size = (mem->next ? (char )mem->next : (char )chunk + chunk->size) - (char *)(mem + 1);
204	SHHEAP_ASSERT(mem->size == size);
205	SHHEAP_ASSERT(mem->prev == prev);
206	if (mem->magic == SHMEMHDR_MAGIC_FREE)
207	free_count++;
208	else
209	SHHEAP_ASSERT(mem->magic == SHMEMHDR_MAGIC_USED);
210	prev = mem;
211	}
212
213	prev = NULL;
214	for (mem = chunk->free_head; mem; mem = mem->next2)
215	{
216	size_t size = (mem->next ? (char )mem->next : (char )chunk + chunk->size) - (char *)(mem + 1);
217	SHHEAP_ASSERT(mem->size == size);
218	SHHEAP_ASSERT(mem->prev2 == prev);
219	SHHEAP_ASSERT(mem->magic == SHMEMHDR_MAGIC_FREE);
220	free_count--;
221	prev = mem;
222	}
223	SHHEAP_ASSERT(free_count == 0);
224	}
225
226	/**
227	* Checks the heap.
228	*/
229	static void shheap_check(void)
230	{
231	shmemchunk *chunk;
232	for (chunk = g_sh_heap; chunk; chunk = chunk->next)
233	shheap_check_chunk(chunk);
234	}
235
236	/**
237	* Grows the heap with another chunk carving out a block
238	*
239	* @returns Pointer to a used entry of size @a size1. NULL
240	* if we're out of memory
241	* @param size1 The size of the block to be returned (aligned).
242	*/
243	static shmemhdr *shheap_grow(size_t size1)
244	{
245	shmemchunk *chunk;
246	shmemhdr *used;
247	shmemhdr *avail;
248	size_t chunk_size;
249
250	/* Calc the chunk size and allocate it. */
251	chunk_size = SHHEAP_ALIGN(size1) + SHHEAP_ALIGN(sizeof(chunk)) + SHHEAP_ALIGN(sizeof(used)) * 10;
252	if (chunk_size < SHHEAP_MIN_CHUNK)
253	chunk_size = SHHEAP_MIN_CHUNK;
254	else
255	chunk_size = SHHEAP_CHUNK_ALIGN(chunk_size);
256
257	# if K_OS == K_OS_WINDOWS
258	chunk = (shmemchunk *)VirtualAlloc(NULL, chunk_size, MEM_COMMIT \| MEM_RESERVE, PAGE_EXECUTE_READWRITE);
259	# else
260	chunk = NULL;
261	# endif
262
263	if (!chunk)
264	return NULL;
265
266	used = (shmemhdr )((char )chunk + SHHEAP_ALIGN(sizeof(*chunk)));
267	avail = (shmemhdr )((char )(used + 1) + size1);
268
269	used->magic = SHMEMHDR_MAGIC_USED;
270	used->size = size1;
271	used->next = avail;
272	used->prev = NULL;
273	used->next2 = SHHEAP_POISON_NULL(0x41);
274	used->prev2 = SHHEAP_POISON_NULL(0x41);
275	used->psh = NULL;
276	used->chunk = chunk;
277
278	avail->magic = SHMEMHDR_MAGIC_FREE;
279	avail->size = (char )chunk + chunk_size - (char )(avail + 1);
280	avail->next = NULL;
281	avail->prev = used;
282	avail->next2 = NULL;
283	avail->prev2 = NULL;
284	avail->psh = NULL;
285	avail->chunk = chunk;
286
287	chunk->head = used;
288	chunk->free_head = avail;
289	chunk->size = chunk_size;
290	chunk->magic = SHMEMCHUNK_MAGIC;
291	chunk->prev = NULL;
292	chunk->next = g_sh_heap;
293	if (g_sh_heap)
294	g_sh_heap->prev = chunk;
295	g_sh_heap = chunk;
296	chunk->padding0 = 0;
297	chunk->padding1 = 0;
298
299	SHHEAP_CHECK_2();
300	return used;
301	}
302
303	/***
304	* Splits a big memory block into two smaller, one with the
305	* size @a size1.
306	*
307	* The one with the given size is removed from the free list
308	* while the other one remains there.
309	*
310	* @returns The @a size1 sized block, NULL on failure.
311	* @param big The block that is too big.
312	* @param size1 The size of the block to be returned (aligned).
313	*/
314	static shmemhdr shheap_split(shmemhdr big, size_t size1)
315	{
316	shmemhdr *split;
317	SHHEAP_ASSERT(SHHEAP_ALIGN(sizeof(big)) == sizeof(big));
318	SHHEAP_ASSERT(big->magic == SHMEMHDR_MAGIC_FREE);
319	SHHEAP_ASSERT(!big->next2 \|\| big->next2->magic == SHMEMHDR_MAGIC_FREE);
320	SHHEAP_ASSERT(!big->prev2 \|\| big->prev2->magic == SHMEMHDR_MAGIC_FREE);
321
322	split = (shmemhdr )((uint8_t )(big + 1) + size1);
323	split->magic = SHMEMHDR_MAGIC_FREE;
324	split->size = big->size - size1 - sizeof(*split);
325	split->next = big->next;
326	split->prev = big;
327	split->next2 = big->next2;
328	split->prev2 = big->prev2;
329	split->psh = SHHEAP_POISON_NULL(0x54);
330	split->chunk = big->chunk;
331
332	if (big->next2)
333	big->next2->prev2 = split;
334	if (big->prev2)
335	big->prev2->next2 = split;
336	else
337	big->chunk->free_head = split;
338
339	big->magic = SHMEMHDR_MAGIC_USED;
340	big->next2 = big->prev2 = SHHEAP_POISON_NULL(0x41);
341
342	if (big->next)
343	big->next->prev = split;
344	big->next = split;
345	big->size = size1;
346
347	SHHEAP_CHECK_2();
348	return big;
349	}
350
351	/***
352	* Unlinks a free memory block.
353	* @param mem The block to unlink.
354	*/
355	static void shheap_unlink_free(shmemhdr *mem)
356	{
357	if (mem->next2)
358	mem->next2->prev2 = mem->prev2;
359	if (mem->prev2)
360	mem->prev2->next2 = mem->next2;
361	else
362	mem->chunk->free_head = mem->next2;
363	mem->magic = SHMEMHDR_MAGIC_USED;
364	mem->next2 = mem->prev2 = SHHEAP_POISON_NULL(0x42);
365	}
366
367	#endif /* SHHEAP_IN_USE */
368
369
370	/** free() */
371	void sh_free(shinstance psh, void ptr)
372	{
373	#ifdef SHHEAP_IN_USE
374	shmemhdr mem = (shmemhdr )ptr - 1;
375	shmemhdr *right;
376	shmemhdr *left;
377	shmtxtmp tmp;
378
379	if (mem->magic != SHMEMHDR_MAGIC_USED)
380	{
381	SHHEAP_ASSERT(0);
382	return;
383	}
384
385	shmtx_enter(&g_sh_heap_mtx, &tmp);
386	SHHEAP_CHECK();
387
388	/* join right. */
389	right = mem->next;
390	if ( right
391	&& right->magic == SHMEMHDR_MAGIC_FREE)
392	{
393	mem->next = right->next;
394	if (right->next)
395	right->next->prev = mem;
396
397	mem->next2 = right->next2;
398	if (right->next2)
399	right->next2->prev2 = mem;
400	mem->prev2 = right->prev2;
401	if (right->prev2)
402	mem->prev2->next2 = mem;
403	else
404	mem->chunk->free_head = mem;
405
406	mem->size += sizeof(*right) + right->size;
407	mem->magic = SHMEMHDR_MAGIC_FREE;
408	right->magic = ~SHMEMHDR_MAGIC_FREE;
409	mem->psh = SHHEAP_POISON_NULL(0x50);
410	SHHEAP_CHECK_2();
411	}
412
413	/* join left */
414	left = mem->prev;
415	if ( left
416	&& left->magic == SHMEMHDR_MAGIC_FREE)
417	{
418	left->next = mem->next;
419	if (mem->next)
420	mem->next->prev = left;
421
422	if (mem->magic == SHMEMHDR_MAGIC_FREE)
423	{
424	if (mem->next2)
425	mem->next2->prev2 = mem->prev2;
426	if (mem->prev2)
427	mem->prev2->next2 = mem->next2;
428	else
429	mem->chunk->free_head = mem->next2;
430	}
431
432	left->size += sizeof(*mem) + mem->size;
433	mem->magic = ~SHMEMHDR_MAGIC_USED;
434	left->psh = SHHEAP_POISON_NULL(0x51);
435	}
436
437	/* insert as free if necessary */
438	else if (mem->magic == SHMEMHDR_MAGIC_USED)
439	{
440	mem->prev2 = NULL;
441	mem->next2 = mem->chunk->free_head;
442	if (mem->chunk->free_head)
443	mem->chunk->free_head->prev2 = mem;
444	mem->chunk->free_head = mem;
445	mem->magic = SHMEMHDR_MAGIC_FREE;
446	mem->psh = SHHEAP_POISON_NULL(0x52);
447	}
448
449	SHHEAP_CHECK();
450	shmtx_leave(&g_sh_heap_mtx, &tmp);
451	#else
452	if (ptr)
453	free(ptr);
454	(void)psh;
455	#endif
456	}
457
458	/** malloc() */
459	void sh_malloc(shinstance psh, size_t size)
460	{
461	#ifdef SHHEAP_IN_USE
462	shmemchunk *chunk;
463	shmemhdr *mem;
464	shmtxtmp tmp;
465
466	size = SHHEAP_ALIGN(size);
467	SHHEAP_ASSERT(size);
468	if (!size)
469	size = SHHEAP_ALIGN(1);
470
471	shmtx_enter(&g_sh_heap_mtx, &tmp);
472	SHHEAP_CHECK();
473
474
475	/* Search for fitting block */
476	mem = NULL;
477	chunk = g_sh_heap;
478	while (chunk)
479	{
480	mem = chunk->free_head;
481	while (mem && mem->size < size)
482	mem = mem->next2;
483	if (mem)
484	break;
485	chunk = chunk->next;
486	}
487	if (mem)
488	{
489	/* split it, or just unlink it? */
490	if (mem->size - size > sizeof(mem) 2)
491	mem = shheap_split(mem, size);
492	else
493	shheap_unlink_free(mem);
494	}
495	else
496	{
497	/* no block found, try grow the heap. */
498	mem = shheap_grow(size);
499	if (!mem)
500	{
501	shmtx_leave(&g_sh_heap_mtx, &tmp);
502	return NULL;
503	}
504	}
505
506	SHHEAP_CHECK();
507	shmtx_leave(&g_sh_heap_mtx, &tmp);
508
509	mem->psh = SHHEAP_POISON_PSH(psh, 0x53);
510
511	return mem + 1;
512
513	#else
514	(void)psh;
515	return malloc(size);
516	#endif
517	}
518
519	/** calloc() */
520	void sh_calloc(shinstance psh, size_t num, size_t item_size)
521	{
522	#ifdef SHHEAP_IN_USE
523	size_t size = num * item_size;
524	void *pv = sh_malloc(psh, size);
525	if (pv)
526	pv = memset(pv, '\0', size);
527	return pv;
528	#else
529	(void)psh;
530	return calloc(num, item_size);
531	#endif
532	}
533
534	/** realloc() */
535	void sh_realloc(shinstance psh, void *old, size_t new_size)
536	{
537	#ifdef SHHEAP_IN_USE
538	void *pv;
539	if (new_size)
540	{
541	if (old)
542	{
543	shmemhdr hdr = (shmemhdr )old - 1;
544	if (hdr->size < new_size)
545	{
546	pv = sh_malloc(psh, new_size);
547	if (pv)
548	{
549	memcpy(pv, old, hdr->size);
550	sh_free(psh, old);
551	}
552	}
553	else
554	pv = old;
555	}
556	else
557	pv = sh_malloc(psh, new_size);
558	}
559	else
560	{
561	sh_free(psh, old);
562	pv = NULL;
563	}
564	return pv;
565	#else
566	return realloc(old, new_size);
567	#endif
568	}
569
570	/** strdup() */
571	char sh_strdup(shinstance psh, const char *string)
572	{
573	size_t len = strlen(string);
574	char *ret = sh_malloc(psh, len + 1);
575	if (ret)
576	memcpy(ret, string, len + 1);
577	return ret;
578	}
579
580

Note: See TracBrowser for help on using the repository browser.

source: kBuild/trunk/src/kash/shheap.c@ 2376

Download in other formats: