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
lightrec_find_block(struct blockcache * cache,u32 pc)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
remove_from_code_lut(struct blockcache * cache,struct block * block)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
lightrec_register_block(struct blockcache * cache,struct block * block)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
lightrec_unregister_block(struct blockcache * cache,struct block * block)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
lightrec_free_block_cache(struct blockcache * cache)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
lightrec_blockcache_init(struct lightrec_state * state)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
lightrec_calculate_block_hash(const struct block * block)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
lightrec_block_is_outdated(struct block * block)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 }
173