From d1a3e6b7b72f54f291f11a50cd5c043984126885 Mon Sep 17 00:00:00 2001 From: Robin Watts Date: Thu, 25 Apr 2013 06:09:47 -0700 Subject: Multi-threaded store SEGV fixes and debug improvements. Fix race condition in the store. When storing an item, we immediately put it into the hash (thus getting our existence check). We then check and try to free enough space for it in the budget. If we cannot free enough, we remove the item from the hash. The race condition comes if someone else finds it in the hash in the meantime. To fix this, we update all 'finds' of things in the hash to move it to the head of the LRU chain (regardless of whether it was in the chain before or not). We only remove it from the hash in the 'failed-to-fit-in-the-budget' case if it's not in the chain already. Also, we fix a bug in the "failed to fit" removal case where we were failing to realise that the the pos pointer was not valid any more. In the course of tracking this bug down various debug functions were improved. These are committed here too. --- fitz/base_hash.c | 19 +++++++--- fitz/fitz-internal.h | 2 ++ fitz/res_store.c | 100 +++++++++++++++++++++++++++++++++------------------ 3 files changed, 81 insertions(+), 40 deletions(-) diff --git a/fitz/base_hash.c b/fitz/base_hash.c index 037988cb..1da8cac9 100644 --- a/fitz/base_hash.c +++ b/fitz/base_hash.c @@ -311,11 +311,11 @@ fz_hash_remove_fast(fz_context *ctx, fz_hash_table *table, void *key, unsigned p { fz_hash_entry *ents = table->ents; - if (memcmp(key, ents[pos].key, table->keylen) != 0) + if (ents[pos].val == NULL || memcmp(key, ents[pos].key, table->keylen) != 0) { - /* The key didn't match! The table must have been rebuilt - * (or the contents moved) in the meantime. Do the removal - * the slow way. */ + /* The value isn't there, or the key didn't match! The table + * must have been rebuilt (or the contents moved) in the + * meantime. Do the removal the slow way. */ fz_hash_remove(ctx, table, key); } else @@ -325,6 +325,12 @@ fz_hash_remove_fast(fz_context *ctx, fz_hash_table *table, void *key, unsigned p #ifndef NDEBUG void fz_print_hash(fz_context *ctx, FILE *out, fz_hash_table *table) +{ + fz_print_hash_details(ctx, out, table, NULL); +} + +void +fz_print_hash_details(fz_context *ctx, FILE *out, fz_hash_table *table, void (*details)(FILE *,void*)) { int i, k; @@ -339,7 +345,10 @@ fz_print_hash(fz_context *ctx, FILE *out, fz_hash_table *table) fprintf(out, "table % 4d: key=", i); for (k = 0; k < MAX_KEY_LEN; k++) fprintf(out, "%02x", ((char*)table->ents[i].key)[k]); - fprintf(out, " val=$%p\n", table->ents[i].val); + if (details) + details(out, table->ents[i].val); + else + fprintf(out, " val=$%p\n", table->ents[i].val); } } } diff --git a/fitz/fitz-internal.h b/fitz/fitz-internal.h index 7193301a..bf7d2873 100644 --- a/fitz/fitz-internal.h +++ b/fitz/fitz-internal.h @@ -271,6 +271,7 @@ void *fz_hash_get_val(fz_context *ctx, fz_hash_table *table, int idx); #ifndef NDEBUG void fz_print_hash(fz_context *ctx, FILE *out, fz_hash_table *table); +void fz_print_hash_details(fz_context *ctx, FILE *out, fz_hash_table *table, void (*details)(FILE *, void *)); #endif /* @@ -587,6 +588,7 @@ int fz_store_scavenge(fz_context *ctx, unsigned int size, int *phase); */ #ifndef NDEBUG void fz_print_store(fz_context *ctx, FILE *out); +void fz_print_store_locked(fz_context *ctx, FILE *out); #endif struct fz_buffer_s diff --git a/fitz/res_store.c b/fitz/res_store.c index 93a7c6e3..bfe7eedb 100644 --- a/fitz/res_store.c +++ b/fitz/res_store.c @@ -188,6 +188,31 @@ ensure_space(fz_context *ctx, unsigned int tofree) return count; } +static void +touch(fz_store *store, fz_item *item) +{ + if (item->next != item) + { + /* Already in the list - unlink it */ + if (item->next) + item->next->prev = item->prev; + else + store->tail = item->prev; + if (item->prev) + item->prev->next = item->next; + else + store->head = item->next; + } + /* Now relink it at the start of the LRU chain */ + item->next = store->head; + if (item->next) + item->next->prev = item; + else + store->tail = item; + store->head = item; + item->prev = NULL; +} + void * fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_store_type *type) { @@ -256,6 +281,8 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_ } fz_catch(ctx) { + /* Any error here means that item never made it into the + * hash - so no one else can have a reference. */ fz_unlock(ctx, FZ_LOCK_ALLOC); fz_free(ctx, item); type->drop_key(ctx, key); @@ -265,6 +292,7 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_ { /* There was one there already! Take a new reference * to the existing one, and drop our current one. */ + touch(store, existing); if (existing->val->refs > 0) existing->val->refs++; fz_unlock(ctx, FZ_LOCK_ALLOC); @@ -286,8 +314,16 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_ if (ensure_space(ctx, size - store->max) == 0) { /* Failed to free any space. */ + /* If we are using the hash table, then we've already + * inserted item - remove it. */ if (use_hash) { + /* If someone else has already picked up a reference + * to item, then we cannot remove it. Leave it in the + * store, and we'll live with being over budget. We + * know this is the case, if it's in the linked list. */ + if (item->next != item) + break; fz_hash_remove_fast(ctx, store->hash, &hash, pos); } fz_unlock(ctx, FZ_LOCK_ALLOC); @@ -302,13 +338,7 @@ fz_store_item(fz_context *ctx, void *key, void *val_, unsigned int itemsize, fz_ store->size += itemsize; /* Regardless of whether it's indexed, it goes into the linked list */ - item->next = store->head; - if (item->next) - item->next->prev = item; - else - store->tail = item; - store->head = item; - item->prev = NULL; + touch(store, item); fz_unlock(ctx, FZ_LOCK_ALLOC); return NULL; @@ -351,31 +381,11 @@ fz_find_item(fz_context *ctx, fz_store_free_fn *free, void *key, fz_store_type * } if (item) { - /* Momentarily things can be in the hash table (and hence can - * be found) without being in the list. Don't attempt to LRU - * these. We indicate such items by setting - * item->next == item. */ - if (item->next != item) - { - /* LRU: Move the block to the front */ - /* Unlink from present position */ - if (item->next) - item->next->prev = item->prev; - else - store->tail = item->prev; - if (item->prev) - item->prev->next = item->next; - else - store->head = item->next; - /* Insert at head */ - item->next = store->head; - if (item->next) - item->next->prev = item; - else - store->tail = item; - item->prev = NULL; - store->head = item; - } + /* LRU the block. This also serves to ensure that any item + * picked up from the hash before it has made it into the + * linked list does not get whipped out again due to the + * store being full. */ + touch(store, item); /* And bump the refcount before returning */ if (item->val->refs > 0) item->val->refs++; @@ -491,15 +501,23 @@ fz_drop_store_context(fz_context *ctx) } #ifndef NDEBUG +static void +print_item(FILE *out, void *item_) +{ + fz_item *item = (fz_item *)item_; + fprintf(out, " val=%p item=%p\n", item->val, item); + fflush(out); +} + void -fz_print_store(fz_context *ctx, FILE *out) +fz_print_store_locked(fz_context *ctx, FILE *out) { fz_item *item, *next; fz_store *store = ctx->store; fprintf(out, "-- resource store contents --\n"); + fflush(out); - fz_lock(ctx, FZ_LOCK_ALLOC); for (item = store->head; item; item = next) { next = item->next; @@ -509,10 +527,22 @@ fz_print_store(fz_context *ctx, FILE *out) fz_unlock(ctx, FZ_LOCK_ALLOC); item->type->debug(out, item->key); fprintf(out, " = %p\n", item->val); + fflush(out); fz_lock(ctx, FZ_LOCK_ALLOC); if (next) next->val->refs--; } + fprintf(out, "-- resource store hash contents --\n"); + fz_print_hash_details(ctx, out, store->hash, print_item); + fprintf(out, "-- end --\n"); + fflush(out); +} + +void +fz_print_store(fz_context *ctx, FILE *out) +{ + fz_lock(ctx, FZ_LOCK_ALLOC); + fz_print_store_locked(ctx, out); fz_unlock(ctx, FZ_LOCK_ALLOC); } #endif @@ -561,7 +591,7 @@ int fz_store_scavenge(fz_context *ctx, unsigned int size, int *phase) #ifdef DEBUG_SCAVENGING printf("Scavenging: store=%d size=%d phase=%d\n", store->size, size, *phase); - fz_print_store(ctx, stderr); + fz_print_store_locked(ctx, stderr); Memento_stats(); #endif do -- cgit v1.2.3