What's better than a freelist? Four freelists!
For each chunk size, pick one of four freelists at random. This
scatters allocations about some more and eliminates the guarantee that
consecutive allocations will always be on the same page.
Technically, there is no bound to how much memory will be used, but in
practice, it will be 3 pages per bucket. (Worst case would be you
somehow always allocate from one list and always free to a different
one, in which case the freed pages leak. In practice, this is so
unlikely I don't think it's worth writing code to handle.)
Index: malloc.c
===
RCS file: /cvs/src/lib/libc/stdlib/malloc.c,v
retrieving revision 1.159
diff -u -p -r1.159 malloc.c
--- malloc.c1 May 2014 04:08:13 - 1.159
+++ malloc.c1 May 2014 04:30:50 -
@@ -64,6 +64,7 @@
#define MALLOC_DELAYED_CHUNK_MASK 15
#define MALLOC_INITIAL_REGIONS 512
#define MALLOC_DEFAULT_CACHE 64
+#defineMALLOC_CHUNK_LISTS 4
/*
* When the P option is active, we move allocations between half a page
@@ -110,7 +111,7 @@ struct dir_info {
/* lists of free chunk info structs */
struct chunk_head chunk_info_list[MALLOC_MAXSHIFT + 1];
/* lists of chunks with free slots */
- struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1];
+ struct chunk_head chunk_dir[MALLOC_MAXSHIFT + 1][MALLOC_CHUNK_LISTS];
size_t free_regions_size; /* free pages cached */
/* free pages cache */
struct region_info free_regions[MALLOC_MAXCACHE];
@@ -621,7 +622,8 @@ omalloc_init(struct dir_info **dp)
}
for (i = 0; i = MALLOC_MAXSHIFT; i++) {
LIST_INIT(d-chunk_info_list[i]);
- LIST_INIT(d-chunk_dir[i]);
+ for (j = 0; j MALLOC_CHUNK_LISTS; j++)
+ LIST_INIT(d-chunk_dir[i][j]);
}
malloc_used += regioninfo_size;
d-canary1 = mopts.malloc_canary ^ (u_int32_t)(uintptr_t)d;
@@ -816,7 +818,7 @@ delete(struct dir_info *d, struct region
* Allocate a page of chunks
*/
static struct chunk_info *
-omalloc_make_chunks(struct dir_info *d, int bits)
+omalloc_make_chunks(struct dir_info *d, int bits, int listnum)
{
struct chunk_info *bp;
void*pp;
@@ -867,7 +869,7 @@ omalloc_make_chunks(struct dir_info *d,
for (; i k; i++)
bp-bits[i / MALLOC_BITS] |= (u_short)1U (i % MALLOC_BITS);
- LIST_INSERT_HEAD(d-chunk_dir[bits], bp, entries);
+ LIST_INSERT_HEAD(d-chunk_dir[bits][listnum], bp, entries);
bits++;
if ((uintptr_t)pp bits)
@@ -884,7 +886,7 @@ omalloc_make_chunks(struct dir_info *d,
static void *
malloc_bytes(struct dir_info *d, size_t size, void *f)
{
- int i, j;
+ int i, j, listnum;
size_t k;
u_short u, *lp;
struct chunk_info *bp;
@@ -907,13 +909,13 @@ malloc_bytes(struct dir_info *d, size_t
j++;
}
+ listnum = getrbyte() % MALLOC_CHUNK_LISTS;
/* If it's empty, make a page more of that size chunks */
- if (LIST_EMPTY(d-chunk_dir[j])) {
- bp = omalloc_make_chunks(d, j);
+ if ((bp = LIST_FIRST(d-chunk_dir[j][listnum])) == NULL) {
+ bp = omalloc_make_chunks(d, j, listnum);
if (bp == NULL)
return NULL;
- } else
- bp = LIST_FIRST(d-chunk_dir[j]);
+ }
if (bp-canary != d-canary1)
wrterror(chunk info corrupted, NULL);
@@ -973,7 +975,7 @@ free_bytes(struct dir_info *d, struct re
{
struct chunk_head *mp;
struct chunk_info *info;
- int i;
+ int i, listnum;
info = (struct chunk_info *)r-size;
if (info-canary != d-canary1)
@@ -994,16 +996,18 @@ free_bytes(struct dir_info *d, struct re
info-bits[i / MALLOC_BITS] |= 1U (i % MALLOC_BITS);
info-free++;
- if (info-size != 0)
- mp = d-chunk_dir + info-shift;
- else
- mp = d-chunk_dir;
-
if (info-free == 1) {
/* Page became non-full */
+ listnum = getrbyte() % MALLOC_CHUNK_LISTS;
+ if (info-size != 0)
+ mp = d-chunk_dir[info-shift][listnum];
+ else
+ mp = d-chunk_dir[0][listnum];
+
LIST_INSERT_HEAD(mp, info, entries);
return;
}
+
if (info-free != info-total)
return;
