gcmodule.c 60.3 KB
Newer Older
1
/*
2

3 4 5
  Reference Cycle Garbage Collection
  ==================================

6
  Neil Schemenauer <nas@arctrix.com>
7 8 9 10

  Based on a post on the python-dev list.  Ideas from Guido van Rossum,
  Eric Tiedemann, and various others.

11
  http://www.arctrix.com/nas/python/gc/
12 13 14 15 16 17 18 19

  The following mailing list threads provide a historical perspective on
  the design of this module.  Note that a fair amount of refinement has
  occurred since those discussions.

  http://mail.python.org/pipermail/python-dev/2000-March/002385.html
  http://mail.python.org/pipermail/python-dev/2000-March/002434.html
  http://mail.python.org/pipermail/python-dev/2000-March/002497.html
20 21 22 23 24 25 26

  For a highlevel view of the collection process, read the collect
  function.

*/

#include "Python.h"
27
#include "internal/context.h"
28 29
#include "internal/mem.h"
#include "internal/pystate.h"
30
#include "frameobject.h"        /* for PyFrame_ClearFreeList */
31
#include "pydtrace.h"
32
#include "pytime.h"             /* for _PyTime_GetMonotonicClock() */
33

34 35 36 37 38
/*[clinic input]
module gc
[clinic start generated code]*/
/*[clinic end generated code: output=da39a3ee5e6b4b0d input=b5c9690ecc842d79]*/

39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
#define GC_DEBUG (0)  /* Enable more asserts */

#define GC_NEXT _PyGCHead_NEXT
#define GC_PREV _PyGCHead_PREV

// update_refs() set this bit for all objects in current generation.
// subtract_refs() and move_unreachable() uses this to distinguish
// visited object is in GCing or not.
//
// move_unreachable() removes this flag from reachable objects.
// Only unreachable objects have this flag.
//
// No objects in interpreter have this flag after GC ends.
#define PREV_MASK_COLLECTING   _PyGC_PREV_MASK_COLLECTING

// Lowest bit of _gc_next is used for UNREACHABLE flag.
//
// This flag represents the object is in unreachable list in move_unreachable()
//
// Although this flag is used only in move_unreachable(), move_unreachable()
// doesn't clear this flag to skip unnecessary iteration.
// move_legacy_finalizers() removes this flag instead.
// Between them, unreachable list is not normal list and we can not use
// most gc_list_* functions for it.
#define NEXT_MASK_UNREACHABLE  (1)

static inline int
gc_is_collecting(PyGC_Head *g)
{
    return (g->_gc_prev & PREV_MASK_COLLECTING) != 0;
}

static inline void
gc_clear_collecting(PyGC_Head *g)
{
    g->_gc_prev &= ~PREV_MASK_COLLECTING;
}

static inline Py_ssize_t
gc_get_refs(PyGC_Head *g)
{
    return (Py_ssize_t)(g->_gc_prev >> _PyGC_PREV_SHIFT);
}

static inline void
gc_set_refs(PyGC_Head *g, Py_ssize_t refs)
{
    g->_gc_prev = (g->_gc_prev & ~_PyGC_PREV_MASK)
        | ((uintptr_t)(refs) << _PyGC_PREV_SHIFT);
}

static inline void
gc_reset_refs(PyGC_Head *g, Py_ssize_t refs)
{
    g->_gc_prev = (g->_gc_prev & _PyGC_PREV_MASK_FINALIZED)
        | PREV_MASK_COLLECTING
        | ((uintptr_t)(refs) << _PyGC_PREV_SHIFT);
}

static inline void
gc_decref(PyGC_Head *g)
{
    assert(gc_get_refs(g) > 0);
    g->_gc_prev -= 1 << _PyGC_PREV_SHIFT;
}

105 106 107 108 109 110
/* Get an object's GC head */
#define AS_GC(o) ((PyGC_Head *)(o)-1)

/* Get the object given the GC head */
#define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))

111
/* Python string to use if unhandled exception occurs */
112
static PyObject *gc_str = NULL;
113

114
/* set for debugging information */
115 116 117 118 119 120 121
#define DEBUG_STATS             (1<<0) /* print collection statistics */
#define DEBUG_COLLECTABLE       (1<<1) /* print collectable objects */
#define DEBUG_UNCOLLECTABLE     (1<<2) /* print uncollectable objects */
#define DEBUG_SAVEALL           (1<<5) /* save all garbage in gc.garbage */
#define DEBUG_LEAK              DEBUG_COLLECTABLE | \
                DEBUG_UNCOLLECTABLE | \
                DEBUG_SAVEALL
122

123 124 125 126 127 128 129 130 131
#define GEN_HEAD(n) (&_PyRuntime.gc.generations[n].head)

void
_PyGC_Initialize(struct _gc_runtime_state *state)
{
    state->enabled = 1; /* automatic collection enabled? */

#define _GEN_HEAD(n) (&state->generations[n].head)
    struct gc_generation generations[NUM_GENERATIONS] = {
132 133 134 135
        /* PyGC_Head,                                    threshold,    count */
        {{(uintptr_t)_GEN_HEAD(0), (uintptr_t)_GEN_HEAD(0)},   700,        0},
        {{(uintptr_t)_GEN_HEAD(1), (uintptr_t)_GEN_HEAD(1)},   10,         0},
        {{(uintptr_t)_GEN_HEAD(2), (uintptr_t)_GEN_HEAD(2)},   10,         0},
136 137 138 139 140
    };
    for (int i = 0; i < NUM_GENERATIONS; i++) {
        state->generations[i] = generations[i];
    };
    state->generation0 = GEN_HEAD(0);
141
    struct gc_generation permanent_generation = {
142 143
          {(uintptr_t)&state->permanent_generation.head,
           (uintptr_t)&state->permanent_generation.head}, 0, 0
144 145
    };
    state->permanent_generation = permanent_generation;
146
}
147

148 149 150
/*
_gc_prev values
---------------
151

152
Between collections, _gc_prev is used for doubly linked list.
153

154 155 156
Lowest two bits of _gc_prev are used for flags.
PREV_MASK_COLLECTING is used only while collecting and cleared before GC ends
or _PyObject_GC_UNTRACK() is called.
157

158 159
During a collection, _gc_prev is temporary used for gc_refs, and the gc list
is singly linked until _gc_prev is restored.
160

161
gc_refs
162 163 164 165 166 167
    At the start of a collection, update_refs() copies the true refcount
    to gc_refs, for each object in the generation being collected.
    subtract_refs() then adjusts gc_refs so that it equals the number of
    times an object is referenced directly from outside the generation
    being collected.

168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186
PREV_MASK_COLLECTING
    Objects in generation being collected are marked PREV_MASK_COLLECTING in
    update_refs().


_gc_next values
---------------

_gc_next takes these values:

0
    The object is not tracked

!= 0
    Pointer to the next object in the GC list.
    Additionally, lowest bit is used temporary for
    NEXT_MASK_UNREACHABLE flag described below.

NEXT_MASK_UNREACHABLE
187
    move_unreachable() then moves objects not reachable (whether directly or
188 189 190 191 192 193 194
    indirectly) from outside the generation into an "unreachable" set and
    set this flag.

    Objects that are found to be reachable have gc_refs set to 1.
    When this flag is set for the reachable object, the object must be in
    "unreachable" set.
    The flag is unset and the object is moved back to "reachable" set.
195

196 197
    move_legacy_finalizers() will remove this flag from "unreachable" set.
*/
198

199 200
/*** list functions ***/

201
static inline void
202 203
gc_list_init(PyGC_Head *list)
{
204 205 206 207
    // List header must not have flags.
    // We can assign pointer by simple cast.
    list->_gc_prev = (uintptr_t)list;
    list->_gc_next = (uintptr_t)list;
208 209
}

210
static inline int
211 212
gc_list_is_empty(PyGC_Head *list)
{
213
    return (list->_gc_next == (uintptr_t)list);
214 215
}

Tim Peters's avatar
Tim Peters committed
216
/* Append `node` to `list`. */
217
static inline void
218 219
gc_list_append(PyGC_Head *node, PyGC_Head *list)
{
220 221 222 223 224 225 226 227 228
    PyGC_Head *last = (PyGC_Head *)list->_gc_prev;

    // last <-> node
    _PyGCHead_SET_PREV(node, last);
    _PyGCHead_SET_NEXT(last, node);

    // node <-> list
    _PyGCHead_SET_NEXT(node, list);
    list->_gc_prev = (uintptr_t)node;
229 230
}

Tim Peters's avatar
Tim Peters committed
231
/* Remove `node` from the gc list it's currently in. */
232
static inline void
233 234
gc_list_remove(PyGC_Head *node)
{
235 236 237 238 239 240 241
    PyGC_Head *prev = GC_PREV(node);
    PyGC_Head *next = GC_NEXT(node);

    _PyGCHead_SET_NEXT(prev, next);
    _PyGCHead_SET_PREV(next, prev);

    node->_gc_next = 0; /* object is not currently tracked */
242 243
}

Tim Peters's avatar
Tim Peters committed
244 245 246 247 248 249 250
/* Move `node` from the gc list it's currently in (which is not explicitly
 * named here) to the end of `list`.  This is semantically the same as
 * gc_list_remove(node) followed by gc_list_append(node, list).
 */
