[ANNOUNCE] haproxy-2.3-dev5

[Christopher Faulet]

Hi,

HAProxy 2.3-dev5 was released on 2020/09/25. It added 104 new commits
after version 2.3-dev4.

Willy has finally finished the first part of the listeners rework and
pushed a bunch of patches. First, the listener and bind_conf structures
have been reorganized to better suite the new design. The listening socket
settings have been moved in a dedicated structure, inlined in the
bind_conf. Thanks to this change, it has been possible to split the
listeners into the listener part and the receiver part. The protocols have
then been reworked to have a listener callback function, responsible to
start a listener and a bind callback function, responsible to bind the
receiver. Both were previously performed by the same callback function. In
addition, common functions used for a given address familily (INET4, INET6,
UNIX...) have been regrouped into a new structure, proto_fam, and
referenced in the protocols. And the last be not the least, the
str2sa_range() function, responsible to parse addresses, has been totally
refactored to be less ambiguous. This function was full of exceptions to
guess the calling context. Now, it is the caller responsibility to provide
desired parsing options.

All this description is probably a bit cryptic and it does not do Willy's
work justice. It was amazingly hard and painful to unmangle. But, it was a
mandatory step to add the QUIC support. The next changes to come in this
area are about the way listeners, receivers and proxies are started,
stopped, paused or resumed.

On his part, William has removed the support of the multi certificates
bundle, to load each certificate in a separate SSL_CTX. This was
implemented with openssl 1.0.2 to load different certificates (RSA, ECDSA
and DSA) for the same SNI host, in the same SSL_CTX, before the
client_hello callback was available. It is now a deprecated way to do and
a mess to maintain. He has also fixed a bug about the verifyhost option
which should be case insensitive.

Still on the SSL part, Olivier has fixed a crash when we were waiting for
the availability of the crypto engine. In its FD handler function, the I/O
callback function was called directly with a NULL tasklet, leading to a
crash. Now, a tasklet wakeup is performed.

The "path-only" option has been added to "balance uri" to have a
consistent way to balance H1 and H2 requests, based on the path, excluding
any authority part.

Finally, the usual set of fixes. Two memory leaks during configuration
parsing have been fixed, thanks to Amaury and Eric. A subtle bug has been
fixed in the smp_prefetch_htx() function causing the "method" sample fetch
to fail for unknown method. And so on.

Thanks to everyone working on this release.

Please find the usual URLs below :
   Site index   : http://www.haproxy.org/
   Discourse: http://discourse.haproxy.org/
   Slack channel: https://slack.haproxy.org/
   Issue tracker: https://github.com/haproxy/haproxy/issues
   Wiki : https://github.com/haproxy/wiki/wiki
   Sources  : http://www.haproxy.org/download/2.3/src/
   Git repository   : http://git.haproxy.org/git/haproxy.git/
   Git Web browsing : http://git.haproxy.org/?p=haproxy.git
   Changelog: http://www.haproxy.org/download/2.3/src/CHANGELOG
   Cyril's HTML doc : http://cbonte.github.io/haproxy-dconv/


---
Complete changelog :
Amaury Denoyelle (1):
  BUG/MINOR: config: Fix memory leak on config parse listen

Brad Smith (1):
  BUILD: makefile: change default value of CC from gcc to cc

Christopher Faulet (1):
  BUG/MINOR: http-fetch: Don't set the sample type during the htx prefetch

Eric Salama (1):
  BUG/MINOR: Fix memory leaks cfg_parse_peers

Ilya Shipitsin (4):
  CLEANUP: Update .gitignore
  BUILD: introduce possibility to define ABORT_NOW() conditionally
  CI: travis-ci: help Coverity to recognize abort()
  CI: travis-ci: split asan step out of running tests

Miroslav Zagorac (1):
  BUILD: trace: include tools.h

Olivier Houchard (1):
  BUG/MEDIUM: ssl: Don't call ssl_sock_io_cb() directly.

Tim Duesterhus (3):
  DOC: Fix typo in iif() example
  BUG/MINOR: Fix type passed of sizeof() for calloc()
  CLEANUP: Do not use a fixed type for 'sizeof' in 'calloc'

