数学建模社区-数学中国

标题: malloc(内存分配)在嵌入式下的一种实现 [打印本页]

作者: wangzheng3056    时间: 2013-7-26 10:17
标题: malloc(内存分配)在嵌入式下的一种实现
想知道malloc是如何实现的吗?这里是一个简单版本,所有的功能都在这个文件实现了。如果你对malloc的原理有兴趣,可以通过这个代码窥视一二。实际上这个实现是著名的嵌入式操作系统vxworks5.5以前的内存分配版本。这里我已经把它实现的更简单易懂了。当然我还有移植到vc++下的版本,更方便调试。有需要请留言
2 F6 T" K+ W. {" d8 @9 G; ~; g2 ]. V
6 N0 _, B& b9 L( M! f

/ p/ T+ [/ |+ Z *\file& @2 [  D+ q5 d; N& ]# [) J; Q
*\brief               
9 X& ^4 m1 R' L* W# T" U+ M *\details        9 P* e8 X5 h1 j7 L
*1 V+ k2 o' E8 k
*\author        Janson* @, s5 `) i$ }1 I
*\version        * m7 t: y8 t/ I. F6 p9 P
*\date                04Jan12
8 u( U5 z7 ?  P6 M. z4 N1 f' I *
+ Q  M1 y( O6 Y5 l *\warning       
% U# K/ X$ Z; `9 s- h& N$ _9 R9 w *
) R9 T/ `$ E4 c- C* s7 G *\history \arg        30Jan12, Janson, Create the file6 C/ {1 k4 V/ ]9 T. N
*        modify from VxWorks source
0 u+ \2 n/ U0 f) Q% B *  Legal Declaration: it is for studying VxWorks only.5 O- B) }  X+ y# |- v" `, e1 ?
*/
% s- `& }( @* W! w. M#include "includes.h"
( P( |# j! Z3 o, Z7 Z
  f" r4 n  |! t! g& P3 S* d/* The memParLib.h file is hear:
8 K9 C6 X- J1 D+ f2 j* ~https://code.google.com/p/vxwork ... rivate/memPartLib.h
7 F& A& b8 {# [; Z( K& ~' ~# j*/
3 }% Y  ]) o7 \. F6 i. T5 ~/ q0 Z- }) `4 C; _  q3 o, Y* d
/* optional check for bad blocks */
; O2 t# @8 f! f5 F, M9 f
( {& `# w" S- k#define MEM_BLOCK_CHECK                        0x10
, O) Q& @3 x$ [
* X3 w, l8 b! g5 z" S" t/* response to errors when allocating memory */: V+ Q# {6 G0 e' B% w# ]$ ]1 s
& x( ]3 j, u7 F6 D1 j
#define MEM_ALLOC_ERROR_LOG_FLAG        0x20
0 D/ q# {, s# w5 ?  p8 H0 \/ u#define MEM_ALLOC_ERROR_SUSPEND_FLAG        0x405 M. V7 e' ~+ u# @3 y! O# q
/ N# G3 T# C9 z1 Z- }' X' ?
/* response to errors when freeing memory */
) K+ Q! R3 e! t7 T- \% \/ f1 s& o# h8 h2 ?: n* a
#define MEM_BLOCK_ERROR_LOG_FLAG        0x800 K( k/ m0 D/ c' j2 I- C
#define MEM_BLOCK_ERROR_SUSPEND_FLAG        0x100
5 }# Y" V- s( w- p- w# n8 D, P% j6 `
3 J: u( |6 q( K- E  @#define NEXT_HDR(pHdr)  ((BLOCK_HDR *) ((char *) (pHdr) + (2 * (pHdr)->nWords)))
  z  i. C! M' Y1 p7 [#define PREV_HDR(pHdr)        ((pHdr)->prevHdr)2 p4 u" ?$ J* F1 d4 a) ]
! p2 M8 p9 C* Z4 K5 z
#define HDR_TO_BLOCK(pHdr)        ((char *) ((int) pHdr + sizeof (BLOCK_HDR)))
& o/ B% x( \( P$ }" T/ R; s9 x2 y#define BLOCK_TO_HDR(pBlock)        ((BLOCK_HDR *) ((int) pBlock - \
. E1 p2 Y  T+ N" `: w& d, Q! `                                                sizeof(BLOCK_HDR)))
# e0 `. w. `% i7 o# K) h! p1 R: P4 F- f
#define HDR_TO_NODE(pHdr)        (& ((FREE_BLOCK *) pHdr)->node)& o( N  T" v8 O& x; K0 h
#define NODE_TO_HDR(pNode)        ((BLOCK_HDR *) ((int) pNode - \& ]) |% |8 P; o( L) \; q
                                                OFFSET (FREE_BLOCK, node)))/ v- X0 \" `9 V
4 R+ b7 f9 r- `  N+ i( ~
static BOOL memPartLibInstalled = FALSE;1 w; t. X2 D; C. ?8 i" I
2 B& _' w) M  O, O& [
static OBJ_CLASS memPartClass;
* F  k2 D; B1 nCLASS_ID memPartClassId = &memPartClass;
+ k$ x# G  Y8 f, u* V$ C4 b, b: O) `* T: O/ H8 y
static PARTITION memSysPartition;0 ^0 n, j5 \9 o& ?# r) M
PART_ID memSysPartId = &memSysPartition;( h+ y: ~9 x; X, F/ J7 M- u
U32 memDefaultAlign = _ALLOC_ALIGN_SIZE;: I( E( f& O) \3 Y( U/ _4 P

% ?. F+ x9 z6 t( b7 dstatic SEMAPHORE semMemSysPartition;! ^! ]% g6 _9 K2 C% F
8 s, B+ R8 _/ q0 q& X5 S& |
static void memPartSemInit(PART_ID partId);
  C+ X8 U- ~" q9 U) `$ m) g/ N2 T# b/ E6 b" B; _! s
FUNCTION  memPartSemInitRtn        = (FUNCTION) memPartSemInit;
- v: \. h/ J; R2 ?, `$ S1 G& m1 Y$ A( @+ O6 Y
unsigned memPartDefaultOption = MEM_BLOCK_ERROR_SUSPEND_FLAG | MEM_BLOCK_CHECK;
$ N2 g  ~/ Z3 M0 J! N
! t$ \3 d) [- [" L! W: O2 cstatic BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree);
# z( _2 _0 [4 H% z) pstatic BLOCK_HDR* memAlignedBlockSplit(PART_ID partId
8 ?. X. F6 O5 K. n. K/ S' c. Q        , FAST BLOCK_HDR* pHdr
, P6 {. G0 e: X- s; q% j2 ]        , FAST unsigned nWords
% t2 J& X/ l+ L) F9 V+ j# X0 g        , unsigned minWords4 _5 h% T. y0 @+ D
        , unsigned align);
9 L7 a* H2 b2 d# ]
5 _! K" e; E; mstatic STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize);
  q& c  R% r7 p) N: U% y+ ~0 {6 e
STATUS memPartLibInit(char* pPool, unsigned poolSize)
$ O, @$ I* D" W2 C" B0 G/ l% e{# q+ {8 Q& D3 X+ h' D5 w$ t8 b
        if((!memPartLibInstalled) && - X/ n! m! y" A  g0 H
                (OK == classInit(memPartClassId, sizeof(PARTITION), OFFSET(PARTITION, objCore)9 s) R! Y' |# G
                , (FUNCTION)memPartCreate, (FUNCTION)memPartInit, (FUNCTION)memPartDestroy)))
  ?6 G) Q  c# v3 m        {
0 l( k/ X6 \3 e1 C- U2 g4 V                memPartInit(&memSysPartition, pPool, poolSize);
$ Q+ A# U8 I/ @$ i                memPartLibInstalled = TRUE;4 j) {6 t- F: o1 E
        }# v( [, E$ Z& J+ j# I. t

: @; U( m) S1 O/ K7 J  R        return ((memPartLibInstalled)? OK : ERROR);
6 G" L4 W' s' g}( e7 K2 T: D2 p/ j- w. e0 S

: M1 {* y, N0 z0 U% wPART_ID memPartCreate(char* pPool, unsigned poolSize)6 w; Q+ J7 d' U0 g0 h0 P" X
{
, r$ e( b3 _* r% Q; ]! T        PART_ID pPart = (PART_ID)objAlloc(memPartClassId);& R: t% i, U) s& x7 D4 E
4 F4 b7 J$ f1 T) C5 Q0 |* |
        if(NULL != pPart)1 {7 }6 t+ v2 ^( m
        {% @- [+ w0 t( P
                memPartInit(pPart, pPool, poolSize);
; W2 s1 Y6 T( y, F! H        }
3 t- M4 B) ^9 C
1 w* J2 N+ ^0 s, Q- F% W5 x% ^        return pPart;
$ e9 L8 Z# h: k8 F" }+ V}
7 s& m! D% I& I( k, w
3 h6 F# g6 s( O# P! {void memPartInit(PART_ID partId, char* pPool, unsigned poolSize)7 n# H# `- V% Y$ Z
{' U! \  d% Y7 ~, l' y3 o
        memset((void*)partId, 0, sizeof(*partId));
2 w3 S7 N5 d) J% f* F
0 |* n8 N; G' Y% x2 H; h        partId->options = memPartDefaultOption;7 K5 ^. q9 ^" ^, O. X+ l
        partId->minBlockWords = sizeof (FREE_BLOCK) >> 1;        /* word not byte */
5 V) J1 ^/ U5 g1 L& X% C- e5 _$ s/ M$ {8 z9 [) V( x4 w
        (* memPartSemInitRtn) (partId);  O+ T% Z+ V$ \
       
1 m8 Y, R  y2 ~- H! ?( T        dllInit(&partId->freeList);. {' r8 W# U7 m1 r9 V/ K
       
9 Q0 J8 Z" t, l1 }0 o3 f  X% j        objCoreInit(&partId->objCore, memPartClassId);  t1 N# o! M' O) ^9 [' V" r
        , {* Z, ~" ^3 G- ^0 }
        memPartAddToPool(partId, pPool, poolSize);
7 U, J1 J6 e4 i& l* g3 ]}
7 D! M0 D, w; k$ y) t: S
% ?) C) D; W+ @" f  qSTATUS memPartDestroy(PART_ID partId); [; ^4 _6 K8 u
{
5 g- w( a8 F- G. N6 v3 W3 H8 C        return (ERROR);' O1 p" V5 D* Y/ u& n
}6 A2 C6 L$ B" m! F1 J( T1 R4 ~  n& L
- w4 N0 D6 c8 g& b
void memAddToPool(FAST char *pPool, FAST unsigned poolSize)' ~$ l. E" t; k2 g6 f
{5 V3 z$ K+ H' j" D- v
    (void)memPartAddToPool(&memSysPartition, pPool, poolSize);" y+ e- T- S# K! e$ Y. |
}
" f* G, p& y9 N- ?, s6 `
; a% w: W' }/ ?3 T! `3 A1 C( Y4 r7 }% m* M+ h: }
static STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize)
& ^! l8 o& K; X) ~- F{' }1 r! R/ x0 r0 e' @' i) Y
        BLOCK_HDR* pHdrStart;
: J* R8 r+ q* b        BLOCK_HDR* pHdrMid;
! z& {/ f( B: |) C! o' O        BLOCK_HDR* pHdrEnd;5 C) l8 {0 J+ n) ?/ T& \
        char* tmp;9 u, `2 L2 C1 n4 }5 {
        int reducePool;
: ~! t$ F& Z* B; H4 p; J0 Y9 d/ u+ m! P6 c7 ]3 h( M
        if(!(IS_CLASS(partId, memPartClassId)))        /* only memPartClass can call this function */
1 a5 V1 x0 D- ~9 q4 P        {* Z! \( K$ O0 |/ b
                return (ERROR);$ W5 E, C+ i8 k% |3 V
        }2 L& N6 m/ N4 n+ u& o% e

% q5 }- Q  [' B$ Y% a        tmp = (char*) MEM_ROUND_UP(pPool);6 b+ r6 o) N# y. e$ @
        reducePool = tmp - pPool;8 w' x5 X( f+ c0 Y7 _4 U0 y  a; V( l) z
5 D+ A2 v  q- G" s6 a4 v6 U: t
        /* adjust the lenght */7 g: A- {+ e6 p+ q7 P& F, O; F
        if(poolSize >= reducePool)
3 V) Q& c, [3 W" w% Z  Y        {
* d7 u5 c" n4 U" D/ I3 z                poolSize -= reducePool;: P4 H* q2 c" i; d6 z( S
        }
1 R* V2 W5 V( r0 ?" n        else
- b* T' |3 a& a        {3 _! C& N% F8 |- \8 P! `) u
                poolSize = 0;* u6 N) {7 [/ g8 K* G* _$ e# @
        }
. v) \; @' V8 a- w. J        pPool = tmp;; L/ i. u# ?2 S5 o+ F8 g# h' L2 T
       
; i; d" `: U0 Y% f9 ~) o3 _# O        poolSize = MEM_ROUND_DOWN(poolSize);0 P) |6 a& B' B. L+ m7 w3 X
       
2 i& f7 T1 a; ?' c* s        /* at least one valid free block and three header blocks */. I( U; p  }5 B; V1 |$ d
        if((sizeof(BLOCK_HDR)*3 + (partId->minBlockWords*2)) > poolSize)3 S5 Y  X4 E0 j, V1 u7 z7 e
        {
: v% M8 k+ H- Y2 x( B                return (ERROR);* O+ G6 ^! A* l
        }* k& A( g1 U( c* s2 i- o( s. a

1 }5 z3 d" s% u' U        /* initialize three blocks */  E; r7 a! i/ y% y4 A2 j8 X
        pHdrStart = (BLOCK_HDR*)pPool;
) J% A( p( ^6 }0 t: w9 K6 }7 p& A        pHdrStart->prevHdr = NULL;( P' d# ]( p$ Y- K4 Q& D
        pHdrStart->free = FALSE;                /* never in use */7 _( g3 {0 H" f, D) ]5 i* M2 U
        pHdrStart->nWords = sizeof(BLOCK_HDR) >> 1;5 n: e  W4 ^$ M$ E

3 `' I* k  h' L8 Y" F, p        pHdrMid = NEXT_HDR(pHdrStart);  J: W6 O3 e* ?
        pHdrMid->prevHdr = pHdrStart;3 b- {3 D: }/ J/ X+ {0 v/ ]4 B
        pHdrMid->free = TRUE;                        /* the main block */3 |2 Z( ?' ?( q  ^7 X5 n' i9 r
        pHdrMid->nWords = (poolSize - 2*sizeof(BLOCK_HDR)) >> 1;
" Q; @- L: i. C& {7 S( t1 P" c0 D, q: v2 T2 n! E
        pHdrEnd = NEXT_HDR(pHdrMid);
7 I- Z1 A5 W0 h5 T8 F! J* g) g        pHdrEnd->prevHdr = pHdrMid;; ^1 R7 v2 A- O6 B% m
        pHdrEnd->free = FALSE;
& Q( l6 R' r: {5 f8 E  P2 c        pHdrEnd->nWords = sizeof (BLOCK_HDR) >> 1;
1 E( n7 s% `' F2 l$ H5 q# h  P1 x
# a/ P' o( _. A' ^        /* TODO take sem hear */1 E: v, D) a8 P9 n9 S
        semTake(partId->semPartId, WAIT_FOREVER);2 C4 O0 e; r- f: w7 T2 o
       
& p. O! ]; u; v! M+ I2 i        dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdrMid));$ J3 }! s/ t6 Z
        partId->totalWords += (poolSize >> 1);4 u* @1 t0 {+ ~0 A
+ U2 m0 u' N' `" {/ w" ^
        /* TODO give sem hear */
& f$ S; r. E. q) ~: i        semGive(partId->semPartId);
6 _$ Z4 I3 h/ d- N/ N$ t& n3 |7 v9 p

, ]3 h% l$ v3 D0 a' O# V' C+ n        return (OK);* j, Y; m& [2 T* @; s7 O, x5 j: n
}2 O# `4 j+ ~8 B& E! T4 r$ A
: L& |* P& D$ {1 k
void* memPartAllignedAlloc(FAST PART_ID partId, unsigned nBytes, unsigned align)' v$ ^! \" c* V6 e# L
{9 n! H6 |+ `# f$ C! ?# W( s
        FAST unsigned nWords;
+ l7 ?8 p& `1 U, o, s% Y        FAST unsigned nWordsExtra;
2 a3 T, K: W) A# F        FAST DL_NODE* pNode;+ ]  o& o5 ^" u! g+ f1 n1 v+ A
        FAST BLOCK_HDR* pHdr;7 r6 g8 j, E# @3 R" }( O
        BLOCK_HDR* pNewHdr;% N7 B8 I4 |! w; S
        BLOCK_HDR* origpHdr;
0 ?, |- ]6 Y* B0 W# |5 v6 G) H
5 T/ [# s/ P" H5 i6 G        if(!(IS_CLASS(partId, memPartClassId)))        /* only memPartClass can call this function */
: u3 e" ?% M( X$ H0 y        {
. O' |' ]: \# D$ E% n3 M7 [  ?                return (NULL);
+ w, B8 z% h3 p  t% x        }) C$ Z/ B3 A& q0 y" A
* O( F. ]  U, a* x7 E: j8 G
        nWords = (MEM_ROUND_UP(nBytes)+sizeof(BLOCK_HDR)) >>1;
6 \$ s8 n* j9 P, H# R+ n' w, I% `" k; e$ b
        if((nWords<<1) < nBytes)
0 |" T) s. d: p        {
  `" f* v$ X8 r5 g0 \6 ~                /* TODO suspend the task */
- C$ @7 F2 p) U  t6 }                return (NULL);
1 U) t* O- |5 R. z        }* M6 l- p2 I! T0 ?3 _8 ~  d, h/ x

# {4 u1 O0 ?/ V9 E        if(nWords < partId->minBlockWords)7 U' w+ t: |" E& ]5 {! y. b& v
        {3 B6 u2 ^! J0 ]) U. t$ T. W
                nWords = partId->minBlockWords;) l: V: k* [! }
        }
2 x! L' {) X6 w9 W9 |2 w1 g1 H9 {0 l. r: h& t6 s- F
        /* TODO task the semaphore hear */
, e  p) B) }8 J0 X, L9 U+ H* l        semTake(partId->semPartId, WAIT_FOREVER);2 }) Y# Q- o7 t2 }2 K. @
        pNode = DLL_FIRST(&partId->freeList);
9 u6 A& K( S& t- k0 n: h        nWordsExtra = nWords + align/2; /* why? */
5 Z* \# A& I1 [( n5 u- V$ C9 z: a- q* E, N' f, j0 ^  o& Z3 S" T& }
        for(;;)
5 A) m5 f7 J' P: d7 |5 k; N        {$ W  V( V' m, ?6 K0 z( I. U. @* D
                while(NULL != pNode): n/ s) _8 _* [9 g
                {
! B, x) v" w% r0 g                        if((NODE_TO_HDR(pNode)->nWords > nWordsExtra) ||9 B6 P/ B* c& O8 a- x
                                ((NODE_TO_HDR(pNode)->nWords == nWords) &&
( J  q& k+ G1 P) m! @$ T0 o                                (ALIGNED(HDR_TO_BLOCK(NODE_TO_HDR(pNode)), align))))/ y( B& X+ M8 h0 t/ {
                        {' C6 X/ S9 s) J) U: N/ D2 k" l
                                break;
% L; J5 X9 c4 X' r  s                        }
. m& t" a7 m3 H" l; g
& Z. _4 }( w/ S0 a" \+ y  f7 O" Z" Q                        pNode = DLL_NEXT(pNode);  M" }# {* x) s& Z: ]# ]% Y/ b9 z" P5 a
                }
# ?( l- i+ @4 b; x7 w3 x0 c- L' Z) S% B% b1 h( i
                if(NULL == pNode)
( Q+ e% C! R0 W2 D1 D7 Z                {! I1 I/ w' `8 j$ o4 I6 W; J
                        /*TODO give the semaphore */
. f( _2 I( Z3 d- s5 {" }, }. o                        semGive(partId->semPartId);8 k% }# Y' D; C- V$ {# i
                        return NULL;4 y# I/ K* j! x* p
                }
& Z5 l8 G" z3 y/ Y+ e/ i) v  S, x
5 Z0 G7 c3 p4 h, F" [5 B                pHdr = NODE_TO_HDR(pNode);: ?3 w$ w) a8 C" G" V
                origpHdr = pHdr;; f2 c  |0 R; R0 u$ n

# q. J$ J7 d+ Z( w( q+ {, x" @; f                pNewHdr = memAlignedBlockSplit(partId, pHdr, nWords, partId->minBlockWords, align);- T1 O: @+ z4 b* ]; d& W
                if(NULL != pNewHdr)! q+ ^. o$ b! J* e6 R
                {
/ z' J! ]  T  B6 r! E  q' p                        pHdr = pNewHdr;6 T7 o; F4 e! m6 Y2 N  D
                        break;4 K; j" x# Y& N
                }
: a! L3 Z% s4 b, t; D; U
8 i+ I% c" w* u* O; u& l, E% Q                pNode = DLL_NEXT(pNode);
! e6 k! \* o/ M        }
& a! N" i9 w, r
: v/ Q0 \0 e% }0 e! ?  Z4 @% R        pHdr->free = FALSE;6 Z( k3 |# L; x% L; z" t
        partId->allBlocksAlloc++;$ }( X% O8 \% B, ^/ k
        partId->allWordsAlloc += pHdr->nWords;
" `& N3 t. h) _/ d( J) R, Y/ O        partId->curBlocksAlloc++;
! w1 M6 K6 d2 v. P8 r% v2 C2 c        partId->curWordsAlloc += pHdr->nWords;+ l7 k, K# r% s+ d2 B1 Z" P
6 j/ ]! O1 h) ]* M$ R
        /*TODO give the  semaphore hear */
$ r* T: H" y8 i7 A2 d5 n" S. i' O        semGive(partId->semPartId);
. }- h, r6 b) J        return (HDR_TO_BLOCK(pHdr));% b$ W% G& x  r* @" }3 B" b9 r
        . k  Z5 h& H/ k" o0 H0 w# ^
}
; k4 X* Y# ?+ w* e" f! G" Y
  s4 s+ @3 t# M4 {, s  g6 O+ kvoid* memPartAlloc(FAST PART_ID partId, unsigned bytes). [+ _2 i9 y# y' {1 }5 I3 w
{% }4 H$ t) e7 I( |; `% p$ Y: R
        return memPartAllignedAlloc(partId, bytes, memDefaultAlign);
; b2 o# S- H0 d% X2 i" T$ Z: p$ h}
! D/ P# ^5 B; O
& \2 S. G9 T7 P! BSTATUS memPartFree(PART_ID partId, char* pBlock)1 A* R2 T2 r2 f0 y1 h% S' y
{$ R$ ?9 r3 S, N
        FAST BLOCK_HDR *pHdr;. r1 \# ~' s/ k$ B
    FAST unsigned   nWords;0 f$ E" [. U; i& l* C6 a
    FAST BLOCK_HDR *pNextHdr;+ _  v/ A  y( T+ x3 H' y

1 }! e( g% E( s        if(!IS_CLASS(partId, memPartClassId))
1 M4 X+ E$ G/ Z3 S% q; c" r: V        {
% v) P. ~7 V9 G                return (ERROR);
- V& m" Q1 o. J1 l+ n        }: v* D% R5 A  P7 g/ S$ c
) R- b( X/ g  v: O% s
        if(NULL == pBlock)
; q3 x  N5 e+ ]+ h9 P        {
& _1 H/ ^7 j( j# s( L# s  _, Z8 f                return (OK);. p# U- |& m( |2 Z1 {
        }9 Y3 e( ^# C, _5 ^" _
+ c( w+ N9 U- U. E( e+ [/ Y/ [( j/ z
        pHdr =  BLOCK_TO_HDR(pBlock);
6 ?; ~" m  {. u! y+ U( ?8 Z( X
& a+ M* Q: _( }6 w0 F        semTake(partId->semPartId, WAIT_FOREVER);* e4 T, }; `6 x" N' y

: T4 R2 S( W- n  r/ i& [        if((partId->options & MEM_BLOCK_CHECK)' M& A9 H+ s3 L- i  m; R
                && !memPartBlockIsValid(partId, pHdr, FALSE))
9 o8 k* e6 k& `4 Q8 B        {
# Y0 ?  G  d) u5 S6 k( f. t- V                semGive(partId->semPartId);
' o: }" N7 q2 L7 L" x" p$ P                return (ERROR);- r3 z  E. y& _% ]3 e  T
        }
; O% {4 A) w2 `5 u
7 u6 Y0 i5 C3 C% O1 D% R% Z2 ^        nWords = pHdr->nWords;
8 s8 \/ i7 F$ N4 R7 u7 A3 O# l        if(PREV_HDR(pHdr)->free)& }& S% K( s' I2 R* ]8 W& W
        {/* the prev hdr is free and than coalesce with it */3 h, y* x# J% v& q8 m* d% F+ I4 V
                pHdr->free = FALSE;
, O$ [* |" q, H' M                pHdr = PREV_HDR(pHdr);
) r' T- A% i- }: T1 |                pHdr->nWords += nWords;
$ s! _5 O* u. v6 j        }7 I; R0 `3 ?  f; S
        else
8 E# W0 I5 l4 @+ R        {1 ^6 T/ Q' ?! [: r) c
                pHdr->free = TRUE;
, x  A. e1 L3 F7 w& R+ v1 k1 U                dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdr));
6 Y2 F  c8 g/ P        }
$ K( T0 G6 r# t7 R! }! u
7 J" `2 @# O: m  e9 l4 w# [        /* check to coalesce with the next */: K# e, ]# H3 @1 U. b8 \
        pNextHdr = NEXT_HDR(pHdr);- A4 A  M4 q) ^! n1 x
        if(pNextHdr->free)
: a5 j* e) U: n2 j1 K( _* E8 @        {
) c2 m& t! N: s/ z9 B/ |9 @                pHdr->nWords += pNextHdr->nWords;7 N4 C7 m6 K9 L3 O/ v
                dllRemove(&partId->freeList, HDR_TO_NODE(pNextHdr));" @. O( D* \2 H) x
        }
' _+ @5 a( E% i; E& o
4 H8 u) A; @  ?5 ?. B        /* cannot use pNextHdr->prevHdr=pHdr hear */+ M" }6 M" d8 ?0 `* a
        NEXT_HDR(pHdr)->prevHdr = pHdr;5 H; Q# @6 ]6 Q( }

3 h. B& {0 P3 i6 \0 U3 w, J        partId->curBlocksAlloc--;
1 b9 g7 X* h) @, h# H+ ]+ {; _        partId->curWordsAlloc -= nWords;5 Q4 d6 }% i) b$ ^

; T5 \' ~" ]0 `- j7 v        /* TODO give sem hear */: e% {' q5 b% O
        semGive(partId->semPartId);
$ s! E$ @/ L* C8 j" G        9 B3 P- f" D- e- u2 w
        return (OK);7 O  B) F5 Y! u
}
' A5 d4 Y# V; b7 L" A8 s, ~. E7 c: n! k# d4 J# q
static BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree)
" A: ?: W# l# V/ v! a* G1 O{; r+ v$ \; C9 a3 @' j0 W
        BOOL valid;# y3 e. W9 v2 M
