From e9a0cb989936ff1fac2fc4f9cfa910bb0467bdc4 Mon Sep 17 00:00:00 2001
From: victor <victor@e16421f0-f15b-0410-abcd-98678b794739>
Date: Fri, 16 Oct 2009 06:43:28 +0000
Subject: [PATCH] right uncle sequence

git-svn-id: https://ttuki.vtt.fi/svn/p2p-next/TUD/p2tp/trunk@425 e16421f0-f15b-0410-abcd-98678b794739
---
 p2tp.h                 | 69 ++++++++++++++++++++++++++++++------------
 tests/transfertest.cpp | 11 ++++---
 transfer.cpp           | 42 ++++++++++++++-----------
 3 files changed, 80 insertions(+), 42 deletions(-)

diff --git a/p2tp.h b/p2tp.h
index 122a469..94a356c 100644
--- a/p2tp.h
+++ b/p2tp.h
@@ -58,7 +58,13 @@ Messages
 
 namespace p2tp {
 
-    typedef std::pair<tint,bin64_t> tintbin;
+    struct tintbin {
+        tint    time;
+        bin64_t bin;
+        tintbin(const tintbin& b) : time(b.time), bin(b.bin) {}
+        tintbin() : time(0), bin(bin64_t::NONE) {}
+        tintbin(tint time_, bin64_t bin_) : time(time_), bin(bin_) {}
+    };
     
 	typedef std::deque<tintbin> tbqueue;
     typedef std::deque<bin64_t> binqueue;
@@ -67,7 +73,7 @@ namespace p2tp {
 		P2TP_HANDSHAKE = 0, 
 		P2TP_DATA = 1, 
 		P2TP_ACK = 2, 
-		P2TP_ACKTS = 8, 
+		P2TP_ACK_TS = 8, 
 		P2TP_HINT = 3, 
 		P2TP_HASH = 4, 
 		P2TP_PEX_ADD = 5,
@@ -99,7 +105,20 @@ namespace p2tp {
         bool            OfferData (bin64_t bin, uint8_t* data, size_t length);
         
 		static FileTransfer* Find (const Sha1Hash& hash);
-		static FileTransfer* file (int fd) { return fd<files.size() ? files[fd] : NULL; }
+		static FileTransfer* file (int fd) { 
+            return fd<files.size() ? files[fd] : NULL; 
+        }
+        
+        int             GetPeakCount () const { return peak_count; }
+        bin64_t         GetPeak (int i) const { return peaks[i]; }
+        const Sha1Hash& GetPeakHash (int i) const { return peak_hashes[i]; }
+        bin64_t         GetPeakFor (bin64_t pos) const;
+        const Sha1Hash& GetHash (bin64_t pos) const { 
+            assert(pos<sizek*2);
+            return hashes[pos];
+        }
+        const Sha1Hash& GetRootHash () const { return root_hash; }
+        
         
 		friend int      Open (const char* filename);
 		friend int      Open (const Sha1Hash& hash, const char* filename);
@@ -124,7 +143,7 @@ namespace p2tp {
 		/**	A map for all packets obtained and succesfully checked. */
 		bins			ack_out;
 		/**	History of bin retrieval. */
-		binqueue		ack_history;
+		binqueue		data_in;
         /** Piece picker strategy. */
         PiecePicker*    picker;
 		/** File for keeping the Merkle hash tree. */
@@ -172,7 +191,7 @@ namespace p2tp {
         int     peer_cwnd;
         virtual void    OnDataSent(bin64_t b) = 0;
         virtual void    OnDataRecvd(bin64_t b) = 0;
-        virtual void    OnAckRcvd(bin64_t b, tint peer_stamp) = 0;
+        virtual void    OnAckRcvd(const tintbin& tsack) = 0;
 		virtual         ~CongestionController() = 0;
 	};
     
@@ -185,9 +204,10 @@ namespace p2tp {
     
     class PeerSelector {
     public:
-        virtual void    PeerKnown (const Sha1Hash& root, struct sockaddr_in& addr) = 0;
-        virtual struct sockaddr_in 
-                        GetPeer (const Sha1Hash& for_root) = 0;
+        virtual void    PeerKnown 
+            (const Sha1Hash& root, struct sockaddr_in& addr) = 0;
+        virtual struct sockaddr_in GetPeer 
+            (const Sha1Hash& for_root) = 0;
     };
     
     class DataStorer {
@@ -213,26 +233,32 @@ namespace p2tp {
 		static void	Recv (int socket);
 		void		Recv (Datagram& dgram);
 		tint		Send ();
-		tint		SendSomething ();
-		void		SendHandshake ();
 
 		void		OnAck (Datagram& dgram);
+		void		OnAckTs (Datagram& dgram);
 		void		OnData (Datagram& dgram);
 		void		OnHint (Datagram& dgram);
 		void		OnHash (Datagram& dgram);
+		void		OnPex (Datagram& dgram);
 		
 		void		AddHandshake (Datagram& dgram);
-		bin 		AddData (Datagram& dgram);
+		bin64_t		AddData (Datagram& dgram);
 		void		AddAck (Datagram& dgram);
 		void		AddHint (Datagram& dgram);
-		void		AddUncleHashes (Datagram& dgram, bin pos);
+		void		AddUncleHashes (Datagram& dgram, bin64_t pos);
 		void		AddPeakHashes (Datagram& dgram);
 
-		void		CleanStaleHints();
-		
+        const std::string id_string () const;
+        /** A channel is "established" if had already sent and received packets. */
+        bool        is_established () { return peer_channel_id && own_id_mentioned; }
+        
 		static int DecodeID(int scrambled);
 		static int EncodeID(int unscrambled);
-		static Channel* channel(int i) {return i<channels.size()?channels[i]:NULL;}
+		static Channel* channel(int i) {
+            return i<channels.size()?channels[i]:NULL;
+        }
+        
+        FileTransfer& file() { return *file_; }
 		
 		/*friend int Connect (int fd, int sock, 
 							const struct sockaddr_in& addr, uint32_t peerch=0);
@@ -248,17 +274,18 @@ namespace p2tp {
 		/**	The UDP socket fd. */
 		int			socket;
 		/**	Descriptor of the file in question. */
-		FileTransfer*	file;
+		FileTransfer*	file_;
 		/**	Peer channel id; zero if we are trying to open a channel. */
 		uint32_t	peer_channel_id;
+        bool        own_id_mentioned;
 		/**	Peer's progress, based on acknowledgements. */
 		bins		ack_in;
 		/**	Last data received; needs to be acked immediately. */
-		bin64_t		data_in;
+		tintbin		data_in_;
         /** Index in the history array. */
-		int			ack_out;
+		uint32_t	ack_out_;
 		/**	Transmit schedule: in most cases filled with the peer's hints */
-		tbqueue		hint_in;
+		binqueue    hint_in;
 		/** Hints sent (to detect and reschedule ignored hints). */
 		tbqueue		hint_out;
 		/** The congestion control strategy. */
@@ -266,6 +293,10 @@ namespace p2tp {
         /** For repeats. */
 		tint		last_send_time, last_recv_time;
         
+        /** Get a rewuest for one packet from the queue of peer's requests. */
+        bin64_t		DequeueHint();
+        void        CleanStaleHints();
+        
         static PeerSelector* peer_selector;
         
 		static int  MAX_REORDERING;
diff --git a/tests/transfertest.cpp b/tests/transfertest.cpp
index 24683e6..67c6163 100644
--- a/tests/transfertest.cpp
+++ b/tests/transfertest.cpp
@@ -58,16 +58,14 @@ TEST(TransferTest,TransferFile) {
     //           ABCD            E000
     //     AB         CD       E0    0
     //  AAAA BBBB  CCCC DDDD  E  0  0  0
-    leech->OfferHash(bin64_t(1,0), seed->hashes[bin64_t(1,0)]);
+    // calculated leech->OfferHash(bin64_t(1,0), seed->hashes[bin64_t(1,0)]);
     leech->OfferHash(bin64_t(1,1), seed->hashes[bin64_t(1,1)]);
     for (int i=0; i<5; i++) {
-        if (i==2) {
+        if (i==2) { // now: stop, save, start
             delete leech;
             FileTransfer::instance = 1;
             leech = new FileTransfer(seed->root_hash,"copy");
             EXPECT_EQ(2,leech->completek);
-            //leech->OfferHash(bin64_t(1,0), seed->hashes[bin64_t(1,0)]);
-            //leech->OfferHash(bin64_t(1,1), seed->hashes[bin64_t(1,1)]);
         }
         bin64_t next = leech->picker->Pick(seed->ack_out,0);
         ASSERT_NE(bin64_t::NONE,next);
@@ -75,6 +73,10 @@ TEST(TransferTest,TransferFile) {
         size_t len = pread(seed->fd,buf,1024,next.base_offset()<<10); // FIXME TEST FOR ERROR
         bin64_t sibling = next.sibling();
         leech->OfferHash(sibling, seed->hashes[sibling]); // i=4 => out of bounds
+        uint8_t memo = *buf;
+        *buf = 'z';
+        EXPECT_FALSE(leech->OfferData(next, buf, len));
+        *buf = memo;
         EXPECT_TRUE(leech->OfferData(next, buf, len));
     }
     EXPECT_EQ(4100,leech->size);
@@ -86,7 +88,6 @@ TEST(TransferTest,TransferFile) {
 /*
  FIXME
  - always rehashes (even fresh files)
- - different heights => bins::remove is buggy
  */
 
 int main (int argc, char** argv) {
diff --git a/transfer.cpp b/transfer.cpp
index a260842..8f2e9b8 100644
--- a/transfer.cpp
+++ b/transfer.cpp
@@ -20,6 +20,7 @@ int FileTransfer::instance = 0;
 
 #include "ext/seq_picker.cpp"
 
+// FIXME: separate Bootstrap() and Download(), then Size(), Progress(), SeqProgress()
 
 FileTransfer::FileTransfer (const Sha1Hash& _root_hash, const char* filename) :
     root_hash(_root_hash), fd(0), hashfd(0), dry_run(false), 
@@ -150,9 +151,14 @@ void            FileTransfer::Submit () {
 void            FileTransfer::OfferHash (bin64_t pos, const Sha1Hash& hash) {    
 	if (!size)  // only peak hashes are accepted at this point
 		return OfferPeak(pos,hash);
-	if (pos>=sizek*2)
-		return;
-    if (ack_out.get(pos)!=bins::EMPTY)
+    int pi=0;
+    while (pi<peak_count && !pos.within(peaks[pi]))
+        pi++;
+    if (pi==peak_count)
+        return;
+    if (pos==peaks[pi] && hash!=peak_hashes[pi])
+        return;
+    else if (ack_out.get(pos.parent())!=bins::EMPTY)
         return; // have this hash already, even accptd data
 	hashes[pos] = hash;
 }
@@ -165,23 +171,23 @@ bool            FileTransfer::OfferData (bin64_t pos, uint8_t* data, size_t leng
         return false;
     if (ack_out.get(pos)==bins::FILLED)
         return true; // ???
-    int peak=0;
-    while (peak<peak_count && !pos.within(peaks[peak]))
-        peak++;
-    if (peak==peak_count)
+    int pi=0;
+    while (pi<peak_count && !pos.within(peaks[pi]))
+        pi++;
+    if (pi==peak_count)
         return false;
-    Sha1Hash hash(data,length);
-    if (pos==peaks[peak]) {
-        if (hash!=peak_hashes[peak])
-            return false;
-    } else {
-        hashes[pos] = hash;
-        for(bin64_t p = pos.parent(); p.within(peaks[peak]) && ack_out.get(p)==bins::EMPTY; p=p.parent()) {
-            Sha1Hash phash = Sha1Hash(hashes[p.left()],hashes[p.right()]) ;
-            if (hashes[p]!=phash)
-                return false; // hash mismatch
-        }
+    bin64_t peak = peaks[pi];
+    
+    Sha1Hash hash(data,length);       
+    bin64_t p = pos;
+    while ( p!=peak && ack_out.get(p)==bins::EMPTY ) {
+        hashes[p] = hash;
+        p = p.parent();
+        hash = Sha1Hash(hashes[p.left()],hashes[p.right()]) ;
     }
+    if (hash!=hashes[p])
+        return false;
+    
     //printf("g %lli %s\n",(uint64_t)pos,hash.hex().c_str());
 	// walk to the nearest proven hash   FIXME 0-layer peak
     ack_out.set(pos,bins::FILLED);
-- 
2.20.1