netsurf: branch master updated. release/3.9-484-g859972d

[Commit Mailer]

Gitweb links:

...log 
http://git.netsurf-browser.org/netsurf.git/shortlog/859972df714b0c91bf7fd181796d34451f07e9f2
...commit 
http://git.netsurf-browser.org/netsurf.git/commit/859972df714b0c91bf7fd181796d34451f07e9f2
...tree 
http://git.netsurf-browser.org/netsurf.git/tree/859972df714b0c91bf7fd181796d34451f07e9f2

The branch, master has been updated
       via  859972df714b0c91bf7fd181796d34451f07e9f2 (commit)
       via  ac75a9161e23b7073edcf0ec07d584b87d2e0e08 (commit)
       via  088917641f0865e11be5e81bf90de3dbc8cba19e (commit)
       via  3e02961ec8f21fd656c8b306c5075c0c799df97f (commit)
       via  54b1960d18042cf6dfd86cfe01d58455357586d2 (commit)
       via  fd80341513813684ba3155b87e4e6cc8c87631f1 (commit)
       via  61187d31ab7ba292510e1e56886325a1c6a1c822 (commit)
      from  be659af7e563527270a8725ae42ecf7c25aecc7e (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commitdiff 
http://git.netsurf-browser.org/netsurf.git/commit/?id=859972df714b0c91bf7fd181796d34451f07e9f2
commit 859972df714b0c91bf7fd181796d34451f07e9f2
Author: Daniel Silverstone <dsilv...@digital-scurf.org>
Commit: Daniel Silverstone <dsilv...@digital-scurf.org>

    llcache: Rework fs_backing_store to use hashmap
    
    As a result, we no longer waste a bunch of RAM on the entries
    tables.  This ought to be no slower, and more memory efficient.
    
    Signed-off-by: Daniel Silverstone <dsilv...@digital-scurf.org>

diff --git a/content/fs_backing_store.c b/content/fs_backing_store.c
index 19eb1ca..71d1c83 100644
--- a/content/fs_backing_store.c
+++ b/content/fs_backing_store.c
@@ -49,6 +49,7 @@
 #include "utils/nsurl.h"
 #include "utils/log.h"
 #include "utils/messages.h"
+#include "utils/hashmap.h"
 #include "desktop/gui_internal.h"
 #include "netsurf/misc.h"
 
@@ -61,20 +62,11 @@
 #define DEFAULT_ENTRY_SIZE 16
 
 /** Backing store file format version */
-#define CONTROL_VERSION 130
+#define CONTROL_VERSION 200
 
 /** Number of milliseconds after a update before control data maintenance is 
performed  */
 #define CONTROL_MAINT_TIME 10000
 
-/** Get address from ident */
-#define BS_ADDRESS(ident, state) ((ident) & ((1 << state->ident_bits) - 1))
-
-/** Lookup store entry index from ident */
-#define BS_ENTRY_INDEX(ident, state) state->addrmap[(ident) & ((1 << 
state->ident_bits) - 1)]
-
-/** Get store entry from ident. */
-#define BS_ENTRY(ident, state) state->entries[state->addrmap[(ident) & ((1 << 
state->ident_bits) - 1)]]
-
 /** Filename of serialised entries */
 #define ENTRIES_FNAME "entries"
 
@@ -184,8 +176,8 @@ struct store_entry_element {
  * @note Order is important to avoid excessive structure packing overhead.
  */
 struct store_entry {
+       nsurl *url; /**< The URL for this entry */
        int64_t last_used; /**< UNIX time the entry was last used */
-       entry_ident_t ident; /**< entry identifier */
        uint16_t use_count; /**< number of times this entry has been accessed */
        uint8_t flags; /**< entry flags */
        /** Entry element (data or meta) specific information */
@@ -219,29 +211,16 @@ struct store_state {
        size_t limit; /**< The backing store upper bound target size */
        size_t hysteresis; /**< The hysteresis around the target size */
 
-       unsigned int ident_bits; /**< log2 number of bits to use for address. */
-
-
-       /* cache entry management */
-       struct store_entry *entries; /**< store entries. */
-       unsigned int entry_bits; /**< log2 number of bits in entry index. */
-       unsigned int last_entry; /**< index of last usable entry. */
+       /**
+        * The cache object hash
+        */
+       hashmap_t *entries;
 
        /** flag indicating if the entries have been made persistent
         * since they were last changed.
         */
        bool entries_dirty;
 
-       /**
-        * URL identifier to entry index mapping.
-        *
-        * This is an open coded index on the entries URL field and
-        * provides a computationally inexpensive way to go from the
-        * URL to an entry.
-        */
-       entry_index_t *addrmap;
-
-
        /** small block indexes */
        struct block_file blocks[ENTRY_ELEM_COUNT][BLOCK_FILE_COUNT];
 
@@ -273,60 +252,44 @@ struct store_state {
  */
 struct store_state *storestate;
 
-
-/**
- * Remove a backing store entry from the entry table.
- *
- * This finds the store entry associated with the given key and
- * removes it from the table. The removed entry is returned but is
- * only valid until the next set_store_entry call.
+/* Entries hashmap parameters
  *
- * @param[in] state The store state to use.
- * @param[in, out] bse Pointer to the entry to be removed.
- * @return NSERROR_OK and \a bse updated on success or NSERROR_NOT_FOUND
- *         if no entry corresponds to the URL.
+ * Our hashmap has nsurl keys and store_entry values
  */
-static nserror
-remove_store_entry(struct store_state *state, struct store_entry **bse)
-{
-       entry_index_t sei; /* store entry index */
-
-       /* sei is index to entry to be removed, we swap it to the end
-        * of the table so there are no gaps and the returned entry is
-        * held in storage with reasonable lifetime.
-        */
-
-       sei = BS_ENTRY_INDEX((*bse)->ident, state);
-
-       /* remove entry from map */
-       BS_ENTRY_INDEX((*bse)->ident, state) = 0;
 
-       /* global allocation accounting  */
-       state->total_alloc -= state->entries[sei].elem[ENTRY_ELEM_DATA].size;
-       state->total_alloc -= state->entries[sei].elem[ENTRY_ELEM_META].size;
-
-       state->last_entry--;
-
-       if (sei == state->last_entry) {
-               /* the removed entry was the last one, how convenient */
-               *bse = &state->entries[sei];
-       } else {
-               /* need to swap entries */
-               struct store_entry tent;
-
-               tent = state->entries[sei];
-               state->entries[sei] = state->entries[state->last_entry];
-               state->entries[state->last_entry] = tent;
-
-               /* update map for moved entry */
-               BS_ENTRY_INDEX(state->entries[sei].ident, state) = sei;
+static bool
+entries_hashmap_key_eq(void *key1, void *key2)
+{
+       return nsurl_compare((nsurl *)key1, (nsurl *)key2, NSURL_COMPLETE);
+}
 
-               *bse = &state->entries[state->last_entry];
+static void *
+entries_hashmap_value_alloc(void *key)
+{
+       struct store_entry *ent = calloc(1, sizeof(struct store_entry));
+       if (ent != NULL) {
+               ent->url = nsurl_ref(key);
        }
+       return ent;
+}
 
-       return NSERROR_OK;
+static void
+entries_hashmap_value_destroy(void *value)
+{
+       struct store_entry *ent = value;
+       /** \todo Do we need to do any disk cleanup here?  if so, meep! */
+       nsurl_unref(ent->url);
+       free(ent);
 }
 
+static hashmap_parameters_t entries_hashmap_parameters = {
+       .key_clone = (hashmap_key_clone_t)nsurl_ref,
+       .key_destroy = (hashmap_key_destroy_t)nsurl_unref,
+       .key_hash = (hashmap_key_hash_t)nsurl_hash,
+       .key_eq = entries_hashmap_key_eq,
+       .value_alloc = entries_hashmap_value_alloc,
+       .value_destroy = entries_hashmap_value_destroy,
+};
 
 /**
  * Generate a filename for an object.
@@ -484,7 +447,7 @@ invalidate_element(struct store_state *state,
                char *fname;
 
                /* unlink the file from disc */
-               fname = store_fname(state, bse->ident, elem_idx);
+               fname = store_fname(state, nsurl_hash(bse->url), elem_idx);
                if (fname == NULL) {
                        return NSERROR_NOMEM;
                }
@@ -492,6 +455,8 @@ invalidate_element(struct store_state *state,
                free(fname);
        }
 
+       state->total_alloc -= bse->elem[elem_idx].size;
+
        return NSERROR_OK;
 }
 
@@ -519,29 +484,27 @@ invalidate_entry(struct store_state *state, struct 
store_entry *bse)
                 * This entry cannot be immediately removed as it has
                 * associated allocation so wait for allocation release.
                 */
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, DEBUG,
                      "invalidating entry with referenced allocation");
                return NSERROR_OK;
        }
 
-       NSLOG(netsurf, INFO, "Removing entry for %p", bse);
-
-       /* remove the entry from the index */
-       ret = remove_store_entry(state, &bse);
-       if (ret != NSERROR_OK) {
-               return ret;
-       }
+       NSLOG(netsurf, VERBOSE, "Removing entry for %s", 
nsurl_access(bse->url));
 
        ret = invalidate_element(state, bse, ENTRY_ELEM_META);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "Error invalidating metadata element");
+               NSLOG(netsurf, ERROR, "Error invalidating metadata element");
        }
 
        ret = invalidate_element(state, bse, ENTRY_ELEM_DATA);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "Error invalidating data element");
+               NSLOG(netsurf, ERROR, "Error invalidating data element");
        }
 
+       /* As our final act we remove bse from the cache */
+       hashmap_remove(state->entries, bse->url);
+       /* From now, bse is invalid memory */
+
        return NSERROR_OK;
 }
 
