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

/*
 * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 * 
 * This 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 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.c
 *	Author:	Chris Youngworth
 *	Date:	2001
 *
 *	Working set detection and maintainence module
 */


#include <mach/mach_types.h>
#include <mach/memory_object.h>
#include <mach/shared_memory_server.h>
#include <vm/task_working_set.h>
#include <vm/vm_kern.h>
#include <vm/vm_map.h>
#include <vm/vm_page.h>
#include <vm/vm_pageout.h>
#include <kern/sched.h>
#include <kern/kalloc.h>

#include <vm/vm_protos.h>

/*
 * LP64todo - Task Working Set Support is for 32-bit only
 */
extern zone_t lsf_zone;

/* declarations for internal use only routines */
int	startup_miss = 0;

tws_hash_t
tws_hash_create(
	unsigned int lines,
	unsigned int rows,
	unsigned int style);

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);

tws_startup_t
tws_create_startup_list(
	tws_hash_t	tws);

unsigned int
tws_startup_list_lookup(
        tws_startup_t   startup,
        vm_offset_t     addr);

kern_return_t
tws_internal_startup_send(
	tws_hash_t	tws);

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

void
tws_hash_clear(
	tws_hash_t	tws);

void
tws_traverse_address_hash_list (
	tws_hash_t 		tws, 
	unsigned int		index,
	vm_offset_t		page_addr,
	vm_object_t		object,
	vm_object_offset_t	offset,
	vm_map_t		map,
	tws_hash_ptr_t		*target_ele,
	tws_hash_ptr_t		**previous_ptr,
	tws_hash_ptr_t		**free_list,
	unsigned int		exclusive_addr);

void
tws_traverse_object_hash_list (
	tws_hash_t 		tws, 
	unsigned int		index,
	vm_object_t		object,
	vm_object_offset_t	offset,
	unsigned int		pagemask,
	tws_hash_ptr_t		*target_ele,
	tws_hash_ptr_t		**previous_ptr,
	tws_hash_ptr_t		**free_list);

tws_hash_ptr_t
new_addr_hash(
	tws_hash_t tws, 
	unsigned int set, 
	unsigned int index);

tws_hash_ptr_t
new_obj_hash(
	tws_hash_t tws, 
	unsigned int set, 
	unsigned int index);

int tws_test_for_community(
		tws_hash_t		tws, 
		vm_object_t		object, 
		vm_object_offset_t	offset, 
		unsigned int		threshold, 
		unsigned int		*pagemask);

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

/* Note:  all of the routines below depend on the associated map lock for */
/* synchronization, the map lock will be on when the routines are called  */
/* and on when they return */

tws_hash_t
tws_hash_create(
	unsigned int lines, 
	unsigned int rows,
	unsigned int style)
{
	tws_hash_t	tws;
	
	if ((style != TWS_HASH_STYLE_BASIC) &&
			(style != TWS_HASH_STYLE_BASIC)) {
		return((tws_hash_t)NULL);
	}

	
	tws = (tws_hash_t)(kalloc(sizeof(struct tws_hash)));
	if(tws == (tws_hash_t)NULL)
		return tws;

	if((tws->table[0] = (tws_hash_ptr_t *)
			kalloc(sizeof(tws_hash_ptr_t) * lines * rows)) 
								== NULL) {
		kfree(tws, sizeof(struct tws_hash));
		return (tws_hash_t)NULL;
	}
	if((tws->table_ele[0] = (tws_hash_ptr_t)
			kalloc(sizeof(struct tws_hash_ptr) * lines * rows)) 
								== NULL) {
		kfree(tws->table[0], sizeof(tws_hash_ptr_t) * lines * rows);
		kfree(tws, sizeof(struct tws_hash));
		return (tws_hash_t)NULL;
	}
	if((tws->alt_ele[0] = (tws_hash_ptr_t)
			kalloc(sizeof(struct tws_hash_ptr) * lines * rows))
								== NULL) {
		kfree(tws->table[0], sizeof(tws_hash_ptr_t) * lines * rows);
		kfree(tws->table_ele[0],
		      sizeof(struct tws_hash_ptr) * lines * rows);
		kfree(tws, sizeof(struct tws_hash));
		return (tws_hash_t)NULL;
	}
	if((tws->cache[0] = (struct tws_hash_line *)
			kalloc(sizeof(struct tws_hash_line) * lines))
								== NULL) {
		kfree(tws->table[0], sizeof(tws_hash_ptr_t) * lines * rows);
		kfree(tws->table_ele[0],
		      sizeof(struct tws_hash_ptr) * lines * rows);
		kfree(tws->alt_ele[0],
		      sizeof(struct tws_hash_ptr) * lines * rows);
		kfree(tws, sizeof(struct tws_hash));
		return (tws_hash_t)NULL;
	}
	tws->free_hash_ele[0] = (tws_hash_ptr_t)0;
	tws->obj_free_count[0] = 0;
	tws->addr_free_count[0] = 0;

	/* most defaults are such that a bzero will initialize */
	bzero((char *)tws->table[0],sizeof(tws_hash_ptr_t)
                                	* lines * rows);
	bzero((char *)tws->table_ele[0],sizeof(struct tws_hash_ptr)
                                	* lines * rows);
	bzero((char *)tws->alt_ele[0],sizeof(struct tws_hash_ptr)
                                	* lines * rows);
	bzero((char *)tws->cache[0], sizeof(struct tws_hash_line) 
					* lines);

	mutex_init(&tws->lock, 0);
	tws->style = style;
	tws->current_line = 0;
	tws->pageout_count = 0;
	tws->line_count = 0;
	tws->startup_cache = NULL;
	tws->startup_name = NULL;
	tws->number_of_lines = lines;
	tws->number_of_elements = rows;
	tws->expansion_count = 1;
	tws->lookup_count = 0;
	tws->insert_count = 0;
	tws->time_of_creation = sched_tick;

	return tws;
}


extern vm_page_t
vm_page_lookup_nohint(vm_object_t object, vm_object_offset_t offset);


void
tws_hash_line_clear(
	tws_hash_t	tws,
	tws_hash_line_t hash_line,
	__unused vm_object_t	object,
	boolean_t live)
{
	struct tws_hash_ele	*hash_ele;
	struct tws_hash_ptr	**trailer;
	struct tws_hash_ptr	**free_list;
	tws_hash_ele_t		addr_ele;
	int			index;
	unsigned int		i, j;
	int			dump_pmap;
	int			hash_loop;


	if(tws->line_count < tws->number_of_lines) {
		tws->line_count++;
		dump_pmap = 1;
	} else {
		if(tws->pageout_count != vm_pageout_scan_event_counter) {
			tws->pageout_count = 
				vm_pageout_scan_event_counter;
			tws->line_count = 0;
			dump_pmap = 1;
		} else {
			dump_pmap = 0;
		}
	}
	hash_line->ele_count = 0;

	for (i=0; i<tws->number_of_elements; i++) {
		hash_loop = 0;
		hash_ele = &(hash_line->list[i]);
		if(hash_ele->object != 0) {
	
			vm_object_offset_t local_off = 0;
			tws_hash_ptr_t	cache_ele;
	
			index = alt_tws_hash(
				hash_ele->page_addr & TWS_ADDR_OFF_MASK,
				tws->number_of_elements, 
				tws->number_of_lines);
	
			tws_traverse_address_hash_list(tws, index, 
				hash_ele->page_addr, hash_ele->object,
				hash_ele->offset, hash_ele->map,
				&cache_ele, &trailer, &free_list, 0);
			if(cache_ele != NULL) {
				addr_ele = (tws_hash_ele_t)((unsigned int)
				   (cache_ele->element) & ~TWS_ADDR_HASH);
				if(addr_ele != hash_ele)
					panic("tws_hash_line_clear:"
						" out of sync\n");
				cache_ele->element = 0;
				*trailer = cache_ele->next;
				cache_ele->next = *free_list;
				*free_list = cache_ele;
			}
	
			index = alt_tws_hash(
				(hash_ele->page_addr - 0x1f000) 
						& TWS_ADDR_OFF_MASK,
				tws->number_of_elements, 
				tws->number_of_lines);

			tws_traverse_address_hash_list(tws, index, 
				hash_ele->page_addr, hash_ele->object, 
				hash_ele->offset, hash_ele->map,
				&cache_ele, &trailer, &free_list, 0);

			if(cache_ele != NULL) {
				addr_ele = (tws_hash_ele_t)((unsigned int)
				   (cache_ele->element) & ~TWS_ADDR_HASH);
				if(addr_ele != hash_ele)
					panic("tws_hash_line_clear: "
						"out of sync\n");
				cache_ele->element = 0;
				*trailer = cache_ele->next;
				cache_ele->next = *free_list;
				*free_list = cache_ele;
			}
	
	
			if((hash_ele->map != NULL) && (live)) {
				vm_page_t	p;
				
#if 0
				if (object != hash_ele->object) {
				    if (object)
				        vm_object_unlock(object);
				    vm_object_lock(hash_ele->object);
				}
#endif
				if (dump_pmap == 1) {
				    for (j = 0x1; j != 0; j = j<<1) {
				        if(j & hash_ele->page_cache) {
					    p = vm_page_lookup_nohint(hash_ele->object, 
								      hash_ele->offset + local_off);
					    if((p != NULL) && (p->wire_count == 0)) {
					        pmap_remove_some_phys((pmap_t)vm_map_pmap(current_map()),
								      p->phys_page);
					    }
					}
					local_off += PAGE_SIZE_64;
				    }
				}
#if 0
				if (object != hash_ele->object) {
				    vm_object_unlock(hash_ele->object);
				    if (object)
				        vm_object_lock(object);
				}
#endif
			}
	
			if(tws->style == TWS_HASH_STYLE_SIGNAL) {
				vm_object_deallocate(hash_ele->object);
				vm_map_deallocate(hash_ele->map);
			}

			index = do_tws_hash(hash_ele->object, hash_ele->offset,
					tws->number_of_elements, 
					tws->number_of_lines);

			tws_traverse_object_hash_list(tws,
				index, hash_ele->object, hash_ele->offset,
				0xFFFFFFFF, &cache_ele, &trailer, &free_list);
			if((cache_ele != NULL) && (cache_ele->element == hash_ele)) {
				cache_ele->element = 0;
				*trailer = cache_ele->next;
				cache_ele->next = *free_list;
				*free_list = cache_ele;
			}
			hash_ele->object = 0;
		}
	}
}

