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
  11 #include <stdbool.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14
  15 /* Must be power of two */
  16 #define LUT_SIZE 0x4000
  17
  18 struct blockcache {
  19         struct lightrec_state *state;
  20         struct block * lut[LUT_SIZE];
  21 };
  22
  23 u16 lightrec_get_lut_entry(const struct block *block)
  24 {
  25         return (kunseg(block->pc) >> 2) & (LUT_SIZE - 1);
  26 }
  27
  28 struct block * lightrec_find_block(struct blockcache *cache, u32 pc)
  29 {
  30         struct block *block;
  31
  32         pc = kunseg(pc);
  33
  34         for (block = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  35              block; block = block->next)
  36                 if (kunseg(block->pc) == pc)
  37                         return block;
  38
  39         return NULL;
  40 }
  41
  42 struct block * lightrec_find_block_from_lut(struct blockcache *cache,
  43                                             u16 lut_entry, u32 addr_in_block)
  44 {
  45         struct block *block;
  46         u32 pc;
  47
  48         addr_in_block = kunseg(addr_in_block);
  49
  50         for (block = cache->lut[lut_entry]; block; block = block->next) {
  51                 pc = kunseg(block->pc);
  52                 if (addr_in_block >= pc &&
  53                     addr_in_block < pc + (block->nb_ops << 2))
  54                         return block;
  55         }
  56
  57         return NULL;
  58 }
  59
  60 void remove_from_code_lut(struct blockcache *cache, struct block *block)
  61 {
  62         struct lightrec_state *state = cache->state;
  63         u32 offset = lut_offset(block->pc);
  64
  65         if (block->function) {
  66                 memset(lut_address(state, offset), 0,
  67                        block->nb_ops * lut_elm_size(state));
  68         }
  69 }
  70
  71 void lightrec_register_block(struct blockcache *cache, struct block *block)
  72 {
  73         u32 pc = kunseg(block->pc);
  74         struct block *old;
  75
  76         old = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  77         if (old)
  78                 block->next = old;
  79
  80         cache->lut[(pc >> 2) & (LUT_SIZE - 1)] = block;
  81
  82         remove_from_code_lut(cache, block);
  83 }
  84
  85 void lightrec_unregister_block(struct blockcache *cache, struct block *block)
  86 {
  87         u32 pc = kunseg(block->pc);
  88         struct block *old = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  89
  90         if (old == block) {
  91                 cache->lut[(pc >> 2) & (LUT_SIZE - 1)] = old->next;
  92                 return;
  93         }
  94
  95         for (; old; old = old->next) {
  96                 if (old->next == block) {
  97                         old->next = block->next;
  98                         return;
  99                 }
 100         }
 101
 102         pr_err("Block at PC 0x%x is not in cache\n", block->pc);
 103 }
 104
 105 static bool lightrec_block_is_old(const struct lightrec_state *state,
 106                                   const struct block *block)
 107 {
 108         u32 diff = state->current_cycle - block->precompile_date;
 109
 110         return diff > (1 << 27); /* About 4 seconds */
 111 }
 112
 113 static void lightrec_free_blocks(struct blockcache *cache,
 114                                  const struct block *except, bool all)
 115 {
 116         struct lightrec_state *state = cache->state;
 117         struct block *block, *next;
 118         bool outdated = all;
 119         unsigned int i;
 120
 121         for (i = 0; i < LUT_SIZE; i++) {
 122                 for (block = cache->lut[i]; block; block = next) {
 123                         next = block->next;
 124
 125                         if (except && block == except)
 126                                 continue;
 127
 128                         if (!all) {
 129                                 outdated = lightrec_block_is_old(state, block) ||
 130                                         lightrec_block_is_outdated(state, block);
 131                         }
 132
 133                         if (outdated) {
 134                                 pr_debug("Freeing outdated block at PC 0x%08x\n", block->pc);
 135                                 remove_from_code_lut(cache, block);
 136                                 lightrec_unregister_block(cache, block);
 137                                 lightrec_free_block(state, block);
 138                         }
 139                 }
 140         }
 141 }
 142
 143 void lightrec_remove_outdated_blocks(struct blockcache *cache,
 144                                      const struct block *except)
 145 {
 146         pr_info("Running out of code space. Cleaning block cache...\n");
 147
 148         lightrec_free_blocks(cache, except, false);
 149 }
 150
 151 void lightrec_free_block_cache(struct blockcache *cache)
 152 {
 153         lightrec_free_blocks(cache, NULL, true);
 154         lightrec_free(cache->state, MEM_FOR_LIGHTREC, sizeof(*cache), cache);
 155 }
 156
 157 struct blockcache * lightrec_blockcache_init(struct lightrec_state *state)
 158 {
 159         struct blockcache *cache;
 160
 161         cache = lightrec_calloc(state, MEM_FOR_LIGHTREC, sizeof(*cache));
 162         if (!cache)
 163                 return NULL;
 164
 165         cache->state = state;
 166
 167         return cache;
 168 }
 169
 170 u32 lightrec_calculate_block_hash(const struct block *block)
 171 {
 172         const u32 *code = block->code;
 173         u32 hash = 0xffffffff;
 174         unsigned int i;
 175
 176         /* Jenkins one-at-a-time hash algorithm */
 177         for (i = 0; i < block->nb_ops; i++) {
 178                 hash += *code++;
 179                 hash += (hash << 10);
 180                 hash ^= (hash >> 6);
 181         }
 182
 183         hash += (hash << 3);
 184         hash ^= (hash >> 11);
 185         hash += (hash << 15);
 186
 187         return hash;
 188 }
 189
 190 bool lightrec_block_is_outdated(struct lightrec_state *state, struct block *block)
 191 {
 192         u32 offset = lut_offset(block->pc);
 193         bool outdated;
 194         void *addr;
 195
 196         if (lut_read(state, offset))
 197                 return false;
 198
 199         outdated = block->hash != lightrec_calculate_block_hash(block);
 200         if (likely(!outdated)) {
 201                 /* The block was marked as outdated, but the content is still
 202                  * the same */
 203                 if (block->function)
 204                         addr = block->function;
 205                 else
 206                         addr = state->get_next_block;
 207
 208                 lut_write(state, offset, addr);
 209         }
 210
 211         return outdated;
 212 }