Compare commits

..

2 Commits

Author SHA1 Message Date
Valentin Balaschenko
5fc815703e more detailed tracing 2026-06-01 11:57:19 +01:00
Valentin Balaschenko
a4abf883cf logs for ref counts 2026-05-31 18:04:34 +01:00
48 changed files with 175 additions and 3404 deletions

View File

@@ -37,12 +37,12 @@ runs:
run: |
echo 'Installing dependencies.'
conan install \
--profile ci \
--build="${BUILD_OPTION}" \
--options:host='&:tests=True' \
--options:host='&:xrpld=True' \
--settings:all build_type="${BUILD_TYPE}" \
--conf:all tools.build:jobs=${BUILD_NPROC} \
--conf:all tools.build:verbosity="${LOG_VERBOSITY}" \
--conf:all tools.compilation:verbosity="${LOG_VERBOSITY}" \
.
--profile ci \
--build="${BUILD_OPTION}" \
--options:host='&:tests=True' \
--options:host='&:xrpld=True' \
--settings:all build_type="${BUILD_TYPE}" \
--conf:all tools.build:jobs=${BUILD_NPROC} \
--conf:all tools.build:verbosity="${LOG_VERBOSITY}" \
--conf:all tools.compilation:verbosity="${LOG_VERBOSITY}" \
.

View File

@@ -15,7 +15,7 @@ runs:
shell: bash
env:
VERSION: ${{ github.ref_name }}
run: echo "VERSION=${VERSION}" >>"${GITHUB_ENV}"
run: echo "VERSION=${VERSION}" >> "${GITHUB_ENV}"
# When a tag is not pushed, then the version (e.g. 1.2.3-b0) is extracted
# from the BuildInfo.cpp file and the shortened commit hash appended to it.
@@ -28,17 +28,17 @@ runs:
echo 'Extracting version from BuildInfo.cpp.'
VERSION="$(cat src/libxrpl/protocol/BuildInfo.cpp | grep "versionString =" | awk -F '"' '{print $2}')"
if [[ -z "${VERSION}" ]]; then
echo 'Unable to extract version from BuildInfo.cpp.'
exit 1
echo 'Unable to extract version from BuildInfo.cpp.'
exit 1
fi
echo 'Appending shortened commit hash to version.'
SHA='${{ github.sha }}'
VERSION="${VERSION}+${SHA:0:7}"
echo "VERSION=${VERSION}" >>"${GITHUB_ENV}"
echo "VERSION=${VERSION}" >> "${GITHUB_ENV}"
- name: Output version
id: version
shell: bash
run: echo "version=${VERSION}" >>"${GITHUB_OUTPUT}"
run: echo "version=${VERSION}" >> "${GITHUB_OUTPUT}"

View File

@@ -1,403 +0,0 @@
#!/usr/bin/env python3
"""
Format embedded shell snippets using the shfmt hook configured in
.pre-commit-config.yaml.
Two shapes are recognised:
* YAML workflow/action files: literal block-scalar runs (`run: |`) and
single-line runs (`run: some command`). A single-line run is upgraded to
a `run: |` block scalar if shfmt's output spans multiple lines.
* Markdown files: ``` ```bash ``` fenced code blocks.
Any block that shfmt cannot parse is skipped with a warning on stderr, so
the file is left untouched and surrounding blocks still get formatted.
For each occurrence the body is dedented, written to a temp .sh file,
formatted via `pre-commit run shfmt --files <temp>` (falling back to
`prek`), then re-indented and written back in place.
When invoked without arguments, every .yml/.yaml under .github/ plus every
.md file in the repo is scanned. When invoked with file arguments (the
pre-commit case), only those files are processed.
"""
from __future__ import annotations
import re
import shutil
import subprocess
import sys
import tempfile
from dataclasses import dataclass
from pathlib import Path
from typing import Union
REPO = Path(__file__).resolve().parents[2]
_HOOK_RUNNER = next((cmd for cmd in ("pre-commit", "prek") if shutil.which(cmd)), None)
if _HOOK_RUNNER is None:
sys.exit("error: neither `pre-commit` nor `prek` found on PATH")
RUN_BLOCK_RE = re.compile(r"^(?P<prefix>[ \t]*(?:- )?)run:[ \t]*\|[+-]?[ \t]*$")
RUN_INLINE_RE = re.compile(
r"^(?P<prefix>[ \t]*(?:- )?)run:[ \t]+" r"(?P<value>(?!\|[+-]?[ \t]*$)\S.*?)[ \t]*$"
)
MD_BASH_OPEN_RE = re.compile(r"^(?P<indent>[ ]{0,3})`{3}bash[ \t]*$")
MD_FENCE_CLOSE_RE = re.compile(r"^[ ]{0,3}`{3,}[ \t]*$")
@dataclass(frozen=True)
class BlockRun:
"""A `run: |` block scalar; `body_start:body_end` slices into `lines`."""
body_start: int
body_end: int
body_indent: int
@dataclass(frozen=True)
class InlineRun:
"""A single-line `run: value` at `line_idx`."""
line_idx: int
prefix: str
value: str
@dataclass(frozen=True)
class MdBashBlock:
"""A markdown ``` ```bash ``` fenced code block.
`body_start:body_end` slices into the file's lines; `open_line_idx`
points at the opening fence line.
"""
open_line_idx: int
body_start: int
body_end: int
body_indent: int
RunItem = Union[BlockRun, InlineRun]
def _scan_block_body(
lines: list[str], body_start: int, run_col: int
) -> tuple[int | None, int]:
"""Locate the body of a `run: |` block scalar starting at `body_start`.
Returns `(body_indent, scan_end)`. `scan_end` is the line index where the
outer scanner should resume. `body_indent` is `None` when no body is
present (the scalar is empty, or the next non-blank line has indent
`<= run_col`).
"""
body_indent: int | None = None
scan_end = len(lines)
for idx in range(body_start, len(lines)):
line = lines[idx]
if line.strip() == "":
continue
indent = len(line) - len(line.lstrip(" "))
if body_indent is None:
if indent > run_col:
body_indent = indent
else:
scan_end = idx
break
elif indent < body_indent:
scan_end = idx
break
if body_indent is not None:
while scan_end > body_start and lines[scan_end - 1].strip() == "":
scan_end -= 1
if scan_end <= body_start:
body_indent = None
return body_indent, scan_end
def find_run_blocks(lines: list[str]) -> list[RunItem]:
"""Return run items in document order."""
items: list[RunItem] = []
line_idx = 0
while line_idx < len(lines):
line = lines[line_idx]
if block_match := RUN_BLOCK_RE.match(line):
run_col = len(block_match.group("prefix"))
body_start = line_idx + 1
body_indent, scan_end = _scan_block_body(lines, body_start, run_col)
if body_indent is not None:
items.append(
BlockRun(
body_start=body_start,
body_end=scan_end,
body_indent=body_indent,
)
)
line_idx = scan_end
continue
if inline_match := RUN_INLINE_RE.match(line):
items.append(
InlineRun(
line_idx=line_idx,
prefix=inline_match.group("prefix"),
value=inline_match.group("value"),
)
)
line_idx += 1
return items
def find_md_bash_blocks(lines: list[str]) -> list[MdBashBlock]:
"""Return ``` ```bash ``` fenced code blocks in document order."""
blocks: list[MdBashBlock] = []
line_idx = 0
while line_idx < len(lines):
open_match = MD_BASH_OPEN_RE.match(lines[line_idx])
if not open_match:
line_idx += 1
continue
body_start = line_idx + 1
close_idx = next(
(
j
for j in range(body_start, len(lines))
if MD_FENCE_CLOSE_RE.match(lines[j])
),
None,
)
if close_idx is None:
line_idx = body_start
continue
body = lines[body_start:close_idx]
non_blank = [b for b in body if b.strip()]
body_indent = (
min(len(b) - len(b.lstrip(" ")) for b in non_blank)
if non_blank
else len(open_match.group("indent"))
)
blocks.append(
MdBashBlock(
open_line_idx=line_idx,
body_start=body_start,
body_end=close_idx,
body_indent=body_indent,
)
)
line_idx = close_idx + 1
return blocks
def dedent(lines: list[str], n: int) -> list[str]:
pad = " " * n
return [
(
""
if line.strip() == ""
else (line[n:] if line.startswith(pad) else line.lstrip(" "))
)
for line in lines
]
def reindent(lines: list[str], n: int) -> list[str]:
pad = " " * n
return [pad + line if line else "" for line in lines]
_SHFMT_ERR_RE = re.compile(r"\.sh:\d+:\d+:\s")
_GHA_EXPR_RE = re.compile(r"\$\{\{.*?\}\}", re.DOTALL)
_GHA_PLACEHOLDER_RE = re.compile(r"__GHA_EXPR_(\d+)__")
def _encode_gha_exprs(text: str) -> tuple[str, list[str]]:
"""Replace `${{ ... }}` expressions with bash-safe placeholder identifiers."""
exprs: list[str] = []
def repl(match: re.Match[str]) -> str:
exprs.append(match.group(0))
return f"__GHA_EXPR_{len(exprs) - 1}__"
return _GHA_EXPR_RE.sub(repl, text), exprs
def _decode_gha_exprs(text: str, exprs: list[str]) -> str:
"""Restore `${{ ... }}` expressions from placeholder identifiers."""
return _GHA_PLACEHOLDER_RE.sub(lambda m: exprs[int(m.group(1))], text)
def shfmt_via_hook(tmp_path: Path) -> tuple[bool, str]:
# `${{ ... }}` is not valid shell, so swap it for a placeholder identifier
# that shfmt can parse, then restore it after formatting.
encoded, exprs = _encode_gha_exprs(tmp_path.read_text())
if exprs:
tmp_path.write_text(encoded)
res = subprocess.run(
[_HOOK_RUNNER, "run", "shfmt", "--files", str(tmp_path)],
cwd=REPO,
capture_output=True,
text=True,
)
output = res.stdout + res.stderr
# shfmt emits parse errors as "<path>:<line>:<col>: <message>".
parse_err = bool(_SHFMT_ERR_RE.search(output))
# A non-zero exit that is neither a parse error nor pre-commit's "I had
# to modify files" signal means the hook itself failed to run (missing
# binary, install failure, bad config, ...). Surface that loudly rather
# than silently treating it as a no-op.
if (
res.returncode != 0
and not parse_err
and "files were modified by this hook" not in output
):
sys.exit(
f"error: `{_HOOK_RUNNER} run shfmt` failed with exit {res.returncode}:\n{output}"
)
if exprs and not parse_err:
tmp_path.write_text(_decode_gha_exprs(tmp_path.read_text(), exprs))
return not parse_err, output
def _skip(path: Path, where: int, kind: str, output: str) -> None:
print(
f" shfmt could not parse {kind} at {path}:{where + 1} — skipped",
file=sys.stderr,
)
print(f" {output.strip()}", file=sys.stderr)
def process_yaml_file(path: Path, tmp_path: Path) -> int:
text = path.read_text()
had_nl = text.endswith("\n")
lines = text.split("\n")
if had_nl:
lines = lines[:-1]
items = find_run_blocks(lines)
if not items:
return 0
changed = 0
# Process in reverse so earlier indices remain valid as we splice.
for item in reversed(items):
if isinstance(item, BlockRun):
body = lines[item.body_start : item.body_end]
tmp_path.write_text("\n".join(dedent(body, item.body_indent)) + "\n")
ok, output = shfmt_via_hook(tmp_path)
if not ok:
_skip(path, item.body_start, "block", output)
continue
formatted = tmp_path.read_text().rstrip("\n")
new_body = reindent(formatted.split("\n"), item.body_indent)
if new_body != body:
lines[item.body_start : item.body_end] = new_body
changed += 1
else:
tmp_path.write_text(item.value + "\n")
ok, output = shfmt_via_hook(tmp_path)
if not ok:
_skip(path, item.line_idx, "inline run", output)
continue
formatted = tmp_path.read_text().rstrip("\n")
if formatted == item.value:
continue
formatted_lines = formatted.split("\n")
if len(formatted_lines) == 1:
lines[item.line_idx] = f"{item.prefix}run: {formatted}"
else:
body_indent = len(item.prefix) + 2
lines[item.line_idx : item.line_idx + 1] = [
f"{item.prefix}run: |",
*reindent(formatted_lines, body_indent),
]
changed += 1
new_text = "\n".join(lines) + ("\n" if had_nl else "")
if new_text != text:
path.write_text(new_text)
return changed
def process_md_file(path: Path, tmp_path: Path) -> int:
text = path.read_text()
had_nl = text.endswith("\n")
lines = text.split("\n")
if had_nl:
lines = lines[:-1]
blocks = find_md_bash_blocks(lines)
if not blocks:
return 0
changed = 0
for block in reversed(blocks):
body = lines[block.body_start : block.body_end]
tmp_path.write_text("\n".join(dedent(body, block.body_indent)) + "\n")
ok, output = shfmt_via_hook(tmp_path)
if not ok:
_skip(path, block.open_line_idx, "```bash block", output)
continue
formatted = tmp_path.read_text().rstrip("\n")
formatted_lines = formatted.split("\n") if formatted else []
new_body = reindent(formatted_lines, block.body_indent)
if new_body != body:
lines[block.body_start : block.body_end] = new_body
changed += 1
new_text = "\n".join(lines) + ("\n" if had_nl else "")
if new_text != text:
path.write_text(new_text)
return changed
def process_file(path: Path, tmp_path: Path) -> int:
if path.suffix in (".yml", ".yaml"):
return process_yaml_file(path, tmp_path)
if path.suffix == ".md":
return process_md_file(path, tmp_path)
return 0
def gather_files(argv: list[str]) -> list[Path]:
"""Return YAML workflow/action files and markdown files that we should
process — either the paths in `argv` or, when `argv` is empty, every
such file in the repo (skipping `external/`)."""
if argv:
candidates: list[Path] = [
(REPO / a).resolve() if not Path(a).is_absolute() else Path(a) for a in argv
]
else:
gh = REPO / ".github"
candidates = [
*gh.rglob("*.yml"),
*gh.rglob("*.yaml"),
*(
p
for p in REPO.rglob("*.md")
if "external" not in p.relative_to(REPO).parts
),
]
return sorted(
p
for p in candidates
if p.exists()
and (
(p.suffix in (".yml", ".yaml") and ".github" in p.parts)
or p.suffix == ".md"
)
)
def main(argv: list[str]) -> int:
files = gather_files(argv)
if not files:
return 0
with tempfile.TemporaryDirectory(prefix="format-inline-bash-") as tmpdir:
tmp_path = Path(tmpdir) / "shfmt.sh"
total = 0
for f in files:
n = process_file(f, tmp_path)
if n:
print(f"{f.relative_to(REPO)}: reformatted {n} block(s)")
total += n
return 1 if total else 0
if __name__ == "__main__":
sys.exit(main(sys.argv[1:]))

View File

@@ -100,8 +100,8 @@ jobs:
- name: Create multi-arch manifests
run: |
for tag in $(jq -cr '.tags[]' <<<"$DOCKER_METADATA_OUTPUT_JSON"); do
docker buildx imagetools create -t "$tag" "${tag}-amd64" "${tag}-arm64"
for tag in $(jq -cr '.tags[]' <<< "$DOCKER_METADATA_OUTPUT_JSON"); do
docker buildx imagetools create -t "$tag" "${tag}-amd64" "${tag}-arm64"
done
- name: Inspect image

View File

@@ -5,17 +5,8 @@ on:
types:
- checks_requested
pull_request:
types:
- opened
- edited
- reopened
- synchronize
- ready_for_review
branches:
- develop
- "release-*"
- "release/*"
- "staging/*"
types: [opened, edited, reopened, synchronize, ready_for_review]
branches: [develop]
jobs:
check_description:
@@ -29,11 +20,11 @@ jobs:
env:
PR_BODY: ${{ github.event.pull_request.body }}
if: ${{ github.event_name == 'pull_request' }}
run: printenv PR_BODY >pr_body.md
run: printenv PR_BODY > pr_body.md
- name: Check PR description differs from template
if: ${{ github.event_name == 'pull_request' }}
run: |
python .github/scripts/check-pr-description.py \
--template-file .github/pull_request_template.md \
--pr-body-file pr_body.md
run: >
python .github/scripts/check-pr-description.py
--template-file .github/pull_request_template.md
--pr-body-file pr_body.md

View File

@@ -5,19 +5,10 @@ on:
types:
- checks_requested
pull_request:
types:
- opened
- edited
- reopened
- synchronize
- ready_for_review
branches:
- develop
- "release-*"
- "release/*"
- "staging/*"
types: [opened, edited, reopened, synchronize, ready_for_review]
branches: [develop]
jobs:
check_title:
if: ${{ github.event.pull_request.draft != true }}
uses: XRPLF/actions/.github/workflows/check-pr-title.yml@cba1f0891650baf1a9c88624dc2d72573be2eb81
uses: XRPLF/actions/.github/workflows/check-pr-title.yml@291206777251b4d493641b5afbdf7c23009d2988

View File

@@ -98,7 +98,7 @@ jobs:
READY: ${{ contains(github.event.pull_request.labels.*.name, 'Ready to merge') }}
MERGE: ${{ github.event_name == 'merge_group' }}
run: |
echo "go=${{ (env.DRAFT != 'true' && env.READY == 'true') || env.FILES == 'true' || env.MERGE == 'true' }}" >>"${GITHUB_OUTPUT}"
echo "go=${{ (env.DRAFT != 'true' && env.READY == 'true') || env.FILES == 'true' || env.MERGE == 'true' }}" >> "${GITHUB_OUTPUT}"
cat "${GITHUB_OUTPUT}"
outputs:
go: ${{ steps.go.outputs.go == 'true' }}
@@ -168,9 +168,9 @@ jobs:
PR_URL: ${{ github.event.pull_request.html_url }}
run: |
gh api --method POST -H "Accept: application/vnd.github+json" -H "X-GitHub-Api-Version: 2022-11-28" \
/repos/xrplf/clio/dispatches -f "event_type=check_libxrpl" \
-F "client_payload[ref]=${{ needs.upload-recipe.outputs.recipe_ref }}" \
-F "client_payload[pr_url]=${PR_URL}"
/repos/xrplf/clio/dispatches -f "event_type=check_libxrpl" \
-F "client_payload[ref]=${{ needs.upload-recipe.outputs.recipe_ref }}" \
-F "client_payload[pr_url]=${PR_URL}"
passed:
if: failure() || cancelled()

