1 /*
2 * Copyright 2008-2012 Freescale Semiconductor Inc.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 * * Redistributions of source code must retain the above copyright
7 * notice, this list of conditions and the following disclaimer.
8 * * Redistributions in binary form must reproduce the above copyright
9 * notice, this list of conditions and the following disclaimer in the
10 * documentation and/or other materials provided with the distribution.
11 * * Neither the name of Freescale Semiconductor nor the
12 * names of its contributors may be used to endorse or promote products
13 * derived from this software without specific prior written permission.
14 *
15 *
16 * ALTERNATIVELY, this software may be distributed under the terms of the
17 * GNU General Public License ("GPL") as published by the Free Software
18 * Foundation, either version 2 of that License or (at your option) any
19 * later version.
20 *
21 * THIS SOFTWARE IS PROVIDED BY Freescale Semiconductor ``AS IS'' AND ANY
22 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
23 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
24 * DISCLAIMED. IN NO EVENT SHALL Freescale Semiconductor BE LIABLE FOR ANY
25 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
26 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
27 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
28 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 */
32
33
34 #include "string_ext.h"
35 #include "error_ext.h"
36 #include "std_ext.h"
37 #include "part_ext.h"
38 #include "xx_ext.h"
39
40 #include "mm.h"
41
42
43
44
45 /**********************************************************************
46 * MM internal routines set *
47 **********************************************************************/
48
49 /****************************************************************
50 * Routine: CreateBusyBlock
51 *
52 * Description:
53 * Initializes a new busy block of "size" bytes and started
54 * rom "base" address. Each busy block has a name that
55 * specified the purpose of the memory allocation.
56 *
57 * Arguments:
58 * base - base address of the busy block
59 * size - size of the busy block
60 * name - name that specified the busy block
61 *
62 * Return value:
63 * A pointer to new created structure returned on success;
64 * Otherwise, NULL.
65 ****************************************************************/
CreateBusyBlock(uint64_t base,uint64_t size,char * name)66 static t_BusyBlock * CreateBusyBlock(uint64_t base, uint64_t size, char *name)
67 {
68 t_BusyBlock *p_BusyBlock;
69 uint32_t n;
70
71 p_BusyBlock = (t_BusyBlock *)XX_Malloc(sizeof(t_BusyBlock));
72 if ( !p_BusyBlock )
73 {
74 REPORT_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
75 return NULL;
76 }
77
78 p_BusyBlock->base = base;
79 p_BusyBlock->end = base + size;
80
81 n = strlen(name);
82 if (n >= MM_MAX_NAME_LEN)
83 n = MM_MAX_NAME_LEN - 1;
84 strncpy(p_BusyBlock->name, name, MM_MAX_NAME_LEN-1);
85 p_BusyBlock->name[n] = '\0';
86 p_BusyBlock->p_Next = 0;
87
88 return p_BusyBlock;
89 }
90
91 /****************************************************************
92 * Routine: CreateNewBlock
93 *
94 * Description:
95 * Initializes a new memory block of "size" bytes and started
96 * from "base" address.
97 *
98 * Arguments:
99 * base - base address of the memory block
100 * size - size of the memory block
101 *
102 * Return value:
103 * A pointer to new created structure returned on success;
104 * Otherwise, NULL.
105 ****************************************************************/
CreateNewBlock(uint64_t base,uint64_t size)106 static t_MemBlock * CreateNewBlock(uint64_t base, uint64_t size)
107 {
108 t_MemBlock *p_MemBlock;
109
110 p_MemBlock = (t_MemBlock *)XX_Malloc(sizeof(t_MemBlock));
111 if ( !p_MemBlock )
112 {
113 REPORT_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
114 return NULL;
115 }
116
117 p_MemBlock->base = base;
118 p_MemBlock->end = base+size;
119 p_MemBlock->p_Next = 0;
120
121 return p_MemBlock;
122 }
123
124 /****************************************************************
125 * Routine: CreateFreeBlock
126 *
127 * Description:
128 * Initializes a new free block of of "size" bytes and
129 * started from "base" address.
130 *
131 * Arguments:
132 * base - base address of the free block
133 * size - size of the free block
134 *
135 * Return value:
136 * A pointer to new created structure returned on success;
137 * Otherwise, NULL.
138 ****************************************************************/
CreateFreeBlock(uint64_t base,uint64_t size)139 static t_FreeBlock * CreateFreeBlock(uint64_t base, uint64_t size)
140 {
141 t_FreeBlock *p_FreeBlock;
142
143 p_FreeBlock = (t_FreeBlock *)XX_Malloc(sizeof(t_FreeBlock));
144 if ( !p_FreeBlock )
145 {
146 REPORT_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
147 return NULL;
148 }
149
150 p_FreeBlock->base = base;
151 p_FreeBlock->end = base + size;
152 p_FreeBlock->p_Next = 0;
153
154 return p_FreeBlock;
155 }
156
157 /****************************************************************
158 * Routine: AddFree
159 *
160 * Description:
161 * Adds a new free block to the free lists. It updates each
162 * free list to include a new free block.
163 * Note, that all free block in each free list are ordered
164 * by their base address.
165 *
166 * Arguments:
167 * p_MM - pointer to the MM object
168 * base - base address of a given free block
169 * end - end address of a given free block
170 *
171 * Return value:
172 *
173 *
174 ****************************************************************/
AddFree(t_MM * p_MM,uint64_t base,uint64_t end)175 static t_Error AddFree(t_MM *p_MM, uint64_t base, uint64_t end)
176 {
177 t_FreeBlock *p_PrevB, *p_CurrB, *p_NewB;
178 uint64_t alignment;
179 uint64_t alignBase;
180 int i;
181
182 /* Updates free lists to include a just released block */
183 for (i=0; i <= MM_MAX_ALIGNMENT; i++)
184 {
185 p_PrevB = p_NewB = 0;
186 p_CurrB = p_MM->freeBlocks[i];
187
188 alignment = (uint64_t)(0x1 << i);
189 alignBase = MAKE_ALIGNED(base, alignment);
190
191 /* Goes to the next free list if there is no block to free */
192 if (alignBase >= end)
193 continue;
194
195 /* Looks for a free block that should be updated */
196 while ( p_CurrB )
197 {
198 if ( alignBase <= p_CurrB->end )
199 {
200 if ( end > p_CurrB->end )
201 {
202 t_FreeBlock *p_NextB;
203 while ( p_CurrB->p_Next && end > p_CurrB->p_Next->end )
204 {
205 p_NextB = p_CurrB->p_Next;
206 p_CurrB->p_Next = p_CurrB->p_Next->p_Next;
207 XX_Free(p_NextB);
208 }
209
210 p_NextB = p_CurrB->p_Next;
211 if ( !p_NextB || (p_NextB && end < p_NextB->base) )
212 {
213 p_CurrB->end = end;
214 }
215 else
216 {
217 p_CurrB->end = p_NextB->end;
218 p_CurrB->p_Next = p_NextB->p_Next;
219 XX_Free(p_NextB);
220 }
221 }
222 else if ( (end < p_CurrB->base) && ((end-alignBase) >= alignment) )
223 {
224 if ((p_NewB = CreateFreeBlock(alignBase, end-alignBase)) == NULL)
225 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
226
227 p_NewB->p_Next = p_CurrB;
228 if (p_PrevB)
229 p_PrevB->p_Next = p_NewB;
230 else
231 p_MM->freeBlocks[i] = p_NewB;
232 break;
233 }
234
235 if ((alignBase < p_CurrB->base) && (end >= p_CurrB->base))
236 {
237 p_CurrB->base = alignBase;
238 }
239
240 /* if size of the free block is less then alignment
241 * deletes that free block from the free list. */
242 if ( (p_CurrB->end - p_CurrB->base) < alignment)
243 {
244 if ( p_PrevB )
245 p_PrevB->p_Next = p_CurrB->p_Next;
246 else
247 p_MM->freeBlocks[i] = p_CurrB->p_Next;
248 XX_Free(p_CurrB);
249 p_CurrB = NULL;
250 }
251 break;
252 }
253 else
254 {
255 p_PrevB = p_CurrB;
256 p_CurrB = p_CurrB->p_Next;
257 }
258 }
259
260 /* If no free block found to be updated, insert a new free block
261 * to the end of the free list.
262 */
263 if ( !p_CurrB && ((((uint64_t)(end-base)) & ((uint64_t)(alignment-1))) == 0) )
264 {
265 if ((p_NewB = CreateFreeBlock(alignBase, end-base)) == NULL)
266 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
267
268 if (p_PrevB)
269 p_PrevB->p_Next = p_NewB;
270 else
271 p_MM->freeBlocks[i] = p_NewB;
272 }
273
274 /* Update boundaries of the new free block */
275 if ((alignment == 1) && !p_NewB)
276 {
277 if ( p_CurrB && base > p_CurrB->base )
278 base = p_CurrB->base;
279 if ( p_CurrB && end < p_CurrB->end )
280 end = p_CurrB->end;
281 }
282 }
283
284 return (E_OK);
285 }
286
287 /****************************************************************
288 * Routine: CutFree
289 *
290 * Description:
291 * Cuts a free block from holdBase to holdEnd from the free lists.
292 * That is, it updates all free lists of the MM object do
293 * not include a block of memory from holdBase to holdEnd.
294 * For each free lists it seek for a free block that holds
295 * either holdBase or holdEnd. If such block is found it updates it.
296 *
297 * Arguments:
298 * p_MM - pointer to the MM object
299 * holdBase - base address of the allocated block
300 * holdEnd - end address of the allocated block
301 *
302 * Return value:
303 * E_OK is returned on success,
304 * otherwise returns an error code.
305 *
306 ****************************************************************/
CutFree(t_MM * p_MM,uint64_t holdBase,uint64_t holdEnd)307 static t_Error CutFree(t_MM *p_MM, uint64_t holdBase, uint64_t holdEnd)
308 {
309 t_FreeBlock *p_PrevB, *p_CurrB, *p_NewB;
310 uint64_t alignBase, base, end;
311 uint64_t alignment;
312 int i;
313
314 for (i=0; i <= MM_MAX_ALIGNMENT; i++)
315 {
316 p_PrevB = p_NewB = 0;
317 p_CurrB = p_MM->freeBlocks[i];
318
319 alignment = (uint64_t)(0x1 << i);
320 alignBase = MAKE_ALIGNED(holdEnd, alignment);
321
322 while ( p_CurrB )
323 {
324 base = p_CurrB->base;
325 end = p_CurrB->end;
326
327 if ( (holdBase <= base) && (holdEnd <= end) && (holdEnd > base) )
328 {
329 if ( alignBase >= end ||
330 (alignBase < end && ((end-alignBase) < alignment)) )
331 {
332 if (p_PrevB)
333 p_PrevB->p_Next = p_CurrB->p_Next;
334 else
335 p_MM->freeBlocks[i] = p_CurrB->p_Next;
336 XX_Free(p_CurrB);
337 }
338 else
339 {
340 p_CurrB->base = alignBase;
341 }
342 break;
343 }
344 else if ( (holdBase > base) && (holdEnd <= end) )
345 {
346 if ( (holdBase-base) >= alignment )
347 {
348 if ( (alignBase < end) && ((end-alignBase) >= alignment) )
349 {
350 if ((p_NewB = CreateFreeBlock(alignBase, end-alignBase)) == NULL)
351 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
352 p_NewB->p_Next = p_CurrB->p_Next;
353 p_CurrB->p_Next = p_NewB;
354 }
355 p_CurrB->end = holdBase;
356 }
357 else if ( (alignBase < end) && ((end-alignBase) >= alignment) )
358 {
359 p_CurrB->base = alignBase;
360 }
361 else
362 {
363 if (p_PrevB)
364 p_PrevB->p_Next = p_CurrB->p_Next;
365 else
366 p_MM->freeBlocks[i] = p_CurrB->p_Next;
367 XX_Free(p_CurrB);
368 }
369 break;
370 }
371 else
372 {
373 p_PrevB = p_CurrB;
374 p_CurrB = p_CurrB->p_Next;
375 }
376 }
377 }
378
379 return (E_OK);
380 }
381
382 /****************************************************************
383 * Routine: AddBusy
384 *
385 * Description:
386 * Adds a new busy block to the list of busy blocks. Note,
387 * that all busy blocks are ordered by their base address in
388 * the busy list.
389 *
390 * Arguments:
391 * MM - handler to the MM object
392 * p_NewBusyB - pointer to the a busy block
393 *
394 * Return value:
395 * None.
396 *
397 ****************************************************************/
AddBusy(t_MM * p_MM,t_BusyBlock * p_NewBusyB)398 static void AddBusy(t_MM *p_MM, t_BusyBlock *p_NewBusyB)
399 {
400 t_BusyBlock *p_CurrBusyB, *p_PrevBusyB;
401
402 /* finds a place of a new busy block in the list of busy blocks */
403 p_PrevBusyB = 0;
404 p_CurrBusyB = p_MM->busyBlocks;
405
406 while ( p_CurrBusyB && p_NewBusyB->base > p_CurrBusyB->base )
407 {
408 p_PrevBusyB = p_CurrBusyB;
409 p_CurrBusyB = p_CurrBusyB->p_Next;
410 }
411
412 /* insert the new busy block into the list of busy blocks */
413 if ( p_CurrBusyB )
414 p_NewBusyB->p_Next = p_CurrBusyB;
415 if ( p_PrevBusyB )
416 p_PrevBusyB->p_Next = p_NewBusyB;
417 else
418 p_MM->busyBlocks = p_NewBusyB;
419 }
420
421 /****************************************************************
422 * Routine: CutBusy
423 *
424 * Description:
425 * Cuts a block from base to end from the list of busy blocks.
426 * This is done by updating the list of busy blocks do not
427 * include a given block, that block is going to be free. If a
428 * given block is a part of some other busy block, so that
429 * busy block is updated. If there are number of busy blocks
430 * included in the given block, so all that blocks are removed
431 * from the busy list and the end blocks are updated.
432 * If the given block devides some block into two parts, a new
433 * busy block is added to the busy list.
434 *
435 * Arguments:
436 * p_MM - pointer to the MM object
437 * base - base address of a given busy block
438 * end - end address of a given busy block
439 *
440 * Return value:
441 * E_OK on success, E_NOMEMORY otherwise.
442 *
443 ****************************************************************/
CutBusy(t_MM * p_MM,uint64_t base,uint64_t end)444 static t_Error CutBusy(t_MM *p_MM, uint64_t base, uint64_t end)
445 {
446 t_BusyBlock *p_CurrB, *p_PrevB, *p_NewB;
447
448 p_CurrB = p_MM->busyBlocks;
449 p_PrevB = p_NewB = 0;
450
451 while ( p_CurrB )
452 {
453 if ( base < p_CurrB->end )
454 {
455 if ( end > p_CurrB->end )
456 {
457 t_BusyBlock *p_NextB;
458 while ( p_CurrB->p_Next && end >= p_CurrB->p_Next->end )
459 {
460 p_NextB = p_CurrB->p_Next;
461 p_CurrB->p_Next = p_CurrB->p_Next->p_Next;
462 XX_Free(p_NextB);
463 }
464
465 p_NextB = p_CurrB->p_Next;
466 if ( p_NextB && end > p_NextB->base )
467 {
468 p_NextB->base = end;
469 }
470 }
471
472 if ( base <= p_CurrB->base )
473 {
474 if ( end < p_CurrB->end && end > p_CurrB->base )
475 {
476 p_CurrB->base = end;
477 }
478 else if ( end >= p_CurrB->end )
479 {
480 if ( p_PrevB )
481 p_PrevB->p_Next = p_CurrB->p_Next;
482 else
483 p_MM->busyBlocks = p_CurrB->p_Next;
484 XX_Free(p_CurrB);
485 }
486 }
487 else
488 {
489 if ( end < p_CurrB->end && end > p_CurrB->base )
490 {
491 if ((p_NewB = CreateBusyBlock(end,
492 p_CurrB->end-end,
493 p_CurrB->name)) == NULL)
494 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
495 p_NewB->p_Next = p_CurrB->p_Next;
496 p_CurrB->p_Next = p_NewB;
497 }
498 p_CurrB->end = base;
499 }
500 break;
501 }
502 else
503 {
504 p_PrevB = p_CurrB;
505 p_CurrB = p_CurrB->p_Next;
506 }
507 }
508
509 return (E_OK);
510 }
511
512 /****************************************************************
513 * Routine: MmGetGreaterAlignment
514 *
515 * Description:
516 * Allocates a block of memory according to the given size
517 * and the alignment. That routine is called from the MM_Get
518 * routine if the required alignment is greater then MM_MAX_ALIGNMENT.
519 * In that case, it goes over free blocks of 64 byte align list
520 * and checks if it has the required size of bytes of the required
521 * alignment. If no blocks found returns ILLEGAL_BASE.
522 * After the block is found and data is allocated, it calls
523 * the internal CutFree routine to update all free lists
524 * do not include a just allocated block. Of course, each
525 * free list contains a free blocks with the same alignment.
526 * It is also creates a busy block that holds
527 * information about an allocated block.
528 *
529 * Arguments:
530 * MM - handle to the MM object
531 * size - size of the MM
532 * alignment - index as a power of two defines
533 * a required alignment that is greater then 64.
534 * name - the name that specifies an allocated block.
535 *
536 * Return value:
537 * base address of an allocated block.
538 * ILLEGAL_BASE if can't allocate a block
539 *
540 ****************************************************************/
MmGetGreaterAlignment(t_MM * p_MM,uint64_t size,uint64_t alignment,char * name)541 static uint64_t MmGetGreaterAlignment(t_MM *p_MM, uint64_t size, uint64_t alignment, char* name)
542 {
543 t_FreeBlock *p_FreeB;
544 t_BusyBlock *p_NewBusyB;
545 uint64_t holdBase, holdEnd, alignBase = 0;
546
547 /* goes over free blocks of the 64 byte alignment list
548 and look for a block of the suitable size and
549 base address according to the alignment. */
550 p_FreeB = p_MM->freeBlocks[MM_MAX_ALIGNMENT];
551
552 while ( p_FreeB )
553 {
554 alignBase = MAKE_ALIGNED(p_FreeB->base, alignment);
555
556 /* the block is found if the aligned base inside the block
557 * and has the anough size. */
558 if ( alignBase >= p_FreeB->base &&
559 alignBase < p_FreeB->end &&
560 size <= (p_FreeB->end - alignBase) )
561 break;
562 else
563 p_FreeB = p_FreeB->p_Next;
564 }
565
566 /* If such block isn't found */
567 if ( !p_FreeB )
568 return (uint64_t)(ILLEGAL_BASE);
569
570 holdBase = alignBase;
571 holdEnd = alignBase + size;
572
573 /* init a new busy block */
574 if ((p_NewBusyB = CreateBusyBlock(holdBase, size, name)) == NULL)
575 return (uint64_t)(ILLEGAL_BASE);
576
577 /* calls Update routine to update a lists of free blocks */
578 if ( CutFree ( p_MM, holdBase, holdEnd ) != E_OK )
579 {
580 XX_Free(p_NewBusyB);
581 return (uint64_t)(ILLEGAL_BASE);
582 }
583
584 /* insert the new busy block into the list of busy blocks */
585 AddBusy ( p_MM, p_NewBusyB );
586
587 return (holdBase);
588 }
589
590
591 /**********************************************************************
592 * MM API routines set *
593 **********************************************************************/
594
595 /*****************************************************************************/
MM_Init(t_Handle * h_MM,uint64_t base,uint64_t size)596 t_Error MM_Init(t_Handle *h_MM, uint64_t base, uint64_t size)
597 {
598 t_MM *p_MM;
599 uint64_t newBase, newSize;
600 int i;
601
602 if (!size)
603 {
604 RETURN_ERROR(MAJOR, E_INVALID_VALUE, ("Size (should be positive)"));
605 }
606
607 /* Initializes a new MM object */
608 p_MM = (t_MM *)XX_Malloc(sizeof(t_MM));
609 if (!p_MM)
610 {
611 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
612 }
613
614 p_MM->h_Spinlock = XX_InitSpinlock();
615 if (!p_MM->h_Spinlock)
616 {
617 XX_Free(p_MM);
618 RETURN_ERROR(MAJOR, E_NO_MEMORY, ("MM spinlock!"));
619 }
620
621 /* Initializes counter of free memory to total size */
622 p_MM->freeMemSize = size;
623
624 /* A busy list is empty */
625 p_MM->busyBlocks = 0;
626
627 /* Initializes a new memory block */
628 if ((p_MM->memBlocks = CreateNewBlock(base, size)) == NULL)
629 {
630 MM_Free(p_MM);
631 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
632 }
633
634 /* Initializes a new free block for each free list*/
635 for (i=0; i <= MM_MAX_ALIGNMENT; i++)
636 {
637 newBase = MAKE_ALIGNED( base, (0x1 << i) );
638 newSize = size - (newBase - base);
639
640 if ((p_MM->freeBlocks[i] = CreateFreeBlock(newBase, newSize)) == NULL)
641 {
642 MM_Free(p_MM);
643 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
644 }
645 }
646
647 *h_MM = p_MM;
648
649 return (E_OK);
650 }
651
652 /*****************************************************************************/
MM_Free(t_Handle h_MM)653 void MM_Free(t_Handle h_MM)
654 {
655 t_MM *p_MM = (t_MM *)h_MM;
656 t_MemBlock *p_MemBlock;
657 t_BusyBlock *p_BusyBlock;
658 t_FreeBlock *p_FreeBlock;
659 void *p_Block;
660 int i;
661
662 ASSERT_COND(p_MM);
663
664 /* release memory allocated for busy blocks */
665 p_BusyBlock = p_MM->busyBlocks;
666 while ( p_BusyBlock )
667 {
668 p_Block = p_BusyBlock;
669 p_BusyBlock = p_BusyBlock->p_Next;
670 XX_Free(p_Block);
671 }
672
673 /* release memory allocated for free blocks */
674 for (i=0; i <= MM_MAX_ALIGNMENT; i++)
675 {
676 p_FreeBlock = p_MM->freeBlocks[i];
677 while ( p_FreeBlock )
678 {
679 p_Block = p_FreeBlock;
680 p_FreeBlock = p_FreeBlock->p_Next;
681 XX_Free(p_Block);
682 }
683 }
684
685 /* release memory allocated for memory blocks */
686 p_MemBlock = p_MM->memBlocks;
687 while ( p_MemBlock )
688 {
689 p_Block = p_MemBlock;
690 p_MemBlock = p_MemBlock->p_Next;
691 XX_Free(p_Block);
692 }
693
694 if (p_MM->h_Spinlock)
695 XX_FreeSpinlock(p_MM->h_Spinlock);
696
697 /* release memory allocated for MM object itself */
698 XX_Free(p_MM);
699 }
700
701 /*****************************************************************************/
MM_Get(t_Handle h_MM,uint64_t size,uint64_t alignment,char * name)702 uint64_t MM_Get(t_Handle h_MM, uint64_t size, uint64_t alignment, char* name)
703 {
704 t_MM *p_MM = (t_MM *)h_MM;
705 t_FreeBlock *p_FreeB;
706 t_BusyBlock *p_NewBusyB;
707 uint64_t holdBase, holdEnd, j, i = 0;
708 uint32_t intFlags;
709
710 SANITY_CHECK_RETURN_VALUE(p_MM, E_INVALID_HANDLE, (uint64_t)ILLEGAL_BASE);
711
712 /* checks that alignment value is greater then zero */
713 if (alignment == 0)
714 {
715 alignment = 1;
716 }
717
718 j = alignment;
719
720 /* checks if alignment is a power of two, if it correct and if the
721 required size is multiple of the given alignment. */
722 while ((j & 0x1) == 0)
723 {
724 i++;
725 j = j >> 1;
726 }
727
728 /* if the given alignment isn't power of two, returns an error */
729 if (j != 1)
730 {
731 REPORT_ERROR(MAJOR, E_INVALID_VALUE, ("alignment (should be power of 2)"));
732 return (uint64_t)ILLEGAL_BASE;
733 }
734
735 if (i > MM_MAX_ALIGNMENT)
736 {
737 return (MmGetGreaterAlignment(p_MM, size, alignment, name));
738 }
739
740 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock);
741 /* look for a block of the size greater or equal to the required size. */
742 p_FreeB = p_MM->freeBlocks[i];
743 while ( p_FreeB && (p_FreeB->end - p_FreeB->base) < size )
744 p_FreeB = p_FreeB->p_Next;
745
746 /* If such block is found */
747 if ( !p_FreeB )
748 {
749 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
750 return (uint64_t)(ILLEGAL_BASE);
751 }
752
753 holdBase = p_FreeB->base;
754 holdEnd = holdBase + size;
755
756 /* init a new busy block */
757 if ((p_NewBusyB = CreateBusyBlock(holdBase, size, name)) == NULL)
758 {
759 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
760 return (uint64_t)(ILLEGAL_BASE);
761 }
762
763 /* calls Update routine to update a lists of free blocks */
764 if ( CutFree ( p_MM, holdBase, holdEnd ) != E_OK )
765 {
766 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
767 XX_Free(p_NewBusyB);
768 return (uint64_t)(ILLEGAL_BASE);
769 }
770
771 /* Decreasing the allocated memory size from free memory size */
772 p_MM->freeMemSize -= size;
773
774 /* insert the new busy block into the list of busy blocks */
775 AddBusy ( p_MM, p_NewBusyB );
776 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
777
778 return (holdBase);
779 }
780
781 /*****************************************************************************/
MM_GetForce(t_Handle h_MM,uint64_t base,uint64_t size,char * name)782 uint64_t MM_GetForce(t_Handle h_MM, uint64_t base, uint64_t size, char* name)
783 {
784 t_MM *p_MM = (t_MM *)h_MM;
785 t_FreeBlock *p_FreeB;
786 t_BusyBlock *p_NewBusyB;
787 uint32_t intFlags;
788 bool blockIsFree = FALSE;
789
790 ASSERT_COND(p_MM);
791
792 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock);
793 p_FreeB = p_MM->freeBlocks[0]; /* The biggest free blocks are in the
794 free list with alignment 1 */
795
796 while ( p_FreeB )
797 {
798 if ( base >= p_FreeB->base && (base+size) <= p_FreeB->end )
799 {
800 blockIsFree = TRUE;
801 break;
802 }
803 else
804 p_FreeB = p_FreeB->p_Next;
805 }
806
807 if ( !blockIsFree )
808 {
809 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
810 return (uint64_t)(ILLEGAL_BASE);
811 }
812
813 /* init a new busy block */
814 if ((p_NewBusyB = CreateBusyBlock(base, size, name)) == NULL)
815 {
816 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
817 return (uint64_t)(ILLEGAL_BASE);
818 }
819
820 /* calls Update routine to update a lists of free blocks */
821 if ( CutFree ( p_MM, base, base+size ) != E_OK )
822 {
823 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
824 XX_Free(p_NewBusyB);
825 return (uint64_t)(ILLEGAL_BASE);
826 }
827
828 /* Decreasing the allocated memory size from free memory size */
829 p_MM->freeMemSize -= size;
830
831 /* insert the new busy block into the list of busy blocks */
832 AddBusy ( p_MM, p_NewBusyB );
833 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
834
835 return (base);
836 }
837
838 /*****************************************************************************/
MM_GetForceMin(t_Handle h_MM,uint64_t size,uint64_t alignment,uint64_t min,char * name)839 uint64_t MM_GetForceMin(t_Handle h_MM, uint64_t size, uint64_t alignment, uint64_t min, char* name)
840 {
841 t_MM *p_MM = (t_MM *)h_MM;
842 t_FreeBlock *p_FreeB;
843 t_BusyBlock *p_NewBusyB;
844 uint64_t holdBase, holdEnd, j = alignment, i=0;
845 uint32_t intFlags;
846
847 ASSERT_COND(p_MM);
848
849 /* checks if alignment is a power of two, if it correct and if the
850 required size is multiple of the given alignment. */
851 while ((j & 0x1) == 0)
852 {
853 i++;
854 j = j >> 1;
855 }
856
857 if ( (j != 1) || (i > MM_MAX_ALIGNMENT) )
858 {
859 return (uint64_t)(ILLEGAL_BASE);
860 }
861
862 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock);
863 p_FreeB = p_MM->freeBlocks[i];
864
865 /* look for the first block that contains the minimum
866 base address. If the whole required size may be fit
867 into it, use that block, otherwise look for the next
868 block of size greater or equal to the required size. */
869 while ( p_FreeB && (min >= p_FreeB->end))
870 p_FreeB = p_FreeB->p_Next;
871
872 /* If such block is found */
873 if ( !p_FreeB )
874 {
875 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
876 return (uint64_t)(ILLEGAL_BASE);
877 }
878
879 /* if this block is large enough, use this block */
880 holdBase = ( min <= p_FreeB->base ) ? p_FreeB->base : min;
881 if ((holdBase + size) <= p_FreeB->end )
882 {
883 holdEnd = holdBase + size;
884 }
885 else
886 {
887 p_FreeB = p_FreeB->p_Next;
888 while ( p_FreeB && ((p_FreeB->end - p_FreeB->base) < size) )
889 p_FreeB = p_FreeB->p_Next;
890
891 /* If such block is found */
892 if ( !p_FreeB )
893 {
894 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
895 return (uint64_t)(ILLEGAL_BASE);
896 }
897
898 holdBase = p_FreeB->base;
899 holdEnd = holdBase + size;
900 }
901
902 /* init a new busy block */
903 if ((p_NewBusyB = CreateBusyBlock(holdBase, size, name)) == NULL)
904 {
905 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
906 return (uint64_t)(ILLEGAL_BASE);
907 }
908
909 /* calls Update routine to update a lists of free blocks */
910 if ( CutFree( p_MM, holdBase, holdEnd ) != E_OK )
911 {
912 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
913 XX_Free(p_NewBusyB);
914 return (uint64_t)(ILLEGAL_BASE);
915 }
916
917 /* Decreasing the allocated memory size from free memory size */
918 p_MM->freeMemSize -= size;
919
920 /* insert the new busy block into the list of busy blocks */
921 AddBusy( p_MM, p_NewBusyB );
922 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
923
924 return (holdBase);
925 }
926
927 /*****************************************************************************/
MM_Put(t_Handle h_MM,uint64_t base)928 uint64_t MM_Put(t_Handle h_MM, uint64_t base)
929 {
930 t_MM *p_MM = (t_MM *)h_MM;
931 t_BusyBlock *p_BusyB, *p_PrevBusyB;
932 uint64_t size;
933 uint32_t intFlags;
934
935 ASSERT_COND(p_MM);
936
937 /* Look for a busy block that have the given base value.
938 * That block will be returned back to the memory.
939 */
940 p_PrevBusyB = 0;
941
942 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock);
943 p_BusyB = p_MM->busyBlocks;
944 while ( p_BusyB && base != p_BusyB->base )
945 {
946 p_PrevBusyB = p_BusyB;
947 p_BusyB = p_BusyB->p_Next;
948 }
949
950 if ( !p_BusyB )
951 {
952 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
953 return (uint64_t)(0);
954 }
955
956 if ( AddFree( p_MM, p_BusyB->base, p_BusyB->end ) != E_OK )
957 {
958 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
959 return (uint64_t)(0);
960 }
961
962 /* removes a busy block form the list of busy blocks */
963 if ( p_PrevBusyB )
964 p_PrevBusyB->p_Next = p_BusyB->p_Next;
965 else
966 p_MM->busyBlocks = p_BusyB->p_Next;
967
968 size = p_BusyB->end - p_BusyB->base;
969
970 /* Adding the deallocated memory size to free memory size */
971 p_MM->freeMemSize += size;
972
973 XX_Free(p_BusyB);
974 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
975
976 return (size);
977 }
978
979 /*****************************************************************************/
MM_PutForce(t_Handle h_MM,uint64_t base,uint64_t size)980 uint64_t MM_PutForce(t_Handle h_MM, uint64_t base, uint64_t size)
981 {
982 t_MM *p_MM = (t_MM *)h_MM;
983 uint64_t end = base + size;
984 uint32_t intFlags;
985
986 ASSERT_COND(p_MM);
987
988 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock);
989
990 if ( CutBusy( p_MM, base, end ) != E_OK )
991 {
992 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
993 return (uint64_t)(0);
994 }
995
996 if ( AddFree ( p_MM, base, end ) != E_OK )
997 {
998 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
999 return (uint64_t)(0);
1000 }
1001
1002 /* Adding the deallocated memory size to free memory size */
1003 p_MM->freeMemSize += size;
1004
1005 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
1006
1007 return (size);
1008 }
1009
1010 /*****************************************************************************/
MM_Add(t_Handle h_MM,uint64_t base,uint64_t size)1011 t_Error MM_Add(t_Handle h_MM, uint64_t base, uint64_t size)
1012 {
1013 t_MM *p_MM = (t_MM *)h_MM;
1014 t_MemBlock *p_MemB, *p_NewMemB;
1015 t_Error errCode;
1016 uint32_t intFlags;
1017
1018 ASSERT_COND(p_MM);
1019
1020 /* find a last block in the list of memory blocks to insert a new
1021 * memory block
1022 */
1023 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock);
1024
1025 p_MemB = p_MM->memBlocks;
1026 while ( p_MemB->p_Next )
1027 {
1028 if ( base >= p_MemB->base && base < p_MemB->end )
1029 {
1030 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
1031 RETURN_ERROR(MAJOR, E_ALREADY_EXISTS, NO_MSG);
1032 }
1033 p_MemB = p_MemB->p_Next;
1034 }
1035 /* check for a last memory block */
1036 if ( base >= p_MemB->base && base < p_MemB->end )
1037 {
1038 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
1039 RETURN_ERROR(MAJOR, E_ALREADY_EXISTS, NO_MSG);
1040 }
1041
1042 /* create a new memory block */
1043 if ((p_NewMemB = CreateNewBlock(base, size)) == NULL)
1044 {
1045 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
1046 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG);
1047 }
1048
1049 /* append a new memory block to the end of the list of memory blocks */
1050 p_MemB->p_Next = p_NewMemB;
1051
1052 /* add a new free block to the free lists */
1053 errCode = AddFree(p_MM, base, base+size);
1054 if (errCode)
1055 {
1056 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
1057 p_MemB->p_Next = 0;
1058 XX_Free(p_NewMemB);
1059 return ((t_Error)errCode);
1060 }
1061
1062 /* Adding the new block size to free memory size */
1063 p_MM->freeMemSize += size;
1064
1065 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags);
1066
1067 return (E_OK);
1068 }
1069
1070 /*****************************************************************************/
MM_GetMemBlock(t_Handle h_MM,int index)1071 uint64_t MM_GetMemBlock(t_Handle h_MM, int index)
1072 {
1073 t_MM *p_MM = (t_MM*)h_MM;
1074 t_MemBlock *p_MemBlock;
1075 int i;
1076
1077 ASSERT_COND(p_MM);
1078
1079 p_MemBlock = p_MM->memBlocks;
1080 for (i=0; i < index; i++)
1081 p_MemBlock = p_MemBlock->p_Next;
1082
1083 if ( p_MemBlock )
1084 return (p_MemBlock->base);
1085 else
1086 return (uint64_t)ILLEGAL_BASE;
1087 }
1088
1089 /*****************************************************************************/
MM_GetBase(t_Handle h_MM)1090 uint64_t MM_GetBase(t_Handle h_MM)
1091 {
1092 t_MM *p_MM = (t_MM*)h_MM;
1093 t_MemBlock *p_MemBlock;
1094
1095 ASSERT_COND(p_MM);
1096
1097 p_MemBlock = p_MM->memBlocks;
1098 return p_MemBlock->base;
1099 }
1100
1101 /*****************************************************************************/
MM_InRange(t_Handle h_MM,uint64_t addr)1102 bool MM_InRange(t_Handle h_MM, uint64_t addr)
1103 {
1104 t_MM *p_MM = (t_MM*)h_MM;
1105 t_MemBlock *p_MemBlock;
1106
1107 ASSERT_COND(p_MM);
1108
1109 p_MemBlock = p_MM->memBlocks;
1110
1111 if ((addr >= p_MemBlock->base) && (addr < p_MemBlock->end))
1112 return TRUE;
1113 else
1114 return FALSE;
1115 }
1116
1117 /*****************************************************************************/
MM_GetFreeMemSize(t_Handle h_MM)1118 uint64_t MM_GetFreeMemSize(t_Handle h_MM)
1119 {
1120 t_MM *p_MM = (t_MM*)h_MM;
1121
1122 ASSERT_COND(p_MM);
1123
1124 return p_MM->freeMemSize;
1125 }
1126
1127 /*****************************************************************************/
MM_Dump(t_Handle h_MM)1128 void MM_Dump(t_Handle h_MM)
1129 {
1130 t_MM *p_MM = (t_MM *)h_MM;
1131 t_FreeBlock *p_FreeB;
1132 t_BusyBlock *p_BusyB;
1133 int i;
1134
1135 p_BusyB = p_MM->busyBlocks;
1136 XX_Print("List of busy blocks:\n");
1137 while (p_BusyB)
1138 {
1139 XX_Print("\t0x%p: (%s: b=0x%llx, e=0x%llx)\n", p_BusyB, p_BusyB->name, p_BusyB->base, p_BusyB->end );
1140 p_BusyB = p_BusyB->p_Next;
1141 }
1142
1143 XX_Print("\nLists of free blocks according to alignment:\n");
1144 for (i=0; i <= MM_MAX_ALIGNMENT; i++)
1145 {
1146 XX_Print("%d alignment:\n", (0x1 << i));
1147 p_FreeB = p_MM->freeBlocks[i];
1148 while (p_FreeB)
1149 {
1150 XX_Print("\t0x%p: (b=0x%llx, e=0x%llx)\n", p_FreeB, p_FreeB->base, p_FreeB->end);
1151 p_FreeB = p_FreeB->p_Next;
1152 }
1153 XX_Print("\n");
1154 }
1155 }
1156