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 ****************************************************************/ 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 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 ****************************************************************/ 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 ****************************************************************/ 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 ****************************************************************/ 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 ****************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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 /*****************************************************************************/ 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