summaryrefslogtreecommitdiffstats
path: root/lib/percpu_counter.c
blob: 2891f94a11c654958fb52f8d965d06b62719500c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
// SPDX-License-Identifier: GPL-2.0
/*
 * Fast batching percpu counters.
 */

#include <linux/percpu_counter.h>
#include <linux/mutex.h>
#include <linux/init.h>
#include <linux/cpu.h>
#include <linux/module.h>
#include <linux/debugobjects.h>

#ifdef CONFIG_HOTPLUG_CPU
static LIST_HEAD(percpu_counters);
static DEFINE_SPINLOCK(percpu_counters_lock);
#endif

#ifdef CONFIG_DEBUG_OBJECTS_PERCPU_COUNTER

static const struct debug_obj_descr percpu_counter_debug_descr;

static bool percpu_counter_fixup_free(void *addr, enum debug_obj_state state)
{
	struct percpu_counter *fbc = addr;

	switch (state) {
	case ODEBUG_STATE_ACTIVE:
		percpu_counter_destroy(fbc);
		debug_object_free(fbc, &percpu_counter_debug_descr);
		return true;
	default:
		return false;
	}
}

static const struct debug_obj_descr percpu_counter_debug_descr = {
	.name		= "percpu_counter",
	.fixup_free	= percpu_counter_fixup_free,
};

static inline void debug_percpu_counter_activate(struct percpu_counter *fbc)
{
	debug_object_init(fbc, &percpu_counter_debug_descr);
	debug_object_activate(fbc, &percpu_counter_debug_descr);
}

static inline void debug_percpu_counter_deactivate(struct percpu_counter *fbc)
{
	debug_object_deactivate(fbc, &percpu_counter_debug_descr);
	debug_object_free(fbc, &percpu_counter_debug_descr);
}

#else	/* CONFIG_DEBUG_OBJECTS_PERCPU_COUNTER */
static inline void debug_percpu_counter_activate(struct percpu_counter *fbc)
{ }
static inline void debug_percpu_counter_deactivate(struct percpu_counter *fbc)
{ }
#endif	/* CONFIG_DEBUG_OBJECTS_PERCPU_COUNTER */

void percpu_counter_set(struct percpu_counter *fbc, s64 amount)
{
	int cpu;
	unsigned long flags;

	raw_spin_lock_irqsave(&fbc->lock, flags);
	for_each_possible_cpu(cpu) {
		s32 *pcount = per_cpu_ptr(fbc->counters, cpu);
		*pcount = 0;
	}
	fbc->count = amount;
	raw_spin_unlock_irqrestore(&fbc->lock, flags);
}
EXPORT_SYMBOL(percpu_counter_set);

/*
 * Add to a counter while respecting batch size.
 *
 * There are 2 implementations, both dealing with the following problem:
 *
 * The decision slow path/fast path and the actual update must be atomic.
 * Otherwise a call in process context could check the current values and
 * decide that the fast path can be used. If now an interrupt occurs before
 * the this_cpu_add(), and the interrupt updates this_cpu(*fbc->counters),
 * then the this_cpu_add() that is executed after the interrupt has completed
 * can produce values larger than "batch" or even overflows.
 */
#ifdef CONFIG_HAVE_CMPXCHG_LOCAL
/*
 * Safety against interrupts is achieved in 2 ways:
 * 1. the fast path uses local cmpxchg (note: no lock prefix)
 * 2. the slow path operates with interrupts disabled
 */
void percpu_counter_add_batch(struct percpu_counter *fbc, s64 amount, s32 batch)
{
	s64 count;
	unsigned long flags;

	count = this_cpu_read(*fbc->counters);
	do {
		if (unlikely(abs(count + amount) >= batch)) {
			raw_spin_lock_irqsave(&fbc->lock, flags);
			/*
			 * Note: by now we might have migrated to another CPU
			 * or the value might have changed.
			 */
			count = __this_cpu_read(*fbc->counters);
			fbc->count += count + amount;
			__this_cpu_sub(*fbc->counters, count);
			raw_spin_unlock_irqrestore(&fbc->lock, flags);
			return;
		}
	} while (!this_cpu_try_cmpxchg(*fbc->counters, &count, count + amount));
}
#else
/*
 * local_irq_save() is used to make the function irq safe:
 * - The slow path would be ok as protected by an irq-safe spinlock.
 * - this_cpu_add would be ok as it is irq-safe by definition.
 */