kern_return_t
tws_internal_lookup(
	tws_hash_t		tws,	
	vm_object_offset_t	offset, 
	vm_object_t		object,
	tws_hash_line_t		 *line) 
{
	int			index;
	int			loop;
	int		  	set; 
	int			ele_line;
	vm_offset_t		pagenum;
	tws_hash_ptr_t		cache_ele;
	tws_hash_ptr_t		*trailer;
	tws_hash_ptr_t		*free_list;

	/* don't cache private objects */
	if(object->private)
		return KERN_SUCCESS;

	index = do_tws_hash(object, offset, 
			tws->number_of_elements, tws->number_of_lines);
	loop = 0;

	tws->lookup_count++; 
	if(tws->lookup_count == 0)
		tws->insert_count = 0;
	if(tws->startup_name != NULL) {
		int age_of_cache;
		age_of_cache = ((sched_tick 
			- tws->time_of_creation) >> SCHED_TICK_SHIFT);
       		if (age_of_cache > 45) {
			return KERN_OPERATION_TIMED_OUT;
		}
	}

	if(tws->lookup_count > (4 * tws->expansion_count 
			* tws->number_of_elements * tws->number_of_lines) &&
			(tws->lookup_count > (2 * tws->insert_count))) {
		if(tws->startup_cache) {
			int age_of_cache;
			age_of_cache = ((sched_tick 
				- tws->time_of_creation) >> SCHED_TICK_SHIFT);
	        	if (age_of_cache > 45) {
				return KERN_OPERATION_TIMED_OUT;
			}
      		}
	}

	pagenum = (vm_offset_t)(offset & TWS_INDEX_MASK);
	pagenum = pagenum >> 12;
	pagenum = 1 << pagenum;  /* get the appropriate page in 32 page block */
	tws_traverse_object_hash_list(tws, index, object, offset, pagenum,
		&cache_ele, &trailer, &free_list);
	if(cache_ele != NULL) {
		set = cache_ele->element->line/tws->number_of_lines;
		ele_line = cache_ele->element->line - set;
		*line = &tws->cache[set][ele_line];
		return KERN_SUCCESS;
	}

	return KERN_FAILURE;


}

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

	if(!tws_lock_try(tws)) {
		return KERN_FAILURE;
	}
	kr = tws_internal_lookup(tws,
		offset, object, line);
	tws_unlock(tws);
	return kr;
}

kern_return_t
tws_expand_working_set(
	tws_hash_t	old_tws, 
	unsigned int	line_count,
	boolean_t	dump_data)
{
	tws_hash_t		new_tws;
	unsigned int		i,j,k;
	struct	tws_hash	temp;

	/* Note we do an elaborate dance to preserve the header that */
	/* task is pointing to.  In this way we can avoid taking a task */
	/* lock every time we want to access the tws */

	if (old_tws->number_of_lines >= line_count) {
		return KERN_FAILURE;
	}
	if((new_tws = tws_hash_create(line_count, 
			old_tws->number_of_elements, old_tws->style)) == 0) {
		return(KERN_NO_SPACE);
	}
	tws_lock(old_tws);
	
	if(!dump_data) {
	   for(i = 0; i<old_tws->number_of_lines; i++) {
	      for(j = 0; j<old_tws->number_of_elements; j++) {
	         for(k = 0; k<old_tws->expansion_count; k++) {
		    tws_hash_ele_t		entry;
		    vm_object_offset_t	paddr;
		    unsigned int		page_index;
		    entry = &old_tws->cache[k][i].list[j];
		    if(entry->object != 0) {
			paddr = 0;
			for(page_index = 1; page_index != 0; 
					page_index = page_index << 1) {
				if (entry->page_cache & page_index) {
					tws_insert(new_tws, 
						entry->offset+paddr,
						entry->object, 
						entry->page_addr+paddr, 
						entry->map);
				}
				paddr+=PAGE_SIZE;
			}
		
		    }
	        }
	      }
	   }
	}

	temp.style = new_tws->style;
	temp.current_line = new_tws->current_line;
	temp.pageout_count = new_tws->pageout_count;
	temp.line_count = new_tws->line_count;
	temp.number_of_lines = new_tws->number_of_lines;
	temp.number_of_elements = new_tws->number_of_elements;
	temp.expansion_count = new_tws->expansion_count;
	temp.lookup_count = new_tws->lookup_count;
	temp.insert_count = new_tws->insert_count;
	for(i = 0; i<new_tws->expansion_count; i++) {
		temp.obj_free_count[i] = new_tws->obj_free_count[i];
		temp.addr_free_count[i] = new_tws->addr_free_count[i];
		temp.free_hash_ele[i] = new_tws->free_hash_ele[i];
		temp.table[i] = new_tws->table[i];
		temp.table_ele[i] = new_tws->table_ele[i];
		temp.alt_ele[i] = new_tws->alt_ele[i];
		temp.cache[i] = new_tws->cache[i];
	}

	new_tws->style = old_tws->style;
	new_tws->current_line = old_tws->current_line;
	new_tws->pageout_count = old_tws->pageout_count;
	new_tws->line_count = old_tws->line_count;
	new_tws->number_of_lines = old_tws->number_of_lines;
	new_tws->number_of_elements = old_tws->number_of_elements;
	new_tws->expansion_count = old_tws->expansion_count;
	new_tws->lookup_count = old_tws->lookup_count;
	new_tws->insert_count = old_tws->insert_count;
	for(i = 0; i<old_tws->expansion_count; i++) {
		new_tws->obj_free_count[i] = old_tws->obj_free_count[i];
		new_tws->addr_free_count[i] = old_tws->addr_free_count[i];
		new_tws->free_hash_ele[i] = old_tws->free_hash_ele[i];
		new_tws->table[i] = old_tws->table[i];
		new_tws->table_ele[i] = old_tws->table_ele[i];
		new_tws->alt_ele[i] = old_tws->alt_ele[i];
		new_tws->cache[i] = old_tws->cache[i];
	}
	
	old_tws->style = temp.style;
	old_tws->current_line = temp.current_line;
	old_tws->pageout_count = temp.pageout_count;
	old_tws->line_count = temp.line_count;
	old_tws->number_of_lines = temp.number_of_lines;
	old_tws->number_of_elements = temp.number_of_elements;
	old_tws->expansion_count = temp.expansion_count;
	old_tws->lookup_count = temp.lookup_count;
	old_tws->insert_count = temp.insert_count;
	for(i = 0; i<temp.expansion_count; i++) {
		old_tws->obj_free_count[i] = temp.obj_free_count[i];;
		old_tws->addr_free_count[i] = temp.addr_free_count[i];;
		old_tws->free_hash_ele[i] = NULL;
		old_tws->table[i] = temp.table[i];
		old_tws->table_ele[i] = temp.table_ele[i];
		old_tws->alt_ele[i] = temp.alt_ele[i];
		old_tws->cache[i] = temp.cache[i];
	}

	tws_hash_destroy(new_tws);
	tws_unlock(old_tws);
	return	KERN_SUCCESS;
}

