updateFallbackDirs.py 45 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257
  1. #!/usr/bin/python
  2. # Usage: scripts/maint/updateFallbackDirs.py > src/or/fallback_dirs.inc
  3. #
  4. # Then read the generated list to ensure no-one slipped anything funny into
  5. # their name or contactinfo
  6. # Script by weasel, April 2015
  7. # Portions by gsathya & karsten, 2013
  8. # https://trac.torproject.org/projects/tor/attachment/ticket/8374/dir_list.2.py
  9. # Modifications by teor, 2015
  10. import StringIO
  11. import string
  12. import re
  13. import datetime
  14. import gzip
  15. import os.path
  16. import json
  17. import math
  18. import sys
  19. import urllib
  20. import urllib2
  21. import hashlib
  22. import dateutil.parser
  23. # bson_lazy provides bson
  24. #from bson import json_util
  25. import logging
  26. logging.basicConfig(level=logging.DEBUG)
  27. ## Top-Level Configuration
  28. # Output all candidate fallbacks, or only output selected fallbacks?
  29. OUTPUT_CANDIDATES = False
  30. ## OnionOO Settings
  31. ONIONOO = 'https://onionoo.torproject.org/'
  32. #ONIONOO = 'https://onionoo.thecthulhu.com/'
  33. # Don't bother going out to the Internet, just use the files available locally,
  34. # even if they're very old
  35. LOCAL_FILES_ONLY = False
  36. ## Whitelist / Blacklist Filter Settings
  37. # The whitelist contains entries that are included if all attributes match
  38. # (IPv4, dirport, orport, id, and optionally IPv6 and IPv6 orport)
  39. # The blacklist contains (partial) entries that are excluded if any
  40. # sufficiently specific group of attributes matches:
  41. # IPv4 & DirPort
  42. # IPv4 & ORPort
  43. # ID
  44. # IPv6 & DirPort
  45. # IPv6 & IPv6 ORPort
  46. # If neither port is included in the blacklist, the entire IP address is
  47. # blacklisted.
  48. # What happens to entries in neither list?
  49. # When True, they are included, when False, they are excluded
  50. INCLUDE_UNLISTED_ENTRIES = True if OUTPUT_CANDIDATES else False
  51. # If an entry is in both lists, what happens?
  52. # When True, it is excluded, when False, it is included
  53. BLACKLIST_EXCLUDES_WHITELIST_ENTRIES = True
  54. WHITELIST_FILE_NAME = 'scripts/maint/fallback.whitelist'
  55. BLACKLIST_FILE_NAME = 'scripts/maint/fallback.blacklist'
  56. # The number of bytes we'll read from a filter file before giving up
  57. MAX_LIST_FILE_SIZE = 1024 * 1024
  58. ## Eligibility Settings
  59. ADDRESS_AND_PORT_STABLE_DAYS = 120
  60. # What time-weighted-fraction of these flags must FallbackDirs
  61. # Equal or Exceed?
  62. CUTOFF_RUNNING = .95
  63. CUTOFF_V2DIR = .95
  64. CUTOFF_GUARD = .95
  65. # What time-weighted-fraction of these flags must FallbackDirs
  66. # Equal or Fall Under?
  67. # .00 means no bad exits
  68. PERMITTED_BADEXIT = .00
  69. ## List Length Limits
  70. # The target for these parameters is 20% of the guards in the network
  71. # This is around 200 as of October 2015
  72. FALLBACK_PROPORTION_OF_GUARDS = None if OUTPUT_CANDIDATES else 0.2
  73. # Limit the number of fallbacks (eliminating lowest by weight)
  74. MAX_FALLBACK_COUNT = None if OUTPUT_CANDIDATES else 500
  75. # Emit a C #error if the number of fallbacks is below
  76. MIN_FALLBACK_COUNT = 100
  77. ## Fallback Weight Settings
  78. # Any fallback with the Exit flag has its weight multipled by this fraction
  79. EXIT_WEIGHT_FRACTION = 1.0
  80. # If True, emit a C #error if we can't satisfy various constraints
  81. # If False, emit a C comment instead
  82. STRICT_FALLBACK_WEIGHTS = False
  83. # Limit the proportional weight
  84. # If a single fallback's weight is too high, it will see too many clients
  85. # We reweight using a lower threshold to provide some leeway for:
  86. # * elimination of low weight relays
  87. # * consensus weight changes
  88. # * fallback directory losses over time
  89. # A relay weighted at 1 in 10 fallbacks will see about 10% of clients that
  90. # use the fallback directories. (The 9 directory authorities see a similar
  91. # proportion of clients.)
  92. TARGET_MAX_WEIGHT_FRACTION = 1/10.0
  93. REWEIGHTING_FUDGE_FACTOR = 0.8
  94. MAX_WEIGHT_FRACTION = TARGET_MAX_WEIGHT_FRACTION * REWEIGHTING_FUDGE_FACTOR
  95. # If a single fallback's weight is too low, it's pointless adding it.
  96. # (Final weights may be slightly higher than this, due to low weight relays
  97. # being excluded.)
  98. # A relay weighted at 1 in 1000 fallbacks will see about 0.1% of clients.
  99. MIN_WEIGHT_FRACTION = 0.0 if OUTPUT_CANDIDATES else 1/1000.0
  100. ## Other Configuration Parameters
  101. # older entries' weights are adjusted with ALPHA^(age in days)
  102. AGE_ALPHA = 0.99
  103. # this factor is used to scale OnionOO entries to [0,1]
  104. ONIONOO_SCALE_ONE = 999.
  105. ## Parsing Functions
  106. def parse_ts(t):
  107. return datetime.datetime.strptime(t, "%Y-%m-%d %H:%M:%S")
  108. def remove_bad_chars(raw_string, bad_char_list):
  109. # Remove each character in the bad_char_list
  110. escaped_string = raw_string
  111. for c in bad_char_list:
  112. escaped_string = escaped_string.replace(c, '')
  113. return escaped_string
  114. def cleanse_whitespace(raw_string):
  115. # Replace all whitespace characters with a space
  116. escaped_string = raw_string
  117. for c in string.whitespace:
  118. escaped_string = escaped_string.replace(c, ' ')
  119. return escaped_string
  120. def cleanse_c_multiline_comment(raw_string):
  121. # Prevent a malicious / unanticipated string from breaking out
  122. # of a C-style multiline comment
  123. # This removes '/*' and '*/'
  124. # To deal with '//', the end comment must be on its own line
  125. bad_char_list = '*'
  126. # Prevent a malicious string from using C nulls
  127. bad_char_list += '\0'
  128. # Be safer by removing bad characters entirely
  129. escaped_string = remove_bad_chars(raw_string, bad_char_list)
  130. # Embedded newlines should be removed by tor/onionoo, but let's be paranoid
  131. escaped_string = cleanse_whitespace(escaped_string)
  132. # Some compilers may further process the content of comments
  133. # There isn't much we can do to cover every possible case
  134. # But comment-based directives are typically only advisory
  135. return escaped_string
  136. def cleanse_c_string(raw_string):
  137. # Prevent a malicious address/fingerprint string from breaking out
  138. # of a C-style string
  139. bad_char_list = '"'
  140. # Prevent a malicious string from using escapes
  141. bad_char_list += '\\'
  142. # Prevent a malicious string from using C nulls
  143. bad_char_list += '\0'
  144. # Be safer by removing bad characters entirely
  145. escaped_string = remove_bad_chars(raw_string, bad_char_list)
  146. # Embedded newlines should be removed by tor/onionoo, but let's be paranoid
  147. escaped_string = cleanse_whitespace(escaped_string)
  148. # Some compilers may further process the content of strings
  149. # There isn't much we can do to cover every possible case
  150. # But this typically only results in changes to the string data
  151. return escaped_string
  152. ## OnionOO Source Functions
  153. # a dictionary of source metadata for each onionoo query we've made
  154. fetch_source = {}
  155. # register source metadata for 'what'
  156. # assumes we only retrieve one document for each 'what'
  157. def register_fetch_source(what, url, relays_published, version):
  158. fetch_source[what] = {}
  159. fetch_source[what]['url'] = url
  160. fetch_source[what]['relays_published'] = relays_published
  161. fetch_source[what]['version'] = version
  162. # list each registered source's 'what'
  163. def fetch_source_list():
  164. return sorted(fetch_source.keys())
  165. # given 'what', provide a multiline C comment describing the source
  166. def describe_fetch_source(what):
  167. desc = '/*'
  168. desc += '\n'
  169. desc += 'Onionoo Source: '
  170. desc += cleanse_c_multiline_comment(what)
  171. desc += ' Date: '
  172. desc += cleanse_c_multiline_comment(fetch_source[what]['relays_published'])
  173. desc += ' Version: '
  174. desc += cleanse_c_multiline_comment(fetch_source[what]['version'])
  175. desc += '\n'
  176. desc += 'URL: '
  177. desc += cleanse_c_multiline_comment(fetch_source[what]['url'])
  178. desc += '\n'
  179. desc += '*/'
  180. return desc
  181. ## File Processing Functions
  182. def write_to_file(str, file_name, max_len):
  183. try:
  184. with open(file_name, 'w') as f:
  185. f.write(str[0:max_len])
  186. except EnvironmentError, error:
  187. logging.debug('Writing file %s failed: %d: %s'%
  188. (file_name,
  189. error.errno,
  190. error.strerror)
  191. )
  192. def read_from_file(file_name, max_len):
  193. try:
  194. if os.path.isfile(file_name):
  195. with open(file_name, 'r') as f:
  196. return f.read(max_len)
  197. except EnvironmentError, error:
  198. logging.debug('Loading file %s failed: %d: %s'%
  199. (file_name,
  200. error.errno,
  201. error.strerror)
  202. )
  203. return None
  204. def load_possibly_compressed_response_json(response):
  205. if response.info().get('Content-Encoding') == 'gzip':
  206. buf = StringIO.StringIO( response.read() )
  207. f = gzip.GzipFile(fileobj=buf)
  208. return json.load(f)
  209. else:
  210. return json.load(response)
  211. def load_json_from_file(json_file_name):
  212. # An exception here may be resolved by deleting the .last_modified
  213. # and .json files, and re-running the script
  214. try:
  215. with open(json_file_name, 'r') as f:
  216. return json.load(f)
  217. except EnvironmentError, error:
  218. raise Exception('Reading not-modified json file %s failed: %d: %s'%
  219. (json_file_name,
  220. error.errno,
  221. error.strerror)
  222. )
  223. ## OnionOO Functions
  224. def datestr_to_datetime(datestr):
  225. # Parse datetimes like: Fri, 02 Oct 2015 13:34:14 GMT
  226. if datestr is not None:
  227. dt = dateutil.parser.parse(datestr)
  228. else:
  229. # Never modified - use start of epoch
  230. dt = datetime.datetime.utcfromtimestamp(0)
  231. # strip any timezone out (in case they're supported in future)
  232. dt = dt.replace(tzinfo=None)
  233. return dt
  234. def onionoo_fetch(what, **kwargs):
  235. params = kwargs
  236. params['type'] = 'relay'
  237. #params['limit'] = 10
  238. params['first_seen_days'] = '%d-'%(ADDRESS_AND_PORT_STABLE_DAYS,)
  239. params['last_seen_days'] = '-7'
  240. params['flag'] = 'V2Dir'
  241. url = ONIONOO + what + '?' + urllib.urlencode(params)
  242. # Unfortunately, the URL is too long for some OS filenames,
  243. # but we still don't want to get files from different URLs mixed up
  244. base_file_name = what + '-' + hashlib.sha1(url).hexdigest()
  245. full_url_file_name = base_file_name + '.full_url'
  246. MAX_FULL_URL_LENGTH = 1024
  247. last_modified_file_name = base_file_name + '.last_modified'
  248. MAX_LAST_MODIFIED_LENGTH = 64
  249. json_file_name = base_file_name + '.json'
  250. if LOCAL_FILES_ONLY:
  251. # Read from the local file, don't write to anything
  252. response_json = load_json_from_file(json_file_name)
  253. else:
  254. # store the full URL to a file for debugging
  255. # no need to compare as long as you trust SHA-1
  256. write_to_file(url, full_url_file_name, MAX_FULL_URL_LENGTH)
  257. request = urllib2.Request(url)
  258. request.add_header('Accept-encoding', 'gzip')
  259. # load the last modified date from the file, if it exists
  260. last_mod_date = read_from_file(last_modified_file_name,
  261. MAX_LAST_MODIFIED_LENGTH)
  262. if last_mod_date is not None:
  263. request.add_header('If-modified-since', last_mod_date)
  264. # Parse last modified date
  265. last_mod = datestr_to_datetime(last_mod_date)
  266. # Not Modified and still recent enough to be useful
  267. # Onionoo / Globe used to use 6 hours, but we can afford a day
  268. required_freshness = datetime.datetime.utcnow()
  269. # strip any timezone out (to match dateutil.parser)
  270. required_freshness = required_freshness.replace(tzinfo=None)
  271. required_freshness -= datetime.timedelta(hours=24)
  272. # Make the OnionOO request
  273. response_code = 0
  274. try:
  275. response = urllib2.urlopen(request)
  276. response_code = response.getcode()
  277. except urllib2.HTTPError, error:
  278. response_code = error.code
  279. if response_code == 304: # not modified
  280. pass
  281. else:
  282. raise Exception("Could not get " + url + ": "
  283. + str(error.code) + ": " + error.reason)
  284. if response_code == 200: # OK
  285. last_mod = datestr_to_datetime(response.info().get('Last-Modified'))
  286. # Check for freshness
  287. if last_mod < required_freshness:
  288. if last_mod_date is not None:
  289. date_message = "Outdated data: last updated " + last_mod_date
  290. else:
  291. date_message = "No data: never downloaded "
  292. raise Exception(date_message + " from " + url)
  293. # Process the data
  294. if response_code == 200: # OK
  295. response_json = load_possibly_compressed_response_json(response)
  296. with open(json_file_name, 'w') as f:
  297. # use the most compact json representation to save space
  298. json.dump(response_json, f, separators=(',',':'))
  299. # store the last modified date in its own file
  300. if response.info().get('Last-modified') is not None:
  301. write_to_file(response.info().get('Last-Modified'),
  302. last_modified_file_name,
  303. MAX_LAST_MODIFIED_LENGTH)
  304. elif response_code == 304: # Not Modified
  305. response_json = load_json_from_file(json_file_name)
  306. else: # Unexpected HTTP response code not covered in the HTTPError above
  307. raise Exception("Unexpected HTTP response code to " + url + ": "
  308. + str(response_code))
  309. register_fetch_source(what,
  310. url,
  311. response_json['relays_published'],
  312. response_json['version'])
  313. return response_json
  314. def fetch(what, **kwargs):
  315. #x = onionoo_fetch(what, **kwargs)
  316. # don't use sort_keys, as the order of or_addresses is significant
  317. #print json.dumps(x, indent=4, separators=(',', ': '))
  318. #sys.exit(0)
  319. return onionoo_fetch(what, **kwargs)
  320. ## Fallback Candidate Class
  321. class Candidate(object):
  322. CUTOFF_ADDRESS_AND_PORT_STABLE = (datetime.datetime.now()
  323. - datetime.timedelta(ADDRESS_AND_PORT_STABLE_DAYS))
  324. def __init__(self, details):
  325. for f in ['fingerprint', 'nickname', 'last_changed_address_or_port',
  326. 'consensus_weight', 'or_addresses', 'dir_address']:
  327. if not f in details: raise Exception("Document has no %s field."%(f,))
  328. if not 'contact' in details:
  329. details['contact'] = None
  330. if not 'flags' in details or details['flags'] is None:
  331. details['flags'] = []
  332. details['last_changed_address_or_port'] = parse_ts(
  333. details['last_changed_address_or_port'])
  334. self._data = details
  335. self._stable_sort_or_addresses()
  336. self._fpr = self._data['fingerprint']
  337. self._running = self._guard = self._v2dir = 0.
  338. self._split_dirport()
  339. self._compute_orport()
  340. if self.orport is None:
  341. raise Exception("Failed to get an orport for %s."%(self._fpr,))
  342. self._compute_ipv6addr()
  343. if self.ipv6addr is None:
  344. logging.debug("Failed to get an ipv6 address for %s."%(self._fpr,))
  345. # Reduce the weight of exits to EXIT_WEIGHT_FRACTION * consensus_weight
  346. if self.is_exit():
  347. current_weight = self._data['consensus_weight']
  348. exit_weight = current_weight * EXIT_WEIGHT_FRACTION
  349. self._data['original_consensus_weight'] = current_weight
  350. self._data['consensus_weight'] = exit_weight
  351. def _stable_sort_or_addresses(self):
  352. # replace self._data['or_addresses'] with a stable ordering,
  353. # sorting the secondary addresses in string order
  354. # leave the received order in self._data['or_addresses_raw']
  355. self._data['or_addresses_raw'] = self._data['or_addresses']
  356. or_address_primary = self._data['or_addresses'][:1]
  357. # subsequent entries in the or_addresses array are in an arbitrary order
  358. # so we stabilise the addresses by sorting them in string order
  359. or_addresses_secondaries_stable = sorted(self._data['or_addresses'][1:])
  360. or_addresses_stable = or_address_primary + or_addresses_secondaries_stable
  361. self._data['or_addresses'] = or_addresses_stable
  362. def get_fingerprint(self):
  363. return self._fpr
  364. # is_valid_ipv[46]_address by gsathya, karsten, 2013
  365. @staticmethod
  366. def is_valid_ipv4_address(address):
  367. if not isinstance(address, (str, unicode)):
  368. return False
  369. # check if there are four period separated values
  370. if address.count(".") != 3:
  371. return False
  372. # checks that each value in the octet are decimal values between 0-255
  373. for entry in address.split("."):
  374. if not entry.isdigit() or int(entry) < 0 or int(entry) > 255:
  375. return False
  376. elif entry[0] == "0" and len(entry) > 1:
  377. return False # leading zeros, for instance in "1.2.3.001"
  378. return True
  379. @staticmethod
  380. def is_valid_ipv6_address(address):
  381. if not isinstance(address, (str, unicode)):
  382. return False
  383. # remove brackets
  384. address = address[1:-1]
  385. # addresses are made up of eight colon separated groups of four hex digits
  386. # with leading zeros being optional
  387. # https://en.wikipedia.org/wiki/IPv6#Address_format
  388. colon_count = address.count(":")
  389. if colon_count > 7:
  390. return False # too many groups
  391. elif colon_count != 7 and not "::" in address:
  392. return False # not enough groups and none are collapsed
  393. elif address.count("::") > 1 or ":::" in address:
  394. return False # multiple groupings of zeros can't be collapsed
  395. found_ipv4_on_previous_entry = False
  396. for entry in address.split(":"):
  397. # If an IPv6 address has an embedded IPv4 address,
  398. # it must be the last entry
  399. if found_ipv4_on_previous_entry:
  400. return False
  401. if not re.match("^[0-9a-fA-f]{0,4}$", entry):
  402. if not Candidate.is_valid_ipv4_address(entry):
  403. return False
  404. else:
  405. found_ipv4_on_previous_entry = True
  406. return True
  407. def _split_dirport(self):
  408. # Split the dir_address into dirip and dirport
  409. (self.dirip, _dirport) = self._data['dir_address'].split(':', 2)
  410. self.dirport = int(_dirport)
  411. def _compute_orport(self):
  412. # Choose the first ORPort that's on the same IPv4 address as the DirPort.
  413. # In rare circumstances, this might not be the primary ORPort address.
  414. # However, _stable_sort_or_addresses() ensures we choose the same one
  415. # every time, even if onionoo changes the order of the secondaries.
  416. self._split_dirport()
  417. self.orport = None
  418. for i in self._data['or_addresses']:
  419. if i != self._data['or_addresses'][0]:
  420. logging.debug('Secondary IPv4 Address Used for %s: %s'%(self._fpr, i))
  421. (ipaddr, port) = i.rsplit(':', 1)
  422. if (ipaddr == self.dirip) and Candidate.is_valid_ipv4_address(ipaddr):
  423. self.orport = int(port)
  424. return
  425. def _compute_ipv6addr(self):
  426. # Choose the first IPv6 address that uses the same port as the ORPort
  427. # Or, choose the first IPv6 address in the list
  428. # _stable_sort_or_addresses() ensures we choose the same IPv6 address
  429. # every time, even if onionoo changes the order of the secondaries.
  430. self.ipv6addr = None
  431. self.ipv6orport = None
  432. # Choose the first IPv6 address that uses the same port as the ORPort
  433. for i in self._data['or_addresses']:
  434. (ipaddr, port) = i.rsplit(':', 1)
  435. if (port == self.orport) and Candidate.is_valid_ipv6_address(ipaddr):
  436. self.ipv6addr = ipaddr
  437. self.ipv6orport = port
  438. return
  439. # Choose the first IPv6 address in the list
  440. for i in self._data['or_addresses']:
  441. (ipaddr, port) = i.rsplit(':', 1)
  442. if Candidate.is_valid_ipv6_address(ipaddr):
  443. self.ipv6addr = ipaddr
  444. self.ipv6orport = port
  445. return
  446. @staticmethod
  447. def _extract_generic_history(history, which='unknown'):
  448. # given a tree like this:
  449. # {
  450. # "1_month": {
  451. # "count": 187,
  452. # "factor": 0.001001001001001001,
  453. # "first": "2015-02-27 06:00:00",
  454. # "interval": 14400,
  455. # "last": "2015-03-30 06:00:00",
  456. # "values": [
  457. # 999,
  458. # 999
  459. # ]
  460. # },
  461. # "1_week": {
  462. # "count": 169,
  463. # "factor": 0.001001001001001001,
  464. # "first": "2015-03-23 07:30:00",
  465. # "interval": 3600,
  466. # "last": "2015-03-30 07:30:00",
  467. # "values": [ ...]
  468. # },
  469. # "1_year": {
  470. # "count": 177,
  471. # "factor": 0.001001001001001001,
  472. # "first": "2014-04-11 00:00:00",
  473. # "interval": 172800,
  474. # "last": "2015-03-29 00:00:00",
  475. # "values": [ ...]
  476. # },
  477. # "3_months": {
  478. # "count": 185,
  479. # "factor": 0.001001001001001001,
  480. # "first": "2014-12-28 06:00:00",
  481. # "interval": 43200,
  482. # "last": "2015-03-30 06:00:00",
  483. # "values": [ ...]
  484. # }
  485. # },
  486. # extract exactly one piece of data per time interval,
  487. # using smaller intervals where available.
  488. #
  489. # returns list of (age, length, value) dictionaries.
  490. generic_history = []
  491. periods = history.keys()
  492. periods.sort(key = lambda x: history[x]['interval'])
  493. now = datetime.datetime.now()
  494. newest = now
  495. for p in periods:
  496. h = history[p]
  497. interval = datetime.timedelta(seconds = h['interval'])
  498. this_ts = parse_ts(h['last'])
  499. if (len(h['values']) != h['count']):
  500. logging.warn('Inconsistent value count in %s document for %s'
  501. %(p, which))
  502. for v in reversed(h['values']):
  503. if (this_ts <= newest):
  504. agt1 = now - this_ts
  505. agt2 = interval
  506. agetmp1 = (agt1.microseconds + (agt1.seconds + agt1.days * 24 * 3600)
  507. * 10**6) / 10**6
  508. agetmp2 = (agt2.microseconds + (agt2.seconds + agt2.days * 24 * 3600)
  509. * 10**6) / 10**6
  510. generic_history.append(
  511. { 'age': agetmp1,
  512. 'length': agetmp2,
  513. 'value': v
  514. })
  515. newest = this_ts
  516. this_ts -= interval
  517. if (this_ts + interval != parse_ts(h['first'])):
  518. logging.warn('Inconsistent time information in %s document for %s'
  519. %(p, which))
  520. #print json.dumps(generic_history, sort_keys=True,
  521. # indent=4, separators=(',', ': '))
  522. return generic_history
  523. @staticmethod
  524. def _avg_generic_history(generic_history):
  525. a = []
  526. for i in generic_history:
  527. if i['age'] > (ADDRESS_AND_PORT_STABLE_DAYS * 24 * 3600):
  528. continue
  529. if (i['length'] is not None
  530. and i['age'] is not None
  531. and i['value'] is not None):
  532. w = i['length'] * math.pow(AGE_ALPHA, i['age']/(3600*24))
  533. a.append( (i['value'] * w, w) )
  534. sv = math.fsum(map(lambda x: x[0], a))
  535. sw = math.fsum(map(lambda x: x[1], a))
  536. if sw == 0.0:
  537. svw = 0.0
  538. else:
  539. svw = sv/sw
  540. return svw
  541. def _add_generic_history(self, history):
  542. periods = r['read_history'].keys()
  543. periods.sort(key = lambda x: r['read_history'][x]['interval'] )
  544. print periods
  545. def add_running_history(self, history):
  546. pass
  547. def add_uptime(self, uptime):
  548. logging.debug('Adding uptime %s.'%(self._fpr,))
  549. # flags we care about: Running, V2Dir, Guard
  550. if not 'flags' in uptime:
  551. logging.debug('No flags in document for %s.'%(self._fpr,))
  552. return
  553. for f in ['Running', 'Guard', 'V2Dir']:
  554. if not f in uptime['flags']:
  555. logging.debug('No %s in flags for %s.'%(f, self._fpr,))
  556. return
  557. running = self._extract_generic_history(uptime['flags']['Running'],
  558. '%s-Running'%(self._fpr))
  559. guard = self._extract_generic_history(uptime['flags']['Guard'],
  560. '%s-Guard'%(self._fpr))
  561. v2dir = self._extract_generic_history(uptime['flags']['V2Dir'],
  562. '%s-V2Dir'%(self._fpr))
  563. if 'BadExit' in uptime['flags']:
  564. badexit = self._extract_generic_history(uptime['flags']['BadExit'],
  565. '%s-BadExit'%(self._fpr))
  566. self._running = self._avg_generic_history(running) / ONIONOO_SCALE_ONE
  567. self._guard = self._avg_generic_history(guard) / ONIONOO_SCALE_ONE
  568. self._v2dir = self._avg_generic_history(v2dir) / ONIONOO_SCALE_ONE
  569. self._badexit = None
  570. if 'BadExit' in uptime['flags']:
  571. self._badexit = self._avg_generic_history(badexit) / ONIONOO_SCALE_ONE
  572. def is_candidate(self):
  573. if (self._data['last_changed_address_or_port'] >
  574. self.CUTOFF_ADDRESS_AND_PORT_STABLE):
  575. logging.debug('%s not a candidate: changed address/port recently (%s)',
  576. self._fpr, self._data['last_changed_address_or_port'])
  577. return False
  578. if self._running < CUTOFF_RUNNING:
  579. logging.debug('%s not a candidate: running avg too low (%lf)',
  580. self._fpr, self._running)
  581. return False
  582. if self._v2dir < CUTOFF_V2DIR:
  583. logging.debug('%s not a candidate: v2dir avg too low (%lf)',
  584. self._fpr, self._v2dir)
  585. return False
  586. if self._badexit is not None and self._badexit > PERMITTED_BADEXIT:
  587. logging.debug('%s not a candidate: badexit avg too high (%lf)',
  588. self._fpr, self._badexit)
  589. return False
  590. # if the relay doesn't report a version, also exclude the relay
  591. if (not self._data.has_key('recommended_version')
  592. or not self._data['recommended_version']):
  593. return False
  594. if self._guard < CUTOFF_GUARD:
  595. logging.debug('%s not a candidate: guard avg too low (%lf)',
  596. self._fpr, self._guard)
  597. return False
  598. return True
  599. def is_in_whitelist(self, relaylist):
  600. """ A fallback matches if each key in the whitelist line matches:
  601. ipv4
  602. dirport
  603. orport
  604. id
  605. ipv6 address and port (if present)
  606. If the fallback has an ipv6 key, the whitelist line must also have
  607. it, and vice versa, otherwise they don't match. """
  608. for entry in relaylist:
  609. if entry['ipv4'] != self.dirip:
  610. continue
  611. if int(entry['dirport']) != self.dirport:
  612. continue
  613. if int(entry['orport']) != self.orport:
  614. continue
  615. if entry['id'] != self._fpr:
  616. continue
  617. if (entry.has_key('ipv6')
  618. and self.ipv6addr is not None and self.ipv6orport is not None):
  619. # if both entry and fallback have an ipv6 address, compare them
  620. if entry['ipv6'] != self.ipv6addr + ':' + self.ipv6orport:
  621. continue
  622. # if the fallback has an IPv6 address but the whitelist entry
  623. # doesn't, or vice versa, the whitelist entry doesn't match
  624. elif entry.has_key('ipv6') and self.ipv6addr is None:
  625. continue
  626. elif not entry.has_key('ipv6') and self.ipv6addr is not None:
  627. continue
  628. return True
  629. return False
  630. def is_in_blacklist(self, relaylist):
  631. """ A fallback matches a blacklist line if a sufficiently specific group
  632. of attributes matches:
  633. ipv4 & dirport
  634. ipv4 & orport
  635. id
  636. ipv6 & dirport
  637. ipv6 & ipv6 orport
  638. If the fallback and the blacklist line both have an ipv6 key,
  639. their values will be compared, otherwise, they will be ignored.
  640. If there is no dirport and no orport, the entry matches all relays on
  641. that ip. """
  642. for entry in relaylist:
  643. for key in entry:
  644. value = entry[key]
  645. if key == 'ipv4' and value == self.dirip:
  646. # if the dirport is present, check it too
  647. if entry.has_key('dirport'):
  648. if int(entry['dirport']) == self.dirport:
  649. return True
  650. # if the orport is present, check it too
  651. elif entry.has_key('orport'):
  652. if int(entry['orport']) == self.orport:
  653. return True
  654. else:
  655. return True
  656. if key == 'id' and value == self._fpr:
  657. return True
  658. if (key == 'ipv6'
  659. and self.ipv6addr is not None and self.ipv6orport is not None):
  660. # if both entry and fallback have an ipv6 address, compare them,
  661. # otherwise, disregard ipv6 addresses
  662. if value == self.ipv6addr + ':' + self.ipv6orport:
  663. # if the dirport is present, check it too
  664. if entry.has_key('dirport'):
  665. if int(entry['dirport']) == self.dirport:
  666. return True
  667. # if the orport is present, check it too
  668. elif entry.has_key('orport'):
  669. if int(entry['orport']) == self.orport:
  670. return True
  671. else:
  672. return True
  673. return False
  674. def is_exit(self):
  675. return 'Exit' in self._data['flags']
  676. def is_guard(self):
  677. return 'Guard' in self._data['flags']
  678. def fallback_weight_fraction(self, total_weight):
  679. return float(self._data['consensus_weight']) / total_weight
  680. # return the original consensus weight, if it exists,
  681. # or, if not, return the consensus weight
  682. def original_consensus_weight(self):
  683. if self._data.has_key('original_consensus_weight'):
  684. return self._data['original_consensus_weight']
  685. else:
  686. return self._data['consensus_weight']
  687. def original_fallback_weight_fraction(self, total_weight):
  688. return float(self.original_consensus_weight()) / total_weight
  689. def fallbackdir_line(self, total_weight, original_total_weight):
  690. # /*
  691. # nickname
  692. # flags
  693. # weight / total (percentage)
  694. # [original weight / original total (original percentage)]
  695. # [contact]
  696. # */
  697. # "address:dirport orport=port id=fingerprint"
  698. # "[ipv6=addr:orport]"
  699. # "weight=num",
  700. # Multiline C comment
  701. s = '/*'
  702. s += '\n'
  703. s += cleanse_c_multiline_comment(self._data['nickname'])
  704. s += '\n'
  705. s += 'Flags: '
  706. s += cleanse_c_multiline_comment(' '.join(sorted(self._data['flags'])))
  707. s += '\n'
  708. weight = self._data['consensus_weight']
  709. percent_weight = self.fallback_weight_fraction(total_weight)*100
  710. s += 'Fallback Weight: %d / %d (%.3f%%)'%(weight, total_weight,
  711. percent_weight)
  712. s += '\n'
  713. o_weight = self.original_consensus_weight()
  714. if o_weight != weight:
  715. o_percent_weight = self.original_fallback_weight_fraction(
  716. original_total_weight)*100
  717. s += 'Consensus Weight: %d / %d (%.3f%%)'%(o_weight,
  718. original_total_weight,
  719. o_percent_weight)
  720. s += '\n'
  721. if self._data['contact'] is not None:
  722. s += cleanse_c_multiline_comment(self._data['contact'])
  723. s += '\n'
  724. s += '*/'
  725. s += '\n'
  726. # Multi-Line C string with trailing comma (part of a string list)
  727. # This makes it easier to diff the file, and remove IPv6 lines using grep
  728. # Integers don't need escaping
  729. s += '"%s orport=%d id=%s"'%(
  730. cleanse_c_string(self._data['dir_address']),
  731. self.orport,
  732. cleanse_c_string(self._fpr))
  733. s += '\n'
  734. if self.ipv6addr is not None:
  735. s += '" ipv6=%s:%s"'%(
  736. cleanse_c_string(self.ipv6addr), cleanse_c_string(self.ipv6orport))
  737. s += '\n'
  738. s += '" weight=%d",'%(weight)
  739. return s
  740. ## Fallback Candidate List Class
  741. class CandidateList(dict):
  742. def __init__(self):
  743. pass
  744. def _add_relay(self, details):
  745. if not 'dir_address' in details: return
  746. c = Candidate(details)
  747. self[ c.get_fingerprint() ] = c
  748. def _add_uptime(self, uptime):
  749. try:
  750. fpr = uptime['fingerprint']
  751. except KeyError:
  752. raise Exception("Document has no fingerprint field.")
  753. try:
  754. c = self[fpr]
  755. except KeyError:
  756. logging.debug('Got unknown relay %s in uptime document.'%(fpr,))
  757. return
  758. c.add_uptime(uptime)
  759. def _add_details(self):
  760. logging.debug('Loading details document.')
  761. d = fetch('details',
  762. fields=('fingerprint,nickname,contact,last_changed_address_or_port,' +
  763. 'consensus_weight,or_addresses,dir_address,' +
  764. 'recommended_version,flags'))
  765. logging.debug('Loading details document done.')
  766. if not 'relays' in d: raise Exception("No relays found in document.")
  767. for r in d['relays']: self._add_relay(r)
  768. def _add_uptimes(self):
  769. logging.debug('Loading uptime document.')
  770. d = fetch('uptime')
  771. logging.debug('Loading uptime document done.')
  772. if not 'relays' in d: raise Exception("No relays found in document.")
  773. for r in d['relays']: self._add_uptime(r)
  774. def add_relays(self):
  775. self._add_details()
  776. self._add_uptimes()
  777. def count_guards(self):
  778. guard_count = 0
  779. for fpr in self.keys():
  780. if self[fpr].is_guard():
  781. guard_count += 1
  782. return guard_count
  783. # Find fallbacks that fit the uptime, stability, and flags criteria
  784. def compute_fallbacks(self):
  785. self.fallbacks = map(lambda x: self[x],
  786. sorted(
  787. filter(lambda x: self[x].is_candidate(),
  788. self.keys()),
  789. key=lambda x: self[x]._data['consensus_weight'],
  790. reverse=True)
  791. )
  792. @staticmethod
  793. def load_relaylist(file_name):
  794. """ Read each line in the file, and parse it like a FallbackDir line:
  795. an IPv4 address and optional port:
  796. <IPv4 address>:<port>
  797. which are parsed into dictionary entries:
  798. ipv4=<IPv4 address>
  799. dirport=<port>
  800. followed by a series of key=value entries:
  801. orport=<port>
  802. id=<fingerprint>
  803. ipv6=<IPv6 address>:<IPv6 orport>
  804. each line's key/value pairs are placed in a dictonary,
  805. (of string -> string key/value pairs),
  806. and these dictionaries are placed in an array.
  807. comments start with # and are ignored """
  808. relaylist = []
  809. file_data = read_from_file(file_name, MAX_LIST_FILE_SIZE)
  810. if file_data is None:
  811. return relaylist
  812. for line in file_data.split('\n'):
  813. relay_entry = {}
  814. # ignore comments
  815. line_comment_split = line.split('#')
  816. line = line_comment_split[0]
  817. # cleanup whitespace
  818. line = cleanse_whitespace(line)
  819. line = line.strip()
  820. if len(line) == 0:
  821. continue
  822. for item in line.split(' '):
  823. item = item.strip()
  824. if len(item) == 0:
  825. continue
  826. key_value_split = item.split('=')
  827. kvl = len(key_value_split)
  828. if kvl < 1 or kvl > 2:
  829. print '#error Bad %s item: %s, format is key=value.'%(
  830. file_name, item)
  831. if kvl == 1:
  832. # assume that entries without a key are the ipv4 address,
  833. # perhaps with a dirport
  834. ipv4_maybe_dirport = key_value_split[0]
  835. ipv4_maybe_dirport_split = ipv4_maybe_dirport.split(':')
  836. dirl = len(ipv4_maybe_dirport_split)
  837. if dirl < 1 or dirl > 2:
  838. print '#error Bad %s IPv4 item: %s, format is ipv4:port.'%(
  839. file_name, item)
  840. if dirl >= 1:
  841. relay_entry['ipv4'] = ipv4_maybe_dirport_split[0]
  842. if dirl == 2:
  843. relay_entry['dirport'] = ipv4_maybe_dirport_split[1]
  844. elif kvl == 2:
  845. relay_entry[key_value_split[0]] = key_value_split[1]
  846. relaylist.append(relay_entry)
  847. return relaylist
  848. # apply the fallback whitelist and blacklist
  849. def apply_filter_lists(self):
  850. excluded_count = 0
  851. logging.debug('Applying whitelist and blacklist.')
  852. # parse the whitelist and blacklist
  853. whitelist = self.load_relaylist(WHITELIST_FILE_NAME)
  854. blacklist = self.load_relaylist(BLACKLIST_FILE_NAME)
  855. filtered_fallbacks = []
  856. for f in self.fallbacks:
  857. in_whitelist = f.is_in_whitelist(whitelist)
  858. in_blacklist = f.is_in_blacklist(blacklist)
  859. if in_whitelist and in_blacklist:
  860. if BLACKLIST_EXCLUDES_WHITELIST_ENTRIES:
  861. # exclude
  862. excluded_count += 1
  863. logging.debug('Excluding %s: in both blacklist and whitelist.' %
  864. f._fpr)
  865. else:
  866. # include
  867. filtered_fallbacks.append(f)
  868. elif in_whitelist:
  869. # include
  870. filtered_fallbacks.append(f)
  871. elif in_blacklist:
  872. # exclude
  873. excluded_count += 1
  874. logging.debug('Excluding %s: in blacklist.' %
  875. f._fpr)
  876. else:
  877. if INCLUDE_UNLISTED_ENTRIES:
  878. # include
  879. filtered_fallbacks.append(f)
  880. else:
  881. # exclude
  882. excluded_count += 1
  883. logging.debug('Excluding %s: in neither blacklist nor whitelist.' %
  884. f._fpr)
  885. self.fallbacks = filtered_fallbacks
  886. return excluded_count
  887. @staticmethod
  888. def summarise_filters(initial_count, excluded_count):
  889. return '/* Whitelist & blacklist excluded %d of %d candidates. */'%(
  890. excluded_count, initial_count)
  891. # Remove any fallbacks in excess of MAX_FALLBACK_COUNT,
  892. # starting with the lowest-weighted fallbacks
  893. # total_weight should be recalculated after calling this
  894. def exclude_excess_fallbacks(self):
  895. if MAX_FALLBACK_COUNT is not None:
  896. self.fallbacks = self.fallbacks[:MAX_FALLBACK_COUNT]
  897. # Clamp the weight of all fallbacks to MAX_WEIGHT_FRACTION * total_weight
  898. # fallbacks are kept sorted, but since excessive weights are reduced to
  899. # the maximum acceptable weight, these relays end up with equal weights
  900. def clamp_high_weight_fallbacks(self, total_weight):
  901. if MAX_WEIGHT_FRACTION * len(self.fallbacks) < 1.0:
  902. error_str = 'Max Fallback Weight %.3f%% is unachievable'%(
  903. MAX_WEIGHT_FRACTION)
  904. error_str += ' with Current Fallback Count %d.'%(len(self.fallbacks))
  905. if STRICT_FALLBACK_WEIGHTS:
  906. print '#error ' + error_str
  907. else:
  908. print '/* ' + error_str + ' */'
  909. relays_clamped = 0
  910. max_acceptable_weight = total_weight * MAX_WEIGHT_FRACTION
  911. for f in self.fallbacks:
  912. frac_weight = f.fallback_weight_fraction(total_weight)
  913. if frac_weight > MAX_WEIGHT_FRACTION:
  914. relays_clamped += 1
  915. current_weight = f._data['consensus_weight']
  916. # if we already have an original weight, keep it
  917. if (not f._data.has_key('original_consensus_weight')
  918. or f._data['original_consensus_weight'] == current_weight):
  919. f._data['original_consensus_weight'] = current_weight
  920. f._data['consensus_weight'] = max_acceptable_weight
  921. return relays_clamped
  922. # Remove any fallbacks with weights lower than MIN_WEIGHT_FRACTION
  923. # total_weight should be recalculated after calling this
  924. def exclude_low_weight_fallbacks(self, total_weight):
  925. self.fallbacks = filter(
  926. lambda x:
  927. x.fallback_weight_fraction(total_weight) >= MIN_WEIGHT_FRACTION,
  928. self.fallbacks)
  929. def fallback_weight_total(self):
  930. return sum(f._data['consensus_weight'] for f in self.fallbacks)
  931. def fallback_min_weight(self):
  932. if len(self.fallbacks) > 0:
  933. return self.fallbacks[-1]
  934. else:
  935. return None
  936. def fallback_max_weight(self):
  937. if len(self.fallbacks) > 0:
  938. return self.fallbacks[0]
  939. else:
  940. return None
  941. def summarise_fallbacks(self, eligible_count, eligible_weight,
  942. relays_clamped, clamped_weight,
  943. guard_count, target_count, max_count):
  944. # Report:
  945. # the number of fallback directories (with min & max limits);
  946. # #error if below minimum count
  947. # the total weight, min & max fallback proportions
  948. # #error if outside max weight proportion
  949. # Multiline C comment with #error if things go bad
  950. s = '/*'
  951. s += '\n'
  952. s += 'Fallback Directory Summary'
  953. s += '\n'
  954. # Integers don't need escaping in C comments
  955. fallback_count = len(self.fallbacks)
  956. if FALLBACK_PROPORTION_OF_GUARDS is None:
  957. fallback_proportion = ''
  958. else:
  959. fallback_proportion = ' (%d * %f)'%(guard_count,
  960. FALLBACK_PROPORTION_OF_GUARDS)
  961. s += 'Final Count: %d (Eligible %d, Usable %d, Target %d%s'%(
  962. min(max_count, fallback_count),
  963. eligible_count,
  964. fallback_count,
  965. target_count,
  966. fallback_proportion)
  967. if MAX_FALLBACK_COUNT is not None:
  968. s += ', Clamped to %d'%(MAX_FALLBACK_COUNT)
  969. s += ')\n'
  970. if fallback_count < MIN_FALLBACK_COUNT:
  971. s += '*/'
  972. s += '\n'
  973. # We must have a minimum number of fallbacks so they are always
  974. # reachable, and are in diverse locations
  975. s += '#error Fallback Count %d is too low. '%(fallback_count)
  976. s += 'Must be at least %d for diversity. '%(MIN_FALLBACK_COUNT)
  977. s += 'Try adding entries to the whitelist, '
  978. s += 'or setting INCLUDE_UNLISTED_ENTRIES = True.'
  979. s += '\n'
  980. s += '/*'
  981. s += '\n'
  982. total_weight = self.fallback_weight_total()
  983. min_fb = self.fallback_min_weight()
  984. min_weight = min_fb._data['consensus_weight']
  985. min_percent = min_fb.fallback_weight_fraction(total_weight)*100.0
  986. max_fb = self.fallback_max_weight()
  987. max_weight = max_fb._data['consensus_weight']
  988. max_frac = max_fb.fallback_weight_fraction(total_weight)
  989. max_percent = max_frac*100.0
  990. s += 'Final Weight: %d (Eligible %d)'%(total_weight, eligible_weight)
  991. s += '\n'
  992. s += 'Max Weight: %d (%.3f%%) (Clamped to %.3f%%)'%(
  993. max_weight,
  994. max_percent,
  995. TARGET_MAX_WEIGHT_FRACTION*100)
  996. s += '\n'
  997. s += 'Min Weight: %d (%.3f%%) (Clamped to %.3f%%)'%(
  998. min_weight,
  999. min_percent,
  1000. MIN_WEIGHT_FRACTION*100)
  1001. s += '\n'
  1002. if eligible_count != fallback_count:
  1003. s += 'Excluded: %d (Clamped, Below Target, or Low Weight)'%(
  1004. eligible_count - fallback_count)
  1005. s += '\n'
  1006. if relays_clamped > 0:
  1007. s += 'Clamped: %d (%.3f%%) Excess Weight, '%(
  1008. clamped_weight,
  1009. (100.0 * clamped_weight) / total_weight)
  1010. s += '%d High Weight Fallbacks (%.1f%%)'%(
  1011. relays_clamped,
  1012. (100.0 * relays_clamped) / fallback_count)
  1013. s += '\n'
  1014. s += '*/'
  1015. if max_frac > TARGET_MAX_WEIGHT_FRACTION:
  1016. s += '\n'
  1017. # We must restrict the maximum fallback weight, so an adversary
  1018. # at or near the fallback doesn't see too many clients
  1019. error_str = 'Max Fallback Weight %.3f%% is too high. '%(max_frac*100)
  1020. error_str += 'Must be at most %.3f%% for client anonymity.'%(
  1021. TARGET_MAX_WEIGHT_FRACTION*100)
  1022. if STRICT_FALLBACK_WEIGHTS:
  1023. s += '#error ' + error_str
  1024. else:
  1025. s += '/* ' + error_str + ' */'
  1026. return s
  1027. ## Main Function
  1028. def list_fallbacks():
  1029. """ Fetches required onionoo documents and evaluates the
  1030. fallback directory criteria for each of the relays """
  1031. candidates = CandidateList()
  1032. candidates.add_relays()
  1033. guard_count = candidates.count_guards()
  1034. if FALLBACK_PROPORTION_OF_GUARDS is None:
  1035. target_count = guard_count
  1036. else:
  1037. target_count = int(guard_count * FALLBACK_PROPORTION_OF_GUARDS)
  1038. # the maximum number of fallbacks is the least of:
  1039. # - the target fallback count (FALLBACK_PROPORTION_OF_GUARDS * guard count)
  1040. # - the maximum fallback count (MAX_FALLBACK_COUNT)
  1041. if MAX_FALLBACK_COUNT is None:
  1042. max_count = guard_count
  1043. else:
  1044. max_count = min(target_count, MAX_FALLBACK_COUNT)
  1045. candidates.compute_fallbacks()
  1046. initial_count = len(candidates.fallbacks)
  1047. excluded_count = candidates.apply_filter_lists()
  1048. print candidates.summarise_filters(initial_count, excluded_count)
  1049. eligible_count = len(candidates.fallbacks)
  1050. eligible_weight = candidates.fallback_weight_total()
  1051. # print the raw fallback list
  1052. #total_weight = candidates.fallback_weight_total()
  1053. #for x in candidates.fallbacks:
  1054. # print x.fallbackdir_line(total_weight, total_weight)
  1055. # When candidates are excluded, total_weight decreases, and
  1056. # the proportional weight of other candidates increases.
  1057. candidates.exclude_excess_fallbacks()
  1058. total_weight = candidates.fallback_weight_total()
  1059. # When candidates are reweighted, total_weight decreases, and
  1060. # the proportional weight of other candidates increases.
  1061. # Previously low-weight candidates might obtain sufficient proportional
  1062. # weights to be included.
  1063. # Save the weight at which we reweighted fallbacks for the summary.
  1064. pre_clamp_total_weight = total_weight
  1065. relays_clamped = candidates.clamp_high_weight_fallbacks(total_weight)
  1066. # When candidates are excluded, total_weight decreases, and
  1067. # the proportional weight of other candidates increases.
  1068. # No new low weight candidates will be created during exclusions.
  1069. # However, high weight candidates may increase over the maximum proportion.
  1070. # This should not be an issue, except in pathological cases.
  1071. candidates.exclude_low_weight_fallbacks(total_weight)
  1072. total_weight = candidates.fallback_weight_total()
  1073. # check we haven't exceeded TARGET_MAX_WEIGHT_FRACTION
  1074. # since reweighting preserves the orginal sort order,
  1075. # the maximum weights will be at the head of the list
  1076. if len(candidates.fallbacks) > 0:
  1077. max_weight_fb = candidates.fallback_max_weight()
  1078. max_weight = max_weight_fb.fallback_weight_fraction(total_weight)
  1079. if max_weight > TARGET_MAX_WEIGHT_FRACTION:
  1080. error_str = 'Maximum fallback weight: %.3f%% exceeds target %.3f%%. '%(
  1081. max_weight*100.0,
  1082. TARGET_MAX_WEIGHT_FRACTION*100.0)
  1083. error_str += 'Try decreasing REWEIGHTING_FUDGE_FACTOR.'
  1084. if STRICT_FALLBACK_WEIGHTS:
  1085. print '#error ' + error_str
  1086. else:
  1087. print '/* ' + error_str + ' */'
  1088. print candidates.summarise_fallbacks(eligible_count, eligible_weight,
  1089. relays_clamped,
  1090. pre_clamp_total_weight - total_weight,
  1091. guard_count, target_count, max_count)
  1092. else:
  1093. print '/* No Fallbacks met criteria */'
  1094. for s in fetch_source_list():
  1095. print describe_fetch_source(s)
  1096. for x in candidates.fallbacks[:max_count]:
  1097. print x.fallbackdir_line(total_weight, pre_clamp_total_weight)
  1098. #print json.dumps(candidates[x]._data, sort_keys=True, indent=4,
  1099. # separators=(',', ': '), default=json_util.default)
  1100. if __name__ == "__main__":
  1101. list_fallbacks()