#include <stdio.h>
#include <stdint.h>
#include <unistd.h>
static char *start;
static const int head = sizeof(uintptr_t);
static void dump() {
char *p, *last = (char *)sbrk(0), *next;
for (p = start; p && p < last; p = next) {
uintptr_t sz = *(uintptr_t *)p;
next = p + head + (sz & ~1);
printf("* %p, %p - %p: %s %d\n", p, p + head, next - 1, sz & 1 ? "used" : "free", sz & ~1);
}
}
void *mymalloc(uintptr_t size) {
char *p, *last = (char *)sbrk(0), *next;
if (!start) start = last;
size = (size + head - 1) & ~(head - 1);
for (p = start; p < last; p = next) {
uintptr_t sz = *(uintptr_t *)p;
next = p + head + (sz & ~1);
if (!(sz & 1) && sz >= size) {
if (sz > size)
*(uintptr_t *)(p + head + size) = sz - size - head;
break;
}
}
if (p >= last) p = (char *)sbrk(head + size);
*(uintptr_t *)p = size | 1;
printf("mymalloc(%d) -> %p\n", size
, p
+ head
); dump();
return p + head;
}
void myfree(void *ptr) {
char *p, *last = (char *)sbrk(0), *next;
uintptr_t *h;
if (!ptr || !start) return;
h = (uintptr_t *)(((char *)ptr) - head);
for (p = start; p < last; p = next) {
uintptr_t sz = *(uintptr_t *)p;
if (!(sz & 1) && p + head + sz == (char *)h) {
sz += head + (*h & ~1);
h = (uintptr_t *)p;
}
sz &= ~1;
next = p + head + sz;
if (p == (char *)h) {
if (next < last) {
int nextsz = *(uintptr_t *)next;
if (!(nextsz & 1)) sz += head + nextsz;
}
if (p + head + sz >= last) brk(p); else *h = sz;
dump();
return;
}
}
}
int main(void) {
void *p[4];
dump();
p[0] = mymalloc(8);
p[1] = mymalloc(16);
p[2] = mymalloc(8);
myfree(p[1]);
p[1] = mymalloc(8);
p[3] = mymalloc(8);
myfree(p[3]);
myfree(p[1]);
myfree(p[2]);
myfree(p[0]);
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRpbnQuaD4KI2luY2x1ZGUgPHVuaXN0ZC5oPgoKc3RhdGljIGNoYXIgKnN0YXJ0OwpzdGF0aWMgY29uc3QgaW50IGhlYWQgPSBzaXplb2YodWludHB0cl90KTsKCnN0YXRpYyB2b2lkIGR1bXAoKSB7CiAgICBjaGFyICpwLCAqbGFzdCA9IChjaGFyICopc2JyaygwKSwgKm5leHQ7CiAgICBmb3IgKHAgPSBzdGFydDsgcCAmJiBwIDwgbGFzdDsgcCA9IG5leHQpIHsKICAgICAgICB1aW50cHRyX3Qgc3ogPSAqKHVpbnRwdHJfdCAqKXA7CiAgICAgICAgbmV4dCA9IHAgKyBoZWFkICsgKHN6ICYgfjEpOwogICAgICAgIHByaW50ZigiKiAlcCwgJXAgLSAlcDogJXMgJWRcbiIsCiAgICAgICAgICAgIHAsIHAgKyBoZWFkLCBuZXh0IC0gMSwgc3ogJiAxID8gInVzZWQiIDogImZyZWUiLCBzeiAmIH4xKTsKICAgIH0KICAgIHByaW50ZigiPT0lcFxuIiwgbGFzdCk7Cn0KCnZvaWQgKm15bWFsbG9jKHVpbnRwdHJfdCBzaXplKSB7CiAgICBjaGFyICpwLCAqbGFzdCA9IChjaGFyICopc2JyaygwKSwgKm5leHQ7CiAgICBpZiAoIXN0YXJ0KSBzdGFydCA9IGxhc3Q7CiAgICBzaXplID0gKHNpemUgKyBoZWFkIC0gMSkgJiB+KGhlYWQgLSAxKTsKICAgIGZvciAocCA9IHN0YXJ0OyBwIDwgbGFzdDsgcCA9IG5leHQpIHsKICAgICAgICB1aW50cHRyX3Qgc3ogPSAqKHVpbnRwdHJfdCAqKXA7CiAgICAgICAgbmV4dCA9IHAgKyBoZWFkICsgKHN6ICYgfjEpOwogICAgICAgIGlmICghKHN6ICYgMSkgJiYgc3ogPj0gc2l6ZSkgewogICAgICAgICAgICBpZiAoc3ogPiBzaXplKQogICAgICAgICAgICAgICAgKih1aW50cHRyX3QgKikocCArIGhlYWQgKyBzaXplKSA9IHN6IC0gc2l6ZSAtIGhlYWQ7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KICAgIH0KICAgIGlmIChwID49IGxhc3QpIHAgPSAoY2hhciAqKXNicmsoaGVhZCArIHNpemUpOwogICAgKih1aW50cHRyX3QgKilwID0gc2l6ZSB8IDE7CiAgICBwcmludGYoIm15bWFsbG9jKCVkKSAtPiAlcFxuIiwgc2l6ZSwgcCArIGhlYWQpOwogICAgZHVtcCgpOwogICAgcmV0dXJuIHAgKyBoZWFkOwp9Cgp2b2lkIG15ZnJlZSh2b2lkICpwdHIpIHsKICAgIGNoYXIgKnAsICpsYXN0ID0gKGNoYXIgKilzYnJrKDApLCAqbmV4dDsKICAgIHVpbnRwdHJfdCAqaDsKICAgIHByaW50ZigibXlmcmVlKCVwKVxuIiwgcHRyKTsKICAgIGlmICghcHRyIHx8ICFzdGFydCkgcmV0dXJuOwogICAgaCA9ICh1aW50cHRyX3QgKikoKChjaGFyICopcHRyKSAtIGhlYWQpOwogICAgZm9yIChwID0gc3RhcnQ7IHAgPCBsYXN0OyBwID0gbmV4dCkgewogICAgICAgIHVpbnRwdHJfdCBzeiA9ICoodWludHB0cl90ICopcDsKICAgICAgICBpZiAoIShzeiAmIDEpICYmIHAgKyBoZWFkICsgc3ogPT0gKGNoYXIgKiloKSB7CiAgICAgICAgICAgIHN6ICs9IGhlYWQgKyAoKmggJiB+MSk7CiAgICAgICAgICAgIGggPSAodWludHB0cl90ICopcDsKICAgICAgICB9CiAgICAgICAgc3ogJj0gfjE7CiAgICAgICAgbmV4dCA9IHAgKyBoZWFkICsgc3o7CiAgICAgICAgaWYgKHAgPT0gKGNoYXIgKiloKSB7CiAgICAgICAgICAgIGlmIChuZXh0IDwgbGFzdCkgewogICAgICAgICAgICAgICAgaW50IG5leHRzeiA9ICoodWludHB0cl90ICopbmV4dDsKICAgICAgICAgICAgICAgIGlmICghKG5leHRzeiAmIDEpKSBzeiArPSBoZWFkICsgbmV4dHN6OwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmIChwICsgaGVhZCArIHN6ID49IGxhc3QpIGJyayhwKTsgZWxzZSAqaCA9IHN6OwogICAgICAgICAgICBkdW1wKCk7CiAgICAgICAgICAgIHJldHVybjsKICAgICAgICB9CiAgICB9Cn0KCmludCBtYWluKHZvaWQpIHsKICAgIHZvaWQgKnBbNF07CiAgICBkdW1wKCk7CiAgICBwWzBdID0gbXltYWxsb2MoOCk7CiAgICBwWzFdID0gbXltYWxsb2MoMTYpOwogICAgcFsyXSA9IG15bWFsbG9jKDgpOwogICAgbXlmcmVlKHBbMV0pOwogICAgcFsxXSA9IG15bWFsbG9jKDgpOwogICAgcFszXSA9IG15bWFsbG9jKDgpOwogICAgbXlmcmVlKHBbM10pOwogICAgbXlmcmVlKHBbMV0pOwogICAgbXlmcmVlKHBbMl0pOwogICAgbXlmcmVlKHBbMF0pOwogICAgcmV0dXJuIDA7Cn0K
==0x8581000
mymalloc(8) -> 0x8581004
* 0x8581000, 0x8581004 - 0x858100b: used 8
==0x858100c
mymalloc(16) -> 0x8581010
* 0x8581000, 0x8581004 - 0x858100b: used 8
* 0x858100c, 0x8581010 - 0x858101f: used 16
==0x8581020
mymalloc(8) -> 0x8581024
* 0x8581000, 0x8581004 - 0x858100b: used 8
* 0x858100c, 0x8581010 - 0x858101f: used 16
* 0x8581020, 0x8581024 - 0x858102b: used 8
==0x858102c
myfree(0x8581010)
* 0x8581000, 0x8581004 - 0x858100b: used 8
* 0x858100c, 0x8581010 - 0x858101f: free 16
* 0x8581020, 0x8581024 - 0x858102b: used 8
==0x858102c
mymalloc(8) -> 0x8581010
* 0x8581000, 0x8581004 - 0x858100b: used 8
* 0x858100c, 0x8581010 - 0x8581017: used 8
* 0x8581018, 0x858101c - 0x858101f: free 4
* 0x8581020, 0x8581024 - 0x858102b: used 8
==0x858102c
mymalloc(8) -> 0x8581030
* 0x8581000, 0x8581004 - 0x858100b: used 8
* 0x858100c, 0x8581010 - 0x8581017: used 8
* 0x8581018, 0x858101c - 0x858101f: free 4
* 0x8581020, 0x8581024 - 0x858102b: used 8
* 0x858102c, 0x8581030 - 0x8581037: used 8
==0x8581038
myfree(0x8581030)
* 0x8581000, 0x8581004 - 0x858100b: used 8
* 0x858100c, 0x8581010 - 0x8581017: used 8
* 0x8581018, 0x858101c - 0x858101f: free 4
* 0x8581020, 0x8581024 - 0x858102b: used 8
==0x858102c
myfree(0x8581010)
* 0x8581000, 0x8581004 - 0x858100b: used 8
* 0x858100c, 0x8581010 - 0x858101f: free 16
* 0x8581020, 0x8581024 - 0x858102b: used 8
==0x858102c
myfree(0x8581024)
* 0x8581000, 0x8581004 - 0x858100b: used 8
==0x858100c
myfree(0x8581004)
==0x8581000