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