[rustc.git] / src / jemalloc / include / jemalloc / internal / size_classes.sh

#!/bin/sh

# The following limits are chosen such that they cover all supported platforms.

# Pointer sizes.
lg_zarr="2 3"

# Quanta.
lg_qarr="3 4"

# The range of tiny size classes is [2^lg_tmin..2^(lg_q-1)].
lg_tmin=3

# Maximum lookup size.
lg_kmax=12

# Page sizes.
lg_parr="12 13 16"

# Size class group size (number of size classes for each size doubling).
lg_g=2

pow2() {
  e=$1
  pow2_result=1
  while [ ${e} -gt 0 ] ; do
    pow2_result=$((${pow2_result} + ${pow2_result}))
    e=$((${e} - 1))
  done
}

lg() {
  x=$1
  lg_result=0
  while [ ${x} -gt 1 ] ; do
    lg_result=$((${lg_result} + 1))
    x=$((${x} / 2))
  done
}

size_class() {
  index=$1
  lg_grp=$2
  lg_delta=$3
  ndelta=$4
  lg_p=$5
  lg_kmax=$6

  lg ${ndelta}; lg_ndelta=${lg_result}; pow2 ${lg_ndelta}
  if [ ${pow2_result} -lt ${ndelta} ] ; then
    rem="yes"
  else
    rem="no"
  fi

  lg_size=${lg_grp}
  if [ $((${lg_delta} + ${lg_ndelta})) -eq ${lg_grp} ] ; then
    lg_size=$((${lg_grp} + 1))
  else
    lg_size=${lg_grp}
    rem="yes"
  fi

  if [ ${lg_size} -lt ${lg_p} ] ; then
    bin="yes"
  else
    bin="no"
  fi
  if [ ${lg_size} -lt ${lg_kmax} \
      -o ${lg_size} -eq ${lg_kmax} -a ${rem} = "no" ] ; then
    lg_delta_lookup=${lg_delta}
  else
    lg_delta_lookup="no"
  fi
  printf '    SC(%3d, %6d, %8d, %6d, %3s, %2s) \\\n' ${index} ${lg_grp} ${lg_delta} ${ndelta} ${bin} ${lg_delta_lookup}
  # Defined upon return:
  # - lg_delta_lookup (${lg_delta} or "no")
  # - bin ("yes" or "no")
}

sep_line() {
  echo "                                               \\"
}

size_classes() {
  lg_z=$1
  lg_q=$2
  lg_t=$3
  lg_p=$4
  lg_g=$5

  pow2 $((${lg_z} + 3)); ptr_bits=${pow2_result}
  pow2 ${lg_g}; g=${pow2_result}

  echo "#define	SIZE_CLASSES \\"
  echo "  /* index, lg_grp, lg_delta, ndelta, bin, lg_delta_lookup */ \\"

  ntbins=0
  nlbins=0
  lg_tiny_maxclass='"NA"'
  nbins=0

  # Tiny size classes.
  ndelta=0
  index=0
  lg_grp=${lg_t}
  lg_delta=${lg_grp}
  while [ ${lg_grp} -lt ${lg_q} ] ; do
    size_class ${index} ${lg_grp} ${lg_delta} ${ndelta} ${lg_p} ${lg_kmax}
    if [ ${lg_delta_lookup} != "no" ] ; then
      nlbins=$((${index} + 1))
    fi
    if [ ${bin} != "no" ] ; then
      nbins=$((${index} + 1))
    fi
    ntbins=$((${ntbins} + 1))
    lg_tiny_maxclass=${lg_grp} # Final written value is correct.
    index=$((${index} + 1))
    lg_delta=${lg_grp}
    lg_grp=$((${lg_grp} + 1))
  done

  # First non-tiny group.
  if [ ${ntbins} -gt 0 ] ; then
    sep_line
    # The first size class has an unusual encoding, because the size has to be
    # split between grp and delta*ndelta.
    lg_grp=$((${lg_grp} - 1))
    ndelta=1
    size_class ${index} ${lg_grp} ${lg_delta} ${ndelta} ${lg_p} ${lg_kmax}
    index=$((${index} + 1))
    lg_grp=$((${lg_grp} + 1))
    lg_delta=$((${lg_delta} + 1))
  fi
  while [ ${ndelta} -lt ${g} ] ; do
    size_class ${index} ${lg_grp} ${lg_delta} ${ndelta} ${lg_p} ${lg_kmax}
    index=$((${index} + 1))
    ndelta=$((${ndelta} + 1))
  done

  # All remaining groups.
  lg_grp=$((${lg_grp} + ${lg_g}))
  while [ ${lg_grp} -lt ${ptr_bits} ] ; do
    sep_line
    ndelta=1
    if [ ${lg_grp} -eq $((${ptr_bits} - 1)) ] ; then
      ndelta_limit=$((${g} - 1))
    else
      ndelta_limit=${g}
    fi
    while [ ${ndelta} -le ${ndelta_limit} ] ; do
      size_class ${index} ${lg_grp} ${lg_delta} ${ndelta} ${lg_p} ${lg_kmax}
      if [ ${lg_delta_lookup} != "no" ] ; then
        nlbins=$((${index} + 1))
        # Final written value is correct:
        lookup_maxclass="((((size_t)1) << ${lg_grp}) + (((size_t)${ndelta}) << ${lg_delta}))"
      fi
      if [ ${bin} != "no" ] ; then
        nbins=$((${index} + 1))
        # Final written value is correct:
        small_maxclass="((((size_t)1) << ${lg_grp}) + (((size_t)${ndelta}) << ${lg_delta}))"
      fi
      index=$((${index} + 1))
      ndelta=$((${ndelta} + 1))
    done
    lg_grp=$((${lg_grp} + 1))
    lg_delta=$((${lg_delta} + 1))
  done
  echo

  # Defined upon completion:
  # - ntbins
  # - nlbins
  # - nbins
  # - lg_tiny_maxclass
  # - lookup_maxclass
  # - small_maxclass
}

