数学建模社区-数学中国
标题:
malloc(内存分配)在嵌入式下的一种实现
[打印本页]
作者:
wangzheng3056
时间:
2013-7-26 10:17
标题:
malloc(内存分配)在嵌入式下的一种实现
想知道malloc是如何实现的吗?这里是一个简单版本,所有的功能都在这个文件实现了。如果你对malloc的原理有兴趣,可以通过这个代码窥视一二。实际上这个实现是著名的嵌入式操作系统vxworks5.5以前的内存分配版本。这里我已经把它实现的更简单易懂了。当然我还有移植到vc++下的版本,更方便调试。有需要请留言
H$ H ?% R- t! @! t" Y
2 X9 @2 @- K7 Q% x6 K
; m9 b. r, R" Y) @1 I; k+ K
! C% G7 u$ b8 F5 a8 r, ]8 }
*\file
3 c( ^* C/ d* T
*\brief
( [9 Y8 e+ X3 h5 U, k; s4 L
*\details
) P- G: \( Z9 b3 Z+ T) w& ]
*
4 N! B! B% }' n* x3 k* K' ]! N# g
*\author Janson
; K' G! z0 g' h0 c
*\version
: e1 b1 B( s& a+ d" K# P0 ^, e
*\date 04Jan12
3 }+ M. d. X9 d" I& `
*
# v# [$ Y7 o0 W
*\warning
q* ^6 K- B# k( |
*
( e' G: j5 u! r; a: a9 R' J7 a+ _/ k
*\history \arg 30Jan12, Janson, Create the file
5 v7 S4 B1 g$ F- d4 ~
* modify from VxWorks source
; r& j. p4 Z3 U) p3 W$ u' F
* Legal Declaration: it is for studying VxWorks only.
1 Y, W: [; x* c0 |5 Q- X
*/
6 J# ~% p+ C3 @* T; H
#include "includes.h"
7 |. u2 }: Y+ S' O7 }
) M, y9 M$ ]7 M# c, z) s4 {
/* The memParLib.h file is hear:
% z, P: _$ ~* O% p
https://code.google.com/p/vxwork ... rivate/memPartLib.h
% G( y, c2 i7 K0 J) t" Q0 N6 a
*/
- h' C1 T( y2 s( x) {/ d9 B+ m
1 m5 \9 O, U: O9 }: f
/* optional check for bad blocks */
6 B4 A. r& }* ~6 h Q$ L
( m) P& ?- @2 J5 H- ?1 J5 B
#define MEM_BLOCK_CHECK 0x10
! T% M7 O, k/ Q a
7 a( O7 H; ] ~$ E
/* response to errors when allocating memory */
2 j- q h. E, s
. N/ t( o& r$ J& k0 r. \& d
#define MEM_ALLOC_ERROR_LOG_FLAG 0x20
6 C7 ~( u; [+ N) X6 z
#define MEM_ALLOC_ERROR_SUSPEND_FLAG 0x40
. d+ `" L+ ~7 O9 Q' }( T
2 V$ v/ ?4 i5 `; a" G0 F0 \
/* response to errors when freeing memory */
. a1 W# [" U, a
# x+ z1 x* e5 P& {. x
#define MEM_BLOCK_ERROR_LOG_FLAG 0x80
& c$ H1 ]6 ]$ n! F! O
#define MEM_BLOCK_ERROR_SUSPEND_FLAG 0x100
; f/ Y8 z" ~ J- a* \; u( x/ W
, y1 Q- l8 R: m3 c: k8 @
#define NEXT_HDR(pHdr) ((BLOCK_HDR *) ((char *) (pHdr) + (2 * (pHdr)->nWords)))
1 F: g1 _ B) J/ X
#define PREV_HDR(pHdr) ((pHdr)->prevHdr)
, r& x" \& A5 m& ~* l9 Z# ~' Z
5 n. [, T; `. |& m; U5 o
#define HDR_TO_BLOCK(pHdr) ((char *) ((int) pHdr + sizeof (BLOCK_HDR)))
) I2 Q; i4 V2 V- \ Q
#define BLOCK_TO_HDR(pBlock) ((BLOCK_HDR *) ((int) pBlock - \
0 @2 W/ w {6 H8 k k: _
sizeof(BLOCK_HDR)))
/ m9 b% L3 D$ N0 T, R5 K: o
; E! d8 A- O/ I& |6 x
#define HDR_TO_NODE(pHdr) (& ((FREE_BLOCK *) pHdr)->node)
9 i; z) I" g. w" P$ T
#define NODE_TO_HDR(pNode) ((BLOCK_HDR *) ((int) pNode - \
9 J# V, }* {- Y* I+ Q0 @; ^
OFFSET (FREE_BLOCK, node)))
, u( q! a) w5 r. V
, ?$ _6 [; F4 ]5 F, |' m
static BOOL memPartLibInstalled = FALSE;
9 w+ W# S& Q' H0 U2 G; B! G
# V1 e g- l7 ?: J
static OBJ_CLASS memPartClass;
1 v' R% }0 G1 p: s( }' r" m
CLASS_ID memPartClassId = &memPartClass;
' v3 a$ k8 u5 x6 x: s
: f7 C; `& W& Z+ }. A3 e
static PARTITION memSysPartition;
! h' {/ S" U L, U! I3 G9 ~
PART_ID memSysPartId = &memSysPartition;
, M- V# e* D; @& X d
U32 memDefaultAlign = _ALLOC_ALIGN_SIZE;
( ~2 M @2 ^1 b2 ?
$ U0 {- z% D# ~' |" V. D- m3 ~
static SEMAPHORE semMemSysPartition;
5 z1 k+ p' v1 Q: Z4 n$ q
% |& ^/ P" x! k* H2 }7 K/ N) E7 m
static void memPartSemInit(PART_ID partId);
# \0 S3 {5 r! M' ?! R& \
; {4 @! T2 P; x9 C3 E( [0 {! ~
FUNCTION memPartSemInitRtn = (FUNCTION) memPartSemInit;
" D; f* Q( k% p
3 t! \! O* M1 z
unsigned memPartDefaultOption = MEM_BLOCK_ERROR_SUSPEND_FLAG | MEM_BLOCK_CHECK;
1 v! N3 N! X. @# ~
$ l9 S. j0 U2 T
static BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree);
I# l S# [6 k- e) V& u6 _6 R
static BLOCK_HDR* memAlignedBlockSplit(PART_ID partId
9 a F$ {4 X! {& B8 R6 U
, FAST BLOCK_HDR* pHdr
, t9 h9 _, f5 ~4 P3 F9 W
, FAST unsigned nWords
0 `7 I* \, n# Q/ j- H0 {5 |* ]
, unsigned minWords
, j. t/ X' f& P
, unsigned align);
X: u2 o) A, w
7 u7 e; C4 N+ j% W2 i- x7 J9 i
static STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize);
, V% H& {: g% w: K- D; u4 t
1 g4 H+ K8 P' g5 C
STATUS memPartLibInit(char* pPool, unsigned poolSize)
/ b8 F; P0 O0 u) k. f* i p, F- m
{
# P6 Y% O7 Z' f% X* l" @/ |, p
if((!memPartLibInstalled) &&
! ^) h( B/ n+ i; h3 o' k5 s
(OK == classInit(memPartClassId, sizeof(PARTITION), OFFSET(PARTITION, objCore)
. H; q, \8 ?8 P& E! L X
, (FUNCTION)memPartCreate, (FUNCTION)memPartInit, (FUNCTION)memPartDestroy)))
5 `+ O; ^0 A: k7 u( X
{
: ~$ ~6 P( f" R1 p/ x
memPartInit(&memSysPartition, pPool, poolSize);
5 s# @) a5 s" a! _7 K: A) [9 c
memPartLibInstalled = TRUE;
`+ i4 n9 q6 y' J* u d2 X
}
+ }; d3 [* s# m
+ F, E! |4 }9 `) p. S. l' L
return ((memPartLibInstalled)? OK : ERROR);
: F4 t4 d. H9 x7 l
}
7 z: e4 }7 J! q# b9 t
0 \ d9 ~9 H: x2 s
PART_ID memPartCreate(char* pPool, unsigned poolSize)
! J2 K# {( N q. N* p
{
4 X7 p& o3 M. `3 P; h' X
PART_ID pPart = (PART_ID)objAlloc(memPartClassId);
5 \0 J) J% f, @) `
) S1 ~$ p: f; ~% T
if(NULL != pPart)
/ _# p9 j" F/ p
{
. w; b# F3 ]7 W
memPartInit(pPart, pPool, poolSize);
2 i! O( b+ ^% I; e* n$ |
}
* w F# Q! M! g& h, i! ?' o
* P4 P2 _ d4 b% p+ [. S8 ?
return pPart;
6 U+ K- P4 o+ @
}
! U4 |) b% }6 ?% Y4 `2 R
) v9 c; |, @. ~: H, N1 r
void memPartInit(PART_ID partId, char* pPool, unsigned poolSize)
. E1 k; v% {2 k2 M r g7 _9 `
{
! [+ S3 z) x+ C1 z$ c
memset((void*)partId, 0, sizeof(*partId));
# g& Q9 E( q) X' o6 B) G. ]2 a
; ? Z9 @% q' h$ s+ g/ X
partId->options = memPartDefaultOption;
# { e" j, A+ p7 K3 j/ ?( ]) M) a2 j
partId->minBlockWords = sizeof (FREE_BLOCK) >> 1; /* word not byte */
% K* V, c" l% n; c9 ]: H7 y
0 o9 S% E, N! M9 s
(* memPartSemInitRtn) (partId);
" t3 |2 A4 f/ U) @
/ ~( b4 ?* A5 G0 P8 Q
dllInit(&partId->freeList);
1 D9 e) c* F4 r
- B: M1 I$ i9 {% N& }! G! B
objCoreInit(&partId->objCore, memPartClassId);
$ A5 J5 Z9 A- G: k
2 i* u( B8 g% T7 n8 q' y5 R
memPartAddToPool(partId, pPool, poolSize);
' g" Y3 R' c/ A, l6 G G, n! A( _
}
3 Z# ]$ ]. Q a9 V7 m: T1 i3 k
- Y; h- H4 ], z% R
STATUS memPartDestroy(PART_ID partId)
. w' s1 h0 M! I5 j
{
! s& Y) n% H& g$ J! x
return (ERROR);
( {. \ x- r- t+ a y2 H3 _ e
}
5 ]3 s7 F# Z0 K7 U+ `. j" B
& O/ `4 L' n! g# T1 g, D
void memAddToPool(FAST char *pPool, FAST unsigned poolSize)
9 W7 t O% h3 U+ X0 [; u
{
9 ~' N! }1 {- V4 B7 N
(void)memPartAddToPool(&memSysPartition, pPool, poolSize);
) z+ g3 i5 b& r; v2 ]* t
}
+ m% ~2 R$ H5 [$ L. K* f) X
( { `: t: @ C' a
- Q w9 ~; l: A8 `& R& _
static STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize)
- E. H4 r$ j1 M6 r) P, l. ^
{
: s) S" O8 Y% Y, A8 ?# P3 z
BLOCK_HDR* pHdrStart;
% [3 `# u j/ m) q7 r! A5 g8 N2 Z
BLOCK_HDR* pHdrMid;
2 a H& H0 r- f1 r$ k, `! i
BLOCK_HDR* pHdrEnd;
8 H: t l+ P7 ]) E/ Q. }
char* tmp;
6 y( y; L% m2 j O
int reducePool;
5 g; }/ x4 N4 P; @. h; n8 r
& Y3 P! z: ~1 ]3 g
if(!(IS_CLASS(partId, memPartClassId))) /* only memPartClass can call this function */
8 S: Y3 M. Q& `
{
# o9 y; F6 F! Q! g/ r5 T' t- R* r
return (ERROR);
$ c8 ]& c. Q, ?. N! `1 Q G5 _( ]
}
8 V) A% g3 m0 C5 }
$ v- l Z6 L$ Q! p0 N
tmp = (char*) MEM_ROUND_UP(pPool);
2 ]2 S% F f8 v0 ~9 p% @+ Z! G/ J
reducePool = tmp - pPool;
' p2 Q1 J$ l- C
; d* F- b4 Q3 N) l! |
/* adjust the lenght */
7 l! R, [7 O; e/ Y; k0 l3 e) W
if(poolSize >= reducePool)
; y' ~: l3 F, d7 r
{
5 _" f6 M+ } G- }8 }' {
poolSize -= reducePool;
$ d" h0 c" ]0 a1 y
}
$ \: J5 o0 `3 P# M2 c4 z
else
& `- w; W; g+ A9 N
{
|1 Q! C, F1 i: p+ \
poolSize = 0;
* _! R" w2 x6 U/ {6 L6 d( V
}
/ `% N3 l( p8 o5 A, `5 C7 k
pPool = tmp;
U* H+ F5 C+ g% s4 @
# ^! Y2 O/ r) }, ~4 t. P8 C
poolSize = MEM_ROUND_DOWN(poolSize);
) y4 _8 k5 G7 ^/ _+ d; J
9 f3 Q( B0 X7 P* [
/* at least one valid free block and three header blocks */
' L$ b$ T! Y7 Z6 C5 _
if((sizeof(BLOCK_HDR)*3 + (partId->minBlockWords*2)) > poolSize)
: b* d0 g1 I N. Y
{
8 J# K2 m. Y; L; h
return (ERROR);
* E1 d/ o4 [) q. E/ A* s4 g+ d {' U
}
% e# H9 l' y( X1 {; l' M+ t
, r$ v* y" M* m, k4 o
/* initialize three blocks */
7 Q# I* [% Y! |7 f$ D0 s) F: Z* a
pHdrStart = (BLOCK_HDR*)pPool;
5 z& L: i9 r+ I% C
pHdrStart->prevHdr = NULL;
3 N- y2 _+ q, ~, d' r3 e. O
pHdrStart->free = FALSE; /* never in use */
# x3 d4 [) E) r3 \5 J6 T
pHdrStart->nWords = sizeof(BLOCK_HDR) >> 1;
$ P, z0 r% _7 h
5 y3 |" p# P5 t$ {5 X# \& h
pHdrMid = NEXT_HDR(pHdrStart);
, K$ j) P6 c; h$ x! {; ^5 I: V+ a0 q
pHdrMid->prevHdr = pHdrStart;
6 C6 }0 E6 a; j( @2 E1 e4 m, M! V# `
pHdrMid->free = TRUE; /* the main block */
6 }+ k/ g3 l) c: T# S/ R
pHdrMid->nWords = (poolSize - 2*sizeof(BLOCK_HDR)) >> 1;
' C* Z7 c: _# R2 ]$ L
4 w& r; z3 A4 o D$ K
pHdrEnd = NEXT_HDR(pHdrMid);
' ~2 R5 g5 I8 n
pHdrEnd->prevHdr = pHdrMid;
- P9 I( n+ e: h; Q0 @. s3 W
pHdrEnd->free = FALSE;
) @2 G% F5 j2 q9 {' `/ Y" P
pHdrEnd->nWords = sizeof (BLOCK_HDR) >> 1;
: J) W6 K' Y+ U2 Y; |
$ G9 o. b0 I, j
/* TODO take sem hear */
5 R3 y4 ~( R( S$ {7 u1 {- _
semTake(partId->semPartId, WAIT_FOREVER);
) b. O$ w# e+ N4 H2 ~; ^
q4 Z7 j. {6 L% G
dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdrMid));
! N$ |0 r8 a: r. Y9 X( q/ M5 ?( _
partId->totalWords += (poolSize >> 1);
( @# K! Q; B' x# z/ A. E$ D
2 P# e; q- ]+ t+ ?; Y" r
/* TODO give sem hear */
6 {8 s$ ^6 K2 W9 k$ k/ [
semGive(partId->semPartId);
/ f5 E& z$ n# @$ N
% |7 v& C- N" j, J- v
+ E8 N5 w d2 F! f! f+ w* E4 x% i
return (OK);
+ d* X' U( K8 v2 z: a0 K
}
; g$ W* E- v0 U! o. F- { w
5 R% L. l1 k- J1 f& ]! n
void* memPartAllignedAlloc(FAST PART_ID partId, unsigned nBytes, unsigned align)
, Q, v: e$ k3 v: r9 K b
{
! h' Q4 m. N. j' K$ ^. b/ d
FAST unsigned nWords;
- k6 P% ?3 `; u/ G. O. n
FAST unsigned nWordsExtra;
' \! N( K0 P" ?6 y
FAST DL_NODE* pNode;
, S7 s# u2 A' L( m# Y
FAST BLOCK_HDR* pHdr;
9 F) ^; `' |4 ^5 o
BLOCK_HDR* pNewHdr;
; X+ M) c% Z* f0 p1 }/ s$ k
BLOCK_HDR* origpHdr;
; q9 N0 T1 m4 {& \% X1 I
4 a( k6 R* O8 r h o9 n( D8 x* T, ^
if(!(IS_CLASS(partId, memPartClassId))) /* only memPartClass can call this function */
' J8 }1 j& {) ~$ a: e7 p7 I
{
6 k6 L4 q# B! l: s& _. g2 e
return (NULL);
0 w+ o/ A" Q) \) ]0 J) g) ^
}
, F- I2 p& j0 G( O; K5 N+ p( s% r
( @" R% T; N6 T: T9 h) d0 F U9 Q
nWords = (MEM_ROUND_UP(nBytes)+sizeof(BLOCK_HDR)) >>1;
' Q7 X, }' @: K1 l5 k. G" |
2 q" Y" F' f# F4 N0 u
if((nWords<<1) < nBytes)
2 `) q! `8 I+ b3 [9 x) D
{
; m9 ~5 |4 o1 m/ g
/* TODO suspend the task */
! y5 E! m' M0 d5 j
return (NULL);
8 N, m Q+ V ?* g; B
}
y/ A, s) x3 C
1 i7 X! [5 S6 R$ G3 r4 C
if(nWords < partId->minBlockWords)
$ r3 T4 H4 `% u+ l2 }
{
! t* n' i. P* L& I- Y
nWords = partId->minBlockWords;
4 b' q) F/ ?, k; O6 d0 g5 j. \
}
8 n' S; |( a% r A
9 l# f2 g! Y/ W( v$ U* w [2 F
/* TODO task the semaphore hear */
4 t) I( }) J) B2 ?9 }1 U! T% W6 z
semTake(partId->semPartId, WAIT_FOREVER);
# e& V( H& G" R7 i8 R$ j4 O4 C
pNode = DLL_FIRST(&partId->freeList);
* y3 e! O1 ~; Z8 Y! i# G- H
nWordsExtra = nWords + align/2; /* why? */
: g- ~# r% O" a$ n
0 |" @! z. H7 i8 ~7 ?8 \
for(;;)
1 c% D9 g4 _' O( L3 K
{
4 H2 f( K2 `9 v
while(NULL != pNode)
% C( s9 e# ]6 g
{
% L' a: H- D) m3 K) Z
if((NODE_TO_HDR(pNode)->nWords > nWordsExtra) ||
2 `# j0 M. P7 ^4 U. `( ?1 |0 S
((NODE_TO_HDR(pNode)->nWords == nWords) &&
: q7 S8 b) k; J% ^
(ALIGNED(HDR_TO_BLOCK(NODE_TO_HDR(pNode)), align))))
; N' p ^4 @* h% B# U( S+ N6 P: C5 F
{
" x J1 c% D$ I& d
break;
8 {1 G& h! j+ g8 @+ b6 O! B
}
' h s% J' {9 w7 d/ m* I' O% J
8 `) n F5 R" f7 ~0 d0 J# O
pNode = DLL_NEXT(pNode);
* u- z0 q( a- `* g7 M/ f# b
}
) {: w6 E. ~4 h/ R7 V: m5 q
% ?% A1 l P3 g6 C6 y
if(NULL == pNode)
) J0 u- v: j6 D
{
$ W6 f/ J: { b9 ]7 a1 C; h+ w
/*TODO give the semaphore */
4 j( X T# N5 p0 b" j# ?
semGive(partId->semPartId);
1 W: \; k' g# s; q
return NULL;
: A# y, `4 }, y3 Z ?: b& Q1 w
}
" A9 H' M: [0 [* `: l# m
; O& K. {7 C$ w
pHdr = NODE_TO_HDR(pNode);
$ B/ V7 g) X$ q0 J6 h( i d
origpHdr = pHdr;
$ b a# g; L/ B l' Q7 b+ D# a
2 f3 |% }1 Z. d2 l
pNewHdr = memAlignedBlockSplit(partId, pHdr, nWords, partId->minBlockWords, align);
& _! }+ u2 H3 ?" x
if(NULL != pNewHdr)
5 b5 Q/ h* q- a% t" n2 z) X
{
! P* N7 m0 U+ Z q; M6 ~! E
pHdr = pNewHdr;
) X" S4 h" S8 r. H
break;
3 L( ^# `$ @; @& ^8 B/ I2 ]* R
}
! Q$ c$ l) P; s+ x- y7 l
. o J& H) y1 o& t( d' n7 v% s
pNode = DLL_NEXT(pNode);
8 Y+ ~8 W( J: D# \
}
/ W& Z/ w+ y$ Z9 t9 t6 F
* Z$ N6 e+ V* N6 h; X) L5 `
pHdr->free = FALSE;
# @3 Q! X/ y' ?. d g" l
partId->allBlocksAlloc++;
; O) |% ]& _4 [2 G" {* Y" k
partId->allWordsAlloc += pHdr->nWords;
* G4 s' _# G- p# K* D4 d5 u9 `
partId->curBlocksAlloc++;
' M" Y j m# X# Y) D. J) U K
partId->curWordsAlloc += pHdr->nWords;
: \5 m" ]) x4 l6 m" E
0 v3 ]7 C: o0 Z. }: |% k
/*TODO give the semaphore hear */
9 \: M* q n" o# ^" n1 T9 H
semGive(partId->semPartId);
1 ?2 b5 [3 S2 K2 w( k* l
return (HDR_TO_BLOCK(pHdr));
T8 L. {: y& ]" e4 _" y
+ r& m' X% F/ x2 s; o9 f
}
' j, J2 u" B" A" r
1 {3 H& Z8 n- J9 p9 T/ d a$ V; [0 x
void* memPartAlloc(FAST PART_ID partId, unsigned bytes)
7 O- M4 P" ?+ w. S! X# F
{
+ e2 M+ _) U1 b' ^ W& D
return memPartAllignedAlloc(partId, bytes, memDefaultAlign);
8 [9 ^- x% D, z1 l; k8 Q. n
}
( M6 J1 J2 ~/ p0 ^5 E, V7 q
* p! X8 f1 H+ L5 Z
STATUS memPartFree(PART_ID partId, char* pBlock)
" }; ~2 z4 J. |% w) m
{
# k2 U( h i; |5 N; V8 u% ~; d
FAST BLOCK_HDR *pHdr;
& ?: V y3 s1 W( M+ F
FAST unsigned nWords;
% C8 ]/ U. F! ~. i- O
FAST BLOCK_HDR *pNextHdr;
7 a$ K$ w! c: o+ [) _
3 E+ K$ I2 i5 u7 ^/ ]- M
if(!IS_CLASS(partId, memPartClassId))
$ T7 h3 b$ [2 V/ N7 x
{
% @# ^ C. a# ]! H1 j( j. @+ N
return (ERROR);
. Q8 P* \- c) S7 I, f" r) J
}
+ C& x; i5 d0 g- A$ X$ S3 J
, q; c5 S% {( }* p
if(NULL == pBlock)
" F- H3 C t6 ~; F
{
. u+ q+ [. N0 m7 y0 @
return (OK);
8 P# r. _9 a" c2 P% w/ }2 Q( Z
}
# ?' x: U3 M/ `1 D4 |3 T
3 b8 k7 A" H" V% `0 [% s/ z, X
pHdr = BLOCK_TO_HDR(pBlock);
! Y7 ~* c8 {( S6 o) b
4 K4 L* [+ a7 t" D, s
semTake(partId->semPartId, WAIT_FOREVER);
; [# w( [7 | ^: m" F4 A! ?
( D1 N8 ?3 z# F& h& ?9 J
if((partId->options & MEM_BLOCK_CHECK)
: K$ J; s" @# A. L
&& !memPartBlockIsValid(partId, pHdr, FALSE))
+ ^3 I* b0 A$ ~; m' L. N3 p
{
# L( |# B) S3 f$ m+ @1 g
semGive(partId->semPartId);
7 M8 ?, Q! {% X2 I% M6 X9 m" `/ @
return (ERROR);
8 M! W+ K4 e* C+ p; ~. P7 @+ I
}
: i) p0 ?! x! u: u, j
" Q. x2 Z m8 T/ ^6 k
nWords = pHdr->nWords;
- D+ M$ `7 b _! j Z" C
if(PREV_HDR(pHdr)->free)
, A" \. h6 x( v1 m2 t) S
{/* the prev hdr is free and than coalesce with it */
9 f! d$ A5 M t& I/ ]+ `
pHdr->free = FALSE;
1 I, r: ]) k: s+ v
pHdr = PREV_HDR(pHdr);
: d u2 \5 N- c1 b
pHdr->nWords += nWords;
) T+ H1 C! C$ _0 G5 y0 O
}
* q+ z( `; s" K4 y B0 A
else
0 B/ G5 F( W! J
{
( ]% p8 m4 V* q, [; @
pHdr->free = TRUE;
, H! v. ~" H/ @1 K& |/ w
dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdr));
6 f2 }) D" X; b3 {3 h
}
4 u5 d: P+ Z: B2 Y0 A ^( @9 E! q
8 n) k% `+ ~! v8 y7 S, ]7 G4 U
/* check to coalesce with the next */
: L: N) g8 v3 a8 P% m; `: {% _
pNextHdr = NEXT_HDR(pHdr);
" h3 L/ U& o4 d8 X! `4 V+ \" Y
if(pNextHdr->free)
8 S7 s/ |% B0 q6 ]# ?) Y- G
{
' A) }! R. u% K5 D0 g9 O$ |
pHdr->nWords += pNextHdr->nWords;
, B1 M/ ]/ [# K4 M$ r
dllRemove(&partId->freeList, HDR_TO_NODE(pNextHdr));
$ y, H* B; e& C; q
}
4 t. p/ L4 |2 Z. T
3 e z1 b9 H1 c2 ~) }* j) {
/* cannot use pNextHdr->prevHdr=pHdr hear */
( t6 s5 i" ?* d, V6 M
NEXT_HDR(pHdr)->prevHdr = pHdr;
: S/ _5 G3 [7 N3 @1 `3 k0 d/ T
& \' e9 G) g4 A5 L
partId->curBlocksAlloc--;
% ^% l+ Y6 {" x1 K# G
partId->curWordsAlloc -= nWords;
' e3 M7 J9 Q7 p y
3 @5 i4 f% U, d5 c
/* TODO give sem hear */
0 G/ [$ F' J( N; L' p J
semGive(partId->semPartId);
. ?0 q- c+ v$ @( H2 D$ A. M
$ }! U+ D( \) h8 N1 a5 s2 ~
return (OK);
- w" h! c s+ a- W0 L
}
+ a3 S. P4 o n8 H* V1 l3 r
: K5 s* G/ R; I F9 u7 G
static BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree)
0 a2 {. C p' R# I; A, S% X" A
{
) ?3 Q( C* E" A- I& P8 D% v2 I0 ]5 e
BOOL valid;
* V. {1 I' J8 ^( X5 i: u1 {
8 x8 h; A6 M/ S' I |; B; R) \
TASK_LOCK();
& }9 s1 p# [) W$ ^0 m$ l/ M
semGive(partId->semPartId);
2 h( ~; l0 m* ]6 u2 C6 i
& S( l. d2 Y, i6 \" U. }( o
valid = MEM_ALIGNED(pHdr)
* z% B; O* w! m9 h/ ?5 D# U
&& MEM_ALIGNED(pHdr->nWords*2)
: ~. ^* t* h* |
&& (pHdr->nWords < partId->totalWords)
: h# J6 d4 L9 K6 r3 j+ x# ?
&& (pHdr->free == isFree)
e$ ^7 Y ?7 m8 {0 l5 k
&& (pHdr == PREV_HDR(NEXT_HDR(pHdr)))
$ r- I4 r" E) j2 ^1 _
&& (pHdr == NEXT_HDR(PREV_HDR(pHdr)));
# p% s7 I; W' r+ @2 P0 ?8 d- o: s
- \2 R0 l' ^( r% a( ]& B& U( [
semTake(partId->semPartId, WAIT_FOREVER);
' |, y# x0 \7 q" V: v0 s; K
TASK_UNLOCK();
, I$ R, d0 @; O' ^6 S( a7 s Q
5 `! L+ t' l4 Y) p# Z" l: O6 x
return valid;
8 U- Q' \" H% P5 m Z) \
}
; f. \, }% S) R% Y" \/ W
; t8 F# D5 t3 i( z1 f, d" C
static BLOCK_HDR* memAlignedBlockSplit(PART_ID partId
4 F2 t, w1 A, d# @# @5 _" Z
, FAST BLOCK_HDR* pHdr
p2 K2 |/ _( c% w
, FAST unsigned nWords
! O& _2 R7 e5 `6 O
, unsigned minWords
9 W9 }, \% p2 x. b
, unsigned align)
5 _+ H+ t! k% I3 [ m- `$ \
{
" o" @$ ?/ ]8 x% O' j; x
FAST BLOCK_HDR *pNewHdr;
5 l. P* u* V1 z2 s
FAST BLOCK_HDR *pNextHdr;
! t# j1 h1 ?2 Y+ W* o3 Z
FAST char *endOfBlock;
0 Y2 G( R9 H1 x$ F( e$ s
FAST char *pNewBlock;
: p- D5 t- k; y* I1 ]5 x2 ~
int blockSize;
" g5 F* I2 Y5 _! z4 O$ U) d
7 T% z; g% m8 \. C; r7 _! x+ g! G$ t
endOfBlock = (char*)pHdr + (pHdr->nWords*2);
6 ]1 w, W1 D, l
% X5 w4 C) n: W7 B
pNewBlock = (char*)((unsigned)endOfBlock - ((nWords - sizeof(BLOCK_HDR)/2)*2));
0 `0 j; Y; f" L7 M9 t! B( O0 X, T2 P
; C9 R2 k: B& ?
pNewBlock = (char*)((unsigned)pNewBlock & (~(align-1)));
4 x1 \4 v6 @+ A/ K! F. d
: C" V. H$ Y, g5 `, r
pNewHdr = BLOCK_TO_HDR(pNewBlock);
1 g. x: v$ @# q- E; s* N3 M$ u
% P# I" l( {" T( S5 V
blockSize = ((char*)pNewHdr - (char*)pHdr)/2;
# P4 [8 I. X# D% z1 f, C2 o! y ~
9 }3 M+ `: V0 z4 {# A# F" A
if(blockSize < minWords)
, N0 H9 M$ n, Z- v7 u8 _
{
6 T5 ~" F/ @, \! U; U9 b( t, ~
if(pNewHdr == pHdr)
, i8 v: [! ]% c) F, U. k, c
{
9 [8 R# c% k3 @6 T
dllRemove(&partId->freeList, HDR_TO_NODE(pHdr));
0 o( q" b" e% Z
}
1 a/ h& ^6 [2 _# |/ y
else
6 p$ S3 l# m" {+ C- h
{
$ C# @- `4 `) f' S& ]' Z# Z
return NULL;
( K5 ?" Q# f( y3 |" ?; p# n: c
}
. ]+ r7 b# c+ G6 v6 v
}
* a5 X4 j& d9 u$ V: K7 p4 O
else
" y7 a, q9 {6 J7 i! s' Q
{ /* recaculate pHdr */
% R& y, G$ D$ @; W" o- u+ c$ N* {
pNewHdr->prevHdr = pHdr;
$ `; m+ [7 ^# E
pHdr->nWords = blockSize;
7 y, b. v$ U9 M/ C. H
}
/ S: M" y4 E) C
* a& J& b9 I6 `8 [
if(((U32)endOfBlock - (U32)pNewHdr - (nWords*2)) < (minWords*2))
' g' A( L# |; p3 Y
{
( R8 D# u; C/ r8 ]- E$ D
pNewHdr->nWords = (endOfBlock - pNewBlock + sizeof(BLOCK_HDR))/2;
+ u! S+ ~: p' i/ n# }1 W3 _) T
pNewHdr->free = TRUE;
: p8 Q9 A5 B2 W7 F5 f
6 \4 b# q2 g; O0 P
NEXT_HDR(pNewHdr)->prevHdr = pNewHdr;
8 y5 k$ F# s0 l. b
}
2 T. u/ K* {, o8 R" {8 S
else
& M# V) O# y/ J3 e3 n% F' a+ |
{/* space left is enough to be a fragment on the free list then */
m) ], h2 D- \4 M# g( X
pNewHdr->nWords = nWords;
3 i, B# _. a" Z: R
pNewHdr->free = TRUE;
* i1 @- k" W7 k9 d p6 s
4 f. X' d! q( A& R8 q$ _0 k2 @
pNextHdr = NEXT_HDR(pNewHdr);
6 A( ]- Z! x3 \( c! }
/* words 包括BlockHdr */
: Z! H# f/ ~3 w5 R
pNextHdr->nWords = ((U32)endOfBlock - (U32)pNextHdr) / 2;
8 H; G" g0 H) _, ?0 x: }' |
pNextHdr->prevHdr = pNewHdr;
* l% j! i( n1 `( O
pNextHdr->free = TRUE;
x: ^4 g: |) N- i! b
% k/ f0 u& B) e7 i* S- U% i3 U
dllAdd(&partId->freeList, HDR_TO_NODE(pNextHdr));
8 {( H/ |7 M' _( t. a5 h# B9 a9 _
, X, }1 ]) g) ? A5 r- Y0 G8 b
NEXT_HDR(pNextHdr)->prevHdr = pNewHdr;
! s1 D6 _+ c! T5 G! e
}
3 Z d9 ^/ P, b1 R
+ `9 |" u: \/ j/ _
return (pNewHdr);
9 G& ]) h, d2 N
}
! T* t! P* k& D
' y0 x6 G9 x6 l7 l$ @
static void memPartSemInit(PART_ID partId)
' e' u2 j' _5 P/ H. d Y' O
{
) X0 @. g# W; s& X
semBInit(&semMemSysPartition, SEM_Q_FIFO, SEM_FULL);
) q# X( S+ k- K( G" K$ F6 {
4 L# v# C; J/ O. h9 u8 v
partId->semPartId = &semMemSysPartition;
) I0 u) c/ _. i0 R4 }+ q( Q
}
5 s$ d! Y6 A2 g: ?
6 s! A S" G& L! ~5 S
void* malloc(unsigned bytes)
% p8 X/ R% I( ^- O/ m: X# ~0 B
{
) ]8 `4 `2 a8 y1 n6 a8 \# l
return memPartAlloc(memSysPartId, bytes);
% k" p4 _1 _/ s2 ?5 I! Y
}
# N' I L$ y1 y; ]5 ]2 k
, z# ?6 x" v( ]
void free(void* p)
" r# V2 g& f8 v! j% q+ i7 N
{
" u) G6 U4 a, B K7 t
memPartFree(memSysPartId, (char*)p);
9 x% ~7 Z/ R2 f0 \; n
}
+ ?7 D5 n$ M: w5 W
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5