Commit | Line | Data |
---|---|---|
d16005f8 PC |
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 | ||
d16005f8 PC |
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 | ||
d16005f8 PC |
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 | } |