William Lallemand (13):
  BUG/MINOR: ssl: verifyhost is case sensitive
  BUG/MINOR: ssl/crt-list: crt-list could end without a \n
  MEDIUM: ssl: remove bundle support in crt-list and directories
  MEDIUM: ssl/cli: remove support for multi certificates bundle
  MINOR: ssl: crtlist_dup_ssl_conf() duplicates a ssl_bind_conf
  MINOR: ssl: crtlist_entry_dup() duplicates a crtlist_entry
  MEDIUM: ssl: emulates the multi-cert bundles in the crtlist
  MEDIUM: ssl: emulate multi-cert bundles loading in standard loading
  CLEANUP: ssl: remove test on "multi" variable in ckch functions
  CLEANUP: ssl/cli: remove test on 'multi' variable in CLI functions
  CLEANUP: ssl: remove utility functions for 

Re: [PATCH] BUILD: trace: include tools.h

[Miroslav Zagorac]

On 09/25/2020 05:59 PM, Willy Tarreau wrote:

Git uses the "---" marker as an end of commit message, to put your
comments to committers below. So when I applied your patch, it dropped
this part. I've reintroduced it, but I thought you would like to know
in order not to get caught by accident on another patch if you're used
to use this :-)

Oh and by the way it also drops lines starting with "#" which tends
to annoy me as I get caught once in a while when referencing a github
issue at the beginning of a line!



Hello Willy,

thank you for the info, I made a comment for commit with 'git commit 
--amend' so I could add those lines with '---'.  When I got the patch 
with 'git format-patch -1' I was a little surprised by those multiple 
lines with '---' but I didn't remove it.


--
Zaga

What can change the nature of a man?

Re: Random with Two Choices Load Balancing Algorithm

[Willy Tarreau]

Hi Norman,

On Fri, Sep 25, 2020 at 03:58:54PM +, Branitsky, Norman wrote:
> Wondering if this was ever implemented?

Yes it was merged into 2.0, it's used by default when you select
random since it's always slightly better than a naive random, and
you can even configure it to set the number of draws you want.

I also made some experiments to measure the gains :

https://www.haproxy.com/blog/power-of-two-load-balancing/

TL;DR: it's only better than the default random, but isn't as good as
the real leastconn like the one we have which is combined with round
robin hance limits collisions between LB nodes in a distributed system.

Willy

RE: Random with Two Choices Load Balancing Algorithm

[Branitsky, Norman]

Wondering if this was ever implemented?

Norman Branitsky
Senior Cloud Architect
P: 416-916-1752

-Original Message-
From: Willy Tarreau  
Sent: Saturday, December 15, 2018 11:09 AM
To: Norman Branitsky 
Cc: haproxy@formilux.org
Subject: Re: Random with Two Choices Load Balancing Algorithm

Hi Norman,

On Thu, Dec 06, 2018 at 04:57:18PM +, Norman Branitsky wrote:
> NGINX just announced the following load balancing method as default for their 
> Ingress Controller for Kubernetes.
> Will this appear on the HAProxy roadmap?

That's interesting because we've had a discussion about this very same algo not 
too long ago with a coworker. I said that it should be trivial to implement, 
though I think that it might make sense to make the number of tries 
configurable. Indeed, I need to read the complete thesis on it but I suspect it 
can make sense to take more than 2 tries if the number of servers and/or LB 
nodes (or the product of the two) is very high. Maybe we'll end up picking 
log()+1 or something like this.

But yes that's definitely very interesting.

Thanks,
Willy

Re: [PATCH] BUILD: trace: include tools.h

[Willy Tarreau]

Hi Miroslav,

On Thu, Sep 24, 2020 at 09:43:56AM +0200, Miroslav Zagorac wrote:
> Hello,
> 
> haproxy cannot be compiled on debian 9.13 if the TRACE option is used.

Thanks, applied!

Note below:
> ---
> src/calltrace.o: In function `make_line':
> .../src/calltrace.c:204: undefined reference to `rdtsc'
> src/calltrace.o: In function `calltrace':
> .../src/calltrace.c:277: undefined reference to `rdtsc'
> collect2: error: ld returned 1 exit status
> Makefile:866: recipe for target 'haproxy' failed
> ---

