pintos-os.org Git - openvswitch/blob - lib/ovsdb-idl.c

   1 /* Copyright (c) 2009 Nicira Networks.
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at:
   6  *
   7  *     http://www.apache.org/licenses/LICENSE-2.0
   8  *
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <config.h>
  17
  18 #include "ovsdb-idl.h"
  19
  20 #include <assert.h>
  21 #include <limits.h>
  22 #include <stdlib.h>
  23
  24 #include "json.h"
  25 #include "jsonrpc.h"
  26 #include "ovsdb-data.h"
  27 #include "ovsdb-error.h"
  28 #include "ovsdb-idl-provider.h"
  29 #include "shash.h"
  30 #include "util.h"
  31
  32 #define THIS_MODULE VLM_ovsdb_idl
  33 #include "vlog.h"
  34
  35 /* An arc from one idl_row to another.  When row A contains a UUID that
  36  * references row B, this is represented by an arc from A (the source) to B
  37  * (the destination).
  38  *
  39  * Arcs from a row to itself are omitted, that is, src and dst are always
  40  * different.
  41  *
  42  * Arcs are never duplicated, that is, even if there are multiple references
  43  * from A to B, there is only a single arc from A to B.
  44  *
  45  * Arcs are directed: an arc from A to B is the converse of an an arc from B to
  46  * A.  Both an arc and its converse may both be present, if each row refers
  47  * to the other circularly.
  48  *
  49  * The source and destination row may be in the same table or in different
  50  * tables.
  51  */
  52 struct ovsdb_idl_arc {
  53     struct list src_node;       /* In src->src_arcs list. */
  54     struct list dst_node;       /* In dst->dst_arcs list. */
  55     struct ovsdb_idl_row *src;  /* Source row. */
  56     struct ovsdb_idl_row *dst;  /* Destination row. */
  57 };
  58
  59 struct ovsdb_idl {
  60     struct jsonrpc_session *session;
  61     struct shash tables;
  62     struct json *monitor_request_id;
  63     unsigned int last_monitor_request_seqno;
  64     unsigned int change_seqno;
  65 };
  66
  67 static struct vlog_rate_limit syntax_rl = VLOG_RATE_LIMIT_INIT(1, 5);
  68 static struct vlog_rate_limit semantic_rl = VLOG_RATE_LIMIT_INIT(1, 5);
  69
  70 static void ovsdb_idl_clear(struct ovsdb_idl *);
  71 static void ovsdb_idl_send_monitor_request(struct ovsdb_idl *);
  72 static void ovsdb_idl_parse_update(struct ovsdb_idl *, const struct json *);
  73 static struct ovsdb_error *ovsdb_idl_parse_update__(struct ovsdb_idl *,
  74                                                     const struct json *);
  75 static void ovsdb_idl_process_update(struct ovsdb_idl_table *,
  76                                      const struct uuid *,
  77                                      const struct json *old,
  78                                      const struct json *new);
  79 static void ovsdb_idl_insert_row(struct ovsdb_idl_row *, const struct json *);
  80 static void ovsdb_idl_delete_row(struct ovsdb_idl_row *);
  81 static void ovsdb_idl_modify_row(struct ovsdb_idl_row *, const struct json *);
  82
  83 static bool ovsdb_idl_row_is_orphan(const struct ovsdb_idl_row *);
  84 static struct ovsdb_idl_row *ovsdb_idl_row_create(struct ovsdb_idl_table *,
  85                                                   const struct uuid *);
  86 static void ovsdb_idl_row_destroy(struct ovsdb_idl_row *);
  87
  88 static void ovsdb_idl_row_clear_fields(struct ovsdb_idl_row *);
  89
  90 struct ovsdb_idl *
  91 ovsdb_idl_create(const char *remote, const struct ovsdb_idl_class *class)
  92 {
  93     struct ovsdb_idl *idl;
  94     size_t i;
  95
  96     idl = xzalloc(sizeof *idl);
  97     idl->session = jsonrpc_session_open(remote);
  98     shash_init(&idl->tables);
  99     for (i = 0; i < class->n_tables; i++) {
 100         const struct ovsdb_idl_table_class *tc = &class->tables[i];
 101         struct ovsdb_idl_table *table;
 102         size_t j;
 103
 104         table = xmalloc(sizeof *table);
 105         assert(!shash_find(&idl->tables, tc->name));
 106         shash_add(&idl->tables, tc->name, table);
 107         table->class = tc;
 108         shash_init(&table->columns);
 109         for (j = 0; j < tc->n_columns; j++) {
 110             const struct ovsdb_idl_column *column = &tc->columns[j];
 111
 112             assert(!shash_find(&table->columns, column->name));
 113             shash_add(&table->columns, column->name, column);
 114         }
 115         hmap_init(&table->rows);
 116         table->idl = idl;
 117     }
 118     idl->last_monitor_request_seqno = UINT_MAX;
 119
 120     return idl;
 121 }
 122
 123 void
 124 ovsdb_idl_destroy(struct ovsdb_idl *idl)
 125 {
 126     if (idl) {
 127         struct shash_node *node;
 128
 129         ovsdb_idl_clear(idl);
 130         jsonrpc_session_close(idl->session);
 131
 132         SHASH_FOR_EACH (node, &idl->tables) {
 133             struct ovsdb_idl_table *table = node->data;
 134
 135             shash_destroy(&table->columns);
 136             hmap_destroy(&table->rows);
 137         }
 138         shash_destroy(&idl->tables);
 139         json_destroy(idl->monitor_request_id);
 140         free(idl);
 141     }
 142 }
 143
 144 static void
 145 ovsdb_idl_clear(struct ovsdb_idl *idl)
 146 {
 147     struct shash_node *node;
 148     bool changed = false;
 149
 150     SHASH_FOR_EACH (node, &idl->tables) {
 151         struct ovsdb_idl_table *table = node->data;
 152         struct ovsdb_idl_row *row, *next_row;
 153
 154         if (hmap_is_empty(&table->rows)) {
 155             continue;
 156         }
 157
 158         changed = true;
 159         HMAP_FOR_EACH_SAFE (row, next_row, struct ovsdb_idl_row, hmap_node,
 160                             &table->rows) {
 161             struct ovsdb_idl_arc *arc, *next_arc;
 162
 163             if (!ovsdb_idl_row_is_orphan(row)) {
 164                 (row->table->class->unparse)(row);
 165                 ovsdb_idl_row_clear_fields(row);
 166             }
 167             hmap_remove(&table->rows, &row->hmap_node);
 168             LIST_FOR_EACH_SAFE (arc, next_arc, struct ovsdb_idl_arc, src_node,
 169                                 &row->src_arcs) {
 170                 free(arc);
 171             }
 172             /* No need to do anything with dst_arcs: some node has those arcs
 173              * as forward arcs and will destroy them itself. */
 174
 175             free(row);
 176         }
 177     }
 178
 179     if (changed) {
 180         idl->change_seqno++;
 181     }
 182 }
 183
 184 void
 185 ovsdb_idl_run(struct ovsdb_idl *idl)
 186 {
 187     int i;
 188
 189     jsonrpc_session_run(idl->session);
 190     for (i = 0; jsonrpc_session_is_connected(idl->session) && i < 50; i++) {
 191         struct jsonrpc_msg *msg, *reply;
 192         unsigned int seqno;
 193
 194         seqno = jsonrpc_session_get_seqno(idl->session);
 195         if (idl->last_monitor_request_seqno != seqno) {
 196             idl->last_monitor_request_seqno = seqno;
 197             ovsdb_idl_send_monitor_request(idl);
 198             break;
 199         }
 200
 201         msg = jsonrpc_session_recv(idl->session);
 202         if (!msg) {
 203             break;
 204         }
 205
 206         reply = NULL;
 207         if (msg->type == JSONRPC_REQUEST && !strcmp(msg->method, "echo")) {
 208             reply = jsonrpc_create_reply(json_clone(msg->params), msg->id);
 209         } else if (msg->type == JSONRPC_NOTIFY
 210                    && !strcmp(msg->method, "update")
 211                    && msg->params->type == JSON_ARRAY
 212                    && msg->params->u.array.n == 2
 213                    && msg->params->u.array.elems[0]->type == JSON_NULL) {
 214             ovsdb_idl_parse_update(idl, msg->params->u.array.elems[1]);
 215         } else if (msg->type == JSONRPC_REPLY
 216                    && idl->monitor_request_id
 217                    && json_equal(idl->monitor_request_id, msg->id)) {
 218             json_destroy(idl->monitor_request_id);
 219             idl->monitor_request_id = NULL;
 220             ovsdb_idl_clear(idl);
 221             ovsdb_idl_parse_update(idl, msg->result);
 222         } else if (msg->type == JSONRPC_REPLY
 223                    && msg->id && msg->id->type == JSON_STRING
 224                    && !strcmp(msg->id->u.string, "echo")) {
 225             /* It's a reply to our echo request.  Ignore it. */
 226         } else {
 227             VLOG_WARN("%s: received unexpected %s message",
 228                       jsonrpc_session_get_name(idl->session),
 229                       jsonrpc_msg_type_to_string(msg->type));
 230             jsonrpc_session_force_reconnect(idl->session);
 231         }
 232         if (reply) {
 233             jsonrpc_session_send(idl->session, reply);
 234         }
 235         jsonrpc_msg_destroy(msg);
 236     }
 237 }
 238
 239 void
 240 ovsdb_idl_wait(struct ovsdb_idl *idl)
 241 {
 242     jsonrpc_session_wait(idl->session);
 243     jsonrpc_session_recv_wait(idl->session);
 244 }
 245
 246 unsigned int
 247 ovsdb_idl_get_seqno(const struct ovsdb_idl *idl)
 248 {
 249     return idl->change_seqno;
 250 }
 251
 252 void
 253 ovsdb_idl_force_reconnect(struct ovsdb_idl *idl)
 254 {
 255     jsonrpc_session_force_reconnect(idl->session);
 256 }
 257 \f
 258 static void
 259 ovsdb_idl_send_monitor_request(struct ovsdb_idl *idl)
 260 {
 261     struct json *monitor_requests;
 262     const struct shash_node *node;
 263     struct jsonrpc_msg *msg;
 264
 265     monitor_requests = json_object_create();
 266     SHASH_FOR_EACH (node, &idl->tables) {
 267         const struct ovsdb_idl_table *table = node->data;
 268         const struct ovsdb_idl_table_class *tc = table->class;
 269         struct json *monitor_request, *columns;
 270         size_t i;
 271
 272         monitor_request = json_object_create();
 273         columns = json_array_create_empty();
 274         for (i = 0; i < tc->n_columns; i++) {
 275             const struct ovsdb_idl_column *column = &tc->columns[i];
 276             json_array_add(columns, json_string_create(column->name));
 277         }
 278         json_object_put(monitor_request, "columns", columns);
 279         json_object_put(monitor_requests, tc->name, monitor_request);
 280     }
 281
 282     json_destroy(idl->monitor_request_id);
 283     msg = jsonrpc_create_request(
 284         "monitor", json_array_create_2(json_null_create(), monitor_requests),
 285         &idl->monitor_request_id);
 286     jsonrpc_session_send(idl->session, msg);
 287 }
 288
 289 static void
 290 ovsdb_idl_parse_update(struct ovsdb_idl *idl, const struct json *table_updates)
 291 {
 292     struct ovsdb_error *error;
 293
 294     idl->change_seqno++;
 295
 296     error = ovsdb_idl_parse_update__(idl, table_updates);
 297     if (error) {
 298         if (!VLOG_DROP_WARN(&syntax_rl)) {
 299             char *s = ovsdb_error_to_string(error);
 300             VLOG_WARN_RL(&syntax_rl, "%s", s);
 301             free(s);
 302         }
 303         ovsdb_error_destroy(error);
 304     }
 305 }
 306
 307 static struct ovsdb_error *
 308 ovsdb_idl_parse_update__(struct ovsdb_idl *idl,
 309                          const struct json *table_updates)
 310 {
 311     const struct shash_node *tables_node;
 312
 313     if (table_updates->type != JSON_OBJECT) {
 314         return ovsdb_syntax_error(table_updates, NULL,
 315                                   "<table-updates> is not an object");
 316     }
 317     SHASH_FOR_EACH (tables_node, json_object(table_updates)) {
 318         const struct json *table_update = tables_node->data;
 319         const struct shash_node *table_node;
 320         struct ovsdb_idl_table *table;
 321
 322         table = shash_find_data(&idl->tables, tables_node->name);
 323         if (!table) {
 324             return ovsdb_syntax_error(
 325                 table_updates, NULL,
 326                 "<table-updates> includes unknown table \"%s\"",
 327                 tables_node->name);
 328         }
 329
 330         if (table_update->type != JSON_OBJECT) {
 331             return ovsdb_syntax_error(table_update, NULL,
 332                                       "<table-update> for table \"%s\" is "
 333                                       "not an object", table->class->name);
 334         }
 335         SHASH_FOR_EACH (table_node, json_object(table_update)) {
 336             const struct json *row_update = table_node->data;
 337             const struct json *old_json, *new_json;
 338             struct uuid uuid;
 339
 340             if (!uuid_from_string(&uuid, table_node->name)) {
 341                 return ovsdb_syntax_error(table_update, NULL,
 342                                           "<table-update> for table \"%s\" "
 343                                           "contains bad UUID "
 344                                           "\"%s\" as member name",
 345                                           table->class->name,
 346                                           table_node->name);
 347             }
 348             if (row_update->type != JSON_OBJECT) {
 349                 return ovsdb_syntax_error(row_update, NULL,
 350                                           "<table-update> for table \"%s\" "
 351                                           "contains <row-update> for %s that "
 352                                           "is not an object",
 353                                           table->class->name,
 354                                           table_node->name);
 355             }
 356
 357             old_json = shash_find_data(json_object(row_update), "old");
 358             new_json = shash_find_data(json_object(row_update), "new");
 359             if (old_json && old_json->type != JSON_OBJECT) {
 360                 return ovsdb_syntax_error(old_json, NULL,
 361                                           "\"old\" <row> is not object");
 362             } else if (new_json && new_json->type != JSON_OBJECT) {
 363                 return ovsdb_syntax_error(new_json, NULL,
 364                                           "\"new\" <row> is not object");
 365             } else if ((old_json != NULL) + (new_json != NULL)
 366                        != shash_count(json_object(row_update))) {
 367                 return ovsdb_syntax_error(row_update, NULL,
 368                                           "<row-update> contains unexpected "
 369                                           "member");
 370             } else if (!old_json && !new_json) {
 371                 return ovsdb_syntax_error(row_update, NULL,
 372                                           "<row-update> missing \"old\" "
 373                                           "and \"new\" members");
 374             }
 375
 376             ovsdb_idl_process_update(table, &uuid, old_json, new_json);
 377         }
 378     }
 379
 380     return NULL;
 381 }
 382
 383 static struct ovsdb_idl_row *
 384 ovsdb_idl_get_row(struct ovsdb_idl_table *table, const struct uuid *uuid)
 385 {
 386     struct ovsdb_idl_row *row;
 387
 388     HMAP_FOR_EACH_WITH_HASH (row, struct ovsdb_idl_row, hmap_node,
 389                              uuid_hash(uuid), &table->rows) {
 390         if (uuid_equals(&row->uuid, uuid)) {
 391             return row;
 392         }
 393     }
 394     return NULL;
 395 }
 396
 397 static void
 398 ovsdb_idl_process_update(struct ovsdb_idl_table *table,
 399                          const struct uuid *uuid, const struct json *old,
 400                          const struct json *new)
 401 {
 402     struct ovsdb_idl_row *row;
 403
 404     row = ovsdb_idl_get_row(table, uuid);
 405     if (!new) {
 406         /* Delete row. */
 407         if (row && !ovsdb_idl_row_is_orphan(row)) {
 408             /* XXX perhaps we should check the 'old' values? */
 409             ovsdb_idl_delete_row(row);
 410         } else {
 411             VLOG_WARN_RL(&semantic_rl, "cannot delete missing row "UUID_FMT" "
 412                          "from table %s",
 413                          UUID_ARGS(uuid), table->class->name);
 414         }
 415     } else if (!old) {
 416         /* Insert row. */
 417         if (!row) {
 418             ovsdb_idl_insert_row(ovsdb_idl_row_create(table, uuid), new);
 419         } else if (ovsdb_idl_row_is_orphan(row)) {
 420             ovsdb_idl_insert_row(row, new);
 421         } else {
 422             VLOG_WARN_RL(&semantic_rl, "cannot add existing row "UUID_FMT" to "
 423                          "table %s", UUID_ARGS(uuid), table->class->name);
 424             ovsdb_idl_modify_row(row, new);
 425         }
 426     } else {
 427         /* Modify row. */
 428         if (row) {
 429             /* XXX perhaps we should check the 'old' values? */
 430             if (!ovsdb_idl_row_is_orphan(row)) {
 431                 ovsdb_idl_modify_row(row, new);
 432             } else {
 433                 VLOG_WARN_RL(&semantic_rl, "cannot modify missing but "
 434                              "referenced row "UUID_FMT" in table %s",
 435                              UUID_ARGS(uuid), table->class->name);
 436                 ovsdb_idl_insert_row(row, new);
 437             }
 438         } else {
 439             VLOG_WARN_RL(&semantic_rl, "cannot modify missing row "UUID_FMT" "
 440                          "in table %s", UUID_ARGS(uuid), table->class->name);
 441             ovsdb_idl_insert_row(ovsdb_idl_row_create(table, uuid), new);
 442         }
 443     }
 444 }
 445
 446 static void
 447 ovsdb_idl_row_update(struct ovsdb_idl_row *row, const struct json *row_json)
 448 {
 449     struct ovsdb_idl_table *table = row->table;
 450     struct shash_node *node;
 451
 452     SHASH_FOR_EACH (node, json_object(row_json)) {
 453         const char *column_name = node->name;
 454         const struct ovsdb_idl_column *column;
 455         struct ovsdb_datum datum;
 456         struct ovsdb_error *error;
 457
 458         column = shash_find_data(&table->columns, column_name);
 459         if (!column) {
 460             VLOG_WARN_RL(&syntax_rl, "unknown column %s updating row "UUID_FMT,
 461                          column_name, UUID_ARGS(&row->uuid));
 462             continue;
 463         }
 464
 465         error = ovsdb_datum_from_json(&datum, &column->type, node->data, NULL);
 466         if (!error) {
 467             ovsdb_datum_swap(&row->fields[column - table->class->columns],
 468                              &datum);
 469             ovsdb_datum_destroy(&datum, &column->type);
 470         } else {
 471             char *s = ovsdb_error_to_string(error);
 472             VLOG_WARN_RL(&syntax_rl, "error parsing column %s in row "UUID_FMT
 473                          " in table %s: %s", column_name,
 474                          UUID_ARGS(&row->uuid), table->class->name, s);
 475             free(s);
 476             ovsdb_error_destroy(error);
 477         }
 478     }
 479 }
 480
 481 static bool
 482 ovsdb_idl_row_is_orphan(const struct ovsdb_idl_row *row)
 483 {
 484     return !row->fields;
 485 }
 486
 487 static void
 488 ovsdb_idl_row_clear_fields(struct ovsdb_idl_row *row)
 489 {
 490     if (!ovsdb_idl_row_is_orphan(row)) {
 491         const struct ovsdb_idl_table_class *class = row->table->class;
 492         size_t i;
 493
 494         for (i = 0; i < class->n_columns; i++) {
 495             ovsdb_datum_destroy(&row->fields[i], &class->columns[i].type);
 496         }
 497         row->fields = NULL;
 498     }
 499 }
 500
 501 static void
 502 ovsdb_idl_row_clear_arcs(struct ovsdb_idl_row *row, bool destroy_dsts)
 503 {
 504     struct ovsdb_idl_arc *arc, *next;
 505
 506     /* Delete all forward arcs.  If 'destroy_dsts', destroy any orphaned rows
 507      * that this causes to be unreferenced. */
 508     LIST_FOR_EACH_SAFE (arc, next, struct ovsdb_idl_arc, src_node,
 509                         &row->src_arcs) {
 510         list_remove(&arc->dst_node);
 511         if (destroy_dsts
 512             && ovsdb_idl_row_is_orphan(arc->dst)
 513             && list_is_empty(&arc->dst->dst_arcs)) {
 514             ovsdb_idl_row_destroy(arc->dst);
 515         }
 516         free(arc);
 517     }
 518     list_init(&row->src_arcs);
 519 }
 520
 521 /* Force nodes that reference 'row' to reparse. */
 522 static void
 523 ovsdb_idl_row_reparse_backrefs(struct ovsdb_idl_row *row, bool destroy_dsts)
 524 {
 525     struct ovsdb_idl_arc *arc, *next;
 526
 527     /* This is trickier than it looks.  ovsdb_idl_row_clear_arcs() will destroy
 528      * 'arc', so we need to use the "safe" variant of list traversal.  However,
 529      * calling ref->table->class->parse will add an arc equivalent to 'arc' to
 530      * row->arcs.  That could be a problem for traversal, but it adds it at the
 531      * beginning of the list to prevent us from stumbling upon it again.
 532      *
 533      * (If duplicate arcs were possible then we would need to make sure that
 534      * 'next' didn't also point into 'arc''s destination, but we forbid
 535      * duplicate arcs.) */
 536     LIST_FOR_EACH_SAFE (arc, next, struct ovsdb_idl_arc, dst_node,
 537                         &row->dst_arcs) {
 538         struct ovsdb_idl_row *ref = arc->src;
 539
 540         (ref->table->class->unparse)(ref);
 541         ovsdb_idl_row_clear_arcs(ref, destroy_dsts);
 542         (ref->table->class->parse)(ref);
 543     }
 544 }
 545
 546 static struct ovsdb_idl_row *
 547 ovsdb_idl_row_create(struct ovsdb_idl_table *table, const struct uuid *uuid)
 548 {
 549     struct ovsdb_idl_row *row = xmalloc(table->class->allocation_size);
 550     hmap_insert(&table->rows, &row->hmap_node, uuid_hash(uuid));
 551     row->uuid = *uuid;
 552     list_init(&row->src_arcs);
 553     list_init(&row->dst_arcs);
 554     row->table = table;
 555     row->fields = NULL;
 556     return row;
 557 }
 558
 559 static void
 560 ovsdb_idl_row_destroy(struct ovsdb_idl_row *row)
 561 {
 562     if (row) {
 563         ovsdb_idl_row_clear_fields(row);
 564         hmap_remove(&row->table->rows, &row->hmap_node);
 565         free(row);
 566     }
 567 }
 568
 569 static void
 570 ovsdb_idl_insert_row(struct ovsdb_idl_row *row, const struct json *row_json)
 571 {
 572     const struct ovsdb_idl_table_class *class = row->table->class;
 573     size_t i;
 574
 575     assert(!row->fields);
 576     row->fields = xmalloc(class->n_columns * sizeof *row->fields);
 577     for (i = 0; i < class->n_columns; i++) {
 578         ovsdb_datum_init_default(&row->fields[i], &class->columns[i].type);
 579     }
 580     ovsdb_idl_row_update(row, row_json);
 581     (class->parse)(row);
 582
 583     ovsdb_idl_row_reparse_backrefs(row, false);
 584 }
 585
 586 static void
 587 ovsdb_idl_delete_row(struct ovsdb_idl_row *row)
 588 {
 589     (row->table->class->unparse)(row);
 590     ovsdb_idl_row_clear_arcs(row, true);
 591     ovsdb_idl_row_clear_fields(row);
 592     if (list_is_empty(&row->dst_arcs)) {
 593         ovsdb_idl_row_destroy(row);
 594     } else {
 595         ovsdb_idl_row_reparse_backrefs(row, true);
 596     }
 597 }
 598
 599 static void
 600 ovsdb_idl_modify_row(struct ovsdb_idl_row *row, const struct json *row_json)
 601 {
 602     (row->table->class->unparse)(row);
 603     ovsdb_idl_row_clear_arcs(row, true);
 604     ovsdb_idl_row_update(row, row_json);
 605     (row->table->class->parse)(row);
 606 }
 607
 608 static bool
 609 may_add_arc(const struct ovsdb_idl_row *src, const struct ovsdb_idl_row *dst)
 610 {
 611     const struct ovsdb_idl_arc *arc;
 612
 613     /* No self-arcs. */
 614     if (src == dst) {
 615         return false;
 616     }
 617
 618     /* No duplicate arcs.
 619      *
 620      * We only need to test whether the first arc in dst->dst_arcs originates
 621      * at 'src', since we add all of the arcs from a given source in a clump
 622      * (in a single call to a row's ->parse function) and new arcs are always
 623      * added at the front of the dst_arcs list. */
 624     if (list_is_empty(&dst->dst_arcs)) {
 625         return true;
 626     }
 627     arc = CONTAINER_OF(dst->dst_arcs.next, struct ovsdb_idl_arc, dst_node);
 628     return arc->src != src;
 629 }
 630
 631 struct ovsdb_idl_row *
 632 ovsdb_idl_get_row_arc(struct ovsdb_idl_row *src,
 633                       struct ovsdb_idl_table_class *dst_table_class,
 634                       const struct uuid *dst_uuid)
 635 {
 636     struct ovsdb_idl *idl = src->table->idl;
 637     struct ovsdb_idl_arc *arc;
 638     struct ovsdb_idl_row *dst;
 639
 640     dst = ovsdb_idl_get_row(src->table, dst_uuid);
 641     if (!dst) {
 642         struct ovsdb_idl_table *dst_table;
 643         dst_table = shash_find_data(&idl->tables, dst_table_class->name);
 644         dst = ovsdb_idl_row_create(dst_table, dst_uuid);
 645     }
 646
 647     /* Add a new arc, if it wouldn't be a self-arc or a duplicate arc. */
 648     if (may_add_arc(src, dst)) {
 649         /* The arc *must* be added at the front of the dst_arcs list.  See
 650          * ovsdb_idl_row_reparse_backrefs() for details. */
 651         arc = xmalloc(sizeof *arc);
 652         list_push_front(&src->src_arcs, &arc->src_node);
 653         list_push_front(&dst->dst_arcs, &arc->dst_node);
 654         arc->src = src;
 655         arc->dst = dst;
 656     }
 657
 658     return !ovsdb_idl_row_is_orphan(dst) ? dst : NULL;
 659 }
 660
 661 static struct ovsdb_idl_row *
 662 next_real_row(struct ovsdb_idl_table *table, struct hmap_node *node)
 663 {
 664     for (; node; node = hmap_next(&table->rows, node)) {
 665         struct ovsdb_idl_row *row;
 666
 667         row = CONTAINER_OF(node, struct ovsdb_idl_row, hmap_node);
 668         if (!ovsdb_idl_row_is_orphan(row)) {
 669             return row;
 670         }
 671     }
 672     return NULL;
 673 }
 674
 675 struct ovsdb_idl_row *
 676 ovsdb_idl_first_row(const struct ovsdb_idl *idl,
 677                     const struct ovsdb_idl_table_class *table_class)
 678 {
 679     struct ovsdb_idl_table *table;
 680
 681     table = shash_find_data(&idl->tables, table_class->name);
 682     return next_real_row(table, hmap_first(&table->rows));
 683 }
 684
 685 struct ovsdb_idl_row *
 686 ovsdb_idl_next_row(const struct ovsdb_idl_row *row)
 687 {
 688     struct ovsdb_idl_table *table = row->table;
 689
 690     return next_real_row(table, hmap_next(&table->rows, &row->hmap_node));
 691 }