Debian Codegraph @

external/bdwgc/doc/gcdescr.md

raw
1 # Conservative GC Algorithmic Overview
2
3 This is a description of the algorithms and data structures used in our
4 conservative garbage collector. I expect the level of detail to increase with
5 time. For a survey of GC algorithms, e.g. see Paul Wilson's
6 ["Uniprocessor Garbage Collection Techniques"](ftp://ftp.cs.utexas.edu/pub/garbage/gcsurvey.ps)
7 excellent paper. For an overview of the collector interface, see
8 [here](gcinterface.md).
9
10 This description is targeted primarily at someone trying to understand the
11 source code. It specifically refers to variable and function names. It may
12 also be useful for understanding the algorithms at a higher level.
13
14 The description here assumes that the collector is used in default mode.
15 In particular, we assume that it used as a garbage collector, and not just
16 a leak detector. We initially assume that it is used in stop-the-world,
17 non-incremental mode, though the presence of the incremental collector will
18 be apparent in the design. We assume the default finalization model, but the
19 code affected by that is very localized.
20
21 ## Introduction
22
23 The garbage collector uses a modified mark-sweep algorithm. Conceptually
24 it operates roughly in four phases, which are performed occasionally as part
25 of a memory allocation:
26
27 1. _Preparation_ Each object has an associated mark bit. Clear all mark
28 bits, indicating that all objects are potentially unreachable.
29 2. _Mark phase_ Marks all objects that can be reachable via chains
30 of pointers from variables. Often the collector has no real information
31 about the location of pointer variables in the heap, so it views all static
32 data areas, stacks and registers as potentially containing pointers. Any bit
33 patterns that represent addresses inside heap objects managed by the
34 collector are viewed as pointers. Unless the client program has made heap
35 object layout information available to the collector, any heap objects found
36 to be reachable from variables are again scanned similarly.
37 3. _Sweep phase_ Scans the heap for inaccessible, and hence unmarked,
38 objects, and returns them to an appropriate free list for reuse. This is not
39 really a separate phase; even in non incremental mode this is operation
40 is usually performed on demand during an allocation that discovers an empty
41 free list. Thus the sweep phase is very unlikely to touch a page that would
42 not have been touched shortly thereafter anyway.
43 4. _Finalization phase_ Unreachable objects which had been registered for
44 finalization are enqueued for finalization outside the collector.
45
46 The remaining sections describe the memory allocation data structures, and
47 then the last 3 collection phases in more detail. We conclude by outlining
48 some of the additional features implemented in the collector.
49
50 ## Allocation
51
52 The collector includes its own memory allocator. The allocator obtains memory
53 from the system in a platform-dependent way. Under UNIX, it uses either
54 `malloc`, `sbrk`, or `mmap`.
55
56 Most static data used by the allocator, as well as that needed by the rest
57 of the garbage collector is stored inside the `_GC_arrays` structure. This
58 allows the garbage collector to easily ignore the collectors own data
59 structures when it searches for root pointers. Other allocator and collector
60 internal data structures are allocated dynamically with `GC_scratch_alloc`.
61 `GC_scratch_alloc` does not allow for deallocation, and is therefore used only
62 for permanent data structures.
63
64 The allocator allocates objects of different _kinds_. Different kinds are
65 handled somewhat differently by certain parts of the garbage collector.
66 Certain kinds are scanned for pointers, others are not. Some may have
67 per-object type descriptors that determine pointer locations. Or a specific
68 kind may correspond to one specific object layout. Two built-in kinds are
69 uncollectible.
70 In spite of that, it is very likely that most C clients of the collector
71 currently use at most two kinds: `NORMAL` and `PTRFREE` objects. The
72 [GCJ](https://gcc.gnu.org/onlinedocs/gcc-4.8.5/gcj/) runtime also makes heavy
73 use of a kind (allocated with `GC_gcj_malloc`) that stores type information
74 at a known offset in method tables.
75
76 The collector uses a two level allocator. A large block is defined to be one
77 larger than half of `HBLKSIZE`, which is a power of 2, typically on the order
78 of the page size.
79
80 Large block sizes are rounded up to the next multiple of `HBLKSIZE` and then
81 allocated by `GC_allochblk`. Recent versions of the collector use an
82 approximate best fit algorithm by keeping free lists for several large block
83 sizes. The actual implementation of `GC_allochblk` is significantly
84 complicated by black-listing issues (see below).
85
86 Small blocks are allocated in chunks of size `HBLKSIZE`. Each chunk
87 is dedicated to only one object size and kind.
88
89 The allocator maintains separate free lists for each size and kind of object.
90 Associated with each kind is an array of free list pointers, with entry
91 `freelist[i]` pointing to a free list of size 'i' objects. In recent versions
92 of the collector, index `i` is expressed in granules, which are the minimum
93 allocatable unit, typically 8 or 16 bytes. The free lists themselves are
94 linked through the first word in each object (see `obj_link` macro).
95
96 Once a large block is split for use in smaller objects, it can only be used
97 for objects of that size, unless the collector discovers a completely empty
98 chunk. Completely empty chunks are restored to the appropriate large block
99 free list.
100
101 In order to avoid allocating blocks for too many distinct object sizes, the
102 collector normally does not directly allocate objects of every possible
103 request size. Instead, the request is rounded up to one of a smaller number
104 of allocated sizes, for which free lists are maintained. The exact allocated
105 sizes are computed on demand, but subject to the constraint that they increase
106 roughly in geometric progression. Thus objects requested early in the
107 execution are likely to be allocated with exactly the requested size, subject
108 to alignment constraints. See `GC_init_size_map` for details.
109
110 The actual size rounding operation during small object allocation
111 is implemented as a table lookup in `GC_size_map` which maps a requested
112 allocation size in bytes to a number of granules.
113
114 Both collector initialization and computation of allocated sizes are handled
115 carefully so that they do not slow down the small object fast allocation path.
116 An attempt to allocate before the collector is initialized, or before the
117 appropriate `GC_size_map` entry is computed, will take the same path as an
118 allocation attempt with an empty free list. This results in a call to the slow
119 path code (`GC_generic_malloc_inner`) which performs the appropriate
120 initialization checks.
121
122 In non-incremental mode, we make a decision about whether to garbage collect
123 whenever an allocation would otherwise have failed with the current heap size.
124 If the total amount of allocation since the last collection is less than the
125 heap size divided by `GC_free_space_divisor`, we try to expand the heap.
126 Otherwise, we initiate a garbage collection. This ensures that the amount
127 of garbage collection work per allocated byte remains constant.
128
129 The above is in fact an oversimplification of the real heap expansion and GC
130 triggering heuristic, which adjusts slightly for root size and certain kinds
131 of fragmentation. In particular:
132
133 * Programs with a large root set size and little live heap memory will
134 expand the heap to amortize the cost of scanning the roots.
135 * GC v5 actually collect more frequently in non-incremental mode. The large
136 block allocator usually refuses to split large heap blocks once the garbage
137 collection threshold is reached. This often has the effect of collecting
138 well before the heap fills up, thus reducing fragmentation and working set
139 size at the expense of GC time. GC v6 chooses an intermediate strategy
140 depending on how much large object allocation has taken place in the past.
141 (If the collector is configured to unmap unused pages, GC v6 uses the
142 strategy of GC v5.)
143 * In calculating the amount of allocation since the last collection we give
144 partial credit for objects we expect to be explicitly deallocated. Even
145 if all objects are explicitly managed, it is often desirable to collect
146 on rare occasion, since that is our only mechanism for coalescing completely
147 empty chunks.
148
149 It has been suggested that this should be adjusted so that we favor expansion
150 if the resulting heap still fits into physical memory. In many cases, that
151 would no doubt help. But it is tricky to do this in a way that remains robust
152 if multiple application are contending for a single pool of physical memory.
153
154 ## Mark phase
155
156 At each collection, the collector marks all objects that are possibly
157 reachable from pointer variables. Since it cannot generally tell where pointer
158 variables are located, it scans the following _root segments_ for pointers:
159
160 * The registers. Depending on the architecture, this may be done using
161 assembly code, or by calling a `setjmp`-like function which saves register
162 contents on the stack.
163 * The stack(s). In the case of a single-threaded application, on most
164 platforms this is done by scanning the memory between (an approximation of)
165 the current stack pointer and `GC_stackbottom`. (For Intel Itanium, the
166 register stack scanned separately.) The `GC_stackbottom` variable is set in
167 a highly platform-specific way depending on the appropriate configuration
168 information in `gcconfig.h`. Note that the currently active stack needs
169 to be scanned carefully, since callee-save registers of client code may
170 appear inside collector stack frames, which may change during the mark
171 process. This is addressed by scanning some sections of the stack _eagerly_,
172 effectively capturing a snapshot at one point in time.
173 * Static data region(s). In the simplest case, this is the region between
174 `DATASTART` and `DATAEND`, as defined in `gcconfig.h`. However, in most
175 cases, this will also involve static data regions associated with dynamic
176 libraries. These are identified by the mostly platform-specific code
177 in `dyn_load.c`. The marker maintains an explicit stack of memory regions
178 that are known to be accessible, but that have not yet been searched for
179 contained pointers. Each stack entry contains the starting address of the
180 block to be scanned, as well as a descriptor of the block. If no layout
181 information is available for the block, then the descriptor is simply
182 a length. (For other possibilities, see `gc_mark.h`.)
183
184 At the beginning of the mark phase, all root segments (as described above) are
185 pushed on the stack by `GC_push_roots`. (Registers and eagerly processed stack
186 sections are processed by pushing the referenced objects instead of the stack
187 section itself.) If `ALL_INTERIOR_POINTERS` is not defined, then stack roots
188 require special treatment. In this case, the normal marking code ignores
189 interior pointers, but `GC_push_all_stack` explicitly checks for interior
190 pointers and pushes descriptors for target objects.
191
192 The marker is structured to allow incremental marking. Each call
193 to `GC_mark_some` performs a small amount of work towards marking the heap.
194 It maintains explicit state in the form of `GC_mark_state`, which identifies
195 a particular sub-phase. Some other pieces of state, most notably the mark
196 stack, identify how much work remains to be done in each sub-phase. The normal
197 progression of mark states for a stop-the-world collection is:
198
199 1. `MS_INVALID` indicating that there may be accessible unmarked objects.
200 In this case `GC_objects_are_marked` will simultaneously be false, so the
201 mark state is advanced to
202 2. `MS_PUSH_UNCOLLECTABLE` indicating that it suffices to push uncollectible
203 objects, roots, and then mark everything reachable from them. `scan_ptr`
204 is advanced through the heap until all uncollectible objects are pushed, and
205 objects reachable from them are marked. At that point, the next call
206 to `GC_mark_some` calls `GC_push_roots` to push the roots. It the advances
207 the mark state to
208 3. `MS_ROOTS_PUSHED` asserting that once the mark stack is empty, all
209 reachable objects are marked. Once in this state, we work only on emptying
210 the mark stack. Once this is completed, the state changes to
211 4. `MS_NONE` indicating that reachable objects are marked. The core mark
212 routine `GC_mark_from`, is called repeatedly by several of the sub-phases
213 when the mark stack starts to fill up. It is also called repeatedly
214 in `MS_ROOTS_PUSHED` state to empty the mark stack. The routine is designed
215 to only perform a limited amount of marking at each call, so that it can
216 also be used by the incremental collector. It is fairly carefully tuned,
217 since it usually consumes a large majority of the garbage collection time.
218
219 The fact that it performs only a small amount of work per call also allows
220 it to be used as the core routine of the parallel marker. In that case it is
221 normally invoked on thread-private mark stacks instead of the global mark
222 stack. More details can be found [here](scale.md).
223
224 The marker correctly handles mark stack overflows. Whenever the mark stack
225 overflows, the mark state is reset to `MS_INVALID`. Since there are already
226 marked objects in the heap, this eventually forces a complete scan of the
227 heap, searching for pointers, during which any unmarked objects referenced
228 by marked objects are again pushed on the mark stack. This process is repeated
229 until the mark phase completes without a stack overflow. Each time the stack
230 overflows, an attempt is made to grow the mark stack. All pieces of the
231 collector that push regions onto the mark stack have to be careful to ensure
232 forward progress, even in case of repeated mark stack overflows. Every mark
233 attempt results in additional marked objects.
234
235 Each mark stack entry is processed by examining all candidate pointers in the
236 range described by the entry. If the region has no associated type
237 information, then this typically requires that each 4-byte aligned quantity
238 (8-byte aligned with 64-bit pointers) be considered a candidate pointer.
239
240 We determine whether a candidate pointer is actually the address of a heap
241 block. This is done in the following steps:
242
243 * The candidate pointer is checked against rough heap bounds. These heap
244 bounds are maintained such that all actual heap objects fall between them.
245 In order to facilitate black-listing (see below) we also include address
246 regions that the heap is likely to expand into. Most non-pointers fail this
247 initial test.
248 * The candidate pointer is divided into two pieces; the most significant
249 bits identify a `HBLKSIZE`-sized page in the address space, and the least
250 significant bits specify an offset within that page. (A hardware page may
251 actually consist of multiple such pages. HBLKSIZE is usually the page size
252 divided by a small power of two.)
253 * The page address part of the candidate pointer is looked up in
254 a [table](tree.md). Each table entry contains either 0, indicating that
255 the page is not part of the garbage collected heap, a small integer _n_,
256 indicating that the page is part of large object, starting at least _n_
257 pages back, or a pointer to a descriptor for the page. In the first case,
258 the candidate pointer `i` not a true pointer and can be safely ignored.
259 In the last two cases, we can obtain a descriptor for the page containing
260 the beginning of the object.
261 * The starting address of the referenced object is computed. The page
262 descriptor contains the size of the object(s) in that page, the object kind,
263 and the necessary mark bits for those objects. The size information can be
264 used to map the candidate pointer to the object starting address.
265 To accelerate this process, the page header also contains a pointer to
266 a precomputed map of page offsets to displacements from the beginning of an
267 object. The use of this map avoids a potentially slow integer remainder
268 operation in computing the object start address.
269 * The mark bit for the target object is checked and set. If the object was
270 previously unmarked, the object is pushed on the mark stack. The descriptor
271 is read from the page descriptor. (This is computed from information
272 `GC_obj_kinds` when the page is first allocated.)
273
274 At the end of the mark phase, mark bits for left-over free lists are cleared,
275 in case a free list was accidentally marked due to a stray pointer.
276
277 ## Sweep phase
278
279 At the end of the mark phase, all blocks in the heap are examined. Unmarked
280 large objects are immediately returned to the large object free list. Each
281 small object page is checked to see if all mark bits are clear. If so, the
282 entire page is returned to the large object free list. Small object pages
283 containing some reachable object are queued for later sweeping, unless
284 we determine that the page contains very little free space, in which case
285 it is not examined further.
286
287 This initial sweep pass touches only block headers, not the blocks themselves.
288 Thus it does not require significant paging, even if large sections of the
289 heap are not in physical memory.
290
291 Nonempty small object pages are swept when an allocation attempt encounters
292 an empty free list for that object size and kind. Pages for the correct size
293 and kind are repeatedly swept until at least one empty block is found.
294 Sweeping such a page involves scanning the mark bit array in the page header,
295 and building a free list linked through the first words in the objects
296 themselves. This does involve touching the appropriate data page, but in most
297 cases it will be touched only just before it is used for allocation. Hence any
298 paging is essentially unavoidable.
299
300 Except in the case of pointer-free objects, we maintain the invariant that any
301 object in a small object free list is cleared (except possibly for the link
302 field). Thus it becomes the burden of the small object sweep routine to clear
303 objects. This has the advantage that we can easily recover from accidentally
304 marking a free list, though that could also be handled by other means. The
305 collector currently spends a fair amount of time clearing objects, and this
306 approach should probably be revisited. In most configurations, we use
307 specialized sweep routines to handle common small object sizes. Since
308 we allocate one mark bit per word, it becomes easier to examine the relevant
309 mark bits if the object size divides the word length evenly. We also suitably
310 unroll the inner sweep loop in each case. (It is conceivable that
311 profile-based procedure cloning in the compiler could make this unnecessary
312 and counterproductive. I know of no existing compiler to which this applies.)
313
314 The sweeping of small object pages could be avoided completely at the expense
315 of examining mark bits directly in the allocator. This would probably be more
316 expensive, since each allocation call would have to reload a large amount
317 of state (e.g. next object address to be swept, position in mark bit table)
318 before it could do its work. The current scheme keeps the allocator simple and
319 allows useful optimizations in the sweeper.
320
321 ## Finalization
322
323 Both `GC_register_disappearing_link` and `GC_register_finalizer` add the
324 request to a corresponding hash table. The hash table is allocated out of
325 collected memory, but the reference to the finalizable object is hidden from
326 the collector. Currently finalization requests are processed non-incrementally
327 at the end of a mark cycle.
328
329 The collector makes an initial pass over the table of finalizable objects,
330 pushing the contents of unmarked objects onto the mark stack. After pushing
331 each object, the marker is invoked to mark all objects reachable from it. The
332 object itself is not explicitly marked. This assures that objects on which
333 a finalizer depends are neither collected nor finalized.
334
335 If in the process of marking from an object the object itself becomes marked,
336 we have uncovered a cycle involving the object. This usually results in
337 a warning from the collector. Such objects are not finalized, since it may be
338 unsafe to do so. See the more detailed discussion of
339 [finalization semantics](finalization.md).
340
341 Any objects remaining unmarked at the end of this process are added to a queue
342 of objects whose finalizers can be run. Depending on collector configuration,
343 finalizers are dequeued and run either implicitly during allocation calls,
344 or explicitly in response to a user request. (Note that the former
345 is unfortunately both the default and not generally safe. If finalizers
346 perform synchronization, it may result in deadlocks. Nontrivial finalizers
347 generally need to perform synchronization, and thus require a different
348 collector configuration.)
349
350 The collector provides a mechanism for replacing the procedure that is used
351 to mark through objects. This is used both to provide support for Java-style
352 unordered finalization, and to ignore certain kinds of cycles, e.g. those
353 arising from C++ implementations of virtual inheritance.
354
355 ## Generational Collection and Dirty Bits
356
357 We basically use the concurrent and generational GC algorithm described in
358 ["Mostly Parallel Garbage Collection"](http://www.hboehm.info/gc/papers/pldi91.ps.Z),
359 by Boehm, Demers, and Shenker.
360
361 The most significant modification is that the collector always starts running
362 in the allocating thread. There is no separate garbage collector thread. (If
363 parallel GC is enabled, helper threads may also be woken up.) If an allocation
364 attempt either requests a large object, or encounters an empty small object
365 free list, and notices that there is a collection in progress, it immediately
366 performs a small amount of marking work as described above.
367
368 This change was made both because we wanted to easily accommodate
369 single-threaded environments, and because a separate GC thread requires very
370 careful control over the scheduler to prevent the mutator from out-running the
371 collector, and hence provoking unneeded heap growth.
372
373 In incremental mode, the heap is always expanded when we encounter
374 insufficient space for an allocation. Garbage collection is triggered whenever
375 we notice that more than `GC_heap_size`/2 * `GC_free_space_divisor` bytes
376 of allocation have taken place. After `GC_full_freq` minor collections a major
377 collection is started.
378
379 All collections initially run uninterrupted until a predetermined amount
380 of time (50 msecs by default) has expired. If this allows the collection
381 to complete entirely, we can avoid correcting for data structure modifications
382 during the collection. If it does not complete, we return control to the
383 mutator, and perform small amounts of additional GC work during those later
384 allocations that cannot be satisfied from small object free lists. When
385 marking completes, the set of modified pages is retrieved, and we mark once
386 again from marked objects on those pages, this time with the mutator stopped.
387
388 We keep track of modified pages using one of several distinct mechanisms:
389
390 * (`MPROTECT_VDB`) By write-protecting physical pages and catching write
391 faults. This is implemented for many Unix-like systems and for Win32. It is
392 not possible in a few environments.
393 * (`GWW_VDB`) By using the Win32 `GetWriteWatch` function to read dirty
394 bits.
395 * (`PROC_VDB`) By retrieving dirty bit information from /proc. (Currently
396 only Sun's Solaris supports this. Though this is considerably cleaner,
397 performance may actually be better with `mprotect` and signals.)
398 * (`PCR_VDB`) By relying on an external dirty bit implementation, in this
399 case the one in Xerox PCR.
400 * (`MANUAL_VDB`) Through explicit mutator cooperation. This requires the
401 client code to call `GC_end_stubborn_change`, and is rarely used.
402 * (`DEFAULT_VDB`) By treating all pages as dirty. This is the default
403 if none of the other techniques is known to be usable. (Practical only for
404 testing.)
405
406 ## Black-listing
407
408 The collector implements _black-listing_ of pages, as described in
409 ["Space Efficient Conservative Collection", PLDI'93](http://dl.acm.org/citation.cfm?doid=155090.155109)
410 by Boehm, also available
411 [here](https://www.cs.rice.edu/~javaplt/311/Readings/pldi93.pdf).
412
413 During the mark phase, the collector tracks _near misses_, i.e. attempts
414 to follow a _pointer_ to just outside the garbage-collected heap, or to
415 a currently unallocated page inside the heap. Pages that have been the targets
416 of such near misses are likely to be the targets of misidentified _pointers_
417 in the future. To minimize the future damage caused by such misidentification,
418 they will be allocated only to small pointer-free objects.
419
420 The collector understands two different kinds of black-listing. A page may be
421 black listed for interior pointer references (`GC_add_to_black_list_stack`),
422 if it was the target of a near miss from a location that requires interior
423 pointer recognition, e.g. the stack, or the heap if `GC_all_interior_pointers`
424 is set. In this case, we also avoid allocating large blocks that include this
425 page.
426
427 If the near miss came from a source that did not require interior pointer
428 recognition, it is black-listed with `GC_add_to_black_list_normal`. A page
429 black-listed in this way may appear inside a large object, so long as it is
430 not the first page of a large object.
431
432 The `GC_allochblk` routine respects black-listing when assigning a block to
433 a particular object kind and size. It occasionally drops (i.e. allocates and
434 forgets) blocks that are completely black-listed in order to avoid excessively
435 long large block free lists containing only unusable blocks. This would
436 otherwise become an issue if there is low demand for small pointer-free
437 objects.
438
439 ## Thread support
440
441 We support several different threading models. Unfortunately Pthreads, the
442 only reasonably well standardized thread model, supports too narrow
443 an interface for conservative garbage collection. There appears to be no
444 completely portable way to allow the collector to coexist with various
445 Pthreads implementations. Hence we currently support only the more common
446 Pthreads implementations.
447
448 In particular, it is very difficult for the collector to stop all other
449 threads in the system and examine the register contents. This is currently
450 accomplished with very different mechanisms for some Pthreads implementations.
451 For Linux/HPUX/OSF1, Solaris and Irix it sends signals to individual Pthreads
452 and has them wait in the signal handler.
453
454 The Linux and Irix implementations use only documented Pthreads calls, but
455 rely on extensions to their semantics. The Linux implementation
456 `pthread_stop_world.c` relies on only very mild extensions to the pthreads
457 semantics, and already supports a large number of other Unix-like pthreads
458 implementations. Our goal is to make this the only pthread support in the
459 collector.
460
461 All implementations must intercept thread creation and a few other
462 thread-specific calls to allow enumeration of threads and location of thread
463 stacks. This is current accomplished with `#define`'s in `gc.h` (really
464 `gc_pthread_redirects.h`), or optionally by using `ld`'s function call
465 wrapping mechanism under Linux.
466
467 Recent versions of the collector support several facilities to enhance the
468 processor-scalability and thread performance of the collector. These are
469 discussed in more detail [here](scale.md). We briefly outline the data
470 approach to thread-local allocation in the next section.
471
472 ## Thread-local allocation
473
474 If thread-local allocation is enabled, the collector keeps separate arrays
475 of free lists for each thread. Thread-local allocation is currently only
476 supported on a few platforms.
477
478 The free list arrays associated with each thread are only used to satisfy
479 requests for objects that are both very small, and belong to one of a small
480 number of well-known kinds. These currently include _normal_ and pointer-free
481 objects. Depending on the configuration, _gcj_ objects may also be included.
482
483 Thread-local free list entries contain either a pointer to the first element
484 of a free list, or they contain a counter of the number of allocation
485 granules, corresponding to objects of this size, allocated so far. Initially
486 they contain the value one, i.e. a small counter value.
487
488 Thread-local allocation allocates directly through the global allocator,
489 if the object is of a size or kind not covered by the local free lists.
490
491 If there is an appropriate local free list, the allocator checks whether
492 it contains a sufficiently small counter value. If so, the counter is simply
493 incremented by the counter value, and the global allocator is used. In this
494 way, the initial few allocations of a given size bypass the local allocator.
495 A thread that only allocates a handful of objects of a given size will not
496 build up its own free list for that size. This avoids wasting space for
497 unpopular objects sizes or kinds.
498
499 Once the counter passes a threshold, `GC_malloc_many` is called to allocate
500 roughly `HBLKSIZE` space and put it on the corresponding local free list.
501 Further allocations of that size and kind then use this free list, and no
502 longer need to acquire the allocation lock. The allocation procedure
503 is otherwise similar to the global free lists. The local free lists are also
504 linked using the first word in the object. In most cases this means they
505 require considerably less time.
506
507 Local free lists are treated buy most of the rest of the collector as though
508 they were in-use reachable data. This requires some care, since pointer-free
509 objects are not normally traced, and hence a special tracing procedure
510 is required to mark all objects on pointer-free and gcj local free lists.
511
512 On thread exit, any remaining thread-local free list entries are transferred
513 back to the global free list.
514
515 Note that if the collector is configured for thread-local allocation,
516 `GC_malloc` only uses thread-local allocation (starting from GC v7).
517
518 For some more details see [here](scale.md), and the technical report entitled
519 ["Fast Multiprocessor Memory Allocation and Garbage Collection"](http://www.hpl.hp.com/techreports/2000/HPL-2000-165.html).