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