View File

@@ -14,7 +14,7 @@ on:
jobs:
# Call the workflow in the XRPLF/actions repo that runs the pre-commit hooks.
run-hooks:
uses: XRPLF/actions/.github/workflows/pre-commit.yml@cba1f0891650baf1a9c88624dc2d72573be2eb81
uses: XRPLF/actions/.github/workflows/pre-commit.yml@5e942d61bf32f7557a7c159cfac4712a687b3e3a
with:
runs_on: ubuntu-latest
container: '{ "image": "ghcr.io/xrplf/ci/tools-rippled-pre-commit:sha-41ec7c1" }'

View File

@@ -53,7 +53,7 @@ jobs:
env:
PLATFORM: ${{ inputs.platform }}
run: |
echo "arch=${PLATFORM##*/}" >>$GITHUB_OUTPUT
echo "arch=${PLATFORM##*/}" >> $GITHUB_OUTPUT
- name: Set up Docker Buildx
uses: docker/setup-buildx-action@d7f5e7f509e45cec5c76c4d5afdd7de93d0b3df5 # v4.1.0

View File

@@ -113,7 +113,7 @@ jobs:
- name: Set ccache log file
if: ${{ inputs.ccache_enabled && runner.debug == '1' }}
run: echo "CCACHE_LOGFILE=${{ runner.temp }}/ccache.log" >>"${GITHUB_ENV}"
run: echo "CCACHE_LOGFILE=${{ runner.temp }}/ccache.log" >> "${GITHUB_ENV}"
- name: Print build environment
uses: XRPLF/actions/print-build-env@59dec886e4afb05a1724443af08baccbc045b574
@@ -146,11 +146,11 @@ jobs:
CMAKE_ARGS: ${{ inputs.cmake_args }}
run: |
cmake \
-G '${{ runner.os == 'Windows' && 'Visual Studio 17 2022' || 'Ninja' }}' \
-DCMAKE_TOOLCHAIN_FILE:FILEPATH=build/generators/conan_toolchain.cmake \
-DCMAKE_BUILD_TYPE="${BUILD_TYPE}" \
${CMAKE_ARGS} \
..
-G '${{ runner.os == 'Windows' && 'Visual Studio 17 2022' || 'Ninja' }}' \
-DCMAKE_TOOLCHAIN_FILE:FILEPATH=build/generators/conan_toolchain.cmake \
-DCMAKE_BUILD_TYPE="${BUILD_TYPE}" \
${CMAKE_ARGS} \
..
- name: Check protocol autogen files are up-to-date
working-directory: ${{ env.BUILD_DIR }}
@@ -172,10 +172,10 @@ jobs:
cmake --build . --target code_gen
DIFF=$(git -C .. status --porcelain -- include/xrpl/protocol_autogen src/tests/libxrpl/protocol_autogen)
if [ -n "${DIFF}" ]; then
echo "::error::Generated protocol files are out of date"
git -C .. diff -- include/xrpl/protocol_autogen src/tests/libxrpl/protocol_autogen
echo "${MESSAGE}"
exit 1
echo "::error::Generated protocol files are out of date"
git -C .. diff -- include/xrpl/protocol_autogen src/tests/libxrpl/protocol_autogen
echo "${MESSAGE}"
exit 1
fi
- name: Build the binary
@@ -186,18 +186,18 @@ jobs:
CMAKE_TARGET: ${{ inputs.cmake_target }}
run: |
cmake \
--build . \
--config "${BUILD_TYPE}" \
--parallel "${BUILD_NPROC}" \
--target "${CMAKE_TARGET}"
--build . \
--config "${BUILD_TYPE}" \
--parallel "${BUILD_NPROC}" \
--target "${CMAKE_TARGET}"
- name: Show ccache statistics
if: ${{ inputs.ccache_enabled }}
run: |
ccache --show-stats -vv
if [ '${{ runner.debug }}' = '1' ]; then
cat "${CCACHE_LOGFILE}"
curl ${CCACHE_REMOTE_STORAGE%|*}/status || true
cat "${CCACHE_LOGFILE}"
curl ${CCACHE_REMOTE_STORAGE%|*}/status || true
fi
- name: Upload the binary (Linux)
@@ -214,7 +214,7 @@ jobs:
working-directory: ${{ env.BUILD_DIR }}
run: |
set -o pipefail
./xrpld --definitions | python3 -m json.tool >server_definitions.json
./xrpld --definitions | python3 -m json.tool > server_definitions.json
- name: Upload server definitions
if: ${{ github.event.repository.visibility == 'public' && inputs.config_name == 'debian-bookworm-gcc-13-amd64-release' }}
@@ -231,10 +231,10 @@ jobs:
run: |
ldd ./xrpld
if [ "$(ldd ./xrpld | grep -E '(libstdc\+\+|libgcc)' | wc -l)" -eq 0 ]; then
echo 'The binary is statically linked.'
echo 'The binary is statically linked.'
else
echo 'The binary is dynamically linked.'
exit 1
echo 'The binary is dynamically linked.'
exit 1
fi
- name: Verify presence of instrumentation (Linux)
@@ -250,12 +250,12 @@ jobs:
run: |
ASAN_OPTS="include=${GITHUB_WORKSPACE}/sanitizers/suppressions/runtime-asan-options.txt:suppressions=${GITHUB_WORKSPACE}/sanitizers/suppressions/asan.supp"
if [[ "${CONFIG_NAME}" == *gcc* ]]; then
ASAN_OPTS="${ASAN_OPTS}:alloc_dealloc_mismatch=0"
ASAN_OPTS="${ASAN_OPTS}:alloc_dealloc_mismatch=0"
fi
echo "ASAN_OPTIONS=${ASAN_OPTS}" >>${GITHUB_ENV}
echo "TSAN_OPTIONS=include=${GITHUB_WORKSPACE}/sanitizers/suppressions/runtime-tsan-options.txt:suppressions=${GITHUB_WORKSPACE}/sanitizers/suppressions/tsan.supp" >>${GITHUB_ENV}
echo "UBSAN_OPTIONS=include=${GITHUB_WORKSPACE}/sanitizers/suppressions/runtime-ubsan-options.txt:suppressions=${GITHUB_WORKSPACE}/sanitizers/suppressions/ubsan.supp" >>${GITHUB_ENV}
echo "LSAN_OPTIONS=include=${GITHUB_WORKSPACE}/sanitizers/suppressions/runtime-lsan-options.txt:suppressions=${GITHUB_WORKSPACE}/sanitizers/suppressions/lsan.supp" >>${GITHUB_ENV}
echo "ASAN_OPTIONS=${ASAN_OPTS}" >> ${GITHUB_ENV}
echo "TSAN_OPTIONS=include=${GITHUB_WORKSPACE}/sanitizers/suppressions/runtime-tsan-options.txt:suppressions=${GITHUB_WORKSPACE}/sanitizers/suppressions/tsan.supp" >> ${GITHUB_ENV}
echo "UBSAN_OPTIONS=include=${GITHUB_WORKSPACE}/sanitizers/suppressions/runtime-ubsan-options.txt:suppressions=${GITHUB_WORKSPACE}/sanitizers/suppressions/ubsan.supp" >> ${GITHUB_ENV}
echo "LSAN_OPTIONS=include=${GITHUB_WORKSPACE}/sanitizers/suppressions/runtime-lsan-options.txt:suppressions=${GITHUB_WORKSPACE}/sanitizers/suppressions/lsan.supp" >> ${GITHUB_ENV}
- name: Run the separate tests
if: ${{ !inputs.build_only }}
@@ -266,9 +266,9 @@ jobs:
PARALLELISM: ${{ runner.os == 'Windows' && '1' || steps.nproc.outputs.nproc }}
run: |
ctest \
--output-on-failure \
-C "${BUILD_TYPE}" \
-j "${PARALLELISM}"
--output-on-failure \
-C "${BUILD_TYPE}" \
-j "${PARALLELISM}"
- name: Run the embedded tests
if: ${{ !inputs.build_only }}
@@ -278,7 +278,7 @@ jobs:
run: |
set -o pipefail
# Coverage builds are slower due to instrumentation; use fewer parallel jobs to avoid flakiness
[ "$COVERAGE_ENABLED" = "true" ] && BUILD_NPROC=$((BUILD_NPROC - 2))
[ "$COVERAGE_ENABLED" = "true" ] && BUILD_NPROC=$(( BUILD_NPROC - 2 ))
./xrpld --unittest --unittest-jobs "${BUILD_NPROC}" 2>&1 | tee unittest.log
- name: Show test failure summary
@@ -287,19 +287,19 @@ jobs:
WORKING_DIR: ${{ runner.os == 'Windows' && format('{0}\{1}', env.BUILD_DIR, inputs.build_type) || env.BUILD_DIR }}
run: |
if [ ! -d "${WORKING_DIR}" ]; then
echo "Working directory '${WORKING_DIR}' does not exist."
exit 0
echo "Working directory '${WORKING_DIR}' does not exist."
exit 0
fi
cd "${WORKING_DIR}"
if [ ! -f unittest.log ]; then
echo "unittest.log not found; embedded tests may not have run."
exit 0
echo "unittest.log not found; embedded tests may not have run."
exit 0
fi
if ! grep -E "failed" unittest.log; then
echo "Log present but no failure lines found in unittest.log."
echo "Log present but no failure lines found in unittest.log."
fi
- name: Debug failure (Linux)
if: ${{ failure() && runner.os == 'Linux' && !inputs.build_only }}
@@ -317,10 +317,10 @@ jobs:
BUILD_TYPE: ${{ inputs.build_type }}
run: |
cmake \
--build . \
--config "${BUILD_TYPE}" \
--parallel "${BUILD_NPROC}" \
--target coverage
--build . \
--config "${BUILD_TYPE}" \
--parallel "${BUILD_NPROC}" \
--target coverage
- name: Upload coverage report
if: ${{ github.repository == 'XRPLF/rippled' && !inputs.build_only && env.COVERAGE_ENABLED == 'true' }}

View File

@@ -38,9 +38,9 @@ jobs:
run: |
DIFF=$(git status --porcelain)
if [ -n "${DIFF}" ]; then
# Print the differences to give the contributor a hint about what to
# expect when running levelization on their own machine.
git diff
echo "${MESSAGE}"
exit 1
# Print the differences to give the contributor a hint about what to
# expect when running levelization on their own machine.
git diff
echo "${MESSAGE}"
exit 1
fi

View File

@@ -48,9 +48,9 @@ jobs:
run: |
DIFF=$(git status --porcelain)
if [ -n "${DIFF}" ]; then
# Print the differences to give the contributor a hint about what to
# expect when running the renaming scripts on their own machine.
git diff
echo "${MESSAGE}"
exit 1
# Print the differences to give the contributor a hint about what to
# expect when running the renaming scripts on their own machine.
git diff
echo "${MESSAGE}"
exit 1
fi

View File

@@ -70,13 +70,13 @@ jobs:
working-directory: ${{ env.BUILD_DIR }}
run: |
cmake \
-G 'Ninja' \
-DCMAKE_TOOLCHAIN_FILE:FILEPATH=build/generators/conan_toolchain.cmake \
-DCMAKE_BUILD_TYPE="${BUILD_TYPE}" \
-Dtests=ON \
-Dwerr=ON \
-Dxrpld=ON \
..
-G 'Ninja' \
-DCMAKE_TOOLCHAIN_FILE:FILEPATH=build/generators/conan_toolchain.cmake \
-DCMAKE_BUILD_TYPE="${BUILD_TYPE}" \
-Dtests=ON \
-Dwerr=ON \
-Dxrpld=ON \
..
# clang-tidy needs headers generated from proto files
- name: Build libxrpl.libpb
@@ -133,7 +133,7 @@ jobs:
- name: Write issue header
if: ${{ steps.run_clang_tidy.outcome != 'success' }}
run: |
cat >"${ISSUE_FILE}" <<EOF
cat > "${ISSUE_FILE}" <<EOF
## Clang-tidy Check Failed
### Clang-tidy Output:
@@ -144,30 +144,30 @@ jobs:
if: ${{ steps.run_clang_tidy.outcome != 'success' }}
run: |
if [ -f "${OUTPUT_FILE}" ]; then
# Extract lines containing 'error:', 'warning:', or 'note:'
grep -E '(error:|warning:|note:)' "${OUTPUT_FILE}" >filtered-output.txt || true
# Extract lines containing 'error:', 'warning:', or 'note:'
grep -E '(error:|warning:|note:)' "${OUTPUT_FILE}" > filtered-output.txt || true
# If filtered output is empty, use original (might be a different error format)
if [ ! -s filtered-output.txt ]; then
cp "${OUTPUT_FILE}" filtered-output.txt
fi
# If filtered output is empty, use original (might be a different error format)
if [ ! -s filtered-output.txt ]; then
cp "${OUTPUT_FILE}" filtered-output.txt
fi
# Truncate if too large
head -c 60000 filtered-output.txt >>"${ISSUE_FILE}"
if [ "$(wc -c <filtered-output.txt)" -gt 60000 ]; then
echo "" >>"${ISSUE_FILE}"
echo "... (output truncated, see artifacts for full output)" >>"${ISSUE_FILE}"
fi
# Truncate if too large
head -c 60000 filtered-output.txt >> "${ISSUE_FILE}"
if [ "$(wc -c < filtered-output.txt)" -gt 60000 ]; then
echo "" >> "${ISSUE_FILE}"
echo "... (output truncated, see artifacts for full output)" >> "${ISSUE_FILE}"
fi
rm filtered-output.txt
rm filtered-output.txt
else
echo "No output file found" >>"${ISSUE_FILE}"
echo "No output file found" >> "${ISSUE_FILE}"
fi
- name: Append issue footer
if: ${{ steps.run_clang_tidy.outcome != 'success' }}
run: |
cat >>"${ISSUE_FILE}" <<EOF
cat >> "${ISSUE_FILE}" <<EOF
\`\`\`
---
@@ -176,7 +176,7 @@ jobs:
- name: Create issue
if: ${{ steps.run_clang_tidy.outcome != 'success' && inputs.create_issue_on_failure }}
uses: XRPLF/actions/create-issue@2b8bc36af85b88bca0dd7bfac2e2dc05f94ad712
uses: XRPLF/actions/create-issue@36d450d12d301e8410c1b7936e5de70c291cbe36
with:
title: "Clang-tidy check failed"
body_file: ${{ env.ISSUE_FILE }}

View File

@@ -39,7 +39,7 @@ jobs:
id: generate
working-directory: .github/scripts/strategy-matrix
run: |
./generate.py --packaging --config=linux.json >>"${GITHUB_OUTPUT}"
./generate.py --packaging --config=linux.json >> "${GITHUB_OUTPUT}"
generate-version:
runs-on: ubuntu-latest

View File

@@ -42,4 +42,4 @@ jobs:
env:
GENERATE_CONFIG: ${{ inputs.os != '' && format('--config={0}.json', inputs.os) || '' }}
GENERATE_OPTION: ${{ inputs.strategy_matrix == 'all' && '--all' || '' }}
run: ./generate.py ${GENERATE_OPTION} ${GENERATE_CONFIG} >>"${GITHUB_OUTPUT}"
run: ./generate.py ${GENERATE_OPTION} ${GENERATE_CONFIG} >> "${GITHUB_OUTPUT}"

View File

@@ -66,19 +66,6 @@ repos:
- id: shfmt
args: [--write, --indent=4, --case-indent=true]
- repo: local
hooks:
- id: format-inline-bash-workflows
name: "format `run:` blocks in workflows/actions"
entry: ./.github/scripts/format-inline-bash.py
language: python
files: ^\.github/(workflows|actions)/.*\.ya?ml$
- id: format-inline-bash-markdown
name: "format ```bash blocks in markdown"
entry: ./.github/scripts/format-inline-bash.py
language: python
files: \.md$
- repo: https://github.com/streetsidesoftware/cspell-cli
rev: 4643f154907327ee0a2c7038f0296e0dd77d9776 # frozen: v10.0.0
hooks:

View File

