The comment against the 'updateMutex' refers to a problem with lock ordering when looking up filters in the virNWFilterObjList which uses an array. That problem does indeed exist. Unfortunately it claims that switching to a hash table would solve the lock ordering problems during instantiation. That is not correct because there is a second lock ordering problem related to how we traverse related filters when instantiating filters. Consider a set of filters: Filter A: Reference Filter C Reference Filter D Filter B: Reference Filter D Reference Filter C In one example, we lock A, C, D, in the other example we lock A, D, C. Signed-off-by: Daniel P. Berrangé <berrange@redhat.com> --- src/nwfilter/nwfilter_gentech_driver.c | 57 ++++++++++++++++++++------ 1 file changed, 45 insertions(+), 12 deletions(-) diff --git a/src/nwfilter/nwfilter_gentech_driver.c b/src/nwfilter/nwfilter_gentech_driver.c index 7bbf1e12fb..9f4a755252 100644 --- a/src/nwfilter/nwfilter_gentech_driver.c +++ b/src/nwfilter/nwfilter_gentech_driver.c @@ -55,19 +55,52 @@ static virNWFilterTechDriver *filter_tech_drivers[] = { NULL }; -/* Serializes instantiation of filters. This is necessary - * to avoid lock ordering deadlocks. eg virNWFilterInstantiateFilterUpdate - * will hold a lock on a virNWFilterObj *. This in turn invokes - * virNWFilterDoInstantiate which invokes virNWFilterDetermineMissingVarsRec - * which invokes virNWFilterObjListFindInstantiateFilter. This iterates over - * every single virNWFilterObj *in the list. So if 2 threads try to - * instantiate a filter in parallel, they'll both hold 1 lock at the top level - * in virNWFilterInstantiateFilterUpdate which will cause the other thread - * to deadlock in virNWFilterObjListFindInstantiateFilter. +/* + * Serializes instantiation of filters. + * + * When instantiating a filter, we need to resolve references + * to other filters and acquire locks on them. The act of + * looking up a filter requires traversing an array, locking + * each filter in turn until we find the one we want. + * + * The mere act of finding a filter by name, while holding + * a lock on another filter, introduces deadlocks due to + * varying lock ordering. + * + * We retain a lock on the referenced filter once found. + * The order in which the locks are acquired depends on + * the order in which filters reference each other. + * + * Filter A: + * Reference Filter C + * Reference Filter D + * + * Filter B: + * Reference Filter D + * Reference Filter C + * + * In one example, we lock A, C, D, in the other example + * we lock A, D, C. + * + * Because C & D are locked in differing orders we are + * once again at risk of deadlocks. + * + * There can be multiple levels of recursion, so it is + * not viable to determine the lock order upfront, it + * has to be done as we traverse the tree. + * + * Thus we serialize any code that needs to traverse + * the filter references. + * + * This covers the following APIs: + * + * virNWFilterDefineXML + * virNWFilterUndefine + * virNWFilterBindingCreate + * virNWFilterBindingDelete * - * XXX better long term solution is to make virNWFilterObjList use a - * hash table as is done for virDomainObjList. You can then get - * lockless lookup of objects by name. + * In addition to the asynchronous filter instantiation + * triggered by the IP address learning backends. */ static virMutex updateMutex; -- 2.35.1