Git uses the "---" marker as an end of commit message, to put your
comments to committers below. So when I applied your patch, it dropped
this part. I've reintroduced it, but I thought you would like to know
in order not to get caught by accident on another patch if you're used
to use this :-)

Oh and by the way it also drops lines starting with "#" which tends
to annoy me as I get caught once in a while when referencing a github
issue at the beginning of a line!

Cheers,
Willy

Re: source algorithm - question.

[Willy Tarreau]

On Fri, Sep 25, 2020 at 03:57:58PM +0200, Lukasz Tasz wrote:
> first is opposite to leastconn - first keep load at the beginning,
> leastconn same everywhere.

Indeed.

> but why source is limiting balancing only to one machine?

Because in almost every case people want to use it to maintain affinity.
For example you don't want the control and data connection of an FTP
client to go to different servers.

> would it be possible to remove this limitation?

It's in part done by hash-balance-factor which forces the algorithm
to pick a different server when the one initially choosen has too high
a load.

However removing completely a hashed server from the pool every time it
reaches its limits would have serious consequences in terms of CPU usage.
At high loads a server should constantly run at its limit, which means
that it's constantly added and removed to/from the pool. This can happen
hundreds of thousands of times per second. Adding or removing a hashed
server into the pool means:
  - recomputing the whole farm's hash for static algorithms
  - inserting or removing a large number of instances of this server
from the consistent hash tree when using consistent hashing

Both are very expensive and while they're actually acceptable for the
rare cases where a server goes up or down, they're really not for when
a server reaches a limit or drops below.

Also, at a low dose, queuing is good and can even be faster than
spreading the load on more servers because it makes a more efficient
use of network packets and TCP connections by merging requests with
ACKs, and can deliver a request to a server having the code to handle
it hot in its cache with a CPU already running at top speed. But that's
true for small queue sizes of course.

Before we had hash-balance-factor, some people were doing something
related to what you describe by using two backends: one with the hash
LB algorithm, and another one with RR, random or anything. And they
would choose what backend to use depending on the average queue size
in the first backend, using the avg_queue(backend) sample fetch.

Now with hash-balance-factor, I really think you could reach your
goal, because usually if a server has some requests in queue, either
all of them do, and you don't care what server you pick, or one has
not, and hash-balance-factor will spot it and use it instead. Just
run it with a very low value, e.g. 101, and that should be OK.

If that's not sufficient, I think we could imagine adding a "no-queue"
option to the balance keyword to indicate that when the selected server
is full, instead the request should be queued in the backend. It would
still require significant changes to make sure that such a request can
*first* be attempted on another server before being queued but I think
it might be possible. An alternative would be to have a modifier on the
consistent hash algorithms to try to find a different server when the
selected one has some queue. The problem is, we need to limit the
attempts because we don't want to loop forever if all have some queue.
Maybe that could actually be a variant of the hash-balance-factor to
ask it to systematically ignore servers with queue.

regards,
Willy

Re: [2.0.17] crash with coredump

[Kirill A. Korinsky]

Very interesting.

Anyway, I can see that this pice of code was refactored some time ago: 
https://github.com/haproxy/haproxy/commit/f96508aae6b49277dcf142caa35042678cf8e2ca
 


Maybe it is worth to try 2.2 or 2.3 branch?

Yes, it is a blind shot and just a guess.

--
wbr, Kirill

> On 25. Sep 2020, at 16:01, Maciej Zdeb  wrote:
> 
> Yes at the same place with same value:
> 
> (gdb) bt full
> #0  0x559ce98b964b in h2s_notify_recv (h2s=0x559cef94e7e0) at 
> src/mux_h2.c:783
> sw = 0x
> 
> 
> 
> pt., 25 wrz 2020 o 15:42 Kirill A. Korinsky  > napisał(a):
> > On 25. Sep 2020, at 15:26, Maciej Zdeb  > > wrote:
> >
> > I was mailing outside the list with Willy and Christopher but it's worth 
> > sharing that the problem occurs even with nbthread = 1. I've managed to 
> > confirm it today.
> 
> 
> I'm curious is it crashed at the same place with the same value?
> 
> --
> wbr, Kirill
> 
> 