cat <<EOF
/* This file was automatically generated by size_classes.sh. */
/******************************************************************************/
#ifdef JEMALLOC_H_TYPES

/*
 * This header requires LG_SIZEOF_PTR, LG_TINY_MIN, LG_QUANTUM, and LG_PAGE to
 * be defined prior to inclusion, and it in turn defines:
 *
 *   LG_SIZE_CLASS_GROUP: Lg of size class count for each size doubling.
 *   SIZE_CLASSES: Complete table of
 *                 SC(index, lg_delta, size, bin, lg_delta_lookup) tuples.
 *     index: Size class index.
 *     lg_grp: Lg group base size (no deltas added).
 *     lg_delta: Lg delta to previous size class.
 *     ndelta: Delta multiplier.  size == 1<<lg_grp + ndelta<<lg_delta
 *     bin: 'yes' if a small bin size class, 'no' otherwise.
 *     lg_delta_lookup: Same as lg_delta if a lookup table size class, 'no'
 *                      otherwise.
 *   NTBINS: Number of tiny bins.
 *   NLBINS: Number of bins supported by the lookup table.
 *   NBINS: Number of small size class bins.
 *   LG_TINY_MAXCLASS: Lg of maximum tiny size class.
 *   LOOKUP_MAXCLASS: Maximum size class included in lookup table.
 *   SMALL_MAXCLASS: Maximum small size class.
 *   LARGE_MINCLASS: Minimum large size class.
 */

#define	LG_SIZE_CLASS_GROUP	${lg_g}

EOF

for lg_z in ${lg_zarr} ; do
  for lg_q in ${lg_qarr} ; do
    lg_t=${lg_tmin}
    while [ ${lg_t} -le ${lg_q} ] ; do
      # Iterate through page sizes and compute how many bins there are.
      for lg_p in ${lg_parr} ; do
        echo "#if (LG_SIZEOF_PTR == ${lg_z} && LG_TINY_MIN == ${lg_t} && LG_QUANTUM == ${lg_q} && LG_PAGE == ${lg_p})"
        size_classes ${lg_z} ${lg_q} ${lg_t} ${lg_p} ${lg_g}
        echo "#define	SIZE_CLASSES_DEFINED"
        echo "#define	NTBINS			${ntbins}"
        echo "#define	NLBINS			${nlbins}"
        echo "#define	NBINS			${nbins}"
        echo "#define	LG_TINY_MAXCLASS	${lg_tiny_maxclass}"
        echo "#define	LOOKUP_MAXCLASS		${lookup_maxclass}"
        echo "#define	SMALL_MAXCLASS		${small_maxclass}"
        echo "#endif"
        echo
      done
      lg_t=$((${lg_t} + 1))
    done
  done
done

cat <<EOF
#ifndef SIZE_CLASSES_DEFINED
#  error "No size class definitions match configuration"
#endif
#undef SIZE_CLASSES_DEFINED
/*
 * The small_size2bin lookup table uses uint8_t to encode each bin index, so we
 * cannot support more than 256 small size classes.  Further constrain NBINS to
 * 255 since all small size classes, plus a "not small" size class must be
 * stored in 8 bits of arena_chunk_map_bits_t's bits field.
 */
#if (NBINS > 255)
#  error "Too many small size classes"
#endif

#define	LARGE_MINCLASS (PAGE_CEILING(SMALL_MAXCLASS+1))

#endif /* JEMALLOC_H_TYPES */
/******************************************************************************/
#ifdef JEMALLOC_H_STRUCTS


