gonzui

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