signature.asc
Description: Message signed with OpenPGP

Re: [2.0.17] crash with coredump

[Willy Tarreau]

On Fri, Sep 25, 2020 at 03:26:47PM +0200, Kirill A. Korinsky wrote:
> > On 25. Sep 2020, at 15:06, Willy Tarreau  wrote:
> > 
> > Till here your analysis is right but:
> >  - the overflow would only be at most the number of extra threads running
> >init_genrand() concurrently, or more precisely the distance between
> >the most upfront to the latest thread, so in the worst case nbthread-1
> >hence there's no way to write a single location into a totally unrelated
> >structure without writing the nbthread-2 words that are between the end
> >of the MT array and the overwritten location ;
> 
> I don't think so.
> 
> We have two threads and steps
> 
> 1. T1: mti < N
> 2. T2: mti < N
> 3. T1:  mtii++
> 4. T2:  mtii++
> 5. T1: mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
> 6. T2: mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
> 
> Let assume that mti = N - 1 at steps 1 and 2. At this case mti (aka MT->o) is 
> N + 1 that is overflow of mt array (MT->v).
> 
> So, when T1 writes something at step 5 it puts a random value to mti (aka
> MT->i). Here I assume that the sume has dwrod similar that size(long) and MT
> hasn't got any gaps between v and I.
> 
> If so at step 6 we have mti with random value and writes to unpredicted place
> in memory.

Oh indeed you're totally right, I didn't notice that i was stored right after
the array! So yes, the index can be overflown with a random value. However,
the probability that a random 32-bit value used as an offset relative to
the previous array remains valid without crashing the process is extremely
low, and the probability that each time it lands in the exact same field of
another totally unrelated structure is even lower.

> >  - the lua code is not threaded (there's a "big lock" around lua since
> >stacks cannot easily be protected, though Thierry has some ideas for
> >this).
> 
> What does not threaded mean here?

