数学建模社区-数学中国

标题: malloc（内存分配）在嵌入式下的一种实现 [打印本页]
作者: wangzheng3056    时间: 2013-7-26 10:17
标题: malloc（内存分配）在嵌入式下的一种实现
想知道malloc是如何实现的吗？这里是一个简单版本，所有的功能都在这个文件实现了。如果你对malloc的原理有兴趣，可以通过这个代码窥视一二。实际上这个实现是著名的嵌入式操作系统vxworks5.5以前的内存分配版本。这里我已经把它实现的更简单易懂了。当然我还有移植到vc++下的版本，更方便调试。有需要请留言; n' a8 ^! f4 [* j; y& ~, O

  v* V$ L+ G5 [  x! E6 r( X
0 H  k3 ]* D, l7 x
0 \, _3 D# L# {# w+ j *\file; i" G* a' w% N
*\brief               
* ~' _  n6 f+ X7 F) O, D4 H" Z5 U *\details        , W% u8 X' ]3 P4 b$ f0 x8 L+ ?
*
* d7 m9 H9 k' a7 v. K% ^" Y; s *\author        Janson3 t" ]6 Z- h- @0 s: o2 {
*\version        ! u+ v' h1 }' z2 k7 k1 J/ H9 ~
*\date                04Jan12
, ~* o  b. [( l# K, }0 K6 P2 G0 h *6 K  ?( t) W! P
*\warning       
5 Y9 P; z# G+ e" n% ~: [6 J- K *1 I4 w0 P$ G* S, h( z
*\history \arg        30Jan12, Janson, Create the file7 v% f8 v4 O- Q1 z+ z( S1 S
*        modify from VxWorks source9 W, i: _+ N5 Y  S, `
*  Legal Declaration: it is for studying VxWorks only.
$ W. T0 j* p0 M */
+ @& e3 i' M5 J1 d: |#include "includes.h"
& J4 @5 h! |7 m( K4 D. C! j5 n9 e+ G6 |% Z$ Y. Y& K
/* The memParLib.h file is hear:
, }* [- S2 D9 z. o6 V' }' b: h2 }https://code.google.com/p/vxwork ... rivate/memPartLib.h6 b! w) ?+ i: y$ q/ E7 z9 M
*/% M, M) i1 x4 H7 z3 h- n, z3 b

" X0 |6 R) \5 M/ L# r& Q' N5 N/* optional check for bad blocks */& B9 P& H' f" n" n/ ?1 ^
# }. V& ]$ K: c% p% K/ L8 t5 a
#define MEM_BLOCK_CHECK                        0x10, v( f! t! B6 U8 N
5 o. I' {, H1 N
/* response to errors when allocating memory */
( t" f, ?8 S+ _3 x' A+ Z6 R/ M
9 ~: V+ U4 ^1 G9 p  s# I. Z#define MEM_ALLOC_ERROR_LOG_FLAG        0x204 u3 `8 h6 V* G; u& {) }
#define MEM_ALLOC_ERROR_SUSPEND_FLAG        0x40
5 A4 `# C$ q- g& h6 [$ H; d
, ]7 j, `- f# f/ P% o/* response to errors when freeing memory */3 a% E  p/ V/ ]+ \& ^9 }( [
6 b9 o) h/ R( G0 ^2 b4 h
#define MEM_BLOCK_ERROR_LOG_FLAG        0x80
8 z) `/ ]* s' F3 W. d, o' R#define MEM_BLOCK_ERROR_SUSPEND_FLAG        0x100% k+ ?5 j- m' t6 ^$ E6 A1 H  ^: p

# P# Y" D  n4 T- e6 Z2 d#define NEXT_HDR(pHdr)  ((BLOCK_HDR *) ((char *) (pHdr) + (2 * (pHdr)->nWords))): R  A+ p8 s/ N" S( r- a5 @# i; y9 x
#define PREV_HDR(pHdr)        ((pHdr)->prevHdr)
3 L/ g. Y1 @  q" f0 K. S$ Z
4 R) R# `$ o: W4 H8 b#define HDR_TO_BLOCK(pHdr)        ((char *) ((int) pHdr + sizeof (BLOCK_HDR)))
) y/ B" E$ @" |, ^% ]8 l( `+ o#define BLOCK_TO_HDR(pBlock)        ((BLOCK_HDR *) ((int) pBlock - \* E; D: z7 `' I' c/ ?
                                                sizeof(BLOCK_HDR)))
) x/ D' N" |3 ?, G$ F7 Q) M+ @8 {
" g5 X2 r0 ]' }% {0 @: {#define HDR_TO_NODE(pHdr)        (& ((FREE_BLOCK *) pHdr)->node)
  _- v  P+ }' a7 z8 @" r#define NODE_TO_HDR(pNode)        ((BLOCK_HDR *) ((int) pNode - \! x7 k. g- D/ H( Z
                                                OFFSET (FREE_BLOCK, node)))
