src/dispatcher.c

   1 /* Dispatch signal to right virtual memory area.
   2    Copyright (C) 1993-1999, 2002-2003  Bruno Haible <bruno@clisp.org>
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  17
  18 #include "sigsegv.h"
  19
  20 #include <stddef.h> /* needed for NULL on SunOS4 */
  21 #include <stdlib.h>
  22 #ifdef _WIN32
  23 #include <malloc.h>
  24 #endif
  25
  26 /*
  27  * A dispatcher contains an AVL tree of non-empty intervals, sorted according
  28  * to their starting address.
  29  */
  30 typedef
  31 struct node_t
  32 {
  33   /* AVL tree management.  */
  34   struct node_t *left;
  35   struct node_t *right;
  36   unsigned int height;
  37   /* Representation of interval.  */
  38   unsigned long address;
  39   unsigned long len;
  40   /* User handler.  */
  41   sigsegv_area_handler_t handler;
  42   void *handler_arg;
  43 }
  44 node_t;
  45
  46 #define empty  ((node_t *) 0)
  47 #define heightof(tree)  ((tree) == empty ? 0 : (tree)->height)
  48 #define MAXHEIGHT  41
  49
  50 static void
  51 rebalance (node_t ***nodeplaces_ptr, unsigned int count)
  52 {
  53   if (count > 0)
  54     do
  55       {
  56         node_t **nodeplace = *--nodeplaces_ptr;
  57         node_t *node = *nodeplace;
  58         node_t *nodeleft = node->left;
  59         node_t *noderight = node->right;
  60         unsigned int heightleft = heightof (nodeleft);
  61         unsigned int heightright = heightof (noderight);
  62         if (heightright + 1 < heightleft)
  63           {
  64             node_t *nodeleftleft = nodeleft->left;
  65             node_t *nodeleftright = nodeleft->right;
  66             unsigned int heightleftright = heightof (nodeleftright);
  67             if (heightof (nodeleftleft) >= heightleftright)
  68               {
  69                 node->left = nodeleftright; nodeleft->right = node;
  70                 nodeleft->height = 1 + (node->height = 1 + heightleftright);
  71                 *nodeplace = nodeleft;
  72               }
  73             else
  74               {
  75                 nodeleft->right = nodeleftright->left;
  76                 node->left = nodeleftright->right;
  77                 nodeleftright->left = nodeleft;
  78                 nodeleftright->right = node;
  79                 nodeleft->height = node->height = heightleftright;
  80                 nodeleftright->height = heightleft;
  81                 *nodeplace = nodeleftright;
  82               }
  83           }
  84         else if (heightleft + 1 < heightright)
  85           {
  86             node_t *noderightright = noderight->right;
  87             node_t *noderightleft = noderight->left;
  88             unsigned int heightrightleft = heightof (noderightleft);
  89             if (heightof (noderightright) >= heightrightleft)
  90               {
  91                 node->right = noderightleft; noderight->left = node;
  92                 noderight->height = 1 + (node->height = 1 + heightrightleft);
  93                 *nodeplace = noderight;
  94               }
  95             else
  96               {
  97                 noderight->left = noderightleft->right;
  98                 node->right = noderightleft->left;
  99                 noderightleft->right = noderight;
 100                 noderightleft->left = node;
 101                 noderight->height = node->height = heightrightleft;
 102                 noderightleft->height = heightright;
 103                 *nodeplace = noderightleft;
 104               }
 105           }
 106         else
 107           {
 108             unsigned int height =
 109               (heightleft<heightright ? heightright : heightleft) + 1;
 110             if (height == node->height)
 111               break;
 112             node->height = height;
 113           }
 114       }
 115     while (--count > 0);
 116 }
 117
 118 static node_t *
 119 insert (node_t *new_node, node_t *tree)
 120 {
 121   unsigned long key = new_node->address;
 122   node_t **nodeplace = &tree;
 123   node_t **stack[MAXHEIGHT];
 124   unsigned int stack_count = 0;
 125   node_t ***stack_ptr = &stack[0];
 126   for (;;)
 127     {
 128       node_t *node = *nodeplace;
 129       if (node == empty)
 130         break;
 131       *stack_ptr++ = nodeplace; stack_count++;
 132       if (key < node->address)
 133         nodeplace = &node->left;
 134       else
 135         nodeplace = &node->right;
 136     }
 137   new_node->left = empty;
 138   new_node->right = empty;
 139   new_node->height = 1;
 140   *nodeplace = new_node;
 141   rebalance (stack_ptr, stack_count);
 142   return tree;
 143 }
 144
 145 static node_t *
 146 delete (node_t *node_to_delete, node_t *tree)
 147 {
 148   unsigned long key = node_to_delete->address;
 149   node_t **nodeplace = &tree;
 150   node_t **stack[MAXHEIGHT];
 151   unsigned int stack_count = 0;
 152   node_t ***stack_ptr = &stack[0];
 153   for (;;)
 154     {
 155       node_t *node = *nodeplace;
 156       if (node == empty)
 157         return tree;
 158       *stack_ptr++ = nodeplace; stack_count++;
 159       if (key == node->address)
 160         {
 161           if (node != node_to_delete)
 162             abort ();
 163           break;
 164         }
 165       if (key < node->address)
 166         nodeplace = &node->left;
 167       else
 168         nodeplace = &node->right;
 169     }
 170   {
 171     node_t **nodeplace_to_delete = nodeplace;
 172     if (node_to_delete->left == empty)
 173       {
 174         *nodeplace_to_delete = node_to_delete->right;
 175         stack_ptr--; stack_count--;
 176       }
 177     else
 178       {
 179         node_t ***stack_ptr_to_delete = stack_ptr;
 180         node_t **nodeplace = &node_to_delete->left;
 181         node_t *node;
 182         for (;;)
 183           {
 184             node = *nodeplace;
 185             if (node->right == empty)
 186               break;
 187             *stack_ptr++ = nodeplace; stack_count++;
 188             nodeplace = &node->right;
 189           }
 190         *nodeplace = node->left;
 191         node->left = node_to_delete->left;
 192         node->right = node_to_delete->right;
 193         node->height = node_to_delete->height;
 194         *nodeplace_to_delete = node;
 195         *stack_ptr_to_delete = &node->left;
 196       }
 197   }
 198   rebalance (stack_ptr, stack_count);
 199   return tree;
 200 }
 201
 202 void
 203 sigsegv_init (sigsegv_dispatcher *dispatcher)
 204 {
 205   dispatcher->tree = empty;
 206 }
 207
 208 void *
 209 sigsegv_register (sigsegv_dispatcher *dispatcher,
 210                   void *address, unsigned long len,
 211                   sigsegv_area_handler_t handler, void *handler_arg)
 212 {
 213   if (len == 0)
 214     return NULL;
 215   else
 216     {
 217       node_t *new_node = (node_t *) malloc (sizeof (node_t));
 218       new_node->address = (unsigned long) address;
 219       new_node->len = len;
 220       new_node->handler = handler;
 221       new_node->handler_arg = handler_arg;
 222       dispatcher->tree = insert (new_node, (node_t *) dispatcher->tree);
 223       return new_node;
 224     }
 225 }
 226
 227 void
 228 sigsegv_unregister (sigsegv_dispatcher *dispatcher, void *ticket)
 229 {
 230   if (ticket != NULL)
 231     {
 232       node_t *node_to_delete = (node_t *) ticket;
 233       dispatcher->tree = delete (node_to_delete, (node_t *) dispatcher->tree);
 234       free (node_to_delete);
 235     }
 236 }
 237
 238 int
 239 sigsegv_dispatch (sigsegv_dispatcher *dispatcher, void *fault_address)
 240 {
 241   unsigned long key = (unsigned long) fault_address;
 242   node_t *tree = (node_t *) dispatcher->tree;
 243   for (;;)
 244     {
 245       if (tree == empty)
 246         return 0;
 247       if (key < tree->address)
 248         tree = tree->left;
 249       else if (key - tree->address >= tree->len)
 250         tree = tree->right;
 251       else
 252         break;
 253     }
 254   return (*tree->handler) (fault_address, tree->handler_arg);
 255 }