1 /* $OpenBSD: mdesc.c,v 1.13 2019/11/28 18:40:42 kn Exp $ */ 2 3 /* 4 * Copyright (c) 2012 Mark Kettenis 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #include <sys/types.h> 20 #include <sys/queue.h> 21 #include <err.h> 22 #include <stdbool.h> 23 #include <stdio.h> 24 #include <stdlib.h> 25 #include <string.h> 26 27 #include "mdesc.h" 28 #include "ldom_util.h" 29 30 struct md_name * 31 md_find_name(struct md *md, const char *str) 32 { 33 struct md_name *name; 34 35 TAILQ_FOREACH(name, &md->name_list, link) 36 if (strcmp(name->str, str) == 0) 37 return name; 38 return NULL; 39 } 40 41 struct md_name * 42 md_add_name(struct md *md, const char *str) 43 { 44 struct md_name *name; 45 46 name = md_find_name(md, str); 47 if (name == NULL) { 48 name = xmalloc(sizeof(*name)); 49 name->str = xstrdup(str); 50 TAILQ_INSERT_TAIL(&md->name_list, name, link); 51 name->refcnt = 0; 52 } 53 name->refcnt++; 54 return name; 55 } 56 57 void 58 md_free_name(struct md *md, struct md_name *name) 59 { 60 if (name->refcnt > 1) { 61 name->refcnt--; 62 return; 63 } 64 65 TAILQ_REMOVE(&md->name_list, name, link); 66 free(name); 67 } 68 69 struct md_data * 70 md_find_data(struct md *md, const uint8_t *b, size_t len) 71 { 72 struct md_data *data; 73 74 TAILQ_FOREACH(data, &md->data_list, link) 75 if (data->len == len && 76 memcmp(data->data, b, len) == 0) 77 return data; 78 79 return NULL; 80 } 81 82 struct md_data * 83 md_add_data(struct md *md, const uint8_t *b, size_t len) 84 { 85 struct md_data *data; 86 87 data = md_find_data(md, b, len); 88 if (data == NULL) { 89 data = xmalloc(sizeof(*data)); 90 data->data = xmalloc(len); 91 memcpy(data->data, b, len); 92 data->len = len; 93 TAILQ_INSERT_TAIL(&md->data_list, data, link); 94 data->refcnt = 0; 95 } 96 data->refcnt++; 97 return data; 98 } 99 100 void 101 md_free_data(struct md *md, struct md_data *data) 102 { 103 if (data->refcnt > 1) { 104 data->refcnt--; 105 return; 106 } 107 108 TAILQ_REMOVE(&md->data_list, data, link); 109 free(data); 110 } 111 112 struct md_node * 113 md_find_node(struct md *md, const char *name) 114 { 115 struct md_node *node; 116 117 TAILQ_FOREACH(node, &md->node_list, link) { 118 if (strcmp(node->name->str, name) == 0) 119 return node; 120 } 121 122 return NULL; 123 } 124 125 struct md_node * 126 md_find_subnode(struct md *md, struct md_node *node, const char *name) 127 { 128 struct md_prop *prop; 129 130 TAILQ_FOREACH(prop, &node->prop_list, link) { 131 if (prop->tag == MD_PROP_ARC && 132 strcmp(prop->name->str, "fwd") == 0 && 133 strcmp(prop->d.arc.node->name->str, name) == 0) 134 return prop->d.arc.node; 135 } 136 137 return NULL; 138 } 139 140 struct md_node * 141 md_add_node(struct md *md, const char *name) 142 { 143 struct md_node *node; 144 145 node = xmalloc(sizeof(*node)); 146 node->name = md_add_name(md, name); 147 TAILQ_INIT(&node->prop_list); 148 TAILQ_INSERT_TAIL(&md->node_list, node, link); 149 150 return node; 151 } 152 153 void 154 md_link_node(struct md *md, struct md_node *node1, struct md_node *node2) 155 { 156 md_add_prop_arc(md, node1, "fwd", node2); 157 md_add_prop_arc(md, node2, "back", node1); 158 } 159 160 struct md_prop * 161 md_find_prop(struct md *md, struct md_node *node, const char *name) 162 { 163 struct md_prop *prop; 164 165 TAILQ_FOREACH(prop, &node->prop_list, link) { 166 if (strcmp(prop->name->str, name) == 0) 167 return prop; 168 } 169 170 return NULL; 171 } 172 173 struct md_prop * 174 md_add_prop(struct md *md, struct md_node *node, const char *name) 175 { 176 struct md_prop *prop; 177 178 prop = xmalloc(sizeof(*prop)); 179 prop->name = md_add_name(md, name); 180 TAILQ_INSERT_TAIL(&node->prop_list, prop, link); 181 182 return prop; 183 } 184 185 struct md_prop * 186 md_add_prop_val(struct md *md, struct md_node *node, const char *name, 187 uint64_t val) 188 { 189 struct md_prop *prop; 190 191 prop = md_add_prop(md, node, name); 192 prop->tag = MD_PROP_VAL; 193 prop->d.val = val; 194 195 return prop; 196 } 197 198 struct md_prop * 199 md_add_prop_str(struct md *md, struct md_node *node, const char *name, 200 const char *str) 201 { 202 struct md_prop *prop; 203 204 prop = md_add_prop(md, node, name); 205 prop->tag = MD_PROP_STR; 206 prop->d.data = md_add_data(md, str, strlen(str) + 1); 207 208 return prop; 209 } 210 211 struct md_prop * 212 md_add_prop_data(struct md *md, struct md_node *node, const char *name, 213 const uint8_t *data, size_t len) 214 { 215 struct md_prop *prop; 216 217 prop = md_add_prop(md, node, name); 218 prop->tag = MD_PROP_DATA; 219 prop->d.data = md_add_data(md, data, len); 220 221 return prop; 222 } 223 224 struct md_prop * 225 md_add_prop_arc(struct md *md, struct md_node *node, const char *name, 226 struct md_node *target_node) 227 { 228 struct md_prop *prop; 229 230 prop = md_add_prop(md, node, name); 231 prop->tag = MD_PROP_ARC; 232 prop->d.arc.node = target_node; 233 234 return prop; 235 } 236 237 void 238 md_delete_prop(struct md *md, struct md_node *node, struct md_prop *prop) 239 { 240 TAILQ_REMOVE(&node->prop_list, prop, link); 241 if (prop->tag == MD_PROP_STR || prop->tag == MD_PROP_DATA) 242 md_free_data(md, prop->d.data); 243 md_free_name(md, prop->name); 244 free(prop); 245 } 246 247 bool 248 md_get_prop_val(struct md *md, struct md_node *node, const char *name, 249 uint64_t *val) 250 { 251 struct md_prop *prop; 252 253 prop = md_find_prop(md, node, name); 254 if (prop == NULL || prop->tag != MD_PROP_VAL) 255 return false; 256 257 *val = prop->d.val; 258 return true; 259 } 260 261 bool 262 md_set_prop_val(struct md *md, struct md_node *node, const char *name, 263 uint64_t val) 264 { 265 struct md_prop *prop; 266 267 prop = md_find_prop(md, node, name); 268 if (prop == NULL || prop->tag != MD_PROP_VAL) 269 return false; 270 271 prop->d.val = val; 272 return true; 273 } 274 275 bool 276 md_get_prop_str(struct md *md, struct md_node *node, const char *name, 277 const char **str) 278 { 279 struct md_prop *prop; 280 281 prop = md_find_prop(md, node, name); 282 if (prop == NULL || prop->tag != MD_PROP_STR) 283 return false; 284 285 *str = prop->d.data->data; 286 return true; 287 } 288 289 bool 290 md_get_prop_data(struct md *md, struct md_node *node, const char *name, 291 const void **data, size_t *len) 292 { 293 struct md_prop *prop; 294 295 prop = md_find_prop(md, node, name); 296 if (prop == NULL || prop->tag != MD_PROP_DATA) 297 return false; 298 299 *data = prop->d.data->data; 300 *len = prop->d.data->len; 301 return true; 302 } 303 304 bool 305 md_set_prop_data(struct md *md, struct md_node *node, const char *name, 306 const uint8_t *data, size_t len) 307 { 308 struct md_prop *prop; 309 310 prop = md_find_prop(md, node, name); 311 if (prop == NULL || prop->tag != MD_PROP_DATA) 312 return false; 313 314 md_free_data(md, prop->d.data); 315 prop->d.data = md_add_data(md, data, len); 316 return true; 317 } 318 319 void 320 md_delete_node(struct md *md, struct md_node *node) 321 { 322 struct md_node *node2; 323 struct md_prop *prop, *prop2; 324 325 TAILQ_FOREACH(node2, &md->node_list, link) { 326 TAILQ_FOREACH_SAFE(prop, &node2->prop_list, link, prop2) { 327 if (prop->tag == MD_PROP_ARC && 328 prop->d.arc.node == node) 329 md_delete_prop(md, node2, prop); 330 } 331 } 332 333 TAILQ_REMOVE(&md->node_list, node, link); 334 md_free_name(md, node->name); 335 free(node); 336 } 337 338 void 339 md_find_delete_node(struct md *md, const char *name) 340 { 341 struct md_node *node; 342 343 node = md_find_node(md, name); 344 if (node) 345 md_delete_node(md, node); 346 } 347 348 struct md * 349 md_alloc(void) 350 { 351 struct md *md; 352 353 md = xmalloc(sizeof(*md)); 354 TAILQ_INIT(&md->node_list); 355 TAILQ_INIT(&md->name_list); 356 TAILQ_INIT(&md->data_list); 357 358 return md; 359 } 360 361 struct md_node * 362 md_find_index(struct md *md, uint64_t index) 363 { 364 struct md_node *node; 365 366 TAILQ_FOREACH(node, &md->node_list, link) { 367 if (node->index == index) 368 return node; 369 } 370 371 return NULL; 372 } 373 374 void 375 md_fixup_arcs(struct md *md) 376 { 377 struct md_node *node; 378 struct md_prop *prop; 379 380 TAILQ_FOREACH(node, &md->node_list, link) { 381 TAILQ_FOREACH(prop, &node->prop_list, link) { 382 if (prop->tag == MD_PROP_ARC) 383 prop->d.arc.node = 384 md_find_index(md, prop->d.arc.index); 385 } 386 } 387 } 388 389 void 390 md_walk_graph(struct md *md, struct md_node *root) 391 { 392 struct md_prop *prop; 393 394 root->index = 1; 395 TAILQ_FOREACH(prop, &root->prop_list, link) { 396 if (prop->tag == MD_PROP_ARC && 397 strcmp(prop->name->str, "fwd") == 0) 398 md_walk_graph(md, prop->d.arc.node); 399 } 400 } 401 402 void 403 md_collect_garbage(struct md *md) 404 { 405 struct md_node *node, *node2; 406 407 TAILQ_FOREACH(node, &md->node_list, link) 408 node->index = 0; 409 410 md_walk_graph(md, md_find_node(md, "root")); 411 412 TAILQ_FOREACH_SAFE(node, &md->node_list, link, node2) { 413 if (node->index == 0) 414 md_delete_node(md, node); 415 } 416 } 417 418 struct md * 419 md_ingest(void *buf, size_t size) 420 { 421 struct md_header *mdh = buf; 422 size_t node_blk_size, name_blk_size, data_blk_size; 423 size_t total_size; 424 struct md_element *mde; 425 struct md_node *node = NULL; 426 struct md_prop *prop; 427 struct md *md; 428 const char *str; 429 const uint8_t *data; 430 uint8_t *node_blk; 431 uint8_t *name_blk; 432 uint8_t *data_blk; 433 uint64_t index; 434 435 if (size < sizeof(struct md_header)) 436 errx(1, "too small"); 437 438 if (betoh32(mdh->transport_version) != MD_TRANSPORT_VERSION) 439 errx(1, "invalid transport version"); 440 441 node_blk_size = betoh32(mdh->node_blk_sz); 442 name_blk_size = betoh32(mdh->name_blk_sz); 443 data_blk_size = betoh32(mdh->data_blk_sz); 444 total_size = node_blk_size + name_blk_size + data_blk_size; 445 446 if (size < total_size) 447 errx(1, "too small"); 448 449 md = md_alloc(); 450 451 mde = (void *)&mdh[1]; 452 node_blk = (void *)mde; 453 name_blk = node_blk + node_blk_size; 454 data_blk = name_blk + name_blk_size; 455 456 for (index = 0; index < node_blk_size / sizeof(*mde); index++, mde++) { 457 switch(mde->tag) { 458 case MD_NODE: 459 str = name_blk + betoh32(mde->name_offset); 460 node = md_add_node(md, str); 461 node->index = index; 462 break; 463 case MD_PROP_VAL: 464 if (node == NULL) 465 errx(1, "Corrupt MD"); 466 str = name_blk + betoh32(mde->name_offset); 467 md_add_prop_val(md, node, str, betoh64(mde->d.val)); 468 break; 469 case MD_PROP_STR: 470 if (node == NULL) 471 errx(1, "Corrupt MD"); 472 str = name_blk + betoh32(mde->name_offset); 473 data = data_blk + betoh32(mde->d.y.data_offset); 474 md_add_prop_str(md, node, str, data); 475 break; 476 case MD_PROP_DATA: 477 if (node == NULL) 478 errx(1, "Corrupt MD"); 479 str = name_blk + betoh32(mde->name_offset); 480 data = data_blk + betoh32(mde->d.y.data_offset); 481 md_add_prop_data(md, node, str, data, 482 betoh32(mde->d.y.data_len)); 483 break; 484 case MD_PROP_ARC: 485 if (node == NULL) 486 errx(1, "Corrupt MD"); 487 str = name_blk + betoh32(mde->name_offset); 488 prop = md_add_prop(md, node, str); 489 prop->tag = MD_PROP_ARC; 490 prop->d.arc.index = betoh64(mde->d.val); 491 prop->d.arc.node = NULL; 492 break; 493 case MD_NODE_END: 494 node = NULL; 495 break; 496 } 497 } 498 499 md_fixup_arcs(md); 500 501 return md; 502 } 503 504 size_t 505 md_exhume(struct md *md, void **buf) 506 { 507 struct md_node *node; 508 struct md_name *name; 509 struct md_data *data; 510 struct md_prop *prop; 511 size_t node_blk_size, name_blk_size, data_blk_size; 512 size_t total_size; 513 struct md_element *mde; 514 struct md_header *mdh; 515 uint32_t offset; 516 uint64_t index; 517 uint8_t *node_blk; 518 uint8_t *name_blk; 519 uint8_t *data_blk; 520 size_t len; 521 522 offset = 0; 523 TAILQ_FOREACH(name, &md->name_list, link) { 524 name->offset = offset; 525 offset += (strlen(name->str) + 1); 526 } 527 name_blk_size = roundup(offset, MD_ALIGNMENT_SIZE); 528 529 offset = 0; 530 TAILQ_FOREACH(data, &md->data_list, link) { 531 data->offset = offset; 532 offset += data->len; 533 offset = roundup(offset, MD_ALIGNMENT_SIZE); 534 } 535 data_blk_size = roundup(offset, MD_ALIGNMENT_SIZE); 536 537 index = 0; 538 TAILQ_FOREACH(node, &md->node_list, link) { 539 node->index = index; 540 TAILQ_FOREACH(prop, &node->prop_list, link) 541 index++; 542 index += 2; 543 } 544 node_blk_size = (index + 1) * sizeof(struct md_element); 545 546 total_size = 16 + node_blk_size + name_blk_size + data_blk_size; 547 mdh = xmalloc(total_size); 548 549 mdh->transport_version = htobe32(MD_TRANSPORT_VERSION); 550 mdh->node_blk_sz = htobe32(node_blk_size); 551 mdh->name_blk_sz = htobe32(name_blk_size); 552 mdh->data_blk_sz = htobe32(data_blk_size); 553 554 mde = (void *)&mdh[1]; 555 node_blk = (void *)mde; 556 name_blk = node_blk + node_blk_size; 557 data_blk = name_blk + name_blk_size; 558 559 TAILQ_FOREACH(node, &md->node_list, link) { 560 memset(mde, 0, sizeof(*mde)); 561 mde->tag = MD_NODE; 562 mde->name_len = strlen(node->name->str); 563 mde->name_offset = htobe32(node->name->offset); 564 if (TAILQ_NEXT(node, link)) 565 mde->d.val = htobe64(TAILQ_NEXT(node, link)->index); 566 else 567 mde->d.val = htobe64(index); 568 mde++; 569 TAILQ_FOREACH(prop, &node->prop_list, link) { 570 memset(mde, 0, sizeof(*mde)); 571 mde->tag = prop->tag; 572 mde->name_len = strlen(prop->name->str); 573 mde->name_offset = htobe32(prop->name->offset); 574 switch(prop->tag) { 575 case MD_PROP_VAL: 576 mde->d.val = htobe64(prop->d.val); 577 break; 578 case MD_PROP_STR: 579 case MD_PROP_DATA: 580 mde->d.y.data_len = 581 htobe32(prop->d.data->len); 582 mde->d.y.data_offset = 583 htobe32(prop->d.data->offset); 584 break; 585 case MD_PROP_ARC: 586 mde->d.val = 587 htobe64(prop->d.arc.node->index); 588 break; 589 } 590 mde++; 591 } 592 memset(mde, 0, sizeof(*mde)); 593 mde->tag = MD_NODE_END; 594 mde++; 595 } 596 memset(mde, 0, sizeof(*mde)); 597 mde->tag = MD_LIST_END; 598 599 TAILQ_FOREACH(name, &md->name_list, link) { 600 len = strlen(name->str) + 1; 601 memcpy(name_blk, name->str, len); 602 name_blk += len; 603 } 604 605 TAILQ_FOREACH(data, &md->data_list, link) { 606 memcpy(data_blk, data->data, data->len); 607 data_blk += roundup(data->len, MD_ALIGNMENT_SIZE); 608 } 609 610 *buf = mdh; 611 return total_size; 612 } 613 614 struct md * 615 md_copy(struct md *md) 616 { 617 void *buf; 618 size_t size; 619 620 size = md_exhume(md, &buf); 621 md = md_ingest(buf, size); 622 free(buf); 623 624 return md; 625 } 626 627 struct md * 628 md_read(const char *path) 629 { 630 FILE *fp; 631 size_t size; 632 void *buf; 633 634 fp = fopen(path, "r"); 635 if (fp == NULL) 636 return NULL; 637 638 if (fseek(fp, 0, SEEK_END) == -1) { 639 fclose(fp); 640 return NULL; 641 } 642 size = ftell(fp); 643 if (size == -1) { 644 fclose(fp); 645 return NULL; 646 } 647 if (fseek(fp, 0, SEEK_SET) == -1) { 648 fclose(fp); 649 return NULL; 650 } 651 652 buf = xmalloc(size); 653 if (fread(buf, size, 1, fp) != 1) { 654 fclose(fp); 655 free(buf); 656 return NULL; 657 } 658 659 fclose(fp); 660 661 return md_ingest(buf, size); 662 } 663 664 void 665 md_write(struct md *md, const char *path) 666 { 667 size_t size; 668 void *buf; 669 FILE *fp; 670 671 size = md_exhume(md, &buf); 672 673 fp = fopen(path, "w"); 674 if (fp == NULL) 675 err(1, "fopen"); 676 677 if (fwrite(buf, size, 1, fp) != 1) 678 err(1, "fwrite"); 679 680 fclose(fp); 681 } 682 683 uint32_t 684 md_size(const char *path) 685 { 686 uint32_t size; 687 FILE *fp; 688 689 fp = fopen(path, "r"); 690 if (fp == NULL) 691 err(1, "fopen"); 692 693 fseek(fp, 0, SEEK_END); 694 size = ftell(fp); 695 fclose(fp); 696 697 return size; 698 } 699