ovsdb/mutation.c

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