[ovs-dev] [PATCH] ovsdb-idl: Add additional support for change tracking.

Ansari, Shad shad.ansari at hp.com
Fri Aug 21 17:30:06 UTC 2015


Ovsdb-idl notifies a client that something changed; it does not track
which table, row changed in what way (insert, modify or delete).
As a result, a client has to scan or reconfigure the entire idl after
ovsdb_idl_run(). This is presumably fine for typical ovs schemas where
tables are relatively small. In use-cases where ovsdb is used with schemas
that can have very large tables, the current ovsdb-idl notification
mechanism does not appear to scale - clients need to do a lot of
processing to determine the exact change delta.

This change adds support for:
- Table and row based change sequence numbers to record the
   most recent IDL change sequence numbers associated with insert,
   modify or delete update on that table or row.
- Allow change tracking of specific columns. This ensures that changed
   rows (inserted, modified, deleted) that have tracked columns, are
   tracked by IDL. The client can directly access the changed rows
   with get_first, get_next operations without the need to scan the
   entire table.
   The tracking functionality is not enabled by default and needs to
   be turned on per-column by the client after ovsdb_idl_create()
   and before ovsdb_idl_run().

Signed-off-by: Shad Ansari shad.ansari at hp.com<mailto:shad.ansari at hp.com>
---
lib/ovsdb-idl-provider.h |   5 ++
lib/ovsdb-idl.c          | 175 ++++++++++++++++++++++++++++++++++++++++++++---
lib/ovsdb-idl.h          |  29 ++++++++
ovsdb/ovsdb-idlc.in      |  32 +++++++++
4 files changed, 230 insertions(+), 11 deletions(-)

diff --git a/lib/ovsdb-idl-provider.h b/lib/ovsdb-idl-provider.h
index 2ed78a7..3dddf69 100644
--- a/lib/ovsdb-idl-provider.h
+++ b/lib/ovsdb-idl-provider.h
@@ -36,6 +36,9 @@ struct ovsdb_idl_row {
     unsigned long int *prereqs; /* Bitmap of columns to verify in "old". */
     unsigned long int *written; /* Bitmap of columns from "new" to write. */
     struct hmap_node txn_node;  /* Node in ovsdb_idl_txn's list. */
+
+    unsigned int change_seqno[OVSDB_IDL_CHANGE_MAX];
+    struct ovs_list track_node;
};

 struct ovsdb_idl_column {
@@ -62,6 +65,8 @@ struct ovsdb_idl_table {
     struct shash columns;    /* Contains "const struct ovsdb_idl_column *"s. */
     struct hmap rows;        /* Contains "struct ovsdb_idl_row"s. */
     struct ovsdb_idl *idl;   /* Containing idl. */
+    unsigned int change_seqno[OVSDB_IDL_CHANGE_MAX];
+    struct ovs_list track_list; /* Tracked rows (ovsdb_idl_row.track_node). */
};

 struct ovsdb_idl_class {
diff --git a/lib/ovsdb-idl.c b/lib/ovsdb-idl.c
index 00b900d..e35de11 100644
--- a/lib/ovsdb-idl.c
+++ b/lib/ovsdb-idl.c
@@ -156,7 +156,7 @@ static struct ovsdb_idl_row *ovsdb_idl_row_create__(
     const struct ovsdb_idl_table_class *);
static struct ovsdb_idl_row *ovsdb_idl_row_create(struct ovsdb_idl_table *,
                                                   const struct uuid *);
-static void ovsdb_idl_row_destroy(struct ovsdb_idl_row *);
+static void ovsdb_idl_row_destroy(struct ovsdb_idl_row *, bool track);

 static void ovsdb_idl_row_parse(struct ovsdb_idl_row *);
static void ovsdb_idl_row_unparse(struct ovsdb_idl_row *);
@@ -174,6 +174,10 @@ static void ovsdb_idl_parse_lock_reply(struct ovsdb_idl *,
static void ovsdb_idl_parse_lock_notify(struct ovsdb_idl *,
                                         const struct json *params,
                                         bool new_has_lock);
+static struct ovsdb_idl_table *
+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);

 /* Creates and returns a connection to database 'remote', which should be in a
  * form acceptable to jsonrpc_session_open().  The connection will maintain an
@@ -227,6 +231,10 @@ ovsdb_idl_create(const char *remote, const struct ovsdb_idl_class *class,
             shash_add_assert(&table->columns, column->name, column);
         }
         hmap_init(&table->rows);
+        list_init(&table->track_list);
+        table->change_seqno[OVSDB_IDL_CHANGE_INSERT]
+            = table->change_seqno[OVSDB_IDL_CHANGE_MODIFY]
+            = table->change_seqno[OVSDB_IDL_CHANGE_DELETE] = 0;
         table->idl = idl;
     }

@@ -292,10 +300,16 @@ ovsdb_idl_clear(struct ovsdb_idl *idl)
             /* No need to do anything with dst_arcs: some node has those arcs
              * as forward arcs and will destroy them itself. */

-            ovsdb_idl_row_destroy(row);
+            if (!list_is_empty(&row->track_node)) {
+                list_remove(&row->track_node);
+            }
+
+            ovsdb_idl_row_destroy(row, false);
         }
     }

