Zbr's days.

About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Fri, 16 Mar 2007

Climbing evening.

Ok, since Grange can not climb for some time, I train myself - so to make training a bit more complex last several days I trained with weights on legs and arms - that does make training more complex and interesting - I try to do the same traverses and boulderings I did before, but this time with weights - that is very fun.

Got my "Games theory" and "Graph theory" books - started to read first one.
It even contains some homework tasks, which I will likely post here (with my solutions) in a new section, so if you think games theory and related economic in particular and decision making in general tasks are interesting for you, stay tuned.

Tomorrow we will celebrate missed Wijo and Fedor birthdays - I will meet with old friends, which I expect to be very fun. I did not see some of them about a half of a year.

/life :: Link / Comments ()

Asyncfd by Davide Libenzi got ring buffer.

Implementation allows to post events into userspace ring buffer.
There are several disadvantages though:

  • it can not be called from interrupt context.
  • there is possibility to lost events when ring is full, since events are posted unconditionally.
  • it has redundant fields in API.
Briefly saying - it goes the way kevent moved, but with additional problems.
For example I do not see how to solve second problem from above list, since kevent has (had) own queue of events, which were copied from the queue when userspace updated indexes, so if userspace ring is full, they would not be lost, but existing mechanism does not have such a queue at all, events are just blindly copied and thus can be lost when ring is full.
First problem must be solved too to support tricky usage (as Davide mentioned in patch description, USB calls might enp up calling it from interrupt context).
One of the problems Davide solves either by using locked userspace memory (which is a big no-no), or by using kernel buffers and read(), which is unconvenient and just breaks the whole idea of ring buffer - having multiple events in userspace without additional (only waiting) syscalls and having syscalls as thread cancellation points without additional structures shared between threads.

Timerfd implementation will likely rise the same questions from Ulrich Drepper as my kevent timers - they are not needed, instead POSIX timers support should be extended (although I always provided two patches - for POSIX timers and own API, maybe Davide will use both too). But POSIX timer events become ready in softirq context, so it is impossible to use above ring buffer implementation for them.
Timerfd code also uses long type in structures shared between userspace and kernelspace, which does not work on x86_64 when userspace is 32bit.

Yes, I know, I'm a bastard moron, since I write only bad things in my blog, but hey, I was not in Cc: list :)
Actually I'm glad people started to work in that area after kevent, that means that my ideas were correct and eventually Linux will adopt a good solution for that problems.
I think Davide will resolve all issues quickly.

/devel/kevent :: Link / Comments ()

Super optimized multidimensional trie implementation.

After morning tea and quite interesting optimization lookup for 96 bit key on 32 bit arch takes about 90-100 nanoseconds! This basically means that my multidimensional trie implementation outperforms hash table in any workload with any hash table size. But I need to admit, that it is random values (three 32 bit values without zeroes in any byte, the same are used for hash table tests), so things can differ in real life.
Memory overhead is about 97 Mb.
Test was performed in userspace.

Update: and the same speed (upto 110 nanoseconds) and memory overhead (about 98 Mb) can be achieved for 160 bit keys - so they can include bound device index and protocol number.

/devel/other :: Link / Comments ()