Собственная реализация Mallo c замораживается на brk

Question

для практики В настоящее время я пытаюсь написать свою собственную функцию mallo c в c. Поэтому мой вопрос: после некоторого выделения из кучи моя программа зависнет. Я нашел сегмент кода, который будет блокировать блокировку, и он остановится, когда я позвоню по вызову системы brk. Я уже пытался разблокировать свой мьютекс, но это не сработало. Чтобы проверить это, я написал перманент l oop, выделил память в массиве и освободил ее случайным образом.

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_->previouse_, если href->next_ не NULL в ветви else .

• findLagerSize следует изменить на findLargerSize и использовать size + sizeof(block) для поиска соответствующего блока памяти.

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