diff options
-rw-r--r-- | OnionRouter.hs | 8 | ||||
-rw-r--r-- | src/Network/Kademlia/Search.hs | 22 | ||||
-rw-r--r-- | todo.txt | 4 |
3 files changed, 23 insertions, 11 deletions
diff --git a/OnionRouter.hs b/OnionRouter.hs index eb79b70b..757214cd 100644 --- a/OnionRouter.hs +++ b/OnionRouter.hs | |||
@@ -32,6 +32,7 @@ import qualified Data.Word64Map as W64 | |||
32 | import Network.Socket | 32 | import Network.Socket |
33 | import System.Endian | 33 | import System.Endian |
34 | import System.IO | 34 | import System.IO |
35 | import System.Timeout | ||
35 | 36 | ||
36 | -- Toxcore saves a maximum of 12 paths: 6 paths are reserved for announcing | 37 | -- Toxcore saves a maximum of 12 paths: 6 paths are reserved for announcing |
37 | -- ourselves and 6 others are used to search for friends. | 38 | -- ourselves and 6 others are used to search for friends. |
@@ -269,13 +270,18 @@ handleEvent getnodes or e@(BuildRoute (RouteId rid)) = do | |||
269 | forkIO $ sendq asel aq (ts !! 0) >>= atomically . writeTVar av . Just | 270 | forkIO $ sendq asel aq (ts !! 0) >>= atomically . writeTVar av . Just |
270 | forkIO $ sendq bsel bq (ts !! 1) >>= atomically . writeTVar bv . Just | 271 | forkIO $ sendq bsel bq (ts !! 1) >>= atomically . writeTVar bv . Just |
271 | forkIO $ sendq csel cq (ts !! 2) >>= atomically . writeTVar cv . Just | 272 | forkIO $ sendq csel cq (ts !! 2) >>= atomically . writeTVar cv . Just |
272 | atomically $ do -- Wait for all 3 results. | 273 | -- This timeout should be unnecessary... But I'm paranoid. |
274 | -- Note: 10 seconds should be sufficient for typical get-nodes queries. | ||
275 | tm <- timeout 20000000 $ atomically $ do -- Wait for all 3 results. | ||
273 | rs <- catMaybes <$> sequence [readTVar av,readTVar bv,readTVar cv] | 276 | rs <- catMaybes <$> sequence [readTVar av,readTVar bv,readTVar cv] |
274 | case rs of [_,_,_] -> do | 277 | case rs of [_,_,_] -> do |
275 | return $ catMaybes $ catMaybes rs | 278 | return $ catMaybes $ catMaybes rs |
276 | -- self <- IntMap.lookup (-1) <$> readTVar (trampolineNodes or) | 279 | -- self <- IntMap.lookup (-1) <$> readTVar (trampolineNodes or) |
277 | -- return $ maybe (catMaybes rs) (\x -> [x,x,x]) self | 280 | -- return $ maybe (catMaybes rs) (\x -> [x,x,x]) self |
278 | _ -> retry | 281 | _ -> retry |
282 | maybe (hPutStrLn stderr "ONION: Unexpected sendq timeout!" >> return []) | ||
283 | return | ||
284 | tm | ||
279 | return $ do | 285 | return $ do |
280 | myThreadId >>= flip labelThread ("OnionRouter.sendqs") | 286 | myThreadId >>= flip labelThread ("OnionRouter.sendqs") |
281 | nodes <- case ts of | 287 | nodes <- case ts of |
diff --git a/src/Network/Kademlia/Search.hs b/src/Network/Kademlia/Search.hs index 58c8fad8..593470c3 100644 --- a/src/Network/Kademlia/Search.hs +++ b/src/Network/Kademlia/Search.hs | |||
@@ -60,7 +60,7 @@ data SearchState nid addr tok ni r = SearchState | |||
60 | searchPendingCount :: TVar Int | 60 | searchPendingCount :: TVar Int |
61 | -- | Nodes scheduled to be queried. | 61 | -- | Nodes scheduled to be queried. |
62 | , searchQueued :: TVar (MinMaxPSQ ni nid) | 62 | , searchQueued :: TVar (MinMaxPSQ ni nid) |
63 | -- | The nearest K nodes that issued a reply. | 63 | -- | The nearest (K - α) nodes that issued a reply. |
64 | , searchInformant :: TVar (MinMaxPSQ' ni nid (Maybe tok)) | 64 | , searchInformant :: TVar (MinMaxPSQ' ni nid (Maybe tok)) |
65 | -- | This tracks already-queried addresses so we avoid bothering them | 65 | -- | This tracks already-queried addresses so we avoid bothering them |
66 | -- again. XXX: We could probably keep only the pending queries in this | 66 | -- again. XXX: We could probably keep only the pending queries in this |
@@ -121,8 +121,17 @@ reset bkts qsearch target st = do | |||
121 | searchAlpha :: Int | 121 | searchAlpha :: Int |
122 | searchAlpha = 8 | 122 | searchAlpha = 8 |
123 | 123 | ||
124 | -- | 'searchK' should be larger than 'searchAlpha'. How much larger depends on | ||
125 | -- how fast the queries are. For Tox's much slower onion-routed queries, we | ||
126 | -- need to ensure that closer non-responding queries don't completely push out | ||
127 | -- farther away queries. | ||
128 | -- | ||
129 | -- For BitTorrent, setting them both 8 was not an issue, but that is no longer | ||
130 | -- supported because now the number of remembered informants is now the | ||
131 | -- difference between these two numbers. So, if searchK = 16 and searchAlpha = | ||
132 | -- 4, then the number of remembered query responses is 12. | ||
124 | searchK :: Int | 133 | searchK :: Int |
125 | searchK = 8 | 134 | searchK = 16 |
126 | 135 | ||
127 | sendQuery :: forall addr nid tok ni r. | 136 | sendQuery :: forall addr nid tok ni r. |
128 | ( Ord addr | 137 | ( Ord addr |
@@ -158,9 +167,10 @@ sendQuery Search{..} searchTarget searchResult sch@SearchState{..} (ni :-> d) = | |||
158 | | otherwise = MM.insertTake k n ( kademliaXor searchSpace searchTarget | 167 | | otherwise = MM.insertTake k n ( kademliaXor searchSpace searchTarget |
159 | $ kademliaLocation searchSpace n ) | 168 | $ kademliaLocation searchSpace n ) |
160 | q | 169 | q |
161 | qsize <- MM.size <$> readTVar searchQueued | 170 | qsize0 <- MM.size <$> readTVar searchQueued |
171 | let qsize = if qsize0 < searchK then searchK else qsize0 | ||
162 | modifyTVar searchQueued $ \q -> foldr (insertFoundNode qsize) q ns | 172 | modifyTVar searchQueued $ \q -> foldr (insertFoundNode qsize) q ns |
163 | modifyTVar searchInformant $ MM.insertTake' searchK ni tok d | 173 | modifyTVar searchInformant $ MM.insertTake' (searchK - searchAlpha) ni tok d |
164 | flip fix rs $ \loop -> \case | 174 | flip fix rs $ \loop -> \case |
165 | r:rs' -> do | 175 | r:rs' -> do |
166 | wanting <- searchResult r | 176 | wanting <- searchResult r |
@@ -178,7 +188,7 @@ searchIsFinished SearchState{ ..} = do | |||
178 | informants <- readTVar searchInformant | 188 | informants <- readTVar searchInformant |
179 | return $ cnt == 0 | 189 | return $ cnt == 0 |
180 | && ( MM.null q | 190 | && ( MM.null q |
181 | || ( MM.size informants >= searchK | 191 | || ( MM.size informants >= (searchK - searchAlpha) |
182 | && ( PSQ.prio (fromJust $ MM.findMax informants) | 192 | && ( PSQ.prio (fromJust $ MM.findMax informants) |
183 | <= PSQ.prio (fromJust $ MM.findMin q)))) | 193 | <= PSQ.prio (fromJust $ MM.findMin q)))) |
184 | 194 | ||
@@ -217,7 +227,7 @@ searchLoop sch@Search{..} target result s@SearchState{..} = do | |||
217 | Just (ni :-> d, q) | 227 | Just (ni :-> d, q) |
218 | | -- If there's fewer than /k/ informants and there's any | 228 | | -- If there's fewer than /k/ informants and there's any |
219 | -- node we haven't yet got a response from. | 229 | -- node we haven't yet got a response from. |
220 | (MM.size informants < searchK) && (cnt > 0 || not (MM.null q)) | 230 | (MM.size informants < searchK - searchAlpha) && (cnt > 0 || not (MM.null q)) |
221 | -- Or there's no informants yet at all. | 231 | -- Or there's no informants yet at all. |
222 | || MM.null informants | 232 | || MM.null informants |
223 | -- Or if the closest scheduled node is nearer than the | 233 | -- Or if the closest scheduled node is nearer than the |
@@ -1,7 +1,3 @@ | |||
1 | kademlia: Search is not working as well as expected. Fast informants are | ||
2 | probably pushing out closer but slow informants for longer-timeout | ||
3 | queries like tox onion-routed queries. | ||
4 | |||
5 | ui: Online help. | 1 | ui: Online help. |
6 | 2 | ||
7 | ui: Explicit routing table node deletion. "forget" command. | 3 | ui: Explicit routing table node deletion. "forget" command. |