-
Notifications
You must be signed in to change notification settings - Fork 1
/
alloc.cc
306 lines (277 loc) · 7.08 KB
/
alloc.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
#define ICI_CORE
#include "fwd.h"
#if defined ICI_JEMALLOC
#include <jemalloc/jemalloc.h>
#endif
namespace ici
{
/*
* The amount of memory we currently have allocated, and a limit.
* When we reach the limit, a garbage collection is triggered (which
* will presumably reduce ici_mem and re-evaluate the limit).
*/
size_t ici_mem;
size_t ici_mem_limit;
/*
* A count and estimated total size of outstanding allocs done through
* ici_alloc and yet freed with ici_free.
*/
size_t ici_n_allocs;
size_t ici_alloc_mem;
#if !ICI_ALLALLOC
/*
* A chunk of memory in which to keep dense allocations of small
* objects to avoid boundary word overheads and allow simple fast
* free lists.
*/
struct chunk
{
char c_data[4088]; // FIXME: assumes 64-bit pointer
chunk *c_next;
};
/*
* The base pointers of our four fast free lists.
*/
char *ici_flists[4];
/*
* The current next available block, and limits, within each of
* the allocation chunks for each of the size categories we have
* for small objects.
*/
static char *mem_next[4];
static char *mem_limit[4];
/*
* The global list of all chunks of small dense objects we have allocated.
* We just keep this so we can free them all on interpreter shutdown.
*/
static chunk *ici_chunks;
#endif /* ICI_ALLALLOC */
constexpr size_t flist_limit = 64;
constexpr size_t flist_index(size_t z)
{
if (z > 0 && z <= flist_limit)
{
constexpr size_t which_flist[] = {0, 1, 2, 2, 3, 3, 3, 3};
return which_flist[(z - 1) >> 3];
}
return z;
}
/*
* Allocate an object of the given 'size'. Return nullptr on failure, usual
* conventions. The resulting object must be freed with ici_nfree() and only
* ici_nfree(). Note that ici_nfree() also requires to know the size of the
* object being freed.
*
* This function is preferable to ici_alloc(). It should be used if
* you can know the size of the allocation when the free happens so
* you can call ici_nfree(). If this isn't the case you will have to
* use ici_alloc().
*
* See also: 'ICIs allocation functions', ici_talloc(), ici_alloc(),
* ici_nfree().
*
* This --func-- forms part of the --ici-api--.
*/
void *ici_nalloc(size_t z)
{
char *r;
#if !ICI_ALLALLOC
size_t fi;
// static char const which_flist[] = {0, 1, 2, 2, 3, 3, 3, 3};
#endif
if ((ici_mem += z) > ici_mem_limit)
{
collect();
}
#if !ICI_ALLALLOC
fi = flist_index(z);
// if (z <= flist_limit)
// {
// fi = which_flist[(z - 1) >> 3];
// }
// else
// {
// fi = z;
// }
if (fi < (int)nels(ici_flists))
{
char **fp;
int cz;
chunk *c;
/*
* Small block. Try to get it off one of the fast free lists.
*/
fp = &ici_flists[fi];
if ((r = *fp) != nullptr)
{
*fp = *(char **)r;
return r;
}
/*
* Free list empty. Rip off a bit more memory from the current
* chunk.
*/
cz = 8 << fi;
if (mem_next[fi] + cz <= mem_limit[fi])
{
r = mem_next[fi];
mem_next[fi] += cz;
return r;
}
/*
* Current chunk empty. Allocate another one.
*/
if ((c = (chunk *)malloc(sizeof(chunk))) == nullptr)
{
collect();
if ((c = (chunk *)malloc(sizeof(chunk))) == nullptr)
{
goto fail;
}
}
c->c_next = ici_chunks;
ici_chunks = c;
mem_next[fi] = (char *)(((unsigned long)c->c_data + 0x3F) & ~0x3F);
mem_limit[fi] = &c->c_data[nels(c->c_data)];
r = mem_next[fi];
mem_next[fi] += cz;
return r;
}
#endif /* ICI_ALLALLOC */
if ((r = (char *)malloc(z)) == nullptr)
{
collect();
if ((r = (char *)malloc(z)) == nullptr)
{
goto fail;
}
}
return r;
fail:
set_error("ran out of memory");
return nullptr;
}
/*
* Free an object allocated with ici_nalloc(). The 'size' passed here
* must be exactly the same size passed to ici_nalloc() when the
* allocation was made. If you don't know the size, you should have
* called ici_alloc() in the first place.
*
* See also: 'ICIs allocation functions', ici_nalloc().
*
* This --func-- forms part of the --ici-api--.
*/
void ici_nfree(void *p, size_t z)
{
#if !ICI_ALLALLOC
int fi;
// static char const which_flist[] = {0, 1, 2, 2, 3, 3, 3, 3};
#endif
ici_mem -= z;
#if !ICI_ALLALLOC
if (z <= flist_limit)
{
/*
* Small block. Just push it onto one of our fast free lists.
*/
// fi = which_flist[(z - 1) >> 3];
fi = flist_index(z);
*(char **)p = ici_flists[fi];
ici_flists[fi] = (char *)p;
}
else
#endif
{
free(p);
}
}
/*
* Allocate a block of size 'z'. This just maps to a raw malloc() but
* does garbage collection as necessary and attempts to track memory
* usage to control when the garbage collector runs. Blocks allocated
* with this must be freed with ici_free().
*
* It is preferable to use ici_talloc(), or failing that, ici_nalloc(),
* instead of this function. But both require that you can match the
* allocation by calling ici_tfree() or ici_nalloc() with the original
* type/size you passed in the allocation call. Those functions use
* dense fast free lists for small objects, and track memory usage
* better.
*
* See also: 'ICIs allocation functions', ici_free(), ici_talloc(),
* ici_nalloc().
*
* This --func-- forms part of the --ici-api--.
*/
void *ici_alloc(size_t z)
{
void *p;
#if ALLCOLLECT
collect();
#else
if ((ici_mem += z) > ici_mem_limit)
{
collect();
}
#endif
++ici_n_allocs;
ici_alloc_mem += z;
if ((p = malloc(z)) == nullptr)
{
collect();
if ((p = malloc(z)) == nullptr)
{
set_error("ran out of memory");
return nullptr;
}
}
return p;
}
/*
* Free a block allocated with ici_alloc().
*
* See also: 'ICIs allocation functions', ici_alloc(), ici_tfree(),
* ici_nfree().
*
* This --func-- forms part of the --ici-api--.
*/
void ici_free(void *p)
{
ptrdiff_t z;
/*
* This makes a really dodgy attempt to track memory usage. Because
* we don't know how big the block being freed is, we just assume it
* is 1/Nth the size of the number of such mysterious allocations
* we have. Does a division - yuk.
*/
z = ici_alloc_mem / ici_n_allocs;
if (z > ptrdiff_t(ici_mem))
{
z = ici_mem;
}
if (z > ptrdiff_t(ici_alloc_mem))
{
z = ici_alloc_mem;
}
ici_mem -= z;
ici_alloc_mem -= z;
--ici_n_allocs;
free(p);
}
/*
* Drop (free) all memory associated with our dense allocations of small
* objects and fast free lists. For use in interpreter shutdown. Will
* cause total disaster if called at any other time.
*/
void drop_all_small_allocations()
{
#if !ICI_ALLALLOC
chunk *c;
while ((c = ici_chunks) != nullptr)
{
ici_chunks = c->c_next;
free(c);
}
#endif /* ICI_ALLALLOC */
}
} // namespace ici