Função malloc e função free

Marta Santos · May 24, 2021 at 06:45 PM

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 · May 24, 2021 at 09:34 PM

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 · May 24, 2021 at 09:59 PM

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 · May 25, 2021 at 09:39 PM

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á.

Edited May 25, 2021 at 09:44 PM by Felipe.Silva

Marta Santos · May 25, 2021 at 09:46 PM

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

Edited May 25, 2021 at 09:57 PM by Marta Santos

Felipe.Silva · May 25, 2021 at 09:55 PM

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 · May 25, 2021 at 10:02 PM

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.

Sign In

Função malloc e função free

Recommended Posts

Marta Santos

Link to comment

Share on other sites

Fernando Mercês

Link to comment

Share on other sites

Marta Santos

Link to comment

Share on other sites

Felipe.Silva

Link to comment

Share on other sites

Marta Santos

Link to comment

Share on other sites

Felipe.Silva

Link to comment

Share on other sites

Marta Santos

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members

Home

Learn

Forums

Store