void percpu_counter_add_batch(struct percpu_counter *fbc, s64 amount, s32 batch)
{
	s64 count;
	unsigned long flags;

	local_irq_save(flags);
	count = __this_cpu_read(*fbc->counters) + amount;
	if (abs(count) >= batch) {
		raw_spin_lock(&fbc->lock);
		fbc->count += count;
		__this_cpu_sub(*fbc->counters, count - amount);
		raw_spin_unlock(&fbc->lock);
	} else {
		this_cpu_add(*fbc->counters, amount);
	}
	local_irq_restore(flags);
}
#endif
EXPORT_SYMBOL(percpu_counter_add_batch);

/*
 * For percpu_counter with a big batch, the devication of its count could
 * be big, and there is requirement to reduce the deviation, like when the
 * counter's batch could be runtime decreased to get a better accuracy,
 * which can be achieved by running this sync function on each CPU.
 */
void percpu_counter_sync(struct percpu_counter *fbc)
{
	unsigned long flags;
	s64 count;

	raw_spin_lock_irqsave(&fbc->lock, flags);
	count = __this_cpu_read(*fbc->counters);
	fbc->count += count;
	__this_cpu_sub(*fbc->counters, count);
	raw_spin_unlock_irqrestore(&fbc->lock, flags);
}
EXPORT_SYMBOL(percpu_counter_sync);

/*
 * Add up all the per-cpu counts, return the result.  This is a more accurate
 * but much slower version of percpu_counter_read_positive().
 *
 * We use the cpu mask of (cpu_online_mask | cpu_dying_mask) to capture sums
 * from CPUs that are in the process of being taken offline. Dying cpus have
 * been removed from the online mask, but may not have had the hotplug dead
 * notifier called to fold the percpu count back into the global counter sum.
 * By including dying CPUs in the iteration mask, we avoid this race condition
 * so __percpu_counter_sum() just does the right thing when CPUs are being taken
 * offline.
 */
s64 __percpu_counter_sum(struct percpu_counter *fbc)
{
	s64 ret;
	int cpu;
	unsigned long flags;

	raw_spin_lock_irqsave(&fbc->lock, flags);
	ret = fbc->count;
	for_each_cpu_or(cpu, cpu_online_mask, cpu_dying_mask) {
		s32 *pcount = per_cpu_ptr(fbc->counters, cpu);
		ret += *pcount;
	}
	raw_spin_unlock_irqrestore(&fbc->lock, flags);
	return ret;
}
EXPORT_SYMBOL(__percpu_counter_sum);

int __percpu_counter_init_many(struct percpu_counter *fbc, s64 amount,
			       gfp_t gfp, u32 nr_counters,
			       struct lock_class_key *key)
{
	unsigned long flags __maybe_unused;
	size_t counter_size;
	s32 __percpu *counters;
	u32 i;

	counter_size = ALIGN(sizeof(*counters), __alignof__(*counters));
	counters = __alloc_percpu_gfp(nr_counters * counter_size,
				      __alignof__(*counters), gfp);
	if (!counters) {
		fbc[0].counters = NULL;
		return -ENOMEM;
	}

	for (i = 0; i < nr_counters; i++) {
		raw_spin_lock_init(&fbc[i].lock);
		lockdep_set_class(&fbc[i].lock, key);
#ifdef CONFIG_HOTPLUG_CPU
		INIT_LIST_HEAD(&fbc[i].list);
#endif
		fbc[i].count = amount;
		fbc[i].counters = (void __percpu *)counters + i * counter_size;

		debug_percpu_counter_activate(&fbc[i]);
	}

#ifdef CONFIG_HOTPLUG_CPU
	spin_lock_irqsave(&percpu_counters_lock, flags);
	for (i = 0; i < nr_counters; i++)
		list_add(&fbc[i].list, &percpu_counters);
	spin_unlock_irqrestore(&percpu_counters_lock, flags);
#endif
	return 0;
}
EXPORT_SYMBOL(__percpu_counter_init_many);

void percpu_counter_destroy_many(struct percpu_counter *fbc, u32 nr_counters)
{
	unsigned long flags __maybe_unused;
	u32 i;

	if (WARN_ON_ONCE(!fbc))
		return;

	if (!fbc[0].counters)
		return;

	for (i = 0; i < nr_counters; i++)
		debug_percpu_counter_deactivate(&fbc[i]);

#ifdef CONFIG_HOTPLUG_CPU
	spin_lock_irqsave(&percpu_counters_lock, flags);
	for (i = 0; i < nr_counters; i++)
		list_del(&fbc[i].list);
	spin_unlock_irqrestore(&percpu_counters_lock, flags);
#endif

	free_percpu(fbc[0].counters);

	for (i = 0; i < nr_counters; i++)
		fbc[i].counters = NULL;
}
EXPORT_SYMBOL(percpu_counter_destroy_many);

