common/vm/vm_usage.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*
 * vm_usage
 *
 * This file implements the getvmusage() private system call.
 * getvmusage() counts the amount of resident memory pages and swap
 * reserved by the specified process collective. A "process collective" is
 * the set of processes owned by a particular, zone, project, task, or user.
 *
 * rss and swap are counted so that for a given process collective, a page is
 * only counted once.  For example, this means that if multiple processes in
 * the same project map the same page, then the project will only be charged
 * once for that page.  On the other hand, if two processes in different
 * projects map the same page, then both projects will be charged
 * for the page.
 *
 * The vm_getusage() calculation is implemented so that the first thread
 * performs the rss/swap counting. Other callers will wait for that thread to
 * finish, copying the results.  This enables multiple rcapds and prstats to
 * consume data from the same calculation.  The results are also cached so that
 * a caller interested in recent results can just copy them instead of starting
 * a new calculation. The caller passes the maximium age (in seconds) of the
 * data.  If the cached data is young enough, the cache is copied, otherwise,
 * a new calculation is executed and the cache is replaced with the new
 * data.
 *
 * The rss calculation for each process collective is as follows:
 *
 *   - Inspect flags, determine if counting rss for zones, projects, tasks,
 *     and/or users.
 *   - For each proc:
 *	- Figure out proc's collectives (zone, project, task, and/or user).
 *	- For each seg in proc's address space:
 *		- If seg is private:
 *			- Lookup anons in the amp.
 *			- For incore pages not previously visited each of the
 *			  proc's collectives, add incore pagesize to each.
 *			  collective.
 *			  Anon's with a refcnt of 1 can be assummed to be not
 *			  previously visited.
 *			- For address ranges without anons in the amp:
 *				- Lookup pages in underlying vnode.
 *				- For incore pages not previously visiting for
 *				  each of the proc's collectives, add incore
 *				  pagesize to each collective.
 *		- If seg is shared:
 *			- Lookup pages in the shared amp or vnode.
 *			- For incore pages not previously visited for each of
 *			  the proc's collectives, add incore pagesize to each
 *			  collective.
 *
 * Swap is reserved by private segments, and shared anonymous segments.
 * The only shared anon segments which do not reserve swap are ISM segments
 * and schedctl segments, both of which can be identified by having
 * amp->swresv == 0.
 *
 * The swap calculation for each collective is as follows:
 *
 *   - Inspect flags, determine if counting rss for zones, projects, tasks,
 *     and/or users.
 *   - For each proc:
 *	- Figure out proc's collectives (zone, project, task, and/or user).
 *	- For each seg in proc's address space:
 *		- If seg is private:
 *			- Add svd->swresv pages to swap count for each of the
 *			  proc's collectives.
 *		- If seg is anon, shared, and amp->swresv != 0
 *			- For address ranges in amp not previously visited for
 *			  each of the proc's collectives, add size of address
 *			  range to the swap count for each collective.
 *
 * These two calculations are done simultaneously, with most of the work
 * being done in vmu_calculate_seg().  The results of the calculation are
 * copied into "vmu_data.vmu_cache_results".
 *
 * To perform the calculation, various things are tracked and cached:
 *
 *    - incore/not-incore page ranges for all vnodes.
 *	(vmu_data.vmu_all_vnodes_hash)
 *	This eliminates looking up the same page more than once.
 *
 *    - incore/not-incore page ranges for all shared amps.
 *	(vmu_data.vmu_all_amps_hash)
 *	This eliminates looking up the same page more than once.
 *
 *    - visited page ranges for each collective.
 *	   - per vnode (entity->vme_vnode_hash)
 *	   - per shared amp (entity->vme_amp_hash)
 *	For accurate counting of map-shared and COW-shared pages.
 *
 *    - visited private anons (refcnt > 1) for each collective.
 *	(entity->vme_anon_hash)
 *	For accurate counting of COW-shared pages.
 *
 * The common accounting structure is the vmu_entity_t, which represents
 * collectives:
 *
 *    - A zone.
 *    - A project, task, or user within a zone.
 *    - The entire system (vmu_data.vmu_system).
 *    - Each collapsed (col) project and user.  This means a given projid or
 *	uid, regardless of which zone the process is in.  For instance,
 *      project 0 in the global zone and project 0 in a non global zone are
 *	the same collapsed project.
 *
 *  Each entity structure tracks which pages have been already visited for
 *  that entity (via previously inspected processes) so that these pages are
 *  not double counted.
 */

#include <sys/errno.h>
#include <sys/types.h>
#include <sys/zone.h>
#include <sys/proc.h>
#include <sys/project.h>
#include <sys/task.h>
#include <sys/thread.h>
#include <sys/time.h>
#include <sys/mman.h>
#include <sys/modhash.h>
#include <sys/modhash_impl.h>
#include <sys/shm.h>
#include <sys/swap.h>
#include <sys/synch.h>
#include <sys/systm.h>
#include <sys/var.h>
#include <sys/vm_usage.h>
#include <sys/zone.h>
#include <sys/sunddi.h>
#include <sys/avl.h>
#include <vm/anon.h>
#include <vm/as.h>
#include <vm/seg_vn.h>
#include <vm/seg_spt.h>

#define	VMUSAGE_HASH_SIZE		512

#define	VMUSAGE_TYPE_VNODE		1
#define	VMUSAGE_TYPE_AMP		2
#define	VMUSAGE_TYPE_ANON		3

#define	VMUSAGE_BOUND_UNKNOWN		0
#define	VMUSAGE_BOUND_INCORE		1
#define	VMUSAGE_BOUND_NOT_INCORE	2

#define	ISWITHIN(node, addr)	((node)->vmb_start <= addr && \
				    (node)->vmb_end >= addr ? 1 : 0)

/*
 * bounds for vnodes and shared amps
 * Each bound is either entirely incore, entirely not in core, or
 * entirely unknown.  bounds are stored in an avl tree sorted by start member
 * when in use, otherwise (free or temporary lists) they're strung
 * together off of vmb_next.
 */
typedef struct vmu_bound {
	avl_node_t vmb_node;
	struct vmu_bound *vmb_next; /* NULL in tree else on free or temp list */
	pgcnt_t vmb_start;  /* page offset in vnode/amp on which bound starts */
	pgcnt_t	vmb_end;    /* page offset in vnode/amp on which bound ends */
	char	vmb_type;   /* One of VMUSAGE_BOUND_* */
} vmu_bound_t;

/*
 * hash of visited objects (vnodes or shared amps)
 * key is address of vnode or amp.  Bounds lists known incore/non-incore
 * bounds for vnode/amp.
 */
typedef struct vmu_object {
	struct vmu_object	*vmo_next;	/* free list */
	caddr_t		vmo_key;
	short		vmo_type;
	avl_tree_t	vmo_bounds;
} vmu_object_t;

/*
 * Entity by which to count results.
 *
 * The entity structure keeps the current rss/swap counts for each entity
 * (zone, project, etc), and hashes of vm structures that have already
 * been visited for the entity.
 *
 * vme_next:	links the list of all entities currently being counted by
 *		vmu_calculate().
 *
 * vme_next_calc: links the list of entities related to the current process
 *		 being counted by vmu_calculate_proc().
 *
 * vmu_calculate_proc() walks all processes.  For each process, it makes a
 * list of the entities related to that process using vme_next_calc.  This
 * list changes each time vmu_calculate_proc() is called.
 *
 */
typedef struct vmu_entity {
	struct vmu_entity *vme_next;
	struct vmu_entity *vme_next_calc;
	mod_hash_t	*vme_vnode_hash; /* vnodes visited for entity */
	mod_hash_t	*vme_amp_hash;	 /* shared amps visited for entity */
	mod_hash_t	*vme_anon_hash;	 /* COW anons visited for entity */
	vmusage_t	vme_result;	 /* identifies entity and results */
} vmu_entity_t;

/*
 * Hash of entities visited within a zone, and an entity for the zone
 * itself.
 */
typedef struct vmu_zone {
	struct vmu_zone	*vmz_next;	/* free list */
	id_t		vmz_id;
	vmu_entity_t	*vmz_zone;
	mod_hash_t	*vmz_projects_hash;
	mod_hash_t	*vmz_tasks_hash;
	mod_hash_t	*vmz_rusers_hash;
	mod_hash_t	*vmz_eusers_hash;
} vmu_zone_t;

/*
 * Cache of results from last calculation
 */
typedef struct vmu_cache {
	vmusage_t	*vmc_results;	/* Results from last call to */
					/* vm_getusage(). */
	uint64_t	vmc_nresults;	/* Count of cached results */
	uint64_t	vmc_refcnt;	/* refcnt for free */
	uint_t		vmc_flags;	/* Flags for vm_getusage() */
	hrtime_t	vmc_timestamp;	/* when cache was created */
} vmu_cache_t;

/*
 * top level rss info for the system
 */
