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