Memory leak when calling decode_arithmetic()

[christopherwxyz]

Currently using @farcaster/shuttle and experiencing a gnarly memory leak. I loaded up a heapdump and narrowed it down to a dynamically growing array or possibly a few variants.

export function decode_arithmetic(bytes) {
	let pos = 0;
	function u16() { return (bytes[pos++] << 8) | bytes[pos++]; }

	// decode the frequency table
	let symbol_count = u16();
	let total = 1;
	let acc = [0, 1]; // first symbol has frequency 1
	for (let i = 1; i < symbol_count; i++) {
		acc.push(total += u16()); // Potential memory growth issue
	}

	// skip the sized-payload that the last 3 symbols index into
	let skip = u16();
	let pos_payload = pos;
	pos += skip;

	let read_width = 0;
	let read_buffer = 0; 
	function read_bit() {
		if (read_width == 0) {
			read_buffer = (read_buffer << 8) | bytes[pos++]; // Potential out-of-bounds read
			read_width = 8;
		}
		return (read_buffer >> --read_width) & 1;
	}

	const N = 31;
	const FULL = 2**N;
	const HALF = FULL >>> 1;
	const QRTR = HALF >> 1;
	const MASK = FULL - 1;

	// fill register
	let register = 0;
	for (let i = 0; i < N; i++) register = (register << 1) | read_bit();

	let symbols = []; // Potential memory growth issue
	let low = 0;
	let range = FULL; // treat like a float
	while (true) {
		let value = Math.floor((((register - low + 1) * total) - 1) / range);
		let start = 0;
		let end = symbol_count;
		while (end - start > 1) { // binary search loop
			let mid = (start + end) >>> 1;
			if (value < acc[mid]) {
				end = mid;
			} else {
				start = mid;
			}
		}
		if (start == 0) break; // first symbol is end mark
		symbols.push(start); // Potential memory growth issue
		let a = low + Math.floor(range * acc[start]   / total);
		let b = low + Math.floor(range * acc[start+1] / total) - 1
		while (((a ^ b) & HALF) == 0) {
			register = (register << 1) & MASK | read_bit();
			a = (a << 1) & MASK;
			b = (b << 1) & MASK | 1;
		}
		while (a & ~b & QRTR) {
			register = (register & HALF) | ((register << 1) & (MASK >>> 1)) | read_bit();
			a = (a << 1) ^ HALF;
			b = ((b ^ HALF) << 1) | HALF | 1;
		}
		low = a;
		range = 1 + b - a;
	}
	let offset = symbol_count - 4;
	return symbols.map(x => { // Potential out-of-bounds access
		switch (x - offset) {
			case 3: return offset + 0x10100 + ((bytes[pos_payload++] << 16) | (bytes[pos_payload++] << 8) | bytes[pos_payload++]);
			case 2: return offset + 0x100 + ((bytes[pos_payload++] << 8) | bytes[pos_payload++]);
			case 1: return offset + bytes[pos_payload++];
			default: return x - 1;
		}
	});
}

Steps to reproduce:

1. Run https://github.com/christopherwxyz/enterprise-shuttle in a local environment (happy to share this on a call since setup is non-trivial).
2. Observe heapdump after 5 minutes of run.
3. Log out to Chrome devtools.

[adraffy]

That function shouldn't run more than once per blob, of which there are 2.

Let me see if I can run this.

[adraffy]

There's not enough information here for me to run this, can you provide steps?

[christopherwxyz]

1. Not sure if it's minimally reproducible. It's being called from enterprise-shuttle -> @farcaster/hub-nodejs -> @farcaster/core -> viem -> ens-normalizer
2. You'll need to run a shuttle instance and let it expand the dynamic array out to a size large enough to prevent garbage collection.
3. I ran this in the dockerfile container locally, then heapdump to a local file to analyze.

[adraffy]

I temporarily added an deinit() function and called init(); deinit(); in a loop while observing process.memoryUsage() and see no leak. IMO, it very unlikely that there is a leak at this level, as I'm only building dag-like structures with Set, Map, and primitives. I also took special care to avoid large spreads to avoid JS engine limitations.

However, this library does have a non-zero setup cost to decompress the full spec and build the appropriate structures. Is your project (or some part of it) using a short-lived worker?

Can you provide me a zip or the JS bundle of whatever code is actually being executed? Possibly the inline base64 blob is getting mangled during your build process? decode_arithmetic() will certainty do something silly if the incoming data is non-sense (eg. zip-bomb equivalent expansion)