shheap.c@ 3459

Last change on this file since 3459 was 3451, checked in by bird, 5 years ago
kash: forked-mode build fixes.
Property svn:eol-style set to `native` Property svn:keywords set to `Id`
File size: 15.5 KB

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

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

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

Download in other formats: