[apple/xnu.git] / osfmk / vm / task_working_set.h

/*
 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * Copyright (c) 1999-2003 Apple Computer, Inc.  All Rights Reserved.
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */
/*
 */

/*
 *	File:	vm/task_working_set.h
 *	Author:	Chris Youngworth
 *	Date:	2001
 *
 *	Working set detection and maintainence module
 *
 */

#ifndef	_VM_TASK_WORKING_SET_H_
#define _VM_TASK_WORKING_SET_H_

#include <kern/queue.h>
#include <vm/vm_object.h>

/* task working set */

#define tws_lock(tws)		mutex_lock(&(tws)->lock)
#define tws_lock_try(tws)	mutex_try(&(tws)->lock)
#define tws_unlock(tws)		mutex_unlock(&(tws)->lock)


#define	TWS_ARRAY_SIZE	8
#define TWS_HASH_LINE_COUNT 32
/* start out size to allow monitoring of working set without excessive use */
/* of wired memory resource. */
#define TWS_SMALL_HASH_LINE_COUNT 4 

/*
 * do not think of changing this hash unless you understand the implications
 * for the hash element page_cache field 
 */
#define do_tws_hash(object,offset, rows, lines) \
		((((((natural_t)(object)) +  \
			(((natural_t)(object)) >> 6) +  \
			(((natural_t)(object)) >> 12) +  \
			(((natural_t)(object)) >> 18) +  \
			(((natural_t)(object)) >> 24)) << 5) +  \
			((natural_t)(((vm_object_offset_t)(offset)) >> 17))) & \
			((rows * lines) -1))


#define alt_tws_hash(addr, rows, lines) \
		((((natural_t)(addr)) >> 17) & \
		((rows * lines) -1))


/* Long term startup data structures for initial cache filling */

#define	TWS_STARTUP_MAX_HASH_RETRY	3

/* 87 is the wrap skew, its based on  RETRY times the RETRY offset of 29 */
/*
#define do_startup_hash(addr, hash_size) \
		((((((natural_t)(addr)) >> 17) & \
		((2 * (hash_size)) -1)) + \
		(87 * (((addr) & TWS_ADDR_OFF_MASK)/(2 * (hash_size))))) & \
		((2 * (hash_size)) -1))
*/
#define do_startup_hash(addr, hash_size) \
		(((((natural_t)(addr)) >> 17) * 3) & \
		(hash_size -1))


struct tws_startup_ele {
	unsigned int		page_cache;
	vm_offset_t		page_addr;
};

typedef struct tws_startup_ele *tws_startup_ele_t;


struct tws_startup_ptr {
	tws_startup_ele_t	element;
	struct tws_startup_ptr	*next;
};

typedef struct tws_startup_ptr	*tws_startup_ptr_t;

struct tws_startup {
	unsigned int	tws_hash_size;	/* total size of struct in bytes */
	unsigned int	ele_count;
	unsigned int	array_size;	/* lines * rows * expansion_count */
	unsigned int	hash_count;
	
	tws_startup_ptr_t	*table; /* hash table */
	struct tws_startup_ptr	*ele;   /* hash elements */
	struct	tws_startup_ele	*array;
};

typedef struct tws_startup	*tws_startup_t;


/* Dynamic cache data structures for working set */

struct tws_hash_ele {
	vm_object_t		object;
	vm_object_offset_t	offset;
	unsigned int		page_cache;
	vm_offset_t		page_addr;
	int			line;
	vm_map_t		map;
};
typedef struct tws_hash_ele *tws_hash_ele_t;

#define TWS_HASH_OFF_MASK ((vm_object_offset_t)0xFFFFFFFFFFFE0000)
#define TWS_ADDR_OFF_MASK ((vm_offset_t)0xFFFE0000)
#define TWS_INDEX_MASK ((vm_object_offset_t)0x000000000001F000)

struct tws_hash_ptr {
	tws_hash_ele_t		element;
	struct tws_hash_ptr	*next;
};
typedef struct tws_hash_ptr *tws_hash_ptr_t;

struct tws_hash_line {
	int		ele_count;
	struct tws_hash_ele	list[TWS_ARRAY_SIZE];
};
typedef struct tws_hash_line *tws_hash_line_t;

#define TWS_HASH_STYLE_DEFAULT	0x0
#define TWS_HASH_STYLE_BASIC	0x1
#define TWS_HASH_STYLE_SIGNAL	0x2


