From 193d895da9cf30e1532a7ba2412d312f0ab08449 Mon Sep 17 00:00:00 2001 From: Christian Thaeter Date: Sat, 25 Jul 2009 19:06:39 +0200 Subject: [PATCH] WIP: preparation for the new deadlock checker, structures init/destroy --- src/nobug.h | 72 ++++++++++++++----- src/nobug_resources.c | 190 +++++++++++++++++++++++++++++++------------------- src/nobug_thread.c | 37 +++++++--- 3 files changed, 199 insertions(+), 100 deletions(-) diff --git a/src/nobug.h b/src/nobug.h index ae4aa2d..7387aa8 100644 --- a/src/nobug.h +++ b/src/nobug.h @@ -1973,12 +1973,22 @@ nobug_ringbuffer_pop (struct nobug_ringbuffer* self); /* multithreading extras */ + +#ifndef LLIST_DEFINED +#define LLIST_DEFINED +struct llist_struct +{ + struct llist_struct *next; + struct llist_struct *prev; +}; +#endif + #if NOBUG_USE_PTHREAD struct nobug_tls_data { const char * thread_id; - struct nobug_resource_user* lock_stack; + struct llist_struct res_stack; /* resources of this thread */ }; extern pthread_key_t nobug_tls_key; @@ -1986,6 +1996,12 @@ extern pthread_key_t nobug_tls_key; const char* nobug_thread_id_set (const char* name); +struct nobug_tls_data* +nobug_thread_set (const char* name); + +struct nobug_tls_data* +nobug_thread_get (void); + const char* nobug_thread_id_get (void); @@ -1997,16 +2013,6 @@ extern pthread_mutex_t nobug_resource_mutex; /* resource registry */ - -#ifndef LLIST_DEFINED -#define LLIST_DEFINED -struct llist_struct -{ - struct llist_struct *next; - struct llist_struct *prev; -}; -#endif - #if NOBUG_USE_PTHREAD #define NOBUG_RESOURCE_LOCK pthread_mutex_lock (&nobug_resource_mutex) #define NOBUG_RESOURCE_UNLOCK pthread_mutex_unlock (&nobug_resource_mutex) @@ -2026,16 +2032,19 @@ enum nobug_resource_state NOBUG_RESOURCE_WAITING, NOBUG_RESOURCE_EXCLUSIVE, NOBUG_RESOURCE_RECURSIVE, - NOBUG_RESOURCE_SHARED, + NOBUG_RESOURCE_SHARED }; + struct nobug_resource_header { - struct llist_struct node; /* link node for resource registry, users and pool list */ + struct llist_struct node; /* link node for resource registry or users */ const char* name; /* name */ const char* extra; /* extra information, file/line usually */ }; +struct nobug_resource_node; +struct nobug_resource_user; struct nobug_resource_record { @@ -2044,19 +2053,36 @@ struct nobug_resource_record const void* object_id; /* unique identifer, usually a this pointer or similar */ const char* type; /* type */ - struct nobug_resource_record* prev; /* higher or same precedence resources */ - struct nobug_resource_record* skip; /* higher precedence */ +#if NOBUG_USE_PTHREAD + struct llist_struct nodes; +#endif }; + +struct nobug_resource_node +{ + struct llist_struct node; /* all nodes for one resource */ + + struct nobug_resource_record* resource; /* backpointer */ + struct nobug_resource_node* parent; /* upwards the tree */ + + struct llist_struct childs; /* down the tree, all nodes pointing to here (TODO make this a slist) */ + struct llist_struct cldnode; /* node to accumulate all childrens of a parent (TODO slist) */ +}; + + struct nobug_resource_user { struct nobug_resource_header hdr; + + struct nobug_resource_node* current; /* this resource */ + enum nobug_resource_state state; /* state */ + + #if NOBUG_USE_PTHREAD - const void* thread_id; /* pointer to this theads id */ + struct nobug_tls_data* thread; /* pointer to this theads id */ + struct llist_struct res_stack; /* resources of this thread */ #endif - struct nobug_resource_user* lock_stack; /* locks in use of this thread */ - struct nobug_resource_record* resource; /* associated resource */ - enum nobug_resource_state state; /* state */ }; @@ -2064,6 +2090,14 @@ extern const char* nobug_resource_error; extern const char* nobug_resource_states[]; + +void +nobug_resource_init (void); + +void +nobug_resource_destroy (void); + + struct nobug_resource_record* nobug_resource_announce (const char* type, const char* name, const void* object_id, const char* extra); diff --git a/src/nobug_resources.c b/src/nobug_resources.c index 6275832..a9a4be2 100644 --- a/src/nobug_resources.c +++ b/src/nobug_resources.c @@ -21,6 +21,14 @@ #define NOBUG_LIBNOBUG_C #include "nobug.h" #include "llist.h" +#include "mpool.h" + +/* + How much memory to reserve for a mpool chunk, 16k by default + */ +#ifndef NOBUG_RESOURCE_MPOOL_CHUNKSIZE +#define NOBUG_RESOURCE_MPOOL_CHUNKSIZE (4096<<2) +#endif #if NOBUG_USE_PTHREAD pthread_mutex_t nobug_resource_mutex = PTHREAD_MUTEX_INITIALIZER; @@ -35,16 +43,6 @@ pthread_mutex_t nobug_resource_mutex = PTHREAD_MUTEX_INITIALIZER; #define NOBUG_RESOURCE_UNLOCK #endif -/* how many resource record to allocate at once for the pool, lessen malloc load and improves cache locality */ -#ifndef NOBUG_RESOURCE_CLUSTER -#define NOBUG_RESOURCE_CLUSTER 64 -#endif - -static llist nobug_resource_registry = {&nobug_resource_registry, &nobug_resource_registry}; -static llist nobug_resource_pool = {&nobug_resource_pool, &nobug_resource_pool}; - -const char* nobug_resource_error = NULL; - #define nobug_resourcestates \ resource_state(invalid), \ resource_state(waiting), \ @@ -61,55 +59,98 @@ const char* nobug_resource_states[] = }; #undef resource_state -static int -compare_resource_records (const_LList av, const_LList bv) + +const char* nobug_resource_error = NULL; + +static llist nobug_resource_registry; +static mpool nobug_resource_record_pool; +static mpool nobug_resource_user_pool; +#if NOBUG_USE_PTHREAD +static mpool nobug_resource_node_pool; +#endif + +static void nobug_resource_record_dtor (void*); +static void nobug_resource_user_dtor (void*); +#if NOBUG_USE_PTHREAD +static void nobug_resource_node_dtor (void*); +#endif + + +void +nobug_resource_init (void) { - const struct nobug_resource_record* a = (const struct nobug_resource_record*)av; - const struct nobug_resource_record* b = (const struct nobug_resource_record*)bv; + llist_init (&nobug_resource_registry); + + mpool_init (&nobug_resource_record_pool, + sizeof(struct nobug_resource_record), + NOBUG_RESOURCE_MPOOL_CHUNKSIZE/sizeof(struct nobug_resource_record), + nobug_resource_record_dtor); + + mpool_init (&nobug_resource_user_pool, + sizeof(struct nobug_resource_user), + NOBUG_RESOURCE_MPOOL_CHUNKSIZE/sizeof(struct nobug_resource_user), + nobug_resource_user_dtor); - return a->object_id > b->object_id? 1 : a->object_id < b->object_id ? -1 : 0; +#if NOBUG_USE_PTHREAD + mpool_init (&nobug_resource_node_pool, + sizeof(struct nobug_resource_node), + NOBUG_RESOURCE_MPOOL_CHUNKSIZE/sizeof(struct nobug_resource_node), + nobug_resource_node_dtor); +#endif } + +void +nobug_resource_destroy (void) +{ #if NOBUG_USE_PTHREAD -static const char* -nobug_resource_deadlock_check (struct nobug_resource_user* handle); + mpool_destroy (&nobug_resource_node_pool); #endif + mpool_destroy (&nobug_resource_user_pool); + mpool_destroy (&nobug_resource_record_pool); +} + -struct nobug_resource_cluster +static void +nobug_resource_record_dtor (void* p) { - union { - struct nobug_resource_header hdr; - struct nobug_resource_record record; - struct nobug_resource_user user; - }entry[NOBUG_RESOURCE_CLUSTER]; - llist link; /* yet unused */ -}; - -static struct nobug_resource_header* -nobug_resource_pool_get () + struct nobug_resource_record* r = p; + llist_unlink_fast_ (&r->hdr.node); +} + + +static void +nobug_resource_user_dtor (void* p) { - if (llist_is_empty (&nobug_resource_pool)) - { - struct nobug_resource_cluster* cluster = malloc (sizeof *cluster); - if (!cluster) - { - nobug_resource_error = "malloc failure"; - return NULL; - } - for (int i = 0; i < NOBUG_RESOURCE_CLUSTER; ++i) - { - llist_init (&cluster->entry[i].hdr.node); - llist_insert_tail (&nobug_resource_pool, &cluster->entry[i].hdr.node); - } - } - return (struct nobug_resource_header*) llist_head (&nobug_resource_pool); + struct nobug_resource_user* u = p; + llist_unlink_fast_ (&u->hdr.node); +#if NOBUG_USE_PTHREAD + llist_unlink_fast_ (&u->res_stack); +#endif } +#if NOBUG_USE_PTHREAD static void -nobug_resource_pool_push (struct nobug_resource_header* self) +nobug_resource_node_dtor (void* p) { - llist_insert_tail (&nobug_resource_pool, &self->node); + struct nobug_resource_node* n = p; + llist_unlink_fast_ (&n->node); + /* must unlink childs, because we don't destroy the tree bottom up */ + llist_unlink_fast_ (&n->childs); + llist_unlink_fast_ (&n->cldnode); +} +#endif + + +static int +compare_resource_records (const_LList av, const_LList bv, void* unused) +{ + (void) unused; + const struct nobug_resource_record* a = (const struct nobug_resource_record*)av; + const struct nobug_resource_record* b = (const struct nobug_resource_record*)bv; + + return a->object_id > b->object_id ? 1 : a->object_id < b->object_id ? -1 : 0; } @@ -118,15 +159,19 @@ nobug_resource_announce (const char* type, const char* name, const void* object_ { NOBUG_RESOURCE_LOCK; - struct nobug_resource_record* node = (struct nobug_resource_record*)nobug_resource_pool_get (); + struct nobug_resource_record* node = mpool_alloc (&nobug_resource_record_pool); if (!node) - return NULL; + { + nobug_resource_error = "internal allocation error"; + return NULL; + } node->hdr.name = name; node->object_id = object_id; node->type = type; - if (llist_find (&nobug_resource_registry, &node->hdr.node, compare_resource_records)) + /* TODO better lookup method than list search (psplay?) */ + if (llist_ufind (&nobug_resource_registry, &node->hdr.node, compare_resource_records, NULL)) { nobug_resource_error = "already registered"; return NULL; @@ -134,46 +179,51 @@ nobug_resource_announce (const char* type, const char* name, const void* object_ llist_init (&node->users); node->hdr.extra = extra; - node->prev = node; /* pointer to self is used to indicate uninitialized parent, NULL means no parent */ - node->skip = node; /* pointer to self is used to indicate uninitialized parent, NULL means no parent */ +#if NOBUG_USE_PTHREAD + llist_init (&node->nodes); +#endif - llist_insert_tail (&nobug_resource_registry, &node->hdr.node); + llist_insert_head (&nobug_resource_registry, llist_init (&node->hdr.node)); NOBUG_RESOURCE_UNLOCK; return node; } +#if NOBUG_USE_PTHREAD +static void +nobug_resource_node_free (struct nobug_resource_node* self) +{ + LLIST_WHILE_HEAD (&self->childs, c) + nobug_resource_node_free (LLIST_TO_STRUCTP(c, struct nobug_resource_node, cldnode)); + + /* one of the childs was in use (should never happen) */ + if (nobug_resource_error) + return; + + llist_unlink_fast_ (&self->cldnode); + llist_unlink_fast_ (&self->node); + mpool_free (&nobug_resource_node_pool, self); +} +#endif + + int nobug_resource_forget (struct nobug_resource_record* self) { NOBUG_RESOURCE_LOCK; - if (!llist_find (&nobug_resource_registry, &self->hdr.node, compare_resource_records)) + if (!llist_find (&nobug_resource_registry, &self->hdr.node, compare_resource_records, NULL)) { nobug_resource_error = "not registered"; return 0; } - if (!llist_is_empty (&self->users)) - { - nobug_resource_error = "still in use"; - return 0; - } - -#if 0 /* NOBUG_USE_PTHREAD Deadlock detector disabled */ - if (self->link != self) - { - /* remove resource from lock-precedence stack */ - LLIST_FOREACH (&nobug_resource_registry, n) - { - struct nobug_resource_record* node = (struct nobug_resource_record*)n; - if(node->link == self) - node->link = self->link; - } - } +#if NOBUG_USE_PTHREAD + LLIST_WHILE_HEAD (&self->nodes, n) + nobug_resource_node_free ((struct nobug_resource_node*)n); #endif - nobug_resource_pool_push (&self->hdr); + mpool_free (&nobug_resource_record_pool, self); NOBUG_RESOURCE_UNLOCK; return 1; } diff --git a/src/nobug_thread.c b/src/nobug_thread.c index 4412831..1713e59 100644 --- a/src/nobug_thread.c +++ b/src/nobug_thread.c @@ -18,6 +18,7 @@ */ #define NOBUG_LIBNOBUG_C #include "nobug.h" +#include "llist.h" pthread_mutex_t nobug_logging_mutex = PTHREAD_MUTEX_INITIALIZER; @@ -26,12 +27,12 @@ pthread_mutex_t nobug_logging_mutex = PTHREAD_MUTEX_INITIALIZER; thread id handling */ pthread_key_t nobug_tls_key; +static unsigned nobug_thread_cnt = 0; -const char* -nobug_thread_id_set (const char* name) -{ - static unsigned nobug_thread_cnt = 0; +struct nobug_tls_data* +nobug_thread_set (const char* name) +{ char buf[256]; snprintf (buf, 256, "%s_%d", name, ++nobug_thread_cnt); struct nobug_tls_data * tls = pthread_getspecific (nobug_tls_key); @@ -41,7 +42,7 @@ nobug_thread_id_set (const char* name) if (!tls) abort(); tls->thread_id = strdup(buf); if (!tls->thread_id) abort(); - tls->lock_stack = NULL; + llist_init (&tls->res_stack); pthread_setspecific (nobug_tls_key, tls); } else @@ -50,19 +51,33 @@ nobug_thread_id_set (const char* name) free ((char*)tls->thread_id); tls->thread_id = strdup(buf); if (!tls->thread_id) abort(); - tls->lock_stack = NULL; + llist_init (&tls->res_stack); } - return tls->thread_id; + return tls; } -const char* -nobug_thread_id_get (void) + +struct nobug_tls_data* +nobug_thread_get (void) { struct nobug_tls_data* tls = pthread_getspecific (nobug_tls_key); if (!tls) - return nobug_thread_id_set ("thread"); + return nobug_thread_set ("thread"); + + return tls; +} - return tls->thread_id; + +const char* +nobug_thread_id_set (const char* name) +{ + return nobug_thread_set (name) -> thread_id; } + +const char* +nobug_thread_id_get (void) +{ + return nobug_thread_get () -> thread_id; +} -- 2.11.4.GIT