backupfile.c rewrite to avoid arbitrary limits on lengths of

numeric backup extensions.

Include "backupfile.h" first.
Include errno.h, stdbool.h, limits.h, unistd.h, xalloc.h.
(CLOSEDIR, INT_STRLEN_BOUND): Remove.
(pathconf) [! (HAVE_PATHCONF && defined _PC_NAME_MAX)]: New macro.
(_POSIX_NAME_MAX) [!defined _POSIX_NAME_MAX]: New macro.
(NAME_MAX_MAXIMUM): New macro.  Unlike the old addext.c, we
also look at _XOPEN_NAME_MAX, for better performance on modern
hosts that support only file names of length 255 or more.
(ISDIGIT): unsigned -> unsigned int
(max_backup_version, version_number): Remove.
(check_extension): New function.  Similar to the old addext, but
static, assumes that the extension has already been added,
and a bit more careful on DOS hosts.
(numbered_backup): New function.  It does what max_backup_version
and version_number used to do, but it doesn't use integer arithmetic
to calculate extensions so it doesn't overflow.
(find_backup_file_name): Rewrite to use these new functions.
This has a new optimization: we needn't call pathconf if the
new numbered backup name has the same length as the old.
Also, use xmalloc rather than malloc, so that the caller
needn't worry about memory exhaustion.

1 files changed, 243 insertions, 115 deletions

diff --git a/lib/backupfile.c b/lib/backupfile.c
index 34d83357f..fe535db21 100644
--- a/lib/backupfile.c
+++ b/lib/backupfile.c
@@ -18,17 +18,30 @@
    If not, write to the Free Software Foundation,
    59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 
-/* Written by David MacKenzie <djm@gnu.ai.mit.edu>.
-   Some algorithms adapted from GNU Emacs. */
+/* Written by Paul Eggert and David MacKenzie.
+   Some algorithms adapted from GNU Emacs.  */
 
 #if HAVE_CONFIG_H
 # include <config.h>
 #endif
 
-#include <stddef.h>
-#include <stdio.h>
+#include "backupfile.h"
+
+#include "argmatch.h"
+#include "dirname.h"
+#include "xalloc.h"
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdlib.h>
 #include <string.h>
 
+#include <limits.h>
+
+#if HAVE_UNISTD_H
+# include <unistd.h>
+#endif
+
 #if HAVE_DIRENT_H
 # include <dirent.h>
 # define NLENGTH(direct) strlen ((direct)->d_name)
@@ -46,27 +59,41 @@
 # endif
 #endif
 
-#if CLOSEDIR_VOID
-/* Fake a return value. */
-# define CLOSEDIR(d) (closedir (d), 0)
-#else
-# define CLOSEDIR(d) closedir (d)
-#endif
-
-#include <stdlib.h>
-
 #if HAVE_DIRENT_H || HAVE_NDIR_H || HAVE_SYS_DIR_H || HAVE_SYS_NDIR_H
 # define HAVE_DIR 1
 #else
 # define HAVE_DIR 0
 #endif
 
-#include <limits.h>
+#if D_INO_IN_DIRENT
+# define REAL_DIR_ENTRY(dp) ((dp)->d_ino != 0)
+#else
+# define REAL_DIR_ENTRY(dp) 1
+#endif
+
+#if ! (HAVE_PATHCONF && defined _PC_NAME_MAX)
+# define pathconf(file, option) (errno = -1)
+#endif
+
+#ifndef _POSIX_NAME_MAX
+# define _POSIX_NAME_MAX 14
+#endif
+#ifndef SIZE_MAX
+# define SIZE_MAX ((size_t) -1)
+#endif
 
-/* Upper bound on the string length of an integer converted to string.
-   302 / 1000 is ceil (log10 (2.0)).  Subtract 1 for the sign bit;
-   add 1 for integer division truncation; add 1 more for a minus sign.  */
-#define INT_STRLEN_BOUND(t) ((sizeof (t) * CHAR_BIT - 1) * 302 / 1000 + 2)
+#if defined _XOPEN_NAME_MAX
+# define NAME_MAX_MINIMUM _XOPEN_NAME_MAX
+#else
+# define NAME_MAX_MINIMUM _POSIX_NAME_MAX
+#endif
+
+#ifndef HAVE_DOS_FILE_NAMES
+# define HAVE_DOS_FILE_NAMES 0
+#endif
+#ifndef HAVE_LONG_FILE_NAMES
+# define HAVE_LONG_FILE_NAMES 0
+#endif
 
 /* ISDIGIT differs from isdigit, as follows:
    - Its arg may be any int or unsigned int; it need not be an unsigned char.
@@ -75,136 +102,237 @@
    POSIX says that only '0' through '9' are digits.  Prefer ISDIGIT to
    ISDIGIT_LOCALE unless it's important to use the locale's definition
    of `digit' even when the host does not conform to POSIX.  */
