Loading...
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
22static int get_next_cpu(int cpu)
23{
24 cpu = cpumask_next(cpu, cpu_possible_mask);
25 if (cpu >= nr_cpu_ids)
26 cpu = cpumask_first(cpu_possible_mask);
27 return cpu;
28}
29
30/* Local list helpers */
31static struct list_head *local_free_list(struct bpf_lru_locallist *loc_l)
32{
33 return &loc_l->lists[LOCAL_FREE_LIST_IDX];
34}
35
36static struct list_head *local_pending_list(struct bpf_lru_locallist *loc_l)
37{
38 return &loc_l->lists[LOCAL_PENDING_LIST_IDX];
39}
40
41/* bpf_lru_node helpers */
42static bool bpf_lru_node_is_ref(const struct bpf_lru_node *node)
43{
44 return node->ref;
45}
46
47static void bpf_lru_list_count_inc(struct bpf_lru_list *l,
48 enum bpf_lru_list_type type)
49{
50 if (type < NR_BPF_LRU_LIST_COUNT)
51 l->counts[type]++;
52}
53
54static void bpf_lru_list_count_dec(struct bpf_lru_list *l,
55 enum bpf_lru_list_type type)
56{
57 if (type < NR_BPF_LRU_LIST_COUNT)
58 l->counts[type]--;
59}
60
61static 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 if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))
67 return;
68
69 /* If the removing node is the next_inactive_rotation candidate,
70 * move the next_inactive_rotation pointer also.
71 */
72 if (&node->list == l->next_inactive_rotation)
73 l->next_inactive_rotation = l->next_inactive_rotation->prev;
74
75 bpf_lru_list_count_dec(l, node->type);
76
77 node->type = tgt_free_type;
78 list_move(&node->list, free_list);
79}
80
81/* Move nodes from local list to the LRU list */
82static 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 if (WARN_ON_ONCE(!IS_LOCAL_LIST_TYPE(node->type)) ||
87 WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(tgt_type)))
88 return;
89
90 bpf_lru_list_count_inc(l, tgt_type);
91 node->type = tgt_type;
92 node->ref = 0;
93 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 */
100static 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 if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)) ||
105 WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(tgt_type)))
106 return;
107
108 if (node->type != tgt_type) {
109 bpf_lru_list_count_dec(l, node->type);
110 bpf_lru_list_count_inc(l, tgt_type);
111 node->type = tgt_type;
112 }
113 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 if (&node->list == l->next_inactive_rotation)
119 l->next_inactive_rotation = l->next_inactive_rotation->prev;
120
121 list_move(&node->list, &l->lists[tgt_type]);
122}
123
124static bool bpf_lru_list_inactive_low(const struct bpf_lru_list *l)
125{
126 return l->counts[BPF_LRU_LIST_T_INACTIVE] <
127 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 */
139static 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 first_node = list_first_entry(active, struct bpf_lru_node, list);
147 list_for_each_entry_safe_reverse(node, tmp_node, active, list) {
148 if (bpf_lru_node_is_ref(node))
149 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
150 else
151 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);
152
153 if (++i == lru->nr_scans || node == first_node)
154 break;
155 }
156}
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 */
166static void __bpf_lru_list_rotate_inactive(struct bpf_lru *lru,
167 struct bpf_lru_list *l)
168{
169 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 if (list_empty(inactive))
175 return;
176
177 last = l->next_inactive_rotation->next;
178 if (last == inactive)
179 last = last->next;
180
181 cur = l->next_inactive_rotation;
182 while (i < lru->nr_scans) {
183 if (cur == inactive) {
184 cur = cur->prev;
185 continue;
186 }
187
188 node = list_entry(cur, struct bpf_lru_node, list);
189 next = cur->prev;
190 if (bpf_lru_node_is_ref(node))
191 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
192 if (cur == last)
193 break;
194 cur = next;
195 i++;
196 }
197
198 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 */
205static unsigned int
206__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 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 list_for_each_entry_safe_reverse(node, tmp_node, inactive, list) {
218 if (bpf_lru_node_is_ref(node)) {
219 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
220 } else if (lru->del_from_htab(lru->del_arg, node)) {
221 __bpf_lru_node_move_to_free(l, node, free_list,
222 tgt_free_type);
223 if (++nshrinked == tgt_nshrink)
224 break;
225 }
226
227 if (++i == lru->nr_scans)
228 break;
229 }
230
231 return nshrinked;
232}
233
234/* 1. Rotate the active list (if needed)
235 * 2. Always rotate the inactive list
236 */
237static void __bpf_lru_list_rotate(struct bpf_lru *lru, struct bpf_lru_list *l)
238{
239 if (bpf_lru_list_inactive_low(l))
240 __bpf_lru_list_rotate_active(lru, l);
241
242 __bpf_lru_list_rotate_inactive(lru, l);
243}
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 */
255static 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 nshrinked = __bpf_lru_list_shrink_inactive(lru, l, tgt_nshrink,
267 free_list, tgt_free_type);
268 if (nshrinked)
269 return nshrinked;
270
271 /* Do a force shrink by ignoring the reference bit */
272 if (!list_empty(&l->lists[BPF_LRU_LIST_T_INACTIVE]))
273 force_shrink_list = &l->lists[BPF_LRU_LIST_T_INACTIVE];
274 else
275 force_shrink_list = &l->lists[BPF_LRU_LIST_T_ACTIVE];
276
277 list_for_each_entry_safe_reverse(node, tmp_node, force_shrink_list,
278 list) {
279 if (lru->del_from_htab(lru->del_arg, node)) {
280 __bpf_lru_node_move_to_free(l, node, free_list,
281 tgt_free_type);
282 return 1;
283 }
284 }
285
286 return 0;
287}
288
289/* Flush the nodes from the local pending list to the LRU list */
290static 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 list_for_each_entry_safe_reverse(node, tmp_node,
296 local_pending_list(loc_l), list) {
297 if (bpf_lru_node_is_ref(node))
298 __bpf_lru_node_move_in(l, node, BPF_LRU_LIST_T_ACTIVE);
299 else
300 __bpf_lru_node_move_in(l, node,
301 BPF_LRU_LIST_T_INACTIVE);
302 }
303}
304
305static void bpf_lru_list_push_free(struct bpf_lru_list *l,
306 struct bpf_lru_node *node)
307{
308 unsigned long flags;
309
310 if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))
311 return;
312
313 raw_spin_lock_irqsave(&l->lock, flags);
314 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);
315 raw_spin_unlock_irqrestore(&l->lock, flags);
316}
317
318static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,
319 struct bpf_lru_locallist *loc_l)
320{
321 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 raw_spin_lock(&l->lock);
326
327 __local_list_flush(l, loc_l);
328
329 __bpf_lru_list_rotate(lru, l);
330
331 list_for_each_entry_safe(node, tmp_node, &l->lists[BPF_LRU_LIST_T_FREE],
332 list) {
333 __bpf_lru_node_move_to_free(l, node, local_free_list(loc_l),
334 BPF_LRU_LOCAL_LIST_T_FREE);
335 if (++nfree == LOCAL_FREE_TARGET)
336 break;
337 }
338
339 if (nfree < LOCAL_FREE_TARGET)
340 __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}
346
347static 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 *(u32 *)((void *)node + lru->hash_offset) = hash;
354 node->cpu = cpu;
355 node->type = BPF_LRU_LOCAL_LIST_T_PENDING;
356 node->ref = 0;
357 list_add(&node->list, local_pending_list(loc_l));
358}
359
360static struct bpf_lru_node *
361__local_list_pop_free(struct bpf_lru_locallist *loc_l)
362{
363 struct bpf_lru_node *node;
364
365 node = list_first_entry_or_null(local_free_list(loc_l),
366 struct bpf_lru_node,
367 list);
368 if (node)
369 list_del(&node->list);
370
371 return node;
372}
373
374static struct bpf_lru_node *
375__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
380ignore_ref:
381 /* Get from the tail (i.e. older element) of the pending list. */
382 list_for_each_entry_reverse(node, local_pending_list(loc_l),
383 list) {
384 if ((!bpf_lru_node_is_ref(node) || force) &&
385 lru->del_from_htab(lru->del_arg, node)) {
386 list_del(&node->list);
387 return node;
388 }
389 }
390
391 if (!force) {
392 force = true;
393 goto ignore_ref;
394 }
395
396 return NULL;
397}
398
399static 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 int cpu = raw_smp_processor_id();
407
408 l = per_cpu_ptr(lru->percpu_lru, cpu);
409
410 raw_spin_lock_irqsave(&l->lock, flags);
411
412 __bpf_lru_list_rotate(lru, l);
413
414 free_list = &l->lists[BPF_LRU_LIST_T_FREE];
415 if (list_empty(free_list))
416 __bpf_lru_list_shrink(lru, l, PERCPU_FREE_TARGET, free_list,
417 BPF_LRU_LIST_T_FREE);
418
419 if (!list_empty(free_list)) {
420 node = list_first_entry(free_list, struct bpf_lru_node, list);
421 *(u32 *)((void *)node + lru->hash_offset) = hash;
422 node->ref = 0;
423 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);
424 }
425
426 raw_spin_unlock_irqrestore(&l->lock, flags);
427
428 return node;
429}
430
431static 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 int cpu = raw_smp_processor_id();
440
441 loc_l = per_cpu_ptr(clru->local_list, cpu);
442
443 raw_spin_lock_irqsave(&loc_l->lock, flags);
444
445 node = __local_list_pop_free(loc_l);
446 if (!node) {
447 bpf_lru_list_pop_free_to_local(lru, loc_l);
448 node = __local_list_pop_free(loc_l);
449 }
450
451 if (node)
452 __local_list_add_pending(lru, loc_l, cpu, node, hash);
453
454 raw_spin_unlock_irqrestore(&loc_l->lock, flags);
455
456 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 first_steal = loc_l->next_steal;
468 steal = first_steal;
469 do {
470 steal_loc_l = per_cpu_ptr(clru->local_list, steal);
471
472 raw_spin_lock_irqsave(&steal_loc_l->lock, flags);
473
474 node = __local_list_pop_free(steal_loc_l);
475 if (!node)
476 node = __local_list_pop_pending(lru, steal_loc_l);
477
478 raw_spin_unlock_irqrestore(&steal_loc_l->lock, flags);
479
480 steal = get_next_cpu(steal);
481 } while (!node && steal != first_steal);
482
483 loc_l->next_steal = steal;
484
485 if (node) {
486 raw_spin_lock_irqsave(&loc_l->lock, flags);
487 __local_list_add_pending(lru, loc_l, cpu, node, hash);
488 raw_spin_unlock_irqrestore(&loc_l->lock, flags);
489 }
490
491 return node;
492}
493
494struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash)
495{
496 if (lru->percpu)
497 return bpf_percpu_lru_pop_free(lru, hash);
498 else
499 return bpf_common_lru_pop_free(lru, hash);
500}
501
502static void bpf_common_lru_push_free(struct bpf_lru *lru,
503 struct bpf_lru_node *node)
504{
505 unsigned long flags;
506
507 if (WARN_ON_ONCE(node->type == BPF_LRU_LIST_T_FREE) ||
508 WARN_ON_ONCE(node->type == BPF_LRU_LOCAL_LIST_T_FREE))
509 return;
510
511 if (node->type == BPF_LRU_LOCAL_LIST_T_PENDING) {
512 struct bpf_lru_locallist *loc_l;
513
514 loc_l = per_cpu_ptr(lru->common_lru.local_list, node->cpu);
515
516 raw_spin_lock_irqsave(&loc_l->lock, flags);
517
518 if (unlikely(node->type != BPF_LRU_LOCAL_LIST_T_PENDING)) {
519 raw_spin_unlock_irqrestore(&loc_l->lock, flags);
520 goto check_lru_list;
521 }
522
523 node->type = BPF_LRU_LOCAL_LIST_T_FREE;
524 node->ref = 0;
525 list_move(&node->list, local_free_list(loc_l));
526
527 raw_spin_unlock_irqrestore(&loc_l->lock, flags);
528 return;
529 }
530
531check_lru_list:
532 bpf_lru_list_push_free(&lru->common_lru.lru_list, node);
533}
534
535static 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 l = per_cpu_ptr(lru->percpu_lru, node->cpu);
542
543 raw_spin_lock_irqsave(&l->lock, flags);
544
545 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);
546
547 raw_spin_unlock_irqrestore(&l->lock, flags);
548}
549
550void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node)
551{
552 if (lru->percpu)
553 bpf_percpu_lru_push_free(lru, node);
554 else
555 bpf_common_lru_push_free(lru, node);
556}
557
558static 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 for (i = 0; i < nr_elems; i++) {
566 struct bpf_lru_node *node;
567
568 node = (struct bpf_lru_node *)(buf + node_offset);
569 node->type = BPF_LRU_LIST_T_FREE;
570 node->ref = 0;
571 list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);
572 buf += elem_size;
573 }
574}
575
576static 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 pcpu_entries = nr_elems / num_possible_cpus();
585
586 i = 0;
587
588 for_each_possible_cpu(cpu) {
589 struct bpf_lru_node *node;
590
591 l = per_cpu_ptr(lru->percpu_lru, cpu);
592again:
593 node = (struct bpf_lru_node *)(buf + node_offset);
594 node->cpu = cpu;
595 node->type = BPF_LRU_LIST_T_FREE;
596 node->ref = 0;
597 list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);
598 i++;
599 buf += elem_size;
600 if (i == nr_elems)
601 break;
602 if (i % pcpu_entries)
603 goto again;
604 }
605}
606
607void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
608 u32 elem_size, u32 nr_elems)
609{
610 if (lru->percpu)
611 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}
617
618static void bpf_lru_locallist_init(struct bpf_lru_locallist *loc_l, int cpu)
619{
620 int i;
621
622 for (i = 0; i < NR_BPF_LRU_LOCAL_LIST_T; i++)
623 INIT_LIST_HEAD(&loc_l->lists[i]);
624
625 loc_l->next_steal = cpu;
626
627 raw_spin_lock_init(&loc_l->lock);
628}
629
630static void bpf_lru_list_init(struct bpf_lru_list *l)
631{
632 int i;
633
634 for (i = 0; i < NR_BPF_LRU_LIST_T; i++)
635 INIT_LIST_HEAD(&l->lists[i]);
636
637 for (i = 0; i < NR_BPF_LRU_LIST_COUNT; i++)
638 l->counts[i] = 0;
639
640 l->next_inactive_rotation = &l->lists[BPF_LRU_LIST_T_INACTIVE];
641
642 raw_spin_lock_init(&l->lock);
643}
644
645int 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 if (percpu) {
651 lru->percpu_lru = alloc_percpu(struct bpf_lru_list);
652 if (!lru->percpu_lru)
653 return -ENOMEM;
654
655 for_each_possible_cpu(cpu) {
656 struct bpf_lru_list *l;
657
658 l = per_cpu_ptr(lru->percpu_lru, cpu);
659 bpf_lru_list_init(l);
660 }
661 lru->nr_scans = PERCPU_NR_SCANS;
662 } else {
663 struct bpf_common_lru *clru = &lru->common_lru;
664
665 clru->local_list = alloc_percpu(struct bpf_lru_locallist);
666 if (!clru->local_list)
667 return -ENOMEM;
668
669 for_each_possible_cpu(cpu) {
670 struct bpf_lru_locallist *loc_l;
671
672 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 lru->nr_scans = LOCAL_NR_SCANS;
678 }
679
680 lru->percpu = percpu;
681 lru->del_from_htab = del_from_htab;
682 lru->del_arg = del_arg;
683 lru->hash_offset = hash_offset;
684
685 return 0;
686}
687
688void bpf_lru_destroy(struct bpf_lru *lru)
689{
690 if (lru->percpu)
691 free_percpu(lru->percpu_lru);
692 else
693 free_percpu(lru->common_lru.local_list);
694}
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
22static int get_next_cpu(int cpu)
23{
24 cpu = cpumask_next(cpu, cpu_possible_mask);
25 if (cpu >= nr_cpu_ids)
26 cpu = cpumask_first(cpu_possible_mask);
27 return cpu;
28}
29
30/* Local list helpers */
31static struct list_head *local_free_list(struct bpf_lru_locallist *loc_l)
32{
33 return &loc_l->lists[LOCAL_FREE_LIST_IDX];
34}
35
36static struct list_head *local_pending_list(struct bpf_lru_locallist *loc_l)
37{
38 return &loc_l->lists[LOCAL_PENDING_LIST_IDX];
39}
40
41/* bpf_lru_node helpers */
42static bool bpf_lru_node_is_ref(const struct bpf_lru_node *node)
43{
44 return node->ref;
45}
46
47static void bpf_lru_list_count_inc(struct bpf_lru_list *l,
48 enum bpf_lru_list_type type)
49{
50 if (type < NR_BPF_LRU_LIST_COUNT)
51 l->counts[type]++;
52}
53
54static void bpf_lru_list_count_dec(struct bpf_lru_list *l,
55 enum bpf_lru_list_type type)
56{
57 if (type < NR_BPF_LRU_LIST_COUNT)
58 l->counts[type]--;
59}
60
61static 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 if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))
67 return;
68
69 /* If the removing node is the next_inactive_rotation candidate,
70 * move the next_inactive_rotation pointer also.
71 */
72 if (&node->list == l->next_inactive_rotation)
73 l->next_inactive_rotation = l->next_inactive_rotation->prev;
74
75 bpf_lru_list_count_dec(l, node->type);
76
77 node->type = tgt_free_type;
78 list_move(&node->list, free_list);
79}
80
81/* Move nodes from local list to the LRU list */
82static 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 if (WARN_ON_ONCE(!IS_LOCAL_LIST_TYPE(node->type)) ||
87 WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(tgt_type)))
88 return;
89
90 bpf_lru_list_count_inc(l, tgt_type);
91 node->type = tgt_type;
92 node->ref = 0;
93 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 */
100static 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 if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)) ||
105 WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(tgt_type)))
106 return;
107
108 if (node->type != tgt_type) {
109 bpf_lru_list_count_dec(l, node->type);
110 bpf_lru_list_count_inc(l, tgt_type);
111 node->type = tgt_type;
112 }
113 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 if (&node->list == l->next_inactive_rotation)
119 l->next_inactive_rotation = l->next_inactive_rotation->prev;
120
121 list_move(&node->list, &l->lists[tgt_type]);
122}
123
124static bool bpf_lru_list_inactive_low(const struct bpf_lru_list *l)
125{
126 return l->counts[BPF_LRU_LIST_T_INACTIVE] <
127 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 */
139static 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 first_node = list_first_entry(active, struct bpf_lru_node, list);
147 list_for_each_entry_safe_reverse(node, tmp_node, active, list) {
148 if (bpf_lru_node_is_ref(node))
149 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
150 else
151 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);
152
153 if (++i == lru->nr_scans || node == first_node)
154 break;
155 }
156}
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 */
166static void __bpf_lru_list_rotate_inactive(struct bpf_lru *lru,
167 struct bpf_lru_list *l)
168{
169 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 if (list_empty(inactive))
175 return;
176
177 last = l->next_inactive_rotation->next;
178 if (last == inactive)
179 last = last->next;
180
181 cur = l->next_inactive_rotation;
182 while (i < lru->nr_scans) {
183 if (cur == inactive) {
184 cur = cur->prev;
185 continue;
186 }
187
188 node = list_entry(cur, struct bpf_lru_node, list);
189 next = cur->prev;
190 if (bpf_lru_node_is_ref(node))
191 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
192 if (cur == last)
193 break;
194 cur = next;
195 i++;
196 }
197
198 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 */
205static unsigned int
206__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 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 list_for_each_entry_safe_reverse(node, tmp_node, inactive, list) {
218 if (bpf_lru_node_is_ref(node)) {
219 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_ACTIVE);
220 } else if (lru->del_from_htab(lru->del_arg, node)) {
221 __bpf_lru_node_move_to_free(l, node, free_list,
222 tgt_free_type);
223 if (++nshrinked == tgt_nshrink)
224 break;
225 }
226
227 if (++i == lru->nr_scans)
228 break;
229 }
230
231 return nshrinked;
232}
233
234/* 1. Rotate the active list (if needed)
235 * 2. Always rotate the inactive list
236 */
237static void __bpf_lru_list_rotate(struct bpf_lru *lru, struct bpf_lru_list *l)
238{
239 if (bpf_lru_list_inactive_low(l))
240 __bpf_lru_list_rotate_active(lru, l);
241
242 __bpf_lru_list_rotate_inactive(lru, l);
243}
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 */
255static 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 nshrinked = __bpf_lru_list_shrink_inactive(lru, l, tgt_nshrink,
267 free_list, tgt_free_type);
268 if (nshrinked)
269 return nshrinked;
270
271 /* Do a force shrink by ignoring the reference bit */
272 if (!list_empty(&l->lists[BPF_LRU_LIST_T_INACTIVE]))
273 force_shrink_list = &l->lists[BPF_LRU_LIST_T_INACTIVE];
274 else
275 force_shrink_list = &l->lists[BPF_LRU_LIST_T_ACTIVE];
276
277 list_for_each_entry_safe_reverse(node, tmp_node, force_shrink_list,
278 list) {
279 if (lru->del_from_htab(lru->del_arg, node)) {
280 __bpf_lru_node_move_to_free(l, node, free_list,
281 tgt_free_type);
282 return 1;
283 }
284 }
285
286 return 0;
287}
288
289/* Flush the nodes from the local pending list to the LRU list */
290static 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 list_for_each_entry_safe_reverse(node, tmp_node,
296 local_pending_list(loc_l), list) {
297 if (bpf_lru_node_is_ref(node))
298 __bpf_lru_node_move_in(l, node, BPF_LRU_LIST_T_ACTIVE);
299 else
300 __bpf_lru_node_move_in(l, node,
301 BPF_LRU_LIST_T_INACTIVE);
302 }
303}
304
305static void bpf_lru_list_push_free(struct bpf_lru_list *l,
306 struct bpf_lru_node *node)
307{
308 unsigned long flags;
309
310 if (WARN_ON_ONCE(IS_LOCAL_LIST_TYPE(node->type)))
311 return;
312
313 raw_spin_lock_irqsave(&l->lock, flags);
314 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);
315 raw_spin_unlock_irqrestore(&l->lock, flags);
316}
317
318static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,
319 struct bpf_lru_locallist *loc_l)
320{
321 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 raw_spin_lock(&l->lock);
326
327 __local_list_flush(l, loc_l);
328
329 __bpf_lru_list_rotate(lru, l);
330
331 list_for_each_entry_safe(node, tmp_node, &l->lists[BPF_LRU_LIST_T_FREE],
332 list) {
333 __bpf_lru_node_move_to_free(l, node, local_free_list(loc_l),
334 BPF_LRU_LOCAL_LIST_T_FREE);
335 if (++nfree == LOCAL_FREE_TARGET)
336 break;
337 }
338
339 if (nfree < LOCAL_FREE_TARGET)
340 __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}
346
347static 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 *(u32 *)((void *)node + lru->hash_offset) = hash;
354 node->cpu = cpu;
355 node->type = BPF_LRU_LOCAL_LIST_T_PENDING;
356 node->ref = 0;
357 list_add(&node->list, local_pending_list(loc_l));
358}
359
360static struct bpf_lru_node *
361__local_list_pop_free(struct bpf_lru_locallist *loc_l)
362{
363 struct bpf_lru_node *node;
364
365 node = list_first_entry_or_null(local_free_list(loc_l),
366 struct bpf_lru_node,
367 list);
368 if (node)
369 list_del(&node->list);
370
371 return node;
372}
373
374static struct bpf_lru_node *
375__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
380ignore_ref:
381 /* Get from the tail (i.e. older element) of the pending list. */
382 list_for_each_entry_reverse(node, local_pending_list(loc_l),
383 list) {
384 if ((!bpf_lru_node_is_ref(node) || force) &&
385 lru->del_from_htab(lru->del_arg, node)) {
386 list_del(&node->list);
387 return node;
388 }
389 }
390
391 if (!force) {
392 force = true;
393 goto ignore_ref;
394 }
395
396 return NULL;
397}
398
399static 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 int cpu = raw_smp_processor_id();
407
408 l = per_cpu_ptr(lru->percpu_lru, cpu);
409
410 raw_spin_lock_irqsave(&l->lock, flags);
411
412 __bpf_lru_list_rotate(lru, l);
413
414 free_list = &l->lists[BPF_LRU_LIST_T_FREE];
415 if (list_empty(free_list))
416 __bpf_lru_list_shrink(lru, l, PERCPU_FREE_TARGET, free_list,
417 BPF_LRU_LIST_T_FREE);
418
419 if (!list_empty(free_list)) {
420 node = list_first_entry(free_list, struct bpf_lru_node, list);
421 *(u32 *)((void *)node + lru->hash_offset) = hash;
422 node->ref = 0;
423 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_INACTIVE);
424 }
425
426 raw_spin_unlock_irqrestore(&l->lock, flags);
427
428 return node;
429}
430
431static 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 int cpu = raw_smp_processor_id();
440
441 loc_l = per_cpu_ptr(clru->local_list, cpu);
442
443 raw_spin_lock_irqsave(&loc_l->lock, flags);
444
445 node = __local_list_pop_free(loc_l);
446 if (!node) {
447 bpf_lru_list_pop_free_to_local(lru, loc_l);
448 node = __local_list_pop_free(loc_l);
449 }
450
451 if (node)
452 __local_list_add_pending(lru, loc_l, cpu, node, hash);
453
454 raw_spin_unlock_irqrestore(&loc_l->lock, flags);
455
456 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 first_steal = loc_l->next_steal;
468 steal = first_steal;
469 do {
470 steal_loc_l = per_cpu_ptr(clru->local_list, steal);
471
472 raw_spin_lock_irqsave(&steal_loc_l->lock, flags);
473
474 node = __local_list_pop_free(steal_loc_l);
475 if (!node)
476 node = __local_list_pop_pending(lru, steal_loc_l);
477
478 raw_spin_unlock_irqrestore(&steal_loc_l->lock, flags);
479
480 steal = get_next_cpu(steal);
481 } while (!node && steal != first_steal);
482
483 loc_l->next_steal = steal;
484
485 if (node) {
486 raw_spin_lock_irqsave(&loc_l->lock, flags);
487 __local_list_add_pending(lru, loc_l, cpu, node, hash);
488 raw_spin_unlock_irqrestore(&loc_l->lock, flags);
489 }
490
491 return node;
492}
493
494struct bpf_lru_node *bpf_lru_pop_free(struct bpf_lru *lru, u32 hash)
495{
496 if (lru->percpu)
497 return bpf_percpu_lru_pop_free(lru, hash);
498 else
499 return bpf_common_lru_pop_free(lru, hash);
500}
501
502static void bpf_common_lru_push_free(struct bpf_lru *lru,
503 struct bpf_lru_node *node)
504{
505 u8 node_type = READ_ONCE(node->type);
506 unsigned long flags;
507
508 if (WARN_ON_ONCE(node_type == BPF_LRU_LIST_T_FREE) ||
509 WARN_ON_ONCE(node_type == BPF_LRU_LOCAL_LIST_T_FREE))
510 return;
511
512 if (node_type == BPF_LRU_LOCAL_LIST_T_PENDING) {
513 struct bpf_lru_locallist *loc_l;
514
515 loc_l = per_cpu_ptr(lru->common_lru.local_list, node->cpu);
516
517 raw_spin_lock_irqsave(&loc_l->lock, flags);
518
519 if (unlikely(node->type != BPF_LRU_LOCAL_LIST_T_PENDING)) {
520 raw_spin_unlock_irqrestore(&loc_l->lock, flags);
521 goto check_lru_list;
522 }
523
524 node->type = BPF_LRU_LOCAL_LIST_T_FREE;
525 node->ref = 0;
526 list_move(&node->list, local_free_list(loc_l));
527
528 raw_spin_unlock_irqrestore(&loc_l->lock, flags);
529 return;
530 }
531
532check_lru_list:
533 bpf_lru_list_push_free(&lru->common_lru.lru_list, node);
534}
535
536static void bpf_percpu_lru_push_free(struct bpf_lru *lru,
537 struct bpf_lru_node *node)
538{
539 struct bpf_lru_list *l;
540 unsigned long flags;
541
542 l = per_cpu_ptr(lru->percpu_lru, node->cpu);
543
544 raw_spin_lock_irqsave(&l->lock, flags);
545
546 __bpf_lru_node_move(l, node, BPF_LRU_LIST_T_FREE);
547
548 raw_spin_unlock_irqrestore(&l->lock, flags);
549}
550
551void bpf_lru_push_free(struct bpf_lru *lru, struct bpf_lru_node *node)
552{
553 if (lru->percpu)
554 bpf_percpu_lru_push_free(lru, node);
555 else
556 bpf_common_lru_push_free(lru, node);
557}
558
559static void bpf_common_lru_populate(struct bpf_lru *lru, void *buf,
560 u32 node_offset, u32 elem_size,
561 u32 nr_elems)
562{
563 struct bpf_lru_list *l = &lru->common_lru.lru_list;
564 u32 i;
565
566 for (i = 0; i < nr_elems; i++) {
567 struct bpf_lru_node *node;
568
569 node = (struct bpf_lru_node *)(buf + node_offset);
570 node->type = BPF_LRU_LIST_T_FREE;
571 node->ref = 0;
572 list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);
573 buf += elem_size;
574 }
575}
576
577static void bpf_percpu_lru_populate(struct bpf_lru *lru, void *buf,
578 u32 node_offset, u32 elem_size,
579 u32 nr_elems)
580{
581 u32 i, pcpu_entries;
582 int cpu;
583 struct bpf_lru_list *l;
584
585 pcpu_entries = nr_elems / num_possible_cpus();
586
587 i = 0;
588
589 for_each_possible_cpu(cpu) {
590 struct bpf_lru_node *node;
591
592 l = per_cpu_ptr(lru->percpu_lru, cpu);
593again:
594 node = (struct bpf_lru_node *)(buf + node_offset);
595 node->cpu = cpu;
596 node->type = BPF_LRU_LIST_T_FREE;
597 node->ref = 0;
598 list_add(&node->list, &l->lists[BPF_LRU_LIST_T_FREE]);
599 i++;
600 buf += elem_size;
601 if (i == nr_elems)
602 break;
603 if (i % pcpu_entries)
604 goto again;
605 }
606}
607
608void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,
609 u32 elem_size, u32 nr_elems)
610{
611 if (lru->percpu)
612 bpf_percpu_lru_populate(lru, buf, node_offset, elem_size,
613 nr_elems);
614 else
615 bpf_common_lru_populate(lru, buf, node_offset, elem_size,
616 nr_elems);
617}
618
619static void bpf_lru_locallist_init(struct bpf_lru_locallist *loc_l, int cpu)
620{
621 int i;
622
623 for (i = 0; i < NR_BPF_LRU_LOCAL_LIST_T; i++)
624 INIT_LIST_HEAD(&loc_l->lists[i]);
625
626 loc_l->next_steal = cpu;
627
628 raw_spin_lock_init(&loc_l->lock);
629}
630
631static void bpf_lru_list_init(struct bpf_lru_list *l)
632{
633 int i;
634
635 for (i = 0; i < NR_BPF_LRU_LIST_T; i++)
636 INIT_LIST_HEAD(&l->lists[i]);
637
638 for (i = 0; i < NR_BPF_LRU_LIST_COUNT; i++)
639 l->counts[i] = 0;
640
641 l->next_inactive_rotation = &l->lists[BPF_LRU_LIST_T_INACTIVE];
642
643 raw_spin_lock_init(&l->lock);
644}
645
646int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
647 del_from_htab_func del_from_htab, void *del_arg)
648{
649 int cpu;
650
651 if (percpu) {
652 lru->percpu_lru = alloc_percpu(struct bpf_lru_list);
653 if (!lru->percpu_lru)
654 return -ENOMEM;
655
656 for_each_possible_cpu(cpu) {
657 struct bpf_lru_list *l;
658
659 l = per_cpu_ptr(lru->percpu_lru, cpu);
660 bpf_lru_list_init(l);
661 }
662 lru->nr_scans = PERCPU_NR_SCANS;
663 } else {
664 struct bpf_common_lru *clru = &lru->common_lru;
665
666 clru->local_list = alloc_percpu(struct bpf_lru_locallist);
667 if (!clru->local_list)
668 return -ENOMEM;
669
670 for_each_possible_cpu(cpu) {
671 struct bpf_lru_locallist *loc_l;
672
673 loc_l = per_cpu_ptr(clru->local_list, cpu);
674 bpf_lru_locallist_init(loc_l, cpu);
675 }
676
677 bpf_lru_list_init(&clru->lru_list);
678 lru->nr_scans = LOCAL_NR_SCANS;
679 }
680
681 lru->percpu = percpu;
682 lru->del_from_htab = del_from_htab;
683 lru->del_arg = del_arg;
684 lru->hash_offset = hash_offset;
685
686 return 0;
687}
688
689void bpf_lru_destroy(struct bpf_lru *lru)
690{
691 if (lru->percpu)
692 free_percpu(lru->percpu_lru);
693 else
694 free_percpu(lru->common_lru.local_list);
695}