static void
gc_list_move(PyGC_Head *node, PyGC_Head *list)
{
251
    /* Unlink from current list. */
252 253 254 255 256
    PyGC_Head *from_prev = GC_PREV(node);
    PyGC_Head *from_next = GC_NEXT(node);
    _PyGCHead_SET_NEXT(from_prev, from_next);
    _PyGCHead_SET_PREV(from_next, from_prev);

257
    /* Relink at end of new list. */
258 259 260 261 262 263
    // list must not have flags.  So we can skip macros.
    PyGC_Head *to_prev = (PyGC_Head*)list->_gc_prev;
    _PyGCHead_SET_PREV(node, to_prev);
    _PyGCHead_SET_NEXT(to_prev, node);
    list->_gc_prev = (uintptr_t)node;
    _PyGCHead_SET_NEXT(node, list);
Tim Peters's avatar
Tim Peters committed
264 265 266
}

/* append list `from` onto list `to`; `from` becomes an empty list */
267 268 269
static void
gc_list_merge(PyGC_Head *from, PyGC_Head *to)
{
270 271
    assert(from != to);
    if (!gc_list_is_empty(from)) {
272 273 274 275 276 277 278 279 280 281 282
        PyGC_Head *to_tail = GC_PREV(to);
        PyGC_Head *from_head = GC_NEXT(from);
        PyGC_Head *from_tail = GC_PREV(from);
        assert(from_head != from);
        assert(from_tail != from);

        _PyGCHead_SET_NEXT(to_tail, from_head);
        _PyGCHead_SET_PREV(from_head, to_tail);

        _PyGCHead_SET_NEXT(from_tail, to);
        _PyGCHead_SET_PREV(to, from_tail);
283 284
    }
    gc_list_init(from);
285 286
}

287
static Py_ssize_t
288 289
gc_list_size(PyGC_Head *list)
{
290 291
    PyGC_Head *gc;
    Py_ssize_t n = 0;
292
    for (gc = GC_NEXT(list); gc != list; gc = GC_NEXT(gc)) {
293 294 295
        n++;
    }
    return n;
296 297
}

298 299 300 301 302 303
/* Append objects in a GC list to a Python list.
 * Return 0 if all OK, < 0 if error (out of memory for list).
 */
static int
append_objects(PyObject *py_list, PyGC_Head *gc_list)
{
304
    PyGC_Head *gc;
305
    for (gc = GC_NEXT(gc_list); gc != gc_list; gc = GC_NEXT(gc)) {
306 307 308 309 310 311 312 313
        PyObject *op = FROM_GC(gc);
        if (op != py_list) {
            if (PyList_Append(py_list, op)) {
                return -1; /* exception */
            }
        }
    }
    return 0;
314 315
}

316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336
#if GC_DEBUG
// validate_list checks list consistency.  And it works as document
// describing when expected_mask is set / unset.
static void
validate_list(PyGC_Head *head, uintptr_t expected_mask)
{
    PyGC_Head *prev = head;
    PyGC_Head *gc = GC_NEXT(head);
    while (gc != head) {
        assert(GC_NEXT(gc) != NULL);
        assert(GC_PREV(gc) == prev);
        assert((gc->_gc_prev & PREV_MASK_COLLECTING) == expected_mask);
        prev = gc;
        gc = GC_NEXT(gc);
    }
    assert(prev == GC_PREV(head));
}
#else
#define validate_list(x,y) do{}while(0)
#endif

337 338 339
/*** end of list stuff ***/


340 341
/* Set all gc_refs = ob_refcnt.  After this, gc_refs is > 0 and
 * PREV_MASK_COLLECTING bit is set for all objects in containers.
342
 */
343 344 345
static void
update_refs(PyGC_Head *containers)
{
346 347 348
    PyGC_Head *gc = GC_NEXT(containers);
    for (; gc != containers; gc = GC_NEXT(gc)) {
        gc_reset_refs(gc, Py_REFCNT(FROM_GC(gc)));
349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
        /* Python's cyclic gc should never see an incoming refcount
         * of 0:  if something decref'ed to 0, it should have been
         * deallocated immediately at that time.
         * Possible cause (if the assert triggers):  a tp_dealloc
         * routine left a gc-aware object tracked during its teardown
         * phase, and did something-- or allowed something to happen --
         * that called back into Python.  gc can trigger then, and may
         * see the still-tracked dying object.  Before this assert
         * was added, such mistakes went on to allow gc to try to
         * delete the object again.  In a debug build, that caused
         * a mysterious segfault, when _Py_ForgetReference tried
         * to remove the object from the doubly-linked list of all
         * objects a second time.  In a release build, an actual
         * double deallocation occurred, which leads to corruption
         * of the allocator's internal bookkeeping pointers.  That's
         * so serious that maybe this should be a release-build
         * check instead of an assert?
         */
367
        assert(gc_get_refs(gc) != 0);
368
    }
369 370
}

371
/* A traversal callback for subtract_refs. */
372 373 374
static int
visit_decref(PyObject *op, void *data)
{
375 376 377 378 379 380 381
    assert(op != NULL);
    if (PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        /* We're only interested in gc_refs for objects in the
         * generation being collected, which can be recognized
         * because only they have positive gc_refs.
         */
382 383 384
        if (gc_is_collecting(gc)) {
            gc_decref(gc);
        }
385 386
    }
    return 0;
387 388
}

389 390 391 392 393
/* Subtract internal references from gc_refs.  After this, gc_refs is >= 0
 * for all objects in containers, and is GC_REACHABLE for all tracked gc
 * objects not in containers.  The ones with gc_refs > 0 are directly
 * reachable from outside containers, and so can't be collected.
 */
394 395 396
static void
subtract_refs(PyGC_Head *containers)
{
397
    traverseproc traverse;
398 399
    PyGC_Head *gc = GC_NEXT(containers);
    for (; gc != containers; gc = GC_NEXT(gc)) {
400 401 402 403 404
        traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
        (void) traverse(FROM_GC(gc),
                       (visitproc)visit_decref,
                       NULL);
    }
405 406
}

407
/* A traversal callback for move_unreachable. */
408
static int
409
visit_reachable(PyObject *op, PyGC_Head *reachable)
410
{
411 412 413
    if (!PyObject_IS_GC(op)) {
        return 0;
    }
414

415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445
    PyGC_Head *gc = AS_GC(op);
    const Py_ssize_t gc_refs = gc_get_refs(gc);

    // Ignore untracked objects and objects in other generation.
    if (gc->_gc_next == 0 || !gc_is_collecting(gc)) {
        return 0;
    }

    if (gc->_gc_next & NEXT_MASK_UNREACHABLE) {
        /* This had gc_refs = 0 when move_unreachable got
         * to it, but turns out it's reachable after all.
         * Move it back to move_unreachable's 'young' list,
         * and move_unreachable will eventually get to it
         * again.
         */
        // Manually unlink gc from unreachable list because
        PyGC_Head *prev = GC_PREV(gc);
        PyGC_Head *next = (PyGC_Head*)(gc->_gc_next & ~NEXT_MASK_UNREACHABLE);
        assert(prev->_gc_next & NEXT_MASK_UNREACHABLE);
        assert(next->_gc_next & NEXT_MASK_UNREACHABLE);
        prev->_gc_next = gc->_gc_next;  // copy NEXT_MASK_UNREACHABLE
        _PyGCHead_SET_PREV(next, prev);

        gc_list_append(gc, reachable);
        gc_set_refs(gc, 1);
    }
    else if (gc_refs == 0) {
        /* This is in move_unreachable's 'young' list, but
         * the traversal hasn't yet gotten to it.  All
         * we need to do is tell move_unreachable that it's
         * reachable.
446
         */
447 448 449 450 451 452 453 454
        gc_set_refs(gc, 1);
    }
    /* Else there's nothing to do.
     * If gc_refs > 0, it must be in move_unreachable's 'young'
     * list, and move_unreachable will eventually get to it.
     */
    else {
        assert(gc_refs > 0);
455 456
    }
    return 0;
457 458
}

459
/* Move the unreachable objects from young to unreachable.  After this,
460 461
 * all objects in young don't have PREV_MASK_COLLECTING flag and
 * unreachable have the flag.
462 463 464
 * All objects in young after this are directly or indirectly reachable
 * from outside the original young; and all objects in unreachable are
 * not.
465 466 467 468 469
 *
 * This function restores _gc_prev pointer.  young and unreachable are
 * doubly linked list after this function.
 * But _gc_next in unreachable list has NEXT_MASK_UNREACHABLE flag.
 * So we can not gc_list_* functions for unreachable until we remove the flag.
470
 */
