src/networks/donkey/donkeyReliability.ml

   1 (* Copyright 2001, 2002 pango *)
   2 (*
   3     This file is part of mldonkey.
   4
   5     mldonkey is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     mldonkey is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with mldonkey; if not, write to the Free Software
  17     Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18 *)
  19
  20 (* The idea:
  21
  22    Contributors can be neutral, reliable, of suspicious.
  23    Contributors of different reliability should not be mixed, as much
  24    as possible.
  25    Suspicious contributors of level (n) can be used in groups that contain
  26    at most n non reliable contributors.
  27
  28    When a chunk is validated, all contributors become reliable.
  29    When a chunk is found broken, all contributors become suspicious, of
  30    level (number of contributors/2).
  31
  32    Suspicious of level 0 = banned.
  33
  34
  35 Let's suppose a chunk has been downloaded using n neutral contributors,
  36       r reliable contributors and s suspicious contributors;
  37
  38 If the chunk is validated =>
  39    all contributors become reliable
  40
  41 If the chunk is broken =>
  42    if there's non reliable contributors (n+s>0), remove reliable contributors
  43    from the list (we trust reliable contributors to be really reliable)
  44    all (remaining) contributors become suspicious "number of contributors/2"
  45
  46 From that, we see than it's acceptable to sometimes mix reliable contributors
  47 with others and still detect suspects (but the chunk may be unvalidated,
  48 resulting in a poor use of reliable contributors).
  49
  50 Neutrals can be mixed with suspicious, but should be accounted for when
  51 checking contributors list limit of suspicious members, so that dichotomia
  52 works. But this should be avoided in the general case, if we believe that
  53 most neutrals are in fact reliable (otherwise p2p networks don't work).
  54 While keeping them separate, the probability that the chunk is validated
  55 and that they all become reliable stays high.
  56
  57 level 1:
  58 reliables go with reliables
  59 neutrals go with neutrals
  60 suspicious go with suspicious
  61
  62 level 2:
  63 reliables go with reliables and neutrals
  64 neutrals go with neutrals
  65 suspicious go with suspicious
  66
  67 level 3:
  68 reliables go with all
  69 neutrals go with neutrals
  70 suspicious go with suspicious
  71
  72 level 4:
  73 reliables go with all
  74 neutrals go with neutrals and suspicious
  75 suspicious go with suspicious
  76
  77 level 5 (or max_int):
  78 no level 5.
  79
  80 levels:       past contributor
  81                r       n        s
  82
  83 incoming   r   1       2        3
  84 contrib    n   5       1        4
  85            s   5       5        1
  86
  87 with several past contributors kinds, take the max of levels.
  88
  89 Legacy blocks (containing legacy data at the beginning of the session)
  90 should be handled as if it was downloaded by another virtual neutral
  91 contributor.
  92
  93 From several choices, prefer the one of lowest level.
  94  *)
  95 open Printf2
  96
  97 open CommonTypes
  98 open CommonNetwork
  99 open GuiTypes
 100 open TcpBufferedSocket
 101 open DonkeyTypes
 102 open DonkeyGlobals
 103
 104 let (reliable_ips : (Ip.t, reliability) Hashtbl.t) = Hashtbl.create 1023
 105
 106 let ip_reliability ip =
 107   try
 108     Hashtbl.find reliable_ips ip
 109   with Not_found -> Reliability_neutral
 110
 111       (*
 112 let socket_reliability sock =
 113   ip_reliability (peer_ip sock)
 114   *)
 115
 116 let client_reliability c =
 117   ip_reliability c.client_ip
 118 (*  match c.client_sock with
 119       None -> ip_reliability c.client_ip
 120     | Some s ->
 121         try
 122           let ip = peer_ip s in
 123           if ip <> c.client_ip then begin
 124             lprintf "[WARNING] client_ip doesn't match peer_ip for client %d" (client_num c);
 125             lprint_newline ()
 126           end;
 127           ip_reliability ip
 128         with _ ->
 129           lprintf "[WARNING] client disconnected, using saved client_ip";
 130           lprint_newline ();
 131           ip_reliability c.client_ip *)
 132
 133
 134   (*
 135 let block_reliability b =
 136   let rec aux ips r n s l =
 137     match ips with
 138         [] -> (r, n, s, l)
 139       | ip :: q ->
 140           match ip_reliability ip with
 141               Reliability_reliable -> aux q (r + 1) n s l
 142             | Reliability_neutral -> aux q r (n + 1) s l
 143             | Reliability_suspicious ipl ->
 144                 aux q r n (s + 1) (min l ipl) in
 145     aux b.block_contributors 0 0 0 max_int
 146     *)
 147
 148 let print_reliability ip =
 149   lprintf "%s is %s\n" (Ip.to_string ip)
 150   (match ip_reliability ip with
 151       Reliability_neutral -> "neutral"
 152     | Reliability_reliable -> "reliable"
 153     | Reliability_suspicious 0 -> "has sent corrupted data"
 154     | Reliability_suspicious s -> Printf.sprintf "suspicious of level %d" s)
 155
 156 let bprint_reliability buf ip =
 157   Printf.bprintf buf "%s is %s\n" (Ip.to_string ip)
 158   (match ip_reliability ip with
 159        Reliability_neutral -> "neutral"
 160      | Reliability_reliable -> "reliable"
 161      | Reliability_suspicious 0 -> "has sent corrupted data"
 162      | Reliability_suspicious s -> Printf.sprintf "suspicious of level %d" s)
 163
 164 let bprint_reliability_table buf =
 165   let sorted_ips = Array.of_list (Hashtbl.fold (fun ip _ l -> ip :: l) reliable_ips []) in
 166   Array.sort Ip.compare sorted_ips;
 167   Array.iter (fun ip -> bprint_reliability buf ip) sorted_ips
 168
 169 let set_ip_reliability ip reliability =
 170   Hashtbl.replace reliable_ips ip reliability
 171
 172 (*
 173 let valid_block_detected b =
 174   List.iter (fun ip ->
 175     set_ip_reliability ip Reliability_reliable;
 176     print_reliability ip
 177   ) b.block_contributors
 178
 179 let corrupted_block_detected b =
 180   let r, n, s, l = block_reliability b in
 181   let n = if b.block_legacy then n + 1 else n in
 182   let r, contributors = if n + s > 0 then
 183     0, List.filter (fun ip -> ip_reliability ip <> Reliability_reliable) b.block_contributors
 184   else r, b.block_contributors in
 185   let max_neighbors = (r + n + s) / 2 in
 186           List.iter (fun ip ->
 187             set_ip_reliability ip (Reliability_suspicious max_neighbors);
 188             print_reliability ip;
 189             if max_neighbors = 0 then
 190               let message = Printf.sprintf "IP %s SHOULD BE BANNED (CORRUPTED DATA)\n" (Ip.to_string ip) in
 191               CommonEvent.add_event (Console_message_event message)
 192           ) contributors
 193
 194 let allowed_by_reliability b c =
 195   let r, n, s, l = block_reliability b in
 196   let n = if b.block_legacy then n + 1 else n in
 197   match client_reliability c with
 198       Reliability_reliable ->
 199         if s > 0 then 3
 200         else if n > 0 then 2
 201         else 1
 202     | Reliability_neutral ->
 203         if r > 0 then max_int
 204         else if n + s + 1 > l then max_int
 205         else if s > 0 then 4
 206         else 1
 207     | Reliability_suspicious crl ->
 208         if r > 0 || n > 0 then max_int
 209         else if n + s + 1 > min l crl then max_int
 210         else 1
 211           *)
 212
 213 let _ =
 214   register_commands
 215     [
 216       "dump_reliability", "Network/Donkey", Arg_none (fun o ->
 217         let buf = o.conn_buf in
 218         bprint_reliability_table buf;
 219         ""
 220       ), ":\t\t\tdisplay the reliability of sources";
 221     ]
 222
 223 open Md4
 224 (* TODO: add timers to remove old entries *)
 225
 226 let (client_hashes : (Ip.t, Md4.t) Hashtbl.t) = Hashtbl.create 1023
 227
 228 let register_client_hash ip hash =
 229   try
 230     let old_hash = Hashtbl.find client_hashes ip in
 231     let hashes_match = (hash = old_hash) in
 232     if not hashes_match then begin
 233         lprintf "client hash clash %s: %s/%s\n"
 234         (Ip.to_string ip) (Md4.to_string old_hash) (Md4.to_string hash);
 235       Hashtbl.replace client_hashes ip hash;
 236     end;
 237     hashes_match
 238   with Not_found ->
 239     Hashtbl.add client_hashes ip hash;
 240     true
 241
 242 module Marshal = struct
 243
 244     let to_string v _ =
 245       let v = Marshal.to_string v [] in
 246 (* The header depends on OCaml version. Remove it. *)
 247       let v = String.sub v (Marshal.header_size)
 248         (String.length v - Marshal.header_size) in
 249       v
 250
 251   end