xref: /src/sys/uvm/uvm_physseg.c

/* $NetBSD: uvm_physseg.c,v 1.4 2016/12/25 03:39:26 christos Exp $ */

/*
 * Copyright (c) 1997 Charles D. Cranor and Washington University.
 * Copyright (c) 1991, 1993, The Regents of the University of California.
 *
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * The Mach Operating System project at Carnegie-Mellon University.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)vm_page.h   7.3 (Berkeley) 4/21/91
 * from: Id: uvm_page.h,v 1.1.2.6 1998/02/04 02:31:42 chuck Exp
 *
 *
 * Copyright (c) 1987, 1990 Carnegie-Mellon University.
 * All rights reserved.
 *
 * Permission to use, copy, modify and distribute this software and
 * its documentation is hereby granted, provided that both the copyright
 * notice and this permission notice appear in all copies of the
 * software, derivative works or modified versions, and any portions
 * thereof, and that both notices appear in supporting documentation.
 *
 * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
 * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND
 * FOR ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
 *
 * Carnegie Mellon requests users of this software to return to
 *
 *  Software Distribution Coordinator  or  Software.Distribution (at) CS.CMU.EDU
 *  School of Computer Science
 *  Carnegie Mellon University
 *  Pittsburgh PA 15213-3890
 *
 * any improvements or extensions that they make and grant Carnegie the
 * rights to redistribute these changes.
 */

/*
 * Consolidated API from uvm_page.c and others.
 * Consolidated and designed by Cherry G. Mathew <cherry (at) zyx.in>
 * rbtree(3) backing implementation by:
 * Santhosh N. Raju <santhosh.raju (at) gmail.com>
 */

#ifdef _KERNEL_OPT
#include "opt_uvm.h"
#endif

#include <sys/param.h>
#include <sys/types.h>
#include <sys/extent.h>
#include <sys/kmem.h>

#include <uvm/uvm.h>
#include <uvm/uvm_page.h>
#include <uvm/uvm_param.h>
#include <uvm/uvm_pdpolicy.h>
#include <uvm/uvm_physseg.h>

/*
 * uvm_physseg: describes one segment of physical memory
 */
struct uvm_physseg {
	struct  rb_node rb_node;	/* tree information */
	paddr_t	start;			/* PF# of first page in segment */
	paddr_t	end;			/* (PF# of last page in segment) + 1 */
	paddr_t	avail_start;		/* PF# of first free page in segment */
	paddr_t	avail_end;		/* (PF# of last free page in segment) +1  */
	struct	vm_page *pgs;		/* vm_page structures (from start) */
	struct  extent *ext;		/* extent(9) structure to manage pgs[] */
	int	free_list;		/* which free list they belong on */
	u_int	start_hint;		/* start looking for free pages here */
					/* protected by uvm_fpageqlock */
#ifdef __HAVE_PMAP_PHYSSEG
	struct	pmap_physseg pmseg;	/* pmap specific (MD) data */
#endif
};

/*
 * These functions are reserved for uvm(9) internal use and are not
 * exported in the header file uvm_physseg.h
 *
 * Thus they are redefined here.
 */
void uvm_physseg_init_seg(uvm_physseg_t, struct vm_page *);
void uvm_physseg_seg_chomp_slab(uvm_physseg_t, struct vm_page *, size_t);

/* returns a pgs array */
struct vm_page *uvm_physseg_seg_alloc_from_slab(uvm_physseg_t, size_t);

#if defined(UVM_HOTPLUG) /* rbtree impementation */

#define		HANDLE_TO_PHYSSEG_NODE(h)	((struct uvm_physseg *)(h))
#define		PHYSSEG_NODE_TO_HANDLE(u)	((uvm_physseg_t)(u))

struct uvm_physseg_graph {
	struct rb_tree rb_tree;		/* Tree for entries */
	int            nentries;	/* Number of entries */
};

static struct uvm_physseg_graph uvm_physseg_graph;

/*
 * Note on kmem(9) allocator usage:
 * We take the conservative approach that plug/unplug are allowed to
 * fail in high memory stress situations.
 *
 * We want to avoid re-entrant situations in which one plug/unplug
 * operation is waiting on a previous one to complete, since this
 * makes the design more complicated than necessary.
 *
 * We may review this and change its behaviour, once the use cases
 * become more obvious.
 */

/*
 * Special alloc()/free() functions for boot time support:
 * We assume that alloc() at boot time is only for new 'vm_physseg's
 * This allows us to use a static array for memory allocation at boot
 * time. Thus we avoid using kmem(9) which is not ready at this point
 * in boot.
 *
 * After kmem(9) is ready, we use it. We currently discard any free()s
 * to this static array, since the size is small enough to be a
 * trivial waste on all architectures we run on.
 */

static size_t nseg = 0;
static struct uvm_physseg uvm_physseg[VM_PHYSSEG_MAX];

static void *
uvm_physseg_alloc(size_t sz)
{
	/*
	 * During boot time, we only support allocating vm_physseg
	 * entries from the static array.
	 * We need to assert for this.
	 */

	if (__predict_false(uvm.page_init_done == false)) {
		if (sz % sizeof(struct uvm_physseg))
			panic("%s: tried to alloc size other than multiple"
			    "of struct uvm_physseg at boot\n", __func__);

		size_t n = sz / sizeof(struct uvm_physseg);
		nseg += n;

		KASSERT(nseg > 0 && nseg <= VM_PHYSSEG_MAX);

		return &uvm_physseg[nseg - n];
	}

	return kmem_zalloc(sz, KM_NOSLEEP);
}