3 ?9 n& W+ D! D5 I, H
        TASK_LOCK();' k& F# b: h& n3 W! G# ^! o6 ^
        semGive(partId->semPartId);) U: U9 l- K! S3 x
        ! ^' y& T1 _0 T: I
        valid = MEM_ALIGNED(pHdr)/ z: W, m. c' a8 k" _
        && MEM_ALIGNED(pHdr->nWords*2)
0 }6 i3 L) n$ V! Q$ l  Y        && (pHdr->nWords < partId->totalWords)
1 l- r6 q7 `4 V        && (pHdr->free == isFree)
( C3 m% m% N# l% Y) @- V        && (pHdr == PREV_HDR(NEXT_HDR(pHdr)))
7 R$ [4 M7 B1 N" H  S1 L: h8 d% V  _7 O        && (pHdr == NEXT_HDR(PREV_HDR(pHdr)));
) I/ r6 s. d& ]$ o. w        0 J9 Z1 T) L/ V3 T
        semTake(partId->semPartId, WAIT_FOREVER);2 Y6 q/ T0 v+ y
        TASK_UNLOCK();
4 d* \) I1 x2 e
' u7 Z& |2 F7 w3 z& n5 y2 F        return valid;2 e: ^4 ]3 L) J7 P4 }/ c
}
' ?+ X  p* f9 W9 e. K  u' Q: U2 Q
- n% M+ a0 f" b8 X% ystatic BLOCK_HDR* memAlignedBlockSplit(PART_ID partId
: ~$ Z8 ]. b( z# ?' A- M& `- c        , FAST BLOCK_HDR* pHdr& k0 Q4 _  K6 {- O
        , FAST unsigned nWords
$ g$ ~6 g# W, n- }* `        , unsigned minWords" P) Z* Y- N; Q
        , unsigned align)- \9 C0 R+ V* G
{) C( ^$ m& a9 t# Q8 w- F
        FAST BLOCK_HDR *pNewHdr;' j; O7 G6 ]  T. d( P; m+ I7 h
    FAST BLOCK_HDR *pNextHdr;
" I$ Y' A8 m9 X1 V, |# e5 Q    FAST char *endOfBlock;
8 S0 l1 H0 z; \  W+ c' @    FAST char *pNewBlock;7 P  b2 {& }6 O3 }: _
    int blockSize;
5 W" N" s. M. ~. h/ F7 s! O$ H. `* c0 [$ B6 B* Z! ?$ }4 R1 r$ l
        endOfBlock = (char*)pHdr + (pHdr->nWords*2);
% g0 ]/ `0 z6 }( r( X  E7 A3 ~. X) v8 f3 ]
        pNewBlock = (char*)((unsigned)endOfBlock - ((nWords - sizeof(BLOCK_HDR)/2)*2));- w+ E( O+ ?- Z) S  e: F

