GitLab

at 2024-02-25T07:21:01-08:00

Apply review suggestions moving comments and renaming pop/push.

First cut at clearing the mark during phase 1

As suggested in
https://gitlab.common-lisp.net/cmucl/cmucl/-/merge_requests/188#note_13750
we can clear the mark bit and set the visited bit in phase 1.
However, this means that we can only add free (unmarked) static vectors which
also do not have the visited bit set.

Tests show that this works as expected.

Don't need inuse list anymore

Remove the inuse_list because the list of static vectors only contains
static vectors that can be freed.  Thus, update
`scan_static_vectors_2` to remove the bit of code checking for live
vectors and adding them to the inuse_list that no longer exists.

Remove unmark_static_vectors_in_use and inuse_static_vector_list

Since we don't need to keep track of the live vectors anymore, get rid
of the variable `inuse_static_vector_list` and the function
`unmark_static_vectors_in_use`.

Clear static vector visited bit when scavenging a weak pointer to it

When scavenging the weak pointer to a static vector, clear out the
visited bit to prevent confusion when scanning all the weak pointers.
This is needed because scanning causes use to unmark live vectors and
set the visited bit so we don't add other weak pointers to the now
unmarked (free) static vector.

Undo the change in `scav_static_vector` so we just the mark bit and
don't clear the visited bit.  That whould happen when we scavenge the
weak pointer.

Update some comments; slightly modify scan_static_vectors to use pop

 static int (*sizetab[256]) (lispobj * where);

 static struct weak_pointer *weak_pointers;

-static struct weak_pointer *inuse_static_vector_list;

 static struct scavenger_hook *scavenger_hooks = (struct scavenger_hook *) NIL;

 /* Like (ceiling x y), but y is constrained to be a power of two */

         int static_p;

         if (debug_static_array_p) {

-            fprintf(stderr, "Possible static vector at %p.  header = 0x%lx\n",

+            fprintf(stderr, "Possible static vector at %p.  header = 0x%08lx\n",

                     ptr, (unsigned long) header);

         }

              * setting the MSB of the header.  And clear out any

              * possible visited bit.

              */

-            *ptr = (header | STATIC_VECTOR_MARK_BIT) & ~STATIC_VECTOR_VISITED_BIT;

+            *ptr = (header | STATIC_VECTOR_MARK_BIT);

             if (debug_static_array_p) {

-                fprintf(stderr, "Scavenged static vector @%p, header = 0x%lx\n",

+                fprintf(stderr, "Scavenged static vector @%p, header = 0x%08lx\n",

                         ptr, (unsigned long) header);

             }

         }

     struct weak_pointer *this_wp = (struct weak_pointer *) where;

     if (this_wp->mark_bit == NIL) {

+        lispobj *header = (lispobj *) PTR(this_wp->value);

+        if (maybe_static_array_p(*header)) {

+            printf("Scavenge wp %p to static array %p header 0x%08lx\n",

+                   this_wp, (lispobj *) this_wp->value, *header);

+

+            *header &= ~STATIC_VECTOR_VISITED_BIT;

+        }

+

 	this_wp->mark_bit = T;

 	this_wp->next = weak_pointers;

 	weak_pointers = this_wp;

     return WEAK_POINTER_NWORDS;

 }

-static inline struct weak_pointer *

-pop(struct weak_pointer **list) 

+/*

+ * Pop the first element from the list `list`, updating `list`, like

+ * CL POP.

+ */

+static struct weak_pointer *

+pop_weak_pointer(struct weak_pointer **list) 

 {

-    /*

-     * Pop the first element from the list `list`, updating `list`, like CL POP.

-     */

     struct weak_pointer *wp = *list;

     *list = (*list)->next;

     return wp;

 }

-static inline void

-push(struct weak_pointer* wp, struct weak_pointer **list)

+/*

+ * Push wp to the head of the list, updating list, like CL PUSH.

+ */

+static void

+push_weak_pointer(struct weak_pointer* wp, struct weak_pointer **list)

 {

-    /*

-     * Push wp to the head of the list, updating list, like CL PUSH.

-     */

     wp->next = *list;

     *list = wp;

 }

 /*

- * Phase 2: Find the weak pointers to static vectors that are in use

- * and not in use.  The vectors that are in use are added to

- * inuse_list.  Those that are not in use are added to freeable_list.

- * Only unique vectors are added to freeable list; a duplicate has its

- * weak pointer to it broken.

+ * Phase 2: Process the list of weak pointers to unused static

+ * vectors.  We find the unique static vectors and add each

+ * corresponding weak pointer to freeable_list.  For the duplicates,

+ * the weak pointer is broken.

  */

 static void

 scan_static_vectors_2(struct weak_pointer *static_vector_list,

-                      struct weak_pointer **freeable_list,

-                      struct weak_pointer **inuse_list)

+                      struct weak_pointer **freeable_list)

 {

     DPRINTF(debug_static_array_p,

             (stdout, "Phase 2: Find unused and unused static vectors\n"));

         lispobj *header;

         /* Pop weak pointer from the list */

-        wp = pop(&static_vector_list);

+        wp = pop_weak_pointer(&static_vector_list);

         header = (lispobj *) PTR(wp->value);

         DPRINTF(debug_static_array_p,

                 (stdout, "  wp %p value %p header 0x%08lx\n",

                  wp, (lispobj *) wp->value, *header));

-        if ((*header & STATIC_VECTOR_MARK_BIT) != 0) {

-            /*

-             * Static vector is in use.  Add this to the in-use list.

-             */

+        /*

+         * If we haven't seen this vector before, set the visited flag

+         * and add it to freeable_list.  If we have visited this

+         * vector before, break the weak pointer.

+         */

+        if ((*header & STATIC_VECTOR_VISITED_BIT) == 0) {

             DPRINTF(debug_static_array_p,

-                    (stdout, "    In-use vector; add to in-use list\n"));

+                    (stdout, "    Visit unused vector, add to freeable list\n"));

-            push(wp, inuse_list);

+            *header |= STATIC_VECTOR_VISITED_BIT;

+            push_weak_pointer(wp, freeable_list);

         } else {

-            /*

-             * Static vector not in use.  If we haven't seen this

-             * vector before, set the visited flag and add it to

-             * freeable_list.  If we have visited this vector before,

-             * break the weak pointer.

-             */

-            if ((*header & STATIC_VECTOR_VISITED_BIT) == 0) {

-                DPRINTF(debug_static_array_p,

-                        (stdout, "    Visit unused vector, add to freeable list\n"));

-

-                *header |= STATIC_VECTOR_VISITED_BIT;

-                push(wp, freeable_list);

-            } else {

-                DPRINTF(debug_static_array_p,

-                        (stdout, "    Already visited unused vector; break weak pointer\n"));

+            DPRINTF(debug_static_array_p,

+                    (stdout, "    Already visited unused vector; break weak pointer\n"));

-                wp->value = NIL;

-                wp->broken = T;

-            }

+            wp->value = NIL;

+            wp->broken = T;

         }

     }

         lispobj *header = (lispobj *) PTR(wp->value);

         lispobj *static_array = (lispobj *) PTR(wp->value);