static void
uvm_physseg_free(void *p, size_t sz)
{
	/*
	 * This is a bit tricky. We do allow simulation of free()
	 * during boot (for eg: when MD code is "steal"ing memory,
	 * and the segment has been exhausted (and thus needs to be
	 * free() - ed.
	 * free() also complicates things because we leak the
	 * free(). Therefore calling code can't assume that free()-ed
	 * memory is available for alloc() again, at boot time.
	 *
	 * Thus we can't explicitly disallow free()s during
	 * boot time. However, the same restriction for alloc()
	 * applies to free(). We only allow uvm_physseg related free()s
	 * via this function during boot time.
	 */

	if (__predict_false(uvm.page_init_done == false)) {
		if (sz % sizeof(struct uvm_physseg))
			panic("%s: tried to free size other than struct uvm_physseg"
			    "at boot\n", __func__);

	}

	/*
	 * Could have been in a single if(){} block - split for
	 * clarity
	 */

	if ((struct uvm_physseg *)p >= uvm_physseg &&
	    (struct uvm_physseg *)p < (uvm_physseg + VM_PHYSSEG_MAX)) {
		if (sz % sizeof(struct uvm_physseg))
			panic("%s: tried to free() other than struct uvm_physseg"
			    "from static array\n", __func__);

		if ((sz / sizeof(struct uvm_physseg)) >= VM_PHYSSEG_MAX)
			panic("%s: tried to free() the entire static array!", __func__);
		return; /* Nothing to free */
	}

	kmem_free(p, sz);
}

/* XXX: Multi page size */
bool
uvm_physseg_plug(paddr_t pfn, size_t pages, uvm_physseg_t *psp)
{
	int preload;
	size_t slabpages;
	struct uvm_physseg *ps, *current_ps = NULL;
	struct vm_page *slab = NULL, *pgs = NULL;

#ifdef DEBUG
	paddr_t off;
	uvm_physseg_t upm;
	upm = uvm_physseg_find(pfn, &off);

	ps = HANDLE_TO_PHYSSEG_NODE(upm);

	if (ps != NULL) /* XXX; do we allow "update" plugs ? */
		return false;
#endif

	/*
	 * do we have room?
	 */

	ps = uvm_physseg_alloc(sizeof (struct uvm_physseg));
	if (ps == NULL) {
		printf("uvm_page_physload: unable to load physical memory "
		    "segment\n");
		printf("\t%d segments allocated, ignoring 0x%"PRIxPADDR" -> 0x%"PRIxPADDR"\n",
		    VM_PHYSSEG_MAX, pfn, pfn + pages + 1);
		printf("\tincrease VM_PHYSSEG_MAX\n");
		return false;
	}

	/* span init */
	ps->start = pfn;
	ps->end = pfn + pages;

	/*
	 * XXX: Ugly hack because uvmexp.npages accounts for only
	 * those pages in the segment included below as well - this
	 * should be legacy and removed.
	 */

	ps->avail_start = ps->start;
	ps->avail_end = ps->end;

	/*
	 * check to see if this is a "preload" (i.e. uvm_page_init hasn't been
	 * called yet, so kmem is not available).
	 */

	preload = 1; /* We are going to assume it is a preload */

	RB_TREE_FOREACH(current_ps, &(uvm_physseg_graph.rb_tree)) {
		/* If there are non NULL pages then we are not in a preload */
		if (current_ps->pgs != NULL) {
			preload = 0;
			/* Try to scavenge from earlier unplug()s. */
			pgs = uvm_physseg_seg_alloc_from_slab(current_ps, pages);

			if (pgs != NULL) {
				break;
			}
		}
	}


	/*
	 * if VM is already running, attempt to kmem_alloc vm_page structures
	 */

	if (!preload) {
		if (pgs == NULL) { /* Brand new */
			/* Iteratively try alloc down from uvmexp.npages */
			for (slabpages = (size_t) uvmexp.npages; slabpages >= pages; slabpages--) {
				slab = kmem_zalloc(sizeof *pgs * (long unsigned int)slabpages, KM_NOSLEEP);
				if (slab != NULL)
					break;
			}

			if (slab == NULL) {
				uvm_physseg_free(ps, sizeof(struct uvm_physseg));
				return false;
			}

			uvm_physseg_seg_chomp_slab(ps, slab, (size_t) slabpages);
			/* We allocate enough for this plug */
			pgs = uvm_physseg_seg_alloc_from_slab(ps, pages);

			if (pgs == NULL) {
				printf("unable to uvm_physseg_seg_alloc_from_slab() from backend\n");
				return false;
			}
		} else {
			/* Reuse scavenged extent */
			ps->ext = current_ps->ext;
		}

		physmem += pages;
		uvmpdpol_reinit();
	} else { /* Boot time - see uvm_page.c:uvm_page_init() */
		pgs = NULL;
		ps->pgs = pgs;
	}

	/*
	 * now insert us in the proper place in uvm_physseg_graph.rb_tree
	 */

	current_ps = rb_tree_insert_node(&(uvm_physseg_graph.rb_tree), ps);
	if (current_ps != ps) {
		panic("uvm_page_physload: Duplicate address range detected!");
	}
	uvm_physseg_graph.nentries++;

	/*
	 * uvm_pagefree() requires the PHYS_TO_VM_PAGE(pgs[i]) on the
	 * newly allocated pgs[] to return the correct value. This is
	 * a bit of a chicken and egg problem, since it needs
	 * uvm_physseg_find() to succeed. For this, the node needs to
	 * be inserted *before* uvm_physseg_init_seg() happens.
	 *
	 * During boot, this happens anyway, since
	 * uvm_physseg_init_seg() is called later on and separately
	 * from uvm_page.c:uvm_page_init().
	 * In the case of hotplug we need to ensure this.
	 */

	if (__predict_true(!preload))
		uvm_physseg_init_seg(ps, pgs);

	if (psp != NULL)
		*psp = ps;

	return true;
}