@@ -551,8 +514,8 @@ invalidate_entry(struct store_state *state, struct 
store_entry *bse)
  */
 static int compar(const void *va, const void *vb)
 {
-       const struct store_entry *a = &BS_ENTRY(*(entry_ident_t *)va, 
storestate);
-       const struct store_entry *b = &BS_ENTRY(*(entry_ident_t *)vb, 
storestate);
+       const struct store_entry *a = *(const struct store_entry **)va;
+       const struct store_entry *b = *(const struct store_entry **)vb;
 
        /* consider the allocation flags - if an entry has an
         * allocation it is considered more valuable as it cannot be
@@ -591,6 +554,22 @@ static int compar(const void *va, const void *vb)
        return 0;
 }
 
+typedef struct {
+       struct store_entry **elist;
+       size_t ent_count;
+} eviction_state_t;
+
+/**
+ * Iterator for gathering entries to compute eviction order
+ */
+static bool
+entry_eviction_iterator_cb(void *key, void *value, void *ctx)
+{
+       eviction_state_t *estate = ctx;
+       struct store_entry *ent = value;
+       estate->elist[estate->ent_count++] = ent;
+       return false;
+}
 
 /**
  * Evict entries from backing store as per configuration.
@@ -608,15 +587,14 @@ static int compar(const void *va, const void *vb)
  */
 static nserror store_evict(struct store_state *state)
 {
-       entry_ident_t *elist; /* sorted list of entry identifiers */
-       unsigned int ent;
-       unsigned int ent_count;
-       size_t removed; /* size of removed entries */
+       size_t ent = 0;
+       size_t removed = 0; /* size of removed entries */
        nserror ret = NSERROR_OK;
+       size_t old_count;
+       eviction_state_t estate;
 
        /* check if the cache has exceeded configured limit */
-       if ((state->total_alloc < state->limit) &&
-           (state->last_entry < (1U << state->entry_bits))) {
+       if (state->total_alloc < state->limit) {
                /* cache within limits */
                return NSERROR_OK;
        }
@@ -627,24 +605,31 @@ static nserror store_evict(struct store_state *state)
              state->hysteresis);
 
        /* allocate storage for the list */
-       elist = malloc(sizeof(entry_ident_t) * state->last_entry);
-       if (elist == NULL) {
+       old_count = hashmap_count(state->entries);
+       estate.ent_count = 0;
+       estate.elist = malloc(sizeof(struct state_entry*) * old_count);
+       if (estate.elist == NULL) {
                return NSERROR_NOMEM;
        }
 
-       /* sort the list avoiding entry 0 which is the empty sentinel */
-       for (ent = 1; ent < state->last_entry; ent++) {
-               elist[ent - 1] = state->entries[ent].ident;
+       if (hashmap_iterate(state->entries, entry_eviction_iterator_cb, 
&estate)) {
+               NSLOG(netsurf, WARNING, "Unexpected termination of eviction 
iterator");
+               free(estate.elist);
+               return NSERROR_UNKNOWN;
        }
-       ent_count = ent - 1; /* important to keep this as the entry count will 
change when entries are removed */
-       qsort(elist, ent_count, sizeof(entry_ident_t), compar);
+
+       if (old_count != estate.ent_count) {
+               NSLOG(netsurf, WARNING, "Incorrect entry count after eviction 
iterator");
+               free(estate.elist);
+               return NSERROR_UNKNOWN;
+       }
+
+       qsort(estate.elist, estate.ent_count, sizeof(struct state_entry*), 
compar);
 
        /* evict entries in listed order */
        removed = 0;
-       for (ent = 0; ent < ent_count; ent++) {
-               struct store_entry *bse;
-
-               bse = &BS_ENTRY(elist[ent], state);
+       for (ent = 0; ent < estate.ent_count; ent++) {
+               struct store_entry *bse = estate.elist[ent];
 
                removed += bse->elem[ENTRY_ELEM_DATA].size;
                removed += bse->elem[ENTRY_ELEM_META].size;
@@ -659,14 +644,55 @@ static nserror store_evict(struct store_state *state)
                }
        }
 
-       free(elist);
+       free(estate.elist);
 
-       NSLOG(netsurf, INFO, "removed %"PRIsizet" in %d entries", removed,
-             ent);
+       NSLOG(netsurf, INFO,
+             "removed %"PRIsizet" in %"PRIsizet" entries, %"PRIsizet" 
remaining in %"PRIsizet" entries",
+             removed, ent, state->total_alloc, old_count - ent);
 
        return ret;
 }
 
+/**
+ * Write a single store entry to disk
+ *
+ * To serialise a single store entry for now we write out a 32bit int
+ * which is the length of the url, then that many bytes of the url.
+ * Then we write out the full store entry struct as-is, which includes
+ * a useless nsurl pointer.
+ */
+static nserror
+write_entry(struct store_entry *ent, int fd)
+{
+       uint32_t len = strlen(nsurl_access(ent->url));
+       if (write(fd, &len, sizeof(len)) != sizeof(len))
+               return NSERROR_SAVE_FAILED;
+       if (write(fd, nsurl_access(ent->url), len) != len)
+               return NSERROR_SAVE_FAILED;
+       if (write(fd, ent, sizeof(*ent)) != sizeof(*ent))
+               return NSERROR_SAVE_FAILED;
+
+       return NSERROR_OK;
+}
+
+typedef struct {
+       int fd;
+       size_t written;
+} write_entry_iteration_state;
+
+/**
+ * Callback for iterating the entries hashmap
+ */
+static bool
+write_entry_iterator(void *key, void *value, void *ctx)
+{
+       /* We ignore the key */
+       struct store_entry *ent = value;
+       write_entry_iteration_state *state = ctx;
+       state->written++;
+       /* We stop early if we fail to write this entry */
+       return write_entry(ent, state->fd) != NSERROR_OK;
+}
 
 /**
  * Write filesystem entries to file.
@@ -678,13 +704,13 @@ static nserror store_evict(struct store_state *state)
  */
 static nserror write_entries(struct store_state *state)
 {
-       int fd;
        char *tname = NULL; /* temporary file name for atomic replace */
        char *fname = NULL; /* target filename */
-       size_t entries_size;
-       size_t written;
+       write_entry_iteration_state weistate;
        nserror ret;
 
+       memset(&weistate, 0, sizeof(weistate));
+
        if (state->entries_dirty == false) {
                /* entries have not been updated since last write */
                return NSERROR_OK;
@@ -695,25 +721,22 @@ static nserror write_entries(struct store_state *state)
                return ret;
        }
 
-       fd = open(tname, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR);
-       if (fd == -1) {
+       weistate.fd = open(tname, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | 
S_IWUSR);
+       if (weistate.fd == -1) {
                free(tname);
                return NSERROR_SAVE_FAILED;
        }
 
-       entries_size = state->last_entry * sizeof(struct store_entry);
-
-       written = (size_t)write(fd, state->entries, entries_size);
-
-       close(fd);
-
-       /* check all data was written */
-       if (written != entries_size) {
+       if (hashmap_iterate(state->entries, write_entry_iterator, &weistate)) {
+               /* The iteration ended early, so we failed */
+               close(weistate.fd);
                unlink(tname);
                free(tname);
                return NSERROR_SAVE_FAILED;
        }
 
+       close(weistate.fd);
+
        ret = netsurf_mkpath(&fname, NULL, 2, state->path, ENTRIES_FNAME);
        if (ret != NSERROR_OK) {
                unlink(tname);
@@ -730,6 +753,8 @@ static nserror write_entries(struct store_state *state)
                return NSERROR_SAVE_FAILED;
        }
 
+       NSLOG(netsurf, INFO, "Wrote out %"PRIsizet" entries", weistate.written);
+
        return NSERROR_OK;
 }
 
@@ -777,7 +802,7 @@ static nserror write_blocks(struct store_state *state)
                                   &state->blocks[elem_idx][bfidx].use_map[0],
                                   BLOCK_USE_MAP_SIZE);
                        if (wr != BLOCK_USE_MAP_SIZE) {
-                               NSLOG(netsurf, INFO,
+                               NSLOG(netsurf, DEBUG,
                                      "writing block file %d use index on file 
number %d failed",
                                      elem_idx,
                                      bfidx);
@@ -836,21 +861,21 @@ static nserror set_block_extents(struct store_state 
*state)
                return NSERROR_OK;
        }
 
-       NSLOG(netsurf, INFO, "Starting");
+       NSLOG(netsurf, DEBUG, "Starting");
        for (elem_idx = 0; elem_idx < ENTRY_ELEM_COUNT; elem_idx++) {
                for (bfidx = 0; bfidx < BLOCK_FILE_COUNT; bfidx++) {
                        if (state->blocks[elem_idx][bfidx].fd != -1) {
                                /* ensure block file is correct extent */
                                ftr = 
ftruncate(state->blocks[elem_idx][bfidx].fd, 1U << (log2_block_size[elem_idx] + 
BLOCK_ENTRY_COUNT));
                                if (ftr == -1) {
-                                       NSLOG(netsurf, INFO,
+                                       NSLOG(netsurf, ERROR,
                                              "Truncate failed errno:%d",
                                              errno);
                                }
                        }
                }
        }
-       NSLOG(netsurf, INFO, "Complete");
+       NSLOG(netsurf, DEBUG, "Complete");
 
        state->blocks_opened = false;
 
@@ -866,7 +891,7 @@ static nserror set_block_extents(struct store_state *state)
  *
  * \param s store state to maintain.
  */
-static void control_maintinance(void *s)
+static void control_maintenance(void *s)
 {
        struct store_state *state = s;
 
@@ -892,36 +917,22 @@ static void control_maintinance(void *s)
 static nserror
 get_store_entry(struct store_state *state, nsurl *url, struct store_entry 
**bse)
 {
-       entry_ident_t ident;
-       unsigned int sei; /* store entry index */
-
-       NSLOG(netsurf, INFO, "url:%s", nsurl_access(url));
-
-       /* use the url hash as the entry identifier */
-       ident = nsurl_hash(url);
+       struct store_entry *ent;
 
-       sei = BS_ENTRY_INDEX(ident, state);
+       ent = hashmap_lookup(state->entries, url);
 
-       if (sei == 0) {
-               NSLOG(netsurf, INFO, "Failed to find ident 0x%x in index",
-                     ident);
+       if (ent == NULL) {
                return NSERROR_NOT_FOUND;
        }
 
-       if (state->entries[sei].ident != ident) {
-               /* entry ident did not match */
-               NSLOG(netsurf, INFO, "ident did not match entry");
-               return NSERROR_NOT_FOUND;
-       }
-
-       *bse = &state->entries[sei];
+       *bse = ent;
 
-       state->entries[sei].last_used = time(NULL);
-       state->entries[sei].use_count++;
+       ent->last_used = time(NULL);
+       ent->use_count++;
 
        state->entries_dirty = true;
 
-       guit->misc->schedule(CONTROL_MAINT_TIME, control_maintinance, state);
+       guit->misc->schedule(CONTROL_MAINT_TIME, control_maintenance, state);
 
        return NSERROR_OK;
 }
@@ -979,13 +990,11 @@ set_store_entry(struct store_state *state,
                const size_t datalen,
                struct store_entry **bse)
 {
-       entry_ident_t ident;
-       entry_index_t sei; /* store entry index */
        struct store_entry *se;
        nserror ret;
        struct store_entry_element *elem;
 
-       NSLOG(netsurf, INFO, "url:%s", nsurl_access(url));
+       NSLOG(netsurf, DEBUG, "url:%s", nsurl_access(url));
 
        /* evict entries as required and ensure there is at least one
         * new entry available.
@@ -995,40 +1004,12 @@ set_store_entry(struct store_state *state,
                return ret;
        }
 
-       /* use the url hash as the entry identifier */
-       ident = nsurl_hash(url);
-
-       /* get the entry index from the ident */
-       sei = BS_ENTRY_INDEX(ident, state);
-       if (sei == 0) {
-               /* allocating the next available entry */
-               sei = state->last_entry;
-               state->last_entry++;
-               BS_ENTRY_INDEX(ident, state) = sei;
-
-               /* the entry */
-               se = &state->entries[sei];
-
-               /* clear the new entry */
-               memset(se, 0, sizeof(struct store_entry));
-       } else {
-               /* index found existing entry */
-
-               /* the entry */
-               se = &state->entries[sei];
-
-               if (se->ident != ident) {
-                       /** @todo Is there a better heuristic than
-                        * first come, first served? Should we check
-                        * to see if the old entry is in use and if
-                        * not prefer the newly stored entry instead?
-                        */
-                       NSLOG(netsurf, INFO,
-                             "Entry index collision trying to replace %x with 
%x",
-                             se->ident,
-                             ident);
-                       return NSERROR_PERMISSION;
-               }
+       se = hashmap_lookup(state->entries, url);
+       if (se == NULL) {
+               se = hashmap_insert(state->entries, url);
+       }
+       if (se == NULL) {
+               return NSERROR_NOMEM;
        }
 
        /* the entry element */
@@ -1039,13 +1020,12 @@ set_store_entry(struct store_state *state,
                /* this entry cannot be removed as it has associated
                 * allocation.
                 */
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, ERROR,
                      "attempt to overwrite entry with in use data");
                return NSERROR_PERMISSION;
        }
 
        /* set the common entry data */
-       se->ident = ident;
        se->use_count = 1;
        se->last_used = time(NULL);
 
@@ -1066,7 +1046,7 @@ set_store_entry(struct store_state *state,
 
        /* ensure control maintenance scheduled. */
        state->entries_dirty = true;
-       guit->misc->schedule(CONTROL_MAINT_TIME, control_maintinance, state);
+       guit->misc->schedule(CONTROL_MAINT_TIME, control_maintenance, state);
 
        *bse = se;
 
@@ -1099,7 +1079,7 @@ store_open(struct store_state *state,
 
        fname = store_fname(state, ident, elem_idx);
        if (fname == NULL) {
-               NSLOG(netsurf, INFO, "filename error");
+               NSLOG(netsurf, ERROR, "filename error");
                return -1;
        }
 
@@ -1107,14 +1087,14 @@ store_open(struct store_state *state,
        if (openflags & O_CREAT) {
                ret = netsurf_mkdir_all(fname);
                if (ret != NSERROR_OK) {
-                       NSLOG(netsurf, INFO,
+                       NSLOG(netsurf, WARNING,
                              "file path \"%s\" could not be created", fname);
                        free(fname);
                        return -1;
                }
        }
 
-       NSLOG(netsurf, INFO, "opening %s", fname);
+       NSLOG(netsurf, DEBUG, "opening %s", fname);
        fd = open(fname, openflags, S_IRUSR | S_IWUSR);
 
        free(fname);
@@ -1122,57 +1102,6 @@ store_open(struct store_state *state,
        return fd;
 }
 
-/**
- * Construct address ident to filesystem entry map
- *
- * To allow a filesystem entry to be found from it's identifier we
- * construct an mapping index. This is a hash map from the entries URL
- * (its unique key) to filesystem entry.
- *
- * As the entire entry list must be iterated over to construct the map
- * we also compute the total storage in use.
- *
- * @param state The backing store global state.
- * @return NSERROR_OK on success or NSERROR_NOMEM if the map storage
- *         could not be allocated.
- */
-static nserror
-build_entrymap(struct store_state *state)
-{
-       unsigned int eloop;
-
-       NSLOG(netsurf, INFO, "Allocating %"PRIsizet" bytes for max of %d 
buckets",
-             (1 << state->ident_bits) * sizeof(entry_index_t),
-             1 << state->ident_bits);
-
-       state->addrmap = calloc(1 << state->ident_bits, sizeof(entry_index_t));
-       if (state->addrmap == NULL) {
-               return NSERROR_NOMEM;
-       }
-
-       state->total_alloc = 0;
-
-       for (eloop = 1; eloop < state->last_entry; eloop++) {
-
-               NSLOG(llcache, DEEPDEBUG,
-                     "entry:%d ident:0x%08x used:%d",
-                     eloop,
-                     BS_ADDRESS(state->entries[eloop].ident, state),
-                     state->entries[eloop].use_count);
-
-               /* update the address map to point at the entry */
-               BS_ENTRY_INDEX(state->entries[eloop].ident, state) = eloop;
-
-               /* account for the storage space */
-               state->total_alloc += 
state->entries[eloop].elem[ENTRY_ELEM_DATA].size;
-               state->total_alloc += 
state->entries[eloop].elem[ENTRY_ELEM_META].size;
-               /* ensure entry does not have any allocation state */
-               state->entries[eloop].elem[ENTRY_ELEM_DATA].flags &= 
~(ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP);
-               state->entries[eloop].elem[ENTRY_ELEM_META].flags &= 
~(ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP);
-       }
-
-       return NSERROR_OK;
-}
 
 /**
  * Unlink entries file
@@ -1206,46 +1135,74 @@ unlink_entries(struct store_state *state)
 static nserror
 read_entries(struct store_state *state)
 {
-       int fd;
-       ssize_t rd;
-       size_t entries_size;
        char *fname = NULL;
+       char *url;
+       nsurl *nsurl;
        nserror ret;
+       size_t read_entries = 0;
+       struct store_entry *ent;
+       int fd;
 
        ret = netsurf_mkpath(&fname, NULL, 2, state->path, ENTRIES_FNAME);
        if (ret != NSERROR_OK) {
                return ret;
        }
 
-       entries_size = (1 << state->entry_bits) * sizeof(struct store_entry);
-
-       NSLOG(netsurf, INFO,
-             "Allocating %"PRIsizet" bytes for max of %d entries of 
%"PRIsizet" length elements %"PRIsizet" length",
-             entries_size,
-             1 << state->entry_bits,
-             sizeof(struct store_entry),
-             sizeof(struct store_entry_element));
-
-       state->entries = calloc(1, entries_size);
+       state->entries = hashmap_create(&entries_hashmap_parameters);
        if (state->entries == NULL) {
                free(fname);
                return NSERROR_NOMEM;
        }
 
        fd = open(fname, O_RDWR);
-       free(fname);
        if (fd != -1) {
-               rd = read(fd, state->entries, entries_size);
-               close(fd);
-               if (rd > 0) {
-                       state->last_entry = rd / sizeof(struct store_entry);
-                       NSLOG(netsurf, INFO, "Read %d entries",
-                             state->last_entry);
+               uint32_t urllen;
+               while (read(fd, &urllen, sizeof(urllen)) == sizeof(urllen)) {
+                       url = calloc(1, urllen+1);
+                       if (read(fd, url, urllen) != urllen) {
+                               free(url);
+                               close(fd);
+                               free(fname);
+                               return NSERROR_INIT_FAILED;
+                       }
+                       ret = nsurl_create(url, &nsurl);
+                       if (ret != NSERROR_OK) {
+                               free(url);
+                               close(fd);
+                               free(fname);
+                               return ret;
+                       }
+                       free(url);
+                       /* We have to be careful here about nsurl refs */
+                       ent = hashmap_insert(state->entries, nsurl);
+                       if (ent == NULL) {
+                               nsurl_unref(nsurl);
+                               close(fd);
+                               free(fname);
+                               return NSERROR_NOMEM;
+                       }
+                       /* At this point, ent actually owns a ref of nsurl */
+                       if (read(fd, ent, sizeof(*ent)) != sizeof(*ent)) {
+                               /* The read failed, so reset the ptr */
+                               ent->url = nsurl; /* It already had a ref */
+                               nsurl_unref(nsurl);
+                               close(fd);
+                               free(fname);
+                               return NSERROR_INIT_FAILED;
+                       }
+                       ent->url = nsurl; /* It already owns a ref */
+                       nsurl_unref(nsurl);
+                       NSLOG(netsurf, DEBUG, "Successfully read entry for %s", 
nsurl_access(ent->url));
+                       read_entries++;
+                       state->total_alloc += ent->elem[ENTRY_ELEM_DATA].size;
+                       state->total_alloc += ent->elem[ENTRY_ELEM_META].size;
                }
-       } else {
-               /* could rebuild entries from fs */
-               state->last_entry = 1;
+               close(fd);
        }
+
+       NSLOG(netsurf, INFO, "Read %"PRIsizet" entries from cache", 
read_entries);
+
+       free(fname);
        return NSERROR_OK;
 }
 
@@ -1283,7 +1240,7 @@ read_blocks(struct store_state *state)
                                          
&state->blocks[elem_idx][bfidx].use_map[0],
                                          BLOCK_USE_MAP_SIZE);
                                if (rd <= 0) {
-                                       NSLOG(netsurf, INFO,
+                                       NSLOG(netsurf, ERROR,
                                              "reading block file %d use index 
on file number %d failed",
                                              elem_idx,
                                              bfidx);
@@ -1382,9 +1339,6 @@ write_control(struct store_state *state)
        }
 
        fprintf(fcontrol, "%u%c", CONTROL_VERSION, 0);
-       fprintf(fcontrol, "%u%c", state->entry_bits, 0);
-       fprintf(fcontrol, "%u%c", state->ident_bits, 0);
-       fprintf(fcontrol, "%u%c", state->last_entry, 0);
 
        fclose(fcontrol);
 
@@ -1404,8 +1358,6 @@ read_control(struct store_state *state)
        nserror ret;
        FILE *fcontrol;
        unsigned int ctrlversion;
-       unsigned int addrbits;
-       unsigned int entrybits;
        char *fname = NULL;
 
        ret = netsurf_mkpath(&fname, NULL, 2, state->path, "control");
@@ -1443,27 +1395,8 @@ read_control(struct store_state *state)
                goto control_error;
        }
 
-       /* second line is log2 max number of entries */
-       if (fscanf(fcontrol, "%u", &entrybits) != 1) {
-               goto control_error;
-       }
-       if (fgetc(fcontrol) != 0) {
-               goto control_error;
-       }
-
-       /* second line is log2 size of address hash */
-       if (fscanf(fcontrol, "%u", &addrbits) != 1) {
-               goto control_error;
-       }
-       if (fgetc(fcontrol) != 0) {
-               goto control_error;
-       }
-
        fclose(fcontrol);
 
-       state->entry_bits = entrybits;
-       state->ident_bits = addrbits;
-
        return NSERROR_OK;
 
 control_error: /* problem with the control file */
@@ -1515,22 +1448,10 @@ initialise(const struct llcache_store_parameters 
*parameters)
        newstate->limit = parameters->limit;
        newstate->hysteresis = parameters->hysteresis;
 
-       if (parameters->address_size == 0) {
-               newstate->ident_bits = DEFAULT_IDENT_SIZE;
-       } else {
-               newstate->ident_bits = parameters->address_size;
-       }
-
-       if (parameters->entry_size == 0) {
-               newstate->entry_bits = DEFAULT_ENTRY_SIZE;
-       } else {
-               newstate->entry_bits = parameters->entry_size;
-       }
-
        /* read store control and create new if required */
        ret = read_control(newstate);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "read control failed %s",
+               NSLOG(netsurf, ERROR, "read control failed %s",
                      messages_get_errorcode(ret));
                ret = write_control(newstate);
                if (ret == NSERROR_OK) {
@@ -1545,13 +1466,6 @@ initialise(const struct llcache_store_parameters 
*parameters)
                return ret;
        }
 
-       /* ensure the maximum number of entries can be represented in
-        * the type available to store it.
-        */
-       if (newstate->entry_bits > (8 * sizeof(entry_index_t))) {
-               newstate->entry_bits = (8 * sizeof(entry_index_t));
-       }
-
        /* read filesystem entries */
        ret = read_entries(newstate);
        if (ret != NSERROR_OK) {
@@ -1561,21 +1475,11 @@ initialise(const struct llcache_store_parameters 
*parameters)
                return ret;
        }
 
-       /* build entry hash map */
-       ret = build_entrymap(newstate);
-       if (ret != NSERROR_OK) {
-               /* that obviously went well */
-               free(newstate->entries);
-               free(newstate->path);
-               free(newstate);
-               return ret;
-       }
-
+       /* read blocks */
        ret = read_blocks(newstate);
        if (ret != NSERROR_OK) {
                /* oh dear */
-               free(newstate->addrmap);
-               free(newstate->entries);
+               hashmap_destroy(newstate->entries);
                free(newstate->path);
                free(newstate);
                return ret;
@@ -1586,12 +1490,10 @@ initialise(const struct llcache_store_parameters 
*parameters)
        NSLOG(netsurf, INFO, "FS backing store init successful");
 
        NSLOG(netsurf, INFO,
-             "path:%s limit:%"PRIsizet" hyst:%"PRIsizet" addr:%d entries:%d",
+             "path:%s limit:%"PRIsizet" hyst:%"PRIsizet,
              newstate->path,
              newstate->limit,
-             newstate->hysteresis,
-             newstate->ident_bits,
-             newstate->entry_bits);
+             newstate->hysteresis);
        NSLOG(netsurf, INFO, "Using %"PRIu64"/%"PRIsizet,
              newstate->total_alloc, newstate->limit);
 
@@ -1614,7 +1516,7 @@ finalise(void)
        unsigned int op_count;
 
        if (storestate != NULL) {
-               guit->misc->schedule(-1, control_maintinance, storestate);
+               guit->misc->schedule(-1, control_maintenance, storestate);
                write_entries(storestate);
                write_blocks(storestate);
 
@@ -1643,8 +1545,7 @@ finalise(void)
                              0);
                }
 
-               free(storestate->addrmap);
-               free(storestate->entries);
+               hashmap_destroy(storestate->entries);
                free(storestate->path);
                free(storestate);
                storestate = NULL;
@@ -1676,7 +1577,7 @@ static nserror store_write_block(struct store_state 
*state,
                state->blocks[elem_idx][bf].fd = store_open(state, bf,
                                elem_idx + ENTRY_ELEM_COUNT, O_CREAT | O_RDWR);
                if (state->blocks[elem_idx][bf].fd == -1) {
-                       NSLOG(netsurf, INFO, "Open failed errno %d", errno);
+                       NSLOG(netsurf, ERROR, "Open failed errno %d", errno);
                        return NSERROR_SAVE_FAILED;
                }
 
@@ -1691,7 +1592,7 @@ static nserror store_write_block(struct store_state 
*state,
                    bse->elem[elem_idx].size,
                    offst);
        if (wr != (ssize_t)bse->elem[elem_idx].size) {
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, ERROR,
                      "Write failed %"PRIssizet" of %d bytes from %p at 0x%jx 
block %d errno %d",
                      wr,
                      bse->elem[elem_idx].size,
@@ -1726,10 +1627,10 @@ static nserror store_write_file(struct store_state 
*state,
        int fd;
        int err;
 
-       fd = store_open(state, bse->ident, elem_idx, O_CREAT | O_WRONLY);
+       fd = store_open(state, nsurl_hash(bse->url), elem_idx, O_CREAT | 
O_WRONLY);
        if (fd < 0) {
                perror("");
-               NSLOG(netsurf, INFO, "Open failed %d errno %d", fd, errno);
+               NSLOG(netsurf, ERROR, "Open failed %d errno %d", fd, errno);
                return NSERROR_SAVE_FAILED;
        }
 
@@ -1738,7 +1639,7 @@ static nserror store_write_file(struct store_state *state,
 
        close(fd);
        if (wr != (ssize_t)bse->elem[elem_idx].size) {
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, ERROR,
                      "Write failed %"PRIssizet" of %d bytes from %p errno %d",
                      wr,
                      bse->elem[elem_idx].size,
@@ -1749,7 +1650,7 @@ static nserror store_write_file(struct store_state *state,
                return NSERROR_SAVE_FAILED;
        }
 
-       NSLOG(netsurf, INFO, "Wrote %"PRIssizet" bytes from %p", wr,
+       NSLOG(netsurf, VERBOSE, "Wrote %"PRIssizet" bytes from %p", wr,
              bse->elem[elem_idx].data);
 
        return NSERROR_OK;
@@ -1791,7 +1692,7 @@ store(nsurl *url,
        /* set the store entry up */
        ret = set_store_entry(storestate, url, elem_idx, data, datalen, &bse);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "store entry setting failed");
+               NSLOG(netsurf, ERROR, "store entry setting failed");
                return ret;
        }
 
@@ -1814,7 +1715,7 @@ static nserror entry_release_alloc(struct 
store_entry_element *elem)
        if ((elem->flags & ENTRY_ELEM_FLAG_HEAP) != 0) {
                elem->ref--;
                if (elem->ref == 0) {
-                       NSLOG(netsurf, INFO, "freeing %p", elem->data);
+                       NSLOG(netsurf, DEEPDEBUG, "freeing %p", elem->data);
                        free(elem->data);
                        elem->flags &= ~ENTRY_ELEM_FLAG_HEAP;
                }
@@ -1846,7 +1747,7 @@ static nserror store_read_block(struct store_state *state,
                state->blocks[elem_idx][bf].fd = store_open(state, bf,
                                elem_idx + ENTRY_ELEM_COUNT, O_CREAT | O_RDWR);
                if (state->blocks[elem_idx][bf].fd == -1) {
-                       NSLOG(netsurf, INFO, "Open failed errno %d", errno);
+                       NSLOG(netsurf, ERROR, "Open failed errno %d", errno);
                        return NSERROR_SAVE_FAILED;
                }
 
@@ -1861,7 +1762,7 @@ static nserror store_read_block(struct store_state *state,
                   bse->elem[elem_idx].size,
                   offst);
        if (rd != (ssize_t)bse->elem[elem_idx].size) {
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, ERROR,
                      "Failed reading %"PRIssizet" of %d bytes into %p from 
0x%jx block %d errno %d",
                      rd,
                      bse->elem[elem_idx].size,
@@ -1872,7 +1773,7 @@ static nserror store_read_block(struct store_state *state,
                return NSERROR_SAVE_FAILED;
        }
 
-       NSLOG(netsurf, INFO,
+       NSLOG(netsurf, DEEPDEBUG,
              "Read %"PRIssizet" bytes into %p from 0x%jx block %d", rd,
              bse->elem[elem_idx].data, (uintmax_t)offst,
              bse->elem[elem_idx].block);
@@ -1898,9 +1799,9 @@ static nserror store_read_file(struct store_state *state,
        size_t tot = 0; /* total size */
 
        /* separate file in backing store */
-       fd = store_open(storestate, bse->ident, elem_idx, O_RDONLY);
+       fd = store_open(storestate, nsurl_hash(bse->url), elem_idx, O_RDONLY);
        if (fd < 0) {
-               NSLOG(netsurf, INFO, "Open failed %d errno %d", fd, errno);
+               NSLOG(netsurf, ERROR, "Open failed %d errno %d", fd, errno);
                /** @todo should this invalidate the entry? */
                return NSERROR_NOT_FOUND;
        }
@@ -1910,7 +1811,7 @@ static nserror store_read_file(struct store_state *state,
                          bse->elem[elem_idx].data + tot,
                          bse->elem[elem_idx].size - tot);
                if (rd <= 0) {
-                       NSLOG(netsurf, INFO,
+                       NSLOG(netsurf, ERROR,
                              "read error returned %"PRIssizet" errno %d",
                              rd,
                              errno);
@@ -1922,7 +1823,7 @@ static nserror store_read_file(struct store_state *state,
 
        close(fd);
 
-       NSLOG(netsurf, INFO, "Read %"PRIsizet" bytes into %p", tot,
+       NSLOG(netsurf, DEEPDEBUG, "Read %"PRIsizet" bytes into %p", tot,
              bse->elem[elem_idx].data);
 
        return ret;
@@ -1956,13 +1857,13 @@ fetch(nsurl *url,
        /* fetch store entry */
        ret = get_store_entry(storestate, url, &bse);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "entry not found");
+               NSLOG(netsurf, DEBUG, "Entry for %s not found", 
nsurl_access(url));
                storestate->miss_count++;
                return ret;
        }
        storestate->hit_count++;
 
-       NSLOG(netsurf, INFO, "retrieving cache data for url:%s",
+       NSLOG(netsurf, DEBUG, "retrieving cache data for url:%s",
              nsurl_access(url));
 
        /* calculate the entry element index */
@@ -1978,7 +1879,7 @@ fetch(nsurl *url,
                /* use the existing allocation and bump the ref count. */
                elem->ref++;
 
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, DEEPDEBUG,
                      "Using existing entry (%p) allocation %p refs:%d", bse,
                      elem->data, elem->ref);
 
@@ -1986,11 +1887,11 @@ fetch(nsurl *url,
                /* allocate from the heap */
                elem->data = malloc(elem->size);
                if (elem->data == NULL) {
-                       NSLOG(netsurf, INFO,
+                       NSLOG(netsurf, ERROR,
                              "Failed to create new heap allocation");
                        return NSERROR_NOMEM;
                }
-               NSLOG(netsurf, INFO, "Created new heap allocation %p",
+               NSLOG(netsurf, DEEPDEBUG, "Created new heap allocation %p",
                      elem->data);
 
                /* mark the entry as having a valid heap allocation */
@@ -2040,7 +1941,7 @@ static nserror release(nsurl *url, enum 
backing_store_flags bsflags)
 
        ret = get_store_entry(storestate, url, &bse);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "entry not found");
+               NSLOG(netsurf, WARNING, "entry not found");
                return ret;
        }
 
diff --git a/content/llcache.h b/content/llcache.h
index 514272f..f9a3016 100644
--- a/content/llcache.h
+++ b/content/llcache.h
@@ -121,43 +121,6 @@ struct llcache_store_parameters {
 
        size_t limit; /**< The backing store upper bound target size */
        size_t hysteresis; /**< The hysteresis around the target size */
-
-       /** log2 of the default maximum number of entries the cache
-        * can track.
-        *
-        * If unset this defaults to 16 (65536 entries) The cache
-        * control file takes precedence so cache data remains
-        * portable between builds with differing defaults.
-        */
-       unsigned int entry_size;
-
-       /** log2 of the default number of entries in the mapping between
-        * the url and cache entries.
-        *
-        * @note This is exposing an internal implementation detail of
-        * the filesystem based default backing store implementation.
-        * However it is likely any backing store implementation will
-        * need some way to map url to cache entries so it is a
-        * generally useful configuration value.
-        *
-        * Too small a value will cause unecessary collisions and
-        * cache misses and larger values cause proportionaly larger
-        * amounts of memory to be used.
-        *
-        * The "birthday paradox" means that the hash will experience
-        * a collision in every 2^(address_size/2) urls the cache
-        * stores.
-        *
-        * A value of 20 means one object stored in every 1024 will
-        * cause a collion and a cache miss while using two megabytes
-        * of storage.
-        *
-        * If unset this defaults to 20 (1048576 entries using two
-        * megabytes) The cache control file takes precedence so cache
-        * data remains portable between builds with differing
-        * defaults.
-        */
-       unsigned int address_size;
 };
 
 /**


commitdiff 
http://git.netsurf-browser.org/netsurf.git/commit/?id=ac75a9161e23b7073edcf0ec07d584b87d2e0e08
commit ac75a9161e23b7073edcf0ec07d584b87d2e0e08
Author: Daniel Silverstone <dsilv...@digital-scurf.org>
Commit: Daniel Silverstone <dsilv...@digital-scurf.org>

    llcache: Persist anything available during llcache_finalise
    
    Signed-off-by: Daniel Silverstone <dsilv...@digital-scurf.org>

diff --git a/content/llcache.c b/content/llcache.c
index 3a75bf9..9c74fbd 100644
--- a/content/llcache.c
+++ b/content/llcache.c
@@ -3769,6 +3769,11 @@ void llcache_finalise(void)
        llcache_object *object, *next;
        uint64_t total_bandwidth = 0; /* total bandwidth */
 
+       /* Attempt to persist anything we have left lying around */
+       llcache_persist(NULL);
+       /* Now clear the persistence callback */
+       guit->misc->schedule(-1, llcache_persist, NULL);
+
        /* Clean uncached objects */
        for (object = llcache->uncached_objects; object != NULL; object = next) 
{
                llcache_object_user *user, *next_user;


commitdiff 
http://git.netsurf-browser.org/netsurf.git/commit/?id=088917641f0865e11be5e81bf90de3dbc8cba19e
commit 088917641f0865e11be5e81bf90de3dbc8cba19e
Author: Daniel Silverstone <dsilv...@digital-scurf.org>
Commit: Daniel Silverstone <dsilv...@digital-scurf.org>

    utils: Add hashmap_count()
    
    Signed-off-by: Daniel Silverstone <dsilv...@digital-scurf.org>

diff --git a/test/hashmap.c b/test/hashmap.c
index 4bda493..ed951e9 100644
--- a/test/hashmap.c
+++ b/test/hashmap.c
@@ -197,7 +197,7 @@ basic_fixture_teardown(void)
 
 START_TEST(empty_hashmap_create_destroy)
 {
-       /* Do nothing in here, all the checks are in the fixture */
+       ck_assert_int_eq(hashmap_count(test_hashmap), 0);
 }
 END_TEST
 
@@ -213,6 +213,7 @@ START_TEST(insert_works)
         hashmap_test_value_t *value = hashmap_insert(test_hashmap, 
corestring_nsurl_about_blank);
        ck_assert(value != NULL);
        ck_assert(value->key == corestring_nsurl_about_blank);
+       ck_assert_int_eq(hashmap_count(test_hashmap), 1);
 }
 END_TEST
 
@@ -229,9 +230,11 @@ START_TEST(insert_then_remove)
        ck_assert(value->key == corestring_nsurl_about_blank);
        ck_assert_int_eq(keys, 1);
        ck_assert_int_eq(values, 1);
+       ck_assert_int_eq(hashmap_count(test_hashmap), 1);
        ck_assert(hashmap_remove(test_hashmap, corestring_nsurl_about_blank) == 
true);
        ck_assert_int_eq(keys, 0);
        ck_assert_int_eq(values, 0);
+       ck_assert_int_eq(hashmap_count(test_hashmap), 0);
 }
 END_TEST
 
@@ -450,6 +453,7 @@ START_TEST(chain_add_all_twice_remove_all_iterate)
        iteration_stop = 0;
        ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
        ck_assert_int_eq(iteration_counter, chain_count);
+       ck_assert_int_eq(hashmap_count(test_hashmap), chain_count);
        
        iteration_counter = 0;
        iteration_stop = chain_count;
@@ -469,6 +473,7 @@ START_TEST(chain_add_all_twice_remove_all_iterate)
        
        ck_assert_int_eq(keys, 0);
        ck_assert_int_eq(values, 0);
+       ck_assert_int_eq(hashmap_count(test_hashmap), 0);
 }
 END_TEST
 
diff --git a/utils/hashmap.c b/utils/hashmap.c
index b7870a3..814dc55 100644
--- a/utils/hashmap.c
+++ b/utils/hashmap.c
@@ -55,6 +55,11 @@ struct hashmap_s {
         * The number of buckets in this map
         */
        uint32_t bucket_count;
+       
+       /**
+        * The number of entries in this map
+        */
+       size_t entry_count;
 };
 
 /* Exported function, documented in hashmap.h */
@@ -65,14 +70,16 @@ hashmap_create(hashmap_parameters_t *params)
 
        ret->params = params;
        ret->bucket_count = DEFAULT_HASHMAP_BUCKETS;
+       ret->entry_count = 0;
        ret->buckets = malloc(ret->bucket_count * sizeof(hashmap_entry_t *));
-       memset(ret->buckets, 0, ret->bucket_count * sizeof(hashmap_entry_t *));
 
        if (ret->buckets == NULL) {
                free(ret);
                return NULL;
        }
-       
+
+       memset(ret->buckets, 0, ret->bucket_count * sizeof(hashmap_entry_t *));
+
        return ret;
 }
 
@@ -176,7 +183,9 @@ hashmap_insert(hashmap_t *hashmap, void *key)
        }
 
        hashmap->buckets[bucket] = entry;
-       
+
+       hashmap->entry_count++;
+
        return entry->value;
 
 err:
@@ -207,6 +216,7 @@ hashmap_remove(hashmap_t *hashmap, void *key)
                                }
                                *entry->prevptr = entry->next;
                                free(entry);
+                               hashmap->entry_count--;
                                return true;
                        }
                }
@@ -233,3 +243,10 @@ hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t 
cb, void *ctx)
 
        return false;
 }
+
+/* Exported function, documented in hashmap.h */
+size_t
+hashmap_count(hashmap_t *hashmap)
+{
+       return hashmap->entry_count;
+}
diff --git a/utils/hashmap.h b/utils/hashmap.h
index cb8fd50..3968fd3 100644
--- a/utils/hashmap.h
+++ b/utils/hashmap.h
@@ -186,4 +186,12 @@ bool hashmap_remove(hashmap_t *hashmap, void *key);
  */
 bool hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t cb, void *ctx);
 
+/**
+ * Get the number of entries in this map
+ *
+ * \param hashmap The hashmap to retrieve the entry count from
+ * \return The number of entries in the hashmap
+ */
+size_t hashmap_count(hashmap_t *hashmap);
+
 #endif


commitdiff 
http://git.netsurf-browser.org/netsurf.git/commit/?id=3e02961ec8f21fd656c8b306c5075c0c799df97f
commit 3e02961ec8f21fd656c8b306c5075c0c799df97f
Author: Daniel Silverstone <dsilv...@digital-scurf.org>
Commit: Daniel Silverstone <dsilv...@digital-scurf.org>

    utils: Fix destroy of non-empty hashmap
    
    Signed-off-by: Daniel Silverstone <dsilv...@digital-scurf.org>

diff --git a/utils/hashmap.c b/utils/hashmap.c
index bfbf6ce..b7870a3 100644
--- a/utils/hashmap.c
+++ b/utils/hashmap.c
@@ -85,11 +85,12 @@ hashmap_destroy(hashmap_t *hashmap)
 
        for (bucket = 0; bucket < hashmap->bucket_count; bucket++) {
                for (entry = hashmap->buckets[bucket];
-                    entry != NULL;
-                    entry = entry->next) {
+                    entry != NULL;) {
+                       hashmap_entry_t *next = entry->next;
                        hashmap->params->value_destroy(entry->value);
                        hashmap->params->key_destroy(entry->key);
                        free(entry);
+                       entry = next;
                }
        }
 


commitdiff 
http://git.netsurf-browser.org/netsurf.git/commit/?id=54b1960d18042cf6dfd86cfe01d58455357586d2
commit 54b1960d18042cf6dfd86cfe01d58455357586d2
Author: Daniel Silverstone <dsilv...@digital-scurf.org>
Commit: Daniel Silverstone <dsilv...@digital-scurf.org>

    utils: Add iteration API to hashmap
    
    Signed-off-by: Daniel Silverstone <dsilv...@digital-scurf.org>

diff --git a/test/hashmap.c b/test/hashmap.c
index 87db6c1..4bda493 100644
--- a/test/hashmap.c
+++ b/test/hashmap.c
@@ -151,6 +151,20 @@ static hashmap_parameters_t test_params = {
        .value_destroy = value_destroy,
 };
 
+/* Iteration helpers */
+
+static size_t iteration_counter = 0;
+static size_t iteration_stop = 0;
+static char iteration_ctx = 0;
+
+static bool
+hashmap_test_iterator_cb(void *key, void *value, void *ctx)
+{
+       ck_assert(ctx == &iteration_ctx);
+       iteration_counter++;
+       return iteration_counter == iteration_stop;
+}
+
 /* Fixtures for basic tests */
 
 static hashmap_t *test_hashmap = NULL;
@@ -230,6 +244,35 @@ START_TEST(insert_then_lookup)
 }
 END_TEST
 
+START_TEST(iterate_empty)
+{
+       iteration_stop = iteration_counter = 0;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, 0);
+}
+END_TEST
+
+START_TEST(iterate_one)
+{
+       iteration_stop = iteration_counter = 0;
+        hashmap_test_value_t *value = hashmap_insert(test_hashmap, 
corestring_nsurl_about_blank);
+       ck_assert(value != NULL);
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, 1);
+}
+END_TEST
+
+START_TEST(iterate_one_and_stop)
+{
+       iteration_stop = 1;
+       iteration_counter = 0;
+        hashmap_test_value_t *value = hashmap_insert(test_hashmap, 
corestring_nsurl_about_blank);
+       ck_assert(value != NULL);
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == true);
+       ck_assert_int_eq(iteration_counter, 1);
+}
+END_TEST
+
 static TCase *basic_api_case_create(void)
 {
        TCase *tc;
@@ -245,7 +288,11 @@ static TCase *basic_api_case_create(void)
        tcase_add_test(tc, remove_not_present);
        tcase_add_test(tc, insert_then_remove);
        tcase_add_test(tc, insert_then_lookup);
-
+       
+       tcase_add_test(tc, iterate_empty);
+       tcase_add_test(tc, iterate_one);
+       tcase_add_test(tc, iterate_one_and_stop);
+       
        return tc;
 }
 
@@ -374,6 +421,57 @@ START_TEST(chain_add_all_twice_remove_all)
 }
 END_TEST
 
+START_TEST(chain_add_all_twice_remove_all_iterate)
+{
+       case_pair *chain_case;
+       size_t chain_count = 0;
+       
+       for (chain_case = chain_pairs;
+            chain_case->url != NULL;
+            chain_case++) {
+               ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == 
NULL);
+               ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != 
NULL);
+               chain_count++;
+       }
+       
+       iteration_counter = 0;
+       iteration_stop = 0;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, chain_count);
+       
+       for (chain_case = chain_pairs;
+            chain_case->url != NULL;
+            chain_case++) {
+               ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) != 
NULL);
+               ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != 
NULL);
+       }
+
+       iteration_counter = 0;
+       iteration_stop = 0;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, chain_count);
+       
+       iteration_counter = 0;
+       iteration_stop = chain_count;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == true);
+       ck_assert_int_eq(iteration_counter, chain_count);
+       
+       for (chain_case = chain_pairs;
+            chain_case->url != NULL;
+            chain_case++) {
+               ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == 
true);
+       }
+
+       iteration_counter = 0;
+       iteration_stop = chain_count;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, 0);
+       
+       ck_assert_int_eq(keys, 0);
+       ck_assert_int_eq(values, 0);
+}
+END_TEST
+
 #define CHAIN_TEST_MALLOC_COUNT_MAX 60
 
 START_TEST(chain_add_all_remove_all_alloc)