471
static void
472
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
473
{
474 475 476
    // previous elem in the young list, used for restore gc_prev.
    PyGC_Head *prev = young;
    PyGC_Head *gc = GC_NEXT(young);
477

478 479 480 481 482
    /* Invariants:  all objects "to the left" of us in young are reachable
     * (directly or indirectly) from outside the young list as it was at entry.
     *
     * All other objects from the original young "to the left" of us are in
     * unreachable now, and have NEXT_MASK_UNREACHABLE.  All objects to the
483 484 485 486 487
     * left of us in 'young' now have been scanned, and no objects here
     * or to the right have been scanned yet.
     */

    while (gc != young) {
488
        if (gc_get_refs(gc)) {
489 490 491 492 493 494 495 496 497 498
            /* gc is definitely reachable from outside the
             * original 'young'.  Mark it as such, and traverse
             * its pointers to find any other objects that may
             * be directly reachable from it.  Note that the
             * call to tp_traverse may append objects to young,
             * so we have to wait until it returns to determine
             * the next object to visit.
             */
            PyObject *op = FROM_GC(gc);
            traverseproc traverse = Py_TYPE(op)->tp_traverse;
499 500 501
            assert(gc_get_refs(gc) > 0);
            // NOTE: visit_reachable may change gc->_gc_next when
            // young->_gc_prev == gc.  Don't do gc = GC_NEXT(gc) before!
502
            (void) traverse(op,
503 504 505 506
                    (visitproc)visit_reachable,
                    (void *)young);
            // relink gc_prev to prev element.
            _PyGCHead_SET_PREV(gc, prev);
507
            // gc is not COLLECTING state after here.
508 509
            gc_clear_collecting(gc);
            prev = gc;
510 511 512 513 514 515 516 517 518
        }
        else {
            /* This *may* be unreachable.  To make progress,
             * assume it is.  gc isn't directly reachable from
             * any object we've already traversed, but may be
             * reachable from an object we haven't gotten to yet.
             * visit_reachable will eventually move gc back into
             * young if that's so, and we'll see it again.
             */
519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549
            // Move gc to unreachable.
            // No need to gc->next->prev = prev because it is single linked.
            prev->_gc_next = gc->_gc_next;

            // We can't use gc_list_append() here because we use
            // NEXT_MASK_UNREACHABLE here.
            PyGC_Head *last = GC_PREV(unreachable);
            // NOTE: Since all objects in unreachable set has
            // NEXT_MASK_UNREACHABLE flag, we set it unconditionally.
            // But this may set the flat to unreachable too.
            // move_legacy_finalizers() should care about it.
            last->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)gc);
            _PyGCHead_SET_PREV(gc, last);
            gc->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)unreachable);
            unreachable->_gc_prev = (uintptr_t)gc;
        }
        gc = (PyGC_Head*)prev->_gc_next;
    }
    // young->_gc_prev must be last element remained in the list.
    young->_gc_prev = (uintptr_t)prev;
}

static void
untrack_tuples(PyGC_Head *head)
{
    PyGC_Head *next, *gc = GC_NEXT(head);
    while (gc != head) {
        PyObject *op = FROM_GC(gc);
        next = GC_NEXT(gc);
        if (PyTuple_CheckExact(op)) {
            _PyTuple_MaybeUntrack(op);
550 551 552
        }
        gc = next;
    }
553 554
}

555 556 557 558
/* Try to untrack all currently tracked dictionaries */
static void
untrack_dicts(PyGC_Head *head)
{
559
    PyGC_Head *next, *gc = GC_NEXT(head);
560 561
    while (gc != head) {
        PyObject *op = FROM_GC(gc);
562 563
        next = GC_NEXT(gc);
        if (PyDict_CheckExact(op)) {
564
            _PyDict_MaybeUntrack(op);
565
        }
566 567 568 569
        gc = next;
    }
}

570
/* Return true if object has a pre-PEP 442 finalization method. */
571
static int
572
has_legacy_finalizer(PyObject *op)
573
{
574
    return op->ob_type->tp_del != NULL;
575 576
}

577
/* Move the objects in unreachable with tp_del slots into `finalizers`.
578 579 580
 *
 * This function also removes NEXT_MASK_UNREACHABLE flag
 * from _gc_next in unreachable.
Jeremy Hylton's avatar
Jeremy Hylton committed
581
 */
582
static void
583
move_legacy_finalizers(PyGC_Head *unreachable, PyGC_Head *finalizers)
584
{
585 586
    PyGC_Head *gc, *next;
    unreachable->_gc_next &= ~NEXT_MASK_UNREACHABLE;
587 588 589 590

    /* March over unreachable.  Move objects with finalizers into
     * `finalizers`.
     */
591
    for (gc = GC_NEXT(unreachable); gc != unreachable; gc = next) {
592 593
        PyObject *op = FROM_GC(gc);

594 595 596
        assert(gc->_gc_next & NEXT_MASK_UNREACHABLE);
        gc->_gc_next &= ~NEXT_MASK_UNREACHABLE;
        next = (PyGC_Head*)gc->_gc_next;
597

598
        if (has_legacy_finalizer(op)) {
599
            gc_clear_collecting(gc);
600 601 602
            gc_list_move(gc, finalizers);
        }
    }
603 604
}

605
/* A traversal callback for move_legacy_finalizer_reachable. */
606 607 608
static int
visit_move(PyObject *op, PyGC_Head *tolist)
{
609
    if (PyObject_IS_GC(op)) {
610 611
        PyGC_Head *gc = AS_GC(op);
        if (gc_is_collecting(gc)) {
612
            gc_list_move(gc, tolist);
613
            gc_clear_collecting(gc);
614 615 616
        }
    }
    return 0;
617 618
}

619
/* Move objects that are reachable from finalizers, from the unreachable set
620
 * into finalizers set.
621
 */
622
static void
623
move_legacy_finalizer_reachable(PyGC_Head *finalizers)
624
{
625
    traverseproc traverse;
626 627
    PyGC_Head *gc = GC_NEXT(finalizers);
    for (; gc != finalizers; gc = GC_NEXT(gc)) {
628 629 630 631 632 633
        /* Note that the finalizers list may grow during this. */
        traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
        (void) traverse(FROM_GC(gc),
                        (visitproc)visit_move,
                        (void *)finalizers);
    }
634 635
}

636 637 638 639 640 641 642 643 644 645
/* Clear all weakrefs to unreachable objects, and if such a weakref has a
 * callback, invoke it if necessary.  Note that it's possible for such
 * weakrefs to be outside the unreachable set -- indeed, those are precisely
 * the weakrefs whose callbacks must be invoked.  See gc_weakref.txt for
 * overview & some details.  Some weakrefs with callbacks may be reclaimed
 * directly by this routine; the number reclaimed is the return value.  Other
 * weakrefs with callbacks may be moved into the `old` generation.  Objects
 * moved into `old` have gc_refs set to GC_REACHABLE; the objects remaining in
 * unreachable are left at GC_TENTATIVELY_UNREACHABLE.  When this returns,
 * no object in `unreachable` is weakly referenced anymore.
646
 */
647 648
static int
handle_weakrefs(PyGC_Head *unreachable, PyGC_Head *old)
649
{
650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666
    PyGC_Head *gc;
    PyObject *op;               /* generally FROM_GC(gc) */
    PyWeakReference *wr;        /* generally a cast of op */
    PyGC_Head wrcb_to_call;     /* weakrefs with callbacks to call */
    PyGC_Head *next;
    int num_freed = 0;

    gc_list_init(&wrcb_to_call);

    /* Clear all weakrefs to the objects in unreachable.  If such a weakref
     * also has a callback, move it into `wrcb_to_call` if the callback
     * needs to be invoked.  Note that we cannot invoke any callbacks until
     * all weakrefs to unreachable objects are cleared, lest the callback
     * resurrect an unreachable object via a still-active weakref.  We
     * make another pass over wrcb_to_call, invoking callbacks, after this
     * pass completes.
     */
667
    for (gc = GC_NEXT(unreachable); gc != unreachable; gc = next) {
668 669 670
        PyWeakReference **wrlist;

        op = FROM_GC(gc);
671
        next = GC_NEXT(gc);
672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724

        if (! PyType_SUPPORTS_WEAKREFS(Py_TYPE(op)))
            continue;

        /* It supports weakrefs.  Does it have any? */
        wrlist = (PyWeakReference **)
                                PyObject_GET_WEAKREFS_LISTPTR(op);

        /* `op` may have some weakrefs.  March over the list, clear
         * all the weakrefs, and move the weakrefs with callbacks
         * that must be called into wrcb_to_call.
         */
        for (wr = *wrlist; wr != NULL; wr = *wrlist) {
            PyGC_Head *wrasgc;                  /* AS_GC(wr) */

            /* _PyWeakref_ClearRef clears the weakref but leaves
             * the callback pointer intact.  Obscure:  it also
             * changes *wrlist.
             */
            assert(wr->wr_object == op);
            _PyWeakref_ClearRef(wr);
            assert(wr->wr_object == Py_None);
            if (wr->wr_callback == NULL)
                continue;                       /* no callback */

    /* Headache time.  `op` is going away, and is weakly referenced by
     * `wr`, which has a callback.  Should the callback be invoked?  If wr
     * is also trash, no:
     *
     * 1. There's no need to call it.  The object and the weakref are
     *    both going away, so it's legitimate to pretend the weakref is
     *    going away first.  The user has to ensure a weakref outlives its
     *    referent if they want a guarantee that the wr callback will get
     *    invoked.
     *
     * 2. It may be catastrophic to call it.  If the callback is also in
     *    cyclic trash (CT), then although the CT is unreachable from
     *    outside the current generation, CT may be reachable from the
     *    callback.  Then the callback could resurrect insane objects.
     *
     * Since the callback is never needed and may be unsafe in this case,
     * wr is simply left in the unreachable set.  Note that because we
     * already called _PyWeakref_ClearRef(wr), its callback will never
     * trigger.
     *
     * OTOH, if wr isn't part of CT, we should invoke the callback:  the
     * weakref outlived the trash.  Note that since wr isn't CT in this
     * case, its callback can't be CT either -- wr acted as an external
     * root to this generation, and therefore its callback did too.  So
     * nothing in CT is reachable from the callback either, so it's hard
     * to imagine how calling it later could create a problem for us.  wr
     * is moved to wrcb_to_call in this case.
     */
725
            if (gc_is_collecting(AS_GC(wr))) {
726
                continue;
727
            }
728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749

            /* Create a new reference so that wr can't go away
             * before we can process it again.
             */
            Py_INCREF(wr);

            /* Move wr to wrcb_to_call, for the next pass. */
            wrasgc = AS_GC(wr);
            assert(wrasgc != next); /* wrasgc is reachable, but
                                       next isn't, so they can't
                                       be the same */
            gc_list_move(wrasgc, &wrcb_to_call);
        }
    }

    /* Invoke the callbacks we decided to honor.  It's safe to invoke them
     * because they can't reference unreachable objects.
     */
    while (! gc_list_is_empty(&wrcb_to_call)) {
        PyObject *temp;
        PyObject *callback;

750
        gc = (PyGC_Head*)wrcb_to_call._gc_next;
751 752 753 754 755 756 757
        op = FROM_GC(gc);
        assert(PyWeakref_Check(op));
        wr = (PyWeakReference *)op;
        callback = wr->wr_callback;
        assert(callback != NULL);

        /* copy-paste of weakrefobject.c's handle_callback() */
758
        temp = PyObject_CallFunctionObjArgs(callback, wr, NULL);
759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775
        if (temp == NULL)
            PyErr_WriteUnraisable(callback);
        else
            Py_DECREF(temp);

        /* Give up the reference we created in the first pass.  When
         * op's refcount hits 0 (which it may or may not do right now),
         * op's tp_dealloc will decref op->wr_callback too.  Note
         * that the refcount probably will hit 0 now, and because this
         * weakref was reachable to begin with, gc didn't already
         * add it to its count of freed objects.  Example:  a reachable
         * weak value dict maps some key to this reachable weakref.
         * The callback removes this key->weakref mapping from the
         * dict, leaving no other references to the weakref (excepting
         * ours).
         */
        Py_DECREF(op);
776
        if (wrcb_to_call._gc_next == (uintptr_t)gc) {
777 778 779
            /* object is still alive -- move it */
            gc_list_move(gc, old);
        }
780
        else {
781
            ++num_freed;
782
        }
783 784 785
    }

    return num_freed;
786 787
}

