replace kern malloc's hand rolled freelist with simpleq macros.

ok deraadt mpi

1 files changed, 31 insertions, 65 deletions

diff --git a/sys/kern/kern_malloc.c b/sys/kern/kern_malloc.c
index a18e0a668ef..c987d2dd20e 100644
--- a/sys/kern/kern_malloc.c
+++ b/sys/kern/kern_malloc.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: kern_malloc.c,v 1.96 2013/03/21 01:29:41 deraadt Exp $	*/
+/*	$OpenBSD: kern_malloc.c,v 1.97 2013/03/26 16:36:01 tedu Exp $	*/
 /*	$NetBSD: kern_malloc.c,v 1.15.4.2 1996/06/13 17:10:56 cgd Exp $	*/
 
 /*
@@ -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 flags)
 {
 	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 flags)
 		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 flags)
 		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 flags)
 		}
 	}
 
-	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, void *oldp, size_t *oldlenp, void *newp,
 
 	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