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 <esteb...@hpe.com> --- lib/ovsdb-idl-provider.h | 30 ++++ lib/ovsdb-idl.c | 378 ++++++++++++++++++++++++++++++++++++++++++++++- lib/ovsdb-idl.h | 52 +++++++ 3 files changed, 459 insertions(+), 1 deletion(-) diff --git a/lib/ovsdb-idl-provider.h b/lib/ovsdb-idl-provider.h index 027f79b..d9597be 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). */ }; @@ -78,6 +81,33 @@ struct ovsdb_idl_class { size_t n_tables; }; +/* + * Contains the configuration per column of the index + */ +struct ovsdb_idl_index_column { + const struct ovsdb_idl_column *column; + column_comparator *comparer; + int sorting_order; +}; + +/* + * Defines a IDL compound index + */ +struct ovsdb_idl_index { + struct skiplist *skiplist; /* Skiplist with pointer to + * rows*/ + struct ovsdb_idl_index_column *columns; /* Columns configuration */ + 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_row *ovsdb_idl_get_row_arc( struct ovsdb_idl_row *src, struct ovsdb_idl_table_class *dst_table, diff --git a/lib/ovsdb-idl.c b/lib/ovsdb-idl.c index 3ab05a3..06be5e8 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); @@ -204,6 +207,16 @@ 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, + size_t allocated_cols); +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 @@ -250,6 +263,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]; @@ -285,6 +299,8 @@ 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); @@ -319,6 +335,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) { @@ -1477,11 +1494,365 @@ ovsdb_idl_row_unparse(struct ovsdb_idl_row *row) for (i = 0; i < class->n_columns; i++) { const struct ovsdb_idl_column *c = &class->columns[i]; - (c->unparse)(row); + + (c->unparse) (row); + } +} + +/* + * The OVSDB-IDL Compound Indexes feature allows to create custom + * indexes over several columns in the IDL. + * With those index, the developer can retrieve rows matching a search + * criteria, or show the rows sorted in a specific way. + */ + +/* + * 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, 1); + 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, + size_t allocated_cols) +{ + struct ovsdb_idl_index *index; + + index = xmalloc(sizeof (struct ovsdb_idl_index)); + index->n_columns = 0; + index->alloc_columns = allocated_cols; + index->skiplist = skiplist_create(64, ovsdb_idl_index_generic_comparer, + index); + index->columns = xmalloc(allocated_cols * + sizeof (struct ovsdb_idl_index_column)); + 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); + } +} + +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++; + index->columns = xrealloc(index->columns, + index->alloc_columns * + sizeof(struct ovsdb_idl_index_column)); + } + + /* Append column to index */ + int i = index->n_columns; + + index->columns[i].column = column; + if (custom_comparer || column->compare) { + index->columns[i].comparer = 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->columns[i].sorting_order = OVSDB_INDEX_ASC; + } else { + index->columns[i].sorting_order = 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->columns[i].comparer(a, b); + + if (val) { + return val * index->columns[i].sorting_order; + } + } + + /* + * 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, and NULL == NULL. + */ +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 && !b) { + return 0; + } else if(a){ + return -1; + } else { + return 1; + } +} + +static void ovsdb_idl_row_clear_old(struct ovsdb_idl_row *row) { ovs_assert(row->old == row->new); @@ -1641,11 +2012,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); @@ -1663,10 +2037,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 e2e2a5e..357cbec 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; @@ -277,5 +279,55 @@ struct ovsdb_idl_loop { 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 *); + +/* + * The OVSDB-IDL Compound Indexes feature allows to create custom + * indexes over several columns in the IDL. + * With those index, the developer can retrieve rows matching a search + * criteria, or show the rows sorted in a specific way. + */ + +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); + +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 _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev