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_populate(struct pcpu_freelist *s, void *buf, u32 elem_size,
  49                             u32 nr_elems)
  50 {
  51         struct pcpu_freelist_head *head;
  52         unsigned long flags;
  53         int i, cpu, pcpu_entries;
  54
  55         pcpu_entries = nr_elems / num_possible_cpus() + 1;
  56         i = 0;
  57
  58         /* disable irq to workaround lockdep false positive
  59          * in bpf usage pcpu_freelist_populate() will never race
  60          * with pcpu_freelist_push()
  61          */
  62         local_irq_save(flags);
  63         for_each_possible_cpu(cpu) {
  64 again:
  65                 head = per_cpu_ptr(s->freelist, cpu);
  66                 __pcpu_freelist_push(head, buf);
  67                 i++;
  68                 buf += elem_size;
  69                 if (i == nr_elems)
  70                         break;
  71                 if (i % pcpu_entries)
  72                         goto again;
  73         }
  74         local_irq_restore(flags);
  75 }
  76
  77 struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *s)
  78 {
  79         struct pcpu_freelist_head *head;
  80         struct pcpu_freelist_node *node;
  81         unsigned long flags;
  82         int orig_cpu, cpu;
  83
  84         local_irq_save(flags);
  85         orig_cpu = cpu = raw_smp_processor_id();
  86         while (1) {
  87                 head = per_cpu_ptr(s->freelist, cpu);
  88                 raw_spin_lock(&head->lock);
  89                 node = head->first;
  90                 if (node) {
  91                         head->first = node->next;
  92                         raw_spin_unlock_irqrestore(&head->lock, flags);
  93                         return node;
  94                 }
  95                 raw_spin_unlock(&head->lock);
  96                 cpu = cpumask_next(cpu, cpu_possible_mask);
  97                 if (cpu >= nr_cpu_ids)
  98                         cpu = 0;
  99                 if (cpu == orig_cpu) {
 100                         local_irq_restore(flags);
 101                         return NULL;
 102                 }
 103         }
 104 }