Well, without hardware support, you need either a huge overhead ([cached] binary search for a bounding allocation for a pointer every time you use it) or a mode

Well, without hardware support, you need either a huge overhead ([cached] binary search for a bounding allocation for a pointer every time you use it) or a moderate overhead with fat pointers. It can be done purely in software, but it's not efficient.