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