static int
uvm_physseg_compare_nodes(void *ctx, const void *nnode1, const void *nnode2)
{
	const struct uvm_physseg *enode1 = nnode1;
	const struct uvm_physseg *enode2 = nnode2;

	KASSERT(enode1->start < enode2->start || enode1->start >= enode2->end);
	KASSERT(enode2->start < enode1->start || enode2->start >= enode1->end);

	if (enode1->start < enode2->start)
		return -1;
	if (enode1->start >= enode2->end)
		return 1;
	return 0;
}

static int
uvm_physseg_compare_key(void *ctx, const void *nnode, const void *pkey)
{
	const struct uvm_physseg *enode = nnode;
	const paddr_t pa = *(const paddr_t *) pkey;

	if(enode->start <= pa && pa < enode->end)
		return 0;
	if (enode->start < pa)
		return -1;
	if (enode->end > pa)
		return 1;

	return 0;
}

static const rb_tree_ops_t uvm_physseg_tree_ops = {
	.rbto_compare_nodes = uvm_physseg_compare_nodes,
	.rbto_compare_key = uvm_physseg_compare_key,
	.rbto_node_offset = offsetof(struct uvm_physseg, rb_node),
	.rbto_context = NULL
};

/*
 * uvm_physseg_init: init the physmem
 *
 * => physmem unit should not be in use at this point
 */

void
uvm_physseg_init(void)
{
	rb_tree_init(&(uvm_physseg_graph.rb_tree), &uvm_physseg_tree_ops);
	uvm_physseg_graph.nentries = 0;
}

uvm_physseg_t
uvm_physseg_get_next(uvm_physseg_t upm)
{
	/* next of invalid is invalid, not fatal */
	if (uvm_physseg_valid_p(upm) == false)
		return UVM_PHYSSEG_TYPE_INVALID;

	return (uvm_physseg_t) rb_tree_iterate(&(uvm_physseg_graph.rb_tree), upm,
	    RB_DIR_RIGHT);
}

uvm_physseg_t
uvm_physseg_get_prev(uvm_physseg_t upm)
{
	/* prev of invalid is invalid, not fatal */
	if (uvm_physseg_valid_p(upm) == false)
		return UVM_PHYSSEG_TYPE_INVALID;

	return (uvm_physseg_t) rb_tree_iterate(&(uvm_physseg_graph.rb_tree), upm,
	    RB_DIR_LEFT);
}

uvm_physseg_t
uvm_physseg_get_last(void)
{
	return (uvm_physseg_t) RB_TREE_MAX(&(uvm_physseg_graph.rb_tree));
}

uvm_physseg_t
uvm_physseg_get_first(void)
{
	return (uvm_physseg_t) RB_TREE_MIN(&(uvm_physseg_graph.rb_tree));
}

paddr_t
uvm_physseg_get_highest_frame(void)
{
	struct uvm_physseg *ps =
	    (uvm_physseg_t) RB_TREE_MAX(&(uvm_physseg_graph.rb_tree));

	return ps->end - 1;
}

/*
 * uvm_page_physunload: unload physical memory and return it to
 * caller.
 */
bool
uvm_page_physunload(uvm_physseg_t upm, int freelist, paddr_t *paddrp)
{
	struct uvm_physseg *seg;

	if (__predict_true(uvm.page_init_done == true))
		panic("%s: unload attempted after uvm_page_init()\n", __func__);

	seg = HANDLE_TO_PHYSSEG_NODE(upm);

	if (seg->free_list != freelist) {
		paddrp = NULL;
		return false;
	}

	/*
	 * During cold boot, what we're about to unplug hasn't been
	 * put on the uvm freelist, nor has uvmexp.npages been
	 * updated. (This happens in uvm_page.c:uvm_page_init())
	 *
	 * For hotplug, we assume here that the pages being unloaded
	 * here are completely out of sight of uvm (ie; not on any uvm
	 * lists), and that  uvmexp.npages has been suitably
	 * decremented before we're called.
	 *
	 * XXX: will avail_end == start if avail_start < avail_end?
	 */

	/* try from front */
	if (seg->avail_start == seg->start &&
	    seg->avail_start < seg->avail_end) {
		*paddrp = ctob(seg->avail_start);
		return uvm_physseg_unplug(seg->avail_start, 1);
	}

	/* try from rear */
	if (seg->avail_end == seg->end &&
	    seg->avail_start < seg->avail_end) {
		*paddrp = ctob(seg->avail_end - 1);
		return uvm_physseg_unplug(seg->avail_end - 1, 1);
	}

	return false;
}

bool
uvm_page_physunload_force(uvm_physseg_t upm, int freelist, paddr_t *paddrp)
{
	struct uvm_physseg *seg;

	seg = HANDLE_TO_PHYSSEG_NODE(upm);

	if (__predict_true(uvm.page_init_done == true))
		panic("%s: unload attempted after uvm_page_init()\n", __func__);
	/* any room in this bank? */
	if (seg->avail_start >= seg->avail_end) {
		paddrp = NULL;
		return false; /* nope */
	}

	*paddrp = ctob(seg->avail_start);

	/* Always unplug from front */
	return uvm_physseg_unplug(seg->avail_start, 1);
}


