Хрестоматия по программированию на Си в Unix
struct _cell *next;
} Cell;
typedef struct _entry {
int length;
int used;
Cell *list;
} Entry;
/* Хэшированная таблица */
#define NENTRIES 64
Entry aTab[NENTRIES];
/* Хэш-функция от адреса */
int aHash(void *addr){
unsigned long x = (unsigned long) addr;
x >>= 3; /* деление на 8, так как адреса из malloc()
обычно четные,
поскольку выровнены на границу double */
return(x % NENTRIES);
/* Тут к месту напомнить, что вычисление остатка от деления на степень двойки
* можно соптимизировать:
* x % (2**N) = x & 0b0001.....1 (N двоичных единиц)
* К примеру, x % 64 = x & 0x3F; (6-ая степень двойки)
*/
}
/* Выделить память, записать адрес в таблицу */
void *aCalloc(int n, int m){
void *ptr = calloc(n, m);
Entry *ep = &aTab[ aHash(ptr) ];
Cell *p;
for(p=ep->list; p; p=p->next)
if(p->addr == NULL){
/* Свободная ячейка: переиспользовать */
p->addr = ptr;
ep->used++;
return ptr;
}
/* Нет свободных, завести новую */
p = (Cell *) calloc(1, sizeof(Cell));
p->addr = ptr;
p->next = ep->list;
ep->list = p;
ep->length++;
ep->used++;
return ptr;
}
/* Освободить память */
int aFree(void *ptr){
Entry *ep = &aTab[ aHash(ptr) ];
Cell *p;
for(p=ep->list; p; p=p->next)
if(p->addr == ptr){
free(ptr);
p->addr = NULL;
/* Ячейка не удаляется, но метится как свободная */
ep->used--;
return 1;
}
/* Нет, такой указатель не отводился.
* Не делать free()
*/
return 0;
}
/* Выдать статистику об использовании хэша */
void aStat(){
int i;
int len_all;
int used_all;
for(i=len_all=used_all=0; i < NENTRIES; i++){
len_all += aTab[i].length;
used_all += aTab[i].used;
printf("%d/%d%s", aTab[i].used, aTab[i].length,
i==NENTRIES-1 ? "\n":" ");
}
printf("%d/%d=%g%%\n",
used_all, len_all,
(double)used_all * 100 / len_all);
}
/* ТЕСТ =================================================================*/
Cell *text;
/* Прочитать файл в память */
void fileIn(char *name){
char buf[10000];
FILE *fp;
if((fp = fopen(name, "r")) == NULL){
printf("Cannot read %s\n", name);
return;
}
while(fgets(buf, sizeof buf, fp) != NULL){
char *s;
Cell *p;
s = (char *) aCalloc(1, strlen(buf)+1);
strcpy(s, buf);
p = (Cell *) aCalloc(sizeof(Cell), 1);
p->addr = s;
p->next = text;
text = p;
}
fclose(fp);
}
/* Уничтожить текст в памяти */
void killAll(){
Cell *ptr, *nxtp;
ptr = text;
while(ptr){
nxtp = ptr->next;
if(!aFree(ptr->addr)) printf("No free(1)\n");
if(!aFree(ptr)) printf("No free(2)\n");
ptr = nxtp;
}
}
/* Удалить из текста строки, начинающиеся с определенной буквы */
void randomKill(int *deleted){
unsigned char c = rand() % 256;
Cell *ptr, *prevp;
unsigned char *s;
retry:
prevp = NULL; ptr = text;
while(ptr){
s = (unsigned char *) ptr->addr;
if(*s == c){ /* нашел */
if(!aFree(s)) printf("No free(3)\n");
/* исключить из списка */
if(prevp) prevp->next = ptr->next;
else text = ptr->next;
if(!aFree(ptr)) printf("No free(4)\n");
/* Заведомо неправильный free
if(!aFree(ptr+1)) printf("No free(5)\n");
*/
(*deleted)++;
goto retry;
}
prevp = ptr;
ptr = ptr->next;
}
}
int main(int ac, char *av[]){
int i, r, d;
char buffer[4098];
srand(time(NULL));
for(i=1; i < ac; i++){
printf("File: %s\n", av[i]);
fileIn(av[i]);
aStat();
d = 0;
for(r=0; r < 128; r++) randomKill(&d);
printf("%d lines deleted\n", d);
aStat();
}
killAll();
aStat();
if(!aFree(buffer))
printf("buffer[] - не динамическая переменная.\n");
return 0;
}
/* Пример 11 */
/* Пакет для ловли наездов областей выделенной памяти
* друг на друга,
* а также просто повреждений динамически отведенной памяти.
*/
#include
#include
#include /* O_RDWR */
#include
#include
#include
#define CHECKALL
/*
----------------- <--------- ptr
| red_zone | головная "пограничная зона"
-----------------
| byte[0] |
| ... |
| byte[size-1] |
| placeholder |
----------------- выровнено на границу RedZoneType
| red_zone | хвостовая "пограничная зона"
-----------------
Основные идеи состоят в следующем:
1) Перед и после области данных строится зона,
заполненная заранее известным "узором".
Если ее содержимое изменилось, испорчено -
значит мы где-то разрушили нашу память.
2) Ведется таблица всех отведенных malloc()-ом сегментов памяти;
для экономии места эта таблица вынесена в файл (но зато это
очень медленно).
3) Мы не можем пользоваться библиотекой STDIO для обменов с файлом,
потому что эта библиотека сама использует malloc() и буфера
могут быть разрушены.
*/
typedef char *RedZoneType; /* выравнивание на границу указателя */
/* Можно выравнивать на границу double:
typedef double RedZoneType;
*/
/* Сегмент, выделяемый в оперативной памяти */
typedef struct _allocFrame {
RedZoneType red_zone; /* головная "пограничная зона" */
RedZoneType stuff[1]; /* место для данных */
/* хвостовая "пограничная зона" безымянна */
} AllocFrame;
const int RedZoneTypeSize = sizeof(RedZoneType);
/* Запись, помещаемая в таблицу всех выделенных malloc()ом
* областей памяти.
*/
typedef struct _memFileRecord {
AllocFrame *ptr; /* адрес */
size_t size, adjsize; /* размер выделенной области */
/* (0,0) - означает "сегмент освобожден" */
int serial;
} MemFileRecord;
char red_table[] = {
0x01, 0x03, 0x02, 0x04,
0x11, 0x13, 0x12, 0x14,
0x21, 0x23, 0x22, 0x24,
0x31, 0x33, 0x32, 0x34
};
char free_table[] = {
'F', 'r', 'e', 'e', 'p', 't', 'r', '\0',
'F', 'r', 'e', 'e', 'p', 't', 'r', '\0'
};
/* Файл для хранения таблицы указателей */
static int mem_fd = (-1);
#define PTABLE "PointerTable.bin"
#define NRECORDS 256
MemFileRecord memrecords[NRECORDS];
/* ============================================================= */
void MEMputTableRecord(AllocFrame *newptr, AllocFrame *oldptr,
size_t size, size_t adjsize);
void MEMputTableRecordKilled(AllocFrame *ptr);
void MEMerasePreviousRecords(AllocFrame *ptr);
int MEMcheckRecord(MemFileRecord *rec);
int MEMcheck_consistency(AllocFrame *ptr);
void MEMmakeRedZones(char *cptr, size_t size, size_t adjsize);
void MEMopenFd();
/* ============================================================= */
/* Этим следует пользоваться вместо стандартных функций */
void *MEMmalloc (size_t size);
void *MEMrealloc(void *ptr, size_t size);
void *MEMcalloc (size_t n, size_t size);
void MEMfree (void *ptr);
void MEMcheckAll(); /* это можно вызывать в середине программы */
/* ============================================================= */
void MEMopenFd(){
if(mem_fd < 0){
close(creat(PTABLE, 0644)); /* создать файл */
mem_fd = open(PTABLE, O_RDWR); /* чтение+запись */
unlink(PTABLE); /* только для M_UNIX */
atexit(MEMcheckAll);
setlocale(LC_ALL, "");
}
}
/* Поместить запись в таблицу всех указателей на
* выделенные области памяти.
*/
void MEMputTableRecord(AllocFrame *newptr, /* для записи */
AllocFrame *oldptr, /* для стирания */
size_t size, /* размер данных */
size_t adjsize /* размер всей записи с зонами */
){
MemFileRecord memrecord;
static int serial = 0;
memrecord.ptr = newptr;
memrecord.size = size;
memrecord.adjsize = adjsize;
memrecord.serial = serial++;
MEMopenFd();
#ifdef CHECKALL
/* стереть прежние записи про этот адрес */
MEMerasePreviousRecords(oldptr);
#endif
lseek(mem_fd, 0L, SEEK_END); /* в конец */
write(mem_fd, &memrecord, sizeof memrecord); /* добавить */
}
/* Сделать запись об уничтожении области памяти */
void MEMputTableRecordKilled(AllocFrame *ptr){
/* Пометить как size=0, adjsize=0 */
MEMputTableRecord(ptr, ptr, 0, 0);
}
/* Коды ответа функции проверки */
#define OK 0 /* все хорошо */
#define DAMAGED 1 /* повреждена "погранзона" */
#define FREED 2 /* эта память уже освобождена */
#define NOTHERE (-1) /* нет в таблице */
/* Проверить сохранность "пограничных зон" */
int MEMcheckRecord(MemFileRecord *rec){
int code = OK;
char *cptr;
register i;
AllocFrame *ptr = rec->ptr;
size_t size = rec->size;
size_t adjsize = rec->adjsize;
if(size == 0 && adjsize == 0){
printf("%p [%p] -- сегмент уже освобожден, "
"record=#%d.\n",
&ptr->stuff[0], ptr,
rec->serial
);
return FREED;
}
cptr = (char *) ptr;
for(i=0; i < adjsize; i++){
if(i < RedZoneTypeSize || i >= RedZoneTypeSize + size ){
/* головная погранзона ИЛИ хвостовая погранзона */
if( cptr[i] != red_table[ i % RedZoneTypeSize ] ){
printf("%p [%p] -- испорчен байт %4d [%4d]"
"= 0x%02X '%c' record=#%d size=%lu.\n",
&ptr->stuff[0], ptr,
i - RedZoneTypeSize, i,
cptr[i] & 0xFF,
isprint(cptr[i] & 0xFF) ? cptr[i] & 0xFF : '?',
rec->serial, size
);
code = DAMAGED;
}
}
}
for(i=0; i < RedZoneTypeSize; i++)
if(cptr[i] == free_table[i]){
printf("%p -- уже освобождено?\n", ptr);
code = FREED;
}
if(code != OK) putchar('\n');
return code;
}
/* Проверить сохранность памяти по указателю ptr. */