#define TWS_ADDR_HASH 1
#define TWS_HASH_EXPANSION_MAX	5
#define TWS_MAX_REHASH 3


struct tws_hash {
	decl_mutex_data(,lock)          /* tws_hash's lock */
	int		style;

	int		current_line;
	unsigned int	pageout_count;
	int		line_count;

	int		number_of_lines;
	int		number_of_elements;
	int		expansion_count;
	unsigned int	time_of_creation;

	int		lookup_count;
	int		insert_count;

	tws_startup_t	startup_cache;
	char		*startup_name;
	int		startup_name_length;
	unsigned int	uid;
	int		mod;
	int		fid;

	unsigned int    obj_free_count[TWS_HASH_EXPANSION_MAX];
	unsigned int    addr_free_count[TWS_HASH_EXPANSION_MAX];
	tws_hash_ptr_t	free_hash_ele[TWS_HASH_EXPANSION_MAX];
	tws_hash_ptr_t	*table[TWS_HASH_EXPANSION_MAX];
	tws_hash_ptr_t	table_ele[TWS_HASH_EXPANSION_MAX];
	tws_hash_ptr_t	alt_ele[TWS_HASH_EXPANSION_MAX];
	struct tws_hash_line	*cache[TWS_HASH_EXPANSION_MAX];
}; 

typedef struct tws_hash *tws_hash_t;


extern tws_hash_t tws_hash_create();

extern void tws_hash_line_clear(
			tws_hash_t	tws,
			tws_hash_line_t hash_line, 
			boolean_t live);

extern kern_return_t tws_lookup(
			tws_hash_t		tws,	
			vm_object_offset_t	offset, 
			vm_object_t		object,
			tws_hash_line_t		 *line);

extern kern_return_t tws_insert(
			tws_hash_t		tws, 
			vm_object_offset_t	offset,
			vm_object_t		object,
			vm_offset_t		page_addr,
			vm_map_t		map);

extern void tws_build_cluster(
			tws_hash_t		tws,
			vm_object_t		object,
			vm_object_offset_t	*start,
			vm_object_offset_t	*end,
			vm_size_t		max_length);

extern tws_line_signal(
		tws_hash_t	tws,
		vm_map_t	map,
		tws_hash_line_t hash_line,
		vm_offset_t	target_page);

extern void tws_hash_destroy(
		tws_hash_t	tws);

extern void tws_hash_clear(
		tws_hash_t	tws);

kern_return_t	task_working_set_create(                
		task_t  task,
		unsigned int lines,
		unsigned int rows,
		unsigned int style);

kern_return_t	tws_expand_working_set(
		vm_offset_t	old_tws,
		int		line_count,
		boolean_t	dump_data);

kern_return_t	tws_handle_startup_file(
		task_t		task,
		unsigned int	uid,
		char		*app_name,
		vm_offset_t	app_vp,
		boolean_t	*new_info);

kern_return_t	tws_write_startup_file(
		task_t		task,
		int		fid,
		int		mod,
		char		*name,
		unsigned int	string_length);

kern_return_t	tws_read_startup_file(
		task_t			task,
		tws_startup_t		startup,
		vm_offset_t		cache_size);

void
tws_hash_ws_flush(
	tws_hash_t	tws);


#endif  /* _VM_TASK_WORKING_SET_H_ */
Commit	Line	Data
0b4e3aa0 A	1	/*
	2	* Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
	3	*
	4	* @APPLE_LICENSE_HEADER_START@
	5	*
43866e37	6	* Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
0b4e3aa0	7	*
43866e37 A	8	* This file contains Original Code and/or Modifications of Original Code
	9	* as defined in and that are subject to the Apple Public Source License
	10	* Version 2.0 (the 'License'). You may not use this file except in
	11	* compliance with the License. Please obtain a copy of the License at
	12	* http://www.opensource.apple.com/apsl/ and read it before using this
	13	* file.
	14	*
	15	* The Original Code and all software distributed under the License are
	16	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
0b4e3aa0 A	17	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
0b4e3aa0 A	18	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
43866e37 A	19	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	20	* Please see the License for the specific language governing rights and
	21	* limitations under the License.
0b4e3aa0 A	22	*
	23	* @APPLE_LICENSE_HEADER_END@
	24	*/
	25	/*
	26	*/
	27
	28	/*
	29	* File: vm/task_working_set.h
	30	* Author: Chris Youngworth
	31	* Date: 2001
	32	*
	33	* Working set detection and maintainence module
	34	*
	35	*/
	36
	37	#ifndef _VM_TASK_WORKING_SET_H_
	38	#define _VM_TASK_WORKING_SET_H_
	39
	40	#include <kern/queue.h>
	41	#include <vm/vm_object.h>
	42
	43	/* task working set */
	44
	45	#define tws_lock(tws) mutex_lock(&(tws)->lock)
	46	#define tws_lock_try(tws) mutex_try(&(tws)->lock)
	47	#define tws_unlock(tws) mutex_unlock(&(tws)->lock)
	48
	49
	50	#define TWS_ARRAY_SIZE 8
	51	#define TWS_HASH_LINE_COUNT 32
	52	/* start out size to allow monitoring of working set without excessive use */
	53	/* of wired memory resource. */
	54	#define TWS_SMALL_HASH_LINE_COUNT 4
	55
