QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2664|回复: 0
打印 上一主题 下一主题

malloc(内存分配)在嵌入式下的一种实现

[复制链接]
字体大小: 正常 放大

937

主题

117

听众

3万

积分

升级  0%

  • TA的每日心情

    2020-10-25 11:55
  • 签到天数: 264 天

    [LV.8]以坛为家I

    自我介绍
    内蒙古大学计算机学院

    社区QQ达人 金点子奖 助人为乐奖 风雨历程奖

    群组2013年数学建模国赛备

    跳转到指定楼层
    1#
    发表于 2013-7-26 10:17 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    想知道malloc是如何实现的吗?这里是一个简单版本,所有的功能都在这个文件实现了。如果你对malloc的原理有兴趣,可以通过这个代码窥视一二。实际上这个实现是著名的嵌入式操作系统vxworks5.5以前的内存分配版本。这里我已经把它实现的更简单易懂了。当然我还有移植到vc++下的版本,更方便调试。有需要请留言
    ( M. P1 f, y9 l+ u
    ! w! u& I6 n8 B' [
    0 ?. U5 ?  e, U% E" H
    6 G8 F5 G- S* J2 d% i: m" ?& V4 K4 q. ] *\file( W9 y) ^0 M& ^* T9 ?# p
    *\brief                  Q5 m( h( o  p+ [# A5 u; \
    *\details       
    . |& H; ]7 h: `' F( f2 U *% a5 i+ I. `7 F" ^
    *\author        Janson; u9 H' |' {2 H5 K
    *\version        9 K8 \/ _% N* V3 _. F
    *\date                04Jan12# F3 O  n5 L% n' H2 B( _
    *
    & a, }9 |7 U- W7 _# ]3 S* b- o' O. [ *\warning       
    ' t( x( W8 }& r6 Z) L1 L/ {4 G6 Z *
    / ^8 s! |! }4 `& J- f *\history \arg        30Jan12, Janson, Create the file
    $ B% T6 c# a. B6 a *        modify from VxWorks source
    - C7 H/ u8 G/ I *  Legal Declaration: it is for studying VxWorks only.
    4 T; t8 S; q8 H  v& Z  z* d2 _) | */
    5 u1 k: W% V$ v#include "includes.h"( }# Z0 ~# F* ^+ N" O4 D
    5 {$ f8 U. A5 E* m$ A
    /* The memParLib.h file is hear:
    + Q( i" M1 d2 Z' x1 S" Ihttps://code.google.com/p/vxwork ... rivate/memPartLib.h
    + v; c( E0 B  A+ ^*/1 R+ A# ^" {$ C* \

    ' z* u, U0 E* T+ r/* optional check for bad blocks */: c( ^9 u+ k# R/ @
    # _. s! X+ m& K
    #define MEM_BLOCK_CHECK                        0x10
    : _0 ]! [' K9 `: J; x5 h/ x8 x) r4 N, K
    /* response to errors when allocating memory */
    - F1 F, }  a9 n
    * M5 e/ T' I8 h& w: W#define MEM_ALLOC_ERROR_LOG_FLAG        0x20
    7 F7 b  f1 ]% q7 U. P% y# N#define MEM_ALLOC_ERROR_SUSPEND_FLAG        0x403 U3 K/ G! l* B! N0 B- z) W

    . u2 H+ s  V1 z( c9 T% C6 o7 y# n/* response to errors when freeing memory */8 I- z# F; S3 `/ f% c
    + ~9 o1 n7 s% h; F
    #define MEM_BLOCK_ERROR_LOG_FLAG        0x80
    0 F0 B& M; W6 [( ?* J% w#define MEM_BLOCK_ERROR_SUSPEND_FLAG        0x100
    - a2 N, x9 E1 g3 k, f* \% u% ]4 n" g
    0 e( l. W" B: J8 z#define NEXT_HDR(pHdr)  ((BLOCK_HDR *) ((char *) (pHdr) + (2 * (pHdr)->nWords)))
    1 m$ n) B5 s( K1 m5 z" ?7 H: j#define PREV_HDR(pHdr)        ((pHdr)->prevHdr)
    1 t( p  b" M3 [! N' z  C3 m+ R, @" l7 W* }# i3 o( E* R1 l! H! }
    #define HDR_TO_BLOCK(pHdr)        ((char *) ((int) pHdr + sizeof (BLOCK_HDR)))
    ! i. f  n9 _4 G6 P7 m#define BLOCK_TO_HDR(pBlock)        ((BLOCK_HDR *) ((int) pBlock - \$ [/ E& r5 r/ j; E& z
                                                    sizeof(BLOCK_HDR)))$ U, h' g9 f! Q) v+ V" ^4 |

    & |% X. L& x3 C% ?7 u#define HDR_TO_NODE(pHdr)        (& ((FREE_BLOCK *) pHdr)->node)2 W  `1 b% ~9 {$ n
    #define NODE_TO_HDR(pNode)        ((BLOCK_HDR *) ((int) pNode - \
    - \3 x$ H0 K; |5 `/ Y- q4 Y                                                OFFSET (FREE_BLOCK, node)))1 V% v7 Q) a% T) k" \. y; g1 `& ?
    % ~  a& P+ D: X4 m% Q: w6 r) t3 X
    static BOOL memPartLibInstalled = FALSE;$ ]' l; b- b- a4 _" s9 A

    ; A! d* r) K' P$ Z& C  |static OBJ_CLASS memPartClass;
    9 q3 p; P/ c( O3 Y7 V; _5 ACLASS_ID memPartClassId = &memPartClass;
    " g4 }: Z- |0 l6 T# x; h, R
    ' i! d! x$ L5 f: q5 X7 L3 tstatic PARTITION memSysPartition;' I# o' \& d. B5 B& |( H3 i$ ]% b, a
    PART_ID memSysPartId = &memSysPartition;3 m; q" A1 p$ M
    U32 memDefaultAlign = _ALLOC_ALIGN_SIZE;
    9 s" g# ~7 A7 B- k+ F. C
    0 M7 l" D! T+ K2 l8 Z0 x  v; \( zstatic SEMAPHORE semMemSysPartition;
    ( e! _/ t. I5 C* [( \
    7 J8 D! p1 {/ X7 P; Bstatic void memPartSemInit(PART_ID partId);3 h* H% V# W) a6 B6 e$ d

    9 ?8 I0 x) j( x* p& nFUNCTION  memPartSemInitRtn        = (FUNCTION) memPartSemInit;
    6 }( m9 I% ]' {% N5 j
    0 C7 X3 z, @3 v* J% E8 A( v3 punsigned memPartDefaultOption = MEM_BLOCK_ERROR_SUSPEND_FLAG | MEM_BLOCK_CHECK;
    ( i4 n* e- v/ f8 L; K& h) l1 A/ X6 Z$ ^2 k4 }
    static BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree);$ q2 A' T5 g& {$ I9 H$ t4 b  d
    static BLOCK_HDR* memAlignedBlockSplit(PART_ID partId
    8 h1 t! z: r) j5 s/ G) U        , FAST BLOCK_HDR* pHdr! W; M7 b& g1 C- n% ^- J7 U
            , FAST unsigned nWords
    ) d. A+ t% s# \! D0 z; F        , unsigned minWords0 [9 @( i1 E% H: H9 k2 W3 _
            , unsigned align);
      ?" v" `2 A8 z6 b* [; l
    + }3 f) b) A; hstatic STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize);
    ( l' r0 a. `/ F: G& e# g
    7 N( U; ^7 C6 M5 s/ x' U" w3 q1 ^1 O  gSTATUS memPartLibInit(char* pPool, unsigned poolSize)
    3 r! Z9 Z7 I7 U1 B/ D5 v{
    # V: @, X  }2 P/ M- u( R% _% f        if((!memPartLibInstalled) && 7 _/ w1 ~, e! S, X! A3 O
                    (OK == classInit(memPartClassId, sizeof(PARTITION), OFFSET(PARTITION, objCore)
    * a% b8 I) W; I4 Q& l                , (FUNCTION)memPartCreate, (FUNCTION)memPartInit, (FUNCTION)memPartDestroy)))' P. ~  `& ]0 o# ?2 B5 _* b
            {: r: R/ Z9 T$ Y  H& w( u
                    memPartInit(&memSysPartition, pPool, poolSize);
    ' n. @; L& p) M/ o$ c8 t. ?                memPartLibInstalled = TRUE;
    ' x0 D( e  r  c! w. I) u! w  r        }; G! V1 F8 A5 |/ I2 R# M1 F

    1 {- @' U# Z$ S( ~& b9 R2 T        return ((memPartLibInstalled)? OK : ERROR);. P5 r8 p4 \, X0 M
    }
    - `/ {7 s  I7 L' {' V5 O
    " @1 B2 }: B8 X& DPART_ID memPartCreate(char* pPool, unsigned poolSize)" {; Y% z3 g, ^& f
    {
    , T1 ]& D, ?$ `4 j6 \) ]        PART_ID pPart = (PART_ID)objAlloc(memPartClassId);
    + i! C  a: f3 F
    ; K6 ?4 A9 l9 p+ e: Z/ C% c        if(NULL != pPart)- m- r: O6 A1 o0 g6 G; ]0 \3 c0 G( B
            {7 q4 U) u0 W% p. r
                    memPartInit(pPart, pPool, poolSize);* c/ ~% g  E2 A( \4 _6 Y7 I" V- {
            }
    ! O% Q" [% B! j0 V4 l' ^, \6 P. m* @$ B5 r4 x! k
            return pPart;
    6 g9 R# o% d) X1 Q1 k9 X4 f& m- M}6 C/ t- h  V9 K! k2 B, }

    " G' K8 E4 \  w$ ~void memPartInit(PART_ID partId, char* pPool, unsigned poolSize)' @  z+ }, Y0 ~9 Q1 P
    {
    ) u+ [% j7 f8 |- V  N        memset((void*)partId, 0, sizeof(*partId));
    ) h/ O8 U  t# X- v2 m" Q2 Y6 {$ A( S
            partId->options = memPartDefaultOption;
    0 B5 D0 c( A5 }% q+ b        partId->minBlockWords = sizeof (FREE_BLOCK) >> 1;        /* word not byte */( q1 V$ b' D7 [
    . W- R# f- @+ b2 q' G
            (* memPartSemInitRtn) (partId);% D2 Q5 @, e1 y9 n/ {2 ?& N, @
           
    ) n) G7 D  t9 _* u/ o' V* O        dllInit(&partId->freeList);
    1 B3 |* N* F& b2 ~$ C        , c% y6 d- y: x
            objCoreInit(&partId->objCore, memPartClassId);" D8 Z2 _4 l/ i2 L$ q0 G: e
           
    ' l( D! L$ }- Q5 P# T        memPartAddToPool(partId, pPool, poolSize);
    " |0 t( h/ o" o$ x* C}
    + q4 Z5 t* x2 P1 g; {- j; L; i+ T/ i, Z( f" K
    STATUS memPartDestroy(PART_ID partId)
    5 F6 z' k' C3 I, U4 Z{
    & S8 k, [/ a4 \0 T/ @6 N) @        return (ERROR);
    & e7 _4 O  S: n) [9 O4 s% s1 d) l}) s& ~2 h# y, W( y* U9 ^1 H

    8 J  \$ E# x! [' _# S+ rvoid memAddToPool(FAST char *pPool, FAST unsigned poolSize)
    - K3 r, [6 z  j- N4 g8 l* S{- T- t* t! ]# `) K( x. @
        (void)memPartAddToPool(&memSysPartition, pPool, poolSize);) Q% e$ K0 H9 F/ j
    }2 L6 ?/ a5 @. i: q* E' l8 a! P
    ; ], V+ z( E  n: @4 i

    8 J' D$ o9 Q4 C7 R/ _2 P3 ostatic STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize)
    . K) D2 `, A' U' w6 s' H4 I& I{
    - ~" d. \& I7 Q, \/ x        BLOCK_HDR* pHdrStart;
    ! _5 R7 S! W) ~+ R+ h: e1 h        BLOCK_HDR* pHdrMid;( p- ~0 x! d; G% h' d
            BLOCK_HDR* pHdrEnd;/ B+ n0 z4 G$ n6 ~$ Z. D
            char* tmp;  S- w% C  y0 `" V) r: N8 r
            int reducePool;
    . \; ^5 s2 b, K8 m9 J2 H9 _& v) N, K+ T. H: Z( e
            if(!(IS_CLASS(partId, memPartClassId)))        /* only memPartClass can call this function */
    6 F0 P' B3 W( t9 v5 t/ F1 k$ o0 s8 ~        {8 O( J- [8 e- L2 k
                    return (ERROR);8 B3 ]- {  i+ i) V- t
            }
      N( P5 r5 ~; }& t
    2 `0 T; n. q4 c* c! M1 p' e) I- a3 l        tmp = (char*) MEM_ROUND_UP(pPool);
    1 e  L. E# B' f, r* J        reducePool = tmp - pPool;
    6 n* d: F/ m- k3 o) D( h- E
    * O+ P. K; X6 n) _        /* adjust the lenght */
    2 T. D- d' k' V        if(poolSize >= reducePool)
    ; D' g: r1 e% i1 \7 b        {
    , u. G1 }- l2 \! V$ o                poolSize -= reducePool;/ I6 ~, J3 p+ C7 C  s% x1 p/ h( V
            }
    " M4 V/ E  s/ F        else
    2 R' N8 Y+ G# y2 {& M        {0 ?/ B- w) N/ N5 m
                    poolSize = 0;4 _; ]: W7 Y1 D6 n4 z. v- K8 U3 ?
            }
    ; A* \6 {: R: \% i# Z1 @3 O        pPool = tmp;
    ! x' m( i+ H8 C* m       
    1 z) Z) u7 Q( Q. D+ A        poolSize = MEM_ROUND_DOWN(poolSize);; O2 U; g' G( ~0 s7 n/ ]; t
            * Q% A! U, @3 A- L6 |" A3 f
            /* at least one valid free block and three header blocks */
    & y* s' E. f; `7 v' g) c1 o        if((sizeof(BLOCK_HDR)*3 + (partId->minBlockWords*2)) > poolSize)
    1 _4 r) O' |! @$ i- O, S        {6 K" L$ B! a2 h, C& f
                    return (ERROR);
    ! d5 ?2 J2 @' [1 y5 {1 ~  E6 B        }) y* v8 @7 |1 S6 L' p
    ; Y8 F/ u1 H0 {7 Q: S
            /* initialize three blocks */9 w: N* g0 y* r9 O" ?
            pHdrStart = (BLOCK_HDR*)pPool;% t- H7 N/ D1 D  m/ @
            pHdrStart->prevHdr = NULL;
    " L1 T4 X3 r" G, U        pHdrStart->free = FALSE;                /* never in use */
    # B, E6 Y/ `, _, B$ I        pHdrStart->nWords = sizeof(BLOCK_HDR) >> 1;
    / C9 l: b1 m0 ?( {- l( p9 q9 f7 }4 i, ^/ A7 N6 X) b
            pHdrMid = NEXT_HDR(pHdrStart);
    # q* X  \( V) {8 s  {        pHdrMid->prevHdr = pHdrStart;8 ?( ^# W/ V; K7 Q0 s1 p, X
            pHdrMid->free = TRUE;                        /* the main block */
    * m4 G% ^: A( }3 _$ n% B        pHdrMid->nWords = (poolSize - 2*sizeof(BLOCK_HDR)) >> 1;
    ( F( E! ?" _, p; J- X; x
    2 d, B5 X% P* V1 v3 x        pHdrEnd = NEXT_HDR(pHdrMid);
    2 f3 X6 {. L; o8 f8 Y9 Y        pHdrEnd->prevHdr = pHdrMid;
    : K$ G( ~: i. ~9 G/ |+ J& }        pHdrEnd->free = FALSE;
    ) ?8 ^1 M0 o# V7 Q5 D5 T        pHdrEnd->nWords = sizeof (BLOCK_HDR) >> 1;2 x! n# z: I# l
    ( M6 `! l7 p& L1 t
            /* TODO take sem hear *// @" u+ f, V3 u; j; ~& p1 f9 L  d
            semTake(partId->semPartId, WAIT_FOREVER);4 _0 Z9 i) b# D
              R* ^8 v; g3 Q7 @
            dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdrMid));
    9 f, [. v' |) b% W' o) K* I        partId->totalWords += (poolSize >> 1);
    $ i! ~1 w- K7 J, v& l: U
    ( T0 j% j" n0 }7 c2 P/ L* S        /* TODO give sem hear */3 o. |/ ^3 i/ M
            semGive(partId->semPartId);0 ~+ L" e! s& L. E

    * B+ R. t- ~, b
    7 q  D2 E2 G1 C* I* }7 ]( E        return (OK);
    0 R. t- f+ E% u1 k4 N}
    ! G) X% P8 J+ R+ L' k
    - I, H  ]* }, r: o0 evoid* memPartAllignedAlloc(FAST PART_ID partId, unsigned nBytes, unsigned align)
    : t& O" h9 t9 [) S{* R! Q: d2 C; b4 Z  k
            FAST unsigned nWords;. H7 Q6 B6 F! L- T: J7 g" V4 Z
            FAST unsigned nWordsExtra;
    % T. b* \# X6 Y, Z1 b        FAST DL_NODE* pNode;
    0 M; R) u& i% w        FAST BLOCK_HDR* pHdr;$ y, Y' B) D# N0 \9 N
            BLOCK_HDR* pNewHdr;# h! C. K* [9 M' ?! Q
            BLOCK_HDR* origpHdr;0 Z5 [1 s/ d% t5 q( I7 r
    0 m9 r& Q9 |5 t4 v! ?- ~: k
            if(!(IS_CLASS(partId, memPartClassId)))        /* only memPartClass can call this function */- e% ~& X6 f9 r9 }5 G
            {. h- y  U" a# i4 a& n$ o2 N- ^& U
                    return (NULL);
    + c3 C- c9 i: [6 n        }1 ]1 q. E2 ^9 o! h0 \3 w5 J
    0 o' }# V2 ]/ c
            nWords = (MEM_ROUND_UP(nBytes)+sizeof(BLOCK_HDR)) >>1;$ `/ @- E/ Z  R, h; C8 g: s
    4 A& E6 X& Z9 h$ @) H! B' W
            if((nWords<<1) < nBytes)
    # k; n0 ~, G, l& C+ \. g( v        {
    0 p  I7 I- C) {8 v" O' S                /* TODO suspend the task */0 b( w9 x8 u/ y5 Y
                    return (NULL);: y0 L" V$ K- m- F( t1 k" P
            }, s6 _, q6 I8 R( K4 I

    0 G  \% r% y3 J2 f0 ~- w        if(nWords < partId->minBlockWords)
    ' I' C2 S  b" [; k  [+ J        {+ {" n) t9 D% G. H3 h, o% r6 d/ z* [
                    nWords = partId->minBlockWords;
    0 K+ i& Q2 |6 F6 `' f* m' S* Y6 B        }
    - ^; O: y% X0 D6 T$ v6 i7 V* F8 O8 \5 }
            /* TODO task the semaphore hear */
    " x) v$ x; g/ \% o8 D        semTake(partId->semPartId, WAIT_FOREVER);( {; {  K$ b' M5 T1 @% K
            pNode = DLL_FIRST(&partId->freeList);
    / v( c' v6 S8 M( f: l) r% c& V% m        nWordsExtra = nWords + align/2; /* why? */: I8 }8 g% Y, U. T
    ( n; i* G% }# T, |$ _1 B
            for(;;)
    0 ?8 G9 S# N. h7 i% a9 r  h        {$ c8 C- {6 b: M1 i% a) c  J: [
                    while(NULL != pNode)
    * s8 u  Q% h  u3 m                {1 o' E& o" l8 R+ G* B  `
                            if((NODE_TO_HDR(pNode)->nWords > nWordsExtra) ||
    0 Q9 C- J3 H/ d8 @                                ((NODE_TO_HDR(pNode)->nWords == nWords) &&
    8 L% c) O! g( M; b3 ~0 w5 h, h0 M                                (ALIGNED(HDR_TO_BLOCK(NODE_TO_HDR(pNode)), align))))
    2 I* y/ A) ]. c1 D% G                        {1 @* z2 l  T& r& y; ]' I
                                    break;, ]" _# t# _. c$ i  @! M: K4 f
                            }' R; c+ S% s8 ?- q9 x

    4 I! h2 i* N1 g* s. Z& \# S0 v                        pNode = DLL_NEXT(pNode);
      O; h0 |/ N* L; s, @2 O                }
    8 ?) g, @: A+ _1 \" e1 Y! ]4 i6 l( Q
                    if(NULL == pNode)/ R  t8 {6 h& h8 C+ D7 k& W! c9 f
                    {+ c* j$ U4 x: q
                            /*TODO give the semaphore */
    3 S8 u' h# N" `7 h4 @+ ~% c/ Z                        semGive(partId->semPartId);2 L( o3 O* P" x* f8 w
                            return NULL;. A4 M- }4 r) v: c* N! ]$ D5 q
                    }
    & ?) V# G) ]; z% M* h
    1 F! l) ^6 [0 C- }. Y; L8 h                pHdr = NODE_TO_HDR(pNode);
    - u7 z1 H  @6 F4 Z                origpHdr = pHdr;# g1 ]3 ?3 N3 ?! |. T

    2 k$ W0 l- r& ?& Y, G& C                pNewHdr = memAlignedBlockSplit(partId, pHdr, nWords, partId->minBlockWords, align);) A3 d) Z7 u+ e. g3 y; L. O
                    if(NULL != pNewHdr)8 K* U, N2 {- a# N: ^/ I
                    {
    5 \+ `! \- v6 i# N6 E% ~9 _                        pHdr = pNewHdr;
    # }$ T9 J' k* Y; x1 ~. U# |                        break;7 }7 ]8 g2 s9 L  x
                    }2 o; u! |, h6 b) ]- Q

    4 y4 V" z4 e5 N7 e7 J                pNode = DLL_NEXT(pNode);
    1 b0 T7 M5 U( Y; }% v" ?7 C        }
    9 x: l% B) ~, \, e: z7 M' L
    ) H4 Z2 Z" {$ T        pHdr->free = FALSE;- d0 V( Q' \! r2 `# s7 w
            partId->allBlocksAlloc++;
    " A! @" b8 j! t' A; d- ]  W. h        partId->allWordsAlloc += pHdr->nWords;
    ) d" |4 V4 n5 p$ _        partId->curBlocksAlloc++;$ v3 V1 }6 y7 ]. h
            partId->curWordsAlloc += pHdr->nWords;
    * ?! Q5 k! L* ?& F" a9 ^) r/ o% v7 ]) \, e
            /*TODO give the  semaphore hear */
    2 b" {$ h0 k7 p( r& N        semGive(partId->semPartId);
    0 m9 k1 i3 B$ X" ~  s5 i        return (HDR_TO_BLOCK(pHdr));
    ) p3 a# C. Z8 }7 ^* S        8 a- M" O  v! g: t
    }
    0 H8 X  O1 I% J/ r) X) f) G  W& c2 _0 f6 U0 `6 s
    void* memPartAlloc(FAST PART_ID partId, unsigned bytes)# W+ d3 j% H, A" {/ Q) G
    {
    / a& y9 Y* [! \( e* v( @0 J: x        return memPartAllignedAlloc(partId, bytes, memDefaultAlign);
    . p- Q' J! }  s* i" L) Y}0 }5 t) N) w% n

    9 [& o; B  ~0 B. qSTATUS memPartFree(PART_ID partId, char* pBlock)" h' f' C% b9 r" Z" k" B
    {
    ( c' Z0 s) X2 j        FAST BLOCK_HDR *pHdr;
      K3 d: Q2 V( ]0 O6 J# g    FAST unsigned   nWords;
    # I3 i1 B! X" a    FAST BLOCK_HDR *pNextHdr;
      \9 V# F# V  T
    : O3 }9 d5 a4 ]7 T5 p7 y1 H; L        if(!IS_CLASS(partId, memPartClassId))3 s8 a; D+ r) [+ W! Q$ ?7 E) B
            {
    6 D% k: {1 E- n2 i                return (ERROR);
    : R3 C0 q# P- d9 K; j' K0 k        }5 M+ ]6 P1 Y  y/ }/ m

    ! q0 \' X  b8 L% J5 e" A; y0 X        if(NULL == pBlock)
    - P2 B+ ], G& n8 W        {
    + ^; J0 `0 ~% D. |                return (OK);
    2 X$ C/ A& A/ V; v4 _) A        }# E0 P; ?' z( L- R) Z9 B" l
    $ ?8 n0 ?9 Q& u. A2 ^" D
            pHdr =  BLOCK_TO_HDR(pBlock);5 ^' p% o' P) \4 L' _" z! e5 q
    3 W7 i. M5 ]% y. _1 q/ _, [+ u
            semTake(partId->semPartId, WAIT_FOREVER);
    ; C# g% D( S& B/ S. a: h7 x8 Z' d' O! J5 R$ I$ u
            if((partId->options & MEM_BLOCK_CHECK)
    7 B: e, {$ c9 X3 u+ m                && !memPartBlockIsValid(partId, pHdr, FALSE))* `& u1 p# v8 t+ H1 N. Z9 R$ F
            {+ W8 k1 \6 O: o" O
                    semGive(partId->semPartId);8 \9 h( i$ i& o' P- Z$ t4 P* D
                    return (ERROR);
    " m+ w. s0 u9 C; h# \" Y' k        }. l+ Z5 t- p: [
    + b. o' M5 l+ D$ k
            nWords = pHdr->nWords;
    4 N4 ?, ?  D) y$ U! V" I" ^        if(PREV_HDR(pHdr)->free)& o! L" }0 {; E; X% u
            {/* the prev hdr is free and than coalesce with it */4 v6 n; i% x% W; L' C. X/ F
                    pHdr->free = FALSE;
    8 W/ B8 d8 N' f# e  O$ Q$ W4 W                pHdr = PREV_HDR(pHdr);
    2 m6 p8 F6 o' Y- V                pHdr->nWords += nWords;) r; D' L4 ~9 w; T
            }$ K0 W6 G0 d# h% [% {' @; U3 L; K* X
            else
    8 f/ [3 k5 C; }4 V) Z/ a+ }        {$ V0 n' u0 X  {. J
                    pHdr->free = TRUE;6 ?  F+ F1 `9 R1 o( u1 e) Y
                    dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdr));
    5 P% E( B4 |% k0 v% Q! ]. H        }* i3 \, T0 ^! ?; H) X) ^8 ]6 Z
    4 X- Z3 L& h& ]
            /* check to coalesce with the next */
    5 t0 d; B7 e; c- g7 Y/ V3 X        pNextHdr = NEXT_HDR(pHdr);. r" `; O- J1 U- |/ r2 _
            if(pNextHdr->free)
      x4 h0 K( A) [$ |; y        {, l  D, x) `) M( u
                    pHdr->nWords += pNextHdr->nWords;" x! O% K! i3 Q0 P/ z5 `( @
                    dllRemove(&partId->freeList, HDR_TO_NODE(pNextHdr));/ ^' E& R1 Y% [! A6 B2 k
            }
    6 O8 X* [8 e5 c: J. n, O4 C& P% E, c
            /* cannot use pNextHdr->prevHdr=pHdr hear */
    ! `6 k! }; X! _$ s0 I        NEXT_HDR(pHdr)->prevHdr = pHdr;
    , C  }9 o8 `2 ^4 H: c0 Z( U6 E
    1 _$ y  j$ v6 t0 }, N. v        partId->curBlocksAlloc--;) H( R  v% B" w( C" d
            partId->curWordsAlloc -= nWords;/ c, [" t& P6 k4 g' g( m2 }( o

    2 Y9 I- L6 I7 B* n, _$ w        /* TODO give sem hear */* J0 @3 s# {# e$ |
            semGive(partId->semPartId);
    - t7 _# L7 B# U, w3 W" p; m        * f1 \# B" o. u6 x
            return (OK);
    6 W; w+ g* A4 m/ Y# O) l+ R}* V+ E- J8 G$ t; j) T9 w# x

    1 T  J8 B, n1 x) }+ o3 f3 Jstatic BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree)' w& {5 V  b2 ^5 c4 C  `/ S. V8 U
    {
    4 w- I5 P7 v) u% _        BOOL valid;
    " M6 {2 q6 W: d; v9 w- V/ t5 T- x: x/ z9 p' u2 j
            TASK_LOCK();
    : f! ?# n' b8 c6 B. D+ `2 W" K, v        semGive(partId->semPartId);
    * C% M9 L; R( Q( b       
    # q) O4 W- f/ U4 j8 p        valid = MEM_ALIGNED(pHdr)
    ! |8 d; h  C! w) n+ v        && MEM_ALIGNED(pHdr->nWords*2)
    : q8 O4 {  @# r        && (pHdr->nWords < partId->totalWords)
    # w2 m: d1 D! I& m7 V) Q) {6 V1 d8 f        && (pHdr->free == isFree)! b! A- L5 u) o; s: U% V
            && (pHdr == PREV_HDR(NEXT_HDR(pHdr)))
    , y0 Z( ?* V  v: |. M( s        && (pHdr == NEXT_HDR(PREV_HDR(pHdr)));. R- [0 b: k6 a" Z5 J% {; m; ]
           
    % p% [% n2 Q) D: B9 n        semTake(partId->semPartId, WAIT_FOREVER);. r/ [3 {4 l) S( H' v! C0 n/ I' m
            TASK_UNLOCK();2 W. ~6 k; V' A3 ~$ b

    $ o' w1 V3 M5 S, W' P6 ]        return valid;
    * E$ p- [. {( W$ t- D}. W$ D' q/ v  E1 c: n

    4 K/ a: q+ E/ ustatic BLOCK_HDR* memAlignedBlockSplit(PART_ID partId6 h6 P/ B# w: `5 V/ b
            , FAST BLOCK_HDR* pHdr" p, t! N- |0 L
            , FAST unsigned nWords
    6 _2 p$ K2 e' P# ?9 Y# Y4 O        , unsigned minWords
    2 s+ j/ @7 o1 S8 `- L# D        , unsigned align)
    # Q7 X- |( o% ?' p{9 Q) K! p2 Y, }& k- v
            FAST BLOCK_HDR *pNewHdr;
    ( G) a1 {/ D% ?3 k3 d% z4 ^/ [    FAST BLOCK_HDR *pNextHdr;5 `% q6 i, g6 N0 z! a2 _
        FAST char *endOfBlock;* Z. h: G( t5 e
        FAST char *pNewBlock;
    6 A: r8 Q! F5 Z    int blockSize;
    " b. T; G, L, L- ^0 f5 I% {, x4 ~. q6 c9 o5 I% Z
            endOfBlock = (char*)pHdr + (pHdr->nWords*2);9 q6 A! r0 H( u; L7 ~, E
    5 K& u! F7 D, w' c# s. _
            pNewBlock = (char*)((unsigned)endOfBlock - ((nWords - sizeof(BLOCK_HDR)/2)*2));5 h$ U, D  Y/ ]/ x6 p$ G) n4 q$ \! S
    2 l2 a+ K3 K/ ~/ ?
            pNewBlock = (char*)((unsigned)pNewBlock & (~(align-1)));/ }7 ?! W0 A8 o+ d9 @

    * [) m. C+ n; D- J% J1 F( b9 t* ]        pNewHdr = BLOCK_TO_HDR(pNewBlock);
    + y: O& k& i" d* G- Q1 k) K. s0 {# g
            blockSize = ((char*)pNewHdr - (char*)pHdr)/2;
    # I4 s% Y$ K3 w3 m9 b. }6 q# }6 j
    # ^0 Q: |' U; q& J( k3 \        if(blockSize < minWords); T  p/ w, i- N: b6 n
            {! p, x# b0 c( @8 G7 j4 n
                    if(pNewHdr == pHdr)* J! W( O7 p0 \  }. o
                    {$ N8 W/ b2 j" _( ?3 x
                            dllRemove(&partId->freeList, HDR_TO_NODE(pHdr));2 K/ B# V: \1 o, |( e! o
                    }3 L: c8 l6 a% I. E) Y9 r3 f
                    else* ^2 q( C4 D% ~7 [
                    {
    5 C, c! _$ t& d, Z5 F7 b! P% d0 ^; J                        return NULL;
    7 c7 C' j* i3 F' M$ {                }
    ! r! l, }" ~7 w* U& M* _2 \7 N3 i% m        }
    / M+ J1 y9 }) j- H) X        else
    " M( }) E$ p7 Z# R$ ]        {        /* recaculate pHdr */
    ; N3 K" Z" @1 X) X" |: j9 L                pNewHdr->prevHdr = pHdr;
    9 b; |" h. k: ]  i" m. a4 a! ]; S& Q                pHdr->nWords = blockSize;
    - z) e: P0 s+ f. S4 r$ v# E        }' Y- s+ A. j8 x: N* V7 J

    4 N9 a3 j% \7 g        if(((U32)endOfBlock - (U32)pNewHdr - (nWords*2)) < (minWords*2)); {; G+ r0 l5 N& y( w- U% s* C
            {
    2 y/ s6 L& |2 P6 T3 J% d# d0 X                pNewHdr->nWords = (endOfBlock - pNewBlock + sizeof(BLOCK_HDR))/2;7 q4 c( F1 j$ G6 d1 t4 U. N
                    pNewHdr->free = TRUE;' K. C+ ]* T, ?& _
    0 ~0 b  _4 V' o. m  G4 t
                    NEXT_HDR(pNewHdr)->prevHdr = pNewHdr;
    7 ]1 _( k( r+ g+ G        }
    . b! \% g( K; h0 S0 u8 _: ?2 U        else
    ; b* x; {2 x! c  d. z        {/* space left is enough to be a fragment on the free list then */
    . O& x% h0 [& T  E1 D, e$ }                pNewHdr->nWords = nWords;
    * f7 K) d. C- N( {% o/ M0 \                pNewHdr->free = TRUE;
    ' r8 V; S) w5 u4 ]! ]7 k  ^" ]5 n1 K0 S- k9 D# n( M0 e2 V; @
                    pNextHdr = NEXT_HDR(pNewHdr);
    , ]) H1 s% I. X) e8 }& ?/ }                /* words 包括BlockHdr */
    3 z! B, E) j! \% P2 @                pNextHdr->nWords = ((U32)endOfBlock - (U32)pNextHdr) / 2;
    ( P& r  f" U3 b* b9 v5 \                pNextHdr->prevHdr = pNewHdr;
    ) t( K1 q$ k* z( [6 ]& `, [3 C2 n                pNextHdr->free = TRUE;1 b# f$ d: h! L" V9 l  u
    & j6 O  b5 n$ A( f
                    dllAdd(&partId->freeList, HDR_TO_NODE(pNextHdr));
    % C2 v& Y& \) D) \, k$ `/ [4 F* j5 r& E) N/ y
                    NEXT_HDR(pNextHdr)->prevHdr = pNewHdr;: W4 x5 i) U1 B5 r8 i3 |% b
            }' D$ L5 c5 i2 p+ s' i9 p
    * l( J. Q) O0 K' X  A) i. B* G
            return (pNewHdr);: [8 J# {; w, W( q+ j4 Y
    }
    , q/ Q; G% E# B- k) v6 I- i" [7 R$ q8 m6 {: @% _' X) w! R% O
    static void memPartSemInit(PART_ID partId)* v2 g8 r7 B$ V8 S) h
    {3 @# q% U( W5 N% j
            semBInit(&semMemSysPartition, SEM_Q_FIFO, SEM_FULL);
    - j0 Q& [9 F9 [* J' G  b/ x1 N8 ^; J- _1 ^! A: n
            partId->semPartId = &semMemSysPartition;
    # M! M* w% `' x* G- q4 }}! y  V4 I% [8 V& w
    # E1 x  \) O7 M/ {8 m
    void* malloc(unsigned bytes)
    % ~8 s0 _$ v6 _! J% v2 c{
    8 k/ _8 P1 O8 D! R        return memPartAlloc(memSysPartId, bytes);
    : U1 b8 v( B, l9 r' ~. m- F% W3 G}& w4 Y% @# g% t; m$ ?7 [; L
    ) U: a% X& v, X, K* R
    void free(void* p)
    $ l- h. Z' r* @, D# i{
    $ B0 M" d8 c7 s" F3 P# f* f        memPartFree(memSysPartId, (char*)p);
    9 `0 u+ z9 N! N- s}
    ' I, X0 a$ M5 [8 o! m( @, p  d
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-7-26 22:49 , Processed in 0.337227 second(s), 50 queries .

    回顶部