Re: string-backed FILEs mess

[Rich Felker <dalias@libc.org>]

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

On Fri, Sep 14, 2018 at 12:24:09PM -0400, Rich Felker wrote:
> On Fri, Sep 14, 2018 at 11:52:27AM -0400, Rich Felker wrote:
> > On Wed, Sep 12, 2018 at 01:18:24PM -0400, Rich Felker wrote:
> > > On Wed, Sep 12, 2018 at 12:33:45PM -0400, Rich Felker wrote:
> > > > OK, I've been properly initializing the FILE rather than leaving it
> > > > uninitialized except for the important fields like the old code did.
> > > > Changing that, it's 1.44s with step 8, 1.60s with step 24. I also
> > > > confirmed that this version of the code is almost as fast as the
> > > > existing code with the memchr removed (just assuming it can read
> > > > ahead).
> > > 
> > > Uhg, the source of the "almost" here makes me even more convinced the
> > > current code must go. Part of the reason it's not as fast was that I
> > > was still setting f.read=__string_read, which requires (this is on
> > > i386, 32-bit) setting up the GOT pointer.
> > > 
> > > What was the old code doing? f.read was uninitialized. But the new
> > > code crashes in that case when hitting the end of the string. Why
> > > doesn't the old code crash? Because f.rend is set way past the end of
> > > the string and never reached. If it were reached:
> > > 
> > > 1. The shgetc macro calls the __shgetc function.
> > > 2. The __shgetc function calls __uflow.
> > > 3. __uflow calls __toread.
> > > 4. __toread inspects uninitialized f->wpos/f->wbase fields and,
> > >    depending on the values it sees, calls f->write, which is also
> > >    uninitialized.
> > > 5. If it gets past that, next __uflow calls the uninitialized f->read.
> > > 
> > > The fact that any of this works at all is a fragile shit-show, and
> > > completely depends on __intscan/__floatscan just using (via shgetc) a
> > > tiny undocumented subset of the FILE structure and a tiny undocumented
> > > subset of the stdio interfaces on it.
> > > 
> > > Really the existing code is just a poor substitute for having an
> > > abstraction for windowed string iteration, using the stdio FILE
> > > structure in a way that also works with real FILEs. It's clever, but
> > > this kind of clever is not a good thing.
> > > 
> > > I'm still not sure what the right way forward is, though.
> > 
> > OK, a small breakthrough that makes this mess a lot simpler:
> > 
> > The __intscan and __floatscan backends do not (and are not allowed to,
> > but this should be documented and isn't) call any stdio functions on
> > the fake FILE* passed to them except for the shgetc and shunget
> > macros, defined as:
> > 
> > #define shgetc(f) (((f)->rpos < (f)->shend) ? *(f)->rpos++ : __shgetc(f))
> > #define shunget(f) ((f)->shend ? (void)(f)->rpos-- : (void)0)
> > 
> > If the < is merely replaced by !=, which is functionally equivalent,
> > then shend can be any type of sentinel pointer we want (e.g. (void*)-1
> > or even just &localvar) to use the buffer as a string with no known
> > length, and we have a guarantee that __shgetc is never called.
> > 
> > I think this -1+2-byte change is an acceptable resolution to the issue
> > for now.
> 
> Uhg, nope, mistake: they also use shcnt/shlim, which perform
> arithmetic on f->shend. This fix might still be salvagable, but not
> without significant additional work removing the dependency on invalid
> arithmetic.

Here's the patch I'm looking at now. Summary of what happened:

Previously, f->shcnt stored the count that would have been read if
consuming the whole buffer, which required an end pointer for the
buffer. The purpose for this was that it allowed reading it and adding
rpos-rend at any time to get the actual count so far, and required no
adjustment at the time of __shgetc (actual function call) since the
call would only happen when reaching the end of the buffer (actually
there may have been bugs in this with the interaction of scanf field
widths and end-of-buffer boundaries; it would be interesting to go
back and check that).

To get rid of the dependency on rend, I'm instead offsetting shcnt by
buf-rpos (start of buffer) at the time of last __shlim/__shgetc call.
This makes for slightly more work in __shgetc the function, but for
the inline macro it's still just as easy to compute the current count.

It doesn't break anything in libc-test or cause a performance or
functionality regression in my strtol performance measurement program,
so I think it's okay, but I'd appreciate any second looks others are
available to give. :-)

As a bonus I added comments.

Rich

