8000 Merge pull request #1 from maxdjohnson/cs194_master · andrewmains12/ruby@036d641 · GitHub
[go: up one dir, main page]
65F7
Skip to content

Commit 036d641

Browse files
author
andrewmains12
committed
Merge pull request kevints#1 from maxdjohnson/cs194_master
Basic naive, single-threaded queue implementation. Slow.
2 parents b12a9cf + d9b05d1 commit 036d641

File tree

1 file changed

+98
-34
lines changed

1 file changed

+98
-34
lines changed

‎gc.c

Lines changed: 98 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -420,6 +420,26 @@ rb_objspace_alloc(void)
420420

421421
static void initial_expand_heap(rb_objspace_t *objspace);
422422

423+
424+
typedef struct mark_queue_node_struct mark_queue_node_t;
425+
struct mark_queue_node_struct {
426+
rb_objspace_t* objspace;
427+
VALUE ptr;
428+
int lev;
429+
mark_queue_node_t* next;
430+
};
431+
432+
typedef struct mark_queue_struct {
433+
mark_queue_node_t* head;
434+
mark_queue_node_t* tail;
435+
unsigned int size;
436+
} mark_queue_t;
437+
438+
mark_queue_t mark_queue = {NULL, NULL, 0};
439+
440+
void gc_mark_defer(rb_objspace_t *objspace, VALUE ptr, int lev);
441+
int gc_mark_pop();
442+
423443
void
424444
rb_gc_set_params(void)
425445
{
@@ -1419,7 +1439,7 @@ mark_locations_array(rb_objspace_t *objspace, register VALUE *x, register long n
14191439
v = *x;
14201440
VALGRIND_MAKE_MEM_DEFINED(&v, sizeof(v));
14211441
if (is_pointer_to_heap(objspace, (void *)v)) {
1422-
gc_mark(objspace, v, 0);
1442+
gc_mark_defer(objspace, v, 0);
14231443
}
14241444
x++;
14251445
}
@@ -1452,7 +1472,7 @@ static int
14521472
mark_entry(ID key, VALUE value, st_data_t data)
14531473
{
14541474
struct mark_tbl_arg *arg = (void*)data;
1455-
gc_mark(arg->objspace, value, arg->lev);
1475+
gc_mark_defer(arg->objspace, value, arg->lev);
14561476
return ST_CONTINUE;
14571477
}
14581478

@@ -1470,7 +1490,7 @@ static int
14701490
mark_key(VALUE key, VALUE value, st_data_t data)
14711491
{
14721492
struct mark_tbl_arg *arg = (void*)data;
1473-
gc_mark(arg->objspace, key, arg->lev);
1493+
gc_mark_defer(arg->objspace, key, arg->lev);
14741494
return ST_CONTINUE;
14751495
}
14761496

@@ -1494,8 +1514,8 @@ static int
14941514
mark_keyvalue(VALUE key, VALUE value, st_data_t data)
14951515
{
14961516
struct mark_tbl_arg *arg = (void*)data;
1497-
gc_mark(arg->objspace, key, arg->lev);
1498-
gc_mark(arg->objspace, value, arg->lev);
1517+
gc_mark_defer(arg->objspace, key, arg->lev);
1518+
gc_mark_defer(arg->objspace, value, arg->lev);
14991519
return ST_CONTINUE;
15001520
}
15011521

@@ -1520,18 +1540,18 @@ mark_method_entry(rb_objspace_t *objspace, const rb_method_entry_t *me, int lev)
15201540
{
15211541
const rb_method_definition_t *def = me->def;
15221542

1523-
gc_mark(objspace, me->klass, lev);
1543+
gc_mark_defer(objspace, me->klass, lev);
15241544
if (!def) return;
15251545
switch (def->type) {
15261546
case VM_METHOD_TYPE_ISEQ:
1527-
gc_mark(objspace, def->body.iseq->self, lev);
1547+
gc_mark_defer(objspace, def->body.iseq->self, lev);
15281548
break;
15291549
case VM_METHOD_TYPE_BMETHOD:
1530-
gc_mark(objspace, def->body.proc, lev);
1550+
gc_mark_defer(objspace, def->body.proc, lev);
15311551
break;
15321552
case VM_METHOD_TYPE_ATTRSET:
15331553
case VM_METHOD_TYPE_IVAR:
1534-
gc_mark(objspace, def->body.attr.location, lev);
1554+
gc_mark_defer(objspace, def->body.attr.location, lev);
15351555
break;
15361556
default:
15371557
break; /* ignore */
@@ -1580,7 +1600,7 @@ static int
15801600
mark_const_entry_i(ID key, const rb_const_entry_t *ce, st_data_t data)
15811601
{
15821602
struct mark_tbl_arg *arg = (void*)data;
1583-
gc_mark(arg->objspace, ce->value, arg->lev);
1603+
gc_mark_defer(arg->objspace, ce->value, arg->lev);
15841604
return ST_CONTINUE;
15851605
}
15861606

@@ -1618,7 +1638,7 @@ void
16181638
rb_gc_mark_maybe(VALUE obj)
16191639
{
16201640
if (is_pointer_to_heap(&rb_objspace, (void *)obj)) {
1621-
gc_mark(&rb_objspace, obj, 0);
1641+
gc_mark_defer(&rb_objspace, obj, 0);
16221642
}
16231643
}
16241644

@@ -1649,6 +1669,45 @@ gc_mark(rb_objspace_t *objspace, VALUE ptr, int lev)
16491669
gc_mark_children(objspace, ptr, lev+1);
16501670
}
16511671

1672+
void
1673+
gc_mark_defer(rb_objspace_t *objspace, VALUE ptr, int lev) {
1674+
mark_queue_node_t* node =
1675+
(mark_queue_node_t*) malloc(sizeof(mark_queue_node_t));
1676+
node->objspace = objspace;
1677+
node->ptr = ptr;
1678+
node->lev = lev;
1679+
node->next = NULL;
1680+
//lock
1681+
if (mark_queue.tail == NULL) {
1682+
mark_queue.head = mark_queue.tail = node;
1683+
} else {
1684+
mark_queue.tail->next = node;
1685+
mark_queue.tail = node;
1686+
}
1687+
mark_queue.size++;
1688+
//unlock
1689+
}
1690+
1691+
int
1692+
gc_mark_pop() {
1693+
mark_queue_node_t* node;
1694+
//lock
1695+
node = mark_queue.head;
1696+
if (node != NULL) {
1697+
mark_queue.head = node->next;
1698+
if (mark_queue.head == NULL) {
1699+
mark_queue.tail = NULL;
1700+
}
1701+
mark_queue.size--;
1702+
}
1703+
//unlock
1704+
if (node != NULL) {
1705+
gc_mark(node->objspace, node->ptr, node->lev);
1706+
free(node);
1707+
}
1708+
return node != NULL;
1709+
}
1710+
16521711
void
16531712
rb_gc_mark(VALUE ptr)
16541713
{
@@ -1692,7 +1751,7 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
16921751
case NODE_RESBODY:
16931752
case NODE_CLASS:
16941753
case NODE_BLOCK_PASS:
1695-
gc_mark(objspace, (VALUE)obj->as.node.u2.node, lev);
1754+
gc_mark_defer(objspace, (VALUE)obj->as.node.u2.node, lev);
16961755
/* fall through */
16971756
case NODE_BLOCK: /* 1,3 */
16981757
case NODE_OPTBLOCK:
@@ -1706,7 +1765,7 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
17061765
case NODE_DEFS:
17071766
case NODE_OP_ASGN1:
17081767
case NODE_ARGS:
1709-
gc_mark(objspace, (VALUE)obj->as.node.u1.node, lev);
1768+
gc_mark_defer(objspace, (VALUE)obj->as.node.u1.node, lev);
17101769
/* fall through */
17111770
case NODE_SUPER: /* 3 */
17121771
case NODE_FCALL:
@@ -1733,7 +1792,7 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
17331792
case NODE_ALIAS:
17341793
case NODE_VALIAS:
17351794
case NODE_ARGSCAT:
1736-
gc_mark(objspace, (VALUE)obj->as.node.u1.node, lev);
1795+
gc_mark_defer(objspace, (VALUE)obj->as.node.u1.node, lev);
17371796
/* fall through */
17381797
case NODE_GASGN: /* 2 */
17391798
case NODE_LASGN:
@@ -1769,7 +1828,7 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
17691828
case NODE_SCOPE: /* 2,3 */
17701829
case NODE_CDECL:
17711830
case NODE_OPT_ARG:
1772-
gc_mark(objspace, (VALUE)obj->as.node.u3.node, lev);
1831+
gc_mark_defer(objspace, (VALUE)obj->as.node.u3.node, lev);
17731832
ptr = (VALUE)obj->as.node.u2.node;
17741833
goto again;
17751834

@@ -1801,19 +1860,19 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
18011860

18021861
default: /* unlisted NODE */
18031862
if (is_pointer_to_heap(objspace, obj->as.node.u1.node)) {
1804-
gc_mark(objspace, (VALUE)obj->as.node.u1.node, lev);
1863+
gc_mark_defer(objspace, (VALUE)obj->as.node.u1.node, lev);
18051864
}
18061865
if (is_pointer_to_heap(objspace, obj->as.node.u2.node)) {
1807-
gc_mark(objspace, (VALUE)obj->as.node.u2.node, lev);
1866+
gc_mark_defer(objspace, (VALUE)obj->as.node.u2.node, lev);
18081867
}
18091868
if (is_pointer_to_heap(objspace, obj->as.node.u3.node)) {
1810-
gc_mark(objspace, (VALUE)obj->as.node.u3.node, lev);
1869+
gc_mark_defer(objspace, (VALUE)obj->as.node.u3.node, lev);
18111870
}
18121871
}
18131872
return; /* no need to mark class. */
18141873
}
18151874

1816-
gc_mark(objspace, obj->as.basic.klass, lev);
1875+
gc_mark_defer(objspace, obj->as.basic.klass, lev);
18171876
switch (BUILTIN_TYPE(obj)) {
18181877
case T_ICLASS:
18191878
case T_CLASS:
@@ -1833,7 +1892,7 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
18331892
long i, len = RARRAY_LEN(obj);
18341893
VALUE *ptr = RARRAY_PTR(obj);
18351894
for (i=0; i < len; i++) {
1836-
gc_mark(objspace, *ptr++, lev);
1895+
gc_mark_defer(objspace, *ptr++, lev);
18371896
}
18381897
}
18391898
break;
@@ -1866,24 +1925,24 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
18661925
long i, len = ROBJECT_NUMIV(obj);
18671926
VALUE *ptr = ROBJECT_IVPTR(obj);
18681927
for (i = 0; i < len; i++) {
1869-
gc_mark(objspace, *ptr++, lev);
1928+
gc_mark_defer(objspace, *ptr++, lev);
18701929
}
18711930
}
18721931
break;
18731932

