diff --git a/src/vtestream-file.h b/src/vtestream-file.h
index 8e7485a..3bfb154 100644
--- a/src/vtestream-file.h
+++ b/src/vtestream-file.h
@@ -20,6 +20,59 @@
  * Google Author(s): Behdad Esfahbod
  */
 
+/*
+ * The data structure implemented here remembers the last certain amount of
+ * data written, with the size dynamically changing. Basic operations include
+ * appending data (advancing the head), forgetting old data (advancing the
+ * tail), and random access read. In these cases the logical head and tail
+ * offsets can only increase. Rare special operations that don't influence the
+ * overall design are popping data from the head, and resetting the stream.
+ *
+ * The mapping from logical to physical offsets can be in one of 4 states:
+ * 1. One continuous region;
+ * 2. Two continuous regions, the second one preceding the first;
+ * 3. Three continuous regions, the second one preceding the first, and the
+ *    third being at the end;
+ * 4. Two continuous regions, the first one preceding the second.
+ *
+ * Initially, data is simply written to the file, we're at state 1:
+ * (A) abcdef
+ *
+ * Later the tail starts to advance too, but we're still in state 1:
+ * (B) __cdefgh
+ *
+ * At some point, based on heuristics, we wrap to the beginning, into state 2:
+ * (C) k___efghij
+ *
+ * The trivial case: If tail reaches EOF before head would bite tail, we're
+ * back at state 1 and we can even truncate the file:
+ * (D) klmnop____
+ * (E) klmnop
+ *
+ * Let's jump back to (C) to see the non-trivial case:
+ * (C) k___efghij
+ *
+ * If head would bite tail, we continue appending at EOF, entering state 3:
+ * (F) klmnofghijp
+ *
+ * As tail keeps advancing, we're still in state 3:
+ * (G) klmno__hijpqr
+ *
+ * When tail finishes with the middle segment, we enter state 4:
+ * (H) klmno_____pqrst
+ *
+ * Further advancing tail keeps us at state 4:
+ * (I) __mno_____pqrstuvw
+ *
+ * When tail finishes with the first segment, we return to state 1:
+ * (J) __________pqrstuvwxy
+ *
+ * Based on the aforementioned heuristics, we probably soon switch to state 2:
+ * (K) z___________rstuvwxy
+ *
+ * and so on...
+ */
+
 #include <errno.h>
 
 #include "vteutils.h"
@@ -336,11 +389,17 @@ _file_write (_file_t *f, const char *data, gsize len, gsize offset)
 typedef struct _VteFileStream {
 	VteStream parent;
 
-	/* The first file/offset is for the write head, second is for last page */
-	_file_t file[2];
-	gsize offset[2];
-	gsize head;
+	_file_t file;
+	int state;
+	struct {
+		gsize st_tail;  /* Stream's logical tail offset. */
+		gsize st_head;  /* Stream's logical head offset. */
+		gsize fd_tail;  /* FD's physical tail offset. */
+		gsize fd_head;  /* FD's physical head offset. Redundant, nevermind. */
+	} segment[3];  /* At most 3 segments, [0] at the tail. */
+	gsize head;  /* This one's redundant too, for convenience. */
 } VteFileStream;
+#define VTE_FILE_STREAM_SEGMENTS(s) ((s)->state == 4 ? 2 : (s)->state)
 
 typedef VteStreamClass VteFileStreamClass;
 
@@ -352,8 +411,8 @@ G_DEFINE_TYPE (VteFileStream, _vte_file_stream, VTE_TYPE_STREAM)
 static void
 _vte_file_stream_init (VteFileStream *stream)
 {
-	_file_init (&stream->file[0]);
-	_file_init (&stream->file[1]);
+	_file_init (&stream->file);
+	stream->state = 1;
 }
 
 VteStream *
@@ -367,25 +426,24 @@ _vte_file_stream_finalize (GObject *object)
 {
 	VteFileStream *stream = (VteFileStream *) object;
 
-	_file_close (&stream->file[0]);
-	_file_close (&stream->file[1]);
+	_file_close (&stream->file);
 
 	G_OBJECT_CLASS (_vte_file_stream_parent_class)->finalize(object);
 }
 
 static inline void
