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