18741933
case T_FILE:
18751934
if (obj->as.file.fptr) {
1876-
gc_mark(objspace, obj->as.file.fptr->pathv, lev);
1877-
gc_mark(objspace, obj->as.file.fptr->tied_io_for_writing, lev);
1878-
gc_mark(objspace, obj->as.file.fptr->writeconv_asciicompat, lev);
1879-
gc_mark(objspace, obj->as.file.fptr->writeconv_pre_ecopts, lev);
1880-
gc_mark(objspace, obj->as.file.fptr->encs.ecopts, lev);
1881-
gc_mark(objspace, obj->as.file.fptr->write_lock, lev);
1935+
gc_mark_defer(objspace, obj->as.file.fptr->pathv, lev);
1936+
gc_mark_defer(objspace, obj->as.file.fptr->tied_io_for_writing, lev);
1937+
gc_mark_defer(objspace, obj->as.file.fptr->writeconv_asciicompat, lev);
1938+
gc_mark_defer(objspace, obj->as.file.fptr->writeconv_pre_ecopts, lev);
1939+
gc_mark_defer(objspace, obj->as.file.fptr->encs.ecopts, lev);
1940+
gc_mark_defer(objspace, obj->as.file.fptr->write_lock, lev);
18821941
}
18831942
break;
18841943

