bug#8401: removing duplication and improving the readlink code

bug#8401: removing duplication and improving the readlink code

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 7913 bytes --]

In two places Emacs calls readlink with similar code to reallocate
buffers until there's enough room to store the symbolic link's value.
And in both places there are minor problems with overflow, since Emacs
uses 32-bit int where modern 64-bit systems use 64-bit ssize_t, and it
doesn't check for overflow in buffer size calculations.  These
problems cause GCC to complain, if warnings are enabled.  I plan to
fix the problems with the following patch, which substitutes a gnulib
implementation of the same basic readlink idea; this implementation
does more-careful buffer size checking, and makes it possible to
avoid the malloc+free in the usual case.

This patch adds a couple of dependencies so it may affect the
Windows build.

The full patch (including autogenerated files) is attached as
a compressed file.

=== modified file 'ChangeLog'
--- ChangeLog	2011-03-28 01:03:57 +0000
+++ ChangeLog	2011-04-01 06:28:48 +0000
@@ -1,3 +1,10 @@
+2011-04-01  Paul Eggert  <eggert@cs.ucla.edu>
+
+	Replace two copies of readlink code with single gnulib version.
+	* Makefile.in (GNULIB_MODULES): Add careadlinkat.
+	* lib/allocator.h, lib/careadlinkat.c, lib/careadlinkat.h:
+	* m4/ssize_t.m4: New files, automatically generated from gnulib.
+
 2011-03-28  Glenn Morris  <rgm@gnu.org>
 
 	* autogen/update_autogen: Pass -f to autoreconf.

=== modified file 'Makefile.in'
--- Makefile.in	2011-03-25 07:14:31 +0000
+++ Makefile.in	2011-04-01 06:28:48 +0000
@@ -331,7 +331,7 @@
 # $(gnulib_srcdir) (relative to $(srcdir) and should have build tools
 # as per $(gnulib_srcdir)/DEPENDENCIES.
 GNULIB_MODULES = \
-  crypto/md5 dtoastr filemode getloadavg getopt-gnu \
+  careadlinkat crypto/md5 dtoastr filemode getloadavg getopt-gnu \
   ignore-value intprops lstat mktime readlink \
   socklen stdio strftime symlink sys_stat
 GNULIB_TOOL_FLAGS = \

=== modified file 'src/ChangeLog'
--- src/ChangeLog	2011-03-31 19:42:38 +0000
+++ src/ChangeLog	2011-04-01 06:38:52 +0000
@@ -1,3 +1,17 @@
+2011-04-01  Paul Eggert  <eggert@cs.ucla.edu>
+
+	Replace two copies of readlink code with single gnulib version.
+	The gnulib version avoids calling malloc in the usual case,
+	and on 64-bit hosts doesn't have some arbitrary 32-bit limits.
+	* fileio.c (Ffile_symlink_p): Use emacs_readlink.
+	* filelock.c (current_lock_owner): Likewise.
+	* lisp.h (READLINK_BUFSIZE, emacs_readlink): New function.
+	* sysdep.c: Include allocator.h, careadlinkat.h.
+	(emacs_no_realloc_allocator): New static constant.
+	(emacs_readlink): New function.
+	* deps.mk (sysdep.o): Depend on ../lib/allocator.h and on
+	../lib/careadlinkat.h.
+
 2011-03-31  Juanma Barranquero  <lekktu@gmail.com>
 
 	* xdisp.c (redisplay_internal): Fix prototype.

=== modified file 'src/deps.mk'
--- src/deps.mk	2011-03-19 22:46:50 +0000
+++ src/deps.mk	2011-04-01 06:38:52 +0000
@@ -187,6 +187,7 @@
    process.h dispextern.h termhooks.h termchar.h termopts.h coding.h \
    frame.h atimer.h window.h msdos.h dosfns.h keyboard.h cm.h lisp.h \
    globals.h $(config_h) composite.h sysselect.h gnutls.h \
+   ../lib/allocator.h ../lib/careadlinkat.h \
    ../lib/unistd.h ../lib/ignore-value.h
 term.o: term.c termchar.h termhooks.h termopts.h lisp.h globals.h $(config_h) \
    cm.h frame.h disptab.h keyboard.h character.h charset.h coding.h ccl.h \

