diff --git a/libsoup/soup-cache.c b/libsoup/soup-cache.c
index 5b64575..0bf2952 100644
--- a/libsoup/soup-cache.c
+++ b/libsoup/soup-cache.c
@@ -30,6 +30,7 @@
 #endif
 
 #include <stdlib.h>
+#include <string.h>
 #include <gio/gio.h>
 
 #define LIBSOUP_USE_UNSTABLE_REQUEST_API
@@ -52,8 +53,7 @@ static void soup_cache_session_feature_init (SoupSessionFeatureInterface *featur
 	                                filled by a single entry */
 
 typedef struct _SoupCacheEntry {
-	char *key;
-	char *filename;
+	guint key;
 	guint freshness_lifetime;
 	gboolean must_revalidate;
 	GString *data;
@@ -219,19 +219,24 @@ get_cacheability (SoupCache *cache, SoupMessage *msg)
 	return cacheability;
 }
 
+static gchar *
+get_filename_from_key (SoupCache *cache, guint key)
+{
+	return g_strdup_printf ("%s%s%u", cache->priv->cache_dir, G_DIR_SEPARATOR_S, key);
+}
+
 static void
-soup_cache_entry_free (SoupCacheEntry *entry, gboolean purge)
+soup_cache_entry_free (SoupCache *cache, SoupCacheEntry *entry, gboolean purge)
 {
 	if (purge) {
-		GFile *file = g_file_new_for_path (entry->filename);
+		gchar *filename = get_filename_from_key (cache, entry->key);
+		GFile *file = g_file_new_for_path (filename);
+		g_free (filename);
 		g_file_delete (file, NULL, NULL);
 		g_object_unref (file);
 	}
 
-	g_free (entry->filename);
-	entry->filename = NULL;
-	g_free (entry->key);
-	entry->key = NULL;
+	entry->key = 0;
 
 	if (entry->headers) {
 		soup_message_headers_free (entry->headers);
@@ -251,7 +256,7 @@ soup_cache_entry_free (SoupCacheEntry *entry, gboolean purge)
 		entry->cancellable = NULL;
 	}
 
-	g_slice_free (SoupCacheEntry, entry);
+	g_free (entry);
 }
 
 static void
@@ -286,11 +291,16 @@ soup_cache_entry_is_fresh_enough (SoupCacheEntry *entry, gint min_fresh)
 	return entry->freshness_lifetime > limit;
 }
 
-static char *
+static guint
 soup_message_get_cache_key (SoupMessage *msg)
 {
+	guint key;
 	SoupURI *uri = soup_message_get_uri (msg);
-	return soup_uri_to_string (uri, FALSE);
+	gchar *uri_str = soup_uri_to_string (uri, FALSE);
+
+	key = g_str_hash (uri_str);
+	g_free (uri_str);
+	return key;
 }
 
 static void
