[Bugs] [Bug 1170075] [RFE] : BitRot detection in glusterfs

bugzilla at redhat.com bugzilla at redhat.com
Thu Mar 19 05:05:55 UTC 2015


--- Comment #27 from Anand Avati <aavati at redhat.com> ---
COMMIT: http://review.gluster.org/9707 committed in master by Vijay Bellur
(vbellur at redhat.com) 
commit 5394f3cf60b0815d2919d24e9945ba47e3bb1f9b
Author: Venky Shankar <vshankar at redhat.com>
Date:   Tue Feb 3 19:05:28 2015 +0530

    contrib/timer-wheel: import linux kernel timer-wheel

    This patch imports timer-wheel[1] algorithm from the linux
    kernel (~/kernel/time/timer.c) with some modifications.

    Timer-wheel is an efficent way to track millions of timers for
    expiry. This is a variant of the simple but RAM heavy approach
    of having a list (timer bucket) for every future second.
    Timer-wheel categorizes every future second into a logarithmic
    array of arrays. This is done by splitting the 32 bit "timeout"
    value into fixed "sliced" bits, thereby each category has a
    fixed size array to which buckets are assigned.

    A classic split would be 8+6+6+6 (used in this patch) which
    results in 256+64+64+64 == 512 buckets. Therefore, the entire
    32 bit futuristic timeouts have been mapped into 512 buckets.

         There are other possible splits, such as "8+8+8+8", but
         this patch sticks to the widely used and tested default.

    Therfore, the first category "holds" timers whose expiry range
    is between 1..256, the next cateogry holds 257..16384, third
    category 16385..1048576 and so on. When timers are added,
    unless it's in the first category, timers with different
    timeouts could end up in the same bucket. This means that the
    timers are "partially sorted" -- sorted in their highest bits.

    The expiry code walks the first array of buckets and exprires
    any pending timers (1..256). Next, at time value 257, timers
    in the first bucket of the second array is "cascaded" onto
    the first category and timers are placed into respective
    buckets according to the thier timeout values. Cascading
    "brings down" the timers timeout to the coorect bucket
    of their respective category. Therefore, timers are sorted
    by their highest bits of the timeout value and then by the
    lower bits too.

    [1] https://lwn.net/Articles/152436/

    Change-Id: I1219abf69290961ae9a3d483e11c107c5f49c4e3
    BUG: 1170075
    Signed-off-by: Venky Shankar <vshankar at redhat.com>
    Reviewed-on: http://review.gluster.org/9707
    Reviewed-by: Vijay Bellur <vbellur at redhat.com>
    Tested-by: Vijay Bellur <vbellur at redhat.com>

You are receiving this mail because:
You are on the CC list for the bug.
Unsubscribe from this bug https://bugzilla.redhat.com/token.cgi?t=hzABk8nOJZ&a=cc_unsubscribe

More information about the Bugs mailing list