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 version 3 as
  24  *  published by the Free Software Foundation.
  25  *
  26  *  uAnytun is distributed in the hope that it will be useful,
  27  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  28  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  29  *  GNU General Public License for more details.
  30  *
  31  *  You should have received a copy of the GNU General Public License
  32  *  along with uAnytun. If not, see <http://www.gnu.org/licenses/>.
  33  */
  34
  35 #include "datatypes.h"
  36
  37 #include "seq_window.h"
  38
  39 #include <stdlib.h>
  40 #include <string.h>
  41
  42 #include <stdio.h>
  43
  44 int seq_win_init(seq_win_t* win, window_size_t size)
  45 {
  46   if(!win)
  47     return -1;
  48
  49   win->size_ = size;
  50   win->first_ = NULL;
  51
  52   return 0;
  53 }
  54
  55 void seq_win_clear(seq_win_t* win)
  56 {
  57   if(!win)
  58     return;
  59
  60   seq_win_element_t* ptr = win->first_;
  61   while(ptr) {
  62     seq_win_element_t* to_free = ptr;
  63     ptr = ptr->next_;
  64     if(to_free->window_)
  65       free(to_free->window_);
  66
  67     free(to_free);
  68   }
  69 }
  70
  71 seq_win_element_t* seq_win_new_element(sender_id_t sender_id, seq_nr_t max, window_size_t size)
  72 {
  73   if(!size)
  74     return NULL;
  75
  76   seq_win_element_t* e = malloc(sizeof(seq_win_element_t));
  77   if(!e)
  78     return NULL;
  79
  80   e->sender_id_ = sender_id;
  81   e->max_ = max;
  82   e->pos_ = 0;
  83   e->window_ = malloc(sizeof(seq_nr_t)*size);
  84   if(!e->window_) {
  85     free(e);
  86     return NULL;
  87   }
  88   memset(e->window_, 0, size);
  89   e->window_[e->pos_] = 1;
  90   e->next_ = NULL;
  91
  92   return e;
  93 }
  94
  95 int seq_win_check_and_add(seq_win_t* win, sender_id_t sender_id, seq_nr_t seq_nr)
  96 {
  97   if(!win)
  98     return -1;
  99
 100   if(!win->size_)
 101     return 0;
 102
 103   seq_win_element_t* ptr = win->first_;
 104   while(ptr) {
 105     if(ptr->sender_id_ == sender_id) {
 106
 107       int shifted = 0;
 108       if(ptr->max_ < win->size_) {
 109         ptr->max_ += SEQ_NR_MAX/2;
 110         seq_nr += SEQ_NR_MAX/2;
 111         shifted = 1;
 112       }
 113       else if(ptr->max_ > (SEQ_NR_MAX - win->size_)) {
 114         ptr->max_ -= SEQ_NR_MAX/2;
 115         seq_nr -= SEQ_NR_MAX/2;
 116         shifted = 2;
 117       }
 118
 119       seq_nr_t min = ptr->max_ - win->size_ + 1;
 120       if(seq_nr < min || seq_nr == ptr->max_) {
 121         if(shifted == 1)
 122           ptr->max_ -= SEQ_NR_MAX/2;
 123         else if(shifted == 2)
 124           ptr->max_ += SEQ_NR_MAX/2;
 125         return 1;
 126       }
 127
 128       if(seq_nr > ptr->max_) {
 129         seq_nr_t diff = seq_nr - ptr->max_;
 130         if(diff >= win->size_)
 131           diff = win->size_;
 132
 133         window_size_t new_pos = ptr->pos_ + diff;
 134
 135         if(new_pos >= win->size_) {
 136           new_pos -= win->size_;
 137
 138           if(ptr->pos_ < win->size_ - 1)
 139             memset(&(ptr->window_[ptr->pos_ + 1]), 0, win->size_ - ptr->pos_ - 1);
 140
 141           memset(ptr->window_, 0, new_pos);
 142         }
 143         else {
 144           memset(&(ptr->window_[ptr->pos_ + 1]), 0, diff);
 145         }
 146         ptr->pos_ = new_pos;
 147         ptr->window_[ptr->pos_] = 1;
 148         ptr->max_ = seq_nr;
 149
 150         if(shifted == 1)
 151           ptr->max_ -= SEQ_NR_MAX/2;
 152         else if(shifted == 2)
 153           ptr->max_ += SEQ_NR_MAX/2;
 154
 155         return 0;
 156       }
 157
 158       seq_nr_t diff = ptr->max_ - seq_nr;
 159       window_size_t pos = diff > ptr->pos_ ? ptr->pos_ + win->size_ : ptr->pos_;
 160       pos -= diff;
 161
 162       if(shifted == 1)
 163         ptr->max_ -= SEQ_NR_MAX/2;
 164       else if(shifted == 2)
 165         ptr->max_ += SEQ_NR_MAX/2;
 166
 167       int ret = ptr->window_[pos];
 168       ptr->window_[pos] = 1;
 169       return ret;
 170     }
 171     ptr = ptr->next_;
 172   }
 173   if(!win->first_) {
 174     win->first_ = seq_win_new_element(sender_id, seq_nr, win->size_);
 175     if(!win->first_)
 176       return -2;
 177   }
 178   else {
 179     ptr = win->first_;
 180     while(ptr->next_)
 181       ptr = ptr->next_;
 182     ptr->next_ = seq_win_new_element(sender_id, seq_nr, win->size_);
 183     if(!ptr->next_)
 184       return -2;
 185   }
 186
 187   return 0;
 188 }
 189
 190 void seq_win_print(seq_win_t* win)
 191 {
 192   printf("Sequence Window:\n");
 193
 194   if(!win)
 195     return;
 196
 197   seq_win_element_t* ptr = win->first_;
 198   while(ptr) {
 199     printf(" [%u]: (%u)-", ptr->sender_id_, ptr->max_);
 200     window_size_t i = ptr->pos_;
 201     while(1) {
 202       if(ptr->window_[i])
 203         printf("O");
 204       else
 205         printf(".");
 206
 207       if(i)
 208         i--;
 209       else
 210         i = win->size_ - 1;
 211
 212       if(i == ptr->pos_)
 213         break;
 214     }
 215     printf("\n");
 216     ptr = ptr->next_;
 217   }
 218 }