Hi,
The basic idea is simple: one of the reasons the recent sshd bug is
potentially exploitable is that a (erroneously) freed malloc chunk
gets re-used in a different role. My malloc has power of two chunk
sizes and so one page of chunks holds many different types of
allocations. Userland malloc has no knowledge of types, we only know
about sizes. So I changed that to use finer-grained chunk sizes.
Originally I thought it would be a *lot* of work, but it's not too
bad: a couple of hours of thinking and a couple of hours coding, which
mostly consisted of hunting for silent assumptions that chunk sizes
are a power of two.
I suspect this is not the final diff, as there is some performance
impact. In particular, sparc64 seems sensitive to these changes. I'm
still investigating why but I wanted to share the current work in
progress anyway.
Yuu can help by testing this.
Thanks,
-Otto
Index: stdlib/malloc.c
===================================================================
RCS file: /home/cvs/src/lib/libc/stdlib/malloc.c,v
retrieving revision 1.276
diff -u -p -r1.276 malloc.c
--- stdlib/malloc.c 27 Dec 2022 17:31:09 -0000 1.276
+++ stdlib/malloc.c 20 Feb 2023 07:33:29 -0000
@@ -67,6 +67,11 @@
#define MALLOC_CHUNK_LISTS 4
#define CHUNK_CHECK_LENGTH 32
+#define B2SIZE(b) ((b) * MALLOC_MINSIZE)
+#define B2ALLOC(b) ((b) == 0 ? MALLOC_MINSIZE : \
+ (b) * MALLOC_MINSIZE)
+#define BUCKETS (MALLOC_MAXCHUNK / MALLOC_MINSIZE)
+
/*
* We move allocations between half a page and a whole page towards the end,
* subject to alignment constraints. This is the extra headroom we allow.
@@ -144,9 +149,9 @@ struct dir_info {
int mutex;
int malloc_mt; /* multi-threaded mode? */
/* lists of free chunk info structs */
- struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1];
+ struct chunk_head chunk_info_list[BUCKETS + 1];
/* lists of chunks with free slots */
- struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1][MALLOC_CHUNK_LISTS];
+ struct chunk_head chunk_dir[BUCKETS + 1][MALLOC_CHUNK_LISTS];
/* delayed free chunk slots */
void *delayed_chunks[MALLOC_DELAYED_CHUNK_MASK + 1];
u_char rbytes[32]; /* random bytes */
@@ -195,8 +200,7 @@ struct chunk_info {
LIST_ENTRY(chunk_info) entries;
void *page; /* pointer to the page */
u_short canary;
- u_short size; /* size of this page's chunks */
- u_short shift; /* how far to shift for this size */
+ u_short bucket;
u_short free; /* how many free chunks */
u_short total; /* how many chunks */
u_short offset; /* requested size table offset */
@@ -247,11 +251,11 @@ static void malloc_exit(void);
#endif
/* low bits of r->p determine size: 0 means >= page size and r->size holding
- * real size, otherwise low bits are a shift count, or 1 for malloc(0)
+ * real size, otherwise low bits is the bucket + 1
*/
#define REALSIZE(sz, r) \
(sz) = (uintptr_t)(r)->p & MALLOC_PAGEMASK, \
- (sz) = ((sz) == 0 ? (r)->size : ((sz) == 1 ? 0 : (1 << ((sz)-1))))
+ (sz) = ((sz) == 0 ? (r)->size : B2SIZE((sz) - 1))
static inline void
_MALLOC_LEAVE(struct dir_info *d)
@@ -502,7 +506,7 @@ omalloc_poolinit(struct dir_info *d, int
d->r = NULL;
d->rbytesused = sizeof(d->rbytes);
d->regions_free = d->regions_total = 0;
- for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
+ for (i = 0; i <= BUCKETS; i++) {
LIST_INIT(&d->chunk_info_list[i]);
for (j = 0; j < MALLOC_CHUNK_LISTS; j++)
LIST_INIT(&d->chunk_dir[i][j]);
@@ -883,21 +887,13 @@ map(struct dir_info *d, size_t sz, int z
}
static void
-init_chunk_info(struct dir_info *d, struct chunk_info *p, int bits)
+init_chunk_info(struct dir_info *d, struct chunk_info *p, u_int bucket)
{
- int i;
+ u_int i;
- if (bits == 0) {
- p->shift = MALLOC_MINSHIFT;
- p->total = p->free = MALLOC_PAGESIZE >> p->shift;
- p->size = 0;
- p->offset = 0xdead;
- } else {
- p->shift = bits;
- p->total = p->free = MALLOC_PAGESIZE >> p->shift;
- p->size = 1U << bits;
- p->offset = howmany(p->total, MALLOC_BITS);
- }
+ p->bucket = bucket;
+ p->total = p->free = MALLOC_PAGESIZE / B2ALLOC(bucket);
+ p->offset = bucket == 0 ? 0xdead : howmany(p->total, MALLOC_BITS);
p->canary = (u_short)d->canary1;
/* set all valid bits in the bitmap */
@@ -907,18 +903,15 @@ init_chunk_info(struct dir_info *d, stru
}
static struct chunk_info *
-alloc_chunk_info(struct dir_info *d, int bits)
+alloc_chunk_info(struct dir_info *d, u_int bucket)
{
struct chunk_info *p;
- if (LIST_EMPTY(&d->chunk_info_list[bits])) {
+ if (LIST_EMPTY(&d->chunk_info_list[bucket])) {
size_t size, count, i;
char *q;
- if (bits == 0)
- count = MALLOC_PAGESIZE / MALLOC_MINSIZE;
- else
- count = MALLOC_PAGESIZE >> bits;
+ count = MALLOC_PAGESIZE / B2ALLOC(bucket);
size = howmany(count, MALLOC_BITS);
size = sizeof(struct chunk_info) + (size - 1) * sizeof(u_short);
@@ -935,13 +928,13 @@ alloc_chunk_info(struct dir_info *d, int
for (i = 0; i < count; i++, q += size) {
p = (struct chunk_info *)q;
- LIST_INSERT_HEAD(&d->chunk_info_list[bits], p, entries);
+ LIST_INSERT_HEAD(&d->chunk_info_list[bucket], p,
entries);
}
}
- p = LIST_FIRST(&d->chunk_info_list[bits]);
+ p = LIST_FIRST(&d->chunk_info_list[bucket]);
LIST_REMOVE(p, entries);
- if (p->shift == 0)
- init_chunk_info(d, p, bits);
+ if (p->total == 0)
+ init_chunk_info(d, p, bucket);
return p;
}
@@ -949,7 +942,7 @@ alloc_chunk_info(struct dir_info *d, int
* Allocate a page of chunks
*/
static struct chunk_info *
-omalloc_make_chunks(struct dir_info *d, int bits, int listnum)
+omalloc_make_chunks(struct dir_info *d, u_int bucket, u_int listnum)
{
struct chunk_info *bp;
void *pp;
@@ -960,18 +953,18 @@ omalloc_make_chunks(struct dir_info *d,
return NULL;
/* memory protect the page allocated in the malloc(0) case */
- if (bits == 0 && mprotect(pp, MALLOC_PAGESIZE, PROT_NONE) == -1)
+ if (bucket == 0 && mprotect(pp, MALLOC_PAGESIZE, PROT_NONE) == -1)
goto err;
- bp = alloc_chunk_info(d, bits);
+ bp = alloc_chunk_info(d, bucket);
if (bp == NULL)
goto err;
bp->page = pp;
- if (insert(d, (void *)((uintptr_t)pp | (bits + 1)), (uintptr_t)bp,
+ if (insert(d, (void *)((uintptr_t)pp | (bucket + 1)), (uintptr_t)bp,
NULL))
goto err;
- LIST_INSERT_HEAD(&d->chunk_dir[bits][listnum], bp, entries);
+ LIST_INSERT_HEAD(&d->chunk_dir[bucket][listnum], bp, entries);
return bp;
err:
@@ -979,23 +972,16 @@ err:
return NULL;
}
-static int
-find_chunksize(size_t size)
+static u_short
+find_bucket(size_t size)
{
- int r;
-
/* malloc(0) is special */
if (size == 0)
return 0;
if (size < MALLOC_MINSIZE)
size = MALLOC_MINSIZE;
- size--;
-
- r = MALLOC_MINSHIFT;
- while (size >> r)
- r++;
- return r;
+ return howmany(size, MALLOC_MINSIZE);
}
static void
@@ -1014,8 +1000,7 @@ fill_canary(char *ptr, size_t sz, size_t
static void *
malloc_bytes(struct dir_info *d, size_t size, void *f)
{
- u_int i, r;
- int j, listnum;
+ u_int i, r, bucket, listnum;
size_t k;
u_short *lp;
struct chunk_info *bp;
@@ -1025,13 +1010,14 @@ malloc_bytes(struct dir_info *d, size_t
d->canary1 != ~d->canary2)
wrterror(d, "internal struct corrupt");
- j = find_chunksize(size);
+ bucket = find_bucket(size);
r = ((u_int)getrbyte(d) << 8) | getrbyte(d);
listnum = r % MALLOC_CHUNK_LISTS;
+
/* If it's empty, make a page more of that size chunks */
- if ((bp = LIST_FIRST(&d->chunk_dir[j][listnum])) == NULL) {
- bp = omalloc_make_chunks(d, j, listnum);
+ if ((bp = LIST_FIRST(&d->chunk_dir[bucket][listnum])) == NULL) {
+ bp = omalloc_make_chunks(d, bucket, listnum);
if (bp == NULL)
return NULL;
}
@@ -1039,12 +1025,12 @@ malloc_bytes(struct dir_info *d, size_t
if (bp->canary != (u_short)d->canary1)
wrterror(d, "chunk info corrupted");
- i = (r / MALLOC_CHUNK_LISTS) & (bp->total - 1);
+ i = (r / MALLOC_CHUNK_LISTS) % bp->total;
- /* start somewhere in a short */
+ /* potentially start somewhere in a short */
lp = &bp->bits[i / MALLOC_BITS];
if (*lp) {
- j = i % MALLOC_BITS;
+ int j = i % MALLOC_BITS; /* j must be signed */
k = ffs(*lp >> j);
if (k != 0) {
k += j - 1;
@@ -1054,7 +1040,7 @@ malloc_bytes(struct dir_info *d, size_t
/* no bit halfway, go to next full short */
i /= MALLOC_BITS;
for (;;) {
- if (++i >= bp->total / MALLOC_BITS)
+ if (++i >= howmany(bp->total, MALLOC_BITS))
i = 0;
lp = &bp->bits[i];
if (*lp) {
@@ -1082,14 +1068,14 @@ found:
if (mopts.chunk_canaries && size > 0)
bp->bits[bp->offset + k] = size;
- k <<= bp->shift;
+ k *= B2ALLOC(bp->bucket);
p = (char *)bp->page + k;
- if (bp->size > 0) {
+ if (bp->bucket > 0) {
if (d->malloc_junk == 2)
- memset(p, SOME_JUNK, bp->size);
+ memset(p, SOME_JUNK, B2SIZE(bp->bucket));
else if (mopts.chunk_canaries)
- fill_canary(p, size, bp->size);
+ fill_canary(p, size, B2SIZE(bp->bucket));
}
return p;
}
@@ -1124,16 +1110,16 @@ find_chunknum(struct dir_info *d, struct
wrterror(d, "chunk info corrupted");
/* Find the chunk number on the page */
- chunknum = ((uintptr_t)ptr & MALLOC_PAGEMASK) >> info->shift;
+ chunknum = ((uintptr_t)ptr & MALLOC_PAGEMASK) / B2ALLOC(info->bucket);
- if ((uintptr_t)ptr & ((1U << (info->shift)) - 1))
+ if ((uintptr_t)ptr & (MALLOC_MINSIZE - 1))
wrterror(d, "modified chunk-pointer %p", ptr);
if (info->bits[chunknum / MALLOC_BITS] &
(1U << (chunknum % MALLOC_BITS)))
wrterror(d, "chunk is already free %p", ptr);
- if (check && info->size > 0) {
+ if (check && info->bucket > 0) {
validate_canary(d, ptr, info->bits[info->offset + chunknum],
- info->size);
+ B2SIZE(info->bucket));
}
return chunknum;
}
@@ -1147,7 +1133,7 @@ free_bytes(struct dir_info *d, struct re
struct chunk_head *mp;
struct chunk_info *info;
uint32_t chunknum;
- int listnum;
+ uint32_t listnum;
info = (struct chunk_info *)r->size;
chunknum = find_chunknum(d, info, ptr, 0);
@@ -1158,11 +1144,7 @@ free_bytes(struct dir_info *d, struct re
if (info->free == 1) {
/* Page became non-full */
listnum = getrbyte(d) % MALLOC_CHUNK_LISTS;
- if (info->size != 0)
- mp = &d->chunk_dir[info->shift][listnum];
- else
- mp = &d->chunk_dir[0][listnum];
-
+ mp = &d->chunk_dir[info->bucket][listnum];
LIST_INSERT_HEAD(mp, info, entries);
return;
}
@@ -1172,15 +1154,12 @@ free_bytes(struct dir_info *d, struct re
LIST_REMOVE(info, entries);
- if (info->size == 0 && !mopts.malloc_freeunmap)
+ if (info->bucket == 0 && !mopts.malloc_freeunmap)
mprotect(info->page, MALLOC_PAGESIZE, PROT_READ | PROT_WRITE);
unmap(d, info->page, MALLOC_PAGESIZE, 0);
delete(d, r);
- if (info->size != 0)
- mp = &d->chunk_info_list[info->shift];
- else
- mp = &d->chunk_info_list[0];
+ mp = &d->chunk_info_list[info->bucket];
LIST_INSERT_HEAD(mp, info, entries);
}
@@ -1517,7 +1496,7 @@ ofree(struct dir_info **argpool, void *p
} else {
/* Validate and optionally canary check */
struct chunk_info *info = (struct chunk_info *)r->size;
- if (info->size != sz)
+ if (B2SIZE(info->bucket) != sz)
wrterror(pool, "internal struct corrupt");
find_chunknum(pool, info, p, mopts.chunk_canaries);
if (!clear) {
@@ -1754,13 +1733,13 @@ orealloc(struct dir_info **argpool, void
}
if (oldsz <= MALLOC_MAXCHUNK && oldsz > 0 &&
newsz <= MALLOC_MAXCHUNK && newsz > 0 &&
- 1 << find_chunksize(newsz) == oldsz && !forced) {
+ !forced && find_bucket(newsz) == find_bucket(oldsz)) {
/* do not reallocate if new size fits good in existing chunk */
if (pool->malloc_junk == 2)
memset((char *)p + newsz, SOME_JUNK, oldsz - newsz);
if (mopts.chunk_canaries) {
info->bits[info->offset + chunknum] = newsz;
- fill_canary(p, newsz, info->size);
+ fill_canary(p, newsz, B2SIZE(info->bucket));
}
STATS_SETF(r, f);
ret = p;
@@ -2052,14 +2031,20 @@ omemalign(struct dir_info *pool, size_t
if (sz > MALLOC_MAXCHUNK && sz < MALLOC_PAGESIZE)
sz = MALLOC_PAGESIZE;
if (alignment <= MALLOC_PAGESIZE) {
+ size_t pof2;
/*
- * max(size, alignment) is enough to assure the requested
- * alignment, since the allocator always allocates
- * power-of-two blocks.
+ * 2^max(size, alignment) is enough to assure the requested
+ * alignment. Large regions are always page aligned
*/
if (sz < alignment)
sz = alignment;
- return omalloc(pool, sz, zero_fill, f);
+ if (sz < MALLOC_PAGESIZE) {
+ pof2 = 1 << MALLOC_MINSIZE;
+ while (pof2 < sz)
+ pof2 <<= 1;
+ } else
+ pof2 = sz;
+ return omalloc(pool, pof2, zero_fill, f);
}
if (sz >= SIZE_MAX - mopts.malloc_guard - MALLOC_PAGESIZE) {
@@ -2256,15 +2241,16 @@ static void
dump_chunk(int fd, struct chunk_info *p, void *f, int fromfreelist)
{
while (p != NULL) {
- dprintf(fd, "chunk %18p %18p %4d %d/%d\n",
+ dprintf(fd, "chunk %18p %18p %4zu %d/%d\n",
p->page, ((p->bits[0] & 1) ? NULL : f),
- p->size, p->free, p->total);
+ B2SIZE(p->bucket), p->free, p->total);
if (!fromfreelist) {
+ size_t sz = B2SIZE(p->bucket);
if (p->bits[0] & 1)
- putleakinfo(NULL, p->size, p->total - p->free);
+ putleakinfo(NULL, sz, p->total - p->free);
else {
- putleakinfo(f, p->size, 1);
- putleakinfo(NULL, p->size,
+ putleakinfo(f, sz, 1);
+ putleakinfo(NULL, sz,
p->total - p->free - 1);
}
break;
@@ -2282,7 +2268,7 @@ dump_free_chunk_info(int fd, struct dir_
struct chunk_info *p;
dprintf(fd, "Free chunk structs:\n");
- for (i = 0; i <= MALLOC_MAXSHIFT; i++) {
+ for (i = 0; i <= BUCKETS; i++) {
count = 0;
LIST_FOREACH(p, &d->chunk_info_list[i], entries)
count++;
@@ -2290,7 +2276,10 @@ dump_free_chunk_info(int fd, struct dir_
p = LIST_FIRST(&d->chunk_dir[i][j]);
if (p == NULL && count == 0)
continue;
- dprintf(fd, "%2d) %3d ", i, count);
+ if (j == 0)
+ dprintf(fd, "%3d) %3d ", i, count);
+ else
+ dprintf(fd, " ");
if (p != NULL)
dump_chunk(fd, p, NULL, 1);
else
