Initial code for metadata store

This adds a mmap based metadata store for NFS-safe highly
efficient desktop-wide metadata lookup and store.

12 files changed, 3086 insertions, 0 deletions

diff --git a/Makefile.am b/Makefile.am
index e9096fdd..d7297823 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -2,6 +2,7 @@ NULL =
 
 SUBDIRS = \
 	common \
+	metadata \
 	client \
 	daemon \
 	monitor \
diff --git a/configure.ac b/configure.ac
index 6137c8ef..0caf9bd1 100644
--- a/configure.ac
+++ b/configure.ac
@@ -154,6 +154,17 @@ if test "x$enable_avahi" != "xno"; then
 	AC_SUBST(AVAHI_LIBS)
 fi
 
+dnl ************************
+dnl *** Check for libXML ***
+dnl ************************
+PKG_CHECK_MODULES(LIBXML, libxml-2.0,
+	[AM_CONDITIONAL(HAVE_LIBXML, true)
+	AC_DEFINE(HAVE_LIBXML, [], [Set if we have libxml])]
+	msg_libxml=yes,
+        [AM_CONDITIONAL(HAVE_LIBXML, false)])
+AC_SUBST(LIBXML_CFLAGS)
+AC_SUBST(LIBXML_LIBS)
+
 dnl **********************
 dnl *** Check for FUSE ***
 dnl **********************
