fbe825fbb99f3a9e9d90df03966362411357571a
[util-vserver.git] / python / bwlimit.py
1 #!/usr/bin/python
2
3 # Bandwidth limit module for PlanetLab nodes. The intent is to use the
4 # Hierarchical Token Bucket (HTB) queueing discipline (qdisc) to allow
5 # slices to fairly share access to available node bandwidth. We
6 # currently define three classes of "available node bandwidth":
7 #
8 # 1. Available hardware bandwidth (bwmax): The maximum rate of the
9 # hardware.
10 #
11 # 2. Available capped bandwidth (bwcap): The maximum rate allowed to
12 # non-exempt destinations. By default, equal to bwmax, but may be
13 # lowered by PIs.
14 #
15 # 3. Available uncapped ("exempt") bandwidth: The difference between
16 # bwmax and what is currently being used of bwcap, or the maximum rate
17 # allowed to destinations exempt from caps (e.g., Internet2).
18 #
19 # All three classes of bandwidth are fairly shared according to the
20 # notion of "shares". For instance, if the node is capped at 5 Mbps,
21 # there are N slices, and each slice has 1 share, then each slice
22 # should get at least 5/N Mbps of bandwidth. How HTB is implemented
23 # makes this statement a little too simplistic. What it really means
24 # is that during any single time period, only a certain number of
25 # bytes can be sent onto the wire. Each slice is guaranteed that at
26 # least some small number of its bytes will be sent. Whatever is left
27 # over from the budget, is split in proportion to the number of shares
28 # each slice has.
29 #
30 # Even if the node is not capped at a particular limit (bwcap ==
31 # bwmax), this module enforces fair share access to bwmax. Also, if
32 # the node is capped at a particular limit, rules may optionally be
33 # defined that classify certain packets into the "exempt" class. This
34 # class receives whatever bandwidth is leftover between bwcap and
35 # bwmax; slices fairly share this bandwidth as well.
36 #
37 # The root context is exempt from sharing and can send as much as it
38 # needs to.
39 #
40 # Some relevant URLs:
41 #
42 # 1. http://lartc.org/howto               for how to use tc
43 # 2. http://luxik.cdi.cz/~devik/qos/htb/  for info on HTB
44 #
45 # Andy Bavier <acb@cs.princeton.edu>
46 # Mark Huang <mlhuang@cs.princeton.edu>
47 # Copyright (C) 2006 The Trustees of Princeton University
48 #
49 # $Id: bwlimit.py,v 1.10 2006/03/14 22:57:50 smuir Exp $
50 #
51
52 import sys, os, re, getopt
53 from sets import Set
54 import pwd
55
56
57 # Where the tc binary lives
58 TC = "/sbin/tc"
59
60 # Default interface
61 dev = "eth0"
62
63 # Verbosity level
64 verbose = 0
65
66 # bwmin should be small enough that it can be considered negligibly
67 # slow compared to the hardware. 8 bits/second appears to be the
68 # smallest value supported by tc.
69 bwmin = 8
70
71 # bwmax should be large enough that it can be considered at least as
72 # fast as the hardware.
73 bwmax = 1000*1000*1000
74
75 # quantum is the maximum number of bytes that can be borrowed by a
76 # share (or slice, if each slice gets 1 share) in one time period
77 # (with HZ=1000, 1 ms). If multiple slices are competing for bandwidth
78 # above their guarantees, and each is attempting to borrow up to the
79 # node bandwidth cap, quantums control how the excess bandwidth is
80 # distributed. Slices with 2 shares will borrow twice the amount in
81 # one time period as slices with 1 share, so averaged over time, they
82 # will get twice as much of the excess bandwidth. The value should be
83 # as small as possible and at least 1 MTU. By default, it would be
84 # calculated as bwmin/10, but since we use such small a value for
85 # bwmin, it's better to just set it to a value safely above 1 Ethernet
86 # MTU.
87 quantum = 1600
88
89 # cburst is the maximum number of bytes that can be burst onto the
90 # wire in one time period (with HZ=1000, 1 ms). If multiple slices
91 # have data queued for transmission, cbursts control how long each
92 # slice can have the wire for. If not specified, it is set to the
93 # smallest possible value that would enable the slice's "ceil" rate
94 # (usually the node bandwidth cap), to be reached if a slice was able
95 # to borrow enough bandwidth to do so. For now, it's unclear how or if
96 # to relate this to the notion of shares, so just let tc set the
97 # default.
98 cburst = None
99
100 # There is another parameter that controls how bandwidth is allocated
101 # between slices on nodes that is outside the scope of HTB. We enforce
102 # a 16 GByte/day total limit on each slice, which works out to about
103 # 1.5mbit. If a slice exceeds this byte limit before the day finishes,
104 # it is capped at (i.e., its "ceil" rate is set to) the smaller of the
105 # node bandwidth cap or 1.5mbit. pl_mom is in charge of enforcing this
106 # rule and executes this script to override "ceil".
107
108 # We support multiple bandwidth limits, by reserving the top nibble of
109 # the minor classid to be the "subclassid". Theoretically, we could
110 # support up to 15 subclasses, but for now, we only define two: the
111 # "default" subclass 1:10 that is capped at the node bandwidth cap (in
112 # this example, 5mbit) and the "exempt" subclass 1:20 that is capped
113 # at bwmax (i.e., not capped). The 1:1 parent class exists only to
114 # make the borrowing model work. All bandwidth above minimum
115 # guarantees is fairly shared (in this example, slice 2 is guaranteed
116 # at least 1mbit in addition to fair access to the rest), subject to
117 # the restrictions of the class hierarchy: namely, that the total
118 # bandwidth to non-exempt destinations should not exceed the node
119 # bandwidth cap.
120 #
121 #                         1:
122 #                         |
123 #                    1:1 (1gbit)
124 #           ______________|_____________
125 #          |                            |
126 #   1:10 (8bit, 5mbit)           1:20 (8bit, 1gbit)
127 #          |                            |
128 # 1:1000 (8bit, 5mbit),        1:2000 (8bit, 1gbit),
129 # 1:1001 (8bit, 5mbit),        1:2001 (8bit, 1gbit),
130 # 1:1002 (1mbit, 5mbit),       1:2002 (1mbit, 1gbit),
131 # ...                          ...
132 # 1:1FFF (8bit, 5mbit)         1:2FFF (8bit, 1gbit)
133 #
134 default_minor = 0x1000
135 exempt_minor = 0x2000
136
137 # root_xid is for the root context. The root context is exempt from
138 # fair sharing in both the default and exempt subclasses. The root
139 # context gets 5 shares by default.
140 root_xid = 0x0000
141 root_share = 5
142
143 # default_xid is for unclassifiable packets. Packets should not be
144 # classified here very often. They can be if a slice's HTB classes are
145 # deleted before its processes are. Each slice gets 1 share by
146 # default.
147 default_xid = 0x0FFF
148 default_share = 1
149
150 # See tc_util.c and http://physics.nist.gov/cuu/Units/binary.html. Be
151 # warned that older versions of tc interpret "kbps", "mbps", "mbit",
152 # and "kbit" to mean (in this system) "kibps", "mibps", "mibit", and
153 # "kibit" and that if an older version is installed, all rates will
154 # be off by a small fraction.
155 suffixes = {
156     "":         1,
157     "bit":      1,
158     "kibit":    1024,
159     "kbit":     1000,
160     "mibit":    1024*1024,
161     "mbit":     1000000,
162     "gibit":    1024*1024*1024,
163     "gbit":     1000000000,
164     "tibit":    1024*1024*1024*1024,
165     "tbit":     1000000000000,
166     "bps":      8,
167     "kibps":    8*1024,
168     "kbps":     8000,
169     "mibps":    8*1024*1024,
170     "mbps":     8000000,
171     "gibps":    8*1024*1024*1024,
172     "gbps":     8000000000,
173     "tibps":    8*1024*1024*1024*1024,
174     "tbps":     8000000000000
175 }
176
177
178 # Parses an integer or a tc rate string (e.g., 1.5mbit) into bits/second
179 def get_tc_rate(s):
180     if type(s) == int:
181         return s
182     m = re.match(r"([0-9.]+)(\D*)", s)
183     if m is None:
184         return -1
185     suffix = m.group(2).lower()
186     if suffixes.has_key(suffix):
187         return int(float(m.group(1)) * suffixes[suffix])
188     else:
189         return -1
190
191
192 # Prints a tc rate string
193 def format_tc_rate(rate):
194     if rate >= 1000000:
195         return "%.0fmbit" % (rate / 1000000.)
196     elif rate >= 1000:
197         return "%.0fkbit" % (rate / 1000.)
198     else:
199         return "%.0fbit" % rate
200
201
202 # Parse /etc/planetlab/bwcap (or equivalent)
203 def read_bwcap(bwcap_file):
204     bwcap = bwmax
205     try:
206         fp = open(bwcap_file, "r")
207         line = fp.readline().strip()
208         if line:
209             bwcap = get_tc_rate(line)
210     except:
211         pass
212     if bwcap == -1:
213         bwcap = bwmax
214     return bwcap
215
216
217 # Get current (live) value of bwcap
218 def get_bwcap(dev = dev):
219
220     state = tc("-d class show dev %s" % dev)
221     base_re = re.compile(r"class htb 1:10 parent 1:1 .*ceil ([^ ]+) .*")
222     base_classes = filter(None, map(base_re.match, state))
223     if not base_classes:
224         return -1
225     if len(base_classes) > 1:
226         raise Exception, "unable to get current bwcap"
227     return get_tc_rate(base_classes[0].group(1))
228
229
230 # Get slice xid (500) from slice name ("500" or "princeton_mlh") or
231 # slice name ("princeton_mlh") from slice xid (500).
232 def get_slice(xid_or_name):
233
234     if xid_or_name == root_xid:
235         return "root"
236     if xid_or_name == default_xid:
237         return "default"
238     if isinstance(xid_or_name, (int, long)):
239         try:
240             return pwd.getpwuid(xid_or_name).pw_name
241         except KeyError:
242             pass
243     else:
244         try:
245             try:
246                 return int(xid_or_name)
247             except ValueError:
248                 pass
249             return pwd.getpwnam(xid_or_name).pw_uid
250         except KeyError:
251             pass
252
253     return None
254
255
256 # Shortcut for running a command
257 def run(cmd, input = None):
258     try:
259         if verbose:
260             sys.stderr.write("Executing: " + cmd + "\n")
261         if input is None:
262             fileobj = os.popen(cmd, "r")
263             output = fileobj.readlines()
264         else:
265             fileobj = os.popen(cmd, "w")
266             fileobj.write(input)
267             output = None
268         if fileobj.close() is None:
269             return output
270     except Exception, e:
271         pass
272     return None
273
274
275 # Shortcut for running a tc command
276 def tc(cmd):
277     return run(TC + " " + cmd)
278
279
280 # (Re)initialize the bandwidth limits on this node
281 def init(dev, bwcap):
282
283     # load the module used to manage exempt classes
284     run("/sbin/modprobe ip_set_iphash")
285
286     # Delete root qdisc 1: if it exists. This will also automatically
287     # delete any child classes.
288     for line in tc("qdisc show dev %s" % dev):
289         # Search for the root qdisc 1:
290         m = re.match(r"qdisc htb 1:", line)
291         if m is not None:
292             tc("qdisc del dev %s root handle 1:" % dev)
293             break
294
295     # Initialize HTB. The "default" clause specifies that if a packet
296     # fails classification, it should go into the class with handle
297     # 1FFF.
298     tc("qdisc add dev %s root handle 1: htb default %x" % \
299        (dev, default_minor | default_xid))
300
301     # Set up a parent class from which all subclasses borrow.
302     tc("class add dev %s parent 1: classid 1:1 htb rate %dbit" % \
303        (dev, bwmax))
304
305     # Set up a subclass that represents the node bandwidth cap. We
306     # allow each slice to borrow up to this rate, so it is also
307     # usually the "ceil" rate for each slice.
308     tc("class add dev %s parent 1:1 classid 1:10 htb rate %dbit ceil %dbit" % \
309        (dev, bwmin, bwcap))
310
311     # Set up a subclass that represents "exemption" from the node
312     # bandwidth cap. Once the node bandwidth cap is reached, bandwidth
313     # to exempt destinations can still be fairly shared up to bwmax.
314     tc("class add dev %s parent 1:1 classid 1:20 htb rate %dbit ceil %dbit" % \
315        (dev, bwmin, bwmax))
316
317     # Set up the root class (and tell VNET what it is). Packets sent
318     # by root end up here and are capped at the node bandwidth
319     # cap.
320     on(root_xid, dev, share = root_share)
321     file("/proc/sys/vnet/root_class", "w").write("%d" % ((1 << 16) | default_minor | root_xid))
322
323     # Set up the default class. Packets that fail classification end
324     # up here.
325     on(default_xid, dev, share = default_share)
326
327
328 # Get the bandwidth limits for a particular slice xid as a tuple (xid,
329 # share, minrate, maxrate), or all classes as a list of tuples.
330 def get(xid = None, dev = dev):
331     if xid is None:
332         ret = []
333     else:
334         ret = None
335
336     # class htb 1:1002 parent 1:10 leaf 81b3: prio 1 rate 8bit ceil 5000Kbit burst 1600b cburst 4Kb
337     for line in tc("-d class show dev %s" % dev):
338         # Search for child classes of 1:10
339         m = re.match(r"class htb 1:([0-9a-f]+) parent 1:10", line)
340         if m is None:
341             continue
342
343         # If we are looking for a particular class
344         classid = int(m.group(1), 16) & default_xid
345         if xid is not None and xid != classid:
346             continue
347
348         # Parse share
349         share = 1
350         m = re.search(r"quantum (\d+)", line)
351         if m is not None:
352             share = int(m.group(1)) / quantum
353
354         # Parse minrate
355         minrate = bwmin
356         m = re.search(r"rate (\w+)", line)
357         if m is not None:
358             minrate = get_tc_rate(m.group(1))
359
360         # Parse maxrate 
361         maxrate = bwmax
362         m = re.search(r"ceil (\w+)", line)
363         if m is not None:
364             maxrate = get_tc_rate(m.group(1))
365
366         if xid is None:
367             # Return a list of parameters
368             ret.append((classid, share, minrate, maxrate))
369         else:
370             # Return the parameters for this class
371             ret = (classid, share, minrate, maxrate)
372             break
373
374     return ret
375
376
377 # Apply specified bandwidth limit to the specified slice xid
378 def on(xid, dev = dev, share = None, minrate = None, maxrate = None):
379     # Get defaults from current state if available
380     cap = get(xid, dev)
381     if cap is not None:
382         if share is None:
383             share = cap[1]
384         if minrate is None:
385             minrate = cap[2]
386         if maxrate is None:
387             maxrate = cap[3]
388
389     # Figure out what the current node bandwidth cap is
390     bwcap = bwmax
391     for line in tc("-d class show dev %s" % dev):
392         # Search for 1:10
393         m = re.match(r"class htb 1:10.*ceil (\w+)", line)
394         if m is not None:
395             bwcap = get_tc_rate(m.group(1))
396             break
397
398     # Set defaults
399     if share is None:
400         share = default_share
401     if minrate is None:
402         minrate = bwmin
403     else:
404         minrate = get_tc_rate(minrate)
405     if maxrate is None:
406         maxrate = bwcap
407     else:
408         maxrate = get_tc_rate(maxrate)
409
410     # Sanity checks
411     if maxrate > bwcap:
412         maxrate = bwcap
413     if minrate > maxrate:
414         minrate = maxrate
415
416     # Set up subclasses for the slice
417     tc("class replace dev %s parent 1:10 classid 1:%x htb rate %dbit ceil %dbit quantum %d" % \
418        (dev, default_minor | xid, minrate, maxrate, share * quantum))
419
420     tc("class replace dev %s parent 1:20 classid 1:%x htb rate %dbit ceil %dbit quantum %d" % \
421        (dev, exempt_minor | xid, minrate, bwmax, share * quantum))
422
423     # Attach a FIFO to each subclass, which helps to throttle back
424     # processes that are sending faster than the token buckets can
425     # support.
426     tc("qdisc replace dev %s parent 1:%x handle %x pfifo" % \
427        (dev, default_minor | xid, default_minor | xid))
428
429     tc("qdisc replace dev %s parent 1:%x handle %x pfifo" % \
430        (dev, exempt_minor | xid, exempt_minor | xid))
431
432
433 # Remove class associated with specified slice xid. If further packets
434 # are seen from this slice, they will be classified into the default
435 # class 1:1FFF.
436 def off(xid, dev = dev):
437     cap = get(xid, dev)
438     if cap is not None:
439         tc("class del dev %s classid 1:%x" % (dev, default_minor | xid))
440         tc("class del dev %s classid 1:%x" % (dev, exempt_minor | xid))
441
442
443 def exempt_init(group_name, node_ips):
444
445     # Clean up
446     iptables = "/sbin/iptables -t vnet %s POSTROUTING" 
447     run(iptables % "-F")
448     run("/sbin/ipset -X " + group_name)
449
450     # Create a hashed IP set of all of these destinations
451     lines = ["-N %s iphash" % group_name]
452     add_cmd = "-A %s " % group_name
453     lines += [(add_cmd + ip) for ip in node_ips]
454     lines += ["COMMIT"]
455     restore = "\n".join(lines) + "\n"
456     run("/sbin/ipset -R", restore)
457
458     # Add rule to match on destination IP set
459     run((iptables + " -m set --set %s dst -j CLASSIFY --set-class 1:%x") %
460         ("-A", group_name, exempt_minor))
461
462
463 def usage():
464     bwcap_description = format_tc_rate(get_bwcap())
465         
466     print """
467 Usage:
468
469 %s [OPTION]... [COMMAND] [ARGUMENT]...
470
471 Options:
472         -d device       Network interface (default: %s)
473         -r rate         Node bandwidth cap (default: %s)
474         -q quantum      Share multiplier (default: %d bytes)
475         -h              This message
476
477 Commands:
478         init
479                 (Re)initialize bandwidth caps.
480         on slice [share] [minrate] [maxrate]
481                 Set bandwidth cap for the specified slice
482         off slice
483                 Remove bandwidth caps for the specified slice
484         get
485                 Get all bandwidth caps
486         get slice
487                 Get bandwidth caps for the specified slice
488         getcap slice
489                 Get maxrate for the specified slice
490         setcap slice maxrate
491                 Set maxrate for the specified slice
492 """ % (sys.argv[0], dev, bwcap_description, quantum)
493     sys.exit(1)
494     
495
496 def main():
497     global dev, quantum, verbose
498
499     # Defaults
500     bwcap = get_bwcap()
501
502     (opts, argv) = getopt.getopt(sys.argv[1:], "f:d:r:g:q:vh")
503     for (opt, optval) in opts:
504         if opt == '-d':
505             dev = optval
506         elif opt == '-r':
507             bwcap = get_tc_rate(optval)
508         elif opt == '-q':
509             quantum = int(optval)
510         elif opt == '-v':
511             verbose += 1
512         elif opt == '-h':
513             usage()
514
515     if len(argv):
516         if argv[0] == "init" or (argv[0] == "on" and len(argv) == 1):
517             # (Re)initialize
518             init(dev, get_tc_rate(bwcap))
519
520         elif argv[0] == "get" or argv[0] == "show":
521             # Show
522             if len(argv) >= 2:
523                 # Show a particular slice
524                 xid = get_slice(argv[1])
525                 if xid is None:
526                     sys.stderr.write("Error: Invalid slice name or context '%s'\n" % argv[1])
527                     usage()
528                 caps = [get(xid, dev)]
529             else:
530                 # Show all slices
531                 caps = get(None, dev)
532
533             for (xid, share, minrate, maxrate) in caps:
534                 slice = get_slice(xid)
535                 if slice is None:
536                     # Orphaned (not associated with a slice) class
537                     slice = "%d?" % xid
538                 print "%s %d %s %s" % \
539                       (slice, share, format_tc_rate(minrate), format_tc_rate(maxrate))
540
541         elif len(argv) >= 2:
542             # slice, ...
543             xid = get_slice(argv[1])
544             if xid is None:
545                 sys.stderr.write("Error: Invalid slice name or context '%s'\n" % argv[1])
546                 usage()
547
548             if argv[0] == "on" or argv[0] == "add" or argv[0] == "replace":
549                 # Enable cap
550                 args = []
551                 if len(argv) >= 3:
552                     # ... share, minrate, maxrate
553                     casts = [int, get_tc_rate, get_tc_rate]
554                     for i, arg in enumerate(argv[2:]):
555                         if i >= len(casts):
556                             break
557                         args.append(casts[i](arg))
558                 on(xid, dev, *args)
559
560             elif argv[0] == "off" or argv[0] == "del":
561                 # Disable cap
562                 off(xid, dev)
563
564             # Backward compatibility with old resman script
565             elif argv[0] == "getcap":
566                 # Get maxrate
567                 cap = get(xid, dev)
568                 if cap is not None:
569                     (xid, share, minrate, maxrate) = cap
570                     print format_tc_rate(maxrate)
571
572             # Backward compatibility with old resman script
573             elif argv[0] == "setcap":
574                 if len(argv) >= 3:
575                     # Set maxrate
576                     on(xid, dev, maxrate = get_tc_rate(argv[2]))
577                 else:
578                     usage()
579
580             else:
581                 usage()
582
583         else:
584             usage()
585
586
587 if __name__ == '__main__':
588     main()