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_register_block(struct blockcache *cache, struct block *block)
  64 {
  65         u32 pc = kunseg(block->pc);
  66         struct block *old;
  67
  68         old = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  69         if (old)
  70                 block->next = old;
  71
  72         cache->lut[(pc >> 2) & (LUT_SIZE - 1)] = block;
  73
  74         remove_from_code_lut(cache, block);
  75 }
  76
  77 void lightrec_unregister_block(struct blockcache *cache, struct block *block)
  78 {
  79         u32 pc = kunseg(block->pc);
  80         struct block *old = cache->lut[(pc >> 2) & (LUT_SIZE - 1)];
  81
  82         if (old == block) {
  83                 cache->lut[(pc >> 2) & (LUT_SIZE - 1)] = old->next;
  84                 return;
  85         }
  86
  87         for (; old; old = old->next) {
  88                 if (old->next == block) {
  89                         old->next = block->next;
  90                         return;
  91                 }
  92         }
  93
  94         pr_err("Block at PC 0x%x is not in cache\n", block->pc);
  95 }
  96
  97 void lightrec_free_block_cache(struct blockcache *cache)
  98 {
  99         struct block *block, *next;
 100         unsigned int i;
 101
 102         for (i = 0; i < LUT_SIZE; i++) {
 103                 for (block = cache->lut[i]; block; block = next) {
 104                         next = block->next;
 105                         lightrec_free_block(block);
 106                 }
 107         }
 108
 109         lightrec_free(cache->state, MEM_FOR_LIGHTREC, sizeof(*cache), cache);
 110 }
 111
 112 struct blockcache * lightrec_blockcache_init(struct lightrec_state *state)
 113 {
 114         struct blockcache *cache;
 115
 116         cache = lightrec_calloc(state, MEM_FOR_LIGHTREC, sizeof(*cache));
 117         if (!cache)
 118                 return NULL;
 119
 120         cache->state = state;
 121
 122         return cache;
 123 }
 124
 125 u32 lightrec_calculate_block_hash(const struct block *block)
 126 {
 127         const struct lightrec_mem_map *map = block->map;
 128         u32 pc, hash = 0xffffffff;
 129         const u32 *code;
 130         unsigned int i;
 131
 132         pc = kunseg(block->pc) - map->pc;
 133
 134         while (map->mirror_of)
 135                 map = map->mirror_of;
 136
 137         code = map->address + pc;
 138
 139         /* Jenkins one-at-a-time hash algorithm */
 140         for (i = 0; i < block->nb_ops; i++) {
 141                 hash += *code++;
 142                 hash += (hash << 10);
 143                 hash ^= (hash >> 6);
 144         }
 145
 146         hash += (hash << 3);
 147         hash ^= (hash >> 11);
 148         hash += (hash << 15);
 149
 150         return hash;
 151 }
 152
 153 bool lightrec_block_is_outdated(struct block *block)
 154 {
 155         void **lut_entry = &block->state->code_lut[lut_offset(block->pc)];
 156         bool outdated;
 157
 158         if (*lut_entry)
 159                 return false;
 160
 161         outdated = block->hash != lightrec_calculate_block_hash(block);
 162         if (likely(!outdated)) {
 163                 /* The block was marked as outdated, but the content is still
 164                  * the same */
 165                 if (block->function)
 166                         *lut_entry = block->function;
 167                 else
 168                         *lut_entry = block->state->get_next_block;
 169         }
 170
 171         return outdated;
 172 }