1 /*
2 * Copyright (c) 2019-2020 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 <kern/sched_prim.h>
25 #include <kern/ledger.h>
26 #include <kern/policy_internal.h>
27
28 #include <libkern/OSDebug.h>
29
30 #include <mach/mach_types.h>
31
32 #include <machine/limits.h>
33
34 #include <os/hash.h>
35
36 #include <vm/vm_compressor_pager_xnu.h>
37 #include <vm/vm_kern_xnu.h> /* kmem_alloc */
38 #include <vm/vm_page_internal.h>
39 #include <vm/vm_pageout_xnu.h>
40 #include <vm/vm_protos_internal.h>
41 #include <vm/vm_purgeable_internal.h>
42 #include <vm/vm_object_internal.h>
43
44 #include <sys/kdebug.h>
45
46 /*
47 * LOCK ORDERING for task-owned purgeable objects
48 *
49 * Whenever we need to hold multiple locks while adding to, removing from,
50 * or scanning a task's task_objq list of VM objects it owns, locks should
51 * be taken in this order:
52 *
53 * VM object ==> vm_purgeable_queue_lock ==> owner_task->task_objq_lock
54 *
55 * If one needs to acquire the VM object lock after any of the other 2 locks,
56 * one needs to use vm_object_lock_try() and, if that fails, release the
57 * other locks and retake them all in the correct order.
58 */
59
60 extern vm_pressure_level_t memorystatus_vm_pressure_level;
61
62 struct token {
63 token_cnt_t count;
64 token_idx_t prev;
65 token_idx_t next;
66 };
67
68 struct token *tokens;
69 token_idx_t token_q_max_cnt = 0;
70 vm_size_t token_q_cur_size = 0;
71
72 token_idx_t token_free_idx = 0; /* head of free queue */
73 token_idx_t token_init_idx = 1; /* token 0 is reserved!! */
74 int32_t token_new_pagecount = 0; /* count of pages that will
75 * be added onto token queue */
76
77 int available_for_purge = 0; /* increase when ripe token
78 * added, decrease when ripe
79 * token removed.
80 * protected by page_queue_lock
81 */
82
83 static int token_q_allocating = 0; /* flag for singlethreading
84 * allocator */
85
86 struct purgeable_q purgeable_queues[PURGEABLE_Q_TYPE_MAX];
87 queue_head_t purgeable_nonvolatile_queue;
88 int purgeable_nonvolatile_count;
89
90 decl_lck_mtx_data(, vm_purgeable_queue_lock);
91
92 static token_idx_t vm_purgeable_token_remove_first(purgeable_q_t queue);
93
94 static void vm_purgeable_stats_helper(vm_purgeable_stat_t *stat, purgeable_q_t queue, int group, task_t target_task);
95
96
97 #if MACH_ASSERT
98 static void
vm_purgeable_token_check_queue(purgeable_q_t queue)99 vm_purgeable_token_check_queue(purgeable_q_t queue)
100 {
101 int token_cnt = 0, page_cnt = 0;
102 token_idx_t token = queue->token_q_head;
103 token_idx_t unripe = 0;
104 int our_inactive_count;
105
106
107 #if DEVELOPMENT
108 static int lightweight_check = 0;
109
110 /*
111 * Due to performance impact, perform this check less frequently on DEVELOPMENT kernels.
112 * Checking the queue scales linearly with its length, so we compensate by
113 * by performing this check less frequently as the queue grows.
114 */
115 if (lightweight_check++ < (100 + queue->debug_count_tokens / 512)) {
116 return;
117 }
118
119 lightweight_check = 0;
120 #endif
121
122 while (token) {
123 if (tokens[token].count != 0) {
124 assert(queue->token_q_unripe);
125 if (unripe == 0) {
126 assert(token == queue->token_q_unripe);
127 unripe = token;
128 }
129 page_cnt += tokens[token].count;
130 }
131 if (tokens[token].next == 0) {
132 assert(queue->token_q_tail == token);
133 }
134
135 token_cnt++;
136 token = tokens[token].next;
137 }
138
139 if (unripe) {
140 assert(queue->token_q_unripe == unripe);
141 }
142 assert(token_cnt == queue->debug_count_tokens);
143
144 /* obsolete queue doesn't maintain token counts */
145 if (queue->type != PURGEABLE_Q_TYPE_OBSOLETE) {
146 our_inactive_count = page_cnt + queue->new_pages + token_new_pagecount;
147 assert(our_inactive_count >= 0);
148 assert((uint32_t) our_inactive_count == vm_page_inactive_count - vm_page_cleaned_count);
149 }
150 }
151 #endif
152
153 /*
154 * Add a token. Allocate token queue memory if necessary.
155 * Call with page queue locked.
156 */
157 kern_return_t
vm_purgeable_token_add(purgeable_q_t queue)158 vm_purgeable_token_add(purgeable_q_t queue)
159 {
160 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
161
162 /* new token */
163 token_idx_t token;
164 enum purgeable_q_type i;
165
166 find_available_token:
167
168 if (token_free_idx) { /* unused tokens available */
169 token = token_free_idx;
170 token_free_idx = tokens[token_free_idx].next;
171 } else if (token_init_idx < token_q_max_cnt) { /* lazy token array init */
172 token = token_init_idx;
173 token_init_idx++;
174 } else { /* allocate more memory */
175 /* Wait if another thread is inside the memory alloc section */
176 while (token_q_allocating) {
177 wait_result_t res = lck_mtx_sleep(&vm_page_queue_lock,
178 LCK_SLEEP_DEFAULT,
179 (event_t)&token_q_allocating,
180 THREAD_UNINT);
181 if (res != THREAD_AWAKENED) {
182 return KERN_ABORTED;
183 }
184 }
185
186 /* Check whether memory is still maxed out */
187 if (token_init_idx < token_q_max_cnt) {
188 goto find_available_token;
189 }
190
191 /* Still no memory. Allocate some. */
192 token_q_allocating = 1;
193
194 /* Drop page queue lock so we can allocate */
195 vm_page_unlock_queues();
196
197 vm_size_t alloc_size = token_q_cur_size + PAGE_SIZE;
198 kmem_return_t kmr = { };
199 kmem_guard_t guard = {
200 .kmg_atomic = true,
201 .kmg_tag = VM_KERN_MEMORY_OSFMK,
202 .kmg_context = os_hash_kernel_pointer(&tokens),
203 };
204
205 if (alloc_size <= TOKEN_COUNT_MAX * sizeof(struct token)) {
206 kmr = kmem_realloc_guard(kernel_map,
207 (vm_offset_t)tokens, token_q_cur_size, alloc_size,
208 KMR_ZERO | KMR_DATA, guard);
209 }
210
211 vm_page_lock_queues();
212
213 if (kmr.kmr_ptr == NULL) {
214 /* Unblock waiting threads */
215 token_q_allocating = 0;
216 thread_wakeup((event_t)&token_q_allocating);
217 return KERN_RESOURCE_SHORTAGE;
218 }
219
220 /* If we get here, we allocated new memory. Update pointers and
221 * dealloc old range */
222 struct token *old_tokens = tokens;
223 vm_size_t old_token_q_cur_size = token_q_cur_size;
224
225 tokens = kmr.kmr_ptr;
226 token_q_cur_size = alloc_size;
227 token_q_max_cnt = (token_idx_t) (token_q_cur_size /
228 sizeof(struct token));
229 assert(token_init_idx < token_q_max_cnt); /* We must have a free token now */
230
231 /* kmem_realloc_guard() might leave the old region mapped. */
232 if (kmem_realloc_should_free((vm_offset_t)old_tokens, kmr)) {
233 vm_page_unlock_queues();
234 kmem_free_guard(kernel_map, (vm_offset_t)old_tokens,
235 old_token_q_cur_size, KMF_NONE, guard);
236 vm_page_lock_queues();
237 }
238
239 /* Unblock waiting threads */
240 token_q_allocating = 0;
241 thread_wakeup((event_t)&token_q_allocating);
242
243 goto find_available_token;
244 }
245
246 assert(token);
247
248 /*
249 * the new pagecount we got need to be applied to all queues except
250 * obsolete
251 */
252 for (i = PURGEABLE_Q_TYPE_FIFO; i < PURGEABLE_Q_TYPE_MAX; i++) {
253 int64_t pages = purgeable_queues[i].new_pages += token_new_pagecount;
254 assert(pages >= 0);
255 assert(pages <= TOKEN_COUNT_MAX);
256 purgeable_queues[i].new_pages = (int32_t) pages;
257 assert(purgeable_queues[i].new_pages == pages);
258 }
259 token_new_pagecount = 0;
260
261 /* set token counter value */
262 if (queue->type != PURGEABLE_Q_TYPE_OBSOLETE) {
263 tokens[token].count = queue->new_pages;
264 } else {
265 tokens[token].count = 0; /* all obsolete items are
266 * ripe immediately */
267 }
268 queue->new_pages = 0;
269
270 /* put token on token counter list */
271 tokens[token].next = 0;
272 if (queue->token_q_tail == 0) {
273 assert(queue->token_q_head == 0 && queue->token_q_unripe == 0);
274 queue->token_q_head = token;
275 tokens[token].prev = 0;
276 } else {
277 tokens[queue->token_q_tail].next = token;
278 tokens[token].prev = queue->token_q_tail;
279 }
280 if (queue->token_q_unripe == 0) { /* only ripe tokens (token
281 * count == 0) in queue */
282 if (tokens[token].count > 0) {
283 queue->token_q_unripe = token; /* first unripe token */
284 } else {
285 available_for_purge++; /* added a ripe token?
286 * increase available count */
287 }
288 }
289 queue->token_q_tail = token;
290
291 #if MACH_ASSERT
292 queue->debug_count_tokens++;
293 /* Check both queues, since we modified the new_pages count on each */
294 vm_purgeable_token_check_queue(&purgeable_queues[PURGEABLE_Q_TYPE_FIFO]);
295 vm_purgeable_token_check_queue(&purgeable_queues[PURGEABLE_Q_TYPE_LIFO]);
296
297 KDBG((VMDBG_CODE(DBG_VM_PURGEABLE_TOKEN_ADD)) | DBG_FUNC_NONE,
298 queue->type,
299 tokens[token].count, /* num pages on token (last token) */
300 queue->debug_count_tokens);
301 #endif
302
303 return KERN_SUCCESS;
304 }
305
306 /*
307 * Remove first token from queue and return its index. Add its count to the
308 * count of the next token.
309 * Call with page queue locked.
310 */
311 static token_idx_t
vm_purgeable_token_remove_first(purgeable_q_t queue)312 vm_purgeable_token_remove_first(purgeable_q_t queue)
313 {
314 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
315
316 token_idx_t token;
317 token = queue->token_q_head;
318
319 assert(token);
320
321 if (token) {
322 assert(queue->token_q_tail);
323 if (queue->token_q_head == queue->token_q_unripe) {
324 /* no ripe tokens... must move unripe pointer */
325 queue->token_q_unripe = tokens[token].next;
326 } else {
327 /* we're removing a ripe token. decrease count */
328 available_for_purge--;
329 assert(available_for_purge >= 0);
330 }
331
332 if (queue->token_q_tail == queue->token_q_head) {
333 assert(tokens[token].next == 0);
334 }
335
336 queue->token_q_head = tokens[token].next;
337 if (queue->token_q_head) {
338 tokens[queue->token_q_head].count += tokens[token].count;
339 tokens[queue->token_q_head].prev = 0;
340 } else {
341 /* currently no other tokens in the queue */
342 /*
343 * the page count must be added to the next newly
344 * created token
345 */
346 queue->new_pages += tokens[token].count;
347 /* if head is zero, tail is too */
348 queue->token_q_tail = 0;
349 }
350
351 #if MACH_ASSERT
352 queue->debug_count_tokens--;
353 vm_purgeable_token_check_queue(queue);
354
355 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_TOKEN_DELETE) | DBG_FUNC_NONE,
356 queue->type,
357 tokens[queue->token_q_head].count, /* num pages on new first token */
358 token_new_pagecount, /* num pages waiting for next token */
359 available_for_purge);
360 #endif
361 }
362 return token;
363 }
364
365 static token_idx_t
vm_purgeable_token_remove_last(purgeable_q_t queue)366 vm_purgeable_token_remove_last(purgeable_q_t queue)
367 {
368 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
369
370 token_idx_t token;
371 token = queue->token_q_tail;
372
373 assert(token);
374
375 if (token) {
376 assert(queue->token_q_head);
377
378 if (queue->token_q_tail == queue->token_q_head) {
379 assert(tokens[token].next == 0);
380 }
381
382 if (queue->token_q_unripe == 0) {
383 /* we're removing a ripe token. decrease count */
384 available_for_purge--;
385 assert(available_for_purge >= 0);
386 } else if (queue->token_q_unripe == token) {
387 /* we're removing the only unripe token */
388 queue->token_q_unripe = 0;
389 }
390
391 if (token == queue->token_q_head) {
392 /* token is the last one in the queue */
393 queue->token_q_head = 0;
394 queue->token_q_tail = 0;
395 } else {
396 token_idx_t new_tail;
397
398 new_tail = tokens[token].prev;
399
400 assert(new_tail);
401 assert(tokens[new_tail].next == token);
402
403 queue->token_q_tail = new_tail;
404 tokens[new_tail].next = 0;
405 }
406
407 queue->new_pages += tokens[token].count;
408
409 #if MACH_ASSERT
410 queue->debug_count_tokens--;
411 vm_purgeable_token_check_queue(queue);
412
413 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_TOKEN_DELETE) | DBG_FUNC_NONE,
414 queue->type,
415 tokens[queue->token_q_head].count, /* num pages on new first token */
416 token_new_pagecount, /* num pages waiting for next token */
417 available_for_purge);
418 #endif
419 }
420 return token;
421 }
422
423 /*
424 * Delete first token from queue. Return token to token queue.
425 * Call with page queue locked.
426 */
427 void
vm_purgeable_token_delete_first(purgeable_q_t queue)428 vm_purgeable_token_delete_first(purgeable_q_t queue)
429 {
430 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
431 token_idx_t token = vm_purgeable_token_remove_first(queue);
432
433 if (token) {
434 /* stick removed token on free queue */
435 tokens[token].next = token_free_idx;
436 tokens[token].prev = 0;
437 token_free_idx = token;
438 }
439 }
440
441 void
vm_purgeable_token_delete_last(purgeable_q_t queue)442 vm_purgeable_token_delete_last(purgeable_q_t queue)
443 {
444 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
445 token_idx_t token = vm_purgeable_token_remove_last(queue);
446
447 if (token) {
448 /* stick removed token on free queue */
449 tokens[token].next = token_free_idx;
450 tokens[token].prev = 0;
451 token_free_idx = token;
452 }
453 }
454
455
456 /* Call with page queue locked. */
457 void
vm_purgeable_q_advance_all()458 vm_purgeable_q_advance_all()
459 {
460 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
461
462 /* check queue counters - if they get really large, scale them back.
463 * They tend to get that large when there is no purgeable queue action */
464 int i;
465 if (token_new_pagecount > (TOKEN_NEW_PAGECOUNT_MAX >> 1)) { /* a system idling years might get there */
466 for (i = PURGEABLE_Q_TYPE_FIFO; i < PURGEABLE_Q_TYPE_MAX; i++) {
467 int64_t pages = purgeable_queues[i].new_pages += token_new_pagecount;
468 assert(pages >= 0);
469 assert(pages <= TOKEN_COUNT_MAX);
470 purgeable_queues[i].new_pages = (int32_t) pages;
471 assert(purgeable_queues[i].new_pages == pages);
472 }
473 token_new_pagecount = 0;
474 }
475
476 /*
477 * Decrement token counters. A token counter can be zero, this means the
478 * object is ripe to be purged. It is not purged immediately, because that
479 * could cause several objects to be purged even if purging one would satisfy
480 * the memory needs. Instead, the pageout thread purges one after the other
481 * by calling vm_purgeable_object_purge_one and then rechecking the memory
482 * balance.
483 *
484 * No need to advance obsolete queue - all items are ripe there,
485 * always
486 */
487 for (i = PURGEABLE_Q_TYPE_FIFO; i < PURGEABLE_Q_TYPE_MAX; i++) {
488 purgeable_q_t queue = &purgeable_queues[i];
489 uint32_t num_pages = 1;
490
491 /* Iterate over tokens as long as there are unripe tokens. */
492 while (queue->token_q_unripe) {
493 if (tokens[queue->token_q_unripe].count && num_pages) {
494 tokens[queue->token_q_unripe].count -= 1;
495 num_pages -= 1;
496 }
497
498 if (tokens[queue->token_q_unripe].count == 0) {
499 queue->token_q_unripe = tokens[queue->token_q_unripe].next;
500 available_for_purge++;
501 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_TOKEN_RIPEN) | DBG_FUNC_NONE,
502 queue->type,
503 tokens[queue->token_q_head].count, /* num pages on new first token */
504 0,
505 available_for_purge);
506 continue; /* One token ripened. Make sure to
507 * check the next. */
508 }
509 if (num_pages == 0) {
510 break; /* Current token not ripe and no more pages.
511 * Work done. */
512 }
513 }
514
515 /*
516 * if there are no unripe tokens in the queue, decrement the
517 * new_pages counter instead new_pages can be negative, but must be
518 * canceled out by token_new_pagecount -- since inactive queue as a
519 * whole always contains a nonnegative number of pages
520 */
521 if (!queue->token_q_unripe) {
522 queue->new_pages -= num_pages;
523 assert((int32_t) token_new_pagecount + queue->new_pages >= 0);
524 }
525 #if MACH_ASSERT
526 vm_purgeable_token_check_queue(queue);
527 #endif
528 }
529 }
530
531 /*
532 * grab any ripe object and purge it obsolete queue first. then, go through
533 * each volatile group. Select a queue with a ripe token.
534 * Start with first group (0)
535 * 1. Look at queue. Is there an object?
536 * Yes - purge it. Remove token.
537 * No - check other queue. Is there an object?
538 * No - increment group, then go to (1)
539 * Yes - purge it. Remove token. If there is no ripe token, remove ripe
540 * token from other queue and migrate unripe token from this
541 * queue to other queue.
542 * Call with page queue locked.
543 */
544 static void
vm_purgeable_token_remove_ripe(purgeable_q_t queue)545 vm_purgeable_token_remove_ripe(purgeable_q_t queue)
546 {
547 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
548 assert(queue->token_q_head && tokens[queue->token_q_head].count == 0);
549 /* return token to free list. advance token list. */
550 token_idx_t new_head = tokens[queue->token_q_head].next;
551 tokens[queue->token_q_head].next = token_free_idx;
552 tokens[queue->token_q_head].prev = 0;
553 token_free_idx = queue->token_q_head;
554 queue->token_q_head = new_head;
555 tokens[new_head].prev = 0;
556 if (new_head == 0) {
557 queue->token_q_tail = 0;
558 }
559
560 #if MACH_ASSERT
561 queue->debug_count_tokens--;
562 vm_purgeable_token_check_queue(queue);
563 #endif
564
565 available_for_purge--;
566 assert(available_for_purge >= 0);
567 }
568
569 /*
570 * Delete a ripe token from the given queue. If there are no ripe tokens on
571 * that queue, delete a ripe token from queue2, and migrate an unripe token
572 * from queue to queue2
573 * Call with page queue locked.
574 */
575 static void
vm_purgeable_token_choose_and_delete_ripe(purgeable_q_t queue,purgeable_q_t queue2)576 vm_purgeable_token_choose_and_delete_ripe(purgeable_q_t queue, purgeable_q_t queue2)
577 {
578 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
579 assert(queue->token_q_head);
580
581 if (tokens[queue->token_q_head].count == 0) {
582 /* This queue has a ripe token. Remove. */
583 vm_purgeable_token_remove_ripe(queue);
584 } else {
585 assert(queue2);
586 /*
587 * queue2 must have a ripe token. Remove, and migrate one
588 * from queue to queue2.
589 */
590 vm_purgeable_token_remove_ripe(queue2);
591 /* migrate unripe token */
592 token_idx_t token;
593 token_cnt_t count;
594
595 /* remove token from queue1 */
596 assert(queue->token_q_unripe == queue->token_q_head); /* queue1 had no unripe
597 * tokens, remember? */
598 token = vm_purgeable_token_remove_first(queue);
599 assert(token);
600
601 count = tokens[token].count;
602
603 /* migrate to queue2 */
604 /* go to migration target loc */
605
606 token_idx_t token_to_insert_before = queue2->token_q_head, token_to_insert_after;
607
608 while (token_to_insert_before != 0 && count > tokens[token_to_insert_before].count) {
609 count -= tokens[token_to_insert_before].count;
610 token_to_insert_before = tokens[token_to_insert_before].next;
611 }
612
613 /* token_to_insert_before is now set correctly */
614
615 /* should the inserted token become the first unripe token? */
616 if ((token_to_insert_before == queue2->token_q_unripe) || (queue2->token_q_unripe == 0)) {
617 queue2->token_q_unripe = token; /* if so, must update unripe pointer */
618 }
619 /*
620 * insert token.
621 * if inserting at end, reduce new_pages by that value;
622 * otherwise, reduce counter of next token
623 */
624
625 tokens[token].count = count;
626
627 if (token_to_insert_before != 0) {
628 token_to_insert_after = tokens[token_to_insert_before].prev;
629
630 tokens[token].next = token_to_insert_before;
631 tokens[token_to_insert_before].prev = token;
632
633 assert(tokens[token_to_insert_before].count >= count);
634 tokens[token_to_insert_before].count -= count;
635 } else {
636 /* if we ran off the end of the list, the token to insert after is the tail */
637 token_to_insert_after = queue2->token_q_tail;
638
639 tokens[token].next = 0;
640 queue2->token_q_tail = token;
641
642 assert(queue2->new_pages >= (int32_t) count);
643 queue2->new_pages -= count;
644 }
645
646 if (token_to_insert_after != 0) {
647 tokens[token].prev = token_to_insert_after;
648 tokens[token_to_insert_after].next = token;
649 } else {
650 /* is this case possible? */
651 tokens[token].prev = 0;
652 queue2->token_q_head = token;
653 }
654
655 #if MACH_ASSERT
656 queue2->debug_count_tokens++;
657 vm_purgeable_token_check_queue(queue2);
658 #endif
659 }
660 }
661
662 /* Find an object that can be locked. Returns locked object. */
663 /* Call with purgeable queue locked. */
664 static vm_object_t
vm_purgeable_object_find_and_lock(purgeable_q_t queue,int group,boolean_t pick_ripe)665 vm_purgeable_object_find_and_lock(
666 purgeable_q_t queue,
667 int group,
668 boolean_t pick_ripe)
669 {
670 vm_object_t object, best_object;
671 int object_task_importance;
672 int best_object_task_importance;
673 int best_object_skipped;
674 int num_objects_skipped;
675 int try_lock_failed = 0;
676 int try_lock_succeeded = 0;
677 task_t owner;
678
679 best_object = VM_OBJECT_NULL;
680 best_object_task_importance = INT_MAX;
681
682 LCK_MTX_ASSERT(&vm_purgeable_queue_lock, LCK_MTX_ASSERT_OWNED);
683 /*
684 * Usually we would pick the first element from a queue. However, we
685 * might not be able to get a lock on it, in which case we try the
686 * remaining elements in order.
687 */
688
689 KDBG_RELEASE(VMDBG_CODE(DBG_VM_PURGEABLE_OBJECT_PURGE_LOOP) | DBG_FUNC_START,
690 pick_ripe,
691 group,
692 VM_KERNEL_UNSLIDE_OR_PERM(queue));
693
694 num_objects_skipped = 0;
695 for (object = (vm_object_t) queue_first(&queue->objq[group]);
696 !queue_end(&queue->objq[group], (queue_entry_t) object);
697 object = (vm_object_t) queue_next(&object->objq),
698 num_objects_skipped++) {
699 /*
700 * To prevent us looping for an excessively long time, choose
701 * the best object we've seen after looking at PURGEABLE_LOOP_MAX elements.
702 * If we haven't seen an eligible object after PURGEABLE_LOOP_MAX elements,
703 * we keep going until we find the first eligible object.
704 */
705 if ((num_objects_skipped >= PURGEABLE_LOOP_MAX) && (best_object != NULL)) {
706 break;
707 }
708
709 if (pick_ripe &&
710 !object->purgeable_when_ripe) {
711 /* we want an object that has a ripe token */
712 continue;
713 }
714
715 object_task_importance = 0;
716
717 /*
718 * We don't want to use VM_OBJECT_OWNER() here: we want to
719 * distinguish kernel-owned and disowned objects.
720 * Disowned objects have no owner and will have no importance...
721 */
722 owner = object->vo_owner;
723 if (owner != NULL && owner != VM_OBJECT_OWNER_DISOWNED) {
724 #if !XNU_TARGET_OS_OSX
725 #if CONFIG_JETSAM
726 object_task_importance = proc_get_memstat_priority((struct proc *)get_bsdtask_info(owner), TRUE);
727 #endif /* CONFIG_JETSAM */
728 #else /* !XNU_TARGET_OS_OSX */
729 object_task_importance = task_importance_estimate(owner);
730 #endif /* !XNU_TARGET_OS_OSX */
731 }
732
733 if (object_task_importance < best_object_task_importance) {
734 if (vm_object_lock_try(object)) {
735 try_lock_succeeded++;
736 if (best_object != VM_OBJECT_NULL) {
737 /* forget about previous best object */
738 vm_object_unlock(best_object);
739 }
740 best_object = object;
741 best_object_task_importance = object_task_importance;
742 best_object_skipped = num_objects_skipped;
743 if (best_object_task_importance == 0) {
744 /* can't get any better: stop looking */
745 break;
746 }
747 } else {
748 try_lock_failed++;
749 }
750 }
751 }
752
753 KDBG_RELEASE(VMDBG_CODE(DBG_VM_PURGEABLE_OBJECT_PURGE_LOOP) | DBG_FUNC_END,
754 num_objects_skipped, /* considered objects */
755 try_lock_failed,
756 try_lock_succeeded,
757 VM_KERNEL_UNSLIDE_OR_PERM(best_object));
758
759 object = best_object;
760
761 if (object == VM_OBJECT_NULL) {
762 return VM_OBJECT_NULL;
763 }
764
765 /* Locked. Great. We'll take it. Remove and return. */
766 // printf("FOUND PURGEABLE object %p skipped %d\n", object, num_objects_skipped);
767
768 vm_object_lock_assert_exclusive(object);
769
770 queue_remove(&queue->objq[group], object,
771 vm_object_t, objq);
772 object->objq.next = NULL;
773 object->objq.prev = NULL;
774 object->purgeable_queue_type = PURGEABLE_Q_TYPE_MAX;
775 object->purgeable_queue_group = 0;
776 /* one less volatile object for this object's owner */
777 vm_purgeable_volatile_owner_update(VM_OBJECT_OWNER(object), -1);
778
779 #if DEBUG
780 object->vo_purgeable_volatilizer = NULL;
781 #endif /* DEBUG */
782
783 /* keep queue of non-volatile objects */
784 queue_enter(&purgeable_nonvolatile_queue, object,
785 vm_object_t, objq);
786 assert(purgeable_nonvolatile_count >= 0);
787 purgeable_nonvolatile_count++;
788 assert(purgeable_nonvolatile_count > 0);
789 /* one more nonvolatile object for this object's owner */
790 vm_purgeable_nonvolatile_owner_update(VM_OBJECT_OWNER(object), +1);
791
792 #if MACH_ASSERT
793 queue->debug_count_objects--;
794 #endif
795 return object;
796 }
797
798 /* Can be called without holding locks */
799 void
vm_purgeable_object_purge_all(void)800 vm_purgeable_object_purge_all(void)
801 {
802 enum purgeable_q_type i;
803 int group;
804 vm_object_t object;
805 unsigned int purged_count;
806 uint32_t collisions;
807
808 purged_count = 0;
809 collisions = 0;
810
811 restart:
812 lck_mtx_lock(&vm_purgeable_queue_lock);
813 /* Cycle through all queues */
814 for (i = PURGEABLE_Q_TYPE_OBSOLETE; i < PURGEABLE_Q_TYPE_MAX; i++) {
815 purgeable_q_t queue;
816
817 queue = &purgeable_queues[i];
818
819 /*
820 * Look through all groups, starting from the lowest. If
821 * we find an object in that group, try to lock it (this can
822 * fail). If locking is successful, we can drop the queue
823 * lock, remove a token and then purge the object.
824 */
825 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
826 while (!queue_empty(&queue->objq[group])) {
827 object = vm_purgeable_object_find_and_lock(queue, group, FALSE);
828 if (object == VM_OBJECT_NULL) {
829 lck_mtx_unlock(&vm_purgeable_queue_lock);
830 mutex_pause(collisions++);
831 goto restart;
832 }
833
834 lck_mtx_unlock(&vm_purgeable_queue_lock);
835
836 /* Lock the page queue here so we don't hold it
837 * over the whole, legthy operation */
838 if (object->purgeable_when_ripe) {
839 vm_page_lock_queues();
840 vm_purgeable_token_remove_first(queue);
841 vm_page_unlock_queues();
842 }
843
844 (void) vm_object_purge(object, 0);
845 assert(object->purgable == VM_PURGABLE_EMPTY);
846 /* no change in purgeable accounting */
847
848 vm_object_unlock(object);
849 purged_count++;
850 goto restart;
851 }
852 assert(queue->debug_count_objects >= 0);
853 }
854 }
855 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_OBJECT_PURGE_ALL) | DBG_FUNC_NONE,
856 purged_count, /* # of purged objects */
857 0,
858 available_for_purge);
859 lck_mtx_unlock(&vm_purgeable_queue_lock);
860 return;
861 }
862
863 boolean_t
vm_purgeable_object_purge_one_unlocked(int force_purge_below_group)864 vm_purgeable_object_purge_one_unlocked(
865 int force_purge_below_group)
866 {
867 boolean_t retval;
868
869 vm_page_lock_queues();
870 retval = vm_purgeable_object_purge_one(force_purge_below_group, 0);
871 vm_page_unlock_queues();
872
873 return retval;
874 }
875
876 boolean_t
vm_purgeable_object_purge_one(int force_purge_below_group,int flags)877 vm_purgeable_object_purge_one(
878 int force_purge_below_group,
879 int flags)
880 {
881 enum purgeable_q_type i;
882 int group;
883 vm_object_t object = 0;
884 purgeable_q_t queue, queue2;
885 boolean_t forced_purge;
886 unsigned int resident_page_count;
887
888
889 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_OBJECT_PURGE) | DBG_FUNC_START,
890 force_purge_below_group, flags);
891
892 /* Need the page queue lock since we'll be changing the token queue. */
893 LCK_MTX_ASSERT(&vm_page_queue_lock, LCK_MTX_ASSERT_OWNED);
894 lck_mtx_lock(&vm_purgeable_queue_lock);
895
896 /* Cycle through all queues */
897 for (i = PURGEABLE_Q_TYPE_OBSOLETE; i < PURGEABLE_Q_TYPE_MAX; i++) {
898 queue = &purgeable_queues[i];
899
900 if (force_purge_below_group == 0) {
901 /*
902 * Are there any ripe tokens on this queue? If yes,
903 * we'll find an object to purge there
904 */
905 if (!queue->token_q_head) {
906 /* no token: look at next purgeable queue */
907 continue;
908 }
909
910 if (tokens[queue->token_q_head].count != 0) {
911 /* no ripe token: next queue */
912 continue;
913 }
914 }
915
916 /*
917 * Now look through all groups, starting from the lowest. If
918 * we find an object in that group, try to lock it (this can
919 * fail). If locking is successful, we can drop the queue
920 * lock, remove a token and then purge the object.
921 */
922 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
923 if (!queue->token_q_head ||
924 tokens[queue->token_q_head].count != 0) {
925 /* no tokens or no ripe tokens */
926
927 if (group >= force_purge_below_group) {
928 /* no more groups to force-purge */
929 break;
930 }
931
932 /*
933 * Try and purge an object in this group
934 * even though no tokens are ripe.
935 */
936 if (!queue_empty(&queue->objq[group]) &&
937 (object = vm_purgeable_object_find_and_lock(queue, group, FALSE))) {
938 lck_mtx_unlock(&vm_purgeable_queue_lock);
939 if (object->purgeable_when_ripe) {
940 vm_purgeable_token_delete_first(queue);
941 }
942 forced_purge = TRUE;
943 goto purge_now;
944 }
945
946 /* nothing to purge in this group: next group */
947 continue;
948 }
949 if (!queue_empty(&queue->objq[group]) &&
950 (object = vm_purgeable_object_find_and_lock(queue, group, TRUE))) {
951 lck_mtx_unlock(&vm_purgeable_queue_lock);
952 if (object->purgeable_when_ripe) {
953 vm_purgeable_token_choose_and_delete_ripe(queue, 0);
954 }
955 forced_purge = FALSE;
956 goto purge_now;
957 }
958 if (i != PURGEABLE_Q_TYPE_OBSOLETE) {
959 /* This is the token migration case, and it works between
960 * FIFO and LIFO only */
961 queue2 = &purgeable_queues[i != PURGEABLE_Q_TYPE_FIFO ?
962 PURGEABLE_Q_TYPE_FIFO :
963 PURGEABLE_Q_TYPE_LIFO];
964
965 if (!queue_empty(&queue2->objq[group]) &&
966 (object = vm_purgeable_object_find_and_lock(queue2, group, TRUE))) {
967 lck_mtx_unlock(&vm_purgeable_queue_lock);
968 if (object->purgeable_when_ripe) {
969 vm_purgeable_token_choose_and_delete_ripe(queue2, queue);
970 }
971 forced_purge = FALSE;
972 goto purge_now;
973 }
974 }
975 assert(queue->debug_count_objects >= 0);
976 }
977 }
978 /*
979 * because we have to do a try_lock on the objects which could fail,
980 * we could end up with no object to purge at this time, even though
981 * we have objects in a purgeable state
982 */
983 lck_mtx_unlock(&vm_purgeable_queue_lock);
984
985 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_OBJECT_PURGE) | DBG_FUNC_END,
986 0, 0, available_for_purge);
987
988 return FALSE;
989
990 purge_now:
991
992 assert(object);
993 vm_page_unlock_queues(); /* Unlock for call to vm_object_purge() */
994 // 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_owner, task_importance_estimate(object->vo_owner), i, group, force_purge_below_group, memorystatus_vm_pressure_level);
995 resident_page_count = object->resident_page_count;
996 (void) vm_object_purge(object, flags);
997 assert(object->purgable == VM_PURGABLE_EMPTY);
998 /* no change in purgeable accounting */
999 vm_object_unlock(object);
1000 vm_page_lock_queues();
1001
1002 vm_pageout_vminfo.vm_pageout_pages_purged += resident_page_count;
1003
1004 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_OBJECT_PURGE) | DBG_FUNC_END,
1005 VM_KERNEL_UNSLIDE_OR_PERM(object), /* purged object */
1006 resident_page_count,
1007 available_for_purge);
1008
1009 return TRUE;
1010 }
1011
1012 /* Called with object lock held */
1013 void
vm_purgeable_object_add(vm_object_t object,purgeable_q_t queue,int group)1014 vm_purgeable_object_add(vm_object_t object, purgeable_q_t queue, int group)
1015 {
1016 vm_object_lock_assert_exclusive(object);
1017 lck_mtx_lock(&vm_purgeable_queue_lock);
1018
1019 assert(object->objq.next != NULL);
1020 assert(object->objq.prev != NULL);
1021 queue_remove(&purgeable_nonvolatile_queue, object,
1022 vm_object_t, objq);
1023 object->objq.next = NULL;
1024 object->objq.prev = NULL;
1025 assert(purgeable_nonvolatile_count > 0);
1026 purgeable_nonvolatile_count--;
1027 assert(purgeable_nonvolatile_count >= 0);
1028 /* one less nonvolatile object for this object's owner */
1029 vm_purgeable_nonvolatile_owner_update(VM_OBJECT_OWNER(object), -1);
1030
1031 if (queue->type == PURGEABLE_Q_TYPE_OBSOLETE) {
1032 group = 0;
1033 }
1034
1035 if (queue->type != PURGEABLE_Q_TYPE_LIFO) { /* fifo and obsolete are
1036 * fifo-queued */
1037 queue_enter(&queue->objq[group], object, vm_object_t, objq); /* last to die */
1038 } else {
1039 queue_enter_first(&queue->objq[group], object, vm_object_t, objq); /* first to die */
1040 }
1041 /* one more volatile object for this object's owner */
1042 vm_purgeable_volatile_owner_update(VM_OBJECT_OWNER(object), +1);
1043
1044 object->purgeable_queue_type = queue->type;
1045 object->purgeable_queue_group = group;
1046
1047 #if DEBUG
1048 assert(object->vo_purgeable_volatilizer == NULL);
1049 object->vo_purgeable_volatilizer = current_task();
1050 OSBacktrace(&object->purgeable_volatilizer_bt[0],
1051 ARRAY_COUNT(object->purgeable_volatilizer_bt));
1052 #endif /* DEBUG */
1053
1054 #if MACH_ASSERT
1055 queue->debug_count_objects++;
1056 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_OBJECT_ADD) | DBG_FUNC_NONE,
1057 0,
1058 tokens[queue->token_q_head].count,
1059 queue->type,
1060 group);
1061 #endif
1062
1063 lck_mtx_unlock(&vm_purgeable_queue_lock);
1064 }
1065
1066 /* Look for object. If found, remove from purgeable queue. */
1067 /* Called with object lock held */
1068 purgeable_q_t
vm_purgeable_object_remove(vm_object_t object)1069 vm_purgeable_object_remove(vm_object_t object)
1070 {
1071 int group;
1072 enum purgeable_q_type type;
1073 purgeable_q_t queue;
1074
1075 vm_object_lock_assert_exclusive(object);
1076
1077 type = object->purgeable_queue_type;
1078 group = object->purgeable_queue_group;
1079
1080 if (type == PURGEABLE_Q_TYPE_MAX) {
1081 if (object->objq.prev || object->objq.next) {
1082 panic("unmarked object on purgeable q");
1083 }
1084
1085 return NULL;
1086 } else if (!(object->objq.prev && object->objq.next)) {
1087 panic("marked object not on purgeable q");
1088 }
1089
1090 lck_mtx_lock(&vm_purgeable_queue_lock);
1091
1092 queue = &purgeable_queues[type];
1093
1094 queue_remove(&queue->objq[group], object, vm_object_t, objq);
1095 object->objq.next = NULL;
1096 object->objq.prev = NULL;
1097 /* one less volatile object for this object's owner */
1098 vm_purgeable_volatile_owner_update(VM_OBJECT_OWNER(object), -1);
1099 #if DEBUG
1100 object->vo_purgeable_volatilizer = NULL;
1101 #endif /* DEBUG */
1102 /* keep queue of non-volatile objects */
1103 if (object->alive && !object->terminating) {
1104 queue_enter(&purgeable_nonvolatile_queue, object,
1105 vm_object_t, objq);
1106 assert(purgeable_nonvolatile_count >= 0);
1107 purgeable_nonvolatile_count++;
1108 assert(purgeable_nonvolatile_count > 0);
1109 /* one more nonvolatile object for this object's owner */
1110 vm_purgeable_nonvolatile_owner_update(VM_OBJECT_OWNER(object), +1);
1111 }
1112
1113 #if MACH_ASSERT
1114 queue->debug_count_objects--;
1115 KDBG(VMDBG_CODE(DBG_VM_PURGEABLE_OBJECT_REMOVE) | DBG_FUNC_NONE,
1116 0,
1117 tokens[queue->token_q_head].count,
1118 queue->type,
1119 group);
1120 #endif
1121
1122 lck_mtx_unlock(&vm_purgeable_queue_lock);
1123
1124 object->purgeable_queue_type = PURGEABLE_Q_TYPE_MAX;
1125 object->purgeable_queue_group = 0;
1126
1127 vm_object_lock_assert_exclusive(object);
1128
1129 return &purgeable_queues[type];
1130 }
1131
1132 void
vm_purgeable_stats_helper(vm_purgeable_stat_t * stat,purgeable_q_t queue,int group,task_t target_task)1133 vm_purgeable_stats_helper(vm_purgeable_stat_t *stat, purgeable_q_t queue, int group, task_t target_task)
1134 {
1135 LCK_MTX_ASSERT(&vm_purgeable_queue_lock, LCK_MTX_ASSERT_OWNED);
1136
1137 stat->count = stat->size = 0;
1138 vm_object_t object;
1139 for (object = (vm_object_t) queue_first(&queue->objq[group]);
1140 !queue_end(&queue->objq[group], (queue_entry_t) object);
1141 object = (vm_object_t) queue_next(&object->objq)) {
1142 if (!target_task || VM_OBJECT_OWNER(object) == target_task) {
1143 stat->count++;
1144 stat->size += (object->resident_page_count * PAGE_SIZE);
1145 }
1146 }
1147 return;
1148 }
1149
1150 void
vm_purgeable_stats(vm_purgeable_info_t info,task_t target_task)1151 vm_purgeable_stats(vm_purgeable_info_t info, task_t target_task)
1152 {
1153 purgeable_q_t queue;
1154 int group;
1155
1156 lck_mtx_lock(&vm_purgeable_queue_lock);
1157
1158 /* Populate fifo_data */
1159 queue = &purgeable_queues[PURGEABLE_Q_TYPE_FIFO];
1160 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
1161 vm_purgeable_stats_helper(&(info->fifo_data[group]), queue, group, target_task);
1162 }
1163
1164 /* Populate lifo_data */
1165 queue = &purgeable_queues[PURGEABLE_Q_TYPE_LIFO];
1166 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
1167 vm_purgeable_stats_helper(&(info->lifo_data[group]), queue, group, target_task);
1168 }
1169
1170 /* Populate obsolete data */
1171 queue = &purgeable_queues[PURGEABLE_Q_TYPE_OBSOLETE];
1172 vm_purgeable_stats_helper(&(info->obsolete_data), queue, 0, target_task);
1173
1174 lck_mtx_unlock(&vm_purgeable_queue_lock);
1175 return;
1176 }
1177
1178 #if DEVELOPMENT || DEBUG
1179 static void
vm_purgeable_account_volatile_queue(purgeable_q_t queue,int group,task_t task,pvm_account_info_t acnt_info)1180 vm_purgeable_account_volatile_queue(
1181 purgeable_q_t queue,
1182 int group,
1183 task_t task,
1184 pvm_account_info_t acnt_info)
1185 {
1186 vm_object_t object;
1187 uint64_t compressed_count;
1188
1189 for (object = (vm_object_t) queue_first(&queue->objq[group]);
1190 !queue_end(&queue->objq[group], (queue_entry_t) object);
1191 object = (vm_object_t) queue_next(&object->objq)) {
1192 if (VM_OBJECT_OWNER(object) == task) {
1193 compressed_count = vm_compressor_pager_get_count(object->pager);
1194 acnt_info->pvm_volatile_compressed_count += compressed_count;
1195 acnt_info->pvm_volatile_count += (object->resident_page_count - object->wired_page_count);
1196 acnt_info->pvm_nonvolatile_count += object->wired_page_count;
1197 }
1198 }
1199 }
1200
1201 /*
1202 * Walks the purgeable object queues and calculates the usage
1203 * associated with the objects for the given task.
1204 */
1205 kern_return_t
vm_purgeable_account(task_t task,pvm_account_info_t acnt_info)1206 vm_purgeable_account(
1207 task_t task,
1208 pvm_account_info_t acnt_info)
1209 {
1210 queue_head_t *nonvolatile_q;
1211 vm_object_t object;
1212 int group;
1213 int state;
1214 uint64_t compressed_count;
1215 purgeable_q_t volatile_q;
1216
1217
1218 if ((task == NULL) || (acnt_info == NULL)) {
1219 return KERN_INVALID_ARGUMENT;
1220 }
1221
1222 acnt_info->pvm_volatile_count = 0;
1223 acnt_info->pvm_volatile_compressed_count = 0;
1224 acnt_info->pvm_nonvolatile_count = 0;
1225 acnt_info->pvm_nonvolatile_compressed_count = 0;
1226
1227 lck_mtx_lock(&vm_purgeable_queue_lock);
1228
1229 nonvolatile_q = &purgeable_nonvolatile_queue;
1230 for (object = (vm_object_t) queue_first(nonvolatile_q);
1231 !queue_end(nonvolatile_q, (queue_entry_t) object);
1232 object = (vm_object_t) queue_next(&object->objq)) {
1233 if (VM_OBJECT_OWNER(object) == task) {
1234 state = object->purgable;
1235 compressed_count = vm_compressor_pager_get_count(object->pager);
1236 if (state == VM_PURGABLE_EMPTY) {
1237 acnt_info->pvm_volatile_count += (object->resident_page_count - object->wired_page_count);
1238 acnt_info->pvm_volatile_compressed_count += compressed_count;
1239 } else {
1240 acnt_info->pvm_nonvolatile_count += (object->resident_page_count - object->wired_page_count);
1241 acnt_info->pvm_nonvolatile_compressed_count += compressed_count;
1242 }
1243 acnt_info->pvm_nonvolatile_count += object->wired_page_count;
1244 }
1245 }
1246
1247 volatile_q = &purgeable_queues[PURGEABLE_Q_TYPE_OBSOLETE];
1248 vm_purgeable_account_volatile_queue(volatile_q, 0, task, acnt_info);
1249
1250 volatile_q = &purgeable_queues[PURGEABLE_Q_TYPE_FIFO];
1251 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
1252 vm_purgeable_account_volatile_queue(volatile_q, group, task, acnt_info);
1253 }
1254
1255 volatile_q = &purgeable_queues[PURGEABLE_Q_TYPE_LIFO];
1256 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
1257 vm_purgeable_account_volatile_queue(volatile_q, group, task, acnt_info);
1258 }
1259 lck_mtx_unlock(&vm_purgeable_queue_lock);
1260
1261 acnt_info->pvm_volatile_count = (acnt_info->pvm_volatile_count * PAGE_SIZE);
1262 acnt_info->pvm_volatile_compressed_count = (acnt_info->pvm_volatile_compressed_count * PAGE_SIZE);
1263 acnt_info->pvm_nonvolatile_count = (acnt_info->pvm_nonvolatile_count * PAGE_SIZE);
1264 acnt_info->pvm_nonvolatile_compressed_count = (acnt_info->pvm_nonvolatile_compressed_count * PAGE_SIZE);
1265
1266 return KERN_SUCCESS;
1267 }
1268 #endif /* DEVELOPMENT || DEBUG */
1269
1270 static uint64_t
vm_purgeable_queue_purge_task_owned(purgeable_q_t queue,int group,task_t task)1271 vm_purgeable_queue_purge_task_owned(
1272 purgeable_q_t queue,
1273 int group,
1274 task_t task)
1275 {
1276 vm_object_t object = VM_OBJECT_NULL;
1277 int collisions = 0;
1278 uint64_t num_pages_purged = 0;
1279
1280 num_pages_purged = 0;
1281 collisions = 0;
1282
1283 look_again:
1284 lck_mtx_lock(&vm_purgeable_queue_lock);
1285
1286 for (object = (vm_object_t) queue_first(&queue->objq[group]);
1287 !queue_end(&queue->objq[group], (queue_entry_t) object);
1288 object = (vm_object_t) queue_next(&object->objq)) {
1289 if (object->vo_owner != task) {
1290 continue;
1291 }
1292
1293 /* found an object: try and grab it */
1294 if (!vm_object_lock_try(object)) {
1295 lck_mtx_unlock(&vm_purgeable_queue_lock);
1296 mutex_pause(collisions++);
1297 goto look_again;
1298 }
1299 /* got it ! */
1300
1301 collisions = 0;
1302
1303 /* remove object from purgeable queue */
1304 queue_remove(&queue->objq[group], object,
1305 vm_object_t, objq);
1306 object->objq.next = NULL;
1307 object->objq.prev = NULL;
1308 object->purgeable_queue_type = PURGEABLE_Q_TYPE_MAX;
1309 object->purgeable_queue_group = 0;
1310 /* one less volatile object for this object's owner */
1311 assert(object->vo_owner == task);
1312 vm_purgeable_volatile_owner_update(task, -1);
1313
1314 #if DEBUG
1315 object->vo_purgeable_volatilizer = NULL;
1316 #endif /* DEBUG */
1317 queue_enter(&purgeable_nonvolatile_queue, object,
1318 vm_object_t, objq);
1319 assert(purgeable_nonvolatile_count >= 0);
1320 purgeable_nonvolatile_count++;
1321 assert(purgeable_nonvolatile_count > 0);
1322 /* one more nonvolatile object for this object's owner */
1323 assert(object->vo_owner == task);
1324 vm_purgeable_nonvolatile_owner_update(task, +1);
1325
1326 /* unlock purgeable queues */
1327 lck_mtx_unlock(&vm_purgeable_queue_lock);
1328
1329 if (object->purgeable_when_ripe) {
1330 /* remove a token */
1331 vm_page_lock_queues();
1332 vm_purgeable_token_remove_first(queue);
1333 vm_page_unlock_queues();
1334 }
1335
1336 /* purge the object */
1337 num_pages_purged += vm_object_purge(object, 0);
1338
1339 assert(object->purgable == VM_PURGABLE_EMPTY);
1340 /* no change for purgeable accounting */
1341 vm_object_unlock(object);
1342
1343 /* we unlocked the purgeable queues, so start over */
1344 goto look_again;
1345 }
1346
1347 lck_mtx_unlock(&vm_purgeable_queue_lock);
1348
1349 return num_pages_purged;
1350 }
1351
1352 uint64_t
vm_purgeable_purge_task_owned(task_t task)1353 vm_purgeable_purge_task_owned(
1354 task_t task)
1355 {
1356 purgeable_q_t queue = NULL;
1357 int group = 0;
1358 uint64_t num_pages_purged = 0;
1359
1360 num_pages_purged = 0;
1361
1362 queue = &purgeable_queues[PURGEABLE_Q_TYPE_OBSOLETE];
1363 num_pages_purged += vm_purgeable_queue_purge_task_owned(queue,
1364 0,
1365 task);
1366
1367 queue = &purgeable_queues[PURGEABLE_Q_TYPE_FIFO];
1368 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
1369 num_pages_purged += vm_purgeable_queue_purge_task_owned(queue,
1370 group,
1371 task);
1372 }
1373
1374 queue = &purgeable_queues[PURGEABLE_Q_TYPE_LIFO];
1375 for (group = 0; group < NUM_VOLATILE_GROUPS; group++) {
1376 num_pages_purged += vm_purgeable_queue_purge_task_owned(queue,
1377 group,
1378 task);
1379 }
1380
1381 return num_pages_purged;
1382 }
1383
1384 void
vm_purgeable_nonvolatile_enqueue(vm_object_t object,task_t owner)1385 vm_purgeable_nonvolatile_enqueue(
1386 vm_object_t object,
1387 task_t owner)
1388 {
1389 int ledger_flags;
1390 kern_return_t kr;
1391
1392 vm_object_lock_assert_exclusive(object);
1393
1394 assert(object->purgable == VM_PURGABLE_NONVOLATILE);
1395 assert(object->vo_owner == NULL);
1396
1397 lck_mtx_lock(&vm_purgeable_queue_lock);
1398
1399 if (owner != NULL &&
1400 owner->task_objects_disowning) {
1401 /* task is exiting and no longer tracking purgeable objects */
1402 owner = VM_OBJECT_OWNER_DISOWNED;
1403 }
1404 if (owner == NULL) {
1405 owner = kernel_task;
1406 }
1407 #if DEBUG
1408 OSBacktrace(&object->purgeable_owner_bt[0],
1409 ARRAY_COUNT(object->purgeable_owner_bt));
1410 object->vo_purgeable_volatilizer = NULL;
1411 #endif /* DEBUG */
1412
1413 ledger_flags = 0;
1414 if (object->vo_no_footprint) {
1415 ledger_flags |= VM_LEDGER_FLAG_NO_FOOTPRINT;
1416 }
1417 kr = vm_object_ownership_change(object,
1418 object->vo_ledger_tag, /* tag unchanged */
1419 owner,
1420 ledger_flags,
1421 FALSE); /* task_objq_locked */
1422 assert(kr == KERN_SUCCESS);
1423
1424 assert(object->objq.next == NULL);
1425 assert(object->objq.prev == NULL);
1426
1427 queue_enter(&purgeable_nonvolatile_queue, object,
1428 vm_object_t, objq);
1429 assert(purgeable_nonvolatile_count >= 0);
1430 purgeable_nonvolatile_count++;
1431 assert(purgeable_nonvolatile_count > 0);
1432 lck_mtx_unlock(&vm_purgeable_queue_lock);
1433
1434 vm_object_lock_assert_exclusive(object);
1435 }
1436
1437 void
vm_purgeable_nonvolatile_dequeue(vm_object_t object)1438 vm_purgeable_nonvolatile_dequeue(
1439 vm_object_t object)
1440 {
1441 task_t owner;
1442 kern_return_t kr;
1443
1444 vm_object_lock_assert_exclusive(object);
1445
1446 owner = VM_OBJECT_OWNER(object);
1447 #if DEBUG
1448 assert(object->vo_purgeable_volatilizer == NULL);
1449 #endif /* DEBUG */
1450 if (owner != NULL) {
1451 /*
1452 * Update the owner's ledger to stop accounting
1453 * for this object.
1454 */
1455 /* transfer ownership to the kernel */
1456 assert(VM_OBJECT_OWNER(object) != kernel_task);
1457 kr = vm_object_ownership_change(
1458 object,
1459 object->vo_ledger_tag, /* unchanged */
1460 VM_OBJECT_OWNER_DISOWNED, /* new owner */
1461 0, /* ledger_flags */
1462 FALSE); /* old_owner->task_objq locked */
1463 assert(kr == KERN_SUCCESS);
1464 assert(object->vo_owner == VM_OBJECT_OWNER_DISOWNED);
1465 }
1466
1467 lck_mtx_lock(&vm_purgeable_queue_lock);
1468 assert(object->objq.next != NULL);
1469 assert(object->objq.prev != NULL);
1470 queue_remove(&purgeable_nonvolatile_queue, object,
1471 vm_object_t, objq);
1472 object->objq.next = NULL;
1473 object->objq.prev = NULL;
1474 assert(purgeable_nonvolatile_count > 0);
1475 purgeable_nonvolatile_count--;
1476 assert(purgeable_nonvolatile_count >= 0);
1477 lck_mtx_unlock(&vm_purgeable_queue_lock);
1478
1479 vm_object_lock_assert_exclusive(object);
1480 }
1481
1482 void
vm_purgeable_accounting(vm_object_t object,vm_purgable_t old_state)1483 vm_purgeable_accounting(
1484 vm_object_t object,
1485 vm_purgable_t old_state)
1486 {
1487 task_t owner;
1488 int resident_page_count;
1489 int wired_page_count;
1490 int compressed_page_count;
1491 int ledger_idx_volatile;
1492 int ledger_idx_nonvolatile;
1493 int ledger_idx_volatile_compressed;
1494 int ledger_idx_nonvolatile_compressed;
1495 int ledger_idx_composite;
1496 int ledger_idx_external_wired;
1497 boolean_t do_footprint;
1498
1499 vm_object_lock_assert_exclusive(object);
1500 assert(object->purgable != VM_PURGABLE_DENY);
1501
1502 owner = VM_OBJECT_OWNER(object);
1503 if (owner == NULL ||
1504 object->purgable == VM_PURGABLE_DENY) {
1505 return;
1506 }
1507
1508 vm_object_ledger_tag_ledgers(object,
1509 &ledger_idx_volatile,
1510 &ledger_idx_nonvolatile,
1511 &ledger_idx_volatile_compressed,
1512 &ledger_idx_nonvolatile_compressed,
1513 &ledger_idx_composite,
1514 &ledger_idx_external_wired,
1515 &do_footprint);
1516 assert(ledger_idx_external_wired == -1);
1517
1518 resident_page_count = object->resident_page_count;
1519 wired_page_count = object->wired_page_count;
1520 if (VM_CONFIG_COMPRESSOR_IS_PRESENT &&
1521 object->pager != NULL) {
1522 compressed_page_count =
1523 vm_compressor_pager_get_count(object->pager);
1524 } else {
1525 compressed_page_count = 0;
1526 }
1527
1528 if (old_state == VM_PURGABLE_VOLATILE ||
1529 old_state == VM_PURGABLE_EMPTY) {
1530 /* less volatile bytes in ledger */
1531 ledger_debit(owner->ledger,
1532 ledger_idx_volatile,
1533 ptoa_64(resident_page_count - wired_page_count));
1534 /* less compressed volatile bytes in ledger */
1535 ledger_debit(owner->ledger,
1536 ledger_idx_volatile_compressed,
1537 ptoa_64(compressed_page_count));
1538
1539 /* more non-volatile bytes in ledger */
1540 ledger_credit(owner->ledger,
1541 ledger_idx_nonvolatile,
1542 ptoa_64(resident_page_count - wired_page_count));
1543 /* more compressed non-volatile bytes in ledger */
1544 ledger_credit(owner->ledger,
1545 ledger_idx_nonvolatile_compressed,
1546 ptoa_64(compressed_page_count));
1547 if (do_footprint) {
1548 /* more footprint */
1549 ledger_credit(owner->ledger,
1550 task_ledgers.phys_footprint,
1551 ptoa_64(resident_page_count
1552 + compressed_page_count
1553 - wired_page_count));
1554 } else if (ledger_idx_composite != -1) {
1555 ledger_credit(owner->ledger,
1556 ledger_idx_composite,
1557 ptoa_64(resident_page_count
1558 + compressed_page_count
1559 - wired_page_count));
1560 }
1561 } else if (old_state == VM_PURGABLE_NONVOLATILE) {
1562 /* less non-volatile bytes in ledger */
1563 ledger_debit(owner->ledger,
1564 ledger_idx_nonvolatile,
1565 ptoa_64(resident_page_count - wired_page_count));
1566 /* less compressed non-volatile bytes in ledger */
1567 ledger_debit(owner->ledger,
1568 ledger_idx_nonvolatile_compressed,
1569 ptoa_64(compressed_page_count));
1570 if (do_footprint) {
1571 /* less footprint */
1572 ledger_debit(owner->ledger,
1573 task_ledgers.phys_footprint,
1574 ptoa_64(resident_page_count
1575 + compressed_page_count
1576 - wired_page_count));
1577 } else if (ledger_idx_composite != -1) {
1578 ledger_debit(owner->ledger,
1579 ledger_idx_composite,
1580 ptoa_64(resident_page_count
1581 + compressed_page_count
1582 - wired_page_count));
1583 }
1584
1585 /* more volatile bytes in ledger */
1586 ledger_credit(owner->ledger,
1587 ledger_idx_volatile,
1588 ptoa_64(resident_page_count - wired_page_count));
1589 /* more compressed volatile bytes in ledger */
1590 ledger_credit(owner->ledger,
1591 ledger_idx_volatile_compressed,
1592 ptoa_64(compressed_page_count));
1593 } else {
1594 panic("vm_purgeable_accounting(%p): "
1595 "unexpected old_state=%d\n",
1596 object, old_state);
1597 }
1598
1599 vm_object_lock_assert_exclusive(object);
1600 }
1601
1602 void
vm_purgeable_nonvolatile_owner_update(task_t owner,int delta)1603 vm_purgeable_nonvolatile_owner_update(
1604 task_t owner,
1605 int delta)
1606 {
1607 if (owner == NULL || delta == 0) {
1608 return;
1609 }
1610
1611 if (delta > 0) {
1612 assert(owner->task_nonvolatile_objects >= 0);
1613 OSAddAtomic(delta, &owner->task_nonvolatile_objects);
1614 assert(owner->task_nonvolatile_objects > 0);
1615 } else {
1616 assert(owner->task_nonvolatile_objects > delta);
1617 OSAddAtomic(delta, &owner->task_nonvolatile_objects);
1618 assert(owner->task_nonvolatile_objects >= 0);
1619 }
1620 }
1621
1622 void
vm_purgeable_volatile_owner_update(task_t owner,int delta)1623 vm_purgeable_volatile_owner_update(
1624 task_t owner,
1625 int delta)
1626 {
1627 if (owner == NULL || delta == 0) {
1628 return;
1629 }
1630
1631 if (delta > 0) {
1632 assert(owner->task_volatile_objects >= 0);
1633 OSAddAtomic(delta, &owner->task_volatile_objects);
1634 assert(owner->task_volatile_objects > 0);
1635 } else {
1636 assert(owner->task_volatile_objects > delta);
1637 OSAddAtomic(delta, &owner->task_volatile_objects);
1638 assert(owner->task_volatile_objects >= 0);
1639 }
1640 }
1641
1642 void
vm_object_owner_compressed_update(vm_object_t object,int delta)1643 vm_object_owner_compressed_update(
1644 vm_object_t object,
1645 int delta)
1646 {
1647 task_t owner;
1648 int ledger_idx_volatile;
1649 int ledger_idx_nonvolatile;
1650 int ledger_idx_volatile_compressed;
1651 int ledger_idx_nonvolatile_compressed;
1652 int ledger_idx_composite;
1653 int ledger_idx_external_wired;
1654 boolean_t do_footprint;
1655
1656 vm_object_lock_assert_exclusive(object);
1657
1658 owner = VM_OBJECT_OWNER(object);
1659
1660 if (delta == 0 ||
1661 !object->internal ||
1662 (object->purgable == VM_PURGABLE_DENY &&
1663 !object->vo_ledger_tag) ||
1664 owner == NULL) {
1665 /* not an owned purgeable (or tagged) VM object: nothing to update */
1666 return;
1667 }
1668
1669 vm_object_ledger_tag_ledgers(object,
1670 &ledger_idx_volatile,
1671 &ledger_idx_nonvolatile,
1672 &ledger_idx_volatile_compressed,
1673 &ledger_idx_nonvolatile_compressed,
1674 &ledger_idx_composite,
1675 &ledger_idx_external_wired,
1676 &do_footprint);
1677 assert(ledger_idx_external_wired == -1);
1678
1679 switch (object->purgable) {
1680 case VM_PURGABLE_DENY:
1681 /* not purgeable: must be ledger-tagged */
1682 assert(object->vo_ledger_tag != VM_LEDGER_TAG_NONE);
1683 OS_FALLTHROUGH;
1684 case VM_PURGABLE_NONVOLATILE:
1685 if (delta > 0) {
1686 ledger_credit(owner->ledger,
1687 ledger_idx_nonvolatile_compressed,
1688 ptoa_64(delta));
1689 if (do_footprint) {
1690 ledger_credit(owner->ledger,
1691 task_ledgers.phys_footprint,
1692 ptoa_64(delta));
1693 } else if (ledger_idx_composite != -1) {
1694 ledger_credit(owner->ledger,
1695 ledger_idx_composite,
1696 ptoa_64(delta));
1697 }
1698 } else {
1699 ledger_debit(owner->ledger,
1700 ledger_idx_nonvolatile_compressed,
1701 ptoa_64(-delta));
1702 if (do_footprint) {
1703 ledger_debit(owner->ledger,
1704 task_ledgers.phys_footprint,
1705 ptoa_64(-delta));
1706 } else if (ledger_idx_composite != -1) {
1707 ledger_debit(owner->ledger,
1708 ledger_idx_composite,
1709 ptoa_64(-delta));
1710 }
1711 }
1712 break;
1713 case VM_PURGABLE_VOLATILE:
1714 case VM_PURGABLE_EMPTY:
1715 if (delta > 0) {
1716 ledger_credit(owner->ledger,
1717 ledger_idx_volatile_compressed,
1718 ptoa_64(delta));
1719 } else {
1720 ledger_debit(owner->ledger,
1721 ledger_idx_volatile_compressed,
1722 ptoa_64(-delta));
1723 }
1724 break;
1725 default:
1726 panic("vm_purgeable_compressed_update(): "
1727 "unexpected purgable %d for object %p\n",
1728 object->purgable, object);
1729 }
1730 }
1731