src/plugins/gam-resource-manager/c5-decision-tree.c

   1 /*
   2  * Copyright (c) 2014, Intel Corporation
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *  * Redistributions of source code must retain the above copyright notice,
   9  *    this list of conditions and the following disclaimer.
  10  *  * Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *  * Neither the name of Intel Corporation nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31 #include <string.h>
  32 #include <ctype.h>
  33 #include <errno.h>
  34
  35 #include <murphy/common.h>
  36
  37 #include "c5-decision-tree.h"
  38
  39
  40 #define ATTRIBUTE_MAX  32
  41 #define ENUM_MAX       16384
  42 #define ENUM_BUCKETS   16
  43
  44
  45
  46 typedef enum   state_e              state_t;
  47 typedef struct conf_iter_s          conf_iter_t;
  48 typedef struct attr_value_iter_s    attr_value_iter_t;
  49 typedef struct value_list_item_s    value_list_item_t;
  50 typedef struct value_list_s         value_list_t;
  51
  52 enum state_e {
  53     START = 0,
  54     NAME,
  55     VALUE,
  56     END
  57 };
  58
  59
  60 struct conf_iter_s {
  61     mrp_decision_conf_t *conf;
  62     int nattr;
  63     mrp_decision_attr_t *attrs[0];
  64 };
  65
  66
  67 struct attr_value_iter_s {
  68     mrp_decision_attr_t *attr;
  69     int ndesc;
  70     mrp_decision_attr_value_desc_t descs[0];
  71 };
  72
  73 struct value_list_item_s {
  74     const char *name;
  75     int32_t value;
  76 };
  77
  78 struct value_list_s {
  79     int size;
  80     value_list_item_t *items;
  81 };
  82
  83 static bool conf_finish(mrp_decision_conf_t *, const char *);
  84 static conf_iter_t *conf_iterator(mrp_decision_conf_t *);
  85
  86 static mrp_decision_attr_t *attr_create(mrp_decision_conf_t*,const char*,int);
  87 static void attr_destroy(void *, void *);
  88 static void attr_add_value(mrp_decision_attr_t *, const char *);
  89 static attr_value_iter_t *attr_value_iterator(mrp_decision_attr_t *);
  90 static size_t attr_print(mrp_decision_attr_t *, bool, char *, size_t);
  91
  92 static void value_destroy(void *, void *);
  93
  94 static bool tree_parse(mrp_decision_conf_t *, FILE *, size_t *, char *,
  95                        mrp_decision_node_t **, int);
  96 static bool tree_parse_terminal_node(mrp_decision_conf_t *, FILE *, size_t *,
  97                                      char *, bool, mrp_decision_node_t **, int);
  98 static bool tree_parse_test_node(mrp_decision_conf_t *, FILE *, size_t *,
  99                                  char *, int, mrp_decision_node_t **, int);
 100
 101
 102
 103 static bool property(char **, char **, char **);
 104 static bool list_item(char **, char **);
 105 static bool identifier(char **, char **, char *);
 106 static bool whitespace(char **);
 107 static bool quoted(char **, char **);
 108
 109 static size_t print_node(mrp_decision_conf_t *, mrp_decision_node_t *,
 110                          conf_iter_t *, char *, size_t, char *);
 111 static size_t print_bitmask(mrp_decision_attr_t *, mrp_decision_bitmask_t,
 112                             char *, size_t);
 113
 114
 115
 116 mrp_decision_conf_t *mrp_decision_conf_create_from_file(const char *stem)
 117 {
 118     FILE *f;
 119     char filnam[1024];
 120     char *buf, *p;
 121     size_t n;
 122     ssize_t linlen;
 123     state_t state;
 124     char decision[256];
 125     char *name;
 126     char *value;
 127     char sep;
 128     size_t lineno;
 129     mrp_decision_conf_t *conf;
 130     mrp_decision_attr_t *attr;
 131     mrp_htbl_config_t aconf;
 132     int id;
 133
 134     if (!stem || !stem[0])
 135         return false;
 136
 137     snprintf(filnam, sizeof(filnam), "%s.names", stem);
 138     if (!(f = fopen(filnam, "r"))) {
 139         mrp_log_error("gam-resource-manager: failed to open file '%s': %s",
 140                       filnam, strerror(errno));
 141         return NULL;
 142     }
 143
 144     if (!(conf = mrp_allocz(sizeof(mrp_decision_conf_t)))) {
 145         mrp_log_error("gam-resource-manager: can't allocate memory for "
 146                       "'%s' decision configuration", stem);
 147         return NULL;
 148     }
 149     else {
 150         aconf.nentry  = ATTRIBUTE_MAX;
 151         aconf.comp    = mrp_string_comp;
 152         aconf.hash    = mrp_string_hash;
 153         aconf.free    = attr_destroy;
 154         aconf.nbucket = ATTRIBUTE_MAX;
 155
 156         conf->stem  = mrp_strdup(stem);
 157         conf->nattr = 0;
 158         conf->attrs = mrp_htbl_create(&aconf);
 159
 160         if (!conf->attrs) {
 161             mrp_log_error("gam-resource-manager: failed to create attribute "
 162                           "hash for '%s' decision configuration", stem);
 163             mrp_decision_conf_destroy(conf);
 164             return NULL;
 165         }
 166     }
 167
 168     state = START;
 169     buf = NULL;
 170     lineno = 0;
 171     attr = NULL;
 172     id = 0;
 173     decision[0] = 0;
 174
 175     while ((linlen = getline(&buf, &n, f)) >= 0) {
 176         lineno++;
 177         p = buf;
 178
 179         whitespace(&p);
 180
 181         while (*p) {
 182             switch (state) {
 183
 184             case START:
 185                 if (!identifier(&p, &name, &sep) || sep != '.')
 186                     goto failed;
 187                 mrp_debug("decision = '%s'", name);
 188                 snprintf(decision, sizeof(decision), "%s", name);
 189                 state = NAME;
 190                 whitespace(&p);
 191                 break;
 192
 193             case NAME:
 194                 if (!identifier(&p, &name, &sep) || sep != ':')
 195                     goto failed;
 196                 mrp_debug("name = '%s'", name);
 197                 if (!(attr = attr_create(conf, name, id++)))
 198                     goto failed;
 199                 state = VALUE;
 200                 whitespace(&p);
 201                 break;
 202
 203             case VALUE:
 204                 if (!identifier(&p, &value, &sep) ||
 205                     (sep != ',' && sep != '.' && sep != 0))
 206                     goto failed;
 207                 mrp_debug("value = '%s'", value);
 208                 if (!strcmp(name, "continuous") && sep != '.')
 209                     goto failed;
 210                 attr_add_value(attr, value);
 211                 if (sep == '.') {
 212                     state = NAME;
 213                     attr = NULL;
 214                 }
 215                 whitespace(&p);
 216                 break;
 217
 218             default:
 219                 break;
 220             }
 221         }
 222
 223         free(buf);
 224         buf = NULL;
 225     } /* while getline */
 226
 227     if (linlen < 0 && !feof(f)) {
 228         mrp_log_error("gam-resource-manager: error during reading "
 229                       "'%s' file: %s", filnam, strerror(errno));
 230         mrp_decision_conf_destroy(conf);
 231         return NULL;
 232     }
 233
 234     fclose(f);
 235
 236     if (!conf_finish(conf, decision)) {
 237         mrp_decision_conf_destroy(conf);
 238         return NULL;
 239     }
 240
 241     mrp_log_info("mrp-resource-manager: successfully loaded "
 242                  "decision configuration from file '%s'", filnam);
 243
 244     return conf;
 245
 246   failed:
 247     mrp_log_error("gam-resource-manager: error in file '%s' line %zu",
 248                   filnam, lineno);
 249     free(buf);
 250     fclose(f);
 251     mrp_decision_conf_destroy(conf);
 252     return NULL;
 253 }
 254
 255 void mrp_decision_conf_destroy(mrp_decision_conf_t *conf)
 256 {
 257     if (conf) {
 258         mrp_log_info("mrp-resource-manager: going to unload "
 259                      "decision configuration '%s'", conf->stem);
 260
 261         if (conf->decision_attr && conf->decision_names)
 262             mrp_free(conf->decision_names);
 263
 264         mrp_htbl_destroy(conf->attrs, TRUE);
 265
 266         mrp_free((void *)conf->stem);
 267         mrp_free((void *)conf);
 268     }
 269 }
 270
 271 bool mrp_decision_set_attr_offset(mrp_decision_conf_t *conf,
 272                                   const char *attr_name,
 273                                   size_t offset)
 274 {
 275     mrp_decision_attr_t *attr;
 276
 277     if (!conf || !attr_name)
 278         return false;
 279
 280     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)attr_name)))
 281         return false;
 282
 283     attr->offset = offset;
 284
 285     return true;
 286 }
 287
 288 ssize_t mrp_decision_attr_list(mrp_decision_conf_t *conf,
 289                                const char **buf, size_t len)
 290 {
 291     conf_iter_t *it;
 292     int i,j,n;
 293
 294     if (!conf || !buf || len < 1)
 295         return -1;
 296
 297     if ((int)len < conf->nattr)
 298         return -1;
 299
 300     if (!(it = conf_iterator(conf)))
 301         return -1;
 302
 303     for (i = j = 0, n = it->nattr;  i < n;  i++) {
 304         if (conf->decision_attr != it->attrs[i])
 305             buf[j++] = it->attrs[i]->name;
 306     }
 307     buf[j] = NULL;
 308
 309     mrp_free(it);
 310
 311     return j;
 312 }
 313
 314 ssize_t mrp_decision_attr_value_list(mrp_decision_conf_t *conf,
 315                                      const char *attr_name,
 316                                      mrp_decision_attr_value_desc_t *buf,
 317                                      size_t len)
 318 {
 319     mrp_decision_attr_t *attr;
 320     attr_value_iter_t *it;
 321     int buf_len;
 322     int actual_len;
 323     size_t size;
 324
 325     if (!conf || !attr_name || !buf || (buf_len = len) < 1)
 326         return -1;
 327
 328     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)attr_name)))
 329         return -1;
 330
 331     if (buf_len < attr->nvalue)
 332         return -1;
 333
 334     if (!(it = attr_value_iterator(attr)))
 335         return -1;
 336
 337     actual_len = it->ndesc;
 338
 339     size = sizeof(mrp_decision_attr_value_desc_t) * actual_len;
 340     memcpy(buf, it->descs, size);
 341
 342     if (buf_len > actual_len) {
 343         size = sizeof(mrp_decision_attr_value_desc_t) * (buf_len - it->ndesc);
 344         memset(buf + it->ndesc, 0, size);
 345     }
 346
 347     mrp_free(it);
 348
 349     return actual_len;
 350 }
 351
 352
 353
 354 const char *mrp_decision_name(mrp_decision_conf_t *conf, int32_t decision)
 355 {
 356     if (!conf || decision < 0 || decision > conf->decision_attr->nvalue)
 357         return "<invalid>";
 358
 359     return conf->decision_names[decision];
 360 }
 361
 362
 363 int32_t mrp_decision_value_max(mrp_decision_conf_t *conf)
 364 {
 365     if (!conf || !conf->decision_attr)
 366         return 0;
 367
 368     return conf->decision_attr->nvalue;
 369 }
 370
 371 int32_t mrp_decision_get_integer_attr_value(mrp_decision_conf_t *conf,
 372                                             const char *attr_name,
 373                                             const char *value_name,
 374                                             bool *error)
 375 {
 376     mrp_decision_attr_t *attr;
 377     mrp_decision_value_t *value;
 378
 379     if (error)
 380         *error = true;
 381
 382     if (!conf || !attr_name || !value_name)
 383         return 0;
 384
 385     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)attr_name)))
 386         return -1;
 387
 388     if (attr->value_type != MRP_DECISION_VALUE_INTEGER)
 389         return -1;
 390
 391     if (!(value = mrp_htbl_lookup(attr->values, (void *)value_name)))
 392         return -1;
 393
 394     if (error)
 395         *error = false;
 396
 397     return value->integer;
 398 }
 399
 400
 401 const char *mrp_decision_get_integer_attr_name(mrp_decision_conf_t *conf,
 402                                                const char *attr_name,
 403                                                int32_t value,
 404                                                bool *error)
 405 {
 406     mrp_decision_attr_t *attr;
 407     attr_value_iter_t *it;
 408     const char *value_name;
 409     int i;
 410
 411     if (error)
 412         *error = true;
 413
 414     if (!conf || !attr_name)
 415         return "<error>";
 416
 417     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)attr_name)))
 418         return "<unknown attribute>";
 419
 420     if (attr->value_type != MRP_DECISION_VALUE_INTEGER)
 421         return "<not integer attribute>";
 422
 423     if (!(it = attr_value_iterator(attr)))
 424         return "<error>";
 425
 426     for (i = 0, value_name = "<unknown value>";   i < it->ndesc;   i++) {
 427         if (it->descs[i].value == value) {
 428             value_name = it->descs[i].name;
 429             break;
 430         }
 431     }
 432
 433     if (i < it->ndesc && error)
 434         *error = false;
 435
 436     return value_name;
 437 }
 438
 439
 440 size_t mrp_decision_conf_print(mrp_decision_conf_t *conf, char *buf,size_t len)
 441 {
 442     conf_iter_t *it;
 443     mrp_decision_attr_t *attr;
 444     int i;
 445     char *p, *e;
 446
 447     e = (p = buf) + len;
 448
 449     if (buf) {
 450         if (!(it = conf_iterator(conf)))
 451             p += snprintf(p, e-p, "<error>");
 452         else {
 453             p += snprintf(p, e-p, "attributes for '%s'\n", conf->stem);
 454
 455             for (i = 0;  i < it->nattr;  i++) {
 456                 attr = it->attrs[i];
 457                 p += attr_print(attr, (attr == conf->decision_attr), p, e-p);
 458             }
 459
 460             mrp_free(it);
 461         }
 462     }
 463
 464     return p - buf;
 465 }
 466
 467
 468 static bool conf_finish(mrp_decision_conf_t *conf,
 469                         const char *decision_attr_name)
 470 {
 471     mrp_decision_attr_t *attr;
 472     attr_value_iter_t *it;
 473     mrp_decision_attr_value_desc_t *dsc;
 474     size_t size;
 475     const char **tbl;
 476     int i, n;
 477
 478     if (!(attr = mrp_htbl_lookup(conf->attrs, (void *)decision_attr_name))) {
 479         mrp_log_error("gam-resoure-manager: can't find decision attribute "
 480                       "'%s' for '%s'", decision_attr_name, conf->stem);
 481         return false;
 482     }
 483
 484     if (attr->nvalue < 1) {
 485         mrp_log_error("gam-resource-manager: attribute '%s' in '%s' is "
 486                       "not suitable for decisions", attr->name, conf->stem);
 487         return false;
 488     }
 489
 490     n = attr->nvalue;
 491     size = sizeof(const char *) * n;
 492
 493     if (!(it = attr_value_iterator(attr)) || !(tbl = mrp_allocz(size))) {
 494         mrp_free(it);
 495         mrp_log_error("gam-resource-manager: can't allocate memory to "
 496                       "finalize '%s' decision", conf->stem);
 497         return false;
 498     }
 499
 500     for (i = 0;  i < n;  i++) {
 501         dsc = it->descs + i;
 502
 503         if (i != dsc->value) {
 504             mrp_log_error("gam-resource-manager: internal error: decision "
 505                           "values of '%s' are non-continous for '%s' decisions",
 506                           attr->name, conf->stem);
 507             mrp_free(it);
 508             mrp_free(tbl);
 509             return false;
 510         }
 511
 512         tbl[i] = dsc->name;
 513     };
 514
 515     mrp_free(it);
 516
 517     conf->decision_attr = attr;
 518     conf->decision_names = tbl;
 519
 520     return true;
 521 }
 522
 523
 524 static int conf_iter_cb(void *key, void *object, void *user_data)
 525 {
 526     conf_iter_t *it = (conf_iter_t *)user_data;
 527     mrp_decision_attr_t *attr = (mrp_decision_attr_t *)object;
 528
 529     MRP_UNUSED(key);
 530
 531     if (it->nattr >= it->conf->nattr) {
 532         mrp_log_error("gam-resource-manager: detected inconsitency while "
 533                       "iterating configuration of '%s'", it->conf->stem);
 534     }
 535     else {
 536         it->attrs[it->nattr++] = attr;
 537     }
 538
 539     return MRP_HTBL_ITER_MORE;
 540 }
 541
 542 static conf_iter_t *conf_iterator(mrp_decision_conf_t *conf)
 543 {
 544     conf_iter_t *it;
 545     size_t size;
 546     mrp_decision_attr_t *tmp;
 547     int i,j;
 548
 549     if (!conf)
 550         it = NULL;
 551     else {
 552         size = sizeof(conf_iter_t) + (sizeof(void *) * conf->nattr);
 553
 554         if ((it = mrp_allocz(size))) {
 555             it->conf = conf;
 556
 557             mrp_htbl_foreach(conf->attrs, conf_iter_cb, it);
 558
 559             for (i = 0;   i < it->nattr - 1;   i++) {
 560                 for (j = i + 1;   j < it->nattr;   j++) {
 561                     if (it->attrs[i]->id > it->attrs[j]->id) {
 562                         tmp = it->attrs[i];
 563                         it->attrs[i] = it->attrs[j];
 564                         it->attrs[j] = tmp;
 565                     }
 566                 }
 567             }
 568         }
 569     }
 570
 571     return it;
 572 }
 573
 574
 575 static mrp_decision_attr_t *attr_create(mrp_decision_conf_t *conf,
 576                                         const char *name, int id)
 577 {
 578     mrp_decision_attr_t *attr;
 579
 580     if (!conf || !name)
 581         attr = NULL;
 582     else {
 583         if ((attr = mrp_allocz(sizeof(mrp_decision_attr_t)))) {
 584             attr->name       = mrp_strdup(name);
 585             attr->id         = id;
 586             attr->attr_type  = MRP_DECISION_ATTR_CONTINUOUS;
 587             attr->value_type = MRP_DECISION_VALUE_INTEGER;
 588             attr->nvalue     = 0;
 589             attr->values     = NULL;
 590         }
 591
 592         if (!mrp_htbl_insert(conf->attrs, (void *)attr->name, attr)) {
 593             attr_destroy((void *)attr->name, (void *)attr);
 594             attr = NULL;
 595         }
 596
 597         conf->nattr++;
 598     }
 599
 600     return attr;
 601 }
 602
 603 static void attr_destroy(void *key, void *object)
 604 {
 605     mrp_decision_attr_t *attr = (mrp_decision_attr_t *)object;
 606
 607     MRP_UNUSED(key);
 608
 609     if (attr->values)
 610         mrp_htbl_destroy(attr->values, TRUE);
 611
 612     mrp_free((void *)attr->name);
 613     mrp_free(object);
 614 }
 615
 616 static void attr_add_value(mrp_decision_attr_t *attr, const char *name)
 617 {
 618     mrp_htbl_config_t vconf;
 619     mrp_decision_value_t *value;
 620     char *key = NULL;
 621
 622     if (attr && name) {
 623         if (attr->attr_type == MRP_DECISION_ATTR_CONTINUOUS) {
 624             vconf.nentry  = ENUM_MAX;
 625             vconf.comp    = mrp_string_comp;
 626             vconf.hash    = mrp_string_hash;
 627             vconf.free    = value_destroy;
 628             vconf.nbucket = ENUM_BUCKETS;
 629
 630             attr->attr_type = MRP_DECISION_ATTR_ENUM;
 631             attr->nvalue    = 0;
 632             attr->values    = mrp_htbl_create(&vconf);
 633         }
 634
 635         if (!(key = mrp_strdup(name)) || !(value = mrp_allocz(sizeof(*value))))
 636             mrp_free((void *)key);
 637         else {
 638             value->integer = attr->nvalue++;
 639             mrp_htbl_insert(attr->values, key, value);
 640         }
 641     }
 642 }
 643
 644 static int attr_value_iter_cb(void *key, void *object, void *user_data)
 645 {
 646     attr_value_iter_t *it = (attr_value_iter_t *)user_data;
 647     const char *name = (const char *)key;
 648     mrp_decision_value_t *value = (mrp_decision_value_t *)object;
 649     mrp_decision_attr_value_desc_t *desc;
 650
 651     if (it->ndesc >= it->attr->nvalue) {
 652         mrp_log_error("gam-resource-manager: detected inconsitency while "
 653                       "iterating decision attribute '%s' for '%s'",
 654                       name, it->attr->name);
 655     }
 656     else {
 657         desc = it->descs + it->ndesc++;
 658         desc->name = name;
 659         desc->value = value->integer;
 660     }
 661
 662     return MRP_HTBL_ITER_MORE;
 663 }
 664
 665 static attr_value_iter_t *attr_value_iterator(mrp_decision_attr_t *attr)
 666 {
 667     attr_value_iter_t *it;
 668     mrp_decision_attr_value_desc_t tmp;
 669     size_t size;
 670     int i,j;
 671
 672     if (!attr)
 673         it = NULL;
 674     else {
 675         size = sizeof(*it) +
 676                (sizeof(mrp_decision_attr_value_desc_t) * attr->nvalue);
 677
 678         if ((it = mrp_allocz(size))) {
 679             it->attr = attr;
 680             it->ndesc = 0;
 681             mrp_htbl_foreach(attr->values, attr_value_iter_cb, it);
 682
 683             for (i = 0;   i < it->ndesc - 1;   i++) {
 684                 for (j = i + 1;  j < it->ndesc;   j++) {
 685                     if (it->descs[i].value > it->descs[j].value) {
 686                         tmp = it->descs[i];
 687                         it->descs[i] = it->descs[j];
 688                         it->descs[j] = tmp;
 689                     }
 690                 }
 691             }
 692         }
 693     }
 694
 695     return it;
 696 }
 697
 698 static size_t attr_print(mrp_decision_attr_t *attr, bool decision,
 699                          char *buf, size_t len)
 700 {
 701 #define PRINT(args...) \
 702     do { if (p < e) p += snprintf(p, e-p, args); } while (0)
 703
 704     attr_value_iter_t *it;
 705     mrp_decision_attr_value_desc_t *dsc;
 706     char *p, *e;
 707     const char *sep;
 708     char nambuf[256];
 709     int i;
 710
 711     e = (p = buf) + len;
 712
 713     if (attr && p < e) {
 714         snprintf(nambuf, sizeof(nambuf), "%2d %s:", attr->id, attr->name);
 715         PRINT(" %c %-24s @%03zu  ", decision ? '*':' ', nambuf, attr->offset);
 716
 717         switch (attr->attr_type) {
 718
 719         case MRP_DECISION_ATTR_ENUM:
 720             if (!(it = attr_value_iterator(attr)))
 721                 PRINT("<error>\n");
 722             else {
 723                 PRINT("{");
 724                 for (i = 0;   i < it->ndesc;   i++) {
 725                     dsc = it->descs + i;
 726                     sep = (i == 0) ?  ""   : ((i % 10) ?
 727                                       ", " :
 728                                       ",\n                                  ");
 729                     PRINT("%s[%d (%s)]", sep, dsc->value, dsc->name);
 730                 }
 731                 PRINT("}\n");
 732
 733                 mrp_free(it);
 734             }
 735             break;
 736
 737         case MRP_DECISION_ATTR_CONTINUOUS:
 738             PRINT("continuous\n");
 739             break;
 740
 741         default:
 742             PRINT("<unsupported attribute type %d>\n", attr->attr_type);
 743             break;
 744         }
 745     }
 746
 747     return p - buf;
 748
 749 #undef PRINT
 750 }
 751
 752 static void value_destroy(void *key, void *object)
 753 {
 754     mrp_free(key);
 755     mrp_free(object);
 756 }
 757
 758
 759 mrp_decision_node_t *mrp_decision_tree_create_from_file(
 760                                              mrp_decision_conf_t *conf,
 761                                              const char *stem)
 762 {
 763     FILE *f;
 764     char filnam[1024];
 765     char *buf, *p;
 766     size_t n;
 767     ssize_t linlen;
 768     size_t lineno;
 769     mrp_decision_node_t *root, *node;
 770     mrp_decision_value_type_t vtype;
 771     char *name, *value;
 772
 773     if (!stem)
 774         stem = conf->stem;
 775
 776     snprintf(filnam, sizeof(filnam), "%s.tree", stem);
 777     if (!(f = fopen(filnam, "r"))) {
 778         printf("failed to open file '%s': %s\n", filnam, strerror(errno));
 779         return NULL;
 780     }
 781
 782     vtype = conf->decision_attr->value_type;
 783
 784     if (!(root = mrp_decision_tree_create(stem, vtype))) {
 785         mrp_log_error("gam-resource-manager: failed to create "
 786                       "decision tree for '%s'", stem);
 787         return NULL;
 788     }
 789
 790     lineno = 0;
 791     buf = NULL;
 792     node = NULL;
 793
 794     while ((linlen = getline(&buf, &n, f)) >= 0) {
 795         lineno++;
 796         p = buf;
 797
 798         whitespace(&p);
 799
 800         if (!strncmp(p, "type", 4)) {
 801             if (!(tree_parse(conf, f, &lineno, buf, &node, 0)))
 802                 goto failed;
 803             if (!(mrp_decision_add_node_to_root(root, node)))
 804                 goto failed;
 805             node = NULL;
 806         }
 807         else if (property(&p, &name, &value)) {
 808             if (!strcmp(name, "id")) {
 809                 mrp_debug("id: %s", value);
 810             }
 811             else if (!strcmp(name, "entries")) {
 812                 mrp_debug("entries: %s", value);
 813             }
 814             else {
 815                 goto parse_error;
 816             }
 817         }
 818
 819         free(buf);
 820         buf = NULL;
 821     }
 822
 823     if (linlen < 0 && !feof(f)) {
 824         mrp_log_error("gam-resource-manager: error during reading "
 825                       "'%s' file: %s", filnam, strerror(errno));
 826         goto failed;
 827     }
 828
 829     fclose(f);
 830
 831     mrp_log_info("mrp-resource-manager: successfully loaded "
 832                  "decision tree from file '%s'", filnam);
 833
 834     return root;
 835
 836  parse_error:
 837     mrp_log_error("gam-resource-manager: error in file '%s' line %zu",
 838                   filnam, lineno);
 839  failed:
 840     mrp_log_error("gam-resource-manager: failed to parse '%s' file",
 841                   filnam);
 842     free(buf);
 843     fclose(f);
 844     mrp_decision_tree_destroy(root);
 845     mrp_decision_tree_destroy(node);
 846     return NULL;
 847 }
 848
 849 static const char *indent(int depth)
 850 {
 851     static char buf[1024];
 852     size_t l = depth * 3;
 853     memset(buf, ' ', l);
 854     buf[l] = 0;
 855     return buf;
 856 }
 857
 858 static bool tree_parse(mrp_decision_conf_t *conf,
 859                        FILE *f, size_t *lineno,
 860                        char *buf,
 861                        mrp_decision_node_t **node,
 862                        int depth)
 863 {
 864     char *p = buf;
 865     char *name, *value, *e;
 866     int type;
 867
 868     if (!property(&p, &name, &value) || strcmp(name, "type"))
 869         return false;
 870
 871     type = strtol(value, &e, 10);
 872
 873     if (e == value || *e)
 874         return false;
 875
 876     switch (type) {
 877     case 0:
 878         return tree_parse_terminal_node(conf, f, lineno, p, false, node, depth);
 879
 880     case 1:
 881     case 2:
 882     case 3:
 883         return tree_parse_test_node(conf, f, lineno, p, type, node, depth);
 884
 885     default:
 886         return false;
 887     }
 888
 889     return true;
 890 }
 891
 892 static bool tree_parse_terminal_node(mrp_decision_conf_t *conf,
 893                                      FILE *f, size_t *lineno,
 894                                      char *buf,
 895                                      bool need_empty,
 896                                      mrp_decision_node_t **node,
 897                                      int depth)
 898 {
 899     char *p = buf;
 900     char *name, *value;
 901     mrp_decision_value_t *vptr;
 902     char *decision_name;
 903     int32_t decision;
 904     bool has_decision;
 905     bool has_cases;
 906
 907     MRP_UNUSED(f);
 908     MRP_UNUSED(lineno);
 909     MRP_UNUSED(depth);
 910
 911     has_decision = false;
 912     has_cases = false;
 913
 914     while (*p) {
 915         if (!property(&p, &name, &value))
 916             break;
 917
 918         if (!strcmp(name, "class")) {
 919             if (!(vptr = mrp_htbl_lookup(conf->decision_attr->values, value)))
 920                 return false;
 921             else {
 922                 decision_name = value;
 923                 decision = vptr->integer;
 924                 has_decision = true;
 925             }
 926         }
 927         if (!strcmp(name, "freq")) {
 928             has_cases = true;
 929         }
 930
 931         whitespace(&p);
 932     }
 933
 934     if (has_decision) {
 935         if (!need_empty && node) {
 936             mrp_debug("%sterminal: %d/%s", indent(depth),
 937                   decision, decision_name);
 938             if (!(*node = mrp_decision_create_terminal_node(vptr)))
 939                 return false;
 940             return true;
 941         }
 942         if (need_empty && !has_cases)
 943             return true;
 944     }
 945
 946     return false;
 947 }
 948
 949 static bool tree_parse_test_node(mrp_decision_conf_t *conf,
 950                                  FILE *f, size_t *lineno,
 951                                  char *buf,
 952                                  int type,
 953                                  mrp_decision_node_t **node,
 954                                  int depth)
 955 {
 956     mrp_decision_node_t *child;
 957     char *p;
 958     char *name, *value;
 959     mrp_decision_attr_t *attr;
 960     int nbr;
 961     char *e;
 962     size_t n;
 963     char *buf2;
 964     int listidx;
 965     value_list_t *lists, *l;
 966     value_list_item_t *iv;
 967     mrp_decision_value_t *av;
 968     mrp_decision_value_type_t testval_type;
 969     mrp_decision_value_t testval;
 970     mrp_decision_condition_t testcond;
 971     int i,j,k;
 972     attr_value_iter_t *ait;
 973     char valbuf[4096], *q;
 974     size_t size;
 975     bool ok, success;
 976     char dbgbuf[256];
 977
 978     p = buf;
 979     child = NULL;
 980     attr = NULL;
 981     nbr  = -1;
 982     listidx = 0;
 983     lists = NULL;
 984     buf2 = NULL;
 985     ait = NULL;
 986     success = false;
 987
 988     testcond = MRP_DECISION_EQ;
 989     testval_type = MRP_DECISION_VALUE_UNKNOWN;
 990     memset(&testval, 0, sizeof(testval));
 991
 992     while (*p) {
 993         if (!property(&p, &name, &value))
 994             break;
 995
 996         if (!strcmp(name, "att")) {
 997             if (attr)
 998                 goto finish_parsing;
 999
1000             if (!(attr = mrp_htbl_lookup(conf->attrs, value)))
1001                 goto finish_parsing;
1002         }
1003         else if (!strcmp(name, "forks")) {
1004             if (nbr >= 0)
1005                 goto finish_parsing;
1006
1007             nbr = strtol(value, &e, 10);
1008
1009             if (*e || e == value || nbr <= 0 || nbr > 100)
1010                 goto finish_parsing;
1011
1012             if (type == 3)
1013                 lists = mrp_allocz(sizeof(*lists) * nbr);
1014         }
1015         else if (!strcmp(name, "elts")) {
1016             if (!attr || !lists || listidx >= nbr)
1017                 goto finish_parsing;
1018
1019             l = lists + listidx++;
1020             l->items = mrp_allocz(sizeof(l->items[0]) * attr->nvalue);
1021
1022             do {
1023                 if (l->size >= attr->nvalue)
1024                     goto finish_parsing;
1025                 if (!(av = mrp_htbl_lookup(attr->values, value)))
1026                     goto finish_parsing;
1027
1028                 iv = l->items + l->size++;
1029                 iv->name = value;
1030                 iv->value = av->integer;
1031
1032             } while (list_item(&p, &value));
1033         }
1034
1035         whitespace(&p);
1036
1037     } /* while property */
1038
1039     if (attr && nbr > 0) {
1040         if (type == 1) {
1041             if (getline(&buf2, &n, f) < 0)
1042                 goto finish_parsing;
1043
1044             if (!tree_parse_terminal_node(conf, f,lineno,buf2, true, NULL, 0))
1045                 goto finish_parsing;
1046
1047             free(buf2);
1048             buf2 = NULL;
1049             nbr--;
1050             if (!(ait = attr_value_iterator(attr)))
1051                 goto finish_parsing;
1052         }
1053
1054         mrp_debug("%stest/%d: '%s'", indent(depth), nbr, attr->name);
1055
1056         if (!(*node = mrp_decision_create_test_node()))
1057             goto finish_parsing;
1058
1059         for (i=0, buf2=NULL;  i < nbr && getline(&buf2,&n,f) >= 0;   i++) {
1060             (*lineno)++;
1061
1062             switch (type) {
1063
1064             case 1:
1065                 testval_type = MRP_DECISION_VALUE_INTEGER;
1066                 testval.integer = ait->descs[i].value;
1067                 testcond = MRP_DECISION_EQ;
1068                 snprintf(valbuf, sizeof(valbuf), "%s", ait->descs[i].name);
1069                 break;
1070
1071             case 2:
1072                 break;
1073
1074             case 3:
1075                 testval_type = MRP_DECISION_VALUE_UNKNOWN;
1076                 l = lists + i;
1077                 if (l->size == 1) {
1078                     testcond = MRP_DECISION_EQ;
1079                     testval_type = MRP_DECISION_VALUE_INTEGER;
1080                     testval.integer = l->items[0].value;
1081                     snprintf(valbuf, sizeof(valbuf), "%s", l->items[0].name);
1082                 }
1083                 else {
1084                     testcond = MRP_DECISION_IN;
1085                     if (l->size <= (int)MRP_DECISION_BITMASK_WIDTH) {
1086                         testval_type = MRP_DECISION_VALUE_BITMASK;
1087                         testval.bitmask = 0;
1088                     }
1089                     else {
1090                         testval_type = MRP_DECISION_ARRAY |
1091                             MRP_DECISION_VALUE_INTEGER;
1092                         testval.array.size = l->size;
1093                         size = sizeof(mrp_decision_value_t) * testval.array.size;
1094                         testval.array.values = mrp_allocz(size);
1095                     }
1096                     e = (q = valbuf) + sizeof(valbuf);
1097                     for (j = 0;   j < l->size;   j++) {
1098                         if (q < e) {
1099                             q += snprintf(q, e-q, "%s%s",
1100                                           j?",":"", l->items[j].name);
1101                         }
1102                         k = l->items[j].value;
1103                         if (testval_type == MRP_DECISION_VALUE_BITMASK)
1104                             testval.bitmask |= MRP_DECISION_BIT(k);
1105                         else
1106                             testval.array.values[j].integer = k;
1107                     }
1108                 }
1109                 break;
1110
1111             default:
1112                 goto finish_parsing;
1113             }
1114
1115             switch (testval_type) {
1116             case MRP_DECISION_VALUE_BITMASK:
1117                 snprintf(dbgbuf, sizeof(dbgbuf), " 0x%x", testval.bitmask);
1118                 break;
1119             case MRP_DECISION_VALUE_INTEGER:
1120                 snprintf(dbgbuf, sizeof(dbgbuf), " %d", testval.integer);
1121                 break;
1122             default:
1123                 dbgbuf[0] = 0;
1124             }
1125             mrp_debug("%s%s %s '%s'%s", indent(depth+1),
1126                       mrp_decision_condition_str(testcond),
1127                       mrp_decision_value_type_str(testval_type),
1128                       valbuf, dbgbuf);
1129
1130             if (!tree_parse(conf, f, lineno, buf2, &child, depth+2))
1131                 goto finish_parsing;
1132
1133             ok = mrp_decision_add_branch_to_test_node(*node, testcond, attr->id,
1134                                                       testval_type, &testval,
1135                                                       attr->offset, child);
1136             if (!ok)
1137                 goto finish_parsing;
1138
1139             child = NULL;
1140             if ((testval_type & MRP_DECISION_ARRAY))
1141                 mrp_free(testval.array.values);
1142             testval_type = MRP_DECISION_VALUE_UNKNOWN;
1143
1144             free(buf2);
1145             buf2 = NULL;
1146         }
1147
1148         success = true;
1149     }
1150
1151  finish_parsing:
1152     if (lists) {
1153         for (i = 0; i < nbr; i++)
1154             free(lists[i].items);
1155         mrp_free(lists);
1156     }
1157     if ((testval_type & MRP_DECISION_ARRAY))
1158         mrp_free(testval.array.values);
1159     mrp_decision_tree_destroy(child);
1160     mrp_free(ait);
1161     free(buf2);
1162
1163     return success;
1164 }
1165
1166
1167
1168 static bool property(char **buf, char **name, char **value)
1169 {
1170     char *p = *buf;
1171     char term;
1172
1173     if (identifier(&p, name, &term) &&
1174         term == '=' &&
1175         quoted(&p, value))
1176     {
1177         whitespace(&p);
1178         *buf = p;
1179         return true;
1180     }
1181
1182     return false;
1183 }
1184
1185 static bool list_item(char **buf, char **name)
1186 {
1187     char *p = *buf;
1188
1189     whitespace(&p);
1190
1191     if (*p++ != ',')
1192         return false;
1193
1194     if (quoted(&p, name)) {
1195         *buf = p;
1196         return true;
1197     }
1198
1199     return false;
1200 }
1201
1202
1203 static bool identifier(char **buf, char **id, char *term)
1204 {
1205     char *p, *q, c;
1206
1207     q = *buf;
1208
1209     whitespace(&q);
1210
1211     for (p = q;  (c = *p);  p++) {
1212         if (!isalnum(c))
1213             break;
1214     }
1215
1216     if (p == q)
1217         return false;
1218
1219     whitespace(&p);
1220     if ((*term = *p))
1221         *p++ = 0;
1222
1223     *buf = p;
1224     *id = q;
1225     return true;
1226 }
1227
1228
1229 static bool whitespace(char **buf)
1230 {
1231     char *p, c;
1232
1233     for (p = *buf;  (c = *p);  p++) {
1234         if (c != ' ' && c != '\t' && c != '\n')
1235             break;
1236     }
1237
1238     *buf = p;
1239     return true;
1240 }
1241
1242 static bool quoted(char **buf, char **string)
1243 {
1244     char *p, *q, c;
1245
1246     q = *buf;
1247
1248     whitespace(&q);
1249
1250     if (*q++ != '"')
1251         return false;
1252
1253     for (p = q; (c = *p);  p++) {
1254         if (c < 0x20)
1255             return -1;
1256         if (c == '"' && p[-1] != '\\') {
1257             *p++ = 0;
1258             *buf = p;
1259             *string = q;
1260             return true;
1261         }
1262     }
1263
1264     return false;
1265 }
1266
1267 size_t mrp_decision_tree_print(mrp_decision_conf_t *conf,
1268                                mrp_decision_node_t *node,
1269                                char *buf, size_t len)
1270 {
1271     conf_iter_t *cit;
1272     char *p, *e;
1273
1274     e = (p = buf) + len;
1275
1276     if (conf && node && buf && len > 0) {
1277         if (!(cit = conf_iterator(conf)))
1278             p += snprintf(p, e-p, "<error>\n");
1279         else {
1280             p += print_node(conf, node, cit, p, e-p, NULL);
1281             p += snprintf(p, e-p, "\n");
1282             mrp_free(cit);
1283         }
1284     }
1285
1286     return p - buf;
1287 }
1288
1289
1290 static size_t print_node(mrp_decision_conf_t *conf,
1291                          mrp_decision_node_t *node,
1292                          conf_iter_t *cit,
1293                          char *buf, size_t len,
1294                          char *indent)
1295 {
1296 #define PRINT(_args...)      \
1297     do {if (p < e) p += snprintf(p,e-p, _args);} while(0)
1298 #define PRINT_VALUE(_t,_v)   \
1299     do {if (p < e) p += mrp_decision_value_print(_t, _v, p,e-p);} while(0)
1300 #define PRINT_BITMASK(_a,_m) \
1301     do {if (p < e) p += print_bitmask(_a, _m, p, e-p);} while(0)
1302 #define PRINT_NODE(_p,_i)    \
1303     do {if (p < e) p += print_node(conf, (_p)->node, cit, p,e-p, _i);} while(0)
1304
1305     static char indent_buf[4096];
1306     static char *indent_end = indent_buf + sizeof(indent_buf);
1307
1308     mrp_decision_root_node_t *root;
1309     mrp_decision_test_node_t *test;
1310     mrp_decision_terminal_node_t *term;
1311     mrp_decision_branch_t *branch;
1312     mrp_decision_attr_t *attr;
1313     const char *attr_name;
1314     int32_t value_idx;
1315     attr_value_iter_t *ait;
1316     char *p, *e, *new_indent;
1317     int32_t decision;
1318     size_t i;
1319
1320     if (!node || !buf)
1321         return 0;
1322
1323     if (!indent) {
1324         indent_buf[0] = 0;
1325         indent = indent_buf;
1326     }
1327
1328     e = (p = buf) + len;
1329
1330     switch (node->type) {
1331
1332     case MRP_DECISION_ROOT_NODE:
1333         root = &node->root;
1334         PRINT("root of %s (decision type: %s)", root->name,
1335               mrp_decision_value_type_str(root->decision_value_type));
1336         new_indent  = indent;
1337         new_indent += snprintf(indent, indent_end-indent, "\n");
1338         PRINT_NODE(root, new_indent);
1339         *indent = 0;
1340         break;
1341
1342     case MRP_DECISION_TEST_NODE:
1343         test = &node->test;
1344
1345         for (i = 0;  i < test->nbranch;  i++) {
1346             branch = test->branches + i;
1347             if (branch->value_id < 0 || branch->value_id >= cit->nattr)
1348                 PRINT("%s:...<invalid attribute>", indent_buf);
1349             else {
1350                 attr = cit->attrs[branch->value_id];
1351                 attr_name = attr ? attr->name : "<invalid attribute>";
1352                 PRINT("%s:...%s %s ", indent_buf, attr_name,
1353                       mrp_decision_condition_str(branch->condition));
1354
1355                 if (branch->value_type != MRP_DECISION_VALUE_INTEGER) {
1356                     PRINT_VALUE(branch->value_type, &branch->value);
1357                     if (branch->value_type == MRP_DECISION_VALUE_BITMASK) {
1358                         PRINT(" (");
1359                         PRINT_BITMASK(attr, branch->value.bitmask);
1360                         PRINT(")");
1361                     }
1362                 }
1363                 else {
1364                     value_idx = branch->value.integer;
1365                     if (value_idx < 0 || value_idx >= attr->nvalue ||
1366                         !(ait = attr_value_iterator(attr)))
1367                         PRINT("<invalid attribute value>");
1368                     else {
1369                         PRINT("%d (%s)", value_idx, ait->descs[value_idx].name);
1370                         mrp_free(ait);
1371                     }
1372                 }
1373             }
1374             new_indent  = indent;
1375             new_indent += snprintf(new_indent, indent_end-indent, "%c   ",
1376                                    i == test->nbranch-1 ? ' ':':');
1377             PRINT_NODE(branch, new_indent);
1378             *indent = 0;
1379         }
1380
1381         break;
1382
1383     case MRP_DECISION_TERMINAL_NODE:
1384         term = &node->terminal;
1385         decision = term->decision.integer;
1386         if (decision < 0 || decision >= conf->decision_attr->nvalue)
1387             PRINT(" => decision <invalid value>");
1388         else
1389             PRINT(" => %s", conf->decision_names[decision]);
1390         break;
1391
1392     default:
1393         PRINT("%s<unknown node type %d>\n", indent_buf, node->type);
1394         break;
1395     }
1396
1397     return p - buf;
1398
1399 #undef PRINT_VALUE
1400 #undef PRINT
1401 }
1402
1403
1404 static size_t print_bitmask(mrp_decision_attr_t *attr,
1405                             mrp_decision_bitmask_t bitmask,
1406                             char *buf, size_t len)
1407 {
1408     attr_value_iter_t *it;
1409     mrp_decision_bitmask_t m;
1410     char *p, *e;
1411     int i,j;
1412     char *sep;
1413
1414     if (!attr || !buf || len < 1)
1415         return 0;
1416
1417     if (!(it = attr_value_iterator(attr)))
1418         return 0;
1419
1420     e = (p = buf) + len;
1421
1422     if (!(m = bitmask))
1423         p += snprintf(p, e-p, "<empty>");
1424     else {
1425         for (i = 0, sep = "";   m && i < it->ndesc && p < e;  i++, m >>= 1) {
1426             if ((m & 1)) {
1427                 if (it->descs[i].value == i)
1428                     j = i;
1429                 else {
1430                     for (j = 0;  j < it->ndesc;  j++) {
1431                         if (it->descs[j].value == i)
1432                             break;
1433                     }
1434                 }
1435                 if (j < 0 || j >= it->ndesc)
1436                     p += snprintf(p, e-p, "%s<unknown value %d>", sep, j);
1437                 else
1438                     p += snprintf(p, e-p, "%s%s", sep, it->descs[j].name);
1439                 sep = ",";
1440             }
1441         }
1442     }
1443
1444     mrp_free(it);
1445
1446     return p - buf;
1447 }