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