My understanding is that this code is loaded from within Lua. And you
have only one thread running Lua at a time, since Lua itself is not
thread safe (it can be built to use external locks but apparently noone
builds it like this by default so it's not usable this way), this is
protected by hlua_global_lock. So you won't have two competing calls
to lrandom from Lua.

However I agree that the bug you found (which I looked for and didn't
spot last time I checked) is real for threaded applications.

Willy

Re: [2.0.17] crash with coredump

[Willy Tarreau]

On Fri, Sep 25, 2020 at 03:26:05PM +0200, Maciej Zdeb wrote:
> > Here I can suggest to implement Yarrow PRGN (that is very simple to
> > implement) with some lua-pure cryptographic hash function.
> 
> We're using lrandom because of the algorithm Mersenne Twister and its well
> known weaknesses and strengths.
> 
> > In fact I know it's possible to call haproxy's internal sample fetch
> > functions from Lua (I never can figure how to do that, I always need
> > to lookup an example for this unfortunately). But once you figure out how
> > to do it, you can call the "rand()" sample fetch that will call the
> > internal thread-safe random number generator.
> 
> Rand() sample fetch cannot be seeded (at the time we checked) so on HAProxy
> servers with nbproc > 1 we got multiple sequences of the same random
> numbers - it was one of the reasons we couldn't use it.

That was fixed long ago in 2.2-dev4 exactly for this reason:

  commit 52bf839394e683eec2fa8aafff5a0dd51d2dd365
  Author: Willy Tarreau 
  Date:   Sun Mar 8 00:42:37 2020 +0100

BUG/MEDIUM: random: implement a thread-safe and process-safe PRNG

This is the replacement of failed attempt to add thread safety and
per-process sequences of random numbers initally tried with commit
1c306aa84d ("BUG/MEDIUM: random: implement per-thread and per-process
random sequences").
(...)
It supports fast jumps allowing to cut the period into smaller
non-overlapping sequences, which we use here to support up to 2^32
processes each having their own, non-overlapping sequence of 2^96
numbers (~7*10^28). This is enough to provide 1 billion randoms per
second and per process for 2200 billion years.

This was backported into 2.0.14 as well. So if you know how to use it
you definitely can right now. But as I mentioned, the thread-unsafety
of lrandom isn't related to your issue at the moment anyway.

> I was mailing outside the list with Willy and Christopher but it's worth
> sharing that the problem occurs even with nbthread = 1. I've managed to
> confirm it today.

Yes, thanks for the info by the way, however being blocked on something
else at the moment I didn't have the opportunity to have a look at it yet.

Regards,
Willy

Re: [2.0.17] crash with coredump

[Maciej Zdeb]

Yes at the same place with same value:

(gdb) bt full
#0  0x559ce98b964b in h2s_notify_recv (h2s=0x559cef94e7e0) at
src/mux_h2.c:783
sw = 0x



pt., 25 wrz 2020 o 15:42 Kirill A. Korinsky  napisał(a):

> > On 25. Sep 2020, at 15:26, Maciej Zdeb  wrote:
> >
> > I was mailing outside the list with Willy and Christopher but it's worth
> sharing that the problem occurs even with nbthread = 1. I've managed to
> confirm it today.
>
>
> I'm curious is it crashed at the same place with the same value?
>
> --
> wbr, Kirill
>
>
>

Re: source algorithm - question.

[Łukasz Tasz]

hi,
thanks for answer,
Not exactly, rather a mix of source and first.
reason behind is that in case that we have free resources, different
clients would get different machines,
with "first" you will get first available slot - and reason behind is to
scale down
source works good until one client still has access to whole backend -
while here it is limited to one backend server.

first is opposite to leastconn - first keep load at the beginning,
leastconn same everywhere.

but why source is limiting balancing only to one machine? would it be
possible to remove this limitation?

Łukasz Tasz
RTKW


czw., 24 wrz 2020 o 15:51 Lukas Tribus  napisał(a):

> Hello,
>
> On Thu, 24 Sep 2020 at 11:40, Łukasz Tasz  wrote:
> >
> > Hi all,
> > haproxy is gr8 - simply.
> >
> > Till today I was using roundobin algorithm, but after studying
> documentation it popped up that source might be better.
> > I'm using haproxy in tcp mode, version 1.8, load from one client
> sometimes requires more then few servers from the backend.
> >
> > but also initialization of handling requests takes some cost - I
> considered picking a source as an algorithm - to avoid picking the next
> server according to roundrobin.
> > But I realised that the behaviour of the queue has changed. With a
> source algorithm for every source(host, client) there is a separate queue
> and one server picked.
> > would it be possible that when one server reaches it's slots, the next
> one is allocated (and next one, and next one)? where I can find detailed
> information on how queues are managed depending on the algorithm which is
> used?
>
> It sounds like what you are looking for is "balance first".
>
> You can read more about this in the documentation about balance:
>
> https://cbonte.github.io/haproxy-dconv/2.0/configuration.html#4.2-balance
>
>
> Lukas
>

Re: [2.0.17] crash with coredump

[Kirill A. Korinsky]

> On 25. Sep 2020, at 15:26, Maciej Zdeb  wrote:
> 
> I was mailing outside the list with Willy and Christopher but it's worth 
> sharing that the problem occurs even with nbthread = 1. I've managed to 
> confirm it today.


I'm curious is it crashed at the same place with the same value?

--
wbr, Kirill




signature.asc
Description: Message signed with OpenPGP

Re: [2.0.17] crash with coredump

[Kirill A. Korinsky]

> On 25. Sep 2020, at 15:06, Willy Tarreau  wrote:
> 
> Till here your analysis is right but:
>  - the overflow would only be at most the number of extra threads running
>init_genrand() concurrently, or more precisely the distance between
>the most upfront to the latest thread, so in the worst case nbthread-1
>hence there's no way to write a single location into a totally unrelated
>structure without writing the nbthread-2 words that are between the end
>of the MT array and the overwritten location ;

I don't think so.

We have two threads and steps

1. T1: mti < N
2. T2: mti < N
3. T1:  mtii++
4. T2:  mtii++
5. T1: mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);
6. T2: mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti);

