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 methodes 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-2008 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
  36 #include "datatypes.h"
  37
  38 #include "seq_window.h"
  39
  40 #include <stdlib.h>
  41 #include <string.h>
  42
  43 #include <stdio.h>
  44
  45 int seq_win_init(seq_win_t* win, window_size_t size)
  46 {
  47   if(!win)
  48     return -1;
  49
  50   win->size_ = size;
  51   win->first_ = NULL;
  52
  53   return 0;
  54 }
  55
  56 void seq_win_clear(seq_win_t* win)
  57 {
  58   if(!win)
  59     return;
  60
  61   seq_win_element_t* ptr = win->first_;
  62   while(ptr) {
  63     seq_win_element_t* to_free = ptr;
  64     ptr = ptr->next_;
  65     if(to_free->window_)
  66       free(to_free->window_);
  67
  68     free(to_free);
  69   }
  70 }
  71
  72 seq_win_element_t* seq_win_new_element(sender_id_t sender_id, seq_nr_t max, window_size_t size)
  73 {
  74   if(!size)
  75     return NULL;
  76
  77   seq_win_element_t* e = malloc(sizeof(seq_win_element_t));
  78   if(!e)
  79     return NULL;
  80
  81   e->sender_id_ = sender_id;
  82   e->max_ = max;
  83   e->pos_ = 0;
  84   e->window_ = malloc(sizeof(seq_nr_t)*size);
  85   if(!e->window_) {
  86     free(e);
  87     return NULL;
  88   }
  89   memset(e->window_, 0, size);
  90   e->window_[e->pos_] = 1;
  91   e->next_ = NULL;
  92
  93   return e;
  94 }
  95
  96 int seq_win_check_and_add(seq_win_t* win, sender_id_t sender_id, seq_nr_t seq_nr)
  97 {
  98   if(!win)
  99     return -1;
 100
 101   if(!win->size_)
 102     return 0;
 103
 104   seq_win_element_t* ptr = win->first_;
 105   while(ptr) {
 106     if(ptr->sender_id_ == sender_id) {
 107
 108       int shifted = 0;
 109       if(ptr->max_ < win->size_) {
 110         ptr->max_ += SEQ_NR_MAX/2;
 111         seq_nr += SEQ_NR_MAX/2;
 112         shifted = 1;
 113       }
 114       else if(ptr->max_ > (SEQ_NR_MAX - win->size_)) {
 115         ptr->max_ -= SEQ_NR_MAX/2;
 116         seq_nr -= SEQ_NR_MAX/2;
 117         shifted = 2;
 118       }
 119
 120       seq_nr_t min = ptr->max_ - win->size_ + 1;
 121       if(seq_nr < min || seq_nr == ptr->max_) {
 122         if(shifted == 1)
 123           ptr->max_ -= SEQ_NR_MAX/2;
 124         else if(shifted == 2)
 125           ptr->max_ += SEQ_NR_MAX/2;
 126         return 1;
 127       }
 128
 129       if(seq_nr > ptr->max_) {
 130         seq_nr_t diff = seq_nr - ptr->max_;
 131         if(diff >= win->size_)
 132           diff = win->size_;
 133
 134         window_size_t new_pos = ptr->pos_ + diff;
 135
 136         if(new_pos >= win->size_) {
 137           new_pos -= win->size_;
 138
 139           if(ptr->pos_ < win->size_ - 1)
 140             memset(&(ptr->window_[ptr->pos_ + 1]), 0, win->size_ - ptr->pos_ - 1);
 141
 142           memset(ptr->window_, 0, new_pos);
 143         }
 144         else {
 145           memset(&(ptr->window_[ptr->pos_ + 1]), 0, diff);
 146         }
 147         ptr->pos_ = new_pos;
 148         ptr->window_[ptr->pos_] = 1;
 149         ptr->max_ = seq_nr;
 150
 151         if(shifted == 1)
 152           ptr->max_ -= SEQ_NR_MAX/2;
 153         else if(shifted == 2)
 154           ptr->max_ += SEQ_NR_MAX/2;
 155
 156         return 0;
 157       }
 158
 159       seq_nr_t diff = ptr->max_ - seq_nr;
 160       window_size_t pos = diff > ptr->pos_ ? ptr->pos_ + win->size_ : ptr->pos_;
 161       pos -= diff;
 162
 163       if(shifted == 1)
 164         ptr->max_ -= SEQ_NR_MAX/2;
 165       else if(shifted == 2)
 166         ptr->max_ += SEQ_NR_MAX/2;
 167
 168       int ret = ptr->window_[pos];
 169       ptr->window_[pos] = 1;
 170       return ret;
 171     }
 172     ptr = ptr->next_;
 173   }
 174   if(!win->first_) {
 175     win->first_ = seq_win_new_element(sender_id, seq_nr, win->size_);
 176     if(!win->first_)
 177       return -2;
 178   }
 179   else {
 180     ptr = win->first_;
 181     while(ptr->next_)
 182       ptr = ptr->next_;
 183     ptr->next_ = seq_win_new_element(sender_id, seq_nr, win->size_);
 184     if(!ptr->next_)
 185       return -2;
 186   }
 187
 188   return 0;
 189 }
 190
 191 void seq_win_print(seq_win_t* win)
 192 {
 193   printf("Sequence Window:\n");
 194
 195   if(!win)
 196     return;
 197
 198   seq_win_element_t* ptr = win->first_;
 199   while(ptr) {
 200     printf(" [%u]: (%u)-", ptr->sender_id_, ptr->max_);
 201     window_size_t i = ptr->pos_;
 202     while(1) {
 203       if(ptr->window_[i])
 204         printf("O");
 205       else
 206         printf(".");
 207
 208       if(i)
 209         i--;
 210       else
 211         i = win->size_ - 1;
 212
 213       if(i == ptr->pos_)
 214         break;
 215     }
 216     printf("\n");
 217     ptr = ptr->next_;
 218   }
 219 }