1 // SPDX-License-Identifier: GPL-2.0-only
2 /* Copyright (c) 2016 Facebook
3 */
4 #include "percpu_freelist.h"
5
pcpu_freelist_init(struct pcpu_freelist * s)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
pcpu_freelist_destroy(struct pcpu_freelist * s)23 void pcpu_freelist_destroy(struct pcpu_freelist *s)
24 {
25 free_percpu(s->freelist);
26 }
27
pcpu_freelist_push_node(struct pcpu_freelist_head * head,struct pcpu_freelist_node * node)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
___pcpu_freelist_push(struct pcpu_freelist_head * head,struct pcpu_freelist_node * node)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
__pcpu_freelist_push(struct pcpu_freelist * s,struct pcpu_freelist_node * node)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
pcpu_freelist_push(struct pcpu_freelist * s,struct pcpu_freelist_node * node)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
pcpu_freelist_populate(struct pcpu_freelist * s,void * buf,u32 elem_size,u32 nr_elems)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
___pcpu_freelist_pop(struct pcpu_freelist * s)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
__pcpu_freelist_pop(struct pcpu_freelist * s)123 struct pcpu_freelist_node *__pcpu_freelist_pop(struct pcpu_freelist *s)
124 {
125 return ___pcpu_freelist_pop(s);
126 }
127
pcpu_freelist_pop(struct pcpu_freelist * s)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