release/src/router/iproute2/tc/tc_core.c

   1 /*
   2  * tc_core.c            TC core library.
   3  *
   4  *              This program is free software; you can redistribute it and/or
   5  *              modify it under the terms of the GNU General Public License
   6  *              as published by the Free Software Foundation; either version
   7  *              2 of the License, or (at your option) any later version.
   8  *
   9  * Authors:     Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
  10  *
  11  */
  12
  13 #include <stdio.h>
  14 #include <stdlib.h>
  15 #include <unistd.h>
  16 #include <syslog.h>
  17 #include <fcntl.h>
  18 #include <math.h>
  19 #include <sys/socket.h>
  20 #include <netinet/in.h>
  21 #include <arpa/inet.h>
  22 #include <string.h>
  23
  24 #include "tc_core.h"
  25
  26 #define ATM_CELL_SIZE           53
  27 #define ATM_CELL_PAYLOAD        48
  28
  29 static __u32 t2us=1;
  30 static __u32 us2t=1;
  31 static double tick_in_usec = 1;
  32
  33 long tc_core_usec2tick(long usec)
  34 {
  35         return usec*tick_in_usec;
  36 }
  37
  38 long tc_core_tick2usec(long tick)
  39 {
  40         return tick/tick_in_usec;
  41 }
  42
  43 unsigned tc_calc_xmittime(unsigned rate, unsigned size)
  44 {
  45         return tc_core_usec2tick(1000000*((double)size/rate));
  46 }
  47
  48 /*
  49  * Calculate the ATM cell overhead.  ATM sends each packet in 48 byte
  50  * chunks, the last chunk being padded if necessary.  Each chunk carries
  51  * an additional 5 byte overhead - the ATM header.*/
  52
  53 static int tc_align_to_cells(int size)
  54 {
  55         int cells;
  56
  57         cells = size / ATM_CELL_PAYLOAD;
  58         if (size % ATM_CELL_PAYLOAD != 0)
  59                 cells++;
  60         return cells * ATM_CELL_SIZE;
  61 }
  62
  63 /** The number this function calculates is subtle.  Ignore it and just believe
  64  * it works if you have a choice, otherwise ..
  65  *
  66  * If there we are calculating the ATM cell overhead the kernel calculations
  67  * will be out sometimes if the range of packet sizes spanned by one
  68  * rate table element crosses an ATM cell boundary.  Consider these three
  69  * senarios:
  70  *    (a) the packet is sent across the ATM link without addition
  71  *        overheads the kernel doesn't know about, and
  72  *    (b) a packet that has 1 byte of additional overhead the kernel
  73  *        doesn't know about.  Here
  74  *    (c) a packet that has 2 bytes of additional overhead the
  75  *        kernel doesn't know about.
  76  * The table below presents what happens.  Each row is for a single rate
  77  * table element.  The "Sizes" column shows what packet sizes the rate table
  78  * element will be used for.  This packet size includes the "unknown to
  79  * kernel" overhead, but does not include overhead incurred by breaking the
  80  * packet up into ATM cells. This ATM cell overhead consists of the 5 byte
  81  * header per ATM cell, plus the padding in the last cell.  The "ATM" column
  82  * shows how many bytes are actually sent across the ATM link, ie it does
  83  * include the ATM cell overhead.
  84  *
  85  *   RateTable Entry  Sizes(a) ATM(a)    Sizes(b) ATM(b)   Sizes(c) ATM(c)
  86  *      ratetable[0]    0..7    53        1..8     53        2..9    53
  87  *      ratetable[1]    8..15   53        9..16    53        2..17   53
  88  *      ratetable[2]   16..23   53       17..24    53       18..25   53
  89  *      ratetable[3]   24..31   53       25..32    53       26..33   53
  90  *      ratetable[4]   32..39   53       33..40    53       34..41   53
  91  *      ratetable[5]   40..47   53       41..48    53       42..49   53,106
  92  *      ratetable[6]   48..55   53,106   49..56   106       50..57  106
  93  *
  94  * For senario (a), the ratetable[6] entry covers two cases: one were a single
  95  * ATM cell is needed to transmit the data, and one where two ATM cells are
  96  * required.  It can't be right for both.  Unfortunately the error is large.
  97  * The same problem arises in senario (c) for ratetable[5].  The problem
  98  * doesn't happen for senario (b), because the boundary between rate table
  99  * entries happens to match the boundary between ATM cells.
 100  *
 101  * What we would like to do is ensure that ratetable boundaries always match
 102  * the ATM cells.  If we do this the error goes away.  The solution is to make
 103  * the kernel add a small bias to the packet size.  (Small because the bias
 104  * will always be smaller than cell_log.)  Adding this small bias will in
 105  * effect slide the ratetable along a bit, so the boundaries match.  The code
 106  * below calculates that bias.  Provided the MTU is less than 4092, doing
 107  * this can always eliminate the error.
 108  *
 109  * Old kernels won't add this bias, so they will have the error described above
 110  * in most cases.  In the worst case senario, considering all possible ATM cell
 111  * sizes (1..48), for 7 of these sizes the old kernel will calculate the rate
 112  * wrongly - ie, be out by 53 bytes.*/
 113
 114 static int tc_calc_cell_align(int atm_cell_tax, char overhead, int cell_log)
 115 {
 116         int cell_size;
 117
 118         if (!atm_cell_tax)
 119                 return 0;
 120         cell_size = 1 << cell_log;
 121         return (overhead + cell_size - 2) % cell_size - cell_size + 1;
 122 }
 123
 124
 125 /*
 126  * A constructor for a tc_ratespec.
 127  */
 128 void tc_calc_ratespec(struct tc_ratespec* spec, __u32* rtab, unsigned bps,
 129         int cell_log, unsigned mtu, unsigned char mpu, int atm_cell_tax,
 130         char overhead)
 131 {
 132         int i;
 133
 134         if (mtu == 0)
 135                 mtu = 2047;
 136
 137 /*    rtab[pkt_len>>cell_log] = pkt_xmit_time  */
 138         if (cell_log < 0) {
 139                 cell_log = 0;
 140                 while ((mtu>>cell_log) > 255)
 141                         cell_log++;
 142         }
 143         for (i=0; i<256; i++) {
 144                 /*
 145                 * sz is the length of packet we will use for this ratetable
 146                 * entry.  The time taken to send a packet of this length will
 147                 * be used for all packet lengths this ratetable entry applies
 148                 * to.  As underestimating how long it will take to transmit a
 149                 * packet is a worse error than overestimating it, the longest
 150                 * packet this rate table entry applies to is used.
 151                 */
 152                 int sz = ((i+1)<<cell_log) - 1 + overhead;
 153                 if (sz < mpu)
 154                         sz = mpu;
 155                 if (atm_cell_tax)
 156                         sz = tc_align_to_cells(sz);
 157                 rtab[i] = tc_calc_xmittime(bps, sz);
 158         }
 159
 160         spec->cell_align = tc_calc_cell_align(atm_cell_tax, overhead, cell_log);
 161         spec->cell_log = cell_log;
 162         spec->feature = 0x8000 | (atm_cell_tax ? 1 : 0);
 163         spec->mpu = mpu | (unsigned)(overhead << 8);
 164         spec->rate = bps;
 165 }
 166
 167 int tc_core_init()
 168 {
 169         FILE *fp = fopen("/proc/net/psched", "r");
 170
 171         if (fp == NULL)
 172                 return -1;
 173
 174         if (fscanf(fp, "%08x%08x", &t2us, &us2t) != 2) {
 175                 fclose(fp);
 176                 return -1;
 177         }
 178         fclose(fp);
 179         tick_in_usec = (double)t2us/us2t;
 180         return 0;
 181 }