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