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