[-- Attachment #2: strtoUB.diff --]
[-- Type: text/plain, Size: 4084 bytes --]

diff --git a/src/internal/shgetc.c b/src/internal/shgetc.c
index e878b00..ebd5fae 100644
--- a/src/internal/shgetc.c
+++ b/src/internal/shgetc.c
@@ -1,10 +1,16 @@
 #include "shgetc.h"
 
+/* The shcnt field stores the number of bytes read so far, offset by
+ * the value of buf-rpos at the last function call (__shlim or __shgetc),
+ * so that between calls the inline shcnt macro can add rpos-buf to get
+ * the actual count. */
+
 void __shlim(FILE *f, off_t lim)
 {
 	f->shlim = lim;
-	f->shcnt = f->rend - f->rpos;
-	if (lim && f->shcnt > lim)
+	f->shcnt = f->buf - f->rpos;
+	/* If lim is nonzero, rend must be a valid pointer. */
+	if (lim && f->rend - f->rpos > lim)
 		f->shend = f->rpos + lim;
 	else
 		f->shend = f->rend;
@@ -13,15 +19,18 @@ void __shlim(FILE *f, off_t lim)
 int __shgetc(FILE *f)
 {
 	int c;
-	if (f->shlim && f->shcnt >= f->shlim || (c=__uflow(f)) < 0) {
+	off_t cnt = shcnt(f);
+	if (f->shlim && cnt >= f->shlim || (c=__uflow(f)) < 0) {
+		f->shcnt = f->buf - f->rpos + cnt;
 		f->shend = 0;
 		return EOF;
 	}
-	if (f->shlim && f->rend - f->rpos > f->shlim - f->shcnt - 1)
-		f->shend = f->rpos + (f->shlim - f->shcnt - 1);
+	cnt++;
+	if (f->shlim && f->rend - f->rpos > f->shlim - cnt)
+		f->shend = f->rpos + (f->shlim - cnt);
 	else
 		f->shend = f->rend;
-	if (f->rend) f->shcnt += f->rend - f->rpos + 1;
+	f->shcnt = f->buf - f->rpos + cnt;
 	if (f->rpos[-1] != c) f->rpos[-1] = c;
 	return c;
 }
diff --git a/src/internal/shgetc.h b/src/internal/shgetc.h
index 210f646..a4dd6d6 100644
--- a/src/internal/shgetc.h
+++ b/src/internal/shgetc.h
@@ -1,9 +1,27 @@
 #include "stdio_impl.h"
 
+/* Scan helper "stdio" functions for use by scanf-family and strto*-family
+ * functions. These accept either avalid stdio FILE, or a minimal pseduo
+ * FILE whose buffer pointers point into a null-terminated string. In the
+ * latter case, the sh_fromstring macro should be used to setup the FILE;
+ * the rest of the structure can be left uninitialized.
+ *
+ * To begin using these functions, shlim must first be called on the FILE
+ * to set a field width limit, or 0 for no limit. For string pseudo-FILEs,
+ * a nonzero limit is not valid and produces undefined behavior. After that,
+ * shgetc, shunget, and shcnt are valid as long as no other stdio functions
+ * are called on the stream. shunget can only be called once without an
+ * intervening successful shgetc on real stdio FILEs. It can be called
+ * multiple times, up to the number of successful shgetc calls, on a
+ * string pseudo-FILE. */
+
 hidden void __shlim(FILE *, off_t);
 hidden int __shgetc(FILE *);
 
-#define shcnt(f) ((f)->shcnt + ((f)->rpos - (f)->rend))
+#define sh_fromstring(f, s) \
+	((f)->buf = (f)->rpos = (void *)(s), (f)->rend = (void*)-1)
+
+#define shcnt(f) ((f)->shcnt + ((f)->rpos - (f)->buf))
 #define shlim(f, lim) __shlim((f), (lim))
-#define shgetc(f) (((f)->rpos < (f)->shend) ? *(f)->rpos++ : __shgetc(f))
+#define shgetc(f) (((f)->rpos != (f)->shend) ? *(f)->rpos++ : __shgetc(f))
 #define shunget(f) ((f)->shend ? (void)(f)->rpos-- : (void)0)
diff --git a/src/stdlib/strtod.c b/src/stdlib/strtod.c
index a898b1d..a5d0118 100644
--- a/src/stdlib/strtod.c
+++ b/src/stdlib/strtod.c
@@ -5,10 +5,8 @@
 
 static long double strtox(const char *s, char **p, int prec)
 {
-	FILE f = {
-		.buf = (void *)s, .rpos = (void *)s,
-		.rend = (void *)-1, .lock = -1
-	};
+	FILE f;
+	sh_fromstring(&f, s);
 	shlim(&f, 0);
 	long double y = __floatscan(&f, prec, 1);
 	off_t cnt = shcnt(&f);
diff --git a/src/stdlib/strtol.c b/src/stdlib/strtol.c
index d82ecf7..f42e7f8 100644
--- a/src/stdlib/strtol.c
+++ b/src/stdlib/strtol.c
@@ -9,13 +9,7 @@ static unsigned long long strtox(const char *s, char **p, int base, unsigned lon
 {
 	/* FIXME: use a helper function or macro to setup the FILE */
 	FILE f;
-	f.flags = 0;
-	f.buf = f.rpos = (void *)s;
-	if ((size_t)s > (size_t)-1/2)
-		f.rend = (void *)-1;
-	else
-		f.rend = (unsigned char *)s+(size_t)-1/2;
-	f.lock = -1;
+	sh_fromstring(&f, s);
 	shlim(&f, 0);
 	unsigned long long y = __intscan(&f, base, 1, lim);
 	if (p) {