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