commit 19cca3a04b9b02e94d22ebb877af3ca2ca9ad5e4
Author: Damian Johnson <atagar(a)torproject.org>
Date: Mon Oct 7 21:14:00 2013 -0700
Using @lru_cache for exit policies
The ExitPolicy and ExitPolicyRule classes are a perfect fit for @lru_cache.
They're read-only classes that already do a fair bit of caching. The annotation
lets us avoid doing this ourselves.
---
stem/exit_policy.py | 250 +++++++++++++++++----------------------
stem/util/lru_cache.py | 10 +-
test/unit/exit_policy/policy.py | 22 ----
3 files changed, 114 insertions(+), 168 deletions(-)
diff --git a/stem/exit_policy.py b/stem/exit_policy.py
index 17f3508..930c8bb 100644
--- a/stem/exit_policy.py
+++ b/stem/exit_policy.py
@@ -56,9 +56,16 @@ exiting to a destination is permissible or not. For instance...
============ ===========
"""
+import stem.prereq
import stem.util.connection
import stem.util.enum
+try:
+ # added in python 3.2
+ from collections import lru_cache
+except ImportError:
+ from stem.util.lru_cache import lru_cache
+
AddressType = stem.util.enum.Enum(("WILDCARD", "Wildcard"), ("IPv4", "IPv4"), ("IPv6", "IPv6"))
# Addresses aliased by the 'private' policy. From the tor man page...
@@ -77,21 +84,6 @@ PRIVATE_ADDRESSES = (
)
-# TODO: The ExitPolicyRule could easily be a mutable class if we did the
-# following...
-#
-# * Provided setter methods that acquired an RLock which also wrapped all of
-# our current methods to provide thread safety.
-#
-# * Reset our derived attributes (self._addr_bin, self._mask_bin, and
-# self._str_representation) when we changed something that it was based on.
-#
-# That said, I'm not sure if this is entirely desirable since for most use
-# cases we *want* the caller to have an immutable ExitPolicy (since it
-# reflects something they... well, can't modify). However, I can think of
-# some use cases where we might want to construct custom policies. Maybe make
-# it a CustomExitPolicyRule subclass?
-
def get_config_policy(rules):
"""
Converts an ExitPolicy found in a torrc to a proper exit pattern. This
@@ -155,12 +147,20 @@ class ExitPolicy(object):
if not isinstance(rule, (bytes, unicode, ExitPolicyRule)):
raise TypeError("Exit policy rules can only contain strings or ExitPolicyRules, got a %s (%s)" % (type(rule), rules))
- self._rules = None # lazily loaded series of ExitPolicyRule
- self._input_rules = rules # input rules, only kept until self._rules is set
+ # Unparsed representation of the rules we were constructed with. Our
+ # _get_rules() method consumes this to provide ExitPolicyRule instances.
+ # This is lazily evaluated so we don't need to actually parse the exit
+ # policy if it's never used.
+
+ self._input_rules = rules
+
+ # Result when no rules apply. According to the spec policies default to 'is
+ # allowed', but our microdescriptor policy subclass might want to change
+ # this.
+
self._is_allowed_default = True
- self._summary_representation = None
- self._can_exit_to_cache = {}
+ @lru_cache()
def can_exit_to(self, address = None, port = None, strict = False):
"""
Checks if this policy allows exiting to a given destination or not. If the
@@ -175,18 +175,13 @@ class ExitPolicy(object):
:returns: **True** if exiting to this destination is allowed, **False** otherwise
"""
- if not (address, port, strict) in self._can_exit_to_cache:
- result = self._is_allowed_default
-
- for rule in self._get_rules():
- if rule.is_match(address, port, strict):
- result = rule.is_accept
- break
-
- self._can_exit_to_cache[(address, port, strict)] = result
+ for rule in self._get_rules():
+ if rule.is_match(address, port, strict):
+ return rule.is_accept
- return self._can_exit_to_cache[(address, port, strict)]
+ return self._is_allowed_default
+ @lru_cache()
def is_exiting_allowed(self):
"""
Provides **True** if the policy allows exiting whatsoever, **False**
@@ -194,6 +189,7 @@ class ExitPolicy(object):
"""
rejected_ports = set()
+
for rule in self._get_rules():
if rule.is_accept:
for port in xrange(rule.min_port, rule.max_port + 1):
@@ -207,6 +203,7 @@ class ExitPolicy(object):
return self._is_allowed_default
+ @lru_cache()
def summary(self):
"""
Provides a short description of our policy chain, similar to a
@@ -227,131 +224,110 @@ class ExitPolicy(object):
:returns: **str** with a concise summary for our policy
"""
- if self._summary_representation is None:
- # determines if we're a white-list or blacklist
- is_whitelist = not self._is_allowed_default
+ # determines if we're a white-list or blacklist
+ is_whitelist = not self._is_allowed_default
- for rule in self._get_rules():
- if rule.is_address_wildcard() and rule.is_port_wildcard():
- is_whitelist = not rule.is_accept
- break
+ for rule in self._get_rules():
+ if rule.is_address_wildcard() and rule.is_port_wildcard():
+ is_whitelist = not rule.is_accept
+ break
- # Iterates over the policies and adds the the ports we'll return (ie,
- # allows if a white-list and rejects if a blacklist). Regardless of a
- # port's allow/reject policy, all further entries with that port are
- # ignored since policies respect the first matching policy.
+ # Iterates over the policies and adds the the ports we'll return (ie,
+ # allows if a white-list and rejects if a blacklist). Regardless of a
+ # port's allow/reject policy, all further entries with that port are
+ # ignored since policies respect the first matching policy.
- display_ports, skip_ports = [], set()
+ display_ports, skip_ports = [], set()
- for rule in self._get_rules():
- if not rule.is_address_wildcard():
- continue
- elif rule.is_port_wildcard():
- break
+ for rule in self._get_rules():
+ if not rule.is_address_wildcard():
+ continue
+ elif rule.is_port_wildcard():
+ break
- for port in xrange(rule.min_port, rule.max_port + 1):
- if port in skip_ports:
- continue
+ for port in xrange(rule.min_port, rule.max_port + 1):
+ if port in skip_ports:
+ continue
- # if accept + white-list or reject + blacklist then add
- if rule.is_accept == is_whitelist:
- display_ports.append(port)
+ # if accept + white-list or reject + blacklist then add
+ if rule.is_accept == is_whitelist:
+ display_ports.append(port)
- # all further entries with this port should be ignored
- skip_ports.add(port)
+ # all further entries with this port should be ignored
+ skip_ports.add(port)
- # convert port list to a list of ranges (ie, ['1-3'] rather than [1, 2, 3])
- if display_ports:
- display_ranges, temp_range = [], []
- display_ports.sort()
- display_ports.append(None) # ending item to include last range in loop
+ # convert port list to a list of ranges (ie, ['1-3'] rather than [1, 2, 3])
+ if display_ports:
+ display_ranges, temp_range = [], []
+ display_ports.sort()
+ display_ports.append(None) # ending item to include last range in loop
- for port in display_ports:
- if not temp_range or temp_range[-1] + 1 == port:
- temp_range.append(port)
+ for port in display_ports:
+ if not temp_range or temp_range[-1] + 1 == port:
+ temp_range.append(port)
+ else:
+ if len(temp_range) > 1:
+ display_ranges.append("%i-%i" % (temp_range[0], temp_range[-1]))
else:
- if len(temp_range) > 1:
- display_ranges.append("%i-%i" % (temp_range[0], temp_range[-1]))
- else:
- display_ranges.append(str(temp_range[0]))
-
- temp_range = [port]
- else:
- # everything for the inverse
- is_whitelist = not is_whitelist
- display_ranges = ["1-65535"]
+ display_ranges.append(str(temp_range[0]))
- # constructs the summary string
- label_prefix = "accept " if is_whitelist else "reject "
-
- self._summary_representation = (label_prefix + ", ".join(display_ranges)).strip()
-
- return self._summary_representation
-
- def _set_default_allowed(self, is_allowed_default):
- """
- Generally policies end with either an 'reject \*:\*' or 'accept \*:\*'
- policy, but if it doesn't then is_allowed_default will determine the
- default response for our :meth:`~stem.exit_policy.ExitPolicy.can_exit_to`
- method.
-
- Our default, and tor's, is **True**.
+ temp_range = [port]
+ else:
+ # everything for the inverse
+ is_whitelist = not is_whitelist
+ display_ranges = ["1-65535"]
- :param bool is_allowed_default:
- :meth:`~stem.exit_policy.ExitPolicy.can_exit_to` default when no rules
- apply
- """
+ # constructs the summary string
+ label_prefix = "accept " if is_whitelist else "reject "
- self._is_allowed_default = is_allowed_default
- self._can_exit_to_cache = {}
+ return (label_prefix + ", ".join(display_ranges)).strip()
+ @lru_cache()
def _get_rules(self):
- if self._rules is None:
- rules = []
- is_all_accept, is_all_reject = True, True
-
- for rule in self._input_rules:
- if isinstance(rule, (bytes, unicode)):
- rule = ExitPolicyRule(rule.strip())
+ rules = []
+ is_all_accept, is_all_reject = True, True
- if rule.is_accept:
- is_all_reject = False
- else:
- is_all_accept = False
+ for rule in self._input_rules:
+ if isinstance(rule, (bytes, unicode)):
+ rule = ExitPolicyRule(rule.strip())
- rules.append(rule)
+ if rule.is_accept:
+ is_all_reject = False
+ else:
+ is_all_accept = False
- if rule.is_address_wildcard() and rule.is_port_wildcard():
- break # this is a catch-all, no reason to include more
+ rules.append(rule)
- # If we only have one kind of entry *and* end with a wildcard then
- # we might as well use the simpler version. For instance...
- #
- # reject *:80, reject *:443, reject *:*
- #
- # ... could also be represented as simply...
- #
- # reject *:*
- #
- # This mostly comes up with reject-all policies because the
- # 'reject private:*' appends an extra seven rules that have no
- # effect.
+ if rule.is_address_wildcard() and rule.is_port_wildcard():
+ break # this is a catch-all, no reason to include more
- if rules and (rules[-1].is_address_wildcard() and rules[-1].is_port_wildcard()):
- if is_all_accept:
- rules = [ExitPolicyRule("accept *:*")]
- elif is_all_reject:
- rules = [ExitPolicyRule("reject *:*")]
+ # If we only have one kind of entry *and* end with a wildcard then
+ # we might as well use the simpler version. For instance...
+ #
+ # reject *:80, reject *:443, reject *:*
+ #
+ # ... could also be represented as simply...
+ #
+ # reject *:*
+ #
+ # This mostly comes up with reject-all policies because the
+ # 'reject private:*' appends an extra seven rules that have no
+ # effect.
- self._rules = rules
- self._input_rules = None
+ if rules and (rules[-1].is_address_wildcard() and rules[-1].is_port_wildcard()):
+ if is_all_accept:
+ rules = [ExitPolicyRule("accept *:*")]
+ elif is_all_reject:
+ rules = [ExitPolicyRule("reject *:*")]
- return self._rules
+ self._input_rules = None
+ return rules
def __iter__(self):
for rule in self._get_rules():
yield rule
+ @lru_cache()
def __str__(self):
return ', '.join([str(rule) for rule in self._get_rules()])
@@ -430,7 +406,7 @@ class MicroExitPolicy(ExitPolicy):
rules.append(MicroExitPolicyRule(self.is_accept, int(min_port), int(max_port)))
super(MicroExitPolicy, self).__init__(*rules)
- self._set_default_allowed(not self.is_accept)
+ self._is_allowed_default = not self.is_accept
def __str__(self):
return self._policy
@@ -505,12 +481,6 @@ class ExitPolicyRule(object):
self._apply_addrspec(rule, addrspec)
self._apply_portspec(rule, portspec)
- # The integer representation of our mask and masked address. These are
- # lazily loaded and used by our is_match() method to compare ourselves to
- # other addresses.
-
- self._mask_bin = self._addr_bin = None
-
# Lazily loaded string representation of our policy.
self._str_representation = None
@@ -700,21 +670,17 @@ class ExitPolicyRule(object):
return self._str_representation
+ @lru_cache()
def _get_mask_bin(self):
# provides an integer representation of our mask
- if self._mask_bin is None:
- self._mask_bin = int(stem.util.connection._get_address_binary(self.get_mask(False)), 2)
-
- return self._mask_bin
+ return int(stem.util.connection._get_address_binary(self.get_mask(False)), 2)
+ @lru_cache()
def _get_address_bin(self):
# provides an integer representation of our address
- if self._addr_bin is None:
- self._addr_bin = int(stem.util.connection._get_address_binary(self.address), 2) & self._mask_bin
-
- return self._addr_bin
+ return int(stem.util.connection._get_address_binary(self.address), 2) & self._get_mask_bin()
def _apply_addrspec(self, rule, addrspec):
# Parses the addrspec...
diff --git a/stem/util/lru_cache.py b/stem/util/lru_cache.py
index 5591862..a0b8f1b 100644
--- a/stem/util/lru_cache.py
+++ b/stem/util/lru_cache.py
@@ -20,6 +20,7 @@ from threading import RLock
_CacheInfo = namedtuple("CacheInfo", ["hits", "misses", "maxsize", "currsize"])
+
class _HashedSeq(list):
__slots__ = 'hashvalue'
@@ -30,10 +31,11 @@ class _HashedSeq(list):
def __hash__(self):
return self.hashvalue
+
def _make_key(args, kwds, typed,
- kwd_mark = (object(),),
- fasttypes = {int, str, frozenset, type(None)},
- sorted=sorted, tuple=tuple, type=type, len=len):
+ kwd_mark = (object(),),
+ fasttypes = {int, str, frozenset, type(None)},
+ sorted=sorted, tuple=tuple, type=type, len=len):
'Make a cache key from optionally typed positional and keyword arguments'
key = args
if kwds:
@@ -49,6 +51,7 @@ def _make_key(args, kwds, typed,
return key[0]
return _HashedSeq(key)
+
def lru_cache(maxsize=100, typed=False):
"""Least-recently-used cache decorator.
@@ -146,7 +149,6 @@ def lru_cache(maxsize=100, typed=False):
# empty the oldest link and make it the new root
root = nonlocal_root[0] = oldroot[NEXT]
oldkey = root[KEY]
- oldvalue = root[RESULT]
root[KEY] = root[RESULT] = None
# now update the cache dictionary for the new links
del cache[oldkey]
diff --git a/test/unit/exit_policy/policy.py b/test/unit/exit_policy/policy.py
index 8659b68..161bae0 100644
--- a/test/unit/exit_policy/policy.py
+++ b/test/unit/exit_policy/policy.py
@@ -47,28 +47,6 @@ class TestExitPolicy(unittest.TestCase):
policy = ExitPolicy(*"reject *:80, reject *:443, reject *:*".split(","))
self.assertEquals(ExitPolicy("reject *:*"), policy)
- def test_set_default_allowed(self):
- policy = ExitPolicy('reject *:80', 'accept *:443')
-
- # our default for being allowed defaults to True
- self.assertFalse(policy.can_exit_to("75.119.206.243", 80))
- self.assertTrue(policy.can_exit_to("75.119.206.243", 443))
- self.assertTrue(policy.can_exit_to("75.119.206.243", 999))
-
- policy._set_default_allowed(False)
- self.assertFalse(policy.can_exit_to("75.119.206.243", 80))
- self.assertTrue(policy.can_exit_to("75.119.206.243", 443))
- self.assertFalse(policy.can_exit_to("75.119.206.243", 999))
-
- # Our is_exiting_allowed() is also influcenced by this flag if we lack any
- # 'accept' rules.
-
- policy = ExitPolicy()
- self.assertTrue(policy.is_exiting_allowed())
-
- policy._set_default_allowed(False)
- self.assertFalse(policy.is_exiting_allowed())
-
def test_can_exit_to(self):
# Basic sanity test for our can_exit_to() method. Most of the interesting
# use cases (ip masks, wildcards, etc) are covered by the ExitPolicyRule