typedef struct vmu_data {
	kmutex_t	vmu_lock;		/* Protects vmu_data */
	kcondvar_t	vmu_cv;			/* Used to signal threads */
						/* Waiting for */
						/* Rss_calc_thread to finish */
	vmu_entity_t	*vmu_system;		/* Entity for tracking */
						/* rss/swap for all processes */
						/* in all zones */
	mod_hash_t	*vmu_zones_hash;	/* Zones visited */
	mod_hash_t	*vmu_projects_col_hash; /* These *_col_hash hashes */
	mod_hash_t	*vmu_rusers_col_hash;	/* keep track of entities, */
	mod_hash_t	*vmu_eusers_col_hash;	/* ignoring zoneid, in order */
						/* to implement VMUSAGE_COL_* */
						/* flags, which aggregate by */
						/* project or user regardless */
						/* of zoneid. */
	mod_hash_t	*vmu_all_vnodes_hash;	/* System wide visited vnodes */
						/* to track incore/not-incore */
	mod_hash_t	*vmu_all_amps_hash;	/* System wide visited shared */
						/* amps to track incore/not- */
						/* incore */
	vmu_entity_t	*vmu_entities;		/* Linked list of entities */
	size_t		vmu_nentities;		/* Count of entities in list */
	vmu_cache_t	*vmu_cache;		/* Cached results */
	kthread_t	*vmu_calc_thread;	/* NULL, or thread running */
						/* vmu_calculate() */
	uint_t		vmu_calc_flags;		/* Flags being using by */
						/* currently running calc */
						/* thread */
	uint_t		vmu_pending_flags;	/* Flags of vm_getusage() */
						/* threads waiting for */
						/* calc thread to finish */
	uint_t		vmu_pending_waiters;	/* Number of threads waiting */
						/* for calc thread */
	vmu_bound_t	*vmu_free_bounds;
	vmu_object_t	*vmu_free_objects;
	vmu_entity_t	*vmu_free_entities;
	vmu_zone_t	*vmu_free_zones;
} vmu_data_t;

extern struct as kas;
extern proc_t *practive;
extern zone_t *global_zone;
extern struct seg_ops segvn_ops;
extern struct seg_ops segspt_shmops;

static vmu_data_t vmu_data;
static kmem_cache_t *vmu_bound_cache;
static kmem_cache_t *vmu_object_cache;

/*
 * Comparison routine for AVL tree. We base our comparison on vmb_start.
 */
static int
bounds_cmp(const void *bnd1, const void *bnd2)
{
	const vmu_bound_t *bound1 = bnd1;
	const vmu_bound_t *bound2 = bnd2;

	if (bound1->vmb_start == bound2->vmb_start) {
		return (0);
	}
	if (bound1->vmb_start < bound2->vmb_start) {
		return (-1);
	}

	return (1);
}

/*
 * Save a bound on the free list.
 */
static void
vmu_free_bound(vmu_bound_t *bound)
{
	bound->vmb_next = vmu_data.vmu_free_bounds;
	bound->vmb_start = 0;
	bound->vmb_end = 0;
	bound->vmb_type = 0;
	vmu_data.vmu_free_bounds = bound;
}

/*
 * Free an object, and all visited bound info.
 */
static void
vmu_free_object(mod_hash_val_t val)
{
	vmu_object_t *obj = (vmu_object_t *)val;
	avl_tree_t *tree = &(obj->vmo_bounds);
	vmu_bound_t *bound;
	void *cookie = NULL;

	while ((bound = avl_destroy_nodes(tree, &cookie)) != NULL)
		vmu_free_bound(bound);
	avl_destroy(tree);

	obj->vmo_type = 0;
	obj->vmo_next = vmu_data.vmu_free_objects;
	vmu_data.vmu_free_objects = obj;
}

/*
 * Free an entity, and hashes of visited objects for that entity.
 */
static void
vmu_free_entity(mod_hash_val_t val)
{
	vmu_entity_t *entity = (vmu_entity_t *)val;

	if (entity->vme_vnode_hash != NULL)
		i_mod_hash_clear_nosync(entity->vme_vnode_hash);
	if (entity->vme_amp_hash != NULL)
		i_mod_hash_clear_nosync(entity->vme_amp_hash);
	if (entity->vme_anon_hash != NULL)
		i_mod_hash_clear_nosync(entity->vme_anon_hash);

	entity->vme_next = vmu_data.vmu_free_entities;
	vmu_data.vmu_free_entities = entity;
}

/*
 * Free zone entity, and all hashes of entities inside that zone,
 * which are projects, tasks, and users.
 */
static void
vmu_free_zone(mod_hash_val_t val)
{
	vmu_zone_t *zone = (vmu_zone_t *)val;

	if (zone->vmz_zone != NULL) {
		vmu_free_entity((mod_hash_val_t)zone->vmz_zone);
		zone->vmz_zone = NULL;
	}
	if (zone->vmz_projects_hash != NULL)
		i_mod_hash_clear_nosync(zone->vmz_projects_hash);
	if (zone->vmz_tasks_hash != NULL)
		i_mod_hash_clear_nosync(zone->vmz_tasks_hash);
	if (zone->vmz_rusers_hash != NULL)
		i_mod_hash_clear_nosync(zone->vmz_rusers_hash);
	if (zone->vmz_eusers_hash != NULL)
		i_mod_hash_clear_nosync(zone->vmz_eusers_hash);
	zone->vmz_next = vmu_data.vmu_free_zones;
	vmu_data.vmu_free_zones = zone;
}

/*
 * Initialize synchronization primitives and hashes for system-wide tracking
 * of visited vnodes and shared amps.  Initialize results cache.
 */
