K&R section 8.7 for loop in free()

Question

In K&R(2nd) section 8.7, I think there is an unexpected infinite for loop in free() and its test part seems wrong.
I inserted four // comments. malloc() has one, morecore() has another and free() has the others.

typedef long Align;

union header {
    struct {
        union header* ptr;
        unsigned size;
    }s;
    Align x;
};

typedef union header Header;

static Header base;
static Header *freep = NULL;

/* malloc: general-purpose storage allocator */
void *malloc(unsigned nbytes)
{
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned  nunits;

    nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
    if ((prevp = freep) == NULL) {          /* no free list yet */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {          /* big enough */
            if (p->s.size == nunits)        /* exactly */
                prevp->s.ptr = p->s.ptr;
            else {                          /* allocate tail end */
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p + 1);
        }
        if (p == freep)                      /* wrapped around free list */
            // base.s.ptr = &base, freep == &base
            if ((p = morecore(nunits)) == NULL)
                return NULL;                 /* none left */
    }
}

#define NALLOC 1024     /* minimum #units to requst */

/* morecore: ask system for more memory */
static Header *morecore(unsigned nu)
{
    char *cp, *sbrk(int);
    Header *up;

    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1)      /* no space at all */
        return NULL;
    up = (Header *) cp;
    up->s.size = nu;
    // base.s.ptr = &base, freep == &base
    free((void *)(up+1));
    return freep;
}

/* free: put block ap in free list */
void free(void *ap)
{
    Header *bp, *p;

    bp = (Header *)ap - 1;  /* point to block header */
    // base.s.ptr = &base, freep == &base
    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;  /* freed block at start or end of arena */
    // for (p = freep; !(0); )\
            if (p >= s.ptr && (0))\
                break;

    if (bp + bp->s.size == p->s.ptr) {     /* join to upper nbr*/
        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) {      /* join to lower nbr */
        p->s.size += bp->s.size;
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;
    freep = p;
}

What I want to say is

void free(void *ap) {
/* ... */
   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;  /* freed block at start or end of arena */
/* ... */
}

this for loop is infinite. Because bp > p && bp < p->s.ptr is the same as 0 because each value of p and p->s.ptr is &base. And p = p->s.ptr does nothing. p points to base, base.s.ptr points to itself. So the value of bp > p && bp < p->s.ptr won't be changed.
Moreover, the pointer bp points to the header of memory received by sbrk(). Is it possible to compare bp with p?
I think the function free() only makes sense when we already got a valid memory block using malloc() and call it to free it. The function call free((void *)(up+1)); in morecore() and the body of free() doesn't match(I think).

Q1. Why is the for loop infinite?
Q2. Is it valid to compare bp with p in that for loop? If so, how and where is bp(which points to the memory allocated by sbrk()) placed?

Shouldn't `if (p >= s.ptr && ...` be `if (p >= **p->**s.ptr && `? — Olaf Dietsche, Jan 11 '21 at 14:48
@OlafDietsche Sorry, you're right. I edited that part. But the question and my thought is not affected. — op ol, Jan 11 '21 at 14:59
This particular code is extra-ordinarily bad even by K&R standards. I would strongly recommend to stop reading this book and forget that you ever saw this code. — Lundin, Jan 11 '21 at 15:12
@Lundin If the code is bad, I'll also enjoy it by parsing how it's bad. So, I want to hear you how you think about my question. — op ol, Jan 11 '21 at 15:17
@opol Go to the question mentioned by Lundin, skip Lundin's rant and the second answer. You will find, that the third answer describes the idea behind this `malloc()` and `free()` implementation pretty well. — Olaf Dietsche, Jan 11 '21 at 15:48
@OlafDietsche: Which answer is "third" may depend on how the user has them sorted. Could you link the specific one you have in mind? — Nate Eldredge, Jan 12 '21 at 00:16

score 0 · Answer 1 · answered Jan 12 '21 at 09:27

Q1. Why is the for loop infinite?

No, it's not infinite.

void free(void *ap) {
/* ... */
   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;  /* freed block at start or end of arena */
/* ... */
}

When base.s.ptr = &base and freep == &base, above code is the same as

void free(void *ap) {
/* ... */
   for (p = freep; !(0); p = p->s.ptr)
        if (1 && (1))
            break;  /* freed block at start or end of arena */
/* ... */
}

(I was confused with the meaning of || operator. I thought bp > p || bp < p->s.ptr should be the same as 0 when I asked the question.)

Q2. Is it valid to compare bp with p in that for loop? If so, how and where is bp(which points to the memory allocated by sbrk()) placed?

Yes, comparing those two is valid. sbrk() returns a previous program break value. So bp and p are comparable.

My question is based on wrong assumptions, so it's not notable. Rather reading all answers in [this link](https://stackoverflow.com/questions/13159564/explain-this-implementation-of-malloc-from-the-kr-book) will be helpful to understand more. I got an answer of Q2 from that link. — op ol, Jan 12 '21 at 09:50

K&R section 8.7 for loop in free()

1 Answers1