[MEDIUM] smarter integer comparison support in ACLs

ACLs now support operators such as 'eq', 'le', 'lt', 'ge' and 'gt'
in order to give more flexibility to the language. Because of this
change, the 'dst_limit' keyword changed to 'dst_conn' and now requires
either a range or a test such as 'dst_conn lt 1000' which is more
understandable.

[RELEASE] Released version 1.3.11.4 with the following main changes :

    - do not re-arm read timeout in SHUTR state
    - optimize I/O by detecting system starvation
    - the epoll FD must not be shared between processes
    - limit the number of events returned by *poll*

[MEDIUM] limit the number of events returned by *poll*

By default, epoll/kqueue used to return as many events as possible.
This could sometimes cause huge latencies (latencies of up to 400 ms
have been observed with many thousands of fds at once). Limiting the
number of events returned also reduces the latency by avoiding too
many blind processing. The value is set to 200 by default and can be
changed in the global section using the tune.maxpollevents parameter.

[BUG] the epoll FD must not be shared between processes

Recreate the epoll file descriptor after a fork(). It will ensure
that all processes will not share their epoll_fd. Some side effects
were encountered because of this, such as epoll_wait() returning an
FD which was previously deleted, in multi-process mode.

[MEDIUM] optimize I/O by detecting system starvation

Compare the results of recv/send with the parameter passed and
detect whether the system has no free buffer space for send()
or has no data anymore for recv(). This dramatically reduces
the number of syscalls (by about 23%).

[BUG] do not re-arm read timeout after writing data

A second occurrence of read-timeout rearming was present in stream_sock.c.
To fix the problem, it was necessary to put the shutdown information in
the buffer (already planned).

[BUG] do not re-arm read timeout in SHUTR state !

There is a long-time bug causing busy loops when either client-side
or server-side enters a SHUTR state. When writing data to the FD,
it was possible to re-arm the read side if the write had been paused.

[RELEASE] Released version 1.3.11.3 with the following main changes :

    - pre-initialize timeouts with tv_eternity during parsing

[BUG] pre-initialize timeouts with tv_eternity during parsing

ETERNITY is not 0 anymore, so all timeouts will not be initialized
to ETERNITY by a simple calloc(). We have to explictly assign them.

This bug caused random session aborts.

[RELEASE] Released version 1.3.11.2 with the following main changes :

    - fixed broken health-checks since switch to timeval

[BUG] fix broken health-checks since switch to timeval

Health-checks were broken because of a return which was unexpectedly removed.

[RELEASE] Released version 1.3.11.1 with the following main changes :

    - fixed ev_kqueue which was forgotten during the switch to timeval
    - allowed null timeouts for past events in select

[MINOR] allow null timeouts for past events in select

[BUG] ev_kqueue was forgotten during the switch to timeval

[RELEASE] Released version 1.3.11 with the following main changes :

    - fixed ev_sepoll again by rewriting the state machine
    - switched all timeouts to timevals instead of milliseconds
    - improved memory management using mempools v2.
    - several minor optimizations

Merge branch 'pools' into merge-pools

[MINOR] disable useless hint in wake_expired_tasks

wake_expired_tasks() used a hint to avoid scanning the tree in most cases,
but it looks like the hint is more expensive than reaching the first node
in the tree. Disable it for now.

[BUG] fix buggy timeout computation in wake_expired_tasks

Wake_expired_tasks is supposed to return a date, not an interval. It
was causing busy loops in pollers.

[BUG] fix null timeouts in *poll-based pollers

Introduction of timeval timers broke *poll-based pollers, because the call to
tv_ms_remain may return 0 while the event is not elapsed yet. Now we carefully
check for those cases and round the result up by 1 ms.

[MAJOR] call garbage collector when doing soft stop

When we're interrupted by another instance, it is very likely
that the other one will need some memory. Now we know how to
free what is not used, so let's do it.

Also only free non-null pointers. Previously, pool_destroy()
did implicitly check for this case which was incidentely
needed.

[MEDIUM] enhance behaviour of mempools v2

- keep the number of users of each pool
- call the garbage collector on out of memory conditions
- sort the pools by size for faster creation
- force the alignment size to 16 bytes instead of 4*sizeof(void *)

[MAJOR] convert the header indexes to use mempool v2

[MAJOR] last bunch of capture changes for mempool v2

The header captures had lots of pools. They have all been transformed.

[MAJOR] ported the captures to use the new mempool v2

The "capture.c" file has also been removed since it was empty.

[MAJOR] ported requri to use mempools v2

[MAJOR] ported appsession to use mempools v2

Also during this process, a bug was found in appsession_refresh().
It would not automatically requeue the task in the queue, so the
old sessions would not vanish.

[MAJOR] ported pendconn to mempools v2