-_vte_file_stream_ensure_file0 (VteFileStream *stream)
+_vte_file_stream_ensure_file (VteFileStream *stream)
 {
 	int fd;
 
-	if (G_LIKELY (_file_isopen (&stream->file[0])))
+	if (G_LIKELY (_file_isopen (&stream->file)))
 		return;
 
         fd = _vte_mkstemp ();
         if (fd == -1)
                 return;
 
-        _file_open (&stream->file[0], fd);
+        _file_open (&stream->file, fd);
 }
 
 static void
@@ -393,21 +451,54 @@ _vte_file_stream_reset (VteStream *astream, gsize offset)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
 
-	_file_reset (&stream->file[0]);
-	_file_reset (&stream->file[1]);
+	_file_reset (&stream->file);
 
-	stream->head = stream->offset[0] = stream->offset[1] = offset;
+	stream->segment[0].st_tail = stream->segment[0].st_head = stream->head = offset;
+	stream->segment[0].fd_tail = stream->segment[0].fd_head = 0;
+	stream->state = 1;
 }
 
+/*
+ * When appending, the following state transfers can occur (even more of them
+ * if the data written is large enough):
+ * 1->2, 2->3.
+ */
 static void
 _vte_file_stream_append (VteStream *astream, const char *data, gsize len)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
+	int last_segment;
+
+	_vte_file_stream_ensure_file (stream);
+
+	g_assert(len > 0);
+
+	/* TODO add comment here about the heuristics */
+	if (G_UNLIKELY (stream->state == 1 && 2 * stream->segment[0].fd_tail > stream->segment[0].fd_head)) {
+		stream->segment[1].st_tail = stream->segment[1].st_head = stream->segment[0].st_head;
+		stream->segment[1].fd_tail = stream->segment[1].fd_head = 0;
+		stream->state = 2;
+	}
 
-	_vte_file_stream_ensure_file0 (stream);
+	if (stream->state == 2) {
+		gsize l;
+		l = MIN(len, stream->segment[0].fd_tail - stream->segment[1].fd_head);
+		_file_write (&stream->file, data, l, stream->segment[1].fd_head);
+		data += l; len -= l;
+		stream->segment[1].st_head += l; stream->segment[1].fd_head += l;
+		if (len == 0) {
+			stream->head = stream->segment[1].st_head;
+			return;
+		}
+		stream->segment[2].st_tail = stream->segment[2].st_head = stream->segment[1].st_head;
+		stream->segment[2].fd_tail = stream->segment[2].fd_head = stream->segment[0].fd_head;
+		stream->state = 3;
+	}
 
-	_file_write (&stream->file[0], data, len, stream->head - stream->offset[0]);
-	stream->head += len;
+	last_segment = VTE_FILE_STREAM_SEGMENTS(stream) - 1;
+	_file_write (&stream->file, data, len, stream->segment[last_segment].fd_head);
+	stream->segment[last_segment].st_head += len; stream->segment[last_segment].fd_head += len;
+	stream->head = stream->segment[last_segment].st_head;
 }
 
 static gboolean
@@ -416,59 +507,129 @@ _vte_file_stream_read (VteStream *astream, gsize offset, char *data, gsize len)
 	VteFileStream *stream = (VteFileStream *) astream;
 	gsize l;
 
-	if (G_UNLIKELY (offset < stream->offset[1]))
+	int segments = VTE_FILE_STREAM_SEGMENTS(stream);
+	int i;
+
+	// FIXME if offset+len >= stream->segment[0].tail: should memset(0) and then partially read
+	if (G_UNLIKELY (offset < stream->segment[0].st_tail))
 		return FALSE;
 
-	if (offset < stream->offset[0]) {
-		l = _file_read (&stream->file[1], data, len, offset - stream->offset[1]);
+	for (i = 0; i < segments; i++) {
+		if (offset >= stream->segment[i].st_head)
+			continue;
+		l = MIN(stream->segment[i].st_head - offset, len);
+		l = _file_read (&stream->file, data, l, offset + stream->segment[i].fd_tail - stream->segment[i].st_tail);
 		offset += l; data += l; len -= l; if (!len) return TRUE;
 	}
 
-	l = _file_read (&stream->file[0], data, len, offset - stream->offset[0]);
-	offset += l; data += l; len -= l; if (!len) return TRUE;
-
 	return FALSE;
 }
 
