src/resolver/target-sorter.c

   1 /*
   2  * Copyright (c) 2012, 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
  30 #include <errno.h>
  31
  32 #include <murphy/common/mm.h>
  33 #include <murphy/common/debug.h>
  34 #include <murphy/common/log.h>
  35
  36 #include "scanner.h"
  37 #include "resolver.h"
  38 #include "resolver-types.h"
  39 #include "fact.h"
  40 #include "target.h"
  41 #include "target-sorter.h"
  42
  43
  44 /*
  45  * dependency graph used to determine target update orders
  46  */
  47
  48 typedef struct {
  49     mrp_resolver_t *r;                   /* resolver context */
  50     int            *edges;               /* edges between nodes */
  51     int             nnode;               /* number of graph nodes */
  52 } graph_t;
  53
  54
  55 static graph_t *build_graph(mrp_resolver_t *r);
  56 static int sort_graph(graph_t *g, int target_idx);
  57 static void free_graph(graph_t *g);
  58 static void dump_graph(graph_t *g, FILE *fp);
  59
  60
  61 int sort_targets(mrp_resolver_t *r)
  62 {
  63     graph_t *g;
  64     int      i, status;
  65
  66     g = build_graph(r);
  67
  68     if (g != NULL) {
  69         dump_graph(g, stdout);
  70
  71         status = 0;
  72
  73         for (i = 0; i < r->ntarget; i++) {
  74             target_t *t = r->targets + i;
  75
  76             mrp_free(t->update_targets);
  77             mrp_free(t->update_facts);
  78             mrp_free(t->fact_stamps);
  79             mrp_free(t->directs);
  80             t->update_targets = NULL;
  81             t->update_facts   = NULL;
  82             t->fact_stamps    = NULL;
  83             t->ndirect        = 0;
  84         }
  85
  86         for (i = 0; i < r->ntarget; i++) {
  87             if (sort_graph(g, i) < 0) {
  88                 mrp_log_error("Failed to determine update order for "
  89                               "resolver target '%s'.", r->targets[i].name);
  90
  91                 if (errno == ELOOP)
  92                     mrp_log_error("Cyclic dependency detected.");
  93
  94                 status = -1;
  95                 break;
  96             }
  97         }
  98
  99         free_graph(g);
 100     }
 101     else
 102         status = -1;
 103
 104     return status;
 105 }
 106
 107
 108 static inline int fact_id(graph_t *g, char *fact)
 109 {
 110     int i;
 111
 112     for (i = 0; i < g->r->nfact; i++)
 113         if (!strcmp(fact, g->r->facts[i].name))
 114             return i;
 115
 116     return -1;
 117 }
 118
 119
 120 static inline int target_id(graph_t *g, char *target)
 121 {
 122     int i;
 123
 124     for (i = 0; i < g->r->ntarget; i++)
 125         if (!strcmp(target, g->r->targets[i].name))
 126             return g->r->nfact + i;
 127
 128     return -1;
 129 }
 130
 131
 132 static inline char *node_name(graph_t *g, int id)
 133 {
 134     if (id < g->r->nfact)
 135         return g->r->facts[id].name;
 136     else
 137         return g->r->targets[id - g->r->nfact].name;
 138 }
 139
 140
 141 static inline int node_id(graph_t *g, char *name)
 142 {
 143     if (name[0] == '$')
 144         return fact_id(g, name);
 145     else
 146         return target_id(g, name);
 147 }
 148
 149
 150 static inline int *edge_markp(graph_t *g, int n1, int n2)
 151 {
 152     static int invalid = 0;
 153
 154     if (n1 >= 0 && n2 >= 0)
 155         return g->edges + (n1 * g->nnode) + n2;
 156     else
 157         return &invalid;
 158 }
 159
 160
 161 static inline void mark_node(graph_t *g, int node)
 162 {
 163     *edge_markp(g, node, node) = 1;
 164 }
 165
 166
 167 static inline void unmark_node(graph_t *g, int node)
 168 {
 169     *edge_markp(g, node, node) = 0;
 170 }
 171
 172
 173 static inline int node_present(graph_t *g, int node)
 174 {
 175     return *edge_markp(g, node, node) == 1;
 176 }
 177
 178
 179 static graph_t *build_graph(mrp_resolver_t *r)
 180 {
 181     graph_t  *g;
 182     int       tid, did, i, j;
 183     target_t *t;
 184
 185     g = mrp_allocz(sizeof(*g));
 186
 187     if (g != NULL) {
 188         g->r     = r;
 189         g->nnode = r->nfact + r->ntarget;
 190         g->edges = mrp_allocz(g->nnode * g->nnode * sizeof(*g->edges));
 191
 192         if (g->edges == NULL)
 193             goto fail;
 194
 195         for (i = 0; i < r->ntarget; i++) {
 196             t   = r->targets + i;
 197             tid = r->nfact + i;
 198
 199             for (j = 0; j < t->ndepend; j++) {
 200                 mrp_debug("adding edge: %s <- %s", t->depends[j], t->name);
 201                 did = node_id(g, t->depends[j]);
 202
 203                 if (did < 0)
 204                     goto fail;
 205
 206                 *edge_markp(g, did, tid) = 1;
 207             }
 208         }
 209     }
 210
 211     return g;
 212
 213  fail:
 214     if (g != NULL) {
 215         mrp_free(g->edges);
 216         mrp_free(g);
 217     }
 218     return NULL;
 219 }
 220
 221
 222 static int mark_present_nodes(graph_t *g, int target_idx)
 223 {
 224     int       tid, did, i;
 225     target_t *t;
 226
 227     tid = g->r->nfact + target_idx;
 228     t   = g->r->targets + target_idx;
 229
 230     if (node_present(g, tid))
 231         return TRUE;
 232
 233     mark_node(g, tid);
 234
 235     for (i = 0; i < t->ndepend; i++) {
 236         did = node_id(g, t->depends[i]);
 237
 238         if (did < 0)
 239             return FALSE;
 240
 241         if (*t->depends[i] == '$')
 242             mark_node(g, did);
 243         else {
 244             if (!mark_present_nodes(g, did - g->r->nfact))
 245                 return FALSE;
 246         }
 247     }
 248
 249     return TRUE;
 250 }
 251
 252
 253 /*
 254  * queues we use for topological sorting
 255  */
 256
 257 typedef struct {
 258     int  size;                           /* max queue capacity */
 259     int *items;                          /* queue item buffer */
 260     int  head;                           /* push index */
 261     int  tail;                           /* pop index */
 262 } que_t;
 263
 264 #define EMPTY_QUE {.items = NULL }       /* initializer for empty queue */
 265
 266
 267 static int que_init(que_t *q, int size)
 268 {
 269     mrp_free(q->items);
 270
 271     q->items = mrp_alloc(size * sizeof(*q->items));
 272
 273     if (q->items != NULL) {
 274         q->size = size;
 275         q->head = 0;
 276         q->tail = 0;
 277
 278         return TRUE;
 279     }
 280     else
 281         return FALSE;
 282 }
 283
 284
 285 static void que_cleanup(que_t *q)
 286 {
 287     mrp_free(q->items);
 288     q->items = NULL;
 289 }
 290
 291
 292 static void que_push(que_t *q, int item)
 293 {
 294     /* we know the max size, so we don't check for overflow here */
 295     q->items[q->tail++] = item;
 296     q->tail            %= q->size;
 297 }
 298
 299
 300 static int que_pop(que_t *q, int *itemp)
 301 {
 302     if (q->head != q->tail) {
 303         *itemp   = q->items[q->head++];
 304         q->head %= q->size;
 305
 306         return TRUE;
 307     }
 308     else {
 309         *itemp = -1;
 310         return FALSE;
 311     }
 312 }
 313
 314
 315 static int sort_graph(graph_t *g, int target_idx)
 316 {
 317     /*
 318      * Notes:
 319      *
 320      *   We perform a topological sort of the dependency graph here
 321      *   for our target with the given idx. We include only nodes
 322      *   for facts and targets which are relevant for our target.
 323      *   These are the ones which our target directly or indirectly
 324      *   depends on. We use the otherwise unused diagonal (no target
 325      *   can depend on itself) of our edge matrix to mark which nodes
 326      *   are present in the graph. Then we use the following algorithm
 327      *   to sort the subgraph of relevant nodes:
 328      *
 329      *       initialize que L to be empty
 330      *       initialize que Q with all nodes without incoming edges
 331      *       while Q is not empty
 332      *           pop a node <n> from Q
 333      *           push <n> to L
 334      *           remove all edges that start from <n>
 335      *           for all nodes <m> where we removed an incoming node
 336      *               if <m> has no more incoming edges
 337      *                   push <m> to Q
 338      *
 339      *       if there are any remaining edges
 340      *           return an error about cyclic dependency
 341      *       else
 342      *           L is the sorted subgraph (our target is the last item in L)
 343      *
 344      *   The resulted sort order of our target is then used as the
 345      *   dependency check/update order when the resolver is asked to
 346      *   update that target.
 347      */
 348
 349     target_t *target;
 350     int       edges[g->nnode * g->nnode];
 351     que_t     L = EMPTY_QUE, Q = EMPTY_QUE;
 352     int       i, j, m, id, node, nedge, nfact, ntarget;
 353
 354     target = g->r->targets + target_idx;
 355
 356     /* save full graph */
 357     memcpy(edges, g->edges, sizeof(edges));
 358
 359     if (!que_init(&L, g->nnode + 1) || !que_init(&Q, g->nnode))
 360         goto fail;
 361
 362     /* find and mark relevant nodes in the graph */
 363     mark_present_nodes(g, target_idx);
 364
 365     mrp_debug("-- target %s --", target->name);
 366     /*dump_graph(g, stdout);*/
 367
 368     /* push all relevant facts, they do not depend on anything */
 369     for (i = 0; i < g->r->nfact; i++) {
 370         id = i;
 371         if (node_present(g, id)) {
 372             que_push(&Q, id);
 373             unmark_node(g, id);
 374         }
 375     }
 376
 377     /* push all relevant targets that have no dependencies */
 378     for (i = 0; i < g->r->ntarget; i++) {
 379         id = g->r->nfact + i;
 380         if (g->r->targets[i].depends == NULL && node_present(g, id)) {
 381             que_push(&Q, id);
 382             unmark_node(g, id);
 383         }
 384     }
 385
 386     /* try sorting the marked subgraph */
 387     while (que_pop(&Q, &node)) {
 388         que_push(&L, node);
 389
 390         mrp_debug("popped node %s", node_name(g, node));
 391
 392         for (m = 0; m < g->nnode; m++) {
 393             if (m == node || !node_present(g, m))
 394                 continue;
 395             *edge_markp(g, node, m) = 0;
 396             nedge = 0;
 397             for (j = 0; j < g->nnode; j++) {
 398                 if (j == m)
 399                     continue;
 400                 if (node_present(g, j) && *edge_markp(g, j, m))
 401                     nedge++;
 402             }
 403             if (nedge == 0) {
 404                 mrp_debug("node %s empty, pushing it", node_name(g, m));
 405                 que_push(&Q, m);
 406                 unmark_node(g, m);
 407             }
 408             else
 409                 mrp_debug("node %s not empty yet", node_name(g, m));
 410         }
 411     }
 412
 413     /* check if the subgraph has any remaining edges */
 414     nedge = 0;
 415     for (node = 0; node < g->nnode; node++) {
 416         if (!node_present(g, node))
 417             continue;
 418         for (m = 0; m < g->nnode; m++) {
 419             if (m == node || !node_present(g, m))
 420                 continue;
 421             if (*edge_markp(g, node, m) == 1) {
 422                 errno = ELOOP;
 423                 goto fail;
 424             }
 425         }
 426     }
 427
 428     mrp_debug("----- %s: graph sorted successfully -----", target->name);
 429
 430     for (i = 0; i < L.tail; i++)
 431         mrp_debug(" %s", node_name(g, L.items[i]));
 432     mrp_debug("-----");
 433
 434     /* save the result in the given target */
 435     if (L.tail > 0) {
 436         nfact   = 0;
 437         ntarget = 0;
 438
 439         for (i = 0; i < L.tail; i++) {
 440             if (L.items[i] < g->r->nfact)
 441                 nfact++;
 442             else
 443                 ntarget++;
 444         }
 445
 446         if (nfact > 0) {
 447             target->update_facts = mrp_alloc_array(int, nfact + 1);
 448             target->fact_stamps  = mrp_allocz_array(uint32_t, nfact);
 449
 450             if (target->update_facts != NULL && target->fact_stamps != NULL) {
 451                 for (i = 0; i < nfact; i++)
 452                     target->update_facts[i] = L.items[i];
 453                 target->update_facts[i] = -1;
 454             }
 455             else
 456                 goto fail;
 457         }
 458
 459         if (ntarget > 0) {
 460             target->update_targets = mrp_alloc_array(int, ntarget + 1);
 461             if (target->update_targets != NULL) {
 462                 for (i = 0; i < ntarget; i++)
 463                     target->update_targets[i] = L.items[nfact+i] - g->r->nfact;
 464                 target->update_targets[i] = -1;
 465             }
 466             else
 467                 goto fail;
 468         }
 469
 470         target->ndirect = 0;
 471         target->directs = mrp_allocz_array(int, target->ndepend);
 472
 473         if (target->ndepend == 0 || target->directs != NULL) {
 474             fact_t   *f;
 475             target_t *t;
 476
 477             for (i = 0; i < target->ndepend; i++) {
 478                 if (*target->depends[i] != '$')
 479                     continue;
 480
 481                 f = lookup_fact(g->r, target->depends[i]);
 482
 483                 if (f != NULL)
 484                     target->directs[target->ndirect++] = f - g->r->facts;
 485                 else
 486                     target->directs[target->ndirect++] = -1;
 487             }
 488
 489             for (i = 0; i < target->ndepend; i++) {
 490                 if (*target->depends[i] == '$')
 491                     continue;
 492
 493                 t = lookup_target(g->r, target->depends[i]);
 494
 495                 if (t != NULL)
 496                     target->directs[target->ndirect++] = g->r->nfact +
 497                         t - g->r->targets;
 498                 else
 499                     target->directs[target->ndirect++] = -1;
 500             }
 501         }
 502         else
 503             goto fail;
 504     }
 505
 506     que_cleanup(&L);
 507     que_cleanup(&Q);
 508
 509     /* restore the original full graph */
 510     memcpy(g->edges, edges, sizeof(edges));
 511
 512     return 0;
 513
 514  fail:
 515     que_cleanup(&L);
 516     que_cleanup(&Q);
 517
 518     memcpy(g->edges, edges, sizeof(edges));
 519
 520     return -1;
 521 }
 522
 523
 524 static void free_graph(graph_t *g)
 525 {
 526     if (g != NULL) {
 527         mrp_free(g->edges);
 528         mrp_free(g);
 529     }
 530 }
 531
 532
 533 static void dump_graph(graph_t *g, FILE *fp)
 534 {
 535     int i, j;
 536
 537     fprintf(fp, "Graph edges:\n");
 538
 539     fprintf(fp, "  %20.20s ", "");
 540     for (i = 0; i < g->nnode; i++)
 541         fprintf(fp, " %d", i % 10);
 542     fprintf(fp, "\n");
 543
 544     for (i = 0; i < g->nnode; i++) {
 545         fprintf(fp, "  %20.20s: ", node_name(g, i));
 546         for (j = 0; j < g->nnode; j++)
 547             fprintf(fp, "%d ", *edge_markp(g, i, j));
 548         fprintf(fp, "\n");
 549     }
 550 }