A pool_destroy() was also missing in deinit()

[MAJOR] switched buffers to mempools v2

[MAJOR] migrated task, tree64 and session to pool2

task and tree64 are already very close in size and are merged together.
Overall performance gained slightly by this simple change.

[MEDIUM] add new memory management functions

Implement pool_destroy2, pool_flush2, pool_gc2. It is safe to call
pool_gc2 to free whatever memory possible.

[MEDIUM] implement memory pools version 2

The new pools know about their size and usage. Malloc is not used
anymore, instead a dedicated function to refill the entries is used.

Merge branch 'timers' into merge-timers

[MINOR] use non-inline tv_* functions in many locations

The __tv_* functions were abused. They are not that small and it is not
always worth using them.

[MINOR] avoid inlining in task.c

The task management functions used to call __tv_* which is not really
optimal given the size of the functions.

[MINOR] add new tv_* functions

The most useful, tv_add_ifset only adds the increment if it is set. It
is designed for use in expiration computation.

Merge branch 'master' into timers

[TESTS] updates to hash experimentations

Aleksandar Lazic has collected many hashing algorithms and put them
in one file to ease benchmarking. Some algos look promising, some
of them have been checked further with uri_hash. Some results on
various systems/hardware are stored in hash_results.txt.

[BUG] fix ev_sepoll again, this time with a new state machine

It was possible in ev_sepoll() to ignore certain events if
all speculative events had been processed at once, because
the epoll_wait() timeout was not cleared, thus delaying the
events delivery.

The state machine was complicated, it has been rewritten.
It seems faster and more correct right now.

[MAJOR] replaced all timeouts with struct timeval

The timeout functions were difficult to manipulate because they were
rounding results to the millisecond. Thus, it was difficult to compare
and to check what expired and what did not. Also, the comparison
functions were heavy with multiplies and divides by 1000. Now, all
timeouts are stored in timevals, reducing the number of operations
for updates and leading to cleaner and more efficient code.

[MINOR] time.h: added a few tv_* functions to manipulate timevals

A few more tv_* functions will be needed to switch from a millisecond-based
scheduler to a struct timeval-based one.

[TESTS] test_pools: added support for dlmalloc()

[TESTS] added test_pools from Aleksandar Lazic

This simple test performs memory allocations using pools and
mallocs and returns the average number of allocations per second.

[RELEASE] Released version 1.3.10.2 with the following main changes :

    - fixed build of files including standard.h on OpenBSD

[BUILD] fixed build of files including standard.h on OpenBSD

The file standard.h included netinet/in.h without including
sys/types.h. This broke build on OpenBSD.

[RELEASE] Released version 1.3.10.1 with the following main changes :

    - fixed sepoll transition matrix (two states were missing)

[BUG] two missing states in sepoll transition matrix

Two states were missing in the speculative epoll state transition
matrix. This could cause some timeouts and unhandled events. The
problem showed up in TCP mode with a fast server at high session
rates, but could in theory also affect HTTP mode.

[RELEASE] Released version 1.3.10 with the following main changes :
    - several fixes in ev_sepoll
    - fixed some expiration dates on some tasks
    - fixed a bug in connection establishment detection due to speculative I/O
    - fixed rare bug occuring on TCP with early close (reported by Andy Smith)
    - implemented URI hashing algorithm (Guillaume Dallaire)
    - implemented SMTP health checks (Peter van Dijk)
    - replaced the rbtree with ul2tree from old scheduler project
    - new framework for generic ACL support
    - added the 'acl' and 'block' keywords to the config language
    - added several ACL criteria and matches (IP, port, URI, ...)
    - cleaned up and better modularization for some time functions
    - fixed list macros
    - fixed useless memory allocation in str2net()
    - store the original destination address in the session

[DOC] add some documentation about ACLs

Minimal documentation about ACLs

[MAJOR] fixed some expiration dates on tasks

The time subsystem really needs fixing. It was still possible
that some tasks with expiration date below the millisecond in
the future caused busy loop around poll() waiting for the
timeout to happen.

[MEDIUM] implement SMTP health checks

Peter van Dijk contributed this patch which implements the "smtpchk"
option, which is to SMTP what "httpchk" is to HTTP. By default, it sends
"HELO localhost" to the servers, and waits for the 250 message, but it
can also send a specific request.

[MINOR] ACL regex matching on the URI ; uri_reg

The URI can be matched on regexen now. The upcase/lowcase flag
can not be set yet and will soon have to.

[MINOR] implement the ACL keywords 'dst' and 'dport'

The file client.c now provides acl_fetch_dip and acl_fetch_dport
to be able to check the client's destination address and port. The
corresponding ACL keywords 'dst' and 'dport' have been added.

[MINOR] implement acl_parse_ip and acl_match_ip

