osfmk/vm/vm_compressor.c

   1 /*
   2  * Copyright (c) 2000-2013 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_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. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #include <vm/vm_compressor.h>
  30
  31 #if CONFIG_PHANTOM_CACHE
  32 #include <vm/vm_phantom_cache.h>
  33 #endif
  34
  35 #include <vm/vm_map.h>
  36 #include <vm/vm_pageout.h>
  37 #include <vm/memory_object.h>
  38 #include <vm/vm_compressor_algorithms.h>
  39 #include <vm/vm_fault.h>
  40 #include <vm/vm_protos.h>
  41 #include <mach/mach_host.h>             /* for host_info() */
  42 #include <kern/ledger.h>
  43 #include <kern/policy_internal.h>
  44 #include <kern/thread_group.h>
  45 #include <san/kasan.h>
  46
  47 #if !CONFIG_EMBEDDED
  48 #include <i386/misc_protos.h>
  49 #endif
  50
  51 #include <IOKit/IOHibernatePrivate.h>
  52
  53 extern boolean_t vm_darkwake_mode;
  54
  55 #if POPCOUNT_THE_COMPRESSED_DATA
  56 boolean_t popcount_c_segs = TRUE;
  57
  58 static inline uint32_t
  59 vmc_pop(uintptr_t ins, int sz)
  60 {
  61         uint32_t rv = 0;
  62
  63         if (__probable(popcount_c_segs == FALSE)) {
  64                 return 0xDEAD707C;
  65         }
  66
  67         while (sz >= 16) {
  68                 uint32_t rv1, rv2;
  69                 uint64_t *ins64 = (uint64_t *) ins;
  70                 uint64_t *ins642 = (uint64_t *) (ins + 8);
  71                 rv1 = __builtin_popcountll(*ins64);
  72                 rv2 = __builtin_popcountll(*ins642);
  73                 rv += rv1 + rv2;
  74                 sz -= 16;
  75                 ins += 16;
  76         }
  77
  78         while (sz >= 4) {
  79                 uint32_t *ins32 = (uint32_t *) ins;
  80                 rv += __builtin_popcount(*ins32);
  81                 sz -= 4;
  82                 ins += 4;
  83         }
  84
  85         while (sz > 0) {
  86                 char *ins8 = (char *)ins;
  87                 rv += __builtin_popcount(*ins8);
  88                 sz--;
  89                 ins++;
  90         }
  91         return rv;
  92 }
  93 #endif
  94
  95 #if VALIDATE_C_SEGMENTS
  96 boolean_t validate_c_segs = TRUE;
  97 #endif
  98 /*
  99  * vm_compressor_mode has a heirarchy of control to set its value.
 100  * boot-args are checked first, then device-tree, and finally
 101  * the default value that is defined below. See vm_fault_init() for
 102  * the boot-arg & device-tree code.
 103  */
 104
 105 #if CONFIG_EMBEDDED
 106
 107 #if CONFIG_FREEZE
 108 int             vm_compressor_mode = VM_PAGER_FREEZER_DEFAULT;
 109
 110 void            *freezer_chead; /* The chead used to track c_segs allocated for the exclusive use of holding just one task's compressed memory.*/
 111 char            *freezer_compressor_scratch_buf = NULL;
 112
 113 extern int      c_freezer_swapout_page_count;      /* This count keeps track of the # of compressed pages holding just one task's compressed memory on the swapout queue. This count is used during each freeze i.e. on a per-task basis.*/
 114
 115 #else /* CONFIG_FREEZE */
 116 int             vm_compressor_mode = VM_PAGER_NOT_CONFIGURED;
 117 #endif /* CONFIG_FREEZE */
 118
 119 int             vm_scale = 1;
 120
 121 #else /* CONFIG_EMBEDDED */
 122 int             vm_compressor_mode = VM_PAGER_COMPRESSOR_WITH_SWAP;
 123 int             vm_scale = 16;
 124
 125 #endif /* CONFIG_EMBEDDED */
 126
 127 int             vm_compressor_is_active = 0;
 128 int             vm_compression_limit = 0;
 129 int             vm_compressor_available = 0;
 130
 131 extern void     vm_pageout_io_throttle(void);
 132
 133 #if CHECKSUM_THE_DATA || CHECKSUM_THE_SWAP || CHECKSUM_THE_COMPRESSED_DATA
 134 extern unsigned int hash_string(char *cp, int len);
 135 static unsigned int vmc_hash(char *, int);
 136 boolean_t checksum_c_segs = TRUE;
 137
 138 unsigned int
 139 vmc_hash(char *cp, int len)
 140 {
 141         if (__probable(checksum_c_segs == FALSE)) {
 142                 return 0xDEAD7A37;
 143         }
 144         return hash_string(cp, len);
 145 }
 146 #endif
 147
 148 #define UNPACK_C_SIZE(cs)       ((cs->c_size == (PAGE_SIZE-1)) ? PAGE_SIZE : cs->c_size)
 149 #define PACK_C_SIZE(cs, size)   (cs->c_size = ((size == PAGE_SIZE) ? PAGE_SIZE - 1 : size))
 150
 151
 152 struct c_sv_hash_entry {
 153         union {
 154                 struct  {
 155                         uint32_t        c_sv_he_ref;
 156                         uint32_t        c_sv_he_data;
 157                 } c_sv_he;
 158                 uint64_t        c_sv_he_record;
 159         } c_sv_he_un;
 160 };
 161
 162 #define he_ref  c_sv_he_un.c_sv_he.c_sv_he_ref
 163 #define he_data c_sv_he_un.c_sv_he.c_sv_he_data
 164 #define he_record c_sv_he_un.c_sv_he_record
 165
 166 #define C_SV_HASH_MAX_MISS      32
 167 #define C_SV_HASH_SIZE          ((1 << 10))
 168 #define C_SV_HASH_MASK          ((1 << 10) - 1)
 169 #define C_SV_CSEG_ID            ((1 << 22) - 1)
 170
 171
 172 union c_segu {
 173         c_segment_t     c_seg;
 174         uintptr_t       c_segno;
 175 };
 176
 177
 178
 179 #define C_SLOT_PACK_PTR(ptr)            (((uintptr_t)ptr - (uintptr_t) KERNEL_PMAP_HEAP_RANGE_START) >> 2)
 180 #define C_SLOT_UNPACK_PTR(cslot)        ((uintptr_t)(cslot->c_packed_ptr << 2) + (uintptr_t) KERNEL_PMAP_HEAP_RANGE_START)
 181
 182
 183 uint32_t        c_segment_count = 0;
 184 uint32_t        c_segment_count_max = 0;
 185
 186 uint64_t        c_generation_id = 0;
 187 uint64_t        c_generation_id_flush_barrier;
 188
 189
 190 #define         HIBERNATE_FLUSHING_SECS_TO_COMPLETE     120
 191
 192 boolean_t       hibernate_no_swapspace = FALSE;
 193 clock_sec_t     hibernate_flushing_deadline = 0;
 194
 195
 196 #if RECORD_THE_COMPRESSED_DATA
 197 char    *c_compressed_record_sbuf;
 198 char    *c_compressed_record_ebuf;
 199 char    *c_compressed_record_cptr;
 200 #endif
 201
 202
 203 queue_head_t    c_age_list_head;
 204 queue_head_t    c_swappedin_list_head;
 205 queue_head_t    c_swapout_list_head;
 206 queue_head_t    c_swapio_list_head;
 207 queue_head_t    c_swappedout_list_head;
 208 queue_head_t    c_swappedout_sparse_list_head;
 209 queue_head_t    c_major_list_head;
 210 queue_head_t    c_filling_list_head;
 211 queue_head_t    c_bad_list_head;
 212
 213 uint32_t        c_age_count = 0;
 214 uint32_t        c_swappedin_count = 0;
 215 uint32_t        c_swapout_count = 0;
 216 uint32_t        c_swapio_count = 0;
 217 uint32_t        c_swappedout_count = 0;
 218 uint32_t        c_swappedout_sparse_count = 0;
 219 uint32_t        c_major_count = 0;
 220 uint32_t        c_filling_count = 0;
 221 uint32_t        c_empty_count = 0;
 222 uint32_t        c_bad_count = 0;
 223
 224
 225 queue_head_t    c_minor_list_head;
 226 uint32_t        c_minor_count = 0;
 227
 228 int             c_overage_swapped_count = 0;
 229 int             c_overage_swapped_limit = 0;
 230
 231 int             c_seg_fixed_array_len;
 232 union  c_segu   *c_segments;
 233 vm_offset_t     c_buffers;
 234 vm_size_t       c_buffers_size;
 235 caddr_t         c_segments_next_page;
 236 boolean_t       c_segments_busy;
 237 uint32_t        c_segments_available;
 238 uint32_t        c_segments_limit;
 239 uint32_t        c_segments_nearing_limit;
 240
 241 uint32_t        c_segment_svp_in_hash;
 242 uint32_t        c_segment_svp_hash_succeeded;
 243 uint32_t        c_segment_svp_hash_failed;
 244 uint32_t        c_segment_svp_zero_compressions;
 245 uint32_t        c_segment_svp_nonzero_compressions;
 246 uint32_t        c_segment_svp_zero_decompressions;
 247 uint32_t        c_segment_svp_nonzero_decompressions;
 248
 249 uint32_t        c_segment_noncompressible_pages;
 250
 251 uint32_t        c_segment_pages_compressed;
 252 uint32_t        c_segment_pages_compressed_limit;
 253 uint32_t        c_segment_pages_compressed_nearing_limit;
 254 uint32_t        c_free_segno_head = (uint32_t)-1;
 255
 256 uint32_t        vm_compressor_minorcompact_threshold_divisor = 10;
 257 uint32_t        vm_compressor_majorcompact_threshold_divisor = 10;
 258 uint32_t        vm_compressor_unthrottle_threshold_divisor = 10;
 259 uint32_t        vm_compressor_catchup_threshold_divisor = 10;
 260
 261 uint32_t        vm_compressor_minorcompact_threshold_divisor_overridden = 0;
 262 uint32_t        vm_compressor_majorcompact_threshold_divisor_overridden = 0;
 263 uint32_t        vm_compressor_unthrottle_threshold_divisor_overridden = 0;
 264 uint32_t        vm_compressor_catchup_threshold_divisor_overridden = 0;
 265
 266 #define         C_SEGMENTS_PER_PAGE     (PAGE_SIZE / sizeof(union c_segu))
 267
 268
 269 lck_grp_attr_t  vm_compressor_lck_grp_attr;
 270 lck_attr_t      vm_compressor_lck_attr;
 271 lck_grp_t       vm_compressor_lck_grp;
 272 lck_mtx_t       *c_list_lock;
 273 lck_rw_t        c_master_lock;
 274 boolean_t       decompressions_blocked = FALSE;
 275
 276 zone_t          compressor_segment_zone;
 277 int             c_compressor_swap_trigger = 0;
 278
 279 uint32_t        compressor_cpus;
 280 char            *compressor_scratch_bufs;
 281 char            *kdp_compressor_scratch_buf;
 282 char            *kdp_compressor_decompressed_page;
 283 addr64_t        kdp_compressor_decompressed_page_paddr;
 284 ppnum_t         kdp_compressor_decompressed_page_ppnum;
 285
 286 clock_sec_t     start_of_sample_period_sec = 0;
 287 clock_nsec_t    start_of_sample_period_nsec = 0;
 288 clock_sec_t     start_of_eval_period_sec = 0;
 289 clock_nsec_t    start_of_eval_period_nsec = 0;
 290 uint32_t        sample_period_decompression_count = 0;
 291 uint32_t        sample_period_compression_count = 0;
 292 uint32_t        last_eval_decompression_count = 0;
 293 uint32_t        last_eval_compression_count = 0;
 294
 295 #define         DECOMPRESSION_SAMPLE_MAX_AGE            (60 * 30)
 296
 297 boolean_t       vm_swapout_ripe_segments = FALSE;
 298 uint32_t        vm_ripe_target_age = (60 * 60 * 48);
 299
 300 uint32_t        swapout_target_age = 0;
 301 uint32_t        age_of_decompressions_during_sample_period[DECOMPRESSION_SAMPLE_MAX_AGE];
 302 uint32_t        overage_decompressions_during_sample_period = 0;
 303
 304
 305 void            do_fastwake_warmup(queue_head_t *, boolean_t);
 306 boolean_t       fastwake_warmup = FALSE;
 307 boolean_t       fastwake_recording_in_progress = FALSE;
 308 clock_sec_t     dont_trim_until_ts = 0;
 309
 310 uint64_t        c_segment_warmup_count;
 311 uint64_t        first_c_segment_to_warm_generation_id = 0;
 312 uint64_t        last_c_segment_to_warm_generation_id = 0;
 313 boolean_t       hibernate_flushing = FALSE;
 314
 315 int64_t         c_segment_input_bytes __attribute__((aligned(8))) = 0;
 316 int64_t         c_segment_compressed_bytes __attribute__((aligned(8))) = 0;
 317 int64_t         compressor_bytes_used __attribute__((aligned(8))) = 0;
 318
 319
 320 struct c_sv_hash_entry c_segment_sv_hash_table[C_SV_HASH_SIZE]  __attribute__ ((aligned(8)));
 321
 322 static boolean_t compressor_needs_to_swap(void);
 323 static void vm_compressor_swap_trigger_thread(void);
 324 static void vm_compressor_do_delayed_compactions(boolean_t);
 325 static void vm_compressor_compact_and_swap(boolean_t);
 326 static void vm_compressor_age_swapped_in_segments(boolean_t);
 327
 328 #if !CONFIG_EMBEDDED
 329 static void vm_compressor_take_paging_space_action(void);
 330 #endif
 331
 332 void compute_swapout_target_age(void);
 333
 334 boolean_t c_seg_major_compact(c_segment_t, c_segment_t);
 335 boolean_t c_seg_major_compact_ok(c_segment_t, c_segment_t);
 336
 337 int  c_seg_minor_compaction_and_unlock(c_segment_t, boolean_t);
 338 int  c_seg_do_minor_compaction_and_unlock(c_segment_t, boolean_t, boolean_t, boolean_t);
 339 void c_seg_try_minor_compaction_and_unlock(c_segment_t c_seg);
 340
 341 void c_seg_move_to_sparse_list(c_segment_t);
 342 void c_seg_insert_into_q(queue_head_t *, c_segment_t);
 343
 344 uint64_t vm_available_memory(void);
 345 uint64_t vm_compressor_pages_compressed(void);
 346
 347 /*
 348  * indicate the need to do a major compaction if
 349  * the overall set of in-use compression segments
 350  * becomes sparse... on systems that support pressure
 351  * driven swapping, this will also cause swapouts to
 352  * be initiated.
 353  */
 354 static inline boolean_t
 355 vm_compressor_needs_to_major_compact()
 356 {
 357         uint32_t        incore_seg_count;
 358
 359         incore_seg_count = c_segment_count - c_swappedout_count - c_swappedout_sparse_count;
 360
 361         if ((c_segment_count >= (c_segments_nearing_limit / 8)) &&
 362             ((incore_seg_count * C_SEG_MAX_PAGES) - VM_PAGE_COMPRESSOR_COUNT) >
 363             ((incore_seg_count / 8) * C_SEG_MAX_PAGES)) {
 364                 return 1;
 365         }
 366         return 0;
 367 }
 368
 369
 370 uint64_t
 371 vm_available_memory(void)
 372 {
 373         return ((uint64_t)AVAILABLE_NON_COMPRESSED_MEMORY) * PAGE_SIZE_64;
 374 }
 375
 376
 377 uint64_t
 378 vm_compressor_pages_compressed(void)
 379 {
 380         return c_segment_pages_compressed * PAGE_SIZE_64;
 381 }
 382
 383
 384 boolean_t
 385 vm_compressor_low_on_space(void)
 386 {
 387         if ((c_segment_pages_compressed > c_segment_pages_compressed_nearing_limit) ||
 388             (c_segment_count > c_segments_nearing_limit)) {
 389                 return TRUE;
 390         }
 391
 392         return FALSE;
 393 }
 394
 395
 396 boolean_t
 397 vm_compressor_out_of_space(void)
 398 {
 399         if ((c_segment_pages_compressed >= c_segment_pages_compressed_limit) ||
 400             (c_segment_count >= c_segments_limit)) {
 401                 return TRUE;
 402         }
 403
 404         return FALSE;
 405 }
 406
 407
 408 int
 409 vm_wants_task_throttled(task_t task)
 410 {
 411         if (task == kernel_task) {
 412                 return 0;
 413         }
 414
 415         if (VM_CONFIG_SWAP_IS_ACTIVE) {
 416                 if ((vm_compressor_low_on_space() || HARD_THROTTLE_LIMIT_REACHED()) &&
 417                     (unsigned int)pmap_compressed(task->map->pmap) > (c_segment_pages_compressed / 4)) {
 418                         return 1;
 419                 }
 420         }
 421         return 0;
 422 }
 423
 424
 425 #if DEVELOPMENT || DEBUG
 426 boolean_t kill_on_no_paging_space = FALSE; /* On compressor/swap exhaustion, kill the largest process regardless of
 427                                             * its chosen process policy. Controlled by a boot-arg of the same name. */
 428 #endif /* DEVELOPMENT || DEBUG */
 429
 430 #if !CONFIG_EMBEDDED
 431
 432 static uint32_t no_paging_space_action_in_progress = 0;
 433 extern void memorystatus_send_low_swap_note(void);
 434
 435 static void
 436 vm_compressor_take_paging_space_action(void)
 437 {
 438         if (no_paging_space_action_in_progress == 0) {
 439                 if (OSCompareAndSwap(0, 1, (UInt32 *)&no_paging_space_action_in_progress)) {
 440                         if (no_paging_space_action()) {
 441 #if DEVELOPMENT || DEBUG
 442                                 if (kill_on_no_paging_space == TRUE) {
 443                                         /*
 444                                          * Since we are choosing to always kill a process, we don't need the
 445                                          * "out of application memory" dialog box in this mode. And, hence we won't
 446                                          * send the knote.
 447                                          */
 448                                         no_paging_space_action_in_progress = 0;
 449                                         return;
 450                                 }
 451 #endif /* DEVELOPMENT || DEBUG */
 452                                 memorystatus_send_low_swap_note();
 453                         }
 454
 455                         no_paging_space_action_in_progress = 0;
 456                 }
 457         }
 458 }
 459 #endif /* !CONFIG_EMBEDDED */
 460
 461
 462 void
 463 vm_compressor_init_locks(void)
 464 {
 465         lck_grp_attr_setdefault(&vm_compressor_lck_grp_attr);
 466         lck_grp_init(&vm_compressor_lck_grp, "vm_compressor", &vm_compressor_lck_grp_attr);
 467         lck_attr_setdefault(&vm_compressor_lck_attr);
 468
 469         lck_rw_init(&c_master_lock, &vm_compressor_lck_grp, &vm_compressor_lck_attr);
 470 }
 471
 472
 473 void
 474 vm_decompressor_lock(void)
 475 {
 476         PAGE_REPLACEMENT_ALLOWED(TRUE);
 477
 478         decompressions_blocked = TRUE;
 479
 480         PAGE_REPLACEMENT_ALLOWED(FALSE);
 481 }
 482
 483 void
 484 vm_decompressor_unlock(void)
 485 {
 486         PAGE_REPLACEMENT_ALLOWED(TRUE);
 487
 488         decompressions_blocked = FALSE;
 489
 490         PAGE_REPLACEMENT_ALLOWED(FALSE);
 491
 492         thread_wakeup((event_t)&decompressions_blocked);
 493 }
 494
 495 static inline void
 496 cslot_copy(c_slot_t cdst, c_slot_t csrc)
 497 {
 498 #if CHECKSUM_THE_DATA
 499         cdst->c_hash_data = csrc->c_hash_data;
 500 #endif
 501 #if CHECKSUM_THE_COMPRESSED_DATA
 502         cdst->c_hash_compressed_data = csrc->c_hash_compressed_data;
 503 #endif
 504 #if POPCOUNT_THE_COMPRESSED_DATA
 505         cdst->c_pop_cdata = csrc->c_pop_cdata;
 506 #endif
 507         cdst->c_size = csrc->c_size;
 508         cdst->c_packed_ptr = csrc->c_packed_ptr;
 509 #if defined(__arm__) || defined(__arm64__)
 510         cdst->c_codec = csrc->c_codec;
 511 #endif
 512 }
 513
 514 vm_map_t compressor_map;
 515 uint64_t compressor_pool_max_size;
 516 uint64_t compressor_pool_size;
 517 uint32_t compressor_pool_multiplier;
 518
 519 #if DEVELOPMENT || DEBUG
 520 /*
 521  * Compressor segments are write-protected in development/debug
 522  * kernels to help debug memory corruption.
 523  * In cases where performance is a concern, this can be disabled
 524  * via the boot-arg "-disable_cseg_write_protection".
 525  */
 526 boolean_t write_protect_c_segs = TRUE;
 527 int vm_compressor_test_seg_wp;
 528 uint32_t vm_ktrace_enabled;
 529 #endif /* DEVELOPMENT || DEBUG */
 530
 531 void
 532 vm_compressor_init(void)
 533 {
 534         thread_t        thread;
 535         struct c_slot   cs_dummy;
 536         c_slot_t cs  = &cs_dummy;
 537         int             c_segment_min_size;
 538         int             c_segment_padded_size;
 539         int             attempts = 1;
 540         kern_return_t   retval = KERN_SUCCESS;
 541         vm_offset_t     start_addr = 0;
 542         vm_size_t       c_segments_arr_size = 0, compressor_submap_size = 0;
 543         vm_map_kernel_flags_t vmk_flags;
 544 #if RECORD_THE_COMPRESSED_DATA
 545         vm_size_t       c_compressed_record_sbuf_size = 0;
 546 #endif /* RECORD_THE_COMPRESSED_DATA */
 547
 548 #if DEVELOPMENT || DEBUG
 549         char bootarg_name[32];
 550         if (PE_parse_boot_argn("-kill_on_no_paging_space", bootarg_name, sizeof(bootarg_name))) {
 551                 kill_on_no_paging_space = TRUE;
 552         }
 553         if (PE_parse_boot_argn("-disable_cseg_write_protection", bootarg_name, sizeof(bootarg_name))) {
 554                 write_protect_c_segs = FALSE;
 555         }
 556         int vmcval = 1;
 557         PE_parse_boot_argn("vm_compressor_validation", &vmcval, sizeof(vmcval));
 558
 559         if (kern_feature_override(KF_COMPRSV_OVRD)) {
 560                 vmcval = 0;
 561         }
 562         if (vmcval == 0) {
 563 #if POPCOUNT_THE_COMPRESSED_DATA
 564                 popcount_c_segs = FALSE;
 565 #endif
 566 #if CHECKSUM_THE_DATA || CHECKSUM_THE_COMPRESSED_DATA
 567                 checksum_c_segs = FALSE;
 568 #endif
 569 #if VALIDATE_C_SEGMENTS
 570                 validate_c_segs = FALSE;
 571 #endif
 572                 write_protect_c_segs = FALSE;
 573         }
 574 #endif /* DEVELOPMENT || DEBUG */
 575
 576         /*
 577          * ensure that any pointer that gets created from
 578          * the vm_page zone can be packed properly
 579          */
 580         cs->c_packed_ptr = C_SLOT_PACK_PTR(zone_map_min_address);
 581
 582         if (C_SLOT_UNPACK_PTR(cs) != (uintptr_t)zone_map_min_address) {
 583                 panic("C_SLOT_UNPACK_PTR failed on zone_map_min_address - %p", (void *)zone_map_min_address);
 584         }
 585
 586         cs->c_packed_ptr = C_SLOT_PACK_PTR(zone_map_max_address);
 587
 588         if (C_SLOT_UNPACK_PTR(cs) != (uintptr_t)zone_map_max_address) {
 589                 panic("C_SLOT_UNPACK_PTR failed on zone_map_max_address - %p", (void *)zone_map_max_address);
 590         }
 591
 592
 593         assert((C_SEGMENTS_PER_PAGE * sizeof(union c_segu)) == PAGE_SIZE);
 594
 595         PE_parse_boot_argn("vm_compression_limit", &vm_compression_limit, sizeof(vm_compression_limit));
 596
 597 #ifdef CONFIG_EMBEDDED
 598         vm_compressor_minorcompact_threshold_divisor = 20;
 599         vm_compressor_majorcompact_threshold_divisor = 30;
 600         vm_compressor_unthrottle_threshold_divisor = 40;
 601         vm_compressor_catchup_threshold_divisor = 60;
 602 #else
 603         if (max_mem <= (3ULL * 1024ULL * 1024ULL * 1024ULL)) {
 604                 vm_compressor_minorcompact_threshold_divisor = 11;
 605                 vm_compressor_majorcompact_threshold_divisor = 13;
 606                 vm_compressor_unthrottle_threshold_divisor = 20;
 607                 vm_compressor_catchup_threshold_divisor = 35;
 608         } else {
 609                 vm_compressor_minorcompact_threshold_divisor = 20;
 610                 vm_compressor_majorcompact_threshold_divisor = 25;
 611                 vm_compressor_unthrottle_threshold_divisor = 35;
 612                 vm_compressor_catchup_threshold_divisor = 50;
 613         }
 614 #endif
 615         /*
 616          * vm_page_init_lck_grp is now responsible for calling vm_compressor_init_locks
 617          * c_master_lock needs to be available early so that "vm_page_find_contiguous" can
 618          * use PAGE_REPLACEMENT_ALLOWED to coordinate with the compressor.
 619          */
 620
 621         c_list_lock = lck_mtx_alloc_init(&vm_compressor_lck_grp, &vm_compressor_lck_attr);
 622
 623         queue_init(&c_bad_list_head);
 624         queue_init(&c_age_list_head);
 625         queue_init(&c_minor_list_head);
 626         queue_init(&c_major_list_head);
 627         queue_init(&c_filling_list_head);
 628         queue_init(&c_swapout_list_head);
 629         queue_init(&c_swapio_list_head);
 630         queue_init(&c_swappedin_list_head);
 631         queue_init(&c_swappedout_list_head);
 632         queue_init(&c_swappedout_sparse_list_head);
 633
 634         c_free_segno_head = -1;
 635         c_segments_available = 0;
 636
 637         if (vm_compression_limit) {
 638                 compressor_pool_size = (uint64_t)vm_compression_limit * PAGE_SIZE_64;
 639         }
 640
 641         compressor_pool_max_size = C_SEG_MAX_LIMIT;
 642         compressor_pool_max_size *= C_SEG_BUFSIZE;
 643
 644 #if defined(__x86_64__)
 645
 646         if (vm_compression_limit == 0) {
 647                 if (max_mem <= (4ULL * 1024ULL * 1024ULL * 1024ULL)) {
 648                         compressor_pool_size = 16ULL * max_mem;
 649                 } else if (max_mem <= (8ULL * 1024ULL * 1024ULL * 1024ULL)) {
 650                         compressor_pool_size = 8ULL * max_mem;
 651                 } else if (max_mem <= (32ULL * 1024ULL * 1024ULL * 1024ULL)) {
 652                         compressor_pool_size = 4ULL * max_mem;
 653                 } else {
 654                         compressor_pool_size = 2ULL * max_mem;
 655                 }
 656         }
 657         if (max_mem <= (8ULL * 1024ULL * 1024ULL * 1024ULL)) {
 658                 compressor_pool_multiplier = 1;
 659         } else if (max_mem <= (32ULL * 1024ULL * 1024ULL * 1024ULL)) {
 660                 compressor_pool_multiplier = 2;
 661         } else {
 662                 compressor_pool_multiplier = 4;
 663         }
 664
 665 #elif defined(__arm__)
 666
 667 #define VM_RESERVE_SIZE                 (1024 * 1024 * 256)
 668 #define MAX_COMPRESSOR_POOL_SIZE        (1024 * 1024 * 450)
 669
 670         if (compressor_pool_max_size > MAX_COMPRESSOR_POOL_SIZE) {
 671                 compressor_pool_max_size = MAX_COMPRESSOR_POOL_SIZE;
 672         }
 673
 674         if (vm_compression_limit == 0) {
 675                 compressor_pool_size = ((kernel_map->max_offset - kernel_map->min_offset) - kernel_map->size) - VM_RESERVE_SIZE;
 676         }
 677         compressor_pool_multiplier = 1;
 678 #else
 679         if (compressor_pool_max_size > max_mem) {
 680                 compressor_pool_max_size = max_mem;
 681         }
 682
 683         if (vm_compression_limit == 0) {
 684                 compressor_pool_size = max_mem;
 685         }
 686         compressor_pool_multiplier = 1;
 687 #endif
 688         if (compressor_pool_size > compressor_pool_max_size) {
 689                 compressor_pool_size = compressor_pool_max_size;
 690         }
 691
 692 try_again:
 693         c_segments_limit = (uint32_t)(compressor_pool_size / (vm_size_t)(C_SEG_ALLOCSIZE));
 694         c_segments_nearing_limit = (uint32_t)(((uint64_t)c_segments_limit * 98ULL) / 100ULL);
 695
 696         c_segment_pages_compressed_limit = (c_segments_limit * (C_SEG_BUFSIZE / PAGE_SIZE) * compressor_pool_multiplier);
 697
 698         if (c_segment_pages_compressed_limit < (uint32_t)(max_mem / PAGE_SIZE)) {
 699                 c_segment_pages_compressed_limit = (uint32_t)(max_mem / PAGE_SIZE);
 700         }
 701
 702         c_segment_pages_compressed_nearing_limit = (uint32_t)(((uint64_t)c_segment_pages_compressed_limit * 98ULL) / 100ULL);
 703
 704         /*
 705          * Submap needs space for:
 706          * - c_segments
 707          * - c_buffers
 708          * - swap reclaimations -- C_SEG_BUFSIZE
 709          */
 710         c_segments_arr_size = vm_map_round_page((sizeof(union c_segu) * c_segments_limit), VM_MAP_PAGE_MASK(kernel_map));
 711         c_buffers_size = vm_map_round_page(((vm_size_t)C_SEG_ALLOCSIZE * (vm_size_t)c_segments_limit), VM_MAP_PAGE_MASK(kernel_map));
 712
 713         compressor_submap_size = c_segments_arr_size + c_buffers_size + C_SEG_BUFSIZE;
 714
 715 #if RECORD_THE_COMPRESSED_DATA
 716         c_compressed_record_sbuf_size = (vm_size_t)C_SEG_ALLOCSIZE + (PAGE_SIZE * 2);
 717         compressor_submap_size += c_compressed_record_sbuf_size;
 718 #endif /* RECORD_THE_COMPRESSED_DATA */
 719
 720         vmk_flags = VM_MAP_KERNEL_FLAGS_NONE;
 721         vmk_flags.vmkf_permanent = TRUE;
 722         retval = kmem_suballoc(kernel_map, &start_addr, compressor_submap_size,
 723             FALSE, VM_FLAGS_ANYWHERE, vmk_flags, VM_KERN_MEMORY_COMPRESSOR,
 724             &compressor_map);
 725
 726         if (retval != KERN_SUCCESS) {
 727                 if (++attempts > 3) {
 728                         panic("vm_compressor_init: kmem_suballoc failed - 0x%llx", (uint64_t)compressor_submap_size);
 729                 }
 730
 731                 compressor_pool_size = compressor_pool_size / 2;
 732
 733                 kprintf("retrying creation of the compressor submap at 0x%llx bytes\n", compressor_pool_size);
 734                 goto try_again;
 735         }
 736         if (kernel_memory_allocate(compressor_map, (vm_offset_t *)(&c_segments), (sizeof(union c_segu) * c_segments_limit), 0, KMA_KOBJECT | KMA_VAONLY | KMA_PERMANENT, VM_KERN_MEMORY_COMPRESSOR) != KERN_SUCCESS) {
 737                 panic("vm_compressor_init: kernel_memory_allocate failed - c_segments\n");
 738         }
 739         if (kernel_memory_allocate(compressor_map, &c_buffers, c_buffers_size, 0, KMA_COMPRESSOR | KMA_VAONLY | KMA_PERMANENT, VM_KERN_MEMORY_COMPRESSOR) != KERN_SUCCESS) {
 740                 panic("vm_compressor_init: kernel_memory_allocate failed - c_buffers\n");
 741         }
 742
 743
 744         c_segment_min_size = sizeof(struct c_segment) + (C_SEG_SLOT_VAR_ARRAY_MIN_LEN * sizeof(struct c_slot));
 745
 746         for (c_segment_padded_size = 128; c_segment_padded_size < c_segment_min_size; c_segment_padded_size = c_segment_padded_size << 1) {
 747                 ;
 748         }
 749
 750         compressor_segment_zone = zinit(c_segment_padded_size, c_segments_limit * c_segment_padded_size, PAGE_SIZE, "compressor_segment");
 751         zone_change(compressor_segment_zone, Z_CALLERACCT, FALSE);
 752         zone_change(compressor_segment_zone, Z_NOENCRYPT, TRUE);
 753
 754         c_seg_fixed_array_len = (c_segment_padded_size - sizeof(struct c_segment)) / sizeof(struct c_slot);
 755
 756         c_segments_busy = FALSE;
 757
 758         c_segments_next_page = (caddr_t)c_segments;
 759         vm_compressor_algorithm_init();
 760
 761         {
 762                 host_basic_info_data_t hinfo;
 763                 mach_msg_type_number_t count = HOST_BASIC_INFO_COUNT;
 764
 765 #define BSD_HOST 1
 766                 host_info((host_t)BSD_HOST, HOST_BASIC_INFO, (host_info_t)&hinfo, &count);
 767
 768                 compressor_cpus = hinfo.max_cpus;
 769                 compressor_scratch_bufs = kalloc_tag(compressor_cpus * vm_compressor_get_decode_scratch_size(), VM_KERN_MEMORY_COMPRESSOR);
 770
 771                 kdp_compressor_scratch_buf = kalloc_tag(vm_compressor_get_decode_scratch_size(), VM_KERN_MEMORY_COMPRESSOR);
 772
 773                 /*
 774                  * kdp_compressor_decompressed_page must be page aligned because we access
 775                  * it through the physical apperture by page number. kalloc() does not
 776                  * guarantee alignment.
 777                  */
 778                 vm_offset_t addr;
 779                 if (kernel_memory_allocate(kernel_map, &addr, PAGE_SIZE, 0, KMA_KOBJECT, VM_KERN_MEMORY_COMPRESSOR) != KERN_SUCCESS) {
 780                         panic("vm_compressor_init: kernel_memory_allocate failed - kdp_compressor_decompressed_page\n");
 781                 }
 782                 assert((addr & PAGE_MASK) == 0);
 783                 kdp_compressor_decompressed_page = (void *)addr;
 784                 kdp_compressor_decompressed_page_paddr = kvtophys((vm_offset_t)kdp_compressor_decompressed_page);
 785                 kdp_compressor_decompressed_page_ppnum = (ppnum_t) atop(kdp_compressor_decompressed_page_paddr);
 786         }
 787 #if CONFIG_FREEZE
 788         freezer_compressor_scratch_buf = kalloc_tag(vm_compressor_get_encode_scratch_size(), VM_KERN_MEMORY_COMPRESSOR);
 789 #endif
 790
 791 #if RECORD_THE_COMPRESSED_DATA
 792         if (kernel_memory_allocate(compressor_map, (vm_offset_t *)&c_compressed_record_sbuf, c_compressed_record_sbuf_size, 0, KMA_KOBJECT, VM_KERN_MEMORY_COMPRESSOR) != KERN_SUCCESS) {
 793                 panic("vm_compressor_init: kernel_memory_allocate failed - c_compressed_record_sbuf\n");
 794         }
 795
 796         c_compressed_record_cptr = c_compressed_record_sbuf;
 797         c_compressed_record_ebuf = c_compressed_record_sbuf + c_compressed_record_sbuf_size;
 798 #endif
 799
 800         if (kernel_thread_start_priority((thread_continue_t)vm_compressor_swap_trigger_thread, NULL,
 801             BASEPRI_VM, &thread) != KERN_SUCCESS) {
 802                 panic("vm_compressor_swap_trigger_thread: create failed");
 803         }
 804         thread_deallocate(thread);
 805
 806         if (vm_pageout_internal_start() != KERN_SUCCESS) {
 807                 panic("vm_compressor_init: Failed to start the internal pageout thread.\n");
 808         }
 809         if (VM_CONFIG_SWAP_IS_PRESENT) {
 810                 vm_compressor_swap_init();
 811         }
 812
 813         if (VM_CONFIG_COMPRESSOR_IS_ACTIVE) {
 814                 vm_compressor_is_active = 1;
 815         }
 816
 817 #if CONFIG_FREEZE
 818         memorystatus_freeze_enabled = TRUE;
 819 #endif /* CONFIG_FREEZE */
 820
 821         vm_compressor_available = 1;
 822
 823         vm_page_reactivate_all_throttled();
 824 }
 825
 826
 827 #if VALIDATE_C_SEGMENTS
 828
 829 static void
 830 c_seg_validate(c_segment_t c_seg, boolean_t must_be_compact)
 831 {
 832         int             c_indx;
 833         int32_t         bytes_used;
 834         uint32_t        c_rounded_size;
 835         uint32_t        c_size;
 836         c_slot_t        cs;
 837
 838         if (__probable(validate_c_segs == FALSE)) {
 839                 return;
 840         }
 841         if (c_seg->c_firstemptyslot < c_seg->c_nextslot) {
 842                 c_indx = c_seg->c_firstemptyslot;
 843                 cs = C_SEG_SLOT_FROM_INDEX(c_seg, c_indx);
 844
 845                 if (cs == NULL) {
 846                         panic("c_seg_validate:  no slot backing c_firstemptyslot");
 847                 }
 848
 849                 if (cs->c_size) {
 850                         panic("c_seg_validate:  c_firstemptyslot has non-zero size (%d)\n", cs->c_size);
 851                 }
 852         }
 853         bytes_used = 0;
 854
 855         for (c_indx = 0; c_indx < c_seg->c_nextslot; c_indx++) {
 856                 cs = C_SEG_SLOT_FROM_INDEX(c_seg, c_indx);
 857
 858                 c_size = UNPACK_C_SIZE(cs);
 859
 860                 c_rounded_size = (c_size + C_SEG_OFFSET_ALIGNMENT_MASK) & ~C_SEG_OFFSET_ALIGNMENT_MASK;
 861
 862                 bytes_used += c_rounded_size;
 863
 864 #if CHECKSUM_THE_COMPRESSED_DATA
 865                 unsigned csvhash;
 866                 if (c_size && cs->c_hash_compressed_data != (csvhash = vmc_hash((char *)&c_seg->c_store.c_buffer[cs->c_offset], c_size))) {
 867                         addr64_t csvphys = kvtophys((vm_offset_t)&c_seg->c_store.c_buffer[cs->c_offset]);
 868                         panic("Compressed data doesn't match original %p phys: 0x%llx %d %p %d %d 0x%x 0x%x", c_seg, csvphys, cs->c_offset, cs, c_indx, c_size, cs->c_hash_compressed_data, csvhash);
 869                 }
 870 #endif
 871 #if POPCOUNT_THE_COMPRESSED_DATA
 872                 unsigned csvpop;
 873                 if (c_size) {
 874                         uintptr_t csvaddr = (uintptr_t) &c_seg->c_store.c_buffer[cs->c_offset];
 875                         if (cs->c_pop_cdata != (csvpop = vmc_pop(csvaddr, c_size))) {
 876                                 panic("Compressed data popcount doesn't match original, bit distance: %d %p (phys: %p) %p %p 0x%llx 0x%x 0x%x 0x%x", (csvpop - cs->c_pop_cdata), (void *)csvaddr, (void *) kvtophys(csvaddr), c_seg, cs, cs->c_offset, c_size, csvpop, cs->c_pop_cdata);
 877                         }
 878                 }
 879 #endif
 880         }
 881
 882         if (bytes_used != c_seg->c_bytes_used) {
 883                 panic("c_seg_validate: bytes_used mismatch - found %d, segment has %d\n", bytes_used, c_seg->c_bytes_used);
 884         }
 885
 886         if (c_seg->c_bytes_used > C_SEG_OFFSET_TO_BYTES((int32_t)c_seg->c_nextoffset)) {
 887                 panic("c_seg_validate: c_bytes_used > c_nextoffset - c_nextoffset = %d,  c_bytes_used = %d\n",
 888                     (int32_t)C_SEG_OFFSET_TO_BYTES((int32_t)c_seg->c_nextoffset), c_seg->c_bytes_used);
 889         }
 890
 891         if (must_be_compact) {
 892                 if (c_seg->c_bytes_used != C_SEG_OFFSET_TO_BYTES((int32_t)c_seg->c_nextoffset)) {
 893                         panic("c_seg_validate: c_bytes_used doesn't match c_nextoffset - c_nextoffset = %d,  c_bytes_used = %d\n",
 894                             (int32_t)C_SEG_OFFSET_TO_BYTES((int32_t)c_seg->c_nextoffset), c_seg->c_bytes_used);
 895                 }
 896         }
 897 }
 898
 899 #endif
 900
 901
 902 void
 903 c_seg_need_delayed_compaction(c_segment_t c_seg, boolean_t c_list_lock_held)
 904 {
 905         boolean_t       clear_busy = FALSE;
 906
 907         if (c_list_lock_held == FALSE) {
 908                 if (!lck_mtx_try_lock_spin_always(c_list_lock)) {
 909                         C_SEG_BUSY(c_seg);
 910
 911                         lck_mtx_unlock_always(&c_seg->c_lock);
 912                         lck_mtx_lock_spin_always(c_list_lock);
 913                         lck_mtx_lock_spin_always(&c_seg->c_lock);
 914
 915                         clear_busy = TRUE;
 916                 }
 917         }
 918         assert(c_seg->c_state != C_IS_FILLING);
 919
 920         if (!c_seg->c_on_minorcompact_q && !(C_SEG_IS_ON_DISK_OR_SOQ(c_seg))) {
 921                 queue_enter(&c_minor_list_head, c_seg, c_segment_t, c_list);
 922                 c_seg->c_on_minorcompact_q = 1;
 923                 c_minor_count++;
 924         }
 925         if (c_list_lock_held == FALSE) {
 926                 lck_mtx_unlock_always(c_list_lock);
 927         }
 928
 929         if (clear_busy == TRUE) {
 930                 C_SEG_WAKEUP_DONE(c_seg);
 931         }
 932 }
 933
 934
 935 unsigned int c_seg_moved_to_sparse_list = 0;
 936
 937 void
 938 c_seg_move_to_sparse_list(c_segment_t c_seg)
 939 {
 940         boolean_t       clear_busy = FALSE;
 941
 942         if (!lck_mtx_try_lock_spin_always(c_list_lock)) {
 943                 C_SEG_BUSY(c_seg);
 944
 945                 lck_mtx_unlock_always(&c_seg->c_lock);
 946                 lck_mtx_lock_spin_always(c_list_lock);
 947                 lck_mtx_lock_spin_always(&c_seg->c_lock);
 948
 949                 clear_busy = TRUE;
 950         }
 951         c_seg_switch_state(c_seg, C_ON_SWAPPEDOUTSPARSE_Q, FALSE);
 952
 953         c_seg_moved_to_sparse_list++;
 954
 955         lck_mtx_unlock_always(c_list_lock);
 956
 957         if (clear_busy == TRUE) {
 958                 C_SEG_WAKEUP_DONE(c_seg);
 959         }
 960 }
 961
 962
 963 void
 964 c_seg_insert_into_q(queue_head_t *qhead, c_segment_t c_seg)
 965 {
 966         c_segment_t c_seg_next;
 967
 968         if (queue_empty(qhead)) {
 969                 queue_enter(qhead, c_seg, c_segment_t, c_age_list);
 970         } else {
 971                 c_seg_next = (c_segment_t)queue_first(qhead);
 972
 973                 while (TRUE) {
 974                         if (c_seg->c_generation_id < c_seg_next->c_generation_id) {
 975                                 queue_insert_before(qhead, c_seg, c_seg_next, c_segment_t, c_age_list);
 976                                 break;
 977                         }
 978                         c_seg_next = (c_segment_t) queue_next(&c_seg_next->c_age_list);
 979
 980                         if (queue_end(qhead, (queue_entry_t) c_seg_next)) {
 981                                 queue_enter(qhead, c_seg, c_segment_t, c_age_list);
 982                                 break;
 983                         }
 984                 }
 985         }
 986 }
 987
 988
 989 int try_minor_compaction_failed = 0;
 990 int try_minor_compaction_succeeded = 0;
 991
 992 void
 993 c_seg_try_minor_compaction_and_unlock(c_segment_t c_seg)
 994 {
 995         assert(c_seg->c_on_minorcompact_q);
 996         /*
 997          * c_seg is currently on the delayed minor compaction
 998          * queue and we have c_seg locked... if we can get the
 999          * c_list_lock w/o blocking (if we blocked we could deadlock
1000          * because the lock order is c_list_lock then c_seg's lock)
1001          * we'll pull it from the delayed list and free it directly
1002          */
1003         if (!lck_mtx_try_lock_spin_always(c_list_lock)) {
1004                 /*
1005                  * c_list_lock is held, we need to bail
1006                  */
1007                 try_minor_compaction_failed++;
1008
1009                 lck_mtx_unlock_always(&c_seg->c_lock);
1010         } else {
1011                 try_minor_compaction_succeeded++;
1012
1013                 C_SEG_BUSY(c_seg);
1014                 c_seg_do_minor_compaction_and_unlock(c_seg, TRUE, FALSE, FALSE);
1015         }
1016 }
1017
1018
1019 int
1020 c_seg_do_minor_compaction_and_unlock(c_segment_t c_seg, boolean_t clear_busy, boolean_t need_list_lock, boolean_t disallow_page_replacement)
1021 {
1022         int     c_seg_freed;
1023
1024         assert(c_seg->c_busy);
1025         assert(!C_SEG_IS_ON_DISK_OR_SOQ(c_seg));
1026
1027         /*
1028          * check for the case that can occur when we are not swapping
1029          * and this segment has been major compacted in the past
1030          * and moved to the majorcompact q to remove it from further
1031          * consideration... if the occupancy falls too low we need
1032          * to put it back on the age_q so that it will be considered
1033          * in the next major compaction sweep... if we don't do this
1034          * we will eventually run into the c_segments_limit
1035          */
1036         if (c_seg->c_state == C_ON_MAJORCOMPACT_Q && C_SEG_SHOULD_MAJORCOMPACT_NOW(c_seg)) {
1037                 c_seg_switch_state(c_seg, C_ON_AGE_Q, FALSE);
1038         }
1039         if (!c_seg->c_on_minorcompact_q) {
1040                 if (clear_busy == TRUE) {
1041                         C_SEG_WAKEUP_DONE(c_seg);
1042                 }
1043
1044                 lck_mtx_unlock_always(&c_seg->c_lock);
1045
1046                 return 0;
1047         }
1048         queue_remove(&c_minor_list_head, c_seg, c_segment_t, c_list);
1049         c_seg->c_on_minorcompact_q = 0;
1050         c_minor_count--;
1051
1052         lck_mtx_unlock_always(c_list_lock);
1053
1054         if (disallow_page_replacement == TRUE) {
1055                 lck_mtx_unlock_always(&c_seg->c_lock);
1056
1057                 PAGE_REPLACEMENT_DISALLOWED(TRUE);
1058
1059                 lck_mtx_lock_spin_always(&c_seg->c_lock);
1060         }
1061         c_seg_freed = c_seg_minor_compaction_and_unlock(c_seg, clear_busy);
1062
1063         if (disallow_page_replacement == TRUE) {
1064                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
1065         }
1066
1067         if (need_list_lock == TRUE) {
1068                 lck_mtx_lock_spin_always(c_list_lock);
1069         }
1070
1071         return c_seg_freed;
1072 }
1073
1074
1075 void
1076 c_seg_wait_on_busy(c_segment_t c_seg)
1077 {
1078         c_seg->c_wanted = 1;
1079         assert_wait((event_t) (c_seg), THREAD_UNINT);
1080
1081         lck_mtx_unlock_always(&c_seg->c_lock);
1082         thread_block(THREAD_CONTINUE_NULL);
1083 }
1084
1085
1086 void
1087 c_seg_switch_state(c_segment_t c_seg, int new_state, boolean_t insert_head)
1088 {
1089         int     old_state = c_seg->c_state;
1090
1091 #if __i386__ || __x86_64__
1092         if (new_state != C_IS_FILLING) {
1093                 LCK_MTX_ASSERT(&c_seg->c_lock, LCK_MTX_ASSERT_OWNED);
1094         }
1095         LCK_MTX_ASSERT(c_list_lock, LCK_MTX_ASSERT_OWNED);
1096 #endif
1097         switch (old_state) {
1098         case C_IS_EMPTY:
1099                 assert(new_state == C_IS_FILLING || new_state == C_IS_FREE);
1100
1101                 c_empty_count--;
1102                 break;
1103
1104         case C_IS_FILLING:
1105                 assert(new_state == C_ON_AGE_Q || new_state == C_ON_SWAPOUT_Q);
1106
1107                 queue_remove(&c_filling_list_head, c_seg, c_segment_t, c_age_list);
1108                 c_filling_count--;
1109                 break;
1110
1111         case C_ON_AGE_Q:
1112                 assert(new_state == C_ON_SWAPOUT_Q || new_state == C_ON_MAJORCOMPACT_Q ||
1113                     new_state == C_IS_FREE);
1114
1115                 queue_remove(&c_age_list_head, c_seg, c_segment_t, c_age_list);
1116                 c_age_count--;
1117                 break;
1118
1119         case C_ON_SWAPPEDIN_Q:
1120                 assert(new_state == C_ON_AGE_Q || new_state == C_IS_FREE);
1121
1122                 queue_remove(&c_swappedin_list_head, c_seg, c_segment_t, c_age_list);
1123                 c_swappedin_count--;
1124                 break;
1125
1126         case C_ON_SWAPOUT_Q:
1127                 assert(new_state == C_ON_AGE_Q || new_state == C_IS_FREE || new_state == C_IS_EMPTY || new_state == C_ON_SWAPIO_Q);
1128
1129                 queue_remove(&c_swapout_list_head, c_seg, c_segment_t, c_age_list);
1130                 thread_wakeup((event_t)&compaction_swapper_running);
1131                 c_swapout_count--;
1132                 break;
1133
1134         case C_ON_SWAPIO_Q:
1135                 assert(new_state == C_ON_SWAPPEDOUT_Q || new_state == C_ON_SWAPPEDOUTSPARSE_Q || new_state == C_ON_AGE_Q);
1136
1137                 queue_remove(&c_swapio_list_head, c_seg, c_segment_t, c_age_list);
1138                 c_swapio_count--;
1139                 break;
1140
1141         case C_ON_SWAPPEDOUT_Q:
1142                 assert(new_state == C_ON_SWAPPEDIN_Q || new_state == C_ON_AGE_Q ||
1143                     new_state == C_ON_SWAPPEDOUTSPARSE_Q ||
1144                     new_state == C_ON_BAD_Q || new_state == C_IS_EMPTY || new_state == C_IS_FREE);
1145
1146                 queue_remove(&c_swappedout_list_head, c_seg, c_segment_t, c_age_list);
1147                 c_swappedout_count--;
1148                 break;
1149
1150         case C_ON_SWAPPEDOUTSPARSE_Q:
1151                 assert(new_state == C_ON_SWAPPEDIN_Q || new_state == C_ON_AGE_Q ||
1152                     new_state == C_ON_BAD_Q || new_state == C_IS_EMPTY || new_state == C_IS_FREE);
1153
1154                 queue_remove(&c_swappedout_sparse_list_head, c_seg, c_segment_t, c_age_list);
1155                 c_swappedout_sparse_count--;
1156                 break;
1157
1158         case C_ON_MAJORCOMPACT_Q:
1159                 assert(new_state == C_ON_AGE_Q || new_state == C_IS_FREE);
1160
1161                 queue_remove(&c_major_list_head, c_seg, c_segment_t, c_age_list);
1162                 c_major_count--;
1163                 break;
1164
1165         case C_ON_BAD_Q:
1166                 assert(new_state == C_IS_FREE);
1167
1168                 queue_remove(&c_bad_list_head, c_seg, c_segment_t, c_age_list);
1169                 c_bad_count--;
1170                 break;
1171
1172         default:
1173                 panic("c_seg %p has bad c_state = %d\n", c_seg, old_state);
1174         }
1175
1176         switch (new_state) {
1177         case C_IS_FREE:
1178                 assert(old_state != C_IS_FILLING);
1179
1180                 break;
1181
1182         case C_IS_EMPTY:
1183                 assert(old_state == C_ON_SWAPOUT_Q || old_state == C_ON_SWAPPEDOUT_Q || old_state == C_ON_SWAPPEDOUTSPARSE_Q);
1184
1185                 c_empty_count++;
1186                 break;
1187
1188         case C_IS_FILLING:
1189                 assert(old_state == C_IS_EMPTY);
1190
1191                 queue_enter(&c_filling_list_head, c_seg, c_segment_t, c_age_list);
1192                 c_filling_count++;
1193                 break;
1194
1195         case C_ON_AGE_Q:
1196                 assert(old_state == C_IS_FILLING || old_state == C_ON_SWAPPEDIN_Q ||
1197                     old_state == C_ON_SWAPOUT_Q || old_state == C_ON_SWAPIO_Q ||
1198                     old_state == C_ON_MAJORCOMPACT_Q || old_state == C_ON_SWAPPEDOUT_Q || old_state == C_ON_SWAPPEDOUTSPARSE_Q);
1199
1200                 if (old_state == C_IS_FILLING) {
1201                         queue_enter(&c_age_list_head, c_seg, c_segment_t, c_age_list);
1202                 } else {
1203                         if (!queue_empty(&c_age_list_head)) {
1204                                 c_segment_t     c_first;
1205
1206                                 c_first = (c_segment_t)queue_first(&c_age_list_head);
1207                                 c_seg->c_creation_ts = c_first->c_creation_ts;
1208                         }
1209                         queue_enter_first(&c_age_list_head, c_seg, c_segment_t, c_age_list);
1210                 }
1211                 c_age_count++;
1212                 break;
1213
1214         case C_ON_SWAPPEDIN_Q:
1215                 assert(old_state == C_ON_SWAPPEDOUT_Q || old_state == C_ON_SWAPPEDOUTSPARSE_Q);
1216
1217                 if (insert_head == TRUE) {
1218                         queue_enter_first(&c_swappedin_list_head, c_seg, c_segment_t, c_age_list);
1219                 } else {
1220                         queue_enter(&c_swappedin_list_head, c_seg, c_segment_t, c_age_list);
1221                 }
1222                 c_swappedin_count++;
1223                 break;
1224
1225         case C_ON_SWAPOUT_Q:
1226                 assert(old_state == C_ON_AGE_Q || old_state == C_IS_FILLING);
1227
1228                 if (insert_head == TRUE) {
1229                         queue_enter_first(&c_swapout_list_head, c_seg, c_segment_t, c_age_list);
1230                 } else {
1231                         queue_enter(&c_swapout_list_head, c_seg, c_segment_t, c_age_list);
1232                 }
1233                 c_swapout_count++;
1234                 break;
1235
1236         case C_ON_SWAPIO_Q:
1237                 assert(old_state == C_ON_SWAPOUT_Q);
1238
1239                 if (insert_head == TRUE) {
1240                         queue_enter_first(&c_swapio_list_head, c_seg, c_segment_t, c_age_list);
1241                 } else {
1242                         queue_enter(&c_swapio_list_head, c_seg, c_segment_t, c_age_list);
1243                 }
1244                 c_swapio_count++;
1245                 break;
1246
1247         case C_ON_SWAPPEDOUT_Q:
1248                 assert(old_state == C_ON_SWAPIO_Q);
1249
1250                 if (insert_head == TRUE) {
1251                         queue_enter_first(&c_swappedout_list_head, c_seg, c_segment_t, c_age_list);
1252                 } else {
1253                         queue_enter(&c_swappedout_list_head, c_seg, c_segment_t, c_age_list);
1254                 }
1255                 c_swappedout_count++;
1256                 break;
1257
1258         case C_ON_SWAPPEDOUTSPARSE_Q:
1259                 assert(old_state == C_ON_SWAPIO_Q || old_state == C_ON_SWAPPEDOUT_Q);
1260
1261                 if (insert_head == TRUE) {
1262                         queue_enter_first(&c_swappedout_sparse_list_head, c_seg, c_segment_t, c_age_list);
1263                 } else {
1264                         queue_enter(&c_swappedout_sparse_list_head, c_seg, c_segment_t, c_age_list);
1265                 }
1266
1267                 c_swappedout_sparse_count++;
1268                 break;
1269
1270         case C_ON_MAJORCOMPACT_Q:
1271                 assert(old_state == C_ON_AGE_Q);
1272
1273                 if (insert_head == TRUE) {
1274                         queue_enter_first(&c_major_list_head, c_seg, c_segment_t, c_age_list);
1275                 } else {
1276                         queue_enter(&c_major_list_head, c_seg, c_segment_t, c_age_list);
1277                 }
1278                 c_major_count++;
1279                 break;
1280
1281         case C_ON_BAD_Q:
1282                 assert(old_state == C_ON_SWAPPEDOUT_Q || old_state == C_ON_SWAPPEDOUTSPARSE_Q);
1283
1284                 if (insert_head == TRUE) {
1285                         queue_enter_first(&c_bad_list_head, c_seg, c_segment_t, c_age_list);
1286                 } else {
1287                         queue_enter(&c_bad_list_head, c_seg, c_segment_t, c_age_list);
1288                 }
1289                 c_bad_count++;
1290                 break;
1291
1292         default:
1293                 panic("c_seg %p requesting bad c_state = %d\n", c_seg, new_state);
1294         }
1295         c_seg->c_state = new_state;
1296 }
1297
1298
1299
1300 void
1301 c_seg_free(c_segment_t c_seg)
1302 {
1303         assert(c_seg->c_busy);
1304
1305         lck_mtx_unlock_always(&c_seg->c_lock);
1306         lck_mtx_lock_spin_always(c_list_lock);
1307         lck_mtx_lock_spin_always(&c_seg->c_lock);
1308
1309         c_seg_free_locked(c_seg);
1310 }
1311
1312
1313 void
1314 c_seg_free_locked(c_segment_t c_seg)
1315 {
1316         int             segno;
1317         int             pages_populated = 0;
1318         int32_t         *c_buffer = NULL;
1319         uint64_t        c_swap_handle = 0;
1320
1321         assert(c_seg->c_busy);
1322         assert(c_seg->c_slots_used == 0);
1323         assert(!c_seg->c_on_minorcompact_q);
1324         assert(!c_seg->c_busy_swapping);
1325
1326         if (c_seg->c_overage_swap == TRUE) {
1327                 c_overage_swapped_count--;
1328                 c_seg->c_overage_swap = FALSE;
1329         }
1330         if (!(C_SEG_IS_ONDISK(c_seg))) {
1331                 c_buffer = c_seg->c_store.c_buffer;
1332         } else {
1333                 c_swap_handle = c_seg->c_store.c_swap_handle;
1334         }
1335
1336         c_seg_switch_state(c_seg, C_IS_FREE, FALSE);
1337
1338         lck_mtx_unlock_always(c_list_lock);
1339
1340         if (c_buffer) {
1341                 pages_populated = (round_page_32(C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset))) / PAGE_SIZE;
1342                 c_seg->c_store.c_buffer = NULL;
1343         } else {
1344                 c_seg->c_store.c_swap_handle = (uint64_t)-1;
1345         }
1346
1347         lck_mtx_unlock_always(&c_seg->c_lock);
1348
1349         if (c_buffer) {
1350                 if (pages_populated) {
1351                         kernel_memory_depopulate(compressor_map, (vm_offset_t) c_buffer, pages_populated * PAGE_SIZE, KMA_COMPRESSOR);
1352                 }
1353         } else if (c_swap_handle) {
1354                 /*
1355                  * Free swap space on disk.
1356                  */
1357                 vm_swap_free(c_swap_handle);
1358         }
1359         lck_mtx_lock_spin_always(&c_seg->c_lock);
1360         /*
1361          * c_seg must remain busy until
1362          * after the call to vm_swap_free
1363          */
1364         C_SEG_WAKEUP_DONE(c_seg);
1365         lck_mtx_unlock_always(&c_seg->c_lock);
1366
1367         segno = c_seg->c_mysegno;
1368
1369         lck_mtx_lock_spin_always(c_list_lock);
1370         /*
1371          * because the c_buffer is now associated with the segno,
1372          * we can't put the segno back on the free list until
1373          * after we have depopulated the c_buffer range, or
1374          * we run the risk of depopulating a range that is
1375          * now being used in one of the compressor heads
1376          */
1377         c_segments[segno].c_segno = c_free_segno_head;
1378         c_free_segno_head = segno;
1379         c_segment_count--;
1380
1381         lck_mtx_unlock_always(c_list_lock);
1382
1383         lck_mtx_destroy(&c_seg->c_lock, &vm_compressor_lck_grp);
1384
1385         if (c_seg->c_slot_var_array_len) {
1386                 kfree(c_seg->c_slot_var_array, sizeof(struct c_slot) * c_seg->c_slot_var_array_len);
1387         }
1388
1389         zfree(compressor_segment_zone, c_seg);
1390 }
1391
1392 #if DEVELOPMENT || DEBUG
1393 int c_seg_trim_page_count = 0;
1394 #endif
1395
1396 void
1397 c_seg_trim_tail(c_segment_t c_seg)
1398 {
1399         c_slot_t        cs;
1400         uint32_t        c_size;
1401         uint32_t        c_offset;
1402         uint32_t        c_rounded_size;
1403         uint16_t        current_nextslot;
1404         uint32_t        current_populated_offset;
1405
1406         if (c_seg->c_bytes_used == 0) {
1407                 return;
1408         }
1409         current_nextslot = c_seg->c_nextslot;
1410         current_populated_offset = c_seg->c_populated_offset;
1411
1412         while (c_seg->c_nextslot) {
1413                 cs = C_SEG_SLOT_FROM_INDEX(c_seg, (c_seg->c_nextslot - 1));
1414
1415                 c_size = UNPACK_C_SIZE(cs);
1416
1417                 if (c_size) {
1418                         if (current_nextslot != c_seg->c_nextslot) {
1419                                 c_rounded_size = (c_size + C_SEG_OFFSET_ALIGNMENT_MASK) & ~C_SEG_OFFSET_ALIGNMENT_MASK;
1420                                 c_offset = cs->c_offset + C_SEG_BYTES_TO_OFFSET(c_rounded_size);
1421
1422                                 c_seg->c_nextoffset = c_offset;
1423                                 c_seg->c_populated_offset = (c_offset + (C_SEG_BYTES_TO_OFFSET(PAGE_SIZE) - 1)) &
1424                                     ~(C_SEG_BYTES_TO_OFFSET(PAGE_SIZE) - 1);
1425
1426                                 if (c_seg->c_firstemptyslot > c_seg->c_nextslot) {
1427                                         c_seg->c_firstemptyslot = c_seg->c_nextslot;
1428                                 }
1429 #if DEVELOPMENT || DEBUG
1430                                 c_seg_trim_page_count += ((round_page_32(C_SEG_OFFSET_TO_BYTES(current_populated_offset)) -
1431                                     round_page_32(C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset))) /
1432                                     PAGE_SIZE);
1433 #endif
1434                         }
1435                         break;
1436                 }
1437                 c_seg->c_nextslot--;
1438         }
1439         assert(c_seg->c_nextslot);
1440 }
1441
1442
1443 int
1444 c_seg_minor_compaction_and_unlock(c_segment_t c_seg, boolean_t clear_busy)
1445 {
1446         c_slot_mapping_t slot_ptr;
1447         uint32_t        c_offset = 0;
1448         uint32_t        old_populated_offset;
1449         uint32_t        c_rounded_size;
1450         uint32_t        c_size;
1451         int             c_indx = 0;
1452         int             i;
1453         c_slot_t        c_dst;
1454         c_slot_t        c_src;
1455
1456         assert(c_seg->c_busy);
1457
1458 #if VALIDATE_C_SEGMENTS
1459         c_seg_validate(c_seg, FALSE);
1460 #endif
1461         if (c_seg->c_bytes_used == 0) {
1462                 c_seg_free(c_seg);
1463                 return 1;
1464         }
1465         lck_mtx_unlock_always(&c_seg->c_lock);
1466
1467         if (c_seg->c_firstemptyslot >= c_seg->c_nextslot || C_SEG_UNUSED_BYTES(c_seg) < PAGE_SIZE) {
1468                 goto done;
1469         }
1470
1471 /* TODO: assert first emptyslot's c_size is actually 0 */
1472
1473 #if DEVELOPMENT || DEBUG
1474         C_SEG_MAKE_WRITEABLE(c_seg);
1475 #endif
1476
1477 #if VALIDATE_C_SEGMENTS
1478         c_seg->c_was_minor_compacted++;
1479 #endif
1480         c_indx = c_seg->c_firstemptyslot;
1481         c_dst = C_SEG_SLOT_FROM_INDEX(c_seg, c_indx);
1482
1483         old_populated_offset = c_seg->c_populated_offset;
1484         c_offset = c_dst->c_offset;
1485
1486         for (i = c_indx + 1; i < c_seg->c_nextslot && c_offset < c_seg->c_nextoffset; i++) {
1487                 c_src = C_SEG_SLOT_FROM_INDEX(c_seg, i);
1488
1489                 c_size = UNPACK_C_SIZE(c_src);
1490
1491                 if (c_size == 0) {
1492                         continue;
1493                 }
1494
1495                 c_rounded_size = (c_size + C_SEG_OFFSET_ALIGNMENT_MASK) & ~C_SEG_OFFSET_ALIGNMENT_MASK;
1496 /* N.B.: This memcpy may be an overlapping copy */
1497                 memcpy(&c_seg->c_store.c_buffer[c_offset], &c_seg->c_store.c_buffer[c_src->c_offset], c_rounded_size);
1498
1499                 cslot_copy(c_dst, c_src);
1500                 c_dst->c_offset = c_offset;
1501
1502                 slot_ptr = (c_slot_mapping_t)C_SLOT_UNPACK_PTR(c_dst);
1503                 slot_ptr->s_cindx = c_indx;
1504
1505                 c_offset += C_SEG_BYTES_TO_OFFSET(c_rounded_size);
1506                 PACK_C_SIZE(c_src, 0);
1507                 c_indx++;
1508
1509                 c_dst = C_SEG_SLOT_FROM_INDEX(c_seg, c_indx);
1510         }
1511         c_seg->c_firstemptyslot = c_indx;
1512         c_seg->c_nextslot = c_indx;
1513         c_seg->c_nextoffset = c_offset;
1514         c_seg->c_populated_offset = (c_offset + (C_SEG_BYTES_TO_OFFSET(PAGE_SIZE) - 1)) & ~(C_SEG_BYTES_TO_OFFSET(PAGE_SIZE) - 1);
1515         c_seg->c_bytes_unused = 0;
1516
1517 #if VALIDATE_C_SEGMENTS
1518         c_seg_validate(c_seg, TRUE);
1519 #endif
1520         if (old_populated_offset > c_seg->c_populated_offset) {
1521                 uint32_t        gc_size;
1522                 int32_t         *gc_ptr;
1523
1524                 gc_size = C_SEG_OFFSET_TO_BYTES(old_populated_offset - c_seg->c_populated_offset);
1525                 gc_ptr = &c_seg->c_store.c_buffer[c_seg->c_populated_offset];
1526
1527                 kernel_memory_depopulate(compressor_map, (vm_offset_t)gc_ptr, gc_size, KMA_COMPRESSOR);
1528         }
1529
1530 #if DEVELOPMENT || DEBUG
1531         C_SEG_WRITE_PROTECT(c_seg);
1532 #endif
1533
1534 done:
1535         if (clear_busy == TRUE) {
1536                 lck_mtx_lock_spin_always(&c_seg->c_lock);
1537                 C_SEG_WAKEUP_DONE(c_seg);
1538                 lck_mtx_unlock_always(&c_seg->c_lock);
1539         }
1540         return 0;
1541 }
1542
1543
1544 static void
1545 c_seg_alloc_nextslot(c_segment_t c_seg)
1546 {
1547         struct c_slot   *old_slot_array = NULL;
1548         struct c_slot   *new_slot_array = NULL;
1549         int             newlen;
1550         int             oldlen;
1551
1552         if (c_seg->c_nextslot < c_seg_fixed_array_len) {
1553                 return;
1554         }
1555
1556         if ((c_seg->c_nextslot - c_seg_fixed_array_len) >= c_seg->c_slot_var_array_len) {
1557                 oldlen = c_seg->c_slot_var_array_len;
1558                 old_slot_array = c_seg->c_slot_var_array;
1559
1560                 if (oldlen == 0) {
1561                         newlen = C_SEG_SLOT_VAR_ARRAY_MIN_LEN;
1562                 } else {
1563                         newlen = oldlen * 2;
1564                 }
1565
1566                 new_slot_array = (struct c_slot *)kalloc(sizeof(struct c_slot) * newlen);
1567
1568                 lck_mtx_lock_spin_always(&c_seg->c_lock);
1569
1570                 if (old_slot_array) {
1571                         memcpy((char *)new_slot_array, (char *)old_slot_array, sizeof(struct c_slot) * oldlen);
1572                 }
1573
1574                 c_seg->c_slot_var_array_len = newlen;
1575                 c_seg->c_slot_var_array = new_slot_array;
1576
1577                 lck_mtx_unlock_always(&c_seg->c_lock);
1578
1579                 if (old_slot_array) {
1580                         kfree(old_slot_array, sizeof(struct c_slot) * oldlen);
1581                 }
1582         }
1583 }
1584
1585
1586
1587 struct {
1588         uint64_t asked_permission;
1589         uint64_t compactions;
1590         uint64_t moved_slots;
1591         uint64_t moved_bytes;
1592         uint64_t wasted_space_in_swapouts;
1593         uint64_t count_of_swapouts;
1594         uint64_t count_of_freed_segs;
1595 } c_seg_major_compact_stats;
1596
1597
1598 #define C_MAJOR_COMPACTION_SIZE_APPROPRIATE     ((C_SEG_BUFSIZE * 90) / 100)
1599
1600
1601 boolean_t
1602 c_seg_major_compact_ok(
1603         c_segment_t c_seg_dst,
1604         c_segment_t c_seg_src)
1605 {
1606         c_seg_major_compact_stats.asked_permission++;
1607
1608         if (c_seg_src->c_bytes_used >= C_MAJOR_COMPACTION_SIZE_APPROPRIATE &&
1609             c_seg_dst->c_bytes_used >= C_MAJOR_COMPACTION_SIZE_APPROPRIATE) {
1610                 return FALSE;
1611         }
1612
1613         if (c_seg_dst->c_nextoffset >= C_SEG_OFF_LIMIT || c_seg_dst->c_nextslot >= C_SLOT_MAX_INDEX) {
1614                 /*
1615                  * destination segment is full... can't compact
1616                  */
1617                 return FALSE;
1618         }
1619
1620         return TRUE;
1621 }
1622
1623
1624 boolean_t
1625 c_seg_major_compact(
1626         c_segment_t c_seg_dst,
1627         c_segment_t c_seg_src)
1628 {
1629         c_slot_mapping_t slot_ptr;
1630         uint32_t        c_rounded_size;
1631         uint32_t        c_size;
1632         uint16_t        dst_slot;
1633         int             i;
1634         c_slot_t        c_dst;
1635         c_slot_t        c_src;
1636         boolean_t       keep_compacting = TRUE;
1637
1638         /*
1639          * segments are not locked but they are both marked c_busy
1640          * which keeps c_decompress from working on them...
1641          * we can safely allocate new pages, move compressed data
1642          * from c_seg_src to c_seg_dst and update both c_segment's
1643          * state w/o holding the master lock
1644          */
1645 #if DEVELOPMENT || DEBUG
1646         C_SEG_MAKE_WRITEABLE(c_seg_dst);
1647 #endif
1648
1649 #if VALIDATE_C_SEGMENTS
1650         c_seg_dst->c_was_major_compacted++;
1651         c_seg_src->c_was_major_donor++;
1652 #endif
1653         c_seg_major_compact_stats.compactions++;
1654
1655         dst_slot = c_seg_dst->c_nextslot;
1656
1657         for (i = 0; i < c_seg_src->c_nextslot; i++) {
1658                 c_src = C_SEG_SLOT_FROM_INDEX(c_seg_src, i);
1659
1660                 c_size = UNPACK_C_SIZE(c_src);
1661
1662                 if (c_size == 0) {
1663                         /* BATCH: move what we have so far; */
1664                         continue;
1665                 }
1666
1667                 if (C_SEG_OFFSET_TO_BYTES(c_seg_dst->c_populated_offset - c_seg_dst->c_nextoffset) < (unsigned) c_size) {
1668                         int     size_to_populate;
1669
1670                         /* doesn't fit */
1671                         size_to_populate = C_SEG_BUFSIZE - C_SEG_OFFSET_TO_BYTES(c_seg_dst->c_populated_offset);
1672
1673                         if (size_to_populate == 0) {
1674                                 /* can't fit */
1675                                 keep_compacting = FALSE;
1676                                 break;
1677                         }
1678                         if (size_to_populate > C_SEG_MAX_POPULATE_SIZE) {
1679                                 size_to_populate = C_SEG_MAX_POPULATE_SIZE;
1680                         }
1681
1682                         kernel_memory_populate(compressor_map,
1683                             (vm_offset_t) &c_seg_dst->c_store.c_buffer[c_seg_dst->c_populated_offset],
1684                             size_to_populate,
1685                             KMA_COMPRESSOR,
1686                             VM_KERN_MEMORY_COMPRESSOR);
1687
1688                         c_seg_dst->c_populated_offset += C_SEG_BYTES_TO_OFFSET(size_to_populate);
1689                         assert(C_SEG_OFFSET_TO_BYTES(c_seg_dst->c_populated_offset) <= C_SEG_BUFSIZE);
1690                 }
1691                 c_seg_alloc_nextslot(c_seg_dst);
1692
1693                 c_dst = C_SEG_SLOT_FROM_INDEX(c_seg_dst, c_seg_dst->c_nextslot);
1694
1695                 memcpy(&c_seg_dst->c_store.c_buffer[c_seg_dst->c_nextoffset], &c_seg_src->c_store.c_buffer[c_src->c_offset], c_size);
1696
1697                 c_rounded_size = (c_size + C_SEG_OFFSET_ALIGNMENT_MASK) & ~C_SEG_OFFSET_ALIGNMENT_MASK;
1698
1699                 c_seg_major_compact_stats.moved_slots++;
1700                 c_seg_major_compact_stats.moved_bytes += c_size;
1701
1702                 cslot_copy(c_dst, c_src);
1703                 c_dst->c_offset = c_seg_dst->c_nextoffset;
1704
1705                 if (c_seg_dst->c_firstemptyslot == c_seg_dst->c_nextslot) {
1706                         c_seg_dst->c_firstemptyslot++;
1707                 }
1708                 c_seg_dst->c_slots_used++;
1709                 c_seg_dst->c_nextslot++;
1710                 c_seg_dst->c_bytes_used += c_rounded_size;
1711                 c_seg_dst->c_nextoffset += C_SEG_BYTES_TO_OFFSET(c_rounded_size);
1712
1713                 PACK_C_SIZE(c_src, 0);
1714
1715                 c_seg_src->c_bytes_used -= c_rounded_size;
1716                 c_seg_src->c_bytes_unused += c_rounded_size;
1717                 c_seg_src->c_firstemptyslot = 0;
1718
1719                 assert(c_seg_src->c_slots_used);
1720                 c_seg_src->c_slots_used--;
1721
1722                 if (c_seg_dst->c_nextoffset >= C_SEG_OFF_LIMIT || c_seg_dst->c_nextslot >= C_SLOT_MAX_INDEX) {
1723                         /* dest segment is now full */
1724                         keep_compacting = FALSE;
1725                         break;
1726                 }
1727         }
1728 #if DEVELOPMENT || DEBUG
1729         C_SEG_WRITE_PROTECT(c_seg_dst);
1730 #endif
1731         if (dst_slot < c_seg_dst->c_nextslot) {
1732                 PAGE_REPLACEMENT_ALLOWED(TRUE);
1733                 /*
1734                  * we've now locked out c_decompress from
1735                  * converting the slot passed into it into
1736                  * a c_segment_t which allows us to use
1737                  * the backptr to change which c_segment and
1738                  * index the slot points to
1739                  */
1740                 while (dst_slot < c_seg_dst->c_nextslot) {
1741                         c_dst = C_SEG_SLOT_FROM_INDEX(c_seg_dst, dst_slot);
1742
1743                         slot_ptr = (c_slot_mapping_t)C_SLOT_UNPACK_PTR(c_dst);
1744                         /* <csegno=0,indx=0> would mean "empty slot", so use csegno+1 */
1745                         slot_ptr->s_cseg = c_seg_dst->c_mysegno + 1;
1746                         slot_ptr->s_cindx = dst_slot++;
1747                 }
1748                 PAGE_REPLACEMENT_ALLOWED(FALSE);
1749         }
1750         return keep_compacting;
1751 }
1752
1753
1754 uint64_t
1755 vm_compressor_compute_elapsed_msecs(clock_sec_t end_sec, clock_nsec_t end_nsec, clock_sec_t start_sec, clock_nsec_t start_nsec)
1756 {
1757         uint64_t end_msecs;
1758         uint64_t start_msecs;
1759
1760         end_msecs = (end_sec * 1000) + end_nsec / 1000000;
1761         start_msecs = (start_sec * 1000) + start_nsec / 1000000;
1762
1763         return end_msecs - start_msecs;
1764 }
1765
1766
1767
1768 uint32_t compressor_eval_period_in_msecs = 250;
1769 uint32_t compressor_sample_min_in_msecs = 500;
1770 uint32_t compressor_sample_max_in_msecs = 10000;
1771 uint32_t compressor_thrashing_threshold_per_10msecs = 50;
1772 uint32_t compressor_thrashing_min_per_10msecs = 20;
1773
1774 /* When true, reset sample data next chance we get. */
1775 static boolean_t        compressor_need_sample_reset = FALSE;
1776
1777
1778 void
1779 compute_swapout_target_age(void)
1780 {
1781         clock_sec_t     cur_ts_sec;
1782         clock_nsec_t    cur_ts_nsec;
1783         uint32_t        min_operations_needed_in_this_sample;
1784         uint64_t        elapsed_msecs_in_eval;
1785         uint64_t        elapsed_msecs_in_sample;
1786         boolean_t       need_eval_reset = FALSE;
1787
1788         clock_get_system_nanotime(&cur_ts_sec, &cur_ts_nsec);
1789
1790         elapsed_msecs_in_sample = vm_compressor_compute_elapsed_msecs(cur_ts_sec, cur_ts_nsec, start_of_sample_period_sec, start_of_sample_period_nsec);
1791
1792         if (compressor_need_sample_reset ||
1793             elapsed_msecs_in_sample >= compressor_sample_max_in_msecs) {
1794                 compressor_need_sample_reset = TRUE;
1795                 need_eval_reset = TRUE;
1796                 goto done;
1797         }
1798         elapsed_msecs_in_eval = vm_compressor_compute_elapsed_msecs(cur_ts_sec, cur_ts_nsec, start_of_eval_period_sec, start_of_eval_period_nsec);
1799
1800         if (elapsed_msecs_in_eval < compressor_eval_period_in_msecs) {
1801                 goto done;
1802         }
1803         need_eval_reset = TRUE;
1804
1805         KERNEL_DEBUG(0xe0400020 | DBG_FUNC_START, elapsed_msecs_in_eval, sample_period_compression_count, sample_period_decompression_count, 0, 0);
1806
1807         min_operations_needed_in_this_sample = (compressor_thrashing_min_per_10msecs * (uint32_t)elapsed_msecs_in_eval) / 10;
1808
1809         if ((sample_period_compression_count - last_eval_compression_count) < min_operations_needed_in_this_sample ||
1810             (sample_period_decompression_count - last_eval_decompression_count) < min_operations_needed_in_this_sample) {
1811                 KERNEL_DEBUG(0xe0400020 | DBG_FUNC_END, sample_period_compression_count - last_eval_compression_count,
1812                     sample_period_decompression_count - last_eval_decompression_count, 0, 1, 0);
1813
1814                 swapout_target_age = 0;
1815
1816                 compressor_need_sample_reset = TRUE;
1817                 need_eval_reset = TRUE;
1818                 goto done;
1819         }
1820         last_eval_compression_count = sample_period_compression_count;
1821         last_eval_decompression_count = sample_period_decompression_count;
1822
1823         if (elapsed_msecs_in_sample < compressor_sample_min_in_msecs) {
1824                 KERNEL_DEBUG(0xe0400020 | DBG_FUNC_END, swapout_target_age, 0, 0, 5, 0);
1825                 goto done;
1826         }
1827         if (sample_period_decompression_count > ((compressor_thrashing_threshold_per_10msecs * elapsed_msecs_in_sample) / 10)) {
1828                 uint64_t        running_total;
1829                 uint64_t        working_target;
1830                 uint64_t        aging_target;
1831                 uint32_t        oldest_age_of_csegs_sampled = 0;
1832                 uint64_t        working_set_approximation = 0;
1833
1834                 swapout_target_age = 0;
1835
1836                 working_target = (sample_period_decompression_count / 100) * 95;                /* 95 percent */
1837                 aging_target = (sample_period_decompression_count / 100) * 1;                   /* 1 percent */
1838                 running_total = 0;
1839
1840                 for (oldest_age_of_csegs_sampled = 0; oldest_age_of_csegs_sampled < DECOMPRESSION_SAMPLE_MAX_AGE; oldest_age_of_csegs_sampled++) {
1841                         running_total += age_of_decompressions_during_sample_period[oldest_age_of_csegs_sampled];
1842
1843                         working_set_approximation += oldest_age_of_csegs_sampled * age_of_decompressions_during_sample_period[oldest_age_of_csegs_sampled];
1844
1845                         if (running_total >= working_target) {
1846                                 break;
1847                         }
1848                 }
1849                 if (oldest_age_of_csegs_sampled < DECOMPRESSION_SAMPLE_MAX_AGE) {
1850                         working_set_approximation = (working_set_approximation * 1000) / elapsed_msecs_in_sample;
1851
1852                         if (working_set_approximation < VM_PAGE_COMPRESSOR_COUNT) {
1853                                 running_total = overage_decompressions_during_sample_period;
1854
1855                                 for (oldest_age_of_csegs_sampled = DECOMPRESSION_SAMPLE_MAX_AGE - 1; oldest_age_of_csegs_sampled; oldest_age_of_csegs_sampled--) {
1856                                         running_total += age_of_decompressions_during_sample_period[oldest_age_of_csegs_sampled];
1857
1858                                         if (running_total >= aging_target) {
1859                                                 break;
1860                                         }
1861                                 }
1862                                 swapout_target_age = (uint32_t)cur_ts_sec - oldest_age_of_csegs_sampled;
1863
1864                                 KERNEL_DEBUG(0xe0400020 | DBG_FUNC_END, swapout_target_age, working_set_approximation, VM_PAGE_COMPRESSOR_COUNT, 2, 0);
1865                         } else {
1866                                 KERNEL_DEBUG(0xe0400020 | DBG_FUNC_END, working_set_approximation, VM_PAGE_COMPRESSOR_COUNT, 0, 3, 0);
1867                         }
1868                 } else {
1869                         KERNEL_DEBUG(0xe0400020 | DBG_FUNC_END, working_target, running_total, 0, 4, 0);
1870                 }
1871
1872                 compressor_need_sample_reset = TRUE;
1873                 need_eval_reset = TRUE;
1874         } else {
1875                 KERNEL_DEBUG(0xe0400020 | DBG_FUNC_END, sample_period_decompression_count, (compressor_thrashing_threshold_per_10msecs * elapsed_msecs_in_sample) / 10, 0, 6, 0);
1876         }
1877 done:
1878         if (compressor_need_sample_reset == TRUE) {
1879                 bzero(age_of_decompressions_during_sample_period, sizeof(age_of_decompressions_during_sample_period));
1880                 overage_decompressions_during_sample_period = 0;
1881
1882                 start_of_sample_period_sec = cur_ts_sec;
1883                 start_of_sample_period_nsec = cur_ts_nsec;
1884                 sample_period_decompression_count = 0;
1885                 sample_period_compression_count = 0;
1886                 last_eval_decompression_count = 0;
1887                 last_eval_compression_count = 0;
1888                 compressor_need_sample_reset = FALSE;
1889         }
1890         if (need_eval_reset == TRUE) {
1891                 start_of_eval_period_sec = cur_ts_sec;
1892                 start_of_eval_period_nsec = cur_ts_nsec;
1893         }
1894 }
1895
1896
1897 int             compaction_swapper_init_now = 0;
1898 int             compaction_swapper_running = 0;
1899 int             compaction_swapper_awakened = 0;
1900 int             compaction_swapper_abort = 0;
1901
1902
1903 #if CONFIG_JETSAM
1904 boolean_t       memorystatus_kill_on_VM_compressor_thrashing(boolean_t);
1905 boolean_t       memorystatus_kill_on_VM_compressor_space_shortage(boolean_t);
1906 boolean_t       memorystatus_kill_on_FC_thrashing(boolean_t);
1907 int             compressor_thrashing_induced_jetsam = 0;
1908 int             filecache_thrashing_induced_jetsam = 0;
1909 static boolean_t        vm_compressor_thrashing_detected = FALSE;
1910 #endif /* CONFIG_JETSAM */
1911
1912 static boolean_t
1913 compressor_needs_to_swap(void)
1914 {
1915         boolean_t       should_swap = FALSE;
1916
1917         if (vm_swapout_ripe_segments == TRUE && c_overage_swapped_count < c_overage_swapped_limit) {
1918                 c_segment_t     c_seg;
1919                 clock_sec_t     now;
1920                 clock_sec_t     age;
1921                 clock_nsec_t    nsec;
1922
1923                 clock_get_system_nanotime(&now, &nsec);
1924                 age = 0;
1925
1926                 lck_mtx_lock_spin_always(c_list_lock);
1927
1928                 if (!queue_empty(&c_age_list_head)) {
1929                         c_seg = (c_segment_t) queue_first(&c_age_list_head);
1930
1931                         age = now - c_seg->c_creation_ts;
1932                 }
1933                 lck_mtx_unlock_always(c_list_lock);
1934
1935                 if (age >= vm_ripe_target_age) {
1936                         return TRUE;
1937                 }
1938         }
1939         if (VM_CONFIG_SWAP_IS_ACTIVE) {
1940                 if (COMPRESSOR_NEEDS_TO_SWAP()) {
1941                         return TRUE;
1942                 }
1943                 if (VM_PAGE_Q_THROTTLED(&vm_pageout_queue_external) && vm_page_anonymous_count < (vm_page_inactive_count / 20)) {
1944                         return TRUE;
1945                 }
1946                 if (vm_page_free_count < (vm_page_free_reserved - (COMPRESSOR_FREE_RESERVED_LIMIT * 2))) {
1947                         return TRUE;
1948                 }
1949         }
1950         compute_swapout_target_age();
1951
1952         if (swapout_target_age) {
1953                 c_segment_t     c_seg;
1954
1955                 lck_mtx_lock_spin_always(c_list_lock);
1956
1957                 if (!queue_empty(&c_age_list_head)) {
1958                         c_seg = (c_segment_t) queue_first(&c_age_list_head);
1959
1960                         if (c_seg->c_creation_ts > swapout_target_age) {
1961                                 swapout_target_age = 0;
1962                         }
1963                 }
1964                 lck_mtx_unlock_always(c_list_lock);
1965         }
1966 #if CONFIG_PHANTOM_CACHE
1967         if (vm_phantom_cache_check_pressure()) {
1968                 should_swap = TRUE;
1969         }
1970 #endif
1971         if (swapout_target_age) {
1972                 should_swap = TRUE;
1973         }
1974
1975 #if CONFIG_JETSAM
1976         if (should_swap || vm_compressor_low_on_space() == TRUE) {
1977                 if (vm_compressor_thrashing_detected == FALSE) {
1978                         vm_compressor_thrashing_detected = TRUE;
1979
1980                         if (swapout_target_age || vm_compressor_low_on_space() == TRUE) {
1981                                 if (swapout_target_age) {
1982                                         /* The compressor is thrashing. */
1983                                         memorystatus_kill_on_VM_compressor_thrashing(TRUE /* async */);
1984                                 } else {
1985                                         /* The compressor is running low on space. */
1986                                         memorystatus_kill_on_VM_compressor_space_shortage(TRUE /* async */);
1987                                 }
1988                                 compressor_thrashing_induced_jetsam++;
1989                         } else {
1990                                 memorystatus_kill_on_FC_thrashing(TRUE /* async */);
1991                                 filecache_thrashing_induced_jetsam++;
1992                         }
1993                 }
1994                 /*
1995                  * let the jetsam take precedence over
1996                  * any major compactions we might have
1997                  * been able to do... otherwise we run
1998                  * the risk of doing major compactions
1999                  * on segments we're about to free up
2000                  * due to the jetsam activity.
2001                  */
2002                 should_swap = FALSE;
2003         }
2004
2005 #endif /* CONFIG_JETSAM */
2006
2007         if (should_swap == FALSE) {
2008                 /*
2009                  * vm_compressor_needs_to_major_compact returns true only if we're
2010                  * about to run out of available compressor segments... in this
2011                  * case, we absolutely need to run a major compaction even if
2012                  * we've just kicked off a jetsam or we don't otherwise need to
2013                  * swap... terminating objects releases
2014                  * pages back to the uncompressed cache, but does not guarantee
2015                  * that we will free up even a single compression segment
2016                  */
2017                 should_swap = vm_compressor_needs_to_major_compact();
2018         }
2019
2020         /*
2021          * returning TRUE when swap_supported == FALSE
2022          * will cause the major compaction engine to
2023          * run, but will not trigger any swapping...
2024          * segments that have been major compacted
2025          * will be moved to the majorcompact queue
2026          */
2027         return should_swap;
2028 }
2029
2030 #if CONFIG_JETSAM
2031 /*
2032  * This function is called from the jetsam thread after killing something to
2033  * mitigate thrashing.
2034  *
2035  * We need to restart our thrashing detection heuristics since memory pressure
2036  * has potentially changed significantly, and we don't want to detect on old
2037  * data from before the jetsam.
2038  */
2039 void
2040 vm_thrashing_jetsam_done(void)
2041 {
2042         vm_compressor_thrashing_detected = FALSE;
2043
2044         /* Were we compressor-thrashing or filecache-thrashing? */
2045         if (swapout_target_age) {
2046                 swapout_target_age = 0;
2047                 compressor_need_sample_reset = TRUE;
2048         }
2049 #if CONFIG_PHANTOM_CACHE
2050         else {
2051                 vm_phantom_cache_restart_sample();
2052         }
2053 #endif
2054 }
2055 #endif /* CONFIG_JETSAM */
2056
2057 uint32_t vm_wake_compactor_swapper_calls = 0;
2058 uint32_t vm_run_compactor_already_running = 0;
2059 uint32_t vm_run_compactor_empty_minor_q = 0;
2060 uint32_t vm_run_compactor_did_compact = 0;
2061 uint32_t vm_run_compactor_waited = 0;
2062
2063 void
2064 vm_run_compactor(void)
2065 {
2066         if (c_segment_count == 0) {
2067                 return;
2068         }
2069
2070         lck_mtx_lock_spin_always(c_list_lock);
2071
2072         if (c_minor_count == 0) {
2073                 vm_run_compactor_empty_minor_q++;
2074
2075                 lck_mtx_unlock_always(c_list_lock);
2076                 return;
2077         }
2078         if (compaction_swapper_running) {
2079                 if (vm_pageout_state.vm_restricted_to_single_processor == FALSE) {
2080                         vm_run_compactor_already_running++;
2081
2082                         lck_mtx_unlock_always(c_list_lock);
2083                         return;
2084                 }
2085                 vm_run_compactor_waited++;
2086
2087                 assert_wait((event_t)&compaction_swapper_running, THREAD_UNINT);
2088
2089                 lck_mtx_unlock_always(c_list_lock);
2090
2091                 thread_block(THREAD_CONTINUE_NULL);
2092
2093                 return;
2094         }
2095         vm_run_compactor_did_compact++;
2096
2097         fastwake_warmup = FALSE;
2098         compaction_swapper_running = 1;
2099
2100         vm_compressor_do_delayed_compactions(FALSE);
2101
2102         compaction_swapper_running = 0;
2103
2104         lck_mtx_unlock_always(c_list_lock);
2105
2106         thread_wakeup((event_t)&compaction_swapper_running);
2107 }
2108
2109
2110 void
2111 vm_wake_compactor_swapper(void)
2112 {
2113         if (compaction_swapper_running || compaction_swapper_awakened || c_segment_count == 0) {
2114                 return;
2115         }
2116
2117         if (c_minor_count || vm_compressor_needs_to_major_compact()) {
2118                 lck_mtx_lock_spin_always(c_list_lock);
2119
2120                 fastwake_warmup = FALSE;
2121
2122                 if (compaction_swapper_running == 0 && compaction_swapper_awakened == 0) {
2123                         vm_wake_compactor_swapper_calls++;
2124
2125                         compaction_swapper_awakened = 1;
2126                         thread_wakeup((event_t)&c_compressor_swap_trigger);
2127                 }
2128                 lck_mtx_unlock_always(c_list_lock);
2129         }
2130 }
2131
2132
2133 void
2134 vm_consider_swapping()
2135 {
2136         c_segment_t     c_seg, c_seg_next;
2137         clock_sec_t     now;
2138         clock_nsec_t    nsec;
2139
2140         assert(VM_CONFIG_SWAP_IS_PRESENT);
2141
2142         lck_mtx_lock_spin_always(c_list_lock);
2143
2144         compaction_swapper_abort = 1;
2145
2146         while (compaction_swapper_running) {
2147                 assert_wait((event_t)&compaction_swapper_running, THREAD_UNINT);
2148
2149                 lck_mtx_unlock_always(c_list_lock);
2150
2151                 thread_block(THREAD_CONTINUE_NULL);
2152
2153                 lck_mtx_lock_spin_always(c_list_lock);
2154         }
2155         compaction_swapper_abort = 0;
2156         compaction_swapper_running = 1;
2157
2158         vm_swapout_ripe_segments = TRUE;
2159
2160         if (!queue_empty(&c_major_list_head)) {
2161                 clock_get_system_nanotime(&now, &nsec);
2162
2163                 c_seg = (c_segment_t)queue_first(&c_major_list_head);
2164
2165                 while (!queue_end(&c_major_list_head, (queue_entry_t)c_seg)) {
2166                         if (c_overage_swapped_count >= c_overage_swapped_limit) {
2167                                 break;
2168                         }
2169
2170                         c_seg_next = (c_segment_t) queue_next(&c_seg->c_age_list);
2171
2172                         if ((now - c_seg->c_creation_ts) >= vm_ripe_target_age) {
2173                                 lck_mtx_lock_spin_always(&c_seg->c_lock);
2174
2175                                 c_seg_switch_state(c_seg, C_ON_AGE_Q, FALSE);
2176
2177                                 lck_mtx_unlock_always(&c_seg->c_lock);
2178                         }
2179                         c_seg = c_seg_next;
2180                 }
2181         }
2182         vm_compressor_compact_and_swap(FALSE);
2183
2184         compaction_swapper_running = 0;
2185
2186         vm_swapout_ripe_segments = FALSE;
2187
2188         lck_mtx_unlock_always(c_list_lock);
2189
2190         thread_wakeup((event_t)&compaction_swapper_running);
2191 }
2192
2193
2194 void
2195 vm_consider_waking_compactor_swapper(void)
2196 {
2197         boolean_t       need_wakeup = FALSE;
2198
2199         if (c_segment_count == 0) {
2200                 return;
2201         }
2202
2203         if (compaction_swapper_running || compaction_swapper_awakened) {
2204                 return;
2205         }
2206
2207         if (!compaction_swapper_inited && !compaction_swapper_init_now) {
2208                 compaction_swapper_init_now = 1;
2209                 need_wakeup = TRUE;
2210         }
2211
2212         if (c_minor_count && (COMPRESSOR_NEEDS_TO_MINOR_COMPACT())) {
2213                 need_wakeup = TRUE;
2214         } else if (compressor_needs_to_swap()) {
2215                 need_wakeup = TRUE;
2216         } else if (c_minor_count) {
2217                 uint64_t        total_bytes;
2218
2219                 total_bytes = compressor_object->resident_page_count * PAGE_SIZE_64;
2220
2221                 if ((total_bytes - compressor_bytes_used) > total_bytes / 10) {
2222                         need_wakeup = TRUE;
2223                 }
2224         }
2225         if (need_wakeup == TRUE) {
2226                 lck_mtx_lock_spin_always(c_list_lock);
2227
2228                 fastwake_warmup = FALSE;
2229
2230                 if (compaction_swapper_running == 0 && compaction_swapper_awakened == 0) {
2231                         memoryshot(VM_WAKEUP_COMPACTOR_SWAPPER, DBG_FUNC_NONE);
2232
2233                         compaction_swapper_awakened = 1;
2234                         thread_wakeup((event_t)&c_compressor_swap_trigger);
2235                 }
2236                 lck_mtx_unlock_always(c_list_lock);
2237         }
2238 }
2239
2240
2241 #define C_SWAPOUT_LIMIT                 4
2242 #define DELAYED_COMPACTIONS_PER_PASS    30
2243
2244 void
2245 vm_compressor_do_delayed_compactions(boolean_t flush_all)
2246 {
2247         c_segment_t     c_seg;
2248         int             number_compacted = 0;
2249         boolean_t       needs_to_swap = FALSE;
2250
2251
2252 #if !CONFIG_EMBEDDED
2253         LCK_MTX_ASSERT(c_list_lock, LCK_MTX_ASSERT_OWNED);
2254 #endif /* !CONFIG_EMBEDDED */
2255
2256         while (!queue_empty(&c_minor_list_head) && needs_to_swap == FALSE) {
2257                 c_seg = (c_segment_t)queue_first(&c_minor_list_head);
2258
2259                 lck_mtx_lock_spin_always(&c_seg->c_lock);
2260
2261                 if (c_seg->c_busy) {
2262                         lck_mtx_unlock_always(c_list_lock);
2263                         c_seg_wait_on_busy(c_seg);
2264                         lck_mtx_lock_spin_always(c_list_lock);
2265
2266                         continue;
2267                 }
2268                 C_SEG_BUSY(c_seg);
2269
2270                 c_seg_do_minor_compaction_and_unlock(c_seg, TRUE, FALSE, TRUE);
2271
2272                 if (VM_CONFIG_SWAP_IS_ACTIVE && (number_compacted++ > DELAYED_COMPACTIONS_PER_PASS)) {
2273                         if ((flush_all == TRUE || compressor_needs_to_swap() == TRUE) && c_swapout_count < C_SWAPOUT_LIMIT) {
2274                                 needs_to_swap = TRUE;
2275                         }
2276
2277                         number_compacted = 0;
2278                 }
2279                 lck_mtx_lock_spin_always(c_list_lock);
2280         }
2281 }
2282
2283
2284 #define C_SEGMENT_SWAPPEDIN_AGE_LIMIT   10
2285
2286 static void
2287 vm_compressor_age_swapped_in_segments(boolean_t flush_all)
2288 {
2289         c_segment_t     c_seg;
2290         clock_sec_t     now;
2291         clock_nsec_t    nsec;
2292
2293         clock_get_system_nanotime(&now, &nsec);
2294
2295         while (!queue_empty(&c_swappedin_list_head)) {
2296                 c_seg = (c_segment_t)queue_first(&c_swappedin_list_head);
2297
2298                 if (flush_all == FALSE && (now - c_seg->c_swappedin_ts) < C_SEGMENT_SWAPPEDIN_AGE_LIMIT) {
2299                         break;
2300                 }
2301
2302                 lck_mtx_lock_spin_always(&c_seg->c_lock);
2303
2304                 c_seg_switch_state(c_seg, C_ON_AGE_Q, FALSE);
2305
2306                 lck_mtx_unlock_always(&c_seg->c_lock);
2307         }
2308 }
2309
2310
2311 extern  int     vm_num_swap_files;
2312 extern  int     vm_num_pinned_swap_files;
2313 extern  int     vm_swappin_enabled;
2314
2315 extern  unsigned int    vm_swapfile_total_segs_used;
2316 extern  unsigned int    vm_swapfile_total_segs_alloced;
2317
2318
2319 void
2320 vm_compressor_flush(void)
2321 {
2322         uint64_t        vm_swap_put_failures_at_start;
2323         wait_result_t   wait_result = 0;
2324         AbsoluteTime    startTime, endTime;
2325         clock_sec_t     now_sec;
2326         clock_nsec_t    now_nsec;
2327         uint64_t        nsec;
2328
2329         HIBLOG("vm_compressor_flush - starting\n");
2330
2331         clock_get_uptime(&startTime);
2332
2333         lck_mtx_lock_spin_always(c_list_lock);
2334
2335         fastwake_warmup = FALSE;
2336         compaction_swapper_abort = 1;
2337
2338         while (compaction_swapper_running) {
2339                 assert_wait((event_t)&compaction_swapper_running, THREAD_UNINT);
2340
2341                 lck_mtx_unlock_always(c_list_lock);
2342
2343                 thread_block(THREAD_CONTINUE_NULL);
2344
2345                 lck_mtx_lock_spin_always(c_list_lock);
2346         }
2347         compaction_swapper_abort = 0;
2348         compaction_swapper_running = 1;
2349
2350         hibernate_flushing = TRUE;
2351         hibernate_no_swapspace = FALSE;
2352         c_generation_id_flush_barrier = c_generation_id + 1000;
2353
2354         clock_get_system_nanotime(&now_sec, &now_nsec);
2355         hibernate_flushing_deadline = now_sec + HIBERNATE_FLUSHING_SECS_TO_COMPLETE;
2356
2357         vm_swap_put_failures_at_start = vm_swap_put_failures;
2358
2359         vm_compressor_compact_and_swap(TRUE);
2360
2361         while (!queue_empty(&c_swapout_list_head)) {
2362                 assert_wait_timeout((event_t) &compaction_swapper_running, THREAD_INTERRUPTIBLE, 5000, 1000 * NSEC_PER_USEC);
2363
2364                 lck_mtx_unlock_always(c_list_lock);
2365
2366                 wait_result = thread_block(THREAD_CONTINUE_NULL);
2367
2368                 lck_mtx_lock_spin_always(c_list_lock);
2369
2370                 if (wait_result == THREAD_TIMED_OUT) {
2371                         break;
2372                 }
2373         }
2374         hibernate_flushing = FALSE;
2375         compaction_swapper_running = 0;
2376
2377         if (vm_swap_put_failures > vm_swap_put_failures_at_start) {
2378                 HIBLOG("vm_compressor_flush failed to clean %llu segments - vm_page_compressor_count(%d)\n",
2379                     vm_swap_put_failures - vm_swap_put_failures_at_start, VM_PAGE_COMPRESSOR_COUNT);
2380         }
2381
2382         lck_mtx_unlock_always(c_list_lock);
2383
2384         thread_wakeup((event_t)&compaction_swapper_running);
2385
2386         clock_get_uptime(&endTime);
2387         SUB_ABSOLUTETIME(&endTime, &startTime);
2388         absolutetime_to_nanoseconds(endTime, &nsec);
2389
2390         HIBLOG("vm_compressor_flush completed - took %qd msecs - vm_num_swap_files = %d, vm_num_pinned_swap_files = %d, vm_swappin_enabled = %d\n",
2391             nsec / 1000000ULL, vm_num_swap_files, vm_num_pinned_swap_files, vm_swappin_enabled);
2392 }
2393
2394
2395 int             compaction_swap_trigger_thread_awakened = 0;
2396
2397 static void
2398 vm_compressor_swap_trigger_thread(void)
2399 {
2400         current_thread()->options |= TH_OPT_VMPRIV;
2401
2402         /*
2403          * compaction_swapper_init_now is set when the first call to
2404          * vm_consider_waking_compactor_swapper is made from
2405          * vm_pageout_scan... since this function is called upon
2406          * thread creation, we want to make sure to delay adjusting
2407          * the tuneables until we are awakened via vm_pageout_scan
2408          * so that we are at a point where the vm_swapfile_open will
2409          * be operating on the correct directory (in case the default
2410          * of /var/vm/  is overridden by the dymanic_pager
2411          */
2412         if (compaction_swapper_init_now) {
2413                 vm_compaction_swapper_do_init();
2414
2415                 if (vm_pageout_state.vm_restricted_to_single_processor == TRUE) {
2416                         thread_vm_bind_group_add();
2417                 }
2418                 thread_set_thread_name(current_thread(), "VM_cswap_trigger");
2419                 compaction_swapper_init_now = 0;
2420         }
2421         lck_mtx_lock_spin_always(c_list_lock);
2422
2423         compaction_swap_trigger_thread_awakened++;
2424         compaction_swapper_awakened = 0;
2425
2426         if (compaction_swapper_running == 0) {
2427                 compaction_swapper_running = 1;
2428
2429                 vm_compressor_compact_and_swap(FALSE);
2430
2431                 compaction_swapper_running = 0;
2432         }
2433         assert_wait((event_t)&c_compressor_swap_trigger, THREAD_UNINT);
2434
2435         if (compaction_swapper_running == 0) {
2436                 thread_wakeup((event_t)&compaction_swapper_running);
2437         }
2438
2439         lck_mtx_unlock_always(c_list_lock);
2440
2441         thread_block((thread_continue_t)vm_compressor_swap_trigger_thread);
2442
2443         /* NOTREACHED */
2444 }
2445
2446
2447 void
2448 vm_compressor_record_warmup_start(void)
2449 {
2450         c_segment_t     c_seg;
2451
2452         lck_mtx_lock_spin_always(c_list_lock);
2453
2454         if (first_c_segment_to_warm_generation_id == 0) {
2455                 if (!queue_empty(&c_age_list_head)) {
2456                         c_seg = (c_segment_t)queue_last(&c_age_list_head);
2457
2458                         first_c_segment_to_warm_generation_id = c_seg->c_generation_id;
2459                 } else {
2460                         first_c_segment_to_warm_generation_id = 0;
2461                 }
2462
2463                 fastwake_recording_in_progress = TRUE;
2464         }
2465         lck_mtx_unlock_always(c_list_lock);
2466 }
2467
2468
2469 void
2470 vm_compressor_record_warmup_end(void)
2471 {
2472         c_segment_t     c_seg;
2473
2474         lck_mtx_lock_spin_always(c_list_lock);
2475
2476         if (fastwake_recording_in_progress == TRUE) {
2477                 if (!queue_empty(&c_age_list_head)) {
2478                         c_seg = (c_segment_t)queue_last(&c_age_list_head);
2479
2480                         last_c_segment_to_warm_generation_id = c_seg->c_generation_id;
2481                 } else {
2482                         last_c_segment_to_warm_generation_id = first_c_segment_to_warm_generation_id;
2483                 }
2484
2485                 fastwake_recording_in_progress = FALSE;
2486
2487                 HIBLOG("vm_compressor_record_warmup (%qd - %qd)\n", first_c_segment_to_warm_generation_id, last_c_segment_to_warm_generation_id);
2488         }
2489         lck_mtx_unlock_always(c_list_lock);
2490 }
2491
2492
2493 #define DELAY_TRIM_ON_WAKE_SECS         25
2494
2495 void
2496 vm_compressor_delay_trim(void)
2497 {
2498         clock_sec_t     sec;
2499         clock_nsec_t    nsec;
2500
2501         clock_get_system_nanotime(&sec, &nsec);
2502         dont_trim_until_ts = sec + DELAY_TRIM_ON_WAKE_SECS;
2503 }
2504
2505
2506 void
2507 vm_compressor_do_warmup(void)
2508 {
2509         lck_mtx_lock_spin_always(c_list_lock);
2510
2511         if (first_c_segment_to_warm_generation_id == last_c_segment_to_warm_generation_id) {
2512                 first_c_segment_to_warm_generation_id = last_c_segment_to_warm_generation_id = 0;
2513
2514                 lck_mtx_unlock_always(c_list_lock);
2515                 return;
2516         }
2517
2518         if (compaction_swapper_running == 0 && compaction_swapper_awakened == 0) {
2519                 fastwake_warmup = TRUE;
2520
2521                 compaction_swapper_awakened = 1;
2522                 thread_wakeup((event_t)&c_compressor_swap_trigger);
2523         }
2524         lck_mtx_unlock_always(c_list_lock);
2525 }
2526
2527 void
2528 do_fastwake_warmup_all(void)
2529 {
2530         lck_mtx_lock_spin_always(c_list_lock);
2531
2532         if (queue_empty(&c_swappedout_list_head) && queue_empty(&c_swappedout_sparse_list_head)) {
2533                 lck_mtx_unlock_always(c_list_lock);
2534                 return;
2535         }
2536
2537         fastwake_warmup = TRUE;
2538
2539         do_fastwake_warmup(&c_swappedout_list_head, TRUE);
2540
2541         do_fastwake_warmup(&c_swappedout_sparse_list_head, TRUE);
2542
2543         fastwake_warmup = FALSE;
2544
2545         lck_mtx_unlock_always(c_list_lock);
2546 }
2547
2548 void
2549 do_fastwake_warmup(queue_head_t *c_queue, boolean_t consider_all_cseg)
2550 {
2551         c_segment_t     c_seg = NULL;
2552         AbsoluteTime    startTime, endTime;
2553         uint64_t        nsec;
2554
2555
2556         HIBLOG("vm_compressor_fastwake_warmup (%qd - %qd) - starting\n", first_c_segment_to_warm_generation_id, last_c_segment_to_warm_generation_id);
2557
2558         clock_get_uptime(&startTime);
2559
2560         lck_mtx_unlock_always(c_list_lock);
2561
2562         proc_set_thread_policy(current_thread(),
2563             TASK_POLICY_INTERNAL, TASK_POLICY_IO, THROTTLE_LEVEL_COMPRESSOR_TIER2);
2564
2565         PAGE_REPLACEMENT_DISALLOWED(TRUE);
2566
2567         lck_mtx_lock_spin_always(c_list_lock);
2568
2569         while (!queue_empty(c_queue) && fastwake_warmup == TRUE) {
2570                 c_seg = (c_segment_t) queue_first(c_queue);
2571
2572                 if (consider_all_cseg == FALSE) {
2573                         if (c_seg->c_generation_id < first_c_segment_to_warm_generation_id ||
2574                             c_seg->c_generation_id > last_c_segment_to_warm_generation_id) {
2575                                 break;
2576                         }
2577
2578                         if (vm_page_free_count < (AVAILABLE_MEMORY / 4)) {
2579                                 break;
2580                         }
2581                 }
2582
2583                 lck_mtx_lock_spin_always(&c_seg->c_lock);
2584                 lck_mtx_unlock_always(c_list_lock);
2585
2586                 if (c_seg->c_busy) {
2587                         PAGE_REPLACEMENT_DISALLOWED(FALSE);
2588                         c_seg_wait_on_busy(c_seg);
2589                         PAGE_REPLACEMENT_DISALLOWED(TRUE);
2590                 } else {
2591                         if (c_seg_swapin(c_seg, TRUE, FALSE) == 0) {
2592                                 lck_mtx_unlock_always(&c_seg->c_lock);
2593                         }
2594                         c_segment_warmup_count++;
2595
2596                         PAGE_REPLACEMENT_DISALLOWED(FALSE);
2597                         vm_pageout_io_throttle();
2598                         PAGE_REPLACEMENT_DISALLOWED(TRUE);
2599                 }
2600                 lck_mtx_lock_spin_always(c_list_lock);
2601         }
2602         lck_mtx_unlock_always(c_list_lock);
2603
2604         PAGE_REPLACEMENT_DISALLOWED(FALSE);
2605
2606         proc_set_thread_policy(current_thread(),
2607             TASK_POLICY_INTERNAL, TASK_POLICY_IO, THROTTLE_LEVEL_COMPRESSOR_TIER0);
2608
2609         clock_get_uptime(&endTime);
2610         SUB_ABSOLUTETIME(&endTime, &startTime);
2611         absolutetime_to_nanoseconds(endTime, &nsec);
2612
2613         HIBLOG("vm_compressor_fastwake_warmup completed - took %qd msecs\n", nsec / 1000000ULL);
2614
2615         lck_mtx_lock_spin_always(c_list_lock);
2616
2617         if (consider_all_cseg == FALSE) {
2618                 first_c_segment_to_warm_generation_id = last_c_segment_to_warm_generation_id = 0;
2619         }
2620 }
2621
2622
2623 void
2624 vm_compressor_compact_and_swap(boolean_t flush_all)
2625 {
2626         c_segment_t     c_seg, c_seg_next;
2627         boolean_t       keep_compacting;
2628         clock_sec_t     now;
2629         clock_nsec_t    nsec;
2630
2631
2632         if (fastwake_warmup == TRUE) {
2633                 uint64_t        starting_warmup_count;
2634
2635                 starting_warmup_count = c_segment_warmup_count;
2636
2637                 KERNEL_DEBUG_CONSTANT(IOKDBG_CODE(DBG_HIBERNATE, 11) | DBG_FUNC_START, c_segment_warmup_count,
2638                     first_c_segment_to_warm_generation_id, last_c_segment_to_warm_generation_id, 0, 0);
2639                 do_fastwake_warmup(&c_swappedout_list_head, FALSE);
2640                 KERNEL_DEBUG_CONSTANT(IOKDBG_CODE(DBG_HIBERNATE, 11) | DBG_FUNC_END, c_segment_warmup_count, c_segment_warmup_count - starting_warmup_count, 0, 0, 0);
2641
2642                 fastwake_warmup = FALSE;
2643         }
2644
2645         /*
2646          * it's possible for the c_age_list_head to be empty if we
2647          * hit our limits for growing the compressor pool and we subsequently
2648          * hibernated... on the next hibernation we could see the queue as
2649          * empty and not proceeed even though we have a bunch of segments on
2650          * the swapped in queue that need to be dealt with.
2651          */
2652         vm_compressor_do_delayed_compactions(flush_all);
2653
2654         vm_compressor_age_swapped_in_segments(flush_all);
2655
2656         /*
2657          * we only need to grab the timestamp once per
2658          * invocation of this function since the
2659          * timescale we're interested in is measured
2660          * in days
2661          */
2662         clock_get_system_nanotime(&now, &nsec);
2663
2664         while (!queue_empty(&c_age_list_head) && compaction_swapper_abort == 0) {
2665                 if (hibernate_flushing == TRUE) {
2666                         clock_sec_t     sec;
2667
2668                         if (hibernate_should_abort()) {
2669                                 HIBLOG("vm_compressor_flush - hibernate_should_abort returned TRUE\n");
2670                                 break;
2671                         }
2672                         if (hibernate_no_swapspace == TRUE) {
2673                                 HIBLOG("vm_compressor_flush - out of swap space\n");
2674                                 break;
2675                         }
2676                         if (vm_swap_files_pinned() == FALSE) {
2677                                 HIBLOG("vm_compressor_flush - unpinned swap files\n");
2678                                 break;
2679                         }
2680                         if (hibernate_in_progress_with_pinned_swap == TRUE &&
2681                             (vm_swapfile_total_segs_alloced == vm_swapfile_total_segs_used)) {
2682                                 HIBLOG("vm_compressor_flush - out of pinned swap space\n");
2683                                 break;
2684                         }
2685                         clock_get_system_nanotime(&sec, &nsec);
2686
2687                         if (sec > hibernate_flushing_deadline) {
2688                                 HIBLOG("vm_compressor_flush - failed to finish before deadline\n");
2689                                 break;
2690                         }
2691                 }
2692                 if (c_swapout_count >= C_SWAPOUT_LIMIT) {
2693                         assert_wait_timeout((event_t) &compaction_swapper_running, THREAD_INTERRUPTIBLE, 100, 1000 * NSEC_PER_USEC);
2694
2695                         lck_mtx_unlock_always(c_list_lock);
2696
2697                         thread_block(THREAD_CONTINUE_NULL);
2698
2699                         lck_mtx_lock_spin_always(c_list_lock);
2700                 }
2701                 /*
2702                  * Minor compactions
2703                  */
2704                 vm_compressor_do_delayed_compactions(flush_all);
2705
2706                 vm_compressor_age_swapped_in_segments(flush_all);
2707
2708                 if (c_swapout_count >= C_SWAPOUT_LIMIT) {
2709                         /*
2710                          * we timed out on the above thread_block
2711                          * let's loop around and try again
2712                          * the timeout allows us to continue
2713                          * to do minor compactions to make
2714                          * more memory available
2715                          */
2716                         continue;
2717                 }
2718
2719                 /*
2720                  * Swap out segments?
2721                  */
2722                 if (flush_all == FALSE) {
2723                         boolean_t       needs_to_swap;
2724
2725                         lck_mtx_unlock_always(c_list_lock);
2726
2727                         needs_to_swap = compressor_needs_to_swap();
2728
2729 #if !CONFIG_EMBEDDED
2730                         if (needs_to_swap == TRUE && vm_swap_low_on_space()) {
2731                                 vm_compressor_take_paging_space_action();
2732                         }
2733 #endif /* !CONFIG_EMBEDDED */
2734
2735                         lck_mtx_lock_spin_always(c_list_lock);
2736
2737                         if (needs_to_swap == FALSE) {
2738                                 break;
2739                         }
2740                 }
2741                 if (queue_empty(&c_age_list_head)) {
2742                         break;
2743                 }
2744                 c_seg = (c_segment_t) queue_first(&c_age_list_head);
2745
2746                 assert(c_seg->c_state == C_ON_AGE_Q);
2747
2748                 if (flush_all == TRUE && c_seg->c_generation_id > c_generation_id_flush_barrier) {
2749                         break;
2750                 }
2751
2752                 lck_mtx_lock_spin_always(&c_seg->c_lock);
2753
2754                 if (c_seg->c_busy) {
2755                         lck_mtx_unlock_always(c_list_lock);
2756                         c_seg_wait_on_busy(c_seg);
2757                         lck_mtx_lock_spin_always(c_list_lock);
2758
2759                         continue;
2760                 }
2761                 C_SEG_BUSY(c_seg);
2762
2763                 if (c_seg_do_minor_compaction_and_unlock(c_seg, FALSE, TRUE, TRUE)) {
2764                         /*
2765                          * found an empty c_segment and freed it
2766                          * so go grab the next guy in the queue
2767                          */
2768                         c_seg_major_compact_stats.count_of_freed_segs++;
2769                         continue;
2770                 }
2771                 /*
2772                  * Major compaction
2773                  */
2774                 keep_compacting = TRUE;
2775
2776                 while (keep_compacting == TRUE) {
2777                         assert(c_seg->c_busy);
2778
2779                         /* look for another segment to consolidate */
2780
2781                         c_seg_next = (c_segment_t) queue_next(&c_seg->c_age_list);
2782
2783                         if (queue_end(&c_age_list_head, (queue_entry_t)c_seg_next)) {
2784                                 break;
2785                         }
2786
2787                         assert(c_seg_next->c_state == C_ON_AGE_Q);
2788
2789                         if (c_seg_major_compact_ok(c_seg, c_seg_next) == FALSE) {
2790                                 break;
2791                         }
2792
2793                         lck_mtx_lock_spin_always(&c_seg_next->c_lock);
2794
2795                         if (c_seg_next->c_busy) {
2796                                 lck_mtx_unlock_always(c_list_lock);
2797                                 c_seg_wait_on_busy(c_seg_next);
2798                                 lck_mtx_lock_spin_always(c_list_lock);
2799
2800                                 continue;
2801                         }
2802                         /* grab that segment */
2803                         C_SEG_BUSY(c_seg_next);
2804
2805                         if (c_seg_do_minor_compaction_and_unlock(c_seg_next, FALSE, TRUE, TRUE)) {
2806                                 /*
2807                                  * found an empty c_segment and freed it
2808                                  * so we can't continue to use c_seg_next
2809                                  */
2810                                 c_seg_major_compact_stats.count_of_freed_segs++;
2811                                 continue;
2812                         }
2813
2814                         /* unlock the list ... */
2815                         lck_mtx_unlock_always(c_list_lock);
2816
2817                         /* do the major compaction */
2818
2819                         keep_compacting = c_seg_major_compact(c_seg, c_seg_next);
2820
2821                         PAGE_REPLACEMENT_DISALLOWED(TRUE);
2822
2823                         lck_mtx_lock_spin_always(&c_seg_next->c_lock);
2824                         /*
2825                          * run a minor compaction on the donor segment
2826                          * since we pulled at least some of it's
2827                          * data into our target...  if we've emptied
2828                          * it, now is a good time to free it which
2829                          * c_seg_minor_compaction_and_unlock also takes care of
2830                          *
2831                          * by passing TRUE, we ask for c_busy to be cleared
2832                          * and c_wanted to be taken care of
2833                          */
2834                         if (c_seg_minor_compaction_and_unlock(c_seg_next, TRUE)) {
2835                                 c_seg_major_compact_stats.count_of_freed_segs++;
2836                         }
2837
2838                         PAGE_REPLACEMENT_DISALLOWED(FALSE);
2839
2840                         /* relock the list */
2841                         lck_mtx_lock_spin_always(c_list_lock);
2842                 } /* major compaction */
2843
2844                 lck_mtx_lock_spin_always(&c_seg->c_lock);
2845
2846                 assert(c_seg->c_busy);
2847                 assert(!c_seg->c_on_minorcompact_q);
2848
2849                 if (VM_CONFIG_SWAP_IS_ACTIVE) {
2850                         /*
2851                          * This mode of putting a generic c_seg on the swapout list is
2852                          * only supported when we have general swapping enabled
2853                          */
2854                         c_seg_switch_state(c_seg, C_ON_SWAPOUT_Q, FALSE);
2855                 } else {
2856                         if ((vm_swapout_ripe_segments == TRUE && c_overage_swapped_count < c_overage_swapped_limit)) {
2857                                 assert(VM_CONFIG_SWAP_IS_PRESENT);
2858                                 /*
2859                                  * we are running compressor sweeps with swap-behind
2860                                  * make sure the c_seg has aged enough before swapping it
2861                                  * out...
2862                                  */
2863                                 if ((now - c_seg->c_creation_ts) >= vm_ripe_target_age) {
2864                                         c_seg->c_overage_swap = TRUE;
2865                                         c_overage_swapped_count++;
2866                                         c_seg_switch_state(c_seg, C_ON_SWAPOUT_Q, FALSE);
2867                                 }
2868                         }
2869                 }
2870                 if (c_seg->c_state == C_ON_AGE_Q) {
2871                         /*
2872                          * this c_seg didn't get moved to the swapout queue
2873                          * so we need to move it out of the way...
2874                          * we just did a major compaction on it so put it
2875                          * on that queue
2876                          */
2877                         c_seg_switch_state(c_seg, C_ON_MAJORCOMPACT_Q, FALSE);
2878                 } else {
2879                         c_seg_major_compact_stats.wasted_space_in_swapouts += C_SEG_BUFSIZE - c_seg->c_bytes_used;
2880                         c_seg_major_compact_stats.count_of_swapouts++;
2881                 }
2882                 C_SEG_WAKEUP_DONE(c_seg);
2883
2884                 lck_mtx_unlock_always(&c_seg->c_lock);
2885
2886                 if (c_swapout_count) {
2887                         lck_mtx_unlock_always(c_list_lock);
2888
2889                         thread_wakeup((event_t)&c_swapout_list_head);
2890
2891                         lck_mtx_lock_spin_always(c_list_lock);
2892                 }
2893         }
2894 }
2895
2896
2897 static c_segment_t
2898 c_seg_allocate(c_segment_t *current_chead)
2899 {
2900         c_segment_t     c_seg;
2901         int             min_needed;
2902         int             size_to_populate;
2903
2904 #if !CONFIG_EMBEDDED
2905         if (vm_compressor_low_on_space()) {
2906                 vm_compressor_take_paging_space_action();
2907         }
2908 #endif /* !CONFIG_EMBEDDED */
2909
2910         if ((c_seg = *current_chead) == NULL) {
2911                 uint32_t        c_segno;
2912
2913                 lck_mtx_lock_spin_always(c_list_lock);
2914
2915                 while (c_segments_busy == TRUE) {
2916                         assert_wait((event_t) (&c_segments_busy), THREAD_UNINT);
2917
2918                         lck_mtx_unlock_always(c_list_lock);
2919
2920                         thread_block(THREAD_CONTINUE_NULL);
2921
2922                         lck_mtx_lock_spin_always(c_list_lock);
2923                 }
2924                 if (c_free_segno_head == (uint32_t)-1) {
2925                         uint32_t        c_segments_available_new;
2926
2927                         if (c_segments_available >= c_segments_limit || c_segment_pages_compressed >= c_segment_pages_compressed_limit) {
2928                                 lck_mtx_unlock_always(c_list_lock);
2929
2930                                 return NULL;
2931                         }
2932                         c_segments_busy = TRUE;
2933                         lck_mtx_unlock_always(c_list_lock);
2934
2935                         kernel_memory_populate(compressor_map, (vm_offset_t)c_segments_next_page,
2936                             PAGE_SIZE, KMA_KOBJECT, VM_KERN_MEMORY_COMPRESSOR);
2937                         c_segments_next_page += PAGE_SIZE;
2938
2939                         c_segments_available_new = c_segments_available + C_SEGMENTS_PER_PAGE;
2940
2941                         if (c_segments_available_new > c_segments_limit) {
2942                                 c_segments_available_new = c_segments_limit;
2943                         }
2944
2945                         for (c_segno = c_segments_available + 1; c_segno < c_segments_available_new; c_segno++) {
2946                                 c_segments[c_segno - 1].c_segno = c_segno;
2947                         }
2948
2949                         lck_mtx_lock_spin_always(c_list_lock);
2950
2951                         c_segments[c_segno - 1].c_segno = c_free_segno_head;
2952                         c_free_segno_head = c_segments_available;
2953                         c_segments_available = c_segments_available_new;
2954
2955                         c_segments_busy = FALSE;
2956                         thread_wakeup((event_t) (&c_segments_busy));
2957                 }
2958                 c_segno = c_free_segno_head;
2959                 assert(c_segno >= 0 && c_segno < c_segments_limit);
2960
2961                 c_free_segno_head = (uint32_t)c_segments[c_segno].c_segno;
2962
2963                 /*
2964                  * do the rest of the bookkeeping now while we're still behind
2965                  * the list lock and grab our generation id now into a local
2966                  * so that we can install it once we have the c_seg allocated
2967                  */
2968                 c_segment_count++;
2969                 if (c_segment_count > c_segment_count_max) {
2970                         c_segment_count_max = c_segment_count;
2971                 }
2972
2973                 lck_mtx_unlock_always(c_list_lock);
2974
2975                 c_seg = (c_segment_t)zalloc(compressor_segment_zone);
2976                 bzero((char *)c_seg, sizeof(struct c_segment));
2977
2978                 c_seg->c_store.c_buffer = (int32_t *)C_SEG_BUFFER_ADDRESS(c_segno);
2979
2980                 lck_mtx_init(&c_seg->c_lock, &vm_compressor_lck_grp, &vm_compressor_lck_attr);
2981
2982                 c_seg->c_state = C_IS_EMPTY;
2983                 c_seg->c_firstemptyslot = C_SLOT_MAX_INDEX;
2984                 c_seg->c_mysegno = c_segno;
2985
2986                 lck_mtx_lock_spin_always(c_list_lock);
2987                 c_empty_count++;
2988                 c_seg_switch_state(c_seg, C_IS_FILLING, FALSE);
2989                 c_segments[c_segno].c_seg = c_seg;
2990                 assert(c_segments[c_segno].c_segno > c_segments_available);
2991                 lck_mtx_unlock_always(c_list_lock);
2992
2993                 *current_chead = c_seg;
2994
2995 #if DEVELOPMENT || DEBUG
2996                 C_SEG_MAKE_WRITEABLE(c_seg);
2997 #endif
2998         }
2999         c_seg_alloc_nextslot(c_seg);
3000
3001         size_to_populate = C_SEG_ALLOCSIZE - C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset);
3002
3003         if (size_to_populate) {
3004                 min_needed = PAGE_SIZE + (C_SEG_ALLOCSIZE - C_SEG_BUFSIZE);
3005
3006                 if (C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset - c_seg->c_nextoffset) < (unsigned) min_needed) {
3007                         if (size_to_populate > C_SEG_MAX_POPULATE_SIZE) {
3008                                 size_to_populate = C_SEG_MAX_POPULATE_SIZE;
3009                         }
3010
3011                         OSAddAtomic64(size_to_populate / PAGE_SIZE, &vm_pageout_vminfo.vm_compressor_pages_grabbed);
3012
3013                         kernel_memory_populate(compressor_map,
3014                             (vm_offset_t) &c_seg->c_store.c_buffer[c_seg->c_populated_offset],
3015                             size_to_populate,
3016                             KMA_COMPRESSOR,
3017                             VM_KERN_MEMORY_COMPRESSOR);
3018                 } else {
3019                         size_to_populate = 0;
3020                 }
3021         }
3022         PAGE_REPLACEMENT_DISALLOWED(TRUE);
3023
3024         lck_mtx_lock_spin_always(&c_seg->c_lock);
3025
3026         if (size_to_populate) {
3027                 c_seg->c_populated_offset += C_SEG_BYTES_TO_OFFSET(size_to_populate);
3028         }
3029
3030         return c_seg;
3031 }
3032
3033 #if DEVELOPMENT || DEBUG
3034 #if CONFIG_FREEZE
3035 extern boolean_t memorystatus_freeze_to_memory;
3036 #endif /* CONFIG_FREEZE */
3037 #endif /* DEVELOPMENT || DEBUG */
3038
3039 static void
3040 c_current_seg_filled(c_segment_t c_seg, c_segment_t *current_chead)
3041 {
3042         uint32_t        unused_bytes;
3043         uint32_t        offset_to_depopulate;
3044         int             new_state = C_ON_AGE_Q;
3045         clock_sec_t     sec;
3046         clock_nsec_t    nsec;
3047         boolean_t       head_insert = FALSE;
3048
3049         unused_bytes = trunc_page_32(C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset - c_seg->c_nextoffset));
3050
3051 #ifndef _OPEN_SOURCE
3052         /* TODO: The HW codec can generate, lazily, a '2nd page not mapped'
3053          * exception. So on such a platform, or platforms where we're confident
3054          * the codec does not require a buffer page to absorb trailing writes,
3055          * we can create an unmapped hole at the tail of the segment, rather
3056          * than a populated mapping. This will also guarantee that the codec
3057          * does not overwrite valid data past the edge of the segment and
3058          * thus eliminate the depopulation overhead.
3059          */
3060 #endif
3061         if (unused_bytes) {
3062                 offset_to_depopulate = C_SEG_BYTES_TO_OFFSET(round_page_32(C_SEG_OFFSET_TO_BYTES(c_seg->c_nextoffset)));
3063
3064                 /*
3065                  *  release the extra physical page(s) at the end of the segment
3066                  */
3067                 lck_mtx_unlock_always(&c_seg->c_lock);
3068
3069                 kernel_memory_depopulate(
3070                         compressor_map,
3071                         (vm_offset_t) &c_seg->c_store.c_buffer[offset_to_depopulate],
3072                         unused_bytes,
3073                         KMA_COMPRESSOR);
3074
3075                 lck_mtx_lock_spin_always(&c_seg->c_lock);
3076
3077                 c_seg->c_populated_offset = offset_to_depopulate;
3078         }
3079         assert(C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset) <= C_SEG_BUFSIZE);
3080
3081 #if DEVELOPMENT || DEBUG
3082         {
3083                 boolean_t       c_seg_was_busy = FALSE;
3084
3085                 if (!c_seg->c_busy) {
3086                         C_SEG_BUSY(c_seg);
3087                 } else {
3088                         c_seg_was_busy = TRUE;
3089                 }
3090
3091                 lck_mtx_unlock_always(&c_seg->c_lock);
3092
3093                 C_SEG_WRITE_PROTECT(c_seg);
3094
3095                 lck_mtx_lock_spin_always(&c_seg->c_lock);
3096
3097                 if (c_seg_was_busy == FALSE) {
3098                         C_SEG_WAKEUP_DONE(c_seg);
3099                 }
3100         }
3101 #endif
3102
3103 #if CONFIG_FREEZE
3104         if (current_chead == (c_segment_t*)&freezer_chead &&
3105             VM_CONFIG_SWAP_IS_PRESENT &&
3106             VM_CONFIG_FREEZER_SWAP_IS_ACTIVE
3107 #if DEVELOPMENT || DEBUG
3108             && !memorystatus_freeze_to_memory
3109 #endif /* DEVELOPMENT || DEBUG */
3110             ) {
3111                 new_state = C_ON_SWAPOUT_Q;
3112         }
3113 #endif /* CONFIG_FREEZE */
3114
3115         if (vm_darkwake_mode == TRUE) {
3116                 new_state = C_ON_SWAPOUT_Q;
3117                 head_insert = TRUE;
3118         }
3119
3120         clock_get_system_nanotime(&sec, &nsec);
3121         c_seg->c_creation_ts = (uint32_t)sec;
3122
3123         lck_mtx_lock_spin_always(c_list_lock);
3124
3125         c_seg->c_generation_id = c_generation_id++;
3126         c_seg_switch_state(c_seg, new_state, head_insert);
3127
3128 #if CONFIG_FREEZE
3129         if (c_seg->c_state == C_ON_SWAPOUT_Q) {
3130                 /*
3131                  * darkwake and freezer can't co-exist together
3132                  * We'll need to fix this accounting as a start.
3133                  */
3134                 assert(vm_darkwake_mode == FALSE);
3135                 c_freezer_swapout_page_count += (C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset)) / PAGE_SIZE_64;
3136         }
3137 #endif /* CONFIG_FREEZE */
3138
3139         if (c_seg->c_state == C_ON_AGE_Q && C_SEG_UNUSED_BYTES(c_seg) >= PAGE_SIZE) {
3140                 c_seg_need_delayed_compaction(c_seg, TRUE);
3141         }
3142
3143         lck_mtx_unlock_always(c_list_lock);
3144
3145         if (c_seg->c_state == C_ON_SWAPOUT_Q) {
3146                 thread_wakeup((event_t)&c_swapout_list_head);
3147         }
3148
3149         *current_chead = NULL;
3150 }
3151
3152
3153 /*
3154  * returns with c_seg locked
3155  */
3156 void
3157 c_seg_swapin_requeue(c_segment_t c_seg, boolean_t has_data, boolean_t minor_compact_ok, boolean_t age_on_swapin_q)
3158 {
3159         clock_sec_t     sec;
3160         clock_nsec_t    nsec;
3161
3162         clock_get_system_nanotime(&sec, &nsec);
3163
3164         lck_mtx_lock_spin_always(c_list_lock);
3165         lck_mtx_lock_spin_always(&c_seg->c_lock);
3166
3167         assert(c_seg->c_busy_swapping);
3168         assert(c_seg->c_busy);
3169
3170         c_seg->c_busy_swapping = 0;
3171
3172         if (c_seg->c_overage_swap == TRUE) {
3173                 c_overage_swapped_count--;
3174                 c_seg->c_overage_swap = FALSE;
3175         }
3176         if (has_data == TRUE) {
3177                 if (age_on_swapin_q == TRUE) {
3178                         c_seg_switch_state(c_seg, C_ON_SWAPPEDIN_Q, FALSE);
3179                 } else {
3180                         c_seg_switch_state(c_seg, C_ON_AGE_Q, FALSE);
3181                 }
3182
3183                 if (minor_compact_ok == TRUE && !c_seg->c_on_minorcompact_q && C_SEG_UNUSED_BYTES(c_seg) >= PAGE_SIZE) {
3184                         c_seg_need_delayed_compaction(c_seg, TRUE);
3185                 }
3186         } else {
3187                 c_seg->c_store.c_buffer = (int32_t*) NULL;
3188                 c_seg->c_populated_offset = C_SEG_BYTES_TO_OFFSET(0);
3189
3190                 c_seg_switch_state(c_seg, C_ON_BAD_Q, FALSE);
3191         }
3192         c_seg->c_swappedin_ts = (uint32_t)sec;
3193
3194         lck_mtx_unlock_always(c_list_lock);
3195 }
3196
3197
3198
3199 /*
3200  * c_seg has to be locked and is returned locked if the c_seg isn't freed
3201  * PAGE_REPLACMENT_DISALLOWED has to be TRUE on entry and is returned TRUE
3202  * c_seg_swapin returns 1 if the c_seg was freed, 0 otherwise
3203  */
3204
3205 int
3206 c_seg_swapin(c_segment_t c_seg, boolean_t force_minor_compaction, boolean_t age_on_swapin_q)
3207 {
3208         vm_offset_t     addr = 0;
3209         uint32_t        io_size = 0;
3210         uint64_t        f_offset;
3211
3212         assert(C_SEG_IS_ONDISK(c_seg));
3213
3214 #if !CHECKSUM_THE_SWAP
3215         c_seg_trim_tail(c_seg);
3216 #endif
3217         io_size = round_page_32(C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset));
3218         f_offset = c_seg->c_store.c_swap_handle;
3219
3220         C_SEG_BUSY(c_seg);
3221         c_seg->c_busy_swapping = 1;
3222
3223         /*
3224          * This thread is likely going to block for I/O.
3225          * Make sure it is ready to run when the I/O completes because
3226          * it needs to clear the busy bit on the c_seg so that other
3227          * waiting threads can make progress too. To do that, boost
3228          * the rwlock_count so that the priority is boosted.
3229          */
3230         set_thread_rwlock_boost();
3231         lck_mtx_unlock_always(&c_seg->c_lock);
3232
3233         PAGE_REPLACEMENT_DISALLOWED(FALSE);
3234
3235         addr = (vm_offset_t)C_SEG_BUFFER_ADDRESS(c_seg->c_mysegno);
3236         c_seg->c_store.c_buffer = (int32_t*) addr;
3237
3238         kernel_memory_populate(compressor_map, addr, io_size, KMA_COMPRESSOR, VM_KERN_MEMORY_COMPRESSOR);
3239
3240         if (vm_swap_get(c_seg, f_offset, io_size) != KERN_SUCCESS) {
3241                 PAGE_REPLACEMENT_DISALLOWED(TRUE);
3242
3243                 kernel_memory_depopulate(compressor_map, addr, io_size, KMA_COMPRESSOR);
3244
3245                 c_seg_swapin_requeue(c_seg, FALSE, TRUE, age_on_swapin_q);
3246         } else {
3247 #if ENCRYPTED_SWAP
3248                 vm_swap_decrypt(c_seg);
3249 #endif /* ENCRYPTED_SWAP */
3250
3251 #if CHECKSUM_THE_SWAP
3252                 if (c_seg->cseg_swap_size != io_size) {
3253                         panic("swapin size doesn't match swapout size");
3254                 }
3255
3256                 if (c_seg->cseg_hash != vmc_hash((char*) c_seg->c_store.c_buffer, (int)io_size)) {
3257                         panic("c_seg_swapin - Swap hash mismatch\n");
3258                 }
3259 #endif /* CHECKSUM_THE_SWAP */
3260
3261                 PAGE_REPLACEMENT_DISALLOWED(TRUE);
3262
3263                 c_seg_swapin_requeue(c_seg, TRUE, force_minor_compaction == TRUE ? FALSE : TRUE, age_on_swapin_q);
3264
3265                 OSAddAtomic64(c_seg->c_bytes_used, &compressor_bytes_used);
3266
3267                 if (force_minor_compaction == TRUE) {
3268                         if (c_seg_minor_compaction_and_unlock(c_seg, FALSE)) {
3269                                 /*
3270                                  * c_seg was completely empty so it was freed,
3271                                  * so be careful not to reference it again
3272                                  *
3273                                  * Drop the rwlock_count so that the thread priority
3274                                  * is returned back to where it is supposed to be.
3275                                  */
3276                                 clear_thread_rwlock_boost();
3277                                 return 1;
3278                         }
3279
3280                         lck_mtx_lock_spin_always(&c_seg->c_lock);
3281                 }
3282         }
3283         C_SEG_WAKEUP_DONE(c_seg);
3284
3285         /*
3286          * Drop the rwlock_count so that the thread priority
3287          * is returned back to where it is supposed to be.
3288          */
3289         clear_thread_rwlock_boost();
3290
3291         return 0;
3292 }
3293
3294
3295 static void
3296 c_segment_sv_hash_drop_ref(int hash_indx)
3297 {
3298         struct c_sv_hash_entry o_sv_he, n_sv_he;
3299
3300         while (1) {
3301                 o_sv_he.he_record = c_segment_sv_hash_table[hash_indx].he_record;
3302
3303                 n_sv_he.he_ref = o_sv_he.he_ref - 1;
3304                 n_sv_he.he_data = o_sv_he.he_data;
3305
3306                 if (OSCompareAndSwap64((UInt64)o_sv_he.he_record, (UInt64)n_sv_he.he_record, (UInt64 *) &c_segment_sv_hash_table[hash_indx].he_record) == TRUE) {
3307                         if (n_sv_he.he_ref == 0) {
3308                                 OSAddAtomic(-1, &c_segment_svp_in_hash);
3309                         }
3310                         break;
3311                 }
3312         }
3313 }
3314
3315
3316 static int
3317 c_segment_sv_hash_insert(uint32_t data)
3318 {
3319         int             hash_sindx;
3320         int             misses;
3321         struct c_sv_hash_entry o_sv_he, n_sv_he;
3322         boolean_t       got_ref = FALSE;
3323
3324         if (data == 0) {
3325                 OSAddAtomic(1, &c_segment_svp_zero_compressions);
3326         } else {
3327                 OSAddAtomic(1, &c_segment_svp_nonzero_compressions);
3328         }
3329
3330         hash_sindx = data & C_SV_HASH_MASK;
3331
3332         for (misses = 0; misses < C_SV_HASH_MAX_MISS; misses++) {
3333                 o_sv_he.he_record = c_segment_sv_hash_table[hash_sindx].he_record;
3334
3335                 while (o_sv_he.he_data == data || o_sv_he.he_ref == 0) {
3336                         n_sv_he.he_ref = o_sv_he.he_ref + 1;
3337                         n_sv_he.he_data = data;
3338
3339                         if (OSCompareAndSwap64((UInt64)o_sv_he.he_record, (UInt64)n_sv_he.he_record, (UInt64 *) &c_segment_sv_hash_table[hash_sindx].he_record) == TRUE) {
3340                                 if (n_sv_he.he_ref == 1) {
3341                                         OSAddAtomic(1, &c_segment_svp_in_hash);
3342                                 }
3343                                 got_ref = TRUE;
3344                                 break;
3345                         }
3346                         o_sv_he.he_record = c_segment_sv_hash_table[hash_sindx].he_record;
3347                 }
3348                 if (got_ref == TRUE) {
3349                         break;
3350                 }
3351                 hash_sindx++;
3352
3353                 if (hash_sindx == C_SV_HASH_SIZE) {
3354                         hash_sindx = 0;
3355                 }
3356         }
3357         if (got_ref == FALSE) {
3358                 return -1;
3359         }
3360
3361         return hash_sindx;
3362 }
3363
3364
3365 #if RECORD_THE_COMPRESSED_DATA
3366
3367 static void
3368 c_compressed_record_data(char *src, int c_size)
3369 {
3370         if ((c_compressed_record_cptr + c_size + 4) >= c_compressed_record_ebuf) {
3371                 panic("c_compressed_record_cptr >= c_compressed_record_ebuf");
3372         }
3373
3374         *(int *)((void *)c_compressed_record_cptr) = c_size;
3375
3376         c_compressed_record_cptr += 4;
3377
3378         memcpy(c_compressed_record_cptr, src, c_size);
3379         c_compressed_record_cptr += c_size;
3380 }
3381 #endif
3382
3383
3384 static int
3385 c_compress_page(char *src, c_slot_mapping_t slot_ptr, c_segment_t *current_chead, char *scratch_buf)
3386 {
3387         int             c_size;
3388         int             c_rounded_size = 0;
3389         int             max_csize;
3390         c_slot_t        cs;
3391         c_segment_t     c_seg;
3392
3393         KERNEL_DEBUG(0xe0400000 | DBG_FUNC_START, *current_chead, 0, 0, 0, 0);
3394 retry:
3395         if ((c_seg = c_seg_allocate(current_chead)) == NULL) {
3396                 return 1;
3397         }
3398         /*
3399          * returns with c_seg lock held
3400          * and PAGE_REPLACEMENT_DISALLOWED(TRUE)...
3401          * c_nextslot has been allocated and
3402          * c_store.c_buffer populated
3403          */
3404         assert(c_seg->c_state == C_IS_FILLING);
3405
3406         cs = C_SEG_SLOT_FROM_INDEX(c_seg, c_seg->c_nextslot);
3407
3408         cs->c_packed_ptr = C_SLOT_PACK_PTR(slot_ptr);
3409         assert(slot_ptr == (c_slot_mapping_t)C_SLOT_UNPACK_PTR(cs));
3410
3411         cs->c_offset = c_seg->c_nextoffset;
3412
3413         max_csize = C_SEG_BUFSIZE - C_SEG_OFFSET_TO_BYTES((int32_t)cs->c_offset);
3414
3415         if (max_csize > PAGE_SIZE) {
3416                 max_csize = PAGE_SIZE;
3417         }
3418
3419 #if CHECKSUM_THE_DATA
3420         cs->c_hash_data = vmc_hash(src, PAGE_SIZE);
3421 #endif
3422         boolean_t incomp_copy = FALSE;
3423         int max_csize_adj = (max_csize - 4);
3424
3425         if (vm_compressor_algorithm() != VM_COMPRESSOR_DEFAULT_CODEC) {
3426 #if defined(__arm__) || defined(__arm64__)
3427                 uint16_t ccodec = CINVALID;
3428
3429                 if (max_csize >= C_SEG_OFFSET_ALIGNMENT_BOUNDARY) {
3430                         c_size = metacompressor((const uint8_t *) src,
3431                             (uint8_t *) &c_seg->c_store.c_buffer[cs->c_offset],
3432                             max_csize_adj, &ccodec,
3433                             scratch_buf, &incomp_copy);
3434 #if C_SEG_OFFSET_ALIGNMENT_BOUNDARY > 4
3435                         if (c_size > max_csize_adj) {
3436                                 c_size = -1;
3437                         }
3438 #endif
3439                 } else {
3440                         c_size = -1;
3441                 }
3442                 assert(ccodec == CCWK || ccodec == CCLZ4);
3443                 cs->c_codec = ccodec;
3444 #endif
3445         } else {
3446 #if defined(__arm__) || defined(__arm64__)
3447                 cs->c_codec = CCWK;
3448 #endif
3449 #if defined(__arm64__)
3450                 __unreachable_ok_push
3451                 if (PAGE_SIZE == 4096) {
3452                         c_size = WKdm_compress_4k((WK_word *)(uintptr_t)src, (WK_word *)(uintptr_t)&c_seg->c_store.c_buffer[cs->c_offset],
3453                             (WK_word *)(uintptr_t)scratch_buf, max_csize_adj);
3454                 } else {
3455                         c_size = WKdm_compress_16k((WK_word *)(uintptr_t)src, (WK_word *)(uintptr_t)&c_seg->c_store.c_buffer[cs->c_offset],
3456                             (WK_word *)(uintptr_t)scratch_buf, max_csize_adj);
3457                 }
3458                 __unreachable_ok_pop
3459 #else
3460                 c_size = WKdm_compress_new((const WK_word *)(uintptr_t)src, (WK_word *)(uintptr_t)&c_seg->c_store.c_buffer[cs->c_offset],
3461                     (WK_word *)(uintptr_t)scratch_buf, max_csize_adj);
3462 #endif
3463         }
3464         assertf(((c_size <= max_csize_adj) && (c_size >= -1)),
3465             "c_size invalid (%d, %d), cur compressions: %d", c_size, max_csize_adj, c_segment_pages_compressed);
3466
3467         if (c_size == -1) {
3468                 if (max_csize < PAGE_SIZE) {
3469                         c_current_seg_filled(c_seg, current_chead);
3470                         assert(*current_chead == NULL);
3471
3472                         lck_mtx_unlock_always(&c_seg->c_lock);
3473                         /* TODO: it may be worth requiring codecs to distinguish
3474                          * between incompressible inputs and failures due to
3475                          * budget exhaustion.
3476                          */
3477                         PAGE_REPLACEMENT_DISALLOWED(FALSE);
3478                         goto retry;
3479                 }
3480                 c_size = PAGE_SIZE;
3481
3482                 if (incomp_copy == FALSE) {
3483                         memcpy(&c_seg->c_store.c_buffer[cs->c_offset], src, c_size);
3484                 }
3485
3486                 OSAddAtomic(1, &c_segment_noncompressible_pages);
3487         } else if (c_size == 0) {
3488                 int             hash_index;
3489
3490                 /*
3491                  * special case - this is a page completely full of a single 32 bit value
3492                  */
3493                 hash_index = c_segment_sv_hash_insert(*(uint32_t *)(uintptr_t)src);
3494
3495                 if (hash_index != -1) {
3496                         slot_ptr->s_cindx = hash_index;
3497                         slot_ptr->s_cseg = C_SV_CSEG_ID;
3498
3499                         OSAddAtomic(1, &c_segment_svp_hash_succeeded);
3500 #if RECORD_THE_COMPRESSED_DATA
3501                         c_compressed_record_data(src, 4);
3502 #endif
3503                         goto sv_compression;
3504                 }
3505                 c_size = 4;
3506
3507                 memcpy(&c_seg->c_store.c_buffer[cs->c_offset], src, c_size);
3508
3509                 OSAddAtomic(1, &c_segment_svp_hash_failed);
3510         }
3511
3512 #if RECORD_THE_COMPRESSED_DATA
3513         c_compressed_record_data((char *)&c_seg->c_store.c_buffer[cs->c_offset], c_size);
3514 #endif
3515 #if CHECKSUM_THE_COMPRESSED_DATA
3516         cs->c_hash_compressed_data = vmc_hash((char *)&c_seg->c_store.c_buffer[cs->c_offset], c_size);
3517 #endif
3518 #if POPCOUNT_THE_COMPRESSED_DATA
3519         cs->c_pop_cdata = vmc_pop((uintptr_t) &c_seg->c_store.c_buffer[cs->c_offset], c_size);
3520 #endif
3521         c_rounded_size = (c_size + C_SEG_OFFSET_ALIGNMENT_MASK) & ~C_SEG_OFFSET_ALIGNMENT_MASK;
3522
3523         PACK_C_SIZE(cs, c_size);
3524         c_seg->c_bytes_used += c_rounded_size;
3525         c_seg->c_nextoffset += C_SEG_BYTES_TO_OFFSET(c_rounded_size);
3526         c_seg->c_slots_used++;
3527
3528         slot_ptr->s_cindx = c_seg->c_nextslot++;
3529         /* <csegno=0,indx=0> would mean "empty slot", so use csegno+1 */
3530         slot_ptr->s_cseg = c_seg->c_mysegno + 1;
3531
3532 sv_compression:
3533         if (c_seg->c_nextoffset >= C_SEG_OFF_LIMIT || c_seg->c_nextslot >= C_SLOT_MAX_INDEX) {
3534                 c_current_seg_filled(c_seg, current_chead);
3535                 assert(*current_chead == NULL);
3536         }
3537         lck_mtx_unlock_always(&c_seg->c_lock);
3538
3539         PAGE_REPLACEMENT_DISALLOWED(FALSE);
3540
3541 #if RECORD_THE_COMPRESSED_DATA
3542         if ((c_compressed_record_cptr - c_compressed_record_sbuf) >= C_SEG_ALLOCSIZE) {
3543                 c_compressed_record_write(c_compressed_record_sbuf, (int)(c_compressed_record_cptr - c_compressed_record_sbuf));
3544                 c_compressed_record_cptr = c_compressed_record_sbuf;
3545         }
3546 #endif
3547         if (c_size) {
3548                 OSAddAtomic64(c_size, &c_segment_compressed_bytes);
3549                 OSAddAtomic64(c_rounded_size, &compressor_bytes_used);
3550         }
3551         OSAddAtomic64(PAGE_SIZE, &c_segment_input_bytes);
3552
3553         OSAddAtomic(1, &c_segment_pages_compressed);
3554         OSAddAtomic(1, &sample_period_compression_count);
3555
3556         KERNEL_DEBUG(0xe0400000 | DBG_FUNC_END, *current_chead, c_size, c_segment_input_bytes, c_segment_compressed_bytes, 0);
3557
3558         return 0;
3559 }
3560
3561 static inline void
3562 sv_decompress(int32_t *ddst, int32_t pattern)
3563 {
3564 #if __x86_64__
3565         memset_word(ddst, pattern, PAGE_SIZE / sizeof(int32_t));
3566 #else
3567         size_t          i;
3568
3569         /* Unroll the pattern fill loop 4x to encourage the
3570          * compiler to emit NEON stores, cf.
3571          * <rdar://problem/25839866> Loop autovectorization
3572          * anomalies.
3573          * We use separate loops for each PAGE_SIZE
3574          * to allow the autovectorizer to engage, as PAGE_SIZE
3575          * is currently not a constant.
3576          */
3577
3578         __unreachable_ok_push
3579         if (PAGE_SIZE == 4096) {
3580                 for (i = 0; i < (4096U / sizeof(int32_t)); i += 4) {
3581                         *ddst++ = pattern;
3582                         *ddst++ = pattern;
3583                         *ddst++ = pattern;
3584                         *ddst++ = pattern;
3585                 }
3586         } else {
3587                 assert(PAGE_SIZE == 16384);
3588                 for (i = 0; i < (int)(16384U / sizeof(int32_t)); i += 4) {
3589                         *ddst++ = pattern;
3590                         *ddst++ = pattern;
3591                         *ddst++ = pattern;
3592                         *ddst++ = pattern;
3593                 }
3594         }
3595         __unreachable_ok_pop
3596 #endif
3597 }
3598
3599 static int
3600 c_decompress_page(char *dst, volatile c_slot_mapping_t slot_ptr, int flags, int *zeroslot)
3601 {
3602         c_slot_t        cs;
3603         c_segment_t     c_seg;
3604         uint32_t        c_segno;
3605         int             c_indx;
3606         int             c_rounded_size;
3607         uint32_t        c_size;
3608         int             retval = 0;
3609         boolean_t       need_unlock = TRUE;
3610         boolean_t       consider_defragmenting = FALSE;
3611         boolean_t       kdp_mode = FALSE;
3612
3613         if (__improbable(flags & C_KDP)) {
3614                 if (not_in_kdp) {
3615                         panic("C_KDP passed to decompress page from outside of debugger context");
3616                 }
3617
3618                 assert((flags & C_KEEP) == C_KEEP);
3619                 assert((flags & C_DONT_BLOCK) == C_DONT_BLOCK);
3620
3621                 if ((flags & (C_DONT_BLOCK | C_KEEP)) != (C_DONT_BLOCK | C_KEEP)) {
3622                         return -2;
3623                 }
3624
3625                 kdp_mode = TRUE;
3626                 *zeroslot = 0;
3627         }
3628
3629 ReTry:
3630         if (__probable(!kdp_mode)) {
3631                 PAGE_REPLACEMENT_DISALLOWED(TRUE);
3632         } else {
3633                 if (kdp_lck_rw_lock_is_acquired_exclusive(&c_master_lock)) {
3634                         return -2;
3635                 }
3636         }
3637
3638 #if HIBERNATION
3639         /*
3640          * if hibernation is enabled, it indicates (via a call
3641          * to 'vm_decompressor_lock' that no further
3642          * decompressions are allowed once it reaches
3643          * the point of flushing all of the currently dirty
3644          * anonymous memory through the compressor and out
3645          * to disk... in this state we allow freeing of compressed
3646          * pages and must honor the C_DONT_BLOCK case
3647          */
3648         if (__improbable(dst && decompressions_blocked == TRUE)) {
3649                 if (flags & C_DONT_BLOCK) {
3650                         if (__probable(!kdp_mode)) {
3651                                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
3652                         }
3653
3654                         *zeroslot = 0;
3655                         return -2;
3656                 }
3657                 /*
3658                  * it's safe to atomically assert and block behind the
3659                  * lock held in shared mode because "decompressions_blocked" is
3660                  * only set and cleared and the thread_wakeup done when the lock
3661                  * is held exclusively
3662                  */
3663                 assert_wait((event_t)&decompressions_blocked, THREAD_UNINT);
3664
3665                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
3666
3667                 thread_block(THREAD_CONTINUE_NULL);
3668
3669                 goto ReTry;
3670         }
3671 #endif
3672         /* s_cseg is actually "segno+1" */
3673         c_segno = slot_ptr->s_cseg - 1;
3674
3675         if (__improbable(c_segno >= c_segments_available)) {
3676                 panic("c_decompress_page: c_segno %d >= c_segments_available %d, slot_ptr(%p), slot_data(%x)",
3677                     c_segno, c_segments_available, slot_ptr, *(int *)((void *)slot_ptr));
3678         }
3679
3680         if (__improbable(c_segments[c_segno].c_segno < c_segments_available)) {
3681                 panic("c_decompress_page: c_segno %d is free, slot_ptr(%p), slot_data(%x)",
3682                     c_segno, slot_ptr, *(int *)((void *)slot_ptr));
3683         }
3684
3685         c_seg = c_segments[c_segno].c_seg;
3686
3687         if (__probable(!kdp_mode)) {
3688                 lck_mtx_lock_spin_always(&c_seg->c_lock);
3689         } else {
3690                 if (kdp_lck_mtx_lock_spin_is_acquired(&c_seg->c_lock)) {
3691                         return -2;
3692                 }
3693         }
3694
3695         assert(c_seg->c_state != C_IS_EMPTY && c_seg->c_state != C_IS_FREE);
3696
3697         if (dst == NULL && c_seg->c_busy_swapping) {
3698                 assert(c_seg->c_busy);
3699
3700                 goto bypass_busy_check;
3701         }
3702         if (flags & C_DONT_BLOCK) {
3703                 if (c_seg->c_busy || (C_SEG_IS_ONDISK(c_seg) && dst)) {
3704                         *zeroslot = 0;
3705
3706                         retval = -2;
3707                         goto done;
3708                 }
3709         }
3710         if (c_seg->c_busy) {
3711                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
3712
3713                 c_seg_wait_on_busy(c_seg);
3714
3715                 goto ReTry;
3716         }
3717 bypass_busy_check:
3718
3719         c_indx = slot_ptr->s_cindx;
3720
3721         if (__improbable(c_indx >= c_seg->c_nextslot)) {
3722                 panic("c_decompress_page: c_indx %d >= c_nextslot %d, c_seg(%p), slot_ptr(%p), slot_data(%x)",
3723                     c_indx, c_seg->c_nextslot, c_seg, slot_ptr, *(int *)((void *)slot_ptr));
3724         }
3725
3726         cs = C_SEG_SLOT_FROM_INDEX(c_seg, c_indx);
3727
3728         c_size = UNPACK_C_SIZE(cs);
3729
3730         if (__improbable(c_size == 0)) {
3731                 panic("c_decompress_page: c_size == 0, c_seg(%p), slot_ptr(%p), slot_data(%x)",
3732                     c_seg, slot_ptr, *(int *)((void *)slot_ptr));
3733         }
3734
3735         c_rounded_size = (c_size + C_SEG_OFFSET_ALIGNMENT_MASK) & ~C_SEG_OFFSET_ALIGNMENT_MASK;
3736
3737         if (dst) {
3738                 uint32_t        age_of_cseg;
3739                 clock_sec_t     cur_ts_sec;
3740                 clock_nsec_t    cur_ts_nsec;
3741
3742                 if (C_SEG_IS_ONDISK(c_seg)) {
3743                         assert(kdp_mode == FALSE);
3744                         retval = c_seg_swapin(c_seg, FALSE, TRUE);
3745                         assert(retval == 0);
3746
3747                         retval = 1;
3748                 }
3749                 if (c_seg->c_state == C_ON_BAD_Q) {
3750                         assert(c_seg->c_store.c_buffer == NULL);
3751                         *zeroslot = 0;
3752
3753                         retval = -1;
3754                         goto done;
3755                 }
3756
3757 #if POPCOUNT_THE_COMPRESSED_DATA
3758                 unsigned csvpop;
3759                 uintptr_t csvaddr = (uintptr_t) &c_seg->c_store.c_buffer[cs->c_offset];
3760                 if (cs->c_pop_cdata != (csvpop = vmc_pop(csvaddr, c_size))) {
3761                         panic("Compressed data popcount doesn't match original, bit distance: %d %p (phys: %p) %p %p 0x%llx 0x%x 0x%x 0x%x", (csvpop - cs->c_pop_cdata), (void *)csvaddr, (void *) kvtophys(csvaddr), c_seg, cs, cs->c_offset, c_size, csvpop, cs->c_pop_cdata);
3762                 }
3763 #endif
3764
3765 #if CHECKSUM_THE_COMPRESSED_DATA
3766                 unsigned csvhash;
3767                 if (cs->c_hash_compressed_data != (csvhash = vmc_hash((char *)&c_seg->c_store.c_buffer[cs->c_offset], c_size))) {
3768                         panic("Compressed data doesn't match original %p %p %u %u %u", c_seg, cs, c_size, cs->c_hash_compressed_data, csvhash);
3769                 }
3770 #endif
3771                 if (c_rounded_size == PAGE_SIZE) {
3772                         /*
3773                          * page wasn't compressible... just copy it out
3774                          */
3775                         memcpy(dst, &c_seg->c_store.c_buffer[cs->c_offset], PAGE_SIZE);
3776                 } else if (c_size == 4) {
3777                         int32_t         data;
3778                         int32_t         *dptr;
3779
3780                         /*
3781                          * page was populated with a single value
3782                          * that didn't fit into our fast hash
3783                          * so we packed it in as a single non-compressed value
3784                          * that we need to populate the page with
3785                          */
3786                         dptr = (int32_t *)(uintptr_t)dst;
3787                         data = *(int32_t *)(&c_seg->c_store.c_buffer[cs->c_offset]);
3788                         sv_decompress(dptr, data);
3789                 } else {
3790                         uint32_t        my_cpu_no;
3791                         char            *scratch_buf;
3792
3793                         if (__probable(!kdp_mode)) {
3794                                 /*
3795                                  * we're behind the c_seg lock held in spin mode
3796                                  * which means pre-emption is disabled... therefore
3797                                  * the following sequence is atomic and safe
3798                                  */
3799                                 my_cpu_no = cpu_number();
3800
3801                                 assert(my_cpu_no < compressor_cpus);
3802
3803                                 scratch_buf = &compressor_scratch_bufs[my_cpu_no * vm_compressor_get_decode_scratch_size()];
3804                         } else {
3805                                 scratch_buf = kdp_compressor_scratch_buf;
3806                         }
3807
3808                         if (vm_compressor_algorithm() != VM_COMPRESSOR_DEFAULT_CODEC) {
3809 #if defined(__arm__) || defined(__arm64__)
3810                                 uint16_t c_codec = cs->c_codec;
3811                                 metadecompressor((const uint8_t *) &c_seg->c_store.c_buffer[cs->c_offset],
3812                                     (uint8_t *)dst, c_size, c_codec, (void *)scratch_buf);
3813 #endif
3814                         } else {
3815 #if defined(__arm64__)
3816                                 __unreachable_ok_push
3817                                 if (PAGE_SIZE == 4096) {
3818                                         WKdm_decompress_4k((WK_word *)(uintptr_t)&c_seg->c_store.c_buffer[cs->c_offset],
3819                                             (WK_word *)(uintptr_t)dst, (WK_word *)(uintptr_t)scratch_buf, c_size);
3820                                 } else {
3821                                         WKdm_decompress_16k((WK_word *)(uintptr_t)&c_seg->c_store.c_buffer[cs->c_offset],
3822                                             (WK_word *)(uintptr_t)dst, (WK_word *)(uintptr_t)scratch_buf, c_size);
3823                                 }
3824                                 __unreachable_ok_pop
3825 #else
3826                                 WKdm_decompress_new((WK_word *)(uintptr_t)&c_seg->c_store.c_buffer[cs->c_offset],
3827                                     (WK_word *)(uintptr_t)dst, (WK_word *)(uintptr_t)scratch_buf, c_size);
3828 #endif
3829                         }
3830                 }
3831
3832 #if CHECKSUM_THE_DATA
3833                 if (cs->c_hash_data != vmc_hash(dst, PAGE_SIZE)) {
3834 #if     defined(__arm__) || defined(__arm64__)
3835                         int32_t *dinput = &c_seg->c_store.c_buffer[cs->c_offset];
3836                         panic("decompressed data doesn't match original cs: %p, hash: 0x%x, offset: %d, c_size: %d, c_rounded_size: %d, codec: %d, header: 0x%x 0x%x 0x%x", cs, cs->c_hash_data, cs->c_offset, c_size, c_rounded_size, cs->c_codec, *dinput, *(dinput + 1), *(dinput + 2));
3837 #else
3838                         panic("decompressed data doesn't match original cs: %p, hash: %d, offset: 0x%x, c_size: %d", cs, cs->c_hash_data, cs->c_offset, c_size);
3839 #endif
3840                 }
3841 #endif
3842                 if (c_seg->c_swappedin_ts == 0 && !kdp_mode) {
3843                         clock_get_system_nanotime(&cur_ts_sec, &cur_ts_nsec);
3844
3845                         age_of_cseg = (uint32_t)cur_ts_sec - c_seg->c_creation_ts;
3846                         if (age_of_cseg < DECOMPRESSION_SAMPLE_MAX_AGE) {
3847                                 OSAddAtomic(1, &age_of_decompressions_during_sample_period[age_of_cseg]);
3848                         } else {
3849                                 OSAddAtomic(1, &overage_decompressions_during_sample_period);
3850                         }
3851
3852                         OSAddAtomic(1, &sample_period_decompression_count);
3853                 }
3854         }
3855         if (flags & C_KEEP) {
3856                 *zeroslot = 0;
3857                 goto done;
3858         }
3859         assert(kdp_mode == FALSE);
3860
3861         c_seg->c_bytes_unused += c_rounded_size;
3862         c_seg->c_bytes_used -= c_rounded_size;
3863
3864         assert(c_seg->c_slots_used);
3865         c_seg->c_slots_used--;
3866
3867         PACK_C_SIZE(cs, 0);
3868
3869         if (c_indx < c_seg->c_firstemptyslot) {
3870                 c_seg->c_firstemptyslot = c_indx;
3871         }
3872
3873         OSAddAtomic(-1, &c_segment_pages_compressed);
3874
3875         if (c_seg->c_state != C_ON_BAD_Q && !(C_SEG_IS_ONDISK(c_seg))) {
3876                 /*
3877                  * C_SEG_IS_ONDISK == TRUE can occur when we're doing a
3878                  * free of a compressed page (i.e. dst == NULL)
3879                  */
3880                 OSAddAtomic64(-c_rounded_size, &compressor_bytes_used);
3881         }
3882         if (c_seg->c_busy_swapping) {
3883                 /*
3884                  * bypass case for c_busy_swapping...
3885                  * let the swapin/swapout paths deal with putting
3886                  * the c_seg on the minor compaction queue if needed
3887                  */
3888                 assert(c_seg->c_busy);
3889                 goto done;
3890         }
3891         assert(!c_seg->c_busy);
3892
3893         if (c_seg->c_state != C_IS_FILLING) {
3894                 if (c_seg->c_bytes_used == 0) {
3895                         if (!(C_SEG_IS_ONDISK(c_seg))) {
3896                                 int     pages_populated;
3897
3898                                 pages_populated = (round_page_32(C_SEG_OFFSET_TO_BYTES(c_seg->c_populated_offset))) / PAGE_SIZE;
3899                                 c_seg->c_populated_offset = C_SEG_BYTES_TO_OFFSET(0);
3900
3901                                 if (pages_populated) {
3902                                         assert(c_seg->c_state != C_ON_BAD_Q);
3903                                         assert(c_seg->c_store.c_buffer != NULL);
3904
3905                                         C_SEG_BUSY(c_seg);
3906                                         lck_mtx_unlock_always(&c_seg->c_lock);
3907
3908                                         kernel_memory_depopulate(compressor_map, (vm_offset_t) c_seg->c_store.c_buffer, pages_populated * PAGE_SIZE, KMA_COMPRESSOR);
3909
3910                                         lck_mtx_lock_spin_always(&c_seg->c_lock);
3911                                         C_SEG_WAKEUP_DONE(c_seg);
3912                                 }
3913                                 if (!c_seg->c_on_minorcompact_q && c_seg->c_state != C_ON_SWAPOUT_Q && c_seg->c_state != C_ON_SWAPIO_Q) {
3914                                         c_seg_need_delayed_compaction(c_seg, FALSE);
3915                                 }
3916                         } else {
3917                                 if (c_seg->c_state != C_ON_SWAPPEDOUTSPARSE_Q) {
3918                                         c_seg_move_to_sparse_list(c_seg);
3919                                         consider_defragmenting = TRUE;
3920                                 }
3921                         }
3922                 } else if (c_seg->c_on_minorcompact_q) {
3923                         assert(c_seg->c_state != C_ON_BAD_Q);
3924                         assert(!C_SEG_IS_ON_DISK_OR_SOQ(c_seg));
3925
3926                         if (C_SEG_SHOULD_MINORCOMPACT_NOW(c_seg)) {
3927                                 c_seg_try_minor_compaction_and_unlock(c_seg);
3928                                 need_unlock = FALSE;
3929                         }
3930                 } else if (!(C_SEG_IS_ONDISK(c_seg))) {
3931                         if (c_seg->c_state != C_ON_BAD_Q && c_seg->c_state != C_ON_SWAPOUT_Q && c_seg->c_state != C_ON_SWAPIO_Q &&
3932                             C_SEG_UNUSED_BYTES(c_seg) >= PAGE_SIZE) {
3933                                 c_seg_need_delayed_compaction(c_seg, FALSE);
3934                         }
3935                 } else if (c_seg->c_state != C_ON_SWAPPEDOUTSPARSE_Q && C_SEG_ONDISK_IS_SPARSE(c_seg)) {
3936                         c_seg_move_to_sparse_list(c_seg);
3937                         consider_defragmenting = TRUE;
3938                 }
3939         }
3940 done:
3941         if (__improbable(kdp_mode)) {
3942                 return retval;
3943         }
3944
3945         if (need_unlock == TRUE) {
3946                 lck_mtx_unlock_always(&c_seg->c_lock);
3947         }
3948
3949         PAGE_REPLACEMENT_DISALLOWED(FALSE);
3950
3951         if (consider_defragmenting == TRUE) {
3952                 vm_swap_consider_defragmenting(VM_SWAP_FLAGS_NONE);
3953         }
3954
3955 #if CONFIG_EMBEDDED
3956         if ((c_minor_count && COMPRESSOR_NEEDS_TO_MINOR_COMPACT()) || vm_compressor_needs_to_major_compact()) {
3957                 vm_wake_compactor_swapper();
3958         }
3959 #endif
3960
3961         return retval;
3962 }
3963
3964
3965 int
3966 vm_compressor_get(ppnum_t pn, int *slot, int flags)
3967 {
3968         c_slot_mapping_t  slot_ptr;
3969         char    *dst;
3970         int     zeroslot = 1;
3971         int     retval;
3972
3973         dst = pmap_map_compressor_page(pn);
3974         slot_ptr = (c_slot_mapping_t)slot;
3975
3976         assert(dst != NULL);
3977
3978         if (slot_ptr->s_cseg == C_SV_CSEG_ID) {
3979                 int32_t         data;
3980                 int32_t         *dptr;
3981
3982                 /*
3983                  * page was populated with a single value
3984                  * that found a home in our hash table
3985                  * grab that value from the hash and populate the page
3986                  * that we need to populate the page with
3987                  */
3988                 dptr = (int32_t *)(uintptr_t)dst;
3989                 data = c_segment_sv_hash_table[slot_ptr->s_cindx].he_data;
3990 #if __x86_64__
3991                 memset_word(dptr, data, PAGE_SIZE / sizeof(int32_t));
3992 #else
3993                 {
3994                         int             i;
3995
3996                         for (i = 0; i < (int)(PAGE_SIZE / sizeof(int32_t)); i++) {
3997                                 *dptr++ = data;
3998                         }
3999                 }
4000 #endif
4001                 if (!(flags & C_KEEP)) {
4002                         c_segment_sv_hash_drop_ref(slot_ptr->s_cindx);
4003
4004                         OSAddAtomic(-1, &c_segment_pages_compressed);
4005                         *slot = 0;
4006                 }
4007                 if (data) {
4008                         OSAddAtomic(1, &c_segment_svp_nonzero_decompressions);
4009                 } else {
4010                         OSAddAtomic(1, &c_segment_svp_zero_decompressions);
4011                 }
4012
4013                 pmap_unmap_compressor_page(pn, dst);
4014                 return 0;
4015         }
4016
4017         retval = c_decompress_page(dst, slot_ptr, flags, &zeroslot);
4018
4019         /*
4020          * zeroslot will be set to 0 by c_decompress_page if (flags & C_KEEP)
4021          * or (flags & C_DONT_BLOCK) and we found 'c_busy' or 'C_SEG_IS_ONDISK' to be TRUE
4022          */
4023         if (zeroslot) {
4024                 *slot = 0;
4025         }
4026
4027         pmap_unmap_compressor_page(pn, dst);
4028
4029         /*
4030          * returns 0 if we successfully decompressed a page from a segment already in memory
4031          * returns 1 if we had to first swap in the segment, before successfully decompressing the page
4032          * returns -1 if we encountered an error swapping in the segment - decompression failed
4033          * returns -2 if (flags & C_DONT_BLOCK) and we found 'c_busy' or 'C_SEG_IS_ONDISK' to be true
4034          */
4035         return retval;
4036 }
4037
4038
4039 int
4040 vm_compressor_free(int *slot, int flags)
4041 {
4042         c_slot_mapping_t  slot_ptr;
4043         int     zeroslot = 1;
4044         int     retval;
4045
4046         assert(flags == 0 || flags == C_DONT_BLOCK);
4047
4048         slot_ptr = (c_slot_mapping_t)slot;
4049
4050         if (slot_ptr->s_cseg == C_SV_CSEG_ID) {
4051                 c_segment_sv_hash_drop_ref(slot_ptr->s_cindx);
4052                 OSAddAtomic(-1, &c_segment_pages_compressed);
4053
4054                 *slot = 0;
4055                 return 0;
4056         }
4057         retval = c_decompress_page(NULL, slot_ptr, flags, &zeroslot);
4058         /*
4059          * returns 0 if we successfully freed the specified compressed page
4060          * returns -2 if (flags & C_DONT_BLOCK) and we found 'c_busy' set
4061          */
4062
4063         if (retval == 0) {
4064                 *slot = 0;
4065         } else {
4066                 assert(retval == -2);
4067         }
4068
4069         return retval;
4070 }
4071
4072
4073 int
4074 vm_compressor_put(ppnum_t pn, int *slot, void  **current_chead, char *scratch_buf)
4075 {
4076         char    *src;
4077         int     retval;
4078
4079         src = pmap_map_compressor_page(pn);
4080         assert(src != NULL);
4081
4082         retval = c_compress_page(src, (c_slot_mapping_t)slot, (c_segment_t *)current_chead, scratch_buf);
4083         pmap_unmap_compressor_page(pn, src);
4084
4085         return retval;
4086 }
4087
4088 void
4089 vm_compressor_transfer(
4090         int     *dst_slot_p,
4091         int     *src_slot_p)
4092 {
4093         c_slot_mapping_t        dst_slot, src_slot;
4094         c_segment_t             c_seg;
4095         int                     c_indx;
4096         c_slot_t                cs;
4097
4098         src_slot = (c_slot_mapping_t) src_slot_p;
4099
4100         if (src_slot->s_cseg == C_SV_CSEG_ID) {
4101                 *dst_slot_p = *src_slot_p;
4102                 *src_slot_p = 0;
4103                 return;
4104         }
4105         dst_slot = (c_slot_mapping_t) dst_slot_p;
4106 Retry:
4107         PAGE_REPLACEMENT_DISALLOWED(TRUE);
4108         /* get segment for src_slot */
4109         c_seg = c_segments[src_slot->s_cseg - 1].c_seg;
4110         /* lock segment */
4111         lck_mtx_lock_spin_always(&c_seg->c_lock);
4112         /* wait if it's busy */
4113         if (c_seg->c_busy && !c_seg->c_busy_swapping) {
4114                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
4115                 c_seg_wait_on_busy(c_seg);
4116                 goto Retry;
4117         }
4118         /* find the c_slot */
4119         c_indx = src_slot->s_cindx;
4120         cs = C_SEG_SLOT_FROM_INDEX(c_seg, c_indx);
4121         /* point the c_slot back to dst_slot instead of src_slot */
4122         cs->c_packed_ptr = C_SLOT_PACK_PTR(dst_slot);
4123         /* transfer */
4124         *dst_slot_p = *src_slot_p;
4125         *src_slot_p = 0;
4126         lck_mtx_unlock_always(&c_seg->c_lock);
4127         PAGE_REPLACEMENT_DISALLOWED(FALSE);
4128 }
4129
4130 #if CONFIG_FREEZE
4131
4132 int     freezer_finished_filling = 0;
4133
4134 void
4135 vm_compressor_finished_filling(
4136         void    **current_chead)
4137 {
4138         c_segment_t     c_seg;
4139
4140         if ((c_seg = *(c_segment_t *)current_chead) == NULL) {
4141                 return;
4142         }
4143
4144         assert(c_seg->c_state == C_IS_FILLING);
4145
4146         lck_mtx_lock_spin_always(&c_seg->c_lock);
4147
4148         c_current_seg_filled(c_seg, (c_segment_t *)current_chead);
4149
4150         lck_mtx_unlock_always(&c_seg->c_lock);
4151
4152         freezer_finished_filling++;
4153 }
4154
4155
4156 /*
4157  * This routine is used to transfer the compressed chunks from
4158  * the c_seg/cindx pointed to by slot_p into a new c_seg headed
4159  * by the current_chead and a new cindx within that c_seg.
4160  *
4161  * Currently, this routine is only used by the "freezer backed by
4162  * compressor with swap" mode to create a series of c_segs that
4163  * only contain compressed data belonging to one task. So, we
4164  * move a task's previously compressed data into a set of new
4165  * c_segs which will also hold the task's yet to be compressed data.
4166  */
4167
4168 kern_return_t
4169 vm_compressor_relocate(
4170         void            **current_chead,
4171         int             *slot_p)
4172 {
4173         c_slot_mapping_t        slot_ptr;
4174         c_slot_mapping_t        src_slot;
4175         uint32_t                c_rounded_size;
4176         uint32_t                c_size;
4177         uint16_t                dst_slot;
4178         c_slot_t                c_dst;
4179         c_slot_t                c_src;
4180         int                     c_indx;
4181         c_segment_t             c_seg_dst = NULL;
4182         c_segment_t             c_seg_src = NULL;
4183         kern_return_t           kr = KERN_SUCCESS;
4184
4185
4186         src_slot = (c_slot_mapping_t) slot_p;
4187
4188         if (src_slot->s_cseg == C_SV_CSEG_ID) {
4189                 /*
4190                  * no need to relocate... this is a page full of a single
4191                  * value which is hashed to a single entry not contained
4192                  * in a c_segment_t
4193                  */
4194                 return kr;
4195         }
4196
4197 Relookup_dst:
4198         c_seg_dst = c_seg_allocate((c_segment_t *)current_chead);
4199         /*
4200          * returns with c_seg lock held
4201          * and PAGE_REPLACEMENT_DISALLOWED(TRUE)...
4202          * c_nextslot has been allocated and
4203          * c_store.c_buffer populated
4204          */
4205         if (c_seg_dst == NULL) {
4206                 /*
4207                  * Out of compression segments?
4208                  */
4209                 kr = KERN_RESOURCE_SHORTAGE;
4210                 goto out;
4211         }
4212
4213         assert(c_seg_dst->c_busy == 0);
4214
4215         C_SEG_BUSY(c_seg_dst);
4216
4217         dst_slot = c_seg_dst->c_nextslot;
4218
4219         lck_mtx_unlock_always(&c_seg_dst->c_lock);
4220
4221 Relookup_src:
4222         c_seg_src = c_segments[src_slot->s_cseg - 1].c_seg;
4223
4224         assert(c_seg_dst != c_seg_src);
4225
4226         lck_mtx_lock_spin_always(&c_seg_src->c_lock);
4227
4228         if (C_SEG_IS_ONDISK(c_seg_src)) {
4229                 /*
4230                  * A "thaw" can mark a process as eligible for
4231                  * another freeze cycle without bringing any of
4232                  * its swapped out c_segs back from disk (because
4233                  * that is done on-demand).
4234                  *
4235                  * If the src c_seg we find for our pre-compressed
4236                  * data is already on-disk, then we are dealing
4237                  * with an app's data that is already packed and
4238                  * swapped out. Don't do anything.
4239                  */
4240
4241                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
4242
4243                 lck_mtx_unlock_always(&c_seg_src->c_lock);
4244
4245                 c_seg_src = NULL;
4246
4247                 goto out;
4248         }
4249
4250         if (c_seg_src->c_busy) {
4251                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
4252                 c_seg_wait_on_busy(c_seg_src);
4253
4254                 c_seg_src = NULL;
4255
4256                 PAGE_REPLACEMENT_DISALLOWED(TRUE);
4257
4258                 goto Relookup_src;
4259         }
4260
4261         C_SEG_BUSY(c_seg_src);
4262
4263         lck_mtx_unlock_always(&c_seg_src->c_lock);
4264
4265         PAGE_REPLACEMENT_DISALLOWED(FALSE);
4266
4267         /* find the c_slot */
4268         c_indx = src_slot->s_cindx;
4269
4270         c_src = C_SEG_SLOT_FROM_INDEX(c_seg_src, c_indx);
4271
4272         c_size = UNPACK_C_SIZE(c_src);
4273
4274         assert(c_size);
4275
4276         if (c_size > (uint32_t)(C_SEG_BUFSIZE - C_SEG_OFFSET_TO_BYTES((int32_t)c_seg_dst->c_nextoffset))) {
4277                 /*
4278                  * This segment is full. We need a new one.
4279                  */
4280
4281                 PAGE_REPLACEMENT_DISALLOWED(TRUE);
4282
4283                 lck_mtx_lock_spin_always(&c_seg_src->c_lock);
4284                 C_SEG_WAKEUP_DONE(c_seg_src);
4285                 lck_mtx_unlock_always(&c_seg_src->c_lock);
4286
4287                 c_seg_src = NULL;
4288
4289                 lck_mtx_lock_spin_always(&c_seg_dst->c_lock);
4290
4291                 assert(c_seg_dst->c_busy);
4292                 assert(c_seg_dst->c_state == C_IS_FILLING);
4293                 assert(!c_seg_dst->c_on_minorcompact_q);
4294
4295                 c_current_seg_filled(c_seg_dst, (c_segment_t *)current_chead);
4296                 assert(*current_chead == NULL);
4297
4298                 C_SEG_WAKEUP_DONE(c_seg_dst);
4299
4300                 lck_mtx_unlock_always(&c_seg_dst->c_lock);
4301
4302                 c_seg_dst = NULL;
4303
4304                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
4305
4306                 goto Relookup_dst;
4307         }
4308
4309         c_dst = C_SEG_SLOT_FROM_INDEX(c_seg_dst, c_seg_dst->c_nextslot);
4310
4311         memcpy(&c_seg_dst->c_store.c_buffer[c_seg_dst->c_nextoffset], &c_seg_src->c_store.c_buffer[c_src->c_offset], c_size);
4312 //is platform alignment actually necessary since wkdm aligns its output?
4313         c_rounded_size = (c_size + C_SEG_OFFSET_ALIGNMENT_MASK) & ~C_SEG_OFFSET_ALIGNMENT_MASK;
4314
4315         cslot_copy(c_dst, c_src);
4316         c_dst->c_offset = c_seg_dst->c_nextoffset;
4317
4318         if (c_seg_dst->c_firstemptyslot == c_seg_dst->c_nextslot) {
4319                 c_seg_dst->c_firstemptyslot++;
4320         }
4321
4322         c_seg_dst->c_slots_used++;
4323         c_seg_dst->c_nextslot++;
4324         c_seg_dst->c_bytes_used += c_rounded_size;
4325         c_seg_dst->c_nextoffset += C_SEG_BYTES_TO_OFFSET(c_rounded_size);
4326
4327
4328         PACK_C_SIZE(c_src, 0);
4329
4330         c_seg_src->c_bytes_used -= c_rounded_size;
4331         c_seg_src->c_bytes_unused += c_rounded_size;
4332
4333         assert(c_seg_src->c_slots_used);
4334         c_seg_src->c_slots_used--;
4335
4336         if (c_indx < c_seg_src->c_firstemptyslot) {
4337                 c_seg_src->c_firstemptyslot = c_indx;
4338         }
4339
4340         c_dst = C_SEG_SLOT_FROM_INDEX(c_seg_dst, dst_slot);
4341
4342         PAGE_REPLACEMENT_ALLOWED(TRUE);
4343         slot_ptr = (c_slot_mapping_t)C_SLOT_UNPACK_PTR(c_dst);
4344         /* <csegno=0,indx=0> would mean "empty slot", so use csegno+1 */
4345         slot_ptr->s_cseg = c_seg_dst->c_mysegno + 1;
4346         slot_ptr->s_cindx = dst_slot;
4347
4348         PAGE_REPLACEMENT_ALLOWED(FALSE);
4349
4350 out:
4351         if (c_seg_src) {
4352                 lck_mtx_lock_spin_always(&c_seg_src->c_lock);
4353
4354                 C_SEG_WAKEUP_DONE(c_seg_src);
4355
4356                 if (c_seg_src->c_bytes_used == 0 && c_seg_src->c_state != C_IS_FILLING) {
4357                         if (!c_seg_src->c_on_minorcompact_q) {
4358                                 c_seg_need_delayed_compaction(c_seg_src, FALSE);
4359                         }
4360                 }
4361
4362                 lck_mtx_unlock_always(&c_seg_src->c_lock);
4363         }
4364
4365         if (c_seg_dst) {
4366                 PAGE_REPLACEMENT_DISALLOWED(TRUE);
4367
4368                 lck_mtx_lock_spin_always(&c_seg_dst->c_lock);
4369
4370                 if (c_seg_dst->c_nextoffset >= C_SEG_OFF_LIMIT || c_seg_dst->c_nextslot >= C_SLOT_MAX_INDEX) {
4371                         /*
4372                          * Nearing or exceeded maximum slot and offset capacity.
4373                          */
4374                         assert(c_seg_dst->c_busy);
4375                         assert(c_seg_dst->c_state == C_IS_FILLING);
4376                         assert(!c_seg_dst->c_on_minorcompact_q);
4377
4378                         c_current_seg_filled(c_seg_dst, (c_segment_t *)current_chead);
4379                         assert(*current_chead == NULL);
4380                 }
4381
4382                 C_SEG_WAKEUP_DONE(c_seg_dst);
4383
4384                 lck_mtx_unlock_always(&c_seg_dst->c_lock);
4385
4386                 c_seg_dst = NULL;
4387
4388                 PAGE_REPLACEMENT_DISALLOWED(FALSE);
4389         }
4390
4391         return kr;
4392 }
4393 #endif /* CONFIG_FREEZE */