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 static io.netty.buffer.PoolChunk.RUN_OFFSET_SHIFT;
20  import static io.netty.buffer.PoolChunk.SIZE_SHIFT;
21  import static io.netty.buffer.PoolChunk.IS_USED_SHIFT;
22  import static io.netty.buffer.PoolChunk.IS_SUBPAGE_SHIFT;
23  import static io.netty.buffer.SizeClasses.LOG2_QUANTUM;
24  
25  final class PoolSubpage<T> implements PoolSubpageMetric {
26  
27      final PoolChunk<T> chunk;
28      final int elemSize;
29      private final int pageShifts;
30      private final int runOffset;
31      private final int runSize;
32      private final long[] bitmap;
33  
34      PoolSubpage<T> prev;
35      PoolSubpage<T> next;
36  
37      boolean doNotDestroy;
38      private int maxNumElems;
39      private int bitmapLength;
40      private int nextAvail;
41      private int numAvail;
42  
43      // TODO: Test if adding padding helps under contention
44      //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
45  
46      /** Special constructor that creates a linked list head */
47      PoolSubpage() {
48          chunk = null;
49          pageShifts = -1;
50          runOffset = -1;
51          elemSize = -1;
52          runSize = -1;
53          bitmap = null;
54      }
55  
56      PoolSubpage(PoolSubpage<T> head, PoolChunk<T> chunk, int pageShifts, int runOffset, int runSize, int elemSize) {
57          this.chunk = chunk;
58          this.pageShifts = pageShifts;
59          this.runOffset = runOffset;
60          this.runSize = runSize;
61          this.elemSize = elemSize;
62          bitmap = new long[runSize >>> 6 + LOG2_QUANTUM]; // runSize / 64 / QUANTUM
63  
64          doNotDestroy = true;
65          if (elemSize != 0) {
66              maxNumElems = numAvail = runSize / elemSize;
67              nextAvail = 0;
68              bitmapLength = maxNumElems >>> 6;
69              if ((maxNumElems & 63) != 0) {
70                  bitmapLength ++;
71              }
72  
73              for (int i = 0; i < bitmapLength; i ++) {
74                  bitmap[i] = 0;
75              }
76          }
77          addToPool(head);
78      }
79  
80      /**
81       * Returns the bitmap index of the subpage allocation.
82       */
83      long allocate() {
84          if (numAvail == 0 || !doNotDestroy) {
85              return -1;
86          }
87  
88          final int bitmapIdx = getNextAvail();
89          int q = bitmapIdx >>> 6;
90          int r = bitmapIdx & 63;
91          assert (bitmap[q] >>> r & 1) == 0;
92          bitmap[q] |= 1L << r;
93  
94          if (-- numAvail == 0) {
95              removeFromPool();
96          }
97  
98          return toHandle(bitmapIdx);
99      }
100 
101     /**
102      * @return {@code true} if this subpage is in use.
103      *         {@code false} if this subpage is not used by its chunk and thus it's OK to be released.
104      */
105     boolean free(PoolSubpage<T> head, int bitmapIdx) {
106         if (elemSize == 0) {
107             return true;
108         }
109         int q = bitmapIdx >>> 6;
110         int r = bitmapIdx & 63;
111         assert (bitmap[q] >>> r & 1) != 0;
112         bitmap[q] ^= 1L << r;
113 
114         setNextAvail(bitmapIdx);
115 
116         if (numAvail ++ == 0) {
117             addToPool(head);
118             /* When maxNumElems == 1, the maximum numAvail is also 1.
119              * Each of these PoolSubpages will go in here when they do free operation.
120              * If they return true directly from here, then the rest of the code will be unreachable
121              * and they will not actually be recycled. So return true only on maxNumElems > 1. */
122             if (maxNumElems > 1) {
123                 return true;
124             }
125         }
126 
127         if (numAvail != maxNumElems) {
128             return true;
129         } else {
130             // Subpage not in use (numAvail == maxNumElems)
131             if (prev == next) {
132                 // Do not remove if this subpage is the only one left in the pool.
133                 return true;
134             }
135 
136             // Remove this subpage from the pool if there are other subpages left in the pool.
137             doNotDestroy = false;
138             removeFromPool();
139             return false;
140         }
141     }
142 
143     private void addToPool(PoolSubpage<T> head) {
144         assert prev == null && next == null;
145         prev = head;
146         next = head.next;
147         next.prev = this;
148         head.next = this;
149     }
150 
151     private void removeFromPool() {
152         assert prev != null && next != null;
153         prev.next = next;
154         next.prev = prev;
155         next = null;
156         prev = null;
157     }
158 
159     private void setNextAvail(int bitmapIdx) {
160         nextAvail = bitmapIdx;
161     }
162 
163     private int getNextAvail() {
164         int nextAvail = this.nextAvail;
165         if (nextAvail >= 0) {
166             this.nextAvail = -1;
167             return nextAvail;
168         }
169         return findNextAvail();
170     }
171 
172     private int findNextAvail() {
173         final long[] bitmap = this.bitmap;
174         final int bitmapLength = this.bitmapLength;
175         for (int i = 0; i < bitmapLength; i ++) {
176             long bits = bitmap[i];
177             if (~bits != 0) {
178                 return findNextAvail0(i, bits);
179             }
180         }
181         return -1;
182     }
183 
184     private int findNextAvail0(int i, long bits) {
185         final int maxNumElems = this.maxNumElems;
186         final int baseVal = i << 6;
187 
188         for (int j = 0; j < 64; j ++) {
189             if ((bits & 1) == 0) {
190                 int val = baseVal | j;
191                 if (val < maxNumElems) {
192                     return val;
193                 } else {
194                     break;
195                 }
196             }
197             bits >>>= 1;
198         }
199         return -1;
200     }
201 
202     private long toHandle(int bitmapIdx) {
203         int pages = runSize >> pageShifts;
204         return (long) runOffset << RUN_OFFSET_SHIFT
205                | (long) pages << SIZE_SHIFT
206                | 1L << IS_USED_SHIFT
207                | 1L << IS_SUBPAGE_SHIFT
208                | bitmapIdx;
209     }
210 
211     @Override
212     public String toString() {
213         final boolean doNotDestroy;
214         final int maxNumElems;
215         final int numAvail;
216         final int elemSize;
217         if (chunk == null) {
218             // This is the head so there is no need to synchronize at all as these never change.
219             doNotDestroy = true;
220             maxNumElems = 0;
221             numAvail = 0;
222             elemSize = -1;
223         } else {
224             synchronized (chunk.arena) {
225                 if (!this.doNotDestroy) {
226                     doNotDestroy = false;
227                     // Not used for creating the String.
228                     maxNumElems = numAvail = elemSize = -1;
229                 } else {
230                     doNotDestroy = true;
231                     maxNumElems = this.maxNumElems;
232                     numAvail = this.numAvail;
233                     elemSize = this.elemSize;
234                 }
235             }
236         }
237 
238         if (!doNotDestroy) {
239             return "(" + runOffset + ": not in use)";
240         }
241 
242         return "(" + runOffset + ": " + (maxNumElems - numAvail) + '/' + maxNumElems +
243                 ", offset: " + runOffset + ", length: " + runSize + ", elemSize: " + elemSize + ')';
244     }
245 
246     @Override
247     public int maxNumElements() {
248         if (chunk == null) {
249             // It's the head.
250             return 0;
251         }
252 
253         synchronized (chunk.arena) {
254             return maxNumElems;
255         }
256     }
257 
258     @Override
259     public int numAvailable() {
260         if (chunk == null) {
261             // It's the head.
262             return 0;
263         }
264 
265         synchronized (chunk.arena) {
266             return numAvail;
267         }
268     }
269 
270     @Override
271     public int elementSize() {
272         if (chunk == null) {
273             // It's the head.
274             return -1;
275         }
276 
277         synchronized (chunk.arena) {
278             return elemSize;
279         }
280     }
281 
282     @Override
283     public int pageSize() {
284         return 1 << pageShifts;
285     }
286 
287     void destroy() {
288         if (chunk != null) {
289             chunk.destroy();
290         }
291     }
292 }