; O& Z7 l' M1 j3 p4 \) u6 a        pNewBlock = (char*)((unsigned)pNewBlock & (~(align-1)));
! h% Z* p! o0 y3 M$ F6 S* d5 G0 ^' z+ Z9 Z+ U
        pNewHdr = BLOCK_TO_HDR(pNewBlock);# e1 h6 A8 S* c3 H! B% _  M
% v# i# j& m1 O9 z% S5 [
        blockSize = ((char*)pNewHdr - (char*)pHdr)/2;
3 I5 {* e5 B+ L0 b5 y
5 o1 f% f5 H& I! |1 D: p5 E        if(blockSize < minWords)
! l' K) e! g2 O8 X- N4 N        {
9 T8 `" ]/ {, p                if(pNewHdr == pHdr): N5 ?* O% L; L5 N
                {
9 U* a4 S# s1 \+ C                        dllRemove(&partId->freeList, HDR_TO_NODE(pHdr));
0 M8 r: |0 l) T# P* `4 b& R                }* E( {4 N1 x+ R- e9 [) i
                else! k1 P8 n3 K5 j4 l2 _6 p; y* z
                {
  y% {* i- w5 {' [0 S5 }& @  [6 s                        return NULL;& [4 A: T# E8 k9 a/ L" W& O: W' p
                }
/ G" e1 @# D0 b" ~6 v. p9 e        }
: d: E* u; B0 C$ }4 O$ U/ w        else
% ^! e: B- g( ~( R        {        /* recaculate pHdr */
: }$ p' @" b) S9 d" P                pNewHdr->prevHdr = pHdr;7 ]; l0 k* d, Y2 B
                pHdr->nWords = blockSize;
! q# o5 W0 I% t5 l        }" u) [8 o: ^% T. k  }
( A. v4 L, {" V2 ~# ]: J2 A; r0 q
        if(((U32)endOfBlock - (U32)pNewHdr - (nWords*2)) < (minWords*2)), G- s: |4 m3 [" C* Q; G
        {
3 u. A/ x8 Z9 a$ @                pNewHdr->nWords = (endOfBlock - pNewBlock + sizeof(BLOCK_HDR))/2;
# i6 i3 {9 K! e8 ~3 R6 o* B                pNewHdr->free = TRUE;
8 t- U2 ]' I  y8 S9 J: c; J- E& Y7 U! L# k4 D" B5 M/ E$ D2 X$ T
                NEXT_HDR(pNewHdr)->prevHdr = pNewHdr;
& X, e& q3 P* O        }
# {& P) z) x& }6 W7 o* `3 v  r9 D        else
# D  n. V: G1 ?% d: {7 {( A        {/* space left is enough to be a fragment on the free list then */
4 m& q9 b5 y. A5 L                pNewHdr->nWords = nWords;/ ]! G' k% W9 i3 A3 m
                pNewHdr->free = TRUE;
# S& n( [# L( T5 M  i
7 A# O/ ^6 W% S' A: D                pNextHdr = NEXT_HDR(pNewHdr);4 X. K( I7 L+ P4 @- v
                /* words 包括BlockHdr */
  w" K" W/ P; E! _+ E! o3 h                pNextHdr->nWords = ((U32)endOfBlock - (U32)pNextHdr) / 2;
0 _" @' ^  S2 m$ u# [" u                pNextHdr->prevHdr = pNewHdr;
3 u7 V( k. w' I0 \# V$ p, j, W                pNextHdr->free = TRUE;' ?6 A( b1 A, {3 J- m9 k

0 ^/ y+ t, T3 y0 K" D$ t& p                dllAdd(&partId->freeList, HDR_TO_NODE(pNextHdr));; {% C5 h$ }1 N& o/ _" t: x+ o' G1 Q: q

3 H6 f1 C, g/ q! Q; T" v                NEXT_HDR(pNextHdr)->prevHdr = pNewHdr;
/ S2 _+ {, a4 u# e) S% k: p        }. N) g& ^- C! c6 i& T

% c! A: d% E4 H6 k6 W! p/ c9 w        return (pNewHdr);, B+ q  A, W( T& N# X6 @
}0 M+ P* T+ }2 l2 K3 k" Q4 G2 i

8 m4 t3 S7 z2 e* I# |3 D7 P% _' Hstatic void memPartSemInit(PART_ID partId)
) A' W5 N& o. B- D{% P. l" C  ^. B5 {) M) C( C
        semBInit(&semMemSysPartition, SEM_Q_FIFO, SEM_FULL);/ z7 c/ I: W$ A

+ S" s  A: z7 [$ }3 r- D, x+ I        partId->semPartId = &semMemSysPartition;& g4 ~1 J1 b& [) z* i/ P* y
}
9 Q+ a" }. V: k0 U* d$ M5 |- u! ^1 ^' @
void* malloc(unsigned bytes)
9 r/ I& o) Z5 F; K! G. A; V{5 T( }$ w* U2 x# d
        return memPartAlloc(memSysPartId, bytes);
0 W9 m0 ]3 k& i5 l& G" X$ U}
0 e- Y# Y1 b$ S' y) o0 k  F2 ]1 z1 b% F$ @  D$ d3 ~6 C
void free(void* p)
7 D3 e3 v  u, {3 z  p8 [7 `{
0 M, o; C1 ?+ i6 B        memPartFree(memSysPartId, (char*)p);
, ]0 t0 G8 ]2 [" ^" g}
( `: |5 R: z0 C1 T




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5