swift.h

   1 /*
   2  *  swift.h
   3  *  the main header file for libswift, normally you should only read this one
   4  *
   5  *  Created by Victor Grishchenko on 3/6/09.
   6  *  Copyright 2009 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9 /*
  10
  11 The P2TP protocol
  12
  13 Messages
  14
  15  HANDSHAKE    00, channelid
  16  Communicates the channel id of the sender. The
  17  initial handshake packet also has the root hash
  18  (a HASH message).
  19
  20  DATA        01, bin_32, buffer
  21  1K of data.
  22
  23  ACK        02, bin_32
  24  ACKTS      08, bin_32, timestamp_32
  25  Confirms successfull delivery of data. Used for
  26  congestion control, as well.
  27
  28  HINT        03, bin_32
  29  Practical value of "hints" is to avoid overlap, mostly.
  30  Hints might be lost in the network or ignored.
  31  Peer might send out data without a hint.
  32  Hint which was not responded (by DATA) in some RTTs
  33  is considered to be ignored.
  34  As peers cant pick randomly kilobyte here and there,
  35  they send out "long hints" for non-base bins.
  36
  37  HASH        04, bin_32, sha1hash
  38  SHA1 hash tree hashes for data verification. The
  39  connection to a fresh peer starts with bootstrapping
  40  him with peak hashes. Later, before sending out
  41  any data, a peer sends the necessary uncle hashes.
  42
  43  PEX+/PEX-    05/06, ipv4 addr, port
  44  Peer exchange messages; reports all connected and
  45  disconected peers. Might has special meaning (as
  46  in the case with swarm supervisors).
  47
  48 */
  49 #ifndef P2TP_H
  50 #define P2TP_H
  51
  52 #ifdef _MSC_VER
  53 #include "compat/stdint.h"
  54 #else
  55 #include <stdint.h>
  56 #endif
  57 #include <deque>
  58 #include <vector>
  59 #include <algorithm>
  60 #include <string>
  61 #include "bin64.h"
  62 #include "bins.h"
  63 #include "datagram.h"
  64 #include "hashtree.h"
  65
  66 namespace swift {
  67
  68     #define NOW Datagram::now
  69
  70     /** tintbin is basically a pair<tint,bin64_t> plus some nice operators.
  71         Most frequently used in different queues (acknowledgements, requests,
  72         etc). */
  73     struct tintbin {
  74         tint    time;
  75         bin64_t bin;
  76         tintbin(const tintbin& b) : time(b.time), bin(b.bin) {}
  77         tintbin() : time(TINT_NEVER), bin(bin64_t::NONE) {}
  78         tintbin(tint time_, bin64_t bin_) : time(time_), bin(bin_) {}
  79         tintbin(bin64_t bin_) : time(NOW), bin(bin_) {}
  80         bool operator < (const tintbin& b) const
  81             { return time > b.time; }
  82         bool operator == (const tintbin& b) const
  83             { return time==b.time && bin==b.bin; }
  84         bool operator != (const tintbin& b) const
  85             { return !(*this==b); }
  86     };
  87
  88     typedef std::deque<tintbin> tbqueue;
  89     typedef std::deque<bin64_t> binqueue;
  90     typedef Address   Address;
  91
  92     /** A heap (priority queue) for timestamped bin numbers (tintbins). */
  93     class tbheap {
  94         tbqueue data_;
  95     public:
  96         int size () const { return data_.size(); }
  97         bool is_empty () const { return data_.empty(); }
  98         tintbin         pop() {
  99             tintbin ret = data_.front();
 100             std::pop_heap(data_.begin(),data_.end());
 101             data_.pop_back();
 102             return ret;
 103         }
 104         void            push(const tintbin& tb) {
 105             data_.push_back(tb);
 106             push_heap(data_.begin(),data_.end());
 107         }
 108         const tintbin&  peek() const {
 109             return data_.front();
 110         }
 111     };
 112
 113     /** swift protocol message types; these are used on the wire. */
 114     typedef enum {
 115         P2TP_HANDSHAKE = 0,
 116         P2TP_DATA = 1,
 117         P2TP_ACK = 2,
 118         P2TP_TS = 8,
 119         P2TP_HINT = 3,
 120         P2TP_HASH = 4,
 121         P2TP_PEX_ADD = 5,
 122         P2TP_PEX_RM = 6,
 123         P2TP_SIGNED_HASH = 7,
 124         P2TP_MESSAGE_COUNT = 8
 125     } messageid_t;
 126
 127     class PiecePicker;
 128     class CongestionController;
 129     class PeerSelector;
 130
 131
 132     /** A class representing single file transfer. */
 133     class    FileTransfer {
 134
 135     public:
 136
 137         /** A constructor. Open/submit/retrieve a file.
 138          *  @param file_name    the name of the file
 139          *  @param root_hash    the root hash of the file; zero hash if the file
 140                                 is newly submitted */
 141         FileTransfer(const char *file_name, const Sha1Hash& root_hash=Sha1Hash::ZERO);
 142
 143         /**    Close everything. */
 144         ~FileTransfer();
 145
 146
 147         /** While we need to feed ACKs to every peer, we try (1) avoid
 148             unnecessary duplication and (2) keep minimum state. Thus,
 149             we use a rotating queue of bin completion events. */
 150         //bin64_t         RevealAck (uint64_t& offset);
 151         /** Rotating queue read for channels of this transmission. */
 152         int             RevealChannel (int& i);
 153
 154         /** Find transfer by the root hash. */
 155         static FileTransfer* Find (const Sha1Hash& hash);
 156         /** Find transfer by the file descriptor. */
 157         static FileTransfer* file (int fd) {
 158             return fd<files.size() ? files[fd] : NULL;
 159         }
 160
 161         /** The binmap for data already retrieved and checked. */
 162         binmap_t&           ack_out ()  { return file_.ack_out(); }
 163         /** Piece picking strategy used by this transfer. */
 164         PiecePicker&    picker () { return *picker_; }
 165         /** The number of channels working for this transfer. */
 166         int             channel_count () const { return hs_in_.size(); }
 167         /** Hash tree checked file; all the hashes and data are kept here. */
 168         HashTree&       file() { return file_; }
 169         /** File descriptor for the data file. */
 170         int             fd () const { return file_.file_descriptor(); }
 171         /** Root SHA1 hash of the transfer (and the data file). */
 172         const Sha1Hash& root_hash () const { return file_.root_hash(); }
 173
 174     private:
 175
 176         static std::vector<FileTransfer*> files;
 177
 178         HashTree        file_;
 179
 180         /** Piece picker strategy. */
 181         PiecePicker*    picker_;
 182
 183         /** Channels working for this transfer. */
 184         binqueue        hs_in_;
 185         int             hs_in_offset_;
 186         std::deque<Address>        pex_in_;
 187
 188         /** Messages we are accepting.    */
 189         uint64_t        cap_out_;
 190
 191         tint            init_time_;
 192
 193     public:
 194         void            OnDataIn (bin64_t pos);
 195         void            OnPexIn (const Address& addr);
 196
 197         friend class Channel;
 198         friend uint64_t  Size (int fdes);
 199         friend bool      IsComplete (int fdes);
 200         friend uint64_t  Complete (int fdes);
 201         friend uint64_t  SeqComplete (int fdes);
 202         friend int     Open (const char* filename, const Sha1Hash& hash) ;
 203         friend void    Close (int fd) ;
 204     };
 205
 206
 207     /** PiecePicker implements some strategy of choosing (picking) what
 208         to request next, given the possible range of choices:
 209         data acknowledged by the peer minus data already retrieved.
 210         May pick sequentially, do rarest first or in some other way. */
 211     class PiecePicker {
 212     public:
 213         virtual void Randomize (uint64_t twist) = 0;
 214         /** The piece picking method itself.
 215          *  @param  offered     the daata acknowledged by the peer
 216          *  @param  max_width   maximum number of packets to ask for
 217          *  @param  expires     (not used currently) when to consider request expired
 218          *  @return             the bin number to request */
 219         virtual bin64_t Pick (binmap_t& offered, uint64_t max_width, tint expires) = 0;
 220     };
 221
 222
 223     class PeerSelector {
 224     public:
 225         virtual void AddPeer (const Address& addr, const Sha1Hash& root) = 0;
 226         virtual Address GetPeer (const Sha1Hash& for_root) = 0;
 227     };
 228
 229
 230     class DataStorer {
 231     public:
 232         DataStorer (const Sha1Hash& id, size_t size);
 233         virtual size_t    ReadData (bin64_t pos,uint8_t** buf) = 0;
 234         virtual size_t    WriteData (bin64_t pos, uint8_t* buf, size_t len) = 0;
 235     };
 236
 237
 238     /**    P2TP channel's "control block"; channels loosely correspond to TCP
 239         connections or FTP sessions; one channel is created for one file
 240         being transferred between two peers. As we don't need buffers and
 241         lots of other TCP stuff, sizeof(Channel+members) must be below 1K.
 242         Normally, API users do not deal with this class. */
 243     class Channel {
 244     public:
 245         Channel    (FileTransfer* file, int socket=-1, Address peer=Address());
 246         ~Channel();
 247
 248         typedef enum {
 249             KEEP_ALIVE_CONTROL,
 250             PING_PONG_CONTROL,
 251             SLOW_START_CONTROL,
 252             AIMD_CONTROL,
 253             LEDBAT_CONTROL
 254         } send_control_t;
 255
 256         static const char* SEND_CONTROL_MODES[];
 257
 258         static Channel*
 259                     RecvDatagram (int socket);
 260         static void Loop (tint till);
 261
 262         void        Recv (Datagram& dgram);
 263         void        Send ();
 264
 265         void        OnAck (Datagram& dgram);
 266         void        OnTs (Datagram& dgram);
 267         bin64_t     OnData (Datagram& dgram);
 268         void        OnHint (Datagram& dgram);
 269         void        OnHash (Datagram& dgram);
 270         void        OnPex (Datagram& dgram);
 271         void        OnHandshake (Datagram& dgram);
 272         void        AddHandshake (Datagram& dgram);
 273         bin64_t     AddData (Datagram& dgram);
 274         void        AddAck (Datagram& dgram);
 275         void        AddTs (Datagram& dgram);
 276         void        AddHint (Datagram& dgram);
 277         void        AddUncleHashes (Datagram& dgram, bin64_t pos);
 278         void        AddPeakHashes (Datagram& dgram);
 279         void        AddPex (Datagram& dgram);
 280
 281         void        BackOffOnLosses (float ratio=0.5);
 282         tint        SwitchSendControl (int control_mode);
 283         tint        NextSendTime ();
 284         tint        KeepAliveNextSendTime ();
 285         tint        PingPongNextSendTime ();
 286         tint        CwndRateNextSendTime ();
 287         tint        SlowStartNextSendTime ();
 288         tint        AimdNextSendTime ();
 289         tint        LedbatNextSendTime ();
 290
 291         static int  MAX_REORDERING;
 292         static tint TIMEOUT;
 293         static tint MIN_DEV;
 294         static tint MAX_SEND_INTERVAL;
 295         static tint LEDBAT_TARGET;
 296         static float LEDBAT_GAIN;
 297         static tint LEDBAT_DELAY_BIN;
 298         static bool SELF_CONN_OK;
 299
 300         const std::string id_string () const;
 301         /** A channel is "established" if had already sent and received packets. */
 302         bool        is_established () { return peer_channel_id_ && own_id_mentioned_; }
 303         FileTransfer& transfer() { return *transfer_; }
 304         HashTree&   file () { return transfer_->file(); }
 305         const Address& peer() const { return peer_; }
 306         tint ack_timeout () {
 307             return rtt_avg_ + std::max(dev_avg_,MIN_DEV)*4;
 308         }
 309         uint32_t    id () const { return id_; }
 310
 311         static int  DecodeID(int scrambled);
 312         static int  EncodeID(int unscrambled);
 313         static Channel* channel(int i) {
 314             return i<channels.size()?channels[i]:NULL;
 315         }
 316         static void CloseTransfer (FileTransfer* trans);
 317         static SOCKET default_socket() { return sockets[0]; }
 318
 319     protected:
 320         /** Channel id: index in the channel array. */
 321         uint32_t    id_;
 322         /**    Socket address of the peer. */
 323         Address     peer_;
 324         /**    The UDP socket fd. */
 325         SOCKET      socket_;
 326         /**    Descriptor of the file in question. */
 327         FileTransfer*    transfer_;
 328         /**    Peer channel id; zero if we are trying to open a channel. */
 329         uint32_t    peer_channel_id_;
 330         bool        own_id_mentioned_;
 331         /**    Peer's progress, based on acknowledgements. */
 332         binmap_t        ack_in_;
 333         /**    Last data received; needs to be acked immediately. */
 334         tintbin     data_in_;
 335         bin64_t     data_in_dbl_;
 336         /** The history of data sent and still unacknowledged. */
 337         tbqueue     data_out_;
 338         bin64_t     data_out_cap_;
 339         /** Index in the history array. */
 340         binmap_t        ack_out_;
 341         /**    Transmit schedule: in most cases filled with the peer's hints */
 342         tbqueue     hint_in_;
 343         /** Hints sent (to detect and reschedule ignored hints). */
 344         tbqueue     hint_out_;
 345         uint64_t    hint_out_size_;
 346         /** Types of messages the peer accepts. */
 347         uint64_t    cap_in_;
 348         /** For repeats. */
 349         //tint        last_send_time, last_recv_time;
 350         /** PEX progress */
 351         int         pex_out_;
 352         /** Smoothed averages for RTT, RTT deviation and data interarrival periods. */
 353         tint        rtt_avg_, dev_avg_, dip_avg_;
 354         tint        last_send_time_;
 355         tint        last_recv_time_;
 356         tint        last_data_out_time_;
 357         tint        last_data_in_time_;
 358         tint        last_loss_time_;
 359         tint        next_send_time_;
 360         tint        peer_send_time_;
 361         /** Congestion window; TODO: int, bytes. */
 362         float       cwnd_;
 363         /** Data sending interval. */
 364         tint        send_interval_;
 365         /** The congestion control strategy. */
 366         int         send_control_;
 367         /** Datagrams (not data) sent since last recv.    */
 368         int         sent_since_recv_;
 369         /** Recent acknowlegements for data previously sent.    */
 370         int         ack_rcvd_recent_;
 371         /** Recent non-acknowlegements (losses) of data previously sent.    */
 372         int         ack_not_rcvd_recent_;
 373         /** LEDBAT one-way delay machinery */
 374         tint        owd_min_bins_[4];
 375         int         owd_min_bin_;
 376         tint        owd_min_bin_start_;
 377         tint        owd_current_[4];
 378         int         owd_cur_bin_;
 379         /** Stats */
 380         int         dgrams_sent_;
 381         int         dgrams_rcvd_;
 382
 383         int         PeerBPS() const {
 384             return TINT_SEC / dip_avg_ * 1024;
 385         }
 386         /** Get a request for one packet from the queue of peer's requests. */
 387         bin64_t     DequeueHint();
 388         void        CleanDataOut (bin64_t acks_pos=bin64_t::NONE);
 389         void        CleanStaleHintOut();
 390         void        CleanHintOut(bin64_t pos);
 391         void        Reschedule();
 392
 393         static PeerSelector* peer_selector;
 394
 395         static SOCKET   sockets[8];
 396         static int      socket_count;
 397         static tint     last_tick;
 398         static tbheap   send_queue;
 399
 400         static Address  tracker;
 401         static std::vector<Channel*> channels;
 402
 403         friend int      Listen (Address addr);
 404         friend void     Shutdown (int sock_des);
 405         friend void     AddPeer (Address address, const Sha1Hash& root);
 406         friend void     SetTracker(const Address& tracker);
 407         friend int      Open (const char*, const Sha1Hash&) ; // FIXME
 408
 409     };
 410
 411
 412
 413     /*************** The top-level API ****************/
 414     /** Start listening a port. Returns socket descriptor. */
 415     int     Listen (Address addr);
 416     /** Run send/receive loop for the specified amount of time. */
 417     void    Loop (tint till);
 418     /** Stop listening to a port. */
 419     void    Shutdown (int sock_des=-1);
 420
 421     /** Open a file, start a transmission; fill it with content for a given root hash;
 422         in case the hash is omitted, the file is a fresh submit. */
 423     int     Open (const char* filename, const Sha1Hash& hash=Sha1Hash::ZERO) ;
 424     /** Get the root hash for the transmission. */
 425     const Sha1Hash& RootMerkleHash (int file) ;
 426     /** Close a file and a transmission. */
 427     void    Close (int fd) ;
 428     /** Add a possible peer which participares in a given transmission. In the case
 429         root hash is zero, the peer might be talked to regarding any transmission
 430         (likely, a tracker, cache or an archive). */
 431     void    AddPeer (Address address, const Sha1Hash& root=Sha1Hash::ZERO);
 432
 433     void    SetTracker(const Address& tracker);
 434
 435     /** Returns size of the file in bytes, 0 if unknown. Might be rounded up to a kilobyte
 436         before the transmission is complete. */
 437     uint64_t  Size (int fdes);
 438     /** Returns the amount of retrieved and verified data, in bytes.
 439         A 100% complete transmission has Size()==Complete(). */
 440     uint64_t  Complete (int fdes);
 441     bool      IsComplete (int fdes);
 442     /** Returns the number of bytes that are complete sequentially, starting from the
 443         beginning, till the first not-yet-retrieved packet. */
 444     uint64_t  SeqComplete (int fdes);
 445
 446
 447     //uint32_t Width (const tbinvec& v);
 448
 449
 450     /** Must be called by any client using the library */
 451     void LibraryInit(void);
 452
 453
 454 } // namespace end
 455
 456
 457 #endif