/*
 * vm_physseg_find: find vm_physseg structure that belongs to a PA
 */
uvm_physseg_t
uvm_physseg_find(paddr_t pframe, psize_t *offp)
{
	struct uvm_physseg * ps = NULL;

	ps = rb_tree_find_node(&(uvm_physseg_graph.rb_tree), &pframe);

	if(ps != NULL && offp != NULL)
		*offp = pframe - ps->start;

	return ps;
}

#if defined(PMAP_STEAL_MEMORY)
void
uvm_physseg_set_avail_start(uvm_physseg_t upm, paddr_t avail_start)
{
	struct uvm_physseg *ps = HANDLE_TO_PHYSSEG_NODE(upm);

#if defined(DIAGNOSTIC)
	paddr_t avail_end;
	avail_end = uvm_physseg_get_avail_end(upm);
#endif
	KASSERT(avail_start < avail_end && avail_start >= ps->start);
	ps->avail_start = avail_start;
}
void uvm_physseg_set_avail_end(uvm_physseg_t upm, paddr_t avail_end)
{
	struct uvm_physseg *ps = HANDLE_TO_PHYSSEG_NODE(upm);

#if defined(DIAGNOSTIC)
	paddr_t avail_start;
	avail_start = uvm_physseg_get_avail_start(upm);
#endif

	KASSERT(avail_end > avail_start && avail_end <= ps->end);

	ps->avail_end = avail_end;
}

#endif /* PMAP_STEAL_MEMORY */
#else  /* UVM_HOTPLUG */

/*
 * physical memory config is stored in vm_physmem.
 */

#define	VM_PHYSMEM_PTR(i)	(&vm_physmem[i])
#if VM_PHYSSEG_MAX == 1
#define VM_PHYSMEM_PTR_SWAP(i, j) /* impossible */
#else
#define VM_PHYSMEM_PTR_SWAP(i, j)					      \
	do { vm_physmem[(i)] = vm_physmem[(j)]; } while (0)
#endif

#define		HANDLE_TO_PHYSSEG_NODE(h)	(VM_PHYSMEM_PTR((int)h))
#define		PHYSSEG_NODE_TO_HANDLE(u)	((int)((vsize_t) (u - vm_physmem) / sizeof(struct uvm_physseg)))

static struct uvm_physseg vm_physmem[VM_PHYSSEG_MAX];	/* XXXCDC: uvm.physmem */
static int vm_nphysseg = 0;				/* XXXCDC: uvm.nphysseg */
#define	vm_nphysmem	vm_nphysseg

void
uvm_physseg_init(void)
{
	/* XXX: Provisioning for rb_tree related init(s) */
	return;
}

int
uvm_physseg_get_next(uvm_physseg_t lcv)
{
	/* next of invalid is invalid, not fatal */
	if (uvm_physseg_valid_p(lcv) == false)
		return UVM_PHYSSEG_TYPE_INVALID;

	return (lcv + 1);
}

int
uvm_physseg_get_prev(uvm_physseg_t lcv)
{
	/* prev of invalid is invalid, not fatal */
	if (uvm_physseg_valid_p(lcv) == false)
		return UVM_PHYSSEG_TYPE_INVALID;

	return (lcv - 1);
}

int
uvm_physseg_get_last(void)
{
	return (vm_nphysseg - 1);
}

int
uvm_physseg_get_first(void)
{
	return 0;
}

paddr_t
uvm_physseg_get_highest_frame(void)
{
	int lcv;
	paddr_t last = 0;
	struct uvm_physseg *ps;

	for (lcv = 0; lcv < vm_nphysseg; lcv++) {
		ps = VM_PHYSMEM_PTR(lcv);
		if (last < ps->end)
			last = ps->end;
	}

	return last;
}


static struct vm_page *
uvm_post_preload_check(void)
{
	int preload, lcv;

	/*
	 * check to see if this is a "preload" (i.e. uvm_page_init hasn't been
	 * called yet, so kmem is not available).
	 */

	for (lcv = 0 ; lcv < vm_nphysmem ; lcv++) {
		if (VM_PHYSMEM_PTR(lcv)->pgs)
			break;
	}
	preload = (lcv == vm_nphysmem);

	/*
	 * if VM is already running, attempt to kmem_alloc vm_page structures
	 */

	if (!preload) {
		panic("Tried to add RAM after uvm_page_init");
	}

	return NULL;
}

/*
 * uvm_page_physunload: unload physical memory and return it to
 * caller.
 */
bool
uvm_page_physunload(uvm_physseg_t psi, int freelist, paddr_t *paddrp)
{
	int x;
	struct uvm_physseg *seg;

	uvm_post_preload_check();

	seg = VM_PHYSMEM_PTR(psi);

	if (seg->free_list != freelist) {
		paddrp = NULL;
		return false;
	}

	/* try from front */
	if (seg->avail_start == seg->start &&
	    seg->avail_start < seg->avail_end) {
		*paddrp = ctob(seg->avail_start);
		seg->avail_start++;
		seg->start++;
		/* nothing left?   nuke it */
		if (seg->avail_start == seg->end) {
			if (vm_nphysmem == 1)
				panic("uvm_page_physget: out of memory!");
			vm_nphysmem--;
			for (x = psi ; x < vm_nphysmem ; x++)
				/* structure copy */
				VM_PHYSMEM_PTR_SWAP(x, x + 1);
		}
		return (true);
	}

	/* try from rear */
	if (seg->avail_end == seg->end &&
	    seg->avail_start < seg->avail_end) {
		*paddrp = ctob(seg->avail_end - 1);
		seg->avail_end--;
		seg->end--;
		/* nothing left?   nuke it */
		if (seg->avail_end == seg->start) {
			if (vm_nphysmem == 1)
				panic("uvm_page_physget: out of memory!");
			vm_nphysmem--;
			for (x = psi ; x < vm_nphysmem ; x++)
				/* structure copy */
				VM_PHYSMEM_PTR_SWAP(x, x + 1);
		}
		return (true);
	}

	return false;
}

