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