@@ -431,6 +529,7 @@ static TCase *chain_case_create(void)
        tcase_add_test(tc, chain_add_remove_all);
        tcase_add_test(tc, chain_add_all_remove_all);
        tcase_add_test(tc, chain_add_all_twice_remove_all);
+       tcase_add_test(tc, chain_add_all_twice_remove_all_iterate);
 
        tcase_add_loop_test(tc, chain_add_all_remove_all_alloc, 0, 
CHAIN_TEST_MALLOC_COUNT_MAX + 1);
        
diff --git a/utils/hashmap.c b/utils/hashmap.c
index 7ed1994..bfbf6ce 100644
--- a/utils/hashmap.c
+++ b/utils/hashmap.c
@@ -213,3 +213,22 @@ hashmap_remove(hashmap_t *hashmap, void *key)
 
        return false;
 }
+
+/* Exported function, documented in hashmap.h */
+bool
+hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t cb, void *ctx)
+{
+       for (uint32_t bucket = 0;
+            bucket < hashmap->bucket_count;
+            bucket++) {
+               for (hashmap_entry_t *entry = hashmap->buckets[bucket];
+                    entry != NULL;
+                    entry = entry->next) {
+                       /* If the callback returns true, we early-exit */
+                       if (cb(entry->key, entry->value, ctx))
+                               return true;
+               }
+       }
+
+       return false;
+}
diff --git a/utils/hashmap.h b/utils/hashmap.h
index 462b51e..cb8fd50 100644
--- a/utils/hashmap.h
+++ b/utils/hashmap.h
@@ -62,6 +62,16 @@ typedef void* (*hashmap_value_alloc_t)(void *);
 typedef void (*hashmap_value_destroy_t)(void *);
 
 /**
+ * Hashmap iteration callback function type.
+ *
+ * First parameter is the key, second is the value.
+ * The final parameter is the context pointer for the iteration.
+ *
+ * Return true to stop iterating early
+ */
+typedef bool (*hashmap_iteration_cb_t)(void *, void *, void *);
+
+/**
  * Parameters for hashmaps
  */
 typedef struct {
@@ -163,5 +173,17 @@ void *hashmap_insert(hashmap_t *hashmap, void *key);
  */
 bool hashmap_remove(hashmap_t *hashmap, void *key);
 
+/**
+ * Iterate the hashmap
+ *
+ * For each key/value pair in the hashmap, call the callback passing in
+ * the key and value.  During iteration you MUST NOT mutate the hashmap.
+ *
+ * \param hashmap The hashmap to iterate
+ * \param cb The callback for each key,value pair
+ * \param ctx The callback context
+ * \return Whether or not we stopped iteration early
+ */
+bool hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t cb, void *ctx);
 
 #endif