-#define ISDIGIT(c) ((unsigned) (c) - '0' <= 9)
-
-#if D_INO_IN_DIRENT
-# define REAL_DIR_ENTRY(dp) ((dp)->d_ino != 0)
-#else
-# define REAL_DIR_ENTRY(dp) 1
-#endif
-
-#include "argmatch.h"
-#include "backupfile.h"
-#include "dirname.h"
+#define ISDIGIT(c) ((unsigned int) (c) - '0' <= 9)
 
 /* The extension added to file names to produce a simple (as opposed
    to numbered) backup file name. */
-const char *simple_backup_suffix = "~";
+char const *simple_backup_suffix = "~";
 
-static int max_backup_version (const char *, const char *);
-static int version_number (const char *, const char *, size_t);
 
-/* Return the name of the new backup file for file FILE,
-   allocated with malloc.  Return 0 if out of memory.
-   FILE must not end with a '/' unless it is the root directory.
-   Do not call this function if backup_type == none. */
+/* If FILENAME (which was of length FILELEN before an extension was
+   appended to it) is too long, replace the extension with the single
+   char E.  If the result is still too long, remove the char just
+   before E.  */
 
-char *
-find_backup_file_name (const char *file, enum backup_type backup_type)
+static void
+check_extension (char *filename, size_t filelen, char e)
 {
-  size_t backup_suffix_size_max;
-  size_t file_len = strlen (file);
-  size_t numbered_suffix_size_max = INT_STRLEN_BOUND (int) + 4;
-  char *s;
-  const char *suffix = simple_backup_suffix;
+  char *basename = base_name (filename);
+  size_t baselen = base_len (basename);
+  size_t baselen_max = HAVE_LONG_FILE_NAMES ? 255 : NAME_MAX_MINIMUM;
 
-  /* Allow room for simple or `.~N~' backups.  */
-  backup_suffix_size_max = strlen (simple_backup_suffix) + 1;
-  if (HAVE_DIR && backup_suffix_size_max < numbered_suffix_size_max)
-    backup_suffix_size_max = numbered_suffix_size_max;
+  if (HAVE_DOS_FILE_NAMES || NAME_MAX_MINIMUM < baselen)
+    {
+      /* The new base name is long enough to require a pathconf check.  */
+      long name_max;
+
+      /* Temporarily modify the buffer into its parent directory name,
+	 invoke pathconf on the directory, and then restore the buffer.  */
+      char tmp[sizeof "."];
+      memcpy (tmp, basename, sizeof ".");
+      strcpy (basename, ".");
+      errno = 0;
+      name_max = pathconf (filename, _PC_NAME_MAX);
+      if (0 <= name_max || errno == 0)
+	{
+	  long size = baselen_max = name_max;
+	  if (name_max != size)
+	    baselen_max = SIZE_MAX;
+	}
+      memcpy (basename, tmp, sizeof ".");
+    }
 
-  s = malloc (file_len + 1
-	      + backup_suffix_size_max + numbered_suffix_size_max);
-  if (s)
+  if (HAVE_DOS_FILE_NAMES && baselen_max <= 12)
     {
-#if HAVE_DIR
-      if (backup_type != simple)
+      /* Live within DOS's 8.3 limit.  */
+      char *dot = strchr (basename, '.');
+      if (!dot)
+	baselen_max = 8;
+      else
 	{
-	  int highest_backup;
-	  size_t dirlen = dir_len (file);
-
-	  memcpy (s, file, dirlen);
-	  if (dirlen == FILE_SYSTEM_PREFIX_LEN (file))
-	    s[dirlen++] = '.';
-	  s[dirlen] = '\0';
-	  highest_backup = max_backup_version (base_name (file), s);
-	  if (! (backup_type == numbered_existing && highest_backup == 0))
-	    {
-	      char *numbered_suffix = s + (file_len + backup_suffix_size_max);
-	      sprintf (numbered_suffix, ".~%d~", highest_backup + 1);
-	      suffix = numbered_suffix;
-	    }
+	  char const *second_dot = strchr (dot + 1, '.');
+	  baselen_max = (second_dot
+			 ? second_dot - basename
+			 : dot + 1 - basename + 3);
 	}
-#endif /* HAVE_DIR */
+    }
 
-      strcpy (s, file);
-      addext (s, suffix, '~');
+  if (baselen_max < baselen)
+    {
+      baselen = filename + filelen - basename;
+      if (baselen_max <= baselen)
+	baselen = baselen_max - 1;
+      basename[baselen] = e;
+      basename[baselen + 1] = '\0';
     }
-  return s;
 }
 
 #if HAVE_DIR
 
