Re: [PATCH v3 1/2] compat: add a mkstemps() compatibility function

[Antriksh Pany <antriksh.pany@gmail.com>]

Hi David

I think I see a few minor issues with the code dealing with random six
letters generation. Please correct me if I am wrong.

On Thu, May 28, 2009 at 3:13 PM, David Aguilar <davvid@gmail.com> wrote:
> mkstemps() is a BSD extension so provide an implementation
> for cross-platform use.
>
> Signed-off-by: David Aguilar <davvid@gmail.com>
> Tested-by: Johannes Sixt <j6t@kdbg.org> (Windows)
> ---
>  Makefile          |   19 +++++++++++++++
>  compat/mkstemps.c |   67 +++++++++++++++++++++++++++++++++++++++++++++++++++++
>  config.mak.in     |    1 +
>  configure.ac      |    6 ++++
>  git-compat-util.h |    5 ++++
>  5 files changed, 98 insertions(+), 0 deletions(-)
>  create mode 100644 compat/mkstemps.c
>
> diff --git a/Makefile b/Makefile
> index eaae45d..a70b5f0 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -52,6 +52,8 @@ all::
>  #
>  # Define NO_MKDTEMP if you don't have mkdtemp in the C library.
>  #
> +# Define NO_MKSTEMPS if you don't have mkstemps in the C library.
> +#
>  # Define NO_SYS_SELECT_H if you don't have sys/select.h.
>  #
>  # Define NO_SYMLINK_HEAD if you never want .git/HEAD to be a symbolic link.
> @@ -636,10 +638,12 @@ EXTLIBS =
>
>  ifeq ($(uname_S),Linux)
>        NO_STRLCPY = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        THREADED_DELTA_SEARCH = YesPlease
>  endif
>  ifeq ($(uname_S),GNU/kFreeBSD)
>        NO_STRLCPY = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        THREADED_DELTA_SEARCH = YesPlease
>  endif
>  ifeq ($(uname_S),UnixWare)
> @@ -651,6 +655,7 @@ ifeq ($(uname_S),UnixWare)
>        SHELL_PATH = /usr/local/bin/bash
>        NO_IPV6 = YesPlease
>        NO_HSTRERROR = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        BASIC_CFLAGS += -Kthread
>        BASIC_CFLAGS += -I/usr/local/include
>        BASIC_LDFLAGS += -L/usr/local/lib
> @@ -674,6 +679,7 @@ ifeq ($(uname_S),SCO_SV)
>        SHELL_PATH = /usr/bin/bash
>        NO_IPV6 = YesPlease
>        NO_HSTRERROR = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        BASIC_CFLAGS += -I/usr/local/include
>        BASIC_LDFLAGS += -L/usr/local/lib
>        NO_STRCASESTR = YesPlease
> @@ -702,6 +708,7 @@ ifeq ($(uname_S),SunOS)
>        NO_MEMMEM = YesPlease
>        NO_HSTRERROR = YesPlease
>        NO_MKDTEMP = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        OLD_ICONV = UnfortunatelyYes
>        ifeq ($(uname_R),5.8)
>                NO_UNSETENV = YesPlease
> @@ -724,6 +731,7 @@ ifeq ($(uname_O),Cygwin)
>        NO_D_INO_IN_DIRENT = YesPlease
>        NO_STRCASESTR = YesPlease
>        NO_MEMMEM = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        NO_SYMLINK_HEAD = YesPlease
>        NEEDS_LIBICONV = YesPlease
>        NO_FAST_WORKING_DIRECTORY = UnfortunatelyYes
> @@ -767,11 +775,13 @@ ifeq ($(uname_S),NetBSD)
>        BASIC_LDFLAGS += -L/usr/pkg/lib $(CC_LD_DYNPATH)/usr/pkg/lib
>        THREADED_DELTA_SEARCH = YesPlease
>        USE_ST_TIMESPEC = YesPlease
> +       NO_MKSTEMPS = YesPlease
>  endif
>  ifeq ($(uname_S),AIX)
>        NO_STRCASESTR=YesPlease
>        NO_MEMMEM = YesPlease
>        NO_MKDTEMP = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        NO_STRLCPY = YesPlease
>        NO_NSEC = YesPlease
>        FREAD_READS_DIRECTORIES = UnfortunatelyYes
> @@ -787,12 +797,14 @@ endif
>  ifeq ($(uname_S),GNU)
>        # GNU/Hurd
>        NO_STRLCPY=YesPlease
> +       NO_MKSTEMPS = YesPlease
>  endif
>  ifeq ($(uname_S),IRIX64)
>        NO_IPV6=YesPlease
>        NO_SETENV=YesPlease
>        NO_STRCASESTR=YesPlease
>        NO_MEMMEM = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        NO_STRLCPY = YesPlease
>        NO_SOCKADDR_STORAGE=YesPlease
>        SHELL_PATH=/usr/gnu/bin/bash
> @@ -805,6 +817,7 @@ ifeq ($(uname_S),HP-UX)
>        NO_SETENV=YesPlease
>        NO_STRCASESTR=YesPlease
>        NO_MEMMEM = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        NO_STRLCPY = YesPlease
>        NO_MKDTEMP = YesPlease
>        NO_UNSETENV = YesPlease
> @@ -834,6 +847,7 @@ ifneq (,$(findstring MINGW,$(uname_S)))
>        NO_C99_FORMAT = YesPlease
>        NO_STRTOUMAX = YesPlease
>        NO_MKDTEMP = YesPlease
> +       NO_MKSTEMPS = YesPlease
>        SNPRINTF_RETURNS_BOGUS = YesPlease
>        NO_SVN_TESTS = YesPlease
>        NO_PERL_MAKEMAKER = YesPlease
> @@ -853,6 +867,7 @@ ifneq (,$(findstring MINGW,$(uname_S)))
>  endif
>  ifneq (,$(findstring arm,$(uname_M)))
>        ARM_SHA1 = YesPlease
> +       NO_MKSTEMPS = YesPlease
>  endif
>
>  -include config.mak.autogen
> @@ -1011,6 +1026,10 @@ ifdef NO_MKDTEMP
>        COMPAT_CFLAGS += -DNO_MKDTEMP
>        COMPAT_OBJS += compat/mkdtemp.o
>  endif
> +ifdef NO_MKSTEMPS
> +       COMPAT_CFLAGS += -DNO_MKSTEMPS
> +       COMPAT_OBJS += compat/mkstemps.o
> +endif
>  ifdef NO_UNSETENV
>        COMPAT_CFLAGS += -DNO_UNSETENV
>        COMPAT_OBJS += compat/unsetenv.o
> diff --git a/compat/mkstemps.c b/compat/mkstemps.c
> new file mode 100644
> index 0000000..87ebc2a
> --- /dev/null
> +++ b/compat/mkstemps.c
> @@ -0,0 +1,67 @@
> +#include "../git-compat-util.h"
> +
> +#ifndef TMP_MAX
> +#define TMP_MAX 16384
> +#endif
> +
> +/* Adapted from libiberty's mkstemp.c. */
> +int gitmkstemps(char *pattern, int suffix_len)
> +{
> +       static const char letters[] =
> +               "abcdefghijklmnopqrstuvwxyz"
> +               "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
> +               "0123456789";
> +       static const int num_letters = 62;
> +       uint64_t value;
> +       struct timeval tv;
> +       char *template;
> +       size_t len;
> +       int fd, count;
> +
> +       len = strlen(pattern);
> +
> +       if (len < 6 + suffix_len) {
> +               errno = EINVAL;
> +               return -1;
> +       }
> +
> +       if (strncmp(&pattern[len - 6 - suffix_len], "XXXXXX", 6)) {
> +               errno = EINVAL;
> +               return -1;
> +       }
> +
> +       /* Replace pattern's XXXXXX characters with randomness.
> +        * Try TMP_MAX different filenames.
> +        */
> +       gettimeofday(&tv, NULL);
> +       value = ((size_t)(tv.tv_usec << 16)) ^ tv.tv_sec ^ getpid();
> +       template = &pattern[len - 6 - suffix_len];
> +       for (count = 0; count < TMP_MAX; ++count) {
> +               uint64_t v = value;
> +               /* Fill in the random bits. */
> +               template[0] = letters[v % num_letters]; v/= num_letters;
> +               template[1] = letters[v % num_letters]; v/= num_letters;
> +               template[2] = letters[v % num_letters]; v/= num_letters;
> +               template[3] = letters[v % num_letters]; v/= num_letters;
> +               template[4] = letters[v % num_letters]; v/= num_letters;
> +               template[5] = letters[v % num_letters]; v/= num_letters;

v is divided 6 times by 62, and a decent amount of randomness shall be
ensured only if 'value' is usually greater than 62^6.

If it is assumed to be ok for 'v' to become zero in the last one odd
steps sometimes (in fact, _frequently_), then you may ignore what I am
pointing out here.

1. On a couple of systems that I checked on, all variables/types on
the right hand side of
      value = ((size_t)(tv.tv_usec << 16)) ^ tv.tv_sec ^ getpid();
are 4 bytes long. So 'value' is ultimately going to be assigned a
number that fits in 4 bytes, ie value < 2^32 (at least on a few
systems).
The systems that I checked on have these `uname -a` outputs:
-   Linux host 2.6.9-55.ELsmp #1 SMP Fri Apr 20 17:03:35 EDT 2007 i686
i686 i386 GNU/Linux
-   Linux host 2.4.21-50.ELsmp #1 SMP Tue May 8 17:18:29 EDT 2007 i686
i686 i386 GNU/Linux

Also, even if size_t were 64 bits, typecasting _after_ the shift does
not help much. And given the uncertainty about sizeof (size_t), we
could use:
  ((uint64_t) tv.tv_usec) << 16)


2. tv_usec has a decimal value range of 0-999999  (10^6 usec make 1
sec). Which means that tv_usec fits completely in 20 bits (or less).
(tv_usec << 16) yields a number that fits completely in 36 bits (or
less). Max value of this number is 999999 * 2^16, or for convenience,
about M = 10^6 * 2^16. This number (in the range of 0 to M) goes on to
be divided by D=62^6. Also, M > D. Thus, there is about a  D / M * 100
~ 87 % probability of the division M / D working out to be zero. i.e,
in 87% cases, the last division (v/= num_letters) will cause 'v' to
become 0.
Therefore, I think an additional shift of 7 or more bits will help in
improving randomness of template[5]. I would suggest left shifting by
24 bits. This seemed ok in some tests I did.


Combining #1 and #2, I guess we could have the computation of 'value' as:
      value = (((uint64_t)tv.tv_usec) << 24) ^ tv.tv_sec ^ getpid();


- Antriksh