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, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright 2006 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 } *Cache[IEXPRSZ]; 56 57 /* 58 * iexpr_init -- initialize the iexpr module 59 */ 60 void 61 iexpr_init(void) 62 { 63 Niexpr = stats_new_counter("iexpr.niexpr", "iexpr cache entries", 1); 64 } 65 66 /* 67 * iexpr_hash -- produce a simple hash from an instanced expression tree 68 */ 69 static unsigned 70 iexpr_hash(struct node *np) 71 { 72 if (np == NULL) 73 return (1); 74 75 switch (np->t) { 76 case T_GLOBID: 77 return ((int)np->u.globid.s); 78 79 case T_ASSIGN: 80 case T_CONDIF: 81 case T_CONDELSE: 82 case T_NE: 83 case T_EQ: 84 case T_LT: 85 case T_LE: 86 case T_GT: 87 case T_GE: 88 case T_BITAND: 89 case T_BITOR: 90 case T_BITXOR: 91 case T_BITNOT: 92 case T_LSHIFT: 93 case T_RSHIFT: 94 case T_LIST: 95 case T_AND: 96 case T_OR: 97 case T_NOT: 98 case T_ADD: 99 case T_SUB: 100 case T_MUL: 101 case T_DIV: 102 case T_MOD: 103 return ((int)np->t * 104 (iexpr_hash(np->u.expr.left) + 105 iexpr_hash(np->u.expr.right))); 106 107 case T_NAME: 108 return ((int)np->u.name.s); 109 110 case T_EVENT: 111 return (iexpr_hash(np->u.event.ename) + 112 iexpr_hash(np->u.event.epname)); 113 114 case T_FUNC: 115 return ((int)np->u.func.s + 116 iexpr_hash(np->u.func.arglist)); 117 118 case T_QUOTE: 119 return ((int)np->u.quote.s); 120 121 case T_NUM: 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 } 131 132 /* 133 * iexpr_cmp -- compare two instanced expression trees 134 */ 135 static int 136 iexpr_cmp(struct node *np1, struct node *np2) 137 { 138 int diff; 139 140 if (np1 == np2) 141 return (0); 142 143 if (np1 == NULL) 144 return (1); 145 146 if (np2 == NULL) 147 return (-1); 148 149 if (np1->t != np2->t) 150 return (np2->t - np1->t); 151 152 /* types match, need to see additional info matches */ 153 switch (np1->t) { 154 case T_GLOBID: 155 return (np2->u.globid.s - np1->u.globid.s); 156 157 case T_ASSIGN: 158 case T_CONDIF: 159 case T_CONDELSE: 160 case T_NE: 161 case T_EQ: 162 case T_LT: 163 case T_LE: 164 case T_GT: 165 case T_GE: 166 case T_BITAND: 167 case T_BITOR: 168 case T_BITXOR: 169 case T_BITNOT: 170 case T_LSHIFT: 171 case T_RSHIFT: 172 case T_LIST: 173 case T_AND: 174 case T_OR: 175 case T_NOT: 176 case T_ADD: 177 case T_SUB: 178 case T_MUL: 179 case T_DIV: 180 case T_MOD: 181 diff = iexpr_cmp(np1->u.expr.left, np2->u.expr.left); 182 if (diff != 0) 183 return (diff); 184 return (iexpr_cmp(np1->u.expr.right, np2->u.expr.right)); 185 186 case T_NAME: 187 if (np2->u.name.s != np1->u.name.s) 188 return (np2->u.name.s - np1->u.name.s); 189 diff = iexpr_cmp(np1->u.name.child, np2->u.name.child); 190 if (diff != 0) 191 return (diff); 192 return (iexpr_cmp(np1->u.name.next, np2->u.name.next)); 193 194 case T_EVENT: 195 diff = iexpr_cmp(np1->u.event.ename, np2->u.event.ename); 196 if (diff != 0) 197 return (diff); 198 return (iexpr_cmp(np1->u.event.epname, np2->u.event.epname)); 199 200 case T_FUNC: 201 if (np1->u.func.s != np2->u.func.s) 202 return (np2->u.func.s - np1->u.func.s); 203 return (iexpr_cmp(np1->u.func.arglist, np2->u.func.arglist)); 204 205 case T_QUOTE: 206 return (np2->u.quote.s - np1->u.quote.s); 207 208 case T_NUM: 209 if (np2->u.ull > np1->u.ull) 210 return (1); 211 else if (np1->u.ull > np2->u.ull) 212 return (-1); 213 else 214 return (0); 215 216 default: 217 outfl(O_DIE, np1->file, np1->line, 218 "iexpr_cmp: unexpected node type: %s", 219 ptree_nodetype2str(np1->t)); 220 } 221 /*NOTREACHED*/ 222 } 223 224 /* 225 * iexpr -- find instanced expr in cache, or add it if necessary 226 */ 227 struct node * 228 iexpr(struct node *np) 229 { 230 unsigned idx = iexpr_hash(np) % IEXPRSZ; 231 struct iexpr *bucketp = Cache[idx]; 232 struct iexpr *cp; 233 234 /* search cache */ 235 for (cp = bucketp; cp != NULL; cp = cp->next) 236 if (iexpr_cmp(cp->np, np) == 0) { 237 /* found it */ 238 tree_free(np); 239 return (cp->np); 240 } 241 242 /* allocate new cache entry */ 243 cp = MALLOC(sizeof (*cp)); 244 cp->np = np; 245 cp->next = bucketp; 246 Cache[idx] = cp; 247 248 stats_counter_bump(Niexpr); 249 250 return (np); 251 } 252 253 /* 254 * iexpr_cached -- return true if np is in the iexpr cache 255 */ 256 int 257 iexpr_cached(struct node *np) 258 { 259 struct iexpr *cp = Cache[iexpr_hash(np) % IEXPRSZ]; 260 261 /* search cache */ 262 for (; cp != NULL; cp = cp->next) 263 if (iexpr_cmp(cp->np, np) == 0) { 264 /* found it */ 265 return (1); 266 } 267 268 return (0); 269 } 270 271 /* 272 * iexpr_fini -- free the iexpr cache 273 */ 274 void 275 iexpr_fini(void) 276 { 277 int i; 278 279 for (i = 0; i < IEXPRSZ; i++) { 280 struct iexpr *cp; 281 struct iexpr *ncp; 282 283 for (cp = Cache[i]; cp != NULL; cp = ncp) { 284 tree_free(cp->np); 285 ncp = cp->next; 286 FREE(cp); 287 } 288 Cache[i] = NULL; 289 } 290 } 291