From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.io!.POSTED.blaine.gmane.org!not-for-mail From: Bruno Haible Newsgroups: gmane.emacs.bugs,gmane.comp.lib.gnulib.bugs Subject: bug#57129: 29.0.50; Improve behavior of conditionals in Eshell Date: Sun, 21 Aug 2022 19:17:08 +0200 Message-ID: <2758072.AiC22s8V5E@nimes> References: <2271941c-3ac3-1525-4d9f-62c757641d6c@cs.ucla.edu> <1903912.fIoEIV5pvu@nimes> Mime-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Info: ciao.gmane.io; posting-host="blaine.gmane.org:116.202.254.214"; logging-data="16349"; mail-complaints-to="usenet@ciao.gmane.io" Cc: jporterbugs@gmail.com, Eli Zaretskii , bug-gnulib@gnu.org, larsi@gnus.org, 57129@debbugs.gnu.org To: Paul Eggert Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Sun Aug 21 19:18:45 2022 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane-mx.org Original-Received: from lists.gnu.org ([209.51.188.17]) by ciao.gmane.io with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oPoaz-00045B-3e for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 21 Aug 2022 19:18:45 +0200 Original-Received: from localhost ([::1]:51912 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1oPoay-0002Br-6h for geb-bug-gnu-emacs@m.gmane-mx.org; Sun, 21 Aug 2022 13:18:44 -0400 Original-Received: from eggs.gnu.org ([2001:470:142:3::10]:49666) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1oPoaK-0002B6-VM for bug-gnu-emacs@gnu.org; Sun, 21 Aug 2022 13:18:05 -0400 Original-Received: from debbugs.gnu.org ([209.51.188.43]:46919) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1oPoaI-0000aG-Al for bug-gnu-emacs@gnu.org; Sun, 21 Aug 2022 13:18:03 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1oPoaH-00072D-Pe for bug-gnu-emacs@gnu.org; Sun, 21 Aug 2022 13:18:01 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Bruno Haible Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Sun, 21 Aug 2022 17:18:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 57129 X-GNU-PR-Package: emacs Original-Received: via spool by 57129-submit@debbugs.gnu.org id=B57129.166110223726978 (code B ref 57129); Sun, 21 Aug 2022 17:18:01 +0000 Original-Received: (at 57129) by debbugs.gnu.org; 21 Aug 2022 17:17:17 +0000 Original-Received: from localhost ([127.0.0.1]:36668 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oPoZY-000714-G4 for submit@debbugs.gnu.org; Sun, 21 Aug 2022 13:17:17 -0400 Original-Received: from mo4-p01-ob.smtp.rzone.de ([81.169.146.164]:42339) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1oPoZU-00070r-SO for 57129@debbugs.gnu.org; Sun, 21 Aug 2022 13:17:15 -0400 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; t=1661102229; s=strato-dkim-0002; d=clisp.org; h=References:In-Reply-To:Message-ID:Date:Subject:Cc:To:From:Cc:Date: From:Subject:Sender; bh=7p2fJ2joyK+HzmmjqJSERB4SqXIT3T2Rfv04xhYyfoE=; b=mWpuOYLTuT9d5BvuP+zHcWpeR9v+O4Pe5Iy1cvobRIfrng3mMzr5X9FPPjWrpKY5Du Y0Uv9bMHBQVuWRZZivpKZ3xJOUuuyIz0bwXUZw6f13kX95Z6qKI9AW5CIZ2tGRpnRq+Q 4yyiKvBhFjJneZ0ZNTHxRoirr4z827GJZIIOB+7gWkpyxE6Ssc7WLHtiiXslS3aWAnWg 3Ce6z2XsWCmV5dluwMqOqUuVCnkZi9NSpqOQhjXmIGxgJt0TPkd+xo1cs+eda6kZsYtt uCDMFEXBPycK63+E57b6JR5D2kES/S15ZbpYG1BngP7vfm8oZpjjBUpmLqkPs74ovrJR O51g== Authentication-Results: strato.com; dkim=none X-RZG-AUTH: ":Ln4Re0+Ic/6oZXR1YgKryK8brlshOcZlIWs+iCP5vnk6shH0WWb0LN8XZoH94zG6tLj91pDF2uL3XvxqkO7mdhiJBa+hRD1V" X-RZG-CLASS-ID: mo00 Original-Received: from nimes.localnet by smtp.strato.de (RZmta 47.47.0 AUTH) with ESMTPSA id g97246y7LHH8P9Q (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256 bits)) (Client did not present a certificate); Sun, 21 Aug 2022 19:17:08 +0200 (CEST) In-Reply-To: <1903912.fIoEIV5pvu@nimes> X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane-mx.org@gnu.org Original-Sender: "bug-gnu-emacs" Xref: news.gmane.io gmane.emacs.bugs:240343 gmane.comp.lib.gnulib.bugs:46163 Archived-At: Paul Eggert asked: > > Could you investigate further why mingw 64-bit fails? Some words on the "why". You seem to have expectations regarding the distribution quality of the resulting file names, but these expectations are not warranted. Donald E. Knuth wrote in TAOCP vol 2 "Seminumerical algorithms" that an arbitrary sequence of number manipulating operations usually has a bad quality as a pseudo-random number generator, and that in order to get good quality pseudo-random numbers, one needs to use *specific* pseudo-random number generators and then *prove* mathematical properties of it. (The same is true, btw, for crypto algorithms.) Then he started discussing linear congruential generators [1] as the simplest example for which something could be proved. The current source code of tempname.c generates the pseudo-random numbers =E2=80=94 assuming no HAS_CLOCK_ENTROPY and no ASLR =E2=80=94 using a mix o= f three operations: (A) A linear congruential generator [2] with m =3D 2^64, a =3D 2862933555777941757, c =3D 3037000493. (B) A floor operation: v =E2=86=90 floor(v / 62^6) (C) A xor operation: v ^=3D prev_v There are three different questions: (Q1) What is the expected quality inside a single gen_tempname call? (Q2) What is the expected quality of multiple gen_tempname calls in a single process? (Q3) What is the expected quality when considering different processes that call gen_tempname? Answers: (Q1) For just 6 'X'es, there is essentially a single (A) operation. Therefore the quality will be good. If someone uses more than 10 'X'es, for example, 50 'X'es, there will be 5 (A) and 5 (B), interleaved: (A), (B), (A), (B), ... This is *not* a linear congruential generator, therefore the expected quality is BAD. In order to fix this case, what I would do is to get back to a linear congruential generator: (A), (A), ..., (A), (B). In other words, feed into (A) exactly the output from the previous (A). This means, do the statements XXXXXX[i] =3D letters[v % 62]; v /=3D 62; not on v itself, but on a copy of v. But wait, there is also the desire to have predictability! This means to not consume all the possible bits the random_bits() call, but only part of it. What I would do here, is to reduce BASE_62_DIGITS from 10 to 6. So that in each round of the loop, 6 base-62 digits are consumed and more than 4 base-62 digits are left in v, for predictability. In the usual calls with 6 'X'es the loop will still end after a single round. (Q2) First of all, the multiple gen_tempname calls can occur in different threads. Since no locking is involved, it is undefined behaviour to access the 'prev_v' variable from different threads. On machines with an IA-64 CPU, the 'prev_v' variable's value may not be propagated from one thread to the other. [3][4][5] The fix is simple, though: Mark 'prev_v' as 'volatile'. Then, what the code does, is a mix of (A), (B), (C). Again, this is *not* a linear congruential generator, therefore the expected quality is BAD. To get good quality, I would suggest to use a linear congruential generator across *all* gen_tempname calls of the entire thread. This means: - Move out the (B) invocations out, like explained above in (Q1). - Remove the (C) code that you added last week. - Store the v value in a per-thread variable. Using '__thread' on glibc systems and a TLS variable (#include "glthread/tls.h") on the other platforms. (Q3) Here, to force differences between different processes, I would suggest to use a fine-grained clock value. In terms of platforms, #if defined CLOCK_MONOTONIC && HAVE_CLOCK_GETTIME is way too restrictive. How about - using CLOCK_REALTIME when CLOCK_MONOTONIC is not available, - using gettimeofday() as fallback, especially on native Windows. If one does (Q3), then the suggestions for (Q2) (other than the 'volatile') may not be needed. Bruno [1] https://en.wikipedia.org/wiki/Linear_congruential_generator [2] https://en.wikipedia.org/wiki/Linear_congruential_generator#c_%E2%89%A0= _0 [3] https://es.cs.uni-kl.de/publications/datarsg/Geor16.pdf [4] https://db.in.tum.de/teaching/ws1718/dataprocessing/chapter3.pdf?lang= =3Dde page 18 [5] https://os.inf.tu-dresden.de/Studium/DOS/SS2014/04-Memory-Consistency.p= df