Let assume that mti = N - 1 at steps 1 and 2. At this case mti (aka MT->o) is N 
+ 1 that is overflow of mt array (MT->v).

So, when T1 writes something at step 5 it puts a random value to mti (aka 
MT->i). Here I assume that the sume has dwrod similar that size(long) and MT 
hasn't got any gaps between v and I.

If so at step 6 we have mti with random value and writes to unpredicted place 
in memory.

>  - the lua code is not threaded (there's a "big lock" around lua since
>stacks cannot easily be protected, though Thierry has some ideas for
>this).

What does not threaded mean here?

I can understand it as all lua function is executed from the only one thread 
(1), or one call is executed at the same thread but different thread can 
execute the same lua code for different TCP/HTTP streams at the same time (2).


--
wbr, Kirill



signature.asc
Description: Message signed with OpenPGP

Re: [2.0.17] crash with coredump

[Maciej Zdeb]

> Here I can suggest to implement Yarrow PRGN (that is very simple to
> implement) with some lua-pure cryptographic hash function.

We're using lrandom because of the algorithm Mersenne Twister and its well
known weaknesses and strengths.

> In fact I know it's possible to call haproxy's internal sample fetch
> functions from Lua (I never can figure how to do that, I always need
> to lookup an example for this unfortunately). But once you figure out how
> to do it, you can call the "rand()" sample fetch that will call the
> internal thread-safe random number generator.

Rand() sample fetch cannot be seeded (at the time we checked) so on HAProxy
servers with nbproc > 1 we got multiple sequences of the same random
numbers - it was one of the reasons we couldn't use it.

I was mailing outside the list with Willy and Christopher but it's worth
sharing that the problem occurs even with nbthread = 1. I've managed to
confirm it today.

pt., 25 wrz 2020 o 15:06 Willy Tarreau  napisał(a):

> Hi Kirill,
>
> On Fri, Sep 25, 2020 at 12:34:16PM +0200, Kirill A. Korinsky wrote:
> > I've extracted a pice of code from lrandom and put it here:
> > https://gist.github.com/catap/bf862cc0d289083fc1ccd38c905e2416
> > 
> >
> > You can see that object generator contains N words (and here it is 624),
> and
> > I use an assumption that Maciej's code doesn't create a new generator for
> > each request and share lrandom.
> >
> > Idea of this RNG is initialize each N words via init_genrand and it
> checking
> > that all of them are used, and after one generated a new ones.
> >
> > Let assume that we called genrand_int32 at the same moment from two
> threads.
> > If condition at lines 39 and 43 are true we start to initialize the next
> > words at both threads.
> >
> > You can see that we can easy move outside of v array at line 21 because
> two
> > threads are increasing i field, and put some random number to i field.
>
> Till here your analysis is right but:
>   - the overflow would only be at most the number of extra threads running
> init_genrand() concurrently, or more precisely the distance between
> the most upfront to the latest thread, so in the worst case nbthread-1
> hence there's no way to write a single location into a totally
> unrelated
> structure without writing the nbthread-2 words that are between the end
> of the MT array and the overwritten location ;
>
>   - the lua code is not threaded (there's a "big lock" around lua since
> stacks cannot easily be protected, though Thierry has some ideas for
> this).
>
> > Ans when the second thread is going to line 27 and nobody knows where it
> put 0x
>
> Actually init_genrand() doesn't actually *write* 0x but only writes
> *something* of 64 bits size and applies a 32-bit mask over it, so it would
> have written 32 bits pseudo-random bits followed by 4 zero bytes.
>
> > How can it be proved / solved?
> >
> > I see a few possible options:
> > 1. Switch off threads inside haproxy
> > 2. Use dedicated lrandom per thread
> > 3. Move away from lrandom
> >
> > As I understand lrandom is using here because it is very fast and
> secure, and
> > reading from /dev/urandom isn't an option.
> >
> > Here I can suggest to implement Yarrow PRGN (that is very simple to
> > implement) with some lua-pure cryptographic hash function.
>
> In fact I know it's possible to call haproxy's internal sample fetch
> functions from Lua (I never can figure how to do that, I always need
> to lookup an example for this unfortunately). But once you figure how
> to do it, you can call the "rand()" sample fetch that will call the
> internal thread-safe random number generator.
>
> Regards,
> Willy
>

