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 swift 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 SWIFT_H
  50 #define SWIFT_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         SWIFT_HANDSHAKE = 0,
 116         SWIFT_DATA = 1,
 117         SWIFT_ACK = 2,
 118         SWIFT_TS = 8,
 119         SWIFT_HINT = 3,
 120         SWIFT_HASH = 4,
 121         SWIFT_PEX_ADD = 5,
 122         SWIFT_PEX_RM = 6,
 123         SWIFT_SIGNED_HASH = 7,
 124         SWIFT_MSGTYPE_SENT = 8,
 125         SWIFT_MSGTYPE_RCVD = 9,
 126         SWIFT_MESSAGE_COUNT = 10
 127     } messageid_t;
 128
 129     class PiecePicker;
 130     class CongestionController;
 131     class PeerSelector;
 132
 133
 134     /** A class representing single file transfer. */
 135     class    FileTransfer {
 136
 137     public:
 138
 139         /** A constructor. Open/submit/retrieve a file.
 140          *  @param file_name    the name of the file
 141          *  @param root_hash    the root hash of the file; zero hash if the file
 142                                 is newly submitted */
 143         FileTransfer(const char *file_name, const Sha1Hash& root_hash=Sha1Hash::ZERO);
 144
 145         /**    Close everything. */
 146         ~FileTransfer();
 147
 148
 149         /** While we need to feed ACKs to every peer, we try (1) avoid
 150             unnecessary duplication and (2) keep minimum state. Thus,
 151             we use a rotating queue of bin completion events. */
 152         //bin64_t         RevealAck (uint64_t& offset);
 153         /** Rotating queue read for channels of this transmission. */
 154         int             RevealChannel (int& i);
 155
 156         /** Find transfer by the root hash. */
 157         static FileTransfer* Find (const Sha1Hash& hash);
 158         /** Find transfer by the file descriptor. */
 159         static FileTransfer* file (int fd) {
 160             return fd<files.size() ? files[fd] : NULL;
 161         }
 162
 163         /** The binmap for data already retrieved and checked. */
 164         binmap_t&           ack_out ()  { return file_.ack_out(); }
 165         /** Piece picking strategy used by this transfer. */
 166         PiecePicker&    picker () { return *picker_; }
 167         /** The number of channels working for this transfer. */
 168         int             channel_count () const { return hs_in_.size(); }
 169         /** Hash tree checked file; all the hashes and data are kept here. */
 170         HashTree&       file() { return file_; }
 171         /** File descriptor for the data file. */
 172         int             fd () const { return file_.file_descriptor(); }
 173         /** Root SHA1 hash of the transfer (and the data file). */
 174         const Sha1Hash& root_hash () const { return file_.root_hash(); }
 175
 176     private:
 177
 178         static std::vector<FileTransfer*> files;
 179
 180         HashTree        file_;
 181
 182         /** Piece picker strategy. */
 183         PiecePicker*    picker_;
 184
 185         /** Channels working for this transfer. */
 186         binqueue        hs_in_;
 187         int             hs_in_offset_;
 188         std::deque<Address> pex_in_;
 189
 190         /** Messages we are accepting.    */
 191         uint64_t        cap_out_;
 192
 193         tint            init_time_;
 194
 195     public:
 196         void            OnDataIn (bin64_t pos);
 197         void            OnPexIn (const Address& addr);
 198
 199         friend class Channel;
 200         friend uint64_t  Size (int fdes);
 201         friend bool      IsComplete (int fdes);
 202         friend uint64_t  Complete (int fdes);
 203         friend uint64_t  SeqComplete (int fdes);
 204         friend int     Open (const char* filename, const Sha1Hash& hash) ;
 205         friend void    Close (int fd) ;
 206     };
 207
 208
 209     /** PiecePicker implements some strategy of choosing (picking) what
 210         to request next, given the possible range of choices:
 211         data acknowledged by the peer minus data already retrieved.
 212         May pick sequentially, do rarest first or in some other way. */
 213     class PiecePicker {
 214     public:
 215         virtual void Randomize (uint64_t twist) = 0;
 216         /** The piece picking method itself.
 217          *  @param  offered     the daata acknowledged by the peer
 218          *  @param  max_width   maximum number of packets to ask for
 219          *  @param  expires     (not used currently) when to consider request expired
 220          *  @return             the bin number to request */
 221         virtual bin64_t Pick (binmap_t& offered, uint64_t max_width, tint expires) = 0;
 222         virtual ~PiecePicker() {}
 223     };
 224
 225
 226     class PeerSelector {
 227     public:
 228         virtual void AddPeer (const Address& addr, const Sha1Hash& root) = 0;
 229         virtual Address GetPeer (const Sha1Hash& for_root) = 0;
 230     };
 231
 232
 233     class DataStorer {
 234     public:
 235         DataStorer (const Sha1Hash& id, size_t size);
 236         virtual size_t    ReadData (bin64_t pos,uint8_t** buf) = 0;
 237         virtual size_t    WriteData (bin64_t pos, uint8_t* buf, size_t len) = 0;
 238     };
 239
 240
 241     /**    swift channel's "control block"; channels loosely correspond to TCP
 242         connections or FTP sessions; one channel is created for one file
 243         being transferred between two peers. As we don't need buffers and
 244         lots of other TCP stuff, sizeof(Channel+members) must be below 1K.
 245         Normally, API users do not deal with this class. */
 246     class Channel {
 247     public:
 248         Channel    (FileTransfer* file, int socket=-1, Address peer=Address());
 249         ~Channel();
 250
 251         typedef enum {
 252             KEEP_ALIVE_CONTROL,
 253             PING_PONG_CONTROL,
 254             SLOW_START_CONTROL,
 255             AIMD_CONTROL,
 256             LEDBAT_CONTROL,
 257             CLOSE_CONTROL
 258         } send_control_t;
 259
 260         static const char* SEND_CONTROL_MODES[];
 261
 262         static Channel*
 263                     RecvDatagram (int socket);
 264         static void Loop (tint till);
 265
 266         void        Recv (Datagram& dgram);
 267         void        Send ();
 268         void        Close ();
 269
 270         void        OnAck (Datagram& dgram);
 271         void        OnTs (Datagram& dgram);
 272         bin64_t     OnData (Datagram& dgram);
 273         void        OnHint (Datagram& dgram);
 274         void        OnHash (Datagram& dgram);
 275         void        OnPex (Datagram& dgram);
 276         void        OnHandshake (Datagram& dgram);
 277         void        AddHandshake (Datagram& dgram);
 278         bin64_t     AddData (Datagram& dgram);
 279         void        AddAck (Datagram& dgram);
 280         void        AddTs (Datagram& dgram);
 281         void        AddHint (Datagram& dgram);
 282         void        AddUncleHashes (Datagram& dgram, bin64_t pos);
 283         void        AddPeakHashes (Datagram& dgram);
 284         void        AddPex (Datagram& dgram);
 285
 286         void        BackOffOnLosses (float ratio=0.5);
 287         tint        SwitchSendControl (int control_mode);
 288         tint        NextSendTime ();
 289         tint        KeepAliveNextSendTime ();
 290         tint        PingPongNextSendTime ();
 291         tint        CwndRateNextSendTime ();
 292         tint        SlowStartNextSendTime ();
 293         tint        AimdNextSendTime ();
 294         tint        LedbatNextSendTime ();
 295
 296         static int  MAX_REORDERING;
 297         static tint TIMEOUT;
 298         static tint MIN_DEV;
 299         static tint MAX_SEND_INTERVAL;
 300         static tint LEDBAT_TARGET;
 301         static float LEDBAT_GAIN;
 302         static tint LEDBAT_DELAY_BIN;
 303         static bool SELF_CONN_OK;
 304         static tint MAX_POSSIBLE_RTT;
 305
 306         const std::string id_string () const;
 307         /** A channel is "established" if had already sent and received packets. */
 308         bool        is_established () { return peer_channel_id_ && own_id_mentioned_; }
 309         FileTransfer& transfer() { return *transfer_; }
 310         HashTree&   file () { return transfer_->file(); }
 311         const Address& peer() const { return peer_; }
 312         tint ack_timeout () {
 313             return std::min(30*TINT_SEC,rtt_avg_ + std::max(dev_avg_,MIN_DEV)*4);
 314         }
 315         uint32_t    id () const { return id_; }
 316
 317         static int  DecodeID(int scrambled);
 318         static int  EncodeID(int unscrambled);
 319         static Channel* channel(int i) {
 320             return i<channels.size()?channels[i]:NULL;
 321         }
 322         static void CloseTransfer (FileTransfer* trans);
 323         static SOCKET default_socket() { return sockets[0]; }
 324
 325     protected:
 326         /** Channel id: index in the channel array. */
 327         uint32_t    id_;
 328         /**    Socket address of the peer. */
 329         Address     peer_;
 330         /**    The UDP socket fd. */
 331         SOCKET      socket_;
 332         /**    Descriptor of the file in question. */
 333         FileTransfer*    transfer_;
 334         /**    Peer channel id; zero if we are trying to open a channel. */
 335         uint32_t    peer_channel_id_;
 336         bool        own_id_mentioned_;
 337         /**    Peer's progress, based on acknowledgements. */
 338         binmap_t        ack_in_;
 339         /**    Last data received; needs to be acked immediately. */
 340         tintbin     data_in_;
 341         bin64_t     data_in_dbl_;
 342         /** The history of data sent and still unacknowledged. */
 343         tbqueue     data_out_;
 344         /** Timeouted data (potentially to be retransmitted). */
 345         tbqueue     data_out_tmo_;
 346         bin64_t     data_out_cap_;
 347         /** Index in the history array. */
 348         binmap_t        ack_out_;
 349         /**    Transmit schedule: in most cases filled with the peer's hints */
 350         tbqueue     hint_in_;
 351         /** Hints sent (to detect and reschedule ignored hints). */
 352         tbqueue     hint_out_;
 353         uint64_t    hint_out_size_;
 354         /** Types of messages the peer accepts. */
 355         uint64_t    cap_in_;
 356         /** For repeats. */
 357         //tint        last_send_time, last_recv_time;
 358         /** PEX progress */
 359         int         pex_out_;
 360         /** Smoothed averages for RTT, RTT deviation and data interarrival periods. */
 361         tint        rtt_avg_, dev_avg_, dip_avg_;
 362         tint        last_send_time_;
 363         tint        last_recv_time_;
 364         tint        last_data_out_time_;
 365         tint        last_data_in_time_;
 366         tint        last_loss_time_;
 367         tint        next_send_time_;
 368         tint        peer_send_time_;
 369         /** Congestion window; TODO: int, bytes. */
 370         float       cwnd_;
 371         /** Data sending interval. */
 372         tint        send_interval_;
 373         /** The congestion control strategy. */
 374         int         send_control_;
 375         /** Datagrams (not data) sent since last recv.    */
 376         int         sent_since_recv_;
 377         /** Recent acknowlegements for data previously sent.    */
 378         int         ack_rcvd_recent_;
 379         /** Recent non-acknowlegements (losses) of data previously sent.    */
 380         int         ack_not_rcvd_recent_;
 381         /** LEDBAT one-way delay machinery */
 382         tint        owd_min_bins_[4];
 383         int         owd_min_bin_;
 384         tint        owd_min_bin_start_;
 385         tint        owd_current_[4];
 386         int         owd_cur_bin_;
 387         /** Stats */
 388         int         dgrams_sent_;
 389         int         dgrams_rcvd_;
 390
 391         int         PeerBPS() const {
 392             return TINT_SEC / dip_avg_ * 1024;
 393         }
 394         /** Get a request for one packet from the queue of peer's requests. */
 395         bin64_t     DequeueHint();
 396         void        CleanDataOut (bin64_t acks_pos=bin64_t::NONE);
 397         void        CleanStaleHintOut();
 398         void        CleanHintOut(bin64_t pos);
 399         void        Reschedule();
 400
 401         static PeerSelector* peer_selector;
 402
 403         static SOCKET   sockets[8];
 404         static int      socket_count;
 405         static tint     last_tick;
 406         static tbheap   send_queue;
 407
 408         static Address  tracker;
 409         static std::vector<Channel*> channels;
 410
 411         friend int      Listen (Address addr);
 412         friend void     Shutdown (int sock_des);
 413         friend void     AddPeer (Address address, const Sha1Hash& root);
 414         friend void     SetTracker(const Address& tracker);
 415         friend int      Open (const char*, const Sha1Hash&) ; // FIXME
 416
 417     };
 418
 419
 420
 421     /*************** The top-level API ****************/
 422     /** Start listening a port. Returns socket descriptor. */
 423     int     Listen (Address addr);
 424     /** Run send/receive loop for the specified amount of time. */
 425     void    Loop (tint till);
 426     /** Stop listening to a port. */
 427     void    Shutdown (int sock_des=-1);
 428
 429     /** Open a file, start a transmission; fill it with content for a given root hash;
 430         in case the hash is omitted, the file is a fresh submit. */
 431     int     Open (const char* filename, const Sha1Hash& hash=Sha1Hash::ZERO) ;
 432     /** Get the root hash for the transmission. */
 433     const Sha1Hash& RootMerkleHash (int file) ;
 434     /** Close a file and a transmission. */
 435     void    Close (int fd) ;
 436     /** Add a possible peer which participares in a given transmission. In the case
 437         root hash is zero, the peer might be talked to regarding any transmission
 438         (likely, a tracker, cache or an archive). */
 439     void    AddPeer (Address address, const Sha1Hash& root=Sha1Hash::ZERO);
 440
 441     void    SetTracker(const Address& tracker);
 442
 443     /** Returns size of the file in bytes, 0 if unknown. Might be rounded up to a kilobyte
 444         before the transmission is complete. */
 445     uint64_t  Size (int fdes);
 446     /** Returns the amount of retrieved and verified data, in bytes.
 447         A 100% complete transmission has Size()==Complete(). */
 448     uint64_t  Complete (int fdes);
 449     bool      IsComplete (int fdes);
 450     /** Returns the number of bytes that are complete sequentially, starting from the
 451         beginning, till the first not-yet-retrieved packet. */
 452     uint64_t  SeqComplete (int fdes);
 453
 454
 455     //uint32_t Width (const tbinvec& v);
 456
 457
 458     /** Must be called by any client using the library */
 459     void LibraryInit(void);
 460
 461
 462 } // namespace end
 463
 464
 465 #endif