Parallel Scanning and Stable Snapshots

Keyboard shortcuts

×

?

Open this guide

Alt + B

Show or hide the lesson list

Alt + O

Show or fold the lesson outline

Alt + N

Open or close notes

Alt + H

Toggle semantic colours

Alt + D

Toggle page brightness

Alt + C

Toggle code brightness

← →

Move through a focused code trace

Home End

First or final step in a focused trace

Escape

Close this guide or an open panel

Reader shortcuts pause while you type in a text field.

Cheatsheet for Lesson 5.11Key ideas, reference and questions

A one-page summary of “Parallel Scanning and Stable Snapshots” you can keep beside your notes. Plain Markdown.

Lesson 5.11 — Parallel Scanning and Stable Snapshots: cheatsheet

• Remember: Copy from the target first; let workers search the owned buffers so matching does not depend on extra live process reads.
• Also useful: A shared work basket lets the next free worker take another region, instead of leaving it idle behind a finished fixed assignment.

Key terms

• dynamic scheduling: Fetching the next index when a worker becomes free is dynamic scheduling.
• Amdahl's law: This is Amdahl's law: total speedup is capped by the fraction of the work that stays serial, no matter how many workers you add to the rest.

Review

• Q: Why sort addresses after parallel scanner workers finish? A: Worker completion order varies, while a stable result order helps tests and review
• Q: Which parallel scanner design gives workers the most stable input? A: Copy bounded readable code regions once, then scan immutable local buffers

Download cheatsheet (.md)

Download cheatsheet (.md)

This is an optional performance study after the chapter’s pattern scanner, memory scanner, and debugger. None of them requires multiple workers. Lesson 5.7 searched one copied code range at a time; here we keep its exact-byte and wildcard comparisons and change only how several stable ranges are searched. That separates the concurrency question from whether a byte pattern really identifies the intended instruction.

Divide the scan into independent ranges

The simple pattern scanner is intentionally single-threaded. Its next advanced step is not “put every Windows call on a thread.” The safe boundary is:

Only the capture phase touches the running Wesnoth process. Workers scan ordinary Vec<u8> buffers owned by the scanner.

TL;DR: Copy from the target first; let workers search the owned buffers so matching does not depend on extra live process reads.

That separation improves more than speed:

• a page cannot disappear halfway through a worker comparison;
• workers do not share a process handle;
• the matching algorithm uses checked local slices;
• captured bytes can be saved and replayed in tests;
• concurrency begins after the unstable operating-system boundary.

Check both safety and progress

Concurrent code needs two different kinds of promises:

• safety asks, “What bad result must never happen?”
• progress asks, “What useful ending must eventually happen?”

For this scanner:

Promise	Concrete guarantee
safety	no worker reads changing remote memory
safety	the global result cap is never exceeded
safety	a found address stays inside its copied region
progress	every worker eventually sees cancellation or an empty work queue
progress	the main thread joins every worker before publishing results
progress	one worker panic becomes an error instead of an endless wait

“Uses atomics” is not a complete concurrency argument. Name which safety fact each atomic protects and which condition lets each loop finish.

Copy only the intended code

The capture stage clips every Windows memory run to the live wesnoth.exe module and keeps only readable executable pages:

let start = region.base.max(module_base);
let end = region.base.saturating_add(region.size).min(module_end);
if start >= end {
    continue;
}

let length = end - start;
let bytes = process.read_bytes(start, length)?;
snapshots.push(RegionSnapshot { base: start, bytes });

The real tool also caps all copied executable bytes at 128 MiB. Memory safety prevents corruption, but it does not prevent a logically unbounded allocation from exhausting the machine.

If a page changes between VirtualQueryEx and ReadProcessMemory, that one region is skipped with a diagnostic. A partial buffer never reaches a worker.

Use an atomic index as a tiny work queue

Each worker asks for the next region number:

let index = next_region.fetch_add(1, Ordering::AcqRel);
let Some(region) = snapshots.get(index) else {
    break;
};

No region is handed out twice. When the index passes the slice, the worker finishes.

