5f35fe8ca3c5fb69e0623066b00c320922a65af8
[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.11 2006/03/15 16:41:21 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 def get_tc_rate(s):
179     """
180     Parses an integer or a tc rate string (e.g., 1.5mbit) into bits/second
181     """
182
183     if type(s) == int:
184         return s
185     m = re.match(r"([0-9.]+)(\D*)", s)
186     if m is None:
187         return -1
188     suffix = m.group(2).lower()
189     if suffixes.has_key(suffix):
190         return int(float(m.group(1)) * suffixes[suffix])
191     else:
192         return -1
193
194
195 def format_tc_rate(rate):
196     """
197     Formats a bits/second rate into a tc rate string
198     """
199
200     if rate >= 1000000000 and (rate % 1000000000) == 0:
201         return "%.0fgbit" % (rate / 1000000000.)
202     elif rate >= 1000000 and (rate % 1000000) == 0:
203         return "%.0fmbit" % (rate / 1000000.)
204     elif rate >= 1000:
205         return "%.0fkbit" % (rate / 1000.)
206     else:
207         return "%.0fbit" % rate
208
209
210 # Parse /etc/planetlab/bwcap (or equivalent)
211 def read_bwcap(bwcap_file):
212     bwcap = bwmax
213     try:
214         fp = open(bwcap_file, "r")
215         line = fp.readline().strip()
216         if line:
217             bwcap = get_tc_rate(line)
218     except:
219         pass
220     if bwcap == -1:
221         bwcap = bwmax
222     return bwcap
223
224
225 def get_bwcap(dev = dev):
226     """
227     Get the current (live) value of the node bandwidth cap
228     """
229
230     state = tc("-d class show dev %s" % dev)
231     base_re = re.compile(r"class htb 1:10 parent 1:1 .*ceil ([^ ]+) .*")
232     base_classes = filter(None, map(base_re.match, state))
233     if not base_classes:
234         return -1
235     if len(base_classes) > 1:
236         raise Exception, "unable to get current bwcap"
237     return get_tc_rate(base_classes[0].group(1))
238
239
240 def get_slice(xid):
241     """
242     Get slice name ("princeton_mlh") from slice xid (500)
243     """
244
245     if xid == root_xid:
246         return "root"
247     if xid == default_xid:
248         return "default"
249     try:
250         return pwd.getpwuid(xid).pw_name
251     except KeyError:
252         pass
253
254     return None
255
256 def get_xid(slice):
257     """
258     Get slice xid ("princeton_mlh") from slice name ("500" or "princeton_mlh")
259     """
260
261     if slice == "root":
262         return root_xid
263     if slice == "default":
264         return default_xid
265     try:
266         try:
267             return int(slice)
268         except ValueError:
269             pass
270         return pwd.getpwnam(slice).pw_uid
271     except KeyError:
272         pass
273
274     return None
275
276 def run(cmd, input = None):
277     """
278     Shortcut for running a shell command
279     """
280
281     try:
282         if verbose:
283             sys.stderr.write("Executing: " + cmd + "\n")
284         if input is None:
285             fileobj = os.popen(cmd, "r")
286             output = fileobj.readlines()
287         else:
288             fileobj = os.popen(cmd, "w")
289             fileobj.write(input)
290             output = None
291         if fileobj.close() is None:
292             return output
293     except Exception, e:
294         pass
295     return None
296
297
298 def tc(cmd):
299     """
300     Shortcut for running a tc command
301     """
302
303     return run(TC + " " + cmd)
304
305
306 def init(dev, bwcap):
307     """
308     (Re)initialize the bandwidth limits on this node
309     """
310
311     # load the module used to manage exempt classes
312     run("/sbin/modprobe ip_set_iphash")
313
314     # Delete root qdisc 1: if it exists. This will also automatically
315     # delete any child classes.
316     for line in tc("qdisc show dev %s" % dev):
317         # Search for the root qdisc 1:
318         m = re.match(r"qdisc htb 1:", line)
319         if m is not None:
320             tc("qdisc del dev %s root handle 1:" % dev)
321             break
322
323     # Initialize HTB. The "default" clause specifies that if a packet
324     # fails classification, it should go into the class with handle
325     # 1FFF.
326     tc("qdisc add dev %s root handle 1: htb default %x" % \
327        (dev, default_minor | default_xid))
328
329     # Set up a parent class from which all subclasses borrow.
330     tc("class add dev %s parent 1: classid 1:1 htb rate %dbit" % \
331        (dev, bwmax))
332
333     # Set up a subclass that represents the node bandwidth cap. We
334     # allow each slice to borrow up to this rate, so it is also
335     # usually the "ceil" rate for each slice.
336     tc("class add dev %s parent 1:1 classid 1:10 htb rate %dbit ceil %dbit" % \
337        (dev, bwmin, bwcap))
338
339     # Set up a subclass that represents "exemption" from the node
340     # bandwidth cap. Once the node bandwidth cap is reached, bandwidth
341     # to exempt destinations can still be fairly shared up to bwmax.
342     tc("class add dev %s parent 1:1 classid 1:20 htb rate %dbit ceil %dbit" % \
343        (dev, bwmin, bwmax))
344
345     # Set up the root class (and tell VNET what it is). Packets sent
346     # by root end up here and are capped at the node bandwidth
347     # cap.
348     on(root_xid, dev, share = root_share)
349     file("/proc/sys/vnet/root_class", "w").write("%d" % ((1 << 16) | default_minor | root_xid))
350
351     # Set up the default class. Packets that fail classification end
352     # up here.
353     on(default_xid, dev, share = default_share)
354
355
356 def get(xid = None, dev = dev):
357     """
358     Get the bandwidth limits and current byte totals for a
359     particular slice xid as a tuple (xid, share, minrate, maxrate,
360     minexemptrate, maxexemptrate, bytes, exemptbytes), or all classes
361     as a list of such tuples.
362     """
363
364     if xid is None:
365         ret = []
366     else:
367         ret = None
368
369     rates = {}
370     rate = None
371
372     # ...
373     # class htb 1:1000 parent 1:10 leaf 1000: prio 0 quantum 8000 rate 8bit ceil 10000Kbit ...
374     #  Sent 6851486 bytes 49244 pkt (dropped 0, overlimits 0 requeues 0)
375     # ...
376     # class htb 1:2000 parent 1:20 leaf 2000: prio 0 quantum 8000 rate 8bit ceil 1000Mbit ...
377     #  Sent 0 bytes 0 pkt (dropped 0, overlimits 0 requeues 0) 
378     # ...
379     for line in tc("-s -d class show dev %s" % dev):
380         # Rate parameter line
381         params = re.match(r"class htb 1:([0-9a-f]+) parent 1:(10|20)", line)
382         # Statistics line
383         stats = re.match(r".* Sent ([0-9]+) bytes", line)
384         # Another class
385         ignore = re.match(r"class htb", line)
386
387         if params is not None:
388             # Which class
389             if params.group(2) == "10":
390                 min = 'min'
391                 max = 'max'
392                 bytes = 'bytes'
393             else:
394                 min = 'minexempt'
395                 max = 'maxexempt'
396                 bytes = 'exemptbytes'
397
398             # Slice ID
399             id = int(params.group(1), 16) & 0x0FFF;
400
401             if rates.has_key(id):
402                 rate = rates[id]
403             else:
404                 rate = {'id': id}
405
406             # Parse share
407             rate['share'] = 1
408             m = re.search(r"quantum (\d+)", line)
409             if m is not None:
410                 rate['share'] = int(m.group(1)) / quantum
411
412             # Parse minrate
413             rate[min] = bwmin
414             m = re.search(r"rate (\w+)", line)
415             if m is not None:
416                 rate[min] = get_tc_rate(m.group(1))
417
418             # Parse maxrate
419             rate[max] = bwmax
420             m = re.search(r"ceil (\w+)", line)
421             if m is not None:
422                 rate[max] = get_tc_rate(m.group(1))
423
424             # Which statistics to parse
425             rate['stats'] = bytes
426
427             rates[id] = rate
428
429         elif stats is not None:
430             if rate is not None:
431                 rate[rate['stats']] = int(stats.group(1))
432
433         elif ignore is not None:
434             rate = None
435
436         # Keep parsing until we get everything
437         if rate is not None and \
438            rate.has_key('min') and rate.has_key('minexempt') and \
439            rate.has_key('max') and rate.has_key('maxexempt') and \
440            rate.has_key('bytes') and rate.has_key('exemptbytes'):
441             params = (rate['id'], rate['share'],
442                       rate['min'], rate['max'],
443                       rate['minexempt'], rate['maxexempt'],
444                       rate['bytes'], rate['exemptbytes'])
445             if xid is None:
446                 # Return a list of parameters
447                 ret.append(params)
448                 rate = None
449             elif xid == rate['id']:
450                 # Return the parameters for this class
451                 ret = params
452                 break
453
454     return ret
455
456
457 def on(xid, dev = dev, share = None, minrate = None, maxrate = None, minexemptrate = None, maxexemptrate = None):
458     """
459     Apply specified bandwidth limit to the specified slice xid
460     """
461
462     # Get defaults from current state if available
463     cap = get(xid, dev)
464     if cap is not None:
465         if share is None:
466             share = cap[1]
467         if minrate is None:
468             minrate = cap[2]
469         if maxrate is None:
470             maxrate = cap[3]
471         if minexemptrate is None:
472             minexemptrate = cap[4]
473         if maxexemptrate is None:
474             maxexemptrate = cap[5]
475
476     # Figure out what the current node bandwidth cap is
477     bwcap = get_bwcap()
478
479     # Set defaults
480     if share is None:
481         share = default_share
482     if minrate is None:
483         minrate = bwmin
484     else:
485         minrate = get_tc_rate(minrate)
486     if maxrate is None:
487         maxrate = bwcap
488     else:
489         maxrate = get_tc_rate(maxrate)
490     if minexemptrate is None:
491         minexemptrate = minrate
492     else:
493         minexemptrate = get_tc_rate(minexemptrate)
494     if maxexemptrate is None:
495         maxexemptrate = bwmax
496     else:
497         maxexemptrate = get_tc_rate(maxexemptrate)
498
499     # Sanity checks
500     if maxrate > bwcap:
501         maxrate = bwcap
502     if minrate > maxrate:
503         minrate = maxrate
504     if maxexemptrate > bwmax:
505         maxexemptrate = bwmax
506     if minexemptrate > maxexemptrate:
507         minexemptrate = maxexemptrate
508
509     # Set up subclasses for the slice
510     tc("class replace dev %s parent 1:10 classid 1:%x htb rate %dbit ceil %dbit quantum %d" % \
511        (dev, default_minor | xid, minrate, maxrate, share * quantum))
512
513     tc("class replace dev %s parent 1:20 classid 1:%x htb rate %dbit ceil %dbit quantum %d" % \
514        (dev, exempt_minor | xid, minexemptrate, maxexemptrate, share * quantum))
515
516     # Attach a FIFO to each subclass, which helps to throttle back
517     # processes that are sending faster than the token buckets can
518     # support.
519     tc("qdisc replace dev %s parent 1:%x handle %x pfifo" % \
520        (dev, default_minor | xid, default_minor | xid))
521
522     tc("qdisc replace dev %s parent 1:%x handle %x pfifo" % \
523        (dev, exempt_minor | xid, exempt_minor | xid))
524
525
526 def set(xid, share = None, minrate = None, maxrate = None, minexemptrate = None, maxexemptrate = None):
527     on(xid = xid, share = share,
528        minrate = minrate, maxrate = maxrate,
529        minexemptrate = minexemptrate, maxexemptrate = maxexemptrate)
530
531
532 # Remove class associated with specified slice xid. If further packets
533 # are seen from this slice, they will be classified into the default
534 # class 1:1FFF.
535 def off(xid, dev = dev):
536     """
537     Remove class associated with specified slice xid. If further
538     packets are seen from this slice, they will be classified into the
539     default class 1:1FFF.
540     """
541
542     cap = get(xid, dev)
543     if cap is not None:
544         tc("class del dev %s classid 1:%x" % (dev, default_minor | xid))
545         tc("class del dev %s classid 1:%x" % (dev, exempt_minor | xid))
546
547
548 def exempt_init(group_name, node_ips):
549     """
550     Initialize the list of destinations exempt from the node bandwidth
551     (burst) cap.
552     """
553
554     # Clean up
555     iptables = "/sbin/iptables -t vnet %s POSTROUTING" 
556     run(iptables % "-F")
557     run("/sbin/ipset -X " + group_name)
558
559     # Create a hashed IP set of all of these destinations
560     lines = ["-N %s iphash" % group_name]
561     add_cmd = "-A %s " % group_name
562     lines += [(add_cmd + ip) for ip in node_ips]
563     lines += ["COMMIT"]
564     restore = "\n".join(lines) + "\n"
565     run("/sbin/ipset -R", restore)
566
567     # Add rule to match on destination IP set
568     run((iptables + " -m set --set %s dst -j CLASSIFY --set-class 1:%x") %
569         ("-A", group_name, exempt_minor))
570
571
572 def usage():
573     bwcap_description = format_tc_rate(get_bwcap())
574         
575     print """
576 Usage:
577
578 %s [OPTION]... [COMMAND] [ARGUMENT]...
579
580 Options:
581         -d device       Network interface (default: %s)
582         -r rate         Node bandwidth cap (default: %s)
583         -q quantum      Share multiplier (default: %d bytes)
584         -n              Print rates in numeric bits per second
585         -v              Enable verbose debug messages
586         -h              This message
587
588 Commands:
589         init
590                 (Re)initialize all bandwidth parameters
591         on slice [share|-] [minrate|-] [maxrate|-] [minexemptrate|-] [maxexemptrate|-]
592                 Set bandwidth parameter(s) for the specified slice
593         off slice
594                 Remove all bandwidth parameters for the specified slice
595         get
596                 Get all bandwidth parameters for all slices
597         get slice
598                 Get bandwidth parameters for the specified slice
599 """ % (sys.argv[0], dev, bwcap_description, quantum)
600     sys.exit(1)
601     
602
603 def main():
604     global dev, quantum, verbose
605
606     # Defaults
607     numeric = False
608     bwcap = get_bwcap()
609
610     (opts, argv) = getopt.getopt(sys.argv[1:], "d:nr:q:vh")
611     for (opt, optval) in opts:
612         if opt == '-d':
613             dev = optval
614         elif opt == '-n':
615             numeric = True
616         elif opt == '-r':
617             bwcap = get_tc_rate(optval)
618         elif opt == '-q':
619             quantum = int(optval)
620         elif opt == '-v':
621             verbose += 1
622         elif opt == '-h':
623             usage()
624
625     if len(argv):
626         if argv[0] == "init" or (argv[0] == "on" and len(argv) == 1):
627             # (Re)initialize
628             init(dev, get_tc_rate(bwcap))
629
630         elif argv[0] == "get" or argv[0] == "show":
631             # Show
632             if len(argv) >= 2:
633                 # Show a particular slice
634                 xid = get_xid(argv[1])
635                 if xid is None:
636                     sys.stderr.write("Error: Invalid slice name or context '%s'\n" % argv[1])
637                     usage()
638                 params = get(xid, dev)
639                 if params is None:
640                     paramslist = []
641                 else:
642                     paramslist = [params]
643             else:
644                 # Show all slices
645                 paramslist = get(None, dev)
646
647             for (xid, share,
648                  minrate, maxrate,
649                  minexemptrate, maxexemptrate,
650                  bytes, exemptbytes) in paramslist:
651                 slice = get_slice(xid)
652                 if slice is None:
653                     # Orphaned (not associated with a slice) class
654                     slice = "%d?" % xid
655                 if numeric:
656                     print "%s %d %d %d %d %d %d %d" % \
657                           (slice, share,
658                            minrate, maxrate,
659                            minexemptrate, maxexemptrate,
660                            bytes, exemptbytes)
661                 else:
662                     print "%s %d %s %s %s %s %d %d" % \
663                           (slice, share,
664                            format_tc_rate(minrate), format_tc_rate(maxrate),
665                            format_tc_rate(minexemptrate), format_tc_rate(maxexemptrate),
666                            bytes, exemptbytes)
667
668         elif len(argv) >= 2:
669             # slice, ...
670             xid = get_xid(argv[1])
671             if xid is None:
672                 sys.stderr.write("Error: Invalid slice name or context '%s'\n" % argv[1])
673                 usage()
674
675             if argv[0] == "on" or argv[0] == "add" or argv[0] == "replace" or argv[0] == "set":
676                 # Enable cap
677                 args = []
678                 if len(argv) >= 3:
679                     # ... share, minrate, maxrate, minexemptrate, maxexemptrate
680                     casts = [int, get_tc_rate, get_tc_rate, get_tc_rate, get_tc_rate]
681                     for i, arg in enumerate(argv[2:]):
682                         if i >= len(casts):
683                             break
684                         if arg == "-":
685                             args.append(None)
686                         else:
687                             args.append(casts[i](arg))
688                 on(xid, dev, *args)
689
690             elif argv[0] == "off" or argv[0] == "del":
691                 # Disable cap
692                 off(xid, dev)
693
694             else:
695                 usage()
696
697         else:
698             usage()
699
700
701 if __name__ == '__main__':
702     main()