From f021a05d4b19202b63042741f1a1b19cf6ee8f13 Mon Sep 17 00:00:00 2001 From: Victor Grishchenko Date: Fri, 15 Jan 2010 19:24:03 +0100 Subject: [PATCH] Commented everything TODO: channel is still a struct --- bin64.h | 32 +++++++++++++++++++++++++++++++- bins.h | 42 +++++++++++++++++++++++++++++++++++++++--- compat.h | 3 ++- datagram.h | 25 +++++++++++++++++++++---- hashtree.h | 32 ++++++++++++++++++++++++++++++-- p2tp.h | 9 ++++++++- send_control.cpp | 2 +- sendrecv.cpp | 8 ++++---- sha1.cpp | 1 + sha1.h | 1 + transfer.cpp | 2 +- 11 files changed, 139 insertions(+), 18 deletions(-) diff --git a/bin64.h b/bin64.h index c2193ad..1ba8532 100644 --- a/bin64.h +++ b/bin64.h @@ -1,3 +1,11 @@ +/* + * bin64.h + * bin numbers (binaty tree enumeration/navigation) + * + * Created by Victor Grishchenko on ??/09/09 in Karlovy Vary + * Copyright 2009 Delft University of Technology. All rights reserved. + * + */ #ifndef BIN64_H #define BIN64_H #include @@ -15,7 +23,11 @@ Bin numbers in the tail111 encoding: meaningless bits in the tail are set to 0111...11, while the head denotes the offset. Thus, 1101 is the bin - at layer 1, offset 3 (i.e. fourth). */ + at layer 1, offset 3 (i.e. fourth). + Obviously, bins form a binary tree. All navigation + is made in terms of binary trees: left, right, + sibling, parent, etc. + */ struct bin64_t { uint64_t v; static const uint64_t NONE; @@ -44,6 +56,7 @@ struct bin64_t { return (tail_bits()+1)>>1; } + /** Get the sibling interval in the binary tree. */ bin64_t sibling () const { // if (v==ALL) return NONE; return bin64_t(v^(tail_bit()<<1)); @@ -66,14 +79,17 @@ struct bin64_t { return r; } + /** Get the bin's offset in base units, i.e. 4 for (1,2). */ uint64_t base_offset () const { return (v&~(tail_bits()))>>1; } + /** Get the bin's offset at its own layer, e.g. 2 for (1,2). */ uint64_t offset () const { return v >> (layer()+1); } + /** Get a child bin; either right(true) or left(false). */ bin64_t to (bool right) const { if (!(v&1)) return NONE; @@ -83,14 +99,17 @@ struct bin64_t { return bin64_t(v^tb); } + /** Get the left child bin. */ bin64_t left () const { return to(false); } + /** Get the right child bin. */ bin64_t right () const { return to(true); } + /** Check whether this bin is within the specified bin. */ bool within (bin64_t maybe_asc) { if (maybe_asc==bin64_t::NONE) return false; @@ -110,21 +129,27 @@ struct bin64_t { return right(); } + /** Twist/untwist a bin number according to the mask. */ bin64_t twisted (uint64_t mask) const { return bin64_t( v ^ ((mask<<1)&~tail_bits()) ); } + /** Get the paretn bin. */ bin64_t parent () const { uint64_t tbs = tail_bits(), ntbs = (tbs+1)|tbs; return bin64_t( (v&~ntbs) | tbs ); } + /** Check whether this bin is the left sibling. */ bool is_left () const { uint64_t tb = tail_bit(); return !(v&(tb<<1)); } + + /** Check whether this bin is the right sibling. */ bool is_right() const { return !is_left(); } + /** Get the leftmost basic bin within this bin. */ bin64_t left_foot () const { if (v==NONE) return NONE; @@ -139,10 +164,15 @@ struct bin64_t { /** Depth-first in-order binary tree traversal. */ bin64_t next_dfsio (uint8_t floor); + /** Return the number of basci bins within this bin. */ bin64_t width () const { return (tail_bits()+1)>>1; } + /** Get the standard-form null-terminated string + representation of this bin, e.g. "(2,1)". + The string is statically allocated, must + not be reused or released. */ const char* str () const; /** The array must have 64 cells, as it is the max diff --git a/bins.h b/bins.h index 5a8debd..8d05680 100644 --- a/bins.h +++ b/bins.h @@ -1,6 +1,6 @@ /* * sbit.cpp - * serp++ + * binmap, a hybrid of bitmap and binary tree * * Created by Victor Grishchenko on 3/28/09. * Copyright 2009 Delft University of Technology. All rights reserved. @@ -10,51 +10,87 @@ #define BINS_H #include "bin64.h" -/** A binmap covering 2^64 range. Complexity limit: 100+200LoC */ +/** A binmap covering 2^64 range. Binmap is a hybrid of a bitmap (aka + bit vector) and a binary tree. The key ability of a binmap is + the aggregation of solid (all-0 or all-1) ranges. */ class bins { public: + /** Need a 3-valued logic as a range might be either all-0 or all-1 + or some mix. In fact, any value different from 0x0 or 0xffff + must be interpreted as MIXED. + All read/write operations on a binmap are made in terms of + aligned binary intervals (bins). + */ typedef enum { FILLED=0xffff, EMPTY=0x0000, MIXED=0x5555 } fill_t; static const int NOJOIN; bins(); + /** Copying constructor. */ bins(const bins& b); + /** Get value for the bin. */ uint16_t get (bin64_t bin); + /** Set value for the bin. */ void set (bin64_t bin, fill_t val=FILLED); + /** Copy a range from another binmap. */ void copy_range (bins& origin, bin64_t range); + /** Find the leftmost bin within the specified range which is + either filled or empty. */ bin64_t find (const bin64_t range, fill_t seek=EMPTY) ; + /** Find the leftmost bin within the specified range which is + either filled or empty. Bins set to 1 in the filter binmap cannot + be returned. In fact, this is an incremental bitwise op. */ bin64_t find_filtered (bins& filter, bin64_t range, fill_t seek=EMPTY) ; - void remove (bins& b); + /** Bitwise SUB; any bins set to one in the filter binmap should + be set to 0 in this binmap. */ + void remove (bins& filter); void dump(const char* note); + /** Represent the binmap as a sequence of 0 and 1 stripes; for each + new stripe only the starting offset is given. The first stripe + is supposed to be empty (if the (0,0) bin is actually filled, + the next stripe will also start at 0). */ uint64_t* get_stripes (int& count); + /** Return the number of cells allocated in the binmap. */ uint32_t size() { return cells_allocated; } uint64_t seq_length (); + /** Return the topmost solid bin which covers the specified bin. */ bin64_t cover(bin64_t val); uint64_t mass (); + /** Return true if the range is solid (either all-0 or 1). If val is + specified, the interval must be both solid and filled/empty, + depending on the value. */ bool is_solid (bin64_t range=bin64_t::ALL, fill_t val=MIXED) ; + /** Whether range/bin is empty. */ bool is_empty (bin64_t range=bin64_t::ALL) { return is_solid(range,EMPTY); } + /** Whether range/bin is filled. */ bool is_filled (bin64_t range=bin64_t::ALL) { return is_solid(range,FILLED); } + /** Clear everything, empty all bins. */ void clear (); + /** Returns whether the int is mixed (not all-1 or all-0). */ static bool is_mixed (uint16_t val) { return val!=EMPTY && val!=FILLED; } + /** Returns whether the int is solid (0x0 or 0xffff). */ static bool is_solid (uint16_t val) { return val==EMPTY || val==FILLED; } + /** Twisting is some generalization of XOR. For every 1-bit in the mask, + the respective layer of the binary tree is flipped, i.e. left and + right change places. Twisting is mostly needed for randomization. */ void twist (uint64_t mask); private: diff --git a/compat.h b/compat.h index 34a4438..1bfeedf 100644 --- a/compat.h +++ b/compat.h @@ -1,6 +1,6 @@ /* * compat.h - * p2tp + * compatibility wrappers * * Created by Arno Bakker, Victor Grishchenko * Copyright 2009 Delft University of Technology. All rights reserved. @@ -35,6 +35,7 @@ namespace p2tp { +/** tint is the time integer type; microsecond-precise. */ typedef int64_t tint; #define TINT_HOUR ((tint)1000000*60*60) #define TINT_MIN ((tint)1000000*60) diff --git a/datagram.h b/datagram.h index 0988358..6866be1 100644 --- a/datagram.h +++ b/datagram.h @@ -1,6 +1,6 @@ /* * datagram.h - * serp++ + * nice IPv4 UDP wrappers * * Created by Victor Grishchenko, Arno Bakker on 3/9/09. * Copyright 2009 Delft University of Technology. All rights reserved. @@ -45,6 +45,7 @@ namespace p2tp { #endif +/** IPv4 address, just a nice wrapping around struct sockaddr_in. */ struct Address { struct sockaddr_in addr; static uint32_t LOCALHOST; @@ -105,36 +106,52 @@ struct Address { }; -struct Datagram { +/** UDP datagram class, a nice wrapping around sendto/recvfrom/select. + Reading/writing from/to a datagram is done in a FIFO (deque) fashion: + written data is appended to the tail (push) while read data is + taken from the "head" of the buffer. */ +class Datagram { Address addr; SOCKET sock; int offset, length; uint8_t buf[MAXDGRAMSZ*2]; +public: + + /** bind to the address */ static SOCKET Bind(Address address); + /** close the port */ static void Close(int port); + /** the current time */ static tint Time(); + /** wait till one of the sockets has some io to do; usec is the timeout */ static SOCKET Wait (int sockcnt, SOCKET* sockets, tint usec=0); static tint now, epoch, start; static uint64_t dgrams_up, dgrams_down, bytes_up, bytes_down; + /** This constructor is normally used to SEND something to the address. */ Datagram (SOCKET socket, const Address addr_) : addr(addr_), offset(0), length(0), sock(socket) {} + /** This constructor is normally used to RECEIVE something at the socket. */ Datagram (SOCKET socket) : offset(0), length(0), sock(socket) { } + /** space remaining */ int space () const { return MAXDGRAMSZ-length; } + /** size of the data (not counting UDP etc headers) */ int size() const { return length-offset; } std::string str() const { return std::string((char*)buf+offset,size()); } const uint8_t* operator * () const { return buf+offset; } - + const Address& address () const { return addr; } + /** Append some data at the back */ int Push (const uint8_t* data, int l) { // scatter-gather one day int toc = l ACK is sent. */ bool OfferData (bin64_t bin, const char* data, size_t length); - /** Not implemented yet. */ + /** For live streaming. Not implemented yet. */ int AppendData (char* data, int length) ; int file_descriptor () const { return fd_; } + /** Returns the number of peaks (read on peak hashes). */ int peak_count () const { return peak_count_; } + /** Returns the i-th peak's bin number. */ bin64_t peak (int i) const { return peaks_[i]; } + /** Returns peak hash #i. */ const Sha1Hash& peak_hash (int i) const { return peak_hashes_[i]; } + /** Return the peak bin the given bin belongs to. */ bin64_t peak_for (bin64_t pos) const; + /** Return a (Merkle) hash for the given bin. */ const Sha1Hash& hash (bin64_t pos) const {return hashes_[pos];} + /** Give the root hash, which is effectively an identifier of this file. */ const Sha1Hash& root_hash () const { return root_hash_; } + /** Get file size, in bytes. */ uint64_t size () const { return size_; } + /** Get file size in packets (in kilobytes, rounded up). */ uint64_t packet_size () const { return sizek_; } + /** Number of bytes retrieved and checked. */ uint64_t complete () const { return complete_; } + /** Number of packets retrieved and checked. */ uint64_t packets_complete () const { return completek_; } + /** The number of bytes completed sequentially, i.e. from the beginning of + the file, uninterrupted. */ uint64_t seq_complete () ; + /** Whether the file is complete. */ bool is_complete () { return size_ && complete_==size_; } + /** The binmap of complete packets. */ bins& ack_out () { return ack_out_; } ~HashTree (); diff --git a/p2tp.h b/p2tp.h index 8882aca..df26eef 100644 --- a/p2tp.h +++ b/p2tp.h @@ -1,6 +1,6 @@ /* * p2tp.h - * serp++ + * the main header file for libswift, normally you should only read this one * * Created by Victor Grishchenko on 3/6/09. * Copyright 2009 Delft University of Technology. All rights reserved. @@ -66,6 +66,10 @@ Messages namespace p2tp { #define NOW Datagram::now + + /** tintbin is basically a pair plus some nice operators. + Most frequently used in different queues (acknowledgements, requests, + etc). */ struct tintbin { tint time; bin64_t bin; @@ -85,6 +89,7 @@ namespace p2tp { typedef std::deque binqueue; typedef Address Address; + /** A heap (priority queue) for timestamped bin numbers (tintbins). */ class tbheap { tbqueue data_; public: @@ -105,6 +110,7 @@ namespace p2tp { } }; + /** swift protocol message types; these are used on the wire. */ typedef enum { P2TP_HANDSHAKE = 0, P2TP_DATA = 1, @@ -122,6 +128,7 @@ namespace p2tp { class PeerSelector; + /** A class representing single file transfer. */ class FileTransfer { public: diff --git a/send_control.cpp b/send_control.cpp index a14d65f..a7d4167 100644 --- a/send_control.cpp +++ b/send_control.cpp @@ -1,6 +1,6 @@ /* * send_control.cpp - * p2tp + * congestion control logic for the swift protocol * * Created by Victor Grishchenko on 12/10/09. * Copyright 2009 Delft University of Technology. All rights reserved. diff --git a/sendrecv.cpp b/sendrecv.cpp index 434d848..e651eb4 100644 --- a/sendrecv.cpp +++ b/sendrecv.cpp @@ -1,6 +1,6 @@ /* - * datasendrecv.cpp - * serp++ + * sendrecv.cpp + * most of the swift's state machine * * Created by Victor Grishchenko on 3/6/09. * Copyright 2009 Delft University of Technology. All rights reserved. @@ -484,7 +484,7 @@ void Channel::AddPex (Datagram& dgram) { Channel* Channel::RecvDatagram (int socket) { Datagram data(socket); data.Recv(); - Address& addr = data.addr; + const Address& addr = data.address(); #define return_log(...) { eprintf(__VA_ARGS__); return NULL; } if (data.size()<4) return_log("datagram shorter than 4 bytes %s\n",addr.str()); @@ -506,7 +506,7 @@ Channel* Channel::RecvDatagram (int socket) { return_log ("hash %s unknown, no such file %s\n",hash.hex().c_str(),addr.str()); dprintf("%s #0 -hash ALL %s\n",tintstr(),hash.hex().c_str()); for(binqueue::iterator i=file->hs_in_.begin(); i!=file->hs_in_.end(); i++) - if (channels[*i] && channels[*i]->peer_==data.addr && + if (channels[*i] && channels[*i]->peer_==data.address() && channels[*i]->last_recv_time_>NOW-TINT_SEC*2) return_log("have a channel already to %s\n",addr.str()); channel = new Channel(file, socket, data.address()); diff --git a/sha1.cpp b/sha1.cpp index 748a8e7..e465f53 100644 --- a/sha1.cpp +++ b/sha1.cpp @@ -1,3 +1,4 @@ +// licensed under the GPL v2 as part of the git project http://git-scm.com/ /* * SHA1 routine optimized to do word accesses rather than byte accesses, * and to avoid unnecessary copies into the context array. diff --git a/sha1.h b/sha1.h index 844ea53..3b804b0 100644 --- a/sha1.h +++ b/sha1.h @@ -1,3 +1,4 @@ +// licensed under the GPL v2 as part of the git project http://git-scm.com/ /* * SHA1 routine optimized to do word accesses rather than byte accesses, * and to avoid unnecessary copies into the context array. diff --git a/transfer.cpp b/transfer.cpp index 88c8690..43ff713 100644 --- a/transfer.cpp +++ b/transfer.cpp @@ -1,6 +1,6 @@ /* * transfer.cpp - * p2tp + * some transfer-scope code * * Created by Victor Grishchenko on 10/6/09. * Copyright 2009 Delft University of Technology. All rights reserved. -- 2.20.1