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 depth_of_id and x as two byte values in memoryMap and depthMap respectively
98   *
99   * memoryMap[id]= depth_of_id  is defined above
100  * depthMap[id]= x  indicates that the first node which is free to be allocated is at depth x (from root)
101  */
102 final class PoolChunk<T> implements PoolChunkMetric {
103 
104     private static final int INTEGER_SIZE_MINUS_ONE = Integer.SIZE - 1;
105 
106     final PoolArena<T> arena;
107     final T memory;
108     final boolean unpooled;
109     final int offset;
110 
111     private final byte[] memoryMap;
112     private final byte[] depthMap;
113     private final PoolSubpage<T>[] subpages;
114     /** Used to determine if the requested capacity is equal to or greater than pageSize. */
115     private final int subpageOverflowMask;
116     private final int pageSize;
117     private final int pageShifts;
118     private final int maxOrder;
119     private final int chunkSize;
120     private final int log2ChunkSize;
121     private final int maxSubpageAllocs;
122     /** Used to mark memory as unusable */
123     private final byte unusable;
124 
125     private int freeBytes;
126 
127     PoolChunkList<T> parent;
128     PoolChunk<T> prev;
129     PoolChunk<T> next;
130 
131     // TODO: Test if adding padding helps under contention
132     //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
133 
134     PoolChunk(PoolArena<T> arena, T memory, int pageSize, int maxOrder, int pageShifts, int chunkSize, int offset) {
135         unpooled = false;
136         this.arena = arena;
137         this.memory = memory;
138         this.pageSize = pageSize;
139         this.pageShifts = pageShifts;
140         this.maxOrder = maxOrder;
141         this.chunkSize = chunkSize;
142         this.offset = offset;
143         unusable = (byte) (maxOrder + 1);
144         log2ChunkSize = log2(chunkSize);
145         subpageOverflowMask = ~(pageSize - 1);
146         freeBytes = chunkSize;
147 
148         assert maxOrder < 30 : "maxOrder should be < 30, but is: " + maxOrder;
149         maxSubpageAllocs = 1 << maxOrder;
150 
151         // Generate the memory map.
152         memoryMap = new byte[maxSubpageAllocs << 1];
153         depthMap = new byte[memoryMap.length];
154         int memoryMapIndex = 1;
155         for (int d = 0; d <= maxOrder; ++ d) { // move down the tree one level at a time
156             int depth = 1 << d;
157             for (int p = 0; p < depth; ++ p) {
158                 // in each level traverse left to right and set value to the depth of subtree
159                 memoryMap[memoryMapIndex] = (byte) d;
160                 depthMap[memoryMapIndex] = (byte) d;
161                 memoryMapIndex ++;
162             }
163         }
164 
165         subpages = newSubpageArray(maxSubpageAllocs);
166     }
167 
168     /** Creates a special chunk that is not pooled. */
169     PoolChunk(PoolArena<T> arena, T memory, int size, int offset) {
170         unpooled = true;
171         this.arena = arena;
172         this.memory = memory;
173         this.offset = offset;
174         memoryMap = null;
175         depthMap = null;
176         subpages = null;
177         subpageOverflowMask = 0;
178         pageSize = 0;
179         pageShifts = 0;
180         maxOrder = 0;
181         unusable = (byte) (maxOrder + 1);
182         chunkSize = size;
183         log2ChunkSize = log2(chunkSize);
184         maxSubpageAllocs = 0;
185     }
186 
187     @SuppressWarnings("unchecked")
188     private PoolSubpage<T>[] newSubpageArray(int size) {
189         return new PoolSubpage[size];
190     }
191 
192     @Override
193     public int usage() {
194         final int freeBytes;
195         synchronized (arena) {
196             freeBytes = this.freeBytes;
197         }
198         return usage(freeBytes);
199     }
200 
201     private int usage(int freeBytes) {
202         if (freeBytes == 0) {
203             return 100;
204         }
205 
206         int freePercentage = (int) (freeBytes * 100L / chunkSize);
207         if (freePercentage == 0) {
208             return 99;
209         }
210         return 100 - freePercentage;
211     }
212 
213     long allocate(int normCapacity) {
214         if ((normCapacity & subpageOverflowMask) != 0) { // >= pageSize
215             return allocateRun(normCapacity);
216         } else {
217             return allocateSubpage(normCapacity);
218         }
219     }
220 
221     /**
222      * Update method used by allocate
223      * This is triggered only when a successor is allocated and all its predecessors
224      * need to update their state
225      * The minimal depth at which subtree rooted at id has some free space
226      *
227      * @param id id
228      */
229     private void updateParentsAlloc(int id) {
230         while (id > 1) {
231             int parentId = id >>> 1;
232             byte val1 = value(id);
233             byte val2 = value(id ^ 1);
234             byte val = val1 < val2 ? val1 : val2;
235             setValue(parentId, val);
236             id = parentId;
237         }
238     }
239 
240     /**
241      * Update method used by free
242      * This needs to handle the special case when both children are completely free
243      * in which case parent be directly allocated on request of size = child-size * 2
244      *
245      * @param id id
246      */
247     private void updateParentsFree(int id) {
248         int logChild = depth(id) + 1;
249         while (id > 1) {
250             int parentId = id >>> 1;
251             byte val1 = value(id);
252             byte val2 = value(id ^ 1);
253             logChild -= 1; // in first iteration equals log, subsequently reduce 1 from logChild as we traverse up
254 
255             if (val1 == logChild && val2 == logChild) {
256                 setValue(parentId, (byte) (logChild - 1));
257             } else {
258                 byte val = val1 < val2 ? val1 : val2;
259                 setValue(parentId, val);
260             }
261 
262             id = parentId;
263         }
264     }
265 
266     /**
267      * Algorithm to allocate an index in memoryMap when we query for a free node
268      * at depth d
269      *
270      * @param d depth
271      * @return index in memoryMap
272      */
273     private int allocateNode(int d) {
274         int id = 1;
275         int initial = - (1 << d); // has last d bits = 0 and rest all = 1
276         byte val = value(id);
277         if (val > d) { // unusable
278             return -1;
279         }
280         while (val < d || (id & initial) == 0) { // id & initial == 1 << d for all ids at depth d, for < d it is 0
281             id <<= 1;
282             val = value(id);
283             if (val > d) {
284                 id ^= 1;
285                 val = value(id);
286             }
287         }
288         byte value = value(id);
289         assert value == d && (id & initial) == 1 << d : String.format("val = %d, id & initial = %d, d = %d",
290                 value, id & initial, d);
291         setValue(id, unusable); // mark as unusable
292         updateParentsAlloc(id);
293         return id;
294     }
295 
296     /**
297      * Allocate a run of pages (>=1)
298      *
299      * @param normCapacity normalized capacity
300      * @return index in memoryMap
301      */
302     private long allocateRun(int normCapacity) {
303         int d = maxOrder - (log2(normCapacity) - pageShifts);
304         int id = allocateNode(d);
305         if (id < 0) {
306             return id;
307         }
308         freeBytes -= runLength(id);
309         return id;
310     }
311 
312     /**
313      * Create/ initialize a new PoolSubpage of normCapacity
314      * Any PoolSubpage created/ initialized here is added to subpage pool in the PoolArena that owns this PoolChunk
315      *
316      * @param normCapacity normalized capacity
317      * @return index in memoryMap
318      */
319     private long allocateSubpage(int normCapacity) {
320         // Obtain the head of the PoolSubPage pool that is owned by the PoolArena and synchronize on it.
321         // This is need as we may add it back and so alter the linked-list structure.
322         PoolSubpage<T> head = arena.findSubpagePoolHead(normCapacity);
323         synchronized (head) {
324             int d = maxOrder; // subpages are only be allocated from pages i.e., leaves
325             int id = allocateNode(d);
326             if (id < 0) {
327                 return id;
328             }
329 
330             final PoolSubpage<T>[] subpages = this.subpages;
331             final int pageSize = this.pageSize;
332 
333             freeBytes -= pageSize;
334 
335             int subpageIdx = subpageIdx(id);
336             PoolSubpage<T> subpage = subpages[subpageIdx];
337             if (subpage == null) {
338                 subpage = new PoolSubpage<T>(head, this, id, runOffset(id), pageSize, normCapacity);
339                 subpages[subpageIdx] = subpage;
340             } else {
341                 subpage.init(head, normCapacity);
342             }
343             return subpage.allocate();
344         }
345     }
346 
347     /**
348      * Free a subpage or a run of pages
349      * When a subpage is freed from PoolSubpage, it might be added back to subpage pool of the owning PoolArena
350      * If the subpage pool in PoolArena has at least one other PoolSubpage of given elemSize, we can
351      * completely free the owning Page so it is available for subsequent allocations
352      *
353      * @param handle handle to free
354      */
355     void free(long handle) {
356         int memoryMapIdx = memoryMapIdx(handle);
357         int bitmapIdx = bitmapIdx(handle);
358 
359         if (bitmapIdx != 0) { // free a subpage
360             PoolSubpage<T> subpage = subpages[subpageIdx(memoryMapIdx)];
361             assert subpage != null && subpage.doNotDestroy;
362 
363             // Obtain the head of the PoolSubPage pool that is owned by the PoolArena and synchronize on it.
364             // This is need as we may add it back and so alter the linked-list structure.
365             PoolSubpage<T> head = arena.findSubpagePoolHead(subpage.elemSize);
366             synchronized (head) {
367                 if (subpage.free(head, bitmapIdx & 0x3FFFFFFF)) {
368                     return;
369                 }
370             }
371         }
372         freeBytes += runLength(memoryMapIdx);
373         setValue(memoryMapIdx, depth(memoryMapIdx));
374         updateParentsFree(memoryMapIdx);
375     }
376 
377     void initBuf(PooledByteBuf<T> buf, long handle, int reqCapacity) {
378         int memoryMapIdx = memoryMapIdx(handle);
379         int bitmapIdx = bitmapIdx(handle);
380         if (bitmapIdx == 0) {
381             byte val = value(memoryMapIdx);
382             assert val == unusable : String.valueOf(val);
383             buf.init(this, handle, runOffset(memoryMapIdx) + offset, reqCapacity, runLength(memoryMapIdx),
384                      arena.parent.threadCache());
385         } else {
386             initBufWithSubpage(buf, handle, bitmapIdx, reqCapacity);
387         }
388     }
389 
390     void initBufWithSubpage(PooledByteBuf<T> buf, long handle, int reqCapacity) {
391         initBufWithSubpage(buf, handle, bitmapIdx(handle), reqCapacity);
392     }
393 
394     private void initBufWithSubpage(PooledByteBuf<T> buf, long handle, int bitmapIdx, int reqCapacity) {
395         assert bitmapIdx != 0;
396 
397         int memoryMapIdx = memoryMapIdx(handle);
398 
399         PoolSubpage<T> subpage = subpages[subpageIdx(memoryMapIdx)];
400         assert subpage.doNotDestroy;
401         assert reqCapacity <= subpage.elemSize;
402 
403         buf.init(
404             this, handle,
405             runOffset(memoryMapIdx) + (bitmapIdx & 0x3FFFFFFF) * subpage.elemSize + offset,
406                 reqCapacity, subpage.elemSize, arena.parent.threadCache());
407     }
408 
409     private byte value(int id) {
410         return memoryMap[id];
411     }
412 
413     private void setValue(int id, byte val) {
414         memoryMap[id] = val;
415     }
416 
417     private byte depth(int id) {
418         return depthMap[id];
419     }
420 
421     private static int log2(int val) {
422         // compute the (0-based, with lsb = 0) position of highest set bit i.e, log2
423         return INTEGER_SIZE_MINUS_ONE - Integer.numberOfLeadingZeros(val);
424     }
425 
426     private int runLength(int id) {
427         // represents the size in #bytes supported by node 'id' in the tree
428         return 1 << log2ChunkSize - depth(id);
429     }
430 
431     private int runOffset(int id) {
432         // represents the 0-based offset in #bytes from start of the byte-array chunk
433         int shift = id ^ 1 << depth(id);
434         return shift * runLength(id);
435     }
436 
437     private int subpageIdx(int memoryMapIdx) {
438         return memoryMapIdx ^ maxSubpageAllocs; // remove highest set bit, to get offset
439     }
440 
441     private static int memoryMapIdx(long handle) {
442         return (int) handle;
443     }
444 
445     private static int bitmapIdx(long handle) {
446         return (int) (handle >>> Integer.SIZE);
447     }
448 
449     @Override
450     public int chunkSize() {
451         return chunkSize;
452     }
453 
454     @Override
455     public int freeBytes() {
456         synchronized (arena) {
457             return freeBytes;
458         }
459     }
460 
461     @Override
462     public String toString() {
463         final int freeBytes;
464         synchronized (arena) {
465             freeBytes = this.freeBytes;
466         }
467 
468         return new StringBuilder()
469                 .append("Chunk(")
470                 .append(Integer.toHexString(System.identityHashCode(this)))
471                 .append(": ")
472                 .append(usage(freeBytes))
473                 .append("%, ")
474                 .append(chunkSize - freeBytes)
475                 .append('/')
476                 .append(chunkSize)
477                 .append(')')
478                 .toString();
479     }
480 
481     void destroy() {
482         arena.destroyChunk(this);
483     }
484 }