commitdiff 
http://git.netsurf-browser.org/netsurf.git/commit/?id=fd80341513813684ba3155b87e4e6cc8c87631f1
commit fd80341513813684ba3155b87e4e6cc8c87631f1
Author: Daniel Silverstone <dsilv...@digital-scurf.org>
Commit: Daniel Silverstone <dsilv...@digital-scurf.org>

    utils: Add hashmap to sources
    
    Signed-off-by: Daniel Silverstone <dsilv...@digital-scurf.org>

diff --git a/utils/Makefile b/utils/Makefile
index e0fbd8e..fa5f58d 100644
--- a/utils/Makefile
+++ b/utils/Makefile
@@ -6,6 +6,7 @@ S_UTILS := \
        file.c \
        filename.c \
        filepath.c \
+       hashmap.c \
        hashtable.c \
        idna.c \
        libdom.c \


commitdiff 
http://git.netsurf-browser.org/netsurf.git/commit/?id=61187d31ab7ba292510e1e56886325a1c6a1c822
commit 61187d31ab7ba292510e1e56886325a1c6a1c822
Author: Daniel Silverstone <dsilv...@digital-scurf.org>
Commit: Daniel Silverstone <dsilv...@digital-scurf.org>

    utils: Add hashmap parameter function types
    
    Signed-off-by: Daniel Silverstone <dsilv...@digital-scurf.org>

