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