Podprogramy zarządzania pamięcią 193
B
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 jednokierunkowej 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
/* 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)
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;
pbiPrev = pbi;
/* jeśli pbi = NULL, pbToFree nie wskazuje na poprawny blok */
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
void UpdateBlockInfo(byte *pbOld, byte *pbNew, size_t sizeNew)
pbi = pbiGetBlockInfo(pbOld);
ASSERT(pbOld == pbi->pb);
/* 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)
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)
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)
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)
/* 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)
byte *pb = (byte *)pv;
ASSERT(pv != NULL && size != 0)
ASSERT(fPtrLessEq(pb + size, pbi->pb + pbi->size);
return (TRUE);
D:\Roboczy\Niezawodność oprogramowania\9 po skladzie 1\rdodB.doc 193
Yoostynka