/**
* @file mlc_smp7.c
* @brief ヒープ領域固定の malloc,free 例.
* @author tenk@6809.net
* @note
* mlc_smp6.c に対して、アドレスの取得を高いアドレスになるようにする
*/
#include <string.h>
#include <assert.h>
/// ヘッダ＆メモリ取得の基本単位. // sizeof(double)の倍数かつ2のn乗のこと
#define UNIT_SZ 64
#define HDR_SZ 12
#define HDR_UNITS ((HDR_SZ+UNIT_SZ-1)/UNIT_SZ)
/// デバッグチェック用のヘッダid
#define ID_MLC 0xfdb9
#define ID_FRE 0x7531
/// 管理ヘッダ. HDR_SZ = sizeof(Header) のこと
typedef union Header {
struct {
union Header *ptr; // 次のブロックへのポインタ
unsigned size; // サイズ(sizeof(Header)単位の個数)
unsigned id; // チェック用のid
} s;
} Header;
/// 空きブロックの管理用
static Header *base; // 最下位アドレスの空きブロックを指す
// メモリの管理チェック用
static char *heap_top;
static char *heap_end;
/// mallocポインタから(Header*)を取得
#define MP2HDRP(mp) ((Header*)((char *)mp - HDR_SZ))
/// ヘッダアドレスからmallocポインタを算出
#define HDRP2MP(hp) ((void*)((char *)hp + HDR_SZ))
/// Header* を UNIT_SZ単位の sz で更新。
#define HP_ADD_SZ(p, sz) ((Header*)((char*)(p) + (sz) * UNIT_SZ))
/// pが ヘッダとして矛盾しないかチェック
static inline void CHECK_HDR_PTR(Header *p, int chkId) {
void *mp = HDRP2MP(p);
assert(heap_top <= (char *)p && (char *)mp <= heap_end);
if (p != base) {
assert(((int)mp & (UNIT_SZ-1)) == 0);
assert(p->s.size > 0 && (char*)HP_ADD_SZ(p, p->s.size) <= heap_end);
}
assert(p->s.ptr == 0 || p <= p->s.ptr || HP_ADD_SZ(p->s.ptr, p->s.ptr->s.size) <= p);
assert(p->s.id == chkId);
}
/// アドレスmemからmemSzバイトをmallocで使うヒープ・メモリとして初期化.
void MallocInit(void *mem, unsigned memSz)
{
Header *freep;
assert(mem != NULL && memSz >= 4*UNIT_SZ);
// デバッグ向けに適当な奇数の値で埋めとく。ただし0や0xffだと、それに
memset(mem, 0x55, memSz); // 依存したバグが出来易いので避ける:-)
// UNIT_SZ単位にアライメントしたアドレスから HDR_SZ をひいたアドレスを先頭とする
base = (Header*)((((unsigned long)mem + 2*HDR_SZ + UNIT_SZ-1) & ~(UNIT_SZ-1)) - 2*HDR_SZ);
base->s.ptr = (Header*)((char*)base + HDR_SZ);
base->s.size = 0;
base->s.id = ID_FRE; // チェック用のidを設定
freep = base->s.ptr;
freep->s.ptr = base;
// アドレス調整を考慮してサイズを求める. サイズは UNIT_SZ 単位の個数。
freep->s.size = ((char*)mem + memSz - (char*)freep) / UNIT_SZ;
freep->s.id = ID_FRE; // チェック用のidを設定
heap_top = (char *)base;
heap_end = (char *)HP_ADD_SZ(freep, freep->s.size);
}
/// nbytesのメモリをヒープから確保
void *Malloc(unsigned nbytes)
{
// ヘッダ部を含めた必要メモリのサイズ(UNIT_SZ単位)を求める
unsigned nunits = (nbytes + HDR_SZ + UNIT_SZ-1) / UNIT_SZ;
Header *prevp = base;
Header *p;
assert(base);
// 空きブロック一覧を順繰りにナめる。
for (p = prevp->s.ptr; ;prevp = p, p = p->s.ptr) {
//CHECK_HDR_PTR(p, ID_FRE);
if (p->s.size >= nunits) // 要求サイズを満たすブロックがあった
break;
if (p == base) // 空き一覧の先頭に戻ったのなら
return NULL; // 空きが無かった
}
CHECK_HDR_PTR(p, ID_FRE);
// 空きが見つかったときの処理
if (p->s.size < nunits+HDR_UNITS) { // 見つかったブロックが調度のとき
prevp->s.ptr = p->s.ptr; // 空き一覧リンクはら外す
} else {
p->s.size -= nunits; // そのブロックの後半から必要ブロック
p = HP_ADD_SZ(p,p->s.size); // を切り出す。
p->s.size = nunits; //
}
p->s.id = ID_MLC; // チェック用のidを設定
p->s.ptr = NULL; // 使わないリンクはとりあえずNULL化
CHECK_HDR_PTR(p, ID_MLC);
return HDRP2MP(p); // ヘッダ部を除いたアドレスを返す
}
/// malloc したメモリを開放
void Free(void *ap)
{
// s.ptr は高いアドレスの空きブロックから低いアドレスにむかって繋がっている/繋げる
Header *bp = MP2HDRP(ap);
Header *r = NULL;
Header *q = base; // 最下位アドレス
Header *p = base->s.ptr; // 最上位アドレス
if (ap == NULL)
return;
CHECK_HDR_PTR(bp, ID_MLC);
bp->s.id = ID_FRE;
if (bp < base->s.ptr) { // 最上位アドレスの空きブロックより低い
// ブロックp(要素n)とq(要素n+1)の間に今回の領域が存在しない間ループ
while ((p < bp && bp < q) == 0) {
//CHECK_HDR_PTR(p, ID_FRE);
r = q;
q = p;
p = p->s.ptr;
if (q == base)
break;
}
}
CHECK_HDR_PTR(p, ID_FRE);
if (HP_ADD_SZ(p,p->s.size) == bp) { // 直前の要素と合体できる場合
p->s.size += bp->s.size; // サイズ更新
//q->s.ptr = p;
bp = p;
} else { // 合体できない場合
bp->s.ptr = p; // 繋ぎ替え
}
if (HP_ADD_SZ(bp,bp->s.size) == q) {// 直後の要素と合体できる場合
// ※ bp>base->s.ptrの場合は条件が成立しないのでここに来ない(r=NULLでは来ない)
bp->s.size += q->s.size; // サイズ更新
r->s.ptr = bp; // 繋ぎ替え
} else { // 合体できない場合
q->s.ptr = bp; // qとpの間に連結
}
CHECK_HDR_PTR(bp, ID_FRE);
CHECK_HDR_PTR(p, ID_FRE);
}
/// 配列を想定した引数で、かつ、0クリアされるメモリ確保
void *Calloc(unsigned asz, unsigned num)
{
unsigned sz = asz * num;
void *m = Malloc(sz);
if (m)
memset(m, 0, sz);
return m;
}
/// Header::s.size の値を実際のバイト数に変換 (usz=0は未対応)
#define UNITSZ2BYT(usz) ((usz) * UNIT_SZ - HDR_SZ)
/// mallocされたメモリの領域サイズを返す
unsigned Msize(void *mp)
{
unsigned sz;
Header *p = MP2HDRP(mp);
CHECK_HDR_PTR(p, ID_MLC);
sz = UNITSZ2BYT(p->s.size);
return sz;
}
/// mallocしたメモリのサイズ変更(手抜き版)
void *Realloc(void *s, unsigned dsz)
{
unsigned ssz = Msize(s);
void *d = Malloc(dsz);
if (ssz > dsz)
ssz = dsz;
if (d)
memcpy(d, s, ssz);
Free(s);
return d;
}
/// p が ヘッダとして正常(1)か否(0)か
static inline int IS_HDR_PTR(Header *p, int chkId) {
void *mp = HDRP2MP(p);
if ((char *)p < heap_top) return 0;
if ((char *)mp > heap_end) return 0;
if (p != base) {
if ((int)mp & (UNIT_SZ-1)) return 0;
if (p->s.size == 0 || (char*)HP_ADD_SZ((p), (p)->s.size) > heap_end) return 0;
}
if (p->s.ptr && p > p->s.ptr && HP_ADD_SZ(p->s.ptr, p->s.ptr->s.size) > p) return 0;
if (p->s.id != chkId) return 0;
return 1;
}
/// mpが malloc されたポインタか(1) 否か(0) をチェック
int IsMallocPtr(void *mp)
{
return IS_HDR_PTR(MP2HDRP(mp), ID_MLC);
}
/// mallocできる最大サイズを求める
unsigned MaxSize(void)
{
unsigned sz = 0;
Header *p;
assert(base);
for (p = base->s.ptr; ;p = p->s.ptr) {
CHECK_HDR_PTR(p, ID_FRE);
if (sz < p->s.size)
sz = p->s.size;
if (p == base)
break;
}
return (sz > 0) ? UNITSZ2BYT(sz) : 0;
}
/// 空き領域のサイズを求める
/// @param *maxSize mallocできる最大サイズを返す
/// @param *total 空き領域の合計サイズを返す
/// @param *split 空き領域の分割数を返す
/// @return 空きリストが壊れてる(0)か正常(1)かを返す
int GetEmptySize(int *maxSize, int *total, int *split)
{
unsigned maxSz= 0;
int n = 0;
int sum = 0;
Header *p;
assert(base);
for (p = base->s.ptr; ;p = p->s.ptr) {
if (IS_HDR_PTR(p, ID_FRE) == 0) {
#if 0
#define ERR_PRINTF(x) printf x
Header *q;
int i = 0;
ERR_PRINTF(("Mallocの空管理リストが不正\t"));
for (q = base->s.ptr; IS_HDR_PTR(q, ID_FRE); q = q->s.ptr, i++) {
ERR_PRINTF(("%d:%#x->", i,q));
}
ERR_PRINTF(("%d:%#x\n", n,p));
#endif
return 0;
}
if (maxSz < p->s.size)
maxSz = p->s.size;
sum += UNITSZ2BYT(p->s.size);
n++;
if (p == base)
break;
}
if (maxSize) *maxSize = (maxSz > 0) ? UNITSZ2BYT(maxSz) : 0;
if (total) *total = sum;
if (split) *split = n;
return 1;
}