Marta Santos Postado Maio 24, 2021 em 18:45 Compartilhar Postado 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); } } } Citar Link para o comentário Compartilhar em outros sites More sharing options...
Fernando Mercês Postado Maio 24, 2021 em 21:34 Compartilhar Postado 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 Citar Link para o comentário Compartilhar em outros sites More sharing options...
Marta Santos Postado Maio 24, 2021 em 21:59 Autor Compartilhar Postado 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???? Citar Link para o comentário Compartilhar em outros sites More sharing options...
Felipe.Silva Postado Maio 25, 2021 em 21:39 Compartilhar Postado Maio 25, 2021 em 21:39 (editado) 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 Citar Link para o comentário Compartilhar em outros sites More sharing options...
Marta Santos Postado Maio 25, 2021 em 21:46 Autor Compartilhar Postado Maio 25, 2021 em 21:46 (editado) 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 Citar Link para o comentário Compartilhar em outros sites More sharing options...
Felipe.Silva Postado Maio 25, 2021 em 21:55 Compartilhar Postado 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". ? Citar Link para o comentário Compartilhar em outros sites More sharing options...
Marta Santos Postado Maio 25, 2021 em 22:02 Autor Compartilhar Postado 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. Citar Link para o comentário Compartilhar em outros sites More sharing options...
Posts Recomendados
Participe da conversa
Você pode postar agora e se cadastrar mais tarde. Se você tem uma conta, faça o login para postar com sua conta.