788
static void
789
debug_cycle(const char *msg, PyObject *op)
790
{
791 792
    PySys_FormatStderr("gc: %s <%s %p>\n",
                       msg, Py_TYPE(op)->tp_name, op);
793 794
}

795
/* Handle uncollectable garbage (cycles with tp_del slots, and stuff reachable
796
 * only from such cycles).
797 798 799 800
 * If DEBUG_SAVEALL, all objects in finalizers are appended to the module
 * garbage list (a Python list), else only the objects in finalizers with
 * __del__ methods are appended to garbage.  All objects in finalizers are
 * merged into the old list regardless.
801
 */
802
static void
803
handle_legacy_finalizers(PyGC_Head *finalizers, PyGC_Head *old)
804
{
805
    PyGC_Head *gc = GC_NEXT(finalizers);
806

807
    assert(!PyErr_Occurred());
808 809 810
    if (_PyRuntime.gc.garbage == NULL) {
        _PyRuntime.gc.garbage = PyList_New(0);
        if (_PyRuntime.gc.garbage == NULL)
811 812
            Py_FatalError("gc couldn't create gc.garbage list");
    }
813
    for (; gc != finalizers; gc = GC_NEXT(gc)) {
814 815
        PyObject *op = FROM_GC(gc);

816
        if ((_PyRuntime.gc.debug & DEBUG_SAVEALL) || has_legacy_finalizer(op)) {
817 818
            if (PyList_Append(_PyRuntime.gc.garbage, op) < 0) {
                PyErr_Clear();
819
                break;
820
            }
821 822 823 824
        }
    }

    gc_list_merge(finalizers, old);
825 826
}

827 828 829 830
/* Run first-time finalizers (if any) on all the objects in collectable.
 * Note that this may remove some (or even all) of the objects from the
 * list, due to refcounts falling to 0.
 */
831
static void
832
finalize_garbage(PyGC_Head *collectable)
833 834
{
    destructor finalize;
835 836 837 838 839 840 841 842 843 844 845
    PyGC_Head seen;

    /* While we're going through the loop, `finalize(op)` may cause op, or
     * other objects, to be reclaimed via refcounts falling to zero.  So
     * there's little we can rely on about the structure of the input
     * `collectable` list across iterations.  For safety, we always take the
     * first object in that list and move it to a temporary `seen` list.
     * If objects vanish from the `collectable` and `seen` lists we don't
     * care.
     */
    gc_list_init(&seen);
846

847
    while (!gc_list_is_empty(collectable)) {
848
        PyGC_Head *gc = GC_NEXT(collectable);
849
        PyObject *op = FROM_GC(gc);
850
        gc_list_move(gc, &seen);
851
        if (!_PyGCHead_FINALIZED(gc) &&
852 853
                PyType_HasFeature(Py_TYPE(op), Py_TPFLAGS_HAVE_FINALIZE) &&
                (finalize = Py_TYPE(op)->tp_finalize) != NULL) {
854
            _PyGCHead_SET_FINALIZED(gc);
855 856
            Py_INCREF(op);
            finalize(op);
857
            assert(!PyErr_Occurred());
858 859 860
            Py_DECREF(op);
        }
    }
861
    gc_list_merge(&seen, collectable);
862 863 864 865 866 867 868 869
}

/* Walk the collectable list and check that they are really unreachable
   from the outside (some objects could have been resurrected by a
   finalizer). */
static int
check_garbage(PyGC_Head *collectable)
{
870
    int ret = 0;
871
    PyGC_Head *gc;
872 873 874 875
    for (gc = GC_NEXT(collectable); gc != collectable; gc = GC_NEXT(gc)) {
        // Use gc_refs and break gc_prev again.
        gc_set_refs(gc, Py_REFCNT(FROM_GC(gc)));
        assert(gc_get_refs(gc) != 0);
876 877
    }
    subtract_refs(collectable);
878 879 880 881 882 883 884 885 886 887
    PyGC_Head *prev = collectable;
    for (gc = GC_NEXT(collectable); gc != collectable; gc = GC_NEXT(gc)) {
        assert(gc_get_refs(gc) >= 0);
        if (gc_get_refs(gc) != 0) {
            ret = -1;
        }
        // Restore gc_prev here.
        _PyGCHead_SET_PREV(gc, prev);
        gc_clear_collecting(gc);
        prev = gc;
888
    }
889
    return ret;
890 891
}

892
/* Break reference cycles by clearing the containers involved.  This is
893
 * tricky business as the lists can be changing and we don't know which
894 895
 * objects may be freed.  It is possible I screwed something up here.
 */
896
static void
Jeremy Hylton's avatar
Jeremy Hylton committed
897
delete_garbage(PyGC_Head *collectable, PyGC_Head *old)
898
{
899 900
    inquiry clear;

901
    assert(!PyErr_Occurred());
902
    while (!gc_list_is_empty(collectable)) {
903
        PyGC_Head *gc = GC_NEXT(collectable);
904 905
        PyObject *op = FROM_GC(gc);

906 907
        assert(Py_REFCNT(FROM_GC(gc)) > 0);

908
        if (_PyRuntime.gc.debug & DEBUG_SAVEALL) {
909 910 911 912
            assert(_PyRuntime.gc.garbage != NULL);
            if (PyList_Append(_PyRuntime.gc.garbage, op) < 0) {
                PyErr_Clear();
            }
913 914 915 916
        }
        else {
            if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
                Py_INCREF(op);
917 918 919 920 921 922
                (void) clear(op);
                if (PyErr_Occurred()) {
                    PySys_WriteStderr("Exception ignored in tp_clear of "
                                      "%.50s\n", Py_TYPE(op)->tp_name);
                    PyErr_WriteUnraisable(NULL);
                }
923 924 925
                Py_DECREF(op);
            }
        }
926
        if (GC_NEXT(collectable) == gc) {
927 928 929 930
            /* object is still alive, move it, it may die later */
            gc_list_move(gc, old);
        }
    }
931 932
}

Christian Heimes's avatar
Christian Heimes committed
933 934 935 936 937 938 939 940
/* Clear all free lists
 * All free lists are cleared during the collection of the highest generation.
 * Allocated items in the free list may keep a pymalloc arena occupied.
 * Clearing the free lists may give back memory to the OS earlier.
 */
static void
clear_freelists(void)
{
941 942 943 944 945 946
    (void)PyMethod_ClearFreeList();
    (void)PyFrame_ClearFreeList();
    (void)PyCFunction_ClearFreeList();
    (void)PyTuple_ClearFreeList();
    (void)PyUnicode_ClearFreeList();
    (void)PyFloat_ClearFreeList();
947 948
    (void)PyList_ClearFreeList();
    (void)PyDict_ClearFreeList();
949
    (void)PySet_ClearFreeList();
950
    (void)PyAsyncGen_ClearFreeLists();
951
    (void)PyContext_ClearFreeList();
Christian Heimes's avatar
Christian Heimes committed
952 953
}

954 955
/* This is the main function.  Read this to understand how the
 * collection process works. */
956
static Py_ssize_t
957 958
collect(int generation, Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
        int nofail)
