GitLab

at 2024-02-16T09:40:50-08:00

Implement algorithm from Carl in the comments

A pretty straightforward implementation of the algorithm from
@cshapiro without having to allocate an array.

Clarify and clean up some comments.

 }

-#if 0

 static void

-update_static_vector_list(lispobj value, lispobj* vectors_to_free, int* num_static_vectors)

+scan_static_vectors(void)

 {

+    struct weak_pointer *wp;

+    struct weak_pointer *clearable_list = NULL;

+

+    printf("Phase 1: build clearable list\n");

+

     /*

-     * We have a static array with the mark cleared which means it's

-     * not used.

+     * Find weak pointers to unmarked static arrays, using a linked

+     * list.  We reuse the next slot ofthe weak pointer to chain these

+     * weak pointers together.

      *

-     * Only add it if we don't already have it.  We don't want

-     * duplicates because we'll end up trying to free things multiple

-     * times.

+     * Invariant: clearable_list only has weak pointers to unmarked

+     * static vectors.

      */

-    int m;

-    int found = 0;

-                        

-    for (m = 0; m < *num_static_vectors; ++m) {

-        if (value == vectors_to_free[m]) {

-            printf("Found %p at %d\n", (lispobj *) value, m);

-            found = 1;

-            break;

+    wp = weak_pointers;

+    while (wp) {

+	lispobj value = wp->value;

+        struct weak_pointer *next = wp->next;

+

+	if (Pointerp(value)) {

+            /* The value may be a static vector */

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

+

+            if (maybe_static_array_p(*header)

+                && (HeaderValue(*header) == 1)) {

+                printf("Adding %p header = 0x%08lx, next = %p\n",

+                       wp, *header, wp->next);

+                wp->next = clearable_list;

+                clearable_list = wp;

+            } else {

+                printf("Skipping %p header = 0x%08lx\n", wp, *header);

+            }

         }

+        wp = next;

     }

-    if (!found) {

-        printf("Adding %p at %d\n", (lispobj *) value, *num_static_vectors);

-        vectors_to_free[*num_static_vectors] = value;

-        ++*num_static_vectors;

-    }

-}

-#endif

-

-void

-scan_weak_pointers(void)

-{

-    struct weak_pointer *wp;

+    printf("Phase 2\n");

+    

     /*

-     * Array of weak pointers to unmarked static vectors that can be

-     * freed.

+     * clearable_list now points to all weak pointers to unmarked

+     * static vectors.  Go through the list.  If it's not marked, mark

+     * it.  If it's marked, break the weak pointer.

+     *

+     * Invariant: clearable_list contains only weak pointers that have

+     * been broken or that point to a unique dead static vector.

      */

-    struct weak_pointer **clearable_list;

+    for (wp = clearable_list; wp; wp = wp->next) {

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

-    /* Total number of weak pointers */

-    int num_weak_pointers = 0;

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

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

+        if (HeaderValue(*header) == 1) {

+            printf("  Mark vector\n");

+            *header |= 0x80000000;

+        } else {

+            printf("  Break weak pointer %p\n", wp);

+            wp->value = NIL;

+            wp->broken = T;

+        }

+    }

+

+    printf("Phase 3: Free static vectors\n");

-    /* Number of static vectors that we can free */

-    int num_static_vectors = 0;

-    int n;

-    

     /*

-     * Count the number of weak pointers so we can allocate enough

-     * space for clearable_list.

+     * Free up space.  Go through clearable_list and for each weak

+     * pointer that has not been broken, we can free the space.  Then

+     * break the weak pointer too, since the space has been freed.

      */

+    for (wp = clearable_list; wp; wp = wp->next) {

+        if (wp->broken == NIL) {

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

+            printf("free wp %p: %p\n", wp, static_array);

-    if (debug_static_array_p) {

-        printf("Phase 0\n");

-    }

-    

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

-        num_weak_pointers++;

-    }

+            wp->value = NIL;

+            wp->broken = T;

-    if (debug_static_array_p) {

-        printf("weak pointer count = %d\n", num_weak_pointers);

+            free(static_array);

+        }

     }

+}

-    /* Nothing to do if there are no weak pointers */

-    if (num_weak_pointers == 0) {

-        return;

-    }

-    

-    /*

-     * Allocate enough space to hold all weak pointers in case they

-     * all point to static vectors.

-     */

-    clearable_list = (struct weak_pointer **) malloc(num_weak_pointers * sizeof(struct weak_pointer *));

-    gc_assert(clearable_list);

+void

+scan_weak_pointers(void)

+{

+    struct weak_pointer *wp;

     /*

      * Now process the weak pointers.

      */

-    if (debug_static_array_p) {

-        printf("Phase 1\n");

-    }

+    printf("scan_weak_pointers...\n");

+    

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

 	lispobj value = wp->value;

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

+        printf("scan_weak: wp = %p value %p header 0x%08lx\n",

+               wp, (lispobj*) value, *first_pointer);

+

 	wp->mark_bit = NIL;

 	if (Pointerp(value)) {

             if (from_space_p(value)) {

                     wp->value = NIL;

                     wp->broken = T;

                 }

-            } else {

-                /* The value may be a static vector */

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

-

-                if (debug_static_array_p) {

-                    printf("wp %p: value %p, header = 0x%08lx\n",

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

-                }

-                

-                if (maybe_static_array_p(*header)) {

-                    /*

-                     * A header value of 1 means we have a static

-                     * vector with the in-use bit cleared, so we can

-                     * add this weak pointer to the clearable list.

-                     */

-                    if (HeaderValue(*header) == 1) {

-                        if (debug_static_array_p) {

-                            printf("  clearable_list[%d] = %p\n", num_static_vectors, wp);

-                        }

-

-                        clearable_list[num_static_vectors] = wp;

-                        ++num_static_vectors;

-                    }

-                }

-            }

-        }

-    }

-

-    /*

-     * At this point, clearable_list contains all the weak pointers to

-     * unmarked (unused) static vecotors.

-     *

-     * Traverse the clearable list.  If the weak pointer points to an

-     * unmarked static vector, mark it.  If it points to a marked

-     * static vector, then we know it shares a referent with another

-     * weak pointer.  Break this weak pointer and remove it from the

-     * clearable list by setting it to NIL.

-     */

-    if (debug_static_array_p) {

-        printf("Phase 2: %d pointers\n", num_static_vectors);

-    }

-

-    for (n = 0; n < num_static_vectors; ++n) {

-        struct weak_pointer *wp = clearable_list[n];

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

-

-        if (debug_static_array_p) {

-            printf("%2d: wp = %p, header = 0x%08lx\n", n, wp, *header);

-        }

-        

-        if (HeaderValue(*header) == 1) {

-            /*

-             * If the header value is 1, we have an unmarked static

-             * vector.  Mark it now.

-             */

-            if (debug_static_array_p) {

-                printf("  Mark vector\n");

-            }

-

-            *header |= 0x80000000;

-        } else {

-            /*

-             * We have a marked static vector.  Break this weak

-             * pointer and remove it from the list by setting it to

-             * NIL.

-             */

-            if (debug_static_array_p) {

-                printf("  Break weak pointer %p\n", wp);

-            }

-

-            wp->value = NIL;

-            wp->broken = T;

-            clearable_list[n] = NULL;

-        }

-    }

-

-    /*

-     * At this point, the clearable list is either NIL or a weak

-     * pointer that references a unique dead static vector.

-     *

-     * Traverse the clearable list skipping over any NIL entries.  For

-     * all other entries, free the static vector and break the weak

-     * pointer.

-     */

-

-    if (debug_static_array_p) {

-        printf("Phase 3: Free static vectors\n");

-    }

-    

-    for (n = 0; n < num_static_vectors; ++n) {

-        struct weak_pointer *wp = clearable_list[n];

-        if (wp != NULL) {

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

-

-            if (debug_static_array_p) {

-                printf("%2d: free wp %p: %p\n", n, (void*) wp, static_array);

             }

-

-            free(static_array);

-            wp->value = NIL;

-            wp->broken = T;

         }

     }

+    printf("scan_weak_pointers done\n");

-    free(clearable_list);

+    scan_static_vectors();

 }

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

Commits:

1 changed file:

Changes: