bernsteinbear.com
this repo has no description
1// Copyright (c) Facebook, Inc. and its affiliates. (http://www.facebook.com)
2#include "api-handle.h"
3
4#include <cstdint>
5
6#include "cpython-data.h"
7#include "cpython-func.h"
8#include "cpython-types.h"
9
10#include "capi-state.h"
11#include "capi.h"
12#include "debugging.h"
13#include "event.h"
14#include "globals.h"
15#include "object-builtins.h"
16#include "objects.h"
17#include "runtime.h"
18#include "scavenger.h"
19#include "thread.h"
20#include "visitor.h"
21
22namespace py {
23
24static const int32_t kEmptyIndex = -1;
25static const int32_t kTombstoneIndex = -2;
26
27struct IndexProbe {
28 word index;
29 word mask;
30 uword perturb;
31};
32
33// Compute hash value suitable for `RawObject::operator==` (aka `a is b`)
34// equality tests.
35static inline uword handleHash(RawObject obj) {
36 if (obj.isHeapObject()) {
37 return obj.raw() >> kObjectAlignmentLog2;
38 }
39 return obj.raw();
40}
41
42static int32_t indexAt(int32_t* indices, word index) { return indices[index]; }
43
44static void indexAtPut(int32_t* indices, word index, int32_t item_index) {
45 indices[index] = item_index;
46}
47
48static void indexAtPutTombstone(int32_t* indices, word index) {
49 indices[index] = kTombstoneIndex;
50}
51
52static void itemAtPut(RawObject* keys, void** values, int32_t index,
53 RawObject key, void* value) {
54 DCHECK(key != SmallInt::fromWord(0), "0 represents empty and tombstone");
55 DCHECK(value != nullptr, "key must be associated with a C-API handle");
56 keys[index] = key;
57 values[index] = value;
58}
59
60static void itemAtPutTombstone(RawObject* keys, void** values, int32_t index) {
61 keys[index] = SmallInt::fromWord(0);
62 values[index] = nullptr;
63}
64
65static RawObject itemKeyAt(RawObject* keys, int32_t index) {
66 return keys[index];
67}
68
69static void* itemValueAt(void** values, int32_t index) { return values[index]; }
70
71static int32_t maxCapacity(word num_indices) {
72 DCHECK(num_indices <= kMaxInt32, "cannot fit %ld indices into 4-byte int",
73 num_indices);
74 return static_cast<int32_t>((num_indices * 2) / 3);
75}
76
77static int32_t* newIndices(word num_indices) {
78 word size = num_indices * sizeof(int32_t);
79 void* result = std::malloc(size);
80 DCHECK(result != nullptr, "malloc failed");
81 std::memset(result, -1, size); // fill with kEmptyIndex
82 return reinterpret_cast<int32_t*>(result);
83}
84
85static RawObject* newKeys(int32_t capacity) {
86 void* result = std::calloc(capacity, sizeof(RawObject));
87 DCHECK(result != nullptr, "malloc failed");
88 return reinterpret_cast<RawObject*>(result);
89}
90
91static void** newValues(int32_t capacity) {
92 void* result = std::malloc(static_cast<size_t>(capacity) * kPointerSize);
93 DCHECK(result != nullptr, "malloc failed");
94 return reinterpret_cast<void**>(result);
95}
96
97static bool nextItem(RawObject* keys, void** values, int32_t* idx, int32_t end,
98 RawObject* key_out, void** value_out) {
99 for (int32_t i = *idx; i < end; i++) {
100 RawObject key = itemKeyAt(keys, i);
101 if (key == SmallInt::fromWord(0)) continue;
102 *key_out = key;
103 *value_out = itemValueAt(values, i);
104 *idx = i + 1;
105 return true;
106 }
107 *idx = end;
108 return false;
109}
110
111static IndexProbe probeBegin(word num_indices, uword hash) {
112 DCHECK(num_indices > 0 && Utils::isPowerOfTwo(num_indices),
113 "number of indices must be a power of two, got %ld", num_indices);
114 word mask = num_indices - 1;
115 return {static_cast<word>(hash) & mask, mask, hash};
116}
117
118static void probeNext(IndexProbe* probe) {
119 // Note that repeated calls to this function guarantee a permutation of all
120 // indices when the number of indices is power of two. See
121 // https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0_0.
122 probe->perturb >>= 5;
123 probe->index = (probe->index * 5 + 1 + probe->perturb) & probe->mask;
124}
125
126void* ApiHandleDict::at(RawObject key) {
127 word index;
128 int32_t item_index;
129 if (lookup(key, &index, &item_index)) {
130 return itemValueAt(values(), item_index);
131 }
132 return nullptr;
133}
134
135inline void* ApiHandleDict::atIndex(int32_t item_index) {
136 return itemValueAt(values(), item_index);
137}
138
139void ApiHandleDict::atPut(RawObject key, void* value) {
140 int32_t item_index;
141 atPutLookup(key, &item_index);
142 atPutValue(item_index, value);
143}
144
145ALWAYS_INLINE bool ApiHandleDict::atPutLookup(RawObject key,
146 int32_t* item_index) {
147 DCHECK(key != SmallInt::fromWord(0),
148 "0 key not allowed (used for tombstone)");
149 uword hash = handleHash(key);
150 int32_t* indices = this->indices();
151 RawObject* keys = this->keys();
152 word num_indices = this->numIndices();
153
154 word next_free_index = -1;
155 for (IndexProbe probe = probeBegin(num_indices, hash);; probeNext(&probe)) {
156 int32_t current_item_index = indexAt(indices, probe.index);
157 if (current_item_index >= 0) {
158 if (itemKeyAt(keys, current_item_index) == key) {
159 *item_index = current_item_index;
160 return false;
161 }
162 continue;
163 }
164 if (next_free_index == -1) {
165 next_free_index = probe.index;
166 }
167 if (current_item_index == kEmptyIndex) {
168 word new_item_index = nextIndex();
169 indexAtPut(indices, next_free_index, new_item_index);
170 keys[new_item_index] = key;
171 setNextIndex(new_item_index + 1);
172 incrementNumItems();
173 *item_index = new_item_index;
174 return true;
175 }
176 }
177}
178
179ALWAYS_INLINE void ApiHandleDict::atPutValue(int32_t item_index, void* value) {
180 DCHECK(value != nullptr, "key cannot be associated with nullptr");
181 values()[item_index] = value;
182
183 // Maintain the invariant that we have space for at least one more item.
184 if (!hasUsableItem()) {
185 grow();
186 }
187}
188
189NEVER_INLINE void ApiHandleDict::grow() {
190 // If at least half of the items in the dense array are tombstones, removing
191 // them will free up plenty of space. Otherwise, the dict must be grown.
192 word growth_factor = (numItems() < capacity() / 2) ? 1 : kGrowthFactor;
193 word new_num_indices = numIndices() * growth_factor;
194 rehash(new_num_indices);
195 DCHECK(hasUsableItem(), "dict must have space for another item");
196}
197
198void ApiHandleDict::initialize(word num_indices) {
199 setIndices(newIndices(num_indices));
200 setNumIndices(num_indices);
201
202 int32_t capacity = maxCapacity(num_indices);
203 setCapacity(capacity);
204 setKeys(newKeys(capacity));
205 setValues(newValues(capacity));
206}
207
208bool ApiHandleDict::lookup(RawObject key, word* sparse, int32_t* dense) {
209 uword hash = handleHash(key);
210 int32_t* indices = this->indices();
211 RawObject* keys = this->keys();
212 word num_indices = this->numIndices();
213
214 for (IndexProbe probe = probeBegin(num_indices, hash);; probeNext(&probe)) {
215 int32_t item_index = indexAt(indices, probe.index);
216 if (item_index >= 0) {
217 if (itemKeyAt(keys, item_index) == key) {
218 *sparse = probe.index;
219 *dense = item_index;
220 return true;
221 }
222 continue;
223 }
224 if (item_index == kEmptyIndex) {
225 return false;
226 }
227 }
228}
229
230void ApiHandleDict::rehash(word new_num_indices) {
231 int32_t end = nextIndex();
232 int32_t* indices = this->indices();
233 RawObject* keys = this->keys();
234 void** values = this->values();
235
236 int32_t new_capacity = maxCapacity(new_num_indices);
237 int32_t* new_indices = newIndices(new_num_indices);
238 RawObject* new_keys = newKeys(new_capacity);
239 void** new_values = newValues(new_capacity);
240
241 // Re-insert items
242 RawObject key = NoneType::object();
243 void* value;
244 for (int32_t i = 0, count = 0; nextItem(keys, values, &i, end, &key, &value);
245 count++) {
246 uword hash = handleHash(key);
247 for (IndexProbe probe = probeBegin(new_num_indices, hash);;
248 probeNext(&probe)) {
249 if (indexAt(new_indices, probe.index) == kEmptyIndex) {
250 indexAtPut(new_indices, probe.index, count);
251 itemAtPut(new_keys, new_values, count, key, value);
252 break;
253 }
254 }
255 }
256
257 setCapacity(new_capacity);
258 setIndices(new_indices);
259 setKeys(new_keys);
260 setNextIndex(numItems());
261 setNumIndices(new_num_indices);
262 setValues(new_values);
263
264 std::free(indices);
265 std::free(keys);
266 std::free(values);
267}
268
269void* ApiHandleDict::remove(RawObject key) {
270 word index;
271 int32_t item_index;
272 if (!lookup(key, &index, &item_index)) {
273 return nullptr;
274 }
275
276 void** values = this->values();
277 void* result = itemValueAt(values, item_index);
278 indexAtPutTombstone(indices(), index);
279 itemAtPutTombstone(keys(), values, item_index);
280 decrementNumItems();
281 return result;
282}
283
284void ApiHandleDict::visitKeys(PointerVisitor* visitor) {
285 RawObject* keys = this->keys();
286 if (keys == nullptr) return;
287 word keys_length = capacity();
288 for (word i = 0; i < keys_length; i++) {
289 visitor->visitPointer(&keys[i], PointerKind::kRuntime);
290 }
291}
292
293// Reserves a new handle in the given runtime's handle buffer.
294static ApiHandle* allocateHandle(Runtime* runtime) {
295 FreeListNode** free_handles = capiFreeHandles(runtime);
296 ApiHandle* result = reinterpret_cast<ApiHandle*>(*free_handles);
297
298 FreeListNode* next = (*free_handles)->next;
299 if (next != nullptr) {
300 *free_handles = next;
301 } else {
302 // No handles left to recycle; advance the frontier
303 *free_handles = reinterpret_cast<FreeListNode*>(result + 1);
304 }
305
306 return result;
307}
308
309// Frees the handle for future re-use by the given runtime.
310static void freeHandle(Runtime* runtime, ApiHandle* handle) {
311 FreeListNode** free_handles = capiFreeHandles(runtime);
312 FreeListNode* node = reinterpret_cast<FreeListNode*>(handle);
313 node->next = *free_handles;
314 *free_handles = node;
315}
316
317RawNativeProxy ApiHandle::asNativeProxy(ApiHandle* handle) {
318 DCHECK(!isImmediate(handle) && handle->reference_ != 0, "expected extension object handle");
319 return RawObject{handle->reference_}.rawCast<RawNativeProxy>();
320}
321
322ApiHandle* ApiHandle::newReference(Runtime* runtime, RawObject obj) {
323 if (isEncodeableAsImmediate(obj)) {
324 return handleFromImmediate(obj);
325 }
326 if (runtime->isInstanceOfNativeProxy(obj)) {
327 ApiHandle* result = static_cast<ApiHandle*>(
328 Int::cast(obj.rawCast<RawNativeProxy>().native()).asCPtr());
329 increfNoImmediate(result);
330 return result;
331 }
332 return ApiHandle::newReferenceWithManaged(runtime, obj);
333}
334
335ApiHandle* ApiHandle::newReferenceWithManaged(Runtime* runtime, RawObject obj) {
336 DCHECK(!isEncodeableAsImmediate(obj), "immediates not handled here");
337 DCHECK(!runtime->isInstanceOfNativeProxy(obj),
338 "native proxy not handled here");
339
340 // Get the handle of a builtin instance
341 ApiHandleDict* handles = capiHandles(runtime);
342 int32_t index;
343 if (!handles->atPutLookup(obj, &index)) {
344 ApiHandle* result = reinterpret_cast<ApiHandle*>(handles->atIndex(index));
345 increfNoImmediate(result);
346 return result;
347 }
348
349 // Initialize an ApiHandle for a builtin object or runtime instance
350 EVENT_ID(AllocateCAPIHandle, obj.layoutId());
351 ApiHandle* handle = allocateHandle(runtime);
352 handle->reference_ = SmallInt::fromWord(0).raw();
353 handle->ob_refcnt = 1;
354
355 handles->atPutValue(index, handle);
356 handle->reference_ = obj.raw();
357 return handle;
358}
359
360ApiHandle* ApiHandle::borrowedReference(Runtime* runtime, RawObject obj) {
361 if (isEncodeableAsImmediate(obj)) {
362 return handleFromImmediate(obj);
363 }
364 if (runtime->isInstanceOfNativeProxy(obj)) {
365 ApiHandle* result = static_cast<ApiHandle*>(
366 Int::cast(obj.rawCast<RawNativeProxy>().native()).asCPtr());
367 result->ob_refcnt |= kBorrowedBit;
368 return result;
369 }
370 ApiHandle* result = ApiHandle::newReferenceWithManaged(runtime, obj);
371 result->ob_refcnt |= kBorrowedBit;
372 result->ob_refcnt--;
373 return result;
374}
375
376RawObject ApiHandle::checkFunctionResult(Thread* thread, PyObject* result) {
377 bool has_pending_exception = thread->hasPendingException();
378 if (result == nullptr) {
379 if (has_pending_exception) return Error::exception();
380 return thread->raiseWithFmt(LayoutId::kSystemError,
381 "NULL return without exception set");
382 }
383 RawObject result_obj = stealReference(result);
384 if (has_pending_exception) {
385 // TODO(T53569173): set the currently pending exception as the cause of the
386 // newly raised SystemError
387 thread->clearPendingException();
388 return thread->raiseWithFmt(LayoutId::kSystemError,
389 "non-NULL return with exception set");
390 }
391 return result_obj;
392}
393
394void* ApiHandle::cache(Runtime* runtime, ApiHandle* handle) {
395 // Only managed objects can have a cached value
396 DCHECK(!isImmediate(handle), "immediate handles do not have caches");
397
398 ApiHandleDict* caches = capiCaches(runtime);
399 RawObject obj = asObjectNoImmediate(handle);
400 DCHECK(!runtime->isInstanceOfNativeProxy(obj),
401 "cache must not be called on extension object");
402 return caches->at(obj);
403}
404
405NEVER_INLINE void ApiHandle::dispose(ApiHandle* handle) {
406 disposeWithRuntime(Thread::current()->runtime(), handle);
407}
408
409void ApiHandle::disposeWithRuntime(Runtime* runtime, ApiHandle* handle) {
410 // TODO(T46009838): If a module handle is being disposed, this should register
411 // a weakref to call the module's m_free once's the module is collected
412
413 RawObject obj = asObjectNoImmediate(handle);
414 DCHECK(!runtime->isInstanceOfNativeProxy(obj),
415 "Dispose must not be called on extension object");
416 capiHandles(runtime)->remove(obj);
417
418 void* cache = capiCaches(runtime)->remove(obj);
419 std::free(cache);
420 freeHandle(runtime, handle);
421}
422
423// TODO(T58710656): Allow immediate handles for SmallStr
424// TODO(T58710677): Allow immediate handles for SmallBytes
425bool ApiHandle::isEncodeableAsImmediate(RawObject obj) {
426 // SmallStr and SmallBytes require solutions for C-API functions that read
427 // out char* whose lifetimes depend on the lifetimes of the PyObject*s.
428 return !obj.isHeapObject() && !obj.isSmallStr() && !obj.isSmallBytes();
429}
430
431void ApiHandle::setCache(Runtime* runtime, ApiHandle* handle, void* value) {
432 ApiHandleDict* caches = capiCaches(runtime);
433 RawObject obj = asObjectNoImmediate(handle);
434 caches->atPut(obj, value);
435}
436
437void ApiHandle::setRefcnt(ApiHandle* handle, Py_ssize_t count) {
438 if (isImmediate(handle)) return;
439 DCHECK((count & kBorrowedBit) == 0, "count must not have high bits set");
440 Py_ssize_t flags = handle->ob_refcnt & kBorrowedBit;
441 handle->ob_refcnt = count | flags;
442}
443
444void disposeApiHandles(Runtime* runtime) {
445 ApiHandleDict* handles = capiHandles(runtime);
446 int32_t end = handles->nextIndex();
447 RawObject* keys = handles->keys();
448 void** values = handles->values();
449
450 RawObject key = NoneType::object();
451 void* value;
452 for (int32_t i = 0; nextItem(keys, values, &i, end, &key, &value);) {
453 ApiHandle* handle = reinterpret_cast<ApiHandle*>(value);
454 ApiHandle::disposeWithRuntime(runtime, handle);
455 }
456}
457
458word numApiHandles(Runtime* runtime) {
459 return capiHandles(runtime)->numItems();
460}
461
462void visitApiHandles(Runtime* runtime, HandleVisitor* visitor) {
463 ApiHandleDict* handles = capiHandles(runtime);
464 int32_t end = handles->nextIndex();
465 RawObject* keys = handles->keys();
466 void** values = handles->values();
467
468 RawObject key = NoneType::object();
469 void* value;
470 for (int32_t i = 0; nextItem(keys, values, &i, end, &key, &value);) {
471 visitor->visitHandle(value, key);
472 }
473}
474
475void visitIncrementedApiHandles(Runtime* runtime, PointerVisitor* visitor) {
476 // Report handles with a refcount > 0 as roots. We deliberately do not visit
477 // other handles and do not update dictionary keys yet.
478 ApiHandleDict* handles = capiHandles(runtime);
479 int32_t end = handles->nextIndex();
480 RawObject* keys = handles->keys();
481 void** values = handles->values();
482
483 RawObject key = NoneType::object();
484 void* value;
485 for (int32_t i = 0; nextItem(keys, values, &i, end, &key, &value);) {
486 ApiHandle* handle = reinterpret_cast<ApiHandle*>(value);
487 if (ApiHandle::refcntNoImmediate(handle) > 0) {
488 visitor->visitPointer(&key, PointerKind::kApiHandle);
489 // We do not write back the changed `key` to the dictionary yet but leave
490 // that to `visitNotIncrementedBorrowedApiHandles` because we still need
491 // the old `key` to access `capiCaches` there).
492 }
493 }
494}
495
496void visitNotIncrementedBorrowedApiHandles(Runtime* runtime,
497 Scavenger* scavenger,
498 PointerVisitor* visitor) {
499 // This function:
500 // - Rebuilds the handle dictionary: The GC may have moved object around so
501 // we have to adjust the dictionary keys to the new references and updated
502 // hash values. As a side effect this also clears tombstones and shrinks
503 // the dictionary if possible.
504 // - Remove (or rather not insert into the new dictionary) entries with
505 // refcount zero, that are not referenced from any other live object
506 // (object is "white" after GC tri-coloring).
507 // - Rebuild cache dictionary to adjust for moved `key` addresses.
508
509 ApiHandleDict* caches = capiCaches(runtime);
510 ApiHandleDict* handles = capiHandles(runtime);
511 int32_t end = handles->nextIndex();
512 int32_t* indices = handles->indices();
513 RawObject* keys = handles->keys();
514 void** values = handles->values();
515
516 word old_num_items = handles->numItems();
517 word new_num_indices = Utils::nextPowerOfTwo((old_num_items * 3) / 2 + 1);
518 int32_t new_capacity = maxCapacity(new_num_indices);
519 int32_t* new_indices = newIndices(new_num_indices);
520 RawObject* new_keys = newKeys(new_capacity);
521 void** new_values = newValues(new_capacity);
522
523 RawObject key = NoneType::object();
524 void* value;
525 int32_t count = 0;
526 for (int32_t i = 0; nextItem(keys, values, &i, end, &key, &value);) {
527 ApiHandle* handle = reinterpret_cast<ApiHandle*>(value);
528 if (ApiHandle::refcntNoImmediate(handle) == 0) {
529 DCHECK(ApiHandle::isBorrowedNoImmediate(handle),
530 "non-borrowed object should already be disposed");
531 if (key.isHeapObject() &&
532 isWhiteObject(scavenger, HeapObject::cast(key))) {
533 // Lookup associated cache data. Note that `key` and the keys in the
534 // `caches` array both use addressed from before GC movement.
535 // `caches.rehash()` happens is delayed until the end of this function.
536 void* cache = caches->remove(key);
537 freeHandle(runtime, handle);
538 std::free(cache);
539 continue;
540 }
541 }
542 visitor->visitPointer(&key, PointerKind::kApiHandle);
543 handle->reference_ = reinterpret_cast<uintptr_t>(key.raw());
544 // Insert into new handle dictionary.
545 uword hash = handleHash(key);
546 for (IndexProbe probe = probeBegin(new_num_indices, hash);;
547 probeNext(&probe)) {
548 if (indexAt(new_indices, probe.index) == kEmptyIndex) {
549 indexAtPut(new_indices, probe.index, count);
550 itemAtPut(new_keys, new_values, count, key, value);
551 break;
552 }
553 }
554 count++;
555 }
556
557 handles->setCapacity(new_capacity);
558 handles->setIndices(new_indices);
559 handles->setKeys(new_keys);
560 handles->setNextIndex(count);
561 handles->setNumIndices(new_num_indices);
562 handles->setValues(new_values);
563
564 std::free(indices);
565 std::free(keys);
566 std::free(values);
567
568 // Re-hash caches dictionary.
569 caches->visitKeys(visitor);
570 caches->rehash(caches->numIndices());
571}
572
573RawObject objectGetMember(Thread* thread, RawObject ptr, RawObject name) {
574 ApiHandle* value = *reinterpret_cast<ApiHandle**>(Int::cast(ptr).asCPtr());
575 if (value != nullptr) {
576 return ApiHandle::asObject(value);
577 }
578 if (name.isNoneType()) {
579 return NoneType::object();
580 }
581 HandleScope scope(thread);
582 Str name_str(&scope, name);
583 return thread->raiseWithFmt(LayoutId::kAttributeError,
584 "Object attribute '%S' is nullptr", &name_str);
585}
586
587bool objectHasHandleCache(Runtime* runtime, RawObject obj) {
588 return ApiHandle::cache(runtime, ApiHandle::borrowedReference(runtime, obj)) != nullptr;
589}
590
591void* objectNewReference(Runtime* runtime, RawObject obj) {
592 return ApiHandle::newReference(runtime, obj);
593}
594
595void objectSetMember(Runtime* runtime, RawObject old_ptr, RawObject new_val) {
596 ApiHandle** old = reinterpret_cast<ApiHandle**>(Int::cast(old_ptr).asCPtr());
597 ApiHandle::decref(*old);
598 *old = ApiHandle::newReference(runtime, new_val);
599}
600
601void dump(PyObject* obj) {
602 if (obj == nullptr) {
603 std::fprintf(stderr, "<nullptr>\n");
604 return;
605 }
606 dump(ApiHandle::asObject(ApiHandle::fromPyObject(obj)));
607}
608
609} // namespace py