bool
uvm_page_physunload_force(uvm_physseg_t psi, int freelist, paddr_t *paddrp)
{
	int x;
	struct uvm_physseg *seg;

	uvm_post_preload_check();

	seg = VM_PHYSMEM_PTR(psi);

	/* any room in this bank? */
	if (seg->avail_start >= seg->avail_end) {
		paddrp = NULL;
		return false; /* nope */
	}

	*paddrp = ctob(seg->avail_start);
	seg->avail_start++;
	/* truncate! */
	seg->start = seg->avail_start;

	/* nothing left?   nuke it */
	if (seg->avail_start == seg->end) {
		if (vm_nphysmem == 1)
			panic("uvm_page_physget: out of memory!");
		vm_nphysmem--;
		for (x = psi ; x < vm_nphysmem ; x++)
			/* structure copy */
			VM_PHYSMEM_PTR_SWAP(x, x + 1);
	}
	return (true);
}

bool
uvm_physseg_plug(paddr_t pfn, size_t pages, uvm_physseg_t *psp)
{
	int lcv;
	struct vm_page *pgs;
	struct uvm_physseg *ps;

#ifdef DEBUG
	paddr_t off;
	uvm_physseg_t upm;
	upm = uvm_physseg_find(pfn, &off);

	if (uvm_physseg_valid_p(upm)) /* XXX; do we allow "update" plugs ? */
		return false;
#endif

	paddr_t start = pfn;
	paddr_t end = pfn + pages;
	paddr_t avail_start = start;
	paddr_t avail_end = end;

	if (uvmexp.pagesize == 0)
		panic("uvm_page_physload: page size not set!");

	/*
	 * do we have room?
	 */

	if (vm_nphysmem == VM_PHYSSEG_MAX) {
		printf("uvm_page_physload: unable to load physical memory "
		    "segment\n");
		printf("\t%d segments allocated, ignoring 0x%llx -> 0x%llx\n",
		    VM_PHYSSEG_MAX, (long long)start, (long long)end);
		printf("\tincrease VM_PHYSSEG_MAX\n");
		if (psp != NULL)
			*psp = UVM_PHYSSEG_TYPE_INVALID_OVERFLOW;
		return false;
	}

	/*
	 * check to see if this is a "preload" (i.e. uvm_page_init hasn't been
	 * called yet, so kmem is not available).
	 */
	pgs = uvm_post_preload_check();

	/*
	 * now insert us in the proper place in vm_physmem[]
	 */

#if (VM_PHYSSEG_STRAT == VM_PSTRAT_RANDOM)
	/* random: put it at the end (easy!) */
	ps = VM_PHYSMEM_PTR(vm_nphysmem);
	lcv = vm_nphysmem;
#elif (VM_PHYSSEG_STRAT == VM_PSTRAT_BSEARCH)
	{
		int x;
		/* sort by address for binary search */
		for (lcv = 0 ; lcv < vm_nphysmem ; lcv++)
			if (start < VM_PHYSMEM_PTR(lcv)->start)
				break;
		ps = VM_PHYSMEM_PTR(lcv);
		/* move back other entries, if necessary ... */
		for (x = vm_nphysmem ; x > lcv ; x--)
			/* structure copy */
			VM_PHYSMEM_PTR_SWAP(x, x - 1);
	}
#elif (VM_PHYSSEG_STRAT == VM_PSTRAT_BIGFIRST)
	{
		int x;
		/* sort by largest segment first */
		for (lcv = 0 ; lcv < vm_nphysmem ; lcv++)
			if ((end - start) >
			    (VM_PHYSMEM_PTR(lcv)->end - VM_PHYSMEM_PTR(lcv)->start))
				break;
		ps = VM_PHYSMEM_PTR(lcv);
		/* move back other entries, if necessary ... */
		for (x = vm_nphysmem ; x > lcv ; x--)
			/* structure copy */
			VM_PHYSMEM_PTR_SWAP(x, x - 1);
	}
#else
	panic("uvm_page_physload: unknown physseg strategy selected!");
#endif

	ps->start = start;
	ps->end = end;
	ps->avail_start = avail_start;
	ps->avail_end = avail_end;

	ps->pgs = pgs;

	vm_nphysmem++;

	if (psp != NULL)
		*psp = lcv;

	return true;
}

/*
 * when VM_PHYSSEG_MAX is 1, we can simplify these functions
 */

#if VM_PHYSSEG_MAX == 1
static inline int vm_physseg_find_contig(struct uvm_physseg *, int, paddr_t, psize_t *);
#elif (VM_PHYSSEG_STRAT == VM_PSTRAT_BSEARCH)
static inline int vm_physseg_find_bsearch(struct uvm_physseg *, int, paddr_t, psize_t *);
#else
static inline int vm_physseg_find_linear(struct uvm_physseg *, int, paddr_t, psize_t *);
#endif

/*
 * vm_physseg_find: find vm_physseg structure that belongs to a PA
 */
