数学建模社区-数学中国
标题:
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 Janson
3 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 file
7 v% f8 v4 O- Q1 z+ z( S1 S
* modify from VxWorks source
9 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.h
6 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 0x20
4 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" {: a
static OBJ_CLASS memPartClass;
! a5 S1 R' V6 }$ B# f2 Y
CLASS_ID memPartClassId = &memPartClass;
5 i" }4 T8 ^% M4 b
- E# M9 y+ V; ?5 t% w% o. K
static 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, n
static 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 U
FUNCTION 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" r
static BLOCK_HDR* memAlignedBlockSplit(PART_ID partId
+ N3 u. ]. E' f+ l' D
, FAST BLOCK_HDR* pHdr
3 {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( H
STATUS 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. s
STATUS 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 e
void 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& O
5 ?( 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 Q
1 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 d
static 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 minWords
4 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 H
static 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, u
5 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