Page MenuHomePhabricator

Don't use a random probe / allocation scheme in the IRMemoryMap

Authored by zturner on Jun 25 2014, 4:15 PM.



The current strategy for host allocation is to choose a random address and attempt to allocate there, eventually failing if the allocation cannot be satisfied.

The C standard only guarantees that RAND_MAX >= 32767, so for platforms where this is true allocations will fail with very high probability. On such platforms, you can reproduce this trivially by running lldb, typing "expr (3)" and then hitting enter you see a failure. Failures generally happen with a frequency of about 1 failure every 5 evaluations.

I cannot come up with a good reason that the allocations need to look like "real" pointers, so this patch changes the allocation scheme to simply jump straight to the end and grab a free chunk of memory.

Diff Detail


Event Timeline

zturner updated this revision to Diff 10860.Jun 25 2014, 4:15 PM
zturner retitled this revision from to Don't use a random probe / allocation scheme in the IRMemoryMap.
zturner updated this object.
zturner edited the test plan for this revision. (Show Details)
zturner added a subscriber: Unknown Object (MLST).
emaste added a subscriber: emaste.Jun 26 2014, 8:00 PM
tfiala added a subscriber: tfiala.Jul 1 2014, 12:06 PM

Looking at this now.

Added a couple questions. Going to try the patch as is in a moment here.

76 ↗(On Diff #10860)

This now shadows the size argument to the function. Maybe rename it to something like allocation_size.

I think you also want to check if size (the argument to the function) + ret would bust the address space (i.e. validate that the requested size can really fit within the address space if it comes where the method suggests).

Are we guaranteed that these allocations are contiguous? If they're not contiguous, and if we do not have enough space at the end of the allocations, then that opens up a reason to look for holes earlier in the address space.

zturner added inline comments.Jul 1 2014, 12:38 PM
76 ↗(On Diff #10860)

They should be contiguous. After all, this is an interval map where each item in the tree can be reduced to the pair (start, size), and by extension represents the interval [start, start+size). So by simply pulling the last entry off the map and rounding up to the required alignment, it should be guaranteed that the entry returns is at the next possible location that a value can be allocated at with the given alignment requirement.

Does anything ever get removed from it? If so, you've got holes.

Yes, but I believe that the scope of this memory map is the execution of a single expression. So unless a single expression tries to allocate more than the entire address space across some number of allocations, it will always be fine.

tfiala added a comment.Jul 1 2014, 1:07 PM

I don't see any new test failures with this. The (lldb) expr command seems to be working fine in a remote inferior process.

The only change I'd like to see if the renaming the shadowed variable to a different name.

I have an open question on the lifetime of an IRMemoryMap and whether we care about holes that develop, and whether we want new allocations to always come at the end of the range if this persists. However, if it is relatively short lived, this probably isn't a big deal.

Bump for the new week. Hopefully can get some traction this week.

zturner closed this revision.Jul 9 2014, 9:51 AM
zturner updated this revision to Diff 11206.

Closed by commit rL212630 (authored by @zturner).