Commit | Line | Data |
---|---|---|
6ee159e2 ZK |
1 | /* |
2 | * Copyright (c) 2012 Neratec Solutions AG | |
3 | * | |
4 | * Permission to use, copy, modify, and/or distribute this software for any | |
5 | * purpose with or without fee is hereby granted, provided that the above | |
6 | * copyright notice and this permission notice appear in all copies. | |
7 | * | |
8 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |
9 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |
10 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |
11 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |
12 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |
13 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |
14 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |
15 | */ | |
16 | ||
17 | #include <linux/slab.h> | |
78241bdc | 18 | #include <linux/spinlock.h> |
6ee159e2 | 19 | |
ad40d3da | 20 | #include "ath.h" |
6ee159e2 ZK |
21 | #include "dfs_pattern_detector.h" |
22 | #include "dfs_pri_detector.h" | |
d265214b JD |
23 | |
24 | struct ath_dfs_pool_stats global_dfs_pool_stats = {}; | |
25 | ||
26 | #define DFS_POOL_STAT_INC(c) (global_dfs_pool_stats.c++) | |
27 | #define DFS_POOL_STAT_DEC(c) (global_dfs_pool_stats.c--) | |
44acedb0 PO |
28 | #define GET_PRI_TO_USE(MIN, MAX, RUNTIME) \ |
29 | (MIN + PRI_TOLERANCE == MAX - PRI_TOLERANCE ? \ | |
30 | MIN + PRI_TOLERANCE : RUNTIME) | |
6ee159e2 | 31 | |
6ee159e2 ZK |
32 | /** |
33 | * struct pulse_elem - elements in pulse queue | |
34 | * @ts: time stamp in usecs | |
35 | */ | |
36 | struct pulse_elem { | |
37 | struct list_head head; | |
38 | u64 ts; | |
39 | }; | |
40 | ||
41 | /** | |
42 | * pde_get_multiple() - get number of multiples considering a given tolerance | |
43 | * @return factor if abs(val - factor*fraction) <= tolerance, 0 otherwise | |
44 | */ | |
45 | static u32 pde_get_multiple(u32 val, u32 fraction, u32 tolerance) | |
46 | { | |
47 | u32 remainder; | |
48 | u32 factor; | |
49 | u32 delta; | |
50 | ||
51 | if (fraction == 0) | |
52 | return 0; | |
53 | ||
54 | delta = (val < fraction) ? (fraction - val) : (val - fraction); | |
55 | ||
56 | if (delta <= tolerance) | |
57 | /* val and fraction are within tolerance */ | |
58 | return 1; | |
59 | ||
60 | factor = val / fraction; | |
61 | remainder = val % fraction; | |
62 | if (remainder > tolerance) { | |
63 | /* no exact match */ | |
64 | if ((fraction - remainder) <= tolerance) | |
65 | /* remainder is within tolerance */ | |
66 | factor++; | |
67 | else | |
68 | factor = 0; | |
69 | } | |
70 | return factor; | |
71 | } | |
72 | ||
73 | /** | |
74 | * DOC: Singleton Pulse and Sequence Pools | |
75 | * | |
76 | * Instances of pri_sequence and pulse_elem are kept in singleton pools to | |
77 | * reduce the number of dynamic allocations. They are shared between all | |
78 | * instances and grow up to the peak number of simultaneously used objects. | |
79 | * | |
80 | * Memory is freed after all references to the pools are released. | |
81 | */ | |
82 | static u32 singleton_pool_references; | |
83 | static LIST_HEAD(pulse_pool); | |
84 | static LIST_HEAD(pseq_pool); | |
78241bdc ZK |
85 | static DEFINE_SPINLOCK(pool_lock); |
86 | ||
87 | static void pool_register_ref(void) | |
88 | { | |
89 | spin_lock_bh(&pool_lock); | |
90 | singleton_pool_references++; | |
b96f20b3 | 91 | DFS_POOL_STAT_INC(pool_reference); |
78241bdc ZK |
92 | spin_unlock_bh(&pool_lock); |
93 | } | |
94 | ||
95 | static void pool_deregister_ref(void) | |
96 | { | |
97 | spin_lock_bh(&pool_lock); | |
98 | singleton_pool_references--; | |
b96f20b3 | 99 | DFS_POOL_STAT_DEC(pool_reference); |
78241bdc ZK |
100 | if (singleton_pool_references == 0) { |
101 | /* free singleton pools with no references left */ | |
102 | struct pri_sequence *ps, *ps0; | |
103 | struct pulse_elem *p, *p0; | |
104 | ||
105 | list_for_each_entry_safe(p, p0, &pulse_pool, head) { | |
106 | list_del(&p->head); | |
b96f20b3 | 107 | DFS_POOL_STAT_DEC(pulse_allocated); |
78241bdc ZK |
108 | kfree(p); |
109 | } | |
110 | list_for_each_entry_safe(ps, ps0, &pseq_pool, head) { | |
111 | list_del(&ps->head); | |
b96f20b3 | 112 | DFS_POOL_STAT_DEC(pseq_allocated); |
78241bdc ZK |
113 | kfree(ps); |
114 | } | |
115 | } | |
116 | spin_unlock_bh(&pool_lock); | |
117 | } | |
118 | ||
119 | static void pool_put_pulse_elem(struct pulse_elem *pe) | |
120 | { | |
121 | spin_lock_bh(&pool_lock); | |
122 | list_add(&pe->head, &pulse_pool); | |
b96f20b3 | 123 | DFS_POOL_STAT_DEC(pulse_used); |
78241bdc ZK |
124 | spin_unlock_bh(&pool_lock); |
125 | } | |
126 | ||
127 | static void pool_put_pseq_elem(struct pri_sequence *pse) | |
128 | { | |
129 | spin_lock_bh(&pool_lock); | |
130 | list_add(&pse->head, &pseq_pool); | |
b96f20b3 | 131 | DFS_POOL_STAT_DEC(pseq_used); |
78241bdc ZK |
132 | spin_unlock_bh(&pool_lock); |
133 | } | |
134 | ||
135 | static struct pri_sequence *pool_get_pseq_elem(void) | |
136 | { | |
137 | struct pri_sequence *pse = NULL; | |
138 | spin_lock_bh(&pool_lock); | |
139 | if (!list_empty(&pseq_pool)) { | |
140 | pse = list_first_entry(&pseq_pool, struct pri_sequence, head); | |
141 | list_del(&pse->head); | |
b96f20b3 | 142 | DFS_POOL_STAT_INC(pseq_used); |
78241bdc ZK |
143 | } |
144 | spin_unlock_bh(&pool_lock); | |
145 | return pse; | |
146 | } | |
147 | ||
148 | static struct pulse_elem *pool_get_pulse_elem(void) | |
149 | { | |
150 | struct pulse_elem *pe = NULL; | |
151 | spin_lock_bh(&pool_lock); | |
152 | if (!list_empty(&pulse_pool)) { | |
153 | pe = list_first_entry(&pulse_pool, struct pulse_elem, head); | |
154 | list_del(&pe->head); | |
b96f20b3 | 155 | DFS_POOL_STAT_INC(pulse_used); |
78241bdc ZK |
156 | } |
157 | spin_unlock_bh(&pool_lock); | |
158 | return pe; | |
159 | } | |
6ee159e2 ZK |
160 | |
161 | static struct pulse_elem *pulse_queue_get_tail(struct pri_detector *pde) | |
162 | { | |
163 | struct list_head *l = &pde->pulses; | |
164 | if (list_empty(l)) | |
165 | return NULL; | |
166 | return list_entry(l->prev, struct pulse_elem, head); | |
167 | } | |
168 | ||
169 | static bool pulse_queue_dequeue(struct pri_detector *pde) | |
170 | { | |
171 | struct pulse_elem *p = pulse_queue_get_tail(pde); | |
172 | if (p != NULL) { | |
173 | list_del_init(&p->head); | |
174 | pde->count--; | |
175 | /* give it back to pool */ | |
78241bdc | 176 | pool_put_pulse_elem(p); |
6ee159e2 ZK |
177 | } |
178 | return (pde->count > 0); | |
179 | } | |
180 | ||
181 | /* remove pulses older than window */ | |
182 | static void pulse_queue_check_window(struct pri_detector *pde) | |
183 | { | |
184 | u64 min_valid_ts; | |
185 | struct pulse_elem *p; | |
186 | ||
187 | /* there is no delta time with less than 2 pulses */ | |
188 | if (pde->count < 2) | |
189 | return; | |
190 | ||
191 | if (pde->last_ts <= pde->window_size) | |
192 | return; | |
193 | ||
194 | min_valid_ts = pde->last_ts - pde->window_size; | |
195 | while ((p = pulse_queue_get_tail(pde)) != NULL) { | |
196 | if (p->ts >= min_valid_ts) | |
197 | return; | |
198 | pulse_queue_dequeue(pde); | |
199 | } | |
200 | } | |
201 | ||
202 | static bool pulse_queue_enqueue(struct pri_detector *pde, u64 ts) | |
203 | { | |
78241bdc ZK |
204 | struct pulse_elem *p = pool_get_pulse_elem(); |
205 | if (p == NULL) { | |
5d8cd3b1 | 206 | p = kmalloc(sizeof(*p), GFP_ATOMIC); |
6ee159e2 | 207 | if (p == NULL) { |
b96f20b3 | 208 | DFS_POOL_STAT_INC(pulse_alloc_error); |
6ee159e2 ZK |
209 | return false; |
210 | } | |
b96f20b3 ZK |
211 | DFS_POOL_STAT_INC(pulse_allocated); |
212 | DFS_POOL_STAT_INC(pulse_used); | |
6ee159e2 ZK |
213 | } |
214 | INIT_LIST_HEAD(&p->head); | |
215 | p->ts = ts; | |
216 | list_add(&p->head, &pde->pulses); | |
217 | pde->count++; | |
218 | pde->last_ts = ts; | |
219 | pulse_queue_check_window(pde); | |
220 | if (pde->count >= pde->max_count) | |
221 | pulse_queue_dequeue(pde); | |
222 | return true; | |
223 | } | |
224 | ||
225 | static bool pseq_handler_create_sequences(struct pri_detector *pde, | |
226 | u64 ts, u32 min_count) | |
227 | { | |
228 | struct pulse_elem *p; | |
229 | list_for_each_entry(p, &pde->pulses, head) { | |
230 | struct pri_sequence ps, *new_ps; | |
231 | struct pulse_elem *p2; | |
232 | u32 tmp_false_count; | |
233 | u64 min_valid_ts; | |
234 | u32 delta_ts = ts - p->ts; | |
235 | ||
236 | if (delta_ts < pde->rs->pri_min) | |
237 | /* ignore too small pri */ | |
238 | continue; | |
239 | ||
240 | if (delta_ts > pde->rs->pri_max) | |
241 | /* stop on too large pri (sorted list) */ | |
242 | break; | |
243 | ||
244 | /* build a new sequence with new potential pri */ | |
245 | ps.count = 2; | |
246 | ps.count_falses = 0; | |
247 | ps.first_ts = p->ts; | |
248 | ps.last_ts = ts; | |
44acedb0 PO |
249 | ps.pri = GET_PRI_TO_USE(pde->rs->pri_min, |
250 | pde->rs->pri_max, ts - p->ts); | |
6ee159e2 ZK |
251 | ps.dur = ps.pri * (pde->rs->ppb - 1) |
252 | + 2 * pde->rs->max_pri_tolerance; | |
253 | ||
254 | p2 = p; | |
255 | tmp_false_count = 0; | |
256 | min_valid_ts = ts - ps.dur; | |
257 | /* check which past pulses are candidates for new sequence */ | |
258 | list_for_each_entry_continue(p2, &pde->pulses, head) { | |
259 | u32 factor; | |
260 | if (p2->ts < min_valid_ts) | |
261 | /* stop on crossing window border */ | |
262 | break; | |
263 | /* check if pulse match (multi)PRI */ | |
264 | factor = pde_get_multiple(ps.last_ts - p2->ts, ps.pri, | |
265 | pde->rs->max_pri_tolerance); | |
266 | if (factor > 0) { | |
267 | ps.count++; | |
268 | ps.first_ts = p2->ts; | |
269 | /* | |
270 | * on match, add the intermediate falses | |
271 | * and reset counter | |
272 | */ | |
273 | ps.count_falses += tmp_false_count; | |
274 | tmp_false_count = 0; | |
275 | } else { | |
276 | /* this is a potential false one */ | |
277 | tmp_false_count++; | |
278 | } | |
279 | } | |
b24fc6fc | 280 | if (ps.count <= min_count) |
6ee159e2 ZK |
281 | /* did not reach minimum count, drop sequence */ |
282 | continue; | |
283 | ||
284 | /* this is a valid one, add it */ | |
285 | ps.deadline_ts = ps.first_ts + ps.dur; | |
78241bdc ZK |
286 | new_ps = pool_get_pseq_elem(); |
287 | if (new_ps == NULL) { | |
5d8cd3b1 | 288 | new_ps = kmalloc(sizeof(*new_ps), GFP_ATOMIC); |
b96f20b3 ZK |
289 | if (new_ps == NULL) { |
290 | DFS_POOL_STAT_INC(pseq_alloc_error); | |
6ee159e2 | 291 | return false; |
b96f20b3 ZK |
292 | } |
293 | DFS_POOL_STAT_INC(pseq_allocated); | |
294 | DFS_POOL_STAT_INC(pseq_used); | |
6ee159e2 ZK |
295 | } |
296 | memcpy(new_ps, &ps, sizeof(ps)); | |
297 | INIT_LIST_HEAD(&new_ps->head); | |
298 | list_add(&new_ps->head, &pde->sequences); | |
299 | } | |
300 | return true; | |
301 | } | |
302 | ||
303 | /* check new ts and add to all matching existing sequences */ | |
304 | static u32 | |
305 | pseq_handler_add_to_existing_seqs(struct pri_detector *pde, u64 ts) | |
306 | { | |
307 | u32 max_count = 0; | |
308 | struct pri_sequence *ps, *ps2; | |
309 | list_for_each_entry_safe(ps, ps2, &pde->sequences, head) { | |
310 | u32 delta_ts; | |
311 | u32 factor; | |
312 | ||
313 | /* first ensure that sequence is within window */ | |
314 | if (ts > ps->deadline_ts) { | |
315 | list_del_init(&ps->head); | |
78241bdc | 316 | pool_put_pseq_elem(ps); |
6ee159e2 ZK |
317 | continue; |
318 | } | |
319 | ||
320 | delta_ts = ts - ps->last_ts; | |
321 | factor = pde_get_multiple(delta_ts, ps->pri, | |
322 | pde->rs->max_pri_tolerance); | |
323 | if (factor > 0) { | |
324 | ps->last_ts = ts; | |
325 | ps->count++; | |
326 | ||
327 | if (max_count < ps->count) | |
328 | max_count = ps->count; | |
329 | } else { | |
330 | ps->count_falses++; | |
331 | } | |
332 | } | |
333 | return max_count; | |
334 | } | |
335 | ||
336 | static struct pri_sequence * | |
337 | pseq_handler_check_detection(struct pri_detector *pde) | |
338 | { | |
339 | struct pri_sequence *ps; | |
340 | ||
341 | if (list_empty(&pde->sequences)) | |
342 | return NULL; | |
343 | ||
344 | list_for_each_entry(ps, &pde->sequences, head) { | |
345 | /* | |
346 | * we assume to have enough matching confidence if we | |
347 | * 1) have enough pulses | |
348 | * 2) have more matching than false pulses | |
349 | */ | |
350 | if ((ps->count >= pde->rs->ppb_thresh) && | |
351 | (ps->count * pde->rs->num_pri >= ps->count_falses)) | |
352 | return ps; | |
353 | } | |
354 | return NULL; | |
355 | } | |
356 | ||
357 | ||
358 | /* free pulse queue and sequences list and give objects back to pools */ | |
359 | static void pri_detector_reset(struct pri_detector *pde, u64 ts) | |
360 | { | |
361 | struct pri_sequence *ps, *ps0; | |
362 | struct pulse_elem *p, *p0; | |
363 | list_for_each_entry_safe(ps, ps0, &pde->sequences, head) { | |
364 | list_del_init(&ps->head); | |
78241bdc | 365 | pool_put_pseq_elem(ps); |
6ee159e2 ZK |
366 | } |
367 | list_for_each_entry_safe(p, p0, &pde->pulses, head) { | |
368 | list_del_init(&p->head); | |
78241bdc | 369 | pool_put_pulse_elem(p); |
6ee159e2 ZK |
370 | } |
371 | pde->count = 0; | |
372 | pde->last_ts = ts; | |
373 | } | |
374 | ||
375 | static void pri_detector_exit(struct pri_detector *de) | |
376 | { | |
377 | pri_detector_reset(de, 0); | |
78241bdc | 378 | pool_deregister_ref(); |
6ee159e2 ZK |
379 | kfree(de); |
380 | } | |
381 | ||
ca21cfde ZK |
382 | static struct pri_sequence *pri_detector_add_pulse(struct pri_detector *de, |
383 | struct pulse_event *event) | |
6ee159e2 ZK |
384 | { |
385 | u32 max_updated_seq; | |
386 | struct pri_sequence *ps; | |
387 | u64 ts = event->ts; | |
388 | const struct radar_detector_specs *rs = de->rs; | |
389 | ||
390 | /* ignore pulses not within width range */ | |
391 | if ((rs->width_min > event->width) || (rs->width_max < event->width)) | |
ca21cfde | 392 | return NULL; |
6ee159e2 ZK |
393 | |
394 | if ((ts - de->last_ts) < rs->max_pri_tolerance) | |
395 | /* if delta to last pulse is too short, don't use this pulse */ | |
ca21cfde | 396 | return NULL; |
dab74cde PO |
397 | /* radar detector spec needs chirp, but not detected */ |
398 | if (rs->chirp && rs->chirp != event->chirp) | |
399 | return NULL; | |
400 | ||
6ee159e2 ZK |
401 | de->last_ts = ts; |
402 | ||
403 | max_updated_seq = pseq_handler_add_to_existing_seqs(de, ts); | |
404 | ||
405 | if (!pseq_handler_create_sequences(de, ts, max_updated_seq)) { | |
6ee159e2 | 406 | pri_detector_reset(de, ts); |
5bb4101b | 407 | return NULL; |
6ee159e2 ZK |
408 | } |
409 | ||
410 | ps = pseq_handler_check_detection(de); | |
411 | ||
ca21cfde ZK |
412 | if (ps == NULL) |
413 | pulse_queue_enqueue(de, ts); | |
414 | ||
415 | return ps; | |
6ee159e2 ZK |
416 | } |
417 | ||
ca21cfde | 418 | struct pri_detector *pri_detector_init(const struct radar_detector_specs *rs) |
6ee159e2 ZK |
419 | { |
420 | struct pri_detector *de; | |
703a4e55 DC |
421 | |
422 | de = kzalloc(sizeof(*de), GFP_ATOMIC); | |
6ee159e2 ZK |
423 | if (de == NULL) |
424 | return NULL; | |
425 | de->exit = pri_detector_exit; | |
426 | de->add_pulse = pri_detector_add_pulse; | |
427 | de->reset = pri_detector_reset; | |
428 | ||
429 | INIT_LIST_HEAD(&de->sequences); | |
430 | INIT_LIST_HEAD(&de->pulses); | |
431 | de->window_size = rs->pri_max * rs->ppb * rs->num_pri; | |
432 | de->max_count = rs->ppb * 2; | |
433 | de->rs = rs; | |
434 | ||
78241bdc | 435 | pool_register_ref(); |
6ee159e2 ZK |
436 | return de; |
437 | } |