1 /* $OpenBSD: mdesc.c,v 1.9 2015/05/23 14:26:06 jsg 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 "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_add_node(struct md *md, const char *name) 127 { 128 struct md_node *node; 129 130 node = xmalloc(sizeof(*node)); 131 node->name = md_add_name(md, name); 132 TAILQ_INIT(&node->prop_list); 133 TAILQ_INSERT_TAIL(&md->node_list, node, link); 134 135 return node; 136 } 137 138 void 139 md_link_node(struct md *md, struct md_node *node1, struct md_node *node2) 140 { 141 md_add_prop_arc(md, node1, "fwd", node2); 142 md_add_prop_arc(md, node2, "back", node1); 143 } 144 145 struct md_prop * 146 md_find_prop(struct md *md, struct md_node *node, const char *name) 147 { 148 struct md_prop *prop; 149 150 TAILQ_FOREACH(prop, &node->prop_list, link) { 151 if (strcmp(prop->name->str, name) == 0) 152 return prop; 153 } 154 155 return NULL; 156 } 157 158 struct md_prop * 159 md_add_prop(struct md *md, struct md_node *node, const char *name) 160 { 161 struct md_prop *prop; 162 163 prop = xmalloc(sizeof(*prop)); 164 prop->name = md_add_name(md, name); 165 TAILQ_INSERT_TAIL(&node->prop_list, prop, link); 166 167 return prop; 168 } 169 170 struct md_prop * 171 md_add_prop_val(struct md *md, struct md_node *node, const char *name, 172 uint64_t val) 173 { 174 struct md_prop *prop; 175 176 prop = md_add_prop(md, node, name); 177 prop->tag = MD_PROP_VAL; 178 prop->d.val = val; 179 180 return prop; 181 } 182 183 struct md_prop * 184 md_add_prop_str(struct md *md, struct md_node *node, const char *name, 185 const char *str) 186 { 187 struct md_prop *prop; 188 189 prop = md_add_prop(md, node, name); 190 prop->tag = MD_PROP_STR; 191 prop->d.data = md_add_data(md, str, strlen(str) + 1); 192 193 return prop; 194 } 195 196 struct md_prop * 197 md_add_prop_data(struct md *md, struct md_node *node, const char *name, 198 const uint8_t *data, size_t len) 199 { 200 struct md_prop *prop; 201 202 prop = md_add_prop(md, node, name); 203 prop->tag = MD_PROP_DATA; 204 prop->d.data = md_add_data(md, data, len); 205 206 return prop; 207 } 208 209 struct md_prop * 210 md_add_prop_arc(struct md *md, struct md_node *node, const char *name, 211 struct md_node *target_node) 212 { 213 struct md_prop *prop; 214 215 prop = md_add_prop(md, node, name); 216 prop->tag = MD_PROP_ARC; 217 prop->d.arc.node = target_node; 218 219 return prop; 220 } 221 222 void 223 md_delete_prop(struct md *md, struct md_node *node, struct md_prop *prop) 224 { 225 TAILQ_REMOVE(&node->prop_list, prop, link); 226 if (prop->tag == MD_PROP_STR || prop->tag == MD_PROP_DATA) 227 md_free_data(md, prop->d.data); 228 md_free_name(md, prop->name); 229 free(prop); 230 } 231 232 bool 233 md_get_prop_val(struct md *md, struct md_node *node, const char *name, 234 uint64_t *val) 235 { 236 struct md_prop *prop; 237 238 prop = md_find_prop(md, node, name); 239 if (prop == NULL || prop->tag != MD_PROP_VAL) 240 return false; 241 242 *val = prop->d.val; 243 return true; 244 } 245 246 bool 247 md_set_prop_val(struct md *md, struct md_node *node, const char *name, 248 uint64_t val) 249 { 250 struct md_prop *prop; 251 252 prop = md_find_prop(md, node, name); 253 if (prop == NULL || prop->tag != MD_PROP_VAL) 254 return false; 255 256 prop->d.val = val; 257 return true; 258 } 259 260 bool 261 md_get_prop_str(struct md *md, struct md_node *node, const char *name, 262 const char **str) 263 { 264 struct md_prop *prop; 265 266 prop = md_find_prop(md, node, name); 267 if (prop == NULL || prop->tag != MD_PROP_STR) 268 return false; 269 270 *str = prop->d.data->data; 271 return true; 272 } 273 274 bool 275 md_get_prop_data(struct md *md, struct md_node *node, const char *name, 276 const void **data, size_t *len) 277 { 278 struct md_prop *prop; 279 280 prop = md_find_prop(md, node, name); 281 if (prop == NULL || prop->tag != MD_PROP_DATA) 282 return false; 283 284 *data = prop->d.data->data; 285 *len = prop->d.data->len; 286 return true; 287 } 288 289 void 290 md_delete_node(struct md *md, struct md_node *node) 291 { 292 struct md_node *node2; 293 struct md_prop *prop, *prop2; 294 295 TAILQ_FOREACH(node2, &md->node_list, link) { 296 TAILQ_FOREACH_SAFE(prop, &node2->prop_list, link, prop2) { 297 if (prop->tag == MD_PROP_ARC && 298 prop->d.arc.node == node) 299 md_delete_prop(md, node2, prop); 300 } 301 } 302 303 TAILQ_REMOVE(&md->node_list, node, link); 304 md_free_name(md, node->name); 305 free(node); 306 } 307 308 void 309 md_find_delete_node(struct md *md, const char *name) 310 { 311 struct md_node *node; 312 313 node = md_find_node(md, name); 314 if (node) 315 md_delete_node(md, node); 316 } 317 318 struct md * 319 md_alloc(void) 320 { 321 struct md *md; 322 323 md = xmalloc(sizeof(*md)); 324 TAILQ_INIT(&md->node_list); 325 TAILQ_INIT(&md->name_list); 326 TAILQ_INIT(&md->data_list); 327 328 return md; 329 } 330 331 struct md_node * 332 md_find_index(struct md *md, uint64_t index) 333 { 334 struct md_node *node; 335 336 TAILQ_FOREACH(node, &md->node_list, link) { 337 if (node->index == index) 338 return node; 339 } 340 341 return NULL; 342 } 343 344 void 345 md_fixup_arcs(struct md *md) 346 { 347 struct md_node *node; 348 struct md_prop *prop; 349 350 TAILQ_FOREACH(node, &md->node_list, link) { 351 TAILQ_FOREACH(prop, &node->prop_list, link) { 352 if (prop->tag == MD_PROP_ARC) 353 prop->d.arc.node = 354 md_find_index(md, prop->d.arc.index); 355 } 356 } 357 } 358 359 void 360 md_walk_graph(struct md *md, struct md_node *root) 361 { 362 struct md_prop *prop; 363 364 root->index = 1; 365 TAILQ_FOREACH(prop, &root->prop_list, link) { 366 if (prop->tag == MD_PROP_ARC && 367 strcmp(prop->name->str, "fwd") == 0) 368 md_walk_graph(md, prop->d.arc.node); 369 } 370 } 371 372 void 373 md_collect_garbage(struct md *md) 374 { 375 struct md_node *node, *node2; 376 377 TAILQ_FOREACH(node, &md->node_list, link) 378 node->index = 0; 379 380 md_walk_graph(md, md_find_node(md, "root")); 381 382 TAILQ_FOREACH_SAFE(node, &md->node_list, link, node2) { 383 if (node->index == 0) 384 md_delete_node(md, node); 385 } 386 } 387 388 struct md * 389 md_ingest(void *buf, size_t size) 390 { 391 struct md_header *mdh = buf; 392 size_t node_blk_size, name_blk_size, data_blk_size; 393 size_t total_size; 394 struct md_element *mde; 395 struct md_node *node = NULL; 396 struct md_prop *prop; 397 struct md *md; 398 const char *str; 399 const uint8_t *data; 400 uint8_t *node_blk; 401 uint8_t *name_blk; 402 uint8_t *data_blk; 403 uint64_t index; 404 405 if (size < sizeof(struct md_header)) 406 errx(1, "too small"); 407 408 if (betoh32(mdh->transport_version) != MD_TRANSPORT_VERSION) 409 errx(1, "invalid transport version"); 410 411 node_blk_size = betoh32(mdh->node_blk_sz); 412 name_blk_size = betoh32(mdh->name_blk_sz); 413 data_blk_size = betoh32(mdh->data_blk_sz); 414 total_size = node_blk_size + name_blk_size + data_blk_size; 415 416 if (size < total_size) 417 errx(1, "too small"); 418 419 md = md_alloc(); 420 421 mde = (void *)&mdh[1]; 422 node_blk = (void *)mde; 423 name_blk = node_blk + node_blk_size; 424 data_blk = name_blk + name_blk_size; 425 426 for (index = 0; index < node_blk_size / sizeof(*mde); index++, mde++) { 427 switch(mde->tag) { 428 case MD_NODE: 429 str = name_blk + betoh32(mde->name_offset); 430 node = md_add_node(md, str); 431 node->index = index; 432 break; 433 case MD_PROP_VAL: 434 if (node == NULL) 435 errx(1, "Corrupt MD"); 436 str = name_blk + betoh32(mde->name_offset); 437 md_add_prop_val(md, node, str, betoh64(mde->d.val)); 438 break; 439 case MD_PROP_STR: 440 if (node == NULL) 441 errx(1, "Corrupt MD"); 442 str = name_blk + betoh32(mde->name_offset); 443 data = data_blk + betoh32(mde->d.y.data_offset); 444 md_add_prop_str(md, node, str, data); 445 break; 446 case MD_PROP_DATA: 447 if (node == NULL) 448 errx(1, "Corrupt MD"); 449 str = name_blk + betoh32(mde->name_offset); 450 data = data_blk + betoh32(mde->d.y.data_offset); 451 md_add_prop_data(md, node, str, data, 452 betoh32(mde->d.y.data_len)); 453 break; 454 case MD_PROP_ARC: 455 if (node == NULL) 456 errx(1, "Corrupt MD"); 457 str = name_blk + betoh32(mde->name_offset); 458 prop = md_add_prop(md, node, str); 459 prop->tag = MD_PROP_ARC; 460 prop->d.arc.index = betoh64(mde->d.val); 461 prop->d.arc.node = NULL; 462 break; 463 case MD_NODE_END: 464 node = NULL; 465 break; 466 } 467 } 468 469 md_fixup_arcs(md); 470 471 return md; 472 } 473 474 size_t 475 md_exhume(struct md *md, void **buf) 476 { 477 struct md_node *node; 478 struct md_name *name; 479 struct md_data *data; 480 struct md_prop *prop; 481 size_t node_blk_size, name_blk_size, data_blk_size; 482 size_t total_size; 483 struct md_element *mde; 484 struct md_header *mdh; 485 uint32_t offset; 486 uint64_t index; 487 uint8_t *node_blk; 488 uint8_t *name_blk; 489 uint8_t *data_blk; 490 size_t len; 491 492 offset = 0; 493 TAILQ_FOREACH(name, &md->name_list, link) { 494 name->offset = offset; 495 offset += (strlen(name->str) + 1); 496 } 497 name_blk_size = roundup(offset, MD_ALIGNMENT_SIZE); 498 499 offset = 0; 500 TAILQ_FOREACH(data, &md->data_list, link) { 501 data->offset = offset; 502 offset += data->len; 503 offset = roundup(offset, MD_ALIGNMENT_SIZE); 504 } 505 data_blk_size = roundup(offset, MD_ALIGNMENT_SIZE); 506 507 index = 0; 508 TAILQ_FOREACH(node, &md->node_list, link) { 509 node->index = index; 510 TAILQ_FOREACH(prop, &node->prop_list, link) 511 index++; 512 index += 2; 513 } 514 node_blk_size = (index + 1) * sizeof(struct md_element); 515 516 total_size = 16 + node_blk_size + name_blk_size + data_blk_size; 517 mdh = xmalloc(total_size); 518 519 mdh->transport_version = htobe32(MD_TRANSPORT_VERSION); 520 mdh->node_blk_sz = htobe32(node_blk_size); 521 mdh->name_blk_sz = htobe32(name_blk_size); 522 mdh->data_blk_sz = htobe32(data_blk_size); 523 524 mde = (void *)&mdh[1]; 525 node_blk = (void *)mde; 526 name_blk = node_blk + node_blk_size; 527 data_blk = name_blk + name_blk_size; 528 529 TAILQ_FOREACH(node, &md->node_list, link) { 530 memset(mde, 0, sizeof(*mde)); 531 mde->tag = MD_NODE; 532 mde->name_len = strlen(node->name->str); 533 mde->name_offset = htobe32(node->name->offset); 534 if (TAILQ_NEXT(node, link)) 535 mde->d.val = htobe64(TAILQ_NEXT(node, link)->index); 536 else 537 mde->d.val = htobe64(index); 538 mde++; 539 TAILQ_FOREACH(prop, &node->prop_list, link) { 540 memset(mde, 0, sizeof(*mde)); 541 mde->tag = prop->tag; 542 mde->name_len = strlen(prop->name->str); 543 mde->name_offset = htobe32(prop->name->offset); 544 switch(prop->tag) { 545 case MD_PROP_VAL: 546 mde->d.val = htobe64(prop->d.val); 547 break; 548 case MD_PROP_STR: 549 case MD_PROP_DATA: 550 mde->d.y.data_len = 551 htobe32(prop->d.data->len); 552 mde->d.y.data_offset = 553 htobe32(prop->d.data->offset); 554 break; 555 case MD_PROP_ARC: 556 mde->d.val = 557 htobe64(prop->d.arc.node->index); 558 break; 559 } 560 mde++; 561 } 562 memset(mde, 0, sizeof(*mde)); 563 mde->tag = MD_NODE_END; 564 mde++; 565 } 566 memset(mde, 0, sizeof(*mde)); 567 mde->tag = MD_LIST_END; 568 569 TAILQ_FOREACH(name, &md->name_list, link) { 570 len = strlen(name->str) + 1; 571 memcpy(name_blk, name->str, len); 572 name_blk += len; 573 } 574 575 TAILQ_FOREACH(data, &md->data_list, link) { 576 memcpy(data_blk, data->data, data->len); 577 data_blk += roundup(data->len, MD_ALIGNMENT_SIZE); 578 } 579 580 *buf = mdh; 581 return total_size; 582 } 583 584 struct md * 585 md_copy(struct md *md) 586 { 587 void *buf; 588 size_t size; 589 590 size = md_exhume(md, &buf); 591 md = md_ingest(buf, size); 592 free(buf); 593 594 return md; 595 } 596 597 struct md * 598 md_read(const char *path) 599 { 600 FILE *fp; 601 size_t size; 602 void *buf; 603 604 fp = fopen(path, "r"); 605 if (fp == NULL) 606 return NULL; 607 608 if (fseek(fp, 0, SEEK_END) == -1) { 609 fclose(fp); 610 return NULL; 611 } 612 size = ftell(fp); 613 if (size == -1) { 614 fclose(fp); 615 return NULL; 616 } 617 if (fseek(fp, 0, SEEK_SET) == -1) { 618 fclose(fp); 619 return NULL; 620 } 621 622 buf = xmalloc(size); 623 if (fread(buf, size, 1, fp) != 1) { 624 fclose(fp); 625 free(buf); 626 return NULL; 627 } 628 629 fclose(fp); 630 631 return md_ingest(buf, size); 632 } 633 634 void 635 md_write(struct md *md, const char *path) 636 { 637 size_t size; 638 void *buf; 639 FILE *fp; 640 641 size = md_exhume(md, &buf); 642 643 fp = fopen(path, "w"); 644 if (fp == NULL) 645 err(1, "fopen"); 646 647 if (fwrite(buf, size, 1, fp) != 1) 648 err(1, "fwrite"); 649 650 fclose(fp); 651 } 652