pintos-os.org Git - openvswitch/blob - ovsdb/mutation.c

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