BUG/MEDIUM: session: risk of crash on out of memory conditions

In session_accept(), if we face a memory allocation error, we try to
emit an HTTP 500 error message in HTTP mode. The problem is that we
must not use http_error_message() for this since it dereferences the
session which can be NULL in this case.

We don't need the session to build the error message anyway since
this function only uses it to retrieve the backend and frontend to
get the most suited error message. Let's pick it ourselves, we're
at the beginning of the session, only the frontend is relevant.

This bug is 1.5-specific.
BUG/MINOR: peers: set the accept date in outgoing connections

Without this, "show sess" on the CLI reports a wrong age.
BUG/MEDIUM: tcp: do not skip tracking rules on second pass

The track-sc* tcp rules are bogus. The test to verify if the
tracked counter was already assigned is performed in the same
condition as the test for the action. The effect is that a
rule which tracks a counter that is already being tracked
is implicitly converted to an accept because the default
rule is an accept.

This bug only affects 1.5-dev releases.
BUG/MEDIUM: acl: do not evaluate next terms after a miss

When a condition does something like :

   action if A B C || D E F

If B returns a miss (can't tell true or false), C must not
be evaluated. This is important when C has a side effect
(eg: sc*_inc_gpc0). However the second part after the ||
can still be evaluated.
MINOR: acl: add a warning when an ACL keyword is used without any value

It's quite common to write directives like the following :

  tcp-request reject if WAIT_END { sc0_inc_gpc0 }

This one will never reject, because sc0_inc_gpc0 is provided no value
to compare against. The proper form should have been something like this :

  tcp-request reject if WAIT_END { sc0_inc_gpc0 gt 0 }

or :

  tcp-request reject if WAIT_END { sc0_inc_gpc0 -m found }

Now we detect the absence of any argument on the command line and emit
a warning suggesting alternatives or the use of "--" to really avoid
matching anything (might be used when debugging).
MINOR: tcp: don't use tick_add_ifset() when timeout is known to be set

These two useless tests propably result from a copy-paste. The test is
performed in the condition to enter the block.
MINOR: buffer: align the last output line of buffer_dump()

If the dumped length of buffer is not multiple of 16, the last output line can
be seen as below:

Dumping contents from byte 0 to byte 125
         0  1  2  3  4  5  6  7    8  9  a  b  c  d  e  f
  0000: 47 45 54 20 2f 69 6e 64 - 65 78 2e 68 74 6d 20 48   GET /index.htm H
  0010: 54 54 50 2f 31 2e 30 0d - 0a 55 73 65 72 2d 41 67   TTP/1.0..User-Ag
  ...
  0060: 30 0d 0a 43 6f 6e 6e 65 - 63 74 69 6f 6e 3a 20 4b   0..Connection: K
  0070: 65 65 70 2d 41 6c 69 76 - 65 0d 0a 0d 0a   eep-Alive....

Yes, the hex column will be overlapped by the text column. Both the hex and
text column should be aligned at their own area as below:

Dumping contents from byte 0 to byte 125
         0  1  2  3  4  5  6  7    8  9  a  b  c  d  e  f
  0000: 47 45 54 20 2f 69 6e 64 - 65 78 2e 68 74 6d 20 48   GET /index.htm H
  0010: 54 54 50 2f 31 2e 30 0d - 0a 55 73 65 72 2d 41 67   TTP/1.0..User-Ag
  ...
  0060: 30 0d 0a 43 6f 6e 6e 65 - 63 74 69 6f 6e 3a 20 4b   0..Connection: K
  0070: 65 65 70 2d 41 6c 69 76 - 65 0d 0a 0d 0a            eep-Alive....

Signed-off-by: Godbach <nylzhaowei@gmail.com>
BUG/MINOR: acl: remove patterns from the tree before freeing them

A call to free_pattern_tree() upon exit() is made to free all ACL
patterns allocated in a tree (strings or IP addresses). Unfortunately
it happens that this function has been bogus from the beginning, it
walks over the whole tree, frees the nodes but forgets to remove them
from the tree prior to freeing them. So after visiting a leaf, the
next eb_next() call will require to revisit some of the upper nodes
that were just freed. This can remain unnoticed for a long time because
free() often just marks the area as free. But in cases of aggressive
memory freeing, the location will not be mapped anymore and the process
segfaults.

Note that the bug has no impact other than polluting kernel logs and
frightening sysadmins, since it happens just before exit().

Simply adding the debug code below makes it easier to reproduce the
same bug :

	while (node) {
		next = eb_next(node);
+		node->node_p = (void *)-1;
		free(node);
		node = next;
	}

Many thanks to the StackExchange team for their very detailed bug report
that permitted to quickly understand this non-obvious bug!

This fix should be backported to 1.4 which introduced the bug.
MEDIUM: backend: Enhance hash-type directive with an algorithm options

Summary:
In testing at tumblr, we found that using djb2 hashing instead of the
default sdbm hashing resulted is better workload distribution to our backends.

This commit implements a change, that allows the user to specify the hash
function they want to use. It does not limit itself to consistent hashing
scenarios.

The supported hash functions are sdbm (default), and djb2.

For a discussion of the feature and analysis, see mailing list thread
"Consistent hashing alternative to sdbm" :

      http://marc.info/?l=haproxy&m=138213693909219

Note: This change does NOT make changes to new features, for instance,
applying an avalance hashing always being performed before applying
consistent hashing.
MEDIUM: backend: Implement avalanche as a modifier of the hashing functions.

Summary:
Avalanche is supported not as a native hashing choice, but a modifier
on the hashing function. Note that this means that possible configs
written after 1.5-dev4 using "hash-type avalanche" will get an informative
error instead. But as discussed on the mailing list it seems nobody ever
used it anyway, so let's fix it before the final 1.5 release.

The default values were selected for backward compatibility with previous
releases, as discussed on the mailing list, which means that the consistent
hashing will still apply the avalanche hash by default when no explicit
algorithm is specified.

Examples
  (default) hash-type map-based
	Map based hashing using sdbm without avalanche

  (default) hash-type consistent
	Consistent hashing using sdbm with avalanche

Additional Examples:

  (a) hash-type map-based sdbm
	Same as default for map-based above
  (b) hash-type map-based sdbm avalanche
	Map based hashing using sdbm with avalanche
  (c) hash-type map-based djb2
	Map based hashing using djb2 without avalanche
  (d) hash-type map-based djb2 avalanche
	Map based hashing using djb2 with avalanche
  (e) hash-type consistent sdbm avalanche
	Same as default for consistent above
  (f) hash-type consistent sdbm
	Consistent hashing using sdbm without avalanche
  (g) hash-type consistent djb2
	Consistent hashing using djb2 without avalanche
  (h) hash-type consistent djb2 avalanche
	Consistent hashing using djb2 with avalanche
MEDIUM: backend: add support for the wt6 hash

This function was designed for haproxy while testing other functions
in the past. Initially it was not planned to be used given the not
very interesting numbers it showed on real URL data : it is not as
smooth as the other ones. But later tests showed that the other ones
are extremely sensible to the server count and the type of input data,
especially DJB2 which must not be used on numeric input. So in fact
this function is still a generally average performer and it can make
sense to merge it in the end, as it can provide an alternative to
sdbm+avalanche or djb2+avalanche for consistent hashing or when hashing
on numeric data such as a source IP address or a visitor identifier in
a URL parameter.
OPTIM/MEDIUM: epoll: fuse active events into polled ones during polling changes

When trying to speculatively send data to a server being connected to,
we see the following pattern :

    connect() = EINPROGRESS
    send() = EAGAIN
    epoll_ctl(add, W)
    epoll_wait() = EPOLLOUT
    send() = success
  > epoll_ctl(del, W)
  > recv() = EAGAIN
  > epoll_ctl(add, R)
    recv() = success
    epoll_ctl(del, R)

The reason for the failed recv() call is that the reading was marked
as speculative while we already have a polled I/O there. So we already
know when removing send write poll that the read is pending. Thus,
let's improve this by merging speculative I/O into polled I/O when
polled state changes. The result is now the following as expected :

    connect() = EINPROGRESS
    send() = EAGAIN
    epoll_ctl(add, W)
    epoll_wait() = EPOLLOUT
    send() = success
    epoll_ctl(mod, R)
    recv() = success
    epoll_ctl(del, R)

This is specific to epoll(), it doesn't make much sense at the moment
to do so for other pollers, because the cost of updating them is very
small.

The average performance gain on small requests is of 1.6% in TCP mode,
which is easily explained with the syscall stats below for 10000 forwarded
connections :

Before :
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 91.02    0.024608           0     60000         1 epoll_wait
  2.19    0.000593           0     20000           shutdown
  1.52    0.000412           0     10000     10000 connect
  1.36    0.000367           0     29998      9998 sendto
  1.09    0.000294           0     49993           epoll_ctl
  0.93    0.000252           0     50004     20002 recvfrom
  0.79    0.000214           0     20005           close
  0.62    0.000167           0     20001     10001 accept4
  0.25    0.000067           0     20002           setsockopt
  0.13    0.000035           0     10001           socket
  0.10    0.000028           0     10001           fcntl

After:
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 87.59    0.024269           0     50012         1 epoll_wait
  3.19    0.000884           0     20000           shutdown
  2.33    0.000646           0     29996      9996 sendto
  2.02    0.000560           0     10005     10003 connect
  1.40    0.000387           0     40013     10013 recvfrom
  1.35    0.000374           0     40000           epoll_ctl
  0.64    0.000178           0     20001     10001 accept4
  0.55    0.000152           0     20005           close
  0.45    0.000124           0     20002           setsockopt
  0.31    0.000086           0     10001           fcntl
  0.17    0.000047           0     10001           socket

Overall :
   -16.6% epoll_wait
   -20%   recvfrom
   -20%   epoll_ctl

On HTTP, the gain is even better :

% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 80.43    0.015386           0     60006         1 epoll_wait
  4.61    0.000882           0     30000     10000 sendto
  3.74    0.000715           0     20001     10001 accept4
  3.35    0.000640           0     10000     10000 connect
  2.66    0.000508           0     20005           close
  1.34    0.000257           0     30002     10002 recvfrom
  1.27    0.000242           0     30005           epoll_ctl
  1.20    0.000230           0     10000           shutdown
  0.62    0.000119           0     20003           setsockopt
  0.40    0.000077           0     10001           socket
  0.39    0.000074           0     10001           fcntl
willy@wtap:haproxy$ head -15 apres.txt
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 83.47    0.020301           0     50008         1 epoll_wait
  4.26    0.001036           0     20005           close
  3.30    0.000803           0     30000     10000 sendto
  2.55    0.000621           0     20001     10001 accept4
  1.76    0.000428           0     10000     10000 connect
  1.20    0.000292           0     10000           shutdown
  1.14    0.000278           0     20001         1 recvfrom
  0.86    0.000210           0     20003           epoll_ctl
  0.71    0.000173           0     20003           setsockopt
  0.49    0.000120           0     10001           socket
  0.25    0.000060           0     10001           fcntl

Overall :
  -16.6% epoll_wait
  -33%   recvfrom
  -33%   epoll_ctl
OPTIM/MINOR: mark the source address as already known on accept()

Commit 986a9d2d12 moved the source address from the stream interface
to the session, but it did not set the flag on the connection to
report that the source address is known. Thus when logs are enabled,
we had a call to getpeername() which is redundant with the result
from accept(). This patch simply sets the flag.
BUG/MINOR: stats: don't count tarpitted connections twice

When a connection is tarpitted, a denied req is counted once when the
action is applied, and then a failed req is counted when the tarpit
timeout expires. This is completely wrong as the tarpit is exactly
equivalent to a deny since it's a disguised deny.

So let's not increment the failed req anymore.

This fix may be backported to 1.4 which has the same issue.
CLEANUP: http: homogenize processing of denied req counter

The reqdeny/reqideny and reqtarpit/reqitarpit rules used to maintain
the stats counters themselves while http-request deny/tarpit and
rspdeny/rspideny used to centralize them at the point where the
error is processed.

Thus, let's do the same for reqdeny/reqtarpit so that the functions
which iterate over the rules do not have to deal with these counters
anymore.
CLEANUP: http: merge error handling for req* and http-request *

The reqdeny/reqtarpit and http-request deny/tarpit were using
a copy-paste of the error handling code because originally the
req* actions used to maintain their own stats. This is not the
case anymore so we can use the same error blocks for both.

The http-request rulesets still has precedence over req* so no
functionality was changed.
url32+src - like base32+src but whole url including parameters

I have a need to limit traffic to each url from each source address. much
like base32+src but the whole url including parameters (this came from
looking at the recent 'Haproxy rate limit per matching request' thread)

attached is patch that seems to do the job, its a copy and paste job of the
base32 functions

the url32 function seems to work too and using 2 machines to request the
same url locks me out of both if I abuse from either with the url32 key
function and only the one if I use url32_src.

Neil
BUG/MEDIUM: http: fix possible parser crash when parsing erroneous "http-request redirect" rules

Baptiste Assmann reported a bug affecting the "http-request redirect"
parser. It may randomly crash when reporting an error message if the
syntax is not OK. It happens that this is caused by the output error
message pointer which was not initialized to NULL.

This bug is 1.5-specific (introduced in dev17), no backport is needed.
BUG/MINOR: http: fix build warning introduced with url32/url32_src

commit 39c63c5 "url32+src - like base32+src but whole url including parameters"
was missing the last argument "const char *kw", resulting in the build warning
below :

src/proto_http.c:10351:2: warning: initialization from incompatible pointer type [enabled by default]
src/proto_http.c:10351:2: warning: (near initialization for 'sample_fetch_keywords.kw[50].process') [enabled by default]
src/proto_http.c:10352:2: warning: initialization from incompatible pointer type [enabled by default]
src/proto_http.c:10352:2: warning: (near initialization for 'sample_fetch_keywords.kw[51].process') [enabled by default]

It's harmless since it's not needed there anyway.
CLEANUP: Make parameters of srv_downtime and srv_getinter const

The parameters of srv_downtime and srv_getinter are not modified
and thus may be const.

Signed-off-by: Simon Horman <horms@verge.net.au>