ovsdb: Implement garbage collection.

9 files changed, 237 insertions, 39 deletions

diff --git a/ovsdb/SPECS b/ovsdb/SPECS
index d64812ae6..3a9af9f39 100644
--- a/ovsdb/SPECS
+++ b/ovsdb/SPECS
@@ -131,6 +131,7 @@ is represented by <database-schema>, as described below.
 
         "columns": {<id>: <column-schema>, ...}   required
         "maxRows": <integer>                      optional
+        "isRoot": <boolean>                       optional
 
     The value of "columns" is a JSON object whose names are column
     names and whose values are <column-schema>s.
@@ -152,12 +153,28 @@ is represented by <database-schema>, as described below.
         the database process is stopped and then started again, each
         "_version" also changes to a new random value.
 
+    If "isRoot" is omitted or specified as false, then any given row
+    in the table may exist only when there is at least one reference
+    to it, with refType "strong", from a different row (in the same
+    table or a different table).  This is a "deferred" action:
+    unreferenced rows in the table are deleted just before transaction
+    commit.  If "isRoot" is specified as true, then rows in the table
+    exist independent of any references (they can be thought of as
+    part of the "root set" in a garbage collector).
+
+    For compatibility with schemas created before "isRoot" was
+    introduced, if "isRoot" is omitted or false in every
+    <table-schema> in a given <database-schema>, then every table is
+    part of the root set.
+
     If "maxRows" is specified, as a positive integer, it limits the
     maximum number of rows that may be present in the table.  This is
     a "deferred" constraint, enforced only at transaction commit time
     (see the "transact" request below).  If "maxRows" is not
     specified, the size of the table is limited only by the resources
-    available to the database server.
+    available to the database server.  "maxRows" constraints are
+    enforced after unreferenced rows are deleted from tables with a
+    false "isRoot".
 
 <column-schema>
 
diff --git a/ovsdb/dot2pic b/ovsdb/dot2pic
index caca9f8d0..52de5e821 100755
--- a/ovsdb/dot2pic
+++ b/ovsdb/dot2pic
@@ -1,6 +1,6 @@
 #! /usr/bin/perl
 
-# Copyright (c) 2009, 2010 Nicira Networks
+# Copyright (c) 2009, 2010, 2011 Nicira Networks
 #
 # Licensed under the Apache License, Version 2.0 (the "License");
 # you may not use this file except in compliance with the License.
