deps/lightrec/recompiler.c

   1 // SPDX-License-Identifier: LGPL-2.1-or-later
   2 /*
   3  * Copyright (C) 2019-2021 Paul Cercueil <paul@crapouillou.net>
   4  */
   5
   6 #include "blockcache.h"
   7 #include "debug.h"
   8 #include "interpreter.h"
   9 #include "lightrec-private.h"
  10 #include "memmanager.h"
  11 #include "reaper.h"
  12 #include "slist.h"
  13
  14 #include <errno.h>
  15 #include <stdatomic.h>
  16 #include <stdbool.h>
  17 #include <stdlib.h>
  18 #include <pthread.h>
  19 #ifdef __linux__
  20 #include <unistd.h>
  21 #endif
  22
  23 struct block_rec {
  24         struct block *block;
  25         struct slist_elm slist;
  26         unsigned int requests;
  27         bool compiling;
  28 };
  29
  30 struct recompiler_thd {
  31         struct lightrec_cstate *cstate;
  32         unsigned int tid;
  33         pthread_t thd;
  34 };
  35
  36 struct recompiler {
  37         struct lightrec_state *state;
  38         pthread_cond_t cond;
  39         pthread_cond_t cond2;
  40         pthread_mutex_t mutex;
  41         bool stop, must_flush;
  42         struct slist_elm slist;
  43
  44         pthread_mutex_t alloc_mutex;
  45
  46         unsigned int nb_recs;
  47         struct recompiler_thd thds[];
  48 };
  49
  50 static unsigned int get_processors_count(void)
  51 {
  52         unsigned int nb = 1;
  53
  54 #if defined(PTW32_VERSION)
  55         nb = pthread_num_processors_np();
  56 #elif defined(__APPLE__) || defined(__FreeBSD__)
  57         int count;
  58         size_t size = sizeof(count);
  59
  60         nb = sysctlbyname("hw.ncpu", &count, &size, NULL, 0) ? 1 : count;
  61 #elif defined(_SC_NPROCESSORS_ONLN)
  62         nb = sysconf(_SC_NPROCESSORS_ONLN);
  63 #endif
  64
  65         return nb < 1 ? 1 : nb;
  66 }
  67
  68 static struct block_rec * lightrec_get_best_elm(struct slist_elm *head)
  69 {
  70         struct block_rec *block_rec, *best = NULL;
  71         struct slist_elm *elm;
  72
  73         for (elm = slist_first(head); elm; elm = elm->next) {
  74                 block_rec = container_of(elm, struct block_rec, slist);
  75
  76                 if (!block_rec->compiling
  77                     && (!best || block_rec->requests > best->requests))
  78                         best = block_rec;
  79         }
  80
  81         return best;
  82 }
  83
  84 static bool lightrec_cancel_block_rec(struct recompiler *rec,
  85                                       struct block_rec *block_rec)
  86 {
  87         if (block_rec->compiling) {
  88                 /* Block is being recompiled - wait for
  89                  * completion */
  90                 pthread_cond_wait(&rec->cond2, &rec->mutex);
  91
  92                 /* We can't guarantee the signal was for us.
  93                  * Since block_rec may have been removed while
  94                  * we were waiting on the condition, we cannot
  95                  * check block_rec->compiling again. The best
  96                  * thing is just to restart the function. */
  97                 return false;
  98         }
  99
 100         /* Block is not yet being processed - remove it from the list */
 101         slist_remove(&rec->slist, &block_rec->slist);
 102         lightrec_free(rec->state, MEM_FOR_LIGHTREC,
 103                       sizeof(*block_rec), block_rec);
 104
 105         return true;
 106 }
 107
 108 static void lightrec_cancel_list(struct recompiler *rec)
 109 {
 110         struct block_rec *block_rec;
 111         struct slist_elm *elm, *head = &rec->slist;
 112
 113         for (elm = slist_first(head); elm; elm = slist_first(head)) {
 114                 block_rec = container_of(elm, struct block_rec, slist);
 115                 lightrec_cancel_block_rec(rec, block_rec);
 116         }
 117 }
 118
 119 static void lightrec_flush_code_buffer(struct lightrec_state *state, void *d)
 120 {
 121         struct recompiler *rec = d;
 122
 123         lightrec_remove_outdated_blocks(state->block_cache, NULL);
 124         rec->must_flush = false;
 125 }
 126
 127 static void lightrec_compile_list(struct recompiler *rec,
 128                                   struct recompiler_thd *thd)
 129 {
 130         struct block_rec *block_rec;
 131         struct block *block;
 132         int ret;
 133
 134         while (!!(block_rec = lightrec_get_best_elm(&rec->slist))) {
 135                 block_rec->compiling = true;
 136                 block = block_rec->block;
 137
 138                 pthread_mutex_unlock(&rec->mutex);
 139
 140                 if (likely(!block_has_flag(block, BLOCK_IS_DEAD))) {
 141                         ret = lightrec_compile_block(thd->cstate, block);
 142                         if (ret == -ENOMEM) {
 143                                 /* Code buffer is full. Request the reaper to
 144                                  * flush it. */
 145
 146                                 pthread_mutex_lock(&rec->mutex);
 147                                 block_rec->compiling = false;
 148                                 pthread_cond_broadcast(&rec->cond2);
 149
 150                                 if (!rec->must_flush) {
 151                                         rec->must_flush = true;
 152                                         lightrec_cancel_list(rec);
 153
 154                                         lightrec_reaper_add(rec->state->reaper,
 155                                                             lightrec_flush_code_buffer,
 156                                                             rec);
 157                                 }
 158                                 return;
 159                         }
 160
 161                         if (ret) {
 162                                 pr_err("Unable to compile block at "PC_FMT": %d\n",
 163                                        block->pc, ret);
 164                         }
 165                 }
 166
 167                 pthread_mutex_lock(&rec->mutex);
 168
 169                 slist_remove(&rec->slist, &block_rec->slist);
 170                 lightrec_free(rec->state, MEM_FOR_LIGHTREC,
 171                               sizeof(*block_rec), block_rec);
 172                 pthread_cond_broadcast(&rec->cond2);
 173         }
 174 }
 175
 176 static void * lightrec_recompiler_thd(void *d)
 177 {
 178         struct recompiler_thd *thd = d;
 179         struct recompiler *rec = container_of(thd, struct recompiler, thds[thd->tid]);
 180
 181         pthread_mutex_lock(&rec->mutex);
 182
 183         while (!rec->stop) {
 184                 do {
 185                         pthread_cond_wait(&rec->cond, &rec->mutex);
 186
 187                         if (rec->stop)
 188                                 goto out_unlock;
 189
 190                 } while (slist_empty(&rec->slist));
 191
 192                 lightrec_compile_list(rec, thd);
 193         }
 194
 195 out_unlock:
 196         pthread_mutex_unlock(&rec->mutex);
 197         return NULL;
 198 }
 199
 200 struct recompiler *lightrec_recompiler_init(struct lightrec_state *state)
 201 {
 202         struct recompiler *rec;
 203         unsigned int i, nb_recs, nb_cpus;
 204         int ret;
 205
 206         nb_cpus = get_processors_count();
 207         nb_recs = nb_cpus < 2 ? 1 : nb_cpus - 1;
 208
 209         rec = lightrec_malloc(state, MEM_FOR_LIGHTREC, sizeof(*rec)
 210                               + nb_recs * sizeof(*rec->thds));
 211         if (!rec) {
 212                 pr_err("Cannot create recompiler: Out of memory\n");
 213                 return NULL;
 214         }
 215
 216         for (i = 0; i < nb_recs; i++) {
 217                 rec->thds[i].tid = i;
 218                 rec->thds[i].cstate = NULL;
 219         }
 220
 221         for (i = 0; i < nb_recs; i++) {
 222                 rec->thds[i].cstate = lightrec_create_cstate(state);
 223                 if (!rec->thds[i].cstate) {
 224                         pr_err("Cannot create recompiler: Out of memory\n");
 225                         goto err_free_cstates;
 226                 }
 227         }
 228
 229         rec->state = state;
 230         rec->stop = false;
 231         rec->must_flush = false;
 232         rec->nb_recs = nb_recs;
 233         slist_init(&rec->slist);
 234
 235         ret = pthread_cond_init(&rec->cond, NULL);
 236         if (ret) {
 237                 pr_err("Cannot init cond variable: %d\n", ret);
 238                 goto err_free_cstates;
 239         }
 240
 241         ret = pthread_cond_init(&rec->cond2, NULL);
 242         if (ret) {
 243                 pr_err("Cannot init cond variable: %d\n", ret);
 244                 goto err_cnd_destroy;
 245         }
 246
 247         ret = pthread_mutex_init(&rec->alloc_mutex, NULL);
 248         if (ret) {
 249                 pr_err("Cannot init alloc mutex variable: %d\n", ret);
 250                 goto err_cnd2_destroy;
 251         }
 252
 253         ret = pthread_mutex_init(&rec->mutex, NULL);
 254         if (ret) {
 255                 pr_err("Cannot init mutex variable: %d\n", ret);
 256                 goto err_alloc_mtx_destroy;
 257         }
 258
 259         for (i = 0; i < nb_recs; i++) {
 260                 ret = pthread_create(&rec->thds[i].thd, NULL,
 261                                      lightrec_recompiler_thd, &rec->thds[i]);
 262                 if (ret) {
 263                         pr_err("Cannot create recompiler thread: %d\n", ret);
 264                         /* TODO: Handle cleanup properly */
 265                         goto err_mtx_destroy;
 266                 }
 267         }
 268
 269         pr_info("Threaded recompiler started with %u workers.\n", nb_recs);
 270
 271         return rec;
 272
 273 err_mtx_destroy:
 274         pthread_mutex_destroy(&rec->mutex);
 275 err_alloc_mtx_destroy:
 276         pthread_mutex_destroy(&rec->alloc_mutex);
 277 err_cnd2_destroy:
 278         pthread_cond_destroy(&rec->cond2);
 279 err_cnd_destroy:
 280         pthread_cond_destroy(&rec->cond);
 281 err_free_cstates:
 282         for (i = 0; i < nb_recs; i++) {
 283                 if (rec->thds[i].cstate)
 284                         lightrec_free_cstate(rec->thds[i].cstate);
 285         }
 286         lightrec_free(state, MEM_FOR_LIGHTREC, sizeof(*rec), rec);
 287         return NULL;
 288 }
 289
 290 void lightrec_free_recompiler(struct recompiler *rec)
 291 {
 292         unsigned int i;
 293
 294         rec->stop = true;
 295
 296         /* Stop the thread */
 297         pthread_mutex_lock(&rec->mutex);
 298         pthread_cond_broadcast(&rec->cond);
 299         lightrec_cancel_list(rec);
 300         pthread_mutex_unlock(&rec->mutex);
 301
 302         for (i = 0; i < rec->nb_recs; i++)
 303                 pthread_join(rec->thds[i].thd, NULL);
 304
 305         for (i = 0; i < rec->nb_recs; i++)
 306                 lightrec_free_cstate(rec->thds[i].cstate);
 307
 308         pthread_mutex_destroy(&rec->mutex);
 309         pthread_mutex_destroy(&rec->alloc_mutex);
 310         pthread_cond_destroy(&rec->cond);
 311         pthread_cond_destroy(&rec->cond2);
 312         lightrec_free(rec->state, MEM_FOR_LIGHTREC, sizeof(*rec), rec);
 313 }
 314
 315 int lightrec_recompiler_add(struct recompiler *rec, struct block *block)
 316 {
 317         struct slist_elm *elm;
 318         struct block_rec *block_rec;
 319         u32 pc1, pc2;
 320         int ret = 0;
 321
 322         pthread_mutex_lock(&rec->mutex);
 323
 324         /* If the recompiler must flush the code cache, we can't add the new
 325          * job. It will be re-added next time the block's address is jumped to
 326          * again. */
 327         if (rec->must_flush)
 328                 goto out_unlock;
 329
 330         /* If the block is marked as dead, don't compile it, it will be removed
 331          * as soon as it's safe. */
 332         if (block_has_flag(block, BLOCK_IS_DEAD))
 333                 goto out_unlock;
 334
 335         for (elm = slist_first(&rec->slist); elm; elm = elm->next) {
 336                 block_rec = container_of(elm, struct block_rec, slist);
 337
 338                 if (block_rec->block == block) {
 339                         /* The block to compile is already in the queue -
 340                          * increment its counter to increase its priority */
 341                         block_rec->requests++;
 342                         goto out_unlock;
 343                 }
 344
 345                 pc1 = kunseg(block_rec->block->pc);
 346                 pc2 = kunseg(block->pc);
 347                 if (pc2 >= pc1 && pc2 < pc1 + block_rec->block->nb_ops * 4) {
 348                         /* The block we want to compile is already covered by
 349                          * another one in the queue - increment its counter to
 350                          * increase its priority */
 351                         block_rec->requests++;
 352                         goto out_unlock;
 353                 }
 354         }
 355
 356         /* By the time this function was called, the block has been recompiled
 357          * and ins't in the wait list anymore. Just return here. */
 358         if (block->function && !block_has_flag(block, BLOCK_SHOULD_RECOMPILE))
 359                 goto out_unlock;
 360
 361         block_rec = lightrec_malloc(rec->state, MEM_FOR_LIGHTREC,
 362                                     sizeof(*block_rec));
 363         if (!block_rec) {
 364                 ret = -ENOMEM;
 365                 goto out_unlock;
 366         }
 367
 368         pr_debug("Adding block "PC_FMT" to recompiler\n", block->pc);
 369
 370         block_rec->block = block;
 371         block_rec->compiling = false;
 372         block_rec->requests = 1;
 373
 374         elm = &rec->slist;
 375
 376         /* Push the new entry to the front of the queue */
 377         slist_append(elm, &block_rec->slist);
 378
 379         /* Signal the thread */
 380         pthread_cond_signal(&rec->cond);
 381
 382 out_unlock:
 383         pthread_mutex_unlock(&rec->mutex);
 384
 385         return ret;
 386 }
 387
 388 void lightrec_recompiler_remove(struct recompiler *rec, struct block *block)
 389 {
 390         struct block_rec *block_rec;
 391         struct slist_elm *elm;
 392
 393         pthread_mutex_lock(&rec->mutex);
 394
 395         while (true) {
 396                 for (elm = slist_first(&rec->slist); elm; elm = elm->next) {
 397                         block_rec = container_of(elm, struct block_rec, slist);
 398
 399                         if (block_rec->block == block) {
 400                                 if (lightrec_cancel_block_rec(rec, block_rec))
 401                                         goto out_unlock;
 402
 403                                 break;
 404                         }
 405                 }
 406
 407                 if (!elm)
 408                         break;
 409         }
 410
 411 out_unlock:
 412         pthread_mutex_unlock(&rec->mutex);
 413 }
 414
 415 void * lightrec_recompiler_run_first_pass(struct lightrec_state *state,
 416                                           struct block *block, u32 *pc)
 417 {
 418         u8 old_flags;
 419
 420         /* There's no point in running the first pass if the block will never
 421          * be compiled. Let the main loop run the interpreter instead. */
 422         if (block_has_flag(block, BLOCK_NEVER_COMPILE))
 423                 return NULL;
 424
 425         /* The block is marked as dead, and will be removed the next time the
 426          * reaper is run. In the meantime, the old function can still be
 427          * executed. */
 428         if (block_has_flag(block, BLOCK_IS_DEAD))
 429                 return block->function;
 430
 431         /* If the block is already fully tagged, there is no point in running
 432          * the first pass. Request a recompilation of the block, and maybe the
 433          * interpreter will run the block in the meantime. */
 434         if (block_has_flag(block, BLOCK_FULLY_TAGGED))
 435                 lightrec_recompiler_add(state->rec, block);
 436
 437         if (likely(block->function)) {
 438                 if (block_has_flag(block, BLOCK_FULLY_TAGGED)) {
 439                         old_flags = block_set_flags(block, BLOCK_NO_OPCODE_LIST);
 440
 441                         if (!(old_flags & BLOCK_NO_OPCODE_LIST)) {
 442                                 pr_debug("Block "PC_FMT" is fully tagged"
 443                                          " - free opcode list\n", block->pc);
 444
 445                                 /* The block was already compiled but the opcode list
 446                                  * didn't get freed yet - do it now */
 447                                 lightrec_free_opcode_list(state, block->opcode_list);
 448                         }
 449                 }
 450
 451                 return block->function;
 452         }
 453
 454         /* Mark the opcode list as freed, so that the threaded compiler won't
 455          * free it while we're using it in the interpreter. */
 456         old_flags = block_set_flags(block, BLOCK_NO_OPCODE_LIST);
 457
 458         /* Block wasn't compiled yet - run the interpreter */
 459         *pc = lightrec_emulate_block(state, block, *pc);
 460
 461         if (!(old_flags & BLOCK_NO_OPCODE_LIST))
 462                 block_clear_flags(block, BLOCK_NO_OPCODE_LIST);
 463
 464         /* The block got compiled while the interpreter was running.
 465          * We can free the opcode list now. */
 466         if (block->function && block_has_flag(block, BLOCK_FULLY_TAGGED)) {
 467                 old_flags = block_set_flags(block, BLOCK_NO_OPCODE_LIST);
 468
 469                 if (!(old_flags & BLOCK_NO_OPCODE_LIST)) {
 470                         pr_debug("Block "PC_FMT" is fully tagged"
 471                                  " - free opcode list\n", block->pc);
 472
 473                         lightrec_free_opcode_list(state, block->opcode_list);
 474                 }
 475         }
 476
 477         return NULL;
 478 }
 479
 480 void lightrec_code_alloc_lock(struct lightrec_state *state)
 481 {
 482         pthread_mutex_lock(&state->rec->alloc_mutex);
 483 }
 484
 485 void lightrec_code_alloc_unlock(struct lightrec_state *state)
 486 {
 487         pthread_mutex_unlock(&state->rec->alloc_mutex);
 488 }