tws_hash_t	test_tws = 0;

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)
{
	unsigned int		index;
	unsigned int		alt_index;
	unsigned int		index_enum[2];
	unsigned int		ele_index;
	tws_hash_ptr_t		cache_ele;
	tws_hash_ptr_t		obj_ele = NULL;
	tws_hash_ptr_t		addr_ele = NULL;
	tws_hash_ptr_t		*trailer;
	tws_hash_ptr_t		*free_list;
	tws_hash_ele_t		target_element = NULL;
	unsigned int		i;
	unsigned int		current_line;
	unsigned int		set;
	int			ctr;
	unsigned int		startup_cache_line;
        int			age_of_cache = 0;

	if(!tws_lock_try(tws)) {
		return KERN_FAILURE;
	}
	tws->insert_count++;
	current_line = 0xFFFFFFFF;
	set = 0;

	startup_cache_line = 0;

	if (tws->startup_cache) {
	        vm_offset_t	startup_page_addr;

	        startup_page_addr = page_addr - (offset - (offset & TWS_HASH_OFF_MASK));

		age_of_cache = ((sched_tick - tws->time_of_creation) >> SCHED_TICK_SHIFT);

		startup_cache_line = tws_startup_list_lookup(tws->startup_cache, startup_page_addr);
	}
	/* This next bit of code, the and alternate hash */
	/* are all made necessary because of IPC COW     */

	/* Note: the use of page_addr modified by delta from offset */
	/* frame base means we may miss some previous entries.  However */
	/* we will not miss the present entry.  This is most important */
	/* in avoiding duplication of entries against long lived non-cow */
	/* objects */
	index_enum[0] = alt_tws_hash(
			page_addr & TWS_ADDR_OFF_MASK,
			tws->number_of_elements, tws->number_of_lines);

	index_enum[1] = alt_tws_hash(
			(page_addr - 0x1f000) & TWS_ADDR_OFF_MASK,
			tws->number_of_elements, tws->number_of_lines);

	for(ctr = 0; ctr < 2;) {
		tws_hash_ele_t	resident;
		tws_traverse_address_hash_list(tws, 
				index_enum[ctr], page_addr, NULL,
				0, NULL,
				&cache_ele, &trailer, &free_list, 1);
		if(cache_ele != NULL) {
			/* found one */
			resident = (tws_hash_ele_t)((unsigned int)
					cache_ele->element & ~TWS_ADDR_HASH);
	   		if((object == resident->object) &&
				resident->offset == 
					(offset & TWS_HASH_OFF_MASK)) {
				/* This is our object/offset */
				resident->page_cache 
						|= startup_cache_line;
	      			resident->page_cache |= 
				   (1<<(((vm_offset_t)
				   (offset & TWS_INDEX_MASK))>>12));
				tws_unlock(tws);
				if (age_of_cache > 45)
					return KERN_OPERATION_TIMED_OUT;
				return KERN_SUCCESS;
			}
	   		if((object->shadow ==
				resident->object) && 
				((resident->offset 
				+ object->shadow_offset) 
				== (offset & TWS_HASH_OFF_MASK))) {
				/* if we just shadowed, inherit */
				/* access pattern from  parent */
				startup_cache_line |= 
				   resident->page_cache;
				/* thow out old entry */
				resident->page_cache = 0;
				break;
			} else {
	      			resident->page_cache &= 
				   ~(1<<(((vm_offset_t)(page_addr 
					- resident->page_addr))
				   	>>12));
			}
			/* Throw out old entry if there are no */
			/* more pages in cache */
			if(resident->page_cache == 0) {
				/* delete addr hash entry */
				cache_ele->element = 0;
				*trailer = cache_ele->next;
				cache_ele->next = *free_list;
				*free_list = cache_ele;
				/* go after object hash */
				index = do_tws_hash(
					resident->object, 
					resident->offset,
					tws->number_of_elements, 
					tws->number_of_lines);
				tws_traverse_object_hash_list(tws,
					index, resident->object, 
					resident->offset,
					0xFFFFFFFF, &cache_ele,
					&trailer, &free_list);
				if(cache_ele != NULL) {
					if(tws->style == 
					   TWS_HASH_STYLE_SIGNAL) {
						vm_object_deallocate(
						   cache_ele->element->object);
						vm_map_deallocate(
						   cache_ele->element->map);
					}
					current_line = 
					   cache_ele->element->line;
					set = current_line
						/tws->number_of_lines;
					current_line -= set *
						tws->number_of_lines;
					if(cache_ele->element->object != 0) {
						cache_ele->element->object = 0;
						tws->cache[set]
							[current_line].ele_count--;
					}
					cache_ele->element = 0;
					*trailer = cache_ele->next;
					cache_ele->next = *free_list;
					*free_list = cache_ele;
				}
			}
			continue;
		}
		ctr+=1;
	}

	/* 
	 * We may or may not have a current line setting coming out of
	 * the code above.  If we have a current line it means we can
	 * choose to back-fill the spot vacated by a previous entry.
	 * We have yet to do a definitive check using the original obj/off
	 * We will do that now and override the current line if we
	 * find an element
	 */

	index = do_tws_hash(object, offset, 
			tws->number_of_elements, tws->number_of_lines);

	alt_index = index_enum[0];

	tws_traverse_object_hash_list(tws, index, object, offset,
			0xFFFFFFFF, &cache_ele, &trailer, &free_list);
	if(cache_ele != NULL) {
		obj_ele = cache_ele;
		current_line = cache_ele->element->line;
		set = current_line/tws->number_of_lines;
		current_line -= set * tws->number_of_lines;
		target_element = cache_ele->element;

		/* Now check to see if we have a hash addr for it */
		tws_traverse_address_hash_list(tws, 
				alt_index, obj_ele->element->page_addr,
				obj_ele->element->object,
				obj_ele->element->offset,
				obj_ele->element->map,
				&cache_ele, &trailer, &free_list, 0);
		if(cache_ele != NULL) {
			addr_ele = cache_ele;
		} else  {
			addr_ele = new_addr_hash(tws, set, alt_index);
			/* if cannot allocate just do without */
			/* we'll get it next time around */
		}
	}


	if(tws->style == TWS_HASH_STYLE_SIGNAL) {
		vm_object_reference(object);
		vm_map_reference(map);
	}

	if(current_line == 0xFFFFFFFF) {
		current_line = tws->current_line;
		set = current_line/tws->number_of_lines;
		current_line = current_line - (set * tws->number_of_lines);

#ifdef notdef
		if(cache_full) {
			tws->current_line = tws->number_of_lines - 1;
		}
#endif
		if(tws->cache[set][current_line].ele_count 
				>= tws->number_of_elements) {
			current_line++;
			tws->current_line++;
			if(current_line == tws->number_of_lines) {
				set++;
				current_line = 0;
				if (set == tws->expansion_count) {
				   if((tws->lookup_count <
				      (2 * tws->insert_count)) &&
				      (set<TWS_HASH_EXPANSION_MAX)) {
				      tws->lookup_count = 0;
				      tws->insert_count = 0;
				      if(tws->number_of_lines 
						< TWS_HASH_LINE_COUNT) {
					tws->current_line--;
					tws_unlock(tws);
					return KERN_NO_SPACE;
				      }
				      /* object persistence is guaranteed by */
				      /* an elevated paging or object        */
				      /* reference count in the caller. */
				      vm_object_unlock(object);
				      if((tws->table[set] = (tws_hash_ptr_t *)
				         kalloc(sizeof(tws_hash_ptr_t) 
						* tws->number_of_lines 
						* tws->number_of_elements)) 
								== NULL) {
				         set = 0;
				      } else if((tws->table_ele[set] = 
					(tws_hash_ptr_t)
				         kalloc(sizeof(struct tws_hash_ptr) 
						* tws->number_of_lines 
						* tws->number_of_elements)) 
								== NULL) {
				         kfree(tws->table[set], 
					       sizeof(tws_hash_ptr_t) 
					       * tws->number_of_lines 
					       * tws->number_of_elements);
				         set = 0;
				      } else if((tws->alt_ele[set] = 
						(tws_hash_ptr_t)
			 		 kalloc(sizeof(struct tws_hash_ptr)
						* tws->number_of_lines 
						* tws->number_of_elements)) 
								== NULL) {
				         kfree(tws->table_ele[set], 
					       sizeof(struct tws_hash_ptr) 
					       * tws->number_of_lines 
					       * tws->number_of_elements);
				         kfree(tws->table[set], 
					       sizeof(tws_hash_ptr_t) 
				       		* tws->number_of_lines 
						* tws->number_of_elements);
				         tws->table[set] = NULL;
				         set = 0;

				      } else if((tws->cache[set] = 
						(struct tws_hash_line *)
						kalloc(sizeof
						(struct tws_hash_line) 
						* tws->number_of_lines)) 
								== NULL) {
				         kfree(tws->alt_ele[set], 
					       sizeof(struct tws_hash_ptr) 
					       * tws->number_of_lines 
					       * tws->number_of_elements);
					 kfree(tws->table_ele[set], 
					       sizeof(struct tws_hash_ptr) 
					       * tws->number_of_lines 
					       * tws->number_of_elements);
				         kfree(tws->table[set], 
					       sizeof(tws_hash_ptr_t) 
					       * tws->number_of_lines 
					       * tws->number_of_elements);
				         tws->table[set] = NULL;
				         set = 0;
							
				      } else {
					 tws->free_hash_ele[set] = 
							(tws_hash_ptr_t)0;
					 tws->obj_free_count[set] = 0;
					 tws->addr_free_count[set] = 0;
				         bzero((char *)tws->table[set], 
						sizeof(tws_hash_ptr_t) 
						* tws->number_of_lines 
						* tws->number_of_elements);
				         bzero((char *)tws->table_ele[set], 
						sizeof(struct tws_hash_ptr) 
						* tws->number_of_lines 
						* tws->number_of_elements);
				         bzero((char *)tws->alt_ele[set], 
						sizeof(struct tws_hash_ptr) 
						* tws->number_of_lines 
						* tws->number_of_elements);
				         bzero((char *)tws->cache[set], 
						sizeof(struct tws_hash_line) 
						* tws->number_of_lines);
				      }
				      vm_object_lock(object);
				   } else {
				      if (tws->startup_name != NULL) {
						tws->current_line--;

						age_of_cache = ((sched_tick - tws->time_of_creation) >> SCHED_TICK_SHIFT);

						tws_unlock(tws);

						if (age_of_cache > 45)
						        return KERN_OPERATION_TIMED_OUT;

						return KERN_FAILURE;
				      }
				      tws->lookup_count = 0;
				      tws->insert_count = 0;
				      set = 0;
				   }
				}
				tws->current_line = set * tws->number_of_lines;
			}
			if(set < tws->expansion_count) {
			   tws_hash_line_clear(tws, 
				&(tws->cache[set][current_line]), object, TRUE);
			   if(tws->cache[set][current_line].ele_count 
						>= tws->number_of_elements) {
				if(tws->style == TWS_HASH_STYLE_SIGNAL) {
					vm_object_deallocate(object);
					vm_map_deallocate(map);
				}
				tws_unlock(tws);
				return KERN_FAILURE;
			   }
			} else {
				tws->expansion_count++;
			}
		}
	}


	/* set object hash element */
	if(obj_ele == NULL) {
		obj_ele = new_obj_hash(tws, set, index);
		if(obj_ele == NULL) {
			tws->cache[set][current_line].ele_count 
				= tws->number_of_elements;
			tws_unlock(tws);
			return KERN_FAILURE;
		}
	}

	/* set address hash element */
	if(addr_ele == NULL) {
		addr_ele = new_addr_hash(tws, set, alt_index);
	}

	if(target_element == NULL) {
		ele_index = 0;
		for(i = 0; i<tws->number_of_elements; i++) {
			if(tws->cache[set][current_line].
				list[ele_index].object == 0) {
				break;
			}
			ele_index++;
			if(ele_index >= tws->number_of_elements)
				ele_index = 0;
		
		}

		if(i == tws->number_of_elements) 
			panic("tws_insert: no free elements");

		target_element = 
			&(tws->cache[set][current_line].list[ele_index]);

		tws->cache[set][current_line].ele_count++;
	}

	obj_ele->element = target_element;
	if(addr_ele) {
		addr_ele->element = (tws_hash_ele_t)
			(((unsigned int)target_element) | TWS_ADDR_HASH);
	}
	target_element->object = object;
	target_element->offset = offset & TWS_HASH_OFF_MASK;
	target_element->page_addr = 
			page_addr - (offset - (offset & TWS_HASH_OFF_MASK));
	target_element->map = map;
	target_element->line = 
			current_line + (set * tws->number_of_lines);

	target_element->page_cache |= startup_cache_line;
	target_element->page_cache |= 1<<(((vm_offset_t)(offset & TWS_INDEX_MASK))>>12);

	tws_unlock(tws);

	if (age_of_cache > 45)
		return KERN_OPERATION_TIMED_OUT;

	return KERN_SUCCESS;
}

