]> git.saurik.com Git - apple/xnu.git/blob - osfmk/vm/task_working_set.c
projects / apple / xnu.git / blob
? search:


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