Two workers claim different regions from one atomic counterEach worker takes the next region number with one atomic step, so no region is scanned twice.

1. 1 The index starts at 0

   Shared

   Atomic region index

   0next region to claim

   Regions (immutable copies)

   region 0

   region 1

   region 2

   Workers

   Worker 1

   waiting

   Worker 2

   waiting

   Nothing has been claimed yet. The regions are immutable copies, so scanning them needs no lock.

2. 2 Worker 1 claims: the index goes 0 → 1

   Shared

   Atomic region index

   1next region to claim

   Regions (immutable copies)

   region 0Worker 1

   region 1

   region 2

   Workers

   Worker 1

   claimed 0, scanning region 0

   Worker 2

   waiting

   The atomic step hands Worker 1 the value 0 and leaves 1 behind. Worker 1 scans region 0.

3. 3 Worker 2 claims: the index goes 1 → 2

   Shared

   Atomic region index

   2next region to claim

   Regions (immutable copies)

   region 0Worker 1

   region 1Worker 2

   region 2

   Workers

   Worker 1

   scanning region 0

   Worker 2

   claimed 1, scanning region 1

   Worker 2 gets 1, not 0, because the first claim already moved the counter. It scans region 1.

Each worker takes the next region number with one atomic step, so no region is scanned twice.

This interactive lab needs JavaScript. The lesson text around it still explains the same idea.

Fetching the next index when a worker becomes free is dynamic scheduling. It is better than permanently giving worker 1 the first quarter of regions and worker 2 the second quarter: a worker that receives several tiny regions can continue helping while another scans a large one.

Alternative: A shared work basket lets the next free worker take another region, instead of leaving it idle behind a finished fixed assignment.

Region sizes can still be badly uneven. If measurement later justifies splitting one large snapshot into fixed-size chunks, adjacent chunks must overlap by pattern.len() - 1 bytes or a pattern crossing the boundary can disappear. The merge step must then remove duplicate addresses from the overlap. Faster scheduling is not correct if it creates blind spots.

Why not create one thread per region? A module can contain many runs, and thread creation itself costs memory and scheduling time. The tool uses at most available_parallelism() workers and never more workers than snapshots.

Bound results across every worker

A weak pattern can match thousands of locations. A per-thread limit is not enough: eight workers with a 4,096-item limit could still produce 32,768 items.

With a toy global cap of three, suppose worker 1 has recorded two matches and worker 2 finds two more. Both cannot simply read “2 of 3 used” and then append: that would publish four. Each must reserve one slot through the shared counter; only one of worker 2’s two matches can obtain the remaining slot. This is the safety promise in the table above. Cancellation is the separate progress promise: workers stop scanning once no more slots can be reserved.

The scanner reserves each result through one atomic counter:

fn reserve_match(counter: &AtomicUsize) -> bool {
    counter
        .fetch_update(Ordering::AcqRel, Ordering::Acquire, |current| {
            (current < MAX_MATCHES).then_some(current + 1)
        })
        .is_ok()
}

fetch_update performs “check below cap and increment” as one atomic operation. When the cap is full, the worker sets a shared cancellation flag. Other workers notice and stop.

The memory ordering communicates two small state transitions:

• Release publishes cancellation;
• Acquire makes another worker observe that published state.

The bytes themselves need no mutex or atomic because they are immutable.

Restore deterministic output

Thread completion order changes from run to run. Addresses should not:

matches.sort_unstable();
matches.dedup();
anyhow::ensure!(matches.len() == 1, "expected one match");

Sorting after the merge makes logs, tests, and human review repeatable. Deduplication is defensive; clipped memory regions should not overlap, but downstream correctness should not depend on that hope.

The same design works for an offline archive or asset scanner: first collect bounded, immutable input chunks, let workers inspect separate chunks, then apply one global output limit and sort results. The game-specific part here is the capture boundary, where bytes come from a changing process.

This distinction matters:

• parallel execution order may vary;
• published result order should be stable.

Complete buildable tool

