Merge pull request #12172 from gasche/major_gc_PAGE_MASK

major_gc.c: avoid using a PAGE_MASK macro

1 files changed, 33 insertions, 21 deletions

diff --git a/runtime/major_gc.c b/runtime/major_gc.c
index 3ed9bba0a8..4adf49c8d8 100644
--- a/runtime/major_gc.c
+++ b/runtime/major_gc.c
@@ -44,14 +44,14 @@
 #define MARK_STACK_INIT_SIZE (1 << 12)
 
 /* The mark stack consists of two parts:
-   1. the stack - consisting of spans of fields that need to be marked, and
-   2. the compressed stack - consisting of entries (k, bitfield)
-      where the bitfield represents word offsets from k that need to
-      be marked.
+   1. the stack - a dynamic array of spans of fields that need to be marked, and
+   2. the compressed stack - a bitset of fields that need to be marked.
 
    The stack is bounded relative to the heap size. When the stack
    overflows the bound, then entries from the stack are compressed and
-   transferred into the compressed stack.
+   transferred into the compressed stack, expect for "large" entries,
+   spans of more than BITS_PER_WORD entries, that are more compactly
+   represented as spans and remain on the uncompressed stack.
 
    When the stack is empty, the compressed stack is processed.
    The compressed stack iterator marks the point up to which
@@ -939,10 +939,22 @@ again:
   return budget;
 }
 
-/* compressed mark stack */
-#define PAGE_MASK (~(uintnat)(BITS_PER_WORD-1))
-#define PTR_TO_PAGE(v) (((uintnat)(v)/sizeof(value)) & PAGE_MASK)
-#define PTR_TO_PAGE_OFFSET(v) ((((uintnat)(v)/sizeof(value)) & ~PAGE_MASK))
+/* Compressed mark stack
+
+   We use a bitset, implemented as a hashtable storing word-sized
+   integers (uintnat). Each integer represents a "chunk" of addresses
+   that may or may not be present in the stack.
+ */
+static const uintnat chunk_mask = ~(uintnat)(BITS_PER_WORD-1);
+static inline uintnat ptr_to_chunk(value *ptr) {
+  return ((uintnat)(ptr) / sizeof(value)) & chunk_mask;
+}
+static inline uintnat ptr_to_chunk_offset(value *ptr) {
+  return ((uintnat)(ptr) / sizeof(value)) & ~chunk_mask;
+}
+static inline value* chunk_and_offset_to_ptr(uintnat chunk, uintnat offset) {
+  return (value*)((chunk + offset) * sizeof(value));
+}
 
 /* mark until the budget runs out or marking is done */
 static intnat mark(intnat budget) {
@@ -950,12 +962,11 @@ static intnat mark(intnat budget) {
   while (budget > 0 && !domain_state->marking_done) {
     budget = do_some_marking(domain_state->mark_stack, budget);
     if (budget > 0) {
-      int i;
       struct mark_stack* mstk = domain_state->mark_stack;
       addrmap_iterator it = mstk->compressed_stack_iter;
       if (caml_addrmap_iter_ok(&mstk->compressed_stack, it)) {
-        uintnat k = caml_addrmap_iter_key(&mstk->compressed_stack, it);
-        value v = caml_addrmap_iter_value(&mstk->compressed_stack, it);
+        uintnat chunk = caml_addrmap_iter_key(&mstk->compressed_stack, it);
+        uintnat bitset = caml_addrmap_iter_value(&mstk->compressed_stack, it);
 
         /* NB: must update the iterator here, as possible that
            mark_slice_darken could lead to the mark stack being pruned
@@ -963,9 +974,9 @@ static intnat mark(intnat budget) {
         mstk->compressed_stack_iter =
                       caml_addrmap_next(&mstk->compressed_stack, it);
 
-        for(i=0; i<BITS_PER_WORD; i++) {
-          if(v & ((uintnat)1 << i)) {
-            value* p = (value*)((k + i)*sizeof(value));
+        for(int ofs=0; ofs<BITS_PER_WORD; ofs++) {
+          if(bitset & ((uintnat)1 << ofs)) {
+            value* p = chunk_and_offset_to_ptr(chunk, ofs);
             mark_slice_darken(domain_state->mark_stack, *p, &budget);
           }
         }
@@ -1756,19 +1767,20 @@ void caml_finish_sweeping (void)
   CAML_EV_END(EV_MAJOR_FINISH_SWEEPING);
 }
 
-Caml_inline int add_addr(struct addrmap* amap, value v) {
-  uintnat k = PTR_TO_PAGE(v);
-  uintnat flag = (uintnat)1 << PTR_TO_PAGE_OFFSET(v);
+Caml_inline int add_addr(struct addrmap* amap, value* ptr) {
+  uintnat chunk = ptr_to_chunk(ptr);
+  uintnat offset = ptr_to_chunk_offset(ptr);
+  uintnat flag = (uintnat)1 << offset;
   int new_entry = 0;
 
-  value* amap_pos = caml_addrmap_insert_pos(amap, k);
+  value* amap_pos = caml_addrmap_insert_pos(amap, chunk);
 
   if (*amap_pos == ADDRMAP_NOT_PRESENT) {
     new_entry = 1;
     *amap_pos = 0;
   }
 
-  CAMLassert(v == (value)((k + PTR_TO_PAGE_OFFSET(v))*sizeof(value)));
+  CAMLassert(ptr == chunk_and_offset_to_ptr(chunk, offset));
 
   if (!(*amap_pos & flag)) {
     *amap_pos |= flag;
@@ -1813,7 +1825,7 @@ static void mark_stack_prune(struct mark_stack* stk)
     } else {
       while(me.start < me.end) {
         compressed_entries += add_addr(&stk->compressed_stack,
-                                       (uintnat)me.start);
+                                       me.start);
         me.start++;
       }
     }