@@ -413,11 +423,9 @@ static SoupCacheEntry *
 soup_cache_entry_new (SoupCache *cache, SoupMessage *msg, time_t request_time, time_t response_time)
 {
 	SoupCacheEntry *entry;
-	SoupMessageHeaders *headers;
 	const char *date;
-	char *md5;
 
-	entry = g_slice_new0 (SoupCacheEntry);
+	entry = g_malloc0 (sizeof(SoupCacheEntry));
 	entry->dirty = FALSE;
 	entry->writing = FALSE;
 	entry->got_body = FALSE;
@@ -426,18 +434,14 @@ soup_cache_entry_new (SoupCache *cache, SoupMessage *msg, time_t request_time, t
 	entry->pos = 0;
 	entry->error = NULL;
 
-	/* key & filename */
+	/* key */
 	entry->key = soup_message_get_cache_key (msg);
-	md5 = g_compute_checksum_for_string (G_CHECKSUM_MD5, entry->key, -1);
-	entry->filename = g_build_filename (cache->priv->cache_dir, md5, NULL);
-	g_free (md5);
 
 	/* Headers */
-	headers = soup_message_headers_new (SOUP_MESSAGE_HEADERS_RESPONSE);
+	entry->headers = soup_message_headers_new (SOUP_MESSAGE_HEADERS_RESPONSE);
 	soup_message_headers_foreach (msg->response_headers,
 				      (SoupMessageHeadersForeachFunc)copy_headers,
-				      headers);
-	entry->headers = headers;
+				      entry->headers);
 
 	/* LRU list */
 	entry->hits = 0;
@@ -517,7 +521,7 @@ close_ready_cb (GObject *source, GAsyncResult *result, SoupCacheWritingFixture *
 	if (g_cancellable_is_cancelled (entry->cancellable)) {
 		entry->dirty = FALSE;
 		soup_cache_entry_remove (cache, entry);
-		soup_cache_entry_free (entry, TRUE);
+		soup_cache_entry_free (cache, entry, TRUE);
 		entry = NULL;
 	} else if ((soup_message_headers_get_encoding (entry->headers) == SOUP_ENCODING_CHUNKED) ||
 		   entry->length != (gsize) content_length) {
@@ -544,7 +548,7 @@ close_ready_cb (GObject *source, GAsyncResult *result, SoupCacheWritingFixture *
 		} else {
 			entry->dirty = FALSE;
 			soup_cache_entry_remove (cache, entry);
-			soup_cache_entry_free (entry, TRUE);
+			soup_cache_entry_free (cache, entry, TRUE);
 			entry = NULL;
 		}
 	}
@@ -717,7 +721,7 @@ soup_cache_entry_remove (SoupCache *cache, SoupCacheEntry *entry)
 	g_assert (g_list_length (cache->priv->lru_start) == g_hash_table_size (cache->priv->cache));
 
 	/* Remove from cache */
-	if (!g_hash_table_remove (cache->priv->cache, entry->key))
+	if (!g_hash_table_remove (cache->priv->cache, GUINT_TO_POINTER(entry->key)))
 		return FALSE;
 
 	/* Remove from LRU */
@@ -788,7 +792,7 @@ make_room_for_new_entry (SoupCache *cache, guint length_to_add)
 		 * freed in close_ready_cb
 		 */
 		if (soup_cache_entry_remove (cache, old_entry)) {
-			soup_cache_entry_free (old_entry, TRUE);
+			soup_cache_entry_free (cache, old_entry, TRUE);
 			lru_entry = cache->priv->lru_start;
 		} else
 			lru_entry = g_list_next (lru_entry);
@@ -797,7 +801,7 @@ make_room_for_new_entry (SoupCache *cache, guint length_to_add)
 
 static gboolean
 soup_cache_entry_insert_by_key (SoupCache *cache,
-				const char *key,
+				const guint key,
 				SoupCacheEntry *entry,
 				gboolean sort)
 {
@@ -815,7 +819,7 @@ soup_cache_entry_insert_by_key (SoupCache *cache,
 		make_room_for_new_entry (cache, length_to_add);
 	}
 
-	g_hash_table_insert (cache->priv->cache, g_strdup (key), entry);
+	g_hash_table_insert (cache->priv->cache, GUINT_TO_POINTER(key), entry);
 
 	/* Compute new cache size */
 	cache->priv->size += length_to_add;
@@ -850,7 +854,7 @@ replace_cb (GObject *source, GAsyncResult *result, SoupCacheWritingFixture *fixt
 		fixture->cache->priv->n_pending--;
 		entry->dirty = FALSE;
 		soup_cache_entry_remove (fixture->cache, entry);
-		soup_cache_entry_free (entry, TRUE);
+		soup_cache_entry_free (fixture->cache, entry, TRUE);
 		soup_cache_writing_fixture_free (fixture);
 		return;
 	}
@@ -906,14 +910,14 @@ msg_got_headers_cb (SoupMessage *msg, gpointer user_data)
 
 	if (cacheable & SOUP_CACHE_CACHEABLE) {
 		SoupCacheEntry *entry;
-		char *key;
+		guint key;
 		GFile *file;
 		SoupCacheWritingFixture *fixture;
+		gchar *filename;
 
 		/* Check if we are already caching this resource */
 		key = soup_message_get_cache_key (msg);
-		entry = g_hash_table_lookup (cache->priv->cache, key);
-		g_free (key);
+		entry = g_hash_table_lookup (cache->priv->cache, GUINT_TO_POINTER(key));
 
 		if (entry && entry->dirty)
 			return;
@@ -921,15 +925,15 @@ msg_got_headers_cb (SoupMessage *msg, gpointer user_data)
 		/* Create a new entry, deleting any old one if present */
 		if (entry) {
 			soup_cache_entry_remove (cache, entry);
-			soup_cache_entry_free (entry, TRUE);
+			soup_cache_entry_free (cache, entry, TRUE);
 		}
 
 		entry = soup_cache_entry_new (cache, msg, request_time, response_time);
 		entry->hits = 1;
 
 		/* Do not continue if it can not be stored */
-		if (!soup_cache_entry_insert_by_key (cache, (const gchar *)entry->key, entry, TRUE)) {
-			soup_cache_entry_free (entry, TRUE);
+		if (!soup_cache_entry_insert_by_key (cache, (const guint) entry->key, entry, TRUE)) {
+			soup_cache_entry_free (cache, entry, TRUE);
 			return;
 		}
 
@@ -948,7 +952,9 @@ msg_got_headers_cb (SoupMessage *msg, gpointer user_data)
 			g_signal_connect (msg, "restarted", G_CALLBACK (msg_restarted_cb), entry);
 
 		/* Prepare entry */
-		file = g_file_new_for_path (entry->filename);
+		filename = get_filename_from_key (cache, entry->key);
+		file = g_file_new_for_path (filename);
+		g_free (filename);
 		cache->priv->n_pending++;
 
 		entry->dirty = TRUE;
@@ -959,24 +965,22 @@ msg_got_headers_cb (SoupMessage *msg, gpointer user_data)
 				      (GAsyncReadyCallback) replace_cb, fixture);
 		g_object_unref (file);
 	} else if (cacheable & SOUP_CACHE_INVALIDATES) {
-		char *key;
+		guint key;
 		SoupCacheEntry *entry;
 
 		key = soup_message_get_cache_key (msg);
-		entry = g_hash_table_lookup (cache->priv->cache, key);
-		g_free (key);
+		entry = g_hash_table_lookup (cache->priv->cache, GUINT_TO_POINTER(key));
 
 		if (entry) {
 			if (soup_cache_entry_remove (cache, entry))
-				soup_cache_entry_free (entry, TRUE);
+				soup_cache_entry_free (cache, entry, TRUE);
 		}
 	} else if (cacheable & SOUP_CACHE_VALIDATES) {
-		char *key;
+		guint key;
 		SoupCacheEntry *entry;
 
 		key = soup_message_get_cache_key (msg);
-		entry = g_hash_table_lookup (cache->priv->cache, key);
-		g_free (key);
+		entry = g_hash_table_lookup (cache->priv->cache, GUINT_TO_POINTER(key));
 
 		/* It's possible to get a CACHE_VALIDATES with no
 		 * entry in the hash table. This could happen if for
@@ -999,18 +1003,15 @@ msg_got_headers_cb (SoupMessage *msg, gpointer user_data)
 GInputStream *
 soup_cache_send_response (SoupCache *cache, SoupMessage *msg)
 {
-	char *key;
 	SoupCacheEntry *entry;
-	char *current_age;
+	char *current_age, *filename;
 	GInputStream *stream = NULL;
 	GFile *file;
 
 	g_return_val_if_fail (SOUP_IS_CACHE (cache), NULL);
 	g_return_val_if_fail (SOUP_IS_MESSAGE (msg), NULL);
 
-	key = soup_message_get_cache_key (msg);
-	entry = g_hash_table_lookup (cache->priv->cache, key);
-	g_free (key);
+	entry = g_hash_table_lookup (cache->priv->cache, GUINT_TO_POINTER(soup_message_get_cache_key (msg)));
 	g_return_val_if_fail (entry, NULL);
 
 	/* If we are told to send a response from cache any validation
@@ -1034,7 +1035,9 @@ soup_cache_send_response (SoupCache *cache, SoupMessage *msg)
 	   some agreement here. Also we have to handle the situation
 	   were the file was no longer there (for example files
 	   removed without notifying the cache */
-	file = g_file_new_for_path (entry->filename);
+	filename = get_filename_from_key (cache, entry->key);
+	file = g_file_new_for_path (filename);
+	g_free (filename);
 	stream = G_INPUT_STREAM (g_file_read (file, NULL, NULL));
 	g_object_unref (file);
 
@@ -1080,10 +1083,7 @@ soup_cache_init (SoupCache *cache)
 
 	priv = cache->priv = SOUP_CACHE_GET_PRIVATE (cache);
 
-	priv->cache = g_hash_table_new_full (g_str_hash,
-					     g_str_equal,
-					     (GDestroyNotify)g_free,
-					     NULL);
+	priv->cache = g_hash_table_new (g_direct_hash, g_direct_equal);
 
 	/* LRU */
 	priv->lru_start = NULL;
@@ -1105,7 +1105,7 @@ remove_cache_item (gpointer data,
 	SoupCacheEntry *entry = (SoupCacheEntry *) data;
 
 	if (soup_cache_entry_remove (cache, entry))
-		soup_cache_entry_free (entry, FALSE);
+		soup_cache_entry_free (cache, entry, FALSE);
 }
 
 static void
@@ -1256,16 +1256,13 @@ soup_cache_new (const char *cache_dir, SoupCacheType cache_type)
 SoupCacheResponse
 soup_cache_has_response (SoupCache *cache, SoupMessage *msg)
 {
-	char *key;
 	SoupCacheEntry *entry;
 	const char *cache_control, *pragma;
 	gpointer value;
 	int max_age, max_stale, min_fresh;
 	GList *lru_item, *item;
 
-	key = soup_message_get_cache_key (msg);
-	entry = g_hash_table_lookup (cache->priv->cache, key);
-	g_free (key);
+	entry = g_hash_table_lookup (cache->priv->cache, GUINT_TO_POINTER(soup_message_get_cache_key (msg)));
 
 	/* 1. The presented Request-URI and that of stored response
 	 * match
@@ -1467,7 +1464,7 @@ clear_cache_item (gpointer data,
 	SoupCacheEntry *entry = (SoupCacheEntry *) data;
 
 	if (soup_cache_entry_remove (cache, entry))
-		soup_cache_entry_free (entry, TRUE);
+		soup_cache_entry_free (cache, entry, TRUE);
 }
 
 /**
@@ -1500,7 +1497,6 @@ soup_cache_generate_conditional_request (SoupCache *cache, SoupMessage *original
 	SoupMessage *msg;
 	SoupURI *uri;
 	SoupCacheEntry *entry;
-	char *key;
 	const char *value;
 
 	g_return_val_if_fail (SOUP_IS_CACHE (cache), NULL);
@@ -1516,9 +1512,7 @@ soup_cache_generate_conditional_request (SoupCache *cache, SoupMessage *original
 
 	/* Now add the validator entries in the header from the cached
 	   data */
-	key = soup_message_get_cache_key (original);
-	entry = g_hash_table_lookup (cache->priv->cache, key);
-	g_free (key);
+	entry = g_hash_table_lookup (cache->priv->cache, GUINT_TO_POINTER(soup_message_get_cache_key (original)));
 
 	g_return_val_if_fail (entry, NULL);
 
@@ -1540,22 +1534,17 @@ soup_cache_generate_conditional_request (SoupCache *cache, SoupMessage *original
 #define SOUP_CACHE_FILE "soup.cache"
 
 #define SOUP_CACHE_HEADERS_FORMAT "{ss}"
-#define SOUP_CACHE_PHEADERS_FORMAT "(ssbuuuuua" SOUP_CACHE_HEADERS_FORMAT ")"
+#define SOUP_CACHE_PHEADERS_FORMAT "(ubuuuuuv)"
 #define SOUP_CACHE_ENTRIES_FORMAT "a" SOUP_CACHE_PHEADERS_FORMAT
 
-/* Basically the same format than above except that some strings are
-   prepended with &. This way the GVariant returns a pointer to the
-   data instead of duplicating the string */
-#define SOUP_CACHE_DECODE_HEADERS_FORMAT "{&s&s}"
-
 static void
 pack_entry (gpointer data,
 	    gpointer user_data)
 {
 	SoupCacheEntry *entry = (SoupCacheEntry *) data;
 	SoupMessageHeadersIter iter;
-	const gchar *header_key, *header_value;
-	GVariantBuilder *headers_builder;
+	const char *header_key, *header_value;
+	GVariantBuilder headers_builder;
 	GVariantBuilder *entries_builder = (GVariantBuilder *)user_data;
 
 	/* Do not store non-consolidated entries */
@@ -1563,21 +1552,20 @@ pack_entry (gpointer data,
 		return;
 
 	/* Pack headers */
-	headers_builder = g_variant_builder_new (G_VARIANT_TYPE_ARRAY);
+	g_variant_builder_init (&headers_builder, G_VARIANT_TYPE ("a" SOUP_CACHE_HEADERS_FORMAT));
 	soup_message_headers_iter_init (&iter, entry->headers);
 	while (soup_message_headers_iter_next (&iter, &header_key, &header_value)) {
 		if (g_utf8_validate (header_value, -1, NULL))
-			g_variant_builder_add (headers_builder, SOUP_CACHE_HEADERS_FORMAT,
+			g_variant_builder_add (&headers_builder, SOUP_CACHE_HEADERS_FORMAT,
 					       header_key, header_value);
 	}
 
 	/* Entry data */
 	g_variant_builder_add (entries_builder, SOUP_CACHE_PHEADERS_FORMAT,
-			       entry->key, entry->filename, entry->must_revalidate,
+			       entry->key, entry->must_revalidate,
 			       entry->freshness_lifetime, entry->corrected_initial_age,
-			       entry->response_time, entry->hits, entry->length, headers_builder);
-
-	g_variant_builder_unref (headers_builder);
+			       entry->response_time, entry->hits, entry->length,
+			       g_variant_builder_end (&headers_builder));
 }
 
 void
@@ -1585,35 +1573,74 @@ soup_cache_dump (SoupCache *cache)
 {
 	SoupCachePrivate *priv = SOUP_CACHE_GET_PRIVATE (cache);
 	gchar *filename;
-	GVariantBuilder *entries_builder;
+	GVariantBuilder entries_builder;
 	GVariant *cache_variant;
 
-	if (!g_list_length (cache->priv->lru_start))
+	filename = g_build_filename (priv->cache_dir, SOUP_CACHE_FILE, NULL);
+	if (!g_list_length (cache->priv->lru_start)) {
+		g_file_set_contents (filename, 0, 0, NULL);
+		g_free (filename);
 		return;
+	}
 
 	/* Create the builder and iterate over all entries */
-	entries_builder = g_variant_builder_new (G_VARIANT_TYPE_ARRAY);
-	g_list_foreach (cache->priv->lru_start, pack_entry, entries_builder);
+	g_variant_builder_init (&entries_builder, G_VARIANT_TYPE (SOUP_CACHE_ENTRIES_FORMAT));
+	g_list_foreach (cache->priv->lru_start, pack_entry, &entries_builder);
 
 	/* Serialize and dump */
-	cache_variant = g_variant_new (SOUP_CACHE_ENTRIES_FORMAT, entries_builder);
-	g_variant_builder_unref (entries_builder);
-
-	filename = g_build_filename (priv->cache_dir, SOUP_CACHE_FILE, NULL);
+	cache_variant = g_variant_builder_end (&entries_builder);
+	g_variant_ref_sink (cache_variant);
 	g_file_set_contents (filename, (const gchar *)g_variant_get_data (cache_variant),
 			     g_variant_get_size (cache_variant), NULL);
 	g_free (filename);
 	g_variant_unref (cache_variant);
 }
 
+static void
+list_cache_files_cb (GObject *source, GAsyncResult *result, gpointer user_data)
+{
+	GFileEnumerator *file_enumerator;
+	GError *error = NULL;
+	GFileInfo *file_info;
+	SoupCache *cache = SOUP_CACHE (user_data);
+
+	file_enumerator = g_file_enumerate_children_finish (G_FILE (source), result, &error);
+	if (error) {
+		if (file_enumerator)
+			g_object_unref (file_enumerator);
+		g_error_free (error);
+		return;
+	}
+
+	while ((file_info = g_file_enumerator_next_file (file_enumerator, NULL, NULL)) != NULL) {
+		const gchar *filename = g_file_info_get_name (file_info);
+
+		if (strcmp (filename, SOUP_CACHE_FILE)) {
+			char *endptr = NULL;
+			guint key = strtoul (filename, &endptr, 10);
+
+			if (endptr || !g_hash_table_lookup (cache->priv->cache, GUINT_TO_POINTER(key))) {
+				GFile *cache_file = g_file_get_child (G_FILE (source), filename);
+				g_debug ("removing corrupt file from cache %s", filename);
+				g_file_delete (cache_file, NULL, NULL);
+				g_object_unref (cache_file);
+			}
+		}
+	}
+
+	g_object_unref (file_enumerator);
+}
+
 void
 soup_cache_load (SoupCache *cache)
 {
 	gchar *filename = NULL, *contents = NULL;
-	GVariant *cache_variant;
-	GVariantIter *entries_iter, *headers_iter;
-	GVariantType *variant_format;
-	gsize length;
+	gboolean must_revalidate;
+	guint freshness_lifetime, hits, key;
+	time_t corrected_initial_age, response_time;
+	GVariant *cache_variant, *headers_variant;
+	GVariantIter entries_iter;
+	gsize length, items;
 	SoupCacheEntry *entry;
 	SoupCachePrivate *priv = cache->priv;
 
@@ -1625,45 +1652,64 @@ soup_cache_load (SoupCache *cache)
 	}
 	g_free (filename);
 
-	variant_format = g_variant_type_new (SOUP_CACHE_ENTRIES_FORMAT);
-	cache_variant = g_variant_new_from_data (variant_format, (const gchar *)contents, length, FALSE, g_free, contents);
-	g_variant_type_free (variant_format);
+	cache_variant = g_variant_new_from_data (G_VARIANT_TYPE (SOUP_CACHE_ENTRIES_FORMAT),
+						 (const gchar *) contents, length, FALSE, g_free, contents);
+	items = g_variant_iter_init (&entries_iter, cache_variant);
+	g_debug ("Loading %li items from cache", items);
 
-	g_variant_get (cache_variant, SOUP_CACHE_ENTRIES_FORMAT, &entries_iter);
-	entry = g_slice_new0 (SoupCacheEntry);
+	while (g_variant_iter_loop (&entries_iter, SOUP_CACHE_PHEADERS_FORMAT,
+				    &key, &must_revalidate,
+				    &freshness_lifetime, &corrected_initial_age,
+				    &response_time, &hits, &length,
+                                    &headers_variant)) {
 
-	while (g_variant_iter_loop (entries_iter, SOUP_CACHE_PHEADERS_FORMAT,
-				    &entry->key, &entry->filename, &entry->must_revalidate,
-				    &entry->freshness_lifetime, &entry->corrected_initial_age,
-				    &entry->response_time, &entry->hits, &entry->length,
-                                    &headers_iter)) {
 		const gchar *header_key, *header_value;
+		GVariantIter headers_iter;
+		SoupMessageHeaders *headers;
+
+		/* If we don't have an array of headers then it means
+		   that we have corrupt data on the cache. It could be
+		   that the cache has data in the old format */
+		g_variant_iter_init (&headers_iter, headers_variant);
+		if (!g_variant_is_of_type (headers_variant, G_VARIANT_TYPE_ARRAY))
+			continue;
 
 		/* SoupMessage Headers */
-		entry->headers = soup_message_headers_new (SOUP_MESSAGE_HEADERS_RESPONSE);
-		while (g_variant_iter_loop (headers_iter, SOUP_CACHE_DECODE_HEADERS_FORMAT, &header_key, &header_value))
-			soup_message_headers_append (entry->headers, header_key, header_value);
+		headers = soup_message_headers_new (SOUP_MESSAGE_HEADERS_RESPONSE);
+		while (g_variant_iter_loop (&headers_iter, SOUP_CACHE_HEADERS_FORMAT, &header_key, &header_value))
+			soup_message_headers_append (headers, header_key, header_value);
 
 		/* Insert in cache */
-		if (!soup_cache_entry_insert_by_key (cache, (const gchar *)entry->key, entry, FALSE))
-			soup_cache_entry_free (entry, TRUE);
+		entry = g_malloc0 (sizeof (SoupCacheEntry));
+		entry->key = key;
+		entry->must_revalidate = must_revalidate;
+		entry->freshness_lifetime = freshness_lifetime;
+		entry->corrected_initial_age = corrected_initial_age;
+		entry->response_time = response_time;
+		entry->hits = hits;
+		entry->length = length;
+		entry->headers = headers;
 
-		/* New entry for the next iteration. This creates an
-		   extra object the last iteration but it's worth it
-		   as we save several if's */
-		entry = g_slice_new0 (SoupCacheEntry);
+		if (!soup_cache_entry_insert_by_key (cache, (const guint) entry->key, entry, FALSE))
+			soup_cache_entry_free (cache, entry, TRUE);
 	}
-	/* Remove last created entry */
-	g_slice_free (SoupCacheEntry, entry);
 
-	/* Sort LRU (shouldn't be needed). First reverse as elements
-	 * are always prepended when inserting
-	 */
-	cache->priv->lru_start = g_list_reverse (cache->priv->lru_start);
-	cache->priv->lru_start = g_list_sort (cache->priv->lru_start, lru_compare_func);
+	if (g_list_length (cache->priv->lru_start)) {
+		cache->priv->lru_start = g_list_reverse (cache->priv->lru_start);
+		cache->priv->lru_start = g_list_sort (cache->priv->lru_start, lru_compare_func);
+	} else {
+		/* If we could not import any entry in the cache then
+		 * it means that the cache data is corrupt or uses an
+		 * old format. In that case we just wipe the files.
+		 */
+		GFile *cache_dir_file = g_file_new_for_path (cache->priv->cache_dir);
+		g_file_enumerate_children_async (cache_dir_file, G_FILE_ATTRIBUTE_STANDARD_NAME,
+						 G_FILE_QUERY_INFO_NONE, G_PRIORITY_LOW, NULL,
+						 list_cache_files_cb, cache);
+		g_object_unref (cache_dir_file);
+	}
 
 	/* frees */
-	g_variant_iter_free (entries_iter);
 	g_variant_unref (cache_variant);
 }
 
