/
MVMMultiCache.h
85 lines (76 loc) · 3.7 KB
/
MVMMultiCache.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/* The multi-dispatch cache is a set of trees keyed on the address of
* an interned callsite. The tree is represented as an array of triples,
* each having the form (action, match, no-match). The match and no-match
* are either:
* * Positive, and an index into the array for what to check next
* * Zero, meaning we failed to find a match
* * Negative, meaning we found a match, and should negate the index
* to get a the resulting candidate
*
* The first MVM_MULTICACHE_HASH_SIZE entries in the array are tree roots.
* They are all set to have a NULL callsite matcher when there's no tree
* there, implying an immediate match failure.
*
* The matcher starts in callsite match mode, meaning that the matcher is
* the memory address of a callsite. This naturally handles hash collisions.
*
* Once we have a matching callsite, it flips into argument matching mode.
* The lowermost bits of the action represent the index into the arguments
* buffer for the argument we need to test. The next bit is for concrete or
* not. The bit after it is rw or not. The remaining bits correspond to the
* STable's type cache ID.
*
* The construction of the tree is such that we only have to test the first
* argument until we get a match, then the second, etc. This means that common
* prefixes are factored out, keeping the tree smaller. The use of a single
* block of memory is also aimed at getting good CPU cache hit rates.
*
* The tree array is immutable, and so can safely be read by many threads, and
* kept in thier CPU caches. Upon a new entry, the cache will be copied, and the
* tweaks made. The cache head pointer will then be set to the new cache, and the
* old cache memory scheduled for freeeing at the next safepoint.
*/
/* A node in the cache. */
struct MVMMultiCacheNode {
union {
MVMCallsite *cs;
MVMuint64 arg_match;
} action;
MVMint32 match;
MVMint32 no_match;
};
/* Body of a multi-dispatch cache. */
struct MVMMultiCacheBody {
/* Pointer to the an array of nodes, which we can initially index
* into using a hahsed calsite. Replaced in whole whenever there is
* a change. */
MVMMultiCacheNode *node_hash_head;
/* Array of results we may return from the cache. Note that this is
* replaced entirely whenever we update the cache. It is append only,
* and so will be valid for older versions of the cache too. We must
* replace this and do a memory barrier before replacing node_hash_head
* with its new version on update. Conversely, readers must read the
* node_hash_head and *then* read results here, so it will always have
* been udpated in time. */
MVMObject **results;
/* The number of results, so we can GC mark and free. */
size_t num_results;
/* The amount of memory the cache uses. Used for freeing with the fixed
* size allocator. */
size_t cache_memory_size;
};
/* Hash table size. Must be a power of 2. */
#define MVM_MULTICACHE_HASH_SIZE 8
#define MVM_MULTICACHE_HASH_FILTER (MVM_MULTICACHE_HASH_SIZE - 1)
struct MVMMultiCache {
MVMObject common;
MVMMultiCacheBody body;
};
/* Function for REPR setup. */
const MVMREPROps * MVMMultiCache_initialize(MVMThreadContext *tc);
/* Functions relating to multi-dispatch cache usage. */
MVMObject * MVM_multi_cache_add(MVMThreadContext *tc, MVMObject *cache, MVMObject *capture, MVMObject *result);
MVMObject * MVM_multi_cache_find(MVMThreadContext *tc, MVMObject *cache, MVMObject *capture);
MVMObject * MVM_multi_cache_find_callsite_args(MVMThreadContext *tc, MVMObject *cache,
MVMCallsite *cs, MVMRegister *args);
MVMObject * MVM_multi_cache_find_spesh(MVMThreadContext *tc, MVMObject *cache, MVMSpeshCallInfo *arg_info, MVMSpeshStatsType *type_tuple);