Complete lab source: parallel_pattern_scanner.rs

parallel_pattern_scanner.rs

windows-labs/src/bin/ · Rust, 155 lines

View on GitHub ↗

#[cfg(windows)]
fn main() -> anyhow::Result<()> {
    use std::{
        sync::atomic::{AtomicBool, AtomicUsize, Ordering},
        thread,
    };

    use anyhow::Context;
    use gha_windows_labs::Process;

    const PATTERN: [u8; 3] = [0x29, 0x42, 0x04];
    const MAX_SNAPSHOT_BYTES: usize = 128 * 1024 * 1024;
    const MAX_MATCHES: usize = 4_096;

    struct RegionSnapshot {
        base: usize,
        bytes: Vec<u8>,
    }

    fn reserve_match(counter: &AtomicUsize) -> bool {
        counter
            .fetch_update(Ordering::AcqRel, Ordering::Acquire, |current| {
                (current < MAX_MATCHES).then_some(current + 1)
            })
            .is_ok()
    }

    let process = Process::open_by_name("wesnoth.exe", false)?;
    anyhow::ensure!(
        process.is_32_bit()?,
        "this profile requires 32-bit Wesnoth 1.14.9"
    );
    let (module_base, module_size) = process.module("wesnoth.exe")?;
    let module_end = module_base
        .checked_add(module_size)
        .context("module range overflowed")?;

    let mut total_bytes = 0_usize;
    let mut snapshots = Vec::new();
    for region in process.regions(module_base, module_end)? {
        if !region.readable || !region.executable {
            continue;
        }
        // 📏 VirtualQueryEx can return a run wider than the module; clip it.
        let start = region.base.max(module_base);
        let end = region.base.saturating_add(region.size).min(module_end);
        if start >= end {
            continue;
        }
        let length = end - start;
        total_bytes = total_bytes
            .checked_add(length)
            .context("snapshot byte count overflowed")?;
        anyhow::ensure!(
            total_bytes <= MAX_SNAPSHOT_BYTES,
            "executable snapshot exceeds {MAX_SNAPSHOT_BYTES} bytes"
        );

        match process.read_bytes(start, length) {
            Ok(bytes) => snapshots.push(RegionSnapshot { base: start, bytes }),
            // ⚠️ The process can change a page between query and copy. Skip that
            // observation rather than feeding a partial buffer to worker threads.
            Err(error) => eprintln!("skipped region {start:#010x}+{length:#x}: {error:#}"),
        }
    }
    anyhow::ensure!(
        !snapshots.is_empty(),
        "no readable executable regions were copied"
    );

    let worker_count = thread::available_parallelism()
        .map(|count| count.get())
        .unwrap_or(1)
        .min(snapshots.len());
    let next_region = AtomicUsize::new(0);
    let match_count = AtomicUsize::new(0);
    let cancelled = AtomicBool::new(false);

    // 🔀 Remote memory is copied before parallel work begins. Workers receive
    // immutable local slices, so no process handle or changing page is shared.
    let mut matches = thread::scope(|scope| -> anyhow::Result<Vec<usize>> {
        let mut workers = Vec::new();
        for _ in 0..worker_count {
            let snapshots = &snapshots;
            let next_region = &next_region;
            let match_count = &match_count;
            let cancelled = &cancelled;
            workers.push(scope.spawn(move || -> anyhow::Result<Vec<usize>> {
                let mut local = Vec::new();
                loop {
                    if cancelled.load(Ordering::Acquire) {
                        break;
                    }
                    let index = next_region.fetch_add(1, Ordering::AcqRel);
                    let Some(region) = snapshots.get(index) else {
                        break;
                    };

                    for (offset, window) in region.bytes.windows(PATTERN.len()).enumerate() {
                        if window != PATTERN {
                            continue;
                        }
                        if !reserve_match(match_count) {
                            cancelled.store(true, Ordering::Release);
                            break;
                        }
                        local.push(
                            region
                                .base
                                .checked_add(offset)
                                .context("match address overflowed")?,
                        );
                    }
                }
                Ok(local)
            }));
        }

        let mut combined = Vec::new();
        for worker in workers {
            let local = worker
                .join()
                .map_err(|_| anyhow::anyhow!("a scanner worker panicked"))??;
            combined.extend(local);
        }
        Ok(combined)
    })?;

    anyhow::ensure!(
        !cancelled.load(Ordering::Acquire),
        "match cap reached; pattern is too broad"
    );
    // ✅ Parallel completion order is nondeterministic; sorting makes output and
    // later uniqueness checks repeatable.
    matches.sort_unstable();
    matches.dedup();

    println!(
        "Scanned {total_bytes} copied bytes with {worker_count} worker(s); {} match(es):",
        matches.len()
    );
    for address in &matches {
        println!("  {address:#010x}: sub dword ptr [edx+4], eax");
    }
    anyhow::ensure!(
        matches.len() == 1,
        "expected exactly one verified course-build match"
    );
    Ok(())
}

