Line data Source code
1 : #ifndef HEADER_fd_src_util_alloc_fd_alloc_cfg_h
2 : #define HEADER_fd_src_util_alloc_fd_alloc_cfg_h
3 :
4 : /* The below table was autogenerated.
5 :
6 : The method begins by choosing the parameters for the wksp allocation
7 : request used to support small allocations (i.e. that align and sz
8 : should be passed to fd_wksp_alloc to create a "huge" superblock).
9 : Below is such that fd_alloc_malloc will request arbitrarily aligned
10 : 512KiB regions. This was picked to match the maximum size supported
11 : by the 19-bit fd_alloc_hdr_t offset (used to find in an address space
12 : invariant way the superblock of an allocation). Unaligned was used
13 : to be as general as possible (e.g. can swap in any other allocator
14 : of last resort as needed).
15 :
16 : Noting that superblocks have an alignment of 16 bytes, the maximum
17 : safe superblock footprint that can be carved out of this request is
18 : H=512KiB-19B=524269B (where the 19B accounts for a 4B fd_alloc_hdr_t
19 : and a 15B worst case alignment padding since fd_alloc_malloc
20 : superblock allocation doesn't assume anything the returned
21 : alignment).
22 :
23 : We note that a superblock can be divided into 1 to 64 blocks and that
24 : dividing it into O(1) blocks defeats the point clustering lots of
25 : similarly sized allocations (used to amortize various space and time
26 : overheads). So we pick the minimum number of blocks in a superblock
27 : as 8 (~sqrt(64) and around an order of magnitude reduction in
28 : overheads).
29 :
30 : Critically, noting that ~ 512KiB/64 ~ 8KiB is pretty clumsy for small
31 : allocations, we recursively nest a smaller sized superblock within
32 : blocks of this superblock.
33 :
34 : Specifically, we pick a "large" superblock size that will nest as
35 : tightly inside a block of a "huge" superblock when the huge
36 : superblock is divided into the minimum 8 blocks. Noting that the the
37 : large superblock will have the same 19B overhead and the huge huge
38 : superblock has a 16B header, we have L=floor((H-16B)/8)-19B=65512B.
39 :
40 : We recurse this all the way down to the smallest potentially useful
41 : superblock size (deciding to use the same 8 nesting for each level),
42 : yielding 5 superblock footprints (tiny 104B, small 1000B, medium
43 : 8168B, large 65512B, huge 524269B).
44 :
45 : We then target 33 sizeclasses for each superblock footprint (33 is
46 : from trial-and-error to get something that doesn't need more than 127
47 : sizeclasses after the below cleanups ... 127 so that the sizeclass
48 : index fits and uses practically all of the 7-bits in the
49 : fd_alloc_hdr_t sizeclass field). We chose block counts for these 33
50 : sizeclasses to be uniformly logarithmic spaced over [8,64) before
51 : rounding nearest. (For the parameters here, this implies a few
52 : percent overhead from the implicit rounding up of an unaligned
53 : allocation.)
54 :
55 : block_footprints are directly computed from these superblock
56 : footprints and and the block counts are recomputed to squeeze some
57 : extra blocks into the superblocks that various integer roundings
58 : might have exposed. We discard any sizeclasses that are redundant
59 : and any sizeclasses that are too small to be useful (blocks need to
60 : be at least 5 as a single byte unaligned allocation will still have a
61 : 4 byte fd_alloc_hdr_t associated with it). This yields the 126 size
62 : classes below.
63 :
64 : On the assumption that small allocations have a shorter lifetime /
65 : higher frequency than large ones, we have the option to use more
66 : concurrency groups for tiny, small and medium superblocks than for
67 : large and huge superblocks (but we don't currently). This would
68 : increase thread contention for decreased preemptive overallocation at
69 : large sizes.
70 :
71 : Note that the block_footprint in this table must be monotonically
72 : increasing to facilitate rapid searching.
73 :
74 : Note also that this allocator could be customized by tweaking
75 : sizeclasses to match specific application allocation sizes to get
76 : even tighter spatial packings. */
77 :
78 : /* Requests with worst case footprint greater than
79 : FD_ALLOC_FOOTPRINT_SMALL_THRESH will be considered as large and done
80 : directly through the fd_wksp_alloc allocator. Smaller footprints
81 : will be grouped together into superblocks to reduce the costs of the
82 : allocations. This should be at most the largest sizeclass block
83 : footprint below. */
84 :
85 : #define FD_ALLOC_FOOTPRINT_SMALL_THRESH (65531UL)
86 :
87 : /* FD_ALLOC_SIZECLASS_CNT is the number of sizeclasses supported by this
88 : implementation. This should be positive integer of at most 127. */
89 :
90 823857144 : #define FD_ALLOC_SIZECLASS_CNT (126UL)
91 :
92 : /* FD_ALLOC_SIZECLASS_LARGE is a sentinel value used to indicate that
93 : an allocation is "large" (i.e. that is was done by the fd_wksp_alloc
94 : allocator). */
95 :
96 0 : #define FD_ALLOC_SIZECLASS_LARGE (127UL)
97 :
98 : struct __attribute__((aligned(8))) fd_alloc_sizeclass_cfg {
99 : uint superblock_footprint; /* Size of the allocation needed to make a superblock for this class */
100 : ushort block_footprint; /* Footprint of blocks in this size class, block_cnt*block_footprint+16 <= superblock_footprint */
101 : uchar block_cnt; /* Number of blocks in this, in [1,64] */
102 : uchar cgroup_mask; /* Number of cgroups for this sizeclass minus 1, a power of 2 minus 1, at most CGROUP_HINT_MAX */
103 : };
104 :
105 : typedef struct fd_alloc_sizeclass_cfg fd_alloc_sizeclass_cfg_t;
106 :
107 : static fd_alloc_sizeclass_cfg_t const fd_alloc_sizeclass_cfg[126] = {
108 : { 104U, (ushort) 5, (uchar)17, (uchar)15 }, // sizeclass 0 - tiny sb sizeclasses
109 : { 104U, (ushort) 6, (uchar)14, (uchar)15 }, // sizeclass 1
110 : { 104U, (ushort) 7, (uchar)12, (uchar)15 }, // sizeclass 2
111 : { 104U, (ushort) 8, (uchar)11, (uchar)15 }, // sizeclass 3
112 : { 104U, (ushort) 9, (uchar) 9, (uchar)15 }, // sizeclass 4
113 : { 104U, (ushort) 11, (uchar) 8, (uchar)15 }, // sizeclass 5
114 : { 1000U, (ushort) 16, (uchar)61, (uchar)15 }, // sizeclass 6 - small sb sizeclasses
115 : { 1000U, (ushort) 17, (uchar)57, (uchar)15 }, // sizeclass 7
116 : { 1000U, (ushort) 18, (uchar)54, (uchar)15 }, // sizeclass 8
117 : { 1000U, (ushort) 19, (uchar)51, (uchar)15 }, // sizeclass 9
118 : { 1000U, (ushort) 20, (uchar)49, (uchar)15 }, // sizeclass 10
119 : { 1000U, (ushort) 22, (uchar)44, (uchar)15 }, // sizeclass 11
120 : { 1000U, (ushort) 24, (uchar)41, (uchar)15 }, // sizeclass 12
121 : { 1000U, (ushort) 25, (uchar)39, (uchar)15 }, // sizeclass 13
122 : { 1000U, (ushort) 27, (uchar)36, (uchar)15 }, // sizeclass 14
123 : { 1000U, (ushort) 28, (uchar)35, (uchar)15 }, // sizeclass 15
124 : { 1000U, (ushort) 30, (uchar)32, (uchar)15 }, // sizeclass 16
125 : { 1000U, (ushort) 32, (uchar)30, (uchar)15 }, // sizeclass 17
126 : { 1000U, (ushort) 35, (uchar)28, (uchar)15 }, // sizeclass 18
127 : { 1000U, (ushort) 37, (uchar)26, (uchar)15 }, // sizeclass 19
128 : { 1000U, (ushort) 39, (uchar)25, (uchar)15 }, // sizeclass 20
129 : { 1000U, (ushort) 42, (uchar)23, (uchar)15 }, // sizeclass 21
130 : { 1000U, (ushort) 44, (uchar)22, (uchar)15 }, // sizeclass 22
131 : { 1000U, (ushort) 46, (uchar)21, (uchar)15 }, // sizeclass 23
132 : { 1000U, (ushort) 51, (uchar)19, (uchar)15 }, // sizeclass 24
133 : { 1000U, (ushort) 54, (uchar)18, (uchar)15 }, // sizeclass 25
134 : { 1000U, (ushort) 57, (uchar)17, (uchar)15 }, // sizeclass 26
135 : { 1000U, (ushort) 61, (uchar)16, (uchar)15 }, // sizeclass 27
136 : { 1000U, (ushort) 65, (uchar)15, (uchar)15 }, // sizeclass 28
137 : { 1000U, (ushort) 70, (uchar)14, (uchar)15 }, // sizeclass 29
138 : { 1000U, (ushort) 75, (uchar)13, (uchar)15 }, // sizeclass 30
139 : { 1000U, (ushort) 82, (uchar)12, (uchar)15 }, // sizeclass 31
140 : { 1000U, (ushort) 89, (uchar)11, (uchar)15 }, // sizeclass 32
141 : { 1000U, (ushort) 98, (uchar)10, (uchar)15 }, // sizeclass 33
142 : { 1000U, (ushort) 109, (uchar) 9, (uchar)15 }, // sizeclass 34
143 : { 1000U, (ushort) 123, (uchar) 8, (uchar)15 }, // sizeclass 35 - holds tiny sb
144 : { 8168U, (ushort) 135, (uchar)60, (uchar)15 }, // sizeclass 36 - medium sb sizeclasses
145 : { 8168U, (ushort) 145, (uchar)56, (uchar)15 }, // sizeclass 37
146 : { 8168U, (ushort) 153, (uchar)53, (uchar)15 }, // sizeclass 38
147 : { 8168U, (ushort) 163, (uchar)50, (uchar)15 }, // sizeclass 39
148 : { 8168U, (ushort) 173, (uchar)47, (uchar)15 }, // sizeclass 40
149 : { 8168U, (ushort) 185, (uchar)44, (uchar)15 }, // sizeclass 41
150 : { 8168U, (ushort) 198, (uchar)41, (uchar)15 }, // sizeclass 42
151 : { 8168U, (ushort) 209, (uchar)39, (uchar)15 }, // sizeclass 43
152 : { 8168U, (ushort) 226, (uchar)36, (uchar)15 }, // sizeclass 44
153 : { 8168U, (ushort) 239, (uchar)34, (uchar)15 }, // sizeclass 45
154 : { 8168U, (ushort) 254, (uchar)32, (uchar)15 }, // sizeclass 46
155 : { 8168U, (ushort) 271, (uchar)30, (uchar)15 }, // sizeclass 47
156 : { 8168U, (ushort) 291, (uchar)28, (uchar)15 }, // sizeclass 48
157 : { 8168U, (ushort) 313, (uchar)26, (uchar)15 }, // sizeclass 49
158 : { 8168U, (ushort) 326, (uchar)25, (uchar)15 }, // sizeclass 50
159 : { 8168U, (ushort) 354, (uchar)23, (uchar)15 }, // sizeclass 51
160 : { 8168U, (ushort) 370, (uchar)22, (uchar)15 }, // sizeclass 52
161 : { 8168U, (ushort) 388, (uchar)21, (uchar)15 }, // sizeclass 53
162 : { 8168U, (ushort) 429, (uchar)19, (uchar)15 }, // sizeclass 54
163 : { 8168U, (ushort) 452, (uchar)18, (uchar)15 }, // sizeclass 55
164 : { 8168U, (ushort) 479, (uchar)17, (uchar)15 }, // sizeclass 56
165 : { 8168U, (ushort) 509, (uchar)16, (uchar)15 }, // sizeclass 57
166 : { 8168U, (ushort) 543, (uchar)15, (uchar)15 }, // sizeclass 58
167 : { 8168U, (ushort) 582, (uchar)14, (uchar)15 }, // sizeclass 59
168 : { 8168U, (ushort) 627, (uchar)13, (uchar)15 }, // sizeclass 60
169 : { 8168U, (ushort) 679, (uchar)12, (uchar)15 }, // sizeclass 61
170 : { 8168U, (ushort) 741, (uchar)11, (uchar)15 }, // sizeclass 62
171 : { 8168U, (ushort) 815, (uchar)10, (uchar)15 }, // sizeclass 63
172 : { 8168U, (ushort) 905, (uchar) 9, (uchar)15 }, // sizeclass 64
173 : { 8168U, (ushort) 1019, (uchar) 8, (uchar)15 }, // sizeclass 65 - holds small sb
174 : { 65512U, (ushort) 1091, (uchar)60, (uchar)15 }, // sizeclass 66 - large sb sizeclasses
175 : { 65512U, (ushort) 1169, (uchar)56, (uchar)15 }, // sizeclass 67
176 : { 65512U, (ushort) 1235, (uchar)53, (uchar)15 }, // sizeclass 68
177 : { 65512U, (ushort) 1309, (uchar)50, (uchar)15 }, // sizeclass 69
178 : { 65512U, (ushort) 1393, (uchar)47, (uchar)15 }, // sizeclass 70
179 : { 65512U, (ushort) 1488, (uchar)44, (uchar)15 }, // sizeclass 71
180 : { 65512U, (ushort) 1597, (uchar)41, (uchar)15 }, // sizeclass 72
181 : { 65512U, (ushort) 1679, (uchar)39, (uchar)15 }, // sizeclass 73
182 : { 65512U, (ushort) 1819, (uchar)36, (uchar)15 }, // sizeclass 74
183 : { 65512U, (ushort) 1926, (uchar)34, (uchar)15 }, // sizeclass 75
184 : { 65512U, (ushort) 2046, (uchar)32, (uchar)15 }, // sizeclass 76
185 : { 65512U, (ushort) 2183, (uchar)30, (uchar)15 }, // sizeclass 77
186 : { 65512U, (ushort) 2339, (uchar)28, (uchar)15 }, // sizeclass 78
187 : { 65512U, (ushort) 2519, (uchar)26, (uchar)15 }, // sizeclass 79
188 : { 65512U, (ushort) 2619, (uchar)25, (uchar)15 }, // sizeclass 80
189 : { 65512U, (ushort) 2847, (uchar)23, (uchar)15 }, // sizeclass 81
190 : { 65512U, (ushort) 2977, (uchar)22, (uchar)15 }, // sizeclass 82
191 : { 65512U, (ushort) 3118, (uchar)21, (uchar)15 }, // sizeclass 83
192 : { 65512U, (ushort) 3447, (uchar)19, (uchar)15 }, // sizeclass 84
193 : { 65512U, (ushort) 3638, (uchar)18, (uchar)15 }, // sizeclass 85
194 : { 65512U, (ushort) 3852, (uchar)17, (uchar)15 }, // sizeclass 86
195 : { 65512U, (ushort) 4093, (uchar)16, (uchar)15 }, // sizeclass 87
196 : { 65512U, (ushort) 4366, (uchar)15, (uchar)15 }, // sizeclass 88
197 : { 65512U, (ushort) 4678, (uchar)14, (uchar)15 }, // sizeclass 89
198 : { 65512U, (ushort) 5038, (uchar)13, (uchar)15 }, // sizeclass 90
199 : { 65512U, (ushort) 5458, (uchar)12, (uchar)15 }, // sizeclass 91
200 : { 65512U, (ushort) 5954, (uchar)11, (uchar)15 }, // sizeclass 92
201 : { 65512U, (ushort) 6549, (uchar)10, (uchar)15 }, // sizeclass 93
202 : { 65512U, (ushort) 7277, (uchar) 9, (uchar)15 }, // sizeclass 94
203 : { 65512U, (ushort) 8187, (uchar) 8, (uchar)15 }, // sizeclass 95 - holds medium sb
204 : { 524269U, (ushort) 8737, (uchar)60, (uchar)15 }, // sizeclass 96 - huge sb sizeclasses
205 : { 524269U, (ushort) 9361, (uchar)56, (uchar)15 }, // sizeclass 97
206 : { 524269U, (ushort) 9891, (uchar)53, (uchar)15 }, // sizeclass 98
207 : { 524269U, (ushort)10485, (uchar)50, (uchar)15 }, // sizeclass 99
208 : { 524269U, (ushort)11154, (uchar)47, (uchar)15 }, // sizeclass 100
209 : { 524269U, (ushort)11914, (uchar)44, (uchar)15 }, // sizeclass 101
210 : { 524269U, (ushort)12786, (uchar)41, (uchar)15 }, // sizeclass 102
211 : { 524269U, (ushort)13442, (uchar)39, (uchar)15 }, // sizeclass 103
212 : { 524269U, (ushort)14562, (uchar)36, (uchar)15 }, // sizeclass 104
213 : { 524269U, (ushort)15419, (uchar)34, (uchar)15 }, // sizeclass 105
214 : { 524269U, (ushort)16382, (uchar)32, (uchar)15 }, // sizeclass 106
215 : { 524269U, (ushort)17475, (uchar)30, (uchar)15 }, // sizeclass 107
216 : { 524269U, (ushort)18723, (uchar)28, (uchar)15 }, // sizeclass 108
217 : { 524269U, (ushort)20163, (uchar)26, (uchar)15 }, // sizeclass 109
218 : { 524269U, (ushort)20970, (uchar)25, (uchar)15 }, // sizeclass 110
219 : { 524269U, (ushort)22793, (uchar)23, (uchar)15 }, // sizeclass 111
220 : { 524269U, (ushort)23829, (uchar)22, (uchar)15 }, // sizeclass 112
221 : { 524269U, (ushort)24964, (uchar)21, (uchar)15 }, // sizeclass 113
222 : { 524269U, (ushort)27592, (uchar)19, (uchar)15 }, // sizeclass 114
223 : { 524269U, (ushort)29125, (uchar)18, (uchar)15 }, // sizeclass 115
224 : { 524269U, (ushort)30838, (uchar)17, (uchar)15 }, // sizeclass 116
225 : { 524269U, (ushort)32765, (uchar)16, (uchar)15 }, // sizeclass 117
226 : { 524269U, (ushort)34950, (uchar)15, (uchar)15 }, // sizeclass 118
227 : { 524269U, (ushort)37446, (uchar)14, (uchar)15 }, // sizeclass 119
228 : { 524269U, (ushort)40327, (uchar)13, (uchar)15 }, // sizeclass 120
229 : { 524269U, (ushort)43687, (uchar)12, (uchar)15 }, // sizeclass 121
230 : { 524269U, (ushort)47659, (uchar)11, (uchar)15 }, // sizeclass 122
231 : { 524269U, (ushort)52425, (uchar)10, (uchar)15 }, // sizeclass 123
232 : { 524269U, (ushort)58250, (uchar) 9, (uchar)15 }, // sizeclass 124
233 : { 524269U, (ushort)65531, (uchar) 8, (uchar)15 } // sizeclass 125 - holds large sb
234 : // huge sb are wksp allocated
235 : };
236 :
237 : #endif /* HEADER_fd_src_util_alloc_fd_alloc_cfg_h */
238 :
|
