osfmk/kern/affinity.c

   1 /*
   2  * Copyright (c) 2007 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 <kern/affinity.h>
  30 #include <kern/task.h>
  31 #include <kern/kalloc.h>
  32 #include <machine/cpu_affinity.h>
  33
  34 /*
  35  * Affinity involves 2 objects:
  36  * - affinity namespace:
  37  *      shared by a task family, this controls affinity tag lookup and
  38  *      allocation; it anchors all affinity sets in one namespace
  39  * - affinity set:
  40  *      anchors all threads with membership of this affinity set
  41  *      and which share an affinity tag in the owning namespace.
  42  *
  43  * Locking:
  44  * - The task lock protects the creation of an affinity namespace.
  45  * - The affinity namespace mutex protects the inheritance of a namespace
  46  *   and its thread membership. This includes its destruction when the task
  47  *   reference count goes to zero.
  48  * - The thread mutex protects a thread's affinity set membership, but in
  49  *   addition, the thread_lock is taken to write thread->affinity_set since this
  50  *   field (representng the active affinity set) is read by the scheduler.
  51  *
  52  * The lock ordering is: task lock, thread mutex, namespace mutex, thread lock.
  53  */
  54
  55 #if AFFINITY_DEBUG
  56 #define DBG(x...)       kprintf("DBG: " x)
  57 #else
  58 #define DBG(x...)
  59 #endif
  60
  61 struct affinity_space {
  62         mutex_t         aspc_lock;
  63         uint32_t        aspc_task_count;
  64         queue_head_t    aspc_affinities;
  65 };
  66 typedef struct affinity_space *affinity_space_t;
  67
  68 static affinity_space_t affinity_space_alloc(void);
  69 static void affinity_space_free(affinity_space_t aspc);
  70 static affinity_set_t affinity_set_alloc(void);
  71 static void affinity_set_free(affinity_set_t aset);
  72 static affinity_set_t affinity_set_find(affinity_space_t aspc, uint32_t tag);
  73 static void affinity_set_place(affinity_space_t aspc, affinity_set_t aset);
  74 static void affinity_set_add(affinity_set_t aset, thread_t thread);
  75 static affinity_set_t affinity_set_remove(affinity_set_t aset, thread_t thread);
  76
  77 /*
  78  * The following globals may be modified by the sysctls
  79  *   kern.affinity_sets_enabled - disables hinting if cleared
  80  *   kern.affinity_sets_mapping - controls cache distribution policy
  81  * See bsd/kern_sysctl.c
  82  */
  83 boolean_t       affinity_sets_enabled = TRUE;
  84 int             affinity_sets_mapping = 1;
  85
  86 boolean_t
  87 thread_affinity_is_supported(void)
  88 {
  89         return (ml_get_max_affinity_sets() != 0);
  90 }
  91
  92
  93 /*
  94  * thread_affinity_get()
  95  * Return the affinity tag for a thread.
  96  * Called with the thread mutex held.
  97  */
  98 uint32_t
  99 thread_affinity_get(thread_t thread)
 100 {
 101         uint32_t tag;
 102
 103         if (thread->affinity_set != NULL)
 104                 tag = thread->affinity_set->aset_tag;
 105         else
 106                 tag = THREAD_AFFINITY_TAG_NULL;
 107
 108         return tag;
 109 }
 110
 111
 112 /*
 113  * thread_affinity_set()
 114  * Place a thread in an affinity set identified by a tag.
 115  * Called with thread referenced but not locked.
 116  */
 117 kern_return_t
 118 thread_affinity_set(thread_t thread, uint32_t tag)
 119 {
 120         affinity_set_t          aset;
 121         affinity_set_t          empty_aset = NULL;
 122         affinity_space_t        aspc;
 123         affinity_space_t        new_aspc = NULL;
 124
 125         DBG("thread_affinity_set(%p,%u)\n", thread, tag);
 126
 127         task_lock(thread->task);
 128         aspc = thread->task->affinity_space;
 129         if (aspc == NULL) {
 130                 task_unlock(thread->task);
 131                 new_aspc = affinity_space_alloc();
 132                 if (new_aspc == NULL)
 133                         return KERN_RESOURCE_SHORTAGE;
 134                 task_lock(thread->task);
 135                 if (thread->task->affinity_space == NULL) {
 136                         thread->task->affinity_space = new_aspc;
 137                         new_aspc = NULL;
 138                 }
 139                 aspc = thread->task->affinity_space;
 140         }
 141         task_unlock(thread->task);
 142         if (new_aspc)
 143                 affinity_space_free(new_aspc);
 144
 145         thread_mtx_lock(thread);
 146         if (!thread->active) {
 147                 /* Beaten to lock and the thread is dead */
 148                 thread_mtx_unlock(thread);
 149                 return KERN_TERMINATED;
 150         }
 151
 152         mutex_lock(&aspc->aspc_lock);
 153         aset = thread->affinity_set;
 154         if (aset != NULL) {
 155                 /*
 156                  * Remove thread from current affinity set
 157                  */
 158                 DBG("thread_affinity_set(%p,%u) removing from aset %p\n",
 159                         thread, tag, aset);
 160                 empty_aset = affinity_set_remove(aset, thread);
 161         }
 162
 163         if (tag != THREAD_AFFINITY_TAG_NULL) {
 164                 aset = affinity_set_find(aspc, tag);
 165                 if (aset != NULL) {
 166                         /*
 167                          * Add thread to existing affinity set
 168                          */
 169                         DBG("thread_affinity_set(%p,%u) found aset %p\n",
 170                                 thread, tag, aset);
 171                 } else {
 172                         /*
 173                          * Use the new affinity set, add this thread
 174                          * and place it in a suitable processor set.
 175                          */
 176                         if (empty_aset != NULL) {
 177                                 aset = empty_aset;
 178                                 empty_aset = NULL;
 179                         } else {
 180                                 aset = affinity_set_alloc();
 181                                 if (aset == NULL) {
 182                                         mutex_unlock(&aspc->aspc_lock);
 183                                         thread_mtx_unlock(thread);
 184                                         return KERN_RESOURCE_SHORTAGE;
 185                                 }
 186                         }
 187                         DBG("thread_affinity_set(%p,%u) (re-)using aset %p\n",
 188                                 thread, tag, aset);
 189                         aset->aset_tag = tag;
 190                         affinity_set_place(aspc, aset);
 191                 }
 192                 affinity_set_add(aset, thread);
 193         }
 194
 195         mutex_unlock(&aspc->aspc_lock);
 196         thread_mtx_unlock(thread);
 197
 198         /*
 199          * If we wound up not using an empty aset we created,
 200          * free it here.
 201          */
 202         if (empty_aset != NULL)
 203                 affinity_set_free(empty_aset);
 204
 205         if (thread == current_thread())
 206                 thread_block(THREAD_CONTINUE_NULL);
 207
 208         return KERN_SUCCESS;
 209 }
 210
 211 /*
 212  * task_affinity_create()
 213  * Called from task create.
 214  */
 215 void
 216 task_affinity_create(task_t parent_task, task_t child_task)
 217 {
 218         affinity_space_t        aspc = parent_task->affinity_space;
 219
 220         DBG("task_affinity_create(%p,%p)\n", parent_task, child_task);
 221
 222         assert(aspc);
 223
 224         /*
 225          * Bump the task reference count on the shared namespace and
 226          * give it to the child.
 227          */
 228         mutex_lock(&aspc->aspc_lock);
 229         aspc->aspc_task_count++;
 230         child_task->affinity_space = aspc;
 231         mutex_unlock(&aspc->aspc_lock);
 232 }
 233
 234 /*
 235  * task_affinity_deallocate()
 236  * Called from task_deallocate() when there's a namespace to dereference.
 237  */
 238 void
 239 task_affinity_deallocate(task_t task)
 240 {
 241         affinity_space_t        aspc = task->affinity_space;
 242
 243         DBG("task_affinity_deallocate(%p) aspc %p task_count %d\n",
 244                 task, aspc, aspc->aspc_task_count);
 245
 246         mutex_lock(&aspc->aspc_lock);
 247         if (--(aspc->aspc_task_count) == 0) {
 248                 assert(queue_empty(&aspc->aspc_affinities));
 249                 mutex_unlock(&aspc->aspc_lock);
 250                 affinity_space_free(aspc);
 251         } else {
 252                 mutex_unlock(&aspc->aspc_lock);
 253         }
 254 }
 255
 256 /*
 257  * task_affinity_info()
 258  * Return affinity tag info (number, min, max) for the task.
 259  */
 260 kern_return_t
 261 task_affinity_info(
 262         task_t                  task,
 263         task_info_t             task_info_out,
 264         mach_msg_type_number_t  *task_info_count)
 265 {
 266         affinity_set_t                  aset;
 267         affinity_space_t                aspc;
 268         task_affinity_tag_info_t        info;
 269
 270         *task_info_count = TASK_AFFINITY_TAG_INFO_COUNT;
 271         info = (task_affinity_tag_info_t) task_info_out;
 272         info->set_count = 0;
 273         info->task_count = 0;
 274         info->min = THREAD_AFFINITY_TAG_NULL;
 275         info->max = THREAD_AFFINITY_TAG_NULL;
 276
 277         task_lock(task);
 278         aspc = task->affinity_space;
 279         if (aspc) {
 280                 mutex_lock(&aspc->aspc_lock);
 281                 queue_iterate(&aspc->aspc_affinities,
 282                                  aset, affinity_set_t, aset_affinities) {
 283                         info->set_count++;
 284                         if (info->min == THREAD_AFFINITY_TAG_NULL ||
 285                             aset->aset_tag < (uint32_t) info->min)
 286                                 info->min = aset->aset_tag;
 287                         if (info->max == THREAD_AFFINITY_TAG_NULL ||
 288                             aset->aset_tag > (uint32_t) info->max)
 289                                 info->max = aset->aset_tag;
 290                 }
 291                 info->task_count = aspc->aspc_task_count;
 292                 mutex_unlock(&aspc->aspc_lock);
 293         }
 294         task_unlock(task);
 295         return KERN_SUCCESS;
 296 }
 297
 298 /*
 299  * Called from thread_dup() during fork() with child's mutex held.
 300  * Set the child into the parent's affinity set.
 301  * Note the affinity space is shared.
 302  */
 303 void
 304 thread_affinity_dup(thread_t parent, thread_t child)
 305 {
 306         affinity_set_t                  aset;
 307         affinity_space_t                aspc;
 308
 309         thread_mtx_lock(parent);
 310         aset = parent->affinity_set;
 311         DBG("thread_affinity_dup(%p,%p) aset %p\n", parent, child, aset);
 312         if (aset == NULL) {
 313                 thread_mtx_unlock(parent);
 314                 return;
 315         }
 316
 317         aspc = aset->aset_space;
 318         assert(aspc == parent->task->affinity_space);
 319         assert(aspc == child->task->affinity_space);
 320
 321         mutex_lock(&aspc->aspc_lock);
 322         affinity_set_add(aset, child);
 323         mutex_unlock(&aspc->aspc_lock);
 324
 325         thread_mtx_unlock(parent);
 326 }
 327
 328 /*
 329  * thread_affinity_terminate()
 330  * Remove thread from any affinity set.
 331  * Called with the thread mutex locked.
 332  */
 333 void
 334 thread_affinity_terminate(thread_t thread)
 335 {
 336         affinity_set_t          aset = thread->affinity_set;
 337         affinity_space_t        aspc;
 338
 339         DBG("thread_affinity_terminate(%p)\n", thread);
 340
 341         aspc = aset->aset_space;
 342         mutex_lock(&aspc->aspc_lock);
 343         if (affinity_set_remove(aset, thread)) {
 344                 affinity_set_free(aset);
 345         }
 346         mutex_unlock(&aspc->aspc_lock);
 347 }
 348
 349 /*
 350  * Create an empty affinity namespace data structure.
 351  */
 352 static affinity_space_t
 353 affinity_space_alloc(void)
 354 {
 355         affinity_space_t        aspc;
 356
 357         aspc = (affinity_space_t) kalloc(sizeof(struct affinity_space));
 358         if (aspc == NULL)
 359                 return NULL;
 360
 361         mutex_init(&aspc->aspc_lock, 0);
 362         queue_init(&aspc->aspc_affinities);
 363         aspc->aspc_task_count = 1;
 364
 365         DBG("affinity_space_create() returns %p\n", aspc);
 366         return aspc;
 367 }
 368
 369 /*
 370  * Destroy the given empty affinity namespace data structure.
 371  */
 372 static void
 373 affinity_space_free(affinity_space_t aspc)
 374 {
 375         assert(queue_empty(&aspc->aspc_affinities));
 376
 377         DBG("affinity_space_free(%p)\n", aspc);
 378         kfree(aspc, sizeof(struct affinity_space));
 379 }
 380
 381
 382 /*
 383  * Create an empty affinity set data structure
 384  * entering it into a list anchored by the owning task.
 385  */
 386 static affinity_set_t
 387 affinity_set_alloc(void)
 388 {
 389         affinity_set_t  aset;
 390
 391         aset = (affinity_set_t) kalloc(sizeof(struct affinity_set));
 392         if (aset == NULL)
 393                 return NULL;
 394
 395         aset->aset_thread_count = 0;
 396         queue_init(&aset->aset_affinities);
 397         queue_init(&aset->aset_threads);
 398         aset->aset_num = 0;
 399         aset->aset_pset = PROCESSOR_SET_NULL;
 400         aset->aset_space = NULL;
 401
 402         DBG("affinity_set_create() returns %p\n", aset);
 403         return aset;
 404 }
 405
 406 /*
 407  * Destroy the given empty affinity set data structure
 408  * after removing it from the parent task.
 409  */
 410 static void
 411 affinity_set_free(affinity_set_t aset)
 412 {
 413         assert(queue_empty(&aset->aset_threads));
 414
 415         DBG("affinity_set_free(%p)\n", aset);
 416         kfree(aset, sizeof(struct affinity_set));
 417 }
 418
 419 /*
 420  * Add a thread to an affinity set.
 421  * The caller must have the thread mutex and space locked.
 422  */
 423 static void
 424 affinity_set_add(affinity_set_t aset, thread_t thread)
 425 {
 426         spl_t   s;
 427
 428         DBG("affinity_set_add(%p,%p)\n", aset, thread);
 429         queue_enter(&aset->aset_threads,
 430                 thread, thread_t, affinity_threads);
 431         aset->aset_thread_count++;
 432         s = splsched();
 433         thread_lock(thread);
 434         thread->affinity_set = affinity_sets_enabled ? aset : NULL;
 435         thread_unlock(thread);
 436         splx(s);
 437 }
 438
 439 /*
 440  * Remove a thread from an affinity set returning the set if now empty.
 441  * The caller must have the thread mutex and space locked.
 442  */
 443 static affinity_set_t
 444 affinity_set_remove(affinity_set_t aset, thread_t thread)
 445 {
 446         spl_t   s;
 447
 448         s = splsched();
 449         thread_lock(thread);
 450         thread->affinity_set = NULL;
 451         thread_unlock(thread);
 452         splx(s);
 453
 454         aset->aset_thread_count--;
 455         queue_remove(&aset->aset_threads,
 456                 thread, thread_t, affinity_threads);
 457         if (queue_empty(&aset->aset_threads)) {
 458                 queue_remove(&aset->aset_space->aspc_affinities,
 459                                 aset, affinity_set_t, aset_affinities);
 460                 assert(aset->aset_thread_count == 0);
 461                 aset->aset_tag = THREAD_AFFINITY_TAG_NULL;
 462                 aset->aset_num = 0;
 463                 aset->aset_pset = PROCESSOR_SET_NULL;
 464                 aset->aset_space = NULL;
 465                 DBG("affinity_set_remove(%p,%p) set now empty\n", aset, thread);
 466                 return aset;
 467         } else {
 468                 DBG("affinity_set_remove(%p,%p)\n", aset, thread);
 469                 return NULL;
 470         }
 471 }
 472
 473 /*
 474  * Find an affinity set in the parent task with the given affinity tag.
 475  * The caller must have the space locked.
 476  */
 477 static affinity_set_t
 478 affinity_set_find(affinity_space_t space, uint32_t tag)
 479 {
 480         affinity_set_t  aset;
 481
 482         queue_iterate(&space->aspc_affinities,
 483                          aset, affinity_set_t, aset_affinities) {
 484                 if (aset->aset_tag == tag) {
 485                         DBG("affinity_set_find(%p,%u) finds %p\n",
 486                             space, tag, aset);
 487                         return aset;
 488                 }
 489         }
 490         DBG("affinity_set_find(%p,%u) not found\n", space, tag);
 491         return NULL;
 492 }
 493
 494 /*
 495  * affinity_set_place() assigns an affinity set to a suitable processor_set.
 496  * The selection criteria is:
 497  *  - the set currently occupied by the least number of affinities
 498  *    belonging to the owning the task.
 499  * The caller must have the space locked.
 500  */
 501 static void
 502 affinity_set_place(affinity_space_t aspc, affinity_set_t new_aset)
 503 {
 504         unsigned int    num_cpu_asets = ml_get_max_affinity_sets();
 505         unsigned int    set_occupancy[num_cpu_asets];
 506         unsigned int    i;
 507         unsigned int    i_least_occupied;
 508         affinity_set_t  aset;
 509
 510         for (i = 0; i < num_cpu_asets; i++)
 511                 set_occupancy[i] = 0;
 512
 513         /*
 514          * Scan the affinity sets calculating the number of sets
 515          * occupy the available physical affinities.
 516          */
 517         queue_iterate(&aspc->aspc_affinities,
 518                          aset, affinity_set_t, aset_affinities) {
 519                 set_occupancy[aset->aset_num]++;
 520         }
 521
 522         /*
 523          * Find the least occupied set (or the first empty set).
 524          * To distribute placements somewhat, start searching from
 525          * a cpu affinity chosen randomly per namespace:
 526          *   [(unsigned int)aspc % 127] % num_cpu_asets
 527          * unless this mapping policy is overridden.
 528          */
 529         if (affinity_sets_mapping == 0)
 530                 i_least_occupied = 0;
 531         else
 532                 i_least_occupied = ((unsigned int)aspc % 127) % num_cpu_asets;
 533         for (i = 0; i < num_cpu_asets; i++) {
 534                 unsigned int    j = (i_least_occupied + i) % num_cpu_asets;
 535                 if (set_occupancy[j] == 0) {
 536                         i_least_occupied = j;
 537                         break;
 538                 }
 539                 if (set_occupancy[j] < set_occupancy[i_least_occupied])
 540                         i_least_occupied = j;
 541         }
 542         new_aset->aset_num = i_least_occupied;
 543         new_aset->aset_pset = ml_affinity_to_pset(i_least_occupied);
 544
 545         /* Add the new affinity set to the group */
 546         new_aset->aset_space = aspc;
 547         queue_enter(&aspc->aspc_affinities,
 548                         new_aset, affinity_set_t, aset_affinities);
 549
 550         DBG("affinity_set_place(%p,%p) selected affinity %u pset %p\n",
 551             aspc, new_aset, new_aset->aset_num, new_aset->aset_pset);
 552 }