Plug garbage collectors

[KavinduZoysa]

In the LLVM GC documentation, it tells us about two types of GCs.

1. Conservative GC
2. Accurate GC

Since conservative GCs do not depend on language or the compiler we are focusing to plug conservative GCs into our implementation.

Here I have tried out Boehm collector which is a conservative GC. Based on the provided instructions we can simply build Boehm collector from the source and ran the following basic sample.

#include "gc.h"
#include <assert.h>
#include <stdio.h>

int main() {
  int i;
  int count = 10000;

  GC_INIT();
  for (i = 0; i < count; ++i) {
     int *p = (int *) GC_MALLOC(sizeof(int)); 
     if (i % (count/100) == 0) {
       printf("Heap size(GC_get_heap_size) = %d\n", GC_get_heap_size());
       printf("Heap size(GC_get_free_bytes) = %d\n", GC_get_free_bytes());
     }
   } 
  return 0;
}

These are the observations.

1. Heap size starts from 65536 and free size approximately equals that size.

Heap size(bytes)         = 65536
Free size in heap(bytes) = 61440
Heap size(bytes)         = 65536
Free size in heap(bytes) = 57344
Heap size(bytes)         = 65536
Free size in heap(bytes) = 53248
Heap size(bytes)         = 65536
Free size in heap(bytes) = 49152

2. Free size decreases and when it is zero, heap size is increased while heap is cleaned.

Heap size(bytes)         = 65536
Free size in heap(bytes) = 12288
Heap size(bytes)         = 65536
Free size in heap(bytes) = 4096
Heap size(bytes)         = 65536
Free size in heap(bytes) = 0
Heap size(bytes)         = 131072
Free size in heap(bytes) = 57344
Heap size(bytes)         = 131072
Free size in heap(bytes) = 53248

3. When the heap is filled, again it is cleaned.

Heap size(bytes)         = 131072
Free size in heap(bytes) = 4096
Heap size(bytes)         = 131072
Free size in heap(bytes) = 0
Heap size(bytes)         = 131072
Free size in heap(bytes) = 0
Heap size(bytes)         = 131072
Free size in heap(bytes) = 122880
Heap size(bytes)         = 131072
Free size in heap(bytes) = 114688

In the nim-lang, we can define the GC which is needed to use. Based on the argument provided, they choose the GC to use and call relevant methods in the GC using their FFI. Also, relevant libraries are dynamically linked. We can do the same to our implementation by declaring and calling relevant methods as needed.

Future steps ...

1. Check how to plug Boehm collector with our implementation.
2. Check the implementation of the Boehm collector and find a way to plug it with the new BValue representation.

[KavinduZoysa]

This is the LLVM IR for a single LLVM IR function.

; ModuleID = 'gc-test.c'
source_filename = "gc-test.c"
target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-pc-linux-gnu"

@.str = private unnamed_addr constant [10 x i8] c"gc-test.c\00", align 1

; Function Attrs: noinline nounwind optnone uwtable
define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i8*, align 8
  store i32 0, i32* %1, align 4
  call void @GC_init()
  %3 = call noalias i8* @GC_debug_malloc(i64 1, i8* getelementptr inbounds ([10 x i8], [10 x i8]* @.str, i64 0, i64 0), i32 14) #3
  store i8* %3, i8** %2, align 8
  ret i32 0
}

declare dso_local void @GC_init() #1

; Function Attrs: allocsize(0)
declare dso_local noalias i8* @GC_debug_malloc(i64, i8*, i32) #2

attributes #0 = { noinline nounwind optnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #1 = { "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #2 = { allocsize(0) "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }
attributes #3 = { allocsize(0) }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"Ubuntu clang version 11.1.0-++20210204122740+1fdec59bffc1-1~exp1~20210203233413.161"}

[KavinduZoysa]

Please follow https://github.com/KavinduZoysa/test-GCs/tree/master/boehm for the progress.

[KavinduZoysa]

Please check https://github.com/KavinduZoysa/test-GCs/tree/master/boehm/dealloc. This includes the test cases for deallocation.