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