1 /*
2 * Copyright 2021 The Netty Project
3 *
4 * The Netty Project licenses this file to you under the Apache License,
5 * version 2.0 (the "License"); you may not use this file except in compliance
6 * with the License. You may obtain a copy of the License at:
7 *
8 * https://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
12 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13 * License for the specific language governing permissions and limitations
14 * under the License.
15 */
16 package io.netty5.buffer.api.pool;
17
18 import io.netty5.util.internal.StringUtil;
19
20 import java.util.ArrayList;
21 import java.util.Collections;
22 import java.util.Iterator;
23 import java.util.List;
24
25 import static java.lang.Math.max;
26 import static java.lang.Math.min;
27
28 final class PoolChunkList implements PoolChunkListMetric {
29 private static final Iterator<PoolChunkMetric> EMPTY_METRICS = Collections.emptyIterator();
30 private final PoolArena arena;
31 private final PoolChunkList nextList;
32 private final int minUsage;
33 private final int maxUsage;
34 private final int maxCapacity;
35 private PoolChunk head;
36 private final int freeMinThreshold;
37 private final int freeMaxThreshold;
38
39 // This is only update once when create the linked like list of PoolChunkList in PoolArena constructor.
40 private PoolChunkList prevList;
41
42 PoolChunkList(PoolArena arena, PoolChunkList nextList, int minUsage, int maxUsage, int chunkSize) {
43 assert minUsage <= maxUsage;
44 this.arena = arena;
45 this.nextList = nextList;
46 this.minUsage = minUsage;
47 this.maxUsage = maxUsage;
48 maxCapacity = calculateMaxCapacity(minUsage, chunkSize);
49
50 // the thresholds are aligned with PoolChunk.usage() logic:
51 // 1) basic logic: usage() = 100 - freeBytes * 100L / chunkSize
52 // so, for example: (usage() >= maxUsage) condition can be transformed in the following way:
53 // 100 - freeBytes * 100L / chunkSize >= maxUsage
54 // freeBytes <= chunkSize * (100 - maxUsage) / 100
55 // let freeMinThreshold = chunkSize * (100 - maxUsage) / 100, then freeBytes <= freeMinThreshold
56 //
57 // 2) usage() returns an int value and has a floor rounding during a calculation,
58 // to be aligned absolute thresholds should be shifted for "the rounding step":
59 // freeBytes * 100 / chunkSize < 1
60 // the condition can be converted to: freeBytes < 1 * chunkSize / 100
61 // this is why we have + 0.99999999 shifts. A example why just +1 shift cannot be used:
62 // freeBytes = 16777216 == freeMaxThreshold: 16777216, usage = 0 < minUsage: 1, chunkSize: 16777216
63 // At the same time we want to have zero thresholds in case of (maxUsage == 100) and (minUsage == 100).
64 //
65 freeMinThreshold = maxUsage == 100 ? 0 : (int) (chunkSize * (100.0 - maxUsage + 0.99999999) / 100L);
66 freeMaxThreshold = minUsage == 100 ? 0 : (int) (chunkSize * (100.0 - minUsage + 0.99999999) / 100L);
67 }
68
69 /**
70 * Calculates the maximum capacity of a buffer that will ever be possible to allocate out of the {@link PoolChunk}s
71 * that belong to the {@link PoolChunkList} with the given {@code minUsage} and {@code maxUsage} settings.
72 */
73 private static int calculateMaxCapacity(int minUsage, int chunkSize) {
74 minUsage = minUsage0(minUsage);
75
76 if (minUsage == 100) {
77 // If the minUsage is 100 we can not allocate anything out of this list.
78 return 0;
79 }
80
81 // Calculate the maximum amount of bytes that can be allocated from a PoolChunk in this PoolChunkList.
82 //
83 // As an example:
84 // - If a PoolChunkList has minUsage == 25 we are allowed to allocate at most 75% of the chunkSize because
85 // this is the maximum amount available in any PoolChunk in this PoolChunkList.
86 return (int) (chunkSize * (100L - minUsage) / 100L);
87 }
88
89 void prevList(PoolChunkList prevList) {
90 assert this.prevList == null;
91 this.prevList = prevList;
92 }
93
94 UntetheredMemory allocate(int size, int sizeIdx, PoolThreadCache threadCache) {
95 int normCapacity = arena.sizeIdx2size(sizeIdx);
96 if (normCapacity > maxCapacity) {
97 // Either this PoolChunkList is empty, or the requested capacity is larger than the capacity which can
98 // be handled by the PoolChunks that are contained in this PoolChunkList.
99 return null;
100 }
101
102 for (PoolChunk cur = head; cur != null; cur = cur.next) {
103 UntetheredMemory memory = cur.allocate(size, sizeIdx, threadCache);
104 if (memory != null) {
105 if (cur.freeBytes <= freeMinThreshold) {
106 remove(cur);
107 nextList.add(cur);
108 }
109 return memory;
110 }
111 }
112 return null;
113 }
114
115 boolean free(PoolChunk chunk, long handle, int normCapacity) {
116 chunk.free(handle, normCapacity);
117 if (chunk.freeBytes > freeMaxThreshold) {
118 remove(chunk);
119 // Move the PoolChunk down the PoolChunkList linked-list.
120 return move0(chunk);
121 }
122 return true;
123 }
124
125 private boolean move(PoolChunk chunk) {
126 if (chunk.freeBytes > freeMaxThreshold) {
127 // Move the PoolChunk down the PoolChunkList linked-list.
128 return move0(chunk);
129 }
130
131 // PoolChunk fits into this PoolChunkList, adding it here.
132 add0(chunk);
133 return true;
134 }
135
136 /**
137 * Moves the {@link PoolChunk} down the {@link PoolChunkList} linked-list, so it will end up in the right
138 * {@link PoolChunkList} that has the correct minUsage / maxUsage in respect to {@link PoolChunk#usage()}.
139 */
140 private boolean move0(PoolChunk chunk) {
141 if (prevList == null) {
142 // There is no previous PoolChunkList so return false which result in having the PoolChunk destroyed and
143 // all memory associated with the PoolChunk will be released.
144 return false;
145 }
146 return prevList.move(chunk);
147 }
148
149 void add(PoolChunk chunk) {
150 if (chunk.freeBytes <= freeMinThreshold) {
151 nextList.add(chunk);
152 return;
153 }
154 add0(chunk);
155 }
156
157 /**
158 * Adds the {@link PoolChunk} to this {@link PoolChunkList}.
159 */
160 void add0(PoolChunk chunk) {
161 chunk.parent = this;
162 if (head == null) {
163 head = chunk;
164 chunk.prev = null;
165 chunk.next = null;
166 } else {
167 chunk.prev = null;
168 chunk.next = head;
169 head.prev = chunk;
170 head = chunk;
171 }
172 }
173
174 private void remove(PoolChunk cur) {
175 if (cur == head) {
176 head = cur.next;
177 if (head != null) {
178 head.prev = null;
179 }
180 } else {
181 PoolChunk next = cur.next;
182 cur.prev.next = next;
183 if (next != null) {
184 next.prev = cur.prev;
185 }
186 }
187 }
188
189 @Override
190 public int minUsage() {
191 return minUsage0(minUsage);
192 }
193
194 @Override
195 public int maxUsage() {
196 return min(maxUsage, 100);
197 }
198
199 private static int minUsage0(int value) {
200 return max(1, value);
201 }
202
203 @Override
204 public Iterator<PoolChunkMetric> iterator() {
205 arena.lock();
206 try {
207 if (head == null) {
208 return EMPTY_METRICS;
209 }
210 List<PoolChunkMetric> metrics = new ArrayList<>();
211 for (PoolChunk cur = head;;) {
212 metrics.add(cur);
213 cur = cur.next;
214 if (cur == null) {
215 break;
216 }
217 }
218 return metrics.iterator();
219 } finally {
220 arena.unlock();
221 }
222 }
223
224 @Override
225 public String toString() {
226 StringBuilder buf = new StringBuilder();
227 arena.lock();
228 try {
229 if (head == null) {
230 return "none";
231 }
232
233 for (PoolChunk cur = head;;) {
234 buf.append(cur);
235 cur = cur.next;
236 if (cur == null) {
237 break;
238 }
239 buf.append(StringUtil.NEWLINE);
240 }
241 } finally {
242 arena.unlock();
243 }
244 return buf.toString();
245 }
246
247 void destroy() {
248 PoolChunk chunk = head;
249 while (chunk != null) {
250 chunk.destroy();
251 PoolChunk tmp = chunk;
252 chunk = chunk.next;
253 tmp.next = null;
254 tmp.prev = null;
255 }
256 head = null;
257 }
258 }