deps/lightrec/blockcache.c

   1 /*
   2  * Copyright (C) 2015-2020 Paul Cercueil <paul@crapouillou.net>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Lesser General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2.1 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Lesser General Public License for more details.
  13  */
  14
  15 #include "blockcache.h"
  16 #include "debug.h"
  17 #include "lightrec-private.h"
  18 #include "memmanager.h"
  19
  20 #include <stdbool.h>
  21 #include <stdlib.h>
  22
  23 /* Must be power of two */
  24 #define LUT_SIZE 0x4000
  25
  26 struct blockcache {
  27         struct lightrec_state *state;
  28         struct block * lut[LUT_SIZE];
  29 };
  30
  31 struct block * lightrec_find_block(struct blockcache *cache, u32 pc)
  32 {
  33         struct block *block;
  34
  35         pc = kunseg(pc);
  36
  37         for (block = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  38              block; block = block->next)
  39                 if (kunseg(block->pc) == pc)
  40                         return block;
  41
  42         return NULL;
  43 }
  44
  45 void remove_from_code_lut(struct blockcache *cache, struct block *block)
  46 {
  47         struct lightrec_state *state = block->state;
  48         const struct opcode *op;
  49         u32 offset = lut_offset(block->pc);
  50
  51         /* Use state->get_next_block in the code LUT, which basically
  52          * calls back get_next_block_func(), until the compiler
  53          * overrides this. This is required, as a NULL value in the code
  54          * LUT means an outdated block. */
  55         state->code_lut[offset] = state->get_next_block;
  56
  57         for (op = block->opcode_list; op; op = op->next)
  58                 if (op->c.i.op == OP_META_SYNC)
  59                         state->code_lut[offset + op->offset] = NULL;
  60
  61 }
  62
  63 void lightrec_mark_for_recompilation(struct blockcache *cache,
  64                                      struct block *block)
  65 {
  66         block->flags |= BLOCK_SHOULD_RECOMPILE;
  67 }
  68
  69 void lightrec_register_block(struct blockcache *cache, struct block *block)
  70 {
  71         u32 pc = kunseg(block->pc);
  72         struct block *old;
  73
  74         old = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  75         if (old)
  76                 block->next = old;
  77
  78         cache->lut[(pc >> 2) & (LUT_SIZE - 1)] = block;
  79
  80         remove_from_code_lut(cache, block);
  81 }
  82
  83 void lightrec_unregister_block(struct blockcache *cache, struct block *block)
  84 {
  85         u32 pc = kunseg(block->pc);
  86         struct block *old = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  87
  88         remove_from_code_lut(cache, block);
  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 void lightrec_free_block_cache(struct blockcache *cache)
 106 {
 107         struct block *block, *next;
 108         unsigned int i;
 109
 110         for (i = 0; i < LUT_SIZE; i++) {
 111                 for (block = cache->lut[i]; block; block = next) {
 112                         next = block->next;
 113                         lightrec_free_block(block);
 114                 }
 115         }
 116
 117         lightrec_free(cache->state, MEM_FOR_LIGHTREC, sizeof(*cache), cache);
 118 }
 119
 120 struct blockcache * lightrec_blockcache_init(struct lightrec_state *state)
 121 {
 122         struct blockcache *cache;
 123
 124         cache = lightrec_calloc(state, MEM_FOR_LIGHTREC, sizeof(*cache));
 125         if (!cache)
 126                 return NULL;
 127
 128         cache->state = state;
 129
 130         return cache;
 131 }
 132
 133 u32 lightrec_calculate_block_hash(const struct block *block)
 134 {
 135         const struct lightrec_mem_map *map = block->map;
 136         u32 pc, hash = 0xffffffff;
 137         const u32 *code;
 138         unsigned int i;
 139
 140         pc = kunseg(block->pc) - map->pc;
 141
 142         while (map->mirror_of)
 143                 map = map->mirror_of;
 144
 145         code = map->address + pc;
 146
 147         /* Jenkins one-at-a-time hash algorithm */
 148         for (i = 0; i < block->nb_ops; i++) {
 149                 hash += *code++;
 150                 hash += (hash << 10);
 151                 hash ^= (hash >> 6);
 152         }
 153
 154         hash += (hash << 3);
 155         hash ^= (hash >> 11);
 156         hash += (hash << 15);
 157
 158         return hash;
 159 }
 160
 161 bool lightrec_block_is_outdated(struct block *block)
 162 {
 163         void **lut_entry = &block->state->code_lut[lut_offset(block->pc)];
 164         bool outdated;
 165
 166         if (*lut_entry)
 167                 return false;
 168
 169         outdated = block->hash != lightrec_calculate_block_hash(block);
 170         if (likely(!outdated)) {
 171                 /* The block was marked as outdated, but the content is still
 172                  * the same */
 173                 if (block->function)
 174                         *lut_entry = block->function;
 175                 else
 176                         *lut_entry = block->state->get_next_block;
 177         }
 178
 179         return outdated;
 180 }