/ F" O3 @0 B% f4 n+ A$ Z; ~9 ]) V# i' \8 }$ X8 G- i( I
static BOOL memPartLibInstalled = FALSE;5 b  i" C9 t1 J! F

) i2 n, m2 F! i" B: @/ p" {: astatic OBJ_CLASS memPartClass;
! a5 S1 R' V6 }$ B# f2 YCLASS_ID memPartClassId = &memPartClass;5 i" }4 T8 ^% M4 b

- E# M9 y+ V; ?5 t% w% o. Kstatic PARTITION memSysPartition;
% f6 b! K* v/ ~9 @2 |PART_ID memSysPartId = &memSysPartition;) d! t' w5 F( V6 b
U32 memDefaultAlign = _ALLOC_ALIGN_SIZE;
2 c7 E8 r/ y. ~+ ]2 ^2 W0 Q
' ^$ m  [/ E% X% s, nstatic SEMAPHORE semMemSysPartition;
. f; v% i- Y3 k7 r. k) b; {* @  O2 e% `. M
static void memPartSemInit(PART_ID partId);8 u. H8 g5 f7 {5 v5 d

' B( z8 S4 @3 `. g7 UFUNCTION  memPartSemInitRtn        = (FUNCTION) memPartSemInit;2 c/ D' B4 {- m* n
7 i$ }% d/ G$ {
unsigned memPartDefaultOption = MEM_BLOCK_ERROR_SUSPEND_FLAG | MEM_BLOCK_CHECK;
5 J4 S& z  N+ Q
. w. ~7 c9 ~; l5 z2 t+ @static BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree);
: x8 J0 x( K7 m& y" rstatic BLOCK_HDR* memAlignedBlockSplit(PART_ID partId+ N3 u. ]. E' f+ l' D
        , FAST BLOCK_HDR* pHdr3 {8 ?5 U2 [7 l7 \
        , FAST unsigned nWords" A  ?0 N) x- E* n& s
        , unsigned minWords/ y$ o2 M, {* O: L- I9 e
        , unsigned align);
2 l- X7 J  f0 F; g8 }, P" w: G* T0 m" g/ K( f2 ]4 A* O
static STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize);6 K0 U* E% X0 [' @

- I3 i  S* j6 @" `/ R5 T( HSTATUS memPartLibInit(char* pPool, unsigned poolSize)
, @& T, w+ k* o, U- S% t{# Z/ \5 q- x; |. E; B0 {
        if((!memPartLibInstalled) && ! j( o) H0 V" t9 ?. d
                (OK == classInit(memPartClassId, sizeof(PARTITION), OFFSET(PARTITION, objCore)
, ~5 ~9 S( X5 I' ^# x  d9 ^  Z                , (FUNCTION)memPartCreate, (FUNCTION)memPartInit, (FUNCTION)memPartDestroy)))
2 `8 @* [$ D  {5 X2 s, O& R        {
1 _7 T3 ^& z) u                memPartInit(&memSysPartition, pPool, poolSize);
1 N5 \/ d3 B  \  L4 R$ D* i# ^; F' z! p                memPartLibInstalled = TRUE;
/ x( F( r0 i' Y6 I2 m. `# s        }* n( Y8 a( t6 y' Q% J

* p/ N. V2 r2 ]4 C! s) B        return ((memPartLibInstalled)? OK : ERROR);
" E0 P% a1 Z7 g) o/ Y/ X}
/ c5 }& ~( o, d
# s! i1 I+ R7 b+ ^PART_ID memPartCreate(char* pPool, unsigned poolSize)
1 G* W5 c1 w, m6 ^$ J{' J# B; ^1 A) z1 Z/ F, n3 D
        PART_ID pPart = (PART_ID)objAlloc(memPartClassId);
) V) _0 P* x. e3 Z& j  p+ s
; X- e, }- {, u- ?. L        if(NULL != pPart)
% y1 V4 m5 B" n7 q# H( _        {
+ b$ M* e0 G2 g6 F" R                memPartInit(pPart, pPool, poolSize);: P: r) M1 L0 n
        }
" Z# {8 {4 O7 }2 L6 v
: R/ Q6 o. H, C; i        return pPart;7 X, e% |* w; o  o; ~+ S
}
' L! T( D2 _( a/ u9 c# U- d) Z$ |# c1 M* ^* C$ k3 n+ l
void memPartInit(PART_ID partId, char* pPool, unsigned poolSize): Z: }% n: Z8 s' X5 k4 ^8 i: U! H
{
; o( x% w' R  ]* b7 V6 h8 g        memset((void*)partId, 0, sizeof(*partId));
' d6 p% ~7 T, g  ]3 t4 c, Q2 ], o6 a) a4 O/ P1 t9 u0 l. m. T3 `
        partId->options = memPartDefaultOption;
- R* _1 v  p; u+ G        partId->minBlockWords = sizeof (FREE_BLOCK) >> 1;        /* word not byte */4 U3 f5 N+ o. i2 R" \

% T8 F. e* X* E" ~4 C- w: \( x' z        (* memPartSemInitRtn) (partId);
' B% O: e/ i( d! T+ c4 ]        ) X; Q: ^8 v! {( I' X) H
        dllInit(&partId->freeList);
6 N, }9 n! J. b" n: \       
4 i/ O$ v& ?3 q: Z! u        objCoreInit(&partId->objCore, memPartClassId);5 Y8 `8 }. O" i0 @* o3 M* z4 V9 W
        & i4 U0 X! U1 {: V" I
        memPartAddToPool(partId, pPool, poolSize);, M$ K- W$ {1 H
}
2 K3 C! ?% Y8 K- p5 M' r
* b1 }1 v) \8 m. sSTATUS memPartDestroy(PART_ID partId)( e5 q  N; V- s& [: v9 w
{  s/ G9 ]0 R. V
        return (ERROR);+ ~7 x, G. ]. m+ g9 P* e2 R2 i
}
  Y% [: z" T% I% a& Z
! Z" a: p6 v9 n$ E% Y9 evoid memAddToPool(FAST char *pPool, FAST unsigned poolSize)! b$ Q+ m6 I  h# ~/ U8 Y; L' q
{
3 l1 ^9 a- a2 M+ Z: m    (void)memPartAddToPool(&memSysPartition, pPool, poolSize);
3 |/ W' J1 S4 H/ y7 b}, b4 t5 X8 p# |
5 N% e0 z/ V0 K2 }& W2 K' ]

) ^/ |& Z& s3 g' ^/ t; ]% b+ @static STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize)! ~: n3 C4 o) C0 \/ c5 y
{
* \/ l/ W3 I4 d4 I) l        BLOCK_HDR* pHdrStart;' Q: M4 u/ t6 X' d& d, a1 |
        BLOCK_HDR* pHdrMid;
" A) m1 h0 y: M" _7 U- {2 n5 R        BLOCK_HDR* pHdrEnd;
  [' q3 n2 Q$ l4 m2 J1 G        char* tmp;' b# k" s7 V/ t& U8 K6 u
        int reducePool;
! K4 }, v! t) r1 w6 H! |+ K' M9 x" ?, k, D% h6 c  d
        if(!(IS_CLASS(partId, memPartClassId)))        /* only memPartClass can call this function */
4 S* \) u6 R: A8 b, C7 K3 v        {" j0 o8 W0 y2 a) d: a
                return (ERROR);
/ J. E+ w" Q; b2 u' G: F! q% f        }9 J- I  @( h7 D, M, ^! v; j
3 V& l! J# W/ Y: ~
        tmp = (char*) MEM_ROUND_UP(pPool);4 |1 `% n6 k% a9 p" l
        reducePool = tmp - pPool;
% o' v) H0 @) k! m! T+ y) g8 S
        /* adjust the lenght */! H+ j( Z4 s- L: p% ?1 u4 T* ^
        if(poolSize >= reducePool)
0 I8 J5 T! W8 {        {
: m* l6 i- E0 |5 K# i                poolSize -= reducePool;# D& m* {- q: i7 e
        }3 h2 t; i9 v: q1 q' l7 ^* I' p' a
        else  j- Y/ c1 L& s3 k$ r4 x! L
        {4 e6 L) r0 M9 I0 n3 I  U. p
                poolSize = 0;
4 s% R$ d, M, J7 b' r: j- X- y        }
  l9 U+ Y4 [7 C/ h        pPool = tmp;
5 k$ U1 w/ R9 ]$ B( O% k          d! D3 q# b3 W. \7 D% y
        poolSize = MEM_ROUND_DOWN(poolSize);
4 o0 H8 P" [8 k# I        0 N, d+ u$ ]! G" a5 ]
        /* at least one valid free block and three header blocks */
- E' p) p0 @8 r4 B        if((sizeof(BLOCK_HDR)*3 + (partId->minBlockWords*2)) > poolSize)
6 p4 C* J" L" a' b; i- Z        {% R7 v4 E/ W( b# J* ^
                return (ERROR);
* Y4 {' E, Q$ R) F        }! H  t9 n" V( [7 K- r$ L- [% |- Y
; S( S) |. H% S  s7 H8 u
        /* initialize three blocks */
% ^) E5 U: O4 ]6 ^        pHdrStart = (BLOCK_HDR*)pPool;
% M& C# D% m. E" x        pHdrStart->prevHdr = NULL;
$ v8 z$ s$ u0 y  a7 Z- i        pHdrStart->free = FALSE;                /* never in use */
% |) a! z6 R  v- W+ r% \& ]. b& z2 z        pHdrStart->nWords = sizeof(BLOCK_HDR) >> 1;
0 }/ d# `+ M& A2 y4 t7 u, e6 F+ v5 y+ Q7 Q3 t
        pHdrMid = NEXT_HDR(pHdrStart);
