drivers/net/wireless/ath/ath9k/dfs_pri_detector.c

   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
  19 #include "dfs_pattern_detector.h"
  20 #include "dfs_pri_detector.h"
  21
  22 /**
  23  * struct pri_sequence - sequence of pulses matching one PRI
  24  * @head: list_head
  25  * @pri: pulse repetition interval (PRI) in usecs
  26  * @dur: duration of sequence in usecs
  27  * @count: number of pulses in this sequence
  28  * @count_falses: number of not matching pulses in this sequence
  29  * @first_ts: time stamp of first pulse in usecs
  30  * @last_ts: time stamp of last pulse in usecs
  31  * @deadline_ts: deadline when this sequence becomes invalid (first_ts + dur)
  32  */
  33 struct pri_sequence {
  34         struct list_head head;
  35         u32 pri;
  36         u32 dur;
  37         u32 count;
  38         u32 count_falses;
  39         u64 first_ts;
  40         u64 last_ts;
  41         u64 deadline_ts;
  42 };
  43
  44 /**
  45  * struct pulse_elem - elements in pulse queue
  46  * @ts: time stamp in usecs
  47  */
  48 struct pulse_elem {
  49         struct list_head head;
  50         u64 ts;
  51 };
  52
  53 /**
  54  * pde_get_multiple() - get number of multiples considering a given tolerance
  55  * @return factor if abs(val - factor*fraction) <= tolerance, 0 otherwise
  56  */
  57 static u32 pde_get_multiple(u32 val, u32 fraction, u32 tolerance)
  58 {
  59         u32 remainder;
  60         u32 factor;
  61         u32 delta;
  62
  63         if (fraction == 0)
  64                 return 0;
  65
  66         delta = (val < fraction) ? (fraction - val) : (val - fraction);
  67
  68         if (delta <= tolerance)
  69                 /* val and fraction are within tolerance */
  70                 return 1;
  71
  72         factor = val / fraction;
  73         remainder = val % fraction;
  74         if (remainder > tolerance) {
  75                 /* no exact match */
  76                 if ((fraction - remainder) <= tolerance)
  77                         /* remainder is within tolerance */
  78                         factor++;
  79                 else
  80                         factor = 0;
  81         }
  82         return factor;
  83 }
  84
  85 /**
  86  * DOC: Singleton Pulse and Sequence Pools
  87  *
  88  * Instances of pri_sequence and pulse_elem are kept in singleton pools to
  89  * reduce the number of dynamic allocations. They are shared between all
  90  * instances and grow up to the peak number of simultaneously used objects.
  91  *
  92  * Memory is freed after all references to the pools are released.
  93  */
  94 static u32 singleton_pool_references;
  95 static LIST_HEAD(pulse_pool);
  96 static LIST_HEAD(pseq_pool);
  97
  98 static struct pulse_elem *pulse_queue_get_tail(struct pri_detector *pde)
  99 {
 100         struct list_head *l = &pde->pulses;
 101         if (list_empty(l))
 102                 return NULL;
 103         return list_entry(l->prev, struct pulse_elem, head);
 104 }
 105
 106 static bool pulse_queue_dequeue(struct pri_detector *pde)
 107 {
 108         struct pulse_elem *p = pulse_queue_get_tail(pde);
 109         if (p != NULL) {
 110                 list_del_init(&p->head);
 111                 pde->count--;
 112                 /* give it back to pool */
 113                 list_add(&p->head, &pulse_pool);
 114         }
 115         return (pde->count > 0);
 116 }
 117
 118 /* remove pulses older than window */
 119 static void pulse_queue_check_window(struct pri_detector *pde)
 120 {
 121         u64 min_valid_ts;
 122         struct pulse_elem *p;
 123
 124         /* there is no delta time with less than 2 pulses */
 125         if (pde->count < 2)
 126                 return;
 127
 128         if (pde->last_ts <= pde->window_size)
 129                 return;
 130
 131         min_valid_ts = pde->last_ts - pde->window_size;
 132         while ((p = pulse_queue_get_tail(pde)) != NULL) {
 133                 if (p->ts >= min_valid_ts)
 134                         return;
 135                 pulse_queue_dequeue(pde);
 136         }
 137 }
 138
 139 static bool pulse_queue_enqueue(struct pri_detector *pde, u64 ts)
 140 {
 141         struct pulse_elem *p;
 142         if (!list_empty(&pulse_pool)) {
 143                 p = list_first_entry(&pulse_pool, struct pulse_elem, head);
 144                 list_del(&p->head);
 145         } else {
 146                 p = kmalloc(sizeof(*p), GFP_KERNEL);
 147                 if (p == NULL) {
 148                         pr_err("failed to allocate pulse_elem\n");
 149                         return false;
 150                 }
 151         }
 152         INIT_LIST_HEAD(&p->head);
 153         p->ts = ts;
 154         list_add(&p->head, &pde->pulses);
 155         pde->count++;
 156         pde->last_ts = ts;
 157         pulse_queue_check_window(pde);
 158         if (pde->count >= pde->max_count)
 159                 pulse_queue_dequeue(pde);
 160         return true;
 161 }
 162
 163 static bool pseq_handler_create_sequences(struct pri_detector *pde,
 164                                           u64 ts, u32 min_count)
 165 {
 166         struct pulse_elem *p;
 167         list_for_each_entry(p, &pde->pulses, head) {
 168                 struct pri_sequence ps, *new_ps;
 169                 struct pulse_elem *p2;
 170                 u32 tmp_false_count;
 171                 u64 min_valid_ts;
 172                 u32 delta_ts = ts - p->ts;
 173
 174                 if (delta_ts < pde->rs->pri_min)
 175                         /* ignore too small pri */
 176                         continue;
 177
 178                 if (delta_ts > pde->rs->pri_max)
 179                         /* stop on too large pri (sorted list) */
 180                         break;
 181
 182                 /* build a new sequence with new potential pri */
 183                 ps.count = 2;
 184                 ps.count_falses = 0;
 185                 ps.first_ts = p->ts;
 186                 ps.last_ts = ts;
 187                 ps.pri = ts - p->ts;
 188                 ps.dur = ps.pri * (pde->rs->ppb - 1)
 189                                 + 2 * pde->rs->max_pri_tolerance;
 190
 191                 p2 = p;
 192                 tmp_false_count = 0;
 193                 min_valid_ts = ts - ps.dur;
 194                 /* check which past pulses are candidates for new sequence */
 195                 list_for_each_entry_continue(p2, &pde->pulses, head) {
 196                         u32 factor;
 197                         if (p2->ts < min_valid_ts)
 198                                 /* stop on crossing window border */
 199                                 break;
 200                         /* check if pulse match (multi)PRI */
 201                         factor = pde_get_multiple(ps.last_ts - p2->ts, ps.pri,
 202                                                   pde->rs->max_pri_tolerance);
 203                         if (factor > 0) {
 204                                 ps.count++;
 205                                 ps.first_ts = p2->ts;
 206                                 /*
 207                                  * on match, add the intermediate falses
 208                                  * and reset counter
 209                                  */
 210                                 ps.count_falses += tmp_false_count;
 211                                 tmp_false_count = 0;
 212                         } else {
 213                                 /* this is a potential false one */
 214                                 tmp_false_count++;
 215                         }
 216                 }
 217                 if (ps.count < min_count)
 218                         /* did not reach minimum count, drop sequence */
 219                         continue;
 220
 221                 /* this is a valid one, add it */
 222                 ps.deadline_ts = ps.first_ts + ps.dur;
 223
 224                 if (!list_empty(&pseq_pool)) {
 225                         new_ps = list_first_entry(&pseq_pool,
 226                                                   struct pri_sequence, head);
 227                         list_del(&new_ps->head);
 228                 } else {
 229                         new_ps = kmalloc(sizeof(*new_ps), GFP_KERNEL);
 230                         if (new_ps == NULL)
 231                                 return false;
 232                 }
 233                 memcpy(new_ps, &ps, sizeof(ps));
 234                 INIT_LIST_HEAD(&new_ps->head);
 235                 list_add(&new_ps->head, &pde->sequences);
 236         }
 237         return true;
 238 }
 239
 240 /* check new ts and add to all matching existing sequences */
 241 static u32
 242 pseq_handler_add_to_existing_seqs(struct pri_detector *pde, u64 ts)
 243 {
 244         u32 max_count = 0;
 245         struct pri_sequence *ps, *ps2;
 246         list_for_each_entry_safe(ps, ps2, &pde->sequences, head) {
 247                 u32 delta_ts;
 248                 u32 factor;
 249
 250                 /* first ensure that sequence is within window */
 251                 if (ts > ps->deadline_ts) {
 252                         list_del_init(&ps->head);
 253                         list_add(&ps->head, &pseq_pool);
 254                         continue;
 255                 }
 256
 257                 delta_ts = ts - ps->last_ts;
 258                 factor = pde_get_multiple(delta_ts, ps->pri,
 259                                           pde->rs->max_pri_tolerance);
 260                 if (factor > 0) {
 261                         ps->last_ts = ts;
 262                         ps->count++;
 263
 264                         if (max_count < ps->count)
 265                                 max_count = ps->count;
 266                 } else {
 267                         ps->count_falses++;
 268                 }
 269         }
 270         return max_count;
 271 }
 272
 273 static struct pri_sequence *
 274 pseq_handler_check_detection(struct pri_detector *pde)
 275 {
 276         struct pri_sequence *ps;
 277
 278         if (list_empty(&pde->sequences))
 279                 return NULL;
 280
 281         list_for_each_entry(ps, &pde->sequences, head) {
 282                 /*
 283                  * we assume to have enough matching confidence if we
 284                  * 1) have enough pulses
 285                  * 2) have more matching than false pulses
 286                  */
 287                 if ((ps->count >= pde->rs->ppb_thresh) &&
 288                     (ps->count * pde->rs->num_pri >= ps->count_falses))
 289                         return ps;
 290         }
 291         return NULL;
 292 }
 293
 294
 295 /* free pulse queue and sequences list and give objects back to pools */
 296 static void pri_detector_reset(struct pri_detector *pde, u64 ts)
 297 {
 298         struct pri_sequence *ps, *ps0;
 299         struct pulse_elem *p, *p0;
 300         list_for_each_entry_safe(ps, ps0, &pde->sequences, head) {
 301                 list_del_init(&ps->head);
 302                 list_add(&ps->head, &pseq_pool);
 303         }
 304         list_for_each_entry_safe(p, p0, &pde->pulses, head) {
 305                 list_del_init(&p->head);
 306                 list_add(&p->head, &pulse_pool);
 307         }
 308         pde->count = 0;
 309         pde->last_ts = ts;
 310 }
 311
 312 static void pri_detector_exit(struct pri_detector *de)
 313 {
 314         pri_detector_reset(de, 0);
 315
 316         singleton_pool_references--;
 317         if (singleton_pool_references == 0) {
 318                 /* free singleton pools with no references left */
 319                 struct pri_sequence *ps, *ps0;
 320                 struct pulse_elem *p, *p0;
 321
 322                 list_for_each_entry_safe(p, p0, &pulse_pool, head) {
 323                         list_del(&p->head);
 324                         kfree(p);
 325                 }
 326                 list_for_each_entry_safe(ps, ps0, &pseq_pool, head) {
 327                         list_del(&ps->head);
 328                         kfree(ps);
 329                 }
 330         }
 331         kfree(de);
 332 }
 333
 334 static bool pri_detector_add_pulse(struct pri_detector *de,
 335                                    struct pulse_event *event)
 336 {
 337         u32 max_updated_seq;
 338         struct pri_sequence *ps;
 339         u64 ts = event->ts;
 340         const struct radar_detector_specs *rs = de->rs;
 341
 342         /* ignore pulses not within width range */
 343         if ((rs->width_min > event->width) || (rs->width_max < event->width))
 344                 return false;
 345
 346         if ((ts - de->last_ts) < rs->max_pri_tolerance)
 347                 /* if delta to last pulse is too short, don't use this pulse */
 348                 return false;
 349         de->last_ts = ts;
 350
 351         max_updated_seq = pseq_handler_add_to_existing_seqs(de, ts);
 352
 353         if (!pseq_handler_create_sequences(de, ts, max_updated_seq)) {
 354                 pr_err("failed to create pulse sequences\n");
 355                 pri_detector_reset(de, ts);
 356                 return false;
 357         }
 358
 359         ps = pseq_handler_check_detection(de);
 360
 361         if (ps != NULL) {
 362                 pr_info("DFS: radar found: pri=%d, count=%d, count_false=%d\n",
 363                          ps->pri, ps->count, ps->count_falses);
 364                 pri_detector_reset(de, ts);
 365                 return true;
 366         }
 367         pulse_queue_enqueue(de, ts);
 368         return false;
 369 }
 370
 371 struct pri_detector *
 372 pri_detector_init(const struct radar_detector_specs *rs)
 373 {
 374         struct pri_detector *de;
 375         de = kzalloc(sizeof(*de), GFP_KERNEL);
 376         if (de == NULL)
 377                 return NULL;
 378         de->exit = pri_detector_exit;
 379         de->add_pulse = pri_detector_add_pulse;
 380         de->reset = pri_detector_reset;
 381
 382         INIT_LIST_HEAD(&de->sequences);
 383         INIT_LIST_HEAD(&de->pulses);
 384         de->window_size = rs->pri_max * rs->ppb * rs->num_pri;
 385         de->max_count = rs->ppb * 2;
 386         de->rs = rs;
 387
 388         singleton_pool_references++;
 389         return de;
 390 }