int
uvm_physseg_find(paddr_t pframe, psize_t *offp)
{

#if VM_PHYSSEG_MAX == 1
	return vm_physseg_find_contig(vm_physmem, vm_nphysseg, pframe, offp);
#elif (VM_PHYSSEG_STRAT == VM_PSTRAT_BSEARCH)
	return vm_physseg_find_bsearch(vm_physmem, vm_nphysseg, pframe, offp);
#else
	return vm_physseg_find_linear(vm_physmem, vm_nphysseg, pframe, offp);
#endif
}

#if VM_PHYSSEG_MAX == 1
static inline int
vm_physseg_find_contig(struct uvm_physseg *segs, int nsegs, paddr_t pframe, psize_t *offp)
{

	/* 'contig' case */
	if (pframe >= segs[0].start && pframe < segs[0].end) {
		if (offp)
			*offp = pframe - segs[0].start;
		return(0);
	}
	return(-1);
}

#elif (VM_PHYSSEG_STRAT == VM_PSTRAT_BSEARCH)

static inline int
vm_physseg_find_bsearch(struct uvm_physseg *segs, int nsegs, paddr_t pframe, psize_t *offp)
{
	/* binary search for it */
	int	start, len, guess;

	/*
	 * if try is too large (thus target is less than try) we reduce
	 * the length to trunc(len/2) [i.e. everything smaller than "try"]
	 *
	 * if the try is too small (thus target is greater than try) then
	 * we set the new start to be (try + 1).   this means we need to
	 * reduce the length to (round(len/2) - 1).
	 *
	 * note "adjust" below which takes advantage of the fact that
	 *  (round(len/2) - 1) == trunc((len - 1) / 2)
	 * for any value of len we may have
	 */

	for (start = 0, len = nsegs ; len != 0 ; len = len / 2) {
		guess = start + (len / 2);	/* try in the middle */

		/* start past our try? */
		if (pframe >= segs[guess].start) {
			/* was try correct? */
			if (pframe < segs[guess].end) {
				if (offp)
					*offp = pframe - segs[guess].start;
				return guess;            /* got it */
			}
			start = guess + 1;	/* next time, start here */
			len--;			/* "adjust" */
		} else {
			/*
			 * pframe before try, just reduce length of
			 * region, done in "for" loop
			 */
		}
	}
	return(-1);
}

#else

static inline int
vm_physseg_find_linear(struct uvm_physseg *segs, int nsegs, paddr_t pframe, psize_t *offp)
{
	/* linear search for it */
	int	lcv;

	for (lcv = 0; lcv < nsegs; lcv++) {
		if (pframe >= segs[lcv].start &&
		    pframe < segs[lcv].end) {
			if (offp)
				*offp = pframe - segs[lcv].start;
			return(lcv);		   /* got it */
		}
	}
	return(-1);
}
#endif
#endif /* UVM_HOTPLUG */

bool
uvm_physseg_valid_p(uvm_physseg_t upm)
{
	struct uvm_physseg *ps;

	if (upm == UVM_PHYSSEG_TYPE_INVALID ||
	    upm == UVM_PHYSSEG_TYPE_INVALID_EMPTY ||
	    upm == UVM_PHYSSEG_TYPE_INVALID_OVERFLOW)
		return false;

	/*
	 * This is the delicate init dance -
	 * needs to go with the dance.
	 */
	if (uvm.page_init_done != true)
		return true;

	ps = HANDLE_TO_PHYSSEG_NODE(upm);

	/* Extra checks needed only post uvm_page_init() */
	if (ps->pgs == NULL)
		return false;

	/* XXX: etc. */

	return true;

}

/*
 * Boot protocol dictates that these must be able to return partially
 * initialised segments.
 */
paddr_t
uvm_physseg_get_start(uvm_physseg_t upm)
{
	if (uvm_physseg_valid_p(upm) == false)
		return (paddr_t) -1;

	return HANDLE_TO_PHYSSEG_NODE(upm)->start;
}

paddr_t
uvm_physseg_get_end(uvm_physseg_t upm)
{
	if (uvm_physseg_valid_p(upm) == false)
		return (paddr_t) -1;

	return HANDLE_TO_PHYSSEG_NODE(upm)->end;
}

paddr_t
uvm_physseg_get_avail_start(uvm_physseg_t upm)
{
	if (uvm_physseg_valid_p(upm) == false)
		return (paddr_t) -1;

	return HANDLE_TO_PHYSSEG_NODE(upm)->avail_start;
}

#if defined(PMAP_STEAL_MEMORY)
void
uvm_physseg_set_avail_start(uvm_physseg_t upm, paddr_t avail_start)
{
	KASSERT(uvm_physseg_valid_p(upm));
	HANDLE_TO_PHYSSEG_NODE(upm)->avail_start = avail_start;
}
#endif

paddr_t
uvm_physseg_get_avail_end(uvm_physseg_t upm)
{
	if (uvm_physseg_valid_p(upm) == false)
		return (paddr_t) -1;

	return HANDLE_TO_PHYSSEG_NODE(upm)->avail_end;
}

struct vm_page *
uvm_physseg_get_pg(uvm_physseg_t upm, paddr_t idx)
{
	KASSERT(uvm_physseg_valid_p(upm));
	return &HANDLE_TO_PHYSSEG_NODE(upm)->pgs[idx];
}

#ifdef __HAVE_PMAP_PHYSSEG
struct pmap_physseg *
uvm_physseg_get_pmseg(uvm_physseg_t upm)
{
	KASSERT(uvm_physseg_valid_p(upm));
	return &(HANDLE_TO_PHYSSEG_NODE(upm)->pmseg);
}
#endif

