Modules/gcmodule.c

   1 /*
   2
   3   Reference Cycle Garbage Collection
   4   ==================================
   5
   6   Neil Schemenauer <nas@arctrix.com>
   7
   8   Based on a post on the python-dev list.  Ideas from Guido van Rossum,
   9   Eric Tiedemann, and various others.
  10
  11   http://www.arctrix.com/nas/python/gc/
  12   http://www.python.org/pipermail/python-dev/2000-March/003869.html
  13   http://www.python.org/pipermail/python-dev/2000-March/004010.html
  14   http://www.python.org/pipermail/python-dev/2000-March/004022.html
  15
  16   For a highlevel view of the collection process, read the collect
  17   function.
  18
  19 */
  20
  21 #include "Python.h"
  22
  23 #ifdef WITH_CYCLE_GC
  24
  25 /* Get an object's GC head */
  26 #define AS_GC(o) ((PyGC_Head *)(o)-1)
  27
  28 /* Get the object given the GC head */
  29 #define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))
  30
  31
  32 /*** Global GC state ***/
  33
  34 /* linked lists of container objects */
  35 PyGC_Head _PyGC_generation0 = {{&_PyGC_generation0, &_PyGC_generation0, 0}};
  36 static PyGC_Head generation1 = {{&generation1, &generation1, 0}};
  37 static PyGC_Head generation2 = {{&generation2, &generation2, 0}};
  38 static int generation = 0; /* current generation being collected */
  39
  40 /* collection frequencies, XXX tune these */
  41 static int enabled = 1; /* automatic collection enabled? */
  42 static int threshold0 = 700; /* net new containers before collection */
  43 static int threshold1 = 10;  /* generation0 collections before collecting 1 */
  44 static int threshold2 = 10;  /* generation1 collections before collecting 2 */
  45
  46 /* net new objects allocated since last collection */
  47 static int allocated;
  48
  49 /* true if we are currently running the collector */
  50 static int collecting;
  51
  52 /* set for debugging information */
  53 #define DEBUG_STATS             (1<<0) /* print collection statistics */
  54 #define DEBUG_COLLECTABLE       (1<<1) /* print collectable objects */
  55 #define DEBUG_UNCOLLECTABLE     (1<<2) /* print uncollectable objects */
  56 #define DEBUG_INSTANCES         (1<<3) /* print instances */
  57 #define DEBUG_OBJECTS           (1<<4) /* print other objects */
  58 #define DEBUG_SAVEALL           (1<<5) /* save all garbage in gc.garbage */
  59 #define DEBUG_LEAK              DEBUG_COLLECTABLE | \
  60                                 DEBUG_UNCOLLECTABLE | \
  61                                 DEBUG_INSTANCES | \
  62                                 DEBUG_OBJECTS | \
  63                                 DEBUG_SAVEALL
  64 static int debug;
  65
  66 /* Special gc_refs value */
  67 #define GC_MOVED  -123
  68
  69 /* list of uncollectable objects */
  70 static PyObject *garbage;
  71
  72 /* Python string to use if unhandled exception occurs */
  73 static PyObject *gc_str;
  74
  75 /*** list functions ***/
  76
  77 static void
  78 gc_list_init(PyGC_Head *list)
  79 {
  80         list->gc.gc_prev = list;
  81         list->gc.gc_next = list;
  82 }
  83
  84 static void
  85 gc_list_append(PyGC_Head *node, PyGC_Head *list)
  86 {
  87         node->gc.gc_next = list;
  88         node->gc.gc_prev = list->gc.gc_prev;
  89         node->gc.gc_prev->gc.gc_next = node;
  90         list->gc.gc_prev = node;
  91 }
  92
  93 static void
  94 gc_list_remove(PyGC_Head *node)
  95 {
  96         node->gc.gc_prev->gc.gc_next = node->gc.gc_next;
  97         node->gc.gc_next->gc.gc_prev = node->gc.gc_prev;
  98         node->gc.gc_next = NULL; /* object is not currently tracked */
  99 }
 100
 101 static void
 102 gc_list_move(PyGC_Head *from, PyGC_Head *to)
 103 {
 104         if (from->gc.gc_next == from) {
 105                 /* empty from list */
 106                 gc_list_init(to);
 107         }
 108         else {
 109                 to->gc.gc_next = from->gc.gc_next;
 110                 to->gc.gc_next->gc.gc_prev = to;
 111                 to->gc.gc_prev = from->gc.gc_prev;
 112                 to->gc.gc_prev->gc.gc_next = to;
 113         }
 114         gc_list_init(from);
 115 }
 116
 117 /* append a list onto another list, from becomes an empty list */
 118 static void
 119 gc_list_merge(PyGC_Head *from, PyGC_Head *to)
 120 {
 121         PyGC_Head *tail;
 122         if (from->gc.gc_next != from) {
 123                 tail = to->gc.gc_prev;
 124                 tail->gc.gc_next = from->gc.gc_next;
 125                 tail->gc.gc_next->gc.gc_prev = tail;
 126                 to->gc.gc_prev = from->gc.gc_prev;
 127                 to->gc.gc_prev->gc.gc_next = to;
 128         }
 129         gc_list_init(from);
 130 }
 131
 132 static long
 133 gc_list_size(PyGC_Head *list)
 134 {
 135         PyGC_Head *gc;
 136         long n = 0;
 137         for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
 138                 n++;
 139         }
 140         return n;
 141 }
 142
 143 /*** end of list stuff ***/
 144
 145
 146
 147 /* Set all gc_refs = ob_refcnt */
 148 static void
 149 update_refs(PyGC_Head *containers)
 150 {
 151         PyGC_Head *gc = containers->gc.gc_next;
 152         for (; gc != containers; gc=gc->gc.gc_next) {
 153                 gc->gc.gc_refs = FROM_GC(gc)->ob_refcnt;
 154         }
 155 }
 156
 157 static int
 158 visit_decref(PyObject *op, void *data)
 159 {
 160         if (op && PyObject_IS_GC(op)) {
 161                 PyGC_Head *gc = AS_GC(op);
 162                 if (gc->gc.gc_next != NULL)
 163                         AS_GC(op)->gc.gc_refs--;
 164         }
 165         return 0;
 166 }
 167
 168 /* Subtract internal references from gc_refs */
 169 static void
 170 subtract_refs(PyGC_Head *containers)
 171 {
 172         traverseproc traverse;
 173         PyGC_Head *gc = containers->gc.gc_next;
 174         for (; gc != containers; gc=gc->gc.gc_next) {
 175                 traverse = FROM_GC(gc)->ob_type->tp_traverse;
 176                 (void) traverse(FROM_GC(gc),
 177                                (visitproc)visit_decref,
 178                                NULL);
 179         }
 180 }
 181
 182 /* Append objects with gc_refs > 0 to roots list */
 183 static void
 184 move_roots(PyGC_Head *containers, PyGC_Head *roots)
 185 {
 186         PyGC_Head *next;
 187         PyGC_Head *gc = containers->gc.gc_next;
 188         while (gc != containers) {
 189                 next = gc->gc.gc_next;
 190                 if (gc->gc.gc_refs > 0) {
 191                         gc_list_remove(gc);
 192                         gc_list_append(gc, roots);
 193                         gc->gc.gc_refs = GC_MOVED;
 194                 }
 195                 gc = next;
 196         }
 197 }
 198
 199 static int
 200 visit_move(PyObject *op, PyGC_Head *tolist)
 201 {
 202         if (PyObject_IS_GC(op)) {
 203                 PyGC_Head *gc = AS_GC(op);
 204                 if (gc->gc.gc_next != NULL && gc->gc.gc_refs != GC_MOVED) {
 205                         gc_list_remove(gc);
 206                         gc_list_append(gc, tolist);
 207                         gc->gc.gc_refs = GC_MOVED;
 208                 }
 209         }
 210         return 0;
 211 }
 212
 213 /* Move objects referenced from reachable to reachable set. */
 214 static void
 215 move_root_reachable(PyGC_Head *reachable)
 216 {
 217         traverseproc traverse;
 218         PyGC_Head *gc = reachable->gc.gc_next;
 219         for (; gc != reachable; gc=gc->gc.gc_next) {
 220                 /* careful, reachable list is growing here */
 221                 PyObject *op = FROM_GC(gc);
 222                 traverse = op->ob_type->tp_traverse;
 223                 (void) traverse(op,
 224                                (visitproc)visit_move,
 225                                (void *)reachable);
 226         }
 227 }
 228
 229 /* return true of object has a finalization method */
 230 static int
 231 has_finalizer(PyObject *op)
 232 {
 233         static PyObject *delstr = NULL;
 234         if (delstr == NULL) {
 235                 delstr = PyString_InternFromString("__del__");
 236                 if (delstr == NULL)
 237                         Py_FatalError("PyGC: can't initialize __del__ string");
 238         }
 239         return (PyInstance_Check(op) ||
 240                 PyType_HasFeature(op->ob_type, Py_TPFLAGS_HEAPTYPE))
 241                && PyObject_HasAttr(op, delstr);
 242 }
 243
 244 /* Move all objects with finalizers (instances with __del__) */
 245 static void
 246 move_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
 247 {
 248         PyGC_Head *next;
 249         PyGC_Head *gc = unreachable->gc.gc_next;
 250         for (; gc != unreachable; gc=next) {
 251                 PyObject *op = FROM_GC(gc);
 252                 next = gc->gc.gc_next;
 253                 if (has_finalizer(op)) {
 254                         gc_list_remove(gc);
 255                         gc_list_append(gc, finalizers);
 256                 }
 257         }
 258 }
 259
 260 /* Move objects referenced from roots to roots */
 261 static void
 262 move_finalizer_reachable(PyGC_Head *finalizers)
 263 {
 264         traverseproc traverse;
 265         PyGC_Head *gc = finalizers->gc.gc_next;
 266         for (; gc != finalizers; gc=gc->gc.gc_next) {
 267                 /* careful, finalizers list is growing here */
 268                 traverse = FROM_GC(gc)->ob_type->tp_traverse;
 269                 (void) traverse(FROM_GC(gc),
 270                                (visitproc)visit_move,
 271                                (void *)finalizers);
 272         }
 273 }
 274
 275 static void
 276 debug_instance(char *msg, PyInstanceObject *inst)
 277 {
 278         char *cname;
 279         /* simple version of instance_repr */
 280         PyObject *classname = inst->in_class->cl_name;
 281         if (classname != NULL && PyString_Check(classname))
 282                 cname = PyString_AsString(classname);
 283         else
 284                 cname = "?";
 285         PySys_WriteStderr("gc: %.100s <%.100s instance at %p>\n",
 286                           msg, cname, inst);
 287 }
 288
 289 static void
 290 debug_cycle(char *msg, PyObject *op)
 291 {
 292         if ((debug & DEBUG_INSTANCES) && PyInstance_Check(op)) {
 293                 debug_instance(msg, (PyInstanceObject *)op);
 294         }
 295         else if (debug & DEBUG_OBJECTS) {
 296                 PySys_WriteStderr("gc: %.100s <%.100s %p>\n",
 297                                   msg, op->ob_type->tp_name, op);
 298         }
 299 }
 300
 301 /* Handle uncollectable garbage (cycles with finalizers). */
 302 static void
 303 handle_finalizers(PyGC_Head *finalizers, PyGC_Head *old)
 304 {
 305         PyGC_Head *gc;
 306         if (garbage == NULL) {
 307                 garbage = PyList_New(0);
 308         }
 309         for (gc = finalizers->gc.gc_next; gc != finalizers;
 310                         gc = finalizers->gc.gc_next) {
 311                 PyObject *op = FROM_GC(gc);
 312                 if ((debug & DEBUG_SAVEALL) || has_finalizer(op)) {
 313                         /* If SAVEALL is not set then just append objects with
 314                          * finalizers to the list of garbage.  All objects in
 315                          * the finalizers list are reachable from those
 316                          * objects. */
 317                         PyList_Append(garbage, op);
 318                 }
 319                 /* object is now reachable again */
 320                 gc_list_remove(gc);
 321                 gc_list_append(gc, old);
 322         }
 323 }
 324
 325 /* Break reference cycles by clearing the containers involved.  This is
 326  * tricky business as the lists can be changing and we don't know which
 327  * objects may be freed.  It is possible I screwed something up here. */
 328 static void
 329 delete_garbage(PyGC_Head *unreachable, PyGC_Head *old)
 330 {
 331         inquiry clear;
 332
 333         while (unreachable->gc.gc_next != unreachable) {
 334                 PyGC_Head *gc = unreachable->gc.gc_next;
 335                 PyObject *op = FROM_GC(gc);
 336                 if (debug & DEBUG_SAVEALL) {
 337                         PyList_Append(garbage, op);
 338                 }
 339                 else {
 340                         if ((clear = op->ob_type->tp_clear) != NULL) {
 341                                 Py_INCREF(op);
 342                                 clear((PyObject *)op);
 343                                 Py_DECREF(op);
 344                         }
 345                 }
 346                 if (unreachable->gc.gc_next == gc) {
 347                         /* object is still alive, move it, it may die later */
 348                         gc_list_remove(gc);
 349                         gc_list_append(gc, old);
 350                 }
 351         }
 352 }
 353
 354 /* This is the main function.  Read this to understand how the
 355  * collection process works. */
 356 static long
 357 collect(PyGC_Head *young, PyGC_Head *old)
 358 {
 359         long n = 0;
 360         long m = 0;
 361         PyGC_Head reachable;
 362         PyGC_Head unreachable;
 363         PyGC_Head finalizers;
 364         PyGC_Head *gc;
 365
 366         if (debug & DEBUG_STATS) {
 367                 PySys_WriteStderr(
 368                         "gc: collecting generation %d...\n"
 369                         "gc: objects in each generation: %ld %ld %ld\n",
 370                         generation,
 371                         gc_list_size(&_PyGC_generation0),
 372                         gc_list_size(&generation1),
 373                         gc_list_size(&generation2));
 374         }
 375
 376         /* Using ob_refcnt and gc_refs, calculate which objects in the
 377          * container set are reachable from outside the set (ie. have a
 378          * refcount greater than 0 when all the references within the
 379          * set are taken into account */
 380         update_refs(young);
 381         subtract_refs(young);
 382
 383         /* Move everything reachable from outside the set into the
 384          * reachable set (ie. gc_refs > 0).  Next, move everything
 385          * reachable from objects in the reachable set. */
 386         gc_list_init(&reachable);
 387         move_roots(young, &reachable);
 388         move_root_reachable(&reachable);
 389
 390         /* move unreachable objects to a temporary list, new objects can be
 391          * allocated after this point */
 392         gc_list_init(&unreachable);
 393         gc_list_move(young, &unreachable);
 394
 395         /* move reachable objects to next generation */
 396         gc_list_merge(&reachable, old);
 397
 398         /* Move objects reachable from finalizers, we can't safely delete
 399          * them.  Python programmers should take care not to create such
 400          * things.  For Python finalizers means instance objects with
 401          * __del__ methods. */
 402         gc_list_init(&finalizers);
 403         move_finalizers(&unreachable, &finalizers);
 404         move_finalizer_reachable(&finalizers);
 405
 406         /* Collect statistics on collectable objects found and print
 407          * debugging information. */
 408         for (gc = unreachable.gc.gc_next; gc != &unreachable;
 409                         gc = gc->gc.gc_next) {
 410                 m++;
 411                 if (debug & DEBUG_COLLECTABLE) {
 412                         debug_cycle("collectable", FROM_GC(gc));
 413                 }
 414         }
 415         /* call tp_clear on objects in the collectable set.  This will cause
 416          * the reference cycles to be broken. It may also cause some objects in
 417          * finalizers to be freed */
 418         delete_garbage(&unreachable, old);
 419
 420         /* Collect statistics on uncollectable objects found and print
 421          * debugging information. */
 422         for (gc = finalizers.gc.gc_next; gc != &finalizers;
 423                         gc = gc->gc.gc_next) {
 424                 n++;
 425                 if (debug & DEBUG_UNCOLLECTABLE) {
 426                         debug_cycle("uncollectable", FROM_GC(gc));
 427                 }
 428         }
 429         if (debug & DEBUG_STATS) {
 430                 if (m == 0 && n == 0) {
 431                         PySys_WriteStderr("gc: done.\n");
 432                 }
 433                 else {
 434                         PySys_WriteStderr(
 435                             "gc: done, %ld unreachable, %ld uncollectable.\n",
 436                             n+m, n);
 437                 }
 438         }
 439
 440         /* Append instances in the uncollectable set to a Python
 441          * reachable list of garbage.  The programmer has to deal with
 442          * this if they insist on creating this type of structure. */
 443         handle_finalizers(&finalizers, old);
 444
 445         if (PyErr_Occurred()) {
 446                 if (gc_str == NULL) {
 447                     gc_str = PyString_FromString("garbage collection");
 448                 }
 449                 PyErr_WriteUnraisable(gc_str);
 450                 Py_FatalError("unexpected exception during garbage collection");
 451         }
 452         allocated = 0;
 453         return n+m;
 454 }
 455
 456 static long
 457 collect_generations(void)
 458 {
 459         static long collections0 = 0;
 460         static long collections1 = 0;
 461         long n = 0;
 462
 463
 464         if (collections1 > threshold2) {
 465                 generation = 2;
 466                 gc_list_merge(&_PyGC_generation0, &generation2);
 467                 gc_list_merge(&generation1, &generation2);
 468                 if (generation2.gc.gc_next != &generation2) {
 469                         n = collect(&generation2, &generation2);
 470                 }
 471                 collections1 = 0;
 472         }
 473         else if (collections0 > threshold1) {
 474                 generation = 1;
 475                 collections1++;
 476                 gc_list_merge(&_PyGC_generation0, &generation1);
 477                 if (generation1.gc.gc_next != &generation1) {
 478                         n = collect(&generation1, &generation2);
 479                 }
 480                 collections0 = 0;
 481         }
 482         else {
 483                 generation = 0;
 484                 collections0++;
 485                 if (_PyGC_generation0.gc.gc_next != &_PyGC_generation0) {
 486                         n = collect(&_PyGC_generation0, &generation1);
 487                 }
 488         }
 489         return n;
 490 }
 491
 492 static char gc_enable__doc__[] =
 493 "enable() -> None\n"
 494 "\n"
 495 "Enable automatic garbage collection.\n"
 496 ;
 497
 498 static PyObject *
 499 gc_enable(PyObject *self, PyObject *args)
 500 {
 501
 502         if (!PyArg_ParseTuple(args, ":enable")) /* check no args */
 503                 return NULL;
 504
 505         enabled = 1;
 506
 507         Py_INCREF(Py_None);
 508         return Py_None;
 509 }
 510
 511 static char gc_disable__doc__[] =
 512 "disable() -> None\n"
 513 "\n"
 514 "Disable automatic garbage collection.\n"
 515 ;
 516
 517 static PyObject *
 518 gc_disable(PyObject *self, PyObject *args)
 519 {
 520
 521         if (!PyArg_ParseTuple(args, ":disable"))        /* check no args */
 522                 return NULL;
 523
 524         enabled = 0;
 525
 526         Py_INCREF(Py_None);
 527         return Py_None;
 528 }
 529
 530 static char gc_isenabled__doc__[] =
 531 "isenabled() -> status\n"
 532 "\n"
 533 "Returns true if automatic garbage collection is enabled.\n"
 534 ;
 535
 536 static PyObject *
 537 gc_isenabled(PyObject *self, PyObject *args)
 538 {
 539
 540         if (!PyArg_ParseTuple(args, ":isenabled"))      /* check no args */
 541                 return NULL;
 542
 543         return Py_BuildValue("i", enabled);
 544 }
 545
 546 static char gc_collect__doc__[] =
 547 "collect() -> n\n"
 548 "\n"
 549 "Run a full collection.  The number of unreachable objects is returned.\n"
 550 ;
 551
 552 static PyObject *
 553 gc_collect(PyObject *self, PyObject *args)
 554 {
 555         long n;
 556
 557         if (!PyArg_ParseTuple(args, ":collect"))        /* check no args */
 558                 return NULL;
 559
 560         if (collecting) {
 561                 n = 0; /* already collecting, don't do anything */
 562         }
 563         else {
 564                 collecting = 1;
 565                 generation = 2;
 566                 gc_list_merge(&_PyGC_generation0, &generation2);
 567                 gc_list_merge(&generation1, &generation2);
 568                 n = collect(&generation2, &generation2);
 569                 collecting = 0;
 570         }
 571
 572         return Py_BuildValue("l", n);
 573 }
 574
 575 static char gc_set_debug__doc__[] =
 576 "set_debug(flags) -> None\n"
 577 "\n"
 578 "Set the garbage collection debugging flags. Debugging information is\n"
 579 "written to sys.stderr.\n"
 580 "\n"
 581 "flags is an integer and can have the following bits turned on:\n"
 582 "\n"
 583 "  DEBUG_STATS - Print statistics during collection.\n"
 584 "  DEBUG_COLLECTABLE - Print collectable objects found.\n"
 585 "  DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects found.\n"
 586 "  DEBUG_INSTANCES - Print instance objects.\n"
 587 "  DEBUG_OBJECTS - Print objects other than instances.\n"
 588 "  DEBUG_SAVEALL - Save objects to gc.garbage rather than freeing them.\n"
 589 "  DEBUG_LEAK - Debug leaking programs (everything but STATS).\n"
 590 ;
 591
 592 static PyObject *
 593 gc_set_debug(PyObject *self, PyObject *args)
 594 {
 595         if (!PyArg_ParseTuple(args, "i:set_debug", &debug))
 596                 return NULL;
 597
 598         Py_INCREF(Py_None);
 599         return Py_None;
 600 }
 601
 602 static char gc_get_debug__doc__[] =
 603 "get_debug() -> flags\n"
 604 "\n"
 605 "Get the garbage collection debugging flags.\n"
 606 ;
 607
 608 static PyObject *
 609 gc_get_debug(PyObject *self, PyObject *args)
 610 {
 611         if (!PyArg_ParseTuple(args, ":get_debug"))      /* no args */
 612                 return NULL;
 613
 614         return Py_BuildValue("i", debug);
 615 }
 616
 617 static char gc_set_thresh__doc__[] =
 618 "set_threshold(threshold0, [threhold1, threshold2]) -> None\n"
 619 "\n"
 620 "Sets the collection thresholds.  Setting threshold0 to zero disables\n"
 621 "collection.\n"
 622 ;
 623
 624 static PyObject *
 625 gc_set_thresh(PyObject *self, PyObject *args)
 626 {
 627         if (!PyArg_ParseTuple(args, "i|ii:set_threshold", &threshold0,
 628                                 &threshold1, &threshold2))
 629                 return NULL;
 630
 631         Py_INCREF(Py_None);
 632         return Py_None;
 633 }
 634
 635 static char gc_get_thresh__doc__[] =
 636 "get_threshold() -> (threshold0, threshold1, threshold2)\n"
 637 "\n"
 638 "Return the current collection thresholds\n"
 639 ;
 640
 641 static PyObject *
 642 gc_get_thresh(PyObject *self, PyObject *args)
 643 {
 644         if (!PyArg_ParseTuple(args, ":get_threshold"))  /* no args */
 645                 return NULL;
 646
 647         return Py_BuildValue("(iii)", threshold0, threshold1, threshold2);
 648 }
 649
 650 static int
 651 referrersvisit(PyObject* obj, PyObject *objs)
 652 {
 653         int i;
 654         for (i = 0; i < PyTuple_GET_SIZE(objs); i++)
 655                 if (PyTuple_GET_ITEM(objs, i) == obj)
 656                         return 1;
 657         return 0;
 658 }
 659
 660 static int
 661 gc_referrers_for(PyObject *objs, PyGC_Head *list, PyObject *resultlist)
 662 {
 663         PyGC_Head *gc;
 664         PyObject *obj;
 665         traverseproc traverse;
 666         for (gc = list->gc.gc_next; gc != list; gc = gc->gc.gc_next) {
 667                 obj = FROM_GC(gc);
 668                 traverse = obj->ob_type->tp_traverse;
 669                 if (obj == objs || obj == resultlist)
 670                         continue;
 671                 if (traverse(obj, (visitproc)referrersvisit, objs)) {
 672                         if (PyList_Append(resultlist, obj) < 0)
 673                                 return 0; /* error */
 674                 }
 675         }
 676         return 1; /* no error */
 677 }
 678
 679 static char gc_get_referrers__doc__[]=
 680 "get_referrers(*objs) -> list\n\
 681 Return the list of objects that directly refer to any of objs.";
 682
 683 static PyObject *
 684 gc_get_referrers(PyObject *self, PyObject *args)
 685 {
 686         PyObject *result = PyList_New(0);
 687         if (!(gc_referrers_for(args, &_PyGC_generation0, result) &&
 688               gc_referrers_for(args, &generation1, result) &&
 689               gc_referrers_for(args, &generation2, result))) {
 690                 Py_DECREF(result);
 691                 return NULL;
 692         }
 693         return result;
 694 }
 695
 696 static char gc_get_objects__doc__[] =
 697 "get_objects() -> [...]\n"
 698 "\n"
 699 "Return a list of objects tracked by the collector (excluding the list\n"
 700 "returned).\n"
 701 ;
 702
 703 /* appending objects in a GC list to a Python list */
 704 static int
 705 append_objects(PyObject *py_list, PyGC_Head *gc_list)
 706 {
 707         PyGC_Head *gc;
 708         for (gc = gc_list->gc.gc_next; gc != gc_list; gc = gc->gc.gc_next) {
 709                 PyObject *op = FROM_GC(gc);
 710                 if (op != py_list) {
 711                         if (PyList_Append(py_list, op)) {
 712                                 return -1; /* exception */
 713                         }
 714                 }
 715         }
 716         return 0;
 717 }
 718
 719 static PyObject *
 720 gc_get_objects(PyObject *self, PyObject *args)
 721 {
 722         PyObject* result;
 723
 724         if (!PyArg_ParseTuple(args, ":get_objects")) /* check no args */
 725                 return NULL;
 726         result = PyList_New(0);
 727         if (result == NULL) {
 728                 return NULL;
 729         }
 730         if (append_objects(result, &_PyGC_generation0) ||
 731             append_objects(result, &generation1) ||
 732             append_objects(result, &generation2)) {
 733                 Py_DECREF(result);
 734                 return NULL;
 735         }
 736         return result;
 737 }
 738
 739
 740 static char gc__doc__ [] =
 741 "This module provides access to the garbage collector for reference cycles.\n"
 742 "\n"
 743 "enable() -- Enable automatic garbage collection.\n"
 744 "disable() -- Disable automatic garbage collection.\n"
 745 "isenabled() -- Returns true if automatic collection is enabled.\n"
 746 "collect() -- Do a full collection right now.\n"
 747 "set_debug() -- Set debugging flags.\n"
 748 "get_debug() -- Get debugging flags.\n"
 749 "set_threshold() -- Set the collection thresholds.\n"
 750 "get_threshold() -- Return the current the collection thresholds.\n"
 751 "get_objects() -- Return a list of all objects tracked by the collector.\n"
 752 "get_referrers() -- Return the list of objects that refer to an object.\n"
 753 ;
 754
 755 static PyMethodDef GcMethods[] = {
 756         {"enable",         gc_enable,     METH_VARARGS, gc_enable__doc__},
 757         {"disable",        gc_disable,    METH_VARARGS, gc_disable__doc__},
 758         {"isenabled",      gc_isenabled,  METH_VARARGS, gc_isenabled__doc__},
 759         {"set_debug",      gc_set_debug,  METH_VARARGS, gc_set_debug__doc__},
 760         {"get_debug",      gc_get_debug,  METH_VARARGS, gc_get_debug__doc__},
 761         {"set_threshold",  gc_set_thresh, METH_VARARGS, gc_set_thresh__doc__},
 762         {"get_threshold",  gc_get_thresh, METH_VARARGS, gc_get_thresh__doc__},
 763         {"collect",        gc_collect,    METH_VARARGS, gc_collect__doc__},
 764         {"get_objects",    gc_get_objects,METH_VARARGS, gc_get_objects__doc__},
 765         {"get_referrers",  gc_get_referrers, METH_VARARGS,
 766                 gc_get_referrers__doc__},
 767         {NULL,  NULL}           /* Sentinel */
 768 };
 769
 770 void
 771 initgc(void)
 772 {
 773         PyObject *m;
 774         PyObject *d;
 775
 776         m = Py_InitModule4("gc",
 777                               GcMethods,
 778                               gc__doc__,
 779                               NULL,
 780                               PYTHON_API_VERSION);
 781         d = PyModule_GetDict(m);
 782         if (garbage == NULL) {
 783                 garbage = PyList_New(0);
 784         }
 785         PyDict_SetItemString(d, "garbage", garbage);
 786         PyDict_SetItemString(d, "DEBUG_STATS",
 787                         PyInt_FromLong(DEBUG_STATS));
 788         PyDict_SetItemString(d, "DEBUG_COLLECTABLE",
 789                         PyInt_FromLong(DEBUG_COLLECTABLE));
 790         PyDict_SetItemString(d, "DEBUG_UNCOLLECTABLE",
 791                         PyInt_FromLong(DEBUG_UNCOLLECTABLE));
 792         PyDict_SetItemString(d, "DEBUG_INSTANCES",
 793                         PyInt_FromLong(DEBUG_INSTANCES));
 794         PyDict_SetItemString(d, "DEBUG_OBJECTS",
 795                         PyInt_FromLong(DEBUG_OBJECTS));
 796         PyDict_SetItemString(d, "DEBUG_SAVEALL",
 797                         PyInt_FromLong(DEBUG_SAVEALL));
 798         PyDict_SetItemString(d, "DEBUG_LEAK",
 799                         PyInt_FromLong(DEBUG_LEAK));
 800 }
 801
 802 /* for debugging */
 803 void _PyGC_Dump(PyGC_Head *g)
 804 {
 805         _PyObject_Dump(FROM_GC(g));
 806 }
 807
 808 #endif /* WITH_CYCLE_GC */
 809
 810 /* extension modules might be compiled with GC support so these
 811    functions must always be available */
 812
 813 void
 814 _PyObject_GC_Track(PyObject *op)
 815 {
 816         _PyObject_GC_TRACK(op);
 817 }
 818
 819 void
 820 _PyObject_GC_UnTrack(PyObject *op)
 821 {
 822         _PyObject_GC_UNTRACK(op);
 823 }
 824
 825 PyObject *
 826 _PyObject_GC_Malloc(PyTypeObject *tp, int nitems)
 827 {
 828         PyObject *op;
 829         const size_t basicsize = _PyObject_VAR_SIZE(tp, nitems);
 830 #ifdef WITH_CYCLE_GC
 831         const size_t nbytes = sizeof(PyGC_Head) + basicsize;
 832         PyGC_Head *g = PyObject_MALLOC(nbytes);
 833         if (g == NULL)
 834                 return (PyObject *)PyErr_NoMemory();
 835         g->gc.gc_next = NULL;
 836         allocated++;
 837         if (allocated > threshold0 &&
 838             enabled &&
 839             threshold0 &&
 840             !collecting &&
 841             !PyErr_Occurred()) {
 842                 collecting = 1;
 843                 collect_generations();
 844                 collecting = 0;
 845         }
 846         op = FROM_GC(g);
 847 #else
 848         op = PyObject_MALLOC(basicsize);
 849         if (op == NULL)
 850                 return (PyObject *)PyErr_NoMemory();
 851
 852 #endif
 853         return op;
 854 }
 855
 856 PyObject *
 857 _PyObject_GC_New(PyTypeObject *tp)
 858 {
 859         PyObject *op = _PyObject_GC_Malloc(tp, 0);
 860         return PyObject_INIT(op, tp);
 861 }
 862
 863 PyVarObject *
 864 _PyObject_GC_NewVar(PyTypeObject *tp, int nitems)
 865 {
 866         PyVarObject *op = (PyVarObject *) _PyObject_GC_Malloc(tp, nitems);
 867         return PyObject_INIT_VAR(op, tp, nitems);
 868 }
 869
 870 PyVarObject *
 871 _PyObject_GC_Resize(PyVarObject *op, int nitems)
 872 {
 873         const size_t basicsize = _PyObject_VAR_SIZE(op->ob_type, nitems);
 874 #ifdef WITH_CYCLE_GC
 875         PyGC_Head *g = AS_GC(op);
 876         g = PyObject_REALLOC(g,  sizeof(PyGC_Head) + basicsize);
 877         if (g == NULL)
 878                 return (PyVarObject *)PyErr_NoMemory();
 879         op = (PyVarObject *) FROM_GC(g);
 880 #else
 881         op = PyObject_REALLOC(op, basicsize);
 882         if (op == NULL)
 883                 return (PyVarObject *)PyErr_NoMemory();
 884 #endif
 885         op->ob_size = nitems;
 886         return op;
 887 }
 888
 889 void
 890 _PyObject_GC_Del(PyObject *op)
 891 {
 892 #ifdef WITH_CYCLE_GC
 893         PyGC_Head *g = AS_GC(op);
 894         if (g->gc.gc_next != NULL)
 895                 gc_list_remove(g);
 896         if (allocated > 0) {
 897                 allocated--;
 898         }
 899         PyObject_FREE(g);
 900 #else
 901         PyObject_FREE(op);
 902 #endif
 903 }
 904