The ACL can now compare IP addresses. The client's IP address
can be checked.

[MEDIUM] added the 'block' keyword to the config language

The new 'block' keyword makes it possible to block a request based on
ACL test results. Block accepts two optional arguments : 'if' <cond>
and 'unless' <cond>.

The request will be blocked with a 403 response if the condition is validated
(if) or if it is not (unless). Do not rely on this one too much, as it's more
of a proof of concept helping in developing other matches.

[MEDIUM] added several ACL criteria and matches

Many ACL criteria have been added. Some others are still commented out
because some functions are still missing.

[MEDIUM] add the 'acl' keyword to the config language

The 'acl' keyword allows one to declare a new ACL. It is an important part
of the ACL framework.

[MAJOR] new framework for generic ACL support

This framework offers all other subsystems the ability to register
ACL matching criteria. Some generic matching functions are already
provided. Others will come soon and the framework shall evolve.

[MEDIUM] store the original destination address in the session

There are multiple places where the client's destination address is
required. Let's store it in the session when needed, and add a flag
to inform that it has been retrieved.

[MINOR] fixed useless memory allocation in str2net()

It was not necessary anymore to allocate memory in str2net().
Moreover, some calls to free() were missing in case of errors.

[TESTS] added a trivial program to benchmark hash algos

The uri_hash.c program makes it very easy to benchmark the
distribution of hash algos. Pass it one word per line, and
it will show the distribution per server for 1 to 10 servers.

[BUG] fix early server close after client close

Problem reported by Andy Smith. If a client sends TCP data
and quickly closes the connection before the server connection
is established, AND the whole buffer can be sent at once when
the connection establishes, then the server side believes that
it can simply abort the connection because the buffer is empty,
without checking that some work was performed.

Fix: ensure that nothing was written before closing.

[MEDIUM] ensure that we always have a null word in config

It is important when parsing configuration file to ensure that at
least one word is empty to mark the end of the line. This will be
required with ACLs in order to avoid reading past the end of line.

[MINOR] add support for variable size arrays in structures

Depending on the version of GCC, variable size arrays are not
declared in the same manner. Let's add a check for the version
and provide a macro.

[MINOR] add LIST_HEAD_INIT to the list management macros

It is useful to have the ability to initialize a list while declaring it.

[MEDIUM] add better list management macros

The FOREACH_ITEM and FOREACH_ITEM_SAFE macros are nasty, they
require too many arguments. Let's port those from linux instead.

[MEDIUM] implement the URI hash algorithm

Guillaume Dallaire contributed the URI hashing algorithm for
use with proxy-caches. It provides the advantage of optimizing
the cache hit rate.

[MEDIUM] always have msg->sol point to beginning of message

Since the 'data' pointer is not stored in message structures, it is
useful to have such a pointer to it when the message has been fully
parsed.

[BUILD] do not build rbtree anymore

Rbtree is not used anymore. Remove it from the makefiles.

[MINOR] uninline task_wakeup

task_wakup has become bigger since we used the trees. Let's not
inline it anymore.

[MINOR] ev_sepoll: refine flags management.

Ensure that we don't call the event handlers if the FD is already
marked FD_STERROR, and ensure that we properly catch HUP and ERR.

[BUG] fixed connection establishment detection

Since the introduction of speculative I/O, it was not always possible
to correctly detect a connection establishment. Particularly, in TCP
mode, there is no data to send and getsockopt() returns no error. The
solution consists in trying a connect() again to get its diagnostic.

[MINOR] remove wait_time nullification in ev_sepoll

in ev_sepoll(), wait_time is forced to zero if at least one
speculative event is converted to a real event. This is completely
wrong.

[MINOR] pre-compute t->expire in event_accept

At the end of event_accept(), t->expire is computed with tv_min
between two exclusive values. Let's simply assign it at the same
time.

[MEDIUM] many cleanups in the time functions

Now, functions whose name begins with '__tv_' are inlined. Also,
'tv_ms' is used as a prefix for functions using milliseconds.

[MINOR] tell the compiler that debug more is unlikely to happen

In process_session(), add unlikely() around debug code.

[MEDIUM] implement and use tv_cmp2_le instead of tv_cmp2_ms

tv_cmp2_ms handles multiple combinations of tv1 and tv2, but only
one form is used: (tv1 <= tv2). So it is overkill to use it everywhere.
A new function designed to do exactly this has been written for that
purpose: tv_cmp2_le. Also, removed old unused tv_* functions.

[MAJOR] changed TV_ETERNITY to ~0 instead of 0

The fact that TV_ETERNITY was 0 was very awkward because it
required that comparison functions handled the special case.
Now it is ~0 and all comparisons are performed on unsigned
values, so that it is naturally greater than any other value.

A performance gain of about 2-5% has been noticed.

