diff --git a/src/vtestream-file.h b/src/vtestream-file.h
index 8e7485a..2a75632 100644
--- a/src/vtestream-file.h
+++ b/src/vtestream-file.h
@@ -20,31 +20,66 @@
  * Google Author(s): Behdad Esfahbod
  */
 
-#include <errno.h>
-
-#include "vteutils.h"
-
-
 /*
- * We provide two file implementations: one based on raw
- * syscalls, and one based on stdio.  The syscall one has
- * got more than enough testing in the past.  The stdio
- * is newer, but has a default cache, which greatly reduces
- * number of syscalls.
+ * 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
  *
- * Change the following conditional to 0 for syscalls, and
- * to 1 for stdio.  Please test both branches before
- * making changes to _file_t semantics or implementation.
+ * 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...
  */
 
-#if 0
-
+#include <errno.h>
+#include <string.h>
+#include <stdio.h>  // TODO: remove (it's temporary for debugging only)
+#include <unistd.h>
 
-/*
- * File implementation using Unix syscalls.
- */
+#include "vteutils.h"
 
-#include <unistd.h>
 
 #ifndef HAVE_PREAD
 #define pread _pread
@@ -108,7 +143,7 @@ _file_try_truncate (_file_t *f, gsize offset)
 	int ret;
 
 	if (G_UNLIKELY (!_file_isopen (f)))
-		return;
+		return TRUE;
 
 	do {
 		ret = ftruncate (f->fd, offset);
@@ -185,162 +220,34 @@ _file_write (_file_t *f, const char *data, gsize len, gsize offset)
 }
 
 
-#else
-
-
 /*
- * File implementation using stdio.
+ * VteFileStream: A file-based stream
  */
 
-#include <stdio.h>
-
-/* Use unlocked versions if available. */
-#ifdef HAVE_FWRITE_UNLOCKED
-#	define fwrite	fwrite_unlocked
-#	define fread	fread_unlocked
-#	define fflush	fflush_unlocked
-#endif
-
-typedef struct
-{
-	FILE *fp;
-	gsize pos;
-} _file_t;
-
-static inline void
-_file_init (_file_t *f)
-{
-	f->fp = NULL;
-	f->pos = -1;
-}
-
-static inline void
-_file_open (_file_t *f, int fd)
-{
-	f->fp = fdopen (fd, "w+");
-	f->pos = 0;
-}
-
-static inline gboolean
-_file_isopen (_file_t *f)
-{
-	return f->fp != NULL;
-}
-
-static inline void
-_file_close (_file_t *f)
-{
-	if (G_UNLIKELY (!_file_isopen (f)))
-		return;
-
-	fclose (f->fp);
-}
-
-
-static gboolean
-_file_try_truncate (_file_t *f, gsize offset)
-{
-	if (G_UNLIKELY (!_file_isopen (f)))
-		return TRUE;
-
-	/* We don't have to truncate.  The bytestream works
-	 * without a working truncate (hence the "try").
-	 * Here's a fallback implementation.  Things should
-	 * work with or without this.
-	 */
-	if (1)
-	{
-		int ret;
-
-		fflush (f->fp);
-
-		do {
-			ret = ftruncate (fileno (f->fp), offset);
-		} while (ret == -1 && errno == EINTR);
-
-		return !ret;
-	}
-
-	return FALSE;
-}
-
-static void
-_file_reset (_file_t *f)
-{
-	int fd;
-
-	if (_file_try_truncate (f, 0))
-		return;
-
-	if (G_UNLIKELY (!_file_isopen (f)))
-		return;
-
-	/* Reopen file to truncate it. */
-
-	fd = dup (fileno (f->fp));
-
-	_file_close (f);
-	_file_open (f, fd);
-}
-
-static gboolean
-_file_seek (_file_t *f, gsize offset)
-{
-	if (f->pos != offset)
-	{
-		if (-1 == fseek (f->fp, offset, SEEK_SET))
-			return FALSE;
-		f->pos = offset;
-	}
-	return TRUE;
-}
-
-static gsize
-_file_read (_file_t *f, char *data, gsize len, gsize offset)
-{
-	gsize ret;
-
-	if (G_UNLIKELY (!_file_isopen (f)))
-		return 0;
-
-	if (!_file_seek (f, offset))
-		return 0;
-
-	ret = fread (data, 1, len, f->fp);
-	f->pos += ret;
-	return ret;
-}
-
-static void
-_file_write (_file_t *f, const char *data, gsize len, gsize offset)
-{
-	gsize ret;
-
-	g_assert (_file_isopen (f) || !len);
-
-	if (!_file_seek (f, offset))
-		return;
-
-	ret = fwrite (data, 1, len, f->fp);
-	f->pos += ret;
-}
-
+typedef struct _VteFileStream {
+	VteStream parent;
 
-#endif
+	_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. */
 
+	// These are used by the buffering layer. TODO: factor out to another struct!!!
+	gsize head_wbuf;
 
-/*
- * VteFileStream: A file-based stream
- */
+	char wbuf[4096];  // TODO use actual block size, or a symbolic constant!!!
+	gsize wbuf_len;
 
-typedef struct _VteFileStream {
-	VteStream parent;
+	char rbuf[4096];
+	gsize rbuf_offset;
 
-	/* The first file/offset is for the write head, second is for last page */
-	_file_t file[2];
-	gsize offset[2];
-	gsize head;
 } VteFileStream;
+#define VTE_FILE_STREAM_SEGMENTS(s) ((s)->state == 4 ? 2 : (s)->state)
 
 typedef VteStreamClass VteFileStreamClass;
 
@@ -349,11 +256,16 @@ static GType _vte_file_stream_get_type (void);
 
 G_DEFINE_TYPE (VteFileStream, _vte_file_stream, VTE_TYPE_STREAM)
 
+/*
+ * Functions implementing the tricky file layout described above; without any
+ * buffering.
+ */
+
 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 +279,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 +304,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_file0 (stream);
+	_vte_file_stream_ensure_file (stream);
 
-	_file_write (&stream->file[0], data, len, stream->head - stream->offset[0]);
-	stream->head += len;
+	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;
+	}
+
+	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;
+	}
+
+	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,70 +360,253 @@ _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;
 }
 
