Função malloc e função free

Marta Santos · Maio 24, 2021 em 18:45

boa tarde, tenho um exercicio onde preciso implementar a função void *myMalloc(unsigned int bytesToAllocate) e a função int myFree(void *address). Tenho também que implementar void debugBlockList() para mostrar todo o conteúdo da lista de blocos.

Até agora fiz o que está no código em baixo, mas estou com RUNTIME ERROR em alguns testes de verificação do código noutros o output que me dá não é o correto...

Alguém me podia ajudar????

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

#define BLOCK_SIZE 12 //sizeof(struct s_block)
#define align4(x) (((((x)-1)>>2)>>2))


typedef struct s_block *t_block;

struct s_block {
    size_t size;  // current size of block
    t_block next; // pointer to next block
    t_block prev;
    int free;     // flag indicating that the block is free or occupied; 0 or 1.
    void *ptr;
    char data[1];
};

t_block head = NULL; // points to the beginning of the list
t_block tail = NULL; // points to the last element of the list


t_block find_block(t_block *last, size_t size) {
    t_block b = head;

    while (b && !(b->free && b->size >= size)){
       *last = b;
        b = b->next;
    }
    return b;
}

t_block extend_heap(t_block last, size_t s) {
 int sb;
 t_block b;
 b = sbrk (0);
 sb = (int)sbrk( BLOCK_SIZE + s);
 if (sb < 0) return (NULL );
 b->size = s;
 b->next = NULL;
 b->prev = last;
 b->ptr = b->data;
 if (last) last ->next = b;
 b->free = 0;
 return (b);
}



/* Get the block from and addr */
t_block get_block (void *p) {
    char *tmp;
    tmp = p;
    return (p = tmp -= BLOCK_SIZE );
}

/* Valid addr for free */
int valid_addr (void *p) {
 if (head) {
   if ((t_block)p>head && p<sbrk(0)) {
     return (p == ( get_block(p))->ptr );
   }
 }
 return (0);
}

void split_block(t_block b, size_t s){
  t_block new;
  new = (t_block )(b->data + s);
  new ->size = b->size - s - BLOCK_SIZE ;
  new ->next = b->next;
  new ->prev = b;
  new ->free = 1;
  new -> ptr = new->data;
  b->size = s;
  b->next = new;
  if(new->next) new->next->prev = new;
}


t_block fusion(t_block b){
  if (b->next && b->next ->free ){
    b->size += BLOCK_SIZE + b->next ->size;
    b->next = b->next ->next;
    if (b->next)
      b->next ->prev = b;
  }
  return (b);
}

void debugBlockList() {
    t_block p = head;
    printf("current block list:\n");
    while(p!=NULL){
      printf("address: %lu - %u bytes (%s)\n", (unsigned long)(p), p->size, p->free?"free":"in use");
      p=p->next;
    }

}

void *myMalloc(size_t size) {

    t_block b,last;
    size_t s = align4(size);
    if(head) {
        last = head;
        b = find_block(&last,s);
        if(b) {
          /* can we split */
          if ((b->size - s) >= ( BLOCK_SIZE + 4))
            split_block(b,s);
          b->free =0;
        } else {
          /* No fitting block , extend the heap */
          b = extend_heap(last ,s);
          if (!b)
             return(NULL );
        }
    } else {
        /* first time */
        b = extend_heap(NULL ,s);
        if (!b)
          return(NULL );
        head = b;
   }

  return(b);
}

void myFree(void *ptr) {
t_block b;
    if ( valid_addr (ptr)) {
        b = get_block (ptr);
        b->free = 1;
        /* fusion with previous if possible */
        if(b->prev && b->prev ->free)
          b = fusion(b->prev );
        /* then fusion with next */
        if (b->next)
          fusion(b);
        else {
          /* free the end of the heap */
          if (b->prev)
            b->prev ->next = NULL;
          else
            /* No more block !*/
            head = NULL;
          brk(b);
        }
    }

}

Fernando Mercês · Maio 24, 2021 em 21:34

Código interessante! Acho que o @Felipe.Silva vai curtir também! Ele publicou um artigo recentemente sobre alocação de memória aqui no Mente Binária. :)

Marta, ao que me parece, sua myFree() não está funcionando. Criei uma main() básica:

int main(void) {
	int *p = myMalloc(sizeof(int));
	scanf("%d", p);
	printf("Before freeing it: %d\n", *p);
	myFree(p);
	printf("After freeing it: %d\n", *p);
	return 0;
}

E o conteúdo de p é impresso na tela, mesmo depois da chamada à myFree():

% ./marta <<< 42
Before freeing it: 42
After freeing it: 42

