kernel/bpf/percpu_freelist.c

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