/* 
 * tws_build_cluster
 * lengthen the cluster of pages by the number of pages encountered in the 
 * working set up to the limit requested by the caller.  The object needs
 * to be locked on entry.  The map does not because the tws_lookup function
 * is used only to find if their is an entry in the cache.  No transient
 * data from the cache is de-referenced.
 *
 */
#if	MACH_PAGEMAP
/*
 * MACH page map - an optional optimization where a bit map is maintained
 * by the VM subsystem for internal objects to indicate which pages of
 * the object currently reside on backing store.  This existence map
 * duplicates information maintained by the vnode pager.  It is 
 * created at the time of the first pageout against the object, i.e. 
 * at the same time pager for the object is created.  The optimization
 * is designed to eliminate pager interaction overhead, if it is 
 * 'known' that the page does not exist on backing store.
 *
 * LOOK_FOR() evaluates to TRUE if the page specified by object/offset is 
 * either marked as paged out in the existence map for the object or no 
 * existence map exists for the object.  LOOK_FOR() is one of the
 * criteria in the decision to invoke the pager.   It is also used as one
 * of the criteria to terminate the scan for adjacent pages in a clustered
 * pagein operation.  Note that LOOK_FOR() always evaluates to TRUE for
 * permanent objects.  Note also that if the pager for an internal object 
 * has not been created, the pager is not invoked regardless of the value 
 * of LOOK_FOR() and that clustered pagein scans are only done on an object
 * for which a pager has been created.
 *
 * PAGED_OUT() evaluates to TRUE if the page specified by the object/offset
 * is marked as paged out in the existence map for the object.  PAGED_OUT()
 * PAGED_OUT() is used to determine if a page has already been pushed
 * into a copy object in order to avoid a redundant page out operation.
 */
#define LOOK_FOR(o, f) (vm_external_state_get((o)->existence_map, (f)) \
			!= VM_EXTERNAL_STATE_ABSENT)
#define PAGED_OUT(o, f) (vm_external_state_get((o)->existence_map, (f)) \
			== VM_EXTERNAL_STATE_EXISTS)
#else /* MACH_PAGEMAP */
/*
 * If the MACH page map optimization is not enabled,
 * LOOK_FOR() always evaluates to TRUE.  The pager will always be 
 * invoked to resolve missing pages in an object, assuming the pager 
 * has been created for the object.  In a clustered page operation, the 
 * absence of a page on backing backing store cannot be used to terminate 
 * a scan for adjacent pages since that information is available only in 
 * the pager.  Hence pages that may not be paged out are potentially 
 * included in a clustered request.  The vnode pager is coded to deal 
 * with any combination of absent/present pages in a clustered 
 * pagein request.  PAGED_OUT() always evaluates to FALSE, i.e. the pager
 * will always be invoked to push a dirty page into a copy object assuming
 * a pager has been created.  If the page has already been pushed, the
 * pager will ingore the new request.
 */
