jemalloc 深入分析 之Region size 设计以及和 index 对应关系

6. Region size 设计以及和 index 对应关系
   6.1. Region size步长的设计
   下图是对于从reg_size=64开始的增加规则，可以看出步长增加规则是每次在相邻幂次数位加1，得到下一个reg_size值。
   

6.2. Region相关的参数定义（anrdoid 64bits）
以下配置是对应于如下的系统参数： (LG_SIZEOF_PTR == 3 && LG_TINY_MIN == 3 && LG_QUANTUM == 4 && LG_PAGE == 12)
#define NTBINS 1
#define NLBINS 29
#define NBINS 36
#define NSIZES 232
#define NPSIZES 199
#define LG_TINY_MAXCLASS 3
#define LOOKUP_MAXCLASS ((((size_t)1) << 11) + (((size_t)4) << 9))
#define SMALL_MAXCLASS ((((size_t)1) << 13) + (((size_t)3) << 11))
#define LG_LARGE_MINCLASS 14
#define HUGE_MAXCLASS ((((size_t)1) << 62) + (((size_t)3) << 60))
6.3. SIZE_CLASSES 定义
#define SIZE_CLASSES
/* index, lg_grp, lg_delta, ndelta, psz, bin, lg_delta_lookup /
SC( 0, 3, 3, 0, no, yes, 3)

SC( 1, 3, 3, 1, no, yes, 3)
SC( 2, 4, 4, 1, no, yes, 4)
SC( 3, 4, 4, 2, no, yes, 4)
SC( 4, 4, 4, 3, no, yes, 4)

SC( 5, 6, 4, 1, no, yes, 4)
SC( 6, 6, 4, 2, no, yes, 4)
SC( 7, 6, 4, 3, no, yes, 4)
SC( 8, 6, 4, 4, no, yes, 4)

SC( 9, 7, 5, 1, no, yes, 5)
SC( 10, 7, 5, 2, no, yes, 5)
SC( 11, 7, 5, 3, no, yes, 5)
SC( 12, 7, 5, 4, no, yes, 5)

SC( 13, 8, 6, 1, no, yes, 6)
SC( 14, 8, 6, 2, no, yes, 6)
SC( 15, 8, 6, 3, no, yes, 6)
SC( 16, 8, 6, 4, no, yes, 6)

SC( 17, 9, 7, 1, no, yes, 7)
SC( 18, 9, 7, 2, no, yes, 7)
SC( 19, 9, 7, 3, no, yes, 7)
SC( 20, 9, 7, 4, no, yes, 7)

SC( 21, 10, 8, 1, no, yes, 8)
SC( 22, 10, 8, 2, no, yes, 8)
SC( 23, 10, 8, 3, no, yes, 8)
SC( 24, 10, 8, 4, no, yes, 8)

SC( 25, 11, 9, 1, no, yes, 9)
SC( 26, 11, 9, 2, no, yes, 9)
SC( 27, 11, 9, 3, no, yes, 9)
SC( 28, 11, 9, 4, yes, yes, 9)

SC( 29, 12, 10, 1, no, yes, no)
SC( 30, 12, 10, 2, no, yes, no)
SC( 31, 12, 10, 3, no, yes, no)
SC( 32, 12, 10, 4, yes, yes, no)

SC( 33, 13, 11, 1, no, yes, no)
SC( 34, 13, 11, 2, yes, yes, no) \
SC( 35, 13, 11, 3, no, yes, no) \ //small max
SC( 36, 13, 11, 4, yes, no, no) \ //large start = 2^14

SC( 37, 14, 12, 1, yes, no, no)
SC( 38, 14, 12, 2, yes, no, no)
SC( 39, 14, 12, 3, yes, no, no)
SC( 40, 14, 12, 4, yes, no, no)

SC( 41, 15, 13, 1, yes, no, no)
SC( 42, 15, 13, 2, yes, no, no)
SC( 43, 15, 13, 3, yes, no, no)
SC( 44, 15, 13, 4, yes, no, no)

SC( 45, 16, 14, 1, yes, no, no)
SC( 46, 16, 14, 2, yes, no, no)
SC( 47, 16, 14, 3, yes, no, no)
SC( 48, 16, 14, 4, yes, no, no)

SC( 49, 17, 15, 1, yes, no, no)
SC( 50, 17, 15, 2, yes, no, no)
SC( 51, 17, 15, 3, yes, no, no)
SC( 52, 17, 15, 4, yes, no, no)

SC( 53, 18, 16, 1, yes, no, no)
SC( 54, 18, 16, 2, yes, no, no)
SC( 55, 18, 16, 3, yes, no, no)
SC( 56, 18, 16, 4, yes, no, no)

SC( 57, 19, 17, 1, yes, no, no)
SC( 58, 19, 17, 2, yes, no, no)
SC( 59, 19, 17, 3, yes, no, no)
SC( 60, 19, 17, 4, yes, no, no)

SC( 61, 20, 18, 1, yes, no, no)
SC( 62, 20, 18, 2, yes, no, no)
SC( 63, 20, 18, 3, yes, no, no)
SC( 64, 20, 18, 4, yes, no, no)

SC( 65, 21, 19, 1, yes, no, no)
SC( 66, 21, 19, 2, yes, no, no)
SC( 67, 21, 19, 3, yes, no, no)
SC( 68, 21, 19, 4, yes, no, no)

SC( 69, 22, 20, 1, yes, no, no)
SC( 70, 22, 20, 2, yes, no, no)
SC( 71, 22, 20, 3, yes, no, no)
SC( 72, 22, 20, 4, yes, no, no)

SC( 73, 23, 21, 1, yes, no, no)
SC( 74, 23, 21, 2, yes, no, no)
SC( 75, 23, 21, 3, yes, no, no)
SC( 76, 23, 21, 4, yes, no, no)

SC( 77, 24, 22, 1, yes, no, no)
SC( 78, 24, 22, 2, yes, no, no)
SC( 79, 24, 22, 3, yes, no, no)
SC( 80, 24, 22, 4, yes, no, no)

SC( 81, 25, 23, 1, yes, no, no)
SC( 82, 25, 23, 2, yes, no, no)
SC( 83, 25, 23, 3, yes, no, no)
SC( 84, 25, 23, 4, yes, no, no)

SC( 85, 26, 24, 1, yes, no, no)
SC( 86, 26, 24, 2, yes, no, no)
SC( 87, 26, 24, 3, yes, no, no)
SC( 88, 26, 24, 4, yes, no, no)

SC( 89, 27, 25, 1, yes, no, no)
SC( 90, 27, 25, 2, yes, no, no)
SC( 91, 27, 25, 3, yes, no, no)
SC( 92, 27, 25, 4, yes, no, no)

SC( 93, 28, 26, 1, yes, no, no)
SC( 94, 28, 26, 2, yes, no, no)
SC( 95, 28, 26, 3, yes, no, no)
SC( 96, 28, 26, 4, yes, no, no)

SC( 97, 29, 27, 1, yes, no, no)
SC( 98, 29, 27, 2, yes, no, no)
SC( 99, 29, 27, 3, yes, no, no)
SC(100, 29, 27, 4, yes, no, no)

SC(101, 30, 28, 1, yes, no, no)
SC(102, 30, 28, 2, yes, no, no)
SC(103, 30, 28, 3, yes, no, no)
SC(104, 30, 28, 4, yes, no, no)

SC(105, 31, 29, 1, yes, no, no)
SC(106, 31, 29, 2, yes, no, no)
SC(107, 31, 29, 3, yes, no, no)
SC(108, 31, 29, 4, yes, no, no)

SC(109, 32, 30, 1, yes, no, no)
SC(110, 32, 30, 2, yes, no, no)
SC(111, 32, 30, 3, yes, no, no)
SC(112, 32, 30, 4, yes, no, no)

SC(113, 33, 31, 1, yes, no, no)
SC(114, 33, 31, 2, yes, no, no)
SC(115, 33, 31, 3, yes, no, no)
SC(116, 33, 31, 4, yes, no, no)

SC(117, 34, 32, 1, yes, no, no)
SC(118, 34, 32, 2, yes, no, no)
SC(119, 34, 32, 3, yes, no, no)
SC(120, 34, 32, 4, yes, no, no)

SC(121, 35, 33, 1, yes, no, no)
SC(122, 35, 33, 2, yes, no, no)
SC(123, 35, 33, 3, yes, no, no)
SC(124, 35, 33, 4, yes, no, no)

SC(125, 36, 34, 1, yes, no, no)
SC(126, 36, 34, 2, yes, no, no)
SC(127, 36, 34, 3, yes, no, no)
SC(128, 36, 34, 4, yes, no, no)

SC(129, 37, 35, 1, yes, no, no)
SC(130, 37, 35, 2, yes, no, no)
SC(131, 37, 35, 3, yes, no, no)
SC(132, 37, 35, 4, yes, no, no)

SC(133, 38, 36, 1, yes, no, no)
SC(134, 38, 36, 2, yes, no, no)
SC(135, 38, 36, 3, yes, no, no)
SC(136, 38, 36, 4, yes, no, no)

SC(137, 39, 37, 1, yes, no, no)
SC(138, 39, 37, 2, yes, no, no)
SC(139, 39, 37, 3, yes, no, no)
SC(140, 39, 37, 4, yes, no, no)

SC(141, 40, 38, 1, yes, no, no)
SC(142, 40, 38, 2, yes, no, no)
SC(143, 40, 38, 3, yes, no, no)
SC(144, 40, 38, 4, yes, no, no)

SC(145, 41, 39, 1, yes, no, no)
SC(146, 41, 39, 2, yes, no, no)
SC(147, 41, 39, 3, yes, no, no)
SC(148, 41, 39, 4, yes, no, no)

SC(149, 42, 40, 1, yes, no, no)
SC(150, 42, 40, 2, yes, no, no)
SC(151, 42, 40, 3, yes, no, no)
SC(152, 42, 40, 4, yes, no, no)

SC(153, 43, 41, 1, yes, no, no)
SC(154, 43, 41, 2, yes, no, no)
SC(155, 43, 41, 3, yes, no, no)
SC(156, 43, 41, 4, yes, no, no)

SC(157, 44, 42, 1, yes, no, no)
SC(158, 44, 42, 2, yes, no, no)
SC(159, 44, 42, 3, yes, no, no)
SC(160, 44, 42, 4, yes, no, no)

SC(161, 45, 43, 1, yes, no, no)
SC(162, 45, 43, 2, yes, no, no)
SC(163, 45, 43, 3, yes, no, no)
SC(164, 45, 43, 4, yes, no, no)

SC(165, 46, 44, 1, yes, no, no)
SC(166, 46, 44, 2, yes, no, no)
SC(167, 46, 44, 3, yes, no, no)
SC(168, 46, 44, 4, yes, no, no)

SC(169, 47, 45, 1, yes, no, no)
SC(170, 47, 45, 2, yes, no, no)
SC(171, 47, 45, 3, yes, no, no)
SC(172, 47, 45, 4, yes, no, no)

SC(173, 48, 46, 1, yes, no, no)
SC(174, 48, 46, 2, yes, no, no)
SC(175, 48, 46, 3, yes, no, no)
SC(176, 48, 46, 4, yes, no, no)

SC(177, 49, 47, 1, yes, no, no)
SC(178, 49, 47, 2, yes, no, no)
SC(179, 49, 47, 3, yes, no, no)
SC(180, 49, 47, 4, yes, no, no)

SC(181, 50, 48, 1, yes, no, no)
SC(182, 50, 48, 2, yes, no, no)
SC(183, 50, 48, 3, yes, no, no)
SC(184, 50, 48, 4, yes, no, no)

SC(185, 51, 49, 1, yes, no, no)
SC(186, 51, 49, 2, yes, no, no)
SC(187, 51, 49, 3, yes, no, no)
SC(188, 51, 49, 4, yes, no, no)

SC(189, 52, 50, 1, yes, no, no)
SC(190, 52, 50, 2, yes, no, no)
SC(191, 52, 50, 3, yes, no, no)
SC(192, 52, 50, 4, yes, no, no)

SC(193, 53, 51, 1, yes, no, no)
SC(194, 53, 51, 2, yes, no, no)
SC(195, 53, 51, 3, yes, no, no)
SC(196, 53, 51, 4, yes, no, no)

SC(197, 54, 52, 1, yes, no, no)
SC(198, 54, 52, 2, yes, no, no)
SC(199, 54, 52, 3, yes, no, no)
SC(200, 54, 52, 4, yes, no, no)

SC(201, 55, 53, 1, yes, no, no)
SC(202, 55, 53, 2, yes, no, no)
SC(203, 55, 53, 3, yes, no, no)
SC(204, 55, 53, 4, yes, no, no)

SC(205, 56, 54, 1, yes, no, no)
SC(206, 56, 54, 2, yes, no, no)
SC(207, 56, 54, 3, yes, no, no)
SC(208, 56, 54, 4, yes, no, no)

SC(209, 57, 55, 1, yes, no, no)
SC(210, 57, 55, 2, yes, no, no)
SC(211, 57, 55, 3, yes, no, no)
SC(212, 57, 55, 4, yes, no, no)

SC(213, 58, 56, 1, yes, no, no)
SC(214, 58, 56, 2, yes, no, no)
SC(215, 58, 56, 3, yes, no, no)
SC(216, 58, 56, 4, yes, no, no)

SC(217, 59, 57, 1, yes, no, no)
SC(218, 59, 57, 2, yes, no, no)
SC(219, 59, 57, 3, yes, no, no)
SC(220, 59, 57, 4, yes, no, no)

SC(221, 60, 58, 1, yes, no, no)
SC(222, 60, 58, 2, yes, no, no)
SC(223, 60, 58, 3, yes, no, no)
SC(224, 60, 58, 4, yes, no, no)

SC(225, 61, 59, 1, yes, no, no)
SC(226, 61, 59, 2, yes, no, no)
SC(227, 61, 59, 3, yes, no, no)
SC(228, 61, 59, 4, yes, no, no)

SC(229, 62, 60, 1, yes, no, no)
SC(230, 62, 60, 2, yes, no, no)
SC(231, 62, 60, 3, yes, no, no)
6.4. size2index_tab （用于reg_size 小于4096的快速查找）
/

• size2index_tab is a compact lookup table that rounds request sizes up to
• size classes. In order to reduce cache footprint, the table is compressed,
• and all accesses are via size2index().
  /
  对于LG_TINY_MIN=3化简后的size2index_tab定义如下：
  const uint8_t size2index_tab[] = {
  #define S2B_3(i) i,
  #define S2B_4(i) S2B_3(i) S2B_3(i)
  #define S2B_5(i) S2B_4(i) S2B_4(i)
  #define S2B_6(i) S2B_5(i) S2B_5(i)
  #define S2B_7(i) S2B_6(i) S2B_6(i)
  #define S2B_8(i) S2B_7(i) S2B_7(i)
  #define S2B_9(i) S2B_8(i) S2B_8(i)
  #define S2B_no(i)
  #define SC(index, lg_grp, lg_delta, ndelta, psz, bin, lg_delta_lookup)
  S2B_##lg_delta_lookup(index)
  SIZE_CLASSES
  };
  下面是SIZE_CLASSES定义，根据这个生成常量数组。
  SC( 0, 3, 3, 0, no, yes, 3)
  
  SC( 1, 3, 3, 1, no, yes, 3)
  SC( 2, 4, 4, 1, no, yes, 4)
  SC( 3, 4, 4, 2, no, yes, 4)
  SC( 4, 4, 4, 3, no, yes, 4)
  
  SC( 5, 6, 4, 1, no, yes, 4)
  SC( 6, 6, 4, 2, no, yes, 4)
  SC( 7, 6, 4, 3, no, yes, 4)
  SC( 8, 6, 4, 4, no, yes, 4)
  
  SC( 9, 7, 5, 1, no, yes, 5)
  SC( 10, 7, 5, 2, no, yes, 5)
  SC( 11, 7, 5, 3, no, yes, 5)
  SC( 12, 7, 5, 4, no, yes, 5)
  
  SC( 13, 8, 6, 1, no, yes, 6)
  SC( 14, 8, 6, 2, no, yes, 6)
  SC( 15, 8, 6, 3, no, yes, 6)
  SC( 16, 8, 6, 4, no, yes, 6)
  
  SC( 17, 9, 7, 1, no, yes, 7)
  SC( 18, 9, 7, 2, no, yes, 7)
  SC( 19, 9, 7, 3, no, yes, 7)
  SC( 20, 9, 7, 4, no, yes, 7)
  
  SC( 21, 10, 8, 1, no, yes, 8)
  SC( 22, 10, 8, 2, no, yes, 8)
  SC( 23, 10, 8, 3, no, yes, 8)
  SC( 24, 10, 8, 4, no, yes, 8)
  
  SC( 25, 11, 9, 1, no, yes, 9)
  SC( 26, 11, 9, 2, no, yes, 9)
  SC( 27, 11, 9, 3, no, yes, 9)
  SC( 28, 11, 9, 4, yes, yes, 9)
  const uint8_t size2index_tab[] = {
  S2B_3(0) S2B_3(1) S2B_4(2) S2B_4(3) S2B_4(4) S2B_4(5) S2B_4(6) S2B_4(7) S2B_4(8) S2B_5(9) S2B_5(10) S2B_5(11) S2B_5(12) S2B_6(13) S2B_6(14) S2B_6(15) S2B_6(16) S2B_7(17) S2B_7(18) S2B_7(19) S2B_7(20) S2B_8(21) S2B_8(22) S2B_8(23) S2B_8(24) S2B_9(25) S2B_9(26) S2B_9(27) S2B_9(28)
  }
  const uint8_t size2index_tab[] = {
  0, 1, 2, 2, 3,3, 4,4, 5,5, 6,6, 7,7, 8,8, 9,9,9,9, 10,10,10,10, 11,11,11,11, 12,12,12,12, 13,13,13,13,13,13,13,13, 14,14,14,14,14,14,14,14, …
  }
  因为后续步长拉大，而size2index_tab按8个字节设置一个索引。所以越后面重复的index会越多。最大索引是4096，4096/8=512。所以size2index_tab数组个数为512。
  (gdb) p /d je_size2index_tab
  $87 = {0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10,
  10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14,
  14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16,
  16, 16, 16, 16, 17 <repeats 16 times>, 18 <repeats 16 times>,
  19 <repeats 16 times>, 20 <repeats 16 times>, 21 <repeats 32 times>,
  22 <repeats 32 times>, 23 <repeats 32 times>, 24 <repeats 32 times>,
  25 <repeats 64 times>, 26 <repeats 64 times>, 27 <repeats 64 times>,
  28 <repeats 64 times>}
  6.5. size2index_compute的计算过程
  lg_floor(size_t x)
  {
  size_t ret;
  assert(x != 0);
  asm (“bsr %1, %0”
  : “=r”(ret) // Outputs.
  : “r”(x) // Inputs.
  );
  assert(ret < UINT_MAX);
  return ((unsigned)ret);
  }
  BSR scans the bits in the second word or doubleword operand from the most significant bit to the least significant bit. The ZF flag is cleared if the bits are all 0; otherwise, ZF is set and the destination register is loaded with the bit index of the first set bit found when scanning in the reverse direction.
  lg_floor找到x的二进制表示，最高位1是第几个数，从右开始，从0开始计数。
  JEMALLOC_INLINE szind_t
  size2index_compute(size_t size)
  {
  if (unlikely(size > HUGE_MAXCLASS))
  return (NSIZES);
  #if (NTBINS != 0)
  if (size <= (ZU(1) << LG_TINY_MAXCLASS)) {
  szind_t lg_tmin = LG_TINY_MAXCLASS - NTBINS + 1;
  szind_t lg_ceil = lg_floor(pow2_ceil_zu(size));
  return (lg_ceil < lg_tmin ? 0 : lg_ceil - lg_tmin);
  }
  #endif
  {
  szind_t x = lg_floor((size<<1)-1);
  szind_t shift = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM) ? 0 :
  x - (LG_SIZE_CLASS_GROUP + LG_QUANTUM);
  szind_t grp = shift << LG_SIZE_CLASS_GROUP;
  szind_t lg_delta = (x < LG_SIZE_CLASS_GROUP + LG_QUANTUM + 1)
  ? LG_QUANTUM : x - LG_SIZE_CLASS_GROUP - 1;
  size_t delta_inverse_mask = ZI(-1) << lg_delta;
  szind_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) &
  ((ZU(1) << LG_SIZE_CLASS_GROUP) - 1);
  szind_t index = NTBINS + grp + mod;
  return (index);
  }
  }
  size2index_compute计算过程如下：
  szind_t x = lg_floor((size<<1)-1);
  //lg_floor找到输入参数的二进制表示，最高位1是第几个数，从右开始，从0开始计数。
  // lg_floor((size<<1)-1);和size的关系？如果size是2的幂次，则x就是size中1的最高位，如果size不是2的幂次，那么x是size中1的最高位+1。所以这里把2的幂次的size放到了上一个group，然后通过mod的计算，2的幂次的size的mod为3，比其他的上一个group的其他size的index都要大。（为什么这么处理呢？因为2的幂次的size的递增的步长和上一个group一样，所以需要这么处理。）如下图所示：
  
  szind_t shift = (x < LG_SIZE_CLASS_GROUP=2 + LG_QUANTUM=4) ? 0 :
  x - (LG_SIZE_CLASS_GROUP=2 + LG_QUANTUM=4); shift=x<6?0:x-6
  szind_t grp = shift << LG_SIZE_CLASS_GROUP=2; grp=shift4
  szind_t lg_delta = (x < LG_SIZE_CLASS_GROUP=2 + LG_QUANTUM=4 + 1)
  ? LG_QUANTUM=4 : x - LG_SIZE_CLASS_GROUP - 1;

lg_delta=(x<7)?4:x-3
size_t delta_inverse_mask = ZI(-1) << lg_delta;
szind_t mod = ((((size-1) & delta_inverse_mask) >> lg_delta)) &
((ZU(1) << LG_SIZE_CLASS_GROUP) - 1); Mod=((((size-1) & delta_inverse_mask) >> lg_delta)) & 0x11
如果size是2的幂次，则size-1是低位全1的一个数，从reg_size从80开始（size从128开始）lg_delta=3，delta_inverse_mask=0xFFFFFFFFFFFFFFF8，这个时候size-1至少是7位，除去低3位，还有4位全1，所以和0x11取与后为3。
如果size是非2的幂次，mod计算结果是0，1，2中的一种。
szind_t index = NTBINS=1 + grp + mod;
return (index);

6.6. index2size_compute的计算过程
index2size_compute(szind_t index)
{
#if (NTBINS > 0)
if (index < NTBINS)
return (ZU(1) << (LG_TINY_MAXCLASS - NTBINS + 1 + index));
#endif
{
size_t reduced_index = index - NTBINS;
size_t grp = reduced_index >> LG_SIZE_CLASS_GROUP;
size_t mod = reduced_index & ((ZU(1) << LG_SIZE_CLASS_GROUP) -
1);
size_t grp_size_mask = ~((!!grp)-1);
size_t grp_size = ((ZU(1) << (LG_QUANTUM +
(LG_SIZE_CLASS_GROUP-1))) << grp) & grp_size_mask;
size_t shift = (grp == 0) ? 1 : grp;
size_t lg_delta = shift + (LG_QUANTUM-1);
size_t mod_size = (mod+1) << lg_delta;
size_t usize = grp_size + mod_size;
return (usize);
}
}
index2size_compute计算过程如下：
size_t reduced_index = index – NTBINS=1;
size_t grp = reduced_index >> LG_SIZE_CLASS_GROUP=2;
size_t mod = reduced_index & ((ZU(1) << LG_SIZE_CLASS_GROUP=2) -
1);
size_t grp_size_mask = ~((!!grp)-1);
size_t grp_size = ((ZU(1) << (LG_QUANTUM +
(LG_SIZE_CLASS_GROUP-1))) << grp) & grp_size_mask;
size_t shift = (grp == 0) ? 1 : grp;
size_t lg_delta = shift + (LG_QUANTUM-1);
size_t mod_size = (mod+1) << lg_delta;
size_t usize = grp_size + mod_size;
return (usize);
index=0,由第一个if (index < NTBINS) 这里算出，因为NTBINS=1，1<<3=8
index=1-4时，reduced_index=0-3，grp=0，mod= reduced_index & 3 = 0-3
grp_size_mask=0x0，grp_size=(1<<5)&0x0=0, shift=1, lg_delta=4,
mod_size=(1-4)<<4=16,32,48,64 usize=0+ mod_size= mod_size=16,32,48,64
index>=5时，reduced_index>=4, grp= reduced_index/4,
mod= reduced_index&0x3=0-3 grp_size_mask=0xffffffff，
grp_size=((1<<5)<<grp)& 0xffffffff=(32<<grp) & 0xffffffff
shift=grp，lg_delta=grp+3，mod_size=(mod+1) << lg_delta=(1-4)<<(grp+3) usize = grp_size + mod_size=(32<<grp) & 0xffffffff+(1-4)<<(grp+3)
=(1<<(grp+5))+(1-4)<<(grp+3) (grp=(index-1)/4) =(1<<lg_grp + ndelta<<lg_delta) lg_grp=grp+5, lg_delta=grp+3 这个就是grp和index2size_tab中的lg_grp和lg_delta的对应关系，也说明了这两个值为什么一直相差2。
index lg_grp lg_delta SC( 5, 6, 4, 1, no, yes, 4) \ //grp=1
SC( 6, 6, 4, 2, no, yes, 4) \ //grp=1
SC( 7, 6, 4, 3, no, yes, 4) \ //grp=1
SC( 8, 6, 4, 4, no, yes, 4) \ //grp=1
\ SC( 9, 7, 5, 1, no, yes, 5) \ //grp=2
SC( 10, 7, 5, 2, no, yes, 5) \ //grp=2
SC( 11, 7, 5, 3, no, yes, 5) \ //grp=2
SC( 12, 7, 5, 4, no, yes, 5) \ //grp=2
6.7. 步长增加规律分析-浪费率控制
步长=2^(lg_delta)=2(grp+3)
区间上限=2^(grp+5)+4*2(grp+3)= 2^(grp+5)+2(grp+5)=2^(grp+6)
区间下限=2^(grp+5)+1*2(grp+3)= 2^(grp+5)+2(grp+3)
所以可以得到步长和区间上限的比值为：2^(grp+3)/ 2^(grp+6)=1/8
步长和区间下限的比值为：2^(grp+3)/ (2^(grp+5)+2(grp+3))=1/5
主要原则就是保证内存浪费率控制1/5内。
6.8. index2size_tab
/*

• index2size_tab encodes the same information as could be computed (at
• unacceptable cost in some code paths) by index2size_compute().
  */
  extern size_t const index2size_tab[NSIZES];
  const size_t index2size_tab[NSIZES] = {
  #define SC(index, lg_grp, lg_delta, ndelta, psz, bin, lg_delta_lookup) \ ((ZU(1)<<lg_grp) + (ZU(ndelta)<<lg_delta)),
  SIZE_CLASSES
  #undef SC
  };
  (gdb) p je_index2size_tab
  $57 = {8, 16, 32, 48, 64, 80, 96, 112, 128, 160, 192, 224, 256, 320, 384,
  448, 512, 640, 768, 896, 1024, 1280, 1536, 1792, 2048, 2560, 3072, 3584, 4096, 5120, 6144, 7168, 8192, 10240, 12288, 14336, 16384, 20480, 24576, 28672, 32768, 40960, 49152, 57344, 65536, 81920, 98304, 114688, 131072,
  163840, 196608, 229376, 262144, 327680, 393216, 458752, 524288, 655360, 786432, 917504, 1048576, 1310720, 1572864, 1835008, 2097152, 2621440,
  3145728, 3670016, 4194304, 5242880, 6291456, 7340032, 8388608, 10485760,
  12582912, 14680064, 16777216, 20971520, 25165824, 29360128, 33554432,
  41943040, 50331648, 58720256, 67108864, 83886080, 100663296, 117440512,
  134217728, 167772160, 201326592, 234881024, 268435456, 335544320,
  402653184, 469762048, 536870912, 671088640, 805306368, 939524096,
  1073741824, 1342177280, 1610612736, 1879048192, 2147483648, 2684354560,
  3221225472, 3758096384, 4294967296, 5368709120, 6442450944, 7516192768,
  8589934592, 10737418240, 12884901888, 15032385536, 17179869184,
  21474836480, 25769803776, 30064771072, 34359738368, 42949672960,
  51539607552, 60129542144, 68719476736, 85899345920, 103079215104,
  120259084288, 137438953472, 171798691840, 206158430208, 240518168576,
  274877906944, 343597383680, 412316860416, 481036337152, 549755813888,
  687194767360, 824633720832, 962072674304, 1099511627776, 1374389534720,
  1649267441664, 1924145348608, 2199023255552, 2748779069440, 3298534883328,
  3848290697216, 4398046511104, 5497558138880, 6597069766656, 7696581394432,
  8796093022208, 10995116277760, 13194139533312, 15393162788864,
  17592186044416, 21990232555520, 26388279066624, 30786325577728,
  35184372088832, 43980465111040, 52776558133248, 61572651155456,
  70368744177664, 87960930222080, 105553116266496, 123145302310912,
  140737488355328, 175921860444160, 211106232532992, 246290604621824,
  281474976710656, 351843720888320, 422212465065984, 492581209243648,
  562949953421312, 703687441776640, 844424930131968, 985162418487296,
  1125899906842624, 1407374883553280, 1688849860263936, 1970324836974592,
  2251799813685248, 2814749767106560, 3377699720527872, 3940649673949184,
  4503599627370496, 5629499534213120, 6755399441055744, 7881299347898368,
  9007199254740992, 11258999068426240, 13510798882111488, 15762598695796736,
  18014398509481984, 22517998136852480, 27021597764222976,
  31525197391593472…}
  (gdb)

详细文章请参考：《jemalloc 深入分析》https://download.****.net/download/ip5108/10941278