Debian Codegraph @

rts/c/free_list.h

raw
1 // Start of free_list.h.
2
3 typedef uintptr_t fl_mem;
4
5 // An entry in the free list. May be invalid, to avoid having to
6 // deallocate entries as soon as they are removed. There is also a
7 // tag, to help with memory reuse.
8 struct free_list_entry {
9 size_t size;
10 fl_mem mem;
11 const char *tag;
12 unsigned char valid;
13 };
14
15 struct free_list {
16 struct free_list_entry *entries; // Pointer to entries.
17 int capacity; // Number of entries.
18 int used; // Number of valid entries.
19 lock_t lock; // Thread safety.
20 };
21
22 static void free_list_init(struct free_list *l) {
23 l->capacity = 30; // Picked arbitrarily.
24 l->used = 0;
25 l->entries = (struct free_list_entry*) malloc(sizeof(struct free_list_entry) * l->capacity);
26 for (int i = 0; i < l->capacity; i++) {
27 l->entries[i].valid = 0;
28 }
29 create_lock(&l->lock);
30 }
31
32 // Remove invalid entries from the free list.
33 static void free_list_pack(struct free_list *l) {
34 lock_lock(&l->lock);
35 int p = 0;
36 for (int i = 0; i < l->capacity; i++) {
37 if (l->entries[i].valid) {
38 l->entries[p] = l->entries[i];
39 if (i > p) {
40 l->entries[i].valid = 0;
41 }
42 p++;
43 }
44 }
45
46 // Now p is the number of used elements. We don't want it to go
47 // less than the default capacity (although in practice it's OK as
48 // long as it doesn't become 1).
49 if (p < 30) {
50 p = 30;
51 }
52 l->entries = realloc(l->entries, p * sizeof(struct free_list_entry));
53 l->capacity = p;
54 lock_unlock(&l->lock);
55 }
56
57 static void free_list_destroy(struct free_list *l) {
58 assert(l->used == 0);
59 free(l->entries);
60 free_lock(&l->lock);
61 }
62
63 // Not part of the interface, so no locking.
64 static int free_list_find_invalid(struct free_list *l) {
65 int i;
66 for (i = 0; i < l->capacity; i++) {
67 if (!l->entries[i].valid) {
68 break;
69 }
70 }
71 return i;
72 }
73
74 static void free_list_insert(struct free_list *l, size_t size, fl_mem mem, const char *tag) {
75 lock_lock(&l->lock);
76 int i = free_list_find_invalid(l);
77
78 if (i == l->capacity) {
79 // List is full; so we have to grow it.
80 int new_capacity = l->capacity * 2 * sizeof(struct free_list_entry);
81 l->entries = realloc(l->entries, new_capacity);
82 for (int j = 0; j < l->capacity; j++) {
83 l->entries[j+l->capacity].valid = 0;
84 }
85 l->capacity *= 2;
86 }
87
88 // Now 'i' points to the first invalid entry.
89 l->entries[i].valid = 1;
90 l->entries[i].size = size;
91 l->entries[i].mem = mem;
92 l->entries[i].tag = tag;
93
94 l->used++;
95 lock_unlock(&l->lock);
96 }
97
98 // Determine whether this entry in the free list is acceptable for
99 // satisfying the request. Not public, so no locking.
100 static bool free_list_acceptable(size_t size, const char* tag, struct free_list_entry *entry) {
101 // We check not just the hard requirement (is the entry acceptable
102 // and big enough?) but also put a cap on how much wasted space
103 // (internal fragmentation) we allow. This is necessarily a
104 // heuristic, and a crude one.
105
106 if (!entry->valid) {
107 return false;
108 }
109
110 if (size > entry->size) {
111 return false;
112 }
113
114 // We know the block fits. Now the question is whether it is too
115 // big. Our policy is as follows:
116 //
117 // 1) We don't care about wasted space below 4096 bytes (to avoid
118 // churn in tiny allocations).
119 //
120 // 2) If the tag matches, we allow _any_ amount of wasted space.
121 //
122 // 3) Otherwise we allow up to 50% wasted space.
123
124 if (entry->size < 4096) {
125 return true;
126 }
127
128 if (entry->tag == tag) {
129 return true;
130 }
131
132 if (entry->size < size * 2) {
133 return true;
134 }
135
136 return false;
137 }
138
139 // Find and remove a memory block of the indicated tag, or if that
140 // does not exist, another memory block with exactly the desired size.
141 // Returns 0 on success.
142 static int free_list_find(struct free_list *l, size_t size, const char *tag,
143 size_t *size_out, fl_mem *mem_out) {
144 lock_lock(&l->lock);
145 int size_match = -1;
146 int i;
147 int ret = 1;
148 for (i = 0; i < l->capacity; i++) {
149 if (free_list_acceptable(size, tag, &l->entries[i]) &&
150 (size_match < 0 || l->entries[i].size < l->entries[size_match].size)) {
151 // If this entry is valid, has sufficient size, and is smaller than the
152 // best entry found so far, use this entry.
153 size_match = i;
154 }
155 }
156
157 if (size_match >= 0) {
158 l->entries[size_match].valid = 0;
159 *size_out = l->entries[size_match].size;
160 *mem_out = l->entries[size_match].mem;
161 l->used--;
162 ret = 0;
163 }
164 lock_unlock(&l->lock);
165 return ret;
166 }
167
168 // Remove the first block in the free list. Returns 0 if a block was
169 // removed, and nonzero if the free list was already empty.
170 static int free_list_first(struct free_list *l, fl_mem *mem_out) {
171 lock_lock(&l->lock);
172 int ret = 1;
173 for (int i = 0; i < l->capacity; i++) {
174 if (l->entries[i].valid) {
175 l->entries[i].valid = 0;
176 *mem_out = l->entries[i].mem;
177 l->used--;
178 ret = 0;
179 break;
180 }
181 }
182 lock_unlock(&l->lock);
183 return ret;
184 }
185
186 // End of free_list.h.