- 在线时间
- 490 小时
- 最后登录
- 2024-2-3
- 注册时间
- 2013-2-28
- 听众数
- 117
- 收听数
- 46
- 能力
- 268 分
- 体力
- 39235 点
- 威望
- 1340 点
- 阅读权限
- 255
- 积分
- 31237
- 相册
- 2
- 日志
- 0
- 记录
- 0
- 帖子
- 1388
- 主题
- 937
- 精华
- 0
- 分享
- 0
- 好友
- 111
升级   0% TA的每日心情 | 衰 2020-10-25 11:55 |
---|
签到天数: 264 天 [LV.8]以坛为家I
- 自我介绍
- 内蒙古大学计算机学院
 群组: 2013年数学建模国赛备 |
想知道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
|