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