1d2912cb1SThomas Gleixner // SPDX-License-Identifier: GPL-2.0-only
2c39649c3SBen Hutchings /*
3c39649c3SBen Hutchings * cpu_rmap.c: CPU affinity reverse-map support
4c39649c3SBen Hutchings * Copyright 2011 Solarflare Communications Inc.
5c39649c3SBen Hutchings */
6c39649c3SBen Hutchings
7c39649c3SBen Hutchings #include <linux/cpu_rmap.h>
8c39649c3SBen Hutchings #include <linux/interrupt.h>
98bc3bcc9SPaul Gortmaker #include <linux/export.h>
10c39649c3SBen Hutchings
11c39649c3SBen Hutchings /*
12c39649c3SBen Hutchings * These functions maintain a mapping from CPUs to some ordered set of
13c39649c3SBen Hutchings * objects with CPU affinities. This can be seen as a reverse-map of
14c39649c3SBen Hutchings * CPU affinity. However, we do not assume that the object affinities
15c39649c3SBen Hutchings * cover all CPUs in the system. For those CPUs not directly covered
16c39649c3SBen Hutchings * by object affinities, we attempt to find a nearest object based on
17c39649c3SBen Hutchings * CPU topology.
18c39649c3SBen Hutchings */
19c39649c3SBen Hutchings
20c39649c3SBen Hutchings /**
21c39649c3SBen Hutchings * alloc_cpu_rmap - allocate CPU affinity reverse-map
22c39649c3SBen Hutchings * @size: Number of objects to be mapped
23c39649c3SBen Hutchings * @flags: Allocation flags e.g. %GFP_KERNEL
24c39649c3SBen Hutchings */
alloc_cpu_rmap(unsigned int size,gfp_t flags)25c39649c3SBen Hutchings struct cpu_rmap *alloc_cpu_rmap(unsigned int size, gfp_t flags)
26c39649c3SBen Hutchings {
27c39649c3SBen Hutchings struct cpu_rmap *rmap;
28c39649c3SBen Hutchings unsigned int cpu;
29c39649c3SBen Hutchings size_t obj_offset;
30c39649c3SBen Hutchings
31c39649c3SBen Hutchings /* This is a silly number of objects, and we use u16 indices. */
32c39649c3SBen Hutchings if (size > 0xffff)
33c39649c3SBen Hutchings return NULL;
34c39649c3SBen Hutchings
35c39649c3SBen Hutchings /* Offset of object pointer array from base structure */
36c39649c3SBen Hutchings obj_offset = ALIGN(offsetof(struct cpu_rmap, near[nr_cpu_ids]),
37c39649c3SBen Hutchings sizeof(void *));
38c39649c3SBen Hutchings
39c39649c3SBen Hutchings rmap = kzalloc(obj_offset + size * sizeof(rmap->obj[0]), flags);
40c39649c3SBen Hutchings if (!rmap)
41c39649c3SBen Hutchings return NULL;
42c39649c3SBen Hutchings
43896f97eaSDavid Decotigny kref_init(&rmap->refcount);
44c39649c3SBen Hutchings rmap->obj = (void **)((char *)rmap + obj_offset);
45c39649c3SBen Hutchings
46c39649c3SBen Hutchings /* Initially assign CPUs to objects on a rota, since we have
47c39649c3SBen Hutchings * no idea where the objects are. Use infinite distance, so
48c39649c3SBen Hutchings * any object with known distance is preferable. Include the
49c39649c3SBen Hutchings * CPUs that are not present/online, since we definitely want
50c39649c3SBen Hutchings * any newly-hotplugged CPUs to have some object assigned.
51c39649c3SBen Hutchings */
52c39649c3SBen Hutchings for_each_possible_cpu(cpu) {
53c39649c3SBen Hutchings rmap->near[cpu].index = cpu % size;
54c39649c3SBen Hutchings rmap->near[cpu].dist = CPU_RMAP_DIST_INF;
55c39649c3SBen Hutchings }
56c39649c3SBen Hutchings
57c39649c3SBen Hutchings rmap->size = size;
58c39649c3SBen Hutchings return rmap;
59c39649c3SBen Hutchings }
60c39649c3SBen Hutchings EXPORT_SYMBOL(alloc_cpu_rmap);
61c39649c3SBen Hutchings
62896f97eaSDavid Decotigny /**
63896f97eaSDavid Decotigny * cpu_rmap_release - internal reclaiming helper called from kref_put
64896f97eaSDavid Decotigny * @ref: kref to struct cpu_rmap
65896f97eaSDavid Decotigny */
cpu_rmap_release(struct kref * ref)66896f97eaSDavid Decotigny static void cpu_rmap_release(struct kref *ref)
67896f97eaSDavid Decotigny {
68896f97eaSDavid Decotigny struct cpu_rmap *rmap = container_of(ref, struct cpu_rmap, refcount);
69896f97eaSDavid Decotigny kfree(rmap);
70896f97eaSDavid Decotigny }
71896f97eaSDavid Decotigny
72896f97eaSDavid Decotigny /**
73896f97eaSDavid Decotigny * cpu_rmap_get - internal helper to get new ref on a cpu_rmap
74896f97eaSDavid Decotigny * @rmap: reverse-map allocated with alloc_cpu_rmap()
75896f97eaSDavid Decotigny */
cpu_rmap_get(struct cpu_rmap * rmap)76896f97eaSDavid Decotigny static inline void cpu_rmap_get(struct cpu_rmap *rmap)
77896f97eaSDavid Decotigny {
78896f97eaSDavid Decotigny kref_get(&rmap->refcount);
79896f97eaSDavid Decotigny }
80896f97eaSDavid Decotigny
81896f97eaSDavid Decotigny /**
82896f97eaSDavid Decotigny * cpu_rmap_put - release ref on a cpu_rmap
83896f97eaSDavid Decotigny * @rmap: reverse-map allocated with alloc_cpu_rmap()
84896f97eaSDavid Decotigny */
cpu_rmap_put(struct cpu_rmap * rmap)85896f97eaSDavid Decotigny int cpu_rmap_put(struct cpu_rmap *rmap)
86896f97eaSDavid Decotigny {
87896f97eaSDavid Decotigny return kref_put(&rmap->refcount, cpu_rmap_release);
88896f97eaSDavid Decotigny }
89896f97eaSDavid Decotigny EXPORT_SYMBOL(cpu_rmap_put);
90896f97eaSDavid Decotigny
91c39649c3SBen Hutchings /* Reevaluate nearest object for given CPU, comparing with the given
92c39649c3SBen Hutchings * neighbours at the given distance.
93c39649c3SBen Hutchings */
cpu_rmap_copy_neigh(struct cpu_rmap * rmap,unsigned int cpu,const struct cpumask * mask,u16 dist)94c39649c3SBen Hutchings static bool cpu_rmap_copy_neigh(struct cpu_rmap *rmap, unsigned int cpu,
95c39649c3SBen Hutchings const struct cpumask *mask, u16 dist)
96c39649c3SBen Hutchings {
97c39649c3SBen Hutchings int neigh;
98c39649c3SBen Hutchings
99c39649c3SBen Hutchings for_each_cpu(neigh, mask) {
100c39649c3SBen Hutchings if (rmap->near[cpu].dist > dist &&
101c39649c3SBen Hutchings rmap->near[neigh].dist <= dist) {
102c39649c3SBen Hutchings rmap->near[cpu].index = rmap->near[neigh].index;
103c39649c3SBen Hutchings rmap->near[cpu].dist = dist;
104c39649c3SBen Hutchings return true;
105c39649c3SBen Hutchings }
106c39649c3SBen Hutchings }
107c39649c3SBen Hutchings return false;
108c39649c3SBen Hutchings }
109c39649c3SBen Hutchings
110c39649c3SBen Hutchings #ifdef DEBUG
debug_print_rmap(const struct cpu_rmap * rmap,const char * prefix)111c39649c3SBen Hutchings static void debug_print_rmap(const struct cpu_rmap *rmap, const char *prefix)
112c39649c3SBen Hutchings {
113c39649c3SBen Hutchings unsigned index;
114c39649c3SBen Hutchings unsigned int cpu;
115c39649c3SBen Hutchings
116c39649c3SBen Hutchings pr_info("cpu_rmap %p, %s:\n", rmap, prefix);
117c39649c3SBen Hutchings
118c39649c3SBen Hutchings for_each_possible_cpu(cpu) {
119c39649c3SBen Hutchings index = rmap->near[cpu].index;
120c39649c3SBen Hutchings pr_info("cpu %d -> obj %u (distance %u)\n",
121c39649c3SBen Hutchings cpu, index, rmap->near[cpu].dist);
122c39649c3SBen Hutchings }
123c39649c3SBen Hutchings }
124c39649c3SBen Hutchings #else
125c39649c3SBen Hutchings static inline void
debug_print_rmap(const struct cpu_rmap * rmap,const char * prefix)126c39649c3SBen Hutchings debug_print_rmap(const struct cpu_rmap *rmap, const char *prefix)
127c39649c3SBen Hutchings {
128c39649c3SBen Hutchings }
129c39649c3SBen Hutchings #endif
130c39649c3SBen Hutchings
get_free_index(struct cpu_rmap * rmap)1319821d8d4SEli Cohen static int get_free_index(struct cpu_rmap *rmap)
1329821d8d4SEli Cohen {
1339821d8d4SEli Cohen int i;
1349821d8d4SEli Cohen
1359821d8d4SEli Cohen for (i = 0; i < rmap->size; i++)
1369821d8d4SEli Cohen if (!rmap->obj[i])
1379821d8d4SEli Cohen return i;
1389821d8d4SEli Cohen
1399821d8d4SEli Cohen return -ENOSPC;
1409821d8d4SEli Cohen }
1419821d8d4SEli Cohen
142c39649c3SBen Hutchings /**
143c39649c3SBen Hutchings * cpu_rmap_add - add object to a rmap
144c39649c3SBen Hutchings * @rmap: CPU rmap allocated with alloc_cpu_rmap()
145c39649c3SBen Hutchings * @obj: Object to add to rmap
146c39649c3SBen Hutchings *
1479821d8d4SEli Cohen * Return index of object or -ENOSPC if no free entry was found
148c39649c3SBen Hutchings */
cpu_rmap_add(struct cpu_rmap * rmap,void * obj)149c39649c3SBen Hutchings int cpu_rmap_add(struct cpu_rmap *rmap, void *obj)
150c39649c3SBen Hutchings {
1519821d8d4SEli Cohen int index = get_free_index(rmap);
152c39649c3SBen Hutchings
1539821d8d4SEli Cohen if (index < 0)
1549821d8d4SEli Cohen return index;
1559821d8d4SEli Cohen
156c39649c3SBen Hutchings rmap->obj[index] = obj;
157c39649c3SBen Hutchings return index;
158c39649c3SBen Hutchings }
159c39649c3SBen Hutchings EXPORT_SYMBOL(cpu_rmap_add);
160c39649c3SBen Hutchings
161c39649c3SBen Hutchings /**
162c39649c3SBen Hutchings * cpu_rmap_update - update CPU rmap following a change of object affinity
163c39649c3SBen Hutchings * @rmap: CPU rmap to update
164c39649c3SBen Hutchings * @index: Index of object whose affinity changed
165c39649c3SBen Hutchings * @affinity: New CPU affinity of object
166c39649c3SBen Hutchings */
cpu_rmap_update(struct cpu_rmap * rmap,u16 index,const struct cpumask * affinity)167c39649c3SBen Hutchings int cpu_rmap_update(struct cpu_rmap *rmap, u16 index,
168c39649c3SBen Hutchings const struct cpumask *affinity)
169c39649c3SBen Hutchings {
170c39649c3SBen Hutchings cpumask_var_t update_mask;
171c39649c3SBen Hutchings unsigned int cpu;
172c39649c3SBen Hutchings
173c39649c3SBen Hutchings if (unlikely(!zalloc_cpumask_var(&update_mask, GFP_KERNEL)))
174c39649c3SBen Hutchings return -ENOMEM;
175c39649c3SBen Hutchings
176c39649c3SBen Hutchings /* Invalidate distance for all CPUs for which this used to be
177c39649c3SBen Hutchings * the nearest object. Mark those CPUs for update.
178c39649c3SBen Hutchings */
179c39649c3SBen Hutchings for_each_online_cpu(cpu) {
180c39649c3SBen Hutchings if (rmap->near[cpu].index == index) {
181c39649c3SBen Hutchings rmap->near[cpu].dist = CPU_RMAP_DIST_INF;
182c39649c3SBen Hutchings cpumask_set_cpu(cpu, update_mask);
183c39649c3SBen Hutchings }
184c39649c3SBen Hutchings }
185c39649c3SBen Hutchings
186c39649c3SBen Hutchings debug_print_rmap(rmap, "after invalidating old distances");
187c39649c3SBen Hutchings
188c39649c3SBen Hutchings /* Set distance to 0 for all CPUs in the new affinity mask.
189c39649c3SBen Hutchings * Mark all CPUs within their NUMA nodes for update.
190c39649c3SBen Hutchings */
191c39649c3SBen Hutchings for_each_cpu(cpu, affinity) {
192c39649c3SBen Hutchings rmap->near[cpu].index = index;
193c39649c3SBen Hutchings rmap->near[cpu].dist = 0;
194c39649c3SBen Hutchings cpumask_or(update_mask, update_mask,
195c39649c3SBen Hutchings cpumask_of_node(cpu_to_node(cpu)));
196c39649c3SBen Hutchings }
197c39649c3SBen Hutchings
198c39649c3SBen Hutchings debug_print_rmap(rmap, "after updating neighbours");
199c39649c3SBen Hutchings
200c39649c3SBen Hutchings /* Update distances based on topology */
201c39649c3SBen Hutchings for_each_cpu(cpu, update_mask) {
202c39649c3SBen Hutchings if (cpu_rmap_copy_neigh(rmap, cpu,
20306931e62SBartosz Golaszewski topology_sibling_cpumask(cpu), 1))
204c39649c3SBen Hutchings continue;
205c39649c3SBen Hutchings if (cpu_rmap_copy_neigh(rmap, cpu,
206c39649c3SBen Hutchings topology_core_cpumask(cpu), 2))
207c39649c3SBen Hutchings continue;
208c39649c3SBen Hutchings if (cpu_rmap_copy_neigh(rmap, cpu,
209c39649c3SBen Hutchings cpumask_of_node(cpu_to_node(cpu)), 3))
210c39649c3SBen Hutchings continue;
211c39649c3SBen Hutchings /* We could continue into NUMA node distances, but for now
212c39649c3SBen Hutchings * we give up.
213c39649c3SBen Hutchings */
214c39649c3SBen Hutchings }
215c39649c3SBen Hutchings
216c39649c3SBen Hutchings debug_print_rmap(rmap, "after copying neighbours");
217c39649c3SBen Hutchings
218c39649c3SBen Hutchings free_cpumask_var(update_mask);
219c39649c3SBen Hutchings return 0;
220c39649c3SBen Hutchings }
221c39649c3SBen Hutchings EXPORT_SYMBOL(cpu_rmap_update);
222c39649c3SBen Hutchings
223c39649c3SBen Hutchings /* Glue between IRQ affinity notifiers and CPU rmaps */
224c39649c3SBen Hutchings
225c39649c3SBen Hutchings struct irq_glue {
226c39649c3SBen Hutchings struct irq_affinity_notify notify;
227c39649c3SBen Hutchings struct cpu_rmap *rmap;
228c39649c3SBen Hutchings u16 index;
229c39649c3SBen Hutchings };
230c39649c3SBen Hutchings
231c39649c3SBen Hutchings /**
232c39649c3SBen Hutchings * free_irq_cpu_rmap - free a CPU affinity reverse-map used for IRQs
233c39649c3SBen Hutchings * @rmap: Reverse-map allocated with alloc_irq_cpu_map(), or %NULL
234c39649c3SBen Hutchings *
235896f97eaSDavid Decotigny * Must be called in process context, before freeing the IRQs.
236c39649c3SBen Hutchings */
free_irq_cpu_rmap(struct cpu_rmap * rmap)237c39649c3SBen Hutchings void free_irq_cpu_rmap(struct cpu_rmap *rmap)
238c39649c3SBen Hutchings {
239c39649c3SBen Hutchings struct irq_glue *glue;
240c39649c3SBen Hutchings u16 index;
241c39649c3SBen Hutchings
242c39649c3SBen Hutchings if (!rmap)
243c39649c3SBen Hutchings return;
244c39649c3SBen Hutchings
2459821d8d4SEli Cohen for (index = 0; index < rmap->size; index++) {
246c39649c3SBen Hutchings glue = rmap->obj[index];
2474e0473f1SEli Cohen if (glue)
248c39649c3SBen Hutchings irq_set_affinity_notifier(glue->notify.irq, NULL);
249c39649c3SBen Hutchings }
250c39649c3SBen Hutchings
251896f97eaSDavid Decotigny cpu_rmap_put(rmap);
252c39649c3SBen Hutchings }
253c39649c3SBen Hutchings EXPORT_SYMBOL(free_irq_cpu_rmap);
254c39649c3SBen Hutchings
255896f97eaSDavid Decotigny /**
256896f97eaSDavid Decotigny * irq_cpu_rmap_notify - callback for IRQ subsystem when IRQ affinity updated
257896f97eaSDavid Decotigny * @notify: struct irq_affinity_notify passed by irq/manage.c
258896f97eaSDavid Decotigny * @mask: cpu mask for new SMP affinity
259896f97eaSDavid Decotigny *
260896f97eaSDavid Decotigny * This is executed in workqueue context.
261896f97eaSDavid Decotigny */
262c39649c3SBen Hutchings static void
irq_cpu_rmap_notify(struct irq_affinity_notify * notify,const cpumask_t * mask)263c39649c3SBen Hutchings irq_cpu_rmap_notify(struct irq_affinity_notify *notify, const cpumask_t *mask)
264c39649c3SBen Hutchings {
265c39649c3SBen Hutchings struct irq_glue *glue =
266c39649c3SBen Hutchings container_of(notify, struct irq_glue, notify);
267c39649c3SBen Hutchings int rc;
268c39649c3SBen Hutchings
269c39649c3SBen Hutchings rc = cpu_rmap_update(glue->rmap, glue->index, mask);
270c39649c3SBen Hutchings if (rc)
271256339d6SKefeng Wang pr_warn("irq_cpu_rmap_notify: update failed: %d\n", rc);
272c39649c3SBen Hutchings }
273c39649c3SBen Hutchings
274896f97eaSDavid Decotigny /**
275896f97eaSDavid Decotigny * irq_cpu_rmap_release - reclaiming callback for IRQ subsystem
276896f97eaSDavid Decotigny * @ref: kref to struct irq_affinity_notify passed by irq/manage.c
277896f97eaSDavid Decotigny */
irq_cpu_rmap_release(struct kref * ref)278c39649c3SBen Hutchings static void irq_cpu_rmap_release(struct kref *ref)
279c39649c3SBen Hutchings {
280c39649c3SBen Hutchings struct irq_glue *glue =
281c39649c3SBen Hutchings container_of(ref, struct irq_glue, notify.kref);
282896f97eaSDavid Decotigny
2834e0473f1SEli Cohen glue->rmap->obj[glue->index] = NULL;
284*7c5d4801SBen Hutchings cpu_rmap_put(glue->rmap);
285c39649c3SBen Hutchings kfree(glue);
286c39649c3SBen Hutchings }
287c39649c3SBen Hutchings
288c39649c3SBen Hutchings /**
28971f0a247SEli Cohen * irq_cpu_rmap_remove - remove an IRQ from a CPU affinity reverse-map
29071f0a247SEli Cohen * @rmap: The reverse-map
29171f0a247SEli Cohen * @irq: The IRQ number
29271f0a247SEli Cohen */
irq_cpu_rmap_remove(struct cpu_rmap * rmap,int irq)29371f0a247SEli Cohen int irq_cpu_rmap_remove(struct cpu_rmap *rmap, int irq)
29471f0a247SEli Cohen {
29571f0a247SEli Cohen return irq_set_affinity_notifier(irq, NULL);
29671f0a247SEli Cohen }
29771f0a247SEli Cohen EXPORT_SYMBOL(irq_cpu_rmap_remove);
29871f0a247SEli Cohen
29971f0a247SEli Cohen /**
300c39649c3SBen Hutchings * irq_cpu_rmap_add - add an IRQ to a CPU affinity reverse-map
301c39649c3SBen Hutchings * @rmap: The reverse-map
302c39649c3SBen Hutchings * @irq: The IRQ number
303c39649c3SBen Hutchings *
304c39649c3SBen Hutchings * This adds an IRQ affinity notifier that will update the reverse-map
305c39649c3SBen Hutchings * automatically.
306c39649c3SBen Hutchings *
307c39649c3SBen Hutchings * Must be called in process context, after the IRQ is allocated but
308c39649c3SBen Hutchings * before it is bound with request_irq().
309c39649c3SBen Hutchings */
irq_cpu_rmap_add(struct cpu_rmap * rmap,int irq)310c39649c3SBen Hutchings int irq_cpu_rmap_add(struct cpu_rmap *rmap, int irq)
311c39649c3SBen Hutchings {
312c39649c3SBen Hutchings struct irq_glue *glue = kzalloc(sizeof(*glue), GFP_KERNEL);
313c39649c3SBen Hutchings int rc;
314c39649c3SBen Hutchings
315c39649c3SBen Hutchings if (!glue)
316c39649c3SBen Hutchings return -ENOMEM;
317c39649c3SBen Hutchings glue->notify.notify = irq_cpu_rmap_notify;
318c39649c3SBen Hutchings glue->notify.release = irq_cpu_rmap_release;
319c39649c3SBen Hutchings glue->rmap = rmap;
320896f97eaSDavid Decotigny cpu_rmap_get(rmap);
3219821d8d4SEli Cohen rc = cpu_rmap_add(rmap, glue);
3229821d8d4SEli Cohen if (rc < 0)
3239821d8d4SEli Cohen goto err_add;
3249821d8d4SEli Cohen
3259821d8d4SEli Cohen glue->index = rc;
326c39649c3SBen Hutchings rc = irq_set_affinity_notifier(irq, &glue->notify);
3279821d8d4SEli Cohen if (rc)
3289821d8d4SEli Cohen goto err_set;
3299821d8d4SEli Cohen
3309821d8d4SEli Cohen return rc;
3319821d8d4SEli Cohen
3329821d8d4SEli Cohen err_set:
3334e0473f1SEli Cohen rmap->obj[glue->index] = NULL;
3349821d8d4SEli Cohen err_add:
3359821d8d4SEli Cohen cpu_rmap_put(glue->rmap);
336c39649c3SBen Hutchings kfree(glue);
337c39649c3SBen Hutchings return rc;
338c39649c3SBen Hutchings }
339c39649c3SBen Hutchings EXPORT_SYMBOL(irq_cpu_rmap_add);
340