Re: [2.0.17] crash with coredump

[Willy Tarreau]

Hi Kirill,

On Fri, Sep 25, 2020 at 12:34:16PM +0200, Kirill A. Korinsky wrote:
> I've extracted a pice of code from lrandom and put it here:
> https://gist.github.com/catap/bf862cc0d289083fc1ccd38c905e2416
> 
> 
> You can see that object generator contains N words (and here it is 624), and
> I use an assumption that Maciej's code doesn't create a new generator for
> each request and share lrandom.
> 
> Idea of this RNG is initialize each N words via init_genrand and it checking
> that all of them are used, and after one generated a new ones.
> 
> Let assume that we called genrand_int32 at the same moment from two threads.
> If condition at lines 39 and 43 are true we start to initialize the next
> words at both threads.
> 
> You can see that we can easy move outside of v array at line 21 because two
> threads are increasing i field, and put some random number to i field.

Till here your analysis is right but:
  - the overflow would only be at most the number of extra threads running
init_genrand() concurrently, or more precisely the distance between
the most upfront to the latest thread, so in the worst case nbthread-1
hence there's no way to write a single location into a totally unrelated
structure without writing the nbthread-2 words that are between the end
of the MT array and the overwritten location ;

  - the lua code is not threaded (there's a "big lock" around lua since
stacks cannot easily be protected, though Thierry has some ideas for
this).

> Ans when the second thread is going to line 27 and nobody knows where it put 
> 0x

Actually init_genrand() doesn't actually *write* 0x but only writes
*something* of 64 bits size and applies a 32-bit mask over it, so it would
have written 32 bits pseudo-random bits followed by 4 zero bytes.

> How can it be proved / solved?
> 
> I see a few possible options:
> 1. Switch off threads inside haproxy
> 2. Use dedicated lrandom per thread
> 3. Move away from lrandom
> 
> As I understand lrandom is using here because it is very fast and secure, and
> reading from /dev/urandom isn't an option.
> 
> Here I can suggest to implement Yarrow PRGN (that is very simple to
> implement) with some lua-pure cryptographic hash function.

In fact I know it's possible to call haproxy's internal sample fetch
functions from Lua (I never can figure how to do that, I always need
to lookup an example for this unfortunately). But once you figure how
to do it, you can call the "rand()" sample fetch that will call the
internal thread-safe random number generator.

Regards,
Willy

Re: [2.0.17] crash with coredump

[Maciej Zdeb]

Hi Kirill,

Thanks for your hints and time! Unfortunately, I think lrandom is not the
cause of crash. We're using lrandom with threads for couple of months on
our other servers without any crash. I think lua in HAproxy is executed in
a single thread so your analysis is correct but this assumption is never
true: "Let assume that we called genrand_int32 at the same moment from two
threads." in HAProxy environment.

I suspect something is going on in SPOE or LUA scripts from external
vendor. I'll share more details as soon as I confirm it is in SPOE or LUA.


pt., 25 wrz 2020 o 12:34 Kirill A. Korinsky  napisał(a):