int
uvm_physseg_get_free_list(uvm_physseg_t upm)
{
	KASSERT(uvm_physseg_valid_p(upm));
	return HANDLE_TO_PHYSSEG_NODE(upm)->free_list;
}

u_int
uvm_physseg_get_start_hint(uvm_physseg_t upm)
{
	KASSERT(uvm_physseg_valid_p(upm));
	return HANDLE_TO_PHYSSEG_NODE(upm)->start_hint;
}

bool
uvm_physseg_set_start_hint(uvm_physseg_t upm, u_int start_hint)
{
	if (uvm_physseg_valid_p(upm) == false)
		return false;

	HANDLE_TO_PHYSSEG_NODE(upm)->start_hint = start_hint;
	return true;
}

void
uvm_physseg_init_seg(uvm_physseg_t upm, struct vm_page *pgs)
{
	psize_t i;
	psize_t n;
	paddr_t paddr;
	struct uvm_physseg *seg;

	KASSERT(upm != UVM_PHYSSEG_TYPE_INVALID && pgs != NULL);

	seg = HANDLE_TO_PHYSSEG_NODE(upm);
	KASSERT(seg != NULL);
	KASSERT(seg->pgs == NULL);

	n = seg->end - seg->start;
	seg->pgs = pgs;

	/* init and free vm_pages (we've already zeroed them) */
	paddr = ctob(seg->start);
	for (i = 0 ; i < n ; i++, paddr += PAGE_SIZE) {
		seg->pgs[i].phys_addr = paddr;
#ifdef __HAVE_VM_PAGE_MD
		VM_MDPAGE_INIT(&seg->pgs[i]);
#endif
		if (atop(paddr) >= seg->avail_start &&
		    atop(paddr) < seg->avail_end) {
			uvmexp.npages++;
			mutex_enter(&uvm_pageqlock);
			/* add page to free pool */
			uvm_pagefree(&seg->pgs[i]);
			mutex_exit(&uvm_pageqlock);
		}
	}
}

void
uvm_physseg_seg_chomp_slab(uvm_physseg_t upm, struct vm_page *pgs, size_t n)
{
	struct uvm_physseg *seg = HANDLE_TO_PHYSSEG_NODE(upm);

	/* max number of pre-boot unplug()s allowed */
#define UVM_PHYSSEG_BOOT_UNPLUG_MAX VM_PHYSSEG_MAX

	static char btslab_ex_storage[EXTENT_FIXED_STORAGE_SIZE(UVM_PHYSSEG_BOOT_UNPLUG_MAX)];

	if (__predict_false(uvm.page_init_done == false)) {
		seg->ext = extent_create("Boot time slab", (u_long) pgs, (u_long) (pgs + n),
		    (void *)btslab_ex_storage, sizeof(btslab_ex_storage), 0);
	} else {
		seg->ext = extent_create("Hotplug slab", (u_long) pgs, (u_long) (pgs + n), NULL, 0, 0);
	}

	KASSERT(seg->ext != NULL);

}

struct vm_page *
uvm_physseg_seg_alloc_from_slab(uvm_physseg_t upm, size_t pages)
{
	int err;
	struct uvm_physseg *seg;
	struct vm_page *pgs = NULL;

	seg = HANDLE_TO_PHYSSEG_NODE(upm);

	KASSERT(pages > 0);

	if (__predict_false(seg->ext == NULL)) {
		/*
		 * This is a situation unique to boot time.
		 * It shouldn't happen at any point other than from
		 * the first uvm_page.c:uvm_page_init() call
		 * Since we're in a loop, we can get away with the
		 * below.
		 */
		KASSERT(uvm.page_init_done != true);

		seg->ext = HANDLE_TO_PHYSSEG_NODE(uvm_physseg_get_prev(upm))->ext;

		KASSERT(seg->ext != NULL);
	}

	/* We allocate enough for this segment */
	err = extent_alloc(seg->ext, sizeof(*pgs) * pages, 1, 0, EX_BOUNDZERO, (u_long *)&pgs);

	if (err != 0) {
#ifdef DEBUG
		printf("%s: extent_alloc failed with error: %d \n",
		    __func__, err);
#endif
	}

	return pgs;
}

/*
 * uvm_page_physload: load physical memory into VM system
 *
 * => all args are PFs
 * => all pages in start/end get vm_page structures
 * => areas marked by avail_start/avail_end get added to the free page pool
 * => we are limited to VM_PHYSSEG_MAX physical memory segments
 */

uvm_physseg_t
uvm_page_physload(paddr_t start, paddr_t end, paddr_t avail_start,
    paddr_t avail_end, int free_list)
{
	struct uvm_physseg *ps;
	uvm_physseg_t upm;

	if (__predict_true(uvm.page_init_done == true))
		panic("%s: unload attempted after uvm_page_init()\n", __func__);
	if (uvmexp.pagesize == 0)
		panic("uvm_page_physload: page size not set!");
	if (free_list >= VM_NFREELIST || free_list < VM_FREELIST_DEFAULT)
		panic("uvm_page_physload: bad free list %d", free_list);
	if (start >= end)
		panic("uvm_page_physload: start >= end");

	if (uvm_physseg_plug(start, end - start, &upm) == false) {
		panic("uvm_physseg_plug() failed at boot.");
		/* NOTREACHED */
		return UVM_PHYSSEG_TYPE_INVALID; /* XXX: correct type */
	}

	ps = HANDLE_TO_PHYSSEG_NODE(upm);

	/* Legacy */
	ps->avail_start = avail_start;
	ps->avail_end = avail_end;

	ps->free_list = free_list; /* XXX: */


	return upm;
}