959
{
960 961 962 963 964 965 966 967
    int i;
    Py_ssize_t m = 0; /* # objects collected */
    Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
    PyGC_Head *young; /* the generation we are examining */
    PyGC_Head *old; /* next older generation */
    PyGC_Head unreachable; /* non-problematic unreachable trash */
    PyGC_Head finalizers;  /* objects with, & reachable from, __del__ */
    PyGC_Head *gc;
968
    _PyTime_t t1 = 0;   /* initialize to prevent a compiler warning */
969

970
    struct gc_generation_stats *stats = &_PyRuntime.gc.generation_stats[generation];
971

972
    if (_PyRuntime.gc.debug & DEBUG_STATS) {
973 974 975 976
        PySys_WriteStderr("gc: collecting generation %d...\n",
                          generation);
        PySys_WriteStderr("gc: objects in each generation:");
        for (i = 0; i < NUM_GENERATIONS; i++)
977
            PySys_FormatStderr(" %zd",
978
                              gc_list_size(GEN_HEAD(i)));
979 980
        PySys_WriteStderr("\ngc: objects in permanent generation: %zd",
                         gc_list_size(&_PyRuntime.gc.permanent_generation.head));
981
        t1 = _PyTime_GetMonotonicClock();
982

983 984 985
        PySys_WriteStderr("\n");
    }

986 987 988
    if (PyDTrace_GC_START_ENABLED())
        PyDTrace_GC_START(generation);

989 990
    /* update collection and allocation counters */
    if (generation+1 < NUM_GENERATIONS)
991
        _PyRuntime.gc.generations[generation+1].count += 1;
992
    for (i = 0; i <= generation; i++)
993
        _PyRuntime.gc.generations[i].count = 0;
994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006

    /* merge younger generations with one we are currently collecting */
    for (i = 0; i < generation; i++) {
        gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
    }

    /* handy references */
    young = GEN_HEAD(generation);
    if (generation < NUM_GENERATIONS-1)
        old = GEN_HEAD(generation+1);
    else
        old = young;

1007 1008
    validate_list(young, 0);
    validate_list(old, 0);
1009 1010 1011 1012 1013
    /* Using ob_refcnt and gc_refs, calculate which objects in the
     * container set are reachable from outside the set (i.e., have a
     * refcount greater than 0 when all the references within the
     * set are taken into account).
     */
1014
    update_refs(young);  // gc_prev is used for gc_refs
1015 1016 1017 1018 1019 1020 1021 1022 1023
    subtract_refs(young);

    /* Leave everything reachable from outside young in young, and move
     * everything else (in young) to unreachable.
     * NOTE:  This used to move the reachable objects into a reachable
     * set instead.  But most things usually turn out to be reachable,
     * so it's more efficient to move the unreachable things.
     */
    gc_list_init(&unreachable);
1024 1025
    move_unreachable(young, &unreachable);  // gc_prev is pointer again
    validate_list(young, 0);
1026

1027
    untrack_tuples(young);
1028 1029 1030
    /* Move reachable objects to next generation. */
    if (young != old) {
        if (generation == NUM_GENERATIONS - 2) {
1031
            _PyRuntime.gc.long_lived_pending += gc_list_size(young);
1032 1033 1034 1035
        }
        gc_list_merge(young, old);
    }
    else {
1036 1037 1038
        /* We only untrack dicts in full collections, to avoid quadratic
           dict build-up. See issue #14775. */
        untrack_dicts(young);
1039 1040
        _PyRuntime.gc.long_lived_pending = 0;
        _PyRuntime.gc.long_lived_total = gc_list_size(young);
1041 1042 1043
    }

    /* All objects in unreachable are trash, but objects reachable from
1044
     * legacy finalizers (e.g. tp_del) can't safely be deleted.
1045 1046
     */
    gc_list_init(&finalizers);
1047 1048
    // NEXT_MASK_UNREACHABLE is cleared here.
    // After move_legacy_finalizers(), unreachable is normal list.
1049 1050
    move_legacy_finalizers(&unreachable, &finalizers);
    /* finalizers contains the unreachable objects with a legacy finalizer;
1051 1052 1053
     * unreachable objects reachable *from* those are also uncollectable,
     * and we move those into the finalizers list too.
     */
1054
    move_legacy_finalizer_reachable(&finalizers);
1055

1056 1057 1058
    validate_list(&finalizers, 0);
    validate_list(&unreachable, PREV_MASK_COLLECTING);

1059 1060 1061
    /* Collect statistics on collectable objects found and print
     * debugging information.
     */
1062
    for (gc = GC_NEXT(&unreachable); gc != &unreachable; gc = GC_NEXT(gc)) {
1063
        m++;
1064
        if (_PyRuntime.gc.debug & DEBUG_COLLECTABLE) {
1065 1066 1067 1068 1069 1070 1071
            debug_cycle("collectable", FROM_GC(gc));
        }
    }

    /* Clear weakrefs and invoke callbacks as necessary. */
    m += handle_weakrefs(&unreachable, old);

1072 1073 1074
    validate_list(old, 0);
    validate_list(&unreachable, PREV_MASK_COLLECTING);

1075
    /* Call tp_finalize on objects which have one. */
1076
    finalize_garbage(&unreachable);
1077

1078
    if (check_garbage(&unreachable)) { // clear PREV_MASK_COLLECTING here
1079 1080 1081 1082 1083 1084 1085 1086 1087
        gc_list_merge(&unreachable, old);
    }
    else {
        /* Call tp_clear on objects in the unreachable set.  This will cause
         * the reference cycles to be broken.  It may also cause some objects
         * in finalizers to be freed.
         */
        delete_garbage(&unreachable, old);
    }
1088 1089 1090

    /* Collect statistics on uncollectable objects found and print
     * debugging information. */
1091
    for (gc = GC_NEXT(&finalizers); gc != &finalizers; gc = GC_NEXT(gc)) {
1092
        n++;
1093
        if (_PyRuntime.gc.debug & DEBUG_UNCOLLECTABLE)
1094 1095
            debug_cycle("uncollectable", FROM_GC(gc));
    }
1096
    if (_PyRuntime.gc.debug & DEBUG_STATS) {
1097
        _PyTime_t t2 = _PyTime_GetMonotonicClock();
1098

1099 1100 1101
        if (m == 0 && n == 0)
            PySys_WriteStderr("gc: done");
        else
1102 1103
            PySys_FormatStderr(
                "gc: done, %zd unreachable, %zd uncollectable",
1104
                n+m, n);
1105 1106
        PySys_WriteStderr(", %.4fs elapsed\n",
                          _PyTime_AsSecondsDouble(t2 - t1));
1107 1108 1109 1110 1111 1112
    }

    /* Append instances in the uncollectable set to a Python
     * reachable list of garbage.  The programmer has to deal with
     * this if they insist on creating this type of structure.
     */
1113
    handle_legacy_finalizers(&finalizers, old);
1114
    validate_list(old, 0);
1115 1116 1117 1118 1119 1120 1121 1122

    /* Clear free list only during the collection of the highest
     * generation */
    if (generation == NUM_GENERATIONS-1) {
        clear_freelists();
    }

    if (PyErr_Occurred()) {
1123 1124 1125 1126 1127 1128 1129 1130 1131
        if (nofail) {
            PyErr_Clear();
        }
        else {
            if (gc_str == NULL)
                gc_str = PyUnicode_FromString("garbage collection");
            PyErr_WriteUnraisable(gc_str);
            Py_FatalError("unexpected exception during garbage collection");
        }
1132
    }
1133

1134
    /* Update stats */
1135 1136 1137 1138
    if (n_collected)
        *n_collected = m;
    if (n_uncollectable)
        *n_uncollectable = n;
1139 1140 1141
    stats->collections++;
    stats->collected += m;
    stats->uncollectable += n;
1142 1143 1144 1145

    if (PyDTrace_GC_DONE_ENABLED())
        PyDTrace_GC_DONE(n+m);

1146
    assert(!PyErr_Occurred());
1147
    return n+m;
1148 1149
}

1150 1151 1152 1153 1154 1155 1156 1157 1158 1159
/* Invoke progress callbacks to notify clients that garbage collection
 * is starting or stopping
 */
static void
invoke_gc_callback(const char *phase, int generation,
                   Py_ssize_t collected, Py_ssize_t uncollectable)
{
    Py_ssize_t i;
    PyObject *info = NULL;

1160
    assert(!PyErr_Occurred());
1161
    /* we may get called very early */
1162
    if (_PyRuntime.gc.callbacks == NULL)
1163 1164
        return;
    /* The local variable cannot be rebound, check it for sanity */
1165
    assert(PyList_CheckExact(_PyRuntime.gc.callbacks));
1166
    if (PyList_GET_SIZE(_PyRuntime.gc.callbacks) != 0) {
1167 1168 1169 1170 1171 1172 1173 1174 1175
        info = Py_BuildValue("{sisnsn}",
            "generation", generation,
            "collected", collected,
            "uncollectable", uncollectable);
        if (info == NULL) {
            PyErr_WriteUnraisable(NULL);
            return;
        }
    }
1176 1177
    for (i=0; i<PyList_GET_SIZE(_PyRuntime.gc.callbacks); i++) {
        PyObject *r, *cb = PyList_GET_ITEM(_PyRuntime.gc.callbacks, i);
1178 1179
        Py_INCREF(cb); /* make sure cb doesn't go away */
        r = PyObject_CallFunction(cb, "sO", phase, info);
1180
        if (r == NULL) {
1181
            PyErr_WriteUnraisable(cb);
1182 1183 1184 1185
        }
        else {
            Py_DECREF(r);
        }
1186 1187 1188
        Py_DECREF(cb);
    }
    Py_XDECREF(info);
1189
    assert(!PyErr_Occurred());
1190 1191 1192 1193 1194 1195 1196 1197 1198
}

/* Perform garbage collection of a generation and invoke
 * progress callbacks.
 */
