Funktionierender Prototyp des Serious Games zur Vermittlung von Wissen zu Software-Engineering-Arbeitsmodellen.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

1 year ago
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306
  1. # -*- test-case-name: twisted.test.test_htb -*-
  2. # Copyright (c) Twisted Matrix Laboratories.
  3. # See LICENSE for details.
  4. """
  5. Hierarchical Token Bucket traffic shaping.
  6. Patterned after U{Martin Devera's Hierarchical Token Bucket traffic
  7. shaper for the Linux kernel<http://luxik.cdi.cz/~devik/qos/htb/>}.
  8. @seealso: U{HTB Linux queuing discipline manual - user guide
  9. <http://luxik.cdi.cz/~devik/qos/htb/manual/userg.htm>}
  10. @seealso: U{Token Bucket Filter in Linux Advanced Routing & Traffic Control
  11. HOWTO<http://lartc.org/howto/lartc.qdisc.classless.html#AEN682>}
  12. """
  13. # TODO: Investigate whether we should be using os.times()[-1] instead of
  14. # time.time. time.time, it has been pointed out, can go backwards. Is
  15. # the same true of os.times?
  16. from time import time
  17. from typing import Optional
  18. from zope.interface import Interface, implementer
  19. from twisted.protocols import pcp
  20. class Bucket:
  21. """
  22. Implementation of a Token bucket.
  23. A bucket can hold a certain number of tokens and it drains over time.
  24. @cvar maxburst: The maximum number of tokens that the bucket can
  25. hold at any given time. If this is L{None}, the bucket has
  26. an infinite size.
  27. @type maxburst: C{int}
  28. @cvar rate: The rate at which the bucket drains, in number
  29. of tokens per second. If the rate is L{None}, the bucket
  30. drains instantaneously.
  31. @type rate: C{int}
  32. """
  33. maxburst: Optional[int] = None
  34. rate: Optional[int] = None
  35. _refcount = 0
  36. def __init__(self, parentBucket=None):
  37. """
  38. Create a L{Bucket} that may have a parent L{Bucket}.
  39. @param parentBucket: If a parent Bucket is specified,
  40. all L{add} and L{drip} operations on this L{Bucket}
  41. will be applied on the parent L{Bucket} as well.
  42. @type parentBucket: L{Bucket}
  43. """
  44. self.content = 0
  45. self.parentBucket = parentBucket
  46. self.lastDrip = time()
  47. def add(self, amount):
  48. """
  49. Adds tokens to the L{Bucket} and its C{parentBucket}.
  50. This will add as many of the C{amount} tokens as will fit into both
  51. this L{Bucket} and its C{parentBucket}.
  52. @param amount: The number of tokens to try to add.
  53. @type amount: C{int}
  54. @returns: The number of tokens that actually fit.
  55. @returntype: C{int}
  56. """
  57. self.drip()
  58. if self.maxburst is None:
  59. allowable = amount
  60. else:
  61. allowable = min(amount, self.maxburst - self.content)
  62. if self.parentBucket is not None:
  63. allowable = self.parentBucket.add(allowable)
  64. self.content += allowable
  65. return allowable
  66. def drip(self):
  67. """
  68. Let some of the bucket drain.
  69. The L{Bucket} drains at the rate specified by the class
  70. variable C{rate}.
  71. @returns: C{True} if the bucket is empty after this drip.
  72. @returntype: C{bool}
  73. """
  74. if self.parentBucket is not None:
  75. self.parentBucket.drip()
  76. if self.rate is None:
  77. self.content = 0
  78. else:
  79. now = time()
  80. deltaTime = now - self.lastDrip
  81. deltaTokens = deltaTime * self.rate
  82. self.content = max(0, self.content - deltaTokens)
  83. self.lastDrip = now
  84. return self.content == 0
  85. class IBucketFilter(Interface):
  86. def getBucketFor(*somethings, **some_kw):
  87. """
  88. Return a L{Bucket} corresponding to the provided parameters.
  89. @returntype: L{Bucket}
  90. """
  91. @implementer(IBucketFilter)
  92. class HierarchicalBucketFilter:
  93. """
  94. Filter things into buckets that can be nested.
  95. @cvar bucketFactory: Class of buckets to make.
  96. @type bucketFactory: L{Bucket}
  97. @cvar sweepInterval: Seconds between sweeping out the bucket cache.
  98. @type sweepInterval: C{int}
  99. """
  100. bucketFactory = Bucket
  101. sweepInterval: Optional[int] = None
  102. def __init__(self, parentFilter=None):
  103. self.buckets = {}
  104. self.parentFilter = parentFilter
  105. self.lastSweep = time()
  106. def getBucketFor(self, *a, **kw):
  107. """
  108. Find or create a L{Bucket} corresponding to the provided parameters.
  109. Any parameters are passed on to L{getBucketKey}, from them it
  110. decides which bucket you get.
  111. @returntype: L{Bucket}
  112. """
  113. if (self.sweepInterval is not None) and (
  114. (time() - self.lastSweep) > self.sweepInterval
  115. ):
  116. self.sweep()
  117. if self.parentFilter:
  118. parentBucket = self.parentFilter.getBucketFor(self, *a, **kw)
  119. else:
  120. parentBucket = None
  121. key = self.getBucketKey(*a, **kw)
  122. bucket = self.buckets.get(key)
  123. if bucket is None:
  124. bucket = self.bucketFactory(parentBucket)
  125. self.buckets[key] = bucket
  126. return bucket
  127. def getBucketKey(self, *a, **kw):
  128. """
  129. Construct a key based on the input parameters to choose a L{Bucket}.
  130. The default implementation returns the same key for all
  131. arguments. Override this method to provide L{Bucket} selection.
  132. @returns: Something to be used as a key in the bucket cache.
  133. """
  134. return None
  135. def sweep(self):
  136. """
  137. Remove empty buckets.
  138. """
  139. for key, bucket in self.buckets.items():
  140. bucket_is_empty = bucket.drip()
  141. if (bucket._refcount == 0) and bucket_is_empty:
  142. del self.buckets[key]
  143. self.lastSweep = time()
  144. class FilterByHost(HierarchicalBucketFilter):
  145. """
  146. A Hierarchical Bucket filter with a L{Bucket} for each host.
  147. """
  148. sweepInterval = 60 * 20
  149. def getBucketKey(self, transport):
  150. return transport.getPeer()[1]
  151. class FilterByServer(HierarchicalBucketFilter):
  152. """
  153. A Hierarchical Bucket filter with a L{Bucket} for each service.
  154. """
  155. sweepInterval = None
  156. def getBucketKey(self, transport):
  157. return transport.getHost()[2]
  158. class ShapedConsumer(pcp.ProducerConsumerProxy):
  159. """
  160. Wraps a C{Consumer} and shapes the rate at which it receives data.
  161. """
  162. # Providing a Pull interface means I don't have to try to schedule
  163. # traffic with callLaters.
  164. iAmStreaming = False
  165. def __init__(self, consumer, bucket):
  166. pcp.ProducerConsumerProxy.__init__(self, consumer)
  167. self.bucket = bucket
  168. self.bucket._refcount += 1
  169. def _writeSomeData(self, data):
  170. # In practice, this actually results in obscene amounts of
  171. # overhead, as a result of generating lots and lots of packets
  172. # with twelve-byte payloads. We may need to do a version of
  173. # this with scheduled writes after all.
  174. amount = self.bucket.add(len(data))
  175. return pcp.ProducerConsumerProxy._writeSomeData(self, data[:amount])
  176. def stopProducing(self):
  177. pcp.ProducerConsumerProxy.stopProducing(self)
  178. self.bucket._refcount -= 1
  179. class ShapedTransport(ShapedConsumer):
  180. """
  181. Wraps a C{Transport} and shapes the rate at which it receives data.
  182. This is a L{ShapedConsumer} with a little bit of magic to provide for
  183. the case where the consumer it wraps is also a C{Transport} and people
  184. will be attempting to access attributes this does not proxy as a
  185. C{Consumer} (e.g. C{loseConnection}).
  186. """
  187. # Ugh. We only wanted to filter IConsumer, not ITransport.
  188. iAmStreaming = False
  189. def __getattr__(self, name):
  190. # Because people will be doing things like .getPeer and
  191. # .loseConnection on me.
  192. return getattr(self.consumer, name)
  193. class ShapedProtocolFactory:
  194. """
  195. Dispense C{Protocols} with traffic shaping on their transports.
  196. Usage::
  197. myserver = SomeFactory()
  198. myserver.protocol = ShapedProtocolFactory(myserver.protocol,
  199. bucketFilter)
  200. Where C{SomeServerFactory} is a L{twisted.internet.protocol.Factory}, and
  201. C{bucketFilter} is an instance of L{HierarchicalBucketFilter}.
  202. """
  203. def __init__(self, protoClass, bucketFilter):
  204. """
  205. Tell me what to wrap and where to get buckets.
  206. @param protoClass: The class of C{Protocol} this will generate
  207. wrapped instances of.
  208. @type protoClass: L{Protocol<twisted.internet.interfaces.IProtocol>}
  209. class
  210. @param bucketFilter: The filter which will determine how
  211. traffic is shaped.
  212. @type bucketFilter: L{HierarchicalBucketFilter}.
  213. """
  214. # More precisely, protoClass can be any callable that will return
  215. # instances of something that implements IProtocol.
  216. self.protocol = protoClass
  217. self.bucketFilter = bucketFilter
  218. def __call__(self, *a, **kw):
  219. """
  220. Make a C{Protocol} instance with a shaped transport.
  221. Any parameters will be passed on to the protocol's initializer.
  222. @returns: A C{Protocol} instance with a L{ShapedTransport}.
  223. """
  224. proto = self.protocol(*a, **kw)
  225. origMakeConnection = proto.makeConnection
  226. def makeConnection(transport):
  227. bucket = self.bucketFilter.getBucketFor(transport)
  228. shapedTransport = ShapedTransport(transport, bucket)
  229. return origMakeConnection(shapedTransport)
  230. proto.makeConnection = makeConnection
  231. return proto