Buddy allocation for large buffers in adaptive allocator by chrisvest · Pull Request #16053 · netty/netty

chrisvest · 2025-12-16T18:43:06Z

Motivation:

The histogram bump allocating chunks have poor chunk and memory reuse in practice, which leads to higher memory usage than the pooled allocator whenever an application performs enough allocations of buffers that don't fit in our size-classed chunks.

Buddy allocation should in theory reduce memory consumption by allowing memory reuse within a chunk, similar to the size-classed chunks, but for variable power-of-two sized allocations.

We've found that beyond 16k-20k buffer sizes, allocations predominantly comes in power-of-two sizes, hence buddy allocation should be a good fit for this size regime.

Modification:

Implement a new chunk type that does buddy allocation, based on an array-embedded binary search tree.
The tree is encoded as a dense byte array, with two bits marking node or child-node usage, and six bits to encode the node size.
The histogram pointer-bump allocating chunk implementation is removed, which unlocks potential simplifications and optimizations that will benefit both buddy and size-classed chunks.
The 32k and 64k size classes are kept for the time being, to keep chunk churn under control, but they are planned to be removed in a follow-up PR.

Result:

We generally get improvements to memory usage, because the buddy allocator is able to reuse its chunks before they are fully deallocated.
If the 32k and 64k size-classes are removed, then the improvements continue to hold up, but we see an increase in allocation churn for buddy chunks.
This needs to be investigated and solved before we can remove the 32k and 64k size-classes.
Presumably, it comes down to making better decisions about the size of the buddy chunks, and in picking which chunks to allocate from next once a magazine has exhausted its current chunk.

…ffers

…t side of any subtree

This is temporary. We should do something faster than this.

Releasing could end up iterating past its sibling pair, so where releasing a node could end up updating a parent path that wasn't a parent of the released node.

When releasing parent nodes we were only considering the siblings one level down, not whether any other child of a given node had been claimed. This could lead to grand-parents getting marked as free, if we returned from a child that had a free sibling. Now we return whether the given subtree is free and only consider the sibling if so.

They were used for debugging and are no longer needed.

chrisvest · 2025-12-19T23:48:54Z

With the fixes to the freeing code, the buddy allocator is now both faster and use less memory (no longer accidentally keeping memory marked as claimed). However, it's not nearly enough to make up for the removal of the 32k and 64k size classes.
Especially in cases where there's high buffer retention - many buffers alive at the same time. In that case, we end up with many chunks and make poor decisions reusing them because we just a queue per magazine group.

FYI @franz1981

chrisvest · 2025-12-19T23:53:20Z

Here's a simulation run with the e-commerce data:

If I comment out the largeBufferMagazineGroup path, so large buffers are unpooled instead of using the buddy allocator for pooling, then memory usage is cut in half, which gives us a picture of how far away from the limit we are.

I think it might be better to look at that problem in a separate follow-up PR. Don't want each PR to get too big.

chrisvest · 2026-01-06T00:27:27Z

@franz1981 I think it'd be better to do chunk picking in a separate PR, so I brought back the 32k and 64k size classes. Those bring the memory usage back to previous levels. I marked this PR ready for review.

# Conflicts: # buffer/src/main/java/io/netty/buffer/AdaptivePoolingAllocator.java

franz1981

I will be soon back after holiday and look at this 🙏

normanmaurer

Generally looking good to me... just a a few nits and a question

normanmaurer · 2026-01-09T14:51:01Z

