bpf_lru_list.c

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