-/* Return the number of the highest-numbered backup file for file
-   FILE in directory DIR.  If there are no numbered backups
-   of FILE in DIR, or an error occurs reading DIR, return 0.
-   */
-
-static int
-max_backup_version (const char *file, const char *dir)
+/* Returned values for NUMBERED_BACKUP.  */
+
+enum numbered_backup_result
+  {
+    /* The new backup name is the same length as an existing backup
+       name, so it's valid for that directory.  */
+    BACKUP_IS_SAME_LENGTH,
+
+    /* Some backup names already exist, but the returned name is longer
+       than any of them, and its length should be checked.  */
+    BACKUP_IS_LONGER,
+
+    /* There are no existing backup names.  The new name's length
+       should be checked.  */
+    BACKUP_IS_NEW
+  };
+
+/* *BUFFER contains a file name.  Store into *BUFFER the next backup
+   name for the named file, with a version number greater than all the
+   existing numbered backups.  Reallocate *BUFFER as necessary; its
+   initial allocated size is BUFFER_SIZE, which must be at least 4
+   bytes longer than the file name to make room for the initially
+   appended ".~1".  FILELEN is the length of the original file name.
+   The returned value indicates what kind of backup was found.  If an
+   I/O or other read error occurs, use the highest backup number that
+   was found.  */
+
+static enum numbered_backup_result
+numbered_backup (char **buffer, size_t buffer_size, size_t filelen)
 {
+  enum numbered_backup_result result = BACKUP_IS_NEW;
   DIR *dirp;
   struct dirent *dp;
-  int highest_version;
-  int this_version;
-  size_t file_name_length;
+  char *buf = *buffer;
+  size_t versionlenmax = 1;
+  char *basename = base_name (buf);
+  size_t basename_offset = basename - buf;
+  size_t baselen = base_len (basename);
+
+  /* Temporarily modify the buffer into its parent directory name,
+     open the directory, and then restore the buffer.  */
+  char tmp[sizeof "."];
+  memcpy (tmp, basename, sizeof ".");
+  strcpy (basename, ".");
+  dirp = opendir (buf);
+  memcpy (basename, tmp, sizeof ".");
+  strcpy (basename + baselen, ".~1~");
 
-  dirp = opendir (dir);
   if (!dirp)
-    return 0;
-
-  highest_version = 0;
-  file_name_length = base_len (file);
+    return result;
 
-  while ((dp = readdir (dirp)) != 0)
+  while ((dp = readdir (dirp)) != NULL)
     {
-      if (!REAL_DIR_ENTRY (dp) || NLENGTH (dp) < file_name_length + 4)
+      char const *p;
+      char *q;
+      bool all_9s;
+      size_t versionlen;
+      size_t new_buflen;
+
+      if (! REAL_DIR_ENTRY (dp) || NLENGTH (dp) < baselen + 4)
+	continue;
+
+      if (memcmp (buf + basename_offset, dp->d_name, baselen + 2) != 0)
+	continue;
+
+      p = dp->d_name + baselen + 2;
+
+      /* Check whether this file has a version number and if so,
+	 whether it is larger.  Use string operations rather than
+	 integer arithmetic, to avoid problems with integer overflow.  */
+
+      if (! ('1' <= *p && *p <= '9'))
+	continue;
+      all_9s = (*p == '9');
+      for (versionlen = 1; ISDIGIT (p[versionlen]); versionlen++)
+	all_9s &= (p[versionlen] == '9');
+
+      if (! (p[versionlen] == '~' && !p[versionlen + 1]
+	     && (versionlenmax < versionlen
+		 || (versionlenmax == versionlen
+		     && memcmp (buf + filelen + 2, p, versionlen) <= 0))))
 	continue;
 
-      this_version = version_number (file, dp->d_name, file_name_length);
-      if (this_version > highest_version)
-	highest_version = this_version;
+      /* This directory has the largest version number seen so far.
+	 Append this highest numbered extension to the file name,
+	 prepending '0' to the number if it is all 9s.  */
+
+      versionlenmax = all_9s + versionlen;
+      result = (all_9s ? BACKUP_IS_LONGER : BACKUP_IS_SAME_LENGTH);
+      new_buflen = filelen + 2 + versionlenmax + 1;
+      if (buffer_size <= new_buflen)
+	{
+	  buf = xnrealloc (buf, 2, new_buflen);
+	  buffer_size = new_buflen * 2;
+	}
+      q = buf + filelen;
+      *q++ = '.';
+      *q++ = '~';
+      *q = '0';
+      q += all_9s;
+      memcpy (q, p, versionlen + 2);
+      
+      /* Add 1 to the version number.  */
+
+      q += versionlen;
+      while (*--q == '9')
+	*q = '0';
+      ++*q;
     }
-  if (CLOSEDIR (dirp))
-    return 0;
-  return highest_version;
+
+  closedir (dirp);
+  *buffer = buf;
+  return result;
 }