+    ovsdb_idl_track_clear(idl);
+
     if (changed) {
         idl->change_seqno++;
     }
@@ -591,6 +605,124 @@ ovsdb_idl_omit(struct ovsdb_idl *idl, const struct ovsdb_idl_column *column)
{
     *ovsdb_idl_get_mode(idl, column) = 0;
}
+
+/* Returns the most recent IDL change sequence number that caused a
+ * insert, modify or delete update to the table with class 'table_class'.
+ */
+unsigned int
+ovsdb_idl_table_get_seqno(const struct ovsdb_idl *idl,
+                          const struct ovsdb_idl_table_class *table_class)
+{
+    struct ovsdb_idl_table *table
+        = ovsdb_idl_table_from_class(idl, table_class);
+    unsigned int max_seqno = table->change_seqno[OVSDB_IDL_CHANGE_INSERT];
+
+    if (max_seqno < table->change_seqno[OVSDB_IDL_CHANGE_MODIFY]) {
+        max_seqno = table->change_seqno[OVSDB_IDL_CHANGE_MODIFY];
+    }
+    if (max_seqno < table->change_seqno[OVSDB_IDL_CHANGE_DELETE]) {
+        max_seqno = table->change_seqno[OVSDB_IDL_CHANGE_DELETE];
+    }
+    return max_seqno;
+}
+
+/* For each row that contains tracked columns, IDL stores the most
+ * recent IDL change sequence numbers associateed with insert, modify
+ * and delete updates to the table.
+ */
+unsigned int
+ovsdb_idl_row_get_seqno(const struct ovsdb_idl_row *row,
+                        enum ovsdb_idl_change change)
+{
+    return row->change_seqno[change];
+}
+
+/* Turns on OVSDB_IDL_TRACK for 'column' in 'idl', ensuring that
+ * all rows whose 'column' is modified are traced. Similarly, insert
+ * or delete of rows having 'column' are tracked. Clients are able
+ * to retrive the tracked rows with the ovsdb_idl_track_get_*()
+ * functions.
+ *
+ * This function should be called between ovsdb_idl_create() and
+ * the first call to ovsdb_idl_run(). The column to be tracked
+ * should have OVSDB_IDL_ALERT turned on.
+ */
+void
+ovsdb_idl_track_add_column(struct ovsdb_idl *idl,
+                           const struct ovsdb_idl_column *column)
+{
+    if (*ovsdb_idl_get_mode(idl, column) & OVSDB_IDL_ALERT) {
+        *ovsdb_idl_get_mode(idl, column) |= OVSDB_IDL_TRACK;
+    }
+}
+
+/* Returns true if 'table' has any tracked column. */
+static bool
+ovsdb_idl_track_is_set(struct ovsdb_idl_table *table) {
+    size_t i;
+
+    for (i = 0; i < table->class->n_columns; i++) {
+        if (table->modes[i] & OVSDB_IDL_TRACK) {
+            return true;
+        }
+    }
+   return false;
+}
+
+/* Returns the first tracked row in table with class 'table_class'
+ * for the specified 'idl'. Returns NULL if there are no tracked rows */
+const struct ovsdb_idl_row *
+ovsdb_idl_track_get_first(const struct ovsdb_idl *idl,
+                          const struct ovsdb_idl_table_class *table_class)
+{
+    struct ovsdb_idl_table *table
+        = ovsdb_idl_table_from_class(idl, table_class);
+
+    if (!list_is_empty(&table->track_list)) {
+        return CONTAINER_OF(list_front(&table->track_list), struct ovsdb_idl_row, track_node);
+    }
+    return NULL;
+}
+
+/* Returns the next tracked row in table after the specified 'row'
+ * (in no particular order). Returns NULL if there are no tracked rows */
+const struct ovsdb_idl_row *
+ovsdb_idl_track_get_next(const struct ovsdb_idl_row *row)
+{
+    if (row->track_node.next != &row->table->track_list) {
+        return CONTAINER_OF(row->track_node.next, struct ovsdb_idl_row, track_node);
+    }
+
+    return NULL;
+}
+
+/* Flushes the tracked rows. Client calls this function after calling
+ * ovsdb_idl_run() and read all tracked rows with the ovsdb_idl_track_get_*()
+ * functions. This is usually done at the end of the client's processing
+ * loop when it is ready to do ovsdb_idl_run() again.
+ */
+void
+ovsdb_idl_track_clear(const struct ovsdb_idl *idl)
+{
+    size_t i;
+
+    for (i = 0; i < idl->class->n_tables; i++) {
+        struct ovsdb_idl_table *table = &idl->tables[i];
+
+        if (!list_is_empty(&table->track_list)) {
+            struct ovsdb_idl_row *row, *next;
+
+            LIST_FOR_EACH_SAFE(row, next, track_node, &table->track_list) {
+                list_remove(&row->track_node);
+                list_init(&row->track_node);
+                if (ovsdb_idl_row_is_orphan(row)) {
+                    free(row);
+                }
+            }
+        }
+    }
+}
+


 static void
