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