-        /*

-         * Invariant: weak pointer must not be broken

-         */

-        gc_assert(wp->broken == NIL);

-

         DPRINTF(debug_static_array_p,

                 (stdout, "  wp %p value %p header 0x%08lx\n",

                  wp, (lispobj*) wp->value, *header));

         /*

-         * Invariant: Mark bit must be clear

+         * Invariants: weak pointer must not be broken and the mark

+         * bit must be clear.

          */

+        gc_assert(wp->broken == NIL);

         gc_assert(((*header & STATIC_VECTOR_MARK_BIT) == 0));

         DPRINTF(debug_static_array_p,

             (stdout, "Phase 3 done\n"));

 }

-/*

- * Unmark all the vectors in inuse_list.  This needs to be called at

- * the end of GC to unmark any live static vectors so that for the

- * next GC we can tell if the static vector is used or not.

- * Otherwise, the vectors will always look as if they're in use

- * because the mark bit is never changed.

- */

-static void

-unmark_static_vectors_in_use(struct weak_pointer *inuse_list)

-{

-    struct weak_pointer *wp;

-

-    DPRINTF(debug_static_array_p,

-            (stdout, "Phase 4: unmark static vectors\n"));

-

-    for (wp = inuse_list; wp; wp = wp->next) {

-        lispobj *header = (lispobj *) PTR(wp->value);

-        /*

-         * Invariant: the weak pointer must not be broken.

-         *

-         * Note that we can't assert that the static vector is marked

-         * because we can have more than one weak pointer to the same

-         * static vector.

-         */

-        gc_assert(wp->broken == NIL);

-        

-        DPRINTF(debug_static_array_p,

-                (stdout, "  wp %p value %p broken %d header 0x%08lx\n",

-                 wp, (lispobj*) wp->value, wp->broken == T, *header));

-

-        /* Only clear if we haven't already */

-        if ((*header & STATIC_VECTOR_MARK_BIT) != 0) {

-            DPRINTF(debug_static_array_p,

-                    (stdout, "    Clearing mark bit\n"));

-

-            *header &= ~STATIC_VECTOR_MARK_BIT;

-        }

-    }

-

-    DPRINTF(debug_static_array_p,

-            (stdout, "Phase 4 done\n"));

-}