ovsdb_idl_send_schema_request(struct ovsdb_idl *idl)
@@ -916,7 +1048,8 @@ ovsdb_idl_process_update(struct ovsdb_idl_table *table,
/* Returns true if a column with mode OVSDB_IDL_MODE_RW changed, false
  * otherwise. */
static bool
-ovsdb_idl_row_update(struct ovsdb_idl_row *row, const struct json *row_json)
+ovsdb_idl_row_update(struct ovsdb_idl_row *row, const struct json *row_json,
+                     enum ovsdb_idl_change change)
{
     struct ovsdb_idl_table *table = row->table;
     struct shash_node *node;
@@ -944,6 +1077,12 @@ ovsdb_idl_row_update(struct ovsdb_idl_row *row, const struct json *row_json)
                 ovsdb_datum_swap(old, &datum);
                 if (table->modes[column_idx] & OVSDB_IDL_ALERT) {
                     changed = true;
+                    row->change_seqno[change] = row->table->change_seqno[change]
+                        = row->table->idl->change_seqno + 1;
+                    if ((table->modes[column_idx] & OVSDB_IDL_TRACK)
+                        && (!list_is_empty(&row->track_node))) {
+                        list_push_front(&row->table->track_list, &row->track_node);
+                    }
                 }
             } else {
                 /* Didn't really change but the OVSDB monitor protocol always
@@ -1067,13 +1206,15 @@ ovsdb_idl_row_clear_arcs(struct ovsdb_idl_row *row, bool destroy_dsts)
     struct ovsdb_idl_arc *arc, *next;

     /* Delete all forward arcs.  If 'destroy_dsts', destroy any orphaned rows
-     * that this causes to be unreferenced. */
+     * that this causes to be unreferenced, if tracking is not enabled.
+     * If tracking is enabled, orphaned nodes are removed from hmap but not freed.
+     */
     LIST_FOR_EACH_SAFE (arc, next, src_node, &row->src_arcs) {
         list_remove(&arc->dst_node);
         if (destroy_dsts
             && ovsdb_idl_row_is_orphan(arc->dst)
             && list_is_empty(&arc->dst->dst_arcs)) {
-            ovsdb_idl_row_destroy(arc->dst);
+            ovsdb_idl_row_destroy(arc->dst, ovsdb_idl_track_is_set(row->table));
         }
         free(arc);
     }
@@ -1113,6 +1254,7 @@ ovsdb_idl_row_create__(const struct ovsdb_idl_table_class *class)
     list_init(&row->src_arcs);
     list_init(&row->dst_arcs);
     hmap_node_nullify(&row->txn_node);
+    list_init(&row->track_node);
     return row;
}

@@ -1127,12 +1269,21 @@ ovsdb_idl_row_create(struct ovsdb_idl_table *table, const struct uuid *uuid)
}

 static void
