Branch data Line data Source code
1 : : // SPDX-License-Identifier: GPL-2.0-only
2 : : /* Copyright (c) 2016 Facebook
3 : : */
4 : : #include <linux/cpumask.h>
5 : : #include <linux/spinlock.h>
6 : : #include <linux/percpu.h>
7 : :
8 : : #include "bpf_lru_list.h"
9 : :
10 : : #define LOCAL_FREE_TARGET (128)
11 : : #define LOCAL_NR_SCANS LOCAL_FREE_TARGET
12 : :
13 : : #define PERCPU_FREE_TARGET (4)
14 : : #define PERCPU_NR_SCANS PERCPU_FREE_TARGET
15 : :
16 : : /* Helpers to get the local list index */
17 : : #define LOCAL_LIST_IDX(t) ((t) - BPF_LOCAL_LIST_T_OFFSET)
18 : : #define LOCAL_FREE_LIST_IDX LOCAL_LIST_IDX(BPF_LRU_LOCAL_LIST_T_FREE)
19 : : #define LOCAL_PENDING_LIST_IDX LOCAL_LIST_IDX(BPF_LRU_LOCAL_LIST_T_PENDING)
20 : : #define IS_LOCAL_LIST_TYPE(t) ((t) >= BPF_LOCAL_LIST_T_OFFSET)
21 : :
22 : 0 : static int get_next_cpu(int cpu)
23 : : {
24 : 0 : cpu = cpumask_next(cpu, cpu_possible_mask);
25 [ # # ]: 0 : if (cpu >= nr_cpu_ids)
26 : : cpu = cpumask_first(cpu_possible_mask);
27 : 0 : return cpu;
28 : : }
29 : :
30 : : /* Local list helpers */
31 : : static struct list_head *local_free_list(struct bpf_lru_locallist *loc_l)
32 : : {
33 : 0 : return &loc_l->lists[LOCAL_FREE_LIST_IDX];
34 : : }
35 : :
36 : : static struct list_head *local_pending_list(struct bpf_lru_locallist *loc_l)
37 : : {
38 : 0 : return &loc_l->lists[LOCAL_PENDING_LIST_IDX];
39 : : }
40 : :
41 : : /* bpf_lru_node helpers */
42 : : static bool bpf_lru_node_is_ref(const struct bpf_lru_node *node)
43 : : {
44 : 0 : return node->ref;
45 : : }
46 : :
47 : : static void bpf_lru_list_count_inc(struct bpf_lru_list *l,
48 : : enum bpf_lru_list_type type)
49 : : {
50 [ # # # # ]: 0 : if (type < NR_BPF_LRU_LIST_COUNT)
51 : 0 : l->counts[type]++;
52 : : }
53 : :
54 : : static void bpf_lru_list_count_dec(struct bpf_lru_list *l,
55 : : enum bpf_lru_list_type type)
56 : : {
57 [ # # # # ]: 0 : if (type < NR_BPF_LRU_LIST_COUNT)
58 : 0 : l->counts[type]--;
59 : : }
60 : :
61 : 0 : static void __bpf_lru_node_move_to_free(struct bpf_lru_list *l,
62 : : struct bpf_lru_node *node,
63 : : struct list_head *free_list,
64 : : enum bpf_lru_list_type tgt_free_type)
65 : : {
66 [ # # # # : 0 : if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))
# # ]
67 : 0 : return;
68 : :
69 : : /* If the removing node is the next_inactive_rotation candidate,
70 : : * move the next_inactive_rotation pointer also.
71 : : */
72 [ # # ]: 0 : if (&node->list == l->next_inactive_rotation)
73 : 0 : l->next_inactive_rotation = l->next_inactive_rotation->prev;
74 : :
75 : 0 : bpf_lru_list_count_dec(l, node->type);
76 : :
77 : 0 : node->type = tgt_free_type;
78 : : list_move(&node->list, free_list);
79 : : }
80 : :
81 : : /* Move nodes from local list to the LRU list */
82 : 0 : static void __bpf_lru_node_move_in(struct bpf_lru_list *l,
83 : : struct bpf_lru_node *node,
84 : : enum bpf_lru_list_type tgt_type)
85 : : {
86 [ # # # # : 0 : if (WARN_ON_ONCE(!IS_LOCAL_LIST_TYPE(node->type)) ||
# # # # ]
87 [ # # # # ]: 0 : WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(tgt_type)))
88 : 0 : return;
89 : :
90 : : bpf_lru_list_count_inc(l, tgt_type);
91 : 0 : node->type = tgt_type;
92 : 0 : node->ref = 0;
93 : 0 : list_move(&node->list, &l->lists[tgt_type]);
94 : : }
95 : :
96 : : /* Move nodes between or within active and inactive list (like
97 : : * active to inactive, inactive to active or tail of active back to
98 : : * the head of active).
99 : : */
100 : 0 : static void __bpf_lru_node_move(struct bpf_lru_list *l,
101 : : struct bpf_lru_node *node,
102 : : enum bpf_lru_list_type tgt_type)
103 : : {
104 [ # # # # : 0 : if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)) ||
# # # # ]
105 [ # # # # ]: 0 : WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(tgt_type)))
106 : 0 : return;
107 : :
108 [ # # ]: 0 : if (node->type != tgt_type) {
109 : : bpf_lru_list_count_dec(l, node->type);
110 : : bpf_lru_list_count_inc(l, tgt_type);
111 : 0 : node->type = tgt_type;
112 : : }
113 : 0 : node->ref = 0;
114 : :
115 : : /* If the moving node is the next_inactive_rotation candidate,
116 : : * move the next_inactive_rotation pointer also.
117 : : */
118 [ # # ]: 0 : if (&node->list == l->next_inactive_rotation)
119 : 0 : l->next_inactive_rotation = l->next_inactive_rotation->prev;
120 : :
121 : 0 : list_move(&node->list, &l->lists[tgt_type]);
122 : : }
123 : :
124 : : static bool bpf_lru_list_inactive_low(const struct bpf_lru_list *l)
125 : : {
126 : 0 : return l->counts[BPF_LRU_LIST_T_INACTIVE] <
127 : 0 : l->counts[BPF_LRU_LIST_T_ACTIVE];
128 : : }
129 : :
130 : : /* Rotate the active list:
131 : : * 1. Start from tail
132 : : * 2. If the node has the ref bit set, it will be rotated
133 : : * back to the head of active list with the ref bit cleared.
134 : : * Give this node one more chance to survive in the active list.
135 : : * 3. If the ref bit is not set, move it to the head of the
136 : : * inactive list.
137 : : * 4. It will at most scan nr_scans nodes
138 : : */
139 : 0 : static void __bpf_lru_list_rotate_active(struct bpf_lru *lru,
140 : : struct bpf_lru_list *l)
141 : : {
142 : : struct list_head *active = &l->lists[BPF_LRU_LIST_T_ACTIVE];
143 : : struct bpf_lru_node *node, *tmp_node, *first_node;
144 : : unsigned int i = 0;
145 : :
146 : 0 : first_node = list_first_entry(active, struct bpf_lru_node, list);
147 [ # # ]: 0 : list_for_each_entry_safe_reverse(node, tmp_node, active, list) {
148 [ # # ]: 0 : if (bpf_lru_node_is_ref(node))
149 : 0 : __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
150 : : else
151 : 0 : __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);
152 : :
153 [ # # # # ]: 0 : if (++i == lru->nr_scans || node == first_node)
154 : : break;
155 : : }
156 : 0 : }
157 : :
158 : : /* Rotate the inactive list. It starts from the next_inactive_rotation
159 : : * 1. If the node has ref bit set, it will be moved to the head
160 : : * of active list with the ref bit cleared.
161 : : * 2. If the node does not have ref bit set, it will leave it
162 : : * at its current location (i.e. do nothing) so that it can
163 : : * be considered during the next inactive_shrink.
164 : : * 3. It will at most scan nr_scans nodes
165 : : */
166 : 0 : static void __bpf_lru_list_rotate_inactive(struct bpf_lru *lru,
167 : : struct bpf_lru_list *l)
168 : : {
169 : 0 : struct list_head *inactive = &l->lists[BPF_LRU_LIST_T_INACTIVE];
170 : : struct list_head *cur, *last, *next = inactive;
171 : : struct bpf_lru_node *node;
172 : : unsigned int i = 0;
173 : :
174 [ # # ]: 0 : if (list_empty(inactive))
175 : 0 : return;
176 : :
177 : 0 : last = l->next_inactive_rotation->next;
178 [ # # ]: 0 : if (last == inactive)
179 : 0 : last = last->next;
180 : :
181 : : cur = l->next_inactive_rotation;
182 [ # # ]: 0 : while (i < lru->nr_scans) {
183 [ # # ]: 0 : if (cur == inactive) {
184 : 0 : cur = cur->prev;
185 : 0 : continue;
186 : : }
187 : :
188 : : node = list_entry(cur, struct bpf_lru_node, list);
189 : 0 : next = cur->prev;
190 [ # # ]: 0 : if (bpf_lru_node_is_ref(node))
191 : 0 : __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
192 [ # # ]: 0 : if (cur == last)
193 : : break;
194 : : cur = next;
195 : 0 : i++;
196 : : }
197 : :
198 : 0 : l->next_inactive_rotation = next;
199 : : }
200 : :
201 : : /* Shrink the inactive list. It starts from the tail of the
202 : : * inactive list and only move the nodes without the ref bit
203 : : * set to the designated free list.
204 : : */
205 : : static unsigned int
206 : 0 : __bpf_lru_list_shrink_inactive(struct bpf_lru *lru,
207 : : struct bpf_lru_list *l,
208 : : unsigned int tgt_nshrink,
209 : : struct list_head *free_list,
210 : : enum bpf_lru_list_type tgt_free_type)
211 : : {
212 : 0 : struct list_head *inactive = &l->lists[BPF_LRU_LIST_T_INACTIVE];
213 : : struct bpf_lru_node *node, *tmp_node;
214 : : unsigned int nshrinked = 0;
215 : : unsigned int i = 0;
216 : :
217 [ # # ]: 0 : list_for_each_entry_safe_reverse(node, tmp_node, inactive, list) {
218 [ # # ]: 0 : if (bpf_lru_node_is_ref(node)) {
219 : 0 : __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
220 [ # # ]: 0 : } else if (lru->del_from_htab(lru->del_arg, node)) {
221 : 0 : __bpf_lru_node_move_to_free(l, node, free_list,
222 : : tgt_free_type);
223 [ # # ]: 0 : if (++nshrinked == tgt_nshrink)
224 : : break;
225 : : }
226 : :
227 [ # # ]: 0 : if (++i == lru->nr_scans)
228 : : break;
229 : : }
230 : :
231 : 0 : return nshrinked;
232 : : }
233 : :
234 : : /* 1. Rotate the active list (if needed)
235 : : * 2. Always rotate the inactive list
236 : : */
237 : 0 : static void __bpf_lru_list_rotate(struct bpf_lru *lru, struct bpf_lru_list *l)
238 : : {
239 [ # # ]: 0 : if (bpf_lru_list_inactive_low(l))
240 : 0 : __bpf_lru_list_rotate_active(lru, l);
241 : :
242 : 0 : __bpf_lru_list_rotate_inactive(lru, l);
243 : 0 : }
244 : :
245 : : /* Calls __bpf_lru_list_shrink_inactive() to shrink some
246 : : * ref-bit-cleared nodes and move them to the designated
247 : : * free list.
248 : : *
249 : : * If it cannot get a free node after calling
250 : : * __bpf_lru_list_shrink_inactive(). It will just remove
251 : : * one node from either inactive or active list without
252 : : * honoring the ref-bit. It prefers inactive list to active
253 : : * list in this situation.
254 : : */
255 : 0 : static unsigned int __bpf_lru_list_shrink(struct bpf_lru *lru,
256 : : struct bpf_lru_list *l,
257 : : unsigned int tgt_nshrink,
258 : : struct list_head *free_list,
259 : : enum bpf_lru_list_type tgt_free_type)
260 : :
261 : : {
262 : : struct bpf_lru_node *node, *tmp_node;
263 : : struct list_head *force_shrink_list;
264 : : unsigned int nshrinked;
265 : :
266 : 0 : nshrinked = __bpf_lru_list_shrink_inactive(lru, l, tgt_nshrink,
267 : : free_list, tgt_free_type);
268 [ # # ]: 0 : if (nshrinked)
269 : : return nshrinked;
270 : :
271 : : /* Do a force shrink by ignoring the reference bit */
272 [ # # ]: 0 : if (!list_empty(&l->lists[BPF_LRU_LIST_T_INACTIVE]))
273 : : force_shrink_list = &l->lists[BPF_LRU_LIST_T_INACTIVE];
274 : : else
275 : 0 : force_shrink_list = &l->lists[BPF_LRU_LIST_T_ACTIVE];
276 : :
277 [ # # ]: 0 : list_for_each_entry_safe_reverse(node, tmp_node, force_shrink_list,
278 : : list) {
279 [ # # ]: 0 : if (lru->del_from_htab(lru->del_arg, node)) {
280 : 0 : __bpf_lru_node_move_to_free(l, node, free_list,
281 : : tgt_free_type);
282 : 0 : return 1;
283 : : }
284 : : }
285 : :
286 : : return 0;
287 : : }
288 : :
289 : : /* Flush the nodes from the local pending list to the LRU list */
290 : 0 : static void __local_list_flush(struct bpf_lru_list *l,
291 : : struct bpf_lru_locallist *loc_l)
292 : : {
293 : : struct bpf_lru_node *node, *tmp_node;
294 : :
295 [ # # ]: 0 : list_for_each_entry_safe_reverse(node, tmp_node,
296 : : local_pending_list(loc_l), list) {
297 [ # # ]: 0 : if (bpf_lru_node_is_ref(node))
298 : 0 : __bpf_lru_node_move_in(l, node, BPF_LRU_LIST_T_ACTIVE);
299 : : else
300 : 0 : __bpf_lru_node_move_in(l, node,
301 : : BPF_LRU_LIST_T_INACTIVE);
302 : : }
303 : 0 : }
304 : :
305 : 0 : static void bpf_lru_list_push_free(struct bpf_lru_list *l,
306 : : struct bpf_lru_node *node)
307 : : {
308 : : unsigned long flags;
309 : :
310 [ # # # # : 0 : if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))
# # ]
311 : 0 : return;
312 : :
313 : 0 : raw_spin_lock_irqsave(&l->lock, flags);
314 : 0 : __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);
315 : 0 : raw_spin_unlock_irqrestore(&l->lock, flags);
316 : : }
317 : :
318 : 0 : static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,
319 : : struct bpf_lru_locallist *loc_l)
320 : : {
321 : 0 : struct bpf_lru_list *l = &lru->common_lru.lru_list;
322 : : struct bpf_lru_node *node, *tmp_node;
323 : : unsigned int nfree = 0;
324 : :
325 : 0 : raw_spin_lock(&l->lock);
326 : :
327 : 0 : __local_list_flush(l, loc_l);
328 : :
329 : 0 : __bpf_lru_list_rotate(lru, l);
330 : :
331 [ # # ]: 0 : list_for_each_entry_safe(node, tmp_node, &l->lists[BPF_LRU_LIST_T_FREE],
332 : : list) {
333 : 0 : __bpf_lru_node_move_to_free(l, node, local_free_list(loc_l),
334 : : BPF_LRU_LOCAL_LIST_T_FREE);
335 [ # # ]: 0 : if (++nfree == LOCAL_FREE_TARGET)
336 : : break;
337 : : }
338 : :
339 [ # # ]: 0 : if (nfree < LOCAL_FREE_TARGET)
340 : 0 : __bpf_lru_list_shrink(lru, l, LOCAL_FREE_TARGET - nfree,
341 : : local_free_list(loc_l),
342 : : BPF_LRU_LOCAL_LIST_T_FREE);
343 : :
344 : : raw_spin_unlock(&l->lock);
345 : 0 : }
346 : :
347 : : static void __local_list_add_pending(struct bpf_lru *lru,
348 : : struct bpf_lru_locallist *loc_l,
349 : : int cpu,
350 : : struct bpf_lru_node *node,
351 : : u32 hash)
352 : : {
353 : 0 : *(u32 *)((void *)node + lru->hash_offset) = hash;
354 : 0 : node->cpu = cpu;
355 : 0 : node->type = BPF_LRU_LOCAL_LIST_T_PENDING;
356 : 0 : node->ref = 0;
357 : 0 : list_add(&node->list, local_pending_list(loc_l));
358 : : }
359 : :
360 : : static struct bpf_lru_node *
361 : : __local_list_pop_free(struct bpf_lru_locallist *loc_l)
362 : : {
363 : : struct bpf_lru_node *node;
364 : :
365 [ # # # # : 0 : node = list_first_entry_or_null(local_free_list(loc_l),
# # ]
366 : : struct bpf_lru_node,
367 : : list);
368 [ # # # # : 0 : if (node)
# # ]
369 : : list_del(&node->list);
370 : :
371 : : return node;
372 : : }
373 : :
374 : : static struct bpf_lru_node *
375 : 0 : __local_list_pop_pending(struct bpf_lru *lru, struct bpf_lru_locallist *loc_l)
376 : : {
377 : : struct bpf_lru_node *node;
378 : : bool force = false;
379 : :
380 : : ignore_ref:
381 : : /* Get from the tail (i.e. older element) of the pending list. */
382 [ # # ]: 0 : list_for_each_entry_reverse(node, local_pending_list(loc_l),
383 : : list) {
384 [ # # # # : 0 : if ((!bpf_lru_node_is_ref(node) || force) &&
# # ]
385 : 0 : lru->del_from_htab(lru->del_arg, node)) {
386 : : list_del(&node->list);
387 : 0 : return node;
388 : : }
389 : : }
390 : :
391 [ # # ]: 0 : if (!force) {
392 : : force = true;
393 : : goto ignore_ref;
394 : : }
395 : :
396 : : return NULL;
397 : : }
398 : :
399 : 0 : static struct bpf_lru_node *bpf_percpu_lru_pop_free(struct bpf_lru *lru,
400 : : u32 hash)
401 : : {
402 : : struct list_head *free_list;
403 : : struct bpf_lru_node *node = NULL;
404 : : struct bpf_lru_list *l;
405 : : unsigned long flags;
406 : 0 : int cpu = raw_smp_processor_id();
407 : :
408 : 0 : l = per_cpu_ptr(lru->percpu_lru, cpu);
409 : :
410 : 0 : raw_spin_lock_irqsave(&l->lock, flags);
411 : :
412 : 0 : __bpf_lru_list_rotate(lru, l);
413 : :
414 : 0 : free_list = &l->lists[BPF_LRU_LIST_T_FREE];
415 [ # # ]: 0 : if (list_empty(free_list))
416 : 0 : __bpf_lru_list_shrink(lru, l, PERCPU_FREE_TARGET, free_list,
417 : : BPF_LRU_LIST_T_FREE);
418 : :
419 [ # # ]: 0 : if (!list_empty(free_list)) {
420 : 0 : node = list_first_entry(free_list, struct bpf_lru_node, list);
421 : 0 : *(u32 *)((void *)node + lru->hash_offset) = hash;
422 : 0 : node->ref = 0;
423 : 0 : __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);
424 : : }
425 : :
426 : 0 : raw_spin_unlock_irqrestore(&l->lock, flags);
427 : :
428 : 0 : return node;
429 : : }
430 : :
431 : 0 : static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru,
432 : : u32 hash)
433 : : {
434 : : struct bpf_lru_locallist *loc_l, *steal_loc_l;
435 : : struct bpf_common_lru *clru = &lru->common_lru;
436 : : struct bpf_lru_node *node;
437 : : int steal, first_steal;
438 : : unsigned long flags;
439 : 0 : int cpu = raw_smp_processor_id();
440 : :
441 : 0 : loc_l = per_cpu_ptr(clru->local_list, cpu);
442 : :
443 : 0 : raw_spin_lock_irqsave(&loc_l->lock, flags);
444 : :
445 : : node = __local_list_pop_free(loc_l);
446 [ # # ]: 0 : if (!node) {
447 : 0 : bpf_lru_list_pop_free_to_local(lru, loc_l);
448 : : node = __local_list_pop_free(loc_l);
449 : : }
450 : :
451 [ # # ]: 0 : if (node)
452 : : __local_list_add_pending(lru, loc_l, cpu, node, hash);
453 : :
454 : 0 : raw_spin_unlock_irqrestore(&loc_l->lock, flags);
455 : :
456 [ # # ]: 0 : if (node)
457 : : return node;
458 : :
459 : : /* No free nodes found from the local free list and
460 : : * the global LRU list.
461 : : *
462 : : * Steal from the local free/pending list of the
463 : : * current CPU and remote CPU in RR. It starts
464 : : * with the loc_l->next_steal CPU.
465 : : */
466 : :
467 : 0 : first_steal = loc_l->next_steal;
468 : : steal = first_steal;
469 : : do {
470 : 0 : steal_loc_l = per_cpu_ptr(clru->local_list, steal);
471 : :
472 : 0 : raw_spin_lock_irqsave(&steal_loc_l->lock, flags);
473 : :
474 : : node = __local_list_pop_free(steal_loc_l);
475 [ # # ]: 0 : if (!node)
476 : 0 : node = __local_list_pop_pending(lru, steal_loc_l);
477 : :
478 : 0 : raw_spin_unlock_irqrestore(&steal_loc_l->lock, flags);
479 : :
480 : 0 : steal = get_next_cpu(steal);
481 [ # # ]: 0 : } while (!node && steal != first_steal);
482 : :
483 : 0 : loc_l->next_steal = steal;
484 : :
485 [ # # ]: 0 : if (node) {
486 : 0 : raw_spin_lock_irqsave(&loc_l->lock, flags);
487 : : __local_list_add_pending(lru, loc_l, cpu, node, hash);
488 : 0 : raw_spin_unlock_irqrestore(&loc_l->lock, flags);
489 : : }
490 : :
491 : 0 : return node;
492 : : }
493 : :
494 : 0 : struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash)
495 : : {
496 [ # # ]: 0 : if (lru->percpu)
497 : 0 : return bpf_percpu_lru_pop_free(lru, hash);
498 : : else
499 : 0 : return bpf_common_lru_pop_free(lru, hash);
500 : : }
501 : :
502 : 0 : static void bpf_common_lru_push_free(struct bpf_lru *lru,
503 : : struct bpf_lru_node *node)
504 : : {
505 : : unsigned long flags;
506 : :
507 [ # # # # : 0 : if (WARN_ON_ONCE(node->type == BPF_LRU_LIST_T_FREE) ||
# # # # ]
508 [ # # # # ]: 0 : WARN_ON_ONCE(node->type == BPF_LRU_LOCAL_LIST_T_FREE))
509 : : return;
510 : :
511 [ # # ]: 0 : if (node->type == BPF_LRU_LOCAL_LIST_T_PENDING) {
512 : : struct bpf_lru_locallist *loc_l;
513 : :
514 : 0 : loc_l = per_cpu_ptr(lru->common_lru.local_list, node->cpu);
515 : :
516 : 0 : raw_spin_lock_irqsave(&loc_l->lock, flags);
517 : :
518 [ # # ]: 0 : if (unlikely(node->type != BPF_LRU_LOCAL_LIST_T_PENDING)) {
519 : 0 : raw_spin_unlock_irqrestore(&loc_l->lock, flags);
520 : 0 : goto check_lru_list;
521 : : }
522 : :
523 : 0 : node->type = BPF_LRU_LOCAL_LIST_T_FREE;
524 : 0 : node->ref = 0;
525 : 0 : list_move(&node->list, local_free_list(loc_l));
526 : :
527 : 0 : raw_spin_unlock_irqrestore(&loc_l->lock, flags);
528 : 0 : return;
529 : : }
530 : :
531 : : check_lru_list:
532 : 0 : bpf_lru_list_push_free(&lru->common_lru.lru_list, node);
533 : : }
534 : :
535 : 0 : static void bpf_percpu_lru_push_free(struct bpf_lru *lru,
536 : : struct bpf_lru_node *node)
537 : : {
538 : : struct bpf_lru_list *l;
539 : : unsigned long flags;
540 : :
541 : 0 : l = per_cpu_ptr(lru->percpu_lru, node->cpu);
542 : :
543 : 0 : raw_spin_lock_irqsave(&l->lock, flags);
544 : :
545 : 0 : __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);
546 : :
547 : 0 : raw_spin_unlock_irqrestore(&l->lock, flags);
548 : 0 : }
549 : :
550 : 0 : void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node)
551 : : {
552 [ # # ]: 0 : if (lru->percpu)
553 : 0 : bpf_percpu_lru_push_free(lru, node);
554 : : else
555 : 0 : bpf_common_lru_push_free(lru, node);
556 : 0 : }
557 : :
558 : : static void bpf_common_lru_populate(struct bpf_lru *lru, void *buf,
559 : : u32 node_offset, u32 elem_size,
560 : : u32 nr_elems)
561 : : {
562 : : struct bpf_lru_list *l = &lru->common_lru.lru_list;
563 : : u32 i;
564 : :
565 [ # # ]: 0 : for (i = 0; i < nr_elems; i++) {
566 : : struct bpf_lru_node *node;
567 : :
568 : 0 : node = (struct bpf_lru_node *)(buf + node_offset);
569 : 0 : node->type = BPF_LRU_LIST_T_FREE;
570 : 0 : node->ref = 0;
571 : 0 : list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);
572 : 0 : buf += elem_size;
573 : : }
574 : : }
575 : :
576 : 0 : static void bpf_percpu_lru_populate(struct bpf_lru *lru, void *buf,
577 : : u32 node_offset, u32 elem_size,
578 : : u32 nr_elems)
579 : : {
580 : : u32 i, pcpu_entries;
581 : : int cpu;
582 : : struct bpf_lru_list *l;
583 : :
584 : 0 : pcpu_entries = nr_elems / num_possible_cpus();
585 : :
586 : : i = 0;
587 : :
588 [ # # ]: 0 : for_each_possible_cpu(cpu) {
589 : : struct bpf_lru_node *node;
590 : :
591 : 0 : l = per_cpu_ptr(lru->percpu_lru, cpu);
592 : : again:
593 : 0 : node = (struct bpf_lru_node *)(buf + node_offset);
594 : 0 : node->cpu = cpu;
595 : 0 : node->type = BPF_LRU_LIST_T_FREE;
596 : 0 : node->ref = 0;
597 : 0 : list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);
598 : 0 : i++;
599 : 0 : buf += elem_size;
600 [ # # ]: 0 : if (i == nr_elems)
601 : : break;
602 [ # # ]: 0 : if (i % pcpu_entries)
603 : : goto again;
604 : : }
605 : 0 : }
606 : :
607 : 0 : void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
608 : : u32 elem_size, u32 nr_elems)
609 : : {
610 [ # # ]: 0 : if (lru->percpu)
611 : 0 : bpf_percpu_lru_populate(lru, buf, node_offset, elem_size,
612 : : nr_elems);
613 : : else
614 : : bpf_common_lru_populate(lru, buf, node_offset, elem_size,
615 : : nr_elems);
616 : 0 : }
617 : :
618 : : static void bpf_lru_locallist_init(struct bpf_lru_locallist *loc_l, int cpu)
619 : : {
620 : : int i;
621 : :
622 [ # # ]: 0 : for (i = 0; i < NR_BPF_LRU_LOCAL_LIST_T; i++)
623 : 0 : INIT_LIST_HEAD(&loc_l->lists[i]);
624 : :
625 : 0 : loc_l->next_steal = cpu;
626 : :
627 : 0 : raw_spin_lock_init(&loc_l->lock);
628 : : }
629 : :
630 : : static void bpf_lru_list_init(struct bpf_lru_list *l)
631 : : {
632 : : int i;
633 : :
634 [ # # # # ]: 0 : for (i = 0; i < NR_BPF_LRU_LIST_T; i++)
635 : 0 : INIT_LIST_HEAD(&l->lists[i]);
636 : :
637 [ # # # # ]: 0 : for (i = 0; i < NR_BPF_LRU_LIST_COUNT; i++)
638 : 0 : l->counts[i] = 0;
639 : :
640 : 0 : l->next_inactive_rotation = &l->lists[BPF_LRU_LIST_T_INACTIVE];
641 : :
642 : 0 : raw_spin_lock_init(&l->lock);
643 : : }
644 : :
645 : 0 : int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
646 : : del_from_htab_func del_from_htab, void *del_arg)
647 : : {
648 : : int cpu;
649 : :
650 [ # # ]: 0 : if (percpu) {
651 : 0 : lru->percpu_lru = alloc_percpu(struct bpf_lru_list);
652 [ # # ]: 0 : if (!lru->percpu_lru)
653 : : return -ENOMEM;
654 : :
655 [ # # ]: 0 : for_each_possible_cpu(cpu) {
656 : : struct bpf_lru_list *l;
657 : :
658 : 0 : l = per_cpu_ptr(lru->percpu_lru, cpu);
659 : : bpf_lru_list_init(l);
660 : : }
661 : 0 : lru->nr_scans = PERCPU_NR_SCANS;
662 : : } else {
663 : : struct bpf_common_lru *clru = &lru->common_lru;
664 : :
665 : 0 : clru->local_list = alloc_percpu(struct bpf_lru_locallist);
666 [ # # ]: 0 : if (!clru->local_list)
667 : : return -ENOMEM;
668 : :
669 [ # # ]: 0 : for_each_possible_cpu(cpu) {
670 : : struct bpf_lru_locallist *loc_l;
671 : :
672 : 0 : loc_l = per_cpu_ptr(clru->local_list, cpu);
673 : : bpf_lru_locallist_init(loc_l, cpu);
674 : : }
675 : :
676 : : bpf_lru_list_init(&clru->lru_list);
677 : 0 : lru->nr_scans = LOCAL_NR_SCANS;
678 : : }
679 : :
680 : 0 : lru->percpu = percpu;
681 : 0 : lru->del_from_htab = del_from_htab;
682 : 0 : lru->del_arg = del_arg;
683 : 0 : lru->hash_offset = hash_offset;
684 : :
685 : 0 : return 0;
686 : : }
687 : :
688 : 0 : void bpf_lru_destroy(struct bpf_lru *lru)
689 : : {
690 [ # # ]: 0 : if (lru->percpu)
691 : 0 : free_percpu(lru->percpu_lru);
692 : : else
693 : 0 : free_percpu(lru->common_lru.local_list);
694 : 0 : }
|
