wahern / timeout Goto Github PK

I'd be interested to see a comparison+benchmark to compare against EB Trees as used in HAProxy: http://1wt.eu/articles/ebtree/

Would it be possible to generate a release that is cryptographically signed with a key ?

It would allow us to import the signed release, and use the signature to verify the code is not modified.

For example tcpdump is available as a .tar.gz file at https://www.tcpdump.org/index.html#latest-releases with an associated signature https://www.tcpdump.org/release/libpcap-1.10.0.tar.gz.sig signed with a private key for which the public key is available at https://www.tcpdump.org/release/signing-key.asc

Any chance you could make this available ?

thanks
Jesper

In Xcode, The definition of struct timeout_cb in timeout.h

struct timeout_cb {
	void (*fn)();
	void *arg;
}; /* struct timeout_cb */

In this line

void (*fn)();

I get a warning "This function declaration is not a prototype Insert 'void'". Can you add a "void" as this:

void (*fn)(void);

Hi there,

It seems from my reading of the code that this implementation doesn't support overflow. That is, say if a timeout of TIMEOUT_MAX + 1 is added before all the timeouts are expired, it will be added to wheel[0][0]. When the time is updated, instead of waiting till next round, this newly added timeout will be expired.

Please correct me if I got anything wrong, or if there is any specific reason why overflow support wasn't added. If not then I'm interested in adding it.

The 'hz' argument is supposed to count frequency. But TIMEOUT_mHZ is not a millihertz; it is a kHz, which corresponds to a frequency of a millisecond. Similarly, TIMEOUT_uHZ is really a MHz, which corresponds to a microsecond; and TIMEOUT_nHZ is really a GHz, corresponding to a nanosecond.

I'm not sure whether it's worthwhile to rename these to the proper SI values, or just to add a comment.

I'm trying to write a branch-complete set of tests, but I don't understand the desired behavior for timeouts_readd() in the case where we advance more than one interval past the expiration time of a timeout whose TIMEOUT_INT flag is set.

To be concrete: Suppose that it is now time 55. Suppose that we have a timeout to with to->expires == 122; to->interval == 100.

Case 1: We advance to time 150. Now to will expire, and be rescheduled with to->expires == 222;. That's fine.

Case 2: We directly advance to time 222. Now to will expire, and be rescheduled with to->expires == 322;. That makes sense.

Case 3: We advance directly to time 250. Now to will expire, and (if I am reading this code right) will be rescheduled with to->expires == 294;. Why should that be? If this behavior is intended, I'd like to know what property it is actually providing so I can test for it. If this behavior is not intended, it should probably get fixed.

Hi wahern,

Exception thrown: read access violation.
to->pending was 0x2404943C4E0.

After debugging, I found
at line 350 wheel = timeout_wheel(rem); in file timeout.c
wheel is 9, which is is the reason why write access violation

However, test runs pretty well in ubuntu 16.04

Regards

The source code cannot be understood

timeouts_update bitwise ........

in file timeout.c at line 463
if (!(0x1 & pending)) break; /* break if we didn't wrap around end of wheel */

should we use T->pending instead of pending ?

timeout_slot() uses relative timeout to calculate wheel idx, but timeout_wheel() uses abs timeout to calculate slot idx. I doubt if this is 100% right. In my opinion, both functions should use relative timeout

I am trying to compile the code under Windows. After some tweaks it compiles, but the test accesses invalid memory - the
wheel = timeout_wheel(rem);
called with rem = 90 returns 4, with WHEEL_NUM == 4.

I think that the culprit is the implementation of clz32/64 function. This should mean "count leading zeros"; however, the _BitScanReverse finds a position of the most significant true bit. For a value 90 this is 6; it should however return 25. Changing the functions to return 31 - zeros and return 63 - zeros seems to fix this issue.

There is still some other problem - the test using {{{cfg3}}} does not seem to progress, still hunting this one.

my input:
struct rand_cfg cfg1 =
{
/min_timeout/1,
/max_timeout/381,
/start_at/100,
/end_at/1000,
/n_timeouts/1,
/max_step/10,
/relative/0,
/try_removing/0,
/finalize/2 };
DO_N(1, check_randomized(&cfg1))

my test result (more logs added):

....---------------init and add all sample timers ---------------
add_timer(pending)::abstimout=248,currtime 100,rem 148,

---------------filter out all expired timers ---------------

---------------now we test pending timers---------------
update(curtime 130)::a pending timer(abs_expires 248) got expired
add_timer(pending)::abstimout=248,currtime 130,rem 118,
update(curtime 200)::a pending timer(abs_expires 248) got expired
add_timer(pending)::abstimout=248,currtime 200,rem 48,
update(curtime 250)::a pending timer(abs_expires 248) got expired
add_timer(expired)::abstimout=248,currtime 250,rem 15),

OK

problem is thetimer with absolute timeout 248 is should not be expired with current time 130, but it actually expired.

why the whole tests passed by is because in times_update() functions calls timeouts_sche() but timeouts_sche() function internally will try to remove existing timer before adding it.