src/seqWindow.cpp

   1 /*
   2  *  anytun
   3  *
   4  *  The secure anycast tunneling protocol (satp) defines a protocol used
   5  *  for communication between any combination of unicast and anycast
   6  *  tunnel endpoints.  It has less protocol overhead than IPSec in Tunnel
   7  *  mode and allows tunneling of every ETHER TYPE protocol (e.g.
   8  *  ethernet, ip, arp ...). satp directly includes cryptography and
   9  *  message authentication based on the methods used by SRTP.  It is
  10  *  intended to deliver a generic, scaleable and secure solution for
  11  *  tunneling and relaying of packets of any protocol.
  12  *
  13  *
  14  *  Copyright (C) 2007-2014 Markus Grüneis, Othmar Gsenger, Erwin Nindl,
  15  *                          Christian Pointner <satp@wirdorange.org>
  16  *
  17  *  This file is part of Anytun.
  18  *
  19  *  Anytun is free software: you can redistribute it and/or modify
  20  *  it under the terms of the GNU General Public License as published by
  21  *  the Free Software Foundation, either version 3 of the License, or
  22  *  any later version.
  23  *
  24  *  Anytun is distributed in the hope that it will be useful,
  25  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  26  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  27  *  GNU General Public License for more details.
  28  *
  29  *  You should have received a copy of the GNU General Public License
  30  *  along with Anytun.  If not, see <http://www.gnu.org/licenses/>.
  31  *
  32  *  In addition, as a special exception, the copyright holders give
  33  *  permission to link the code of portions of this program with the
  34  *  OpenSSL library under certain conditions as described in each
  35  *  individual source file, and distribute linked combinations
  36  *  including the two.
  37  *  You must obey the GNU General Public License in all respects
  38  *  for all of the code used other than OpenSSL.  If you modify
  39  *  file(s) with this exception, you may extend this exception to your
  40  *  version of the file(s), but you are not obligated to do so.  If you
  41  *  do not wish to do so, delete this exception statement from your
  42  *  version.  If you delete this exception statement from all source
  43  *  files in the program, then also delete it here.
  44  */
  45
  46 #include "threadUtils.hpp"
  47 #include "datatypes.h"
  48 #include <cstring>
  49 #include "seqWindow.h"
  50
  51 SeqWindowElement::SeqWindowElement()
  52 {
  53   window_ = NULL;
  54   pos_ = 0;
  55   max_ = 0;
  56 }
  57
  58 SeqWindowElement::~SeqWindowElement()
  59 {
  60   if(window_) {
  61     delete[] window_;
  62   }
  63 }
  64
  65 void SeqWindowElement::init(window_size_t w, seq_nr_t m)
  66 {
  67   if(window_) {
  68     delete[] window_;
  69   }
  70   window_ = new uint8_t[w];
  71   memset(window_, 0, w);
  72   pos_ = 0;
  73   max_ = m;
  74   window_[pos_] = 1;
  75 }
  76
  77 SeqWindow::SeqWindow(window_size_t w) : window_size_(w)
  78 {
  79 }
  80
  81 SeqWindow::~SeqWindow()
  82 {
  83 }
  84
  85 bool SeqWindow::checkAndAdd(sender_id_t sender, seq_nr_t seq_nr)
  86 {
  87   Lock lock(mutex_);
  88   if(!window_size_) {
  89     return false;
  90   }
  91
  92   SenderMap::iterator s = sender_.find(sender);
  93   if(s == sender_.end()) {
  94     sender_[sender].init(window_size_, seq_nr);
  95     return false;
  96   }
  97
  98   int shifted = 0;
  99   if(s->second.max_ < window_size_) {
 100     s->second.max_ += SEQ_NR_MAX/2;
 101     seq_nr += SEQ_NR_MAX/2;
 102     shifted = 1;
 103   } else if(s->second.max_ > (SEQ_NR_MAX - window_size_)) {
 104     s->second.max_ -= SEQ_NR_MAX/2;
 105     seq_nr -= SEQ_NR_MAX/2;
 106     shifted = 2;
 107   }
 108
 109   seq_nr_t min = s->second.max_ - window_size_ + 1;
 110   if(seq_nr < min || seq_nr == s->second.max_) {
 111     if(shifted == 1) {
 112       s->second.max_ -= SEQ_NR_MAX/2;
 113     } else if(shifted == 2) {
 114       s->second.max_ += SEQ_NR_MAX/2;
 115     }
 116     return true;
 117   }
 118
 119   if(seq_nr > s->second.max_) {
 120     seq_nr_t diff = seq_nr - s->second.max_;
 121     if(diff >= window_size_) {
 122       diff = window_size_;
 123     }
 124
 125     window_size_t new_pos = s->second.pos_ + diff;
 126
 127     if(new_pos >= window_size_) {
 128       new_pos -= window_size_;
 129
 130       if(s->second.pos_ < window_size_ - 1) {
 131         memset(&(s->second.window_[s->second.pos_ + 1]), 0, window_size_ - s->second.pos_ - 1);
 132       }
 133
 134       memset(s->second.window_, 0, new_pos);
 135     } else {
 136       memset(&(s->second.window_[s->second.pos_ + 1]), 0, diff);
 137     }
 138     s->second.pos_ = new_pos;
 139     s->second.window_[s->second.pos_] = 1;
 140     s->second.max_ = seq_nr;
 141
 142     if(shifted == 1) {
 143       s->second.max_ -= SEQ_NR_MAX/2;
 144     } else if(shifted == 2) {
 145       s->second.max_ += SEQ_NR_MAX/2;
 146     }
 147
 148     return false;
 149   }
 150
 151   seq_nr_t diff = s->second.max_ - seq_nr;
 152   window_size_t pos = diff > s->second.pos_ ? s->second.pos_ + window_size_ : s->second.pos_;
 153   pos -= diff;
 154
 155   if(shifted == 1) {
 156     s->second.max_ -= SEQ_NR_MAX/2;
 157   } else if(shifted == 2) {
 158     s->second.max_ += SEQ_NR_MAX/2;
 159   }
 160
 161   int ret = s->second.window_[pos];
 162   s->second.window_[pos] = 1;
 163
 164   if(ret) {
 165     return true;
 166   }
 167
 168   return false;
 169 }
 170
 171 void SeqWindow::clear(sender_id_t sender)
 172 {
 173   Lock lock(mutex_);
 174   sender_.erase(sender);
 175 }
 176
 177 void SeqWindow::clear()
 178 {
 179   Lock lock(mutex_);
 180   sender_.clear();
 181 }