-ovsdb_idl_row_destroy(struct ovsdb_idl_row *row)
+ovsdb_idl_row_destroy(struct ovsdb_idl_row *row, bool track)
{
     if (row) {
         ovsdb_idl_row_clear_old(row);
         hmap_remove(&row->table->rows, &row->hmap_node);
-        free(row);
+        if (!track) {
+            free(row);
+        } else {
+           row->change_seqno[OVSDB_IDL_CHANGE_DELETE]
+               = row->table->change_seqno[OVSDB_IDL_CHANGE_DELETE]
+               = row->table->idl->change_seqno + 1;
+           if (!list_is_empty(&row->track_node)) {
+               list_push_front(&row->table->track_list, &row->track_node);
+           }
+        }
     }
}

@@ -1147,7 +1298,7 @@ ovsdb_idl_insert_row(struct ovsdb_idl_row *row, const struct json *row_json)
     for (i = 0; i < class->n_columns; i++) {
         ovsdb_datum_init_default(&row->old[i], &class->columns[i].type);
     }
-    ovsdb_idl_row_update(row, row_json);
+    ovsdb_idl_row_update(row, row_json, OVSDB_IDL_CHANGE_INSERT);
     ovsdb_idl_row_parse(row);

     ovsdb_idl_row_reparse_backrefs(row);
