0

let's look at this given code:

void free(void *ap) {
Header *bp, *p;

bp = (Header *)ap - 1;
for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
    if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
        break;
if (bp + bp->s.size == p->s.ptr) {
    bp->s.size += p->s.ptr->s.size;
    bp->s.ptr = p->s.ptr->s.ptr;
} else
    bp->s.ptr = p->s.ptr;
if (p + p->s.size == bp) {
    p->s.size += bp->s.size;
    p->s.ptr = bp->s.ptr;
} else
    p->s.ptr = bp;
freep = p;
}

As I understand if this given free gets a pointer to already existed memory block, this loop:

for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
    if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
        break;

will actually goes forever. Because when p==ap and for every other p the condition:!(bp > p && bp < p->s.ptr) will be true and the condition p >= p->s.ptr && (bp > p || bp < p->s.ptr) will be false.

Editing: The full code can be seen here: Explain this implementation of malloc from the K&R book

Victor
  • 105
  • 4
  • What is `Header`? What is `freep`? What is `s`? Please show a [MCVE]. – Jabberwocky Feb 06 '18 at 14:16
  • 2
    BTW: I'm not sure if studying C from a 30 years old book is actually a good idea. – Jabberwocky Feb 06 '18 at 14:23
  • 2
    @MichaelWalz: I do. IMHO it still remains the best exposition of C out there. Indeed then you should move onto further study. – Bathsheba Feb 06 '18 at 14:28
  • 1
    It is pretty normal for an allocator to assume that a previously allocated block might be useful in the future. So no, it doesn't release memory, it makes it available for future malloc() calls. A more sophisticated allocator will co-operate with the OS to release the address space as well, usually when enough contiguous space becomes available again, but taking a dependency on the OS implementation surely wasn't the point of the code. – Hans Passant Feb 06 '18 at 14:52

1 Answers1

1

Since freep is the free list (as the name suggests) and ap an allocated chuck (and thus it is not in the free list), p==ap shouldn't be true. The loop end one of the following conditions is true:

  • the chunk to free is between the current and the next free-list element with a higher address (loop condition);
  • the chunk to free above at the end (highest address) of the free list, i.e. there, where the free list wraps. (if condition).
Matthias
  • 8,018
  • 2
  • 27
  • 53
  • So actually you are agree with me that the given free function doesn't free allocated memory when it gets one( when ap is in the free list)?. I asked this question because the name of the free function is misleading. – Victor Feb 06 '18 at 14:42
  • 1
    The function does free allocated memory. Allocated memory is memory that is **not** in the free list. You get in trouble, when you try to free memory that is already in the free list. – Matthias Feb 06 '18 at 14:55