src/seq_window.c

   1 /*
   2  *  uAnytun
   3  *
   4  *  uAnytun is a tiny implementation of SATP. Unlike Anytun which is a full
   5  *  featured implementation uAnytun has no support for multiple connections
   6  *  or synchronisation. It is a small single threaded implementation intended
   7  *  to act as a client on small platforms.
   8  *  The secure anycast tunneling protocol (satp) defines a protocol used
   9  *  for communication between any combination of unicast and anycast
  10  *  tunnel endpoints.  It has less protocol overhead than IPSec in Tunnel
  11  *  mode and allows tunneling of every ETHER TYPE protocol (e.g.
  12  *  ethernet, ip, arp ...). satp directly includes cryptography and
  13  *  message authentication based on the methods used by SRTP.  It is
  14  *  intended to deliver a generic, scaleable and secure solution for
  15  *  tunneling and relaying of packets of any protocol.
  16  *
  17  *
  18  *  Copyright (C) 2007-2014 Christian Pointner <equinox@anytun.org>
  19  *
  20  *  This file is part of uAnytun.
  21  *
  22  *  uAnytun is free software: you can redistribute it and/or modify
  23  *  it under the terms of the GNU General Public License as published by
  24  *  the Free Software Foundation, either version 3 of the License, or
  25  *  any later version.
  26  *
  27  *  uAnytun is distributed in the hope that it will be useful,
  28  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  29  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  30  *  GNU General Public License for more details.
  31  *
  32  *  You should have received a copy of the GNU General Public License
  33  *  along with uAnytun. If not, see <http://www.gnu.org/licenses/>.
  34  *
  35  *  In addition, as a special exception, the copyright holders give
  36  *  permission to link the code of portions of this program with the
  37  *  OpenSSL library under certain conditions as described in each
  38  *  individual source file, and distribute linked combinations
  39  *  including the two.
  40  *  You must obey the GNU General Public License in all respects
  41  *  for all of the code used other than OpenSSL.  If you modify
  42  *  file(s) with this exception, you may extend this exception to your
  43  *  version of the file(s), but you are not obligated to do so.  If you
  44  *  do not wish to do so, delete this exception statement from your
  45  *  version.  If you delete this exception statement from all source
  46  *  files in the program, then also delete it here.
  47  */
  48
  49 #include "datatypes.h"
  50
  51 #include "seq_window.h"
  52
  53 #include <stdlib.h>
  54 #include <string.h>
  55
  56 #include <stdio.h>
  57
  58 int seq_win_init(seq_win_t* win, window_size_t size)
  59 {
  60   if(!win)
  61     return -1;
  62
  63   win->size_ = size;
  64   win->first_ = NULL;
  65
  66   return 0;
  67 }
  68
  69 void seq_win_clear(seq_win_t* win)
  70 {
  71   if(!win)
  72     return;
  73
  74   seq_win_element_t* ptr = win->first_;
  75   while(ptr) {
  76     seq_win_element_t* to_free = ptr;
  77     ptr = ptr->next_;
  78     if(to_free->window_)
  79       free(to_free->window_);
  80
  81     free(to_free);
  82   }
  83
  84   win->first_ = NULL;
  85 }
  86
  87 static seq_win_element_t* seq_win_new_element(sender_id_t sender_id, seq_nr_t max, window_size_t size)
  88 {
  89   if(!size)
  90     return NULL;
  91
  92   seq_win_element_t* e = malloc(sizeof(seq_win_element_t));
  93   if(!e)
  94     return NULL;
  95
  96   e->sender_id_ = sender_id;
  97   e->max_ = max;
  98   e->pos_ = 0;
  99   e->window_ = malloc(sizeof((*e->window_))*size);
 100   if(!e->window_) {
 101     free(e);
 102     return NULL;
 103   }
 104   memset(e->window_, 0, size);
 105   e->window_[e->pos_] = 1;
 106   e->next_ = NULL;
 107
 108   return e;
 109 }
 110
 111 int seq_win_check_and_add(seq_win_t* win, sender_id_t sender_id, seq_nr_t seq_nr)
 112 {
 113   if(!win)
 114     return -1;
 115
 116   if(!win->size_)
 117     return 0;
 118
 119   seq_win_element_t* ptr = win->first_;
 120   while(ptr) {
 121     if(ptr->sender_id_ == sender_id) {
 122
 123       int shifted = 0;
 124       if(ptr->max_ < win->size_) {
 125         ptr->max_ += SEQ_NR_MAX/2;
 126         seq_nr += SEQ_NR_MAX/2;
 127         shifted = 1;
 128       }
 129       else if(ptr->max_ > (SEQ_NR_MAX - win->size_)) {
 130         ptr->max_ -= SEQ_NR_MAX/2;
 131         seq_nr -= SEQ_NR_MAX/2;
 132         shifted = 2;
 133       }
 134
 135       seq_nr_t min = ptr->max_ - win->size_ + 1;
 136       if(seq_nr < min || seq_nr == ptr->max_) {
 137         if(shifted == 1)
 138           ptr->max_ -= SEQ_NR_MAX/2;
 139         else if(shifted == 2)
 140           ptr->max_ += SEQ_NR_MAX/2;
 141         return 1;
 142       }
 143
 144       if(seq_nr > ptr->max_) {
 145         seq_nr_t diff = seq_nr - ptr->max_;
 146         if(diff >= win->size_)
 147           diff = win->size_;
 148
 149         window_size_t new_pos = ptr->pos_ + diff;
 150
 151         if(new_pos >= win->size_) {
 152           new_pos -= win->size_;
 153
 154           if(ptr->pos_ < win->size_ - 1)
 155             memset(&(ptr->window_[ptr->pos_ + 1]), 0, win->size_ - ptr->pos_ - 1);
 156
 157           memset(ptr->window_, 0, new_pos);
 158         }
 159         else {
 160           memset(&(ptr->window_[ptr->pos_ + 1]), 0, diff);
 161         }
 162         ptr->pos_ = new_pos;
 163         ptr->window_[ptr->pos_] = 1;
 164         ptr->max_ = seq_nr;
 165
 166         if(shifted == 1)
 167           ptr->max_ -= SEQ_NR_MAX/2;
 168         else if(shifted == 2)
 169           ptr->max_ += SEQ_NR_MAX/2;
 170
 171         return 0;
 172       }
 173
 174       seq_nr_t diff = ptr->max_ - seq_nr;
 175       window_size_t pos = diff > ptr->pos_ ? ptr->pos_ + win->size_ : ptr->pos_;
 176       pos -= diff;
 177
 178       if(shifted == 1)
 179         ptr->max_ -= SEQ_NR_MAX/2;
 180       else if(shifted == 2)
 181         ptr->max_ += SEQ_NR_MAX/2;
 182
 183       int ret = ptr->window_[pos];
 184       ptr->window_[pos] = 1;
 185       return ret;
 186     }
 187     ptr = ptr->next_;
 188   }
 189   if(!win->first_) {
 190     win->first_ = seq_win_new_element(sender_id, seq_nr, win->size_);
 191     if(!win->first_)
 192       return -2;
 193   }
 194   else {
 195     ptr = win->first_;
 196     while(ptr->next_)
 197       ptr = ptr->next_;
 198     ptr->next_ = seq_win_new_element(sender_id, seq_nr, win->size_);
 199     if(!ptr->next_)
 200       return -2;
 201   }
 202
 203   return 0;
 204 }
 205
 206 void seq_win_print(seq_win_t* win)
 207 {
 208   printf("Sequence Window:\n");
 209
 210   if(!win)
 211     return;
 212
 213   seq_win_element_t* ptr = win->first_;
 214   while(ptr) {
 215     printf(" [%u]: (%u)-", ptr->sender_id_, ptr->max_);
 216     window_size_t i = ptr->pos_;
 217     while(1) {
 218       if(ptr->window_[i])
 219         printf("O");
 220       else
 221         printf(".");
 222
 223       if(i)
 224         i--;
 225       else
 226         i = win->size_ - 1;
 227
 228       if(i == ptr->pos_)
 229         break;
 230     }
 231     printf("\n");
 232     ptr = ptr->next_;
 233   }
 234 }