Branch data Line data Source code
1 : : // This file is a part of Julia. License is MIT: https://julialang.org/license
2 : :
3 : : /*
4 : : Symbol table
5 : : */
6 : :
7 : : #include <stdlib.h>
8 : : #include <string.h>
9 : : #include <stdarg.h>
10 : : #include "julia.h"
11 : : #include "julia_internal.h"
12 : : #include "julia_assert.h"
13 : :
14 : : #ifdef __cplusplus
15 : : extern "C" {
16 : : #endif
17 : :
18 : : static _Atomic(jl_sym_t*) symtab = NULL;
19 : :
20 : : #define MAX_SYM_LEN ((size_t)INTPTR_MAX - sizeof(jl_taggedvalue_t) - sizeof(jl_sym_t) - 1)
21 : :
22 : 109865000 : static uintptr_t hash_symbol(const char *str, size_t len) JL_NOTSAFEPOINT
23 : : {
24 : 109865000 : uintptr_t oid = memhash(str, len) ^ ~(uintptr_t)0/3*2;
25 : : // compute the same hash value as v1.6 and earlier, which used `hash_uint(3h - objectid(sym))`
26 : 109867000 : return inthash(-oid);
27 : : }
28 : :
29 : 15591500 : static size_t symbol_nbytes(size_t len) JL_NOTSAFEPOINT
30 : : {
31 : 15591500 : return (sizeof(jl_taggedvalue_t) + sizeof(jl_sym_t) + len + 1 + 7) & -8;
32 : : }
33 : :
34 : 15591500 : static jl_sym_t *mk_symbol(const char *str, size_t len) JL_NOTSAFEPOINT
35 : : {
36 : : jl_sym_t *sym;
37 : 15591500 : size_t nb = symbol_nbytes(len);
38 [ - + ]: 15591500 : assert(jl_symbol_type && "not initialized");
39 : :
40 : 15591500 : jl_taggedvalue_t *tag = (jl_taggedvalue_t*)jl_gc_perm_alloc_nolock(nb, 0, sizeof(void*), 0);
41 : 15591500 : sym = (jl_sym_t*)jl_valueof(tag);
42 : : // set to old marked so that we won't look at it in the GC or write barrier.
43 : 15591500 : tag->header = ((uintptr_t)jl_symbol_type) | GC_OLD_MARKED;
44 : 15591500 : jl_atomic_store_relaxed(&sym->left, NULL);
45 : 15591500 : jl_atomic_store_relaxed(&sym->right, NULL);
46 : 15591500 : sym->hash = hash_symbol(str, len);
47 : 15591500 : memcpy(jl_symbol_name(sym), str, len);
48 : 15591500 : jl_symbol_name(sym)[len] = 0;
49 : 15591500 : return sym;
50 : : }
51 : :
52 : 94273600 : static jl_sym_t *symtab_lookup(_Atomic(jl_sym_t*) *ptree, const char *str, size_t len, _Atomic(jl_sym_t*) **slot) JL_NOTSAFEPOINT
53 : : {
54 : 94273600 : jl_sym_t *node = jl_atomic_load_relaxed(ptree); // consume
55 : 94273600 : uintptr_t h = hash_symbol(str, len);
56 : :
57 : : // Tree nodes sorted by major key of (int(hash)) and minor key of (str).
58 [ + + ]: 1628890000 : while (node != NULL) {
59 : 1613290000 : intptr_t x = (intptr_t)(h - node->hash);
60 [ + + ]: 1613290000 : if (x == 0) {
61 : 78681900 : x = strncmp(str, jl_symbol_name(node), len);
62 [ + + + # ]: 78681900 : if (x == 0 && jl_symbol_name(node)[len] == 0) {
63 [ + + ]: 78681500 : if (slot != NULL)
64 : 78681500 : *slot = ptree;
65 : 78681500 : return node;
66 : : }
67 : : }
68 [ + + ]: 1534620000 : if (x < 0)
69 : 809654000 : ptree = &node->left;
70 : : else
71 : 724966000 : ptree = &node->right;
72 : 1534620000 : node = jl_atomic_load_relaxed(ptree); // consume
73 : : }
74 [ + + ]: 15601400 : if (slot != NULL)
75 : 15591500 : *slot = ptree;
76 : 15601400 : return node;
77 : : }
78 : :
79 : 94273600 : jl_sym_t *_jl_symbol(const char *str, size_t len) JL_NOTSAFEPOINT // (or throw)
80 : : {
81 : : #ifndef __clang_gcanalyzer__
82 : : // Hide the error throwing from the analyser since there isn't a way to express
83 : : // "safepoint only when throwing error" currently.
84 [ - + ]: 94273600 : if (len > MAX_SYM_LEN)
85 : 0 : jl_exceptionf(jl_argumenterror_type, "Symbol name too long");
86 : : #endif
87 [ - + ]: 94273600 : assert(!memchr(str, 0, len));
88 : : _Atomic(jl_sym_t*) *slot;
89 : 94273600 : jl_sym_t *node = symtab_lookup(&symtab, str, len, &slot);
90 [ + + ]: 94273000 : if (node == NULL) {
91 : 15591500 : uv_mutex_lock(&gc_perm_lock);
92 : : // Someone might have updated it, check and look up again
93 [ - + - - ]: 15591500 : if (jl_atomic_load_relaxed(slot) != NULL && (node = symtab_lookup(slot, str, len, &slot))) {
94 : 0 : uv_mutex_unlock(&gc_perm_lock);
95 : 0 : return node;
96 : : }
97 : 15591500 : node = mk_symbol(str, len);
98 : 15591500 : jl_atomic_store_release(slot, node);
99 : 15591500 : uv_mutex_unlock(&gc_perm_lock);
100 : : }
101 : 94273000 : return node;
102 : : }
103 : :
104 : 27724200 : JL_DLLEXPORT jl_sym_t *jl_symbol(const char *str) JL_NOTSAFEPOINT // (or throw)
105 : : {
106 : 27724200 : return _jl_symbol(str, strlen(str));
107 : : }
108 : :
109 : 0 : JL_DLLEXPORT jl_sym_t *jl_symbol_lookup(const char *str) JL_NOTSAFEPOINT
110 : : {
111 : 0 : return symtab_lookup(&symtab, str, strlen(str), NULL);
112 : : }
113 : :
114 : 414351 : JL_DLLEXPORT jl_sym_t *jl_symbol_n(const char *str, size_t len)
115 : : {
116 [ + + ]: 414351 : if (memchr(str, 0, len))
117 : 1 : jl_exceptionf(jl_argumenterror_type, "Symbol name may not contain \\0");
118 : 414350 : return _jl_symbol(str, len);
119 : : }
120 : :
121 : 3 : JL_DLLEXPORT jl_sym_t *jl_get_root_symbol(void)
122 : : {
123 : 3 : return jl_atomic_load_relaxed(&symtab);
124 : : }
125 : :
126 : : static _Atomic(uint32_t) gs_ctr = 0; // TODO: per-module?
127 : 3 : uint32_t jl_get_gs_ctr(void) { return jl_atomic_load_relaxed(&gs_ctr); }
128 : 566 : void jl_set_gs_ctr(uint32_t ctr) { jl_atomic_store_relaxed(&gs_ctr, ctr); }
129 : :
130 : 421 : JL_DLLEXPORT jl_sym_t *jl_gensym(void)
131 : : {
132 : : char name[16];
133 : : char *n;
134 : 421 : uint32_t ctr = jl_atomic_fetch_add(&gs_ctr, 1);
135 : 421 : n = uint2str(&name[2], sizeof(name)-2, ctr, 10);
136 : 421 : *(--n) = '#'; *(--n) = '#';
137 : 421 : return jl_symbol(n);
138 : : }
139 : :
140 : 545 : JL_DLLEXPORT jl_sym_t *jl_tagged_gensym(const char *str, size_t len)
141 : : {
142 [ + + ]: 545 : if (len == (size_t)-1) {
143 : 33 : len = strlen(str);
144 : : }
145 [ + + ]: 512 : else if (memchr(str, 0, len)) {
146 : 1 : jl_exceptionf(jl_argumenterror_type, "Symbol name may not contain \\0");
147 : : }
148 : : char gs_name[14];
149 : 544 : size_t alloc_len = sizeof(gs_name) + len + 3;
150 [ + - - + ]: 544 : if (len > MAX_SYM_LEN || alloc_len > MAX_SYM_LEN)
151 : 0 : jl_exceptionf(jl_argumenterror_type, "Symbol name too long");
152 [ - + ]: 544 : char *name = (char*)(len >= 256 ? malloc_s(alloc_len) : alloca(alloc_len));
153 : : char *n;
154 : 544 : name[0] = '#';
155 : 544 : name[1] = '#';
156 : 544 : name[2 + len] = '#';
157 : 544 : memcpy(name + 2, str, len);
158 : 544 : uint32_t ctr = jl_atomic_fetch_add(&gs_ctr, 1);
159 : 544 : n = uint2str(gs_name, sizeof(gs_name), ctr, 10);
160 : 544 : memcpy(name + 3 + len, n, sizeof(gs_name) - (n - gs_name));
161 : 544 : jl_sym_t *sym = _jl_symbol(name, alloc_len - (n - gs_name)- 1);
162 [ - + ]: 544 : if (len >= 256)
163 : 0 : free(name);
164 : 544 : return sym;
165 : : }
166 : :
167 : : #ifdef __cplusplus
168 : : }
169 : : #endif
|
