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 T-Engine Forum at 2013/03/08.
   11:  *    Modified by TRON Forum(http://www.tron.org/) at 2015/06/04.
   12:  *
   13:  *----------------------------------------------------------------------
   14:  */
   15: /*
   16:  * This software package is available for use, modification, 
   17:  * and redistribution in accordance with the terms of the attached 
   18:  * T-License 2.x.
   19:  * If you want to redistribute the source code, you need to attach 
   20:  * the T-License 2.x document.
   21:  * There's no obligation to publish the content, and no obligation 
   22:  * to disclose it to the TRON Forum if you have modified the 
   23:  * software package.
   24:  * You can also distribute the modified source code. In this case, 
   25:  * please register the modification to T-Kernel traceability service.
   26:  * People can know the history of modifications by the service, 
   27:  * and can be sure that the version you have inherited some 
   28:  * modification of a particular version or not.
   29:  *
   30:  *    http://trace.tron.org/tk/?lang=en
   31:  *    http://trace.tron.org/tk/?lang=ja
   32:  *
   33:  * As per the provisions of the T-License 2.x, TRON Forum ensures that 
   34:  * the portion of the software that is copyrighted by Ken Sakamura or 
   35:  * the TRON Forum does not infringe the copyrights of a third party.
   36:  * However, it does not make any warranty other than this.
   37:  * DISCLAIMER: TRON Forum and Ken Sakamura shall not be held
   38:  * responsible for any consequences or damages caused directly or
   39:  * indirectly by the use of this software package.
   40:  *
   41:  * The source codes in bsd_source.tar.gz in this software package are 
   42:  * derived from NetBSD or OpenBSD and not covered under T-License 2.x.
   43:  * They need to be changed or redistributed according to the 
   44:  * representation of each source header.
   45:  */
   46: 
   47: /*
   48:  *      imalloc.c (T2EX)
   49:  *      Kernel Memory Allocation (Imalloc)
   50:  */
   51: 
   52: #include "sysmgr.h"
   53: #include <sys/imalloc.h>
   54: #include <sys/queue.h>
   55: #include "cpu_conf.h"
   56: 
   57: #if defined(USE_MMU) && defined(MMU_MIN_USER_LEVEL)
   58: #define IMALLOC_MIN_USER_LEVEL  MMU_MIN_USER_LEVEL
   59: #else
   60: #define IMALLOC_MIN_USER_LEVEL  3 /* for compatibility */
   61: #endif
   62: 
   63: /*
   64:  * Memory allocation management information
   65:  */
   66: typedef struct {
   67:         const QUEUE    nouse;             /* Area to match alignment */
   68: 
   69:         /* AreaQue for connecting each area where reserved pages are
   70:            divided Sort in ascending order of addresses in a page.
   71:            Do not sort between pages. */
   72:         QUEUE          areaque;
   73:         /* FreeQue for connecting unused area in reserved pages
   74:            Sort from small to large free spaces. */
   75:         QUEUE          freeque;
   76: 
   77:         UINT           mematr;          /* Memory attribute */
   78: } IMACB;
   79: 
   80: /*
   81:  * Compensation for aligning "&areaque" position to 8 bytes border
   82:  */
   83: #define AlignIMACB(imacb)       ( (IMACB*)((UW)(imacb) & ~0x00000007U) )
   84: 
   85: LOCAL   UINT              pagesz;             /* Page size (byte) */
   86: 
   87: /*
   88:  * Minimum unit of subdivision
   89:  *      The lower 3 bits of address is always 0
   90:  *      because memory is allocated by ROUNDSZ.
   91:  *      AreaQue uses the lower 3 bits for flag.
   92:  */
   93: #define ROUNDSZ         ( sizeof(QUEUE) )      /* 8 bytes */
   94: #define ROUND(sz)       ( ((sz) + (ROUNDSZ-1)) & ~(ROUNDSZ-1) )
   95: 
   96: /* Minimum fragment size */
   97: #define MIN_FRAGMENT    ( sizeof(QUEUE) * 2 )
   98: 
   99: /*
  100:  * Flag that uses the lower bits of AreaQue's 'prev'.
  101:  */
  102: #define AREA_USE        0x00000001U    /* In-use */
  103: #define AREA_TOP        0x00000002U    /* Top of page */
  104: #define AREA_END        0x00000004U    /* End of page */
  105: #define AREA_MASK       0x00000007U
  106: 
  107: #define setAreaFlag(q, f)       ( (q)->prev = (QUEUE*)((UW)(q)->prev |  (f)) )
  108: #define clrAreaFlag(q, f)       ( (q)->prev = (QUEUE*)((UW)(q)->prev & ~(f)) )
  109: #define chkAreaFlag(q, f)       ( ((UW)(q)->prev & (f)) != 0 )
  110: 
  111: #define Mask(x)         ( (QUEUE*)((UW)(x) & ~AREA_MASK) )
  112: #define Assign(x, y)    ( (x) = (QUEUE*)(((UW)(x) & AREA_MASK) | (UW)(y)) )
  113: 
  114: /*
  115:  * Area size
  116:  */
  117: #define AreaSize(aq)    ((size_t)( (VB*)(aq)->next - (VB*)((aq) + 1) ))
  118: #define FreeSize(fq)    ((size_t)( (VB*)((fq) - 1)->next - (VB*)(fq) ))
  119: 
  120: /*
  121:  * Byte size -> Page number
  122:  */
  123: Inline size_t PageCount( size_t size )
  124: {
  125:         return (size + (pagesz-1)) / pagesz;
  126: }
  127: 
  128: /*
  129:  * FreeQue search
  130:  *      Search free area whose size is equal to 'blksz', or closest and
  131:  *      larger than 'blksz'.
  132:  *      If it can not be found, return '&imacb->freeque'.
  133:  */
  134: LOCAL QUEUE* searchFreeArea( size_t blksz, IMACB *imacb )
  135: {
  136:         QUEUE  *q = &imacb->freeque;
  137: 
  138:         /* For area that is less than 1/4 of the page size, search from
  139:            smaller size. Otherwise, search from larger size. */
  140:         if ( blksz > pagesz / 4 ) {
  141:                 /* Search from larger size */
  142:                 size_t fsz = 0;
  143:                 while ( (q = q->prev) != &imacb->freeque ) {
  144:                         fsz = FreeSize(q);
  145:                         if ( fsz <= blksz ) {
  146:                                 return ( fsz < blksz )? q->next: q;
  147:                         }
  148:                 }
  149:                 return ( fsz >= blksz )? q->next: q;
  150:         } else {
  151:                 /* Search from smaller size */
  152:                 while ( (q = q->next) != &imacb->freeque ) {
  153:                         if ( FreeSize(q) >= blksz ) {
  154:                                 break;
  155:                         }
  156:                 }
  157:                 return q;
  158:         }
  159: }
  160: 
  161: /*
  162:  * Registration of free area on FreeQue
  163:  *      FreeQue is composed of 2 types: Queue that links the different
  164:  *      size of areas by size
  165:  *      and queue that links the same size areas.
  166:  *
  167:  *      imacb->freeque
  168:  *      |
  169:  *      |  +-----------------------+   +-----------------------+
  170:  *      |  | AreaQue            |     | AreaQue                 |
  171:  *      |  +-----------------------+   +-----------------------+
  172:  *      *---> FreeQue by size           |  *----> FreeQue same size   ---->
  173:  *      |  | FreeQue same size    ----*   | EmptyQue           |
  174:  *      |  |                    |    |                        |
  175:  *      |  |                    |    |                        |
  176:  *      |  +-----------------------+   +-----------------------+
  177:  *      |  | AreaQue            |     | AreaQue                 |
  178:  *      v  +-----------------------+   +-----------------------+
  179:  */
  180: LOCAL void appendFreeArea( QUEUE *aq, IMACB *imacb )
  181: {
  182:         QUEUE  *fq;
  183:         size_t size = AreaSize(aq);
  184: 
  185:         /* Registration position search */
  186:         /*  Search free area whose size is equal to 'blksz',
  187:          *  or closest and larger than 'blksz'.
  188:          *  If it can not be found, return '&imacb->freeque'.
  189:          */
  190:         fq = searchFreeArea(size, imacb);
  191: 
  192:         /* Registration */
  193:         clrAreaFlag(aq, AREA_USE);
  194:         if ( fq != &imacb->freeque && FreeSize(fq) == size ) {
  195:                 QueInsert(aq + 1, fq + 1);
  196:         } else {
  197:                 QueInsert(aq + 1, fq);
  198:         }
  199:         QueInit(aq + 2);
  200: }
  201: 
  202: /*
  203:  * Delete from FreeQue
  204:  */
  205: LOCAL void removeFreeQue( QUEUE *fq )
  206: {
  207:         if ( !isQueEmpty(fq + 1) ) {
  208:                 QUEUE *nq = (fq + 1)->next;
  209: 
  210:                 QueRemove(fq + 1);
  211:                 QueInsert(nq + 1, nq);
  212:                 QueRemove(nq);
  213:                 QueInsert(nq, fq);
  214:         }
  215: 
  216:         QueRemove(fq);
  217: }
  218: 
  219: /*
  220:  * Register area
  221:  *      Insert 'ent' just after 'que'
  222:  */
  223: LOCAL void insertAreaQue( QUEUE *que, QUEUE *ent )
  224: {
  225:         ent->prev = que;
  226:         ent->next = que->next;
  227:         Assign(que->next->prev, ent);
  228:         que->next = ent;
  229: }
  230: 
  231: /*
  232:  * Delete area
  233:  */
  234: LOCAL void removeAreaQue( QUEUE *aq )
  235: {
  236:         Mask(aq->prev)->next = aq->next;
  237:         Assign(aq->next->prev, Mask(aq->prev));
  238: }
  239: 
  240: /*
  241:  * Subdivide and allocate
  242:  */
  243: Inline void* mem_alloc( QUEUE *aq, size_t blksz, IMACB *imacb )
  244: {
  245:         QUEUE  *q;
  246: 
  247:         /* If there are fragments smaller than the minimum fragment size,
  248:            allocate them also */
  249:         if ( AreaSize(aq) - blksz >= MIN_FRAGMENT + sizeof(QUEUE) ) {
  250: 
  251:                 /* Divide area into 2 */
  252:                 q = (QUEUE*)((VB*)(aq + 1) + blksz);
  253:                 insertAreaQue(aq, q);
  254: 
  255:                 /* Register remaining area to FreeQue */
  256:                 appendFreeArea(q, imacb);
  257:         }
  258:         setAreaFlag(aq, AREA_USE);
  259: 
  260:         return (void*)(aq + 1);
  261: }
  262: 
  263: /*
  264:  * Get memory
  265:  */
  266: LOCAL void* imalloc( size_t size, IMACB *imacb )
  267: {
  268:         QUEUE  *q;
  269:         void   *mem;
  270:         UW     imask;
  271: 
  272:         /* If it is smaller than the minimum fragment size,
  273:            allocate the minimum size to it. */
  274:         if ( size < MIN_FRAGMENT ) {
  275:                 size = MIN_FRAGMENT;
  276:         }
  277:         size = ROUND(size);
  278: 
  279:         DI(imask);  /* Exclusive control by interrupt disable */
  280: 
  281:         /* Search FreeQue */
  282:         q = searchFreeArea(size, imacb);
  283:         if ( q != &imacb->freeque ) {
  284:                 /* There is free area: Split from FreeQue once */
  285:                 removeFreeQue(q);
  286: 
  287:                 q = q - 1;
  288:         } else {
  289:                 /* Reserve new pages because there is no free space */
  290:                 QUEUE *e;
  291:                 size_t        n;
  292: 
  293:                 /* Reserve pages */
  294:                 EI(imask);
  295:                 n = PageCount(size + sizeof(QUEUE) * 2);
  296:                 q = GetSysMemBlk(n, imacb->mematr);
  297:                 if ( q == NULL ) {
  298:                         goto err_ret;  /* Insufficient memory */
  299:                 }
  300:                 DI(imask);
  301: 
  302:                 /* Register on AreaQue */
  303:                 e = (QUEUE*)((VB*)q + n * pagesz) - 1;
  304:                 insertAreaQue(&imacb->areaque, e);
  305:                 insertAreaQue(&imacb->areaque, q);
  306:                 setAreaFlag(q, AREA_TOP);
  307:                 setAreaFlag(e, AREA_END);
  308:         }
  309: 
  310:         /* Allocate memory */
  311:         mem = mem_alloc(q, size, imacb);
  312: 
  313:         EI(imask);
  314:         return mem;
  315: 
  316: err_ret:
  317:         TM_DEBUG_PRINT(("imalloc error\n"));
  318:         return NULL;
  319: }
  320: 
  321: /*
  322:  * Get memory
  323:  */
  324: LOCAL void* icalloc( size_t nmemb, size_t size, IMACB *imacb )
  325: {
  326:         size_t sz = nmemb * size;
  327:         void   *mem;
  328: 
  329:         mem = imalloc(sz, imacb);
  330:         if ( mem == NULL ) {
  331:                 return NULL;
  332:         }
  333: 
  334:         memset(mem, 0, sz);
  335: 
  336:         return mem;
  337: }
  338: 
  339: /*
  340:  * Free memory
  341:  *      It may be called during interrupt disable. In this case, need to wait
  342:  *       until interrupt is enabled and until free.
  343:  */
  344: LOCAL void ifree( void *ptr, IMACB *imacb )
  345: {
  346:         QUEUE  *aq;
  347:         UW     imask;
  348: 
  349:         DI(imask);  /* Exclusive control by interrupt disable */
  350: 
  351:         aq = (QUEUE*)ptr - 1;
  352:         clrAreaFlag(aq, AREA_USE);
  353: 
  354:         if ( !chkAreaFlag(aq->next, AREA_END|AREA_USE) ) {
  355:                 /* Merge with free area in after location */
  356:                 removeFreeQue(aq->next + 1);
  357:                 removeAreaQue(aq->next);
  358:         }
  359: 
  360:         if ( !chkAreaFlag(aq, AREA_TOP) && !chkAreaFlag(aq->prev, AREA_USE) ) {
  361:                 /* Merge with free area in front location */
  362:                 aq = aq->prev;
  363:                 removeFreeQue(aq + 1);
  364:                 removeAreaQue(aq->next);
  365:         }
  366: 
  367:         /* If the whole page is free, then free the page.
  368:          * However, do not free the page if it is called during
  369:          * interrupt disabled.
  370:          */
  371:         if ( !isDI(imask) && chkAreaFlag(aq, AREA_TOP) && chkAreaFlag(aq->next, AREA_END) ) {
  372:                 /* Free pages */
  373:                 removeAreaQue(aq->next);
  374:                 removeAreaQue(aq);
  375:                 EI(imask);
  376:                 RelSysMemBlk(aq);
  377:                 DI(imask);
  378:         } else {
  379:                 /* Register free area to FreeQue */
  380:                 appendFreeArea(aq, imacb);
  381:         }
  382: 
  383:         EI(imask);
  384: }
  385: 
  386: /* ------------------------------------------------------------------------ */
  387: /*
  388:  * Allocate memory whose attributes are specified by 'attr.'
  389:  *      attr = TA_RNGn | TA_NORESIDENT
  390:  */
  391: 
  392: LOCAL IMACB     Imacb[2][2];
  393: 
  394: #define RING(attr)      ( ( (((attr) & TA_RNG3) >> 8) >= IMALLOC_MIN_USER_LEVEL )? 1: 0 )
  395: #define RESIDENT(attr)  ( ( ((attr) & TA_NORESIDENT) == 0 )? 1: 0 )
  396: 
  397: #define SelIMACB(attr)  ( AlignIMACB(&Imacb[RING(attr)][RESIDENT(attr)]) )
  398: 
  399: EXPORT void* IAmalloc( size_t size, UINT attr )
  400: {
  401:         return imalloc(size, SelIMACB(attr));
  402: }
  403: 
  404: EXPORT void* IAcalloc( size_t nmemb, size_t size, UINT attr )
  405: {
  406:         return icalloc(nmemb, size, SelIMACB(attr));
  407: }
  408: 
  409: EXPORT void  IAfree( void *ptr, UINT attr )
  410: {
  411:         ifree(ptr, SelIMACB(attr));
  412: }
  413: 
  414: /* ------------------------------------------------------------------------ */
  415: /*
  416:  * Allocate resident memory where T-Kernel system call is enabled
  417:  * and the protection level (TSVCLimit) is lowest.
  418:  */
  419: 
  420: /* SVC control protection level (T-Kernel/OS) */
  421: IMPORT INT      svc_call_limit;
  422: 
  423: #define TA_RNG  ( (UINT)svc_call_limit << 8 )
  424: 
  425: EXPORT void* Imalloc( size_t size )
  426: {
  427:         return IAmalloc(size, TA_RNG);
  428: }
  429: 
  430: EXPORT void* Icalloc( size_t nmemb, size_t size )
  431: {
  432:         return IAcalloc(nmemb, size, TA_RNG);
  433: }
  434: 
  435: EXPORT void  Ifree( void *ptr )
  436: {
  437:         IAfree(ptr, TA_RNG);
  438: }
  439: 
  440: /* ------------------------------------------------------------------------ */
  441: 
  442: /*
  443:  * IMACB Initialization
  444:  */
  445: LOCAL void initIMACB( UINT attr )
  446: {
  447:         IMACB  *imacb = SelIMACB(attr);
  448: 
  449:         QueInit(&imacb->areaque);
  450:         QueInit(&imacb->freeque);
  451:         imacb->mematr = attr;
  452: }
  453: 
  454: /*
  455:  * Imalloc initial setting
  456:  */
  457: EXPORT ER init_Imalloc( void )
  458: {
  459:         T_RSMB rsmb;
  460:         ER     ercd;
  461: 
  462:         ercd = RefSysMemInfo(&rsmb);
  463:         if ( ercd < E_OK ) {
  464:                 goto err_ret;
  465:         }
  466: 
  467:         pagesz = (UINT)rsmb.blksz;
  468: 
  469:         initIMACB(TA_RNG0);
  470:         initIMACB(TA_RNG0|TA_NORESIDENT);
  471:         initIMACB(TA_RNG3);
  472:         initIMACB(TA_RNG3|TA_NORESIDENT);
  473: 
  474:         return E_OK;
  475: 
  476: err_ret:
  477:         TM_DEBUG_PRINT(("init_Imalloc ercd = %d\n", ercd));
  478:         return ercd;
  479: }