#define LOOK_FOR(o, f) TRUE
#define PAGED_OUT(o, f) FALSE
#endif /* MACH_PAGEMAP */


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)
{
	tws_hash_line_t		line;
	vm_object_offset_t	before = *start;
	vm_object_offset_t	after =  *end;
	vm_object_offset_t	original_start = *start;
	vm_object_offset_t	original_end = *end;
	vm_size_t		length =  (vm_size_t)(*end - *start);
	vm_page_t		m;
	kern_return_t		kret;
	vm_object_offset_t	object_size;
	int			age_of_cache;
	vm_size_t		pre_heat_size;
	unsigned int		ele_cache;
	unsigned int		end_cache = 0;
	unsigned int		start_cache = 0;
	unsigned int		memory_scarce = 0;

	if((object->private) || !(object->pager))
		return;

	if (!object->internal) {
		/* XXX FBDP !internal doesn't mean vnode pager */
		kret = vnode_pager_get_object_size(
       		 	object->pager,
			&object_size);
		if (kret != KERN_SUCCESS) {
			object_size = object->size;
		}
	} else {
		object_size = object->size;
	}

	if((!tws) || (!tws_lock_try(tws))) {
		return;
	}
	age_of_cache = ((sched_tick 
			- tws->time_of_creation) >> SCHED_TICK_SHIFT);

	if (vm_page_free_count < (2 * vm_page_free_target))
	        memory_scarce = 1;

	/* When pre-heat files are not available, resort to speculation */
	/* based on size of file */

	if (tws->startup_cache || object->internal || age_of_cache > 45) {
		pre_heat_size = 0;
	} else {
		if (object_size > (vm_object_offset_t)(1024 * 1024))
			pre_heat_size = 8 * PAGE_SIZE;
		else if (object_size > (vm_object_offset_t)(128 * 1024))
			pre_heat_size = 4 * PAGE_SIZE;
		else
			pre_heat_size = 2 * PAGE_SIZE;
	}

       	if (tws->startup_cache) {
	        int target_page_count;

		if (memory_scarce)
		        target_page_count = 16;
		else
		        target_page_count = 4;

	        if (tws_test_for_community(tws, object, *start, target_page_count, &ele_cache))
		{
	                start_cache = ele_cache;
			*start = *start & TWS_HASH_OFF_MASK;
			*end = *start + (32 * PAGE_SIZE_64);

			if (*end > object_size) {
				*end = round_page_64(object_size);
				max_length = 0;
			} else
			        end_cache = ele_cache;

			while (max_length > ((*end - *start) + (32 * PAGE_SIZE))) {
			        int	expanded;

				expanded = 0;
				after = *end;

				if ((after + (32 * PAGE_SIZE_64)) <= object_size &&
				    (tws_test_for_community(tws, object, after, 8, &ele_cache))) {

					*end = after + (32 * PAGE_SIZE_64);
					end_cache = ele_cache;
					expanded = 1;
				}
				if (max_length < ((*end - *start) + (32 * PAGE_SIZE_64))) {
					break;
				}
				if (*start) {
				        before = (*start - PAGE_SIZE_64) & TWS_HASH_OFF_MASK;

					if (tws_test_for_community(tws, object, before, 8, &ele_cache)) {

					        *start = before;
						start_cache = ele_cache;
						expanded = 1;
					}
				}
				if (expanded == 0)
					break;
			}
			if (end_cache)
			        *end -= PAGE_SIZE_64;

			if (start_cache != 0) {
				unsigned int mask;

				for (mask = 1; mask != 0; mask = mask << 1) {
			        	if (*start == original_start)
				        	break;
					if (!(start_cache & mask))
						*start += PAGE_SIZE_64;
					else
						break;
				}
			}
			if (end_cache != 0) {
				unsigned int mask;

				for (mask = 0x80000000; 
						mask != 0; mask = mask >> 1) {
			        	if (*end == original_end)
				       		 break;
					if (!(end_cache & mask))
						*end -= PAGE_SIZE_64;
					else
						break;
				}
			}
			tws_unlock(tws);

			if (*end < original_end)
			        *end = original_end;
			return;
		}
	}

	while ((length < max_length) &&
		(object_size >= 
			(after + PAGE_SIZE_64))) {
		if(length >= pre_heat_size) {
		   if(tws_internal_lookup(tws, after, object,
				&line) != KERN_SUCCESS) {
			vm_object_offset_t	extend;
				
			extend = after + PAGE_SIZE_64;
			if(tws_internal_lookup(tws, extend, object,
						&line) != KERN_SUCCESS) {
				break;
			}
		   }
		}

	        if ((object->existence_map != NULL)
					&& (!LOOK_FOR(object, after))) {
			break;
		} 

		if (vm_page_lookup(object, after) != VM_PAGE_NULL) {
			/*
			 * don't bridge resident pages
			 */
		        break;
		}

		if (object->internal) {
			/*
			 * need to acquire a real page in
			 * advance because this acts as
			 * a throttling mechanism for
			 * data_requests to the default
			 * pager.  If this fails, give up
			 * trying to find any more pages
			 * in the cluster and send off the
			 * request for what we already have.
			 */
			if ((m = vm_page_grab()) == VM_PAGE_NULL) {
				break;
			}
	        } else if ((m = vm_page_grab_fictitious())
			       	        == VM_PAGE_NULL) {
			break;
		}
		m->absent = TRUE;
		m->unusual = TRUE;
	        m->clustered = TRUE;
		m->list_req_pending = TRUE;

	        vm_page_insert(m, object, after);
		object->absent_count++;
		after += PAGE_SIZE_64;
		length += PAGE_SIZE;
	}
	*end = after;
	while (length < max_length) {
		if (before == 0) 
			break;
		before -= PAGE_SIZE_64;

		if(length >= pre_heat_size) {
		   if(tws_internal_lookup(tws, before, object,
				&line) != KERN_SUCCESS) {
			vm_object_offset_t	extend;
				
			extend = before;
			if (extend == 0)
				break;
			extend -= PAGE_SIZE_64;
			if(tws_internal_lookup(tws, extend, object,
					&line) != KERN_SUCCESS) {
				break;
			}
		   }
		}
		if ((object->existence_map != NULL) 
					&& (!LOOK_FOR(object, before))) {
			break;
		}

		if (vm_page_lookup(object, before) != VM_PAGE_NULL) {
			/*
			 * don't bridge resident pages
			 */
		        break;
		}

		if (object->internal) {
			/*
			 * need to acquire a real page in
			 * advance because this acts as
			 * a throttling mechanism for
			 * data_requests to the default
			 * pager.  If this fails, give up
			 * trying to find any more pages
			 * in the cluster and send off the
			 * request for what we already have.
			 */
			if ((m = vm_page_grab()) == VM_PAGE_NULL) {
				break;
			}
	        } else if ((m = vm_page_grab_fictitious())
			       	        == VM_PAGE_NULL) {
			break;
	        }
	        m->absent = TRUE;
		m->unusual = TRUE;
	        m->clustered = TRUE;
		m->list_req_pending = TRUE;

	        vm_page_insert(m, object, before);
		object->absent_count++;
		*start -= PAGE_SIZE_64;
		length += PAGE_SIZE;
	}
	tws_unlock(tws);
}

void
tws_line_signal(
	tws_hash_t	tws,
	vm_map_t	map,
	tws_hash_line_t hash_line,
	vm_offset_t	target_page)
{
	unsigned int		i,j;
	vm_object_t		object;
	vm_object_offset_t	offset;
	vm_object_offset_t	before;
	vm_object_offset_t	after;
	struct tws_hash_ele	*element;
	vm_page_t		m,p;
	kern_return_t		rc;

	if(tws->style != TWS_HASH_STYLE_SIGNAL)
		return;

	vm_map_lock(map);
	for (i=0; i<tws->number_of_elements; i++) {

		vm_object_offset_t local_off = 0;

		if(hash_line->list[i].object == 0)
			continue;

		element = &hash_line->list[i];

		if (element->page_addr == target_page)
			continue;

		j = 1;
		while (j != 0) {
			if(j & element->page_cache)
				break;
			j <<= 1;
			local_off += PAGE_SIZE_64;
		}
		object = element->object;
		offset = element->offset + local_off;

		/* first try a fast test to speed up no-op signal */
		if (((p = vm_page_lookup(object, offset)) != NULL) 
			|| (object->pager == NULL) 
			|| (object->shadow_severed)) {
			continue;
		}	

		if((!object->alive) || 
			(!object->pager_created) || (!object->pager_ready))
			continue;

                if (object->internal) { 
			if (object->existence_map == NULL) {
				if (object->shadow)
					continue;
			} else {
				if(!LOOK_FOR(object, offset))
					continue;
			}
		}

		vm_object_reference(object);
		vm_map_unlock(map);
			
		if(object->internal) {
			m = vm_page_grab();
		} else {
			m = vm_page_grab_fictitious();
		}

		if(m == NULL) {
			vm_object_deallocate(object);
			vm_map_lock(map);
			continue;
		}

		vm_object_lock(object);
		if (((p = vm_page_lookup(object, offset)) != NULL) 
			|| (object->pager == NULL) 
			|| (object->shadow_severed)) {
			VM_PAGE_FREE(m);
			vm_object_unlock(object);
			vm_object_deallocate(object);
			vm_map_lock(map);
			continue;
		}

		vm_page_insert(m, object, offset);

		if (object->absent_count > vm_object_absent_max) {
			VM_PAGE_FREE(m);
			vm_object_unlock(object);
			vm_object_deallocate(object);
			vm_map_lock(map);
			break;
		}
		m->list_req_pending = TRUE; 
		m->absent = TRUE; 
		m->unusual = TRUE; 
		object->absent_count++;

		before = offset;
		after = offset + PAGE_SIZE_64;
		tws_build_cluster(tws, object, &before, &after, 0x16000);
		vm_object_unlock(object);

		rc = memory_object_data_request(object->pager, 
				before + object->paging_offset, 
				(vm_size_t)(after - before), VM_PROT_READ);
		if (rc != KERN_SUCCESS) {
			offset = before;
			vm_object_lock(object);
			while (offset < after) {
                        	m = vm_page_lookup(object, offset);
				if(m && m->absent && m->busy)
					VM_PAGE_FREE(m);
				offset += PAGE_SIZE;
			}
			vm_object_unlock(object);
			vm_object_deallocate(object);
		} else {
			vm_object_deallocate(object);
		}
		vm_map_lock(map);
		continue;
	}
	vm_map_unlock(map);
}

