Remembered places and the fallback's text: sibling and subtree rescans make one captured page cost minutes #588

New issue

Closed

opened 2026-10-01 10:48:06 +00:00 by tiagoagueda · 1 comment

tiagoagueda commented

2026-10-01 10:48:06 +00:00

Owner

Found on 2026-09-29 in a read-only review of postulo at 95348908d, reading the remembered-places reader and the link-farm measure and timing them on generated pages.

Checked again on 2026-10-01 against main at 0a5cad587: still present. plugins/builtin/ has not changed; the API's calls to after_capture are now at api/api.py:547-551 and the unthrottled html path at api/api.py:605-607.

The remembered-places reader finds what a label labels by scanning the label's parent from its first child every time, so a parent with k label-like children costs O(k²). The fallback's link-farm measure re-walks the whole subtree of every container it meets, which costs O(n × depth). Both run on every capture, inside the request or the capture errand, over pages of up to 2 MB, and a page of a few hundred kilobytes is enough to hold a worker for minutes.

Where:
- plugins/builtin/hints.py:246-263 (_labels) visits every dt, th, td, label, strong, b and span. For each, _next_element (:183-191) scans the parent's children from the start until it finds the element; a td also rebuilds the list of its row's cells (:237, cells = [c for c in element.parent.children if isinstance(c, Element)]); a "Label:" runs _rest_of_line (:202-225), which again starts from the parent's first child and calls text_of on each child after the label.
- plugins/builtin/htmlutil.py:293-322 (_link_farms) runs element.iter(), _text_length(element) and _text_length of every link for each div, section, ul, ol, aside and nav that is not already inside a farm, plus an ancestor walk (:310) for every element.
- Callers: jobs/remembered.py:276 (after_capture, through registry.page_places) runs in the API request (api/api.py:545-549) and in the capture errand; hints.fill runs _labels again (hints.py:347) whenever a label place is remembered; main_text (htmlutil.py:325-357) runs _link_farms for every page the fallback reads.
What happens: measured with registry.page_places: one <tr> holding 2,500 / 5,000 / 10,000 closed <td> (25 / 50 / 100 KB) took 0.4 s / 1.6 s / 6.5 s; one <p> holding 2,500 / 5,000 / 10,000 <span>a:</span> b pairs took 0.2 s / 0.8 s / 3.5 s; a <dl> of 2,500 / 5,000 pairs took 0.24 s / 0.87 s. Each doubling quadruples the time, so a 2 MB page of the same shape runs far past gunicorn's 120 s --timeout (docker/Dockerfile:354). main_text over 500 links and prose inside 100 / 200 / 400 nested <div>s (about 50 KB) took 0.4 s / 0.9 s / 1.9 s, linear in depth for the same size.
Who can trigger it: anyone who can get a page captured: the site behind an address a person captures, or an account holder sending html through POST /api/v1/captures with a captures token (that path is not throttled by throttle.capture, api/api.py:603-605). The instance runs three workers (docker/Dockerfile:362), and an errand has no gunicorn timeout at all.
Why it matters: a single capture can hold a worker until it is killed, and three hold the whole instance; a reverse proxy's limits, which the threat model leaves denial of service to, cannot see the cost of a 100 KB body. The only bounds, MOST_BYTES and PER_KIND, cap the output after the work is done.
Fix: compute each element's position among its siblings once: build a next-sibling map in one pass over parent.children in _labels (or record it in _TreeBuilder), check the "row of exactly two cells" condition once per row, and have _rest_of_line start from the label's own index. In _link_farms, compute each node's text length and link-text length bottom-up in one post-order pass and decide farms from those totals, so the page costs O(n). Bound places and _labels by the number of elements visited as well as by output size.

Done when

A test in tests/test_remembered_places.py runs hints.places over one <tr> of 20,000 cells and over a <p> of 20,000 "Label:" spans and finishes in well under a second (a generous bound such as 2 s, which the present code misses by more than an order of magnitude).
A test in tests/test_page_metadata.py runs htmlutil.main_text over 400 nested <div>s holding links and prose and stays within the same kind of bound.

