itree.c revision aab83bb83be7342f6cfccaed8d5fe0b2f404855d
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*
* itree.c -- instance tree creation and manipulation
*
* this module provides the instance tree
*/
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <strings.h>
#include "alloc.h"
#include "out.h"
#include "stable.h"
#include "literals.h"
#include "lut.h"
#include "tree.h"
#include "ptree.h"
#include "itree.h"
#include "ipath.h"
#include "iexpr.h"
#include "eval.h"
#include "config.h"
/*
* struct info contains the state we keep when expanding a prop statement
* as part of constructing the instance tree. state kept in struct info
* is the non-recursive stuff -- the stuff that doesn't need to be on
* the stack. the rest of the state that is passed between all the
* mutually recursive functions, is required to be on the stack since
* we need to backtrack and recurse as we do the instance tree construction.
*/
struct info {
} Ninfo;
/*
* struct wildcardinfo is used to track wildcarded portions of paths.
*
* for example, if the epname of an event is "c/d" and the path "a/b/c/d"
* exists, the wildcard path ewname is filled in with the path "a/b". when
* matching is done, epname is temporarily replaced with the concatenation
* of ewname and epname.
*
* a linked list of these structs is used to track the expansion of each
* event node as it is processed in vmatch() --> vmatch_event() calls.
*/
struct wildcardinfo {
int got_wc_hz;
struct wildcardinfo *next;
};
struct node *c);
/*
* the following struct contains the state we build up during
* vertical and horizontal expansion so that generate()
* has everything it needs to construct the appropriate arrows.
* after setting up the state by calling:
* generate_arrownp()
* generate_nork()
* generate_new()
* generate_from()
* generate_to()
* the actual arrow generation is done by calling:
* generate()
*/
static struct {
int generation; /* generation number of arrow set */
int matched; /* number of matches */
int n; /* n value associated with arrow */
int k; /* k value associated with arrow */
} G;
static void
{
}
static void
generate_nork(int n, int k)
{
G.n = n;
G.k = k;
}
static void
generate_new(void)
{
G.generation++;
}
static void
{
G.fromnp = fromeventnp;
}
static void
{
}
static void
{
} else {
if (!G.frombp) {
}
}
}
enum childnode_action {
};
static struct node *
{
const char *file;
int line;
return (NULL);
switch (npc->t) {
case T_NUM:
break;
case T_NAME:
break;
default:
"invalid child type %s",
ptree_nodetype2str(npc->t));
}
}
}
} else {
}
}
return (retp);
}
struct prop_wlk_data {
};
/*
* let oldepname be a subset of epname. return the subsection of epname
* that ends with oldepname. make each component in the path explicitly
* instanced (i.e., with a T_NUM child).
*/
static struct node *
{
int foundmatch = 0;
return (NULL);
/*
* search for the longest path in epname which contains
* oldnode->u.event.epname. set npend to point to just past the
* end of this path.
*/
break;
}
foundmatch = 1;
/* oldepname matched npref up to end */
break;
}
}
}
}
if (foundmatch == 0) {
/*
* if oldepname could not be found in epname, return a
* duplicate of the former. do not try to instantize
* oldepname since it might not be a path.
*/
}
/*
* dup (epname -- npend). all children should be T_NUMs.
*/
int childnum;
} else {
}
} else {
}
}
return (ret);
}
/*
* restriction: oldnode->u.event.epname has to be equivalent to or a subset
* of epname
*/
static struct node *
{
epname);
return (ret);
}
static void
{
/* handle engines by instantizing the entire engine */
/* there are only SERD engines for now */
return;
}
switch (orhs->t) {
case T_NUM:
break;
case T_TIMEVAL:
break;
case T_NAME:
break;
case T_EVENT:
break;
case T_GLOBID:
break;
case T_FUNC:
/* for T_FUNC, we don't duplicate it, just point to node */
break;
default:
}
}
static struct lut *
{
struct prop_wlk_data pd;
}
/*ARGSUSED*/
static void
{
/* we allocated the lut during itree_create(), so free it */
}
}
/*ARGSUSED*/
static void
{
}
/*ARGSUSED*/
static void
{
}
/*
* event_cmp -- used via lut_lookup/lut_add on instance tree lut
*/
static int
{
int diff;
return (diff);
return (diff);
return (0);
}
struct event *
{
struct node searcheventnode;
struct node searchenamenode;
searcheventnode.t = T_EVENT;
searchenamenode.t = T_NAME;
}
static struct event *
{
return (ret);
/* wasn't already in tree, allocate it */
return (ret);
}
/*
* Used for handling expansions where first part of oldepname is a horizontal
* expansion. Recurses through entire tree. oldepname argument is always the
* full path as in the rules. Once we find a match we go back to using
* hmatch_event to handle the rest.
*/
static void
{
char *cp_s;
int cp_num;
struct node *saved_ewname;
struct node *saved_epname;
/*
* Found one.
*/
/*
* Need to set ewname, epname for correct node as is
* needed by constraint path matching. This code is
* similar to that in vmatch_event.
*/
/*
* Find correct ewname by walking back up the config
* tree adding each name portion as we go.
*/
}
}
/*
* Now create correct epname by duping new ewname
* and appending oldepname.
*/
/*
* Now complete hmatch.
*/
/*
* set everything back again
*/
}
/*
* Try the next level down.
*/
}
}
/*
* hmatch_event -- perform any appropriate horizontal expansion on an event
*
* this routine is used to perform horizontal expansion on both the
* left-hand-side events in a prop, and the right-hand-side events.
* when called to handle a left-side event, nextnp point to the right
* side of the prop that should be passed to hmatch() for each match
* found by horizontal expansion. when no horizontal expansion exists,
* we will still "match" one event for every event found in the list on
* the left-hand-side of the prop because vmatch() already found that
* there's at least one match during vertical expansion.
*/
static void
{
/*
* end of pathname recursion, either we just located
* a left-hand-side event and we're ready to move on
* to the expanding the right-hand-side events, or
* we're further down the recursion and we just located
* a right-hand-side event. the passed-in parameter
* "nextnp" tells us whether we're working on the left
* side and need to move on to nextnp, or if nextnp is
* NULL, we're working on the right side.
*/
if (nextnp) {
/*
* finished a left side expansion, move on to right.
* tell generate() what event we just matched so
* it can be used at the source of any arrows
* we generate as we match events on the right side.
*/
} else {
/*
* finished a right side expansion. tell generate
* the information about the destination and let
* it construct the arrows as appropriate.
*/
}
return;
}
return;
/*
* we only get here when eventnp already has a completely
* instanced epname in it already. so we first recurse
* down to the end of the name and as the recursion pops
* up, we look for opportunities to advance horizontal
* expansions on to the next match.
*/
char *cp_s;
int cp_num;
int ocp_num;
const char *iters;
int hexpand = 0;
/*
* Ancestor was horizontal though, so must rematch
*/
} else {
/*
* do horizontal expansion on this node
*/
hexpand = 1;
sizeof (struct iterinfo));
hexpand = 1;
} else {
/*
* This name has already been used in a
* horizontal expansion. This time just match it
*/
}
}
/*
* handle case where this is the first section of oldepname
* and it is horizontally expanded. Instead of just looking for
* siblings, we want to scan the entire config tree for further
* matches.
*/
/*
* Run through config looking for any that match the
* name.
*/
return;
}
/*
* Run through siblings looking for any that match the name.
* If hexpand not set then num must also match ocp_num.
*/
if (hexpand)
continue;
nextnp, 1);
}
}
if (hexpand)
} else {
}
}
/*
* hmatch -- check for horizontal expansion matches
*
* np points to the things we're matching (like a T_LIST or a T_EVENT)
* and if we're working on a left-side of a prop, nextnp points to
* the other side of the prop that we'll tackle next when this recursion
* bottoms out. when all the events in the entire prop arrow have been
* horizontally expanded, generate() will be called to generate the
* actualy arrow.
*/
static void
{
return; /* all done */
/*
* for each item in the list of events (which could just
* be a single event, or it could get larger in the loop
* below due to horizontal expansion), call hmatch on
* the right side and create arrows to each element.
*/
switch (np->t) {
case T_LIST:
/* loop through the list */
break;
case T_EVENT:
break;
default:
"hmatch: unexpected type: %s",
ptree_nodetype2str(np->t));
}
}
static int
{
return (1);
return (-1); /* our internal version of "all" */
else
"itree_np2nork: internal error type %s",
ptree_nodetype2str(norknp->t));
/*NOTREACHED*/
return (1);
}
static struct iterinfo *
{
return (ret);
}
/*ARGSUSED*/
static void
{
}
static void
{
char *cp_s;
int cp_num;
int newewname = 0;
/*
* handle case where the first section of the path name is horizontally
* expanded. The whole expansion is handled by hmatch on the first
* match here - so we just skip any subsequent matches here.
*/
return;
/*
* Reached the end of the name. u.name.cp pointers should be set
* up for each part of name. From this we can use config tree
* to build up the wildcard part of the name (if any).
*/
/*
* no wildcarding done - move on to next entry
*/
return;
}
/*
* ewname not yet set up - do it now
*/
newewname = 1;
}
}
}
/*
* dup ewname and append oldepname
*/
/*
* reduce duped ewname to original then free
*/
if (newewname) {
/*
* free ewname if allocated above
*/
}
return;
}
/*
* We have an np. See if we can match it in this section of
* the config tree.
*/
return; /* no more config to match against */
/* found a matching component name */
/*
* an explicit instance number was given
* in the source. so only consider this
* a configuration match if the number
* also matches.
*/
continue;
const char *iters;
/*
* vertical iterator. look it up in
* the appropriate lut and if we get
* back a value it is either one that we
* set earlier, in which case we record
* the new value for this iteration and
* keep matching, or it is one that was
* set by an earlier reference to the
* iterator, in which case we only consider
* this a configuration match if the number
* matches cp_num.
*/
/* we're the first use, record our np */
(void *)iters,
/*
* we're the first use, back again
* for another iteration. so update
* the num bound to this iterator in
* the lut.
*/
/*
* an earlier reference to this
* iterator bound it to a different
* instance number, so there's no
* match here after all.
*
* however, it's possible that this
* component should really be part of
* the wildcard. we explore this by
* forcing this component into the
* wildcarded section.
*
* for an more details of what's
* going to happen now, see
* comments block below entitled
* "forcing components into
* wildcard path".
*/
continue;
}
}
/*
* if this was an IT_HORIZONTAL name, hmatch() will
* expand all matches horizontally into a list.
* we know the list will contain at least
* one element (the one we just matched),
* so we just let hmatch_event() do the rest.
*
* recurse on to next component. Note that
* wildcarding is now turned off.
*/
/*
* handle case where this is the first section of the
* path name and it is horizontally expanded.
* In this case we want all matching nodes in the config
* to be expanded horizontally - so set got_wc_hz and
* leave all further processing to hmatch.
*/
/*
* forcing components into wildcard path:
*
* if this component is the first match, force it
* to be part of the wildcarded path and see if we
* can get additional matches.
*
* here's an example. suppose we have the
* definition
* event foo@x/y
* and configuration
*
* the code up to this point will treat "a0" as the
* nonwildcarded part, resulting in the instanced
* event
*
* in the configuration we have to force "x0" into
* the wildcarded part of the path.
* by doing so, we discover the wildcarded part
*
* the following call to vmatch_event() is also
* needed to properly handle the configuration
*
* the recursions into vmatch_event() will start
* off uncovering "b0" as the wildcarded part and
* "x0" as the start of the nonwildcarded path.
* however, the next recursion will not result in a
* match since there is no "y" following "x0". the
* if "x0" is forced to be a part of the wildcarded
* path.
*/
/*
* hmatch() finished iterating through
* the configuration as described above, so
* don't continue iterating here.
*/
return;
}
/*
* no match - carry on down the tree looking for
* wildcarding
*/
wcp);
}
}
}
/*
* vmatch -- find the next vertical expansion match in the config database
*
* this routine is called with three node pointers:
* np -- the parse we're matching
* lnp -- the rest of the list we're currently working on
* anp -- the rest of the arrow we're currently working on
*
* the expansion matching happens via three types of recursion:
*
* - when given an arrow, handle the left-side and then recursively
* handle the right side (which might be another cascaded arrow).
*
* - when handling one side of an arrow, recurse through the T_LIST
* to get to each event (or just move on to the event if there
* is a single event instead of a list) since the arrow parse
* trees recurse left, we actually start with the right-most
* event list in the prop statement and work our way towards
* the left-most event list.
*
* - when handling an event, recurse down each component of the
* pathname, matching in the config database and recording the
* matches in the explicit iterator dictionary as we go.
*
* when the bottom of this matching recursion is met, meaning we have
* set the "cp" pointers on all the names in the entire statement,
* we call hmatch() which does it's own recursion to handle horizontal
* expandsion and then call generate() to generate nodes, bubbles, and
* arrows in the instance tree. generate() looks at the cp pointers to
* see what instance numbers were matched in the configuration database.
*
* when horizontal expansion appears, vmatch() finds only the first match
* and hmatch() then takes the horizontal expansion through all the other
* matches when generating the arrows in the instance tree.
*
* the "infop" passed down through the recursion contains a dictionary
* of the explicit iterators (all the implicit iterators have been converted
* to explicit iterators when the parse tree was created by tree.c), which
* allows things like this to work correctly:
*
* prop error.a@x[n]/y/z -> error.b@x/y[n]/z -> error.c@x/y/z[n];
*
* during the top level call, the explicit iterator "n" will match an
* instance number in the config database, and the result will be recorded
* in the explicit iterator dictionary and passed down via "infop". so
* when the recursive call tries to match y[n] in the config database, it
* will only match the same instance number as x[n] did since the dictionary
* is consulted to see if "n" took on a value already.
*
* at any point during the recursion, match*() can return to indicate
* a match was not found in the config database and that the caller should
* move on to the next potential match, if any.
*
* constraints are completely ignored by match(), so the statement:
*
* prop error.a@x[n] -> error.b@x[n] {n != 0};
*
* might very well match x[0] if it appears in the config database. it
* is the generate() routine that takes that match and then decides what
* arrow, if any, should be generated in the instance tree. generate()
* looks at the explicit iterator dictionary to get values like "n" in
* the above example so that it can evaluate constraints.
*
*/
static void
{
int epmatches;
struct wildcardinfo *wcp;
G.matched = 1;
if (lnp)
else if (anp)
else {
/* end of vertical match recursion */
for (;;) {
generate_new(); /* new set of arrows */
} else {
break;
}
}
}
return;
}
switch (np->t) {
case T_EVENT: {
epmatches = 0;
/*
* see if we already have a match in the wcps
*/
break;
break;
break;
break;
epmatches++;
}
if (epmatches)
break;
}
/*
* complete names match, can just borrow the fields
*/
return;
}
G.matched = 0;
if (epmatches) {
/*
* just first part of names match - do wildcarding
* by using existing wcp including ewname and also
* copying as much of pwname as is valid, then start
* vmatch_event() at start of non-matching section
*/
}
if (G.matched == 0) {
/*
* This list entry is NULL. Move on to next item
* in the list.
*/
}
return;
}
/*
* names do not match - allocate a new wcp
*/
if (G.matched == 0) {
/*
* This list entry is NULL. Move on to next item in the
* list.
*/
}
break;
}
case T_LIST:
break;
case T_ARROW:
break;
default:
"vmatch: unexpected type: %s",
ptree_nodetype2str(np->t));
}
}
static void
{
} else
}
static void
{
return;
switch (np->t) {
case T_NAME:
break;
case T_LIST:
break;
case T_ARROW:
break;
case T_EVENT:
break;
}
}
/*
* itree_create -- apply the current config to the current parse tree
*
* returns a lut mapping fully-instance-qualified names to struct events.
*
*/
struct lut *
{
extern int alloc_total();
int init_size;
init_size = alloc_total();
continue;
}
}
alloc_total() - init_size);
return (retval);
}
/*
* initial first pass of the rules.
* We don't use the config at all. Just check the last part of the pathname
* in the rules. If this matches the last part of the pathname in the first
* ereport, then set pathname to the pathname in the ereport. If not then
* set pathname to just the last part of pathname with instance number 0.
* Constraints are ignored and all nork values are set to 0. If after all that
* any rules can still not be associated with the ereport, then they are set
* to not needed in prune_propagations() and ignored in the real itree_create()
* which follows.
*/
static struct event *
{
return (ret);
return (ret);
}
/*ARGSUSED*/
struct lut *
{
int gen = 0;
extern int alloc_total();
int init_size;
init_size = alloc_total();
while (arrownp) {
gen++;
} else {
}
while (slst) {
} else {
}
while (dlst) {
} else {
}
sizeof (struct arrow));
gen);
}
}
}
}
alloc_total() - init_size);
}
void
{
int init_size;
init_size = alloc_total();
init_size - alloc_total());
}
void
{
int init_size;
init_size = alloc_total();
init_size - alloc_total());
}
void
{
}
/*ARGSUSED*/
static void
{
struct plut_wlk_data propd;
else
}
/* Print only TO bubbles in this loop */
continue;
}
/* Print only INHIBIT bubbles in this loop */
continue;
}
/* Print only FROM bubbles in this loop */
continue;
}
}
static void
{
struct constraintlist *cp;
else
else
}
return;
}
/* Display anything from the propogation node? */
}
}
}
void
{
}
/*ARGSUSED*/
static void
{
/* Free the properties */
/* Free the payload properties */
if (ep->payloadprops)
/* Free the serd properties */
/* Free my bubbles */
/*
* Free arrows if they are FROM me. Free arrowlists on
* other types of bubbles (but not the attached arrows,
* which will be freed when we free the originating
* bubble.
*/
else
itree_free_arrowlists(bub, 0);
}
}
/*ARGSUSED*/
static void
{
if (ep->keep_in_tree)
return;
/* Free the properties */
/* Free the payload properties */
/* Free the serd properties */
/* Free my bubbles */
}
}
static void
{
}
static struct bubble *
{
/* Use existing bubbles as appropriate when possible */
/* see if an existing "to" bubble works for us */
return (curr); /* matched gen number */
return (curr); /* coalesce K==1 bubbles */
}
/* see if an existing "from" bubble works for us */
return (curr);
}
}
else
return (newb);
}
struct bubble *
{
for (;;) {
else
return (next);
/* bubble was empty, skip it */
}
}
static void
{
}
else
}
static struct arrow *
{
/*
* Set default delays, then try to re-set them from
* any within() constraints.
*/
return (NULL);
}
return (newa);
}
/* returns false if traits show that arrow should not be added after all */
static int
{
/*
* search for the within values first on the declaration of
* the destination event, and then on the prop. this allows
* one to specify a "default" within by putting it on the
* declaration, but then allow overriding on the prop statement.
*/
/*
* handle any global constraints inherited from the
* "fromev" event's declaration
*/
#ifdef notdef
/* XXX not quite ready to evaluate constraints from decls yet */
(void) itree_add_constraint(ap,
#endif /* notdef */
/* handle constraints on the from event in the prop statement */
return (0); /* constraint disallows arrow */
/*
* handle any global constraints inherited from the
* "toev" event's declaration
*/
#ifdef notdef
/* XXX not quite ready to evaluate constraints from decls yet */
(void) itree_add_constraint(ap,
#endif /* notdef */
/* handle constraints on the to event in the prop statement */
return (0); /* constraint disallows arrow */
}
/* if we came up with any deferred constraints, add them to arrow */
}
return (1); /* constraints allow arrow */
}
/*
* Set within() constraint. If the constraint were set multiple times,
* the last one would "win".
*/
static void
{
/* end of expressions list */
return;
switch (xpr->t) {
case T_LIST:
return;
case T_FUNC:
return;
switch (arglist->t) {
case T_TIMEVAL:
break;
case T_NAME:
break;
case T_LIST:
case T_TIMEVAL:
break;
case T_NAME:
break;
default:
}
break;
default:
}
break;
default:
return;
}
}
static void
{
if (arrows_too) {
}
}
}
static void
{
return;
}
return;
}
}
}
static void
{
else
}
}
struct arrowlist *
{
else
return (next);
}
static struct constraintlist *
{
struct constraintlist *curr;
struct constraintlist *newc;
;
else
return (newc);
}
struct constraintlist *
{
struct constraintlist *next;
else
return (next);
}
static void
{
else
}
}
const char *
itree_bubbletype2str(enum bubbletype t)
{
static char buf[100];
switch (t) {
default:
return (buf);
}
}
/*
* itree_fini -- clean up any half-built itrees
*/
void
itree_fini(void)
{
}
}
}