[ovs-dev] [PATCH 3/5] ovsdb-idl: IDL Compound Indexes Implementation
Rodriguez Betancourt, Esteban
estebarb at hpe.com
Wed Mar 9 00:03:54 UTC 2016
In the C IDL, allows to create multicolumn indexes in the
tables, that are keep synched with the data in the replica.
Signed-off-by: Esteban Rodriguez Betancourt <estebarb at hpe.com>
---
lib/ovsdb-idl-provider.h | 3 +
lib/ovsdb-idl.c | 378 +++++++++++++++++++++++++++++++++++++++++++++++
lib/ovsdb-idl.h | 63 ++++++++
3 files changed, 444 insertions(+)
diff --git a/lib/ovsdb-idl-provider.h b/lib/ovsdb-idl-provider.h
index 190acca..423217e 100644
--- a/lib/ovsdb-idl-provider.h
+++ b/lib/ovsdb-idl-provider.h
@@ -1,4 +1,5 @@
/* Copyright (c) 2009, 2010, 2011, 2012 Nicira, Inc.
+ * Copyright (C) 2016 Hewlett Packard Enterprise Development LP
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -49,6 +50,7 @@ struct ovsdb_idl_column {
bool mutable;
void (*parse)(struct ovsdb_idl_row *, const struct ovsdb_datum *);
void (*unparse)(struct ovsdb_idl_row *);
+ int (*compare)(const void *, const void *); /* Perform a comparison over ovsrec_* */
};
struct ovsdb_idl_table_class {
@@ -69,6 +71,7 @@ struct ovsdb_idl_table {
struct hmap rows; /* Contains "struct ovsdb_idl_row"s. */
struct ovsdb_idl *idl; /* Containing idl. */
unsigned int change_seqno[OVSDB_IDL_CHANGE_MAX];
+ struct shash indexes; /* Contains "struct ovsdb_idl_index"s */
struct ovs_list track_list; /* Tracked rows (ovsdb_idl_row.track_node). */
};
diff --git a/lib/ovsdb-idl.c b/lib/ovsdb-idl.c
index 4cb1c81..24920a0 100644
--- a/lib/ovsdb-idl.c
+++ b/lib/ovsdb-idl.c
@@ -1,4 +1,5 @@
/* Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016 Nicira, Inc.
+ * Copyright (C) 2016 Hewlett Packard Enterprise Development LP
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -36,8 +37,10 @@
#include "ovsdb-parser.h"
#include "poll-loop.h"
#include "shash.h"
+#include "skiplist.h"
#include "sset.h"
#include "util.h"
+#include "uuid.h"
#include "openvswitch/vlog.h"
VLOG_DEFINE_THIS_MODULE(ovsdb_idl);
@@ -203,6 +206,15 @@ ovsdb_idl_table_from_class(const struct ovsdb_idl *,
const struct ovsdb_idl_table_class *);
static bool ovsdb_idl_track_is_set(struct ovsdb_idl_table *table);
+static int
+ovsdb_idl_index_generic_comparer(const void *, const void *, const void *);
+static struct ovsdb_idl_index *
+ovsdb_idl_create_index_(const struct ovsdb_idl_table *table);
+static void
+ovsdb_idl_destroy_indexes(struct ovsdb_idl_table *table);
+static void ovsdb_idl_add_to_indexes(const struct ovsdb_idl_row *);
+static void ovsdb_idl_remove_from_indexes(const struct ovsdb_idl_row *);
+
/* Creates and returns a connection to database 'remote', which should be in a
* form acceptable to jsonrpc_session_open(). The connection will maintain an
* in-memory replica of the remote database whose schema is described by
@@ -249,6 +261,7 @@ ovsdb_idl_create(const char *remote, const struct ovsdb_idl_class *class,
memset(table->modes, default_mode, tc->n_columns);
table->need_table = false;
shash_init(&table->columns);
+ shash_init(&table->indexes);
for (j = 0; j < tc->n_columns; j++) {
const struct ovsdb_idl_column *column = &tc->columns[j];
@@ -284,6 +297,7 @@ ovsdb_idl_destroy(struct ovsdb_idl *idl)
for (i = 0; i < idl->class->n_tables; i++) {
struct ovsdb_idl_table *table = &idl->tables[i];
+ ovsdb_idl_destroy_indexes(table);
shash_destroy(&table->columns);
hmap_destroy(&table->rows);
free(table->modes);
@@ -318,6 +332,7 @@ ovsdb_idl_clear(struct ovsdb_idl *idl)
struct ovsdb_idl_arc *arc, *next_arc;
if (!ovsdb_idl_row_is_orphan(row)) {
+ ovsdb_idl_remove_from_indexes(row);
ovsdb_idl_row_unparse(row);
}
LIST_FOR_EACH_SAFE (arc, next_arc, src_node, &row->src_arcs) {
@@ -1454,6 +1469,364 @@ ovsdb_idl_row_unparse(struct ovsdb_idl_row *row)
}
}
+/*
+ * Creates a new index, that is attached to the given idl and table.
+ * The index has the given name.
+ * All the indexes must be created before the first ovsdb_idl_run is
+ * executed.
+ */
+struct ovsdb_idl_index *
+ovsdb_idl_create_index(struct ovsdb_idl *idl,
+ const struct ovsdb_idl_table_class *tc,
+ const char *index_name)
+{
+ size_t i;
+ struct ovsdb_idl_index *index;
+ for(i = 0; i < idl->class->n_tables; i++){
+ struct ovsdb_idl_table *table = &idl->tables[i];
+
+ if (table->class == tc) {
+ index = ovsdb_idl_create_index_(table);
+ if(!shash_add_once(&table->indexes,
+ index_name,
+ index)){
+ VLOG_ERR("Can't repeat index name '%s' at table %s",
+ index_name, table->class->name);
+ return NULL;
+ }
+ index->index_name = index_name;
+ return index;
+ }
+ }
+ OVS_NOT_REACHED();
+ return NULL;
+}
+
+static struct ovsdb_idl_index *
+ovsdb_idl_create_index_(const struct ovsdb_idl_table *table)
+{
+ struct ovsdb_idl_index *index;
+ size_t max_columns = table->class->n_columns;
+ index = malloc(sizeof(struct ovsdb_idl_index));
+ index->n_columns = 0;
+ index->alloc_columns = max_columns;
+ index->skiplist = skiplist_create(64, ovsdb_idl_index_generic_comparer,
+ index);
+ index->columns = malloc(max_columns * sizeof(struct ovsdb_idl_column *));
+ index->comparers = malloc(max_columns * sizeof(skiplist_comparator));
+ index->sorting_order = malloc(max_columns * sizeof(int));
+ index->row_sync = false;
+ index->table = table;
+ return index;
+}
+
+static void
+ovsdb_idl_destroy_indexes(struct ovsdb_idl_table *table)
+{
+ struct shash_node *node;
+ struct ovsdb_idl_index *index;
+ SHASH_FOR_EACH(node, &(table->indexes)){
+ index = (struct ovsdb_idl_index *)node->data;
+ skiplist_destroy(index->skiplist);
+ free(index->columns);
+ free(index->comparers);
+ free(index->sorting_order);
+ }
+}
+
+static void
+ovsdb_idl_add_to_indexes(const struct ovsdb_idl_row *row)
+{
+ struct ovsdb_idl_table *table = row->table;
+ struct ovsdb_idl_index *index;
+ struct shash_node *node;
+ SHASH_FOR_EACH(node, &(table->indexes)) {
+ index = (struct ovsdb_idl_index*) node->data;
+ index->row_sync = true;
+ skiplist_insert(index->skiplist, row);
+ index->row_sync = false;
+ }
+}
+
+static void
+ovsdb_idl_remove_from_indexes(const struct ovsdb_idl_row *row)
+{
+ struct ovsdb_idl_table *table = row->table;
+ struct ovsdb_idl_index *index;
+ struct shash_node *node;
+ SHASH_FOR_EACH(node, &(table->indexes)) {
+ index = (struct ovsdb_idl_index*) node->data;
+ index->row_sync = true;
+ skiplist_delete(index->skiplist, row);
+ index->row_sync = false;
+ }
+}
+
+/*
+ * Generic string comparer
+ */
+int
+ovsdb_idl_index_strcmp(char *data1, char *data2) {
+ return strcmp(data1, data2);
+}
+
+/*
+ * Generic int64_t comparer
+ */
+int
+ovsdb_idl_index_intcmp(int64_t a, int64_t b) {
+ return (a > b) - (a < b);
+}
+
+/*
+ * Generic float comparer
+ */
+int
+ovsdb_idl_index_doublecmp(double a, double b) {
+ return (a > b) - (a < b);
+}
+/*
+ * Adds a column to an existing index (all columns must be inserted before
+ * the first ovsdb_idl_run is executed).
+ * In "order", accepts the values OVSDB_INDEX_ASC or OVSDB_INDEX_DESC
+ * (OVSDB_INDEX_ASC by default).
+ * In "custom_comparer" it accepts a custom comparison function. If given NULL
+ * it will use the default comparator for the column (only available for
+ * string, numeric or real columns).
+ */
+void
+ovsdb_idl_index_add_column(struct ovsdb_idl_index *index,
+ const struct ovsdb_idl_column *column,
+ int order,
+ column_comparator custom_comparer
+ )
+{
+ /* Check that the column or table is tracked */
+ if(!index->table->need_table &&
+ !((OVSDB_IDL_MONITOR | OVSDB_IDL_ALERT) &
+ *ovsdb_idl_get_mode(index->table->idl, column))){
+ VLOG_ERR("Can't add column '%s' at index '%s' in "
+ "table '%s'. Column isn't monitored.",
+ column->name,
+ index->index_name,
+ index->table->class->name);
+ }
+
+ /* Allocate more memory for column configuration */
+ if(index->n_columns == index->alloc_columns){
+ index->alloc_columns++;
+ const struct ovsdb_idl_column **tmp_cols = malloc(index->alloc_columns);
+ column_comparator *tmp_cmps = malloc(index->alloc_columns);
+ int *tmp_order = malloc(index->alloc_columns);
+
+ memcpy(tmp_cols, index->columns,
+ index->n_columns * sizeof(struct ovsdb_idl_column *));
+ memcpy(tmp_cmps, index->comparers,
+ index->n_columns * sizeof(column_comparator));
+ memcpy(tmp_order, index->sorting_order,
+ index->n_columns * sizeof(int));
+
+ free(index->columns);
+ free(index->comparers);
+ free(index->sorting_order);
+
+ index->columns = tmp_cols;
+ index->comparers = tmp_cmps;
+ index->sorting_order = tmp_order;
+ }
+
+ /* Append column to index */
+ int i = index->n_columns;
+ index->columns[i] = column;
+ if(custom_comparer || column->compare) {
+ index->comparers[i] = custom_comparer ? custom_comparer :
+ (column_comparator) column->compare;
+ } else {
+ VLOG_ERR("Column %s doesn't have default comparator, and"
+ "no custom comparator was given.", column->name);
+ }
+ if(order == OVSDB_INDEX_ASC) {
+ index->sorting_order[i] = OVSDB_INDEX_ASC;
+ } else {
+ index->sorting_order[i] = OVSDB_INDEX_DESC;
+ }
+ index->n_columns++;
+}
+
+/*
+ * Initializes a index cursor
+ */
+bool
+ovsdb_idl_initialize_cursor(struct ovsdb_idl *idl,
+ const struct ovsdb_idl_table_class *tc,
+ const char *index_name,
+ struct ovsdb_idl_index_cursor *cursor)
+{
+ size_t i;
+ for(i = 0; i < idl->class->n_tables; i++){
+ struct ovsdb_idl_table *table = &idl->tables[i];
+
+ if (table->class == tc) {
+ cursor->index = (struct ovsdb_idl_index *) shash_find(
+ &table->indexes,
+ index_name)->data;
+ if(!cursor->index) {
+ VLOG_ERR("Cursor initialization fails. "
+ "Index %s at table %s doesn't exist.",
+ index_name,
+ tc->name);
+ cursor->index = NULL;
+ cursor->position = NULL;
+ return false;
+ }
+ cursor->position = skiplist_first(cursor->index->skiplist);
+ return true;
+ }
+ }
+ VLOG_ERR("Cursor initialization fails. "
+ "Index %s at table %s doesn't exist.",
+ index_name,
+ tc->name);
+ return false;
+}
+
+/*
+ * Generic comparator that can compare each index, using the custom
+ * configuration (an struct ovsdb_idl_index) passed to it.
+ * Not intended for direct usage.
+ */
+static int
+ovsdb_idl_index_generic_comparer(const void *a,
+ const void *b,
+ const void *conf)
+{
+ size_t i;
+ const struct ovsdb_idl_index *index = (const struct ovsdb_idl_index *)conf;
+
+ for(i = 0; i < index->n_columns; i++){
+ int val = index->comparers[i](a, b);
+ if(val){
+ return val * index->sorting_order[i];
+ }
+ }
+
+ /*
+ * If row_sync is true then the IDL is synchronization the replica's
+ * rows with the ones stored in the index. In this case is necessary
+ * to compare also by pointer value (eg: so the correct row is removed).
+ * In any other case (the user is doing a search) the values are
+ * already equal, so return 0.
+ * Also, the pointers obviously are random, so in different IDLs of the
+ * same OVSDB instance the index could have different ordering.
+ * Comparing first by UUID can guarantee the same order at any IDL.
+ */
+ if(index->row_sync){
+ const struct ovsdb_idl_row *row_a, *row_b;
+ row_a = (const struct ovsdb_idl_row *)a;
+ row_b = (const struct ovsdb_idl_row *)b;
+ int value = uuid_compare_3way(&row_a->uuid, &row_b->uuid);
+ return value ? value : (a < b) - (a > b);
+ } else {
+ return 0;
+ }
+}
+
+/*
+ * Moves the cursor to the first entry in the index.
+ * Returns a pointer to the corresponding ovsdb_idl_row, or NULL.
+ */
+struct ovsdb_idl_row *
+ovsdb_idl_index_first(struct ovsdb_idl_index_cursor *cursor)
+{
+ cursor->position = skiplist_first(cursor->index->skiplist);
+ return ovsdb_idl_index_data(cursor);
+}
+
+/*
+ * Moves the cursor to the following record in the index.
+ */
+struct ovsdb_idl_row *
+ovsdb_idl_index_next(struct ovsdb_idl_index_cursor *cursor)
+{
+ if(!cursor->position){
+ return NULL;
+ }
+ cursor->position = skiplist_next(cursor->position);
+ return ovsdb_idl_index_data(cursor);
+}
+
+/*
+ * Returns the ovsdb_idl_row pointer corresponding to the current record
+ */
+struct ovsdb_idl_row *
+ovsdb_idl_index_data(struct ovsdb_idl_index_cursor *cursor)
+{
+ return (struct ovsdb_idl_row *)skiplist_get_data(cursor->position);
+}
+
+/*
+ * Moves the cursor to the first entry with a value equal to the given value.
+ * If the value given is NULL then the function will behave like
+ * ovsdb_idl_index_first.
+ * Returns a pointer to the corresponding ovsdb_idl_row (that can be casted
+ * to a ovsrec) or NULL.
+ */
+struct ovsdb_idl_row *
+ovsdb_idl_index_find(struct ovsdb_idl_index_cursor *cursor,
+ struct ovsdb_idl_row *value)
+{
+ if(value) {
+ cursor->position = skiplist_find(cursor->index->skiplist, value);
+ } else {
+ cursor->position = skiplist_first(cursor->index->skiplist);
+ }
+ return ovsdb_idl_index_data(cursor);
+}
+
+/*
+ * Moves the cursor to the first entry with a value greater or equal
+ * to the given value.
+ * If the value given is NULL then the function will behave like
+ * ovsdb_idl_index_first.
+ * Returns a pointer to the corresponding ovsdb_idl_row (that can be casted
+ * to a ovsrec) or NULL.
+ */
+struct ovsdb_idl_row *
+ovsdb_idl_index_forward_to(struct ovsdb_idl_index_cursor *cursor,
+ struct ovsdb_idl_row *value)
+{
+ if(value) {
+ cursor->position = skiplist_forward_to(cursor->index->skiplist, value);
+ } else {
+ cursor->position = skiplist_first(cursor->index->skiplist);
+ }
+ return ovsdb_idl_index_data(cursor);
+}
+
+/*
+ * Returns the result of comparing two ovsrecs (casted to ovsdb_idl_row),
+ * using the comparer defined in the index.
+ * Returns:
+ * < 0 if a < b
+ * 0 if a == b
+ * > 0 if a > b
+ * When some input is NULL this function considers NULL to be greater than
+ * any other value. NULL compared to NULL returns 1.
+ */
+int
+ovsdb_idl_index_compare(struct ovsdb_idl_index_cursor *cursor,
+ struct ovsdb_idl_row *a, struct ovsdb_idl_row *b)
+{
+ if(a && b) {
+ return ovsdb_idl_index_generic_comparer(a, b, cursor->index);
+ } else if(a) {
+ return -1;
+ } else {
+ /* If cmp(NULL, b) or cmp(NULL, NULL) */
+ return 1;
+ }
+}
+
static void
ovsdb_idl_row_clear_old(struct ovsdb_idl_row *row)
{
@@ -1613,11 +1986,14 @@ ovsdb_idl_insert_row(struct ovsdb_idl_row *row, const struct json *row_json)
ovsdb_idl_row_parse(row);
ovsdb_idl_row_reparse_backrefs(row);
+
+ ovsdb_idl_add_to_indexes(row);
}
static void
ovsdb_idl_delete_row(struct ovsdb_idl_row *row)
{
+ ovsdb_idl_remove_from_indexes(row);
ovsdb_idl_row_unparse(row);
ovsdb_idl_row_clear_arcs(row, true);
ovsdb_idl_row_clear_old(row);
@@ -1635,10 +2011,12 @@ ovsdb_idl_modify_row(struct ovsdb_idl_row *row, const struct json *row_json)
{
bool changed;
+ ovsdb_idl_remove_from_indexes(row);
ovsdb_idl_row_unparse(row);
ovsdb_idl_row_clear_arcs(row, true);
changed = ovsdb_idl_row_update(row, row_json, OVSDB_IDL_CHANGE_MODIFY);
ovsdb_idl_row_parse(row);
+ ovsdb_idl_add_to_indexes(row);
return changed;
}
diff --git a/lib/ovsdb-idl.h b/lib/ovsdb-idl.h
index 136c38c..fcbc3ab 100644
--- a/lib/ovsdb-idl.h
+++ b/lib/ovsdb-idl.h
@@ -1,4 +1,5 @@
/* Copyright (c) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Nicira, Inc.
+ * Copyright (C) 2016 Hewlett Packard Enterprise Development LP
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
@@ -38,6 +39,7 @@
#include <stdint.h>
#include "compiler.h"
#include "ovsdb-types.h"
+#include "skiplist.h"
struct json;
struct ovsdb_datum;
@@ -276,4 +278,65 @@ void ovsdb_idl_loop_destroy(struct ovsdb_idl_loop *);
struct ovsdb_idl_txn *ovsdb_idl_loop_run(struct ovsdb_idl_loop *);
void ovsdb_idl_loop_commit_and_wait(struct ovsdb_idl_loop *);
+struct ovsdb_idl_index *
+ovsdb_idl_create_index(struct ovsdb_idl *idl,
+ const struct ovsdb_idl_table_class *tc,
+ const char *index_name);
+
+#define OVSDB_INDEX_DESC -1
+#define OVSDB_INDEX_ASC 1
+
+/*
+ * Skiplist comparison function. Allows to store sorted data.
+ */
+typedef int
+(*column_comparator)(const void *a, const void *b);
+
+/*
+ * Defines a IDL compound index
+ */
+struct ovsdb_idl_index {
+ struct skiplist *skiplist; /* Skiplist with pointer to
+ * rows*/
+ const struct ovsdb_idl_column **columns; /* Columns indexed */
+ column_comparator *comparers; /* Compare functions used */
+ int *sorting_order; /* Order per column */
+ size_t n_columns; /* Number of columns in index */
+ size_t alloc_columns; /* Size allocated memory for
+ * columns, comparers and
+ * sorting order */
+ bool row_sync; /* Determines if the replica
+ * is modifying its content or
+ * not */
+ const struct ovsdb_idl_table *table; /* Table that owns this index */
+ const char* index_name; /* The name of this index */
+};
+
+struct ovsdb_idl_index_cursor {
+ struct ovsdb_idl_index *index; /* Index used by this cursor */
+ struct skiplist_node *position; /* Current position in the index */
+};
+
+int ovsdb_idl_index_strcmp(char *, char *);
+int ovsdb_idl_index_intcmp(int64_t, int64_t);
+int ovsdb_idl_index_doublecmp(double, double);
+void ovsdb_idl_index_add_column(struct ovsdb_idl_index *,
+ const struct ovsdb_idl_column *,
+ int order,
+ column_comparator custom_comparer
+ );
+bool ovsdb_idl_initialize_cursor(struct ovsdb_idl *,
+ const struct ovsdb_idl_table_class *tc,
+ const char *index_name,
+ struct ovsdb_idl_index_cursor *cursor);
+struct ovsdb_idl_row *ovsdb_idl_index_first(struct ovsdb_idl_index_cursor *);
+struct ovsdb_idl_row *ovsdb_idl_index_next(struct ovsdb_idl_index_cursor *);
+struct ovsdb_idl_row *ovsdb_idl_index_data(struct ovsdb_idl_index_cursor *);
+struct ovsdb_idl_row *ovsdb_idl_index_find(struct ovsdb_idl_index_cursor *,
+ struct ovsdb_idl_row *);
+struct ovsdb_idl_row *ovsdb_idl_index_forward_to(struct ovsdb_idl_index_cursor *,
+ struct ovsdb_idl_row *);
+int ovsdb_idl_index_compare(struct ovsdb_idl_index_cursor *,
+ struct ovsdb_idl_row *a, struct ovsdb_idl_row *b);
+
#endif /* ovsdb-idl.h */
--
1.9.1
More information about the dev
mailing list