Branch data Line data Source code
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>
18 : : #include <linux/spinlock.h>
19 : :
20 : : #include "ath.h"
21 : : #include "dfs_pattern_detector.h"
22 : : #include "dfs_pri_detector.h"
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--)
28 : : #define GET_PRI_TO_USE(MIN, MAX, RUNTIME) \
29 : : (MIN + PRI_TOLERANCE == MAX - PRI_TOLERANCE ? \
30 : : MIN + PRI_TOLERANCE : RUNTIME)
31 : :
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 : 0 : static u32 pde_get_multiple(u32 val, u32 fraction, u32 tolerance)
46 : : {
47 : 0 : u32 remainder;
48 : 0 : u32 factor;
49 : 0 : u32 delta;
50 : :
51 : 0 : if (fraction == 0)
52 : : return 0;
53 : :
54 [ # # # # ]: 0 : delta = (val < fraction) ? (fraction - val) : (val - fraction);
55 : :
56 [ # # # # ]: 0 : if (delta <= tolerance)
57 : : /* val and fraction are within tolerance */
58 : : return 1;
59 : :
60 : 0 : factor = val / fraction;
61 : 0 : remainder = val % fraction;
62 [ # # # # ]: 0 : if (remainder > tolerance) {
63 : : /* no exact match */
64 [ # # # # ]: 0 : if ((fraction - remainder) <= tolerance)
65 : : /* remainder is within tolerance */
66 : 0 : 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);
85 : : static DEFINE_SPINLOCK(pool_lock);
86 : :
87 : 0 : static void pool_register_ref(void)
88 : : {
89 : 0 : spin_lock_bh(&pool_lock);
90 : 0 : singleton_pool_references++;
91 : 0 : DFS_POOL_STAT_INC(pool_reference);
92 : 0 : spin_unlock_bh(&pool_lock);
93 : 0 : }
94 : :
95 : 0 : static void pool_deregister_ref(void)
96 : : {
97 : 0 : spin_lock_bh(&pool_lock);
98 : 0 : singleton_pool_references--;
99 : 0 : DFS_POOL_STAT_DEC(pool_reference);
100 [ # # ]: 0 : if (singleton_pool_references == 0) {
101 : : /* free singleton pools with no references left */
102 : 0 : struct pri_sequence *ps, *ps0;
103 : 0 : struct pulse_elem *p, *p0;
104 : :
105 [ # # ]: 0 : list_for_each_entry_safe(p, p0, &pulse_pool, head) {
106 : 0 : list_del(&p->head);
107 : 0 : DFS_POOL_STAT_DEC(pulse_allocated);
108 : 0 : kfree(p);
109 : : }
110 [ # # ]: 0 : list_for_each_entry_safe(ps, ps0, &pseq_pool, head) {
111 : 0 : list_del(&ps->head);
112 : 0 : DFS_POOL_STAT_DEC(pseq_allocated);
113 : 0 : kfree(ps);
114 : : }
115 : : }
116 : 0 : spin_unlock_bh(&pool_lock);
117 : 0 : }
118 : :
119 : 0 : static void pool_put_pulse_elem(struct pulse_elem *pe)
120 : : {
121 : 0 : spin_lock_bh(&pool_lock);
122 : 0 : list_add(&pe->head, &pulse_pool);
123 : 0 : DFS_POOL_STAT_DEC(pulse_used);
124 : 0 : spin_unlock_bh(&pool_lock);
125 : 0 : }
126 : :
127 : 0 : static void pool_put_pseq_elem(struct pri_sequence *pse)
128 : : {
129 : 0 : spin_lock_bh(&pool_lock);
130 : 0 : list_add(&pse->head, &pseq_pool);
131 : 0 : DFS_POOL_STAT_DEC(pseq_used);
132 : 0 : spin_unlock_bh(&pool_lock);
133 : 0 : }
134 : :
135 : 0 : static struct pri_sequence *pool_get_pseq_elem(void)
136 : : {
137 : 0 : struct pri_sequence *pse = NULL;
138 : 0 : spin_lock_bh(&pool_lock);
139 [ # # ]: 0 : if (!list_empty(&pseq_pool)) {
140 : 0 : pse = list_first_entry(&pseq_pool, struct pri_sequence, head);
141 : 0 : list_del(&pse->head);
142 : 0 : DFS_POOL_STAT_INC(pseq_used);
143 : : }
144 : 0 : spin_unlock_bh(&pool_lock);
145 : 0 : return pse;
146 : : }
147 : :
148 : 0 : static struct pulse_elem *pool_get_pulse_elem(void)
149 : : {
150 : 0 : struct pulse_elem *pe = NULL;
151 : 0 : spin_lock_bh(&pool_lock);
152 [ # # ]: 0 : if (!list_empty(&pulse_pool)) {
153 : 0 : pe = list_first_entry(&pulse_pool, struct pulse_elem, head);
154 : 0 : list_del(&pe->head);
155 : 0 : DFS_POOL_STAT_INC(pulse_used);
156 : : }
157 : 0 : spin_unlock_bh(&pool_lock);
158 : 0 : return pe;
159 : : }
160 : :
161 : 0 : static struct pulse_elem *pulse_queue_get_tail(struct pri_detector *pde)
162 : : {
163 : 0 : struct list_head *l = &pde->pulses;
164 : 0 : if (list_empty(l))
165 : : return NULL;
166 : 0 : return list_entry(l->prev, struct pulse_elem, head);
167 : : }
168 : :
169 : 0 : static bool pulse_queue_dequeue(struct pri_detector *pde)
170 : : {
171 [ # # ]: 0 : struct pulse_elem *p = pulse_queue_get_tail(pde);
172 [ # # ]: 0 : if (p != NULL) {
173 : 0 : list_del_init(&p->head);
174 : 0 : pde->count--;
175 : : /* give it back to pool */
176 : 0 : pool_put_pulse_elem(p);
177 : : }
178 : 0 : return (pde->count > 0);
179 : : }
180 : :
181 : : /* remove pulses older than window */
182 : 0 : static void pulse_queue_check_window(struct pri_detector *pde)
183 : : {
184 : 0 : u64 min_valid_ts;
185 : 0 : struct pulse_elem *p;
186 : :
187 : : /* there is no delta time with less than 2 pulses */
188 [ # # ]: 0 : if (pde->count < 2)
189 : : return;
190 : :
191 [ # # ]: 0 : if (pde->last_ts <= pde->window_size)
192 : : return;
193 : :
194 : 0 : min_valid_ts = pde->last_ts - pde->window_size;
195 [ # # # # ]: 0 : while ((p = pulse_queue_get_tail(pde)) != NULL) {
196 [ # # ]: 0 : if (p->ts >= min_valid_ts)
197 : : return;
198 : 0 : pulse_queue_dequeue(pde);
199 : : }
200 : : }
201 : :
202 : 0 : static bool pulse_queue_enqueue(struct pri_detector *pde, u64 ts)
203 : : {
204 : 0 : struct pulse_elem *p = pool_get_pulse_elem();
205 [ # # ]: 0 : if (p == NULL) {
206 : 0 : p = kmalloc(sizeof(*p), GFP_ATOMIC);
207 [ # # ]: 0 : if (p == NULL) {
208 : 0 : DFS_POOL_STAT_INC(pulse_alloc_error);
209 : 0 : return false;
210 : : }
211 : 0 : DFS_POOL_STAT_INC(pulse_allocated);
212 : 0 : DFS_POOL_STAT_INC(pulse_used);
213 : : }
214 : 0 : INIT_LIST_HEAD(&p->head);
215 : 0 : p->ts = ts;
216 : 0 : list_add(&p->head, &pde->pulses);
217 : 0 : pde->count++;
218 : 0 : pde->last_ts = ts;
219 : 0 : pulse_queue_check_window(pde);
220 [ # # ]: 0 : if (pde->count >= pde->max_count)
221 : 0 : pulse_queue_dequeue(pde);
222 : : return true;
223 : : }
224 : :
225 : 0 : static bool pseq_handler_create_sequences(struct pri_detector *pde,
226 : : u64 ts, u32 min_count)
227 : : {
228 : 0 : struct pulse_elem *p;
229 [ # # ]: 0 : list_for_each_entry(p, &pde->pulses, head) {
230 : 0 : struct pri_sequence ps, *new_ps;
231 : 0 : struct pulse_elem *p2;
232 : 0 : u32 tmp_false_count;
233 : 0 : u64 min_valid_ts;
234 : 0 : u32 delta_ts = ts - p->ts;
235 : :
236 [ # # ]: 0 : if (delta_ts < pde->rs->pri_min)
237 : : /* ignore too small pri */
238 : 0 : continue;
239 : :
240 [ # # ]: 0 : 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 : 0 : ps.count = 2;
246 : 0 : ps.count_falses = 0;
247 : 0 : ps.first_ts = p->ts;
248 : 0 : ps.last_ts = ts;
249 [ # # ]: 0 : ps.pri = GET_PRI_TO_USE(pde->rs->pri_min,
250 : : pde->rs->pri_max, ts - p->ts);
251 : 0 : ps.dur = ps.pri * (pde->rs->ppb - 1)
252 : 0 : + 2 * pde->rs->max_pri_tolerance;
253 : :
254 : 0 : p2 = p;
255 : 0 : tmp_false_count = 0;
256 : 0 : min_valid_ts = ts - ps.dur;
257 : : /* check which past pulses are candidates for new sequence */
258 [ # # ]: 0 : list_for_each_entry_continue(p2, &pde->pulses, head) {
259 : 0 : u32 factor;
260 [ # # ]: 0 : if (p2->ts < min_valid_ts)
261 : : /* stop on crossing window border */
262 : : break;
263 : : /* check if pulse match (multi)PRI */
264 [ # # ]: 0 : factor = pde_get_multiple(ps.last_ts - p2->ts, ps.pri,
265 : : pde->rs->max_pri_tolerance);
266 [ # # ]: 0 : if (factor > 0) {
267 : 0 : ps.count++;
268 : 0 : ps.first_ts = p2->ts;
269 : : /*
270 : : * on match, add the intermediate falses
271 : : * and reset counter
272 : : */
273 : 0 : ps.count_falses += tmp_false_count;
274 : 0 : tmp_false_count = 0;
275 : : } else {
276 : : /* this is a potential false one */
277 : 0 : tmp_false_count++;
278 : : }
279 : : }
280 [ # # ]: 0 : if (ps.count <= min_count)
281 : : /* did not reach minimum count, drop sequence */
282 : 0 : continue;
283 : :
284 : : /* this is a valid one, add it */
285 : 0 : ps.deadline_ts = ps.first_ts + ps.dur;
286 : 0 : new_ps = pool_get_pseq_elem();
287 [ # # ]: 0 : if (new_ps == NULL) {
288 : 0 : new_ps = kmalloc(sizeof(*new_ps), GFP_ATOMIC);
289 [ # # ]: 0 : if (new_ps == NULL) {
290 : 0 : DFS_POOL_STAT_INC(pseq_alloc_error);
291 : 0 : return false;
292 : : }
293 : 0 : DFS_POOL_STAT_INC(pseq_allocated);
294 : 0 : DFS_POOL_STAT_INC(pseq_used);
295 : : }
296 : 0 : memcpy(new_ps, &ps, sizeof(ps));
297 : 0 : INIT_LIST_HEAD(&new_ps->head);
298 : 0 : 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 : 0 : pseq_handler_add_to_existing_seqs(struct pri_detector *pde, u64 ts)
306 : : {
307 : 0 : u32 max_count = 0;
308 : 0 : struct pri_sequence *ps, *ps2;
309 [ # # ]: 0 : list_for_each_entry_safe(ps, ps2, &pde->sequences, head) {
310 : 0 : u32 delta_ts;
311 : 0 : u32 factor;
312 : :
313 : : /* first ensure that sequence is within window */
314 [ # # ]: 0 : if (ts > ps->deadline_ts) {
315 : 0 : list_del_init(&ps->head);
316 : 0 : pool_put_pseq_elem(ps);
317 : 0 : continue;
318 : : }
319 : :
320 : 0 : delta_ts = ts - ps->last_ts;
321 : 0 : factor = pde_get_multiple(delta_ts, ps->pri,
322 [ # # ]: 0 : pde->rs->max_pri_tolerance);
323 [ # # ]: 0 : if (factor > 0) {
324 : 0 : ps->last_ts = ts;
325 : 0 : ps->count++;
326 : :
327 : 0 : if (max_count < ps->count)
328 : : max_count = ps->count;
329 : : } else {
330 : 0 : ps->count_falses++;
331 : : }
332 : : }
333 : 0 : return max_count;
334 : : }
335 : :
336 : : static struct pri_sequence *
337 : 0 : pseq_handler_check_detection(struct pri_detector *pde)
338 : : {
339 : 0 : struct pri_sequence *ps;
340 : :
341 : 0 : if (list_empty(&pde->sequences))
342 : : return NULL;
343 : :
344 [ # # ]: 0 : 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 [ # # ]: 0 : if ((ps->count >= pde->rs->ppb_thresh) &&
351 [ # # ]: 0 : (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 : 0 : static void pri_detector_reset(struct pri_detector *pde, u64 ts)
360 : : {
361 : 0 : struct pri_sequence *ps, *ps0;
362 : 0 : struct pulse_elem *p, *p0;
363 [ # # ]: 0 : list_for_each_entry_safe(ps, ps0, &pde->sequences, head) {
364 : 0 : list_del_init(&ps->head);
365 : 0 : pool_put_pseq_elem(ps);
366 : : }
367 [ # # ]: 0 : list_for_each_entry_safe(p, p0, &pde->pulses, head) {
368 : 0 : list_del_init(&p->head);
369 : 0 : pool_put_pulse_elem(p);
370 : : }
371 : 0 : pde->count = 0;
372 : 0 : pde->last_ts = ts;
373 : 0 : }
374 : :
375 : 0 : static void pri_detector_exit(struct pri_detector *de)
376 : : {
377 : 0 : pri_detector_reset(de, 0);
378 : 0 : pool_deregister_ref();
379 : 0 : kfree(de);
380 : 0 : }
381 : :
382 : 0 : static struct pri_sequence *pri_detector_add_pulse(struct pri_detector *de,
383 : : struct pulse_event *event)
384 : : {
385 : 0 : u32 max_updated_seq;
386 : 0 : struct pri_sequence *ps;
387 : 0 : u64 ts = event->ts;
388 : 0 : const struct radar_detector_specs *rs = de->rs;
389 : :
390 : : /* ignore pulses not within width range */
391 [ # # # # ]: 0 : if ((rs->width_min > event->width) || (rs->width_max < event->width))
392 : : return NULL;
393 : :
394 [ # # ]: 0 : if ((ts - de->last_ts) < rs->max_pri_tolerance)
395 : : /* if delta to last pulse is too short, don't use this pulse */
396 : : return NULL;
397 : : /* radar detector spec needs chirp, but not detected */
398 [ # # # # ]: 0 : if (rs->chirp && rs->chirp != event->chirp)
399 : : return NULL;
400 : :
401 : 0 : de->last_ts = ts;
402 : :
403 : 0 : max_updated_seq = pseq_handler_add_to_existing_seqs(de, ts);
404 : :
405 [ # # ]: 0 : if (!pseq_handler_create_sequences(de, ts, max_updated_seq)) {
406 : 0 : pri_detector_reset(de, ts);
407 : 0 : return NULL;
408 : : }
409 : :
410 [ # # ]: 0 : ps = pseq_handler_check_detection(de);
411 : :
412 [ # # ]: 0 : if (ps == NULL)
413 : 0 : pulse_queue_enqueue(de, ts);
414 : :
415 : : return ps;
416 : : }
417 : :
418 : 0 : struct pri_detector *pri_detector_init(const struct radar_detector_specs *rs)
419 : : {
420 : 0 : struct pri_detector *de;
421 : :
422 : 0 : de = kzalloc(sizeof(*de), GFP_ATOMIC);
423 [ # # ]: 0 : if (de == NULL)
424 : : return NULL;
425 : 0 : de->exit = pri_detector_exit;
426 : 0 : de->add_pulse = pri_detector_add_pulse;
427 : 0 : de->reset = pri_detector_reset;
428 : :
429 : 0 : INIT_LIST_HEAD(&de->sequences);
430 : 0 : INIT_LIST_HEAD(&de->pulses);
431 : 0 : de->window_size = rs->pri_max * rs->ppb * rs->num_pri;
432 : 0 : de->max_count = rs->ppb * 2;
433 : 0 : de->rs = rs;
434 : :
435 : 0 : pool_register_ref();
436 : 0 : return de;
437 : : }
|
