"Immortal" objects aren't immortal and that breaks things.

[markshannon]

Bug report

Bug description:

Immortal objects should live forever. By definition, immortality is a permanent property of an object; if it can loose immortality, then it wasn't immortal in the first place.

Immortality allows some useful optimizations and safety guarantees that can make CPython faster and more robust.

Which would be great, if we didn't play fast and loose with immortality.
For no good reason that I'm aware of there are two functions _Py_ClearImmortal and _Py_SetMortal that make immortal objects mortal. This is nonsense. We must remove these functions.

We have also added _Py_IsImmortalLoose because it is too easy for C-extensions
Instead of adding these workarounds, we need to fix this problem as well.

Let's fix immortality so that we can rely on it and take advantage of it.

CPython versions tested on:

3.12, 3.13, CPython main branch

Operating systems tested on:

Other

Linked PRs

• GH-125174: Make immortal objects more robust, following design from PEP 683 #125251
• GH-125174: Mark objects as statically allocated. #127797
• GH-125174: Fix compiler warning #127860
• GH-125174: Don't use UINT32_MAX in header file #127863
• GH-125174: Make immortality "sticky" #131184
• GH-125174 Revert: Make immortality "sticky" (GH-131184)" #131230
• GH-125174: Make immortality "sticky" #131355

[markshannon]

There is a fairly simple thing we can do to make immortal refcounts more robust: Start them in the middle of the region of immortality.

We want a fast check for immortality, so we use a sign check: refcnt < 0.
This means the top bit must be 1. By setting the top two bits to 11 and the remaining bits to zero, the refcount can be off by up to 2**30 and the immortality check still works.
As a refinement, we can offset the starting value to zero a bit, and have meaningful underflow checks in debugging mode:
Initial refcount for immortal objects: 0b1011000000000...

Top 3 bits	Meaning
111	Underflow
110	Immortal
101	Immortal
100	Immortal
011	Mortal
010	Mortal
001	Mortal
000	Mortal

[markshannon]

It might we worth correcting the refcount of immortal objects occasionally. This could be done during GC. When an immortal object is encountered, rewrite its refcount to the starting value if necessary.

[encukou]

There is a fairly simple thing we can do to make immortal refcounts more robust: Start them in the middle of the region of immortality.

That's essentially what PEP-683 originally specified.

[ericsnowcurrently]

CC @eduardo-elizondo

[markshannon]

Can we add a couple of tests for stable ABI decrefs and increfs that change the refcount of an immortal object by a few million to check that everything still works OK.

[ericsnowcurrently]

I agree with pretty much everything here.

[ericsnowcurrently]

There's also the question of immortal heap objects, AKA "interpreter-immortal". They must not outlive the allocator under which they were created. Each isolated interpreter has its own allocator, so immortalized heap objects there must not outlive the interpreter. We ran into some recent crashes related to this.