0b4e3aa0 A	56	/*
	57	* do not think of changing this hash unless you understand the implications
	58	* for the hash element page_cache field
	59	*/
	60	#define do_tws_hash(object,offset, rows, lines) \
9bccf70c A	61	((((((natural_t)(object)) + \
	62	(((natural_t)(object)) >> 6) + \
	63	(((natural_t)(object)) >> 12) + \
	64	(((natural_t)(object)) >> 18) + \
	65	(((natural_t)(object)) >> 24)) << 5) + \
0b4e3aa0	66	((natural_t)(((vm_object_offset_t)(offset)) >> 17))) & \
9bccf70c	67	((rows * lines) -1))
0b4e3aa0 A	68
	69
	70	#define alt_tws_hash(addr, rows, lines) \
9bccf70c A	71	((((natural_t)(addr)) >> 17) & \
	72	((rows * lines) -1))
	73
	74
	75	/* Long term startup data structures for initial cache filling */
	76
	77	#define TWS_STARTUP_MAX_HASH_RETRY 3
	78
	79	/* 87 is the wrap skew, its based on RETRY times the RETRY offset of 29 */
	80	/*
	81	#define do_startup_hash(addr, hash_size) \
	82	((((((natural_t)(addr)) >> 17) & \
	83	((2 * (hash_size)) -1)) + \
	84	(87 * (((addr) & TWS_ADDR_OFF_MASK)/(2 * (hash_size))))) & \
	85	((2 * (hash_size)) -1))
	86	*/
	87	#define do_startup_hash(addr, hash_size) \
	88	(((((natural_t)(addr)) >> 17) * 3) & \
	89	(hash_size -1))
	90
	91
	92
	93	struct tws_startup_ele {
	94	unsigned int page_cache;
	95	vm_offset_t page_addr;
	96	};
	97
	98	typedef struct tws_startup_ele *tws_startup_ele_t;
	99
	100
	101	struct tws_startup_ptr {
	102	tws_startup_ele_t element;
	103	struct tws_startup_ptr *next;
	104	};
	105
	106	typedef struct tws_startup_ptr *tws_startup_ptr_t;
	107
	108	struct tws_startup {
	109	unsigned int tws_hash_size; /* total size of struct in bytes */
	110	unsigned int ele_count;
	111	unsigned int array_size; /* lines * rows * expansion_count */
	112	unsigned int hash_count;
	113
	114	tws_startup_ptr_t table; / hash table */
	115	struct tws_startup_ptr ele; / hash elements */
	116	struct tws_startup_ele *array;
	117	};
	118
	119	typedef struct tws_startup *tws_startup_t;
	120
	121
	122	/* Dynamic cache data structures for working set */
0b4e3aa0 A	123
	124	struct tws_hash_ele {
	125	vm_object_t object;
	126	vm_object_offset_t offset;
	127	unsigned int page_cache;
	128	vm_offset_t page_addr;
	129	int line;
	130	vm_map_t map;
	131	};
	132	typedef struct tws_hash_ele *tws_hash_ele_t;
	133
	134	#define TWS_HASH_OFF_MASK ((vm_object_offset_t)0xFFFFFFFFFFFE0000)
9bccf70c	135	#define TWS_ADDR_OFF_MASK ((vm_offset_t)0xFFFE0000)
0b4e3aa0 A	136	#define TWS_INDEX_MASK ((vm_object_offset_t)0x000000000001F000)
0b4e3aa0 A	137
9bccf70c A	138	struct tws_hash_ptr {
	139	tws_hash_ele_t element;
	140	struct tws_hash_ptr *next;
	141	};
	142	typedef struct tws_hash_ptr *tws_hash_ptr_t;
	143
