Re: [perl #16278] [PATCH] Quicker pointer checking for stack walking

[Jason Gloudon]

On Sun, Aug 18, 2002 at 02:51:34AM +0000, Jason Gloudon wrote:
> # New Ticket Created by  Jason Gloudon 
> # Please include the string:  [perl #16278]
> # in the subject line of all future correspondence about this issue. 
> # <URL: http://rt.perl.org/rt2/Ticket/Display.html?id=16278 >

Moved the static prototype to dod.c

-- 
Jason

Index: dod.c
===================================================================
RCS file: /cvs/public/parrot/dod.c,v
retrieving revision 1.13
diff -u -r1.13 dod.c
--- dod.c       17 Aug 2002 01:11:08 -0000      1.13
+++ dod.c       18 Aug 2002 03:20:43 -0000
@@ -1,7 +1,7 @@
 /* dod.c 
  *  Copyright: (When this is determined...it will go here)
  *  CVS Info
- *     $Id: dod.c,v 1.13 2002/08/17 01:11:08 sfink Exp $
+ *     $Id: dod.c,v 1.12 2002/08/14 00:10:48 grunblatt Exp $
  *  Overview:
  *     Handles dead object destruction of the various headers
  *  Data Structure and Algorithms:
@@ -14,6 +14,8 @@
 
 #include "parrot/parrot.h"
 
+static size_t find_common_mask(size_t val1, size_t val2);
+
 PMC *
 mark_used(PMC *used_pmc, PMC *current_end_of_list)
 {
@@ -329,11 +331,32 @@
 }
 
 #ifndef PLATFORM_STACK_WALK
+
+/* Find a mask covering the longest common bit-prefix of val1 and val2 */
+static size_t
+find_common_mask(size_t val1, size_t val2){
+    int i, count;
+    int bound = sizeof(size_t) * 8;
+
+    for(i = 0; i < bound; i++){
+        if(val1 == val2){
+                return ~(size_t)0 << i;
+        }
+        val1 >>= 1;
+        val2 >>= 1;
+    }
+
+    internal_exception(INTERP_ERROR,
+                       "Unexpected condition in find_common_prefix()!\n");
+    return 0;
+}
+
 PMC*
 trace_system_stack(struct Parrot_Interp *interpreter, PMC *last)
 {
     size_t lo_var_ptr = (size_t)interpreter->lo_var_ptr;
     size_t hi_var_ptr = (size_t)&lo_var_ptr;
+    size_t prefix;
     ptrdiff_t cur_var_ptr;
     ptrdiff_t direction = (hi_var_ptr > lo_var_ptr) ? 1 : -1;
 
@@ -342,6 +365,12 @@
     size_t pmc_min = get_min_pmc_address(interpreter);
     size_t pmc_max = get_max_pmc_address(interpreter);
 
+    size_t mask = find_common_mask(buffer_min < pmc_min ? buffer_min: pmc_min,
+                buffer_max > pmc_max ? buffer_max : pmc_max);
+
+    /* Get the expected prefix */
+    prefix = mask & buffer_min;
+
     if (!lo_var_ptr)
         return last;
     
@@ -350,10 +379,14 @@
          cur_var_ptr = (size_t)( (ptrdiff_t)cur_var_ptr + direction * 
PARROT_PTR_ALIGNMENT )
          ) {
         size_t ptr = *(size_t *)cur_var_ptr;
-        if (pmc_min <= ptr && ptr < pmc_max && is_pmc_ptr(interpreter,(void *)ptr)) {
-            last = mark_used((PMC *)ptr, last);
-        } else if (buffer_min <= ptr && ptr < buffer_max && 
is_buffer_ptr(interpreter,(void *)ptr)) {
-            buffer_lives((Buffer *)ptr);
+
+        /* Do a quick approximate range check by bit-masking */
+        if((ptr & mask) == prefix){
+            if (pmc_min < ptr && ptr < pmc_max && is_pmc_ptr(interpreter,(void 
+*)ptr)) {
+                last = mark_used((PMC *)ptr, last);
+            } else if (buffer_min < ptr && ptr < buffer_max && 
+is_buffer_ptr(interpreter,(void *)ptr)) {
+                buffer_lives((Buffer *)ptr);
+            }
         }
     }
     return last;