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