Figure out how to support large allocations

[tCm3nc]

By large allocations I mean greater than 2^16 byte allocations. When performing pointer arithmetic, the mechanism to check if the access is valid is currently performed like so:

QEMU_pointer_arithmetic_helper(tagged_ptr, addend):

• untagged_ptr = translate_ptr(tagged_ptr,..);
• check shadow memory (untagged_ptr + addend);
• If valid, return untagged_ptr + addend. (When load/stores happen, we will lose track of this pointer because it is not a tagged pointer!)
• If not valid, return tagged_ptr + addend. Resulting in a crash on invalid memory access.

This can be improved though.

For a large allocation, split it into 2^16 blocks. For each 2^16 block, we allocate different tags.

The above helper changes to:

• untagged_ptr = translate_ptr(tagged_ptr,...)
• untagged_ptr + addend
• Check allocation interval tree for valid allocation. If valid:
  • tag = shadow_memory[untagged_ptr + addend]
  • return tag | lower 16 bits of untagged_ptr
  • if invalid: bail.

[tCm3nc]

The first trance of this is complete. I need further to add the interval tree code in order to be able to determine whether a particular pointer addition is within range or not. There will likely be clashes with cryptography code where an opaque value, would clash with a valid tagged pointer and its associated shadow memory. Not sure what to do in this scenario though.