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> {
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(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(elemSize);
57      }
58  
59      void init(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  
75          addToPool();
76      }
77  
78      /**
79       * Returns the bitmap index of the subpage allocation.
80       */
81      long allocate() {
82          if (elemSize == 0) {
83              return toHandle(0);
84          }
85  
86          if (numAvail == 0 || !doNotDestroy) {
87              return -1;
88          }
89  
90          final int bitmapIdx = getNextAvail();
91          int q = bitmapIdx >>> 6;
92          int r = bitmapIdx & 63;
93          assert (bitmap[q] >>> r & 1) == 0;
94          bitmap[q] |= 1L << r;
95  
96          if (-- numAvail == 0) {
97              removeFromPool();
98          }
99  
100         return toHandle(bitmapIdx);
101     }
102 
103     /**
104      * @return {@code true} if this subpage is in use.
105      *         {@code false} if this subpage is not used by its chunk and thus it's OK to be released.
106      */
107     boolean free(int bitmapIdx) {
108 
109         if (elemSize == 0) {
110             return true;
111         }
112 
113         int q = bitmapIdx >>> 6;
114         int r = bitmapIdx & 63;
115         assert (bitmap[q] >>> r & 1) != 0;
116         bitmap[q] ^= 1L << r;
117 
118         setNextAvail(bitmapIdx);
119 
120         if (numAvail ++ == 0) {
121             addToPool();
122             return true;
123         }
124 
125         if (numAvail != maxNumElems) {
126             return true;
127         } else {
128             // Subpage not in use (numAvail == maxNumElems)
129             if (prev == next) {
130                 // Do not remove if this subpage is the only one left in the pool.
131                 return true;
132             }
133 
134             // Remove this subpage from the pool if there are other subpages left in the pool.
135             doNotDestroy = false;
136             removeFromPool();
137             return false;
138         }
139     }
140 
141     private void addToPool() {
142         PoolSubpage<T> head = chunk.arena.findSubpagePoolHead(elemSize);
143         assert prev == null && next == null;
144         prev = head;
145         next = head.next;
146         next.prev = this;
147         head.next = this;
148     }
149 
150     private void removeFromPool() {
151         assert prev != null && next != null;
152         prev.next = next;
153         next.prev = prev;
154         next = null;
155         prev = null;
156     }
157 
158     private void setNextAvail(int bitmapIdx) {
159         nextAvail = bitmapIdx;
160     }
161 
162     private int getNextAvail() {
163         int nextAvail = this.nextAvail;
164         if (nextAvail >= 0) {
165             this.nextAvail = -1;
166             return nextAvail;
167         }
168         return findNextAvail();
169     }
170 
171     private int findNextAvail() {
172         final long[] bitmap = this.bitmap;
173         final int bitmapLength = this.bitmapLength;
174         for (int i = 0; i < bitmapLength; i ++) {
175             long bits = bitmap[i];
176             if (~bits != 0) {
177                 return findNextAvail0(i, bits);
178             }
179         }
180         return -1;
181     }
182 
183     private int findNextAvail0(int i, long bits) {
184         final int maxNumElems = this.maxNumElems;
185         final int baseVal = i << 6;
186 
187         for (int j = 0; j < 64; j ++) {
188             if ((bits & 1) == 0) {
189                 int val = baseVal | j;
190                 if (val < maxNumElems) {
191                     return val;
192                 } else {
193                     break;
194                 }
195             }
196             bits >>>= 1;
197         }
198         return -1;
199     }
200 
201     private long toHandle(int bitmapIdx) {
202         return 0x4000000000000000L | (long) bitmapIdx << 32 | memoryMapIdx;
203     }
204 
205     public String toString() {
206         if (!doNotDestroy) {
207             return "(" + memoryMapIdx + ": not in use)";
208         }
209 
210         return String.valueOf('(') + memoryMapIdx + ": " + (maxNumElems - numAvail) + '/' + maxNumElems +
211                ", offset: " + runOffset + ", length: " + pageSize + ", elemSize: " + elemSize + ')';
212     }
213 }