Em que momento você recebe um runtime error?

Abraço,

Fernando

Marta Santos · Maio 24, 2021 em 21:59

18 minutes ago, Fernando Mercês said:
Código interessante! Acho que o @Felipe.Silva vai curtir também! Ele publicou um artigo recentemente sobre alocação de memória aqui no Mente Binária. ?

Marta, ao que me parece, sua myFree() não está funcionando. Criei uma main() básica:
int main(void) {
	int *p = myMalloc(sizeof(int));
	scanf("%d", p);
	printf("Before freeing it: %d\n", *p);
	myFree(p);
	printf("After freeing it: %d\n", *p);
	return 0;
}
E o conteúdo de p é impresso na tela, mesmo depois da chamada à myFree():
% ./marta <<< 42
Before freeing it: 42
After freeing it: 42
Em que momento você recebe um runtime error?

Abraço,

Fernando

Olá Fernando!

Ao que parece não era necessário implementar o código todo que mandei no inicio...

Foi-me dado o seguinte código:

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

#define BLOCK_SIZE sizeof(struct s_block)

typedef struct s_block *t_block;

struct s_block {
    size_t size;  // current size of block
    t_block next; // pointer to next block
    int free;     // flag indicating that the block is free or occupied; 0 or 1.
};

t_block head = NULL; // points to the beginning of the list
t_block tail = NULL; // points to the last element of the list


t_block find_block(size_t size) {
    t_block b = head;
    // TODO: alterar para best-fit
    while (b!=NULL && !(b->free && b->size >= size))
        b = b->next;
    return b;
}

t_block extend_heap(size_t s) {
    t_block b = sbrk(BLOCK_SIZE+s);
    if (b == (void *)-1)
        return NULL; /* if sbrk fails, return NULL pointer*/

    b->size = s;
    b->next = NULL;
    b->free = 0;
    if (head==NULL) head = b;
    else tail->next = b;
    tail = b;
    return b;   // with metadata
}

void debugBlockList() {
    t_block p = head;
    printf("current block list:\n");
// TODO

    printf("address: %lu - %u bytes (%s)\n",
       (unsigned long)(p), p->size, p->free?"free":"in use");

}


void *myMalloc(size_t size) {
// TODO
}

void myFree(void *ptr) {
// TODO
}



/**
 * teste myMalloc/myFree
 **/
int main(int argc, char *argv[]) {
    unsigned int maxSpace;

    if (argc != 2) {
        printf("%s max_memory_to_allocate\n", argv[0]);
        exit(1);
    }
    maxSpace = atoi(argv[1]);

    printf("Metadata size=%d\n", BLOCK_SIZE);
    // getting the current break value
    printf("Current program break = %lu\n", (unsigned long)sbrk(0));

    for (int s = 1; s < maxSpace; s *= 2) {
        void *ptr = myMalloc(s);
        if (ptr == NULL)
            printf("No more mem\n");
        else
            printf("returned pointer = %lu\n", (unsigned long)ptr);
        myFree(ptr);
    }
    debugBlockList();
    // getting the current break value
    printf("Current program break = %lu\n", (unsigned long)sbrk(0));
    for (int s = maxSpace; s>0; s /= 2) {
        void *ptr = myMalloc(s);
        if (ptr == NULL)
            printf("No more mem\n");
        else
            printf("returned pointer = %lu\n", (unsigned long)ptr);
    }
    debugBlockList();

    return 0;
}

