B

Podprogramy zarządzania pamięcią

Kod zamieszczony w niniejszym dodatku stanowi implementację prostego systemu rejestrującego operacje związane z dynamicznym zarządzaniem pamięcią — przydział, zwalnianie i realokację bloków oraz kontrolę odwołań do nich. System zrealizowany został na podstawie jednokierunko­wej listy łączonej, której każdy element reprezentuje jeden dynamicznie przydzielony blok wraz z jego podstawowymi atrybutami — adresem początku i rozmiarem. Poszczególne elementy tworzone są za pomocą funkcji malloc i dla prostoty wstawiane na początku listy — kolejność poszczególnych bloków w liście nie jest bowiem istotna.

Być może implementacja ta nie jest specjalnie efektywna — bardziej zaawansowana struktura z rodzaju B-drzewa, czy drzewa AVL z pewnością byłaby tu bardziej odpowiednia — jednak podstawowym celem niniejszego dodatku jest przedstawienie podstawowych koncepcji zarządzania pamięcią i efektywność nie jest tu czynnikiem decydującym.

block.h

#ifdef DEBUG

/* ------------------------------------------------------

* blockinfo jest strukturą zawierającą informację o przydzielonym

* bloku pamięci. Każdy przydzielony blok posiada swą reprezentację

* w postaci bloku blockinfo w kronice przydziału pamięci

*/

typedef struct BLOCKINFO

{

struct BLOCKINFO *pbiNext;

byte *pb; /* początek bloku */

size_t size; /* rozmiar bloku */

flag fReferenced /* było odwołanie do bloku? */

} blockinfo;

flag fCreateBlockInfo(byte *pbNew, size_t sizeNew);

void FreeBlockInfo(byte *pbToTree);

void UpdateBlockInfo(byte *pbOld, byte *pbNew, size_t sizeNew);

size_t sizeofBlock(byte *pb);

void ClearMemoryRefs(void);

void NoteMemoryRef(void *pv);

void CheckMemoryRefs(void);

flag fValidPointer(void *pv, size_t size);

#endif

block.c

#ifdef DEBUG

/* Funkcje zawarte w niniejszym pliku dokonują porównywania

* dowolnych wskaźników. Norma ANSI nie zapewnia przenośności

* takiego kodu.

*

* Poniższe makra izolują samo porównywanie wskaźników.

* Zakłada się "płaski" model adresowania pamięci, w stosunku

* do którego daje się zastosować zwykłe porównywanie liczbowe —

* poniższe definicje są więc nieadekwatne do modelu "segment:offset"

* charakterystycznego dla komputerów 80x86.

*/

#define fPtrLess (pLeft, pRight) ((pLeft) < (pRight))

#define fPtrGrtr (pLeft, pRight) ((pLeft) > (pRight))

#define fPtrEqual (pLeft, pRight) ((pLeft) == (pRight))

#define fPtrLessEq (pLeft, pRight) ((pLeft) <= (pRight))

#define fPtrGrtrEq (pLeft, pRight) ((pLeft) >= (pRight))

/*------------------------------------------------------*/

/* *** prywatne dane i funkcje *** */

/*------------------------------------------------------*/

/*------------------------------------------------------

* pbiHead wskazuje na jednokierunkową listę wiązaną

* zawierającą informacje diagnostyczne dla menedżera

* pamięci

*/

static blockinfo *pbiHead = NULL;

/*-----------------------------------------------------

* pbigetBlockInfo(pb)

*

* pbigetBlockInfo przeszukuje kronikę pamięci w celu znalezienia

* bloku wskazywanego przez pb oraz związanej z nim struktury

* blockinfo w kronice pamięci.

*

* uwaga:

* pb MUSI wskazywać na przydzielony blok, w przeciwnym razie

* nie zostanie spełniona asercja. Niniejsza funkcja kończy się

* sukcesem albo załamuje na skutek niespełnionej asercji, nigdy

* nie zwracając informacji o błędzie.

*

*

* blockinfo *pb;

* …

* pbi = pbiGetBlockInfo(pb);

* //pbi->pb wskazuje na początek bloku

* //pbi->size jest rozmiarem bloku

*/

static blockinfo *pbigetBlockInfo(byte *pb)

{

blockinfo *pbi;

for (pbi = pbiHead; pbi != NULL; pbi = pbi->pbiNext)

{

byte *pbStart = pbi->pb;

byte *pbEnd = pbi->pb + pbi->size - 1;

if (fPtrGtrEq(pb, pbStart) && fPtrLessEq(pb, pbEnd))

break;

}

/* Niemożliwe znalezienie bloku */

ASSERT(pbi != NULL);

return (pbi);

}

/*------------------------------------------------------*/

/* *** funkcje publiczne *** */

/*------------------------------------------------------*/

/* fcreateBlockinfo(pbNew, sizeNew)

*

* Niniejsza funkcja tworzy element kroniki związany z blokiem pbNew.

* Funkcja zwraca TRUE jeżeli operacja się powiedzie i FALSE

* w przeciwnym razie

*

*

* if (fCreateBlockInfo(pbNew, sizeNew))

* // udało się, utworzono pozycję kroniki

* else

* // błąd - nie utworzono pozycji, zwolnij pbNew

*

*/

flag fCreateBlockInfo(byte *pbNew, size_t sizeNew)

{

blockinfo *pbi;

ASSERT(pbNew != NULL && sizeNew != 0);

pbi = (blockinfo *)malloc(sizeof(blockinfo));

if (pbi != NULL)

{

pbi->pb = pbNew;

pbi->size = sizeNew;

pbi->pbiNext = pbiHead;

pbiHead = pbi;

}

return (flag)(pbi != NULL);

}

