Branch data Line data Source code
1 : : /*
2 : : * This file is part of the MicroPython project, http://micropython.org/
3 : : *
4 : : * The MIT License (MIT)
5 : : *
6 : : * Copyright (c) 2013, 2014 Damien P. George
7 : : *
8 : : * Permission is hereby granted, free of charge, to any person obtaining a copy
9 : : * of this software and associated documentation files (the "Software"), to deal
10 : : * in the Software without restriction, including without limitation the rights
11 : : * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 : : * copies of the Software, and to permit persons to whom the Software is
13 : : * furnished to do so, subject to the following conditions:
14 : : *
15 : : * The above copyright notice and this permission notice shall be included in
16 : : * all copies or substantial portions of the Software.
17 : : *
18 : : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 : : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 : : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 : : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 : : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 : : * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24 : : * THE SOFTWARE.
25 : : */
26 : :
27 : : #include <assert.h>
28 : : #include <string.h>
29 : : #include <stdio.h>
30 : :
31 : : #include "py/mpstate.h"
32 : : #include "py/qstr.h"
33 : : #include "py/gc.h"
34 : : #include "py/runtime.h"
35 : :
36 : : // NOTE: we are using linear arrays to store and search for qstr's (unique strings, interned strings)
37 : : // ultimately we will replace this with a static hash table of some kind
38 : :
39 : : #if MICROPY_DEBUG_VERBOSE // print debugging info
40 : : #define DEBUG_printf DEBUG_printf
41 : : #else // don't print debugging info
42 : : #define DEBUG_printf(...) (void)0
43 : : #endif
44 : :
45 : : // A qstr is an index into the qstr pool.
46 : : // The data for a qstr is \0 terminated (so they can be printed using printf)
47 : :
48 : : #define Q_HASH_MASK ((1 << (8 * MICROPY_QSTR_BYTES_IN_HASH)) - 1)
49 : :
50 : : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
51 : : #define QSTR_ENTER() mp_thread_mutex_lock(&MP_STATE_VM(qstr_mutex), 1)
52 : : #define QSTR_EXIT() mp_thread_mutex_unlock(&MP_STATE_VM(qstr_mutex))
53 : : #else
54 : : #define QSTR_ENTER()
55 : : #define QSTR_EXIT()
56 : : #endif
57 : :
58 : : // Initial number of entries for qstr pool, set so that the first dynamically
59 : : // allocated pool is twice this size. The value here must be <= MP_QSTRnumber_of.
60 : : #define MICROPY_ALLOC_QSTR_ENTRIES_INIT (10)
61 : :
62 : : // this must match the equivalent function in makeqstrdata.py
63 : 806825 : size_t qstr_compute_hash(const byte *data, size_t len) {
64 : : // djb2 algorithm; see http://www.cse.yorku.ca/~oz/hash.html
65 : 806825 : size_t hash = 5381;
66 [ + + ]: 11994154 : for (const byte *top = data + len; data < top; data++) {
67 : 11187329 : hash = ((hash << 5) + hash) ^ (*data); // hash * 33 ^ data
68 : : }
69 : 806825 : hash &= Q_HASH_MASK;
70 : : // Make sure that valid hash is never zero, zero means "hash not computed"
71 [ + + ]: 806825 : if (hash == 0) {
72 : 13 : hash++;
73 : : }
74 : 806825 : return hash;
75 : : }
76 : :
77 : : const qstr_hash_t mp_qstr_const_hashes[] = {
78 : : #ifndef NO_QSTR
79 : : #define QDEF(id, hash, len, str) hash,
80 : : #include "genhdr/qstrdefs.generated.h"
81 : : #undef QDEF
82 : : #endif
83 : : };
84 : :
85 : : const qstr_len_t mp_qstr_const_lengths[] = {
86 : : #ifndef NO_QSTR
87 : : #define QDEF(id, hash, len, str) len,
88 : : #include "genhdr/qstrdefs.generated.h"
89 : : #undef QDEF
90 : : #endif
91 : : };
92 : :
93 : : const qstr_pool_t mp_qstr_const_pool = {
94 : : NULL, // no previous pool
95 : : 0, // no previous pool
96 : : MICROPY_ALLOC_QSTR_ENTRIES_INIT,
97 : : MP_QSTRnumber_of, // corresponds to number of strings in array just below
98 : : (qstr_hash_t *)mp_qstr_const_hashes,
99 : : (qstr_len_t *)mp_qstr_const_lengths,
100 : : {
101 : : #ifndef NO_QSTR
102 : : #define QDEF(id, hash, len, str) str,
103 : : #include "genhdr/qstrdefs.generated.h"
104 : : #undef QDEF
105 : : #endif
106 : : },
107 : : };
108 : :
109 : : #ifdef MICROPY_QSTR_EXTRA_POOL
110 : : extern const qstr_pool_t MICROPY_QSTR_EXTRA_POOL;
111 : : #define CONST_POOL MICROPY_QSTR_EXTRA_POOL
112 : : #else
113 : : #define CONST_POOL mp_qstr_const_pool
114 : : #endif
115 : :
116 : 3224 : void qstr_init(void) {
117 : 3224 : MP_STATE_VM(last_pool) = (qstr_pool_t *)&CONST_POOL; // we won't modify the const_pool since it has no allocated room left
118 : 3224 : MP_STATE_VM(qstr_last_chunk) = NULL;
119 : :
120 : : #if MICROPY_PY_THREAD && !MICROPY_PY_THREAD_GIL
121 : 3224 : mp_thread_mutex_init(&MP_STATE_VM(qstr_mutex));
122 : : #endif
123 : 3224 : }
124 : :
125 : 3228446 : STATIC const qstr_pool_t *find_qstr(qstr *q) {
126 : : // search pool for this qstr
127 : : // total_prev_len==0 in the final pool, so the loop will always terminate
128 : 3228446 : const qstr_pool_t *pool = MP_STATE_VM(last_pool);
129 [ + + ]: 10111308 : while (*q < pool->total_prev_len) {
130 : 6882862 : pool = pool->prev;
131 : : }
132 : 3228446 : *q -= pool->total_prev_len;
133 [ - + ]: 3228446 : assert(*q < pool->len);
134 : 3228446 : return pool;
135 : : }
136 : :
137 : : // qstr_mutex must be taken while in this function
138 : 34719 : STATIC qstr qstr_add(mp_uint_t hash, mp_uint_t len, const char *q_ptr) {
139 : 34719 : DEBUG_printf("QSTR: add hash=%d len=%d data=%.*s\n", hash, len, len, q_ptr);
140 : :
141 : : // make sure we have room in the pool for a new qstr
142 [ + + ]: 34719 : if (MP_STATE_VM(last_pool)->len >= MP_STATE_VM(last_pool)->alloc) {
143 : 3568 : size_t new_alloc = MP_STATE_VM(last_pool)->alloc * 2;
144 : : #ifdef MICROPY_QSTR_EXTRA_POOL
145 : : // Put a lower bound on the allocation size in case the extra qstr pool has few entries
146 : 3568 : new_alloc = MAX(MICROPY_ALLOC_QSTR_ENTRIES_INIT, new_alloc);
147 : : #endif
148 : 3568 : mp_uint_t pool_size = sizeof(qstr_pool_t)
149 : 3568 : + (sizeof(const char *) + sizeof(qstr_hash_t) + sizeof(qstr_len_t)) * new_alloc;
150 : 3568 : qstr_pool_t *pool = (qstr_pool_t *)m_malloc_maybe(pool_size);
151 [ - + ]: 3568 : if (pool == NULL) {
152 : : // Keep qstr_last_chunk consistent with qstr_pool_t: qstr_last_chunk is not scanned
153 : : // at garbage collection since it's reachable from a qstr_pool_t. And the caller of
154 : : // this function expects q_ptr to be stored in a qstr_pool_t so it can be reached
155 : : // by the collector. If qstr_pool_t allocation failed, qstr_last_chunk needs to be
156 : : // NULL'd. Otherwise it may become a dangling pointer at the next garbage collection.
157 : 0 : MP_STATE_VM(qstr_last_chunk) = NULL;
158 : 0 : QSTR_EXIT();
159 : 0 : m_malloc_fail(new_alloc);
160 : : }
161 : 3568 : pool->hashes = (qstr_hash_t *)(pool->qstrs + new_alloc);
162 : 3568 : pool->lengths = (qstr_len_t *)(pool->hashes + new_alloc);
163 : 3568 : pool->prev = MP_STATE_VM(last_pool);
164 : 3568 : pool->total_prev_len = MP_STATE_VM(last_pool)->total_prev_len + MP_STATE_VM(last_pool)->len;
165 : 3568 : pool->alloc = new_alloc;
166 : 3568 : pool->len = 0;
167 : 3568 : MP_STATE_VM(last_pool) = pool;
168 : 34719 : DEBUG_printf("QSTR: allocate new pool of size %d\n", MP_STATE_VM(last_pool)->alloc);
169 : : }
170 : :
171 : : // add the new qstr
172 : 34719 : mp_uint_t at = MP_STATE_VM(last_pool)->len;
173 : 34719 : MP_STATE_VM(last_pool)->hashes[at] = hash;
174 : 34719 : MP_STATE_VM(last_pool)->lengths[at] = len;
175 : 34719 : MP_STATE_VM(last_pool)->qstrs[at] = q_ptr;
176 : 34719 : MP_STATE_VM(last_pool)->len++;
177 : :
178 : : // return id for the newly-added qstr
179 : 34719 : return MP_STATE_VM(last_pool)->total_prev_len + at;
180 : : }
181 : :
182 : 479226 : qstr qstr_find_strn(const char *str, size_t str_len) {
183 : : // work out hash of str
184 : 479226 : size_t str_hash = qstr_compute_hash((const byte *)str, str_len);
185 : :
186 : : // search pools for the data
187 [ + + ]: 1712262 : for (const qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL; pool = pool->prev) {
188 [ + + ]: 284172569 : for (mp_uint_t at = 0, top = pool->len; at < top; at++) {
189 [ + + + + ]: 282939533 : if (pool->hashes[at] == str_hash && pool->lengths[at] == str_len
190 [ + + ]: 159750 : && memcmp(pool->qstrs[at], str, str_len) == 0) {
191 : 159665 : return pool->total_prev_len + at;
192 : : }
193 : : }
194 : : }
195 : :
196 : : // not found; return null qstr
197 : : return 0;
198 : : }
199 : :
200 : 6633 : qstr qstr_from_str(const char *str) {
201 : 6633 : return qstr_from_strn(str, strlen(str));
202 : : }
203 : :
204 : 180037 : qstr qstr_from_strn(const char *str, size_t len) {
205 : 180037 : QSTR_ENTER();
206 : 180037 : qstr q = qstr_find_strn(str, len);
207 [ + + ]: 180037 : if (q == 0) {
208 : : // qstr does not exist in interned pool so need to add it
209 : :
210 : : // check that len is not too big
211 [ + + ]: 34771 : if (len >= (1 << (8 * MICROPY_QSTR_BYTES_IN_LEN))) {
212 : 52 : QSTR_EXIT();
213 : 52 : mp_raise_msg(&mp_type_RuntimeError, MP_ERROR_TEXT("name too long"));
214 : : }
215 : :
216 : : // compute number of bytes needed to intern this string
217 : 34719 : size_t n_bytes = len + 1;
218 : :
219 [ + + + + ]: 34719 : if (MP_STATE_VM(qstr_last_chunk) != NULL && MP_STATE_VM(qstr_last_used) + n_bytes > MP_STATE_VM(qstr_last_alloc)) {
220 : : // not enough room at end of previously interned string so try to grow
221 : 2849 : char *new_p = m_renew_maybe(char, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_alloc) + n_bytes, false);
222 [ + + ]: 2849 : if (new_p == NULL) {
223 : : // could not grow existing memory; shrink it to fit previous
224 : 2355 : (void)m_renew_maybe(char, MP_STATE_VM(qstr_last_chunk), MP_STATE_VM(qstr_last_alloc), MP_STATE_VM(qstr_last_used), false);
225 : 2355 : MP_STATE_VM(qstr_last_chunk) = NULL;
226 : : } else {
227 : : // could grow existing memory
228 : 494 : MP_STATE_VM(qstr_last_alloc) += n_bytes;
229 : : }
230 : : }
231 : :
232 [ + + ]: 34719 : if (MP_STATE_VM(qstr_last_chunk) == NULL) {
233 : : // no existing memory for the interned string so allocate a new chunk
234 : 5579 : size_t al = n_bytes;
235 [ + + ]: 5579 : if (al < MICROPY_ALLOC_QSTR_CHUNK_INIT) {
236 : 5561 : al = MICROPY_ALLOC_QSTR_CHUNK_INIT;
237 : : }
238 : 5579 : MP_STATE_VM(qstr_last_chunk) = m_new_maybe(char, al);
239 [ - + ]: 5579 : if (MP_STATE_VM(qstr_last_chunk) == NULL) {
240 : : // failed to allocate a large chunk so try with exact size
241 : 0 : MP_STATE_VM(qstr_last_chunk) = m_new_maybe(char, n_bytes);
242 [ # # ]: 0 : if (MP_STATE_VM(qstr_last_chunk) == NULL) {
243 : 0 : QSTR_EXIT();
244 : 0 : m_malloc_fail(n_bytes);
245 : : }
246 : : al = n_bytes;
247 : : }
248 : 5579 : MP_STATE_VM(qstr_last_alloc) = al;
249 : 5579 : MP_STATE_VM(qstr_last_used) = 0;
250 : : }
251 : :
252 : : // allocate memory from the chunk for this new interned string's data
253 : 34719 : char *q_ptr = MP_STATE_VM(qstr_last_chunk) + MP_STATE_VM(qstr_last_used);
254 : 34719 : MP_STATE_VM(qstr_last_used) += n_bytes;
255 : :
256 : : // store the interned strings' data
257 : 34719 : size_t hash = qstr_compute_hash((const byte *)str, len);
258 : 34719 : memcpy(q_ptr, str, len);
259 : 34719 : q_ptr[len] = '\0';
260 : 34719 : q = qstr_add(hash, len, q_ptr);
261 : : }
262 : 179985 : QSTR_EXIT();
263 : 179985 : return q;
264 : : }
265 : :
266 : 2569804 : mp_uint_t qstr_hash(qstr q) {
267 : 2569804 : const qstr_pool_t *pool = find_qstr(&q);
268 : 2569810 : return pool->hashes[q];
269 : : }
270 : :
271 : 20010 : size_t qstr_len(qstr q) {
272 : 20010 : const qstr_pool_t *pool = find_qstr(&q);
273 : 20010 : return pool->lengths[q];
274 : : }
275 : :
276 : 7966 : const char *qstr_str(qstr q) {
277 : 7966 : const qstr_pool_t *pool = find_qstr(&q);
278 : 7966 : return pool->qstrs[q];
279 : : }
280 : :
281 : 630666 : const byte *qstr_data(qstr q, size_t *len) {
282 : 630666 : const qstr_pool_t *pool = find_qstr(&q);
283 : 630666 : *len = pool->lengths[q];
284 : 630666 : return (byte *)pool->qstrs[q];
285 : : }
286 : :
287 : 8 : void qstr_pool_info(size_t *n_pool, size_t *n_qstr, size_t *n_str_data_bytes, size_t *n_total_bytes) {
288 : 8 : QSTR_ENTER();
289 : 8 : *n_pool = 0;
290 : 8 : *n_qstr = 0;
291 : 8 : *n_str_data_bytes = 0;
292 : 8 : *n_total_bytes = 0;
293 [ + - + + ]: 16 : for (const qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
294 : 8 : *n_pool += 1;
295 : 8 : *n_qstr += pool->len;
296 [ + + ]: 40 : for (qstr_len_t *l = pool->lengths, *l_top = pool->lengths + pool->len; l < l_top; l++) {
297 : 32 : *n_str_data_bytes += *l + 1;
298 : : }
299 : : #if MICROPY_ENABLE_GC
300 : 8 : *n_total_bytes += gc_nbytes(pool); // this counts actual bytes used in heap
301 : : #else
302 : : *n_total_bytes += sizeof(qstr_pool_t)
303 : : + (sizeof(const char *) + sizeof(qstr_hash_t) + sizeof(qstr_len_t)) * pool->alloc;
304 : : #endif
305 : : }
306 : 8 : *n_total_bytes += *n_str_data_bytes;
307 : 8 : QSTR_EXIT();
308 : 8 : }
309 : :
310 : : #if MICROPY_PY_MICROPYTHON_MEM_INFO
311 : 4 : void qstr_dump_data(void) {
312 : 4 : QSTR_ENTER();
313 [ + - + + ]: 8 : for (const qstr_pool_t *pool = MP_STATE_VM(last_pool); pool != NULL && pool != &CONST_POOL; pool = pool->prev) {
314 [ + + ]: 20 : for (const char *const *q = pool->qstrs, *const *q_top = pool->qstrs + pool->len; q < q_top; q++) {
315 : 16 : mp_printf(&mp_plat_print, "Q(%s)\n", *q);
316 : : }
317 : : }
318 : 4 : QSTR_EXIT();
319 : 4 : }
320 : : #endif
321 : :
322 : : #if MICROPY_ROM_TEXT_COMPRESSION
323 : :
324 : : #ifdef NO_QSTR
325 : :
326 : : // If NO_QSTR is set, it means we're doing QSTR extraction.
327 : : // So we won't yet have "genhdr/compressed.data.h"
328 : :
329 : : #else
330 : :
331 : : // Emit the compressed_string_data string.
332 : : #define MP_COMPRESSED_DATA(x) STATIC const char *compressed_string_data = x;
333 : : #define MP_MATCH_COMPRESSED(a, b)
334 : : #include "genhdr/compressed.data.h"
335 : : #undef MP_COMPRESSED_DATA
336 : : #undef MP_MATCH_COMPRESSED
337 : :
338 : : #endif // NO_QSTR
339 : :
340 : : // This implements the "common word" compression scheme (see makecompresseddata.py) where the most
341 : : // common 128 words in error messages are replaced by their index into the list of common words.
342 : :
343 : : // The compressed string data is delimited by setting high bit in the final char of each word.
344 : : // e.g. aaaa<0x80|a>bbbbbb<0x80|b>....
345 : : // This method finds the n'th string.
346 : 5998 : STATIC const byte *find_uncompressed_string(uint8_t n) {
347 : 5998 : const byte *c = (byte *)compressed_string_data;
348 [ + + ]: 191396 : while (n > 0) {
349 [ + + ]: 1085330 : while ((*c & 0x80) == 0) {
350 : 899932 : ++c;
351 : : }
352 : 185398 : ++c;
353 : 185398 : --n;
354 : : }
355 : 5998 : return c;
356 : : }
357 : :
358 : : // Given a compressed string in src, decompresses it into dst.
359 : : // dst must be large enough (use MP_MAX_UNCOMPRESSED_TEXT_LEN+1).
360 : 1392 : void mp_decompress_rom_string(byte *dst, const mp_rom_error_text_t src_chr) {
361 : : // Skip past the 0xff marker.
362 : 1392 : const byte *src = (byte *)src_chr + 1;
363 : : // Need to add spaces around compressed words, except for the first (i.e. transition from 1<->2).
364 : : // 0 = start, 1 = compressed, 2 = regular.
365 : 1392 : int state = 0;
366 [ + + ]: 16148 : while (*src) {
367 [ + + ]: 14756 : if ((byte) * src >= 128) {
368 [ + + ]: 5998 : if (state != 0) {
369 : 4814 : *dst++ = ' ';
370 : : }
371 : 5998 : state = 1;
372 : :
373 : : // High bit set, replace with common word.
374 : 5998 : const byte *word = find_uncompressed_string(*src & 0x7f);
375 : : // The word is terminated by the final char having its high bit set.
376 [ + + ]: 29868 : while ((*word & 0x80) == 0) {
377 : 23870 : *dst++ = *word++;
378 : : }
379 : 5998 : *dst++ = (*word & 0x7f);
380 : : } else {
381 : : // Otherwise just copy one char.
382 [ + + ]: 8758 : if (state == 1) {
383 : 988 : *dst++ = ' ';
384 : : }
385 : 8758 : state = 2;
386 : :
387 : 8758 : *dst++ = *src;
388 : : }
389 : 14756 : ++src;
390 : : }
391 : : // Add null-terminator.
392 : 1392 : *dst = 0;
393 : 1392 : }
394 : :
395 : : #endif // MICROPY_ROM_TEXT_COMPRESSION
|
