View Javadoc
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 }