1#ifndef __PERCPU_IDA_H__
2#define __PERCPU_IDA_H__
3
4#include <linux/types.h>
5#include <linux/bitops.h>
6#include <linux/init.h>
7#include <linux/sched.h>
8#include <linux/spinlock_types.h>
9#include <linux/wait.h>
10#include <linux/cpumask.h>
11
12struct percpu_ida_cpu;
13
14struct percpu_ida {
15	/*
16	 * number of tags available to be allocated, as passed to
17	 * percpu_ida_init()
18	 */
19	unsigned			nr_tags;
20	unsigned			percpu_max_size;
21	unsigned			percpu_batch_size;
22
23	struct percpu_ida_cpu __percpu	*tag_cpu;
24
25	/*
26	 * Bitmap of cpus that (may) have tags on their percpu freelists:
27	 * steal_tags() uses this to decide when to steal tags, and which cpus
28	 * to try stealing from.
29	 *
30	 * It's ok for a freelist to be empty when its bit is set - steal_tags()
31	 * will just keep looking - but the bitmap _must_ be set whenever a
32	 * percpu freelist does have tags.
33	 */
34	cpumask_t			cpus_have_tags;
35
36	struct {
37		spinlock_t		lock;
38		/*
39		 * When we go to steal tags from another cpu (see steal_tags()),
40		 * we want to pick a cpu at random. Cycling through them every
41		 * time we steal is a bit easier and more or less equivalent:
42		 */
43		unsigned		cpu_last_stolen;
44
45		/* For sleeping on allocation failure */
46		wait_queue_head_t	wait;
47
48		/*
49		 * Global freelist - it's a stack where nr_free points to the
50		 * top
51		 */
52		unsigned		nr_free;
53		unsigned		*freelist;
54	} ____cacheline_aligned_in_smp;
55};
56
57/*
58 * Number of tags we move between the percpu freelist and the global freelist at
59 * a time
60 */
61#define IDA_DEFAULT_PCPU_BATCH_MOVE	32U
62/* Max size of percpu freelist, */
63#define IDA_DEFAULT_PCPU_SIZE	((IDA_DEFAULT_PCPU_BATCH_MOVE * 3) / 2)
64
65int percpu_ida_alloc(struct percpu_ida *pool, int state);
66void percpu_ida_free(struct percpu_ida *pool, unsigned tag);
67
68void percpu_ida_destroy(struct percpu_ida *pool);
69int __percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags,
70	unsigned long max_size, unsigned long batch_size);
71static inline int percpu_ida_init(struct percpu_ida *pool, unsigned long nr_tags)
72{
73	return __percpu_ida_init(pool, nr_tags, IDA_DEFAULT_PCPU_SIZE,
74		IDA_DEFAULT_PCPU_BATCH_MOVE);
75}
76
77typedef int (*percpu_ida_cb)(unsigned, void *);
78int percpu_ida_for_each_free(struct percpu_ida *pool, percpu_ida_cb fn,
79	void *data);
80
81unsigned percpu_ida_free_tags(struct percpu_ida *pool, int cpu);
82#endif /* __PERCPU_IDA_H__ */
83