Eric Lee / smarc-fsl-linux-kernel

09 Dec, 2011

1 commit

  • 8af2a218d   sch_red: Adaptative RED AQM ... Browse Code »

    Adaptative RED AQM for linux, based on paper from Sally FLoyd,
    Ramakrishna Gummadi, and Scott Shenker, August 2001 :

    http://icir.org/floyd/papers/adaptiveRed.pdf

    Goal of Adaptative RED is to make max_p a dynamic value between 1% and
    50% to reach the target average queue : (max_th - min_th) / 2

    Every 500 ms:
    if (avg > target and max_p < target and max_p >= 0.01)
    decrease max_p : max_p *= beta;

    target :[min_th + 0.4*(min_th - max_th),
    min_th + 0.6*(min_th - max_th)].
    alpha : min(0.01, max_p / 4)
    beta : 0.9
    max_P is a Q0.32 fixed point number (unsigned, with 32 bits mantissa)

    Changes against our RED implementation are :

    max_p is no longer a negative power of two (1/(2^Plog)), but a Q0.32
    fixed point number, to allow full range described in Adatative paper.

    To deliver a random number, we now use a reciprocal divide (thats really
    a multiply), but this operation is done once per marked/droped packet
    when in RED_BETWEEN_TRESH window, so added cost (compared to previous
    AND operation) is near zero.

    dump operation gives current max_p value in a new TCA_RED_MAX_P
    attribute.

    Example on a 10Mbit link :

    tc qdisc add dev $DEV parent 1:1 handle 10: est 1sec 8sec red \
    limit 400000 min 30000 max 90000 avpkt 1000 \
    burst 55 ecn adaptative bandwidth 10Mbit

    # tc -s -d qdisc show dev eth3
    ...
    qdisc red 10: parent 1:1 limit 400000b min 30000b max 90000b ecn
    adaptative ewma 5 max_p=0.113335 Scell_log 15
    Sent 50414282 bytes 34504 pkt (dropped 35, overlimits 1392 requeues 0)
    rate 9749Kbit 831pps backlog 72056b 16p requeues 0
    marked 1357 early 35 pdrop 0 other 0

    Signed-off-by: Eric Dumazet
    Signed-off-by: David S. Miller

    Eric Dumazet
     

14 Dec, 2006

1 commit

  • 6a2d7a955   [PATCH] SLAB: use a multiply instead of a divide in obj_to_index() ... Browse Code »

    When some objects are allocated by one CPU but freed by another CPU we can
    consume lot of cycles doing divides in obj_to_index().

    (Typical load on a dual processor machine where network interrupts are
    handled by one particular CPU (allocating skbufs), and the other CPU is
    running the application (consuming and freeing skbufs))

    Here on one production server (dual-core AMD Opteron 285), I noticed this
    divide took 1.20 % of CPU_CLK_UNHALTED events in kernel. But Opteron are
    quite modern cpus and the divide is much more expensive on oldest
    architectures :

    On a 200 MHz sparcv9 machine, the division takes 64 cycles instead of 1
    cycle for a multiply.

    Doing some math, we can use a reciprocal multiplication instead of a divide.

    If we want to compute V = (A / B) (A and B being u32 quantities)
    we can instead use :

    V = ((u64)A * RECIPROCAL(B)) >> 32 ;

    where RECIPROCAL(B) is precalculated to ((1LL << 32) + (B - 1)) / B

    Note :

    I wrote pure C code for clarity. gcc output for i386 is not optimal but
    acceptable :

    mull 0x14(%ebx)
    mov %edx,%eax // part of the >> 32
    xor %edx,%edx // useless
    mov %eax,(%esp) // could be avoided
    mov %edx,0x4(%esp) // useless
    mov (%esp),%ebx

    [akpm@osdl.org: small cleanups]
    Signed-off-by: Eric Dumazet
    Cc: Christoph Lameter
    Cc: David Miller
    Signed-off-by: Andrew Morton
    Signed-off-by: Linus Torvalds

    Eric Dumazet