=== modified file 'src/fileio.c'
--- src/fileio.c	2011-03-25 17:37:15 +0000
+++ src/fileio.c	2011-04-01 06:28:48 +0000
@@ -2579,9 +2579,8 @@
 {
   Lisp_Object handler;
   char *buf;
-  int bufsize;
-  int valsize;
   Lisp_Object val;
+  char readlink_buf[READLINK_BUFSIZE];
 
   CHECK_STRING (filename);
   filename = Fexpand_file_name (filename, Qnil);
@@ -2594,36 +2593,15 @@
 
   filename = ENCODE_FILE (filename);
 
-  bufsize = 50;
-  buf = NULL;
-  do
-    {
-      bufsize *= 2;
-      buf = (char *) xrealloc (buf, bufsize);
-      memset (buf, 0, bufsize);
-
-      errno = 0;
-      valsize = readlink (SSDATA (filename), buf, bufsize);
-      if (valsize == -1)
-	{
-#ifdef ERANGE
-	  /* HP-UX reports ERANGE if buffer is too small.  */
-	  if (errno == ERANGE)
-	    valsize = bufsize;
-	  else
-#endif
-	    {
-	      xfree (buf);
-	      return Qnil;
-	    }
-	}
-    }
-  while (valsize >= bufsize);
-
-  val = make_string (buf, valsize);
+  buf = emacs_readlink (SSDATA (filename), readlink_buf);
+  if (! buf)
+    return Qnil;
+
+  val = build_string (buf);
   if (buf[0] == '/' && strchr (buf, ':'))
     val = concat2 (build_string ("/:"), val);
-  xfree (buf);
+  if (buf != readlink_buf)
+    xfree (buf);
   val = DECODE_FILE (val);
   return val;
 }

=== modified file 'src/filelock.c'
--- src/filelock.c	2011-03-15 01:19:50 +0000
+++ src/filelock.c	2011-04-01 06:28:48 +0000
@@ -396,36 +396,16 @@
 static int
 current_lock_owner (lock_info_type *owner, char *lfname)
 {
-  int len, ret;
+  int ret;
+  size_t len;
   int local_owner = 0;
   char *at, *dot, *colon;
-  char *lfinfo = 0;
-  int bufsize = 50;
-  /* Read arbitrarily-long contents of symlink.  Similar code in
-     file-symlink-p in fileio.c.  */
-  do
-    {
-      bufsize *= 2;
-      lfinfo = (char *) xrealloc (lfinfo, bufsize);
-      errno = 0;
-      len = readlink (lfname, lfinfo, bufsize);
-#ifdef ERANGE
-      /* HP-UX reports ERANGE if the buffer is too small.  */
-      if (len == -1 && errno == ERANGE)
-	len = bufsize;
-#endif
-    }
-  while (len >= bufsize);
+  char readlink_buf[READLINK_BUFSIZE];
+  char *lfinfo = emacs_readlink (lfname, readlink_buf);
 
   /* If nonexistent lock file, all is well; otherwise, got strange error. */
-  if (len == -1)
-    {
-      xfree (lfinfo);
-      return errno == ENOENT ? 0 : -1;
-    }
-
-  /* Link info exists, so `len' is its length.  Null terminate.  */
-  lfinfo[len] = 0;
+  if (!lfinfo)
+    return errno == ENOENT ? 0 : -1;
 
   /* Even if the caller doesn't want the owner info, we still have to
      read it to determine return value, so allocate it.  */
@@ -441,7 +421,8 @@
   dot = strrchr (lfinfo, '.');
   if (!at || !dot)
     {
-      xfree (lfinfo);
+      if (lfinfo != readlink_buf)
+	xfree (lfinfo);
       return -1;
     }
   len = at - lfinfo;
@@ -467,7 +448,8 @@
   owner->host[len] = 0;
 
   /* We're done looking at the link info.  */
-  xfree (lfinfo);
+  if (lfinfo != readlink_buf)
+    xfree (lfinfo);
 
   /* On current host?  */
   if (STRINGP (Fsystem_name ())

=== modified file 'src/lisp.h'
--- src/lisp.h	2011-03-29 23:35:49 +0000
+++ src/lisp.h	2011-04-01 06:28:48 +0000
@@ -3340,6 +3340,8 @@
 extern int emacs_close (int);
 extern int emacs_read (int, char *, unsigned int);
 extern int emacs_write (int, const char *, unsigned int);
+enum { READLINK_BUFSIZE = 1024 };
+extern char *emacs_readlink (const char *, char [READLINK_BUFSIZE]);
 #ifndef HAVE_MEMSET
 extern void *memset (void *, int, size_t);
 #endif

=== modified file 'src/sysdep.c'
--- src/sysdep.c	2011-03-27 02:27:11 +0000
+++ src/sysdep.c	2011-04-01 06:28:48 +0000
@@ -31,6 +31,8 @@
 #endif /* HAVE_LIMITS_H */
 #include <unistd.h>
 
+#include <allocator.h>
+#include <careadlinkat.h>
 #include <ignore-value.h>
 
 #include "lisp.h"
@@ -1866,6 +1868,22 @@
     }
   return (bytes_written);
 }