@@ -577,6 +588,7 @@ AC_OUTPUT([
 Makefile
 common/Makefile
 client/Makefile
+metadata/Makefile
 daemon/trashlib/Makefile
 daemon/Makefile
 monitor/Makefile
diff --git a/metadata/.gitignore b/metadata/.gitignore
new file mode 100644
index 00000000..e06c8b1f
--- /dev/null
+++ b/metadata/.gitignore
@@ -0,0 +1,4 @@
+convert-nautilus-metadata
+meta-get
+meta-ls
+meta-set
diff --git a/metadata/Makefile.am b/metadata/Makefile.am
new file mode 100644
index 00000000..151f842c
--- /dev/null
+++ b/metadata/Makefile.am
@@ -0,0 +1,29 @@
+NULL =
+
+noinst_LTLIBRARIES=libmetadata.la
+
+APPS = 	\
+	$(NULL)
+
+if HAVE_LIBXML
+APPS += convert-nautilus-metadata
+endif
+
+noinst_PROGRAMS = $(APPS)
+
+
+INCLUDES = -I$(top_srcdir) -I$(top_srcdir)/gvfs \
+	$(LIBXML_CFLAGS) $(GLIB_CFLAGS) $(DBUS_CFLAGS) \
+	-DG_LOG_DOMAIN=\"GVFS\" -DG_DISABLE_DEPRECATED \
+	-DDBUS_API_SUBJECT_TO_CHANGE
+
+libmetadata_la_SOURCES = 		\
+	metatree.c metatree.h		\
+	metabuilder.c metabuilder.h 	\
+	crc32.c crc32.h			\
+	$(NULL)
+
+libmetadata_la_LIBADD = $(GLIB_LIBS)
+
+convert_nautilus_metadata_LDADD = libmetadata.la $(LIBXML_LIBS)
+convert_nautilus_metadata_SOURCES = metadata-nautilus.c
diff --git a/metadata/crc32.c b/metadata/crc32.c
new file mode 100644
index 00000000..5eb64df2
--- /dev/null
+++ b/metadata/crc32.c
@@ -0,0 +1,95 @@
+/*
+ * Copyright © 2002, 2003 Sun Microsystems, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of Sun Microsystems, Inc. nor the names of
+ *    contributors may be used to endorse or promote products derived from
+ *    this software without specific prior written permission.
+ *
+ * This software is provided "AS IS," without a warranty of any kind.
+ *
+ * ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
+ * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
+ * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED.
+ * SUN AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES OR
+ * LIABILITIES SUFFERED BY LICENSEE AS A RESULT OF OR RELATING TO USE,
+ * MODIFICATION OR DISTRIBUTION OF THE SOFTWARE OR ITS DERIVATIVES.
+ * IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE,
+ * PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
+ * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE
+ * THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE
+ * SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ *
+ */
+
+/* $Id$ */
+/* @(#)crc32.c 1.5 03/01/08 SMI */
+
+/*
+ *
+ * @file crc32.c
+ * @brief CRC-32 calculation function
+ * @author Alexander Gelfenbain
+ *
+ */
+
+#include "crc32.h"
+
+static const guint32 crcTable[256] = {
+  0x00000000UL, 0x77073096UL, 0xEE0E612CUL, 0x990951BAUL, 0x076DC419UL, 0x706AF48FUL, 0xE963A535UL, 0x9E6495A3UL,
+  0x0EDB8832UL, 0x79DCB8A4UL, 0xE0D5E91EUL, 0x97D2D988UL, 0x09B64C2BUL, 0x7EB17CBDUL, 0xE7B82D07UL, 0x90BF1D91UL,
+  0x1DB71064UL, 0x6AB020F2UL, 0xF3B97148UL, 0x84BE41DEUL, 0x1ADAD47DUL, 0x6DDDE4EBUL, 0xF4D4B551UL, 0x83D385C7UL,
+  0x136C9856UL, 0x646BA8C0UL, 0xFD62F97AUL, 0x8A65C9ECUL, 0x14015C4FUL, 0x63066CD9UL, 0xFA0F3D63UL, 0x8D080DF5UL,
+  0x3B6E20C8UL, 0x4C69105EUL, 0xD56041E4UL, 0xA2677172UL, 0x3C03E4D1UL, 0x4B04D447UL, 0xD20D85FDUL, 0xA50AB56BUL,
+  0x35B5A8FAUL, 0x42B2986CUL, 0xDBBBC9D6UL, 0xACBCF940UL, 0x32D86CE3UL, 0x45DF5C75UL, 0xDCD60DCFUL, 0xABD13D59UL,
+  0x26D930ACUL, 0x51DE003AUL, 0xC8D75180UL, 0xBFD06116UL, 0x21B4F4B5UL, 0x56B3C423UL, 0xCFBA9599UL, 0xB8BDA50FUL,
+  0x2802B89EUL, 0x5F058808UL, 0xC60CD9B2UL, 0xB10BE924UL, 0x2F6F7C87UL, 0x58684C11UL, 0xC1611DABUL, 0xB6662D3DUL,
+  0x76DC4190UL, 0x01DB7106UL, 0x98D220BCUL, 0xEFD5102AUL, 0x71B18589UL, 0x06B6B51FUL, 0x9FBFE4A5UL, 0xE8B8D433UL,
+  0x7807C9A2UL, 0x0F00F934UL, 0x9609A88EUL, 0xE10E9818UL, 0x7F6A0DBBUL, 0x086D3D2DUL, 0x91646C97UL, 0xE6635C01UL,
+  0x6B6B51F4UL, 0x1C6C6162UL, 0x856530D8UL, 0xF262004EUL, 0x6C0695EDUL, 0x1B01A57BUL, 0x8208F4C1UL, 0xF50FC457UL,
+  0x65B0D9C6UL, 0x12B7E950UL, 0x8BBEB8EAUL, 0xFCB9887CUL, 0x62DD1DDFUL, 0x15DA2D49UL, 0x8CD37CF3UL, 0xFBD44C65UL,
+  0x4DB26158UL, 0x3AB551CEUL, 0xA3BC0074UL, 0xD4BB30E2UL, 0x4ADFA541UL, 0x3DD895D7UL, 0xA4D1C46DUL, 0xD3D6F4FBUL,
+  0x4369E96AUL, 0x346ED9FCUL, 0xAD678846UL, 0xDA60B8D0UL, 0x44042D73UL, 0x33031DE5UL, 0xAA0A4C5FUL, 0xDD0D7CC9UL,
+  0x5005713CUL, 0x270241AAUL, 0xBE0B1010UL, 0xC90C2086UL, 0x5768B525UL, 0x206F85B3UL, 0xB966D409UL, 0xCE61E49FUL,
+  0x5EDEF90EUL, 0x29D9C998UL, 0xB0D09822UL, 0xC7D7A8B4UL, 0x59B33D17UL, 0x2EB40D81UL, 0xB7BD5C3BUL, 0xC0BA6CADUL,
+  0xEDB88320UL, 0x9ABFB3B6UL, 0x03B6E20CUL, 0x74B1D29AUL, 0xEAD54739UL, 0x9DD277AFUL, 0x04DB2615UL, 0x73DC1683UL,
+  0xE3630B12UL, 0x94643B84UL, 0x0D6D6A3EUL, 0x7A6A5AA8UL, 0xE40ECF0BUL, 0x9309FF9DUL, 0x0A00AE27UL, 0x7D079EB1UL,
+  0xF00F9344UL, 0x8708A3D2UL, 0x1E01F268UL, 0x6906C2FEUL, 0xF762575DUL, 0x806567CBUL, 0x196C3671UL, 0x6E6B06E7UL,
+  0xFED41B76UL, 0x89D32BE0UL, 0x10DA7A5AUL, 0x67DD4ACCUL, 0xF9B9DF6FUL, 0x8EBEEFF9UL, 0x17B7BE43UL, 0x60B08ED5UL,
+  0xD6D6A3E8UL, 0xA1D1937EUL, 0x38D8C2C4UL, 0x4FDFF252UL, 0xD1BB67F1UL, 0xA6BC5767UL, 0x3FB506DDUL, 0x48B2364BUL,
+  0xD80D2BDAUL, 0xAF0A1B4CUL, 0x36034AF6UL, 0x41047A60UL, 0xDF60EFC3UL, 0xA867DF55UL, 0x316E8EEFUL, 0x4669BE79UL,
+  0xCB61B38CUL, 0xBC66831AUL, 0x256FD2A0UL, 0x5268E236UL, 0xCC0C7795UL, 0xBB0B4703UL, 0x220216B9UL, 0x5505262FUL,
+  0xC5BA3BBEUL, 0xB2BD0B28UL, 0x2BB45A92UL, 0x5CB36A04UL, 0xC2D7FFA7UL, 0xB5D0CF31UL, 0x2CD99E8BUL, 0x5BDEAE1DUL,
+  0x9B64C2B0UL, 0xEC63F226UL, 0x756AA39CUL, 0x026D930AUL, 0x9C0906A9UL, 0xEB0E363FUL, 0x72076785UL, 0x05005713UL,
+  0x95BF4A82UL, 0xE2B87A14UL, 0x7BB12BAEUL, 0x0CB61B38UL, 0x92D28E9BUL, 0xE5D5BE0DUL, 0x7CDCEFB7UL, 0x0BDBDF21UL,
+  0x86D3D2D4UL, 0xF1D4E242UL, 0x68DDB3F8UL, 0x1FDA836EUL, 0x81BE16CDUL, 0xF6B9265BUL, 0x6FB077E1UL, 0x18B74777UL,
+  0x88085AE6UL, 0xFF0F6A70UL, 0x66063BCAUL, 0x11010B5CUL, 0x8F659EFFUL, 0xF862AE69UL, 0x616BFFD3UL, 0x166CCF45UL,
+  0xA00AE278UL, 0xD70DD2EEUL, 0x4E048354UL, 0x3903B3C2UL, 0xA7672661UL, 0xD06016F7UL, 0x4969474DUL, 0x3E6E77DBUL,
+  0xAED16A4AUL, 0xD9D65ADCUL, 0x40DF0B66UL, 0x37D83BF0UL, 0xA9BCAE53UL, 0xDEBB9EC5UL, 0x47B2CF7FUL, 0x30B5FFE9UL,
+  0xBDBDF21CUL, 0xCABAC28AUL, 0x53B39330UL, 0x24B4A3A6UL, 0xBAD03605UL, 0xCDD70693UL, 0x54DE5729UL, 0x23D967BFUL,
+  0xB3667A2EUL, 0xC4614AB8UL, 0x5D681B02UL, 0x2A6F2B94UL, 0xB40BBE37UL, 0xC30C8EA1UL, 0x5A05DF1BUL, 0x2D02EF8DUL
+};
+
+guint32
+crc32 (const void *ptr, size_t len)
+{
+  guint32 crc = 0xFFFFFFFF;
+  const guint8 *bp = (const guint8 *) ptr;
+  size_t i;
+
+  for (i=0; i<len; i++)
+    crc = crcTable[(crc ^ bp[i]) & 0xFF] ^ (crc >> 8);
+
+  return crc ^ 0xFFFFFFFF;
+}
diff --git a/metadata/crc32.h b/metadata/crc32.h
new file mode 100644
index 00000000..2a820bda
--- /dev/null
+++ b/metadata/crc32.h
@@ -0,0 +1,49 @@
+/*
+ * Copyright © 2002, 2003 Sun Microsystems, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * 3. Neither the name of Sun Microsystems, Inc. nor the names of
+ *    contributors may be used to endorse or promote products derived from
+ *    this software without specific prior written permission.
+ *
+ * This software is provided "AS IS," without a warranty of any kind.
+ *
+ * ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES,
+ * INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
+ * PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED.
+ * SUN AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES OR
+ * LIABILITIES SUFFERED BY LICENSEE AS A RESULT OF OR RELATING TO USE,
+ * MODIFICATION OR DISTRIBUTION OF THE SOFTWARE OR ITS DERIVATIVES.
+ * IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST REVENUE,
+ * PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
+ * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE
+ * THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE
+ * SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
+ *
+ */
+
+/* $Id$ */
+/* @(#)crc32.h 1.6 03/01/08 SMI */
+
+/*
+ *
+ * @file crc32.h
+ * @brief CRC-32 calculation function
+ * @author Alexander Gelfenbain
+ *
+ */
+
+#include <glib.h>
+
+guint32 crc32(const void *ptr, size_t len);
diff --git a/metadata/file-format.txt b/metadata/file-format.txt
new file mode 100644
index 00000000..dd289bcc
--- /dev/null
+++ b/metadata/file-format.txt
@@ -0,0 +1,109 @@
+Tree file:
+
+Generic:
+Breath-first stored, first tree, then data
+offsets and sizes are uint32
+time_t are uint32 with base stored in header
+data stored in big endian
+non-string blocks padded to 32bit
+all key names and values are utf8, without zeros
+filenames are byte strings
+
+
+Detailed:
+magic
+file type version
+
+guint32 rotated # != 0 => new file has been written, changed at runtime
+guint32 random_tag
+offset to root
+offset to keywords
+gint64 time_t base (other time_ts stored as offsets)
+
+keywords:
+n_keywords
+array of offset to keywords, sorted by keyword
+string block for keywords
+
+root dirent:
+offset to name ("/")
+offset to children for root
+offset to root metadata
+time_t last_change for root metadata
+
+children:
+Each dir in breath-first order:
+  int num_children
+  children, array of: (sorted by name)
+    offset name
+    offset children
+    offset metadata
+    time_t last_change_metadata
+  string block for names:
+    zero terminated strings
+
+metadata:
+each metadata block: (in breath first order)
+  int num_keys
+  keys, array of: sorted by keyword
+    guint32 keyword | high bit set => is_list
+    offset value (pointer to string, or array of strings)
+  block of string arrays for values
+for each directory, string block of values for metadata in dir
+
+----------------------------------------
+------------- Journal ------------------
+----------------------------------------
+
+Fixed size, rotated when full
+Array of operations, each with a checksum
+Readers handle only up to first non-ok checksum
+Writer periodically rewrites stable tree and creates new journal
+
+strings are stored as plain zero terminated c-strings
+
+Updates to stable:
+1 block writes
+2 write new stable to tmp file, w/ fsync
+3 create new empty journal (name based on random_tag)
+4 rename new stable over old
+5 set rotated to true in old (via open fd)
+6 sync old fd
+7 remove old journal
+8 re-enable writes
+
+When opening a stable file + journal there is a race where we can open the
+old tree, but then the old journal is removed before we read it. To
+handle this, on open you must always re-check "rotated" after the
+journal has been opened (or failed to open) and verified
+
+Journal file header:
+char[6] magic
+char[2] file type version
+guint32 random_tag
+guint32 file_size # Must be same as file size
+guint32 num_entries
+
+Journal entry:
+
+guint32 entry_size # Must verify wrt file size (includes entry_size, etc)
+guint32 crc32 # crc32 of following data, including padding and last size
+guint64 mtime
+byte operation type (set: 0, set_list: 1: unset: 2, move: 3, copy: 4)
+cstring path # target if copy/move
+ set:
+  cstring key
+  cstring value
+ set_list:
+  cstring key
+  <zero padding to even 32bit address>
+  guint32 n_values
+  cstring value
+ uset:
+  cstring key
+ copy: (overwrites all destination data)
+  cstring source_path
+ remove:
+  <nothing>
+<zero padding to even 32bit address>
+guint32 entry_size_end # Must be same as entry_size, for reverse skipping
diff --git a/metadata/metabuilder.c b/metadata/metabuilder.c
new file mode 100644
index 00000000..85b7a835
--- /dev/null
+++ b/metadata/metabuilder.c
@@ -0,0 +1,816 @@
+#include "metabuilder.h"
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <string.h>
+#include <unistd.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <glib/gstdio.h>
+
+#define MAJOR_VERSION 1
+#define MINOR_VERSION 0
+#define MAJOR_JOURNAL_VERSION 1
+#define MINOR_JOURNAL_VERSION 0
+#define NEW_JOURNAL_SIZE (32*1024)
+
+#define RANDOM_TAG_OFFSET 12
+#define ROTATED_OFFSET 8
+
+MetaBuilder *
+meta_builder_new (void)
+{
+  MetaBuilder *builder;
+
+  builder = g_new0 (MetaBuilder, 1);
+  builder->root = metafile_new ("/", NULL);
+
+  return builder;
+}
+
+static gint
+compare_metafile (gconstpointer  a,
+		  gconstpointer  b)
+{
+  const MetaFile *aa, *bb;
+
+  aa = a;
+  bb = b;
+  return strcmp (aa->name, bb->name);
+}
+
+static gint
+compare_metadata (gconstpointer  a,
+		  gconstpointer  b)
+{
+  const MetaData *aa, *bb;
+
+  aa = a;
+  bb = b;
+  return strcmp (aa->key, bb->key);
+}
+
+MetaFile *
+metafile_new (const char *name,
+	      MetaFile *parent)
+{
+  MetaFile *f;
+
+  f = g_new0 (MetaFile, 1);
+  f->name = g_strdup (name);
+  if (parent)
+    parent->children = g_list_insert_sorted (parent->children, f,
+					     compare_metafile);
+
+  return f;
+}
+
+MetaFile *
+metafile_lookup_child (MetaFile *metafile,
+		       const char *name,
+		       gboolean create)
+{
+  GList *l;
+  MetaFile *child;
+
+  for (l = metafile->children; l != NULL; l = l->next)
+    {
+      child = l->data;
+      if (strcmp (child->name, name) == 0)
+	return child;
+    }
+  child = NULL;
+  if (create)
+    child = metafile_new (name, metafile);
+  return child;
+}
+
+MetaFile *
+meta_builder_lookup (MetaBuilder *builder,
+		     const char *path,
+		     gboolean create)
+{
+  MetaFile *f;
+  const char *element_start;
+  char *element;
+
+  f = builder->root;
+  while (f)
+    {
+      while (*path == '/')
+	path++;
+
+      if (*path == 0)
+	break; /* Found it! */
+
+      element_start = path;
+      while (*path != 0 && *path != '/')
+	path++;
+      element = g_strndup (element_start, path - element_start);
+
+      f = metafile_lookup_child (f, element, create);
+      g_free (element);
+    }
+  return f;
+}
+
+static MetaData *
+metadata_new (const char *key,
+	      MetaFile *file)
+{
+  MetaData *data;
+
+  data = g_new0 (MetaData, 1);
+  data->key = g_strdup (key);
+
+  if (file)
+    file->data = g_list_insert_sorted (file->data, data, compare_metadata);
+
+  return data;
+}
+
+MetaData *
+metafile_key_lookup (MetaFile *file,
+		     const char *key,
+		     gboolean create)
+{
+  GList *l;
+  MetaData *data;
+
+  for (l = file->data; l != NULL; l = l->next)
+    {
+      data = l->data;
+      if (strcmp (data->key, key) == 0)
+	return data;
+    }
+
+  data = NULL;
+  if (create)
+    data = metadata_new (key, file);
+
+  return data;
+}
+
+static void
+metadata_clear (MetaData *data)
+{
+  if (data->is_list)
+    {
+      g_list_foreach (data->values, (GFunc)g_free, NULL);
+      g_list_free (data->values);
+      data->values = NULL;
+    }
+  else
+    {
+      g_free (data->value);
+    }
+}
+
+void
+metafile_key_set_value (MetaFile *metafile,
+			const char *key,
+			const char *value)
+{
+  MetaData *data;
+
+  data = metafile_key_lookup (metafile, key, TRUE);
+  metadata_clear (data);
+  data->is_list = FALSE;
+  data->value = g_strdup (value);
+}
+
+void
+metafile_key_list_add (MetaFile *metafile,
+		       const char *key,
+		       const char *value)
+{
+  MetaData *data;
+
+  data = metafile_key_lookup (metafile, key, TRUE);
+  if (!data->is_list)
+    {
+      metadata_clear (data);
+      data->is_list = TRUE;
+    }
+
+  data->values = g_list_append (data->values, g_strdup (value));
+}
+
+static void
+metafile_print (MetaFile *file, int indent, char *parent)
+{
+  GList *l, *v;
+  MetaData *data;
+  char *dir;
+
+  if (parent)
+    dir = g_strconcat (parent, "/", file->name, NULL);
+  else
+    dir = g_strdup ("");
+
+  if (parent)
+    {
+      g_print ("%*s%s\n", indent, "", dir);
+      indent += 3;
+    }
+
+  for (l = file->data; l != NULL; l = l->next)
+    {
+      data = l->data;
+      g_print ("%*s%s=", indent, "", data->key);
+      if (data->is_list)
+	{
+	  for (v = data->values; v != NULL; v = v->next)
+	    {
+	      g_print ("%s", (char *)v->data);
+	      if (v->next != NULL)
+		g_print (", ");
+	    }
+	}
+      else
+	g_print ("%s", data->value);
+      g_print ("\n");
+    }
+  for (l = file->children; l != NULL; l = l->next)
+    {
+      metafile_print (l->data, indent, dir);
+    }
+
+  g_free (dir);
+}
+
+void
+meta_builder_print (MetaBuilder *builder)
+{
+  metafile_print (builder->root, 0, NULL);
+}
+
+static void
+set_uint32 (GString *s, guint32 offset, guint32 val)
+{
+  union {
+    guint32 as_int;
+    char as_bytes[4];
+  } u;
+
+  u.as_int = GUINT32_TO_BE (val);
+  memcpy (s->str + offset, u.as_bytes, 4);
+}
+
+static GString *
+append_uint32 (GString *s, guint32 val, guint32 *offset)
+{
+  union {
+    guint32 as_int;
+    char as_bytes[4];
+  } u;
+
+  if (offset)
+    *offset = s->len;
+
+  u.as_int = GUINT32_TO_BE (val);
+
+  g_string_append_len (s, u.as_bytes, 4);
+
+  return s;
+}
+
+static GString *
+append_time_t (GString *s, gint64 val, MetaBuilder *builder)
+{
+  guint32 offset;
+
+  if (val == 0)
+    offset = 0;
+  else if (val <= builder->time_t_base)
+    offset = 1;
+  else
+    offset = val - builder->time_t_base;
+
+  return append_uint32 (s, offset, NULL);
+}
+
+static GString *
+append_int64 (GString *s, gint64 val)
+{
+  union {
+    gint64 as_int;
+    char as_bytes[8];
+  } u;
+
+  u.as_int = GINT64_TO_BE (val);
+
+  g_string_append_len (s, u.as_bytes, 8);
+
+  return s;
+}
+
+static void
+metafile_collect_times (MetaFile *file,
+			gint64 *time_t_min,
+			gint64 *time_t_max)
+{
+  GList *l;
+  MetaFile *child;
+
+  if (*time_t_min == 0)
+    *time_t_min = file->last_changed;
+  else if (file->last_changed != 0 && file->last_changed < *time_t_min)
+    *time_t_min = file->last_changed;
+
+  if (file->last_changed > *time_t_max)
+    *time_t_max = file->last_changed;
+
+  for (l = file->children; l != NULL; l = l->next)
+    {
+      child = l->data;
+      metafile_collect_times (child, time_t_min, time_t_max);
+    }
+}
+
+static void
+metafile_collect_keywords (MetaFile *file,
+			   GHashTable *hash)
+{
+  GList *l;
+  MetaData *data;
+  MetaFile *child;
+
+  file->metadata_pointer = 0;
+  file->children_pointer = 0;
+
+  for (l = file->data; l != NULL; l = l->next)
+    {
+      data = l->data;
+      g_hash_table_insert (hash, data->key, GINT_TO_POINTER (1));
+    }
+
+  for (l = file->children; l != NULL; l = l->next)
+    {
+      child = l->data;
+      metafile_collect_keywords (child, hash);
+    }
+}
+
+GHashTable *
+string_block_begin (void)
+{
+  return g_hash_table_new (g_str_hash, g_str_equal);
+}
+
+static void
+append_string (GString *out,
+	       const char *string,
+	       GHashTable *string_block)
+{
+  guint32 offset;
+  GList *offsets;
+
+  append_uint32 (out, 0xdeaddead, &offset);
+
+  if (g_hash_table_lookup_extended (string_block,
+				    string, NULL,
+				    (gpointer *)&offsets))
+    {
+      offsets = g_list_append (offsets, GUINT_TO_POINTER (offset));
+    }
+  else
+    {
+      g_hash_table_insert (string_block,
+			   (char *)string,
+			   g_list_prepend (NULL, GUINT_TO_POINTER (offset)));
+    }
+}
+
+static void
+string_block_end (GString *out,
+		  GHashTable *string_block)
+{
+  char *string;
+  GList *offsets, *l;
+  guint32 string_offset, offset;
+  GHashTableIter iter;
+
+  g_hash_table_iter_init (&iter, string_block);
+  while (g_hash_table_iter_next (&iter,
+				 (gpointer *)&string,
+				 (gpointer *)&offsets))
+    {
+      string_offset = out->len;
+      g_string_append_len (out, string, strlen (string) + 1);
+      for (l = offsets; l != NULL; l = l->next)
+	{
+	  offset = GPOINTER_TO_UINT (l->data);
+	  set_uint32 (out, offset, string_offset);
+	}
+    }
+
+  g_hash_table_destroy (string_block);
+
+  /* Pad to 32bit */
+  while (out->len % 4 != 0)
+    g_string_append_c (out, 0);
+}
+
+static void
+write_children (GString *out,
+		MetaBuilder *builder)
+{
+  GHashTable *strings;
+  MetaFile *child, *file;
+  GList *l;
+  GList *files;
+
+  files = g_list_prepend (NULL, builder->root);
+
+  while (files != NULL)
+    {
+      file = files->data;
+      files = g_list_remove_link (files, files);
+
+      if (file->children == NULL)
+	continue; /* No children, skip file */
+
+      strings = string_block_begin ();
+
+      if (file->children_pointer != 0)
+	set_uint32 (out, file->children_pointer, out->len);
+
+      append_uint32 (out, g_list_length (file->children), NULL);
+
+      for (l = file->children; l != NULL; l = l->next)
+	{
+	  child = l->data;
+
+	  /* No mtime, children or metadata, no need for this
+	     to be in the file */
+	  if (child->last_changed == 0 &&
+	      child->children == NULL &&
+	      child->data == NULL)
+	    continue;
+
+	  append_string (out, child->name, strings);
+	  append_uint32 (out, 0, &child->children_pointer);
+	  append_uint32 (out, 0, &child->metadata_pointer);
+	  append_time_t (out, child->last_changed, builder);
+
+	  if (file->children)
+	    files = g_list_append (files, child);
+	}
+
+      string_block_end (out, strings);
+    }
+}
+
+static void
+write_metadata_for_file (GString *out,
+			 MetaFile *file,
+			 GHashTable *strings,
+			 GHashTable *key_hash)
+{
+  GList *l;
+  MetaData *data;
+  guint32 key;
+
+  g_assert (file->metadata_pointer != 0);
+  set_uint32 (out, file->metadata_pointer, out->len);
+
+  append_uint32 (out, g_list_length (file->data), NULL);
+
+  for (l = file->data; l != NULL; l = l->next)
+    {
+      data = l->data;
+
+      if (data->is_list)
+	continue; /* TODO: we skip this for now */
+
+      key = GPOINTER_TO_UINT (g_hash_table_lookup (key_hash, data->key));
+      append_uint32 (out, key, NULL);
+      append_string (out, data->value, strings);
+    }
+}
+
+static void
+write_metadata (GString *out,
+		MetaBuilder *builder,
+		GHashTable *key_hash)
+{
+  GHashTable *strings;
+  MetaFile *child, *file;
+  GList *l;
+  GList *files;
+
+  /* Root metadata */
+  if (builder->root->data != NULL)
+    {
+      strings = string_block_begin ();
+      write_metadata_for_file (out, builder->root,
+			       strings, key_hash);
+      string_block_end (out, strings);
+    }
+
+  /* the rest, breadth first with all files in one
+     dir sharing string block */
+  files = g_list_prepend (NULL, builder->root);
+  while (files != NULL)
+    {
+      file = files->data;
+      files = g_list_remove_link (files, files);
+
+      if (file->children == NULL)
+	continue; /* No children, skip file */
+
+      strings = string_block_begin ();
+
+      for (l = file->children; l != NULL; l = l->next)
+	{
+	  child = l->data;
+
+	  if (child->data != NULL)
+	    write_metadata_for_file (out, child,
+				     strings, key_hash);
+
+	  if (child->children != NULL)
+	    files = g_list_append (files, child);
+	}
+
+      string_block_end (out, strings);
+    }
+}
+
+gboolean
+write_all_data_and_close (int fd, char *data, gsize len)
+{
+  gsize written;
+  gboolean res;
+
+  res = FALSE;
+
+  while (len > 0)
+    {
+      written = write (fd, data, len);
+
+      if (written < 0)
+	{
+	  if (errno == EAGAIN)
+	    continue;
+	  goto out;
+	}
+      else if (written == 0)
+	goto out; /* WTH? Don't loop forever*/
+
+      len -= written;
+      data += written;
+    }
+
+  if (fsync (fd) == -1)
+    goto out;
+
+  res = TRUE; /* Succeeded! */
+
+ out:
+  if (close (fd) == -1)
+    res = FALSE;
+
+  return res;
+}
+
+static char *
+get_journal_filename (const char *filename, guint32 random_tag)
+{
+  const char *hexdigits = "0123456789abcdef";
+  char tag[9];
+  int i;
+
+  for (i = 7; i >= 0; i--)
+    {
+      tag[i] = hexdigits[random_tag % 0x10];
+      random_tag >>= 4;
+    }
+
+  tag[8] = 0;
+
+  return g_strconcat (filename, "-", tag, ".log", NULL);
+}
+
+static gboolean
+create_new_journal (const char *filename, guint32 random_tag)
+{
+  char *journal_name;
+  guint32 size_offset;
+  GString *out;
+  gsize pos;
+  gboolean res;
+
+  journal_name = get_journal_filename (filename, random_tag);
+
+  out = g_string_new (NULL);
+
+  /* HEADER */
+  g_string_append_c (out, 0xda);
+  g_string_append_c (out, 0x1a);
+  g_string_append_c (out, 'j');
+  g_string_append_c (out, 'o');
+  g_string_append_c (out, 'u');
+  g_string_append_c (out, 'r');
+
+  /* VERSION */
+  g_string_append_c (out, MAJOR_JOURNAL_VERSION);
+  g_string_append_c (out, MINOR_JOURNAL_VERSION);
+
+  append_uint32 (out, random_tag, NULL);
+  append_uint32 (out, 0, &size_offset);
+  append_uint32 (out, 0, NULL); /* Num entries, none so far */
+
+  pos = out->len;
+
+  g_string_set_size (out, NEW_JOURNAL_SIZE);
+  memset (out->str + pos, 0, out->len - pos);
+
+  set_uint32 (out, size_offset, out->len);
+
+  res = g_file_set_contents (journal_name,
+			     out->str, out->len,
+			     NULL);
+
+  g_free (journal_name);
+  g_string_free (out, TRUE);
+
+  return res;
+}
+
+static GString *
+metadata_create_static (MetaBuilder *builder,
+			guint32 *random_tag_out)
+{
+  GString *out;
+  GHashTable *hash, *key_hash;
+  GHashTableIter iter;
+  char *key;
+  GList *keys, *l;
+  GHashTable *strings;
+  guint32 index;
+  guint32 attributes_pointer;
+  gint64 time_t_min;
+  gint64 time_t_max;
+  guint32 random_tag, root_name;
+
+  out = g_string_new (NULL);
+
+  /* HEADER */
+  g_string_append_c (out, 0xda);
+  g_string_append_c (out, 0x1a);
+  g_string_append_c (out, 'm');
+  g_string_append_c (out, 'e');
+  g_string_append_c (out, 't');
+  g_string_append_c (out, 'a');
+
+  /* VERSION */
+  g_string_append_c (out, MAJOR_VERSION);
+  g_string_append_c (out, MINOR_VERSION);
+
+  append_uint32 (out, 0, NULL); /* Rotated */
+  random_tag = g_random_int ();
+  *random_tag_out = random_tag;
+  append_uint32 (out, random_tag, NULL);
+  append_uint32 (out, 0, &builder->root_pointer);
+  append_uint32 (out, 0, &attributes_pointer);
+
+  time_t_min = 0;
+  time_t_max = 0;
+  metafile_collect_times (builder->root, &time_t_min, &time_t_max);
+
+  /* Store the base as the min value in use minus one so that
+     0 is free to mean "not defined" */
+  time_t_min = time_t_min - 1;
+
+  /* Pick the base as the minimum, unless that leads to
+     a 32bit overflow */
+  if (time_t_max - time_t_min > G_MAXUINT32)
+    time_t_min = time_t_max - G_MAXUINT32;
+  builder->time_t_base = time_t_min;
+  append_int64 (out, builder->time_t_base);
+
+  /* Collect and sort all used keys */
+  hash = g_hash_table_new (g_str_hash, g_str_equal);
+  metafile_collect_keywords (builder->root, hash);
+  g_hash_table_iter_init (&iter, hash);
+  keys = NULL;
+  while (g_hash_table_iter_next (&iter, (gpointer *)&key, NULL))
+    keys = g_list_prepend (keys, key);
+  g_hash_table_destroy (hash);
+  keys = g_list_sort (keys, (GCompareFunc)strcmp);
+
+  /* Write keys to file and collect mapping for keys */
+  set_uint32 (out, attributes_pointer, out->len);
+  key_hash = g_hash_table_new (g_str_hash, g_str_equal);
+  strings = string_block_begin ();
+  append_uint32 (out, g_list_length (keys), NULL);
+  for (l = keys, index = 0; l != NULL; l = l->next, index++)
+    {
+      key = l->data;
+      append_string (out, key, strings);
+      g_hash_table_insert (key_hash, key, GUINT_TO_POINTER (index));
+    }
+  string_block_end (out, strings);
+
+  /* update root pointer */
+  set_uint32 (out, builder->root_pointer, out->len);
+
+  /* Root name */
+  append_uint32 (out, 0, &root_name);
+
+  /* Root child pointer */
+  append_uint32 (out, 0, &builder->root->children_pointer);
+
+  /* Root metadata pointer */
+  append_uint32 (out, 0, &builder->root->metadata_pointer);
+
+  /* Root last changed */
+  append_uint32 (out, builder->root->last_changed, NULL);
+
+  /* Root name */
+  set_uint32 (out, root_name, out->len);
+  g_string_append_len (out, "/", 2);
+
+  /* Pad to 32bit */
+  while (out->len % 4 != 0)
+    g_string_append_c (out, 0);
+
+  write_children (out, builder);
+  write_metadata (out, builder, key_hash);
+
+  g_hash_table_destroy (key_hash);
+
+  return out;
+}
+
+gboolean
+meta_builder_write (MetaBuilder *builder,
+		    const char *filename)
+{
+  GString *out;
+  guint32 random_tag;
+  int fd, fd2;
+  char *tmp_name;
+
+  out = metadata_create_static (builder, &random_tag);
+
+  tmp_name = g_strdup_printf ("%s.XXXXXX", filename);
+  fd = g_mkstemp (tmp_name);
+  if (fd == -1)
+    goto out;
+
+  if (!write_all_data_and_close (fd, out->str, out->len))
+    goto out;
+
+  if (!create_new_journal (filename, random_tag))
+    goto out;
+
+  /* Open old file so we can set it rotated */
+  fd2 = open (filename, O_RDONLY);
+  if (g_rename (tmp_name, filename) == -1)
+    {
+      if (fd2 != -1)
+	close (fd2);
+      goto out;
+    }
+
+  /* Mark old file (if any) as rotated) */
+  if (fd2 != -1)
+    {
+      gboolean have_old_tag;
+      guint32 old_tag;
+      char *old_log;
+      guint32 c = 0xffffffff;
+
+
+      if (lseek(fd2, RANDOM_TAG_OFFSET, SEEK_SET) == RANDOM_TAG_OFFSET &&
+	  read (fd2, &old_tag, 4) == 4)
+	{
+	  have_old_tag = TRUE;
+	  old_tag = GUINT32_FROM_BE (old_tag);
+	}
+
+      if (lseek(fd2, ROTATED_OFFSET, SEEK_SET) == ROTATED_OFFSET)
+	write (fd2, &c, 4);
+      close (fd2);
+
+      if (have_old_tag)
+	{
+	  old_log = get_journal_filename (filename, old_tag);
+	  g_unlink (old_log);
+	  g_free (old_log);
+	}
+    }
+
+  g_string_free (out, TRUE);
+  g_free (tmp_name);
+  return TRUE;
+
+ out:
+  if (fd != -1)
+    g_unlink (tmp_name);
+  g_string_free (out, TRUE);
+  g_free (tmp_name);
+  return FALSE;
+}
diff --git a/metadata/metabuilder.h b/metadata/metabuilder.h
new file mode 100644
index 00000000..18f3aba9
--- /dev/null
+++ b/metadata/metabuilder.h
@@ -0,0 +1,51 @@
+#include <glib.h>
+
+typedef struct _MetaBuilder MetaBuilder;
+typedef struct _MetaFile MetaFile;
+typedef struct _MetaData MetaData;
+
+struct _MetaBuilder {
+  MetaFile *root;
+
+  guint32 root_pointer;
+  gint64 time_t_base;
+};
+
+struct _MetaFile {
+  char *name;
+  GList *children;
+  gint64 last_changed;
+  GList *data;
+
+  guint32 metadata_pointer;
+  guint32 children_pointer;
+};
+
+struct _MetaData {
+  char *key;
+  gboolean is_list;
+  char *value;
+  GList *values;
+};
+
+MetaBuilder *meta_builder_new       (void);
+void         meta_builder_print     (MetaBuilder *builder);
+MetaFile *   meta_builder_lookup    (MetaBuilder *builder,
+				     const char  *path,
+				     gboolean     create);
+gboolean     meta_builder_write     (MetaBuilder *builder,
+				     const char  *filename);
+MetaFile *   metafile_new           (const char  *name,
+				     MetaFile    *parent);
+MetaFile *   metafile_lookup_child  (MetaFile    *metafile,
+				     const char  *name,
+				     gboolean     create);
+MetaData *   metafile_key_lookup    (MetaFile    *file,
+				     const char  *key,
+				     gboolean     create);
+void         metafile_key_set_value (MetaFile    *metafile,
+				     const char  *key,
+				     const char  *value);
+void         metafile_key_list_add  (MetaFile    *metafile,
+				     const char  *key,
+				     const char  *value);
diff --git a/metadata/metadata-nautilus.c b/metadata/metadata-nautilus.c
new file mode 100644
index 00000000..8617f11e
--- /dev/null
+++ b/metadata/metadata-nautilus.c
@@ -0,0 +1,220 @@
+#include <string.h>
+#include "metabuilder.h"
+#include <libxml/tree.h>
+
+static xmlNodePtr
+xml_get_children (xmlNodePtr parent)
+{
+	if (parent == NULL) {
+		return NULL;
+	}
+	return parent->children;
+}
+
+static xmlNodePtr
+xml_get_root_children (xmlDocPtr document)
+{
+	return xml_get_children (xmlDocGetRootElement (document));
+}
+
+
+static char *
+get_uri_from_nautilus_metafile_name (const char *filename)
+{
+  GString *s;
+  char c;
+  char *base_name, *p;
+  int len;
+
+  base_name = g_path_get_basename (filename);
+  len = strlen (base_name);
+  if (len <=  4 ||
+      strcmp (base_name + len - 4, ".xml") != 0)
+    {
+      g_free (base_name);
+      return NULL;
+    }
+  base_name[len-4] = 0;
+
+  s = g_string_new (NULL);
+
+  p = base_name;
+  while (*p)
+    {
+      c = *p++;
+      if (c == '%')
+	{
+	  c =
+	    g_ascii_xdigit_value (p[0]) << 4 |
+	    g_ascii_xdigit_value (p[1]);
+	  p += 2;
+	}
+      g_string_append_c (s, c);
+    }
+  g_free (base_name);
+
+  return g_string_free (s, FALSE);
+}
+
+static void
+parse_xml_node (MetaFile *metafile,
+		xmlNodePtr filenode)
+{
+  xmlChar *data;
+  guint64 timestamp;
+  xmlNodePtr node;
+  xmlAttrPtr attr;
+  xmlChar *property;
+  char *combined_key;
+
+  data = xmlGetProp (filenode, (xmlChar *)"timestamp");
+  if (data)
+    {
+      timestamp = g_ascii_strtoll ((char *)data, NULL, 10);
+      if (timestamp != 0)
+	metafile->last_changed = timestamp;
+    }
+
+  for (attr = filenode->properties; attr != NULL; attr = attr->next)
+    {
+      if (strcmp ((char *)attr->name, "name") == 0 ||
+	  strcmp ((char *)attr->name, "timestamp") == 0)
+	continue;
+
+      property = xmlGetProp (filenode, attr->name);
+      if (property)
+	metafile_key_set_value (metafile, (char *)attr->name, (char *)property);
+      xmlFree (property);
+    }
+
+  for (node = filenode->children; node != NULL; node = node->next)
+    {
+      for (attr = node->properties; attr != NULL; attr = attr->next)
+	{
+	  property = xmlGetProp (node, attr->name);
+	  if (property)
+	    {
+	      combined_key = g_strconcat ((char *)node->name,
+					  "-",
+					  (char *)attr->name,
+					  NULL);
+	      metafile_key_list_add (metafile, combined_key, (char *)property);
+	      g_free (combined_key);
+	    }
+	  xmlFree (property);
+	}
+    }
+}
+
+static void
+parse_xml_file (MetaBuilder *builder,
+		xmlDocPtr xml,
+		char *dir)
+{
+  xmlNodePtr node;
+  xmlChar *name;
+  char *unescaped_name;
+  MetaFile *dir_metafile, *metafile;
+
+  dir_metafile =  meta_builder_lookup (builder, dir, TRUE);
+
+  for (node = xml_get_root_children (xml);
+       node != NULL; node = node->next)
+    {
+      if (strcmp ((char *)node->name, "file") == 0)
+	{
+	  name = xmlGetProp (node, (xmlChar *)"name");
+	  unescaped_name = g_uri_unescape_string ((char *)name, "/");
+	  xmlFree (name);
+
+	  if (strcmp (unescaped_name, ".") == 0)
+	    metafile = dir_metafile;
+	  else
+	    metafile = metafile_lookup_child (dir_metafile, unescaped_name, TRUE);
+
+	  parse_xml_node (metafile, node);
+	  g_free (unescaped_name);
+	}
+    }
+}
+
+static void
+parse_nautilus_file (MetaBuilder *builder,
+		     char *file)
+{
+  char *uri;
+  char *dir;
+  gchar *contents;
+  gsize length;
+  xmlDocPtr xml;
+
+  if (!g_file_get_contents (file, &contents, &length, NULL))
+    {
+      g_print ("failed to load %s\n", file);
+      return;
+    }
+
+  uri = get_uri_from_nautilus_metafile_name (file);
+  if (uri == NULL)
+    {
+      g_free (contents);
+      return;
+    }
+
+  dir = g_filename_from_uri (uri, NULL, NULL);
+  g_free (uri);
+  if (dir == NULL)
+    {
+      g_free (contents);
+      return;
+    }
+
+  xml = xmlParseMemory (contents, length);
+  g_free (contents);
+  if (xml == NULL)
+    return;
+
+  parse_xml_file (builder, xml, dir);
+  xmlFreeDoc (xml);
+}
+
+/*static gboolean recursive = FALSE;*/
+static char *filename = NULL;
+static GOptionEntry entries[] =
+{
+  { "out", 'o', 0, G_OPTION_ARG_FILENAME, &filename, "Output filename", NULL },
+  { NULL }
+};
+
+int
+main (int argc, char *argv[])
+{
+  GOptionContext *context;
+  MetaBuilder *builder;
+  GError *error = NULL;
+  int i;
+
+  context = g_option_context_new ("<nautilus metadata files> - convert nautilus metadata");
+  g_option_context_add_main_entries (context, entries, NULL);
+  if (!g_option_context_parse (context, &argc, &argv, &error))
+    {
+      g_printerr ("option parsing failed: %s\n", error->message);
+      return 1;
+    }
+
+  if (argc < 2)
+    {
+      g_print ("No files specified\n");
+      return 1;
+    }
+
+  builder = meta_builder_new ();
+  for (i = 1; i < argc; i++)
+    parse_nautilus_file (builder, argv[i]);
+  if (filename)
+    meta_builder_write (builder, filename);
+  else
+    meta_builder_print (builder);
+
+  return 0;
+}
diff --git a/metadata/metatree.c b/metadata/metatree.c
new file mode 100644
index 00000000..4aacc82b
--- /dev/null
+++ b/metadata/metatree.c
@@ -0,0 +1,1642 @@
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <fcntl.h>
+#include <string.h>
+#include <unistd.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "metatree.h"
+#include <glib.h>
+#include "crc32.h"
+
+#define MAGIC "\xda\x1ameta"
+#define MAGIC_LEN 6
+#define MAJOR_VERSION 1
+#define MINOR_VERSION 0
+#define JOURNAL_MAGIC "\xda\x1ajour"
+#define JOURNAL_MAGIC_LEN 6
+#define JOURNAL_MAJOR_VERSION 1
+#define JOURNAL_MINOR_VERSION 0
+
+#define KEY_IS_LIST_MASK (1<<31)
+
+typedef enum {
+  JOURNAL_OP_SET_KEY,
+  JOURNAL_OP_SETV_KEY,
+  JOURNAL_OP_UNSET_KEY,
+  JOURNAL_OP_COPY_PATH,
+  JOURNAL_OP_REMOVE_PATH
+} MetaJournalEntryType;
+
+typedef struct {
+  guchar magic[6];
+  guchar major;
+  guchar minor;
+  guint32 rotated;
+  guint32 random_tag;
+  guint32 root;
+  guint32 attributes;
+  guint64 time_t_base;
+} MetaFileHeader;
+
+typedef struct {
+  guint32 name;
+  guint32 children;
+  guint32 metadata;
+  guint32 last_changed;
+} MetaFileDirEnt;
+
+typedef struct {
+  guint32 num_children;
+  MetaFileDirEnt children[1];
+} MetaFileDir;
+
+typedef struct {
+  guint32 key;
+  guint32 value;
+} MetaFileDataEnt;
+
+typedef struct {
+  guint32 num_keys;
+  MetaFileDataEnt keys[1];
+} MetaFileData;
+
+typedef struct {
+  guchar magic[6];
+  guchar major;
+  guchar minor;
+  guint32 random_tag;
+  guint32 file_size;
+  guint32 num_entries;
+} MetaJournalHeader;
+
+typedef struct {
+  guint32 entry_size;
+  guint32 crc32;
+  guint64 mtime;
+  guint8 entry_type;
+  char path[1];
+} MetaJournalEntry;
+
+typedef struct {
+  char *filename;
+  int fd;
+  char *data;
+  gsize len;
+
+  MetaJournalHeader *header;
+  MetaJournalEntry *first_entry;
+  guint last_entry_num;
+  MetaJournalEntry *last_entry;
+
+  gboolean journal_valid; /* True if all entries validated on open */
+} MetaJournal;
+
+struct _MetaTree {
+  char *filename;
+  gboolean for_write;
+
+  int fd;
+  char *data;
+  gsize len;
+
+  guint32 tag;
+  gint64 time_t_base;
+  MetaFileHeader *header;
+  MetaFileDirEnt *root;
+
+  int num_attributes;
+  char **attributes;
+
+  MetaJournal *journal;
+};
+
+static MetaJournal *meta_journal_open (const char  *filename,
+				       gboolean     for_write,
+				       guint32      tag);
+static void         meta_journal_free (MetaJournal *journal);
+
+static gpointer
+verify_block_pointer (MetaTree *tree, guint32 pos, guint32 len)
+{
+  pos = GUINT32_FROM_BE (pos);
+
+  /* Ensure 32bit aligned */
+  if (pos %4 != 0)
+    return NULL;
+
+  if (pos > tree->len)
+    return NULL;
+
+  if (pos + len < pos ||
+      pos + len > tree->len)
+    return NULL;
+
+  return tree->data + pos;
+}
+
+static gpointer
+verify_array_block (MetaTree *tree, guint32 pos, gsize element_size)
+{
+  guint32 *nump, num;
+
+  nump = verify_block_pointer (tree, pos, sizeof (guint32));
+  if (nump == NULL)
+    return NULL;
+
+  num = GUINT32_FROM_BE (*nump);
+
+  return verify_block_pointer (tree, pos, sizeof (guint32) + num * element_size);
+}
+
+static gpointer
+verify_children_block (MetaTree *tree, guint32 pos)
+{
+  return verify_array_block (tree, pos, sizeof (MetaFileDirEnt));
+}
+
+static gpointer
+verify_metadata_block (MetaTree *tree, guint32 pos)
+{
+  return verify_array_block (tree, pos, sizeof (MetaFileDataEnt));
+}
+
+static char *
+verify_string (MetaTree *tree, guint32 pos)
+{
+  char *str, *ptr, *end;
+
+  pos = GUINT32_FROM_BE (pos);
+
+  if (pos > tree->len)
+    return NULL;
+
+  str = ptr = tree->data + pos;
+  end = tree->data + tree->len;
+
+  while (ptr < end && *ptr != 0)
+    ptr++;
+
+  if (ptr == end)
+    return NULL;
+
+  return str;
+}
+
+static void
+meta_tree_clear (MetaTree *tree)
+{
+  if (tree->journal)
+    {
+      meta_journal_free (tree->journal);
+      tree->journal = NULL;
+    }
+
+  g_free (tree->attributes);
+  tree->num_attributes = 0;
+  tree->attributes = NULL;
+
+  tree->tag = 0;
+  tree->time_t_base = 0;
+  tree->header = NULL;
+  tree->root = NULL;
+
+  if (tree->data)
+    {
+      munmap(tree->data, tree->len);
+      tree->data = NULL;
+    }
+
+  tree->len = 0;
+  if (tree->fd != 0)
+    {
+      close (tree->fd);
+      tree->fd = 0;
+    }
+}
+
+void
+meta_tree_free (MetaTree *tree)
+{
+  meta_tree_clear (tree);
+  g_free (tree->filename);
+  g_free (tree);
+}
+
+static gboolean
+meta_tree_init (MetaTree *tree)
+{
+  struct stat statbuf;
+  int fd;
+  void *data;
+  guint32 *attributes;
+  int i;
+
+  fd = open (tree->filename, O_RDONLY);
+  if (fd == -1)
+    return FALSE;
+
+  if (fstat (fd, &statbuf) != 0 ||
+      statbuf.st_size < sizeof (MetaFileHeader))
+    {
+      close (fd);
+      return FALSE;
+    }
+
+  data = mmap (NULL, statbuf.st_size, PROT_READ, MAP_SHARED, fd, 0);
+  if (data == MAP_FAILED)
+    {
+      close (fd);
+      return FALSE;
+    }
+
+  tree->fd = fd;
+  tree->len = statbuf.st_size;
+  tree->data = data;
+  tree->header = (MetaFileHeader *)data;
+
+  if (memcmp (tree->header->magic, MAGIC, MAGIC_LEN) != 0)
+    goto err;
+
+  if (tree->header->major != MAJOR_VERSION)
+    goto err;
+
+  tree->root = verify_block_pointer (tree, tree->header->root, sizeof (MetaFileDirEnt));
+  if (tree->root == NULL)
+    goto err;
+
+  attributes = verify_array_block (tree, tree->header->attributes, sizeof (guint32));
+  if (attributes == NULL)
+    goto err;
+
+  tree->num_attributes = GUINT32_FROM_BE (*attributes);
+  attributes++;
+  tree->attributes = g_new (char *, tree->num_attributes);
+  for (i = 0; i < tree->num_attributes; i++)
+    {
+      tree->attributes[i] = verify_string (tree, attributes[i]);
+      if (tree->attributes[i] == NULL)
+	goto err;
+    }
+
+  tree->tag = GUINT32_FROM_BE (tree->header->random_tag);
+  tree->time_t_base = GINT64_FROM_BE (tree->header->time_t_base);
+
+  tree->journal = meta_journal_open (tree->filename, tree->for_write, tree->tag);
+
+  /* There is a race with tree replacing, where the journal could have been
+     deleted (and the tree replaced) inbetween opening the tree file and the
+     journal. However we can detect this case by looking at the tree and see
+     if its been rotated, we do this to ensure we have an uptodate tree+journal
+     combo. */
+  meta_tree_refresh (tree);
+
+  return TRUE;
+
+ err:
+  meta_tree_clear (tree);
+  return FALSE;
+}
+
+MetaTree *
+meta_tree_open (const char *filename,
+		gboolean for_write)
+{
+  MetaTree *tree;
+
+  g_assert (sizeof (MetaFileHeader) == 32);
+  g_assert (sizeof (MetaFileDirEnt) == 16);
+  g_assert (sizeof (MetaFileDataEnt) == 8);
+
+  tree = g_new0 (MetaTree, 1);
+  tree->filename = g_strdup (filename);
+  tree->for_write = for_write;
+
+  if (!meta_tree_init (tree))
+    {
+      meta_tree_free (tree);
+      return NULL;
+    }
+  return tree;
+}
+
+void
+meta_tree_refresh (MetaTree *tree)
+{
+  if (tree->header != NULL &&
+      GUINT32_FROM_BE (tree->header->rotated) == 0)
+    return; /* Got a valid tree and its not rotated */
+
+  if (tree->header)
+    meta_tree_clear (tree);
+  meta_tree_init (tree);
+}
+
+
+struct FindName {
+  MetaTree *tree;
+  const char *name;
+};
+
+static int
+find_dir_element (const void *_key, const void *_dirent)
+{
+  const struct FindName *key = _key;
+  const MetaFileDirEnt *dirent = _dirent;
+  char *dirent_name;
+
+  dirent_name = verify_string (key->tree, dirent->name);
+  if (dirent_name == NULL)
+    return -1;
+  return strcmp (key->name, dirent_name);
+}
+
+/* modifies path!!! */
+static MetaFileDirEnt *
+dir_lookup_path (MetaTree *tree,
+		 MetaFileDirEnt *dirent,
+		 char *path)
+{
+  char *end_path;
+  MetaFileDir *dir;
+  struct FindName key;
+
+  while (*path == '/')
+    path++;
+
+  if (*path == 0)
+    return dirent;
+
+  if (dirent->children == 0)
+    return NULL;
+
+  dir = verify_children_block (tree, dirent->children);
+  if (dir == NULL)
+    return NULL;
+
+  end_path = path;
+  while (*end_path != 0 &&
+	 *end_path != '/')
+    end_path++;
+
+  if (*end_path != 0)
+    *end_path++ = 0;
+
+  key.name = path;
+  key.tree = tree;
+  dirent = bsearch (&key, &dir->children[0],
+		    GUINT32_FROM_BE (dir->num_children), sizeof (MetaFileDirEnt),
+		    find_dir_element);
+
+  if (dirent == NULL)
+    return NULL;
+
+  return dir_lookup_path (tree, dirent, end_path);
+}
+
+static MetaFileDirEnt *
+meta_tree_lookup (MetaTree *tree,
+		  const char *path)
+{
+  MetaFileDirEnt *dirent;
+  char *path_copy;
+
+  path_copy = g_strdup (path);
+  dirent = dir_lookup_path (tree, tree->root, path_copy);
+  g_free (path_copy);
+
+  return dirent;
+}
+
+static MetaFileData *
+meta_tree_lookup_data (MetaTree *tree,
+		       const char *path)
+{
+  MetaFileDirEnt *dirent;
+  MetaFileData *data;
+
+  data = NULL;
+  dirent = meta_tree_lookup (tree, path);
+  if (dirent)
+    data = verify_metadata_block (tree, dirent->metadata);
+
+  return data;
+}
+
+static int
+find_attribute_id (const void *_key, const void *_entry)
+{
+  const char *key = _key;
+  const char *const*entry = _entry;
+
+  return strcmp (key, *entry);
+}
+
+#define NO_KEY ((guint32)-1)
+
+static guint32
+get_id_for_key (MetaTree *tree,
+		const char *attribute)
+{
+  char **attribute_ptr;
+
+  attribute_ptr = bsearch (attribute, tree->attributes,
+			   tree->num_attributes, sizeof (char *),
+			   find_attribute_id);
+
+  if (attribute_ptr == NULL)
+    return NO_KEY;
+
+  return attribute_ptr - tree->attributes;
+}
+
+struct FindId {
+  MetaTree *tree;
+  guint32 id;
+};
+
+static int
+find_data_element (const void *_key, const void *_dataent)
+{
+  const struct FindId *key = _key;
+  const MetaFileDataEnt *dataent = _dataent;
+  guint32 key_id;
+
+  key_id = GUINT32_FROM_BE (dataent->key) & ~KEY_IS_LIST_MASK;
+
+  return key->id - key_id;
+}
+
+static MetaFileDataEnt *
+meta_data_get_key (MetaTree *tree,
+		   MetaFileData *data,
+		   const char *attribute)
+{
+  MetaFileDataEnt *dataent;
+  struct FindId key;
+
+  key.id = get_id_for_key (tree, attribute);
+  key.tree = tree;
+  dataent = bsearch (&key, &data->keys[0],
+		     GUINT32_FROM_BE (data->num_keys), sizeof (MetaFileDataEnt),
+		     find_data_element);
+
+  return dataent;
+}
+
+static char *
+get_journal_filename (const char *filename, guint32 random_tag)
+{
+  const char *hexdigits = "0123456789abcdef";
+  char tag[9];
+  int i;
+
+  for (i = 7; i >= 0; i--)
+    {
+      tag[i] = hexdigits[random_tag % 0x10];
+      random_tag >>= 4;
+    }
+
+  tag[8] = 0;
+
+  return g_strconcat (filename, "-", tag, ".log", NULL);
+}
+
+static void
+meta_journal_free (MetaJournal *journal)
+{
+  g_free (journal->filename);
+  munmap(journal->data, journal->len);
+  close (journal->fd);
+  g_free (journal);
+}
+
+static MetaJournalEntry *
+verify_journal_entry (MetaJournal *journal,
+		      MetaJournalEntry *entry)
+{
+  guint32 offset, real_crc32;
+  guint32 entry_len, entry_len_end;
+  char *ptr;
+
+  ptr = (char *)entry;
+  if (ptr < journal->data)
+    return NULL;
+  offset =  ptr - journal->data;
+
+  /* Must be 32bit aligned */
+  if (offset % 4 != 0)
+    return NULL;
+
+  /* entry_size must be valid */
+  if (offset > journal->len - 4)
+    return NULL;
+
+  /* Verify that entry fits and has right size */
+  entry_len = GUINT32_FROM_BE (entry->entry_size);
+
+  /* Must be 32bit aligned */
+  if (entry_len % 4 != 0)
+    return NULL;
+  /* Must have space for at the very least:
+     len+crc32+mtime+type+path_terminating_zeor+end_len */
+  if (journal->len < 4 + 4 + 8 + 1 + 1 + 4)
+    return NULL;
+
+  if (entry_len > journal->len ||
+      offset > journal->len - entry_len)
+    return NULL;
+
+  entry_len_end = GUINT32_FROM_BE (*(guint32 *)(journal->data + offset + entry_len - 4));
+  if (entry_len != entry_len_end)
+    return NULL;
+
+  real_crc32 = crc32 (journal->data + offset + 8, entry_len - 8);
+  if (real_crc32 != GUINT32_FROM_BE (entry->crc32))
+    return NULL;
+
+  return (MetaJournalEntry *)(journal->data + offset + entry_len);
+}
+
+/* Try to validate more entries */
+static void
+meta_journal_validate_more (MetaJournal *journal)
+{
+  guint32 num_entries, i;
+  MetaJournalEntry *entry, *next_entry;
+
+  if (!journal->journal_valid)
+    return; /* Once we've seen a failure, never look for more */
+
+  /* TODO: Use atomic read here? */
+  num_entries = GUINT32_FROM_BE (*(volatile guint32 *)&journal->header->num_entries);
+
+  entry = journal->last_entry;
+  i = journal->last_entry_num;
+  while (i < num_entries)
+    {
+      next_entry = verify_journal_entry (journal, entry);
+
+      if (next_entry == NULL)
+	{
+	  journal->journal_valid = FALSE;
+	  break;
+	}
+
+      entry = next_entry;
+      i++;
+    }
+
+  journal->last_entry = entry;
+  journal->last_entry_num = i;
+}
+
+static void
+set_uint32 (GString *s, guint32 offset, guint32 val)
+{
+  union {
+    guint32 as_int;
+    char as_bytes[4];
+  } u;
+
+  u.as_int = GUINT32_TO_BE (val);
+  memcpy (s->str + offset, u.as_bytes, 4);
+}
+
+static GString *
+append_uint32 (GString *s, guint32 val)
+{
+  union {
+    guint32 as_int;
+    char as_bytes[4];
+  } u;
+
+  u.as_int = GUINT32_TO_BE (val);
+  g_string_append_len (s, u.as_bytes, 4);
+  return s;
+}
+
+static GString *
+append_uint64 (GString *s, guint64 val)
+{
+  union {
+    guint64 as_int;
+    char as_bytes[8];
+  } u;
+
+  u.as_int = GUINT64_TO_BE (val);
+  g_string_append_len (s, u.as_bytes, 8);
+  return s;
+}
+
+static GString *
+append_string (GString *s, const char *str)
+{
+  g_string_append (s, str);
+  g_string_append_c (s, 0);
+  return s;
+}
+
+static guint64
+get_time_t (MetaTree *tree, guint32 val)
+{
+  val = GUINT32_FROM_BE (val);
+  if (val == 0)
+    return 0;
+  return val + tree->time_t_base;
+}
+
+static GString *
+meta_journal_entry_init (int op,
+			 guint64 mtime,
+			 const char *path)
+{
+  GString *out;
+
+  out = g_string_new (NULL);
+  append_uint32 (out, 0); /* len */
+  append_uint32 (out, 0); /* crc32 */
+  append_uint64 (out, mtime);
+  g_string_append_c (out, (char)op);
+  append_string (out, path);
+
+  return out;
+}
+
+static GString *
+meta_journal_entry_finish (GString *out)
+{
+  guint32 len;
+
+  while (out->len % 4 != 0)
+    g_string_append_c (out, 0);
+
+  len = out->len + 4;
+  append_uint32 (out, len);
+  set_uint32 (out, 0, len);
+  set_uint32 (out, 4, crc32 (out->str + 8, len - 8));
+  return out;
+}
+
+static GString *
+meta_journal_entry_new_set (guint64 mtime,
+			    const char *path,
+			    const char *key,
+			    const char *value)
+{
+  GString *out;
+
+  out = meta_journal_entry_init (JOURNAL_OP_SET_KEY, mtime, path);
+  append_string (out, key);
+  append_string (out, value);
+  return meta_journal_entry_finish (out);
+}
+
+static gboolean
+meta_journal_add_entry (MetaJournal *journal,
+			GString *entry)
+{
+  char *ptr;
+  guint32 offset;
+
+  g_assert (journal->journal_valid);
+
+  ptr = (char *)journal->last_entry;
+  offset =  ptr - journal->data;
+
+  /* Does the entry fit? */
+  if (entry->len > journal->len - offset)
+    return FALSE;
+
+  memcpy (ptr, entry->str, entry->len);
+
+  journal->header->num_entries = GUINT_TO_BE (journal->last_entry_num + 1);
+  meta_journal_validate_more (journal);
+  g_assert (journal->journal_valid);
+
+  return TRUE;
+}
+
+static MetaJournal *
+meta_journal_open (const char *filename, gboolean for_write, guint32 tag)
+{
+  MetaJournal *journal;
+  struct stat statbuf;
+  int fd;
+  char *data;
+  char *journal_filename;
+  int open_flags, mmap_prot;
+
+  g_assert (sizeof (MetaJournalHeader) == 20);
+
+  journal_filename = get_journal_filename (filename, tag);
+
+  if (for_write)
+    open_flags = O_RDWR;
+  else
+    open_flags = O_RDONLY;
+
+  fd = open (journal_filename, open_flags);
+  g_free (journal_filename);
+  if (fd == -1)
+    return NULL;
+
+  if (fstat (fd, &statbuf) != 0 ||
+      statbuf.st_size < sizeof (MetaJournalHeader))
+    {
+      close (fd);
+      return NULL;
+    }
+
+  mmap_prot = PROT_READ;
+  if (for_write)
+    mmap_prot |= PROT_WRITE;
+  data = mmap (NULL, statbuf.st_size, mmap_prot, MAP_SHARED, fd, 0);
+  if (data == MAP_FAILED)
+    {
+      close (fd);
+      return NULL;
+    }
+
+  journal = g_new0 (MetaJournal, 1);
+  journal->filename = g_strdup (filename);
+  journal->fd = fd;
+  journal->len = statbuf.st_size;
+  journal->data = data;
+  journal->header = (MetaJournalHeader *)data;
+  journal->first_entry = (MetaJournalEntry *)(data + sizeof (MetaJournalHeader));
+  journal->last_entry = journal->first_entry;
+  journal->last_entry_num = 0;
+
+  if (memcmp (journal->header->magic, JOURNAL_MAGIC, JOURNAL_MAGIC_LEN) != 0)
+    goto err;
+
+  if (journal->header->major != JOURNAL_MAJOR_VERSION)
+    goto err;
+
+  if (journal->len != GUINT32_FROM_BE (journal->header->file_size))
+    goto err;
+
+  if (tag != GUINT32_FROM_BE (journal->header->random_tag))
+    goto err;
+
+  journal->journal_valid = TRUE;
+  meta_journal_validate_more (journal);
+
+  return journal;
+
+ err:
+  meta_journal_free (journal);
+  return NULL;
+}
+
+static char *
+get_next_arg (char *str)
+{
+  return str  + strlen (str) + 1;
+}
+
+static gboolean
+journal_entry_is_key_type (MetaJournalEntry *entry)
+{
+ return
+   entry->entry_type == JOURNAL_OP_SET_KEY ||
+   entry->entry_type == JOURNAL_OP_SETV_KEY ||
+   entry->entry_type == JOURNAL_OP_UNSET_KEY;
+}
+
+static gboolean
+journal_entry_is_path_type (MetaJournalEntry *entry)
+{
+ return
+   entry->entry_type == JOURNAL_OP_COPY_PATH ||
+   entry->entry_type == JOURNAL_OP_REMOVE_PATH;
+}
+
+/* returns remainer if path has "prefix" as prefix (or is equal to prefix) */
+static const char *
+get_prefix_match (const char *path,
+		  const char *prefix)
+{
+  gsize prefix_len;
+  const char *remainder;
+
+  prefix_len = strlen (prefix);
+
+  /* Handle trailing slashes in prefix, this is not
+     generally common, but happens in the case of the
+     root dir "/" */
+  while (prefix_len > 0 &&
+	 prefix[prefix_len-1] == '/')
+    prefix_len--;
+
+  if (strncmp (path, prefix, prefix_len) != 0)
+    return NULL;
+
+  remainder = path + prefix_len;
+  if (*remainder != 0 &&
+      *remainder != '/')
+    return NULL; /* only a string prefix, not a path prefix */
+
+  while (*remainder == '/')
+    remainder++;
+
+  return remainder;
+}
+
+typedef gboolean (*journal_key_callback) (MetaJournal *journal,
+					  MetaJournalEntryType entry_type,
+					  const char *path,
+					  const char *key,
+					  gpointer value,
+					  char **iter_path,
+					  gpointer user_data);
+typedef gboolean (*journal_path_callback) (MetaJournal *journal,
+					   MetaJournalEntryType entry_type,
+					   const char *path,
+					   const char *source_path,
+					   char **iter_path,
+					   gpointer user_data);
+
+static char *
+meta_journal_iterate (MetaJournal *journal,
+		      const char *path,
+		      journal_key_callback key_callback,
+		      journal_path_callback path_callback,
+		      gpointer user_data)
+{
+  MetaJournalEntry *entry;
+  guint32 *sizep;
+  char *journal_path, *journal_key, *source_path;
+  char *path_copy, *value;
+  gboolean res;
+
+  path_copy = g_strdup (path);
+
+  if (journal == NULL)
+    return path_copy;
+
+  entry = journal->last_entry;
+  while (entry > journal->first_entry)
+    {
+      sizep = (guint32 *)entry;
+      entry = (MetaJournalEntry *)((char *)entry - GUINT32_FROM_BE (*(sizep-1)));
+
+      journal_path = &entry->path[0];
+
+      if (journal_entry_is_key_type (entry) &&
+	  key_callback) /* set, setv or unset */
+	{
+	  journal_key = get_next_arg (journal_path);
+	  value = get_next_arg (journal_key);
+
+	  /* Only affects is path is exactly the same */
+	  res = key_callback (journal, entry->entry_type,
+			      journal_path, journal_key,
+			      value,
+			      &path_copy, user_data);
+	  if (!res)
+	    {
+	      g_free (path_copy);
+	      return NULL;
+	    }
+	}
+      else if (journal_entry_is_path_type (entry) &&
+	       path_callback) /* copy or remove */
+	{
+	  source_path = NULL;
+	  if (entry->entry_type == JOURNAL_OP_COPY_PATH)
+	    source_path = get_next_arg (journal_path);
+
+	  res = path_callback (journal, entry->entry_type,
+			       journal_path, source_path,
+			       &path_copy, user_data);
+	  if (!res)
+	    {
+	      g_free (path_copy);
+	      return NULL;
+	    }
+	}
+      else
+	g_warning ("Unknown journal entry type %d\n", entry->entry_type);
+    }
+
+  return path_copy;
+}
+
+typedef struct {
+  const char *key;
+  MetaKeyType type;
+  gpointer value;
+} PathKeyData;
+
+static gboolean
+journal_iter_key (MetaJournal *journal,
+		  MetaJournalEntryType entry_type,
+		  const char *path,
+		  const char *key,
+		  gpointer value,
+		  char **iter_path,
+		  gpointer user_data)
+{
+  PathKeyData *data = user_data;
+
+  if (strcmp (path, *iter_path) != 0)
+    return TRUE; /* No match, continue */
+
+  if (strcmp (data->key, key) != 0)
+    return TRUE; /* No match, continue */
+
+  switch (entry_type)
+    {
+    case JOURNAL_OP_SET_KEY:
+      data->type = META_KEY_TYPE_STRING;
+      data->value = value;
+      break;
+    case JOURNAL_OP_SETV_KEY:
+      data->type = META_KEY_TYPE_STRINGV;
+      data->value = value;
+      break;
+    case JOURNAL_OP_UNSET_KEY:
+      data->type = META_KEY_TYPE_NONE;
+      data->value = NULL;
+      break;
+    default:
+      /* No other key type should reach this  */
+      g_assert_not_reached ();
+    }
+  return FALSE; /* stop iterating */
+}
+
+static gboolean
+journal_iter_path (MetaJournal *journal,
+		   MetaJournalEntryType entry_type,
+		   const char *path,
+		   const char *source_path,
+		   char **iter_path,
+		   gpointer user_data)
+{
+  PathKeyData *data = user_data;
+  char *old_path;
+  const char *remainder;
+
+  /* is this a parent of the iter path */
+  remainder = get_prefix_match (*iter_path, path);
+  if (remainder == NULL)
+    return TRUE; /* Not related, continue */
+
+  /* path is affected as a child of this node */
+  if (entry_type == JOURNAL_OP_REMOVE_PATH)
+    {
+      if (data)
+	{
+	  data->type = META_KEY_TYPE_NONE;
+	  data->value = NULL;
+	}
+      return FALSE; /* stop iterating */
+    }
+  else if (entry_type == JOURNAL_OP_COPY_PATH)
+    {
+      old_path = *iter_path;
+      *iter_path = g_build_filename (source_path, remainder, NULL);
+      g_free (old_path);
+      return TRUE; /* Continue, with new path */
+    }
+  return TRUE;
+}
+
+static char *
+meta_journal_reverse_map_path_and_key (MetaJournal *journal,
+				       const char *path,
+				       const char *key,
+				       MetaKeyType *type,
+				       gpointer *value)
+{
+  PathKeyData data = {0};
+  char *res_path;
+
+  data.key = key;
+  res_path = meta_journal_iterate (journal,
+				   path,
+				   journal_iter_key,
+				   journal_iter_path,
+				   &data);
+  *type = data.type;
+  *value = data.value;
+  return res_path;
+}
+
+MetaKeyType
+meta_tree_lookup_key_type  (MetaTree                         *tree,
+			    const char                       *path,
+			    const char                       *key)
+{
+  MetaFileData *data;
+  MetaFileDataEnt *ent;
+  char *new_path;
+  MetaKeyType type;
+  gpointer value;
+
+  new_path = meta_journal_reverse_map_path_and_key (tree->journal,
+						    path,
+						    key,
+						    &type, &value);
+  if (new_path == NULL)
+    return type;
+
+  data = meta_tree_lookup_data (tree, new_path);
+  ent = NULL;
+  if (data)
+    ent = meta_data_get_key (tree, data, key);
+
+  g_free (new_path);
+
+  if (ent == NULL)
+    return META_KEY_TYPE_NONE;
+  if (GUINT32_FROM_BE (ent->key) & KEY_IS_LIST_MASK)
+    return META_KEY_TYPE_STRINGV;
+  else
+    return META_KEY_TYPE_STRING;
+}
+
+guint64
+meta_tree_get_last_changed (MetaTree                         *tree,
+			    const char                       *path)
+{
+  /* TODO */
+  return 0;
+}
+
+char *
+meta_tree_lookup_string    (MetaTree                         *tree,
+			    const char                       *path,
+			    const char                       *key)
+{
+  MetaFileData *data;
+  MetaFileDataEnt *ent;
+  MetaKeyType type;
+  gpointer value;
+  char *new_path;
+
+  new_path = meta_journal_reverse_map_path_and_key (tree->journal,
+						    path,
+						    key,
+						    &type, &value);
+  if (new_path == NULL)
+    {
+      if (type == META_KEY_TYPE_STRING)
+	return g_strdup (value);
+      return NULL;
+    }
+
+  data = meta_tree_lookup_data (tree, new_path);
+  ent = NULL;
+  if (data)
+    ent = meta_data_get_key (tree, data, key);
+
+  g_free (new_path);
+
+  if (ent == NULL)
+    return NULL;
+  if (ent->key & KEY_IS_LIST_MASK)
+    return NULL;
+  return verify_string (tree, ent->value);
+}
+
+char **
+meta_tree_lookup_stringv   (MetaTree                         *tree,
+			    const char                       *path,
+			    const char                       *key)
+{
+  /* TODO */
+  return NULL;
+}
+
+typedef struct {
+  char *name;
+  guint64 last_changed;
+  gboolean has_children;
+  gboolean has_data;
+  gboolean exists; /* May be true even if deleted is true, if recreated */
+  gboolean deleted; /* Was deleted at some point, ignore everything before */
+
+  gboolean reported; /* Set to true when reported to user */
+} EnumDirChildInfo;
+
+typedef struct {
+  GHashTable *children;
+} EnumDirData;
+
+
+static void
+child_info_free (EnumDirChildInfo *info)
+{
+  g_free (info->name);
+  g_free (info);
+}
+
+static EnumDirChildInfo *
+get_child_info (EnumDirData *data,
+		const char *remainder,
+		gboolean *direct_child)
+{
+  EnumDirChildInfo *info;
+  const char *slash;
+  char *name;
+
+  slash = strchr (remainder, '/');
+  if (slash != 0)
+    name = g_strndup (remainder, slash - remainder);
+  else
+    name = g_strdup (remainder);
+
+  *direct_child = slash == NULL;
+
+  info = g_hash_table_lookup (data->children, name);
+  if (info == NULL)
+    {
+      info = g_new0 (EnumDirChildInfo, 1);
+      info->name = name;
+      g_hash_table_insert (data->children, info->name, info);
+    }
+  else
+    g_free (name);
+
+  return info;
+}
+
+static gboolean
+enum_dir_iter_key (MetaJournal *journal,
+		   MetaJournalEntryType entry_type,
+		   const char *path,
+		   const char *key,
+		   gpointer value,
+		   char **iter_path,
+		   gpointer user_data)
+{
+  EnumDirData *data = user_data;
+  EnumDirChildInfo *info;
+  gboolean direct_child;
+  const char *remainder;
+
+  /* is this a true child of iter_path, then that may create a child */
+  remainder = get_prefix_match (path, *iter_path);
+  if (remainder != NULL && *remainder != 0)
+    {
+      info = get_child_info (data, remainder, &direct_child);
+
+      if (!info->deleted)
+	{
+	  info->exists = TRUE;
+	  if (info->last_changed == 0)
+	    info->last_changed = 0; /*TODO*/
+	  info->has_children |= !direct_child;
+	  info->has_data |=
+	    direct_child && entry_type != JOURNAL_OP_UNSET_KEY;
+	}
+    }
+
+  return TRUE; /* continue */
+}
+
+static gboolean
+enum_dir_iter_path (MetaJournal *journal,
+		    MetaJournalEntryType entry_type,
+		    const char *path,
+		    const char *source_path,
+		    char **iter_path,
+		    gpointer user_data)
+{
+  EnumDirData *data = user_data;
+  EnumDirChildInfo *info;
+  gboolean direct_child;
+  const char *remainder;
+  char *old_path;
+
+  /* Is path a true child of iter_path */
+  remainder = get_prefix_match (path, *iter_path);
+  if (remainder != NULL && *remainder != 0)
+    {
+      info = get_child_info (data, remainder, &direct_child);
+
+	/* copy destination a true child, that creates a child */
+      if (entry_type == JOURNAL_OP_COPY_PATH)
+	{
+	  if (!info->deleted)
+	    {
+	      info->exists = TRUE;
+	      if (info->last_changed == 0)
+		info->last_changed = 0; /*TODO*/
+	      info->has_children = TRUE;
+	      info->has_data = TRUE;
+	    }
+	}
+      else if (entry_type == JOURNAL_OP_REMOVE_PATH &&
+	       direct_child)
+	{
+	  info->deleted = TRUE;
+	}
+    }
+
+  /* is this a parent of the iter path */
+  remainder = get_prefix_match (*iter_path, path);
+  if (remainder != NULL)
+    {
+      /* path is affected as a child of this node */
+      if (entry_type == JOURNAL_OP_REMOVE_PATH)
+	return FALSE; /* stop iterating */
+      else if (entry_type == JOURNAL_OP_COPY_PATH)
+	{
+	  old_path = *iter_path;
+	  *iter_path = g_build_filename (source_path, remainder, NULL);
+	  g_free (old_path);
+	  return TRUE; /* Continue, with new path */
+	}
+    }
+
+  return TRUE;
+}
+
+static gboolean
+enumerate_dir (MetaTree *tree,
+	       MetaFileDir *dir,
+	       GHashTable *children,
+	       meta_tree_dir_enumerate_callback callback,
+	       gpointer user_data)
+{
+  guint32 i, num_children;
+  MetaFileDirEnt *dirent;
+  EnumDirChildInfo *info;
+  char *dirent_name;
+  gboolean has_children;
+  gboolean has_data;
+  guint64 last_changed;
+
+  num_children = GUINT32_FROM_BE (dir->num_children);
+  for (i = 0; i < num_children; i++)
+    {
+      dirent = &dir->children[i];
+      dirent_name = verify_string (tree, dirent->name);
+      if (dirent_name == NULL)
+	continue;
+
+      last_changed = get_time_t (tree, dirent->last_changed);
+      has_children = dirent->children != 0;
+      has_data = dirent->metadata != 0;
+
+      info = g_hash_table_lookup (children, dirent_name);
+      if (info)
+	{
+	  if (info->deleted)
+	    continue; /* if recreated (i.e. exists == TRUE), report later */
+
+	  info->reported = TRUE;
+
+	  if (info->last_changed != 0)
+	    last_changed = MAX (last_changed, info->last_changed);
+
+	  has_children |= info->has_children;
+	  has_data |= info->has_data;
+	}
+
+      if (!callback (dirent_name,
+		     last_changed,
+		     has_children,
+		     has_data,
+		     user_data))
+	return FALSE;
+    }
+  return TRUE;
+}
+
+void
+meta_tree_enumerate_dir (MetaTree                         *tree,
+			 const char                       *path,
+			 meta_tree_dir_enumerate_callback  callback,
+			 gpointer                          user_data)
+{
+  EnumDirData data;
+  GHashTable *children;
+  EnumDirChildInfo *info;
+  MetaFileDirEnt *dirent;
+  GHashTableIter iter;
+  MetaFileDir *dir;
+  char *res_path;
+
+  data.children = children =
+    g_hash_table_new_full (g_str_hash,
+			   g_str_equal,
+			   NULL,
+			   (GDestroyNotify)child_info_free);
+
+
+  res_path = meta_journal_iterate (tree->journal,
+				   path,
+				   enum_dir_iter_key,
+				   enum_dir_iter_path,
+				   &data);
+
+  if (res_path != NULL)
+    {
+      dirent = meta_tree_lookup (tree, res_path);
+      if (dirent != NULL &&
+	  dirent->children != 0)
+	{
+	  dir = verify_children_block (tree, dirent->children);
+	  if (dir)
+	    {
+	      if (!enumerate_dir (tree, dir, children, callback, user_data))
+		goto out;
+	    }
+	}
+    }
+
+  g_hash_table_iter_init (&iter, children);
+  while (g_hash_table_iter_next (&iter, NULL, (gpointer  *)&info))
+    {
+      if (info->reported || !info->exists)
+	continue;
+
+      if (!callback (info->name,
+		     info->last_changed,
+		     info->has_children,
+		     info->has_data,
+		     user_data))
+	break;
+    }
+ out:
+  g_hash_table_destroy (children);
+}
+
+typedef struct {
+  char *key;
+
+  MetaKeyType type;
+  gpointer value;
+
+  gboolean seen; /* We saw this key in the journal */
+} EnumKeysInfo;
+
+typedef struct {
+  GHashTable *keys;
+} EnumKeysData;
+
+
+static void
+key_info_free (EnumKeysInfo *info)
+{
+  g_free (info->key);
+  g_free (info);
+}
+
+static EnumKeysInfo *
+get_key_info (EnumKeysData *data,
+	      const char *key)
+{
+  EnumKeysInfo *info;
+
+  info = g_hash_table_lookup (data->keys, key);
+  if (info == NULL)
+    {
+      info = g_new0 (EnumKeysInfo, 1);
+      info->key = g_strdup (key);
+      g_hash_table_insert (data->keys, info->key, info);
+    }
+
+  return info;
+}
+
+static gboolean
+enum_keys_iter_key (MetaJournal *journal,
+		    MetaJournalEntryType entry_type,
+		    const char *path,
+		    const char *key,
+		    gpointer value,
+		    char **iter_path,
+		    gpointer user_data)
+{
+  EnumKeysData *data = user_data;
+  EnumKeysInfo *info;
+
+  if (strcmp (path, *iter_path) == 0)
+    {
+      info = get_key_info (data, key);
+
+      if (!info->seen)
+	{
+	  info->seen = TRUE;
+	  if (entry_type == JOURNAL_OP_UNSET_KEY)
+	    info->type = META_KEY_TYPE_NONE;
+	  else if (entry_type == JOURNAL_OP_SET_KEY)
+	    info->type = META_KEY_TYPE_STRING;
+	  else
+	    info->type = META_KEY_TYPE_STRINGV;
+	  info->value = value;
+	}
+    }
+
+  return TRUE; /* continue */
+}
+
+static gboolean
+enum_keys_iter_path (MetaJournal *journal,
+		     MetaJournalEntryType entry_type,
+		     const char *path,
+		     const char *source_path,
+		     char **iter_path,
+		     gpointer user_data)
+{
+  const char *remainder;
+  char *old_path;
+
+  /* is this a parent of the iter path */
+  remainder = get_prefix_match (*iter_path, path);
+  if (remainder != NULL)
+    {
+      /* path is affected as a child of this node */
+      if (entry_type == JOURNAL_OP_REMOVE_PATH)
+	return FALSE; /* stop iterating */
+      else if (entry_type == JOURNAL_OP_COPY_PATH)
+	{
+	  old_path = *iter_path;
+	  *iter_path = g_build_filename (source_path, remainder, NULL);
+	  g_free (old_path);
+	  return TRUE; /* Continue, with new path */
+	}
+    }
+
+  return TRUE;
+}
+
+static gboolean
+enumerate_data (MetaTree *tree,
+		MetaFileData *data,
+		GHashTable *keys,
+		meta_tree_keys_enumerate_callback callback,
+		gpointer user_data)
+{
+  guint32 i, num_keys;
+  MetaFileDataEnt *ent;
+  EnumKeysInfo *info;
+  char *key_name;
+  guint32 key_id;
+  MetaKeyType type;
+  gpointer value;
+
+  num_keys = GUINT32_FROM_BE (data->num_keys);
+  for (i = 0; i < num_keys; i++)
+    {
+      ent = &data->keys[i];
+
+      key_id = GUINT32_FROM_BE (ent->key) & ~KEY_IS_LIST_MASK;
+      if (GUINT32_FROM_BE (ent->key) & KEY_IS_LIST_MASK)
+	type = META_KEY_TYPE_STRINGV;
+      else
+	type = META_KEY_TYPE_STRING;
+
+      if (key_id >= tree->num_attributes)
+	continue;
+
+      key_name = tree->attributes[key_id];
+      if (key_name == NULL)
+	continue;
+
+      info = g_hash_table_lookup (keys, key_name);
+      if (info)
+	continue; /* overridden, handle later */
+
+      if (type == META_KEY_TYPE_STRING)
+	value = verify_string (tree, ent->value);
+      else
+	{
+	  value = NULL;
+	  g_print ("TODO: Handle stringv metadata from tree\n");
+	}
+
+      if (!callback (key_name,
+		     type,
+		     value,
+		     user_data))
+	return FALSE;
+    }
+  return TRUE;
+}
+
+void
+meta_tree_enumerate_keys (MetaTree                         *tree,
+			  const char                       *path,
+			  meta_tree_keys_enumerate_callback callback,
+			  gpointer                          user_data)
+{
+  EnumKeysData keydata;
+  GHashTable *keys;
+  EnumKeysInfo *info;
+  MetaFileData *data;
+  GHashTableIter iter;
+  char *res_path;
+
+  keydata.keys = keys =
+    g_hash_table_new_full (g_str_hash,
+			   g_str_equal,
+			   NULL,
+			   (GDestroyNotify)key_info_free);
+
+
+  res_path = meta_journal_iterate (tree->journal,
+				   path,
+				   enum_keys_iter_key,
+				   enum_keys_iter_path,
+				   &keydata);
+
+  if (res_path != NULL)
+    {
+      data = meta_tree_lookup_data (tree, res_path);
+      if (data != NULL)
+	{
+	  if (!enumerate_data (tree, data, keys, callback, user_data))
+	    goto out;
+	}
+    }
+
+  g_hash_table_iter_init (&iter, keys);
+  while (g_hash_table_iter_next (&iter, NULL, (gpointer  *)&info))
+    {
+      gpointer value;
+
+      if (info->type == META_KEY_TYPE_NONE)
+	continue;
+
+      if (info->type == META_KEY_TYPE_STRING)
+	value = info->value;
+      else
+	{
+	  value = NULL;
+	  g_print ("TODO: Handle stringv metadata from journal\n");
+	}
+
+      if (!callback (info->key,
+		     info->type,
+		     value,
+		     user_data))
+	break;
+    }
+ out:
+  g_hash_table_destroy (keys);
+}
+
+gboolean
+meta_tree_flush (MetaTree *tree)
+{
+  /* TODO: roll over */
+  return FALSE;
+}
+
+gboolean
+meta_tree_unset (MetaTree                         *tree,
+		 const char                       *path,
+		 const char                       *key)
+{
+  return FALSE;
+}
+
+gboolean
+meta_tree_set_string (MetaTree                         *tree,
+		      const char                       *path,
+		      const char                       *key,
+		      const char                       *value)
+{
+  GString *entry;
+  guint64 mtime;
+
+  if (tree->journal == NULL ||
+      !tree->journal->journal_valid)
+    return FALSE;
+
+  mtime = time (NULL);
+
+  entry = meta_journal_entry_new_set (mtime, path, key, value);
+
+ retry:
+  if (!meta_journal_add_entry (tree->journal, entry))
+    {
+      if (meta_tree_flush (tree))
+	goto retry;
+
+      g_string_free (entry, TRUE);
+      return FALSE;
+    }
+
+  g_string_free (entry, TRUE);
+  return TRUE;
+}
+
+gboolean
+meta_tree_set_stringv (MetaTree                         *tree,
+		       const char                       *path,
+		       const char                       *key,
+		       const char                      **value)
+{
+  return FALSE;
+}
diff --git a/metadata/metatree.h b/metadata/metatree.h
new file mode 100644
index 00000000..b18d30d9
--- /dev/null
+++ b/metadata/metatree.h
@@ -0,0 +1,58 @@
+#include <glib.h>
+
+typedef struct _MetaTree MetaTree;
+
+typedef enum {
+  META_KEY_TYPE_NONE,
+  META_KEY_TYPE_STRING,
+  META_KEY_TYPE_STRINGV
+} MetaKeyType;
+
+typedef gboolean (*meta_tree_dir_enumerate_callback) (const char *entry,
+						      guint64 last_changed,
+						      gboolean has_children,
+						      gboolean has_data,
+						      gpointer user_data);
+
+typedef gboolean (*meta_tree_keys_enumerate_callback) (const char *key,
+						       MetaKeyType type,
+						       gpointer value,
+						       gpointer user_data);
+
+void      meta_tree_free    (MetaTree   *tree);
+MetaTree *meta_tree_open    (const char *filename,
+			     gboolean    for_write);
+void      meta_tree_refresh (MetaTree   *tree); /* May invalidates all strings */
+
+
+MetaKeyType meta_tree_lookup_key_type  (MetaTree                         *tree,
+					const char                       *path,
+					const char                       *key);
+guint64     meta_tree_get_last_changed (MetaTree                         *tree,
+					const char                       *path);
+char *      meta_tree_lookup_string    (MetaTree                         *tree,
+					const char                       *path,
+					const char                       *key);
+char **     meta_tree_lookup_stringv   (MetaTree                         *tree,
+					const char                       *path,
+					const char                       *key);
+void        meta_tree_enumerate_dir    (MetaTree                         *tree,
+					const char                       *path,
+					meta_tree_dir_enumerate_callback  callback,
+					gpointer                          user_data);
+void        meta_tree_enumerate_keys   (MetaTree                         *tree,
+					const char                       *path,
+					meta_tree_keys_enumerate_callback callback,
+					gpointer                          user_data);
+gboolean    meta_tree_flush            (MetaTree                         *tree);
+gboolean    meta_tree_unset            (MetaTree                         *tree,
+					const char                       *path,
+					const char                       *key);
+gboolean    meta_tree_set_string       (MetaTree                         *tree,
+					const char                       *path,
+					const char                       *key,
+					const char                       *value);
+gboolean    meta_tree_set_stringv      (MetaTree                         *tree,
+					const char                       *path,
+					const char                       *key,
+					const char                      **value);