1 /*
2 * %CopyrightBegin%
3 *
4 * Copyright Ericsson AB 2003-2017. All Rights Reserved.
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * %CopyrightEnd%
19 */
20
21
22 #ifdef HAVE_CONFIG_H
23 #include "config.h"
24 #endif
25 #include "global.h"
26
27 #include "hipe_stack.h"
28
29 /*
30 * Native-code stack descriptor hash table.
31 *
32 * This uses a specialised version of BEAM's hash table code:
33 * - Hash table size is always a power of two.
34 * Permits replacing an expensive integer division operation
35 * with a cheap bitwise 'and' in the hash index calculation
36 * - Lookups assume the key is in the table.
37 * Permits removing NULL checks.
38 * - Switched order of the hash bucket next and hvalue fields.
39 * The hvalue field, which must always be checked, gets a zero
40 * structure offset, which is faster on some architectures;
41 * the next field is only referenced if hvalue didn't match.
42 * These changes yield a much more efficient lookup operation.
43 */
44 struct hipe_sdesc_table hipe_sdesc_table;
45
alloc_bucket(unsigned int size)46 static struct hipe_sdesc **alloc_bucket(unsigned int size)
47 {
48 unsigned long nbytes = size * sizeof(struct hipe_sdesc*);
49 struct hipe_sdesc **bucket = erts_alloc(ERTS_ALC_T_HIPE_LL, nbytes);
50 sys_memzero(bucket, nbytes);
51 return bucket;
52 }
53
hipe_grow_sdesc_table(void)54 static void hipe_grow_sdesc_table(void)
55 {
56 unsigned int old_size, new_size, new_mask;
57 struct hipe_sdesc **old_bucket, **new_bucket;
58 unsigned int i;
59
60 old_size = 1 << hipe_sdesc_table.log2size;
61 hipe_sdesc_table.log2size += 1;
62 new_size = 1 << hipe_sdesc_table.log2size;
63 new_mask = new_size - 1;
64 hipe_sdesc_table.mask = new_mask;
65 old_bucket = hipe_sdesc_table.bucket;
66 new_bucket = alloc_bucket(new_size);
67 hipe_sdesc_table.bucket = new_bucket;
68 for (i = 0; i < old_size; ++i) {
69 struct hipe_sdesc *b = old_bucket[i];
70 while (b != NULL) {
71 struct hipe_sdesc *next = b->bucket.next;
72 unsigned int j = (b->bucket.hvalue >> HIPE_RA_LSR_COUNT) & new_mask;
73 b->bucket.next = new_bucket[j];
74 new_bucket[j] = b;
75 b = next;
76 }
77 }
78 erts_free(ERTS_ALC_T_HIPE_LL, old_bucket);
79 }
80
hipe_put_sdesc(struct hipe_sdesc * sdesc)81 struct hipe_sdesc *hipe_put_sdesc(struct hipe_sdesc *sdesc)
82 {
83 unsigned long ra;
84 unsigned int i;
85 struct hipe_sdesc *chain;
86 unsigned int size;
87
88 ra = sdesc->bucket.hvalue;
89 i = (ra >> HIPE_RA_LSR_COUNT) & hipe_sdesc_table.mask;
90 chain = hipe_sdesc_table.bucket[i];
91
92 for (; chain != NULL; chain = chain->bucket.next)
93 if (chain->bucket.hvalue == ra)
94 return chain; /* collision! (shouldn't happen) */
95
96 sdesc->bucket.next = hipe_sdesc_table.bucket[i];
97 hipe_sdesc_table.bucket[i] = sdesc;
98 hipe_sdesc_table.used += 1;
99 size = 1 << hipe_sdesc_table.log2size;
100 if (hipe_sdesc_table.used > (4*size)/5) /* rehash at 80% */
101 hipe_grow_sdesc_table();
102 return sdesc;
103 }
104
hipe_destruct_sdesc(struct hipe_sdesc * sdesc)105 void hipe_destruct_sdesc(struct hipe_sdesc *sdesc)
106 {
107 unsigned int i;
108 struct hipe_sdesc** prevp;
109 void* free_me;
110
111 i = (sdesc->bucket.hvalue >> HIPE_RA_LSR_COUNT) & hipe_sdesc_table.mask;
112 prevp = &hipe_sdesc_table.bucket[i];
113
114 for (; *prevp != sdesc; prevp = &(*prevp)->bucket.next)
115 ASSERT(*prevp);
116
117 *prevp = sdesc->bucket.next;
118 hipe_sdesc_table.used -= 1;
119
120 if (sdesc->has_exnra)
121 free_me = ErtsContainerStruct(sdesc, struct hipe_sdesc_with_exnra, sdesc);
122 else
123 free_me = sdesc;
124 erts_free(ERTS_ALC_T_HIPE_LL, free_me);
125 }
126
hipe_init_sdesc_table(struct hipe_sdesc * sdesc)127 void hipe_init_sdesc_table(struct hipe_sdesc *sdesc)
128 {
129 unsigned int log2size, size;
130
131 log2size = 10;
132 size = 1 << log2size;
133 hipe_sdesc_table.log2size = log2size;
134 hipe_sdesc_table.mask = size - 1;
135 hipe_sdesc_table.used = 0;
136 hipe_sdesc_table.bucket = alloc_bucket(size);
137
138 hipe_put_sdesc(sdesc);
139 }
140
141 /*
142 * XXX: x86 and SPARC currently use the same stack descriptor
143 * representation. If different representations are needed in
144 * the future, this code has to be made target dependent.
145 */
hipe_decode_sdesc(Eterm arg)146 struct hipe_sdesc *hipe_decode_sdesc(Eterm arg)
147 {
148 Uint ra, exnra;
149 Eterm *live;
150 Uint fsize, nargs, stk_nargs, nlive, i, nslots, off;
151 Uint livebitswords, sdescbytes;
152 void *p;
153 struct hipe_sdesc *sdesc;
154 Eterm* mfa_tpl;
155 Eterm* tp;
156
157 if (is_not_tuple(arg))
158 return 0;
159
160 tp = tuple_val(arg);
161 if (tp[0] != make_arityval(6) ||
162 term_to_Uint(tp[1], &ra) == 0 ||
163 term_to_Uint(tp[2], &exnra) == 0 ||
164 is_not_small(tp[3]) ||
165 (fsize = unsigned_val(tp[3])) > 65535 ||
166 is_not_small(tp[4]) ||
167 (stk_nargs = unsigned_val(tp[4])) > 255 ||
168 is_not_tuple(tp[5]) ||
169 is_not_tuple(tp[6]) ||
170 (mfa_tpl = tuple_val(tp[6]))[0] != make_arityval(3) ||
171 is_not_atom(mfa_tpl[1]) ||
172 is_not_atom(mfa_tpl[2]) ||
173 is_not_small(mfa_tpl[3]) ||
174 (nargs = unsigned_val(mfa_tpl[3])) > 255)
175 return 0;
176
177 if (stk_nargs > nargs)
178 return 0;
179
180 /* Get tuple with live slots */
181 live = tuple_val(tp[5]) + 1;
182 /* Get number of live slots */
183 nlive = arityval(live[-1]);
184 /* Calculate size of frame = locals + ra + stack arguments */
185 nslots = fsize + 1 + stk_nargs;
186 /* Check that only valid slots are given. */
187 for (i = 0; i < nlive; ++i) {
188 if (is_not_small(live[i]) ||
189 (off = unsigned_val(live[i]), off >= nslots) ||
190 off == fsize)
191 return 0;
192 }
193
194 /* Calculate number of words for the live bitmap. */
195 livebitswords = (fsize + stk_nargs + 1 + 31) / 32;
196 /* Calculate number of bytes needed for the stack descriptor. */
197 sdescbytes =
198 (exnra
199 ? offsetof(struct hipe_sdesc_with_exnra, sdesc.livebits)
200 : offsetof(struct hipe_sdesc, livebits))
201 + livebitswords * sizeof(int);
202 p = erts_alloc(ERTS_ALC_T_HIPE_LL, sdescbytes);
203 /* If we have an exception handler use the
204 special sdesc_with_exnra structure. */
205 if (exnra) {
206 struct hipe_sdesc_with_exnra *sdesc_we = p;
207 sdesc_we->exnra = exnra;
208 sdesc = &(sdesc_we->sdesc);
209 } else
210 sdesc = p;
211
212 sdesc->m_aix = atom_val(mfa_tpl[1]);
213 sdesc->f_aix = atom_val(mfa_tpl[2]);
214 sdesc->a = nargs;
215
216
217 /* Initialise head of sdesc. */
218 sdesc->bucket.next = 0;
219 sdesc->bucket.hvalue = ra;
220 sdesc->fsize = fsize;
221 sdesc->has_exnra = (exnra ? 1 : 0);
222 sdesc->stk_nargs = stk_nargs;
223 /* Clear all live-bits */
224 for (i = 0; i < livebitswords; ++i)
225 sdesc->livebits[i] = 0;
226 /* Set live-bits given by caller. */
227 for (i = 0; i < nlive; ++i) {
228 off = unsigned_val(live[i]);
229 sdesc->livebits[off / 32] |= (1 << (off & 31));
230 }
231 return sdesc;
232 }
233