Bonjour,

j'essaye de recoder un petit malloc à l'aide de sbrk(), en implementant un best-fit.

Alors j'ai rajouté un main pour tester et je me retrouve avec un gros segfault

j'ai lancé Valgrind et là pleins d'invalid write et read, le problème commence déjà dans le 1er IF de my_malloc();

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

J'ai l'impression qu'il y a des initialisations manquantes ou bien je fais mal mes sbrk(), en tout cas un piste

Merci d'avance.

Ligne 37, est une erreur à mon sens, peut-être

head->free = 1 + '0';

?

fred1599 a écrit:

Ligne 37, est une erreur à mon sens, peut-être

head->free = 1 + '0';

?

Alors merci pour la remarque, je viens de rajouter à tout les ->free <+'0'>.

Quand je lance ./test j'ai tout bon, par contre quand je lance avec valgrind j'ai encore des invalid write aux mêmes endroits.

Dans chaque appel de malloc j'ai 3 erreurs:

-invalid write of size 8 (address is 0 bytes after the brk data segment limit)

-invalid write of size 8 (address is 8 bytes after the brk data segment limit)

-invalid write of size 1 (address is 16 bytes after the brk data segment limit)

-
Edité par MainDawnSir 12 juin 2022 à 16:44:52

fred1599 a écrit:

Quelle est ta commande de compilation ?

gcc -o test main.c

./test ou bien valgrind ./test

essai avec

gcc main.c -pedantic -Wall -o test

-
Edité par fred1599 12 juin 2022 à 17:27:04

Bonjour,

ce qu'il faut surtout faire, pour utiliser au mieux les logs valgrind, est de compiler en mode debug = rajouter l'option -g.

Ensuite il faut demander à valgrind d'être bien explicite = valgrind --leak-check=full --track-origins=yes --show-reachable=yes ./test

Tout est bien expliqué dans les docs.