c - 需要帮助解决由Game Maker语言重写动态内存分配器(最初为C)引起的最后几个非bug的“怪胎”

Question

对于这个有点长的问题表示歉意。这里有很多事情需要解释。

因此，我在Game Maker中有以下脚本序列，旨在提供C的malloc和自由接口的类似物。他们打算具有相同的接口，但是由于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）//错误如下所示


我收到的错误在下面的引用中给出。似乎表明我出发的细分市场中存在错误。代码的上下文（即click事件）并没有真正的用处，因为那只是用来制作一个小的调试器的事件，我将在下面链接。我单击一个红色正方形，然后弹出一个框，输入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个索引中数组的实际内容。也许有人会看到以下内容：you'll need GM 8.0 Lite to open this

This isn't my link nor have I downloaded it from here, but this seems like the only (safe) download of GM 8.0 Lite to remain on the web.



问题

我目前使用的版本实际上没有遇到任何错误。但是，我必须交换这两个函数调用才能使所有功能仍然正常工作，这一事实非常令人不安。感觉就像是更大问题的征兆。从理论上讲，没有什么要求它们按照任何顺序进行。因此，该代码区域中的某个地方存在问题。似乎由于无法测试正确的输入而无法定位。我主要是好奇为什么会这么做。很有可能，将来实际上不会引起我任何问题。

同样，红色按钮执行malloc，绿色按钮执行free。如果有人需要更多有关有效输入的信息，请随时询问。我知道C内存管理接口不如C ++的new和delete命令那么著名。

谢谢！



编辑：

有些人很好奇为什么我需要用面向对象的编程语言编写自己的动态内存分配器。简而言之，存在引用的概念（例如Java语言中的引用），但从字面上看，它们是相当不完整的。参见下面的引用（应该很清楚为什么这么多要求我实现自己的结构）：


  请注意，实例到实例ID的分配在每个步骤都会更改，因此您不能使用先前步骤中的值。还请注意，被删除的实例将保留在列表中，直到步骤结束。因此，如果您还要删除实例，则需要检查实例是否仍然存在。让我举个例子吧。假设游戏中的每个单元都有特定的功能，而您想找到最强的一个，则可以使用以下代码：


从instances的文档中。

Answer 1

问题位于子函数getFree中：

getFree()
{
    return (HEAP_SPACE[argument[0]] & (1 << 31));
}

与通常将c强制转换为布尔函数的c有所不同，游戏制造商在某种程度上固有地是无类型的，因此如果分配了该块（是的，该函数返回的值与逻辑指示的值相反。）目的。）返回“ 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);
}

True和false分别映射到游戏制造商的1和0。

另外，不相关的注释是，malloc函数不会将块对齐到2个索引增量。然而，这与该问题无关，这是调整块长度的简单问题。