LCOV - code coverage report
Current view: top level - kernel/bpf - bpf_lru_list.c (source / functions) Hit Total Coverage
Test: gcov_data_raspi2_real_modules_combined.info Lines: 0 245 0.0 %
Date: 2020-09-30 20:25:40 Functions: 0 23 0.0 %
Branches: 0 192 0.0 %

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

Generated by: LCOV version 1.14