Нужна помощь в устранении последних не связанных с ошибками "странностей", вызванных переписыванием динамического распределителя памяти (первоначально в C) на языке Game Maker
Извиняюсь за довольно длинный вопрос. Здесь просто много чего нужно объяснить.
Итак, у меня есть следующая последовательность сценариев в Game Maker, предназначенная для предоставления аналога malloc и свободных интерфейсов C. Они намерены иметь тот же интерфейс, за исключением того, что Game Maker не имеет прямого доступа к виртуальной памяти, они используют массив в качестве пространства кучи. Сам динамический распределитель памяти моделируется на основе модели заполнения блоков. Лично я нахожу, что описание этого не слишком понятно для меня, поэтому я склонен считать его "низкоуровневым двусвязным списком логического типа, в котором выделенные блоки памяти хранятся между узлами". Во всяком случае, к коду:
Код
mm_init()
{
HEAD_NODE = 0;
/*no need to align 0*/
HEAP_SPACE[HEAD_NODE] = 0;
LINKED_LIST_LENGTH = 0;
TAIL_NODE = HEAD_NODE;
return 0;
}
mm_malloc()
{
newsize = argument[0];
freeP = HEAD_NODE;
if (getLength(freeP) - newsize > 0 && !getFree(freeP))
{
insert(freeP, newsize);
setFree(freeP,true);
return freeP + 1;
}
while (getNext(freeP) < TAIL_NODE)
{
freeP=getNext(freeP);
if (getLength(freeP) - newsize > 0 && !getFree(freeP))
{
insert(freeP, newsize);
setFree(freeP,true);
return freeP + 1;
}
}
p = TAIL_NODE; /*add to the heap and return the starting position*/
//p = mem_sbrk(newsize + 8); /*add to the heap and return the starting position*/
if (p == -1)
{
return NULL;
} else
{
HEAP_SPACE[p] = (newsize) + (1 << 31);
HEAP_SPACE[getNext(p) - 1] = newsize;
if (LINKED_LIST_LENGTH == 0)
{
HEAD_NODE = p;
}
TAIL_NODE = getNext(p);
LINKED_LIST_LENGTH += 1;
return (p + 1);
}
}
mm_free ()
{
/* adjust so that ptr points
* to the node for this block
*/
p = argument[0] - 1;
HEAP_SPACE[p] = getLength(p);
/*did the pointer originate from the heap*/
if (p > HEAD_NODE && p < TAIL_NODE)
{
if (!getFree(getPrevious(p)))
{
/* the previous node
* can be coalesced
*/
removeNode(p);
p = getPrevious(p);
}
if (!getFree(getNext(p)) && getNext(p) <= TAIL_NODE)
{
/* the next node
* can be coalesced
*/
if (getNext(p) == TAIL_NODE)
{
TAIL_NODE = p;
}
removeNode(getNext(p));
}
}
}
getNext()
{
return (argument[0] + getLength(argument[0]) + 2);
}
getPrevious()
{
return (argument[0] - getLength(argument[0]-1) - 2);
}
getLength()
{
/*zero out the leftmost bit, reserved for the free value*/
return HEAP_SPACE[argument[0]] & (~(1 << 31));
}
getFree()
{
return (HEAP_SPACE[argument[0]] & (1 << 31));
}
setLength()
{
HEAP_SPACE[argument[0]] = argument[1] + (getFree(argument[0]) << 31);
HEAP_SPACE[getNext(argument[0]) - 1] = argument[1];
}
setFree()
{
HEAP_SPACE[argument[0]] = getLength(argument[0]) + (argument[1] << 31);
}
removeNode()
{
setLength(getPrevious(argument[0]),getLength(getPrevious(argument[0]))+getLength(argument[0])+2);
LINKED_LIST_LENGTH -= 1;
/*length is in terms of integer words*/
}
insert()
{
/* the node has to fit to avoid distorting
* the linked list's heap property
*/
if (argument[1] + 2 < getLength(argument[0]))
{
node = argument[0] + argument[1] + 2;
/*ensure the free field is 0*/
HEAP_SPACE[node] = 0;
setLength(node,getLength(argument[0])-argument[1]-2);
setLength(argument[0],argument[1]);
} else
{
/* all blocks and nodes are 2 byte aligned, so a difference of one
* would only exist in the case of a system flaw
*/
HEAP_SPACE[argument[0]] = getLength(argument[0]) + (1 << 31);
}
}
Эта проблема'
В любом случае, главная проблема здесь - функция malloc.
Рассмотрим следующую выдержку из malloc:
if (getLength(freeP) - newsize > 0 && !getFree(freeP))
{
insert(freeP, newsize);
setFree(freeP,true);
return freeP + 1;
}
while (getNext(freeP) < TAIL_NODE)
{
freeP=getNext(freeP);
if (getLength(freeP) - newsize > 0 && !getFree(freeP))
{
insert(freeP, newsize);
setFree(freeP,true);
return freeP + 1;
}
}
Если я изменю это на следующее, это сломается при определенных обстоятельствах (я объясню внизу). Он не должен ломаться, так как в теории установка значения узла в true не должна иметь никакого отношения к вставке узла между ним и следующим.
if (getLength(freeP) - newsize > 0 && !getFree(freeP))
{
setFree(freeP,true);
insert(freeP, newsize);
return freeP + 1;
}
while (getNext(freeP) < TAIL_NODE)
{
freeP=getNext(freeP);
if (getLength(freeP) - newsize > 0 && !getFree(freeP))
{
setFree(freeP,true);
insert(freeP, newsize);
return freeP + 1;
}
}
В частности, я смог получить ошибку при выполнении следующей последовательности вызовов функций (все из которых теоретически допустимы):
- mm_malloc (10)
- mm_malloc (10)
- mm_free (1)
- mm_malloc (5) // ошибка, показанная ниже
Ошибка, которую я получаю, приведена в цитате ниже. Кажется, это указывает на ошибку в сегменте, который я установил. Контекст кода (то есть событие щелчка) не очень полезен, поскольку это просто событие, используемое для создания небольшого отладчика, на который я буду ссылаться ниже. Я нажимаю на красный квадрат, и появляется всплывающее окно для ввода данных в malloc.
___________________________________________
ERROR in
action number 1
of Mouse Event for Left Button
for object obj_malloc:
In script mm_malloc:
In script insert:
In script setLength:
Error in code at line 2:
HEAP_SPACE[getNext(argument[0]) - 1] = argument[1];
^
at position 13: Array index >= 32000
Вот ссылка на отладчик, который я использовал для тестирования распределителя. Это довольно полезно, поскольку показывает фактическое содержимое массива примерно через 30 индексов. Возможно, кто-то увидит что-то с этим: вам понадобится GM 8.0 Lite, чтобы открыть это
Вопрос
На самом деле я не испытываю никаких ошибок со сборкой, которая у меня сейчас есть. Однако тот факт, что мне пришлось обмениваться этими двумя вызовами функций, чтобы все по-прежнему работало, вызывает большое беспокойство. Это похоже на симптом более серьезной проблемы. Теоретически, ничто не требует, чтобы они шли в любом порядке. Так что есть проблема где-то в этой области кода. Просто кажется, что я не могу найти это из-за того, что не проверял правильные входные данные. Мне в первую очередь просто любопытно, почему он это делает. Скорее всего, это не вызовет у меня проблем в будущем.
Кроме того, красная кнопка выполняет malloc, а зеленая кнопка выполняет free. Если кому-то нужно больше информации о том, что именно является действительным, пожалуйста, не стесняйтесь спрашивать. Я знаю, что интерфейс управления памятью C не так хорошо известен, как, скажем, команды C++ new и delete.
Спасибо!
Редактировать:
Некоторым людям было любопытно, почему мне нужно написать собственный распределитель динамической памяти на объектно-ориентированном языке программирования. Проще говоря, есть понятие ссылок (как в языке Java), но они буквально сломаны. Смотрите следующую цитату (должно быть довольно ясно, почему это в значительной степени требует от меня реализации моих собственных структур):
Обратите внимание, что присвоение экземпляров идентификатору экземпляра меняется каждый шаг, поэтому вы не можете использовать значения из предыдущих шагов. Также обратите внимание, что удаленные экземпляры останутся в списке до конца шага. Поэтому, если вы также удаляете экземпляры, вам нужно проверить, существует ли экземпляр еще. Позвольте мне привести пример. Предположим, что каждый юнит в вашей игре обладает определенной силой, и вы хотите найти сильнейшего, вы можете использовать следующий код:
Из документации на экземпляры.
1 ответ
Проблема заключается в подфункции getFree:
getFree()
{
return (HEAP_SPACE[argument[0]] & (1 << 31));
}
В отличие от c, который обычно приводил бы его к 0 или 1 как к булевой функции, создатель игры до некоторой степени не имеет типа и поэтому, если блок выделен (да, функция возвращает значения, противоположные тем, которые диктует логика. цель.) возвращает "1 << 31".
Теперь рассмотрим зажигательную функцию setLength:
setLength()
{
HEAP_SPACE[argument[0]] = argument[1] + (getFree(argument[0]) << 31);
HEAP_SPACE[getNext(argument[0]) - 1] = argument[1];
}
Эта функция принимает возвращаемое значение getFree и сдвигает его на 31 бит. В общем, это означает, что мы добавили (1 << 62) к длине. Примечание: этот бит НЕ будет отфильтрован по длине, это означает, что мы испортили значение длины узла.
В ретроспективе исправление довольно тривиально:
getFree()
{
return ((HEAP_SPACE[argument[0]] & (1 << 31)) > 0);
}
Истина и ложь отображаются в 1 и 0 в Game Maker.
Также, на несвязанной ноте, функция malloc не выравнивает блоки с 2 приращениями индекса. Однако это не имело никакого отношения к этой проблеме, так как это простой вопрос регулировки длины блока.