Why do I hit Invalid write/read after sbrk (recoding mini malloc)?

Question

I'm trying to recode a mini malloc using sbrk() and implementing a best-fit algorithm. I added a main to test my malloc along with my free().

Next thing a Segfault even though some of the values I tried to malloc in the main appear to be allocated (correct me if I'm wrong). Now with Valgrind I got some invalid write and read.

The problem starts from the first if of my_malloc() when hitting sbrk(). Here's my code:

#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string.h>
#include <stddef.h>
 
#define SBRK_FAILED ((void *)-1)
 
typedef struct s_block *t_block;
 
struct s_block {
    int size;
    t_block next;
    t_block prev;
    char free;
};
 
t_block *first_block = NULL;
t_block head = NULL;
t_block tail = NULL;
 
void *my_malloc(size_t size)
{
    t_block best_fit = NULL;
    t_block traveler_node = NULL;
 
    printf("mhere malloc\n");
    if (head == NULL) {//no free mapped spaces to allocate, sbrk to >> brk pt
        //Initialize head and tail blocks
        printf("first if malloc s\n");
        head = sbrk(sizeof(t_block));
        tail = head;
        head->size = size + sizeof(t_block);
        head->next = NULL;
        head->prev = NULL;
        head->free = 1;
        printf("first if malloc e\n");
        return sbrk(size);//Return address of starting of block size w/ info
    } else {
        //Find smallest free block that is large enough
        traveler_node = head;
        printf("else malloc s\n");
        while (traveler_node != NULL) {
            printf("in while\n");
            printf("size of this node = %d\n", traveler_node->size);
            printf("done\n");
            if (traveler_node->free == 0 && (unsigned long int)traveler_node->size >= (size + sizeof(t_block)) &&
            (best_fit == NULL || (unsigned long int)traveler_node->size < (unsigned long int)best_fit->size)) {
                best_fit = traveler_node;
                printf("second if in else malloc s\n");
                if ((unsigned long int)best_fit->size == size + sizeof(t_block)) {
                    // Best fit found, return it
                    printf("if in if in while in else malloc s\n");
                    best_fit->free = 1;
                    return (best_fit + sizeof(t_block));
                }
                printf("second if in else malloc e\n");
            }
            traveler_node = traveler_node->next;
            printf("size of next node = %d\n", traveler_node->size);
        }
        if (best_fit == NULL) {
            printf("if in else malloc s\n");
            //No blocks of appropriate size empty, add after tail and set new tail
            best_fit = sbrk(sizeof(t_block));
            best_fit->free = 1;
            best_fit->size = size + sizeof(t_block);
            best_fit->prev = tail;
            best_fit->next = NULL;
            tail = best_fit;
            printf("if in else malloc e\n");
            return sbrk(size);
        } else if ((unsigned long int)best_fit->size > sizeof(t_block)*2 + size) {
            //Split block
            printf("else if in else malloc s\n");
            traveler_node = (t_block)(best_fit + sizeof(t_block) + size);
            traveler_node->prev = best_fit;
            traveler_node->next = best_fit->next;
            traveler_node->next->prev = traveler_node;
            traveler_node->free = 0;
            traveler_node->size = best_fit->size - sizeof(t_block) - size;
            best_fit->free = 1;
            best_fit->size = size + sizeof(t_block);
            best_fit->next = traveler_node;
            printf("else if in else malloc e\n");
            return (best_fit + sizeof(t_block));
        } else {
            printf("else in else malloc s\n");
            //Block is not large enough to be split
            best_fit->free = 1;
            return best_fit + sizeof(t_block);
        }
    }
}
 
void my_free(void *ptr)
{
    t_block to_free = ptr - sizeof(t_block);
 
    to_free->free = 0;
    if (to_free != tail) {
        if (to_free != head && to_free->prev->free == 0) {
            to_free->prev->next = to_free->next;
            to_free->next->prev = to_free->prev;
            to_free->prev->size += to_free->size;
            to_free = to_free->prev;
        }
        if (to_free->next->free == 0) {
            to_free->size += to_free->next->size;
            to_free->next = to_free->next->next;
            to_free->next->prev = to_free;
        }
    } else {
        if (to_free == head) {
            head = tail = NULL;
            sbrk(-to_free->size);
            return;
        } else {
            tail = to_free->prev;
            tail->next = NULL;
            sbrk(-(to_free->size));
            if (tail->free == 0)
                my_free(tail + sizeof(t_block));
        }
    }
}
 
void    try(int input, int wanted)
{
  if (input != wanted)
    printf("\x1B[31mFAIL\033[0m\n");
  else
    printf("\x1B[32mOKAY\033[0m\n");
}
 
int main(void)
{
  char  *test = my_malloc(5);
  int   i;
 
  if (test == NULL)
    {
      write(1, "Malloc failed\n", strlen("Malloc failed\n"));
      return (0);
    }
 
  test[0] = 't';
  test[1] = 'e';
  test[2] = 's';
  test[3] = 't';
  test[4] = '\0';
  printf("*test == test : "); try(strcmp(test, "test") == 0, 1);
 
  my_free(test);
 
  char  *lol = my_malloc(18);
  lol[0] = 'l';
  lol[1] = 'o';
  lol[2] = 'l';
  lol[3] = '\0';
  printf("*lol == lol : "); try(strcmp(lol, "lol") == 0, 1);
 
  my_free(lol);
 
  char  *big = my_malloc(22);
  for (i = 0; i < 21; i++)
    big[i] = 'a' + i;
  big[i] = '\0';
  printf("*big == [a-u] : "); try(strcmp(big, "abcdefghijklmnopqrstu") == 0, 1);
  printf("big == test : "); try(big == test, 1);
 
  printf("\n");
  return (0);
}

Any feedback on this faulty(****) program is highly appreciated!

Answer 1

These statements:

        head = sbrk(sizeof(t_block));
...
        head->size = size + sizeof(t_block);

don't compute: you are asking the system for sizeof(t_block) but pretending that you have asked for size + sizeof(t_block).

You should also round size up so your malloc returns properly-aligned memory.