[MEDIUM] fade out memory usage when stopping proxies

Now we try to free as many pools as possible when a proxy is stopping.
The reason is that we want to ease the process replacement when applying
a new configuration, without keeping too many unused memory allocated.

[MEDIUM] Added easier support for Doug Lea's malloc (dlmalloc)

It's now as easy as passing "DLMALLOC_SRC=<path_to_dlmalloc.c>" to
build with support for dlmalloc. The dlmalloc source is not provided
with haproxy in order to ensure that people will use either the most
recent, or the most suited version for their platform. The minimal
mmap size is specified in DLMALLOC_THRES, which defaults to 4096. It
should be increased on platforms with larger pages (eg: 8 kB on some
64 bit systems).

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

    - acl: smarter integer comparison support in ACLs
    - acl: specify the direction during fetches
    - acl: provide the argument length for fetch functions
    - acl: provide a reference to the expr to fetch()
    - acl: implement matching on header values
    - acl: support maching on 'path' component
    - acl: permit to return any header when no name specified
    - errorfile: use a local file to feed error messages
    - negation in ACL conds was not cleared between terms
    - fix segfault at exit when using captures
    - improve memory freeing upon exit
    - acl: support '-i' to ignore case when matching
    - str2net() must not change the const char *
    - provide default ACLs
    - acl: distinguish between request and response headers
    - added the 'use_backend' keyword for full content-switching
    - acl: added the TRUE and FALSE ACLs.
    - shut warnings 'is*' macros from ctype.h on solaris

[CLEANUP] shut warnings 'is*' macros from ctype.h on solaris

Solaris visibly uses an array for is*, which returns warnings
about the use of signed chars as indexes. Good opportunity to
put casts everywhere.

[MEDIUM] acl: added the TRUE and FALSE ACLs.

Those ACLs are sometimes useful for troubleshooting. Two ACL subjects
"always_true" and "always_false" have been added too. They return what
their subject says for every pattern. Also, acl_match_pst() has been
removed.

[MAJOR] added the 'use_backend' keyword for full content-switching

The new "use_backend" keyword permits full content switching by the
use of ACLs. Its usage is simple :

   use_backend <backend_name> {if|unless} <acl_cond>

[MEDIUM] acl: distinguish between request and response headers

hdr(x) will now still be used for request headers, and shdr(x) for
server headers (response).

[MEDIUM] provide default ACLs

The following ACLs are predefined :

  LOCALHOST      = src 127.0.0.1/8
  HTTP_1.0       = req_ver 1.0
  HTTP_1.1       = req_ver 1.1
  METH_CONNECT   = method CONNECT
  METH_GET       = method GET HEAD
  METH_HEAD      = method HEAD
  METH_OPTIONS   = method OPTIONS
  METH_POST      = method POST
  METH_TRACE     = method TRACE
  HTTP_URL_ABS   = url_reg ^[^/:]*://
  HTTP_URL_SLASH = url_beg /
  HTTP_URL_STAR  = url *
  HTTP_CONTENT   = hdr_val(content-length) gt 0

[BUG] str2net() must not change the const char *

str2net needs to put \0 in a const char *. Use strdup() for that.

[MEDIUM] acl: support '-i' to ignore case when matching

Implemented the "-i" option on ACLs to state that the matching
will have to be performed for all patterns ignoring case. The
usage is :

   acl <aclname> <aclsubject> -i pattern1 ...

If a pattern must begin with "-", either it must not be the first one,
or the "--" option should be specified first.

[MINOR] improve memory freeing upon exit

The deinit() function is specialized in memory area freeing.
There were a ton of information that were not released at the
exit time, which made valgrind complain. Now, most of the entries
are freed. However, it seems like regfree() does not completely
free a regex (12 bytes lost per regex).

[BUG] fix segfault at exit when using captures

since pools v2, the way pools were destroyed at exit is incorrect
because it ought to account for users of those pools before freeing
them. This test also ensures there is no double free.

[BUG] negation in ACL conds was not cleared between terms

The exclamation mark (!) in front of an ACL condition was propagated
to the whole line instead of being flushed after parsing an acl name.

[MEDIUM] errorfile: use a local file to feed error messages

It is now possible to read error messages from local files,
using the 'errorfile' keyword. Those files are read during
parsing, so there's no I/O involved. They make it possible
to return custom error messages with custom status and headers.

[MINOR] acl: permit to return any header when no name specified

Having the ability to match on hdr_xxx in addition to hdr_xxx(yyy)
makes it possible to match any value or to count the headers easily.

[MEDIUM] acl: support maching on 'path' component

'path', 'path_reg', 'path_beg', 'path_end', 'path_sub', 'path_dir'
and 'path_dom' have been implemented to process the path component
of the URI. It starts after the host part, and stops before the
question mark.

[MEDIUM] acl: implement matching on header values

hdr(x), hdr_reg(x), hdr_beg(x), hdr_end(x), hdr_sub(x), hdr_dir(x),
hdr_dom(x), hdr_cnt(x) and hdr_val(x) have been implemented. They
apply to any of the possibly multiple values of header <x>.

Right now, hdr_val() is limited to integer matching, but it should
reasonably be upgraded to match long long ints.

[MINOR] acl: provide a reference to the expr to fetch()

The fetch() functions may need to access the full expr to get
their args. Turn the void *arg into a struct acl_expr *expr.

[MINOR] acl: provide the argument length for fetch functions

Some fetch() functions will require an argument (eg: header).
It's wise to provide the argument size to optimize string
comparisons.

[MINOR] acl: specify the direction during fetches

Some fetches such as 'line' or 'hdr' need to know the direction of
the test (request or response). A new 'dir' parameter is now
propagated from the caller to achieve this.

[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.