Fixing a quadratic slowdown in libxml2's XSD validation

E-invoices often carry their attachments inside the XML: the PDF of the invoice, a delivery note, a timesheet, each one base64-encoded into a single element (cbc:EmbeddedDocumentBinaryObject in UBL, business term BT-125 in EN 16931). A 20 MB PDF becomes a 27 MB text node.

Validated against its XSD with libxml2 as a stream, an invoice with a 30 MB attachment takes longer than a 1 GB document without one. The time does not go into the document; it goes into that one element. This post is about why, and about the fix we now run and have sent to libxml2.

The shape of the problem

To isolate it, I took the smallest schema that shows it, one element of type xs:base64Binary:

<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <xs:element name="attachment" type="xs:base64Binary"/>
</xs:schema>

and documents holding nothing but random bytes in base64, in 76-character lines like a real attachment. Then I timed xmllint --stream --schema from libxml2 2.15.4 (with --huge, which lifts the 10 MB limit on a text node) on an Apple M4:

Double the size, four times the time. That is the signature of a quadratic algorithm, and at these sizes it stops being a curiosity: an invoice with a scanned contract attached takes a quarter of a minute, a large one several minutes, for a check that should take a fraction of a second.

Where the time goes

libxml2 can validate in two ways. It can build the whole document as a tree and walk the tree against the schema, or it can validate while it reads, with the streaming xmlTextReader, which is what you use when a document might not fit in memory. xmlvalid's engine always streams; it is how a 5 GB file validates in the browser with flat memory.

When streaming, the parser hands text to the schema validator in pieces as it reads it. An instrumented build shows the pieces are at most 512 bytes, so a 30 MB text node arrives as about 62,000 of them. The validator needs the whole value to check it against its type, so it glues the pieces together in xmlSchemaVPushText:

if (vctxt->inode->flags & XML_SCHEMA_NODE_INFO_FLAG_OWNED_VALUES) {
    vctxt->inode->value = BAD_CAST xmlStrncat(
        (xmlChar *) vctxt->inode->value, value, len);
} else {
    vctxt->inode->value =
        BAD_CAST xmlStrncatNew(vctxt->inode->value, value, len);
    vctxt->inode->flags |= XML_SCHEMA_NODE_INFO_FLAG_OWNED_VALUES;
}

xmlStrncat is the textbook string append. It does not know how long the existing string is, so it finds out with strlen, then asks realloc for exactly enough room for the new piece:

size = xmlStrlen(cur);
ret = (xmlChar *) xmlRealloc(cur, (size_t) size + len + 1);
memcpy(&ret[size], add, len);
ret[size + len] = 0;

Each of the 62,000 appends reads the whole value so far to find its end. On average that is half the final length, 15 MB, so the appends read about a terabyte of memory between them to build a 30 MB string. The realloc to the exact size adds a copy whenever the allocator cannot grow the block in place.

The tree-based path does not have this problem. There the text node already exists in one piece, and the same 30 MB document validates in 0.17 s. Most tools that validate XML build a tree, which may be why the issue, filed by libxml2's maintainer in 2023, stayed open: it only shows up in the mode you choose precisely because your documents are large.

The fix

The usual cure for a slow append is to remember two numbers next to the buffer: how much of it is used and how much is allocated. Appending then copies only the new piece, and when the buffer is full it doubles, so the total copying stays proportional to the final length.

The node info structure the validator keeps for each open element gets the two fields:

size_t valueLen;  /* length of an owned, concatenated value */
size_t valueSize; /* its allocated size; 0 until the first concat */

and the append becomes:

need = inode->valueLen + len + 1;
if (need > inode->valueSize) {
    size_t size = inode->valueSize * 2;

    if (size < need)
        size = need;
    buf = xmlRealloc((xmlChar *) inode->value, size);
    /* ... out of memory handling ... */
    inode->value = buf;
    inode->valueSize = size;
}
buf = (xmlChar *) inode->value;
memcpy(buf + inode->valueLen, value, len);
inode->valueLen += len;
buf[inode->valueLen] = 0;

Two details matter more than the loop. The first piece of a value may still point into memory the validator does not own, so on the first append it is copied into a buffer of its own, which is also the one moment strlen is called. And the lengths are checked against INT_MAX before adding, because the rest of libxml2 measures strings in int, and a validator that people feed untrusted documents should not be the place where a length wraps.

The result, same files, same machine:

Linear, as it should be: about 5 ms per megabyte.

Running it and sending it upstream

The patch changes about fifty lines of xmlschemas.c and applies to libxml2 2.13 and 2.15. xmlvalid builds its own libxml2 for both engines, the native one behind the API and the command-line client and the WebAssembly one in the browser, so it runs the patched version everywhere. Business rules on large invoices have their own limits, covered in the 5 GB post; the schema check no longer cares how big an attachment is.

A fix that only lives in one product's build helps that product. libxml2 is in nearly every Linux system and underneath PHP's XML extensions, Python's lxml and Ruby's Nokogiri, so the change went to libxml2 as merge request !471, which closes issue #516. At the time of writing it passes CI and is waiting for review. When a release includes it, our local patch goes away.

If you validate large documents

Until then, a few things are worth knowing if your own code streams XML through libxml2 against an XSD, directly or through a binding:

• Time it on your largest text node, not your largest file. A 2 GB file of small elements is fast; a 30 MB file with one big element is not.
• Base64 is the usual culprit. Embedded PDFs and images in invoices, SOAP attachments (MTOM aside), signed documents with certificates inline.
• A tree-based validation of the same file is fast if the document fits in memory, at the cost of the memory.
• Or validate in the browser. The validator runs the patched libxml2 compiled to WebAssembly, so a large invoice with attachments checks in about the time it takes to read it, and stays on your machine.

More from the blog

• Why is my XML valid but still rejected?
• Validating a 5 GB XML file in the browser