SEO

after reviewing ben hawkes's ruxcon slides, there's a few things we can do
to improve malloc.

to review, the issues:
pginfo and pgfree are allocated with imalloc. meaning, if the attacker
can overwrite the right size chunk, they can hit them. by default chunks
are returned in a deterministic order, so one should assume attacker can
control order.

pginfo for some sizes comes out of the page too, which is mostly safe,
except for possibility of overflow. anyway, fixing above fixed this.

besides possibility to damage malloc structures, the general order in
which memory is recycled is known and doesn't change.

diff time!

allocate pginfo and pgfree structures on the side, keep separate free
lists, and don't let them touch the dirty user memory. segregation good.

something i've thought about doing for a while but haven't implemented
until now is a delay buffer for free. keep a backlog of 16 pointers.
instead of freeing the pointer the user just gave back, free a random one
from the list. this disrupts things.

the two changes are independent, combined in one diff for convenience, but
easily separated.

works for me.

oh, and deleted 3 retarded __inline__s and made some pretty.

Index: malloc.c
================================================== =================
RCS file: /cvs/src/lib/libc/stdlib/malloc.c,v
retrieving revision 1.83
diff -u -r1.83 malloc.c
--- malloc.c 14 May 2006 19:53:40 -0000 1.83
+++ malloc.c 7 Oct 2006 21:49:28 -0000
@@ -75,6 +75,18 @@
#define malloc_pageshift (PGSHIFT)
#endif

+#ifndef malloc_minsize
+#define malloc_minsize 16UL
+#endif
+
+#if !defined(malloc_pagesize)
+#define malloc_pagesize (1UL<<malloc_pageshift)
+#endif
+
+/* How many bits per u_long in the bitmap */
+#define MALLOC_BITS (NBBY * sizeof(u_long))
+
+
/*
* No user serviceable parts behind this point.
*
@@ -87,12 +99,9 @@
u_short shift; /* How far to shift for this size chunks */
u_short free; /* How many free chunks */
u_short total; /* How many chunk */
- u_long bits[1];/* Which chunks are free */
+ u_long bits[(malloc_pagesize / malloc_minsize) / MALLOC_BITS];/* Which chunks are free */
};

-/* How many bits per u_long in the bitmap */
-#define MALLOC_BITS (NBBY * sizeof(u_long))
-
/*
* This structure describes a number of free pages.
*/
@@ -113,14 +122,6 @@
#define MALLOC_FOLLOW ((struct pginfo*) 3)
#define MALLOC_MAGIC ((struct pginfo*) 4)

-#ifndef malloc_minsize
-#define malloc_minsize 16UL
-#endif
-
-#if !defined(malloc_pagesize)
-#define malloc_pagesize (1UL<<malloc_pageshift)
-#endif
-
#if ((1UL<<malloc_pageshift) != malloc_pagesize)
#error "(1UL<<malloc_pageshift) != malloc_pagesize"
#endif
@@ -254,6 +255,66 @@
static void *irealloc(void *ptr, size_t size);
static void *malloc_bytes(size_t size);

+static struct pginfo *pginfo_list;
+
+static struct pgfree *pgfree_list;
+
+static struct pgfree *
+alloc_pgfree()
+{
+ struct pgfree *p;
+ int i;
+
+ if (pgfree_list == NULL) {
+ p = MMAP(malloc_pagesize);
+ if (!p)
+ return NULL;
+ for (i = 0; i < malloc_pagesize / sizeof(*p); i++) {
+ p[i].next = pgfree_list;
+ pgfree_list = &p[i];
+ }
+ }
+ p = pgfree_list;
+ pgfree_list = p->next;
+ memset(p, 0, sizeof *p);
+ return p;
+}
+
+static struct pginfo *
+alloc_pginfo()
+{
+ struct pginfo *p;
+ int i;
+
+ if (pginfo_list == NULL) {
+ p = MMAP(malloc_pagesize);
+ if (!p)
+ return NULL;
+ for (i = 0; i < malloc_pagesize / sizeof(*p); i++) {
+ p[i].next = pginfo_list;
+ pginfo_list = &p[i];
+ }
+ }
+ p = pginfo_list;
+ pginfo_list = p->next;
+ memset(p, 0, sizeof *p);
+ return p;
+}
+
+static void
+put_pgfree(struct pgfree *p)
+{
+ p->next = pgfree_list;
+ pgfree_list = p;
+}
+
+static void
+put_pginfo(struct pginfo *p)
+{
+ p->next = pginfo_list;
+ pginfo_list = p;
+}
+
/*
* Function for page directory lookup.
*/
@@ -764,12 +825,12 @@
static void *
malloc_pages(size_t size)
{
- void *p, *delay_free = NULL, *tp;
+ void *p, *tp;
int i;
struct pginfo **pd;
struct pdinfo *pi;
u_long pidx, index;
- struct pgfree *pf;
+ struct pgfree *pf, *delay_free = NULL;

size = pageround(size) + malloc_guard;

@@ -936,7 +997,7 @@
if (px == NULL)
px = delay_free;
else
- ifree(delay_free);
+ put_pgfree(delay_free);
}
return (p);
}
@@ -945,7 +1006,7 @@
* Allocate a page of fragments
*/