@@ -1156,11 +1307,13 @@ ovsdb_idl_insert_row(struct ovsdb_idl_row *row, const struct json *row_json)
static void
ovsdb_idl_delete_row(struct ovsdb_idl_row *row)
{
-    ovsdb_idl_row_unparse(row);
+    if (!ovsdb_idl_track_is_set(row->table)) {
+        ovsdb_idl_row_unparse(row);
+    }
     ovsdb_idl_row_clear_arcs(row, true);
     ovsdb_idl_row_clear_old(row);
     if (list_is_empty(&row->dst_arcs)) {
-        ovsdb_idl_row_destroy(row);
+        ovsdb_idl_row_destroy(row, ovsdb_idl_track_is_set(row->table));
     } else {
         ovsdb_idl_row_reparse_backrefs(row);
     }
@@ -1175,7 +1328,7 @@ ovsdb_idl_modify_row(struct ovsdb_idl_row *row, const struct json *row_json)

     ovsdb_idl_row_unparse(row);
     ovsdb_idl_row_clear_arcs(row, true);
-    changed = ovsdb_idl_row_update(row, row_json);
+    changed = ovsdb_idl_row_update(row, row_json, OVSDB_IDL_CHANGE_MODIFY);
     ovsdb_idl_row_parse(row);

     return changed;
diff --git a/lib/ovsdb-idl.h b/lib/ovsdb-idl.h
index ac63ec9..153f4f1 100644
--- a/lib/ovsdb-idl.h
+++ b/lib/ovsdb-idl.h
@@ -42,6 +42,7 @@
struct json;
struct ovsdb_datum;
struct ovsdb_idl_class;
+struct ovsdb_idl_row;
struct ovsdb_idl_column;
struct ovsdb_idl_table_class;
struct uuid;
@@ -93,9 +94,14 @@ int ovsdb_idl_get_last_error(const struct ovsdb_idl *);
  *     is suitable only for use by a client that "owns" a particular column.
  *
  *   - OVDSB_IDL_ALERT without OVSDB_IDL_MONITOR is not valid.
+ *
+ *   - (OVSDB_IDL_MONITOR | OVSDB_IDL_ALERT | OVSDB_IDL_TRACK), for a column
+ *     that a client wants to track using the change tracking
+ *     ovsdb_idl_track_get_*() functions.
  */
#define OVSDB_IDL_MONITOR (1 << 0) /* Monitor this column? */
#define OVSDB_IDL_ALERT   (1 << 1) /* Alert client when column updated? */
+#define OVSDB_IDL_TRACK   (1 << 2)

 void ovsdb_idl_add_column(struct ovsdb_idl *, const struct ovsdb_idl_column *);
void ovsdb_idl_add_table(struct ovsdb_idl *,
@@ -103,6 +109,29 @@ void ovsdb_idl_add_table(struct ovsdb_idl *,

 void ovsdb_idl_omit(struct ovsdb_idl *, const struct ovsdb_idl_column *);
void ovsdb_idl_omit_alert(struct ovsdb_idl *, const struct ovsdb_idl_column *);
+
+/* Row, table sequence numbers */
+unsigned int ovsdb_idl_table_get_seqno(
+    const struct ovsdb_idl *idl,
+    const struct ovsdb_idl_table_class *table_class);
+unsigned int ovsdb_idl_row_get_seqno(
+    const struct ovsdb_idl_row *row,
+    unsigned int track_flags);
+
+/* Change tracking. */
+enum ovsdb_idl_change {
+    OVSDB_IDL_CHANGE_INSERT,
+    OVSDB_IDL_CHANGE_MODIFY,
+    OVSDB_IDL_CHANGE_DELETE,
+    OVSDB_IDL_CHANGE_MAX
+};
+void ovsdb_idl_track_add_column(struct ovsdb_idl *idl,
+                                const struct ovsdb_idl_column *column);
+const struct ovsdb_idl_row *ovsdb_idl_track_get_first(
+    const struct ovsdb_idl *, const struct ovsdb_idl_table_class *);
+const struct ovsdb_idl_row *ovsdb_idl_track_get_next(const struct ovsdb_idl_row *);
+void ovsdb_idl_track_clear(const struct ovsdb_idl *);
+


 /* Reading the database replica. */

diff --git a/ovsdb/ovsdb-idlc.in b/ovsdb/ovsdb-idlc.in
index 555efca..282feb2 100755
--- a/ovsdb/ovsdb-idlc.in
+++ b/ovsdb/ovsdb-idlc.in
@@ -177,6 +177,15 @@ const struct %(s)s *%(s)s_next(const struct %(s)s *);
              (ROW) ? ((NEXT) = %(s)s_next(ROW), 1) : 0; \\
              (ROW) = (NEXT))

+unsigned int %(s)s_get_seqno(const struct ovsdb_idl *);
+unsigned int %(s)s_row_get_seqno(const struct %(s)s *row, enum ovsdb_idl_change change);
+const struct %(s)s *%(s)s_track_get_first(const struct ovsdb_idl *);
+const struct %(s)s *%(s)s_track_get_next(const struct %(s)s *);
+#define %(S)s_FOR_EACH_TRACKED(ROW, IDL) \\
+        for ((ROW) = %(s)s_track_get_first(IDL); \\
+             (ROW); \\
+             (ROW) = %(s)s_track_get_next(ROW))
+
void %(s)s_init(struct %(s)s *);
void %(s)s_delete(const struct %(s)s *);
struct %(s)s *%(s)s_insert(struct ovsdb_idl_txn *);
@@ -462,6 +471,28 @@ const struct %(s)s *
%(s)s_next(const struct %(s)s *row)
{
     return %(s)s_cast(ovsdb_idl_next_row(&row->header_));
+}
+
+unsigned int %(s)s_get_seqno(const struct ovsdb_idl *idl)
+{
+    return ovsdb_idl_table_get_seqno(idl, &%(p)stable_classes[%(P)sTABLE_%(T)s]);
+}
+
+unsigned int %(s)s_row_get_seqno(const struct %(s)s *row, enum ovsdb_idl_change change)
+{
+    return ovsdb_idl_row_get_seqno(&row->header_, change);
+}
+
+const struct %(s)s *
+%(s)s_track_get_first(const struct ovsdb_idl *idl)
+{
+    return %(s)s_cast(ovsdb_idl_track_get_first(idl, &%(p)stable_classes[%(P)sTABLE_%(T)s]));
+}
+
+const struct %(s)s
+*%(s)s_track_get_next(const struct %(s)s *row)
+{
+    return %(s)s_cast(ovsdb_idl_track_get_next(&row->header_));
}''' % {'s': structName,
         'p': prefix,
         'P': prefix.upper(),
@@ -469,6 +500,7 @@ const struct %(s)s *
         'T': tableName.upper()}

         print '''
+
/* Deletes 'row' from table "%(t)s".  'row' may be freed, so it must not be
  * accessed afterward.
  *
--
1.9.1






More information about the dev mailing list