]> git.ipfire.org Git - thirdparty/bind9.git/commit
Adaptive memory allocation strategy for qp-tries
authoralessio <alessio@isc.org>
Sun, 9 Mar 2025 08:13:16 +0000 (09:13 +0100)
committerEvan Hunt <each@isc.org>
Thu, 22 May 2025 22:19:27 +0000 (15:19 -0700)
commit70b1777d8aef75da1b184fe8155dc818ce66628a
treed352132fb65672f7dafbf45fdbc6cb9e188a1fdb
parent13d0bab7c21c5028580bbdd7a32d51a3f10d8895
Adaptive memory allocation strategy for qp-tries

qp-tries allocate their nodes (twigs) in chunks to reduce allocator
pressure and improve memory locality. The choice of chunk size presents
a tradeoff: larger chunks benefit qp-tries with many values (as seen
in large zones and resolvers) but waste memory in smaller use cases.

Previously, our fixed chunk size of 2^10 twigs meant that even an
empty qp-trie would consume 12KB of memory, while reducing this size
would negatively impact resolver performance.

This commit implements an adaptive chunking strategy that:
 - Tracks the size of the most recently allocated chunk.
 - Doubles the chunk size for each new allocation until reaching a
   predefined maximum.

This approach effectively balances memory efficiency for small tries
while maintaining the performance benefits of larger chunk sizes for
bigger data structures.

This commit also splits the callback freeing qpmultis into two
phases, one that frees the underlying qptree, and one that reclaims
the qpmulti memory. In order to prevent races between the qpmulti
destructor and chunk garbage collection jobs, the second phase is
protected by reference counting.
lib/dns/include/dns/qp.h
lib/dns/qp.c
lib/dns/qp_p.h
lib/dns/qpcache.c
lib/isc/include/isc/util.h
lib/isc/mem.c