1#include "internal.h"
2
3/* Free_queue function naming semantics:
4 *
5 * "Draining" is when the free_queue elements are removed one by one,
6 * and each element first tries to get put on a given per-core
7 * cache's magazines. The free_queue elements that do not fit in the
8 * magazine are then optionally freed from the slab cache or re-enqueued.
9 *
10 * "Flushing" is when the free_queue elements are all freed from the
11 * slab cache. The per-core magazines are not touched */
12
13void slab_free_queue_init(struct slab_domain *domain, struct slab_free_queue *q,
14 size_t capacity) {
15 q->capacity = capacity;
16 q->slots =
17 kmalloc(sizeof(struct slab_free_slot) * capacity, ALLOC_FLAGS_ZERO);
18 if (!q->slots)
19 panic("Could not allocate slab free queue slots!");
20
21 atomic_store(&q->head, 0);
22 atomic_store(&q->tail, 0);
23
24 for (size_t i = 0; i < capacity; i++)
25 atomic_store(&q->slots[i].seq, i);
26
27 q->parent = domain;
28 q->count = 0;
29}
30
31bool slab_free_queue_ringbuffer_enqueue(struct slab_free_queue *q,
32 vaddr_t addr) {
33 uint64_t pos;
34 struct slab_free_slot *slot;
35 uint64_t seq;
36 int64_t diff;
37
38 while (true) {
39 pos = atomic_load_explicit(&q->head, memory_order_relaxed);
40 slot = &q->slots[pos % q->capacity];
41 seq = atomic_load_explicit(&slot->seq, memory_order_acquire);
42 diff = (int64_t) seq - (int64_t) pos;
43
44 if (diff == 0) {
45 if (atomic_compare_exchange_weak_explicit(&q->head, &pos, pos + 1,
46 memory_order_acq_rel,
47 memory_order_relaxed)) {
48
49 slot->addr = addr;
50
51 atomic_store_explicit(&slot->seq, pos + 1,
52 memory_order_release);
53
54 SLAB_FREE_QUEUE_INC_COUNT(q);
55 return true;
56 }
57 } else if (diff < 0) {
58 return false;
59 }
60 }
61}
62
63vaddr_t slab_free_queue_ringbuffer_dequeue(struct slab_free_queue *q) {
64 uint64_t pos;
65 struct slab_free_slot *slot;
66 uint64_t seq;
67 int64_t diff;
68
69 while (true) {
70 pos = atomic_load_explicit(&q->tail, memory_order_relaxed);
71 slot = &q->slots[pos % q->capacity];
72 seq = atomic_load_explicit(&slot->seq, memory_order_acquire);
73 diff = (int64_t) seq - (int64_t) (pos + 1);
74
75 if (diff == 0) {
76 if (atomic_compare_exchange_weak_explicit(&q->tail, &pos, pos + 1,
77 memory_order_acq_rel,
78 memory_order_relaxed)) {
79
80 vaddr_t ret = slot->addr;
81 slot->addr = 0;
82
83 atomic_store_explicit(&slot->seq, pos + q->capacity,
84 memory_order_release);
85
86 SLAB_FREE_QUEUE_DEC_COUNT(q);
87 return ret;
88 }
89 } else if (diff < 0) {
90 return 0x0;
91 }
92 }
93}
94
95bool slab_free_queue_enqueue(struct slab_free_queue *q, vaddr_t addr) {
96 return slab_free_queue_ringbuffer_enqueue(q, addr);
97}
98
99vaddr_t slab_free_queue_dequeue(struct slab_free_queue *q) {
100 return slab_free_queue_ringbuffer_dequeue(q);
101}
102
103static void slab_free_queue_free(struct slab_domain *d, void *ptr,
104 enum alloc_behavior bh) {
105 int32_t class = slab_size_to_index(size: ksize(ptr));
106 bool fits_in_slab = class >= 0;
107
108 if (fits_in_slab)
109 return slab_free(domain: d, obj: ptr);
110
111 struct slab_page_hdr *header = slab_page_hdr_for_addr(ptr);
112 return slab_free_page_hdr(hdr: header, bh);
113}
114
115size_t slab_free_queue_drain(struct slab_percpu_cache *cache,
116 struct slab_free_queue *queue, size_t target,
117 enum alloc_behavior bh) {
118 kassert(cache == slab_percpu_cache_local());
119 size_t drained_to_magazine = 0; /* Return value */
120 size_t addrs_dequeued = 0; /* Used to check against `target` */
121
122 while (true) {
123 if (addrs_dequeued >= target)
124 break;
125
126 /* Drain an element from our free_queue */
127 vaddr_t addr = slab_free_queue_dequeue(q: queue);
128 if (!addr)
129 break;
130
131 addrs_dequeued++;
132
133 /* What class? */
134 int32_t class = slab_size_to_index(size: slab_allocation_size(addr));
135 if (class < 0)
136 goto flush;
137
138 /* Magazines only cache nonpageable addresses */
139 struct slab *slab = slab_for_ptr(ptr: (void *) addr);
140 if (slab_is_pageable(s: slab))
141 goto flush;
142
143 /* Push it onto the magazine */
144 enum slab_magazine_type mtype =
145 slab_is_zeroed(s: slab) ? SLAB_MAGAZINE_ZERO : SLAB_MAGAZINE_NORMAL;
146
147 if (mtype == SLAB_MAGAZINE_ZERO)
148 memset((void *) addr, 0, slab->parent_cache->obj_size);
149
150 struct slab_magazine *mag = &cache->mags[mtype][class];
151 if (!slab_magazine_push(mag, obj: addr))
152 goto flush;
153
154 /* Success - pushed onto magazine */
155 drained_to_magazine++;
156 continue;
157
158 flush:
159 slab_free_queue_free(d: cache->domain, ptr: (void *) addr, bh);
160 }
161
162 return drained_to_magazine;
163}
164
165size_t slab_free_queue_flush(struct slab_domain *domain,
166 struct slab_free_queue *queue) {
167 size_t total_freed = 0;
168
169 /* Drain the ringbuffer one element at a time */
170 while (true) {
171 vaddr_t addr = slab_free_queue_ringbuffer_dequeue(q: queue);
172 if (addr == 0x0)
173 break;
174
175 slab_free(domain, obj: (void *) addr);
176 }
177 return total_freed;
178}
179
180size_t slab_free_queue_get_target_drain(struct slab_domain *domain,
181 size_t pct) {
182 size_t slab_domain_cpus = domain->domain->num_cores;
183 size_t total_fq_elems = SLAB_FREE_QUEUE_GET_COUNT(&domain->free_queue);
184 size_t portion = slab_domain_cpus / SLAB_PERCPU_REFILL_PER_CORE_WEIGHT;
185 if (portion == 0)
186 portion = 1;
187
188 return (total_fq_elems / portion) * pct / 100;
189}
190
191size_t slab_free_queue_drain_limited(struct slab_percpu_cache *pc,
192 struct slab_domain *dom, size_t pct,
193 enum alloc_behavior bh) {
194 size_t target = slab_free_queue_get_target_drain(domain: dom, pct);
195
196 /* This will also fill up the magazines for other orders. We set the target
197 * to prevent overly aggressive stealing from the free_queue into our
198 * percpu cache to allow other CPUs in our domain to get their fair share of
199 * what remains in the free_queue in the event that they must also refill */
200 return slab_free_queue_drain(cache: pc, queue: &dom->free_queue, target, bh);
201}
202