Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log

bmem.c @ 25

Last change on this file since 25 was 2, checked in by phkim, 11 years ago

1.phkim

revision copy newcon3sk r27

Property svn:executable set to *

File size: 64.8 KB

Line
1	/***************************************************************************
2	* Copyright (c) 2001-2012, Broadcom Corporation
3	* All Rights Reserved
4	* Confidential Property of Broadcom Corporation
5	*
6	* THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE
7	* AGREEMENT BETWEEN THE USER AND BROADCOM. YOU HAVE NO RIGHT TO USE OR
8	* EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.
9	*
10	* $brcm_Workfile: bmem.c $
11	* $brcm_Revision: Hydra_Software_Devel/81 $
12	* $brcm_Date: 2/7/12 6:36p $
13	*
14	* Module Description:
15	*
16	* Revision History:
17	*
18	* $brcm_Log: /magnum/basemodules/mem/bmem.c $
19	*
20	* Hydra_Software_Devel/81 2/7/12 6:36p albertl
21	* SW7425-2345: Changed total allocation and number of allocation tracking
22	* to work in eFastest.
23	*
24	* Hydra_Software_Devel/80 1/18/12 6:00p albertl
25	* SW7346-637: Fixed bug in free block size checking. Changed to use base
26	* address offset instead of front address offset.
27	*
28	* Hydra_Software_Devel/79 1/17/12 7:15p albertl
29	* SW7346-637: Fixed to properly check if aligned addresses run outside of
30	* selected block.
31	*
32	* Hydra_Software_Devel/78 1/12/12 4:13p albertl
33	* SW7346-637: Fixed allocation to use larger of heap and requested
34	* alignment when requesting free block.
35	*
36	* Hydra_Software_Devel/77 11/30/11 4:25p albertl
37	* SW7425-1857: Fixed unchecked BMEM_Heap_ConvertAddressToCached returns
38	* and bIsCached checking.
39	*
40	* Hydra_Software_Devel/76 11/14/11 3:16p albertl
41	* SW7425-1627: Fixed addrBase calculation in
42	* GetLargestAvailableBlockSize.
43	*
44	* Hydra_Software_Devel/75 11/14/11 2:21p albertl
45	* SW7425-1293: Fixed use of uncached address when cached addresses exist
46	* during heap creation. Fixed coverity issues.
47	*
48	* Hydra_Software_Devel/74 11/11/11 4:00p albertl
49	* SW7425-1627: Changed GetLargestAvailableBlockSize to take minimum
50	* alignment into account.
51	*
52	* Hydra_Software_Devel/73 10/25/11 4:00p albertl
53	* SW7425-1293: Fixed type punned warnings.
54	*
55	* Hydra_Software_Devel/72 10/19/11 7:03p albertl
56	* SW7425-1293: Fixed cached guardband checking and filling with proper
57	* flushing.
58	*
59	* Hydra_Software_Devel/71 10/7/11 11:26p hongtaoz
60	* SW7425-1293: rolled back the previous change;
61	*
62	* Hydra_Software_Devel/70 10/7/11 2:32p albertl
63	* SW7425-1293: Changed guardband checking and fill to use cached memory
64	* addresses when available.
65	*
66	* Hydra_Software_Devel/69 9/9/11 7:10p albertl
67	* SW7346-201: Moved watermark calculation to alloc and free for accurate
68	* calculation.
69	*
70	* Hydra_Software_Devel/68 9/8/11 4:22p albertl
71	* SW7405-5350: Changed block info to be doublely linked. Implemented
72	* faster pbi removal and assigned slower removal and error checking to
73	* BMEM_FREE_CAREFULLY.
74	*
75	* Hydra_Software_Devel/67 9/7/11 2:39p albertl
76	* SW7346-201: Changed watermark to not require allocation tracking.
77	*
78	* Hydra_Software_Devel/66 8/24/11 5:35p albertl
79	* SW7405-5349: Added line parameter to memory monitor interface.
80	*
81	* Hydra_Software_Devel/65 4/13/11 12:05p albertl
82	* SW7425-333: Added smart detection of cached address to
83	* BMEM_Heap_ConvertAddress_ToOffset.
84	*
85	* Hydra_Software_Devel/64 4/5/11 1:29p erickson
86	* SW7420-1734: remove incorrect enter/leave critical section in
87	* BMEM_Close
88	*
89	* Hydra_Software_Devel/63 3/28/11 5:12p albertl
90	* SW7425-247: Incorporated BDBG_OBJECT handle validation.
91	*
92	* Hydra_Software_Devel/62 3/7/11 5:05p albertl
93	* SW7425-131: Allow BMEM_Heap_FlushCache to work for memory allocated on
94	* any heap.
95	*
96	* Hydra_Software_Devel/61 1/10/11 3:31p albertl
97	* SW7408-193: BMEM_Heapinfo now includes high watermark. Added
98	* BMEM_Heap_ResetHighWatermark().
99	*
100	* Hydra_Software_Devel/60 4/28/10 6:48p albertl
101	* SW7405-4264: Fixed build warning.
102	*
103	* Hydra_Software_Devel/59 4/15/10 3:26p albertl
104	* SW7550-370: Fixed alignment to occur on physical addresses rather than
105	* virtual addresses.
106	*
107	* Hydra_Software_Devel/58 3/28/10 4:14p albertl
108	* SW7405-3979: Changed to assign filename pointer correctly.
109	*
110	* Hydra_Software_Devel/57 3/26/10 5:14p albertl
111	* SW7405-3979: Changed filename field from string to pointer and removed
112	* slow copy operation.
113	*
114	* Hydra_Software_Devel/56 2/26/10 2:14p erickson
115	* SW7325-655: BMEM_Heap_FreeCached should only flush user accessible
116	* memory. the scrap and bookkeeping is never access via cached memory.
117	*
118	* Hydra_Software_Devel/55 2/26/10 1:44p erickson
119	* SW7325-655: fix compilation error
120	*
121	* Hydra_Software_Devel/54 2/26/10 1:40p albertl
122	* SW7325-655: Added BMEM_Heap_FreeCached.
123	*
124	* Hydra_Software_Devel/53 2/12/10 10:38a erickson
125	* SW7405-3877: make BMEM_AllocAligned BDBG_MSG more useful to users
126	*
127	* Hydra_Software_Devel/52 5/26/09 4:17p albertl
128	* PR55389: Replaced uintptr_t with uint32_t.
129	*
130	* Hydra_Software_Devel/51 5/11/09 2:18p pntruong
131	* PR53840: [Core2.1/USB] USB Connect (Phase1) support in HPK driver for
132	* OTV Core2 v2.1.
133	*
134	* Hydra_Software_Devel/50 3/23/09 7:38p albertl
135	* PR41512: Fixed build warnings.
136	*
137	* Hydra_Software_Devel/49 3/23/09 6:37p albertl
138	* PR41512: Optimized guard band checking.
139	*
140	* Hydra_Software_Devel/48 2/25/09 4:48p erickson
141	* PR52471: added const keyword to global data
142	*
143	* Hydra_Software_Devel/47 12/3/08 5:16p albertl
144	* PR48035: Added ulTotalFree and ulTotalAllocated to BMEM_HeapInfo.
145	*
146	* Hydra_Software_Devel/46 11/3/08 4:58p albertl
147	* PR48488: Changed default alignment to BMEM_HEAP_ALIGNMENT.
148	*
149	* Hydra_Software_Devel/45 10/24/08 5:45p albertl
150	* PR48199, PR48046: Removed BMEM_SetCache entirely as it is obsolete.
151	*
152	* Hydra_Software_Devel/45 10/24/08 5:43p albertl
153	* PR48199, PR48046: Removed BMEM_SetCache entirely as it is obsolete.
154	*
155	* Hydra_Software_Devel/44 10/24/08 4:40p albertl
156	* PR48199: Fixed coverity error with unreachable BDBG_ASSERT.
157	*
158	* Hydra_Software_Devel/43 7/28/08 4:23p tdo
159	* PR45187: Fix compiling error for BMEM_SAFETY_CONFIG=BMEM_CONFIG_SAFEST
160	* flag
161	*
162	* Hydra_Software_Devel/42 4/8/08 7:19p albertl
163	* PR40246: Changed to assert if pheap parameters are null.
164	*
165	* Hydra_Software_Devel/41 6/8/07 5:19p darnstein
166	* PR31999: Add a test for a certain failure in BMEM_Heap_Create().
167	*
168	* Hydra_Software_Devel/40 5/14/07 1:19p albertl
169	* PR30621: Fixed heaps being added to allocation list but not being
170	* removed when freed in some safety configurations.
171	*
172	* Hydra_Software_Devel/39 3/19/07 2:26p erickson
173	* PR28682: fix compilation error because of macro change, also removed
174	* TRACE-like MSG's
175	*
176	* Hydra_Software_Devel/38 2/1/07 3:45p jgarrett
177	* PR 20139: Removing release-mode warning
178	*
179	* Hydra_Software_Devel/37 1/24/07 8:05p albertl
180	* PR27214: Fixed compile worning with BMEM_P_PrintBlock.
181	*
182	* Hydra_Software_Devel/36 1/16/07 2:41p erickson
183	* PR25037: improve BMEM validate and debug messages
184	*
185	* Hydra_Software_Devel/35 10/12/06 6:54p albertl
186	* PR20247: Fixed all heap safety config field checks to use new
187	* pSafetyConfigInfo structure.
188	*
189	* Hydra_Software_Devel/34 6/21/06 3:10p albertl
190	* PR20247: Moved safety config table to bmem.c BMEM_P_Heap now uses a
191	* BMEM_P_SafetyConfigInfo pointer to track safety configuration settings
192	* instead of tracking each configuration separately.
193	*
194	* Hydra_Software_Devel/33 6/20/06 6:05p albertl
195	* PR20247: hMem field in heap updated even when NULL.
196	*
197	* Hydra_Software_Devel/32 6/16/06 3:21p albertl
198	* PR20247, PR20276, PR20354: Added the ability to control debug
199	* configuration at runtime. Added address and offset checking to
200	* conversion functions. BMEM_SetCache can now only be called before
201	* heaps are allocated from. Added BMEM_Heap functions.
202	*
203	* Hydra_Software_Devel/31 2/8/06 7:29p hongtaoz
204	* PR19082: BMEM_Alloc returns NULL pointer if size is zero;
205	*
206	* Hydra_Software_Devel/30 10/7/05 3:53p jasonh
207	* PR 17374: Allowed GetHeapInfo to return original creation parameters.
208	*
209	* Hydra_Software_Devel/29 8/10/05 11:54a hongtaoz
210	* PR13076: BMEM_SetCache returns error if NULL callbacks are provided;
211	*
212	* Hydra_Software_Devel/28 8/1/05 5:40p albertl
213	* PR16375: BMEM_Heap_Validate now returns the errorcode corresponding to
214	* the first error encountered..
215	*
216	* Hydra_Software_Devel/27 4/28/05 5:07p jasonh
217	* PR 15059: Fixed problems associated with freeing blocks (rare corner
218	* case).
219	*
220	* Hydra_Software_Devel/26 3/10/05 5:04p albertl
221	* PR13677: Both local and system bookkeeping made available at heap
222	* creation though functions BMEM_CreateHeapSystem and
223	* BMEM_CreateHeapLocal.
224	*
225	* Hydra_Software_Devel/25 1/21/05 4:56p albertl
226	* PR13717: Replaced BMEM_DBG_ENTER with BDBG_ENTER. Moved printouts to
227	* BDBG_MSG, fixed pvHeap.
228	*
229	* Hydra_Software_Devel/24 12/14/04 4:31p marcusk
230	* PR13562: Updated to output the heap size, allocated size, and free size
231	* when a memory allocation fails.
232	*
233	* Hydra_Software_Devel/23 11/3/04 10:45a pntruong
234	* PR13076: Call the correct flush for _isr function.
235	*
236	* Hydra_Software_Devel/22 11/2/04 5:27p pntruong
237	* PR13076: Fixed re-entry problem.
238	*
239	* Hydra_Software_Devel/21 11/2/04 10:32a hongtaoz
240	* PR13076: added cached memory support;
241	*
242	* Hydra_Software_Devel/20 5/27/04 7:40p hongtaoz
243	* PR10059: fixed a minor merge sort bug;
244	*
245	* Hydra_Software_Devel/19 5/27/04 2:17p hongtaoz
246	* PR10059: fixed free clear size error;
247	*
248	* Hydra_Software_Devel/18 5/26/04 7:01p hongtaoz
249	* PR10059: sorted freed heap in size ascending order to avoid memory
250	* fragamentation;
251	*
252	* Hydra_Software_Devel/17 4/1/04 12:48p vsilyaev
253	* PR 10201: Added memory monitor
254	*
255	* Hydra_Software_Devel/16 2/25/04 2:52p hongtaoz
256	* PR9855: removed redundent functions BMEM_Report and BMEM_ReportVerbose;
257	* being aware of that BMEM_Dbg_DumpBlock and BMEM_Dbg_DumpHeap suffice
258	* heap debug requirement; avoid using floating point in BMEM_Dbg_Map;
259	*
260	* Hydra_Software_Devel/15 12/31/03 12:02p jasonh
261	* PR 8940: Changed return type of destroyheap to void. Removed use of
262	* DEBUG macro and printf.
263	*
264	* Hydra_Software_Devel/14 11/11/03 11:17a jasonh
265	* PR 8589: Fixed offset to address conversion.
266	*
267	* Hydra_Software_Devel/13 10/31/03 9:52a jasonh
268	* Removed side-effects of assert statement.
269	*
270	* Hydra_Software_Devel/12 9/15/03 5:18p jasonh
271	* Fixed semaphore assert check.
272	*
273	* Hydra_Software_Devel/11 9/15/03 5:02p jasonh
274	* Moved destroy heap to local and system specific files. Added asserts
275	* around semaphore access routines. Fixed get free block to allow block
276	* of exact size to be allocated. Added implementation of conversion
277	* functions.
278	*
279	* Hydra_Software_Devel/10 9/5/03 3:40p jasonh
280	* Fixed guardband check.
281	*
282	* Hydra_Software_Devel/9 9/5/03 2:03p jasonh
283	* Added documentation. Re-named Check to ValidateHeap. Removed
284	* implementation of Alloc and AllocAligned (they are now macros). Added
285	* stubs for convert and report functions.
286	*
287	* Hydra_Software_Devel/8 9/4/03 7:15p jasonh
288	* Added basic implementations of alloc and allocaligned routines.
289	*
290	* Hydra_Software_Devel/7 9/4/03 6:44p jasonh
291	* Added debug module tag.
292	*
293	* Hydra_Software_Devel/6 9/2/03 1:53p vadim
294	* Some magnum updates. DestroyHeap is currently a stub.
295	*
296	* Hydra_Software_Devel/2 3/20/03 3:51p erickson
297	* renamed all MEM_ to BMEM_
298	*
299	* Hydra_Software_Devel/1 3/20/03 3:24p erickson
300	* initial bmem work, taken from SetTop/memorylib
301	*
302	* SanJose_DVTSW_Devel\9 4/16/02 5:49p jasonh
303	* Warning police.
304	*
305	* SanJose_DVTSW_Devel\8 4/15/02 3:34p poz
306	* Updated public functions to new names.
307	*
308	* SanJose_DVTSW_Devel\7 4/15/02 3:13p ngibbs
309	* Fixed semaphore-related oops introduced during merge.
310	*
311	* SanJose_DVTSW_Devel\6 4/15/02 2:37p jasonh
312	* Whoops. A number of minor compile errors fixed.
313	*
314	* SanJose_DVTSW_Devel\5 4/15/02 2:28p poz
315	* Modifications to allow bookkeeping to exist non-local to the data.
316	* Tweaks to reentrancy stuff.
317	* Updated comments, copyright, and keywords in header.
318	*
319	***************************************************************************/
320
321	#include "bstd.h"
322	#include "bkni.h"
323	#include "berr_ids.h"
324	#include "bmem.h"
325	#include "bmem_config.h"
326	#include "bmem_priv.h"
327	#include "bmem_debug.h"
328
329	BDBG_MODULE(BMEM);
330
331	BDBG_OBJECT_ID(BMEM);
332	BDBG_OBJECT_ID(BMEM_Heap);
333
334	#define BMEM_P_GUARD_DWORD ((uint32_t)(BMEM_GUARD_BYTE << 24 \| BMEM_GUARD_BYTE << 16 \| BMEM_GUARD_BYTE << 8 \| BMEM_GUARD_BYTE))
335
336	static void BMEM_P_AddUsed(BMEM_Heap_Handle pheap, BMEM_P_BlockInfo *pbi);
337	static void BMEM_P_AddFree(BMEM_Heap_Handle pheap, BMEM_P_BlockInfo *pbi);
338	static BMEM_P_BlockInfo *BMEM_P_GetFreeBlock(BMEM_Heap_Handle pheap,
339	size_t ulSize, uint32_t ulAlignMask);
340
341	/* Safety Mode configuration table */
342	const BMEM_P_SafetyConfigInfo BMEM_P_SafetyConfigTbl[] =
343	{ /* eSafetyConfig, bTrackAllocations, bFreeClear, bFreeCarefully, iGuardSize, bCheckDisorder, bCheckGuardOnFree bCheckAllGuards, bTrackFileAndLine */
344	{BMEM_CONFIG_FASTEST, BMEM_TRACK_ALLOCATIONS_FASTEST, BMEM_FREE_CLEAR_FASTEST, BMEM_FREE_CAREFULLY_FASTEST, BMEM_GUARD_SIZE_FASTEST, BMEM_CHECK_DISORDER_FASTEST, BMEM_CHECK_GUARD_ON_FREE_FASTEST, BMEM_CHECK_ALL_GUARDS_FASTEST, BMEM_TRACK_FILE_AND_LINE_FASTEST},
345	{BMEM_CONFIG_NORMAL, BMEM_TRACK_ALLOCATIONS_NORMAL, BMEM_FREE_CLEAR_NORMAL, BMEM_FREE_CAREFULLY_NORMAL, BMEM_GUARD_SIZE_NORMAL, BMEM_CHECK_DISORDER_NORMAL, BMEM_CHECK_GUARD_ON_FREE_NORMAL, BMEM_CHECK_ALL_GUARDS_NORMAL, BMEM_TRACK_FILE_AND_LINE_NORMAL},
346	{BMEM_CONFIG_TRACK, BMEM_TRACK_ALLOCATIONS_TRACK, BMEM_FREE_CLEAR_TRACK, BMEM_FREE_CAREFULLY_TRACK, BMEM_GUARD_SIZE_TRACK, BMEM_CHECK_DISORDER_TRACK, BMEM_CHECK_GUARD_ON_FREE_TRACK, BMEM_CHECK_ALL_GUARDS_TRACK, BMEM_TRACK_FILE_AND_LINE_TRACK},
347	{BMEM_CONFIG_SAFE, BMEM_TRACK_ALLOCATIONS_SAFE, BMEM_FREE_CLEAR_SAFE, BMEM_FREE_CAREFULLY_SAFE, BMEM_GUARD_SIZE_SAFE, BMEM_CHECK_DISORDER_SAFE, BMEM_CHECK_GUARD_ON_FREE_SAFE, BMEM_CHECK_ALL_GUARDS_SAFE, BMEM_TRACK_FILE_AND_LINE_SAFE},
348	{BMEM_CONFIG_SAFEST, BMEM_TRACK_ALLOCATIONS_SAFEST, BMEM_FREE_CLEAR_SAFEST, BMEM_FREE_CAREFULLY_SAFEST, BMEM_GUARD_SIZE_SAFEST, BMEM_CHECK_DISORDER_SAFEST, BMEM_CHECK_GUARD_ON_FREE_SAFEST, BMEM_CHECK_ALL_GUARDS_SAFEST, BMEM_TRACK_FILE_AND_LINE_SAFEST}
349	};
350
351	const uint32_t BMEM_P_SafetyTableSize = (sizeof(BMEM_P_SafetyConfigTbl) / sizeof(BMEM_P_SafetyConfigInfo));
352
353	static const BMEM_Heap_Settings s_stDefaultHeapSettings =
354	{
355	BMEM_HEAP_ALIGNMENT, /* uiAlignment */
356	BMEM_SAFETY_CONFIG, /* eSafetyConfig */
357	BMEM_BOOKKEEPING_CONFIG, /* eBookKeeping */
358	0, /* pCachedAddress */
359	NULL, /* flush */
360	NULL /* flush_isr */
361	};
362
363	const char s_achFilenameFreeString[] = "(free)";
364
365	/***************************************************************************/
366	BERR_Code BMEM_GetDefaultSettings
367	(
368	BMEM_Settings *pDefSettings
369	)
370	{
371	*pDefSettings = NULL;
372	return BERR_SUCCESS;
373	}
374
375	/***************************************************************************/
376	BERR_Code BMEM_Open
377	(
378	BMEM_ModuleHandle *phMem,
379	const BMEM_Settings *pDefSettings
380	)
381	{
382	BMEM_ModuleHandle hMem;
383
384	BSTD_UNUSED(pDefSettings);
385
386	if (!phMem)
387	{
388	return BERR_INVALID_PARAMETER;
389	}
390
391	hMem = (BMEM_ModuleHandle) BKNI_Malloc( sizeof( BMEM_P_Mem ) );
392	if (!hMem) {
393	return BERR_TRACE(BERR_OUT_OF_SYSTEM_MEMORY);
394	}
395	BDBG_OBJECT_SET(hMem, BMEM);
396	BLST_S_INIT(&(hMem->HeapList));
397
398	*phMem = hMem;
399
400	return BERR_SUCCESS;
401	}
402
403	/***************************************************************************/
404	void BMEM_Close
405	(
406	BMEM_ModuleHandle hMem
407	)
408	{
409	BMEM_P_Heap *pHeap = NULL;
410
411	BDBG_OBJECT_ASSERT(hMem, BMEM);
412
413	for(pHeap = BLST_S_FIRST(&(hMem->HeapList)); pHeap ; pHeap = BLST_S_FIRST(&(hMem->HeapList)))
414	{
415	BMEM_Heap_Destroy(pHeap);
416	}
417	BDBG_OBJECT_DESTROY(hMem, BMEM);
418	BKNI_Free( hMem );
419	}
420
421	/***************************************************************************/
422	void *BMEM_P_Heap_TagAllocAligned(
423	BMEM_Heap_Handle pheap, /* Heap to allocate from */
424	size_t ulSize, /* size in bytes of block to allocate */
425	unsigned int ucAlignBits, /* alignment for the block */
426	unsigned int Boundary, /* boundry restricting allocated value */
427	const char* pchFilename, /* source filename where block is allocated from */
428	int iLine ) /* line number in file where allocation occurs */
429	{
430	BERR_Code err;
431	void *pvRet = NULL;
432	BMEM_P_BlockInfo *pbiNew = NULL;
433	BMEM_P_BlockInfo *pbi;
434
435	uint32_t addrBase;
436	uint32_t addrFinal;
437
438	uint32_t addrFront;
439	uint32_t addrFrontOffset = 0;
440	size_t ulWasteFront;
441
442	uint32_t addrMiddle;
443
444	uint32_t addrBack;
445	uint32_t addrBackOffset = 0;
446	size_t ulWasteBack;
447
448	size_t ulOrigSize;
449
450	uint32_t ulAlignMask;
451
452	uint32_t ulBookKeepingSize;
453	uint32_t ulFrontBookKeepingSize;
454	uint32_t ulMinBlockSize;
455
456	/* TODO: Implement Boundary */
457	BSTD_UNUSED(Boundary);
458	#if !(BMEM_TRACK_FILE_AND_LINE)
459	BSTD_UNUSED(pchFilename);
460	BSTD_UNUSED(iLine);
461	#endif
462
463	BDBG_OBJECT_ASSERT(pheap, BMEM_Heap);
464	BDBG_ENTER(BMEM_P_Heap_TagAllocAligned);
465
466	ulBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
467	BMEM_BOOKKEEPING_SIZE_LOCAL : BMEM_BOOKKEEPING_SIZE_SYSTEM;
468	ulFrontBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
469	BMEM_FRONT_BOOKKEEPING_SIZE_LOCAL : BMEM_FRONT_BOOKKEEPING_SIZE_SYSTEM;
470	ulMinBlockSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
471	BMEM_MIN_BLOCK_SIZE_LOCAL : BMEM_MIN_BLOCK_SIZE_SYSTEM;
472
473	#if 0
474	/* this MSG before the allocation is useful for internal debug */
475	BDBG_MSG(("BMEM_Heap_TagAlloc(%p (%p), %lu, %u, %s, %d)",
476	(pheap ? pheap->pvHeap : NULL), pheap, ulSize, (int)ucAlignBits, pchFilename, iLine));
477	#endif
478
479	if(ulSize == 0) return NULL;
480
481	ulAlignMask = ((uint32_t) 1 << ucAlignBits) - 1;
482	/* Force the heap's alignment at minimum */
483	ulAlignMask \|= pheap->ulAlignMask;
484
485	/* The size of the block must be at the heap's alignment also */
486	ulSize = (ulSize+pheap->ulAlignMask) & ~pheap->ulAlignMask;
487
488	#if BMEM_CHECK_ALL_GUARDS
489	if(pheap->pSafetyConfigInfo->bCheckAllGuards)
490	{
491	BMEM_Heap_Validate(pheap);
492	}
493	#endif
494
495	/* get semaphore */
496	err = BMEM_P_GET_SEMAPHORE(pheap);
497	BDBG_ASSERT(err == BERR_SUCCESS);
498
499	/* get a free block that can contain the requested size */
500	if((pbi = BMEM_P_GetFreeBlock(pheap, ulSize, ulAlignMask)) == NULL)
501	{
502	/* unable to find a free block of the needed size. */
503	BMEM_P_RELEASE_SEMAPHORE(pheap);
504	BDBG_WRN(("Unable to allocate requested memory of size %ld by %s:%d", ulSize, pchFilename, iLine));
505	BMEM_Dbg_DumpHeap(pheap);
506	goto done;
507	}
508
509	/*
510	* TODO: I get an itching feeling that this code can be combined with
511	* the code later on which determines what memory can be given back
512	* to the free heap. It seems like I'm doing the same calculation
513	* twice: once to figure out the theoretical waste, and once for the
514	* actual waste.
515	*
516	* Anyway, they are still separate since it makes logical sense to do
517	* things in this order (determine options, decide which one, do the
518	* actual allocation). I haven't had the time to optimize (which I
519	* believe means simplify, in this case) the code.
520	*
521	* One obvious method for simplification would be to always allocate
522	* from the front (or back) of the free block. I decided that
523	* maximizing heap usage (i.e. minimizing fragmentation) was a better
524	* choice for now.
525	*/
526
527	/* Free blocks never have scrap, so we don't need to worry about that */
528
529	/*
530	* There are two places to try to place the new allocation,
531	* at the front of the block and at the end.
532	*
533	* The wastage for each (due to alignment) will be calculated and
534	* the one with the minimum waste used.
535	*/
536
537	ulOrigSize = pbi->ulSize;
538	addrBase = BMEM_P_GetAddress(pheap, pbi);
539
540	/* First the front */
541	addrFront = addrBase + ulFrontBookKeepingSize;
542
543	/* Alignment should be calculated on physical address */
544	/* Push it forward to the next alignment */
545	if(BMEM_Heap_ConvertAddressToOffset(pheap, (void *)addrFront, &addrFrontOffset) != BERR_SUCCESS)
546	{
547	BDBG_ERR(("Invalid address being converted to offset."));
548	goto done;
549	}
550	addrFrontOffset = (addrFrontOffset + ulAlignMask) & ~ulAlignMask;
551	if(BMEM_Heap_ConvertOffsetToAddress(pheap, addrFrontOffset, (void *)&addrFront) != BERR_SUCCESS)
552	{
553	BDBG_ERR(("Invalid offset being converted to address."));
554	goto done;
555	}
556
557	/* Calculate the waste */
558	ulWasteFront = addrFront-ulFrontBookKeepingSize-addrBase;
559	if((ulOrigSize-ulSize-ulWasteFront-BMEM_BACK_BOOKKEEPING_SIZE)
560	< ulMinBlockSize)
561	{
562	ulWasteFront = ulOrigSize-ulSize-ulBookKeepingSize;
563	}
564
565	/* Now the back */
566	addrBack = addrBase + ulOrigSize - ulSize - BMEM_BACK_BOOKKEEPING_SIZE;
567
568	/* Calculate the waste */
569	/* Alignment should be calculated on physical address */
570	if(BMEM_Heap_ConvertAddressToOffset(pheap, (void *)addrBack, &addrBackOffset) != BERR_SUCCESS)
571	{
572	BDBG_ERR(("Invalid address being converted to offset."));
573	goto done;
574	}
575	ulWasteBack = addrBackOffset & ulAlignMask;
576	/* Pull it back to the next alignment */
577	addrBackOffset = addrBackOffset & ~ulAlignMask;
578	if(BMEM_Heap_ConvertOffsetToAddress(pheap, addrBackOffset, (void *)&addrBack) != BERR_SUCCESS)
579	{
580	BDBG_ERR(("Invalid offset being converted to address."));
581	goto done;
582	}
583
584	if((ulOrigSize-ulSize-ulWasteBack-ulBookKeepingSize)
585	< ulMinBlockSize)
586	{
587	ulWasteBack = ulOrigSize-ulSize-ulBookKeepingSize;
588	}
589
590	/*
591	* Decide if we're taking the front or the back.
592	*
593	* This addrFinal is the address which will be returned by the
594	* function. The bookeeping info is a bit in front of it.
595	*
596	*/
597	addrFinal = (ulWasteFront <= ulWasteBack ? addrFront : addrBack);
598
599	/*
600	* OK! We now have the optimal place to put the allocation
601	* within the block. Split the block up and do the allocation.
602	*/
603
604	/*
605	* Of all those calculations above, the only things which are used
606	* below this point are addrFinal, addrBase, and ulOrigSize. (The
607	* other variables are wiped out and reused.)
608	*
609	* What this means is that if you come up with some fancy way to figure
610	* out addrFinal, you can do that instead of the above.
611	*/
612
613	/*
614	* There are theoretically three blocks which can be made here,
615	* a front free block, the allocated block, and a back free block.
616	* If any block is too small, then it is added to the allocation.
617	* This reduces fragmentation of tiny bits of memory.
618	*
619	*
620	* [addrBase.......addrFinal.......addrMiddle.....addrBack]
621	*
622	* B^-------------^G
623	* ulSize
624	* ^-------------^ ^----------------------^
625	* ulWasteFront ulWasteBack
626	*
627	* B-------------GB---------------GB----------------------G
628	* pbiFreeFront pbiNew pbiFreeBack
629	*
630	*
631	* B = BMEM_P_BlockInfo (has guard bytes in it)
632	* G = guard bytes
633	*
634	*/
635
636	addrFinal -= ulFrontBookKeepingSize;
637	addrMiddle = addrFinal + ulSize + ulBookKeepingSize;
638	addrBack = addrBase + ulOrigSize;
639
640	pbiNew = BMEM_P_GetBlockInfo(pheap, addrFinal);
641	pbiNew->ulFrontScrap = 0;
642	pbiNew->ulBackScrap = 0;
643	pbiNew->ulSize = ulSize + ulBookKeepingSize;
644	pbiNew->pnext = NULL;
645	pbiNew->pprev = NULL;
646
647	#if BMEM_TRACK_FILE_AND_LINE
648	if(pheap->pSafetyConfigInfo->bTrackFileAndLine)
649	{
650	pbiNew->ulLine = iLine;
651	pbiNew->pchFilename = pchFilename;
652	}
653	#endif
654
655	/* Determine if slack at the front should be made into a free block. */
656	ulWasteFront = addrFinal - addrBase;
657	if(ulWasteFront < ulMinBlockSize)
658	{
659	/* Not enough to make a block, keep it as scrap */
660	pbiNew->ulSize += ulWasteFront;
661	pbiNew->ulFrontScrap = ulWasteFront;
662
663	/* We can't reuse the old BlockInfo, so drop it. */
664	if(addrBase!=addrFinal)
665	{
666	BMEM_P_DropBlockInfo(pheap, pbi);
667	}
668	}
669	else
670	{
671	/* Make a free node for this left over area. */
672	/* This is the same base address as the original free block */
673	pbi->ulSize = ulWasteFront;
674	pbi->ulFrontScrap = 0;
675	pbi->ulBackScrap = 0;
676
677	/* Connect up the free node and update the guard band */
678	BMEM_P_AddFree(pheap, pbi);
679	}
680
681	/* Determine if slack at the back should be made into a free block. */
682	ulWasteBack = addrBack - addrMiddle;
683	if(ulWasteBack < ulMinBlockSize)
684	{
685	/* This leftover is too small to turn into a free block */
686	pbiNew->ulSize += ulWasteBack;
687	pbiNew->ulBackScrap = ulWasteBack;
688	}
689	else
690	{
691	/* Make a new free node for this leftover area. */
692	BMEM_P_BlockInfo *pbiFreeBack = BMEM_P_GetBlockInfo(pheap, addrMiddle);
693
694	pbiFreeBack->ulSize = ulWasteBack;
695	pbiFreeBack->ulFrontScrap = 0;
696	pbiFreeBack->ulBackScrap = 0;
697
698	/* Connect up the free node and update the guard band */
699	BMEM_P_AddFree(pheap, pbiFreeBack);
700	}
701
702	/*
703	* OK! We've freed what we could back to the free list and updated
704	* our size.
705	*
706	* Finalize the data structure and connect it up to the
707	* alloc'ed list.
708	*/
709	pheap->ulNumAllocated++;
710	pheap->ulTotalAllocated += pbiNew->ulSize;
711	if (pheap->ulTotalAllocated > pheap->ulHighWatermark)
712	{
713	pheap->ulHighWatermark = pheap->ulTotalAllocated;
714	}
715
716	BMEM_P_AddUsed(pheap, pbiNew);
717
718	pvRet = (void *)(addrFinal+ulFrontBookKeepingSize);
719
720	if (pheap->monitor) {
721	pheap->monitor->alloc(pheap->monitor->cnxt, pheap->ulOffset +
722	((uint32_t)pvRet - (uint32_t)pheap->pvHeap), ulSize, pchFilename, iLine);
723	}
724
725	pheap->bCacheLocked = true;
726
727	BDBG_MSG(("BMEM_AllocAligned(heap %p), offset=0x%x, ptr=%p, size=%lu, align=%u, code=%s:%d)",
728	pheap,
729	pheap->ulOffset + ((uint32_t)pvRet - (uint32_t)pheap->pvHeap),
730	pvRet, ulSize, (int)ucAlignBits, pchFilename, iLine));
731
732	BMEM_P_RELEASE_SEMAPHORE(pheap);
733
734	done:
735	BDBG_LEAVE(BMEM_P_Heap_TagAllocAligned);
736	return pvRet;
737	}
738
739	/{private}****************************************************************
740	Summary:
741	Finds a free block of a certain size.
742
743	Description:
744	This function searches through the free block list looking for a block
745	which can contain an object of the given size and alignment. If one is
746	found, it is removed from the free list and returned.
747
748	Returns:
749	A pointer to the BlockInfo for a block which satisfies the size and
750	alignment constraints, or NULL if no such block exists.
751	****************************************************************************/
752	BMEM_P_BlockInfo *BMEM_P_GetFreeBlock
753	(
754	BMEM_Heap_Handle pheap,
755	size_t ulSize,
756	uint32_t ulAlignMask
757	)
758	{
759	BMEM_P_BlockInfo *pbi;
760	BMEM_P_BlockInfo *pbiLast = NULL;
761
762	uint32_t ulBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
763	BMEM_BOOKKEEPING_SIZE_LOCAL : BMEM_BOOKKEEPING_SIZE_SYSTEM;
764	uint32_t ulFrontBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
765	BMEM_FRONT_BOOKKEEPING_SIZE_LOCAL : BMEM_FRONT_BOOKKEEPING_SIZE_SYSTEM;
766
767	for(pbi = pheap->pFreeTop; pbi != NULL; pbi = pbi->pnext)
768	{
769	if(pbi->ulSize >= (ulSize+ulBookKeepingSize))
770	{
771	uint32_t addrBaseOffset = 0;
772	uint32_t addrFront = 0;
773	uint32_t addrFrontOffset = 0;
774	uint32_t addrFrontOffsetAligned = 0;
775
776	/* Free blocks never have scrap */
777
778	/* Determine where aligned allocation would start */
779	addrFront = BMEM_P_GetAddress( pheap, pbi ) + ulFrontBookKeepingSize;
780
781	/* Alignment should be calculated on physical offset of starting address */
782	if(BMEM_Heap_ConvertAddressToOffset(pheap, (void *)addrFront, &addrFrontOffset) != BERR_SUCCESS)
783	{
784	BDBG_ERR(("Invalid address being converted to offset."));
785	break;
786	}
787	addrBaseOffset = addrFrontOffset - ulFrontBookKeepingSize;
788	addrFrontOffsetAligned = (addrFrontOffset + ulAlignMask) & ~ulAlignMask;
789
790	/* Make sure allocation with requested size starting on aligned address still fits in block */
791	if((addrFrontOffsetAligned + ulSize + BMEM_BACK_BOOKKEEPING_SIZE) <= (addrBaseOffset + pbi->ulSize))
792	{
793	/* This block can fit the request */
794	/* Remove this free node from the list to be returned */
795	if(pbiLast == NULL)
796	{
797	pheap->pFreeTop = pbi->pnext;
798	if(pheap->pFreeTop)
799	{
800	pheap->pFreeTop->pprev = NULL;
801	}
802	}
803	else
804	{
805	pbiLast->pnext = pbi->pnext;
806	if(pbi->pnext)
807	{
808	pbi->pnext->pprev = pbiLast;
809	}
810	}
811	goto done;
812	}
813	}
814
815	pbiLast = pbi;
816	}
817
818	pbi = NULL;
819	done:
820	return pbi;
821	}
822
823	#if BMEM_TRACK_FILE_AND_LINE
824	/* This prints file/line information if available */
825	static void BMEM_P_PrintBlock(BMEM_Heap_Handle pheap, BMEM_P_BlockInfo *pbi)
826	{
827	if (pheap->pSafetyConfigInfo->bTrackFileAndLine) {
828	/* make sure the filename is printable. at this point, we're already corrupt, so
829	why trust the filename? */
830	char temp[BMEM_FILENAME_LENGTH];
831	int i;
832
833	BKNI_Memcpy(temp, pbi->pchFilename, BMEM_FILENAME_LENGTH);
834	for (i=0;i<BMEM_FILENAME_LENGTH;i++) {
835	if (!temp[i]) break;
836	if (temp[i] < 32) temp[i]='.';
837	}
838	if (i == BMEM_FILENAME_LENGTH) {
839	temp[BMEM_FILENAME_LENGTH-1] = 0;
840	}
841
842	/* NOTE: %.128s is not portable. we have to use %s. */
843	BDBG_ERR((" addr=%p(pbi=%p), size=%u, allocated at: %s:%d",
844	BMEM_P_GetAddress( pheap, pbi ), pbi, pbi->ulSize, temp, pbi->ulLine));
845	}
846	}
847	#endif
848
849	/***************************************************************************/
850	BERR_Code BMEM_Heap_Free(BMEM_Heap_Handle pheap, void *pv)
851	{
852	BERR_Code err;
853	BMEM_P_BlockInfo *pbi;
854
855	uint32_t ulFrontBookKeepingSize;
856
857	BDBG_ENTER(BMEM_Free);
858	BDBG_OBJECT_ASSERT(pheap, BMEM_Heap);
859	ulFrontBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
860	BMEM_FRONT_BOOKKEEPING_SIZE_LOCAL : BMEM_FRONT_BOOKKEEPING_SIZE_SYSTEM;
861	BDBG_MSG(("BMEM_Free(%p (%p), %p)", (pheap ? pheap->pvHeap : NULL), pheap, pv));
862
863	if(pv == NULL)
864	{
865	goto done;
866	}
867
868	#if BMEM_CHECK_ALL_GUARDS
869	if(pheap->pSafetyConfigInfo->bCheckAllGuards)
870	{
871	BMEM_Heap_Validate(pheap);
872	}
873	#endif
874
875	/* acquire semaphore */
876	err = BMEM_P_GET_SEMAPHORE(pheap);
877	BDBG_ASSERT(err == BERR_SUCCESS);
878
879	/* get information about requested block */
880	pbi = BMEM_P_GetBlockInfo( pheap,
881	(uint32_t) pv - ulFrontBookKeepingSize );
882
883	#if BMEM_TRACK_ALLOCATIONS
884	if(pheap->pSafetyConfigInfo->bTrackAllocations)
885	{
886	#if BMEM_FREE_CAREFULLY
887	if(pheap->pSafetyConfigInfo->bFreeCarefully)
888	{
889	BMEM_P_BlockInfo *pbiNext;
890	BMEM_P_BlockInfo *pbiLast = NULL;
891
892	for(pbiNext = pheap->pAllocTop;
893	pbiNext != NULL;
894	pbiNext = pbiNext->pnext)
895	{
896	if(pbiNext == pbi)
897	{
898	if(pbiLast==NULL)
899	{
900	pheap->pAllocTop = pbi->pnext;
901	if(pheap->pAllocTop)
902	{
903	pheap->pAllocTop->pprev = NULL;
904	}
905	}
906	else
907	{
908	pbiLast->pnext = pbi->pnext;
909	if(pbi->pnext)
910	{
911	pbi->pnext->pprev = pbiLast;
912	}
913	}
914	break;
915	}
916
917	pbiLast = pbiNext;
918	}
919
920	if(pbiNext == NULL)
921	{
922	BDBG_ERR(("Unable to find block in allocated list!"));
923	#if BMEM_TRACK_FILE_AND_LINE
924	if(pheap->pSafetyConfigInfo->bTrackFileAndLine)
925	{
926	BMEM_P_PrintBlock(pheap, pbi);
927	}
928	#endif
929	pheap->ulNumErrors++;
930	goto done_release_sem;
931	}
932
933	}
934	else
935	#endif /* BMEM_FREE_CAREFULLY */
936	{
937	if(pbi->pprev)
938	{
939	pbi->pprev->pnext = pbi->pnext;
940
941	if (pbi->pnext)
942	{
943	pbi->pnext->pprev = pbi->pprev;
944	}
945	}
946	else
947	{
948	pheap->pAllocTop = pbi->pnext;
949	if(pheap->pAllocTop)
950	{
951	pheap->pAllocTop->pprev = NULL;
952	}
953	}
954	}
955	}
956	#endif /* BMEM_TRACK_ALLOCATIONS */
957
958	#if BMEM_CHECK_GUARD_ON_FREE
959	if(pheap->pSafetyConfigInfo->bCheckGuardOnFree)
960	{
961	BMEM_P_CheckGuard(pheap, pbi);
962	}
963	#endif
964
965	if(pbi->ulFrontScrap != 0)
966	{
967	/* Remove the scrap area */
968	size_t ulSize = pbi->ulSize;
969	uint32_t addr = BMEM_P_GetAddress( pheap, pbi ) - pbi->ulFrontScrap;
970
971	BMEM_P_DropBlockInfo(pheap, pbi);
972
973	pbi = BMEM_P_GetBlockInfo(pheap, addr);
974	pbi->ulSize = ulSize;
975	pbi->ulFrontScrap = 0;
976	}
977	pbi->ulBackScrap = 0;
978
979	#if BMEM_FREE_CLEAR
980	if(pheap->pSafetyConfigInfo->bFreeClear)
981	{
982	uint32_t ulBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
983	BMEM_BOOKKEEPING_SIZE_LOCAL : BMEM_BOOKKEEPING_SIZE_SYSTEM;
984	uint8_t pc = ((uint8_t )BMEM_P_GetAddress(pheap, pbi))+
985	ulFrontBookKeepingSize;
986	BKNI_Memset((void*)pc, BMEM_CLEAR_BYTE,
987	pbi->ulSize - ulBookKeepingSize - pbi->ulFrontScrap - pbi->ulBackScrap);
988	}
989	#endif /* BMEM_FREE_CLEAR */
990
991	pheap->ulNumAllocated--;
992	pheap->ulTotalAllocated -= pbi->ulSize;
993
994	BMEM_P_AddFree(pheap, pbi);
995	if (pheap->monitor) {
996	pheap->monitor->free(pheap->monitor->cnxt, pheap->ulOffset +
997	((uint32_t)pv - (uint32_t)pheap->pvHeap));
998	}
999
1000	#if BMEM_FREE_CAREFULLY
1001	done_release_sem:
1002	#endif
1003	BMEM_P_RELEASE_SEMAPHORE(pheap);
1004
1005	done:
1006	BDBG_LEAVE(BMEM_Free);
1007	return BERR_SUCCESS;
1008	}
1009
1010	/***************************************************************************/
1011	BERR_Code BMEM_Heap_FreeCached(BMEM_Heap_Handle pheap, void *pvCachedAddress)
1012	{
1013	BERR_Code err = BERR_SUCCESS;
1014	void *pv = NULL;
1015
1016	BDBG_OBJECT_ASSERT(pheap, BMEM_Heap);
1017
1018	err = BMEM_P_GET_SEMAPHORE(pheap);
1019	BDBG_ASSERT(err == BERR_SUCCESS);
1020
1021	/* verify it's a cached address we know about. */
1022	if (pvCachedAddress &&
1023	pheap->pvCache &&
1024	pheap->pfFlushCb_isr &&
1025	pvCachedAddress >= pheap->pvCache &&
1026	(uint8_t)pvCachedAddress < (uint8_t)pheap->pvCache+pheap->zSize)
1027	{
1028	BMEM_P_BlockInfo *pbi;
1029	uint32_t ulFrontBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
1030	BMEM_FRONT_BOOKKEEPING_SIZE_LOCAL : BMEM_FRONT_BOOKKEEPING_SIZE_SYSTEM;
1031	unsigned userSize; /* the memory that the user sees. only flush this. */
1032
1033	/* convert from cached to uncached before lookup & free */
1034	pv = (void)((uint8_t)pvCachedAddress - (uint8_t)pheap->pvCache + (uint8_t)pheap->pvHeap);
1035
1036	/* get information about requested block */
1037	pbi = BMEM_P_GetBlockInfo( pheap, (uint32_t) pv - ulFrontBookKeepingSize );
1038
1039	userSize = pbi->ulSize - pbi->ulFrontScrap - pbi->ulBackScrap - ulFrontBookKeepingSize - BMEM_BACK_BOOKKEEPING_SIZE;
1040	BDBG_ASSERT(userSize <= pbi->ulSize);
1041
1042	BDBG_MSG(("BMEM_Heap_FreeCached(%p) flushing %p %d", pheap, pvCachedAddress, userSize));
1043	pheap->pfFlushCb_isr(pvCachedAddress, userSize);
1044	}
1045	else {
1046	/* this isn't a cached addr we know about. caller should fix the code. */
1047	err = BERR_TRACE(BERR_INVALID_PARAMETER);
1048	}
1049
1050	BMEM_P_RELEASE_SEMAPHORE(pheap);
1051
1052	if (pv) {
1053	/* here's the uncached free */
1054	BMEM_Heap_Free(pheap, pv);
1055	}
1056
1057	return err;
1058	}
1059
1060	/{private}****************************************************************
1061	Summary:
1062	Adds a block to the free list. Note the free list is always kept as size
1063	ascending order.
1064
1065	Description:
1066	This function takes the given BlockInfo and adds it to the list of free
1067	blocks available for future allocations. When it does this, it performs a
1068	heap compaction in order to maximize the size of free blocks; it also sorts
1069	the free list according to the size ascending order to prevent memory
1070	fragmentation.
1071
1072	Returns:
1073	void
1074	****************************************************************************/
1075	static void BMEM_P_AddFree(BMEM_Heap_Handle pheap, BMEM_P_BlockInfo *pbi)
1076	{
1077	BMEM_P_BlockInfo *pbiBack = NULL;
1078	BMEM_P_BlockInfo *pbiBackPrev = NULL;
1079	BMEM_P_BlockInfo *pbiFront = NULL;
1080	BMEM_P_BlockInfo *pbiFrontPrev = NULL;
1081	BMEM_P_BlockInfo pbiTmp, pbiTmpPrev;
1082	uint32_t ulFrontAddress;
1083	uint32_t ulBackAddress;
1084	bool bMergeFront = false;
1085	bool bMergeBack = false;
1086
1087	/*
1088	* The free list is kept sorted in size order (smallest to largest).
1089	* This makes the compaction operation non-trivial. Neighbor compaction
1090	* is done on every free.
1091	*
1092	* 1. Scan through the list to find the new free block's
1093	* neighbors (front and back).
1094	* 2. If front neighbor found, combine with new node.
1095	* Resulting node is removed from list.
1096	* 3. If back neighbor found, combine and remove back neighbor.
1097	* 4. Insert resulting node into free list according to size.
1098	*/
1099
1100	/*
1101	* Step #1:
1102	* Scan through the list to find the new free block's
1103	* neighbors (front and back).
1104	*/
1105
1106	/* determine front and back address of new entry (re-used) */
1107	ulFrontAddress = BMEM_P_GetAddress(pheap, pbi) - pbi->ulFrontScrap;
1108	ulBackAddress = BMEM_P_GetAddress(pheap, pbi) + pbi->ulSize - pbi->ulFrontScrap;
1109
1110	/* traverse through entire list looking for neighbors. */
1111	for(pbiTmpPrev=NULL, pbiTmp=pheap->pFreeTop;
1112	pbiTmp!=NULL;
1113	pbiTmpPrev=pbiTmp, pbiTmp=pbiTmp->pnext)
1114	{
1115	#if BMEM_CHECK_DISORDER
1116	if(pheap->pSafetyConfigInfo->bCheckDisorder)
1117	{
1118	if(pbiTmpPrev!=NULL)
1119	{
1120	if(pbiTmpPrev->ulSize > pbiTmp->ulSize)
1121	{
1122	BDBG_ERR(("Disordered blocks! Two blocks are:"));
1123	#if BMEM_TRACK_FILE_AND_LINE
1124	if(pheap->pSafetyConfigInfo->bTrackFileAndLine)
1125	{
1126	BMEM_P_PrintBlock(pheap, pbiTmpPrev);
1127	BMEM_P_PrintBlock(pheap, pbiTmp);
1128	}
1129	#endif
1130	pheap->ulNumErrors++;
1131	}
1132	}
1133	}
1134	#endif /* BMEM_CHECK_DISORDER */
1135
1136	/* front neighbor?. */
1137	if(BMEM_P_GetAddress(pheap, pbiTmp) + pbiTmp->ulSize - pbiTmp->ulFrontScrap
1138	== ulFrontAddress)
1139	{
1140	/* found front neighbor */
1141	pbiFront = pbiTmp;
1142	pbiFrontPrev = pbiTmpPrev;
1143	bMergeFront = true;
1144
1145	/* found back neighbor as well? */
1146	if(bMergeBack)
1147	{
1148	/* no need to continue */
1149	break;
1150	}
1151
1152	/* back neighbor? */
1153	} else if(BMEM_P_GetAddress(pheap, pbiTmp) - pbiTmp->ulFrontScrap
1154	== ulBackAddress)
1155	{
1156	/* found back neighbor */
1157	pbiBack=pbiTmp;
1158	pbiBackPrev = pbiTmpPrev;
1159	bMergeBack = true;
1160
1161	/* found front neighbor as well? */
1162	if(bMergeFront)
1163	{
1164	/* no need to continue */
1165	break;
1166	}
1167	}
1168	}
1169
1170	/*
1171	* Step #2:
1172	* If front neighbor found, combine with new node.
1173	* Resulting combined node is removed from list so that in both cases
1174	* the final node is not on list
1175	*/
1176	if(pbiFront)
1177	{
1178	/* merge front neighbor with this block */
1179	pbiFront->ulSize += pbi->ulSize;
1180
1181	/* not the first element of the list? */
1182	if(pbiFrontPrev)
1183	{
1184	/* remove pbiFront from middle of list */
1185	pbiFrontPrev->pnext = pbiFront->pnext;
1186	if(pbiFront->pnext)
1187	{
1188	pbiFront->pnext->pprev = pbiFront;
1189	}
1190
1191	/* first element in the list */
1192	} else
1193	{
1194	/* remove pbiFront from head of list */
1195	pheap->pFreeTop = pbiFront->pnext;
1196	if(pheap->pFreeTop)
1197	{
1198	pheap->pFreeTop->pprev = NULL;
1199	}
1200	}
1201
1202	/* did we just remove pbiBackPrev? */
1203	if (pbiBackPrev == pbiFront)
1204	{
1205	/* update with new pbiBackPrev */
1206	pbiBackPrev = pbiFrontPrev;
1207	}
1208
1209	/* no need to keep original new node */
1210	BMEM_P_DropBlockInfo(pheap, pbi);
1211	}
1212	else
1213	{
1214	/* This block doesn't have immediate front neighbor. */
1215	pbiFront = pbi;
1216	}
1217
1218	/*
1219	* Step #3:
1220	* If back neighbor found, combine and remove back neighbor.
1221	* At this point, pbiFront is the new node. Since it has already
1222	* been removed from the list, pbiFrontPrev is undefined and should
1223	* not be used after this point.
1224	*/
1225
1226	/* do we have a back neighbor? */
1227	if(pbiBack)
1228	{
1229	/* not the first element of the list? */
1230	if(pbiBackPrev)
1231	{
1232	/* remove pbiBack from middle of list */
1233	pbiBackPrev->pnext = pbiBack->pnext;
1234	if(pbiBack->pnext)
1235	{
1236	pbiBack->pnext->pprev = pbiBackPrev;
1237	}
1238
1239	/* first element in the list */
1240	} else
1241	{
1242	/* remove pbiBack from head of list */
1243	pheap->pFreeTop = pbiBack->pnext;
1244	if(pheap->pFreeTop)
1245	{
1246	pheap->pFreeTop->pprev = NULL;
1247	}
1248	}
1249
1250	/* update front size with back size */
1251	pbiFront->ulSize += pbiBack->ulSize;
1252
1253	/* after merge, we need to remove back info */
1254	BMEM_P_DropBlockInfo(pheap, pbiBack);
1255	}
1256
1257	/*
1258	* Step #4:
1259	* Insert resulting node into free list according to size.
1260	*/
1261
1262	/* determine where block needs to be located */
1263	for(pbiTmpPrev=NULL, pbiTmp = pheap->pFreeTop;
1264	pbiTmp != NULL;
1265	pbiTmpPrev=pbiTmp, pbiTmp = pbiTmp->pnext)
1266	{
1267	/* found a node that is bigger or of equal size? */
1268	if(pbiTmp->ulSize >= pbiFront->ulSize)
1269	{
1270	/* insertion location found */
1271	break;
1272	}
1273	}
1274
1275	/* insert into the middle of the list? */
1276	if(pbiTmpPrev)
1277	{
1278	/* insert into the middle */
1279	pbiTmpPrev->pnext = pbiFront;
1280	if(pbiFront)
1281	{
1282	pbiFront->pprev = pbiTmpPrev;
1283	}
1284
1285	/* insert at the head of the list */
1286	}else
1287	{
1288	pheap->pFreeTop = pbiFront;
1289	if(pheap->pFreeTop)
1290	{
1291	pheap->pFreeTop->pprev = NULL;
1292	}
1293	}
1294	pbiFront->pnext = pbiTmp;
1295	if(pbiTmp)
1296	{
1297	pbiTmp->pprev = pbiFront;
1298	}
1299
1300	#if BMEM_TRACK_FILE_AND_LINE
1301	if(pheap->pSafetyConfigInfo->bTrackFileAndLine)
1302	{
1303	pbiFront->pchFilename = s_achFilenameFreeString;
1304	pbiFront->ulLine = 0;
1305	}
1306	#endif
1307
1308	BMEM_P_FillGuard(pheap, pbiFront);
1309	}
1310
1311	/{private}****************************************************************
1312	Summary:
1313	Adds a block to the allocated list.
1314
1315	Description:
1316	This function takes the given BlockInfo and adds it to the list of
1317	allocated blocks (assuming that allocated blocks are being tracked).
1318
1319	Returns:
1320	void
1321	****************************************************************************/
1322	static void BMEM_P_AddUsed(BMEM_Heap_Handle pheap, BMEM_P_BlockInfo *pbi)
1323	{
1324	#ifdef BMEM_TRACK_ALLOCATIONS
1325	if(pheap->pSafetyConfigInfo->bTrackAllocations)
1326	{
1327	pbi->pnext = pheap->pAllocTop;
1328	if(pheap->pAllocTop)
1329	{
1330	pheap->pAllocTop->pprev = pbi;
1331	}
1332	pheap->pAllocTop = pbi;
1333	pheap->pAllocTop->pprev = NULL;
1334	}
1335	#endif
1336
1337	BMEM_P_FillGuard(pheap, pbi);
1338	}
1339
1340	/***************************************************************************/
1341	size_t BMEM_Heap_GetLargestAvailableBlockSize(
1342	BMEM_Heap_Handle pheap
1343	)
1344	{
1345	BERR_Code err;
1346	BMEM_P_BlockInfo *pbi;
1347	size_t zLargestSize = 0;
1348
1349	uint32_t ulBookKeepingSize, ulFrontBookKeepingSize, ulFrontScrap;
1350	uint32_t addrBase = 0, addrFront, addrFrontOffset, addrFrontOffsetAligned;
1351
1352	BDBG_OBJECT_ASSERT(pheap, BMEM_Heap);
1353	BDBG_ENTER(BMEM_GetLargestAvailableBlockSize);
1354	ulBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
1355	BMEM_BOOKKEEPING_SIZE_LOCAL : BMEM_BOOKKEEPING_SIZE_SYSTEM;
1356	ulFrontBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
1357	BMEM_FRONT_BOOKKEEPING_SIZE_LOCAL : BMEM_FRONT_BOOKKEEPING_SIZE_SYSTEM;
1358
1359	/* acquire semaphore */
1360	err = BMEM_P_GET_SEMAPHORE(pheap);
1361	BDBG_ASSERT(err == BERR_SUCCESS);
1362
1363	/* traverse through all free blocks looking for the largest block */
1364	for (pbi = pheap->pFreeTop; pbi!=NULL; pbi=pbi->pnext)
1365	{
1366	/* larger than current? */
1367	if (pbi->ulSize > zLargestSize)
1368	{
1369	/* update current max */
1370	zLargestSize = pbi->ulSize;
1371	addrBase = BMEM_P_GetAddress(pheap, pbi);
1372	}
1373	}
1374
1375	if(zLargestSize)
1376	{
1377	/* the following calculates size of alignment scrap */
1378	addrFront = addrBase + ulFrontBookKeepingSize;
1379
1380	/* Alignment should be calculated on physical address */
1381	/* Push it forward to the next alignment */
1382	if(BMEM_Heap_ConvertAddressToOffset(pheap, (void *)addrFront, &addrFrontOffset) != BERR_SUCCESS)
1383	{
1384	BDBG_ERR(("Invalid address being converted to offset."));
1385	zLargestSize = 0;
1386	goto done;
1387	}
1388	addrFrontOffset = (addrFrontOffset + pheap->ulAlignMask) & ~pheap->ulAlignMask;
1389
1390	/* the following calculates size of alignment scrap */
1391	addrFrontOffsetAligned = (addrFrontOffset + pheap->ulAlignMask) & ~pheap->ulAlignMask;
1392
1393	/* Calculate the waste */
1394	ulFrontScrap = addrFrontOffsetAligned - addrFrontOffset;
1395
1396	/* can this block contain additional bookkeeping and alignment scrap bytes? */
1397	if (zLargestSize > ulBookKeepingSize + ulFrontScrap)
1398	{
1399	/* reduce the size of the block by the bookkeeping amount */
1400	zLargestSize -= (ulBookKeepingSize + ulFrontScrap);
1401	/* align available size */
1402	zLargestSize &= ~pheap->ulAlignMask;
1403
1404	/* not large enough to contain bookkeeping bytes */
1405	} else
1406	{
1407	/* not big enough to allocate */
1408	zLargestSize = 0;
1409	}
1410	}
1411
1412	done:
1413	/* release semaphore */
1414	BMEM_P_RELEASE_SEMAPHORE(pheap);
1415
1416	/* return largest size found */
1417	BDBG_MSG(("BMEM_LargestBlock = %lu", zLargestSize));
1418	BDBG_LEAVE(BMEM_GetLargestAvailableBlockSize);
1419
1420	return zLargestSize;
1421	}
1422
1423	/*********************************************************************func
1424	* BMEM_GetInfo - Gets information about the heap.
1425	*
1426	* The function BMEM_GetInfo fills in a structure with a variety of
1427	* interesting information about the heap. This information is mainly useful
1428	* for debugging and statistic gathering. See the BMEM_HeapInfo structure
1429	* definition for the set of information returned.
1430	*
1431	* Returns:
1432	* void
1433	*
1434	*/
1435	void BMEM_Heap_GetInfo
1436	(
1437	BMEM_Heap_Handle pheap,
1438	BMEM_HeapInfo *phi
1439	)
1440	{
1441	BERR_Code err;
1442	BMEM_P_BlockInfo *pbi;
1443
1444	BDBG_OBJECT_ASSERT(pheap, BMEM_Heap);
1445	BDBG_ENTER(BMEM_Heap_GetInfo);
1446	BDBG_MSG(("BMEM_Heap_GetInfo(%p (%p), %p)", (pheap ? pheap->pvHeap : NULL), pheap, phi));
1447
1448	/* acquire semaphore */
1449	err = BMEM_P_GET_SEMAPHORE(pheap);
1450	BDBG_ASSERT(err == BERR_SUCCESS);
1451
1452	/* get creation data */
1453	phi->pvAddress = pheap->pvHeap;
1454	phi->ulOffset = pheap->ulOffset;
1455	phi->zSize = pheap->zSize;
1456	phi->uiAlignment = pheap->uiAlignment;
1457
1458	/* get statistics */
1459	phi->ulLargestFree = 0;
1460	phi->ulSmallestFree = 0xffffffff;
1461	phi->ulTotalFree = 0;
1462	phi->ulNumFree = 0;
1463	for(pbi = pheap->pFreeTop; pbi!=NULL; pbi=pbi->pnext)
1464	{
1465	if(pbi->ulSize > phi->ulLargestFree)
1466	{
1467	phi->ulLargestFree = pbi->ulSize;
1468	}
1469	if(pbi->ulSize < phi->ulSmallestFree)
1470	{
1471	phi->ulSmallestFree = pbi->ulSize;
1472	}
1473	phi->ulTotalFree += pbi->ulSize;
1474	++phi->ulNumFree;
1475	}
1476
1477	phi->ulLargestAllocated = 0;
1478	phi->ulSmallestAllocated = 0xffffffff;
1479	phi->ulTotalAllocated = 0;
1480	phi->ulNumAllocated = 0;
1481
1482	#ifdef BMEM_TRACK_ALLOCATIONS
1483	for(pbi = pheap->pAllocTop; pbi!=NULL; pbi=pbi->pnext)
1484	{
1485	if(pbi->ulSize > phi->ulLargestAllocated)
1486	{
1487	phi->ulLargestAllocated = pbi->ulSize;
1488	}
1489	if(pbi->ulSize < phi->ulSmallestAllocated)
1490	{
1491	phi->ulSmallestAllocated = pbi->ulSize;
1492	}
1493	/* phi->ulTotalAllocated += pbi->ulSize;
1494	++phi->ulNumAllocated;
1495	*/
1496	}
1497	#endif
1498
1499	phi->ulNumAllocated = pheap->ulNumAllocated;
1500	phi->ulTotalAllocated = pheap->ulTotalAllocated;
1501	phi->ulHighWatermark = pheap->ulHighWatermark;
1502
1503	/* release semaphore */
1504	BMEM_P_RELEASE_SEMAPHORE(pheap);
1505
1506	/* set number of errors found */
1507	phi->ulNumErrors = pheap->ulNumErrors;
1508
1509	BDBG_LEAVE(BMEM_Heap_GetInfo);
1510	}
1511
1512	void BMEM_Heap_ResetHighWatermark
1513	(
1514	BMEM_Heap_Handle pheap
1515	)
1516	{
1517	BDBG_ENTER(BMEM_Heap_ResetHighWatermark);
1518	pheap->ulHighWatermark = 0;
1519	BDBG_LEAVE(BMEM_Heap_ResetHighWatermark);
1520	}
1521
1522	/***************************************************************************/
1523	static BERR_Code BMEM_P_ValidatePointer(BMEM_Heap_Handle pheap, BMEM_P_BlockInfo *pbi)
1524	{
1525	if ((uint32_t)pbi % 4 != 0) {
1526	BDBG_ERR(("Unaligned pointer %p", pbi));
1527	return BERR_UNKNOWN;
1528	}
1529	if (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) {
1530	if ((void)pbi < (void)pheap->pStart \|\| (void)pbi > (void)pheap->pEnd) {
1531	BDBG_ERR(("Pointer %p out of heap %p..%p", pbi, pheap->pStart, pheap->pEnd));
1532	return BERR_UNKNOWN;
1533	}
1534	}
1535	/* TODO: else for BMEM_BOOKKEEPING_SYSTEM */
1536	return BERR_SUCCESS;
1537	}
1538
1539	/* Use a large number to detect linked list loops */
1540	#define BMEM_P_MAX_NODES_FOR_LOOP_TEST 50000
1541
1542	static BERR_Code BMEM_P_CheckList(BMEM_Heap_Handle pheap, BMEM_P_BlockInfo pbi, const char name)
1543	{
1544	BERR_Code err;
1545	int count = 0;
1546
1547	BSTD_UNUSED(name);
1548
1549	/* Check free list */
1550	for (; pbi; pbi=pbi->pnext) {
1551	/* 1. Validate pointers to avoid unaligned access and page faults based on corruptions. */
1552	err = BMEM_P_ValidatePointer(pheap, pbi);
1553	if (err) return BERR_TRACE(err);
1554
1555	/* 2. Check guard bands for overruns. */
1556	err = BMEM_P_CheckGuard(pheap, pbi);
1557	if (err) return BERR_TRACE(err);
1558
1559	/* 3. Check for a loop in the list by detecting excessive iterations. */
1560	count++;
1561	if (count > BMEM_P_MAX_NODES_FOR_LOOP_TEST) {
1562	pheap->ulNumErrors++;
1563	BDBG_ERR(("Loop in %s list!", name));
1564	return BERR_TRACE(BERR_UNKNOWN);
1565	}
1566	}
1567	return BERR_SUCCESS;
1568	}
1569
1570	/* BMEM_Heap_Validate is the first line of defense against heap corruptions.
1571	We should avoid any implicit failures (segfaults, unaligned accesses) and provide
1572	explicit failures with hopefully helpful debug information. */
1573	BERR_Code BMEM_Heap_Validate
1574	(
1575	BMEM_Heap_Handle pheap
1576	)
1577	{
1578	BERR_Code err = BERR_SUCCESS;
1579
1580	BDBG_ENTER(BMEM_Heap_Validate);
1581
1582	BDBG_OBJECT_ASSERT(pheap, BMEM_Heap);
1583
1584	/* acquire semaphore */
1585	err = BMEM_P_GET_SEMAPHORE(pheap);
1586	BDBG_ASSERT(err == BERR_SUCCESS);
1587
1588	/* validate free list */
1589	err = BMEM_P_CheckList(pheap, pheap->pFreeTop, "free");
1590	if (err) goto done_release_sem;
1591
1592	#ifdef BMEM_TRACK_ALLOCATIONS
1593	if(pheap->pSafetyConfigInfo->bTrackAllocations)
1594	{
1595	/* validate allocated list */
1596	err = BMEM_P_CheckList(pheap, pheap->pAllocTop, "allocated");
1597	if (err) goto done_release_sem;
1598
1599	/* Check to see if any blocks are in both the free and allocated lists */
1600	{
1601	BMEM_P_BlockInfo *pbiTmp;
1602	for(pbiTmp = pheap->pFreeTop; pbiTmp!=NULL; pbiTmp=pbiTmp->pnext)
1603	{
1604	BMEM_P_BlockInfo *pbi;
1605	for(pbi = pheap->pAllocTop; pbi!=NULL; pbi=pbi->pnext)
1606	{
1607	if(pbi == pbiTmp)
1608	{
1609	pheap->ulNumErrors++;
1610	err = BERR_TRACE(BERR_UNKNOWN);
1611	BDBG_ERR(("Block in both free and alloc lists!"));
1612	#if BMEM_TRACK_FILE_AND_LINE
1613	if(pheap->pSafetyConfigInfo->bTrackFileAndLine)
1614	{
1615	BMEM_P_PrintBlock(pheap, pbi);
1616	}
1617	#endif
1618	goto done_release_sem; /* unrecoverable problem, bail */
1619	}
1620	}
1621	}
1622	}
1623	}
1624	#endif
1625
1626	done_release_sem:
1627	/* release semaphore */
1628	BMEM_P_RELEASE_SEMAPHORE(pheap);
1629
1630	/* return status */
1631	BDBG_LEAVE(BMEM_Heap_Validate);
1632	return err;
1633	}
1634
1635	/*********************************************************************func
1636	* BMEM_P_FillGuard - Fills the guards bytes of a block.
1637	*
1638	* This function fills both the front and back guard bytes of a given block.
1639	* If the block has any back scrap, this area is also filled with the guard
1640	* byte. (The front scrap is not since it actually sits in front of
1641	* bookkeeping information.)
1642	*
1643	* Returns:
1644	* void
1645	*/
1646	void BMEM_P_FillGuard(BMEM_Heap_Handle pheap, BMEM_P_BlockInfo *pbi)
1647	{
1648	#if (BMEM_GUARD_SIZE != 0)
1649	if (pheap->ulGuardSizeBytes)
1650	{
1651	size_t i;
1652	uint32_t ulFrontBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
1653	BMEM_FRONT_BOOKKEEPING_SIZE_LOCAL : BMEM_FRONT_BOOKKEEPING_SIZE_SYSTEM;
1654	uint8_t pcFront = (uint8_t )BMEM_P_GetAddress(pheap, pbi) +
1655	ulFrontBookKeepingSize- pheap->ulGuardSizeBytes;
1656	uint8_t pcBack = (uint8_t )BMEM_P_GetAddress(pheap, pbi) - pbi->ulFrontScrap +
1657	pbi->ulSize - pbi->ulBackScrap - pheap->ulGuardSizeBytes;
1658	void *pcFrontCached = NULL;
1659	void *pcBackCached = NULL;
1660	bool bIsCached;
1661	BERR_Code err;
1662
1663	err = BMEM_Heap_ConvertAddressToCached(pheap, pcFront, &pcFrontCached);
1664	if (err == BERR_SUCCESS)
1665	{
1666	err = BMEM_Heap_ConvertAddressToCached(pheap, pcBack, &pcBackCached);
1667	}
1668
1669	bIsCached = (err == BERR_SUCCESS) && ((pcFront != pcFrontCached) \|\| (pcBack != pcBackCached));
1670
1671	if (bIsCached)
1672	{
1673	BMEM_Heap_FlushCache_isr(pheap, pcFrontCached, pheap->ulGuardSizeBytes);
1674	BMEM_Heap_FlushCache_isr(pheap, pcBackCached, pbi->ulBackScrap + pheap->ulGuardSizeBytes);
1675	pcFront = pcFrontCached;
1676	pcBack = pcBackCached;
1677	}
1678
1679	for(i=0; i<pheap->ulGuardSizeBytes; ++i)
1680	{
1681	pcFront[i] = BMEM_GUARD_BYTE;
1682	}
1683
1684	for(i=0; i<pbi->ulBackScrap + pheap->ulGuardSizeBytes; ++i )
1685	{
1686	pcBack[i] = BMEM_GUARD_BYTE;
1687	}
1688
1689	if (bIsCached)
1690	{
1691	BMEM_Heap_FlushCache_isr(pheap, pcFrontCached, pheap->ulGuardSizeBytes);
1692	BMEM_Heap_FlushCache_isr(pheap, pcBackCached, pbi->ulBackScrap + pheap->ulGuardSizeBytes);
1693	}
1694	}
1695
1696	#else
1697	BSTD_UNUSED(pbi);
1698	#endif
1699	BSTD_UNUSED(pheap); /* GetAddress might be a macro which doesn't use pheap */
1700	}
1701
1702	/*********************************************************************func
1703	* BMEM_P_CheckGuard - Checks the guard bytes to see if they are valid.
1704	*
1705	* This function checks the front guard and back guard bytes (including the
1706	* back scrap, if any) for any out-of-bound writes. If the guard bytes are
1707	* not the specified value, then an error is noted and false returned.
1708	*
1709	* Returns:
1710	* Returns true if the guard bytes are unmolested, and false if an overrun
1711	* or underrun is detected.
1712	*/
1713	BERR_Code BMEM_P_CheckGuard
1714	(
1715	BMEM_Heap_Handle pheap,
1716	BMEM_P_BlockInfo *pbi
1717	)
1718	{
1719	BERR_Code err = BERR_SUCCESS;
1720
1721	#if (BMEM_GUARD_SIZE != 0)
1722	if (pheap->ulGuardSizeBytes)
1723	{
1724	size_t ii;
1725
1726	uint32_t ulFrontBookKeepingSize = (pheap->eBookKeeping == BMEM_BOOKKEEPING_LOCAL) ?
1727	BMEM_FRONT_BOOKKEEPING_SIZE_LOCAL : BMEM_FRONT_BOOKKEEPING_SIZE_SYSTEM;
1728
1729	/* pointers for checking in 32-bit increments */
1730	uint32_t pulFront = (uint32_t ) (BMEM_P_GetAddress( pheap, pbi ) +
1731	ulFrontBookKeepingSize - pheap->ulGuardSizeBytes);
1732
1733	uint32_t pulBack = (uint32_t ) (BMEM_P_GetAddress( pheap, pbi ) -
1734	pbi->ulFrontScrap + pbi->ulSize - pbi->ulBackScrap - pheap->ulGuardSizeBytes);
1735
1736	void *pulFrontCached = NULL;
1737	void *pulBackCached = NULL;
1738	bool bIsCached;
1739
1740	uint32_t ulGuardSizeWords = pheap->ulGuardSizeBytes / 4;
1741	uint32_t ulBackGuardSizeWords = (pheap->ulGuardSizeBytes + pbi->ulBackScrap) / 4;
1742
1743	err = BMEM_Heap_ConvertAddressToCached(pheap, pulFront, &pulFrontCached);
1744	if (err == BERR_SUCCESS)
1745	{
1746	err = BMEM_Heap_ConvertAddressToCached(pheap, pulBack, &pulBackCached);
1747	}
1748
1749	bIsCached = (err == BERR_SUCCESS) && ((pulFront != pulFrontCached) \|\| (pulBack != pulBackCached));
1750
1751	if (bIsCached)
1752	{
1753	pulFront = pulFrontCached;
1754	pulBack = pulBackCached;
1755	}
1756
1757	/* check in 32-bit chunks to take advantage of cache */
1758	for( ii = 0; ii < ulGuardSizeWords; ++ii )
1759	{
1760	if( pulFront[ ii ] != BMEM_P_GUARD_DWORD )
1761	{
1762	pheap->ulNumErrors++;
1763	err = BERR_UNKNOWN;
1764	BDBG_ERR(("Front guard violation in block! (%d)", pheap->ulGuardSizeBytes));
1765	#if BMEM_TRACK_FILE_AND_LINE
1766	if(pheap->pSafetyConfigInfo->bTrackFileAndLine)
1767	{
1768	BMEM_P_PrintBlock(pheap, pbi);
1769	}
1770	#endif
1771	for( ii = 0; ii < ulGuardSizeWords; ++ii )
1772	{
1773	BKNI_Printf("%02x", pulFront[ii]);
1774	}
1775	BKNI_Printf("\n");
1776	break;
1777	}
1778	}
1779
1780	for( ii=0; ii < ulBackGuardSizeWords; ++ii )
1781	{
1782	if( pulBack[ ii ] != BMEM_P_GUARD_DWORD )
1783	{
1784	pheap->ulNumErrors++;
1785	err = BERR_UNKNOWN;
1786	BDBG_ERR(("Back guard violation in block! (%d)", pbi->ulBackScrap + pheap->ulGuardSizeBytes));
1787	#if BMEM_TRACK_FILE_AND_LINE
1788	if(pheap->pSafetyConfigInfo->bTrackFileAndLine)
1789	{
1790	BMEM_P_PrintBlock(pheap, pbi);
1791	}
1792	#endif
1793	for( ii=0; ii < ulBackGuardSizeWords; ++ii )
1794	{
1795	BKNI_Printf("%02x", pulBack[ii]);
1796	}
1797	BKNI_Printf("\n");
1798	break;
1799	}
1800	}
1801	}
1802
1803	#else
1804	BSTD_UNUSED(pheap);
1805	BSTD_UNUSED(pbi);
1806	#endif
1807
1808	return err;
1809	}
1810
1811	/***************************************************************************/
1812	BERR_Code BMEM_Heap_ConvertOffsetToAddress
1813	(
1814	BMEM_Heap_Handle Heap,
1815	uint32_t Offset,
1816	void **Address
1817	)
1818	{
1819	BMEM_Heap_Handle hCurHeap = Heap;
1820
1821	BDBG_OBJECT_ASSERT(Heap, BMEM_Heap);
1822
1823	/* calculate */
1824	Address = (void )((uint8_t *)hCurHeap->pvHeap + Offset - hCurHeap->ulOffset);
1825	if (BMEM_P_Heap_CheckAddress(hCurHeap, (uint8_t )Address))
1826	{
1827	goto done;
1828	}
1829	else if (Heap->hMem)
1830	{
1831	/* check other heaps for match */
1832	for(hCurHeap = BLST_S_FIRST(&(Heap->hMem->HeapList)); hCurHeap ; hCurHeap = BLST_S_NEXT(hCurHeap, link))
1833	{
1834	if (hCurHeap != Heap)
1835	{
1836	/* calculate */
1837	Address = (void )((uint8_t *)hCurHeap->pvHeap + Offset - hCurHeap->ulOffset);
1838	if (BMEM_P_Heap_CheckAddress(hCurHeap, (uint8_t )Address))
1839	{
1840	goto done;
1841	}
1842	}
1843	}
1844	}
1845
1846	/* invalid offset, cannot find heap offset belongs to */
1847	return BERR_INVALID_PARAMETER;
1848
1849	done:
1850	return BERR_SUCCESS;
1851	}
1852
1853	/***************************************************************************/
1854	BERR_Code BMEM_Heap_ConvertAddressToOffset
1855	(
1856	BMEM_Heap_Handle Heap,
1857	void *Address,
1858	uint32_t *Offset
1859	)
1860	{
1861	BMEM_Heap_Handle hCurHeap = Heap;
1862	void *unCachedAddress;
1863
1864	BDBG_OBJECT_ASSERT(Heap, BMEM_Heap);
1865
1866	if ((BMEM_P_Heap_CheckAddress(hCurHeap, (uint8_t *)Address)) \|\|
1867	(hCurHeap->pvCache && BMEM_P_Heap_CheckCachedAddress(hCurHeap, (uint8_t *)Address)))
1868	{
1869	goto done;
1870	}
1871	else if (Heap->hMem)
1872	{
1873	/* check other heaps for match */
1874	for(hCurHeap = BLST_S_FIRST(&(Heap->hMem->HeapList)); hCurHeap ; hCurHeap = BLST_S_NEXT(hCurHeap, link))
1875	{
1876	if ((hCurHeap != Heap) &&
1877	((BMEM_P_Heap_CheckAddress(hCurHeap, (uint8_t *)Address)) \|\|
1878	(hCurHeap->pvCache && BMEM_P_Heap_CheckCachedAddress(hCurHeap, (uint8_t *)Address))))
1879	{
1880	goto done;
1881	}
1882	}
1883	}
1884
1885	/* invalid address, cannot find heap address belongs to */
1886	return BERR_INVALID_PARAMETER;
1887
1888	done:
1889	/* calculate */
1890
1891	if(BMEM_P_Heap_CheckCachedAddress(hCurHeap, (uint8_t *)Address))
1892	{
1893	unCachedAddress = (void)((uint8_t)Address - (uint8_t)hCurHeap->pvCache + (uint8_t)hCurHeap->pvHeap);
1894	}
1895	else
1896	{
1897	unCachedAddress = Address;
1898	}
1899
1900	Offset = hCurHeap->ulOffset + (uint8_t )unCachedAddress - (uint8_t *)hCurHeap->pvHeap;
1901
1902	return BERR_SUCCESS;
1903	}
1904
1905	/***************************************************************************/
1906	BERR_Code BMEM_Heap_ConvertAddressToCached
1907	(
1908	BMEM_Heap_Handle Heap, /* Heap that contains the memory block. */
1909	void pvAddress, / Address of the memory block */
1910	void *ppvCachedAddress / [out] Returned cache address. */
1911	)
1912	{
1913	BMEM_Heap_Handle hCurHeap = Heap;
1914
1915	BDBG_OBJECT_ASSERT(Heap, BMEM_Heap);
1916
1917	if (BMEM_P_Heap_CheckAddress(hCurHeap, (uint8_t *)pvAddress))
1918	{
1919	goto done;
1920	}
1921	else if (Heap->hMem)
1922	{
1923	/* check other heaps for match */
1924	for(hCurHeap = BLST_S_FIRST(&(Heap->hMem->HeapList)); hCurHeap ; hCurHeap = BLST_S_NEXT(hCurHeap, link))
1925	{
1926	if ((hCurHeap != Heap) && (BMEM_P_Heap_CheckAddress(hCurHeap, (uint8_t *)pvAddress)))
1927	{
1928	goto done;
1929	}
1930	}
1931	}
1932
1933	/* invalid address, cannot find heap address belongs to */
1934	return BERR_INVALID_PARAMETER;
1935
1936	done:
1937	/* If the user never provided the cached mapping nor cache flushing,
1938	* then don't convert just return the non-cached address. */
1939	if((hCurHeap->pvCache) &&
1940	(hCurHeap->pfFlushCb) &&
1941	(hCurHeap->pfFlushCb_isr) &&
1942	(ppvCachedAddress))
1943	{
1944	ppvCachedAddress = (void)((uint8_t*)hCurHeap->pvCache +
1945	((uint8_t)pvAddress - (uint8_t)hCurHeap->pvHeap));
1946	}
1947	else if(ppvCachedAddress)
1948	{
1949	/* Did not set cached so just return the non-cached address. */
1950	*ppvCachedAddress = pvAddress;
1951	}
1952
1953	return BERR_SUCCESS;
1954	}
1955
1956	/{private}****************************************************************
1957	Summary:
1958	Finds the heap the cache address blongs to
1959
1960	Output:
1961	phCacheHeap
1962
1963	Returns:
1964	BERR_SUCCESS
1965	BERR_INVALID_PARAMETER
1966	****************************************************************************/
1967	BERR_Code BMEM_P_Heap_FindCacheHeap
1968	(
1969	BMEM_Heap_Handle Heap, /* Heap */
1970	void pvCachedAddress, / Start address to flush */
1971	BMEM_Heap_Handle phCacheHeap / Actual heap containing cache memory */
1972	)
1973	{
1974	BMEM_Heap_Handle hCurHeap = Heap;
1975
1976	BDBG_OBJECT_ASSERT(Heap, BMEM_Heap);
1977
1978	if ((pvCachedAddress >= (void*)Heap->pvCache) &&
1979	(pvCachedAddress <= (void)(Heap->pEnd - (uint8_t )Heap->pvHeap + (uint8_t *)Heap->pvCache)))
1980	{
1981	goto done;
1982	}
1983	else if (Heap->hMem)
1984	{
1985	/* check other heaps for match */
1986	for(hCurHeap = BLST_S_FIRST(&(Heap->hMem->HeapList)); hCurHeap ; hCurHeap = BLST_S_NEXT(hCurHeap, link))
1987	{
1988	if ((hCurHeap != Heap) &&
1989	(pvCachedAddress >= (void*)Heap->pvCache) &&
1990	(pvCachedAddress <= (void)(Heap->pEnd - (uint8_t )Heap->pvHeap + (uint8_t *)Heap->pvCache)))
1991	{
1992	goto done;
1993	}
1994	}
1995	}
1996
1997	/* invalid address, cannot find heap address belongs to */
1998	*phCacheHeap = NULL;
1999	return BERR_INVALID_PARAMETER;
2000
2001	done:
2002	*phCacheHeap = hCurHeap;
2003	return BERR_SUCCESS;
2004	}
2005
2006	/***************************************************************************/
2007	BERR_Code BMEM_Heap_FlushCache
2008	(
2009	BMEM_Heap_Handle Heap, /* Heap containing the cached memory. */
2010	void pvCachedAddress, / Start address to flush */
2011	size_t size /* Size in bytes of the block to flush */
2012	)
2013	{
2014	BMEM_Heap_Handle hCacheHeap;
2015	BERR_Code err;
2016
2017	BDBG_OBJECT_ASSERT(Heap, BMEM_Heap);
2018
2019	err = BMEM_P_Heap_FindCacheHeap(Heap, pvCachedAddress, &hCacheHeap);
2020
2021	if(err != BERR_SUCCESS)
2022	{
2023	return BERR_INVALID_PARAMETER;
2024	}
2025
2026	/* Call platform specific flush. */
2027	if(hCacheHeap->pfFlushCb)
2028	{
2029	hCacheHeap->pfFlushCb(pvCachedAddress, size);
2030	}
2031
2032	return BERR_SUCCESS;
2033	}
2034
2035	/***************************************************************************/
2036	BERR_Code BMEM_Heap_FlushCache_isr
2037	(
2038	BMEM_Heap_Handle Heap, /* Heap containing the cached memory. */
2039	void pvCachedAddress, / Start address to flush */
2040	size_t size /* Size in bytes of the block to flush */
2041	)
2042	{
2043	BMEM_Heap_Handle hCacheHeap;
2044	BERR_Code err;
2045
2046	BDBG_OBJECT_ASSERT(Heap, BMEM_Heap);
2047
2048	err = BMEM_P_Heap_FindCacheHeap(Heap, pvCachedAddress, &hCacheHeap);
2049
2050	if(err != BERR_SUCCESS)
2051	{
2052	return BERR_INVALID_PARAMETER;
2053	}
2054
2055	/* Call platform specific flush. */
2056	if(hCacheHeap->pfFlushCb_isr)
2057	{
2058	hCacheHeap->pfFlushCb_isr(pvCachedAddress, size);
2059	}
2060
2061	return BERR_SUCCESS;
2062	}
2063
2064	/***************************************************************************/
2065	BERR_Code BMEM_Heap_InstallMonitor(BMEM_Heap_Handle heap, BMEM_MonitorInterface *monitor)
2066	{
2067	BERR_Code err;
2068
2069	BDBG_OBJECT_ASSERT(heap, BMEM_Heap);
2070	/* acquire semaphore */
2071	err = BMEM_P_GET_SEMAPHORE(heap);
2072	BDBG_ASSERT(err == BERR_SUCCESS);
2073
2074	heap->monitor = monitor;
2075	/* release semaphore */
2076	BMEM_P_RELEASE_SEMAPHORE(heap);
2077	return BERR_SUCCESS;
2078	}
2079
2080	/***************************************************************************/
2081	void BMEM_Heap_RemoveMonitor(BMEM_Heap_Handle heap, BMEM_MonitorInterface *monitor)
2082	{
2083	BERR_Code err;
2084	BSTD_UNUSED(monitor);
2085
2086	BDBG_OBJECT_ASSERT(heap, BMEM_Heap);
2087	/* we have to acquire semaphore, to prevent removing monitor disapearing
2088	* underneath of alloc or free */
2089	/* acquire semaphore */
2090	err = BMEM_P_GET_SEMAPHORE(heap);
2091	BDBG_ASSERT(err == BERR_SUCCESS);
2092
2093	heap->monitor = NULL;
2094
2095	/* release semaphore */
2096	BMEM_P_RELEASE_SEMAPHORE(heap);
2097	return;
2098	}
2099
2100	/***************************************************************************/
2101	BERR_Code BMEM_Heap_GetDefaultSettings
2102	(
2103	BMEM_Heap_Settings *pHeapSettings
2104	)
2105	{
2106	BERR_Code err = BERR_SUCCESS;
2107
2108	BDBG_ENTER(BMEM_Heap_GetDefaultSettings);
2109
2110	if(pHeapSettings)
2111	{
2112	*pHeapSettings = s_stDefaultHeapSettings;
2113	}
2114	else
2115	{
2116	err = BERR_INVALID_PARAMETER;
2117	}
2118
2119	BDBG_LEAVE(BMEM_Heap_GetDefaultSettings);
2120	return err;
2121	}
2122
2123	/***************************************************************************/
2124	BERR_Code BMEM_Heap_Create
2125	(
2126	BMEM_ModuleHandle hMem, /* main handle from BMEM_Open() - NULL is possible for older chipsets (7038/3560 only) */
2127	void pvAddress, / Pointer to beginning of memory chunk to manage (uncached) */
2128	uint32_t ulOffset, /* Device offset of initial location */
2129	size_t zSize, /* Size of chunk to manage in bytes */
2130	BMEM_Heap_Settings pHeapSettings, / default settings */
2131	BMEM_Heap_Handle phHeap / returned heap */
2132	)
2133	{
2134	BERR_Code err = BERR_SUCCESS;
2135
2136	#if !((BCHP_CHIP==7038) \|\| (BCHP_CHIP==3560))
2137	if(!hMem)
2138	{
2139	BDBG_ERR(("Must provide BMEM_ModuleHandle for this chipset."));
2140	return BERR_INVALID_PARAMETER;
2141	}
2142	#endif
2143
2144	if (pHeapSettings->eBookKeeping == BMEM_BOOKKEEPING_SYSTEM)
2145	{
2146	err = BMEM_P_SystemCreateHeap (phHeap, pvAddress, ulOffset, zSize, pHeapSettings);
2147	}
2148	else if (pHeapSettings->eBookKeeping == BMEM_BOOKKEEPING_LOCAL)
2149	{
2150	err = BMEM_P_LocalCreateHeap (phHeap, pvAddress, ulOffset, zSize, pHeapSettings);
2151	}
2152	else
2153	{
2154	BDBG_ERR(("Must be configured for either system or local bookkeeping."));
2155	BDBG_ASSERT(false);
2156	return BERR_INVALID_PARAMETER;
2157	}
2158
2159	if (*phHeap)
2160	{
2161	(*phHeap)->hMem = hMem;
2162
2163	if ((err == BERR_SUCCESS) && (hMem != NULL))
2164	{
2165	BLST_S_INSERT_HEAD(&(hMem->HeapList), (*phHeap), link);
2166	}
2167	}
2168
2169	BDBG_OBJECT_ASSERT(*phHeap, BMEM_Heap);
2170	return err;
2171	}
2172
2173	/***************************************************************************/
2174	void BMEM_Heap_Destroy
2175	(
2176	BMEM_Heap_Handle Heap
2177	)
2178	{
2179	BDBG_OBJECT_ASSERT(Heap, BMEM_Heap);
2180	if(Heap->hMem)
2181	{
2182	BLST_S_REMOVE(&(Heap->hMem->HeapList), Heap, BMEM_P_Heap, link);
2183	}
2184	(*Heap->pDestroyHeapFunc) (Heap);
2185	}
2186
2187	/*********************************************************************func
2188	* BMEM_CreateHeap - Initializes the heap with bookkeeping (whether system
2189	* or local) based on the BMEM_BOOKKEEPING_CONFIG flag
2190	* setting.
2191	*
2192	* This function inititalizes a heap at a given location and size.
2193	* Any previous allocations in the chunk of memory handed over to this
2194	* function are lost. Every heap has a base minimum alignment for all of
2195	* the allocations within that heap. (However, you can specify a greater
2196	* alignment when actually doing an allocation.)
2197	*
2198	*
2199	* Returns:
2200	* Returns true if heap is initialized, or false if the size of the heap
2201	* is too small to manage or there isn't enough system memory to allocate
2202	* bookkeeping information (when configured for system memory
2203	* bookkeeping).
2204	*
2205	*/
2206	/* This module is empty unless we're using local bookkeeping. */
2207	BERR_Code BMEM_CreateHeap
2208	(
2209	BMEM_Handle ppHeap, / Address to store pointer of new heap info structure */
2210	void pvHeap, / Pointer to beginning of memory chunk to manage */
2211	uint32_t ulOffset, /* Device offset of initial location */
2212	size_t zSize, /* Size of chunk to manage in bytes */
2213	unsigned int uiAlignment /* Minimum alignment for all allocations in the heap */
2214	)
2215	{
2216	BMEM_Heap_Settings stHeapSettings;
2217	BMEM_Heap_Settings *pHeapSettings = &stHeapSettings;
2218
2219	BMEM_Heap_GetDefaultSettings(pHeapSettings);
2220
2221	pHeapSettings->uiAlignment = uiAlignment;
2222
2223	#if (BMEM_BOOKKEEPING_CONFIG == BMEM_BOOKKEEPING_SYSTEM)
2224	pHeapSettings->eBookKeeping = BMEM_BOOKKEEPING_SYSTEM;
2225	#elif (BMEM_BOOKKEEPING_CONFIG == BMEM_BOOKKEEPING_LOCAL)
2226	pHeapSettings->eBookKeeping = BMEM_BOOKKEEPING_LOCAL;
2227	#else
2228	BDBG_ERR(("Must be configured for either system or local bookkeeping."));
2229	BDBG_ASSERT(false);
2230	#endif /* (BMEM_BOOKKEEPING_CONFIG == BMEM_BOOKKEEPING_SYSTEM) */
2231
2232	return (BMEM_Heap_Create(NULL, pvHeap, ulOffset, zSize, pHeapSettings, ppHeap));
2233	}
2234
2235	/* End of File */

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

Context Navigation

source: svn/trunk/newcon3bcm2_21bu/magnum/basemodules/mem/bmem.c @ 25

Download in other formats: