shheap.c

Last change on this file was 3477, checked in by bird, 4 years ago
kash: Use kHlpAssert instead of assert.h (debugger stops on the assertion rather than at exit process code).
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 15.5 KB

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

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

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

Download in other formats: