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  /**
20   * Description of algorithm for PageRun/PoolSubpage allocation from PoolChunk
21   *
22   * Notation: The following terms are important to understand the code
23   * > page  - a page is the smallest unit of memory chunk that can be allocated
24   * > chunk - a chunk is a collection of pages
25   * > in this code chunkSize = 2^{maxOrder} * pageSize
26   *
27   * To begin we allocate a byte array of size = chunkSize
28   * Whenever a ByteBuf of given size needs to be created we search for the first position
29   * in the byte array that has enough empty space to accommodate the requested size and
30   * return a (long) handle that encodes this offset information, (this memory segment is then
31   * marked as reserved so it is always used by exactly one ByteBuf and no more)
32   *
33   * For simplicity all sizes are normalized according to PoolArena#normalizeCapacity method
34   * This ensures that when we request for memory segments of size >= pageSize the normalizedCapacity
35   * equals the next nearest power of 2
36   *
37   * To search for the first offset in chunk that has at least requested size available we construct a
38   * complete balanced binary tree and store it in an array (just like heaps) - memoryMap
39   *
40   * The tree looks like this (the size of each node being mentioned in the parenthesis)
41   *
42   * depth=0        1 node (chunkSize)
43   * depth=1        2 nodes (chunkSize/2)
44   * ..
45   * ..
46   * depth=d        2^d nodes (chunkSize/2^d)
47   * ..
48   * depth=maxOrder 2^maxOrder nodes (chunkSize/2^{maxOrder} = pageSize)
49   *
50   * depth=maxOrder is the last level and the leafs consist of pages
51   *
52   * With this tree available searching in chunkArray translates like this:
53   * To allocate a memory segment of size chunkSize/2^k we search for the first node (from left) at height k
54   * which is unused
55   *
56   * Algorithm:
57   * ----------
58   * Encode the tree in memoryMap with the notation
59   *   memoryMap[id] = x => in the subtree rooted at id, the first node that is free to be allocated
60   *   is at depth x (counted from depth=0) i.e., at depths [depth_of_id, x), there is no node that is free
61   *
62   *  As we allocate & free nodes, we update values stored in memoryMap so that the property is maintained
63   *
64   * Initialization -
65   *   In the beginning we construct the memoryMap array by storing the depth of a node at each node
66   *     i.e., memoryMap[id] = depth_of_id
67   *
68   * Observations:
69   * -------------
70   * 1) memoryMap[id] = depth_of_id  => it is free / unallocated
71   * 2) memoryMap[id] > depth_of_id  => at least one of its child nodes is allocated, so we cannot allocate it, but
72   *                                    some of its children can still be allocated based on their availability
73   * 3) memoryMap[id] = maxOrder + 1 => the node is fully allocated & thus none of its children can be allocated, it
74   *                                    is thus marked as unusable
75   *
76   * Algorithm: [allocateNode(d) => we want to find the first node (from left) at height h that can be allocated]
77   * ----------
78   * 1) start at root (i.e., depth = 0 or id = 1)
79   * 2) if memoryMap[1] > d => cannot be allocated from this chunk
80   * 3) if left node value <= h; we can allocate from left subtree so move to left and repeat until found
81   * 4) else try in right subtree
82   *
83   * Algorithm: [allocateRun(size)]
84   * ----------
85   * 1) Compute d = log_2(chunkSize/size)
86   * 2) Return allocateNode(d)
87   *
88   * Algorithm: [allocateSubpage(size)]
89   * ----------
90   * 1) use allocateNode(maxOrder) to find an empty (i.e., unused) leaf (i.e., page)
91   * 2) use this handle to construct the PoolSubpage object or if it already exists just call init(normCapacity)
92   *    note that this PoolSubpage object is added to subpagesPool in the PoolArena when we init() it
93   *
94   * Note:
95   * -----
96   * In the implementation for improving cache coherence,
97   * we store 2 pieces of information (i.e, 2 byte vals) as a short value in memoryMap
98   *
99   * memoryMap[id]= (depth_of_id, x)
100  * where as per convention defined above
101  * the second value (i.e, x) indicates that the first node which is free to be allocated is at depth x (from root)
102  */
103 
104 final class PoolChunk<T> {
105 
106     final PoolArena<T> arena;
107     final T memory;
108     final boolean unpooled;
109 
110     private final byte[] memoryMap;
111     private final byte[] depthMap;
112     private final PoolSubpage<T>[] subpages;
113     /** Used to determine if the requested capacity is equal to or greater than pageSize. */
114     private final int subpageOverflowMask;
115     private final int pageSize;
116     private final int pageShifts;
117     private final int maxOrder;
118     private final int chunkSize;
119     private final int log2ChunkSize;
120     private final int maxSubpageAllocs;
121     /** Used to mark memory as unusable */
122     private final byte unusable;
123 
124     private int freeBytes;
125 
126     PoolChunkList<T> parent;
127     PoolChunk<T> prev;
128     PoolChunk<T> next;
129 
130     // TODO: Test if adding padding helps under contention
131     //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
132 
133     PoolChunk(PoolArena<T> arena, T memory, int pageSize, int maxOrder, int pageShifts, int chunkSize) {
134         unpooled = false;
135         this.arena = arena;
136         this.memory = memory;
137         this.pageSize = pageSize;
138         this.pageShifts = pageShifts;
139         this.maxOrder = maxOrder;
140         this.chunkSize = chunkSize;
141         unusable = (byte) (maxOrder + 1);
142         log2ChunkSize = log2(chunkSize);
143         subpageOverflowMask = ~(pageSize - 1);
144         freeBytes = chunkSize;
145 
146         assert maxOrder < 30 : "maxOrder should be < 30, but is: " + maxOrder;
147         maxSubpageAllocs = 1 << maxOrder;
148 
149         // Generate the memory map.
150         memoryMap = new byte[maxSubpageAllocs << 1];
151         depthMap = new byte[memoryMap.length];
152         int memoryMapIndex = 1;
153         for (int d = 0; d <= maxOrder; ++ d) { // move down the tree one level at a time
154             int depth = 1 << d;
155             for (int p = 0; p < depth; ++ p) {
156                 // in each level traverse left to right and set value to the depth of subtree
157                 memoryMap[memoryMapIndex] = (byte) d;
158                 depthMap[memoryMapIndex] = (byte) d;
159                 memoryMapIndex ++;
160             }
161         }
162 
163         subpages = newSubpageArray(maxSubpageAllocs);
164     }
165 
166     /** Creates a special chunk that is not pooled. */
167     PoolChunk(PoolArena<T> arena, T memory, int size) {
168         unpooled = true;
169         this.arena = arena;
170         this.memory = memory;
171         memoryMap = null;
172         depthMap = null;
173         subpages = null;
174         subpageOverflowMask = 0;
175         pageSize = 0;
176         pageShifts = 0;
177         maxOrder = 0;
178         unusable = (byte) (maxOrder + 1);
179         chunkSize = size;
180         log2ChunkSize = log2(chunkSize);
181         maxSubpageAllocs = 0;
182     }
183 
184     @SuppressWarnings("unchecked")
185     private PoolSubpage<T>[] newSubpageArray(int size) {
186         return new PoolSubpage[size];
187     }
188 
189     int usage() {
190         final int freeBytes = this.freeBytes;
191         if (freeBytes == 0) {
192             return 100;
193         }
194 
195         int freePercentage = (int) (freeBytes * 100L / chunkSize);
196         if (freePercentage == 0) {
197             return 99;
198         }
199         return 100 - freePercentage;
200     }
201 
202     long allocate(int normCapacity) {
203         if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize
204             return allocateRun(normCapacity);
205         } else {
206             return allocateSubpage(normCapacity);
207         }
208     }
209 
210     /**
211      * Update method used by allocate
212      * This is triggered only when a successor is allocated and all its predecessors
213      * need to update their state
214      * The minimal depth at which subtree rooted at id has some free space
215      *
216      * @param id id
217      */
218     private void updateParentsAlloc(int id) {
219         while (id > 1) {
220             int parentId = id >>> 1;
221             byte val1 = value(id);
222             byte val2 = value(id ^ 1);
223             byte val = val1 < val2 ? val1 : val2;
224             setValue(parentId, val);
225             id = parentId;
226         }
227     }
228 
229     /**
230      * Update method used by free
231      * This needs to handle the special case when both children are completely free
232      * in which case parent be directly allocated on request of size = child-size * 2
233      *
234      * @param id id
235      */
236     private void updateParentsFree(int id) {
237         int logChild = depth(id) + 1;
238         while (id > 1) {
239             int parentId = id >>> 1;
240             byte val1 = value(id);
241             byte val2 = value(id ^ 1);
242             logChild -= 1; // in first iteration equals log, subsequently reduce 1 from logChild as we traverse up
243 
244             if (val1 == logChild && val2 == logChild) {
245                 setValue(parentId, (byte) (logChild - 1));
246             } else {
247                 byte val = val1 < val2 ? val1 : val2;
248                 setValue(parentId, val);
249             }
250 
251             id = parentId;
252         }
253     }
254 
255     /**
256      * Algorithm to allocate an index in memoryMap when we query for a free node
257      * at depth d
258      *
259      * @param d depth
260      * @return index in memoryMap
261      */
262     private int allocateNode(int d) {
263         int id = 1;
264         int initial = - (1 << d); // has last d bits = 0 and rest all = 1
265         byte val = value(id);
266         if (val > d) { // unusable
267             return -1;
268         }
269         while (val < d || (id & initial) == 0) { // id & initial == 1 << d for all ids at depth d, for < d it is 0
270             id <<= 1;
271             val = value(id);
272             if (val > d) {
273                 id ^= 1;
274                 val = value(id);
275             }
276         }
277         byte value = value(id);
278         assert value == d && (id & initial) == 1 << d : String.format("val = %d, id & initial = %d, d = %d",
279                 value, id & initial, d);
280         setValue(id, unusable); // mark as unusable
281         updateParentsAlloc(id);
282         return id;
283     }
284 
285     /**
286      * Allocate a run of pages (>=1)
287      *
288      * @param normCapacity normalized capacity
289      * @return index in memoryMap
290      */
291     private long allocateRun(int normCapacity) {
292         int d = maxOrder - (log2(normCapacity) - pageShifts);
293         int id = allocateNode(d);
294         if (id < 0) {
295             return id;
296         }
297         freeBytes -= runLength(id);
298         return id;
299     }
300 
301     /**
302      * Create/ initialize a new PoolSubpage of normCapacity
303      * Any PoolSubpage created/ initialized here is added to subpage pool in the PoolArena that owns this PoolChunk
304      *
305      * @param normCapacity normalized capacity
306      * @return index in memoryMap
307      */
308     private long allocateSubpage(int normCapacity) {
309         int d = maxOrder; // subpages are only be allocated from pages i.e., leaves
310         int id = allocateNode(d);
311         if (id < 0) {
312             return id;
313         }
314 
315         final PoolSubpage<T>[] subpages = this.subpages;
316         final int pageSize = this.pageSize;
317 
318         freeBytes -= pageSize;
319 
320         int subpageIdx = subpageIdx(id);
321         PoolSubpage<T> subpage = subpages[subpageIdx];
322         if (subpage == null) {
323             subpage = new PoolSubpage<T>(this, id, runOffset(id), pageSize, normCapacity);
324             subpages[subpageIdx] = subpage;
325         } else {
326             subpage.init(normCapacity);
327         }
328         return subpage.allocate();
329     }
330 
331     /**
332      * Free a subpage or a run of pages
333      * When a subpage is freed from PoolSubpage, it might be added back to subpage pool of the owning PoolArena
334      * If the subpage pool in PoolArena has at least one other PoolSubpage of given elemSize, we can
335      * completely free the owning Page so it is available for subsequent allocations
336      *
337      * @param handle handle to free
338      */
339     void free(long handle) {
340         int memoryMapIdx = (int) handle;
341         int bitmapIdx = (int) (handle >>> Integer.SIZE);
342 
343         if (bitmapIdx != 0) { // free a subpage
344             PoolSubpage<T> subpage = subpages[subpageIdx(memoryMapIdx)];
345             assert subpage != null && subpage.doNotDestroy;
346             if (subpage.free(bitmapIdx & 0x3FFFFFFF)) {
347                 return;
348             }
349         }
350         freeBytes += runLength(memoryMapIdx);
351         setValue(memoryMapIdx, depth(memoryMapIdx));
352         updateParentsFree(memoryMapIdx);
353     }
354 
355     void initBuf(PooledByteBuf<T> buf, long handle, int reqCapacity) {
356         int memoryMapIdx = (int) handle;
357         int bitmapIdx = (int) (handle >>> Integer.SIZE);
358         if (bitmapIdx == 0) {
359             byte val = value(memoryMapIdx);
360             assert val == unusable : String.valueOf(val);
361             buf.init(this, handle, runOffset(memoryMapIdx), reqCapacity, runLength(memoryMapIdx));
362         } else {
363             initBufWithSubpage(buf, handle, bitmapIdx, reqCapacity);
364         }
365     }
366 
367     void initBufWithSubpage(PooledByteBuf<T> buf, long handle, int reqCapacity) {
368         initBufWithSubpage(buf, handle, (int) (handle >>> Integer.SIZE), reqCapacity);
369     }
370 
371     private void initBufWithSubpage(PooledByteBuf<T> buf, long handle, int bitmapIdx, int reqCapacity) {
372         assert bitmapIdx != 0;
373 
374         int memoryMapIdx = (int) handle;
375 
376         PoolSubpage<T> subpage = subpages[subpageIdx(memoryMapIdx)];
377         assert subpage.doNotDestroy;
378         assert reqCapacity <= subpage.elemSize;
379 
380         buf.init(
381             this, handle,
382             runOffset(memoryMapIdx) + (bitmapIdx & 0x3FFFFFFF) * subpage.elemSize, reqCapacity, subpage.elemSize);
383     }
384 
385     private byte value(int id) {
386         return memoryMap[id];
387     }
388 
389     private void setValue(int id, byte val) {
390         memoryMap[id] = val;
391     }
392 
393     private byte depth(int id) {
394         return depthMap[id];
395     }
396 
397     private static int log2(int val) {
398         // compute the (0-based, with lsb = 0) position of highest set bit i.e, log2
399         return Integer.SIZE - 1 - Integer.numberOfLeadingZeros(val);
400     }
401 
402     private int runLength(int id) {
403         // represents the size in #bytes supported by node 'id' in the tree
404         return 1 << log2ChunkSize - depth(id);
405     }
406 
407     private int runOffset(int id) {
408         // represents the 0-based offset in #bytes from start of the byte-array chunk
409         int shift = id ^ 1 << depth(id);
410         return shift * runLength(id);
411     }
412 
413     private int subpageIdx(int memoryMapIdx) {
414         return memoryMapIdx ^ maxSubpageAllocs; // remove highest set bit, to get offset
415     }
416 
417     @Override
418     public String toString() {
419         return new StringBuilder()
420             .append("Chunk(")
421             .append(Integer.toHexString(System.identityHashCode(this)))
422             .append(": ")
423             .append(usage())
424             .append("%, ")
425             .append(chunkSize - freeBytes)
426             .append('/')
427             .append(chunkSize)
428             .append(')')
429             .toString();
430     }
431 }