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 2008 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 *
26 * iexpr.c -- instanced expression cache module
27 *
28 * this module provides a cache of fully instantized expressions.
29 */
30
31 #pragma ident "%Z%%M% %I% %E% SMI"
32
33 #include <stdio.h>
34 #include <string.h>
35 #include "alloc.h"
36 #include "out.h"
37 #include "lut.h"
38 #include "tree.h"
39 #include "ptree.h"
40 #include "itree.h"
41 #include "ipath.h"
42 #include "iexpr.h"
43 #include "stats.h"
44 #include "eval.h"
45 #include "config.h"
46
47 #define IEXPRSZ 1024 /* hash table size */
48
49 static struct stats *Niexpr;
50
51 /* the cache is a hash table of these structs */
52 static struct iexpr {
53 struct node *np;
54 struct iexpr *next; /* next entry in hash bucket */
55 int count;
56 } *Cache[IEXPRSZ];
57
58 /*
59 * iexpr_init -- initialize the iexpr module
60 */
61 void
iexpr_init(void)62 iexpr_init(void)
63 {
64 Niexpr = stats_new_counter("iexpr.niexpr", "iexpr cache entries", 1);
65 }
66
67 /*
68 * iexpr_hash -- produce a simple hash from an instanced expression tree
69 */
70 static unsigned
iexpr_hash(struct node * np)71 iexpr_hash(struct node *np)
72 {
73 if (np == NULL)
74 return (1);
75
76 switch (np->t) {
77 case T_GLOBID:
78 return ((uintptr_t)np->u.globid.s);
79
80 case T_ASSIGN:
81 case T_CONDIF:
82 case T_CONDELSE:
83 case T_NE:
84 case T_EQ:
85 case T_LT:
86 case T_LE:
87 case T_GT:
88 case T_GE:
89 case T_BITAND:
90 case T_BITOR:
91 case T_BITXOR:
92 case T_BITNOT:
93 case T_LSHIFT:
94 case T_RSHIFT:
95 case T_LIST:
96 case T_AND:
97 case T_OR:
98 case T_NOT:
99 case T_ADD:
100 case T_SUB:
101 case T_MUL:
102 case T_DIV:
103 case T_MOD:
104 return ((int)np->t *
105 (iexpr_hash(np->u.expr.left) +
106 iexpr_hash(np->u.expr.right)));
107
108 case T_NAME:
109 return ((uintptr_t)np->u.name.s);
110
111 case T_EVENT:
112 return (iexpr_hash(np->u.event.ename) +
113 iexpr_hash(np->u.event.epname));
114
115 case T_FUNC:
116 return ((uintptr_t)np->u.func.s +
117 iexpr_hash(np->u.func.arglist));
118
119 case T_QUOTE:
120 return ((uintptr_t)np->u.quote.s);
121
122 case T_NUM:
123 case T_TIMEVAL:
124 return ((int)np->u.ull);
125
126 default:
127 outfl(O_DIE, np->file, np->line,
128 "iexpr_hash: unexpected node type: %s",
129 ptree_nodetype2str(np->t));
130 }
131 /*NOTREACHED*/
132 return (1);
133 }
134
135 /*
136 * iexpr_cmp -- compare two instanced expression trees
137 */
138 static int
iexpr_cmp(struct node * np1,struct node * np2)139 iexpr_cmp(struct node *np1, struct node *np2)
140 {
141 int diff;
142
143 if (np1 == np2)
144 return (0);
145
146 if (np1 == NULL)
147 return (1);
148
149 if (np2 == NULL)
150 return (-1);
151
152 if (np1->t != np2->t)
153 return (np2->t - np1->t);
154
155 /* types match, need to see additional info matches */
156 switch (np1->t) {
157 case T_GLOBID:
158 return (np2->u.globid.s - np1->u.globid.s);
159
160 case T_ASSIGN:
161 case T_CONDIF:
162 case T_CONDELSE:
163 case T_NE:
164 case T_EQ:
165 case T_LT:
166 case T_LE:
167 case T_GT:
168 case T_GE:
169 case T_BITAND:
170 case T_BITOR:
171 case T_BITXOR:
172 case T_BITNOT:
173 case T_LSHIFT:
174 case T_RSHIFT:
175 case T_LIST:
176 case T_AND:
177 case T_OR:
178 case T_NOT:
179 case T_ADD:
180 case T_SUB:
181 case T_MUL:
182 case T_DIV:
183 case T_MOD:
184 diff = iexpr_cmp(np1->u.expr.left, np2->u.expr.left);
185 if (diff != 0)
186 return (diff);
187 return (iexpr_cmp(np1->u.expr.right, np2->u.expr.right));
188
189 case T_NAME:
190 if (np2->u.name.s != np1->u.name.s)
191 return (np2->u.name.s - np1->u.name.s);
192 diff = iexpr_cmp(np1->u.name.child, np2->u.name.child);
193 if (diff != 0)
194 return (diff);
195 return (iexpr_cmp(np1->u.name.next, np2->u.name.next));
196
197 case T_EVENT:
198 diff = iexpr_cmp(np1->u.event.ename, np2->u.event.ename);
199 if (diff != 0)
200 return (diff);
201 return (iexpr_cmp(np1->u.event.epname, np2->u.event.epname));
202
203 case T_FUNC:
204 if (np1->u.func.s != np2->u.func.s)
205 return (np2->u.func.s - np1->u.func.s);
206 return (iexpr_cmp(np1->u.func.arglist, np2->u.func.arglist));
207
208 case T_QUOTE:
209 return (np2->u.quote.s - np1->u.quote.s);
210
211 case T_NUM:
212 case T_TIMEVAL:
213 if (np2->u.ull > np1->u.ull)
214 return (1);
215 else if (np1->u.ull > np2->u.ull)
216 return (-1);
217 else
218 return (0);
219
220 default:
221 outfl(O_DIE, np1->file, np1->line,
222 "iexpr_cmp: unexpected node type: %s",
223 ptree_nodetype2str(np1->t));
224 }
225 /*NOTREACHED*/
226 return (0);
227 }
228
229 /*
230 * iexpr -- find instanced expr in cache, or add it if necessary
231 */
232 struct node *
iexpr(struct node * np)233 iexpr(struct node *np)
234 {
235 unsigned idx = iexpr_hash(np) % IEXPRSZ;
236 struct iexpr *bucketp = Cache[idx];
237 struct iexpr *cp;
238
239 /* search cache */
240 for (cp = bucketp; cp != NULL; cp = cp->next)
241 if (iexpr_cmp(cp->np, np) == 0) {
242 /* found it */
243 tree_free(np);
244 cp->count++;
245 return (cp->np);
246 }
247
248 /* allocate new cache entry */
249 cp = MALLOC(sizeof (*cp));
250 cp->np = np;
251 cp->next = bucketp;
252 cp->count = 1;
253 Cache[idx] = cp;
254
255 stats_counter_bump(Niexpr);
256
257 return (np);
258 }
259
260 void
iexpr_free(struct node * np)261 iexpr_free(struct node *np)
262 {
263 unsigned idx = iexpr_hash(np) % IEXPRSZ;
264 struct iexpr *cp;
265 struct iexpr *prevcp = NULL;
266
267 /* search cache */
268 for (cp = Cache[idx]; cp != NULL; cp = cp->next) {
269 if (iexpr_cmp(cp->np, np) == 0) {
270 /* found it */
271 cp->count--;
272 if (cp->count == 0) {
273 tree_free(cp->np);
274 if (prevcp == NULL)
275 Cache[idx] = cp->next;
276 else
277 prevcp->next = cp->next;
278 FREE(cp);
279 }
280 return;
281 }
282 prevcp = cp;
283 }
284 }
285
286 /*
287 * iexpr_cached -- return true if np is in the iexpr cache
288 */
289 int
iexpr_cached(struct node * np)290 iexpr_cached(struct node *np)
291 {
292 struct iexpr *cp = Cache[iexpr_hash(np) % IEXPRSZ];
293
294 /* search cache */
295 for (; cp != NULL; cp = cp->next)
296 if (iexpr_cmp(cp->np, np) == 0) {
297 /* found it */
298 return (1);
299 }
300
301 return (0);
302 }
303
304 /*
305 * iexpr_fini -- free the iexpr cache
306 */
307 void
iexpr_fini(void)308 iexpr_fini(void)
309 {
310 int i;
311
312 for (i = 0; i < IEXPRSZ; i++) {
313 struct iexpr *cp;
314 struct iexpr *ncp;
315
316 for (cp = Cache[i]; cp != NULL; cp = ncp) {
317 tree_free(cp->np);
318 ncp = cp->next;
319 FREE(cp);
320 }
321 Cache[i] = NULL;
322 }
323 }
324