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