| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
It's bad form to remove other people's copyright and license when you
copy their source for your own use.
Defining BITS_PER_LONG as 64 is incorrect on 32-bit platforms.
The mismatch between the unsigned long of the timer and the int
param to fls() means on 64-bit platforms that any bits set in the
high 32-bits of the the timer are lost/ignored.
gf_tw_find_last_bit() is meant to find the last bit in an array of
longs. It's overkill for gluster's timerwheel where we only ever pass
a single long; replacing it with a direct call to fls() which is
renamed to gf_tw_fls()
The timer routines are slightly modified from the kernel timer
functions that first appeared circa 2.6.x in .../kernel/timer.c
AFAICT.
find_last_bit() comes from the (linux) kernel (.../lib/find_bit.c
in 4.x kernels, .../lib/find_last_bit.c in 3.x kernels) but as noted
above, it is removed with this patch.
__fls() comes from the linux kernel (.../include/asm-generic/
bitops/{__fls.h,builtin-__fls.h}
Restoring/updating the copyright and license to the version from
the 4.x kernel find_bit.c. (timer.c does not have a license, __fls.h
and builtin-__fls.h do not have a copyright or license, but the whole
kernel is licensed under GPLv2 anyway.)
Change-Id: I2d2defccf1ccc74f55d99e94212747a36a1dff35
Signed-off-by: Kaleb S. KEITHLEY <kkeithle@redhat.com>
Reviewed-on: https://review.gluster.org/17146
Smoke: Gluster Build System <jenkins@build.gluster.org>
NetBSD-regression: NetBSD Build System <jenkins@build.gluster.org>
CentOS-regression: Gluster Build System <jenkins@build.gluster.org>
Reviewed-by: Jeff Darcy <jeff@pl.atyp.us>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
| |
This reverts commit c92b8347aea8ce78ca3fbc49b88f5adadc98509b.
Commit is not ready for a merge!
Change-Id: I3b3b52f7bfb4781dd42160e2b1059b4cdeb17956
Reviewed-on: https://review.gluster.org/17147
Tested-by: Shyamsundar Ranganathan <srangana@redhat.com>
Reviewed-by: Kaleb KEITHLEY <kkeithle@redhat.com>
Smoke: Gluster Build System <jenkins@build.gluster.org>
NetBSD-regression: NetBSD Build System <jenkins@build.gluster.org>
CentOS-regression: Gluster Build System <jenkins@build.gluster.org>
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Simply always defining BITS_PER_LONG as 64 seems like it's almost
certainly wrong on 32-bit platforms and could potentially result in
incorrect results.
fls and, e.g., __builtin_ffs() return the same answer for any given
input, making it seem like the name fls (find last set) is a misnomer
and ffs (find first set, starting from the lsb) is the more accurate
name.
Using __builtin_ffs() causes the compiler (in intel) to emit code
with the bsf (bit scan forward) insn, which is approx 3x faster than
the code in ffs(), at least on the machine I tried it on. (Even so,
it takes 10M+ iterations for the speed difference to be measurable.
Choosing the "faster" implementation seems like a no-brainer, even
if there may not be any significant gain by doing so.)
Change-Id: I1616dda1a5b76f208ba737a713877c1673131e33
Signed-off-by: Kaleb S. KEITHLEY <kkeithle@redhat.com>
Reviewed-on: https://review.gluster.org/17142
Smoke: Gluster Build System <jenkins@build.gluster.org>
NetBSD-regression: NetBSD Build System <jenkins@build.gluster.org>
CentOS-regression: Gluster Build System <jenkins@build.gluster.org>
Reviewed-by: Niels de Vos <ndevos@redhat.com>
Reviewed-by: Jeff Darcy <jeff@pl.atyp.us>
|
|
|
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.
[
NOTE:
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@redhat.com>
Reviewed-on: http://review.gluster.org/9707
Reviewed-by: Vijay Bellur <vbellur@redhat.com>
Tested-by: Vijay Bellur <vbellur@redhat.com>
|