+
+static struct allocator const emacs_norealloc_allocator =
+  { xmalloc, NULL, xfree, memory_full };
+
+/* Get the symbolic link value of FILENAME.  Return a pointer to a
+   NUL-terminated string.  If readlink fails, return NULL and set
+   errno.  If the value fits in INITIAL_BUF, return INITIAL_BUF.
+   Otherwise, allocate memory and return a pointer to that memory.  If
+   memory allocation fails, diagnose and fail without returning.  If
+   successful, store the length of the symbolic link into *LINKLEN.  */
+char *
+emacs_readlink (char const *filename, char initial_buf[READLINK_BUFSIZE])
+{
+  return careadlinkat (AT_FDCWD, filename, initial_buf, READLINK_BUFSIZE,
+		       &emacs_norealloc_allocator, careadlinkatcwd);
+}
 \f
 #ifdef USG
 /*


[-- Attachment #2: patch.txt.gz --]
[-- Type: application/x-gzip, Size: 6330 bytes --]

bug#8401: removing duplication and improving the readlink code

[Eli Zaretskii]

> Date: Thu, 31 Mar 2011 23:47:14 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> CC: Eli Zaretskii <eliz@gnu.org>
> 
> In two places Emacs calls readlink with similar code to reallocate
> buffers until there's enough room to store the symbolic link's value.
> And in both places there are minor problems with overflow, since Emacs
> uses 32-bit int where modern 64-bit systems use 64-bit ssize_t, and it
> doesn't check for overflow in buffer size calculations.  These
> problems cause GCC to complain, if warnings are enabled.  I plan to
> fix the problems with the following patch, which substitutes a gnulib
> implementation of the same basic readlink idea; this implementation
> does more-careful buffer size checking, and makes it possible to
> avoid the malloc+free in the usual case.

Isn't much easier and much more elegant to use ssize_t instead of an
int for the buffer sizes in both cases?

> This patch adds a couple of dependencies so it may affect the
> Windows build.

If this patch is accepted, the new emacs_readlink function will be a
trivial "fail" stub on Windows.  I don't see a need to compile in all
this gnulib code just to return NULL because readlink always fails.

bug#8401: removing duplication and improving the readlink code

[Paul Eggert]

On 04/01/2011 01:33 AM, Eli Zaretskii wrote:
> Isn't much easier and much more elegant to use ssize_t instead of an
> int for the buffer sizes in both cases?

That doesn't suffice; the code should not only use ssize_t for
readlink's returned value, but it should also use size_t for the
buffer size, and it should check that neither type overflows.

We could modify both copies of Emacs's readlink-using
code to fix these problems, but when there's duplication like
this, it's typically better to have just one copy of the code,
and make any necessary fixes in that copy.

On 04/01/2011 01:33 AM, Eli Zaretskii wrote:
> If this patch is accepted, the new emacs_readlink function will be a
> trivial "fail" stub on Windows.

That would introduce an unnecessary "#ifdef DOS_NT" into the mainline
code.  We should strive to keep the mainline code free of
porting #ifdefs when it is easy, as it is in this case.
The proposed code should run just fine on Windows, using
the already-existing stubs.  We shouldn't need to clutter up
up the mainline code with unnecessary Windows-specific
microoptimizations.

bug#8401: removing duplication and improving the readlink code

[Eli Zaretskii]

> Date: Fri, 01 Apr 2011 12:00:28 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> CC: 8401@debbugs.gnu.org
> 
> On 04/01/2011 01:33 AM, Eli Zaretskii wrote:
> > Isn't much easier and much more elegant to use ssize_t instead of an
> > int for the buffer sizes in both cases?
> 
> That doesn't suffice; the code should not only use ssize_t for
> readlink's returned value, but it should also use size_t for the
> buffer size

Well, let's use that as well, then.

> and it should check that neither type overflows.

Are we really going to consider seriously the case of a link name
overflowing a 64-bit ssize_t data type?  On what platform can this
happen?  I could perhaps be sympathetic to defensive programming in
this area if it were a simple enough test.  But why do we need to
introduce the allocator and careadlinkat modules, and all the nested
function calls needed for them, just to protect a simple code fragment
from overflowing?

> We could modify both copies of Emacs's readlink-using
> code to fix these problems, but when there's duplication like
> this, it's typically better to have just one copy of the code,
> and make any necessary fixes in that copy.

We could refactor the duplicated code into a short function, and use
that.

> On 04/01/2011 01:33 AM, Eli Zaretskii wrote:
> > If this patch is accepted, the new emacs_readlink function will be a
> > trivial "fail" stub on Windows.
> 
> That would introduce an unnecessary "#ifdef DOS_NT" into the mainline
> code.  We should strive to keep the mainline code free of
> porting #ifdefs when it is easy, as it is in this case.
> The proposed code should run just fine on Windows, using
> the already-existing stubs.  We shouldn't need to clutter up
> up the mainline code with unnecessary Windows-specific
> microoptimizations.

I'm all for that, but if you want to help, please restructure the code
so that neither allocator.h nor careadlinkat are not used on platforms
whose readlink is an always-fail stub.

Sorry, but there are limits to what I can stand in code inelegance and
gratuitous complexity without having my stomach spilled out.  I have
no authority to reject your patch, but I _can_ leave the parts of code
I'm responsible for as unaffected by it as possible.

On top of all that, the functions you introduce use malloc/realloc,
which I think will prevent their callers from being safe for
asynchronous calls triggered by external events (mouse etc.).  The
original code used xmalloc/xrealloc instead, which have Emacs-specific
implementations to avoid that limitation.

bug#8401: removing duplication and improving the readlink code

[Paul Eggert]

On 04/01/2011 12:38 PM, Eli Zaretskii wrote:

> the functions you introduce use malloc/realloc,
> which I think will prevent their callers from being safe for
> asynchronous calls triggered by external events (mouse etc.).

No, because the functions always use Emacs xmalloc / xrealloc when
Emacs invokes them.  This is because emacs_readlink tells the
lower-level primitives to use xmalloc and xrealloc.

>> That doesn't suffice; the code should not only use ssize_t for
>> readlink's returned value, but it should also use size_t for the
>> buffer size
> 
> Well, let's use that as well, then.

What I sense that you're suggesting, is that we take all the fixes in
the gnulib code, and port them all into the two duplicates of similar
code that's in Emacs.  That would be an error-prone process and would
leave us with three copies of the code to maintain.  It's better to
have just one copy of the code.

> Are we really going to consider seriously the case of a link name
> overflowing a 64-bit ssize_t data type?

As a general rule, GNU code shouldn't have arbitrary limits, and
should defend against limits in underyling systems.  Emacs is not
as good as it should be about this, and I'm trying to make it better.
This is just one example of many, found by static checking, and we
might as well fix it while we're fixing all the others.

> But why do we need to introduce the allocator and careadlinkat
> modules, and all the nested function calls needed for them, just to
> protect a simple code fragment from overflowing?

It's more reliable to put the overflow checks in one place, where they
can be carefully checked, than to duplicate the code in multiple
places where it's easy for programmers to get it wrong.

> We could refactor the duplicated code into a short function, and use
> that.

That's what's being done here.  The function does even more than that,
though, as it avoids the need to call malloc and free entirely, in the
usual case.  This is a performance win in the typical case.

> please restructure the code so that neither allocator.h nor
> careadlinkat are not used on platforms whose readlink is an
> always-fail stub.

That's not possible to do, unless we add more "#ifdef DOS_NT"s to the
mainstream code.  But that would be undesirable.  The mainstream code
should be written for the usual case, and platforms that lack the
necessary primitives should supply their own stubs (which may always
fail, but that's OK).  That is standard porting technology, and it's
an improvement over sprinking #ifdefs throughout the mainstream code.

bug#8401: removing duplication and improving the readlink code

[Eli Zaretskii]

> Date: Fri, 01 Apr 2011 13:09:22 -0700
> From: Paul Eggert <eggert@cs.ucla.edu>
> CC: 8401@debbugs.gnu.org
> 
> On 04/01/2011 12:38 PM, Eli Zaretskii wrote:
> 
> > the functions you introduce use malloc/realloc,
> > which I think will prevent their callers from being safe for
> > asynchronous calls triggered by external events (mouse etc.).
> 
> No, because the functions always use Emacs xmalloc / xrealloc when
> Emacs invokes them.  This is because emacs_readlink tells the
> lower-level primitives to use xmalloc and xrealloc.

You are right, I stand corrected.

However, this just underlines the difficulty of reading the convoluted
arrangement that this patch introduces.  Any such difficulty is an
impediment to maintenance.

> >> That doesn't suffice; the code should not only use ssize_t for
> >> readlink's returned value, but it should also use size_t for the
> >> buffer size
> > 
> > Well, let's use that as well, then.
> 
> What I sense that you're suggesting, is that we take all the fixes in
> the gnulib code, and port them all into the two duplicates of similar
> code that's in Emacs.

No.  Gnulib code that you suggest to add does much more than just
avoid overflow.  See below.

> > Are we really going to consider seriously the case of a link name
> > overflowing a 64-bit ssize_t data type?
> 
> As a general rule, GNU code shouldn't have arbitrary limits, and
> should defend against limits in underyling systems.

Sorry, that doesn't answer the question.

The issue at hand is the price (in complexity and gratuitous added
code) we should pay for a simple overflow test.  I submit that the
price you are asking for is way too high in this case.  Where a single
comparison will suffice to resolve a very remote possibility of
overflow, you suggest to add 2 non-trivial gnulib modules.

> Emacs is not as good as it should be about this, and I'm trying to
> make it better.

Your efforts are appreciated.  But the issue at hand is not whether
Emacs code can and should be made better.  The issue is _how_ to do
that.  I respectfully submit that in this particular case, the
technique selected for improving the code in this particular area is
not the best alternative.

> This is just one example of many, found by static checking, and we
> might as well fix it while we're fixing all the others.

I support fixing possible overflows, just not with sledgehammer style
techniques such as this one.

> > We could refactor the duplicated code into a short function, and use
> > that.
> 
> That's what's being done here.  The function does even more than that,
> though

Exactly!

> it avoids the need to call malloc and free entirely, in the usual
> case.  This is a performance win in the typical case.

There should be a good reason for introducing this additional code; a
remote possibility of an overflow is not such a good reason.  As for
performance win, the callers of this code are not performance
critical, AFAICT.  So this is an example of premature optimization,
IMO.

What I'm suggesting is to solve the overflow, and nothing else.
Again, I can hardly believe that doing so would need more than a
simple comparison, and I agree that a function which allocates a
buffer and calls readlink with that buffer, while avoiding overflow,
could be used in both places, to avoid code replication.

bug#8401: removing duplication and improving the readlink code

[Paul Eggert]

On 04/01/2011 01:57 PM, Eli Zaretskii wrote:

> this just underlines the difficulty of reading the convoluted
> arrangement that this patch introduces.

Actually, the patch reduces the complexity of Emacs proper; it
removes 58 lines and adds 39 lines.  The patch's core is simple: a
function emacs_readlink, whose body is two lines long, replaces
duplicated code elsewhere in Emacs.

There's nothing that hard about this.  There is some indirection (which
you're calling a "convoluted arrangement"), but that is normal when
replacing inline code with a call to a parameterizable library.  It's
not rocket science.

> this just underlines the difficulty of reading the convoluted
> arrangement that this patch introduces

I would think that only a quick and careless read of the code would
lead one to believe that it calls malloc from Emacs without blocking
interrupts.  However, I wrote the code and perhaps am not the best to
judge its clarity.  A specific suggestion to make the code clearer
(without introducing bugs or reducing flexibility) would be welcome.

> Sorry, that doesn't answer the question.

OK, then the answer is yes, I'm going to seriously consider the case
of Emacs going bad when int or size_t or ssize_t overflows.  This can
occur when the underlying file system is corrupted and reports an incorrect
file size.  I've had this happen personally.  In such cases Emacs
should not crash.

> There should be a good reason for introducing this

There are at least four good reasons.  The change simplifies Emacs's
source code.  It makes Emacs smaller and faster; for example, it
typically reduces the number of system calls (on my RHEL 5.6 host a
patched Emacs typically uses four fewer system calls to lock a file).
The change improves the reliability of Emacs slightly, in unusual
overflow cases.  And the code is written and works.

bug#8401: removing duplication and improving the readlink code

[Stefan Monnier]

> source code.  It makes Emacs smaller and faster; for example, it

In which way does it make it smaller?  Do you mean the source code
exclusing the gnulib imported modues, or do you really mean
the executable?


        Stefan

bug#8401: removing duplication and improving the readlink code

[Paul Eggert]

On 04/03/2011 09:41 AM, Stefan Monnier wrote:
> In which way does it make it smaller?  Do you mean the source code
> exclusing the gnulib imported modues, or do you really mean
> the executable?

I meant less memory used at runtime, because a patched
Emacs typically skips a malloc when it reads a link.
(The non-gnulib source code also shrinks.)  These effects
are both minor, of course.