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