@@ -151,8 +151,8 @@ git init
git remote add origin git@github.com:XRPLF/conan-center-index.git
git sparse-checkout init
for recipe in "${recipes[@]}"; do
echo "Checking out recipe '${recipe}'..."
git sparse-checkout add recipes/${recipe}
echo "Checking out recipe '${recipe}'..."
git sparse-checkout add recipes/${recipe}
done
git fetch origin master
git checkout master
@@ -180,7 +180,7 @@ the new recipe will be automatically pulled from the official Conan Center.
If you see an error similar to the following after running `conan profile show`:
```text
```bash
ERROR: Invalid setting '17' is not a valid 'settings.compiler.version' value.
Possible values are ['5.0', '5.1', '6.0', '6.1', '7.0', '7.3', '8.0', '8.1',
'9.0', '9.1', '10.0', '11.0', '12.0', '13', '13.0', '13.1', '14', '14.0', '15',

View File

@@ -93,7 +93,6 @@ words:
- daria
- dcmake
- dearmor
- dedented
- deleteme
- demultiplexer
- deserializaton

View File

@@ -7,6 +7,24 @@
namespace xrpl {
namespace detail {
// All-time peak strong/weak ref counts ever observed across all
// IntrusiveRefCounts instances. Read from doSweep periodically.
inline std::atomic<std::uint32_t> kPeakStrongObserved{0};
inline std::atomic<std::uint32_t> kPeakWeakObserved{0};
inline void
updateRefCountPeak(std::atomic<std::uint32_t>& peak, std::uint32_t v) noexcept
{
auto cur = peak.load(std::memory_order_relaxed);
while (v > cur && !peak.compare_exchange_weak(
cur, v, std::memory_order_relaxed))
{
// retry; cur is updated by compare_exchange_weak on failure
}
}
} // namespace detail
/** Action to perform when releasing a strong pointer.
noop: Do nothing. For example, a `noop` action will occur when a count is
@@ -226,13 +244,18 @@ private:
inline void
IntrusiveRefCounts::addStrongRef() const noexcept
{
refCounts_.fetch_add(kStrongDelta, std::memory_order_acq_rel);
auto const prev = refCounts_.fetch_add(kStrongDelta, std::memory_order_acq_rel);
auto const newStrong = static_cast<std::uint32_t>((prev & kStrongMask) + 1);
detail::updateRefCountPeak(detail::kPeakStrongObserved, newStrong);
}
inline void
IntrusiveRefCounts::addWeakRef() const noexcept
{
refCounts_.fetch_add(kWeakDelta, std::memory_order_acq_rel);
auto const prev = refCounts_.fetch_add(kWeakDelta, std::memory_order_acq_rel);
auto const newWeak =
static_cast<std::uint32_t>(((prev & kWeakMask) >> kStrongCountNumBits) + 1);
detail::updateRefCountPeak(detail::kPeakWeakObserved, newWeak);
}
inline ReleaseStrongRefAction
@@ -331,6 +354,11 @@ IntrusiveRefCounts::addWeakReleaseStrongRef() const
(!(prevIntVal & kPartialDestroyStartedMask)),
"xrpl::IntrusiveRefCounts::addWeakReleaseStrongRef : not "
"started partial destroy");
// This op converts one strong into one weak: capture the new
// weak count for the leak-proof peak.
auto const newWeak = static_cast<std::uint32_t>(
((prevIntVal & kWeakMask) >> kStrongCountNumBits) + 1);
detail::updateRefCountPeak(detail::kPeakWeakObserved, newWeak);
return action;
}
}
@@ -377,6 +405,10 @@ IntrusiveRefCounts::checkoutStrongRefFromWeak() const noexcept
desiredValue = curValue + kStrongDelta;
}
// Successful CAS promoted a weak ref to strong. Capture the new strong
// count for the leak-proof peak.
auto const newStrong = static_cast<std::uint32_t>(desiredValue & kStrongMask);
detail::updateRefCountPeak(detail::kPeakStrongObserved, newStrong);
return true;
}
@@ -413,6 +445,8 @@ inline IntrusiveRefCounts::RefCountPair::RefCountPair(IntrusiveRefCounts::FieldT
, partialDestroyStartedBit{v & kPartialDestroyStartedMask}
, partialDestroyFinishedBit{v & kPartialDestroyFinishedMask}
{
detail::updateRefCountPeak(detail::kPeakStrongObserved, strong);
detail::updateRefCountPeak(detail::kPeakWeakObserved, weak);
XRPL_ASSERT(
(strong < kCheckStrongMaxValue && weak < kCheckWeakMaxValue),
"xrpl::IntrusiveRefCounts::RefCountPair(FieldType) : inputs inside "

View File

@@ -1,9 +1,7 @@
#pragma once
#include <xrpl/ledger/OrderBookIndex.h>
#include <xrpl/ledger/RawView.h>
#include <xrpl/ledger/ReadView.h>
#include <xrpl/ledger/TopOfBookCache.h>
#include <xrpl/ledger/detail/RawStateTable.h>
#include <xrpl/protocol/STArray.h>
#include <xrpl/protocol/XRPAmount.h>
@@ -91,17 +89,6 @@ private:
bool open_ = true;
// Per-view top-of-book cache. Lifetime is the view's lifetime; on
// OpenView copy (used to snapshot for parallel apply / batch views),
// the underlying data is copied but counters reset.
mutable TopOfBookCache topOfBookCache_;
// Per-view ordered order-book index (Plan 9). Generalizes the cache from
// "best page" to the full quality-ordered offer sequence, letting the
// crossing path iterate via an in-memory cursor instead of re-walking the
// SHAMap with succ() per offer. Maintained off the same notifications.
mutable OrderBookIndex orderBookIndex_;
public:
OpenView() = delete;
OpenView&
@@ -213,46 +200,6 @@ public:
std::shared_ptr<SLE const>
read(Keylet const& k) const override;
// Top-of-book cache hooks
[[nodiscard]] std::optional<uint256>
topOfBookFirstPage(Book const& book) const override;
void
recordTopOfBook(Book const& book, uint256 const& firstPageKey) const override;
void
notifyOfferInserted(Book const& book, uint256 const& dirKey, uint256 const& offerKey)
const override;
void
notifyOfferDeleted(Book const& book, uint256 const& dirKey, uint256 const& offerKey)
const override;
[[nodiscard]] std::optional<std::vector<uint256>>
orderedBook(Book const& book) const override;
[[nodiscard]] TopOfBookCache const&
topOfBookCache() const noexcept
{
return topOfBookCache_;
}
[[nodiscard]] OrderBookIndex const&
orderBookIndex() const noexcept
{
return orderBookIndex_;
}
// Non-const access for seeding (rebuild-from-state at attach time) and for
// the cursor's lazy populate. The index is auxiliary, so this never affects
// the authoritative state.
[[nodiscard]] OrderBookIndex&
orderBookIndex() noexcept
{
return orderBookIndex_;
}
std::unique_ptr<SlesType::iter_base>
slesBegin() const override;

View File

@@ -1,181 +0,0 @@
#pragma once
#include <xrpl/basics/base_uint.h>
#include <xrpl/ledger/detail/PersistentOrderTree.h>
#include <xrpl/protocol/Book.h>
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <optional>
#include <shared_mutex>
#include <unordered_map>
#include <utility>
#include <vector>
namespace xrpl {
class ReadView;
/** Deterministic, ordered, **persistent** in-memory index of every active order
book.
`BookTip::step()` finds the next offer to cross by calling `ReadView::succ()`
— an O(log N) SHAMap successor walk from the book root, re-done once per
consumed offer. Profiling shows that walk is ~32% of crossing-apply cost.
This index materializes the same quality-ordered offer sequence so iteration
becomes an in-memory cursor advance instead of a trie re-walk.
It generalizes `TopOfBookCache` from "the best directory page" to "the full
ordered book". Like `FlatStateMap`, it is **auxiliary**: the SHAMap remains
the authoritative state and the source of the consensus root. The index is
rebuildable from the SHAMap at any time (`rebuildBook`) and differentially
validated against it (`validateMatchesShaMap`); a divergence is a bug in the
maintenance hooks, never a fallback.
**Persistence.** Each book's offers live in an immutable, structurally-shared
weight-balanced tree ([[detail/PersistentOrderTree.h]]). `clone()` copies only
the per-book `shared_ptr` roots (O(#books)), not the offers — so the
open-ledger copy-on-write (`OpenView` copy per `modify()`) preserves the index
cheaply and it stays warm across transactions, instead of cold-starting and
rebuilding per tx. Immutable nodes also make the COW rollback of a discarded
sandbox free: it simply drops its own root pointers.
Ordering invariant (the load-bearing property for bit-exact crossing):
- Books are keyed by `Book` (which already carries the permissioned-DEX
`domain`), so each book — open or domain — is indexed independently.
- Within a book, the tree is keyed by `(dirRoot, insertSeq)`. `dirRoot` is
the quality-directory root key; ascending == best-quality-first ==
`succ()` order. `insertSeq` is a per-book monotonic counter capturing
directory append order; since `dirRemove` preserves relative order and
offer keys are never reused, in-order traversal reproduces the SHAMap
directory walk byte-for-byte.
Maintenance drives `insertOffer`/`deleteOffer` from the offer-mutation
notifications (`notifyOfferInserted`/`notifyOfferDeleted`), which fire with
the quality-directory root key and the offer key.
*/
class OrderBookIndex
{
public:
OrderBookIndex() = default;
/** Move-construct by locking the source and stealing its book map.
Counters are not transferred (a fresh view starts its own accounting). */
OrderBookIndex(OrderBookIndex&& other);
OrderBookIndex(OrderBookIndex const&) = delete;
OrderBookIndex&
operator=(OrderBookIndex const&) = delete;
OrderBookIndex&
operator=(OrderBookIndex&&) = delete;
/** Cheap structural copy: clones the per-book tree roots (O(#books)
shared_ptr copies), sharing all offer nodes. Used by the `OpenView` copy
ctor so the index stays warm across the open-ledger COW. Counters reset. */
[[nodiscard]] OrderBookIndex
clone() const;
// --- maintenance (apply-path hooks) ---
/** Record that `offerKey` was inserted into `book` at quality-directory root
`dirRoot`. Appended (next insertSeq) so it sorts after same-level offers,
preserving directory order. */
void
insertOffer(Book const& book, uint256 const& dirRoot, uint256 const& offerKey);
/** Record that `offerKey` was removed from `book` at quality-directory root
`dirRoot`. The book is dropped when it empties. Removing an absent key is
a no-op. */
void
deleteOffer(Book const& book, uint256 const& dirRoot, uint256 const& offerKey);
// --- ordered read access (BookTip seam) ---
/** All offer keys of `book`, best-quality-first, directory order within a
level. Empty if the book is absent. */
[[nodiscard]] std::vector<uint256>
flatten(Book const& book) const;
/** The best (first) offer key of `book`, or nullopt if absent. */
[[nodiscard]] std::optional<uint256>
firstOffer(Book const& book) const;
// --- rebuild / validation (composition with the authoritative SHAMap) ---
/** Repopulate `book` from `view` by the canonical quality-ordered walk
(`succ()` over directory roots + directory iteration within each). */
void
rebuildBook(ReadView const& view, Book const& book);
/** True iff the maintained sequence for `book` equals a fresh walk of
`view`. The differential invariant. */
[[nodiscard]] bool
validateMatchesShaMap(ReadView const& view, Book const& book) const;
// --- bookkeeping ---
/** True if `book` has an entry (at least one offer). O(1). Present implies
non-empty (empty books are dropped). */
[[nodiscard]] bool
contains(Book const& book) const;
void
eraseBook(Book const& book);
void
clear();
[[nodiscard]] std::size_t
bookCount() const;
[[nodiscard]] std::size_t
offerCount(Book const& book) const;
[[nodiscard]] std::uint64_t
inserts() const noexcept
{
return inserts_.load(std::memory_order_relaxed);
}
[[nodiscard]] std::uint64_t
deletes() const noexcept
{
return deletes_.load(std::memory_order_relaxed);
}
[[nodiscard]] std::uint64_t
rebuilds() const noexcept
{
return rebuilds_.load(std::memory_order_relaxed);
}
// --- operator-facing kill switch (mirrors TopOfBookCache) ---
[[nodiscard]] static bool
enabled() noexcept;
static void
setEnabled(bool on) noexcept;
private:
struct BookState
{
detail::OrderTreePtr root; // persistent (dirRoot, insertSeq) -> offerKey
std::uint64_t nextSeq{0}; // per-book monotonic append counter
};
// Canonical quality-ordered walk of `book` in `view`: (dirRoot, offerKey)
// for each offer, best-quality-first, directory order within a level.
[[nodiscard]] static std::vector<std::pair<uint256, uint256>>
walkBook(ReadView const& view, Book const& book);
mutable std::shared_mutex mutex_;
std::unordered_map<Book, BookState> books_;
std::atomic<std::uint64_t> inserts_{0};
std::atomic<std::uint64_t> deletes_{0};
std::atomic<std::uint64_t> rebuilds_{0};
};
} // namespace xrpl

View File

@@ -3,7 +3,6 @@
#include <xrpl/basics/chrono.h>
#include <xrpl/beast/hash/uhash.h>
#include <xrpl/ledger/detail/ReadViewFwdRange.h>
#include <xrpl/protocol/Book.h>
#include <xrpl/protocol/Fees.h>
#include <xrpl/protocol/IOUAmount.h>
#include <xrpl/protocol/Indexes.h>
@@ -17,7 +16,6 @@
#include <cstdint>
#include <optional>
#include <unordered_set>
#include <vector>
namespace xrpl {
@@ -190,68 +188,6 @@ public:
return count;
}
//
// Top-of-book cache hooks
//
// The default implementations make every non-overriding view a no-op
// pass-through, so non-orderbook code is unaffected. OpenView overrides
// these to maintain a real `TopOfBookCache`; views that wrap a base
// (ApplyViewBase, PaymentSandbox, ...) delegate to that base.
/** Return the cached keylet of the best (lowest-keyed) directory page
for `book`, if known. std::nullopt forces a `succ()` fallback.
*/
[[nodiscard]] virtual std::optional<uint256>
topOfBookFirstPage(Book const& book) const
{
return std::nullopt;
}
/** Populate the cache after a `succ()`-driven discovery. Called from
the cold path of `BookTip::step()`.
*/
virtual void
recordTopOfBook(Book const& book, uint256 const& firstPageKey) const
{
}
/** Apply-path notification: an offer was inserted into `book` at
directory keylet `dirKey`. The cache may use this to update or
invalidate its entry; the call must be safe under any base view.
*/
virtual void
notifyOfferInserted(Book const& book, uint256 const& dirKey, uint256 const& offerKey) const
{
}
/** Apply-path notification: an offer was deleted from `book` at
directory keylet `dirKey`. If the deleted offer was on the
cached top page, the cache invalidates that entry.
`offerKey` is the deleted offer's ledger key — unused by the cache,
consumed by the order-book index.
*/
virtual void
notifyOfferDeleted(Book const& book, uint256 const& dirKey, uint256 const& offerKey) const
{
}
/** Return `book`'s offer keys best-quality-first (the order the crossing
path consumes them), or std::nullopt to force the `succ()`-based walk.
Lets `BookTip` iterate the book from an in-memory cursor instead of
re-walking the SHAMap with `succ()` per offer. A returned vector is
guaranteed complete for `book` — implementations rebuild from the
authoritative state on a miss, so the cursor can never under-include.
Empty/absent books return nullopt (the cheap `succ()` path finds
nothing). Default: no index, always nullopt.
*/
[[nodiscard]] virtual std::optional<std::vector<uint256>>
orderedBook(Book const& book) const
{
return std::nullopt;
}
// used by the implementation
[[nodiscard]] virtual std::unique_ptr<SlesType::iter_base>
slesBegin() const = 0;

View File

@@ -35,7 +35,6 @@ public:
apply(RawView& to)
{
items_.apply(to);
flushTopOfBookNotifications();
}
};

View File

@@ -1,163 +0,0 @@
#pragma once
#include <xrpl/basics/base_uint.h>
#include <xrpl/protocol/Book.h>
#include <xrpl/protocol/Protocol.h>
#include <atomic>
#include <cstdint>
#include <mutex>
#include <optional>
#include <unordered_map>
namespace xrpl {
/** One entry in the top-of-book cache.
Records the keylet of the best-quality (lowest-keyed) directory page
for a single order book at the time the entry was recorded.
*/
struct TopOfBookEntry
{
/// Keylet of the best directory page for the book.
uint256 firstPageKey;
/// Quality bits encoded in firstPageKey (decoded for fast comparison).
std::uint64_t bestQuality{0};
/// Ledger sequence at which this entry was populated.
LedgerIndex asOfLedger{0};
};
/** Cache of "best directory page" keylet per active order book.
Reads of the top of an order book usually return the same directory page
over and over, but `BookTip::step()` re-walks the SHAMap on every call.
This cache memoizes that result. Lookups become a single hash-map probe;
the SHAMap successor walk happens only on cold or invalidated entries.
The cache is auxiliary — invalidating an entry is always safe, since the
next read repopulates lazily via `ReadView::succ()`. That property is what
lets the cache ship without an amendment.
Maintenance rules, applied at the apply path:
- **Offer inserted**: if the new offer's directory keylet is at-or-better
than the cached top, update the entry. Otherwise no-op.
- **Offer deleted**: if the deleted offer was on the cached top page,
invalidate. Otherwise no-op.
A best-page key is `keylet::quality(keylet::kBook(book), rate).key`. All
pages of a single book share the same prefix, so lower uint256 key =
better quality. Comparisons in this file rely on that ordering.
*/
class TopOfBookCache
{
public:
TopOfBookCache() = default;
/** Copy-construct (used when snapshotting open->closed ledger).
Hit/miss/invalidation counters are not copied; only the data is.
*/
TopOfBookCache(TopOfBookCache const& other);
/** Move-construct by locking the source and stealing its map.
Needed because views that own a cache (OpenView) are moveable;
std::mutex is not, so the move is implemented via lock-and-move.
Counters are not transferred.
*/
TopOfBookCache(TopOfBookCache&& other);
TopOfBookCache&
operator=(TopOfBookCache const&) = delete;
TopOfBookCache&
operator=(TopOfBookCache&&) = delete;
/** Look up the cached top of `book`.
Returns std::nullopt on miss. Hit/miss counters are updated.
*/
[[nodiscard]] std::optional<TopOfBookEntry>
get(Book const& book) const;
/** Record (or overwrite) a top-of-book entry for `book`.
Called from the cold path after `succ()` discovers the first page.
*/
void
record(Book const& book, uint256 const& firstPageKey, LedgerIndex seq);
/** Notify the cache that an offer was inserted into `book` at directory
keylet `dirKey`.
If the new keylet is better than (less than) the cached top, the entry
is updated. If it is equal, no change. If worse, no change.
If no entry exists for `book`, this is a no-op: the next read will
populate from `succ()`.
*/
void
onOfferInsert(Book const& book, uint256 const& dirKey, LedgerIndex seq);
/** Notify the cache that an offer was deleted from `book` at directory
keylet `dirKey`.
If the delete was on the cached top page, invalidate (the page may
now be empty, or the offer count is irrelevant — next read repopulates).
Otherwise no-op.
*/
void
onOfferDelete(Book const& book, uint256 const& dirKey);
/** Drop the entry for `book` unconditionally.
Used as a safety hatch and by tests.
*/
void
invalidate(Book const& book);
/** Drop every entry. */
void
clear();
[[nodiscard]] std::size_t
size() const;
[[nodiscard]] std::uint64_t
hits() const noexcept
{
return hits_.load(std::memory_order_relaxed);
}
[[nodiscard]] std::uint64_t
misses() const noexcept
{
return misses_.load(std::memory_order_relaxed);
}
[[nodiscard]] std::uint64_t
invalidations() const noexcept
{
return invalidations_.load(std::memory_order_relaxed);
}
/** Operator-facing kill switch.
When false, `BookTip` skips cache consults and writes entirely,
falling back to plain `succ()`. Default is true.
*/
[[nodiscard]] static bool
enabled() noexcept;
static void
setEnabled(bool on) noexcept;
private:
mutable std::mutex mutex_;
std::unordered_map<Book, TopOfBookEntry> map_;
mutable std::atomic<std::uint64_t> hits_{0};
mutable std::atomic<std::uint64_t> misses_{0};
std::atomic<std::uint64_t> invalidations_{0};
};
} // namespace xrpl

