138494Sobrien// SPDX-License-Identifier: GPL-2.0-only 2174294Sobrien/* Copyright (c) 2016 Facebook 338494Sobrien */ 438494Sobrien#include "percpu_freelist.h" 538494Sobrien 638494Sobrienint pcpu_freelist_init(struct pcpu_freelist *s) 738494Sobrien{ 838494Sobrien int cpu; 938494Sobrien 1038494Sobrien s->freelist = alloc_percpu(struct pcpu_freelist_head); 1138494Sobrien if (!s->freelist) 1238494Sobrien return -ENOMEM; 1338494Sobrien 1438494Sobrien for_each_possible_cpu(cpu) { 1538494Sobrien struct pcpu_freelist_head *head = per_cpu_ptr(s->freelist, cpu); 1638494Sobrien 1738494Sobrien raw_spin_lock_init(&head->lock); 1838494Sobrien head->first = NULL; 1938494Sobrien } 2042629Sobrien raw_spin_lock_init(&s->extralist.lock); 2138494Sobrien s->extralist.first = NULL; 2238494Sobrien return 0; 2338494Sobrien} 2438494Sobrien 2538494Sobrienvoid pcpu_freelist_destroy(struct pcpu_freelist *s) 2638494Sobrien{ 2738494Sobrien free_percpu(s->freelist); 2838494Sobrien} 2938494Sobrien 3038494Sobrienstatic inline void pcpu_freelist_push_node(struct pcpu_freelist_head *head, 3138494Sobrien struct pcpu_freelist_node *node) 3238494Sobrien{ 3338494Sobrien node->next = head->first; 3438494Sobrien WRITE_ONCE(head->first, node); 3538494Sobrien} 3638494Sobrien 3738494Sobrienstatic inline void ___pcpu_freelist_push(struct pcpu_freelist_head *head, 3838494Sobrien struct pcpu_freelist_node *node) 3938494Sobrien{ 40174294Sobrien raw_spin_lock(&head->lock); 4138494Sobrien pcpu_freelist_push_node(head, node); 4238494Sobrien raw_spin_unlock(&head->lock); 4338494Sobrien} 4438494Sobrien 4538494Sobrienstatic inline bool pcpu_freelist_try_push_extra(struct pcpu_freelist *s, 4638494Sobrien struct pcpu_freelist_node *node) 4738494Sobrien{ 4838494Sobrien if (!raw_spin_trylock(&s->extralist.lock)) 4938494Sobrien return false; 5038494Sobrien 5138494Sobrien pcpu_freelist_push_node(&s->extralist, node); 5238494Sobrien raw_spin_unlock(&s->extralist.lock); 5338494Sobrien return true; 5438494Sobrien} 5538494Sobrien 56174294Sobrienstatic inline void ___pcpu_freelist_push_nmi(struct pcpu_freelist *s, 57174294Sobrien struct pcpu_freelist_node *node) 5838494Sobrien{ 5938494Sobrien int cpu, orig_cpu; 6038494Sobrien 6138494Sobrien orig_cpu = raw_smp_processor_id(); 6238494Sobrien while (1) { 6338494Sobrien for_each_cpu_wrap(cpu, cpu_possible_mask, orig_cpu) { 6438494Sobrien struct pcpu_freelist_head *head; 6538494Sobrien 6638494Sobrien head = per_cpu_ptr(s->freelist, cpu); 67174294Sobrien if (raw_spin_trylock(&head->lock)) { 68174294Sobrien pcpu_freelist_push_node(head, node); 69174294Sobrien raw_spin_unlock(&head->lock); 70174294Sobrien return; 7138494Sobrien } 7238494Sobrien } 7338494Sobrien 7438494Sobrien /* cannot lock any per cpu lock, try extralist */ 75174294Sobrien if (pcpu_freelist_try_push_extra(s, node)) 76174294Sobrien return; 77174294Sobrien } 78174294Sobrien} 79174294Sobrien 80174294Sobrienvoid __pcpu_freelist_push(struct pcpu_freelist *s, 8138494Sobrien struct pcpu_freelist_node *node) 8238494Sobrien{ 8338494Sobrien if (in_nmi()) 8438494Sobrien ___pcpu_freelist_push_nmi(s, node); 8538494Sobrien else 8638494Sobrien ___pcpu_freelist_push(this_cpu_ptr(s->freelist), node); 8738494Sobrien} 8838494Sobrien 8938494Sobrienvoid pcpu_freelist_push(struct pcpu_freelist *s, 9038494Sobrien struct pcpu_freelist_node *node) 9138494Sobrien{ 9238494Sobrien unsigned long flags; 9338494Sobrien 9438494Sobrien local_irq_save(flags); 9538494Sobrien __pcpu_freelist_push(s, node); 9638494Sobrien local_irq_restore(flags); 9738494Sobrien} 9838494Sobrien 9938494Sobrienvoid pcpu_freelist_populate(struct pcpu_freelist *s, void *buf, u32 elem_size, 10038494Sobrien u32 nr_elems) 10138494Sobrien{ 10238494Sobrien struct pcpu_freelist_head *head; 10338494Sobrien unsigned int cpu, cpu_idx, i, j, n, m; 10438494Sobrien 10538494Sobrien n = nr_elems / num_possible_cpus(); 106174294Sobrien m = nr_elems % num_possible_cpus(); 10738494Sobrien 10838494Sobrien cpu_idx = 0; 10938494Sobrien for_each_possible_cpu(cpu) { 11038494Sobrien head = per_cpu_ptr(s->freelist, cpu); 11138494Sobrien j = n + (cpu_idx < m ? 1 : 0); 11238494Sobrien for (i = 0; i < j; i++) { 11338494Sobrien /* No locking required as this is not visible yet. */ 11438494Sobrien pcpu_freelist_push_node(head, buf); 11538494Sobrien buf += elem_size; 11638494Sobrien } 11738494Sobrien cpu_idx++; 11838494Sobrien } 11938494Sobrien} 12038494Sobrien 12138494Sobrienstatic struct pcpu_freelist_node *___pcpu_freelist_pop(struct pcpu_freelist *s) 12238494Sobrien{ 123174294Sobrien struct pcpu_freelist_head *head; 12438494Sobrien struct pcpu_freelist_node *node; 12538494Sobrien int cpu; 12638494Sobrien 12738494Sobrien for_each_cpu_wrap(cpu, cpu_possible_mask, raw_smp_processor_id()) { 12838494Sobrien head = per_cpu_ptr(s->freelist, cpu); 129174294Sobrien if (!READ_ONCE(head->first)) 130174294Sobrien continue; 131174294Sobrien raw_spin_lock(&head->lock); 132174294Sobrien node = head->first; 13338494Sobrien if (node) { 134119679Smbr WRITE_ONCE(head->first, node->next); 13538494Sobrien raw_spin_unlock(&head->lock); 136119679Smbr return node; 137119679Smbr } 13838494Sobrien raw_spin_unlock(&head->lock); 139119679Smbr } 14038494Sobrien 14138494Sobrien /* per cpu lists are all empty, try extralist */ 14238494Sobrien if (!READ_ONCE(s->extralist.first)) 14338494Sobrien return NULL; 144174294Sobrien raw_spin_lock(&s->extralist.lock); 14538494Sobrien node = s->extralist.first; 14638494Sobrien if (node) 14738494Sobrien WRITE_ONCE(s->extralist.first, node->next); 14838494Sobrien raw_spin_unlock(&s->extralist.lock); 149174294Sobrien return node; 15038494Sobrien} 151174294Sobrien 15238494Sobrienstatic struct pcpu_freelist_node * 15338494Sobrien___pcpu_freelist_pop_nmi(struct pcpu_freelist *s) 154174294Sobrien{ 15538494Sobrien struct pcpu_freelist_head *head; 15638494Sobrien struct pcpu_freelist_node *node; 15738494Sobrien int cpu; 15838494Sobrien 15938494Sobrien for_each_cpu_wrap(cpu, cpu_possible_mask, raw_smp_processor_id()) { 16038494Sobrien head = per_cpu_ptr(s->freelist, cpu); 16138494Sobrien if (!READ_ONCE(head->first)) 16238494Sobrien continue; 16338494Sobrien if (raw_spin_trylock(&head->lock)) { 16438494Sobrien node = head->first; 16538494Sobrien if (node) { 166174294Sobrien WRITE_ONCE(head->first, node->next); 16738494Sobrien raw_spin_unlock(&head->lock); 168174294Sobrien return node; 169174294Sobrien } 170174294Sobrien raw_spin_unlock(&head->lock); 17138494Sobrien } 172174294Sobrien } 173 174 /* cannot pop from per cpu lists, try extralist */ 175 if (!READ_ONCE(s->extralist.first) || !raw_spin_trylock(&s->extralist.lock)) 176 return NULL; 177 node = s->extralist.first; 178 if (node) 179 WRITE_ONCE(s->extralist.first, node->next); 180 raw_spin_unlock(&s->extralist.lock); 181 return node; 182} 183 184struct pcpu_freelist_node *__pcpu_freelist_pop(struct pcpu_freelist *s) 185{ 186 if (in_nmi()) 187 return ___pcpu_freelist_pop_nmi(s); 188 return ___pcpu_freelist_pop(s); 189} 190 191struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *s) 192{ 193 struct pcpu_freelist_node *ret; 194 unsigned long flags; 195 196 local_irq_save(flags); 197 ret = __pcpu_freelist_pop(s); 198 local_irq_restore(flags); 199 return ret; 200} 201