Currently the only immortal heap objects I know about are the interned strings (incidentally, the origin of the crashes). To deal with that, we've switched legacy interpreters to share the main interpreter's interned strings dict. For isolated interpreters we still need to fix this, probably by returning a new immortal object created using the main interpreter (thus bound to the global runtime's lifetime).

One of the following must be done to make interpreter-immortal (heap) objects generally safe:

• never allow "external references" (references to the immortal objects outside the originating interpreter)
• never allow external references, except for in interpreters that share the originating allocator (legacy interpreters share the main allocator); this requires that the allocator be finalized with the last interpreter (or runtime)
• block finalizing the originating interpreter until all external references have been released

Alternately, we could require that all immortal heap objects be runtime-global, thus disallowing interpreter-bound immortality. This would either mean we have all interpreters share a single global allocator, or we have a separate global allocator just for immortal heap objects, which would require a separate API.

FWIW, I like the idea of heap object allocation and immortalization being strongly coupled. Being able to mark a heap object as immortal after-the-fact is prone to problems.

Regardless, we need to be very careful that immortal objects only be fully immutable, for the sake of cross-interpreter safety, among other reasons. I suppose mutable immortal objects would be fine for internal global (cross-interpreter) cases for objects that are strictly not exposed to users, where we can use locks for safety. Otherwise, any mutable immortal object would have to be bound the originating interpreter's lifetime, and we're back to interpreter-immortal. For now we should just avoid mutable immortal objects.

[encukou]

I like the idea of heap object allocation and immortalization being strongly coupled.

And it should probably also be strongly coupled with deduplication (interning) -- like with strings, you don't want to immortalize a tuple if another equal tuple is already immortal.

[markshannon]

There's also the question of immortal heap objects...

What is the question, exactly?

Being able to mark a heap object as immortal after-the-fact is prone to problems.

Why? It seems a perfectly reasonable thing to do. In fact, it is one of the motivations for PEP 683.

One of the following must be done to make interpreter-immortal (heap) objects generally safe:

OOI, why aren't they safe now? Wasn't that part of PEP 683?

never allow "external references" (references to the immortal objects outside the originating interpreter)

Yes. This is the obviously correct, and probably only correct answer.
Static objects (object belonging to the process, not an individual interpreter) can still be shared.

never allow external references, except for in interpreters that share the originating allocator (legacy interpreters share the main allocator); this requires that the allocator be finalized with the last interpreter (or runtime)

This sounds complicated and error prone

block finalizing the originating interpreter until all external references have been released

This also sounds complicated and expensive to track the references.

[markshannon]

With the margin of error of about 1 billion, things are about as robust as we can make them for now.

Immortal objects aren't going to be truly immortal until all C extensions have been recompiled against a recent version of the headers. But there is nothing we can do about that except wait.

[markshannon]

I'm reopening this issue because of immortality through overflow.
Consider this scenario:
Code A is aware of immortality
Code B uses the stable ABI and is not aware of immortality

There exists an object, O, with a refcnt of 1.
B increases the refcnt by N, where N is large enough so the the refcount of O is one away from immortality.
A then increases the refcount thrice, leaving it immortal and only incrementing the refcount once.
B then decreases the refcnt by N leaving it with a reference of 2
A then decreases the refcount thrice, leaving it with a refcnt of -1 and a double-free crash.

The problem is the lack of "stickiness" of immortality in this scenario.

The fix would be to make the threshold of immortality higher for increfs than the decrefs.
The challenge is doing that efficiently*

@ericsnowcurrently
@eduardo-elizondo

Note that this is only an issue for 64 bit builds. It is impossible for N above to be large enough to cause a problem on 32 bit builds.

---

* One approach might to use use 0 to represent immortality for increfs and > INT_MAX for decrefs (with 32 bit unsigned refcounts).
This might need a bit of extra code in Py_Dealloc to check for immortal objects due to overflow.

[mdboom]

B increases the refcnt by N, where N is large enough so the the refcount of O is one away from immortality.

How practically possible is this, though? That's ~17GB of pointers to reference this one object, which of course is possible, but my Linux box still throws an OOM if I request to allocate that much memory in a single block.

[markshannon]

How practically possible is this, though?

Its' not very likely at all, but it is possible. The test in #131184 takes ~20GB, but it will crash the interpreter.

[markshannon]

While it is still theoretically possible to crash the interpreter, it is now practically impossible to so accidentally.

FTR, here's how it's done:

• Create over a billion (strictly 1 << 30) stack references a newly created object
  • This can be done by, for example, calling a function that has 1100 local variables to the new object in over 1000 threads to the full recursion limit of 1000 and waiting at that point.
• Once there are over 1 << 30 stack references to the object, create over 2 billion (1 << 31) heap references to the object which will cause the object to be made immortal and drop some refcount increments.
  • E.g. l = [ obj ] * ((1 << 31) + 10)
• Free all the stack reference, by e.g. resuming the threads and waiting for them to complete. This will make the object mortal again with a lower refcount than the number of heap references
• Free the heap references, which will make the refcount of the object go negative, crashing the interpreter.