static Py_ssize_t
collect_with_callback(int generation)
{
    Py_ssize_t result, collected, uncollectable;
1199
    assert(!PyErr_Occurred());
1200
    invoke_gc_callback("start", generation, 0, 0);
1201
    result = collect(generation, &collected, &uncollectable, 0);
1202
    invoke_gc_callback("stop", generation, collected, uncollectable);
1203
    assert(!PyErr_Occurred());
1204 1205 1206
    return result;
}

1207
static Py_ssize_t
1208 1209
collect_generations(void)
{
1210 1211 1212 1213 1214 1215 1216
    int i;
    Py_ssize_t n = 0;

    /* Find the oldest generation (highest numbered) where the count
     * exceeds the threshold.  Objects in the that generation and
     * generations younger than it will be collected. */
    for (i = NUM_GENERATIONS-1; i >= 0; i--) {
1217
        if (_PyRuntime.gc.generations[i].count > _PyRuntime.gc.generations[i].threshold) {
1218 1219 1220 1221 1222
            /* Avoid quadratic performance degradation in number
               of tracked objects. See comments at the beginning
               of this file, and issue #4074.
            */
            if (i == NUM_GENERATIONS - 1
1223
                && _PyRuntime.gc.long_lived_pending < _PyRuntime.gc.long_lived_total / 4)
1224
                continue;
1225
            n = collect_with_callback(i);
1226 1227 1228 1229
            break;
        }
    }
    return n;
1230 1231
}

1232 1233 1234 1235 1236 1237 1238
#include "clinic/gcmodule.c.h"

/*[clinic input]
gc.enable

Enable automatic garbage collection.
[clinic start generated code]*/
1239 1240

static PyObject *
1241 1242
gc_enable_impl(PyObject *module)
/*[clinic end generated code: output=45a427e9dce9155c input=81ac4940ca579707]*/
1243
{
1244
    _PyRuntime.gc.enabled = 1;
1245
    Py_RETURN_NONE;
1246 1247
}

1248 1249 1250 1251 1252
/*[clinic input]
gc.disable

Disable automatic garbage collection.
[clinic start generated code]*/
1253 1254

static PyObject *
1255 1256
gc_disable_impl(PyObject *module)
/*[clinic end generated code: output=97d1030f7aa9d279 input=8c2e5a14e800d83b]*/
1257
{
1258
    _PyRuntime.gc.enabled = 0;
1259
    Py_RETURN_NONE;
1260 1261
}

1262 1263
/*[clinic input]
gc.isenabled -> bool
1264

1265 1266 1267 1268 1269 1270
Returns true if automatic garbage collection is enabled.
[clinic start generated code]*/

static int
gc_isenabled_impl(PyObject *module)
/*[clinic end generated code: output=1874298331c49130 input=30005e0422373b31]*/
1271
{
1272
    return _PyRuntime.gc.enabled;
1273
}
1274

1275 1276
/*[clinic input]
gc.collect -> Py_ssize_t
1277

1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291
    generation: int(c_default="NUM_GENERATIONS - 1") = 2

Run the garbage collector.

With no arguments, run a full collection.  The optional argument
may be an integer specifying which generation to collect.  A ValueError
is raised if the generation number is invalid.

The number of unreachable objects is returned.
[clinic start generated code]*/

static Py_ssize_t
gc_collect_impl(PyObject *module, int generation)
/*[clinic end generated code: output=b697e633043233c7 input=40720128b682d879]*/
1292
{
1293 1294
    Py_ssize_t n;

1295
    if (generation < 0 || generation >= NUM_GENERATIONS) {
1296
        PyErr_SetString(PyExc_ValueError, "invalid generation");
1297
        return -1;
1298 1299
    }

1300
    if (_PyRuntime.gc.collecting)
1301 1302
        n = 0; /* already collecting, don't do anything */
    else {
1303
        _PyRuntime.gc.collecting = 1;
1304
        n = collect_with_callback(generation);
1305
        _PyRuntime.gc.collecting = 0;
1306 1307
    }

1308
    return n;
1309 1310
}

1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327
/*[clinic input]
gc.set_debug

    flags: int
        An integer that can have the following bits turned on:
          DEBUG_STATS - Print statistics during collection.
          DEBUG_COLLECTABLE - Print collectable objects found.
          DEBUG_UNCOLLECTABLE - Print unreachable but uncollectable objects
            found.
          DEBUG_SAVEALL - Save objects to gc.garbage rather than freeing them.
          DEBUG_LEAK - Debug leaking programs (everything but STATS).
    /

Set the garbage collection debugging flags.

Debugging information is written to sys.stderr.
[clinic start generated code]*/
1328 1329

static PyObject *
1330 1331
gc_set_debug_impl(PyObject *module, int flags)
/*[clinic end generated code: output=7c8366575486b228 input=5e5ce15e84fbed15]*/
1332
{
1333
    _PyRuntime.gc.debug = flags;
1334

1335
    Py_RETURN_NONE;
1336 1337
}

1338 1339
/*[clinic input]
gc.get_debug -> int
1340

1341 1342 1343 1344 1345 1346
Get the garbage collection debugging flags.
[clinic start generated code]*/

static int
gc_get_debug_impl(PyObject *module)
/*[clinic end generated code: output=91242f3506cd1e50 input=91a101e1c3b98366]*/
1347
{
1348
    return _PyRuntime.gc.debug;
1349 1350
}

1351
PyDoc_STRVAR(gc_set_thresh__doc__,
1352
"set_threshold(threshold0, [threshold1, threshold2]) -> None\n"
1353 1354
"\n"
"Sets the collection thresholds.  Setting threshold0 to zero disables\n"
1355
"collection.\n");
1356 1357

static PyObject *
1358
gc_set_thresh(PyObject *self, PyObject *args)
1359
{
1360 1361
    int i;
    if (!PyArg_ParseTuple(args, "i|ii:set_threshold",
1362 1363 1364
                          &_PyRuntime.gc.generations[0].threshold,
                          &_PyRuntime.gc.generations[1].threshold,
                          &_PyRuntime.gc.generations[2].threshold))
1365 1366 1367
        return NULL;
    for (i = 2; i < NUM_GENERATIONS; i++) {
        /* generations higher than 2 get the same threshold */
1368
        _PyRuntime.gc.generations[i].threshold = _PyRuntime.gc.generations[2].threshold;
1369 1370
    }

1371
    Py_RETURN_NONE;
1372 1373
}

1374 1375 1376 1377 1378
/*[clinic input]
gc.get_threshold

Return the current collection thresholds.
[clinic start generated code]*/
1379 1380

static PyObject *
1381 1382
gc_get_threshold_impl(PyObject *module)
/*[clinic end generated code: output=7902bc9f41ecbbd8 input=286d79918034d6e6]*/
1383
{
1384
    return Py_BuildValue("(iii)",
1385 1386 1387
                         _PyRuntime.gc.generations[0].threshold,
                         _PyRuntime.gc.generations[1].threshold,
                         _PyRuntime.gc.generations[2].threshold);
1388 1389
}

1390 1391 1392 1393 1394
/*[clinic input]
gc.get_count

Return a three-tuple of the current collection counts.
[clinic start generated code]*/
1395 1396

static PyObject *
1397 1398
gc_get_count_impl(PyObject *module)
/*[clinic end generated code: output=354012e67b16398f input=a392794a08251751]*/
1399
{
1400
    return Py_BuildValue("(iii)",
1401 1402 1403
                         _PyRuntime.gc.generations[0].count,
                         _PyRuntime.gc.generations[1].count,
                         _PyRuntime.gc.generations[2].count);
1404 1405
}

1406
static int
1407
referrersvisit(PyObject* obj, PyObject *objs)
1408
{
1409 1410 1411 1412 1413
    Py_ssize_t i;
    for (i = 0; i < PyTuple_GET_SIZE(objs); i++)
        if (PyTuple_GET_ITEM(objs, i) == obj)
            return 1;
    return 0;
1414 1415
}

1416
static int
1417
gc_referrers_for(PyObject *objs, PyGC_Head *list, PyObject *resultlist)
1418
{
1419 1420 1421
    PyGC_Head *gc;
    PyObject *obj;
    traverseproc traverse;
1422
    for (gc = GC_NEXT(list); gc != list; gc = GC_NEXT(gc)) {
1423 1424 1425 1426 1427 1428 1429 1430 1431 1432
        obj = FROM_GC(gc);
        traverse = Py_TYPE(obj)->tp_traverse;
        if (obj == objs || obj == resultlist)
            continue;
        if (traverse(obj, (visitproc)referrersvisit, objs)) {
            if (PyList_Append(resultlist, obj) < 0)
                return 0; /* error */
        }
    }
    return 1; /* no error */
1433 1434
}

