Skip to content

Commit 41ad2f8

Browse files
dcodeIOdcodeIO
committed
Add a more convenient tracing utility for debugging; Fix basic GC test
1 parent f56face commit 41ad2f8

File tree

19 files changed

+2097
-536
lines changed

19 files changed

+2097
-536
lines changed

‎cli/asc.js‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -414,7 +414,8 @@ exports.main = function main(argv, options, callback) {
414414
// Initialize default aliases
415415
assemblyscript.setGlobalAlias(compilerOptions, "Math", "NativeMath");
416416
assemblyscript.setGlobalAlias(compilerOptions, "Mathf", "NativeMathf");
417-
assemblyscript.setGlobalAlias(compilerOptions, "abort", "~lib/env/abort"); // to disable: --use abort=
417+
assemblyscript.setGlobalAlias(compilerOptions, "abort", "~lib/env/abort");
418+
assemblyscript.setGlobalAlias(compilerOptions, "trace", "~lib/env/trace");
418419

419420
// Add or override aliases if specified
420421
if (args.use) {

‎src/builtins.ts‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2700,6 +2700,7 @@ export function compileCall(
27002700
}
27012701
}
27022702
}
2703+
compiler.currentType = Type.void;
27032704
return exprs.length
27042705
? module.createBlock(null, exprs)
27052706
: module.createNop();

‎src/program.ts‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -626,8 +626,8 @@ export class Program extends DiagnosticEmitter {
626626
}
627627