+/*
+ * 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_swap_fds (VteFileStream *stream)
+_vte_file_stream_truncate (VteStream *astream, gsize offset)
 {
-	_file_t f;
+	VteFileStream *stream = (VteFileStream *) astream;
+	int last_segment;
+
+	g_assert(offset >= stream->segment[0].st_tail);
+	g_assert(offset <= stream->head);
+
+	if (G_UNLIKELY (offset == stream->segment[0].st_tail)) {
+		_vte_file_stream_reset (astream, offset);
+		return;
+	}
 
-	f = stream->file[0]; stream->file[0] = stream->file[1]; stream->file[1] = f;
+	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_truncate (VteStream *astream, gsize offset)
+_vte_file_stream_advance_tail (VteStream *astream, gsize offset)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
 
-	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->head)) {
+		_vte_file_stream_reset (astream, offset);
+		return;
 	}
 
-	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]);
+	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;
+			}
+		}
 	}
+}
+
+#if 0
+static gsize
+_vte_file_stream_head (VteStream *astream)
+{
+	VteFileStream *stream = (VteFileStream *) astream;
 
-	stream->head = offset;
+	return stream->head;
 }
+#endif
+
+
+/*
+ * Functions that implement buffering/caching on top of the previous layout.
+ * This offers the same API as the non-caching counterpart. These methods
+ * always use aligned 4kB blocks when talking to the underlying non-caching
+ * methods.
+ */
 
 static void
-_vte_file_stream_advance_tail (VteStream *astream, gsize offset)
+_vte_file_stream_buffered_reset (VteStream *astream, gsize offset)
+{
+	VteFileStream *stream = (VteFileStream *) astream;
+
+	_vte_file_stream_reset (astream, offset);
+	stream->head_wbuf = offset;
+	stream->wbuf_len = 0;
+	stream->rbuf_offset = 1;  /* Aligned to multiple of 4096, hence 1 never matches, i.e. we'll get cache miss */
+}
+
+static void
+_vte_file_stream_buffered_append (VteStream *astream, const char *data, gsize len)
+{
+	VteFileStream *stream = (VteFileStream *) astream;
+
+	stream->head_wbuf += len;
+	while (len) {
+		gsize l = MIN(4096 - stream->wbuf_len, len);
+		memcpy(stream->wbuf + stream->wbuf_len, data, l);
+		stream->wbuf_len += l; data += l; len -= l;
+		if (stream->wbuf_len == 4096) {
+			_vte_file_stream_append (astream, stream->wbuf, 4096);
+			stream->wbuf_len = 0;
+		}
+	}
+}
+
+static gboolean
+_vte_file_stream_buffered_read (VteStream *astream, gsize offset, char *data, gsize len)
 {
 	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]);
