a repeatable 'more' crash and question about wide char and 'get_line' safety

Hi,
I've got a repeatable (for me!) crash in 'more' in git
( 5d3da4a24d0f952eb3709ba62c74aaa04729e08f ) that's also in at least 2.23.1 - and I don't know how much older.

I believe the problem relates to the way the Line buffer is managed in get_line; but more of the diagnosis below.

The problem:
------------

*** Error in `/usr/bin/more': free(): invalid pointer: 0x000000000060f850 ***

This was generated on OpenSuse 'factory' with their 2.23.1-4.3.x86_64 package, but then verified it on the current util-linux git. Here is the bug I filed in their system:

https://bugzilla.novell.com/show_bug.cgi?id=829720

With the following test file:
https://bugzilla.novell.com/attachment.cgi?id=548234

(It's a fragment of /var/lib/rpm/Packages that I was stupid enough to more).

The seg triggers in an 86x25 terminal for me just with

more tstfile2

It needs a UTF-8 LANG, I'm running with en_GB.UTF-8 but en_US.UTF-8 also triggers it.

My original test triggered an invalid free check, but with the help of valgrind I narrowed it down to:

==22488== Invalid write of size 1
==22488== at 0x4037A2: get_line (more.c:1043)

        if (colflg && eatnl && Wrap) {
                *p++ = '\n';    /* simulate normal wrap */
        }

==22488== by 0x4066C3: screen (more.c:660)
==22488== by 0x4025E4: main (more.c:503)
==22488== Address 0x542c318 is 0 bytes after a block of size 344 alloc'd
==22488== at 0x4C297AB: malloc (in /usr/lib64/valgrind/vgpreload_memcheck-amd64-lin

Answers/questions
-----------------

I've put a load of debug in and have some answers/questions:

1) The loop in get_line() is:
while (p < &Line[LineLen - 1]) {

if I understand correctly that would seem to imply that if the loop always wrote no more than 1 character per iteration there should be 1 space left in Line when you hit the bottom; of the loop, one for the \n in the code above that writes the '\n' sometimes.... but then it always writes a \0 on the end as well - so whenever we tack on a \n I think we overflow with the \0 if we're right at the end.

2) unfortunately there are cases where the loop writes more than 1 char per iteration; looking at:

http://git.kernel.org/cgit/utils/util-linux/util-linux.git/tree/text-utils/more.c#n874

we see that the wide character code can take it's (size_t)-1 case, write a character and then it GOTO's (*) process_mbc: and hopefully lands in the default case and writes some characters in it's else clause; (in this test case 1) - but that loop worries me that it's possible to write more than one.

So hmm, what's the fix?

a) I think that loop limit needs to be at least LineLen - 2 just to cope with the \n and \0 case; and there is also at least one inner loop (for tabs) that also has that loop limit coded in it that needs to match

b) If we knew what the worst case was for the number of characters the WIDECHAR stuff could write then we could make the loop termination condition would then leave enoguh space for an entire widechar.

c) Do we also need to change the allocation code in prepare_line_buffer?

It has:
size_t nsz = Mcol * 4;

Now that magic 4 isn't commented, but I'm currently guessing as it being the answer of (b) above - ie the size of a widechar? If so then I think it needs at least a +2 for the \n and \0

Dave (who doesn't know multi byte/wide stuff)

* Please hand Dijkstra a muffin

 -----Open up your eyes, open up your mind, open up your code -------   
/ Dr. David Alan Gilbert    |       Running GNU/Linux       | Happy  \ 
\ gro.gilbert @ treblig.org |                               | In Hex /
 \ _________________________|_____ http://www.treblig.org   |_______/

Hi,
This is a fix for the bug I reported with 'more' crashing:
http://marc.info/?l=util-linux-ng&m=137401887913346&w=2

It seems to work for me, but I'd appreciate another pair of eyes on it, especially a pair with a better understanding of wide characters.

I could also see that it might be nice to add my failing case from the bug as a regression test, but is there a good way to get those tests to run with a given idea of terminal width/character encoding?

Dave

commit 96c2d8eaed137cbb9d62f0f50bdf689aa8a0f2e3

Author: Dr. David Alan Gilbert <[email protected]>
Date:   Fri Jul 19 23:19:39 2013 +0100

Ensure there is space at the end of the buffer for the termination characters, and that there is space for a full wide character.

index 3bbeede..b81e32a 100644
@@ -43,6 +43,7 @@
  *	modified mem allocation handling for util-linux
  */
 
+#include <assert.h>
 #include <stdio.h>
 #include <string.h>
 #include <unistd.h>

@@ -167,6 +168,9 @@ int shellp;			/* A previous shell command exists */
 sigjmp_buf restore;
 char *Line;			/* Line buffer */
 size_t LineLen;			/* size of Line buffer */
+const unsigned int line_end_space = 2; /* For the nl and \0 at the end */
+const unsigned int wchar_max_bytes = 4; /* I don't see a portable way to
+					determine this */
 int Lpp = LINES_PER_PAGE;	/* lines per page */
 char *Clear;			/* clear screen */
 char *eraseln;			/* erase line */

@@ -827,7 +831,7 @@ static void prompt(char *filename)
 void prepare_line_buffer(void)
 {
 	char *nline;
-	size_t nsz = Mcol * 4;
+	size_t nsz = Mcol * wchar_max_bytes + line_end_space;
 
 	if (LineLen >= nsz)
 		return;

@@ -872,7 +876,7 @@ int get_line(register FILE *f, int *length)
 		Currline++;
 		c = Getc(f);
 	}
-	while (p < &Line[LineLen - 1]) {
+	while (p <= &Line[LineLen - (line_end_space + wchar_max_bytes)]) {
 #ifdef HAVE_WIDECHAR
 		if (fold_opt && use_mbc_buffer_flag && MB_CUR_MAX > 1) {
 			use_mbc_buffer_flag = 0;

@@ -961,7 +965,7 @@ int get_line(register FILE *f, int *length)
 					my_putstring(eraseln);
 					promptlen = 0;
 				} else {
-					for (--p; p < &Line[LineLen - 1];) {
+					for (--p; p <= &Line[LineLen - (1 + line_end_space)];) {
 						*p++ = ' ';
 						if ((++column & 7) == 0)
 							break;

@@ -1039,6 +1043,7 @@ int get_line(register FILE *f, int *length)
 	if (colflg && eatnl && Wrap) {
 		*p++ = '\n';	/* simulate normal wrap */
 	}
+	assert(p < &Line[LineLen]);
 	*length = p - Line;
 	*p = 0;
 	return (column);

It seems that bug has been introduced 4 years ago by my commit 1ac300932deab8dea2c43050921bbbdb36d62ff1.

The original code used static buffer Line[LINSIZ+2] -- yes, +2 for \n\0.

I have applied the patch below. Please, test it (I'm not able to reproduce the problem with the file from Suse bugzilla).

Thanks!

Karel

From: Karel Zak <[email protected]>
Date: Thu, 1 Aug 2013 12:58:22 +0200
Subject: [PATCH] more: fix buffer overflow

The bug has been probably introduced by commit
1ac300932deab8dea2c43050921bbbdb36d62ff1.

References: https://bugzilla.novell.com/show_bug.cgi?id=829720

---
 text-utils/more.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

index 3bbeede..3377118 100644
@@ -835,7 +835,8 @@ void prepare_line_buffer(void)
 	if (nsz < LINSIZ)
 		nsz = LINSIZ;
 
-	nline = xrealloc(Line, nsz);
+	/* alloc nsz and extra space for \n\0 */
+	nline = xrealloc(Line, nsz + 2);
 	Line = nline;
 	LineLen = nsz;
 }

1.8.1.4

Hi Karel,
Thanks for the reply. I'll give it a go over the weekend,
but I don't think it can handle the wchar problems I described and fixed in my follow up patch. If a 4byte wchar hapens to land at the end of the buffer how do you guarantee the space?

Dave

 -----Open up your eyes, open up your mind, open up your code -------   
/ Dr. David Alan Gilbert    |       Running GNU/Linux       | Happy  \ 
\ gro.gilbert @ treblig.org |                               | In Hex /
 \ _________________________|_____ http://www.treblig.org   |_______/

Ah, I probably see what you mean. So I have added p < &Line[LineLen - 1] check to the for() where the code copies the multibyte buffer to line buffer. See git tree for more details.

Karel

 Karel Zak  <[email protected]>
 http://karelzak.blogspot.com

OK; so I think with your ...ea608842 change then it should work (not tried to push it); but with that change hopefully the extra check in ..623bc74f should never trigger; which is good because if it does then I think you'll end up outputing part of a wide character which would get messy.

One thing I tried to do in my change was remove the magic '4's that pop up in a few places because of the wide characters.

(Any particular reason you prefered this over my fix?)

Dave

 -----Open up your eyes, open up your mind, open up your code -------   
/ Dr. David Alan Gilbert    |       Running GNU/Linux       | Happy  \ 
\ gro.gilbert @ treblig.org |                               | In Hex /
 \ _________________________|_____ http://www.treblig.org   |_______/

then it would be better to use #define ...

Anyway, the more.c code is so horrible that it does not make sense to waste time to try to make it perfect. It would be better to do complete refactoring (some control struct, small functions, no global variables, etc.)

Unfortunately I somehow missed the widechar issue in my first commit, so your original patch was no bad (except the global const variables).

Thanks, look forward to see more patches from you :-)

Karel

 Karel Zak  <[email protected]>
 http://karelzak.blogspot.com