osfmk/kern/restartable.c

   1 /*
   2  * Copyright (c) 2019 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 <mach/mach_types.h>
  30 #include <mach/task.h>
  31
  32 #include <kern/ast.h>
  33 #include <kern/kalloc.h>
  34 #include <kern/kern_types.h>
  35 #include <kern/mach_param.h>
  36 #include <kern/machine.h>
  37 #include <kern/misc_protos.h>
  38 #include <kern/processor.h>
  39 #include <kern/queue.h>
  40 #include <kern/restartable.h>
  41 #include <kern/task.h>
  42 #include <kern/thread.h>
  43 #include <kern/waitq.h>
  44
  45 #include <os/hash.h>
  46 #include <os/refcnt.h>
  47
  48 /**
  49  * @file osfmk/kern/restartable.c
  50  *
  51  * @brief
  52  * This module implements restartable userspace functions.
  53  *
  54  * @discussion
  55  * task_restartable_ranges_register() allows task to configure
  56  * the restartable ranges, only once per task,
  57  * before it has made its second thread.
  58  *
  59  * task_restartable_ranges_synchronize() can later be used to trigger
  60  * restarts for threads with a PC in a restartable region.
  61  *
  62  * It is implemented with an AST (AST_RESET_PCS) that will cause threads
  63  * as they return to userspace to reset PCs in a restartable region
  64  * to the recovery offset of this region.
  65  *
  66  * Because signal delivery would mask the proper saved PC for threads,
  67  * sigreturn also forcefully sets the AST and will go through the logic
  68  * every single time.
  69  */
  70
  71 typedef int (*cmpfunc_t)(const void *a, const void *b);
  72 extern void qsort(void *a, size_t n, size_t es, cmpfunc_t cmp);
  73
  74 struct restartable_ranges {
  75         queue_chain_t            rr_link;
  76         os_refcnt_t              rr_ref;
  77         uint32_t                 rr_count;
  78         uint32_t                 rr_hash;
  79         task_restartable_range_t rr_ranges[];
  80 };
  81
  82 #if DEBUG || DEVELOPMENT
  83 #define RR_HASH_SIZE   256
  84 #else
  85 // Release kernel userspace should have shared caches and a single registration
  86 #define RR_HASH_SIZE    16
  87 #endif
  88
  89 static queue_head_t rr_hash[RR_HASH_SIZE];
  90 LCK_GRP_DECLARE(rr_lock_grp, "restartable ranges");
  91 LCK_SPIN_DECLARE(rr_spinlock, &rr_lock_grp);
  92
  93 #define rr_lock()   lck_spin_lock_grp(&rr_spinlock, &rr_lock_grp)
  94 #define rr_unlock() lck_spin_unlock(&rr_spinlock);
  95
  96 #pragma mark internals
  97
  98 /**
  99  * @function _ranges_cmp
 100  *
 101  * @brief
 102  * Compares two ranges together.
 103  */
 104 static int
 105 _ranges_cmp(const void *_r1, const void *_r2)
 106 {
 107         const task_restartable_range_t *r1 = _r1;
 108         const task_restartable_range_t *r2 = _r2;
 109
 110         if (r1->location != r2->location) {
 111                 return r1->location < r2->location ? -1 : 1;
 112         }
 113         if (r1->length == r2->length) {
 114                 return 0;
 115         }
 116         return r1->length < r2->length ? -1 : 1;
 117 }
 118
 119 /**
 120  * @function _ranges_validate
 121  *
 122  * @brief
 123  * Validates an array of PC ranges for wraps and intersections.
 124  *
 125  * @discussion
 126  * This sorts and modifies the input.
 127  *
 128  * The ranges must:
 129  * - not wrap around,
 130  * - have a length/recovery offset within a page of the range start
 131  *
 132  * @returns
 133  * - KERN_SUCCESS:          ranges are valid
 134  * - KERN_INVALID_ARGUMENT: ranges are invalid
 135  */
 136 static kern_return_t
 137 _ranges_validate(task_t task, task_restartable_range_t *ranges, uint32_t count)
 138 {
 139         qsort(ranges, count, sizeof(task_restartable_range_t), _ranges_cmp);
 140         uint64_t limit = task_has_64Bit_data(task) ? UINT64_MAX : UINT32_MAX;
 141         uint64_t end, recovery;
 142
 143         if (count == 0) {
 144                 return KERN_INVALID_ARGUMENT;
 145         }
 146
 147         for (size_t i = 0; i < count; i++) {
 148                 if (ranges[i].length > TASK_RESTARTABLE_OFFSET_MAX ||
 149                     ranges[i].recovery_offs > TASK_RESTARTABLE_OFFSET_MAX) {
 150                         return KERN_INVALID_ARGUMENT;
 151                 }
 152                 if (ranges[i].flags) {
 153                         return KERN_INVALID_ARGUMENT;
 154                 }
 155                 if (os_add_overflow(ranges[i].location, ranges[i].length, &end)) {
 156                         return KERN_INVALID_ARGUMENT;
 157                 }
 158                 if (os_add_overflow(ranges[i].location, ranges[i].recovery_offs, &recovery)) {
 159                         return KERN_INVALID_ARGUMENT;
 160                 }
 161                 if (ranges[i].location > limit || end > limit || recovery > limit) {
 162                         return KERN_INVALID_ARGUMENT;
 163                 }
 164                 if (i + 1 < count && end > ranges[i + 1].location) {
 165                         return KERN_INVALID_ARGUMENT;
 166                 }
 167         }
 168
 169         return KERN_SUCCESS;
 170 }
 171
 172 /**
 173  * @function _ranges_lookup
 174  *
 175  * @brief
 176  * Lookup the left side of a range for a given PC within a set of ranges.
 177  *
 178  * @returns
 179  * - 0: no PC range found
 180  * - the left-side of the range.
 181  */
 182 __attribute__((always_inline))
 183 static mach_vm_address_t
 184 _ranges_lookup(struct restartable_ranges *rr, mach_vm_address_t pc)
 185 {
 186         task_restartable_range_t *ranges = rr->rr_ranges;
 187         uint32_t l = 0, r = rr->rr_count;
 188
 189         if (pc <= ranges[0].location) {
 190                 return 0;
 191         }
 192         if (pc >= ranges[r - 1].location + ranges[r - 1].length) {
 193                 return 0;
 194         }
 195
 196         while (l < r) {
 197                 uint32_t i = (r + l) / 2;
 198                 mach_vm_address_t location = ranges[i].location;
 199
 200                 if (pc <= location) {
 201                         /* if the PC is exactly at pc_start, no reset is needed */
 202                         r = i;
 203                 } else if (location + ranges[i].length <= pc) {
 204                         /* if the PC is exactly at the end, it's out of the function */
 205                         l = i + 1;
 206                 } else {
 207                         /* else it's strictly in the range, return the recovery pc */
 208                         return location + ranges[i].recovery_offs;
 209                 }
 210         }
 211
 212         return 0;
 213 }
 214
 215 /**
 216  * @function _restartable_ranges_dispose
 217  *
 218  * @brief
 219  * Helper to dispose of a range that has reached a 0 refcount.
 220  */
 221 __attribute__((noinline))
 222 static void
 223 _restartable_ranges_dispose(struct restartable_ranges *rr, bool hash_remove)
 224 {
 225         if (hash_remove) {
 226                 rr_lock();
 227                 remqueue(&rr->rr_link);
 228                 rr_unlock();
 229         }
 230         kfree(rr, sizeof(*rr) + rr->rr_count * sizeof(task_restartable_range_t));
 231 }
 232
 233 /**
 234  * @function _restartable_ranges_equals
 235  *
 236  * @brief
 237  * Helper to compare two restartable ranges.
 238  */
 239 static bool
 240 _restartable_ranges_equals(
 241         const struct restartable_ranges *rr1,
 242         const struct restartable_ranges *rr2)
 243 {
 244         size_t rr1_size = rr1->rr_count * sizeof(task_restartable_range_t);
 245         return rr1->rr_hash == rr2->rr_hash &&
 246                rr1->rr_count == rr2->rr_count &&
 247                memcmp(rr1->rr_ranges, rr2->rr_ranges, rr1_size) == 0;
 248 }
 249
 250 /**
 251  * @function _restartable_ranges_create
 252  *
 253  * @brief
 254  * Helper to create a uniqued restartable range.
 255  *
 256  * @returns
 257  * - KERN_SUCCESS
 258  * - KERN_INVALID_ARGUMENT: the validation of the new ranges failed.
 259  * - KERN_RESOURCE_SHORTAGE: too many ranges, out of memory
 260  */
 261 static kern_return_t
 262 _restartable_ranges_create(task_t task, task_restartable_range_t *ranges,
 263     uint32_t count, struct restartable_ranges **rr_storage)
 264 {
 265         struct restartable_ranges *rr, *rr_found, *rr_base;
 266         queue_head_t *head;
 267         uint32_t base_count, total_count;
 268         size_t base_size, size;
 269         kern_return_t kr;
 270
 271         rr_base = *rr_storage;
 272         base_count = rr_base ? rr_base->rr_count : 0;
 273         base_size = sizeof(task_restartable_range_t) * base_count;
 274         size = sizeof(task_restartable_range_t) * count;
 275
 276         if (os_add_overflow(base_count, count, &total_count)) {
 277                 return KERN_INVALID_ARGUMENT;
 278         }
 279         if (total_count > 1024) {
 280                 return KERN_RESOURCE_SHORTAGE;
 281         }
 282
 283         rr = kalloc(sizeof(*rr) + base_size + size);
 284         if (rr == NULL) {
 285                 return KERN_RESOURCE_SHORTAGE;
 286         }
 287
 288         queue_chain_init(rr->rr_link);
 289         os_ref_init(&rr->rr_ref, NULL);
 290         rr->rr_count = total_count;
 291         if (base_size) {
 292                 memcpy(rr->rr_ranges, rr_base->rr_ranges, base_size);
 293         }
 294         memcpy(rr->rr_ranges + base_count, ranges, size);
 295         kr = _ranges_validate(task, rr->rr_ranges, total_count);
 296         if (kr) {
 297                 _restartable_ranges_dispose(rr, false);
 298                 return kr;
 299         }
 300         rr->rr_hash = os_hash_jenkins(rr->rr_ranges,
 301             rr->rr_count * sizeof(task_restartable_range_t));
 302
 303         head = &rr_hash[rr->rr_hash % RR_HASH_SIZE];
 304
 305         rr_lock();
 306         queue_iterate(head, rr_found, struct restartable_ranges *, rr_link) {
 307                 if (_restartable_ranges_equals(rr, rr_found) &&
 308                 os_ref_retain_try(&rr_found->rr_ref)) {
 309                         goto found;
 310                 }
 311         }
 312
 313         enqueue_tail(head, &rr->rr_link);
 314         rr_found = rr;
 315
 316 found:
 317         if (rr_base && os_ref_release_relaxed(&rr_base->rr_ref) == 0) {
 318                 remqueue(&rr_base->rr_link);
 319         } else {
 320                 rr_base = NULL;
 321         }
 322         rr_unlock();
 323
 324         *rr_storage = rr_found;
 325
 326         if (rr_found != rr) {
 327                 _restartable_ranges_dispose(rr, false);
 328         }
 329         if (rr_base) {
 330                 _restartable_ranges_dispose(rr_base, false);
 331         }
 332         return KERN_SUCCESS;
 333 }
 334
 335 #pragma mark extern interfaces
 336
 337 void
 338 restartable_ranges_release(struct restartable_ranges *rr)
 339 {
 340         if (os_ref_release_relaxed(&rr->rr_ref) == 0) {
 341                 _restartable_ranges_dispose(rr, true);
 342         }
 343 }
 344
 345 void
 346 thread_reset_pcs_ast(thread_t thread)
 347 {
 348         task_t task = thread->task;
 349         struct restartable_ranges *rr;
 350         mach_vm_address_t pc;
 351
 352         /*
 353          * Because restartable_ranges are set while the task only has on thread
 354          * and can't be mutated outside of this, no lock is required to read this.
 355          */
 356         rr = task->restartable_ranges;
 357         if (rr) {
 358                 /* pairs with the barrier in task_restartable_ranges_synchronize() */
 359                 os_atomic_thread_fence(acquire);
 360
 361                 pc = _ranges_lookup(rr, machine_thread_pc(thread));
 362
 363                 if (pc) {
 364                         machine_thread_reset_pc(thread, pc);
 365                 }
 366         }
 367 }
 368
 369 void
 370 restartable_init(void)
 371 {
 372         for (size_t i = 0; i < RR_HASH_SIZE; i++) {
 373                 queue_head_init(rr_hash[i]);
 374         }
 375 }
 376
 377 #pragma mark MiG interfaces
 378
 379 kern_return_t
 380 task_restartable_ranges_register(
 381         task_t                    task,
 382         task_restartable_range_t *ranges,
 383         mach_msg_type_number_t    count)
 384 {
 385         kern_return_t kr;
 386         thread_t th;
 387
 388         if (task != current_task()) {
 389                 return KERN_FAILURE;
 390         }
 391
 392
 393         kr = _ranges_validate(task, ranges, count);
 394
 395         if (kr == KERN_SUCCESS) {
 396                 task_lock(task);
 397
 398                 queue_iterate(&task->threads, th, thread_t, task_threads) {
 399                         if (th != current_thread()) {
 400                                 kr = KERN_NOT_SUPPORTED;
 401                                 break;
 402                         }
 403                 }
 404 #if !DEBUG && !DEVELOPMENT
 405                 /*
 406                  * For security reasons, on release kernels, only allow for this to be
 407                  * configured once.
 408                  *
 409                  * But to be able to test the feature we need to relax this for
 410                  * dev kernels.
 411                  */
 412                 if (task->restartable_ranges) {
 413                         kr = KERN_NOT_SUPPORTED;
 414                 }
 415 #endif
 416                 if (kr == KERN_SUCCESS) {
 417                         kr = _restartable_ranges_create(task, ranges, count,
 418                             &task->restartable_ranges);
 419                 }
 420                 task_unlock(task);
 421         }
 422
 423         return kr;
 424 }
 425
 426 kern_return_t
 427 task_restartable_ranges_synchronize(task_t task)
 428 {
 429         thread_t thread;
 430
 431         if (task != current_task()) {
 432                 return KERN_FAILURE;
 433         }
 434
 435         /* pairs with the barrier in thread_reset_pcs_ast() */
 436         os_atomic_thread_fence(release);
 437
 438         task_lock(task);
 439
 440         if (task->restartable_ranges) {
 441                 queue_iterate(&task->threads, thread, thread_t, task_threads) {
 442                         if (thread != current_thread()) {
 443                                 thread_mtx_lock(thread);
 444                                 act_set_ast_reset_pcs(thread);
 445                                 thread_mtx_unlock(thread);
 446                         }
 447                 }
 448         }
 449
 450         task_unlock(task);
 451
 452         return KERN_SUCCESS;
 453 }