sys/contrib/ncsw/etc/mm.c

   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 }