View Javadoc
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.<PoolChunkMetric>emptyList().iterator();
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.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         synchronized (arena) {
213             if (head == null) {
214                 return EMPTY_METRICS;
215             }
216             List<PoolChunkMetric> metrics = new ArrayList<PoolChunkMetric>();
217             for (PoolChunk<T> cur = head;;) {
218                 metrics.add(cur);
219                 cur = cur.next;
220                 if (cur == null) {
221                     break;
222                 }
223             }
224             return metrics.iterator();
225         }
226     }
227 
228     @Override
229     public String toString() {
230         StringBuilder buf = new StringBuilder();
231         synchronized (arena) {
232             if (head == null) {
233                 return "none";
234             }
235 
236             for (PoolChunk<T> cur = head;;) {
237                 buf.append(cur);
238                 cur = cur.next;
239                 if (cur == null) {
240                     break;
241                 }
242                 buf.append(StringUtil.NEWLINE);
243             }
244         }
245         return buf.toString();
246     }
247 
248     void destroy(PoolArena<T> arena) {
249         PoolChunk<T> chunk = head;
250         while (chunk != null) {
251             arena.destroyChunk(chunk);
252             chunk = chunk.next;
253         }
254         head = null;
255     }
256 }