自己的 Malloc 实现冻结在 brk

Question

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

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 冻结了我的程序。

感谢您的帮助！

Answer 1

您的代码中存在多个问题：

在 blockAdd 中，如果 href->next_ 在 else 分支中不是 NULL，则无法更新 href->next_->previouse_。
findLagerSize 应更改为 findLargerSize 并应使用 size + sizeof(block) 定位适当的内存块。
allocateMemory 也是不正确的：传递给 sbrk 的大小应该包括 sizeof(block) 额外的字节，因此分配的块应该插入到堆中并拆分如果大于 size + sizeof(block).
在freeList中，如果checkAllFree()return为真，你应该调用brk(head)，而不是brk(ptr)。
在 merge 中，您没有正确更新 href->size：您应该合并尺寸。此外，您不更新 href-_next->previouse_.
shrinkHeap 的原型应该有一个 return 类型和一个参数列表：
```
void shrinkHeap(void)
```
在 shrinkHeap 中，您必须在调用 brk 之前更新 link ，因为指针可能会在称呼。此外，您必须测试 href->previouse_ 是否不是 NULL 并且此更新可以简化为：

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

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

在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); }

自己的 Malloc 实现冻结在 brk

Own Malloc implementation freeze at brk

c

malloc

free

heap-memory

brk