osfmk/vm/vm_compressor_algorithms.c

   1 /*
   2  * Copyright (c) 2010-2016 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 /* This module implements a hybrid/adaptive compression scheme, using WKdm where
  29  * profitable and, currently, an LZ4 variant elsewhere.
  30  * (Created 2016, Derek Kumar)
  31  */
  32 #include "lz4.h"
  33 #include "WKdm_new.h"
  34 #include <vm/vm_compressor_algorithms.h>
  35 #include <vm/vm_compressor.h>
  36
  37 #define MZV_MAGIC (17185)
  38 #define LZ4_SCRATCH_ALIGN (64)
  39 #define WKC_SCRATCH_ALIGN (64)
  40
  41 #define LZ4_SCRATCH_ALIGN (64)
  42 #define WKC_SCRATCH_ALIGN (64)
  43
  44 #define memcpy_T_NT memcpy
  45 #define memcpy_NT_T memcpy
  46
  47 typedef union {
  48         uint8_t lz4state[lz4_encode_scratch_size]__attribute((aligned(LZ4_SCRATCH_ALIGN)));
  49         uint8_t wkscratch[0] __attribute((aligned(WKC_SCRATCH_ALIGN))); // TODO
  50 } compressor_encode_scratch_t;
  51
  52 typedef union {
  53         uint8_t lz4decodestate[lz4_encode_scratch_size]__attribute((aligned(64)));
  54         uint8_t wkdecompscratch[0] __attribute((aligned(64)));
  55 } compressor_decode_scratch_t;
  56
  57 typedef struct {
  58         uint16_t lz4_selection_run;
  59         uint16_t lz4_run_length;
  60         uint16_t lz4_preselects;
  61         uint32_t lz4_total_preselects;
  62         uint16_t lz4_failure_skips;
  63         uint32_t lz4_total_failure_skips;
  64         uint16_t lz4_failure_run_length;
  65         uint16_t lz4_total_unprofitables;
  66         uint32_t lz4_total_negatives;
  67         uint32_t lz4_total_failures;
  68 } compressor_state_t;
  69
  70 compressor_tuneables_t vmctune = {
  71         .lz4_threshold = 2048,
  72         .wkdm_reeval_threshold = 1536,
  73         .lz4_max_failure_skips = 0,
  74         .lz4_max_failure_run_length = ~0U,
  75         .lz4_max_preselects = 0,
  76         .lz4_run_preselection_threshold = ~0U,
  77         .lz4_run_continue_bytes = 0,
  78         .lz4_profitable_bytes = 0,
  79 };
  80
  81 compressor_state_t vmcstate = {
  82         .lz4_selection_run = 0,
  83         .lz4_run_length = 0,
  84         .lz4_preselects = 0,
  85         .lz4_total_preselects = 0,
  86         .lz4_failure_skips = 0,
  87         .lz4_total_failure_skips = 0,
  88         .lz4_failure_run_length = 0,
  89         .lz4_total_unprofitables = 0,
  90         .lz4_total_negatives = 0,
  91 };
  92
  93 compressor_stats_t compressor_stats;
  94
  95 enum compressor_preselect_t {
  96         CPRESELLZ4 = 0,
  97         CSKIPLZ4 = 1,
  98         CPRESELWK = 2,
  99 };
 100
 101 vm_compressor_mode_t vm_compressor_current_codec = VM_COMPRESSOR_DEFAULT_CODEC;
 102
 103 boolean_t verbose = FALSE;
 104
 105 #if DEVELOPMENT || DEBUG
 106 #define VERBOSE(x...)                                                   \
 107         do {                                                            \
 108                 if (verbose)                                            \
 109                         printf(x);                                      \
 110         } while(0)
 111 #define VM_COMPRESSOR_STAT(x...)                                        \
 112         do {                                                            \
 113                 (x);                                                    \
 114         } while(0)
 115 //TODO make atomic where needed, decompression paths
 116 #define VM_DECOMPRESSOR_STAT(x...)                                      \
 117         do {                                                            \
 118                 (x);                                                    \
 119         } while(0)
 120 #else
 121 #define VERBOSE(x...)                                                   \
 122         do {                                                            \
 123         }while (0)
 124 #define VM_COMPRESSOR_STAT(x...)                                        \
 125         do {                                                            \
 126         }while (0)
 127 #define VM_DECOMPRESSOR_STAT(x...)                                      \
 128         do {                                                            \
 129         }while (0)
 130 #endif
 131
 132 static inline enum compressor_preselect_t compressor_preselect(void) {
 133         if (vmcstate.lz4_failure_skips >= vmctune.lz4_max_failure_skips) {
 134                 vmcstate.lz4_failure_skips = 0;
 135                 vmcstate.lz4_failure_run_length = 0;
 136         }
 137
 138         if (vmcstate.lz4_failure_run_length >= vmctune.lz4_max_failure_run_length) {
 139                 vmcstate.lz4_failure_skips++;
 140                 vmcstate.lz4_total_failure_skips++;
 141                 return CSKIPLZ4;
 142         }
 143
 144         if (vmcstate.lz4_preselects >= vmctune.lz4_max_preselects) {
 145                 vmcstate.lz4_preselects = 0;
 146                 return CPRESELWK;
 147         }
 148
 149         if (vmcstate.lz4_run_length >= vmctune.lz4_run_preselection_threshold) {
 150                 vmcstate.lz4_preselects++;
 151                 vmcstate.lz4_total_preselects++;
 152                 return CPRESELLZ4;
 153         }
 154         return CPRESELWK;
 155 }
 156
 157 static inline void compressor_selector_update(int lz4sz, int didwk, int wksz) {
 158         VM_COMPRESSOR_STAT(compressor_stats.lz4_compressions++);
 159
 160         if (lz4sz == 0) {
 161                 VM_COMPRESSOR_STAT(compressor_stats.lz4_compressed_bytes+=PAGE_SIZE);
 162                 VM_COMPRESSOR_STAT(compressor_stats.lz4_compression_failures++);
 163                 vmcstate.lz4_failure_run_length++;
 164                 VM_COMPRESSOR_STAT(vmcstate.lz4_total_failures++);
 165                 vmcstate.lz4_run_length = 0;
 166         } else {
 167                 vmcstate.lz4_failure_run_length = 0;
 168
 169                 VM_COMPRESSOR_STAT(compressor_stats.lz4_compressed_bytes+=lz4sz);
 170
 171                 if (lz4sz <= vmctune.wkdm_reeval_threshold) {
 172                         vmcstate.lz4_run_length = 0;
 173                 } else {
 174                         if (!didwk) {
 175                                 vmcstate.lz4_run_length++;
 176                         }
 177                 }
 178
 179                 if (didwk) {
 180                         if (__probable(wksz > lz4sz)) {
 181                                 uint32_t lz4delta = wksz - lz4sz;
 182                                 VM_COMPRESSOR_STAT(compressor_stats.lz4_wk_compression_delta+=lz4delta);
 183                                 if (lz4delta >= vmctune.lz4_run_continue_bytes) {
 184                                         vmcstate.lz4_run_length++;
 185                                 } else if (lz4delta <= vmctune.lz4_profitable_bytes) {
 186                                         vmcstate.lz4_failure_run_length++;
 187                                         VM_COMPRESSOR_STAT(vmcstate.lz4_total_unprofitables++);
 188                                         vmcstate.lz4_run_length = 0;
 189                                 } else {
 190                                         vmcstate.lz4_run_length = 0;
 191                                 }
 192                         } else {
 193                                 VM_COMPRESSOR_STAT(compressor_stats.lz4_wk_compression_negative_delta+=(lz4sz-wksz));
 194                                 vmcstate.lz4_failure_run_length++;
 195                                 VM_COMPRESSOR_STAT(vmcstate.lz4_total_negatives++);
 196                                 vmcstate.lz4_run_length = 0;
 197                         }
 198                 }
 199         }
 200 }
 201
 202 //todo fix clang diagnostic
 203 #pragma clang diagnostic push
 204 #pragma clang diagnostic ignored "-Wincompatible-pointer-types"
 205
 206 static inline void WKdmD(WK_word* src_buf, WK_word* dest_buf, WK_word* scratch, unsigned int bytes) {
 207 #if DEVELOPMENT || DEBUG
 208         uint32_t *inw = (uint32_t *) src_buf;
 209         if (*inw != MZV_MAGIC) {
 210                 if ((*inw | *(inw+1) | *(inw+2)) & 0xFFFF0000) {
 211                         panic("WKdmDecompress: invalid header 0x%x 0x%x 0x%x\n", *inw, *(inw +1), *(inw+2));
 212                 }
 213         }
 214 #endif /* DEVELOPMENT || DEBUG */
 215         WKdm_decompress_new(src_buf, dest_buf, scratch, bytes);
 216 }
 217
 218 static inline int WKdmC(WK_word* src_buf, WK_word* dest_buf, WK_word* scratch, unsigned int limit) {
 219         return WKdm_compress_new(src_buf, dest_buf, scratch, limit);
 220 }
 221
 222
 223 int metacompressor(const uint8_t *in, uint8_t *cdst, int32_t outbufsz, uint16_t *codec, void *cscratchin) {
 224         int sz = -1;
 225         int dowk = FALSE, dolz4 = FALSE, skiplz4 = FALSE;
 226         int insize = PAGE_SIZE;
 227         compressor_encode_scratch_t *cscratch = cscratchin;
 228
 229         if (vm_compressor_current_codec == CMODE_WK) {
 230                 dowk = TRUE;
 231         } else if (vm_compressor_current_codec == CMODE_LZ4) {
 232                 dolz4 = TRUE;
 233         } else if (vm_compressor_current_codec == CMODE_HYB) {
 234                 enum compressor_preselect_t presel = compressor_preselect();
 235                 if (presel == CPRESELLZ4) {
 236                         dolz4 = TRUE;
 237                         goto lz4compress;
 238                 } else if (presel == CSKIPLZ4) {
 239                         dowk = TRUE;
 240                         skiplz4 = TRUE;
 241                 } else {
 242                         assert(presel == CPRESELWK);
 243                         dowk = TRUE;
 244                 }
 245         }
 246
 247         if (dowk) {
 248                 *codec = CCWK;
 249                 sz = WKdmC(in, cdst, &cscratch->wkscratch[0], outbufsz);
 250                 VM_COMPRESSOR_STAT(compressor_stats.wk_compressions++);
 251
 252                 VERBOSE("WKDm Compress: %d\n", sz);
 253                 if (sz == -1) {
 254                         VM_COMPRESSOR_STAT(compressor_stats.wk_compressed_bytes_total+=PAGE_SIZE);
 255                         VM_COMPRESSOR_STAT(compressor_stats.wk_compression_failures++);
 256
 257                         if (vm_compressor_current_codec == CMODE_HYB) {
 258                                 goto lz4eval;
 259                         }
 260                         goto cexit;
 261                 } else if (sz == 0) {
 262                         VM_COMPRESSOR_STAT(compressor_stats.wk_sv_compressions++);
 263                         VM_COMPRESSOR_STAT(compressor_stats.wk_compressed_bytes_total+=8);
 264                 } else {
 265                         VM_COMPRESSOR_STAT(compressor_stats.wk_compressed_bytes_total+=sz);
 266                 }
 267         }
 268 lz4eval:
 269         if (vm_compressor_current_codec == CMODE_HYB) {
 270                 if (((sz == -1) || (sz >= vmctune.lz4_threshold)) && (skiplz4 == FALSE)) {
 271                         dolz4 = TRUE;
 272                 } else {
 273                         __unused int wkc = (sz == -1) ? PAGE_SIZE : sz;
 274                         VM_COMPRESSOR_STAT(compressor_stats.wk_compressions_exclusive++);
 275                         VM_COMPRESSOR_STAT(compressor_stats.wk_compressed_bytes_exclusive+=wkc);
 276                         goto cexit;
 277                 }
 278         }
 279
 280 lz4compress:
 281
 282         if (dolz4) {
 283                 if (sz == -1) {
 284                         sz = PAGE_SIZE;
 285                 }
 286                 int wksz = sz;
 287                 *codec = CCLZ4;
 288
 289                 sz = (int) lz4raw_encode_buffer(cdst, outbufsz, in, insize, &cscratch->lz4state[0]);
 290
 291                 VERBOSE("LZ4 Compress: %d\n", sz);
 292                 compressor_selector_update(sz, dowk, wksz);
 293                 if (sz == 0) {
 294                         sz = -1;
 295                         goto cexit;
 296                 }
 297         }
 298 cexit:
 299         return sz;
 300 }
 301
 302 void metadecompressor(const uint8_t *source, uint8_t *dest, uint32_t csize, uint16_t ccodec, void *compressor_dscratchin) {
 303         int dolz4 = (ccodec == CCLZ4);
 304         int rval;
 305         compressor_decode_scratch_t *compressor_dscratch = compressor_dscratchin;
 306
 307         if (dolz4) {
 308                 rval = (int)lz4raw_decode_buffer(dest, PAGE_SIZE, source, csize, &compressor_dscratch->lz4decodestate[0]);
 309                 VM_DECOMPRESSOR_STAT(compressor_stats.lz4_decompressions+=1);
 310                 VM_DECOMPRESSOR_STAT(compressor_stats.lz4_decompressed_bytes+=csize);
 311
 312                 assertf(rval == PAGE_SIZE, "LZ4 decode: size != pgsize %d", rval);
 313
 314         } else {
 315                 assert(ccodec == CCWK);
 316                 WKdmD(source, dest, &compressor_dscratch->wkdecompscratch[0], csize);
 317                 VM_DECOMPRESSOR_STAT(compressor_stats.wk_decompressions+=1);
 318                 VM_DECOMPRESSOR_STAT(compressor_stats.wk_decompressed_bytes+=csize);
 319         }
 320 }
 321 #pragma clang diagnostic pop
 322
 323 uint32_t vm_compressor_get_encode_scratch_size(void) {
 324         if (vm_compressor_current_codec != VM_COMPRESSOR_DEFAULT_CODEC) {
 325                 return MAX(sizeof(compressor_encode_scratch_t), WKdm_SCRATCH_BUF_SIZE_INTERNAL);
 326         } else {
 327                 return WKdm_SCRATCH_BUF_SIZE_INTERNAL;
 328         }
 329 }
 330
 331 uint32_t vm_compressor_get_decode_scratch_size(void) {
 332         if (vm_compressor_current_codec != VM_COMPRESSOR_DEFAULT_CODEC) {
 333                 return MAX(sizeof(compressor_decode_scratch_t), WKdm_SCRATCH_BUF_SIZE_INTERNAL);
 334         } else {
 335                 return WKdm_SCRATCH_BUF_SIZE_INTERNAL;
 336         }
 337 }
 338
 339
 340 int vm_compressor_algorithm(void) {
 341         return vm_compressor_current_codec;
 342 }
 343
 344 void vm_compressor_algorithm_init(void) {
 345         vm_compressor_mode_t new_codec = VM_COMPRESSOR_DEFAULT_CODEC;
 346
 347
 348         PE_parse_boot_argn("vm_compressor_codec", &new_codec, sizeof(new_codec));
 349         assertf(((new_codec == VM_COMPRESSOR_DEFAULT_CODEC) || (new_codec == CMODE_WK) ||
 350                 (new_codec == CMODE_LZ4) || (new_codec = CMODE_HYB)),
 351             "Invalid VM compression codec: %u", new_codec);
 352
 353
 354         if (PE_parse_boot_argn("-vm_compressor_wk", &new_codec, sizeof(new_codec))) {
 355                 new_codec = VM_COMPRESSOR_DEFAULT_CODEC;
 356         } else if (PE_parse_boot_argn("-vm_compressor_hybrid", &new_codec, sizeof(new_codec))) {
 357                 new_codec = CMODE_HYB;
 358         }
 359
 360 }
 361 //TODO check open-sourceability of lz4