" T& B1 Y+ b' c) [) W" T        pHdrMid->prevHdr = pHdrStart;) K- l8 P; _$ V4 J6 }! v
        pHdrMid->free = TRUE;                        /* the main block */* z5 B1 d0 {: w8 o! Y* Y, O
        pHdrMid->nWords = (poolSize - 2*sizeof(BLOCK_HDR)) >> 1;% n" V( h! f% U) ?( `- o5 Q

. x+ x8 q) W! s5 L        pHdrEnd = NEXT_HDR(pHdrMid);% U! h- K( d& K$ E9 X
        pHdrEnd->prevHdr = pHdrMid;
9 W0 V+ q) {2 A& ~' Q+ Y        pHdrEnd->free = FALSE;
/ L+ }" m/ n  O        pHdrEnd->nWords = sizeof (BLOCK_HDR) >> 1;4 `- E" S% }, Q1 j0 @3 V

0 B3 Z! X3 f* p3 |  i, m. f* [* H        /* TODO take sem hear */* [, k! w0 u" d  x+ D$ t
        semTake(partId->semPartId, WAIT_FOREVER);
- T; G3 E/ R+ c# S* D       
4 X  w" q( ~4 h0 Y) ]        dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdrMid));
8 ^3 N8 n; z2 \" x0 M  ^& G        partId->totalWords += (poolSize >> 1);
. n: o( ]: {/ l7 q0 [. o1 T! T4 j' [5 J# s* s
        /* TODO give sem hear */) m# G/ j/ k( Z& S  [
        semGive(partId->semPartId);" N3 H/ y0 ?' K3 @! E
2 c7 S8 j  S/ v  X% p1 N4 R0 ~
, z1 \9 N, P) s" G' K
        return (OK);
6 v( K1 t; t+ E! K}9 r3 [( Q; r1 x; k' @3 _8 J
3 U7 ]+ M8 |: g" L& @
void* memPartAllignedAlloc(FAST PART_ID partId, unsigned nBytes, unsigned align)7 r. K% F/ C, s
{
, A  u$ u! P  T* W# b        FAST unsigned nWords;
5 v9 \: g% r) B1 V! N4 ?2 \' M        FAST unsigned nWordsExtra;
7 z) J+ p: B$ j, ?( {1 F0 @        FAST DL_NODE* pNode;+ {0 Q5 k7 E' {5 }1 k
        FAST BLOCK_HDR* pHdr;
( y0 e) z) l% z% M) h- w        BLOCK_HDR* pNewHdr;2 W, e$ i/ C  [- g! f, K
        BLOCK_HDR* origpHdr;* Z7 w7 g# t: `8 X3 C- y; T, y5 R3 v4 k

9 F. `, D$ |4 z/ R/ A1 v- Q1 [        if(!(IS_CLASS(partId, memPartClassId)))        /* only memPartClass can call this function */
1 Q& I1 ]/ {9 z3 e- l        {! o" `- Q9 O/ H: d, b
                return (NULL);. A* H, ^' w* U: Y( I( g* b
        }
* B0 K1 p% V& O5 ?( s) V) ]( _& J$ k' e' B6 Y
        nWords = (MEM_ROUND_UP(nBytes)+sizeof(BLOCK_HDR)) >>1;
4 }$ P5 L/ u8 J4 [9 D* }7 d, I: m9 W% u
        if((nWords<<1) < nBytes)
, O3 Y8 \0 n1 v+ R        {6 A, y- G  W. k1 K
                /* TODO suspend the task *// d5 N; s4 t7 p; q& a/ \. V
                return (NULL);
6 _2 j; K6 @3 n$ B1 @0 K6 X        }& ?7 k; b7 U5 S" f6 y3 e5 m) }+ d

7 }3 {, e/ q' L, @4 ]        if(nWords < partId->minBlockWords)
; r2 U# e! g  N        {
4 X+ T4 O/ z8 Z- L( l                nWords = partId->minBlockWords;
. }( P0 i$ I9 P        }9 a- Z4 R8 g6 b8 b) u6 d" K
. d& I" d3 z8 g+ q% \" }
        /* TODO task the semaphore hear */" I2 F; t2 s- G4 F2 a
        semTake(partId->semPartId, WAIT_FOREVER);6 J9 }4 h9 P, ]# @( S, \
        pNode = DLL_FIRST(&partId->freeList);6 w: a# S) n) t6 X- j2 T/ N% B/ w" o
        nWordsExtra = nWords + align/2; /* why? */
