Первая публикация 13.04.2013
On an implementation of continuity check of heap during memory allocation
Введение
Операторы выделения и освобождения памяти из «кучи» являются широко используемыми языковыми возможностями наряду с присваиваниями, условиями и т.п. В последние десятилетия имеется тенденция к усложнению реализации этих операторов, что связано с попытками исключить в принципе возможность нарушения программистом внутренней структуры «кучи» в результате ошибочных действий при явном выделении и освобождении памяти в программе. В некоторых языках программист уже не может сам явно выделять память, а для ее освобождения от ненужных объектов используется встроенная программа «сборки мусора». Однако платой за такое повышение надежности является снижение эффективности при распределении памяти, усложнение внутренних структур и малая предсказуемость времени отклика в программе из-за нерегулярной работы «сборщика мусора» [1].
Автор статьи в течение многих лет использовал систему программирования на языке PL/1 [2], где реализована наиболее простая и наименее надежная схема управления памятью, почти полностью возлагающая на программиста ответственность за правильность при выделении и освобождении памяти. В реальных проектах, особенно больших, ошибки при управлении памятью возникали и оказывались очень болезненными, поскольку трудно диагностировались. Но с другой стороны, не хотелось из-за этого отказываться от свободного манипулирования памятью в программе, позволяющего удобно и эффективно решать поставленные задачи. Компромисс был найден в добавлении к встроенному в язык аппарату управления памятью несложных средств контроля целостности внутренней структуры «кучи». Такие средства позволили постоянно проверять отсутствие каких-либо нарушений при распределении памяти и в противном случае сообщать об этом сигналом ошибки. В процессе контроля становилась доступной информация, позволяющая определить место нарушения, а поэтому часто и его причину.
Организация «кучи» в рассматриваемой системе программирования
Основой внутренней структуры «кучи», как, вероятно, и во многих других системах программирования, является связанный список, поскольку это наиболее удобная в данном случае организация памяти. Поскольку работа идет в среде Win32, под один адрес в связанном списке выделяется 4 байта. Так как не используется «сборка мусора», достаточно самой минимальной информации внутри «кучи»: адреса очередного блока и признака занят он или свободен.
Однако, поскольку при освобождении памяти принята стратегия автоматического слияния двух подряд идущих свободных блоков, связанный список «кучи» сделан двунаправленным, т.е. в начале каждого блока есть ссылка и на начало предыдущего блока в списке и на начало следующего блока. Такой двойной связанный список позволяет при освобождении памяти работать со смежными блоками без необходимости просмотра всего списка с начала для поиска предыдущего блока. В самом первом блоке ссылка на предыдущий блок устанавливается в ноль и в самом последнем блоке ссылка на следующий блок устанавливается в ноль.
Для признака занятости блока используется младший бит ссылки на предыдущий блок. Предполагается, что сам адрес блока всегда кратен двум, и этот бит не используется для адресации. Таким образом, память можно выделять лишь порциями байт, кратными двум. Это несущественное ограничение, особенно учитывая частое требование выравнивания блока памяти на границу двойного слова. Зато тогда для признака занятости блока не требуется дополнительных байт и все накладные расходы на один блок в «куче» составляют 8 байт: ссылка на предыдущий блок (младший бит – признак занятости) и ссылка на следующий блок.
Такая простая и регулярная структура «кучи» позволяет эффективно реализовать выделение и освобождение памяти, а также облегчает контроль целостности «кучи», например, значения всех ссылок на блоки в списке должны идти в возрастающем порядке.
Исходный текст системной подпрограммы управления памятью
Ниже приведен исходный текст подпрограммы управления и контроля памяти из системной библиотеки для рассматриваемого языка PL/1. Для журнальной статьи этот текст на ассемблере для процессора IA-32 несколько велик. Однако автор не предлагает читателям, даже хорошо знакомым с ассемблером, самими разбираться в этом тексте. Его объяснение имеется далее в статье. Цель приведения текста – показать, что небольшим числом команд (т.е. просто и поэтому эффективно) реализован весь аппарат управления памятью, причем значительная часть – это даже не собственно выделение/освобождение памяти, а вспомогательные средства контроля целостности «кучи».
EXTRN ?SIGC:N
;——————- ОБНУЛЯТЬ ПОСЛЕ КАЖДОГО ALLOCATE ——————
PUBLIC ?ALLOC_ZR:
…….MOV DS:N0001,033H ;ИСПРАВЛЯЕМ RET НА XOR EAX,EAX
…….RET
;—————– НЕ ОБНУЛЯТЬ ПОСЛЕ КАЖДОГО ALLOCATE —————–
PUBLIC ?ALLOC_NZ:
MOV DS:N0001,0C3H ;ИСПРАВЛЯЕМ XOR EAX,EAX НА RET
RET
;——————— ALLOCATE (ВЫДЕЛЕНИЕ ПАМЯТИ) ——————–
PUBLIC ?ALLOP:………………;ВЫЗЫВАЕТСЯ ИЗ ПРОГРАММ PL/1
MOV ECX,OFFSET ?BEGIN ;АДРЕС НАЧАЛА СВЯЗАННОГО СПИСКА
;—- ДОСТАЛИ АДРЕС НАЧАЛА “КУЧИ” PL/1 —-
MOV EAX,[ECX]+0 ;НАЧАЛО СВЯЗАННОГО СПИСКА
MOV ?START_MEM,EAX ;ЭТО И НАЧАЛО БУДУЩЕЙ ПРОВЕРКИ
XOR ESI,ESI
MOV EAX,[ECX]+4 ;ПЕРВЫЙ СВОБОДНЫЙ БЛОК В “КУЧЕ”
;—- ИСХОДНОЕ СОСТОЯНИЕ ПРИ ПРОВЕРКИ ЦЕЛОСТНОСТИ “КУЧИ” —-
MOV ?ОБЪЕМ_МЕМ,ESI ;ПОКА НЕТ ПРОВЕРКИ СУММАРНОГО ОБЪЕМА
;—- ВЫРАВНИВАНИЕ ЗАКАЗАННОГО ЧИСЛА БАЙТ НА СЛОВО —-
INC EBX
AND BL,NOT 1 ;ВЫРОВНИЛИ НА ГРАНИЦУ СЛОВА
;—- ВСТАЕМ НА ПЕРВЫЙ СВОБОДНЫЙ БЛОК “КУЧИ” —-
XCHG EBX,EAX ;НАЧАЛО СПИСКА ПАМЯТИ
;—- ЦИКЛ ПОИСКА ПОДХОДЯЩЕГО СВОБОДНОГО БЛОКА “КУЧИ” —-
M0001:TEST B PTR [EBX],1 ;ЭТОТ БЛОК СВОБОДЕН ?
JZ M0003………………………….;ДА – ПРОВЕРЯЕМ ДЛИНУ
M0002:MOV EBX,[EBX]+4 ;АДРЕС СЛЕДУЮЩЕГО БЛОКА
OR EBX,EBX…………………….;ЕЩЕ ЕСТЬ БЛОКИ ?
JNZ M0001……………………….;ДА – ПРОДОЛЖАЕМ ПОИСК
;—- НЕ НАЙДЕНО ПОДХОДЯЩЕГО БЛОКА —-
MOV AX,0700H…………………;УСТАНАВЛИВАЕМ КОД (7,0)
MOV EDX,OFFSET ОШИБ2 ;”ВСЯ ПАМЯТЬ ИСЧЕРПАНА”
JMPS M0005……………………..;ВЫДАЕМ СИГНАЛ ОШИБКИ
;—- ВЫЧИСЛЕНИЕ ДЛИНЫ СВОБОДНОГО БЛОКА —-
M0003:MOV EDX,[EBX]+4 ;АДРЕС СЛЕДУЮЩЕГО БЛОКА
LEA ECX,[EBX]+8…………….;АДРЕС НАЧАЛА ДАННЫХ В БЛОКЕ
SUB EDX,ECX…………………..;ДЛИНА ПОЛЕЗНОГО МЕСТА В БЛОКЕ
JB M0006…………………………;НЕ МОЖЕТ БЫТЬ ОТРИЦАТЕЛЬНОЙ
OR ESI,ESI……….;ЕЩЕ НЕТ ПЕРВОГО СВОБОДНОГО ?
CMOVZ ESI,EBX ;ЗАПОМНИЛИ ПЕРВЫЙ СВОБОДНЫЙ БЛОК
;—- ПРОВЕРКА, ХВАТАЕТ ЛИ ДЛИНЫ БЛОКА —-
SUB EDX,EAX…..;ВЫЧИТАЕМ СКОЛЬКО НАДО
JB M0002…………;ЭТОТ БЛОК СЛИШКОМ МАЛ
INC B PTR [EBX] ;ОТМЕТИЛИ, ЧТО ТЕПЕРЬ БЛОК ЗАНЯТ
CMP EDX,16………;ОСТАЛОСЬ МАЛО СВОБОДНЫХ БАЙТ ?
JB @………………….;ТОГДА НЕ СОЗДАЕМ НОВЫХ БЛОКОВ
;—- РАЗБИВАЕМ НАЙДЕННЫЙ БЛОК НА ЗАНЯТЫЙ И НОВЫЙ —-
ADD ECX,EAX…………..;НАЧАЛО НОВОГО СВОБОДНОГО БЛОКА
MOV EDX,[EBX]+4……;НАЧАЛО СЛЕДУЮЩЕГО БЛОКА
MOV [ECX]+0,EBX……;ПРЕДЫДУЩИЙ В НОВОМ БЛОКЕ
MOV [ECX]+4,EDX……;СЛЕДУЮЩИЙ В НОВОМ БЛОКЕ
MOV [EBX]+4,ECX……;СЛЕДУЮЩИЙ В НАЙДЕННОМ БЛОКЕ
RCR CL,1…………………..;ВЫБРОСИЛИ ПРИЗНАК ЗАНЯТОСТИ
RCR B PTR [EDX]+0,1 ;ДОСТАЛИ ПРИЗНАК ЗАНЯТОСТИ
RCL CL,1……………………;СОХРАНИЛИ ПРИЗНАК ЗАНЯТОСТИ СЛЕДУЮЩЕГО
MOV [EDX]+0,ECX……;АДРЕС НОВОГО БЛОКА КАК ПРЕДЫДУЩИЙ
;—- ВЫХОД С АДРЕСОМ ПАМЯТИ —-
@: ADD EBX,8 ;НАЧАЛО ПАМЯТИ ПОЛЬЗОВАТЕЛЯ В БЛОКЕ
MOV ?BEGIN+4,ESI ;НОВЫЙ АДРЕС ПЕРВОГО СВОБОДНОГО
XCHG ECX,EAX ;ДЛИНА БЛОКА ДЛЯ ВОЗМОЖНОГО ОБНУЛЕНИЯ
;—- СРАЗУ ВЫХОД ИЛИ ЕЩЕ ОБНУЛЕНИЕ ВСЕГО ВЫДЕЛЕННОГО БЛОКА —-
N0001 DB 0C3H ;\RET
DB 0C0H ;/ИЛИ XOR EAX,EAX
;—- ОБНУЛЕНИЕ ALLOCATE, ЕСЛИ ЗАКАЗАНО —-
MOV EDI,EBX ;НАЧАЛО ВЫДЕЛЕННОГО БЛОКА
TEST CL,2
JZ @
STOSW
@: SHR ECX,2
REP STOSD ;САМО ОБНУЛЕНИЕ ДВОЙНЫМИ СЛОВАМИ
RET
;—- ВЫВОД ОШИБКИ В СВЯЗАННОМ СПИСКЕ БЛОКОВ —-
M0004:MOV AX,2500H ;УСТАНОВИЛИ КОД (37,0)
MOV EDX,OFFSET ОШИБ1 ;”ПАМЯТЬ КУЧИ РАЗРУШЕНА”
M0005:CALL ?SIGC ;ВЫДАЕМ СИГНАЛ ОШИБКИ
;—- В СЛУЧАЕ ОШИБКИ НАЧИНАЕМ ПОЛНУЮ ПРОВЕРКУ —-
M0006:JMP ?TEST_MEM ;ПРОВЕРКА И ПОИСК НАЧАЛА НАРУШЕНИЯ
;——————— FREE (ОСВОБОЖДЕНИЕ ПАМЯТИ) ———————
PUBLIC ?FREOP:………………;ВЫЗЫВАЕТСЯ ИЗ ПРОГРАММ PL/1
MOV ECX,OFFSET ?BEGIN ;АДРЕС НАЧАЛА СПИСКА
;—- ПРОВЕРКА УКАЗАТЕЛЯ НА NULL —-
OR EBX,EBX ;ЗАДАН ПУСТОЙ УКАЗАТЕЛЬ ?
JZ M0007 ;ТОГДА НИЧЕГО НЕ ДЕЛАЕМ
;—- ПРОВЕРКА, ЧТО АДРЕС ВНУТРИ СПИСКА БЛОКОВ —-
MOV EAX,[ECX]+0……………;НАЧАЛО СПИСКА БЛОКОВ
CMP EBX,EAX…………………..;МЕНЬШЕ НИЖНЕЙ ГРАНИЦЫ ?
JB M0004………………………….;ДА – НЕВЕРНЫЙ АДРЕС
CMP EBX,?MAX_MEMORY ;БОЛЬШЕ ВЕРХНЕЙ ГРАНИЦЫ ?
MOV EDX,OFFSET ?START_MEM
JAE M0004………………………..;ДА – НЕВЕРНЫЙ АДРЕС
;—- ПОДГОТОВКА К ВОЗМОЖНЫМ ПРОВЕРКАМ ЦЕЛОСТНОСТИ —-
MOV [EDX]+0,EAX
MOV D PTR [EDX]+4,0 ;ПРОВЕРКА БУДЕТ С НАЧАЛА
SUB EBX,8 ;АДРЕС НАЧАЛА ПАМЯТИ В БЛОКЕ
;—- КОРРЕКТИРОВКА АДРЕСА ПЕРВОГО СВОБОДНОГО БЛОКА —-
CMP [ECX]+4,EBX
JB @
MOV [ECX]+4,EBX
;—- ИСХОДНОЕ ПОЛОЖЕНИЕ ПРИ ПРОВЕРКЕ ЦЕЛОСТНОСТИ “КУЧИ” —-
@: MOV EDX,[EBX]+0 ;АДРЕС ПРЕДЫДУЩЕГО БЛОКА
MOV ECX,[EBX]+4…….;АДРЕС СЛЕДУЮЩЕГО БЛОКА
TEST DL,1…………………..;ПРАВИЛЬНЫЙ (ЗАНЯТЫЙ) АДРЕС ?
JZ M0006…………………..;НЕ МОЖЕТ БЫТЬ УЖЕ СВОБОДНЫМ
;—- ОТМЕЧАЕМ БЛОК КАК СВОБОДНЫЙ —-
DEC EDX ;СНЯЛИ ПРИЗНАК ЗАНЯТОСТИ
MOV [EBX]+0,DL ;ПОМЕСТИЛИ АДРЕС НА МЕСТО
;—- ПРОВЕРКА АДРЕСОВ ПРЕДЫДУЩЕГО И СЛЕДУЮЩЕГО БЛОКОВ —-
CMP EDX,EBX…….;ПРЕДЫДУЩИЙ ДОЛЖЕН БЫТЬ МЕНЬШЕ
JAE M0006…………;ИНАЧЕ ОШИБКА
CMP EBX,ECX…….;СЛЕДУЮЩИЙ ДОЛЖЕН БЫТЬ БОЛЬШЕ
JAE M0006…………;ИНАЧЕ ОШИБКА
;—- ПРОВЕРКА, НУЖНО ЛИ СКЛЕИВАТЬ С ПРЕДЫДУЩИМ —-
OR EDX,EDX…………………;ПРЕДЫДУЩЕГО БЛОКА НЕТ ?
JZ @………………………………;НЕ СКЛЕИВАЕМ
TEST B PTR [EDX]+0,1…..;ПРЕДЫДУЩИЙ БЛОК ЗАНЯТ ?
JNZ @……………………………;ЗАНЯТ – НЕ СКЛЕИВАЕМ
;—- СКЛЕЙКА С ПРЕДЫДУЩИМ БЛОКОМ —-
MOV AL,[ECX]+0…….;ДОСТАЛИ ПРИЗНАК ЗАНЯТОСТИ СЛЕДУЮЩЕГО
AND EAX,1………………;ВЫДЕЛИЛИ ПРИЗНАК ЗАНЯТОСТИ
OR EAX,EDX……………;УСТАНОВИЛИ ПРИЗНАК ЗАНЯТОСТИ
MOV [ECX]+0,EAX…..;ТЕПЕРЬ ЗДЕСЬ ПРЕДЫДУЩИЙ
MOV [EDX]+4,ECX…..;ТЕПЕРЬ ЗДЕСЬ СЛЕДУЮЩИЙ
;—- ПРОВЕРКА, НУЖНО ЛИ СКЛЕИВАТЬ СО СЛЕДУЮЩИМ —-
@: TEST B PTR [ECX]+0,1…….;СЛЕДУЮЩИЙ БЛОК СВОБОДЕН ?
JNZ M0007…………………………..;БЛОК ЗАНЯТ – НЕ СКЛЕИВАЕМ
;—- СКЛЕЙКА СО СЛЕДУЮЩИМ БЛОКОМ —-
MOV EBX,[ECX]+4…….;АДРЕС СЛЕДУЮЩЕГО В СЛЕДУЮЩЕМ
MOV ECX,[ECX]+0…….;АДРЕС ПРЕДЫДУЩЕГО В СЛЕДУЮЩЕМ
TEST B PTR [EBX],1……;И СЛЕДУЮЩИЙ СВОБОДЕН ?
JZ M0006…………………..;ЭТОГО НЕ МОЖЕТ БЫТЬ
MOV [EBX]+0,ECX……..;ТЕПЕРЬ УКАЗЫВАЕТ НА ПРЕДЫДУЩИЙ
INC B PTR [EBX]+0…….;И ЗАНЯТЫЙ
MOV [ECX]+4,EBX……..;НОВЫЙ СЛЕДУЮЩИЙ
M0007:RET
;—————- ПОЛНАЯ ПРОВЕРКА ЦЕЛОСТНОСТИ ПАМЯТИ ——————
PUBLIC ?TEST_MEM:…….;МОЖЕТ ВЫЗЫВАТЬСЯ В ПРОГРАММЕ
MOV EBX,?BEGIN…………..;НАЧАЛО СПИСКА БЛОКОВ
MOV EAX,[EBX]+0………….;АДРЕС ПЕРВОГО БЛОКА
XOR EBP,EBP………………….;МАКСИМАЛЬНОЕ ЧИСЛО ПРОВЕРОК
XOR EDX,EDX…………………;ПОКА НЕТ ОБЪЕМА ПАМЯТИ
MOV ESI,[EBX]+4…………….;АДРЕС СЛЕДУЮЩЕГО БЛОКА
CMP EAX,1……………………….;НАЧАЛО ИЛИ НОЛЬ (СВОБОДЕН) ИЛИ 1
JA ERROR………………………..;ЛЮБОЕ ДРУГОЕ ЗНАЧЕНИЕ – ОШИБКА
JMPS TST1………………………..;ПРИСТУПАЕМ К ЦИКЛУ ПРОВЕРОК
;————— ЧАСТИЧНАЯ ПРОВЕРКА ЦЕЛОСТНОСТИ ПАМЯТИ —————-
PUBLIC ?TEST_MEM_KVANT:..;МОЖЕТ ВЫЗЫВАТЬСЯ В ПРОГРАММЕ
MOV EBX,?START_MEM…………;НАЧАЛО СПИСКА ПАМЯТИ
MOV EDX,?ОБЪЕМ_MEM……….;ТЕКУЩИЙ ОБЪЕМ ПАМЯТИ
OR EBX,EBX…………………………….;ЕЩЕ НИ РАЗУ НЕ ПРОВЕРЯЛИ ?
JNZ @
MOV EBX,?BEGIN
MOV ?START_MEM,EBX…………;ТОГДА НА НАЧАЛО ПРОВЕРКИ
@: MOV EAX,[EBX]+0……………..;ПРЕДЫДУЩИЙ ВСЕГДА НОЛЬ
MOV EBP,100…………………………..;НЕ БОЛЕЕ 100 ПРОВЕРОК ЗА РАЗ
MOV ESI,[EBX]+4…………………….;АДРЕС СЛЕДУЮЩЕГО ЭЛЕМЕНТА
TST1: XOR ECX,ECX………………….;МАКСИМАЛЬНОЕ ЧИСЛО ЦИКЛОВ
;—- ЦИКЛ ПО БЛОКАМ СВЯЗАННОГО СПИСКА “КУЧИ” —-
TST2: MOV EDI,EBX…….;ЗАПОМНИЛИ ПРЕДЫДУЩИЙ
SUB EBX,[ESI]+0………….;АДРЕСА ДОЛЖНЫ СОВПАДАТЬ
JZ @……………………………..;ДА, СОВПАДАЮТ
INC EBX……………………….;ИЛИ ОТЛИЧАТЬСЯ НА 1 (ПРИЗНАК ЗАНЯТОСТИ)
JNZ ERROR………………….;АДРЕС ИСПОРЧЕН
@: OR EAX,[ESI]+0……….;СУММА ДВУХ ПРИЗНАКОВ
TEST AL,1………………………;ОБА СВОБОДНЫЕ ?
JZ ERROR……………………..;НЕ ДОЛЖНО БЫТЬ ДВУХ ПОДРЯД СВОБОДНЫХ
MOV EBX,ESI………………..;ЗАПОМНИЛИ ТЕКУЩИЙ
MOV EAX,[ESI]+0………….;АДРЕС ПРЕДЫДУЩЕГО БЛОКА
MOV ESI,[ESI]+4……………;АДРЕС СЛЕДУЮЩЕГО БЛОКА
OR ESI,ESI……………………..;КОНЕЦ ВСЕГО СПИСКА ?
JZ ВЫХОД……………………..;ДА, ВЫХОДИМ
ADD EDX,ESI………………….;\УЧЛИ ОБЪЕМ
SUB EDX,EBX………………….;/ЭТОГО УЧАСТКА
CMP ESI,?MAX_MEMORY ;ВЫСКОЧИЛИ ЗА ПРЕДЕЛЫ ПАМЯТИ ?
JA ERROR……………………….;ВЫСКОЧИЛИ – ОШИБКА
DEC EBP………………………….;ЗАКОНЧИЛАСЬ ПОРЦИЯ ?
JZ ВЫХ1…………………………..;ВЫХОДИМ ИЗ ОЧЕРЕДНОЙ ПОРЦИИ
LOOP TST2……………………….;ЗАЩИТА ОТ БЕСКОНЕЧНОГО ЗАЦИКЛИВАНИЯ
;—- НАЙДЕН СЛУЧАЙ “ПАМЯТЬ РАЗРУШЕНА” —-
ERROR:MOV ?ERR_MEM,EDI….;ПОСЛЕДНИЙ ПРАВИЛЬНЫЙ АДРЕС
MOV EBX,EDI…………………………..;ЗАПОМНИЛИ ЕГО
;—- ВЫДЕЛИЛИ МЕСТО В СТЕКЕ ДЛЯ СООБЩЕНИЯ —-
SUB…..ESP,10+LENGTH ОШИБ3
PUSH..8
POP…..ECX
MOV….EDI,ESP
;—- ЗАПИСАЛИ ДЛИНУ СТРОКИ СООБЩЕНИЯ ОБ ОШИБКЕ —-
MOV AL,LENGTH ОШИБ3+8
STOSB
;—- ФОРМИРУЕМ ПОСЛЕДНИЙ ПРАВИЛЬНЫЙ АДРЕС КАК ТЕКСТ —-
M0008:SHLD EAX,EBX,4
SHL EBX,4
AND AL,0FH
ADD AL,’0′
CMP AL,’9′
JBE @
ADD AL,7
@: STOSB
LOOP M0008
;—- ДОПИСЫВАЕМ ПОЯСНЕНИЕ “ПАМЯТЬ РАЗРУШЕНА” —-
MOV…..CL,LENGTH ОШИБ3
MOV…..ESI,OFFSET ОШИБ3
REP…….MOVSB
;—- ВЫХОДИМ С КОДОМ ОШИБКИ 38 (ПАМЯТЬ РАЗРУШЕНА) —-
MOV AX,2600H….;УСТАНОВИЛИ КОД (38,0)
MOV EDX,ESP……;КОММЕНТАРИЙ С АДРЕСОМ
JMP ?SIGC………….;ВЫДАЕМ СИГНАЛ ОШИБКИ
;—- ЦЕЛОСТНОСТЬ ПРОВЕРЕНА, ПРОВЕРЯЕМ ЭТАЛОННЫЙ ОБЪЕМ ПАМЯТИ —-
ВЫХОД:MOV ECX,OFFSET ?ЭТАЛОН_MEM
MOV EBX,?BEGIN
CMP D PTR [ECX],0 ;УЖЕ ЕСТЬ ЭТАЛОН ?
JNZ @……………………;ДА, УЖЕ ЕСТЬ
;—- ОДИН РАЗ ПОСЛЕ ALLOCATE/FREE ЗАПОМНИЛИ ЭТАЛОННЫЙ ОБЪЕМ —-
MOV [ECX],EDX
;—- СОБСТВЕННО ПРОВЕРКА ПОЛНОГО ОБЪЕМА —-
@: SUB EDX,[ECX]
JNZ ERROR ;ОБЪЕМ ПАМЯТИ ВДРУГ ИЗМЕНИЛСЯ
;—- ЗАПОМНИЛИ НАЧАЛО ОЧЕРЕДНОЙ ПОРЦИИ ПРОВЕРОК —-
ВЫХ1: MOV EBP,OFFSET ?START_MEM
MOV [EBP]+0,EBX
MOV [EBP]+4,EDX
XOR ECX,ECX
;—- ЕСЛИ ДОШЛИ ДО КОНЦА – ПРОВЕРКИ НАЧИНАЕМ ОПЯТЬ С НАЧАЛА —-
AND EBX,NOT 1
MOV EBX,[EBX]+4
CMP [EBX]+4,ECX
JNZ @
;—- ИСХОДНОЕ СОСТОЯНИЕ ПРОВЕРКИ С НАЧАЛА —-
MOV EAX,?BEGIN
MOV [EBP]+0,EAX
MOV [EBP]+4,ECX
@: RET
DSEG
EXTRN ?BEGIN:D,?MAX_MEMORY:D ;НАЧАЛО И МАКСИМАЛЬНЫЙ АДРЕС ПАМЯТИ
;—- ТЕКУЩИЙ АДРЕС ПОРЦИИ ПРИ ПРОВЕРКЕ ЦЕЛОСТНОСТИ —-
?START_MEM DD 0
;—- ТЕКУЩИЙ ОБЪЕМ ПРОВЕРЕННЫХ БЛОКОВ ПРИ ПРОВЕРКЕ ЦЕЛОСТНОСТИ —-
?ОБЪЕМ_МЕМ DD 0
;—- ЭТАЛОННЫЙ ОБЪЕМ ВСЕХ БЛОКОВ ПРИ ПРОВЕРКЕ ЦЕЛОСТНОСТИ —-
?ЭТАЛОН_МЕМ DD 0
?ERR_MEM DD 0
;—- ТЕКСТЫ СООБЩЕНИЙ ОБ ОШИБКАХ РАСПРЕДЕЛЕНИЯ ПАМЯТИ —-
ОШИБ1 DB LENGTH ОШИБ1-1,’ПАМЯТЬ КУЧИ РАЗРУШЕНА’
ОШИБ2 DB LENGTH ОШИБ2-1,’ВСЯ ПАМЯТЬ ИСЧЕРПАНА’
ОШИБ3 DB ‘ ПАМЯТЬ РАЗРУШЕНА’
Реализация оператора выделения памяти
Реализация оператора ALLOCATE (подпрограмма ?ALLOP), т.е. оператора выделения памяти, проста: по связанному списку «кучи» ищется первый свободный блок с размером не меньше заданного. Найденный блок разбивается на два: заданного размера, помечаемый теперь как занятый, и свободный остаток. Если остаток очень мал (менее 16 байт), разбивка блока не производится. Программисту возвращается адрес памяти, отстоящий на 8 байт от начала выделенного блока, в эти байты записываются служебные ссылки на предыдущий и следующий блоки.
Поиск начинается с запомненного ранее адреса первого свободного блока, а не вообще с начала всего связанного списка. Такая особенность обусловлена тем, что в реальных проектах, особенно при выделении памяти для одинаковых по размеру объектов, память в «куче» часто выделяется «плотно» без неиспользуемых участков, и неэффективно каждый раз при поиске проходить по занятому участку «кучи», постоянно растущему от ее начала.
К деталям, не имеющим отношения к теме статьи, относятся вспомогательные процедуры ?ALLOC_ZR и ?ALLOC_NZ, включающие и выключающие режим обнуления выделенной памяти. Автоматическое обнуление выделенной памяти позволяет не задавать явно ее инициализацию в программе, однако иногда затраты на ненужное обнуление больших блоков памяти велики, поэтому и добавлена возможность включения/выключения обнуления с помощью вызова данных процедур.
Реализация оператора освобождения памяти
Реализация оператора FREE (подпрограмма ?FREOP), т.е. оператора освобождения памяти, состоит в том, что помечается блок заданного адреса как опять свободный и, если предыдущий или следующий блоки тоже свободны, этот блок «сливается» со смежным, чтобы предотвратить фрагментацию свободной памяти в «куче».
Как было описано в [2], в точке обращения в программе к оператору FREE в указатель автоматически записывается нулевое значение для уменьшения риска «висячих ссылок».
Реализация контроля целостности памяти
Некоторые проверки правильности адресов имеются внутри подпрограмм ?ALLOP и ?FREOP и выполняются всегда, но, конечно, этого недостаточно для надежной работы. Поэтому добавлены две служебные подпрограммы ?TEST_MEM и ?TEST_MEM_KVANT без параметров, которые требуют явного вызова в программе и предназначены только для контроля целостности «кучи». Разница между ними в том, что первая проводит полную проверку всей «кучи», а вторая – только частичную (не более 100 очередных блоков за одно обращение). Поэтому время выполнения ?TEST_MEM_KVANT невелико и не превышает некоторой величины, тогда как длительность работы ?TEST_MEM зависит от числа блоков в «куче» и в общем случае не определена.
Предполагается, что ?TEST_MEM используется в отладочных режимах, в случаях обработки ошибок и т.п. Тогда как использование ?TEST_MEM_KVANT рассчитано и на длительную «штатную» эксплуатацию в отлаженных программах, при этом вызов подпрограммы можно поместить в некий всегда выполняющийся «главный» цикл программы, например, в цикл ожидания сообщений. Каждый раз, когда в программе происходит обращение к операторам ALLOCATE/FREE, «текущая» работа ?TEST_MEM_KVANT и уже накопленные результаты отменяются, проверка начинается с начала, поскольку структура «кучи» изменилась.
Контроль целостности «кучи» основан на проверках всех ограничений структуры, разумности адресов, а также на подсчете общего объема всех занятых и свободных блоков в «куче». Эта величина однократно выделяется программе при создании «кучи» с помощью подпрограммы Windows API VirtualAlloc и, естественно, не может самопроизвольно измениться при работе с «кучей».
В принципе, при ошибках распределения памяти структура «кучи» может быть испорчена любым образом. Непредсказуемо могут быть испорчены ссылки на блоки, однако, вероятность, что при этом не нарушится монотонное возрастание адресов, отсутствие двух смежных свободных блоков и т.д. мала. И уж совсем исчезающе мала вероятность, что нарушения ссылок внутри «кучи» не изменят суммарный размер всех занятых и свободных блоков. Хотя, конечно, теоретически могут быть случаи «порчи» памяти и без нарушения внутренней структуры «кучи».
Пример работы средств контроля
Простейший пример, моделирующий «порчу» памяти:
TEST:PROC MAIN;
DCL
A(100) FIXED(31) BASED(P),
P PTR,
?TEST_MEM ENTRY;
ALLOCATE(100) SET(P);
A=0;
FREE A;
END TEST;
В данном примере для моделирования характерной ошибки распределения памяти вместо оператора ALLOCATE A; записан оператор явного выделения блока размером 100 байт из «кучи» с занесением адреса в указатель P. В этом случае следующий оператор A=0; разрушит структуру «кучи», поскольку массив А должен занимать 400 байт, а в используемом для него по умолчанию указателе P записан адрес блока размером всего 100 байт.
Запуск программы даст неопределенную ошибку (рис.1).
Рис. 1. Неопределенная ошибка вследствие нарушения структуры «кучи».
Однако, если после оператора A=0; добавить вызов подпрограммы ?TEST_MEM, результат запуска программы изменится. На рис. 2. показан результат такого запуска программы в режиме интерактивной отладки.
Рис. 2. Результат выполнения с вызовом ?TEST_MEM в режиме интерактивной отладки.
Во-первых, эффект неопределенной ошибки изменился на более конкретную причину «память разрушена» поскольку оператор A=0; затер нулями в «куче» начало следующего блока со ссылками и алгоритм ?TEST_MEM обнаружил это. Во-вторых, имеется подсказка в виде комментария к ошибке со значением 01B4B590. Это последний адрес в связанном списке «кучи», когда контроль целостности еще не находил ошибок. В режиме интерактивной отладки директивой «d .p» было запрошено значение указателя P. Оно оказалось на 8 байт больше начала блока, где обнаружено нарушение структуры. Это подсказка на возможную причину нарушения: до блока по адресу, хранящемуся в указателе P, в структуре «кучи» все еще было нормально. Поэтому можно предположить, что обращение именно к этому объекту и «разрушило память».
Заключение
Такие средства контроля при распределении памяти, конечно, не могут обеспечить полную защиту от ошибочных действий в программе. Однако, при всей простоте и даже примитивности этого контроля, он дал хорошие результаты и позволил существенно улучшить отладку и эксплуатацию программ, защитив от часто встречающихся ошибок. Мало того, при многолетнем сопровождении больших проектов не было зафиксировано ни одного реального случая, когда бы нарушение целостности структуры «кучи» прошло бы при таком контроле незамеченным и вызвало бы в дальнейшем неопределенные эффекты в программе. И это достигнуто ценой лишь нескольких десятков команд, добавленных в системную библиотеку, и не приведших к ощутимой потере эффективности при управлении памятью.
Литература
- Т. Пратт «Языки программирования: разработка и реализация» глава 7 управление памятью. Издательство «Мир» Москва, 1979
- Д.Ю. Караваев «К вопросу о совершенствовании языка программирования» RSDN Magazine #4 2011
Автор публикации
