[libvirt PATCH 2/2] conf: use a hash table for storing nwfilter object list
Daniel P. Berrangé
berrange at redhat.com
Thu Mar 10 10:10:04 UTC 2022
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 at 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
More information about the libvir-list
mailing list