View File

@@ -3,13 +3,8 @@
#include <xrpl/ledger/ApplyView.h>
#include <xrpl/ledger/ReadView.h>
#include <xrpl/ledger/detail/ApplyStateTable.h>
#include <xrpl/protocol/Book.h>
#include <xrpl/protocol/XRPAmount.h>
#include <unordered_set>
#include <utility>
#include <vector>
namespace xrpl::detail {
class ApplyViewBase : public ApplyView, public RawView
@@ -48,26 +43,6 @@ public:
[[nodiscard]] std::shared_ptr<SLE const>
read(Keylet const& k) const override;
// Top-of-book cache hooks — delegated to the wrapped base view so
// sandboxed views share the underlying open-ledger cache.
[[nodiscard]] std::optional<uint256>
topOfBookFirstPage(Book const& book) const override;
void
recordTopOfBook(Book const& book, uint256 const& firstPageKey) const override;
void
notifyOfferInserted(Book const& book, uint256 const& dirKey, uint256 const& offerKey)
const override;
void
notifyOfferDeleted(Book const& book, uint256 const& dirKey, uint256 const& offerKey)
const override;
[[nodiscard]] std::optional<std::vector<uint256>>
orderedBook(Book const& book) const override;
[[nodiscard]] std::unique_ptr<SlesType::iter_base>
slesBegin() const override;
@@ -120,45 +95,10 @@ public:
void
rawDestroyXRP(XRPAmount const& feeDrops) override;
/** Flush buffered top-of-book notifications to the wrapped base view.
Called by `Sandbox::apply` (and similar commit points) after the
state table itself has been applied. Notifications buffered during
the sandbox's lifetime are replayed against `base_` in insertion
order so the parent cache only sees changes that actually commit.
*/
void
flushTopOfBookNotifications() const;
/** Discard buffered notifications (e.g. when a sandbox is dropped
without applying). Safe to call multiple times.
*/
void
discardTopOfBookNotifications() const noexcept;
protected:
ApplyFlags flags_;
ReadView const* base_;
detail::ApplyStateTable items_;
// Top-of-book cache notifications are buffered here for the lifetime
// of the sandbox and only flushed to `base_` on `apply()`. This keeps
// rolled-back transactions (e.g. FillOrKill via the sbCancel branch
// of OfferCreate) from polluting the parent's cache.
//
// `dirtyBooks_` records every book mutated by buffered notifications;
// reads against `topOfBookFirstPage` skip the cache for these books so
// we never observe our own un-committed state. Outside of the dirty
// set, the parent's cache is trusted as usual.
struct OfferNote
{
Book book;
uint256 dirKey;
uint256 offerKey;
bool isDelete;
};
mutable std::vector<OfferNote> pendingTopOfBookNotifications_;
mutable std::unordered_set<Book> dirtyBooks_;
};
} // namespace xrpl::detail

View File

@@ -1,257 +0,0 @@
#pragma once
#include <xrpl/basics/base_uint.h>
#include <cstdint>
#include <memory>
#include <optional>
#include <vector>
namespace xrpl::detail {
/** Persistent (immutable, structurally-shared) ordered tree for the order-book
index.
A weight-balanced BST (Adams BB[α], the family used by Haskell `Data.Map`
and std::map-replacement libraries) of immutable `shared_ptr<const Node>`.
Keyed by `(dirRoot, insertSeq)`:
- `dirRoot` ascending == best-quality-first (book directory pages share a
prefix, quality is in the low bytes — lower key = better quality).
- `insertSeq` ascending within a `dirRoot` == directory append order
(the per-book monotonic counter mirrors `dirAppend`; `dirRemove`
preserves relative order, so this reproduces the directory walk
byte-for-byte).
Operations are persistent via path-copying: insert/delete reallocate only
the O(log n) nodes on the root→leaf path and SHARE every untouched subtree.
A "copy" of a tree is just copying the root `shared_ptr` — O(1) — which is
what lets the order-book index survive the open-ledger copy-on-write cheaply
and stay warm across transactions.
Immutable nodes are safe to share across threads/snapshots without locking.
*/
struct OrderTreeNode
{
uint256 dirRoot;
std::uint64_t insertSeq;
uint256 offerKey;
std::uint32_t size; // subtree node count (balance + rank)
std::shared_ptr<OrderTreeNode const> left;
std::shared_ptr<OrderTreeNode const> right;
};
using OrderTreePtr = std::shared_ptr<OrderTreeNode const>;
// Weight-balance parameters (Adams). delta bounds the size ratio between
// siblings; gamma chooses single vs double rotation.
inline constexpr std::uint32_t kOtDelta = 3;
inline constexpr std::uint32_t kOtGamma = 2;
[[nodiscard]] inline std::uint32_t
otSize(OrderTreePtr const& t) noexcept
{
return t ? t->size : 0;
}
// -1 / 0 / +1 ordering on (dirRoot, insertSeq).
[[nodiscard]] inline int
otCmp(
uint256 const& aDir,
std::uint64_t aSeq,
uint256 const& bDir,
std::uint64_t bSeq) noexcept
{
if (aDir < bDir)
return -1;
if (bDir < aDir)
return 1;
if (aSeq < bSeq)
return -1;
if (bSeq < aSeq)
return 1;
return 0;
}
[[nodiscard]] inline OrderTreePtr
otNode(
uint256 const& dir,
std::uint64_t seq,
uint256 const& off,
OrderTreePtr l,
OrderTreePtr r)
{
auto n = std::make_shared<OrderTreeNode>();
n->dirRoot = dir;
n->insertSeq = seq;
n->offerKey = off;
n->left = std::move(l);
n->right = std::move(r);
n->size = otSize(n->left) + otSize(n->right) + 1;
return n;
}
// Rebalance a node whose subtrees may violate the weight balance by one step.
[[nodiscard]] inline OrderTreePtr
otBalance(
uint256 const& dir,
std::uint64_t seq,
uint256 const& off,
OrderTreePtr const& l,
OrderTreePtr const& r)
{
auto const ln = otSize(l);
auto const rn = otSize(r);
if (ln + rn <= 1)
return otNode(dir, seq, off, l, r);
if (rn > kOtDelta * ln)
{
// Right-heavy.
auto const& rl = r->left;
auto const& rr = r->right;
if (otSize(rl) < kOtGamma * otSize(rr))
// single left rotation
return otNode(
r->dirRoot,
r->insertSeq,
r->offerKey,
otNode(dir, seq, off, l, rl),
rr);
// double left rotation
return otNode(
rl->dirRoot,
rl->insertSeq,
rl->offerKey,
otNode(dir, seq, off, l, rl->left),
otNode(r->dirRoot, r->insertSeq, r->offerKey, rl->right, rr));
}
if (ln > kOtDelta * rn)
{
// Left-heavy.
auto const& ll = l->left;
auto const& lr = l->right;
if (otSize(lr) < kOtGamma * otSize(ll))
// single right rotation
return otNode(
l->dirRoot,
l->insertSeq,
l->offerKey,
ll,
otNode(dir, seq, off, lr, r));
// double right rotation
return otNode(
lr->dirRoot,
lr->insertSeq,
lr->offerKey,
otNode(l->dirRoot, l->insertSeq, l->offerKey, ll, lr->left),
otNode(dir, seq, off, lr->right, r));
}
return otNode(dir, seq, off, l, r);
}
[[nodiscard]] inline OrderTreePtr
otInsert(OrderTreePtr const& t, uint256 const& dir, std::uint64_t seq, uint256 const& off)
{
if (!t)
return otNode(dir, seq, off, nullptr, nullptr);
int const c = otCmp(dir, seq, t->dirRoot, t->insertSeq);
if (c < 0)
return otBalance(
t->dirRoot, t->insertSeq, t->offerKey, otInsert(t->left, dir, seq, off), t->right);
if (c > 0)
return otBalance(
t->dirRoot, t->insertSeq, t->offerKey, t->left, otInsert(t->right, dir, seq, off));
// Equal key: replace payload (keys are unique in practice; never hit).
return otNode(t->dirRoot, t->insertSeq, off, t->left, t->right);
}
// Remove the minimum node of a non-null tree; write its fields into `outMin`.
[[nodiscard]] inline OrderTreePtr
otDeleteMin(OrderTreePtr const& t, OrderTreeNode& outMin)
{
if (!t->left)
{
outMin = *t;
return t->right;
}
return otBalance(
t->dirRoot, t->insertSeq, t->offerKey, otDeleteMin(t->left, outMin), t->right);
}
// Join two subtrees (all keys in l < all keys in r) by promoting r's minimum.
[[nodiscard]] inline OrderTreePtr
otGlue(OrderTreePtr const& l, OrderTreePtr const& r)
{
if (!l)
return r;
if (!r)
return l;
OrderTreeNode minN;
auto const r2 = otDeleteMin(r, minN);
return otBalance(minN.dirRoot, minN.insertSeq, minN.offerKey, l, r2);
}
[[nodiscard]] inline OrderTreePtr
otDelete(OrderTreePtr const& t, uint256 const& dir, std::uint64_t seq)
{
if (!t)
return nullptr;
int const c = otCmp(dir, seq, t->dirRoot, t->insertSeq);
if (c < 0)
return otBalance(
t->dirRoot, t->insertSeq, t->offerKey, otDelete(t->left, dir, seq), t->right);
if (c > 0)
return otBalance(
t->dirRoot, t->insertSeq, t->offerKey, t->left, otDelete(t->right, dir, seq));
return otGlue(t->left, t->right);
}
// In-order traversal: appends offer keys best-quality-first, append order
// within a level.
inline void
otInorder(OrderTreePtr const& t, std::vector<uint256>& out)
{
if (!t)
return;
otInorder(t->left, out);
out.push_back(t->offerKey);
otInorder(t->right, out);
}
// Leftmost (best) offer key.
[[nodiscard]] inline std::optional<uint256>
otFirst(OrderTreePtr t)
{
if (!t)
return std::nullopt;
while (t->left)
t = t->left;
return t->offerKey;
}
// Find the insertSeq for (dirRoot, offerKey). All nodes sharing a dirRoot form
// a contiguous in-order range that may straddle a node's two children, so when
// dirRoot matches we must check the node and both subtrees. O(level-size) worst
// case; effectively O(log n) for front deletions (crossing consumes front-first
// and the target is then the level's leftmost remaining node).
[[nodiscard]] inline std::optional<std::uint64_t>
otFindSeq(OrderTreePtr const& t, uint256 const& dir, uint256 const& off)
{
if (!t)
return std::nullopt;
if (dir < t->dirRoot)
return otFindSeq(t->left, dir, off);
if (t->dirRoot < dir)
return otFindSeq(t->right, dir, off);
if (t->offerKey == off)
return t->insertSeq;
if (auto const l = otFindSeq(t->left, dir, off))
return l;
return otFindSeq(t->right, dir, off);
}
} // namespace xrpl::detail

View File

@@ -15,8 +15,8 @@ Generation requires a one-time setup step to create a virtual environment
and install Python dependencies, followed by running the generation target:
```bash
cmake --build . --target setup_code_gen # create venv and install dependencies (once)
cmake --build . --target code_gen # generate code
cmake --build . --target setup_code_gen # create venv and install dependencies (once)
cmake --build . --target code_gen # generate code
```
By default, `CODEGEN_VENV_DIR` points to `.venv` in the project root. The

View File