1435
PyDoc_STRVAR(gc_get_referrers__doc__,
1436
"get_referrers(*objs) -> list\n\
1437
Return the list of objects that directly refer to any of objs.");
1438

1439
static PyObject *
1440
gc_get_referrers(PyObject *self, PyObject *args)
1441
{
1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452
    int i;
    PyObject *result = PyList_New(0);
    if (!result) return NULL;

    for (i = 0; i < NUM_GENERATIONS; i++) {
        if (!(gc_referrers_for(args, GEN_HEAD(i), result))) {
            Py_DECREF(result);
            return NULL;
        }
    }
    return result;
1453
}
1454

1455
/* Append obj to list; return true if error (out of memory), false if OK. */
1456
static int
1457
referentsvisit(PyObject *obj, PyObject *list)
1458
{
1459
    return PyList_Append(list, obj) < 0;
1460 1461
}

1462 1463
PyDoc_STRVAR(gc_get_referents__doc__,
"get_referents(*objs) -> list\n\
1464
Return the list of objects that are directly referred to by objs.");
1465 1466

static PyObject *
1467
gc_get_referents(PyObject *self, PyObject *args)
1468
{
1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489
    Py_ssize_t i;
    PyObject *result = PyList_New(0);

    if (result == NULL)
        return NULL;

    for (i = 0; i < PyTuple_GET_SIZE(args); i++) {
        traverseproc traverse;
        PyObject *obj = PyTuple_GET_ITEM(args, i);

        if (! PyObject_IS_GC(obj))
            continue;
        traverse = Py_TYPE(obj)->tp_traverse;
        if (! traverse)
            continue;
        if (traverse(obj, (visitproc)referentsvisit, result)) {
            Py_DECREF(result);
            return NULL;
        }
    }
    return result;
1490 1491
}

1492 1493 1494 1495 1496
/*[clinic input]
gc.get_objects

Return a list of objects tracked by the collector (excluding the list returned).
[clinic start generated code]*/
1497 1498

static PyObject *
1499 1500
gc_get_objects_impl(PyObject *module)
/*[clinic end generated code: output=fcb95d2e23e1f750 input=9439fe8170bf35d8]*/
1501
{
1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514
    int i;
    PyObject* result;

    result = PyList_New(0);
    if (result == NULL)
        return NULL;
    for (i = 0; i < NUM_GENERATIONS; i++) {
        if (append_objects(result, GEN_HEAD(i))) {
            Py_DECREF(result);
            return NULL;
        }
    }
    return result;
1515 1516
}

1517 1518 1519 1520 1521
/*[clinic input]
gc.get_stats

Return a list of dictionaries containing per-generation statistics.
[clinic start generated code]*/
1522 1523

static PyObject *
1524 1525
gc_get_stats_impl(PyObject *module)
/*[clinic end generated code: output=a8ab1d8a5d26f3ab input=1ef4ed9d17b1a470]*/
1526 1527 1528 1529 1530 1531 1532 1533
{
    int i;
    PyObject *result;
    struct gc_generation_stats stats[NUM_GENERATIONS], *st;

    /* To get consistent values despite allocations while constructing
       the result list, we use a snapshot of the running stats. */
    for (i = 0; i < NUM_GENERATIONS; i++) {
1534
        stats[i] = _PyRuntime.gc.generation_stats[i];
1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564
    }

    result = PyList_New(0);
    if (result == NULL)
        return NULL;

    for (i = 0; i < NUM_GENERATIONS; i++) {
        PyObject *dict;
        st = &stats[i];
        dict = Py_BuildValue("{snsnsn}",
                             "collections", st->collections,
                             "collected", st->collected,
                             "uncollectable", st->uncollectable
                            );
        if (dict == NULL)
            goto error;
        if (PyList_Append(result, dict)) {
            Py_DECREF(dict);
            goto error;
        }
        Py_DECREF(dict);
    }
    return result;

error:
    Py_XDECREF(result);
    return NULL;
}


1565 1566 1567 1568 1569 1570 1571 1572 1573 1574
/*[clinic input]
gc.is_tracked

    obj: object
    /

Returns true if the object is tracked by the garbage collector.

Simple atomic objects will return false.
[clinic start generated code]*/
1575 1576

static PyObject *
1577 1578
gc_is_tracked(PyObject *module, PyObject *obj)
/*[clinic end generated code: output=14f0103423b28e31 input=d83057f170ea2723]*/
1579
{
1580 1581
    PyObject *result;

1582
    if (PyObject_IS_GC(obj) && _PyObject_GC_IS_TRACKED(obj))
1583 1584 1585 1586 1587
        result = Py_True;
    else
        result = Py_False;
    Py_INCREF(result);
    return result;
1588 1589
}

1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627
/*[clinic input]
gc.freeze

Freeze all current tracked objects and ignore them for future collections.

This can be used before a POSIX fork() call to make the gc copy-on-write friendly.
Note: collection before a POSIX fork() call may free pages for future allocation
which can cause copy-on-write.
[clinic start generated code]*/

static PyObject *
gc_freeze_impl(PyObject *module)
/*[clinic end generated code: output=502159d9cdc4c139 input=b602b16ac5febbe5]*/
{
    for (int i = 0; i < NUM_GENERATIONS; ++i) {
        gc_list_merge(GEN_HEAD(i), &_PyRuntime.gc.permanent_generation.head);
        _PyRuntime.gc.generations[i].count = 0;
    }
    Py_RETURN_NONE;
}

/*[clinic input]
gc.unfreeze

Unfreeze all objects in the permanent generation.

Put all objects in the permanent generation back into oldest generation.
[clinic start generated code]*/

static PyObject *
gc_unfreeze_impl(PyObject *module)
/*[clinic end generated code: output=1c15f2043b25e169 input=2dd52b170f4cef6c]*/
{
    gc_list_merge(&_PyRuntime.gc.permanent_generation.head, GEN_HEAD(NUM_GENERATIONS-1));
    Py_RETURN_NONE;
}

/*[clinic input]
1628
gc.get_freeze_count -> Py_ssize_t
1629 1630 1631 1632

Return the number of objects in the permanent generation.
[clinic start generated code]*/

1633
static Py_ssize_t
1634
gc_get_freeze_count_impl(PyObject *module)
1635
/*[clinic end generated code: output=61cbd9f43aa032e1 input=45ffbc65cfe2a6ed]*/
1636 1637 1638 1639
{
    return gc_list_size(&_PyRuntime.gc.permanent_generation.head);
}

1640

1641
PyDoc_STRVAR(gc__doc__,
1642 1643
"This module provides access to the garbage collector for reference cycles.\n"
"\n"
1644 1645 1646
"enable() -- Enable automatic garbage collection.\n"
"disable() -- Disable automatic garbage collection.\n"
"isenabled() -- Returns true if automatic collection is enabled.\n"
1647
"collect() -- Do a full collection right now.\n"
1648
"get_count() -- Return the current collection counts.\n"
1649
"get_stats() -- Return list of dictionaries containing per-generation stats.\n"
1650 1651 1652 1653
"set_debug() -- Set debugging flags.\n"
"get_debug() -- Get debugging flags.\n"
"set_threshold() -- Set the collection thresholds.\n"
"get_threshold() -- Return the current the collection thresholds.\n"
1654
"get_objects() -- Return a list of all objects tracked by the collector.\n"
1655
"is_tracked() -- Returns true if a given object is tracked.\n"
1656
"get_referrers() -- Return the list of objects that refer to an object.\n"
1657 1658 1659 1660
"get_referents() -- Return the list of objects that an object refers to.\n"
"freeze() -- Freeze all tracked objects and ignore them for future collections.\n"
"unfreeze() -- Unfreeze all objects in the permanent generation.\n"
"get_freeze_count() -- Return the number of objects in the permanent generation.\n");
1661 1662

static PyMethodDef GcMethods[] = {
1663 1664 1665 1666 1667 1668
    GC_ENABLE_METHODDEF
    GC_DISABLE_METHODDEF
    GC_ISENABLED_METHODDEF
    GC_SET_DEBUG_METHODDEF
    GC_GET_DEBUG_METHODDEF
    GC_GET_COUNT_METHODDEF
1669
    {"set_threshold",  gc_set_thresh, METH_VARARGS, gc_set_thresh__doc__},
1670 1671 1672 1673 1674
    GC_GET_THRESHOLD_METHODDEF
    GC_COLLECT_METHODDEF
    GC_GET_OBJECTS_METHODDEF
    GC_GET_STATS_METHODDEF
    GC_IS_TRACKED_METHODDEF
1675 1676 1677 1678
    {"get_referrers",  gc_get_referrers, METH_VARARGS,
        gc_get_referrers__doc__},
    {"get_referents",  gc_get_referents, METH_VARARGS,
        gc_get_referents__doc__},
1679 1680 1681
    GC_FREEZE_METHODDEF
    GC_UNFREEZE_METHODDEF
    GC_GET_FREEZE_COUNT_METHODDEF
1682
    {NULL,      NULL}           /* Sentinel */
1683 1684
};

1685
static struct PyModuleDef gcmodule = {
1686
    PyModuleDef_HEAD_INIT,
1687 1688 1689 1690 1691 1692 1693 1694
    "gc",              /* m_name */
    gc__doc__,         /* m_doc */
    -1,                /* m_size */
    GcMethods,         /* m_methods */
    NULL,              /* m_reload */
    NULL,              /* m_traverse */
    NULL,              /* m_clear */
    NULL               /* m_free */
1695 1696
};

1697
PyMODINIT_FUNC
1698
PyInit_gc(void)
1699
{
1700 1701 1702 1703 1704 1705 1706
    PyObject *m;

    m = PyModule_Create(&gcmodule);

    if (m == NULL)
        return NULL;

1707 1708 1709
    if (_PyRuntime.gc.garbage == NULL) {
        _PyRuntime.gc.garbage = PyList_New(0);
        if (_PyRuntime.gc.garbage == NULL)
1710 1711
            return NULL;
    }
1712 1713
    Py_INCREF(_PyRuntime.gc.garbage);
    if (PyModule_AddObject(m, "garbage", _PyRuntime.gc.garbage) < 0)
1714 1715
        return NULL;

1716 1717 1718
    if (_PyRuntime.gc.callbacks == NULL) {
        _PyRuntime.gc.callbacks = PyList_New(0);
        if (_PyRuntime.gc.callbacks == NULL)
1719 1720
            return NULL;
    }
1721 1722
    Py_INCREF(_PyRuntime.gc.callbacks);
    if (PyModule_AddObject(m, "callbacks", _PyRuntime.gc.callbacks) < 0)
1723 1724
        return NULL;

1725
#define ADD_INT(NAME) if (PyModule_AddIntConstant(m, #NAME, NAME) < 0) return NULL
1726 1727 1728 1729 1730
    ADD_INT(DEBUG_STATS);
    ADD_INT(DEBUG_COLLECTABLE);
    ADD_INT(DEBUG_UNCOLLECTABLE);
    ADD_INT(DEBUG_SAVEALL);
    ADD_INT(DEBUG_LEAK);
1731
#undef ADD_INT
1732
    return m;
1733 1734
}

1735
/* API to invoke gc.collect() from C */
1736
Py_ssize_t
1737 1738
PyGC_Collect(void)
{
1739
    Py_ssize_t n;
1740

1741
    if (_PyRuntime.gc.collecting)
1742 1743
        n = 0; /* already collecting, don't do anything */
    else {
1744
        PyObject *exc, *value, *tb;
1745
        _PyRuntime.gc.collecting = 1;
1746
        PyErr_Fetch(&exc, &value, &tb);
1747
        n = collect_with_callback(NUM_GENERATIONS - 1);
1748
        PyErr_Restore(exc, value, tb);
1749
        _PyRuntime.gc.collecting = 0;
1750
    }
1751

1752
    return n;
1753 1754
}

1755 1756 1757
Py_ssize_t
_PyGC_CollectIfEnabled(void)
{
1758
    if (!_PyRuntime.gc.enabled)
1759 1760 1761 1762 1763
        return 0;

    return PyGC_Collect();
}

1764 1765 1766 1767 1768
Py_ssize_t
_PyGC_CollectNoFail(void)
{
    Py_ssize_t n;

1769
    assert(!PyErr_Occurred());
1770 1771 1772 1773 1774 1775
    /* Ideally, this function is only called on interpreter shutdown,
       and therefore not recursively.  Unfortunately, when there are daemon
       threads, a daemon thread can start a cyclic garbage collection
       during interpreter shutdown (and then never finish it).
       See http://bugs.python.org/issue8713#msg195178 for an example.
       */
1776
    if (_PyRuntime.gc.collecting)
1777 1778
        n = 0;
    else {
1779
        _PyRuntime.gc.collecting = 1;
1780
        n = collect(NUM_GENERATIONS - 1, NULL, NULL, 1);
1781
        _PyRuntime.gc.collecting = 0;
1782
    }
1783 1784
    return n;
}
1785

1786
void
1787
_PyGC_DumpShutdownStats(void)
1788
{
1789 1790
    if (!(_PyRuntime.gc.debug & DEBUG_SAVEALL)
        && _PyRuntime.gc.garbage != NULL && PyList_GET_SIZE(_PyRuntime.gc.garbage) > 0) {
1791
        const char *message;
1792
        if (_PyRuntime.gc.debug & DEBUG_UNCOLLECTABLE)
1793
            message = "gc: %zd uncollectable objects at " \
1794 1795
                "shutdown";
        else
1796
            message = "gc: %zd uncollectable objects at " \
1797
                "shutdown; use gc.set_debug(gc.DEBUG_UNCOLLECTABLE) to list them";
1798 1799 1800 1801 1802
        /* PyErr_WarnFormat does too many things and we are at shutdown,
           the warnings module's dependencies (e.g. linecache) may be gone
           already. */
        if (PyErr_WarnExplicitFormat(PyExc_ResourceWarning, "gc", 0,
                                     "gc", NULL, message,
1803
                                     PyList_GET_SIZE(_PyRuntime.gc.garbage)))
1804
            PyErr_WriteUnraisable(NULL);
1805
        if (_PyRuntime.gc.debug & DEBUG_UNCOLLECTABLE) {
1806
            PyObject *repr = NULL, *bytes = NULL;
1807
            repr = PyObject_Repr(_PyRuntime.gc.garbage);
1808
            if (!repr || !(bytes = PyUnicode_EncodeFSDefault(repr)))
1809
                PyErr_WriteUnraisable(_PyRuntime.gc.garbage);
1810 1811
            else {
                PySys_WriteStderr(
1812
                    "      %s\n",
1813 1814 1815 1816 1817 1818 1819
                    PyBytes_AS_STRING(bytes)
                    );
            }
            Py_XDECREF(repr);
            Py_XDECREF(bytes);
        }
    }
1820 1821 1822 1823 1824
}

void
_PyGC_Fini(void)
{
1825
    Py_CLEAR(_PyRuntime.gc.callbacks);
1826 1827
}

1828
/* for debugging */
1829 1830
void
_PyGC_Dump(PyGC_Head *g)
1831
{
1832
    _PyObject_Dump(FROM_GC(g));
1833 1834 1835 1836 1837
}

/* extension modules might be compiled with GC support so these
   functions must always be available */

1838 1839 1840 1841 1842
#undef PyObject_GC_Track
#undef PyObject_GC_UnTrack
#undef PyObject_GC_Del
#undef _PyObject_GC_Malloc

1843
void
1844
PyObject_GC_Track(void *op)
1845
{
1846
    _PyObject_GC_TRACK(op);
1847 1848
}

1849 1850
void
PyObject_GC_UnTrack(void *op)
1851
{
1852 1853 1854
    /* Obscure:  the Py_TRASHCAN mechanism requires that we be able to
     * call PyObject_GC_UnTrack twice on an object.
     */
1855
    if (_PyObject_GC_IS_TRACKED(op)) {
1856
        _PyObject_GC_UNTRACK(op);
1857
    }
1858 1859
}

1860 1861
static PyObject *
_PyObject_GC_Alloc(int use_calloc, size_t basicsize)
1862
{
1863 1864
    PyObject *op;
    PyGC_Head *g;
1865
    size_t size;
1866 1867
    if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
        return PyErr_NoMemory();
1868 1869 1870 1871 1872
    size = sizeof(PyGC_Head) + basicsize;
    if (use_calloc)
        g = (PyGC_Head *)PyObject_Calloc(1, size);
    else
        g = (PyGC_Head *)PyObject_Malloc(size);
1873 1874
    if (g == NULL)
        return PyErr_NoMemory();
1875 1876 1877
    assert(((uintptr_t)g & 3) == 0);  // g must be aligned 4bytes boundary
    g->_gc_next = 0;
    g->_gc_prev = 0;
1878 1879 1880 1881 1882
    _PyRuntime.gc.generations[0].count++; /* number of allocated GC objects */
    if (_PyRuntime.gc.generations[0].count > _PyRuntime.gc.generations[0].threshold &&
        _PyRuntime.gc.enabled &&
        _PyRuntime.gc.generations[0].threshold &&
        !_PyRuntime.gc.collecting &&
1883
        !PyErr_Occurred()) {
1884
        _PyRuntime.gc.collecting = 1;
1885
        collect_generations();
1886
        _PyRuntime.gc.collecting = 0;
1887 1888 1889
    }
    op = FROM_GC(g);
    return op;
1890 1891
}

1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903
PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
    return _PyObject_GC_Alloc(0, basicsize);
}

PyObject *
_PyObject_GC_Calloc(size_t basicsize)
{
    return _PyObject_GC_Alloc(1, basicsize);
}

1904 1905 1906
PyObject *
_PyObject_GC_New(PyTypeObject *tp)
{
1907 1908 1909 1910
    PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
    if (op != NULL)
        op = PyObject_INIT(op, tp);
    return op;
1911 1912 1913
}

PyVarObject *
Martin v. Löwis's avatar
Martin v. Löwis committed
1914
_PyObject_GC_NewVar(PyTypeObject *tp, Py_ssize_t nitems)
1915
{
1916 1917 1918 1919 1920 1921 1922 1923 1924
    size_t size;
    PyVarObject *op;

    if (nitems < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }
    size = _PyObject_VAR_SIZE(tp, nitems);
    op = (PyVarObject *) _PyObject_GC_Malloc(size);
1925 1926 1927
    if (op != NULL)
        op = PyObject_INIT_VAR(op, tp, nitems);
    return op;
1928 1929 1930
}

PyVarObject *
1931
_PyObject_GC_Resize(PyVarObject *op, Py_ssize_t nitems)
1932
{
1933 1934
    const size_t basicsize = _PyObject_VAR_SIZE(Py_TYPE(op), nitems);
    PyGC_Head *g = AS_GC(op);
1935
    assert(!_PyObject_GC_IS_TRACKED(op));
1936 1937 1938 1939 1940 1941 1942 1943
    if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
        return (PyVarObject *)PyErr_NoMemory();
    g = (PyGC_Head *)PyObject_REALLOC(g,  sizeof(PyGC_Head) + basicsize);
    if (g == NULL)
        return (PyVarObject *)PyErr_NoMemory();
    op = (PyVarObject *) FROM_GC(g);
    Py_SIZE(op) = nitems;
    return op;
1944 1945 1946
}

void
1947
PyObject_GC_Del(void *op)
1948
{
1949
    PyGC_Head *g = AS_GC(op);
1950
    if (_PyObject_GC_IS_TRACKED(op)) {
1951
        gc_list_remove(g);
1952
    }
1953 1954
    if (_PyRuntime.gc.generations[0].count > 0) {
        _PyRuntime.gc.generations[0].count--;
1955 1956
    }
    PyObject_FREE(g);
1957
}