From 17d18afbfd65619e830d551cb002441519cde059 Mon Sep 17 00:00:00 2001 From: Ben Pfaff Date: Thu, 11 Mar 2010 17:14:31 -0800 Subject: [PATCH] ovsdb: Check for changed columns only once per transaction commit. Until now, each part of a transaction commit that is interested in whether a column's value has changed has had to do a comparison of the old and new values itself. There can be several interested parties per commit (generally one for file storage and one for each remove OVSDB connection), so this seems like too much redundancy. This commit adds a bitmap to struct ovsdb_txn_row that tracks whether a column's value has actually changed, to reduce this overhead. As a convenient side effect of doing these checks up front, it then becomes easily possible to drop txn_rows (and txn_tables and entire txns) that become no-ops. (This probably fixes bug #2400, which reported that some no-ops actually report updates over monitors.) --- lib/bitmap.h | 17 +++++++++-- ovsdb/file.c | 15 ++++++---- ovsdb/jsonrpc-server.c | 13 +++++---- ovsdb/transaction.c | 64 ++++++++++++++++++++++++++++++++++++++---- ovsdb/transaction.h | 3 +- 5 files changed, 91 insertions(+), 21 deletions(-) diff --git a/lib/bitmap.h b/lib/bitmap.h index 5b50c9cc..fd05d3da 100644 --- a/lib/bitmap.h +++ b/lib/bitmap.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2008, 2009 Nicira Networks. + * Copyright (c) 2008, 2009, 2010 Nicira Networks. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -35,11 +35,22 @@ bitmap_bit__(size_t offset) return 1UL << (offset % BITMAP_ULONG_BITS); } +static inline size_t +bitmap_n_longs(size_t n_bits) +{ + return DIV_ROUND_UP(n_bits, BITMAP_ULONG_BITS); +} + +static inline size_t +bitmap_n_bytes(size_t n_bits) +{ + return bitmap_n_longs(n_bits) * sizeof(unsigned long int); +} + static inline unsigned long * bitmap_allocate(size_t n_bits) { - size_t n_longs = DIV_ROUND_UP(n_bits, BITMAP_ULONG_BITS); - return xcalloc(sizeof(unsigned long int), n_longs); + return xzalloc(bitmap_n_bytes(n_bits)); } static inline void diff --git a/ovsdb/file.c b/ovsdb/file.c index 65a535b3..c61d5caa 100644 --- a/ovsdb/file.c +++ b/ovsdb/file.c @@ -20,6 +20,7 @@ #include #include +#include "bitmap.h" #include "column.h" #include "log.h" #include "json.h" @@ -45,7 +46,8 @@ struct ovsdb_file_txn { static void ovsdb_file_txn_init(struct ovsdb_file_txn *); static void ovsdb_file_txn_add_row(struct ovsdb_file_txn *, const struct ovsdb_row *old, - const struct ovsdb_row *new); + const struct ovsdb_row *new, + const unsigned long int *changed); static struct ovsdb_error *ovsdb_file_txn_commit(struct json *, const char *comment, bool durable, @@ -352,7 +354,7 @@ ovsdb_file_save_copy(const char *file_name, int locking, const struct ovsdb_row *row; HMAP_FOR_EACH (row, struct ovsdb_row, hmap_node, &table->rows) { - ovsdb_file_txn_add_row(&ftxn, NULL, row); + ovsdb_file_txn_add_row(&ftxn, NULL, row, NULL); } } error = ovsdb_file_txn_commit(ftxn.json, comment, true, log); @@ -394,10 +396,11 @@ ovsdb_file_replica_cast(struct ovsdb_replica *replica) static bool ovsdb_file_replica_change_cb(const struct ovsdb_row *old, const struct ovsdb_row *new, + const unsigned long int *changed, void *ftxn_) { struct ovsdb_file_txn *ftxn = ftxn_; - ovsdb_file_txn_add_row(ftxn, old, new); + ovsdb_file_txn_add_row(ftxn, old, new, changed); return true; } @@ -444,7 +447,8 @@ ovsdb_file_txn_init(struct ovsdb_file_txn *ftxn) static void ovsdb_file_txn_add_row(struct ovsdb_file_txn *ftxn, const struct ovsdb_row *old, - const struct ovsdb_row *new) + const struct ovsdb_row *new, + const unsigned long int *changed) { struct json *row; @@ -461,8 +465,7 @@ ovsdb_file_txn_add_row(struct ovsdb_file_txn *ftxn, if (idx != OVSDB_COL_UUID && column->persistent && (old - ? !ovsdb_datum_equals(&old->fields[idx], &new->fields[idx], - type) + ? bitmap_is_set(changed, idx) : !ovsdb_datum_is_default(&new->fields[idx], type))) { if (!row) { diff --git a/ovsdb/jsonrpc-server.c b/ovsdb/jsonrpc-server.c index e3984647..73c3c1c0 100644 --- a/ovsdb/jsonrpc-server.c +++ b/ovsdb/jsonrpc-server.c @@ -20,6 +20,7 @@ #include #include +#include "bitmap.h" #include "column.h" #include "json.h" #include "jsonrpc.h" @@ -804,6 +805,7 @@ struct ovsdb_jsonrpc_monitor_aux { static bool ovsdb_jsonrpc_monitor_change_cb(const struct ovsdb_row *old, const struct ovsdb_row *new, + const unsigned long int *changed, void *aux_) { struct ovsdb_jsonrpc_monitor_aux *aux = aux_; @@ -841,14 +843,13 @@ ovsdb_jsonrpc_monitor_change_cb(const struct ovsdb_row *old, for (i = 0; i < aux->mt->columns.n_columns; i++) { const struct ovsdb_column *column = aux->mt->columns.columns[i]; unsigned int idx = column->index; - bool changed = false; + bool column_changed = false; if (type == OJMS_MODIFY) { - changed = !ovsdb_datum_equals(&old->fields[idx], - &new->fields[idx], &column->type); - n_changed += changed; + column_changed = bitmap_is_set(changed, idx); + n_changed += column_changed; } - if (changed || type == OJMS_DELETE) { + if (column_changed || type == OJMS_DELETE) { if (!old_json) { old_json = json_object_create(); } @@ -951,7 +952,7 @@ ovsdb_jsonrpc_monitor_get_initial(const struct ovsdb_jsonrpc_monitor *m) HMAP_FOR_EACH (row, struct ovsdb_row, hmap_node, &mt->table->rows) { - ovsdb_jsonrpc_monitor_change_cb(NULL, row, &aux); + ovsdb_jsonrpc_monitor_change_cb(NULL, row, NULL, &aux); } } } diff --git a/ovsdb/transaction.c b/ovsdb/transaction.c index ac9b7f31..8a10d1ed 100644 --- a/ovsdb/transaction.c +++ b/ovsdb/transaction.c @@ -19,6 +19,7 @@ #include +#include "bitmap.h" #include "dynamic-string.h" #include "hash.h" #include "hmap.h" @@ -68,6 +69,8 @@ struct ovsdb_txn_row { /* Used by for_each_txn_row(). */ unsigned int serial; /* Serial number of in-progress commit. */ + + unsigned long changed[]; /* Bits set to 1 for columns that changed. */ }; static void ovsdb_txn_row_prefree(struct ovsdb_txn_row *); @@ -98,7 +101,7 @@ ovsdb_txn_free(struct ovsdb_txn *txn) free(txn); } -static struct ovsdb_error * WARN_UNUSED_RESULT +static struct ovsdb_error * ovsdb_txn_row_abort(struct ovsdb_txn *txn OVS_UNUSED, struct ovsdb_txn_row *txn_row) { @@ -253,7 +256,7 @@ update_ref_counts(struct ovsdb_txn *txn) return for_each_txn_row(txn, check_ref_count); } -static struct ovsdb_error * WARN_UNUSED_RESULT +static struct ovsdb_error * ovsdb_txn_row_commit(struct ovsdb_txn *txn OVS_UNUSED, struct ovsdb_txn_row *txn_row) { @@ -267,18 +270,67 @@ ovsdb_txn_row_commit(struct ovsdb_txn *txn OVS_UNUSED, return NULL; } +static struct ovsdb_error * WARN_UNUSED_RESULT +determine_changes(struct ovsdb_txn *txn, struct ovsdb_txn_row *txn_row) +{ + struct ovsdb_table *table; + + table = (txn_row->old ? txn_row->old : txn_row->new)->table; + if (txn_row->old && txn_row->new) { + struct shash_node *node; + bool changed = false; + + SHASH_FOR_EACH (node, &table->schema->columns) { + const struct ovsdb_column *column = node->data; + const struct ovsdb_type *type = &column->type; + unsigned int idx = column->index; + + if (!ovsdb_datum_equals(&txn_row->old->fields[idx], + &txn_row->new->fields[idx], + type)) { + bitmap_set1(txn_row->changed, idx); + changed = true; + } + } + + if (!changed) { + /* Nothing actually changed in this row, so drop it. */ + ovsdb_txn_row_abort(txn, txn_row); + } + } else { + bitmap_set_multiple(txn_row->changed, 0, + shash_count(&table->schema->columns), 1); + } + + return NULL; +} + struct ovsdb_error * ovsdb_txn_commit(struct ovsdb_txn *txn, bool durable) { struct ovsdb_replica *replica; struct ovsdb_error *error; + /* Figure out what actually changed, and abort early if the transaction + * was really a no-op. */ + error = for_each_txn_row(txn, determine_changes); + if (error) { + ovsdb_error_destroy(error); + return OVSDB_BUG("can't happen"); + } + if (list_is_empty(&txn->txn_tables)) { + ovsdb_txn_abort(txn); + return NULL; + } + + /* Update reference counts and check referential integrity. */ error = update_ref_counts(txn); if (error) { ovsdb_txn_abort(txn); return error; } + /* Send the commit to each replica. */ LIST_FOR_EACH (replica, struct ovsdb_replica, node, &txn->db->replicas) { error = (replica->class->commit)(replica, txn, durable); if (error) { @@ -308,7 +360,7 @@ ovsdb_txn_for_each_change(const struct ovsdb_txn *txn, LIST_FOR_EACH (t, struct ovsdb_txn_table, node, &txn->txn_tables) { HMAP_FOR_EACH (r, struct ovsdb_txn_row, hmap_node, &t->txn_rows) { - if (!cb(r->old, r->new, aux)) { + if (!cb(r->old, r->new, r->changed, aux)) { break; } } @@ -335,11 +387,13 @@ ovsdb_txn_row_create(struct ovsdb_txn *txn, struct ovsdb_table *table, const struct ovsdb_row *old_, struct ovsdb_row *new) { struct ovsdb_row *old = (struct ovsdb_row *) old_; + size_t n_columns = shash_count(&table->schema->columns); struct ovsdb_txn_table *txn_table; struct ovsdb_txn_row *txn_row; - txn_row = xmalloc(sizeof *txn_row); - txn_row->old = old; + txn_row = xzalloc(offsetof(struct ovsdb_txn_row, changed) + + bitmap_n_bytes(n_columns)); + txn_row->old = (struct ovsdb_row *) old; txn_row->new = new; txn_row->n_refs = old ? old->n_refs : 0; txn_row->serial = serial - 1; diff --git a/ovsdb/transaction.h b/ovsdb/transaction.h index 1c54ec3a..414b358b 100644 --- a/ovsdb/transaction.h +++ b/ovsdb/transaction.h @@ -1,4 +1,4 @@ -/* Copyright (c) 2009 Nicira Networks +/* Copyright (c) 2009, 2010 Nicira Networks * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -35,6 +35,7 @@ void ovsdb_txn_row_delete(struct ovsdb_txn *, const struct ovsdb_row *); typedef bool ovsdb_txn_row_cb_func(const struct ovsdb_row *old, const struct ovsdb_row *new, + const unsigned long int *changed, void *aux); void ovsdb_txn_for_each_change(const struct ovsdb_txn *, ovsdb_txn_row_cb_func *, void *aux); -- 2.30.2