# t3 ~+ T" l7 [! _
9 r  ]1 E+ m* ^" e: v/ @+ B        for(;;)9 Y, S. B2 t5 ^- N' Y. N  ^
        {
8 ?! Q% d" j; k8 }0 O0 L                while(NULL != pNode), X: [* e" o3 a/ R* F, t
                {
) W$ c- ^0 u* s' M2 ?                        if((NODE_TO_HDR(pNode)->nWords > nWordsExtra) ||
8 n8 O  O* w5 S* t, S/ a6 j                                ((NODE_TO_HDR(pNode)->nWords == nWords) && : `" b' v  w5 w9 [# D* W
                                (ALIGNED(HDR_TO_BLOCK(NODE_TO_HDR(pNode)), align))))
  I: U( S+ K0 c- l! Q                        {
! _8 T: ]' h' w% L                                break;- ^& i  `4 z, u% p
                        }
/ k$ F2 ]8 L6 {8 G7 I; h$ W
! P! C' q, S9 \  B5 w/ S0 t0 c$ L                        pNode = DLL_NEXT(pNode);, \) x9 s/ c3 p
                }% s7 \4 s& ^: A
; z; u. }# S$ P( a7 g) a
                if(NULL == pNode)
: {# D3 {0 {; J, _: h& X                {4 c4 ]% R, \1 N* |, D3 F! ]: C( q
                        /*TODO give the semaphore */
3 `& d: I3 b7 J7 n, r: {- u                        semGive(partId->semPartId);$ v3 K+ O# J4 A% H
                        return NULL;
" [& c6 d& n* u& W% I8 x) I2 f4 h                }2 p' ?3 B* d! W/ F
+ q4 D6 B# |3 v. \  _4 I! g9 w
                pHdr = NODE_TO_HDR(pNode);- J) c+ `# J9 }# m% B9 x6 b! `
                origpHdr = pHdr;2 f' _# P! w  S/ z) Y8 q) `

. G7 P; f1 c" L2 B7 a, d7 K: k                pNewHdr = memAlignedBlockSplit(partId, pHdr, nWords, partId->minBlockWords, align);. R# T2 d4 T! \1 Z8 n
                if(NULL != pNewHdr)
. W* Y: W& |% C% R) f" F                {2 o9 l# o0 Y# P2 y1 Z  h0 j
                        pHdr = pNewHdr;
