Linked Lists not working correctly when implementing malloc

Question

I'm trying to create my own version of malloc using best fit. To do this I am using linked lists to keep track of the allocations. However when I go to allocate space, the linked lists dont seem to be connecting. I've gone through the code over and over but can't see the problem. Any help would be appreciated so much.

Is this the same assignment as in Creating own malloc for an assignment. Getting a segmentation fault If so, you need to clearly state that this is for a homework assignment to help prevent numerous similar questions scattered across across the list. — David C. Rankin
– David C. Rankin, Commented Mar 22, 2015 at 2:02
That wasn't mine but it looks similar. This is for a project. — Dan Smith
– Dan Smith, Commented Mar 22, 2015 at 2:07
post the contents of #include "mymalloc.h". So the struct/list definition is available. — David C. Rankin
– David C. Rankin, Commented Mar 22, 2015 at 2:08
Header file is up. Sorry was having some trouble with Internet connection... — Dan Smith
– Dan Smith, Commented Mar 22, 2015 at 2:18
What does the source for my_free() look like? I assume that is the function that puts memory areas onto the free list? — Richard Chambers
– Richard Chambers, Commented Mar 22, 2015 at 2:30

jschultz410 · Accepted Answer · 2015-03-22 04:26:32Z

2

One problem is in allocating your node structures:

root = (struct node *)sbrk(sizeof(root));
...
added = (struct node *)sbrk(sizeof(root));

Should be:

root = (struct node *)sbrk(sizeof(*root));
...
added = (struct node *)sbrk(sizeof(*root));

At best, your nodes and your allocations would "share" memory incorrectly.

Also, I think you need to be careful to ensure proper alignment of your memory. I'm not sure your code (or sbrk) does that.

Here's a problem with your splitting code:

return best+sizeof(best);
...
newnode = best+best->mallocsize+sizeof(root);

Since best is a struct node*, these additions jump further ahead in memory than I think you intended. I think you meant to cast best to a (char*) in these expressions.

Also, I think the computation for newnode is wrong, even after you cast to (char*). I think you want something more like:

newnode = best + 1 + size / sizeof(*root) + !!(size % sizeof(*root));

You also forget to compute and set newnode->mallocsize!

The following math probably will be done in unsigned (i.e. - int's promoted to size_t's):

if (best->mallocsize-size-sizeof(short) < sizeof(root)) {

In that case, you can underflow 0 on the left hand side, which will cause you to improperly split the node. You can fix this by throwing the subtraction over to the other side of the inequality because you already ensured that size < best->mallocsize:

if (best->mallocsize - size < sizeof(root) + sizeof(short)) {

Couple of other points:

In your best fit search, you almost always skip over the root for some reason.
In your best fit search, you don't consider unused node's whose mallocsize equals size.
In your best fit search, once you find an optimally sized unused node (i.e. - size == current->mallocsize), end the search (i.e. - break the loop).
In your allocations you call sbrk twice: once for your node and once for the application's memory. If you are doing this to ensure proper alignment of memory, then that's good (assuming sbrk does this for you), but then your assumption that a node + 1 gives you the address of the application's memory may not be true.

edited Mar 22, 2015 at 4:26

answered Mar 22, 2015 at 3:19

jschultz410

2,93916 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Dan Smith Over a year ago

YES! That worked. Thank you I can't believe I just spent 5 hours of my life on an asterisk....

jschultz410 Over a year ago

You have the same problem in your later allocation too. I'll edit.

jschultz410 Over a year ago

@DanSmith Found some more issues.

Dan Smith Over a year ago

Thanks man, I think I got them all fixed. I moved the current=current->next to after the if statement. I added a >= to the if statement and a break. For the last part I did change it. I though my way would be simpler I guess I didn't take into account the sbrk doing alignment. I allocated the whole thing in the first sbrk and then that pointer plus the node size at the end.

Collectives™ on Stack Overflow

Linked Lists not working correctly when implementing malloc

1 Answer 1

4 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related