Add support for custom allocators

This makes it explicit in the API where memory is allocated, and allows the
user to provide a custom allocator to avoid the use of the default system
allocator for whatever reason.

55 files changed, 1823 insertions, 819 deletions

diff --git a/doc/conf.py.in b/doc/conf.py.in
index e3e7f1ad..51a09d4e 100644
--- a/doc/conf.py.in
+++ b/doc/conf.py.in
@@ -27,6 +27,7 @@ except ModuleNotFoundError:
 # Ignore everything opaque or external for nitpicky mode
 _opaque = [
     "FILE",
+    "SerdAllocatorImpl",
     "SerdCaretImpl",
     "SerdEnvImpl",
     "SerdNodeImpl",
diff --git a/include/serd/buffer.h b/include/serd/buffer.h
index 20abfb29..a56188e7 100644
--- a/include/serd/buffer.h
+++ b/include/serd/buffer.h
@@ -5,6 +5,7 @@
 #define SERD_BUFFER_H
 
 #include "serd/attributes.h"
+#include "serd/memory.h"
 #include "zix/attributes.h"
 
 #include <stddef.h>
@@ -23,18 +24,19 @@ SERD_BEGIN_DECLS
    @{
 */
 
-/// A mutable buffer in memory
+/// A dynamically resizable mutable buffer in memory
 typedef struct {
-  void* ZIX_NULLABLE buf; ///< Buffer
-  size_t             len; ///< Size of buffer in bytes
+  SerdAllocator* ZIX_NULLABLE allocator; ///< Allocator for buf
+  void* ZIX_NULLABLE          buf;       ///< Buffer
+  size_t                      len;       ///< Size of buffer in bytes
 } SerdBuffer;
 
 /**
    A function for writing to a buffer, resizing it if necessary.
 
    This function can be used as a #SerdWriteFunc to write to a #SerdBuffer
-   which is resized as necessary with realloc().  The `stream` parameter must
-   point to an initialized #SerdBuffer.
+   which is reallocated as necessary.  The `stream` parameter must point to an
+   initialized #SerdBuffer.
 
    Note that when writing a string, the string in the buffer will not be
    null-terminated until serd_buffer_close() is called.
diff --git a/include/serd/caret.h b/include/serd/caret.h
index 429a6fcd..54df0932 100644
--- a/include/serd/caret.h
+++ b/include/serd/caret.h
@@ -5,6 +5,7 @@
 #define SERD_CARET_H
 
 #include "serd/attributes.h"
+#include "serd/memory.h"
 #include "serd/node.h"
 #include "zix/attributes.h"
 
@@ -29,23 +30,27 @@ typedef struct SerdCaretImpl SerdCaret;
    valid.  That is, serd_caret_document() will return exactly the pointer
    `document`, not a copy.
 
+   @param allocator Allocator to use for caret memory.
    @param document The document or the caret refers to (usually a file URI)
    @param line The line number in the document (1-based)
    @param column The column number in the document (1-based)
    @return A new caret that must be freed with serd_caret_free()
 */
 SERD_API SerdCaret* ZIX_ALLOCATED
-serd_caret_new(const SerdNode* ZIX_NONNULL document,
+serd_caret_new(SerdAllocator* ZIX_NULLABLE allocator,
+               const SerdNode* ZIX_NONNULL document,
                unsigned                    line,
                unsigned                    column);
 
 /// Return a copy of `caret`
 SERD_API SerdCaret* ZIX_ALLOCATED
-serd_caret_copy(const SerdCaret* ZIX_NULLABLE caret);
+serd_caret_copy(SerdAllocator* ZIX_NULLABLE   allocator,
+                const SerdCaret* ZIX_NULLABLE caret);
 
 /// Free `caret`
 SERD_API void
-serd_caret_free(SerdCaret* ZIX_NULLABLE caret);
+serd_caret_free(SerdAllocator* ZIX_NULLABLE allocator,
+                SerdCaret* ZIX_NULLABLE     caret);
 
 /// Return true iff `lhs` is equal to `rhs`
 SERD_PURE_API bool
diff --git a/include/serd/env.h b/include/serd/env.h
index b4f908a9..a0c47997 100644
--- a/include/serd/env.h
+++ b/include/serd/env.h
@@ -5,6 +5,7 @@
 #define SERD_ENV_H
 
 #include "serd/attributes.h"
+#include "serd/memory.h"
 #include "serd/node.h"
 #include "serd/sink.h"
 #include "serd/status.h"
@@ -26,11 +27,12 @@ typedef struct SerdEnvImpl SerdEnv;
 
 /// Create a new environment
 SERD_API SerdEnv* ZIX_ALLOCATED
-serd_env_new(SerdStringView base_uri);
+serd_env_new(SerdAllocator* ZIX_NULLABLE allocator, SerdStringView base_uri);
 
 /// Copy an environment
 SERD_API SerdEnv* ZIX_ALLOCATED
-serd_env_copy(const SerdEnv* ZIX_NULLABLE env);
+serd_env_copy(SerdAllocator* ZIX_NULLABLE allocator,
+              const SerdEnv* ZIX_NULLABLE env);
 
 /// Return true iff `a` is equal to `b`
 SERD_PURE_API bool
diff --git a/include/serd/memory.h b/include/serd/memory.h
index 050b7597..4a653349 100644
--- a/include/serd/memory.h
+++ b/include/serd/memory.h
@@ -7,6 +7,8 @@
 #include "serd/attributes.h"
 #include "zix/attributes.h"
 
+#include <stddef.h>
+
 SERD_BEGIN_DECLS
 
 /**
@@ -16,14 +18,106 @@ SERD_BEGIN_DECLS
 */
 
 /**
+   A memory allocator.
+
+   This object-like structure provides an interface like the standard C
+   functions malloc(), calloc(), realloc(), free(), and aligned_alloc().  It
+   contains function pointers that differ from their standard counterparts by
+   taking a context parameter (a pointer to this struct), which allows the user
+   to implement custom stateful allocators.
+*/
+typedef struct SerdAllocatorImpl SerdAllocator;
+
+/**
+   General malloc-like memory allocation function.
+
+   This works like the standard C malloc(), except has an additional handle
+   parameter for implementing stateful allocators without static data.
+*/
+typedef void* ZIX_ALLOCATED (*SerdAllocatorMallocFunc)( //
+  SerdAllocator* ZIX_NULLABLE allocator,
+  size_t                      size);
+
+/**
+   General calloc-like memory allocation function.
+
+   This works like the standard C calloc(), except has an additional handle
+   parameter for implementing stateful allocators without static data.
+*/
+typedef void* ZIX_ALLOCATED (*SerdAllocatorCallocFunc)( //
+  SerdAllocator* ZIX_NULLABLE allocator,
+  size_t                      nmemb,
+  size_t                      size);
+
+/**
+   General realloc-like memory reallocation function.
+
+   This works like the standard C remalloc(), except has an additional handle
+   parameter for implementing stateful allocators without static data.
+*/
+typedef void* ZIX_ALLOCATED (*SerdAllocatorReallocFunc)( //
+  SerdAllocator* ZIX_NULLABLE allocator,
+  void* ZIX_NULLABLE          ptr,
+  size_t                      size);
+
+/**
+   General free-like memory deallocation function.
+
+   This works like the standard C remalloc(), except has an additional handle
+   parameter for implementing stateful allocators without static data.
+*/
+typedef void (*SerdAllocatorFreeFunc)( //
+  SerdAllocator* ZIX_NULLABLE allocator,
+  void* ZIX_NULLABLE          ptr);
+
+/**
+   General aligned_alloc-like memory deallocation function.
+
+   This works like the standard C aligned_alloc(), except has an additional
+   handle parameter for implementing stateful allocators without static data.
+*/
+typedef void* ZIX_ALLOCATED (*SerdAllocatorAlignedAllocFunc)( //
+  SerdAllocator* ZIX_NULLABLE allocator,
+  size_t                      alignment,
+  size_t                      size);
+
+/**
+   General aligned memory deallocation function.
+
+   This works like the standard C free(), but must be used to free memory
+   allocated with the aligned_alloc() method of the allocator.  This allows
+   portability to systems (like Windows) that can not use the same free function
+   in these cases.
+*/
+typedef void (*SerdAllocatorAlignedFreeFunc)( //
+  SerdAllocator* ZIX_NULLABLE allocator,
+  void* ZIX_NULLABLE          ptr);
+
+/// Definition of SerdAllocator
+struct SerdAllocatorImpl {
+  SerdAllocatorMallocFunc ZIX_ALLOCATED       malloc;
+  SerdAllocatorCallocFunc ZIX_ALLOCATED       calloc;
+  SerdAllocatorReallocFunc ZIX_ALLOCATED      realloc;
+  SerdAllocatorFreeFunc ZIX_ALLOCATED         free;
+  SerdAllocatorAlignedAllocFunc ZIX_ALLOCATED aligned_alloc;
+  SerdAllocatorAlignedFreeFunc ZIX_ALLOCATED  aligned_free;
+};
+
+/// Return the default allocator which simply uses the system allocator
+SERD_CONST_API SerdAllocator* ZIX_NONNULL
+serd_default_allocator(void);
+
+/**
    Free memory allocated by Serd.
 
    This function exists because some systems require memory allocated by a
    library to be freed by code in the same library.  It is otherwise equivalent
    to the standard C free() function.
+
+   This may be used to free memory allocated using serd_default_allocator().
 */
 SERD_API void
-serd_free(void* ZIX_NULLABLE ptr);
+serd_free(SerdAllocator* ZIX_NULLABLE allocator, void* ZIX_NULLABLE ptr);
 
 /**
    @}
diff --git a/include/serd/node.h b/include/serd/node.h
index b0b14a24..f42f07f1 100644
--- a/include/serd/node.h
+++ b/include/serd/node.h
@@ -5,6 +5,7 @@
 #define SERD_NODE_H
 
 #include "serd/attributes.h"
+#include "serd/memory.h"
 #include "serd/string_view.h"
 #include "serd/uri.h"
 #include "serd/write_result.h"
@@ -117,13 +118,15 @@ typedef uint32_t SerdNodeFlags;
    to create URIs, blank nodes, CURIEs, and simple string literals.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_token(SerdNodeType type, SerdStringView string);
+serd_new_token(SerdAllocator* ZIX_NULLABLE allocator,
+               SerdNodeType                type,
+               SerdStringView              string);
 
 /**
    Create a new string literal node.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_string(SerdStringView string);
+serd_new_string(SerdAllocator* ZIX_NULLABLE allocator, SerdStringView string);
 
 /**
    Create a new literal node with optional datatype or language.
@@ -132,6 +135,8 @@ serd_new_string(SerdStringView string);
    associated datatype URI or language tag, as well as control whether a
    literal should be written as a short or long (triple-quoted) string.
 
+   @param allocator Allocator for the returned node.
+
    @param string The string value of the literal.
 
    @param flags Flags to describe the literal and its metadata.  This must be a
@@ -147,27 +152,28 @@ serd_new_string(SerdStringView string);
    serd_node_free(), or null if the arguments are invalid or allocation failed.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_literal(SerdStringView string,
-                 SerdNodeFlags  flags,
-                 SerdStringView meta);
+serd_new_literal(SerdAllocator* ZIX_NULLABLE allocator,
+                 SerdStringView              string,
+                 SerdNodeFlags               flags,
+                 SerdStringView              meta);
 
 /**
    Create a new node from a blank node label.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_blank(SerdStringView string);
+serd_new_blank(SerdAllocator* ZIX_NULLABLE allocator, SerdStringView string);
 
 /**
    Create a new URI node from a parsed URI.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_parsed_uri(SerdURIView uri);
+serd_new_parsed_uri(SerdAllocator* ZIX_NULLABLE allocator, SerdURIView uri);
 
 /**
    Create a new URI node from a string.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_uri(SerdStringView string);
+serd_new_uri(SerdAllocator* ZIX_NULLABLE allocator, SerdStringView string);
 
 /**
    Create a new file URI node from a file system path and optional hostname.
@@ -178,13 +184,15 @@ serd_new_uri(SerdStringView string);
    If `path` is relative, `hostname` is ignored.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_file_uri(SerdStringView path, SerdStringView hostname);
+serd_new_file_uri(SerdAllocator* ZIX_NULLABLE allocator,
+                  SerdStringView              path,
+                  SerdStringView              hostname);
 
 /**
    Create a new canonical xsd:boolean node.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_boolean(bool b);
+serd_new_boolean(SerdAllocator* ZIX_NULLABLE allocator, bool b);
 
 /**
    Create a new canonical xsd:decimal literal.
@@ -196,11 +204,14 @@ serd_new_boolean(bool b);
    (a leading and/or trailing '0' will be added if necessary), for example,
    "1.0".  It will never be in scientific notation.
 
+   @param allocator Allocator for the returned node.
    @param d The value for the new node.
    @param datatype Datatype of node, or NULL for xsd:decimal.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_decimal(double d, const SerdNode* ZIX_NULLABLE datatype);
+serd_new_decimal(SerdAllocator* ZIX_NULLABLE  allocator,
+                 double                       d,
+                 const SerdNode* ZIX_NULLABLE datatype);
 
 /**
    Create a new canonical xsd:double literal.
@@ -212,11 +223,12 @@ serd_new_decimal(double d, const SerdNode* ZIX_NULLABLE datatype);
    Uses the shortest possible representation that precisely describes the
    value, which has at most 17 significant digits (under 24 characters total).
 
+   @param allocator Allocator for the returned node.
    @param d Double value to write.
    @return A literal node with datatype xsd:double.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_double(double d);
+serd_new_double(SerdAllocator* ZIX_NULLABLE allocator, double d);
 
 /**
    Create a new canonical xsd:float literal.
@@ -224,11 +236,12 @@ serd_new_double(double d);
    Uses identical formatting to serd_new_double(), except with at most 9
    significant digits (under 14 characters total).
 
+   @param allocator Allocator for the returned node.
    @param f Float value of literal.
    @return A literal node with datatype xsd:float.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_float(float f);
+serd_new_float(SerdAllocator* ZIX_NULLABLE allocator, float f);
 
 /**
    Create a new canonical xsd:integer literal.
@@ -236,10 +249,11 @@ serd_new_float(float f);
    The node will be an xsd:integer literal like "1234", with datatype
    xsd:integer.
 
+   @param allocator Allocator for the returned node.
    @param i Integer value of literal.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_integer(int64_t i);
+serd_new_integer(SerdAllocator* ZIX_NULLABLE allocator, int64_t i);
 
 /**
    Create a new canonical xsd:base64Binary literal.
@@ -247,21 +261,31 @@ serd_new_integer(int64_t i);
    This function can be used to make a node out of arbitrary binary data, which
    can be decoded using serd_base64_decode().
 
+   @param allocator Allocator for the returned node.
    @param buf Raw binary data to encode in node.
    @param size Size of `buf` in bytes.
 */
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_new_base64(const void* ZIX_NONNULL buf, size_t size);
+serd_new_base64(SerdAllocator* ZIX_NULLABLE allocator,
+                const void* ZIX_NONNULL     buf,
+                size_t                      size);
+
+/**
+   Return a deep copy of `node`.
 
-/// Return a deep copy of `node`
+   @param allocator Allocator for the returned node.
+   @param node The node to copyl
+*/
 SERD_API SerdNode* ZIX_ALLOCATED
-serd_node_copy(const SerdNode* ZIX_NULLABLE node);
+serd_node_copy(SerdAllocator* ZIX_NULLABLE  allocator,
+               const SerdNode* ZIX_NULLABLE node);
 
 /**
    Free any data owned by `node`.
 */
 SERD_API void
-serd_node_free(SerdNode* ZIX_NULLABLE node);
+serd_node_free(SerdAllocator* ZIX_NULLABLE allocator,
+               SerdNode* ZIX_NULLABLE      node);
 
 /**
    @}
diff --git a/include/serd/sink.h b/include/serd/sink.h
index 291e8d3f..e34ce941 100644
--- a/include/serd/sink.h
+++ b/include/serd/sink.h
@@ -6,6 +6,7 @@
 
 #include "serd/attributes.h"
 #include "serd/event.h"
+#include "serd/memory.h"
 #include "serd/node.h"
 #include "serd/statement.h"
 #include "serd/status.h"
@@ -65,14 +66,16 @@ typedef void (*SerdFreeFunc)(void* ZIX_NULLABLE ptr);
 /**
    Create a new sink.
 
+   @param allocator Allocator to use for the returned sink.
    @param handle Opaque handle that will be passed to sink functions.
    @param event_func Function that will be called for every event.
    @param free_handle Free function to call on handle in serd_sink_free().
 */
 SERD_API SerdSink* ZIX_ALLOCATED
-serd_sink_new(void* ZIX_NULLABLE         handle,
-              SerdEventFunc ZIX_NULLABLE event_func,
-              SerdFreeFunc ZIX_NULLABLE  free_handle);
+serd_sink_new(SerdAllocator* ZIX_NULLABLE allocator,
+              void* ZIX_NULLABLE          handle,
+              SerdEventFunc ZIX_NULLABLE  event_func,
+              SerdFreeFunc ZIX_NULLABLE   free_handle);
 
 /// Free `sink`
 SERD_API void
diff --git a/include/serd/statement.h b/include/serd/statement.h
index a4109958..03d7ae6d 100644
--- a/include/serd/statement.h
+++ b/include/serd/statement.h
@@ -6,6 +6,7 @@
 
 #include "serd/attributes.h"
 #include "serd/caret.h"
+#include "serd/memory.h"
 #include "serd/node.h"
 #include "zix/attributes.h"
 
@@ -55,6 +56,7 @@ typedef struct SerdStatementImpl SerdStatement;
    statements in models, this is the lifetime of the model.  For user-created
    statements, the simplest way to handle this is to use `SerdNodes`.
 
+   @param allocator Allocator for the returned statement.
    @param s The subject
    @param p The predicate ("key")
    @param o The object ("value")
@@ -63,7 +65,8 @@ typedef struct SerdStatementImpl SerdStatement;
    @return A new statement that must be freed with serd_statement_free()
 */
 SERD_API SerdStatement* ZIX_ALLOCATED
-serd_statement_new(const SerdNode* ZIX_NONNULL   s,
+serd_statement_new(SerdAllocator* ZIX_NULLABLE   allocator,
+                   const SerdNode* ZIX_NONNULL   s,
                    const SerdNode* ZIX_NONNULL   p,
                    const SerdNode* ZIX_NONNULL   o,
                    const SerdNode* ZIX_NULLABLE  g,
@@ -71,11 +74,13 @@ serd_statement_new(const SerdNode* ZIX_NONNULL   s,
 
 /// Return a copy of `statement`
 SERD_API SerdStatement* ZIX_ALLOCATED
-serd_statement_copy(const SerdStatement* ZIX_NULLABLE statement);
+serd_statement_copy(SerdAllocator* ZIX_NULLABLE       allocator,
+                    const SerdStatement* ZIX_NULLABLE statement);
 
 /// Free `statement`
 SERD_API void
-serd_statement_free(SerdStatement* ZIX_NULLABLE statement);
+serd_statement_free(SerdAllocator* ZIX_NULLABLE allocator,
+                    SerdStatement* ZIX_NULLABLE statement);
 
 /// Return the given node of the statement
 SERD_PURE_API const SerdNode* ZIX_NULLABLE
diff --git a/include/serd/uri.h b/include/serd/uri.h
index 7a63f183..c978782f 100644
--- a/include/serd/uri.h
+++ b/include/serd/uri.h
@@ -5,6 +5,7 @@
 #define SERD_URI_H
 
 #include "serd/attributes.h"
+#include "serd/memory.h"
 #include "serd/stream.h"
 #include "serd/string_view.h"
 #include "zix/attributes.h"
@@ -55,12 +56,15 @@ static const SerdURIView SERD_URI_NULL =
 
    The returned path and `*hostname` must be freed with serd_free().
 
+   @param allocator Allocator for the returned string.
    @param uri A file URI.
    @param hostname If non-NULL, set to the hostname, if present.
-   @return A newly-allocated filesystem path.
+
+   @return A newly allocated path string that must be freed with serd_free().
 */
 SERD_API char* ZIX_ALLOCATED
-serd_parse_file_uri(const char* ZIX_NONNULL         uri,
+serd_parse_file_uri(SerdAllocator* ZIX_NULLABLE     allocator,
+                    const char* ZIX_NONNULL         uri,
                     char* ZIX_NONNULL* ZIX_NULLABLE hostname);
 
 /// Return true iff `string` starts with a valid URI scheme
diff --git a/include/serd/world.h b/include/serd/world.h
index 9440e6eb..dc2b3b83 100644
--- a/include/serd/world.h
+++ b/include/serd/world.h
@@ -5,6 +5,7 @@
 #define SERD_WORLD_H
 
 #include "serd/attributes.h"
+#include "serd/memory.h"
 #include "serd/node.h"
 #include "serd/status.h"
 #include "zix/attributes.h"
@@ -35,12 +36,16 @@ typedef struct {
    shared between worlds.
 */
 SERD_MALLOC_API SerdWorld* ZIX_ALLOCATED
-serd_world_new(void);
+serd_world_new(SerdAllocator* ZIX_NULLABLE allocator);
 
 /// Free `world`
 SERD_API void
 serd_world_free(SerdWorld* ZIX_NULLABLE world);
 
+/// Return the allocator used by `world`
+SERD_PURE_API SerdAllocator* ZIX_NONNULL
+serd_world_allocator(const SerdWorld* ZIX_NONNULL world);
+
 /**
    Return the current resource limits.
 
diff --git a/meson.build b/meson.build
index 4cf4e8d6..ad745658 100644
--- a/meson.build
+++ b/meson.build
@@ -88,10 +88,6 @@ else
       'fcntl.h',
       'posix_fadvise(0, 0, 4096, POSIX_FADV_SEQUENTIAL);',
     ],
-    'posix_memalign': [
-      'stdlib.h',
-      'void* mem=NULL; posix_memalign(&mem, 8U, 8U);',
-    ],
     'strerror_r': [
       'string.h',
       'char buf[128]; return strerror_r(0, &buf, sizeof(buf));',
@@ -165,6 +161,7 @@ sources = files(
   'src/env.c',
   'src/input_stream.c',
   'src/log.c',
+  'src/memory.c',
   'src/node.c',
   'src/output_stream.c',
   'src/read_nquads.c',
diff --git a/meson/suppressions/meson.build b/meson/suppressions/meson.build
index dba5c46c..8e825cac 100644
--- a/meson/suppressions/meson.build
+++ b/meson/suppressions/meson.build
@@ -53,6 +53,7 @@ if is_variable('cc')
       c_suppressions += [
         '-Wno-format-nonliteral',
         '-Wno-inline',
+        '-Wno-null-dereference', # ARM32
         '-Wno-padded',
         '-Wno-switch-default',
         '-Wno-unsuffixed-float-constants',
diff --git a/src/block_dumper.c b/src/block_dumper.c
index 174f0215..21a10fcc 100644
--- a/src/block_dumper.c
+++ b/src/block_dumper.c
@@ -2,12 +2,15 @@
 // SPDX-License-Identifier: ISC
 
 #include "block_dumper.h"
+
+#include "memory.h"
 #include "system.h"
 
 #include <stddef.h>
 
 SerdStatus
-serd_block_dumper_open(SerdBlockDumper* const  dumper,
+serd_block_dumper_open(const SerdWorld* const  world,
+                       SerdBlockDumper* const  dumper,
                        SerdOutputStream* const output,
                        const size_t            block_size)
 {
@@ -24,7 +27,7 @@ serd_block_dumper_open(SerdBlockDumper* const  dumper,
     return SERD_SUCCESS;
   }
 
-  dumper->buf = (char*)serd_allocate_buffer(block_size);
+  dumper->buf = (char*)serd_waligned_alloc(world, SERD_PAGE_SIZE, block_size);
   return dumper->buf ? SERD_SUCCESS : SERD_BAD_ALLOC;
 }
 
@@ -50,5 +53,5 @@ serd_block_dumper_flush(SerdBlockDumper* const dumper)
 void
 serd_block_dumper_close(SerdBlockDumper* const dumper)
 {
-  serd_free_aligned(dumper->buf);
+  serd_aaligned_free(dumper->allocator, dumper->buf);
 }
diff --git a/src/block_dumper.h b/src/block_dumper.h
index 24fb977c..e5a2c318 100644
--- a/src/block_dumper.h
+++ b/src/block_dumper.h
@@ -4,14 +4,18 @@
 #ifndef SERD_SRC_BLOCK_DUMPER_H
 #define SERD_SRC_BLOCK_DUMPER_H
 
+#include "serd/memory.h"
 #include "serd/output_stream.h"
 #include "serd/status.h"
+#include "serd/world.h"
 #include "zix/attributes.h"
 
 #include <stddef.h>
 #include <string.h>
 
 typedef struct {
+  SerdAllocator* ZIX_NONNULL allocator; ///< Buffer allocator
+
   SerdOutputStream* ZIX_ALLOCATED out;        ///< Output stream to write to
   char* ZIX_ALLOCATED             buf;        ///< Local buffer if needed
   size_t                          size;       ///< Bytes pending for this block
@@ -25,7 +29,8 @@ typedef struct {
    calling serd_block_dumper_close().
 */
 SerdStatus
-serd_block_dumper_open(SerdBlockDumper* ZIX_NONNULL  dumper,
+serd_block_dumper_open(const SerdWorld* ZIX_NONNULL  world,
+                       SerdBlockDumper* ZIX_NONNULL  dumper,
                        SerdOutputStream* ZIX_NONNULL output,
                        size_t                        block_size);
 
diff --git a/src/buffer.c b/src/buffer.c
index befa3943..c16a0ad6 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -1,11 +1,12 @@
 // Copyright 2011-2021 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
+#include "memory.h"
+
 #include "serd/buffer.h"
 
 #include <assert.h>
 #include <stddef.h>
-#include <stdlib.h>
 #include <string.h>
 
 size_t
@@ -20,20 +21,21 @@ serd_buffer_write(const void* const buf,
   SerdBuffer* const buffer  = (SerdBuffer*)stream;
   const size_t      n_bytes = size * nmemb;
 
-  char* const new_buf = (char*)realloc(buffer->buf, buffer->len + n_bytes);
+  char* const new_buf =
+    (char*)serd_arealloc(buffer->allocator, buffer->buf, buffer->len + n_bytes);
+
   if (new_buf) {
     memcpy(new_buf + buffer->len, buf, n_bytes);
     buffer->buf = new_buf;
     buffer->len += nmemb;
+    return n_bytes;
   }
 
-  return new_buf ? nmemb : 0;
+  return 0;
 }
 
 int
 serd_buffer_close(void* const stream)
 {
-  serd_buffer_write("", 1, 1, stream); // Write null terminator
-
-  return 0;
+  return serd_buffer_write("", 1, 1, stream) != 1; // Write null terminator
 }
diff --git a/src/byte_source.c b/src/byte_source.c
index e4810b60..cf9a2466 100644
--- a/src/byte_source.c
+++ b/src/byte_source.c
@@ -3,6 +3,7 @@
 
 #include "byte_source.h"
 
+#include "memory.h"
 #include "system.h"
 
 #include "serd/node.h"
@@ -11,7 +12,6 @@
 #include <assert.h>
 #include <stdbool.h>
 #include <stdint.h>
-#include <stdlib.h>
 #include <string.h>
 
 SerdStatus
@@ -40,33 +40,48 @@ serd_byte_source_page(SerdByteSource* const source)
 }
 
 static void
-serd_byte_source_init_buffer(SerdByteSource* const source)
+serd_byte_source_init_buffer(SerdAllocator* const  allocator,
+                             SerdByteSource* const source)
 {
   if (source->block_size > 1) {
-    source->block    = (uint8_t*)serd_allocate_buffer(source->block_size);
-    source->read_buf = source->block;
-    memset(source->block, '\0', source->block_size);
+    source->block = (uint8_t*)serd_aaligned_alloc(
+      allocator, SERD_PAGE_SIZE, source->block_size);
+
+    if ((source->read_buf = source->block)) {
+      memset(source->block, '\0', source->block_size);
+    }
   } else {
     source->read_buf = &source->read_byte;
   }
 }
 
 SerdByteSource*
-serd_byte_source_new_input(SerdInputStream* const input,
+serd_byte_source_new_input(SerdAllocator* const   allocator,
+                           SerdInputStream* const input,
                            const SerdNode* const  name,
                            const size_t           block_size)
 {
   assert(input);
+  assert(block_size);
+  assert(input->stream);
 
-  if (!block_size || !input->stream) {
+  SerdNode* const source_name =
+    name ? serd_node_copy(allocator, name)
+         : serd_new_string(allocator, serd_string("input"));
+
+  if (!source_name) {
     return NULL;
   }
 
-  SerdByteSource* source = (SerdByteSource*)calloc(1, sizeof(SerdByteSource));
+  SerdByteSource* source =
+    (SerdByteSource*)serd_acalloc(allocator, 1, sizeof(SerdByteSource));
 
-  source->name =
-    name ? serd_node_copy(name) : serd_new_string(serd_string("input"));
+  if (!source) {
+    serd_node_free(allocator, source_name);
+    return NULL;
+  }
 
+  source->name           = source_name;
   source->in             = input;
   source->block_size     = block_size;
   source->buf_size       = block_size;
@@ -74,21 +89,27 @@ serd_byte_source_new_input(SerdInputStream* const input,
   source->caret.line     = 1U;
   source->caret.col      = 1U;
 
-  serd_byte_source_init_buffer(source);
+  serd_byte_source_init_buffer(allocator, source);
+  if (block_size > 1 && !source->block) {
+    serd_node_free(allocator, source_name);
+    serd_afree(allocator, source);
+    return NULL;
+  }
 
   return source;
 }
 
 void
-serd_byte_source_free(SerdByteSource* const source)
+serd_byte_source_free(SerdAllocator* const  allocator,
+                      SerdByteSource* const source)
 {
   if (source) {
     if (source->block_size > 1) {
-      serd_free_aligned(source->block);
+      serd_aaligned_free(allocator, source->block);
     }
 
-    serd_node_free(source->name);
-    free(source);
+    serd_node_free(allocator, source->name);
+    serd_afree(allocator, source);
   }
 }
 
diff --git a/src/byte_source.h b/src/byte_source.h
index 3a16a7c6..ba63e794 100644
--- a/src/byte_source.h
+++ b/src/byte_source.h
@@ -8,6 +8,7 @@
 
 #include "serd/caret.h"
 #include "serd/input_stream.h"
+#include "serd/memory.h"
 #include "serd/node.h"
 #include "serd/status.h"
 #include "zix/attributes.h"
@@ -32,12 +33,13 @@ typedef struct {
 } SerdByteSource;
 
 SerdByteSource*
-serd_byte_source_new_input(SerdInputStream* input,
+serd_byte_source_new_input(SerdAllocator*   allocator,
+                           SerdInputStream* input,
                            const SerdNode*  name,
                            size_t           block_size);
 
 void
-serd_byte_source_free(SerdByteSource* source);
+serd_byte_source_free(SerdAllocator* allocator, SerdByteSource* source);
 
 SerdStatus
 serd_byte_source_prepare(SerdByteSource* source);
diff --git a/src/caret.c b/src/caret.c
index 02d5b94b..2d7e9a8e 100644
--- a/src/caret.c
+++ b/src/caret.c
@@ -3,7 +3,10 @@
 
 #include "caret.h"
 
+#include "memory.h"
+
 #include "serd/caret.h"
+#include "serd/memory.h"
 
 #include <assert.h>
 #include <stdbool.h>
@@ -11,13 +14,15 @@
 #include <string.h>
 
 SerdCaret*
-serd_caret_new(const SerdNode* const document,
+serd_caret_new(SerdAllocator* const  allocator,
+               const SerdNode* const document,
                const unsigned        line,
                const unsigned        column)
 {
   assert(document);
 
-  SerdCaret* caret = (SerdCaret*)malloc(sizeof(SerdCaret));
+  SerdCaret* const caret =
+    (SerdCaret*)serd_amalloc(allocator, sizeof(SerdCaret));
 
   if (caret) {
     caret->document = document;
@@ -29,21 +34,26 @@ serd_caret_new(const SerdNode* const document,
 }
 
 SerdCaret*
-serd_caret_copy(const SerdCaret* const caret)
+serd_caret_copy(SerdAllocator* const allocator, const SerdCaret* const caret)
 {
   if (!caret) {
     return NULL;
   }
 
-  SerdCaret* copy = (SerdCaret*)malloc(sizeof(SerdCaret));
-  memcpy(copy, caret, sizeof(SerdCaret));
+  SerdCaret* const copy =
+    (SerdCaret*)serd_amalloc(allocator, sizeof(SerdCaret));
+
+  if (copy) {
+    memcpy(copy, caret, sizeof(SerdCaret));
+  }
+
   return copy;
 }
 
 void
-serd_caret_free(SerdCaret* const caret)
+serd_caret_free(SerdAllocator* const allocator, SerdCaret* const caret)
 {
-  free(caret);
+  serd_afree(allocator, caret);
 }
 
 bool
diff --git a/src/env.c b/src/env.c
index e9af7d77..90924cd2 100644
--- a/src/env.c
+++ b/src/env.c
@@ -4,6 +4,7 @@
 #include "serd/env.h"
 
 #include "env.h"
+#include "memory.h"
 #include "node.h"
 
 #include "serd/node.h"
@@ -11,8 +12,6 @@
 
 #include <assert.h>
 #include <stdbool.h>
-#include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 typedef struct {
@@ -21,42 +20,69 @@ typedef struct {
 } SerdPrefix;
 
 struct SerdEnvImpl {
-  SerdPrefix* prefixes;
-  size_t      n_prefixes;
-  SerdNode*   base_uri_node;
-  SerdURIView base_uri;
+  SerdAllocator* allocator;
+  SerdPrefix*    prefixes;
+  size_t         n_prefixes;
+  SerdNode*      base_uri_node;
+  SerdURIView    base_uri;
 };
 
 SerdEnv*
-serd_env_new(const SerdStringView base_uri)
+serd_env_new(SerdAllocator* const allocator, const SerdStringView base_uri)
 {
-  SerdEnv* env = (SerdEnv*)calloc(1, sizeof(struct SerdEnvImpl));
-  if (env && base_uri.length) {
-    serd_env_set_base_uri(env, base_uri);
+  SerdEnv* env =
+    (SerdEnv*)serd_acalloc(allocator, 1, sizeof(struct SerdEnvImpl));
+
+  if (env) {
+    env->allocator = allocator;
+
+    if (base_uri.length) {
+      if (serd_env_set_base_uri(env, base_uri)) {
+        serd_afree(allocator, env);
+        return NULL;
+      }
+    }
   }
 
   return env;
 }
 
 SerdEnv*
-serd_env_copy(const SerdEnv* const env)
+serd_env_copy(SerdAllocator* const allocator, const SerdEnv* const env)
 {
   if (!env) {
     return NULL;
   }
 
-  SerdEnv* copy = (SerdEnv*)calloc(1, sizeof(struct SerdEnvImpl));
+  SerdEnv* const copy =
+    (SerdEnv*)serd_acalloc(allocator, 1, sizeof(struct SerdEnvImpl));
+
   if (copy) {
+    copy->allocator  = allocator;
     copy->n_prefixes = env->n_prefixes;
-    copy->prefixes = (SerdPrefix*)malloc(copy->n_prefixes * sizeof(SerdPrefix));
+
+    if (!(copy->prefixes = (SerdPrefix*)serd_acalloc(
+            allocator, copy->n_prefixes, sizeof(SerdPrefix)))) {
+      serd_afree(allocator, copy);
+      return NULL;
+    }
+
     for (size_t i = 0; i < copy->n_prefixes; ++i) {
-      copy->prefixes[i].name = serd_node_copy(env->prefixes[i].name);
-      copy->prefixes[i].uri  = serd_node_copy(env->prefixes[i].uri);
+      if (!(copy->prefixes[i].name =
+              serd_node_copy(allocator, env->prefixes[i].name)) ||
+          !(copy->prefixes[i].uri =
+              serd_node_copy(allocator, env->prefixes[i].uri))) {
+        serd_env_free(copy);
+        return NULL;
+      }
     }
 
     const SerdNode* const base = serd_env_base_uri(env);
     if (base) {
-      serd_env_set_base_uri(copy, serd_node_string_view(base));
+      if (serd_env_set_base_uri(copy, serd_node_string_view(base))) {
+        serd_env_free(copy);
+        return NULL;
+      }
     }
   }
 
@@ -71,12 +97,12 @@ serd_env_free(SerdEnv* const env)
   }
 
   for (size_t i = 0; i < env->n_prefixes; ++i) {
-    serd_node_free(env->prefixes[i].name);
-    serd_node_free(env->prefixes[i].uri);
+    serd_node_free(env->allocator, env->prefixes[i].name);
+    serd_node_free(env->allocator, env->prefixes[i].uri);
   }
-  free(env->prefixes);
-  serd_node_free(env->base_uri_node);
-  free(env);
+  serd_afree(env->allocator, env->prefixes);
+  serd_node_free(env->allocator, env->base_uri_node);
+  serd_afree(env->allocator, env);
 }
 
 bool
@@ -119,7 +145,7 @@ serd_env_set_base_uri(SerdEnv* const env, const SerdStringView uri)
   assert(env);
 
   if (!uri.length) {
-    serd_node_free(env->base_uri_node);
+    serd_node_free(env->allocator, env->base_uri_node);
     env->base_uri_node = NULL;
     env->base_uri      = SERD_URI_NULL;
     return SERD_SUCCESS;
@@ -132,10 +158,14 @@ serd_env_set_base_uri(SerdEnv* const env, const SerdStringView uri)
     serd_resolve_uri(serd_parse_uri(uri.data), env->base_uri);
 
   // Replace the current base URI
-  env->base_uri_node = serd_new_parsed_uri(new_base_uri);
-  env->base_uri      = serd_node_uri_view(env->base_uri_node);
+  if ((env->base_uri_node =
+         serd_new_parsed_uri(env->allocator, new_base_uri))) {
+    env->base_uri = serd_node_uri_view(env->base_uri_node);
+  } else {
+    return SERD_BAD_ALLOC;
+  }
 
-  serd_node_free(old_base_uri);
+  serd_node_free(env->allocator, old_base_uri);
   return SERD_SUCCESS;
 }
 
@@ -170,7 +200,7 @@ serd_env_find(const SerdEnv* const env,
   return NULL;
 }
 
-static void
+static SerdStatus
 serd_env_add(SerdEnv* const       env,
              const SerdStringView name,
              const SerdStringView uri)
@@ -178,18 +208,34 @@ serd_env_add(SerdEnv* const       env,
   SerdPrefix* const prefix = serd_env_find(env, name.data, name.length);
   if (prefix) {
     if (!!strcmp(serd_node_string(prefix->uri), uri.data)) {
-      serd_node_free(prefix->uri);
-      prefix->uri = serd_new_uri(uri);
+      serd_node_free(env->allocator, prefix->uri);
+      prefix->uri = serd_new_uri(env->allocator, uri);
     }
   } else {
-    SerdPrefix* const new_prefixes = (SerdPrefix*)realloc(
-      env->prefixes, (++env->n_prefixes) * sizeof(SerdPrefix));
-    if (new_prefixes) {
-      env->prefixes                           = new_prefixes;
-      env->prefixes[env->n_prefixes - 1].name = serd_new_string(name);
-      env->prefixes[env->n_prefixes - 1].uri  = serd_new_uri(uri);
+    SerdPrefix* const new_prefixes =
+      (SerdPrefix*)serd_arealloc(env->allocator,
+                                 env->prefixes,
+                                 (env->n_prefixes + 1) * sizeof(SerdPrefix));
+    if (!new_prefixes) {
+      return SERD_BAD_ALLOC;
     }
+
+    env->prefixes = new_prefixes;
+
+    SerdNode* const name_node = serd_new_string(env->allocator, name);
+    SerdNode* const uri_node  = serd_new_uri(env->allocator, uri);
+    if (!name_node || !uri_node) {
+      serd_node_free(env->allocator, uri_node);
+      serd_node_free(env->allocator, name_node);
+      return SERD_BAD_ALLOC;
+    }
+
+    new_prefixes[env->n_prefixes].name = name_node;
+    new_prefixes[env->n_prefixes].uri  = uri_node;
+    ++env->n_prefixes;
   }
+
+  return SERD_SUCCESS;
 }
 
 SerdStatus
@@ -201,8 +247,7 @@ serd_env_set_prefix(SerdEnv* const       env,
 
   if (serd_uri_string_has_scheme(uri.data)) {
     // Set prefix to absolute URI
-    serd_env_add(env, name, uri);
-    return SERD_SUCCESS;
+    return serd_env_add(env, name, uri);
   }
 
   if (!env->base_uri_node) {
@@ -215,13 +260,17 @@ serd_env_set_prefix(SerdEnv* const       env,
   assert(abs_uri_view.scheme.length);
 
   // Create a new node for the absolute URI
-  SerdNode* const abs_uri = serd_new_parsed_uri(abs_uri_view);
+  SerdNode* const abs_uri = serd_new_parsed_uri(env->allocator, abs_uri_view);
+  if (!abs_uri) {
+    return SERD_BAD_ALLOC;
+  }
+
   assert(serd_uri_string_has_scheme(serd_node_string(abs_uri)));
 
   // Set prefix to resolved (absolute) URI
-  serd_env_add(env, name, serd_node_string_view(abs_uri));
-  serd_node_free(abs_uri);
-  return SERD_SUCCESS;
+  const SerdStatus st = serd_env_add(env, name, serd_node_string_view(abs_uri));
+  serd_node_free(env->allocator, abs_uri);
+  return st;
 }
 
 SerdStatus
@@ -290,7 +339,7 @@ serd_env_expand_curie(const SerdEnv* const env, const SerdStringView curie)
   }
 
   const size_t    len = prefix.length + suffix.length;
-  SerdNode* const ret = serd_node_malloc(len, 0U, SERD_URI);
+  SerdNode* const ret = serd_node_malloc(env->allocator, len, 0U, SERD_URI);
   if (ret) {
     char* const string = serd_node_buffer(ret);
     memcpy(string, prefix.data, prefix.length);
@@ -310,7 +359,8 @@ serd_env_expand_node(const SerdEnv* const env, const SerdNode* const node)
   const SerdURIView uri     = serd_node_uri_view(node);
   const SerdURIView abs_uri = serd_resolve_uri(uri, env->base_uri);
 
-  return abs_uri.scheme.length ? serd_new_parsed_uri(abs_uri) : NULL;
+  return abs_uri.scheme.length ? serd_new_parsed_uri(env->allocator, abs_uri)
+                               : NULL;
 }
 
 SerdStatus
diff --git a/src/memory.c b/src/memory.c
new file mode 100644
index 00000000..74694c14
--- /dev/null
+++ b/src/memory.c
@@ -0,0 +1,17 @@
+// Copyright 2011-2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "memory.h"
+
+#include "serd/memory.h"
+#include "zix/allocator.h"
+
+SerdAllocator*
+serd_default_allocator(void)
+{
+  /* Note that SerdAllocator is intentionally the same as ZixAllocator.  It
+     only exists to avoid exposing the zix API in the public serd API, which
+     I'm not sure would be appropriate. */
+
+  return (SerdAllocator*)zix_default_allocator();
+}
diff --git a/src/memory.h b/src/memory.h
new file mode 100644
index 00000000..80c60724
--- /dev/null
+++ b/src/memory.h
@@ -0,0 +1,136 @@
+// Copyright 2011-2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef SERD_SRC_MEMORY_H
+#define SERD_SRC_MEMORY_H
+
+#include "serd/memory.h"
+#include "serd/world.h"
+
+#include <stddef.h>
+#include <string.h>
+
+// Allocator convenience wrappers that fall back to the default for NULL
+
+/// Convenience wrapper that defers to malloc() if allocator is null
+static inline void*
+serd_amalloc(SerdAllocator* const allocator, const size_t size)
+{
+  SerdAllocator* const actual =
+    allocator ? allocator : serd_default_allocator();
+
+  return actual->malloc(actual, size);
+}
+
+/// Convenience wrapper that defers to calloc() if allocator is null
+static inline void*
+serd_acalloc(SerdAllocator* const allocator,
+             const size_t         nmemb,
+             const size_t         size)
+{
+  SerdAllocator* const actual =
+    allocator ? allocator : serd_default_allocator();
+
+  return actual->calloc(actual, nmemb, size);
+}
+
+/// Convenience wrapper that defers to realloc() if allocator is null
+static inline void*
+serd_arealloc(SerdAllocator* const allocator,
+              void* const          ptr,
+              const size_t         size)
+{
+  SerdAllocator* const actual =
+    allocator ? allocator : serd_default_allocator();
+
+  return actual->realloc(actual, ptr, size);
+}
+
+/// Convenience wrapper that defers to free() if allocator is null
+static inline void
+serd_afree(SerdAllocator* const allocator, void* const ptr)
+{
+  SerdAllocator* const actual =
+    allocator ? allocator : serd_default_allocator();
+
+  actual->free(actual, ptr);
+}
+
+/// Convenience wrapper that defers to the system allocator if allocator is null
+static inline void*
+serd_aaligned_alloc(SerdAllocator* const allocator,
+                    const size_t         alignment,
+                    const size_t         size)
+{
+  SerdAllocator* const actual =
+    allocator ? allocator : serd_default_allocator();
+
+  return actual->aligned_alloc(actual, alignment, size);
+}
+
+/// Convenience wrapper for serd_aaligned_alloc that zeros memory
+static inline void*
+serd_aaligned_calloc(SerdAllocator* const allocator,
+                     const size_t         alignment,
+                     const size_t         size)
+{
+  void* const ptr = serd_aaligned_alloc(allocator, alignment, size);
+  if (ptr) {
+    memset(ptr, 0, size);
+  }
+  return ptr;
+}
+
+/// Convenience wrapper that defers to the system allocator if allocator is null
+static inline void
+serd_aaligned_free(SerdAllocator* const allocator, void* const ptr)
+{
+  SerdAllocator* const actual =
+    allocator ? allocator : serd_default_allocator();
+
+  actual->aligned_free(actual, ptr);
+}
+
+// World convenience wrappers
+
+static inline void*
+serd_wmalloc(const SerdWorld* const world, const size_t size)
+{
+  return serd_amalloc(serd_world_allocator(world), size);
+}
+
+static inline void*
+serd_wcalloc(const SerdWorld* const world,
+             const size_t           nmemb,
+             const size_t           size)
+{
+  return serd_acalloc(serd_world_allocator(world), nmemb, size);
+}
+
+static inline void*
+serd_wrealloc(const SerdWorld* const world, void* const ptr, const size_t size)
+{
+  return serd_arealloc(serd_world_allocator(world), ptr, size);
+}
+
+static inline void
+serd_wfree(const SerdWorld* const world, void* const ptr)
+{
+  serd_afree(serd_world_allocator(world), ptr);
+}
+
+static inline void*
+serd_waligned_alloc(const SerdWorld* const world,
+                    const size_t           alignment,
+                    const size_t           size)
+{
+  return serd_aaligned_alloc(serd_world_allocator(world), alignment, size);
+}
+
+static inline void
+serd_waligned_free(const SerdWorld* const world, void* const ptr)
+{
+  serd_aaligned_free(serd_world_allocator(world), ptr);
+}
+
+#endif // SERD_SRC_MEMORY_H
diff --git a/src/node.c b/src/node.c
index a80a38b2..135ccc22 100644
--- a/src/node.c
+++ b/src/node.c
@@ -3,9 +3,9 @@
 
 #include "node.h"
 
+#include "memory.h"
 #include "namespaces.h"
 #include "string_utils.h"
-#include "system.h"
 
 #include "exess/exess.h"
 #include "serd/buffer.h"
@@ -110,35 +110,46 @@ serd_node_total_size(const SerdNode* const node)
 }
 
 SerdNode*
-serd_node_malloc(const size_t        length,
-                 const SerdNodeFlags flags,
-                 const SerdNodeType  type)
+serd_node_malloc(SerdAllocator* const allocator,
+                 const size_t         length,
+                 const SerdNodeFlags  flags,
+                 const SerdNodeType   type)
 {
   const size_t size = sizeof(SerdNode) + serd_node_pad_length(length);
-  SerdNode*    node = (SerdNode*)serd_calloc_aligned(serd_node_align, size);
 
-  node->length = 0;
-  node->flags  = flags;
-  node->type   = type;
+  SerdNode* const node =
+    (SerdNode*)serd_aaligned_calloc(allocator, serd_node_align, size);
+
+  if (node) {
+    node->length = 0;
+    node->flags  = flags;
+    node->type   = type;
+  }
 
   assert((uintptr_t)node % serd_node_align == 0U);
   return node;
 }
 
-void
-serd_node_set(SerdNode** const dst, const SerdNode* const src)
+SerdStatus
+serd_node_set(SerdAllocator* const  allocator,
+              SerdNode** const      dst,
+              const SerdNode* const src)
 {
   assert(dst);
   assert(src);
 
   const size_t size = serd_node_total_size(src);
   if (!*dst || serd_node_total_size(*dst) < size) {
-    serd_free_aligned(*dst);
-    *dst = (SerdNode*)serd_calloc_aligned(serd_node_align, size);
+    serd_aaligned_free(allocator, *dst);
+    if (!(*dst = (SerdNode*)serd_aaligned_calloc(
+            allocator, serd_node_align, size))) {
+      return SERD_BAD_ALLOC;
+    }
   }
 
   assert(*dst);
   memcpy(*dst, src, size);
+  return SERD_SUCCESS;
 }
 
 /**
@@ -169,11 +180,13 @@ result(const SerdStatus status, const size_t count)
 }
 
 SerdNode*
-serd_new_token(const SerdNodeType type, const SerdStringView str)
+serd_new_token(SerdAllocator* const allocator,
+               const SerdNodeType   type,
+               const SerdStringView str)
 {
   SerdNodeFlags flags  = 0U;
   const size_t  length = str.data ? str.length : 0U;
-  SerdNode*     node   = serd_node_malloc(length, flags, type);
+  SerdNode*     node   = serd_node_malloc(allocator, length, flags, type);
 
   if (node) {
     if (str.data) {
@@ -189,10 +202,10 @@ serd_new_token(const SerdNodeType type, const SerdStringView str)
 }
 
 SerdNode*
-serd_new_string(const SerdStringView str)
+serd_new_string(SerdAllocator* const allocator, const SerdStringView str)
 {
   SerdNodeFlags flags = 0U;
-  SerdNode*     node  = serd_node_malloc(str.length, flags, SERD_LITERAL);
+  SerdNode* node = serd_node_malloc(allocator, str.length, flags, SERD_LITERAL);
 
   if (node) {
     if (str.data && str.length) {
@@ -236,12 +249,14 @@ is_langtag(const SerdStringView string)
 }
 
 SerdNode*
-serd_new_literal(const SerdStringView string,
+serd_new_literal(SerdAllocator* const allocator,
+                 const SerdStringView string,
                  const SerdNodeFlags  flags,
                  const SerdStringView meta)
 {
   if (!(flags & (SERD_HAS_DATATYPE | SERD_HAS_LANGUAGE))) {
-    SerdNode* node = serd_node_malloc(string.length, flags, SERD_LITERAL);
+    SerdNode* node =
+      serd_node_malloc(allocator, string.length, flags, SERD_LITERAL);
 
     memcpy(serd_node_buffer(node), string.data, string.length);
     node->length = string.length;
@@ -268,7 +283,8 @@ serd_new_literal(const SerdStringView string,
   const size_t meta_len  = serd_node_pad_length(meta.length);
   const size_t meta_size = sizeof(SerdNode) + meta_len;
 
-  SerdNode* node = serd_node_malloc(len + meta_size, flags, SERD_LITERAL);
+  SerdNode* node =
+    serd_node_malloc(allocator, len + meta_size, flags, SERD_LITERAL);
   memcpy(serd_node_buffer(node), string.data, string.length);
   node->length = string.length;
 
@@ -283,9 +299,9 @@ serd_new_literal(const SerdStringView string,
 }
 
 SerdNode*
-serd_new_blank(const SerdStringView str)
+serd_new_blank(SerdAllocator* const allocator, const SerdStringView str)
 {
-  return serd_new_token(SERD_BLANK, str);
+  return serd_new_token(allocator, SERD_BLANK, str);
 }
 
 ExessResult
@@ -396,16 +412,20 @@ serd_get_base64(const SerdNode* const node,
 }
 
 SerdNode*
-serd_node_copy(const SerdNode* node)
+serd_node_copy(SerdAllocator* const allocator, const SerdNode* node)
 {
   if (!node) {
     return NULL;
   }
 
   const size_t size = serd_node_total_size(node);
-  SerdNode*    copy = (SerdNode*)serd_calloc_aligned(serd_node_align, size);
+  SerdNode*    copy =
+    (SerdNode*)serd_aaligned_alloc(allocator, serd_node_align, size);
+
+  if (copy) {
+    memcpy(copy, node, size);
+  }
 
-  memcpy(copy, node, size);
   return copy;
 }
 
@@ -466,39 +486,45 @@ serd_node_compare(const SerdNode* const a, const SerdNode* const b)
 }
 
 SerdNode*
-serd_new_uri(const SerdStringView string)
+serd_new_uri(SerdAllocator* const allocator, const SerdStringView string)
 {
-  return serd_new_token(SERD_URI, string);
+  return serd_new_token(allocator, SERD_URI, string);
 }
 
 SerdNode*
-serd_new_parsed_uri(const SerdURIView uri)
+serd_new_parsed_uri(SerdAllocator* const allocator, const SerdURIView uri)
 {
-  const size_t    len        = serd_uri_string_length(uri);
-  SerdNode* const node       = serd_node_malloc(len, 0, SERD_URI);
-  char*           ptr        = serd_node_buffer(node);
-  const size_t    actual_len = serd_write_uri(uri, string_sink, &ptr);
+  const size_t    len  = serd_uri_string_length(uri);
+  SerdNode* const node = serd_node_malloc(allocator, len, 0, SERD_URI);
 
-  assert(actual_len == len);
+  if (node) {
+    char*        ptr        = serd_node_buffer(node);
+    const size_t actual_len = serd_write_uri(uri, string_sink, &ptr);
+
+    assert(actual_len == len);
 
-  serd_node_buffer(node)[actual_len] = '\0';
-  node->length                       = actual_len;
+    serd_node_buffer(node)[actual_len] = '\0';
+    node->length                       = actual_len;
+  }
 
   serd_node_check_padding(node);
   return node;
 }
 
 SerdNode*
-serd_new_file_uri(const SerdStringView path, const SerdStringView hostname)
+serd_new_file_uri(SerdAllocator* const allocator,
+                  const SerdStringView path,
+                  const SerdStringView hostname)
 {
-  SerdBuffer buffer = {NULL, 0U};
+  SerdBuffer buffer = {NULL, NULL, 0U};
 
   serd_write_file_uri(path, hostname, serd_buffer_write, &buffer);
   serd_buffer_close(&buffer);
 
   const size_t      length = buffer.len;
   const char* const string = (char*)buffer.buf;
-  SerdNode* const   node   = serd_new_string(serd_substring(string, length));
+  SerdNode* const   node =
+    serd_new_string(allocator, serd_substring(string, length));
 
   free(buffer.buf);
   serd_node_check_padding(node);
@@ -510,7 +536,8 @@ typedef size_t (*SerdWriteLiteralFunc)(const void* user_data,
                                        char*       buf);
 
 static SerdNode*
-serd_new_custom_literal(const void* const          user_data,
+serd_new_custom_literal(SerdAllocator* const       allocator,
+                        const void* const          user_data,
                         const size_t               len,
                         const SerdWriteLiteralFunc write,
                         const SerdNode* const      datatype)
@@ -523,7 +550,7 @@ serd_new_custom_literal(const void* const          user_data,
   const size_t total_size    = serd_node_pad_length(len) + datatype_size;
 
   SerdNode* const node = serd_node_malloc(
-    total_size, datatype ? SERD_HAS_DATATYPE : 0U, SERD_LITERAL);
+    allocator, total_size, datatype ? SERD_HAS_DATATYPE : 0U, SERD_LITERAL);
 
   node->length = write(user_data, len + 1, serd_node_buffer(node));
 
@@ -531,46 +558,50 @@ serd_new_custom_literal(const void* const          user_data,
     memcpy(serd_node_meta(node), datatype, datatype_size);
   }
 
-  serd_node_check_padding(node);
   return node;
 }
 
 SerdNode*
-serd_new_double(const double d)
+serd_new_double(SerdAllocator* const allocator, const double d)
 {
   char buf[EXESS_MAX_DOUBLE_LENGTH + 1] = {0};
 
   const ExessResult r = exess_write_double(d, sizeof(buf), buf);
 
   return r.status ? NULL
-                  : serd_new_literal(serd_substring(buf, r.count),
+                  : serd_new_literal(allocator,
+                                     serd_substring(buf, r.count),
                                      SERD_HAS_DATATYPE,
                                      serd_string(EXESS_XSD_URI "double"));
 }
 
 SerdNode*
-serd_new_float(const float f)
+serd_new_float(SerdAllocator* const allocator, const float f)
 {
   char buf[EXESS_MAX_FLOAT_LENGTH + 1] = {0};
 
   const ExessResult r = exess_write_float(f, sizeof(buf), buf);
 
   return r.status ? NULL
-                  : serd_new_literal(serd_substring(buf, r.count),
+                  : serd_new_literal(allocator,
+                                     serd_substring(buf, r.count),
                                      SERD_HAS_DATATYPE,
                                      serd_string(EXESS_XSD_URI "float"));
 }
 
 SerdNode*
-serd_new_boolean(bool b)
+serd_new_boolean(SerdAllocator* const allocator, bool b)
 {
-  return serd_new_literal(b ? serd_string("true") : serd_string("false"),
+  return serd_new_literal(allocator,
+                          b ? serd_string("true") : serd_string("false"),
                           SERD_HAS_DATATYPE,
                           serd_node_string_view(&serd_xsd_boolean.node));
 }
 
 SerdNode*
-serd_new_decimal(const double d, const SerdNode* const datatype)
+serd_new_decimal(SerdAllocator* const  allocator,
+                 const double          d,
+                 const SerdNode* const datatype)
 {
   // Use given datatype, or xsd:decimal as a default if it is null
   const SerdNode* type      = datatype ? datatype : &serd_xsd_decimal.node;
@@ -581,8 +612,11 @@ serd_new_decimal(const double d, const SerdNode* const datatype)
   assert(!r.status);
 
   // Allocate node with enough space for value and datatype URI
-  SerdNode* const node = serd_node_malloc(
-    serd_node_pad_length(r.count) + type_size, SERD_HAS_DATATYPE, SERD_LITERAL);
+  SerdNode* const node =
+    serd_node_malloc(allocator,
+                     serd_node_pad_length(r.count) + type_size,
+                     SERD_HAS_DATATYPE,
+                     SERD_LITERAL);
 
   // Write string directly into node
   r = exess_write_decimal(d, r.count + 1, serd_node_buffer(node));
@@ -595,7 +629,7 @@ serd_new_decimal(const double d, const SerdNode* const datatype)
 }
 
 SerdNode*
-serd_new_integer(const int64_t i)
+serd_new_integer(SerdAllocator* const allocator, const int64_t i)
 {
   // Use given datatype, or xsd:integer as a default if it is null
   const SerdNode* datatype      = &serd_xsd_integer.node;
@@ -607,7 +641,8 @@ serd_new_integer(const int64_t i)
 
   // Allocate node with enough space for value and datatype URI
   SerdNode* const node =
-    serd_node_malloc(serd_node_pad_length(r.count) + datatype_size,
+    serd_node_malloc(allocator,
+                     serd_node_pad_length(r.count) + datatype_size,
                      SERD_HAS_DATATYPE,
                      SERD_LITERAL);
 
@@ -634,13 +669,13 @@ write_base64_literal(const void* const user_data,
 }
 
 SerdNode*
-serd_new_base64(const void* buf, size_t size)
+serd_new_base64(SerdAllocator* const allocator, const void* buf, size_t size)
 {
   const size_t    len  = exess_write_base64(size, buf, 0, NULL).count;
   SerdConstBuffer blob = {buf, size};
 
   return serd_new_custom_literal(
-    &blob, len, write_base64_literal, &serd_xsd_base64Binary.node);
+    allocator, &blob, len, write_base64_literal, &serd_xsd_base64Binary.node);
 }
 
 SerdNodeType
@@ -721,7 +756,7 @@ serd_node_flags(const SerdNode* const node)
 }
 
 void
-serd_node_free(SerdNode* const node)
+serd_node_free(SerdAllocator* const allocator, SerdNode* const node)
 {
-  serd_free_aligned(node);
+  serd_aaligned_free(allocator, node);
 }
diff --git a/src/node.h b/src/node.h
index a31085be..43368367 100644
--- a/src/node.h
+++ b/src/node.h
@@ -5,7 +5,9 @@
 #define SERD_SRC_NODE_H
 
 #include "exess/exess.h"
+#include "serd/memory.h"
 #include "serd/node.h"
+#include "serd/status.h"
 #include "zix/attributes.h"
 
 #include <stdbool.h>
@@ -46,10 +48,14 @@ serd_node_pattern_match(const SerdNode* ZIX_NULLABLE a,
 }
 
 SerdNode* ZIX_ALLOCATED
-serd_node_malloc(size_t length, SerdNodeFlags flags, SerdNodeType type);
+serd_node_malloc(SerdAllocator* ZIX_NULLABLE allocator,
+                 size_t                      length,
+                 SerdNodeFlags               flags,
+                 SerdNodeType                type);
 
-void
-serd_node_set(SerdNode* ZIX_NONNULL* ZIX_NONNULL dst,
+SerdStatus
+serd_node_set(SerdAllocator* ZIX_NULLABLE        allocator,
+              SerdNode* ZIX_NONNULL* ZIX_NONNULL dst,
               const SerdNode* ZIX_NONNULL        src);
 
 ZIX_PURE_FUNC size_t
diff --git a/src/reader.c b/src/reader.c
index 8b74836f..bbb1325b 100644
--- a/src/reader.c
+++ b/src/reader.c
@@ -4,6 +4,7 @@
 #include "reader.h"
 
 #include "byte_source.h"
+#include "memory.h"
 #include "namespaces.h"
 #include "node.h"
 #include "read_nquads.h"
@@ -13,7 +14,6 @@
 #include "stack.h"
 #include "statement.h"
 #include "string_utils.h"
-#include "system.h"
 #include "world.h"
 
 #include "serd/input_stream.h"
@@ -22,7 +22,6 @@
 #include <assert.h>
 #include <stdarg.h>
 #include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 static SerdStatus
@@ -241,17 +240,25 @@ serd_reader_new(SerdWorld* const      world,
     return NULL;
   }
 
-  SerdReader* me = (SerdReader*)calloc(1, sizeof(SerdReader));
+  SerdReader* me = (SerdReader*)serd_wcalloc(world, 1, sizeof(SerdReader));
+  if (!me) {
+    return NULL;
+  }
 
   me->world   = world;
   me->sink    = sink;
   me->env     = env;
-  me->stack   = serd_stack_new(stack_size, serd_node_align);
+  me->stack   = serd_stack_new(world->allocator, stack_size, serd_node_align);
   me->syntax  = syntax;
   me->flags   = flags;
   me->next_id = 1;
   me->strict  = !(flags & SERD_READ_LAX);
 
+  if (!me->stack.buf) {
+    serd_wfree(world, me);
+    return NULL;
+  }
+
   // Reserve a bit of space at the end of the stack to zero pad nodes
   me->stack.buf_size -= serd_node_align;
 
@@ -278,9 +285,9 @@ serd_reader_free(SerdReader* const reader)
     serd_reader_finish(reader);
   }
 
-  serd_free_aligned(reader->stack.buf);
-  free(reader->bprefix);
-  free(reader);
+  serd_aaligned_free(reader->world->allocator, reader->stack.buf);
+  serd_wfree(reader->world, reader->bprefix);
+  serd_wfree(reader->world, reader);
 }
 
 void
@@ -288,14 +295,15 @@ serd_reader_add_blank_prefix(SerdReader* const reader, const char* const prefix)
 {
   assert(reader);
 
-  free(reader->bprefix);
+  serd_wfree(reader->world, reader->bprefix);
   reader->bprefix_len = 0;
   reader->bprefix     = NULL;
 
   const size_t prefix_len = prefix ? strlen(prefix) : 0;
   if (prefix_len) {
     reader->bprefix_len = prefix_len;
-    reader->bprefix     = (char*)malloc(reader->bprefix_len + 1);
+    reader->bprefix =
+      (char*)serd_wmalloc(reader->world, reader->bprefix_len + 1);
     memcpy(reader->bprefix, prefix, reader->bprefix_len + 1);
   }
 }
@@ -326,13 +334,18 @@ serd_reader_start(SerdReader* const      reader,
   assert(reader);
   assert(input);
 
+  if (!block_size || !input->stream) {
+    return SERD_BAD_ARG;
+  }
+
   if (reader->source) {
     return SERD_BAD_CALL;
   }
 
-  reader->source = serd_byte_source_new_input(input, input_name, block_size);
+  reader->source = serd_byte_source_new_input(
+    reader->world->allocator, input, input_name, block_size);
 
-  return reader->source ? SERD_SUCCESS : SERD_BAD_ARG;
+  return reader->source ? SERD_SUCCESS : SERD_BAD_ALLOC;
 }
 
 static SerdStatus
@@ -393,7 +406,7 @@ serd_reader_finish(SerdReader* const reader)
 {
   assert(reader);
 
-  serd_byte_source_free(reader->source);
+  serd_byte_source_free(reader->world->allocator, reader->source);
   reader->source = NULL;
   return SERD_SUCCESS;
 }
diff --git a/src/serd_config.h b/src/serd_config.h
index 0bd9b5ac..0146c181 100644
--- a/src/serd_config.h
+++ b/src/serd_config.h
@@ -74,13 +74,6 @@
 #    endif
 #  endif
 
-// POSIX.1-2001: posix_memalign()
-#  ifndef HAVE_POSIX_MEMALIGN
-#    if SERD_POSIX_VERSION >= 200112L
-#      define HAVE_POSIX_MEMALIGN 1
-#    endif
-#  endif
-
 // POSIX.1-2001: strerror_r()
 #  ifndef HAVE_STRERROR_R
 #    if defined(_POSIX_VERSION) && _POSIX_VERSION >= 200112L
@@ -116,12 +109,6 @@
 #  define USE_POSIX_FADVISE 0
 #endif
 
-#if defined(HAVE_POSIX_MEMALIGN) && HAVE_POSIX_MEMALIGN
-#  define USE_POSIX_MEMALIGN 1
-#else
-#  define USE_POSIX_MEMALIGN 0
-#endif
-
 #ifdef HAVE_STRERROR_R
 #  define USE_STRERROR_R 1
 #else
diff --git a/src/sink.c b/src/sink.c
index adf85b08..48ada0c5 100644
--- a/src/sink.c
+++ b/src/sink.c
@@ -3,6 +3,7 @@
 
 #include "sink.h"
 
+#include "memory.h"
 #include "statement.h"
 
 #include "serd/node.h"
@@ -14,15 +15,19 @@
 #include <stdlib.h>
 
 SerdSink*
-serd_sink_new(void* const   handle,
-              SerdEventFunc event_func,
-              SerdFreeFunc  free_handle)
+serd_sink_new(SerdAllocator* const allocator,
+              void* const          handle,
+              SerdEventFunc        event_func,
+              SerdFreeFunc         free_handle)
 {
-  SerdSink* sink = (SerdSink*)calloc(1, sizeof(SerdSink));
+  SerdSink* sink = (SerdSink*)serd_acalloc(allocator, 1, sizeof(SerdSink));
 
-  sink->handle      = handle;
-  sink->on_event    = event_func;
-  sink->free_handle = free_handle;
+  if (sink) {
+    sink->allocator   = allocator;
+    sink->handle      = handle;
+    sink->on_event    = event_func;
+    sink->free_handle = free_handle;
+  }
 
   return sink;
 }
@@ -35,7 +40,7 @@ serd_sink_free(SerdSink* sink)
       sink->free_handle(sink->handle);
     }
 
-    free(sink);
+    serd_afree(sink->allocator, sink);
   }
 }
 
diff --git a/src/sink.h b/src/sink.h
index 097e0d6d..baed246e 100644
--- a/src/sink.h
+++ b/src/sink.h
@@ -5,15 +5,17 @@
 #define SERD_SRC_SINK_H
 
 #include "serd/event.h"
+#include "serd/memory.h"
 #include "serd/sink.h"
 
 /**
    An interface that receives a stream of RDF data.
 */
 struct SerdSinkImpl {
-  void*         handle;
-  SerdFreeFunc  free_handle;
-  SerdEventFunc on_event;
+  SerdAllocator* allocator;
+  void*          handle;
+  SerdFreeFunc   free_handle;
+  SerdEventFunc  on_event;
 };
 
 #endif // SERD_SRC_SINK_H
diff --git a/src/stack.h b/src/stack.h
index 20bd561b..40e8065d 100644
--- a/src/stack.h
+++ b/src/stack.h
@@ -4,7 +4,7 @@
 #ifndef SERD_SRC_STACK_H
 #define SERD_SRC_STACK_H
 
-#include "system.h"
+#include "memory.h"
 
 #include <assert.h>
 #include <stdbool.h>
@@ -19,21 +19,21 @@ typedef struct {
 } SerdStack;
 
 static inline SerdStack
-serd_stack_new(size_t size, size_t align)
+serd_stack_new(SerdAllocator* const allocator, size_t size, size_t align)
 {
   const size_t aligned_size = (size + (align - 1)) / align * align;
 
   SerdStack stack;
-  stack.buf      = (char*)serd_calloc_aligned(align, aligned_size);
+  stack.buf      = (char*)serd_aaligned_calloc(allocator, align, aligned_size);
   stack.buf_size = size;
   stack.size     = align; // 0 is reserved for null
   return stack;
 }
 
 static inline void
-serd_stack_free(SerdStack* stack)
+serd_stack_free(SerdAllocator* const allocator, SerdStack* stack)
 {
-  serd_free_aligned(stack->buf);
+  serd_aaligned_free(allocator, stack->buf);
   stack->buf      = NULL;
   stack->buf_size = 0;
   stack->size     = 0;
diff --git a/src/statement.c b/src/statement.c
index 418e999e..5ea14910 100644
--- a/src/statement.c
+++ b/src/statement.c
@@ -4,8 +4,10 @@
 #include "statement.h"
 
 #include "caret.h"
+#include "memory.h"
 #include "node.h"
 
+#include "serd/memory.h"
 #include "serd/statement.h"
 
 #include <assert.h>
@@ -16,7 +18,7 @@
 static bool
 is_resource(const SerdNode* const node)
 {
-  const SerdNodeType type = node ? serd_node_type(node) : (SerdNodeType)0;
+  const SerdNodeType type = serd_node_type(node);
   return type == SERD_URI || type == SERD_BLANK || type == SERD_VARIABLE;
 }
 
@@ -26,13 +28,16 @@ serd_statement_is_valid(const SerdNode* const subject,
                         const SerdNode* const object,
                         const SerdNode* const graph)
 {
-  return is_resource(subject) && is_resource(predicate) && object &&
+  (void)object;
+
+  return is_resource(subject) && is_resource(predicate) &&
          serd_node_type(predicate) != SERD_BLANK &&
          (!graph || is_resource(graph));
 }
 
 SerdStatement*
-serd_statement_new(const SerdNode* const  s,
+serd_statement_new(SerdAllocator* const   allocator,
+                   const SerdNode* const  s,
                    const SerdNode* const  p,
                    const SerdNode* const  o,
                    const SerdNode* const  g,
@@ -46,39 +51,62 @@ serd_statement_new(const SerdNode* const  s,
     return NULL;
   }
 
-  SerdStatement* statement = (SerdStatement*)malloc(sizeof(SerdStatement));
+  SerdStatement* statement =
+    (SerdStatement*)serd_amalloc(allocator, sizeof(SerdStatement));
+
   if (statement) {
     statement->nodes[0] = s;
     statement->nodes[1] = p;
     statement->nodes[2] = o;
     statement->nodes[3] = g;
-    statement->caret    = serd_caret_copy(caret);
+    statement->caret    = NULL;
+
+    if (caret) {
+      if (!(statement->caret = serd_caret_copy(allocator, caret))) {
+        serd_afree(allocator, statement);
+        return NULL;
+      }
+    }
   }
+
   return statement;
 }
 
 SerdStatement*
-serd_statement_copy(const SerdStatement* const statement)
+serd_statement_copy(SerdAllocator* const       allocator,
+                    const SerdStatement* const statement)
 {
   if (!statement) {
     return NULL;
   }
 
-  SerdStatement* copy = (SerdStatement*)malloc(sizeof(SerdStatement));
-  memcpy(copy, statement, sizeof(SerdStatement));
-  if (statement->caret) {
-    copy->caret = (SerdCaret*)malloc(sizeof(SerdCaret));
-    memcpy(copy->caret, statement->caret, sizeof(SerdCaret));
+  SerdStatement* copy =
+    (SerdStatement*)serd_amalloc(allocator, sizeof(SerdStatement));
+
+  if (copy) {
+    memcpy(copy, statement, sizeof(SerdStatement));
+
+    if (statement->caret) {
+      if (!(copy->caret =
+              (SerdCaret*)serd_amalloc(allocator, sizeof(SerdCaret)))) {
+        serd_afree(allocator, copy);
+        return NULL;
+      }
+
+      memcpy(copy->caret, statement->caret, sizeof(SerdCaret));
+    }
   }
+
   return copy;
 }
 
 void
-serd_statement_free(SerdStatement* const statement)
+serd_statement_free(SerdAllocator* const allocator,
+                    SerdStatement* const statement)
 {
   if (statement) {
-    free(statement->caret);
-    free(statement);
+    serd_afree(allocator, statement->caret);
+    serd_afree(allocator, statement);
   }
 }
 
diff --git a/src/string.c b/src/string.c
index ed3149d0..46f8ff9a 100644
--- a/src/string.c
+++ b/src/string.c
@@ -1,15 +1,15 @@
 // Copyright 2011-2020 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
+#include "memory.h"
+
 #include "serd/memory.h"
 #include "serd/status.h"
 
-#include <stdlib.h>
-
 void
-serd_free(void* const ptr)
+serd_free(SerdAllocator* const allocator, void* const ptr)
 {
-  free(ptr);
+  serd_afree(allocator, ptr);
 }
 
 const char*
diff --git a/src/system.c b/src/system.c
index 16a292f5..4c29f7a1 100644
--- a/src/system.c
+++ b/src/system.c
@@ -9,8 +9,6 @@
 #  include <malloc.h>
 #endif
 
-#include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 int
@@ -26,49 +24,3 @@ serd_system_strerror(const int errnum, char* const buf, const size_t buflen)
   return 0;
 #endif
 }
-
-void*
-serd_malloc_aligned(const size_t alignment, const size_t size)
-{
-#if defined(_WIN32)
-  return _aligned_malloc(size, alignment);
-#elif USE_POSIX_MEMALIGN
-  void*     ptr = NULL;
-  const int ret = posix_memalign(&ptr, alignment, size);
-  return ret ? NULL : ptr;
-#else
-  (void)alignment;
-  return malloc(size);
-#endif
-}
-
-void*
-serd_calloc_aligned(const size_t alignment, const size_t size)
-{
-#if defined(_WIN32) || defined(USE_POSIX_MEMALIGN)
-  void* const ptr = serd_malloc_aligned(alignment, size);
-  if (ptr) {
-    memset(ptr, 0, size);
-  }
-  return ptr;
-#else
-  (void)alignment;
-  return calloc(1, size);
-#endif
-}
-
-void*
-serd_allocate_buffer(const size_t size)
-{
-  return serd_malloc_aligned(SERD_PAGE_SIZE, size);
-}
-
-void
-serd_free_aligned(void* const ptr)
-{
-#ifdef _WIN32
-  _aligned_free(ptr);
-#else
-  free(ptr);
-#endif
-}
diff --git a/src/system.h b/src/system.h
index a0ec05dc..b606744b 100644
--- a/src/system.h
+++ b/src/system.h
@@ -4,9 +4,7 @@
 #ifndef SERD_SRC_SYSTEM_H
 #define SERD_SRC_SYSTEM_H
 
-#include "zix/attributes.h"
-
-#include <stdio.h>
+#include <stddef.h>
 
 #define SERD_PAGE_SIZE 4096
 
@@ -14,20 +12,4 @@
 int
 serd_system_strerror(int errnum, char* buf, size_t buflen);
 
-/// Allocate a buffer aligned to `alignment` bytes
-ZIX_MALLOC_FUNC void*
-serd_malloc_aligned(size_t alignment, size_t size);
-
-/// Allocate a zeroed buffer aligned to `alignment` bytes
-ZIX_MALLOC_FUNC void*
-serd_calloc_aligned(size_t alignment, size_t size);
-
-/// Allocate an aligned buffer for I/O
-ZIX_MALLOC_FUNC void*
-serd_allocate_buffer(size_t size);
-
-/// Free a buffer allocated with an aligned allocation function
-void
-serd_free_aligned(void* ptr);
-
 #endif // SERD_SRC_SYSTEM_H
diff --git a/src/uri.c b/src/uri.c
index 6fc1f17c..234bf834 100644
--- a/src/uri.c
+++ b/src/uri.c
@@ -1,10 +1,12 @@
 // Copyright 2011-2023 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
+#include "memory.h"
 #include "string_utils.h"
 #include "uri_utils.h"
 
 #include "serd/buffer.h"
+#include "serd/memory.h"
 #include "serd/status.h"
 #include "serd/stream.h"
 #include "serd/string_view.h"
@@ -14,7 +16,6 @@
 #include <stdbool.h>
 #include <stdint.h>
 #include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 static SerdStatus
@@ -25,7 +26,9 @@ write_file_uri_char(const char c, void* const stream)
 }
 
 static char*
-parse_hostname(const char* const authority, char** const hostname)
+parse_hostname(SerdAllocator* const allocator,
+               const char* const    authority,
+               char** const         hostname)
 {
   char* const path = strchr(authority, '/');
   if (!path) {
@@ -34,7 +37,7 @@ parse_hostname(const char* const authority, char** const hostname)
 
   if (hostname) {
     const size_t len = (size_t)(path - authority);
-    if (!(*hostname = (char*)calloc(len + 1, 1))) {
+    if (!(*hostname = (char*)serd_acalloc(allocator, len + 1, 1))) {
       return NULL;
     }
 
@@ -45,7 +48,9 @@ parse_hostname(const char* const authority, char** const hostname)
 }
 
 char*
-serd_parse_file_uri(const char* const uri, char** const hostname)
+serd_parse_file_uri(SerdAllocator* const allocator,
+                    const char* const    uri,
+                    char** const         hostname)
 {
   assert(uri);
 
@@ -60,7 +65,7 @@ serd_parse_file_uri(const char* const uri, char** const hostname)
     const char* auth = uri + 7;
     if (*auth == '/') { // No hostname
       path = auth;
-    } else if (!(path = parse_hostname(auth, hostname))) {
+    } else if (!(path = parse_hostname(allocator, auth, hostname))) {
       return NULL;
     }
   }
@@ -69,7 +74,7 @@ serd_parse_file_uri(const char* const uri, char** const hostname)
     ++path;
   }
 
-  SerdBuffer buffer = {NULL, 0};
+  SerdBuffer buffer = {allocator, NULL, 0};
   for (const char* s = path; !st && *s; ++s) {
     if (*s != '%') {
       st = write_file_uri_char(*s, &buffer);
@@ -90,7 +95,7 @@ serd_parse_file_uri(const char* const uri, char** const hostname)
   }
 
   if (st || serd_buffer_close(&buffer)) {
-    free(buffer.buf);
+    serd_free(allocator, buffer.buf);
     return NULL;
   }
 
diff --git a/src/world.c b/src/world.c
index f5ab2f19..2c563f15 100644
--- a/src/world.c
+++ b/src/world.c
@@ -4,6 +4,7 @@
 #include "world.h"
 
 #include "log.h"
+#include "memory.h"
 #include "node.h"
 
 #include "serd/node.h"
@@ -13,23 +14,26 @@
 
 #include <assert.h>
 #include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 SerdWorld*
-serd_world_new(void)
+serd_world_new(SerdAllocator* const allocator)
 {
-  SerdWorld* world      = (SerdWorld*)calloc(1, sizeof(SerdWorld));
-  SerdNode*  blank_node = serd_new_blank(serd_string("b00000000000"));
+  SerdAllocator* const actual =
+    allocator ? allocator : serd_default_allocator();
+
+  SerdWorld* world = (SerdWorld*)serd_acalloc(actual, 1, sizeof(SerdWorld));
+  SerdNode*  blank_node = serd_new_blank(actual, serd_string("b00000000000"));
 
   if (!world || !blank_node) {
-    serd_node_free(blank_node);
-    free(world);
+    serd_node_free(actual, blank_node);
+    serd_afree(actual, world);
     return NULL;
   }
 
   world->limits.reader_stack_size = 1048576U;
   world->limits.writer_max_depth  = 128U;
+  world->allocator                = actual;
   world->blank_node               = blank_node;
 
   serd_log_init(&world->log);
@@ -41,8 +45,8 @@ void
 serd_world_free(SerdWorld* const world)
 {
   if (world) {
-    serd_node_free(world->blank_node);
-    free(world);
+    serd_node_free(world->allocator, world->blank_node);
+    serd_afree(world->allocator, world);
   }
 }
 
@@ -78,3 +82,11 @@ serd_world_get_blank(SerdWorld* const world)
 
 #undef BLANK_CHARS
 }
+
+SerdAllocator*
+serd_world_allocator(const SerdWorld* const world)
+{
+  assert(world);
+  assert(world->allocator);
+  return world->allocator;
+}
diff --git a/src/world.h b/src/world.h
index af6281d4..2499b761 100644
--- a/src/world.h
+++ b/src/world.h
@@ -6,16 +6,21 @@
 
 #include "log.h"
 
+#include "serd/memory.h"
 #include "serd/node.h"
 #include "serd/world.h"
 
+#include <stdbool.h>
 #include <stdint.h>
 
 struct SerdWorldImpl {
-  SerdLimits limits;
-  SerdLog    log;
-  uint32_t   next_blank_id;
-  SerdNode*  blank_node;
+  SerdLimits     limits;
+  SerdAllocator* allocator;
+  SerdLog        log;
+  uint32_t       next_blank_id;
+  SerdNode*      blank_node;
+
+  bool stderr_color;
 };
 
 #endif // SERD_SRC_WORLD_H
diff --git a/src/writer.c b/src/writer.c
index fa1abd9f..6d52b4e6 100644
--- a/src/writer.c
+++ b/src/writer.c
@@ -3,6 +3,7 @@
 
 #include "block_dumper.h"
 #include "env.h"
+#include "memory.h"
 #include "namespaces.h"
 #include "node.h"
 #include "sink.h"
@@ -34,7 +35,6 @@
 #include <stdbool.h>
 #include <stdint.h>
 #include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 typedef enum {
@@ -175,14 +175,11 @@ supports_uriref(const SerdWriter* writer)
 }
 
 static SerdStatus
-free_context(WriteContext* const ctx)
+free_context(SerdWriter* const writer)
 {
-  serd_node_free(ctx->graph);
-  serd_node_free(ctx->subject);
-  serd_node_free(ctx->predicate);
-  ctx->graph     = NULL;
-  ctx->subject   = NULL;
-  ctx->predicate = NULL;
+  serd_node_free(writer->world->allocator, writer->context.graph);
+  serd_node_free(writer->world->allocator, writer->context.subject);
+  serd_node_free(writer->world->allocator, writer->context.predicate);
   return SERD_SUCCESS;
 }
 
@@ -234,13 +231,14 @@ push_context(SerdWriter* const        writer,
 
   // Update the current context
 
-  const WriteContext current = {type,
-                                flags,
-                                serd_node_copy(graph),
-                                serd_node_copy(subject),
-                                serd_node_copy(predicate),
-                                0U,
-                                0U};
+  const WriteContext current = {
+    type,
+    flags,
+    serd_node_copy(writer->world->allocator, graph),
+    serd_node_copy(writer->world->allocator, subject),
+    serd_node_copy(writer->world->allocator, predicate),
+    0U,
+    0U};
 
   writer->context = current;
   return SERD_SUCCESS;
@@ -251,7 +249,7 @@ pop_context(SerdWriter* writer)
 {
   assert(writer->anon_stack_size > 0);
 
-  free_context(&writer->context);
+  free_context(writer);
   writer->context = writer->anon_stack[--writer->anon_stack_size];
 }
 
@@ -971,10 +969,10 @@ write_pred(SerdWriter* writer, SerdStatementFlags flags, const SerdNode* pred)
   TRY(st, write_node(writer, pred, SERD_PREDICATE, flags));
   TRY(st, write_sep(writer, flags, SEP_P_O));
 
-  serd_node_set(&writer->context.predicate, pred);
   writer->context.predicates     = true;
   writer->context.comma_indented = false;
-  return st;
+  return serd_node_set(
+    writer->world->allocator, &writer->context.predicate, pred);
 }
 
 SERD_NODISCARD static SerdStatus
@@ -1068,7 +1066,7 @@ update_abbreviation_context(SerdWriter* const        writer,
 {
   SerdStatus st = SERD_SUCCESS;
 
-  // Push context for anonymous or list subject if necessary
+  // Push context for list or anonymous subject if necessary
   if (flags & SERD_ANON_S) {
     st = push_context(writer, CTX_BLANK, flags, graph, subject, predicate);
   } else if (flags & SERD_LIST_S) {
@@ -1175,9 +1173,13 @@ write_turtle_trig_statement(SerdWriter* const        writer,
       TRY(st, write_sep(writer, flags, SEP_ANON_S_P));
     }
 
-    // Set context to new subject and write predicate
+    // Set context to new subject
     reset_context(writer, 0U);
-    serd_node_set(&writer->context.subject, subject);
+    TRY(st,
+        serd_node_set(
+          writer->world->allocator, &writer->context.subject, subject));
+
+    // Write predicate
     if (!(flags & SERD_LIST_S)) {
       TRY(st, write_pred(writer, flags, predicate));
     }
@@ -1218,7 +1220,7 @@ write_trig_statement(SerdWriter* const        writer,
     if (graph) {
       TRY(st, write_node(writer, graph, SERD_GRAPH, flags));
       TRY(st, write_sep(writer, flags, SEP_GRAPH_BEGIN));
-      serd_node_set(&writer->context.graph, graph);
+      serd_node_set(writer->world->allocator, &writer->context.graph, graph);
     }
   }
 
@@ -1340,14 +1342,18 @@ serd_writer_new(SerdWorld*        world,
   assert(env);
   assert(output);
 
-  SerdBlockDumper dumper = {NULL, NULL, 0U, 0U};
-  if (serd_block_dumper_open(&dumper, output, block_size)) {
+  SerdBlockDumper dumper = {world->allocator, NULL, NULL, 0U, 0U};
+  if (serd_block_dumper_open(world, &dumper, output, block_size)) {
     return NULL;
   }
 
-  const size_t       max_depth = world->limits.writer_max_depth;
-  const WriteContext context   = WRITE_CONTEXT_NULL;
-  SerdWriter*        writer    = (SerdWriter*)calloc(1, sizeof(SerdWriter));
+  const WriteContext context = WRITE_CONTEXT_NULL;
+
+  SerdWriter* writer = (SerdWriter*)serd_wcalloc(world, 1, sizeof(SerdWriter));
+  if (!writer) {
+    serd_block_dumper_close(&dumper);
+    return NULL;
+  }
 
   writer->world     = world;
   writer->syntax    = syntax;
@@ -1358,13 +1364,19 @@ serd_writer_new(SerdWorld*        world,
   writer->output    = dumper;
   writer->context   = context;
 
-  if (max_depth) {
-    writer->max_depth  = max_depth;
-    writer->anon_stack = (WriteContext*)calloc(max_depth, sizeof(WriteContext));
+  if (world->limits.writer_max_depth) {
+    writer->max_depth  = world->limits.writer_max_depth;
+    writer->anon_stack = (WriteContext*)serd_wcalloc(
+      world, world->limits.writer_max_depth, sizeof(WriteContext));
+    if (!writer->anon_stack) {
+      serd_wfree(world, writer);
+      return NULL;
+    }
   }
 
-  writer->iface.handle   = writer;
-  writer->iface.on_event = (SerdEventFunc)serd_writer_on_event;
+  writer->iface.allocator = world->allocator;
+  writer->iface.handle    = writer;
+  writer->iface.on_event  = (SerdEventFunc)serd_writer_on_event;
 
   return writer;
 }
@@ -1374,14 +1386,15 @@ serd_writer_chop_blank_prefix(SerdWriter* writer, const char* prefix)
 {
   assert(writer);
 
-  free(writer->bprefix);
+  serd_wfree(writer->world, writer->bprefix);
   writer->bprefix_len = 0;
   writer->bprefix     = NULL;
 
   const size_t prefix_len = prefix ? strlen(prefix) : 0;
   if (prefix_len) {
     writer->bprefix_len = prefix_len;
-    writer->bprefix     = (char*)malloc(writer->bprefix_len + 1);
+    writer->bprefix =
+      (char*)serd_wmalloc(writer->world, writer->bprefix_len + 1);
     memcpy(writer->bprefix, prefix, writer->bprefix_len + 1);
   }
 }
@@ -1417,12 +1430,12 @@ serd_writer_set_root_uri(SerdWriter* writer, const SerdStringView uri)
 {
   assert(writer);
 
-  serd_node_free(writer->root_node);
+  serd_node_free(writer->world->allocator, writer->root_node);
   writer->root_node = NULL;
   writer->root_uri  = SERD_URI_NULL;
 
   if (uri.length) {
-    writer->root_node = serd_new_uri(uri);
+    writer->root_node = serd_new_uri(writer->world->allocator, uri);
     writer->root_uri  = serd_node_uri_view(writer->root_node);
   }
 
@@ -1462,13 +1475,13 @@ serd_writer_free(SerdWriter* writer)
   }
 
   serd_writer_finish(writer);
-  free_context(&writer->context);
+  free_context(writer);
   free_anon_stack(writer);
   serd_block_dumper_close(&writer->output);
-  free(writer->anon_stack);
-  free(writer->bprefix);
-  serd_node_free(writer->root_node);
-  free(writer);
+  serd_wfree(writer->world, writer->anon_stack);
+  serd_wfree(writer->world, writer->bprefix);
+  serd_node_free(writer->world->allocator, writer->root_node);
+  serd_wfree(writer->world, writer);
 }
 
 const SerdSink*
diff --git a/test/failing_allocator.c b/test/failing_allocator.c
new file mode 100644
index 00000000..89c19bad
--- /dev/null
+++ b/test/failing_allocator.c
@@ -0,0 +1,104 @@
+// Copyright 2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#include "failing_allocator.h"
+
+#include "zix/attributes.h"
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+static bool
+attempt(SerdFailingAllocator* const allocator)
+{
+  ++allocator->n_allocations;
+
+  if (!allocator->n_remaining) {
+    return false;
+  }
+
+  --allocator->n_remaining;
+  return true;
+}
+
+ZIX_MALLOC_FUNC static void*
+serd_failing_malloc(SerdAllocator* const allocator, const size_t size)
+{
+  SerdFailingAllocator* const state = (SerdFailingAllocator*)allocator;
+  SerdAllocator* const        base  = serd_default_allocator();
+
+  return attempt(state) ? base->malloc(base, size) : NULL;
+}
+
+ZIX_MALLOC_FUNC static void*
+serd_failing_calloc(SerdAllocator* const allocator,
+                    const size_t         nmemb,
+                    const size_t         size)
+{
+  SerdFailingAllocator* const state = (SerdFailingAllocator*)allocator;
+  SerdAllocator* const        base  = serd_default_allocator();
+
+  return attempt(state) ? base->calloc(base, nmemb, size) : NULL;
+}
+
+static void*
+serd_failing_realloc(SerdAllocator* const allocator,
+                     void* const          ptr,
+                     const size_t         size)
+{
+  SerdFailingAllocator* const state = (SerdFailingAllocator*)allocator;
+  SerdAllocator* const        base  = serd_default_allocator();
+
+  return attempt(state) ? base->realloc(base, ptr, size) : NULL;
+}
+
+static void
+serd_failing_free(SerdAllocator* const allocator, void* const ptr)
+{
+  (void)allocator;
+
+  SerdAllocator* const base = serd_default_allocator();
+
+  base->free(base, ptr);
+}
+
+ZIX_MALLOC_FUNC static void*
+serd_failing_aligned_alloc(SerdAllocator* const allocator,
+                           const size_t         alignment,
+                           const size_t         size)
+{
+  SerdFailingAllocator* const state = (SerdFailingAllocator*)allocator;
+  SerdAllocator* const        base  = serd_default_allocator();
+
+  return attempt(state) ? base->aligned_alloc(base, alignment, size) : NULL;
+}
+
+static void
+serd_failing_aligned_free(SerdAllocator* const allocator, void* const ptr)
+{
+  (void)allocator;
+
+  SerdAllocator* const base = serd_default_allocator();
+
+  base->aligned_free(base, ptr);
+}
+
+ZIX_CONST_FUNC SerdFailingAllocator
+serd_failing_allocator(void)
+{
+  SerdFailingAllocator failing_allocator = {
+    {
+      serd_failing_malloc,
+      serd_failing_calloc,
+      serd_failing_realloc,
+      serd_failing_free,
+      serd_failing_aligned_alloc,
+      serd_failing_aligned_free,
+    },
+    0,
+    SIZE_MAX,
+  };
+
+  return failing_allocator;
+}
diff --git a/test/failing_allocator.h b/test/failing_allocator.h
new file mode 100644
index 00000000..7bc514bb
--- /dev/null
+++ b/test/failing_allocator.h
@@ -0,0 +1,21 @@
+// Copyright 2021 David Robillard <d@drobilla.net>
+// SPDX-License-Identifier: ISC
+
+#ifndef SERD_TEST_FAILING_ALLOCATOR_H
+#define SERD_TEST_FAILING_ALLOCATOR_H
+
+#include "serd/serd.h"
+
+#include <stddef.h>
+
+/// An allocator that fails after some number of successes for testing
+typedef struct {
+  SerdAllocator base;          ///< Base allocator instance
+  size_t        n_allocations; ///< Number of attempted allocations
+  size_t        n_remaining;   ///< Number of remaining successful allocations
+} SerdFailingAllocator;
+
+SerdFailingAllocator
+serd_failing_allocator(void);
+
+#endif // SERD_TEST_FAILING_ALLOCATOR_H
diff --git a/test/meson.build b/test/meson.build
index dde17566..5c0ac7e8 100644
--- a/test/meson.build
+++ b/test/meson.build
@@ -155,7 +155,7 @@ foreach unit : unit_tests
     unit,
     executable(
       'test_@0@'.format(unit),
-      files('test_@0@.c'.format(unit)),
+      files('failing_allocator.c', 'test_@0@.c'.format(unit)),
       c_args: c_suppressions + platform_c_args,
       dependencies: [serd_dep, zix_dep],
     ),
diff --git a/test/test_caret.c b/test/test_caret.c
index a239c242..a97b3d0f 100644
--- a/test/test_caret.c
+++ b/test/test_caret.c
@@ -1,35 +1,38 @@
-// Copyright 2019-2020 David Robillard <d@drobilla.net>
+// Copyright 2019-2021 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/caret.h"
 #include "serd/node.h"
 #include "serd/string_view.h"
 
 #include <assert.h>
 #include <stddef.h>
+#include <stdint.h>
 
-int
-main(void)
+static int
+test_caret(void)
 {
-  SerdNode* const  node  = serd_new_string(serd_string("node"));
-  SerdCaret* const caret = serd_caret_new(node, 46, 2);
+  SerdNode* const  node  = serd_new_string(NULL, serd_string("node"));
+  SerdCaret* const caret = serd_caret_new(NULL, node, 46, 2);
 
   assert(serd_caret_equals(caret, caret));
   assert(serd_caret_document(caret) == node);
   assert(serd_caret_line(caret) == 46);
   assert(serd_caret_column(caret) == 2);
 
-  SerdCaret* const copy = serd_caret_copy(caret);
+  SerdCaret* const copy = serd_caret_copy(NULL, caret);
 
   assert(serd_caret_equals(caret, copy));
-  assert(!serd_caret_copy(NULL));
+  assert(!serd_caret_copy(NULL, NULL));
 
-  SerdNode* const  other_node = serd_new_string(serd_string("other"));
-  SerdCaret* const other_file = serd_caret_new(other_node, 46, 2);
-  SerdCaret* const other_line = serd_caret_new(node, 47, 2);
-  SerdCaret* const other_col  = serd_caret_new(node, 46, 3);
+  SerdNode* const  other_node = serd_new_string(NULL, serd_string("other"));
+  SerdCaret* const other_file = serd_caret_new(NULL, other_node, 46, 2);
+  SerdCaret* const other_line = serd_caret_new(NULL, node, 47, 2);
+  SerdCaret* const other_col  = serd_caret_new(NULL, node, 46, 3);
 
   assert(!serd_caret_equals(caret, other_file));
   assert(!serd_caret_equals(caret, other_line));
@@ -37,13 +40,57 @@ main(void)
   assert(!serd_caret_equals(caret, NULL));
   assert(!serd_caret_equals(NULL, caret));
 
-  serd_caret_free(other_col);
-  serd_caret_free(other_line);
-  serd_caret_free(other_file);
-  serd_node_free(other_node);
-  serd_caret_free(copy);
-  serd_caret_free(caret);
-  serd_node_free(node);
+  serd_caret_free(NULL, other_col);
+  serd_caret_free(NULL, other_line);
+  serd_caret_free(NULL, other_file);
+  serd_node_free(NULL, other_node);
+  serd_caret_free(NULL, copy);
+  serd_caret_free(NULL, caret);
+  serd_node_free(NULL, node);
+
+  return 0;
+}
+
+static void
+test_failed_alloc(void)
+{
+  SerdNode* node = serd_new_token(NULL, SERD_LITERAL, serd_string("node"));
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
 
+  // Successfully allocate a new caret to count the number of allocations
+  SerdCaret* const caret = serd_caret_new(&allocator.base, node, 46, 2);
+  assert(caret);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations;
+  for (size_t i = 0U; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_caret_new(&allocator.base, node, 46, 2));
+  }
+
+  // Successfully copy the caret to count the number of allocations
+  allocator.n_allocations = 0;
+  allocator.n_remaining   = SIZE_MAX;
+  SerdCaret* const copy   = serd_caret_copy(&allocator.base, caret);
+  assert(copy);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_copy_allocs = allocator.n_allocations;
+  for (size_t i = 0U; i < n_copy_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_caret_copy(&allocator.base, caret));
+  }
+
+  serd_caret_free(&allocator.base, copy);
+  serd_caret_free(&allocator.base, caret);
+  serd_node_free(NULL, node);
+}
+
+int
+main(void)
+{
+  test_caret();
+  test_failed_alloc();
   return 0;
 }
diff --git a/test/test_env.c b/test/test_env.c
index 33e41af4..89947826 100644
--- a/test/test_env.c
+++ b/test/test_env.c
@@ -3,6 +3,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/env.h"
 #include "serd/event.h"
 #include "serd/node.h"
@@ -11,21 +13,139 @@
 #include "serd/string_view.h"
 
 #include <assert.h>
+#include <stdio.h>
 #include <string.h>
 
 #define NS_EG "http://example.org/"
 
 static void
+test_new_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  // Successfully allocate a env to count the number of allocations
+  SerdEnv* const env = serd_env_new(&allocator.base, serd_empty_string());
+  assert(env);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_env_new(&allocator.base, serd_empty_string()));
+  }
+
+  serd_env_free(env);
+}
+
+static void
+test_copy_failed_alloc(void)
+{
+  static const char name[] = "eg";
+  static const char uri[]  = "http://example.org/";
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdEnv* const env = serd_env_new(&allocator.base, serd_empty_string());
+
+  assert(!serd_env_set_prefix(env, serd_string(name), serd_string(uri)));
+  assert(!serd_env_set_base_uri(env, serd_string(uri)));
+
+  // Successfully copy an env to count the number of allocations
+  const size_t   n_setup_allocs = allocator.n_allocations;
+  SerdEnv* const copy           = serd_env_copy(&allocator.base, env);
+  assert(copy);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_copy_allocs = allocator.n_allocations - n_setup_allocs;
+  for (size_t i = 0; i < n_copy_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_env_copy(&allocator.base, env));
+  }
+
+  serd_env_free(copy);
+  serd_env_free(env);
+}
+
+static void
+test_set_prefix_absolute_failed_alloc(void)
+{
+  const SerdStringView base_uri = serd_string("http://example.org/");
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdEnv* const env = serd_env_new(&allocator.base, base_uri);
+
+  char name[64] = "eg";
+  char uri[64]  = "http://example.org/";
+
+  SerdStatus   st             = SERD_SUCCESS;
+  const size_t n_setup_allocs = allocator.n_allocations;
+
+  // Successfully set an absolute prefix to count the number of allocations
+  st = serd_env_set_prefix(env, serd_string(name), serd_string(uri));
+  assert(st == SERD_SUCCESS);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_set_prefix_allocs = allocator.n_allocations - n_setup_allocs;
+  for (size_t i = 0; i < n_set_prefix_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    snprintf(name, sizeof(name), "eg%zu", i);
+    snprintf(uri, sizeof(name), "http://example.org/%zu", i);
+
+    st = serd_env_set_prefix(env, serd_string(name), serd_string(uri));
+    assert(st == SERD_BAD_ALLOC);
+  }
+
+  serd_env_free(env);
+}
+
+static void
+test_set_prefix_relative_failed_alloc(void)
+{
+  const SerdStringView base_uri = serd_string("http://example.org/");
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  char name[64] = "egX";
+  char uri[64]  = "relativeX";
+
+  // Successfully set an absolute prefix to count the number of allocations
+  SerdEnv*   env = serd_env_new(&allocator.base, base_uri);
+  SerdStatus st = serd_env_set_prefix(env, serd_string(name), serd_string(uri));
+  assert(st == SERD_SUCCESS);
+  serd_env_free(env);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_set_prefix_allocs = allocator.n_allocations;
+  for (size_t i = 0; i < n_set_prefix_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    snprintf(name, sizeof(name), "eg%zu", i);
+    snprintf(uri, sizeof(uri), "relative%zu", i);
+
+    env = serd_env_new(&allocator.base, base_uri);
+    if (env) {
+      st = serd_env_set_prefix(env, serd_string(name), serd_string(uri));
+      assert(st == SERD_BAD_ALLOC);
+    }
+
+    serd_env_free(env);
+  }
+}
+
+static void
 test_copy(void)
 {
-  assert(!serd_env_copy(NULL));
+  assert(!serd_env_copy(NULL, NULL));
 
-  SerdEnv* const env = serd_env_new(serd_string("http://example.org/base/"));
+  SerdEnv* const env =
+    serd_env_new(NULL, serd_string("http://example.org/base/"));
 
   serd_env_set_prefix(
     env, serd_string("eg"), serd_string("http://example.org/"));
 
-  SerdEnv* const env_copy = serd_env_copy(env);
+  SerdEnv* const env_copy = serd_env_copy(NULL, env);
 
   assert(serd_env_equals(env, env_copy));
 
@@ -46,7 +166,7 @@ test_copy(void)
 static void
 test_comparison(void)
 {
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
 
   assert(!serd_env_equals(env, NULL));
   assert(!serd_env_equals(NULL, env));
@@ -60,7 +180,7 @@ static void
 test_null(void)
 {
   // "Copying" NULL returns null
-  assert(!serd_env_copy(NULL));
+  assert(!serd_env_copy(NULL, NULL));
 
   // Accessors are tolerant to a NULL env for convenience
   assert(!serd_env_base_uri(NULL));
@@ -81,8 +201,8 @@ count_prefixes(void* handle, const SerdEvent* event)
 static void
 test_base_uri(void)
 {
-  SerdEnv* const  env = serd_env_new(serd_empty_string());
-  SerdNode* const eg  = serd_new_uri(serd_string(NS_EG));
+  SerdEnv* const  env = serd_env_new(NULL, serd_empty_string());
+  SerdNode* const eg  = serd_new_uri(NULL, serd_string(NS_EG));
 
   // Test that invalid calls work as expected
   assert(!serd_env_base_uri(env));
@@ -101,8 +221,8 @@ test_base_uri(void)
   assert(!serd_env_set_base_uri(env, serd_empty_string()));
   assert(!serd_env_base_uri(env));
 
+  serd_node_free(NULL, eg);
   serd_env_free(env);
-  serd_node_free(eg);
 }
 
 static void
@@ -114,7 +234,7 @@ test_set_prefix(void)
   const SerdStringView rel   = serd_string("rel");
   const SerdStringView base  = serd_string("http://example.org/");
 
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
 
   // Set a valid prefix
   assert(!serd_env_set_prefix(env, name1, eg));
@@ -130,7 +250,7 @@ test_set_prefix(void)
 
   size_t          n_prefixes = 0;
   SerdSink* const count_prefixes_sink =
-    serd_sink_new(&n_prefixes, count_prefixes, NULL);
+    serd_sink_new(NULL, &n_prefixes, count_prefixes, NULL);
 
   serd_env_write_prefixes(env, count_prefixes_sink);
   serd_sink_free(count_prefixes_sink);
@@ -142,13 +262,13 @@ test_set_prefix(void)
 static void
 test_expand_untyped_literal(void)
 {
-  SerdNode* const untyped = serd_new_string(serd_string("data"));
-  SerdEnv* const  env     = serd_env_new(serd_empty_string());
+  SerdNode* const untyped = serd_new_string(NULL, serd_string("data"));
+  SerdEnv* const  env     = serd_env_new(NULL, serd_empty_string());
 
   assert(!serd_env_expand_node(env, untyped));
 
   serd_env_free(env);
-  serd_node_free(untyped);
+  serd_node_free(NULL, untyped);
 }
 
 static void
@@ -157,14 +277,14 @@ test_expand_bad_uri_datatype(void)
   const SerdStringView type = serd_string("Type");
 
   SerdNode* const typed =
-    serd_new_literal(serd_string("data"), SERD_HAS_DATATYPE, type);
+    serd_new_literal(NULL, serd_string("data"), SERD_HAS_DATATYPE, type);
 
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
 
   assert(!serd_env_expand_node(env, typed));
 
   serd_env_free(env);
-  serd_node_free(typed);
+  serd_node_free(NULL, typed);
 }
 
 static void
@@ -172,19 +292,19 @@ test_expand_uri(void)
 {
   const SerdStringView base = serd_string("http://example.org/b/");
 
-  SerdEnv* const  env       = serd_env_new(base);
-  SerdNode* const rel       = serd_new_uri(serd_string("rel"));
+  SerdEnv* const  env       = serd_env_new(NULL, base);
+  SerdNode* const rel       = serd_new_uri(NULL, serd_string("rel"));
   SerdNode* const rel_out   = serd_env_expand_node(env, rel);
-  SerdNode* const empty     = serd_new_uri(serd_empty_string());
+  SerdNode* const empty     = serd_new_uri(NULL, serd_empty_string());
   SerdNode* const empty_out = serd_env_expand_node(env, empty);
 
   assert(!strcmp(serd_node_string(rel_out), "http://example.org/b/rel"));
   assert(!strcmp(serd_node_string(empty_out), "http://example.org/b/"));
 
-  serd_node_free(empty_out);
-  serd_node_free(empty);
-  serd_node_free(rel_out);
-  serd_node_free(rel);
+  serd_node_free(NULL, empty_out);
+  serd_node_free(NULL, empty);
+  serd_node_free(NULL, rel_out);
+  serd_node_free(NULL, rel);
   serd_env_free(env);
 }
 
@@ -193,27 +313,27 @@ test_expand_empty_uri_ref(void)
 {
   const SerdStringView base = serd_string("http://example.org/b/");
 
-  SerdNode* const rel     = serd_new_uri(serd_string("rel"));
-  SerdEnv* const  env     = serd_env_new(base);
+  SerdNode* const rel     = serd_new_uri(NULL, serd_string("rel"));
+  SerdEnv* const  env     = serd_env_new(NULL, base);
   SerdNode* const rel_out = serd_env_expand_node(env, rel);
 
   assert(!strcmp(serd_node_string(rel_out), "http://example.org/b/rel"));
-  serd_node_free(rel_out);
+  serd_node_free(NULL, rel_out);
 
   serd_env_free(env);
-  serd_node_free(rel);
+  serd_node_free(NULL, rel);
 }
 
 static void
 test_expand_bad_uri(void)
 {
-  SerdNode* const bad_uri = serd_new_uri(serd_string("rel"));
-  SerdEnv* const  env     = serd_env_new(serd_empty_string());
+  SerdNode* const bad_uri = serd_new_uri(NULL, serd_string("rel"));
+  SerdEnv* const  env     = serd_env_new(NULL, serd_empty_string());
 
   assert(!serd_env_expand_node(env, bad_uri));
 
   serd_env_free(env);
-  serd_node_free(bad_uri);
+  serd_node_free(NULL, bad_uri);
 }
 
 static void
@@ -222,7 +342,7 @@ test_expand_curie(void)
   const SerdStringView name = serd_string("eg.1");
   const SerdStringView eg   = serd_string(NS_EG);
 
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
 
   assert(!serd_env_set_prefix(env, name, eg));
 
@@ -231,7 +351,7 @@ test_expand_curie(void)
 
   assert(expanded);
   assert(!strcmp(serd_node_string(expanded), "http://example.org/foo"));
-  serd_node_free(expanded);
+  serd_node_free(NULL, expanded);
 
   serd_env_free(env);
 }
@@ -239,7 +359,7 @@ test_expand_curie(void)
 static void
 test_expand_bad_curie(void)
 {
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
 
   assert(!serd_env_expand_curie(NULL, serd_empty_string()));
   assert(!serd_env_expand_curie(NULL, serd_string("what:ever")));
@@ -252,13 +372,13 @@ test_expand_bad_curie(void)
 static void
 test_expand_blank(void)
 {
-  SerdNode* const blank = serd_new_blank(serd_string("b1"));
-  SerdEnv* const  env   = serd_env_new(serd_empty_string());
+  SerdNode* const blank = serd_new_blank(NULL, serd_string("b1"));
+  SerdEnv* const  env   = serd_env_new(NULL, serd_empty_string());
 
   assert(!serd_env_expand_node(env, blank));
 
   serd_env_free(env);
-  serd_node_free(blank);
+  serd_node_free(NULL, blank);
 }
 
 static void
@@ -268,8 +388,8 @@ test_equals(void)
   const SerdStringView base1 = serd_string(NS_EG "b1/");
   const SerdStringView base2 = serd_string(NS_EG "b2/");
 
-  SerdEnv* const env1 = serd_env_new(base1);
-  SerdEnv* const env2 = serd_env_new(base2);
+  SerdEnv* const env1 = serd_env_new(NULL, base1);
+  SerdEnv* const env2 = serd_env_new(NULL, base2);
 
   assert(!serd_env_equals(env1, NULL));
   assert(!serd_env_equals(NULL, env1));
@@ -289,7 +409,7 @@ test_equals(void)
   serd_env_set_base_uri(env2, base2);
   assert(!serd_env_equals(env1, env2));
 
-  SerdEnv* const env3 = serd_env_copy(env2);
+  SerdEnv* const env3 = serd_env_copy(NULL, env2);
   assert(serd_env_equals(env3, env2));
   serd_env_free(env3);
 
@@ -300,6 +420,10 @@ test_equals(void)
 int
 main(void)
 {
+  test_new_failed_alloc();
+  test_copy_failed_alloc();
+  test_set_prefix_absolute_failed_alloc();
+  test_set_prefix_relative_failed_alloc();
   test_copy();
   test_comparison();
   test_null();
diff --git a/test/test_free_null.c b/test/test_free_null.c
index 87dfa7db..891f9b65 100644
--- a/test/test_free_null.c
+++ b/test/test_free_null.c
@@ -17,14 +17,14 @@
 int
 main(void)
 {
-  serd_free(NULL);
-  serd_node_free(NULL);
+  serd_free(NULL, NULL);
+  serd_node_free(NULL, NULL);
   serd_world_free(NULL);
   serd_env_free(NULL);
   serd_sink_free(NULL);
   serd_reader_free(NULL);
   serd_writer_free(NULL);
-  serd_caret_free(NULL);
+  serd_caret_free(NULL, NULL);
 
   return 0;
 }
diff --git a/test/test_log.c b/test/test_log.c
index 3ab2008f..5da8ec09 100644
--- a/test/test_log.c
+++ b/test/test_log.c
@@ -39,7 +39,7 @@ custom_log_func(void* const               handle,
 static void
 test_bad_arg(void)
 {
-  SerdWorld* const world  = serd_world_new();
+  SerdWorld* const world  = serd_world_new(NULL);
   bool             called = false;
 
   serd_set_log_func(world, custom_log_func, &called);
@@ -52,7 +52,7 @@ test_bad_arg(void)
 static void
 test_default_log(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
 
   for (unsigned i = 0; i <= SERD_LOG_LEVEL_DEBUG; ++i) {
     const SerdLogLevel level = (SerdLogLevel)i;
@@ -66,7 +66,7 @@ test_default_log(void)
 static void
 test_custom_log(void)
 {
-  SerdWorld* const world  = serd_world_new();
+  SerdWorld* const world  = serd_world_new(NULL);
   bool             called = false;
 
   serd_set_log_func(world, custom_log_func, &called);
@@ -82,22 +82,22 @@ test_custom_log(void)
 static void
 test_caret(void)
 {
-  SerdWorld* const world = serd_world_new();
-  SerdNode* const  name  = serd_new_string(serd_string("filename"));
-  SerdCaret* const caret = serd_caret_new(name, 46, 2);
+  SerdWorld* const world = serd_world_new(NULL);
+  SerdNode* const  name  = serd_new_string(NULL, serd_string("filename"));
+  SerdCaret* const caret = serd_caret_new(NULL, name, 46, 2);
 
   serd_logf_at(world, SERD_LOG_LEVEL_NOTICE, caret, "is just ahead of me");
   serd_logf_at(world, SERD_LOG_LEVEL_NOTICE, NULL, "isn't");
 
-  serd_caret_free(caret);
-  serd_node_free(name);
+  serd_caret_free(NULL, caret);
+  serd_node_free(NULL, name);
   serd_world_free(world);
 }
 
 static void
 test_filename_only(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
 
   const SerdLogField fields[3] = {{"TEST_KEY", "TEST VALUE"},
                                   {"SERD_FILE", "somename"},
diff --git a/test/test_node.c b/test/test_node.c
index 07ea4973..23d1a45a 100644
--- a/test/test_node.c
+++ b/test/test_node.c
@@ -3,7 +3,6 @@
 
 #undef NDEBUG
 
-#include "serd/memory.h"
 #include "serd/node.h"
 #include "serd/status.h"
 #include "serd/string_view.h"
@@ -51,23 +50,23 @@
 static void
 test_boolean(void)
 {
-  SerdNode* const true_node = serd_new_boolean(true);
+  SerdNode* const true_node = serd_new_boolean(NULL, true);
   assert(!strcmp(serd_node_string(true_node), "true"));
   assert(serd_get_boolean(true_node));
 
   const SerdNode* const true_datatype = serd_node_datatype(true_node);
   assert(true_datatype);
   assert(!strcmp(serd_node_string(true_datatype), NS_XSD "boolean"));
-  serd_node_free(true_node);
+  serd_node_free(NULL, true_node);
 
-  SerdNode* const false_node = serd_new_boolean(false);
+  SerdNode* const false_node = serd_new_boolean(NULL, false);
   assert(!strcmp(serd_node_string(false_node), "false"));
   assert(!serd_get_boolean(false_node));
 
   const SerdNode* const false_datatype = serd_node_datatype(false_node);
   assert(false_datatype);
   assert(!strcmp(serd_node_string(false_datatype), NS_XSD "boolean"));
-  serd_node_free(false_node);
+  serd_node_free(NULL, false_node);
 }
 
 static void
@@ -76,12 +75,12 @@ check_get_boolean(const char* string,
                   const bool  expected)
 {
   SerdNode* const node = serd_new_literal(
-    serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
+    NULL, serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
 
   assert(node);
   assert(serd_get_boolean(node) == expected);
 
-  serd_node_free(node);
+  serd_node_free(NULL, node);
 }
 
 static void
@@ -115,7 +114,7 @@ test_decimal(void)
                                              "0.0000000001"};
 
   for (size_t i = 0; i < sizeof(test_values) / sizeof(double); ++i) {
-    SerdNode*   node     = serd_new_decimal(test_values[i], NULL);
+    SerdNode*   node     = serd_new_decimal(NULL, test_values[i], NULL);
     const char* node_str = serd_node_string(node);
     assert(!strcmp(node_str, test_strings[i]));
 
@@ -128,7 +127,7 @@ test_decimal(void)
 
     const double value = serd_get_double(node);
     assert(!memcmp(&value, &test_values[i], sizeof(value)));
-    serd_node_free(node);
+    serd_node_free(NULL, node);
   }
 }
 
@@ -140,7 +139,7 @@ test_double(void)
     "0.0E0", "-0.0E0", "1.2E0", "-2.3E0", "4.56789E6"};
 
   for (size_t i = 0; i < sizeof(test_values) / sizeof(double); ++i) {
-    SerdNode*   node     = serd_new_double(test_values[i]);
+    SerdNode*   node     = serd_new_double(NULL, test_values[i]);
     const char* node_str = serd_node_string(node);
     assert(!strcmp(node_str, test_strings[i]));
 
@@ -153,7 +152,7 @@ test_double(void)
 
     const double value = serd_get_double(node);
     assert(!memcmp(&value, &test_values[i], sizeof(value)));
-    serd_node_free(node);
+    serd_node_free(NULL, node);
   }
 }
 
@@ -163,14 +162,14 @@ check_get_double(const char*  string,
                  const double expected)
 {
   SerdNode* const node = serd_new_literal(
-    serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
+    NULL, serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
 
   assert(node);
 
   const double value = serd_get_double(node);
   assert(!memcmp(&value, &expected, sizeof(value)));
 
-  serd_node_free(node);
+  serd_node_free(NULL, node);
 }
 
 static void
@@ -187,20 +186,22 @@ test_get_double(void)
 
   SERD_DISABLE_CONVERSION_WARNINGS
 
-  SerdNode* const nan = serd_new_string(serd_string("unknown"));
+  SerdNode* const nan = serd_new_string(NULL, serd_string("unknown"));
   assert(isnan(serd_get_double(nan)));
-  serd_node_free(nan);
+  serd_node_free(NULL, nan);
 
-  SerdNode* const invalid = serd_new_literal(
-    serd_string("!invalid"), SERD_HAS_DATATYPE, serd_string(NS_XSD "long"));
+  SerdNode* const invalid = serd_new_literal(NULL,
+                                             serd_string("!invalid"),
+                                             SERD_HAS_DATATYPE,
+                                             serd_string(NS_XSD "long"));
 
   assert(isnan(serd_get_double(invalid)));
-  serd_node_free(invalid);
+  serd_node_free(NULL, invalid);
 
-  SerdNode* const base64 = serd_new_base64(blob, sizeof(blob));
+  SerdNode* const base64 = serd_new_base64(NULL, blob, sizeof(blob));
 
   assert(isnan(serd_get_double(base64)));
-  serd_node_free(base64);
+  serd_node_free(NULL, base64);
 
   SERD_RESTORE_WARNINGS
 }
@@ -213,7 +214,7 @@ test_float(void)
     "0.0E0", "-0.0E0", "1.5E0", "-2.5E0", "4.56789E6"};
 
   for (size_t i = 0; i < sizeof(test_values) / sizeof(float); ++i) {
-    SerdNode*   node     = serd_new_float(test_values[i]);
+    SerdNode*   node     = serd_new_float(NULL, test_values[i]);
     const char* node_str = serd_node_string(node);
     assert(!strcmp(node_str, test_strings[i]));
 
@@ -226,7 +227,7 @@ test_float(void)
 
     const float value = serd_get_float(node);
     assert(!memcmp(&value, &test_values[i], sizeof(value)));
-    serd_node_free(node);
+    serd_node_free(NULL, node);
   }
 }
 
@@ -236,14 +237,14 @@ check_get_float(const char* string,
                 const float expected)
 {
   SerdNode* const node = serd_new_literal(
-    serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
+    NULL, serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
 
   assert(node);
 
   const float value = serd_get_float(node);
   assert(!memcmp(&value, &expected, sizeof(value)));
 
-  serd_node_free(node);
+  serd_node_free(NULL, node);
 }
 
 static void
@@ -258,18 +259,20 @@ test_get_float(void)
 
   SERD_DISABLE_CONVERSION_WARNINGS
 
-  SerdNode* const nan = serd_new_string(serd_string("unknown"));
+  SerdNode* const nan = serd_new_string(NULL, serd_string("unknown"));
   assert(isnan(serd_get_float(nan)));
-  serd_node_free(nan);
+  serd_node_free(NULL, nan);
 
-  SerdNode* const invalid = serd_new_literal(
-    serd_string("!invalid"), SERD_HAS_DATATYPE, serd_string(NS_XSD "long"));
+  SerdNode* const invalid = serd_new_literal(NULL,
+                                             serd_string("!invalid"),
+                                             SERD_HAS_DATATYPE,
+                                             serd_string(NS_XSD "long"));
 
   assert(isnan(serd_get_double(invalid)));
 
   SERD_RESTORE_WARNINGS
 
-  serd_node_free(invalid);
+  serd_node_free(NULL, invalid);
 }
 
 static void
@@ -280,7 +283,7 @@ test_integer(void)
     "0", "0", "-23", "23", "-12340", "1000", "-1000"};
 
   for (size_t i = 0; i < sizeof(test_values) / sizeof(double); ++i) {
-    SerdNode*   node     = serd_new_integer(test_values[i]);
+    SerdNode*   node     = serd_new_integer(NULL, test_values[i]);
     const char* node_str = serd_node_string(node);
     assert(!strcmp(node_str, test_strings[i]));
     const size_t len = strlen(node_str);
@@ -291,7 +294,7 @@ test_integer(void)
     assert(!strcmp(serd_node_string(datatype), NS_XSD "integer"));
 
     assert(serd_get_integer(node) == test_values[i]);
-    serd_node_free(node);
+    serd_node_free(NULL, node);
   }
 }
 
@@ -301,12 +304,12 @@ check_get_integer(const char*   string,
                   const int64_t expected)
 {
   SerdNode* const node = serd_new_literal(
-    serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
+    NULL, serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
 
   assert(node);
   assert(serd_get_integer(node) == expected);
 
-  serd_node_free(node);
+  serd_node_free(NULL, node);
 }
 
 static void
@@ -325,7 +328,7 @@ test_get_integer(void)
 static void
 test_base64(void)
 {
-  assert(!serd_new_base64(&SERD_URI_NULL, 0));
+  assert(!serd_new_base64(NULL, &SERD_URI_NULL, 0));
 
   // Test valid base64 blobs with a range of sizes
   for (size_t size = 1; size < 256; ++size) {
@@ -334,7 +337,7 @@ test_base64(void)
       data[i] = (uint8_t)((size + i) % 256);
     }
 
-    SerdNode*    blob     = serd_new_base64(data, size);
+    SerdNode*    blob     = serd_new_base64(NULL, data, size);
     const char*  blob_str = serd_node_string(blob);
     const size_t max_size = serd_get_base64_size(blob);
     uint8_t*     out      = (uint8_t*)calloc(1, max_size);
@@ -353,8 +356,8 @@ test_base64(void)
     assert(datatype);
     assert(!strcmp(serd_node_string(datatype), NS_XSD "base64Binary"));
 
-    serd_node_free(blob);
-    serd_free(out);
+    serd_node_free(NULL, blob);
+    free(out);
     free(data);
   }
 }
@@ -365,7 +368,7 @@ check_get_base64(const char* string,
                  const char* expected)
 {
   SerdNode* const node = serd_new_literal(
-    serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
+    NULL, serd_string(string), SERD_HAS_DATATYPE, serd_string(datatype_uri));
 
   assert(node);
 
@@ -380,7 +383,7 @@ check_get_base64(const char* string,
   assert(strlen(decoded) <= max_size);
 
   free(decoded);
-  serd_node_free(node);
+  serd_node_free(NULL, node);
 }
 
 static void
@@ -390,14 +393,16 @@ test_get_base64(void)
   check_get_base64("Zm9vYg==", NS_XSD "base64Binary", "foob");
   check_get_base64(" \f\n\r\t\vZm9v \f\n\r\t\v", NS_XSD "base64Binary", "foo");
 
-  SerdNode* const node = serd_new_literal(
-    serd_string("Zm9v"), SERD_HAS_DATATYPE, serd_string(NS_XSD "base64Binary"));
+  SerdNode* const node = serd_new_literal(NULL,
+                                          serd_string("Zm9v"),
+                                          SERD_HAS_DATATYPE,
+                                          serd_string(NS_XSD "base64Binary"));
 
   char                  small[2] = {0};
   const SerdWriteResult r        = serd_get_base64(node, sizeof(small), small);
 
   assert(r.status == SERD_OVERFLOW);
-  serd_node_free(node);
+  serd_node_free(NULL, node);
 }
 
 static void
@@ -408,56 +413,56 @@ test_node_equals(void)
   static const SerdStringView replacement_char = {
     (const char*)replacement_char_str, 3};
 
-  SerdNode* lhs = serd_new_string(replacement_char);
-  SerdNode* rhs = serd_new_string(serd_string("123"));
+  SerdNode* lhs = serd_new_string(NULL, replacement_char);
+  SerdNode* rhs = serd_new_string(NULL, serd_string("123"));
 
   assert(serd_node_equals(lhs, lhs));
   assert(!serd_node_equals(lhs, rhs));
 
-  assert(!serd_node_copy(NULL));
+  assert(!serd_node_copy(NULL, NULL));
 
-  serd_node_free(lhs);
-  serd_node_free(rhs);
+  serd_node_free(NULL, lhs);
+  serd_node_free(NULL, rhs);
 }
 
 static void
 test_node_from_string(void)
 {
-  SerdNode* const hello = serd_new_string(serd_string("hello\""));
+  SerdNode* const hello = serd_new_string(NULL, serd_string("hello\""));
   assert(serd_node_length(hello) == 6);
   assert(!serd_node_flags(hello));
   assert(!strncmp(serd_node_string(hello), "hello\"", 6));
   assert(!strcmp(serd_node_string_view(hello).data, "hello\""));
   assert(serd_node_string_view(hello).length == 6);
-  serd_node_free(hello);
+  serd_node_free(NULL, hello);
 
-  SerdNode* const uri = serd_new_uri(serd_string("http://example.org/"));
+  SerdNode* const uri = serd_new_uri(NULL, serd_string("http://example.org/"));
   assert(serd_node_length(uri) == 19);
   assert(!strcmp(serd_node_string(uri), "http://example.org/"));
   assert(serd_node_uri_view(uri).authority.length == 11);
   assert(!strncmp(serd_node_uri_view(uri).authority.data, "example.org", 11));
-  serd_node_free(uri);
+  serd_node_free(NULL, uri);
 }
 
 static void
 test_node_from_substring(void)
 {
-  SerdNode* const a_b = serd_new_string(serd_substring("a\"bc", 3));
+  SerdNode* const a_b = serd_new_string(NULL, serd_substring("a\"bc", 3));
   assert(serd_node_length(a_b) == 3);
   assert(!serd_node_flags(a_b));
   assert(strlen(serd_node_string(a_b)) == 3);
   assert(!strncmp(serd_node_string(a_b), "a\"b", 3));
-  serd_node_free(a_b);
+  serd_node_free(NULL, a_b);
 }
 
 static void
 check_copy_equals(const SerdNode* const node)
 {
-  SerdNode* const copy = serd_node_copy(node);
+  SerdNode* const copy = serd_node_copy(NULL, node);
 
   assert(serd_node_equals(node, copy));
 
-  serd_node_free(copy);
+  serd_node_free(NULL, copy);
 }
 
 static void
@@ -466,35 +471,46 @@ test_literal(void)
   const SerdStringView hello_str = serd_string("hello");
   const SerdStringView empty_str = serd_empty_string();
 
-  assert(!serd_new_literal(
-    hello_str, SERD_HAS_DATATYPE | SERD_HAS_LANGUAGE, serd_string("whatever")));
+  assert(!serd_new_literal(NULL,
+                           hello_str,
+                           SERD_HAS_DATATYPE | SERD_HAS_LANGUAGE,
+                           serd_string("whatever")));
 
-  assert(!serd_new_literal(hello_str, SERD_HAS_DATATYPE, empty_str));
-  assert(!serd_new_literal(hello_str, SERD_HAS_LANGUAGE, empty_str));
+  assert(!serd_new_literal(NULL, hello_str, SERD_HAS_DATATYPE, empty_str));
+  assert(!serd_new_literal(NULL, hello_str, SERD_HAS_LANGUAGE, empty_str));
 
-  assert(!serd_new_literal(hello_str, SERD_HAS_DATATYPE, serd_string("Type")));
-  assert(!serd_new_literal(hello_str, SERD_HAS_DATATYPE, serd_string("de")));
+  assert(
+    !serd_new_literal(NULL, hello_str, SERD_HAS_DATATYPE, serd_string("Type")));
+  assert(
+    !serd_new_literal(NULL, hello_str, SERD_HAS_DATATYPE, serd_string("de")));
 
-  assert(!serd_new_literal(hello_str, SERD_HAS_LANGUAGE, serd_string("3n")));
-  assert(!serd_new_literal(hello_str, SERD_HAS_LANGUAGE, serd_string("d3")));
-  assert(!serd_new_literal(hello_str, SERD_HAS_LANGUAGE, serd_string("d3")));
-  assert(!serd_new_literal(hello_str, SERD_HAS_LANGUAGE, serd_string("en-!")));
+  assert(
+    !serd_new_literal(NULL, hello_str, SERD_HAS_LANGUAGE, serd_string("3n")));
+  assert(
+    !serd_new_literal(NULL, hello_str, SERD_HAS_LANGUAGE, serd_string("d3")));
+  assert(
+    !serd_new_literal(NULL, hello_str, SERD_HAS_LANGUAGE, serd_string("d3")));
+  assert(
+    !serd_new_literal(NULL, hello_str, SERD_HAS_LANGUAGE, serd_string("en-!")));
 
-  SerdNode* hello2 = serd_new_string(serd_string("hello\""));
+  SerdNode* hello2 = serd_new_string(NULL, serd_string("hello\""));
 
   assert(serd_node_length(hello2) == 6 &&
          !strcmp(serd_node_string(hello2), "hello\""));
 
   check_copy_equals(hello2);
 
-  assert(!serd_new_literal(
-    serd_string("plain"), SERD_HAS_DATATYPE, serd_string(NS_RDF "langString")));
+  assert(!serd_new_literal(NULL,
+                           serd_string("plain"),
+                           SERD_HAS_DATATYPE,
+                           serd_string(NS_RDF "langString")));
 
-  serd_node_free(hello2);
+  serd_node_free(NULL, hello2);
 
   const char* lang_lit_str = "\"Hello\"@en-ca";
   SerdNode*   sliced_lang_lit =
-    serd_new_literal(serd_substring(lang_lit_str + 1, 5),
+    serd_new_literal(NULL,
+                     serd_substring(lang_lit_str + 1, 5),
                      SERD_HAS_LANGUAGE,
                      serd_substring(lang_lit_str + 8, 5));
 
@@ -504,11 +520,12 @@ test_literal(void)
   assert(lang);
   assert(!strcmp(serd_node_string(lang), "en-ca"));
   check_copy_equals(sliced_lang_lit);
-  serd_node_free(sliced_lang_lit);
+  serd_node_free(NULL, sliced_lang_lit);
 
   const char* type_lit_str = "\"Hallo\"^^<http://example.org/Greeting>";
   SerdNode*   sliced_type_lit =
-    serd_new_literal(serd_substring(type_lit_str + 1, 5),
+    serd_new_literal(NULL,
+                     serd_substring(type_lit_str + 1, 5),
                      SERD_HAS_DATATYPE,
                      serd_substring(type_lit_str + 10, 27));
 
@@ -517,53 +534,56 @@ test_literal(void)
   const SerdNode* const datatype = serd_node_datatype(sliced_type_lit);
   assert(datatype);
   assert(!strcmp(serd_node_string(datatype), "http://example.org/Greeting"));
-  serd_node_free(sliced_type_lit);
+  serd_node_free(NULL, sliced_type_lit);
 }
 
 static void
 test_blank(void)
 {
-  SerdNode* blank = serd_new_blank(serd_string("b0"));
+  SerdNode* blank = serd_new_blank(NULL, serd_string("b0"));
   assert(serd_node_length(blank) == 2);
   assert(serd_node_flags(blank) == 0);
   assert(!strcmp(serd_node_string(blank), "b0"));
-  serd_node_free(blank);
+  serd_node_free(NULL, blank);
 }
 
 static void
 test_compare(void)
 {
   SerdNode* xsd_short =
-    serd_new_uri(serd_string("http://www.w3.org/2001/XMLSchema#short"));
+    serd_new_uri(NULL, serd_string("http://www.w3.org/2001/XMLSchema#short"));
 
-  SerdNode* angst = serd_new_string(serd_string("angst"));
+  SerdNode* angst = serd_new_string(NULL, serd_string("angst"));
 
   SerdNode* angst_de = serd_new_literal(
-    serd_string("angst"), SERD_HAS_LANGUAGE, serd_string("de"));
+    NULL, serd_string("angst"), SERD_HAS_LANGUAGE, serd_string("de"));
 
   assert(angst_de);
   SerdNode* angst_en = serd_new_literal(
-    serd_string("angst"), SERD_HAS_LANGUAGE, serd_string("en"));
+    NULL, serd_string("angst"), SERD_HAS_LANGUAGE, serd_string("en"));
 
   SerdNode* hallo = serd_new_literal(
-    serd_string("Hallo"), SERD_HAS_LANGUAGE, serd_string("de"));
+    NULL, serd_string("Hallo"), SERD_HAS_LANGUAGE, serd_string("de"));
 
-  SerdNode* hello    = serd_new_string(serd_string("Hello"));
-  SerdNode* universe = serd_new_string(serd_string("Universe"));
-  SerdNode* integer  = serd_new_integer(4);
-  SerdNode* blank    = serd_new_blank(serd_string("b1"));
-  SerdNode* uri      = serd_new_uri(serd_string("http://example.org/"));
+  SerdNode* hello    = serd_new_string(NULL, serd_string("Hello"));
+  SerdNode* universe = serd_new_string(NULL, serd_string("Universe"));
+  SerdNode* integer  = serd_new_integer(NULL, 4);
+  SerdNode* blank    = serd_new_blank(NULL, serd_string("b1"));
+  SerdNode* uri      = serd_new_uri(NULL, serd_string("http://example.org/"));
 
   SerdNode* aardvark =
-    serd_new_literal(serd_string("alex"),
+    serd_new_literal(NULL,
+                     serd_string("alex"),
                      SERD_HAS_DATATYPE,
                      serd_string("http://example.org/Aardvark"));
 
-  SerdNode* badger = serd_new_literal(serd_string("bobby"),
+  SerdNode* badger = serd_new_literal(NULL,
+                                      serd_string("bobby"),
                                       SERD_HAS_DATATYPE,
                                       serd_string("http://example.org/Badger"));
 
   // Types are ordered according to their SerdNodeType (more or less arbitrary)
+  assert(serd_node_compare(integer, hello) < 0);
   assert(serd_node_compare(hello, uri) < 0);
   assert(serd_node_compare(uri, blank) < 0);
 
@@ -575,18 +595,18 @@ test_compare(void)
   assert(serd_node_compare(angst_de, angst_en) < 0);
   assert(serd_node_compare(aardvark, badger) < 0);
 
-  serd_node_free(uri);
-  serd_node_free(blank);
-  serd_node_free(integer);
-  serd_node_free(badger);
-  serd_node_free(aardvark);
-  serd_node_free(universe);
-  serd_node_free(hello);
-  serd_node_free(hallo);
-  serd_node_free(angst_en);
-  serd_node_free(angst_de);
-  serd_node_free(angst);
-  serd_node_free(xsd_short);
+  serd_node_free(NULL, uri);
+  serd_node_free(NULL, blank);
+  serd_node_free(NULL, integer);
+  serd_node_free(NULL, badger);
+  serd_node_free(NULL, aardvark);
+  serd_node_free(NULL, universe);
+  serd_node_free(NULL, hello);
+  serd_node_free(NULL, hallo);
+  serd_node_free(NULL, angst_en);
+  serd_node_free(NULL, angst_de);
+  serd_node_free(NULL, angst);
+  serd_node_free(NULL, xsd_short);
 }
 
 int
diff --git a/test/test_overflow.c b/test/test_overflow.c
index 6272e807..7b1693a8 100644
--- a/test/test_overflow.c
+++ b/test/test_overflow.c
@@ -22,14 +22,14 @@ test_size(SerdWorld* const      world,
   limits.reader_stack_size = stack_size;
   serd_world_set_limits(world, limits);
 
-  SerdSink*         sink   = serd_sink_new(NULL, NULL, NULL);
-  SerdEnv* const    env    = serd_env_new(serd_empty_string());
+  SerdSink*         sink   = serd_sink_new(NULL, NULL, NULL, NULL);
+  SerdEnv* const    env    = serd_env_new(NULL, serd_empty_string());
   SerdReader* const reader = serd_reader_new(world, syntax, flags, env, sink);
   if (!reader) {
     return SERD_BAD_STACK;
   }
 
-  SerdNode*       string_name = serd_new_string(serd_string("string"));
+  SerdNode*       string_name = serd_new_string(NULL, serd_string("string"));
   const char*     position    = str;
   SerdInputStream in          = serd_open_input_string(&position);
   serd_reader_start(reader, &in, string_name, 1);
@@ -37,7 +37,7 @@ test_size(SerdWorld* const      world,
   const SerdStatus st = serd_reader_read_document(reader);
 
   serd_close_input(&in);
-  serd_node_free(string_name);
+  serd_node_free(NULL, string_name);
   serd_reader_free(reader);
   serd_env_free(env);
   serd_sink_free(sink);
@@ -76,7 +76,7 @@ test_ntriples_overflow(void)
     NULL,
   };
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
 
   for (const char* const* t = test_strings; *t; ++t) {
     test_all_sizes(world, *t, SERD_NTRIPLES, 0U);
@@ -202,7 +202,7 @@ test_turtle_overflow(void)
     NULL,
   };
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
 
   for (const char* const* t = test_strings; *t; ++t) {
     test_all_sizes(world, *t, SERD_TURTLE, SERD_READ_VARIABLES);
diff --git a/test/test_reader.c b/test/test_reader.c
index f1ec1d35..a0eaee5c 100644
--- a/test/test_reader.c
+++ b/test/test_reader.c
@@ -3,6 +3,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/caret.h"
 #include "serd/env.h"
 #include "serd/event.h"
@@ -60,6 +62,81 @@ test_sink(void* handle, const SerdEvent* event)
   return SERD_SUCCESS;
 }
 
+static void
+test_new_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const world   = serd_world_new(&allocator.base);
+  SerdEnv* const   env     = serd_env_new(&allocator.base, serd_empty_string());
+  size_t           ignored = 0U;
+  SerdSink* const  sink =
+    serd_sink_new(&allocator.base, &ignored, test_sink, NULL);
+
+  // Successfully allocate a reader to count the number of allocations
+  const size_t n_world_allocs = allocator.n_allocations;
+  SerdReader*  reader = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
+  assert(reader);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations - n_world_allocs;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_reader_new(world, SERD_TURTLE, 0U, env, sink));
+  }
+
+  serd_reader_free(reader);
+  serd_env_free(env);
+  serd_sink_free(sink);
+  serd_world_free(world);
+}
+
+static void
+test_start_failed_alloc(const char* const path)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  FILE* const f = fopen(path, "w+b");
+  assert(f);
+
+  fprintf(f, "_:s <http://example.org/p> _:o .\n");
+  fflush(f);
+  fseek(f, 0L, SEEK_SET);
+
+  SerdWorld*  world   = serd_world_new(&allocator.base);
+  SerdEnv*    env     = serd_env_new(&allocator.base, serd_empty_string());
+  size_t      ignored = 0U;
+  SerdSink*   sink = serd_sink_new(&allocator.base, &ignored, test_sink, NULL);
+  SerdReader* reader = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
+  assert(reader);
+
+  SerdInputStream in =
+    serd_open_input_stream((SerdReadFunc)fread, (SerdErrorFunc)ferror, NULL, f);
+
+  // Successfully start a new read to count the number of allocations
+  const size_t n_setup_allocs = allocator.n_allocations;
+  assert(serd_reader_start(reader, &in, NULL, 4096) == SERD_SUCCESS);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations - n_setup_allocs;
+  assert(!serd_reader_finish(reader));
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    in = serd_open_input_stream(
+      (SerdReadFunc)fread, (SerdErrorFunc)ferror, NULL, f);
+
+    SerdStatus st = serd_reader_start(reader, &in, NULL, 4096);
+    assert(st == SERD_BAD_ALLOC);
+  }
+
+  serd_reader_free(reader);
+  serd_env_free(env);
+  serd_sink_free(sink);
+  serd_world_free(world);
+  fclose(f);
+}
+
 ZIX_PURE_FUNC static size_t
 prepare_test_read(void* buf, size_t size, size_t nmemb, void* stream)
 {
@@ -84,7 +161,7 @@ prepare_test_error(void* stream)
 static void
 test_prepare_error(const char* const path)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   ReaderTest       rt    = {0, 0, 0, 0};
 
   FILE* const f = fopen(path, "w+b");
@@ -94,12 +171,11 @@ test_prepare_error(const char* const path)
   fflush(f);
   fseek(f, 0L, SEEK_SET);
 
-  SerdSink* const sink = serd_sink_new(&rt, test_sink, NULL);
+  SerdSink* const sink = serd_sink_new(NULL, &rt, test_sink, NULL);
   assert(sink);
 
-  SerdEnv* const    env    = serd_env_new(serd_empty_string());
+  SerdEnv* const    env    = serd_env_new(NULL, serd_empty_string());
   SerdReader* const reader = serd_reader_new(world, SERD_TURTLE, 0, env, sink);
-
   assert(reader);
 
   SerdInputStream in =
@@ -124,14 +200,13 @@ test_prepare_error(const char* const path)
 static void
 test_read_string(void)
 {
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   ReaderTest rt    = {0, 0, 0, 0};
-  SerdSink*  sink  = serd_sink_new(&rt, test_sink, NULL);
+  SerdSink*  sink  = serd_sink_new(NULL, &rt, test_sink, NULL);
   assert(sink);
 
-  SerdEnv* const    env    = serd_env_new(serd_empty_string());
+  SerdEnv* const    env    = serd_env_new(NULL, serd_empty_string());
   SerdReader* const reader = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
-
   assert(reader);
 
   static const char* const string1 =
@@ -228,11 +303,12 @@ test_read_eof_by_page(const char* const path)
   fflush(f);
   fseek(f, 0L, SEEK_SET);
 
-  SerdWorld*      world   = serd_world_new();
-  ReaderTest      ignored = {0, 0, 0, 0};
-  SerdSink*       sink    = serd_sink_new(&ignored, test_sink, NULL);
-  SerdEnv*        env     = serd_env_new(serd_empty_string());
-  SerdReader*     reader  = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
+  SerdWorld* const world  = serd_world_new(NULL);
+  ReaderTest       rt     = {0, 0, 0, 0};
+  SerdSink* const  sink   = serd_sink_new(NULL, &rt, test_sink, NULL);
+  SerdEnv* const   env    = serd_env_new(NULL, serd_empty_string());
+  SerdReader*      reader = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
+
   SerdInputStream in =
     serd_open_input_stream((SerdReadFunc)fread, (SerdErrorFunc)ferror, NULL, f);
 
@@ -255,11 +331,11 @@ test_read_eof_by_page(const char* const path)
 static void
 test_read_eof_by_byte(void)
 {
-  SerdWorld*  world   = serd_world_new();
-  ReaderTest  ignored = {0, 0, 0, 0};
-  SerdSink*   sink    = serd_sink_new(&ignored, test_sink, NULL);
-  SerdEnv*    env     = serd_env_new(serd_empty_string());
-  SerdReader* reader  = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
+  SerdWorld* const world  = serd_world_new(NULL);
+  ReaderTest       rt     = {0, 0, 0, 0};
+  SerdSink* const  sink   = serd_sink_new(NULL, &rt, test_sink, NULL);
+  SerdEnv* const   env    = serd_env_new(NULL, serd_empty_string());
+  SerdReader*      reader = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
 
   size_t          n_reads = 0U;
   SerdInputStream in      = serd_open_input_stream(
@@ -305,12 +381,12 @@ test_read_nquads_chunks(const char* const path)
 
   fseek(f, 0, SEEK_SET);
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   ReaderTest       rt    = {0, 0, 0, 0};
-  SerdSink* const  sink  = serd_sink_new(&rt, test_sink, NULL);
+  SerdSink* const  sink  = serd_sink_new(NULL, &rt, test_sink, NULL);
   assert(sink);
 
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
   assert(env);
 
   SerdReader* const reader = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
@@ -391,12 +467,12 @@ test_read_turtle_chunks(const char* const path)
   fwrite(&null, sizeof(null), 1, f);
   fseek(f, 0, SEEK_SET);
 
-  SerdWorld* world = serd_world_new();
-  ReaderTest rt    = {0, 0, 0, 0};
-  SerdSink*  sink  = serd_sink_new(&rt, test_sink, NULL);
+  SerdWorld* const world = serd_world_new(NULL);
+  ReaderTest       rt    = {0, 0, 0, 0};
+  SerdSink* const  sink  = serd_sink_new(NULL, &rt, test_sink, NULL);
   assert(sink);
 
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
   assert(env);
 
   SerdReader* const reader = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
@@ -479,13 +555,13 @@ test_read_turtle_chunks(const char* const path)
 static void
 test_read_empty(const char* const path)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   ReaderTest       rt    = {0, 0, 0, 0};
 
-  SerdSink* const sink = serd_sink_new(&rt, test_sink, NULL);
+  SerdSink* const sink = serd_sink_new(NULL, &rt, test_sink, NULL);
   assert(sink);
 
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
   assert(env);
 
   SerdReader* const reader =
@@ -536,10 +612,10 @@ check_cursor(void* handle, const SerdEvent* event)
 static void
 test_error_cursor(void)
 {
-  SerdWorld*        world  = serd_world_new();
+  SerdWorld* const  world  = serd_world_new(NULL);
   bool              called = false;
-  SerdSink*         sink   = serd_sink_new(&called, check_cursor, NULL);
-  SerdEnv* const    env    = serd_env_new(serd_empty_string());
+  SerdSink* const   sink   = serd_sink_new(NULL, &called, check_cursor, NULL);
+  SerdEnv* const    env    = serd_env_new(NULL, serd_empty_string());
   SerdReader* const reader = serd_reader_new(world, SERD_TURTLE, 0U, env, sink);
   assert(sink);
   assert(reader);
@@ -548,7 +624,7 @@ test_error_cursor(void)
     "<http://example.org/s> <http://example.org/p> "
     "<http://example.org/o> .";
 
-  SerdNode* const string_name = serd_new_string(serd_string("string"));
+  SerdNode* const string_name = serd_new_string(NULL, serd_string("string"));
   const char*     position    = string;
   SerdInputStream in          = serd_open_input_string(&position);
 
@@ -559,7 +635,7 @@ test_error_cursor(void)
   assert(called);
   assert(!serd_close_input(&in));
 
-  serd_node_free(string_name);
+  serd_node_free(NULL, string_name);
   serd_reader_free(reader);
   serd_env_free(env);
   serd_sink_free(sink);
@@ -575,6 +651,8 @@ main(void)
   char* const ttl_path     = zix_path_join(NULL, dir, "serd_test_reader.ttl");
   char* const nq_path      = zix_path_join(NULL, dir, "serd_test_reader.nq");
 
+  test_new_failed_alloc();
+  test_start_failed_alloc(ttl_path);
   test_read_nquads_chunks(nq_path);
   test_read_turtle_chunks(ttl_path);
   test_prepare_error(ttl_path);
diff --git a/test/test_reader_writer.c b/test/test_reader_writer.c
index 55c4b584..d6a2675d 100644
--- a/test/test_reader_writer.c
+++ b/test/test_reader_writer.c
@@ -97,7 +97,7 @@ faulty_sink(const void* const buf,
 static void
 test_write_errors(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   ErrorContext     ctx   = {0U, 0U};
 
   const size_t max_offsets[] = {0, 368, 1900, 1992, 413};
@@ -109,7 +109,7 @@ test_write_errors(void)
       ctx.n_written    = 0;
       ctx.error_offset = o;
 
-      SerdEnv* const   env = serd_env_new(serd_empty_string());
+      SerdEnv* const   env = serd_env_new(NULL, serd_empty_string());
       SerdOutputStream out =
         serd_open_output_stream(faulty_sink, NULL, NULL, &ctx);
 
@@ -141,8 +141,8 @@ test_write_errors(void)
 static void
 test_writer(const char* const path)
 {
-  SerdWorld* world = serd_world_new();
-  SerdEnv*   env   = serd_env_new(serd_empty_string());
+  SerdWorld* world = serd_world_new(NULL);
+  SerdEnv*   env   = serd_env_new(NULL, serd_empty_string());
 
   SerdOutputStream output = serd_open_output_file(path);
 
@@ -154,7 +154,7 @@ test_writer(const char* const path)
   serd_writer_chop_blank_prefix(writer, "tmp");
   serd_writer_chop_blank_prefix(writer, NULL);
 
-  SerdNode* lit = serd_new_string(serd_string("hello"));
+  SerdNode* lit = serd_new_string(NULL, serd_string("hello"));
 
   const SerdSink* const iface = serd_writer_sink(writer);
   assert(serd_sink_write_base(iface, lit));
@@ -164,9 +164,9 @@ test_writer(const char* const path)
   static const uint8_t bad_buf[]    = {0xEF, 0xBF, 0xBD, 0};
   const SerdStringView bad_buf_view = {(const char*)bad_buf, 3};
 
-  SerdNode* s   = serd_new_uri(serd_string("http://example.org"));
-  SerdNode* p   = serd_new_uri(serd_string("http://example.org/pred"));
-  SerdNode* bad = serd_new_string(bad_buf_view);
+  SerdNode* s   = serd_new_uri(NULL, serd_string("http://example.org"));
+  SerdNode* p   = serd_new_uri(NULL, serd_string("http://example.org/pred"));
+  SerdNode* bad = serd_new_string(NULL, bad_buf_view);
 
   // Write 3 invalid statements (should write nothing)
   const SerdNode* junk[][3] = {{s, bad, bad}, {bad, p, bad}, {s, bad, p}};
@@ -174,17 +174,18 @@ test_writer(const char* const path)
     assert(serd_sink_write(iface, 0, junk[i][0], junk[i][1], junk[i][2], NULL));
   }
 
-  serd_node_free(bad);
+  serd_node_free(NULL, bad);
 
   const SerdStringView urn_Type = serd_string("urn:Type");
   const SerdStringView en       = serd_string("en");
 
-  SerdNode* const o = serd_new_string(serd_string("o"));
+  SerdNode* const o = serd_new_string(NULL, serd_string("o"));
 
   SerdNode* const t =
-    serd_new_literal(serd_string("t"), SERD_HAS_DATATYPE, urn_Type);
+    serd_new_literal(NULL, serd_string("t"), SERD_HAS_DATATYPE, urn_Type);
 
-  SerdNode* const l = serd_new_literal(serd_string("l"), SERD_HAS_LANGUAGE, en);
+  SerdNode* const l =
+    serd_new_literal(NULL, serd_string("l"), SERD_HAS_LANGUAGE, en);
 
   const SerdNode* good[][3] = {{s, p, o}, {s, p, t}, {s, p, l}};
 
@@ -199,46 +200,47 @@ test_writer(const char* const path)
   static const char* const bad_uri_str   = (const char*)bad_uri_buf;
 
   // Write statements with bad UTF-8 (should be replaced)
-  SerdNode* bad_lit = serd_new_string(serd_string(bad_lit_str));
-  SerdNode* bad_uri = serd_new_uri(serd_string(bad_uri_str));
+  SerdNode* bad_lit = serd_new_string(NULL, serd_string(bad_lit_str));
+  SerdNode* bad_uri = serd_new_uri(NULL, serd_string(bad_uri_str));
   assert(!serd_sink_write(iface, 0, s, p, bad_lit, 0));
   assert(!serd_sink_write(iface, 0, s, p, bad_uri, 0));
-  serd_node_free(bad_uri);
-  serd_node_free(bad_lit);
+  serd_node_free(NULL, bad_uri);
+  serd_node_free(NULL, bad_lit);
 
   // Write 1 valid statement
-  SerdNode* const hello = serd_new_string(serd_string("hello"));
+  SerdNode* const hello = serd_new_string(NULL, serd_string("hello"));
   assert(!serd_sink_write(iface, 0, s, p, hello, 0));
-  serd_node_free(hello);
+  serd_node_free(NULL, hello);
 
   serd_writer_free(writer);
   serd_close_output(&output);
 
-  serd_node_free(lit);
-  serd_node_free(o);
-  serd_node_free(t);
-  serd_node_free(l);
+  serd_node_free(NULL, lit);
+  serd_node_free(NULL, o);
+  serd_node_free(NULL, t);
+  serd_node_free(NULL, l);
 
   // Test buffer sink
-  SerdBuffer      buffer = {NULL, 0};
-  SerdNode* const base   = serd_new_uri(serd_string("http://example.org/base"));
+  SerdBuffer      buffer = {NULL, NULL, 0};
+  SerdNode* const base =
+    serd_new_uri(NULL, serd_string("http://example.org/base"));
 
   output = serd_open_output_buffer(&buffer);
   writer = serd_writer_new(world, SERD_TURTLE, 0, env, &output, 1U);
 
   serd_sink_write_base(serd_writer_sink(writer), base);
 
-  serd_node_free(base);
+  serd_node_free(NULL, base);
   serd_writer_free(writer);
   serd_close_output(&output);
 
   char* const out = (char*)buffer.buf;
   assert(out);
   assert(!strcmp(out, "@base <http://example.org/base> .\n"));
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
-  serd_node_free(p);
-  serd_node_free(s);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
 
   serd_env_free(env);
   serd_world_free(world);
@@ -247,12 +249,12 @@ test_writer(const char* const path)
 static void
 test_reader(const char* path)
 {
-  SerdWorld*      world = serd_world_new();
-  ReaderTest      rt    = {0};
-  SerdSink* const sink  = serd_sink_new(&rt, test_sink, NULL);
+  SerdWorld* const world = serd_world_new(NULL);
+  ReaderTest       rt    = {0};
+  SerdSink* const  sink  = serd_sink_new(NULL, &rt, test_sink, NULL);
   assert(sink);
 
-  SerdEnv* const env = serd_env_new(serd_empty_string());
+  SerdEnv* const env = serd_env_new(NULL, serd_empty_string());
   assert(env);
 
   // Test that too little stack space fails gracefully
diff --git a/test/test_sink.c b/test/test_sink.c
index b0756fcc..9c7959de 100644
--- a/test/test_sink.c
+++ b/test/test_sink.c
@@ -1,8 +1,10 @@
-// Copyright 2019-2020 David Robillard <d@drobilla.net>
+// Copyright 2019-2021 David Robillard <d@drobilla.net>
 // SPDX-License-Identifier: ISC
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/env.h"
 #include "serd/event.h"
 #include "serd/node.h"
@@ -88,17 +90,36 @@ on_event(void* const handle, const SerdEvent* const event)
 }
 
 static void
+test_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  // Successfully allocate a sink to count the number of allocations
+  SerdSink* const sink = serd_sink_new(&allocator.base, NULL, NULL, NULL);
+  assert(sink);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_allocs = allocator.n_allocations;
+  for (size_t i = 0; i < n_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_sink_new(&allocator.base, NULL, NULL, NULL));
+  }
+
+  serd_sink_free(sink);
+}
+
+static void
 test_callbacks(void)
 {
-  SerdNode* const base  = serd_new_uri(serd_string(NS_EG));
-  SerdNode* const name  = serd_new_string(serd_string("eg"));
-  SerdNode* const uri   = serd_new_uri(serd_string(NS_EG "uri"));
-  SerdNode* const blank = serd_new_blank(serd_string("b1"));
-  SerdEnv*        env   = serd_env_new(serd_node_string_view(base));
+  SerdNode* const base  = serd_new_uri(NULL, serd_string(NS_EG));
+  SerdNode* const name  = serd_new_string(NULL, serd_string("eg"));
+  SerdNode* const uri   = serd_new_uri(NULL, serd_string(NS_EG "uri"));
+  SerdNode* const blank = serd_new_blank(NULL, serd_string("b1"));
+  SerdEnv*        env   = serd_env_new(NULL, serd_node_string_view(base));
   State           state = {0, 0, 0, 0, 0, SERD_SUCCESS};
 
   SerdStatement* const statement =
-    serd_statement_new(base, uri, blank, NULL, NULL);
+    serd_statement_new(NULL, base, uri, blank, NULL, NULL);
 
   const SerdBaseEvent      base_event      = {SERD_BASE, uri};
   const SerdPrefixEvent    prefix_event    = {SERD_PREFIX, name, uri};
@@ -107,7 +128,7 @@ test_callbacks(void)
 
   // Call functions on a sink with no functions set
 
-  SerdSink* null_sink = serd_sink_new(&state, NULL, NULL);
+  SerdSink* null_sink = serd_sink_new(NULL, &state, NULL, NULL);
 
   assert(!serd_sink_write_base(null_sink, base));
   assert(!serd_sink_write_prefix(null_sink, name, uri));
@@ -130,7 +151,7 @@ test_callbacks(void)
 
   // Try again with a sink that has the event handler set
 
-  SerdSink* sink = serd_sink_new(&state, on_event, NULL);
+  SerdSink* sink = serd_sink_new(NULL, &state, on_event, NULL);
 
   assert(!serd_sink_write_base(sink, base));
   assert(serd_node_equals(state.last_base, base));
@@ -150,12 +171,12 @@ test_callbacks(void)
 
   serd_sink_free(sink);
 
-  serd_statement_free(statement);
+  serd_statement_free(NULL, statement);
   serd_env_free(env);
-  serd_node_free(blank);
-  serd_node_free(uri);
-  serd_node_free(name);
-  serd_node_free(base);
+  serd_node_free(NULL, blank);
+  serd_node_free(NULL, uri);
+  serd_node_free(NULL, name);
+  serd_node_free(NULL, base);
 }
 
 static void
@@ -166,7 +187,7 @@ test_free(void)
 
   // Set up a sink with dynamically allocated data and a free function
   uintptr_t* data = (uintptr_t*)calloc(1, sizeof(uintptr_t));
-  SerdSink*  sink = serd_sink_new(data, NULL, free);
+  SerdSink*  sink = serd_sink_new(NULL, data, NULL, free);
 
   // Free the sink, which should free the data (rely on valgrind or sanitizers)
   serd_sink_free(sink);
@@ -175,6 +196,7 @@ test_free(void)
 int
 main(void)
 {
+  test_failed_alloc();
   test_callbacks();
   test_free();
   return 0;
diff --git a/test/test_statement.c b/test/test_statement.c
index d70542f1..0127b7bf 100644
--- a/test/test_statement.c
+++ b/test/test_statement.c
@@ -16,67 +16,67 @@
 static void
 test_new(void)
 {
-  SerdNode* const u = serd_new_uri(serd_string(NS_EG "s"));
-  SerdNode* const b = serd_new_blank(serd_string("b0"));
-  SerdNode* const l = serd_new_string(serd_string("str"));
-
-  assert(!serd_statement_new(u, b, u, NULL, NULL));
-  assert(!serd_statement_new(l, u, u, NULL, NULL));
-  assert(!serd_statement_new(l, u, b, u, NULL));
-  assert(!serd_statement_new(u, l, b, NULL, NULL));
-  assert(!serd_statement_new(u, l, b, u, NULL));
-  assert(!serd_statement_new(u, u, u, l, NULL));
-
-  serd_node_free(l);
-  serd_node_free(b);
-  serd_node_free(u);
+  SerdNode* const u = serd_new_uri(NULL, serd_string(NS_EG "s"));
+  SerdNode* const b = serd_new_blank(NULL, serd_string("b0"));
+  SerdNode* const l = serd_new_string(NULL, serd_string("str"));
+
+  assert(!serd_statement_new(NULL, u, b, u, NULL, NULL));
+  assert(!serd_statement_new(NULL, l, u, u, NULL, NULL));
+  assert(!serd_statement_new(NULL, l, u, b, u, NULL));
+  assert(!serd_statement_new(NULL, u, l, b, NULL, NULL));
+  assert(!serd_statement_new(NULL, u, l, b, u, NULL));
+  assert(!serd_statement_new(NULL, u, u, u, l, NULL));
+
+  serd_node_free(NULL, l);
+  serd_node_free(NULL, b);
+  serd_node_free(NULL, u);
 }
 
 static void
 test_copy(void)
 {
-  assert(!serd_statement_copy(NULL));
+  assert(!serd_statement_copy(NULL, NULL));
 
-  SerdNode* const f = serd_new_string(serd_string("file"));
-  SerdNode* const s = serd_new_uri(serd_string(NS_EG "s"));
-  SerdNode* const p = serd_new_uri(serd_string(NS_EG "p"));
-  SerdNode* const o = serd_new_uri(serd_string(NS_EG "o"));
-  SerdNode* const g = serd_new_uri(serd_string(NS_EG "g"));
+  SerdNode* const f = serd_new_string(NULL, serd_string("file"));
+  SerdNode* const s = serd_new_uri(NULL, serd_string(NS_EG "s"));
+  SerdNode* const p = serd_new_uri(NULL, serd_string(NS_EG "p"));
+  SerdNode* const o = serd_new_uri(NULL, serd_string(NS_EG "o"));
+  SerdNode* const g = serd_new_uri(NULL, serd_string(NS_EG "g"));
 
-  SerdCaret* const     caret     = serd_caret_new(f, 1, 1);
-  SerdStatement* const statement = serd_statement_new(s, p, o, g, caret);
-  SerdStatement* const copy      = serd_statement_copy(statement);
+  SerdCaret* const     caret     = serd_caret_new(NULL, f, 1, 1);
+  SerdStatement* const statement = serd_statement_new(NULL, s, p, o, g, caret);
+  SerdStatement* const copy      = serd_statement_copy(NULL, statement);
 
   assert(serd_statement_equals(copy, statement));
   assert(serd_caret_equals(serd_statement_caret(copy), caret));
 
-  serd_statement_free(copy);
-  serd_caret_free(caret);
-  serd_statement_free(statement);
-  serd_node_free(g);
-  serd_node_free(o);
-  serd_node_free(p);
-  serd_node_free(s);
-  serd_node_free(f);
+  serd_statement_free(NULL, copy);
+  serd_caret_free(NULL, caret);
+  serd_statement_free(NULL, statement);
+  serd_node_free(NULL, g);
+  serd_node_free(NULL, o);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
+  serd_node_free(NULL, f);
 }
 
 static void
 test_free(void)
 {
-  serd_statement_free(NULL);
+  serd_statement_free(NULL, NULL);
 }
 
 static void
 test_fields(void)
 {
-  SerdNode* const f = serd_new_string(serd_string("file"));
-  SerdNode* const s = serd_new_uri(serd_string(NS_EG "s"));
-  SerdNode* const p = serd_new_uri(serd_string(NS_EG "p"));
-  SerdNode* const o = serd_new_uri(serd_string(NS_EG "o"));
-  SerdNode* const g = serd_new_uri(serd_string(NS_EG "g"));
+  SerdNode* const f = serd_new_string(NULL, serd_string("file"));
+  SerdNode* const s = serd_new_uri(NULL, serd_string(NS_EG "s"));
+  SerdNode* const p = serd_new_uri(NULL, serd_string(NS_EG "p"));
+  SerdNode* const o = serd_new_uri(NULL, serd_string(NS_EG "o"));
+  SerdNode* const g = serd_new_uri(NULL, serd_string(NS_EG "g"));
 
-  SerdCaret* const     caret     = serd_caret_new(f, 1, 1);
-  SerdStatement* const statement = serd_statement_new(s, p, o, g, caret);
+  SerdCaret* const     caret     = serd_caret_new(NULL, f, 1, 1);
+  SerdStatement* const statement = serd_statement_new(NULL, s, p, o, g, caret);
 
   assert(serd_statement_equals(statement, statement));
   assert(!serd_statement_equals(statement, NULL));
@@ -103,29 +103,29 @@ test_fields(void)
   assert(!serd_statement_matches(statement, NULL, NULL, s, NULL));
   assert(!serd_statement_matches(statement, NULL, NULL, NULL, s));
 
-  SerdStatement* const diff_s = serd_statement_new(o, p, o, g, caret);
+  SerdStatement* const diff_s = serd_statement_new(NULL, o, p, o, g, caret);
   assert(!serd_statement_equals(statement, diff_s));
-  serd_statement_free(diff_s);
+  serd_statement_free(NULL, diff_s);
 
-  SerdStatement* const diff_p = serd_statement_new(s, o, o, g, caret);
+  SerdStatement* const diff_p = serd_statement_new(NULL, s, o, o, g, caret);
   assert(!serd_statement_equals(statement, diff_p));
-  serd_statement_free(diff_p);
+  serd_statement_free(NULL, diff_p);
 
-  SerdStatement* const diff_o = serd_statement_new(s, p, s, g, caret);
+  SerdStatement* const diff_o = serd_statement_new(NULL, s, p, s, g, caret);
   assert(!serd_statement_equals(statement, diff_o));
-  serd_statement_free(diff_o);
+  serd_statement_free(NULL, diff_o);
 
-  SerdStatement* const diff_g = serd_statement_new(s, p, o, s, caret);
+  SerdStatement* const diff_g = serd_statement_new(NULL, s, p, o, s, caret);
   assert(!serd_statement_equals(statement, diff_g));
-  serd_statement_free(diff_g);
-
-  serd_statement_free(statement);
-  serd_caret_free(caret);
-  serd_node_free(g);
-  serd_node_free(o);
-  serd_node_free(p);
-  serd_node_free(s);
-  serd_node_free(f);
+  serd_statement_free(NULL, diff_g);
+
+  serd_statement_free(NULL, statement);
+  serd_caret_free(NULL, caret);
+  serd_node_free(NULL, g);
+  serd_node_free(NULL, o);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
+  serd_node_free(NULL, f);
 }
 
 int
diff --git a/test/test_terse_write.c b/test/test_terse_write.c
index 39e3767a..0bdb0280 100644
--- a/test/test_terse_write.c
+++ b/test/test_terse_write.c
@@ -5,6 +5,7 @@
 
 #include "serd/buffer.h"
 #include "serd/env.h"
+#include "serd/memory.h"
 #include "serd/node.h"
 #include "serd/output_stream.h"
 #include "serd/sink.h"
@@ -16,7 +17,6 @@
 
 #include <assert.h>
 #include <stdio.h>
-#include <stdlib.h>
 #include <string.h>
 
 #define NS_RDF "http://www.w3.org/1999/02/22-rdf-syntax-ns#"
@@ -39,20 +39,20 @@ check_output(SerdWriter* writer, SerdBuffer* buffer, const char* expected)
 static int
 test(void)
 {
-  SerdBuffer buffer = {NULL, 0};
-  SerdWorld* world  = serd_world_new();
-  SerdEnv*   env    = serd_env_new(serd_empty_string());
+  SerdBuffer buffer = {NULL, NULL, 0};
+  SerdWorld* world  = serd_world_new(NULL);
+  SerdEnv*   env    = serd_env_new(NULL, serd_empty_string());
 
-  SerdNode* b1 = serd_new_blank(serd_string("b1"));
-  SerdNode* l1 = serd_new_blank(serd_string("l1"));
-  SerdNode* l2 = serd_new_blank(serd_string("l2"));
-  SerdNode* s1 = serd_new_string(serd_string("s1"));
-  SerdNode* s2 = serd_new_string(serd_string("s2"));
+  SerdNode* b1 = serd_new_blank(NULL, serd_string("b1"));
+  SerdNode* l1 = serd_new_blank(NULL, serd_string("l1"));
+  SerdNode* l2 = serd_new_blank(NULL, serd_string("l2"));
+  SerdNode* s1 = serd_new_string(NULL, serd_string("s1"));
+  SerdNode* s2 = serd_new_string(NULL, serd_string("s2"));
 
-  SerdNode* rdf_first = serd_new_uri(serd_string(NS_RDF "first"));
-  SerdNode* rdf_value = serd_new_uri(serd_string(NS_RDF "value"));
-  SerdNode* rdf_rest  = serd_new_uri(serd_string(NS_RDF "rest"));
-  SerdNode* rdf_nil   = serd_new_uri(serd_string(NS_RDF "nil"));
+  SerdNode* rdf_first = serd_new_uri(NULL, serd_string(NS_RDF "first"));
+  SerdNode* rdf_value = serd_new_uri(NULL, serd_string(NS_RDF "value"));
+  SerdNode* rdf_rest  = serd_new_uri(NULL, serd_string(NS_RDF "rest"));
+  SerdNode* rdf_nil   = serd_new_uri(NULL, serd_string(NS_RDF "nil"));
 
   serd_env_set_prefix(env, serd_string("rdf"), serd_string(NS_RDF));
 
@@ -91,19 +91,19 @@ test(void)
   check_output(writer, &buffer, "[] rdf:value ( \"s1\" \"s2\" ) .\n");
 
   serd_writer_free(writer);
-  serd_node_free(rdf_nil);
-  serd_node_free(rdf_rest);
-  serd_node_free(rdf_value);
-  serd_node_free(rdf_first);
-  serd_node_free(s2);
-  serd_node_free(s1);
-  serd_node_free(l2);
-  serd_node_free(l1);
-  serd_node_free(b1);
+  serd_node_free(NULL, rdf_nil);
+  serd_node_free(NULL, rdf_rest);
+  serd_node_free(NULL, rdf_value);
+  serd_node_free(NULL, rdf_first);
+  serd_node_free(NULL, s2);
+  serd_node_free(NULL, s1);
+  serd_node_free(NULL, l2);
+  serd_node_free(NULL, l1);
+  serd_node_free(NULL, b1);
   serd_close_output(&output);
+  serd_free(NULL, buffer.buf);
   serd_env_free(env);
   serd_world_free(world);
-  free(buffer.buf);
 
   return 0;
 }
diff --git a/test/test_uri.c b/test/test_uri.c
index 74b732fd..79d3f73e 100644
--- a/test/test_uri.c
+++ b/test/test_uri.c
@@ -3,6 +3,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/memory.h"
 #include "serd/node.h"
 #include "serd/string_view.h"
@@ -14,6 +16,35 @@
 #include <string.h>
 
 static void
+test_file_uri_failed_alloc(void)
+{
+  static const char* const string = "file://host/path/spacey%20dir/100%%.ttl";
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  // Successfully parse a URI to count the number of allocations
+  char* hostname = NULL;
+  char* path     = serd_parse_file_uri(&allocator.base, string, &hostname);
+
+  assert(!strcmp(path, "/path/spacey dir/100%.ttl"));
+  assert(!strcmp(hostname, "host"));
+  serd_free(&allocator.base, path);
+  serd_free(&allocator.base, hostname);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_allocs = allocator.n_allocations;
+  for (size_t i = 0; i < n_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    path = serd_parse_file_uri(&allocator.base, string, &hostname);
+    assert(!path || !hostname);
+
+    serd_free(&allocator.base, path);
+    serd_free(&allocator.base, hostname);
+  }
+}
+
+static void
 test_uri_string_has_scheme(void)
 {
   assert(!serd_uri_string_has_scheme("relative"));
@@ -44,19 +75,21 @@ test_file_uri(const char* const hostname,
     expected_path = path;
   }
 
-  SerdNode* node = serd_new_file_uri(serd_string(path), serd_string(hostname));
+  SerdNode* node =
+    serd_new_file_uri(NULL, serd_string(path), serd_string(hostname));
 
   const char* node_str     = serd_node_string(node);
   char*       out_hostname = NULL;
-  char*       out_path     = serd_parse_file_uri(node_str, &out_hostname);
+  char* const out_path     = serd_parse_file_uri(NULL, node_str, &out_hostname);
+
   assert(!strcmp(node_str, expected_uri));
   assert((hostname && out_hostname) || (!hostname && !out_hostname));
   assert(!hostname || !strcmp(hostname, out_hostname));
   assert(!strcmp(out_path, expected_path));
 
-  serd_free(out_path);
-  serd_free(out_hostname);
-  serd_node_free(node);
+  serd_free(NULL, out_path);
+  serd_free(NULL, out_hostname);
+  serd_node_free(NULL, node);
 }
 
 static void
@@ -107,22 +140,22 @@ test_uri_parsing(void)
 #endif
 
   // Missing trailing '/' after authority
-  assert(!serd_parse_file_uri("file://truncated", NULL));
+  assert(!serd_parse_file_uri(NULL, "file://truncated", NULL));
 
   // Check that NULL hostname doesn't crash
-  char* out_path = serd_parse_file_uri("file://me/path", NULL);
+  char* out_path = serd_parse_file_uri(NULL, "file://me/path", NULL);
   assert(!strcmp(out_path, "/path"));
-  serd_free(out_path);
+  serd_free(NULL, out_path);
 
   // Invalid first escape character
-  out_path = serd_parse_file_uri("file:///foo/%0Xbar", NULL);
+  out_path = serd_parse_file_uri(NULL, "file:///foo/%0Xbar", NULL);
   assert(!strcmp(out_path, "/foo/bar"));
-  serd_free(out_path);
+  serd_free(NULL, out_path);
 
   // Invalid second escape character
-  out_path = serd_parse_file_uri("file:///foo/%X0bar", NULL);
+  out_path = serd_parse_file_uri(NULL, "file:///foo/%X0bar", NULL);
   assert(!strcmp(out_path, "/foo/bar"));
-  serd_free(out_path);
+  serd_free(NULL, out_path);
 }
 
 static void
@@ -134,12 +167,12 @@ test_parse_uri(void)
   const SerdURIView empty_uri = serd_parse_uri("");
 
   SerdNode* const nil =
-    serd_new_parsed_uri(serd_resolve_uri(empty_uri, base_uri));
+    serd_new_parsed_uri(NULL, serd_resolve_uri(empty_uri, base_uri));
 
   assert(serd_node_type(nil) == SERD_URI);
   assert(!strcmp(serd_node_string(nil), base.data));
 
-  serd_node_free(nil);
+  serd_node_free(NULL, nil);
 }
 
 static void
@@ -194,22 +227,22 @@ check_relative_uri(const char* const uri_string,
   assert(base_string);
   assert(expected_string);
 
-  SerdNode* const   uri_node  = serd_new_uri(serd_string(uri_string));
+  SerdNode* const   uri_node  = serd_new_uri(NULL, serd_string(uri_string));
   const SerdURIView uri       = serd_node_uri_view(uri_node);
-  SerdNode* const   base_node = serd_new_uri(serd_string(base_string));
+  SerdNode* const   base_node = serd_new_uri(NULL, serd_string(base_string));
   const SerdURIView base      = serd_node_uri_view(base_node);
 
   SerdNode* result_node = NULL;
   if (!root_string) {
-    result_node = serd_new_parsed_uri(serd_relative_uri(uri, base));
+    result_node = serd_new_parsed_uri(NULL, serd_relative_uri(uri, base));
   } else {
-    SerdNode* const   root_node = serd_new_uri(serd_string(root_string));
+    SerdNode* const   root_node = serd_new_uri(NULL, serd_string(root_string));
     const SerdURIView root      = serd_node_uri_view(root_node);
 
     result_node = serd_uri_is_within(uri, root)
-                    ? serd_new_parsed_uri(serd_relative_uri(uri, base))
-                    : serd_new_uri(serd_string(uri_string));
-    serd_node_free(root_node);
+                    ? serd_new_parsed_uri(NULL, serd_relative_uri(uri, base))
+                    : serd_new_uri(NULL, serd_string(uri_string));
+    serd_node_free(NULL, root_node);
   }
 
   assert(!strcmp(serd_node_string(result_node), expected_string));
@@ -223,9 +256,9 @@ check_relative_uri(const char* const uri_string,
   assert(chunk_equals(&result.query, &expected.query));
   assert(chunk_equals(&result.fragment, &expected.fragment));
 
-  serd_node_free(result_node);
-  serd_node_free(base_node);
-  serd_node_free(uri_node);
+  serd_node_free(NULL, result_node);
+  serd_node_free(NULL, base_node);
+  serd_node_free(NULL, uri_node);
 }
 
 static void
@@ -326,9 +359,9 @@ test_relative_uri(void)
 static void
 check_uri_string(const SerdURIView uri, const char* const expected)
 {
-  SerdNode* const node = serd_new_parsed_uri(uri);
+  SerdNode* const node = serd_new_parsed_uri(NULL, uri);
   assert(!strcmp(serd_node_string(node), expected));
-  serd_node_free(node);
+  serd_node_free(NULL, node);
 }
 
 static void
@@ -379,6 +412,7 @@ test_uri_resolution(void)
 int
 main(void)
 {
+  test_file_uri_failed_alloc();
   test_uri_string_has_scheme();
   test_uri_parsing();
   test_parse_uri();
diff --git a/test/test_world.c b/test/test_world.c
index 3f7f6ea6..7ff20143 100644
--- a/test/test_world.c
+++ b/test/test_world.c
@@ -3,6 +3,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/node.h"
 #include "serd/world.h"
 
@@ -11,9 +13,28 @@
 #include <string.h>
 
 static void
+test_new_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  // Successfully allocate a world to count the number of allocations
+  SerdWorld* const world = serd_world_new(&allocator.base);
+  assert(world);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_world_new(&allocator.base));
+  }
+
+  serd_world_free(world);
+}
+
+static void
 test_get_blank(void)
 {
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   char       expected[12];
 
   for (unsigned i = 0; i < 32; ++i) {
@@ -29,6 +50,7 @@ test_get_blank(void)
 int
 main(void)
 {
+  test_new_failed_alloc();
   test_get_blank();
 
   return 0;
diff --git a/test/test_writer.c b/test/test_writer.c
index 47350031..39bcd34a 100644
--- a/test/test_writer.c
+++ b/test/test_writer.c
@@ -3,6 +3,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/buffer.h"
 #include "serd/env.h"
 #include "serd/event.h"
@@ -26,23 +28,112 @@
 static void
 test_writer_new(void)
 {
-  SerdWorld*       world  = serd_world_new();
-  SerdEnv*         env    = serd_env_new(serd_empty_string());
-  SerdBuffer       buffer = {NULL, 0};
+  SerdWorld*       world  = serd_world_new(NULL);
+  SerdEnv*         env    = serd_env_new(NULL, serd_empty_string());
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   assert(!serd_writer_new(world, SERD_TURTLE, 0U, env, &output, 0U));
 
+  serd_env_free(env);
   serd_world_free(world);
+}
+
+static void
+test_new_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const world  = serd_world_new(&allocator.base);
+  SerdEnv*         env    = serd_env_new(&allocator.base, serd_empty_string());
+  SerdBuffer       buffer = {&allocator.base, NULL, 0};
+  SerdOutputStream output = serd_open_output_buffer(&buffer);
+  const size_t     n_world_allocs = allocator.n_allocations;
+
+  // Successfully allocate a writer to count the number of allocations
+  SerdWriter* const writer =
+    serd_writer_new(world, SERD_TURTLE, 0U, env, &output, 1U);
+
+  assert(writer);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations - n_world_allocs;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_writer_new(world, SERD_TURTLE, 0U, env, &output, 1U));
+  }
+
+  serd_writer_free(writer);
   serd_env_free(env);
+  serd_world_free(world);
+}
+
+static void
+test_write_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld*       world  = serd_world_new(&allocator.base);
+  SerdEnv*         env    = serd_env_new(NULL, serd_empty_string());
+  SerdBuffer       buffer = {&allocator.base, NULL, 0};
+  SerdOutputStream output = serd_open_output_buffer(&buffer);
+
+  SerdNode* s  = serd_new_uri(NULL, serd_string("http://example.org/s"));
+  SerdNode* p1 = serd_new_uri(NULL, serd_string("http://example.org/p"));
+
+  SerdNode* p2 = serd_new_uri(
+    NULL, serd_string("http://example.org/dramatically/longer/predicate"));
+
+  SerdNode* o = serd_new_token(NULL, SERD_BLANK, serd_string("o"));
+
+  const size_t n_setup_allocs = allocator.n_allocations;
+
+  // Successfully write a statement to count the number of allocations
+  SerdWriter* writer =
+    serd_writer_new(world, SERD_TURTLE, 0U, env, &output, 1U);
+  const SerdSink* sink = serd_writer_sink(writer);
+  assert(writer);
+  assert(sink);
+  assert(!serd_sink_write(sink, 0U, s, p1, o, NULL));
+  assert(!serd_sink_write(sink, 0U, s, p2, o, NULL));
+  const size_t n_new_allocs = allocator.n_allocations - n_setup_allocs;
+
+  serd_writer_free(writer);
+
+  // Test that each allocation failing is handled gracefully
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    if ((writer = serd_writer_new(world, SERD_TURTLE, 0U, env, &output, 1U))) {
+      sink = serd_writer_sink(writer);
+
+      const SerdStatus st1 = serd_sink_write(sink, 0U, s, p1, o, NULL);
+      const SerdStatus st2 = serd_sink_write(sink, 0U, s, p2, o, NULL);
+
+      assert(st1 == SERD_BAD_ALLOC || st1 == SERD_BAD_WRITE ||
+             st2 == SERD_BAD_ALLOC || st2 == SERD_BAD_WRITE);
+
+      serd_writer_free(writer);
+    }
+  }
+
+  serd_close_output(&output);
+  serd_env_free(env);
+  serd_buffer_close(&buffer);
+  serd_free(NULL, buffer.buf);
+  serd_node_free(NULL, o);
+  serd_node_free(NULL, p2);
+  serd_node_free(NULL, p1);
+  serd_node_free(NULL, s);
+  serd_world_free(world);
 }
 
 static void
 test_write_bad_event(void)
 {
-  SerdWorld*       world  = serd_world_new();
-  SerdEnv*         env    = serd_env_new(serd_empty_string());
-  SerdBuffer       buffer = {NULL, 0};
+  SerdWorld*       world  = serd_world_new(NULL);
+  SerdEnv*         env    = serd_env_new(NULL, serd_empty_string());
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer =
@@ -58,7 +149,7 @@ test_write_bad_event(void)
   char* const out = (char*)buffer.buf;
   assert(out);
   assert(!strcmp(out, ""));
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
   serd_writer_free(writer);
   serd_env_free(env);
@@ -68,26 +159,28 @@ test_write_bad_event(void)
 static void
 test_write_long_literal(void)
 {
-  SerdWorld*       world  = serd_world_new();
-  SerdEnv*         env    = serd_env_new(serd_empty_string());
-  SerdBuffer       buffer = {NULL, 0};
+  SerdWorld*       world  = serd_world_new(NULL);
+  SerdEnv*         env    = serd_env_new(NULL, serd_empty_string());
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer =
     serd_writer_new(world, SERD_TURTLE, 0U, env, &output, 1U);
   assert(writer);
 
-  SerdNode* s = serd_new_uri(serd_string("http://example.org/s"));
-  SerdNode* p = serd_new_uri(serd_string("http://example.org/p"));
-  SerdNode* o = serd_new_literal(
-    serd_string("hello \"\"\"world\"\"\"!"), SERD_IS_LONG, serd_empty_string());
+  SerdNode* s = serd_new_uri(NULL, serd_string("http://example.org/s"));
+  SerdNode* p = serd_new_uri(NULL, serd_string("http://example.org/p"));
+  SerdNode* o = serd_new_literal(NULL,
+                                 serd_string("hello \"\"\"world\"\"\"!"),
+                                 SERD_IS_LONG,
+                                 serd_empty_string());
 
   assert(serd_node_flags(o) & SERD_IS_LONG);
   assert(!serd_sink_write(serd_writer_sink(writer), 0, s, p, o, NULL));
 
-  serd_node_free(o);
-  serd_node_free(p);
-  serd_node_free(s);
+  serd_node_free(NULL, o);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
   serd_writer_free(writer);
   serd_close_output(&output);
   serd_env_free(env);
@@ -100,7 +193,7 @@ test_write_long_literal(void)
     "\t<http://example.org/p> \"\"\"hello \"\"\\\"world\"\"\\\"!\"\"\" .\n";
 
   assert(!strcmp(out, expected));
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
   serd_world_free(world);
 }
@@ -121,8 +214,8 @@ static void
 test_writer_cleanup(void)
 {
   SerdStatus       st    = SERD_SUCCESS;
-  SerdWorld*       world = serd_world_new();
-  SerdEnv*         env   = serd_env_new(serd_empty_string());
+  SerdWorld*       world = serd_world_new(NULL);
+  SerdEnv*         env   = serd_env_new(NULL, serd_empty_string());
   SerdOutputStream output =
     serd_open_output_stream(null_sink, NULL, NULL, NULL);
 
@@ -131,9 +224,9 @@ test_writer_cleanup(void)
 
   const SerdSink* sink = serd_writer_sink(writer);
 
-  SerdNode* s = serd_new_uri(serd_string("http://example.org/s"));
-  SerdNode* p = serd_new_uri(serd_string("http://example.org/p"));
-  SerdNode* o = serd_new_blank(serd_string("start"));
+  SerdNode* s = serd_new_uri(NULL, serd_string("http://example.org/s"));
+  SerdNode* p = serd_new_uri(NULL, serd_string("http://example.org/p"));
+  SerdNode* o = serd_new_blank(NULL, serd_string("start"));
 
   st = serd_sink_write(sink, SERD_ANON_O, s, p, o, NULL);
   assert(!st);
@@ -143,11 +236,11 @@ test_writer_cleanup(void)
     char buf[12] = {0};
     snprintf(buf, sizeof(buf), "b%u", i);
 
-    SerdNode* next_o = serd_new_blank(serd_string(buf));
+    SerdNode* next_o = serd_new_blank(NULL, serd_string(buf));
 
     st = serd_sink_write(sink, SERD_ANON_O, o, p, next_o, NULL);
 
-    serd_node_free(o);
+    serd_node_free(NULL, o);
     o = next_o;
   }
 
@@ -155,14 +248,14 @@ test_writer_cleanup(void)
   assert(!(st = serd_writer_finish(writer)));
 
   // Set the base to an empty URI
-  SerdNode* empty_uri = serd_new_uri(serd_string(""));
+  SerdNode* empty_uri = serd_new_uri(NULL, serd_string(""));
   assert(!(st = serd_sink_write_base(sink, empty_uri)));
-  serd_node_free(empty_uri);
+  serd_node_free(NULL, empty_uri);
 
   // Free (which could leak if the writer doesn't clean up the stack properly)
-  serd_node_free(o);
-  serd_node_free(p);
-  serd_node_free(s);
+  serd_node_free(NULL, o);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
   serd_writer_free(writer);
   serd_env_free(env);
   serd_world_free(world);
@@ -175,8 +268,8 @@ test_strict_write(void)
   FILE* const       fd   = fopen(path, "wb");
   assert(fd);
 
-  SerdWorld*        world = serd_world_new();
-  SerdEnv* const    env   = serd_env_new(serd_empty_string());
+  SerdWorld*        world = serd_world_new(NULL);
+  SerdEnv* const    env   = serd_env_new(NULL, serd_empty_string());
   SerdOutputStream  out   = serd_open_output_stream(null_sink, NULL, NULL, fd);
   SerdWriter* const writer =
     serd_writer_new(world, SERD_TURTLE, 0U, env, &out, 1U);
@@ -187,19 +280,19 @@ test_strict_write(void)
 
   const uint8_t bad_str[] = {0xFF, 0x90, 'h', 'i', 0};
 
-  SerdNode* s = serd_new_uri(serd_string("http://example.org/s"));
-  SerdNode* p = serd_new_uri(serd_string("http://example.org/p"));
+  SerdNode* s = serd_new_uri(NULL, serd_string("http://example.org/s"));
+  SerdNode* p = serd_new_uri(NULL, serd_string("http://example.org/p"));
 
-  SerdNode* bad_lit = serd_new_string(serd_string((const char*)bad_str));
-  SerdNode* bad_uri = serd_new_uri(serd_string((const char*)bad_str));
+  SerdNode* bad_lit = serd_new_string(NULL, serd_string((const char*)bad_str));
+  SerdNode* bad_uri = serd_new_uri(NULL, serd_string((const char*)bad_str));
 
   assert(serd_sink_write(sink, 0, s, p, bad_lit, NULL) == SERD_BAD_TEXT);
   assert(serd_sink_write(sink, 0, s, p, bad_uri, NULL) == SERD_BAD_TEXT);
 
-  serd_node_free(bad_uri);
-  serd_node_free(bad_lit);
-  serd_node_free(p);
-  serd_node_free(s);
+  serd_node_free(NULL, bad_uri);
+  serd_node_free(NULL, bad_lit);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
   serd_writer_free(writer);
   serd_env_free(env);
   serd_world_free(world);
@@ -224,15 +317,14 @@ error_sink(const void* const buf,
 static void
 test_write_error(void)
 {
-  SerdWorld* const world = serd_world_new();
-  SerdEnv* const   env   = serd_env_new(serd_empty_string());
+  SerdWorld* const world = serd_world_new(NULL);
+  SerdEnv* const   env   = serd_env_new(NULL, serd_empty_string());
   SerdOutputStream out = serd_open_output_stream(error_sink, NULL, NULL, NULL);
-  SerdWriter*      writer = NULL;
-  SerdStatus       st     = SERD_SUCCESS;
+  SerdStatus       st  = SERD_SUCCESS;
 
-  SerdNode* u = serd_new_uri(serd_string("http://example.com/u"));
+  SerdNode* u = serd_new_uri(NULL, serd_string("http://example.com/u"));
 
-  writer =
+  SerdWriter* const writer =
     serd_writer_new(world, SERD_TURTLE, (SerdWriterFlags)0, env, &out, 1U);
   assert(writer);
 
@@ -242,7 +334,7 @@ test_write_error(void)
   assert(st == SERD_BAD_WRITE);
   serd_writer_free(writer);
 
-  serd_node_free(u);
+  serd_node_free(NULL, u);
   serd_env_free(env);
   serd_world_free(world);
 }
@@ -250,8 +342,8 @@ test_write_error(void)
 static void
 test_writer_stack_overflow(void)
 {
-  SerdWorld* world = serd_world_new();
-  SerdEnv*   env   = serd_env_new(serd_empty_string());
+  SerdWorld* world = serd_world_new(NULL);
+  SerdEnv*   env   = serd_env_new(NULL, serd_empty_string());
 
   SerdOutputStream output =
     serd_open_output_stream(null_sink, NULL, NULL, NULL);
@@ -261,10 +353,10 @@ test_writer_stack_overflow(void)
 
   const SerdSink* sink = serd_writer_sink(writer);
 
-  SerdNode* const s = serd_new_uri(serd_string("http://example.org/s"));
-  SerdNode* const p = serd_new_uri(serd_string("http://example.org/p"));
+  SerdNode* const s = serd_new_uri(NULL, serd_string("http://example.org/s"));
+  SerdNode* const p = serd_new_uri(NULL, serd_string("http://example.org/p"));
 
-  SerdNode*  o  = serd_new_blank(serd_string("blank"));
+  SerdNode*  o  = serd_new_blank(NULL, serd_string("blank"));
   SerdStatus st = serd_sink_write(sink, SERD_ANON_O, s, p, o, NULL);
   assert(!st);
 
@@ -273,11 +365,11 @@ test_writer_stack_overflow(void)
     char buf[1024];
     snprintf(buf, sizeof(buf), "b%u", i);
 
-    SerdNode* next_o = serd_new_blank(serd_string(buf));
+    SerdNode* next_o = serd_new_blank(NULL, serd_string(buf));
 
     st = serd_sink_write(sink, SERD_ANON_O, o, p, next_o, NULL);
 
-    serd_node_free(o);
+    serd_node_free(NULL, o);
     o = next_o;
 
     if (st) {
@@ -288,9 +380,9 @@ test_writer_stack_overflow(void)
 
   assert(st == SERD_BAD_STACK);
 
-  serd_node_free(o);
-  serd_node_free(p);
-  serd_node_free(s);
+  serd_node_free(NULL, o);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
   serd_writer_free(writer);
   serd_close_output(&output);
   serd_env_free(env);
@@ -300,14 +392,14 @@ test_writer_stack_overflow(void)
 static void
 test_write_empty_syntax(void)
 {
-  SerdWorld* world = serd_world_new();
-  SerdEnv*   env   = serd_env_new(serd_empty_string());
+  SerdWorld* world = serd_world_new(NULL);
+  SerdEnv*   env   = serd_env_new(NULL, serd_empty_string());
 
-  SerdNode* s = serd_new_uri(serd_string("http://example.org/s"));
-  SerdNode* p = serd_new_uri(serd_string("http://example.org/p"));
-  SerdNode* o = serd_new_uri(serd_string("http://example.org/o"));
+  SerdNode* s = serd_new_uri(NULL, serd_string("http://example.org/s"));
+  SerdNode* p = serd_new_uri(NULL, serd_string("http://example.org/p"));
+  SerdNode* o = serd_new_uri(NULL, serd_string("http://example.org/o"));
 
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer =
@@ -321,12 +413,12 @@ test_write_empty_syntax(void)
   char* const out = (char*)buffer.buf;
   assert(out);
   assert(strlen(out) == 0);
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
   serd_writer_free(writer);
-  serd_node_free(o);
-  serd_node_free(p);
-  serd_node_free(s);
+  serd_node_free(NULL, o);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
   serd_close_output(&output);
   serd_env_free(env);
   serd_world_free(world);
@@ -335,9 +427,9 @@ test_write_empty_syntax(void)
 static void
 check_pname_escape(const char* const lname, const char* const expected)
 {
-  SerdWorld*       world  = serd_world_new();
-  SerdEnv*         env    = serd_env_new(serd_empty_string());
-  SerdBuffer       buffer = {NULL, 0};
+  SerdWorld*       world  = serd_world_new(NULL);
+  SerdEnv*         env    = serd_env_new(NULL, serd_empty_string());
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer =
@@ -349,20 +441,20 @@ check_pname_escape(const char* const lname, const char* const expected)
 
   serd_env_set_prefix(env, serd_string("eg"), serd_string(prefix));
 
-  SerdNode* s = serd_new_uri(serd_string("http://example.org/s"));
-  SerdNode* p = serd_new_uri(serd_string("http://example.org/p"));
+  SerdNode* s = serd_new_uri(NULL, serd_string("http://example.org/s"));
+  SerdNode* p = serd_new_uri(NULL, serd_string("http://example.org/p"));
 
   char* const uri = (char*)calloc(1, prefix_len + strlen(lname) + 1);
   memcpy(uri, prefix, prefix_len + 1);
   memcpy(uri + prefix_len, lname, strlen(lname) + 1);
 
-  SerdNode* node = serd_new_uri(serd_string(uri));
+  SerdNode* node = serd_new_uri(NULL, serd_string(uri));
   assert(!serd_sink_write(serd_writer_sink(writer), 0, s, p, node, NULL));
-  serd_node_free(node);
+  serd_node_free(NULL, node);
 
   free(uri);
-  serd_node_free(p);
-  serd_node_free(s);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
   serd_writer_free(writer);
   serd_close_output(&output);
   serd_env_free(env);
@@ -370,7 +462,7 @@ check_pname_escape(const char* const lname, const char* const expected)
 
   char* const out = (char*)buffer.buf;
   assert(!strcmp(out, expected));
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
   serd_world_free(world);
 }
@@ -409,12 +501,13 @@ test_write_pname_escapes(void)
 static void
 test_write_bad_uri(void)
 {
-  SerdWorld*       world  = serd_world_new();
-  SerdEnv*         env    = serd_env_new(serd_empty_string());
-  SerdNode*        s      = serd_new_uri(serd_string("http://example.org/s"));
-  SerdNode*        p      = serd_new_uri(serd_string("http://example.org/p"));
-  SerdNode*        rel    = serd_new_uri(serd_string("rel"));
-  SerdBuffer       buffer = {NULL, 0};
+  SerdWorld* world = serd_world_new(NULL);
+  SerdEnv*   env   = serd_env_new(NULL, serd_empty_string());
+  SerdNode*  s     = serd_new_uri(NULL, serd_string("http://example.org/s"));
+  SerdNode*  p     = serd_new_uri(NULL, serd_string("http://example.org/p"));
+  SerdNode*  rel   = serd_new_uri(NULL, serd_string("rel"));
+
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
   SerdWriter*      writer =
     serd_writer_new(world, SERD_NTRIPLES, 0U, env, &output, 1U);
@@ -429,10 +522,10 @@ test_write_bad_uri(void)
 
   serd_writer_free(writer);
   serd_close_output(&output);
-  serd_free(buffer.buf);
-  serd_node_free(rel);
-  serd_node_free(p);
-  serd_node_free(s);
+  serd_free(NULL, buffer.buf);
+  serd_node_free(NULL, rel);
+  serd_node_free(NULL, p);
+  serd_node_free(NULL, s);
   serd_env_free(env);
   serd_world_free(world);
 }
@@ -441,6 +534,8 @@ int
 main(void)
 {
   test_writer_new();
+  test_new_failed_alloc();
+  test_write_failed_alloc();
   test_write_bad_event();
   test_write_long_literal();
   test_writer_cleanup();
diff --git a/tools/console.c b/tools/console.c
index f7de779f..012c50a3 100644
--- a/tools/console.c
+++ b/tools/console.c
@@ -54,10 +54,10 @@ serd_set_base_uri_from_path(SerdEnv* const env, const char* const path)
   }
 
   SerdNode* const file_uri =
-    serd_new_file_uri(serd_string(input_path), serd_empty_string());
+    serd_new_file_uri(NULL, serd_string(input_path), serd_empty_string());
 
   serd_env_set_base_uri(env, serd_node_string_view(file_uri));
-  serd_node_free(file_uri);
+  serd_node_free(NULL, file_uri);
   zix_free(NULL, input_path);
 
   return SERD_SUCCESS;
diff --git a/tools/serd-pipe.c b/tools/serd-pipe.c
index 84893506..9be11d66 100644
--- a/tools/serd-pipe.c
+++ b/tools/serd-pipe.c
@@ -163,7 +163,7 @@ main(int argc, char** argv)
           return missing_arg(prog, 'B');
         }
 
-        base = serd_new_uri(serd_string(argv[a]));
+        base = serd_new_uri(NULL, serd_string(argv[a]));
         break;
       } else if (opt == 'b') {
         if (argv[a][o + 1] || ++a == argc) {
@@ -280,19 +280,20 @@ main(int argc, char** argv)
       (output_syntax == SERD_NQUADS || output_syntax == SERD_NTRIPLES)) {
     // Choose base URI from the single input path
     char* const input_path = zix_canonical_path(NULL, inputs[0]);
-    if (!input_path || !(base = serd_new_file_uri(serd_string(input_path),
-                                                  serd_empty_string()))) {
+    if (!input_path ||
+        !(base = serd_new_file_uri(
+            NULL, serd_string(input_path), serd_empty_string()))) {
       SERDI_ERRORF("unable to determine base URI from path %s\n", inputs[0]);
     }
     zix_free(NULL, input_path);
   }
 
-  SerdWorld* const world  = serd_world_new();
+  SerdWorld* const world  = serd_world_new(NULL);
   const SerdLimits limits = {stack_size, MAX_DEPTH};
   serd_world_set_limits(world, limits);
 
-  SerdEnv* const env =
-    serd_env_new(base ? serd_node_string_view(base) : serd_empty_string());
+  SerdEnv* const env = serd_env_new(
+    NULL, base ? serd_node_string_view(base) : serd_empty_string());
 
   SerdOutputStream out = serd_open_tool_output(out_filename);
   if (!out.stream) {
@@ -370,9 +371,9 @@ main(int argc, char** argv)
   free(prefix);
 
   serd_writer_free(writer);
-  serd_node_free(input_name);
+  serd_node_free(NULL, input_name);
   serd_env_free(env);
-  serd_node_free(base);
+  serd_node_free(NULL, base);
   serd_world_free(world);
 
   if (serd_close_output(&out)) {