]> git.saurik.com Git - apple/xnu.git/blob - osfmk/vm/vm_purgeable.c
xnu-2422.100.13.tar.gz
[apple/xnu.git] / osfmk / vm / vm_purgeable.c
1 /*
2 * Copyright (c) 2007 Apple Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_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. Please obtain a copy of the License at
10 * http://www.opensource.apple.com/apsl/ and read it before using this
11 * file.
12 *
13 * The 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, QUIET ENJOYMENT OR NON-INFRINGEMENT.
18 * Please see the License for the specific language governing rights and
19 * limitations under the License.
20 *
21 * @APPLE_LICENSE_HEADER_END@
22 */
23
24 #include <mach/mach_types.h>
25 #include <vm/vm_page.h>
26 #include <vm/vm_kern.h> /* kmem_alloc */
27 #include <vm/vm_protos.h>
28 #include <vm/vm_purgeable_internal.h>
29 #include <sys/kdebug.h>
30 #include <kern/sched_prim.h>
31 #include <machine/limits.h>
32
33 extern vm_pressure_level_t memorystatus_vm_pressure_level;
34
35 struct token {
36 token_cnt_t count;
37 token_idx_t prev;
38 token_idx_t next;
39 };
40
41 struct token *tokens;
42 token_idx_t token_q_max_cnt = 0;
43 vm_size_t token_q_cur_size = 0;
44
45 token_idx_t token_free_idx = 0; /* head of free queue */
46 token_idx_t token_init_idx = 1; /* token 0 is reserved!! */
47 int32_t token_new_pagecount = 0; /* count of pages that will
48 * be added onto token queue */
49
50 int available_for_purge = 0; /* increase when ripe token
51 * added, decrease when ripe
52 * token removed.
53 * protected by page_queue_lock
54 */
55
56 static int token_q_allocating = 0; /* flag for singlethreading
57 * allocator */
58
59 struct purgeable_q purgeable_queues[PURGEABLE_Q_TYPE_MAX];
60
61 decl_lck_mtx_data(,vm_purgeable_queue_lock)
62
63 #define TOKEN_ADD 0x40 /* 0x100 */
64 #define TOKEN_DELETE 0x41 /* 0x104 */
65 #define TOKEN_RIPEN 0x42 /* 0x108 */
66 #define OBJECT_ADD 0x48 /* 0x120 */
67 #define OBJECT_REMOVE 0x49 /* 0x124 */
68 #define OBJECT_PURGE 0x4a /* 0x128 */
69 #define OBJECT_PURGE_ALL 0x4b /* 0x12c */
70
71 static token_idx_t vm_purgeable_token_remove_first(purgeable_q_t queue);
72
73 static void vm_purgeable_stats_helper(vm_purgeable_stat_t *stat, purgeable_q_t queue, int group, task_t target_task);
74
75 #if MACH_ASSERT
76 static void
77 vm_purgeable_token_check_queue(purgeable_q_t queue)
78 {
79 int token_cnt = 0, page_cnt = 0;
80 token_idx_t token = queue->token_q_head;
81 token_idx_t unripe = 0;
82 int our_inactive_count;
83
84 while (token) {
85 if (tokens[token].count != 0) {
86 assert(queue->token_q_unripe);
87 if (unripe == 0) {
88 assert(token == queue->token_q_unripe);
89 unripe = token;
90 }
91 page_cnt += tokens[token].count;
92 }
93 if (tokens[token].next == 0)
94 assert(queue->token_q_tail == token);
95
96 token_cnt++;
97 token = tokens[token].next;
98 }
99
100 if (unripe)
101 assert(queue->token_q_unripe == unripe);
102 assert(token_cnt == queue->debug_count_tokens);
103
104 /* obsolete queue doesn't maintain token counts */
105 if(queue->type != PURGEABLE_Q_TYPE_OBSOLETE)
106 {
107 our_inactive_count = page_cnt + queue->new_pages + token_new_pagecount;
108 assert(our_inactive_count >= 0);
109 assert((uint32_t) our_inactive_count == vm_page_inactive_count - vm_page_cleaned_count);
110 }
111 }
112 #endif
113
114 /*
115 * Add a token. Allocate token queue memory if necessary.
116 * Call with page queue locked.
117 */
118 kern_return_t
119 vm_purgeable_token_add(purgeable_q_t queue)
120 {
121 #if MACH_ASSERT
122 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
123 #endif
124
125 /* new token */
126 token_idx_t token;
127 enum purgeable_q_type i;
128
129 find_available_token:
130
131 if (token_free_idx) { /* unused tokens available */
132 token = token_free_idx;
133 token_free_idx = tokens[token_free_idx].next;
134 } else if (token_init_idx < token_q_max_cnt) { /* lazy token array init */
135 token = token_init_idx;
136 token_init_idx++;
137 } else { /* allocate more memory */
138 /* Wait if another thread is inside the memory alloc section */
139 while(token_q_allocating) {
140 wait_result_t res = lck_mtx_sleep(&vm_page_queue_lock,
141 LCK_SLEEP_DEFAULT,
142 (event_t)&token_q_allocating,
143 THREAD_UNINT);
144 if(res != THREAD_AWAKENED) return KERN_ABORTED;
145 };
146
147 /* Check whether memory is still maxed out */
148 if(token_init_idx < token_q_max_cnt)
149 goto find_available_token;
150
151 /* Still no memory. Allocate some. */
152 token_q_allocating = 1;
153
154 /* Drop page queue lock so we can allocate */
155 vm_page_unlock_queues();
156
157 struct token *new_loc;
158 vm_size_t alloc_size = token_q_cur_size + PAGE_SIZE;
159 kern_return_t result;
160
161 if (alloc_size / sizeof (struct token) > TOKEN_COUNT_MAX) {
162 result = KERN_RESOURCE_SHORTAGE;
163 } else {
164 if (token_q_cur_size) {
165 result = kmem_realloc(kernel_map,
166 (vm_offset_t) tokens,
167 token_q_cur_size,
168 (vm_offset_t *) &new_loc,
169 alloc_size);
170 } else {
171 result = kmem_alloc(kernel_map,
172 (vm_offset_t *) &new_loc,
173 alloc_size);
174 }
175 }
176
177 vm_page_lock_queues();
178
179 if (result) {
180 /* Unblock waiting threads */
181 token_q_allocating = 0;
182 thread_wakeup((event_t)&token_q_allocating);
183 return result;
184 }
185
186 /* If we get here, we allocated new memory. Update pointers and
187 * dealloc old range */
188 struct token *old_tokens=tokens;
189 tokens=new_loc;
190 vm_size_t old_token_q_cur_size=token_q_cur_size;
191 token_q_cur_size=alloc_size;
192 token_q_max_cnt = (token_idx_t) (token_q_cur_size /
193 sizeof(struct token));
194 assert (token_init_idx < token_q_max_cnt); /* We must have a free token now */
195
196 if (old_token_q_cur_size) { /* clean up old mapping */
197 vm_page_unlock_queues();
198 /* kmem_realloc leaves the old region mapped. Get rid of it. */
199 kmem_free(kernel_map, (vm_offset_t)old_tokens, old_token_q_cur_size);
200 vm_page_lock_queues();
201 }
202
203 /* Unblock waiting threads */
204 token_q_allocating = 0;
205 thread_wakeup((event_t)&token_q_allocating);
206
207 goto find_available_token;
208 }
209
210 assert (token);
211
212 /*
213 * the new pagecount we got need to be applied to all queues except
214 * obsolete
215 */
216 for (i = PURGEABLE_Q_TYPE_FIFO; i < PURGEABLE_Q_TYPE_MAX; i++) {
217 int64_t pages = purgeable_queues[i].new_pages += token_new_pagecount;
218 assert(pages >= 0);
219 assert(pages <= TOKEN_COUNT_MAX);
220 purgeable_queues[i].new_pages = (int32_t) pages;
221 assert(purgeable_queues[i].new_pages == pages);
222 }
223 token_new_pagecount = 0;
224
225 /* set token counter value */
226 if (queue->type != PURGEABLE_Q_TYPE_OBSOLETE)
227 tokens[token].count = queue->new_pages;
228 else
229 tokens[token].count = 0; /* all obsolete items are
230 * ripe immediately */
231 queue->new_pages = 0;
232
233 /* put token on token counter list */
234 tokens[token].next = 0;
235 if (queue->token_q_tail == 0) {
236 assert(queue->token_q_head == 0 && queue->token_q_unripe == 0);
237 queue->token_q_head = token;
238 tokens[token].prev = 0;
239 } else {
240 tokens[queue->token_q_tail].next = token;
241 tokens[token].prev = queue->token_q_tail;
242 }
243 if (queue->token_q_unripe == 0) { /* only ripe tokens (token
244 * count == 0) in queue */
245 if (tokens[token].count > 0)
246 queue->token_q_unripe = token; /* first unripe token */
247 else
248 available_for_purge++; /* added a ripe token?
249 * increase available count */
250 }
251 queue->token_q_tail = token;
252
253 #if MACH_ASSERT
254 queue->debug_count_tokens++;
255 /* Check both queues, since we modified the new_pages count on each */
256 vm_purgeable_token_check_queue(&purgeable_queues[PURGEABLE_Q_TYPE_FIFO]);
257 vm_purgeable_token_check_queue(&purgeable_queues[PURGEABLE_Q_TYPE_LIFO]);
258
259 KERNEL_DEBUG_CONSTANT((MACHDBG_CODE(DBG_MACH_VM, TOKEN_ADD)),
260 queue->type,
261 tokens[token].count, /* num pages on token
262 * (last token) */
263 queue->debug_count_tokens,
264 0,
265 0);
266 #endif
267
268 return KERN_SUCCESS;
269 }
270
271 /*
272 * Remove first token from queue and return its index. Add its count to the
273 * count of the next token.
274 * Call with page queue locked.
275 */
276 static token_idx_t
277 vm_purgeable_token_remove_first(purgeable_q_t queue)
278 {
279 #if MACH_ASSERT
280 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
281 #endif
282
283 token_idx_t token;
284 token = queue->token_q_head;
285
286 assert(token);
287
288 if (token) {
289 assert(queue->token_q_tail);
290 if (queue->token_q_head == queue->token_q_unripe) {
291 /* no ripe tokens... must move unripe pointer */
292 queue->token_q_unripe = tokens[token].next;
293 } else {
294 /* we're removing a ripe token. decrease count */
295 available_for_purge--;
296 assert(available_for_purge >= 0);
297 }
298
299 if (queue->token_q_tail == queue->token_q_head)
300 assert(tokens[token].next == 0);
301
302 queue->token_q_head = tokens[token].next;
303 if (queue->token_q_head) {
304 tokens[queue->token_q_head].count += tokens[token].count;
305 tokens[queue->token_q_head].prev = 0;
306 } else {
307 /* currently no other tokens in the queue */
308 /*
309 * the page count must be added to the next newly
310 * created token
311 */
312 queue->new_pages += tokens[token].count;
313 /* if head is zero, tail is too */
314 queue->token_q_tail = 0;
315 }
316
317 #if MACH_ASSERT
318 queue->debug_count_tokens--;
319 vm_purgeable_token_check_queue(queue);
320
321 KERNEL_DEBUG_CONSTANT((MACHDBG_CODE(DBG_MACH_VM, TOKEN_DELETE)),
322 queue->type,
323 tokens[queue->token_q_head].count, /* num pages on new
324 * first token */
325 token_new_pagecount, /* num pages waiting for
326 * next token */
327 available_for_purge,
328 0);
329 #endif
330 }
331 return token;
332 }
333
334 static token_idx_t
335 vm_purgeable_token_remove_last(purgeable_q_t queue)
336 {
337 #if MACH_ASSERT
338 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
339 #endif
340
341 token_idx_t token;
342 token = queue->token_q_tail;
343
344 assert(token);
345
346 if (token) {
347 assert(queue->token_q_head);
348
349 if (queue->token_q_tail == queue->token_q_head)
350 assert(tokens[token].next == 0);
351
352 if (queue->token_q_unripe == 0) {
353 /* we're removing a ripe token. decrease count */
354 available_for_purge--;
355 assert(available_for_purge >= 0);
356 } else if (queue->token_q_unripe == token) {
357 /* we're removing the only unripe token */
358 queue->token_q_unripe = 0;
359 }
360
361 if (token == queue->token_q_head) {
362 /* token is the last one in the queue */
363 queue->token_q_head = 0;
364 queue->token_q_tail = 0;
365 } else {
366 token_idx_t new_tail;
367
368 new_tail = tokens[token].prev;
369
370 assert(new_tail);
371 assert(tokens[new_tail].next == token);
372
373 queue->token_q_tail = new_tail;
374 tokens[new_tail].next = 0;
375 }
376
377 queue->new_pages += tokens[token].count;
378
379 #if MACH_ASSERT
380 queue->debug_count_tokens--;
381 vm_purgeable_token_check_queue(queue);
382
383 KERNEL_DEBUG_CONSTANT((MACHDBG_CODE(DBG_MACH_VM, TOKEN_DELETE)),
384 queue->type,
385 tokens[queue->token_q_head].count, /* num pages on new
386 * first token */
387 token_new_pagecount, /* num pages waiting for
388 * next token */
389 available_for_purge,
390 0);
391 #endif
392 }
393 return token;
394 }
395
396 /*
397 * Delete first token from queue. Return token to token queue.
398 * Call with page queue locked.
399 */
400 void
401 vm_purgeable_token_delete_first(purgeable_q_t queue)
402 {
403 #if MACH_ASSERT
404 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
405 #endif
406 token_idx_t token = vm_purgeable_token_remove_first(queue);
407
408 if (token) {
409 /* stick removed token on free queue */
410 tokens[token].next = token_free_idx;
411 tokens[token].prev = 0;
412 token_free_idx = token;
413 }
414 }
415
416 void
417 vm_purgeable_token_delete_last(purgeable_q_t queue)
418 {
419 #if MACH_ASSERT
420 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
421 #endif
422 token_idx_t token = vm_purgeable_token_remove_last(queue);
423
424 if (token) {
425 /* stick removed token on free queue */
426 tokens[token].next = token_free_idx;
427 tokens[token].prev = 0;
428 token_free_idx = token;
429 }
430 }
431
432
433 /* Call with page queue locked. */
434 void
435 vm_purgeable_q_advance_all()
436 {
437 #if MACH_ASSERT
438 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
439 #endif
440
441 /* check queue counters - if they get really large, scale them back.
442 * They tend to get that large when there is no purgeable queue action */
443 int i;
444 if(token_new_pagecount > (TOKEN_NEW_PAGECOUNT_MAX >> 1)) /* a system idling years might get there */
445 {
446 for (i = PURGEABLE_Q_TYPE_FIFO; i < PURGEABLE_Q_TYPE_MAX; i++) {
447 int64_t pages = purgeable_queues[i].new_pages += token_new_pagecount;
448 assert(pages >= 0);
449 assert(pages <= TOKEN_COUNT_MAX);
450 purgeable_queues[i].new_pages = (int32_t) pages;
451 assert(purgeable_queues[i].new_pages == pages);
452 }
453 token_new_pagecount = 0;
454 }
455
456 /*
457 * Decrement token counters. A token counter can be zero, this means the
458 * object is ripe to be purged. It is not purged immediately, because that
459 * could cause several objects to be purged even if purging one would satisfy
460 * the memory needs. Instead, the pageout thread purges one after the other
461 * by calling vm_purgeable_object_purge_one and then rechecking the memory
462 * balance.
463 *
464 * No need to advance obsolete queue - all items are ripe there,
465 * always
466 */
467 for (i = PURGEABLE_Q_TYPE_FIFO; i < PURGEABLE_Q_TYPE_MAX; i++) {
468 purgeable_q_t queue = &purgeable_queues[i];
469 uint32_t num_pages = 1;
470
471 /* Iterate over tokens as long as there are unripe tokens. */
472 while (queue->token_q_unripe) {
473 if (tokens[queue->token_q_unripe].count && num_pages)
474 {
475 tokens[queue->token_q_unripe].count -= 1;
476 num_pages -= 1;
477 }
478
479 if (tokens[queue->token_q_unripe].count == 0) {
480 queue->token_q_unripe = tokens[queue->token_q_unripe].next;
481 available_for_purge++;
482 KERNEL_DEBUG_CONSTANT((MACHDBG_CODE(DBG_MACH_VM, TOKEN_RIPEN)),
483 queue->type,
484 tokens[queue->token_q_head].count, /* num pages on new
485 * first token */
486 0,
487 available_for_purge,
488 0);
489 continue; /* One token ripened. Make sure to
490 * check the next. */
491 }
492 if (num_pages == 0)
493 break; /* Current token not ripe and no more pages.
494 * Work done. */
495 }
496
497 /*
498 * if there are no unripe tokens in the queue, decrement the
499 * new_pages counter instead new_pages can be negative, but must be
500 * canceled out by token_new_pagecount -- since inactive queue as a
501 * whole always contains a nonnegative number of pages
502 */
503 if (!queue->token_q_unripe) {
504 queue->new_pages -= num_pages;
505 assert((int32_t) token_new_pagecount + queue->new_pages >= 0);
506 }
507 #if MACH_ASSERT
508 vm_purgeable_token_check_queue(queue);
509 #endif
510 }
511 }
512
513 /*
514 * grab any ripe object and purge it obsolete queue first. then, go through
515 * each volatile group. Select a queue with a ripe token.
516 * Start with first group (0)
517 * 1. Look at queue. Is there an object?
518 * Yes - purge it. Remove token.
519 * No - check other queue. Is there an object?
520 * No - increment group, then go to (1)
521 * Yes - purge it. Remove token. If there is no ripe token, remove ripe
522 * token from other queue and migrate unripe token from this
523 * queue to other queue.
524 * Call with page queue locked.
525 */
526 static void
527 vm_purgeable_token_remove_ripe(purgeable_q_t queue)
528 {
529 #if MACH_ASSERT
530 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
531 #endif
532 assert(queue->token_q_head && tokens[queue->token_q_head].count == 0);
533 /* return token to free list. advance token list. */
534 token_idx_t new_head = tokens[queue->token_q_head].next;
535 tokens[queue->token_q_head].next = token_free_idx;
536 tokens[queue->token_q_head].prev = 0;
537 token_free_idx = queue->token_q_head;
538 queue->token_q_head = new_head;
539 tokens[new_head].prev = 0;
540 if (new_head == 0)
541 queue->token_q_tail = 0;
542
543 #if MACH_ASSERT
544 queue->debug_count_tokens--;
545 vm_purgeable_token_check_queue(queue);
546 #endif
547
548 available_for_purge--;
549 assert(available_for_purge >= 0);
550 }
551
552 /*
553 * Delete a ripe token from the given queue. If there are no ripe tokens on
554 * that queue, delete a ripe token from queue2, and migrate an unripe token
555 * from queue to queue2
556 * Call with page queue locked.
557 */
558 static void
559 vm_purgeable_token_choose_and_delete_ripe(purgeable_q_t queue, purgeable_q_t queue2)
560 {
561 #if MACH_ASSERT
562 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
563 #endif
564 assert(queue->token_q_head);
565
566 if (tokens[queue->token_q_head].count == 0) {
567 /* This queue has a ripe token. Remove. */
568 vm_purgeable_token_remove_ripe(queue);
569 } else {
570 assert(queue2);
571 /*
572 * queue2 must have a ripe token. Remove, and migrate one
573 * from queue to queue2.
574 */
575 vm_purgeable_token_remove_ripe(queue2);
576 /* migrate unripe token */
577 token_idx_t token;
578 token_cnt_t count;
579
580 /* remove token from queue1 */
581 assert(queue->token_q_unripe == queue->token_q_head); /* queue1 had no unripe
582 * tokens, remember? */
583 token = vm_purgeable_token_remove_first(queue);
584 assert(token);
585
586 count = tokens[token].count;
587
588 /* migrate to queue2 */
589 /* go to migration target loc */
590
591 token_idx_t token_to_insert_before = queue2->token_q_head, token_to_insert_after;
592
593 while (token_to_insert_before != 0 && count > tokens[token_to_insert_before].count) {
594 count -= tokens[token_to_insert_before].count;
595 token_to_insert_before = tokens[token_to_insert_before].next;
596 }
597
598 /* token_to_insert_before is now set correctly */
599
600 /* should the inserted token become the first unripe token? */
601 if ((token_to_insert_before == queue2->token_q_unripe) || (queue2->token_q_unripe == 0))
602 queue2->token_q_unripe = token; /* if so, must update unripe pointer */
603
604 /*
605 * insert token.
606 * if inserting at end, reduce new_pages by that value;
607 * otherwise, reduce counter of next token
608 */
609
610 tokens[token].count = count;
611
612 if (token_to_insert_before != 0) {
613 token_to_insert_after = tokens[token_to_insert_before].prev;
614
615 tokens[token].next = token_to_insert_before;
616 tokens[token_to_insert_before].prev = token;
617
618 assert(tokens[token_to_insert_before].count >= count);
619 tokens[token_to_insert_before].count -= count;
620 } else {
621 /* if we ran off the end of the list, the token to insert after is the tail */
622 token_to_insert_after = queue2->token_q_tail;
623
624 tokens[token].next = 0;
625 queue2->token_q_tail = token;
626
627 assert(queue2->new_pages >= (int32_t) count);
628 queue2->new_pages -= count;
629 }
630
631 if (token_to_insert_after != 0) {
632 tokens[token].prev = token_to_insert_after;
633 tokens[token_to_insert_after].next = token;
634 } else {
635 /* is this case possible? */
636 tokens[token].prev = 0;
637 queue2->token_q_head = token;
638 }
639
640 #if MACH_ASSERT
641 queue2->debug_count_tokens++;
642 vm_purgeable_token_check_queue(queue2);
643 #endif
644 }
645 }
646
647 /* Find an object that can be locked. Returns locked object. */
648 /* Call with purgeable queue locked. */
649 static vm_object_t
650 vm_purgeable_object_find_and_lock(
651 purgeable_q_t queue,
652 int group,
653 boolean_t pick_ripe)
654 {
655 vm_object_t object, best_object;
656 int object_task_importance;
657 int best_object_task_importance;
658 int best_object_skipped;
659 int num_objects_skipped;
660 task_t owner;
661
662 best_object = VM_OBJECT_NULL;
663 best_object_task_importance = INT_MAX;
664
665 lck_mtx_assert(&vm_purgeable_queue_lock, LCK_MTX_ASSERT_OWNED);
666 /*
667 * Usually we would pick the first element from a queue. However, we
668 * might not be able to get a lock on it, in which case we try the
669 * remaining elements in order.
670 */
671
672 num_objects_skipped = -1;
673 for (object = (vm_object_t) queue_first(&queue->objq[group]);
674 !queue_end(&queue->objq[group], (queue_entry_t) object);
675 object = (vm_object_t) queue_next(&object->objq),
676 num_objects_skipped++) {
677
678 if (pick_ripe &&
679 ! object->purgeable_when_ripe) {
680 /* we want an object that has a ripe token */
681 continue;
682 }
683
684 object_task_importance = 0;
685 owner = object->vo_purgeable_owner;
686 if (owner) {
687 object_task_importance = task_importance_estimate(owner);
688 }
689 if (object_task_importance < best_object_task_importance) {
690 if (vm_object_lock_try(object)) {
691 if (best_object != VM_OBJECT_NULL) {
692 /* forget about previous best object */
693 vm_object_unlock(best_object);
694 }
695 best_object = object;
696 best_object_task_importance = object_task_importance;
697 best_object_skipped = num_objects_skipped;
698 if (best_object_task_importance == 0) {
699 /* can't get any better: stop looking */
700 break;
701 }
702 }
703 }
704 }
705
706 if (best_object) {
707 /* Locked. Great. We'll take it. Remove and return. */
708 // printf("FOUND PURGEABLE object %p skipped %d\n", object, num_objects_skipped);
709
710 /* clear ownership when dequeueing purgeable object */
711 owner = best_object->vo_purgeable_owner;
712 if (owner) {
713 assert(owner->task_volatile_objects > 0);
714 OSAddAtomic(-1, &owner->task_volatile_objects);
715 best_object->vo_purgeable_owner = NULL;
716 }
717
718 queue_remove(&queue->objq[group], best_object,
719 vm_object_t, objq);
720 best_object->purgeable_queue_type = PURGEABLE_Q_TYPE_MAX;
721 best_object->purgeable_queue_group = 0;
722 best_object->objq.next = NULL;
723 best_object->objq.prev = NULL;
724 #if MACH_ASSERT
725 queue->debug_count_objects--;
726 #endif
727 return best_object;
728 }
729
730 return 0;
731 }
732
733 /* Can be called without holding locks */
734 void
735 vm_purgeable_object_purge_all(void)
736 {
737 enum purgeable_q_type i;
738 int group;
739 vm_object_t object;
740 unsigned int purged_count;
741 uint32_t collisions;
742
743 purged_count = 0;
744 collisions = 0;
745
746 restart:
747 lck_mtx_lock(&vm_purgeable_queue_lock);
748 /* Cycle through all queues */
749 for (i = PURGEABLE_Q_TYPE_OBSOLETE; i < PURGEABLE_Q_TYPE_MAX; i++) {
750 purgeable_q_t queue;
751
752 queue = &purgeable_queues[i];
753
754 /*
755 * Look through all groups, starting from the lowest. If
756 * we find an object in that group, try to lock it (this can
757 * fail). If locking is successful, we can drop the queue
758 * lock, remove a token and then purge the object.
759 */
760 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
761 while (!queue_empty(&queue->objq[group])) {
762 object = vm_purgeable_object_find_and_lock(queue, group, FALSE);
763 if (object == VM_OBJECT_NULL) {
764 lck_mtx_unlock(&vm_purgeable_queue_lock);
765 mutex_pause(collisions++);
766 goto restart;
767 }
768
769 lck_mtx_unlock(&vm_purgeable_queue_lock);
770
771 /* Lock the page queue here so we don't hold it
772 * over the whole, legthy operation */
773 if (object->purgeable_when_ripe) {
774 vm_page_lock_queues();
775 vm_purgeable_token_remove_first(queue);
776 vm_page_unlock_queues();
777 }
778
779 assert(object->purgable == VM_PURGABLE_VOLATILE);
780 (void) vm_object_purge(object);
781 vm_object_unlock(object);
782 purged_count++;
783 goto restart;
784 }
785 assert(queue->debug_count_objects >= 0);
786 }
787 }
788 KERNEL_DEBUG_CONSTANT((MACHDBG_CODE(DBG_MACH_VM, OBJECT_PURGE_ALL)),
789 purged_count, /* # of purged objects */
790 0,
791 available_for_purge,
792 0,
793 0);
794 lck_mtx_unlock(&vm_purgeable_queue_lock);
795 return;
796 }
797
798 boolean_t
799 vm_purgeable_object_purge_one_unlocked(
800 int force_purge_below_group)
801 {
802 boolean_t retval;
803
804 vm_page_lock_queues();
805 retval = vm_purgeable_object_purge_one(force_purge_below_group);
806 vm_page_unlock_queues();
807
808 return retval;
809 }
810
811 boolean_t
812 vm_purgeable_object_purge_one(
813 int force_purge_below_group)
814 {
815 enum purgeable_q_type i;
816 int group;
817 vm_object_t object = 0;
818 purgeable_q_t queue, queue2;
819 boolean_t forced_purge;
820
821 /* Need the page queue lock since we'll be changing the token queue. */
822 #if MACH_ASSERT
823 lck_mtx_assert(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
824 #endif
825 lck_mtx_lock(&vm_purgeable_queue_lock);
826
827 /* Cycle through all queues */
828 for (i = PURGEABLE_Q_TYPE_OBSOLETE; i < PURGEABLE_Q_TYPE_MAX; i++) {
829 queue = &purgeable_queues[i];
830
831 if (force_purge_below_group == 0) {
832 /*
833 * Are there any ripe tokens on this queue? If yes,
834 * we'll find an object to purge there
835 */
836 if (!queue->token_q_head) {
837 /* no token: look at next purgeable queue */
838 continue;
839 }
840
841 if (tokens[queue->token_q_head].count != 0) {
842 /* no ripe token: next queue */
843 continue;
844 }
845 }
846
847 /*
848 * Now look through all groups, starting from the lowest. If
849 * we find an object in that group, try to lock it (this can
850 * fail). If locking is successful, we can drop the queue
851 * lock, remove a token and then purge the object.
852 */
853 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
854 if (!queue->token_q_head ||
855 tokens[queue->token_q_head].count != 0) {
856 /* no tokens or no ripe tokens */
857
858 if (group >= force_purge_below_group) {
859 /* no more groups to force-purge */
860 break;
861 }
862
863 /*
864 * Try and purge an object in this group
865 * even though no tokens are ripe.
866 */
867 if (!queue_empty(&queue->objq[group]) &&
868 (object = vm_purgeable_object_find_and_lock(queue, group, FALSE))) {
869 lck_mtx_unlock(&vm_purgeable_queue_lock);
870 if (object->purgeable_when_ripe) {
871 vm_purgeable_token_delete_first(queue);
872 }
873 forced_purge = TRUE;
874 goto purge_now;
875 }
876
877 /* nothing to purge in this group: next group */
878 continue;
879 }
880 if (!queue_empty(&queue->objq[group]) &&
881 (object = vm_purgeable_object_find_and_lock(queue, group, TRUE))) {
882 lck_mtx_unlock(&vm_purgeable_queue_lock);
883 if (object->purgeable_when_ripe) {
884 vm_purgeable_token_choose_and_delete_ripe(queue, 0);
885 }
886 forced_purge = FALSE;
887 goto purge_now;
888 }
889 if (i != PURGEABLE_Q_TYPE_OBSOLETE) {
890 /* This is the token migration case, and it works between
891 * FIFO and LIFO only */
892 queue2 = &purgeable_queues[i != PURGEABLE_Q_TYPE_FIFO ?
893 PURGEABLE_Q_TYPE_FIFO :
894 PURGEABLE_Q_TYPE_LIFO];
895
896 if (!queue_empty(&queue2->objq[group]) &&
897 (object = vm_purgeable_object_find_and_lock(queue2, group, TRUE))) {
898 lck_mtx_unlock(&vm_purgeable_queue_lock);
899 if (object->purgeable_when_ripe) {
900 vm_purgeable_token_choose_and_delete_ripe(queue2, queue);
901 }
902 forced_purge = FALSE;
903 goto purge_now;
904 }
905 }
906 assert(queue->debug_count_objects >= 0);
907 }
908 }
909 /*
910 * because we have to do a try_lock on the objects which could fail,
911 * we could end up with no object to purge at this time, even though
912 * we have objects in a purgeable state
913 */
914 lck_mtx_unlock(&vm_purgeable_queue_lock);
915 return FALSE;
916
917 purge_now:
918
919 assert(object);
920 assert(object->purgable == VM_PURGABLE_VOLATILE);
921 vm_page_unlock_queues(); /* Unlock for call to vm_object_purge() */
922 // printf("%sPURGING object %p task %p importance %d queue %d group %d force_purge_below_group %d memorystatus_vm_pressure_level %d\n", forced_purge ? "FORCED " : "", object, object->vo_purgeable_owner, task_importance_estimate(object->vo_purgeable_owner), i, group, force_purge_below_group, memorystatus_vm_pressure_level);
923 (void) vm_object_purge(object);
924 vm_object_unlock(object);
925 vm_page_lock_queues();
926
927 KERNEL_DEBUG_CONSTANT((MACHDBG_CODE(DBG_MACH_VM, OBJECT_PURGE)),
928 object, /* purged object */
929 0,
930 available_for_purge,
931 0,
932 0);
933
934 return TRUE;
935 }
936
937 /* Called with object lock held */
938 void
939 vm_purgeable_object_add(vm_object_t object, purgeable_q_t queue, int group)
940 {
941 task_t owner;
942
943 vm_object_lock_assert_exclusive(object);
944 lck_mtx_lock(&vm_purgeable_queue_lock);
945
946 if (queue->type == PURGEABLE_Q_TYPE_OBSOLETE)
947 group = 0;
948
949 if (queue->type != PURGEABLE_Q_TYPE_LIFO) /* fifo and obsolete are
950 * fifo-queued */
951 queue_enter(&queue->objq[group], object, vm_object_t, objq); /* last to die */
952 else
953 queue_enter_first(&queue->objq[group], object, vm_object_t, objq); /* first to die */
954
955 object->purgeable_queue_type = queue->type;
956 object->purgeable_queue_group = group;
957
958 /* set ownership when enqueueing purgeable object */
959 assert(object->vo_purgeable_owner == NULL);
960 owner = current_task();
961 if (current_task() != kernel_task) {
962 OSAddAtomic(+1, &owner->task_volatile_objects);
963 assert(owner->task_volatile_objects > 0);
964 object->vo_purgeable_owner = owner;
965 }
966
967 #if MACH_ASSERT
968 queue->debug_count_objects++;
969 KERNEL_DEBUG_CONSTANT((MACHDBG_CODE(DBG_MACH_VM, OBJECT_ADD)),
970 0,
971 tokens[queue->token_q_head].count,
972 queue->type,
973 group,
974 0);
975 #endif
976
977 lck_mtx_unlock(&vm_purgeable_queue_lock);
978 }
979
980 /* Look for object. If found, remove from purgeable queue. */
981 /* Called with object lock held */
982 purgeable_q_t
983 vm_purgeable_object_remove(vm_object_t object)
984 {
985 int group;
986 task_t owner;
987 enum purgeable_q_type type;
988 purgeable_q_t queue;
989
990 vm_object_lock_assert_exclusive(object);
991
992 type = object->purgeable_queue_type;
993 group = object->purgeable_queue_group;
994
995 if (type == PURGEABLE_Q_TYPE_MAX) {
996 if (object->objq.prev || object->objq.next)
997 panic("unmarked object on purgeable q");
998
999 return NULL;
1000 } else if (!(object->objq.prev && object->objq.next))
1001 panic("marked object not on purgeable q");
1002
1003 lck_mtx_lock(&vm_purgeable_queue_lock);
1004
1005 queue = &purgeable_queues[type];
1006
1007 /* clear ownership when dequeueing purgeable object */
1008 owner = object->vo_purgeable_owner;
1009 if (owner) {
1010 assert(owner->task_volatile_objects > 0);
1011 OSAddAtomic(-1, &owner->task_volatile_objects);
1012 object->vo_purgeable_owner = NULL;
1013 }
1014
1015 queue_remove(&queue->objq[group], object, vm_object_t, objq);
1016
1017 #if MACH_ASSERT
1018 queue->debug_count_objects--;
1019 KERNEL_DEBUG_CONSTANT((MACHDBG_CODE(DBG_MACH_VM, OBJECT_REMOVE)),
1020 0,
1021 tokens[queue->token_q_head].count,
1022 queue->type,
1023 group,
1024 0);
1025 #endif
1026
1027 lck_mtx_unlock(&vm_purgeable_queue_lock);
1028
1029 object->purgeable_queue_type = PURGEABLE_Q_TYPE_MAX;
1030 object->purgeable_queue_group = 0;
1031
1032 object->objq.next = NULL;
1033 object->objq.prev = NULL;
1034
1035 return &purgeable_queues[type];
1036 }
1037
1038 void
1039 vm_purgeable_stats_helper(vm_purgeable_stat_t *stat, purgeable_q_t queue, int group, task_t target_task)
1040 {
1041 lck_mtx_assert(&vm_purgeable_queue_lock, LCK_MTX_ASSERT_OWNED);
1042
1043 stat->count = stat->size = 0;
1044 vm_object_t object;
1045 for (object = (vm_object_t) queue_first(&queue->objq[group]);
1046 !queue_end(&queue->objq[group], (queue_entry_t) object);
1047 object = (vm_object_t) queue_next(&object->objq)) {
1048 if (!target_task || object->vo_purgeable_owner == target_task) {
1049 stat->count++;
1050 stat->size += (object->resident_page_count * PAGE_SIZE);
1051 }
1052 }
1053 return;
1054 }
1055
1056 void
1057 vm_purgeable_stats(vm_purgeable_info_t info, task_t target_task)
1058 {
1059 purgeable_q_t queue;
1060 int group;
1061
1062 lck_mtx_lock(&vm_purgeable_queue_lock);
1063
1064 /* Populate fifo_data */
1065 queue = &purgeable_queues[PURGEABLE_Q_TYPE_FIFO];
1066 for (group = 0; group < NUM_VOLATILE_GROUPS; group++)
1067 vm_purgeable_stats_helper(&(info->fifo_data[group]), queue, group, target_task);
1068
1069 /* Populate lifo_data */
1070 queue = &purgeable_queues[PURGEABLE_Q_TYPE_LIFO];
1071 for (group = 0; group < NUM_VOLATILE_GROUPS; group++)
1072 vm_purgeable_stats_helper(&(info->lifo_data[group]), queue, group, target_task);
1073
1074 /* Populate obsolete data */
1075 queue = &purgeable_queues[PURGEABLE_Q_TYPE_OBSOLETE];
1076 vm_purgeable_stats_helper(&(info->obsolete_data), queue, 0, target_task);
1077
1078 lck_mtx_unlock(&vm_purgeable_queue_lock);
1079 return;
1080 }
1081
1082
1083 static void
1084 vm_purgeable_queue_disown(
1085 purgeable_q_t queue,
1086 int group,
1087 task_t task)
1088 {
1089 vm_object_t object;
1090 int num_objects;
1091
1092 lck_mtx_assert(&vm_purgeable_queue_lock, LCK_MTX_ASSERT_OWNED);
1093
1094 num_objects = 0;
1095 for (object = (vm_object_t) queue_first(&queue->objq[group]);
1096 !queue_end(&queue->objq[group], (queue_entry_t) object);
1097 object = (vm_object_t) queue_next(&object->objq)) {
1098 if (object->vo_purgeable_owner == task) {
1099 object->vo_purgeable_owner = NULL;
1100 num_objects++;
1101 }
1102 }
1103 assert(task->task_volatile_objects >= num_objects);
1104 OSAddAtomic(-num_objects, &task->task_volatile_objects);
1105 return;
1106 }
1107
1108 void
1109 vm_purgeable_disown(
1110 task_t task)
1111 {
1112 purgeable_q_t queue;
1113 int group;
1114
1115 if (task == NULL) {
1116 return;
1117 }
1118
1119 lck_mtx_lock(&vm_purgeable_queue_lock);
1120
1121 queue = &purgeable_queues[PURGEABLE_Q_TYPE_OBSOLETE];
1122 vm_purgeable_queue_disown(queue, 0, task);
1123
1124 queue = &purgeable_queues[PURGEABLE_Q_TYPE_FIFO];
1125 for (group = 0; group < NUM_VOLATILE_GROUPS; group++)
1126 vm_purgeable_queue_disown(queue, group, task);
1127
1128 queue = &purgeable_queues[PURGEABLE_Q_TYPE_LIFO];
1129 for (group = 0; group < NUM_VOLATILE_GROUPS; group++)
1130 vm_purgeable_queue_disown(queue, group, task);
1131
1132 lck_mtx_unlock(&vm_purgeable_queue_lock);
1133 }