bool
uvm_physseg_unplug(paddr_t pfn, size_t pages)
{
	uvm_physseg_t upm;
	paddr_t off = 0, start, end;
	struct uvm_physseg *seg;

	upm = uvm_physseg_find(pfn, &off);

	if (!uvm_physseg_valid_p(upm)) {
		printf("%s: Tried to unplug from unknown offset\n", __func__);
		return false;
	}

	seg = HANDLE_TO_PHYSSEG_NODE(upm);

	start = uvm_physseg_get_start(upm);
	end = uvm_physseg_get_end(upm);

	if (end < (pfn + pages)) {
		printf("%s: Tried to unplug oversized span \n", __func__);
		return false;
	}

#ifndef DIAGNOSTIC
	(void) start;
#endif
	KASSERT(pfn == start + off); /* sanity */

	if (__predict_true(uvm.page_init_done == true)) {
		/* XXX: KASSERT() that seg->pgs[] are not on any uvm lists */
		if (extent_free(seg->ext, (u_long)(seg->pgs + off), sizeof(struct vm_page) * pages, EX_MALLOCOK | EX_NOWAIT) != 0)
			return false;
	}

	if (off == 0 && (pfn + pages) == end) {
#if defined(UVM_HOTPLUG) /* rbtree implementation */
		int segcount = 0;
		struct uvm_physseg *current_ps;
		/* Complete segment */
		if (uvm_physseg_graph.nentries == 1)
			panic("%s: out of memory!", __func__);

		if (__predict_true(uvm.page_init_done == true)) {
			RB_TREE_FOREACH(current_ps, &(uvm_physseg_graph.rb_tree)) {
				if (seg->ext == current_ps->ext)
					segcount++;
			}
			KASSERT(segcount > 0);

			if (segcount == 1) {
				extent_destroy(seg->ext);
			}

			/*
			 * We assume that the unplug will succeed from
			 *  this point onwards
			 */
			uvmexp.npages -= (int) pages;
		}

		rb_tree_remove_node(&(uvm_physseg_graph.rb_tree), upm);
		memset(seg, 0, sizeof(struct uvm_physseg));
		uvm_physseg_free(seg, sizeof(struct uvm_physseg));
		uvm_physseg_graph.nentries--;
#else /* UVM_HOTPLUG */
		int x;
		if (vm_nphysmem == 1)
			panic("uvm_page_physget: out of memory!");
		vm_nphysmem--;
		for (x = upm ; x < vm_nphysmem ; x++)
			/* structure copy */
			VM_PHYSMEM_PTR_SWAP(x, x + 1);
#endif /* UVM_HOTPLUG */
		/* XXX: KASSERT() that seg->pgs[] are not on any uvm lists */
		return true;
	}

	if (off > 0 &&
	    (pfn + pages) < end) {
#if defined(UVM_HOTPLUG) /* rbtree implementation */
		/* middle chunk - need a new segment */
		struct uvm_physseg *ps, *current_ps;
		ps = uvm_physseg_alloc(sizeof (struct uvm_physseg));
		if (ps == NULL) {
			printf("%s: Unable to allocated new fragment vm_physseg \n",
			    __func__);
			return false;
		}

		/* Remove middle chunk */
		if (__predict_true(uvm.page_init_done == true)) {
			KASSERT(seg->ext != NULL);
			ps->ext = seg->ext;

			/* XXX: KASSERT() that seg->pgs[] are not on any uvm lists */
			/*
			 * We assume that the unplug will succeed from
			 *  this point onwards
			 */
			uvmexp.npages -= (int) pages;
		}

		ps->start = pfn + pages;
		ps->avail_start = ps->start; /* XXX: Legacy */

		ps->end = seg->end;
		ps->avail_end = ps->end; /* XXX: Legacy */

		seg->end = pfn;
		seg->avail_end = seg->end; /* XXX: Legacy */


		/*
		 * The new pgs array points to the beginning of the
		 * tail fragment.
		 */
		if (__predict_true(uvm.page_init_done == true))
			ps->pgs = seg->pgs + off + pages;

		current_ps = rb_tree_insert_node(&(uvm_physseg_graph.rb_tree), ps);
		if (current_ps != ps) {
			panic("uvm_page_physload: Duplicate address range detected!");
		}
		uvm_physseg_graph.nentries++;
#else /* UVM_HOTPLUG */
		panic("%s: can't unplug() from the middle of a segment without"
		    "UVM_HOTPLUG\n",  __func__);
		/* NOTREACHED */
#endif /* UVM_HOTPLUG */
		return true;
	}

	if (off == 0 && (pfn + pages) < end) {
		/* Remove front chunk */
		if (__predict_true(uvm.page_init_done == true)) {
			/* XXX: KASSERT() that seg->pgs[] are not on any uvm lists */
			/*
			 * We assume that the unplug will succeed from
			 *  this point onwards
			 */
			uvmexp.npages -= (int) pages;
		}

		/* Truncate */
		seg->start = pfn + pages;
		seg->avail_start = seg->start; /* XXX: Legacy */

		/*
		 * Move the pgs array start to the beginning of the
		 * tail end.
		 */
		if (__predict_true(uvm.page_init_done == true))
			seg->pgs += pages;

		return true;
	}

	if (off > 0 && (pfn + pages) == end) {
		/* back chunk */


		/* Truncate! */
		seg->end = pfn;
		seg->avail_end = seg->end; /* XXX: Legacy */

		uvmexp.npages -= (int) pages;

		return true;
	}

	printf("%s: Tried to unplug unknown range \n", __func__);

	return false;
}