#[cfg(not(windows))]
fn main() {
    eprintln!("This live parallel scanner must run on Windows.");
}

The source is also available as parallel_pattern_scanner.rs.

Build and run it

Windows VM

Start the exact 32-bit Wesnoth 1.14.9 course build in a local match:

cd windows-labs
cargo build --release --target i686-pc-windows-msvc --bin parallel_pattern_scanner
.\target\i686-pc-windows-msvc\release\parallel_pattern_scanner.exe

The tool searches for the verified gold-subtraction bytes:

29 42 04    ; sub dword ptr [edx+4], eax

A supported build should produce one address. Zero means the build, capture, or signature assumption is wrong. More than one means the signature is ambiguous. Parallelism does not change what those counts mean.

Measure before claiming a speedup

Parallel scanning has fixed costs:

• copying the process is still sequential;
• creating workers costs time;
• a three-byte pattern is cheap to compare;
• merging and sorting remain;
• small modules may fit in cache and finish faster on one thread.

Measure the capture and scan phases separately with Instant. If capture dominates, adding workers cannot solve that bottleneck. This is Amdahl’s law: total speedup is capped by the fraction of the work that stays serial, no matter how many workers you add to the rest. Concretely, if capture takes 80% of the run and scanning the other 20%, parallelizing the scan perfectly still only shrinks that 20%. Ten workers cannot beat roughly a 1.25x overall speedup, because the 80% you didn’t parallelize is still there.

Narration: If copying takes longer than matching, faster matching will barely change the total waiting time. Time both phases before adding workers.

For course-sized modules, the architecture lesson is more important than the benchmark number.

Failure cases to test

Create local byte buffers and verify:

1. a match at the first and last legal offsets;
2. no match;
3. overlapping matches;
4. more matches than the global cap;
5. one empty snapshot list;
6. a base address whose base + offset would overflow;
7. worker panic reporting;
8. sorted output across repeated runs.

Do these tests without a game process. Only the small capture layer requires Windows and Wesnoth.

What makes the parallel result trustworthy

The finished scanner relies on five linked properties:

• copying process bytes first gives workers stable local input;
• one global match cap bounds the total result, regardless of worker count;
• cancellation stops unnecessary work after the cap is reached;
• sorting makes the returned address order reproducible;
• one unique match still needs semantic verification before use, however fast the scan ran.

Chapter 6 starts from that verified site and asks how a small DLL can enter a supported process, redirect one call, and restore the original path.

🧩

Knowledge check

Separate scheduling from results

Why sort addresses after parallel scanner workers finish?

1Worker completion order varies, while a stable result order helps tests and review2Sorting makes an ambiguous pattern unique, so the scanner can accept its result3Windows requires addresses to arrive in ascending order before they are published4Sorting changes the remote pages to read-only, so a later scan cannot disturb them

Check answer

Finished Lesson 5.11?

Mark it done and the lesson list shows a ✓ beside it. A chapter whose lessons are all done is marked done too. Progress is saved in this browser only.

Mark lesson doneLesson done. Mark it not done

Chapter 5: 11 lessons

📝 Notes