Branch data Line data Source code
1 : : /* Copyright (c) 2009, 2010, 2011, 2012, 2014 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 "ovsdb-data.h"
19 : :
20 : : #include <ctype.h>
21 : : #include <float.h>
22 : : #include <inttypes.h>
23 : : #include <limits.h>
24 : :
25 : : #include "openvswitch/dynamic-string.h"
26 : : #include "hash.h"
27 : : #include "ovs-thread.h"
28 : : #include "ovsdb-error.h"
29 : : #include "ovsdb-parser.h"
30 : : #include "openvswitch/json.h"
31 : : #include "openvswitch/shash.h"
32 : : #include "smap.h"
33 : : #include "sort.h"
34 : : #include "unicode.h"
35 : : #include "util.h"
36 : :
37 : : static struct json *
38 : 571176 : wrap_json(const char *name, struct json *wrapped)
39 : : {
40 : 571176 : return json_array_create_2(json_string_create(name), wrapped);
41 : : }
42 : :
43 : : /* Initializes 'atom' with the default value of the given 'type'.
44 : : *
45 : : * The default value for an atom is as defined in RFC 7047:
46 : : *
47 : : * - "integer" or "real": 0
48 : : *
49 : : * - "boolean": false
50 : : *
51 : : * - "string": "" (the empty string)
52 : : *
53 : : * - "uuid": 00000000-0000-0000-0000-000000000000
54 : : *
55 : : * The caller must eventually arrange for 'atom' to be destroyed (with
56 : : * ovsdb_atom_destroy()). */
57 : : void
58 : 953361 : ovsdb_atom_init_default(union ovsdb_atom *atom, enum ovsdb_atomic_type type)
59 : : {
60 [ - + + + : 953361 : switch (type) {
+ + - ]
61 : : case OVSDB_TYPE_VOID:
62 : 0 : OVS_NOT_REACHED();
63 : :
64 : : case OVSDB_TYPE_INTEGER:
65 : 297025 : atom->integer = 0;
66 : 297025 : break;
67 : :
68 : : case OVSDB_TYPE_REAL:
69 : 533 : atom->real = 0.0;
70 : 533 : break;
71 : :
72 : : case OVSDB_TYPE_BOOLEAN:
73 : 151926 : atom->boolean = false;
74 : 151926 : break;
75 : :
76 : : case OVSDB_TYPE_STRING:
77 : 290000 : atom->string = xmemdup("", 1);
78 : 290000 : break;
79 : :
80 : : case OVSDB_TYPE_UUID:
81 : 213877 : uuid_zero(&atom->uuid);
82 : 213877 : break;
83 : :
84 : : case OVSDB_N_TYPES:
85 : : default:
86 : 0 : OVS_NOT_REACHED();
87 : : }
88 : 953361 : }
89 : :
90 : : /* Returns a read-only atom of the given 'type' that has the default value for
91 : : * 'type'. The caller must not modify or free the returned atom.
92 : : *
93 : : * See ovsdb_atom_init_default() for an explanation of the default value of an
94 : : * atom. */
95 : : const union ovsdb_atom *
96 : 177 : ovsdb_atom_default(enum ovsdb_atomic_type type)
97 : : {
98 : : static union ovsdb_atom default_atoms[OVSDB_N_TYPES];
99 : : static struct ovsthread_once once = OVSTHREAD_ONCE_INITIALIZER;
100 : :
101 [ + + ]: 177 : if (ovsthread_once_start(&once)) {
102 : : int i;
103 : :
104 [ + + ]: 294 : for (i = 0; i < OVSDB_N_TYPES; i++) {
105 [ + + ]: 252 : if (i != OVSDB_TYPE_VOID) {
106 : 210 : ovsdb_atom_init_default(&default_atoms[i], i);
107 : : }
108 : : }
109 : 42 : ovsthread_once_done(&once);
110 : : }
111 : :
112 [ - + ]: 177 : ovs_assert(ovsdb_atomic_type_is_valid(type));
113 : 177 : return &default_atoms[type];
114 : : }
115 : :
116 : : /* Returns true if 'atom', which must have the given 'type', has the default
117 : : * value for that type.
118 : : *
119 : : * See ovsdb_atom_init_default() for an explanation of the default value of an
120 : : * atom. */
121 : : bool
122 : 426660 : ovsdb_atom_is_default(const union ovsdb_atom *atom,
123 : : enum ovsdb_atomic_type type)
124 : : {
125 [ - + + + : 426660 : switch (type) {
+ + - ]
126 : : case OVSDB_TYPE_VOID:
127 : 0 : OVS_NOT_REACHED();
128 : :
129 : : case OVSDB_TYPE_INTEGER:
130 : 83176 : return atom->integer == 0;
131 : :
132 : : case OVSDB_TYPE_REAL:
133 : 415 : return atom->real == 0.0;
134 : :
135 : : case OVSDB_TYPE_BOOLEAN:
136 : 50906 : return atom->boolean == false;
137 : :
138 : : case OVSDB_TYPE_STRING:
139 : 225330 : return atom->string[0] == '\0';
140 : :
141 : : case OVSDB_TYPE_UUID:
142 : 66833 : return uuid_is_zero(&atom->uuid);
143 : :
144 : : case OVSDB_N_TYPES:
145 : : default:
146 : 0 : OVS_NOT_REACHED();
147 : : }
148 : : }
149 : :
150 : : /* Initializes 'new' as a copy of 'old', with the given 'type'.
151 : : *
152 : : * The caller must eventually arrange for 'new' to be destroyed (with
153 : : * ovsdb_atom_destroy()). */
154 : : void
155 : 2557372 : ovsdb_atom_clone(union ovsdb_atom *new, const union ovsdb_atom *old,
156 : : enum ovsdb_atomic_type type)
157 : : {
158 [ - + + + : 2557372 : switch (type) {
+ + - ]
159 : : case OVSDB_TYPE_VOID:
160 : 0 : OVS_NOT_REACHED();
161 : :
162 : : case OVSDB_TYPE_INTEGER:
163 : 594807 : new->integer = old->integer;
164 : 594807 : break;
165 : :
166 : : case OVSDB_TYPE_REAL:
167 : 1114 : new->real = old->real;
168 : 1114 : break;
169 : :
170 : : case OVSDB_TYPE_BOOLEAN:
171 : 133387 : new->boolean = old->boolean;
172 : 133387 : break;
173 : :
174 : : case OVSDB_TYPE_STRING:
175 : 1347876 : new->string = xstrdup(old->string);
176 : 1347876 : break;
177 : :
178 : : case OVSDB_TYPE_UUID:
179 : 480188 : new->uuid = old->uuid;
180 : 480188 : break;
181 : :
182 : : case OVSDB_N_TYPES:
183 : : default:
184 : 0 : OVS_NOT_REACHED();
185 : : }
186 : 2557372 : }
187 : :
188 : : /* Swaps the contents of 'a' and 'b', which need not have the same type. */
189 : : void
190 : 4627996 : ovsdb_atom_swap(union ovsdb_atom *a, union ovsdb_atom *b)
191 : : {
192 : 4627996 : union ovsdb_atom tmp = *a;
193 : 4627996 : *a = *b;
194 : 4627996 : *b = tmp;
195 : 4627996 : }
196 : :
197 : : /* Returns a hash value for 'atom', which has the specified 'type', folding
198 : : * 'basis' into the calculation. */
199 : : uint32_t
200 : 262335 : ovsdb_atom_hash(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
201 : : uint32_t basis)
202 : : {
203 [ - + + + : 262335 : switch (type) {
+ + - ]
204 : : case OVSDB_TYPE_VOID:
205 : 0 : OVS_NOT_REACHED();
206 : :
207 : : case OVSDB_TYPE_INTEGER:
208 : 7037 : return hash_int(atom->integer, basis);
209 : :
210 : : case OVSDB_TYPE_REAL:
211 : 1439 : return hash_double(atom->real, basis);
212 : :
213 : : case OVSDB_TYPE_BOOLEAN:
214 : 1651 : return hash_boolean(atom->boolean, basis);
215 : :
216 : : case OVSDB_TYPE_STRING:
217 : 50206 : return hash_string(atom->string, basis);
218 : :
219 : : case OVSDB_TYPE_UUID:
220 : 202002 : return hash_int(uuid_hash(&atom->uuid), basis);
221 : :
222 : : case OVSDB_N_TYPES:
223 : : default:
224 : 0 : OVS_NOT_REACHED();
225 : : }
226 : : }
227 : :
228 : : /* Compares 'a' and 'b', which both have type 'type', and returns a
229 : : * strcmp()-like result. */
230 : : int
231 : 6263640 : ovsdb_atom_compare_3way(const union ovsdb_atom *a,
232 : : const union ovsdb_atom *b,
233 : : enum ovsdb_atomic_type type)
234 : : {
235 [ - + + + : 6263640 : switch (type) {
+ + - ]
236 : : case OVSDB_TYPE_VOID:
237 : 0 : OVS_NOT_REACHED();
238 : :
239 : : case OVSDB_TYPE_INTEGER:
240 [ + + ]: 385165 : return a->integer < b->integer ? -1 : a->integer > b->integer;
241 : :
242 : : case OVSDB_TYPE_REAL:
243 [ + + ]: 1517 : return a->real < b->real ? -1 : a->real > b->real;
244 : :
245 : : case OVSDB_TYPE_BOOLEAN:
246 : 21216 : return a->boolean - b->boolean;
247 : :
248 : : case OVSDB_TYPE_STRING:
249 : 3391692 : return strcmp(a->string, b->string);
250 : :
251 : : case OVSDB_TYPE_UUID:
252 : 2464050 : return uuid_compare_3way(&a->uuid, &b->uuid);
253 : :
254 : : case OVSDB_N_TYPES:
255 : : default:
256 : 0 : OVS_NOT_REACHED();
257 : : }
258 : : }
259 : :
260 : : static struct ovsdb_error *
261 : 397242 : unwrap_json(const struct json *json, const char *name,
262 : : enum json_type value_type, const struct json **value)
263 : : {
264 [ + + ]: 397242 : if (json->type != JSON_ARRAY
265 [ + - ]: 397241 : || json->u.array.n != 2
266 [ + - ]: 397241 : || json->u.array.elems[0]->type != JSON_STRING
267 [ + - ][ + + ]: 397241 : || (name && strcmp(json->u.array.elems[0]->u.string, name))
268 [ - + ]: 385059 : || json->u.array.elems[1]->type != value_type)
269 : : {
270 : 12183 : *value = NULL;
271 : 12183 : return ovsdb_syntax_error(json, NULL, "expected [\"%s\", <%s>]", name,
272 : : json_type_to_string(value_type));
273 : : }
274 : 385059 : *value = json->u.array.elems[1];
275 : 385059 : return NULL;
276 : : }
277 : :
278 : : static struct ovsdb_error *
279 : 155380 : parse_json_pair(const struct json *json,
280 : : const struct json **elem0, const struct json **elem1)
281 : : {
282 [ + - ][ - + ]: 155380 : if (json->type != JSON_ARRAY || json->u.array.n != 2) {
283 : 0 : return ovsdb_syntax_error(json, NULL, "expected 2-element array");
284 : : }
285 : 155380 : *elem0 = json->u.array.elems[0];
286 : 155380 : *elem1 = json->u.array.elems[1];
287 : 155380 : return NULL;
288 : : }
289 : :
290 : : static void
291 : 12305 : ovsdb_symbol_referenced(struct ovsdb_symbol *symbol,
292 : : const struct ovsdb_base_type *base)
293 : : {
294 [ - + ]: 12305 : ovs_assert(base->type == OVSDB_TYPE_UUID);
295 : :
296 [ + + ]: 12305 : if (base->u.uuid.refTableName) {
297 [ + + - ]: 12261 : switch (base->u.uuid.refType) {
298 : : case OVSDB_REF_STRONG:
299 : 11888 : symbol->strong_ref = true;
300 : 11888 : break;
301 : : case OVSDB_REF_WEAK:
302 : 373 : symbol->weak_ref = true;
303 : 373 : break;
304 : : }
305 : : }
306 : 12305 : }
307 : :
308 : : static struct ovsdb_error * OVS_WARN_UNUSED_RESULT
309 : 255901 : ovsdb_atom_parse_uuid(struct uuid *uuid, const struct json *json,
310 : : struct ovsdb_symbol_table *symtab,
311 : : const struct ovsdb_base_type *base)
312 : : {
313 : : struct ovsdb_error *error0;
314 : : const struct json *value;
315 : :
316 : 255901 : error0 = unwrap_json(json, "uuid", JSON_STRING, &value);
317 [ + + ]: 255901 : if (!error0) {
318 : 243730 : const char *uuid_string = json_string(value);
319 [ - + ]: 243730 : if (!uuid_from_string(uuid, uuid_string)) {
320 : 243730 : return ovsdb_syntax_error(json, NULL, "\"%s\" is not a valid UUID",
321 : : uuid_string);
322 : : }
323 [ + + ]: 12171 : } else if (symtab) {
324 : : struct ovsdb_error *error1;
325 : :
326 : 12169 : error1 = unwrap_json(json, "named-uuid", JSON_STRING, &value);
327 [ + - ]: 12169 : if (!error1) {
328 : : struct ovsdb_symbol *symbol;
329 : :
330 : 12169 : ovsdb_error_destroy(error0);
331 [ + + ]: 12169 : if (!ovsdb_parser_is_id(json_string(value))) {
332 : 1 : return ovsdb_syntax_error(json, NULL, "named-uuid string is "
333 : : "not a valid <id>");
334 : : }
335 : :
336 : 12168 : symbol = ovsdb_symbol_table_insert(symtab, json_string(value));
337 : 12168 : *uuid = symbol->uuid;
338 : 12168 : ovsdb_symbol_referenced(symbol, base);
339 : 12168 : return NULL;
340 : : }
341 : 0 : ovsdb_error_destroy(error1);
342 : : }
343 : :
344 : 255901 : return error0;
345 : : }
346 : :
347 : : static struct ovsdb_error * OVS_WARN_UNUSED_RESULT
348 : 1017506 : ovsdb_atom_from_json__(union ovsdb_atom *atom,
349 : : const struct ovsdb_base_type *base,
350 : : const struct json *json,
351 : : struct ovsdb_symbol_table *symtab)
352 : : {
353 : 1017506 : enum ovsdb_atomic_type type = base->type;
354 : :
355 [ - + + + : 1017506 : switch (type) {
+ + - ]
356 : : case OVSDB_TYPE_VOID:
357 : 0 : OVS_NOT_REACHED();
358 : :
359 : : case OVSDB_TYPE_INTEGER:
360 [ + + ]: 166707 : if (json->type == JSON_INTEGER) {
361 : 166706 : atom->integer = json->u.integer;
362 : 166706 : return NULL;
363 : : }
364 : 1 : break;
365 : :
366 : : case OVSDB_TYPE_REAL:
367 [ + + ]: 512 : if (json->type == JSON_INTEGER) {
368 : 327 : atom->real = json->u.integer;
369 : 327 : return NULL;
370 [ + - ]: 185 : } else if (json->type == JSON_REAL) {
371 : 185 : atom->real = json->u.real;
372 : 185 : return NULL;
373 : : }
374 : 0 : break;
375 : :
376 : : case OVSDB_TYPE_BOOLEAN:
377 [ + + ]: 6693 : if (json->type == JSON_TRUE) {
378 : 2020 : atom->boolean = true;
379 : 2020 : return NULL;
380 [ + + ]: 4673 : } else if (json->type == JSON_FALSE) {
381 : 4672 : atom->boolean = false;
382 : 4672 : return NULL;
383 : : }
384 : 1 : break;
385 : :
386 : : case OVSDB_TYPE_STRING:
387 [ + + ]: 587693 : if (json->type == JSON_STRING) {
388 : 587692 : atom->string = xstrdup(json->u.string);
389 : 587692 : return NULL;
390 : : }
391 : 1 : break;
392 : :
393 : : case OVSDB_TYPE_UUID:
394 : 255901 : return ovsdb_atom_parse_uuid(&atom->uuid, json, symtab, base);
395 : :
396 : : case OVSDB_N_TYPES:
397 : : default:
398 : 0 : OVS_NOT_REACHED();
399 : : }
400 : :
401 : 3 : return ovsdb_syntax_error(json, NULL, "expected %s",
402 : : ovsdb_atomic_type_to_string(type));
403 : : }
404 : :
405 : : /* Parses 'json' as an atom of the type described by 'base'. If successful,
406 : : * returns NULL and initializes 'atom' with the parsed atom. On failure,
407 : : * returns an error and the contents of 'atom' are indeterminate. The caller
408 : : * is responsible for freeing the error or the atom that is returned.
409 : : *
410 : : * Violations of constraints expressed by 'base' are treated as errors.
411 : : *
412 : : * If 'symtab' is nonnull, then named UUIDs in 'symtab' are accepted. Refer to
413 : : * RFC 7047 for information about this, and for the syntax that this function
414 : : * accepts. If 'base' is a reference and a symbol is parsed, then the symbol's
415 : : * 'strong_ref' or 'weak_ref' member is set to true, as appropriate. */
416 : : struct ovsdb_error *
417 : 1017506 : ovsdb_atom_from_json(union ovsdb_atom *atom,
418 : : const struct ovsdb_base_type *base,
419 : : const struct json *json,
420 : : struct ovsdb_symbol_table *symtab)
421 : : {
422 : : struct ovsdb_error *error;
423 : :
424 : 1017506 : error = ovsdb_atom_from_json__(atom, base, json, symtab);
425 [ + + ]: 1017506 : if (error) {
426 : 6 : return error;
427 : : }
428 : :
429 : 1017500 : error = ovsdb_atom_check_constraints(atom, base);
430 [ + + ]: 1017500 : if (error) {
431 : 51 : ovsdb_atom_destroy(atom, base->type);
432 : : }
433 : 1017500 : return error;
434 : : }
435 : :
436 : : /* Converts 'atom', of the specified 'type', to JSON format, and returns the
437 : : * JSON. The caller is responsible for freeing the returned JSON.
438 : : *
439 : : * Refer to RFC 7047 for the format of the JSON that this function produces. */
440 : : struct json *
441 : 1304963 : ovsdb_atom_to_json(const union ovsdb_atom *atom, enum ovsdb_atomic_type type)
442 : : {
443 [ - + + + : 1304963 : switch (type) {
+ + - ]
444 : : case OVSDB_TYPE_VOID:
445 : 0 : OVS_NOT_REACHED();
446 : :
447 : : case OVSDB_TYPE_INTEGER:
448 : 214754 : return json_integer_create(atom->integer);
449 : :
450 : : case OVSDB_TYPE_REAL:
451 : 649 : return json_real_create(atom->real);
452 : :
453 : : case OVSDB_TYPE_BOOLEAN:
454 : 11193 : return json_boolean_create(atom->boolean);
455 : :
456 : : case OVSDB_TYPE_STRING:
457 : 823780 : return json_string_create(atom->string);
458 : :
459 : : case OVSDB_TYPE_UUID:
460 : 254587 : return wrap_json("uuid", json_string_create_nocopy(
461 : 763761 : xasprintf(UUID_FMT, UUID_ARGS(&atom->uuid))));
462 : :
463 : : case OVSDB_N_TYPES:
464 : : default:
465 : 0 : OVS_NOT_REACHED();
466 : : }
467 : : }
468 : :
469 : : static char *
470 : 16880 : ovsdb_atom_from_string__(union ovsdb_atom *atom,
471 : : const struct ovsdb_base_type *base, const char *s,
472 : : struct ovsdb_symbol_table *symtab)
473 : : {
474 : 16880 : enum ovsdb_atomic_type type = base->type;
475 : :
476 [ - + + + : 16880 : switch (type) {
+ + - ]
477 : : case OVSDB_TYPE_VOID:
478 : 0 : OVS_NOT_REACHED();
479 : :
480 : : case OVSDB_TYPE_INTEGER: {
481 : : long long int integer;
482 [ + + ]: 2011 : if (!str_to_llong(s, 10, &integer)) {
483 : 2 : return xasprintf("\"%s\" is not a valid integer", s);
484 : : }
485 : 2009 : atom->integer = integer;
486 : : }
487 : 2009 : break;
488 : :
489 : : case OVSDB_TYPE_REAL:
490 [ - + ]: 17 : if (!str_to_double(s, &atom->real)) {
491 : 0 : return xasprintf("\"%s\" is not a valid real number", s);
492 : : }
493 : : /* Our JSON input routines map negative zero to zero, so do that here
494 : : * too for consistency. */
495 [ + + ]: 17 : if (atom->real == 0.0) {
496 : 6 : atom->real = 0.0;
497 : : }
498 : 17 : break;
499 : :
500 : : case OVSDB_TYPE_BOOLEAN:
501 [ + + ][ + - ]: 53 : if (!strcmp(s, "true") || !strcmp(s, "yes") || !strcmp(s, "on")
[ + - ]
502 [ - + ]: 18 : || !strcmp(s, "1")) {
503 : 35 : atom->boolean = true;
504 [ + + ][ + - ]: 18 : } else if (!strcmp(s, "false") || !strcmp(s, "no") || !strcmp(s, "off")
[ + - ]
505 [ - + ]: 1 : || !strcmp(s, "0")) {
506 : 17 : atom->boolean = false;
507 : : } else {
508 : 1 : return xasprintf("\"%s\" is not a valid boolean "
509 : : "(use \"true\" or \"false\")", s);
510 : : }
511 : 52 : break;
512 : :
513 : : case OVSDB_TYPE_STRING:
514 [ + + ]: 14624 : if (*s == '\0') {
515 : 1 : return xstrdup("An empty string is not valid as input; "
516 : : "use \"\" to represent the empty string");
517 [ + + ]: 14623 : } else if (*s == '"') {
518 : 238 : size_t s_len = strlen(s);
519 : :
520 [ + - ][ + + ]: 238 : if (s_len < 2 || s[s_len - 1] != '"') {
521 : 1 : return xasprintf("%s: missing quote at end of "
522 : : "quoted string", s);
523 [ + + ]: 237 : } else if (!json_string_unescape(s + 1, s_len - 2,
524 : : &atom->string)) {
525 : 2 : char *error = xasprintf("%s: %s", s, atom->string);
526 : 2 : free(atom->string);
527 : 237 : return error;
528 : : }
529 : : } else {
530 : 14385 : atom->string = xstrdup(s);
531 : : }
532 : 14620 : break;
533 : :
534 : : case OVSDB_TYPE_UUID:
535 [ + + ]: 175 : if (*s == '@') {
536 : 137 : struct ovsdb_symbol *symbol = ovsdb_symbol_table_insert(symtab, s);
537 : 137 : atom->uuid = symbol->uuid;
538 : 137 : ovsdb_symbol_referenced(symbol, base);
539 [ + + ]: 38 : } else if (!uuid_from_string(&atom->uuid, s)) {
540 : 1 : return xasprintf("\"%s\" is not a valid UUID", s);
541 : : }
542 : 174 : break;
543 : :
544 : : case OVSDB_N_TYPES:
545 : : default:
546 : 0 : OVS_NOT_REACHED();
547 : : }
548 : :
549 : 16872 : return NULL;
550 : : }
551 : :
552 : : /* Initializes 'atom' to a value of type 'base' parsed from 's', which takes
553 : : * one of the following forms:
554 : : *
555 : : * - OVSDB_TYPE_INTEGER: A decimal integer optionally preceded by a sign.
556 : : *
557 : : * - OVSDB_TYPE_REAL: A floating-point number in the format accepted by
558 : : * strtod().
559 : : *
560 : : * - OVSDB_TYPE_BOOLEAN: "true", "yes", "on", "1" for true, or "false",
561 : : * "no", "off", or "0" for false.
562 : : *
563 : : * - OVSDB_TYPE_STRING: A JSON string if it begins with a quote, otherwise
564 : : * an arbitrary string.
565 : : *
566 : : * - OVSDB_TYPE_UUID: A UUID in RFC 4122 format. If 'symtab' is nonnull,
567 : : * then an identifier beginning with '@' is also acceptable. If the
568 : : * named identifier is already in 'symtab', then the associated UUID is
569 : : * used; otherwise, a new, random UUID is used and added to the symbol
570 : : * table. If 'base' is a reference and a symbol is parsed, then the
571 : : * symbol's 'strong_ref' or 'weak_ref' member is set to true, as
572 : : * appropriate.
573 : : *
574 : : * Returns a null pointer if successful, otherwise an error message describing
575 : : * the problem. On failure, the contents of 'atom' are indeterminate. The
576 : : * caller is responsible for freeing the atom or the error.
577 : : */
578 : : char *
579 : 16880 : ovsdb_atom_from_string(union ovsdb_atom *atom,
580 : : const struct ovsdb_base_type *base, const char *s,
581 : : struct ovsdb_symbol_table *symtab)
582 : : {
583 : : struct ovsdb_error *error;
584 : : char *msg;
585 : :
586 : 16880 : msg = ovsdb_atom_from_string__(atom, base, s, symtab);
587 [ + + ]: 16880 : if (msg) {
588 : 8 : return msg;
589 : : }
590 : :
591 : 16872 : error = ovsdb_atom_check_constraints(atom, base);
592 [ + + ]: 16872 : if (error) {
593 : 3 : ovsdb_atom_destroy(atom, base->type);
594 : 3 : msg = ovsdb_error_to_string(error);
595 : 3 : ovsdb_error_destroy(error);
596 : : }
597 : 16872 : return msg;
598 : : }
599 : :
600 : : static bool
601 : 8265 : string_needs_quotes(const char *s)
602 : : {
603 : 8265 : const char *p = s;
604 : : unsigned char c;
605 : :
606 : 8265 : c = *p++;
607 [ + + ][ + + ]: 8265 : if (!isalpha(c) && c != '_') {
608 : 1126 : return true;
609 : : }
610 : :
611 [ + + ]: 48493 : while ((c = *p++) != '\0') {
612 [ + + ][ + + ]: 44007 : if (!isalpha(c) && c != '_' && c != '-' && c != '.') {
[ + + ][ + + ]
613 : 2653 : return true;
614 : : }
615 : : }
616 : :
617 [ + + ][ + + ]: 4486 : if (!strcmp(s, "true") || !strcmp(s, "false")) {
618 : 162 : return true;
619 : : }
620 : :
621 : 4324 : return false;
622 : : }
623 : :
624 : : /* Appends 'atom' (which has the given 'type') to 'out', in a format acceptable
625 : : * to ovsdb_atom_from_string(). */
626 : : void
627 : 16097 : ovsdb_atom_to_string(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
628 : : struct ds *out)
629 : : {
630 [ - + + + : 16097 : switch (type) {
+ + - ]
631 : : case OVSDB_TYPE_VOID:
632 : 0 : OVS_NOT_REACHED();
633 : :
634 : : case OVSDB_TYPE_INTEGER:
635 : 4264 : ds_put_format(out, "%"PRId64, atom->integer);
636 : 4264 : break;
637 : :
638 : : case OVSDB_TYPE_REAL:
639 : 30 : ds_put_format(out, "%.*g", DBL_DIG, atom->real);
640 : 30 : break;
641 : :
642 : : case OVSDB_TYPE_BOOLEAN:
643 [ + + ]: 509 : ds_put_cstr(out, atom->boolean ? "true" : "false");
644 : 509 : break;
645 : :
646 : : case OVSDB_TYPE_STRING:
647 [ + + ]: 8265 : if (string_needs_quotes(atom->string)) {
648 : : struct json json;
649 : :
650 : 3941 : json.type = JSON_STRING;
651 : 3941 : json.u.string = atom->string;
652 : 3941 : json_to_ds(&json, 0, out);
653 : : } else {
654 : 4324 : ds_put_cstr(out, atom->string);
655 : : }
656 : 8265 : break;
657 : :
658 : : case OVSDB_TYPE_UUID:
659 : 3029 : ds_put_format(out, UUID_FMT, UUID_ARGS(&atom->uuid));
660 : 3029 : break;
661 : :
662 : : case OVSDB_N_TYPES:
663 : : default:
664 : 0 : OVS_NOT_REACHED();
665 : : }
666 : 16097 : }
667 : :
668 : : /* Appends 'atom' (which has the given 'type') to 'out', in a bare string
669 : : * format that cannot be parsed uniformly back into a datum but is easier for
670 : : * shell scripts, etc., to deal with. */
671 : : void
672 : 1065 : ovsdb_atom_to_bare(const union ovsdb_atom *atom, enum ovsdb_atomic_type type,
673 : : struct ds *out)
674 : : {
675 [ + + ]: 1065 : if (type == OVSDB_TYPE_STRING) {
676 : 1000 : ds_put_cstr(out, atom->string);
677 : : } else {
678 : 65 : ovsdb_atom_to_string(atom, type, out);
679 : : }
680 : 1065 : }
681 : :
682 : : static struct ovsdb_error *
683 : 647315 : check_string_constraints(const char *s,
684 : : const struct ovsdb_string_constraints *c)
685 : : {
686 : : size_t n_chars;
687 : : char *msg;
688 : :
689 : 647315 : msg = utf8_validate(s, &n_chars);
690 [ + + ]: 647315 : if (msg) {
691 : : struct ovsdb_error *error;
692 : :
693 : 2 : error = ovsdb_error("constraint violation",
694 : : "not a valid UTF-8 string: %s", msg);
695 : 2 : free(msg);
696 : 2 : return error;
697 : : }
698 : :
699 [ + + ]: 647313 : if (n_chars < c->minLen) {
700 : 3 : return ovsdb_error(
701 : : "constraint violation",
702 : : "\"%s\" length %"PRIuSIZE" is less than minimum allowed "
703 : : "length %u", s, n_chars, c->minLen);
704 [ + + ]: 647310 : } else if (n_chars > c->maxLen) {
705 : 1 : return ovsdb_error(
706 : : "constraint violation",
707 : : "\"%s\" length %"PRIuSIZE" is greater than maximum allowed "
708 : : "length %u", s, n_chars, c->maxLen);
709 : : }
710 : :
711 : 647315 : return NULL;
712 : : }
713 : :
714 : : /* Checks whether 'atom' meets the constraints (if any) defined in 'base'.
715 : : * (base->type must specify 'atom''s type.) Returns a null pointer if the
716 : : * constraints are met, otherwise an error that explains the violation.
717 : : *
718 : : * Checking UUID constraints is deferred to transaction commit time, so this
719 : : * function does nothing for UUID constraints. */
720 : : struct ovsdb_error *
721 : 1166180 : ovsdb_atom_check_constraints(const union ovsdb_atom *atom,
722 : : const struct ovsdb_base_type *base)
723 : : {
724 [ + + ]: 1166180 : if (base->enum_
725 [ + + ]: 65914 : && ovsdb_datum_find_key(base->enum_, atom, base->type) == UINT_MAX) {
726 : : struct ovsdb_error *error;
727 : 18 : struct ds actual = DS_EMPTY_INITIALIZER;
728 : 18 : struct ds valid = DS_EMPTY_INITIALIZER;
729 : :
730 : 18 : ovsdb_atom_to_string(atom, base->type, &actual);
731 : 18 : ovsdb_datum_to_string(base->enum_,
732 : : ovsdb_base_type_get_enum_type(base->type),
733 : : &valid);
734 : 18 : error = ovsdb_error("constraint violation",
735 : : "%s is not one of the allowed values (%s)",
736 : : ds_cstr(&actual), ds_cstr(&valid));
737 : 18 : ds_destroy(&actual);
738 : 18 : ds_destroy(&valid);
739 : :
740 : 18 : return error;
741 : : }
742 : :
743 [ - + + + : 1166162 : switch (base->type) {
+ + - ]
744 : : case OVSDB_TYPE_VOID:
745 : 0 : OVS_NOT_REACHED();
746 : :
747 : : case OVSDB_TYPE_INTEGER:
748 [ + + ]: 199963 : if (atom->integer >= base->u.integer.min
749 [ + + ]: 199935 : && atom->integer <= base->u.integer.max) {
750 : 199927 : return NULL;
751 [ + + ]: 36 : } else if (base->u.integer.min != INT64_MIN) {
752 [ + + ]: 34 : if (base->u.integer.max != INT64_MAX) {
753 : 11 : return ovsdb_error("constraint violation",
754 : : "%"PRId64" is not in the valid range "
755 : : "%"PRId64" to %"PRId64" (inclusive)",
756 : : atom->integer,
757 : : base->u.integer.min, base->u.integer.max);
758 : : } else {
759 : 23 : return ovsdb_error("constraint violation",
760 : : "%"PRId64" is less than minimum allowed "
761 : : "value %"PRId64,
762 : : atom->integer, base->u.integer.min);
763 : : }
764 : : } else {
765 : 2 : return ovsdb_error("constraint violation",
766 : : "%"PRId64" is greater than maximum allowed "
767 : : "value %"PRId64,
768 : : atom->integer, base->u.integer.max);
769 : : }
770 : : OVS_NOT_REACHED();
771 : :
772 : : case OVSDB_TYPE_REAL:
773 [ + + ][ + + ]: 839 : if (atom->real >= base->u.real.min && atom->real <= base->u.real.max) {
774 : 828 : return NULL;
775 [ + + ]: 11 : } else if (base->u.real.min != -DBL_MAX) {
776 [ + + ]: 9 : if (base->u.real.max != DBL_MAX) {
777 : 7 : return ovsdb_error("constraint violation",
778 : : "%.*g is not in the valid range "
779 : : "%.*g to %.*g (inclusive)",
780 : : DBL_DIG, atom->real,
781 : : DBL_DIG, base->u.real.min,
782 : : DBL_DIG, base->u.real.max);
783 : : } else {
784 : 2 : return ovsdb_error("constraint violation",
785 : : "%.*g is less than minimum allowed "
786 : : "value %.*g",
787 : : DBL_DIG, atom->real,
788 : : DBL_DIG, base->u.real.min);
789 : : }
790 : : } else {
791 : 2 : return ovsdb_error("constraint violation",
792 : : "%.*g is greater than maximum allowed "
793 : : "value %.*g",
794 : : DBL_DIG, atom->real,
795 : : DBL_DIG, base->u.real.max);
796 : : }
797 : : OVS_NOT_REACHED();
798 : :
799 : : case OVSDB_TYPE_BOOLEAN:
800 : 17297 : return NULL;
801 : :
802 : : case OVSDB_TYPE_STRING:
803 : 647315 : return check_string_constraints(atom->string, &base->u.string);
804 : :
805 : : case OVSDB_TYPE_UUID:
806 : 300748 : return NULL;
807 : :
808 : : case OVSDB_N_TYPES:
809 : : default:
810 : 0 : OVS_NOT_REACHED();
811 : : }
812 : : }
813 : :
814 : : static union ovsdb_atom *
815 : 7479986 : alloc_default_atoms(enum ovsdb_atomic_type type, size_t n)
816 : : {
817 [ + + ][ + + ]: 7479986 : if (type != OVSDB_TYPE_VOID && n) {
818 : : union ovsdb_atom *atoms;
819 : : unsigned int i;
820 : :
821 : 953146 : atoms = xmalloc(n * sizeof *atoms);
822 [ + + ]: 1906292 : for (i = 0; i < n; i++) {
823 : 953146 : ovsdb_atom_init_default(&atoms[i], type);
824 : : }
825 : 953146 : return atoms;
826 : : } else {
827 : : /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
828 : : * treated as xmalloc(1). */
829 : 6526840 : return NULL;
830 : : }
831 : : }
832 : :
833 : : /* Initializes 'datum' as an empty datum. (An empty datum can be treated as
834 : : * any type.) */
835 : : void
836 : 245611 : ovsdb_datum_init_empty(struct ovsdb_datum *datum)
837 : : {
838 : 245611 : datum->n = 0;
839 : 245611 : datum->keys = NULL;
840 : 245611 : datum->values = NULL;
841 : 245611 : }
842 : :
843 : : /* Initializes 'datum' as a datum that has the default value for 'type'.
844 : : *
845 : : * The default value for a particular type is as defined in RFC 7047:
846 : : *
847 : : * - If n_min is 0, then the default value is the empty set (or map).
848 : : *
849 : : * - If n_min is 1, the default value is a single value or a single
850 : : * key-value pair, whose key and value are the defaults for their
851 : : * atomic types. (See ovsdb_atom_init_default() for details.)
852 : : *
853 : : * - n_min > 1 is invalid. See ovsdb_type_is_valid().
854 : : */
855 : : void
856 : 3739993 : ovsdb_datum_init_default(struct ovsdb_datum *datum,
857 : : const struct ovsdb_type *type)
858 : : {
859 : 3739993 : datum->n = type->n_min;
860 : 3739993 : datum->keys = alloc_default_atoms(type->key.type, datum->n);
861 : 3739993 : datum->values = alloc_default_atoms(type->value.type, datum->n);
862 : 3739993 : }
863 : :
864 : : /* Returns a read-only datum of the given 'type' that has the default value for
865 : : * 'type'. The caller must not modify or free the returned datum.
866 : : *
867 : : * See ovsdb_datum_init_default() for an explanation of the default value of a
868 : : * datum. */
869 : : const struct ovsdb_datum *
870 : 35954 : ovsdb_datum_default(const struct ovsdb_type *type)
871 : : {
872 [ + + ]: 35954 : if (type->n_min == 0) {
873 : : static const struct ovsdb_datum empty;
874 : 3145 : return ∅
875 [ + - ]: 32809 : } else if (type->n_min == 1) {
876 : : static struct ovsdb_datum default_data[OVSDB_N_TYPES][OVSDB_N_TYPES];
877 : : struct ovsdb_datum *d;
878 : 32809 : int kt = type->key.type;
879 : 32809 : int vt = type->value.type;
880 : :
881 [ - + ]: 32809 : ovs_assert(ovsdb_type_is_valid(type));
882 : :
883 : 32809 : d = &default_data[kt][vt];
884 [ + + ]: 32809 : if (!d->n) {
885 : 147 : d->n = 1;
886 : 147 : d->keys = CONST_CAST(union ovsdb_atom *, ovsdb_atom_default(kt));
887 [ + + ]: 147 : if (vt != OVSDB_TYPE_VOID) {
888 : 25 : d->values = CONST_CAST(union ovsdb_atom *,
889 : : ovsdb_atom_default(vt));
890 : : }
891 : : }
892 : 32809 : return d;
893 : : } else {
894 : 0 : OVS_NOT_REACHED();
895 : : }
896 : : }
897 : :
898 : : /* Returns true if 'datum', which must have the given 'type', has the default
899 : : * value for that type.
900 : : *
901 : : * See ovsdb_datum_init_default() for an explanation of the default value of a
902 : : * datum. */
903 : : bool
904 : 881905 : ovsdb_datum_is_default(const struct ovsdb_datum *datum,
905 : : const struct ovsdb_type *type)
906 : : {
907 : : size_t i;
908 : :
909 [ + + ]: 881905 : if (datum->n != type->n_min) {
910 : 130027 : return false;
911 : : }
912 [ + + ]: 852113 : for (i = 0; i < datum->n; i++) {
913 [ + + ]: 426660 : if (!ovsdb_atom_is_default(&datum->keys[i], type->key.type)) {
914 : 326425 : return false;
915 : : }
916 [ - + ]: 100235 : if (type->value.type != OVSDB_TYPE_VOID
917 [ # # ]: 0 : && !ovsdb_atom_is_default(&datum->values[i], type->value.type)) {
918 : 0 : return false;
919 : : }
920 : : }
921 : :
922 : 425453 : return true;
923 : : }
924 : :
925 : : static union ovsdb_atom *
926 : 5902194 : clone_atoms(const union ovsdb_atom *old, enum ovsdb_atomic_type type, size_t n)
927 : : {
928 [ + + ][ + + ]: 5902194 : if (type != OVSDB_TYPE_VOID && n) {
929 : : union ovsdb_atom *new;
930 : : unsigned int i;
931 : :
932 : 1575391 : new = xmalloc(n * sizeof *new);
933 [ + + ]: 3917558 : for (i = 0; i < n; i++) {
934 : 2342167 : ovsdb_atom_clone(&new[i], &old[i], type);
935 : : }
936 : 1575391 : return new;
937 : : } else {
938 : : /* Avoid wasting memory in the n == 0 case, because xmalloc(0) is
939 : : * treated as xmalloc(1). */
940 : 4326803 : return NULL;
941 : : }
942 : : }
943 : :
944 : : /* Initializes 'new' as a copy of 'old', with the given 'type'.
945 : : *
946 : : * The caller must eventually arrange for 'new' to be destroyed (with
947 : : * ovsdb_datum_destroy()). */
948 : : void
949 : 2951097 : ovsdb_datum_clone(struct ovsdb_datum *new, const struct ovsdb_datum *old,
950 : : const struct ovsdb_type *type)
951 : : {
952 : 2951097 : unsigned int n = old->n;
953 : 2951097 : new->n = n;
954 : 2951097 : new->keys = clone_atoms(old->keys, type->key.type, n);
955 : 2951097 : new->values = clone_atoms(old->values, type->value.type, n);
956 : 2951097 : }
957 : :
958 : : static void
959 : 15470706 : free_data(enum ovsdb_atomic_type type,
960 : : union ovsdb_atom *atoms, size_t n_atoms)
961 : : {
962 [ + + ]: 15470706 : if (ovsdb_atom_needs_destruction(type)) {
963 : : unsigned int i;
964 [ + + ]: 8451711 : for (i = 0; i < n_atoms; i++) {
965 : 2720897 : ovsdb_atom_destroy(&atoms[i], type);
966 : : }
967 : : }
968 : 15470706 : free(atoms);
969 : 15470706 : }
970 : :
971 : : /* Frees the data owned by 'datum', which must have the given 'type'.
972 : : *
973 : : * This does not actually call free(datum). If necessary, the caller must be
974 : : * responsible for that. */
975 : : void
976 : 7735353 : ovsdb_datum_destroy(struct ovsdb_datum *datum, const struct ovsdb_type *type)
977 : : {
978 : 7735353 : free_data(type->key.type, datum->keys, datum->n);
979 : 7735353 : free_data(type->value.type, datum->values, datum->n);
980 : 7735353 : }
981 : :
982 : : /* Swaps the contents of 'a' and 'b', which need not have the same type. */
983 : : void
984 : 544234 : ovsdb_datum_swap(struct ovsdb_datum *a, struct ovsdb_datum *b)
985 : : {
986 : 544234 : struct ovsdb_datum tmp = *a;
987 : 544234 : *a = *b;
988 : 544234 : *b = tmp;
989 : 544234 : }
990 : :
991 : : struct ovsdb_datum_sort_cbdata {
992 : : enum ovsdb_atomic_type key_type;
993 : : enum ovsdb_atomic_type value_type;
994 : : struct ovsdb_datum *datum;
995 : : };
996 : :
997 : : static int
998 : 3375211 : ovsdb_datum_sort_compare_cb(size_t a, size_t b, void *cbdata_)
999 : : {
1000 : 3375211 : struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
1001 : : int retval;
1002 : :
1003 : 3375211 : retval = ovsdb_atom_compare_3way(&cbdata->datum->keys[a],
1004 : 3375211 : &cbdata->datum->keys[b],
1005 : : cbdata->key_type);
1006 [ + + ][ + - ]: 3375211 : if (retval || cbdata->value_type == OVSDB_TYPE_VOID) {
1007 : 3375211 : return retval;
1008 : : }
1009 : :
1010 : 0 : return ovsdb_atom_compare_3way(&cbdata->datum->values[a],
1011 : 0 : &cbdata->datum->values[b],
1012 : : cbdata->value_type);
1013 : : }
1014 : :
1015 : : static void
1016 : 3645371 : ovsdb_datum_sort_swap_cb(size_t a, size_t b, void *cbdata_)
1017 : : {
1018 : 3645371 : struct ovsdb_datum_sort_cbdata *cbdata = cbdata_;
1019 : :
1020 : 3645371 : ovsdb_atom_swap(&cbdata->datum->keys[a], &cbdata->datum->keys[b]);
1021 [ + + ]: 3645371 : if (cbdata->datum->values) {
1022 : 982625 : ovsdb_atom_swap(&cbdata->datum->values[a], &cbdata->datum->values[b]);
1023 : : }
1024 : 3645371 : }
1025 : :
1026 : : static void
1027 : 222830 : ovsdb_datum_sort__(struct ovsdb_datum *datum, enum ovsdb_atomic_type key_type,
1028 : : enum ovsdb_atomic_type value_type)
1029 : : {
1030 : : struct ovsdb_datum_sort_cbdata cbdata;
1031 : :
1032 : 222830 : cbdata.key_type = key_type;
1033 : 222830 : cbdata.value_type = value_type;
1034 : 222830 : cbdata.datum = datum;
1035 : 222830 : sort(datum->n, ovsdb_datum_sort_compare_cb, ovsdb_datum_sort_swap_cb,
1036 : : &cbdata);
1037 : 222830 : }
1038 : :
1039 : : /* The keys in an ovsdb_datum must be unique and in sorted order. Most
1040 : : * functions that modify an ovsdb_datum maintain these invariants. For those
1041 : : * that don't, this function checks and restores these invariants for 'datum',
1042 : : * whose keys are of type 'key_type'.
1043 : : *
1044 : : * This function returns NULL if successful, otherwise an error message. The
1045 : : * caller must free the returned error when it is no longer needed. On error,
1046 : : * 'datum' is sorted but not unique. */
1047 : : struct ovsdb_error *
1048 : 728139 : ovsdb_datum_sort(struct ovsdb_datum *datum, enum ovsdb_atomic_type key_type)
1049 : : {
1050 : : size_t i;
1051 : :
1052 [ + + ]: 728139 : if (datum->n < 2) {
1053 : 576138 : return NULL;
1054 : : }
1055 : :
1056 : 152001 : ovsdb_datum_sort__(datum, key_type, OVSDB_TYPE_VOID);
1057 : :
1058 [ + + ]: 509012 : for (i = 0; i < datum->n - 1; i++) {
1059 [ + + ]: 357029 : if (ovsdb_atom_equals(&datum->keys[i], &datum->keys[i + 1],
1060 : : key_type)) {
1061 [ + + ]: 18 : if (datum->values) {
1062 : 2 : return ovsdb_error(NULL, "map contains duplicate key");
1063 : : } else {
1064 : 16 : return ovsdb_error(NULL, "set contains duplicate");
1065 : : }
1066 : : }
1067 : : }
1068 : 151983 : return NULL;
1069 : : }
1070 : :
1071 : : /* This function is the same as ovsdb_datum_sort(), except that the caller
1072 : : * knows that 'datum' is unique. The operation therefore "cannot fail", so
1073 : : * this function assert-fails if it actually does. */
1074 : : void
1075 : 76505 : ovsdb_datum_sort_assert(struct ovsdb_datum *datum,
1076 : : enum ovsdb_atomic_type key_type)
1077 : : {
1078 : 76505 : struct ovsdb_error *error = ovsdb_datum_sort(datum, key_type);
1079 [ - + ]: 76505 : if (error) {
1080 : 0 : OVS_NOT_REACHED();
1081 : : }
1082 : 76505 : }
1083 : :
1084 : : /* This is similar to ovsdb_datum_sort(), except that it drops duplicate keys
1085 : : * instead of reporting an error. In a map type, the smallest value among a
1086 : : * group of duplicate pairs is retained and the others are dropped.
1087 : : *
1088 : : * Returns the number of keys (or pairs) that were dropped. */
1089 : : size_t
1090 : 266106 : ovsdb_datum_sort_unique(struct ovsdb_datum *datum,
1091 : : enum ovsdb_atomic_type key_type,
1092 : : enum ovsdb_atomic_type value_type)
1093 : : {
1094 : : size_t src, dst;
1095 : :
1096 [ + + ]: 266106 : if (datum->n < 2) {
1097 : 195277 : return 0;
1098 : : }
1099 : :
1100 : 70829 : ovsdb_datum_sort__(datum, key_type, value_type);
1101 : :
1102 : 70829 : dst = 1;
1103 [ + + ]: 452025 : for (src = 1; src < datum->n; src++) {
1104 [ - + ]: 381196 : if (ovsdb_atom_equals(&datum->keys[src], &datum->keys[dst - 1],
1105 : : key_type)) {
1106 : 0 : ovsdb_atom_destroy(&datum->keys[src], key_type);
1107 [ # # ]: 0 : if (value_type != OVSDB_TYPE_VOID) {
1108 : 0 : ovsdb_atom_destroy(&datum->values[src], value_type);
1109 : : }
1110 : : } else {
1111 [ - + ]: 381196 : if (src != dst) {
1112 : 0 : datum->keys[dst] = datum->keys[src];
1113 [ # # ]: 0 : if (value_type != OVSDB_TYPE_VOID) {
1114 : 0 : datum->values[dst] = datum->values[src];
1115 : : }
1116 : : }
1117 : 381196 : dst++;
1118 : : }
1119 : : }
1120 : 70829 : datum->n = dst;
1121 : 70829 : return datum->n - src;
1122 : : }
1123 : :
1124 : : /* Checks that each of the atoms in 'datum' conforms to the constraints
1125 : : * specified by its 'type'. Returns an error if a constraint is violated,
1126 : : * otherwise a null pointer.
1127 : : *
1128 : : * This function is not commonly useful because the most ordinary way to obtain
1129 : : * a datum is ultimately via ovsdb_atom_from_string() or
1130 : : * ovsdb_atom_from_json(), which check constraints themselves. */
1131 : : struct ovsdb_error *
1132 : 123717 : ovsdb_datum_check_constraints(const struct ovsdb_datum *datum,
1133 : : const struct ovsdb_type *type)
1134 : : {
1135 : : struct ovsdb_error *error;
1136 : : unsigned int i;
1137 : :
1138 [ + + ]: 247427 : for (i = 0; i < datum->n; i++) {
1139 : 123717 : error = ovsdb_atom_check_constraints(&datum->keys[i], &type->key);
1140 [ + + ]: 123717 : if (error) {
1141 : 7 : return error;
1142 : : }
1143 : : }
1144 : :
1145 [ + + ]: 123710 : if (type->value.type != OVSDB_TYPE_VOID) {
1146 [ + + ]: 11594 : for (i = 0; i < datum->n; i++) {
1147 : 5797 : error = ovsdb_atom_check_constraints(&datum->values[i],
1148 : : &type->value);
1149 [ - + ]: 5797 : if (error) {
1150 : 0 : return error;
1151 : : }
1152 : : }
1153 : : }
1154 : :
1155 : 123710 : return NULL;
1156 : : }
1157 : :
1158 : : static struct ovsdb_error *
1159 : 641949 : ovsdb_datum_from_json__(struct ovsdb_datum *datum,
1160 : : const struct ovsdb_type *type,
1161 : : const struct json *json,
1162 : : struct ovsdb_symbol_table *symtab)
1163 : : {
1164 : : struct ovsdb_error *error;
1165 : :
1166 [ + + ]: 641949 : if (ovsdb_type_is_map(type)
1167 [ + + ]: 555589 : || (json->type == JSON_ARRAY
1168 [ + - ]: 192156 : && json->u.array.n > 0
1169 [ + - ]: 192156 : && json->u.array.elems[0]->type == JSON_STRING
1170 [ + + ]: 192156 : && !strcmp(json->u.array.elems[0]->u.string, "set"))) {
1171 : 129172 : bool is_map = ovsdb_type_is_map(type);
1172 [ + + ]: 129172 : const char *class = is_map ? "map" : "set";
1173 : : const struct json *inner;
1174 : : unsigned int i;
1175 : : size_t n;
1176 : :
1177 : 129172 : error = unwrap_json(json, class, JSON_ARRAY, &inner);
1178 [ + + ]: 129172 : if (error) {
1179 : 12 : return error;
1180 : : }
1181 : :
1182 : 129160 : n = inner->u.array.n;
1183 [ + - ][ - + ]: 129160 : if (n < type->n_min || n > type->n_max) {
1184 : 0 : return ovsdb_syntax_error(json, NULL, "%s must have %u to "
1185 : : "%u members but %"PRIuSIZE" are present",
1186 : : class, type->n_min, type->n_max, n);
1187 : : }
1188 : :
1189 : 129160 : datum->n = 0;
1190 : 129160 : datum->keys = xmalloc(n * sizeof *datum->keys);
1191 [ + + ]: 129160 : datum->values = is_map ? xmalloc(n * sizeof *datum->values) : NULL;
1192 [ + + ]: 461432 : for (i = 0; i < n; i++) {
1193 : 332272 : const struct json *element = inner->u.array.elems[i];
1194 : 332272 : const struct json *key = NULL;
1195 : 332272 : const struct json *value = NULL;
1196 : :
1197 [ + + ]: 332272 : if (!is_map) {
1198 : 176892 : key = element;
1199 : : } else {
1200 : 155380 : error = parse_json_pair(element, &key, &value);
1201 [ - + ]: 155380 : if (error) {
1202 : 0 : goto error;
1203 : : }
1204 : : }
1205 : :
1206 : 332272 : error = ovsdb_atom_from_json(&datum->keys[i], &type->key,
1207 : : key, symtab);
1208 [ - + ]: 332272 : if (error) {
1209 : 0 : goto error;
1210 : : }
1211 : :
1212 [ + + ]: 332272 : if (is_map) {
1213 : 155380 : error = ovsdb_atom_from_json(&datum->values[i],
1214 : : &type->value, value, symtab);
1215 [ - + ]: 155380 : if (error) {
1216 : 0 : ovsdb_atom_destroy(&datum->keys[i], type->key.type);
1217 : 0 : goto error;
1218 : : }
1219 : : }
1220 : :
1221 : 332272 : datum->n++;
1222 : : }
1223 : 129160 : return NULL;
1224 : :
1225 : : error:
1226 : 0 : ovsdb_datum_destroy(datum, type);
1227 : 129172 : return error;
1228 : : } else {
1229 : 512777 : datum->n = 1;
1230 : 512777 : datum->keys = xmalloc(sizeof *datum->keys);
1231 : 512777 : datum->values = NULL;
1232 : :
1233 : 512777 : error = ovsdb_atom_from_json(&datum->keys[0], &type->key,
1234 : : json, symtab);
1235 [ + + ]: 512777 : if (error) {
1236 : 15 : free(datum->keys);
1237 : : }
1238 : 512777 : return error;
1239 : : }
1240 : : }
1241 : :
1242 : : /* Parses 'json' as a datum of the type described by 'type'. If successful,
1243 : : * returns NULL and initializes 'datum' with the parsed datum. On failure,
1244 : : * returns an error and the contents of 'datum' are indeterminate. The caller
1245 : : * is responsible for freeing the error or the datum that is returned.
1246 : : *
1247 : : * Violations of constraints expressed by 'type' are treated as errors.
1248 : : *
1249 : : * If 'symtab' is nonnull, then named UUIDs in 'symtab' are accepted. Refer to
1250 : : * RFC 7047 for information about this, and for the syntax that this function
1251 : : * accepts. */
1252 : : struct ovsdb_error *
1253 : 641949 : ovsdb_datum_from_json(struct ovsdb_datum *datum,
1254 : : const struct ovsdb_type *type,
1255 : : const struct json *json,
1256 : : struct ovsdb_symbol_table *symtab)
1257 : : {
1258 : : struct ovsdb_error *error;
1259 : :
1260 : 641949 : error = ovsdb_datum_from_json__(datum, type, json, symtab);
1261 [ + + ]: 641949 : if (error) {
1262 : 27 : return error;
1263 : : }
1264 : :
1265 : 641922 : error = ovsdb_datum_sort(datum, type->key.type);
1266 [ + + ]: 641922 : if (error) {
1267 : 6 : ovsdb_datum_destroy(datum, type);
1268 : : }
1269 : 641922 : return error;
1270 : : }
1271 : :
1272 : : /* Parses 'json' as a datum of the type described by 'type' for internal
1273 : : * use. This function is similar to 'ovsdb_datum_from_json', except the
1274 : : * member size of set or map is not checked.
1275 : : *
1276 : : * The datum generated should be used then discard. It is not suitable
1277 : : * for storing into IDL because of the possible member size violation. */
1278 : : struct ovsdb_error *
1279 : 45829 : ovsdb_transient_datum_from_json(struct ovsdb_datum *datum,
1280 : : const struct ovsdb_type *type,
1281 : : const struct json *json)
1282 : : {
1283 : 45829 : struct ovsdb_type relaxed_type = *type;
1284 : :
1285 : 45829 : relaxed_type.n_min = 0;
1286 : 45829 : relaxed_type.n_max = UINT_MAX;
1287 : :
1288 : 45829 : return ovsdb_datum_from_json(datum, &relaxed_type, json, NULL);
1289 : : }
1290 : :
1291 : : /* Converts 'datum', of the specified 'type', to JSON format, and returns the
1292 : : * JSON. The caller is responsible for freeing the returned JSON.
1293 : : *
1294 : : * 'type' constraints on datum->n are ignored.
1295 : : *
1296 : : * Refer to RFC 7047 for the format of the JSON that this function produces. */
1297 : : struct json *
1298 : 895498 : ovsdb_datum_to_json(const struct ovsdb_datum *datum,
1299 : : const struct ovsdb_type *type)
1300 : : {
1301 [ + + ]: 895498 : if (ovsdb_type_is_map(type)) {
1302 : : struct json **elems;
1303 : : size_t i;
1304 : :
1305 : 129757 : elems = xmalloc(datum->n * sizeof *elems);
1306 [ + + ]: 295096 : for (i = 0; i < datum->n; i++) {
1307 : 165339 : elems[i] = json_array_create_2(
1308 : 165339 : ovsdb_atom_to_json(&datum->keys[i], type->key.type),
1309 : 165339 : ovsdb_atom_to_json(&datum->values[i], type->value.type));
1310 : : }
1311 : :
1312 : 129757 : return wrap_json("map", json_array_create(elems, datum->n));
1313 [ + + ]: 765741 : } else if (datum->n == 1) {
1314 : 578909 : return ovsdb_atom_to_json(&datum->keys[0], type->key.type);
1315 : : } else {
1316 : : struct json **elems;
1317 : : size_t i;
1318 : :
1319 : 186832 : elems = xmalloc(datum->n * sizeof *elems);
1320 [ + + ]: 582034 : for (i = 0; i < datum->n; i++) {
1321 : 395202 : elems[i] = ovsdb_atom_to_json(&datum->keys[i], type->key.type);
1322 : : }
1323 : :
1324 : 186832 : return wrap_json("set", json_array_create(elems, datum->n));
1325 : : }
1326 : : }
1327 : :
1328 : : static const char *
1329 : 20260 : skip_spaces(const char *p)
1330 : : {
1331 [ + + ]: 56305 : while (isspace((unsigned char) *p)) {
1332 : 36045 : p++;
1333 : : }
1334 : 20260 : return p;
1335 : : }
1336 : :
1337 : : static char *
1338 : 9357 : parse_atom_token(const char **s, const struct ovsdb_base_type *base,
1339 : : union ovsdb_atom *atom, struct ovsdb_symbol_table *symtab)
1340 : : {
1341 : : char *token, *error;
1342 : :
1343 : 9357 : error = ovsdb_token_parse(s, &token);
1344 [ + - ]: 9357 : if (!error) {
1345 : 9357 : error = ovsdb_atom_from_string(atom, base, token, symtab);
1346 : 9357 : free(token);
1347 : : }
1348 : 9357 : return error;
1349 : : }
1350 : :
1351 : : static char *
1352 : 9295 : parse_key_value(const char **s, const struct ovsdb_type *type,
1353 : : union ovsdb_atom *key, union ovsdb_atom *value,
1354 : : struct ovsdb_symbol_table *symtab)
1355 : : {
1356 : 9295 : const char *start = *s;
1357 : : char *error;
1358 : :
1359 : 9295 : error = parse_atom_token(s, &type->key, key, symtab);
1360 [ + + ][ + + ]: 9295 : if (!error && type->value.type != OVSDB_TYPE_VOID) {
1361 : 95 : *s = skip_spaces(*s);
1362 [ + + ]: 95 : if (**s == '=') {
1363 : 62 : (*s)++;
1364 : 62 : *s = skip_spaces(*s);
1365 : 62 : error = parse_atom_token(s, &type->value, value, symtab);
1366 : : } else {
1367 : 33 : error = xasprintf("%s: syntax error at \"%c\" expecting \"=\"",
1368 : 33 : start, **s);
1369 : : }
1370 [ + + ]: 95 : if (error) {
1371 : 33 : ovsdb_atom_destroy(key, type->key.type);
1372 : : }
1373 : : }
1374 : 9295 : return error;
1375 : : }
1376 : :
1377 : : static void
1378 : 9258 : free_key_value(const struct ovsdb_type *type,
1379 : : union ovsdb_atom *key, union ovsdb_atom *value)
1380 : : {
1381 : 9258 : ovsdb_atom_destroy(key, type->key.type);
1382 [ + + ]: 9258 : if (type->value.type != OVSDB_TYPE_VOID) {
1383 : 62 : ovsdb_atom_destroy(value, type->value.type);
1384 : : }
1385 : 9258 : }
1386 : :
1387 : : /* Initializes 'datum' as a datum of the given 'type', parsing its contents
1388 : : * from 's'. The format of 's' is a series of space or comma separated atoms
1389 : : * or, for a map, '='-delimited pairs of atoms. Each atom must in a format
1390 : : * acceptable to ovsdb_atom_from_string(). Optionally, a set may be enclosed
1391 : : * in "[]" or a map in "{}"; for an empty set or map these punctuators are
1392 : : * required.
1393 : : *
1394 : : * Optionally, a symbol table may be supplied as 'symtab'. It is passed to
1395 : : * ovsdb_atom_to_string(). */
1396 : : char *
1397 : 5868 : ovsdb_datum_from_string(struct ovsdb_datum *datum,
1398 : : const struct ovsdb_type *type, const char *s,
1399 : : struct ovsdb_symbol_table *symtab)
1400 : : {
1401 : 5868 : bool is_map = ovsdb_type_is_map(type);
1402 : : struct ovsdb_error *dberror;
1403 : : const char *p;
1404 : : int end_delim;
1405 : : char *error;
1406 : :
1407 : 5868 : ovsdb_datum_init_empty(datum);
1408 : :
1409 : : /* Swallow a leading delimiter if there is one. */
1410 : 5868 : p = skip_spaces(s);
1411 [ + + ][ + + ]: 5868 : if (*p == (is_map ? '{' : '[')) {
1412 [ + + ]: 680 : end_delim = is_map ? '}' : ']';
1413 : 680 : p = skip_spaces(p + 1);
1414 [ - + ]: 5188 : } else if (!*p) {
1415 [ # # ]: 0 : if (is_map) {
1416 : 0 : return xstrdup("use \"{}\" to specify the empty map");
1417 : : } else {
1418 : 0 : return xstrdup("use \"[]\" to specify the empty set");
1419 : : }
1420 : : } else {
1421 : 5188 : end_delim = 0;
1422 : : }
1423 : :
1424 [ + + ][ + + ]: 15126 : while (*p && *p != end_delim) {
1425 : : union ovsdb_atom key, value;
1426 : :
1427 [ - + ]: 9295 : if (ovsdb_token_is_delim(*p)) {
1428 : 0 : char *type_str = ovsdb_type_to_english(type);
1429 : 0 : error = xasprintf("%s: unexpected \"%c\" parsing %s",
1430 : 0 : s, *p, type_str);
1431 : 0 : free(type_str);
1432 : 37 : goto error;
1433 : : }
1434 : :
1435 : : /* Add to datum. */
1436 : 9295 : error = parse_key_value(&p, type, &key, &value, symtab);
1437 [ + + ]: 9295 : if (error) {
1438 : 37 : goto error;
1439 : : }
1440 : 9258 : ovsdb_datum_add_unsafe(datum, &key, &value, type);
1441 : 9258 : free_key_value(type, &key, &value);
1442 : :
1443 : : /* Skip optional white space and comma. */
1444 : 9258 : p = skip_spaces(p);
1445 [ + + ]: 9258 : if (*p == ',') {
1446 : 9258 : p = skip_spaces(p + 1);
1447 : : }
1448 : : }
1449 : :
1450 [ - + ]: 5831 : if (*p != end_delim) {
1451 : 0 : error = xasprintf("%s: missing \"%c\" at end of data", s, end_delim);
1452 : 0 : goto error;
1453 : : }
1454 [ + + ]: 5831 : if (end_delim) {
1455 : 680 : p = skip_spaces(p + 1);
1456 [ - + ]: 680 : if (*p) {
1457 : 0 : error = xasprintf("%s: trailing garbage after \"%c\"",
1458 : : s, end_delim);
1459 : 0 : goto error;
1460 : : }
1461 : : }
1462 : :
1463 [ - + ]: 5831 : if (datum->n < type->n_min) {
1464 [ # # ]: 0 : error = xasprintf("%s: %u %s specified but the minimum number is %u",
1465 : : s, datum->n, is_map ? "pair(s)" : "value(s)",
1466 : : type->n_min);
1467 : 0 : goto error;
1468 [ + + ]: 5831 : } else if (datum->n > type->n_max) {
1469 [ - + ]: 1 : error = xasprintf("%s: %u %s specified but the maximum number is %u",
1470 : : s, datum->n, is_map ? "pair(s)" : "value(s)",
1471 : : type->n_max);
1472 : 1 : goto error;
1473 : : }
1474 : :
1475 : 5830 : dberror = ovsdb_datum_sort(datum, type->key.type);
1476 [ + + ]: 5830 : if (dberror) {
1477 : 7 : ovsdb_error_destroy(dberror);
1478 [ + + ]: 7 : if (ovsdb_type_is_map(type)) {
1479 : 1 : error = xasprintf("%s: map contains duplicate key", s);
1480 : : } else {
1481 : 6 : error = xasprintf("%s: set contains duplicate value", s);
1482 : : }
1483 : 7 : goto error;
1484 : : }
1485 : :
1486 : 5823 : return NULL;
1487 : :
1488 : : error:
1489 : 45 : ovsdb_datum_destroy(datum, type);
1490 : 45 : ovsdb_datum_init_empty(datum);
1491 : 5868 : return error;
1492 : : }
1493 : :
1494 : : /* Appends to 'out' the 'datum' (with the given 'type') in a format acceptable
1495 : : * to ovsdb_datum_from_string(). */
1496 : : void
1497 : 23726 : ovsdb_datum_to_string(const struct ovsdb_datum *datum,
1498 : : const struct ovsdb_type *type, struct ds *out)
1499 : : {
1500 : 23726 : bool is_map = ovsdb_type_is_map(type);
1501 : : size_t i;
1502 : :
1503 [ + + ][ + + ]: 23726 : if (type->n_max > 1 || !datum->n) {
1504 [ + + ]: 12766 : ds_put_char(out, is_map ? '{' : '[');
1505 : : }
1506 [ + + ]: 37546 : for (i = 0; i < datum->n; i++) {
1507 [ + + ]: 13820 : if (i > 0) {
1508 : 1118 : ds_put_cstr(out, ", ");
1509 : : }
1510 : :
1511 : 13820 : ovsdb_atom_to_string(&datum->keys[i], type->key.type, out);
1512 [ + + ]: 13820 : if (is_map) {
1513 : 2096 : ds_put_char(out, '=');
1514 : 2096 : ovsdb_atom_to_string(&datum->values[i], type->value.type, out);
1515 : : }
1516 : : }
1517 [ + + ][ + + ]: 23726 : if (type->n_max > 1 || !datum->n) {
1518 [ + + ]: 12766 : ds_put_char(out, is_map ? '}' : ']');
1519 : : }
1520 : 23726 : }
1521 : :
1522 : : /* Appends to 'out' the 'datum' (with the given 'type') in a bare string format
1523 : : * that cannot be parsed uniformly back into a datum but is easier for shell
1524 : : * scripts, etc., to deal with. */
1525 : : void
1526 : 1065 : ovsdb_datum_to_bare(const struct ovsdb_datum *datum,
1527 : : const struct ovsdb_type *type, struct ds *out)
1528 : : {
1529 : 1065 : bool is_map = ovsdb_type_is_map(type);
1530 : : size_t i;
1531 : :
1532 [ + + ]: 2130 : for (i = 0; i < datum->n; i++) {
1533 [ - + ]: 1065 : if (i > 0) {
1534 : 0 : ds_put_cstr(out, " ");
1535 : : }
1536 : :
1537 : 1065 : ovsdb_atom_to_bare(&datum->keys[i], type->key.type, out);
1538 [ - + ]: 1065 : if (is_map) {
1539 : 0 : ds_put_char(out, '=');
1540 : 0 : ovsdb_atom_to_bare(&datum->values[i], type->value.type, out);
1541 : : }
1542 : : }
1543 : 1065 : }
1544 : :
1545 : : /* Initializes 'datum' as a string-to-string map whose contents are taken from
1546 : : * 'smap'. Destroys 'smap'. */
1547 : : void
1548 : 0 : ovsdb_datum_from_smap(struct ovsdb_datum *datum, struct smap *smap)
1549 : : {
1550 : : struct smap_node *node, *next;
1551 : : size_t i;
1552 : :
1553 : 0 : datum->n = smap_count(smap);
1554 : 0 : datum->keys = xmalloc(datum->n * sizeof *datum->keys);
1555 : 0 : datum->values = xmalloc(datum->n * sizeof *datum->values);
1556 : :
1557 : 0 : i = 0;
1558 [ # # ][ # # ]: 0 : SMAP_FOR_EACH_SAFE (node, next, smap) {
[ # # ]
1559 : 0 : smap_steal(smap, node,
1560 : 0 : &datum->keys[i].string, &datum->values[i].string);
1561 : 0 : i++;
1562 : : }
1563 [ # # ]: 0 : ovs_assert(i == datum->n);
1564 : :
1565 : 0 : smap_destroy(smap);
1566 : 0 : ovsdb_datum_sort_unique(datum, OVSDB_TYPE_STRING, OVSDB_TYPE_STRING);
1567 : 0 : }
1568 : :
1569 : : static uint32_t
1570 : 392398 : hash_atoms(enum ovsdb_atomic_type type, const union ovsdb_atom *atoms,
1571 : : unsigned int n, uint32_t basis)
1572 : : {
1573 [ + + ]: 392398 : if (type != OVSDB_TYPE_VOID) {
1574 : : unsigned int i;
1575 : :
1576 [ + + ]: 460848 : for (i = 0; i < n; i++) {
1577 : 262270 : basis = ovsdb_atom_hash(&atoms[i], type, basis);
1578 : : }
1579 : : }
1580 : 392398 : return basis;
1581 : : }
1582 : :
1583 : : uint32_t
1584 : 196199 : ovsdb_datum_hash(const struct ovsdb_datum *datum,
1585 : : const struct ovsdb_type *type, uint32_t basis)
1586 : : {
1587 : 196199 : basis = hash_atoms(type->key.type, datum->keys, datum->n, basis);
1588 : 196199 : basis ^= (type->key.type << 24) | (type->value.type << 16) | datum->n;
1589 : 196199 : basis = hash_atoms(type->value.type, datum->values, datum->n, basis);
1590 : 196199 : return basis;
1591 : : }
1592 : :
1593 : : static int
1594 : 2560259 : atom_arrays_compare_3way(const union ovsdb_atom *a,
1595 : : const union ovsdb_atom *b,
1596 : : enum ovsdb_atomic_type type,
1597 : : size_t n)
1598 : : {
1599 : : unsigned int i;
1600 : :
1601 [ + + ]: 4067920 : for (i = 0; i < n; i++) {
1602 : 1844211 : int cmp = ovsdb_atom_compare_3way(&a[i], &b[i], type);
1603 [ + + ]: 1844211 : if (cmp) {
1604 : 336550 : return cmp;
1605 : : }
1606 : : }
1607 : :
1608 : 2223709 : return 0;
1609 : : }
1610 : :
1611 : : bool
1612 : 2404990 : ovsdb_datum_equals(const struct ovsdb_datum *a,
1613 : : const struct ovsdb_datum *b,
1614 : : const struct ovsdb_type *type)
1615 : : {
1616 : 2404990 : return !ovsdb_datum_compare_3way(a, b, type);
1617 : : }
1618 : :
1619 : : int
1620 : 2406528 : ovsdb_datum_compare_3way(const struct ovsdb_datum *a,
1621 : : const struct ovsdb_datum *b,
1622 : : const struct ovsdb_type *type)
1623 : : {
1624 : : int cmp;
1625 : :
1626 [ + + ]: 2406528 : if (a->n != b->n) {
1627 [ + + ]: 256237 : return a->n < b->n ? -1 : 1;
1628 : : }
1629 : :
1630 : 2150291 : cmp = atom_arrays_compare_3way(a->keys, b->keys, type->key.type, a->n);
1631 [ + + ]: 2150291 : if (cmp) {
1632 : 318456 : return cmp;
1633 : : }
1634 : :
1635 : 1831835 : return (type->value.type == OVSDB_TYPE_VOID ? 0
1636 [ + + ]: 1831835 : : atom_arrays_compare_3way(a->values, b->values, type->value.type,
1637 : 409968 : a->n));
1638 : : }
1639 : :
1640 : : /* If 'key' is one of the keys in 'datum', returns its index within 'datum',
1641 : : * otherwise UINT_MAX. 'key.type' must be the type of the atoms stored in the
1642 : : * 'keys' array in 'datum'.
1643 : : */
1644 : : unsigned int
1645 : 70219 : ovsdb_datum_find_key(const struct ovsdb_datum *datum,
1646 : : const union ovsdb_atom *key,
1647 : : enum ovsdb_atomic_type key_type)
1648 : : {
1649 : 70219 : unsigned int low = 0;
1650 : 70219 : unsigned int high = datum->n;
1651 [ + + ]: 122960 : while (low < high) {
1652 : 119682 : unsigned int idx = (low + high) / 2;
1653 : 119682 : int cmp = ovsdb_atom_compare_3way(key, &datum->keys[idx], key_type);
1654 [ + + ]: 119682 : if (cmp < 0) {
1655 : 38680 : high = idx;
1656 [ + + ]: 81002 : } else if (cmp > 0) {
1657 : 14061 : low = idx + 1;
1658 : : } else {
1659 : 66941 : return idx;
1660 : : }
1661 : : }
1662 : 3278 : return UINT_MAX;
1663 : : }
1664 : :
1665 : : /* If 'key' and 'value' is one of the key-value pairs in 'datum', returns its
1666 : : * index within 'datum', otherwise UINT_MAX. 'key.type' must be the type of
1667 : : * the atoms stored in the 'keys' array in 'datum'. 'value_type' may be the
1668 : : * type of the 'values' atoms or OVSDB_TYPE_VOID to compare only keys.
1669 : : */
1670 : : unsigned int
1671 : 1408 : ovsdb_datum_find_key_value(const struct ovsdb_datum *datum,
1672 : : const union ovsdb_atom *key,
1673 : : enum ovsdb_atomic_type key_type,
1674 : : const union ovsdb_atom *value,
1675 : : enum ovsdb_atomic_type value_type)
1676 : : {
1677 : 1408 : unsigned int idx = ovsdb_datum_find_key(datum, key, key_type);
1678 [ + + ]: 1408 : if (idx != UINT_MAX
1679 [ + + ]: 684 : && value_type != OVSDB_TYPE_VOID
1680 [ + + ]: 425 : && !ovsdb_atom_equals(&datum->values[idx], value, value_type)) {
1681 : 81 : idx = UINT_MAX;
1682 : : }
1683 : 1408 : return idx;
1684 : : }
1685 : :
1686 : : /* If atom 'i' in 'a' is also in 'b', returns its index in 'b', otherwise
1687 : : * UINT_MAX. 'type' must be the type of 'a' and 'b', except that
1688 : : * type->value.type may be set to OVSDB_TYPE_VOID to compare keys but not
1689 : : * values. */
1690 : : static unsigned int
1691 : 1408 : ovsdb_datum_find(const struct ovsdb_datum *a, int i,
1692 : : const struct ovsdb_datum *b,
1693 : : const struct ovsdb_type *type)
1694 : : {
1695 [ + + ]: 1408 : return ovsdb_datum_find_key_value(b,
1696 : 2816 : &a->keys[i], type->key.type,
1697 : 2196 : a->values ? &a->values[i] : NULL,
1698 : : type->value.type);
1699 : : }
1700 : :
1701 : : /* Returns true if every element in 'a' is also in 'b', false otherwise. */
1702 : : bool
1703 : 725 : ovsdb_datum_includes_all(const struct ovsdb_datum *a,
1704 : : const struct ovsdb_datum *b,
1705 : : const struct ovsdb_type *type)
1706 : : {
1707 : : size_t i;
1708 : :
1709 [ + + ]: 725 : if (a->n > b->n) {
1710 : 209 : return false;
1711 : : }
1712 [ + + ]: 772 : for (i = 0; i < a->n; i++) {
1713 [ + + ]: 457 : if (ovsdb_datum_find(a, i, b, type) == UINT_MAX) {
1714 : 201 : return false;
1715 : : }
1716 : : }
1717 : 315 : return true;
1718 : : }
1719 : :
1720 : : /* Returns true if no element in 'a' is also in 'b', false otherwise. */
1721 : : bool
1722 : 496 : ovsdb_datum_excludes_all(const struct ovsdb_datum *a,
1723 : : const struct ovsdb_datum *b,
1724 : : const struct ovsdb_type *type)
1725 : : {
1726 : : size_t i;
1727 : :
1728 [ + + ]: 830 : for (i = 0; i < a->n; i++) {
1729 [ + + ]: 592 : if (ovsdb_datum_find(a, i, b, type) != UINT_MAX) {
1730 : 258 : return false;
1731 : : }
1732 : : }
1733 : 238 : return true;
1734 : : }
1735 : :
1736 : : static void
1737 : 1618 : ovsdb_datum_reallocate(struct ovsdb_datum *a, const struct ovsdb_type *type,
1738 : : unsigned int capacity)
1739 : : {
1740 : 1618 : a->keys = xrealloc(a->keys, capacity * sizeof *a->keys);
1741 [ + + ]: 1618 : if (type->value.type != OVSDB_TYPE_VOID) {
1742 : 1509 : a->values = xrealloc(a->values, capacity * sizeof *a->values);
1743 : : }
1744 : 1618 : }
1745 : :
1746 : : /* Removes the element with index 'idx' from 'datum', which has type 'type'.
1747 : : * If 'idx' is not the last element in 'datum', then the removed element is
1748 : : * replaced by the (former) last element.
1749 : : *
1750 : : * This function does not maintain ovsdb_datum invariants. Use
1751 : : * ovsdb_datum_sort() to check and restore these invariants. */
1752 : : void
1753 : 145 : ovsdb_datum_remove_unsafe(struct ovsdb_datum *datum, size_t idx,
1754 : : const struct ovsdb_type *type)
1755 : : {
1756 : 145 : ovsdb_atom_destroy(&datum->keys[idx], type->key.type);
1757 : 145 : datum->keys[idx] = datum->keys[datum->n - 1];
1758 [ + + ]: 145 : if (type->value.type != OVSDB_TYPE_VOID) {
1759 : 21 : ovsdb_atom_destroy(&datum->values[idx], type->value.type);
1760 : 21 : datum->values[idx] = datum->values[datum->n - 1];
1761 : : }
1762 : 145 : datum->n--;
1763 : 145 : }
1764 : :
1765 : : /* Adds the element with the given 'key' and 'value' to 'datum', which must
1766 : : * have the specified 'type'.
1767 : : *
1768 : : * This function always allocates memory, so it is not an efficient way to add
1769 : : * a number of elements to a datum.
1770 : : *
1771 : : * This function does not maintain ovsdb_datum invariants. Use
1772 : : * ovsdb_datum_sort() to check and restore these invariants. (But a datum with
1773 : : * 0 or 1 elements cannot violate the invariants anyhow.) */
1774 : : void
1775 : 149875 : ovsdb_datum_add_unsafe(struct ovsdb_datum *datum,
1776 : : const union ovsdb_atom *key,
1777 : : const union ovsdb_atom *value,
1778 : : const struct ovsdb_type *type)
1779 : : {
1780 : 149875 : size_t idx = datum->n++;
1781 : 149875 : datum->keys = xrealloc(datum->keys, datum->n * sizeof *datum->keys);
1782 : 149875 : ovsdb_atom_clone(&datum->keys[idx], key, type->key.type);
1783 [ + + ]: 149875 : if (type->value.type != OVSDB_TYPE_VOID) {
1784 : 60939 : datum->values = xrealloc(datum->values,
1785 : 60939 : datum->n * sizeof *datum->values);
1786 : 60939 : ovsdb_atom_clone(&datum->values[idx], value, type->value.type);
1787 : : }
1788 : 149875 : }
1789 : :
1790 : : void
1791 : 3662 : ovsdb_datum_union(struct ovsdb_datum *a, const struct ovsdb_datum *b,
1792 : : const struct ovsdb_type *type, bool replace)
1793 : : {
1794 : : unsigned int n;
1795 : : size_t bi;
1796 : :
1797 : 3662 : n = a->n;
1798 [ + + ]: 6058 : for (bi = 0; bi < b->n; bi++) {
1799 : : unsigned int ai;
1800 : :
1801 : 2396 : ai = ovsdb_datum_find_key(a, &b->keys[bi], type->key.type);
1802 [ + + ]: 2396 : if (ai == UINT_MAX) {
1803 [ + + ]: 2255 : if (n == a->n) {
1804 : 1618 : ovsdb_datum_reallocate(a, type, a->n + (b->n - bi));
1805 : : }
1806 : 2255 : ovsdb_atom_clone(&a->keys[n], &b->keys[bi], type->key.type);
1807 [ + + ]: 2255 : if (type->value.type != OVSDB_TYPE_VOID) {
1808 : 2136 : ovsdb_atom_clone(&a->values[n], &b->values[bi],
1809 : : type->value.type);
1810 : : }
1811 : 2255 : n++;
1812 [ - + ][ # # ]: 141 : } else if (replace && type->value.type != OVSDB_TYPE_VOID) {
1813 : 0 : ovsdb_atom_destroy(&a->values[ai], type->value.type);
1814 : 0 : ovsdb_atom_clone(&a->values[ai], &b->values[bi],
1815 : : type->value.type);
1816 : : }
1817 : : }
1818 [ + + ]: 3662 : if (n != a->n) {
1819 : : struct ovsdb_error *error;
1820 : 1618 : a->n = n;
1821 : 1618 : error = ovsdb_datum_sort(a, type->key.type);
1822 [ - + ]: 1618 : ovs_assert(!error);
1823 : : }
1824 : 3662 : }
1825 : :
1826 : : void
1827 : 157 : ovsdb_datum_subtract(struct ovsdb_datum *a, const struct ovsdb_type *a_type,
1828 : : const struct ovsdb_datum *b,
1829 : : const struct ovsdb_type *b_type)
1830 : : {
1831 : 157 : bool changed = false;
1832 : : size_t i;
1833 : :
1834 [ - + ]: 157 : ovs_assert(a_type->key.type == b_type->key.type);
1835 [ + + ][ - + ]: 157 : ovs_assert(a_type->value.type == b_type->value.type
1836 : : || b_type->value.type == OVSDB_TYPE_VOID);
1837 : :
1838 : : /* XXX The big-O of this could easily be improved. */
1839 [ + + ]: 516 : for (i = 0; i < a->n; ) {
1840 : 359 : unsigned int idx = ovsdb_datum_find(a, i, b, b_type);
1841 [ + + ]: 359 : if (idx != UINT_MAX) {
1842 : 89 : changed = true;
1843 : 89 : ovsdb_datum_remove_unsafe(a, i, a_type);
1844 : : } else {
1845 : 270 : i++;
1846 : : }
1847 : : }
1848 [ + + ]: 157 : if (changed) {
1849 : 81 : ovsdb_datum_sort_assert(a, a_type->key.type);
1850 : : }
1851 : 157 : }
1852 : :
1853 : : struct ovsdb_symbol_table *
1854 : 18938 : ovsdb_symbol_table_create(void)
1855 : : {
1856 : 18938 : struct ovsdb_symbol_table *symtab = xmalloc(sizeof *symtab);
1857 : 18938 : shash_init(&symtab->sh);
1858 : 18938 : return symtab;
1859 : : }
1860 : :
1861 : : void
1862 : 18743 : ovsdb_symbol_table_destroy(struct ovsdb_symbol_table *symtab)
1863 : : {
1864 [ + - ]: 18743 : if (symtab) {
1865 : 18743 : shash_destroy_free_data(&symtab->sh);
1866 : 18743 : free(symtab);
1867 : : }
1868 : 18743 : }
1869 : :
1870 : : struct ovsdb_symbol *
1871 : 45967 : ovsdb_symbol_table_get(const struct ovsdb_symbol_table *symtab,
1872 : : const char *name)
1873 : : {
1874 : 45967 : return shash_find_data(&symtab->sh, name);
1875 : : }
1876 : :
1877 : : struct ovsdb_symbol *
1878 : 16689 : ovsdb_symbol_table_put(struct ovsdb_symbol_table *symtab, const char *name,
1879 : : const struct uuid *uuid, bool created)
1880 : : {
1881 : : struct ovsdb_symbol *symbol;
1882 : :
1883 [ - + ]: 16689 : ovs_assert(!ovsdb_symbol_table_get(symtab, name));
1884 : 16689 : symbol = xmalloc(sizeof *symbol);
1885 : 16689 : symbol->uuid = *uuid;
1886 : 16689 : symbol->created = created;
1887 : 16689 : symbol->strong_ref = false;
1888 : 16689 : symbol->weak_ref = false;
1889 : 16689 : shash_add(&symtab->sh, name, symbol);
1890 : 16689 : return symbol;
1891 : : }
1892 : :
1893 : : struct ovsdb_symbol *
1894 : 28972 : ovsdb_symbol_table_insert(struct ovsdb_symbol_table *symtab,
1895 : : const char *name)
1896 : : {
1897 : : struct ovsdb_symbol *symbol;
1898 : :
1899 : 28972 : symbol = ovsdb_symbol_table_get(symtab, name);
1900 [ + + ]: 28972 : if (!symbol) {
1901 : : struct uuid uuid;
1902 : :
1903 : 16666 : uuid_generate(&uuid);
1904 : 16666 : symbol = ovsdb_symbol_table_put(symtab, name, &uuid, false);
1905 : : }
1906 : 28972 : return symbol;
1907 : : }
1908 : :
1909 : : /* APIs for Generating and apply diffs. */
1910 : :
1911 : : /* Generate a difference ovsdb_dataum between 'old' and 'new'.
1912 : : * 'new' can be regenerated by applying the difference to the 'old'.
1913 : : *
1914 : : * The diff operation is reversible. Given 'old',
1915 : : * 'new' can be recreated by applying diff to 'old'.
1916 : : *
1917 : : * Thus
1918 : : * Let d = 'old' diff 'new'
1919 : : * then 'new' = 'old' diff d
1920 : : *
1921 : : * The 'diff' datum is always safe; the orders of keys are maintained
1922 : : * since they are added in order. */
1923 : : void
1924 : 91089 : ovsdb_datum_diff(struct ovsdb_datum *diff,
1925 : : const struct ovsdb_datum *old,
1926 : : const struct ovsdb_datum *new,
1927 : : const struct ovsdb_type *type)
1928 : : {
1929 : : size_t oi, ni;
1930 : :
1931 : 91089 : ovsdb_datum_init_empty(diff);
1932 [ + + ]: 91089 : if (!ovsdb_type_is_composite(type)) {
1933 : 63468 : ovsdb_datum_clone(diff, new, type);
1934 : 63468 : return;
1935 : : }
1936 : :
1937 : : /* Generate the diff in O(n) time. */
1938 [ + + ][ + + ]: 136870 : for (oi = ni = 0; oi < old->n && ni < new->n; ) {
1939 : 109249 : int c = ovsdb_atom_compare_3way(&old->keys[oi], &new->keys[ni],
1940 : : type->key.type);
1941 [ + + ]: 109249 : if (c < 0) {
1942 : 30166 : ovsdb_datum_add_unsafe(diff, &old->keys[oi], &old->values[oi],
1943 : : type);
1944 : 30166 : oi++;
1945 [ + + ]: 79083 : } else if (c > 0) {
1946 : 5167 : ovsdb_datum_add_unsafe(diff, &new->keys[ni], &new->values[ni],
1947 : : type);
1948 : 5167 : ni++;
1949 : : } else {
1950 [ + + + + ]: 98819 : if (type->value.type != OVSDB_TYPE_VOID &&
1951 : 24903 : ovsdb_atom_compare_3way(&old->values[oi], &new->values[ni],
1952 : : type->value.type)) {
1953 : 18199 : ovsdb_datum_add_unsafe(diff, &new->keys[ni], &new->values[ni],
1954 : : type);
1955 : : }
1956 : 73916 : oi++; ni++;
1957 : : }
1958 : : }
1959 : :
1960 [ + + ]: 54040 : for (; oi < old->n; oi++) {
1961 : 26419 : ovsdb_datum_add_unsafe(diff, &old->keys[oi], &old->values[oi], type);
1962 : : }
1963 : :
1964 [ + + ]: 84776 : for (; ni < new->n; ni++) {
1965 : 57155 : ovsdb_datum_add_unsafe(diff, &new->keys[ni], &new->values[ni], type);
1966 : : }
1967 : : }
1968 : :
1969 : : /* Apply 'diff' to 'old' to regenerate 'new'.
1970 : : *
1971 : : * Return NULL if the 'new' is successfully generated, otherwise, return
1972 : : * ovsdb_error and the stat of 'new' is indeterministic. */
1973 : : struct ovsdb_error *
1974 : 45829 : ovsdb_datum_apply_diff(struct ovsdb_datum *new,
1975 : : const struct ovsdb_datum *old,
1976 : : const struct ovsdb_datum *diff,
1977 : : const struct ovsdb_type *type)
1978 : : {
1979 : 45829 : ovsdb_datum_init_empty(new);
1980 : 45829 : ovsdb_datum_diff(new, old, diff, type);
1981 : :
1982 : : /* Make sure member size of 'new' conforms to type. */
1983 [ + - ][ + + ]: 45829 : if (new->n < type->n_min || new->n > type->n_max) {
1984 : 2 : ovsdb_datum_destroy(new, type);
1985 : 2 : return ovsdb_error(NULL, "Datum crated by diff has size error");
1986 : : }
1987 : :
1988 : 45827 : return NULL;
1989 : : }
1990 : :
1991 : :
1992 : : /* Extracts a token from the beginning of 's' and returns a pointer just after
1993 : : * the token. Stores the token itself into '*outp', which the caller is
1994 : : * responsible for freeing (with free()).
1995 : : *
1996 : : * If 's[0]' is a delimiter, the returned token is the empty string.
1997 : : *
1998 : : * A token extends from 's' to the first delimiter, as defined by
1999 : : * ovsdb_token_is_delim(), or until the end of the string. A delimiter can be
2000 : : * escaped with a backslash, in which case the backslash does not appear in the
2001 : : * output. Double quotes also cause delimiters to be ignored, but the double
2002 : : * quotes are retained in the output. (Backslashes inside double quotes are
2003 : : * not removed, either.)
2004 : : */
2005 : : char *
2006 : 32525 : ovsdb_token_parse(const char **s, char **outp)
2007 : : {
2008 : : const char *p;
2009 : : struct ds out;
2010 : : bool in_quotes;
2011 : : char *error;
2012 : :
2013 : 32525 : ds_init(&out);
2014 : 32525 : in_quotes = false;
2015 [ + + ]: 302241 : for (p = *s; *p != '\0'; ) {
2016 : 295416 : int c = *p++;
2017 [ + + ]: 295416 : if (c == '\\') {
2018 [ + + ]: 10 : if (in_quotes) {
2019 : 8 : ds_put_char(&out, '\\');
2020 : : }
2021 [ - + ]: 10 : if (!*p) {
2022 : 0 : error = xasprintf("%s: backslash at end of argument", *s);
2023 : 0 : goto error;
2024 : : }
2025 : 10 : ds_put_char(&out, *p++);
2026 [ + + ][ + + ]: 295406 : } else if (!in_quotes && ovsdb_token_is_delim(c)) {
2027 : 25700 : p--;
2028 : 25700 : break;
2029 : : } else {
2030 : 269706 : ds_put_char(&out, c);
2031 [ + + ]: 269706 : if (c == '"') {
2032 : 438 : in_quotes = !in_quotes;
2033 : : }
2034 : : }
2035 : : }
2036 [ - + ]: 32525 : if (in_quotes) {
2037 : 0 : error = xasprintf("%s: quoted string extends past end of argument",
2038 : : *s);
2039 : 0 : goto error;
2040 : : }
2041 : 32525 : *outp = ds_cstr(&out);
2042 : 32525 : *s = p;
2043 : 32525 : return NULL;
2044 : :
2045 : : error:
2046 : 0 : ds_destroy(&out);
2047 : 0 : *outp = NULL;
2048 : 32525 : return error;
2049 : : }
2050 : :
2051 : : /* Returns true if 'c' delimits tokens, or if 'c' is 0, and false otherwise. */
2052 : : bool
2053 : 302283 : ovsdb_token_is_delim(unsigned char c)
2054 : : {
2055 : 302283 : return strchr(":=, []{}!<>", c) != NULL;
2056 : : }
|
