]> 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.13.8.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_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 /* XXX FBDP !internal doesn't mean vnode pager */
1083 kret = vnode_pager_get_object_size(
1084 object->pager,
1085 &object_size);
1086 if (kret != KERN_SUCCESS) {
1087 object_size = object->size;
1088 }
1089 } else {
1090 object_size = object->size;
1091 }
1092
1093 if((!tws) || (!tws_lock_try(tws))) {
1094 return;
1095 }
1096 age_of_cache = ((sched_tick
1097 - tws->time_of_creation) >> SCHED_TICK_SHIFT);
1098
1099 if (vm_page_free_count < (2 * vm_page_free_target))
1100 memory_scarce = 1;
1101
1102 /* When pre-heat files are not available, resort to speculation */
1103 /* based on size of file */
1104
1105 if (tws->startup_cache || object->internal || age_of_cache > 45) {
1106 pre_heat_size = 0;
1107 } else {
1108 if (object_size > (vm_object_offset_t)(1024 * 1024))
1109 pre_heat_size = 8 * PAGE_SIZE;
1110 else if (object_size > (vm_object_offset_t)(128 * 1024))
1111 pre_heat_size = 4 * PAGE_SIZE;
1112 else
1113 pre_heat_size = 2 * PAGE_SIZE;
1114 }
1115
1116 if (tws->startup_cache) {
1117 int target_page_count;
1118
1119 if (memory_scarce)
1120 target_page_count = 16;
1121 else
1122 target_page_count = 4;
1123
1124 if (tws_test_for_community(tws, object, *start, target_page_count, &ele_cache))
1125 {
1126 start_cache = ele_cache;
1127 *start = *start & TWS_HASH_OFF_MASK;
1128 *end = *start + (32 * PAGE_SIZE_64);
1129
1130 if (*end > object_size) {
1131 *end = round_page_64(object_size);
1132 max_length = 0;
1133 } else
1134 end_cache = ele_cache;
1135
1136 while (max_length > ((*end - *start) + (32 * PAGE_SIZE))) {
1137 int expanded;
1138
1139 expanded = 0;
1140 after = *end;
1141
1142 if ((after + (32 * PAGE_SIZE_64)) <= object_size &&
1143 (tws_test_for_community(tws, object, after, 8, &ele_cache))) {
1144
1145 *end = after + (32 * PAGE_SIZE_64);
1146 end_cache = ele_cache;
1147 expanded = 1;
1148 }
1149 if (max_length < ((*end - *start) + (32 * PAGE_SIZE_64))) {
1150 break;
1151 }
1152 if (*start) {
1153 before = (*start - PAGE_SIZE_64) & TWS_HASH_OFF_MASK;
1154
1155 if (tws_test_for_community(tws, object, before, 8, &ele_cache)) {
1156
1157 *start = before;
1158 start_cache = ele_cache;
1159 expanded = 1;
1160 }
1161 }
1162 if (expanded == 0)
1163 break;
1164 }
1165 if (end_cache)
1166 *end -= PAGE_SIZE_64;
1167
1168 if (start_cache != 0) {
1169 unsigned int mask;
1170
1171 for (mask = 1; mask != 0; mask = mask << 1) {
1172 if (*start == original_start)
1173 break;
1174 if (!(start_cache & mask))
1175 *start += PAGE_SIZE_64;
1176 else
1177 break;
1178 }
1179 }
1180 if (end_cache != 0) {
1181 unsigned int mask;
1182
1183 for (mask = 0x80000000;
1184 mask != 0; mask = mask >> 1) {
1185 if (*end == original_end)
1186 break;
1187 if (!(end_cache & mask))
1188 *end -= PAGE_SIZE_64;
1189 else
1190 break;
1191 }
1192 }
1193 tws_unlock(tws);
1194
1195 if (*end < original_end)
1196 *end = original_end;
1197 return;
1198 }
1199 }
1200
1201 while ((length < max_length) &&
1202 (object_size >=
1203 (after + PAGE_SIZE_64))) {
1204 if(length >= pre_heat_size) {
1205 if(tws_internal_lookup(tws, after, object,
1206 &line) != KERN_SUCCESS) {
1207 vm_object_offset_t extend;
1208
1209 extend = after + PAGE_SIZE_64;
1210 if(tws_internal_lookup(tws, extend, object,
1211 &line) != KERN_SUCCESS) {
1212 break;
1213 }
1214 }
1215 }
1216
1217 if ((object->existence_map != NULL)
1218 && (!LOOK_FOR(object, after))) {
1219 break;
1220 }
1221
1222 if (vm_page_lookup(object, after) != VM_PAGE_NULL) {
1223 /*
1224 * don't bridge resident pages
1225 */
1226 break;
1227 }
1228
1229 if (object->internal) {
1230 /*
1231 * need to acquire a real page in
1232 * advance because this acts as
1233 * a throttling mechanism for
1234 * data_requests to the default
1235 * pager. If this fails, give up
1236 * trying to find any more pages
1237 * in the cluster and send off the
1238 * request for what we already have.
1239 */
1240 if ((m = vm_page_grab()) == VM_PAGE_NULL) {
1241 break;
1242 }
1243 } else if ((m = vm_page_grab_fictitious())
1244 == VM_PAGE_NULL) {
1245 break;
1246 }
1247 m->absent = TRUE;
1248 m->unusual = TRUE;
1249 m->clustered = TRUE;
1250 m->list_req_pending = TRUE;
1251
1252 vm_page_insert(m, object, after);
1253 object->absent_count++;
1254 after += PAGE_SIZE_64;
1255 length += PAGE_SIZE;
1256 }
1257 *end = after;
1258 while (length < max_length) {
1259 if (before == 0)
1260 break;
1261 before -= PAGE_SIZE_64;
1262
1263 if(length >= pre_heat_size) {
1264 if(tws_internal_lookup(tws, before, object,
1265 &line) != KERN_SUCCESS) {
1266 vm_object_offset_t extend;
1267
1268 extend = before;
1269 if (extend == 0)
1270 break;
1271 extend -= PAGE_SIZE_64;
1272 if(tws_internal_lookup(tws, extend, object,
1273 &line) != KERN_SUCCESS) {
1274 break;
1275 }
1276 }
1277 }
1278 if ((object->existence_map != NULL)
1279 && (!LOOK_FOR(object, before))) {
1280 break;
1281 }
1282
1283 if (vm_page_lookup(object, before) != VM_PAGE_NULL) {
1284 /*
1285 * don't bridge resident pages
1286 */
1287 break;
1288 }
1289
1290 if (object->internal) {
1291 /*
1292 * need to acquire a real page in
1293 * advance because this acts as
1294 * a throttling mechanism for
1295 * data_requests to the default
1296 * pager. If this fails, give up
1297 * trying to find any more pages
1298 * in the cluster and send off the
1299 * request for what we already have.
1300 */
1301 if ((m = vm_page_grab()) == VM_PAGE_NULL) {
1302 break;
1303 }
1304 } else if ((m = vm_page_grab_fictitious())
1305 == VM_PAGE_NULL) {
1306 break;
1307 }
1308 m->absent = TRUE;
1309 m->unusual = TRUE;
1310 m->clustered = TRUE;
1311 m->list_req_pending = TRUE;
1312
1313 vm_page_insert(m, object, before);
1314 object->absent_count++;
1315 *start -= PAGE_SIZE_64;
1316 length += PAGE_SIZE;
1317 }
1318 tws_unlock(tws);
1319 }
1320
1321 void
1322 tws_line_signal(
1323 tws_hash_t tws,
1324 vm_map_t map,
1325 tws_hash_line_t hash_line,
1326 vm_offset_t target_page)
1327 {
1328 unsigned int i,j;
1329 vm_object_t object;
1330 vm_object_offset_t offset;
1331 vm_object_offset_t before;
1332 vm_object_offset_t after;
1333 struct tws_hash_ele *element;
1334 vm_page_t m,p;
1335 kern_return_t rc;
1336
1337 if(tws->style != TWS_HASH_STYLE_SIGNAL)
1338 return;
1339
1340 vm_map_lock(map);
1341 for (i=0; i<tws->number_of_elements; i++) {
1342
1343 vm_object_offset_t local_off = 0;
1344
1345 if(hash_line->list[i].object == 0)
1346 continue;
1347
1348 element = &hash_line->list[i];
1349
1350 if (element->page_addr == target_page)
1351 continue;
1352
1353 j = 1;
1354 while (j != 0) {
1355 if(j & element->page_cache)
1356 break;
1357 j <<= 1;
1358 local_off += PAGE_SIZE_64;
1359 }
1360 object = element->object;
1361 offset = element->offset + local_off;
1362
1363 /* first try a fast test to speed up no-op signal */
1364 if (((p = vm_page_lookup(object, offset)) != NULL)
1365 || (object->pager == NULL)
1366 || (object->shadow_severed)) {
1367 continue;
1368 }
1369
1370 if((!object->alive) ||
1371 (!object->pager_created) || (!object->pager_ready))
1372 continue;
1373
1374 if (object->internal) {
1375 if (object->existence_map == NULL) {
1376 if (object->shadow)
1377 continue;
1378 } else {
1379 if(!LOOK_FOR(object, offset))
1380 continue;
1381 }
1382 }
1383
1384 vm_object_reference(object);
1385 vm_map_unlock(map);
1386
1387 if(object->internal) {
1388 m = vm_page_grab();
1389 } else {
1390 m = vm_page_grab_fictitious();
1391 }
1392
1393 if(m == NULL) {
1394 vm_object_deallocate(object);
1395 vm_map_lock(map);
1396 continue;
1397 }
1398
1399 vm_object_lock(object);
1400 if (((p = vm_page_lookup(object, offset)) != NULL)
1401 || (object->pager == NULL)
1402 || (object->shadow_severed)) {
1403 VM_PAGE_FREE(m);
1404 vm_object_unlock(object);
1405 vm_object_deallocate(object);
1406 vm_map_lock(map);
1407 continue;
1408 }
1409
1410 vm_page_insert(m, object, offset);
1411
1412 if (object->absent_count > vm_object_absent_max) {
1413 VM_PAGE_FREE(m);
1414 vm_object_unlock(object);
1415 vm_object_deallocate(object);
1416 vm_map_lock(map);
1417 break;
1418 }
1419 m->list_req_pending = TRUE;
1420 m->absent = TRUE;
1421 m->unusual = TRUE;
1422 object->absent_count++;
1423
1424 before = offset;
1425 after = offset + PAGE_SIZE_64;
1426 tws_build_cluster(tws, object, &before, &after, 0x16000);
1427 vm_object_unlock(object);
1428
1429 rc = memory_object_data_request(object->pager,
1430 before + object->paging_offset,
1431 (vm_size_t)(after - before), VM_PROT_READ);
1432 if (rc != KERN_SUCCESS) {
1433 offset = before;
1434 vm_object_lock(object);
1435 while (offset < after) {
1436 m = vm_page_lookup(object, offset);
1437 if(m && m->absent && m->busy)
1438 VM_PAGE_FREE(m);
1439 offset += PAGE_SIZE;
1440 }
1441 vm_object_unlock(object);
1442 vm_object_deallocate(object);
1443 } else {
1444 vm_object_deallocate(object);
1445 }
1446 vm_map_lock(map);
1447 continue;
1448 }
1449 vm_map_unlock(map);
1450 }
1451
1452 /* tws locked on entry */
1453
1454 tws_startup_t
1455 tws_create_startup_list(
1456 tws_hash_t tws)
1457 {
1458
1459 tws_startup_t startup;
1460 unsigned int i,j,k;
1461 unsigned int total_elements;
1462 unsigned int startup_size;
1463 unsigned int sindex;
1464 unsigned int hash_index;
1465 tws_startup_ptr_t element;
1466
1467 total_elements = tws->expansion_count *
1468 (tws->number_of_lines * tws->number_of_elements);
1469
1470 startup_size = sizeof(struct tws_startup)
1471 + (total_elements * sizeof(tws_startup_ptr_t *))
1472 + (total_elements * sizeof(struct tws_startup_ptr))
1473 + (total_elements * sizeof(struct tws_startup_ele));
1474 startup = (tws_startup_t)(kalloc(startup_size));
1475
1476 if(startup == NULL)
1477 return startup;
1478
1479 bzero((char *) startup, startup_size);
1480
1481 startup->table = (tws_startup_ptr_t *)
1482 (((int)startup) + (sizeof(struct tws_startup)));
1483 startup->ele = (struct tws_startup_ptr *)
1484 (((vm_offset_t)startup->table) +
1485 (total_elements * sizeof(tws_startup_ptr_t)));
1486
1487 startup->array = (struct tws_startup_ele *)
1488 (((vm_offset_t)startup->ele) +
1489 (total_elements * sizeof(struct tws_startup_ptr)));
1490
1491 startup->tws_hash_size = startup_size;
1492 startup->ele_count = 0; /* burn first hash ele, else we can't tell from zero */
1493 startup->array_size = total_elements;
1494 startup->hash_count = 1;
1495
1496 sindex = 0;
1497
1498
1499 for(i = 0; i<tws->number_of_lines; i++) {
1500 for(j = 0; j<tws->number_of_elements; j++) {
1501 for(k = 0; k<tws->expansion_count; k++) {
1502 tws_hash_ele_t entry;
1503 unsigned int hash_retry;
1504 vm_offset_t addr;
1505
1506 entry = &tws->cache[k][i].list[j];
1507 addr = entry->page_addr;
1508 hash_retry = 0;
1509 if(entry->object != 0) {
1510 /* get a hash element */
1511 hash_index = do_startup_hash(addr,
1512 startup->array_size);
1513
1514 if(startup->hash_count < total_elements) {
1515 element = &(startup->ele[startup->hash_count]);
1516 startup->hash_count += 1;
1517 } else {
1518 /* exit we're out of elements */
1519 break;
1520 }
1521 /* place the hash element */
1522 element->next = startup->table[hash_index];
1523 startup->table[hash_index] = (tws_startup_ptr_t)
1524 ((int)element - (int)&startup->ele[0]);
1525
1526 /* set entry OFFSET in hash element */
1527 element->element = (tws_startup_ele_t)
1528 ((int)&startup->array[sindex] -
1529 (int)&startup->array[0]);
1530
1531 startup->array[sindex].page_addr = entry->page_addr;
1532 startup->array[sindex].page_cache = entry->page_cache;
1533 startup->ele_count++;
1534 sindex++;
1535
1536 }
1537 }
1538 }
1539 }
1540
1541 return startup;
1542 }
1543
1544
1545 /*
1546 * Returns an entire cache line. The line is deleted from the startup
1547 * cache on return. The caller can check startup->ele_count for an empty
1548 * list. Access synchronization is the responsibility of the caller.
1549 */
1550
1551 unsigned int
1552 tws_startup_list_lookup(
1553 tws_startup_t startup,
1554 vm_offset_t addr)
1555 {
1556 unsigned int hash_index;
1557 unsigned int page_cache_bits;
1558 unsigned int startup_shift;
1559 tws_startup_ele_t entry;
1560 vm_offset_t next_addr;
1561 tws_startup_ptr_t element;
1562 tws_startup_ptr_t base_ele;
1563 tws_startup_ptr_t *previous_ptr;
1564
1565 page_cache_bits = 0;
1566
1567 hash_index = do_startup_hash(addr, startup->array_size);
1568
1569 if(((unsigned int)&(startup->table[hash_index])) >= ((unsigned int)startup + startup->tws_hash_size)) {
1570 return page_cache_bits = 0;
1571 }
1572 element = (tws_startup_ptr_t)((int)startup->table[hash_index] +
1573 (int)&startup->ele[0]);
1574 base_ele = element;
1575 previous_ptr = &(startup->table[hash_index]);
1576 while(element > &startup->ele[0]) {
1577 if (((int)element + sizeof(struct tws_startup_ptr))
1578 > ((int)startup + startup->tws_hash_size)) {
1579 return page_cache_bits;
1580 }
1581 entry = (tws_startup_ele_t)
1582 ((int)element->element
1583 + (int)&startup->array[0]);
1584 if((((int)entry + sizeof(struct tws_startup_ele))
1585 > ((int)startup + startup->tws_hash_size))
1586 || ((int)entry < (int)startup)) {
1587 return page_cache_bits;
1588 }
1589 if ((addr >= entry->page_addr) &&
1590 (addr <= (entry->page_addr + 0x1F000))) {
1591 startup_shift = (addr - entry->page_addr)>>12;
1592 page_cache_bits |= entry->page_cache >> startup_shift;
1593 /* don't dump the pages, unless the addresses */
1594 /* line up perfectly. The cache may be used */
1595 /* by other mappings */
1596 entry->page_cache &= (1 << startup_shift) - 1;
1597 if(addr == entry->page_addr) {
1598 if(base_ele == element) {
1599 base_ele = (tws_startup_ptr_t)
1600 ((int)element->next
1601 + (int)&startup->ele[0]);
1602 startup->table[hash_index] = element->next;
1603 element = base_ele;
1604 } else {
1605 *previous_ptr = element->next;
1606 element = (tws_startup_ptr_t)
1607 ((int)*previous_ptr
1608 + (int)&startup->ele[0]);
1609 }
1610 entry->page_addr = 0;
1611 startup->ele_count--;
1612 continue;
1613 }
1614 }
1615 next_addr = addr + 0x1F000;
1616 if ((next_addr >= entry->page_addr) &&
1617 (next_addr <= (entry->page_addr + 0x1F000))) {
1618 startup_shift = (next_addr - entry->page_addr)>>12;
1619 page_cache_bits |= entry->page_cache << (0x1F - startup_shift);
1620 entry->page_cache &= ~((1 << (startup_shift + 1)) - 1);
1621 if(entry->page_cache == 0) {
1622 if(base_ele == element) {
1623 base_ele = (tws_startup_ptr_t)
1624 ((int)element->next
1625 + (int)&startup->ele[0]);
1626 startup->table[hash_index] = element->next;
1627 element = base_ele;
1628 } else {
1629 *previous_ptr = element->next;
1630 element = (tws_startup_ptr_t)
1631 ((int)*previous_ptr
1632 + (int)&startup->ele[0]);
1633 }
1634 entry->page_addr = 0;
1635 startup->ele_count--;
1636 continue;
1637 }
1638 }
1639 previous_ptr = &(element->next);
1640 element = (tws_startup_ptr_t)
1641 ((int) element->next + (int) &startup->ele[0]);
1642 }
1643
1644 return page_cache_bits;
1645 }
1646
1647 kern_return_t
1648 tws_send_startup_info(
1649 task_t task)
1650 {
1651
1652 tws_hash_t tws;
1653
1654 task_lock(task);
1655 tws = task->dynamic_working_set;
1656 task_unlock(task);
1657 if(tws == NULL) {
1658 return KERN_FAILURE;
1659 }
1660 return tws_internal_startup_send(tws);
1661 }
1662
1663
1664 kern_return_t
1665 tws_internal_startup_send(
1666 tws_hash_t tws)
1667 {
1668
1669 tws_startup_t scache;
1670
1671 if(tws == NULL) {
1672 return KERN_FAILURE;
1673 }
1674 tws_lock(tws);
1675 /* used to signal write or release depending on state of tws */
1676 if(tws->startup_cache) {
1677 vm_offset_t startup_buf;
1678 vm_size_t size;
1679 startup_buf = (vm_offset_t)tws->startup_cache;
1680 size = tws->startup_cache->tws_hash_size;
1681 tws->startup_cache = 0;
1682 tws_unlock(tws);
1683 kmem_free(kernel_map, startup_buf, size);
1684 return KERN_SUCCESS;
1685 }
1686 if(tws->startup_name == NULL) {
1687 tws_unlock(tws);
1688 return KERN_FAILURE;
1689 }
1690 scache = tws_create_startup_list(tws);
1691 if(scache == NULL)
1692 return KERN_FAILURE;
1693 bsd_write_page_cache_file(tws->uid, tws->startup_name,
1694 (caddr_t) scache, scache->tws_hash_size,
1695 tws->mod, tws->fid);
1696 kfree(scache, scache->tws_hash_size);
1697 kfree(tws->startup_name, tws->startup_name_length);
1698 tws->startup_name = NULL;
1699 tws_unlock(tws);
1700 return KERN_SUCCESS;
1701 }
1702
1703 kern_return_t
1704 tws_handle_startup_file(
1705 task_t task,
1706 unsigned int uid,
1707 char *app_name,
1708 void *app_vp,
1709 boolean_t *new_info)
1710
1711 {
1712 tws_startup_t startup;
1713 vm_offset_t cache_size;
1714 kern_return_t error;
1715 int fid;
1716 int mod;
1717
1718 *new_info = FALSE;
1719 /* don't pre-heat kernel task */
1720 if(task == kernel_task)
1721 return KERN_SUCCESS;
1722 error = bsd_read_page_cache_file(uid, &fid,
1723 &mod, app_name,
1724 app_vp,
1725 (vm_offset_t *) &startup,
1726 &cache_size);
1727 if(error) {
1728 return KERN_FAILURE;
1729 }
1730 if(startup == NULL) {
1731 /* Entry for app does not exist, make */
1732 /* one */
1733 /* we will want our own copy of the shared */
1734 /* regions to pick up a true picture of all */
1735 /* the pages we will touch. */
1736 if((lsf_zone->count * lsf_zone->elem_size)
1737 > (lsf_zone->max_size >> 1)) {
1738 /* We don't want to run out of shared memory */
1739 /* map entries by starting too many private versions */
1740 /* of the shared library structures */
1741 return KERN_SUCCESS;
1742 }
1743 *new_info = TRUE;
1744
1745 error = tws_write_startup_file(task,
1746 fid, mod, app_name, uid);
1747 if(error)
1748 return error;
1749
1750 } else {
1751 error = tws_read_startup_file(task,
1752 (tws_startup_t)startup,
1753 cache_size);
1754 if(error) {
1755 kmem_free(kernel_map,
1756 (vm_offset_t)startup, cache_size);
1757 return error;
1758 }
1759 }
1760 return KERN_SUCCESS;
1761 }
1762
1763 kern_return_t
1764 tws_write_startup_file(
1765 task_t task,
1766 int fid,
1767 int mod,
1768 char *name,
1769 unsigned int uid)
1770 {
1771 tws_hash_t tws;
1772 unsigned int string_length;
1773
1774 string_length = strlen(name);
1775
1776 restart:
1777 task_lock(task);
1778 tws = task->dynamic_working_set;
1779 task_unlock(task);
1780
1781 if(tws == NULL) {
1782 kern_return_t error;
1783
1784 /* create a dynamic working set of normal size */
1785 if((error = task_working_set_create(task, 0, 0, TWS_HASH_STYLE_DEFAULT)) != KERN_SUCCESS)
1786 return error;
1787 /* we need to reset tws and relock */
1788 goto restart;
1789 }
1790 tws_lock(tws);
1791
1792 if(tws->startup_name != NULL) {
1793 tws_unlock(tws);
1794 return KERN_FAILURE;
1795 }
1796
1797 tws->startup_name = (char *)
1798 kalloc((string_length + 1) * (sizeof(char)));
1799 if(tws->startup_name == NULL) {
1800 tws_unlock(tws);
1801 return KERN_FAILURE;
1802 }
1803
1804 bcopy(name, (char *)tws->startup_name, string_length + 1);
1805 tws->startup_name_length = (string_length + 1) * sizeof(char);
1806 tws->uid = uid;
1807 tws->fid = fid;
1808 tws->mod = mod;
1809
1810 tws_unlock(tws);
1811 return KERN_SUCCESS;
1812 }
1813
1814 unsigned long tws_read_startup_file_rejects = 0;
1815
1816 kern_return_t
1817 tws_read_startup_file(
1818 task_t task,
1819 tws_startup_t startup,
1820 vm_offset_t cache_size)
1821 {
1822 tws_hash_t tws;
1823 int lines;
1824 int old_exp_count;
1825 unsigned int ele_count;
1826
1827 restart:
1828 task_lock(task);
1829 tws = task->dynamic_working_set;
1830
1831 /* create a dynamic working set to match file size */
1832
1833 /* start with total size of the data we got from app_profile */
1834 ele_count = cache_size;
1835 /* skip the startup header */
1836 ele_count -= sizeof(struct tws_startup);
1837 /*
1838 * For each startup cache entry, we have one of these:
1839 * tws_startup_ptr_t startup->table[];
1840 * struct tws_startup_ptr startup->ele[];
1841 * struct tws_startup_ele startup->array[];
1842 */
1843 ele_count /= (sizeof (tws_startup_ptr_t) +
1844 sizeof (struct tws_startup_ptr) +
1845 sizeof (struct tws_startup_ele));
1846
1847 /*
1848 * Sanity check: make sure the value for startup->array_size
1849 * that we read from the app_profile file matches the size
1850 * of the data we read from disk. If it doesn't match, we
1851 * can't trust the data and we just drop it all.
1852 */
1853 if (cache_size < sizeof(struct tws_startup) ||
1854 startup->array_size != ele_count) {
1855 tws_read_startup_file_rejects++;
1856 task_unlock(task);
1857 kmem_free(kernel_map, (vm_offset_t)startup, cache_size);
1858 return(KERN_SUCCESS);
1859 }
1860
1861 /*
1862 * We'll create the task working set with the default row size
1863 * (TWS_ARRAY_SIZE), so this will give us the number of lines
1864 * we need to store all the data from the app_profile startup
1865 * cache.
1866 */
1867 lines = ele_count / TWS_ARRAY_SIZE;
1868
1869 if(lines <= TWS_SMALL_HASH_LINE_COUNT) {
1870 lines = TWS_SMALL_HASH_LINE_COUNT;
1871 task_unlock(task);
1872 kmem_free(kernel_map, (vm_offset_t)startup, cache_size);
1873 return(KERN_SUCCESS);
1874 } else {
1875 old_exp_count = lines/TWS_HASH_LINE_COUNT;
1876 if((old_exp_count * TWS_HASH_LINE_COUNT) != lines) {
1877 lines = (old_exp_count + 1)
1878 * TWS_HASH_LINE_COUNT;
1879 }
1880 if(tws == NULL) {
1881 kern_return_t error;
1882
1883 task_unlock(task);
1884 if ((error = task_working_set_create(task, lines, 0, TWS_HASH_STYLE_DEFAULT)) != KERN_SUCCESS)
1885 return error;
1886 /* we need to reset tws and relock */
1887 goto restart;
1888 } else {
1889 task_unlock(task);
1890 tws_expand_working_set(
1891 (void *)tws, lines, TRUE);
1892 }
1893 }
1894
1895 tws_lock(tws);
1896
1897 if(tws->startup_cache != NULL) {
1898 tws_unlock(tws);
1899 return KERN_FAILURE;
1900 }
1901
1902
1903 /* now need to fix up internal table pointers */
1904 startup->table = (tws_startup_ptr_t *)
1905 (((int)startup) + (sizeof(struct tws_startup)));
1906 startup->ele = (struct tws_startup_ptr *)
1907 (((vm_offset_t)startup->table) +
1908 (startup->array_size * sizeof(tws_startup_ptr_t)));
1909 startup->array = (struct tws_startup_ele *)
1910 (((vm_offset_t)startup->ele) +
1911 (startup->array_size * sizeof(struct tws_startup_ptr)));
1912 /* the allocation size and file size should be the same */
1913 /* just in case their not, make sure we dealloc correctly */
1914 startup->tws_hash_size = cache_size;
1915
1916 tws->startup_cache = startup;
1917 tws_unlock(tws);
1918 return KERN_SUCCESS;
1919 }
1920
1921
1922 void
1923 tws_hash_ws_flush(tws_hash_t tws) {
1924 tws_startup_t scache;
1925 if(tws == NULL) {
1926 return;
1927 }
1928 tws_lock(tws);
1929 if(tws->startup_name != NULL) {
1930 scache = tws_create_startup_list(tws);
1931 if(scache == NULL) {
1932 /* dump the name cache, we'll */
1933 /* get it next time */
1934 kfree(tws->startup_name, tws->startup_name_length);
1935 tws->startup_name = NULL;
1936 tws_unlock(tws);
1937 return;
1938 }
1939 bsd_write_page_cache_file(tws->uid, tws->startup_name,
1940 (caddr_t) scache, scache->tws_hash_size,
1941 tws->mod, tws->fid);
1942 kfree(scache, scache->tws_hash_size);
1943 kfree(tws->startup_name, tws->startup_name_length);
1944 tws->startup_name = NULL;
1945 }
1946 tws_unlock(tws);
1947 return;
1948 }
1949
1950 void
1951 tws_hash_destroy(tws_hash_t tws)
1952 {
1953 unsigned int i,k;
1954
1955 if(tws->startup_cache != NULL) {
1956 kmem_free(kernel_map,
1957 (vm_offset_t)tws->startup_cache,
1958 tws->startup_cache->tws_hash_size);
1959 tws->startup_cache = NULL;
1960 }
1961 if(tws->startup_name != NULL) {
1962 tws_internal_startup_send(tws);
1963 }
1964 for (i=0; i<tws->number_of_lines; i++) {
1965 for(k=0; k<tws->expansion_count; k++) {
1966 /* clear the object refs */
1967 tws_hash_line_clear(tws, &(tws->cache[k][i]), NULL, FALSE);
1968 }
1969 }
1970 i = 0;
1971 while (i < tws->expansion_count) {
1972
1973 kfree(tws->table[i],
1974 sizeof(tws_hash_ptr_t)
1975 * tws->number_of_lines
1976 * tws->number_of_elements);
1977 kfree(tws->table_ele[i],
1978 sizeof(struct tws_hash_ptr)
1979 * tws->number_of_lines
1980 * tws->number_of_elements);
1981 kfree(tws->alt_ele[i],
1982 sizeof(struct tws_hash_ptr)
1983 * tws->number_of_lines
1984 * tws->number_of_elements);
1985 kfree(tws->cache[i],
1986 sizeof(struct tws_hash_line) * tws->number_of_lines);
1987 i++;
1988 }
1989 if(tws->startup_name != NULL) {
1990 kfree(tws->startup_name, tws->startup_name_length);
1991 }
1992 kfree(tws, sizeof(struct tws_hash));
1993 }
1994
1995 void
1996 tws_hash_clear(tws_hash_t tws)
1997 {
1998 unsigned int i, k;
1999
2000 for (i=0; i<tws->number_of_lines; i++) {
2001 for(k=0; k<tws->expansion_count; k++) {
2002 /* clear the object refs */
2003 tws_hash_line_clear(tws, &(tws->cache[k][i]), NULL, FALSE);
2004 }
2005 }
2006 }
2007
2008 kern_return_t
2009 task_working_set_create(
2010 task_t task,
2011 unsigned int lines,
2012 unsigned int rows,
2013 unsigned int style)
2014 {
2015
2016 if (lines == 0) {
2017 lines = TWS_HASH_LINE_COUNT;
2018 }
2019 if (rows == 0) {
2020 rows = TWS_ARRAY_SIZE;
2021 }
2022 if (style == TWS_HASH_STYLE_DEFAULT) {
2023 style = TWS_HASH_STYLE_BASIC;
2024 }
2025 task_lock(task);
2026 if(task->dynamic_working_set != 0) {
2027 task_unlock(task);
2028 return(KERN_FAILURE);
2029 } else if((task->dynamic_working_set =
2030 tws_hash_create(lines, rows, style)) == 0) {
2031 task_unlock(task);
2032 return(KERN_NO_SPACE);
2033 }
2034 task_unlock(task);
2035 return KERN_SUCCESS;
2036 }
2037
2038
2039 /* Internal use only routines */
2040
2041
2042 /*
2043 * internal sub-function for address space lookup
2044 * returns the target element and the address of the
2045 * previous pointer The previous pointer is the address
2046 * of the pointer pointing to the target element.
2047 * TWS must be locked
2048 */
2049
2050 void
2051 tws_traverse_address_hash_list (
2052 tws_hash_t tws,
2053 unsigned int index,
2054 vm_offset_t page_addr,
2055 vm_object_t object,
2056 vm_object_offset_t offset,
2057 vm_map_t map,
2058 tws_hash_ptr_t *target_ele,
2059 tws_hash_ptr_t **previous_ptr,
2060 tws_hash_ptr_t **free_list,
2061 unsigned int exclusive_addr)
2062 {
2063 unsigned int k;
2064 tws_hash_ptr_t cache_ele;
2065 tws_hash_ptr_t base_ele;
2066
2067 *target_ele = NULL;
2068 *previous_ptr = NULL;
2069
2070 for(k=0; k<tws->expansion_count; k++) {
2071 tws_hash_ele_t ele;
2072 cache_ele = tws->table[k][index];
2073 base_ele = cache_ele;
2074 *previous_ptr = (tws_hash_ptr_t *)&(tws->table[k][index]);
2075 while(cache_ele != NULL) {
2076 if(((unsigned int)
2077 cache_ele->element & TWS_ADDR_HASH) == 0) {
2078 *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
2079 cache_ele = cache_ele->next;
2080 continue;
2081 }
2082 ele = (tws_hash_ele_t)((unsigned int)
2083 cache_ele->element & ~TWS_ADDR_HASH);
2084 if ((ele == 0) || (ele->object == 0)) {
2085 /* A little clean-up of empty elements */
2086 cache_ele->element = 0;
2087 if(base_ele == cache_ele) {
2088 base_ele = cache_ele->next;
2089 tws->table[k][index] = cache_ele->next;
2090 cache_ele->next = tws->free_hash_ele[k];
2091 tws->free_hash_ele[k] = cache_ele;
2092 cache_ele = base_ele;
2093 } else {
2094 **previous_ptr = cache_ele->next;
2095 cache_ele->next = tws->free_hash_ele[k];
2096 tws->free_hash_ele[k] = cache_ele;
2097 cache_ele = **previous_ptr;
2098 }
2099 continue;
2100 }
2101
2102 if ((ele->page_addr <= page_addr)
2103 && (page_addr <= (ele->page_addr +
2104 (vm_offset_t)TWS_INDEX_MASK))
2105 && ((object == NULL)
2106 || ((object == ele->object)
2107 && (offset == ele->offset)
2108 && (map == ele->map)))) {
2109 if(exclusive_addr) {
2110 int delta;
2111 delta = ((page_addr - ele->page_addr)
2112 >> 12);
2113 if((1 << delta) & ele->page_cache) {
2114 /* We've found a match */
2115 *target_ele = cache_ele;
2116 *free_list =
2117 (tws_hash_ptr_t *)
2118 &(tws->free_hash_ele[k]);
2119 return;
2120 }
2121 } else {
2122 /* We've found a match */
2123 *target_ele = cache_ele;
2124 *free_list = (tws_hash_ptr_t *)
2125 &(tws->free_hash_ele[k]);
2126 return;
2127 }
2128 }
2129 *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
2130 cache_ele = cache_ele->next;
2131 }
2132 }
2133 }
2134
2135
2136 /*
2137 * internal sub-function for object space lookup
2138 * returns the target element and the address of the
2139 * previous pointer The previous pointer is the address
2140 * of the pointer pointing to the target element.
2141 * TWS must be locked
2142 */
2143
2144
2145 void
2146 tws_traverse_object_hash_list (
2147 tws_hash_t tws,
2148 unsigned int index,
2149 vm_object_t object,
2150 vm_object_offset_t offset,
2151 unsigned int pagemask,
2152 tws_hash_ptr_t *target_ele,
2153 tws_hash_ptr_t **previous_ptr,
2154 tws_hash_ptr_t **free_list)
2155 {
2156 unsigned int k;
2157 tws_hash_ptr_t cache_ele;
2158 tws_hash_ptr_t base_ele;
2159
2160 *target_ele = NULL;
2161 *previous_ptr = NULL;
2162
2163 for(k=0; k<tws->expansion_count; k++) {
2164 cache_ele = tws->table[k][index];
2165 base_ele = cache_ele;
2166 *previous_ptr = &(tws->table[k][index]);
2167 while(cache_ele != NULL) {
2168 if((((unsigned int)cache_ele->element)
2169 & TWS_ADDR_HASH) != 0) {
2170 *previous_ptr = &(cache_ele->next);
2171 cache_ele = cache_ele->next;
2172 continue;
2173 }
2174 if ((cache_ele->element == 0) ||
2175 (cache_ele->element->object == 0)) {
2176 /* A little clean-up of empty elements */
2177 cache_ele->element = 0;
2178 if(base_ele == cache_ele) {
2179 base_ele = cache_ele->next;
2180 tws->table[k][index] = cache_ele->next;
2181 cache_ele->next = tws->free_hash_ele[k];
2182 tws->free_hash_ele[k] = cache_ele;
2183 cache_ele = tws->table[k][index];
2184 } else {
2185 **previous_ptr = cache_ele->next;
2186 cache_ele->next = tws->free_hash_ele[k];
2187 tws->free_hash_ele[k] = cache_ele;
2188 cache_ele = **previous_ptr;
2189 }
2190 continue;
2191 }
2192 if ((cache_ele->element->object == object)
2193 && (cache_ele->element->offset ==
2194 (offset - (offset & ~TWS_HASH_OFF_MASK)))) {
2195 if((cache_ele->element->page_cache & pagemask)
2196 || (pagemask == 0xFFFFFFFF)) {
2197 /* We've found a match */
2198 *target_ele = cache_ele;
2199 *free_list = &(tws->free_hash_ele[k]);
2200 return;
2201 }
2202 }
2203 *previous_ptr = (tws_hash_ptr_t *)&(cache_ele->next);
2204 cache_ele = cache_ele->next;
2205 }
2206 }
2207 }
2208
2209
2210 /*
2211 * For a given object/offset, discover whether the indexed 32 page frame
2212 * containing the object/offset exists and if their are at least threshold
2213 * pages present. Returns true if population meets threshold.
2214 */
2215 int
2216 tws_test_for_community(
2217 tws_hash_t tws,
2218 vm_object_t object,
2219 vm_object_offset_t offset,
2220 unsigned int threshold,
2221 unsigned int *pagemask)
2222 {
2223 int index;
2224 tws_hash_ptr_t cache_ele;
2225 tws_hash_ptr_t *trailer;
2226 tws_hash_ptr_t *free_list;
2227 int community = 0;
2228
2229 index = do_tws_hash(object, offset,
2230 tws->number_of_elements, tws->number_of_lines);
2231 tws_traverse_object_hash_list(tws, index, object, offset, 0xFFFFFFFF,
2232 &cache_ele, &trailer, &free_list);
2233
2234 if(cache_ele != NULL) {
2235 int i;
2236 unsigned int ctr;
2237 ctr = 0;
2238 for(i=1; i!=0; i=i<<1) {
2239 if(i & cache_ele->element->page_cache)
2240 ctr++;
2241 if(ctr == threshold) {
2242 community = 1;
2243 *pagemask = cache_ele->element->page_cache;
2244 break;
2245 }
2246 }
2247 }
2248
2249 return community;
2250
2251 }
2252
2253
2254 /*
2255 * Gets new hash element for object hash from free pools
2256 * TWS must be locked
2257 */
2258
2259 tws_hash_ptr_t
2260 new_obj_hash(
2261 tws_hash_t tws,
2262 unsigned int set,
2263 unsigned int index)
2264 {
2265 tws_hash_ptr_t element;
2266
2267 if(tws->obj_free_count[set] < tws->number_of_lines * tws->number_of_elements) {
2268 element = &(tws->table_ele[set][tws->obj_free_count[set]]);
2269 tws->obj_free_count[set]+=1;
2270 } else if(tws->free_hash_ele[set] == NULL) {
2271 return NULL;
2272 } else {
2273 element = tws->free_hash_ele[set];
2274 if(element == NULL)
2275 return element;
2276 tws->free_hash_ele[set] = tws->free_hash_ele[set]->next;
2277 }
2278 element->element = 0;
2279 element->next = tws->table[set][index];
2280 tws->table[set][index] = element;
2281 return element;
2282 }
2283
2284 /*
2285 * Gets new hash element for addr hash from free pools
2286 * TWS must be locked
2287 */
2288
2289 tws_hash_ptr_t
2290 new_addr_hash(
2291 tws_hash_t tws,
2292 unsigned int set,
2293 unsigned int index)
2294 {
2295 tws_hash_ptr_t element;
2296
2297 if(tws->addr_free_count[set]
2298 < tws->number_of_lines * tws->number_of_elements) {
2299 element = &(tws->alt_ele[set][tws->addr_free_count[set]]);
2300 tws->addr_free_count[set]+=1;
2301 } else if(tws->free_hash_ele[set] == NULL) {
2302 return NULL;
2303 } else {
2304 element = tws->free_hash_ele[set];
2305 if(element == NULL)
2306 return element;
2307 tws->free_hash_ele[set] = tws->free_hash_ele[set]->next;
2308 }
2309 element->element = (tws_hash_ele_t)TWS_ADDR_HASH;
2310 element->next = tws->table[set][index];
2311 tws->table[set][index] = element;
2312 return element;
2313 }
mirror of XNU