physmem allocator: change the view of free memory from single free pages

to free ranges.
Classify memory based on region with associated use-counter (which is used
to construct a priority list of where to allocate memory).

Based on code from tedu@, help from many.
Ok art@

1 files changed, 25 insertions, 303 deletions

diff --git a/sys/uvm/uvm_pglist.c b/sys/uvm/uvm_pglist.c
index 093cd134b7f..ff0f8d91f68 100644
--- a/sys/uvm/uvm_pglist.c
+++ b/sys/uvm/uvm_pglist.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_pglist.c,v 1.29 2009/05/04 18:08:06 oga Exp $	*/
+/*	$OpenBSD: uvm_pglist.c,v 1.30 2009/06/01 17:42:33 ariane Exp $	*/
 /*	$NetBSD: uvm_pglist.c,v 1.13 2001/02/18 21:19:08 chs Exp $	*/
 
 /*-
@@ -56,112 +56,6 @@ u_long	uvm_pglistalloc_npages;
 #define	STAT_DECR(v)
 #endif
 
-int	uvm_pglistalloc_simple(psize_t, paddr_t, paddr_t, struct pglist *);
-
-/*
- * Simple page allocation: pages do not need to be contiguous. We just
- * attempt to find enough free pages in the given range.
- */
-int
-uvm_pglistalloc_simple(psize_t size, paddr_t low, paddr_t high,
-    struct pglist *rlist)
-{
-	psize_t todo;
-	int psi;
-	struct vm_page *pg;
-	struct vm_physseg *seg;
-	paddr_t slow, shigh;
-	int pgflidx, error, free_list;
-	UVMHIST_FUNC("uvm_pglistalloc_simple"); UVMHIST_CALLED(pghist);
-#ifdef DEBUG
-	vm_page_t tp;
-#endif
-
-	/* Default to "lose". */
-	error = ENOMEM;
-
-	todo = atop(size);
-
-	/*
-	 * Block all memory allocation and lock the free list.
-	 */
-	uvm_lock_fpageq();
-
-	/* Are there even any free pages? */
-	if (uvmexp.free <= (uvmexp.reserve_pagedaemon + uvmexp.reserve_kernel))
-		goto out;
-
-	for (psi = 0, seg = vm_physmem; psi < vm_nphysseg; psi++, seg++) {
-		/*
-		 * Skip this segment if incompatible with the address range.
-		 */
-		if (seg->avail_end <= atop(low))
-			continue;
-		if (seg->avail_start >= atop(high))
-			continue;
-
-		slow = MAX(atop(low), seg->avail_start);
-		shigh = MIN(atop(high), seg->avail_end);
-
-		/* we want to be able to allocate at least a page... */
-		if (slow == shigh)
-			continue;
-
-		for (pg = &seg->pgs[slow - seg->start]; slow != shigh;
-		    slow++, pg++) {
-			if (VM_PAGE_IS_FREE(pg) == 0)
-				continue;
-
-			free_list = uvm_page_lookup_freelist(pg);
-			pgflidx = (pg->pg_flags & PG_ZERO) ?
-			    PGFL_ZEROS : PGFL_UNKNOWN;
-#ifdef DEBUG
-			for (tp = TAILQ_FIRST(&uvm.page_free[free_list].pgfl_queues[pgflidx]);
-			     tp != NULL; tp = TAILQ_NEXT(tp, pageq)) {
-				if (tp == pg)
-					break;
-			}
-			if (tp == NULL)
-				panic("uvm_pglistalloc_simple: page not on freelist");
-#endif
-			TAILQ_REMOVE(&uvm.page_free[free_list].pgfl_queues[pgflidx],
-			    pg, pageq);
-			uvmexp.free--;
-			if (pg->pg_flags & PG_ZERO)
-				uvmexp.zeropages--;
-			pg->uobject = NULL;
-			pg->uanon = NULL;
-			pg->pg_version++;
-			TAILQ_INSERT_TAIL(rlist, pg, pageq);
-			STAT_INCR(uvm_pglistalloc_npages);
-			if (--todo == 0) {
-				error = 0;
-				goto out;
-			}
-		}
-
-	}
-
-out:
-	/*
-	 * check to see if we need to generate some free pages waking
-	 * the pagedaemon.
-	 */
-
-	if (!error && (uvmexp.free + uvmexp.paging < uvmexp.freemin ||
-	    (uvmexp.free + uvmexp.paging < uvmexp.freetarg &&
-	    uvmexp.inactive < uvmexp.inactarg))) {
-		wakeup(&uvm.pagedaemon_proc);
-	}
-
-	uvm_unlock_fpageq();
-
-	if (error)
-		uvm_pglistfree(rlist);
-
-	return (error);
-}
-
 /*
  * uvm_pglistalloc: allocate a list of pages
  *
@@ -179,202 +73,45 @@ out:
  *	alignment	memory must be aligned to this power-of-two boundary.
  *	boundary	no segment in the allocation may cross this 
  *			power-of-two boundary (relative to zero).
+ * => flags:
+ *	UVM_PLA_NOWAIT	fail if allocation fails
+ *	UVM_PLA_WAITOK	wait for memory to become avail if allocation fails
+ *	UVM_PLA_ZERO	return zeroed memory
+ *	UVM_PLA_TRY_CONTIG device prefers p-lineair mem
  */
 
 int
 uvm_pglistalloc(psize_t size, paddr_t low, paddr_t high, paddr_t alignment,
     paddr_t boundary, struct pglist *rlist, int nsegs, int flags)
 {
-	int psi;
-	struct vm_page *pgs;
-	struct vm_physseg *seg;
-	paddr_t slow, shigh;
-	paddr_t try, idxpa, lastidxpa;
-	int tryidx, idx, pgflidx, endidx, error, free_list;
-	vm_page_t m;
-	u_long pagemask;
-#ifdef DEBUG
-	vm_page_t tp;
-#endif
 	UVMHIST_FUNC("uvm_pglistalloc"); UVMHIST_CALLED(pghist);
 
 	KASSERT((alignment & (alignment - 1)) == 0);
 	KASSERT((boundary & (boundary - 1)) == 0);
-	/*
-	 * This argument is always ignored for now, but ensure drivers always
-	 * show intention.
-	 */
 	KASSERT(!(flags & UVM_PLA_WAITOK) ^ !(flags & UVM_PLA_NOWAIT));
-	
-	/*
-	 * Our allocations are always page granularity, so our alignment
-	 * must be, too.
-	 */
-	if (alignment < PAGE_SIZE)
-		alignment = PAGE_SIZE;
 
 	if (size == 0)
 		return (EINVAL);
 
-	size = round_page(size);
-	low = roundup(low, alignment);
-
 	/*
-	 * If we are allowed to allocate as many segments as pages,
-	 * no need to be smart.
+	 * Convert byte addresses to page numbers.
 	 */
-	if ((nsegs >= size / PAGE_SIZE) && (alignment == PAGE_SIZE) &&
-	    (boundary == 0)) {
-		error = uvm_pglistalloc_simple(size, low, high, rlist);
-		goto done;
-	}
-
-	if (boundary != 0 && boundary < size)
-		return (EINVAL);
-
-	pagemask = ~(boundary - 1);
-
-	/* Default to "lose". */
-	error = ENOMEM;
-
-	/*
-	 * Block all memory allocation and lock the free list.
-	 */
-	uvm_lock_fpageq();
-
-	/* Are there even any free pages? */
-	if (uvmexp.free <= (uvmexp.reserve_pagedaemon + uvmexp.reserve_kernel))
-		goto out;
-
-	for (psi = 0, seg = vm_physmem; psi < vm_nphysseg; psi++, seg++) {
-		/*
-		 * Skip this segment if incompatible with the address range.
-		 */
-		if (seg->avail_end <= atop(low))
-			continue;
-		if (seg->avail_start >= atop(high))
-			continue;
-
-		slow = MAX(low, ptoa(seg->avail_start));
-		shigh = MIN(high, ptoa(seg->avail_end));
-
-		try = roundup(slow, alignment);
-		for (;; try += alignment) {
-			if (try + size > shigh) {
-				/*
-				 * We've run past the allowable range, or
-				 * the segment. Try another.
-				 */
-				break;
-			}
-
-			tryidx = idx = atop(try) - seg->start;
-			endidx = idx + atop(size);
-			pgs = vm_physmem[psi].pgs;
-
-			/*
-			 * Found a suitable starting page.  See if the
-			 * range is free.
-			 */
-
-			for (; idx < endidx; idx++) {
-				if (VM_PAGE_IS_FREE(&pgs[idx]) == 0) {
-					break;
-				}
-				idxpa = VM_PAGE_TO_PHYS(&pgs[idx]);
-				if (idx == tryidx)
-					continue;
-
-				/*
-				 * Check that the region is contiguous
-				 * (it really should...) and does not
-				 * cross an alignment boundary.
-				 */
-				lastidxpa = VM_PAGE_TO_PHYS(&pgs[idx - 1]);
-				if ((lastidxpa + PAGE_SIZE) != idxpa)
-					break;
-
-				if (boundary != 0 &&
-				    ((lastidxpa ^ idxpa) & pagemask) != 0)
-					break;
-			}
-
-			if (idx == endidx) {
-				goto found;
-			}
-		}
-	}
-
-	/*
-	 * We could not allocate a contiguous range.  This is where
-	 * we should try harder if nsegs > 1...
-	 */
-	goto out;
-
-#if PGFL_NQUEUES != 2
-#error uvm_pglistalloc needs to be updated
-#endif
-
-found:
-	/*
-	 * we have a chunk of memory that conforms to the requested constraints.
-	 */
-	idx = tryidx;
-	while (idx < endidx) {
-		m = &pgs[idx];
-		free_list = uvm_page_lookup_freelist(m);
-		pgflidx = (m->pg_flags & PG_ZERO) ? PGFL_ZEROS : PGFL_UNKNOWN;
-#ifdef DEBUG
-		for (tp = TAILQ_FIRST(&uvm.page_free[
-			free_list].pgfl_queues[pgflidx]);
-		     tp != NULL;
-		     tp = TAILQ_NEXT(tp, pageq)) {
-			if (tp == m)
-				break;
-		}
-		if (tp == NULL)
-			panic("uvm_pglistalloc: page not on freelist");
-#endif
-		TAILQ_REMOVE(&uvm.page_free[free_list].pgfl_queues[pgflidx],
-		    m, pageq);
-		uvmexp.free--;
-		if (m->pg_flags & PG_ZERO)
-			uvmexp.zeropages--;
-		m->uobject = NULL;
-		m->uanon = NULL;
-		m->pg_version++;
-		TAILQ_INSERT_TAIL(rlist, m, pageq);
-		idx++;
-		STAT_INCR(uvm_pglistalloc_npages);
-	}
-	error = 0;
-
-out:
-	/*
-	 * check to see if we need to generate some free pages waking
-	 * the pagedaemon.
-	 */
-	 
-	if (uvmexp.free + uvmexp.paging < uvmexp.freemin ||
-	    (uvmexp.free + uvmexp.paging < uvmexp.freetarg &&
-	     uvmexp.inactive < uvmexp.inactarg)) {
-		wakeup(&uvm.pagedaemon_proc);
-	}
-
-	uvm_unlock_fpageq();
-
-done: 
-	/* No locking needed here, pages are not on any queue. */
-	if (error == 0) {
-		TAILQ_FOREACH(m, rlist, pageq) {
-			if (flags & UVM_PLA_ZERO &&
-			    (m->pg_flags & PG_ZERO) == 0)
-				uvm_pagezero(m);
-			m->pg_flags = PG_CLEAN;
-		}
-	}
-
-	return (error);
+	if (alignment < PAGE_SIZE)
+		alignment = PAGE_SIZE;
+	low = atop(roundup(low, alignment));
+	/* Allows for overflow: 0xffff + 1 = 0x0000 */
+	if ((high & PAGE_MASK) == PAGE_MASK)
+		high = atop(high) + 1;
+	else
+		high = atop(high);
+	size = atop(round_page(size));
+	alignment = atop(alignment);
+	if (boundary < PAGE_SIZE && boundary != 0)
+		boundary = PAGE_SIZE;
+	boundary = atop(boundary);
+
+	return uvm_pmr_getpages(size, low, high, alignment, boundary, nsegs,
+	    flags, rlist);
 }
 
 /*
@@ -389,14 +126,8 @@ uvm_pglistfree(struct pglist *list)
 	struct vm_page *m;
 	UVMHIST_FUNC("uvm_pglistfree"); UVMHIST_CALLED(pghist);
 
-	/*
-	 * Block all memory allocation and lock the free list.
-	 */
-	uvm_lock_fpageq();
-
-	while ((m = TAILQ_FIRST(list)) != NULL) {
+	TAILQ_FOREACH(m, list, pageq) {
 		KASSERT((m->pg_flags & (PQ_ACTIVE|PQ_INACTIVE)) == 0);
-		TAILQ_REMOVE(list, m, pageq);
 #ifdef DEBUG
 		if (m->uobject == (void *)0xdeadbeef &&
 		    m->uanon == (void *)0xdeadbeef) {
@@ -408,15 +139,6 @@ uvm_pglistfree(struct pglist *list)
 		m->uanon = (void *)0xdeadbeef;
 #endif
 		atomic_clearbits_int(&m->pg_flags, PQ_MASK);
-		atomic_setbits_int(&m->pg_flags, PQ_FREE);
-		TAILQ_INSERT_TAIL(&uvm.page_free[
-		    uvm_page_lookup_freelist(m)].pgfl_queues[PGFL_UNKNOWN],
-		    m, pageq);
-		uvmexp.free++;
-		if (uvmexp.zeropages < UVM_PAGEZERO_TARGET)
-			uvm.page_idle_zero = vm_page_zero_enable;
-		STAT_DECR(uvm_pglistalloc_npages);
 	}
-
-	uvm_unlock_fpageq();
+	uvm_pmr_freepageq(list);
 }