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_res_spin_lock_init(&head->lock); 18 head->first = NULL; 19 } 20 return 0; 21 } 22 23 void pcpu_freelist_destroy(struct pcpu_freelist *s) 24 { 25 free_percpu(s->freelist); 26 } 27 28 static inline void pcpu_freelist_push_node(struct pcpu_freelist_head *head, 29 struct pcpu_freelist_node *node) 30 { 31 node->next = head->first; 32 WRITE_ONCE(head->first, node); 33 } 34 35 static inline bool ___pcpu_freelist_push(struct pcpu_freelist_head *head, 36 struct pcpu_freelist_node *node) 37 { 38 if (raw_res_spin_lock(&head->lock)) 39 return false; 40 pcpu_freelist_push_node(head, node); 41 raw_res_spin_unlock(&head->lock); 42 return true; 43 } 44 45 void __pcpu_freelist_push(struct pcpu_freelist *s, 46 struct pcpu_freelist_node *node) 47 { 48 struct pcpu_freelist_head *head; 49 int cpu; 50 51 if (___pcpu_freelist_push(this_cpu_ptr(s->freelist), node)) 52 return; 53 54 while (true) { 55 for_each_cpu_wrap(cpu, cpu_possible_mask, raw_smp_processor_id()) { 56 if (cpu == raw_smp_processor_id()) 57 continue; 58 head = per_cpu_ptr(s->freelist, cpu); 59 if (raw_res_spin_lock(&head->lock)) 60 continue; 61 pcpu_freelist_push_node(head, node); 62 raw_res_spin_unlock(&head->lock); 63 return; 64 } 65 } 66 } 67 68 void pcpu_freelist_push(struct pcpu_freelist *s, 69 struct pcpu_freelist_node *node) 70 { 71 unsigned long flags; 72 73 local_irq_save(flags); 74 __pcpu_freelist_push(s, node); 75 local_irq_restore(flags); 76 } 77 78 void pcpu_freelist_populate(struct pcpu_freelist *s, void *buf, u32 elem_size, 79 u32 nr_elems) 80 { 81 struct pcpu_freelist_head *head; 82 unsigned int cpu, cpu_idx, i, j, n, m; 83 84 n = nr_elems / num_possible_cpus(); 85 m = nr_elems % num_possible_cpus(); 86 87 cpu_idx = 0; 88 for_each_possible_cpu(cpu) { 89 head = per_cpu_ptr(s->freelist, cpu); 90 j = n + (cpu_idx < m ? 1 : 0); 91 for (i = 0; i < j; i++) { 92 /* No locking required as this is not visible yet. */ 93 pcpu_freelist_push_node(head, buf); 94 buf += elem_size; 95 } 96 cpu_idx++; 97 } 98 } 99 100 static struct pcpu_freelist_node *___pcpu_freelist_pop(struct pcpu_freelist *s) 101 { 102 struct pcpu_freelist_node *node = NULL; 103 struct pcpu_freelist_head *head; 104 int cpu; 105 106 for_each_cpu_wrap(cpu, cpu_possible_mask, raw_smp_processor_id()) { 107 head = per_cpu_ptr(s->freelist, cpu); 108 if (!READ_ONCE(head->first)) 109 continue; 110 if (raw_res_spin_lock(&head->lock)) 111 continue; 112 node = head->first; 113 if (node) { 114 WRITE_ONCE(head->first, node->next); 115 raw_res_spin_unlock(&head->lock); 116 return node; 117 } 118 raw_res_spin_unlock(&head->lock); 119 } 120 return node; 121 } 122 123 struct pcpu_freelist_node *__pcpu_freelist_pop(struct pcpu_freelist *s) 124 { 125 return ___pcpu_freelist_pop(s); 126 } 127 128 struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *s) 129 { 130 struct pcpu_freelist_node *ret; 131 unsigned long flags; 132 133 local_irq_save(flags); 134 ret = __pcpu_freelist_pop(s); 135 local_irq_restore(flags); 136 return ret; 137 } 138