Graceful Recovery From malloc Failure
S. Gilles
2017-08-04
Background
An argu^Wpolite discussion I've seen play out a few times so far
goes like this:
A: I have created a new library/operating system/programming
language for you to use. Please enjoy.
B: I have a bug report: the memory allocations are not checked
for failure. Very bad things will happen on line N + k if
the memory allocation on line N failed.
A: Thank you for the report - I've made a fix.
B: Your fix is to call abort(3) if malloc(3) ever fails. This
is better, but could you instead clean up the heap and
report failure to the user?
A: That would be really hard, and what are you going to do
besides abort() anyway?
In my experience, by this point in the conversation negotiations
have broken down a little, and no progress is made.
Here's a perfect example of what could be done besides abort():
Background (topology)
For my research, I'm interested in generalizing (very slightly)
Thurston's Gluing Equations: for any hyperbolic 3-manifold M, if
you are interested in listing all possible “nice” maps
f : { loops in M } → { Some Lie group G }
it turns out that it suffices to cut M up into a (finite) number
of tetrahedra, and then associate to each tetrahedron a (finite)
set of (non-zero) complex numbers: the A-coordinates. Performing
some mechanical computations, you get a second (finite) set of
(non-zero) complex numbers: the X-coordinates.
Not only that, but the {A,X}-coordinates are associated to
particular geometric locations on those tetrahedra, and that f(γ)
can be calculated by (roughly) multiplying together the X-coordinates
that lie along the loop γ.
For the manifold M = S₃ \ 4₁ (the complement of the figure-eight
knot, which has a hyperbolic structure), for example, it turns
out that there are only 2 tetrahedra, and to consider maps into
SO(5,ℝ) requires with 23 X-coordinates for each tetrahedron
(according to one convention, if I've counted correctly). So if
you know 46 (non-zero) complex numbers, you can compute f.
It turns out 46 numbers are too many. Some are always in pairs
of (x, 1/x), some may not be used in recovering f, etc. The
question then arises “What are the exact set of restrictions we
need to put on thes 46 numbers to guarantee that they correspond
to some f?”.
My research is to (using specific “quivers” developed recently,
independently, by Zickert and Le) try and answer this question
when G is a Lie group of type Bₙ, Cₙ or (hopefully) Gₙ. My approach
is not very clever, but it will give context to the situation in
which I care about memory errors.
I fix a canonical set of A-coordinates as a basis/super-basis,
then force the assumption that the A-coordinates belong to a
triangulation (these equations aren't difficult). Then I represent
all X-coordinates as rational polynomials in terms of that basis.
Next, I evaluate those polynomials for some pseudorandom assignments
of complex numbers to A-coordinates. This allows me to make some
guesses about which products of X-coordinates will be 1. When I
symbolically confirm a guess, I obtain a restriction on the
X-coordinates, which must be satisfied for an X-coordinate
assignment to correspond to a triangulation
Once I have enough necessary restrictions, I'll test whether they
are sufficient through other means, so for now the important thing
is to multiply as many different polynomials together and list
all ways to get 1.
The code in question:
X := { the rational polynomials representing the X-coordinates }
C := make_guesses_via_numerical_approximation(X)
for c in C, (c is a list with length n) {
if (Prod over i=1,2,…n of X[c[i]] is 1) { (*)
output({ X[c[i]] : i=1,2,…n })
}
}
Line (*) is performed using the PARI library[0]. Regardless of
whatever optimizations are applied to obtain C, some products
must be computed to check if some variables cancel. For reference,
one of the worse elements of X, in one computation, is
x'_{1'} = ((a'₁·a'₀₃·a'₃₂·a'₂₃²·a₁³·a₀₃·a₂₃²·a₀² + ((a'₁³·a'₃₂²·a₁³
+ a'₂·a'₁³·a'₃₂·a₂·a₁)·a₀₃·a₂₃² + (a'₁·a'₀₃·a'₃₂·a'₂₃²·a₁⁵ +
a'₂·a'₁·a'₀₃·a'₂₃²·a₂·a₁³)·a₃₂)·a₀ + (a'₁³·a'₃₂²·a₁⁵ +
2·a'₂·a'₁³·a'₃₂·a₂·a₁³ + a'₂²·a'₁³·a₂²·a₁)·a₃₂)·aₛ² +
(((a'₂·a'₁³·a'₃₂·a₁·a₀₃·a₃₀ + a'₂·a'₁²·a'₃₀·a'₃₂·a₁²·a₀₃)·a₂₃³
+ (a'₂·a'₁²·a'₃₂·a'₂₃·a₁²·a₀₃·a₃₀ +
a'₂·a'₁·a'₃₀·a'₃₂·a'₂₃·a₁³·a₀₃)·a₂₃²)·a₀² + (((a'₂·a'₁³·a'₃₂·a₁³
+ a'₂²·a'₁³·a₂·a₁)·a₃₀ + (a'₂·a'₁²·a'₃₀·a'₃₂·a₁⁴ +
a'₂²·a'₁²·a'₃₀·a₂·a₁²))·a₃₂·a₂₃ + ((a'₂·a'₁²·a'₃₂·a'₂₃·a₁⁴ +
a'₂²·a'₁²·a'₂₃·a₂·a₁²)·a₃₀ + (a'₂·a'₁·a'₃₀·a'₃₂·a'₂₃·a₁⁵ +
a'₂²·a'₁·a'₃₀·a'₂₃·a₂·a₁³))·a₃₂)·a₀)·aₛ)/((a'₀₃²·a'₂₃³·a₁²·a₀₃·a₂₃³·a₀³
+ (a'₁²·a'₀₃·a'₃₂·a'₂₃·a₁²·a₀₃·a₂₃³ +
2·a'₂·a'₁·a'₀₃·a'₂₃²·a₂·a₁·a₀₃·a₂₃² + a'₀₃²·a'₂₃³·a₁⁴·a₃₂·a₂₃)·a₀²
+ ((a'₁²·a'₀₃·a'₃₂·a'₂₃·a₁⁴ + a'₂·a'₁²·a'₀₃·a'₂₃·a₂·a₁²)·a₃₂
+ (a'₂·a'₁²·a'₃₂·a'₂₃·a₂·a₁² + a'₂²·a'₁²·a'₂₃·a₂²)·a₀₃)·a₂₃·a₀)·aₛ²
+ ((2·a'₂·a'₁·a'₀₃·a'₂₃²·a₁·a₀₃·a₃₀ +
2·a'₂·a'₀₃·a'₃₀·a'₂₃²·a₁²·a₀₃)·a₂₃³·a₀³ +
((2·a'₂²·a'₁²·a'₂₃·a₂·a₀₃·a₃₀ + 2·a'₂²·a'₁·a'₃₀·a'₂₃·a₂·a₁·a₀₃)·a₂₃²
+ (2·a'₂·a'₁·a'₀₃·a'₂₃²·a₁³·a₃₀ +
2·a'₂·a'₀₃·a'₃₀·a'₂₃²·a₁⁴)·a₃₂·a₂₃)·a₀²)·aₛ +
((a'₂²·a'₁²·a'₂₃·a₀₃·a₃₀² + 2·a'₂²·a'₁·a'₃₀·a'₂₃·a₁·a₀₃·a₃₀
+ a'₂²·a'₃₀²·a'₂₃·a₁²·a₀₃)·a₂₃³·a₀³ + (a'₂²·a'₁²·a'₂₃·a₁²·a₃₀²
+ 2·a'₂²·a'₁·a'₃₀·a'₂₃·a₁³·a₃₀ + a'₂²·a'₃₀²·a'₂₃·a₁⁴)·a₃₂·a₂₃·a₀²))
This takes, I estimate, somewhere on the order of 10KiB for PARI
to store in a way that can be used efficiently.
If a few elements of that complexity are multiplied together, and
the product doesn't cancel to 1, it's entirely possible that
PARI's internal representation of that result will take more than
4GiB of memory (which appears to be the maximum size I can make
PARI's stack).
Unluckily, PARI's stack-based operations kill the program on
failure. In my particular situation, overflowing PARI's stack is
something I could recover from: I'd just output a warning that
that particular product needs to be checked by hand.
This is the prime sort of example that I think B should be giving:
programs performing memory-intensive operations, some of which
are optional. I am content with a small number of warnings on
stderr regarding products which are difficult to compute. I am
not content with a 12 hour computation aborting 7 hours in.
Fixes
In my particular case, there are fixes. PARI primarily works off
its own, internal stack, but objects can be moved to main memory
if needed. This removes the 4GiB limit.
More importantly, however, PARI exposes the top, bottom, and
current position of its internal stack. This allows me to monitor
memory usage in (*), and cleanly skip the computation if too much
of the stack memory starts being used.
It also turns out that checking for continual memory growth is
an excellent heuristic that a computation is probably not going
to cancel to 1. If
o all factors have roughly the same initial size,
o “unlucky” multiplications increase memory usage exponentially,
and
o such growth has been observed when multiplying ceil(half)
factors,
it's very improbable that the last few factors have enough
complexity to cancel the intermediate product, so we can abandon
the computation, skipping the last (and probably the most intensive)
steps. This also allows me to use low 10s of MiB, not GiB, for
PARI's stack.
[0] http://pari.math.u-bordeaux.fr
