~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/kernel/bpf/bpf_lru_list.c

Version: ~ [ linux-5.6 ] ~ [ linux-5.5.13 ] ~ [ linux-5.4.28 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.113 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.174 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.217 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.217 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.82 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp