ovsdb/condition.c

   1 /* Copyright (c) 2009, 2010, 2011 Nicira, Inc.
   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 "condition.h"
  19
  20 #include <limits.h>
  21
  22 #include "column.h"
  23 #include "openvswitch/json.h"
  24 #include "ovsdb-error.h"
  25 #include "row.h"
  26
  27 #include <string.h>
  28
  29 #include "table.h"
  30 #include "util.h"
  31
  32 static struct ovsdb_error *
  33 ovsdb_clause_from_json(const struct ovsdb_table_schema *ts,
  34                        const struct json *json,
  35                        struct ovsdb_symbol_table *symtab,
  36                        struct ovsdb_clause *clause)
  37 {
  38     const struct json_array *array;
  39     struct ovsdb_error *error;
  40     const char *function_name;
  41     const char *column_name;
  42     struct ovsdb_type type;
  43
  44     if (json->type == JSON_TRUE || json->type == JSON_FALSE) {
  45         clause->function =
  46             json->type == JSON_TRUE ? OVSDB_F_TRUE : OVSDB_F_FALSE;
  47
  48         /* Column and arg fields are not being used with boolean functions.
  49          * Use dummy values */
  50         clause->column = ovsdb_table_schema_get_column(ts, "_uuid");
  51         clause->index = clause->column->index;
  52         ovsdb_datum_init_default(&clause->arg, &clause->column->type);
  53         return NULL;
  54     }
  55
  56     if (json->type != JSON_ARRAY
  57         || json->array.n != 3
  58         || json->array.elems[0]->type != JSON_STRING
  59         || json->array.elems[1]->type != JSON_STRING) {
  60         return ovsdb_syntax_error(json, NULL, "Parse error in condition.");
  61     }
  62     array = json_array(json);
  63
  64     column_name = json_string(array->elems[0]);
  65     clause->column = ovsdb_table_schema_get_column(ts, column_name);
  66     if (!clause->column) {
  67         return ovsdb_syntax_error(json, "unknown column",
  68                                   "No column %s in table %s.",
  69                                   column_name, ts->name);
  70     }
  71     clause->index = clause->column->index;
  72     type = clause->column->type;
  73
  74     function_name = json_string(array->elems[1]);
  75     error = ovsdb_function_from_string(function_name, &clause->function);
  76     if (error) {
  77         return error;
  78     }
  79
  80     /* Type-check and relax restrictions on 'type' if appropriate.  */
  81     switch (clause->function) {
  82     case OVSDB_F_LT:
  83     case OVSDB_F_LE:
  84     case OVSDB_F_GT:
  85     case OVSDB_F_GE:
  86         /* Allow these operators for types with n_min == 0, n_max == 1.
  87          * (They will always be "false" if the value is missing.) */
  88         if (!(ovsdb_type_is_scalar(&type)
  89             || ovsdb_type_is_optional_scalar(&type))
  90             || (type.key.type != OVSDB_TYPE_INTEGER
  91                 && type.key.type != OVSDB_TYPE_REAL)) {
  92             char *s = ovsdb_type_to_english(&type);
  93             error = ovsdb_syntax_error(
  94                 json, NULL, "Type mismatch: \"%s\" operator may not be "
  95                 "applied to column %s of type %s.",
  96                 ovsdb_function_to_string(clause->function),
  97                 clause->column->name, s);
  98             free(s);
  99             return error;
 100         }
 101
 102         /* Force the argument to be a scalar. */
 103         type.n_min = 1;
 104
 105         break;
 106
 107     case OVSDB_F_EQ:
 108     case OVSDB_F_NE:
 109         break;
 110
 111     case OVSDB_F_EXCLUDES:
 112         if (!ovsdb_type_is_scalar(&type)) {
 113             type.n_min = 0;
 114             type.n_max = UINT_MAX;
 115         }
 116         break;
 117
 118     case OVSDB_F_INCLUDES:
 119         if (!ovsdb_type_is_scalar(&type)) {
 120             type.n_min = 0;
 121         }
 122         break;
 123     case OVSDB_F_TRUE:
 124     case OVSDB_F_FALSE:
 125         OVS_NOT_REACHED();
 126     }
 127     return ovsdb_datum_from_json(&clause->arg, &type, array->elems[2], symtab);
 128 }
 129
 130 static void
 131 ovsdb_clause_free(struct ovsdb_clause *clause)
 132 {
 133     ovsdb_datum_destroy(&clause->arg, &clause->column->type);
 134 }
 135
 136 static int
 137 compare_clauses_3way(const void *a_, const void *b_)
 138 {
 139     const struct ovsdb_clause *a = a_;
 140     const struct ovsdb_clause *b = b_;
 141
 142     if (a->function != b->function) {
 143         /* Bring functions to the front based on the fraction of table rows
 144          * that they are (heuristically) expected to leave in the query
 145          * results.  Note that "enum ovsdb_function" is intentionally ordered
 146          * to make this trivial. */
 147         return a->function < b->function ? -1 : 1;
 148     } else if (a->column->index != b->column->index) {
 149         if (a->column->index < OVSDB_N_STD_COLUMNS
 150             || b->column->index < OVSDB_N_STD_COLUMNS) {
 151             /* Bring the standard columns and in particular the UUID column
 152              * (since OVSDB_COL_UUID has value 0) to the front.  We have an
 153              * index on the UUID column, so that makes our queries cheaper. */
 154             return a->column->index < b->column->index ? -1 : 1;
 155         } else {
 156             /* Order clauses predictably to make testing easier. */
 157             return strcmp(a->column->name, b->column->name);
 158         }
 159     } else {
 160         return 0;
 161     }
 162 }
 163
 164 static int
 165 compare_clauses_3way_with_data(const void *a_, const void *b_)
 166 {
 167     const struct ovsdb_clause *a = a_;
 168     const struct ovsdb_clause *b = b_;
 169     int res;
 170
 171     res = compare_clauses_3way(a, b);
 172     return res ? res : ovsdb_datum_compare_3way(&a->arg,
 173                                                 &b->arg,
 174                                                 &a->column->type);
 175  }
 176
 177 struct ovsdb_o_column {
 178     const struct ovsdb_column *column;
 179     struct hmap o_clauses;
 180 };
 181
 182 struct ovsdb_o_clause {
 183     struct ovsdb_datum *arg;
 184     struct hmap_node hmap_node;
 185 };
 186
 187 static void
 188 ovsdb_condition_optimize(struct ovsdb_condition *cnd)
 189 {
 190     size_t i;
 191     uint32_t hash;
 192
 193     if (!cnd->optimized) {
 194         return;
 195     }
 196
 197     for(i = 0; i < cnd->n_clauses; i++) {
 198         struct ovsdb_clause *clause = &cnd->clauses[i];
 199
 200         if (clause->function != OVSDB_F_EQ) {
 201             continue;
 202         }
 203
 204         struct ovsdb_o_clause *o_clause = xzalloc(sizeof *o_clause);
 205         struct ovsdb_o_column *o_column =
 206             shash_find_data(&cnd->o_columns, clause->column->name);
 207
 208         if (!o_column) {
 209             o_column = xzalloc(sizeof *o_column);
 210             o_column->column = clause->column;
 211             hmap_init(&o_column->o_clauses);
 212             shash_add(&cnd->o_columns, clause->column->name, o_column);
 213         }
 214         o_clause->arg = &clause->arg;
 215         hash = ovsdb_datum_hash(&clause->arg, &clause->column->type, 0);
 216         hmap_insert(&o_column->o_clauses, &o_clause->hmap_node, hash);
 217     }
 218 }
 219
 220 static void
 221 ovsdb_condition_optimize_destroy(struct ovsdb_condition *cnd)
 222 {
 223      struct shash_node *node, *next;
 224
 225      SHASH_FOR_EACH_SAFE (node, next, &cnd->o_columns) {
 226          struct ovsdb_o_column *o_column = node->data;
 227          struct ovsdb_o_clause *c, *c_next;
 228
 229          HMAP_FOR_EACH_SAFE(c, c_next, hmap_node, &o_column->o_clauses) {
 230              hmap_remove(&o_column->o_clauses, &c->hmap_node);
 231              free(c);
 232          }
 233          hmap_destroy(&o_column->o_clauses);
 234          shash_delete(&cnd->o_columns, node);
 235          free(o_column);
 236      }
 237      shash_destroy(&cnd->o_columns);
 238 }
 239
 240 struct ovsdb_error *
 241 ovsdb_condition_from_json(const struct ovsdb_table_schema *ts,
 242                           const struct json *json,
 243                           struct ovsdb_symbol_table *symtab,
 244                           struct ovsdb_condition *cnd)
 245 {
 246     const struct json_array *array = json_array(json);
 247     size_t i;
 248
 249     ovsdb_condition_init(cnd);
 250     cnd->clauses = xmalloc(array->n * sizeof *cnd->clauses);
 251
 252     for (i = 0; i < array->n; i++) {
 253         struct ovsdb_error *error;
 254         error = ovsdb_clause_from_json(ts, array->elems[i], symtab,
 255                                        &cnd->clauses[i]);
 256         if (error) {
 257             ovsdb_condition_destroy(cnd);
 258             cnd->clauses = NULL;
 259             cnd->n_clauses = 0;
 260             return error;
 261         }
 262         cnd->n_clauses++;
 263         if (cnd->clauses[i].function > OVSDB_F_EQ) {
 264             cnd->optimized = false;
 265         }
 266     }
 267
 268     /* A real database would have a query optimizer here. */
 269     qsort(cnd->clauses, cnd->n_clauses, sizeof *cnd->clauses,
 270           compare_clauses_3way_with_data);
 271
 272     ovsdb_condition_optimize(cnd);
 273
 274     return NULL;
 275 }
 276
 277 static struct json *
 278 ovsdb_clause_to_json(const struct ovsdb_clause *clause)
 279 {
 280     if (clause->function != OVSDB_F_TRUE &&
 281         clause->function != OVSDB_F_FALSE) {
 282         return json_array_create_3(
 283                 json_string_create(clause->column->name),
 284                 json_string_create(ovsdb_function_to_string(clause->function)),
 285                 ovsdb_datum_to_json(&clause->arg, &clause->column->type));
 286     }
 287
 288     return json_boolean_create(clause->function == OVSDB_F_TRUE);
 289 }
 290
 291 struct json *
 292 ovsdb_condition_to_json(const struct ovsdb_condition *cnd)
 293 {
 294     struct json **clauses;
 295     size_t i;
 296
 297     clauses = xmalloc(cnd->n_clauses * sizeof *clauses);
 298     for (i = 0; i < cnd->n_clauses; i++) {
 299         clauses[i] = ovsdb_clause_to_json(&cnd->clauses[i]);
 300     }
 301     return json_array_create(clauses, cnd->n_clauses);
 302 }
 303
 304 static bool
 305 ovsdb_clause_evaluate(const struct ovsdb_datum *fields,
 306                       const struct ovsdb_clause *c,
 307                       unsigned int index_map[])
 308 {
 309     const struct ovsdb_datum *field = &fields[index_map ?
 310                                               index_map[c->column->index] :
 311                                               c->column->index];
 312     const struct ovsdb_datum *arg = &c->arg;
 313     const struct ovsdb_type *type = &c->column->type;
 314
 315     if (c->function == OVSDB_F_TRUE ||
 316         c->function == OVSDB_F_FALSE) {
 317         return c->function == OVSDB_F_TRUE;
 318     }
 319     if (ovsdb_type_is_optional_scalar(type)
 320         && field->n == 0
 321         && (c->function == OVSDB_F_LT ||
 322             c->function == OVSDB_F_LE ||
 323             c->function == OVSDB_F_GT ||
 324             c->function == OVSDB_F_GE)) {
 325         return false;
 326     } else if ((ovsdb_type_is_scalar(type)
 327                 || ovsdb_type_is_optional_scalar(type))
 328                && field->n == 1
 329                && arg->n == 1) {
 330         int cmp = ovsdb_atom_compare_3way(&field->keys[0], &arg->keys[0],
 331                                           type->key.type);
 332         switch (c->function) {
 333         case OVSDB_F_LT:
 334             return cmp < 0;
 335         case OVSDB_F_LE:
 336             return cmp <= 0;
 337         case OVSDB_F_EQ:
 338         case OVSDB_F_INCLUDES:
 339             return cmp == 0;
 340         case OVSDB_F_NE:
 341         case OVSDB_F_EXCLUDES:
 342             return cmp != 0;
 343         case OVSDB_F_GE:
 344             return cmp >= 0;
 345         case OVSDB_F_GT:
 346             return cmp > 0;
 347         case OVSDB_F_TRUE:
 348         case OVSDB_F_FALSE:
 349             OVS_NOT_REACHED();
 350         }
 351     } else {
 352         switch (c->function) {
 353         case OVSDB_F_EQ:
 354             return ovsdb_datum_equals(field, arg, type);
 355         case OVSDB_F_NE:
 356             return !ovsdb_datum_equals(field, arg, type);
 357         case OVSDB_F_INCLUDES:
 358             return ovsdb_datum_includes_all(arg, field, type);
 359         case OVSDB_F_EXCLUDES:
 360             return ovsdb_datum_excludes_all(arg, field, type);
 361         case OVSDB_F_LT:
 362         case OVSDB_F_LE:
 363         case OVSDB_F_GE:
 364         case OVSDB_F_GT:
 365         case OVSDB_F_TRUE:
 366         case OVSDB_F_FALSE:
 367             OVS_NOT_REACHED();
 368         }
 369     }
 370
 371     OVS_NOT_REACHED();
 372 }
 373
 374 static void
 375 ovsdb_clause_clone(struct ovsdb_clause *new, struct ovsdb_clause *old)
 376 {
 377     new->function = old->function;
 378     new->column = old->column;
 379     ovsdb_datum_clone(&new->arg,
 380                       &old->arg,
 381                       &old->column->type);
 382 }
 383
 384 bool
 385 ovsdb_condition_match_every_clause(const struct ovsdb_row *row,
 386                                    const struct ovsdb_condition *cnd)
 387 {
 388     size_t i;
 389
 390     for (i = 0; i < cnd->n_clauses; i++) {
 391         if (!ovsdb_clause_evaluate(row->fields, &cnd->clauses[i], NULL)) {
 392             return false;
 393         }
 394     }
 395
 396     return true;
 397 }
 398
 399 static bool
 400 ovsdb_condition_match_any_clause_optimized(const struct ovsdb_datum *row_datum,
 401                                            const struct ovsdb_condition *cnd,
 402                                            unsigned int index_map[])
 403 {
 404     if (ovsdb_condition_is_true(cnd)) {
 405         return true;
 406     }
 407
 408     struct shash_node *node;
 409     SHASH_FOR_EACH (node, &cnd->o_columns) {
 410         struct ovsdb_o_column *o_column = node->data;
 411         const struct ovsdb_column *column = o_column->column;
 412         const struct ovsdb_datum *arg = &row_datum[index_map ?
 413                                                    index_map[column->index] :
 414                                                    column->index];
 415         uint32_t hash = ovsdb_datum_hash(arg, &column->type, 0);
 416         struct ovsdb_o_clause *o_clause;
 417
 418         HMAP_FOR_EACH_WITH_HASH(o_clause, hmap_node, hash, &o_column->o_clauses) {
 419             if (ovsdb_datum_equals(arg, o_clause->arg, &column->type)) {
 420                 return true;
 421             }
 422         }
 423     }
 424     return false;
 425 }
 426
 427 /* Returns true if condition evaluation of one of the clauses is
 428  * true. index_map[] is an optional array that if exists indicates a mapping
 429  * between indexing row_datum to the indexes in ovsdb_column */
 430 bool
 431 ovsdb_condition_match_any_clause(const struct ovsdb_datum *row_datum,
 432                                  const struct ovsdb_condition *cnd,
 433                                  unsigned int index_map[])
 434 {
 435     size_t i;
 436
 437     if (cnd->optimized) {
 438         return ovsdb_condition_match_any_clause_optimized(row_datum, cnd,
 439                                                           index_map);
 440     }
 441
 442     for (i = 0; i < cnd->n_clauses; i++) {
 443         if (ovsdb_clause_evaluate(row_datum, &cnd->clauses[i], index_map)) {
 444             return true;
 445         }
 446     }
 447
 448     return false;
 449 }
 450
 451 void
 452 ovsdb_condition_destroy(struct ovsdb_condition *cnd)
 453 {
 454     size_t i;
 455
 456     for (i = 0; i < cnd->n_clauses; i++) {
 457         ovsdb_clause_free(&cnd->clauses[i]);
 458     }
 459     free(cnd->clauses);
 460     cnd->n_clauses = 0;
 461
 462     ovsdb_condition_optimize_destroy(cnd);
 463 }
 464
 465 void
 466 ovsdb_condition_init(struct ovsdb_condition *cnd)
 467 {
 468     cnd->clauses = NULL;
 469     cnd->n_clauses = 0;
 470     cnd->optimized = true;
 471     shash_init(&cnd->o_columns);
 472 }
 473
 474 bool
 475 ovsdb_condition_empty(const struct ovsdb_condition *cnd)
 476 {
 477     return cnd->n_clauses == 0;
 478 }
 479
 480 int
 481 ovsdb_condition_cmp_3way(const struct ovsdb_condition *a,
 482                          const struct ovsdb_condition *b)
 483 {
 484     size_t i;
 485     int res;
 486
 487     if (a->n_clauses != b->n_clauses) {
 488         return a->n_clauses < b->n_clauses ? -1 : 1;
 489     }
 490
 491     /* We assume clauses are sorted */
 492     for (i = 0; i < a->n_clauses; i++) {
 493         res = (compare_clauses_3way_with_data(&a->clauses[i], &b->clauses[i]));
 494         if (res != 0) {
 495             return res;
 496         }
 497     }
 498
 499     return 0;
 500 }
 501
 502 void
 503 ovsdb_condition_clone(struct ovsdb_condition *to,
 504                       const struct ovsdb_condition *from)
 505 {
 506     size_t i;
 507
 508     ovsdb_condition_init(to);
 509
 510     to->clauses = xzalloc(from->n_clauses * sizeof *to->clauses);
 511
 512     for (i = 0; i < from->n_clauses; i++) {
 513         ovsdb_clause_clone(&to->clauses[i], &from->clauses[i]);
 514     }
 515     to->n_clauses = from->n_clauses;
 516     to->optimized = from->optimized;
 517     if (to->optimized) {
 518         ovsdb_condition_optimize(to);
 519     }
 520 }
 521
 522 /* Return true if ovsdb_condition_match_any_clause() will return true on
 523  * any row */
 524 bool
 525 ovsdb_condition_is_true(const struct ovsdb_condition *cond)
 526 {
 527     return (!cond->n_clauses ||
 528        (cond->n_clauses >= 1 && (cond->clauses[0].function == OVSDB_F_TRUE)) ||
 529        (cond->n_clauses >= 2 && (cond->clauses[1].function == OVSDB_F_TRUE)));
 530 }
 531
 532 bool
 533 ovsdb_condition_is_false(const struct ovsdb_condition *cond)
 534 {
 535     return ((cond->n_clauses == 1) &&
 536             (cond->clauses[0].function == OVSDB_F_FALSE));
 537  }
 538
 539 const struct ovsdb_column **
 540 ovsdb_condition_get_columns(const struct ovsdb_condition *cond,
 541                             size_t *n_columns)
 542 {
 543     const struct ovsdb_column **columns;
 544     size_t i;
 545
 546     columns = xmalloc(cond->n_clauses * sizeof *columns);
 547     for (i = 0; i < cond->n_clauses; i++) {
 548         columns[i] = cond->clauses[i].column;
 549     }
 550     *n_columns = i;
 551
 552     return columns;
 553 }