-static void
-_vte_file_stream_swap_fds (VteFileStream *stream)
-{
-	_file_t f;
-
-	f = stream->file[0]; stream->file[0] = stream->file[1]; stream->file[1] = f;
-}
-
+/*
+ * When truncating, the following state transfers can occur (even more of them
+ * if the truncated amount is large enough):
+ * 4->1, 3->2, 2->1.
+ */
 static void
 _vte_file_stream_truncate (VteStream *astream, gsize offset)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
+	int last_segment;
 
-	if (G_UNLIKELY (offset < stream->offset[1])) {
-		_file_reset (&stream->file[1]);
-		stream->offset[1] = offset;
-	}
+	g_assert(offset >= stream->segment[0].st_tail);
+	g_assert(offset <= stream->head);
 
-	if (G_UNLIKELY (offset < stream->offset[0])) {
-		_file_reset (&stream->file[0]);
-		stream->offset[0] = stream->offset[1];
-		_vte_file_stream_swap_fds (stream);
-	} else {
-		_file_try_truncate (&stream->file[0], offset - stream->offset[0]);
+	if (G_UNLIKELY (offset == stream->segment[0].st_tail)) {
+		_vte_file_stream_reset (astream, offset);
+		return;
 	}
 
-	stream->head = offset;
+	while (TRUE) {
+		last_segment = VTE_FILE_STREAM_SEGMENTS(stream) - 1;
+		if (offset >= stream->segment[last_segment].st_head) return;
+		if (offset > stream->segment[last_segment].st_tail) {
+			/* Truncate some (but not all) bytes from the last segment. */
+			gsize diff = stream->segment[last_segment].st_head - offset;
+			stream->segment[last_segment].st_head -= diff;
+			stream->segment[last_segment].fd_head -= diff;
+			stream->head = stream->segment[last_segment].st_head;
+			if (stream->state != 2) {
+				_file_try_truncate(&stream->file, stream->segment[last_segment].fd_head);
+			}
+			return;
+		} else {
+			/* Discard the whole last segment. */
+			switch (stream->state) {
+			case 1:
+				g_assert_not_reached();
+				break;
+			case 2:
+				stream->state = 1;
+				break;
+			case 3:
+				stream->state = 2;
+				_file_try_truncate(&stream->file, stream->segment[0].fd_head);
+				break;
+			case 4:
+				stream->state = 1;
+				_file_try_truncate(&stream->file, stream->segment[0].fd_head);
+				break;
+			default:
+				g_assert_not_reached();
+				break;
+			}
+		}
+	}
+	last_segment = VTE_FILE_STREAM_SEGMENTS(stream) - 1;
+	stream->head = stream->segment[last_segment].st_head;
 }
 
+/*
+ * When advancing the tail, the following state transfers can occur (even more
+ * of them if the amount discarded is large enough):
+ * 2->1, 3->4, 4->1.
+ */
 static void
 _vte_file_stream_advance_tail (VteStream *astream, gsize offset)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
 
-	if (offset >= stream->offset[0]) {
-		stream->offset[1] = stream->offset[0];
-		stream->offset[0] = stream->head;
-		_vte_file_stream_swap_fds (stream);
-		_file_reset (&stream->file[0]);
+	g_assert(offset >= stream->segment[0].st_tail);
+	g_assert(offset <= stream->head);
+
+	if (G_UNLIKELY (offset == stream->head)) {
+		_vte_file_stream_reset (astream, offset);
+		return;
+	}
+
+	while (offset > stream->segment[0].st_tail) {
+		if (offset < stream->segment[0].st_head) {
+			/* Drop some (but not all) bytes from the first segment. */
+			gsize diff = offset - stream->segment[0].st_tail;
+			stream->segment[0].st_tail += diff;
+			stream->segment[0].fd_tail += diff;
+			return;
+		} else {
+			/* Drop the entire first segment. */
+			switch (stream->state) {
+			case 1:
+				g_assert_not_reached();
+				break;
+			case 2:
+			case 4:
+				stream->segment[0] = stream->segment[1];
+				stream->state = 1;
+				break;
+			case 3:
+				stream->segment[0] = stream->segment[1];
+				stream->segment[1] = stream->segment[2];
+				stream->state = 4;
+				break;
+			default:
+				g_assert_not_reached();
+				break;
+			}
+		}
 	}
 }
 
