17aec1d6eScindi /* 27aec1d6eScindi * CDDL HEADER START 37aec1d6eScindi * 47aec1d6eScindi * The contents of this file are subject to the terms of the 580ab886dSwesolows * Common Development and Distribution License (the "License"). 680ab886dSwesolows * You may not use this file except in compliance with the License. 77aec1d6eScindi * 87aec1d6eScindi * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 97aec1d6eScindi * or http://www.opensolaris.org/os/licensing. 107aec1d6eScindi * See the License for the specific language governing permissions 117aec1d6eScindi * and limitations under the License. 127aec1d6eScindi * 137aec1d6eScindi * When distributing Covered Code, include this CDDL HEADER in each 147aec1d6eScindi * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 157aec1d6eScindi * If applicable, add the following below this CDDL HEADER, with the 167aec1d6eScindi * fields enclosed by brackets "[]" replaced with your own identifying 177aec1d6eScindi * information: Portions Copyright [yyyy] [name of copyright owner] 187aec1d6eScindi * 197aec1d6eScindi * CDDL HEADER END 207aec1d6eScindi */ 2180ab886dSwesolows 227aec1d6eScindi /* 23837416c3Scy152378 * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 247aec1d6eScindi * Use is subject to license terms. 257aec1d6eScindi * 267aec1d6eScindi * iexpr.c -- instanced expression cache module 277aec1d6eScindi * 287aec1d6eScindi * this module provides a cache of fully instantized expressions. 297aec1d6eScindi */ 307aec1d6eScindi 317aec1d6eScindi #pragma ident "%Z%%M% %I% %E% SMI" 327aec1d6eScindi 337aec1d6eScindi #include <stdio.h> 347aec1d6eScindi #include <string.h> 357aec1d6eScindi #include "alloc.h" 367aec1d6eScindi #include "out.h" 377aec1d6eScindi #include "lut.h" 387aec1d6eScindi #include "tree.h" 397aec1d6eScindi #include "ptree.h" 407aec1d6eScindi #include "itree.h" 417aec1d6eScindi #include "ipath.h" 427aec1d6eScindi #include "iexpr.h" 437aec1d6eScindi #include "stats.h" 447aec1d6eScindi #include "eval.h" 457aec1d6eScindi #include "config.h" 467aec1d6eScindi 477aec1d6eScindi #define IEXPRSZ 1024 /* hash table size */ 487aec1d6eScindi 497aec1d6eScindi static struct stats *Niexpr; 507aec1d6eScindi 517aec1d6eScindi /* the cache is a hash table of these structs */ 527aec1d6eScindi static struct iexpr { 537aec1d6eScindi struct node *np; 547aec1d6eScindi struct iexpr *next; /* next entry in hash bucket */ 5500d0963fSdilpreet int count; 567aec1d6eScindi } *Cache[IEXPRSZ]; 577aec1d6eScindi 587aec1d6eScindi /* 597aec1d6eScindi * iexpr_init -- initialize the iexpr module 607aec1d6eScindi */ 617aec1d6eScindi void 627aec1d6eScindi iexpr_init(void) 637aec1d6eScindi { 647aec1d6eScindi Niexpr = stats_new_counter("iexpr.niexpr", "iexpr cache entries", 1); 657aec1d6eScindi } 667aec1d6eScindi 677aec1d6eScindi /* 687aec1d6eScindi * iexpr_hash -- produce a simple hash from an instanced expression tree 697aec1d6eScindi */ 707aec1d6eScindi static unsigned 717aec1d6eScindi iexpr_hash(struct node *np) 727aec1d6eScindi { 737aec1d6eScindi if (np == NULL) 747aec1d6eScindi return (1); 757aec1d6eScindi 767aec1d6eScindi switch (np->t) { 777aec1d6eScindi case T_GLOBID: 78837416c3Scy152378 return ((uintptr_t)np->u.globid.s); 797aec1d6eScindi 807aec1d6eScindi case T_ASSIGN: 817aec1d6eScindi case T_CONDIF: 827aec1d6eScindi case T_CONDELSE: 837aec1d6eScindi case T_NE: 847aec1d6eScindi case T_EQ: 857aec1d6eScindi case T_LT: 867aec1d6eScindi case T_LE: 877aec1d6eScindi case T_GT: 887aec1d6eScindi case T_GE: 897aec1d6eScindi case T_BITAND: 907aec1d6eScindi case T_BITOR: 917aec1d6eScindi case T_BITXOR: 927aec1d6eScindi case T_BITNOT: 937aec1d6eScindi case T_LSHIFT: 947aec1d6eScindi case T_RSHIFT: 957aec1d6eScindi case T_LIST: 967aec1d6eScindi case T_AND: 977aec1d6eScindi case T_OR: 987aec1d6eScindi case T_NOT: 997aec1d6eScindi case T_ADD: 1007aec1d6eScindi case T_SUB: 1017aec1d6eScindi case T_MUL: 1027aec1d6eScindi case T_DIV: 1037aec1d6eScindi case T_MOD: 1047aec1d6eScindi return ((int)np->t * 1057aec1d6eScindi (iexpr_hash(np->u.expr.left) + 1067aec1d6eScindi iexpr_hash(np->u.expr.right))); 1077aec1d6eScindi 1087aec1d6eScindi case T_NAME: 109837416c3Scy152378 return ((uintptr_t)np->u.name.s); 1107aec1d6eScindi 1117aec1d6eScindi case T_EVENT: 1127aec1d6eScindi return (iexpr_hash(np->u.event.ename) + 1137aec1d6eScindi iexpr_hash(np->u.event.epname)); 1147aec1d6eScindi 1157aec1d6eScindi case T_FUNC: 116837416c3Scy152378 return ((uintptr_t)np->u.func.s + 1177aec1d6eScindi iexpr_hash(np->u.func.arglist)); 1187aec1d6eScindi 1197aec1d6eScindi case T_QUOTE: 120837416c3Scy152378 return ((uintptr_t)np->u.quote.s); 1217aec1d6eScindi 1227aec1d6eScindi case T_NUM: 123*b7d3956bSstephh case T_TIMEVAL: 1247aec1d6eScindi return ((int)np->u.ull); 1257aec1d6eScindi 1267aec1d6eScindi default: 1277aec1d6eScindi outfl(O_DIE, np->file, np->line, 1287aec1d6eScindi "iexpr_hash: unexpected node type: %s", 1297aec1d6eScindi ptree_nodetype2str(np->t)); 1307aec1d6eScindi } 1317aec1d6eScindi /*NOTREACHED*/ 13280ab886dSwesolows return (1); 1337aec1d6eScindi } 1347aec1d6eScindi 1357aec1d6eScindi /* 1367aec1d6eScindi * iexpr_cmp -- compare two instanced expression trees 1377aec1d6eScindi */ 1387aec1d6eScindi static int 1397aec1d6eScindi iexpr_cmp(struct node *np1, struct node *np2) 1407aec1d6eScindi { 1417aec1d6eScindi int diff; 1427aec1d6eScindi 1437aec1d6eScindi if (np1 == np2) 1447aec1d6eScindi return (0); 1457aec1d6eScindi 1467aec1d6eScindi if (np1 == NULL) 1477aec1d6eScindi return (1); 1487aec1d6eScindi 1497aec1d6eScindi if (np2 == NULL) 1507aec1d6eScindi return (-1); 1517aec1d6eScindi 1527aec1d6eScindi if (np1->t != np2->t) 1537aec1d6eScindi return (np2->t - np1->t); 1547aec1d6eScindi 1557aec1d6eScindi /* types match, need to see additional info matches */ 1567aec1d6eScindi switch (np1->t) { 1577aec1d6eScindi case T_GLOBID: 1587aec1d6eScindi return (np2->u.globid.s - np1->u.globid.s); 1597aec1d6eScindi 1607aec1d6eScindi case T_ASSIGN: 1617aec1d6eScindi case T_CONDIF: 1627aec1d6eScindi case T_CONDELSE: 1637aec1d6eScindi case T_NE: 1647aec1d6eScindi case T_EQ: 1657aec1d6eScindi case T_LT: 1667aec1d6eScindi case T_LE: 1677aec1d6eScindi case T_GT: 1687aec1d6eScindi case T_GE: 1697aec1d6eScindi case T_BITAND: 1707aec1d6eScindi case T_BITOR: 1717aec1d6eScindi case T_BITXOR: 1727aec1d6eScindi case T_BITNOT: 1737aec1d6eScindi case T_LSHIFT: 1747aec1d6eScindi case T_RSHIFT: 1757aec1d6eScindi case T_LIST: 1767aec1d6eScindi case T_AND: 1777aec1d6eScindi case T_OR: 1787aec1d6eScindi case T_NOT: 1797aec1d6eScindi case T_ADD: 1807aec1d6eScindi case T_SUB: 1817aec1d6eScindi case T_MUL: 1827aec1d6eScindi case T_DIV: 1837aec1d6eScindi case T_MOD: 1847aec1d6eScindi diff = iexpr_cmp(np1->u.expr.left, np2->u.expr.left); 1857aec1d6eScindi if (diff != 0) 1867aec1d6eScindi return (diff); 1877aec1d6eScindi return (iexpr_cmp(np1->u.expr.right, np2->u.expr.right)); 1887aec1d6eScindi 1897aec1d6eScindi case T_NAME: 1907aec1d6eScindi if (np2->u.name.s != np1->u.name.s) 1917aec1d6eScindi return (np2->u.name.s - np1->u.name.s); 1927aec1d6eScindi diff = iexpr_cmp(np1->u.name.child, np2->u.name.child); 1937aec1d6eScindi if (diff != 0) 1947aec1d6eScindi return (diff); 1957aec1d6eScindi return (iexpr_cmp(np1->u.name.next, np2->u.name.next)); 1967aec1d6eScindi 1977aec1d6eScindi case T_EVENT: 1987aec1d6eScindi diff = iexpr_cmp(np1->u.event.ename, np2->u.event.ename); 1997aec1d6eScindi if (diff != 0) 2007aec1d6eScindi return (diff); 2017aec1d6eScindi return (iexpr_cmp(np1->u.event.epname, np2->u.event.epname)); 2027aec1d6eScindi 2037aec1d6eScindi case T_FUNC: 2047aec1d6eScindi if (np1->u.func.s != np2->u.func.s) 2057aec1d6eScindi return (np2->u.func.s - np1->u.func.s); 2067aec1d6eScindi return (iexpr_cmp(np1->u.func.arglist, np2->u.func.arglist)); 2077aec1d6eScindi 2087aec1d6eScindi case T_QUOTE: 2097aec1d6eScindi return (np2->u.quote.s - np1->u.quote.s); 2107aec1d6eScindi 2117aec1d6eScindi case T_NUM: 212*b7d3956bSstephh case T_TIMEVAL: 2137aec1d6eScindi if (np2->u.ull > np1->u.ull) 2147aec1d6eScindi return (1); 2157aec1d6eScindi else if (np1->u.ull > np2->u.ull) 2167aec1d6eScindi return (-1); 2177aec1d6eScindi else 2187aec1d6eScindi return (0); 2197aec1d6eScindi 2207aec1d6eScindi default: 2217aec1d6eScindi outfl(O_DIE, np1->file, np1->line, 2227aec1d6eScindi "iexpr_cmp: unexpected node type: %s", 2237aec1d6eScindi ptree_nodetype2str(np1->t)); 2247aec1d6eScindi } 2257aec1d6eScindi /*NOTREACHED*/ 22680ab886dSwesolows return (0); 2277aec1d6eScindi } 2287aec1d6eScindi 2297aec1d6eScindi /* 2307aec1d6eScindi * iexpr -- find instanced expr in cache, or add it if necessary 2317aec1d6eScindi */ 2327aec1d6eScindi struct node * 2337aec1d6eScindi iexpr(struct node *np) 2347aec1d6eScindi { 2357aec1d6eScindi unsigned idx = iexpr_hash(np) % IEXPRSZ; 2367aec1d6eScindi struct iexpr *bucketp = Cache[idx]; 2377aec1d6eScindi struct iexpr *cp; 2387aec1d6eScindi 2397aec1d6eScindi /* search cache */ 2407aec1d6eScindi for (cp = bucketp; cp != NULL; cp = cp->next) 2417aec1d6eScindi if (iexpr_cmp(cp->np, np) == 0) { 2427aec1d6eScindi /* found it */ 2437aec1d6eScindi tree_free(np); 24400d0963fSdilpreet cp->count++; 2457aec1d6eScindi return (cp->np); 2467aec1d6eScindi } 2477aec1d6eScindi 2487aec1d6eScindi /* allocate new cache entry */ 2497aec1d6eScindi cp = MALLOC(sizeof (*cp)); 2507aec1d6eScindi cp->np = np; 2517aec1d6eScindi cp->next = bucketp; 25200d0963fSdilpreet cp->count = 1; 2537aec1d6eScindi Cache[idx] = cp; 2547aec1d6eScindi 2557aec1d6eScindi stats_counter_bump(Niexpr); 2567aec1d6eScindi 2577aec1d6eScindi return (np); 2587aec1d6eScindi } 2597aec1d6eScindi 26000d0963fSdilpreet void 26100d0963fSdilpreet iexpr_free(struct node *np) 26200d0963fSdilpreet { 26300d0963fSdilpreet unsigned idx = iexpr_hash(np) % IEXPRSZ; 26400d0963fSdilpreet struct iexpr *cp; 26500d0963fSdilpreet struct iexpr *prevcp = NULL; 26600d0963fSdilpreet 26700d0963fSdilpreet /* search cache */ 26800d0963fSdilpreet for (cp = Cache[idx]; cp != NULL; cp = cp->next) { 26900d0963fSdilpreet if (iexpr_cmp(cp->np, np) == 0) { 27000d0963fSdilpreet /* found it */ 27100d0963fSdilpreet cp->count--; 27200d0963fSdilpreet if (cp->count == 0) { 27300d0963fSdilpreet tree_free(cp->np); 27400d0963fSdilpreet if (prevcp == NULL) 27500d0963fSdilpreet Cache[idx] = cp->next; 27600d0963fSdilpreet else 27700d0963fSdilpreet prevcp->next = cp->next; 27800d0963fSdilpreet FREE(cp); 27900d0963fSdilpreet } 28000d0963fSdilpreet return; 28100d0963fSdilpreet } 28200d0963fSdilpreet prevcp = cp; 28300d0963fSdilpreet } 28400d0963fSdilpreet } 28500d0963fSdilpreet 2867aec1d6eScindi /* 2877aec1d6eScindi * iexpr_cached -- return true if np is in the iexpr cache 2887aec1d6eScindi */ 2897aec1d6eScindi int 2907aec1d6eScindi iexpr_cached(struct node *np) 2917aec1d6eScindi { 2927aec1d6eScindi struct iexpr *cp = Cache[iexpr_hash(np) % IEXPRSZ]; 2937aec1d6eScindi 2947aec1d6eScindi /* search cache */ 2957aec1d6eScindi for (; cp != NULL; cp = cp->next) 2967aec1d6eScindi if (iexpr_cmp(cp->np, np) == 0) { 2977aec1d6eScindi /* found it */ 2987aec1d6eScindi return (1); 2997aec1d6eScindi } 3007aec1d6eScindi 3017aec1d6eScindi return (0); 3027aec1d6eScindi } 3037aec1d6eScindi 3047aec1d6eScindi /* 3057aec1d6eScindi * iexpr_fini -- free the iexpr cache 3067aec1d6eScindi */ 3077aec1d6eScindi void 3087aec1d6eScindi iexpr_fini(void) 3097aec1d6eScindi { 3107aec1d6eScindi int i; 3117aec1d6eScindi 3127aec1d6eScindi for (i = 0; i < IEXPRSZ; i++) { 3137aec1d6eScindi struct iexpr *cp; 3147aec1d6eScindi struct iexpr *ncp; 3157aec1d6eScindi 3167aec1d6eScindi for (cp = Cache[i]; cp != NULL; cp = ncp) { 3177aec1d6eScindi tree_free(cp->np); 3187aec1d6eScindi ncp = cp->next; 3197aec1d6eScindi FREE(cp); 3207aec1d6eScindi } 3217aec1d6eScindi Cache[i] = NULL; 3227aec1d6eScindi } 3237aec1d6eScindi } 324