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 final 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 LOG2GROUP_IDX = 1;
89 private static final int LOG2DELTA_IDX = 2;
90 private static final int NDELTA_IDX = 3;
91 private static final int PAGESIZE_IDX = 4;
92 private static final int SUBPAGE_IDX = 5;
93 private static final int LOG2_DELTA_LOOKUP_IDX = 6;
94
95 private static final byte no = 0, yes = 1;
96
97 final int pageSize;
98 final int pageShifts;
99 final int chunkSize;
100 final int directMemoryCacheAlignment;
101
102 final int nSizes;
103 final int nSubpages;
104 final int nPSizes;
105 final int lookupMaxSize;
106 final int smallMaxSizeIdx;
107
108 private final int[] pageIdx2sizeTab;
109
110 // lookup table for sizeIdx <= smallMaxSizeIdx
111 private final int[] sizeIdx2sizeTab;
112
113 // lookup table used for size <= lookupMaxClass
114 // spacing is 1 << LOG2_QUANTUM, so the size of array is lookupMaxClass >> LOG2_QUANTUM
115 private final int[] size2idxTab;
116
117 SizeClasses(int pageSize, int pageShifts, int chunkSize, int directMemoryCacheAlignment) {
118 int group = log2(chunkSize) - LOG2_QUANTUM - LOG2_SIZE_CLASS_GROUP + 1;
119
120 //generate size classes
121 //[index, log2Group, log2Delta, nDelta, isMultiPageSize, isSubPage, log2DeltaLookup]
122 short[][] sizeClasses = new short[group << LOG2_SIZE_CLASS_GROUP][7];
123
124 int normalMaxSize = -1;
125 int nSizes = 0;
126 int size = 0;
127
128 int log2Group = LOG2_QUANTUM;
129 int log2Delta = LOG2_QUANTUM;
130 int ndeltaLimit = 1 << LOG2_SIZE_CLASS_GROUP;
131
132 //First small group, nDelta start at 0.
133 //first size class is 1 << LOG2_QUANTUM
134 for (int nDelta = 0; nDelta < ndeltaLimit; nDelta++, nSizes++) {
135 short[] sizeClass = newSizeClass(nSizes, log2Group, log2Delta, nDelta, pageShifts);
136 sizeClasses[nSizes] = sizeClass;
137 size = sizeOf(sizeClass, directMemoryCacheAlignment);
138 }
139
140 log2Group += LOG2_SIZE_CLASS_GROUP;
141
142 //All remaining groups, nDelta start at 1.
143 for (; size < chunkSize; log2Group++, log2Delta++) {
144 for (int nDelta = 1; nDelta <= ndeltaLimit && size < chunkSize; nDelta++, nSizes++) {
145 short[] sizeClass = newSizeClass(nSizes, log2Group, log2Delta, nDelta, pageShifts);
146 sizeClasses[nSizes] = sizeClass;
147 size = normalMaxSize = sizeOf(sizeClass, directMemoryCacheAlignment);
148 }
149 }
150
151 //chunkSize must be normalMaxSize
152 assert chunkSize == normalMaxSize;
153
154 int smallMaxSizeIdx = 0;
155 int lookupMaxSize = 0;
156 int nPSizes = 0;
157 int nSubpages = 0;
158 for (int idx = 0; idx < nSizes; idx++) {
159 short[] sz = sizeClasses[idx];
160 if (sz[PAGESIZE_IDX] == yes) {
161 nPSizes++;
162 }
163 if (sz[SUBPAGE_IDX] == yes) {
164 nSubpages++;
165 smallMaxSizeIdx = idx;
166 }
167 if (sz[LOG2_DELTA_LOOKUP_IDX] != no) {
168 lookupMaxSize = sizeOf(sz, directMemoryCacheAlignment);
169 }
170 }
171 this.smallMaxSizeIdx = smallMaxSizeIdx;
172 this.lookupMaxSize = lookupMaxSize;
173 this.nPSizes = nPSizes;
174 this.nSubpages = nSubpages;
175 this.nSizes = nSizes;
176
177 this.pageSize = pageSize;
178 this.pageShifts = pageShifts;
179 this.chunkSize = chunkSize;
180 this.directMemoryCacheAlignment = directMemoryCacheAlignment;
181
182 //generate lookup tables
183 this.sizeIdx2sizeTab = newIdx2SizeTab(sizeClasses, nSizes, directMemoryCacheAlignment);
184 this.pageIdx2sizeTab = newPageIdx2sizeTab(sizeClasses, nSizes, nPSizes, directMemoryCacheAlignment);
185 this.size2idxTab = newSize2idxTab(lookupMaxSize, sizeClasses);
186 }
187
188 //calculate size class
189 private static short[] newSizeClass(int index, int log2Group, int log2Delta, int nDelta, int pageShifts) {
190 short isMultiPageSize;
191 if (log2Delta >= pageShifts) {
192 isMultiPageSize = yes;
193 } else {
194 int pageSize = 1 << pageShifts;
195 int size = calculateSize(log2Group, nDelta, log2Delta);
196
197 isMultiPageSize = size == size / pageSize * pageSize? yes : no;
198 }
199
200 int log2Ndelta = nDelta == 0? 0 : log2(nDelta);
201
202 byte remove = 1 << log2Ndelta < nDelta? yes : no;
203
204 int log2Size = log2Delta + log2Ndelta == log2Group? log2Group + 1 : log2Group;
205 if (log2Size == log2Group) {
206 remove = yes;
207 }
208
209 short isSubpage = log2Size < pageShifts + LOG2_SIZE_CLASS_GROUP? yes : no;
210
211 int log2DeltaLookup = log2Size < LOG2_MAX_LOOKUP_SIZE ||
212 log2Size == LOG2_MAX_LOOKUP_SIZE && remove == no
213 ? log2Delta : no;
214
215 return new short[] {
216 (short) index, (short) log2Group, (short) log2Delta,
217 (short) nDelta, isMultiPageSize, isSubpage, (short) log2DeltaLookup
218 };
219 }
220
221 private static int[] newIdx2SizeTab(short[][] sizeClasses, int nSizes, int directMemoryCacheAlignment) {
222 int[] sizeIdx2sizeTab = new int[nSizes];
223
224 for (int i = 0; i < nSizes; i++) {
225 short[] sizeClass = sizeClasses[i];
226 sizeIdx2sizeTab[i] = sizeOf(sizeClass, directMemoryCacheAlignment);
227 }
228 return sizeIdx2sizeTab;
229 }
230
231 private static int calculateSize(int log2Group, int nDelta, int log2Delta) {
232 return (1 << log2Group) + (nDelta << log2Delta);
233 }
234
235 private static int sizeOf(short[] sizeClass, int directMemoryCacheAlignment) {
236 int log2Group = sizeClass[LOG2GROUP_IDX];
237 int log2Delta = sizeClass[LOG2DELTA_IDX];
238 int nDelta = sizeClass[NDELTA_IDX];
239
240 int size = calculateSize(log2Group, nDelta, log2Delta);
241
242 return alignSizeIfNeeded(size, directMemoryCacheAlignment);
243 }
244
245 private static int[] newPageIdx2sizeTab(short[][] sizeClasses, int nSizes, int nPSizes,
246 int directMemoryCacheAlignment) {
247 int[] pageIdx2sizeTab = new int[nPSizes];
248 int pageIdx = 0;
249 for (int i = 0; i < nSizes; i++) {
250 short[] sizeClass = sizeClasses[i];
251 if (sizeClass[PAGESIZE_IDX] == yes) {
252 pageIdx2sizeTab[pageIdx++] = sizeOf(sizeClass, directMemoryCacheAlignment);
253 }
254 }
255 return pageIdx2sizeTab;
256 }
257
258 private static int[] newSize2idxTab(int lookupMaxSize, short[][] sizeClasses) {
259 int[] size2idxTab = new int[lookupMaxSize >> LOG2_QUANTUM];
260 int idx = 0;
261 int size = 0;
262
263 for (int i = 0; size <= lookupMaxSize; i++) {
264 int log2Delta = sizeClasses[i][LOG2DELTA_IDX];
265 int times = 1 << log2Delta - LOG2_QUANTUM;
266
267 while (size <= lookupMaxSize && times-- > 0) {
268 size2idxTab[idx++] = i;
269 size = idx + 1 << LOG2_QUANTUM;
270 }
271 }
272 return size2idxTab;
273 }
274
275 @Override
276 public int sizeIdx2size(int sizeIdx) {
277 return sizeIdx2sizeTab[sizeIdx];
278 }
279
280 @Override
281 public int sizeIdx2sizeCompute(int sizeIdx) {
282 int group = sizeIdx >> LOG2_SIZE_CLASS_GROUP;
283 int mod = sizeIdx & (1 << LOG2_SIZE_CLASS_GROUP) - 1;
284
285 int groupSize = group == 0? 0 :
286 1 << LOG2_QUANTUM + LOG2_SIZE_CLASS_GROUP - 1 << group;
287
288 int shift = group == 0? 1 : group;
289 int lgDelta = shift + LOG2_QUANTUM - 1;
290 int modSize = mod + 1 << lgDelta;
291
292 return groupSize + modSize;
293 }
294
295 @Override
296 public long pageIdx2size(int pageIdx) {
297 return pageIdx2sizeTab[pageIdx];
298 }
299
300 @Override
301 public long pageIdx2sizeCompute(int pageIdx) {
302 int group = pageIdx >> LOG2_SIZE_CLASS_GROUP;
303 int mod = pageIdx & (1 << LOG2_SIZE_CLASS_GROUP) - 1;
304
305 long groupSize = group == 0? 0 :
306 1L << pageShifts + LOG2_SIZE_CLASS_GROUP - 1 << group;
307
308 int shift = group == 0? 1 : group;
309 int log2Delta = shift + pageShifts - 1;
310 int modSize = mod + 1 << log2Delta;
311
312 return groupSize + modSize;
313 }
314
315 @Override
316 public int size2SizeIdx(int size) {
317 if (size == 0) {
318 return 0;
319 }
320 if (size > chunkSize) {
321 return nSizes;
322 }
323
324 size = alignSizeIfNeeded(size, directMemoryCacheAlignment);
325
326 if (size <= lookupMaxSize) {
327 //size-1 / MIN_TINY
328 return size2idxTab[size - 1 >> LOG2_QUANTUM];
329 }
330
331 int x = log2((size << 1) - 1);
332 int shift = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
333 ? 0 : x - (LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM);
334
335 int group = shift << LOG2_SIZE_CLASS_GROUP;
336
337 int log2Delta = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
338 ? LOG2_QUANTUM : x - LOG2_SIZE_CLASS_GROUP - 1;
339
340 int mod = size - 1 >> log2Delta & (1 << LOG2_SIZE_CLASS_GROUP) - 1;
341
342 return group + mod;
343 }
344
345 @Override
346 public int pages2pageIdx(int pages) {
347 return pages2pageIdxCompute(pages, false);
348 }
349
350 @Override
351 public int pages2pageIdxFloor(int pages) {
352 return pages2pageIdxCompute(pages, true);
353 }
354
355 private int pages2pageIdxCompute(int pages, boolean floor) {
356 int pageSize = pages << pageShifts;
357 if (pageSize > chunkSize) {
358 return nPSizes;
359 }
360
361 int x = log2((pageSize << 1) - 1);
362
363 int shift = x < LOG2_SIZE_CLASS_GROUP + pageShifts
364 ? 0 : x - (LOG2_SIZE_CLASS_GROUP + pageShifts);
365
366 int group = shift << LOG2_SIZE_CLASS_GROUP;
367
368 int log2Delta = x < LOG2_SIZE_CLASS_GROUP + pageShifts + 1?
369 pageShifts : x - LOG2_SIZE_CLASS_GROUP - 1;
370
371 int mod = pageSize - 1 >> log2Delta & (1 << LOG2_SIZE_CLASS_GROUP) - 1;
372
373 int pageIdx = group + mod;
374
375 if (floor && pageIdx2sizeTab[pageIdx] > pages << pageShifts) {
376 pageIdx--;
377 }
378
379 return pageIdx;
380 }
381
382 // Round size up to the nearest multiple of alignment.
383 private static int alignSizeIfNeeded(int size, int directMemoryCacheAlignment) {
384 if (directMemoryCacheAlignment <= 0) {
385 return size;
386 }
387 int delta = size & directMemoryCacheAlignment - 1;
388 return delta == 0? size : size + directMemoryCacheAlignment - delta;
389 }
390
391 @Override
392 public int normalizeSize(int size) {
393 if (size == 0) {
394 return sizeIdx2sizeTab[0];
395 }
396 size = alignSizeIfNeeded(size, directMemoryCacheAlignment);
397 if (size <= lookupMaxSize) {
398 int ret = sizeIdx2sizeTab[size2idxTab[size - 1 >> LOG2_QUANTUM]];
399 assert ret == normalizeSizeCompute(size);
400 return ret;
401 }
402 return normalizeSizeCompute(size);
403 }
404
405 private static int normalizeSizeCompute(int size) {
406 int x = log2((size << 1) - 1);
407 int log2Delta = x < LOG2_SIZE_CLASS_GROUP + LOG2_QUANTUM + 1
408 ? LOG2_QUANTUM : x - LOG2_SIZE_CLASS_GROUP - 1;
409 int delta = 1 << log2Delta;
410 int delta_mask = delta - 1;
411 return size + delta_mask & ~delta_mask;
412 }
413 }
以上源码来自： 即时通讯网 - 即时通讯开发者社区！