diff --git a/utils/hashmap.h b/utils/hashmap.h
index 4e1237a..462b51e 100644
--- a/utils/hashmap.h
+++ b/utils/hashmap.h
@@ -32,6 +32,36 @@
 typedef struct hashmap_s hashmap_t;
 
 /**
+ * Key cloning function type
+ */
+typedef void* (*hashmap_key_clone_t)(void *);
+
+/**
+ * Key destructor function type
+ */
+typedef void (*hashmap_key_destroy_t)(void *);
+
+/**
+ * Key hashing function type
+ */
+typedef uint32_t (*hashmap_key_hash_t)(void *);
+
+/**
+ * Key comparison function type
+ */
+typedef bool (*hashmap_key_eq_t)(void *, void*);
+
+/**
+ * Value allocation function type
+ */
+typedef void* (*hashmap_value_alloc_t)(void *);
+
+/**
+ * Value destructor function type
+ */
+typedef void (*hashmap_value_destroy_t)(void *);
+
+/**
  * Parameters for hashmaps
  */
 typedef struct {
@@ -39,12 +69,12 @@ typedef struct {
         * A function which when called will clone a key and give
         * ownership of the returned object to the hashmap
         */
-       void * (*key_clone)(void *key);
+       hashmap_key_clone_t key_clone;
 
        /**
         * A function which when given a key will return its hash.
         */
-       uint32_t (*key_hash)(void *key);
+       hashmap_key_hash_t key_hash;
        
        /**
         * A function to compare two keys and return if they are equal.
@@ -52,22 +82,22 @@ typedef struct {
         * as the function is a full equality model.
         * (i.e. key1 == key2 => key2 == key1)
         */
-       bool (*key_eq)(void *key1, void *key2);
+       hashmap_key_eq_t key_eq;
         
        /**
         * A function which when called will destroy a key object
         */
-       void (*key_destroy)(void *key);
+       hashmap_key_destroy_t key_destroy;
 
        /**
         * A function which when called will allocate a value object
         */
-       void * (*value_alloc)(void *key);
+       hashmap_value_alloc_t value_alloc;
 
        /**
         * A function which when called will destroy a value object
         */
-       void (*value_destroy)(void *value);
+       hashmap_value_destroy_t value_destroy;
 } hashmap_parameters_t;
 
 


-----------------------------------------------------------------------

Summary of changes:
 content/fs_backing_store.c |  597 ++++++++++++++++++--------------------------
 content/llcache.c          |    5 +
 content/llcache.h          |   37 ---
 test/hashmap.c             |  108 +++++++-
 utils/Makefile             |    1 +
 utils/hashmap.c            |   47 +++-
 utils/hashmap.h            |   72 +++++-
 7 files changed, 469 insertions(+), 398 deletions(-)

diff --git a/content/fs_backing_store.c b/content/fs_backing_store.c
index 19eb1ca..71d1c83 100644
--- a/content/fs_backing_store.c
+++ b/content/fs_backing_store.c
@@ -49,6 +49,7 @@
 #include "utils/nsurl.h"
 #include "utils/log.h"
 #include "utils/messages.h"
+#include "utils/hashmap.h"
 #include "desktop/gui_internal.h"
 #include "netsurf/misc.h"
 
@@ -61,20 +62,11 @@
 #define DEFAULT_ENTRY_SIZE 16
 
 /** Backing store file format version */
-#define CONTROL_VERSION 130
+#define CONTROL_VERSION 200
 
 /** Number of milliseconds after a update before control data maintenance is 
performed  */
 #define CONTROL_MAINT_TIME 10000
 
-/** Get address from ident */
-#define BS_ADDRESS(ident, state) ((ident) & ((1 << state->ident_bits) - 1))
-
-/** Lookup store entry index from ident */
-#define BS_ENTRY_INDEX(ident, state) state->addrmap[(ident) & ((1 << 
state->ident_bits) - 1)]
-
-/** Get store entry from ident. */
-#define BS_ENTRY(ident, state) state->entries[state->addrmap[(ident) & ((1 << 
state->ident_bits) - 1)]]
-
 /** Filename of serialised entries */
 #define ENTRIES_FNAME "entries"
 
@@ -184,8 +176,8 @@ struct store_entry_element {
  * @note Order is important to avoid excessive structure packing overhead.
  */
 struct store_entry {
+       nsurl *url; /**< The URL for this entry */
        int64_t last_used; /**< UNIX time the entry was last used */
-       entry_ident_t ident; /**< entry identifier */
        uint16_t use_count; /**< number of times this entry has been accessed */
        uint8_t flags; /**< entry flags */
        /** Entry element (data or meta) specific information */
@@ -219,29 +211,16 @@ struct store_state {
        size_t limit; /**< The backing store upper bound target size */
        size_t hysteresis; /**< The hysteresis around the target size */
 
-       unsigned int ident_bits; /**< log2 number of bits to use for address. */
-
-
-       /* cache entry management */
-       struct store_entry *entries; /**< store entries. */
-       unsigned int entry_bits; /**< log2 number of bits in entry index. */
-       unsigned int last_entry; /**< index of last usable entry. */
+       /**
+        * The cache object hash
+        */
+       hashmap_t *entries;
 
        /** flag indicating if the entries have been made persistent
         * since they were last changed.
         */
        bool entries_dirty;
 
-       /**
-        * URL identifier to entry index mapping.
-        *
-        * This is an open coded index on the entries URL field and
-        * provides a computationally inexpensive way to go from the
-        * URL to an entry.
-        */
-       entry_index_t *addrmap;
-
-
        /** small block indexes */
        struct block_file blocks[ENTRY_ELEM_COUNT][BLOCK_FILE_COUNT];
 
@@ -273,60 +252,44 @@ struct store_state {
  */
 struct store_state *storestate;
 
-
-/**
- * Remove a backing store entry from the entry table.
- *
- * This finds the store entry associated with the given key and
- * removes it from the table. The removed entry is returned but is
- * only valid until the next set_store_entry call.
+/* Entries hashmap parameters
  *
- * @param[in] state The store state to use.
- * @param[in, out] bse Pointer to the entry to be removed.
- * @return NSERROR_OK and \a bse updated on success or NSERROR_NOT_FOUND
- *         if no entry corresponds to the URL.
+ * Our hashmap has nsurl keys and store_entry values
  */
-static nserror
-remove_store_entry(struct store_state *state, struct store_entry **bse)
-{
-       entry_index_t sei; /* store entry index */
-
-       /* sei is index to entry to be removed, we swap it to the end
-        * of the table so there are no gaps and the returned entry is
-        * held in storage with reasonable lifetime.
-        */
-
-       sei = BS_ENTRY_INDEX((*bse)->ident, state);
-
-       /* remove entry from map */
-       BS_ENTRY_INDEX((*bse)->ident, state) = 0;
 
-       /* global allocation accounting  */
-       state->total_alloc -= state->entries[sei].elem[ENTRY_ELEM_DATA].size;
-       state->total_alloc -= state->entries[sei].elem[ENTRY_ELEM_META].size;
-
-       state->last_entry--;
-
-       if (sei == state->last_entry) {
-               /* the removed entry was the last one, how convenient */
-               *bse = &state->entries[sei];
-       } else {
-               /* need to swap entries */
-               struct store_entry tent;
-
-               tent = state->entries[sei];
-               state->entries[sei] = state->entries[state->last_entry];
-               state->entries[state->last_entry] = tent;
-
-               /* update map for moved entry */
-               BS_ENTRY_INDEX(state->entries[sei].ident, state) = sei;
+static bool
+entries_hashmap_key_eq(void *key1, void *key2)
+{
+       return nsurl_compare((nsurl *)key1, (nsurl *)key2, NSURL_COMPLETE);
+}
 
-               *bse = &state->entries[state->last_entry];
+static void *
+entries_hashmap_value_alloc(void *key)
+{
+       struct store_entry *ent = calloc(1, sizeof(struct store_entry));
+       if (ent != NULL) {
+               ent->url = nsurl_ref(key);
        }
+       return ent;
+}
 
-       return NSERROR_OK;
+static void
+entries_hashmap_value_destroy(void *value)
+{
+       struct store_entry *ent = value;
+       /** \todo Do we need to do any disk cleanup here?  if so, meep! */
+       nsurl_unref(ent->url);
+       free(ent);
 }
 
+static hashmap_parameters_t entries_hashmap_parameters = {
+       .key_clone = (hashmap_key_clone_t)nsurl_ref,
+       .key_destroy = (hashmap_key_destroy_t)nsurl_unref,
+       .key_hash = (hashmap_key_hash_t)nsurl_hash,
+       .key_eq = entries_hashmap_key_eq,
+       .value_alloc = entries_hashmap_value_alloc,
+       .value_destroy = entries_hashmap_value_destroy,
+};
 
 /**
  * Generate a filename for an object.
@@ -484,7 +447,7 @@ invalidate_element(struct store_state *state,
                char *fname;
 
                /* unlink the file from disc */
-               fname = store_fname(state, bse->ident, elem_idx);
+               fname = store_fname(state, nsurl_hash(bse->url), elem_idx);
                if (fname == NULL) {
                        return NSERROR_NOMEM;
                }
@@ -492,6 +455,8 @@ invalidate_element(struct store_state *state,
                free(fname);
        }
 
+       state->total_alloc -= bse->elem[elem_idx].size;
+
        return NSERROR_OK;
 }
 
@@ -519,29 +484,27 @@ invalidate_entry(struct store_state *state, struct 
store_entry *bse)
                 * This entry cannot be immediately removed as it has
                 * associated allocation so wait for allocation release.
                 */
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, DEBUG,
                      "invalidating entry with referenced allocation");
                return NSERROR_OK;
        }
 
-       NSLOG(netsurf, INFO, "Removing entry for %p", bse);
-
-       /* remove the entry from the index */
-       ret = remove_store_entry(state, &bse);
-       if (ret != NSERROR_OK) {
-               return ret;
-       }
+       NSLOG(netsurf, VERBOSE, "Removing entry for %s", 
nsurl_access(bse->url));
 
        ret = invalidate_element(state, bse, ENTRY_ELEM_META);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "Error invalidating metadata element");
+               NSLOG(netsurf, ERROR, "Error invalidating metadata element");
        }
 
        ret = invalidate_element(state, bse, ENTRY_ELEM_DATA);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "Error invalidating data element");
+               NSLOG(netsurf, ERROR, "Error invalidating data element");
        }
 
+       /* As our final act we remove bse from the cache */
+       hashmap_remove(state->entries, bse->url);
+       /* From now, bse is invalid memory */
+
        return NSERROR_OK;
 }
 