+        @Override
+        public int remainingCapacity() {
+            if (!freeList.isEmpty()) {
+                freeList.drain(256, this);


Also it feels kind of odd that a "getter" would have such a "side-effect".

Perhaps, but the alternative is to iterate and sum the sizes of pending frees. It'd require adding some reduce-on-range method to the MpscIntQueue, which is of course possible.

The whole remainingCapacity business is a hold-over from bump allocation, so it's something we should move away from entirely, and instead rely on readInitInto returning a boolean.

Fixing this up is something I want to do in a future PR, perhaps as part of improving chunk picking.

normanmaurer · 2026-01-09T14:56:34Z

            } else {
                RefCnt.resetRefCnt(refCnt);
                delegate.setIndex(0, 0);
-                allocatedBytes = 0;


Is this correct ?

Yes, because updates to this field may be delayed, e.g. by the BuddyChunk freeList. So we can't reset it in case there's relative updates pending. Instead we need to let the concrete Chunk implementations manage it.

Just like SizeClassedChunks, the BuddyChunks can be released directly back to the shared pool in the magazine group, without waiting for the chunk to be fully freed. This allows it to be reused much sooner, and reduces memory usage. This is technically enough to remove the 32k and 64k size classes. However, if we do that, then it would currently cause an increase in chunk churn, where chunks are allocated and released a lot. The churn needs to come under control, before those two size classes can be removed.

chrisvest · 2026-01-10T01:10:39Z

@franz1981 @normanmaurer Added one more commit where I fixed a missing piece that was causing the increased memory usage seen in #16053 (comment)

Like the SizeClassedChunks, the BuddyChunks can of course be reused before all their buffers have been freed.

This means it's now technically possible to remove the 32k and 64k. However, doing so introduces a fair bit of chunk churn, as can be seen in this chart:

Getting the churn under control, and making smarter picking decisions, is what I'll work on next in a separate PR.

normanmaurer · 2026-01-12T22:34:25Z

@chrisvest don't we also want to cherry-pick to 4.1 ?

chrisvest · 2026-01-12T22:35:49Z

Yeah, I'll add it.

Motivation: The histogram bump allocating chunks have poor chunk and memory reuse in practice, which leads to higher memory usage than the pooled allocator whenever an application performs enough allocations of buffers that don't fit in our size-classed chunks. Buddy allocation should in theory reduce memory consumption by allowing memory reuse within a chunk, similar to the size-classed chunks, but for variable power-of-two sized allocations. We've found that beyond 16k-20k buffer sizes, allocations predominantly comes in power-of-two sizes, hence buddy allocation should be a good fit for this size regime. Modification: * Implement a new chunk type that does buddy allocation, based on an array-embedded binary search tree. * The tree is encoded as a dense byte array, with two bits marking node or child-node usage, and six bits to encode the node size. * The histogram pointer-bump allocating chunk implementation is removed, which unlocks potential simplifications and optimizations that will benefit both buddy and size-classed chunks. * The 32k and 64k size classes are kept for the time being, to keep chunk churn under control, but they are planned to be removed in a follow-up PR. Result: We generally get improvements to memory usage, because the buddy allocator is able to reuse its chunks before they are fully deallocated. If the 32k and 64k size-classes are removed, then the improvements continue to hold up, but we see an increase in allocation churn for buddy chunks. This needs to be investigated and solved before we can remove the 32k and 64k size-classes. Presumably, it comes down to making better decisions about the size of the buddy chunks, and in picking which chunks to allocate from next once a magazine has exhausted its current chunk. (cherry picked from commit 2dbc1e7)

…6133) Motivation: The histogram bump allocating chunks have poor chunk and memory reuse in practice, which leads to higher memory usage than the pooled allocator whenever an application performs enough allocations of buffers that don't fit in our size-classed chunks. Buddy allocation should in theory reduce memory consumption by allowing memory reuse within a chunk, similar to the size-classed chunks, but for variable power-of-two sized allocations. We've found that beyond 16k-20k buffer sizes, allocations predominantly comes in power-of-two sizes, hence buddy allocation should be a good fit for this size regime. Modification: * Implement a new chunk type that does buddy allocation, based on an array-embedded binary search tree. * The tree is encoded as a dense byte array, with two bits marking node or child-node usage, and six bits to encode the node size. * The histogram pointer-bump allocating chunk implementation is removed, which unlocks potential simplifications and optimizations that will benefit both buddy and size-classed chunks. * The 32k and 64k size classes are kept for the time being, to keep chunk churn under control, but they are planned to be removed in a follow-up PR. Result: We generally get improvements to memory usage, because the buddy allocator is able to reuse its chunks before they are fully deallocated. If the 32k and 64k size-classes are removed, then the improvements continue to hold up, but we see an increase in allocation churn for buddy chunks. This needs to be investigated and solved before we can remove the 32k and 64k size-classes. Presumably, it comes down to making better decisions about the size of the buddy chunks, and in picking which chunks to allocate from next once a magazine has exhausted its current chunk. (cherry picked from commit 2dbc1e7)

…6132) Motivation: The histogram bump allocating chunks have poor chunk and memory reuse in practice, which leads to higher memory usage than the pooled allocator whenever an application performs enough allocations of buffers that don't fit in our size-classed chunks. Buddy allocation should in theory reduce memory consumption by allowing memory reuse within a chunk, similar to the size-classed chunks, but for variable power-of-two sized allocations. We've found that beyond 16k-20k buffer sizes, allocations predominantly comes in power-of-two sizes, hence buddy allocation should be a good fit for this size regime. Modification: * Implement a new chunk type that does buddy allocation, based on an array-embedded binary search tree. * The tree is encoded as a dense byte array, with two bits marking node or child-node usage, and six bits to encode the node size. * The histogram pointer-bump allocating chunk implementation is removed, which unlocks potential simplifications and optimizations that will benefit both buddy and size-classed chunks. * The 32k and 64k size classes are kept for the time being, to keep chunk churn under control, but they are planned to be removed in a follow-up PR. Result: We generally get improvements to memory usage, because the buddy allocator is able to reuse its chunks before they are fully deallocated. If the 32k and 64k size-classes are removed, then the improvements continue to hold up, but we see an increase in allocation churn for buddy chunks. This needs to be investigated and solved before we can remove the 32k and 64k size-classes. Presumably, it comes down to making better decisions about the size of the buddy chunks, and in picking which chunks to allocate from next once a magazine has exhausted its current chunk. (cherry picked from commit 2dbc1e7)

