gonzui

    1: /*
    2:  *----------------------------------------------------------------------
    3:  *    T-Kernel 2.0 Software Package
    4:  *
    5:  *    Copyright 2011 by Ken Sakamura.
    6:  *    This software is distributed under the latest version of T-License 2.x.
    7:  *----------------------------------------------------------------------
    8:  *
    9:  *    Released by T-Engine Forum(http://www.t-engine.org/) at 2011/05/17.
   10:  *    Modified by T-Engine Forum at 2014/09/10.
   11:  *    Modified by TRON Forum(http://www.tron.org/) at 2015/06/01.
   12:  *
   13:  *----------------------------------------------------------------------
   14:  */
   15: 
   16: /*
   17:  *      @(#)memalloc.c (libtk)
   18:  *
   19:  *      Memory allocation library
   20:  *
   21:  *      Redivides memory obtained in block units for allocation.
   22:  *      Must be reentrant
   23:  */
   24: 
   25: #include "mem.h"
   26: 
   27: /*
   28:  * Minimum fragment size
   29:  *      A size smaller than 'sizeof(QUEUE) * 2' will result in malfunction.
   30:  */
   31: EXPORT size_t _mem_minfragment = sizeof(QUEUE) * 2;
   32: 
   33: /*
   34:  * Memory allocation check function
   35:  */
   36: EXPORT BOOL (*_mem_chkalloc)( void *ptr, int mode, MACB *macb );
   37: 
   38: #define chkalloc        (*_mem_chkalloc)
   39: 
   40: /*
   41:  * Byte size -->  number of pages
   42:  */
   43: Inline size_t toPageCount( size_t size, MACB *macb )
   44: {
   45:         return (size + (macb->pagesz-1)) / macb->pagesz;
   46: }
   47: 
   48: /*
   49:  * Free queue search
   50:  *      Searches for a free space with the same size as 'size' or
   51:  *      the next largest.
   52:  *      If none is found, returns &freeque.
   53:  */
   54: LOCAL QUEUE* searchFreeArea( size_t size, MACB *macb )
   55: {
   56:         QUEUE  *q = &macb->freeque;
   57: 
   58:         /*
   59:          * Areas up to 1/4 of page size are searched starting
   60:          * from the smallest;
   61:          * others are searched starting from the largest.
   62:          */
   63:         if ( size > macb->pagesz / 4 ) {
   64:                 /* Searches in order of increasing size */
   65:                 size_t fsz = 0;
   66:                 while ( (q = q->prev) != &macb->freeque ) {
   67:                         fsz = (size_t)FreeSize(q);
   68:                         if ( fsz <= size ) {
   69:                                 return ( fsz < size )? q->next: q;
   70:                         }
   71:                 }
   72:                 return ( fsz >= size )? q->next: q;
   73:         } else {
   74:                 /* Searches in order of decreasing size */
   75:                 while ( (q = q->next) != &macb->freeque ) {
   76:                         if ( (size_t)FreeSize(q) >= size ) {
   77:                                 break;
   78:                         }
   79:                 }
   80:                 return q;
   81:         }
   82: }
   83: 
   84: /*
   85:  * Registration in free space free queue
   86:  *      Free queue comprises a two-tier structure: a queue linking
   87:  *      areas of differing size in order of size, and a queue
   88:  *      linking areas that are the same size.
   89:  *
   90:  *     macb->freeque
   91:  *      |
   92:  *      |   +-----------------------+                +-----------------------+
   93:  *      |   | AreaQue                    |         | AreaQue              |
   94:  *      |   +-----------------------+                +-----------------------+
   95:  *      +----> FreeQue size order   |         +--------> FreeQue same size ----->
   96:  *      |   |  FreeQue same size --------+      |   EmptyQue         |
   97:  *      |   |                            |                |                     |
   98:  *      |   |                            |                |                     |
   99:  *      |   +-----------------------+                +-----------------------+
  100:  *      |   | AreaQue                    |         | AreaQue              |
  101:  *      |   +-----------------------+                +-----------------------+
  102:  */
  103: LOCAL void appendFreeArea( QUEUE *aq, MACB *macb )
  104: {
  105:         QUEUE  *fq;
  106:         size_t size = (size_t)AreaSize(aq);
  107: 
  108:         /* Search registration position */
  109:         /*  Searches for a free space with the same size as 'size' or
  110:          *  the next largest.
  111:          *  If none is found, returns &freeque.
  112:          */
  113:         fq = searchFreeArea(size, macb);
  114: 
  115:         /* Registration */
  116:         clrAreaFlag(aq, AREA_USE);
  117:         if ( fq != &macb->freeque && (size_t)FreeSize(fq) == size ) {
  118:                 QueInsert(aq + 1, fq + 1);
  119:         } else {
  120:                 QueInsert(aq + 1, fq);
  121:         }
  122:         QueInit(aq + 2);
  123: }
  124: 
  125: /*
  126:  * Delete from free queue
  127:  */
  128: LOCAL void removeFreeQue( QUEUE *fq )
  129: {
  130:         if ( !isQueEmpty(fq + 1) ) {
  131:                 QUEUE *nq = (fq + 1)->next;
  132: 
  133:                 QueRemove(fq + 1);
  134:                 QueInsert(nq + 1, nq);
  135:                 QueRemove(nq);
  136:                 QueInsert(nq, fq);
  137:         }
  138: 
  139:         QueRemove(fq);
  140: }
  141: 
  142: /*
  143:  * Area registration
  144:  *      Insert 'ent' directly after 'que'
  145:  */
  146: LOCAL void insertAreaQue( QUEUE *que, QUEUE *ent )
  147: {
  148:         ent->prev = que;
  149:         ent->next = que->next;
  150:         Assign(que->next->prev, ent);
  151:         que->next = ent;
  152: }
  153: 
  154: /*
  155:  * Delete area
  156:  */
  157: LOCAL void removeAreaQue( QUEUE *aq )
  158: {
  159:         Mask(aq->prev)->next = aq->next;
  160:         Assign(aq->next->prev, Mask(aq->prev));
  161: }
  162: 
  163: /*
  164:  * Allocate new page capable of allocating a contiguous area at least
  165:  * as big as 'size' byte
  166:  */
  167: Inline QUEUE* newPage( size_t size, MACB *macb )
  168: {
  169:         QUEUE  *top, *end;
  170:         size_t nblk;
  171: 
  172:         if ( macb->pagesz == 0 ) {
  173:                 return NULL;
  174:         }
  175: 
  176:         /* Allocate page */
  177:         nblk = toPageCount(size + sizeof(QUEUE)*2, macb);
  178:         top = (QUEUE*)(*macb->getblk)(nblk, macb->mematr);
  179:         if ( top == NULL ) {
  180:                 return NULL;
  181:         }
  182: 
  183:         /* Register in area queue */
  184:         end = (QUEUE*)((VB*)top + nblk * macb->pagesz) - 1;
  185:         insertAreaQue(&macb->areaque, end);
  186:         insertAreaQue(&macb->areaque, top);
  187:         setAreaFlag(top, AREA_TOP);
  188:         setAreaFlag(end, AREA_END);
  189: 
  190:         return top;
  191: }
  192: 
  193: /*
  194:  * Fragment and allocate
  195:  */
  196: Inline void* allocate( QUEUE *aq, size_t size, MACB *macb )
  197: {
  198:         QUEUE  *q;
  199: 
  200:         /* Any fragments smaller than the minimum fragment size
  201:            will also be allocated together */
  202:         if ( (size_t)AreaSize(aq) - size >= MIN_FRAGMENT + sizeof(QUEUE) ) {
  203: 
  204:                 /* Divide area in half */
  205:                 q = (QUEUE*)((VB*)(aq + 1) + size);
  206:                 insertAreaQue(aq, q);
  207: 
  208:                 /* Register surplus area in free queue */
  209:                 appendFreeArea(q, macb);
  210:         }
  211:         setAreaFlag(aq, AREA_USE);
  212: 
  213:         return (void*)(aq + 1);
  214: }
  215: 
  216: /* ------------------------------------------------------------------------ */
  217: 
  218: /*
  219:  * Memory allocate
  220:  */
  221: EXPORT void* _mem_malloc( size_t size, MACB *_macb )
  222: {
  223:         MACB   *macb = AlignMACB(_macb);
  224:         QUEUE  *q;
  225: 
  226:         if ( macb->testmode > 0 ) {
  227:                 chkalloc(NULL, 0, macb);
  228:         }
  229: 
  230:         /* If smaller than the minimum fragment size,
  231:            allocate the minimum fragment size */
  232:         if ( size > 0 && size < MIN_FRAGMENT ) {
  233:                 size = MIN_FRAGMENT;
  234:         }
  235: 
  236:         size = ROUND(size);
  237:         if ( size <= 0 ) {
  238:                 return NULL;
  239:         }
  240: 
  241:         /* Search free queue */
  242:         q = searchFreeArea(size, macb);
  243:         if ( q != &macb->freeque ) {
  244:                 /* Free space available: first, isolate from free queue */
  245:                 removeFreeQue(q);
  246: 
  247:                 q = q - 1;
  248:         } else {
  249:                 /* No free space, then allocate new page */
  250:                 q = newPage(size, macb);
  251:                 if ( q == NULL ) {
  252:                         return NULL;  /* Insufficient memory */
  253:                 }
  254:         }
  255: 
  256:         /* Allocate memory */
  257:         return allocate(q, size, macb);
  258: }
  259: 
  260: /*
  261:  * Memory allocate  and clear
  262:  */
  263: EXPORT void* _mem_calloc( size_t nmemb, size_t size, MACB *macb )
  264: {
  265:         size_t sz = nmemb * size;
  266:         void   *p;
  267: 
  268:         /* Allocate memory */
  269:         p = _mem_malloc(sz, macb);
  270:         if ( p == NULL ) {
  271:                 return NULL;
  272:         }
  273: 
  274:         /* Memory clear */
  275:         return MEMSET(p, 0, sz);
  276: }
  277: 
  278: /*
  279:  * Memory allocation size change
  280:  */
  281: EXPORT void* _mem_realloc( void *ptr, size_t size, MACB *_macb )
  282: {
  283:         MACB   *macb = AlignMACB(_macb);
  284:         QUEUE  *aq;
  285:         size_t oldsz, sz;
  286: 
  287:         if ( macb->testmode > 0 ) {
  288:                 if ( !chkalloc(ptr, 0, macb) ) {
  289:                         return NULL;
  290:                 }
  291:         }
  292: 
  293:         /* If smaller than minimum fragment size,
  294:            allocate minimum fragment size */
  295:         if ( size > 0 && size < MIN_FRAGMENT ) {
  296:                 size = MIN_FRAGMENT;
  297:         }
  298: 
  299:         size = ROUND(size);
  300: 
  301:         aq = (QUEUE*)ptr - 1;
  302: 
  303:         if ( ptr != NULL ) {
  304:                 /* Current allocation size */
  305:                 oldsz = (size_t)AreaSize(aq);
  306: 
  307:                 /* Merge if next space is free space */
  308:                 if ( !chkAreaFlag(aq->next, AREA_END|AREA_USE) ) {
  309:                         removeFreeQue(aq->next + 1);
  310:                         removeAreaQue(aq->next);
  311:                 }
  312: 
  313:                 sz = (size_t)AreaSize(aq);
  314:         } else {
  315:                 sz = oldsz = 0;
  316:         }
  317: 
  318:         if ( size <= sz ) {
  319:                 if ( size > 0 ) {
  320:                         /* Fragment current area and allocate */
  321:                         allocate(aq, size, macb);
  322:                 } else {
  323:                         /* Release area */
  324:                         _mem_free(ptr, macb);
  325:                         ptr = NULL;
  326:                 }
  327:         } else {
  328:                 /* Allocate new area */
  329:                 void *newptr = _mem_malloc(size, macb);
  330:                 if ( newptr == NULL ) {
  331:                         /* Reallocate original area at original size */
  332:                         if ( ptr != NULL ) {
  333:                                 allocate(aq, oldsz, macb);
  334:                         }
  335:                         return NULL;
  336:                 }
  337: 
  338:                 if ( ptr != NULL ) {
  339:                         /* Copy contents */
  340:                         MEMCPY(newptr, ptr, oldsz);
  341: 
  342:                         /* Release old area */
  343:                         _mem_free(ptr, macb);
  344:                 }
  345:                 ptr = newptr;
  346:         }
  347: 
  348:         return ptr;
  349: }
  350: 
  351: /*
  352:  * Free memory
  353:  */
  354: EXPORT void  _mem_free( void *ptr, MACB *_macb )
  355: {
  356:         MACB   *macb = AlignMACB(_macb);
  357:         QUEUE  *aq;
  358: 
  359:         if ( ptr == NULL ) {
  360:                 return;
  361:         }
  362: 
  363:         if ( macb->testmode > 0 ) {
  364:                 if ( !chkalloc(ptr, 0, macb) ) {
  365:                         return;
  366:                 }
  367:         }
  368: 
  369:         aq = (QUEUE*)ptr - 1;
  370:         clrAreaFlag(aq, AREA_USE);
  371: 
  372:         if ( !chkAreaFlag(aq->next, AREA_END|AREA_USE) ) {
  373:                 /* Merge with just next free area */
  374:                 removeFreeQue(aq->next + 1);
  375:                 removeAreaQue(aq->next);
  376:         }
  377: 
  378:         if ( !chkAreaFlag(aq, AREA_TOP) && !chkAreaFlag(aq->prev, AREA_USE) ) {
  379:                 /* Merge with just previous free area */
  380:                 aq = aq->prev;
  381:                 removeFreeQue(aq + 1);
  382:                 removeAreaQue(aq->next);
  383:         }
  384: 
  385:         /* If whole page is empty, then release the page itself */
  386:         if ( chkAreaFlag(aq, AREA_TOP) && chkAreaFlag(aq->next, AREA_END) ) {
  387:                 /* Page release */
  388:                 removeAreaQue(aq->next);
  389:                 removeAreaQue(aq);
  390:                 (*macb->relblk)(aq);
  391:         } else {
  392:                 /* Register free area in free queue */
  393:                 appendFreeArea(aq, macb);
  394:         }
  395: }