> Good day,
>
> I'd like to share with your my two cents regarding this topic:
>
> lrandom (PRNG for lua, we're using it for 2 or 3 years without any
> problems, and soon we will drop it from our build)
>
>
> Never heard of this last one, not that it would make it suspicious at
> all, just that it might indicate you're having a slightly different
> workload than most common ones and can help spotting directions where
> to look for the problem.
>
>
>
> As far as I know Haproxy is using threads by default for some time and I
> assume that Maciej's setup doesn't change anything and it had enabled
> threads.
>
> If so I believe that lrandom is the root cause of this issue.
>
> I've extracted a pice of code from lrandom and put it here:
> https://gist.github.com/catap/bf862cc0d289083fc1ccd38c905e2416
>
> You can see that object generator contains N words (and here it is 624),
> and I use an assumption that Maciej's code doesn't create a new generator
> for each request and share lrandom.
>
> Idea of this RNG is initialize each N words via init_genrand and it
> checking that all of them are used, and after one generated a new ones.
>
> Let assume that we called genrand_int32 at the same moment from two
> threads. If condition at lines 39 and 43 are true we start to initialize
> the next words at both threads.
>
> You can see that we can easy move outside of v array at line 21 because
> two threads are increasing i field, and put some random number to i field.
>
> Ans when the second thread is going to line 27 and nobody knows where it
> put 0x
>
> Let me quote Willy Tarreau:
>
> In the trace it's said that sw = 0x. Looking at all places where
> h2s->recv_wait() is modified, it's either NULL or a valid pointer to some
> structure. We could have imagined that for whatever reason h2s is wrong
> here, but this call only happens when its state is still valid, and it
> experiences double dereferences before landing here, which tends to
> indicate that the h2s pointer is OK. Thus the only hypothesis I can have
> for now is memory corruption :-/ That field would get overwritten with
> (int)-1 for whatever reason, maybe a wrong cast somewhere, but it's not
> as if we had many of these.
>
>
> and base on this I believe that it is the case.
>
> How can it be proved / solved?
>
> I see a few possible options:
> 1. Switch off threads inside haproxy
> 2. Use dedicated lrandom per thread
> 3. Move away from lrandom
>
> As I understand lrandom is using here because it is very fast and secure,
> and reading from /dev/urandom isn't an option.
>
> Here I can suggest to implement Yarrow PRGN (that is very simple to
> implement) with some lua-pure cryptographic hash function.
>
> --
> wbr, Kirill
>
>

Re: [2.0.17] crash with coredump

[Kirill A. Korinsky]

Good day,

I'd like to share with your my two cents regarding this topic:

>> lrandom (PRNG for lua, we're using it for 2 or 3 years without any
>> problems, and soon we will drop it from our build)
> 
> Never heard of this last one, not that it would make it suspicious at
> all, just that it might indicate you're having a slightly different
> workload than most common ones and can help spotting directions where
> to look for the problem.


As far as I know Haproxy is using threads by default for some time and I assume 
that Maciej's setup doesn't change anything and it had enabled threads.

If so I believe that lrandom is the root cause of this issue.

I've extracted a pice of code from lrandom and put it here: 
https://gist.github.com/catap/bf862cc0d289083fc1ccd38c905e2416 


You can see that object generator contains N words (and here it is 624), and I 
use an assumption that Maciej's code doesn't create a new generator for each 
request and share lrandom.

Idea of this RNG is initialize each N words via init_genrand and it checking 
that all of them are used, and after one generated a new ones.

Let assume that we called genrand_int32 at the same moment from two threads. If 
condition at lines 39 and 43 are true we start to initialize the next words at 
both threads.

You can see that we can easy move outside of v array at line 21 because two 
threads are increasing i field, and put some random number to i field.

Ans when the second thread is going to line 27 and nobody knows where it put 
0x

Let me quote Willy Tarreau:

> In the trace it's said that sw = 0x. Looking at all places where
> h2s->recv_wait() is modified, it's either NULL or a valid pointer to some
> structure. We could have imagined that for whatever reason h2s is wrong
> here, but this call only happens when its state is still valid, and it
> experiences double dereferences before landing here, which tends to
> indicate that the h2s pointer is OK. Thus the only hypothesis I can have
> for now is memory corruption :-/ That field would get overwritten with
> (int)-1 for whatever reason, maybe a wrong cast somewhere, but it's not
> as if we had many of these.

and base on this I believe that it is the case.

How can it be proved / solved?

I see a few possible options:
1. Switch off threads inside haproxy
2. Use dedicated lrandom per thread
3. Move away from lrandom

As I understand lrandom is using here because it is very fast and secure, and 
reading from /dev/urandom isn't an option.

Here I can suggest to implement Yarrow PRGN (that is very simple to implement) 
with some lua-pure cryptographic hash function.

--
wbr, Kirill



signature.asc
Description: Message signed with OpenPGP