compiler/purify/src/hash.c

   1 #include <stdio.h>
   2 #include <assert.h>
   3 #include <limits.h>
   4 #include "hash.h"
   5 #include "util.h"
   6 #include "error.h"
   7 #include "memory.h"
   8 #include "debug.h"
   9
  10 MemHashTable memHash;
  11 MemHash * Purify_LastNode;
  12
  13 #define CalcHash(addr) \
  14     ({ unsigned long x; \
  15         x = (long)(addr); \
  16         x >>= 16; \
  17         ((x & 0xFF) ^ (x >> 8)) & 0xFF; \
  18     })
  19
  20 MemHash * Purify_AddMemory (void * memory, int size, int flag, int type)
  21 {
  22     MemHash * node = xmalloc (sizeof (MemHash));
  23     int hashcode;
  24
  25     node->mem   = memory;
  26     node->flags = xmalloc (size);
  27     node->size  = size;
  28     node->type  = type;
  29     node->data  = NULL;
  30
  31     if (flag != -1)
  32         Purify_SetMemoryFlags (node, 0, size, flag);
  33
  34     hashcode = CalcHash (memory);
  35
  36     node->next = memHash[hashcode];
  37     memHash[hashcode] = node;
  38
  39     return node;
  40 }
  41
  42 void Purify_RemMemory (const void * mem)
  43 {
  44     int hashcode = CalcHash (mem);
  45     MemHash * node = (MemHash *)&memHash[hashcode], * next;
  46
  47 #if LDEBUG
  48     printf ("Purify_FindMemory (mem=%p)\n", mem);
  49 #endif
  50
  51     for ( ; (next=node->next); node=next)
  52     {
  53 #if LDEBUG
  54         printf ("    Checking against %p:%d (%p)\n",
  55             node->mem, node->size, node->mem+node->size);
  56 #endif
  57         if (next->mem <= mem && next->mem+next->size > mem)
  58         {
  59 #if LDEBUG
  60             printf ("    Node found\n");
  61 #endif
  62             node->next = next->next;
  63             xfree (next);
  64             if (Purify_LastNode == next)
  65                 Purify_LastNode = NULL;
  66             return;
  67         }
  68     }
  69
  70 #if LDEBUG
  71     printf ("    Nothing found\n");
  72 #endif
  73 }
  74
  75
  76 void Purify_SetMemoryFlags (MemHash * mem, int offset, int size, int flag)
  77 {
  78     char * ptr;
  79
  80 #if 0
  81     printf ("SetMemoryFlags (hash=%p, offset=%d, size=%d, flag=%d)\n",
  82         mem, offset, size, flag
  83     );
  84 #endif
  85
  86     passert (offset+size <= mem->size);
  87
  88     ptr = mem->flags + offset;
  89
  90     while (size--)
  91         *ptr ++ = flag;
  92 }
  93
  94 void Purify_ModifyMemoryFlags (MemHash * mem, int offset, int size, int flag,
  95     int mask)
  96 {
  97     char * ptr;
  98
  99     passert (offset+size <= mem->size);
 100
 101     ptr = mem->flags + offset;
 102
 103     flag &= mask;
 104     mask = ~mask;
 105
 106     while (size--)
 107     {
 108         *ptr = (*ptr & mask) | flag;
 109         ptr ++;
 110     }
 111 }
 112
 113 #undef LDEBUG
 114 #define LDEBUG 0
 115
 116 MemHash * Purify_FindMemory (const void * mem)
 117 {
 118     int hashcode = CalcHash (mem);
 119     MemHash * node = memHash[hashcode];
 120
 121 #if LDEBUG
 122     printf ("Purify_FindMemory (mem=%p)\n", mem);
 123 #endif
 124
 125     for ( ; node; node=node->next)
 126     {
 127 #if LDEBUG
 128         printf ("    Checking against %p:%d (%p)\n",
 129             node->mem, node->size, node->mem+node->size);
 130 #endif
 131         if (node->mem <= mem && node->mem+node->size > mem)
 132         {
 133             Purify_LastNode = node;
 134 #if LDEBUG
 135             printf ("    Node found\n");
 136 #endif
 137             return node;
 138         }
 139     }
 140
 141     Purify_LastNode = NULL;
 142     Purify_Error = NotOwnMemory;
 143
 144 #if LDEBUG
 145     printf ("    Nothing found\n");
 146 #endif
 147     return NULL;
 148 }
 149
 150 int Purify_CheckMemoryAccess (const void * mem, int size, int access)
 151 {
 152     MemHash * node = Purify_FindMemory (mem);
 153     long offset, cnt;
 154     char * ptr;
 155
 156     if (!node)
 157         return 0;
 158
 159     offset = (long)mem - (long)node->mem;
 160
 161     if (offset+size > node->size)
 162     {
 163         Purify_Error = BorderAccess;
 164         return 0;
 165     }
 166
 167     ptr = node->flags + offset;
 168
 169     if (access == PURIFY_MemAccess_Read)
 170     {
 171         cnt = size;
 172         while (cnt--)
 173         {
 174             if (!(*ptr & PURIFY_MemFlag_Readable) )
 175             {
 176                 if (*ptr & PURIFY_MemFlag_Free)
 177                 {
 178                     Purify_Error = (node->type == PURIFY_MemType_Stack)
 179                         ? FreeStackRead : FreeRead;
 180                     return 0;
 181                 }
 182                 else if (*ptr & PURIFY_MemFlag_Empty)
 183                 {
 184                     Purify_Error = UndefRead;
 185                     return 0;
 186                 }
 187                 else
 188                 {
 189                     Purify_Error = IllRead;
 190                     return 0;
 191                 }
 192             }
 193
 194             ptr ++;
 195         }
 196     }
 197     else /* write */
 198     {
 199         if (node->type == PURIFY_MemType_Code)
 200         {
 201             Purify_Error = CodeWrite;
 202             return 0;
 203         }
 204
 205         cnt=size;
 206         while (cnt--)
 207         {
 208             if (!(*ptr & PURIFY_MemFlag_Writable) )
 209             {
 210                 if (*ptr & PURIFY_MemFlag_Free)
 211                 {
 212                     Purify_Error =
 213                         (node->type == PURIFY_MemType_Stack)
 214                             ? FreeStackWrite
 215                             : FreeWrite;
 216                     return 0;
 217                 }
 218                 else
 219                 {
 220                     Purify_Error = IllWrite;
 221                     return 0;
 222                 }
 223             }
 224
 225             ptr ++;
 226         }
 227
 228         Purify_ModifyMemoryFlags (node, offset, size,
 229             PURIFY_MemFlag_Readable,
 230             PURIFY_MemFlag_Readable|PURIFY_MemFlag_Empty
 231         );
 232     }
 233
 234     return 1;
 235 }
 236
 237 void Purify_PrintMemory (void)
 238 {
 239     MemHash * node;
 240     int i;
 241 #if 0
 242     int t, cnt;
 243 #endif
 244
 245     for (i=0; i<256; i++)
 246     {
 247         if ((node = memHash[i]))
 248         {
 249             printf ("Hashline %3d:\n", i);
 250
 251             for ( ;
 252                 node;
 253                 node=node->next
 254             )
 255             {
 256                 printf ("    Node %p: Memory=%p Size=%d Type=",
 257                     node,
 258                     node->mem,
 259                     node->size
 260                 );
 261
 262                 switch (node->type)
 263                 {
 264                 case PURIFY_MemType_Heap:  printf ("heap "); break;
 265                 case PURIFY_MemType_Stack: printf ("stack"); break;
 266                 case PURIFY_MemType_Code:  printf ("code "); break;
 267                 case PURIFY_MemType_Data:  printf ("data "); break;
 268                 }
 269
 270                 if (node->data)
 271                 {
 272                     switch (node->type)
 273                     {
 274                     case PURIFY_MemType_Stack:
 275                     case PURIFY_MemType_Code:
 276                     case PURIFY_MemType_Data:
 277                         printf (" name=\"%s\"", (char *)node->data);
 278                         break;
 279
 280                     case PURIFY_MemType_Heap:
 281                         {
 282                             PMemoryNode * mem = (PMemoryNode *)(node->data);
 283
 284                             printf (" %s()", mem->alloc.current.functionname);
 285                         }
 286                         break;
 287                     }
 288                 }
 289
 290                 putchar ('\n');
 291
 292 #if 0
 293 #define WIDTH   56
 294
 295                 for (cnt=0,t=0; t<node->size; t++,cnt++)
 296                 {
 297                     if (cnt == 0)
 298                         printf ("\t%4d: ", t);
 299
 300                     printf ("%x", node->flags[t]);
 301
 302                     if (cnt == WIDTH-1)
 303                     {
 304                         putchar ('\n');
 305                         cnt = -1;
 306                     }
 307                     else if ((cnt & 7) == 7)
 308                         putchar (' ');
 309                 }
 310
 311                 if (((t-1) & WIDTH) != WIDTH-1)
 312                     putchar ('\n');
 313 #endif
 314             }
 315         }
 316     }
 317 }
 318
 319 #ifndef ABS
 320 #   define ABS(x)       (((x) < 0) ? -(x) : (x))
 321 #endif
 322
 323 MemHash * Purify_FindNextMemory (const void * mem, int * offsetptr)
 324 {
 325     MemHash * node, * next;
 326     int i, offset, o;
 327
 328     next = NULL;
 329     offset = INT_MAX;
 330
 331     for (i=0; i<256; i++)
 332     {
 333         for (node = memHash[i];
 334             node;
 335             node=node->next
 336         )
 337         {
 338             o = (long)mem - (long)node->mem;
 339
 340             if (o > 0)
 341             {
 342                 if (o < node->size)
 343                 {
 344                     *offsetptr = o;
 345                     return node;
 346                 }
 347                 else
 348                 {
 349                     o -= node->size;
 350                 }
 351             }
 352
 353             if (ABS(o) < ABS(offset)
 354                 || (ABS(o) == ABS(offset) && o > 0)
 355             )
 356             {
 357                 offset = o;
 358                 next = node;
 359             }
 360         }
 361     }
 362
 363     *offsetptr = offset;
 364     return next;
 365 }