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 raw_res_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 bool ___pcpu_freelist_push(struct pcpu_freelist_head *head, 38 struct pcpu_freelist_node *node) 39 { 40 if (raw_res_spin_lock(&head->lock)) 41 return false; 42 pcpu_freelist_push_node(head, node); 43 raw_res_spin_unlock(&head->lock); 44 return true; 45 } 46 47 void __pcpu_freelist_push(struct pcpu_freelist *s, 48 struct pcpu_freelist_node *node) 49 { 50 struct pcpu_freelist_head *head; 51 int cpu, this_cpu; 52 53 if (___pcpu_freelist_push(this_cpu_ptr(s->freelist), node)) 54 return; 55 56 this_cpu = raw_smp_processor_id(); 57 while (true) { 58 for_each_cpu_wrap(cpu, cpu_possible_mask, this_cpu) { 59 if (cpu == this_cpu) 60 continue; 61 62 head = per_cpu_ptr(s->freelist, cpu); 63 if (___pcpu_freelist_push(head, node)) 64 return; 65 } 66 67 /* 68 * Push cannot fail. Use the extra list when none of the 69 * per-CPU freelists can accept the node. 70 */ 71 if (___pcpu_freelist_push(&s->extralist, node)) 72 return; 73 } 74 } 75 76 void pcpu_freelist_push(struct pcpu_freelist *s, 77 struct pcpu_freelist_node *node) 78 { 79 unsigned long flags; 80 81 local_irq_save(flags); 82 __pcpu_freelist_push(s, node); 83 local_irq_restore(flags); 84 } 85 86 void pcpu_freelist_populate(struct pcpu_freelist *s, void *buf, u32 elem_size, 87 u32 nr_elems) 88 { 89 struct pcpu_freelist_head *head; 90 unsigned int cpu, cpu_idx, i, j, n, m; 91 92 n = nr_elems / num_possible_cpus(); 93 m = nr_elems % num_possible_cpus(); 94 95 cpu_idx = 0; 96 for_each_possible_cpu(cpu) { 97 head = per_cpu_ptr(s->freelist, cpu); 98 j = n + (cpu_idx < m ? 1 : 0); 99 for (i = 0; i < j; i++) { 100 /* No locking required as this is not visible yet. */ 101 pcpu_freelist_push_node(head, buf); 102 buf += elem_size; 103 } 104 cpu_idx++; 105 } 106 } 107 108 static struct pcpu_freelist_node *___pcpu_freelist_pop(struct pcpu_freelist *s) 109 { 110 struct pcpu_freelist_node *node = NULL; 111 struct pcpu_freelist_head *head; 112 int cpu; 113 114 for_each_cpu_wrap(cpu, cpu_possible_mask, raw_smp_processor_id()) { 115 head = per_cpu_ptr(s->freelist, cpu); 116 if (!READ_ONCE(head->first)) 117 continue; 118 if (raw_res_spin_lock(&head->lock)) 119 continue; 120 node = head->first; 121 if (node) { 122 WRITE_ONCE(head->first, node->next); 123 raw_res_spin_unlock(&head->lock); 124 return node; 125 } 126 raw_res_spin_unlock(&head->lock); 127 } 128 129 /* Per-CPU lists are empty or unavailable, try the extra list. */ 130 head = &s->extralist; 131 if (!READ_ONCE(head->first)) 132 return NULL; 133 if (raw_res_spin_lock(&head->lock)) 134 return NULL; 135 node = head->first; 136 if (node) 137 WRITE_ONCE(head->first, node->next); 138 raw_res_spin_unlock(&head->lock); 139 return node; 140 } 141 142 struct pcpu_freelist_node *__pcpu_freelist_pop(struct pcpu_freelist *s) 143 { 144 return ___pcpu_freelist_pop(s); 145 } 146 147 struct pcpu_freelist_node *pcpu_freelist_pop(struct pcpu_freelist *s) 148 { 149 struct pcpu_freelist_node *ret; 150 unsigned long flags; 151 152 local_irq_save(flags); 153 ret = __pcpu_freelist_pop(s); 154 local_irq_restore(flags); 155 return ret; 156 } 157