0

I'm implementing a memory manager using free list, whose node is a struct that contains meta data about the chunk of memory to be managed.

I'll call malloc() once at the very beginning to get a piece of memory from the OS. Then I'll manage it using my own program. In subsequent programs, I cannot use malloc() any more, so I have to keep the meta data (list of nodes) inside that memory. Here's my problem, suppose:

struct list *node1 = malloc(n_bytes);   // only call malloc() once here
node1->memStart = node1 + sizeof(struct list)   // beginning address of managable
                                                // memory
node1->size = bytes_allocated;
node1->used = 1;
node1->next = NULL;
// starting address of node2
struct list *node2 = node1->memStart + node1->size;      // used another node to track the second piece of
                                                        // that memory
node2->size = 4096; 
node2->used = 0;      // node2's memory is unused yet
node2->memStart = node2 + sizeof(struct list);
node2->next = NULL;
node1-next = node2;   // link them

So here I'm not sure if I've written these meta data (size, used, memStart, next) to the memory address starting at node1, thus making it look like:

----------<----node1
|  size  |
----------
|  used  |
----------
|memStart|------|
----------      |
|  next  |      |
----------      |
|        |<-----|
|  mem   | 
|        |
----------<----node2
|  size  |
----------
|  used  |
----------
|memStart|
----------
|  next  |
----------
|        |
|  mem   | 
|        |
----------

So I just wonder after the above code, whether the memory layout would be like the one drawn above. It's mainly about node2, I'm not sure if I can use it like this to write the meta data to the memory. It's important because as more and more memory is allocated, I'll need more nodes to keep track of them. I think the way to do this without malloc(otherwise it doesn't make sense to write my own manager) is to do pointer arithmetics to chop the memory into chunks and use an overhead to keep track of them.

The structure of list should be:

struct list{
  int size;
  void *memStart;
  int used;
  struct list *next;
}
J Freebird
  • 3,664
  • 7
  • 46
  • 81
  • The way to do it without `malloc` is to use `brk()` and `sbrk()` syscalls. That's what `malloc` does. – Filipe Gonçalves Feb 14 '14 at 11:06
  • 1
    Which value do you assign to `bytes_allocated` and where does the magic 4096 come from? Also it would be helpful to know `struct list`'s declaration. – alk Feb 14 '14 at 11:10
  • @JFreebird Note that with this approach it is possible to make unaligned nodes. In some enviroments this will result in crash or something worse. You may have to add padding between previous memory area and next node. – user694733 Feb 14 '14 at 13:58
  • @alk bytes_allocated is just some long int like 1024, which is a user input. So if I want to allocate 1KB using my own memory manager, I should write memalloc(1024), just simulate the function of malloc(). The 4096 is just the size of the available memory, it's an example. – J Freebird Feb 14 '14 at 17:35
  • @user694733 what do you mean by that? Could you please elaborate? Thanks. – J Freebird Feb 14 '14 at 17:38

1 Answers1

6

No, the memory layout will not be like the one drawn above. Consider this line:

node1->memStart = node1 + sizeof(struct list)

Because of pointer arithmetic, node1 + x will scale x by sizeof(*node1). That is, node1 + sizeof(struct list) yields a pointer to an address that is node1 + sizeof(struct list)*sizeof(struct list) bytes away. This is basic pointer arithmetic in C. You want this instead:

node1->memStart = ((char *) node1) + sizeof(struct list)

Depending on the definition of memStart in struct list, this may also be wrong:

struct list *node2 = node1->memStart + node1->size;

However, if you declared memStart as char *, it should work, assuming bytes_allocated (which you don't show how you got it) is correct.

This line has the same error as the equivalent one for node1:

node2->memStart = node2 + sizeof(struct list);
Filipe Gonçalves
  • 20,783
  • 6
  • 53
  • 70
  • Thanks a lot Filipe. I just added the struct of list. I thought memStart should be a void*, just a pointer to track the start address of a memory block. but it seems it should be char*, though I don't really understand why. And bytes_allocated is just some long int like 1024, which is a user input. So if I want to allocate 1KB using my own memory manager, I should write memalloc(1024), just simulate the function of malloc(). So if the position nodes pointed to is correct, can I assign its members (node2->size etc.) values to write a continues memory? I'm a bit confused how it works. – J Freebird Feb 14 '14 at 17:46
  • @JFreebird `memStart` doesn't have to be `char *`. It can be `void *`, you just have to make sure that `node1` is interpreted as `char *` before doing any pointer arithmetic, like I showed above. The rest should work as long as `bytes_allocated` is less than or equal to the real memory you allocated (of course). Just bear in mind that alignment issues may arise. I recommend having a look at K&R's final chapter, they show a sample `malloc` implementation. Use that as a reference. – Filipe Gonçalves Feb 15 '14 at 13:42
  • Thanks for the info! But could you give me some more hint on the alignment issue? I read that last section of that book, it used an union to deal with it. So the size of the union will be the largest member, thus it adds some padding among nodes? But I don't really understand how it can occur and why there's such a problem. Thanks. – J Freebird Feb 15 '14 at 18:46
  • @JFreebird Typically, not every address can be used to store any data type. For example, if integers are 4 bytes, then on most architectures every address storing an integer is a multiple of 4. Why? Well, if 0 can store an integer, then the next integer would be at 4, and the next at 8, etc. What about `double`? If `double` is 8 bytes, then you will most likely have to store it on addresses that are multiples of 8. This is mostly due to efficiency issues and the way that the CPU works. Every system has one data type that is the most stringent [continues on next comment] – Filipe Gonçalves Feb 15 '14 at 18:54
  • According to K&R (page 185), if the most restrictive type can be stored at a particular address, all other types may be also. So, on your memory allocator, you will want to return addresses aligned for the most restrictive type on the system. See this question to learn more about why alignment is a concern: http://stackoverflow.com/questions/381244/purpose-of-memory-alignment And see Chapter 8, section 8.7 on K&R to learn how to implement an allocator with this in mind. K&R uses a `typedef` for the most stringent type; another common approach is using a union with all types. – Filipe Gonçalves Feb 15 '14 at 18:57
  • that IBM article says compilers will add padding among struct members to make them aligned. So once they're in the aligned address, this won't be a problem? And I'm also using sizeof(struct list) instead of calculating it myself. Do you have any idea whether the cc compiler on MINIX takes care of this, or the MINIX on virtualbox can deal with unaligned address? Thanks a lot. – J Freebird Feb 15 '14 at 22:31
  • Yes, compilers add padding in structures. Your `struct list` has been padded accordingly, you shouldn't worry about it. But you must still worry about returning memory addresses aligned with the most stringent type. Padding is a different business, you don't have to worry about that. – Filipe Gonçalves Feb 15 '14 at 22:46