В 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())?
if (p >= s.ptr && ...
не должно бытьif (p >= **p->**s.ptr &&
? - person Olaf Dietsche   schedule 11.01.2021malloc()
иfree()
. - person Olaf Dietsche   schedule 11.01.2021