@@ -4,10 +4,6 @@
#include <xrpl/protocol/Indexes.h>
#include <xrpl/protocol/Quality.h>
#include <cstddef>
#include <cstdint>
#include <vector>
namespace xrpl {
class Logs;
@@ -21,7 +17,6 @@ class BookTip
private:
ApplyView& view_;
bool valid_{false};
Book originalBook_;
uint256 book_;
uint256 end_;
uint256 dir_;
@@ -29,15 +24,6 @@ private:
std::shared_ptr<SLE> entry_;
Quality quality_{};
// Plan 9: when the order-book index supplies an ordered offer-key snapshot
// for this book, iterate it instead of re-walking the SHAMap with succ()
// per offer. `useCursor_` is decided on the first step; thereafter the two
// paths are mutually exclusive for the iterator's lifetime.
std::vector<uint256> cursor_;
std::size_t cursorPos_{0};
bool useCursor_{false};
std::uint64_t lastCursorQuality_{0};
public:
/** Create the iterator. */
BookTip(ApplyView& view, Book const& book);

View File

@@ -74,10 +74,10 @@ VERSION=2.4.0-local
PKG_RELEASE=1
docker run --rm \
-v "$(pwd):/src" \
-w /src \
"$IMAGE" \
./package/build_pkg.sh --pkg-version "$VERSION" --pkg-release "$PKG_RELEASE"
-v "$(pwd):/src" \
-w /src \
"$IMAGE" \
./package/build_pkg.sh --pkg-version "$VERSION" --pkg-release "$PKG_RELEASE"
# Output:
# build/debbuild/*.deb (DEB + dbgsym .ddeb)
@@ -92,12 +92,12 @@ needed, but the host toolchain replaces the pinned CI image:
```bash
cmake \
-Dxrpld=ON \
-Dxrpld_version=2.4.0-local \
-Dtests=OFF \
..
-Dxrpld=ON \
-Dxrpld_version=2.4.0-local \
-Dtests=OFF \
..
cmake --build . --target package # deb on Debian/Ubuntu, rpm on RHEL
cmake --build . --target package # deb on Debian/Ubuntu, rpm on RHEL
```
The `cmake/XrplPackaging.cmake` module defines the target only if at least one

View File

@@ -64,75 +64,6 @@ ApplyViewBase::read(Keylet const& k) const
return items_.read(*base_, k);
}
std::optional<uint256>
ApplyViewBase::topOfBookFirstPage(Book const& book) const
{
// Reads inside a sandbox that has already mutated `book` cannot use
// the parent's cache: the parent's view of the top doesn't reflect
// our buffered changes yet. Fall back to succ() in that case.
if (dirtyBooks_.find(book) != dirtyBooks_.end())
return std::nullopt;
return base_->topOfBookFirstPage(book);
}
void
ApplyViewBase::recordTopOfBook(Book const& book, uint256 const& firstPageKey) const
{
// Don't populate the parent cache from inside a dirty sandbox view —
// our succ() result may reflect uncommitted mutations from the parent's
// perspective.
if (dirtyBooks_.find(book) != dirtyBooks_.end())
return;
base_->recordTopOfBook(book, firstPageKey);
}
void
ApplyViewBase::notifyOfferInserted(Book const& book, uint256 const& dirKey, uint256 const& offerKey)
const
{
dirtyBooks_.insert(book);
pendingTopOfBookNotifications_.emplace_back(book, dirKey, offerKey, /*isDelete=*/false);
}
void
ApplyViewBase::notifyOfferDeleted(Book const& book, uint256 const& dirKey, uint256 const& offerKey)
const
{
dirtyBooks_.insert(book);
pendingTopOfBookNotifications_.emplace_back(book, dirKey, offerKey, /*isDelete=*/true);
}
std::optional<std::vector<uint256>>
ApplyViewBase::orderedBook(Book const& book) const
{
// Unlike topOfBookFirstPage, do NOT skip dirty books: the cursor is taken
// once and iterated locally, and it self-heals any offer this sandbox has
// buffered-deleted via peek()-null-skip in BookTip. So always delegate to
// the (immutable-for-this-crossing) base index.
return base_->orderedBook(book);
}
void
ApplyViewBase::flushTopOfBookNotifications() const
{
for (auto const& note : pendingTopOfBookNotifications_)
{
if (note.isDelete)
base_->notifyOfferDeleted(note.book, note.dirKey, note.offerKey);
else
base_->notifyOfferInserted(note.book, note.dirKey, note.offerKey);
}
pendingTopOfBookNotifications_.clear();
dirtyBooks_.clear();
}
void
ApplyViewBase::discardTopOfBookNotifications() const noexcept
{
pendingTopOfBookNotifications_.clear();
dirtyBooks_.clear();
}
auto
ApplyViewBase::slesBegin() const -> std::unique_ptr<SlesType::iter_base>
{

View File

@@ -31,9 +31,7 @@ ApplyViewImpl::apply(
bool isDryRun,
beast::Journal j)
{
auto meta = items_.apply(to, tx, ter, deliver_, parentBatchId, isDryRun, j);
flushTopOfBookNotifications();
return meta;
return items_.apply(to, tx, ter, deliver_, parentBatchId, isDryRun, j);
}
std::size_t

View File

@@ -86,12 +86,7 @@ OpenView::OpenView(OpenView const& rhs)
, base_{rhs.base_}
, items_{rhs.items_}
, hold_{rhs.hold_}
, open_{rhs.open_}
// Plan 9 P9.6: carry the persistent order-book index forward on the
// open-ledger COW (modify() copies the OpenView per tx). clone() is O(#books)
// shared_ptr copies sharing all offer nodes, so the index stays warm across
// transactions instead of cold-starting and rebuilding per tx.
, orderBookIndex_{rhs.orderBookIndex_.clone()} {};
, open_{rhs.open_} {};
OpenView::OpenView(OpenLedgerT, ReadView const* base, Rules rules, std::shared_ptr<void const> hold)
: monotonicResource_{
@@ -174,71 +169,6 @@ OpenView::read(Keylet const& k) const
return items_.read(*base_, k);
}
std::optional<uint256>
OpenView::topOfBookFirstPage(Book const& book) const
{
if (!TopOfBookCache::enabled())
return std::nullopt;
if (auto const entry = topOfBookCache_.get(book))
return entry->firstPageKey;
return std::nullopt;
}
void
OpenView::recordTopOfBook(Book const& book, uint256 const& firstPageKey) const
{
if (!TopOfBookCache::enabled())
return;
topOfBookCache_.record(book, firstPageKey, header_.seq);
}
void
OpenView::notifyOfferInserted(Book const& book, uint256 const& dirKey, uint256 const& offerKey)
const
{
// Maintain only books already in the index: a book enters the index only
// via rebuildBook (which captures the full authoritative state), so it is
// always complete. Inserting into an absent book would create a PARTIAL
// entry (missing pre-existing offers) that a later crossing would trust —
// wrong. Absent books are populated completely on first read (orderedBook's
// rebuild-on-absent). This mirrors TopOfBookCache::onOfferInsert's no-op.
if (OrderBookIndex::enabled() && orderBookIndex_.contains(book))
orderBookIndex_.insertOffer(book, dirKey, offerKey);
if (!TopOfBookCache::enabled())
return;
topOfBookCache_.onOfferInsert(book, dirKey, header_.seq);
}
void
OpenView::notifyOfferDeleted(Book const& book, uint256 const& dirKey, uint256 const& offerKey)
const
{
if (OrderBookIndex::enabled())
orderBookIndex_.deleteOffer(book, dirKey, offerKey);
if (!TopOfBookCache::enabled())
return;
topOfBookCache_.onOfferDelete(book, dirKey);
}
std::optional<std::vector<uint256>>
OpenView::orderedBook(Book const& book) const
{
if (!OrderBookIndex::enabled())
return std::nullopt;
// Guarantee completeness: if the index has no entry for `book`, populate it
// from the authoritative state before serving the cursor. A maintained,
// already-present book skips this (the steady-state fast path). The index
// never holds a partial book, so the cursor can't under-include.
if (!orderBookIndex_.contains(book))
orderBookIndex_.rebuildBook(*this, book);
auto offers = orderBookIndex_.flatten(book);
if (offers.empty())
return std::nullopt; // genuinely empty book — let succ() find nothing
return offers;
}
auto
OpenView::slesBegin() const -> std::unique_ptr<SlesType::iter_base>
{

View File

@@ -1,199 +0,0 @@
#include <xrpl/ledger/OrderBookIndex.h>
#include <xrpl/ledger/ReadView.h>
#include <xrpl/ledger/helpers/DirectoryHelpers.h>
#include <xrpl/protocol/Indexes.h>
#include <xrpl/protocol/STLedgerEntry.h>
#include <atomic>
namespace xrpl {
namespace {
// Operator-facing kill switch. Defaults to true; set false via setEnabled()
// to bypass the index entirely and fall back to baseline succ() iteration
// without a restart (mirrors TopOfBookCache).
std::atomic<bool> gEnabled{true};
} // namespace
bool
OrderBookIndex::enabled() noexcept
{
return gEnabled.load(std::memory_order_relaxed);
}
void
OrderBookIndex::setEnabled(bool on) noexcept
{
gEnabled.store(on, std::memory_order_relaxed);
}
OrderBookIndex::OrderBookIndex(OrderBookIndex&& other)
{
std::unique_lock lock(other.mutex_);
books_ = std::move(other.books_);
}
OrderBookIndex
OrderBookIndex::clone() const
{
OrderBookIndex out;
std::shared_lock lock(mutex_);
// Copying the map copies each BookState — a shared_ptr root (O(1), shares
// all offer nodes) + the counter. Total O(#books).
out.books_ = books_;
return out;
}
void
OrderBookIndex::insertOffer(Book const& book, uint256 const& dirRoot, uint256 const& offerKey)
{
std::unique_lock lock(mutex_);
auto& st = books_[book];
st.root = detail::otInsert(st.root, dirRoot, st.nextSeq++, offerKey);
inserts_.fetch_add(1, std::memory_order_relaxed);
}
void
OrderBookIndex::deleteOffer(Book const& book, uint256 const& dirRoot, uint256 const& offerKey)
{
std::unique_lock lock(mutex_);
auto const it = books_.find(book);
if (it == books_.end())
return;
auto const seq = detail::otFindSeq(it->second.root, dirRoot, offerKey);
if (!seq)
return;
it->second.root = detail::otDelete(it->second.root, dirRoot, *seq);
deletes_.fetch_add(1, std::memory_order_relaxed);
if (!it->second.root)
books_.erase(it);
}
std::vector<uint256>
OrderBookIndex::flatten(Book const& book) const
{
std::vector<uint256> out;
std::shared_lock lock(mutex_);
auto const it = books_.find(book);
if (it != books_.end())
detail::otInorder(it->second.root, out);
return out;
}
std::optional<uint256>
OrderBookIndex::firstOffer(Book const& book) const
{
std::shared_lock lock(mutex_);
auto const it = books_.find(book);
if (it == books_.end())
return std::nullopt;
return detail::otFirst(it->second.root);
}
std::vector<std::pair<uint256, uint256>>
OrderBookIndex::walkBook(ReadView const& view, Book const& book)
{
// Canonical quality-ordered enumeration, mirroring NetworkOPs::getBookPage
// and BookTip: succ() over directory roots in [bookBase, bookEnd), then
// cdirFirst/cdirNext across each root's pages. uTip advances to the found
// root, so the next succ() yields the next-worse quality; a root's overflow
// pages live outside [bookBase, bookEnd) and are reached only via sfIndexNext
// inside cdirNext, never by succ().
std::vector<std::pair<uint256, uint256>> out;
uint256 const bookBase = getBookBase(book);
uint256 const bookEnd = getQualityNext(bookBase);
uint256 uTip = bookBase;
for (;;)
{
auto const next = view.succ(uTip, bookEnd);
if (!next)
break;
uint256 const dirRoot = *next;
std::shared_ptr<SLE const> page;
unsigned int index = 0;
uint256 offerKey;
if (cdirFirst(view, dirRoot, page, index, offerKey))
{
do
{
out.emplace_back(dirRoot, offerKey);
} while (cdirNext(view, dirRoot, page, index, offerKey));
}
uTip = dirRoot;
}
return out;
}
void
OrderBookIndex::rebuildBook(ReadView const& view, Book const& book)
{
auto const walked = walkBook(view, book);
BookState st;
// Inserting in walk order assigns ascending insertSeq, so in-order traversal
// reproduces the walk exactly.
for (auto const& [dirRoot, offerKey] : walked)
st.root = detail::otInsert(st.root, dirRoot, st.nextSeq++, offerKey);
std::unique_lock lock(mutex_);
if (!st.root)
books_.erase(book);
else
books_[book] = std::move(st);
rebuilds_.fetch_add(1, std::memory_order_relaxed);
}
bool
OrderBookIndex::validateMatchesShaMap(ReadView const& view, Book const& book) const
{
std::vector<uint256> fresh;
for (auto const& [dirRoot, offerKey] : walkBook(view, book))
fresh.push_back(offerKey);
return fresh == flatten(book);
}
bool
OrderBookIndex::contains(Book const& book) const
{
std::shared_lock lock(mutex_);
return books_.find(book) != books_.end();
}
void
OrderBookIndex::eraseBook(Book const& book)
{
std::unique_lock lock(mutex_);
books_.erase(book);
}
void
OrderBookIndex::clear()
{
std::unique_lock lock(mutex_);
books_.clear();
}
std::size_t
OrderBookIndex::bookCount() const
{
std::shared_lock lock(mutex_);
return books_.size();
}
std::size_t
OrderBookIndex::offerCount(Book const& book) const
{
std::shared_lock lock(mutex_);
auto const it = books_.find(book);
if (it == books_.end())
return 0;
return detail::otSize(it->second.root);
}
} // namespace xrpl

View File

@@ -453,7 +453,6 @@ PaymentSandbox::apply(RawView& to)
{
XRPL_ASSERT(!ps_, "xrpl::PaymentSandbox::apply : non-null sandbox");
items_.apply(to);
flushTopOfBookNotifications();
}
void
@@ -462,7 +461,6 @@ PaymentSandbox::apply(PaymentSandbox& to)
XRPL_ASSERT(ps_ == &to, "xrpl::PaymentSandbox::apply : matching sandbox");
items_.apply(to);
tab_.apply(to.tab_);
flushTopOfBookNotifications();
}
XRPAmount

View File

@@ -1,123 +0,0 @@
#include <xrpl/ledger/TopOfBookCache.h>
#include <xrpl/protocol/Indexes.h>
#include <atomic>
#include <mutex>
namespace xrpl {
namespace {
// Operator-facing kill switch. Defaults to true; set false via setEnabled()
// to bypass the cache entirely (e.g. in case a workload exposes a bug, the
// node can be brought back to baseline succ() behavior without restart).
std::atomic<bool> gEnabled{true};
} // namespace
bool
TopOfBookCache::enabled() noexcept
{
return gEnabled.load(std::memory_order_relaxed);
}
void
TopOfBookCache::setEnabled(bool on) noexcept
{
gEnabled.store(on, std::memory_order_relaxed);
}
TopOfBookCache::TopOfBookCache(TopOfBookCache const& other)
{
std::lock_guard lock(other.mutex_);
map_ = other.map_;
}
TopOfBookCache::TopOfBookCache(TopOfBookCache&& other)
{
std::lock_guard lock(other.mutex_);
map_ = std::move(other.map_);
}
std::optional<TopOfBookEntry>
TopOfBookCache::get(Book const& book) const
{
std::lock_guard lock(mutex_);
auto it = map_.find(book);
if (it == map_.end())
{
misses_.fetch_add(1, std::memory_order_relaxed);
return std::nullopt;
}
hits_.fetch_add(1, std::memory_order_relaxed);
return it->second;
}
void
TopOfBookCache::record(Book const& book, uint256 const& firstPageKey, LedgerIndex seq)
{
std::lock_guard lock(mutex_);
auto& entry = map_[book];
entry.firstPageKey = firstPageKey;
entry.bestQuality = getQuality(firstPageKey);
entry.asOfLedger = seq;
}
void
TopOfBookCache::onOfferInsert(Book const& book, uint256 const& dirKey, LedgerIndex seq)
{
std::lock_guard lock(mutex_);
auto it = map_.find(book);
if (it == map_.end())
{
// No cached top — defer to the next reader, which populates lazily.
return;
}
// Lower keylet == better quality (pages share the book prefix, quality
// bits are encoded in the low bytes).
if (dirKey < it->second.firstPageKey)
{
it->second.firstPageKey = dirKey;
it->second.bestQuality = getQuality(dirKey);
it->second.asOfLedger = seq;
}
}
void
TopOfBookCache::onOfferDelete(Book const& book, uint256 const& dirKey)
{
std::lock_guard lock(mutex_);
auto it = map_.find(book);
if (it == map_.end())
return;
if (it->second.firstPageKey == dirKey)
{
map_.erase(it);
invalidations_.fetch_add(1, std::memory_order_relaxed);
}
}
void
TopOfBookCache::invalidate(Book const& book)
{
std::lock_guard lock(mutex_);
if (map_.erase(book) != 0)
invalidations_.fetch_add(1, std::memory_order_relaxed);
}
void
TopOfBookCache::clear()
{
std::lock_guard lock(mutex_);
map_.clear();
}
std::size_t
TopOfBookCache::size() const
{
std::lock_guard lock(mutex_);
return map_.size();
}
} // namespace xrpl

View File

@@ -5,46 +5,17 @@
#include <xrpl/beast/utility/instrumentation.h>
#include <xrpl/ledger/ApplyView.h>
#include <xrpl/ledger/helpers/AccountRootHelpers.h>
#include <xrpl/protocol/Book.h>
#include <xrpl/protocol/Indexes.h>
#include <xrpl/protocol/LedgerFormats.h>
#include <xrpl/protocol/SField.h>
#include <xrpl/protocol/STAmount.h>
#include <xrpl/protocol/STArray.h> // IWYU pragma: keep
#include <xrpl/protocol/STLedgerEntry.h>
#include <xrpl/protocol/TER.h>
#include <memory>
#include <optional>
namespace xrpl {
namespace {
// Reconstruct the Book this offer was placed on. The primary directory uses
// the offer's sfDomainID (if any); the open-book directory of a hybrid offer
// is the same in/out assets with no domain.
Book
primaryBookFromOffer(SLE const& sle)
{
auto const takerPays = sle.getFieldAmount(sfTakerPays);
auto const takerGets = sle.getFieldAmount(sfTakerGets);
std::optional<uint256> domain;
if (sle.isFieldPresent(sfDomainID))
domain = sle.getFieldH256(sfDomainID);
return Book{takerPays.asset(), takerGets.asset(), domain};
}
Book
openBookFromOffer(SLE const& sle)
{
auto const takerPays = sle.getFieldAmount(sfTakerPays);
auto const takerGets = sle.getFieldAmount(sfTakerGets);
return Book{takerPays.asset(), takerGets.asset(), std::nullopt};
}
} // namespace
TER
offerDelete(ApplyView& view, std::shared_ptr<SLE> const& sle, beast::Journal j)
{
@@ -66,12 +37,6 @@ offerDelete(ApplyView& view, std::shared_ptr<SLE> const& sle, beast::Journal j)
return tefBAD_LEDGER; // LCOV_EXCL_LINE
}
// Plan 8: notify the top-of-book cache that the primary book lost an
// offer at `uDirectory`. If this was the cached top page the cache
// invalidates; otherwise no-op. uDirectory is the first-page keylet of
// the offer's quality bucket — i.e. exactly what the cache stores.
view.notifyOfferDeleted(primaryBookFromOffer(*sle), uDirectory, offerIndex);
if (sle->isFieldPresent(sfAdditionalBooks))
{
XRPL_ASSERT(
@@ -89,10 +54,6 @@ offerDelete(ApplyView& view, std::shared_ptr<SLE> const& sle, beast::Journal j)
{
return tefBAD_LEDGER; // LCOV_EXCL_LINE
}
// Hybrid offers also live on the open (no-domain) book — notify
// that cache too.
view.notifyOfferDeleted(openBookFromOffer(*sle), dirIndex, offerIndex);
}
}

View File

@@ -1,32 +1,25 @@
#include <xrpl/tx/paths/BookTip.h>
#include <xrpl/beast/utility/Journal.h>
#include <xrpl/beast/utility/instrumentation.h>
#include <xrpl/ledger/ApplyView.h>
#include <xrpl/ledger/OrderBookIndex.h>
#include <xrpl/ledger/TopOfBookCache.h>
#include <xrpl/ledger/helpers/DirectoryHelpers.h>
#include <xrpl/ledger/helpers/OfferHelpers.h>
#include <xrpl/protocol/Book.h>
#include <xrpl/protocol/Indexes.h>
#include <xrpl/protocol/SField.h>
#include <xrpl/protocol/STLedgerEntry.h>
#include <memory>
#include <optional>
namespace xrpl {
BookTip::BookTip(ApplyView& view, Book const& book)
: view_(view), originalBook_(book), book_(getBookBase(book)), end_(getQualityNext(book_))
: view_(view), book_(getBookBase(book)), end_(getQualityNext(book_))
{
}
bool
BookTip::step(beast::Journal j)
{
bool const firstStep = !valid_;
if (valid_)
{
if (entry_)
@@ -36,91 +29,12 @@ BookTip::step(beast::Journal j)
}
}
// Plan 9: on the first step, ask the order-book index for an ordered
// snapshot of this book's offers. A returned vector is guaranteed complete
// (the index rebuilds from authoritative state on a miss), so iterating it
// is equivalent to the succ() walk — but O(1) per offer instead of an
// O(log N) trie re-walk. nullopt ⇒ no index ⇒ the succ() path below.
if (firstStep && OrderBookIndex::enabled())
{
if (auto snap = view_.orderedBook(originalBook_))
{
cursor_ = std::move(*snap);
cursorPos_ = 0;
useCursor_ = true;
}
}
if (useCursor_)
{
for (;;)
{
if (cursorPos_ >= cursor_.size())
return false;
uint256 const offerKey = cursor_[cursorPos_++];
auto sle = view_.peek(keylet::offer(offerKey));
if (!sle)
// The snapshot is from the (immutable) base index; this offer
// was buffered-deleted by the sandbox (e.g. a pre-crossing
// cancel). Skip it — the succ() walk wouldn't see it either.
continue;
index_ = offerKey;
dir_ = sle->getFieldH256(sfBookDirectory);
quality_ = Quality(getQuality(dir_));
entry_ = std::move(sle);
valid_ = true;
// Cursor order must be best-quality-first, exactly like succ().
XRPL_ASSERT(
getQuality(dir_) >= lastCursorQuality_,
"xrpl::BookTip::step : order-book cursor yields non-decreasing quality");
lastCursorQuality_ = getQuality(dir_);
return true;
}
}
bool firstIter = firstStep;
for (;;)
{
// See if there's an entry at or worse than current quality. Notice
// that the quality is encoded only in the index of the first page
// of a directory.
std::optional<uint256> firstPage;
bool fromCache = false;
if (firstIter && TopOfBookCache::enabled())
{
if (auto const cached = view_.topOfBookFirstPage(originalBook_))
{
firstPage = *cached;
fromCache = true;
}
}
if (!firstPage)
{
firstPage = view_.succ(book_, end_);
if (firstIter && firstPage && TopOfBookCache::enabled())
view_.recordTopOfBook(originalBook_, *firstPage);
}
#ifndef NDEBUG
// Differential gate (Plan 8 P8.7): in debug builds every cache hit
// is shadow-verified against a fresh successor walk. Divergence
// here is a bug in the invalidation logic, not a fallback.
if (fromCache && firstPage)
{
auto const verified = view_.succ(book_, end_);
XRPL_ASSERT(
verified == firstPage,
"BookTip::step : top-of-book cache hit diverges from succ()");
}
#endif
firstIter = false;
auto const firstPage = view_.succ(book_, end_);
if (!firstPage)
return false;
@@ -146,8 +60,6 @@ BookTip::step(beast::Journal j)
// There should never be an empty directory but just in case,
// we handle that case by advancing to the next directory.
// Also covers the case where a stale cache hit returned a
// page that no longer has any indexes.
book_ = *firstPage;
}

View File

@@ -95,12 +95,6 @@ TOfferStreamBase<TIn, TOut>::erase(ApplyView& view)
p->setFieldV256(sfIndexes, v);
view.update(p);
// Plan 9: this stale-entry cleanup strips sfIndexes directly (not via
// dirRemove, which would be a protocol-breaking change), so it bypasses
// the usual offerDelete notification. Notify the order-book index here so
// it doesn't retain a phantom key. Auxiliary only — no ledger-state change.
view.notifyOfferDeleted(book_, tip_.dir(), tip_.index());
JLOG(j_.trace()) << "Missing offer " << tip_.index() << " removed from directory "
<< tip_.dir();
}

View File

@@ -593,11 +593,6 @@ OfferCreate::applyHybrid(
if (!bookExists)
ctx_.registry.get().getOrderBookDB().addOrderBook(book);
// Plan 8: notify the top-of-book cache that the open book just got a
// new offer at `dir.key`. The cache updates its top only if this is
// at-or-better than the current cached top; otherwise no-op.
sb.notifyOfferInserted(book, dir.key, offerKey.key);
sleOffer->setFieldArray(sfAdditionalBooks, bookArr);
return tesSUCCESS;
}
@@ -920,11 +915,6 @@ OfferCreate::applyGuts(Sandbox& sb, Sandbox& sbCancel)
// LCOV_EXCL_STOP
}
// Plan 8: notify the top-of-book cache that `book` got a new offer at
// `dir.key`. The cache updates its top only if this is at-or-better
// than the current cached top; otherwise no-op.
sb.notifyOfferInserted(book, dir.key, offerIndex.key);
auto sleOffer = std::make_shared<SLE>(offerIndex);
sleOffer->setAccountID(sfAccount, accountID_);
sleOffer->setFieldU32(sfSequence, offerSequence);

View File

@@ -1,135 +0,0 @@
#include <test/jtx/Account.h>
#include <test/jtx/Env.h>
#include <test/jtx/amount.h>
#include <test/jtx/offer.h>
#include <test/jtx/pay.h>
#include <test/jtx/trust.h>
#include <xrpl/beast/unit_test/suite.h>
#include <xrpl/json/json_value.h>
#include <xrpl/ledger/OrderBookIndex.h>
#include <xrpl/protocol/UintTypes.h>
#include <xrpl/protocol/jss.h>
#include <vector>
namespace xrpl::test {
/** Bit-exactness gate for the Plan 9 order-book index seam: a scripted
crossing scenario must produce an identical sequence of ledger hashes with
the index enabled (BookTip iterates the in-memory cursor) and disabled
(BookTip walks the SHAMap with succ()). Any divergence in the cursor's order
or contents changes consumed offers/amounts and therefore the ledger hash. */
class OrderBookCrossing_test : public beast::unit_test::Suite
{
// Run a deterministic crossing scenario and return the ledger hash after
// every close. The scenario exercises the cursor-specific paths:
// multi-quality books, a multi-offer (shared-quality) level, an unfunded
// offer, partial fills, and a pre-crossing cancel (peek-null-skip).
std::vector<uint256>
runScenario()
{
using namespace jtx;
Env env{*this};
std::vector<uint256> hashes;
// accountHash is the consensus state root — it reflects every crossing
// effect (consumed offers, balances, directories). If the cursor and
// succ() paths diverge at all, this differs.
auto snap = [&] { hashes.push_back(env.closed()->header().accountHash); };
auto const gw = Account{"gw"};
auto const USD = gw["USD"];
Account const alice{"alice"}; // maker, spread of qualities
Account const bob{"bob"}; // maker, shared-quality level
Account const carol{"carol"}; // maker, becomes unfunded
Account const dave{"dave"}; // taker
env.fund(XRP(10'000'000), gw, alice, bob, carol, dave);
env.close();
snap();
env.trust(USD(100'000'000), alice, bob, carol, dave);
env.close();
env(pay(gw, alice, USD(1'000'000)));
env(pay(gw, bob, USD(1'000'000)));
env(pay(gw, carol, USD(1'000'000)));
env.close();
snap();
// alice: 8 distinct qualities. bob: 4 offers at one shared quality
// (a multi-entry level). carol: one offer she will defund.
for (int i = 0; i < 8; ++i)
env(offer(alice, XRP(500 + i), USD(100)));
for (int i = 0; i < 4; ++i)
env(offer(bob, XRP(503), USD(100)));
env(offer(carol, XRP(501), USD(100)));
env.close();
snap();
// Defund carol: move her USD away so her resting offer is unfunded at
// cross time (exercises the unfunded-skip path through the cursor).
env(pay(carol, gw, USD(1'000'000)));
env.close();
snap();
// dave places an offer, then cancels it via an OfferCreate carrying
// OfferSequence (pre-crossing delete → cursor peek-null-skip path).
auto const daveOfferSeq = env.seq(dave);
env(offer(dave, USD(100), XRP(2'000))); // far from market: rests
env.close();
snap();
// dave crosses: partial and full fills across alice/bob/carol levels.
env(offer(dave, USD(250), XRP(1'255)));
env.close();
snap();
env(offer(dave, USD(500), XRP(2'520)));
env.close();
snap();
// A crossing OfferCreate that also cancels dave's resting offer.
auto cross = offer(dave, USD(100), XRP(505));
cross[jss::OfferSequence] = daveOfferSeq;
env(cross);
env.close();
snap();
return hashes;
}
void
testIndexMatchesBaseline()
{
testcase("ledger hashes identical with order-book index on vs off");
OrderBookIndex::setEnabled(false);
auto const baseline = runScenario();
OrderBookIndex::setEnabled(true);
auto const withIndex = runScenario();
OrderBookIndex::setEnabled(true); // restore default
BEAST_EXPECT(baseline.size() == withIndex.size());
bool identical = baseline.size() == withIndex.size();
for (std::size_t i = 0; i < baseline.size() && i < withIndex.size(); ++i)
{
if (baseline[i] != withIndex[i])
{
identical = false;
log << " ledger-hash divergence at close " << i << "\n";
}
}
BEAST_EXPECT(identical);
}
public:
void
run() override
{
testIndexMatchesBaseline();
}
};
BEAST_DEFINE_TESTSUITE(OrderBookCrossing, app, xrpl);
} // namespace xrpl::test

View File

@@ -1,512 +0,0 @@
#include <test/jtx/Account.h>
#include <test/jtx/Env.h>
#include <test/jtx/amount.h>
#include <test/jtx/fee.h>
#include <test/jtx/offer.h>
#include <test/jtx/pay.h>
#include <test/jtx/seq.h>
#include <test/jtx/trust.h>
#include <xrpl/beast/unit_test/suite.h>
#include <xrpl/ledger/ApplyView.h>
#include <xrpl/ledger/ApplyViewImpl.h>
#include <xrpl/ledger/OpenView.h>
#include <xrpl/ledger/TopOfBookCache.h>
#include <xrpl/protocol/Book.h>
#include <xrpl/protocol/Issue.h>
#include <xrpl/tx/apply.h>
#include <xrpl/tx/paths/BookTip.h>
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <cstdlib>
#include <vector>
namespace xrpl::test {
/** Level 1 micro-benchmark for the top-of-book cache.
A/Bs the cache via its runtime kill switch (TopOfBookCache::setEnabled) over
a deep order book, entirely in-process (no network, no synced ledger).
Two arms:
- readArm (isolated): drives BookTip's first-step top-of-book read against
an OpenView this benchmark constructs and OWNS, so cache counters are
reliable (the open-ledger apply path copies the OpenView per tx and the
copy ctor resets counters, so counters read off env.current() are not).
This isolates the optimized primitive (succ() walk -> hash probe). It is a
BEST-CASE, hot-entry read number — not an end-to-end throughput figure.
- e2eArm (end-to-end): times a batch of real crossing OfferCreates through
the full Env apply path (real offer consumption => invalidation/repopulate
churn). Timing only; also captures the cache's own overhead (the OpenView
copy on every modify()). Answers "does the isolated saving show up at all,
net of overhead". Realistic hit-rate under MainNet-like mixed load is a
later, heavier exercise (Level 1.5 / Level 3), not measured here.
Registered MANUAL — never runs in normal CI. Invoke explicitly:
rippled --unittest=TopOfBookCacheBench
*/
class TopOfBookCacheBench_test : public beast::unit_test::Suite
{
using clock = std::chrono::steady_clock;
// Median of repeated samples — robust to scheduler noise.
static double
median(std::vector<double> v)
{
std::sort(v.begin(), v.end());
return v.empty() ? 0.0 : v[v.size() / 2];
}
struct ReadArm
{
double nsPerRead{0};
std::uint64_t hits{0};
std::uint64_t misses{0};
std::uint64_t invalidations{0};
bool foundTop{false};
};
// Build a deep order book (XRP <-> USD), close it into the LCL, and return
// the Book those offers populate. `pages` distinct qualities => `pages`
// directory pages.
static Book
buildDeepBook(jtx::Env& env, jtx::Account const& gw, int pages)
{
using namespace jtx;
auto const USD = gw["USD"];
Account const maker{"maker"};
env.fund(XRP(1'000'000), gw, maker);
env.close();
env.trust(USD(10'000'000), maker);
env.close();
env(pay(gw, maker, USD(1'000'000)));
env.close();
// Each offer: maker receives takerPays (XRP), gives takerGets (USD).
// Distinct takerPays => distinct quality => distinct directory page.
for (int i = 0; i < pages; ++i)
env(offer(maker, XRP(500 + i), USD(100)));
env.close();
// Book{in = takerPays.asset(), out = takerGets.asset()} — see
// OfferCreate.cpp:570.
return Book{xrpIssue(), USD.issue(), std::nullopt};
}
// Isolated read-path arm. Owns the OpenView so counters are trustworthy.
ReadArm
runReadArm(jtx::Env& env, Book const& book, bool cacheEnabled, std::size_t reads)
{
TopOfBookCache::setEnabled(cacheEnabled);
// Fresh owned view per arm => clean counters (no reset API otherwise).
OpenView ov(kOpenLedger, env.closed()->rules(), env.closed());
// One read = fresh BookTip + a single step() = one top-of-book probe.
// BookTip's first step is read-only (it deletes only from the 2nd step
// on), so a single ApplyView can be reused across reads.
ApplyViewImpl av(&ov, TapNone);
ReadArm r;
{
BookTip bt(av, book);
r.foundTop = bt.step(env.journal) && bt.entry() != nullptr;
}
auto const once = [&] {
for (std::size_t i = 0; i < reads; ++i)
{
BookTip bt(av, book);
bt.step(env.journal);
}
};
once(); // warmup (also populates the cache in the enabled arm)
std::vector<double> samples;
for (int rep = 0; rep < 5; ++rep)
{
auto const t0 = clock::now();
once();
auto const t1 = clock::now();
samples.push_back(
static_cast<double>(
std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count()) /
static_cast<double>(reads));
}
r.nsPerRead = median(std::move(samples));
r.hits = ov.topOfBookCache().hits();
r.misses = ov.topOfBookCache().misses();
r.invalidations = ov.topOfBookCache().invalidations();
return r;
}
void
testReadPath()
{
testcase("Arm 1: isolated top-of-book read (owned OpenView)");
using namespace jtx;
// Isolate the TopOfBookCache read path: the order-book index, when on,
// supersedes the cache in BookTip (cursor instead of cache+succ), so it
// must be off for this arm to measure the cache.
OrderBookIndex::setEnabled(false);
int const pages = 64;
std::size_t const reads = 200'000;
Env env{*this};
auto const book = buildDeepBook(env, Account{"gw"}, pages);
auto const off = runReadArm(env, book, /*cacheEnabled=*/false, reads);
auto const on = runReadArm(env, book, /*cacheEnabled=*/true, reads);
TopOfBookCache::setEnabled(true); // restore default
BEAST_EXPECT(off.foundTop);
BEAST_EXPECT(on.foundTop);
// Disabled arm never consults the cache.
BEAST_EXPECT(off.hits == 0 && off.misses == 0);
// Enabled arm: 1 cold miss, the rest hits.
BEAST_EXPECT(on.hits > 0);
BEAST_EXPECT(on.misses >= 1);
BEAST_EXPECT(on.invalidations == 0);
double const speedup = on.nsPerRead > 0 ? off.nsPerRead / on.nsPerRead : 0.0;
#ifndef NDEBUG
log << "\n*** DEBUG build: BookTip's differential gate shadow-verifies "
"every cache hit with an extra succ() walk, so the cache-ON path "
"does MORE work here. Arm 1 timing is only meaningful in a "
"Release (NDEBUG) build; counters below are valid regardless. ***\n";
#endif
log << "\n=== Arm 1: isolated read (best-case, hot entry) ===\n"
<< " book pages : " << pages << "\n"
<< " reads / sample : " << reads << "\n"
<< " cache OFF ns/read : " << off.nsPerRead << "\n"
<< " cache ON ns/read : " << on.nsPerRead << "\n"
<< " speedup : " << speedup << "x\n"
<< " cache ON hits/miss : " << on.hits << " / " << on.misses << "\n"
<< std::endl;
OrderBookIndex::setEnabled(true); // restore default
}
// End-to-end arm: time real crossing offers through the full apply path.
double
runE2EArm(bool cacheEnabled, int pages, int crossings)
{
using namespace jtx;
TopOfBookCache::setEnabled(cacheEnabled);
Env env{*this};
auto const gw = Account{"gw"};
auto const USD = gw["USD"];
buildDeepBook(env, gw, pages);
// Taker buys USD with XRP, crossing the maker's resting offers.
Account const taker{"taker"};
env.fund(XRP(1'000'000), taker);
env.close();
env.trust(USD(10'000'000), taker);
env.close();
auto const t0 = clock::now();
for (int i = 0; i < crossings; ++i)
{
env(offer(taker, USD(100), XRP(500 + (i % pages))));
if ((i % 10) == 9)
env.close();
}
env.close();
auto const t1 = clock::now();
return static_cast<double>(
std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count()) /
crossings;
}
void
testEndToEnd()
{
testcase("Arm 2: end-to-end crossing throughput (timing only)");
int const pages = 64;
int const crossings = 300;
double const off = runE2EArm(/*cacheEnabled=*/false, pages, crossings);
double const on = runE2EArm(/*cacheEnabled=*/true, pages, crossings);
TopOfBookCache::setEnabled(true); // restore default
BEAST_EXPECT(off > 0 && on > 0);
log << "\n=== Arm 2: end-to-end crossing (full apply path, real churn) ===\n"
<< " book pages : " << pages << "\n"
<< " crossing offers : " << crossings << "\n"
<< " cache OFF us/cross : " << off << "\n"
<< " cache ON us/cross : " << on << "\n"
<< " delta : " << (off - on) << " us/cross"
<< " (note: dominated by tx machinery + cache copy overhead)\n"
<< std::endl;
}
// Profiling arm: measure PURE crossing-apply cost with NO ledger close.
// env.close() runs full consensus close (flushDirty hashing + SQLite ledger
// writes); Arm 2 closed every 10 offers, contaminating its per-crossing
// number. Here we pre-sign crossing OfferCreates and replay them against a
// fresh owned OpenView per rep (each rep starts with the full book), timing
// only xrpl::apply (preflight + preclaim + doApply). Long enough total work
// to attach `sample`/Instruments to the running process.
void
testCrossingApplyProfile()
{
testcase("Arm 3: pure crossing-apply cost (no ledger close)");
using namespace jtx;
int const pages = 64;
int const crossPerRep = 50; // crossings applied per fresh book
// BENCH_PROFILE=1 cranks reps so the apply loop runs ~30s for `sample`.
bool const profiling = std::getenv("BENCH_PROFILE") != nullptr;
int const reps = profiling ? 5000 : 400;
Env env{*this};
auto const gw = Account{"gw"};
auto const USD = gw["USD"];
buildDeepBook(env, gw, pages);
Account const taker{"taker"};
env.fund(XRP(10'000'000), taker);
env.close();
env.trust(USD(100'000'000), taker);
env.close();
// Pre-sign the crossing OfferCreates once, with explicit increasing
// sequences starting at taker's current seq. Each fresh accum resets
// taker to that same seq, so the identical signed set replays cleanly.
std::uint32_t const startSeq = env.seq(taker);
std::vector<std::shared_ptr<STTx const>> txns;
txns.reserve(crossPerRep);
for (int i = 0; i < crossPerRep; ++i)
{
auto jtx = env.jt(
offer(taker, USD(100), XRP(500 + (i % pages))),
Seq(startSeq + i),
Fee(100));
txns.push_back(jtx.stx);
}
auto const base = env.current(); // open view over the closed book
std::size_t applied = 0, crossed = 0;
std::vector<double> samples;
for (int rep = 0; rep < reps; ++rep)
{
OpenView accum(kOpenLedger, base->rules(), base);
auto const t0 = clock::now();
for (auto const& tx : txns)
{
auto const r = apply(env.app(), accum, *tx, TapNone, env.journal);
if (rep == 0)
{
++applied;
if (r.applied && isTesSuccess(r.ter))
++crossed;
}
}
auto const t1 = clock::now();
samples.push_back(
static_cast<double>(
std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count()) /
crossPerRep / 1000.0); // us/crossing
}
BEAST_EXPECT(applied == static_cast<std::size_t>(crossPerRep));
BEAST_EXPECT(crossed > 0);
log << "\n=== Arm 3: pure crossing-apply (no ledger close) ===\n"
<< " book pages : " << pages << "\n"
<< " crossings / rep : " << crossPerRep << "\n"
<< " reps : " << reps << "\n"
<< " tesSUCCESS (rep 0) : " << crossed << " / " << applied << "\n"
<< " median us / crossing : " << median(samples) << "\n"
<< " (compare to Arm 2's ~780us which INCLUDED ledger close)\n"
<< std::endl;
}
// Arm 4 (Plan 9 headline): pure crossing-apply with the order-book index
// ON vs OFF. OFF = baseline succ()-per-offer walk; ON = BookTip iterates the
// in-memory cursor (index pre-seeded per rep, untimed, modelling the
// maintained steady state). Same owned-OpenView / no-ledger-close method as
// Arm 3, so the delta isolates the succ() cost the cursor removes.
void
testCrossingIndexArm()
{
testcase("Arm 4: crossing-apply, order-book index ON vs OFF");
using namespace jtx;
int const pages = 64;
int const crossPerRep = 50;
int const reps = 400;
Env env{*this};
auto const gw = Account{"gw"};
auto const USD = gw["USD"];
auto const book = buildDeepBook(env, gw, pages);
Account const taker{"taker"};
env.fund(XRP(10'000'000), taker);
env.close();
env.trust(USD(100'000'000), taker);
env.close();
std::uint32_t const startSeq = env.seq(taker);
std::vector<std::shared_ptr<STTx const>> txns;
txns.reserve(crossPerRep);
for (int i = 0; i < crossPerRep; ++i)
txns.push_back(
env.jt(offer(taker, USD(100), XRP(500 + (i % pages))), Seq(startSeq + i), Fee(100))
.stx);
auto const base = env.current();
auto runArm = [&](bool indexEnabled) {
OrderBookIndex::setEnabled(indexEnabled);
std::vector<double> samples;
for (int rep = 0; rep < reps; ++rep)
{
OpenView accum(kOpenLedger, base->rules(), base);
// Warm the maintained index outside the timed region (models the
// steady state where it is kept in sync, not rebuilt per cross).
if (indexEnabled)
accum.orderBookIndex().rebuildBook(accum, book);
auto const t0 = clock::now();
for (auto const& tx : txns)
apply(env.app(), accum, *tx, TapNone, env.journal);
auto const t1 = clock::now();
samples.push_back(
static_cast<double>(
std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count()) /
crossPerRep / 1000.0);
}
return median(samples);
};
double const off = runArm(false);
double const on = runArm(true);
OrderBookIndex::setEnabled(true); // restore default
double const speedup = on > 0 ? off / on : 0.0;
log << "\n=== Arm 4: crossing-apply, index ON vs OFF (no ledger close) ===\n"
<< " book pages : " << pages << "\n"
<< " crossings / rep : " << crossPerRep << "\n"
<< " index OFF us/crossing : " << off << " (baseline succ() walk)\n"
<< " index ON us/crossing : " << on << " (in-memory cursor)\n"
<< " speedup : " << speedup << "x\n"
<< std::endl;
}
// Arm 5 (P9.6 headline): the REALISTIC per-tx path. Each crossing is applied
// to a fresh COW copy of the prior OpenView — exactly what OpenLedger::modify
// does per transaction — so the persistent index warms via the clone (no
// pre-seed) and the clone cost is INCLUDED in the timing. Index ON should now
// beat OFF on this path (the warm cursor amortizes the one cold rebuild),
// unlike the non-persistent index which cold-started and rebuilt every tx.
void
testCrossingWarmArm()
{
testcase("Arm 5: realistic per-tx-copy crossing, index ON vs OFF");
using namespace jtx;
int const pages = 400; // deep enough to stay populated across the batch
int const crossPerRep = 100;
int const reps = 200;
Env env{*this};
auto const gw = Account{"gw"};
auto const USD = gw["USD"];
auto const book = buildDeepBook(env, gw, pages);
Account const taker{"taker"};
env.fund(XRP(100'000'000), taker);
env.close();
env.trust(USD(1'000'000'000), taker);
env.close();
std::uint32_t const startSeq = env.seq(taker);
std::vector<std::shared_ptr<STTx const>> txns;
txns.reserve(crossPerRep);
for (int i = 0; i < crossPerRep; ++i)
txns.push_back(
env.jt(offer(taker, USD(100), XRP(500 + (i % pages))), Seq(startSeq + i), Fee(100))
.stx);
auto const base = env.current();
auto runArm = [&](bool indexEnabled) {
OrderBookIndex::setEnabled(indexEnabled);
std::vector<double> samples;
for (int rep = 0; rep < reps; ++rep)
{
// Fresh cold OpenView over the closed book (index empty).
auto current = std::make_shared<OpenView>(kOpenLedger, base->rules(), base);
auto const t0 = clock::now();
for (auto const& tx : txns)
{
// The per-tx COW copy (clones the persistent index) — exactly
// what OpenLedger::modify does per transaction.
auto next = std::make_shared<OpenView>(*current);
apply(env.app(), *next, *tx, TapNone, env.journal);
current = next;
}
auto const t1 = clock::now();
samples.push_back(
static_cast<double>(
std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count()) /
crossPerRep / 1000.0);
}
return median(samples);
};
double const off = runArm(false);
double const on = runArm(true);
OrderBookIndex::setEnabled(true);
double const speedup = on > 0 ? off / on : 0.0;
log << "\n=== Arm 5: realistic per-tx-copy crossing (clones index per tx) ===\n"
<< " book pages : " << pages << "\n"
<< " crossings / rep : " << crossPerRep << "\n"
<< " index OFF us/crossing : " << off << " (succ() per offer, per tx)\n"
<< " index ON us/crossing : " << on << " (warm cursor; clone+rebuild amortized)\n"
<< " speedup : " << speedup << "x\n"
<< std::endl;
}
public:
void
run() override
{
// BENCH_PROFILE=1 runs only the crossing-apply loop (long) for `sample`.
if (std::getenv("BENCH_PROFILE") != nullptr)
{
testCrossingApplyProfile();
return;
}
testReadPath();
testEndToEnd();
testCrossingApplyProfile();
testCrossingIndexArm();
testCrossingWarmArm();
}
};
BEAST_DEFINE_TESTSUITE_MANUAL_PRIO(TopOfBookCacheBench, app, xrpl, 20);
} // namespace xrpl::test

View File

@@ -1,257 +0,0 @@
#include <test/jtx/Account.h>
#include <test/jtx/Env.h>
#include <test/jtx/amount.h>
#include <test/jtx/fee.h>
#include <test/jtx/offer.h>
#include <test/jtx/pay.h>
#include <test/jtx/seq.h>
#include <test/jtx/trust.h>
#include <xrpl/beast/unit_test/suite.h>
#include <xrpl/ledger/ApplyView.h>
#include <xrpl/ledger/OpenView.h>
#include <xrpl/ledger/OrderBookIndex.h>
#include <xrpl/protocol/Indexes.h>
#include <xrpl/protocol/Issue.h>
#include <xrpl/protocol/SField.h>
#include <xrpl/tx/apply.h>
#include <memory>
#include <vector>
namespace xrpl::test {
/** Proves OrderBookIndex's rebuild/walk against a real SHAMap-backed book, and
that an index maintained by inserting offers in creation order matches the
canonical directory walk (the determinism assumption behind P9.3). */
class OrderBookIndex_test : public beast::unit_test::Suite
{
// Read an offer's quality-directory root (the key the index levels on).
static uint256
bookDirOf(ReadView const& view, uint256 const& offerKey)
{
auto const sle = view.read(keylet::offer(offerKey));
return sle ? sle->getFieldH256(sfBookDirectory) : uint256{};
}
void
testRebuildMatchesWalk()
{
testcase("rebuild matches SHAMap walk, ordered best-quality-first");
using namespace jtx;
Env env{*this};
auto const gw = Account{"gw"};
auto const USD = gw["USD"];
Account const maker{"maker"};
env.fund(XRP(10'000'000), gw, maker);
env.close();
env.trust(USD(100'000'000), maker);
env.close();
env(pay(gw, maker, USD(10'000'000)));
env.close();
// Book the maker's offers populate: in = TakerPays asset (XRP),
// out = TakerGets asset (USD). (OfferCreate.cpp builds it this way.)
Book const book{xrpIssue(), USD.issue(), std::nullopt};
// Place offers, recording each offer's key in creation order.
// - 5 distinct qualities (distinct TakerPays => distinct levels)
// - one quality with 40 offers to force a multi-page directory level
// (exercises cdirNext across pages in the walk).
std::vector<uint256> created;
auto place = [&](int xrpPays, int usdGets) {
auto const seq = env.seq(maker);
env(offer(maker, XRP(xrpPays), USD(usdGets)));
created.push_back(keylet::offer(maker, seq).key);
};
for (int q = 0; q < 5; ++q)
place(500 + q, 100); // 5 distinct qualities
for (int i = 0; i < 40; ++i)
place(800, 100); // 40 offers at one shared quality
env.close();
auto const view = env.closed();
// Rebuild from the authoritative state.
OrderBookIndex rebuilt;
rebuilt.rebuildBook(*view, book);
BEAST_EXPECT(rebuilt.offerCount(book) == created.size());
BEAST_EXPECT(rebuilt.validateMatchesShaMap(*view, book));
BEAST_EXPECT(rebuilt.rebuilds() == 1u);
// Flattened order must be non-decreasing in quality (best first).
auto const flat = rebuilt.flatten(book);
BEAST_EXPECT(flat.size() == created.size());
bool ordered = true;
for (std::size_t i = 1; i < flat.size(); ++i)
{
auto const prev = getQuality(bookDirOf(*view, flat[i - 1]));
auto const cur = getQuality(bookDirOf(*view, flat[i]));
if (cur < prev)
ordered = false;
}
BEAST_EXPECT(ordered);
// An index maintained by inserting in creation order (simulating the
// P9.3 apply-path hooks, no deletions) must equal the rebuilt index.
OrderBookIndex maintained;
for (auto const& offerKey : created)
maintained.insertOffer(book, bookDirOf(*view, offerKey), offerKey);
BEAST_EXPECT(maintained.flatten(book) == flat);
BEAST_EXPECT(maintained.validateMatchesShaMap(*view, book));
}
void
testEmptyAndAbsentBook()
{
testcase("rebuild of an empty book yields nothing");
using namespace jtx;
Env env{*this};
env.fund(XRP(10'000), Account{"gw"});
env.close();
Book const book{xrpIssue(), Account{"gw"}["USD"].issue(), std::nullopt};
OrderBookIndex idx;
idx.rebuildBook(*env.closed(), book);
BEAST_EXPECT(idx.offerCount(book) == 0u);
BEAST_EXPECT(idx.bookCount() == 0u);
BEAST_EXPECT(idx.validateMatchesShaMap(*env.closed(), book));
}
// P9.3: an index seeded from state and then maintained through real
// OfferCreate apply (crossings delete offers, placements insert them) must
// stay byte-exactly equal to a fresh SHAMap walk. This proves the notify
// hooks keep the index in sync without any read-path/seam involvement.
void
testMaintenanceInSync()
{
testcase("index stays in sync through real crossing/placement apply");
using namespace jtx;
Env env{*this};
auto const gw = Account{"gw"};
auto const USD = gw["USD"];
Account const maker{"maker"};
Account const taker{"taker"};
env.fund(XRP(10'000'000), gw, maker, taker);
env.close();
env.trust(USD(100'000'000), maker, taker);
env.close();
env(pay(gw, maker, USD(10'000'000)));
env.close();
Book const book{xrpIssue(), USD.issue(), std::nullopt};
// Resting book: 30 offers across distinct qualities.
for (int i = 0; i < 30; ++i)
env(offer(maker, XRP(500 + i), USD(100)));
env.close();
// Owned OpenView over the closed state; seed the index by rebuild
// (the attach-time / startup model).
auto const base = env.current();
OpenView accum(kOpenLedger, base->rules(), base);
accum.orderBookIndex().rebuildBook(accum, book);
BEAST_EXPECT(accum.orderBookIndex().validateMatchesShaMap(accum, book));
BEAST_EXPECT(accum.orderBookIndex().offerCount(book) == 30u);
// Pre-sign a mixed batch: taker crossings (consume → delete) and maker
// placements at new qualities (insert), with explicit sequences.
std::vector<std::shared_ptr<STTx const>> txns;
std::uint32_t takerSeq = env.seq(taker);
std::uint32_t makerSeq = env.seq(maker);
for (int i = 0; i < 15; ++i)
{
txns.push_back(
env.jt(offer(taker, USD(100), XRP(500 + i)), Seq(takerSeq++), Fee(100)).stx);
txns.push_back(
env.jt(offer(maker, XRP(700 + i), USD(100)), Seq(makerSeq++), Fee(100)).stx);
}
// Apply to the owned view; the index is maintained via the notify
// hooks (flushed on each apply). Validate after every tx so a desync
// is pinned to the exact transaction that caused it.
for (auto const& tx : txns)
{
auto const r = apply(env.app(), accum, *tx, TapNone, env.journal);
BEAST_EXPECT(r.applied);
BEAST_EXPECT(accum.orderBookIndex().validateMatchesShaMap(accum, book));
}
// The index actually did work (both directions exercised).
BEAST_EXPECT(accum.orderBookIndex().inserts() > 0u);
BEAST_EXPECT(accum.orderBookIndex().deletes() > 0u);
}
// P9.6 Stage E: across a ledger close the open-round index is not carried
// (the next round starts cold and warms via rebuild-on-touch). Confirm that
// after real crossings + a close, the post-close state rebuilds clean — i.e.
// the close handoff leaves no index/SHAMap drift.
void
testCloseHandoff()
{
testcase("index rebuilds clean across a ledger close");
using namespace jtx;
Env env{*this};
auto const gw = Account{"gw"};
auto const USD = gw["USD"];
Account const maker{"maker"};
Account const taker{"taker"};
env.fund(XRP(10'000'000), gw, maker, taker);
env.close();
env.trust(USD(100'000'000), maker, taker);
env.close();
env(pay(gw, maker, USD(10'000'000)));
env.close();
Book const book{xrpIssue(), USD.issue(), std::nullopt};
for (int i = 0; i < 20; ++i)
env(offer(maker, XRP(500 + i), USD(100)));
env.close();
// Round 1: real crossings through the open ledger, then close.
for (int i = 0; i < 8; ++i)
env(offer(taker, USD(100), XRP(500 + i)));
env.close();
// After the close, a fresh index rebuilt from the post-close ledger must
// match the SHAMap walk (no drift left by the round's crossings).
{
OrderBookIndex idx;
idx.rebuildBook(*env.closed(), book);
BEAST_EXPECT(idx.validateMatchesShaMap(*env.closed(), book));
}
// Round 2: more crossings on top of the post-close state, then re-check.
for (int i = 8; i < 16; ++i)
env(offer(taker, USD(100), XRP(500 + i)));
env.close();
{
OrderBookIndex idx;
idx.rebuildBook(*env.closed(), book);
BEAST_EXPECT(idx.validateMatchesShaMap(*env.closed(), book));
}
}
public:
void
run() override
{
testRebuildMatchesWalk();
testEmptyAndAbsentBook();
testMaintenanceInSync();
testCloseHandoff();
}
};
BEAST_DEFINE_TESTSUITE(OrderBookIndex, ledger, xrpl);
} // namespace xrpl::test

View File

@@ -39,10 +39,6 @@ xrpl_add_test(tx)
target_link_libraries(xrpl.test.tx PRIVATE xrpl.imports.test)
add_dependencies(xrpl.tests xrpl.test.tx)
xrpl_add_test(ledger)
target_link_libraries(xrpl.test.ledger PRIVATE xrpl.imports.test)
add_dependencies(xrpl.tests xrpl.test.ledger)
xrpl_add_test(protocol_autogen)
target_link_libraries(xrpl.test.protocol_autogen PRIVATE xrpl.imports.test)
add_dependencies(xrpl.tests xrpl.test.protocol_autogen)

View File

@@ -1,175 +0,0 @@
#include <xrpl/ledger/OrderBookIndex.h>
#include <xrpl/protocol/AccountID.h>
#include <xrpl/protocol/Asset.h>
#include <xrpl/protocol/Book.h>
#include <xrpl/protocol/Indexes.h>
#include <xrpl/protocol/Issue.h>
#include <xrpl/protocol/UintTypes.h>
#include <gtest/gtest.h>
namespace xrpl::test {
namespace {
// Synthetic-but-consistent IOU book (XRP <-> tagged currency), matching the
// TopOfBookCache test helper so the two suites stay comparable.
Book
makeIOUBook(std::uint8_t tag)
{
Currency c{};
c.data()[19] = tag;
AccountID issuer{};
issuer.data()[19] = tag;
Issue const inIssue{c, issuer};
return Book{Asset{inIssue}, Asset{Issue{xrpCurrency(), xrpAccount()}}, std::nullopt};
}
// Quality-directory root key for a book at a given rate. Lower rate => lower
// key => better quality (the ordering the index relies on).
uint256
dirKey(Book const& book, std::uint64_t rate)
{
return keylet::quality(keylet::kBook(book), rate).key;
}
// Arbitrary distinct offer key.
uint256
offerKey(std::uint8_t tag)
{
uint256 k{};
k.data()[0] = tag;
return k;
}
} // namespace
TEST(OrderBookIndex, EmptyBook)
{
OrderBookIndex idx;
Book const book = makeIOUBook(1);
EXPECT_TRUE(idx.flatten(book).empty());
EXPECT_FALSE(idx.firstOffer(book).has_value());
EXPECT_EQ(idx.bookCount(), 0u);
EXPECT_EQ(idx.offerCount(book), 0u);
}
TEST(OrderBookIndex, InsertWithinLevelPreservesAppendOrder)
{
OrderBookIndex idx;
Book const book = makeIOUBook(2);
uint256 const lvl = dirKey(book, 1'000'000u);
idx.insertOffer(book, lvl, offerKey(1));
idx.insertOffer(book, lvl, offerKey(2));
idx.insertOffer(book, lvl, offerKey(3));
std::vector<uint256> const expect{offerKey(1), offerKey(2), offerKey(3)};
EXPECT_EQ(idx.flatten(book), expect);
EXPECT_EQ(idx.firstOffer(book), offerKey(1));
EXPECT_EQ(idx.offerCount(book), 3u);
EXPECT_EQ(idx.inserts(), 3u);
}
TEST(OrderBookIndex, LevelsOrderedBestQualityFirstRegardlessOfInsertOrder)
{
OrderBookIndex idx;
Book const book = makeIOUBook(3);
uint256 const best = dirKey(book, 1'000'000u);
uint256 const mid = dirKey(book, 2'000'000u);
uint256 const worst = dirKey(book, 3'000'000u);
ASSERT_LT(best, mid);
ASSERT_LT(mid, worst);
// Insert worst-first to prove ordering is by quality, not insertion.
idx.insertOffer(book, worst, offerKey(30));
idx.insertOffer(book, best, offerKey(10));
idx.insertOffer(book, mid, offerKey(20));
std::vector<uint256> const expect{offerKey(10), offerKey(20), offerKey(30)};
EXPECT_EQ(idx.flatten(book), expect);
EXPECT_EQ(idx.firstOffer(book), offerKey(10));
}
TEST(OrderBookIndex, DeletePreservesOrderAndDropsEmptyLevel)
{
OrderBookIndex idx;
Book const book = makeIOUBook(4);
uint256 const a = dirKey(book, 1'000u);
uint256 const b = dirKey(book, 2'000u);
idx.insertOffer(book, a, offerKey(1));
idx.insertOffer(book, a, offerKey(2));
idx.insertOffer(book, a, offerKey(3));
idx.insertOffer(book, b, offerKey(4));
// Remove a middle offer: relative order of the rest is preserved.
idx.deleteOffer(book, a, offerKey(2));
std::vector<uint256> const expect1{offerKey(1), offerKey(3), offerKey(4)};
EXPECT_EQ(idx.flatten(book), expect1);
EXPECT_EQ(idx.deletes(), 1u);
// Empty the first level: it is dropped, second becomes the front.
idx.deleteOffer(book, a, offerKey(1));
idx.deleteOffer(book, a, offerKey(3));
EXPECT_EQ(idx.firstOffer(book), offerKey(4));
EXPECT_EQ(idx.flatten(book), std::vector<uint256>{offerKey(4)});
// Empty the book entirely: it is removed from the index.
idx.deleteOffer(book, b, offerKey(4));
EXPECT_TRUE(idx.flatten(book).empty());
EXPECT_EQ(idx.bookCount(), 0u);
}
TEST(OrderBookIndex, DeleteAbsentIsNoOp)
{
OrderBookIndex idx;
Book const book = makeIOUBook(5);
uint256 const lvl = dirKey(book, 1'000u);
idx.insertOffer(book, lvl, offerKey(1));
idx.deleteOffer(book, lvl, offerKey(99)); // absent key
idx.deleteOffer(book, dirKey(book, 9u), offerKey(1)); // absent level
idx.deleteOffer(makeIOUBook(6), lvl, offerKey(1)); // absent book
EXPECT_EQ(idx.flatten(book), std::vector<uint256>{offerKey(1)});
EXPECT_EQ(idx.deletes(), 0u);
}
TEST(OrderBookIndex, DistinctBooksIndependent)
{
OrderBookIndex idx;
Book const a = makeIOUBook(7);
Book const b = makeIOUBook(8);
idx.insertOffer(a, dirKey(a, 100u), offerKey(1));
idx.insertOffer(b, dirKey(b, 100u), offerKey(2));
EXPECT_EQ(idx.bookCount(), 2u);
idx.eraseBook(a);
EXPECT_TRUE(idx.flatten(a).empty());
EXPECT_EQ(idx.flatten(b), std::vector<uint256>{offerKey(2)});
EXPECT_EQ(idx.bookCount(), 1u);
}
TEST(OrderBookIndex, ClearEmptiesEverything)
{
OrderBookIndex idx;
Book const book = makeIOUBook(9);
idx.insertOffer(book, dirKey(book, 1u), offerKey(1));
idx.clear();
EXPECT_EQ(idx.bookCount(), 0u);
EXPECT_TRUE(idx.flatten(book).empty());
}
TEST(OrderBookIndex, KillSwitchToggleable)
{
EXPECT_TRUE(OrderBookIndex::enabled());
OrderBookIndex::setEnabled(false);
EXPECT_FALSE(OrderBookIndex::enabled());
OrderBookIndex::setEnabled(true);
EXPECT_TRUE(OrderBookIndex::enabled());
}
} // namespace xrpl::test

View File

@@ -1,151 +0,0 @@
#include <xrpl/ledger/detail/PersistentOrderTree.h>
#include <gtest/gtest.h>
#include <cmath>
#include <cstring>
#include <map>
#include <random>
#include <utility>
#include <vector>
namespace xrpl::detail {
namespace {
// 256-bit value whose numeric order matches integer order (n written
// big-endian into the low 8 bytes; base_uint compares MSB-first).
uint256
u256(std::uint64_t n)
{
uint256 k;
std::memset(k.data(), 0, k.size());
auto* end = k.data() + k.size();
for (int i = 0; i < 8; ++i)
end[-1 - i] = static_cast<unsigned char>((n >> (8 * i)) & 0xff);
return k;
}
using RefKey = std::pair<uint256, std::uint64_t>; // (dirRoot, insertSeq)
// Reference inorder: std::map orders by (dirRoot, insertSeq); collect offers.
std::vector<uint256>
refInorder(std::map<RefKey, uint256> const& ref)
{
std::vector<uint256> out;
out.reserve(ref.size());
for (auto const& [k, off] : ref)
out.push_back(off);
return out;
}
std::vector<uint256>
treeInorder(OrderTreePtr const& t)
{
std::vector<uint256> out;
otInorder(t, out);
return out;
}
int
height(OrderTreePtr const& t)
{
if (!t)
return 0;
return 1 + std::max(height(t->left), height(t->right));
}
// Verify subtree size fields are consistent.
std::uint32_t
checkSize(OrderTreePtr const& t)
{
if (!t)
return 0;
auto const s = checkSize(t->left) + checkSize(t->right) + 1;
EXPECT_EQ(s, t->size);
return s;
}
} // namespace
TEST(PersistentOrderTree, MatchesStdMapUnderRandomOps)
{
std::mt19937_64 rng(0xC0FFEEu); // fixed seed → deterministic
std::map<RefKey, uint256> ref;
OrderTreePtr tree;
// A small set of dirRoots (quality levels) so levels hold multiple offers,
// exercising within-level ordering and the dirRoot-range delete search.
constexpr std::uint64_t kDirs = 8;
std::uint64_t seqCounter = 0;
std::uint64_t offerCounter = 0;
std::vector<RefKey> live;
for (int op = 0; op < 4000; ++op)
{
bool const doInsert = live.empty() || (rng() % 100) < 60;
if (doInsert)
{
uint256 const dir = u256(rng() % kDirs);
std::uint64_t const seq = ++seqCounter; // unique → unique key
uint256 const off = u256(1'000'000 + (++offerCounter));
RefKey const key{dir, seq};
ref.emplace(key, off);
tree = otInsert(tree, dir, seq, off);
live.push_back(key);
}
else
{
// Delete a random live key by (dirRoot, offerKey) lookup, exactly
// like OrderBookIndex::deleteOffer does.
auto const idx = rng() % live.size();
RefKey const key = live[idx];
uint256 const off = ref.at(key);
auto const foundSeq = otFindSeq(tree, key.first, off);
ASSERT_TRUE(foundSeq.has_value());
EXPECT_EQ(*foundSeq, key.second);
tree = otDelete(tree, key.first, *foundSeq);
ref.erase(key);
live[idx] = live.back();
live.pop_back();
}
// Inorder equivalence after every op.
ASSERT_EQ(treeInorder(tree), refInorder(ref));
// Size field integrity + element count.
EXPECT_EQ(otSize(tree), ref.size());
checkSize(tree);
// first == reference begin's offer.
if (ref.empty())
EXPECT_FALSE(otFirst(tree).has_value());
else
EXPECT_EQ(otFirst(tree), ref.begin()->second);
}
// Weight-balanced height stays logarithmic (loose bound).
auto const n = otSize(tree);
if (n > 0)
EXPECT_LE(height(tree), 3 * (static_cast<int>(std::log2(n)) + 1) + 3);
}
TEST(PersistentOrderTree, StructuralSharingImmutability)
{
OrderTreePtr base;
for (std::uint64_t i = 0; i < 200; ++i)
base = otInsert(base, u256(i % 4), i + 1, u256(10'000 + i));
auto const before = treeInorder(base);
// Mutate copies; the captured `base` must be unaffected (immutable nodes).
auto inserted = otInsert(base, u256(2), 99'999, u256(42));
auto deleted = otDelete(base, u256(0), 1);
EXPECT_EQ(treeInorder(base), before); // base unchanged by insert
EXPECT_EQ(otSize(inserted), otSize(base) + 1); // derived tree grew
EXPECT_EQ(otSize(deleted), otSize(base) - 1); // derived tree shrank
EXPECT_EQ(treeInorder(base), before); // base unchanged by delete
}
} // namespace xrpl::detail

View File

@@ -1,200 +0,0 @@
#include <xrpl/ledger/TopOfBookCache.h>
#include <xrpl/protocol/AccountID.h>
#include <xrpl/protocol/Asset.h>
#include <xrpl/protocol/Book.h>
#include <xrpl/protocol/Indexes.h>
#include <xrpl/protocol/Issue.h>
#include <xrpl/protocol/UintTypes.h>
#include <gtest/gtest.h>
#include <optional>
namespace xrpl::test {
namespace {
// Construct a synthetic-but-consistent IOU book. The currency byte
// distinguishes books for cache lookups; pairs are XRP <-> <currency>.
Book
makeIOUBook(std::uint8_t tag)
{
Currency c{};
c.data()[19] = tag;
AccountID issuer{};
issuer.data()[19] = tag;
Issue const inIssue{c, issuer};
return Book{Asset{inIssue}, Asset{Issue{xrpCurrency(), xrpAccount()}}, std::nullopt};
}
// Derive the directory keylet (first-page key) for a given book at a given
// quality rate. Two distinct rates produce two distinct, prefix-comparable
// keys for the same book.
uint256
dirKey(Book const& book, std::uint64_t rate)
{
return keylet::quality(keylet::kBook(book), rate).key;
}
} // namespace
TEST(TopOfBookCache, EmptyCacheMisses)
{
TopOfBookCache cache;
EXPECT_FALSE(cache.get(makeIOUBook(1)).has_value());
EXPECT_EQ(cache.size(), 0u);
EXPECT_EQ(cache.hits(), 0u);
EXPECT_EQ(cache.misses(), 1u);
}
TEST(TopOfBookCache, RecordThenHit)
{
TopOfBookCache cache;
Book const book = makeIOUBook(2);
uint256 const key = dirKey(book, 1'000'000u);
cache.record(book, key, /*seq=*/42);
auto const got = cache.get(book);
ASSERT_TRUE(got.has_value());
EXPECT_EQ(got->firstPageKey, key);
EXPECT_EQ(got->bestQuality, getQuality(key));
EXPECT_EQ(got->asOfLedger, 42u);
EXPECT_EQ(cache.hits(), 1u);
EXPECT_EQ(cache.misses(), 0u);
}
TEST(TopOfBookCache, OnOfferInsertBetterReplacesTop)
{
TopOfBookCache cache;
Book const book = makeIOUBook(3);
uint256 const worse = dirKey(book, 2'000'000u);
uint256 const better = dirKey(book, 1'000'000u);
// Higher rate keys sort higher (worse quality). Sanity check.
ASSERT_LT(better, worse);
cache.record(book, worse, 1);
cache.onOfferInsert(book, better, 2);
auto const got = cache.get(book);
ASSERT_TRUE(got.has_value());
EXPECT_EQ(got->firstPageKey, better);
EXPECT_EQ(got->asOfLedger, 2u);
}
TEST(TopOfBookCache, OnOfferInsertSameLeavesTop)
{
TopOfBookCache cache;
Book const book = makeIOUBook(4);
uint256 const key = dirKey(book, 1'000'000u);
cache.record(book, key, 5);
cache.onOfferInsert(book, key, 6);
auto const got = cache.get(book);
ASSERT_TRUE(got.has_value());
EXPECT_EQ(got->firstPageKey, key);
// asOfLedger preserved — same-quality insert is a no-op.
EXPECT_EQ(got->asOfLedger, 5u);
}
TEST(TopOfBookCache, OnOfferInsertWorseLeavesTop)
{
TopOfBookCache cache;
Book const book = makeIOUBook(5);
uint256 const best = dirKey(book, 1'000'000u);
uint256 const worse = dirKey(book, 3'000'000u);
ASSERT_LT(best, worse);
cache.record(book, best, 5);
cache.onOfferInsert(book, worse, 9);
auto const got = cache.get(book);
ASSERT_TRUE(got.has_value());
EXPECT_EQ(got->firstPageKey, best);
EXPECT_EQ(got->asOfLedger, 5u);
}
TEST(TopOfBookCache, OnOfferInsertWithoutEntryIsNoOp)
{
TopOfBookCache cache;
Book const book = makeIOUBook(6);
uint256 const key = dirKey(book, 1'000u);
// No prior entry — we don't speculatively populate.
cache.onOfferInsert(book, key, 1);
EXPECT_FALSE(cache.get(book).has_value());
}
TEST(TopOfBookCache, OnOfferDeleteOfTopInvalidates)
{
TopOfBookCache cache;
Book const book = makeIOUBook(7);
uint256 const top = dirKey(book, 1'000u);
cache.record(book, top, 1);
cache.onOfferDelete(book, top);
EXPECT_FALSE(cache.get(book).has_value());
EXPECT_EQ(cache.invalidations(), 1u);
}
TEST(TopOfBookCache, OnOfferDeleteOfOtherPageLeavesTop)
{
TopOfBookCache cache;
Book const book = makeIOUBook(8);
uint256 const top = dirKey(book, 1'000u);
uint256 const worsePage = dirKey(book, 4'000u);
cache.record(book, top, 1);
cache.onOfferDelete(book, worsePage);
auto const got = cache.get(book);
ASSERT_TRUE(got.has_value());
EXPECT_EQ(got->firstPageKey, top);
EXPECT_EQ(cache.invalidations(), 0u);
}
TEST(TopOfBookCache, DistinctBooksIndependent)
{
TopOfBookCache cache;
Book const a = makeIOUBook(10);
Book const b = makeIOUBook(11);
cache.record(a, dirKey(a, 100u), 1);
cache.record(b, dirKey(b, 200u), 2);
EXPECT_TRUE(cache.get(a).has_value());
EXPECT_TRUE(cache.get(b).has_value());
EXPECT_EQ(cache.size(), 2u);
cache.onOfferDelete(a, dirKey(a, 100u));
EXPECT_FALSE(cache.get(a).has_value());
EXPECT_TRUE(cache.get(b).has_value());
EXPECT_EQ(cache.size(), 1u);
}
TEST(TopOfBookCache, InvalidateUnconditional)
{
TopOfBookCache cache;
Book const book = makeIOUBook(12);
cache.record(book, dirKey(book, 100u), 1);
cache.invalidate(book);
EXPECT_FALSE(cache.get(book).has_value());
EXPECT_EQ(cache.invalidations(), 1u);
// Re-invalidating doesn't double-count.
cache.invalidate(book);
EXPECT_EQ(cache.invalidations(), 1u);
}
TEST(TopOfBookCache, KillSwitchToggleable)
{
EXPECT_TRUE(TopOfBookCache::enabled());
TopOfBookCache::setEnabled(false);
EXPECT_FALSE(TopOfBookCache::enabled());
TopOfBookCache::setEnabled(true);
EXPECT_TRUE(TopOfBookCache::enabled());
}
} // namespace xrpl::test

View File

@@ -1,8 +0,0 @@
#include <gtest/gtest.h>
int
main(int argc, char** argv)
{
::testing::InitGoogleTest(&argc, argv);
return RUN_ALL_TESTS();
}

View File

@@ -1084,6 +1084,21 @@ public:
<< "; size after: " << cachedSLEs_.size();
}
{
auto const peakStrong =
xrpl::detail::kPeakStrongObserved.load(std::memory_order_relaxed);
auto const peakWeak =
xrpl::detail::kPeakWeakObserved.load(std::memory_order_relaxed);
constexpr std::uint32_t kStrongLimit = 65503; // kCheckStrongMaxValue
constexpr std::uint32_t kWeakLimit = 16351; // kCheckWeakMaxValue
JLOG(journal_.warn())
<< "RefCount peak since startup: "
<< "strong=" << peakStrong << "/" << kStrongLimit
<< " (" << (peakStrong * 100 / kStrongLimit) << "%); "
<< "weak=" << peakWeak << "/" << kWeakLimit
<< " (" << (peakWeak * 100 / kWeakLimit) << "%)";
}
mallocTrim("doSweep", journal_);
// Set timer to do another sweep later.