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