628628
// register 'main' if present
629-
if (this.elementsLookup.has("main")) {
630-
let element = <Element>this.elementsLookup.get("main");
629+
if (this.moduleLevelExports.has("main")) {
630+
let element = (<ModuleExport>this.moduleLevelExports.get("main")).element;
631631
if (
632632
element.kind == ElementKind.FUNCTION_PROTOTYPE &&
633633
!(<FunctionPrototype>element).isAny(CommonFlags.GENERIC | CommonFlags.AMBIENT)

‎std/assembly/collector/itcm.ts‎

Lines changed: 101 additions & 105 deletions
Original file line numberDiff line numberDiff line change
@@ -4,13 +4,37 @@
44
* @module std/assembly/collector/itcm
55
*//***/
66

7-
// Based on the concepts of Bach Le's μgc, see: https://github.com/bullno1/ugc
7+
// Largely based on the Bach Le's μgc, see: https://github.com/bullno1/ugc
8+
9+
const TRACE = true;
810

911
import {
1012
AL_MASK,
1113
MAX_SIZE_32
1214
} from "../internal/allocator";
1315

16+
/** Collector states. */
17+
const enum State {
18+
/** Not yet initialized. */
19+
INIT = 0,
20+
/** Currently transitioning from SWEEP to MARK state. */
21+
IDLE = 1,
22+
/** Currently marking reachable objects. */
23+
MARK = 2,
24+
/** Currently sweeping unreachable objects. */
25+
SWEEP = 3
26+
}
27+
28+
/** Current collector state. */
29+
var state = State.INIT;
30+
/** Current white color value. */
31+
var white = 0;
32+
33+
// From and to spaces
34+
var from: ManagedObject;
35+
var to: ManagedObject;
36+
var iter: ManagedObject;
37+
1438
// ╒═══════════════ Managed object layout (32-bit) ════════════════╕
1539
// 3 2 1
1640
// 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 bits
@@ -23,175 +47,144 @@ import {
2347
// └───────────────────────────────────────────────────────────────┘
2448
// F: flags
2549

26-
/** Managed object flags. */
27-
namespace Flags {
28-
/** Object is unreachable (so far). */
29-
export var WHITE = 0;
30-
/** Object is reachable. */
31-
export var BLACK = 1;
32-
/** Object is reachable but its children have not yet been scanned. */
33-
export const GRAY = 2;
34-
/** Mask to obtain just the flag bits. */
35-
export const MASK = AL_MASK;
36-
}
37-
3850
/** Represents a managed object in memory, consisting of a header followed by the object's data. */
3951
@unmanaged
4052
class ManagedObject {
4153

42-
/** Pointer to the next object with additional flags stored in the alignment bits. */
43-
nextWithFlags: usize;
54+
/** Pointer to the next object with color flags stored in the alignment bits. */
55+
nextWithColor: usize;
4456

4557
/** Pointer to the previous object. */
4658
prev: ManagedObject;
4759

48-
/** Visitor function called with the data pointer (excl. header). */
49-
visitFn: (obj: usize) => void;
60+
/** Visitor function called with the payload reference. */
61+
visitFn: (ref: usize) => void;
5062

5163
/** Size of a managed object after alignment. */
5264
static readonly SIZE: usize = (offsetof<ManagedObject>() + AL_MASK) & ~AL_MASK;
5365

5466
/** Gets the pointer to the next object in the list. */
5567
get next(): ManagedObject {
56-
return changetype<ManagedObject>(this.nextWithFlags & ~Flags.MASK);
68+
return changetype<ManagedObject>(this.nextWithColor & ~3);
5769
}
5870

5971
/** Sets the pointer to the next object in the list. */
6072
set next(obj: ManagedObject) {
61-
this.nextWithFlags = changetype<usize>(obj) | (this.nextWithFlags & Flags.MASK);
73+
this.nextWithColor = changetype<usize>(obj) | (this.nextWithColor & 3);
74+
}
75+
76+
/** Gets this object's color. */
77+
get color(): i32 {
78+
return this.nextWithColor & 3;
79+
}
80+
81+
/** Sets this object's color. */
82+
set color(color: i32) {
83+
this.nextWithColor = (this.nextWithColor & ~3) | color;
6284
}
6385

6486
/** Inserts an object to this list. */
65-
insert(obj: ManagedObject): void {
87+
push(obj: ManagedObject): void {
6688
var prev = this.prev;
89+
trace(" push", 3, objToRef(prev), objToRef(obj), objToRef(this));
6790
obj.next = this;
6891
obj.prev = prev;
6992
prev.next = obj;
7093
this.prev = obj;
7194
}
7295

73-
/** Removes this object from its list. */
74-
remove(): void {
96+
/** Unlinks this object from its list. */
97+
unlink(): void {
7598
var next = this.next;
7699
var prev = this.prev;
100+
if (TRACE) trace(" unlink", 3, objToRef(prev), objToRef(this), objToRef(next));
77101
next.prev = prev;
78102
prev.next = next;
79103
}
80104

81105
clear(): void {
82-
this.nextWithFlags = changetype<usize>(this);
106+
if (TRACE) trace(" clear", 1, objToRef(this));
107+
this.nextWithColor = changetype<usize>(this);
83108
this.prev = this;
84109
}
85110

86-
/** Tests if this object is white, that is unreachable (so far). */
87-
get isWhite(): bool {
88-
return (this.nextWithFlags & Flags.MASK) == Flags.WHITE;
89-
}
90-
91-
/** Marks this object as white, that is unreachable (so far). */
92-
makeWhite(): void {
93-
this.nextWithFlags = (this.nextWithFlags & ~Flags.MASK) | Flags.WHITE;
94-
}
95-
96-
/** Tests if this object is black, that is reachable. Root objects are always reachable. */
97-
get isBlack(): bool {
98-
return (this.nextWithFlags & Flags.MASK) == Flags.BLACK;
99-
}
100-
101-
/** Marks this object as black, that is reachable. */
102-
makeBlack(): void {
103-
this.nextWithFlags = (this.nextWithFlags & ~Flags.MASK) | Flags.BLACK;
104-
}
105-
106-
/** Tests if this object is gray, that is reachable with unscanned children. */
107-
get isGray(): bool {
108-
return (this.nextWithFlags & Flags.MASK) == Flags.GRAY;
109-
}
110-
111111
/** Marks this object as gray, that is reachable with unscanned children. */
112112
makeGray(): void {
113-
if (this != iter) {
114-
this.remove();
115-
set2.insert(this);
116-
} else {
117-
iter = iter.prev;
118-
}
119-
this.nextWithFlags = (this.nextWithFlags & ~Flags.MASK) | Flags.GRAY;
113+
if (TRACE) trace(" makeGray", 1, objToRef(this));
114+
const gray = 2;
115+
if (this == iter) iter = this.prev;
116+
this.unlink();
117+
to.push(this);
118+
this.nextWithColor = (this.nextWithColor & ~3) | gray;
120119
}
121120
}
122121

123-
/** Collector states. */
124-
const enum State {
125-
/** Not yet initialized. */
126-
INIT = 0,
127-
/** Currently transitioning from SWEEP to MARK state. */
128-
IDLE = 1,
129-
/** Currently marking reachable objects. */
130-
MARK = 2,
131-
/** Currently sweeping unreachable objects. */
132-
SWEEP = 3
122+
function markRoots(): void {
123+
if (TRACE) trace(" markRoots");
124+
gc.iterateRoots(function markRoot(ref: usize): void {
125+
if (TRACE) trace(" markRoot", 1, ref);
126+
if (ref) __gc_mark(ref);
127+
});
133128
}
134129

135-
/** Current collector state. */
136-
var state = State.INIT;
137-
138-
// From and to spaces
139-
var set1: ManagedObject;
140-
var set2: ManagedObject;
141-
var iter: ManagedObject;
142-
143130
/** Performs a single step according to the current state. */
144131
function step(): void {
145132
var obj: ManagedObject;
146133
switch (state) {
147134
case State.INIT: {
148-
set1 = changetype<ManagedObject>(memory.allocate(ManagedObject.SIZE));
149-
set1.clear();
150-
set2 = changetype<ManagedObject>(memory.allocate(ManagedObject.SIZE));
151-
set2.clear();
152-
iter = set2;
135+
if (TRACE) trace("gc~step/INIT");
136+
from = changetype<ManagedObject>(memory.allocate(ManagedObject.SIZE));
137+
from.visitFn = changetype<(ref: usize) => void>(<u32>-1); // would error
138+
from.clear();
139+
to = changetype<ManagedObject>(memory.allocate(ManagedObject.SIZE));
140+
to.visitFn = changetype<(ref: usize) => void>(<u32>-1); // would error
141+
to.clear();
142+
iter = to;
143+
state = State.IDLE;
144+
if (TRACE) trace("gc~state = IDLE");
153145
// fall-through
154146
}
155147
case State.IDLE: {
156-
// start by marking roots
157-
gc.iterateRoots(function mark_root(ref: usize): void {
158-
if (ref) {
159-
let obj = changetype<ManagedObject>(ref - ManagedObject.SIZE);
160-
obj.makeBlack();
161-
obj.visitFn(ref);
162-
}
163-
});
148+
if (TRACE) trace("gc~step/IDLE");
149+
markRoots();
164150
state = State.MARK;
151+
if (TRACE) trace("gc~state = MARK");
165152
break;
166153
}
167154
case State.MARK: {
168155
obj = iter.next;
169-
if (obj != set2) {
156+
if (obj !== to) {
157+
if (TRACE) trace("gc~step/MARK iterate", 1, objToRef(obj));
170158
iter = obj;
171-
obj.makeBlack();
172-
obj.visitFn(changetype<usize>(obj) + ManagedObject.SIZE);
159+
obj.color = <i32>!white;
160+
obj.visitFn(objToRef(obj));
173161
} else {
162+
if (TRACE) trace("gc~step/MARK finish");
163+
markRoots();
174164
obj = iter.next;
175-
if (obj == set2) {
176-
let set1_ = set1;
177-
set1 = set2;
178-
set2 = set1_;
179-
Flags.WHITE ^= 1;
180-
Flags.BLACK ^= 1;
181-
iter = set1.next;
165+
if (obj === to) {
166+
let prevFrom = from;
167+
from = to;
168+
to = prevFrom;
169+
white = <i32>!white;
170+
iter = prevFrom.next;
182171
state = State.SWEEP;
172+
if (TRACE) trace("gc~state = SWEEP");
183173
}
184174
}
185175
break;
186176
}
187177
case State.SWEEP: {
188178
obj = iter;
189-
if (obj !== set2) {
179+
if (obj !== to) {
180+
if (TRACE) trace("gc~step/SWEEP free", 1, objToRef(obj));
190181
iter = obj.next;
191182
memory.free(changetype<usize>(obj));
192183
} else {
193-
set2.clear();
184+
if (TRACE) trace("gc~step/SWEEP finish");
185+
to.clear();
194186
state = State.IDLE;
187+
if (TRACE) trace("gc~state = IDLE");
195188
}
196189
break;
197190
}
@@ -213,30 +206,33 @@ function step(): void {
213206
size: usize,
214207
visitFn: (ref: usize) => void
215208
): usize {
216-
assert(size <= MAX_SIZE_32 - ManagedObject.SIZE);
209+
if (TRACE) trace("gc.allocate", 1, size);
210+
if (size > MAX_SIZE_32 - ManagedObject.SIZE) unreachable();
211+
step(); // also makes sure it's initialized
217212
var obj = changetype<ManagedObject>(memory.allocate(ManagedObject.SIZE + size));
218-
obj.makeWhite();
219213
obj.visitFn = visitFn;
220-
set1.insert(obj);
214+
obj.color = white;
215+
from.push(obj);
221216
return objToRef(obj);
222217
}
223218

224219
/** Marks a reachable object. Called from the visitFn functions. */
225220
@global export function __gc_mark(ref: usize): void {
221+
if (TRACE) trace("gc.mark", 1, ref);
226222
var obj = refToObj(ref);
227-
if (state == State.SWEEP) return;
228-
if (obj.isWhite) obj.makeGray();
223+
if (obj.color == white) obj.makeGray();
229224
}
230225

231226
/** Links a managed child object to its parent object. */
232227
@global export function __gc_link(parentRef: usize, childRef: usize): void {
228+
if (TRACE) trace("gc.link", 2, parentRef, childRef);
233229
var parent = refToObj(parentRef);
234-
var child = refToObj(childRef);
235-
if (parent.isBlack && child.isWhite) parent.makeGray();
230+
if (parent.color == <i32>!white && refToObj(childRef).color == white) parent.makeGray();
236231
}
237232

238233
/** Performs a full garbage collection cycle. */
239234
@global export function __gc_collect(): void {
235+
if (TRACE) trace("gc.collect");
240236
// begin collecting if not yet collecting
241237
switch (state) {
242238
case State.INIT:

‎std/assembly/env.ts‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,16 @@
1-
/** Environment abort function called where assertions evaluate to false / on throw. */
21
declare function abort(
32
message?: string | null,
43
fileName?: string | null,
54
lineNumber?: u32,
65
columnNumber?: u32
76
): void;
7+
8+
declare function trace(
9+
message: string,
10+
n?: i32,
11+
a0?: f64,
12+
a1?: f64,
13+
a2?: f64,
14+
a3?: f64,
15+
a4?: f64
16+
): void;

‎std/assembly/gc.ts‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -9,19 +9,19 @@ export namespace gc {
99
}
1010

1111
export function mark(ref: usize): void {
12-
if (isDefined(__gc_mark)) return __gc_mark(ref); // tslint:disable-line
12+
if (isDefined(__gc_mark)) { __gc_mark(ref); return; } // tslint:disable-line
1313
WARNING("Calling 'gc.mark' requires a garbage collector to be present.");
1414
unreachable();
1515
}
1616

1717
export function link(parentRef: usize, childRef: usize): void {
18-
if (isDefined(__gc_link)) return __gc_link(parentRef, childRef); // tslint:disable-line
18+
if (isDefined(__gc_link)) { __gc_link(parentRef, childRef); return; } // tslint:disable-line
1919
WARNING("Calling 'gc.link' requires a garbage collector to be present.");
2020
unreachable();
2121
}
2222

2323
export function collect(): void {
24-
if (isDefined(__gc_collect)) return __gc_collect(); // tslint:disable-line
24+
if (isDefined(__gc_collect)) { __gc_collect(); return; } // tslint:disable-line
2525
WARNING("Calling 'gc.collect' requires a garbage collector to be present.");
2626
unreachable();
2727
}

0 commit comments

Comments
 (0)