int percpu_counter_batch __read_mostly = 32;
EXPORT_SYMBOL(percpu_counter_batch);

static int compute_batch_value(unsigned int cpu)
{
	int nr = num_online_cpus();

	percpu_counter_batch = max(32, nr*2);
	return 0;
}

static int percpu_counter_cpu_dead(unsigned int cpu)
{
#ifdef CONFIG_HOTPLUG_CPU
	struct percpu_counter *fbc;

	compute_batch_value(cpu);

	spin_lock_irq(&percpu_counters_lock);
	list_for_each_entry(fbc, &percpu_counters, list) {
		s32 *pcount;

		raw_spin_lock(&fbc->lock);
		pcount = per_cpu_ptr(fbc->counters, cpu);
		fbc->count += *pcount;
		*pcount = 0;
		raw_spin_unlock(&fbc->lock);
	}
	spin_unlock_irq(&percpu_counters_lock);
#endif
	return 0;
}

/*
 * Compare counter against given value.
 * Return 1 if greater, 0 if equal and -1 if less
 */
int __percpu_counter_compare(struct percpu_counter *fbc, s64 rhs, s32 batch)
{
	s64	count;

	count = percpu_counter_read(fbc);
	/* Check to see if rough count will be sufficient for comparison */
	if (abs(count - rhs) > (batch * num_online_cpus())) {
		if (count > rhs)
			return 1;
		else
			return -1;
	}
	/* Need to use precise count */
	count = percpu_counter_sum(fbc);
	if (count > rhs)
		return 1;
	else if (count < rhs)
		return -1;
	else
		return 0;
}
EXPORT_SYMBOL(__percpu_counter_compare);

/*
 * Compare counter, and add amount if total is: less than or equal to limit if
 * amount is positive, or greater than or equal to limit if amount is negative.
 * Return true if amount is added, or false if total would be beyond the limit.
 *
 * Negative limit is allowed, but unusual.
 * When negative amounts (subs) are given to percpu_counter_limited_add(),
 * the limit would most naturally be 0 - but other limits are also allowed.
 *
 * Overflow beyond S64_MAX is not allowed for: counter, limit and amount
 * are all assumed to be sane (far from S64_MIN and S64_MAX).
 */
bool __percpu_counter_limited_add(struct percpu_counter *fbc,
				  s64 limit, s64 amount, s32 batch)
{
	s64 count;
	s64 unknown;
	unsigned long flags;
	bool good = false;

	if (amount == 0)
		return true;

	local_irq_save(flags);
	unknown = batch * num_online_cpus();
	count = __this_cpu_read(*fbc->counters);

	/* Skip taking the lock when safe */
	if (abs(count + amount) <= batch &&
	    ((amount > 0 && fbc->count + unknown <= limit) ||
	     (amount < 0 && fbc->count - unknown >= limit))) {
		this_cpu_add(*fbc->counters, amount);
		local_irq_restore(flags);
		return true;
	}

	raw_spin_lock(&fbc->lock);
	count = fbc->count + amount;

	/* Skip percpu_counter_sum() when safe */
	if (amount > 0) {
		if (count - unknown > limit)
			goto out;
		if (count + unknown <= limit)
			good = true;
	} else {
		if (count + unknown < limit)
			goto out;
		if (count - unknown >= limit)
			good = true;
	}

	if (!good) {
		s32 *pcount;
		int cpu;

		for_each_cpu_or(cpu, cpu_online_mask, cpu_dying_mask) {
			pcount = per_cpu_ptr(fbc->counters, cpu);
			count += *pcount;
		}
		if (amount > 0) {
			if (count > limit)
				goto out;
		} else {
			if (count < limit)
				goto out;
		}
		good = true;
	}

	count = __this_cpu_read(*fbc->counters);
	fbc->count += count + amount;
	__this_cpu_sub(*fbc->counters, count);
out:
	raw_spin_unlock(&fbc->lock);
	local_irq_restore(flags);
	return good;
}

static int __init percpu_counter_startup(void)
{
	int ret;

	ret = cpuhp_setup_state(CPUHP_AP_ONLINE_DYN, "lib/percpu_cnt:online",
				compute_batch_value, NULL);
	WARN_ON(ret < 0);
	ret = cpuhp_setup_state_nocalls(CPUHP_PERCPU_CNT_DEAD,
					"lib/percpu_cnt:dead", NULL,
					percpu_counter_cpu_dead);
	WARN_ON(ret < 0);
	return 0;
}
module_init(percpu_counter_startup);