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

source code of linux/kernel/bpf/bpf_lru_list.c