View Javadoc
1   /*
2    * Copyright 2020 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    *   https://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  package io.netty.buffer;
17  
18  import static io.netty.buffer.PoolThreadCache.*;
19  
20  /**
21   * SizeClasses requires {@code pageShifts} to be defined prior to inclusion,
22   * and it in turn defines:
23   * <p>
24   *   LOG2_SIZE_CLASS_GROUP: Log of size class count for each size doubling.
25   *   LOG2_MAX_LOOKUP_SIZE: Log of max size class in the lookup table.
26   *   sizeClasses: Complete table of [index, log2Group, log2Delta, nDelta, isMultiPageSize,
27   *                 isSubPage, log2DeltaLookup] tuples.
28   *     index: Size class index.
29   *     log2Group: Log of group base size (no deltas added).
30   *     log2Delta: Log of delta to previous size class.
31   *     nDelta: Delta multiplier.
32   *     isMultiPageSize: 'yes' if a multiple of the page size, 'no' otherwise.
33   *     isSubPage: 'yes' if a subpage size class, 'no' otherwise.
34   *     log2DeltaLookup: Same as log2Delta if a lookup table size class, 'no'
35   *                      otherwise.
36   * <p>
37   *   nSubpages: Number of subpages size classes.
38   *   nSizes: Number of size classes.
39   *   nPSizes: Number of size classes that are multiples of pageSize.
40   *
41   *   smallMaxSizeIdx: Maximum small size class index.
42   *
43   *   lookupMaxClass: Maximum size class included in lookup table.
44   *   log2NormalMinClass: Log of minimum normal size class.
45   * <p>
46   *   The first size class and spacing are 1 << LOG2_QUANTUM.
47   *   Each group has 1 << LOG2_SIZE_CLASS_GROUP of size classes.
48   *
49   *   size = 1 << log2Group + nDelta * (1 << log2Delta)
50   *
51   *   The first size class has an unusual encoding, because the size has to be
52   *   split between group and delta*nDelta.
53   *
54   *   If pageShift = 13, sizeClasses looks like this:
55   *
56   *   (index, log2Group, log2Delta, nDelta, isMultiPageSize, isSubPage, log2DeltaLookup)
57   * <p>
58   *   ( 0,     4,        4,         0,       no,             yes,        4)
59   *   ( 1,     4,        4,         1,       no,             yes,        4)
60   *   ( 2,     4,        4,         2,       no,             yes,        4)
61   *   ( 3,     4,        4,         3,       no,             yes,        4)
62   * <p>
63   *   ( 4,     6,        4,         1,       no,             yes,        4)
64   *   ( 5,     6,        4,         2,       no,             yes,        4)
65   *   ( 6,     6,        4,         3,       no,             yes,        4)
66   *   ( 7,     6,        4,         4,       no,             yes,        4)
67   * <p>
68   *   ( 8,     7,        5,         1,       no,             yes,        5)
69   *   ( 9,     7,        5,         2,       no,             yes,        5)
70   *   ( 10,    7,        5,         3,       no,             yes,        5)
71   *   ( 11,    7,        5,         4,       no,             yes,        5)
72   *   ...
73   *   ...
74   *   ( 72,    23,       21,        1,       yes,            no,        no)
75   *   ( 73,    23,       21,        2,       yes,            no,        no)
76   *   ( 74,    23,       21,        3,       yes,            no,        no)
77   *   ( 75,    23,       21,        4,       yes,            no,        no)
78   * <p>
79   *   ( 76,    24,       22,        1,       yes,            no,        no)
80   */
81  abstract class SizeClasses implements SizeClassesMetric {
82  
83      static final int LOG2_QUANTUM = 4;
84  
85      private static final int LOG2_SIZE_CLASS_GROUP = 2;
86      private static final int LOG2_MAX_LOOKUP_SIZE = 12;
87  
88      private static final int INDEX_IDX = 0;
89      private static final int LOG2GROUP_IDX = 1;
90      private static final int LOG2DELTA_IDX = 2;
91      private static final int NDELTA_IDX = 3;
92      private static final int PAGESIZE_IDX = 4;
93      private static final int SUBPAGE_IDX = 5;
94      private static final int LOG2_DELTA_LOOKUP_IDX = 6;
95  
96      private static final byte no = 0, yes = 1;
97  
98      protected final int pageSize;
99      protected final int pageShifts;
100     protected final int chunkSize;
101     protected final int directMemoryCacheAlignment;
102 
103     final int nSizes;
104     final int nSubpages;
105     final int nPSizes;
106     final int lookupMaxSize;
107     final int smallMaxSizeIdx;
108 
109     private final int[] pageIdx2sizeTab;
110 
111     // lookup table for sizeIdx <= smallMaxSizeIdx
112     private final int[] sizeIdx2sizeTab;
113 
114     // lookup table used for size <= lookupMaxClass
115     // spacing is 1 << LOG2_QUANTUM, so the size of array is lookupMaxClass >> LOG2_QUANTUM
116     private final int[] size2idxTab;
117 
118     protected SizeClasses(int pageSize, int pageShifts, int chunkSize, int directMemoryCacheAlignment) {
119         int group = log2(chunkSize) + 1 - LOG2_QUANTUM;
120 
121         //generate size classes
122         //[index, log2Group, log2Delta, nDelta, isMultiPageSize, isSubPage, log2DeltaLookup]
123         short[][] sizeClasses = new short[group << LOG2_SIZE_CLASS_GROUP][7];
124 
125         int normalMaxSize = -1;
126         int nSizes = 0;
127         int size = 0;
128 
129         int log2Group = LOG2_QUANTUM;
130         int log2Delta = LOG2_QUANTUM;
131         int ndeltaLimit = 1 << LOG2_SIZE_CLASS_GROUP;
132 
133         //First small group, nDelta start at 0.
134         //first size class is 1 << LOG2_QUANTUM
135         for (int nDelta = 0; nDelta < ndeltaLimit; nDelta++, nSizes++) {
136             short[] sizeClass = newSizeClass(nSizes, log2Group, log2Delta, nDelta, pageShifts);
137             sizeClasses[nSizes] = sizeClass;
138             size = sizeOf(sizeClass, directMemoryCacheAlignment);
139         }
140 
141         log2Group += LOG2_SIZE_CLASS_GROUP;
142 
143         //All remaining groups, nDelta start at 1.
144         for (; size < chunkSize; log2Group++, log2Delta++) {
145             for (int nDelta = 1; nDelta <= ndeltaLimit && size < chunkSize; nDelta++, nSizes++) {
146                 short[] sizeClass = newSizeClass(nSizes, log2Group, log2Delta, nDelta, pageShifts);
147                 sizeClasses[nSizes] = sizeClass;
148                 size = normalMaxSize = sizeOf(sizeClass, directMemoryCacheAlignment);
149             }
150         }
151 
152         //chunkSize must be normalMaxSize
153         assert chunkSize == normalMaxSize;
154 
155         int smallMaxSizeIdx = 0;
156         int lookupMaxSize = 0;
157         int nPSizes = 0;
158         int nSubpages = 0;
159         for (int idx = 0; idx < nSizes; idx++) {
160             short[] sz = sizeClasses[idx];
161             if (sz[PAGESIZE_IDX] == yes) {
162                 nPSizes++;
163             }
164             if (sz[SUBPAGE_IDX] == yes) {
165                 nSubpages++;
166                 smallMaxSizeIdx = idx;
167             }
168             if (sz[LOG2_DELTA_LOOKUP_IDX] != no) {
169                 lookupMaxSize = sizeOf(sz, directMemoryCacheAlignment);
170             }
171         }
172         this.smallMaxSizeIdx = smallMaxSizeIdx;
173         this.lookupMaxSize = lookupMaxSize;
174         this.nPSizes = nPSizes;
175         this.nSubpages = nSubpages;
176         this.nSizes = nSizes;
177 
178         this.pageSize = pageSize;
179         this.pageShifts = pageShifts;
180         this.chunkSize = chunkSize;
181         this.directMemoryCacheAlignment = directMemoryCacheAlignment;
182 
183         //generate lookup tables
184         sizeIdx2sizeTab = newIdx2SizeTab(sizeClasses, nSizes, directMemoryCacheAlignment);
185         pageIdx2sizeTab = newPageIdx2sizeTab(sizeClasses, nSizes, nPSizes, directMemoryCacheAlignment);
186         size2idxTab = newSize2idxTab(lookupMaxSize, sizeClasses);
187     }
188 
189     //calculate size class
190     private static short[] newSizeClass(int index, int log2Group, int log2Delta, int nDelta, int pageShifts) {
191         short isMultiPageSize;
192         if (log2Delta >= pageShifts) {
193             isMultiPageSize = yes;
194         } else {
195             int pageSize = 1 << pageShifts;
196             int size = calculateSize(log2Group, nDelta, log2Delta);
197 
198             isMultiPageSize = size == size / pageSize * pageSize? yes : no;
199         }
200 
201         int log2Ndelta = nDelta == 0? 0 : log2(nDelta);
202 
203         byte remove = 1 << log2Ndelta < nDelta? yes : no;
204 
205         int log2Size = log2Delta + log2Ndelta == log2Group? log2Group + 1 : log2Group;
206         if (log2Size == log2Group) {
207             remove = yes;
208         }
209 
210         short isSubpage = log2Size < pageShifts + LOG2_SIZE_CLASS_GROUP? yes : no;
211 
212         int log2DeltaLookup = log2Size < LOG2_MAX_LOOKUP_SIZE ||
213                               log2Size == LOG2_MAX_LOOKUP_SIZE && remove == no
214                 ? log2Delta : no;
215 
216         return new short[] {
217                 (short) index, (short) log2Group, (short) log2Delta,
218                 (short) nDelta, isMultiPageSize, isSubpage, (short) log2DeltaLookup
219         };
220     }
221 
222     private static int[] newIdx2SizeTab(short[][] sizeClasses, int nSizes, int directMemoryCacheAlignment) {
223         int[] sizeIdx2sizeTab = new int[nSizes];
224 
225         for (int i = 0; i < nSizes; i++) {
226             short[] sizeClass = sizeClasses[i];
227             sizeIdx2sizeTab[i] = sizeOf(sizeClass, directMemoryCacheAlignment);
228         }
229         return sizeIdx2sizeTab;
230     }
231 
232     private static int calculateSize(int log2Group, int nDelta, int log2Delta) {
233         return (1 << log2Group) + (nDelta << log2Delta);
234     }
235 
236     private static int sizeOf(short[] sizeClass, int directMemoryCacheAlignment) {
237         int log2Group = sizeClass[LOG2GROUP_IDX];
238         int log2Delta = sizeClass[LOG2DELTA_IDX];
239         int nDelta = sizeClass[NDELTA_IDX];
240 
241         int size = calculateSize(log2Group, nDelta, log2Delta);
242 
243         return alignSizeIfNeeded(size, directMemoryCacheAlignment);
244     }
245 
246     private static int[] newPageIdx2sizeTab(short[][] sizeClasses, int nSizes, int nPSizes,
247                                             int directMemoryCacheAlignment) {
248         int[] pageIdx2sizeTab = new int[nPSizes];
249         int pageIdx = 0;
250         for (int i = 0; i < nSizes; i++) {
251             short[] sizeClass = sizeClasses[i];
252             if (sizeClass[PAGESIZE_IDX] == yes) {
253                 pageIdx2sizeTab[pageIdx++] = sizeOf(sizeClass, directMemoryCacheAlignment);
254             }
255         }
256         return pageIdx2sizeTab;
257     }
258 
259     private static int[] newSize2idxTab(int lookupMaxSize, short[][] sizeClasses) {
260         int[] size2idxTab = new int[lookupMaxSize >> LOG2_QUANTUM];
261         int idx = 0;
262         int size = 0;
263 
264         for (int i = 0; size <= lookupMaxSize; i++) {
265             int log2Delta = sizeClasses[i][LOG2DELTA_IDX];
266             int times = 1 << log2Delta - LOG2_QUANTUM;
267 
268             while (size <= lookupMaxSize && times-- > 0) {
269                 size2idxTab[idx++] = i;
270                 size = idx + 1 << LOG2_QUANTUM;
271             }
272         }
273         return size2idxTab;
274     }
275 
276     @Override
277     public int sizeIdx2size(int sizeIdx) {
278         return sizeIdx2sizeTab[sizeIdx];
279     }
280 
281     @Override
282     public int sizeIdx2sizeCompute(int sizeIdx) {
283         int group = sizeIdx >> LOG2_SIZE_CLASS_GROUP;
284         int mod = sizeIdx & (1 << LOG2_SIZE_CLASS_GROUP) - 1;
285 
286         int groupSize = group == 0? 0 :
287                 1 << LOG2_QUANTUM + LOG2_SIZE_CLASS_GROUP - 1 << group;
288 
289         int shift = group == 0? 1 : group;
290         int lgDelta = shift + LOG2_QUANTUM - 1;
291         int modSize = mod + 1 << lgDelta;
292 
293         return groupSize + modSize;
294     }
295 
296     @Override
297     public long pageIdx2size(int pageIdx) {
298         return pageIdx2sizeTab[pageIdx];
299     }
300 
301     @Override
302     public long pageIdx2sizeCompute(int pageIdx) {
303         int group = pageIdx >> LOG2_SIZE_CLASS_GROUP;
304         int mod = pageIdx & (1 << LOG2_SIZE_CLASS_GROUP) - 1;
305 
306         long groupSize = group == 0? 0 :
307                 1L << pageShifts + LOG2_SIZE_CLASS_GROUP - 1 << group;
308 
309         int shift = group == 0? 1 : group;
310         int log2Delta = shift + pageShifts - 1;
311         int modSize = mod + 1 << log2Delta;
312 
313         return groupSize + modSize;
314     }
315 
316     @Override
317     public int size2SizeIdx(int size) {
318         if (size == 0) {
319             return 0;
320         }
321         if (size > chunkSize) {
322             return nSizes;
323         }
324 
325         size = alignSizeIfNeeded(size, directMemoryCacheAlignment);
326 
327         if (size <= lookupMaxSize) {
328             //size-1 / MIN_TINY
329             return size2idxTab[size - 1 >> LOG2_QUANTUM];
330         }
331 
332         int x = log2((size << 1) - 1);
333         int shift = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
334                 ? 0 : x - (LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM);
335 
336         int group = shift << LOG2_SIZE_CLASS_GROUP;
337 
338         int log2Delta = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
339                 ? LOG2_QUANTUM : x - LOG2_SIZE_CLASS_GROUP - 1;
340 
341         int deltaInverseMask = -1 << log2Delta;
342         int mod = (size - 1 & deltaInverseMask) >> log2Delta &
343                   (1 << LOG2_SIZE_CLASS_GROUP) - 1;
344 
345         return group + mod;
346     }
347 
348     @Override
349     public int pages2pageIdx(int pages) {
350         return pages2pageIdxCompute(pages, false);
351     }
352 
353     @Override
354     public int pages2pageIdxFloor(int pages) {
355         return pages2pageIdxCompute(pages, true);
356     }
357 
358     private int pages2pageIdxCompute(int pages, boolean floor) {
359         int pageSize = pages << pageShifts;
360         if (pageSize > chunkSize) {
361             return nPSizes;
362         }
363 
364         int x = log2((pageSize << 1) - 1);
365 
366         int shift = x < LOG2_SIZE_CLASS_GROUP + pageShifts
367                 ? 0 : x - (LOG2_SIZE_CLASS_GROUP + pageShifts);
368 
369         int group = shift << LOG2_SIZE_CLASS_GROUP;
370 
371         int log2Delta = x < LOG2_SIZE_CLASS_GROUP + pageShifts + 1?
372                 pageShifts : x - LOG2_SIZE_CLASS_GROUP - 1;
373 
374         int deltaInverseMask = -1 << log2Delta;
375         int mod = (pageSize - 1 & deltaInverseMask) >> log2Delta &
376                   (1 << LOG2_SIZE_CLASS_GROUP) - 1;
377 
378         int pageIdx = group + mod;
379 
380         if (floor && pageIdx2sizeTab[pageIdx] > pages << pageShifts) {
381             pageIdx--;
382         }
383 
384         return pageIdx;
385     }
386 
387     // Round size up to the nearest multiple of alignment.
388     private static int alignSizeIfNeeded(int size, int directMemoryCacheAlignment) {
389         if (directMemoryCacheAlignment <= 0) {
390             return size;
391         }
392         int delta = size & directMemoryCacheAlignment - 1;
393         return delta == 0? size : size + directMemoryCacheAlignment - delta;
394     }
395 
396     @Override
397     public int normalizeSize(int size) {
398         if (size == 0) {
399             return sizeIdx2sizeTab[0];
400         }
401         size = alignSizeIfNeeded(size, directMemoryCacheAlignment);
402         if (size <= lookupMaxSize) {
403             int ret = sizeIdx2sizeTab[size2idxTab[size - 1 >> LOG2_QUANTUM]];
404             assert ret == normalizeSizeCompute(size);
405             return ret;
406         }
407         return normalizeSizeCompute(size);
408     }
409 
410     private static int normalizeSizeCompute(int size) {
411         int x = log2((size << 1) - 1);
412         int log2Delta = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
413                 ? LOG2_QUANTUM : x - LOG2_SIZE_CLASS_GROUP - 1;
414         int delta = 1 << log2Delta;
415         int delta_mask = delta - 1;
416         return size + delta_mask & ~delta_mask;
417     }
418 }