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