1 /*
2 * This module implements a hash table class for mapping C/C++ addresses to the
3 * corresponding wrapped Python object.
4 *
5 * Copyright (c) 2017 Riverbank Computing Limited <info@riverbankcomputing.com>
6 *
7 * This file is part of SIP.
8 *
9 * This copy of SIP is licensed for use under the terms of the SIP License
10 * Agreement. See the file LICENSE for more details.
11 *
12 * This copy of SIP may also used under the terms of the GNU General Public
13 * License v2 or v3 as published by the Free Software Foundation which can be
14 * found in the files LICENSE-GPL2 and LICENSE-GPL3 included in this package.
15 *
16 * SIP is supplied WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
18 */
19
20
21 #include <string.h>
22
23 #include "sipint.h"
24
25
26 #define hash_1(k,s) (((unsigned long)(k)) % (s))
27 #define hash_2(k,s) ((s) - 2 - (hash_1((k),(s)) % ((s) - 2)))
28
29
30 /* Prime numbers to use as hash table sizes. */
31 static unsigned long hash_primes[] = {
32 521, 1031, 2053, 4099,
33 8209, 16411, 32771, 65537, 131101, 262147,
34 524309, 1048583, 2097169, 4194319, 8388617, 16777259,
35 33554467, 67108879, 134217757, 268435459, 536870923, 1073741827,
36 2147483659U,0
37 };
38
39
40 static sipHashEntry *newHashTable(unsigned long);
41 static sipHashEntry *findHashEntry(sipObjectMap *,void *);
42 static void add_object(sipObjectMap *om, void *addr, sipSimpleWrapper *val);
43 static void add_aliases(sipObjectMap *om, void *addr, sipSimpleWrapper *val,
44 const sipClassTypeDef *base_ctd, const sipClassTypeDef *ctd);
45 static int remove_object(sipObjectMap *om, void *addr, sipSimpleWrapper *val);
46 static void remove_aliases(sipObjectMap *om, void *addr, sipSimpleWrapper *val,
47 const sipClassTypeDef *base_ctd, const sipClassTypeDef *ctd);
48 static void reorganiseMap(sipObjectMap *om);
49 static void *getUnguardedPointer(sipSimpleWrapper *w);
50
51
52 /*
53 * Initialise an object map.
54 */
sipOMInit(sipObjectMap * om)55 void sipOMInit(sipObjectMap *om)
56 {
57 om -> primeIdx = 0;
58 om -> unused = om -> size = hash_primes[om -> primeIdx];
59 om -> stale = 0;
60 om -> hash_array = newHashTable(om -> size);
61 }
62
63
64 /*
65 * Finalise an object map.
66 */
sipOMFinalise(sipObjectMap * om)67 void sipOMFinalise(sipObjectMap *om)
68 {
69 sip_api_free(om -> hash_array);
70 }
71
72
73 /*
74 * Allocate and initialise a new hash table.
75 */
newHashTable(unsigned long size)76 static sipHashEntry *newHashTable(unsigned long size)
77 {
78 size_t nbytes;
79 sipHashEntry *hashtab;
80
81 nbytes = sizeof (sipHashEntry) * size;
82
83 if ((hashtab = (sipHashEntry *)sip_api_malloc(nbytes)) != NULL)
84 memset(hashtab,0,nbytes);
85
86 return hashtab;
87 }
88
89
90 /*
91 * Return a pointer to the hash entry that is used, or should be used, for the
92 * given C/C++ address.
93 */
findHashEntry(sipObjectMap * om,void * key)94 static sipHashEntry *findHashEntry(sipObjectMap *om,void *key)
95 {
96 unsigned long hash, inc;
97 void *hek;
98
99 hash = hash_1(key,om -> size);
100 inc = hash_2(key,om -> size);
101
102 while ((hek = om -> hash_array[hash].key) != NULL && hek != key)
103 hash = (hash + inc) % om -> size;
104
105 return &om -> hash_array[hash];
106 }
107
108
109 /*
110 * Return the wrapped Python object of a specific type for a C/C++ address or
111 * NULL if it wasn't found.
112 */
sipOMFindObject(sipObjectMap * om,void * key,const sipTypeDef * td)113 sipSimpleWrapper *sipOMFindObject(sipObjectMap *om, void *key,
114 const sipTypeDef *td)
115 {
116 sipHashEntry *he = findHashEntry(om, key);
117 sipSimpleWrapper *sw;
118 PyTypeObject *py_type = sipTypeAsPyTypeObject(td);
119
120 /* Go through each wrapped object at this address. */
121 for (sw = he->first; sw != NULL; sw = sw->next)
122 {
123 sipSimpleWrapper *unaliased;
124
125 unaliased = (sipIsAlias(sw) ? (sipSimpleWrapper *)sw->data : sw);
126
127 /*
128 * If the reference count is 0 then it is in the process of being
129 * deleted, so ignore it. It's not completely clear how this can
130 * happen (but it can) because it implies that the garbage collection
131 * code is being re-entered (and there are guards in place to prevent
132 * this).
133 */
134 if (Py_REFCNT(unaliased) == 0)
135 continue;
136
137 /* Ignore it if the C/C++ address is no longer valid. */
138 if (sip_api_get_address(unaliased) == NULL)
139 continue;
140
141 /*
142 * If this wrapped object is of the given type, or a sub-type of it,
143 * then we assume it is the same C++ object.
144 */
145 if (PyObject_TypeCheck(unaliased, py_type))
146 return unaliased;
147 }
148
149 return NULL;
150 }
151
152
153 /*
154 * Add a C/C++ address and the corresponding wrapped Python object to the map.
155 */
sipOMAddObject(sipObjectMap * om,sipSimpleWrapper * val)156 void sipOMAddObject(sipObjectMap *om, sipSimpleWrapper *val)
157 {
158 void *addr = getUnguardedPointer(val);
159 const sipClassTypeDef *base_ctd;
160
161 /* Add the object. */
162 add_object(om, addr, val);
163
164 /* Add any aliases. */
165 base_ctd = (const sipClassTypeDef *)((sipWrapperType *)Py_TYPE(val))->wt_td;
166 add_aliases(om, addr, val, base_ctd, base_ctd);
167 }
168
169
170 /*
171 * Add an alias for any address that is different when cast to a super-type.
172 */
add_aliases(sipObjectMap * om,void * addr,sipSimpleWrapper * val,const sipClassTypeDef * base_ctd,const sipClassTypeDef * ctd)173 static void add_aliases(sipObjectMap *om, void *addr, sipSimpleWrapper *val,
174 const sipClassTypeDef *base_ctd, const sipClassTypeDef *ctd)
175 {
176 const sipEncodedTypeDef *sup;
177
178 /* See if there are any super-classes. */
179 if ((sup = ctd->ctd_supers) != NULL)
180 {
181 sipClassTypeDef *sup_ctd = sipGetGeneratedClassType(sup, ctd);
182
183 /* Recurse up the hierachy for the first super-class. */
184 add_aliases(om, addr, val, base_ctd, sup_ctd);
185
186 /*
187 * We only check for aliases for subsequent super-classes because the
188 * first one can never need one.
189 */
190 while (!sup++->sc_flag)
191 {
192 void *sup_addr;
193
194 sup_ctd = sipGetGeneratedClassType(sup, ctd);
195
196 /* Recurse up the hierachy for the remaining super-classes. */
197 add_aliases(om, addr, val, base_ctd, sup_ctd);
198
199 sup_addr = (*base_ctd->ctd_cast)(addr, (sipTypeDef *)sup_ctd);
200
201 if (sup_addr != addr)
202 {
203 sipSimpleWrapper *alias;
204
205 /* Note that we silently ignore errors. */
206 if ((alias = sip_api_malloc(sizeof (sipSimpleWrapper))) != NULL)
207 {
208 /*
209 * An alias is basically a bit-wise copy of the Python
210 * object but only to ensure the fields we are subverting
211 * are in the right place. An alias should never be passed
212 * to the Python API.
213 */
214 *alias = *val;
215
216 alias->sw_flags = (val->sw_flags & SIP_SHARE_MAP) | SIP_ALIAS;
217 alias->data = val;
218 alias->next = NULL;
219
220 add_object(om, sup_addr, alias);
221 }
222 }
223 }
224 }
225 }
226
227
228 /*
229 * Add a wrapper (which may be an alias) to the map.
230 */
add_object(sipObjectMap * om,void * addr,sipSimpleWrapper * val)231 static void add_object(sipObjectMap *om, void *addr, sipSimpleWrapper *val)
232 {
233 sipHashEntry *he = findHashEntry(om, addr);
234
235 /*
236 * If the bucket is in use then we appear to have several objects at the
237 * same address.
238 */
239 if (he->first != NULL)
240 {
241 /*
242 * This can happen for three reasons. A variable of one class can be
243 * declared at the start of another class. Therefore there are two
244 * objects, of different classes, with the same address. The second
245 * reason is that the old C/C++ object has been deleted by C/C++ but we
246 * didn't get to find out for some reason, and a new C/C++ instance has
247 * been created at the same address. The third reason is if we are in
248 * the process of deleting a Python object but the C++ object gets
249 * wrapped again because the C++ dtor called a method that has been
250 * re-implemented in Python. The absence of the SIP_SHARE_MAP flag
251 * tells us that a new C++ instance has just been created and so we
252 * know the second reason is the correct one so we mark the old
253 * pointers as invalid and reuse the entry. Otherwise we just add this
254 * one to the existing list of objects at this address.
255 */
256 if (!(val->sw_flags & SIP_SHARE_MAP))
257 {
258 sipSimpleWrapper *sw = he->first;
259
260 he->first = NULL;
261
262 while (sw != NULL)
263 {
264 sipSimpleWrapper *next = sw->next;
265
266 if (sipIsAlias(sw))
267 {
268 sip_api_free(sw);
269 }
270 else
271 {
272 /*
273 * We are removing it from the map here. However, note
274 * that we first have to call the destructor before marking
275 * it as not being in the map, as the destructor itself
276 * might end up trying to remove the wrapper and its
277 * aliases from the map. In that case, if the wrapper is
278 * already marked as not in the map, the removal will just
279 * return early, leaving any potential aliases as stale
280 * entries in the map. If we later try to wrap a different
281 * object at the same address, we end up retrieving the
282 * stale alias entry from the object map, triggering a
283 * use-after-free when accessing its C++ object.
284 */
285 sip_api_instance_destroyed(sw);
286 sipSetNotInMap(sw);
287 }
288
289 sw = next;
290 }
291 }
292
293 val->next = he->first;
294 he->first = val;
295
296 return;
297 }
298
299 /* See if the bucket was unused or stale. */
300 if (he->key == NULL)
301 {
302 he->key = addr;
303 om->unused--;
304 }
305 else
306 {
307 om->stale--;
308 }
309
310 /* Add the rest of the new value. */
311 he->first = val;
312 val->next = NULL;
313
314 reorganiseMap(om);
315 }
316
317
318 /*
319 * Reorganise a map if it is running short of space.
320 */
reorganiseMap(sipObjectMap * om)321 static void reorganiseMap(sipObjectMap *om)
322 {
323 unsigned long old_size, i;
324 sipHashEntry *ohe, *old_tab;
325
326 /* Don't bother if it still has more than 12% available. */
327 if (om -> unused > om -> size >> 3)
328 return;
329
330 /*
331 * If reorganising (ie. making the stale buckets unused) using the same
332 * sized table would make 25% available then do that. Otherwise use a
333 * bigger table (if possible).
334 */
335 if (om -> unused + om -> stale < om -> size >> 2 && hash_primes[om -> primeIdx + 1] != 0)
336 om -> primeIdx++;
337
338 old_size = om -> size;
339 old_tab = om -> hash_array;
340
341 om -> unused = om -> size = hash_primes[om -> primeIdx];
342 om -> stale = 0;
343 om -> hash_array = newHashTable(om -> size);
344
345 /* Transfer the entries from the old table to the new one. */
346 ohe = old_tab;
347
348 for (i = 0; i < old_size; ++i)
349 {
350 if (ohe -> key != NULL && ohe -> first != NULL)
351 {
352 *findHashEntry(om,ohe -> key) = *ohe;
353 om -> unused--;
354 }
355
356 ++ohe;
357 }
358
359 sip_api_free(old_tab);
360 }
361
362
363 /*
364 * Remove a C/C++ object from the table. Return 0 if it was removed
365 * successfully.
366 */
sipOMRemoveObject(sipObjectMap * om,sipSimpleWrapper * val)367 int sipOMRemoveObject(sipObjectMap *om, sipSimpleWrapper *val)
368 {
369 void *addr;
370 const sipClassTypeDef *base_ctd;
371
372 /* Handle the trivial case. */
373 if (sipNotInMap(val))
374 return 0;
375
376 if ((addr = getUnguardedPointer(val)) == NULL)
377 return 0;
378
379 /* Remove any aliases. */
380 base_ctd = (const sipClassTypeDef *)((sipWrapperType *)Py_TYPE(val))->wt_td;
381 remove_aliases(om, addr, val, base_ctd, base_ctd);
382
383 /* Remove the object. */
384 return remove_object(om, addr, val);
385 }
386
387
388 /*
389 * Remove an alias for any address that is different when cast to a super-type.
390 */
remove_aliases(sipObjectMap * om,void * addr,sipSimpleWrapper * val,const sipClassTypeDef * base_ctd,const sipClassTypeDef * ctd)391 static void remove_aliases(sipObjectMap *om, void *addr, sipSimpleWrapper *val,
392 const sipClassTypeDef *base_ctd, const sipClassTypeDef *ctd)
393 {
394 const sipEncodedTypeDef *sup;
395
396 /* See if there are any super-classes. */
397 if ((sup = ctd->ctd_supers) != NULL)
398 {
399 sipClassTypeDef *sup_ctd = sipGetGeneratedClassType(sup, ctd);
400
401 /* Recurse up the hierachy for the first super-class. */
402 remove_aliases(om, addr, val, base_ctd, sup_ctd);
403
404 /*
405 * We only check for aliases for subsequent super-classes because the
406 * first one can never need one.
407 */
408 while (!sup++->sc_flag)
409 {
410 void *sup_addr;
411
412 sup_ctd = sipGetGeneratedClassType(sup, ctd);
413
414 /* Recurse up the hierachy for the remaining super-classes. */
415 remove_aliases(om, addr, val, base_ctd, sup_ctd);
416
417 sup_addr = (*base_ctd->ctd_cast)(addr, (sipTypeDef *)sup_ctd);
418
419 if (sup_addr != addr)
420 remove_object(om, sup_addr, val);
421 }
422 }
423 }
424
425
426 /*
427 * Remove a wrapper from the map.
428 */
remove_object(sipObjectMap * om,void * addr,sipSimpleWrapper * val)429 static int remove_object(sipObjectMap *om, void *addr, sipSimpleWrapper *val)
430 {
431 sipHashEntry *he = findHashEntry(om, addr);
432 sipSimpleWrapper **swp;
433
434 for (swp = &he->first; *swp != NULL; swp = &(*swp)->next)
435 {
436 sipSimpleWrapper *sw, *next;
437 int do_remove;
438
439 sw = *swp;
440 next = sw->next;
441
442 if (sipIsAlias(sw))
443 {
444 if (sw->data == val)
445 {
446 sip_api_free(sw);
447 do_remove = TRUE;
448 }
449 else
450 {
451 do_remove = FALSE;
452 }
453 }
454 else
455 {
456 do_remove = (sw == val);
457 }
458
459 if (do_remove)
460 {
461 *swp = next;
462
463 /*
464 * If the bucket is now empty then count it as stale. Note that we
465 * do not NULL the key and count it as unused because that might
466 * throw out the search for another entry that wanted to go here,
467 * found it already occupied, and was put somewhere else. In other
468 * words, searches must be repeatable until we reorganise the
469 * table.
470 */
471 if (he->first == NULL)
472 om->stale++;
473
474 return 0;
475 }
476 }
477
478 return -1;
479 }
480
481
482 /*
483 * Return the unguarded pointer to a C/C++ instance, ie. the pointer was valid
484 * but may longer be.
485 */
getUnguardedPointer(sipSimpleWrapper * w)486 static void *getUnguardedPointer(sipSimpleWrapper *w)
487 {
488 return (w->access_func != NULL) ? w->access_func(w, UnguardedPointer) : w->data;
489 }
490