在线时间 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++下的版本,更方便调试。有需要请留言
- d; L0 f' m7 E. a3 w: J 1 t6 G- C4 Q) x
3 N7 l8 D$ D0 {! O
! {( ?' \5 _0 m( Z7 o *\file
( i5 ^" P3 g) q8 J: r+ y *\brief 6 ?3 G: w1 H3 F
*\details # x) }* D) ~4 @' Q+ L, [5 i1 V& L
** J" A* G: H- B9 c( b
*\author Janson3 v' b! x' e; K
*\version
( F J. @* P* P% D p, C *\date 04Jan12% D6 z: [" ?. d' L
*
% G8 X3 r" a5 X0 D) @8 f R: C% f- q3 x *\warning
+ @2 ]( n) E- K. w *$ V6 Y: k# L4 w
*\history \arg 30Jan12, Janson, Create the file% s1 U3 e' M3 \
* modify from VxWorks source
2 e, {0 x$ o7 w+ ~8 o * Legal Declaration: it is for studying VxWorks only.
# S% o/ s; o; N( Y* p7 Q4 `# d */' i0 p: K) m% i% Y' j
#include "includes.h"7 c& c2 G" U$ I0 t6 W9 w- @* `
2 N9 c5 H- y& H
/* The memParLib.h file is hear:- a1 i6 }9 e2 v1 K# T
https://code.google.com/p/vxwork ... rivate/memPartLib.h ( j8 R# z7 v0 Y( i3 f
*/# f/ Q' m4 w$ Q! g" i/ x! `5 f9 d
. Z* _5 Q `+ L1 a% M" N
/* optional check for bad blocks */0 \8 [1 w6 c |5 Y& `7 O4 {
, B' g) e3 L8 ~) i( V #define MEM_BLOCK_CHECK 0x10
; \& [% c# q) A# G9 }1 P
1 i5 }$ O1 u& M4 ] /* response to errors when allocating memory */7 O; n7 U7 t+ C% d% g
' W8 S9 l$ O a$ I% H; A
#define MEM_ALLOC_ERROR_LOG_FLAG 0x20
7 r! X: E1 U& B #define MEM_ALLOC_ERROR_SUSPEND_FLAG 0x40
( E: x+ w/ i4 ?) ~ : g$ L2 `( i$ D5 s. D+ Y1 o/ W
/* response to errors when freeing memory */
0 r+ c6 ?3 P3 V6 d8 Z3 J
: g5 H( Z2 Y$ ?3 ]9 I #define MEM_BLOCK_ERROR_LOG_FLAG 0x80. c1 k$ g+ l( z
#define MEM_BLOCK_ERROR_SUSPEND_FLAG 0x100
3 V. G% ?0 n/ T; M " b1 T3 O9 v. b" A& ?% P6 W M
#define NEXT_HDR(pHdr) ((BLOCK_HDR *) ((char *) (pHdr) + (2 * (pHdr)->nWords)))
5 D0 t& l9 y- O* D0 S& @# z #define PREV_HDR(pHdr) ((pHdr)->prevHdr)
4 n6 P8 T" G, y) x' J4 F7 i6 J
) |. k% C' r$ o: c #define HDR_TO_BLOCK(pHdr) ((char *) ((int) pHdr + sizeof (BLOCK_HDR)))) J9 |) q, n+ O/ t& K
#define BLOCK_TO_HDR(pBlock) ((BLOCK_HDR *) ((int) pBlock - \- j' Z9 O5 k0 d# G& _" }
sizeof(BLOCK_HDR)))
# w4 b8 d6 a9 K8 r+ D: _ 9 I1 d2 B6 {2 ?
#define HDR_TO_NODE(pHdr) (& ((FREE_BLOCK *) pHdr)->node)
: Y5 n+ r/ G- A; M7 u P #define NODE_TO_HDR(pNode) ((BLOCK_HDR *) ((int) pNode - \6 p/ o3 W! o T; ^$ l
OFFSET (FREE_BLOCK, node)))& e+ O7 F }3 X* e
, O, i5 N' t F4 ?0 x- U1 m static BOOL memPartLibInstalled = FALSE;
- ?- A- z S" l. T& l
: ]# @) }: W" F+ S5 X* ^/ H static OBJ_CLASS memPartClass;" V, g+ G* o+ N9 R8 K$ x8 p
CLASS_ID memPartClassId = &memPartClass;
! K/ j; g& O4 h7 M* n& I
3 q" t' z2 x- f: Z static PARTITION memSysPartition;
( k! o' A8 p. \% V$ Z9 ^ PART_ID memSysPartId = &memSysPartition;+ c& ^9 A; M% b: t. s7 I) t
U32 memDefaultAlign = _ALLOC_ALIGN_SIZE;! E; h2 ^8 F: h$ _4 c
8 V+ j3 B1 w. } static SEMAPHORE semMemSysPartition;9 F; P' U+ e I. I) V2 o
# }# A" g; m; [* \
static void memPartSemInit(PART_ID partId);" G' Q6 D) @6 V: i) f$ K
7 I9 T( C0 \, r( k9 x$ o/ n; i/ N7 U FUNCTION memPartSemInitRtn = (FUNCTION) memPartSemInit;4 P1 s% D0 p$ Q/ H
; F; O L6 _# j) [6 h1 ~1 k( s unsigned memPartDefaultOption = MEM_BLOCK_ERROR_SUSPEND_FLAG | MEM_BLOCK_CHECK;+ b) s6 C. x% r/ w& u
1 J" o$ O, J; N
static BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree);# ]" V3 ~0 @. D
static BLOCK_HDR* memAlignedBlockSplit(PART_ID partId }' C3 b# N3 S0 y
, FAST BLOCK_HDR* pHdr% j1 _3 J2 i: W' k6 z: E4 l6 z" Y
, FAST unsigned nWords
" Y( c# T b. l , unsigned minWords+ Z" p. [1 R d5 s% Y2 s
, unsigned align);
! @2 m3 L# N+ G r; l r2 ^8 v0 M
# o' s( t+ P" j7 @0 H) L" q static STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize);
# E- l2 J5 h# Q& } s# f7 q* D
; q+ u1 v& Q+ d- v STATUS memPartLibInit(char* pPool, unsigned poolSize)
+ k$ m' y% f! f9 U {, x( h2 h2 f: g# u
if((!memPartLibInstalled) && & o6 D, M& ? }7 d O4 f# K
(OK == classInit(memPartClassId, sizeof(PARTITION), OFFSET(PARTITION, objCore)
! [0 d8 }- T4 \+ `1 l h7 A, f , (FUNCTION)memPartCreate, (FUNCTION)memPartInit, (FUNCTION)memPartDestroy)))( ^* r2 p$ l3 g+ C% H2 w+ q% ^
{
- m" G5 q9 F5 D5 `" m: s: _8 M memPartInit(&memSysPartition, pPool, poolSize);
/ \* A8 R/ M8 F# j( ^) F memPartLibInstalled = TRUE;
, y3 R8 t/ Z. e0 w7 ? }
% J9 r: m% f8 \0 _
, W' f+ R0 }3 R2 o6 o( L6 i return ((memPartLibInstalled)? OK : ERROR);
( s5 r- S5 J7 a1 G6 @ }. q" g6 K& G& A. |% E
7 E7 O% D$ a! o* J) S' K$ q& }0 T PART_ID memPartCreate(char* pPool, unsigned poolSize)) L1 K6 x! N1 q; A
{
2 o9 m7 r5 |" o" a# m3 \ PART_ID pPart = (PART_ID)objAlloc(memPartClassId);
, @3 o- o3 Y$ n' ?& k
$ d- y1 x3 K5 G( z if(NULL != pPart)
: T; Y8 k* Q" f {
; {) e* n6 f/ T/ U. x% A memPartInit(pPart, pPool, poolSize);
( b' P: h; w, z6 z, W0 Z5 M2 D }
4 n9 { q3 U2 [2 c4 `8 f# T 8 |/ [, L9 n4 _$ Q: X
return pPart;" j1 E" y& H! B4 n% C6 f Z
}9 U7 u4 q' g% d% X
) i5 B3 m; G$ L4 u. r* t void memPartInit(PART_ID partId, char* pPool, unsigned poolSize)1 C- F+ ?. f0 o
{. b3 R4 i1 q4 B5 m5 D, s6 v I3 J" x+ D0 x
memset((void*)partId, 0, sizeof(*partId));
. ?4 D5 `4 n8 K$ O! A
0 H! P y- v0 I# k( I4 ?: z, i% u2 \ partId->options = memPartDefaultOption;
- ~0 g$ A7 h. K3 l2 g/ ` partId->minBlockWords = sizeof (FREE_BLOCK) >> 1; /* word not byte */
- ?5 n+ s6 a; o J. T / ]2 R0 }! y2 N ^1 [: i! j
(* memPartSemInitRtn) (partId);
0 J) O$ f d, w; _+ k& l- l' V2 C. t- c
7 K- b" D$ t5 ?( C/ y9 S dllInit(&partId->freeList);/ A; d! P" Q8 u% G
8 S+ B0 j$ E) X9 z ^; r0 | objCoreInit(&partId->objCore, memPartClassId); c3 x2 Z) m: `; @. j' O0 R
6 x) U. f* Q. I5 }% U/ J memPartAddToPool(partId, pPool, poolSize);
4 c+ _! c7 Y- u/ f- ]3 J }6 L' a; [ H! k
7 A% j; H8 U2 p, E% A) D
STATUS memPartDestroy(PART_ID partId)2 h! {0 ?; @$ r8 Y K; K3 @
{8 S! f. R, A2 e8 E( \" v0 I
return (ERROR);
3 g: S& g. m% c: u! W. H }
) n( t1 y w' a ( C& T1 H5 u! K% }9 h! ?0 |3 `
void memAddToPool(FAST char *pPool, FAST unsigned poolSize)
( p* m0 z) }+ Q8 G" p6 ]- o {/ ~2 }, E( G1 g. |3 W
(void)memPartAddToPool(&memSysPartition, pPool, poolSize);' ], v- d* ?# p6 x% H4 A; T
}
: N4 e0 B% g7 p8 z" p6 t9 j
9 h; x3 D) F( r( o
7 j) |! c' H/ \$ Y7 J" v static STATUS memPartAddToPool(PART_ID partId, char* pPool, unsigned poolSize)+ N* R/ S5 T! p1 O9 w
{
9 s9 `$ w# Y. A |) N BLOCK_HDR* pHdrStart;$ J8 Y, L! g3 E2 u5 \
BLOCK_HDR* pHdrMid;
6 @/ S5 Y% X8 o6 ?) B8 ^ BLOCK_HDR* pHdrEnd;* [! j" I* V6 @3 b7 L1 x$ S l
char* tmp;
. {5 g! B% M: x4 X" [ int reducePool;, w* @" J" b9 }, {- t( }( ^( p
- Z+ q8 g: ^( R# D
if(!(IS_CLASS(partId, memPartClassId))) /* only memPartClass can call this function */7 g }! v3 J" ?9 n8 X+ `
{; `) {# D4 k/ ^' d
return (ERROR);
0 t" y! b0 Q+ }* Q z, j" v5 n/ I1 P }. A: d' C1 }" I2 q- u6 a
" ^3 \9 I7 K C# F) c* J9 B tmp = (char*) MEM_ROUND_UP(pPool);5 u% F, w5 k! q7 `% @& A
reducePool = tmp - pPool;0 D0 R4 E: {' b5 V' s& w
5 j4 }- Y+ ]: g7 U
/* adjust the lenght */; M5 C0 a. s u7 ~7 q
if(poolSize >= reducePool)
$ ]- Z: _" B) X' G/ s) d- \ {
; |, Q# q" o; q# a" P poolSize -= reducePool;% l* [$ }$ c/ l% m& b3 [( Z; u* D7 x8 {
}
+ f2 o% s; ^( A- t7 ?7 z else
' p$ m R) F6 @: Z. U% q {
( C: ?6 a( q$ ]* B poolSize = 0;
' L6 |' I% l+ \% ~1 i }) F( ^- r5 R. o
pPool = tmp;$ A5 C3 A8 w3 }; k, A6 J7 T! }
$ [- k H* s/ t, R; x% N$ t" J+ ~, i poolSize = MEM_ROUND_DOWN(poolSize);
; u9 {7 s4 k% H9 `8 N4 O4 Z4 D
/ S0 T) u) v+ h* @1 G' w' T /* at least one valid free block and three header blocks */
6 E# O7 ]. y* a if((sizeof(BLOCK_HDR)*3 + (partId->minBlockWords*2)) > poolSize)3 O3 g1 w4 u; N& i
{
7 M/ k/ P, k" d6 y5 P% s return (ERROR);+ a* X2 f. B% `# g( U! d: R+ \
}) I' s8 n/ }1 Y% ^+ S
4 i9 e; ^+ H! q1 G1 D: j /* initialize three blocks */6 v# i: D+ i1 a2 D6 k. x3 ~
pHdrStart = (BLOCK_HDR*)pPool;
p+ A" o# Y: E; I! f pHdrStart->prevHdr = NULL; r2 M4 u5 j; q* j8 G
pHdrStart->free = FALSE; /* never in use */ Q2 I$ L, p3 k5 n8 O, p
pHdrStart->nWords = sizeof(BLOCK_HDR) >> 1;6 T& \0 N! V" H1 b" r
3 z7 A( r+ X0 S( D7 E7 x( v; I pHdrMid = NEXT_HDR(pHdrStart);
2 l7 N% o& {4 x' y3 g* N$ Z pHdrMid->prevHdr = pHdrStart;
[6 n( |* ]0 _4 r& F pHdrMid->free = TRUE; /* the main block */
& X- L8 Y( q2 s7 t pHdrMid->nWords = (poolSize - 2*sizeof(BLOCK_HDR)) >> 1;
" X3 a' V' A8 j ' D* f+ R- Y) e, p2 }2 r- l
pHdrEnd = NEXT_HDR(pHdrMid);% q: J; A9 t* n2 q$ l
pHdrEnd->prevHdr = pHdrMid;% ^% c7 S3 L* b6 T/ r1 L! R' @; v
pHdrEnd->free = FALSE;
, ]* I1 T! W1 b$ U3 _ v2 Z pHdrEnd->nWords = sizeof (BLOCK_HDR) >> 1;
! {0 @+ w- Y9 ?) Q2 f4 S- m3 y7 K 3 }3 A1 k4 O2 Z" |1 ?% |6 L6 [
/* TODO take sem hear */
) {% z. Y: J$ o1 I0 m( t+ h semTake(partId->semPartId, WAIT_FOREVER); T! U1 x t0 e! V
* L) W: @8 z2 a u& N) o dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdrMid));
7 C1 T$ D, J0 i partId->totalWords += (poolSize >> 1);1 H$ z! ?- @8 s, E
& ^& J, L7 \# f& J* u- O* h
/* TODO give sem hear *// u% W# z) t$ f7 O# x
semGive(partId->semPartId);% W+ i9 `% U% z3 F8 Q
; o; `8 I! t6 y% h8 x
) m* x6 Y* U, X- _; A5 B return (OK);
: G3 }+ [; F) E }' I2 `" p! V, R' l- d
: }4 u' X4 F2 a1 G, T; @ void* memPartAllignedAlloc(FAST PART_ID partId, unsigned nBytes, unsigned align)/ o, O& G0 x: U9 U& b9 H8 I
{' O2 S( D& X8 P: ]
FAST unsigned nWords;& Y/ N5 h. ?2 w1 L! g/ q
FAST unsigned nWordsExtra;) Z- `9 }6 ?0 h4 M/ h3 M# E9 r
FAST DL_NODE* pNode;1 T8 c$ ?! H" L1 S; o7 b" Y
FAST BLOCK_HDR* pHdr;6 }& E# y9 J; F" A$ _& u, u
BLOCK_HDR* pNewHdr;. O( a3 l: \2 S2 A+ D5 H
BLOCK_HDR* origpHdr;0 l: y( d2 o2 C3 [& S/ }
4 a) ]: f6 ~1 t& }/ B; P if(!(IS_CLASS(partId, memPartClassId))) /* only memPartClass can call this function */( J- J# H) r* [8 E& R& R2 a
{
- }, g2 x' f: w1 A! \ return (NULL);4 j% ~6 b* T4 R; N
}. J: Z8 u6 n% c3 m4 w9 f M6 p
Z/ d6 j2 S u/ f nWords = (MEM_ROUND_UP(nBytes)+sizeof(BLOCK_HDR)) >>1;
2 |2 G! m4 E8 U& _) c& F8 ]
' D: }3 i3 p# u& o if((nWords<<1) < nBytes)
* r1 E0 U( [; v" O: I {* h m1 p4 h' r! Q* w
/* TODO suspend the task */5 S$ C1 e* Z8 e
return (NULL); d9 |& }; V( |% ~* v* R
}5 P" f2 |1 w% p' Z
) d" r/ c* O# g6 s& O
if(nWords < partId->minBlockWords)0 U) q3 i% e7 p, t
{! t! w6 f: i( E2 `* U+ \
nWords = partId->minBlockWords;
# c; X* L" L5 k* A* B7 X5 z }
2 ~/ ]; d, r$ u* h5 g6 h$ g
" {* X9 P N m( o$ g( {, P; K /* TODO task the semaphore hear */+ p3 t+ ^/ y. \* \7 C8 K
semTake(partId->semPartId, WAIT_FOREVER);% V: x9 L, P( Q1 Z9 Y2 P( L8 w
pNode = DLL_FIRST(&partId->freeList);4 C- f! s" \+ k
nWordsExtra = nWords + align/2; /* why? */( ~. Z. t: z: c2 b7 t4 v9 q
: W0 s4 z2 D/ Q+ m# l) G. s
for(;;)
, x. Z; D, h1 Q* i& J) X0 {( z {
: e! N* J( p! d) ] while(NULL != pNode)
- V% ^! T, t. k. r: Q {
; y1 I d* [( h. R6 {& `; @ if((NODE_TO_HDR(pNode)->nWords > nWordsExtra) ||( J- R" q0 `$ o# {1 T
((NODE_TO_HDR(pNode)->nWords == nWords) && $ X8 {9 K& I: u; V
(ALIGNED(HDR_TO_BLOCK(NODE_TO_HDR(pNode)), align))))& P [6 c% z \+ b! p6 ^/ _! D
{
( v i. z# E. Z break;; z1 S6 T2 l0 o' J) S% G
}
' _6 o2 S. a4 S, ` / ?/ v& w; a7 S9 ]. q2 C
pNode = DLL_NEXT(pNode);# n7 L) s: {: v; B$ k: L% O
}- \' P; J P2 n' w3 [( X
) _8 r. ]+ d0 ~
if(NULL == pNode)
w7 k' c$ Y# f& ~& v S {
# d) `8 I7 K! H3 j% W+ E; Q /*TODO give the semaphore */2 T- _1 ^5 \$ k2 U, b' K6 S# `
semGive(partId->semPartId);
; }7 y, E+ \/ L# x) s/ g9 i3 Z return NULL;# I# D3 R$ x8 B! a( `. ~5 O
}
- r: ?3 z$ l; Y( c! M8 t
* w5 ?: O' i' f' H: s pHdr = NODE_TO_HDR(pNode);
5 H! C& k% ^" J8 a% ~% y* L' W origpHdr = pHdr;7 z) G" S' `9 ~, ] a; w% ?1 L/ i
6 D4 f9 M8 H5 }* |
pNewHdr = memAlignedBlockSplit(partId, pHdr, nWords, partId->minBlockWords, align);
, B5 R0 U3 K7 b+ d7 H: P! Q if(NULL != pNewHdr) b# ^ Q. |0 O. \/ y
{
: u# `2 {" V; O x pHdr = pNewHdr;
( j, J; D( h5 D break;1 e7 j& [; o; e3 o
}! R' A4 U& Q) ^, ~% I
! E Y* f- L! B. f1 \9 I+ J- C# B: r
pNode = DLL_NEXT(pNode); ~# c# M" p! _- W+ ]3 z5 i
}
8 F) F( n/ B% ]; {* R9 i' z 6 f* p& I( d7 D4 D
pHdr->free = FALSE;
: N( J8 @/ n5 e, ^6 D partId->allBlocksAlloc++;
( p1 ^* _6 _" I) V$ O9 c% F- }( F partId->allWordsAlloc += pHdr->nWords;* |" ^0 N+ O: Y- d# b- }
partId->curBlocksAlloc++;
" Z" b7 P+ s, [" d5 { partId->curWordsAlloc += pHdr->nWords;
. \5 ]0 [. U$ t' {0 V* c$ x9 m$ u- p1 o$ X
: ~( g) N e$ R j2 \ /*TODO give the semaphore hear */
+ C, O t) `. r semGive(partId->semPartId);6 f% I5 \% R! f" S6 l. ~: y v
return (HDR_TO_BLOCK(pHdr));
- [! q* r( V% z/ {6 k4 c3 C 5 w/ j: h# |9 ?+ c0 ~. K
}! o% X" y6 ~& P: f
; s- O2 F) Q$ |! T* B: b5 T
void* memPartAlloc(FAST PART_ID partId, unsigned bytes)
5 s# C) ]$ X4 Q. Y& A; c {
; ~6 J7 x: n8 K2 C2 B! f0 x return memPartAllignedAlloc(partId, bytes, memDefaultAlign);/ o0 @. A9 @' e$ H) M e
}1 T$ E& K g' X/ Y! y k
9 J2 x/ z( j: ]$ a, \3 |* L3 r: p7 X STATUS memPartFree(PART_ID partId, char* pBlock)6 `4 ~" i8 Z r* X
{
& g3 }9 {5 t9 L FAST BLOCK_HDR *pHdr;
) E: g" N e8 B+ c+ [" [% Q FAST unsigned nWords;( q5 ]: }2 K2 O6 K/ J
FAST BLOCK_HDR *pNextHdr;' n; n, D. O: O K
, e, R7 C+ f. O+ }& i if(!IS_CLASS(partId, memPartClassId)), x5 G, v' ~' |
{
4 m; n1 i! t# ^ X0 M return (ERROR);
0 X0 b( g6 i2 Q j& C+ T. B$ K3 [ }* d1 t- P, P9 ~$ w, i- r
. F5 k' K/ R* p- p8 M if(NULL == pBlock), t, {) s, ^0 K
{
0 R y. k6 D8 |( K; P return (OK);' o. \1 C' }7 u1 V+ i6 F
}0 W0 d, D$ L1 Y& J0 x& F, F
- }5 S, ?& }) }) a6 q/ V" |. ^
pHdr = BLOCK_TO_HDR(pBlock);- x0 P' B% {4 K, W! f
/ a9 L* v, V- y" V$ G; Y9 a semTake(partId->semPartId, WAIT_FOREVER);1 @. Y; e3 s- H: ]( o; i
% K x. N. j0 i
if((partId->options & MEM_BLOCK_CHECK)
& }. Y9 f$ q9 Z- a && !memPartBlockIsValid(partId, pHdr, FALSE))" s7 e' Z; X3 L4 f
{
, c1 M% _* |! z% y. X1 } semGive(partId->semPartId);
' W7 f, ?9 m6 @% I- _ return (ERROR);
* O: o# x! g: H/ e) r6 | }
) ^& H& s% t7 r+ ]& ` 6 d ^. v) v) [' x5 z! ~& ~& N; l' |
nWords = pHdr->nWords;) I$ y, m. G/ X1 v8 P6 L( m1 L
if(PREV_HDR(pHdr)->free)
3 ^3 h1 P& q( G/ l6 B# P {/* the prev hdr is free and than coalesce with it */
" T ]2 O8 ^3 v2 C- b pHdr->free = FALSE;
* d7 g* U) O1 g4 m! G. s# S6 L pHdr = PREV_HDR(pHdr);* k3 b: U+ J: L3 j4 U
pHdr->nWords += nWords;
% l5 n/ H$ J# I0 J }
# T4 P8 @& g0 _& F- x else
5 ?4 p2 N5 {% B, o; h4 Z( d3 O& s5 { {0 p; B5 s$ W* H7 r8 I
pHdr->free = TRUE;& U. D0 k A% m! J1 i0 T$ c1 k
dllInsert(&partId->freeList, (DL_NODE*)NULL, HDR_TO_NODE(pHdr));
3 A- o- p' _3 @. ~' O7 R5 \" w }# [* B0 \8 {! h7 a6 {- U/ M
3 W Y* ]$ X6 s9 k /* check to coalesce with the next */( U; c, G+ S' h. H5 g% c5 X# b6 A0 q
pNextHdr = NEXT_HDR(pHdr);
( D- ^4 R# ]. K) b4 ]% j( h( W if(pNextHdr->free)
" [) I7 e5 ^9 B* b: p {* v6 I% H, ]5 O' b6 u& j- e& A
pHdr->nWords += pNextHdr->nWords;
$ g0 D* @& v/ G( ]( i dllRemove(&partId->freeList, HDR_TO_NODE(pNextHdr));0 b3 ?% k# o- L( F- Z* r
}
% z! W9 V" l; x' l0 g8 V6 u , ^7 O( I5 V2 o# j. F
/* cannot use pNextHdr->prevHdr=pHdr hear */# O. A6 A7 [" i" r4 C: H2 t
NEXT_HDR(pHdr)->prevHdr = pHdr;
# o9 _- E- V" q 4 F8 A% W8 r# j+ y
partId->curBlocksAlloc--;
- o/ W k' \* K' G- Q0 ~" p partId->curWordsAlloc -= nWords;5 y7 a; ^" w2 {7 U4 b
# z6 M. ?* W( }- b* z /* TODO give sem hear */
5 ]5 J y6 @1 F; g! T semGive(partId->semPartId);; K4 @# i+ ~2 T( L: V1 g) `8 h
/ d% o. B4 c5 B6 X+ @' F
return (OK);. M0 W H* f1 r: A
}
! ^$ v! _) v8 i1 g( \
6 { k% q2 Y) t, B0 x! W* D static BOOL memPartBlockIsValid(PART_ID partId, FAST BLOCK_HDR* pHdr, BOOL isFree)* y! U$ g4 n, i; a, r, B0 I+ O
{7 e! c! L) n- {$ U8 u, |
BOOL valid;6 a3 l2 w, _4 W& w
`1 k: f1 U$ T' V7 D2 x/ A) ~
TASK_LOCK();
# d) n3 H4 x$ S# O$ o- ` semGive(partId->semPartId);8 N( n: K% P, I1 o
: W0 {0 L$ d1 I3 }: \. y1 @9 z
valid = MEM_ALIGNED(pHdr)
" M' \; _2 _! w) m2 [4 L" ?7 N4 X) i && MEM_ALIGNED(pHdr->nWords*2)
7 X( Q! H4 X! f && (pHdr->nWords < partId->totalWords)
( Y& f- |) K. W8 t && (pHdr->free == isFree)3 l& L. m* \3 Y4 Y( b
&& (pHdr == PREV_HDR(NEXT_HDR(pHdr)))% i& w) }( ?( a
&& (pHdr == NEXT_HDR(PREV_HDR(pHdr)));
5 `5 `/ e' f( B& {4 h + U0 Q% C4 |2 Q, c+ n" g
semTake(partId->semPartId, WAIT_FOREVER);
+ X& x5 L5 w3 i# b TASK_UNLOCK();" U9 f% i- ^- V4 W
3 g* ~$ }' Y: N) ]+ M. B0 U
return valid;
0 S: E/ h" a; o+ }. {# k }
) [: L5 h# z- D" d 7 c7 L! j. K3 b) M! r7 ^ @
static BLOCK_HDR* memAlignedBlockSplit(PART_ID partId) a5 B. ], c8 K0 a. }0 }6 M* D
, FAST BLOCK_HDR* pHdr& k+ W x ^. r
, FAST unsigned nWords
: d0 J8 Q9 Z( R/ O3 c8 ~* j5 T , unsigned minWords
0 i3 L+ u; Y/ e , unsigned align)
8 u" X9 H# d+ f# K# x {- r: O3 r, g$ w8 h6 n4 L P. v
FAST BLOCK_HDR *pNewHdr;% P. V& F) d4 n. X- x
FAST BLOCK_HDR *pNextHdr;5 m0 g( S, e# @" q% t4 m# p
FAST char *endOfBlock;
- ~; x# ?! r& h% j! Z" b FAST char *pNewBlock;
, |8 u( |5 s6 R) ^& ~3 t int blockSize;
# S: Y; _, x3 @) T) [8 D% ]/ d- `
/ W. b0 j+ s/ S* A6 w4 H endOfBlock = (char*)pHdr + (pHdr->nWords*2);' T5 [- E) F5 F# H3 T9 h. r6 o0 o
" s5 b4 l! |* [$ \6 z1 C7 }% n pNewBlock = (char*)((unsigned)endOfBlock - ((nWords - sizeof(BLOCK_HDR)/2)*2));
- [ {0 `, \5 [( X4 |/ M
' k% m. h3 E' b! y) { P pNewBlock = (char*)((unsigned)pNewBlock & (~(align-1)));7 V( S, t9 F# ~0 b: y! D0 r
$ S- `% V# j. D( t, e7 Q, h& S pNewHdr = BLOCK_TO_HDR(pNewBlock);
2 C- B" {' G H' B/ l6 m4 i $ i" I. D3 _2 n" p1 u0 D
blockSize = ((char*)pNewHdr - (char*)pHdr)/2;1 i* R* K; X6 Z! p& Z* H
! V0 g& y+ P0 |) v% M B if(blockSize < minWords)
/ F" r- I' J' U' Z- U8 c {' d1 \% ^0 z0 _ @
if(pNewHdr == pHdr)6 V+ e8 }7 n* u3 q! r; P
{0 O2 Q9 O. j- n, F7 P3 h8 r: A
dllRemove(&partId->freeList, HDR_TO_NODE(pHdr));' t4 E6 h$ D. P9 n1 L
} \, O* w8 K: ~4 `: m
else
# U" e( y0 N. n% U7 Y {) _( E. U: x+ r9 t
return NULL;
. Y% H) I( |9 C( ^& r5 y$ h1 z }
% x) i2 }2 \0 R+ h }0 \7 q! u# L! t/ }* n
else m1 G; k5 r) O! q5 G% b
{ /* recaculate pHdr */1 v$ O7 _6 J( d5 R9 s o9 H
pNewHdr->prevHdr = pHdr; E( V/ o- ^5 v3 C2 A! d3 s* o
pHdr->nWords = blockSize;
+ ^9 ?! M+ J- L' v+ z! j }1 d& N2 m6 |- V; Z$ s$ B6 f! {
) Q' i+ }; E9 F( g. ^: j! \
if(((U32)endOfBlock - (U32)pNewHdr - (nWords*2)) < (minWords*2))' G$ {0 ]% |8 h0 l" i
{
+ G! c+ v( l' ` R5 L pNewHdr->nWords = (endOfBlock - pNewBlock + sizeof(BLOCK_HDR))/2;: c9 O8 C' h" E% G5 |
pNewHdr->free = TRUE;
# c( c- K1 o2 f( Z4 T * }6 y/ t w( M3 C9 K4 _0 L- D7 h
NEXT_HDR(pNewHdr)->prevHdr = pNewHdr;- w( | n- _; n# O
}& N0 i. \7 L- b; d5 q
else
& R1 Z, ^5 w6 s0 ^( b {/* space left is enough to be a fragment on the free list then */# L' ?) y2 W* e5 S
pNewHdr->nWords = nWords;; @' g9 J+ D" l/ b' u$ S1 f) X
pNewHdr->free = TRUE;7 w8 I* Q* `. h% _" W6 A
. Z, k6 D0 Y/ O, l0 R pNextHdr = NEXT_HDR(pNewHdr);8 I+ T9 Q; q0 @6 S
/* words 包括BlockHdr */ D3 U: h! d. W& K9 W
pNextHdr->nWords = ((U32)endOfBlock - (U32)pNextHdr) / 2;$ j+ o! Z/ \- }4 n1 j- j3 a9 _9 {+ A
pNextHdr->prevHdr = pNewHdr;
5 M. L8 v* D3 | M$ N pNextHdr->free = TRUE;
7 Q/ t+ J. z% F! Q
, h8 M1 L' t6 v, ` `/ k dllAdd(&partId->freeList, HDR_TO_NODE(pNextHdr));7 `' A8 z6 e3 Y6 f
9 S' i- U6 B2 k i1 t7 `( x$ k! W
NEXT_HDR(pNextHdr)->prevHdr = pNewHdr;' c5 @! W5 q+ l: ?2 ?
}
8 \, f' \8 G: {2 y, L+ ` * O9 e t7 F- M% J& [
return (pNewHdr);
, _& F* K$ S6 T- p7 N$ S) d }) g) S$ l9 E: y q
% b$ y8 }. R0 b1 D! T
static void memPartSemInit(PART_ID partId); n1 N; `% H8 ?2 R2 _$ g
{5 ?7 U D) _; C0 k6 @
semBInit(&semMemSysPartition, SEM_Q_FIFO, SEM_FULL);
1 U5 l S# \6 N- [
. z: \0 }2 \+ V8 t partId->semPartId = &semMemSysPartition;
& h; @; R% ]0 H }
7 [, w& i- i, q7 w1 W8 r 6 U( X) j# g4 \1 h, ?
void* malloc(unsigned bytes)
B! K8 U- r9 _& ]0 }4 U. |4 X: i8 T {
7 T% |. B5 b3 L0 v& J( r return memPartAlloc(memSysPartId, bytes);
& ~/ X! ~% E" Y* G1 D/ m& T }- W( W5 g5 C& _4 x9 }9 g0 g
. `+ p" W" I3 G; c2 h" h
void free(void* p)
* D3 G6 w' a4 s. b7 \ {7 L; c) Z) Z1 Y. e
memPartFree(memSysPartId, (char*)p);, f( D0 w9 q5 G. n
}
L6 C' y) ?3 W. u, F. I
zan