/home/travis/build/MoarVM/MoarVM/src/core/fixedsizealloc.h
Line | Count | Source |
1 | | /* The global, top-level data structure for the fixed size allocator. */ |
2 | | struct MVMFixedSizeAlloc { |
3 | | /* Size classes for the fixed size allocator. Each one represents a bunch |
4 | | * of objects of the same size. The allocated sizes are rounded and then |
5 | | * one of these buckets is used (more size classes are allocated if a |
6 | | * need arises). */ |
7 | | MVMFixedSizeAllocSizeClass *size_classes; |
8 | | |
9 | | /* Spin lock used for reading from the free list, to avoid ABA. */ |
10 | | AO_t freelist_spin; |
11 | | |
12 | | /* Mutex for when we can't do a cheap/simple allocation. */ |
13 | | uv_mutex_t complex_alloc_mutex; |
14 | | |
15 | | /* Head of the "free at next safepoint" list of overflows (that is, |
16 | | * items that don't fit in a fixed size allocator bin). */ |
17 | | MVMFixedSizeAllocSafepointFreeListEntry *free_at_next_safepoint_overflows; |
18 | | }; |
19 | | |
20 | | /* Free list entry. Must be no bigger than the smallest size class. */ |
21 | | struct MVMFixedSizeAllocFreeListEntry { |
22 | | void *next; |
23 | | }; |
24 | | |
25 | | /* Entry in the "free at next safe point" linked list. */ |
26 | | struct MVMFixedSizeAllocSafepointFreeListEntry { |
27 | | void *to_free; |
28 | | MVMFixedSizeAllocSafepointFreeListEntry *next; |
29 | | }; |
30 | | |
31 | | /* Pages of objects of a particular size class. */ |
32 | | struct MVMFixedSizeAllocSizeClass { |
33 | | /* Each page holds allocated chunks of memory. */ |
34 | | char **pages; |
35 | | |
36 | | /* Head of the free list. */ |
37 | | MVMFixedSizeAllocFreeListEntry *free_list; |
38 | | |
39 | | /* The current allocation position if we've nothing on the |
40 | | * free list. */ |
41 | | char *alloc_pos; |
42 | | |
43 | | /* The current page allocation limit (once we hit this, we need |
44 | | * to go to the next page) Also just used when no free list. */ |
45 | | char *alloc_limit; |
46 | | |
47 | | /* The current page number that we're allocating in. */ |
48 | | MVMuint32 cur_page; |
49 | | |
50 | | /* The number of pages allocated. */ |
51 | | MVMuint32 num_pages; |
52 | | |
53 | | /* Head of the "free at next safepoint" list. */ |
54 | | MVMFixedSizeAllocSafepointFreeListEntry *free_at_next_safepoint_list; |
55 | | }; |
56 | | |
57 | | /* The per-thread data structure for the fixed size allocator, hung off the |
58 | | * thread context. Holds a free list per size bin. Allocations on the thread |
59 | | * will preferentially use the thread free list, and threads will free to |
60 | | * their own free lists, up to a length limit. On hitting the limit, they |
61 | | * will free back to the global allocator. This helps ensure patterns like |
62 | | * producer/consumer don't end up with a "leak". */ |
63 | | struct MVMFixedSizeAllocThread { |
64 | | MVMFixedSizeAllocThreadSizeClass *size_classes; |
65 | | }; |
66 | | struct MVMFixedSizeAllocThreadSizeClass { |
67 | | /* Head of the free list. */ |
68 | | MVMFixedSizeAllocFreeListEntry *free_list; |
69 | | |
70 | | /* How many items are on this thread's free list. */ |
71 | | MVMuint32 items; |
72 | | }; |
73 | | |
74 | | /* The number of bits we discard from the requested size when binning |
75 | | * the allocation request into a size class. For example, if this is |
76 | | * 3 bits then: |
77 | | * Request for 2 bytes ==> bin 0 (objects 0 - 8 bytes) |
78 | | * Request for 4 bytes ==> bin 0 (objects 0 - 8 bytes) |
79 | | * Request for 8 bytes ==> bin 0 (objects 0 - 8 bytes) |
80 | | * Request for 12 bytes ==> bin 1 (objects 9 - 16 bytes) |
81 | | * Request for 16 bytes ==> bin 1 (objects 9 - 16 bytes) |
82 | | */ |
83 | 89.4M | #define MVM_FSA_BIN_BITS 3 |
84 | | |
85 | | /* Mask used to know if we hit a size class exactly or have to round up. */ |
86 | 43.1M | #define MVM_FSA_BIN_MASK ((1 << MVM_FSA_BIN_BITS) - 1) |
87 | | |
88 | | /* Number of bins in the FSA. Beyond this, we just degrade to malloc/free. */ |
89 | 43.1M | #define MVM_FSA_BINS 96 |
90 | | |
91 | | /* The number of items that go into each page. */ |
92 | 72.2k | #define MVM_FSA_PAGE_ITEMS 128 |
93 | | |
94 | | /* The length limit for the per-thread free list. */ |
95 | 19.9M | #define MVM_FSA_THREAD_FREELIST_LIMIT 1024 |
96 | | |
97 | | /* Functions. */ |
98 | | MVMFixedSizeAlloc * MVM_fixed_size_create(MVMThreadContext *tc); |
99 | | void MVM_fixed_size_create_thread(MVMThreadContext *tc); |
100 | | void * MVM_fixed_size_alloc(MVMThreadContext *tc, MVMFixedSizeAlloc *fsa, size_t bytes); |
101 | | void * MVM_fixed_size_alloc_zeroed(MVMThreadContext *tc, MVMFixedSizeAlloc *fsa, size_t bytes); |
102 | | void * MVM_fixed_size_realloc(MVMThreadContext *tc, MVMFixedSizeAlloc *al, void * p, size_t old_bytes, size_t new_bytes); |
103 | | void * MVM_fixed_size_realloc_at_safepoint(MVMThreadContext *tc, MVMFixedSizeAlloc *al, void * p, size_t old_bytes, size_t new_bytes); |
104 | | void MVM_fixed_size_destroy(MVMFixedSizeAlloc *al); |
105 | | void MVM_fixed_size_destroy_thread(MVMThreadContext *tc); |
106 | | void MVM_fixed_size_free(MVMThreadContext *tc, MVMFixedSizeAlloc *fsa, size_t bytes, void *free); |
107 | | void MVM_fixed_size_free_at_safepoint(MVMThreadContext *tc, MVMFixedSizeAlloc *fsa, size_t bytes, void *free); |
108 | | void MVM_fixed_size_safepoint(MVMThreadContext *tc, MVMFixedSizeAlloc *al); |