usr/src/cmd/fm/modules/common/eversholt/iexpr.c

   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 }