Binary Buddies implementation questions

Question

I've read and understand the concepts behind the binary buddies approach to memory allocation, and I'm trying to put it to work in C but I have a few implementation specific questions before I can really get started.

https://drive.google.com/file/d/0BxJX9LHXUU59OWZ6ZmhvV1lBX2M/view?usp=sharing - This is a link to the assignment specification, my question pertains to problem 5.

The problem specifies that one call to malloc is to be made at the initialization of the allocator, and all requests for memory must be serviced using the space acquired from this call.

It's clear that the initial pointer to this space must be incremented in some way when a call to get_memory() is made, and the new pointer will be returned to the calling process. How can I increment the pointer by a specific number of bytes?
I understand that free lists for each block size must be kept, but I'm unsure exactly how these will be initialized and maintained. What is stored in the free list exactly? The memory pointer?

I apologize if these questions have been asked before, I haven't found a relevant question that provided enough clarity for me to get working.

score 0 · Answer 1 · edited May 23 '17 at 12:22

For your first question, you just have to increment your pointer like a normal variable.

The value of a pointer corresponds to the address in memory of the data it points to. By incrementing it by, say 10, you actually move 10 bytes further into your memory.

As for the free list, malloc() creates a structure contingent with the allocated memory block containing informations such as the address of the memory block,its size, and whether it is free or not.

You goal is to create these structures so you can keep track of the status the different memory blocks you have allocated or free with your get_memory() and release_memory() function.

You might also find this useful : https://stackoverflow.com/a/1957125/4758798

score 0 · Answer 2 · answered Apr 08 '15 at 14:53

It's clear that the initial pointer to this space must be incremented in some way when a call to get_memory() is made, and the new pointer will be returned to the calling process. How can I increment the pointer by a specific number of bytes?

When you call get_memory(), you will return a pointer to the main memory added to some offset. The word 'increment' implies that you are going to change the value of the initial pointer, which you should not do.

Here is some simple code of me subaddressing one big memory block.

#include <stdlib.h>
#include <stdio.h>

int main (void)
{
  // Allocate a block of memory
  void * memory_block = malloc (512);

  // Now "Split" that memory into two halves.
  void * first_half = memory_block;
  void * second_half = memory_block + 256;

  // We can even keep splitting...
  void * second_first_half = second_half;
  void * second_second_half = second_half + 128;

  // Note that this splitting doesn't actually change the main memory block.  
  // We're just bookmarking locations in it.

  printf ("memory_block %p\n", memory_block);
  printf ("first_half %p\n", first_half);
  printf ("second_half %p\n", second_half);
  printf ("second_first_half %p\n", second_first_half);
  printf ("second_second_half %p\n", second_second_half);

  return 0;
}

I understand that free lists for each block size must be kept, but I'm unsure exactly how these will be initialized and maintained. What is stored in the free list exactly? The memory pointer?

At a minimum, you probably want to keep track of the memory pointer and the size of that memory block, so something like this...

typedef struct memory_block {
  void * memory;
  size_t size;
} memory_block_t;

There are other ways to represent this though. For example, you get equivalent information by keeping track of their memory offsets relative to the global malloc. I would suggest treating memory as a set of offsets like this:

void * global_memory; // Assigned by start_memory()

// Functionally equivalent to the above struct
// memory = global_memory + begin;
// size = end - begin;
typedef struct memory_block {
  size_t begin;
  size_t end;
} memory_block_t;

There are multiple approaches to this difficult problem.

Binary Buddies implementation questions

2 Answers2