/* tws locked on entry */

tws_startup_t
tws_create_startup_list(
	tws_hash_t	tws)
{

	tws_startup_t		startup;
	unsigned int		i,j,k;
	unsigned int		total_elements;
	unsigned int		startup_size;
	unsigned int		sindex;
	unsigned int		hash_index;
	tws_startup_ptr_t	element;

	total_elements = tws->expansion_count *
			(tws->number_of_lines * tws->number_of_elements);

	startup_size = sizeof(struct tws_startup) 
			+ (total_elements * sizeof(tws_startup_ptr_t *))
			+ (total_elements * sizeof(struct tws_startup_ptr))
			+ (total_elements * sizeof(struct tws_startup_ele));
	startup = (tws_startup_t)(kalloc(startup_size));

	if(startup == NULL)
		return startup;

	bzero((char *) startup, startup_size);

	startup->table = (tws_startup_ptr_t *)
		(((int)startup) + (sizeof(struct tws_startup)));
	startup->ele = (struct tws_startup_ptr *)
			(((vm_offset_t)startup->table) + 
			(total_elements * sizeof(tws_startup_ptr_t)));

	startup->array = (struct tws_startup_ele *)
			(((vm_offset_t)startup->ele) + 
			(total_elements * sizeof(struct tws_startup_ptr)));

	startup->tws_hash_size = startup_size;
	startup->ele_count = 0;  /* burn first hash ele, else we can't tell from zero */
	startup->array_size = total_elements;
	startup->hash_count = 1;

	sindex = 0;
	
	
	for(i = 0; i<tws->number_of_lines; i++) {
	   for(j = 0; j<tws->number_of_elements; j++) {
	      for(k = 0; k<tws->expansion_count; k++) {
		tws_hash_ele_t		entry;
		unsigned int		hash_retry;
		vm_offset_t		addr;

		entry = &tws->cache[k][i].list[j];
		addr = entry->page_addr;
		hash_retry = 0;
		if(entry->object != 0) {
			/* get a hash element */
			hash_index = do_startup_hash(addr, 
						startup->array_size);

			if(startup->hash_count < total_elements) {
				element = &(startup->ele[startup->hash_count]);
				startup->hash_count += 1;
			} else {
				/* exit we're out of elements */
				break;
			}
			/* place the hash element */
			element->next = startup->table[hash_index];
			startup->table[hash_index] = (tws_startup_ptr_t)
				((int)element - (int)&startup->ele[0]);

			/* set entry OFFSET in hash element */
			element->element =  (tws_startup_ele_t)
				((int)&startup->array[sindex] - 
						(int)&startup->array[0]);
		
			startup->array[sindex].page_addr = entry->page_addr;
			startup->array[sindex].page_cache = entry->page_cache;
			startup->ele_count++;
			sindex++;
		
		}
	     }
	   }
	}

	return startup;
}


/*
 * Returns an entire cache line.  The line is deleted from the startup
 * cache on return. The caller can check startup->ele_count for an empty
 * list. Access synchronization is the responsibility of the caller.
 */

unsigned int
tws_startup_list_lookup(
	tws_startup_t	startup,
	vm_offset_t	addr)
{
	unsigned int		hash_index;
	unsigned int		page_cache_bits;
	unsigned int		startup_shift;
	tws_startup_ele_t	entry;
	vm_offset_t		next_addr;
	tws_startup_ptr_t	element;
	tws_startup_ptr_t	base_ele;
	tws_startup_ptr_t	*previous_ptr;

	page_cache_bits = 0;

	hash_index = do_startup_hash(addr, startup->array_size);

	if(((unsigned int)&(startup->table[hash_index])) >= ((unsigned int)startup + startup->tws_hash_size)) {
		return page_cache_bits = 0;
	}
	element = (tws_startup_ptr_t)((int)startup->table[hash_index] +
			(int)&startup->ele[0]);
	base_ele = element;
	previous_ptr = &(startup->table[hash_index]);
	while(element > &startup->ele[0]) {
		if (((int)element + sizeof(struct tws_startup_ptr))
			> ((int)startup + startup->tws_hash_size))  {
			return page_cache_bits;
		}
		entry = (tws_startup_ele_t)
			((int)element->element 
				+ (int)&startup->array[0]);
		if((((int)entry + sizeof(struct tws_startup_ele))
			> ((int)startup + startup->tws_hash_size)) 
				|| ((int)entry < (int)startup))  {
			return page_cache_bits;
		}
		if ((addr >= entry->page_addr) && 
			(addr <= (entry->page_addr + 0x1F000))) {
			startup_shift = (addr - entry->page_addr)>>12;
			page_cache_bits |= entry->page_cache >> startup_shift;
			/* don't dump the pages, unless the addresses */
			/* line up perfectly.  The cache may be used */
			/* by other mappings */
			entry->page_cache &= (1 << startup_shift) - 1;
			if(addr == entry->page_addr) {
				if(base_ele == element) {
					base_ele = (tws_startup_ptr_t)
						((int)element->next 
						+ (int)&startup->ele[0]);
					startup->table[hash_index] = element->next;
					element = base_ele;
				} else {
					*previous_ptr = element->next;
					element = (tws_startup_ptr_t)
						((int)*previous_ptr 
						+ (int)&startup->ele[0]);
				}
				entry->page_addr = 0;
				startup->ele_count--;
				continue;
			}
		}
		next_addr = addr + 0x1F000;
		if ((next_addr >= entry->page_addr) && 
			(next_addr <= (entry->page_addr + 0x1F000))) {
			startup_shift = (next_addr - entry->page_addr)>>12;
			page_cache_bits |= entry->page_cache << (0x1F - startup_shift);
			entry->page_cache &= ~((1 << (startup_shift + 1)) - 1);
			if(entry->page_cache == 0) {
				if(base_ele == element) {
					base_ele = (tws_startup_ptr_t)
						((int)element->next 
						+ (int)&startup->ele[0]);
					startup->table[hash_index] = element->next;
					element = base_ele;
				} else {
					*previous_ptr = element->next;
					element = (tws_startup_ptr_t)
						((int)*previous_ptr 
						+ (int)&startup->ele[0]);
				}
				entry->page_addr = 0;
				startup->ele_count--;
				continue;
			}
		}
		previous_ptr = &(element->next);
		element = (tws_startup_ptr_t) 
			((int) element->next + (int) &startup->ele[0]);
	}

	return page_cache_bits;
}

kern_return_t
tws_send_startup_info(
		task_t		task)
{

	tws_hash_t		tws;

	task_lock(task);
	tws = task->dynamic_working_set;
	task_unlock(task);
	if(tws == NULL) {
		return KERN_FAILURE;
	}
	return tws_internal_startup_send(tws);
}


kern_return_t
tws_internal_startup_send(
		tws_hash_t	tws)
{

	tws_startup_t 		scache;

	if(tws == NULL) {
		return KERN_FAILURE;
	}
	tws_lock(tws);
	/* used to signal write or release depending on state of tws */
	if(tws->startup_cache) {
		vm_offset_t	startup_buf;
		vm_size_t	size;
		startup_buf = (vm_offset_t)tws->startup_cache;
		size = tws->startup_cache->tws_hash_size;
		tws->startup_cache = 0;
		tws_unlock(tws);
		kmem_free(kernel_map, startup_buf, size);
		return KERN_SUCCESS;
	}
   	if(tws->startup_name == NULL) {
		tws_unlock(tws);
		return KERN_FAILURE;
	}
	scache = tws_create_startup_list(tws);
	if(scache == NULL)
		return KERN_FAILURE;
	bsd_write_page_cache_file(tws->uid, tws->startup_name, 
				  (caddr_t) scache, scache->tws_hash_size, 
				  tws->mod, tws->fid);
	kfree(scache, scache->tws_hash_size);
	kfree(tws->startup_name, tws->startup_name_length);
	tws->startup_name = NULL;
	tws_unlock(tws);
	return KERN_SUCCESS;
}

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

