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_FMT" 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_FMT"\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_all_blocks(struct blockcache *cache)
 163 {
 164         lightrec_free_blocks(cache, NULL, true);
 165 }
 166
 167 void lightrec_free_block_cache(struct blockcache *cache)
 168 {
 169         lightrec_free_all_blocks(cache);
 170         lightrec_free(cache->state, MEM_FOR_LIGHTREC, sizeof(*cache), cache);
 171 }
 172
 173 struct blockcache * lightrec_blockcache_init(struct lightrec_state *state)
 174 {
 175         struct blockcache *cache;
 176
 177         cache = lightrec_calloc(state, MEM_FOR_LIGHTREC, sizeof(*cache));
 178         if (!cache)
 179                 return NULL;
 180
 181         cache->state = state;
 182
 183         return cache;
 184 }
 185
 186 u32 lightrec_calculate_block_hash(const struct block *block)
 187 {
 188         const u32 *code = block->code;
 189         u32 hash = 0xffffffff;
 190         unsigned int i;
 191
 192         /* Jenkins one-at-a-time hash algorithm */
 193         for (i = 0; i < block->nb_ops; i++) {
 194                 hash += *code++;
 195                 hash += (hash << 10);
 196                 hash ^= (hash >> 6);
 197         }
 198
 199         hash += (hash << 3);
 200         hash ^= (hash >> 11);
 201         hash += (hash << 15);
 202
 203         return hash;
 204 }
 205
 206 static void lightrec_reset_lut_offset(struct lightrec_state *state, void *d)
 207 {
 208         u32 pc = (u32)(uintptr_t) d;
 209         struct block *block;
 210         void *addr;
 211
 212         block = lightrec_find_block(state->block_cache, pc);
 213         if (!block)
 214                 return;
 215
 216         if (block_has_flag(block, BLOCK_IS_DEAD))
 217                 return;
 218
 219         addr = block->function ?: state->get_next_block;
 220         lut_write(state, lut_offset(pc), addr);
 221 }
 222
 223 bool lightrec_block_is_outdated(struct lightrec_state *state, struct block *block)
 224 {
 225         u32 offset = lut_offset(block->pc);
 226         bool outdated;
 227
 228         if (lut_read(state, offset))
 229                 return false;
 230
 231         outdated = block->hash != lightrec_calculate_block_hash(block);
 232         if (likely(!outdated)) {
 233                 /* The block was marked as outdated, but the content is still
 234                  * the same */
 235
 236                 if (ENABLE_THREADED_COMPILER) {
 237                         /*
 238                          * When compiling a block that covers ours, the threaded
 239                          * compiler will set the LUT entries of the various
 240                          * entry points. Therefore we cannot write the LUT here,
 241                          * as we would risk overwriting the new entry points.
 242                          * Leave it to the reaper to re-install the LUT entries.
 243                          */
 244
 245                         lightrec_reaper_add(state->reaper,
 246                                             lightrec_reset_lut_offset,
 247                                             (void *)(uintptr_t) block->pc);
 248                 } else if (block->function) {
 249                         lut_write(state, offset, block->function);
 250                 } else {
 251                         lut_write(state, offset, state->get_next_block);
 252                 }
 253         }
 254
 255         return outdated;
 256 }