c-在brk拥有Malloc实现冻结

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

谢谢你的帮助！

Answer 1

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

• 在blockAdd中，如果href->next_不是else分支中的NULL，则无法更新href->next_->previouse_。

• CCD_ 6应当被改变为CCD_ 7并且应当使用CCD_。

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

• 在freeList中，如果checkAllFree()返回true，则应调用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，即使程序没有写入内存块并调用未定义的行为，也会导致竞技场的进一步损坏。

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