@@ -29,7 +29,14 @@ while (<>) {
         $y *= $scale;
         $width *= $scale;
         $height *= $scale;
+        print "linethick = ", ($style eq 'bold' ? 0.5 : 1.0), ";\n";
         print "box at $x,$y wid $width height $height \"$name\"\n";
+        if ($style eq 'bold') {
+            my $inset = 2.0 / 72.0;
+            $width -= $inset * 2;
+            $height -= $inset * 2;
+            print "box at $x,$y wid $width height $height\n";
+        }
     } elsif (/edge/) {
         my (undef, $tail, $head, $n, $rest) = split(' ', $_, 5);
         my @xy;
@@ -51,6 +58,8 @@ while (<>) {
         }
         my ($style, $color) = split(' ', $rest);
 
+        print "linethick = ", ($style eq 'dotted' ? 0.5 : 1), ";\n";
+
         print "spline -> from $xy[0][0],$xy[0][1]";
         for (my ($i) = 0; $i <= $#xy; $i++) {
             print " to $xy[$i][0],$xy[$i][1]";
diff --git a/ovsdb/ovsdb-doc.in b/ovsdb/ovsdb-doc.in
index 5f3033480..5ba4e7168 100755
--- a/ovsdb/ovsdb-doc.in
+++ b/ovsdb/ovsdb-doc.in
@@ -290,9 +290,11 @@ Table	Purpose
 .SH "TABLE RELATIONSHIPS"
 .PP
 The following diagram shows the relationship among tables in the
-database.  Each node represents a table.  Each edge leads from the
+database.  Each node represents a table.  Tables that are part of the
+``root set'' are shown with double borders.  Each edge leads from the
 table that contains it and points to the table that its value
-represents.  Edges are labeled with their column names.
+represents.  Edges are labeled with their column names.  Thick lines
+represent strong references; thin lines represent weak references.
 .RS -1in
 """
         erStream = open(erFile, "r")
diff --git a/ovsdb/ovsdb-dot.in b/ovsdb/ovsdb-dot.in
index 571ac8f0c..d41728627 100755
--- a/ovsdb/ovsdb-dot.in
+++ b/ovsdb/ovsdb-dot.in
@@ -16,6 +16,7 @@ def printEdge(tableName, baseType, label):
         options['label'] = '"%s"' % label
         if baseType.ref_type == 'weak':
             options['constraint'] = 'false'
+            options['style'] = 'dotted'
         print "\t%s -> %s [%s];" % (
             tableName,
             baseType.ref_table,
@@ -25,12 +26,17 @@ def schemaToDot(schemaFile):
     schema = ovs.db.schema.DbSchema.from_json(ovs.json.from_file(schemaFile))
 
     print "digraph %s {" % schema.name
+    print '\tsize="6.5,4";'
+    print '\tmargin="0";'
+    print "\tnode [shape=box];"
+    print "\tedge [dir=none, arrowhead=none, arrowtail=none];"
     for tableName, table in schema.tables.iteritems():
-        print '\tsize="6.5,4";'
-        print '\tmargin="0";'
-        print "\tnode [shape=box];"
-        print "\tedge [dir=none, arrowhead=none, arrowtail=none];"
-        print "\t%s;" % tableName
+        options = {}
+        if table.is_root:
+            options['style'] = 'bold'
+        print "\t%s [%s];" % (
+            tableName,
+            ', '.join(['%s=%s' % (k,v) for k,v in options.items()]))
         for columnName, column in table.columns.iteritems():
             if column.type.value:
                 printEdge(tableName, column.type.key, "%s key" % columnName)
diff --git a/ovsdb/ovsdb-idlc.in b/ovsdb/ovsdb-idlc.in
index 418308995..2a4c67ca3 100755
--- a/ovsdb/ovsdb-idlc.in
+++ b/ovsdb/ovsdb-idlc.in
@@ -487,7 +487,11 @@ static void\n%s_columns_init(void)
     print "struct ovsdb_idl_table_class %stable_classes[%sN_TABLES] = {" % (prefix, prefix.upper())
     for tableName, table in sorted(schema.tables.iteritems()):
         structName = "%s%s" % (prefix, tableName.lower())
-        print "    {\"%s\"," % tableName
+        if table.is_root:
+            is_root = "true"
+        else:
+            is_root = "false"
+        print "    {\"%s\", %s," % (tableName, is_root)
         print "     %s_columns, ARRAY_SIZE(%s_columns)," % (
             structName, structName)
         print "     sizeof(struct %s)}," % structName
diff --git a/ovsdb/ovsdb.c b/ovsdb/ovsdb.c
index e76544e36..aad84152b 100644
--- a/ovsdb/ovsdb.c
+++ b/ovsdb/ovsdb.c
@@ -127,6 +127,21 @@ is_valid_version(const char *s)
     return n != -1 && s[n] == '\0';
 }
 
+/* Returns the number of tables in 'schema''s root set. */
+static size_t
+root_set_size(const struct ovsdb_schema *schema)
+{
+    struct shash_node *node;
+    size_t n_root;
+
+    SHASH_FOR_EACH (node, &schema->tables) {
+        struct ovsdb_table_schema *table = node->data;
+
+        n_root += table->is_root;
+    }
+    return n_root;
+}
+
 struct ovsdb_error *
 ovsdb_schema_from_json(struct json *json, struct ovsdb_schema **schemap)
 {
@@ -205,6 +220,18 @@ ovsdb_schema_from_json(struct json *json, struct ovsdb_schema **schemap)
         }
     }
 
+    /* "isRoot" was not part of the original schema definition.  Before it was
+     * added, there was no support for garbage collection.  So, for backward
+     * compatibility, if the root set is empty then assume that every table is
+     * in the root set. */
+    if (root_set_size(schema) == 0) {
+        SHASH_FOR_EACH (node, &schema->tables) {
+            struct ovsdb_table_schema *table = node->data;
+
+            table->is_root = true;
+        }
+    }
+
     *schemap = schema;
     return 0;
 }
@@ -214,6 +241,7 @@ ovsdb_schema_to_json(const struct ovsdb_schema *schema)
 {
     struct json *json, *tables;
     struct shash_node *node;
+    bool default_is_root;
 
     json = json_object_create();
     json_object_put_string(json, "name", schema->name);
@@ -224,12 +252,18 @@ ovsdb_schema_to_json(const struct ovsdb_schema *schema)
         json_object_put_string(json, "cksum", schema->cksum);
     }
 
+    /* "isRoot" was not part of the original schema definition.  Before it was
+     * added, there was no support for garbage collection.  So, for backward
+     * compatibility, if every table is in the root set then do not output
+     * "isRoot" in table schemas. */
+    default_is_root = root_set_size(schema) == shash_count(&schema->tables);
+
     tables = json_object_create();
 
     SHASH_FOR_EACH (node, &schema->tables) {
         struct ovsdb_table_schema *table = node->data;
         json_object_put(tables, table->name,
-                        ovsdb_table_schema_to_json(table));
+                        ovsdb_table_schema_to_json(table, default_is_root));
     }
     json_object_put(json, "tables", tables);
 
diff --git a/ovsdb/table.c b/ovsdb/table.c
index 5e83683b7..2f693501b 100644
--- a/ovsdb/table.c
+++ b/ovsdb/table.c
@@ -1,4 +1,4 @@
-/* Copyright (c) 2009, 2010 Nicira Networks
+/* Copyright (c) 2009, 2010, 2011 Nicira Networks
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -37,7 +37,7 @@ add_column(struct ovsdb_table_schema *ts, struct ovsdb_column *column)
 
 struct ovsdb_table_schema *
 ovsdb_table_schema_create(const char *name, bool mutable,
-                          unsigned int max_rows)
+                          unsigned int max_rows, bool is_root)
 {
     struct ovsdb_column *uuid, *version;
     struct ovsdb_table_schema *ts;
@@ -47,6 +47,7 @@ ovsdb_table_schema_create(const char *name, bool mutable,
     ts->mutable = mutable;
     shash_init(&ts->columns);
     ts->max_rows = max_rows;
+    ts->is_root = is_root;
 
     uuid = ovsdb_column_create("_uuid", false, true, &ovsdb_type_uuid);
     add_column(ts, uuid);
@@ -65,7 +66,8 @@ ovsdb_table_schema_clone(const struct ovsdb_table_schema *old)
     struct ovsdb_table_schema *new;
     struct shash_node *node;
 
-    new = ovsdb_table_schema_create(old->name, old->mutable, old->max_rows);
+    new = ovsdb_table_schema_create(old->name, old->mutable,
+                                    old->max_rows, old->is_root);
     SHASH_FOR_EACH (node, &old->columns) {
         const struct ovsdb_column *column = node->data;
 
@@ -97,7 +99,7 @@ ovsdb_table_schema_from_json(const struct json *json, const char *name,
                              struct ovsdb_table_schema **tsp)
 {
     struct ovsdb_table_schema *ts;
-    const struct json *columns, *mutable, *max_rows;
+    const struct json *columns, *mutable, *max_rows, *is_root;
     struct shash_node *node;
     struct ovsdb_parser parser;
     struct ovsdb_error *error;
@@ -111,6 +113,7 @@ ovsdb_table_schema_from_json(const struct json *json, const char *name,
                                   OP_TRUE | OP_FALSE | OP_OPTIONAL);
     max_rows = ovsdb_parser_member(&parser, "maxRows",
                                    OP_INTEGER | OP_OPTIONAL);
+    is_root = ovsdb_parser_member(&parser, "isRoot", OP_BOOLEAN | OP_OPTIONAL);
     error = ovsdb_parser_finish(&parser);
     if (error) {
         return error;
@@ -133,7 +136,8 @@ ovsdb_table_schema_from_json(const struct json *json, const char *name,
 
     ts = ovsdb_table_schema_create(name,
                                    mutable ? json_boolean(mutable) : true,
-                                   MIN(n_max_rows, UINT_MAX));
+                                   MIN(n_max_rows, UINT_MAX),
+                                   is_root ? json_boolean(is_root) : false);
     SHASH_FOR_EACH (node, json_object(columns)) {
         struct ovsdb_column *column;
 
@@ -156,8 +160,19 @@ ovsdb_table_schema_from_json(const struct json *json, const char *name,
     return 0;
 }
 
+/* Returns table schema 'ts' serialized into JSON.
+ *
+ * The "isRoot" member is included in the JSON only if its value would differ
+ * from 'default_is_root'.  Ordinarily 'default_is_root' should be false,
+ * because ordinarily a table would be not be part of the root set if its
+ * "isRoot" member is omitted.  However, garbage collection was not orginally
+ * included in OVSDB, so in older schemas that do not include any "isRoot"
+ * members, every table is implicitly part of the root set.  To serialize such
+ * a schema in a way that can be read by older OVSDB tools, specify
+ * 'default_is_root' as true. */
 struct json *
-ovsdb_table_schema_to_json(const struct ovsdb_table_schema *ts)
+ovsdb_table_schema_to_json(const struct ovsdb_table_schema *ts,
+                           bool default_is_root)
 {
     struct json *json, *columns;
     struct shash_node *node;
@@ -166,6 +181,9 @@ ovsdb_table_schema_to_json(const struct ovsdb_table_schema *ts)
     if (!ts->mutable) {
         json_object_put(json, "mutable", json_boolean_create(false));
     }
+    if (default_is_root != ts->is_root) {
+        json_object_put(json, "isRoot", json_boolean_create(ts->is_root));
+    }
 
     columns = json_object_create();
 
diff --git a/ovsdb/table.h b/ovsdb/table.h
index 4d3b9ee72..95da74035 100644
--- a/ovsdb/table.h
+++ b/ovsdb/table.h
@@ -1,4 +1,4 @@
-/* Copyright (c) 2009, 2010 Nicira Networks
+/* Copyright (c) 2009, 2010, 2011 Nicira Networks
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -30,11 +30,11 @@ struct ovsdb_table_schema {
     bool mutable;
     struct shash columns;       /* Contains "struct ovsdb_column *"s. */
     unsigned int max_rows;      /* Maximum number of rows. */
+    bool is_root;               /* Part of garbage collection root set? */
 };
 
-struct ovsdb_table_schema *ovsdb_table_schema_create(const char *name,
-                                                     bool mutable,
-                                                     unsigned int max_rows);
+struct ovsdb_table_schema *ovsdb_table_schema_create(
+    const char *name, bool mutable, unsigned int max_rows, bool is_root);
 struct ovsdb_table_schema *ovsdb_table_schema_clone(
     const struct ovsdb_table_schema *);
 void ovsdb_table_schema_destroy(struct ovsdb_table_schema *);
@@ -43,7 +43,8 @@ struct ovsdb_error *ovsdb_table_schema_from_json(const struct json *,
                                                  const char *name,
                                                  struct ovsdb_table_schema **)
     WARN_UNUSED_RESULT;
-struct json *ovsdb_table_schema_to_json(const struct ovsdb_table_schema *);
+struct json *ovsdb_table_schema_to_json(const struct ovsdb_table_schema *,
+                                        bool default_is_root);
 
 const struct ovsdb_column *ovsdb_table_schema_get_column(
     const struct ovsdb_table_schema *, const char *name);
diff --git a/ovsdb/transaction.c b/ovsdb/transaction.c
index 615c164b2..c07541ed3 100644
--- a/ovsdb/transaction.c
+++ b/ovsdb/transaction.c
@@ -81,6 +81,8 @@ struct ovsdb_txn_row {
     unsigned long changed[];    /* Bits set to 1 for columns that changed. */
 };
 
+static struct ovsdb_error * WARN_UNUSED_RESULT
+delete_garbage_row(struct ovsdb_txn *txn, struct ovsdb_txn_row *r);
 static void ovsdb_txn_row_prefree(struct ovsdb_txn_row *);
 static struct ovsdb_error * WARN_UNUSED_RESULT
 for_each_txn_row(struct ovsdb_txn *txn,
@@ -158,6 +160,20 @@ find_txn_row(const struct ovsdb_table *table, const struct uuid *uuid)
     return NULL;
 }
 
+static struct ovsdb_txn_row *
+find_or_make_txn_row(struct ovsdb_txn *txn, const struct ovsdb_table *table,
+                     const struct uuid *uuid)
+{
+    struct ovsdb_txn_row *txn_row = find_txn_row(table, uuid);
+    if (!txn_row) {
+        const struct ovsdb_row *row = ovsdb_table_get_row(table, uuid);
+        if (row) {
+            txn_row = ovsdb_txn_row_modify(txn, row)->txn_row;
+        }
+    }
+    return txn_row;
+}
+
 static struct ovsdb_error * WARN_UNUSED_RESULT
 ovsdb_txn_adjust_atom_refs(struct ovsdb_txn *txn, const struct ovsdb_row *r,
                            const struct ovsdb_column *c,
@@ -175,24 +191,22 @@ ovsdb_txn_adjust_atom_refs(struct ovsdb_txn *txn, const struct ovsdb_row *r,
     table = base->u.uuid.refTable;
     for (i = 0; i < n; i++) {
         const struct uuid *uuid = &atoms[i].uuid;
-        struct ovsdb_txn_row *txn_row = find_txn_row(table, uuid);
+        struct ovsdb_txn_row *txn_row;
+
         if (uuid_equals(uuid, ovsdb_row_get_uuid(r))) {
             /* Self-references don't count. */
             continue;
         }
+
+        txn_row = find_or_make_txn_row(txn, table, uuid);
         if (!txn_row) {
-            const struct ovsdb_row *row = ovsdb_table_get_row(table, uuid);
-            if (row) {
-                txn_row = ovsdb_txn_row_modify(txn, row)->txn_row;
-            } else {
-                return ovsdb_error("referential integrity violation",
-                                   "Table %s column %s row "UUID_FMT" "
-                                   "references nonexistent row "UUID_FMT" in "
-                                   "table %s.",
-                                   r->table->schema->name, c->name,
-                                   UUID_ARGS(ovsdb_row_get_uuid(r)),
-                                   UUID_ARGS(uuid), table->schema->name);
-            }
+            return ovsdb_error("referential integrity violation",
+                               "Table %s column %s row "UUID_FMT" "
+                               "references nonexistent row "UUID_FMT" in "
+                               "table %s.",
+                               r->table->schema->name, c->name,
+                               UUID_ARGS(ovsdb_row_get_uuid(r)),
+                               UUID_ARGS(uuid), table->schema->name);
         }
         txn_row->n_refs += delta;
     }
@@ -258,6 +272,92 @@ check_ref_count(struct ovsdb_txn *txn OVS_UNUSED, struct ovsdb_txn_row *r)
 }
 
 static struct ovsdb_error * WARN_UNUSED_RESULT
+delete_row_refs(struct ovsdb_txn *txn, const struct ovsdb_row *row,
+                const struct ovsdb_base_type *base,
+                const union ovsdb_atom *atoms, unsigned int n)
+{
+    const struct ovsdb_table *table;
+    unsigned int i;
+
+    if (!ovsdb_base_type_is_strong_ref(base)) {
+        return NULL;
+    }
+
+    table = base->u.uuid.refTable;
+    for (i = 0; i < n; i++) {
+        const struct uuid *uuid = &atoms[i].uuid;
+        struct ovsdb_txn_row *txn_row;
+
+        if (uuid_equals(uuid, ovsdb_row_get_uuid(row))) {
+            /* Self-references don't count. */
+            continue;
+        }
+
+        txn_row = find_or_make_txn_row(txn, table, uuid);
+        if (!txn_row) {
+            return OVSDB_BUG("strong ref target missing");
+        } else if (!txn_row->n_refs) {
+            return OVSDB_BUG("strong ref target has zero n_refs");
+        } else if (!txn_row->new) {
+            return OVSDB_BUG("deleted strong ref target");
+        }
+
+        if (--txn_row->n_refs == 0) {
+            struct ovsdb_error *error = delete_garbage_row(txn, txn_row);
+            if (error) {
+                return error;
+            }
+        }
+    }
+
+    return NULL;
+}
+
+static struct ovsdb_error * WARN_UNUSED_RESULT
+delete_garbage_row(struct ovsdb_txn *txn, struct ovsdb_txn_row *txn_row)
+{
+    struct shash_node *node;
+    struct ovsdb_row *row;
+
+    if (txn_row->table->schema->is_root) {
+        return NULL;
+    }
+
+    row = txn_row->new;
+    txn_row->new = NULL;
+    hmap_remove(&txn_row->table->rows, &row->hmap_node);
+    SHASH_FOR_EACH (node, &txn_row->table->schema->columns) {
+        const struct ovsdb_column *column = node->data;
+        const struct ovsdb_datum *field = &row->fields[column->index];
+        struct ovsdb_error *error;
+
+        error = delete_row_refs(txn, row,
+                                &column->type.key, field->keys, field->n);
+        if (error) {
+            return error;
+        }
+
+        error = delete_row_refs(txn, row,
+                                &column->type.value, field->values, field->n);
+        if (error) {
+            return error;
+        }
+    }
+    ovsdb_row_destroy(row);
+
+    return NULL;
+}
+
+static struct ovsdb_error * WARN_UNUSED_RESULT
+collect_garbage(struct ovsdb_txn *txn, struct ovsdb_txn_row *txn_row)
+{
+    if (txn_row->new && !txn_row->n_refs) {
+        return delete_garbage_row(txn, txn_row);
+    }
+    return NULL;
+}
+
+static struct ovsdb_error * WARN_UNUSED_RESULT
 update_ref_counts(struct ovsdb_txn *txn)
 {
     struct ovsdb_error *error;
@@ -491,15 +591,22 @@ ovsdb_txn_commit(struct ovsdb_txn *txn, bool durable)
         return NULL;
     }
 
-    /* Check maximum rows table constraints. */
-    error = check_max_rows(txn);
+    /* Update reference counts and check referential integrity. */
+    error = update_ref_counts(txn);
     if (error) {
         ovsdb_txn_abort(txn);
         return error;
     }
 
-    /* Update reference counts and check referential integrity. */
-    error = update_ref_counts(txn);
+    /* Delete unreferenced, non-root rows. */
+    error = for_each_txn_row(txn, collect_garbage);
+    if (error) {
+        ovsdb_txn_abort(txn);
+        return OVSDB_WRAP_BUG("can't happen", error);
+    }
+
+    /* Check maximum rows table constraints. */
+    error = check_max_rows(txn);
     if (error) {
         ovsdb_txn_abort(txn);
         return error;