7 p; A9 _# L2 A  a3 E  c  `% x                        break;
4 ]6 l" N7 E, Y; v                }
$ N, \; j7 `! z  |) M3 p: T- H/ I. w  N; v1 S- P
                pNode = DLL_NEXT(pNode);$ K2 ]: W2 m; Q) ^
        }/ u% ]. N& L& A2 K2 e# n

, J  @1 D' i( q) a2 i, ^        pHdr->free = FALSE;
% U& R, R; j: m$ D: F        partId->allBlocksAlloc++;9 A' i3 |+ @3 q3 @' y/ x
        partId->allWordsAlloc += pHdr->nWords;, m6 _1 Y0 j* u- V7 b: c
        partId->curBlocksAlloc++;+ ^# |  u* H- b: Q3 O5 F
        partId->curWordsAlloc += pHdr->nWords;2 S  Y! a6 n5 q) {3 I3 r

( @- \3 V' f9 ?5 `+ r        /*TODO give the  semaphore hear */4 Z0 N: _7 o8 m
        semGive(partId->semPartId);. e, p1 l3 U9 J4 b" Q) a. u) g: W
        return (HDR_TO_BLOCK(pHdr));
3 {5 H* i: I/ w  C3 Z        5 S9 j# ?6 k2 {" m2 u" a, h
}
7 {+ E# y8 |  T# c) P' N/ [, M) i. u* i' a" z
void* memPartAlloc(FAST PART_ID partId, unsigned bytes)/ _7 j: d/ l! m# o5 D  Z
{
* y; T4 K0 }0 o1 N6 q        return memPartAllignedAlloc(partId, bytes, memDefaultAlign);; w! {) P0 e: d3 d) V
}- l* Y/ L, \5 R" O  a
8 C1 k# G  P. J0 J7 [! J  E
STATUS memPartFree(PART_ID partId, char* pBlock), o+ B( X/ p. J
{
' C2 O. M. Q7 [* |, f! e        FAST BLOCK_HDR *pHdr;
1 f, D$ V9 Q) o$ [$ ^2 [7 n    FAST unsigned   nWords;
$ ~: d. p% R" @* @- E$ V9 _    FAST BLOCK_HDR *pNextHdr;3 H3 O& V; j1 ^

  }- R! R& E3 A' i' ^/ d9 R( z; W        if(!IS_CLASS(partId, memPartClassId)): g, T* i9 t, Q* z$ ^
        {
: M2 r$ E$ Z. [                return (ERROR);
  e- Y4 C: [  \# F" P7 V& l1 {7 P        }9 R8 @. r/ Y/ a! l) J: i
9 W: C# H/ P5 H3 F' q. ]/ i/ V
        if(NULL == pBlock)4 s+ x1 B5 [: V( f3 l
        {
# G! r: p4 G  ^/ s' Z+ {$ l                return (OK);
2 [5 q- d! D" a1 `: H        }
7 J' S' A) D* H# g3 Q9 U& S$ ~# }$ Z- h0 s$ F
        pHdr =  BLOCK_TO_HDR(pBlock);
8 J+ \) K6 m" J1 }5 k8 ?. p+ d+ z9 u6 ~. ?" H! m+ v& I5 D2 I
        semTake(partId->semPartId, WAIT_FOREVER);
( ?0 c! R) L) n2 N/ p0 q5 Q1 G" H/ S+ `6 u8 I7 o: ~' q) q2 m. R
        if((partId->options & MEM_BLOCK_CHECK), W2 Z  `5 E8 q1 S/ U
                && !memPartBlockIsValid(partId, pHdr, FALSE))+ P6 `0 J' r2 ]2 a) q. G, L
        {
/ f$ Y5 N" o; @+ X( e5 B# ?1 o                semGive(partId->semPartId);
; n" A# X: Z4 i& y1 Y9 l' {                return (ERROR);
! O6 }0 b2 O8 y7 e        }
0 Y& ~  N3 ^; I" w" q; `. U/ d; I. p& r6 T1 D. R
        nWords = pHdr->nWords;
, ?1 R+ R- g* V. q+ j        if(PREV_HDR(pHdr)->free)3 B9 L0 q" `- v0 Y% [# t5 ?* M" o
        {/* the prev hdr is free and than coalesce with it */1 v6 x. p; s1 o7 b& B! y
                pHdr->free = FALSE;
# H! U0 T, n6 Z                pHdr = PREV_HDR(pHdr);
% t+ H& o) b( [                pHdr->nWords += nWords;
9 s9 s' K, s' o2 x& g% V( D        }4 W  ^$ K4 _% @/ H- Y1 d$ C
        else
! Q( J# m# `8 B/ [  d        {) @5 J$ t+ i( w0 k8 b
                pHdr->free = TRUE;3 J8 F9 C* X3 N  }- _
                dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdr));
  @* o) B9 l* P        }3 ~# Z7 \. x/ V, r& r* {  m0 F9 i
- t# \/ |, Y( C
        /* check to coalesce with the next */5 i$ u+ [+ r: n& ~
        pNextHdr = NEXT_HDR(pHdr);! m4 Y( O0 _& @
        if(pNextHdr->free)
' \+ n$ Y1 q2 K2 q1 S0 {        {
* Y0 w4 A: R* R7 ?1 E                pHdr->nWords += pNextHdr->nWords;
- B6 h% D9 k# h: _* W. u; Z. S                dllRemove(&partId->freeList, HDR_TO_NODE(pNextHdr));
5 c# k2 V. t: n  n        }
( X+ Q$ C7 f5 Q& t7 o  v. C* o$ o8 Z- T. r) C: s
        /* cannot use pNextHdr->prevHdr=pHdr hear */# S; S' F  k: n( m- T- Z5 A# x
        NEXT_HDR(pHdr)->prevHdr = pHdr;9 U5 ~! p" g6 h2 Y2 k
: v4 B; A$ R8 J: N7 d
        partId->curBlocksAlloc--;
6 a- p  o& E3 a# R% p9 n; g        partId->curWordsAlloc -= nWords;
- u& x- X6 Y, N1 y' B; l0 |# ~# e; ~  b5 A& Q/ N" G
        /* TODO give sem hear */( R! ^7 ?* |  n: q/ J
        semGive(partId->semPartId);
  H" q( ^4 d) v        & z/ X" e* l& l6 X/ V8 n
        return (OK);( A0 [% z7 n% z. O, X7 s
}
- l5 P6 s9 u" m. V* r: U+ W) Q7 E: D- B$ l
static BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree)1 i! D0 n0 c( s6 i0 T# @
{
0 ?0 p. Q. S( v        BOOL valid;/ s( T' _3 `/ k
$ U- Y# t3 y+ G8 e, E
        TASK_LOCK();
6 B/ x2 e- E- }6 c* i3 V* K& F! Y        semGive(partId->semPartId);
8 w  u% d1 ]; V       
% f0 j# G% V% E$ s( E( W        valid = MEM_ALIGNED(pHdr)
  h( q+ n( a& _* [4 E        && MEM_ALIGNED(pHdr->nWords*2)0 B3 {4 R/ f1 ^3 a
        && (pHdr->nWords < partId->totalWords)   N* p# y2 w# b8 g6 c  S) x
        && (pHdr->free == isFree); S: j/ l, Y: F9 M6 E8 [8 \
        && (pHdr == PREV_HDR(NEXT_HDR(pHdr)))
* T+ Q+ [) J5 `5 A5 g0 d$ N        && (pHdr == NEXT_HDR(PREV_HDR(pHdr)));
5 q' O- d+ s7 w3 |4 C       
, ~9 e3 p1 q( B5 c& v  P        semTake(partId->semPartId, WAIT_FOREVER);- k7 x3 ^- M) c9 K/ G
        TASK_UNLOCK();2 q0 L0 D0 v$ O( U
0 D2 J5 @  `4 Y2 ?" H4 f
        return valid;, \9 z4 o- A" Y& i4 ]" W: U0 t
}
8 t  o) Q/ }% [' l# \" O  ^
  h  u# c0 _3 B, R5 k4 dstatic BLOCK_HDR* memAlignedBlockSplit(PART_ID partId( _( n5 A- s8 b1 G0 g9 P
        , FAST BLOCK_HDR* pHdr# B: E6 V# ~1 x% \* r. J5 |- U. R
        , FAST unsigned nWords
  n7 M1 z6 y# F        , unsigned minWords4 D: m1 x+ D4 d3 |& W
        , unsigned align)
- f, I* b5 u. N  {- P! n{
! N0 L# V' U6 J  w        FAST BLOCK_HDR *pNewHdr;
* v7 P7 M6 ]- w: n    FAST BLOCK_HDR *pNextHdr;% T" y* R7 m$ R3 m
    FAST char *endOfBlock;
& Z( Z( s1 U) {! h7 K! J  I, J+ K    FAST char *pNewBlock;
& M( D6 V/ u- Y) g- g* Z    int blockSize;7 n1 Y, c% G: ?6 n$ t  e
: B; D. v6 F6 s; X% ~
        endOfBlock = (char*)pHdr + (pHdr->nWords*2);! L+ T( A# }4 z8 ^- d6 |0 @
3 z# v" o3 s4 m" s; b: P
        pNewBlock = (char*)((unsigned)endOfBlock - ((nWords - sizeof(BLOCK_HDR)/2)*2));
, v* k. |6 W$ O3 ^6 e5 i
3 G# c! ^9 j; V' m6 s        pNewBlock = (char*)((unsigned)pNewBlock & (~(align-1)));
7 d, E( s) U) G( y' J/ t. f+ \
% D! t' y9 ^, p; R        pNewHdr = BLOCK_TO_HDR(pNewBlock);, _+ L7 V' ?9 C2 E. w

  ]! d5 o* Y& m. {: \7 y& j        blockSize = ((char*)pNewHdr - (char*)pHdr)/2;
  W1 ]/ N: _1 a
  a9 O! z* Q; c( B- E1 J/ E        if(blockSize < minWords). M2 \- N4 K4 @& L
        {
( Z4 @+ y& n: K) R0 C                if(pNewHdr == pHdr)
( A  M$ P& z1 r# r                {
: Q3 W5 q* C/ _) L                        dllRemove(&partId->freeList, HDR_TO_NODE(pHdr));) i8 c* s- B' B/ c# n3 Y
                }1 `; v' c' C' N4 c2 a
                else
' L. U3 U+ L" P/ U1 K                {
) V" N$ k8 ]  y/ h5 }7 K5 J3 a                        return NULL;
. q; W- R: T! [$ z1 P$ k                }
/ ], }- F5 J8 y7 O" g  o8 B        }9 T% s4 f. ~! w3 s
        else
5 a( R7 C; h2 N        {        /* recaculate pHdr */
) A3 e+ f+ d5 u                pNewHdr->prevHdr = pHdr;* h3 l% W& q! _0 s$ L) I
                pHdr->nWords = blockSize;
: Y5 ?0 H) d! ?        }' A3 _/ J% V7 H" Q
% U* ?% e4 V1 k; M5 V4 _3 t
        if(((U32)endOfBlock - (U32)pNewHdr - (nWords*2)) < (minWords*2))
9 w4 r+ `: ^2 v0 \5 m        {
  o' U. {; {# |/ b                pNewHdr->nWords = (endOfBlock - pNewBlock + sizeof(BLOCK_HDR))/2;9 \! p$ \0 q% c+ A2 x3 G6 U+ T
                pNewHdr->free = TRUE;' ]) {% _% R3 _, h' L

6 t) D9 r" c2 M# D9 }2 }                NEXT_HDR(pNewHdr)->prevHdr = pNewHdr;
2 {+ T5 D0 w& w. ^        }2 K9 {+ _8 {: B2 i8 n4 y* Q  |' O
        else/ e* x: X7 K4 o2 j* m7 v* X
        {/* space left is enough to be a fragment on the free list then */
: Z- A1 s+ v& h, z) a                pNewHdr->nWords = nWords;" ?1 \8 E) v7 A. z2 ^; ~0 l
                pNewHdr->free = TRUE;! h. z' K9 H9 h  E5 P- z- A
" b6 I1 G3 B7 F, z
                pNextHdr = NEXT_HDR(pNewHdr);
# H1 A5 t9 s2 l7 p# L, g                /* words 包括BlockHdr */
& Z& N# k: k+ p                pNextHdr->nWords = ((U32)endOfBlock - (U32)pNextHdr) / 2;) E4 o( E' k+ Y& C. s! B' J
                pNextHdr->prevHdr = pNewHdr;/ v/ q# `0 A! W4 ^( u' @! O/ F
                pNextHdr->free = TRUE;( l& F! Y* f" A8 |9 m5 `

  p% Y+ ]- ]' d: d& W                dllAdd(&partId->freeList, HDR_TO_NODE(pNextHdr));
' s4 ^* W$ y$ x
3 W) G! P* k5 }" t. r: d+ b  z                NEXT_HDR(pNextHdr)->prevHdr = pNewHdr;3 ]: K4 L% x( d6 P
        }( ^" a$ i% R( r4 F, Y- }& h
6 h# v! P; Y: o/ j% f! ], y2 N8 Z1 o; t
        return (pNewHdr);
, i: R- C: O) p' `- ?3 {5 B}
6 T( c# E  K1 [! q0 P7 X- G
0 v! J4 ~0 s7 P6 P: ^3 g" d0 V7 Hstatic void memPartSemInit(PART_ID partId)
1 U) ^% s$ u0 Q! x{
9 i$ ], Q3 e; z# E3 z        semBInit(&semMemSysPartition, SEM_Q_FIFO, SEM_FULL);
4 G9 i5 a5 l* {6 ^$ R
2 W( L- A4 M2 T        partId->semPartId = &semMemSysPartition;4 c  c, t3 F, L- Z3 I/ X
}
  u7 `$ s, r# u- y6 s, u5 E5 l2 v2 w* e' q: E4 h
void* malloc(unsigned bytes)
0 V5 |7 {% {, I7 z0 F6 j{
) W: f: ~# [( l! a  v. Y- t4 M        return memPartAlloc(memSysPartId, bytes);
: g' U: e. U- f: ]2 p}
3 T. A3 v7 }/ K* ?6 J+ \4 Y" V
! m. [7 h* v# P( _void free(void* p)
! L9 A; {2 U9 ^" E, e{
, F! r; X& F* e! b        memPartFree(memSysPartId, (char*)p);
/ u+ v( s$ H5 U( w6 \}  H- g% I3 k% |  ?




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