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