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