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