18851944
case T_REGEXP:
1886-
gc_mark(objspace, obj->as.regexp.src, lev);
1945+
gc_mark_defer(objspace, obj->as.regexp.src, lev);
18871946
break;
18881947

18891948
case T_FLOAT:
@@ -1892,21 +1951,21 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
18921951
break;
18931952

18941953
case T_MATCH:
1895-
gc_mark(objspace, obj->as.match.regexp, lev);
1954+
gc_mark_defer(objspace, obj->as.match.regexp, lev);
18961955
if (obj->as.match.str) {
18971956
ptr = obj->as.match.str;
18981957
goto again;
18991958
}
19001959
break;
19011960

19021961
case T_RATIONAL:
1903-
gc_mark(objspace, obj->as.rational.num, lev);
1904-
gc_mark(objspace, obj->as.rational.den, lev);
1962+
gc_mark_defer(objspace, obj->as.rational.num, lev);
1963+
gc_mark_defer(objspace, obj->as.rational.den, lev);
19051964
break;
19061965

19071966
case T_COMPLEX:
1908-
gc_mark(objspace, obj->as.complex.real, lev);
1909-
gc_mark(objspace, obj->as.complex.imag, lev);
1967+
gc_mark_defer(objspace, obj->as.complex.real, lev);
1968+
gc_mark_defer(objspace, obj->as.complex.imag, lev);
19101969
break;
19111970

19121971
case T_STRUCT:
@@ -1915,7 +1974,7 @@ gc_mark_children(rb_objspace_t *objspace, VALUE ptr, int lev)
19151974
VALUE *ptr = RSTRUCT_PTR(obj);
19161975

19171976
while (len--) {
1918-
gc_mark(objspace, *ptr++, lev);
1977+
gc_mark_defer(objspace, *ptr++, lev);
19191978
}
19201979
}
19211980
break;
@@ -2428,6 +2487,10 @@ mark_current_machine_context(rb_objspace_t *objspace, rb_thread_t *th)
24282487
#endif
24292488
}
24302489

2490+
static void gc_mark_loop() {
2491+
while(gc_mark_pop()){};
2492+
}
2493+
24312494
static void
24322495
gc_marks(rb_objspace_t *objspace)
24332496
{
@@ -2476,6 +2539,7 @@ gc_marks(rb_objspace_t *objspace)
24762539
gc_mark_rest(objspace);
24772540
}
24782541
}
2542+
gc_mark_loop();
24792543
GC_PROF_MARK_TIMER_STOP;
24802544
}
24812545

0 commit comments

Comments
 (0)
0