void
vm_usage_init()
{
	mutex_init(&vmu_data.vmu_lock, NULL, MUTEX_DEFAULT, NULL);
	cv_init(&vmu_data.vmu_cv, NULL, CV_DEFAULT, NULL);

	vmu_data.vmu_system = NULL;
	vmu_data.vmu_zones_hash = NULL;
	vmu_data.vmu_projects_col_hash = NULL;
	vmu_data.vmu_rusers_col_hash = NULL;
	vmu_data.vmu_eusers_col_hash = NULL;

	vmu_data.vmu_free_bounds = NULL;
	vmu_data.vmu_free_objects = NULL;
	vmu_data.vmu_free_entities = NULL;
	vmu_data.vmu_free_zones = NULL;

	vmu_data.vmu_all_vnodes_hash = mod_hash_create_ptrhash(
	    "vmusage vnode hash", VMUSAGE_HASH_SIZE, vmu_free_object,
	    sizeof (vnode_t));
	vmu_data.vmu_all_amps_hash = mod_hash_create_ptrhash(
	    "vmusage amp hash", VMUSAGE_HASH_SIZE, vmu_free_object,
	    sizeof (struct anon_map));
	vmu_data.vmu_projects_col_hash = mod_hash_create_idhash(
	    "vmusage collapsed project hash", VMUSAGE_HASH_SIZE,
	    vmu_free_entity);
	vmu_data.vmu_rusers_col_hash = mod_hash_create_idhash(
	    "vmusage collapsed ruser hash", VMUSAGE_HASH_SIZE,
	    vmu_free_entity);
	vmu_data.vmu_eusers_col_hash = mod_hash_create_idhash(
	    "vmusage collpased euser hash", VMUSAGE_HASH_SIZE,
	    vmu_free_entity);
	vmu_data.vmu_zones_hash = mod_hash_create_idhash(
	    "vmusage zone hash", VMUSAGE_HASH_SIZE, vmu_free_zone);

	vmu_bound_cache = kmem_cache_create("vmu_bound_cache",
	    sizeof (vmu_bound_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
	vmu_object_cache = kmem_cache_create("vmu_object_cache",
	    sizeof (vmu_object_t), 0, NULL, NULL, NULL, NULL, NULL, 0);

	vmu_data.vmu_entities = NULL;
	vmu_data.vmu_nentities = 0;

	vmu_data.vmu_cache = NULL;
	vmu_data.vmu_calc_thread = NULL;
	vmu_data.vmu_calc_flags = 0;
	vmu_data.vmu_pending_flags = 0;
	vmu_data.vmu_pending_waiters = 0;
}

/*
 * Allocate hashes for tracking vm objects visited for an entity.
 * Update list of entities.
 */
static vmu_entity_t *
vmu_alloc_entity(id_t id, int type, id_t zoneid)
{
	vmu_entity_t *entity;

	if (vmu_data.vmu_free_entities != NULL) {
		entity = vmu_data.vmu_free_entities;
		vmu_data.vmu_free_entities =
		    vmu_data.vmu_free_entities->vme_next;
		bzero(&entity->vme_result, sizeof (vmusage_t));
	} else {
		entity = kmem_zalloc(sizeof (vmu_entity_t), KM_SLEEP);
	}
	entity->vme_result.vmu_id = id;
	entity->vme_result.vmu_zoneid = zoneid;
	entity->vme_result.vmu_type = type;

	if (entity->vme_vnode_hash == NULL)
		entity->vme_vnode_hash = mod_hash_create_ptrhash(
		    "vmusage vnode hash", VMUSAGE_HASH_SIZE, vmu_free_object,
		    sizeof (vnode_t));

	if (entity->vme_amp_hash == NULL)
		entity->vme_amp_hash = mod_hash_create_ptrhash(
		    "vmusage amp hash", VMUSAGE_HASH_SIZE, vmu_free_object,
		    sizeof (struct anon_map));

	if (entity->vme_anon_hash == NULL)
		entity->vme_anon_hash = mod_hash_create_ptrhash(
		    "vmusage anon hash", VMUSAGE_HASH_SIZE,
		    mod_hash_null_valdtor, sizeof (struct anon));

	entity->vme_next = vmu_data.vmu_entities;
	vmu_data.vmu_entities = entity;
	vmu_data.vmu_nentities++;

	return (entity);
}

/*
 * Allocate a zone entity, and hashes for tracking visited vm objects
 * for projects, tasks, and users within that zone.
 */
static vmu_zone_t *
vmu_alloc_zone(id_t id)
{
	vmu_zone_t *zone;

	if (vmu_data.vmu_free_zones != NULL) {
		zone = vmu_data.vmu_free_zones;
		vmu_data.vmu_free_zones =
		    vmu_data.vmu_free_zones->vmz_next;
		zone->vmz_next = NULL;
		zone->vmz_zone = NULL;
	} else {
		zone = kmem_zalloc(sizeof (vmu_zone_t), KM_SLEEP);
	}

	zone->vmz_id = id;

	if ((vmu_data.vmu_calc_flags & (VMUSAGE_ZONE | VMUSAGE_ALL_ZONES)) != 0)
		zone->vmz_zone = vmu_alloc_entity(id, VMUSAGE_ZONE, id);

	if ((vmu_data.vmu_calc_flags & (VMUSAGE_PROJECTS |
	    VMUSAGE_ALL_PROJECTS)) != 0 && zone->vmz_projects_hash == NULL)
		zone->vmz_projects_hash = mod_hash_create_idhash(
		    "vmusage project hash", VMUSAGE_HASH_SIZE, vmu_free_entity);

	if ((vmu_data.vmu_calc_flags & (VMUSAGE_TASKS | VMUSAGE_ALL_TASKS))
	    != 0 && zone->vmz_tasks_hash == NULL)
		zone->vmz_tasks_hash = mod_hash_create_idhash(
		    "vmusage task hash", VMUSAGE_HASH_SIZE, vmu_free_entity);

	if ((vmu_data.vmu_calc_flags & (VMUSAGE_RUSERS | VMUSAGE_ALL_RUSERS))
	    != 0 && zone->vmz_rusers_hash == NULL)
		zone->vmz_rusers_hash = mod_hash_create_idhash(
		    "vmusage ruser hash", VMUSAGE_HASH_SIZE, vmu_free_entity);

	if ((vmu_data.vmu_calc_flags & (VMUSAGE_EUSERS | VMUSAGE_ALL_EUSERS))
	    != 0 && zone->vmz_eusers_hash == NULL)
		zone->vmz_eusers_hash = mod_hash_create_idhash(
		    "vmusage euser hash", VMUSAGE_HASH_SIZE, vmu_free_entity);

	return (zone);
}

/*
 * Allocate a structure for tracking visited bounds for a vm object.
 */
static vmu_object_t *
vmu_alloc_object(caddr_t key, int type)
{
	vmu_object_t *object;

	if (vmu_data.vmu_free_objects != NULL) {
		object = vmu_data.vmu_free_objects;
		vmu_data.vmu_free_objects =
		    vmu_data.vmu_free_objects->vmo_next;
	} else {
		object = kmem_cache_alloc(vmu_object_cache, KM_SLEEP);
	}

	object->vmo_next = NULL;
	object->vmo_key = key;
	object->vmo_type = type;
	avl_create(&(object->vmo_bounds), bounds_cmp, sizeof (vmu_bound_t), 0);

	return (object);
}

/*
 * Allocate and return a bound structure.
 */
static vmu_bound_t *
vmu_alloc_bound()
{
	vmu_bound_t *bound;

	if (vmu_data.vmu_free_bounds != NULL) {
		bound = vmu_data.vmu_free_bounds;
		vmu_data.vmu_free_bounds =
		    vmu_data.vmu_free_bounds->vmb_next;
	} else {
		bound = kmem_cache_alloc(vmu_bound_cache, KM_SLEEP);
	}

	bound->vmb_next = NULL;
	bound->vmb_start = 0;
	bound->vmb_end = 0;
	bound->vmb_type = 0;
	return (bound);
}

/*
 * vmu_find_insert_* functions implement hash lookup or allocate and
 * insert operations.
 */
static vmu_object_t *
vmu_find_insert_object(mod_hash_t *hash, caddr_t key, uint_t type)
{
	int ret;
	vmu_object_t *object;

	ret = i_mod_hash_find_nosync(hash, (mod_hash_key_t)key,
	    (mod_hash_val_t *)&object);
	if (ret != 0) {
		object = vmu_alloc_object(key, type);
		ret = i_mod_hash_insert_nosync(hash, (mod_hash_key_t)key,
		    (mod_hash_val_t)object, (mod_hash_hndl_t)0);
		ASSERT(ret == 0);
	}
	return (object);
}

static int
vmu_find_insert_anon(mod_hash_t *hash, caddr_t key)
{
	int ret;
	caddr_t val;

	ret = i_mod_hash_find_nosync(hash, (mod_hash_key_t)key,
	    (mod_hash_val_t *)&val);

	if (ret == 0)
		return (0);

	ret = i_mod_hash_insert_nosync(hash, (mod_hash_key_t)key,
	    (mod_hash_val_t)key, (mod_hash_hndl_t)0);

	ASSERT(ret == 0);

	return (1);
}

static vmu_entity_t *
vmu_find_insert_entity(mod_hash_t *hash, id_t id, uint_t type, id_t zoneid)
{
	int ret;
	vmu_entity_t *entity;

	ret = i_mod_hash_find_nosync(hash, (mod_hash_key_t)(uintptr_t)id,
	    (mod_hash_val_t *)&entity);
	if (ret != 0) {
		entity = vmu_alloc_entity(id, type, zoneid);
		ret = i_mod_hash_insert_nosync(hash,
		    (mod_hash_key_t)(uintptr_t)id, (mod_hash_val_t)entity,
		    (mod_hash_hndl_t)0);
		ASSERT(ret == 0);
	}
	return (entity);
}


/*
 * Returns list of object bounds between start and end.  New bounds inserted
 * by this call are given type.
 *
 * Returns the number of pages covered if new bounds are created.  Returns 0
 * if region between start/end consists of all existing bounds.
 */
static pgcnt_t
vmu_insert_lookup_object_bounds(vmu_object_t *ro, pgcnt_t start, pgcnt_t
    end, char type, vmu_bound_t **first, vmu_bound_t **last)
{
	avl_tree_t	*tree = &(ro->vmo_bounds);
	avl_index_t	where;
	vmu_bound_t	*walker, *tmp;
	pgcnt_t		ret = 0;

	ASSERT(start <= end);

	*first = *last = NULL;

	tmp = vmu_alloc_bound();
	tmp->vmb_start = start;
	tmp->vmb_type = type;

	/* Hopelessly optimistic case. */
	if (walker = avl_find(tree, tmp, &where)) {
		/* We got lucky. */
		vmu_free_bound(tmp);
		*first = walker;
	}

	if (walker == NULL) {
		/* Is start in the previous node? */
		walker = avl_nearest(tree, where, AVL_BEFORE);
		if (walker != NULL) {
			if (ISWITHIN(walker, start)) {
				/* We found start. */
				vmu_free_bound(tmp);
				*first = walker;
			}
		}
	}

	/*
	 * At this point, if *first is still NULL, then we
	 * didn't get a direct hit and start isn't covered
	 * by the previous node. We know that the next node
	 * must have a greater start value than we require
	 * because avl_find tells us where the AVL routines would
	 * insert our new node. We have some gap between the
	 * start we want and the next node.
	 */
	if (*first == NULL) {
		walker = avl_nearest(tree, where, AVL_AFTER);
		if (walker != NULL && walker->vmb_start <= end) {
			/* Fill the gap. */
			tmp->vmb_end = walker->vmb_start - 1;
			*first = tmp;
		} else {
			/* We have a gap over [start, end]. */
			tmp->vmb_end = end;
			*first = *last = tmp;
		}
		ret += tmp->vmb_end - tmp->vmb_start + 1;
		avl_insert(tree, tmp, where);
	}

	ASSERT(*first != NULL);

	if (*last != NULL) {
		/* We're done. */
		return (ret);
	}

	/*
	 * If we are here we still need to set *last and
	 * that may involve filling in some gaps.
	 */
	*last = *first;
	for (;;) {
		if (ISWITHIN(*last, end)) {
			/* We're done. */
			break;
		}
		walker = AVL_NEXT(tree, *last);
		if (walker == NULL || walker->vmb_start > end) {
			/* Bottom or mid tree with gap. */
			tmp = vmu_alloc_bound();
			tmp->vmb_start = (*last)->vmb_end + 1;
			tmp->vmb_end = end;
			tmp->vmb_type = type;
			ret += tmp->vmb_end - tmp->vmb_start + 1;
			avl_insert_here(tree, tmp, *last, AVL_AFTER);
			*last = tmp;
			break;
		} else {
			if ((*last)->vmb_end + 1 != walker->vmb_start) {
				/* Non-contiguous. */
				tmp = vmu_alloc_bound();
				tmp->vmb_start = (*last)->vmb_end + 1;
				tmp->vmb_end = walker->vmb_start - 1;
				tmp->vmb_type = type;
				ret += tmp->vmb_end - tmp->vmb_start + 1;
				avl_insert_here(tree, tmp, *last, AVL_AFTER);
				*last = tmp;
			} else {
				*last = walker;
			}
		}
	}

	return (ret);
}

/*
 * vmu_update_bounds()
 *
 * tree: avl_tree in which first and last hang.
 *
 * first, last:	list of continuous bounds, of which zero or more are of
 * 		type VMUSAGE_BOUND_UNKNOWN.
 *
 * new_tree: avl_tree in which new_first and new_last hang.
 *
 * new_first, new_last:	list of continuous bounds, of which none are of
 *			type VMUSAGE_BOUND_UNKNOWN.  These bounds are used to
 *			update the types of bounds in (first,last) with
 *			type VMUSAGE_BOUND_UNKNOWN.
 *
 * For the list of bounds (first,last), this function updates any bounds
 * with type VMUSAGE_BOUND_UNKNOWN using the type of the corresponding bound in
 * the list (new_first, new_last).
 *
 * If a bound of type VMUSAGE_BOUND_UNKNOWN spans multiple bounds in the list
 * (new_first, new_last), it will be split into multiple bounds.
 *
 * Return value:
 * 	The number of pages in the list of bounds (first,last) that were of
 *	type VMUSAGE_BOUND_UNKNOWN, which have been updated to be of type
 *	VMUSAGE_BOUND_INCORE.
 *
 */
static pgcnt_t
vmu_update_bounds(avl_tree_t *tree, vmu_bound_t **first, vmu_bound_t **last,
    avl_tree_t *new_tree, vmu_bound_t *new_first, vmu_bound_t *new_last)
{
	vmu_bound_t *next, *new_next, *tmp;
	pgcnt_t rss = 0;

	next = *first;
	new_next = new_first;

	/*
	 * Verify first and last bound are covered by new bounds if they
	 * have unknown type.
	 */
	ASSERT((*first)->vmb_type != VMUSAGE_BOUND_UNKNOWN ||
	    (*first)->vmb_start >= new_first->vmb_start);
	ASSERT((*last)->vmb_type != VMUSAGE_BOUND_UNKNOWN ||
	    (*last)->vmb_end <= new_last->vmb_end);
	for (;;) {
		/* If bound already has type, proceed to next bound. */
		if (next->vmb_type != VMUSAGE_BOUND_UNKNOWN) {
			if (next == *last)
				break;
			next = AVL_NEXT(tree, next);
			continue;
		}
		while (new_next->vmb_end < next->vmb_start)
			new_next = AVL_NEXT(new_tree, new_next);
		ASSERT(new_next->vmb_type != VMUSAGE_BOUND_UNKNOWN);
		next->vmb_type = new_next->vmb_type;
		if (new_next->vmb_end < next->vmb_end) {
			/* need to split bound */
			tmp = vmu_alloc_bound();
			tmp->vmb_type = VMUSAGE_BOUND_UNKNOWN;
			tmp->vmb_start = new_next->vmb_end + 1;
			tmp->vmb_end = next->vmb_end;
			avl_insert_here(tree, tmp, next, AVL_AFTER);
			next->vmb_end = new_next->vmb_end;
			if (*last == next)
				*last = tmp;
			if (next->vmb_type == VMUSAGE_BOUND_INCORE)
				rss += next->vmb_end - next->vmb_start + 1;
			next = tmp;
		} else {
			if (next->vmb_type == VMUSAGE_BOUND_INCORE)
				rss += next->vmb_end - next->vmb_start + 1;
			if (next == *last)
				break;
			next = AVL_NEXT(tree, next);
		}
	}
	return (rss);
}

/*
 * Merges adjacent bounds with same type between first and last bound.
 * After merge, last pointer may point to a different bound, as (incoming)
 * last bound may have been merged away.
 */
static void
vmu_merge_bounds(avl_tree_t *tree, vmu_bound_t **first, vmu_bound_t **last)
{
	vmu_bound_t *current;
	vmu_bound_t *next;

	ASSERT(tree != NULL);
	ASSERT(*first != NULL);
	ASSERT(*last != NULL);

	current = *first;
	while (current != *last) {
		next = AVL_NEXT(tree, current);
		if ((current->vmb_end + 1) == next->vmb_start &&
		    current->vmb_type == next->vmb_type) {
			current->vmb_end = next->vmb_end;
			avl_remove(tree, next);
			vmu_free_bound(next);
			if (next == *last) {
				*last = current;
			}
		} else {
			current = AVL_NEXT(tree, current);
		}
	}
}

/*
 * Given an amp and a list of bounds, updates each bound's type with
 * VMUSAGE_BOUND_INCORE or VMUSAGE_BOUND_NOT_INCORE.
 *
 * If a bound is partially incore, it will be split into two bounds.
 * first and last may be modified, as bounds may be split into multiple
 * bounds if they are partially incore/not-incore.
 *
 * Set incore to non-zero if bounds are already known to be incore.
 *
 */
static void
vmu_amp_update_incore_bounds(avl_tree_t *tree, struct anon_map *amp,
    vmu_bound_t **first, vmu_bound_t **last, boolean_t incore)
{
	vmu_bound_t *next;
	vmu_bound_t *tmp;
	pgcnt_t index;
	short bound_type;
	short page_type;
	vnode_t *vn;
	anoff_t off;
	struct anon *ap;

	next = *first;
	/* Shared anon slots don't change once set. */
	ANON_LOCK_ENTER(&amp->a_rwlock, RW_READER);
	for (;;) {
		if (incore == B_TRUE)
			next->vmb_type = VMUSAGE_BOUND_INCORE;

		if (next->vmb_type != VMUSAGE_BOUND_UNKNOWN) {
			if (next == *last)
				break;
			next = AVL_NEXT(tree, next);
			continue;
		}
		bound_type = next->vmb_type;
		index = next->vmb_start;
		while (index <= next->vmb_end) {

			/*
			 * These are used to determine how much to increment
			 * index when a large page is found.
			 */
			page_t *page;
			pgcnt_t pgcnt = 1;
			uint_t pgshft;
			pgcnt_t pgmsk;

			ap = anon_get_ptr(amp->ahp, index);
			if (ap != NULL)
				swap_xlate(ap, &vn, &off);

			if (ap != NULL && vn != NULL && vn->v_pages != NULL &&
			    (page = page_exists(vn, off)) != NULL) {
				page_type = VMUSAGE_BOUND_INCORE;
				if (page->p_szc > 0) {
					pgcnt = page_get_pagecnt(page->p_szc);
					pgshft = page_get_shift(page->p_szc);
					pgmsk = (0x1 << (pgshft - PAGESHIFT))
					    - 1;
				}
			} else {
				page_type = VMUSAGE_BOUND_NOT_INCORE;
			}
			if (bound_type == VMUSAGE_BOUND_UNKNOWN) {
				next->vmb_type = page_type;
			} else if (next->vmb_type != page_type) {
				/*
				 * If current bound type does not match page
				 * type, need to split off new bound.
				 */
				tmp = vmu_alloc_bound();
				tmp->vmb_type = page_type;
				tmp->vmb_start = index;
				tmp->vmb_end = next->vmb_end;
				avl_insert_here(tree, tmp, next, AVL_AFTER);
				next->vmb_end = index - 1;
				if (*last == next)
					*last = tmp;
				next = tmp;
			}
			if (pgcnt > 1) {
				/*
				 * If inside large page, jump to next large
				 * page
				 */
				index = (index & ~pgmsk) + pgcnt;
			} else {
				index++;
			}
		}
		if (next == *last) {
			ASSERT(next->vmb_type != VMUSAGE_BOUND_UNKNOWN);
			break;
		} else
			next = AVL_NEXT(tree, next);
	}
	ANON_LOCK_EXIT(&amp->a_rwlock);
}

/*
 * Same as vmu_amp_update_incore_bounds(), except for tracking
 * incore-/not-incore for vnodes.
 */
static void
vmu_vnode_update_incore_bounds(avl_tree_t *tree, vnode_t *vnode,
    vmu_bound_t **first, vmu_bound_t **last)
{
	vmu_bound_t *next;
	vmu_bound_t *tmp;
	pgcnt_t index;
	short bound_type;
	short page_type;

	next = *first;
	for (;;) {
		if (vnode->v_pages == NULL)
			next->vmb_type = VMUSAGE_BOUND_NOT_INCORE;

		if (next->vmb_type != VMUSAGE_BOUND_UNKNOWN) {
			if (next == *last)
				break;
			next = AVL_NEXT(tree, next);
			continue;
		}

		bound_type = next->vmb_type;
		index = next->vmb_start;
		while (index <= next->vmb_end) {

			/*
			 * These are used to determine how much to increment
			 * index when a large page is found.
			 */
			page_t *page;
			pgcnt_t pgcnt = 1;
			uint_t pgshft;
			pgcnt_t pgmsk;

			if (vnode->v_pages != NULL &&
			    (page = page_exists(vnode, ptob(index))) != NULL) {
				page_type = VMUSAGE_BOUND_INCORE;
				if (page->p_szc > 0) {
					pgcnt = page_get_pagecnt(page->p_szc);
					pgshft = page_get_shift(page->p_szc);
					pgmsk = (0x1 << (pgshft - PAGESHIFT))
					    - 1;
				}
			} else {
				page_type = VMUSAGE_BOUND_NOT_INCORE;
			}
			if (bound_type == VMUSAGE_BOUND_UNKNOWN) {
				next->vmb_type = page_type;
			} else if (next->vmb_type != page_type) {
				/*
				 * If current bound type does not match page
				 * type, need to split off new bound.
				 */
				tmp = vmu_alloc_bound();
				tmp->vmb_type = page_type;
				tmp->vmb_start = index;
				tmp->vmb_end = next->vmb_end;
				avl_insert_here(tree, tmp, next, AVL_AFTER);
				next->vmb_end = index - 1;
				if (*last == next)
					*last = tmp;
				next = tmp;
			}
			if (pgcnt > 1) {
				/*
				 * If inside large page, jump to next large
				 * page
				 */
				index = (index & ~pgmsk) + pgcnt;
			} else {
				index++;
			}
		}
		if (next == *last) {
			ASSERT(next->vmb_type != VMUSAGE_BOUND_UNKNOWN);
			break;
		} else
			next = AVL_NEXT(tree, next);
	}
}

/*
 * Calculate the rss and swap consumed by a segment.  vmu_entities is the
 * list of entities to visit.  For shared segments, the vnode or amp
 * is looked up in each entity to see if it has been already counted.  Private
 * anon pages are checked per entity to ensure that COW pages are not
 * double counted.
 *
 * For private mapped files, first the amp is checked for private pages.
 * Bounds not backed by the amp are looked up in the vnode for each entity
 * to avoid double counting of private COW vnode pages.
 */
static void
vmu_calculate_seg(vmu_entity_t *vmu_entities, struct seg *seg)
{
	struct segvn_data *svd;
	struct shm_data *shmd;
	struct spt_data *sptd;
	vmu_object_t *shared_object = NULL;
	vmu_object_t *entity_object = NULL;
	vmu_entity_t *entity;
	vmusage_t *result;
	vmu_bound_t *first = NULL;
	vmu_bound_t *last = NULL;
	vmu_bound_t *cur = NULL;
	vmu_bound_t *e_first = NULL;
	vmu_bound_t *e_last = NULL;
	vmu_bound_t *tmp;
	pgcnt_t p_index, s_index, p_start, p_end, s_start, s_end, rss, virt;
	struct anon_map *private_amp = NULL;
	boolean_t incore = B_FALSE;
	boolean_t shared = B_FALSE;
	int file = 0;
	pgcnt_t swresv = 0;
	pgcnt_t panon = 0;

	s_start = 0;
	p_end = 0;
	/* Can zero-length segments exist?  Not sure, so paranoia. */
	if (seg->s_size <= 0)
		return;

	/*
	 * Figure out if there is a shared object (such as a named vnode or
	 * a shared amp, then figure out if there is a private amp, which
	 * identifies private pages.
	 */
	if (seg->s_ops == &segvn_ops) {
		svd = (struct segvn_data *)seg->s_data;
		if (svd->type == MAP_SHARED) {
			shared = B_TRUE;
		} else {
			swresv = svd->swresv;

			if (SEGVN_LOCK_TRYENTER(seg->s_as, &svd->lock,
			    RW_READER) != 0) {
				/*
				 * Text replication anon maps can be shared
				 * across all zones. Space used for text
				 * replication is typically capped as a small %
				 * of memory.  To keep it simple for now we
				 * don't account for swap and memory space used
				 * for text replication.
				 */
				if (svd->tr_state == SEGVN_TR_OFF &&
				    svd->amp != NULL) {
					private_amp = svd->amp;
					p_start = svd->anon_index;
					p_end = svd->anon_index +
					    btop(seg->s_size) - 1;
				}
				SEGVN_LOCK_EXIT(seg->s_as, &svd->lock);
			}
		}
		if (svd->vp != NULL) {
			file = 1;
			shared_object = vmu_find_insert_object(
			    vmu_data.vmu_all_vnodes_hash, (caddr_t)svd->vp,
			    VMUSAGE_TYPE_VNODE);
			s_start = btop(svd->offset);
			s_end = btop(svd->offset + seg->s_size) - 1;
		}
		if (svd->amp != NULL && svd->type == MAP_SHARED) {
			ASSERT(shared_object == NULL);
			shared_object = vmu_find_insert_object(
			    vmu_data.vmu_all_amps_hash, (caddr_t)svd->amp,
			    VMUSAGE_TYPE_AMP);
			s_start = svd->anon_index;
			s_end = svd->anon_index + btop(seg->s_size) - 1;
			/* schedctl mappings are always in core */
			if (svd->amp->swresv == 0)
				incore = B_TRUE;
		}
	} else if (seg->s_ops == &segspt_shmops) {
		shared = B_TRUE;
		shmd = (struct shm_data *)seg->s_data;
		shared_object = vmu_find_insert_object(
		    vmu_data.vmu_all_amps_hash, (caddr_t)shmd->shm_amp,
		    VMUSAGE_TYPE_AMP);
		s_start = 0;
		s_end = btop(seg->s_size) - 1;
		sptd = shmd->shm_sptseg->s_data;

		/* ism segments are always incore and do not reserve swap */
		if (sptd->spt_flags & SHM_SHARE_MMU)
			incore = B_TRUE;

	} else {
		return;
	}

	/*
	 * If there is a private amp, count anon pages that exist.  If an
	 * anon has a refcnt > 1 (COW sharing), then save the anon in a
	 * hash so that it is not double counted.
	 *
	 * If there is also a shared object, then figure out the bounds
	 * which are not mapped by the private amp.
	 */
	if (private_amp != NULL) {

		/* Enter as writer to prevent COW anons from being freed */
		ANON_LOCK_ENTER(&private_amp->a_rwlock, RW_WRITER);

		p_index = p_start;
		s_index = s_start;

		while (p_index <= p_end) {

			pgcnt_t p_index_next;
			pgcnt_t p_bound_size;
			int cnt;
			anoff_t off;
			struct vnode *vn;
			struct anon *ap;
			page_t *page;		/* For handling of large */
			pgcnt_t pgcnt = 1;	/* pages */
			pgcnt_t pgstart;
			pgcnt_t pgend;
			uint_t pgshft;
			pgcnt_t pgmsk;

			p_index_next = p_index;
			ap = anon_get_next_ptr(private_amp->ahp,
			    &p_index_next);

			/*
			 * If next anon is past end of mapping, simulate
			 * end of anon so loop terminates.
			 */
			if (p_index_next > p_end) {
				p_index_next = p_end + 1;
				ap = NULL;
			}
			/*
			 * For COW segments, keep track of bounds not
			 * backed by private amp so they can be looked
			 * up in the backing vnode
			 */
			if (p_index_next != p_index) {

				/*
				 * Compute index difference between anon and
				 * previous anon.
				 */
				p_bound_size = p_index_next - p_index - 1;

				if (shared_object != NULL) {
					cur = vmu_alloc_bound();
					cur->vmb_start = s_index;
					cur->vmb_end = s_index + p_bound_size;
					cur->vmb_type = VMUSAGE_BOUND_UNKNOWN;
					if (first == NULL) {
						first = cur;
						last = cur;
					} else {
						last->vmb_next = cur;
						last = cur;
					}
				}
				p_index = p_index + p_bound_size + 1;
				s_index = s_index + p_bound_size + 1;
			}

			/* Detect end of anons in amp */
			if (ap == NULL)
				break;

			cnt = ap->an_refcnt;
			swap_xlate(ap, &vn, &off);

			if (vn == NULL || vn->v_pages == NULL ||
			    (page = page_exists(vn, off)) == NULL) {
				p_index++;
				s_index++;
				continue;
			}

			/*
			 * If large page is found, compute portion of large
			 * page in mapping, and increment indicies to the next
			 * large page.
			 */
			if (page->p_szc > 0) {

				pgcnt = page_get_pagecnt(page->p_szc);
				pgshft = page_get_shift(page->p_szc);
				pgmsk = (0x1 << (pgshft - PAGESHIFT)) - 1;

				/* First page in large page */
				pgstart = p_index & ~pgmsk;
				/* Last page in large page */
				pgend = pgstart + pgcnt - 1;
				/*
				 * Artifically end page if page extends past
				 * end of mapping.
				 */
				if (pgend > p_end)
					pgend = p_end;

				/*
				 * Compute number of pages from large page
				 * which are mapped.
				 */
				pgcnt = pgend - p_index + 1;

				/*
				 * Point indicies at page after large page,
				 * or at page after end of mapping.
				 */
				p_index += pgcnt;
				s_index += pgcnt;
			} else {
				p_index++;
				s_index++;
			}

			/*
			 * Assume anon structs with a refcnt
			 * of 1 are not COW shared, so there
			 * is no reason to track them per entity.
			 */
			if (cnt == 1) {
				panon += pgcnt;
				continue;
			}
			for (entity = vmu_entities; entity != NULL;
			    entity = entity->vme_next_calc) {

				result = &entity->vme_result;
				/*
				 * Track COW anons per entity so
				 * they are not double counted.
				 */
				if (vmu_find_insert_anon(entity->vme_anon_hash,
				    (caddr_t)ap) == 0)
					continue;

				result->vmu_rss_all += (pgcnt << PAGESHIFT);
				result->vmu_rss_private +=
				    (pgcnt << PAGESHIFT);
			}
		}
		ANON_LOCK_EXIT(&private_amp->a_rwlock);
	}

	/* Add up resident anon and swap reserved for private mappings */
	if (swresv > 0 || panon > 0) {
		for (entity = vmu_entities; entity != NULL;
		    entity = entity->vme_next_calc) {
			result = &entity->vme_result;
			result->vmu_swap_all += swresv;
			result->vmu_swap_private += swresv;
			result->vmu_rss_all += (panon << PAGESHIFT);
			result->vmu_rss_private += (panon << PAGESHIFT);
		}
	}

	/* Compute resident pages backing shared amp or named vnode */
	if (shared_object != NULL) {
		avl_tree_t *tree = &(shared_object->vmo_bounds);

		if (first == NULL) {
			/*
			 * No private amp, or private amp has no anon
			 * structs.  This means entire segment is backed by
			 * the shared object.
			 */
			first = vmu_alloc_bound();
			first->vmb_start = s_start;
			first->vmb_end = s_end;
			first->vmb_type = VMUSAGE_BOUND_UNKNOWN;
		}
		/*
		 * Iterate bounds not backed by private amp, and compute
		 * resident pages.
		 */
		cur = first;
		while (cur != NULL) {

			if (vmu_insert_lookup_object_bounds(shared_object,
			    cur->vmb_start, cur->vmb_end, VMUSAGE_BOUND_UNKNOWN,
			    &first, &last) > 0) {
				/* new bounds, find incore/not-incore */
				if (shared_object->vmo_type ==
				    VMUSAGE_TYPE_VNODE) {
					vmu_vnode_update_incore_bounds(
					    tree,
					    (vnode_t *)
					    shared_object->vmo_key, &first,
					    &last);
				} else {
					vmu_amp_update_incore_bounds(
					    tree,
					    (struct anon_map *)
					    shared_object->vmo_key, &first,
					    &last, incore);
				}
				vmu_merge_bounds(tree, &first, &last);
			}
			for (entity = vmu_entities; entity != NULL;
			    entity = entity->vme_next_calc) {
				avl_tree_t *e_tree;

				result = &entity->vme_result;

				entity_object = vmu_find_insert_object(
				    shared_object->vmo_type ==
				    VMUSAGE_TYPE_VNODE ? entity->vme_vnode_hash:
				    entity->vme_amp_hash,
				    shared_object->vmo_key,
				    shared_object->vmo_type);

				virt = vmu_insert_lookup_object_bounds(
				    entity_object, cur->vmb_start, cur->vmb_end,
				    VMUSAGE_BOUND_UNKNOWN, &e_first, &e_last);

				if (virt == 0)
					continue;
				/*
				 * Range visited for this entity
				 */
				e_tree = &(entity_object->vmo_bounds);
				rss = vmu_update_bounds(e_tree, &e_first,
				    &e_last, tree, first, last);
				result->vmu_rss_all += (rss << PAGESHIFT);
				if (shared == B_TRUE && file == B_FALSE) {
					/* shared anon mapping */
					result->vmu_swap_all +=
					    (virt << PAGESHIFT);
					result->vmu_swap_shared +=
					    (virt << PAGESHIFT);
					result->vmu_rss_shared +=
					    (rss << PAGESHIFT);
				} else if (shared == B_TRUE && file == B_TRUE) {
					/* shared file mapping */
					result->vmu_rss_shared +=
					    (rss << PAGESHIFT);
				} else if (shared == B_FALSE &&
				    file == B_TRUE) {
					/* private file mapping */
					result->vmu_rss_private +=
					    (rss << PAGESHIFT);
				}
				vmu_merge_bounds(e_tree, &e_first, &e_last);
			}
			tmp = cur;
			cur = cur->vmb_next;
			vmu_free_bound(tmp);
		}
	}
}

/*
 * Based on the current calculation flags, find the relevant entities
 * which are relative to the process.  Then calculate each segment
 * in the process'es address space for each relevant entity.
 */
static void
vmu_calculate_proc(proc_t *p)
{
	vmu_entity_t *entities = NULL;
	vmu_zone_t *zone;
	vmu_entity_t *tmp;
	struct as *as;
	struct seg *seg;
	int ret;

	/* Figure out which entities are being computed */
	if ((vmu_data.vmu_system) != NULL) {
		tmp = vmu_data.vmu_system;
		tmp->vme_next_calc = entities;
		entities = tmp;
	}
	if (vmu_data.vmu_calc_flags &
	    (VMUSAGE_ZONE | VMUSAGE_ALL_ZONES | VMUSAGE_PROJECTS |
	    VMUSAGE_ALL_PROJECTS | VMUSAGE_TASKS | VMUSAGE_ALL_TASKS |
	    VMUSAGE_RUSERS | VMUSAGE_ALL_RUSERS | VMUSAGE_EUSERS |
	    VMUSAGE_ALL_EUSERS)) {
		ret = i_mod_hash_find_nosync(vmu_data.vmu_zones_hash,
		    (mod_hash_key_t)(uintptr_t)p->p_zone->zone_id,
		    (mod_hash_val_t *)&zone);
		if (ret != 0) {
			zone = vmu_alloc_zone(p->p_zone->zone_id);
			ret = i_mod_hash_insert_nosync(vmu_data.vmu_zones_hash,
			    (mod_hash_key_t)(uintptr_t)p->p_zone->zone_id,
			    (mod_hash_val_t)zone, (mod_hash_hndl_t)0);
			ASSERT(ret == 0);
		}
		if (zone->vmz_zone != NULL) {
			tmp = zone->vmz_zone;
			tmp->vme_next_calc = entities;
			entities = tmp;
		}
		if (vmu_data.vmu_calc_flags &
		    (VMUSAGE_PROJECTS | VMUSAGE_ALL_PROJECTS)) {
			tmp = vmu_find_insert_entity(zone->vmz_projects_hash,
			    p->p_task->tk_proj->kpj_id, VMUSAGE_PROJECTS,
			    zone->vmz_id);
			tmp->vme_next_calc = entities;
			entities = tmp;
		}
		if (vmu_data.vmu_calc_flags &
		    (VMUSAGE_TASKS | VMUSAGE_ALL_TASKS)) {
			tmp = vmu_find_insert_entity(zone->vmz_tasks_hash,
			    p->p_task->tk_tkid, VMUSAGE_TASKS, zone->vmz_id);
			tmp->vme_next_calc = entities;
			entities = tmp;
		}
		if (vmu_data.vmu_calc_flags &
		    (VMUSAGE_RUSERS | VMUSAGE_ALL_RUSERS)) {
			tmp = vmu_find_insert_entity(zone->vmz_rusers_hash,
			    crgetruid(p->p_cred), VMUSAGE_RUSERS, zone->vmz_id);
			tmp->vme_next_calc = entities;
			entities = tmp;
		}
		if (vmu_data.vmu_calc_flags &
		    (VMUSAGE_EUSERS | VMUSAGE_ALL_EUSERS)) {
			tmp = vmu_find_insert_entity(zone->vmz_eusers_hash,
			    crgetuid(p->p_cred), VMUSAGE_EUSERS, zone->vmz_id);
			tmp->vme_next_calc = entities;
			entities = tmp;
		}
	}
	/* Entities which collapse projects and users for all zones */
	if (vmu_data.vmu_calc_flags & VMUSAGE_COL_PROJECTS) {
		tmp = vmu_find_insert_entity(vmu_data.vmu_projects_col_hash,
		    p->p_task->tk_proj->kpj_id, VMUSAGE_PROJECTS, ALL_ZONES);
		tmp->vme_next_calc = entities;
		entities = tmp;
	}
	if (vmu_data.vmu_calc_flags & VMUSAGE_COL_RUSERS) {
		tmp = vmu_find_insert_entity(vmu_data.vmu_rusers_col_hash,
		    crgetruid(p->p_cred), VMUSAGE_RUSERS, ALL_ZONES);
		tmp->vme_next_calc = entities;
		entities = tmp;
	}
	if (vmu_data.vmu_calc_flags & VMUSAGE_COL_EUSERS) {
		tmp = vmu_find_insert_entity(vmu_data.vmu_eusers_col_hash,
		    crgetuid(p->p_cred), VMUSAGE_EUSERS, ALL_ZONES);
		tmp->vme_next_calc = entities;
		entities = tmp;
	}

	ASSERT(entities != NULL);
	/* process all segs in process's address space */
	as = p->p_as;
	AS_LOCK_ENTER(as, RW_READER);
	for (seg = AS_SEGFIRST(as); seg != NULL;
	    seg = AS_SEGNEXT(as, seg)) {
		vmu_calculate_seg(entities, seg);
	}
	AS_LOCK_EXIT(as);
}

/*
 * Free data created by previous call to vmu_calculate().
 */
static void
vmu_clear_calc()
{
	if (vmu_data.vmu_system != NULL) {
		vmu_free_entity(vmu_data.vmu_system);
		vmu_data.vmu_system = NULL;
	}
	if (vmu_data.vmu_zones_hash != NULL)
		i_mod_hash_clear_nosync(vmu_data.vmu_zones_hash);
	if (vmu_data.vmu_projects_col_hash != NULL)
		i_mod_hash_clear_nosync(vmu_data.vmu_projects_col_hash);
	if (vmu_data.vmu_rusers_col_hash != NULL)
		i_mod_hash_clear_nosync(vmu_data.vmu_rusers_col_hash);
	if (vmu_data.vmu_eusers_col_hash != NULL)
		i_mod_hash_clear_nosync(vmu_data.vmu_eusers_col_hash);

	i_mod_hash_clear_nosync(vmu_data.vmu_all_vnodes_hash);
	i_mod_hash_clear_nosync(vmu_data.vmu_all_amps_hash);
}

/*
 * Free unused data structures.  These can result if the system workload
 * decreases between calculations.
 */
static void
vmu_free_extra()
{
	vmu_bound_t *tb;
	vmu_object_t *to;
	vmu_entity_t *te;
	vmu_zone_t *tz;

	while (vmu_data.vmu_free_bounds != NULL) {
		tb = vmu_data.vmu_free_bounds;
		vmu_data.vmu_free_bounds = vmu_data.vmu_free_bounds->vmb_next;
		kmem_cache_free(vmu_bound_cache, tb);
	}
	while (vmu_data.vmu_free_objects != NULL) {
		to = vmu_data.vmu_free_objects;
		vmu_data.vmu_free_objects =
		    vmu_data.vmu_free_objects->vmo_next;
		kmem_cache_free(vmu_object_cache, to);
	}
	while (vmu_data.vmu_free_entities != NULL) {
		te = vmu_data.vmu_free_entities;
		vmu_data.vmu_free_entities =
		    vmu_data.vmu_free_entities->vme_next;
		if (te->vme_vnode_hash != NULL)
			mod_hash_destroy_hash(te->vme_vnode_hash);
		if (te->vme_amp_hash != NULL)
			mod_hash_destroy_hash(te->vme_amp_hash);
		if (te->vme_anon_hash != NULL)
			mod_hash_destroy_hash(te->vme_anon_hash);
		kmem_free(te, sizeof (vmu_entity_t));
	}
	while (vmu_data.vmu_free_zones != NULL) {
		tz = vmu_data.vmu_free_zones;
		vmu_data.vmu_free_zones =
		    vmu_data.vmu_free_zones->vmz_next;
		if (tz->vmz_projects_hash != NULL)
			mod_hash_destroy_hash(tz->vmz_projects_hash);
		if (tz->vmz_tasks_hash != NULL)
			mod_hash_destroy_hash(tz->vmz_tasks_hash);
		if (tz->vmz_rusers_hash != NULL)
			mod_hash_destroy_hash(tz->vmz_rusers_hash);
		if (tz->vmz_eusers_hash != NULL)
			mod_hash_destroy_hash(tz->vmz_eusers_hash);
		kmem_free(tz, sizeof (vmu_zone_t));
	}
}

extern kcondvar_t *pr_pid_cv;

/*
 * Determine which entity types are relevant and allocate the hashes to
 * track them.  Then walk the process table and count rss and swap
 * for each process'es address space.  Address space object such as
 * vnodes, amps and anons are tracked per entity, so that they are
 * not double counted in the results.
 *
 */
static void
vmu_calculate()
{
	int i = 0;
	int ret;
	proc_t *p;

	vmu_clear_calc();

	if (vmu_data.vmu_calc_flags & VMUSAGE_SYSTEM)
		vmu_data.vmu_system = vmu_alloc_entity(0, VMUSAGE_SYSTEM,
		    ALL_ZONES);

	/*
	 * Walk process table and calculate rss of each proc.
	 *
	 * Pidlock and p_lock cannot be held while doing the rss calculation.
	 * This is because:
	 *	1.  The calculation allocates using KM_SLEEP.
	 *	2.  The calculation grabs a_lock, which cannot be grabbed
	 *	    after p_lock.
	 *
	 * Since pidlock must be dropped, we cannot simply just walk the
	 * practive list.  Instead, we walk the process table, and sprlock
	 * each process to ensure that it does not exit during the
	 * calculation.
	 */

	mutex_enter(&pidlock);
	for (i = 0; i < v.v_proc; i++) {
again:
		p = pid_entry(i);
		if (p == NULL)
			continue;

		mutex_enter(&p->p_lock);
		mutex_exit(&pidlock);

		if (panicstr) {
			mutex_exit(&p->p_lock);
			return;
		}

		/* Try to set P_PR_LOCK */
		ret = sprtrylock_proc(p);
		if (ret == -1) {
			/* Process in invalid state */
			mutex_exit(&p->p_lock);
			mutex_enter(&pidlock);
			continue;
		} else if (ret == 1) {
			/*
			 * P_PR_LOCK is already set.  Wait and try again.
			 * This also drops p_lock.
			 */
			sprwaitlock_proc(p);
			mutex_enter(&pidlock);
			goto again;
		}
		mutex_exit(&p->p_lock);

		vmu_calculate_proc(p);

		mutex_enter(&p->p_lock);
		sprunlock(p);
		mutex_enter(&pidlock);
	}
	mutex_exit(&pidlock);

	vmu_free_extra();
}

/*
 * allocate a new cache for N results satisfying flags
 */
vmu_cache_t *
vmu_cache_alloc(size_t nres, uint_t flags)
{
	vmu_cache_t *cache;

	cache = kmem_zalloc(sizeof (vmu_cache_t), KM_SLEEP);
	cache->vmc_results = kmem_zalloc(sizeof (vmusage_t) * nres, KM_SLEEP);
	cache->vmc_nresults = nres;
	cache->vmc_flags = flags;
	cache->vmc_refcnt = 1;
	return (cache);
}

/*
 * Make sure cached results are not freed
 */
static void
vmu_cache_hold(vmu_cache_t *cache)
{
	ASSERT(MUTEX_HELD(&vmu_data.vmu_lock));
	cache->vmc_refcnt++;
}

/*
 * free cache data
 */
static void
vmu_cache_rele(vmu_cache_t *cache)
{
	ASSERT(MUTEX_HELD(&vmu_data.vmu_lock));
	ASSERT(cache->vmc_refcnt > 0);
	cache->vmc_refcnt--;
	if (cache->vmc_refcnt == 0) {
		kmem_free(cache->vmc_results, sizeof (vmusage_t) *
		    cache->vmc_nresults);
		kmem_free(cache, sizeof (vmu_cache_t));
	}
}

/*
 * Copy out the cached results to a caller.  Inspect the callers flags
 * and zone to determine which cached results should be copied.
 */
static int
vmu_copyout_results(vmu_cache_t *cache, vmusage_t *buf, size_t *nres,
    uint_t flags, int cpflg)
{
	vmusage_t *result, *out_result;
	vmusage_t dummy;
	size_t i, count = 0;
	size_t bufsize;
	int ret = 0;
	uint_t types = 0;

	if (nres != NULL) {
		if (ddi_copyin((caddr_t)nres, &bufsize, sizeof (size_t), cpflg))
			return (set_errno(EFAULT));
	} else {
		bufsize = 0;
	}

	/* figure out what results the caller is interested in. */
	if ((flags & VMUSAGE_SYSTEM) && curproc->p_zone == global_zone)
		types |= VMUSAGE_SYSTEM;
	if (flags & (VMUSAGE_ZONE | VMUSAGE_ALL_ZONES))
		types |= VMUSAGE_ZONE;
	if (flags & (VMUSAGE_PROJECTS | VMUSAGE_ALL_PROJECTS |
	    VMUSAGE_COL_PROJECTS))
		types |= VMUSAGE_PROJECTS;
	if (flags & (VMUSAGE_TASKS | VMUSAGE_ALL_TASKS))
		types |= VMUSAGE_TASKS;
	if (flags & (VMUSAGE_RUSERS | VMUSAGE_ALL_RUSERS | VMUSAGE_COL_RUSERS))
		types |= VMUSAGE_RUSERS;
	if (flags & (VMUSAGE_EUSERS | VMUSAGE_ALL_EUSERS | VMUSAGE_COL_EUSERS))
		types |= VMUSAGE_EUSERS;

	/* count results for current zone */
	out_result = buf;
	for (result = cache->vmc_results, i = 0;
	    i < cache->vmc_nresults; result++, i++) {

		/* Do not return "other-zone" results to non-global zones */
		if (curproc->p_zone != global_zone &&
		    curproc->p_zone->zone_id != result->vmu_zoneid)
			continue;

		/*
		 * If non-global zone requests VMUSAGE_SYSTEM, fake
		 * up VMUSAGE_ZONE result as VMUSAGE_SYSTEM result.
		 */
		if (curproc->p_zone != global_zone &&
		    (flags & VMUSAGE_SYSTEM) != 0 &&
		    result->vmu_type == VMUSAGE_ZONE) {
			count++;
			if (out_result != NULL) {
				if (bufsize < count) {
					ret = set_errno(EOVERFLOW);
				} else {
					dummy = *result;
					dummy.vmu_zoneid = ALL_ZONES;
					dummy.vmu_id = 0;
					dummy.vmu_type = VMUSAGE_SYSTEM;
					if (ddi_copyout(&dummy, out_result,
					    sizeof (vmusage_t), cpflg))
						return (set_errno(EFAULT));
					out_result++;
				}
			}
		}

		/* Skip results that do not match requested type */
		if ((result->vmu_type & types) == 0)
			continue;

		/* Skip collated results if not requested */
		if (result->vmu_zoneid == ALL_ZONES) {
			if (result->vmu_type == VMUSAGE_PROJECTS &&
			    (flags & VMUSAGE_COL_PROJECTS) == 0)
				continue;
			if (result->vmu_type == VMUSAGE_EUSERS &&
			    (flags & VMUSAGE_COL_EUSERS) == 0)
				continue;
			if (result->vmu_type == VMUSAGE_RUSERS &&
			    (flags & VMUSAGE_COL_RUSERS) == 0)
				continue;
		}

		/* Skip "other zone" results if not requested */
		if (result->vmu_zoneid != curproc->p_zone->zone_id) {
			if (result->vmu_type == VMUSAGE_ZONE &&
			    (flags & VMUSAGE_ALL_ZONES) == 0)
				continue;
			if (result->vmu_type == VMUSAGE_PROJECTS &&
			    (flags & (VMUSAGE_ALL_PROJECTS |
			    VMUSAGE_COL_PROJECTS)) == 0)
				continue;
			if (result->vmu_type == VMUSAGE_TASKS &&
			    (flags & VMUSAGE_ALL_TASKS) == 0)
				continue;
			if (result->vmu_type == VMUSAGE_RUSERS &&
			    (flags & (VMUSAGE_ALL_RUSERS |
			    VMUSAGE_COL_RUSERS)) == 0)
				continue;
			if (result->vmu_type == VMUSAGE_EUSERS &&
			    (flags & (VMUSAGE_ALL_EUSERS |
			    VMUSAGE_COL_EUSERS)) == 0)
				continue;
		}
		count++;
		if (out_result != NULL) {
			if (bufsize < count) {
				ret = set_errno(EOVERFLOW);
			} else {
				if (ddi_copyout(result, out_result,
				    sizeof (vmusage_t), cpflg))
					return (set_errno(EFAULT));
				out_result++;
			}
		}
	}
	if (nres != NULL)
		if (ddi_copyout(&count, (void *)nres, sizeof (size_t), cpflg))
			return (set_errno(EFAULT));

	return (ret);
}

/*
 * vm_getusage()
 *
 * Counts rss and swap by zone, project, task, and/or user.  The flags argument
 * determines the type of results structures returned.  Flags requesting
 * results from more than one zone are "flattened" to the local zone if the
 * caller is not the global zone.
 *
 * args:
 *	flags:	bitmap consisting of one or more of VMUSAGE_*.
 *	age:	maximum allowable age (time since counting was done) in
 *		seconds of the results.  Results from previous callers are
 *		cached in kernel.
 *	buf:	pointer to buffer array of vmusage_t.  If NULL, then only nres
 *		set on success.
 *	nres:	Set to number of vmusage_t structures pointed to by buf
 *		before calling vm_getusage().
 *		On return 0 (success) or ENOSPC, is set to the number of result
 *		structures returned or attempted to return.
 *
 * returns 0 on success, -1 on failure:
 *	EINTR (interrupted)
 *	ENOSPC (nres to small for results, nres set to needed value for success)
 *	EINVAL (flags invalid)
 *	EFAULT (bad address for buf or nres)
 */
int
vm_getusage(uint_t flags, time_t age, vmusage_t *buf, size_t *nres, int cpflg)
{
	vmu_entity_t *entity;
	vmusage_t *result;
	int ret = 0;
	int cacherecent = 0;
	hrtime_t now;
	uint_t flags_orig;

	/*
	 * Non-global zones cannot request system wide and/or collated
	 * results, or the system result, so munge the flags accordingly.
	 */
	flags_orig = flags;
	if (curproc->p_zone != global_zone) {
		if (flags & (VMUSAGE_ALL_PROJECTS | VMUSAGE_COL_PROJECTS)) {
			flags &= ~(VMUSAGE_ALL_PROJECTS | VMUSAGE_COL_PROJECTS);
			flags |= VMUSAGE_PROJECTS;
		}
		if (flags & (VMUSAGE_ALL_RUSERS | VMUSAGE_COL_RUSERS)) {
			flags &= ~(VMUSAGE_ALL_RUSERS | VMUSAGE_COL_RUSERS);
			flags |= VMUSAGE_RUSERS;
		}
		if (flags & (VMUSAGE_ALL_EUSERS | VMUSAGE_COL_EUSERS)) {
			flags &= ~(VMUSAGE_ALL_EUSERS | VMUSAGE_COL_EUSERS);
			flags |= VMUSAGE_EUSERS;
		}
		if (flags & VMUSAGE_SYSTEM) {
			flags &= ~VMUSAGE_SYSTEM;
			flags |= VMUSAGE_ZONE;
		}
	}

	/* Check for unknown flags */
	if ((flags & (~VMUSAGE_MASK)) != 0)
		return (set_errno(EINVAL));

	/* Check for no flags */
	if ((flags & VMUSAGE_MASK) == 0)
		return (set_errno(EINVAL));

	mutex_enter(&vmu_data.vmu_lock);
	now = gethrtime();

start:
	if (vmu_data.vmu_cache != NULL) {

		vmu_cache_t *cache;

		if ((vmu_data.vmu_cache->vmc_timestamp +
		    ((hrtime_t)age * NANOSEC)) > now)
			cacherecent = 1;

		if ((vmu_data.vmu_cache->vmc_flags & flags) == flags &&
		    cacherecent == 1) {
			cache = vmu_data.vmu_cache;
			vmu_cache_hold(cache);
			mutex_exit(&vmu_data.vmu_lock);

			ret = vmu_copyout_results(cache, buf, nres, flags_orig,
			    cpflg);
			mutex_enter(&vmu_data.vmu_lock);
			vmu_cache_rele(cache);
			if (vmu_data.vmu_pending_waiters > 0)
				cv_broadcast(&vmu_data.vmu_cv);
			mutex_exit(&vmu_data.vmu_lock);
			return (ret);
		}
		/*
		 * If the cache is recent, it is likely that there are other
		 * consumers of vm_getusage running, so add their flags to the
		 * desired flags for the calculation.
		 */
		if (cacherecent == 1)
			flags = vmu_data.vmu_cache->vmc_flags | flags;
	}
	if (vmu_data.vmu_calc_thread == NULL) {

		vmu_cache_t *cache;

		vmu_data.vmu_calc_thread = curthread;
		vmu_data.vmu_calc_flags = flags;
		vmu_data.vmu_entities = NULL;
		vmu_data.vmu_nentities = 0;
		if (vmu_data.vmu_pending_waiters > 0)
			vmu_data.vmu_calc_flags |=
			    vmu_data.vmu_pending_flags;

		vmu_data.vmu_pending_flags = 0;
		mutex_exit(&vmu_data.vmu_lock);
		vmu_calculate();
		mutex_enter(&vmu_data.vmu_lock);
		/* copy results to cache */
		if (vmu_data.vmu_cache != NULL)
			vmu_cache_rele(vmu_data.vmu_cache);
		cache = vmu_data.vmu_cache =
		    vmu_cache_alloc(vmu_data.vmu_nentities,
		    vmu_data.vmu_calc_flags);

		result = cache->vmc_results;
		for (entity = vmu_data.vmu_entities; entity != NULL;
		    entity = entity->vme_next) {
			*result = entity->vme_result;
			result++;
		}
		cache->vmc_timestamp = gethrtime();
		vmu_cache_hold(cache);

		vmu_data.vmu_calc_flags = 0;
		vmu_data.vmu_calc_thread = NULL;

		if (vmu_data.vmu_pending_waiters > 0)
			cv_broadcast(&vmu_data.vmu_cv);

		mutex_exit(&vmu_data.vmu_lock);

		/* copy cache */
		ret = vmu_copyout_results(cache, buf, nres, flags_orig, cpflg);
		mutex_enter(&vmu_data.vmu_lock);
		vmu_cache_rele(cache);
		mutex_exit(&vmu_data.vmu_lock);

		return (ret);
	}
	vmu_data.vmu_pending_flags |= flags;
	vmu_data.vmu_pending_waiters++;
	while (vmu_data.vmu_calc_thread != NULL) {
		if (cv_wait_sig(&vmu_data.vmu_cv,
		    &vmu_data.vmu_lock) == 0) {
			vmu_data.vmu_pending_waiters--;
			mutex_exit(&vmu_data.vmu_lock);
			return (set_errno(EINTR));
		}
	}
	vmu_data.vmu_pending_waiters--;
	goto start;
}