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 } 105