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 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 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 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 * 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 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 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 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