A Hugo incarnation of the blog.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

runtime.c 7.3KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269
  1. #include <stdint.h>
  2. #include <assert.h>
  3. #include <memory.h>
  4. #include <stdio.h>
  5. #include "runtime.h"
  6. struct node_base* alloc_node() {
  7. struct node_base* new_node = malloc(sizeof(struct node_app));
  8. new_node->gc_next = NULL;
  9. new_node->gc_reachable = 0;
  10. assert(new_node != NULL);
  11. return new_node;
  12. }
  13. struct node_app* alloc_app(struct node_base* l, struct node_base* r) {
  14. struct node_app* node = (struct node_app*) alloc_node();
  15. node->base.tag = NODE_APP;
  16. node->left = l;
  17. node->right = r;
  18. return node;
  19. }
  20. struct node_num* alloc_num(int32_t n) {
  21. struct node_num* node = (struct node_num*) alloc_node();
  22. node->base.tag = NODE_NUM;
  23. node->value = n;
  24. return node;
  25. }
  26. struct node_global* alloc_global(void (*f)(struct gmachine*), int32_t a) {
  27. struct node_global* node = (struct node_global*) alloc_node();
  28. node->base.tag = NODE_GLOBAL;
  29. node->arity = a;
  30. node->function = f;
  31. return node;
  32. }
  33. struct node_ind* alloc_ind(struct node_base* n) {
  34. struct node_ind* node = (struct node_ind*) alloc_node();
  35. node->base.tag = NODE_IND;
  36. node->next = n;
  37. return node;
  38. }
  39. void free_node_direct(struct node_base* n) {
  40. if(n->tag == NODE_DATA) {
  41. free(((struct node_data*) n)->array);
  42. }
  43. }
  44. void gc_visit_node(struct node_base* n) {
  45. if(n->gc_reachable) return;
  46. n->gc_reachable = 1;
  47. if(n->tag == NODE_APP) {
  48. struct node_app* app = (struct node_app*) n;
  49. gc_visit_node(app->left);
  50. gc_visit_node(app->right);
  51. } if(n->tag == NODE_IND) {
  52. struct node_ind* ind = (struct node_ind*) n;
  53. gc_visit_node(ind->next);
  54. } if(n->tag == NODE_DATA) {
  55. struct node_data* data = (struct node_data*) n;
  56. struct node_base** to_visit = data->array;
  57. while(*to_visit) {
  58. gc_visit_node(*to_visit);
  59. to_visit++;
  60. }
  61. }
  62. }
  63. void stack_init(struct stack* s) {
  64. s->size = 4;
  65. s->count = 0;
  66. s->data = malloc(sizeof(*s->data) * s->size);
  67. assert(s->data != NULL);
  68. }
  69. void stack_free(struct stack* s) {
  70. free(s->data);
  71. }
  72. void stack_push(struct stack* s, struct node_base* n) {
  73. while(s->count >= s->size) {
  74. s->data = realloc(s->data, sizeof(*s->data) * (s->size *= 2));
  75. assert(s->data != NULL);
  76. }
  77. s->data[s->count++] = n;
  78. }
  79. struct node_base* stack_pop(struct stack* s) {
  80. assert(s->count > 0);
  81. return s->data[--s->count];
  82. }
  83. struct node_base* stack_peek(struct stack* s, size_t o) {
  84. assert(s->count > o);
  85. return s->data[s->count - o - 1];
  86. }
  87. void stack_popn(struct stack* s, size_t n) {
  88. assert(s->count >= n);
  89. s->count -= n;
  90. }
  91. void gmachine_init(struct gmachine* g) {
  92. stack_init(&g->stack);
  93. g->gc_nodes = NULL;
  94. g->gc_node_count = 0;
  95. g->gc_node_threshold = 128;
  96. }
  97. void gmachine_free(struct gmachine* g) {
  98. stack_free(&g->stack);
  99. struct node_base* to_free = g->gc_nodes;
  100. struct node_base* next;
  101. while(to_free) {
  102. next = to_free->gc_next;
  103. free_node_direct(to_free);
  104. free(to_free);
  105. to_free = next;
  106. }
  107. }
  108. void gmachine_slide(struct gmachine* g, size_t n) {
  109. assert(g->stack.count > n);
  110. g->stack.data[g->stack.count - n - 1] = g->stack.data[g->stack.count - 1];
  111. g->stack.count -= n;
  112. }
  113. void gmachine_update(struct gmachine* g, size_t o) {
  114. assert(g->stack.count > o + 1);
  115. struct node_ind* ind =
  116. (struct node_ind*) g->stack.data[g->stack.count - o - 2];
  117. ind->base.tag = NODE_IND;
  118. ind->next = g->stack.data[g->stack.count -= 1];
  119. }
  120. void gmachine_alloc(struct gmachine* g, size_t o) {
  121. while(o--) {
  122. stack_push(&g->stack,
  123. gmachine_track(g, (struct node_base*) alloc_ind(NULL)));
  124. }
  125. }
  126. void gmachine_pack(struct gmachine* g, size_t n, int8_t t) {
  127. assert(g->stack.count >= n);
  128. struct node_base** data = malloc(sizeof(*data) * (n + 1));
  129. assert(data != NULL);
  130. memcpy(data, &g->stack.data[g->stack.count - n], n * sizeof(*data));
  131. data[n] = NULL;
  132. struct node_data* new_node = (struct node_data*) alloc_node();
  133. new_node->array = data;
  134. new_node->base.tag = NODE_DATA;
  135. new_node->tag = t;
  136. stack_popn(&g->stack, n);
  137. stack_push(&g->stack, gmachine_track(g, (struct node_base*) new_node));
  138. }
  139. void gmachine_split(struct gmachine* g, size_t n) {
  140. struct node_data* node = (struct node_data*) stack_pop(&g->stack);
  141. for(size_t i = 0; i < n; i++) {
  142. stack_push(&g->stack, node->array[i]);
  143. }
  144. }
  145. struct node_base* gmachine_track(struct gmachine* g, struct node_base* b) {
  146. g->gc_node_count++;
  147. b->gc_next = g->gc_nodes;
  148. g->gc_nodes = b;
  149. if(g->gc_node_count >= g->gc_node_threshold) {
  150. uint64_t nodes_before = g->gc_node_count;
  151. gc_visit_node(b);
  152. gmachine_gc(g);
  153. g->gc_node_threshold = g->gc_node_count * 2;
  154. }
  155. return b;
  156. }
  157. void gmachine_gc(struct gmachine* g) {
  158. for(size_t i = 0; i < g->stack.count; i++) {
  159. gc_visit_node(g->stack.data[i]);
  160. }
  161. struct node_base** head_ptr = &g->gc_nodes;
  162. while(*head_ptr) {
  163. if((*head_ptr)->gc_reachable) {
  164. (*head_ptr)->gc_reachable = 0;
  165. head_ptr = &(*head_ptr)->gc_next;
  166. } else {
  167. struct node_base* to_free = *head_ptr;
  168. *head_ptr = to_free->gc_next;
  169. free_node_direct(to_free);
  170. free(to_free);
  171. g->gc_node_count--;
  172. }
  173. }
  174. }
  175. void unwind(struct gmachine* g) {
  176. struct stack* s = &g->stack;
  177. while(1) {
  178. struct node_base* peek = stack_peek(s, 0);
  179. if(peek->tag == NODE_APP) {
  180. struct node_app* n = (struct node_app*) peek;
  181. stack_push(s, n->left);
  182. } else if(peek->tag == NODE_GLOBAL) {
  183. struct node_global* n = (struct node_global*) peek;
  184. assert(s->count > n->arity);
  185. for(size_t i = 1; i <= n->arity; i++) {
  186. s->data[s->count - i]
  187. = ((struct node_app*) s->data[s->count - i - 1])->right;
  188. }
  189. n->function(g);
  190. } else if(peek->tag == NODE_IND) {
  191. struct node_ind* n = (struct node_ind*) peek;
  192. stack_pop(s);
  193. stack_push(s, n->next);
  194. } else {
  195. break;
  196. }
  197. }
  198. }
  199. extern void f_main(struct gmachine* s);
  200. void print_node(struct node_base* n) {
  201. if(n->tag == NODE_APP) {
  202. struct node_app* app = (struct node_app*) n;
  203. print_node(app->left);
  204. putchar(' ');
  205. print_node(app->right);
  206. } else if(n->tag == NODE_DATA) {
  207. printf("(Packed)");
  208. } else if(n->tag == NODE_GLOBAL) {
  209. struct node_global* global = (struct node_global*) n;
  210. printf("(Global: %p)", global->function);
  211. } else if(n->tag == NODE_IND) {
  212. print_node(((struct node_ind*) n)->next);
  213. } else if(n->tag == NODE_NUM) {
  214. struct node_num* num = (struct node_num*) n;
  215. printf("%d", num->value);
  216. }
  217. }
  218. int main(int argc, char** argv) {
  219. struct gmachine gmachine;
  220. struct node_global* first_node = alloc_global(f_main, 0);
  221. struct node_base* result;
  222. gmachine_init(&gmachine);
  223. gmachine_track(&gmachine, (struct node_base*) first_node);
  224. stack_push(&gmachine.stack, (struct node_base*) first_node);
  225. unwind(&gmachine);
  226. result = stack_pop(&gmachine.stack);
  227. printf("Result: ");
  228. print_node(result);
  229. putchar('\n');
  230. gmachine_free(&gmachine);
  231. }