/*--------------------------------------------------------

/* FreeBlockInfo(pbToFree)

* Niniejsza funkcja zwalnia pozycję kroniki związaną z blokiem

* wskazywanym przez pbToFree. pbToFree MUSI wskazywać na

* przydzielony blok, w przeciwnym razie nie zostanie spełniona

* asercja.

*/

void FreeBlockInfo(byte *pbToFree);

{

blockinfo *pbi, *pbiPrev;

pbiPrev = NULL;

for (pbi = pbiHead; pbi != NULL; pbi = pbi->pbiNext);

{

if (fPtrEqual(pbi->pb, pbToFree))

{

if (pbjPrev == NULL)

pbiHead = pbi->pbiNext;

else

pbiPrev->pbiNext = pbi->pbiNext;

break;

}

pbiPrev = pbi;

}

/* jeśli pbi = NULL, pbToFree nie wskazuje na poprawny blok */

ASSERT(pbi != NULL);

memset(pbi, bGarbage, sizeof(blockinfo));

free(pbi);

}

/* UpdateBlockInfo(pbOld, pbNew, sizeNew);

* Niniejsza funkcja poszukuje w kronice bloku identyfikowanego przez

* pbOld i uaktualnia informację o bloku, który teraz znajduje się

* pod adresem pbNew i ma rozmiar sizeNew. pbOld MUSI wskazywać na

* przydzielony blok, w przeciwnym razie nie zostanie spełniona

* asercja.

*/

void UpdateBlockInfo(byte *pbOld, byte *pbNew, size_t sizeNew)

{

blockinfo *pbi;

ASSERT(pbNew != NULL && sizeNew != 0);

pbi = pbiGetBlockInfo(pbOld);

ASSERT(pbOld == pbi->pb);

pbi->pb = pbNew;

pbi->size = sizeNew;

}

/*--------------------------------------------------------

/* sizeOfBlock(pb)

*

* sizeofBlock zwraca rozmiar bloku wskazywanego przez pb.

* pb MUSI wskazywać na przydzielony blok, w przeciwnym razie nie

* zostanie spełniona asercja.

*/

size_t sizeofBlock(byte *pb)

{

blockinfo *pbi;

pbi = pbiGetBlockInfo(pb);

ASSERT(pb == pbi->pb);

return (pbi->size);

}

/* ----------------------------------------------------------*/

/* Poniższe funkcje używane są do odnalezienia "wiszących" */

/* wskaźników i zagubionych bloków pamięci. Dyskusja nad ich */

/* treścią znajduje się w rozdziale 3. */

/* ----------------------------------------------------------*/

/* ----------------------------------------------------------

* ClearMemoryRefs(void)

*

* ClearMemoryRefs resetuje wskaźniki odwołania dla każdego

* bloku notowanego w kronice

*

*/

void ClearMemoryRefs(void)

{

blockinfo *pbi;

for (pbi = pbiHead; pbi != NULL; pbi = pbi->pbiNext);

pbi->fReferenced = FALSE

}

/* ----------------------------------------------------------

* NoteMemoryRef(pv)

*

* NoteMemoryRef rejestruje odwołanie do bloku zawierającego

* adres pv. pv nie musi wskazywać na początek bloku, może wskazywać

* na którykolwiek jego bajt

*

*/

void NoteMemoryRef(void *pv)

{

blockinfo *pbi;

pbi= pbiGetBlockInfo((byte *)pv);

pbi->fReferenced = TRUE;

}

/* ----------------------------------------------------------

* CheckMemoryRefs(void)

* Niniejsza funkcja przegląda kronikę w celu znalezienia bloków,

* do których nie nastąpiły jeszcze odwołania. W przypadku

* znalezienia bloku funkcja sygnalizuje ten fakt za pomocą

* stosownej asercji

*/

void CheckMemoryRefs(void)

{

blockinfo *pbi;

for (pbi = pbiHead; pbi != NULL; pbi = pbi->pbiNext)

{

/* prosty test na poprawność wskazywanego bloku */

ASSERT(pbi->pb != NULL && pbi->size != 0);

/* brak rejestracji odwołania do bloku pbi

* oznacza wyciek pamięci

*/

ASSERT(pbi->fReferenced);

}

}

/* ----------------------------------------------------------

* fValidPointer(pv, size)

* Niniejsza funkcja dokonuje sprawdzenia, czy wskaźnik pv wskazuje

* na przydzielony obszar pamięci i czy pomiędzy pv a końcem bloku

* znajduje się co najmniej "size" bajtów. Niespełnienie któregoś

* z tych warunków powoduje niespełnienie asercji — funkcja nigdy nie

* zwraca wartości FALSE.

*

* Powodem, dla którego funkcja zawsze zwraca wartość TRUE, jest

* możliwość wywoływania jej wewnątrz makra ASSERT.

*/

flag fValidPointer(void *pv, size_t size)

{

blockinfo *pbi;

byte *pb = (byte *)pv;

ASSERT(pv != NULL && size != 0)

pbi = pbiGetBlockInfo(pb);

ASSERT(fPtrLessEq(pb + size, pbi->pb + pbi->size);

return (TRUE);

}

#endif

194 Niezawodność oprogramowania

Podprogramy zarządzania pamięcią 193

194 D:\Roboczy\Niezawodność oprogramowania\9 po skladzie 1\rdodB.doc

D:\Roboczy\Niezawodność oprogramowania\9 po skladzie 1\rdodB.doc 193

---