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 *
md_find_name(struct md * md,const char * str)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 *
md_add_name(struct md * md,const char * str)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
md_free_name(struct md * md,struct md_name * name)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 *
md_find_data(struct md * md,const uint8_t * b,size_t len)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 *
md_add_data(struct md * md,const uint8_t * b,size_t len)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
md_free_data(struct md * md,struct md_data * data)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 *
md_find_node(struct md * md,const char * name)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 *
md_find_subnode(struct md * md,struct md_node * node,const char * name)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 *
md_add_node(struct md * md,const char * name)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
md_link_node(struct md * md,struct md_node * node1,struct md_node * node2)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 *
md_find_prop(struct md * md,struct md_node * node,const char * name)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 *
md_add_prop(struct md * md,struct md_node * node,const char * name)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 *
md_add_prop_val(struct md * md,struct md_node * node,const char * name,uint64_t val)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 *
md_add_prop_str(struct md * md,struct md_node * node,const char * name,const char * str)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 *
md_add_prop_data(struct md * md,struct md_node * node,const char * name,const uint8_t * data,size_t len)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 *
md_add_prop_arc(struct md * md,struct md_node * node,const char * name,struct md_node * target_node)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
md_delete_prop(struct md * md,struct md_node * node,struct md_prop * prop)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
md_get_prop_val(struct md * md,struct md_node * node,const char * name,uint64_t * val)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
md_set_prop_val(struct md * md,struct md_node * node,const char * name,uint64_t val)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
md_get_prop_str(struct md * md,struct md_node * node,const char * name,const char ** str)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
md_get_prop_data(struct md * md,struct md_node * node,const char * name,const void ** data,size_t * len)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
md_set_prop_data(struct md * md,struct md_node * node,const char * name,const uint8_t * data,size_t len)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
md_delete_node(struct md * md,struct md_node * node)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
md_find_delete_node(struct md * md,const char * name)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 *
md_alloc(void)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 *
md_find_index(struct md * md,uint64_t index)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
md_fixup_arcs(struct md * md)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
md_walk_graph(struct md * md,struct md_node * root)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
md_collect_garbage(struct md * md)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 *
md_ingest(void * buf,size_t size)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
md_exhume(struct md * md,void ** buf)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 *
md_copy(struct md * 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 *
md_read(const char * path)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
md_write(struct md * md,const char * path)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
md_size(const char * path)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