{
		tws_startup_t	startup;
		vm_offset_t	cache_size;	
		kern_return_t	error;
		int		fid;
		int		mod;
		
		*new_info = FALSE;
		/* don't pre-heat kernel task */
		if(task == kernel_task)
			return KERN_SUCCESS;
		error = bsd_read_page_cache_file(uid, &fid, 
					&mod, app_name, 
					app_vp,
					(vm_offset_t *) &startup, 
					&cache_size);
		if(error) {
			return KERN_FAILURE;
		}
		if(startup == NULL) {
			/* Entry for app does not exist, make */
			/* one */
			/* we will want our own copy of the shared */
			/* regions to pick up a true picture of all */
			/* the pages we will touch. */
			if((lsf_zone->count * lsf_zone->elem_size) 
						> (lsf_zone->max_size >> 1)) {
				/* We don't want to run out of shared memory */
				/* map entries by starting too many private versions */
				/* of the shared library structures */
				return KERN_SUCCESS;
			}
			*new_info = TRUE;

			error = tws_write_startup_file(task, 
					fid, mod, app_name, uid);
			if(error)
				return error;

		} else {
			error = tws_read_startup_file(task, 
						(tws_startup_t)startup, 
						cache_size);
			if(error) {
				kmem_free(kernel_map, 
					(vm_offset_t)startup, cache_size); 
				return error;
			}
		}
		return KERN_SUCCESS;
}

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

		string_length = strlen(name);

restart:
		task_lock(task);
		tws = task->dynamic_working_set;
		task_unlock(task);

		if(tws == NULL) {
			kern_return_t error;

			/* create a dynamic working set of normal size */
			if((error = task_working_set_create(task, 0, 0, TWS_HASH_STYLE_DEFAULT)) != KERN_SUCCESS)
				return error;
			/* we need to reset tws and relock */
			goto restart;
		}
		tws_lock(tws);

		if(tws->startup_name != NULL) {
			tws_unlock(tws);
			return KERN_FAILURE;
		}

		tws->startup_name = (char *)
			kalloc((string_length + 1) * (sizeof(char)));
		if(tws->startup_name == NULL) {
			tws_unlock(tws);
			return KERN_FAILURE;
		}

		bcopy(name, (char *)tws->startup_name, string_length + 1);
		tws->startup_name_length = (string_length + 1) * sizeof(char);
		tws->uid = uid;
		tws->fid = fid;
		tws->mod = mod;

		tws_unlock(tws);
		return KERN_SUCCESS;
}

unsigned long tws_read_startup_file_rejects = 0;

kern_return_t
tws_read_startup_file(
		task_t			task,
		tws_startup_t		startup,
		vm_offset_t		cache_size)
{
		tws_hash_t		tws;
		int			lines;
		int			old_exp_count;
		unsigned int		ele_count;

restart:
		task_lock(task);
		tws = task->dynamic_working_set;

		/* create a dynamic working set to match file size */

		/* start with total size of the data we got from app_profile */
		ele_count = cache_size;
		/* skip the startup header */
		ele_count -= sizeof(struct tws_startup); 
		/*
		 * For each startup cache entry, we have one of these:
		 *	tws_startup_ptr_t startup->table[];
		 * 	struct tws_startup_ptr startup->ele[];
		 *	struct tws_startup_ele startup->array[];
		 */
		ele_count /= (sizeof (tws_startup_ptr_t) +
			      sizeof (struct tws_startup_ptr) +
			      sizeof (struct tws_startup_ele));

		/*
		 * Sanity check: make sure the value for startup->array_size
		 * that we read from the app_profile file matches the size
		 * of the data we read from disk.  If it doesn't match, we
		 * can't trust the data and we just drop it all.
		 */
		if (cache_size < sizeof(struct tws_startup) ||
		    startup->array_size != ele_count) {
			tws_read_startup_file_rejects++;
			task_unlock(task);
			kmem_free(kernel_map, (vm_offset_t)startup, cache_size); 
			return(KERN_SUCCESS);
		}

		/*
		 * We'll create the task working set with the default row size
		 * (TWS_ARRAY_SIZE), so this will give us the number of lines
		 * we need to store all the data from the app_profile startup
		 * cache.
		 */
		lines = ele_count / TWS_ARRAY_SIZE;

		if(lines <= TWS_SMALL_HASH_LINE_COUNT) {
			lines = TWS_SMALL_HASH_LINE_COUNT;
			task_unlock(task);
			kmem_free(kernel_map, (vm_offset_t)startup, cache_size); 
			return(KERN_SUCCESS);
		} else {
			old_exp_count = lines/TWS_HASH_LINE_COUNT;
			if((old_exp_count * TWS_HASH_LINE_COUNT) != lines) {
				lines = (old_exp_count + 1) 
						* TWS_HASH_LINE_COUNT;
			}
			if(tws == NULL) {
				kern_return_t error;

				task_unlock(task);
				if ((error = task_working_set_create(task, lines, 0, TWS_HASH_STYLE_DEFAULT)) != KERN_SUCCESS)
					return error;
				/* we need to reset tws and relock */
				goto restart;
			} else {
				task_unlock(task);
				tws_expand_working_set(
					(void *)tws, lines, TRUE);
			}
		}
		
		tws_lock(tws);
		
		if(tws->startup_cache != NULL) {
			tws_unlock(tws);
			return KERN_FAILURE;
		}


		/* now need to fix up internal table pointers */
		startup->table = (tws_startup_ptr_t *)
			(((int)startup) + (sizeof(struct tws_startup)));
		startup->ele = (struct tws_startup_ptr *)
			(((vm_offset_t)startup->table) + 
			(startup->array_size * sizeof(tws_startup_ptr_t)));
		startup->array = (struct tws_startup_ele *)
			(((vm_offset_t)startup->ele) + 
			(startup->array_size * sizeof(struct tws_startup_ptr)));
		/* the allocation size and file size should be the same */
		/* just in case their not, make sure we dealloc correctly  */
		startup->tws_hash_size = cache_size;

		tws->startup_cache = startup;
		tws_unlock(tws);
		return KERN_SUCCESS;
}


void
tws_hash_ws_flush(tws_hash_t tws) {
	tws_startup_t 		scache;
	if(tws == NULL) {
		return;
	}
	tws_lock(tws);
	if(tws->startup_name != NULL) {
		scache = tws_create_startup_list(tws);
		if(scache == NULL) {
			/* dump the name cache, we'll */
			/* get it next time */
			kfree(tws->startup_name, tws->startup_name_length);
			tws->startup_name = NULL;
			tws_unlock(tws);
			return;
		}
		bsd_write_page_cache_file(tws->uid, tws->startup_name, 
				(caddr_t) scache, scache->tws_hash_size, 
				tws->mod, tws->fid);
		kfree(scache, scache->tws_hash_size);
		kfree(tws->startup_name, tws->startup_name_length);
		tws->startup_name = NULL;
	}
	tws_unlock(tws);
	return;
}

void
tws_hash_destroy(tws_hash_t	tws)
{
	unsigned int	i,k;

	if(tws->startup_cache != NULL) {
		kmem_free(kernel_map,
			(vm_offset_t)tws->startup_cache, 
			tws->startup_cache->tws_hash_size);
		tws->startup_cache = NULL;
	}
	if(tws->startup_name != NULL) {
		tws_internal_startup_send(tws);
	}
	for (i=0; i<tws->number_of_lines; i++) {
		for(k=0; k<tws->expansion_count; k++) {
			/* clear the object refs */
			tws_hash_line_clear(tws, &(tws->cache[k][i]), NULL, FALSE);
		}
	}
	i = 0;
	while (i < tws->expansion_count) {
		
		kfree(tws->table[i],
		      sizeof(tws_hash_ptr_t) 
		      * tws->number_of_lines 
		      * tws->number_of_elements);
		kfree(tws->table_ele[i], 
		      sizeof(struct tws_hash_ptr) 
		      * tws->number_of_lines 
		      * tws->number_of_elements);
		kfree(tws->alt_ele[i], 
		      sizeof(struct tws_hash_ptr) 
		      * tws->number_of_lines 
		      * tws->number_of_elements);
		kfree(tws->cache[i],
		      sizeof(struct tws_hash_line) * tws->number_of_lines);
		i++;
	}
	if(tws->startup_name != NULL) {
		kfree(tws->startup_name, tws->startup_name_length);
	}
	kfree(tws, sizeof(struct tws_hash));
}

void
tws_hash_clear(tws_hash_t	tws)
{
	unsigned int	i, k;

	for (i=0; i<tws->number_of_lines; i++) {
		for(k=0; k<tws->expansion_count; k++) {
			/* clear the object refs */
			tws_hash_line_clear(tws, &(tws->cache[k][i]), NULL, FALSE);
		}
	}
}

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

	if (lines == 0) {
		lines = TWS_HASH_LINE_COUNT;
	}
	if (rows == 0) {
		rows = TWS_ARRAY_SIZE;
	}
	if (style == TWS_HASH_STYLE_DEFAULT) {
		style = TWS_HASH_STYLE_BASIC;
	}
	task_lock(task);
	if(task->dynamic_working_set != 0) {
		task_unlock(task);
		return(KERN_FAILURE);
	} else if((task->dynamic_working_set =
		tws_hash_create(lines, rows, style)) == 0) {
		task_unlock(task);
		return(KERN_NO_SPACE);
	}
	task_unlock(task);
	return KERN_SUCCESS;
}


