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