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