kernel/bpf/percpu_freelist.c

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