-static __inline__ int
+static int
malloc_make_chunks(int bits)
{
struct pginfo *bp, **pd;
@@ -955,17 +1016,13 @@
#endif /* MALLOC_EXTRA_SANITY */
void *pp;
long i, k;
- size_t l;

/* Allocate a new bucket */
- pp = malloc_pages((size_t) malloc_pagesize);
+ pp = malloc_pages((size_t)malloc_pagesize);
if (pp == NULL)
return (0);

/* Find length of admin structure */
- l = sizeof *bp - sizeof(u_long);
- l += sizeof(u_long) *
- (((malloc_pagesize >> bits) + MALLOC_BITS - 1) / MALLOC_BITS);

/* Don't waste more than two chunks on this */

@@ -975,14 +1032,10 @@
* pginfo page.
* --> Treat it like the big chunk alloc, get a second data page.
*/
- if (bits != 0 && (1UL << (bits)) <= l + l) {
- bp = (struct pginfo *) pp;
- } else {
- bp = (struct pginfo *) imalloc(l);
- if (bp == NULL) {
- ifree(pp);
- return (0);
- }
+ bp = alloc_pginfo();
+ if (bp == NULL) {
+ ifree(pp);
+ return (0);
}

/* memory protect the page allocated in the malloc(0) case */
@@ -998,7 +1051,7 @@
k = mprotect(pp, malloc_pagesize, PROT_NONE);
if (k < 0) {
ifree(pp);
- ifree(bp);
+ put_pginfo(bp);
return (0);
}
} else {
@@ -1019,18 +1072,6 @@
for (; i < k; i++)
bp->bits[i / MALLOC_BITS] |= 1UL << (i % MALLOC_BITS);

- k = (long)l;
- if (bp == bp->page) {
- /* Mark the ones we stole for ourselves */
- for (i = 0; k > 0; i++) {
- bp->bits[i / MALLOC_BITS] &= ~(1UL << (i % MALLOC_BITS));
- bp->free--;
- bp->total--;
- k -= (1 << bits);
- }
- }
- /* MALLOC_LOCK */
-
pdir_lookup(ptr2index(pp), &pi);
#ifdef MALLOC_EXTRA_SANITY
pidx = PI_IDX(ptr2index(pp));
@@ -1325,7 +1366,7 @@
/*
* Free a sequence of pages
*/
-static __inline__ void
+static void
free_pages(void *ptr, u_long index, struct pginfo * info)
{
u_long i, pidx, lidx;
@@ -1409,7 +1450,7 @@
mprotect(ptr, l, PROT_NONE);

/* Add to free-list. */
- if (px == NULL && (px = malloc_bytes(sizeof *px)) == NULL)
+ if (px == NULL && (px = alloc_pgfree()) == NULL)
goto not_return;
px->page = ptr;
px->pdir = spi;
@@ -1578,7 +1619,7 @@
/* XXX: We could realloc/shrink the pagedir here I guess. */
if (pf->size == 0) { /* Remove from free-list as well. */
if (px)
- ifree(px);
+ put_pgfree(px);
if ((px = pf->prev) != &free_list) {
if (pi == NULL && last_index == (index - 1)) {
if (spi == NULL) {
@@ -1592,7 +1633,7 @@
pdi_mod) - 1;
for (pi = spi, i = index;
pd[PI_OFF(i)] == MALLOC_NOT_MINE;
- i--)
+ i--) {
#ifdef MALLOC_EXTRA_SANITY
if (!PI_OFF(i)) {
pi = pi->prev;
@@ -1601,10 +1642,8 @@
pd = pi->base;
i = (PD_IDX(pi->dirnum) + 1) * pdi_mod;
}
-#else /* !MALLOC_EXTRA_SANITY */
- {
- }
#endif /* MALLOC_EXTRA_SANITY */
+ }
malloc_brk = index2ptr(i + 1);
}
last_index = i;
@@ -1622,7 +1661,7 @@
}
not_return:
if (pt != NULL)
- ifree(pt);
+ put_pgfree(pt);
}

/*
@@ -1630,7 +1669,7 @@
*/

/* ARGSUSED */
-static __inline__ void
+static void
free_bytes(void *ptr, u_long index, struct pginfo * info)
{
struct pginfo **mp, **pd;
@@ -1711,12 +1750,13 @@
if (info->size == 0)
mprotect(info->page, malloc_pagesize, PROT_READ | PROT_WRITE);

- vp = info->page; /* Order is important ! */
- if (vp != (void *) info)
- ifree(info);
+ vp = info->page;
+ put_pginfo(info);
ifree(vp);
}

+static void *ifree_buffer[16];
+
static void
ifree(void *ptr)
{
@@ -1726,6 +1766,8 @@
u_long pidx;
#endif /* MALLOC_EXTRA_SANITY */
struct pdinfo *pi;
+ void *tmpptr;
+ unsigned int tmpidx;

if (!malloc_started) {
wrtwarning("malloc() has never been called");
@@ -1736,7 +1778,7 @@
return;

if (malloc_ptrguard && PTR_ALIGNED(ptr))
- ptr = (char *) ptr - PTR_GAP;
+ ptr = (char *)ptr - PTR_GAP;

index = ptr2index(ptr);

@@ -1750,6 +1792,16 @@
wrtwarning("ifree: junk pointer, too high to make sense");
return;
}
+ /* delay return, returning a random something from before instead */
+ tmpidx = arc4random() % 16;
+ tmpptr = ifree_buffer[tmpidx];
+ ifree_buffer[tmpidx] = ptr;
+ ptr = tmpptr;
+ if (!ptr)
+ return;
+ index = ptr2index(ptr);
+
+
pdir_lookup(index, &pi);
#ifdef MALLOC_EXTRA_SANITY
pidx = PI_IDX(index);
@@ -1773,7 +1825,7 @@

/* does not matter if malloc_bytes fails */
if (px == NULL)
- px = malloc_bytes(sizeof *px);
+ px = alloc_pgfree();

return;
}


--
die energie aus fleisch und blut deine sprache und die ganze wut
deine gefuehle die du lebst und dein herz fuehl wie es bebt
zeitbombe! sie tickt in dir zeitbombe! sie explodiert in deinem kopf
- girls under glass