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