1 #!/bin/sh 2 3 # The following limits are chosen such that they cover all supported platforms. 4 5 # Pointer sizes. 6 lg_zarr="2 3" 7 8 # Quanta. 9 lg_qarr="3 4" 10 11 # The range of tiny size classes is [2^lg_tmin..2^(lg_q-1)]. 12 lg_tmin=3 13 14 # Maximum lookup size. 15 lg_kmax=12 16 17 # Page sizes. 18 lg_parr="12 13 16" 19 20 # Size class group size (number of size classes for each size doubling). 21 lg_g=2 22 23 pow2() { 24 e=$1 25 pow2_result=1 26 while [ ${e} -gt 0 ] ; do 27 pow2_result=$((${pow2_result} + ${pow2_result})) 28 e=$((${e} - 1)) 29 done 30 } 31 32 lg() { 33 x=$1 34 lg_result=0 35 while [ ${x} -gt 1 ] ; do 36 lg_result=$((${lg_result} + 1)) 37 x=$((${x} / 2)) 38 done 39 } 40 41 size_class() { 42 index=$1 43 lg_grp=$2 44 lg_delta=$3 45 ndelta=$4 46 lg_p=$5 47 lg_kmax=$6 48 49 lg ${ndelta}; lg_ndelta=${lg_result}; pow2 ${lg_ndelta} 50 if [ ${pow2_result} -lt ${ndelta} ] ; then 51 rem="yes" 52 else 53 rem="no" 54 fi 55 56 lg_size=${lg_grp} 57 if [ $((${lg_delta} + ${lg_ndelta})) -eq ${lg_grp} ] ; then 58 lg_size=$((${lg_grp} + 1)) 59 else 60 lg_size=${lg_grp} 61 rem="yes" 62 fi 63 64 if [ ${lg_size} -lt ${lg_p} ] ; then 65 bin="yes" 66 else 67 bin="no" 68 fi 69 if [ ${lg_size} -lt ${lg_kmax} \ 70 -o ${lg_size} -eq ${lg_kmax} -a ${rem} = "no" ] ; then 71 lg_delta_lookup=${lg_delta} 72 else 73 lg_delta_lookup="no" 74 fi 75 printf ' SC(%3d, %6d, %8d, %6d, %3s, %2s) \\\n' ${index} ${lg_grp} ${lg_delta} ${ndelta} ${bin} ${lg_delta_lookup} 76 # Defined upon return: 77 # - lg_delta_lookup (${lg_delta} or "no") 78 # - bin ("yes" or "no") 79 } 80 81 sep_line() { 82 echo " \\" 83 } 84 85 size_classes() { 86 lg_z=$1 87 lg_q=$2 88 lg_t=$3 89 lg_p=$4 90 lg_g=$5 91 92 pow2 $((${lg_z} + 3)); ptr_bits=${pow2_result} 93 pow2 ${lg_g}; g=${pow2_result} 94 95 echo "#define SIZE_CLASSES \\" 96 echo " /* index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup */ \\" 97 98 ntbins=0 99 nlbins=0 100 lg_tiny_maxclass='"NA"' 101 nbins=0 102 103 # Tiny size classes. 104 ndelta=0 105 index=0 106 lg_grp=${lg_t} 107 lg_delta=${lg_grp} 108 while [ ${lg_grp} -lt ${lg_q} ] ; do 109 size_class ${index} ${lg_grp} ${lg_delta} ${ndelta} ${lg_p} ${lg_kmax} 110 if [ ${lg_delta_lookup} != "no" ] ; then 111 nlbins=$((${index} + 1)) 112 fi 113 if [ ${bin} != "no" ] ; then 114 nbins=$((${index} + 1)) 115 fi 116 ntbins=$((${ntbins} + 1)) 117 lg_tiny_maxclass=${lg_grp} # Final written value is correct. 118 index=$((${index} + 1)) 119 lg_delta=${lg_grp} 120 lg_grp=$((${lg_grp} + 1)) 121 done 122 123 # First non-tiny group. 124 if [ ${ntbins} -gt 0 ] ; then 125 sep_line 126 # The first size class has an unusual encoding, because the size has to be 127 # split between grp and delta*ndelta. 128 lg_grp=$((${lg_grp} - 1)) 129 ndelta=1 130 size_class ${index} ${lg_grp} ${lg_delta} ${ndelta} ${lg_p} ${lg_kmax} 131 index=$((${index} + 1)) 132 lg_grp=$((${lg_grp} + 1)) 133 lg_delta=$((${lg_delta} + 1)) 134 fi 135 while [ ${ndelta} -lt ${g} ] ; do 136 size_class ${index} ${lg_grp} ${lg_delta} ${ndelta} ${lg_p} ${lg_kmax} 137 index=$((${index} + 1)) 138 ndelta=$((${ndelta} + 1)) 139 done 140 141 # All remaining groups. 142 lg_grp=$((${lg_grp} + ${lg_g})) 143 while [ ${lg_grp} -lt ${ptr_bits} ] ; do 144 sep_line 145 ndelta=1 146 if [ ${lg_grp} -eq $((${ptr_bits} - 1)) ] ; then 147 ndelta_limit=$((${g} - 1)) 148 else 149 ndelta_limit=${g} 150 fi 151 while [ ${ndelta} -le ${ndelta_limit} ] ; do 152 size_class ${index} ${lg_grp} ${lg_delta} ${ndelta} ${lg_p} ${lg_kmax} 153 if [ ${lg_delta_lookup} != "no" ] ; then 154 nlbins=$((${index} + 1)) 155 # Final written value is correct: 156 lookup_maxclass="((((size_t)1) << ${lg_grp}) + (((size_t)${ndelta}) << ${lg_delta}))" 157 fi 158 if [ ${bin} != "no" ] ; then 159 nbins=$((${index} + 1)) 160 # Final written value is correct: 161 small_maxclass="((((size_t)1) << ${lg_grp}) + (((size_t)${ndelta}) << ${lg_delta}))" 162 fi 163 index=$((${index} + 1)) 164 ndelta=$((${ndelta} + 1)) 165 done 166 lg_grp=$((${lg_grp} + 1)) 167 lg_delta=$((${lg_delta} + 1)) 168 done 169 echo 170 171 # Defined upon completion: 172 # - ntbins 173 # - nlbins 174 # - nbins 175 # - lg_tiny_maxclass 176 # - lookup_maxclass 177 # - small_maxclass 178 } 179 180 cat <<EOF 181 /* This file was automatically generated by size_classes.sh. */ 182 /******************************************************************************/ 183 #ifdef JEMALLOC_H_TYPES 184 185 /* 186 * This header requires LG_SIZEOF_PTR, LG_TINY_MIN, LG_QUANTUM, and LG_PAGE to 187 * be defined prior to inclusion, and it in turn defines: 188 * 189 * LG_SIZE_CLASS_GROUP: Lg of size class count for each size doubling. 190 * SIZE_CLASSES: Complete table of 191 * SC(index, lg_delta, size, bin, lg_delta_lookup) tuples. 192 * index: Size class index. 193 * lg_grp: Lg group base size (no deltas added). 194 * lg_delta: Lg delta to previous size class. 195 * ndelta: Delta multiplier. size == 1<<lg_grp + ndelta<<lg_delta 196 * bin: 'yes' if a small bin size class, 'no' otherwise. 197 * lg_delta_lookup: Same as lg_delta if a lookup table size class, 'no' 198 * otherwise. 199 * NTBINS: Number of tiny bins. 200 * NLBINS: Number of bins supported by the lookup table. 201 * NBINS: Number of small size class bins. 202 * LG_TINY_MAXCLASS: Lg of maximum tiny size class. 203 * LOOKUP_MAXCLASS: Maximum size class included in lookup table. 204 * SMALL_MAXCLASS: Maximum small size class. 205 */ 206 207 #define LG_SIZE_CLASS_GROUP ${lg_g} 208 209 EOF 210 211 for lg_z in ${lg_zarr} ; do 212 for lg_q in ${lg_qarr} ; do 213 lg_t=${lg_tmin} 214 while [ ${lg_t} -le ${lg_q} ] ; do 215 # Iterate through page sizes and compute how many bins there are. 216 for lg_p in ${lg_parr} ; do 217 echo "#if (LG_SIZEOF_PTR == ${lg_z} && LG_TINY_MIN == ${lg_t} && LG_QUANTUM == ${lg_q} && LG_PAGE == ${lg_p})" 218 size_classes ${lg_z} ${lg_q} ${lg_t} ${lg_p} ${lg_g} 219 echo "#define SIZE_CLASSES_DEFINED" 220 echo "#define NTBINS ${ntbins}" 221 echo "#define NLBINS ${nlbins}" 222 echo "#define NBINS ${nbins}" 223 echo "#define LG_TINY_MAXCLASS ${lg_tiny_maxclass}" 224 echo "#define LOOKUP_MAXCLASS ${lookup_maxclass}" 225 echo "#define SMALL_MAXCLASS ${small_maxclass}" 226 echo "#endif" 227 echo 228 done 229 lg_t=$((${lg_t} + 1)) 230 done 231 done 232 done 233 234 cat <<EOF 235 #ifndef SIZE_CLASSES_DEFINED 236 # error "No size class definitions match configuration" 237 #endif 238 #undef SIZE_CLASSES_DEFINED 239 /* 240 * The small_size2bin lookup table uses uint8_t to encode each bin index, so we 241 * cannot support more than 256 small size classes. Further constrain NBINS to 242 * 255 since all small size classes, plus a "not small" size class must be 243 * stored in 8 bits of arena_chunk_map_t's bits field. 244 */ 245 #if (NBINS > 255) 246 # error "Too many small size classes" 247 #endif 248 249 #endif /* JEMALLOC_H_TYPES */ 250 /******************************************************************************/ 251 #ifdef JEMALLOC_H_STRUCTS 252 253 254 #endif /* JEMALLOC_H_STRUCTS */ 255 /******************************************************************************/ 256 #ifdef JEMALLOC_H_EXTERNS 257 258 259 #endif /* JEMALLOC_H_EXTERNS */ 260 /******************************************************************************/ 261 #ifdef JEMALLOC_H_INLINES 262 263 264 #endif /* JEMALLOC_H_INLINES */ 265 /******************************************************************************/ 266 EOF 267
