1 /* Implementation of the HeapView type */
2
3 PyDoc_STRVAR(hv_doc,
4 "HeapView(root, heapdefs:tuple)\n"
5 "\n"
6 "Create a new HeapView object with arguments:\n"
7 "\n"
8 " root The initial value of the root member.\n"
9 " heapdefs Definitions of specially treated extension types.\n"
10 "\n"
11 "A HeapView object provides methods to get memory related information\n"
12 "about the system heap and about individual objects. \n"
13 "\n"
14 "It implements much of the low-level functionality for the Heapy\n"
15 "system. It is intended to provide what can not be done at all or would\n"
16 "be much slower if programmed directly in Python. It is not intended to\n"
17 "be used directly by a user, but to be wrapped in higher level objects.\n"
18 "\n"
19 "Some terms that are referred to in the method descriptions:\n"
20 "\n"
21 "Visible objects.\n"
22 "\n"
23 "The HeapView object attempts to restrict its view of the heap to only\n"
24 "the 'visible objects'. This is to make it possible to analyse the heap\n"
25 "via a Python library that inevitably itself is continually allocating\n"
26 "and deallocating objects. These should be hidden from the heap view\n"
27 "presented. This is primarily done via a special tag attribute, see\n"
28 "'_hiding_tag_' and 'register__hiding_tag__type'. Frames can be hidden\n"
29 "with another mechanism, see 'limitframe'. For hiding all objects of a\n"
30 "special type, 'register_hidden_exact_type' may be used. It is also\n"
31 "possible to use a separate interpreter and hide its root objects, see\n"
32 "'is_hiding_calling_interpreter'.\n"
33 "\n"
34 "Classifiers.\n"
35 "\n"
36 "The methods named cli_* are factory methods that create objects of\n"
37 "type ObjectClassifier. The principal difference between classifiers is\n"
38 "how a single object is classified. The single-object classification\n"
39 "function is available in classifier objects; it is the classify\n"
40 "method. There are also methods that operate on collections of objects,\n"
41 "namely partition and select. These eliminate the per-object\n"
42 "Python-level function call overhead that would occur if the classify\n"
43 "method were to be called from Python for each object in a collection.\n"
44 "See also the ObjectClassifier type.\n"
45 "\n"
46 "Individual size.\n"
47 "\n"
48 "The individual size of an object is its individually allocated memory size. \n"
49 "\n"
50 "It includes:\n"
51 "\n"
52 "o The basic object size, as can be found out in a standard way.\n"
53 "o The extra memory for variable size objects.\n"
54 "o For GC collected objects, the size of the GC information.\n"
55 "o An alignment to the next highest multiple of a pointer size.\n"
56 "o The size of any other memory allocated that belongs to the object.\n"
57 "\n"
58 "Some types of objects have extra memory allocated that can not be\n"
59 "accounted for in the standard way. This memory should nevertheless be\n"
60 "included in the individual size. To determine the size of these\n"
61 "objects, special functions are needed. These are defined for standard\n"
62 "builtin types, such as lists and dicts. Other types should be defined\n"
63 "via the heapdefs argument to the HeapView constructor.\n"
64 "\n"
65 "The individual size does not include:\n"
66 "\n"
67 "o Subobjects that are accounted for separately.\n"
68 "o Overhead for the memory allocation system. This varies depending\n"
69 " on the kind of memory allocator, the requested size, etc.\n"
70 );
71
72 #if PY_MAJOR_VERSION >= 3 && PY_MINOR_VERSION >= 9
73 # define Py_BUILD_CORE
74 /* PyGC_Head */
75 # undef _PyGC_FINALIZED
76 # include <internal/pycore_gc.h>
77 # undef Py_BUILD_CORE
78 #endif
79
80 #define ALIGN sizeof(void *)
81 #define ALIGN_MASK (ALIGN - 1)
82
83 #define XT_SIZE 1024
84 #define XT_MASK (XT_SIZE-1)
85
86 /* Forward declarations */
87
88 static PyObject *hv_heap(NyHeapViewObject *self, PyObject *args, PyObject *kwds);
89
90 static ExtraType *hv_new_extra_type(NyHeapViewObject *hv, PyTypeObject *type);
91
92 int cli_cmp_as_int(PyObject *cmp);
93
94 /* Helpers */
95
96 static PyObject *
hv_PyList_Pop(PyObject * list)97 hv_PyList_Pop(PyObject *list)
98 {
99 Py_ssize_t size = PyList_Size(list);
100 if (size > 0) {
101 PyObject *r = PyList_GetItem(list, size - 1);
102 Py_XINCREF(r);
103 if (r)
104 if (PyList_SetSlice(list, size - 1, size, 0) < 0)
105 return 0;
106
107 return r;
108 } else {
109 if (size == 0)
110 PyErr_Format(PyExc_IndexError, "pop from empty list");
111 return 0;
112 }
113 }
114
115 /* HeapView methods */
116
117 static int
hv_gc_traverse(NyHeapViewObject * hv,visitproc visit,void * arg)118 hv_gc_traverse(NyHeapViewObject *hv, visitproc visit, void *arg)
119 {
120 Py_VISIT(hv->root);
121 Py_VISIT(hv->limitframe);
122 Py_VISIT(hv->static_types);
123 Py_VISIT(hv->weak_type_callback);
124
125 if (hv->xt_table) {
126 size_t i;
127 for (i = 0; i < hv->xt_size; i++) {
128 ExtraType *xt;
129 for (xt = hv->xt_table[i]; xt; xt = xt->xt_next) {
130 Py_VISIT(xt->xt_weak_type);
131 }
132 }
133 }
134 return 0;
135 }
136
137
138 void
xt_free_table(ExtraType ** xt_table,size_t size)139 xt_free_table(ExtraType **xt_table, size_t size)
140 {
141 size_t i;
142 if (!xt_table)
143 return;
144 for (i = 0; i < size; i++) {
145 ExtraType *xt = xt_table[i];
146 while (xt) {
147 ExtraType *xt_next = xt->xt_next;
148 Py_DECREF(xt->xt_weak_type);
149 PyMem_Del(xt);
150 xt = xt_next;
151 }
152 }
153 PyMem_Del(xt_table);
154 }
155
156 static int
hv_gc_clear(NyHeapViewObject * hv)157 hv_gc_clear(NyHeapViewObject *hv)
158 {
159 /* xxx Paranoid, clumsy, but recursion-safe variant? */
160 PyObject *ro = hv->root;
161 PyObject *lf = hv->limitframe;
162 PyObject *he = hv->_hiding_tag_;
163 PyObject *stob = hv->static_types;
164 PyObject *wtc = hv->weak_type_callback;
165 void *xt = hv->xt_table;
166
167 hv->root = 0;
168 hv->limitframe = 0;
169 hv->_hiding_tag_ = 0;
170 hv->static_types = 0;
171 hv->weak_type_callback = 0;
172 hv->xt_table = 0;
173
174 xt_free_table(xt, hv->xt_size);
175
176 Py_XDECREF(ro);
177 Py_XDECREF(lf);
178
179 Py_XDECREF(he);
180 Py_XDECREF(stob);
181 Py_XDECREF(wtc);
182 return 0;
183 }
184
185 static size_t
hv_default_size(PyObject * obj)186 hv_default_size(PyObject *obj)
187 {
188 if (PyErr_Occurred())
189 return -1;
190 size_t z = _PySys_GetSizeOf(obj);
191 if (!PyErr_Occurred() || !PyErr_ExceptionMatches(PyExc_TypeError))
192 return z;
193 PyErr_Clear();
194
195 z = Py_TYPE(obj)->tp_basicsize;
196 if (Py_TYPE(obj)->tp_itemsize) {
197 Py_ssize_t itemsize = Py_TYPE(obj)->tp_itemsize;
198 if (itemsize < 0)
199 itemsize = -itemsize; /* For (e.g.) long(Should we check? */
200 z += Py_SIZE(obj) * itemsize;
201 z = (z + ALIGN_MASK) & ~ALIGN_MASK;
202 }
203 if (PyObject_IS_GC(obj))
204 z += sizeof(PyGC_Head);
205 return z;
206 }
207
208 static int
owht_relate(NyHeapRelate * r,PyTypeObject * type)209 owht_relate(NyHeapRelate *r, PyTypeObject *type)
210 {
211 PyObject *v = r->src;
212 PyMemberDef *mp = type->tp_members;
213 if (mp) {
214 while (mp->name) {
215 if ((mp->type == T_OBJECT_EX || mp->type == T_OBJECT) &&
216 *((PyObject **)((char *)v+mp->offset)) == r->tgt) {
217 if (r->visit(NYHR_ATTRIBUTE, PyUnicode_FromString(mp->name), r))
218 return 1;
219 }
220 mp++;
221 }
222 }
223 return 0;
224 }
225
226 static NyHeapDef default_hd = {
227 0, /* flags */
228 0, /* type */
229 hv_default_size, /* size */
230 0, /* traverse */
231 0, /* relate */
232 };
233
234
235
236 static size_t
xt_error_size(PyObject * obj)237 xt_error_size(PyObject *obj)
238 {
239 return -1;
240 }
241
242 static int
xt_default_relate(struct ExtraType * xt,NyHeapRelate * r)243 xt_default_relate(struct ExtraType *xt, NyHeapRelate *r)
244 {
245 PyTypeObject *type = xt->xt_type;
246 PyObject **dictptr;
247 if (owht_relate(r, type))
248 return 1;
249 dictptr = _PyObject_GetDictPtr(r->src);
250 if (dictptr) {
251 if (*dictptr == r->tgt) {
252 if (r->visit(NYHR_ATTRIBUTE, PyUnicode_FromString("__dict__"), r))
253 return 1;
254 }
255 if (dict_relate_kv(r, *dictptr, NYHR_HASATTR, NYHR_ATTRIBUTE)) {
256 return 1;
257 }
258 }
259 return 0;
260 }
261
262 static int
xt_hd_relate(struct ExtraType * xt,NyHeapRelate * r)263 xt_hd_relate(struct ExtraType *xt, NyHeapRelate *r)
264 {
265 return xt->xt_hd->relate(r);
266 }
267
268 static int
xt_inherited_relate(struct ExtraType * xt,NyHeapRelate * r)269 xt_inherited_relate(struct ExtraType *xt, NyHeapRelate *r)
270 {
271 if (owht_relate(r, xt->xt_type))
272 return 1;
273 return xt->xt_base->xt_relate(xt->xt_base, r);
274 }
275
276 static int
xt_error_relate(struct ExtraType * xt,NyHeapRelate * r)277 xt_error_relate(struct ExtraType *xt, NyHeapRelate *r)
278 {
279 return -1;
280 }
281
282 static int
xt_error_traverse(struct ExtraType * xt,PyObject * obj,visitproc visit,void * arg)283 xt_error_traverse(struct ExtraType *xt, PyObject *obj, visitproc visit, void *arg)
284 {
285 return -1;
286 }
287
288 static int
xt_no_traverse(struct ExtraType * xt,PyObject * obj,visitproc visit,void * arg)289 xt_no_traverse(struct ExtraType *xt, PyObject *obj, visitproc visit, void *arg)
290 {
291 return 0;
292 }
293
294
295 static int
xt_tp_traverse(struct ExtraType * xt,PyObject * obj,visitproc visit,void * arg)296 xt_tp_traverse(struct ExtraType *xt, PyObject *obj, visitproc visit, void *arg)
297 {
298 return Py_TYPE(obj)->tp_traverse(obj, visit, arg);
299 }
300
301
302 static int
xt_hd_traverse(struct ExtraType * xt,PyObject * obj,visitproc visit,void * arg)303 xt_hd_traverse(struct ExtraType *xt, PyObject *obj, visitproc visit, void *arg)
304 {
305 PyErr_CheckSignals();
306 if (PyErr_Occurred())
307 return -1;
308 NyHeapTraverse ta;
309 NyHeapViewObject *hv = (void *)xt->xt_hv;
310 ta.flags = 0;
311 ta.obj = obj;
312 ta.visit = visit;
313 ta.arg = arg;
314 ta._hiding_tag_ = hv->_hiding_tag_;
315 ta.hv = (PyObject *)hv;
316 return xt->xt_hd->traverse(&ta);
317 }
318
319 static int
xt_he_traverse(struct ExtraType * xt,PyObject * obj,visitproc visit,void * arg)320 xt_he_traverse(struct ExtraType *xt, PyObject *obj, visitproc visit, void *arg)
321 {
322 Py_ssize_t offs = xt->xt_he_offs;
323 NyHeapViewObject *hv = (void *)xt->xt_hv;
324 PyObject **phe = (PyObject **)((char *)obj + offs);
325 if (*phe == hv->_hiding_tag_) {
326 return 0;
327 }
328 return xt->xt_he_traverse(xt, obj, visit, arg);
329 }
330
331
332 static ExtraType xt_error = {
333 0, /* xt_type */
334 xt_error_size, /* xt_size */
335 xt_error_traverse, /* xt_traverse */
336 xt_error_relate, /* xt_relate */
337 };
338
339 #define XT_ERROR 0
340 #define XT_HE 1
341 #define XT_TP 2
342 #define XT_NO 3
343 #define XT_HD 4
344 #define XT_HI 5
345
346 #define XT_HASH(hv, type) (((Py_uintptr_t)type >> 4) & XT_MASK)
347
348 void
xt_findout_size(ExtraType * xt)349 xt_findout_size(ExtraType *xt)
350 {
351 if (xt->xt_hd->size)
352 xt->xt_size = xt->xt_hd->size;
353 else
354 xt->xt_size = hv_default_size;
355 }
356
357 void
xt_findout_traverse(ExtraType * xt)358 xt_findout_traverse(ExtraType *xt)
359 {
360 if (xt->xt_hd->traverse) {
361 xt->xt_traverse = xt_hd_traverse;
362 xt->xt_trav_code = XT_HD;
363 return;
364 } else if (xt->xt_type->tp_traverse) {
365 xt->xt_traverse = xt_tp_traverse;
366 xt->xt_trav_code = XT_TP;
367 return;
368 } else {
369 xt->xt_traverse = xt_no_traverse;
370 xt->xt_trav_code = XT_NO;
371 return;
372 }
373 }
374
375 void
xt_findout_relate(ExtraType * xt)376 xt_findout_relate(ExtraType *xt)
377 {
378 if (xt->xt_hd->relate)
379 xt->xt_relate = xt_hd_relate;
380 else
381 xt->xt_relate = xt_default_relate;
382 }
383
384 static ExtraType *
hv_new_xt_for_type_at_xtp(NyHeapViewObject * hv,PyTypeObject * type,ExtraType ** xtp)385 hv_new_xt_for_type_at_xtp(NyHeapViewObject *hv, PyTypeObject *type, ExtraType **xtp)
386 {
387 ExtraType *xt = PyMem_New(ExtraType, 1);
388 if (!xt) {
389 PyErr_NoMemory();
390 return 0;
391 }
392 memset(xt, 0, sizeof(ExtraType));
393 *xtp = xt;
394 xt->xt_hv = (void *)hv;
395 xt->xt_type = type;
396 xt->xt_weak_type = PyWeakref_NewRef((PyObject *)type, hv->weak_type_callback);
397 if (!xt->xt_weak_type) {
398 PyMem_Del(xt);
399 return 0;
400 }
401 return xt;
402 }
403
404 static ExtraType *
hv_new_xt_for_type(NyHeapViewObject * hv,PyTypeObject * type)405 hv_new_xt_for_type(NyHeapViewObject *hv, PyTypeObject *type)
406 {
407 int hash = XT_HASH(hv, type);
408 ExtraType **xtp = &hv->xt_table[hash];
409 ExtraType *xt;
410 while ((xt = *xtp)) {
411 if (xt->xt_type == type) {
412 PyErr_Format(PyExc_ValueError,
413 "Duplicate heap definition for type '%.50s'",
414 type->tp_name);
415 return 0;
416 }
417 xtp = &xt->xt_next;
418 }
419 return hv_new_xt_for_type_at_xtp(hv, type, xtp);
420
421 }
422
423 static void
xt_set_heapdef(ExtraType * xt,NyHeapDef * hd)424 xt_set_heapdef(ExtraType *xt, NyHeapDef *hd)
425 {
426 xt->xt_hd = hd;
427 xt_findout_traverse(xt);
428 xt_findout_size(xt);
429 xt_findout_relate(xt);
430 }
431
432 static ExtraType *
hv_extra_type(NyHeapViewObject * hv,PyTypeObject * type)433 hv_extra_type(NyHeapViewObject *hv, PyTypeObject *type)
434 {
435 int hash = XT_HASH(hv, type);
436 ExtraType **xtp = &hv->xt_table[hash];
437 ExtraType *xt;
438 #ifdef COUNT_COLL
439 int i = 0;
440 #endif
441 while ((xt = *xtp)) {
442 if (xt->xt_type == type) {
443 #ifdef COUNT_COLL
444 if (i > maxcoll) {
445 maxcoll = i;
446 fprintf(stderr, "maxcoll %d\n", maxcoll);
447 }
448 #endif
449 return xt;
450 }
451 xtp = &xt->xt_next;
452 #ifdef COUNT_COLL
453 i += 1;
454 #endif
455 }
456 xt = hv_new_extra_type(hv, type);
457 if (!xt)
458 xt = &xt_error;
459 return xt;
460 }
461
462 static ExtraType *
hv_new_extra_type(NyHeapViewObject * hv,PyTypeObject * type)463 hv_new_extra_type(NyHeapViewObject *hv, PyTypeObject *type)
464 {
465 ExtraType *xt;
466 if (!type->tp_base) {
467 xt = hv_new_xt_for_type(hv, type);
468 if (!xt)
469 return 0;
470 xt_set_heapdef(xt, &default_hd);
471 } else {
472 ExtraType *base = hv_extra_type(hv, type->tp_base);
473 if (base == &xt_error)
474 return 0;
475 xt = hv_new_xt_for_type(hv, type);
476 if (!xt)
477 return 0;
478 xt->xt_base = base;
479 xt->xt_hd = base->xt_hd;
480 if (base->xt_trav_code == XT_HE) {
481 xt->xt_he_xt = base->xt_he_xt;
482 xt->xt_trav_code = base->xt_trav_code;
483 xt->xt_traverse = base->xt_traverse;
484 xt->xt_he_traverse = base->xt_he_traverse;
485 xt->xt_he_offs = base->xt_he_offs;
486 } else {
487 xt_findout_traverse(xt); /* xxx ??? */
488 }
489 xt->xt_size = base->xt_size;
490 xt->xt_relate = xt_inherited_relate;
491 }
492 return xt;
493 }
494
495 #ifdef COUNT_COLL
496
497 int maxcoll = 0;
498
499 #endif
500
501 static int
xt_relate(ExtraType * xt,NyHeapRelate * hr)502 xt_relate(ExtraType *xt, NyHeapRelate *hr)
503 {
504 PyTypeObject *type = Py_TYPE(hr->src);
505 if (PyType_Ready(type) == -1)
506 return -1;
507 if ((PyObject *)type == hr->tgt) {
508 if (hr->visit(NYHR_INTERATTR, PyUnicode_FromString("ob_type"), hr))
509 return 0;
510 }
511 return xt->xt_relate(xt, hr);
512 }
513
514
515 static size_t
xt_size(ExtraType * xt,PyObject * obj)516 xt_size(ExtraType *xt, PyObject *obj)
517 {
518 return xt->xt_size(obj);
519 }
520
521
522 static int
xt_traverse(ExtraType * xt,PyObject * obj,visitproc visit,void * arg)523 xt_traverse(ExtraType *xt, PyObject *obj, visitproc visit, void *arg)
524 {
525 if (xt->xt_trav_code == XT_NO)
526 return 0;
527 else if (xt->xt_trav_code == XT_TP)
528 return Py_TYPE(obj)->tp_traverse(obj, visit, arg);
529 else
530 return xt->xt_traverse(xt, obj, visit, arg);
531 }
532
533 NyNodeSetObject *
hv_mutnodeset_new(NyHeapViewObject * hv)534 hv_mutnodeset_new(NyHeapViewObject *hv)
535 {
536 return NyMutNodeSet_NewHiding(hv->_hiding_tag_);
537 }
538
539 static size_t
hv_std_size(NyHeapViewObject * hv,PyObject * obj)540 hv_std_size(NyHeapViewObject *hv, PyObject *obj)
541 {
542 return xt_size(hv_extra_type(hv, Py_TYPE(obj)), obj);
543 }
544
545 static int
hv_std_relate(NyHeapRelate * hr)546 hv_std_relate(NyHeapRelate *hr)
547 {
548 return xt_relate(hv_extra_type((NyHeapViewObject *)hr->hv, Py_TYPE(hr->src)), hr);
549 }
550
551 static int
hv_std_traverse(NyHeapViewObject * hv,PyObject * obj,visitproc visit,void * arg)552 hv_std_traverse(NyHeapViewObject *hv,
553 PyObject *obj, visitproc visit, void *arg)
554 {
555 return xt_traverse(hv_extra_type(hv, Py_TYPE(obj)), obj, visit, arg);
556 }
557
558 typedef struct {
559 NyHeapViewObject *hv;
560 NyNodeSetObject *ns;
561 PyObject *rm;
562 } CMSTravArg;
563
564 int
hv_is_obj_hidden(NyHeapViewObject * hv,PyObject * obj)565 hv_is_obj_hidden(NyHeapViewObject *hv, PyObject *obj)
566 {
567 PyTypeObject *type = Py_TYPE(obj);
568 ExtraType *xt = hv_extra_type(hv, type);
569 if (xt->xt_trav_code == XT_HE) {
570 Py_ssize_t offs = xt->xt_he_offs;
571 PyObject **phe = (PyObject **)((char *)obj + offs);
572 if (*phe == hv->_hiding_tag_) {
573 return 1;
574 }
575 } else if (xt->xt_trav_code == XT_HI) {
576 return 1;
577 } else if (type == &NyRootState_Type) {
578 /* Fixes a dominos confusion; see Notes Apr 20 2005 */
579 return 1;
580 } else {
581 PyObject **dp = _PyObject_GetDictPtr(obj);
582 if (dp && *dp && PyDict_GetItem(*dp, _hiding_tag__name) == hv->_hiding_tag_) {
583 return 1;
584 }
585 }
586 return 0;
587 }
588
589
590 static int
hv_cms_rec(PyObject * obj,CMSTravArg * ta)591 hv_cms_rec(PyObject *obj, CMSTravArg *ta)
592 {
593 if (hv_is_obj_hidden(ta->hv, obj)) {
594 if (PyList_Append(ta->rm, obj) == -1)
595 return -1;
596 }
597 return 0;
598 }
599
600
601 static int
hv_cleanup_mutset(NyHeapViewObject * hv,NyNodeSetObject * ns)602 hv_cleanup_mutset(NyHeapViewObject *hv, NyNodeSetObject *ns)
603 {
604 CMSTravArg ta;
605 int ret = -1;
606 Py_ssize_t i, size;
607 ta.hv = hv;
608 ta.ns = ns;
609 ta.rm = PyList_New(0);
610 if (!ta.rm)
611 goto err;
612 if (NyNodeSet_iterate(ta.ns, (visitproc)hv_cms_rec, &ta) == -1)
613 goto err;
614 size = PyList_Size(ta.rm);
615 for (i = 0; i < size; i++) {
616 PyObject *obj = PyList_GET_ITEM(ta.rm, i);
617 if (NyNodeSet_clrobj(ta.ns, obj) == -1)
618 goto err;
619 }
620 ret = 0;
621 err:
622 Py_XDECREF(ta.rm);
623 return ret;
624 }
625
626 static int
hv_add_heapdef(NyHeapViewObject * hv,NyHeapDef * hd)627 hv_add_heapdef(NyHeapViewObject *hv, NyHeapDef *hd)
628 {
629 ExtraType *xt = hv_new_xt_for_type(hv, hd->type);
630 if (!xt)
631 return -1;
632 xt_set_heapdef(xt, hd);
633 return 0;
634 }
635
636 static int
hv_add_heapdefs_array(NyHeapViewObject * hv,NyHeapDef * hd)637 hv_add_heapdefs_array(NyHeapViewObject *hv, NyHeapDef *hd)
638 {
639 while (hd->type) {
640 if (hv_add_heapdef(hv, hd) == -1)
641 return -1;
642 hd++;
643 }
644 return 0;
645 }
646
647 static int
hv_add_heapdefs_tuple(NyHeapViewObject * hv,PyTupleObject * heapdefs)648 hv_add_heapdefs_tuple(NyHeapViewObject *hv, PyTupleObject *heapdefs)
649 {
650 Py_ssize_t i;
651 for (i = 0; i < PyTuple_Size((PyObject *)heapdefs); i++) {
652 PyObject *obj = PyTuple_GetItem((PyObject *)heapdefs, i);
653 if (!PyCapsule_CheckExact(obj)) {
654 PyErr_SetString(PyExc_TypeError, "heapdefs must be a capsule object");
655 return -1;
656 }
657 const char *name = PyCapsule_GetName(obj);
658 const char *dot = strrchr(name, '.');
659 if (!dot || strcmp(dot, "._NyHeapDefs_")) {
660 PyErr_SetString(PyExc_TypeError, "heapdefs must be named <package name>._NyHeapDefs_");
661 return -1;
662 }
663 NyHeapDef *hd = PyCapsule_GetPointer(obj, name);
664 if (!hd)
665 return -1;
666 if (hv_add_heapdefs_array(hv, hd) == -1)
667 return -1;
668 }
669 return 0;
670 }
671
672
673
674 PyObject *
NyHeapView_SubTypeNew(PyTypeObject * type,PyObject * root,PyTupleObject * heapdefs)675 NyHeapView_SubTypeNew(PyTypeObject *type, PyObject *root, PyTupleObject *heapdefs)
676 {
677 NyHeapViewObject *hv = (NyHeapViewObject *)type->tp_alloc(type, 1);
678 size_t i;
679 if (!hv)
680 return 0;
681 Py_INCREF(root);
682 hv->root = root;
683 hv->limitframe = 0;
684 hv->_hiding_tag_ = Py_None;
685 Py_INCREF(Py_None);
686 hv->static_types = 0;
687 hv->xt_size = XT_SIZE;
688 hv->xt_mask = XT_MASK;
689 hv->weak_type_callback = 0;
690 hv->xt_table = 0;
691
692 /* The HeapView object hv is now initialized to some well-defined state --
693 but we have waited to try allocation till now when all
694 allocated members have been set (to 0 etc) so
695 that hv now may be correctly deallocated. */
696
697 hv->weak_type_callback = PyObject_GetAttrString((PyObject *)hv, "delete_extra_type");
698 if (!(hv->weak_type_callback))
699 goto err;
700
701 hv->xt_table = PyMem_New(ExtraType *, hv->xt_size);
702 if (!hv->xt_table)
703 goto err;
704 for (i = 0; i < hv->xt_size; i++)
705 hv->xt_table[i] = 0;
706
707 hv->static_types = (PyObject *)NyMutNodeSet_New();
708 if (!(hv->static_types))
709 goto err;
710
711 /* Add standard and user-defined heap definitions */
712
713 if (hv_add_heapdefs_array(hv, NyStdTypes_HeapDef) == -1)
714 goto err;
715 if (hv_add_heapdefs_array(hv, NyHvTypes_HeapDef) == -1)
716 goto err;
717 if (hv_add_heapdefs_tuple(hv, heapdefs) == -1)
718 goto err;
719 return (PyObject *)hv;
720
721 err:
722 Py_DECREF(hv);
723 return 0;
724 }
725
726 static PyObject *
hv_new(PyTypeObject * type,PyObject * args,PyObject * kwds)727 hv_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
728 {
729 PyObject *heapdefs = NULL;
730 PyObject *root = NULL;
731 static char *kwlist[] = {"root", "heapdefs", 0};
732 if (!PyArg_ParseTupleAndKeywords(args, kwds, "OO!:hv_new",kwlist,
733 &root,
734 &PyTuple_Type, &heapdefs))
735 return NULL;
736 return NyHeapView_SubTypeNew(type, root, (PyTupleObject *)heapdefs);
737 }
738
739 static void
hv_dealloc(PyObject * v)740 hv_dealloc(PyObject *v)
741 {
742 PyObject_GC_UnTrack(v);
743 Py_TRASHCAN_SAFE_BEGIN(v)
744 hv_gc_clear((NyHeapViewObject *)v);
745 Py_TYPE(v)->tp_free(v);
746 Py_TRASHCAN_SAFE_END(v)
747 }
748
749 PyDoc_STRVAR(hv_delete_extra_type_doc,
750 "HV.delete_extra_type(weakref)\n\
751 \n\
752 Delete extra type information. For internal use as a weak-ref callback.");
753
754 /* hv_delete_extra_type will be called by the weak type callback on its type.
755 I don't consider it time critical, because it wouldnt happen too often..
756 so make it simple, allow to take time in the order of the total number of
757 (extra) types.
758
759 */
760
761 static PyObject *
hv_delete_extra_type(NyHeapViewObject * hv,PyObject * wr)762 hv_delete_extra_type(NyHeapViewObject *hv, PyObject *wr)
763 {
764 size_t i;
765
766 if (!PyWeakref_Check(wr)) {
767 PyErr_Format(PyExc_TypeError,
768 "delete_extra_type: argument must be a weak ref, got '%.50s'",
769 Py_TYPE(wr)->tp_name);
770 return 0;
771 }
772 for (i = 0; i < hv->xt_size; i++) {
773 ExtraType *xt, **xtp;
774 for (xtp = &hv->xt_table[i]; (xt = *xtp); xtp = &xt->xt_next) {
775 if (xt->xt_weak_type == wr) {
776 *xtp = xt->xt_next;
777 PyMem_Del(xt);
778 Py_DECREF(wr);
779 Py_INCREF(Py_None);
780 return Py_None;
781 }
782 }
783 }
784 PyErr_Format(PyExc_ValueError,
785 "delete_extra_type: reference object %p not found",
786 wr);
787 return 0;
788 }
789
790 #include "hv_cli.c"
791
792 typedef struct {
793 NyHeapViewObject *hv;
794 NyNodeSetObject *hs;
795 PyObject *arg;
796 int (*visit)(PyObject *, void *);
797 PyObject *to_visit;
798 } IterTravArg;
799
800 static int
iter_rec(PyObject * obj,IterTravArg * ta)801 iter_rec(PyObject *obj, IterTravArg *ta) {
802 int r;
803 if (Py_REFCNT(obj) > 1) {
804 r = NyNodeSet_setobj(ta->hs, obj);
805 if (r)
806 return r < 0 ? r : 0;
807 }
808 r = ta->visit(obj, ta->arg);
809 if (!r) {
810 r = PyList_Append(ta->to_visit, obj);
811 }
812 return r;
813 }
814
815 int
NyHeapView_iterate(NyHeapViewObject * hv,int (* visit)(PyObject *,void *),void * arg)816 NyHeapView_iterate(NyHeapViewObject *hv, int (*visit)(PyObject *, void *),
817 void *arg)
818 {
819 IterTravArg ta;
820 int r;
821 ta.hv = hv;
822 ta.visit = visit;
823 ta.arg = arg;
824 ta.hs = hv_mutnodeset_new(hv);
825 ta.to_visit = PyList_New(0);
826 if (!(ta.hs && ta.to_visit))
827 goto err;
828 r = iter_rec(ta.hv->root, &ta);
829 while (PyList_Size(ta.to_visit)) {
830 PyObject *obj = hv_PyList_Pop(ta.to_visit);
831 if (!obj)
832 goto err;
833 if (hv_std_traverse(ta.hv, obj, (visitproc)iter_rec, &ta) == -1) {
834 Py_DECREF(obj);
835 goto err;
836 }
837 Py_DECREF(obj);
838 }
839
840 goto out;
841
842 err:
843 r = -1;
844 out:
845 Py_XDECREF(ta.to_visit);
846 Py_XDECREF(ta.hs);
847 return r;
848 }
849
850 PyDoc_STRVAR(hv_heap_doc,
851 "HV.heap() -> NodeSet\n\
852 \n\
853 Return a set containing all 'visible objects' in the heap view\n\
854 defined by HV. See also HeapView.__doc__.");
855
856 typedef struct {
857 NyHeapViewObject *hv;
858 NyNodeSetObject *visited;
859 PyObject *to_visit;
860 } HeapTravArg;
861
862 static int
hv_heap_rec(PyObject * obj,HeapTravArg * ta)863 hv_heap_rec(PyObject *obj, HeapTravArg *ta) {
864 int r;
865 if (hv_is_obj_hidden(ta->hv, obj) && Py_TYPE(obj) != &NyRootState_Type)
866 return 0;
867 r = NyNodeSet_setobj(ta->visited, obj);
868 if (r)
869 return r < 0 ? r : 0;
870 else
871 return PyList_Append(ta->to_visit, obj);
872 }
873
874 static int
hv_update_static_types_visitor(PyObject * obj,NyHeapViewObject * hv)875 hv_update_static_types_visitor(PyObject *obj, NyHeapViewObject *hv) {
876 if (PyType_Check(obj) &&
877 !(((PyTypeObject *)obj)->tp_flags & Py_TPFLAGS_HEAPTYPE))
878 return NyNodeSet_setobj((NyNodeSetObject *)(hv->static_types), obj);
879 return 0;
880 }
881
882 static int
hv_update_static_types(NyHeapViewObject * hv,PyObject * it)883 hv_update_static_types(NyHeapViewObject *hv, PyObject *it)
884 {
885 return iterable_iterate(it, (visitproc)hv_update_static_types_visitor, hv);
886 }
887
888
889 static PyObject *
hv_heap(NyHeapViewObject * self,PyObject * args,PyObject * kwds)890 hv_heap(NyHeapViewObject *self, PyObject *args, PyObject *kwds)
891 {
892 HeapTravArg ta;
893 ta.hv = self;
894 ta.visited = hv_mutnodeset_new(self);
895 ta.to_visit = PyList_New(0);
896 if (!(ta.visited && ta.to_visit))
897 goto err;
898 if (hv_heap_rec(ta.hv->root, &ta) == -1)
899 goto err;
900 while (PyList_Size(ta.to_visit)) {
901 PyObject *obj = hv_PyList_Pop(ta.to_visit);
902 if (!obj)
903 goto err;
904 if (hv_std_traverse(ta.hv, obj, (visitproc)hv_heap_rec, &ta) == -1) {
905 Py_DECREF(obj);
906 goto err;
907 }
908 Py_DECREF(obj);
909 }
910 if (hv_cleanup_mutset(ta.hv, ta.visited) == -1)
911 goto err;
912 if (PyObject_Length(self->static_types) == 0) {
913 if (hv_update_static_types(self, (PyObject *)ta.visited) == -1)
914 goto err;
915 }
916 Py_XDECREF(ta.to_visit);
917 return (PyObject *)ta.visited;
918 err:
919 Py_XDECREF(ta.visited);
920 Py_XDECREF(ta.to_visit);
921 return 0;
922 }
923
924 typedef struct {
925 NyHeapViewObject *hv;
926 Py_ssize_t sum;
927 } SalArg;
928
929 static int
hv_indisize_sum_rec(PyObject * obj,SalArg * ta)930 hv_indisize_sum_rec(PyObject *obj, SalArg *ta)
931 {
932 ta->sum += hv_std_size(ta->hv, obj);
933 return 0;
934 }
935
936 PyDoc_STRVAR(hv_indisize_sum_doc,
937 "HV.indisize_sum(S:iterable) -> int\n\
938 \n\
939 Return the sum of the 'individual size' of the objects in S.\n\
940 See also HeapView.__doc.");
941
942 static PyObject *
hv_indisize_sum(NyHeapViewObject * self,PyObject * arg)943 hv_indisize_sum(NyHeapViewObject *self, PyObject *arg)
944 {
945 SalArg ta;
946 ta.sum = 0;
947 ta.hv = self;
948 if (iterable_iterate(arg, (visitproc)hv_indisize_sum_rec, &ta) == -1)
949 return 0;
950 return PyLong_FromSsize_t(ta.sum);
951 }
952
953
954
955 typedef struct {
956 NyHeapRelate hr;
957 int err;
958 PyObject *relas[NYHR_LIMIT];
959 } hv_relate_visit_arg;
960
961 static int
hv_relate_visit(unsigned int relatype,PyObject * relator,NyHeapRelate * arg_)962 hv_relate_visit(unsigned int relatype, PyObject *relator, NyHeapRelate *arg_)
963 {
964 hv_relate_visit_arg *arg = (void *)arg_;
965 arg->err = -1;
966 if (!relator) {
967 if (PyErr_Occurred())
968 return -1;
969 relator = Py_None;
970 Py_INCREF(relator);
971 }
972 if (relatype >= NYHR_LIMIT) {
973 PyErr_SetString(PyExc_SystemError, "conf_relate_visit: invalid relation type");
974 goto ret;
975 }
976 if (!arg->relas[relatype]) {
977 if (!(arg->relas[relatype] = PyList_New(0)))
978 goto ret;
979 }
980 arg->err = PyList_Append(arg->relas[relatype], relator);
981 ret:
982 Py_DECREF(relator);
983 return arg->err;
984 }
985
986 typedef struct {
987 PyObject *src;
988 PyObject *tgt;
989 Py_ssize_t ne;
990 }
991 NETravArg;
992
993 static int
hv_ne_rec(PyObject * obj,NETravArg * ta)994 hv_ne_rec(PyObject *obj, NETravArg *ta)
995 {
996 if (obj == ta->tgt)
997 ta->ne++;
998 return 0;
999 }
1000
1001 PyDoc_STRVAR(hv_numedges_doc,
1002 "HV.numedges(src, tgt) -> int\n\
1003 \n\
1004 Return the number of edges from src to tgt.");
1005
1006 static PyObject *
hv_numedges(NyHeapViewObject * self,PyObject * args)1007 hv_numedges(NyHeapViewObject *self, PyObject *args)
1008 {
1009 NETravArg ta;
1010 if (!PyArg_ParseTuple(args, "OO:numedges", &ta.src, &ta.tgt))
1011 return NULL;
1012 ta.ne = 0;
1013 if (hv_std_traverse(self, ta.src, (visitproc)hv_ne_rec, &ta) == -1)
1014 return 0;
1015 return PyLong_FromSsize_t(ta.ne);
1016 }
1017
1018 typedef struct {
1019 NyHeapViewObject *hv;
1020 NyNodeSetObject *start, *avoid;
1021 NyNodeSetObject *visited;
1022 PyObject *to_visit;
1023 } RATravArg;
1024
1025 static int
hv_ra_rec(PyObject * obj,RATravArg * ta)1026 hv_ra_rec(PyObject *obj, RATravArg *ta)
1027 {
1028 int r;
1029 if (NyNodeSet_hasobj(ta->avoid, obj))
1030 return 0;
1031 r = NyNodeSet_setobj(ta->visited, obj);
1032 if (r)
1033 return r < 0 ? r : 0;
1034 else
1035 return PyList_Append(ta->to_visit, obj);
1036 }
1037
1038 PyDoc_STRVAR(hv_reachable_doc,
1039 "HV.reachable(X:NodeSet, Y:NodeSet) -> NodeSet\n\
1040 \n\
1041 Return the set of objects reached via a path in the visible heap as\n\
1042 defined by HV, from some object in X, avoiding any object in Y.");
1043
1044 static PyObject *
hv_reachable(NyHeapViewObject * self,PyObject * args,PyObject * kwds)1045 hv_reachable(NyHeapViewObject *self, PyObject *args, PyObject *kwds)
1046 {
1047 RATravArg ta;
1048 static char *kwlist[] = {"start", "avoid", 0};
1049 if (!PyArg_ParseTupleAndKeywords(args, kwds, "O!O!:reachable", kwlist,
1050 NyNodeSet_TYPE, &ta.start,
1051 NyNodeSet_TYPE, &ta.avoid))
1052 return 0;
1053 ta.hv = self;
1054 ta.visited = hv_mutnodeset_new(self);
1055 ta.to_visit = PyList_New(0);
1056 if (!(ta.visited && ta.to_visit))
1057 goto err;
1058 if (NyNodeSet_iterate(ta.start, (visitproc)hv_ra_rec, &ta) == -1)
1059 goto err;
1060 while (PyList_Size(ta.to_visit)) {
1061 PyObject *obj = hv_PyList_Pop(ta.to_visit);
1062 if (!obj)
1063 goto err;
1064 if (hv_std_traverse(ta.hv, obj, (visitproc)hv_ra_rec, &ta) == -1) {
1065 Py_DECREF(obj);
1066 goto err;
1067 }
1068 Py_DECREF(obj);
1069 }
1070 if (hv_cleanup_mutset(ta.hv, ta.visited) == -1)
1071 goto err;
1072 Py_XDECREF(ta.to_visit);
1073 return (PyObject *)ta.visited;
1074 err:
1075 Py_XDECREF(ta.visited);
1076 Py_XDECREF(ta.to_visit);
1077 return 0;
1078 }
1079
1080 static int
hv_ra_rec_e(PyObject * obj,RATravArg * ta)1081 hv_ra_rec_e(PyObject *obj, RATravArg *ta)
1082 {
1083 int r;
1084 r = NyNodeSet_setobj(ta->visited, obj);
1085 if (r)
1086 return r < 0 ? r : 0;
1087 else {
1088 if (NyNodeSet_hasobj(ta->avoid, obj))
1089 return 0;
1090 return PyList_Append(ta->to_visit, obj);
1091 }
1092 }
1093
1094 PyDoc_STRVAR(hv_reachable_x_doc,
1095 "HV.reachable_x(X:NodeSet, Y:NodeSet) -> NodeSet\n\
1096 \n\
1097 Return the set of objects reached via a path in the visible heap as\n\
1098 defined by HV, from some object in X, avoiding any object in Y except\n\
1099 at the end of the path.");
1100
1101 static PyObject *
hv_reachable_x(NyHeapViewObject * self,PyObject * args,PyObject * kwds)1102 hv_reachable_x(NyHeapViewObject *self, PyObject *args, PyObject *kwds)
1103 {
1104 RATravArg ta;
1105 static char *kwlist[] = {"start", "avoid", 0};
1106 if (!PyArg_ParseTupleAndKeywords(args, kwds, "O!O!:reachable", kwlist,
1107 NyNodeSet_TYPE, &ta.start,
1108 NyNodeSet_TYPE, &ta.avoid))
1109 return 0;
1110 ta.hv = self;
1111 ta.visited = hv_mutnodeset_new(self);
1112 ta.to_visit = PyList_New(0);
1113 if (!(ta.visited && ta.to_visit))
1114 goto err;
1115 if (NyNodeSet_iterate(ta.start, (visitproc)hv_ra_rec_e, &ta) == -1)
1116 goto err;
1117 while (PyList_Size(ta.to_visit)) {
1118 PyObject *obj = hv_PyList_Pop(ta.to_visit);
1119 if (!obj)
1120 goto err;
1121 if (hv_std_traverse(ta.hv, obj, (visitproc)hv_ra_rec_e, &ta) == -1) {
1122 Py_DECREF(obj);
1123 goto err;
1124 }
1125 Py_DECREF(obj);
1126 }
1127 if (hv_cleanup_mutset(ta.hv, ta.visited) == -1)
1128 goto err;
1129 Py_XDECREF(ta.to_visit);
1130 return (PyObject *)ta.visited;
1131 err:
1132 Py_XDECREF(ta.visited);
1133 Py_XDECREF(ta.to_visit);
1134 return 0;
1135 }
1136
1137 static Py_ssize_t
hv_get_member_offset(PyTypeObject * type,char * member_name)1138 hv_get_member_offset(PyTypeObject *type, char *member_name)
1139 {
1140 PyObject *mro = type->tp_mro;
1141 if (mro) {
1142 Py_ssize_t i;
1143 for (i = 0; i < PyTuple_GET_SIZE(mro); i++) {
1144 PyObject *t = PyTuple_GET_ITEM(mro, i);
1145 if (PyType_Check(t)) {
1146 PyMemberDef *mp = ((PyTypeObject *)t)->tp_members;
1147 if (mp) {
1148 while (mp->name) {
1149 if (strcmp(mp->name, member_name) == 0)
1150 return mp->offset;
1151 mp++;
1152 }
1153 }
1154 }
1155 }
1156 }
1157 return -1;
1158 }
1159
1160 PyDoc_STRVAR(hv_register__hiding_tag__type_doc,
1161 "HV.register__hiding_tag__type(type)\n\
1162 \n\
1163 Register a type of objects that may be hidden from the heap view\n\
1164 defined by HV. The type must have a slot named _hiding_tag_. An object\n\
1165 that is an instance of the type, or of a subtype, is hidden when its\n\
1166 _hiding_tag_ is HV._hiding_tag_.");
1167
1168 static PyObject *
hv_register__hiding_tag__type(NyHeapViewObject * hv,PyObject * args,PyObject * kwds)1169 hv_register__hiding_tag__type(NyHeapViewObject *hv, PyObject *args, PyObject *kwds)
1170 {
1171 static char *kwlist[] = {"type", 0};
1172 PyTypeObject *type;
1173 ExtraType *xt;
1174 Py_ssize_t offs;
1175 if (!PyArg_ParseTupleAndKeywords(args, kwds, "O!:register_hiding_type", kwlist,
1176 &PyType_Type, &type))
1177 return NULL;
1178 offs = hv_get_member_offset(type, "_hiding_tag_");
1179 if (offs == -1) {
1180 PyErr_SetString(PyExc_ValueError,
1181 "register__hiding_tag__type: type has no '_hiding_tag_' slot");
1182 return 0;
1183 }
1184
1185 xt = hv_extra_type(hv, type);
1186 if (xt == &xt_error)
1187 return 0;
1188 if (xt->xt_trav_code == XT_HE || xt->xt_trav_code == XT_HI) {
1189 PyErr_SetString(PyExc_ValueError,
1190 "register__hiding_tag__type: type is already registered");
1191 return 0;
1192 }
1193 xt->xt_he_traverse = xt->xt_traverse;
1194 xt->xt_he_xt = xt;
1195 xt->xt_he_offs = offs;
1196 xt->xt_traverse = xt_he_traverse;
1197 xt->xt_trav_code = XT_HE;
1198 Py_INCREF(Py_None);
1199 return Py_None;
1200 }
1201
1202 PyDoc_STRVAR(hv_register_hidden_exact_type_doc,
1203 "HV.register_hidden_exact_type(type)\n\
1204 \n\
1205 Register a type of objects that should be hidden from the heap view\n\
1206 defined by HV. Objects of the exact type registered -- not including\n\
1207 subtypes -- will be hidden.\n\
1208 \n\
1209 See also: register__hiding_tag__type.");
1210
1211 static PyObject *
hv_register_hidden_exact_type(NyHeapViewObject * hv,PyObject * args,PyObject * kwds)1212 hv_register_hidden_exact_type(NyHeapViewObject *hv, PyObject *args, PyObject *kwds)
1213 {
1214 static char *kwlist[] = {"type", 0};
1215 PyTypeObject *type;
1216 ExtraType *xt;
1217 if (!PyArg_ParseTupleAndKeywords(args, kwds, "O!:register_hiding_type", kwlist,
1218 &PyType_Type, &type))
1219 return NULL;
1220 xt = hv_extra_type(hv, type);
1221 if (xt == &xt_error)
1222 return 0;
1223 if (xt->xt_trav_code == XT_HE || xt->xt_trav_code == XT_HI) {
1224 PyErr_SetString(PyExc_ValueError,
1225 "register_hidden_exact_type: type is already registered");
1226 return 0;
1227 }
1228 xt->xt_traverse = xt_no_traverse;
1229 xt->xt_trav_code = XT_HI;
1230 Py_INCREF(Py_None);
1231 return Py_None;
1232 }
1233
1234
1235
1236 PyDoc_STRVAR(hv_relate_doc,
1237 "HV.relate(src, tgt) -> relation structure\n\
1238 \n\
1239 Return a description of the relation between src and tgt. This is used\n\
1240 for descriptions of edges in paths.\n\
1241 \n\
1242 [The result is in a special format that I choose to not define here\n\
1243 since it is for special low-level use and subject to change.]");
1244
1245 static PyObject *
hv_relate(NyHeapViewObject * self,PyObject * args,PyObject * kwds)1246 hv_relate(NyHeapViewObject *self, PyObject *args, PyObject *kwds)
1247 {
1248 static char *kwlist[] = {"src", "tgt", 0};
1249 hv_relate_visit_arg crva;
1250 int i;
1251 PyObject *res = 0;
1252 if (!PyArg_ParseTupleAndKeywords(args, kwds, "OO:relate", kwlist,
1253 &crva.hr.src,
1254 &crva.hr.tgt))
1255 return NULL;
1256 crva.hr.flags = 0;
1257 crva.hr.hv = (void *)self;
1258 crva.hr.visit = hv_relate_visit;
1259 crva.err = 0;
1260 for (i = 0; i < NYHR_LIMIT; i++)
1261 crva.relas[i] = 0;
1262 if (hv_std_relate(&crva.hr) == -1 ||
1263 crva.err ||
1264 (!(res = PyTuple_New(NYHR_LIMIT)))) {
1265 goto retres;
1266 }
1267 for (i = 0; i < NYHR_LIMIT; i++) {
1268 PyObject *x;
1269 if (!crva.relas[i]) {
1270 x = PyTuple_New(0);
1271 } else {
1272 x = PyList_AsTuple(crva.relas[i]);
1273 }
1274 if (!x) {
1275 Py_DECREF(res);
1276 res = 0;
1277 goto retres;
1278 } else {
1279 PyTuple_SetItem(res, i, x);
1280 }
1281 }
1282 retres:
1283 for (i = 0; i < NYHR_LIMIT; i++)
1284 Py_XDECREF(crva.relas[i]);
1285 return res;
1286 }
1287
1288
1289 typedef struct {
1290 NyHeapViewObject *hv;
1291 NyNodeSetObject *hs;
1292 } HVRITravArg;
1293
1294
1295
1296 static int
hv_ss_visit(PyObject * obj,NyNodeSetObject * hs)1297 hv_ss_visit(PyObject *obj, NyNodeSetObject *hs)
1298 {
1299 if (NyNodeSet_setobj(hs, obj) == -1)
1300 return -1;
1301 return 0;
1302 }
1303
1304 static int
hv_relimg_trav(PyObject * obj,HVRITravArg * ta)1305 hv_relimg_trav(PyObject *obj, HVRITravArg *ta)
1306 {
1307 return hv_std_traverse(ta->hv, obj, (visitproc)hv_ss_visit, ta->hs);
1308 }
1309
1310 PyDoc_STRVAR(hv_relimg_doc,
1311 "HV.relimg(S:iterable) -> NodeSet\n\
1312 \n\
1313 Return the 'relational image of HV wrt S'. That is, the set of nodes\n\
1314 that are directly referred to from the nodes in S via the visible heap\n\
1315 reachability relation as defined by HV.");
1316
1317 static NyNodeSetObject *
hv_relimg(NyHeapViewObject * hv,PyObject * S)1318 hv_relimg(NyHeapViewObject *hv, PyObject *S)
1319 {
1320 HVRITravArg ta;
1321 ta.hv = hv;
1322 ta.hs = hv_mutnodeset_new(hv);
1323 if (!ta.hs)
1324 return 0;
1325 if (iterable_iterate(S, (visitproc)hv_relimg_trav, &ta) == -1)
1326 goto err;
1327 if (hv_cleanup_mutset(ta.hv, ta.hs) == -1)
1328 goto err;
1329 return ta.hs;
1330 err:
1331 Py_DECREF(ta.hs);
1332 return 0;
1333 }
1334
1335 typedef struct {
1336 NyHeapViewObject *hv;
1337 NyNodeSetObject *U, *S, *V;
1338 NyNodeGraphObject *P;
1339 NyNodeGraphObject *edgestoavoid;
1340 PyObject *u;
1341 int find_one_flag;
1342 } ShPathTravArg;
1343
1344
1345 static int
hv_shpath_inner(PyObject * v,ShPathTravArg * ta)1346 hv_shpath_inner(PyObject *v, ShPathTravArg *ta)
1347 {
1348 int r;
1349 if (ta->edgestoavoid) {
1350 NyNodeGraphEdge *lo, *hi;
1351 if (NyNodeGraph_Region(ta->edgestoavoid, ta->u, &lo, &hi) == -1)
1352 return -1;
1353 for (;lo < hi; lo++) {
1354 if (lo->tgt == v)
1355 return 0;
1356 }
1357 }
1358 r = NyNodeSet_hasobj(ta->S, v);
1359 if (r == -1)
1360 return r;
1361 if (r)
1362 return 0;
1363 r = NyNodeSet_setobj(ta->V, v);
1364 if (r == -1)
1365 return -1;
1366 if (!r || !ta->find_one_flag)
1367 if (NyNodeGraph_AddEdge(ta->P, v, ta->u) == -1)
1368 return -1;
1369 return 0;
1370 }
1371
1372
1373 static int
hv_shpath_outer(PyObject * u,ShPathTravArg * ta)1374 hv_shpath_outer(PyObject *u, ShPathTravArg *ta)
1375 {
1376 if ((void *) u == ta->hv ||
1377 (void *) u == ta->S ||
1378 (void *) u == ta->V ||
1379 (void *) u == ta->P ||
1380 (void *) u == ta->edgestoavoid ||
1381 (void *) u == ta->U)
1382 return 0;
1383 ta->u = u;
1384 return hv_std_traverse(ta->hv, u, (visitproc)hv_shpath_inner, ta);
1385 }
1386
1387 PyDoc_STRVAR(hv_shpathstep_doc,
1388 "HV.shpathstep(G:NodeGraph, U:NodeSet, S:NodeSet\n"
1389 " [,AvoidEdges:NodeGraph [,find_one:bool]]) -> NodeSet\n"
1390 "\n"
1391 "This method implements one step of a shortest path algorithm.\n"
1392 "The arguments are:\n"
1393 "\n"
1394 " G Updated by the method, with the edges from nodes in the\n"
1395 " source set to the new nodes visited.\n"
1396 " U The source set for this step.\n"
1397 " S The set of already visited nodes.\n"
1398 " AvoidEdges Edges to avoid.\n"
1399 " find_one If True, at most one edge will be found from each node\n"
1400 " in the source set. Normally, all edges will be found.\n"
1401 "\n"
1402 "Return value: The new nodes visited. This may be used for the\n"
1403 " U argument the next time the method is called.\n"
1404 "\n"
1405 "See also: shpgraph_algorithm in Path.py.");
1406
1407 static PyObject *
hv_shpathstep(NyHeapViewObject * self,PyObject * args,PyObject * kwds)1408 hv_shpathstep(NyHeapViewObject *self, PyObject *args, PyObject *kwds)
1409 {
1410 ShPathTravArg ta;
1411 static char *kwlist[] = {"G", "U", "S", "AvoidEdges", "find_one", 0};
1412 ta.find_one_flag = 0;
1413 ta.edgestoavoid = 0;
1414 if (!PyArg_ParseTupleAndKeywords(args, kwds, "O!O!O!|O!i:shpathstep", kwlist,
1415 &NyNodeGraph_Type, &ta.P,
1416 NyNodeSet_TYPE, &ta.U,
1417 NyNodeSet_TYPE, &ta.S,
1418 &NyNodeGraph_Type, &ta.edgestoavoid,
1419 &ta.find_one_flag))
1420 return 0;
1421 ta.hv = self;
1422 if (ta.edgestoavoid && ta.edgestoavoid->used_size == 0)
1423 ta.edgestoavoid = 0;
1424 ta.V = hv_mutnodeset_new(self);
1425 if (!(ta.V))
1426 goto err;
1427 if (NyNodeSet_iterate(ta.U, (visitproc)hv_shpath_outer, &ta) == -1)
1428 goto err;
1429 return (PyObject *)ta.V;
1430 err:
1431 Py_XDECREF(ta.V);
1432 return 0;
1433 }
1434
1435
1436
1437 PyDoc_STRVAR(hv_limitframe_doc,
1438 "HV.limitframe : frame | None\n\
1439 \n\
1440 The traversal limiting frame.\n\
1441 \n\
1442 If limitframe is set to a frame object, the frames that are more\n\
1443 recently entered than limitframe will be hidden when traversing the\n\
1444 heap from the root RootState. It will start traversing from limitframe\n\
1445 rather than from the most recent frame as it would otherwise do.");
1446
1447 static int
hv_set_limitframe(NyHeapViewObject * self,PyObject * arg,void * unused)1448 hv_set_limitframe(NyHeapViewObject *self, PyObject *arg, void *unused)
1449 {
1450 PyObject *orf = self->limitframe;
1451 if (arg == Py_None) {
1452 self->limitframe = 0;
1453 } else if (PyFrame_Check(arg)) {
1454 self->limitframe = arg;
1455 Py_INCREF(arg);
1456 } else {
1457 PyErr_SetString(PyExc_TypeError, "set_limitframe: frame or None expected");
1458 return -1;
1459 }
1460 Py_XDECREF(orf);
1461 return 0;
1462 }
1463
1464 static PyObject *
hv_get_limitframe(NyHeapViewObject * self,void * unused)1465 hv_get_limitframe(NyHeapViewObject *self, void *unused)
1466 {
1467 PyObject *r = self->limitframe;
1468 if (!r)
1469 r = Py_None;
1470 Py_INCREF(r);
1471 return r;
1472 }
1473
1474 PyDoc_STRVAR(hv_update_dictowners_doc,
1475 "HV.update_dictowners(owners:NodeGraph)\n\
1476 \n\
1477 Update owners with ownership edges.\n\
1478 \n\
1479 The dict owners graph will be updated with an edge from each dict\n\
1480 object in the heap, to either its owner or to None.");
1481
1482 PyObject *
hv_update_dictowners(NyHeapViewObject * self,PyObject * args)1483 hv_update_dictowners(NyHeapViewObject *self, PyObject *args)
1484 {
1485 NyNodeGraphObject *rg;
1486 if (!PyArg_ParseTuple(args, "O!:update_dictowners",
1487 &NyNodeGraph_Type, &rg))
1488 return NULL;
1489 if (hv_cli_dictof_update(self, rg) == -1)
1490 return 0;
1491 Py_INCREF(Py_None);
1492 return Py_None;
1493 }
1494
1495 /* Code specific for update ... */
1496
1497 typedef struct {
1498 NyHeapViewObject *hv;
1499 NyNodeSetObject *targetset, *markset, *outset;
1500 NyNodeGraphObject *rg;
1501 PyObject *to_visit;
1502 PyObject *sentinel;
1503 NyNodeSetObject *trace_set;
1504 PyObject *trace_stack;
1505 PyObject *trace_res;
1506 int trav_stat;
1507 } RetaTravArg;
1508
1509
1510 static int
rg_rec(PyObject * obj,RetaTravArg * ta)1511 rg_rec(PyObject *obj, RetaTravArg *ta) {
1512 if (obj == (PyObject *)ta->rg || obj == ta->hv->root)
1513 return 0;
1514 return PyList_Append(ta->to_visit, obj);
1515 }
1516
1517
1518 PyDoc_STRVAR(hv_update_referrers_doc,
1519 "HV.update_referrers(X:NodeGraph, Y:NodeSet)\n"
1520 "\n"
1521 "Update referrer graph X for Y.\n"
1522 "\n"
1523 "The visible heap defined by HV will be traversed from the root of HV\n"
1524 "so that the edges of every path from the root to nodes in Y will be\n"
1525 "represented, inverted, in X.");
1526
1527 PyObject *
hv_update_referrers(NyHeapViewObject * self,PyObject * args)1528 hv_update_referrers(NyHeapViewObject *self, PyObject *args)
1529 {
1530 RetaTravArg ta;
1531 if (!PyArg_ParseTuple(args, "O!O!:update_referrers",
1532 &NyNodeGraph_Type, &ta.rg,
1533 NyNodeSet_TYPE, &ta.targetset))
1534 return NULL;
1535
1536 PyObject *ret = 0;
1537
1538 ta.hv = self;
1539 ta.markset = hv_mutnodeset_new(self);
1540 ta.outset = hv_mutnodeset_new(self);
1541 ta.trace_set = hv_mutnodeset_new(self);
1542 ta.to_visit = PyList_New(0);
1543 ta.trace_stack = PyList_New(0);
1544 ta.trace_res = PyList_New(0);
1545 ta.sentinel = PyObject_New(PyObject, &PyBaseObject_Type);
1546
1547 if (!(ta.markset && ta.outset && ta.trace_set && ta.to_visit &&
1548 ta.trace_stack && ta.trace_res && ta.sentinel))
1549 goto err;
1550
1551 if (PyList_Append(ta.to_visit, ta.hv->root) == -1)
1552 goto err;
1553 while (PyList_Size(ta.to_visit)) {
1554 PyObject *obj = hv_PyList_Pop(ta.to_visit);
1555 if (!obj)
1556 goto err;
1557 if (obj == ta.sentinel) {
1558 // Recurse out
1559 PyObject *last_obj = hv_PyList_Pop(ta.trace_stack);
1560 PyObject *last_res = hv_PyList_Pop(ta.trace_res);
1561 if (!(last_obj && last_res))
1562 goto err_inner;
1563 if (NyNodeSet_clrobj(ta.trace_set, last_obj) == -1)
1564 goto err_inner_inner;
1565 if (last_res == Py_True) {
1566 if (Py_REFCNT(last_obj) > 2)
1567 if (NyNodeSet_setobj(ta.outset, last_obj) == -1)
1568 goto err_inner_inner;
1569 Py_ssize_t trace_len = PyList_Size(ta.trace_stack);
1570 if (trace_len) {
1571 PyObject *last_last_obj = PyList_GetItem(ta.trace_stack, trace_len - 1);
1572 if (!last_last_obj)
1573 goto err_inner_inner;
1574 if (NyNodeGraph_AddEdge(ta.rg, last_obj, last_last_obj) == -1)
1575 goto err_inner_inner;
1576 Py_INCREF(Py_True);
1577 if (PyList_SetItem(ta.trace_res, trace_len - 1, Py_True) == -1)
1578 goto err_inner_inner;
1579 }
1580 } else if (Py_REFCNT(last_obj) > 2)
1581 if (NyNodeSet_setobj(ta.markset, last_obj) == -1)
1582 goto err_inner_inner;
1583
1584 Py_DECREF(last_obj);
1585 Py_DECREF(last_res);
1586 goto next;
1587
1588 err_inner_inner:
1589 Py_DECREF(last_obj);
1590 Py_DECREF(last_res);
1591 goto err_inner;
1592 } else {
1593 // Recurse in
1594 int is_target = -1;
1595 ExtraType *xt = hv_extra_type(ta.hv, Py_TYPE(obj));
1596
1597 if (xt->xt_trav_code == XT_NO) {
1598 is_target = ta.targetset ? NyNodeSet_hasobj(ta.targetset, obj) :
1599 obj != ta.hv->root;
1600 if (!is_target)
1601 goto next;
1602 if (is_target == -1)
1603 goto err_inner;
1604 }
1605
1606 if (NyNodeSet_hasobj(ta.markset, obj))
1607 goto next;
1608
1609 int in_trace = NyNodeSet_setobj(ta.trace_set, obj);
1610 if (in_trace == -1)
1611 goto err_inner;
1612
1613 int no_recurse = in_trace || NyNodeSet_hasobj(ta.outset, obj);
1614 if (no_recurse == -1)
1615 goto err_inner;
1616
1617 int do_trace = no_recurse;
1618 if (!do_trace) {
1619 if (is_target == -1) {
1620 is_target = ta.targetset ? NyNodeSet_hasobj(ta.targetset, obj) :
1621 obj != ta.hv->root;
1622 if (is_target == -1)
1623 goto err_inner;
1624 }
1625 do_trace = is_target;
1626 }
1627
1628 PyObject *res = do_trace ? Py_True : Py_False;
1629
1630 if (PyList_Append(ta.trace_stack, obj) == -1)
1631 goto err_inner;
1632 if (PyList_Append(ta.trace_res, res) == -1)
1633 goto err_inner;
1634
1635 if (PyList_Append(ta.to_visit, ta.sentinel) == -1)
1636 goto err_inner;
1637
1638 if (!no_recurse)
1639 if (xt_traverse(xt, obj, (visitproc)rg_rec, &ta) == -1)
1640 goto err_inner;
1641 }
1642
1643 next:
1644 Py_DECREF(obj);
1645 continue;
1646
1647 err_inner:
1648 Py_DECREF(obj);
1649 goto err;
1650 }
1651
1652 ret = Py_None;
1653
1654 err:
1655 Py_XDECREF(ta.markset);
1656 Py_XDECREF(ta.outset);
1657 Py_XDECREF(ta.trace_set);
1658 Py_XDECREF(ta.to_visit);
1659 Py_XDECREF(ta.trace_stack);
1660 Py_XDECREF(ta.trace_res);
1661 Py_XDECREF(ta.sentinel);
1662
1663 Py_XINCREF(ret);
1664 return ret;
1665 }
1666
1667 PyDoc_STRVAR(hv_update_referrers_completely_doc,
1668 "HV.update_referrers_completely(X:nodegraph)\n\
1669 \n\
1670 Update referrer graph X 'completely'.\n\
1671 \n\
1672 [Experimental algorithm that updates X with the referrers to all\n\
1673 objects in the heap (of visible nodes as defined in HV). It is not\n\
1674 normally used.]");
1675
1676 typedef struct {
1677 NyHeapViewObject *hv;
1678 NyNodeGraphObject *rg;
1679 PyObject *retainer;
1680 int num;
1681 } URCOTravArg;
1682
1683 int dummy;
1684
1685 static int
urco_traverse(PyObject * obj,URCOTravArg * ta)1686 urco_traverse(PyObject *obj, URCOTravArg *ta)
1687 {
1688 if (hv_is_obj_hidden(ta->hv, obj))
1689 return 0;
1690 if (NyNodeGraph_AddEdge(ta->rg, obj, ta->retainer) == -1)
1691 return -1;
1692 ta->num++;
1693 return 0;
1694 }
1695
1696 PyObject *
hv_update_referrers_completely(NyHeapViewObject * self,PyObject * args)1697 hv_update_referrers_completely(NyHeapViewObject *self, PyObject *args)
1698 {
1699 URCOTravArg ta;
1700 PyObject *objects=0, *result=0, *_hiding_tag_=0;
1701 Py_ssize_t len, i;
1702 ta.hv = self;
1703 _hiding_tag_ = self->_hiding_tag_;
1704 self->_hiding_tag_ = Py_None;
1705 if (!PyArg_ParseTuple(args, "O!:update_referrers_completely",
1706 &NyNodeGraph_Type, &ta.rg))
1707 goto err;
1708 objects = gc_get_objects();
1709 if (!objects)
1710 goto err;
1711 len = PyList_Size(objects);
1712 if (len == -1)
1713 goto err;
1714 NyNodeGraph_Clear(ta.rg);
1715 for (i = 0; i < len; i++) {
1716 PyObject *retainer = PyList_GET_ITEM(objects, i);
1717 ta.num = 0;
1718 if (retainer == (void *)ta.rg)
1719 continue;
1720 if (NyNodeGraph_Check(retainer))
1721 continue; /* Note 22/11 2004 */
1722 else if ((NyNodeSet_Check(retainer) &&
1723 ((NyNodeSetObject *)retainer)->_hiding_tag_ == _hiding_tag_))
1724 ta.retainer = Py_None;
1725 else
1726 ta.retainer = retainer;
1727 if (hv_std_traverse(ta.hv, retainer, (visitproc)urco_traverse, &ta) == -1)
1728 goto err;
1729 }
1730 result = Py_None;
1731 Py_INCREF(result);
1732 err:
1733 self->_hiding_tag_ = _hiding_tag_;
1734 Py_XDECREF(objects);
1735 return result;
1736 }
1737
1738 static PyMethodDef hv_methods[] = {
1739 {"cli_and", (PyCFunction)hv_cli_and, METH_VARARGS, hv_cli_and_doc},
1740 {"cli_dictof", (PyCFunction)hv_cli_dictof, METH_VARARGS, hv_cli_dictof_doc},
1741 {"cli_findex", (PyCFunction)hv_cli_findex, METH_VARARGS, hv_cli_findex_doc},
1742 {"cli_id", (PyCFunction)hv_cli_id, METH_VARARGS, hv_cli_id_doc},
1743 {"cli_idset", (PyCFunction)hv_cli_idset, METH_VARARGS, hv_cli_idset_doc},
1744 {"cli_indisize", (PyCFunction)hv_cli_indisize, METH_VARARGS, hv_cli_indisize_doc},
1745 {"cli_inrel", (PyCFunction)hv_cli_inrel, METH_VARARGS, hv_cli_inrel_doc},
1746 {"cli_none", (PyCFunction)hv_cli_none, METH_NOARGS, hv_cli_none_doc},
1747 {"cli_prod", (PyCFunction)hv_cli_prod, METH_VARARGS, hv_cli_prod_doc},
1748 {"cli_rcs", (PyCFunction)hv_cli_rcs, METH_VARARGS, hv_cli_rcs_doc},
1749 {"cli_type", (PyCFunction)hv_cli_type, METH_NOARGS, hv_cli_type_doc},
1750 {"cli_user_defined", (PyCFunction)hv_cli_user_defined, METH_VARARGS|METH_KEYWORDS, hv_cli_user_defined_doc},
1751 {"delete_extra_type", (PyCFunction)hv_delete_extra_type, METH_O, hv_delete_extra_type_doc},
1752 {"indisize_sum", (PyCFunction)hv_indisize_sum, METH_O, hv_indisize_sum_doc},
1753 {"heap", (PyCFunction)hv_heap, METH_NOARGS, hv_heap_doc},
1754 {"numedges", (PyCFunction)hv_numedges, METH_VARARGS, hv_numedges_doc},
1755 {"reachable", (PyCFunction)hv_reachable, METH_VARARGS|METH_KEYWORDS, hv_reachable_doc},
1756 {"reachable_x", (PyCFunction)hv_reachable_x, METH_VARARGS|METH_KEYWORDS, hv_reachable_x_doc},
1757 {"register_hidden_exact_type", (PyCFunction)hv_register_hidden_exact_type, METH_VARARGS|METH_KEYWORDS,
1758 hv_register_hidden_exact_type_doc},
1759 {"register__hiding_tag__type", (PyCFunction)hv_register__hiding_tag__type, METH_VARARGS|METH_KEYWORDS,
1760 hv_register__hiding_tag__type_doc},
1761 {"relate", (PyCFunction)hv_relate, METH_VARARGS|METH_KEYWORDS, hv_relate_doc},
1762 {"relimg", (PyCFunction)hv_relimg, METH_O, hv_relimg_doc},
1763 {"shpathstep", (PyCFunction)hv_shpathstep, METH_VARARGS|METH_KEYWORDS, hv_shpathstep_doc},
1764 {"update_dictowners", (PyCFunction)hv_update_dictowners, METH_VARARGS,
1765 hv_update_dictowners_doc},
1766 {"update_referrers", (PyCFunction)hv_update_referrers, METH_VARARGS,
1767 hv_update_referrers_doc},
1768 {"update_referrers_completely", (PyCFunction)hv_update_referrers_completely, METH_VARARGS,
1769 hv_update_referrers_completely_doc},
1770
1771 {0} /* sentinel */
1772 };
1773
1774 #define OFF(x) offsetof(NyHeapViewObject, x)
1775
1776
1777 static PyMemberDef hv_members[] = {
1778 {"_hiding_tag_", T_OBJECT, OFF(_hiding_tag_), 0,
1779 "HV._hiding_tag_\n\
1780 \n\
1781 The hiding tag defining what objects are hidden from the view defined\n\
1782 by HV. Objects that contain a _hiding_tag_ object which is identical\n\
1783 to HV._hiding_tag_, will be hidden from view, in the following cases:\n\
1784 \n\
1785 o The object is of a type that has been registered for hiding\n\
1786 via _hiding_tag, or is of a subtype of such a type.\n\
1787 \n\
1788 o The object is of instance type. Such an object will be checked\n\
1789 for a _hiding_tag_ item in its __dict__.\n\
1790 "},
1791 {"is_hiding_calling_interpreter", T_UBYTE, OFF(is_hiding_calling_interpreter), 0,
1792 "HV.is_hiding_calling_interpreter : boolean kind\n\
1793 \n\
1794 If True, the data of the interpreter using the HV will be hidden from\n\
1795 the heap view as seen from RootState.\n\
1796 \n\
1797 This is used when multiple Python interpreters are used. One\n\
1798 interpreter will be monitoring the operation of the other\n\
1799 interpreter(s). It would set is_hiding_calling_interpreter to True in\n\
1800 the HV it is using. Its own data will then be hidden from view, making\n\
1801 memory leak detection more practical."},
1802
1803 {"root", T_OBJECT, OFF(root), 0,
1804 "HV.root\n\
1805 \n\
1806 An object that is used as the starting point when traversing the\n\
1807 heap. It is normally set to the special RootState object, which has\n\
1808 special functionality for finding the objects in the internals of the\n\
1809 Python interpreter structures. It can be set to any other object,\n\
1810 especially for test purposes.\n\
1811 \n\
1812 See also: RootState"},
1813 {"static_types", T_OBJECT , OFF(static_types), READONLY,
1814 "HV.static_types : NodeSet, read only\n\
1815 \n\
1816 The 'static types' that have been found.\n\
1817 \n\
1818 The static types are the type objects that are not heap allocated, but\n\
1819 are defined directly in C code. HeapView searches for these among all\n\
1820 reachable objects (at a suitable time or as needed)."},
1821
1822
1823 {0} /* Sentinel */
1824 };
1825
1826 #undef OFF
1827
1828 static PyGetSetDef hv_getset[] = {
1829 {"limitframe", (getter)hv_get_limitframe, (setter)hv_set_limitframe, hv_limitframe_doc},
1830 {0}
1831 };
1832
1833
1834 PyTypeObject NyHeapView_Type = {
1835 PyVarObject_HEAD_INIT(NULL, 0)
1836 .tp_name = "guppy.heapy.heapyc.HeapView",
1837 .tp_basicsize = sizeof(NyHeapViewObject),
1838 .tp_dealloc = (destructor)hv_dealloc,
1839 .tp_getattro = PyObject_GenericGetAttr,
1840 .tp_flags = Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_BASETYPE,
1841 .tp_doc = hv_doc,
1842 .tp_traverse = (traverseproc)hv_gc_traverse,
1843 .tp_clear = (inquiry)hv_gc_clear,
1844 .tp_methods = hv_methods,
1845 .tp_members = hv_members,
1846 .tp_getset = hv_getset,
1847 .tp_alloc = PyType_GenericAlloc,
1848 .tp_new = hv_new,
1849 .tp_free = PyObject_GC_Del,
1850 };
1851