repos / gcs.git

commit

60f2e3f

parent

60f2e3f

author

Evgenii Akentev

date

2024-09-10 12:55:53 +0400 +04

Add basic mark-sweep

1@@ -0,0 +1 @@
2+a.out

  1@@ -0,0 +1,172 @@
  2+#include <stdio.h>
  3+#include <stdlib.h>
  4+
  5+// To simplify things sizes are statically defined
  6+#define FIELDS_SIZE 4
  7+#define HEAP_SIZE 8
  8+#define ROOTS_SIZE 4
  9+#define WORKLIST_SIZE 100
 10+
 11+struct Object;
 12+
 13+typedef struct Object {
 14+  int val;
 15+  int field_size;
 16+  int isMarked;
 17+  struct Object* fields[FIELDS_SIZE];
 18+} Object;
 19+
 20+typedef struct {
 21+  int size;
 22+  Object** objects;
 23+} Heap;
 24+
 25+typedef struct {
 26+  int size;
 27+  Object* objects[ROOTS_SIZE];
 28+} Roots;
 29+
 30+typedef struct {
 31+  int current;
 32+  Object* objects[WORKLIST_SIZE];
 33+} Worklist;
 34+
 35+void push(Worklist* w, Object* o) {
 36+  w->current += 1;
 37+  w->objects[w->current] = o;
 38+}
 39+
 40+int isEmpty(Worklist *w) {
 41+  if (w->current == -1) return 1;
 42+
 43+  return 0;
 44+}
 45+
 46+Object* pop(Worklist *w) {
 47+  Object* item = w->objects[w->current];
 48+  w->current -= 1;
 49+  return item;
 50+}
 51+
 52+Heap* mkHeap () {
 53+  Heap* h = malloc(sizeof(Heap));
 54+  h->size = HEAP_SIZE;
 55+  h->objects = calloc(h->size, sizeof(Object*));
 56+  return h;
 57+}
 58+
 59+int heapObjectsNumber(Heap* h) {
 60+  int c = 0;
 61+  for (int i = 0; i < h->size; i++) {
 62+    if (h->objects[i] != NULL) c++;
 63+  }
 64+  return c;
 65+}
 66+
 67+void freeHeap (Heap* h) {
 68+  for (int i = 0; i < h->size; i++) {
 69+    if (h->objects[i] != NULL) {
 70+      free(h->objects[i]);
 71+    }
 72+  }
 73+  free(h->objects);
 74+  free(h);
 75+}
 76+
 77+Object* allocate(int val, Heap* h) {
 78+  Object* p = NULL;
 79+  for (int i = 0; i < h->size; i++) {
 80+    if (h->objects[i] == NULL && p == NULL) {
 81+      p = malloc(sizeof(Object));
 82+      *p = (Object){val, FIELDS_SIZE, 0, NULL};
 83+      h->objects[i] = p;
 84+    }
 85+  }
 86+  return p;
 87+}
 88+
 89+void mark(Heap* h, Roots* roots, Worklist* w) {
 90+  while (isEmpty(w) == 0) {
 91+    Object *ref = pop(w);
 92+    for (int i = 0; i < ref->field_size; i++) {
 93+       Object* child = ref->fields[i];
 94+      if (child != NULL && child->isMarked != 1) {
 95+        child->isMarked = 1;
 96+        push(w, child);
 97+      }
 98+    }
 99+  }
100+}
101+
102+void markFromRoots(Heap* h, Roots* roots) {
103+  Worklist worklist;
104+  worklist.current = -1;
105+
106+  for (int i = 0; i < roots->size; i++) {
107+    Object* ref = roots->objects[i];
108+    if (ref != NULL && ref->isMarked != 1) {
109+      ref->isMarked = 1;
110+      push(&worklist, ref);
111+      mark(h, roots, &worklist);
112+    }
113+  }
114+}
115+
116+void sweep(Heap *h) {
117+  for (int i = 0; i < h->size; i++) {
118+    if (h->objects[i] != NULL) {
119+      if (h->objects[i]->isMarked == 1) {
120+        h->objects[i]->isMarked = 0; 
121+      } else {
122+        free(h->objects[i]);
123+        h->objects[i] = NULL;
124+      }
125+    }
126+  }
127+}
128+
129+void collect(Heap* h, Roots* roots) {
130+  markFromRoots(h, roots);
131+  sweep(h);
132+}
133+
134+Object* new(int val, Heap* h, Roots* roots) {
135+  Object* ref = allocate(val, h);
136+  if (ref == NULL) {
137+    printf("Running collect");
138+    collect(h, roots);
139+    ref = allocate(val, h);
140+    if (ref == NULL) {
141+      printf("Out of memory\n");
142+      exit(0);
143+    }
144+  }
145+  return ref;
146+}
147+
148+int main() {
149+  Heap* h = mkHeap();
150+  Roots roots;
151+  roots.size = ROOTS_SIZE;
152+  for (int i = 0; i < roots.size; i++) {
153+    roots.objects[i] = NULL;
154+  }
155+
156+  // mutator
157+  roots.objects[0] = new(7, h, &roots);
158+  roots.objects[0] = new(5, h, &roots);
159+
160+  roots.objects[0]->fields[0] = new(8, h, &roots);
161+
162+  printf("heap size before collect: %d\n", heapObjectsNumber(h));
163+  printf("heap third obj value: %d\n", h->objects[2]->val);
164+
165+  collect(h, &roots);
166+
167+  printf("heap second obj value: %d\n", h->objects[1]->val);
168+
169+  printf("heap size after collect: %d\n", heapObjectsNumber(h));
170+
171+  freeHeap(h);
172+  return 0;
173+}