percpu_freelist.c

  1// SPDX-License-Identifier: GPL-2.0-only
  2/* Copyright (c) 2016 Facebook
  3 */
  4#include "percpu_freelist.h"
  5
  6int 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
 23void pcpu_freelist_destroy(struct pcpu_freelist *s)
 24{
 25	free_percpu(s->freelist);
 26}
 27
 28static 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
 35static 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
 45void __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
 68void 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
 78void 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
100static 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
123struct pcpu_freelist_node *__pcpu_freelist_pop(struct pcpu_freelist *s)
124{
125	return ___pcpu_freelist_pop(s);
126}
127
128struct 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}