+	// TODO need to assert that offset is at least the (non-4K-aligned) tail offset.
+
+	while (len && offset < stream->head) {
+		gsize l = MIN(4096 - offset % 4096, len);
+		gsize offset_aligned = offset / 4096 * 4096;
+		if (offset_aligned != stream->rbuf_offset) {
+			gboolean ret = _vte_file_stream_read (astream, offset_aligned, stream->rbuf, 4096);
+			g_assert (ret == TRUE);  // TODO ???
+			stream->rbuf_offset = offset_aligned;
+		}
+		memcpy(data, stream->rbuf + offset % 4096, l);
+		offset += l; data += l; len -= l;
 	}
+	if (len) {
+		g_assert(offset % 4096 + len <= stream->wbuf_len);
+		memcpy(data, stream->wbuf + offset % 4096, len);
+	}
+	return TRUE;
+}
+
+static void
+_vte_file_stream_buffered_truncate (VteStream *astream, gsize offset)
+{
+	VteFileStream *stream = (VteFileStream *) astream;
+
+	g_assert (offset <= stream->head_wbuf);
+
+	if (offset < stream->head) {
+		/* Truncating goes back to the part that we've written to the
+		 * file. For simplicity (since this is a very rare, user
+		 * initiated event - the window is made taller) go for the
+		 * simplest local hack here that allows to leave the rest of
+		 * the code intact, that is, read back the new partial last
+		 * block to the write cache. */
+		gsize offset_aligned = offset / 4096 * 4096;
+		gboolean ret = _vte_file_stream_read (astream, offset_aligned, stream->wbuf, 4096);
+		g_assert (ret == TRUE);  // TODO ???
+		_vte_file_stream_truncate (astream, offset_aligned);
+
+		if (stream->rbuf_offset >= offset_aligned) {
+			/* Invalidate the read cache. */
+			stream->rbuf_offset = 1;
+		}
+	}
+	stream->wbuf_len = offset % 4096;
+	stream->head_wbuf = offset;
+}
+
+static void
+_vte_file_stream_buffered_advance_tail (VteStream *astream, gsize offset)
+{
+	VteFileStream *stream = (VteFileStream *) astream;
+
+	if (offset < 4096) return;  // XXX
+	offset = offset / 4096 * 4096 - 4096;  // TODO why is it faster with that extra "-4096"?... because the stream
+	  // doesn't become empty and so we don't call ftruncate
+	if (offset < stream->segment[0].st_tail) return;
+
+	_vte_file_stream_advance_tail (astream, offset);
 }
 
 static gsize
-_vte_file_stream_head (VteStream *astream)
+_vte_file_stream_buffered_head (VteStream *astream)
 {
 	VteFileStream *stream = (VteFileStream *) astream;
 
-	return stream->head;
+	return stream->head_wbuf;
 }
 
+
 static void
 _vte_file_stream_class_init (VteFileStreamClass *klass)
 {
@@ -487,10 +614,10 @@ _vte_file_stream_class_init (VteFileStreamClass *klass)
 
 	gobject_class->finalize = _vte_file_stream_finalize;
 
-	klass->reset = _vte_file_stream_reset;
-	klass->append = _vte_file_stream_append;
-	klass->read = _vte_file_stream_read;
-	klass->truncate = _vte_file_stream_truncate;
-	klass->advance_tail = _vte_file_stream_advance_tail;
-	klass->head = _vte_file_stream_head;
+	klass->reset = _vte_file_stream_buffered_reset;
+	klass->append = _vte_file_stream_buffered_append;
+	klass->read = _vte_file_stream_buffered_read;
+	klass->truncate = _vte_file_stream_buffered_truncate;
+	klass->advance_tail = _vte_file_stream_buffered_advance_tail;
+	klass->head = _vte_file_stream_buffered_head;
 }
