Background
We (SAP) need some parts of LLVM to be robust against memory leaks in case of out of memory situations. This is because we work in the context of an in-memory database, where each crash of the process can potentially lead to data loss. Therefore, we invested and continuously invest into making LLVM core data structures more robust against OOM situations. Amongst other things, we hardened DenseMap and DenseSet, which this RFC is about.
Overview
To achieve malfunction-safety, we need to keep track of the construction/destruction state of key/value. This is necessary to ensure, that the keys/values are always destructed correctly in any scenario (exceptional and unexceptional) if they were constructed beforehand. Previously, this was not guaranteed. Furthermore, we found some unfavorable combinations in the order of instructions, that led to memory leaks in case of bad_allocs being thrown.
As especially DenseMap is a very central data structure within LLVM, it is important to keep an eye on memory consumption / performance along the way.
The outside behaviour of Dense[Map|Set], especially the API, is not changed by the improvements.
Implementation
The tracking part is done by extending Dense[Map|Set]Pair with two bools. We realized this, by essentially offering two variants of Dense[Map|Set]Pair. One for the trivially_destructible case, where we don’t need the booleans and one for the non trivially_destructible, where we need the tracking.
In case of DenseMap:
// OOM safe DenseMap bucket
// flags to indicate if key and value are constructed
// this is necessary since assigning empty key or tombstone key throws for some key types
template<typename KeyT, typename ValueT, typename Enable = void>
struct DenseMapPairImpl;
template <typename KeyT, typename ValueT>
using EnableIfTriviallyDestructibleMap = typename std::enable_if_t<std::is_trivially_destructible_v<KeyT> && std::is_trivially_destructible_v<ValueT>>;
template <typename KeyT, typename ValueT>
using EnableIfNotTriviallyDestructibleMap = typename std::enable_if_t<!std::is_trivially_destructible_v<KeyT> || !std::is_trivially_destructible_v<ValueT>>;
template <typename KeyT, typename ValueT>
struct DenseMapPairImpl<KeyT, ValueT, EnableIfTriviallyDestructibleMap<KeyT, ValueT>> : public DenseMapPair<KeyT, ValueT> {
LLVM_ATTRIBUTE_ALWAYS_INLINE void setKeyConstructed(bool) {}
LLVM_ATTRIBUTE_ALWAYS_INLINE bool isKeyConstructed() const { return false; }
LLVM_ATTRIBUTE_ALWAYS_INLINE void setValueConstructed(bool) {}
LLVM_ATTRIBUTE_ALWAYS_INLINE bool isValueConstructed() const { return false; }
};
template <typename KeyT, typename ValueT>
struct DenseMapPairImpl<KeyT, ValueT, EnableIfNotTriviallyDestructibleMap<KeyT, ValueT>> : DenseMapPair<KeyT, ValueT> {
private:
bool m_keyConstructed;
bool m_valueConstructed;
public:
LLVM_ATTRIBUTE_ALWAYS_INLINE void setKeyConstructed(bool constructed) { m_keyConstructed = constructed; }
LLVM_ATTRIBUTE_ALWAYS_INLINE bool isKeyConstructed() const { return m_keyConstructed; }
LLVM_ATTRIBUTE_ALWAYS_INLINE void setValueConstructed(bool constructed) { m_valueConstructed = constructed; }
LLVM_ATTRIBUTE_ALWAYS_INLINE bool isValueConstructed() const { return m_valueConstructed; }
};
These two booleans will cause an increase in size of each non trivially_destructible Dense[Map|Set]Pair. We haven’t measured the impact using the LLVM internal benchmarks yet, but our battle-tested/benchmarked compiler did not show any dramatic increases in memory size or performance.
Testing
We have created unit tests that test correct behavior of all operations on Dense[Map|Set] using our own malfunction framework. We are willing to upstream a minimal version of the framework, in order to robustly test our improvements from a malfunction standpoint. Due to the fact, that our patches have no functional impact, the existing functional tests should be sufficient.
Conclusion
Feel free to comment on this thread, since we wanted to inquire about the general interest in this regard before trying to upstream our patches. Do you have improvement suggestions or objections?
Thanks in advance,
Marc