K&R раздел 8.7 для цикла в free()

В K&R(2nd), раздел 8.7, я думаю, что есть неожиданный бесконечный цикл for в free(), и его тестовая часть кажется неправильной.
Я вставил четыре // комментария. У malloc() есть один, у morecore() есть другой, а у free() есть остальные.

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;
}

Я хочу сказать,

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 */
/* ... */
}

этот цикл for бесконечен. Поскольку bp > p && bp < p->s.ptr совпадает с 0, потому что каждое значение p и p->s.ptr равно &base. А p = p->s.ptr ничего не делает. p указывает на base, base.s.ptr указывает на себя. Таким образом, значение bp > p && bp < p->s.ptr не изменится.
Более того, указатель bp указывает на заголовок памяти, полученный sbrk(). Можно ли сравнить bp с p?
Я думаю, что функция free() имеет смысл только тогда, когда мы уже получили действительный блок памяти с помощью malloc() и вызываем его для его освобождения. Вызов функции free((void *)(up+1)); в morecore() и тело функции free() не совпадают (я так думаю).

Q1. Почему цикл for бесконечен?
Q2. Можно ли сравнивать bp с p в этом цикле for? Если да, то как и где находится bp (указывающий на память, выделенную sbrk())?


person op ol    schedule 11.01.2021    source источник
comment
Разве if (p >= s.ptr && ... не должно быть if (p >= **p->**s.ptr && ?   -  person Olaf Dietsche    schedule 11.01.2021
comment
@OlafDietsche Извините, вы правы. Я отредактировал эту часть. Но вопрос и мою мысль это не затронуло.   -  person op ol    schedule 11.01.2021
comment
Этот конкретный код чрезвычайно плох даже по стандартам K&R. Я настоятельно рекомендую прекратить читать эту книгу и забыть, что вы когда-либо видели этот код.   -  person Lundin    schedule 11.01.2021
comment
@Lundin Если код плохой, мне также понравится, разбирая, насколько он плохой. Итак, я хочу услышать, что вы думаете о моем вопросе.   -  person op ol    schedule 11.01.2021
comment
@opol Перейдите к вопросу, упомянутому Лундином, пропустите разглагольствования Лундина и второй ответ. Вы обнаружите, что третий ответ довольно хорошо описывает идею этой реализации malloc() и free().   -  person Olaf Dietsche    schedule 11.01.2021
comment
@OlafDietsche: Какой ответ является третьим, может зависеть от того, как пользователь отсортировал их. Не могли бы вы связать конкретный, который вы имеете в виду?   -  person Nate Eldredge    schedule 12.01.2021
comment
Плохо, извините: stackoverflow.com/a/46291725/1741542   -  person Olaf Dietsche    schedule 12.01.2021


Ответы (1)


Q1. Почему цикл for бесконечен?

Нет, это не бесконечность.

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 */
/* ... */
}

Когда base.s.ptr = &base и freep == &base, приведенный выше код такой же, как

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

(Меня смутило значение оператора ||. Я думал, что bp > p || bp < p->s.ptr должно совпадать с 0, когда задавал вопрос.)

Q2. Можно ли сравнивать bp с p в этом цикле for? Если да, то как и где находится bp (указывающий на память, выделенную sbrk())?

Да, сравнение этих двух корректно. sbrk() возвращает предыдущее значение прерывания программы. Итак, bp и p сопоставимы.

person op ol    schedule 12.01.2021
comment
Мой вопрос основан на неверных предположениях, поэтому он не примечателен. Скорее будет полезно прочитать все ответы в этой ссылке чтобы понять больше. Я получил ответ Q2 по этой ссылке. - person op ol; 12.01.2021