c - 自己的 Malloc 实现冻结在 brk

Question

为了练习，我目前正在尝试用 c 编写自己的 malloc 函数。所以我的问题是，在从堆中进行一些分配后，我的程序将冻结。我找到了导致冻结的代码段，当我调用 brk sys 调用时它会冻结。我已经尝试在那里解锁我的互斥锁，但这没有用。为了测试它，我编写了一个永久循环并在数组中分配内存并随机释放它。

static list *head = NULL;
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

typedef struct list
{         
  size_t size_;                
  int free_;                  
  struct list *next_;      
  struct list *previouse_;
} block;

void blockAdd(block *href, size_t size)
{
  href->free_ = FALSE;
  href->next_ = NULL;
  href->previouse_ = NULL;

  if (!head || head > href)
  {
    if (head)
    {
      head->previouse_ = href;
    }
    href->size_ = size + sizeof(block);
    href->next_ = head;
    head = href;
  }
  else
  {
    href->next_ = NULL;
    block *current = head;

    while (current->next_ && current->next_ < href)
    {
      current = current->next_;
    }
    href->size_ = size + sizeof(block);
    href->next_ = current->next_;
    href->previouse_ = current;
    current->next_ = href;
  }
}

void *findExactSizeMatch(size_t size)
{
  block *href = head;
  size_t t = size + sizeof(block);

  while (href)
  {
    if (href->size_ == (size + sizeof(block)) && href->free_)
    {
      href->free_ = FALSE;
      return href;
    }
    href = href->next_;
  }
  return NULL;
}

void *findLagerBlock(size_t size)
{
  block *href = head;

  while (href)
  {
    if (href->free_ && href->size_ > size)
    {
      return split(href, size);
    }
    href = href->next_;
  }

  return NULL;
}

void *allocateMemory(size_t size)
{
  block *new_block = sbrk(BLOCK_SIZE(size));

  if (new_block == SBRK_FAILED)
  {
    exit(1);
  }
  blockAdd(new_block, size);

  return new_block;
}

bool checkAllFree()
{
  block *href = head;

  while (href)
  {
    if (!href->free_)
    {
      return FALSE;
    }
    href = href->next_;
  }
  return TRUE;
}

void freeList(block *ptr)
{
  if (checkAllFree())
  {
    if (brk(ptr) == BRK_FAILED)
    {
     exit(1);
    }
    head = NULL;
  }
}

void merge()
{
  block *href = head;

  while (href && href->next_)
  {
    if (href->free_ && href->next_->free_)
    {
      href->size_ = href->next_->size_;
      href->next_ = href->next_->next_;
    }
    href = href->next_;
  }
}

//--------------------------Here it makes some strange things
shrinkHeap()
{
  block *href = head;

  while (href && href->next_)
  {
    href = href->next_;
  }

  if (href && href->free_)
  {
    if (brk(href) == BRK_FAILED)
    {
      exit(1);
    }
    href->previouse_->next_ = href->next_;
  }
}

void *malloc(size_t size)
{
  if (!size)
  {
    return NULL;
  }
  pthread_mutex_lock(&mutex);

  block *new_list = NULL;

  new_list = findExactSizeMatch(size);
  if (new_list)
  {
    pthread_mutex_unlock(&mutex);
    return new_list + sizeof(block);
  }

  new_list = allocateMemory(size);
  pthread_mutex_unlock(&mutex);

  return new_list + sizeof(block);
}

void free(void *ptr)
{
  if (!ptr || !head)
  {
    return;
  }
  pthread_mutex_lock(&mutex);

  block *pref = ptr - sizeof(block);

  pref->free_ = TRUE;

  freeList(pref);
  shrinkHeap();
  merge();

  pthread_mutex_unlock(&mutex);
}

我不知道为什么，但是 brk 冻结了我的程序。

谢谢你的帮助！

标签： cmallocheap-memoryfreebrk

Answer 1

您的代码中有多个问题：

• 在 中，如果不在分支中blockAdd，则无法更新。href->next_->previouse_href->next_NULLelse

• findLagerSize应更改为findLargerSize并size + sizeof(block)应用于定位适当的内存块。

• allocateMemory也不正确：传递给的大小sbrk应该包括sizeof(block)额外的字节，因此分配的块应该插入堆中，如果大于size + sizeof(block).

• 在freeList，如果checkAllFree()返回真，你应该调用brk(head)，而不是brk(ptr)。

• 在 中merge，您没有href->size正确更新：您应该组合大小。此外你不更新href-_next->previouse_。

