1
2
3
4#include <linux/jhash.h>
5#include <linux/slab.h>
6#include <linux/xarray.h>
7#include <linux/hashtable.h>
8
9#include "mapping.h"
10
11#define MAPPING_GRACE_PERIOD 2000
12
13struct mapping_ctx {
14 struct xarray xarray;
15 DECLARE_HASHTABLE(ht, 8);
16 struct mutex lock;
17 unsigned long max_id;
18 size_t data_size;
19 bool delayed_removal;
20 struct delayed_work dwork;
21 struct list_head pending_list;
22 spinlock_t pending_list_lock;
23};
24
25struct mapping_item {
26 struct rcu_head rcu;
27 struct list_head list;
28 unsigned long timeout;
29 struct hlist_node node;
30 int cnt;
31 u32 id;
32 char data[];
33};
34
35int mapping_add(struct mapping_ctx *ctx, void *data, u32 *id)
36{
37 struct mapping_item *mi;
38 int err = -ENOMEM;
39 u32 hash_key;
40
41 mutex_lock(&ctx->lock);
42
43 hash_key = jhash(data, ctx->data_size, 0);
44 hash_for_each_possible(ctx->ht, mi, node, hash_key) {
45 if (!memcmp(data, mi->data, ctx->data_size))
46 goto attach;
47 }
48
49 mi = kzalloc(sizeof(*mi) + ctx->data_size, GFP_KERNEL);
50 if (!mi)
51 goto err_alloc;
52
53 memcpy(mi->data, data, ctx->data_size);
54 hash_add(ctx->ht, &mi->node, hash_key);
55
56 err = xa_alloc(&ctx->xarray, &mi->id, mi, XA_LIMIT(1, ctx->max_id),
57 GFP_KERNEL);
58 if (err)
59 goto err_assign;
60attach:
61 ++mi->cnt;
62 *id = mi->id;
63
64 mutex_unlock(&ctx->lock);
65
66 return 0;
67
68err_assign:
69 hash_del(&mi->node);
70 kfree(mi);
71err_alloc:
72 mutex_unlock(&ctx->lock);
73
74 return err;
75}
76
77static void mapping_remove_and_free(struct mapping_ctx *ctx,
78 struct mapping_item *mi)
79{
80 xa_erase(&ctx->xarray, mi->id);
81 kfree_rcu(mi, rcu);
82}
83
84static void mapping_free_item(struct mapping_ctx *ctx,
85 struct mapping_item *mi)
86{
87 if (!ctx->delayed_removal) {
88 mapping_remove_and_free(ctx, mi);
89 return;
90 }
91
92 mi->timeout = jiffies + msecs_to_jiffies(MAPPING_GRACE_PERIOD);
93
94 spin_lock(&ctx->pending_list_lock);
95 list_add_tail(&mi->list, &ctx->pending_list);
96 spin_unlock(&ctx->pending_list_lock);
97
98 schedule_delayed_work(&ctx->dwork, MAPPING_GRACE_PERIOD);
99}
100
101int mapping_remove(struct mapping_ctx *ctx, u32 id)
102{
103 unsigned long index = id;
104 struct mapping_item *mi;
105 int err = -ENOENT;
106
107 mutex_lock(&ctx->lock);
108 mi = xa_load(&ctx->xarray, index);
109 if (!mi)
110 goto out;
111 err = 0;
112
113 if (--mi->cnt > 0)
114 goto out;
115
116 hash_del(&mi->node);
117 mapping_free_item(ctx, mi);
118out:
119 mutex_unlock(&ctx->lock);
120
121 return err;
122}
123
124int mapping_find(struct mapping_ctx *ctx, u32 id, void *data)
125{
126 unsigned long index = id;
127 struct mapping_item *mi;
128 int err = -ENOENT;
129
130 rcu_read_lock();
131 mi = xa_load(&ctx->xarray, index);
132 if (!mi)
133 goto err_find;
134
135 memcpy(data, mi->data, ctx->data_size);
136 err = 0;
137
138err_find:
139 rcu_read_unlock();
140 return err;
141}
142
143static void
144mapping_remove_and_free_list(struct mapping_ctx *ctx, struct list_head *list)
145{
146 struct mapping_item *mi;
147
148 list_for_each_entry(mi, list, list)
149 mapping_remove_and_free(ctx, mi);
150}
151
152static void mapping_work_handler(struct work_struct *work)
153{
154 unsigned long min_timeout = 0, now = jiffies;
155 struct mapping_item *mi, *next;
156 LIST_HEAD(pending_items);
157 struct mapping_ctx *ctx;
158
159 ctx = container_of(work, struct mapping_ctx, dwork.work);
160
161 spin_lock(&ctx->pending_list_lock);
162 list_for_each_entry_safe(mi, next, &ctx->pending_list, list) {
163 if (time_after(now, mi->timeout))
164 list_move(&mi->list, &pending_items);
165 else if (!min_timeout ||
166 time_before(mi->timeout, min_timeout))
167 min_timeout = mi->timeout;
168 }
169 spin_unlock(&ctx->pending_list_lock);
170
171 mapping_remove_and_free_list(ctx, &pending_items);
172
173 if (min_timeout)
174 schedule_delayed_work(&ctx->dwork, abs(min_timeout - now));
175}
176
177static void mapping_flush_work(struct mapping_ctx *ctx)
178{
179 if (!ctx->delayed_removal)
180 return;
181
182 cancel_delayed_work_sync(&ctx->dwork);
183 mapping_remove_and_free_list(ctx, &ctx->pending_list);
184}
185
186struct mapping_ctx *
187mapping_create(size_t data_size, u32 max_id, bool delayed_removal)
188{
189 struct mapping_ctx *ctx;
190
191 ctx = kzalloc(sizeof(*ctx), GFP_KERNEL);
192 if (!ctx)
193 return ERR_PTR(-ENOMEM);
194
195 ctx->max_id = max_id ? max_id : UINT_MAX;
196 ctx->data_size = data_size;
197
198 if (delayed_removal) {
199 INIT_DELAYED_WORK(&ctx->dwork, mapping_work_handler);
200 INIT_LIST_HEAD(&ctx->pending_list);
201 spin_lock_init(&ctx->pending_list_lock);
202 ctx->delayed_removal = true;
203 }
204
205 mutex_init(&ctx->lock);
206 xa_init_flags(&ctx->xarray, XA_FLAGS_ALLOC1);
207
208 return ctx;
209}
210
211void mapping_destroy(struct mapping_ctx *ctx)
212{
213 mapping_flush_work(ctx);
214 xa_destroy(&ctx->xarray);
215 mutex_destroy(&ctx->lock);
216
217 kfree(ctx);
218}
219
