limit check bug

Stephen Weeks MLton@sourcelight.com
Tue, 12 Feb 2002 16:49:16 -0800


There is a serious bug in how we decide whether or not a limit check
succeeds.  Here is the test that we use.

	frontier + bytesAllocated > limit

The problem is that the addition can overflow!  We almost never see
this because for object allocation bytesAllocated is zero (because of
LIMIT_SLOP) or very small.  But for array allocation, especially with
unrestricted array lengths, bytesAllocated can be quite large (even 4G).
We can even get screwed with small allocations if the heap happens to
be near the top of the address space and the frontier is close to the
limit.

This could even explain the bug tha Henry was seeing with large
arrays.

Unfortunately, we can't just change the test to

	bytesAllocated > limit - frontier

because frontier may be greater than limit (by up to LIMIT_SLOP).

The only solution that I see is to have two kinds of limit checks:
cheap ones where we know that the add won't overflow like we're used
to:

	frontier + bytesAllocated > limit

and more expensive ones that use the other form if necessary

	(frontier > limit
		or bytesAllocated > limit - frontier)

For simplicity for right now, I propose to make the cheap ones be
where bytesAllocated = 0.  If we find this gives performance problems,
then we can increase LIMIT_SLOP or play other games to make sure that
the heap is sufficiently below the top of the address space that we
know it won't overflow (maybe we already know something like this
already due to Linux vm layout?)

Any thoughts?