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