(onde está #TODO é o que tenho que fazer)

Só posso implementar a função malloc e a função free com as funções já disponobilizadas - find_block / extend_heap. Não tinha percebido isso.

Até agora, tenho o seguinte:

void *myMalloc(size_t size) {
// TODO
    t_block b;
    if(head){
       tail = head;
       b = find_block(size);
       if(b) {
          b->free=0;
       } else {
          b = extend_heap(size);
          if(!b)
            return (NULL);
       }
    } else {
       b = extend_heap(size);
       if(!b) {
         return (NULL);
       }
       head = b;
    }
    return(b+1);
}

/* Get the block from and addr */
t_block get_block (void *p){
    char *tmp;
    tmp = p;
    return(p = tmp -= BLOCK_SIZE);
}

/* Valid addr for free */
int valid_addr (void *p){
    if(head) {
       if(p>head && p<sbrk(0)) {
          return (p == (get_block(p)));
       }
    }
    return (0);
}

void myFree(void *ptr) {
// TODO
    t_block b;
    if(valid_addr(ptr)){
       b = get_block(ptr);
       b->free=1;
    } else {
       if(b=tail) b = tail->next = NULL;
       else head = NULL;
       brk(b);
    }
}

Acho que o problema está no myFree, mas não estou a conseguir perceber o que está mal nem como implementar esta função sem usar as funções get_block e valid_addr....

Alguma dica????

Felipe.Silva · Maio 25, 2021 em 21:39

void *myMalloc(size_t size) {
// TODO
    t_block b;
    if(head){
       tail = head;
      // ....

Esse "tail = head" não me parece certo. Pela lógica do código tail deveria ser atualizado para o novo bloco alocado na memória toda vez que a função extend_heap() precisar ser chamada... Do jeito que está tail volta a apontar para head a cada nova chamada de myMalloc() (exceto a primeira chamada onde head ainda será NULL).

Sugiro atualizar o código para as vezes que precisou chamar "b = extend_heap(size);" atualizar tail para apontar para b.

Ah, e qual é a lógica do else dentro da função myFree()? Também toma cuidado com a diferença entre = e ==. Dentro do if deveria ser == certo?

Outra coisa que não entendi é isso: b = tail->next = NULL;

Você quer modificar b para NULL? Mas logo em seguida você executa brk(b); o que não faria sentido passar NULL para esta função.
E b também não é inicializada caso o valid_addr retorne false, pois você declarou a variável mas só a inicializa dentro do if.

Essa estrutura s_block foi o professor que passou assim? Pois eu vejo um probleminha ao precisar desalocar memória e atualizar o valor de tail. Como você vai pegar o endereço do penúltimo bloco sem um ponteiro para o bloco anterior?
Até daria para percorrer a lista para isso, mas seria mais eficiente ter um ponteiro t_block previous na estrutura. ?

E uma coisa interessante é se sua myFree() liberasse todos os últimos blocos que estejam marcados como free, e não somente o último. Ou então deixar apenas N blocos no final e liberar o resto, assim poupa tempo pro myMalloc() não precisar de extend_heap() o tempo todo.

Ah, uma dica: Antes de mais nada sugiro implementar logo a função debugBlockList(). Ela vai te ajudar a "visualizar" a lista e assim ficará mais fácil entender o que está funcionando conforme deveria e o que não está.

Editado Maio 25, 2021 em 21:44 por Felipe.Silva

Marta Santos · Maio 25, 2021 em 21:46

14 minutes ago, Felipe.Silva said:
void *myMalloc(size_t size) {
// TODO
    t_block b;
    if(head){
       tail = head;
      // ....
Esse "tail = head" não me parece certo. Pela lógica do código tail deveria ser atualizado para o novo bloco alocado na memória toda vez que a função extend_heap() precisar ser chamada... Do jeito que está tail volta a apontar para head a cada nova chamada de myMalloc() (exceto a primeira chamada onde head ainda será NULL).

Sugiro atualizar o código para as vezes que precisou chamar "b = extend_heap(size);" atualizar tail para apontar para b.

Ah, e qual é a lógica do else dentro da função myFree()? Também toma cuidado com a diferença entre = e ==. Dentro do if deveria ser == certo?

Outra coisa que não entendi é isso: b = tail->next = NULL;

Você quer modificar b para NULL? Mas logo em seguida você executa brk(b); o que não faria sentido passar NULL para esta função.
E b também não é inicializada caso o head não seja NULL, pois você declarou a variável mas só a inicializar dentro do if.

Essa estrutura s_block foi o professor que passou assim? Pois eu vejo um probleminha ao precisar desalocar memória e atualizar o valor de tail. Como você vai pegar o endereço do penúltimo bloco sem um ponteiro para o bloco anterior?
Até daria para percorrer a lista para isso, mas seria mais eficiente ter um ponteiro t_block previous na estrutura. ?

Ah, uma dica: Antes de mais nada sugiro implementar logo a função debugBlockList(). Ela vai te ajudar a "visualizar" a lista e assim ficará mais fácil entender o que está funcionando conforme deveria e o que não está.

Olá,

Entretanto atualizei as funções e ficou assim...

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>

#define BLOCK_SIZE sizeof(struct s_block)

typedef struct s_block *t_block;

struct s_block {
    size_t size;  // current size of block
    t_block next; // pointer to next block
    int free;     // flag indicating that the block is free or occupied; 0 or 1.
};

t_block head = NULL; // points to the beginning of the list
t_block tail = NULL; // points to the last element of the list


t_block find_block(size_t size) {
    t_block b = head;
    // TODO: alterar para best-fit
    while (b!=NULL && !(b->free && b->size >= size)){
        b = b->next;
    }
    return b;
}

t_block extend_heap(size_t s) {
    t_block b = (t_block) sbrk(BLOCK_SIZE+s);
    if (b == (void *)-1)
        return NULL; /* if sbrk fails, return NULL pointer*/

    b->size = s;
    b->next = NULL;
    b->free = 0;
    if (head==NULL) head = b;
    else tail->next = b;
    tail = b;
    return b;   // with metadata

}

void debugBlockList() {
    t_block p = head;
    printf("current block list:\n");
    while(p!=NULL){
      printf("address: %lu - %u bytes (%s)\n", (unsigned long)(p), p->size, p->free?"free":"in use");
      p=p->next;
    }

}


void *myMalloc(size_t size) {

    t_block b = find_block(size);

       if(b) {
          b->free = 0;
       } else {
           b = extend_heap(size);
           if(!b) return NULL;
       }

    return(b+1);
}

void myFree(void *ptr) {
    t_block b = (t_block)ptr - 1;
    b -> free = 1;
}

Acho que ficou bem, mas agora tenho que fazer uma implementação best-fit para o find_block

Editado Maio 25, 2021 em 21:57 por Marta Santos

Felipe.Silva · Maio 25, 2021 em 21:55

Você parou de atualizar head e tail em myMalloc()... Mas atualizar esses ponteiros é importante para o funcionamento desse sistema aí.
Por exemplo: O que a função find_block() retorna se head for NULL? Ela só pode retornar NULL... Se você nunca inicializar head para apontar para um bloco, find_block() vai sempre retornar NULL.

Você pode fazer algo mais ou menos assim:

void *myMalloc(size_t size)
{
  t_block b = find_block(size);
  if (b)
  {
    b->free = 0;
  }
  else
  {
    b = extend_heap(size);
    if (!b)
      return NULL;

    if (!head)
      head = b;

    tail = b;
  }
  return (b + 1);
}

Repare como eu inicializo head quando extend_heap() é chamado pela primeira vez. E repare que sempre é necessário chamá-lo eu atualizo tail. Entendeu a ideia? Assim head está sempre apontando para o primeiro bloco alocado e tail sempre apontando para o último.

Não esquece disso também na myFree(). Ela precisa atualizar tail toda vez que liberar um bloco. E lembre-se que existe a possibilidade de myFree() ser usada no bloco apontado por head, neste caso o ponteiro head passaria a apontar para uma memória que já foi liberada.
Talvez a solução mais simples neste caso seja redefinir head para NULL e "recomeçar". ?

Marta Santos · Maio 25, 2021 em 22:02

5 minutes ago, Felipe.Silva said:
Você parou de atualizar head e tail em myMalloc()... Mas atualizar esses ponteiros é importante para o funcionamento desse sistema aí.
Por exemplo: O que a função find_block() retorna se head for NULL? Ela só pode retornar NULL... Se você nunca inicializar head para apontar para um bloco, find_block() vai sempre retornar NULL.

Você pode fazer algo mais ou menos assim:
void *myMalloc(size_t size)
{
  t_block b = find_block(size);
  if (b)
  {
    b->free = 0;
  }
  else
  {
    b = extend_heap(size);
    if (!b)
      return NULL;

    if (!head)
      head = b;

    tail = b;
  }
  return (b + 1);
}
Repare como eu inicializo head quando extend_heap() é chamado pela primeira vez. E repare que sempre é necessário chamá-lo eu atualizo tail. Entendeu a ideia? Assim head está sempre apontando para o primeiro bloco alocado e tail sempre apontando para o último.

Não esquece disso também na myFree(). Ela precisa atualizar tail toda vez que liberar um bloco. E lembre-se que existe a possibilidade de myFree() ser usada no bloco apontado por head, neste caso o ponteiro head passaria a apontar para uma memória que já foi liberada.
Talvez a solução mais simples neste caso seja redefinir head para NULL e "recomeçar". ?

Eu atualizei a minha resposta anterior porque recebi um email do meu professor a indicar que provavelmente o que falta é a implementação best-fit do find_block

Não é necessário atualizar tail nem head porque os blocos são atualizados no extend_heap.

Entrar

Função malloc e função free

Posts Recomendados

Marta Santos

Link para o comentário

Compartilhar em outros sites

Fernando Mercês

Link para o comentário

Compartilhar em outros sites

Marta Santos

Link para o comentário

Compartilhar em outros sites

Felipe.Silva

Link para o comentário

Compartilhar em outros sites

Marta Santos

Link para o comentário

Compartilhar em outros sites

Felipe.Silva

Link para o comentário

Compartilhar em outros sites

Marta Santos

Link para o comentário

Compartilhar em outros sites

Participe da conversa

Quem Está Navegando 0 membros estão online

Home

Ensino

Fóruns

Loja