Branch data     Line data    Source code

       1                 :            : // SPDX-License-Identifier: GPL-2.0-only
       2                 :            : /* Copyright (c) 2016 Facebook
       3                 :            :  */
       4                 :            : #include "percpu_freelist.h"
       5                 :            : 
       6                 :          0 : int pcpu_freelist_init(struct pcpu_freelist *s)
       7                 :            : {
       8                 :            :         int cpu;
       9                 :            : 
      10                 :          0 :         s->freelist = alloc_percpu(struct pcpu_freelist_head);
      11                 :          0 :         if (!s->freelist)
      12                 :            :                 return -ENOMEM;
      13                 :            : 
      14                 :          0 :         for_each_possible_cpu(cpu) {
      15                 :          0 :                 struct pcpu_freelist_head *head = per_cpu_ptr(s->freelist, cpu);
      16                 :            : 
      17                 :          0 :                 raw_spin_lock_init(&head->lock);
      18                 :          0 :                 head->first = NULL;
      19                 :            :         }
      20                 :            :         return 0;
      21                 :            : }
      22                 :            : 
      23                 :          0 : void pcpu_freelist_destroy(struct pcpu_freelist *s)
      24                 :            : {
      25                 :          0 :         free_percpu(s->freelist);
      26                 :          0 : }
      27                 :            : 
      28                 :          0 : static inline void ___pcpu_freelist_push(struct pcpu_freelist_head *head,
      29                 :            :                                          struct pcpu_freelist_node *node)
      30                 :            : {
      31                 :          0 :         raw_spin_lock(&head->lock);
      32                 :          0 :         node->next = head->first;
      33                 :          0 :         head->first = node;
      34                 :            :         raw_spin_unlock(&head->lock);
      35                 :          0 : }
      36                 :            : 
      37                 :          0 : void __pcpu_freelist_push(struct pcpu_freelist *s,
      38                 :            :                         struct pcpu_freelist_node *node)
      39                 :            : {
      40                 :          0 :         struct pcpu_freelist_head *head = this_cpu_ptr(s->freelist);
      41                 :            : 
      42                 :          0 :         ___pcpu_freelist_push(head, node);
      43                 :          0 : }
      44                 :            : 
      45                 :          0 : void pcpu_freelist_push(struct pcpu_freelist *s,
      46                 :            :                         struct pcpu_freelist_node *node)
      47                 :            : {
      48                 :            :         unsigned long flags;
      49                 :            : 
      50                 :          0 :         local_irq_save(flags);
      51                 :            :         __pcpu_freelist_push(s, node);
      52                 :          0 :         local_irq_restore(flags);
      53                 :          0 : }
      54                 :            : 
      55                 :          0 : void pcpu_freelist_populate(struct pcpu_freelist *s, void *buf, u32 elem_size,
      56                 :            :                             u32 nr_elems)
      57                 :            : {
      58                 :            :         struct pcpu_freelist_head *head;
      59                 :            :         unsigned long flags;
      60                 :            :         int i, cpu, pcpu_entries;
      61                 :            : 
      62                 :          0 :         pcpu_entries = nr_elems / num_possible_cpus() + 1;
      63                 :            :         i = 0;
      64                 :            : 
      65                 :            :         /* disable irq to workaround lockdep false positive
      66                 :            :          * in bpf usage pcpu_freelist_populate() will never race
      67                 :            :          * with pcpu_freelist_push()
      68                 :            :          */
      69                 :          0 :         local_irq_save(flags);
      70                 :          0 :         for_each_possible_cpu(cpu) {
      71                 :            : again:
      72                 :          0 :                 head = per_cpu_ptr(s->freelist, cpu);
      73                 :          0 :                 ___pcpu_freelist_push(head, buf);
      74                 :          0 :                 i++;
      75                 :          0 :                 buf += elem_size;
      76                 :          0 :                 if (i == nr_elems)
      77                 :            :                         break;
      78                 :          0 :                 if (i % pcpu_entries)
      79                 :            :                         goto again;
      80                 :            :         }
      81                 :          0 :         local_irq_restore(flags);
      82                 :          0 : }
      83                 :            : 
      84                 :          0 : struct pcpu_freelist_node *__pcpu_freelist_pop(struct pcpu_freelist *s)
      85                 :            : {
      86                 :            :         struct pcpu_freelist_head *head;
      87                 :            :         struct pcpu_freelist_node *node;
      88                 :            :         int orig_cpu, cpu;
      89                 :            : 
      90                 :            :         orig_cpu = cpu = raw_smp_processor_id();
      91                 :            :         while (1) {
      92                 :          0 :                 head = per_cpu_ptr(s->freelist, cpu);
      93                 :          0 :                 raw_spin_lock(&head->lock);
      94                 :          0 :                 node = head->first;
      95                 :          0 :                 if (node) {
      96                 :          0 :                         head->first = node->next;
      97                 :            :                         raw_spin_unlock(&head->lock);
      98                 :          0 :                         return node;
      99                 :            :                 }
     100                 :            :                 raw_spin_unlock(&head->lock);
     101                 :          0 :                 cpu = cpumask_next(cpu, cpu_possible_mask);
     102                 :          0 :                 if (cpu >= nr_cpu_ids)
     103                 :            :                         cpu = 0;
     104                 :          0 :                 if (cpu == orig_cpu)
     105                 :            :                         return NULL;
     106                 :            :         }
     107                 :            : }
     108                 :            : 
     109                 :          0 : struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *s)
     110                 :            : {
     111                 :            :         struct pcpu_freelist_node *ret;
     112                 :            :         unsigned long flags;
     113                 :            : 
     114                 :          0 :         local_irq_save(flags);
     115                 :          0 :         ret = __pcpu_freelist_pop(s);
     116                 :          0 :         local_irq_restore(flags);
     117                 :          0 :         return ret;
     118                 :            : }