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