kern malloc rolls its own linked list code. for the sake of clarity
and to make future changes easier, i'd like to make it a simpleq.
it would be very nice if this could be tested on a few different kinds
of machines. it's not supposed to actually change anything, but that's
what testing is to verify.
Index: sys/malloc.h
===================================================================
RCS file: /cvs/src/sys/sys/malloc.h,v
retrieving revision 1.101
diff -u -p -r1.101 malloc.h
--- sys/malloc.h 7 Feb 2013 11:06:42 -0000 1.101
+++ sys/malloc.h 21 Mar 2013 06:42:10 -0000
@@ -35,6 +35,8 @@
#ifndef _SYS_MALLOC_H_
#define _SYS_MALLOC_H_
+#include <sys/queue.h>
+
#define KERN_MALLOC_BUCKETS 1
#define KERN_MALLOC_BUCKET 2
#define KERN_MALLOC_KMEMNAMES 3
@@ -340,11 +342,25 @@ struct kmemusage {
#define ku_pagecnt ku_un.pagecnt
/*
+ * Normally the freelist structure is used only to hold the list pointer
+ * for free objects. However, when running with diagnostics, the first
+ * 8 bytes of the structure is unused except for diagnostic information,
+ * and the free list pointer is at offset 8 in the structure. Since the
+ * first 8 bytes is the portion of the structure most often modified, this
+ * helps to detect memory reuse problems and avoid free list corruption.
+ */
+struct kmem_freelist {
+ int32_t kf_spare0;
+ int16_t kf_type;
+ int16_t kf_spare1;
+ SIMPLEQ_ENTRY(kmem_freelist) kf_flist;
+};
+
+/*
* Set of buckets for each size of memory block that is retained
*/
struct kmembuckets {
- caddr_t kb_next; /* list of free blocks */
- caddr_t kb_last; /* last free block */
+ SIMPLEQ_HEAD(, kmem_freelist) kb_freelist; /* list of free blocks */
u_int64_t kb_calls; /* total calls to allocate this size */
u_int64_t kb_total; /* total number of blocks allocated */
u_int64_t kb_totalfree; /* # of free elements in this bucket */
Index: kern/kern_malloc.c
===================================================================
RCS file: /cvs/src/sys/kern/kern_malloc.c,v
retrieving revision 1.95
diff -u -p -r1.95 kern_malloc.c
--- kern/kern_malloc.c 15 Mar 2013 19:10:43 -0000 1.95
+++ kern/kern_malloc.c 21 Mar 2013 07:43:07 -0000
@@ -175,25 +175,6 @@ poison_check(void *v, size_t len)
}
-
-/*
- * Normally the freelist structure is used only to hold the list pointer
- * for free objects. However, when running with diagnostics, the first
- * 8 bytes of the structure is unused except for diagnostic information,
- * and the free list pointer is at offset 8 in the structure. Since the
- * first 8 bytes is the portion of the structure most often modified, this
- * helps to detect memory reuse problems and avoid free list corruption.
- */
-struct freelist {
- int32_t spare0;
- int16_t type;
- int16_t spare1;
- caddr_t next;
-};
-#else /* !DIAGNOSTIC */
-struct freelist {
- caddr_t next;
-};
#endif /* DIAGNOSTIC */
#ifndef SMALL_KERNEL
@@ -209,10 +190,10 @@ malloc(unsigned long size, int type, int
{
struct kmembuckets *kbp;
struct kmemusage *kup;
- struct freelist *freep;
+ struct kmem_freelist *freep;
long indx, npg, allocsize;
int s;
- caddr_t va, cp, savedlist;
+ caddr_t va, cp;
#ifdef DIAGNOSTIC
size_t pidx;
int freshalloc;
@@ -270,7 +251,7 @@ malloc(unsigned long size, int type, int
allocsize = round_page(size);
else
allocsize = 1 << indx;
- if (kbp->kb_next == NULL) {
+ if (SIMPLEQ_FIRST(&kbp->kb_freelist) == NULL) {
npg = atop(round_page(allocsize));
va = (caddr_t)uvm_km_kmemalloc_pla(kmem_map, NULL,
(vsize_t)ptoa(npg), 0,
@@ -311,58 +292,48 @@ malloc(unsigned long size, int type, int
kup->ku_freecnt = kbp->kb_elmpercl;
kbp->kb_totalfree += kbp->kb_elmpercl;
#endif
- /*
- * Just in case we blocked while allocating memory,
- * and someone else also allocated memory for this
- * bucket, don't assume the list is still empty.
- */
- savedlist = kbp->kb_next;
- kbp->kb_next = cp = va + (npg * PAGE_SIZE) - allocsize;
+ cp = va + (npg * PAGE_SIZE) - allocsize;
for (;;) {
- freep = (struct freelist *)cp;
+ freep = (struct kmem_freelist *)cp;
#ifdef DIAGNOSTIC
/*
* Copy in known text to detect modification
* after freeing.
*/
poison(cp, allocsize);
- freep->type = M_FREE;
+ freep->kf_type = M_FREE;
#endif /* DIAGNOSTIC */
+ SIMPLEQ_INSERT_HEAD(&kbp->kb_freelist, freep, kf_flist);
if (cp <= va)
break;
cp -= allocsize;
- freep->next = cp;
}
- freep->next = savedlist;
- if (savedlist == NULL)
- kbp->kb_last = (caddr_t)freep;
} else {
#ifdef DIAGNOSTIC
freshalloc = 0;
#endif
}
- va = kbp->kb_next;
- kbp->kb_next = ((struct freelist *)va)->next;
+ freep = SIMPLEQ_FIRST(&kbp->kb_freelist);
+ SIMPLEQ_REMOVE_HEAD(&kbp->kb_freelist, kf_flist);
+ va = (caddr_t)freep;
#ifdef DIAGNOSTIC
- freep = (struct freelist *)va;
- savedtype = (unsigned)freep->type < M_LAST ?
- memname[freep->type] : "???";
- if (freshalloc == 0 && kbp->kb_next) {
+ savedtype = (unsigned)freep->kf_type < M_LAST ?
+ memname[freep->kf_type] : "???";
+ if (freshalloc == 0 && SIMPLEQ_FIRST(&kbp->kb_freelist)) {
int rv;
- vaddr_t addr = (vaddr_t)kbp->kb_next;
+ vaddr_t addr = (vaddr_t)SIMPLEQ_FIRST(&kbp->kb_freelist);
vm_map_lock(kmem_map);
rv = uvm_map_checkprot(kmem_map, addr,
- addr + sizeof(struct freelist), VM_PROT_WRITE);
+ addr + sizeof(struct kmem_freelist), VM_PROT_WRITE);
vm_map_unlock(kmem_map);
if (!rv) {
printf("%s %zd of object %p size 0x%lx %s %s"
" (invalid addr %p)\n",
"Data modified on freelist: word",
- (int32_t *)&kbp->kb_next - (int32_t *)kbp, va, size,
+ (int32_t *)&addr - (int32_t *)kbp, va, size,
"previous type", savedtype, (void *)addr);
- kbp->kb_next = NULL;
}
}
@@ -381,7 +352,7 @@ malloc(unsigned long size, int type, int
}
}
- freep->spare0 = 0;
+ freep->kf_spare0 = 0;
#endif /* DIAGNOSTIC */
#ifdef KMEMSTATS
kup = btokup(va);
@@ -416,11 +387,10 @@ free(void *addr, int type)
{
struct kmembuckets *kbp;
struct kmemusage *kup;
- struct freelist *freep;
+ struct kmem_freelist *freep;
long size;
int s;
#ifdef DIAGNOSTIC
- caddr_t cp;
long alloc;
#endif
#ifdef KMEMSTATS
@@ -471,16 +441,16 @@ free(void *addr, int type)
splx(s);
return;
}
- freep = (struct freelist *)addr;
+ freep = (struct kmem_freelist *)addr;
#ifdef DIAGNOSTIC
/*
* Check for multiple frees. Use a quick check to see if
* it looks free before laboriously searching the freelist.
*/
- if (freep->spare0 == WEIRD_ADDR) {
- for (cp = kbp->kb_next; cp;
- cp = ((struct freelist *)cp)->next) {
- if (addr != cp)
+ if (freep->kf_spare0 == WEIRD_ADDR) {
+ struct kmem_freelist *fp;
+ SIMPLEQ_FOREACH(fp, &kbp->kb_freelist, kf_flist) {
+ if (addr != fp)
continue;
printf("multiply freed item %p\n", addr);
panic("free: duplicated free");
@@ -494,7 +464,7 @@ free(void *addr, int type)
*/
poison(addr, size);
- freep->type = type;
+ freep->kf_type = type;
#endif /* DIAGNOSTIC */
#ifdef KMEMSTATS
kup->ku_freecnt++;
@@ -511,12 +481,7 @@ free(void *addr, int type)
wakeup(ksp);
ksp->ks_inuse--;
#endif
- if (kbp->kb_next == NULL)
- kbp->kb_next = addr;
- else
- ((struct freelist *)kbp->kb_last)->next = addr;
- freep->next = NULL;
- kbp->kb_last = addr;
+ SIMPLEQ_INSERT_TAIL(&kbp->kb_freelist, freep, kf_flist);
splx(s);
}
@@ -575,12 +540,10 @@ void
kmeminit(void)
{
vaddr_t base, limit;
-#ifdef KMEMSTATS
long indx;
-#endif
#ifdef DIAGNOSTIC
- if (sizeof(struct freelist) > (1 << MINBUCKET))
+ if (sizeof(struct kmem_freelist) > (1 << MINBUCKET))
panic("kmeminit: minbucket too small/struct freelist too big");
#endif
@@ -602,6 +565,9 @@ kmeminit(void)
kmemlimit = (char *)limit;
kmemusage = (struct kmemusage *) uvm_km_zalloc(kernel_map,
(vsize_t)(nkmempages * sizeof(struct kmemusage)));
+ for (indx = 0; indx < MINBUCKET + 16; indx++) {
+ SIMPLEQ_INIT(&bucket[indx].kb_freelist);
+ }
#ifdef KMEMSTATS
for (indx = 0; indx < MINBUCKET + 16; indx++) {
if (1 << indx >= PAGE_SIZE)
@@ -652,7 +618,7 @@ sysctl_malloc(int *name, u_int namelen,
case KERN_MALLOC_BUCKET:
bcopy(&bucket[BUCKETINDX(name[1])], &kb, sizeof(kb));
- kb.kb_next = kb.kb_last = 0;
+ bzero(&kb.kb_freelist, sizeof(kb.kb_freelist));
return (sysctl_rdstruct(oldp, oldlenp, newp, &kb, sizeof(kb)));
case KERN_MALLOC_KMEMSTATS:
#ifdef KMEMSTATS
