1 /* Copyright (c) 2008-2011 Freescale Semiconductor, Inc. 2 * All rights reserved. 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 #include "string_ext.h" 34 #include "error_ext.h" 35 #include "std_ext.h" 36 #include "sprint_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 ****************************************************************/ 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 ****************************************************************/ 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 ****************************************************************/ 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 ****************************************************************/ 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 } 250 break; 251 } 252 else 253 { 254 p_PrevB = p_CurrB; 255 p_CurrB = p_CurrB->p_Next; 256 } 257 } 258 259 /* If no free block found to be updated, insert a new free block 260 * to the end of the free list. 261 */ 262 if ( !p_CurrB && ((((uint64_t)(end-base)) & ((uint64_t)(alignment-1))) == 0) ) 263 { 264 if ((p_NewB = CreateFreeBlock(alignBase, end-base)) == NULL) 265 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG); 266 267 if (p_PrevB) 268 p_PrevB->p_Next = p_NewB; 269 else 270 p_MM->freeBlocks[i] = p_NewB; 271 } 272 273 /* Update boundaries of the new free block */ 274 if ((alignment == 1) && !p_NewB) 275 { 276 if ( p_CurrB && base > p_CurrB->base ) 277 base = p_CurrB->base; 278 if ( p_CurrB && end < p_CurrB->end ) 279 end = p_CurrB->end; 280 } 281 } 282 283 return (E_OK); 284 } 285 286 /**************************************************************** 287 * Routine: CutFree 288 * 289 * Description: 290 * Cuts a free block from holdBase to holdEnd from the free lists. 291 * That is, it updates all free lists of the MM object do 292 * not include a block of memory from holdBase to holdEnd. 293 * For each free lists it seek for a free block that holds 294 * either holdBase or holdEnd. If such block is found it updates it. 295 * 296 * Arguments: 297 * p_MM - pointer to the MM object 298 * holdBase - base address of the allocated block 299 * holdEnd - end address of the allocated block 300 * 301 * Return value: 302 * E_OK is returned on success, 303 * otherwise returns an error code. 304 * 305 ****************************************************************/ 306 static t_Error CutFree(t_MM *p_MM, uint64_t holdBase, uint64_t holdEnd) 307 { 308 t_FreeBlock *p_PrevB, *p_CurrB, *p_NewB; 309 uint64_t alignBase, base, end; 310 uint64_t alignment; 311 int i; 312 313 for (i=0; i <= MM_MAX_ALIGNMENT; i++) 314 { 315 p_PrevB = p_NewB = 0; 316 p_CurrB = p_MM->freeBlocks[i]; 317 318 alignment = (uint64_t)(0x1 << i); 319 alignBase = MAKE_ALIGNED(holdEnd, alignment); 320 321 while ( p_CurrB ) 322 { 323 base = p_CurrB->base; 324 end = p_CurrB->end; 325 326 if ( (holdBase <= base) && (holdEnd <= end) && (holdEnd > base) ) 327 { 328 if ( alignBase >= end || 329 (alignBase < end && ((end-alignBase) < alignment)) ) 330 { 331 if (p_PrevB) 332 p_PrevB->p_Next = p_CurrB->p_Next; 333 else 334 p_MM->freeBlocks[i] = p_CurrB->p_Next; 335 XX_Free(p_CurrB); 336 } 337 else 338 { 339 p_CurrB->base = alignBase; 340 } 341 break; 342 } 343 else if ( (holdBase > base) && (holdEnd <= end) ) 344 { 345 if ( (holdBase-base) >= alignment ) 346 { 347 if ( (alignBase < end) && ((end-alignBase) >= alignment) ) 348 { 349 if ((p_NewB = CreateFreeBlock(alignBase, end-alignBase)) == NULL) 350 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG); 351 p_NewB->p_Next = p_CurrB->p_Next; 352 p_CurrB->p_Next = p_NewB; 353 } 354 p_CurrB->end = holdBase; 355 } 356 else if ( (alignBase < end) && ((end-alignBase) >= alignment) ) 357 { 358 p_CurrB->base = alignBase; 359 } 360 else 361 { 362 if (p_PrevB) 363 p_PrevB->p_Next = p_CurrB->p_Next; 364 else 365 p_MM->freeBlocks[i] = p_CurrB->p_Next; 366 XX_Free(p_CurrB); 367 } 368 break; 369 } 370 else 371 { 372 p_PrevB = p_CurrB; 373 p_CurrB = p_CurrB->p_Next; 374 } 375 } 376 } 377 378 return (E_OK); 379 } 380 381 /**************************************************************** 382 * Routine: AddBusy 383 * 384 * Description: 385 * Adds a new busy block to the list of busy blocks. Note, 386 * that all busy blocks are ordered by their base address in 387 * the busy list. 388 * 389 * Arguments: 390 * MM - handler to the MM object 391 * p_NewBusyB - pointer to the a busy block 392 * 393 * Return value: 394 * None. 395 * 396 ****************************************************************/ 397 static void AddBusy(t_MM *p_MM, t_BusyBlock *p_NewBusyB) 398 { 399 t_BusyBlock *p_CurrBusyB, *p_PrevBusyB; 400 401 /* finds a place of a new busy block in the list of busy blocks */ 402 p_PrevBusyB = 0; 403 p_CurrBusyB = p_MM->busyBlocks; 404 405 while ( p_CurrBusyB && p_NewBusyB->base > p_CurrBusyB->base ) 406 { 407 p_PrevBusyB = p_CurrBusyB; 408 p_CurrBusyB = p_CurrBusyB->p_Next; 409 } 410 411 /* insert the new busy block into the list of busy blocks */ 412 if ( p_CurrBusyB ) 413 p_NewBusyB->p_Next = p_CurrBusyB; 414 if ( p_PrevBusyB ) 415 p_PrevBusyB->p_Next = p_NewBusyB; 416 else 417 p_MM->busyBlocks = p_NewBusyB; 418 } 419 420 /**************************************************************** 421 * Routine: CutBusy 422 * 423 * Description: 424 * Cuts a block from base to end from the list of busy blocks. 425 * This is done by updating the list of busy blocks do not 426 * include a given block, that block is going to be free. If a 427 * given block is a part of some other busy block, so that 428 * busy block is updated. If there are number of busy blocks 429 * included in the given block, so all that blocks are removed 430 * from the busy list and the end blocks are updated. 431 * If the given block devides some block into two parts, a new 432 * busy block is added to the busy list. 433 * 434 * Arguments: 435 * p_MM - pointer to the MM object 436 * base - base address of a given busy block 437 * end - end address of a given busy block 438 * 439 * Return value: 440 * E_OK on success, E_NOMEMORY otherwise. 441 * 442 ****************************************************************/ 443 static t_Error CutBusy(t_MM *p_MM, uint64_t base, uint64_t end) 444 { 445 t_BusyBlock *p_CurrB, *p_PrevB, *p_NewB; 446 447 p_CurrB = p_MM->busyBlocks; 448 p_PrevB = p_NewB = 0; 449 450 while ( p_CurrB ) 451 { 452 if ( base < p_CurrB->end ) 453 { 454 if ( end > p_CurrB->end ) 455 { 456 t_BusyBlock *p_NextB; 457 while ( p_CurrB->p_Next && end >= p_CurrB->p_Next->end ) 458 { 459 p_NextB = p_CurrB->p_Next; 460 p_CurrB->p_Next = p_CurrB->p_Next->p_Next; 461 XX_Free(p_NextB); 462 } 463 464 p_NextB = p_CurrB->p_Next; 465 if ( p_NextB && end > p_NextB->base ) 466 { 467 p_NextB->base = end; 468 } 469 } 470 471 if ( base <= p_CurrB->base ) 472 { 473 if ( end < p_CurrB->end && end > p_CurrB->base ) 474 { 475 p_CurrB->base = end; 476 } 477 else if ( end >= p_CurrB->end ) 478 { 479 if ( p_PrevB ) 480 p_PrevB->p_Next = p_CurrB->p_Next; 481 else 482 p_MM->busyBlocks = p_CurrB->p_Next; 483 XX_Free(p_CurrB); 484 } 485 } 486 else 487 { 488 if ( end < p_CurrB->end && end > p_CurrB->base ) 489 { 490 if ((p_NewB = CreateBusyBlock(end, 491 p_CurrB->end-end, 492 p_CurrB->name)) == NULL) 493 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG); 494 p_NewB->p_Next = p_CurrB->p_Next; 495 p_CurrB->p_Next = p_NewB; 496 } 497 p_CurrB->end = base; 498 } 499 break; 500 } 501 else 502 { 503 p_PrevB = p_CurrB; 504 p_CurrB = p_CurrB->p_Next; 505 } 506 } 507 508 return (E_OK); 509 } 510 511 /**************************************************************** 512 * Routine: MmGetGreaterAlignment 513 * 514 * Description: 515 * Allocates a block of memory according to the given size 516 * and the alignment. That routine is called from the MM_Get 517 * routine if the required alignment is greater then MM_MAX_ALIGNMENT. 518 * In that case, it goes over free blocks of 64 byte align list 519 * and checks if it has the required size of bytes of the required 520 * alignment. If no blocks found returns ILLEGAL_BASE. 521 * After the block is found and data is allocated, it calls 522 * the internal CutFree routine to update all free lists 523 * do not include a just allocated block. Of course, each 524 * free list contains a free blocks with the same alignment. 525 * It is also creates a busy block that holds 526 * information about an allocated block. 527 * 528 * Arguments: 529 * MM - handle to the MM object 530 * size - size of the MM 531 * alignment - index as a power of two defines 532 * a required alignment that is greater then 64. 533 * name - the name that specifies an allocated block. 534 * 535 * Return value: 536 * base address of an allocated block. 537 * ILLEGAL_BASE if can't allocate a block 538 * 539 ****************************************************************/ 540 static uint64_t MmGetGreaterAlignment(t_MM *p_MM, uint64_t size, uint64_t alignment, char* name) 541 { 542 t_FreeBlock *p_FreeB; 543 t_BusyBlock *p_NewBusyB; 544 uint64_t holdBase, holdEnd, alignBase = 0; 545 546 /* goes over free blocks of the 64 byte alignment list 547 and look for a block of the suitable size and 548 base address according to the alignment. */ 549 p_FreeB = p_MM->freeBlocks[MM_MAX_ALIGNMENT]; 550 551 while ( p_FreeB ) 552 { 553 alignBase = MAKE_ALIGNED(p_FreeB->base, alignment); 554 555 /* the block is found if the aligned base inside the block 556 * and has the anough size. */ 557 if ( alignBase >= p_FreeB->base && 558 alignBase < p_FreeB->end && 559 size <= (p_FreeB->end - alignBase) ) 560 break; 561 else 562 p_FreeB = p_FreeB->p_Next; 563 } 564 565 /* If such block isn't found */ 566 if ( !p_FreeB ) 567 return (uint64_t)(ILLEGAL_BASE); 568 569 holdBase = alignBase; 570 holdEnd = alignBase + size; 571 572 /* init a new busy block */ 573 if ((p_NewBusyB = CreateBusyBlock(holdBase, size, name)) == NULL) 574 return (uint64_t)(ILLEGAL_BASE); 575 576 /* calls Update routine to update a lists of free blocks */ 577 if ( CutFree ( p_MM, holdBase, holdEnd ) != E_OK ) 578 return (uint64_t)(ILLEGAL_BASE); 579 580 /* insert the new busy block into the list of busy blocks */ 581 AddBusy ( p_MM, p_NewBusyB ); 582 583 return (holdBase); 584 } 585 586 587 /********************************************************************** 588 * MM API routines set * 589 **********************************************************************/ 590 591 /*****************************************************************************/ 592 t_Error MM_Init(t_Handle *h_MM, uint64_t base, uint64_t size) 593 { 594 t_MM *p_MM; 595 uint64_t newBase, newSize; 596 int i; 597 598 if (!size) 599 { 600 RETURN_ERROR(MAJOR, E_INVALID_VALUE, ("Size (should be positive)")); 601 } 602 603 /* Initializes a new MM object */ 604 p_MM = (t_MM *)XX_Malloc(sizeof(t_MM)); 605 if (!p_MM) 606 { 607 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG); 608 } 609 610 p_MM->h_Spinlock = XX_InitSpinlock(); 611 if (!p_MM->h_Spinlock) 612 { 613 XX_Free(p_MM); 614 RETURN_ERROR(MAJOR, E_NO_MEMORY, ("MM spinlock!")); 615 } 616 617 /* initializes a new memory block */ 618 if ((p_MM->memBlocks = CreateNewBlock(base, size)) == NULL) 619 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG); 620 621 /* A busy list is empty */ 622 p_MM->busyBlocks = 0; 623 624 /*Initializes a new free block for each free list*/ 625 for (i=0; i <= MM_MAX_ALIGNMENT; i++) 626 { 627 newBase = MAKE_ALIGNED( base, (0x1 << i) ); 628 newSize = size - (newBase - base); 629 630 if ((p_MM->freeBlocks[i] = CreateFreeBlock(newBase, newSize)) == NULL) 631 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG); 632 } 633 634 *h_MM = p_MM; 635 636 return (E_OK); 637 } 638 639 /*****************************************************************************/ 640 void MM_Free(t_Handle h_MM) 641 { 642 t_MM *p_MM = (t_MM *)h_MM; 643 t_MemBlock *p_MemBlock; 644 t_BusyBlock *p_BusyBlock; 645 t_FreeBlock *p_FreeBlock; 646 void *p_Block; 647 int i; 648 649 ASSERT_COND(p_MM); 650 651 /* release memory allocated for busy blocks */ 652 p_BusyBlock = p_MM->busyBlocks; 653 while ( p_BusyBlock ) 654 { 655 p_Block = p_BusyBlock; 656 p_BusyBlock = p_BusyBlock->p_Next; 657 XX_Free(p_Block); 658 } 659 660 /* release memory allocated for free blocks */ 661 for (i=0; i <= MM_MAX_ALIGNMENT; i++) 662 { 663 p_FreeBlock = p_MM->freeBlocks[i]; 664 while ( p_FreeBlock ) 665 { 666 p_Block = p_FreeBlock; 667 p_FreeBlock = p_FreeBlock->p_Next; 668 XX_Free(p_Block); 669 } 670 } 671 672 /* release memory allocated for memory blocks */ 673 p_MemBlock = p_MM->memBlocks; 674 while ( p_MemBlock ) 675 { 676 p_Block = p_MemBlock; 677 p_MemBlock = p_MemBlock->p_Next; 678 XX_Free(p_Block); 679 } 680 681 if (p_MM->h_Spinlock) 682 XX_FreeSpinlock(p_MM->h_Spinlock); 683 684 /* release memory allocated for MM object itself */ 685 XX_Free(p_MM); 686 } 687 688 /*****************************************************************************/ 689 uint64_t MM_Get(t_Handle h_MM, uint64_t size, uint64_t alignment, char* name) 690 { 691 t_MM *p_MM = (t_MM *)h_MM; 692 t_FreeBlock *p_FreeB; 693 t_BusyBlock *p_NewBusyB; 694 uint64_t holdBase, holdEnd, j, i = 0; 695 uint32_t intFlags; 696 697 SANITY_CHECK_RETURN_VALUE(p_MM, E_INVALID_HANDLE, (uint64_t)ILLEGAL_BASE); 698 699 /* checks that alignment value is greater then zero */ 700 if (alignment == 0) 701 { 702 alignment = 1; 703 } 704 705 j = alignment; 706 707 /* checks if alignment is a power of two, if it correct and if the 708 required size is multiple of the given alignment. */ 709 while ((j & 0x1) == 0) 710 { 711 i++; 712 j = j >> 1; 713 } 714 715 /* if the given alignment isn't power of two, returns an error */ 716 if (j != 1) 717 { 718 REPORT_ERROR(MAJOR, E_INVALID_VALUE, ("alignment (should be power of 2)")); 719 return (uint64_t)ILLEGAL_BASE; 720 } 721 722 if (i > MM_MAX_ALIGNMENT) 723 { 724 return (MmGetGreaterAlignment(p_MM, size, alignment, name)); 725 } 726 727 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock); 728 /* look for a block of the size greater or equal to the required size. */ 729 p_FreeB = p_MM->freeBlocks[i]; 730 while ( p_FreeB && (p_FreeB->end - p_FreeB->base) < size ) 731 p_FreeB = p_FreeB->p_Next; 732 733 /* If such block is found */ 734 if ( !p_FreeB ) 735 { 736 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 737 return (uint64_t)(ILLEGAL_BASE); 738 } 739 740 holdBase = p_FreeB->base; 741 holdEnd = holdBase + size; 742 743 /* init a new busy block */ 744 if ((p_NewBusyB = CreateBusyBlock(holdBase, size, name)) == NULL) 745 { 746 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 747 return (uint64_t)(ILLEGAL_BASE); 748 } 749 750 /* calls Update routine to update a lists of free blocks */ 751 if ( CutFree ( p_MM, holdBase, holdEnd ) != E_OK ) 752 { 753 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 754 return (uint64_t)(ILLEGAL_BASE); 755 } 756 757 /* insert the new busy block into the list of busy blocks */ 758 AddBusy ( p_MM, p_NewBusyB ); 759 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 760 761 return (holdBase); 762 } 763 764 /*****************************************************************************/ 765 uint64_t MM_GetForce(t_Handle h_MM, uint64_t base, uint64_t size, char* name) 766 { 767 t_MM *p_MM = (t_MM *)h_MM; 768 t_FreeBlock *p_FreeB; 769 t_BusyBlock *p_NewBusyB; 770 uint32_t intFlags; 771 bool blockIsFree = FALSE; 772 773 ASSERT_COND(p_MM); 774 775 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock); 776 p_FreeB = p_MM->freeBlocks[0]; /* The biggest free blocks are in the 777 free list with alignment 1 */ 778 779 while ( p_FreeB ) 780 { 781 if ( base >= p_FreeB->base && (base+size) <= p_FreeB->end ) 782 { 783 blockIsFree = TRUE; 784 break; 785 } 786 else 787 p_FreeB = p_FreeB->p_Next; 788 } 789 790 if ( !blockIsFree ) 791 { 792 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 793 return (uint64_t)(ILLEGAL_BASE); 794 } 795 796 /* init a new busy block */ 797 if ((p_NewBusyB = CreateBusyBlock(base, size, name)) == NULL) 798 { 799 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 800 return (uint64_t)(ILLEGAL_BASE); 801 } 802 803 /* calls Update routine to update a lists of free blocks */ 804 if ( CutFree ( p_MM, base, base+size ) != E_OK ) 805 { 806 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 807 return (uint64_t)(ILLEGAL_BASE); 808 } 809 810 /* insert the new busy block into the list of busy blocks */ 811 AddBusy ( p_MM, p_NewBusyB ); 812 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 813 814 return (base); 815 } 816 817 /*****************************************************************************/ 818 uint64_t MM_GetForceMin(t_Handle h_MM, uint64_t size, uint64_t alignment, uint64_t min, char* name) 819 { 820 t_MM *p_MM = (t_MM *)h_MM; 821 t_FreeBlock *p_FreeB; 822 t_BusyBlock *p_NewBusyB; 823 uint64_t holdBase, holdEnd, j = alignment, i=0; 824 uint32_t intFlags; 825 826 ASSERT_COND(p_MM); 827 828 /* checks if alignment is a power of two, if it correct and if the 829 required size is multiple of the given alignment. */ 830 while ((j & 0x1) == 0) 831 { 832 i++; 833 j = j >> 1; 834 } 835 836 if ( (j != 1) || (i > MM_MAX_ALIGNMENT) ) 837 { 838 return (uint64_t)(ILLEGAL_BASE); 839 } 840 841 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock); 842 p_FreeB = p_MM->freeBlocks[i]; 843 844 /* look for the first block that contains the minimum 845 base address. If the whole required size may be fit 846 into it, use that block, otherwise look for the next 847 block of size greater or equal to the required size. */ 848 while ( p_FreeB && (min >= p_FreeB->end)) 849 p_FreeB = p_FreeB->p_Next; 850 851 /* If such block is found */ 852 if ( !p_FreeB ) 853 { 854 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 855 return (uint64_t)(ILLEGAL_BASE); 856 } 857 858 /* if this block is large enough, use this block */ 859 holdBase = ( min <= p_FreeB->base ) ? p_FreeB->base : min; 860 if ((holdBase + size) <= p_FreeB->end ) 861 { 862 holdEnd = holdBase + size; 863 } 864 else 865 { 866 p_FreeB = p_FreeB->p_Next; 867 while ( p_FreeB && ((p_FreeB->end - p_FreeB->base) < size) ) 868 p_FreeB = p_FreeB->p_Next; 869 870 /* If such block is found */ 871 if ( !p_FreeB ) 872 { 873 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 874 return (uint64_t)(ILLEGAL_BASE); 875 } 876 877 holdBase = p_FreeB->base; 878 holdEnd = holdBase + size; 879 } 880 881 /* init a new busy block */ 882 if ((p_NewBusyB = CreateBusyBlock(holdBase, size, name)) == NULL) 883 { 884 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 885 return (uint64_t)(ILLEGAL_BASE); 886 } 887 888 /* calls Update routine to update a lists of free blocks */ 889 if ( CutFree( p_MM, holdBase, holdEnd ) != E_OK ) 890 { 891 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 892 return (uint64_t)(ILLEGAL_BASE); 893 } 894 895 /* insert the new busy block into the list of busy blocks */ 896 AddBusy( p_MM, p_NewBusyB ); 897 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 898 899 return (holdBase); 900 } 901 902 /*****************************************************************************/ 903 uint64_t MM_Put(t_Handle h_MM, uint64_t base) 904 { 905 t_MM *p_MM = (t_MM *)h_MM; 906 t_BusyBlock *p_BusyB, *p_PrevBusyB; 907 uint64_t size; 908 uint32_t intFlags; 909 910 ASSERT_COND(p_MM); 911 912 /* Look for a busy block that have the given base value. 913 * That block will be returned back to the memory. 914 */ 915 p_PrevBusyB = 0; 916 917 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock); 918 p_BusyB = p_MM->busyBlocks; 919 while ( p_BusyB && base != p_BusyB->base ) 920 { 921 p_PrevBusyB = p_BusyB; 922 p_BusyB = p_BusyB->p_Next; 923 } 924 925 if ( !p_BusyB ) 926 { 927 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 928 return (uint64_t)(0); 929 } 930 931 if ( AddFree( p_MM, p_BusyB->base, p_BusyB->end ) != E_OK ) 932 { 933 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 934 return (uint64_t)(0); 935 } 936 937 /* removes a busy block form the list of busy blocks */ 938 if ( p_PrevBusyB ) 939 p_PrevBusyB->p_Next = p_BusyB->p_Next; 940 else 941 p_MM->busyBlocks = p_BusyB->p_Next; 942 943 size = p_BusyB->end - p_BusyB->base; 944 945 XX_Free(p_BusyB); 946 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 947 948 return (size); 949 } 950 951 /*****************************************************************************/ 952 uint64_t MM_PutForce(t_Handle h_MM, uint64_t base, uint64_t size) 953 { 954 t_MM *p_MM = (t_MM *)h_MM; 955 uint64_t end = base + size; 956 uint32_t intFlags; 957 958 ASSERT_COND(p_MM); 959 960 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock); 961 if ( CutBusy( p_MM, base, end ) != E_OK ) 962 { 963 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 964 return (uint64_t)(0); 965 } 966 967 if ( AddFree ( p_MM, base, end ) != E_OK ) 968 { 969 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 970 return (uint64_t)(0); 971 } 972 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 973 974 return (size); 975 } 976 977 /*****************************************************************************/ 978 t_Error MM_Add(t_Handle h_MM, uint64_t base, uint64_t size) 979 { 980 t_MM *p_MM = (t_MM *)h_MM; 981 t_MemBlock *p_MemB, *p_NewMemB; 982 t_Error errCode; 983 uint32_t intFlags; 984 985 ASSERT_COND(p_MM); 986 987 /* find a last block in the list of memory blocks to insert a new 988 * memory block 989 */ 990 intFlags = XX_LockIntrSpinlock(p_MM->h_Spinlock); 991 p_MemB = p_MM->memBlocks; 992 while ( p_MemB->p_Next ) 993 { 994 if ( base >= p_MemB->base && base < p_MemB->end ) 995 { 996 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 997 RETURN_ERROR(MAJOR, E_ALREADY_EXISTS, NO_MSG); 998 } 999 p_MemB = p_MemB->p_Next; 1000 } 1001 /* check for a last memory block */ 1002 if ( base >= p_MemB->base && base < p_MemB->end ) 1003 { 1004 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 1005 RETURN_ERROR(MAJOR, E_ALREADY_EXISTS, NO_MSG); 1006 } 1007 1008 /* create a new memory block */ 1009 if ((p_NewMemB = CreateNewBlock(base, size)) == NULL) 1010 { 1011 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 1012 RETURN_ERROR(MAJOR, E_NO_MEMORY, NO_MSG); 1013 } 1014 1015 /* append a new memory block to the end of the list of memory blocks */ 1016 p_MemB->p_Next = p_NewMemB; 1017 1018 /* add a new free block to the free lists */ 1019 errCode = AddFree(p_MM, base, base+size); 1020 if (errCode) 1021 { 1022 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 1023 p_MemB->p_Next = 0; 1024 XX_Free(p_NewMemB); 1025 return ((t_Error)errCode); 1026 } 1027 XX_UnlockIntrSpinlock(p_MM->h_Spinlock, intFlags); 1028 1029 return (E_OK); 1030 } 1031 1032 /*****************************************************************************/ 1033 uint64_t MM_GetMemBlock(t_Handle h_MM, int index) 1034 { 1035 t_MM *p_MM = (t_MM*)h_MM; 1036 t_MemBlock *p_MemBlock; 1037 int i; 1038 1039 ASSERT_COND(p_MM); 1040 1041 p_MemBlock = p_MM->memBlocks; 1042 for (i=0; i < index; i++) 1043 p_MemBlock = p_MemBlock->p_Next; 1044 1045 if ( p_MemBlock ) 1046 return (p_MemBlock->base); 1047 else 1048 return (uint64_t)ILLEGAL_BASE; 1049 } 1050 1051 /*****************************************************************************/ 1052 uint64_t MM_GetBase(t_Handle h_MM) 1053 { 1054 t_MM *p_MM = (t_MM*)h_MM; 1055 t_MemBlock *p_MemBlock; 1056 1057 ASSERT_COND(p_MM); 1058 1059 p_MemBlock = p_MM->memBlocks; 1060 return p_MemBlock->base; 1061 } 1062 1063 /*****************************************************************************/ 1064 bool MM_InRange(t_Handle h_MM, uint64_t addr) 1065 { 1066 t_MM *p_MM = (t_MM*)h_MM; 1067 t_MemBlock *p_MemBlock; 1068 1069 ASSERT_COND(p_MM); 1070 1071 p_MemBlock = p_MM->memBlocks; 1072 1073 if ((addr >= p_MemBlock->base) && (addr < p_MemBlock->end)) 1074 return TRUE; 1075 else 1076 return FALSE; 1077 } 1078 1079 /*****************************************************************************/ 1080 void MM_Dump(t_Handle h_MM, void *buff) 1081 { 1082 t_MM *p_MM = (t_MM *)h_MM; 1083 t_FreeBlock *p_FreeB; 1084 t_BusyBlock *p_BusyB; 1085 int i; 1086 1087 p_BusyB = p_MM->busyBlocks; 1088 Sprint(buff, "List of busy blocks:\n"); 1089 while (p_BusyB) 1090 { 1091 Sprint(buff, "\t0x%p: (%s: b=0x%lx, e=0x%lx)\n", 1092 p_BusyB, p_BusyB->name, p_BusyB->base, p_BusyB->end ); 1093 p_BusyB = p_BusyB->p_Next; 1094 } 1095 1096 Sprint(buff, "\nLists of free blocks according to alignment:\n"); 1097 for (i=0; i <= MM_MAX_ALIGNMENT; i++) 1098 { 1099 Sprint(buff, "%d alignment:\n", (0x1 << i)); 1100 p_FreeB = p_MM->freeBlocks[i]; 1101 while (p_FreeB) 1102 { 1103 Sprint(buff, "\t0x%p: (b=0x%lx, e=0x%lx)\n", 1104 p_FreeB, p_FreeB->base, p_FreeB->end); 1105 p_FreeB = p_FreeB->p_Next; 1106 } 1107 Sprint(buff, "\n"); 1108 } 1109 } 1110