@@ -551,8 +514,8 @@ invalidate_entry(struct store_state *state, struct 
store_entry *bse)
  */
 static int compar(const void *va, const void *vb)
 {
-       const struct store_entry *a = &BS_ENTRY(*(entry_ident_t *)va, 
storestate);
-       const struct store_entry *b = &BS_ENTRY(*(entry_ident_t *)vb, 
storestate);
+       const struct store_entry *a = *(const struct store_entry **)va;
+       const struct store_entry *b = *(const struct store_entry **)vb;
 
        /* consider the allocation flags - if an entry has an
         * allocation it is considered more valuable as it cannot be
@@ -591,6 +554,22 @@ static int compar(const void *va, const void *vb)
        return 0;
 }
 
+typedef struct {
+       struct store_entry **elist;
+       size_t ent_count;
+} eviction_state_t;
+
+/**
+ * Iterator for gathering entries to compute eviction order
+ */
+static bool
+entry_eviction_iterator_cb(void *key, void *value, void *ctx)
+{
+       eviction_state_t *estate = ctx;
+       struct store_entry *ent = value;
+       estate->elist[estate->ent_count++] = ent;
+       return false;
+}
 
 /**
  * Evict entries from backing store as per configuration.
@@ -608,15 +587,14 @@ static int compar(const void *va, const void *vb)
  */
 static nserror store_evict(struct store_state *state)
 {
-       entry_ident_t *elist; /* sorted list of entry identifiers */
-       unsigned int ent;
-       unsigned int ent_count;
-       size_t removed; /* size of removed entries */
+       size_t ent = 0;
+       size_t removed = 0; /* size of removed entries */
        nserror ret = NSERROR_OK;
+       size_t old_count;
+       eviction_state_t estate;
 
        /* check if the cache has exceeded configured limit */
-       if ((state->total_alloc < state->limit) &&
-           (state->last_entry < (1U << state->entry_bits))) {
+       if (state->total_alloc < state->limit) {
                /* cache within limits */
                return NSERROR_OK;
        }
@@ -627,24 +605,31 @@ static nserror store_evict(struct store_state *state)
              state->hysteresis);
 
        /* allocate storage for the list */
-       elist = malloc(sizeof(entry_ident_t) * state->last_entry);
-       if (elist == NULL) {
+       old_count = hashmap_count(state->entries);
+       estate.ent_count = 0;
+       estate.elist = malloc(sizeof(struct state_entry*) * old_count);
+       if (estate.elist == NULL) {
                return NSERROR_NOMEM;
        }
 
-       /* sort the list avoiding entry 0 which is the empty sentinel */
-       for (ent = 1; ent < state->last_entry; ent++) {
-               elist[ent - 1] = state->entries[ent].ident;
+       if (hashmap_iterate(state->entries, entry_eviction_iterator_cb, 
&estate)) {
+               NSLOG(netsurf, WARNING, "Unexpected termination of eviction 
iterator");
+               free(estate.elist);
+               return NSERROR_UNKNOWN;
        }
-       ent_count = ent - 1; /* important to keep this as the entry count will 
change when entries are removed */
-       qsort(elist, ent_count, sizeof(entry_ident_t), compar);
+
+       if (old_count != estate.ent_count) {
+               NSLOG(netsurf, WARNING, "Incorrect entry count after eviction 
iterator");
+               free(estate.elist);
+               return NSERROR_UNKNOWN;
+       }
+
+       qsort(estate.elist, estate.ent_count, sizeof(struct state_entry*), 
compar);
 
        /* evict entries in listed order */
        removed = 0;
-       for (ent = 0; ent < ent_count; ent++) {
-               struct store_entry *bse;
-
-               bse = &BS_ENTRY(elist[ent], state);
+       for (ent = 0; ent < estate.ent_count; ent++) {
+               struct store_entry *bse = estate.elist[ent];
 
                removed += bse->elem[ENTRY_ELEM_DATA].size;
                removed += bse->elem[ENTRY_ELEM_META].size;
@@ -659,14 +644,55 @@ static nserror store_evict(struct store_state *state)
                }
        }
 
-       free(elist);
+       free(estate.elist);
 
-       NSLOG(netsurf, INFO, "removed %"PRIsizet" in %d entries", removed,
-             ent);
+       NSLOG(netsurf, INFO,
+             "removed %"PRIsizet" in %"PRIsizet" entries, %"PRIsizet" 
remaining in %"PRIsizet" entries",
+             removed, ent, state->total_alloc, old_count - ent);
 
        return ret;
 }
 
+/**
+ * Write a single store entry to disk
+ *
+ * To serialise a single store entry for now we write out a 32bit int
+ * which is the length of the url, then that many bytes of the url.
+ * Then we write out the full store entry struct as-is, which includes
+ * a useless nsurl pointer.
+ */
+static nserror
+write_entry(struct store_entry *ent, int fd)
+{
+       uint32_t len = strlen(nsurl_access(ent->url));
+       if (write(fd, &len, sizeof(len)) != sizeof(len))
+               return NSERROR_SAVE_FAILED;
+       if (write(fd, nsurl_access(ent->url), len) != len)
+               return NSERROR_SAVE_FAILED;
+       if (write(fd, ent, sizeof(*ent)) != sizeof(*ent))
+               return NSERROR_SAVE_FAILED;
+
+       return NSERROR_OK;
+}
+
+typedef struct {
+       int fd;
+       size_t written;
+} write_entry_iteration_state;
+
+/**
+ * Callback for iterating the entries hashmap
+ */
+static bool
+write_entry_iterator(void *key, void *value, void *ctx)
+{
+       /* We ignore the key */
+       struct store_entry *ent = value;
+       write_entry_iteration_state *state = ctx;
+       state->written++;
+       /* We stop early if we fail to write this entry */
+       return write_entry(ent, state->fd) != NSERROR_OK;
+}
 
 /**
  * Write filesystem entries to file.
@@ -678,13 +704,13 @@ static nserror store_evict(struct store_state *state)
  */
 static nserror write_entries(struct store_state *state)
 {
-       int fd;
        char *tname = NULL; /* temporary file name for atomic replace */
        char *fname = NULL; /* target filename */
-       size_t entries_size;
-       size_t written;
+       write_entry_iteration_state weistate;
        nserror ret;
 
+       memset(&weistate, 0, sizeof(weistate));
+
        if (state->entries_dirty == false) {
                /* entries have not been updated since last write */
                return NSERROR_OK;
@@ -695,25 +721,22 @@ static nserror write_entries(struct store_state *state)
                return ret;
        }
 
-       fd = open(tname, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR);
-       if (fd == -1) {
+       weistate.fd = open(tname, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | 
S_IWUSR);
+       if (weistate.fd == -1) {
                free(tname);
                return NSERROR_SAVE_FAILED;
        }
 
-       entries_size = state->last_entry * sizeof(struct store_entry);
-
-       written = (size_t)write(fd, state->entries, entries_size);
-
-       close(fd);
-
-       /* check all data was written */
-       if (written != entries_size) {
+       if (hashmap_iterate(state->entries, write_entry_iterator, &weistate)) {
+               /* The iteration ended early, so we failed */
+               close(weistate.fd);
                unlink(tname);
                free(tname);
                return NSERROR_SAVE_FAILED;
        }
 
+       close(weistate.fd);
+
        ret = netsurf_mkpath(&fname, NULL, 2, state->path, ENTRIES_FNAME);
        if (ret != NSERROR_OK) {
                unlink(tname);
@@ -730,6 +753,8 @@ static nserror write_entries(struct store_state *state)
                return NSERROR_SAVE_FAILED;
        }
 
+       NSLOG(netsurf, INFO, "Wrote out %"PRIsizet" entries", weistate.written);
+
        return NSERROR_OK;
 }
 
@@ -777,7 +802,7 @@ static nserror write_blocks(struct store_state *state)
                                   &state->blocks[elem_idx][bfidx].use_map[0],
                                   BLOCK_USE_MAP_SIZE);
                        if (wr != BLOCK_USE_MAP_SIZE) {
-                               NSLOG(netsurf, INFO,
+                               NSLOG(netsurf, DEBUG,
                                      "writing block file %d use index on file 
number %d failed",
                                      elem_idx,
                                      bfidx);
@@ -836,21 +861,21 @@ static nserror set_block_extents(struct store_state 
*state)
                return NSERROR_OK;
        }
 
-       NSLOG(netsurf, INFO, "Starting");
+       NSLOG(netsurf, DEBUG, "Starting");
        for (elem_idx = 0; elem_idx < ENTRY_ELEM_COUNT; elem_idx++) {
                for (bfidx = 0; bfidx < BLOCK_FILE_COUNT; bfidx++) {
                        if (state->blocks[elem_idx][bfidx].fd != -1) {
                                /* ensure block file is correct extent */
                                ftr = 
ftruncate(state->blocks[elem_idx][bfidx].fd, 1U << (log2_block_size[elem_idx] + 
BLOCK_ENTRY_COUNT));
                                if (ftr == -1) {
-                                       NSLOG(netsurf, INFO,
+                                       NSLOG(netsurf, ERROR,
                                              "Truncate failed errno:%d",
                                              errno);
                                }
                        }
                }
        }
-       NSLOG(netsurf, INFO, "Complete");
+       NSLOG(netsurf, DEBUG, "Complete");
 
        state->blocks_opened = false;
 
@@ -866,7 +891,7 @@ static nserror set_block_extents(struct store_state *state)
  *
  * \param s store state to maintain.
  */
-static void control_maintinance(void *s)
+static void control_maintenance(void *s)
 {
        struct store_state *state = s;
 
@@ -892,36 +917,22 @@ static void control_maintinance(void *s)
 static nserror
 get_store_entry(struct store_state *state, nsurl *url, struct store_entry 
**bse)
 {
-       entry_ident_t ident;
-       unsigned int sei; /* store entry index */
-
-       NSLOG(netsurf, INFO, "url:%s", nsurl_access(url));
-
-       /* use the url hash as the entry identifier */
-       ident = nsurl_hash(url);
+       struct store_entry *ent;
 
-       sei = BS_ENTRY_INDEX(ident, state);
+       ent = hashmap_lookup(state->entries, url);
 
-       if (sei == 0) {
-               NSLOG(netsurf, INFO, "Failed to find ident 0x%x in index",
-                     ident);
+       if (ent == NULL) {
                return NSERROR_NOT_FOUND;
        }
 
-       if (state->entries[sei].ident != ident) {
-               /* entry ident did not match */
-               NSLOG(netsurf, INFO, "ident did not match entry");
-               return NSERROR_NOT_FOUND;
-       }
-
-       *bse = &state->entries[sei];
+       *bse = ent;
 
-       state->entries[sei].last_used = time(NULL);
-       state->entries[sei].use_count++;
+       ent->last_used = time(NULL);
+       ent->use_count++;
 
        state->entries_dirty = true;
 
-       guit->misc->schedule(CONTROL_MAINT_TIME, control_maintinance, state);
+       guit->misc->schedule(CONTROL_MAINT_TIME, control_maintenance, state);
 
        return NSERROR_OK;
 }
@@ -979,13 +990,11 @@ set_store_entry(struct store_state *state,
                const size_t datalen,
                struct store_entry **bse)
 {
-       entry_ident_t ident;
-       entry_index_t sei; /* store entry index */
        struct store_entry *se;
        nserror ret;
        struct store_entry_element *elem;
 
-       NSLOG(netsurf, INFO, "url:%s", nsurl_access(url));
+       NSLOG(netsurf, DEBUG, "url:%s", nsurl_access(url));
 
        /* evict entries as required and ensure there is at least one
         * new entry available.
@@ -995,40 +1004,12 @@ set_store_entry(struct store_state *state,
                return ret;
        }
 
-       /* use the url hash as the entry identifier */
-       ident = nsurl_hash(url);
-
-       /* get the entry index from the ident */
-       sei = BS_ENTRY_INDEX(ident, state);
-       if (sei == 0) {
-               /* allocating the next available entry */
-               sei = state->last_entry;
-               state->last_entry++;
-               BS_ENTRY_INDEX(ident, state) = sei;
-
-               /* the entry */
-               se = &state->entries[sei];
-
-               /* clear the new entry */
-               memset(se, 0, sizeof(struct store_entry));
-       } else {
-               /* index found existing entry */
-
-               /* the entry */
-               se = &state->entries[sei];
-
-               if (se->ident != ident) {
-                       /** @todo Is there a better heuristic than
-                        * first come, first served? Should we check
-                        * to see if the old entry is in use and if
-                        * not prefer the newly stored entry instead?
-                        */
-                       NSLOG(netsurf, INFO,
-                             "Entry index collision trying to replace %x with 
%x",
-                             se->ident,
-                             ident);
-                       return NSERROR_PERMISSION;
-               }
+       se = hashmap_lookup(state->entries, url);
+       if (se == NULL) {
+               se = hashmap_insert(state->entries, url);
+       }
+       if (se == NULL) {
+               return NSERROR_NOMEM;
        }
 
        /* the entry element */
@@ -1039,13 +1020,12 @@ set_store_entry(struct store_state *state,
                /* this entry cannot be removed as it has associated
                 * allocation.
                 */
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, ERROR,
                      "attempt to overwrite entry with in use data");
                return NSERROR_PERMISSION;
        }
 
        /* set the common entry data */
-       se->ident = ident;
        se->use_count = 1;
        se->last_used = time(NULL);
 
@@ -1066,7 +1046,7 @@ set_store_entry(struct store_state *state,
 
        /* ensure control maintenance scheduled. */
        state->entries_dirty = true;
-       guit->misc->schedule(CONTROL_MAINT_TIME, control_maintinance, state);
+       guit->misc->schedule(CONTROL_MAINT_TIME, control_maintenance, state);
 
        *bse = se;
 
@@ -1099,7 +1079,7 @@ store_open(struct store_state *state,
 
        fname = store_fname(state, ident, elem_idx);
        if (fname == NULL) {
-               NSLOG(netsurf, INFO, "filename error");
+               NSLOG(netsurf, ERROR, "filename error");
                return -1;
        }
 
@@ -1107,14 +1087,14 @@ store_open(struct store_state *state,
        if (openflags & O_CREAT) {
                ret = netsurf_mkdir_all(fname);
                if (ret != NSERROR_OK) {
-                       NSLOG(netsurf, INFO,
+                       NSLOG(netsurf, WARNING,
                              "file path \"%s\" could not be created", fname);
                        free(fname);
                        return -1;
                }
        }
 
-       NSLOG(netsurf, INFO, "opening %s", fname);
+       NSLOG(netsurf, DEBUG, "opening %s", fname);
        fd = open(fname, openflags, S_IRUSR | S_IWUSR);
 
        free(fname);
@@ -1122,57 +1102,6 @@ store_open(struct store_state *state,
        return fd;
 }
 
-/**
- * Construct address ident to filesystem entry map
- *
- * To allow a filesystem entry to be found from it's identifier we
- * construct an mapping index. This is a hash map from the entries URL
- * (its unique key) to filesystem entry.
- *
- * As the entire entry list must be iterated over to construct the map
- * we also compute the total storage in use.
- *
- * @param state The backing store global state.
- * @return NSERROR_OK on success or NSERROR_NOMEM if the map storage
- *         could not be allocated.
- */
-static nserror
-build_entrymap(struct store_state *state)
-{
-       unsigned int eloop;
-
-       NSLOG(netsurf, INFO, "Allocating %"PRIsizet" bytes for max of %d 
buckets",
-             (1 << state->ident_bits) * sizeof(entry_index_t),
-             1 << state->ident_bits);
-
-       state->addrmap = calloc(1 << state->ident_bits, sizeof(entry_index_t));
-       if (state->addrmap == NULL) {
-               return NSERROR_NOMEM;
-       }
-
-       state->total_alloc = 0;
-
-       for (eloop = 1; eloop < state->last_entry; eloop++) {
-
-               NSLOG(llcache, DEEPDEBUG,
-                     "entry:%d ident:0x%08x used:%d",
-                     eloop,
-                     BS_ADDRESS(state->entries[eloop].ident, state),
-                     state->entries[eloop].use_count);
-
-               /* update the address map to point at the entry */
-               BS_ENTRY_INDEX(state->entries[eloop].ident, state) = eloop;
-
-               /* account for the storage space */
-               state->total_alloc += 
state->entries[eloop].elem[ENTRY_ELEM_DATA].size;
-               state->total_alloc += 
state->entries[eloop].elem[ENTRY_ELEM_META].size;
-               /* ensure entry does not have any allocation state */
-               state->entries[eloop].elem[ENTRY_ELEM_DATA].flags &= 
~(ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP);
-               state->entries[eloop].elem[ENTRY_ELEM_META].flags &= 
~(ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP);
-       }
-
-       return NSERROR_OK;
-}
 
 /**
  * Unlink entries file
@@ -1206,46 +1135,74 @@ unlink_entries(struct store_state *state)
 static nserror
 read_entries(struct store_state *state)
 {
-       int fd;
-       ssize_t rd;
-       size_t entries_size;
        char *fname = NULL;
+       char *url;
+       nsurl *nsurl;
        nserror ret;
+       size_t read_entries = 0;
+       struct store_entry *ent;
+       int fd;
 
        ret = netsurf_mkpath(&fname, NULL, 2, state->path, ENTRIES_FNAME);
        if (ret != NSERROR_OK) {
                return ret;
        }
 
-       entries_size = (1 << state->entry_bits) * sizeof(struct store_entry);
-
-       NSLOG(netsurf, INFO,
-             "Allocating %"PRIsizet" bytes for max of %d entries of 
%"PRIsizet" length elements %"PRIsizet" length",
-             entries_size,
-             1 << state->entry_bits,
-             sizeof(struct store_entry),
-             sizeof(struct store_entry_element));
-
-       state->entries = calloc(1, entries_size);
+       state->entries = hashmap_create(&entries_hashmap_parameters);
        if (state->entries == NULL) {
                free(fname);
                return NSERROR_NOMEM;
        }
 
        fd = open(fname, O_RDWR);
-       free(fname);
        if (fd != -1) {
-               rd = read(fd, state->entries, entries_size);
-               close(fd);
-               if (rd > 0) {
-                       state->last_entry = rd / sizeof(struct store_entry);
-                       NSLOG(netsurf, INFO, "Read %d entries",
-                             state->last_entry);
+               uint32_t urllen;
+               while (read(fd, &urllen, sizeof(urllen)) == sizeof(urllen)) {
+                       url = calloc(1, urllen+1);
+                       if (read(fd, url, urllen) != urllen) {
+                               free(url);
+                               close(fd);
+                               free(fname);
+                               return NSERROR_INIT_FAILED;
+                       }
+                       ret = nsurl_create(url, &nsurl);
+                       if (ret != NSERROR_OK) {
+                               free(url);
+                               close(fd);
+                               free(fname);
+                               return ret;
+                       }
+                       free(url);
+                       /* We have to be careful here about nsurl refs */
+                       ent = hashmap_insert(state->entries, nsurl);
+                       if (ent == NULL) {
+                               nsurl_unref(nsurl);
+                               close(fd);
+                               free(fname);
+                               return NSERROR_NOMEM;
+                       }
+                       /* At this point, ent actually owns a ref of nsurl */
+                       if (read(fd, ent, sizeof(*ent)) != sizeof(*ent)) {
+                               /* The read failed, so reset the ptr */
+                               ent->url = nsurl; /* It already had a ref */
+                               nsurl_unref(nsurl);
+                               close(fd);
+                               free(fname);
+                               return NSERROR_INIT_FAILED;
+                       }
+                       ent->url = nsurl; /* It already owns a ref */
+                       nsurl_unref(nsurl);
+                       NSLOG(netsurf, DEBUG, "Successfully read entry for %s", 
nsurl_access(ent->url));
+                       read_entries++;
+                       state->total_alloc += ent->elem[ENTRY_ELEM_DATA].size;
+                       state->total_alloc += ent->elem[ENTRY_ELEM_META].size;
                }
-       } else {
-               /* could rebuild entries from fs */
-               state->last_entry = 1;
+               close(fd);
        }
+
+       NSLOG(netsurf, INFO, "Read %"PRIsizet" entries from cache", 
read_entries);
+
+       free(fname);
        return NSERROR_OK;
 }
 
@@ -1283,7 +1240,7 @@ read_blocks(struct store_state *state)
                                          
&state->blocks[elem_idx][bfidx].use_map[0],
                                          BLOCK_USE_MAP_SIZE);
                                if (rd <= 0) {
-                                       NSLOG(netsurf, INFO,
+                                       NSLOG(netsurf, ERROR,
                                              "reading block file %d use index 
on file number %d failed",
                                              elem_idx,
                                              bfidx);
@@ -1382,9 +1339,6 @@ write_control(struct store_state *state)
        }
 
        fprintf(fcontrol, "%u%c", CONTROL_VERSION, 0);
-       fprintf(fcontrol, "%u%c", state->entry_bits, 0);
-       fprintf(fcontrol, "%u%c", state->ident_bits, 0);
-       fprintf(fcontrol, "%u%c", state->last_entry, 0);
 
        fclose(fcontrol);
 
@@ -1404,8 +1358,6 @@ read_control(struct store_state *state)
        nserror ret;
        FILE *fcontrol;
        unsigned int ctrlversion;
-       unsigned int addrbits;
-       unsigned int entrybits;
        char *fname = NULL;
 
        ret = netsurf_mkpath(&fname, NULL, 2, state->path, "control");
@@ -1443,27 +1395,8 @@ read_control(struct store_state *state)
                goto control_error;
        }
 
-       /* second line is log2 max number of entries */
-       if (fscanf(fcontrol, "%u", &entrybits) != 1) {
-               goto control_error;
-       }
-       if (fgetc(fcontrol) != 0) {
-               goto control_error;
-       }
-
-       /* second line is log2 size of address hash */
-       if (fscanf(fcontrol, "%u", &addrbits) != 1) {
-               goto control_error;
-       }
-       if (fgetc(fcontrol) != 0) {
-               goto control_error;
-       }
-
        fclose(fcontrol);
 
-       state->entry_bits = entrybits;
-       state->ident_bits = addrbits;
-
        return NSERROR_OK;
 
 control_error: /* problem with the control file */
@@ -1515,22 +1448,10 @@ initialise(const struct llcache_store_parameters 
*parameters)
        newstate->limit = parameters->limit;
        newstate->hysteresis = parameters->hysteresis;
 
-       if (parameters->address_size == 0) {
-               newstate->ident_bits = DEFAULT_IDENT_SIZE;
-       } else {
-               newstate->ident_bits = parameters->address_size;
-       }
-
-       if (parameters->entry_size == 0) {
-               newstate->entry_bits = DEFAULT_ENTRY_SIZE;
-       } else {
-               newstate->entry_bits = parameters->entry_size;
-       }
-
        /* read store control and create new if required */
        ret = read_control(newstate);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "read control failed %s",
+               NSLOG(netsurf, ERROR, "read control failed %s",
                      messages_get_errorcode(ret));
                ret = write_control(newstate);
                if (ret == NSERROR_OK) {
@@ -1545,13 +1466,6 @@ initialise(const struct llcache_store_parameters 
*parameters)
                return ret;
        }
 
-       /* ensure the maximum number of entries can be represented in
-        * the type available to store it.
-        */
-       if (newstate->entry_bits > (8 * sizeof(entry_index_t))) {
-               newstate->entry_bits = (8 * sizeof(entry_index_t));
-       }
-
        /* read filesystem entries */
        ret = read_entries(newstate);
        if (ret != NSERROR_OK) {
@@ -1561,21 +1475,11 @@ initialise(const struct llcache_store_parameters 
*parameters)
                return ret;
        }
 
-       /* build entry hash map */
-       ret = build_entrymap(newstate);
-       if (ret != NSERROR_OK) {
-               /* that obviously went well */
-               free(newstate->entries);
-               free(newstate->path);
-               free(newstate);
-               return ret;
-       }
-
+       /* read blocks */
        ret = read_blocks(newstate);
        if (ret != NSERROR_OK) {
                /* oh dear */
-               free(newstate->addrmap);
-               free(newstate->entries);
+               hashmap_destroy(newstate->entries);
                free(newstate->path);
                free(newstate);
                return ret;
@@ -1586,12 +1490,10 @@ initialise(const struct llcache_store_parameters 
*parameters)
        NSLOG(netsurf, INFO, "FS backing store init successful");
 
        NSLOG(netsurf, INFO,
-             "path:%s limit:%"PRIsizet" hyst:%"PRIsizet" addr:%d entries:%d",
+             "path:%s limit:%"PRIsizet" hyst:%"PRIsizet,
              newstate->path,
              newstate->limit,
-             newstate->hysteresis,
-             newstate->ident_bits,
-             newstate->entry_bits);
+             newstate->hysteresis);
        NSLOG(netsurf, INFO, "Using %"PRIu64"/%"PRIsizet,
              newstate->total_alloc, newstate->limit);
 
@@ -1614,7 +1516,7 @@ finalise(void)
        unsigned int op_count;
 
        if (storestate != NULL) {
-               guit->misc->schedule(-1, control_maintinance, storestate);
+               guit->misc->schedule(-1, control_maintenance, storestate);
                write_entries(storestate);
                write_blocks(storestate);
 
@@ -1643,8 +1545,7 @@ finalise(void)
                              0);
                }
 
-               free(storestate->addrmap);
-               free(storestate->entries);
+               hashmap_destroy(storestate->entries);
                free(storestate->path);
                free(storestate);
                storestate = NULL;
@@ -1676,7 +1577,7 @@ static nserror store_write_block(struct store_state 
*state,
                state->blocks[elem_idx][bf].fd = store_open(state, bf,
                                elem_idx + ENTRY_ELEM_COUNT, O_CREAT | O_RDWR);
                if (state->blocks[elem_idx][bf].fd == -1) {
-                       NSLOG(netsurf, INFO, "Open failed errno %d", errno);
+                       NSLOG(netsurf, ERROR, "Open failed errno %d", errno);
                        return NSERROR_SAVE_FAILED;
                }
 
@@ -1691,7 +1592,7 @@ static nserror store_write_block(struct store_state 
*state,
                    bse->elem[elem_idx].size,
                    offst);
        if (wr != (ssize_t)bse->elem[elem_idx].size) {
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, ERROR,
                      "Write failed %"PRIssizet" of %d bytes from %p at 0x%jx 
block %d errno %d",
                      wr,
                      bse->elem[elem_idx].size,
@@ -1726,10 +1627,10 @@ static nserror store_write_file(struct store_state 
*state,
        int fd;
        int err;
 
-       fd = store_open(state, bse->ident, elem_idx, O_CREAT | O_WRONLY);
+       fd = store_open(state, nsurl_hash(bse->url), elem_idx, O_CREAT | 
O_WRONLY);
        if (fd < 0) {
                perror("");
-               NSLOG(netsurf, INFO, "Open failed %d errno %d", fd, errno);
+               NSLOG(netsurf, ERROR, "Open failed %d errno %d", fd, errno);
                return NSERROR_SAVE_FAILED;
        }
 
@@ -1738,7 +1639,7 @@ static nserror store_write_file(struct store_state *state,
 
        close(fd);
        if (wr != (ssize_t)bse->elem[elem_idx].size) {
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, ERROR,
                      "Write failed %"PRIssizet" of %d bytes from %p errno %d",
                      wr,
                      bse->elem[elem_idx].size,
@@ -1749,7 +1650,7 @@ static nserror store_write_file(struct store_state *state,
                return NSERROR_SAVE_FAILED;
        }
 
-       NSLOG(netsurf, INFO, "Wrote %"PRIssizet" bytes from %p", wr,
+       NSLOG(netsurf, VERBOSE, "Wrote %"PRIssizet" bytes from %p", wr,
              bse->elem[elem_idx].data);
 
        return NSERROR_OK;
@@ -1791,7 +1692,7 @@ store(nsurl *url,
        /* set the store entry up */
        ret = set_store_entry(storestate, url, elem_idx, data, datalen, &bse);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "store entry setting failed");
+               NSLOG(netsurf, ERROR, "store entry setting failed");
                return ret;
        }
 
@@ -1814,7 +1715,7 @@ static nserror entry_release_alloc(struct 
store_entry_element *elem)
        if ((elem->flags & ENTRY_ELEM_FLAG_HEAP) != 0) {
                elem->ref--;
                if (elem->ref == 0) {
-                       NSLOG(netsurf, INFO, "freeing %p", elem->data);
+                       NSLOG(netsurf, DEEPDEBUG, "freeing %p", elem->data);
                        free(elem->data);
                        elem->flags &= ~ENTRY_ELEM_FLAG_HEAP;
                }
@@ -1846,7 +1747,7 @@ static nserror store_read_block(struct store_state *state,
                state->blocks[elem_idx][bf].fd = store_open(state, bf,
                                elem_idx + ENTRY_ELEM_COUNT, O_CREAT | O_RDWR);
                if (state->blocks[elem_idx][bf].fd == -1) {
-                       NSLOG(netsurf, INFO, "Open failed errno %d", errno);
+                       NSLOG(netsurf, ERROR, "Open failed errno %d", errno);
                        return NSERROR_SAVE_FAILED;
                }
 
@@ -1861,7 +1762,7 @@ static nserror store_read_block(struct store_state *state,
                   bse->elem[elem_idx].size,
                   offst);
        if (rd != (ssize_t)bse->elem[elem_idx].size) {
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, ERROR,
                      "Failed reading %"PRIssizet" of %d bytes into %p from 
0x%jx block %d errno %d",
                      rd,
                      bse->elem[elem_idx].size,
@@ -1872,7 +1773,7 @@ static nserror store_read_block(struct store_state *state,
                return NSERROR_SAVE_FAILED;
        }
 
-       NSLOG(netsurf, INFO,
+       NSLOG(netsurf, DEEPDEBUG,
              "Read %"PRIssizet" bytes into %p from 0x%jx block %d", rd,
              bse->elem[elem_idx].data, (uintmax_t)offst,
              bse->elem[elem_idx].block);
@@ -1898,9 +1799,9 @@ static nserror store_read_file(struct store_state *state,
        size_t tot = 0; /* total size */
 
        /* separate file in backing store */
-       fd = store_open(storestate, bse->ident, elem_idx, O_RDONLY);
+       fd = store_open(storestate, nsurl_hash(bse->url), elem_idx, O_RDONLY);
        if (fd < 0) {
-               NSLOG(netsurf, INFO, "Open failed %d errno %d", fd, errno);
+               NSLOG(netsurf, ERROR, "Open failed %d errno %d", fd, errno);
                /** @todo should this invalidate the entry? */
                return NSERROR_NOT_FOUND;
        }
@@ -1910,7 +1811,7 @@ static nserror store_read_file(struct store_state *state,
                          bse->elem[elem_idx].data + tot,
                          bse->elem[elem_idx].size - tot);
                if (rd <= 0) {
-                       NSLOG(netsurf, INFO,
+                       NSLOG(netsurf, ERROR,
                              "read error returned %"PRIssizet" errno %d",
                              rd,
                              errno);
@@ -1922,7 +1823,7 @@ static nserror store_read_file(struct store_state *state,
 
        close(fd);
 
-       NSLOG(netsurf, INFO, "Read %"PRIsizet" bytes into %p", tot,
+       NSLOG(netsurf, DEEPDEBUG, "Read %"PRIsizet" bytes into %p", tot,
              bse->elem[elem_idx].data);
 
        return ret;
@@ -1956,13 +1857,13 @@ fetch(nsurl *url,
        /* fetch store entry */
        ret = get_store_entry(storestate, url, &bse);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "entry not found");
+               NSLOG(netsurf, DEBUG, "Entry for %s not found", 
nsurl_access(url));
                storestate->miss_count++;
                return ret;
        }
        storestate->hit_count++;
 
-       NSLOG(netsurf, INFO, "retrieving cache data for url:%s",
+       NSLOG(netsurf, DEBUG, "retrieving cache data for url:%s",
              nsurl_access(url));
 
        /* calculate the entry element index */
@@ -1978,7 +1879,7 @@ fetch(nsurl *url,
                /* use the existing allocation and bump the ref count. */
                elem->ref++;
 
-               NSLOG(netsurf, INFO,
+               NSLOG(netsurf, DEEPDEBUG,
                      "Using existing entry (%p) allocation %p refs:%d", bse,
                      elem->data, elem->ref);
 
@@ -1986,11 +1887,11 @@ fetch(nsurl *url,
                /* allocate from the heap */
                elem->data = malloc(elem->size);
                if (elem->data == NULL) {
-                       NSLOG(netsurf, INFO,
+                       NSLOG(netsurf, ERROR,
                              "Failed to create new heap allocation");
                        return NSERROR_NOMEM;
                }
-               NSLOG(netsurf, INFO, "Created new heap allocation %p",
+               NSLOG(netsurf, DEEPDEBUG, "Created new heap allocation %p",
                      elem->data);
 
                /* mark the entry as having a valid heap allocation */
@@ -2040,7 +1941,7 @@ static nserror release(nsurl *url, enum 
backing_store_flags bsflags)
 
        ret = get_store_entry(storestate, url, &bse);
        if (ret != NSERROR_OK) {
-               NSLOG(netsurf, INFO, "entry not found");
+               NSLOG(netsurf, WARNING, "entry not found");
                return ret;
        }
 
diff --git a/content/llcache.c b/content/llcache.c
index 3a75bf9..9c74fbd 100644
--- a/content/llcache.c
+++ b/content/llcache.c
@@ -3769,6 +3769,11 @@ void llcache_finalise(void)
        llcache_object *object, *next;
        uint64_t total_bandwidth = 0; /* total bandwidth */
 
+       /* Attempt to persist anything we have left lying around */
+       llcache_persist(NULL);
+       /* Now clear the persistence callback */
+       guit->misc->schedule(-1, llcache_persist, NULL);
+
        /* Clean uncached objects */
        for (object = llcache->uncached_objects; object != NULL; object = next) 
{
                llcache_object_user *user, *next_user;
diff --git a/content/llcache.h b/content/llcache.h
index 514272f..f9a3016 100644
--- a/content/llcache.h
+++ b/content/llcache.h
@@ -121,43 +121,6 @@ struct llcache_store_parameters {
 
        size_t limit; /**< The backing store upper bound target size */
        size_t hysteresis; /**< The hysteresis around the target size */
-
-       /** log2 of the default maximum number of entries the cache
-        * can track.
-        *
-        * If unset this defaults to 16 (65536 entries) The cache
-        * control file takes precedence so cache data remains
-        * portable between builds with differing defaults.
-        */
-       unsigned int entry_size;
-
-       /** log2 of the default number of entries in the mapping between
-        * the url and cache entries.
-        *
-        * @note This is exposing an internal implementation detail of
-        * the filesystem based default backing store implementation.
-        * However it is likely any backing store implementation will
-        * need some way to map url to cache entries so it is a
-        * generally useful configuration value.
-        *
-        * Too small a value will cause unecessary collisions and
-        * cache misses and larger values cause proportionaly larger
-        * amounts of memory to be used.
-        *
-        * The "birthday paradox" means that the hash will experience
-        * a collision in every 2^(address_size/2) urls the cache
-        * stores.
-        *
-        * A value of 20 means one object stored in every 1024 will
-        * cause a collion and a cache miss while using two megabytes
-        * of storage.
-        *
-        * If unset this defaults to 20 (1048576 entries using two
-        * megabytes) The cache control file takes precedence so cache
-        * data remains portable between builds with differing
-        * defaults.
-        */
-       unsigned int address_size;
 };
 
 /**
diff --git a/test/hashmap.c b/test/hashmap.c
index 87db6c1..ed951e9 100644
--- a/test/hashmap.c
+++ b/test/hashmap.c
@@ -151,6 +151,20 @@ static hashmap_parameters_t test_params = {
        .value_destroy = value_destroy,
 };
 
+/* Iteration helpers */
+
+static size_t iteration_counter = 0;
+static size_t iteration_stop = 0;
+static char iteration_ctx = 0;
+
+static bool
+hashmap_test_iterator_cb(void *key, void *value, void *ctx)
+{
+       ck_assert(ctx == &iteration_ctx);
+       iteration_counter++;
+       return iteration_counter == iteration_stop;
+}
+
 /* Fixtures for basic tests */
 
 static hashmap_t *test_hashmap = NULL;
@@ -183,7 +197,7 @@ basic_fixture_teardown(void)
 
 START_TEST(empty_hashmap_create_destroy)
 {
-       /* Do nothing in here, all the checks are in the fixture */
+       ck_assert_int_eq(hashmap_count(test_hashmap), 0);
 }
 END_TEST
 
@@ -199,6 +213,7 @@ START_TEST(insert_works)
         hashmap_test_value_t *value = hashmap_insert(test_hashmap, 
corestring_nsurl_about_blank);
        ck_assert(value != NULL);
        ck_assert(value->key == corestring_nsurl_about_blank);
+       ck_assert_int_eq(hashmap_count(test_hashmap), 1);
 }
 END_TEST
 
@@ -215,9 +230,11 @@ START_TEST(insert_then_remove)
        ck_assert(value->key == corestring_nsurl_about_blank);
        ck_assert_int_eq(keys, 1);
        ck_assert_int_eq(values, 1);
+       ck_assert_int_eq(hashmap_count(test_hashmap), 1);
        ck_assert(hashmap_remove(test_hashmap, corestring_nsurl_about_blank) == 
true);
        ck_assert_int_eq(keys, 0);
        ck_assert_int_eq(values, 0);
+       ck_assert_int_eq(hashmap_count(test_hashmap), 0);
 }
 END_TEST
 
@@ -230,6 +247,35 @@ START_TEST(insert_then_lookup)
 }
 END_TEST
 
+START_TEST(iterate_empty)
+{
+       iteration_stop = iteration_counter = 0;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, 0);
+}
+END_TEST
+
+START_TEST(iterate_one)
+{
+       iteration_stop = iteration_counter = 0;
+        hashmap_test_value_t *value = hashmap_insert(test_hashmap, 
corestring_nsurl_about_blank);
+       ck_assert(value != NULL);
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, 1);
+}
+END_TEST
+
+START_TEST(iterate_one_and_stop)
+{
+       iteration_stop = 1;
+       iteration_counter = 0;
+        hashmap_test_value_t *value = hashmap_insert(test_hashmap, 
corestring_nsurl_about_blank);
+       ck_assert(value != NULL);
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == true);
+       ck_assert_int_eq(iteration_counter, 1);
+}
+END_TEST
+
 static TCase *basic_api_case_create(void)
 {
        TCase *tc;
@@ -245,7 +291,11 @@ static TCase *basic_api_case_create(void)
        tcase_add_test(tc, remove_not_present);
        tcase_add_test(tc, insert_then_remove);
        tcase_add_test(tc, insert_then_lookup);
-
+       
+       tcase_add_test(tc, iterate_empty);
+       tcase_add_test(tc, iterate_one);
+       tcase_add_test(tc, iterate_one_and_stop);
+       
        return tc;
 }
 
@@ -374,6 +424,59 @@ START_TEST(chain_add_all_twice_remove_all)
 }
 END_TEST
 
+START_TEST(chain_add_all_twice_remove_all_iterate)
+{
+       case_pair *chain_case;
+       size_t chain_count = 0;
+       
+       for (chain_case = chain_pairs;
+            chain_case->url != NULL;
+            chain_case++) {
+               ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) == 
NULL);
+               ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != 
NULL);
+               chain_count++;
+       }
+       
+       iteration_counter = 0;
+       iteration_stop = 0;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, chain_count);
+       
+       for (chain_case = chain_pairs;
+            chain_case->url != NULL;
+            chain_case++) {
+               ck_assert(hashmap_lookup(test_hashmap, chain_case->nsurl) != 
NULL);
+               ck_assert(hashmap_insert(test_hashmap, chain_case->nsurl) != 
NULL);
+       }
+
+       iteration_counter = 0;
+       iteration_stop = 0;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, chain_count);
+       ck_assert_int_eq(hashmap_count(test_hashmap), chain_count);
+       
+       iteration_counter = 0;
+       iteration_stop = chain_count;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == true);
+       ck_assert_int_eq(iteration_counter, chain_count);
+       
+       for (chain_case = chain_pairs;
+            chain_case->url != NULL;
+            chain_case++) {
+               ck_assert(hashmap_remove(test_hashmap, chain_case->nsurl) == 
true);
+       }
+
+       iteration_counter = 0;
+       iteration_stop = chain_count;
+       ck_assert(hashmap_iterate(test_hashmap, hashmap_test_iterator_cb, 
&iteration_ctx) == false);
+       ck_assert_int_eq(iteration_counter, 0);
+       
+       ck_assert_int_eq(keys, 0);
+       ck_assert_int_eq(values, 0);
+       ck_assert_int_eq(hashmap_count(test_hashmap), 0);
+}
+END_TEST
+
 #define CHAIN_TEST_MALLOC_COUNT_MAX 60
 
 START_TEST(chain_add_all_remove_all_alloc)
@@ -431,6 +534,7 @@ static TCase *chain_case_create(void)
        tcase_add_test(tc, chain_add_remove_all);
        tcase_add_test(tc, chain_add_all_remove_all);
        tcase_add_test(tc, chain_add_all_twice_remove_all);
+       tcase_add_test(tc, chain_add_all_twice_remove_all_iterate);
 
        tcase_add_loop_test(tc, chain_add_all_remove_all_alloc, 0, 
CHAIN_TEST_MALLOC_COUNT_MAX + 1);
        
diff --git a/utils/Makefile b/utils/Makefile
index e0fbd8e..fa5f58d 100644
--- a/utils/Makefile
+++ b/utils/Makefile
@@ -6,6 +6,7 @@ S_UTILS := \
        file.c \
        filename.c \
        filepath.c \
+       hashmap.c \
        hashtable.c \
        idna.c \
        libdom.c \
diff --git a/utils/hashmap.c b/utils/hashmap.c
index 7ed1994..814dc55 100644
--- a/utils/hashmap.c
+++ b/utils/hashmap.c
@@ -55,6 +55,11 @@ struct hashmap_s {
         * The number of buckets in this map
         */
        uint32_t bucket_count;
+       
+       /**
+        * The number of entries in this map
+        */
+       size_t entry_count;
 };
 
 /* Exported function, documented in hashmap.h */
@@ -65,14 +70,16 @@ hashmap_create(hashmap_parameters_t *params)
 
        ret->params = params;
        ret->bucket_count = DEFAULT_HASHMAP_BUCKETS;
+       ret->entry_count = 0;
        ret->buckets = malloc(ret->bucket_count * sizeof(hashmap_entry_t *));
-       memset(ret->buckets, 0, ret->bucket_count * sizeof(hashmap_entry_t *));
 
        if (ret->buckets == NULL) {
                free(ret);
                return NULL;
        }
-       
+
+       memset(ret->buckets, 0, ret->bucket_count * sizeof(hashmap_entry_t *));
+
        return ret;
 }
 
@@ -85,11 +92,12 @@ hashmap_destroy(hashmap_t *hashmap)
 
        for (bucket = 0; bucket < hashmap->bucket_count; bucket++) {
                for (entry = hashmap->buckets[bucket];
-                    entry != NULL;
-                    entry = entry->next) {
+                    entry != NULL;) {
+                       hashmap_entry_t *next = entry->next;
                        hashmap->params->value_destroy(entry->value);
                        hashmap->params->key_destroy(entry->key);
                        free(entry);
+                       entry = next;
                }
        }
 
@@ -175,7 +183,9 @@ hashmap_insert(hashmap_t *hashmap, void *key)
        }
 
        hashmap->buckets[bucket] = entry;
-       
+
+       hashmap->entry_count++;
+
        return entry->value;
 
 err:
@@ -206,6 +216,7 @@ hashmap_remove(hashmap_t *hashmap, void *key)
                                }
                                *entry->prevptr = entry->next;
                                free(entry);
+                               hashmap->entry_count--;
                                return true;
                        }
                }
@@ -213,3 +224,29 @@ hashmap_remove(hashmap_t *hashmap, void *key)
 
        return false;
 }
+
+/* Exported function, documented in hashmap.h */
+bool
+hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t cb, void *ctx)
+{
+       for (uint32_t bucket = 0;
+            bucket < hashmap->bucket_count;
+            bucket++) {
+               for (hashmap_entry_t *entry = hashmap->buckets[bucket];
+                    entry != NULL;
+                    entry = entry->next) {
+                       /* If the callback returns true, we early-exit */
+                       if (cb(entry->key, entry->value, ctx))
+                               return true;
+               }
+       }
+
+       return false;
+}
+
+/* Exported function, documented in hashmap.h */
+size_t
+hashmap_count(hashmap_t *hashmap)
+{
+       return hashmap->entry_count;
+}
diff --git a/utils/hashmap.h b/utils/hashmap.h
index 4e1237a..3968fd3 100644
--- a/utils/hashmap.h
+++ b/utils/hashmap.h
@@ -32,6 +32,46 @@
 typedef struct hashmap_s hashmap_t;
 
 /**
+ * Key cloning function type
+ */
+typedef void* (*hashmap_key_clone_t)(void *);
+
+/**
+ * Key destructor function type
+ */
+typedef void (*hashmap_key_destroy_t)(void *);
+
+/**
+ * Key hashing function type
+ */
+typedef uint32_t (*hashmap_key_hash_t)(void *);
+
+/**
+ * Key comparison function type
+ */
+typedef bool (*hashmap_key_eq_t)(void *, void*);
+
+/**
+ * Value allocation function type
+ */
+typedef void* (*hashmap_value_alloc_t)(void *);
+
+/**
+ * Value destructor function type
+ */
+typedef void (*hashmap_value_destroy_t)(void *);
+
+/**
+ * Hashmap iteration callback function type.
+ *
+ * First parameter is the key, second is the value.
+ * The final parameter is the context pointer for the iteration.
+ *
+ * Return true to stop iterating early
+ */
+typedef bool (*hashmap_iteration_cb_t)(void *, void *, void *);
+
+/**
  * Parameters for hashmaps
  */
 typedef struct {
@@ -39,12 +79,12 @@ typedef struct {
         * A function which when called will clone a key and give
         * ownership of the returned object to the hashmap
         */
-       void * (*key_clone)(void *key);
+       hashmap_key_clone_t key_clone;
 
        /**
         * A function which when given a key will return its hash.
         */
-       uint32_t (*key_hash)(void *key);
+       hashmap_key_hash_t key_hash;
        
        /**
         * A function to compare two keys and return if they are equal.
@@ -52,22 +92,22 @@ typedef struct {
         * as the function is a full equality model.
         * (i.e. key1 == key2 => key2 == key1)
         */
-       bool (*key_eq)(void *key1, void *key2);
+       hashmap_key_eq_t key_eq;
         
        /**
         * A function which when called will destroy a key object
         */
-       void (*key_destroy)(void *key);
+       hashmap_key_destroy_t key_destroy;
 
        /**
         * A function which when called will allocate a value object
         */
-       void * (*value_alloc)(void *key);
+       hashmap_value_alloc_t value_alloc;
 
        /**
         * A function which when called will destroy a value object
         */
-       void (*value_destroy)(void *value);
+       hashmap_value_destroy_t value_destroy;
 } hashmap_parameters_t;
 
 
@@ -133,5 +173,25 @@ void *hashmap_insert(hashmap_t *hashmap, void *key);
  */
 bool hashmap_remove(hashmap_t *hashmap, void *key);
 
+/**
+ * Iterate the hashmap
+ *
+ * For each key/value pair in the hashmap, call the callback passing in
+ * the key and value.  During iteration you MUST NOT mutate the hashmap.
+ *
+ * \param hashmap The hashmap to iterate
+ * \param cb The callback for each key,value pair
+ * \param ctx The callback context
+ * \return Whether or not we stopped iteration early
+ */
+bool hashmap_iterate(hashmap_t *hashmap, hashmap_iteration_cb_t cb, void *ctx);
+
+/**
+ * Get the number of entries in this map
+ *
+ * \param hashmap The hashmap to retrieve the entry count from
+ * \return The number of entries in the hashmap
+ */
+size_t hashmap_count(hashmap_t *hashmap);
 
 #endif


-- 
NetSurf Browser

_______________________________________________
netsurf-commits mailing list
netsurf-commits@netsurf-browser.org
http://listmaster.pepperfish.net/cgi-bin/mailman/listinfo/netsurf-commits-netsurf-browser.org