#endif /* JEMALLOC_H_STRUCTS */
/******************************************************************************/
#ifdef JEMALLOC_H_EXTERNS


#endif /* JEMALLOC_H_EXTERNS */
/******************************************************************************/
#ifdef JEMALLOC_H_INLINES


#endif /* JEMALLOC_H_INLINES */
/******************************************************************************/
EOF
Commit	Line	Data
1a4d82fc JJ	1	#!/bin/sh
	2
	3	# The following limits are chosen such that they cover all supported platforms.
	4
	5	# Pointer sizes.
	6	lg_zarr="2 3"
	7
	8	# Quanta.
7453a54e	9	lg_qarr="3 4"
1a4d82fc JJ	10
1a4d82fc JJ	11	# The range of tiny size classes is [2^lg_tmin..2^(lg_q-1)].
7453a54e	12	lg_tmin=3
1a4d82fc JJ	13
	14	# Maximum lookup size.
	15	lg_kmax=12
	16
	17	# Page sizes.
7453a54e	18	lg_parr="12 13 16"
1a4d82fc JJ	19
1a4d82fc JJ	20	# Size class group size (number of size classes for each size doubling).
7453a54e	21	lg_g=2
1a4d82fc JJ	22
	23	pow2() {
	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
	32	lg() {
	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
	41	size_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
7453a54e	64	if [ ${lg_size} -lt ${lg_p} ] ; then
1a4d82fc JJ	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
	81	sep_line() {
	82	echo " \\"
	83	}
	84
	85	size_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
180	cat <<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
7453a54e	191	* SC(index, lg_delta, size, bin, lg_delta_lookup) tuples.
1a4d82fc JJ	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.
7453a54e	205	* LARGE_MINCLASS: Minimum large size class.
1a4d82fc JJ	206	*/
	207
	208	#define LG_SIZE_CLASS_GROUP ${lg_g}
	209
	210	EOF
	211
	212	for lg_z in ${lg_zarr} ; do
	213	for lg_q in ${lg_qarr} ; do
	214	lg_t=${lg_tmin}
	215	while [ ${lg_t} -le ${lg_q} ] ; do
	216	# Iterate through page sizes and compute how many bins there are.
	217	for lg_p in ${lg_parr} ; do
	218	echo "#if (LG_SIZEOF_PTR == ${lg_z} && LG_TINY_MIN == ${lg_t} && LG_QUANTUM == ${lg_q} && LG_PAGE == ${lg_p})"
	219	size_classes ${lg_z} ${lg_q} ${lg_t} ${lg_p} ${lg_g}
	220	echo "#define SIZE_CLASSES_DEFINED"
	221	echo "#define NTBINS ${ntbins}"
	222	echo "#define NLBINS ${nlbins}"
	223	echo "#define NBINS ${nbins}"
	224	echo "#define LG_TINY_MAXCLASS ${lg_tiny_maxclass}"
	225	echo "#define LOOKUP_MAXCLASS ${lookup_maxclass}"
	226	echo "#define SMALL_MAXCLASS ${small_maxclass}"
	227	echo "#endif"
	228	echo
	229	done
	230	lg_t=$((${lg_t} + 1))
	231	done
	232	done
	233	done
	234
	235	cat <<EOF
	236	#ifndef SIZE_CLASSES_DEFINED
	237	# error "No size class definitions match configuration"
	238	#endif
	239	#undef SIZE_CLASSES_DEFINED
	240	/*
7453a54e	241	* The small_size2bin lookup table uses uint8_t to encode each bin index, so we
1a4d82fc JJ	242	* cannot support more than 256 small size classes. Further constrain NBINS to
	243	* 255 since all small size classes, plus a "not small" size class must be
	244	* stored in 8 bits of arena_chunk_map_bits_t's bits field.
	245	*/
	246	#if (NBINS > 255)
	247	# error "Too many small size classes"
	248	#endif
	249
7453a54e SL	250	#define LARGE_MINCLASS (PAGE_CEILING(SMALL_MAXCLASS+1))
7453a54e SL	251
1a4d82fc JJ	252	#endif /* JEMALLOC_H_TYPES */
	253	/******************************************************************************/
	254	#ifdef JEMALLOC_H_STRUCTS
	255
	256
	257	#endif /* JEMALLOC_H_STRUCTS */
	258	/******************************************************************************/
	259	#ifdef JEMALLOC_H_EXTERNS
	260
	261
	262	#endif /* JEMALLOC_H_EXTERNS */
	263	/******************************************************************************/
	264	#ifdef JEMALLOC_H_INLINES
	265
	266
	267	#endif /* JEMALLOC_H_INLINES */
	268	/******************************************************************************/
	269	EOF