The current use of an array for nwfilter objects requires the caller to iterate over all elements to find a filter, and also requires locking each filter. Switching to a pair of hash tables enables O(1) lookups both by name and uuid, with no locking required. Signed-off-by: Daniel P. Berrangé <berrange@redhat.com> --- src/conf/virnwfilterobj.c | 264 +++++++++++++++++-------- src/nwfilter/nwfilter_gentech_driver.c | 8 +- 2 files changed, 179 insertions(+), 93 deletions(-) diff --git a/src/conf/virnwfilterobj.c b/src/conf/virnwfilterobj.c index 6bbdf6e6fa..808283e4ed 100644 --- a/src/conf/virnwfilterobj.c +++ b/src/conf/virnwfilterobj.c @@ -43,10 +43,14 @@ struct _virNWFilterObj { }; struct _virNWFilterObjList { - size_t count; - virNWFilterObj **objs; -}; + /* uuid string -> virNWFilterObj mapping + * for O(1), lookup-by-uuid */ + GHashTable *objs; + /* name -> virNWFilterObj mapping for O(1), + * lookup-by-name */ + GHashTable *objsName; +}; static virNWFilterObj * virNWFilterObjNew(void) @@ -106,10 +110,8 @@ virNWFilterObjFree(virNWFilterObj *obj) void virNWFilterObjListFree(virNWFilterObjList *nwfilters) { - size_t i; - for (i = 0; i < nwfilters->count; i++) - virNWFilterObjFree(nwfilters->objs[i]); - g_free(nwfilters->objs); + g_hash_table_unref(nwfilters->objs); + g_hash_table_unref(nwfilters->objsName); g_free(nwfilters); } @@ -117,7 +119,17 @@ virNWFilterObjListFree(virNWFilterObjList *nwfilters) virNWFilterObjList * virNWFilterObjListNew(void) { - return g_new0(virNWFilterObjList, 1); + virNWFilterObjList *nwfilters = g_new0(virNWFilterObjList, 1); + + /* virNWFilterObj is not ref counted, so we rely fact that + * an instance will always exist in both hash tables, or + * neither hash table. Thus we only need to have a destroy + * callback for one of the two hash tables. + */ + nwfilters->objs = virHashNew((GDestroyNotify)virNWFilterObjFree); + nwfilters->objsName = virHashNew(NULL); + + return nwfilters; } @@ -125,21 +137,14 @@ void virNWFilterObjListRemove(virNWFilterObjList *nwfilters, virNWFilterObj *obj) { - size_t i; + char uuidstr[VIR_UUID_STRING_BUFLEN]; - virNWFilterObjUnlock(obj); + virUUIDFormat(obj->def->uuid, uuidstr); - for (i = 0; i < nwfilters->count; i++) { - virNWFilterObjLock(nwfilters->objs[i]); - if (nwfilters->objs[i] == obj) { - virNWFilterObjUnlock(nwfilters->objs[i]); - virNWFilterObjFree(nwfilters->objs[i]); + virNWFilterObjUnlock(obj); - VIR_DELETE_ELEMENT(nwfilters->objs, i, nwfilters->count); - break; - } - virNWFilterObjUnlock(nwfilters->objs[i]); - } + g_hash_table_remove(nwfilters->objsName, obj->def->name); + g_hash_table_remove(nwfilters->objs, uuidstr); } @@ -147,20 +152,16 @@ virNWFilterObj * virNWFilterObjListFindByUUID(virNWFilterObjList *nwfilters, const unsigned char *uuid) { - size_t i; + char uuidstr[VIR_UUID_STRING_BUFLEN]; virNWFilterObj *obj; - virNWFilterDef *def; - for (i = 0; i < nwfilters->count; i++) { - obj = nwfilters->objs[i]; + virUUIDFormat(uuid, uuidstr); + + obj = g_hash_table_lookup(nwfilters->objs, uuidstr); + if (obj) virNWFilterObjLock(obj); - def = obj->def; - if (!memcmp(def->uuid, uuid, VIR_UUID_BUFLEN)) - return obj; - virNWFilterObjUnlock(obj); - } - return NULL; + return obj; } @@ -168,20 +169,13 @@ virNWFilterObj * virNWFilterObjListFindByName(virNWFilterObjList *nwfilters, const char *name) { - size_t i; virNWFilterObj *obj; - virNWFilterDef *def; - for (i = 0; i < nwfilters->count; i++) { - obj = nwfilters->objs[i]; + obj = g_hash_table_lookup(nwfilters->objsName, name); + if (obj) virNWFilterObjLock(obj); - def = obj->def; - if (STREQ_NULLABLE(def->name, name)) - return obj; - virNWFilterObjUnlock(obj); - } - return NULL; + return obj; } @@ -308,6 +302,7 @@ virNWFilterObjListAssignDef(virNWFilterObjList *nwfilters, { virNWFilterObj *obj; virNWFilterDef *objdef; + char uuidstr[VIR_UUID_STRING_BUFLEN]; if ((obj = virNWFilterObjListFindByUUID(nwfilters, def->uuid))) { objdef = obj->def; @@ -323,8 +318,6 @@ virNWFilterObjListAssignDef(virNWFilterObjList *nwfilters, virNWFilterObjUnlock(obj); } else { if ((obj = virNWFilterObjListFindByName(nwfilters, def->name))) { - char uuidstr[VIR_UUID_STRING_BUFLEN]; - objdef = obj->def; virUUIDFormat(objdef->uuid, uuidstr); virReportError(VIR_ERR_OPERATION_FAILED, @@ -368,7 +361,10 @@ virNWFilterObjListAssignDef(virNWFilterObjList *nwfilters, if (!(obj = virNWFilterObjNew())) return NULL; - VIR_APPEND_ELEMENT_COPY(nwfilters->objs, nwfilters->count, obj); + virUUIDFormat(def->uuid, uuidstr); + + g_hash_table_insert(nwfilters->objs, g_strdup(uuidstr), obj); + g_hash_table_insert(nwfilters->objsName, g_strdup(def->name), obj); obj->def = def; @@ -376,26 +372,69 @@ virNWFilterObjListAssignDef(virNWFilterObjList *nwfilters, } +struct virNWFilterObjListData { + virNWFilterObjListFilter filter; + virConnectPtr conn; + int count; +}; + + +static void +virNWFilterObjListCount(void *payload, + void *key G_GNUC_UNUSED, + void *opaque) +{ + virNWFilterObj *obj = payload; + struct virNWFilterObjListData *data = opaque; + g_auto(virLockGuard) lock = virObjectLockGuard(obj); + + if (data->filter(data->conn, obj->def)) + data->count++; +} + + int virNWFilterObjListNumOfNWFilters(virNWFilterObjList *nwfilters, virConnectPtr conn, virNWFilterObjListFilter filter) { - size_t i; - int nfilters = 0; - - for (i = 0; i < nwfilters->count; i++) { - virNWFilterObj *obj = nwfilters->objs[i]; - virNWFilterObjLock(obj); - if (!filter || filter(conn, obj->def)) - nfilters++; - virNWFilterObjUnlock(obj); - } + struct virNWFilterObjListData data = { filter, conn, 0 }; - return nfilters; + g_hash_table_foreach(nwfilters->objs, + virNWFilterObjListCount, + &data); + return data.count; } +struct virNWFilterNameData { + virNWFilterObjListFilter filter; + virConnectPtr conn; + int numnames; + int maxnames; + char **const names; +}; + + +static void +virNWFilterObjListCopyNames(void *payload, + void *key G_GNUC_UNUSED, + void *opaque) +{ + virNWFilterObj *obj = payload; + struct virNWFilterNameData *data = opaque; + g_auto(virLockGuard) lock = virObjectLockGuard(obj); + + if (data->filter && + !data->filter(data->conn, obj->def)) + return; + + if (data->numnames < data->maxnames) { + data->names[data->numnames] = g_strdup(obj->def->name); + data->numnames++; + } +} + int virNWFilterObjListGetNames(virNWFilterObjList *nwfilters, virConnectPtr conn, @@ -403,22 +442,80 @@ virNWFilterObjListGetNames(virNWFilterObjList *nwfilters, char **const names, int maxnames) { - int nnames = 0; - size_t i; - virNWFilterDef *def; + struct virNWFilterNameData data = + { filter, conn, 0, maxnames, names }; - for (i = 0; i < nwfilters->count && nnames < maxnames; i++) { - virNWFilterObj *obj = nwfilters->objs[i]; - virNWFilterObjLock(obj); - def = obj->def; - if (!filter || filter(conn, def)) { - names[nnames] = g_strdup(def->name); - nnames++; + g_hash_table_foreach(nwfilters->objs, + virNWFilterObjListCopyNames, + &data); + + return data.numnames; +} + + +struct virNWFilterListData { + virNWFilterObj **filters; + size_t nfilters; +}; + + +static void +virNWFilterObjListCollectIterator(void *payload, + void *key G_GNUC_UNUSED, + void *opaque) +{ + struct virNWFilterListData *data = opaque; + virNWFilterObj *obj = payload; + + virNWFilterObjLock(obj); + data->filters[data->nfilters++] = payload; +} + + +static void +virNWFilterObjListFilterApply(virNWFilterObj ***list, + size_t *nfilters, + virConnectPtr conn, + virNWFilterObjListFilter filter) +{ + size_t i = 0; + + while (i < *nfilters) { + virNWFilterObj *obj = (*list)[i]; + + if (filter && !filter(conn, obj->def)) { + VIR_DELETE_ELEMENT(*list, i, *nfilters); + virNWFilterObjUnlock(obj); + continue; } - virNWFilterObjUnlock(obj); + + i++; } +} + + +static int +virNWFilterObjListCollect(virNWFilterObjList *nwfilters, + virConnectPtr conn, + virNWFilterObj ***filters, + size_t *nfilters, + virNWFilterObjListFilter filter) +{ + struct virNWFilterListData data = { NULL, 0 }; + + data.filters = g_new0(virNWFilterObj *, + g_hash_table_size(nwfilters->objs)); + + g_hash_table_foreach(nwfilters->objs, + virNWFilterObjListCollectIterator, + &data); - return nnames; + virNWFilterObjListFilterApply(&data.filters, &data.nfilters, conn, filter); + + *nfilters = data.nfilters; + *filters = data.filters; + + return 0; } @@ -429,32 +526,26 @@ virNWFilterObjListExport(virConnectPtr conn, virNWFilterObjListFilter filter) { virNWFilterPtr *tmp_filters = NULL; - int nfilters = 0; - virNWFilterPtr nwfilter = NULL; - virNWFilterObj *obj = NULL; - virNWFilterDef *def; + virNWFilterObj **objs = NULL; + size_t nfilters = 0; size_t i; int ret = -1; + if (virNWFilterObjListCollect(nwfilters, conn, &objs, &nfilters, filter) < 0) + return -1; + if (!filters) { - ret = nwfilters->count; + ret = nfilters; goto cleanup; } - tmp_filters = g_new0(virNWFilterPtr, nwfilters->count + 1); + tmp_filters = g_new0(virNWFilterPtr, nfilters + 1); - for (i = 0; i < nwfilters->count; i++) { - obj = nwfilters->objs[i]; - virNWFilterObjLock(obj); - def = obj->def; - if (!filter || filter(conn, def)) { - if (!(nwfilter = virGetNWFilter(conn, def->name, def->uuid))) { - virNWFilterObjUnlock(obj); - goto cleanup; - } - tmp_filters[nfilters++] = nwfilter; - } - virNWFilterObjUnlock(obj); + for (i = 0; i < nfilters; i++) { + tmp_filters[i] = virGetNWFilter(conn, objs[i]->def->name, objs[i]->def->uuid); + + if (!tmp_filters[i]) + goto cleanup; } *filters = g_steal_pointer(&tmp_filters); @@ -462,11 +553,12 @@ virNWFilterObjListExport(virConnectPtr conn, cleanup: if (tmp_filters) { - for (i = 0; i < nfilters; i ++) + for (i = 0; i < nfilters; i++) virObjectUnref(tmp_filters[i]); } VIR_FREE(tmp_filters); - + for (i = 0; i < nfilters; i++) + virNWFilterObjUnlock(objs[i]); return ret; } diff --git a/src/nwfilter/nwfilter_gentech_driver.c b/src/nwfilter/nwfilter_gentech_driver.c index 9f4a755252..c609405ac0 100644 --- a/src/nwfilter/nwfilter_gentech_driver.c +++ b/src/nwfilter/nwfilter_gentech_driver.c @@ -59,13 +59,7 @@ static virNWFilterTechDriver *filter_tech_drivers[] = { * Serializes instantiation of filters. * * When instantiating a filter, we need to resolve references - * to other filters and acquire locks on them. The act of - * looking up a filter requires traversing an array, locking - * each filter in turn until we find the one we want. - * - * The mere act of finding a filter by name, while holding - * a lock on another filter, introduces deadlocks due to - * varying lock ordering. + * to other filters and acquire locks on them. * * We retain a lock on the referenced filter once found. * The order in which the locks are acquired depends on -- 2.35.1