-

 static void

 scan_static_vectors(struct weak_pointer *static_vector_list)

 {

     struct weak_pointer *freeable_list = NULL;

     /*

-     * For each weak pointer, add it either the inuse list or the

-     * freeable list.

+     * For each weak pointer, either break it, or add it to the

+     * freeable list because it points to a unique static vector.

      */

-    inuse_static_vector_list = NULL;

-    scan_static_vectors_2(static_vector_list, &freeable_list, &inuse_static_vector_list);

+    scan_static_vectors_2(static_vector_list, &freeable_list);

     /* Free the unused unique static vectors. */

     scan_static_vectors_3(freeable_list);

      *

      * Also find any weak pointers to static vectors.  This

      * destructively modifies the next slot of the weak pointer to

-     * chain all the weak pointers to static vectors together.

+     * chain all the weak pointers to unused static vectors together.

      */

     DPRINTF(debug_static_array_p,

             (stdout, "Phase 1: Process weak pointers\n"));

-    while (wp) {

-        struct weak_pointer *next = wp->next;

-	lispobj value = wp->value;

-	lispobj *first_pointer = (lispobj *) PTR(value);

+    while (weak_pointers) {

+	lispobj value;

+	lispobj *first_pointer;

+

+        wp = pop_weak_pointer(&weak_pointers);

+	value = wp->value;

+	first_pointer = (lispobj *) PTR(value);

 	wp->mark_bit = NIL;

 	if (Pointerp(value)) {

                 }

             } else {

                 /* The value may be a static vector */

-                lispobj header = *(lispobj *) PTR(value);

-

-                if (maybe_static_array_p(header)) {

-

-                    DPRINTF(debug_static_array_p,

-                            (stdout, "  Add static vector:  wp %p value %p header 0x%08lx\n",

-                             wp, (lispobj *) wp->value, header));

-

-                    push(wp, &static_vector_list);

+                lispobj *header = (lispobj *) PTR(value);

+

+                if (maybe_static_array_p(*header)) {

+                    if (*header & STATIC_VECTOR_MARK_BIT) {

+                        DPRINTF(debug_static_array_p,

+                                (stdout, "  Update status bits for live vector: wp %p value %p header 0x%08lx\n",

+                                 wp, (lispobj *) wp->value, *header));

+                        *header = (*header & ~STATIC_VECTOR_MARK_BIT) | STATIC_VECTOR_VISITED_BIT;

+                    } else if ((*header & STATIC_VECTOR_VISITED_BIT) == 0) {

+                        /* Only add the vector if it is unmarked and has not been visited */

+                        DPRINTF(debug_static_array_p,

+                                (stdout, "  Add static vector:  wp %p value %p header 0x%08lx\n",

+                                 wp, (lispobj *) wp->value, *header));

+

+                        push_weak_pointer(wp, &static_vector_list);

+                    }

                 } else {

                     DPRINTF(debug_static_array_p,

                             (stdout, "  Skip: wp %p value %p header 0x%08lx\n",

-                             wp, (lispobj *) wp->value, header));

+                             wp, (lispobj *) wp->value, *header));

                 }

             }

         }

-        wp = next;

     }

     scan_static_vectors(static_vector_list);

 	}

 	scavenger_hooks = (struct scavenger_hook *) NIL;

     }

-

-    /*

-     * Unmark any live static vectors.  This needs to be done at the

-     * very end when all GCs are done, lest we accidentally free a

-     * static vector that was actually in use.

-     */

-    unmark_static_vectors_in_use(inuse_static_vector_list);

 }

Raymond Toy pushed to branch issue-243-weak-pointer-to-static-array at cmucl / cmucl

Commits:

1 changed file:

Changes: