ovsdb/mutation.c

   1 /* Copyright (c) 2009, 2010, 2011, 2012 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 "mutation.h"
  19
  20 #include <float.h>
  21 #include <limits.h>
  22
  23 #include "column.h"
  24 #include "ovsdb-error.h"
  25 #include "openvswitch/json.h"
  26 #include "row.h"
  27
  28 #include <string.h>
  29
  30 #include "table.h"
  31 #include "util.h"
  32
  33 struct ovsdb_error *
  34 ovsdb_mutator_from_string(const char *name, enum ovsdb_mutator *mutator)
  35 {
  36 #define OVSDB_MUTATOR(ENUM, NAME)               \
  37     if (!strcmp(name, NAME)) {                  \
  38         *mutator = ENUM;                        \
  39         return NULL;                            \
  40     }
  41     OVSDB_MUTATORS;
  42 #undef OVSDB_MUTATOR
  43
  44     return ovsdb_syntax_error(NULL, "unknown mutator",
  45                               "No mutator named %s.", name);
  46 }
  47
  48 const char *
  49 ovsdb_mutator_to_string(enum ovsdb_mutator mutator)
  50 {
  51     switch (mutator) {
  52 #define OVSDB_MUTATOR(ENUM, NAME) case ENUM: return NAME;
  53         OVSDB_MUTATORS;
  54 #undef OVSDB_MUTATOR
  55     }
  56
  57     return NULL;
  58 }
  59
  60 static OVS_WARN_UNUSED_RESULT struct ovsdb_error *
  61 type_mismatch(const struct ovsdb_mutation *m, const struct json *json)
  62 {
  63     struct ovsdb_error *error;
  64     char *s;
  65
  66     s = ovsdb_type_to_english(&m->column->type);
  67     error = ovsdb_syntax_error(
  68         json, NULL, "Type mismatch: \"%s\" operator may not be "
  69         "applied to column %s of type %s.",
  70         ovsdb_mutator_to_string(m->mutator), m->column->name, s);
  71     free(s);
  72
  73     return error;
  74 }
  75
  76 static OVS_WARN_UNUSED_RESULT struct ovsdb_error *
  77 ovsdb_mutation_from_json(const struct ovsdb_table_schema *ts,
  78                          const struct json *json,
  79                          struct ovsdb_symbol_table *symtab,
  80                          struct ovsdb_mutation *m)
  81 {
  82     const struct json_array *array;
  83     struct ovsdb_error *error;
  84     const char *mutator_name;
  85     const char *column_name;
  86
  87     if (json->type != JSON_ARRAY
  88         || json->array.n != 3
  89         || json->array.elems[0]->type != JSON_STRING
  90         || json->array.elems[1]->type != JSON_STRING) {
  91         return ovsdb_syntax_error(json, NULL, "Parse error in mutation.");
  92     }
  93     array = json_array(json);
  94
  95     column_name = json_string(array->elems[0]);
  96     m->column = ovsdb_table_schema_get_column(ts, column_name);
  97     if (!m->column) {
  98         return ovsdb_syntax_error(json, "unknown column",
  99                                   "No column %s in table %s.",
 100                                   column_name, ts->name);
 101     }
 102     if (!m->column->mutable) {
 103         return ovsdb_syntax_error(json, "constraint violation",
 104                                   "Cannot mutate immutable column %s in "
 105                                   "table %s.", column_name, ts->name);
 106     }
 107
 108     ovsdb_type_clone(&m->type, &m->column->type);
 109
 110     mutator_name = json_string(array->elems[1]);
 111     error = ovsdb_mutator_from_string(mutator_name, &m->mutator);
 112     if (error) {
 113         goto exit;
 114     }
 115
 116     /* Type-check and relax restrictions on 'type' if appropriate.  */
 117     switch (m->mutator) {
 118     case OVSDB_M_ADD:
 119     case OVSDB_M_SUB:
 120     case OVSDB_M_MUL:
 121     case OVSDB_M_DIV:
 122     case OVSDB_M_MOD:
 123         if ((!ovsdb_type_is_scalar(&m->type) && !ovsdb_type_is_set(&m->type))
 124             || (m->type.key.type != OVSDB_TYPE_INTEGER
 125                 && m->type.key.type != OVSDB_TYPE_REAL)
 126             || (m->mutator == OVSDB_M_MOD
 127                 && m->type.key.type == OVSDB_TYPE_REAL)) {
 128             return type_mismatch(m, json);
 129         }
 130         ovsdb_base_type_clear_constraints(&m->type.key);
 131         m->type.n_min = m->type.n_max = 1;
 132         error = ovsdb_datum_from_json(&m->arg, &m->type, array->elems[2],
 133                                       symtab);
 134         break;
 135
 136     case OVSDB_M_INSERT:
 137     case OVSDB_M_DELETE:
 138         if (!ovsdb_type_is_set(&m->type) && !ovsdb_type_is_map(&m->type)) {
 139             return type_mismatch(m, json);
 140         }
 141         m->type.n_min = 0;
 142         if (m->mutator == OVSDB_M_DELETE) {
 143             m->type.n_max = UINT_MAX;
 144         }
 145         error = ovsdb_datum_from_json(&m->arg, &m->type, array->elems[2],
 146                                       symtab);
 147         if (error && ovsdb_type_is_map(&m->type)
 148             && m->mutator == OVSDB_M_DELETE) {
 149             ovsdb_error_destroy(error);
 150             m->type.value.type = OVSDB_TYPE_VOID;
 151             error = ovsdb_datum_from_json(&m->arg, &m->type, array->elems[2],
 152                                           symtab);
 153         }
 154         break;
 155
 156     default:
 157         OVS_NOT_REACHED();
 158     }
 159
 160 exit:
 161     if (error) {
 162         ovsdb_type_destroy(&m->type);
 163     }
 164     return error;
 165 }
 166
 167 static void
 168 ovsdb_mutation_free(struct ovsdb_mutation *m)
 169 {
 170     ovsdb_datum_destroy(&m->arg, &m->type);
 171     ovsdb_type_destroy(&m->type);
 172 }
 173
 174 struct ovsdb_error *
 175 ovsdb_mutation_set_from_json(const struct ovsdb_table_schema *ts,
 176                              const struct json *json,
 177                              struct ovsdb_symbol_table *symtab,
 178                              struct ovsdb_mutation_set *set)
 179 {
 180     const struct json_array *array = json_array(json);
 181     size_t i;
 182
 183     set->mutations = xmalloc(array->n * sizeof *set->mutations);
 184     set->n_mutations = 0;
 185     for (i = 0; i < array->n; i++) {
 186         struct ovsdb_error *error;
 187         error = ovsdb_mutation_from_json(ts, array->elems[i], symtab,
 188                                          &set->mutations[i]);
 189         if (error) {
 190             ovsdb_mutation_set_destroy(set);
 191             set->mutations = NULL;
 192             set->n_mutations = 0;
 193             return error;
 194         }
 195         set->n_mutations++;
 196     }
 197
 198     return NULL;
 199 }
 200
 201 static struct json *
 202 ovsdb_mutation_to_json(const struct ovsdb_mutation *m)
 203 {
 204     return json_array_create_3(
 205         json_string_create(m->column->name),
 206         json_string_create(ovsdb_mutator_to_string(m->mutator)),
 207         ovsdb_datum_to_json(&m->arg, &m->type));
 208 }
 209
 210 struct json *
 211 ovsdb_mutation_set_to_json(const struct ovsdb_mutation_set *set)
 212 {
 213     struct json **mutations;
 214     size_t i;
 215
 216     mutations = xmalloc(set->n_mutations * sizeof *mutations);
 217     for (i = 0; i < set->n_mutations; i++) {
 218         mutations[i] = ovsdb_mutation_to_json(&set->mutations[i]);
 219     }
 220     return json_array_create(mutations, set->n_mutations);
 221 }
 222
 223 void
 224 ovsdb_mutation_set_destroy(struct ovsdb_mutation_set *set)
 225 {
 226     size_t i;
 227
 228     for (i = 0; i < set->n_mutations; i++) {
 229         ovsdb_mutation_free(&set->mutations[i]);
 230     }
 231     free(set->mutations);
 232 }
 233 \f
 234 enum ovsdb_mutation_scalar_error {
 235     ME_OK,
 236     ME_DOM,
 237     ME_RANGE
 238 };
 239
 240 struct ovsdb_scalar_mutation {
 241     int (*mutate_integer)(int64_t *x, int64_t y);
 242     int (*mutate_real)(double *x, double y);
 243     enum ovsdb_mutator mutator;
 244 };
 245
 246 static const struct ovsdb_scalar_mutation add_mutation;
 247 static const struct ovsdb_scalar_mutation sub_mutation;
 248 static const struct ovsdb_scalar_mutation mul_mutation;
 249 static const struct ovsdb_scalar_mutation div_mutation;
 250 static const struct ovsdb_scalar_mutation mod_mutation;
 251
 252 static struct ovsdb_error *
 253 ovsdb_mutation_scalar_error(enum ovsdb_mutation_scalar_error error,
 254                             enum ovsdb_mutator mutator)
 255 {
 256     switch (error) {
 257     case ME_OK:
 258         return OVSDB_BUG("unexpected success");
 259
 260     case ME_DOM:
 261         return ovsdb_error("domain error", "Division by zero.");
 262
 263     case ME_RANGE:
 264         return ovsdb_error("range error",
 265                            "Result of \"%s\" operation is out of range.",
 266                            ovsdb_mutator_to_string(mutator));
 267
 268     default:
 269         return OVSDB_BUG("unexpected error");
 270     }
 271 }
 272
 273 static int
 274 check_real_range(double x)
 275 {
 276     return x >= -DBL_MAX && x <= DBL_MAX ? 0 : ME_RANGE;
 277 }
 278
 279 static struct ovsdb_error *
 280 mutate_scalar(const struct ovsdb_type *dst_type, struct ovsdb_datum *dst,
 281               const union ovsdb_atom *arg,
 282               const struct ovsdb_scalar_mutation *mutation)
 283 {
 284     const struct ovsdb_base_type *base = &dst_type->key;
 285     struct ovsdb_error *error;
 286     unsigned int i;
 287
 288     if (base->type == OVSDB_TYPE_INTEGER) {
 289         int64_t y = arg->integer;
 290         for (i = 0; i < dst->n; i++) {
 291             enum ovsdb_mutation_scalar_error me;
 292
 293             me = (mutation->mutate_integer)(&dst->keys[i].integer, y);
 294             if (me != ME_OK) {
 295                 return ovsdb_mutation_scalar_error(me, mutation->mutator);
 296             }
 297         }
 298     } else if (base->type == OVSDB_TYPE_REAL) {
 299         double y = arg->real;
 300         for (i = 0; i < dst->n; i++) {
 301             double *x = &dst->keys[i].real;
 302             enum ovsdb_mutation_scalar_error me;
 303
 304             me = (mutation->mutate_real)(x, y);
 305             if (me == ME_OK) {
 306                 me = check_real_range(*x);
 307             }
 308             if (me != ME_OK) {
 309                 return ovsdb_mutation_scalar_error(me, mutation->mutator);
 310             }
 311         }
 312     } else {
 313         OVS_NOT_REACHED();
 314     }
 315
 316     for (i = 0; i < dst->n; i++) {
 317         error = ovsdb_atom_check_constraints(&dst->keys[i], base);
 318         if (error) {
 319             return error;
 320         }
 321     }
 322
 323     error = ovsdb_datum_sort(dst, dst_type->key.type);
 324     if (error) {
 325         ovsdb_error_destroy(error);
 326         return ovsdb_error("constraint violation",
 327                            "Result of \"%s\" operation contains duplicates.",
 328                            ovsdb_mutator_to_string(mutation->mutator));
 329     }
 330     return NULL;
 331 }
 332
 333 static struct ovsdb_error *
 334 ovsdb_mutation_check_count(struct ovsdb_datum *dst,
 335                            const struct ovsdb_type *dst_type)
 336 {
 337     if (!ovsdb_datum_conforms_to_type(dst, dst_type)) {
 338         char *s = ovsdb_type_to_english(dst_type);
 339         struct ovsdb_error *e = ovsdb_error(
 340             "constraint violation",
 341             "Attempted to store %u elements in %s.", dst->n, s);
 342         free(s);
 343         return e;
 344     }
 345     return NULL;
 346 }
 347
 348 struct ovsdb_error *
 349 ovsdb_mutation_set_execute(struct ovsdb_row *row,
 350                            const struct ovsdb_mutation_set *set)
 351 {
 352     size_t i;
 353
 354     for (i = 0; i < set->n_mutations; i++) {
 355         const struct ovsdb_mutation *m = &set->mutations[i];
 356         struct ovsdb_datum *dst = &row->fields[m->column->index];
 357         const struct ovsdb_type *dst_type = &m->column->type;
 358         const struct ovsdb_datum *arg = &set->mutations[i].arg;
 359         const struct ovsdb_type *arg_type = &m->type;
 360         struct ovsdb_error *error;
 361
 362         switch (m->mutator) {
 363         case OVSDB_M_ADD:
 364             error = mutate_scalar(dst_type, dst, &arg->keys[0], &add_mutation);
 365             break;
 366
 367         case OVSDB_M_SUB:
 368             error = mutate_scalar(dst_type, dst, &arg->keys[0], &sub_mutation);
 369             break;
 370
 371         case OVSDB_M_MUL:
 372             error = mutate_scalar(dst_type, dst, &arg->keys[0], &mul_mutation);
 373             break;
 374
 375         case OVSDB_M_DIV:
 376             error = mutate_scalar(dst_type, dst, &arg->keys[0], &div_mutation);
 377             break;
 378
 379         case OVSDB_M_MOD:
 380             error = mutate_scalar(dst_type, dst, &arg->keys[0], &mod_mutation);
 381             break;
 382
 383         case OVSDB_M_INSERT:
 384             ovsdb_datum_union(dst, arg, dst_type, false);
 385             error = ovsdb_mutation_check_count(dst, dst_type);
 386             break;
 387
 388         case OVSDB_M_DELETE:
 389             ovsdb_datum_subtract(dst, dst_type, arg, arg_type);
 390             error = ovsdb_mutation_check_count(dst, dst_type);
 391             break;
 392
 393         default:
 394             OVS_NOT_REACHED();
 395         }
 396         if (error) {
 397             return error;
 398         }
 399     }
 400
 401     return NULL;
 402 }
 403 \f
 404 static int
 405 add_int(int64_t *x, int64_t y)
 406 {
 407     /* Check for overflow.  See _Hacker's Delight_ pp. 27. */
 408     int64_t z = ~(*x ^ y) & INT64_MIN;
 409     if ((~(*x ^ y) & ~(((*x ^ z) + y) ^ y)) >> 63) {
 410         return ME_RANGE;
 411     } else {
 412         *x += y;
 413         return 0;
 414     }
 415 }
 416
 417 static int
 418 sub_int(int64_t *x, int64_t y)
 419 {
 420     /* Check for overflow.  See _Hacker's Delight_ pp. 27. */
 421     int64_t z = (*x ^ y) & INT64_MIN;
 422     if (((*x ^ y) & (((*x ^ z) - y) ^ y)) >> 63) {
 423         return ME_RANGE;
 424     } else {
 425         *x -= y;
 426         return 0;
 427     }
 428 }
 429
 430 static int
 431 mul_int(int64_t *x, int64_t y)
 432 {
 433     /* Check for overflow.  See _Hacker's Delight_ pp. 30. */
 434     if (*x > 0
 435         ? (y > 0
 436            ? *x >= INT64_MAX / y
 437            : y  < INT64_MIN / *x)
 438         : (y > 0
 439            ? *x < INT64_MIN / y
 440            : *x != 0 && y < INT64_MAX / y)) {
 441         return ME_RANGE;
 442     } else {
 443         *x *= y;
 444         return 0;
 445     }
 446 }
 447
 448 static int
 449 check_int_div(int64_t x, int64_t y)
 450 {
 451     /* Check for overflow.  See _Hacker's Delight_ pp. 32. */
 452     if (!y) {
 453         return ME_DOM;
 454     } else if (x == INT64_MIN && y == -1) {
 455         return ME_RANGE;
 456     } else {
 457         return 0;
 458     }
 459 }
 460
 461 static int
 462 div_int(int64_t *x, int64_t y)
 463 {
 464     int error = check_int_div(*x, y);
 465     if (!error) {
 466         *x /= y;
 467     }
 468     return error;
 469 }
 470
 471 static int
 472 mod_int(int64_t *x, int64_t y)
 473 {
 474     int error = check_int_div(*x, y);
 475     if (!error) {
 476         *x %= y;
 477     }
 478     return error;
 479 }
 480
 481 static int
 482 add_double(double *x, double y)
 483 {
 484     *x += y;
 485     return 0;
 486 }
 487
 488 static int
 489 sub_double(double *x, double y)
 490 {
 491     *x -= y;
 492     return 0;
 493 }
 494
 495 static int
 496 mul_double(double *x, double y)
 497 {
 498     *x *= y;
 499     return 0;
 500 }
 501
 502 static int
 503 div_double(double *x, double y)
 504 {
 505     if (y == 0) {
 506         return ME_DOM;
 507     } else {
 508         *x /= y;
 509         return 0;
 510     }
 511 }
 512
 513 static const struct ovsdb_scalar_mutation add_mutation = {
 514     add_int, add_double, OVSDB_M_ADD
 515 };
 516
 517 static const struct ovsdb_scalar_mutation sub_mutation = {
 518     sub_int, sub_double, OVSDB_M_SUB
 519 };
 520
 521 static const struct ovsdb_scalar_mutation mul_mutation = {
 522     mul_int, mul_double, OVSDB_M_MUL
 523 };
 524
 525 static const struct ovsdb_scalar_mutation div_mutation = {
 526     div_int, div_double, OVSDB_M_DIV
 527 };
 528
 529 static const struct ovsdb_scalar_mutation mod_mutation = {
 530     mod_int, NULL, OVSDB_M_MOD
 531 };