'Re: bug in vi's undo'

[prev in list] [next in list] [prev in thread] [next in thread] 

List:       busybox
Subject:    Re: bug in vi's undo
From:       Jody Bruchon <jody () jodybruchon ! com>
Date:       2018-06-03 19:44:44
Message-ID: 01b96e54-b43a-07d4-4ac0-f588654964da () jodybruchon ! com
[Download RAW message or body]

On 6/3/2018 1:32 AM, Kartik Agaram wrote:
> $ git log |head -n1
> commit 0972c7f7a570c38edb68e1c60a45614b7a7c7d55
> $ uname -a
> Linux akkartik 4.4.0-112-generic #135-Ubuntu SMP Fri Jan 19 11:48:14
> UTC 2018 i686 i686 i686 GNU/Linux
> $ gcc --version
> gcc (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609
>
> To reproduce:
>
> $ make menuconfig
> # accept all defaults, save config
> $ make
> $ cat > x
> a
> b
> c
> d
> e
> $ ./busybox vi x
> Navigate to the bottom line, delete using 'dd'.
> Hit 'dd' again to delete the new bottom line.
> Hit 'u' to undo the previous deletion.
> Hit 'u' a second time.
>
> Expected contents:
> a
> b
> c
> d
> e
>
> Contents seen:
> ^@a
> b
> c
> d
>
> An earlier version also segfaulted at this point.
>
> === Attempt #1
>
> The issue seems to be fixed by deleting this special-case when the
> deleted text is at the end of the buffer:
>
> @@ -2307,10 +2307,6 @@ static void undo_push(char *src, unsigned int
> length, uint8_t u_type)    // Add to
>          // Allocate a new undo object
>          if (u_type == UNDO_DEL || u_type == UNDO_DEL_CHAIN) {
>                  // For UNDO_DEL objects, save deleted text
> -               if ((src + length) == end)
> -                       length--;
> -               // If this deletion empties text[], strip the newline.
> When the buffer becomes
> -               // zero-length, a newline is added back, which
> requires this to compensate.
>                  undo_entry = xzalloc(offsetof(struct undo_object,
> undo_text) + length);
>                  memcpy(undo_entry->undo_text, src, length);
>          } else {
>
> However, as that deleted comment hints, then I reintroduce a bug in a
> different situation:
>
> Delete all 5 lines with '5dd'.
> Hit 'u' to undo.
>
> Instead of seeing the original 5 lines, I end up with an extra final newline.
>
> === Attempt #2
>
> I can fix both situations by changing the condition to match (my
> interpretation of) the comment, triggering only when the entire buffer
> is deleted:
>
> @@ -2307,7 +2307,7 @@ static void undo_push(char *src, unsigned int
> length, uint8_t u_type)     // Add to
>          // Allocate a new undo object
>          if (u_type == UNDO_DEL || u_type == UNDO_DEL_CHAIN) {
>                  // For UNDO_DEL objects, save deleted text
> -               if ((src + length) == end)
> +               if (src == text && (src + length) == end)
>                          length--;
>                  // If this deletion empties text[], strip the newline.
> When the buffer becomes
>                  // zero-length, a newline is added back, which
> requires this to compensate.
>
> Can any of you[1] think other situations where this would break?
>
> Thanks,
> Kartik
>
> [1] Particularly Jody Bruchon, original author of commit a8d6f9be in
> Apr 2014. Thanks in advance, Jody.
I am the author of the original commit but my original code has been 
significantly modified since then, so I may not have much useful insight 
for this one. I have experienced problems with several BusyBox versions 
where undoing some things, particularly the 'x' command, poops nulls 
(the ^@ you're seeing in the buffer) everywhere. After receiving your 
email I went back to BusyBox 1.22.1 which my patch was against and I 
confirmed that my original undo with queuing patch does indeed segfault 
in this "double dd at end" case, and apparently so does BusyBox master. 
Valgrind says there are some problems with touching invalid memory 
(partial output):

-- snip --
==6625== Invalid read of size 1
==6625==    at 0x4C2DFC0: memmove (vg_replace_strmem.c:1109)
==6625==    by 0x495BBC: text_hole_make (vi.c:2487)
==6625==    by 0x499012: undo_pop (vi.c:2398)
==6625==    by 0x499012: do_cmd (vi.c:3696)
==6625==    by 0x49AD12: edit_file (vi.c:879)
==6625==    by 0x49AE58: vi_main (vi.c:700)
==6625==    by 0x4115EE: run_applet_no_and_exit (appletlib.c:947)
==6625==    by 0x4117C0: run_applet_and_exit (appletlib.c:965)
==6625==    by 0x411866: busybox_main (appletlib.c:908)
==6625==    by 0x411866: run_applet_and_exit (appletlib.c:958)
==6625==    by 0x41197F: main (appletlib.c:1073)
==6625==  Address 0x5418a63 is 3 bytes after a block of size 10,240 alloc'd
==6625==    at 0x4C27ADF: malloc (vg_replace_malloc.c:296)
==6625==    by 0x4125A6: xmalloc (xfuncs_printf.c:50)
==6625==    by 0x4125E4: xzalloc (xfuncs_printf.c:71)
==6625==    by 0x497AAA: init_text_buffer (vi.c:720)
==6625==    by 0x49AA73: edit_file (vi.c:789)
==6625==    by 0x49AE58: vi_main (vi.c:700)
==6625==    by 0x4115EE: run_applet_no_and_exit (appletlib.c:947)
==6625==    by 0x4117C0: run_applet_and_exit (appletlib.c:965)
==6625==    by 0x411866: busybox_main (appletlib.c:908)
==6625==    by 0x411866: run_applet_and_exit (appletlib.c:958)
==6625==    by 0x41197F: main (appletlib.c:1073)
==6625==
==6625==
==6625== Process terminating with default action of signal 11 (SIGSEGV)
==6625==  Access not within mapped region at address 0x5811000
==6625==    at 0x4C2DFC3: memmove (vg_replace_strmem.c:1109)
==6625==    by 0x495BBC: text_hole_make (vi.c:2487)
==6625==    by 0x499012: undo_pop (vi.c:2398)
==6625==    by 0x499012: do_cmd (vi.c:3696)
==6625==    by 0x49AD12: edit_file (vi.c:879)
==6625==    by 0x49AE58: vi_main (vi.c:700)
==6625==    by 0x4115EE: run_applet_no_and_exit (appletlib.c:947)
==6625==    by 0x4117C0: run_applet_and_exit (appletlib.c:965)
==6625==    by 0x411866: busybox_main (appletlib.c:908)
==6625==    by 0x411866: run_applet_and_exit (appletlib.c:958)
==6625==    by 0x41197F: main (appletlib.c:1073)
==6625==  If you believe this happened as a result of a stack
==6625==  overflow in your program's main thread (unlikely but
==6625==  possible), you can try to increase the size of the
==6625==  main thread stack using the --main-stacksize= flag.
==6625==  The main thread stack size used in this run was 8388608.

-- snip --

Several Valgrind warnings are about text_hole_make(), in fact. If I had 
to take a shot in the dark I'd guess there is some sort of off-by-one 
error...or that I managed to violate this comment in text_hole_make():

"and be careful to not use pointers into potentially freed text[]!"

The way BusyBox vi tracks stuff is interesting and sometimes a little 
difficult to work with. I tried to write a vi clone of my own[1] as a 
coding exercise and my approach to the implementation was to store the 
data on a line-by-line basis (allocated in 32-byte chunks at first and 
then doubled as the line expands, with a realloc if a line extension is 
required) instead of the usual text editor method of having a buffer and 
"opening holes." Perhaps converting BusyBox vi to a line-based text 
storage method instead of a buffer-and-hole method would simplify 
things. In any case, my efforts showed me how much of a pain writing a 
compact text editor can be.

This one's probably going to require some tooling around in gdb; I 
currently don't have time to do that, but I hope I've pointed someone in 
the right direction.

-Jody

[1] https://github.com/jbruchon/vee-eye
_______________________________________________
busybox mailing list
busybox@busybox.net
http://lists.busybox.net/mailman/listinfo/busybox

[prev in list] [next in list] [prev in thread] [next in thread] 