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 raw_spin_lock_init(&s->extralist.lock); 21 s->extralist.first = NULL; 22 return 0; 23 } 24 25 void pcpu_freelist_destroy(struct pcpu_freelist *s) 26 { 27 free_percpu(s->freelist); 28 } 29 30 static inline void pcpu_freelist_push_node(struct pcpu_freelist_head *head, 31 struct pcpu_freelist_node *node) 32 { 33 node->next = head->first; 34 WRITE_ONCE(head->first, node); 35 } 36 37 static inline void ___pcpu_freelist_push(struct pcpu_freelist_head *head, 38 struct pcpu_freelist_node *node) 39 { 40 raw_spin_lock(&head->lock); 41 pcpu_freelist_push_node(head, node); 42 raw_spin_unlock(&head->lock); 43 } 44 45 static inline bool pcpu_freelist_try_push_extra(struct pcpu_freelist *s, 46 struct pcpu_freelist_node *node) 47 { 48 if (!raw_spin_trylock(&s->extralist.lock)) 49 return false; 50 51 pcpu_freelist_push_node(&s->extralist, node); 52 raw_spin_unlock(&s->extralist.lock); 53 return true; 54 } 55 56 static inline void ___pcpu_freelist_push_nmi(struct pcpu_freelist *s, 57 struct pcpu_freelist_node *node) 58 { 59 int cpu, orig_cpu; 60 61 orig_cpu = cpu = raw_smp_processor_id(); 62 while (1) { 63 struct pcpu_freelist_head *head; 64 65 head = per_cpu_ptr(s->freelist, cpu); 66 if (raw_spin_trylock(&head->lock)) { 67 pcpu_freelist_push_node(head, node); 68 raw_spin_unlock(&head->lock); 69 return; 70 } 71 cpu = cpumask_next(cpu, cpu_possible_mask); 72 if (cpu >= nr_cpu_ids) 73 cpu = 0; 74 75 /* cannot lock any per cpu lock, try extralist */ 76 if (cpu == orig_cpu && 77 pcpu_freelist_try_push_extra(s, node)) 78 return; 79 } 80 } 81 82 void __pcpu_freelist_push(struct pcpu_freelist *s, 83 struct pcpu_freelist_node *node) 84 { 85 if (in_nmi()) 86 ___pcpu_freelist_push_nmi(s, node); 87 else 88 ___pcpu_freelist_push(this_cpu_ptr(s->freelist), node); 89 } 90 91 void pcpu_freelist_push(struct pcpu_freelist *s, 92 struct pcpu_freelist_node *node) 93 { 94 unsigned long flags; 95 96 local_irq_save(flags); 97 __pcpu_freelist_push(s, node); 98 local_irq_restore(flags); 99 } 100 101 void pcpu_freelist_populate(struct pcpu_freelist *s, void *buf, u32 elem_size, 102 u32 nr_elems) 103 { 104 struct pcpu_freelist_head *head; 105 int i, cpu, pcpu_entries; 106 107 pcpu_entries = nr_elems / num_possible_cpus() + 1; 108 i = 0; 109 110 for_each_possible_cpu(cpu) { 111 again: 112 head = per_cpu_ptr(s->freelist, cpu); 113 /* No locking required as this is not visible yet. */ 114 pcpu_freelist_push_node(head, buf); 115 i++; 116 buf += elem_size; 117 if (i == nr_elems) 118 break; 119 if (i % pcpu_entries) 120 goto again; 121 } 122 } 123 124 static struct pcpu_freelist_node *___pcpu_freelist_pop(struct pcpu_freelist *s) 125 { 126 struct pcpu_freelist_head *head; 127 struct pcpu_freelist_node *node; 128 int orig_cpu, cpu; 129 130 orig_cpu = cpu = raw_smp_processor_id(); 131 while (1) { 132 head = per_cpu_ptr(s->freelist, cpu); 133 if (!READ_ONCE(head->first)) 134 goto next_cpu; 135 raw_spin_lock(&head->lock); 136 node = head->first; 137 if (node) { 138 WRITE_ONCE(head->first, node->next); 139 raw_spin_unlock(&head->lock); 140 return node; 141 } 142 raw_spin_unlock(&head->lock); 143 next_cpu: 144 cpu = cpumask_next(cpu, cpu_possible_mask); 145 if (cpu >= nr_cpu_ids) 146 cpu = 0; 147 if (cpu == orig_cpu) 148 break; 149 } 150 151 /* per cpu lists are all empty, try extralist */ 152 if (!READ_ONCE(s->extralist.first)) 153 return NULL; 154 raw_spin_lock(&s->extralist.lock); 155 node = s->extralist.first; 156 if (node) 157 WRITE_ONCE(s->extralist.first, node->next); 158 raw_spin_unlock(&s->extralist.lock); 159 return node; 160 } 161 162 static struct pcpu_freelist_node * 163 ___pcpu_freelist_pop_nmi(struct pcpu_freelist *s) 164 { 165 struct pcpu_freelist_head *head; 166 struct pcpu_freelist_node *node; 167 int orig_cpu, cpu; 168 169 orig_cpu = cpu = raw_smp_processor_id(); 170 while (1) { 171 head = per_cpu_ptr(s->freelist, cpu); 172 if (!READ_ONCE(head->first)) 173 goto next_cpu; 174 if (raw_spin_trylock(&head->lock)) { 175 node = head->first; 176 if (node) { 177 WRITE_ONCE(head->first, node->next); 178 raw_spin_unlock(&head->lock); 179 return node; 180 } 181 raw_spin_unlock(&head->lock); 182 } 183 next_cpu: 184 cpu = cpumask_next(cpu, cpu_possible_mask); 185 if (cpu >= nr_cpu_ids) 186 cpu = 0; 187 if (cpu == orig_cpu) 188 break; 189 } 190 191 /* cannot pop from per cpu lists, try extralist */ 192 if (!READ_ONCE(s->extralist.first) || !raw_spin_trylock(&s->extralist.lock)) 193 return NULL; 194 node = s->extralist.first; 195 if (node) 196 WRITE_ONCE(s->extralist.first, node->next); 197 raw_spin_unlock(&s->extralist.lock); 198 return node; 199 } 200 201 struct pcpu_freelist_node *__pcpu_freelist_pop(struct pcpu_freelist *s) 202 { 203 if (in_nmi()) 204 return ___pcpu_freelist_pop_nmi(s); 205 return ___pcpu_freelist_pop(s); 206 } 207 208 struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *s) 209 { 210 struct pcpu_freelist_node *ret; 211 unsigned long flags; 212 213 local_irq_save(flags); 214 ret = __pcpu_freelist_pop(s); 215 local_irq_restore(flags); 216 return ret; 217 } 218