[MAJOR] replaced rbtree with ul2tree.

The rbtree-based wait queue consumes a lot of CPU. Use the ul2tree
instead. Lots of cleanups and code reorganizations made it possible
to reduce the task struct and simplify the code a bit.

[MINOR] removed useless counters from ul2tree_insert()

node_right_lookup and node_right_lookup were two statistical counters.
Let's remove them as we do not need them.

[MINOR] import ul2tree from old librt project

This is an import of the old ul2tree code as well as required bitops.
All of them will have to be refreshed at one moment.

[MINOR] added support for dual-linked lists

Imported dual-linked lists management macros from the old scheduler project,
and fixed a long-standing nasty bug in the DLIST_ADD() macro.

[RELEASE] Released version 1.3.9 with the following changes :

    - modularized the polling mechanisms and use function pointers instead
      of macros at many places
    - implemented support for FreeBSD's kqueue() polling mechanism
    - fixed a warning on OpenBSD : MIN/MAX redefined
    - change socket registration order at startup to accomodate kqueue.
    - several makefile cleanups to support old shells
    - fix build with limits.h once for all
    - ev_epoll: do not rely on fd_sets anymore, use changes stacks instead.
    - fdtab now holds the results of polling
    - implemented support for speculative I/O processing with epoll()
    - remove useless calls to shutdown(SHUT_RD), resulting in small speed boost
    - auto-registering of pollers at load time

[BUILD] regparm in fd.h broke build on gcc-2.95

It was necessary to put the attribute after the type.

[MAJOR] introduced speculative I/O with epoll()

The principle behind speculative I/O is to speculatively try to
perform I/O before registering the events in the system. This
considerably reduces the number of calls to epoll_ctl() and
sometimes even epoll_wait(), and manages to increase overall
performance by about 10%.

The new poller has been called "sepoll". It is used by default
on Linux when it works. A corresponding option "nosepoll" and
the command line argument "-ds" allow to disable it.

[MAJOR] auto-registering of pollers at load time

Gcc provides __attribute__((constructor)) which is very convenient
to execute functions at startup right before main(). All the pollers
have been converted to have their register() function declared like
this, so that it is not necessary anymore to call them from a centralized
file.

[BUILD] declare epoll_* as static when using our own functions

We will have to share this code among several implementations.

[MAJOR] remove useless calls to shutdown(SHUT_RD)

shutdown(SHUT_RD) is useless on data TCP sockets. It does nothing
and consumes one syscall. Remove it.

[MAJOR] implemented support for speculative I/O processing

The pollers will now be able to speculatively call the I/O
processing functions and decide whether or not they want to
poll on those FDs. The changes primarily consist in teaching
those functions how to pass the info they got an EAGAIN.

[MINOR] add support for the polling results in fdtab

Now fdtab can contain the FD_POLL_* events so that the pollers
which can fill them can give userful information to readers and
writers about the precise condition of wakeup.

[MINOR] recompute maxfd before touching fdtab

It may be dangerous to play with fdtab before doing fd_insert()
because this last one is responsible for growing maxfd as needed.
Call fd_insert() before instead.

[MINOR] copy-paste typo when checking for -dk to disable kqueue.

[MAJOR] missing tv_now in kqueue_poll() blocking timeouts

a missing call to tv_now(&now) just after kevent() prevented
the timeouts from expiring.

[MAJOR] ev_epoll: do not rely on fd_sets anymore

The new epoll-based poller uses a list of changes in order to
process only the fds which have changed.

[BUILD] Fix limits.h once for all

Patch #cf83df3d162687d9c74783357421bd89f596eaac was stupid. Including
limits.h is portable and easier. At least it now builds on Solaris,
FreeBSD, Linux and OpenBSD.

[CLEANUP] make makefile more old sh-friendly

Older SH on Solaris does not know about $(cmd) but only know `cmd`.

[MINOR] kqueue: use fd_clo() to close the fd

fd_clo() does not call kevent() which is not needed during a close().
This one will be faster.

[MAJOR] delay registering of listener sockets at startup

Some pollers such as kqueue lose their FD across fork(), meaning that
the registered file descriptors are lost too. Now when the proxies are
started by start_proxies(), the file descriptors are not registered yet,
leaving enough time for the fork() to take place and to get a new pollfd.
It will be the first call to maintain_proxies that will register them.

[MEDIUM] kqueue: do not manually remove fds

FDs attached to a kevent are automatically removed after close().
Also, do not mark the FDs as EV_CLEAR. We want to stay informed
about readiness.

[BUILD] enable kqueue on MacOS X too

MacOS X is said to have kqueue. Let's enable it too.

[MAJOR] kqueue bug in handling infinite timeouts

Calls to kevent() need to pass NULL when there is no timeout.