Found on 2026-09-29 in a read-only review of postulo at 95348908d, reading the remembered-places reader and the link-farm measure and timing them on generated pages. Checked again on 2026-10-01 against `main` at `0a5cad587`: still present. `plugins/builtin/` has not changed; the API's calls to `after_capture` are now at `api/api.py:547-551` and the unthrottled `html` path at `api/api.py:605-607`. The remembered-places reader finds what a label labels by scanning the label's parent from its first child every time, so a parent with k label-like children costs O(k²). The fallback's link-farm measure re-walks the whole subtree of every container it meets, which costs O(n × depth). Both run on every capture, inside the request or the capture errand, over pages of up to 2 MB, and a page of a few hundred kilobytes is enough to hold a worker for minutes. - **Where:** - `plugins/builtin/hints.py:246-263` (`_labels`) visits every `dt`, `th`, `td`, `label`, `strong`, `b` and `span`. For each, `_next_element` (`:183-191`) scans the parent's children from the start until it finds the element; a `td` also rebuilds the list of its row's cells (`:237`, `cells = [c for c in element.parent.children if isinstance(c, Element)]`); a "Label:" runs `_rest_of_line` (`:202-225`), which again starts from the parent's first child and calls `text_of` on each child after the label. - `plugins/builtin/htmlutil.py:293-322` (`_link_farms`) runs `element.iter()`, `_text_length(element)` and `_text_length` of every link for each `div`, `section`, `ul`, `ol`, `aside` and `nav` that is not already inside a farm, plus an ancestor walk (`:310`) for every element. - Callers: `jobs/remembered.py:276` (`after_capture`, through `registry.page_places`) runs in the API request (`api/api.py:545-549`) and in the capture errand; `hints.fill` runs `_labels` again (`hints.py:347`) whenever a label place is remembered; `main_text` (`htmlutil.py:325-357`) runs `_link_farms` for every page the fallback reads. - **What happens:** measured with `registry.page_places`: one `<tr>` holding 2,500 / 5,000 / 10,000 closed `<td>` (25 / 50 / 100 KB) took 0.4 s / 1.6 s / 6.5 s; one `<p>` holding 2,500 / 5,000 / 10,000 `<span>a:</span> b` pairs took 0.2 s / 0.8 s / 3.5 s; a `<dl>` of 2,500 / 5,000 pairs took 0.24 s / 0.87 s. Each doubling quadruples the time, so a 2 MB page of the same shape runs far past gunicorn's 120 s `--timeout` (`docker/Dockerfile:354`). `main_text` over 500 links and prose inside 100 / 200 / 400 nested `<div>`s (about 50 KB) took 0.4 s / 0.9 s / 1.9 s, linear in depth for the same size. - **Who can trigger it:** anyone who can get a page captured: the site behind an address a person captures, or an account holder sending `html` through `POST /api/v1/captures` with a `captures` token (that path is not throttled by `throttle.capture`, `api/api.py:603-605`). The instance runs three workers (`docker/Dockerfile:362`), and an errand has no gunicorn timeout at all. - **Why it matters:** a single capture can hold a worker until it is killed, and three hold the whole instance; a reverse proxy's limits, which the threat model leaves denial of service to, cannot see the cost of a 100 KB body. The only bounds, `MOST_BYTES` and `PER_KIND`, cap the output after the work is done. - **Fix:** compute each element's position among its siblings once: build a next-sibling map in one pass over `parent.children` in `_labels` (or record it in `_TreeBuilder`), check the "row of exactly two cells" condition once per row, and have `_rest_of_line` start from the label's own index. In `_link_farms`, compute each node's text length and link-text length bottom-up in one post-order pass and decide farms from those totals, so the page costs O(n). Bound `places` and `_labels` by the number of elements visited as well as by output size. ## Done when - A test in `tests/test_remembered_places.py` runs `hints.places` over one `<tr>` of 20,000 cells and over a `<p>` of 20,000 "Label:" spans and finishes in well under a second (a generous bound such as 2 s, which the present code misses by more than an order of magnitude). - A test in `tests/test_page_metadata.py` runs `htmlutil.main_text` over 400 nested `<div>`s holding links and prose and stays within the same kind of bound.

tiagoagueda added this to the 0.6.0 milestone

2026-10-01 10:48:06 +00:00

tiagoagueda added the

enhancement

label

2026-10-01 10:48:06 +00:00

tiagoagueda referenced this issue from a commit

2026-10-06 04:51:05 +00:00

Read remembered places and link farms in one pass over the page

tiagoagueda commented

2026-10-06 09:32:15 +00:00

Author