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.
Merge branch 'master' of http://git.1wt.eu/git/haproxy