• 的原型shrinkHeap应该有一个返回类型和一个参数列表：

  void shrinkHeap(void)
  

• shrinkHeap您必须在调用之前更新链接，因为调用brk后指针可能会变得无效。此外，您必须测试是否href->previouse_不是NULL，并且此更新可以简化为：

      if (href->previouse_ != NULL)
          href->previouse_->next_ = NULL;
  

• 您的malloc函数有一个缺陷：return new_list + sizeof(block);不返回指向已分配块的指针，而是返回更远的指针，导致应用程序写入超出已分配块的末尾，从而可能破坏竞技场。此外，free 计算的指针不指向 ，block即使程序没有写入内存块并调用未定义的行为，也会导致 arena 进一步损坏。

  在 中的两个地方malloc()，您应该改为：

      return new_list + 1;
  

• 类似地free()，但不一定会导致错误，您应该避免对void指针执行算术运算，将它们转换为unsigned char *可移植代码：

  block *pref = (void *)((unsigned char*)ptr - sizeof(block));
  

  或在正确键入后执行算术：

  block *pref = ptr;
  ptr -= 1;
  

这是修改后的版本：

static struct list *head = NULL;
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

typedef struct list {
    size_t size_;           // block size, including header
    int free_;              // free indicator, true or false
    struct list *next_;
    struct list *previouse_;
} block;

void blockAdd(block *href, size_t size) {
    href->free_ = FALSE;
    href->size_ = size + sizeof(block);
    href->next_ = NULL;
    href->previouse_ = NULL;

    if (!head || head > href) {
        if (head) {
            head->previouse_ = href;
        }
        href->next_ = head;
        head = href;
    } else {
        block *current = head;
        while (current->next_ && current->next_ < href) {
            current = current->next_;
        }
        href->next_ = current->next_;
        if (href->next_) {
            href->next_->previouse_ = href;
        }
        href->previouse_ = current;
        current->next_ = href;
    }
}

void *findExactSizeMatch(size_t size) {
    block *href = head;
    size_t t = size + sizeof(block);

    while (href) {
        if (href->free_ && href->size_ == t) {
            href->free_ = FALSE;
            return href;
        }
        href = href->next_;
    }
    return NULL;
}

void *findLargerBlock(size_t size) {
    block *href = head;
    size_t t = size + sizeof(block);

    while (href) {
        if (href->free_ && href->size_ > t) {
            return split(href, size);
        }
        href = href->next_;
    }
    return NULL;
}

void *allocateMemory(size_t size) {
    /* should add size of `block` */
    block *new_block = sbrk(BLOCK_SIZE(size));

    if (new_block == SBRK_FAILED) {
        exit(1);
    }
    /* should split new_block if BLOCK_SIZE(size) > size */
    blockAdd(new_block, size);

    return new_block;
}

bool checkAllFree() {
    block *href = head;

    while (href) {
        if (!href->free_) {
            return FALSE;
        }
        href = href->next_;
    }
    return TRUE;
}

void freeList(block *ptr) {
    if (checkAllFree()) {
        if (brk(head) == BRK_FAILED) {
            exit(1);
        }
        head = NULL;
    }
}

void merge(void) {
    block *href = head;

    while (href && href->next_) {
        if (href->free_ && href->next_->free_) {
            href->size_ += href->next_->size_;
            href->next_ = href->next_->next_;
            href->next_->previouse_ = href;
        }
        href = href->next_;
    }
}

void shrinkHeap(void) {
    block *href = head;

    if (href) {
        while (href->next_) {
            href = href->next_;
        }
        if (href->free_) {
            if (href->previouse_ != NULL) {
                href->previouse_->next_ = NULL;
            }
            if (brk(href) == BRK_FAILED) {
                exit(1);
            }
        }
    }
}

void *malloc(size_t size) {
    if (!size) {
        return NULL;
    }
    pthread_mutex_lock(&mutex);

    block *new_list = findExactSizeMatch(size);
    if (new_list == NULL) {
        new_list = findLargerSize(size);
    }
    if (new_list == NULL) {
        new_list = allocateMemory(size);
    }
    pthread_mutex_unlock(&mutex);
    if (new_list)
        return new_list += 1;
    else
        return NULL;
}

void free(void *ptr) {
    if (!ptr || !head) {
        return;
    }
    pthread_mutex_lock(&mutex);

    block *pref = ptr;
    pref -= 1;
    pref->free_ = TRUE;

    freeList(pref);
    merge();
    shrinkHeap();

    pthread_mutex_unlock(&mutex);
}