+#endif /* HAVE_DIR */
 
-/* If BACKUP is a numbered backup of BASE, return its version number;
-   otherwise return 0.  BASE_LENGTH is the length of BASE.
-   */
+/* Return the name of the new backup file for the existing file FILE,
+   allocated with malloc.  Report an error and fail if out of memory.
+   Do not call this function if backup_type == none. */
 
-static int
-version_number (const char *base, const char *backup, size_t base_length)
+char *
+find_backup_file_name (char const *file, enum backup_type backup_type)
 {
-  int version;
-  const char *p;
+  size_t filelen = strlen (file);
+  char *s;
+  size_t ssize;
+  bool simple = true;
 
-  version = 0;
-  if (strncmp (base, backup, base_length) == 0
-      && backup[base_length] == '.'
-      && backup[base_length + 1] == '~')
-    {
-      for (p = &backup[base_length + 2]; ISDIGIT (*p); ++p)
-	version = version * 10 + *p - '0';
-      if (p[0] != '~' || p[1])
-	version = 0;
-    }
-  return version;
+  /* Allow room for simple or ".~N~" backups.  The guess must be at
+     least sizeof ".~1~", but otherwise will be adjusted as needed.  */
+  size_t simple_backup_suffix_size = strlen (simple_backup_suffix) + 1;
+  size_t backup_suffix_size_guess = simple_backup_suffix_size;
+  enum { GUESS = sizeof ".~12345~" };
+  if (HAVE_DIR && backup_suffix_size_guess < GUESS)
+    backup_suffix_size_guess = GUESS;
+
+  ssize = filelen + backup_suffix_size_guess + 1;
+  s = xmalloc (ssize);
+  memcpy (s, file, filelen + 1);
+
+#if HAVE_DIR
+  if (backup_type != simple)
+    switch (numbered_backup (&s, ssize, filelen))
+      {
+      case BACKUP_IS_SAME_LENGTH:
+	return s;
+
+      case BACKUP_IS_LONGER:
+	simple = false;
+	break;
+
+      case BACKUP_IS_NEW:
+	simple = (backup_type == numbered_existing);
+	break;
+      }
+#endif
+
+  if (simple)
+    memcpy (s + filelen, simple_backup_suffix, simple_backup_suffix_size);
+  check_extension (s, filelen, '~');
+  return s;
 }
-#endif /* HAVE_DIR */
 
-static const char * const backup_args[] =
+static char const * const backup_args[] =
 {
   /* In a series of synonyms, present the most meaning full first, so
      that argmatch_valid be more readable. */
@@ -229,7 +357,7 @@ static const enum backup_type backup_types[] =
    for the specified CONTEXT.  Unambiguous abbreviations are accepted.  */
 
 enum backup_type
-get_version (const char *context, const char *version)
+get_version (char const *context, char const *version)
 {
   if (version == 0 || *version == 0)
     return numbered_existing;
@@ -245,7 +373,7 @@ get_version (const char *context, const char *version)
    Unambiguous abbreviations are accepted.  */
 
 enum backup_type
-xget_version (const char *context, const char *version)
+xget_version (char const *context, char const *version)
 {
   if (version && *version)
     return get_version (context, version);