1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 
22 /*
23  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
24  * Use is subject to license terms.
25  *
26  * itree.c -- instance tree creation and manipulation
27  *
28  * this module provides the instance tree
29  */
30 
31 #include <stdio.h>
32 #include <ctype.h>
33 #include <string.h>
34 #include <strings.h>
35 #include "alloc.h"
36 #include "out.h"
37 #include "stable.h"
38 #include "literals.h"
39 #include "lut.h"
40 #include "tree.h"
41 #include "ptree.h"
42 #include "itree.h"
43 #include "ipath.h"
44 #include "iexpr.h"
45 #include "eval.h"
46 #include "config.h"
47 
48 /*
49  * struct info contains the state we keep when expanding a prop statement
50  * as part of constructing the instance tree.  state kept in struct info
51  * is the non-recursive stuff -- the stuff that doesn't need to be on
52  * the stack.  the rest of the state that is passed between all the
53  * mutually recursive functions, is required to be on the stack since
54  * we need to backtrack and recurse as we do the instance tree construction.
55  */
56 struct info {
57 	struct lut *lut;
58 	struct node *anp;	/* arrow np */
59 	struct lut *ex;		/* dictionary of explicit iterators */
60 	struct config *croot;
61 } Ninfo;
62 
63 /*
64  * struct wildcardinfo is used to track wildcarded portions of paths.
65  *
66  * for example, if the epname of an event is "c/d" and the path "a/b/c/d"
67  * exists, the wildcard path ewname is filled in with the path "a/b".  when
68  * matching is done, epname is temporarily replaced with the concatenation
69  * of ewname and epname.
70  *
71  * a linked list of these structs is used to track the expansion of each
72  * event node as it is processed in vmatch() --> vmatch_event() calls.
73  */
74 struct wildcardinfo {
75 	struct node *nptop;		/* event node fed to vmatch */
76 	struct node *oldepname;		/* epname without the wildcard part */
77 	struct node *ewname;		/* wildcard path */
78 	int got_wc_hz;
79 	struct wildcardinfo *next;
80 };
81 
82 static struct wildcardinfo *wcproot = NULL;
83 
84 static void vmatch(struct info *infop, struct node *np, struct node *lnp,
85     struct node *anp);
86 static void hmatch(struct info *infop, struct node *np, struct node *nextnp);
87 static void hmatch_event(struct info *infop, struct node *eventnp,
88     struct node *epname, struct config *ncp, struct node *nextnp, int rematch);
89 static void itree_pbubble(int flags, struct bubble *bp);
90 static void itree_pruner(void *left, void *right, void *arg);
91 static void itree_destructor(void *left, void *right, void *arg);
92 static int itree_set_arrow_traits(struct arrow *ap, struct node *fromev,
93     struct node *toev, struct lut *ex);
94 static void itree_free_arrowlists(struct bubble *bubp, int arrows_too);
95 static void itree_prune_arrowlists(struct bubble *bubp);
96 static void arrow_add_within(struct arrow *ap, struct node *xpr);
97 static struct arrow *itree_add_arrow(struct node *apnode,
98     struct node *fromevent, struct node *toevent, struct lut *ex);
99 static struct event *find_or_add_event(struct info *infop, struct node *np);
100 static void add_arrow(struct bubble *bp, struct arrow *ap);
101 static struct constraintlist *itree_add_constraint(struct arrow *arrowp,
102     struct node *c);
103 static struct bubble *itree_add_bubble(struct event *eventp,
104     enum bubbletype btype, int nork, int gen);
105 static void itree_free_bubble(struct bubble *freeme);
106 static void itree_free_constraints(struct arrow *ap);
107 
108 /*
109  * the following struct contains the state we build up during
110  * vertical and horizontal expansion so that generate()
111  * has everything it needs to construct the appropriate arrows.
112  * after setting up the state by calling:
113  *	generate_arrownp()
114  *	generate_nork()
115  *	generate_new()
116  *	generate_from()
117  *	generate_to()
118  * the actual arrow generation is done by calling:
119  *	generate()
120  */
121 static struct {
122 	int generation;		/* generation number of arrow set */
123 	int matched;		/* number of matches */
124 	struct node *arrownp;	/* top-level parse tree for arrow */
125 	int n;			/* n value associated with arrow */
126 	int k;			/* k value associated with arrow */
127 	struct node *fromnp;	/* left-hand-side event in parse tree */
128 	struct node *tonp;	/* right-hand-side event in parse tree */
129 	struct event *frome;	/* left-hand-side event in instance tree */
130 	struct event *toe;	/* right-hand-side event in instance tree */
131 	struct bubble *frombp;	/* bubble arrow comes from */
132 	struct bubble *tobp;	/* bubble arrow goes to */
133 } G;
134 
135 static void
generate_arrownp(struct node * arrownp)136 generate_arrownp(struct node *arrownp)
137 {
138 	G.arrownp = arrownp;
139 }
140 
141 static void
generate_nork(int n,int k)142 generate_nork(int n, int k)
143 {
144 	G.n = n;
145 	G.k = k;
146 }
147 
148 static void
generate_new(void)149 generate_new(void)
150 {
151 	G.generation++;
152 }
153 
154 static void
generate_from(struct node * fromeventnp)155 generate_from(struct node *fromeventnp)
156 {
157 	G.frombp = NULL;
158 	G.fromnp = fromeventnp;
159 }
160 
161 static void
generate_to(struct node * toeventnp)162 generate_to(struct node *toeventnp)
163 {
164 	G.tonp = toeventnp;
165 }
166 
167 static void
generate(struct info * infop)168 generate(struct info *infop)
169 {
170 	struct arrow *arrowp;
171 
172 	ASSERT(G.arrownp != NULL);
173 	ASSERT(G.fromnp != NULL);
174 	ASSERT(G.tonp != NULL);
175 
176 	out(O_ALTFP|O_VERB3|O_NONL, "        Arrow \"");
177 	ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, G.fromnp);
178 	out(O_ALTFP|O_VERB3|O_NONL, "\" -> \"");
179 	ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, G.tonp);
180 	out(O_ALTFP|O_VERB3|O_NONL, "\" ");
181 
182 	arrowp = itree_add_arrow(G.arrownp, G.fromnp, G.tonp, infop->ex);
183 	if (arrowp == NULL) {
184 		out(O_ALTFP|O_VERB3, "(prevented by constraints)");
185 	} else {
186 		out(O_ALTFP|O_VERB3, "");
187 		if (!G.frombp) {
188 			G.frome = find_or_add_event(infop, G.fromnp);
189 			G.frombp = itree_add_bubble(G.frome, B_FROM, G.n, 0);
190 		}
191 		G.toe = find_or_add_event(infop, G.tonp);
192 		G.tobp = itree_add_bubble(G.toe, B_TO, G.k, G.generation);
193 		arrowp->tail = G.frombp;
194 		arrowp->head = G.tobp;
195 		add_arrow(G.frombp, arrowp);
196 		add_arrow(G.tobp, arrowp);
197 	}
198 }
199 
200 enum childnode_action {
201 	CN_NONE,
202 	CN_DUP
203 };
204 
205 static struct node *
tname_dup(struct node * namep,enum childnode_action act)206 tname_dup(struct node *namep, enum childnode_action act)
207 {
208 	struct node *retp = NULL;
209 	const char *file;
210 	int line;
211 
212 	if (namep == NULL)
213 		return (NULL);
214 
215 	file = namep->file;
216 	line = namep->line;
217 
218 	for (; namep != NULL; namep = namep->u.name.next) {
219 		struct node *newnp = newnode(T_NAME, file, line);
220 
221 		newnp->u.name.t = namep->u.name.t;
222 		newnp->u.name.s = namep->u.name.s;
223 		newnp->u.name.last = newnp;
224 		newnp->u.name.it = namep->u.name.it;
225 		newnp->u.name.cp = namep->u.name.cp;
226 
227 		if (act == CN_DUP) {
228 			struct node *npc;
229 
230 			npc = namep->u.name.child;
231 			if (npc != NULL) {
232 				switch (npc->t) {
233 				case T_NUM:
234 					newnp->u.name.child =
235 					    newnode(T_NUM, file, line);
236 					newnp->u.name.child->u.ull =
237 					    npc->u.ull;
238 					break;
239 				case T_NAME:
240 					newnp->u.name.child =
241 					    tree_name(npc->u.name.s,
242 					    npc->u.name.it, file, line);
243 					break;
244 				default:
245 					out(O_DIE, "tname_dup: "
246 					    "invalid child type %s",
247 					    ptree_nodetype2str(npc->t));
248 				}
249 			}
250 		}
251 
252 		if (retp == NULL) {
253 			retp = newnp;
254 		} else {
255 			retp->u.name.last->u.name.next = newnp;
256 			retp->u.name.last = newnp;
257 		}
258 	}
259 
260 	return (retp);
261 }
262 
263 struct prop_wlk_data {
264 	struct lut *props;
265 	struct node *epname;
266 };
267 
268 static struct lut *props2instance(struct node *, struct node *);
269 
270 /*
271  * let oldepname be a subset of epname.  return the subsection of epname
272  * that ends with oldepname.  make each component in the path explicitly
273  * instanced (i.e., with a T_NUM child).
274  */
275 static struct node *
tname_dup_to_epname(struct node * oldepname,struct node * epname)276 tname_dup_to_epname(struct node *oldepname, struct node *epname)
277 {
278 	struct node *npref, *npend, *np1, *np2;
279 	struct node *ret = NULL;
280 	int foundmatch = 0;
281 
282 	if (epname == NULL)
283 		return (NULL);
284 
285 	/*
286 	 * search for the longest path in epname which contains
287 	 * oldnode->u.event.epname.  set npend to point to just past the
288 	 * end of this path.
289 	 */
290 	npend = NULL;
291 	for (npref = epname; npref; npref = npref->u.name.next) {
292 		if (npref->u.name.s == oldepname->u.name.s) {
293 			for (np1 = npref, np2 = oldepname;
294 			    np1 != NULL && np2 != NULL;
295 			    np1 = np1->u.name.next, np2 = np2->u.name.next) {
296 				if (np1->u.name.s != np2->u.name.s)
297 					break;
298 			}
299 			if (np2 == NULL) {
300 				foundmatch = 1;
301 				npend = np1;
302 				if (np1 == NULL) {
303 					/* oldepname matched npref up to end */
304 					break;
305 				}
306 			}
307 		}
308 	}
309 
310 	if (foundmatch == 0) {
311 		/*
312 		 * if oldepname could not be found in epname, return a
313 		 * duplicate of the former.  do not try to instantize
314 		 * oldepname since it might not be a path.
315 		 */
316 		return (tname_dup(oldepname, CN_DUP));
317 	}
318 
319 	/*
320 	 * dup (epname -- npend).  all children should be T_NUMs.
321 	 */
322 	for (npref = epname;
323 	    ! (npref == NULL || npref == npend);
324 	    npref = npref->u.name.next) {
325 		struct node *newnp = newnode(T_NAME, oldepname->file,
326 		    oldepname->line);
327 
328 		newnp->u.name.t = npref->u.name.t;
329 		newnp->u.name.s = npref->u.name.s;
330 		newnp->u.name.last = newnp;
331 		newnp->u.name.it = npref->u.name.it;
332 		newnp->u.name.cp = npref->u.name.cp;
333 
334 		newnp->u.name.child = newnode(T_NUM, oldepname->file,
335 		    oldepname->line);
336 
337 		if (npref->u.name.child == NULL ||
338 		    npref->u.name.child->t != T_NUM) {
339 			int childnum;
340 
341 			ASSERT(npref->u.name.cp != NULL);
342 			config_getcompname(npref->u.name.cp, NULL, &childnum);
343 			newnp->u.name.child->u.ull = childnum;
344 		} else {
345 			newnp->u.name.child->u.ull =
346 			    npref->u.name.child->u.ull;
347 		}
348 
349 		if (ret == NULL) {
350 			ret = newnp;
351 		} else {
352 			ret->u.name.last->u.name.next = newnp;
353 			ret->u.name.last = newnp;
354 		}
355 	}
356 
357 	return (ret);
358 }
359 
360 /*
361  * restriction: oldnode->u.event.epname has to be equivalent to or a subset
362  * of epname
363  */
364 static struct node *
tevent_dup_to_epname(struct node * oldnode,struct node * epname)365 tevent_dup_to_epname(struct node *oldnode, struct node *epname)
366 {
367 	struct node *ret;
368 
369 	ret = newnode(T_EVENT, oldnode->file, oldnode->line);
370 	ret->u.event.ename = tname_dup(oldnode->u.event.ename, CN_NONE);
371 	ret->u.event.epname = tname_dup_to_epname(oldnode->u.event.epname,
372 	    epname);
373 	return (ret);
374 }
375 
376 static void
nv_instantiate(void * name,void * val,void * arg)377 nv_instantiate(void *name, void *val, void *arg)
378 {
379 	struct prop_wlk_data *pd = (struct prop_wlk_data *)arg;
380 	struct node *orhs = (struct node *)val;
381 	struct node *nrhs;
382 
383 	/* handle engines by instantizing the entire engine */
384 	if (name == L_engine) {
385 		ASSERT(orhs->t == T_EVENT);
386 		ASSERT(orhs->u.event.ename->u.name.t == N_SERD);
387 
388 		/* there are only SERD engines for now */
389 
390 		nrhs = newnode(T_SERD, orhs->file, orhs->line);
391 		nrhs->u.stmt.np = tevent_dup_to_epname(orhs, pd->epname);
392 		nrhs->u.stmt.lutp = props2instance(orhs, pd->epname);
393 		pd->props = lut_add(pd->props, name, nrhs, NULL);
394 		return;
395 	}
396 
397 	switch (orhs->t) {
398 	case T_NUM:
399 		nrhs = newnode(T_NUM, orhs->file, orhs->line);
400 		nrhs->u.ull = orhs->u.ull;
401 		pd->props = lut_add(pd->props, name, nrhs, NULL);
402 		break;
403 	case T_TIMEVAL:
404 		nrhs = newnode(T_TIMEVAL, orhs->file, orhs->line);
405 		nrhs->u.ull = orhs->u.ull;
406 		pd->props = lut_add(pd->props, name, nrhs, NULL);
407 		break;
408 	case T_NAME:
409 		nrhs = tname_dup_to_epname(orhs, pd->epname);
410 		pd->props = lut_add(pd->props, name, nrhs, NULL);
411 		break;
412 	case T_EVENT:
413 		nrhs = tevent_dup_to_epname(orhs, pd->epname);
414 		pd->props = lut_add(pd->props, name, nrhs, NULL);
415 		break;
416 	case T_GLOBID:
417 		nrhs = newnode(T_GLOBID, orhs->file, orhs->line);
418 		nrhs->u.globid.s = orhs->u.globid.s;
419 		pd->props = lut_add(pd->props, name, nrhs, NULL);
420 		break;
421 	case T_FUNC:
422 		/* for T_FUNC, we don't duplicate it, just point to node */
423 		pd->props = lut_add(pd->props, name, orhs, NULL);
424 		break;
425 	default:
426 		out(O_DIE, "unexpected nvpair value type %s",
427 		    ptree_nodetype2str(((struct node *)val)->t));
428 	}
429 }
430 
431 static struct lut *
props2instance(struct node * eventnp,struct node * epname)432 props2instance(struct node *eventnp, struct node *epname)
433 {
434 	struct prop_wlk_data pd;
435 
436 	pd.props = NULL;
437 	pd.epname = epname;
438 
439 	ASSERT(eventnp->u.event.declp != NULL);
440 	lut_walk(eventnp->u.event.declp->u.stmt.lutp, nv_instantiate, &pd);
441 	return (pd.props);
442 }
443 
444 /*ARGSUSED*/
445 static void
instances_destructor(void * left,void * right,void * arg)446 instances_destructor(void *left, void *right, void *arg)
447 {
448 	struct node *dn = (struct node *)right;
449 
450 	if (dn->t == T_SERD) {
451 		/* we allocated the lut during itree_create(), so free it */
452 		lut_free(dn->u.stmt.lutp, instances_destructor, NULL);
453 		dn->u.stmt.lutp = NULL;
454 	}
455 	if (dn->t != T_FUNC)	/* T_FUNC pointed to original node */
456 		tree_free(dn);
457 }
458 
459 /*ARGSUSED*/
460 static void
payloadprops_destructor(void * left,void * right,void * arg)461 payloadprops_destructor(void *left, void *right, void *arg)
462 {
463 	FREE(right);
464 }
465 
466 /*ARGSUSED*/
467 static void
serdprops_destructor(void * left,void * right,void * arg)468 serdprops_destructor(void *left, void *right, void *arg)
469 {
470 	FREE(right);
471 }
472 
473 /*
474  * event_cmp -- used via lut_lookup/lut_add on instance tree lut
475  */
476 static int
event_cmp(struct event * ep1,struct event * ep2)477 event_cmp(struct event *ep1, struct event *ep2)
478 {
479 	int diff;
480 
481 	if ((diff = ep2->enode->u.event.ename->u.name.s -
482 	    ep1->enode->u.event.ename->u.name.s) != 0)
483 		return (diff);
484 	if ((diff = (char *)ep2->ipp - (char *)ep1->ipp) != 0)
485 		return (diff);
486 	return (0);
487 
488 }
489 
490 struct event *
itree_lookup(struct lut * itp,const char * ename,const struct ipath * ipp)491 itree_lookup(struct lut *itp, const char *ename, const struct ipath *ipp)
492 {
493 	struct event searchevent;	/* just used for searching */
494 	struct node searcheventnode;
495 	struct node searchenamenode;
496 
497 	searchevent.enode = &searcheventnode;
498 	searcheventnode.t = T_EVENT;
499 	searcheventnode.u.event.ename = &searchenamenode;
500 	searchenamenode.t = T_NAME;
501 	searchenamenode.u.name.s = ename;
502 	searchevent.ipp = ipp;
503 	return (lut_lookup(itp, (void *)&searchevent, (lut_cmp)event_cmp));
504 }
505 
506 static struct event *
find_or_add_event(struct info * infop,struct node * np)507 find_or_add_event(struct info *infop, struct node *np)
508 {
509 	struct event *ret;
510 	struct event searchevent;	/* just used for searching */
511 
512 	ASSERTeq(np->t, T_EVENT, ptree_nodetype2str);
513 
514 	searchevent.enode = np;
515 	searchevent.ipp = ipath(np->u.event.epname);
516 	if ((ret = lut_lookup(infop->lut, (void *)&searchevent,
517 	    (lut_cmp)event_cmp)) != NULL)
518 		return (ret);
519 
520 	/* wasn't already in tree, allocate it */
521 	ret = alloc_xmalloc(sizeof (*ret));
522 	bzero(ret, sizeof (*ret));
523 
524 	ret->t = np->u.event.ename->u.name.t;
525 	ret->enode = np;
526 	ret->ipp = searchevent.ipp;
527 	ret->props = props2instance(np, np->u.event.epname);
528 
529 	infop->lut = lut_add(infop->lut, (void *)ret, (void *)ret,
530 	    (lut_cmp)event_cmp);
531 
532 	return (ret);
533 }
534 
535 /*
536  * Used for handling expansions where first part of oldepname is a horizontal
537  * expansion. Recurses through entire tree. oldepname argument is always the
538  * full path as in the rules. Once we find a match we go back to using
539  * hmatch_event to handle the rest.
540  */
541 static void
hmatch_full_config(struct info * infop,struct node * eventnp,struct node * oldepname,struct config * ncp,struct node * nextnp,struct iterinfo * iterinfop)542 hmatch_full_config(struct info *infop, struct node *eventnp,
543     struct node *oldepname, struct config *ncp, struct node *nextnp,
544     struct iterinfo *iterinfop)
545 {
546 	char *cp_s;
547 	int cp_num;
548 	struct config *cp;
549 	struct node *saved_ewname;
550 	struct node *saved_epname;
551 	struct config *pcp, *ocp;
552 	struct node *cpnode;
553 	struct node *ewlp, *ewfp;
554 
555 	for (cp = ncp; cp; cp = config_next(cp)) {
556 		config_getcompname(cp, &cp_s, &cp_num);
557 		if (cp_s == oldepname->u.name.s) {
558 			/*
559 			 * Found one.
560 			 */
561 			iterinfop->num = cp_num;
562 
563 			/*
564 			 * Need to set ewname, epname for correct node as is
565 			 * needed by constraint path matching. This code is
566 			 * similar to that in vmatch_event.
567 			 */
568 			saved_ewname = eventnp->u.event.ewname;
569 			saved_epname = eventnp->u.event.epname;
570 			ocp = oldepname->u.name.cp;
571 
572 			/*
573 			 * Find correct ewname by walking back up the config
574 			 * tree adding each name portion as we go.
575 			 */
576 			pcp = config_parent(cp);
577 			eventnp->u.event.ewname = NULL;
578 			for (; pcp != infop->croot; pcp = config_parent(pcp)) {
579 				config_getcompname(pcp, &cp_s, &cp_num);
580 				cpnode = tree_name(cp_s, IT_NONE, NULL, 0);
581 				cpnode->u.name.child = newnode(T_NUM, NULL, 0);
582 				cpnode->u.name.child->u.ull = cp_num;
583 				cpnode->u.name.cp = pcp;
584 				if (eventnp->u.event.ewname != NULL) {
585 					cpnode->u.name.next =
586 					    eventnp->u.event.ewname;
587 					cpnode->u.name.last =
588 					    eventnp->u.event.ewname->
589 					    u.name.last;
590 				}
591 				eventnp->u.event.ewname = cpnode;
592 			}
593 
594 			/*
595 			 * Now create correct epname by duping new ewname
596 			 * and appending oldepname.
597 			 */
598 			ewfp = tname_dup(eventnp->u.event.ewname, CN_DUP);
599 			ewlp = ewfp->u.name.last;
600 			ewfp->u.name.last = oldepname->u.name.last;
601 			ewlp->u.name.next = oldepname;
602 			oldepname->u.name.cp = cp;
603 			eventnp->u.event.epname = ewfp;
604 
605 			outfl(O_ALTFP|O_VERB3|O_NONL, infop->anp->file,
606 			    infop->anp->line, "hmatch_full_config: ");
607 			ptree_name_iter(O_ALTFP|O_VERB3|O_NONL,
608 			    eventnp->u.event.epname);
609 			out(O_ALTFP|O_VERB3, NULL);
610 
611 			/*
612 			 * Now complete hmatch.
613 			 */
614 			hmatch_event(infop, eventnp, oldepname->u.name.next,
615 			    config_child(cp), nextnp, 1);
616 
617 			/*
618 			 * set everything back again
619 			 */
620 			oldepname->u.name.cp = ocp;
621 			iterinfop->num = -1;
622 			ewlp->u.name.next = NULL;
623 			ewfp->u.name.last = ewlp;
624 			tree_free(ewfp);
625 			tree_free(eventnp->u.event.ewname);
626 			eventnp->u.event.ewname = saved_ewname;
627 			eventnp->u.event.epname = saved_epname;
628 		}
629 		/*
630 		 * Try the next level down.
631 		 */
632 		hmatch_full_config(infop, eventnp,
633 		    oldepname, config_child(cp), nextnp, iterinfop);
634 	}
635 }
636 
637 /*
638  * hmatch_event -- perform any appropriate horizontal expansion on an event
639  *
640  * this routine is used to perform horizontal expansion on both the
641  * left-hand-side events in a prop, and the right-hand-side events.
642  * when called to handle a left-side event, nextnp point to the right
643  * side of the prop that should be passed to hmatch() for each match
644  * found by horizontal expansion.   when no horizontal expansion exists,
645  * we will still "match" one event for every event found in the list on
646  * the left-hand-side of the prop because vmatch() already found that
647  * there's at least one match during vertical expansion.
648  */
649 static void
hmatch_event(struct info * infop,struct node * eventnp,struct node * epname,struct config * ncp,struct node * nextnp,int rematch)650 hmatch_event(struct info *infop, struct node *eventnp, struct node *epname,
651     struct config *ncp, struct node *nextnp, int rematch)
652 {
653 	if (epname == NULL) {
654 		/*
655 		 * end of pathname recursion, either we just located
656 		 * a left-hand-side event and we're ready to move on
657 		 * to the expanding the right-hand-side events, or
658 		 * we're further down the recursion and we just located
659 		 * a right-hand-side event.  the passed-in parameter
660 		 * "nextnp" tells us whether we're working on the left
661 		 * side and need to move on to nextnp, or if nextnp is
662 		 * NULL, we're working on the right side.
663 		 */
664 		if (nextnp) {
665 			/*
666 			 * finished a left side expansion, move on to right.
667 			 * tell generate() what event we just matched so
668 			 * it can be used at the source of any arrows
669 			 * we generate as we match events on the right side.
670 			 */
671 			generate_from(eventnp);
672 			hmatch(infop, nextnp, NULL);
673 		} else {
674 			/*
675 			 * finished a right side expansion.  tell generate
676 			 * the information about the destination and let
677 			 * it construct the arrows as appropriate.
678 			 */
679 			generate_to(eventnp);
680 			generate(infop);
681 		}
682 
683 		return;
684 	}
685 
686 	ASSERTeq(epname->t, T_NAME, ptree_nodetype2str);
687 
688 	if (epname->u.name.cp == NULL)
689 		return;
690 
691 	/*
692 	 * we only get here when eventnp already has a completely
693 	 * instanced epname in it already.  so we first recurse
694 	 * down to the end of the name and as the recursion pops
695 	 * up, we look for opportunities to advance horizontal
696 	 * expansions on to the next match.
697 	 */
698 	if (epname->u.name.it == IT_HORIZONTAL || rematch) {
699 		struct config *cp;
700 		struct config *ocp = epname->u.name.cp;
701 		char *cp_s;
702 		int cp_num;
703 		int ocp_num;
704 		struct iterinfo *iterinfop = NULL;
705 		const char *iters;
706 		int hexpand = 0;
707 
708 		if (epname->u.name.it != IT_HORIZONTAL) {
709 			/*
710 			 * Ancestor was horizontal though, so must rematch
711 			 * against the name/num found in vmatch.
712 			 */
713 			config_getcompname(ocp, NULL, &ocp_num);
714 		} else {
715 			iters = epname->u.name.child->u.name.s;
716 			if ((iterinfop = lut_lookup(infop->ex,
717 			    (void *)iters, NULL)) == NULL) {
718 				/*
719 				 * do horizontal expansion on this node
720 				 */
721 				hexpand = 1;
722 				iterinfop = alloc_xmalloc(
723 				    sizeof (struct iterinfo));
724 				iterinfop->num = -1;
725 				iterinfop->np = epname;
726 				infop->ex = lut_add(infop->ex, (void *)iters,
727 				    iterinfop, NULL);
728 			} else if (iterinfop->num == -1) {
729 				hexpand = 1;
730 			} else {
731 				/*
732 				 * This name has already been used in a
733 				 * horizontal expansion. This time just match it
734 				 */
735 				ocp_num = iterinfop->num;
736 			}
737 		}
738 		/*
739 		 * handle case where this is the first section of oldepname
740 		 * and it is horizontally expanded. Instead of just looking for
741 		 * siblings, we want to scan the entire config tree for further
742 		 * matches.
743 		 */
744 		if (epname == eventnp->u.event.oldepname &&
745 		    epname->u.name.it == IT_HORIZONTAL) {
746 			/*
747 			 * Run through config looking for any that match the
748 			 * name.
749 			 */
750 			hmatch_full_config(infop, eventnp, epname,
751 			    infop->croot, nextnp, iterinfop);
752 			return;
753 		}
754 
755 		/*
756 		 * Run through siblings looking for any that match the name.
757 		 * If hexpand not set then num must also match ocp_num.
758 		 */
759 		for (cp = rematch ? ncp : ocp; cp; cp = config_next(cp)) {
760 			config_getcompname(cp, &cp_s, &cp_num);
761 			if (cp_s == epname->u.name.s) {
762 				if (hexpand)
763 					iterinfop->num = cp_num;
764 				else if (ocp_num != cp_num)
765 					continue;
766 				epname->u.name.cp = cp;
767 				hmatch_event(infop, eventnp,
768 				    epname->u.name.next, config_child(cp),
769 				    nextnp, 1);
770 			}
771 		}
772 		epname->u.name.cp = ocp;
773 		if (hexpand)
774 			iterinfop->num = -1;
775 	} else {
776 		hmatch_event(infop, eventnp, epname->u.name.next,
777 		    NULL, nextnp, 0);
778 	}
779 }
780 
781 /*
782  * hmatch -- check for horizontal expansion matches
783  *
784  * np points to the things we're matching (like a T_LIST or a T_EVENT)
785  * and if we're working on a left-side of a prop, nextnp points to
786  * the other side of the prop that we'll tackle next when this recursion
787  * bottoms out.  when all the events in the entire prop arrow have been
788  * horizontally expanded, generate() will be called to generate the
789  * actualy arrow.
790  */
791 static void
hmatch(struct info * infop,struct node * np,struct node * nextnp)792 hmatch(struct info *infop, struct node *np, struct node *nextnp)
793 {
794 	if (np == NULL)
795 		return;		/* all done */
796 
797 	/*
798 	 * for each item in the list of events (which could just
799 	 * be a single event, or it could get larger in the loop
800 	 * below due to horizontal expansion), call hmatch on
801 	 * the right side and create arrows to each element.
802 	 */
803 
804 	switch (np->t) {
805 	case T_LIST:
806 		/* loop through the list */
807 		if (np->u.expr.left)
808 			hmatch(infop, np->u.expr.left, nextnp);
809 		if (np->u.expr.right)
810 			hmatch(infop, np->u.expr.right, nextnp);
811 		break;
812 
813 	case T_EVENT:
814 		hmatch_event(infop, np, np->u.event.epname,
815 		    NULL, nextnp, 0);
816 		break;
817 
818 	default:
819 		outfl(O_DIE, np->file, np->line,
820 		    "hmatch: unexpected type: %s",
821 		    ptree_nodetype2str(np->t));
822 	}
823 }
824 
825 static int
itree_np2nork(struct node * norknp)826 itree_np2nork(struct node *norknp)
827 {
828 	if (norknp == NULL)
829 		return (1);
830 	else if (norknp->t == T_NAME && norknp->u.name.s == L_A)
831 		return (-1);	/* our internal version of "all" */
832 	else if (norknp->t == T_NUM)
833 		return ((int)norknp->u.ull);
834 	else
835 		outfl(O_DIE, norknp->file, norknp->line,
836 		    "itree_np2nork: internal error type %s",
837 		    ptree_nodetype2str(norknp->t));
838 	/*NOTREACHED*/
839 	return (1);
840 }
841 
842 static struct iterinfo *
newiterinfo(int num,struct node * np)843 newiterinfo(int num, struct node *np)
844 {
845 	struct iterinfo *ret = alloc_xmalloc(sizeof (*ret));
846 
847 	ret->num = num;
848 	ret->np = np;
849 	return (ret);
850 }
851 
852 /*ARGSUSED*/
853 static void
iterinfo_destructor(void * left,void * right,void * arg)854 iterinfo_destructor(void *left, void *right, void *arg)
855 {
856 	struct iterinfo *iterinfop = (struct iterinfo *)right;
857 
858 	alloc_xfree(iterinfop, sizeof (*iterinfop));
859 }
860 
861 static void
vmatch_event(struct info * infop,struct config * cp,struct node * np,struct node * lnp,struct node * anp,struct wildcardinfo * wcp)862 vmatch_event(struct info *infop, struct config *cp, struct node *np,
863 	    struct node *lnp, struct node *anp, struct wildcardinfo *wcp)
864 {
865 	char *cp_s;
866 	int cp_num;
867 	struct node *ewlp, *ewfp;
868 	struct config *pcp;
869 	struct node *cpnode;
870 	int newewname = 0;
871 
872 	/*
873 	 * handle case where the first section of the path name is horizontally
874 	 * expanded. The whole expansion is handled by hmatch on the first
875 	 * match here - so we just skip any subsequent matches here.
876 	 */
877 	if (wcp->got_wc_hz == 1)
878 		return;
879 
880 	if (np == NULL) {
881 		/*
882 		 * Reached the end of the name. u.name.cp pointers should be set
883 		 * up for each part of name. From this we can use config tree
884 		 * to build up the wildcard part of the name (if any).
885 		 */
886 		pcp = config_parent(wcp->nptop->u.event.epname->u.name.cp);
887 		if (pcp == infop->croot) {
888 			/*
889 			 * no wildcarding done - move on to next entry
890 			 */
891 			wcp->nptop->u.event.ewname = wcp->ewname;
892 			wcp->nptop->u.event.oldepname = wcp->oldepname;
893 			vmatch(infop, np, lnp, anp);
894 			wcp->got_wc_hz = 0;
895 			return;
896 		}
897 		if (wcp->ewname == NULL) {
898 			/*
899 			 * ewname not yet set up - do it now
900 			 */
901 			newewname = 1;
902 			for (; pcp != infop->croot; pcp = config_parent(pcp)) {
903 				config_getcompname(pcp, &cp_s, &cp_num);
904 				cpnode = tree_name(cp_s, IT_NONE, NULL, 0);
905 				cpnode->u.name.child = newnode(T_NUM, NULL, 0);
906 				cpnode->u.name.child->u.ull = cp_num;
907 				cpnode->u.name.cp = pcp;
908 				if (wcp->ewname != NULL) {
909 					cpnode->u.name.next = wcp->ewname;
910 					cpnode->u.name.last =
911 					    wcp->ewname->u.name.last;
912 				}
913 				wcp->ewname = cpnode;
914 			}
915 		}
916 
917 		/*
918 		 * dup ewname and append oldepname
919 		 */
920 		ewfp = tname_dup(wcp->ewname, CN_DUP);
921 		ewlp = ewfp->u.name.last;
922 		ewfp->u.name.last = wcp->oldepname->u.name.last;
923 		ewlp->u.name.next = wcp->oldepname;
924 
925 		wcp->nptop->u.event.epname = ewfp;
926 		wcp->nptop->u.event.ewname = wcp->ewname;
927 		wcp->nptop->u.event.oldepname = wcp->oldepname;
928 		vmatch(infop, np, lnp, anp);
929 		wcp->got_wc_hz = 0;
930 		wcp->nptop->u.event.epname = wcp->oldepname;
931 
932 		/*
933 		 * reduce duped ewname to original then free
934 		 */
935 		ewlp->u.name.next = NULL;
936 		ewfp->u.name.last = ewlp;
937 		tree_free(ewfp);
938 
939 		if (newewname) {
940 			/*
941 			 * free ewname if allocated above
942 			 */
943 			tree_free(wcp->ewname);
944 			wcp->ewname = NULL;
945 		}
946 		return;
947 	}
948 
949 	/*
950 	 * We have an np. See if we can match it in this section of
951 	 * the config tree.
952 	 */
953 	if (cp == NULL)
954 		return;	/* no more config to match against */
955 
956 	for (; cp; cp = config_next(cp)) {
957 		config_getcompname(cp, &cp_s, &cp_num);
958 
959 		if (cp_s == np->u.name.s) {
960 			/* found a matching component name */
961 			if (np->u.name.child &&
962 			    np->u.name.child->t == T_NUM) {
963 				/*
964 				 * an explicit instance number was given
965 				 * in the source.  so only consider this
966 				 * a configuration match if the number
967 				 * also matches.
968 				 */
969 				if (cp_num != np->u.name.child->u.ull)
970 					continue;
971 
972 			} else if (np->u.name.it != IT_HORIZONTAL) {
973 				struct iterinfo *iterinfop;
974 				const char *iters;
975 
976 				/*
977 				 * vertical iterator.  look it up in
978 				 * the appropriate lut and if we get
979 				 * back a value it is either one that we
980 				 * set earlier, in which case we record
981 				 * the new value for this iteration and
982 				 * keep matching, or it is one that was
983 				 * set by an earlier reference to the
984 				 * iterator, in which case we only consider
985 				 * this a configuration match if the number
986 				 * matches cp_num.
987 				 */
988 
989 				ASSERT(np->u.name.child != NULL);
990 				ASSERT(np->u.name.child->t == T_NAME);
991 				iters = np->u.name.child->u.name.s;
992 
993 				if ((iterinfop = lut_lookup(infop->ex,
994 				    (void *)iters, NULL)) == NULL) {
995 					/* we're the first use, record our np */
996 					infop->ex = lut_add(infop->ex,
997 					    (void *)iters,
998 					    newiterinfo(cp_num, np), NULL);
999 				} else if (np == iterinfop->np) {
1000 					/*
1001 					 * we're the first use, back again
1002 					 * for another iteration.  so update
1003 					 * the num bound to this iterator in
1004 					 * the lut.
1005 					 */
1006 					iterinfop->num = cp_num;
1007 				} else if (cp_num != iterinfop->num) {
1008 					/*
1009 					 * an earlier reference to this
1010 					 * iterator bound it to a different
1011 					 * instance number, so there's no
1012 					 * match here after all.
1013 					 *
1014 					 * however, it's possible that this
1015 					 * component should really be part of
1016 					 * the wildcard.  we explore this by
1017 					 * forcing this component into the
1018 					 * wildcarded section.
1019 					 *
1020 					 * for an more details of what's
1021 					 * going to happen now, see
1022 					 * comments block below entitled
1023 					 * "forcing components into
1024 					 * wildcard path".
1025 					 */
1026 					if (np == wcp->nptop->u.event.epname)
1027 						vmatch_event(infop,
1028 						    config_child(cp), np, lnp,
1029 						    anp, wcp);
1030 					continue;
1031 				}
1032 			}
1033 
1034 			/*
1035 			 * if this was an IT_HORIZONTAL name, hmatch() will
1036 			 * expand all matches horizontally into a list.
1037 			 * we know the list will contain at least
1038 			 * one element (the one we just matched),
1039 			 * so we just let hmatch_event() do the rest.
1040 			 *
1041 			 * recurse on to next component. Note that
1042 			 * wildcarding is now turned off.
1043 			 */
1044 			np->u.name.cp = cp;
1045 			vmatch_event(infop, config_child(cp), np->u.name.next,
1046 			    lnp, anp, wcp);
1047 			np->u.name.cp = NULL;
1048 
1049 			/*
1050 			 * handle case where this is the first section of the
1051 			 * path name and it is horizontally expanded.
1052 			 * In this case we want all matching nodes in the config
1053 			 * to be expanded horizontally - so set got_wc_hz and
1054 			 * leave all further processing to hmatch.
1055 			 */
1056 			if (G.matched && np == wcp->nptop->u.event.epname &&
1057 			    np->u.name.it == IT_HORIZONTAL)
1058 				wcp->got_wc_hz = 1;
1059 
1060 			/*
1061 			 * forcing components into wildcard path:
1062 			 *
1063 			 * if this component is the first match, force it
1064 			 * to be part of the wildcarded path and see if we
1065 			 * can get additional matches.
1066 			 *
1067 			 * here's an example.  suppose we have the
1068 			 * definition
1069 			 *	event foo@x/y
1070 			 * and configuration
1071 			 *	a0/x0/y0/a1/x1/y1
1072 			 *
1073 			 * the code up to this point will treat "a0" as the
1074 			 * wildcarded part of the path and "x0/y0" as the
1075 			 * nonwildcarded part, resulting in the instanced
1076 			 * event
1077 			 *	foo@a0/x0/y0
1078 			 *
1079 			 * in order to discover the next match (.../x1/y1)
1080 			 * in the configuration we have to force "x0" into
1081 			 * the wildcarded part of the path.
1082 			 * by doing so, we discover the wildcarded part
1083 			 * "a0/x0/y0/a1" and the nonwildcarded part "x1/y1"
1084 			 *
1085 			 * the following call to vmatch_event() is also
1086 			 * needed to properly handle the configuration
1087 			 *	b0/x0/b1/x1/y1
1088 			 *
1089 			 * the recursions into vmatch_event() will start
1090 			 * off uncovering "b0" as the wildcarded part and
1091 			 * "x0" as the start of the nonwildcarded path.
1092 			 * however, the next recursion will not result in a
1093 			 * match since there is no "y" following "x0".  the
1094 			 * subsequent match of (wildcard = "b0/x0/b1" and
1095 			 * nonwildcard = "x1/y1") will be discovered only
1096 			 * if "x0" is forced to be a part of the wildcarded
1097 			 * path.
1098 			 */
1099 			if (np == wcp->nptop->u.event.epname)
1100 				vmatch_event(infop, config_child(cp), np, lnp,
1101 				    anp, wcp);
1102 
1103 			if (np->u.name.it == IT_HORIZONTAL) {
1104 				/*
1105 				 * hmatch() finished iterating through
1106 				 * the configuration as described above, so
1107 				 * don't continue iterating here.
1108 				 */
1109 				return;
1110 			}
1111 		} else if (np == wcp->nptop->u.event.epname) {
1112 			/*
1113 			 * no match - carry on down the tree looking for
1114 			 * wildcarding
1115 			 */
1116 			vmatch_event(infop, config_child(cp), np, lnp, anp,
1117 			    wcp);
1118 		}
1119 	}
1120 }
1121 
1122 /*
1123  * vmatch -- find the next vertical expansion match in the config database
1124  *
1125  * this routine is called with three node pointers:
1126  *	 np -- the parse we're matching
1127  *	lnp -- the rest of the list we're currently working on
1128  *	anp -- the rest of the arrow we're currently working on
1129  *
1130  * the expansion matching happens via three types of recursion:
1131  *
1132  *	- when given an arrow, handle the left-side and then recursively
1133  *	  handle the right side (which might be another cascaded arrow).
1134  *
1135  *	- when handling one side of an arrow, recurse through the T_LIST
1136  *	  to get to each event (or just move on to the event if there
1137  *	  is a single event instead of a list)  since the arrow parse
1138  *	  trees recurse left, we actually start with the right-most
1139  *	  event list in the prop statement and work our way towards
1140  *	  the left-most event list.
1141  *
1142  *	- when handling an event, recurse down each component of the
1143  *	  pathname, matching in the config database and recording the
1144  *	  matches in the explicit iterator dictionary as we go.
1145  *
1146  * when the bottom of this matching recursion is met, meaning we have
1147  * set the "cp" pointers on all the names in the entire statement,
1148  * we call hmatch() which does it's own recursion to handle horizontal
1149  * expandsion and then call generate() to generate nodes, bubbles, and
1150  * arrows in the instance tree.  generate() looks at the cp pointers to
1151  * see what instance numbers were matched in the configuration database.
1152  *
1153  * when horizontal expansion appears, vmatch() finds only the first match
1154  * and hmatch() then takes the horizontal expansion through all the other
1155  * matches when generating the arrows in the instance tree.
1156  *
1157  * the "infop" passed down through the recursion contains a dictionary
1158  * of the explicit iterators (all the implicit iterators have been converted
1159  * to explicit iterators when the parse tree was created by tree.c), which
1160  * allows things like this to work correctly:
1161  *
1162  *	prop error.a@x[n]/y/z -> error.b@x/y[n]/z -> error.c@x/y/z[n];
1163  *
1164  * during the top level call, the explicit iterator "n" will match an
1165  * instance number in the config database, and the result will be recorded
1166  * in the explicit iterator dictionary and passed down via "infop".  so
1167  * when the recursive call tries to match y[n] in the config database, it
1168  * will only match the same instance number as x[n] did since the dictionary
1169  * is consulted to see if "n" took on a value already.
1170  *
1171  * at any point during the recursion, match*() can return to indicate
1172  * a match was not found in the config database and that the caller should
1173  * move on to the next potential match, if any.
1174  *
1175  * constraints are completely ignored by match(), so the statement:
1176  *
1177  *	prop error.a@x[n] -> error.b@x[n] {n != 0};
1178  *
1179  * might very well match x[0] if it appears in the config database.  it
1180  * is the generate() routine that takes that match and then decides what
1181  * arrow, if any, should be generated in the instance tree.  generate()
1182  * looks at the explicit iterator dictionary to get values like "n" in
1183  * the above example so that it can evaluate constraints.
1184  *
1185  */
1186 static void
vmatch(struct info * infop,struct node * np,struct node * lnp,struct node * anp)1187 vmatch(struct info *infop, struct node *np, struct node *lnp, struct node *anp)
1188 {
1189 	struct node *np1, *np2, *oldepname, *oldnptop;
1190 	int epmatches;
1191 	struct config *cp;
1192 	struct wildcardinfo *wcp;
1193 
1194 	if (np == NULL) {
1195 		G.matched = 1;
1196 		if (lnp)
1197 			vmatch(infop, lnp, NULL, anp);
1198 		else if (anp)
1199 			vmatch(infop, anp, NULL, NULL);
1200 		else {
1201 			struct node *src;
1202 			struct node *dst;
1203 
1204 			/* end of vertical match recursion */
1205 			outfl(O_ALTFP|O_VERB3|O_NONL,
1206 			    infop->anp->file, infop->anp->line, "vmatch: ");
1207 			ptree_name_iter(O_ALTFP|O_VERB3|O_NONL, infop->anp);
1208 			out(O_ALTFP|O_VERB3, NULL);
1209 
1210 			generate_nork(
1211 			    itree_np2nork(infop->anp->u.arrow.nnp),
1212 			    itree_np2nork(infop->anp->u.arrow.knp));
1213 			dst = infop->anp->u.arrow.rhs;
1214 			src = infop->anp->u.arrow.lhs;
1215 			for (;;) {
1216 				generate_new();	/* new set of arrows */
1217 				if (src->t == T_ARROW) {
1218 					hmatch(infop, src->u.arrow.rhs, dst);
1219 					generate_nork(
1220 					    itree_np2nork(src->u.arrow.nnp),
1221 					    itree_np2nork(src->u.arrow.knp));
1222 					dst = src->u.arrow.rhs;
1223 					src = src->u.arrow.lhs;
1224 				} else {
1225 					hmatch(infop, src, dst);
1226 					break;
1227 				}
1228 			}
1229 		}
1230 		return;
1231 	}
1232 
1233 	switch (np->t) {
1234 	case T_EVENT: {
1235 		epmatches = 0;
1236 		/*
1237 		 * see if we already have a match in the wcps
1238 		 */
1239 		for (wcp = wcproot; wcp; wcp = wcp->next) {
1240 			oldepname = wcp->oldepname;
1241 			oldnptop = wcp->nptop;
1242 			for (np1 = oldepname, np2 = np->u.event.epname;
1243 			    np1 != NULL && np2 != NULL; np1 = np1->u.name.next,
1244 			    np2 = np2->u.name.next) {
1245 				if (strcmp(np1->u.name.s, np2->u.name.s) != 0)
1246 					break;
1247 				if (np1->u.name.child->t !=
1248 				    np2->u.name.child->t)
1249 					break;
1250 				if (np1->u.name.child->t == T_NUM &&
1251 				    np1->u.name.child->u.ull !=
1252 				    np2->u.name.child->u.ull)
1253 					break;
1254 				if (np1->u.name.child->t == T_NAME &&
1255 				    strcmp(np1->u.name.child->u.name.s,
1256 				    np2->u.name.child->u.name.s) != 0)
1257 					break;
1258 				epmatches++;
1259 			}
1260 			if (epmatches)
1261 				break;
1262 		}
1263 		if (epmatches && np1 == NULL && np2 == NULL) {
1264 			/*
1265 			 * complete names match, can just borrow the fields
1266 			 */
1267 			oldepname = np->u.event.epname;
1268 			np->u.event.epname = oldnptop->u.event.epname;
1269 			np->u.event.oldepname = wcp->oldepname;
1270 			np->u.event.ewname = wcp->ewname;
1271 			vmatch(infop, NULL, lnp, anp);
1272 			np->u.event.epname = oldepname;
1273 			return;
1274 		}
1275 		G.matched = 0;
1276 		if (epmatches) {
1277 			/*
1278 			 * just first part of names match - do wildcarding
1279 			 * by using existing wcp including ewname and also
1280 			 * copying as much of pwname as is valid, then start
1281 			 * vmatch_event() at start of non-matching section
1282 			 */
1283 			for (np1 = oldepname, np2 = np->u.event.epname;
1284 			    epmatches != 0; epmatches--) {
1285 				cp = np1->u.name.cp;
1286 				np2->u.name.cp = cp;
1287 				np1 = np1->u.name.next;
1288 				np2 = np2->u.name.next;
1289 			}
1290 			wcp->oldepname = np->u.event.epname;
1291 			wcp->nptop = np;
1292 			vmatch_event(infop, config_child(cp), np2, lnp,
1293 			    anp, wcp);
1294 			wcp->oldepname = oldepname;
1295 			wcp->nptop = oldnptop;
1296 			if (G.matched == 0) {
1297 				/*
1298 				 * This list entry is NULL. Move on to next item
1299 				 * in the list.
1300 				 */
1301 				vmatch(infop, NULL, lnp, anp);
1302 			}
1303 			return;
1304 		}
1305 		/*
1306 		 * names do not match - allocate a new wcp
1307 		 */
1308 		wcp = MALLOC(sizeof (struct wildcardinfo));
1309 		wcp->next = wcproot;
1310 		wcproot = wcp;
1311 		wcp->nptop = np;
1312 		wcp->oldepname = np->u.event.epname;
1313 		wcp->ewname = NULL;
1314 		wcp->got_wc_hz = 0;
1315 
1316 		vmatch_event(infop, config_child(infop->croot),
1317 		    np->u.event.epname, lnp, anp, wcp);
1318 
1319 		wcproot = wcp->next;
1320 		FREE(wcp);
1321 		if (G.matched == 0) {
1322 			/*
1323 			 * This list entry is NULL. Move on to next item in the
1324 			 * list.
1325 			 */
1326 			vmatch(infop, NULL, lnp, anp);
1327 		}
1328 		break;
1329 	}
1330 	case T_LIST:
1331 		ASSERT(lnp == NULL);
1332 		vmatch(infop, np->u.expr.right, np->u.expr.left, anp);
1333 		break;
1334 
1335 	case T_ARROW:
1336 		ASSERT(lnp == NULL && anp == NULL);
1337 		vmatch(infop, np->u.arrow.rhs, NULL, np->u.arrow.parent);
1338 		break;
1339 
1340 	default:
1341 		outfl(O_DIE, np->file, np->line,
1342 		    "vmatch: unexpected type: %s",
1343 		    ptree_nodetype2str(np->t));
1344 	}
1345 }
1346 
1347 static void
find_first_arrow(struct info * infop,struct node * anp)1348 find_first_arrow(struct info *infop, struct node *anp)
1349 {
1350 	if (anp->u.arrow.lhs->t == T_ARROW) {
1351 		anp->u.arrow.lhs->u.arrow.parent = anp;
1352 		find_first_arrow(infop, anp->u.arrow.lhs);
1353 	} else
1354 		vmatch(infop, anp->u.arrow.lhs, NULL, anp);
1355 }
1356 
1357 static void
cp_reset(struct node * np)1358 cp_reset(struct node *np)
1359 {
1360 	if (np == NULL)
1361 		return;
1362 	switch (np->t) {
1363 	case T_NAME:
1364 		np->u.name.cp = NULL;
1365 		cp_reset(np->u.name.next);
1366 		break;
1367 
1368 	case T_LIST:
1369 		cp_reset(np->u.expr.left);
1370 		cp_reset(np->u.expr.right);
1371 		break;
1372 
1373 	case T_ARROW:
1374 		cp_reset(np->u.arrow.lhs);
1375 		cp_reset(np->u.arrow.rhs);
1376 		break;
1377 
1378 	case T_EVENT:
1379 		cp_reset(np->u.event.epname);
1380 		break;
1381 	}
1382 }
1383 
1384 /*
1385  * itree_create -- apply the current config to the current parse tree
1386  *
1387  * returns a lut mapping fully-instance-qualified names to struct events.
1388  *
1389  */
1390 struct lut *
itree_create(struct config * croot)1391 itree_create(struct config *croot)
1392 {
1393 	struct lut *retval;
1394 	struct node *propnp;
1395 	extern int alloc_total();
1396 	int init_size;
1397 
1398 	Ninfo.lut = NULL;
1399 	Ninfo.croot = croot;
1400 	init_size = alloc_total();
1401 	out(O_ALTFP|O_STAMP, "start itree_create using %d bytes", init_size);
1402 	for (propnp = Props; propnp; propnp = propnp->u.stmt.next) {
1403 		struct node *anp = propnp->u.stmt.np;
1404 
1405 		ASSERTeq(anp->t, T_ARROW, ptree_nodetype2str);
1406 
1407 		if (!anp->u.arrow.needed)
1408 			continue;
1409 		Ninfo.anp = anp;
1410 		Ninfo.ex = NULL;
1411 
1412 		generate_arrownp(anp);
1413 		anp->u.arrow.parent = NULL;
1414 		find_first_arrow(&Ninfo, anp);
1415 
1416 		if (Ninfo.ex) {
1417 			lut_free(Ninfo.ex, iterinfo_destructor, NULL);
1418 			Ninfo.ex = NULL;
1419 		}
1420 		cp_reset(anp);
1421 	}
1422 
1423 	out(O_ALTFP|O_STAMP, "itree_create added %d bytes",
1424 	    alloc_total() - init_size);
1425 	retval = Ninfo.lut;
1426 	Ninfo.lut = NULL;
1427 	return (retval);
1428 }
1429 
1430 /*
1431  * initial first pass of the rules.
1432  * We don't use the config at all. Just check the last part of the pathname
1433  * in the rules. If this matches the last part of the pathname in the first
1434  * ereport, then set pathname to the pathname in the ereport. If not then
1435  * set pathname to just the last part of pathname with instance number 0.
1436  * Constraints are ignored and all nork values are set to 0. If after all that
1437  * any rules can still not be associated with the ereport, then they are set
1438  * to not needed in prune_propagations() and ignored in the real itree_create()
1439  * which follows.
1440  */
1441 
1442 static struct event *
add_event_dummy(struct node * np,const struct ipath * ipp)1443 add_event_dummy(struct node *np, const struct ipath *ipp)
1444 {
1445 	struct event *ret;
1446 	struct event searchevent;	/* just used for searching */
1447 	extern struct ipath *ipath_dummy(struct node *, struct ipath *);
1448 	struct ipath *ipp_un;
1449 	extern struct ipath *ipath_for_usednames(struct node *);
1450 
1451 	searchevent.enode = np;
1452 	searchevent.ipp = ipath_dummy(np->u.event.epname, (struct ipath *)ipp);
1453 	ipp_un = ipath_for_usednames(np->u.event.epname);
1454 	if ((ret = lut_lookup(Ninfo.lut, (void *)&searchevent,
1455 	    (lut_cmp)event_cmp)) != NULL)
1456 		return (ret);
1457 
1458 	ret = alloc_xmalloc(sizeof (*ret));
1459 	bzero(ret, sizeof (*ret));
1460 	ret->t = np->u.event.ename->u.name.t;
1461 	ret->enode = np;
1462 	ret->ipp = searchevent.ipp;
1463 	ret->ipp_un = ipp_un;
1464 	Ninfo.lut = lut_add(Ninfo.lut, (void *)ret, (void *)ret,
1465 	    (lut_cmp)event_cmp);
1466 	return (ret);
1467 }
1468 
1469 /*ARGSUSED*/
1470 struct lut *
itree_create_dummy(const char * e0class,const struct ipath * e0ipp)1471 itree_create_dummy(const char *e0class, const struct ipath *e0ipp)
1472 {
1473 	struct node *propnp;
1474 	struct event *frome, *toe;
1475 	struct bubble *frombp, *tobp;
1476 	struct arrow *arrowp;
1477 	struct node *src, *dst, *slst, *dlst, *arrownp, *oldarrownp;
1478 	int gen = 0;
1479 	extern int alloc_total();
1480 	int init_size;
1481 
1482 	Ninfo.lut = NULL;
1483 	init_size = alloc_total();
1484 	out(O_ALTFP|O_STAMP, "start itree_create using %d bytes", init_size);
1485 	for (propnp = Props; propnp; propnp = propnp->u.stmt.next) {
1486 		arrownp = propnp->u.stmt.np;
1487 		while (arrownp) {
1488 			gen++;
1489 			dlst = arrownp->u.arrow.rhs;
1490 			slst = arrownp->u.arrow.lhs;
1491 			oldarrownp = arrownp;
1492 			if (slst->t == T_ARROW) {
1493 				arrownp = slst;
1494 				slst = slst->u.arrow.rhs;
1495 			} else {
1496 				arrownp = NULL;
1497 			}
1498 			while (slst) {
1499 				if (slst->t == T_LIST) {
1500 					src = slst->u.expr.right;
1501 					slst = slst->u.expr.left;
1502 				} else {
1503 					src = slst;
1504 					slst = NULL;
1505 				}
1506 				frome = add_event_dummy(src, e0ipp);
1507 				frombp = itree_add_bubble(frome, B_FROM, 0, 0);
1508 				while (dlst) {
1509 					if (dlst->t == T_LIST) {
1510 						dst = dlst->u.expr.right;
1511 						dlst = dlst->u.expr.left;
1512 					} else {
1513 						dst = dlst;
1514 						dlst = NULL;
1515 					}
1516 					arrowp = alloc_xmalloc(
1517 					    sizeof (struct arrow));
1518 					bzero(arrowp, sizeof (struct arrow));
1519 					arrowp->pnode = oldarrownp;
1520 					toe = add_event_dummy(dst, e0ipp);
1521 					tobp = itree_add_bubble(toe, B_TO, 0,
1522 					    gen);
1523 					arrowp->tail = frombp;
1524 					arrowp->head = tobp;
1525 					add_arrow(frombp, arrowp);
1526 					add_arrow(tobp, arrowp);
1527 					arrow_add_within(arrowp,
1528 					    dst->u.event.declp->u.stmt.np->
1529 					    u.event.eexprlist);
1530 					arrow_add_within(arrowp,
1531 					    dst->u.event.eexprlist);
1532 				}
1533 			}
1534 		}
1535 	}
1536 	out(O_ALTFP|O_STAMP, "itree_create added %d bytes",
1537 	    alloc_total() - init_size);
1538 	return (Ninfo.lut);
1539 }
1540 
1541 void
itree_free(struct lut * lutp)1542 itree_free(struct lut *lutp)
1543 {
1544 	int init_size;
1545 
1546 	init_size = alloc_total();
1547 	out(O_ALTFP|O_STAMP, "start itree_free");
1548 	lut_free(lutp, itree_destructor, NULL);
1549 	out(O_ALTFP|O_STAMP, "itree_free freed %d bytes",
1550 	    init_size - alloc_total());
1551 }
1552 
1553 void
itree_prune(struct lut * lutp)1554 itree_prune(struct lut *lutp)
1555 {
1556 	int init_size;
1557 
1558 	init_size = alloc_total();
1559 	out(O_ALTFP|O_STAMP, "start itree_prune");
1560 	lut_walk(lutp, itree_pruner, NULL);
1561 	out(O_ALTFP|O_STAMP, "itree_prune freed %d bytes",
1562 	    init_size - alloc_total());
1563 }
1564 
1565 void
itree_pevent_brief(int flags,struct event * ep)1566 itree_pevent_brief(int flags, struct event *ep)
1567 {
1568 	ASSERT(ep != NULL);
1569 	ASSERT(ep->enode != NULL);
1570 	ASSERT(ep->ipp != NULL);
1571 
1572 	ipath_print(flags, ep->enode->u.event.ename->u.name.s, ep->ipp);
1573 }
1574 
1575 /*ARGSUSED*/
1576 static void
itree_pevent(struct event * lhs,struct event * ep,void * arg)1577 itree_pevent(struct event *lhs, struct event *ep, void *arg)
1578 {
1579 	struct plut_wlk_data propd;
1580 	struct bubble *bp;
1581 	int flags = (int)(intptr_t)arg;
1582 
1583 	itree_pevent_brief(flags, ep);
1584 	if (ep->t == N_EREPORT)
1585 		out(flags, " (count %d)", ep->count);
1586 	else
1587 		out(flags, NULL);
1588 
1589 	if (ep->props) {
1590 		propd.flags = flags;
1591 		propd.first = 1;
1592 		out(flags, "Properties:");
1593 		lut_walk(ep->props, ptree_plut, (void *)&propd);
1594 	}
1595 
1596 	for (bp = itree_next_bubble(ep, NULL); bp;
1597 	    bp = itree_next_bubble(ep, bp)) {
1598 		/* Print only TO bubbles in this loop */
1599 		if (bp->t != B_TO)
1600 			continue;
1601 		itree_pbubble(flags, bp);
1602 	}
1603 
1604 	for (bp = itree_next_bubble(ep, NULL); bp;
1605 	    bp = itree_next_bubble(ep, bp)) {
1606 		/* Print only INHIBIT bubbles in this loop */
1607 		if (bp->t != B_INHIBIT)
1608 			continue;
1609 		itree_pbubble(flags, bp);
1610 	}
1611 
1612 	for (bp = itree_next_bubble(ep, NULL); bp;
1613 	    bp = itree_next_bubble(ep, bp)) {
1614 		/* Print only FROM bubbles in this loop */
1615 		if (bp->t != B_FROM)
1616 			continue;
1617 		itree_pbubble(flags, bp);
1618 	}
1619 }
1620 
1621 static void
itree_pbubble(int flags,struct bubble * bp)1622 itree_pbubble(int flags, struct bubble *bp)
1623 {
1624 	struct constraintlist *cp;
1625 	struct arrowlist *ap;
1626 
1627 	ASSERT(bp != NULL);
1628 
1629 	out(flags|O_NONL, "   ");
1630 	if (bp->mark)
1631 		out(flags|O_NONL, "*");
1632 	else
1633 		out(flags|O_NONL, " ");
1634 	if (bp->t == B_FROM)
1635 		out(flags|O_NONL, "N=%d to:", bp->nork);
1636 	else if (bp->t == B_TO)
1637 		out(flags|O_NONL, "K=%d from:", bp->nork);
1638 	else
1639 		out(flags|O_NONL, "K=%d masked from:", bp->nork);
1640 
1641 	if (bp->t == B_TO || bp->t == B_INHIBIT) {
1642 		for (ap = itree_next_arrow(bp, NULL); ap;
1643 		    ap = itree_next_arrow(bp, ap)) {
1644 			ASSERT(ap->arrowp->head == bp);
1645 			ASSERT(ap->arrowp->tail != NULL);
1646 			ASSERT(ap->arrowp->tail->myevent != NULL);
1647 			out(flags|O_NONL, " ");
1648 			itree_pevent_brief(flags, ap->arrowp->tail->myevent);
1649 		}
1650 		out(flags, NULL);
1651 		return;
1652 	}
1653 
1654 	for (ap = itree_next_arrow(bp, NULL); ap;
1655 	    ap = itree_next_arrow(bp, ap)) {
1656 		ASSERT(ap->arrowp->tail == bp);
1657 		ASSERT(ap->arrowp->head != NULL);
1658 		ASSERT(ap->arrowp->head->myevent != NULL);
1659 
1660 		out(flags|O_NONL, " ");
1661 		itree_pevent_brief(flags, ap->arrowp->head->myevent);
1662 
1663 		out(flags|O_NONL, " ");
1664 		ptree_timeval(flags, &ap->arrowp->mindelay);
1665 		out(flags|O_NONL, ",");
1666 		ptree_timeval(flags, &ap->arrowp->maxdelay);
1667 
1668 		/* Display anything from the propogation node? */
1669 		out(O_VERB3|O_NONL, " <%s:%d>",
1670 		    ap->arrowp->pnode->file, ap->arrowp->pnode->line);
1671 
1672 		if (itree_next_constraint(ap->arrowp, NULL))
1673 			out(flags|O_NONL, " {");
1674 
1675 		for (cp = itree_next_constraint(ap->arrowp, NULL); cp;
1676 		    cp = itree_next_constraint(ap->arrowp, cp)) {
1677 			ptree(flags, cp->cnode, 1, 0);
1678 			if (itree_next_constraint(ap->arrowp, cp))
1679 				out(flags|O_NONL, ", ");
1680 		}
1681 
1682 		if (itree_next_constraint(ap->arrowp, NULL))
1683 			out(flags|O_NONL, "}");
1684 	}
1685 	out(flags, NULL);
1686 }
1687 
1688 void
itree_ptree(int flags,struct lut * itp)1689 itree_ptree(int flags, struct lut *itp)
1690 {
1691 	lut_walk(itp, (lut_cb)itree_pevent, (void *)(intptr_t)flags);
1692 }
1693 
1694 /*ARGSUSED*/
1695 static void
itree_destructor(void * left,void * right,void * arg)1696 itree_destructor(void *left, void *right, void *arg)
1697 {
1698 	struct event *ep = (struct event *)right;
1699 	struct bubble *nextbub, *bub;
1700 
1701 	/* Free the properties */
1702 	if (ep->props)
1703 		lut_free(ep->props, instances_destructor, NULL);
1704 
1705 	/* Free the payload properties */
1706 	if (ep->payloadprops)
1707 		lut_free(ep->payloadprops, payloadprops_destructor, NULL);
1708 
1709 	/* Free the serd properties */
1710 	if (ep->serdprops)
1711 		lut_free(ep->serdprops, serdprops_destructor, NULL);
1712 
1713 	/* Free my bubbles */
1714 	for (bub = ep->bubbles; bub != NULL; ) {
1715 		nextbub = bub->next;
1716 		/*
1717 		 * Free arrows if they are FROM me.  Free arrowlists on
1718 		 * other types of bubbles (but not the attached arrows,
1719 		 * which will be freed when we free the originating
1720 		 * bubble.
1721 		 */
1722 		if (bub->t == B_FROM)
1723 			itree_free_arrowlists(bub, 1);
1724 		else
1725 			itree_free_arrowlists(bub, 0);
1726 		itree_free_bubble(bub);
1727 		bub = nextbub;
1728 	}
1729 
1730 	nvlist_free(ep->nvp);
1731 	alloc_xfree(ep, sizeof (*ep));
1732 }
1733 
1734 /*ARGSUSED*/
1735 static void
itree_pruner(void * left,void * right,void * arg)1736 itree_pruner(void *left, void *right, void *arg)
1737 {
1738 	struct event *ep = (struct event *)right;
1739 	struct bubble *nextbub, *bub;
1740 
1741 	if (ep->keep_in_tree)
1742 		return;
1743 
1744 	/* Free the properties */
1745 	lut_free(ep->props, instances_destructor, NULL);
1746 
1747 	/* Free the payload properties */
1748 	lut_free(ep->payloadprops, payloadprops_destructor, NULL);
1749 
1750 	/* Free the serd properties */
1751 	lut_free(ep->serdprops, serdprops_destructor, NULL);
1752 
1753 	/* Free my bubbles */
1754 	for (bub = ep->bubbles; bub != NULL; ) {
1755 		nextbub = bub->next;
1756 		itree_prune_arrowlists(bub);
1757 		itree_free_bubble(bub);
1758 		bub = nextbub;
1759 	}
1760 
1761 	nvlist_free(ep->nvp);
1762 	ep->props = NULL;
1763 	ep->payloadprops = NULL;
1764 	ep->serdprops = NULL;
1765 	ep->bubbles = NULL;
1766 	ep->nvp = NULL;
1767 }
1768 
1769 static void
itree_free_bubble(struct bubble * freeme)1770 itree_free_bubble(struct bubble *freeme)
1771 {
1772 	alloc_xfree(freeme, sizeof (*freeme));
1773 }
1774 
1775 static struct bubble *
itree_add_bubble(struct event * eventp,enum bubbletype btype,int nork,int gen)1776 itree_add_bubble(struct event *eventp, enum bubbletype btype, int nork, int gen)
1777 {
1778 	struct bubble *prev = NULL;
1779 	struct bubble *curr;
1780 	struct bubble *newb;
1781 
1782 	/* Use existing bubbles as appropriate when possible */
1783 	for (curr = eventp->bubbles;
1784 	    curr != NULL;
1785 	    prev = curr, curr = curr->next) {
1786 		if (btype == B_TO && curr->t == B_TO) {
1787 			/* see if an existing "to" bubble works for us */
1788 			if (gen == curr->gen)
1789 				return (curr);	/* matched gen number */
1790 			else if (nork == 1 && curr->nork == 1) {
1791 				curr->gen = gen;
1792 				return (curr);	/* coalesce K==1 bubbles */
1793 			}
1794 		} else if (btype == B_FROM && curr->t == B_FROM) {
1795 			/* see if an existing "from" bubble works for us */
1796 			if ((nork == N_IS_ALL && curr->nork == N_IS_ALL) ||
1797 			    (nork == 0 && curr->nork == 0))
1798 				return (curr);
1799 		}
1800 	}
1801 
1802 	newb = alloc_xmalloc(sizeof (struct bubble));
1803 	newb->next = NULL;
1804 	newb->t = btype;
1805 	newb->myevent = eventp;
1806 	newb->nork = nork;
1807 	newb->mark = 0;
1808 	newb->gen = gen;
1809 	newb->arrows = NULL;
1810 
1811 	if (prev == NULL)
1812 		eventp->bubbles = newb;
1813 	else
1814 		prev->next = newb;
1815 
1816 	return (newb);
1817 }
1818 
1819 struct bubble *
itree_next_bubble(struct event * eventp,struct bubble * last)1820 itree_next_bubble(struct event *eventp, struct bubble *last)
1821 {
1822 	struct bubble *next;
1823 
1824 	for (;;) {
1825 		if (last != NULL)
1826 			next = last->next;
1827 		else
1828 			next = eventp->bubbles;
1829 
1830 		if (next == NULL || next->arrows != NULL)
1831 			return (next);
1832 
1833 		/* bubble was empty, skip it */
1834 		last = next;
1835 	}
1836 }
1837 
1838 static void
add_arrow(struct bubble * bp,struct arrow * ap)1839 add_arrow(struct bubble *bp, struct arrow *ap)
1840 {
1841 	struct arrowlist *prev = NULL;
1842 	struct arrowlist *curr;
1843 	struct arrowlist *newal;
1844 
1845 	newal = alloc_xmalloc(sizeof (struct arrowlist));
1846 	bzero(newal, sizeof (struct arrowlist));
1847 	newal->arrowp = ap;
1848 
1849 	curr = itree_next_arrow(bp, NULL);
1850 	while (curr != NULL) {
1851 		prev = curr;
1852 		curr = itree_next_arrow(bp, curr);
1853 	}
1854 
1855 	if (prev == NULL)
1856 		bp->arrows = newal;
1857 	else
1858 		prev->next = newal;
1859 }
1860 
1861 static struct arrow *
itree_add_arrow(struct node * apnode,struct node * fromevent,struct node * toevent,struct lut * ex)1862 itree_add_arrow(struct node *apnode, struct node *fromevent,
1863     struct node *toevent, struct lut *ex)
1864 {
1865 	struct arrow *newa;
1866 
1867 	newa = alloc_xmalloc(sizeof (struct arrow));
1868 	bzero(newa, sizeof (struct arrow));
1869 	newa->pnode = apnode;
1870 	newa->constraints = NULL;
1871 
1872 	/*
1873 	 *  Set default delays, then try to re-set them from
1874 	 *  any within() constraints.
1875 	 */
1876 	newa->mindelay = newa->maxdelay = 0ULL;
1877 	if (itree_set_arrow_traits(newa, fromevent, toevent, ex) == 0) {
1878 		alloc_xfree(newa, sizeof (struct arrow));
1879 		return (NULL);
1880 	}
1881 
1882 	return (newa);
1883 }
1884 
1885 /* returns false if traits show that arrow should not be added after all */
1886 static int
itree_set_arrow_traits(struct arrow * ap,struct node * fromev,struct node * toev,struct lut * ex)1887 itree_set_arrow_traits(struct arrow *ap, struct node *fromev,
1888     struct node *toev, struct lut *ex)
1889 {
1890 	struct node *events[] = { NULL, NULL, NULL };
1891 	struct node *newc = NULL;
1892 
1893 	ASSERTeq(fromev->t, T_EVENT, ptree_nodetype2str);
1894 	ASSERTeq(toev->t, T_EVENT, ptree_nodetype2str);
1895 
1896 	/*
1897 	 * search for the within values first on the declaration of
1898 	 * the destination event, and then on the prop.  this allows
1899 	 * one to specify a "default" within by putting it on the
1900 	 * declaration,  but then allow overriding on the prop statement.
1901 	 */
1902 	arrow_add_within(ap, toev->u.event.declp->u.stmt.np->u.event.eexprlist);
1903 	arrow_add_within(ap, toev->u.event.eexprlist);
1904 
1905 	/*
1906 	 * handle any global constraints inherited from the
1907 	 * "fromev" event's declaration
1908 	 */
1909 	ASSERT(fromev->u.event.declp != NULL);
1910 	ASSERT(fromev->u.event.declp->u.stmt.np != NULL);
1911 
1912 #ifdef	notdef
1913 	/* XXX not quite ready to evaluate constraints from decls yet */
1914 	if (fromev->u.event.declp->u.stmt.np->u.event.eexprlist)
1915 		(void) itree_add_constraint(ap,
1916 		    fromev->u.event.declp->u.stmt.np->u.event.eexprlist);
1917 #endif	/* notdef */
1918 
1919 	/* handle constraints on the from event in the prop statement */
1920 	events[0] = fromev;
1921 	events[1] = toev;
1922 	if (eval_potential(fromev->u.event.eexprlist, ex, events, &newc,
1923 	    Ninfo.croot) == 0)
1924 		return (0);		/* constraint disallows arrow */
1925 
1926 	/*
1927 	 * handle any global constraints inherited from the
1928 	 * "toev" event's declaration
1929 	 */
1930 	ASSERT(toev->u.event.declp != NULL);
1931 	ASSERT(toev->u.event.declp->u.stmt.np != NULL);
1932 
1933 #ifdef	notdef
1934 	/* XXX not quite ready to evaluate constraints from decls yet */
1935 	if (toev->u.event.declp->u.stmt.np->u.event.eexprlist)
1936 		(void) itree_add_constraint(ap,
1937 		    toev->u.event.declp->u.stmt.np->u.event.eexprlist);
1938 #endif	/* notdef */
1939 
1940 	/* handle constraints on the to event in the prop statement */
1941 	events[0] = toev;
1942 	events[1] = fromev;
1943 	if (eval_potential(toev->u.event.eexprlist, ex, events, &newc,
1944 	    Ninfo.croot) == 0) {
1945 		if (newc != NULL)
1946 			tree_free(newc);
1947 		return (0);		/* constraint disallows arrow */
1948 	}
1949 
1950 	/* if we came up with any deferred constraints, add them to arrow */
1951 	if (newc != NULL) {
1952 		out(O_ALTFP|O_VERB3, "(deferred constraints)");
1953 		(void) itree_add_constraint(ap, iexpr(newc));
1954 	}
1955 
1956 	return (1);	/* constraints allow arrow */
1957 }
1958 
1959 /*
1960  * Set within() constraint.  If the constraint were set multiple times,
1961  * the last one would "win".
1962  */
1963 static void
arrow_add_within(struct arrow * ap,struct node * xpr)1964 arrow_add_within(struct arrow *ap, struct node *xpr)
1965 {
1966 	struct node *arglist;
1967 
1968 	/* end of expressions list */
1969 	if (xpr == NULL)
1970 		return;
1971 
1972 	switch (xpr->t) {
1973 	case T_LIST:
1974 		arrow_add_within(ap, xpr->u.expr.left);
1975 		arrow_add_within(ap, xpr->u.expr.right);
1976 		return;
1977 	case T_FUNC:
1978 		if (xpr->u.func.s != L_within)
1979 			return;
1980 		arglist = xpr->u.func.arglist;
1981 		switch (arglist->t) {
1982 		case T_TIMEVAL:
1983 			ap->mindelay = 0;
1984 			ap->maxdelay = arglist->u.ull;
1985 			break;
1986 		case T_NAME:
1987 			ASSERT(arglist->u.name.s == L_infinity);
1988 			ap->mindelay = 0;
1989 			ap->maxdelay = TIMEVAL_EVENTUALLY;
1990 			break;
1991 		case T_LIST:
1992 			ASSERT(arglist->u.expr.left->t == T_TIMEVAL);
1993 			ap->mindelay = arglist->u.expr.left->u.ull;
1994 			switch (arglist->u.expr.right->t) {
1995 			case T_TIMEVAL:
1996 				ap->maxdelay = arglist->u.ull;
1997 				break;
1998 			case T_NAME:
1999 				ASSERT(arglist->u.expr.right->u.name.s ==
2000 				    L_infinity);
2001 				ap->maxdelay = TIMEVAL_EVENTUALLY;
2002 				break;
2003 			default:
2004 				out(O_DIE, "within: unexpected 2nd arg type");
2005 			}
2006 			break;
2007 		default:
2008 			out(O_DIE, "within: unexpected 1st arg type");
2009 		}
2010 		break;
2011 	default:
2012 		return;
2013 	}
2014 }
2015 
2016 static void
itree_free_arrowlists(struct bubble * bubp,int arrows_too)2017 itree_free_arrowlists(struct bubble *bubp, int arrows_too)
2018 {
2019 	struct arrowlist *al, *nal;
2020 
2021 	al = bubp->arrows;
2022 	while (al != NULL) {
2023 		nal = al->next;
2024 		if (arrows_too) {
2025 			itree_free_constraints(al->arrowp);
2026 			alloc_xfree(al->arrowp, sizeof (struct arrow));
2027 		}
2028 		alloc_xfree(al, sizeof (*al));
2029 		al = nal;
2030 	}
2031 }
2032 
2033 static void
itree_delete_arrow(struct bubble * bubp,struct arrow * arrow)2034 itree_delete_arrow(struct bubble *bubp, struct arrow *arrow)
2035 {
2036 	struct arrowlist *al, *oal;
2037 
2038 	al = bubp->arrows;
2039 	if (al->arrowp == arrow) {
2040 		bubp->arrows = al->next;
2041 		alloc_xfree(al, sizeof (*al));
2042 		return;
2043 	}
2044 	while (al != NULL) {
2045 		oal = al;
2046 		al = al->next;
2047 		ASSERT(al != NULL);
2048 		if (al->arrowp == arrow) {
2049 			oal->next = al->next;
2050 			alloc_xfree(al, sizeof (*al));
2051 			return;
2052 		}
2053 	}
2054 }
2055 
2056 static void
itree_prune_arrowlists(struct bubble * bubp)2057 itree_prune_arrowlists(struct bubble *bubp)
2058 {
2059 	struct arrowlist *al, *nal;
2060 
2061 	al = bubp->arrows;
2062 	while (al != NULL) {
2063 		nal = al->next;
2064 		if (bubp->t == B_FROM)
2065 			itree_delete_arrow(al->arrowp->head, al->arrowp);
2066 		else
2067 			itree_delete_arrow(al->arrowp->tail, al->arrowp);
2068 		itree_free_constraints(al->arrowp);
2069 		alloc_xfree(al->arrowp, sizeof (struct arrow));
2070 		alloc_xfree(al, sizeof (*al));
2071 		al = nal;
2072 	}
2073 }
2074 
2075 struct arrowlist *
itree_next_arrow(struct bubble * bubble,struct arrowlist * last)2076 itree_next_arrow(struct bubble *bubble, struct arrowlist *last)
2077 {
2078 	struct arrowlist *next;
2079 
2080 	if (last != NULL)
2081 		next = last->next;
2082 	else
2083 		next = bubble->arrows;
2084 	return (next);
2085 }
2086 
2087 static struct constraintlist *
itree_add_constraint(struct arrow * arrowp,struct node * c)2088 itree_add_constraint(struct arrow *arrowp, struct node *c)
2089 {
2090 	struct constraintlist *prev = NULL;
2091 	struct constraintlist *curr;
2092 	struct constraintlist *newc;
2093 
2094 	for (curr = arrowp->constraints;
2095 	    curr != NULL;
2096 	    prev = curr, curr = curr->next)
2097 		;
2098 
2099 	newc = alloc_xmalloc(sizeof (struct constraintlist));
2100 	newc->next = NULL;
2101 	newc->cnode = c;
2102 
2103 	if (prev == NULL)
2104 		arrowp->constraints = newc;
2105 	else
2106 		prev->next = newc;
2107 
2108 	return (newc);
2109 }
2110 
2111 struct constraintlist *
itree_next_constraint(struct arrow * arrowp,struct constraintlist * last)2112 itree_next_constraint(struct arrow *arrowp, struct constraintlist *last)
2113 {
2114 	struct constraintlist *next;
2115 
2116 	if (last != NULL)
2117 		next = last->next;
2118 	else
2119 		next = arrowp->constraints;
2120 	return (next);
2121 }
2122 
2123 static void
itree_free_constraints(struct arrow * ap)2124 itree_free_constraints(struct arrow *ap)
2125 {
2126 	struct constraintlist *cl, *ncl;
2127 
2128 	cl = ap->constraints;
2129 	while (cl != NULL) {
2130 		ncl = cl->next;
2131 		ASSERT(cl->cnode != NULL);
2132 		if (!iexpr_cached(cl->cnode))
2133 			tree_free(cl->cnode);
2134 		else
2135 			iexpr_free(cl->cnode);
2136 		alloc_xfree(cl, sizeof (*cl));
2137 		cl = ncl;
2138 	}
2139 }
2140 
2141 const char *
itree_bubbletype2str(enum bubbletype t)2142 itree_bubbletype2str(enum bubbletype t)
2143 {
2144 	static char buf[100];
2145 
2146 	switch (t) {
2147 	case B_FROM:	return L_from;
2148 	case B_TO:	return L_to;
2149 	case B_INHIBIT:	return L_inhibit;
2150 	default:
2151 		(void) sprintf(buf, "[unexpected bubbletype: %d]", t);
2152 		return (buf);
2153 	}
2154 }
2155 
2156 /*
2157  * itree_fini -- clean up any half-built itrees
2158  */
2159 void
itree_fini(void)2160 itree_fini(void)
2161 {
2162 	if (Ninfo.lut != NULL) {
2163 		itree_free(Ninfo.lut);
2164 		Ninfo.lut = NULL;
2165 	}
2166 	if (Ninfo.ex) {
2167 		lut_free(Ninfo.ex, iterinfo_destructor, NULL);
2168 		Ninfo.ex = NULL;
2169 	}
2170 }
2171