]> git.saurik.com Git - apple/xnu.git/blob - osfmk/vm/task_working_set.c
projects / apple / xnu.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
xnu-792.6.61.tar.gz
[apple/xnu.git] / osfmk / vm / task_working_set.c
1 /*
2 * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * The contents of this file constitute Original Code as defined in and
7 * are subject to the Apple Public Source License Version 1.1 (the
8 * "License"). You may not use this file except in compliance with the
9 * License. Please obtain a copy of the License at
10 * http://www.apple.com/publicsource and read it before using this file.
11 *
12 * This Original Code and all software distributed under the License are
13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the
17 * License for the specific language governing rights and limitations
18 * under the License.
19 *
20 * @APPLE_LICENSE_HEADER_END@
21 */
22 /*
23 */
24 /*
25 * File: vm/task_working_set.c
26 * Author: Chris Youngworth
27 * Date: 2001
28 *
29 * Working set detection and maintainence module
30 */
31
32
33 #include <mach/mach_types.h>
34 #include <mach/memory_object.h>
35 #include <mach/shared_memory_server.h>
36 #include <vm/task_working_set.h>
37 #include <vm/vm_kern.h>
38 #include <vm/vm_map.h>
39 #include <vm/vm_page.h>
40 #include <vm/vm_pageout.h>
41 #include <kern/sched.h>
42 #include <kern/kalloc.h>
43
44 #include <vm/vm_protos.h>
45
46 /*
47 * LP64todo - Task Working Set Support is for 32-bit only
48 */
49 extern zone_t lsf_zone;
50
51 /* declarations for internal use only routines */
52 int startup_miss = 0;
53
54 tws_hash_t
55 tws_hash_create(
56 unsigned int lines,
57 unsigned int rows,
58 unsigned int style);
59
60 kern_return_t
61 tws_write_startup_file(
62 task_t task,
63 int fid,
64 int mod,
65 char *name,
66 unsigned int string_length);
67
68 kern_return_t
69 tws_read_startup_file(
70 task_t task,
71 tws_startup_t startup,
72 vm_offset_t cache_size);
73
74 tws_startup_t
75 tws_create_startup_list(
76 tws_hash_t tws);
77
78 unsigned int
79 tws_startup_list_lookup(
80 tws_startup_t startup,
81 vm_offset_t addr);
82
83 kern_return_t
84 tws_internal_startup_send(
85 tws_hash_t tws);
86
87 void
88 tws_hash_line_clear(
89 tws_hash_t tws,
90 tws_hash_line_t hash_line,
91 vm_object_t object,
92 boolean_t live);
93
94 void
95 tws_hash_clear(
96 tws_hash_t tws);
97
98 void
99 tws_traverse_address_hash_list (
100 tws_hash_t tws,
101 unsigned int index,
102 vm_offset_t page_addr,
103 vm_object_t object,
104 vm_object_offset_t offset,
105 vm_map_t map,
106 tws_hash_ptr_t *target_ele,
107 tws_hash_ptr_t **previous_ptr,
108 tws_hash_ptr_t **free_list,
109 unsigned int exclusive_addr);
110
111 void
112 tws_traverse_object_hash_list (
113 tws_hash_t tws,
114 unsigned int index,
115 vm_object_t object,
116 vm_object_offset_t offset,
117 unsigned int pagemask,
118 tws_hash_ptr_t *target_ele,
119 tws_hash_ptr_t **previous_ptr,
120 tws_hash_ptr_t **free_list);
121
122 tws_hash_ptr_t
123 new_addr_hash(
124 tws_hash_t tws,
125 unsigned int set,
126 unsigned int index);
127
128 tws_hash_ptr_t
129 new_obj_hash(
130 tws_hash_t tws,
131 unsigned int set,
132 unsigned int index);
133
134 int tws_test_for_community(
135 tws_hash_t tws,
136 vm_object_t object,
137 vm_object_offset_t offset,
138 unsigned int threshold,
139 unsigned int *pagemask);
140
141 kern_return_t
142 tws_internal_lookup(
143 tws_hash_t tws,
144 vm_object_offset_t offset,
145 vm_object_t object,
146 tws_hash_line_t *line);
147
148 /* Note: all of the routines below depend on the associated map lock for */
149 /* synchronization, the map lock will be on when the routines are called */
150 /* and on when they return */
151
152 tws_hash_t
153 tws_hash_create(
154 unsigned int lines,
155 unsigned int rows,
156 unsigned int style)
157 {
158 tws_hash_t tws;
159
160 if ((style != TWS_HASH_STYLE_BASIC) &&
161 (style != TWS_HASH_STYLE_BASIC)) {
162 return((tws_hash_t)NULL);
163 }
164
165
166 tws = (tws_hash_t)(kalloc(sizeof(struct tws_hash)));
167 if(tws == (tws_hash_t)NULL)
168 return tws;
169
170 if((tws->table[0] = (tws_hash_ptr_t *)
171 kalloc(sizeof(tws_hash_ptr_t) * lines * rows))
172 == NULL) {
173 kfree(tws, sizeof(struct tws_hash));
174 return (tws_hash_t)NULL;
175 }
176 if((tws->table_ele[0] = (tws_hash_ptr_t)
177 kalloc(sizeof(struct tws_hash_ptr) * lines * rows))
178 == NULL) {
179 kfree(tws->table[0], sizeof(tws_hash_ptr_t) * lines * rows);
180 kfree(tws, sizeof(struct tws_hash));
181 return (tws_hash_t)NULL;
182 }
183 if((tws->alt_ele[0] = (tws_hash_ptr_t)
184 kalloc(sizeof(struct tws_hash_ptr) * lines * rows))
185 == NULL) {
186 kfree(tws->table[0], sizeof(tws_hash_ptr_t) * lines * rows);
187 kfree(tws->table_ele[0],
188 sizeof(struct tws_hash_ptr) * lines * rows);
189 kfree(tws, sizeof(struct tws_hash));
190 return (tws_hash_t)NULL;
191 }
192 if((tws->cache[0] = (struct tws_hash_line *)
193 kalloc(sizeof(struct tws_hash_line) * lines))
194 == NULL) {
195 kfree(tws->table[0], sizeof(tws_hash_ptr_t) * lines * rows);
196 kfree(tws->table_ele[0],
197 sizeof(struct tws_hash_ptr) * lines * rows);
198 kfree(tws->alt_ele[0],
199 sizeof(struct tws_hash_ptr) * lines * rows);
200 kfree(tws, sizeof(struct tws_hash));
201 return (tws_hash_t)NULL;
202 }
203 tws->free_hash_ele[0] = (tws_hash_ptr_t)0;
204 tws->obj_free_count[0] = 0;
205 tws->addr_free_count[0] = 0;
206
207 /* most defaults are such that a bzero will initialize */
208 bzero((char *)tws->table[0],sizeof(tws_hash_ptr_t)
209 * lines * rows);
210 bzero((char *)tws->table_ele[0],sizeof(struct tws_hash_ptr)
211 * lines * rows);
212 bzero((char *)tws->alt_ele[0],sizeof(struct tws_hash_ptr)
213 * lines * rows);
214 bzero((char *)tws->cache[0], sizeof(struct tws_hash_line)
215 * lines);
216
217 mutex_init(&tws->lock, 0);
218 tws->style = style;
219 tws->current_line = 0;
220 tws->pageout_count = 0;
221 tws->line_count = 0;
222 tws->startup_cache = NULL;
223 tws->startup_name = NULL;
224 tws->number_of_lines = lines;
225 tws->number_of_elements = rows;
226 tws->expansion_count = 1;
227 tws->lookup_count = 0;
228 tws->insert_count = 0;
229 tws->time_of_creation = sched_tick;
230
231 return tws;
232 }
233
234
235 extern vm_page_t
236 vm_page_lookup_nohint(vm_object_t object, vm_object_offset_t offset);
237
238
239 void
240 tws_hash_line_clear(
241 tws_hash_t tws,
242 tws_hash_line_t hash_line,
243 __unused vm_object_t object,
244 boolean_t live)
245 {
246 struct tws_hash_ele *hash_ele;
247 struct tws_hash_ptr **trailer;
248 struct tws_hash_ptr **free_list;
249 tws_hash_ele_t addr_ele;
250 int index;
251 unsigned int i, j;
252 int dump_pmap;
253 int hash_loop;
254
255
256 if(tws->line_count < tws->number_of_lines) {
257 tws->line_count++;
258 dump_pmap = 1;
259 } else {
260 if(tws->pageout_count != vm_pageout_scan_event_counter) {
261 tws->pageout_count =
262 vm_pageout_scan_event_counter;
263 tws->line_count = 0;
264 dump_pmap = 1;
265 } else {
266 dump_pmap = 0;
267 }
268 }
269 hash_line->ele_count = 0;
270
271 for (i=0; i<tws->number_of_elements; i++) {
272 hash_loop = 0;
273 hash_ele = &(hash_line->list[i]);
274 if(hash_ele->object != 0) {
275
276 vm_object_offset_t local_off = 0;
277 tws_hash_ptr_t cache_ele;
278
279 index = alt_tws_hash(
280 hash_ele->page_addr & TWS_ADDR_OFF_MASK,
281 tws->number_of_elements,
282 tws->number_of_lines);
283
284 tws_traverse_address_hash_list(tws, index,
285 hash_ele->page_addr, hash_ele->object,
286 hash_ele->offset, hash_ele->map,
287 &cache_ele, &trailer, &free_list, 0);
288 if(cache_ele != NULL) {
289 addr_ele = (tws_hash_ele_t)((unsigned int)
290 (cache_ele->element) & ~TWS_ADDR_HASH);
291 if(addr_ele != hash_ele)
292 panic("tws_hash_line_clear:"
293 " out of sync\n");
294 cache_ele->element = 0;
295 *trailer = cache_ele->next;
296 cache_ele->next = *free_list;
297 *free_list = cache_ele;
298 }
299
300 index = alt_tws_hash(
301 (hash_ele->page_addr - 0x1f000)
302 & TWS_ADDR_OFF_MASK,
303 tws->number_of_elements,
304 tws->number_of_lines);
305
306 tws_traverse_address_hash_list(tws, index,
307 hash_ele->page_addr, hash_ele->object,
308 hash_ele->offset, hash_ele->map,
309 &cache_ele, &trailer, &free_list, 0);
310
311 if(cache_ele != NULL) {
312 addr_ele = (tws_hash_ele_t)((unsigned int)
313 (cache_ele->element) & ~TWS_ADDR_HASH);
314 if(addr_ele != hash_ele)
315 panic("tws_hash_line_clear: "
316 "out of sync\n");
317 cache_ele->element = 0;
318 *trailer = cache_ele->next;
319 cache_ele->next = *free_list;
320 *free_list = cache_ele;
321 }
322
323
324 if((hash_ele->map != NULL) && (live)) {
325 vm_page_t p;
326
327 #if 0
328 if (object != hash_ele->object) {
329 if (object)
330 vm_object_unlock(object);
331 vm_object_lock(hash_ele->object);
332 }
333 #endif
334 if (dump_pmap == 1) {
335 for (j = 0x1; j != 0; j = j<<1) {
336 if(j & hash_ele->page_cache) {
337 p = vm_page_lookup_nohint(hash_ele->object,
338 hash_ele->offset + local_off);
339 if((p != NULL) && (p->wire_count == 0)) {
340 pmap_remove_some_phys((pmap_t)vm_map_pmap(current_map()),
341 p->phys_page);
342 }
343 }
344 local_off += PAGE_SIZE_64;
345 }
346 }
347 #if 0
348 if (object != hash_ele->object) {
349 vm_object_unlock(hash_ele->object);
350 if (object)
351 vm_object_lock(object);
352 }
353 #endif
354 }
355
356 if(tws->style == TWS_HASH_STYLE_SIGNAL) {
357 vm_object_deallocate(hash_ele->object);
358 vm_map_deallocate(hash_ele->map);
359 }
360
361 index = do_tws_hash(hash_ele->object, hash_ele->offset,
362 tws->number_of_elements,
363 tws->number_of_lines);
364
365 tws_traverse_object_hash_list(tws,
366 index, hash_ele->object, hash_ele->offset,
367 0xFFFFFFFF, &cache_ele, &trailer, &free_list);
368 if((cache_ele != NULL) && (cache_ele->element == hash_ele)) {
369 cache_ele->element = 0;
370 *trailer = cache_ele->next;
371 cache_ele->next = *free_list;
372 *free_list = cache_ele;
373 }
374 hash_ele->object = 0;
375 }
376 }
377 }
378
379 kern_return_t
380 tws_internal_lookup(
381 tws_hash_t tws,
382 vm_object_offset_t offset,
383 vm_object_t object,
384 tws_hash_line_t *line)
385 {
386 int index;
387 int loop;
388 int set;
389 int ele_line;
390 vm_offset_t pagenum;
391 tws_hash_ptr_t cache_ele;
392 tws_hash_ptr_t *trailer;
393 tws_hash_ptr_t *free_list;
394
395 /* don't cache private objects */
396 if(object->private)
397 return KERN_SUCCESS;
398
399 index = do_tws_hash(object, offset,
400 tws->number_of_elements, tws->number_of_lines);
401 loop = 0;
402
403 tws->lookup_count++;
404 if(tws->lookup_count == 0)
405 tws->insert_count = 0;
406 if(tws->startup_name != NULL) {
407 int age_of_cache;
408 age_of_cache = ((sched_tick
409 - tws->time_of_creation) >> SCHED_TICK_SHIFT);
410 if (age_of_cache > 45) {
411 return KERN_OPERATION_TIMED_OUT;
412 }
413 }
414
415 if(tws->lookup_count > (4 * tws->expansion_count
416 * tws->number_of_elements * tws->number_of_lines) &&
417 (tws->lookup_count > (2 * tws->insert_count))) {
418 if(tws->startup_cache) {
419 int age_of_cache;
420 age_of_cache = ((sched_tick
421 - tws->time_of_creation) >> SCHED_TICK_SHIFT);
422 if (age_of_cache > 45) {
423 return KERN_OPERATION_TIMED_OUT;
424 }
425 }
426 }
427
428 pagenum = (vm_offset_t)(offset & TWS_INDEX_MASK);
429 pagenum = pagenum >> 12;
430 pagenum = 1 << pagenum; /* get the appropriate page in 32 page block */
431 tws_traverse_object_hash_list(tws, index, object, offset, pagenum,
432 &cache_ele, &trailer, &free_list);
433 if(cache_ele != NULL) {
434 set = cache_ele->element->line/tws->number_of_lines;
435 ele_line = cache_ele->element->line - set;
436 *line = &tws->cache[set][ele_line];
437 return KERN_SUCCESS;
438 }
439
440 return KERN_FAILURE;
441
442
443 }
444
445 kern_return_t
446 tws_lookup(
447 tws_hash_t tws,
448 vm_object_offset_t offset,
449 vm_object_t object,
450 tws_hash_line_t *line)
451 {
452 kern_return_t kr;
453
454 if(!tws_lock_try(tws)) {
455 return KERN_FAILURE;
456 }
457 kr = tws_internal_lookup(tws,
458 offset, object, line);
459 tws_unlock(tws);
460 return kr;
461 }
462
463 kern_return_t
464 tws_expand_working_set(
465 tws_hash_t old_tws,
466 unsigned int line_count,
467 boolean_t dump_data)
468 {
469 tws_hash_t new_tws;
470 unsigned int i,j,k;
471 struct tws_hash temp;
472
473 /* Note we do an elaborate dance to preserve the header that */
474 /* task is pointing to. In this way we can avoid taking a task */
475 /* lock every time we want to access the tws */
476
477 if (old_tws->number_of_lines >= line_count) {
478 return KERN_FAILURE;
479 }
480 if((new_tws = tws_hash_create(line_count,
481 old_tws->number_of_elements, old_tws->style)) == 0) {
482 return(KERN_NO_SPACE);
483 }
484 tws_lock(old_tws);
485
486 if(!dump_data) {
487 for(i = 0; i<old_tws->number_of_lines; i++) {
488 for(j = 0; j<old_tws->number_of_elements; j++) {
489 for(k = 0; k<old_tws->expansion_count; k++) {
490 tws_hash_ele_t entry;
491 vm_object_offset_t paddr;
492 unsigned int page_index;
493 entry = &old_tws->cache[k][i].list[j];
494 if(entry->object != 0) {
495 paddr = 0;
496 for(page_index = 1; page_index != 0;
497 page_index = page_index << 1) {
498 if (entry->page_cache & page_index) {
499 tws_insert(new_tws,
500 entry->offset+paddr,
501 entry->object,
502 entry->page_addr+paddr,
503 entry->map);
504 }
505 paddr+=PAGE_SIZE;
506 }
507
508 }
509 }
510 }
511 }
512 }
513
514 temp.style = new_tws->style;
515 temp.current_line = new_tws->current_line;
516 temp.pageout_count = new_tws->pageout_count;
517 temp.line_count = new_tws->line_count;
518 temp.number_of_lines = new_tws->number_of_lines;
519 temp.number_of_elements = new_tws->number_of_elements;
520 temp.expansion_count = new_tws->expansion_count;
521 temp.lookup_count = new_tws->lookup_count;
522 temp.insert_count = new_tws->insert_count;
523 for(i = 0; i<new_tws->expansion_count; i++) {
524 temp.obj_free_count[i] = new_tws->obj_free_count[i];
525 temp.addr_free_count[i] = new_tws->addr_free_count[i];
526 temp.free_hash_ele[i] = new_tws->free_hash_ele[i];
527 temp.table[i] = new_tws->table[i];
528 temp.table_ele[i] = new_tws->table_ele[i];
529 temp.alt_ele[i] = new_tws->alt_ele[i];
530 temp.cache[i] = new_tws->cache[i];
531 }
532
533 new_tws->style = old_tws->style;
534 new_tws->current_line = old_tws->current_line;
535 new_tws->pageout_count = old_tws->pageout_count;
536 new_tws->line_count = old_tws->line_count;
537 new_tws->number_of_lines = old_tws->number_of_lines;
538 new_tws->number_of_elements = old_tws->number_of_elements;
539 new_tws->expansion_count = old_tws->expansion_count;
540 new_tws->lookup_count = old_tws->lookup_count;
541 new_tws->insert_count = old_tws->insert_count;
542 for(i = 0; i<old_tws->expansion_count; i++) {
543 new_tws->obj_free_count[i] = old_tws->obj_free_count[i];
544 new_tws->addr_free_count[i] = old_tws->addr_free_count[i];
545 new_tws->free_hash_ele[i] = old_tws->free_hash_ele[i];
546 new_tws->table[i] = old_tws->table[i];
547 new_tws->table_ele[i] = old_tws->table_ele[i];
548 new_tws->alt_ele[i] = old_tws->alt_ele[i];
549 new_tws->cache[i] = old_tws->cache[i];
550 }
551
552 old_tws->style = temp.style;
553 old_tws->current_line = temp.current_line;
554 old_tws->pageout_count = temp.pageout_count;
555 old_tws->line_count = temp.line_count;
556 old_tws->number_of_lines = temp.number_of_lines;
557 old_tws->number_of_elements = temp.number_of_elements;
558 old_tws->expansion_count = temp.expansion_count;
559 old_tws->lookup_count = temp.lookup_count;
560 old_tws->insert_count = temp.insert_count;
561 for(i = 0; i<temp.expansion_count; i++) {
562 old_tws->obj_free_count[i] = temp.obj_free_count[i];;
563 old_tws->addr_free_count[i] = temp.addr_free_count[i];;
564 old_tws->free_hash_ele[i] = NULL;
565 old_tws->table[i] = temp.table[i];
566 old_tws->table_ele[i] = temp.table_ele[i];
567 old_tws->alt_ele[i] = temp.alt_ele[i];
568 old_tws->cache[i] = temp.cache[i];
569 }
570
571 tws_hash_destroy(new_tws);
572 tws_unlock(old_tws);
573 return KERN_SUCCESS;
574 }
575
576 tws_hash_t test_tws = 0;
577
578 kern_return_t
579 tws_insert(
580 tws_hash_t tws,
581 vm_object_offset_t offset,
582 vm_object_t object,
583 vm_offset_t page_addr,
584 vm_map_t map)
585 {
586 unsigned int index;
587 unsigned int alt_index;
588 unsigned int index_enum[2];
589 unsigned int ele_index;
590 tws_hash_ptr_t cache_ele;
591 tws_hash_ptr_t obj_ele = NULL;
592 tws_hash_ptr_t addr_ele = NULL;
593 tws_hash_ptr_t *trailer;
594 tws_hash_ptr_t *free_list;
595 tws_hash_ele_t target_element = NULL;
596 unsigned int i;
597 unsigned int current_line;
598 unsigned int set;
599 int ctr;
600 unsigned int startup_cache_line;
601 int age_of_cache = 0;
602
603 if(!tws_lock_try(tws)) {
604 return KERN_FAILURE;
605 }
606 tws->insert_count++;
607 current_line = 0xFFFFFFFF;
608 set = 0;
609
610 startup_cache_line = 0;
611
612 if (tws->startup_cache) {
613 vm_offset_t startup_page_addr;
614
615 startup_page_addr = page_addr - (offset - (offset & TWS_HASH_OFF_MASK));
616
617 age_of_cache = ((sched_tick - tws->time_of_creation) >> SCHED_TICK_SHIFT);
618
619 startup_cache_line = tws_startup_list_lookup(tws->startup_cache, startup_page_addr);
620 }
621 /* This next bit of code, the and alternate hash */
622 /* are all made necessary because of IPC COW */
623
624 /* Note: the use of page_addr modified by delta from offset */
625 /* frame base means we may miss some previous entries. However */
626 /* we will not miss the present entry. This is most important */
627 /* in avoiding duplication of entries against long lived non-cow */
628 /* objects */
629 index_enum[0] = alt_tws_hash(
630 page_addr & TWS_ADDR_OFF_MASK,
631 tws->number_of_elements, tws->number_of_lines);
632
633 index_enum[1] = alt_tws_hash(
634 (page_addr - 0x1f000) & TWS_ADDR_OFF_MASK,
635 tws->number_of_elements, tws->number_of_lines);
636
637 for(ctr = 0; ctr < 2;) {
638 tws_hash_ele_t resident;
639 tws_traverse_address_hash_list(tws,
640 index_enum[ctr], page_addr, NULL,
641 0, NULL,
642 &cache_ele, &trailer, &free_list, 1);
643 if(cache_ele != NULL) {
644 /* found one */
645 resident = (tws_hash_ele_t)((unsigned int)
646 cache_ele->element & ~TWS_ADDR_HASH);
647 if((object == resident->object) &&
648 resident->offset ==
649 (offset & TWS_HASH_OFF_MASK)) {
650 /* This is our object/offset */
651 resident->page_cache
652 |= startup_cache_line;
653 resident->page_cache |=
654 (1<<(((vm_offset_t)
655 (offset & TWS_INDEX_MASK))>>12));
656 tws_unlock(tws);
657 if (age_of_cache > 45)
658 return KERN_OPERATION_TIMED_OUT;
659 return KERN_SUCCESS;
660 }
661 if((object->shadow ==
662 resident->object) &&
663 ((resident->offset
664 + object->shadow_offset)
665 == (offset & TWS_HASH_OFF_MASK))) {
666 /* if we just shadowed, inherit */
667 /* access pattern from parent */
668 startup_cache_line |=
669 resident->page_cache;
670 /* thow out old entry */
671 resident->page_cache = 0;
672 break;
673 } else {
674 resident->page_cache &=
675 ~(1<<(((vm_offset_t)(page_addr
676 - resident->page_addr))
677 >>12));
678 }
679 /* Throw out old entry if there are no */
680 /* more pages in cache */
681 if(resident->page_cache == 0) {
682 /* delete addr hash entry */
683 cache_ele->element = 0;
684 *trailer = cache_ele->next;
685 cache_ele->next = *free_list;
686 *free_list = cache_ele;
687 /* go after object hash */
688 index = do_tws_hash(
689 resident->object,
690 resident->offset,
691 tws->number_of_elements,
692 tws->number_of_lines);
693 tws_traverse_object_hash_list(tws,
694 index, resident->object,
695 resident->offset,
696 0xFFFFFFFF, &cache_ele,
697 &trailer, &free_list);
698 if(cache_ele != NULL) {
699 if(tws->style ==
700 TWS_HASH_STYLE_SIGNAL) {
701 vm_object_deallocate(
702 cache_ele->element->object);
703 vm_map_deallocate(
704 cache_ele->element->map);
705 }
706 current_line =
707 cache_ele->element->line;
708 set = current_line
709 /tws->number_of_lines;
710 current_line -= set *
711 tws->number_of_lines;
712 if(cache_ele->element->object != 0) {
713 cache_ele->element->object = 0;
714 tws->cache[set]
715 [current_line].ele_count--;
716 }
717 cache_ele->element = 0;
718 *trailer = cache_ele->next;
719 cache_ele->next = *free_list;
720 *free_list = cache_ele;
721 }
722 }
723 continue;
724 }
725 ctr+=1;
726 }
727
728 /*
729 * We may or may not have a current line setting coming out of
730 * the code above. If we have a current line it means we can
731 * choose to back-fill the spot vacated by a previous entry.
732 * We have yet to do a definitive check using the original obj/off
733 * We will do that now and override the current line if we
734 * find an element
735 */
736
737 index = do_tws_hash(object, offset,
738 tws->number_of_elements, tws->number_of_lines);
739
740 alt_index = index_enum[0];
741
742 tws_traverse_object_hash_list(tws, index, object, offset,
743 0xFFFFFFFF, &cache_ele, &trailer, &free_list);
744 if(cache_ele != NULL) {
745 obj_ele = cache_ele;
746 current_line = cache_ele->element->line;
747 set = current_line/tws->number_of_lines;
748 current_line -= set * tws->number_of_lines;
749 target_element = cache_ele->element;
750
751 /* Now check to see if we have a hash addr for it */
752 tws_traverse_address_hash_list(tws,
753 alt_index, obj_ele->element->page_addr,
754 obj_ele->element->object,
755 obj_ele->element->offset,
756 obj_ele->element->map,
757 &cache_ele, &trailer, &free_list, 0);
758 if(cache_ele != NULL) {
759 addr_ele = cache_ele;
760 } else {
761 addr_ele = new_addr_hash(tws, set, alt_index);
762 /* if cannot allocate just do without */
763 /* we'll get it next time around */
764 }
765 }
766
767
768
769 if(tws->style == TWS_HASH_STYLE_SIGNAL) {
770 vm_object_reference(object);
771 vm_map_reference(map);
772 }
773
774 if(current_line == 0xFFFFFFFF) {
775 current_line = tws->current_line;
776 set = current_line/tws->number_of_lines;
777 current_line = current_line - (set * tws->number_of_lines);
778
779 #ifdef notdef
780 if(cache_full) {
781 tws->current_line = tws->number_of_lines - 1;
782 }
783 #endif
784 if(tws->cache[set][current_line].ele_count
785 >= tws->number_of_elements) {
786 current_line++;
787 tws->current_line++;
788 if(current_line == tws->number_of_lines) {
789 set++;
790 current_line = 0;
791 if (set == tws->expansion_count) {
792 if((tws->lookup_count <
793 (2 * tws->insert_count)) &&
794 (set<TWS_HASH_EXPANSION_MAX)) {
795 tws->lookup_count = 0;
796 tws->insert_count = 0;
797 if(tws->number_of_lines
798 < TWS_HASH_LINE_COUNT) {
799 tws->current_line--;
800 tws_unlock(tws);
801 return KERN_NO_SPACE;
802 }
803 /* object persistence is guaranteed by */
804 /* an elevated paging or object */
805 /* reference count in the caller. */
806 vm_object_unlock(object);
807 if((tws->table[set] = (tws_hash_ptr_t *)
808 kalloc(sizeof(tws_hash_ptr_t)
809 * tws->number_of_lines
810 * tws->number_of_elements))
811 == NULL) {
812 set = 0;
813 } else if((tws->table_ele[set] =
814 (tws_hash_ptr_t)
815 kalloc(sizeof(struct tws_hash_ptr)
816 * tws->number_of_lines
817 * tws->number_of_elements))
818 == NULL) {
819 kfree(tws->table[set],
820 sizeof(tws_hash_ptr_t)
821 * tws->number_of_lines
822 * tws->number_of_elements);
823 set = 0;
824 } else if((tws->alt_ele[set] =
825 (tws_hash_ptr_t)
826 kalloc(sizeof(struct tws_hash_ptr)
827 * tws->number_of_lines
828 * tws->number_of_elements))
829 == NULL) {
830 kfree(tws->table_ele[set],
831 sizeof(struct tws_hash_ptr)
832 * tws->number_of_lines
833 * tws->number_of_elements);
834 kfree(tws->table[set],
835 sizeof(tws_hash_ptr_t)
836 * tws->number_of_lines
837 * tws->number_of_elements);
838 tws->table[set] = NULL;
839 set = 0;
840
841 } else if((tws->cache[set] =
842 (struct tws_hash_line *)
843 kalloc(sizeof
844 (struct tws_hash_line)
845 * tws->number_of_lines))
846 == NULL) {
847 kfree(tws->alt_ele[set],
848 sizeof(struct tws_hash_ptr)
849 * tws->number_of_lines
850 * tws->number_of_elements);
851 kfree(tws->table_ele[set],
852 sizeof(struct tws_hash_ptr)
853 * tws->number_of_lines
854 * tws->number_of_elements);
855 kfree(tws->table[set],
856 sizeof(tws_hash_ptr_t)
857 * tws->number_of_lines
858 * tws->number_of_elements);
859 tws->table[set] = NULL;
860 set = 0;
861
862 } else {
863 tws->free_hash_ele[set] =
864 (tws_hash_ptr_t)0;
865 tws->obj_free_count[set] = 0;
866 tws->addr_free_count[set] = 0;
867 bzero((char *)tws->table[set],
868 sizeof(tws_hash_ptr_t)
869 * tws->number_of_lines
870 * tws->number_of_elements);
871 bzero((char *)tws->table_ele[set],
872 sizeof(struct tws_hash_ptr)
873 * tws->number_of_lines
874 * tws->number_of_elements);
875 bzero((char *)tws->alt_ele[set],
876 sizeof(struct tws_hash_ptr)
877 * tws->number_of_lines
878 * tws->number_of_elements);
879 bzero((char *)tws->cache[set],
880 sizeof(struct tws_hash_line)
881 * tws->number_of_lines);
882 }
883 vm_object_lock(object);
884 } else {
885 if (tws->startup_name != NULL) {
886 tws->current_line--;
887
888 age_of_cache = ((sched_tick - tws->time_of_creation) >> SCHED_TICK_SHIFT);
889
890 tws_unlock(tws);
891
892 if (age_of_cache > 45)
893 return KERN_OPERATION_TIMED_OUT;
894
895 return KERN_FAILURE;
896 }
897 tws->lookup_count = 0;
898 tws->insert_count = 0;
899 set = 0;
900 }
901 }
902 tws->current_line = set * tws->number_of_lines;
903 }
904 if(set < tws->expansion_count) {
905 tws_hash_line_clear(tws,
906 &(tws->cache[set][current_line]), object, TRUE);
907 if(tws->cache[set][current_line].ele_count
908 >= tws->number_of_elements) {
909 if(tws->style == TWS_HASH_STYLE_SIGNAL) {
910 vm_object_deallocate(object);
911 vm_map_deallocate(map);
912 }
913 tws_unlock(tws);
914 return KERN_FAILURE;
915 }
916 } else {
917 tws->expansion_count++;
918 }
919 }
920 }
921
922
923 /* set object hash element */
924 if(obj_ele == NULL) {
925 obj_ele = new_obj_hash(tws, set, index);
926 if(obj_ele == NULL) {
927 tws->cache[set][current_line].ele_count
928 = tws->number_of_elements;
929 tws_unlock(tws);
930 return KERN_FAILURE;
931 }
932 }
933
934 /* set address hash element */
935 if(addr_ele == NULL) {
936 addr_ele = new_addr_hash(tws, set, alt_index);
937 }
938
939 if(target_element == NULL) {
940 ele_index = 0;
941 for(i = 0; i<tws->number_of_elements; i++) {
942 if(tws->cache[set][current_line].
943 list[ele_index].object == 0) {
944 break;
945 }
946 ele_index++;
947 if(ele_index >= tws->number_of_elements)
948 ele_index = 0;
949
950 }
951
952 if(i == tws->number_of_elements)
953 panic("tws_insert: no free elements");
954
955 target_element =
956 &(tws->cache[set][current_line].list[ele_index]);
957
958 tws->cache[set][current_line].ele_count++;
959 }
960
961 obj_ele->element = target_element;
962 if(addr_ele) {
963 addr_ele->element = (tws_hash_ele_t)
964 (((unsigned int)target_element) | TWS_ADDR_HASH);
965 }
966 target_element->object = object;
967 target_element->offset = offset & TWS_HASH_OFF_MASK;
968 target_element->page_addr =
969 page_addr - (offset - (offset & TWS_HASH_OFF_MASK));
970 target_element->map = map;
971 target_element->line =
972 current_line + (set * tws->number_of_lines);
973
974 target_element->page_cache |= startup_cache_line;
975 target_element->page_cache |= 1<<(((vm_offset_t)(offset & TWS_INDEX_MASK))>>12);
976
977 tws_unlock(tws);
978
979 if (age_of_cache > 45)
980 return KERN_OPERATION_TIMED_OUT;
981
982 return KERN_SUCCESS;
983 }
984
985 /*
986 * tws_build_cluster
987 * lengthen the cluster of pages by the number of pages encountered in the
988 * working set up to the limit requested by the caller. The object needs
989 * to be locked on entry. The map does not because the tws_lookup function
990 * is used only to find if their is an entry in the cache. No transient
991 * data from the cache is de-referenced.
992 *
993 */
994 #if MACH_PAGEMAP
995 /*
996 * MACH page map - an optional optimization where a bit map is maintained
997 * by the VM subsystem for internal objects to indicate which pages of
998 * the object currently reside on backing store. This existence map
999 * duplicates information maintained by the vnode pager. It is
1000 * created at the time of the first pageout against the object, i.e.
1001 * at the same time pager for the object is created. The optimization
1002 * is designed to eliminate pager interaction overhead, if it is
1003 * 'known' that the page does not exist on backing store.
1004 *
1005 * LOOK_FOR() evaluates to TRUE if the page specified by object/offset is
1006 * either marked as paged out in the existence map for the object or no
1007 * existence map exists for the object. LOOK_FOR() is one of the
1008 * criteria in the decision to invoke the pager. It is also used as one
1009 * of the criteria to terminate the scan for adjacent pages in a clustered
1010 * pagein operation. Note that LOOK_FOR() always evaluates to TRUE for
1011 * permanent objects. Note also that if the pager for an internal object
1012 * has not been created, the pager is not invoked regardless of the value
1013 * of LOOK_FOR() and that clustered pagein scans are only done on an object
1014 * for which a pager has been created.
1015 *
1016 * PAGED_OUT() evaluates to TRUE if the page specified by the object/offset
1017 * is marked as paged out in the existence map for the object. PAGED_OUT()
1018 * PAGED_OUT() is used to determine if a page has already been pushed
1019 * into a copy object in order to avoid a redundant page out operation.
1020 */
1021 #define LOOK_FOR(o, f) (vm_external_state_get((o)->existence_map, (f)) \
1022 != VM_EXTERNAL_STATE_ABSENT)
1023 #define PAGED_OUT(o, f) (vm_external_state_get((o)->existence_map, (f)) \
1024 == VM_EXTERNAL_STATE_EXISTS)
1025 #else /* MACH_PAGEMAP */
1026 /*
1027 * If the MACH page map optimization is not enabled,
1028 * LOOK_FOR() always evaluates to TRUE. The pager will always be
1029 * invoked to resolve missing pages in an object, assuming the pager
1030 * has been created for the object. In a clustered page operation, the
1031 * absence of a page on backing backing store cannot be used to terminate
1032 * a scan for adjacent pages since that information is available only in
1033 * the pager. Hence pages that may not be paged out are potentially
1034 * included in a clustered request. The vnode pager is coded to deal
1035 * with any combination of absent/present pages in a clustered
1036 * pagein request. PAGED_OUT() always evaluates to FALSE, i.e. the pager
1037 * will always be invoked to push a dirty page into a copy object assuming
1038 * a pager has been created. If the page has already been pushed, the
1039 * pager will ingore the new request.
1040 */
1041 #define LOOK_FOR(o, f) TRUE
1042 #define PAGED_OUT(o, f) FALSE
1043 #endif /* MACH_PAGEMAP */
1044
1045
1046 void
1047 tws_build_cluster(
1048 tws_hash_t tws,
1049 vm_object_t object,
1050 vm_object_offset_t *start,
1051 vm_object_offset_t *end,
1052 vm_size_t max_length)
1053 {
1054 tws_hash_line_t line;
1055 vm_object_offset_t before = *start;
1056 vm_object_offset_t after = *end;
1057 vm_object_offset_t original_start = *start;
1058 vm_object_offset_t original_end = *end;
1059 vm_size_t length = (vm_size_t)(*end - *start);
1060 vm_page_t m;
1061 kern_return_t kret;
1062 vm_object_offset_t object_size;
1063 int age_of_cache;
1064 vm_size_t pre_heat_size;
1065 unsigned int ele_cache;
1066 unsigned int end_cache = 0;
1067 unsigned int start_cache = 0;
1068 unsigned int memory_scarce = 0;
1069
1070 if((object->private) || !(object->pager))
1071 return;
1072
1073 if (!object->internal) {
1074 kret = vnode_pager_get_object_size(
1075 object->pager,
1076 &object_size);
1077 } else {
1078 object_size = object->size;
1079 }
1080
1081 if((!tws) || (!tws_lock_try(tws))) {
1082 return;
1083 }
1084 age_of_cache = ((sched_tick
1085 - tws->time_of_creation) >> SCHED_TICK_SHIFT);
1086
1087 if (vm_page_free_count < (2 * vm_page_free_target))
1088 memory_scarce = 1;
1089
1090 /* When pre-heat files are not available, resort to speculation */
1091 /* based on size of file */
1092
1093 if (tws->startup_cache || object->internal || age_of_cache > 45) {
1094 pre_heat_size = 0;
1095 } else {
1096 if (object_size > (vm_object_offset_t)(1024 * 1024))
1097 pre_heat_size = 8 * PAGE_SIZE;
1098 else if (object_size > (vm_object_offset_t)(128 * 1024))
1099 pre_heat_size = 4 * PAGE_SIZE;
1100 else
1101 pre_heat_size = 2 * PAGE_SIZE;
1102 }
1103
1104 if (tws->startup_cache) {
1105 int target_page_count;
1106
1107 if (memory_scarce)
1108 target_page_count = 16;
1109 else
1110 target_page_count = 4;
1111
1112 if (tws_test_for_community(tws, object, *start, target_page_count, &ele_cache))
1113 {
1114 start_cache = ele_cache;
1115 *start = *start & TWS_HASH_OFF_MASK;
1116 *end = *start + (32 * PAGE_SIZE_64);
1117
1118 if (*end > object_size) {
1119 *end = round_page_64(object_size);
1120 max_length = 0;
1121 } else
1122 end_cache = ele_cache;
1123
1124 while (max_length > ((*end - *start) + (32 * PAGE_SIZE))) {
1125 int expanded;
1126
1127 expanded = 0;
1128 after = *end;
1129
1130 if ((after + (32 * PAGE_SIZE_64)) <= object_size &&
1131 (tws_test_for_community(tws, object, after, 8, &ele_cache))) {
1132
1133 *end = after + (32 * PAGE_SIZE_64);
1134 end_cache = ele_cache;
1135 expanded = 1;
1136 }
1137 if (max_length < ((*end - *start) + (32 * PAGE_SIZE_64))) {
1138 break;
1139 }
1140 if (*start) {
1141 before = (*start - PAGE_SIZE_64) & TWS_HASH_OFF_MASK;
1142
1143 if (tws_test_for_community(tws, object, before, 8, &ele_cache)) {
1144
1145 *start = before;
1146 start_cache = ele_cache;
1147 expanded = 1;
1148 }
1149 }
1150 if (expanded == 0)
1151 break;
1152 }
1153 if (end_cache)
1154 *end -= PAGE_SIZE_64;
1155
1156 if (start_cache != 0) {
1157 unsigned int mask;
1158
1159 for (mask = 1; mask != 0; mask = mask << 1) {
1160 if (*start == original_start)
1161 break;
1162 if (!(start_cache & mask))
1163 *start += PAGE_SIZE_64;
1164 else
1165 break;
1166 }
1167 }
1168 if (end_cache != 0) {
1169 unsigned int mask;
1170
1171 for (mask = 0x80000000;
1172 mask != 0; mask = mask >> 1) {
1173 if (*end == original_end)
1174 break;
1175 if (!(end_cache & mask))
1176 *end -= PAGE_SIZE_64;
1177 else
1178 break;
1179 }
1180 }
1181 tws_unlock(tws);
1182
1183 if (*end < original_end)
1184 *end = original_end;
1185 return;
1186 }
1187 }
1188
1189 while ((length < max_length) &&
1190 (object_size >=
1191 (after + PAGE_SIZE_64))) {
1192 if(length >= pre_heat_size) {
1193 if(tws_internal_lookup(tws, after, object,
1194 &line) != KERN_SUCCESS) {
1195 vm_object_offset_t extend;
1196
1197 extend = after + PAGE_SIZE_64;
1198 if(tws_internal_lookup(tws, extend, object,
1199 &line) != KERN_SUCCESS) {
1200 break;
1201 }
1202 }
1203 }
1204
1205 if ((object->existence_map != NULL)
1206 && (!LOOK_FOR(object, after))) {
1207 break;
1208 }
1209
1210 if (vm_page_lookup(object, after) != VM_PAGE_NULL) {
1211 /*
1212 * don't bridge resident pages
1213 */
1214 break;
1215 }
1216
1217 if (object->internal) {
1218 /*
1219 * need to acquire a real page in
1220 * advance because this acts as
1221 * a throttling mechanism for
1222 * data_requests to the default
1223 * pager. If this fails, give up
1224 * trying to find any more pages
1225 * in the cluster and send off the
1226 * request for what we already have.
1227 */
1228 if ((m = vm_page_grab()) == VM_PAGE_NULL) {
1229 break;
1230 }
1231 } else if ((m = vm_page_grab_fictitious())
1232 == VM_PAGE_NULL) {
1233 break;
1234 }
1235 m->absent = TRUE;
1236 m->unusual = TRUE;
1237 m->clustered = TRUE;
1238 m->list_req_pending = TRUE;
1239
1240 vm_page_insert(m, object, after);
1241 object->absent_count++;
1242 after += PAGE_SIZE_64;
1243 length += PAGE_SIZE;
1244 }
1245 *end = after;
1246 while (length < max_length) {
1247 if (before == 0)
1248 break;
1249 before -= PAGE_SIZE_64;
1250
1251 if(length >= pre_heat_size) {
1252 if(tws_internal_lookup(tws, before, object,
1253 &line) != KERN_SUCCESS) {
1254 vm_object_offset_t extend;
1255
1256 extend = before;
1257 if (extend == 0)
1258 break;
1259 extend -= PAGE_SIZE_64;
1260 if(tws_internal_lookup(tws, extend, object,
1261 &line) != KERN_SUCCESS) {
1262 break;
1263 }
1264 }
1265 }
1266 if ((object->existence_map != NULL)
1267 && (!LOOK_FOR(object, before))) {
1268 break;
1269 }
1270
1271 if (vm_page_lookup(object, before) != VM_PAGE_NULL) {
1272 /*
1273 * don't bridge resident pages
1274 */
1275 break;
1276 }
1277
1278 if (object->internal) {
1279 /*
1280 * need to acquire a real page in
1281 * advance because this acts as
1282 * a throttling mechanism for
1283 * data_requests to the default
1284 * pager. If this fails, give up
1285 * trying to find any more pages
1286 * in the cluster and send off the
1287 * request for what we already have.
1288 */
1289 if ((m = vm_page_grab()) == VM_PAGE_NULL) {
1290 break;
1291 }
1292 } else if ((m = vm_page_grab_fictitious())
1293 == VM_PAGE_NULL) {
1294 break;
1295 }
1296 m->absent = TRUE;
1297 m->unusual = TRUE;
1298 m->clustered = TRUE;
1299 m->list_req_pending = TRUE;
1300
1301 vm_page_insert(m, object, before);
1302 object->absent_count++;
1303 *start -= PAGE_SIZE_64;
1304 length += PAGE_SIZE;
1305 }
1306 tws_unlock(tws);
1307 }
1308
1309 void
1310 tws_line_signal(
1311 tws_hash_t tws,
1312 vm_map_t map,
1313 tws_hash_line_t hash_line,
1314 vm_offset_t target_page)
1315 {
1316 unsigned int i,j;
1317 vm_object_t object;
1318 vm_object_offset_t offset;
1319 vm_object_offset_t before;
1320 vm_object_offset_t after;
1321 struct tws_hash_ele *element;
1322 vm_page_t m,p;
1323 kern_return_t rc;
1324
1325 if(tws->style != TWS_HASH_STYLE_SIGNAL)
1326 return;
1327
1328 vm_map_lock(map);
1329 for (i=0; i<tws->number_of_elements; i++) {
1330
1331 vm_object_offset_t local_off = 0;
1332
1333 if(hash_line->list[i].object == 0)
1334 continue;
1335
1336 element = &hash_line->list[i];
1337
1338 if (element->page_addr == target_page)
1339 continue;
1340
1341 j = 1;
1342 while (j != 0) {
1343 if(j & element->page_cache)
1344 break;
1345 j <<= 1;
1346 local_off += PAGE_SIZE_64;
1347 }
1348 object = element->object;
1349 offset = element->offset + local_off;
1350
1351 /* first try a fast test to speed up no-op signal */
1352 if (((p = vm_page_lookup(object, offset)) != NULL)
1353 || (object->pager == NULL)
1354 || (object->shadow_severed)) {
1355 continue;
1356 }
1357
1358 if((!object->alive) ||
1359 (!object->pager_created) || (!object->pager_ready))
1360 continue;
1361
1362 if (object->internal) {
1363 if (object->existence_map == NULL) {
1364 if (object->shadow)
1365 continue;
1366 } else {
1367 if(!LOOK_FOR(object, offset))
1368 continue;
1369 }
1370 }
1371
1372 vm_object_reference(object);
1373 vm_map_unlock(map);
1374
1375 if(object->internal) {
1376 m = vm_page_grab();
1377 } else {
1378 m = vm_page_grab_fictitious();
1379 }
1380
1381 if(m == NULL) {
1382 vm_object_deallocate(object);
1383 vm_map_lock(map);
1384 continue;
1385 }
1386
1387 vm_object_lock(object);
1388 if (((p = vm_page_lookup(object, offset)) != NULL)
1389 || (object->pager == NULL)
1390 || (object->shadow_severed)) {
1391 VM_PAGE_FREE(m);
1392 vm_object_unlock(object);
1393 vm_object_deallocate(object);
1394 vm_map_lock(map);
1395 continue;
1396 }
1397
1398 vm_page_insert(m, object, offset);
1399
1400 if (object->absent_count > vm_object_absent_max) {
1401 VM_PAGE_FREE(m);
1402 vm_object_unlock(object);
1403 vm_object_deallocate(object);
1404 vm_map_lock(map);
1405 break;
1406 }
1407 m->list_req_pending = TRUE;
1408 m->absent = TRUE;
1409 m->unusual = TRUE;
1410 object->absent_count++;
1411
1412 before = offset;
1413 after = offset + PAGE_SIZE_64;
1414 tws_build_cluster(tws, object, &before, &after, 0x16000);
1415 vm_object_unlock(object);
1416
1417 rc = memory_object_data_request(object->pager,
1418 before + object->paging_offset,
1419 (vm_size_t)(after - before), VM_PROT_READ);
1420 if (rc != KERN_SUCCESS) {
1421 offset = before;
1422 vm_object_lock(object);
1423 while (offset < after) {
1424 m = vm_page_lookup(object, offset);
1425 if(m && m->absent && m->busy)
1426 VM_PAGE_FREE(m);
1427 offset += PAGE_SIZE;
1428 }
1429 vm_object_unlock(object);
1430 vm_object_deallocate(object);
1431 } else {
1432 vm_object_deallocate(object);
1433 }
1434 vm_map_lock(map);
1435 continue;
1436 }
1437 vm_map_unlock(map);
1438 }
1439
1440 /* tws locked on entry */
1441
1442 tws_startup_t
1443 tws_create_startup_list(
1444 tws_hash_t tws)
1445 {
1446
1447 tws_startup_t startup;
1448 unsigned int i,j,k;
1449 unsigned int total_elements;
1450 unsigned int startup_size;
1451 unsigned int sindex;
1452 unsigned int hash_index;
1453 tws_startup_ptr_t element;
1454
1455 total_elements = tws->expansion_count *
1456 (tws->number_of_lines * tws->number_of_elements);
1457
1458 startup_size = sizeof(struct tws_startup)
1459 + (total_elements * sizeof(tws_startup_ptr_t *))
1460 + (total_elements * sizeof(struct tws_startup_ptr))
1461 + (total_elements * sizeof(struct tws_startup_ele));
1462 startup = (tws_startup_t)(kalloc(startup_size));
1463
1464 if(startup == NULL)
1465 return startup;
1466
1467 bzero((char *) startup, startup_size);
1468
1469 startup->table = (tws_startup_ptr_t *)
1470 (((int)startup) + (sizeof(struct tws_startup)));
1471 startup->ele = (struct tws_startup_ptr *)
1472 (((vm_offset_t)startup->table) +
1473 (total_elements * sizeof(tws_startup_ptr_t)));
1474
1475 startup->array = (struct tws_startup_ele *)
1476 (((vm_offset_t)startup->ele) +
1477 (total_elements * sizeof(struct tws_startup_ptr)));
1478
1479 startup->tws_hash_size = startup_size;
1480 startup->ele_count = 0; /* burn first hash ele, else we can't tell from zero */
1481 startup->array_size = total_elements;
1482 startup->hash_count = 1;
1483
1484 sindex = 0;
1485
1486
1487 for(i = 0; i<tws->number_of_lines; i++) {
1488 for(j = 0; j<tws->number_of_elements; j++) {
1489 for(k = 0; k<tws->expansion_count; k++) {
1490 tws_hash_ele_t entry;
1491 unsigned int hash_retry;
1492 vm_offset_t addr;
1493
1494 entry = &tws->cache[k][i].list[j];
1495 addr = entry->page_addr;
1496 hash_retry = 0;
1497 if(entry->object != 0) {
1498 /* get a hash element */
1499 hash_index = do_startup_hash(addr,
1500 startup->array_size);
1501
1502 if(startup->hash_count < total_elements) {
1503 element = &(startup->ele[startup->hash_count]);
1504 startup->hash_count += 1;
1505 } else {
1506 /* exit we're out of elements */
1507 break;
1508 }
1509 /* place the hash element */
1510 element->next = startup->table[hash_index];
1511 startup->table[hash_index] = (tws_startup_ptr_t)
1512 ((int)element - (int)&startup->ele[0]);
1513
1514 /* set entry OFFSET in hash element */
1515 element->element = (tws_startup_ele_t)
1516 ((int)&startup->array[sindex] -
1517 (int)&startup->array[0]);
1518
1519 startup->array[sindex].page_addr = entry->page_addr;
1520 startup->array[sindex].page_cache = entry->page_cache;
1521 startup->ele_count++;
1522 sindex++;
1523
1524 }
1525 }
1526 }
1527 }
1528
1529 return startup;
1530 }
1531
1532
1533 /*
1534 * Returns an entire cache line. The line is deleted from the startup
1535 * cache on return. The caller can check startup->ele_count for an empty
1536 * list. Access synchronization is the responsibility of the caller.
1537 */
1538
1539 unsigned int
1540 tws_startup_list_lookup(
1541 tws_startup_t startup,
1542 vm_offset_t addr)
1543 {
1544 unsigned int hash_index;
1545 unsigned int page_cache_bits;
1546 unsigned int startup_shift;
1547 tws_startup_ele_t entry;
1548 vm_offset_t next_addr;
1549 tws_startup_ptr_t element;
1550 tws_startup_ptr_t base_ele;
1551 tws_startup_ptr_t *previous_ptr;
1552
1553 page_cache_bits = 0;
1554
1555 hash_index = do_startup_hash(addr, startup->array_size);
1556
1557 if(((unsigned int)&(startup->table[hash_index])) >= ((unsigned int)startup + startup->tws_hash_size)) {
1558 return page_cache_bits = 0;
1559 }
1560 element = (tws_startup_ptr_t)((int)startup->table[hash_index] +
1561 (int)&startup->ele[0]);
1562 base_ele = element;
1563 previous_ptr = &(startup->table[hash_index]);
1564 while(element > &startup->ele[0]) {
1565 if (((int)element + sizeof(struct tws_startup_ptr))
1566 > ((int)startup + startup->tws_hash_size)) {
1567 return page_cache_bits;
1568 }
1569 entry = (tws_startup_ele_t)
1570 ((int)element->element
1571 + (int)&startup->array[0]);
1572 if((((int)entry + sizeof(struct tws_startup_ele))
1573 > ((int)startup + startup->tws_hash_size))
1574 || ((int)entry < (int)startup)) {
1575 return page_cache_bits;
1576 }
1577 if ((addr >= entry->page_addr) &&
1578 (addr <= (entry->page_addr + 0x1F000))) {
1579 startup_shift = (addr - entry->page_addr)>>12;
1580 page_cache_bits |= entry->page_cache >> startup_shift;
1581 /* don't dump the pages, unless the addresses */
1582 /* line up perfectly. The cache may be used */
1583 /* by other mappings */
1584 entry->page_cache &= (1 << startup_shift) - 1;
1585 if(addr == entry->page_addr) {
1586 if(base_ele == element) {
1587 base_ele = (tws_startup_ptr_t)
1588 ((int)element->next
1589 + (int)&startup->ele[0]);
1590 startup->table[hash_index] = element->next;
1591 element = base_ele;
1592 } else {
1593 *previous_ptr = element->next;
1594 element = (tws_startup_ptr_t)
1595 ((int)*previous_ptr
1596 + (int)&startup->ele[0]);
1597 }
1598 entry->page_addr = 0;
1599 startup->ele_count--;
1600 continue;
1601 }
1602 }
1603 next_addr = addr + 0x1F000;
1604 if ((next_addr >= entry->page_addr) &&
1605 (next_addr <= (entry->page_addr + 0x1F000))) {
1606 startup_shift = (next_addr - entry->page_addr)>>12;
1607 page_cache_bits |= entry->page_cache << (0x1F - startup_shift);
1608 entry->page_cache &= ~((1 << (startup_shift + 1)) - 1);
1609 if(entry->page_cache == 0) {
1610 if(base_ele == element) {
1611 base_ele = (tws_startup_ptr_t)
1612 ((int)element->next
1613 + (int)&startup->ele[0]);
1614 startup->table[hash_index] = element->next;
1615 element = base_ele;
1616 } else {
1617 *previous_ptr = element->next;
1618 element = (tws_startup_ptr_t)
1619 ((int)*previous_ptr
1620 + (int)&startup->ele[0]);
1621 }
1622 entry->page_addr = 0;
1623 startup->ele_count--;
1624 continue;
1625 }
1626 }
1627 previous_ptr = &(element->next);
1628 element = (tws_startup_ptr_t)
1629 ((int) element->next + (int) &startup->ele[0]);
1630 }
1631
1632 return page_cache_bits;
1633 }
1634
1635 kern_return_t
1636 tws_send_startup_info(
1637 task_t task)
1638 {
1639
1640 tws_hash_t tws;
1641
1642 task_lock(task);
1643 tws = task->dynamic_working_set;
1644 task_unlock(task);
1645 if(tws == NULL) {
1646 return KERN_FAILURE;
1647 }
1648 return tws_internal_startup_send(tws);
1649 }
1650
1651
1652 kern_return_t
1653 tws_internal_startup_send(
1654 tws_hash_t tws)
1655 {
1656
1657 tws_startup_t scache;
1658
1659 if(tws == NULL) {
1660 return KERN_FAILURE;
1661 }
1662 tws_lock(tws);
1663 /* used to signal write or release depending on state of tws */
1664 if(tws->startup_cache) {
1665 vm_offset_t startup_buf;
1666 vm_size_t size;
1667 startup_buf = (vm_offset_t)tws->startup_cache;
1668 size = tws->startup_cache->tws_hash_size;
1669 tws->startup_cache = 0;
1670 tws_unlock(tws);
1671 kmem_free(kernel_map, startup_buf, size);
1672 return KERN_SUCCESS;
1673 }
1674 if(tws->startup_name == NULL) {
1675 tws_unlock(tws);
1676 return KERN_FAILURE;
1677 }
1678 scache = tws_create_startup_list(tws);
1679 if(scache == NULL)
1680 return KERN_FAILURE;
1681 bsd_write_page_cache_file(tws->uid, tws->startup_name,
1682 (caddr_t) scache, scache->tws_hash_size,
1683 tws->mod, tws->fid);
1684 kfree(scache, scache->tws_hash_size);
1685 kfree(tws->startup_name, tws->startup_name_length);
1686 tws->startup_name = NULL;
1687 tws_unlock(tws);
1688 return KERN_SUCCESS;
1689 }
1690
1691 kern_return_t
1692 tws_handle_startup_file(
1693 task_t task,
1694 unsigned int uid,
1695 char *app_name,
1696 void *app_vp,
1697 boolean_t *new_info)
1698
1699 {
1700 tws_startup_t startup;
1701 vm_offset_t cache_size;
1702 kern_return_t error;
1703 int fid;
1704 int mod;
1705
1706 *new_info = FALSE;
1707 /* don't pre-heat kernel task */
1708 if(task == kernel_task)
1709 return KERN_SUCCESS;
1710 error = bsd_read_page_cache_file(uid, &fid,
1711 &mod, app_name,
1712 app_vp,
1713 (vm_offset_t *) &startup,
1714 &cache_size);
1715 if(error) {
1716 return KERN_FAILURE;
1717 }
1718 if(startup == NULL) {
1719 /* Entry for app does not exist, make */
1720 /* one */
1721 /* we will want our own copy of the shared */
1722 /* regions to pick up a true picture of all */
1723 /* the pages we will touch. */
1724 if((lsf_zone->count * lsf_zone->elem_size)
1725 > (lsf_zone->max_size >> 1)) {
1726 /* We don't want to run out of shared memory */
1727 /* map entries by starting too many private versions */
1728 /* of the shared library structures */
1729 return KERN_SUCCESS;
1730 }
1731 *new_info = TRUE;
1732
1733 error = tws_write_startup_file(task,
1734 fid, mod, app_name, uid);
1735 if(error)
1736 return error;
1737
1738 } else {
1739 error = tws_read_startup_file(task,
1740 (tws_startup_t)startup,
1741 cache_size);
1742 if(error) {
1743 kmem_free(kernel_map,
1744 (vm_offset_t)startup, cache_size);
1745 return error;
1746 }
1747 }
1748 return KERN_SUCCESS;
1749 }
1750
1751 kern_return_t
1752 tws_write_startup_file(
1753 task_t task,
1754 int fid,
1755 int mod,
1756 char *name,
1757 unsigned int uid)
1758 {
1759 tws_hash_t tws;
1760 unsigned int string_length;
1761
1762 string_length = strlen(name);
1763
1764 restart:
1765 task_lock(task);
1766 tws = task->dynamic_working_set;
1767 task_unlock(task);
1768
1769 if(tws == NULL) {
1770 kern_return_t error;
1771
1772 /* create a dynamic working set of normal size */
1773 if((error = task_working_set_create(task, 0, 0, TWS_HASH_STYLE_DEFAULT)) != KERN_SUCCESS)
1774 return error;
1775 /* we need to reset tws and relock */
1776 goto restart;
1777 }
1778 tws_lock(tws);
1779
1780 if(tws->startup_name != NULL) {
1781 tws_unlock(tws);
1782 return KERN_FAILURE;
1783 }
1784
1785 tws->startup_name = (char *)
1786 kalloc((string_length + 1) * (sizeof(char)));
1787 if(tws->startup_name == NULL) {
1788 tws_unlock(tws);
1789 return KERN_FAILURE;
1790 }
1791
1792 bcopy(name, (char *)tws->startup_name, string_length + 1);
1793 tws->startup_name_length = (string_length + 1) * sizeof(char);
1794 tws->uid = uid;
1795 tws->fid = fid;
1796 tws->mod = mod;
1797
1798 tws_unlock(tws);
1799 return KERN_SUCCESS;
1800 }
1801
1802 unsigned long tws_read_startup_file_rejects = 0;
1803
1804 kern_return_t
1805 tws_read_startup_file(
1806 task_t task,
1807 tws_startup_t startup,
1808 vm_offset_t cache_size)
1809 {
1810 tws_hash_t tws;
1811 int lines;
1812 int old_exp_count;
1813 unsigned int ele_count;
1814
1815 restart:
1816 task_lock(task);
1817 tws = task->dynamic_working_set;
1818
1819 /* create a dynamic working set to match file size */
1820
1821 /* start with total size of the data we got from app_profile */
1822 ele_count = cache_size;
1823 /* skip the startup header */
1824 ele_count -= sizeof(struct tws_startup);
1825 /*
1826 * For each startup cache entry, we have one of these:
1827 * tws_startup_ptr_t startup->table[];
1828 * struct tws_startup_ptr startup->ele[];
1829 * struct tws_startup_ele startup->array[];
1830 */
1831 ele_count /= (sizeof (tws_startup_ptr_t) +
1832 sizeof (struct tws_startup_ptr) +
1833 sizeof (struct tws_startup_ele));
1834
1835 /*
1836 * Sanity check: make sure the value for startup->array_size
1837 * that we read from the app_profile file matches the size
1838 * of the data we read from disk. If it doesn't match, we
1839 * can't trust the data and we just drop it all.
1840 */
1841 if (cache_size < sizeof(struct tws_startup) ||
1842 startup->array_size != ele_count) {
1843 tws_read_startup_file_rejects++;
1844 task_unlock(task);
1845 kmem_free(kernel_map, (vm_offset_t)startup, cache_size);
1846 return(KERN_SUCCESS);
1847 }
1848
1849 /*
1850 * We'll create the task working set with the default row size
1851 * (TWS_ARRAY_SIZE), so this will give us the number of lines
1852 * we need to store all the data from the app_profile startup
1853 * cache.
1854 */
1855 lines = ele_count / TWS_ARRAY_SIZE;
1856
1857 if(lines <= TWS_SMALL_HASH_LINE_COUNT) {
1858 lines = TWS_SMALL_HASH_LINE_COUNT;
1859 task_unlock(task);
1860 kmem_free(kernel_map, (vm_offset_t)startup, cache_size);
1861 return(KERN_SUCCESS);
1862 } else {
1863 old_exp_count = lines/TWS_HASH_LINE_COUNT;
1864 if((old_exp_count * TWS_HASH_LINE_COUNT) != lines) {
1865 lines = (old_exp_count + 1)
1866 * TWS_HASH_LINE_COUNT;
1867 }
1868 if(tws == NULL) {
1869 kern_return_t error;
1870
1871 task_unlock(task);
1872 if ((error = task_working_set_create(task, lines, 0, TWS_HASH_STYLE_DEFAULT)) != KERN_SUCCESS)
1873 return error;
1874 /* we need to reset tws and relock */
1875 goto restart;
1876 } else {
1877 task_unlock(task);
1878 tws_expand_working_set(
1879 (void *)tws, lines, TRUE);
1880 }
1881 }
1882
1883 tws_lock(tws);
1884
1885 if(tws->startup_cache != NULL) {
1886 tws_unlock(tws);
1887 return KERN_FAILURE;
1888 }
1889
1890
1891 /* now need to fix up internal table pointers */
1892 startup->table = (tws_startup_ptr_t *)
1893 (((int)startup) + (sizeof(struct tws_startup)));
1894 startup->ele = (struct tws_startup_ptr *)
1895 (((vm_offset_t)startup->table) +
1896 (startup->array_size * sizeof(tws_startup_ptr_t)));
1897 startup->array = (struct tws_startup_ele *)
1898 (((vm_offset_t)startup->ele) +
1899 (startup->array_size * sizeof(struct tws_startup_ptr)));
1900 /* the allocation size and file size should be the same */
1901 /* just in case their not, make sure we dealloc correctly */
1902 startup->tws_hash_size = cache_size;
1903
1904 tws->startup_cache = startup;
1905 tws_unlock(tws);
1906 return KERN_SUCCESS;
1907 }
1908
1909
1910 void
1911 tws_hash_ws_flush(tws_hash_t tws) {
1912 tws_startup_t scache;
1913 if(tws == NULL) {
1914 return;
1915 }
1916 tws_lock(tws);
1917 if(tws->startup_name != NULL) {
1918 scache = tws_create_startup_list(tws);
1919 if(scache == NULL) {
1920 /* dump the name cache, we'll */
1921 /* get it next time */
1922 kfree(tws->startup_name, tws->startup_name_length);
1923 tws->startup_name = NULL;
1924 tws_unlock(tws);
1925 return;
1926 }
1927 bsd_write_page_cache_file(tws->uid, tws->startup_name,
1928 (caddr_t) scache, scache->tws_hash_size,
1929 tws->mod, tws->fid);
1930 kfree(scache, scache->tws_hash_size);
1931 kfree(tws->startup_name, tws->startup_name_length);
1932 tws->startup_name = NULL;
1933 }
1934 tws_unlock(tws);
1935 return;
1936 }
1937
1938 void
1939 tws_hash_destroy(tws_hash_t tws)
1940 {
1941 unsigned int i,k;
1942
1943 if(tws->startup_cache != NULL) {
1944 kmem_free(kernel_map,
1945 (vm_offset_t)tws->startup_cache,
1946 tws->startup_cache->tws_hash_size);
1947 tws->startup_cache = NULL;
1948 }
1949 if(tws->startup_name != NULL) {
1950 tws_internal_startup_send(tws);
1951 }
1952 for (i=0; i<tws->number_of_lines; i++) {
1953 for(k=0; k<tws->expansion_count; k++) {
1954 /* clear the object refs */
1955 tws_hash_line_clear(tws, &(tws->cache[k][i]), NULL, FALSE);
1956 }
1957 }
1958 i = 0;
1959 while (i < tws->expansion_count) {
1960
1961 kfree(tws->table[i],
1962 sizeof(tws_hash_ptr_t)
1963 * tws->number_of_lines
1964 * tws->number_of_elements);
1965 kfree(tws->table_ele[i],
1966 sizeof(struct tws_hash_ptr)
1967 * tws->number_of_lines
1968 * tws->number_of_elements);
1969 kfree(tws->alt_ele[i],
1970 sizeof(struct tws_hash_ptr)
1971 * tws->number_of_lines
1972 * tws->number_of_elements);
1973 kfree(tws->cache[i],
1974 sizeof(struct tws_hash_line) * tws->number_of_lines);
1975 i++;
1976 }
1977 if(tws->startup_name != NULL) {
1978 kfree(tws->startup_name, tws->startup_name_length);
1979 }
1980 kfree(tws, sizeof(struct tws_hash));
1981 }
1982
1983 void
1984 tws_hash_clear(tws_hash_t tws)
1985 {
1986 unsigned int i, k;
1987
1988 for (i=0; i<tws->number_of_lines; i++) {
1989 for(k=0; k<tws->expansion_count; k++) {
1990 /* clear the object refs */
1991 tws_hash_line_clear(tws, &(tws->cache[k][i]), NULL, FALSE);
1992 }
1993 }
1994 }
1995
1996 kern_return_t
1997 task_working_set_create(
1998 task_t task,
1999 unsigned int lines,
2000 unsigned int rows,
2001 unsigned int style)
2002 {
2003
2004 if (lines == 0) {
2005 lines = TWS_HASH_LINE_COUNT;
2006 }
2007 if (rows == 0) {
2008 rows = TWS_ARRAY_SIZE;
2009 }
2010 if (style == TWS_HASH_STYLE_DEFAULT) {
2011 style = TWS_HASH_STYLE_BASIC;
2012 }
2013 task_lock(task);
2014 if(task->dynamic_working_set != 0) {
2015 task_unlock(task);
2016 return(KERN_FAILURE);
2017 } else if((task->dynamic_working_set =
2018 tws_hash_create(lines, rows, style)) == 0) {
2019 task_unlock(task);
2020 return(KERN_NO_SPACE);
2021 }
2022 task_unlock(task);
2023 return KERN_SUCCESS;
2024 }
2025
2026
2027 /* Internal use only routines */
2028
2029
2030 /*
2031 * internal sub-function for address space lookup
2032 * returns the target element and the address of the
2033 * previous pointer The previous pointer is the address
2034 * of the pointer pointing to the target element.
2035 * TWS must be locked
2036 */
2037
2038 void
2039 tws_traverse_address_hash_list (
2040 tws_hash_t tws,
2041 unsigned int index,
2042 vm_offset_t page_addr,
2043 vm_object_t object,
2044 vm_object_offset_t offset,
2045 vm_map_t map,
2046 tws_hash_ptr_t *target_ele,
2047 tws_hash_ptr_t **previous_ptr,
2048 tws_hash_ptr_t **free_list,
2049 unsigned int exclusive_addr)
2050 {
2051 unsigned int k;
2052 tws_hash_ptr_t cache_ele;
2053 tws_hash_ptr_t base_ele;
2054
2055 *target_ele = NULL;
2056 *previous_ptr = NULL;
2057
2058 for(k=0; k<tws->expansion_count; k++) {
2059 tws_hash_ele_t ele;
2060 cache_ele = tws->table[k][index];
2061 base_ele = cache_ele;
2062 *previous_ptr = (tws_hash_ptr_t *)&(tws->table[k][index]);
2063 while(cache_ele != NULL) {
2064 if(((unsigned int)
2065 cache_ele->element & TWS_ADDR_HASH) == 0) {
2066 *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
2067 cache_ele = cache_ele->next;
2068 continue;
2069 }
2070 ele = (tws_hash_ele_t)((unsigned int)
2071 cache_ele->element & ~TWS_ADDR_HASH);
2072 if ((ele == 0) || (ele->object == 0)) {
2073 /* A little clean-up of empty elements */
2074 cache_ele->element = 0;
2075 if(base_ele == cache_ele) {
2076 base_ele = cache_ele->next;
2077 tws->table[k][index] = cache_ele->next;
2078 cache_ele->next = tws->free_hash_ele[k];
2079 tws->free_hash_ele[k] = cache_ele;
2080 cache_ele = base_ele;
2081 } else {
2082 **previous_ptr = cache_ele->next;
2083 cache_ele->next = tws->free_hash_ele[k];
2084 tws->free_hash_ele[k] = cache_ele;
2085 cache_ele = **previous_ptr;
2086 }
2087 continue;
2088 }
2089
2090 if ((ele->page_addr <= page_addr)
2091 && (page_addr <= (ele->page_addr +
2092 (vm_offset_t)TWS_INDEX_MASK))
2093 && ((object == NULL)
2094 || ((object == ele->object)
2095 && (offset == ele->offset)
2096 && (map == ele->map)))) {
2097 if(exclusive_addr) {
2098 int delta;
2099 delta = ((page_addr - ele->page_addr)
2100 >> 12);
2101 if((1 << delta) & ele->page_cache) {
2102 /* We've found a match */
2103 *target_ele = cache_ele;
2104 *free_list =
2105 (tws_hash_ptr_t *)
2106 &(tws->free_hash_ele[k]);
2107 return;
2108 }
2109 } else {
2110 /* We've found a match */
2111 *target_ele = cache_ele;
2112 *free_list = (tws_hash_ptr_t *)
2113 &(tws->free_hash_ele[k]);
2114 return;
2115 }
2116 }
2117 *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
2118 cache_ele = cache_ele->next;
2119 }
2120 }
2121 }
2122
2123
2124 /*
2125 * internal sub-function for object space lookup
2126 * returns the target element and the address of the
2127 * previous pointer The previous pointer is the address
2128 * of the pointer pointing to the target element.
2129 * TWS must be locked
2130 */
2131
2132
2133 void
2134 tws_traverse_object_hash_list (
2135 tws_hash_t tws,
2136 unsigned int index,
2137 vm_object_t object,
2138 vm_object_offset_t offset,
2139 unsigned int pagemask,
2140 tws_hash_ptr_t *target_ele,
2141 tws_hash_ptr_t **previous_ptr,
2142 tws_hash_ptr_t **free_list)
2143 {
2144 unsigned int k;
2145 tws_hash_ptr_t cache_ele;
2146 tws_hash_ptr_t base_ele;
2147
2148 *target_ele = NULL;
2149 *previous_ptr = NULL;
2150
2151 for(k=0; k<tws->expansion_count; k++) {
2152 cache_ele = tws->table[k][index];
2153 base_ele = cache_ele;
2154 *previous_ptr = &(tws->table[k][index]);
2155 while(cache_ele != NULL) {
2156 if((((unsigned int)cache_ele->element)
2157 & TWS_ADDR_HASH) != 0) {
2158 *previous_ptr = &(cache_ele->next);
2159 cache_ele = cache_ele->next;
2160 continue;
2161 }
2162 if ((cache_ele->element == 0) ||
2163 (cache_ele->element->object == 0)) {
2164 /* A little clean-up of empty elements */
2165 cache_ele->element = 0;
2166 if(base_ele == cache_ele) {
2167 base_ele = cache_ele->next;
2168 tws->table[k][index] = cache_ele->next;
2169 cache_ele->next = tws->free_hash_ele[k];
2170 tws->free_hash_ele[k] = cache_ele;
2171 cache_ele = tws->table[k][index];
2172 } else {
2173 **previous_ptr = cache_ele->next;
2174 cache_ele->next = tws->free_hash_ele[k];
2175 tws->free_hash_ele[k] = cache_ele;
2176 cache_ele = **previous_ptr;
2177 }
2178 continue;
2179 }
2180 if ((cache_ele->element->object == object)
2181 && (cache_ele->element->offset ==
2182 (offset - (offset & ~TWS_HASH_OFF_MASK)))) {
2183 if((cache_ele->element->page_cache & pagemask)
2184 || (pagemask == 0xFFFFFFFF)) {
2185 /* We've found a match */
2186 *target_ele = cache_ele;
2187 *free_list = &(tws->free_hash_ele[k]);
2188 return;
2189 }
2190 }
2191 *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
2192 cache_ele = cache_ele->next;
2193 }
2194 }
2195 }
2196
2197
2198 /*
2199 * For a given object/offset, discover whether the indexed 32 page frame
2200 * containing the object/offset exists and if their are at least threshold
2201 * pages present. Returns true if population meets threshold.
2202 */
2203 int
2204 tws_test_for_community(
2205 tws_hash_t tws,
2206 vm_object_t object,
2207 vm_object_offset_t offset,
2208 unsigned int threshold,
2209 unsigned int *pagemask)
2210 {
2211 int index;
2212 tws_hash_ptr_t cache_ele;
2213 tws_hash_ptr_t *trailer;
2214 tws_hash_ptr_t *free_list;
2215 int community = 0;
2216
2217 index = do_tws_hash(object, offset,
2218 tws->number_of_elements, tws->number_of_lines);
2219 tws_traverse_object_hash_list(tws, index, object, offset, 0xFFFFFFFF,
2220 &cache_ele, &trailer, &free_list);
2221
2222 if(cache_ele != NULL) {
2223 int i;
2224 unsigned int ctr;
2225 ctr = 0;
2226 for(i=1; i!=0; i=i<<1) {
2227 if(i & cache_ele->element->page_cache)
2228 ctr++;
2229 if(ctr == threshold) {
2230 community = 1;
2231 *pagemask = cache_ele->element->page_cache;
2232 break;
2233 }
2234 }
2235 }
2236
2237 return community;
2238
2239 }
2240
2241
2242 /*
2243 * Gets new hash element for object hash from free pools
2244 * TWS must be locked
2245 */
2246
2247 tws_hash_ptr_t
2248 new_obj_hash(
2249 tws_hash_t tws,
2250 unsigned int set,
2251 unsigned int index)
2252 {
2253 tws_hash_ptr_t element;
2254
2255 if(tws->obj_free_count[set] < tws->number_of_lines * tws->number_of_elements) {
2256 element = &(tws->table_ele[set][tws->obj_free_count[set]]);
2257 tws->obj_free_count[set]+=1;
2258 } else if(tws->free_hash_ele[set] == NULL) {
2259 return NULL;
2260 } else {
2261 element = tws->free_hash_ele[set];
2262 if(element == NULL)
2263 return element;
2264 tws->free_hash_ele[set] = tws->free_hash_ele[set]->next;
2265 }
2266 element->element = 0;
2267 element->next = tws->table[set][index];
2268 tws->table[set][index] = element;
2269 return element;
2270 }
2271
2272 /*
2273 * Gets new hash element for addr hash from free pools
2274 * TWS must be locked
2275 */
2276
2277 tws_hash_ptr_t
2278 new_addr_hash(
2279 tws_hash_t tws,
2280 unsigned int set,
2281 unsigned int index)
2282 {
2283 tws_hash_ptr_t element;
2284
2285 if(tws->addr_free_count[set]
2286 < tws->number_of_lines * tws->number_of_elements) {
2287 element = &(tws->alt_ele[set][tws->addr_free_count[set]]);
2288 tws->addr_free_count[set]+=1;
2289 } else if(tws->free_hash_ele[set] == NULL) {
2290 return NULL;
2291 } else {
2292 element = tws->free_hash_ele[set];
2293 if(element == NULL)
2294 return element;
2295 tws->free_hash_ele[set] = tws->free_hash_ele[set]->next;
2296 }
2297 element->element = (tws_hash_ele_t)TWS_ADDR_HASH;
2298 element->next = tws->table[set][index];
2299 tws->table[set][index] = element;
2300 return element;
2301 }
mirror of XNU