/* Internal use only routines */


/* 
 * internal sub-function for address space lookup
 * returns the target element and the address of the
 * previous pointer  The previous pointer is the address 
 * of the pointer pointing to the target element.
 * TWS must be locked
 */

void
tws_traverse_address_hash_list (
	tws_hash_t 		tws, 
	unsigned int		index,
	vm_offset_t		page_addr,
	vm_object_t		object,
	vm_object_offset_t	offset,
	vm_map_t		map,
	tws_hash_ptr_t		*target_ele,
	tws_hash_ptr_t		**previous_ptr,
	tws_hash_ptr_t		**free_list,
	unsigned int		exclusive_addr)
{
	unsigned int	k;
	tws_hash_ptr_t	cache_ele;
	tws_hash_ptr_t	base_ele;

	*target_ele = NULL;
	*previous_ptr = NULL;

	for(k=0; k<tws->expansion_count; k++) {
		tws_hash_ele_t ele;
		cache_ele = tws->table[k][index];
		base_ele = cache_ele;
		*previous_ptr = (tws_hash_ptr_t *)&(tws->table[k][index]);
		while(cache_ele != NULL) {
			if(((unsigned int)
				cache_ele->element & TWS_ADDR_HASH) == 0) {
				*previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
				cache_ele = cache_ele->next;
				continue;
			}
			ele = (tws_hash_ele_t)((unsigned int)
				cache_ele->element & ~TWS_ADDR_HASH);
			if ((ele == 0) || (ele->object == 0)) {
				/* A little clean-up of empty elements */
				cache_ele->element = 0;
				if(base_ele == cache_ele) {
					base_ele = cache_ele->next;
					tws->table[k][index] = cache_ele->next;
					cache_ele->next = tws->free_hash_ele[k];
					tws->free_hash_ele[k] = cache_ele;
					cache_ele = base_ele;
				} else {
					**previous_ptr = cache_ele->next;
					cache_ele->next = tws->free_hash_ele[k];
					tws->free_hash_ele[k] = cache_ele;
					cache_ele = **previous_ptr;
				}
				continue;
			}
	
			if ((ele->page_addr <= page_addr) 
				&& (page_addr <= (ele->page_addr + 
				(vm_offset_t)TWS_INDEX_MASK))
				&& ((object == NULL) 
					|| ((object == ele->object)
					&& (offset == ele->offset)
					&& (map == ele->map)))) {
				if(exclusive_addr) {
					int delta;
					delta = ((page_addr - ele->page_addr)
					 >> 12);
					if((1 << delta) & ele->page_cache) {
						/* We've found a match */
						*target_ele = cache_ele;
						*free_list = 
						   (tws_hash_ptr_t *)
						   &(tws->free_hash_ele[k]);
						return;
					}
				} else {
					/* We've found a match */
					*target_ele = cache_ele;
					*free_list = (tws_hash_ptr_t *)
						&(tws->free_hash_ele[k]);
					return;
				}
			}
			*previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
			cache_ele = cache_ele->next;
		}
	}
}


/* 
 * internal sub-function for object space lookup
 * returns the target element and the address of the
 * previous pointer  The previous pointer is the address 
 * of the pointer pointing to the target element.
 * TWS must be locked
 */


void
tws_traverse_object_hash_list (
	tws_hash_t 		tws, 
	unsigned int		index,
	vm_object_t		object,
	vm_object_offset_t	offset,
	unsigned int		pagemask,
	tws_hash_ptr_t		*target_ele,
	tws_hash_ptr_t		**previous_ptr,
	tws_hash_ptr_t		**free_list)
{
	unsigned int	k;
	tws_hash_ptr_t	cache_ele;
	tws_hash_ptr_t	base_ele;

	*target_ele = NULL;
	*previous_ptr = NULL;

	for(k=0; k<tws->expansion_count; k++) {
		cache_ele = tws->table[k][index];
		base_ele = cache_ele;
		*previous_ptr = &(tws->table[k][index]);
		while(cache_ele != NULL) {
			if((((unsigned int)cache_ele->element) 
						& TWS_ADDR_HASH) != 0) {
				*previous_ptr = &(cache_ele->next);
				cache_ele = cache_ele->next;
				continue;
			}
			if ((cache_ele->element == 0) || 
				(cache_ele->element->object == 0)) {
				/* A little clean-up of empty elements */
				cache_ele->element = 0;
				if(base_ele == cache_ele) {
					base_ele = cache_ele->next;
					tws->table[k][index] = cache_ele->next;
					cache_ele->next = tws->free_hash_ele[k];
					tws->free_hash_ele[k] = cache_ele;
					cache_ele = tws->table[k][index];
				} else {
					**previous_ptr = cache_ele->next;
					cache_ele->next = tws->free_hash_ele[k];
					tws->free_hash_ele[k] = cache_ele;
					cache_ele = **previous_ptr;
				}
				continue;
			}
			if ((cache_ele->element->object == object)
				&& (cache_ele->element->offset == 
				(offset - (offset & ~TWS_HASH_OFF_MASK)))) {
				if((cache_ele->element->page_cache & pagemask) 
					|| (pagemask == 0xFFFFFFFF)) {
					/* We've found a match */
					*target_ele = cache_ele;
					*free_list = &(tws->free_hash_ele[k]);
					return;
				}
			}
			*previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
			cache_ele = cache_ele->next;
		}
	}
}


/*
 * For a given object/offset, discover whether the indexed 32 page frame 
 * containing the object/offset exists and if their are at least threshold
 * pages present.  Returns true if population meets threshold.
 */
int 
tws_test_for_community(
		tws_hash_t		tws, 
		vm_object_t		object, 
		vm_object_offset_t	offset, 
		unsigned int		threshold, 
		unsigned int		*pagemask) 
{
	int	index;
	tws_hash_ptr_t	cache_ele;
	tws_hash_ptr_t	*trailer;
	tws_hash_ptr_t	*free_list;
	int		community = 0;

	index = do_tws_hash(object, offset, 
			tws->number_of_elements, tws->number_of_lines);
	tws_traverse_object_hash_list(tws, index, object, offset, 0xFFFFFFFF,
		&cache_ele, &trailer, &free_list);

	if(cache_ele != NULL) {
		int i;
		unsigned int ctr;
		ctr = 0;
		for(i=1; i!=0; i=i<<1) {
			if(i & cache_ele->element->page_cache)
				ctr++;
			if(ctr == threshold) {
				community = 1;
				*pagemask = cache_ele->element->page_cache;
				break;
			}
		}
	}

	return community;
	
}


/* 
 * Gets new hash element for object hash from free pools
 * TWS must be locked
 */

tws_hash_ptr_t
new_obj_hash(
	tws_hash_t tws, 
	unsigned int set, 
	unsigned int index)
{
	tws_hash_ptr_t element;

	if(tws->obj_free_count[set] < tws->number_of_lines * tws->number_of_elements) {
		element = &(tws->table_ele[set][tws->obj_free_count[set]]);
		tws->obj_free_count[set]+=1;
	} else if(tws->free_hash_ele[set] == NULL) {
		return NULL;
	} else {
		element = tws->free_hash_ele[set];
		if(element == NULL)
			return element;
		tws->free_hash_ele[set] = tws->free_hash_ele[set]->next;
	}
	element->element = 0;
	element->next = tws->table[set][index];
	tws->table[set][index] = element;
	return element;
}

/* 
 * Gets new hash element for addr hash from free pools
 * TWS must be locked
 */

tws_hash_ptr_t
new_addr_hash(
	tws_hash_t tws, 
	unsigned int set, 
	unsigned int index)
{
	tws_hash_ptr_t element;

	if(tws->addr_free_count[set] 
			< tws->number_of_lines * tws->number_of_elements) {
		element = &(tws->alt_ele[set][tws->addr_free_count[set]]);
		tws->addr_free_count[set]+=1;
	} else if(tws->free_hash_ele[set] == NULL) {
		return NULL;
	} else {
		element = tws->free_hash_ele[set];
		if(element == NULL)
			return element;
		tws->free_hash_ele[set] = tws->free_hash_ele[set]->next;
	}
	element->element = (tws_hash_ele_t)TWS_ADDR_HASH;
	element->next = tws->table[set][index];
	tws->table[set][index] = element;
	return element;
}