0b4e3aa0 A	144	struct tws_hash_line {
	145	int ele_count;
	146	struct tws_hash_ele list[TWS_ARRAY_SIZE];
	147	};
	148	typedef struct tws_hash_line *tws_hash_line_t;
	149
	150	#define TWS_HASH_STYLE_DEFAULT 0x0
	151	#define TWS_HASH_STYLE_BASIC 0x1
	152	#define TWS_HASH_STYLE_SIGNAL 0x2
	153
	154
9bccf70c	155	#define TWS_ADDR_HASH 1
0b4e3aa0	156	#define TWS_HASH_EXPANSION_MAX 5
9bccf70c	157	#define TWS_MAX_REHASH 3
0b4e3aa0 A	158
	159
	160	struct tws_hash {
	161	decl_mutex_data(,lock) /* tws_hash's lock */
	162	int style;
	163
	164	int current_line;
	165	unsigned int pageout_count;
	166	int line_count;
	167
	168	int number_of_lines;
	169	int number_of_elements;
	170	int expansion_count;
	171	unsigned int time_of_creation;
	172
	173	int lookup_count;
	174	int insert_count;
	175
9bccf70c A	176	tws_startup_t startup_cache;
	177	char *startup_name;
	178	int startup_name_length;
	179	unsigned int uid;
	180	int mod;
	181	int fid;
	182
	183	unsigned int obj_free_count[TWS_HASH_EXPANSION_MAX];
	184	unsigned int addr_free_count[TWS_HASH_EXPANSION_MAX];
	185	tws_hash_ptr_t free_hash_ele[TWS_HASH_EXPANSION_MAX];
	186	tws_hash_ptr_t *table[TWS_HASH_EXPANSION_MAX];
	187	tws_hash_ptr_t table_ele[TWS_HASH_EXPANSION_MAX];
	188	tws_hash_ptr_t alt_ele[TWS_HASH_EXPANSION_MAX];
0b4e3aa0 A	189	struct tws_hash_line *cache[TWS_HASH_EXPANSION_MAX];
	190	};
	191
	192	typedef struct tws_hash *tws_hash_t;
	193
	194
	195	extern tws_hash_t tws_hash_create();
	196
	197	extern void tws_hash_line_clear(
	198	tws_hash_t tws,
	199	tws_hash_line_t hash_line,
	200	boolean_t live);
	201
	202	extern kern_return_t tws_lookup(
	203	tws_hash_t tws,
	204	vm_object_offset_t offset,
	205	vm_object_t object,
	206	tws_hash_line_t *line);
	207
	208	extern kern_return_t tws_insert(
	209	tws_hash_t tws,
	210	vm_object_offset_t offset,
	211	vm_object_t object,
	212	vm_offset_t page_addr,
	213	vm_map_t map);
	214
	215	extern void tws_build_cluster(
	216	tws_hash_t tws,
	217	vm_object_t object,
	218	vm_object_offset_t *start,
	219	vm_object_offset_t *end,
	220	vm_size_t max_length);
	221
	222	extern tws_line_signal(
	223	tws_hash_t tws,
	224	vm_map_t map,
	225	tws_hash_line_t hash_line,
	226	vm_offset_t target_page);
	227
	228	extern void tws_hash_destroy(
	229	tws_hash_t tws);
	230
	231	extern void tws_hash_clear(
	232	tws_hash_t tws);
	233
	234	kern_return_t task_working_set_create(
	235	task_t task,
	236	unsigned int lines,
	237	unsigned int rows,
	238	unsigned int style);
	239
	240	kern_return_t tws_expand_working_set(
	241	vm_offset_t old_tws,
9bccf70c A	242	int line_count,
	243	boolean_t dump_data);
	244
	245	kern_return_t tws_handle_startup_file(
	246	task_t task,
	247	unsigned int uid,
	248	char *app_name,
	249	vm_offset_t app_vp,
	250	boolean_t *new_info);
	251
	252	kern_return_t tws_write_startup_file(
	253	task_t task,
	254	int fid,
	255	int mod,
	256	char *name,
	257	unsigned int string_length);
	258
	259	kern_return_t tws_read_startup_file(
	260	task_t task,
	261	tws_startup_t startup,
	262	vm_offset_t cache_size);
	263
90556fb8 A	264	void
90556fb8 A	265	tws_hash_ws_flush(
55e303ae	266	tws_hash_t tws);
90556fb8	267
0b4e3aa0 A	268
	269
	270	#endif /* _VM_TASK_WORKING_SET_H_ */