Item — HN Reader

One cool technique is to use the packed bits to check if a raw pointer is still valid.

Say you have a pool of objects, when you allocate one you give out a pointer, but in the packed bits you add a 'generation' counter. Every time you free that object from the pool you increment the counter. When you dereference a pointer you can check the generation in the packed pointer and the one in the pool. If they don't match you're using a pointer to an invalid object.

2 comments

It's a cool technique, but only useful in very limited scenarios. In particular, it is unsuitable when the number of reallocations is unbounded, because the generation counter can easily overflow.

Even if you can squeeze in 32 tag bits (you would need to leverage the virtual memory system in some platform-specific way), counting to 4-billion-and-change takes no time on modern CPUs, so you would realistically overflow the tag in milliseconds.

But if your system is aware of virtual memory, you can still do interesting things, like remapping a whole arena with a different "tag" and use the information in GC write barriers.

ah for sure, the context will matter but I'd say that if you're generating and destroying 4 billion objects very fast then probably storing pointers to those objects is already a bad idea!

It's mostly a question of whether a user can accidentally or maliciously cause 4 billion objects to be constructed in the same location. Maybe it happens accidentally after the system has been running for a year, and everything comes tumbling down.

A similar technique is sometimes used to mitigate the ABA problem in lock-free data structures.

Only using way more bits. The original IBM lock-free stack algorithm assumed 32 bits was safe because it would take 100 years for a 32 bit counter to wrap at the time. Now it's less than 1 second.

There's some Bugblatter Beast logic here. They assume that if they can't imagine a counter/pointer value reuse ever reoccurring then malicious actors won't be able to imagine it either.

Here's an idea. How about fixing the buffer overflows and lack of data sanitation that allow code injection to occur in the first place.