chrisvest added 9 commits December 16, 2025 08:54

First draft of implementing buddy allocation in adaptive for large bu…

98a9a8e

…ffers

Remove the histogram-based bump allocating chunk implementation

e8baf79

Fix a bug in buddy allocation computing incorrect offset for the righ…

a5313e3

…t side of any subtree

Fix a couple of bugs in the buddy allocation

abba848

More accurate remaining capacity for buddy allocation

1651cea

This is temporary. We should do something faster than this.

Add a data consistency test targeting the buddy allocator

155b9fe

Fix a problem in the buddy allocator

3e3d1e3

Releasing could end up iterating past its sibling pair, so where releasing a node could end up updating a parent path that wasn't a parent of the released node.

Remove the Graphviz DOT generating functions

3487b55

They were used for debugging and are no longer needed.

chrisvest added 3 commits December 21, 2025 19:12

Merge branch '4.2' into 4.2-buddy-alloc

8ab221d

Merge branch '4.2' into 4.2-buddy-alloc

c567b03

Bring back the 32k and 64k size classes

e2ae245

I think it might be better to look at that problem in a separate follow-up PR. Don't want each PR to get too big.

chrisvest marked this pull request as ready for review January 6, 2026 00:25

chrisvest requested a review from franz1981 January 6, 2026 18:49

Merge branch '4.2' into 4.2-buddy-alloc

471f4eb

# Conflicts: # buffer/src/main/java/io/netty/buffer/AdaptivePoolingAllocator.java

franz1981 reviewed Jan 6, 2026

View reviewed changes

chrisvest added the needs-cherry-pick-5.0 This PR should be cherry-picked to 5.0 once merged. label Jan 7, 2026

chrisvest requested a review from normanmaurer January 8, 2026 21:03

normanmaurer requested changes Jan 9, 2026

View reviewed changes

Address review comments

f1a7aa0

chrisvest requested a review from normanmaurer January 9, 2026 21:11

normanmaurer approved these changes Jan 12, 2026

View reviewed changes

normanmaurer added this to the 4.2.10.Final milestone Jan 12, 2026

chrisvest merged commit 2dbc1e7 into netty:4.2 Jan 12, 2026
47 of 51 checks passed

chrisvest deleted the 4.2-buddy-alloc branch January 12, 2026 22:32

chrisvest added the needs-cherry-pick-4.1 This PR should be cherry-picked to 4.1 once merged. label Jan 12, 2026

nsnmurthyk mentioned this pull request Apr 16, 2026

Netty Issue: GZIP trailer corruption with large payloads after upgrading from 4.2.9 to 4.2.11 #16656

Closed

Uh oh!

Conversation

chrisvest commented Dec 16, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

chrisvest commented Dec 19, 2025

Uh oh!

chrisvest commented Dec 19, 2025

Uh oh!

chrisvest commented Jan 6, 2026

Uh oh!

franz1981 left a comment

Choose a reason for hiding this comment

Uh oh!

normanmaurer left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

normanmaurer Jan 9, 2026

Choose a reason for hiding this comment

Uh oh!

normanmaurer Jan 9, 2026

Choose a reason for hiding this comment

Uh oh!

chrisvest Jan 9, 2026

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

normanmaurer Jan 9, 2026

Choose a reason for hiding this comment

Uh oh!

chrisvest Jan 9, 2026

Choose a reason for hiding this comment

Uh oh!

chrisvest commented Jan 10, 2026

Uh oh!

Uh oh!

normanmaurer commented Jan 12, 2026

Uh oh!

chrisvest commented Jan 12, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

chrisvest commented Dec 16, 2025 •

edited

Loading