deps/lightrec/blockcache.c

   1 // SPDX-License-Identifier: LGPL-2.1-or-later
   2 /*
   3  * Copyright (C) 2015-2021 Paul Cercueil <paul@crapouillou.net>
   4  */
   5
   6 #include "blockcache.h"
   7 #include "debug.h"
   8 #include "lightrec-private.h"
   9 #include "memmanager.h"
  10 #include "reaper.h"
  11 #include "recompiler.h"
  12
  13 #include <stdbool.h>
  14 #include <stdlib.h>
  15 #include <string.h>
  16
  17 /* Must be power of two */
  18 #define LUT_SIZE 0x4000
  19
  20 struct blockcache {
  21         struct lightrec_state *state;
  22         struct block * lut[LUT_SIZE];
  23 };
  24
  25 u16 lightrec_get_lut_entry(const struct block *block)
  26 {
  27         return (kunseg(block->pc) >> 2) & (LUT_SIZE - 1);
  28 }
  29
  30 struct block * lightrec_find_block(struct blockcache *cache, u32 pc)
  31 {
  32         struct block *block;
  33
  34         pc = kunseg(pc);
  35
  36         for (block = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  37              block; block = block->next)
  38                 if (kunseg(block->pc) == pc)
  39                         return block;
  40
  41         return NULL;
  42 }
  43
  44 struct block * lightrec_find_block_from_lut(struct blockcache *cache,
  45                                             u16 lut_entry, u32 addr_in_block)
  46 {
  47         struct block *block;
  48         u32 pc;
  49
  50         addr_in_block = kunseg(addr_in_block);
  51
  52         for (block = cache->lut[lut_entry]; block; block = block->next) {
  53                 pc = kunseg(block->pc);
  54                 if (addr_in_block >= pc &&
  55                     addr_in_block < pc + (block->nb_ops << 2))
  56                         return block;
  57         }
  58
  59         return NULL;
  60 }
  61
  62 void remove_from_code_lut(struct blockcache *cache, struct block *block)
  63 {
  64         struct lightrec_state *state = cache->state;
  65         u32 offset = lut_offset(block->pc);
  66
  67         if (block->function) {
  68                 memset(lut_address(state, offset), 0,
  69                        block->nb_ops * lut_elm_size(state));
  70         }
  71 }
  72
  73 void lightrec_register_block(struct blockcache *cache, struct block *block)
  74 {
  75         u32 pc = kunseg(block->pc);
  76         struct block *old;
  77
  78         old = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  79         if (old)
  80                 block->next = old;
  81
  82         cache->lut[(pc >> 2) & (LUT_SIZE - 1)] = block;
  83
  84         remove_from_code_lut(cache, block);
  85 }
  86
  87 void lightrec_unregister_block(struct blockcache *cache, struct block *block)
  88 {
  89         u32 pc = kunseg(block->pc);
  90         struct block *old = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  91
  92         if (old == block) {
  93                 cache->lut[(pc >> 2) & (LUT_SIZE - 1)] = old->next;
  94                 return;
  95         }
  96
  97         for (; old; old = old->next) {
  98                 if (old->next == block) {
  99                         old->next = block->next;
 100                         return;
 101                 }
 102         }
 103
 104         pr_err("Block at PC 0x%x is not in cache\n", block->pc);
 105 }
 106
 107 static bool lightrec_block_is_old(const struct lightrec_state *state,
 108                                   const struct block *block)
 109 {
 110         u32 diff = state->current_cycle - block->precompile_date;
 111
 112         return diff > (1 << 27); /* About 4 seconds */
 113 }
 114
 115 static void lightrec_free_blocks(struct blockcache *cache,
 116                                  const struct block *except, bool all)
 117 {
 118         struct lightrec_state *state = cache->state;
 119         struct block *block, *next;
 120         bool outdated = all;
 121         unsigned int i;
 122         u8 old_flags;
 123
 124         for (i = 0; i < LUT_SIZE; i++) {
 125                 for (block = cache->lut[i]; block; block = next) {
 126                         next = block->next;
 127
 128                         if (except && block == except)
 129                                 continue;
 130
 131                         if (!all) {
 132                                 outdated = lightrec_block_is_old(state, block) ||
 133                                         lightrec_block_is_outdated(state, block);
 134                         }
 135
 136                         if (!outdated)
 137                                 continue;
 138
 139                         old_flags = block_set_flags(block, BLOCK_IS_DEAD);
 140
 141                         if (!(old_flags & BLOCK_IS_DEAD)) {
 142                                 if (ENABLE_THREADED_COMPILER)
 143                                         lightrec_recompiler_remove(state->rec, block);
 144
 145                                 pr_debug("Freeing outdated block at PC 0x%08x\n", block->pc);
 146                                 remove_from_code_lut(cache, block);
 147                                 lightrec_unregister_block(cache, block);
 148                                 lightrec_free_block(state, block);
 149                         }
 150                 }
 151         }
 152 }
 153
 154 void lightrec_remove_outdated_blocks(struct blockcache *cache,
 155                                      const struct block *except)
 156 {
 157         pr_info("Running out of code space. Cleaning block cache...\n");
 158
 159         lightrec_free_blocks(cache, except, false);
 160 }
 161
 162 void lightrec_free_block_cache(struct blockcache *cache)
 163 {
 164         lightrec_free_blocks(cache, NULL, true);
 165         lightrec_free(cache->state, MEM_FOR_LIGHTREC, sizeof(*cache), cache);
 166 }
 167
 168 struct blockcache * lightrec_blockcache_init(struct lightrec_state *state)
 169 {
 170         struct blockcache *cache;
 171
 172         cache = lightrec_calloc(state, MEM_FOR_LIGHTREC, sizeof(*cache));
 173         if (!cache)
 174                 return NULL;
 175
 176         cache->state = state;
 177
 178         return cache;
 179 }
 180
 181 u32 lightrec_calculate_block_hash(const struct block *block)
 182 {
 183         const u32 *code = block->code;
 184         u32 hash = 0xffffffff;
 185         unsigned int i;
 186
 187         /* Jenkins one-at-a-time hash algorithm */
 188         for (i = 0; i < block->nb_ops; i++) {
 189                 hash += *code++;
 190                 hash += (hash << 10);
 191                 hash ^= (hash >> 6);
 192         }
 193
 194         hash += (hash << 3);
 195         hash ^= (hash >> 11);
 196         hash += (hash << 15);
 197
 198         return hash;
 199 }
 200
 201 static void lightrec_reset_lut_offset(struct lightrec_state *state, void *d)
 202 {
 203         u32 pc = (u32)(uintptr_t) d;
 204         struct block *block;
 205         void *addr;
 206
 207         block = lightrec_find_block(state->block_cache, pc);
 208         if (!block)
 209                 return;
 210
 211         if (block_has_flag(block, BLOCK_IS_DEAD))
 212                 return;
 213
 214         addr = block->function ?: state->get_next_block;
 215         lut_write(state, lut_offset(pc), addr);
 216 }
 217
 218 bool lightrec_block_is_outdated(struct lightrec_state *state, struct block *block)
 219 {
 220         u32 offset = lut_offset(block->pc);
 221         bool outdated;
 222
 223         if (lut_read(state, offset))
 224                 return false;
 225
 226         outdated = block->hash != lightrec_calculate_block_hash(block);
 227         if (likely(!outdated)) {
 228                 /* The block was marked as outdated, but the content is still
 229                  * the same */
 230
 231                 if (ENABLE_THREADED_COMPILER) {
 232                         /*
 233                          * When compiling a block that covers ours, the threaded
 234                          * compiler will set the LUT entries of the various
 235                          * entry points. Therefore we cannot write the LUT here,
 236                          * as we would risk overwriting the new entry points.
 237                          * Leave it to the reaper to re-install the LUT entries.
 238                          */
 239
 240                         lightrec_reaper_add(state->reaper,
 241                                             lightrec_reset_lut_offset,
 242                                             (void *)(uintptr_t) block->pc);
 243                 } else if (block->function) {
 244                         lut_write(state, offset, block->function);
 245                 } else {
 246                         lut_write(state, offset, state->get_next_block);
 247                 }
 248         }
 249
 250         return outdated;
 251 }