Add custom allocator support

26 files changed, 1471 insertions, 367 deletions

diff --git a/test/.clang-tidy b/test/.clang-tidy
index d8601571..fa6f671c 100644
--- a/test/.clang-tidy
+++ b/test/.clang-tidy
@@ -13,6 +13,7 @@ Checks: >
   -clang-analyzer-valist.Uninitialized,
   -cppcoreguidelines-avoid-non-const-global-variables,
   -hicpp-signed-bitwise,
+  -llvm-header-guard,
   -llvmlibc-*,
   -readability-function-cognitive-complexity,
 WarningsAsErrors: '*'
diff --git a/test/failing_allocator.c b/test/failing_allocator.c
new file mode 100644
index 00000000..e04f3eaf
--- /dev/null
+++ b/test/failing_allocator.c
@@ -0,0 +1,121 @@
+/*
+  Copyright 2021 David Robillard <d@drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#include "failing_allocator.h"
+
+#include "serd/serd.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;
+}
+
+SERD_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;
+}
+
+SERD_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);
+}
+
+SERD_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);
+}
+
+SERD_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..4539ede8
--- /dev/null
+++ b/test/failing_allocator.h
@@ -0,0 +1,34 @@
+/*
+  Copyright 2021 David Robillard <d@drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#ifndef SERD_FAILING_ALLOCATOR_H
+#define SERD_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_FAILING_ALLOCATOR_H
diff --git a/test/meson.build b/test/meson.build
index a25ac6de..eae5d42e 100644
--- a/test/meson.build
+++ b/test/meson.build
@@ -8,9 +8,11 @@ run_sort_suite = find_program('run_sort_suite.py')
 wrapper = meson.get_cross_property('exe_wrapper', '')
 
 unit_tests = [
+  'canon',
   'caret',
   'cursor',
   'env',
+  'filter',
   'free_null',
   'log',
   'model',
@@ -40,7 +42,7 @@ endif
 foreach unit : unit_tests
   test(unit,
        executable('test_@0@'.format(unit),
-                  'test_@0@.c'.format(unit),
+                  files('test_@0@.c'.format(unit), 'failing_allocator.c'),
                   c_args: c_warnings + platform_args + prog_args,
                   dependencies: serd_dep),
        env: test_env,
diff --git a/test/test_canon.c b/test/test_canon.c
new file mode 100644
index 00000000..1e4dc24c
--- /dev/null
+++ b/test/test_canon.c
@@ -0,0 +1,108 @@
+/*
+  Copyright 2021 David Robillard <d@drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#undef NDEBUG
+
+#include "failing_allocator.h"
+#include "serd/serd.h"
+
+#include <assert.h>
+#include <stddef.h>
+
+static SerdStatus
+ignore_event(void* handle, const SerdEvent* event)
+{
+  (void)handle;
+  (void)event;
+  return SERD_SUCCESS;
+}
+
+static void
+test_new_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const world = serd_world_new(&allocator.base);
+  SerdNodes* const nodes = serd_nodes_new(&allocator.base);
+
+  SerdSink*    target         = serd_sink_new(world, NULL, ignore_event, NULL);
+  const size_t n_setup_allocs = allocator.n_allocations;
+
+  // Successfully allocate a canon to count the number of allocations
+  SerdSink* canon = serd_canon_new(world, target, 0u);
+  assert(canon);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations - n_setup_allocs;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_canon_new(world, target, 0u));
+  }
+
+  serd_sink_free(canon);
+  serd_sink_free(target);
+  serd_nodes_free(nodes);
+  serd_world_free(world);
+}
+
+static void
+test_write_failed_alloc(void)
+{
+  static const SerdStringView s_string = SERD_STRING("http://example.org/s");
+  static const SerdStringView p_string = SERD_STRING("http://example.org/p");
+  static const SerdStringView o_string = SERD_STRING("012.340");
+  static const SerdStringView xsd_float =
+    SERD_STRING("http://www.w3.org/2001/XMLSchema#float");
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const      world = serd_world_new(&allocator.base);
+  SerdNodes* const      nodes = serd_nodes_new(&allocator.base);
+  const SerdNode* const s     = serd_nodes_uri(nodes, s_string);
+  const SerdNode* const p     = serd_nodes_uri(nodes, p_string);
+  const SerdNode* const o =
+    serd_nodes_literal(nodes, o_string, SERD_HAS_DATATYPE, xsd_float);
+
+  SerdSink*    target         = serd_sink_new(world, NULL, ignore_event, NULL);
+  SerdSink*    canon          = serd_canon_new(world, target, 0u);
+  const size_t n_setup_allocs = allocator.n_allocations;
+
+  // Successfully write statement to count the number of allocations
+  assert(canon);
+  assert(!serd_sink_write(canon, 0u, s, p, o, NULL));
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations - n_setup_allocs;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    const SerdStatus st = serd_sink_write(canon, 0u, s, p, o, NULL);
+    assert(st == SERD_BAD_ALLOC);
+  }
+
+  serd_sink_free(canon);
+  serd_sink_free(target);
+  serd_nodes_free(nodes);
+  serd_world_free(world);
+}
+
+int
+main(void)
+{
+  test_new_failed_alloc();
+  test_write_failed_alloc();
+  return 0;
+}
diff --git a/test/test_caret.c b/test/test_caret.c
index 54037a30..5fb6d18d 100644
--- a/test/test_caret.c
+++ b/test/test_caret.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2019-2020 David Robillard <d@drobilla.net>
+  Copyright 2019-2021 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -16,34 +16,39 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
 #include <stddef.h>
+#include <stdint.h>
 
-int
-main(void)
+static int
+test_caret(void)
 {
-  SerdNodes* const      nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
   const SerdNode* const node  = serd_nodes_string(nodes, SERD_STRING("node"));
-  SerdCaret* const      caret = serd_caret_new(node, 46, 2);
+  SerdCaret* const      caret = serd_caret_new(allocator, node, 46, 2);
 
   assert(serd_caret_equals(caret, caret));
   assert(serd_caret_name(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(allocator, caret);
 
   assert(serd_caret_equals(caret, copy));
-  assert(!serd_caret_copy(NULL));
+  assert(!serd_caret_copy(allocator, NULL));
 
   const SerdNode* const other_node =
     serd_nodes_string(nodes, 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);
+  SerdCaret* const other_file = serd_caret_new(allocator, other_node, 46, 2);
+  SerdCaret* const other_line = serd_caret_new(allocator, node, 47, 2);
+  SerdCaret* const other_col  = serd_caret_new(allocator, node, 46, 3);
 
   assert(!serd_caret_equals(caret, other_file));
   assert(!serd_caret_equals(caret, other_line));
@@ -51,12 +56,60 @@ 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_caret_free(copy);
-  serd_caret_free(caret);
+  serd_caret_free(allocator, other_col);
+  serd_caret_free(allocator, other_line);
+  serd_caret_free(allocator, other_file);
+  serd_caret_free(allocator, copy);
+  serd_caret_free(allocator, caret);
   serd_nodes_free(nodes);
 
   return 0;
 }
+
+static void
+test_failed_alloc(void)
+{
+  char node_buf[32];
+
+  assert(!serd_node_construct_token(
+            sizeof(node_buf), node_buf, SERD_LITERAL, SERD_STRING("node"))
+            .status);
+
+  const SerdNode*      node      = (const SerdNode*)node_buf;
+  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);
+}
+
+int
+main(void)
+{
+  test_caret();
+  test_failed_alloc();
+  return 0;
+}
diff --git a/test/test_cursor.c b/test/test_cursor.c
index cade0621..23f4aefd 100644
--- a/test/test_cursor.c
+++ b/test/test_cursor.c
@@ -24,12 +24,12 @@
 static void
 test_copy(void)
 {
-  assert(!serd_cursor_copy(NULL));
+  assert(!serd_cursor_copy(NULL, NULL));
 
-  SerdWorld* const  world = serd_world_new();
+  SerdWorld* const  world = serd_world_new(NULL);
   SerdModel* const  model = serd_model_new(world, SERD_ORDER_SPO, 0u);
   SerdCursor* const begin = serd_model_begin(model);
-  SerdCursor* const copy  = serd_cursor_copy(begin);
+  SerdCursor* const copy  = serd_cursor_copy(NULL, begin);
 
   assert(serd_cursor_equals(copy, begin));
 
@@ -42,7 +42,7 @@ test_copy(void)
 static void
 test_comparison(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   SerdNodes* const nodes = serd_world_nodes(world);
   SerdModel* const model = serd_model_new(world, SERD_ORDER_SPO, 0u);
 
diff --git a/test/test_env.c b/test/test_env.c
index e2d53f6c..e6d6cbe5 100644
--- a/test/test_env.c
+++ b/test/test_env.c
@@ -16,19 +16,144 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
+#include <inttypes.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();
+
+  SerdWorld* const world          = serd_world_new(&allocator.base);
+  const size_t     n_world_allocs = allocator.n_allocations;
+
+  // Successfully allocate a env to count the number of allocations
+  SerdEnv* const env = serd_env_new(world, SERD_EMPTY_STRING());
+  assert(env);
+
+  // 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_env_new(world, SERD_EMPTY_STRING()));
+  }
+
+  serd_env_free(env);
+  serd_world_free(world);
+}
+
+static void
+test_copy_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const world          = serd_world_new(&allocator.base);
+  SerdEnv* const   env            = serd_env_new(world, SERD_EMPTY_STRING());
+  const size_t     n_world_allocs = allocator.n_allocations;
+
+  // Successfully copy an env to count the number of allocations
+  SerdEnv* 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_world_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);
+  serd_world_free(world);
+}
+
+static void
+test_set_prefix_absolute_failed_alloc(void)
+{
+  static const SerdStringView base_uri = SERD_STRING("http://example.org/");
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const world          = serd_world_new(&allocator.base);
+  SerdEnv* const   env            = serd_env_new(world, base_uri);
+  const size_t     n_world_allocs = allocator.n_allocations;
+
+  char name[64] = "eg";
+  char uri[64]  = "http://example.org/";
+
+  // Successfully set an absolute prefix to count the number of allocations
+  SerdStatus 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_world_allocs;
+  for (size_t i = 0; i < n_set_prefix_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    snprintf(name, sizeof(name), "eg%" PRIuPTR, i);
+    snprintf(uri, sizeof(name), "http://example.org/%" PRIuPTR, i);
+
+    st = serd_env_set_prefix(env, SERD_STRING(name), SERD_STRING(uri));
+    assert(st == SERD_BAD_ALLOC);
+  }
+
+  serd_env_free(env);
+  serd_world_free(world);
+}
+
+static void
+test_set_prefix_relative_failed_alloc(void)
+{
+  static const SerdStringView base_uri = SERD_STRING("http://example.org/");
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const world          = serd_world_new(&allocator.base);
+  const size_t     n_setup_allocs = allocator.n_allocations;
+
+  char name[64] = "egX";
+  char uri[64]  = "relativeX";
+
+  // Successfully set an absolute prefix to count the number of allocations
+  SerdEnv*   env = serd_env_new(world, 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 - n_setup_allocs;
+  for (size_t i = 0; i < n_set_prefix_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    snprintf(name, sizeof(name), "eg%" PRIuPTR, i);
+    snprintf(uri, sizeof(uri), "relative%" PRIuPTR, i);
+
+    env = serd_env_new(world, 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);
+  }
+
+  serd_world_free(world);
+}
+
+static void
 test_copy(void)
 {
-  assert(!serd_env_copy(NULL));
+  assert(!serd_env_copy(NULL, NULL));
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
 
   SerdEnv* const env =
     serd_env_new(world, SERD_STRING("http://example.org/base/"));
@@ -36,7 +161,7 @@ test_copy(void)
   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(serd_world_allocator(world), env);
 
   assert(serd_env_equals(env, env_copy));
 
@@ -58,7 +183,7 @@ test_copy(void)
 static void
 test_comparison(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   SerdEnv* const   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
   assert(!serd_env_equals(env, NULL));
@@ -74,7 +199,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));
@@ -95,9 +220,9 @@ count_prefixes(void* handle, const SerdEvent* event)
 static void
 test_base_uri(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   SerdEnv* const   env   = serd_env_new(world, SERD_EMPTY_STRING());
-  SerdNode* const  eg    = serd_new_uri(SERD_STRING(NS_EG));
+  SerdNode* const  eg    = serd_new_uri(NULL, SERD_STRING(NS_EG));
 
   // Test that invalid calls work as expected
   assert(!serd_env_base_uri(env));
@@ -116,7 +241,7 @@ test_base_uri(void)
   assert(!serd_env_set_base_uri(env, SERD_EMPTY_STRING()));
   assert(!serd_env_base_uri(env));
 
-  serd_node_free(eg);
+  serd_node_free(NULL, eg);
   serd_env_free(env);
   serd_world_free(world);
 }
@@ -130,7 +255,7 @@ test_set_prefix(void)
   static const SerdStringView rel   = SERD_STRING("rel");
   static const SerdStringView base  = SERD_STRING("http://example.org/");
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   SerdEnv* const   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
   // Set a valid prefix
@@ -160,14 +285,14 @@ test_set_prefix(void)
 static void
 test_expand_untyped_literal(void)
 {
-  SerdWorld* const world   = serd_world_new();
-  SerdNode* const  untyped = serd_new_string(SERD_STRING("data"));
+  SerdWorld* const world   = serd_world_new(NULL);
+  SerdNode* const  untyped = serd_new_string(NULL, SERD_STRING("data"));
   SerdEnv* const   env     = serd_env_new(world, SERD_EMPTY_STRING());
 
   assert(!serd_env_expand_node(env, untyped));
 
   serd_env_free(env);
-  serd_node_free(untyped);
+  serd_node_free(NULL, untyped);
   serd_world_free(world);
 }
 
@@ -176,8 +301,8 @@ test_expand_bad_uri_datatype(void)
 {
   static const SerdStringView type = SERD_STRING("Type");
 
-  SerdWorld* world = serd_world_new();
-  SerdNodes* nodes = serd_nodes_new();
+  SerdWorld* world = serd_world_new(NULL);
+  SerdNodes* nodes = serd_nodes_new(serd_world_allocator(world));
 
   const SerdNode* const typed =
     serd_nodes_literal(nodes, SERD_STRING("data"), SERD_HAS_DATATYPE, type);
@@ -196,20 +321,20 @@ test_expand_uri(void)
 {
   static const SerdStringView base = SERD_STRING("http://example.org/b/");
 
-  SerdWorld* const world     = serd_world_new();
+  SerdWorld* const world     = serd_world_new(NULL);
   SerdEnv* const   env       = serd_env_new(world, base);
-  SerdNode* const  rel       = serd_new_uri(SERD_STRING("rel"));
+  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(serd_world_allocator(world), empty_out);
+  serd_node_free(NULL, empty);
+  serd_node_free(serd_world_allocator(world), rel_out);
+  serd_node_free(NULL, rel);
   serd_env_free(env);
   serd_world_free(world);
 }
@@ -219,30 +344,30 @@ test_expand_empty_uri_ref(void)
 {
   static const SerdStringView base = SERD_STRING("http://example.org/b/");
 
-  SerdWorld* const world   = serd_world_new();
-  SerdNode* const  rel     = serd_new_uri(SERD_STRING("rel"));
+  SerdWorld* const world   = serd_world_new(NULL);
+  SerdNode* const  rel     = serd_new_uri(NULL, SERD_STRING("rel"));
   SerdEnv* const   env     = serd_env_new(world, 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(serd_world_allocator(world), rel_out);
 
   serd_env_free(env);
-  serd_node_free(rel);
+  serd_node_free(NULL, rel);
   serd_world_free(world);
 }
 
 static void
 test_expand_bad_uri(void)
 {
-  SerdWorld* const world   = serd_world_new();
-  SerdNode* const  bad_uri = serd_new_uri(SERD_STRING("rel"));
+  SerdWorld* const world   = serd_world_new(NULL);
+  SerdNode* const  bad_uri = serd_new_uri(NULL, SERD_STRING("rel"));
   SerdEnv* const   env     = serd_env_new(world, 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);
   serd_world_free(world);
 }
 
@@ -252,7 +377,7 @@ test_expand_curie(void)
   static const SerdStringView name = SERD_STRING("eg.1");
   static const SerdStringView eg   = SERD_STRING(NS_EG);
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   SerdEnv* const   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
   assert(!serd_env_set_prefix(env, name, eg));
@@ -262,7 +387,7 @@ test_expand_curie(void)
 
   assert(expanded);
   assert(!strcmp(serd_node_string(expanded), "http://example.org/foo"));
-  serd_node_free(expanded);
+  serd_node_free(serd_world_allocator(world), expanded);
 
   serd_env_free(env);
   serd_world_free(world);
@@ -271,7 +396,7 @@ test_expand_curie(void)
 static void
 test_expand_bad_curie(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   SerdEnv* const   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
   assert(!serd_env_expand_curie(NULL, SERD_EMPTY_STRING()));
@@ -286,14 +411,14 @@ test_expand_bad_curie(void)
 static void
 test_expand_blank(void)
 {
-  SerdWorld* const world = serd_world_new();
-  SerdNode* const  blank = serd_new_token(SERD_BLANK, SERD_STRING("b1"));
+  SerdWorld* const world = serd_world_new(NULL);
+  SerdNode* const  blank = serd_new_token(NULL, SERD_BLANK, SERD_STRING("b1"));
   SerdEnv* const   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
   assert(!serd_env_expand_node(env, blank));
 
   serd_env_free(env);
-  serd_node_free(blank);
+  serd_node_free(NULL, blank);
   serd_world_free(world);
 }
 
@@ -304,7 +429,7 @@ test_equals(void)
   static const SerdStringView base1 = SERD_STRING(NS_EG "b1/");
   static const SerdStringView base2 = SERD_STRING(NS_EG "b2/");
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   SerdEnv* const   env1  = serd_env_new(world, base1);
   SerdEnv* const   env2  = serd_env_new(world, base2);
 
@@ -326,7 +451,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);
 
@@ -338,6 +463,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_filter.c b/test/test_filter.c
new file mode 100644
index 00000000..e326f9fb
--- /dev/null
+++ b/test/test_filter.c
@@ -0,0 +1,68 @@
+/*
+  Copyright 2021 David Robillard <d@drobilla.net>
+
+  Permission to use, copy, modify, and/or distribute this software for any
+  purpose with or without fee is hereby granted, provided that the above
+  copyright notice and this permission notice appear in all copies.
+
+  THIS SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+  WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+  MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+  ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+  WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+  ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+*/
+
+#undef NDEBUG
+
+#include "failing_allocator.h"
+#include "serd/serd.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+static void
+test_new_failed_alloc(void)
+{
+  static const SerdStringView s_string = SERD_STRING("http://example.org/s");
+  static const SerdStringView p_string = SERD_STRING("http://example.org/p");
+  static const SerdStringView o_string = SERD_STRING("http://example.org/o");
+  static const SerdStringView g_string = SERD_STRING("http://example.org/g");
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const      world = serd_world_new(&allocator.base);
+  SerdNodes* const      nodes = serd_nodes_new(&allocator.base);
+  const SerdNode* const s     = serd_nodes_uri(nodes, s_string);
+  const SerdNode* const p     = serd_nodes_uri(nodes, p_string);
+  const SerdNode* const o     = serd_nodes_uri(nodes, o_string);
+  const SerdNode* const g     = serd_nodes_uri(nodes, g_string);
+
+  SerdSink*    target         = serd_sink_new(world, NULL, NULL, NULL);
+  const size_t n_setup_allocs = allocator.n_allocations;
+
+  // Successfully allocate a filter to count the number of allocations
+  SerdSink* filter = serd_filter_new(world, target, s, p, o, g, true);
+  assert(filter);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations - n_setup_allocs;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+    assert(!serd_filter_new(world, target, s, p, o, g, true));
+  }
+
+  serd_sink_free(filter);
+  serd_sink_free(target);
+  serd_nodes_free(nodes);
+  serd_world_free(world);
+}
+
+int
+main(void)
+{
+  test_new_failed_alloc();
+  return 0;
+}
diff --git a/test/test_free_null.c b/test/test_free_null.c
index 85529a2b..4494368b 100644
--- a/test/test_free_null.c
+++ b/test/test_free_null.c
@@ -23,8 +23,8 @@
 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);
@@ -32,9 +32,9 @@ main(void)
   serd_writer_free(NULL);
   serd_nodes_free(NULL);
   serd_model_free(NULL);
-  serd_statement_free(NULL);
+  serd_statement_free(NULL, NULL);
   serd_cursor_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 707a00f2..c9031ff3 100644
--- a/test/test_log.c
+++ b/test/test_log.c
@@ -47,7 +47,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);
@@ -60,7 +60,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;
@@ -74,7 +74,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);
@@ -90,22 +90,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[2] = {{"TEST_KEY", "TEST VALUE"},
                                   {"SERD_FILE", "somename"}};
diff --git a/test/test_model.c b/test/test_model.c
index 72db88ae..827bd638 100644
--- a/test/test_model.c
+++ b/test/test_model.c
@@ -16,14 +16,16 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
+#include "serd/serd.h"
+
 #include <assert.h>
 #include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 
-#include "serd/serd.h"
-
 #define WILDCARD_NODE NULL
 
 #define NS_RDF "http://www.w3.org/1999/02/22-rdf-syntax-ns#"
@@ -147,7 +149,9 @@ test_read(SerdWorld*      world,
           const SerdNode* g,
           const unsigned  n_quads)
 {
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   SerdCursor*          cursor = serd_model_begin(model);
   const SerdStatement* prev   = NULL;
@@ -345,6 +349,32 @@ ignore_only_index_error(void* const               handle,
 }
 
 static int
+test_failed_new_alloc(SerdWorld* ignored_world, const unsigned n_quads)
+{
+  (void)ignored_world;
+  (void)n_quads;
+
+  SerdFailingAllocator allocator      = serd_failing_allocator();
+  SerdWorld* const     world          = serd_world_new(&allocator.base);
+  const size_t         n_world_allocs = allocator.n_allocations;
+
+  // Successfully allocate a model to count the number of allocations
+  SerdModel* model = serd_model_new(world, SERD_ORDER_SPO, 0u);
+  assert(model);
+
+  // 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_model_new(world, SERD_ORDER_SPO, 0u));
+  }
+
+  serd_model_free(model);
+  serd_world_free(world);
+  return 0;
+}
+
+static int
 test_free_null(SerdWorld* world, const unsigned n_quads)
 {
   (void)world;
@@ -564,7 +594,9 @@ test_inserter(SerdWorld* world, const unsigned n_quads)
 {
   (void)n_quads;
 
-  SerdNodes* const nodes    = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes    = serd_nodes_new(allocator);
   SerdModel*       model    = serd_model_new(world, SERD_ORDER_SPO, 0u);
   SerdSink*        inserter = serd_inserter_new(model, NULL);
 
@@ -615,7 +647,9 @@ test_erase_with_iterator(SerdWorld* world, const unsigned n_quads)
   assert(serd_cursor_advance(iter2) == SERD_BAD_CURSOR);
 
   // Check that erasing the end iterator does nothing
-  SerdCursor* const end = serd_cursor_copy(serd_model_end(model));
+  SerdCursor* const end =
+    serd_cursor_copy(serd_world_allocator(world), serd_model_end(model));
+
   assert(serd_model_erase(model, end) == SERD_FAILURE);
 
   serd_cursor_free(end);
@@ -630,7 +664,9 @@ test_add_erase(SerdWorld* world, const unsigned n_quads)
 {
   (void)n_quads;
 
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
   SerdModel* const model = serd_model_new(world, SERD_ORDER_SPO, 0u);
 
   // Add (s p "hello")
@@ -667,7 +703,9 @@ test_add_bad_statement(SerdWorld* world, const unsigned n_quads)
 {
   (void)n_quads;
 
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_world_allocator(world);
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
   const SerdNode*  s     = serd_nodes_uri(nodes, SERD_STRING("urn:s"));
   const SerdNode*  p     = serd_nodes_uri(nodes, SERD_STRING("urn:p"));
   const SerdNode*  o     = serd_nodes_uri(nodes, SERD_STRING("urn:o"));
@@ -675,7 +713,7 @@ test_add_bad_statement(SerdWorld* world, const unsigned n_quads)
   const SerdNode* f =
     serd_nodes_uri(nodes, SERD_STRING("file:///tmp/file.ttl"));
 
-  SerdCaret* caret = serd_caret_new(f, 16, 18);
+  SerdCaret* caret = serd_caret_new(allocator, f, 16, 18);
   SerdModel* model = serd_model_new(world, SERD_ORDER_SPO, 0u);
 
   assert(!serd_model_add_with_caret(model, s, p, o, NULL, caret));
@@ -699,7 +737,7 @@ test_add_bad_statement(SerdWorld* world, const unsigned n_quads)
 
   serd_cursor_free(begin);
   serd_model_free(model);
-  serd_caret_free(caret);
+  serd_caret_free(allocator, caret);
   serd_nodes_free(nodes);
   return 0;
 }
@@ -709,7 +747,7 @@ test_add_with_caret(SerdWorld* world, const unsigned n_quads)
 {
   (void)n_quads;
 
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdNodes* const nodes = serd_nodes_new(serd_world_allocator(world));
   const SerdNode*  lit   = serd_nodes_string(nodes, SERD_STRING("string"));
   const SerdNode*  uri   = serd_nodes_uri(nodes, SERD_STRING("urn:uri"));
   const SerdNode*  blank = serd_nodes_blank(nodes, SERD_STRING("b1"));
@@ -762,7 +800,7 @@ test_copy(SerdWorld* world, const unsigned n_quads)
   SerdModel* model = serd_model_new(world, SERD_ORDER_SPO, 0u);
   generate(world, model, n_quads, NULL);
 
-  SerdModel* copy = serd_model_copy(model);
+  SerdModel* copy = serd_model_copy(serd_world_allocator(world), model);
   assert(serd_model_equals(model, copy));
 
   serd_model_free(model);
@@ -1039,7 +1077,7 @@ test_write_flat_range(SerdWorld* world, const unsigned n_quads)
   (void)n_quads;
 
   SerdModel* model = serd_model_new(world, SERD_ORDER_SPO, SERD_STORE_GRAPHS);
-  SerdNodes* nodes = serd_nodes_new();
+  SerdNodes* nodes = serd_nodes_new(serd_world_allocator(world));
 
   const SerdNode* s  = serd_nodes_uri(nodes, SERD_STRING("urn:s"));
   const SerdNode* p  = serd_nodes_uri(nodes, SERD_STRING("urn:p"));
@@ -1052,7 +1090,7 @@ test_write_flat_range(SerdWorld* world, const unsigned n_quads)
   serd_model_add(model, s, p, b2, NULL);
   serd_model_add(model, b2, p, o, NULL);
 
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdEnv*         env    = serd_env_new(world, SERD_EMPTY_STRING());
   SerdOutputStream out    = serd_open_output_buffer(&buffer);
 
@@ -1083,7 +1121,7 @@ test_write_flat_range(SerdWorld* world, const unsigned n_quads)
   assert(str);
   assert(!strcmp(str, expected));
 
-  serd_free(buffer.buf);
+  serd_free(NULL, buffer.buf);
   serd_writer_free(writer);
   serd_model_free(model);
   serd_env_free(env);
@@ -1097,7 +1135,7 @@ test_write_bad_list(SerdWorld* world, const unsigned n_quads)
   (void)n_quads;
 
   SerdModel* model = serd_model_new(world, SERD_ORDER_SPO, SERD_STORE_GRAPHS);
-  SerdNodes* nodes = serd_nodes_new();
+  SerdNodes* nodes = serd_nodes_new(serd_world_allocator(world));
 
   serd_model_add_index(model, SERD_ORDER_OPS);
 
@@ -1123,7 +1161,7 @@ test_write_bad_list(SerdWorld* world, const unsigned n_quads)
   serd_model_add(model, list2, prest, norest, NULL);
   serd_model_add(model, norest, pfirst, val2, NULL);
 
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdEnv*         env    = serd_env_new(world, SERD_EMPTY_STRING());
   SerdOutputStream out    = serd_open_output_buffer(&buffer);
 
@@ -1149,7 +1187,7 @@ test_write_bad_list(SerdWorld* world, const unsigned n_quads)
   assert(str);
   assert(!strcmp(str, expected));
 
-  free(buffer.buf);
+  serd_free(NULL, buffer.buf);
   serd_writer_free(writer);
   serd_close_output(&out);
   serd_model_free(model);
@@ -1164,7 +1202,7 @@ test_write_infinite_list(SerdWorld* world, const unsigned n_quads)
   (void)n_quads;
 
   SerdModel* model = serd_model_new(world, SERD_ORDER_SPO, SERD_STORE_GRAPHS);
-  SerdNodes* nodes = serd_nodes_new();
+  SerdNodes* nodes = serd_nodes_new(serd_world_allocator(world));
 
   serd_model_add_index(model, SERD_ORDER_OPS);
 
@@ -1185,7 +1223,7 @@ test_write_infinite_list(SerdWorld* world, const unsigned n_quads)
   serd_model_add(model, list2, pfirst, val2, NULL);
   serd_model_add(model, list2, prest, list1, NULL);
 
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdEnv*         env    = serd_env_new(world, SERD_EMPTY_STRING());
   SerdOutputStream out    = serd_open_output_buffer(&buffer);
 
@@ -1217,7 +1255,7 @@ test_write_infinite_list(SerdWorld* world, const unsigned n_quads)
   assert(str);
   assert(!strcmp(str, expected));
 
-  free(buffer.buf);
+  serd_free(NULL, buffer.buf);
   serd_writer_free(writer);
   serd_close_output(&out);
   serd_model_free(model);
@@ -1253,7 +1291,7 @@ test_write_error_in_list_subject(SerdWorld* world, const unsigned n_quads)
   serd_set_log_func(world, expected_error, NULL);
 
   SerdModel* model = serd_model_new(world, SERD_ORDER_SPO, 0u);
-  SerdNodes* nodes = serd_nodes_new();
+  SerdNodes* nodes = serd_nodes_new(serd_world_allocator(world));
 
   serd_model_add_index(model, SERD_ORDER_OPS);
 
@@ -1310,7 +1348,7 @@ test_write_error_in_list_object(SerdWorld* world, const unsigned n_quads)
   serd_set_log_func(world, expected_error, NULL);
 
   SerdModel* model = serd_model_new(world, SERD_ORDER_SPO, 0u);
-  SerdNodes* nodes = serd_nodes_new();
+  SerdNodes* nodes = serd_nodes_new(serd_world_allocator(world));
 
   serd_model_add_index(model, SERD_ORDER_OPS);
 
@@ -1367,7 +1405,8 @@ main(void)
 
   typedef int (*TestFunc)(SerdWorld*, unsigned);
 
-  const TestFunc tests[] = {test_free_null,
+  const TestFunc tests[] = {test_failed_new_alloc,
+                            test_free_null,
                             test_get_world,
                             test_get_default_order,
                             test_get_flags,
@@ -1401,7 +1440,7 @@ main(void)
                             test_write_error_in_list_object,
                             NULL};
 
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   int        ret   = 0;
 
   for (const TestFunc* t = tests; *t; ++t) {
diff --git a/test/test_node.c b/test/test_node.c
index 41ee6209..5c053294 100644
--- a/test/test_node.c
+++ b/test/test_node.c
@@ -59,23 +59,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
@@ -84,12 +84,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
@@ -123,7 +123,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]);
+    SerdNode*   node     = serd_new_decimal(NULL, test_values[i]);
     const char* node_str = serd_node_string(node);
     assert(!strcmp(node_str, test_strings[i]));
 
@@ -136,7 +136,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);
   }
 }
 
@@ -148,7 +148,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]));
 
@@ -161,7 +161,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);
   }
 }
 
@@ -171,14 +171,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
@@ -195,21 +195,23 @@ 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), SERD_EMPTY_STRING());
+    serd_new_base64(NULL, blob, sizeof(blob), SERD_EMPTY_STRING());
 
   assert(isnan(serd_get_double(base64)));
-  serd_node_free(base64);
+  serd_node_free(NULL, base64);
 
   SERD_RESTORE_WARNINGS
 }
@@ -222,7 +224,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]));
 
@@ -235,7 +237,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);
   }
 }
 
@@ -245,14 +247,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
@@ -267,31 +269,34 @@ 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
 test_integer(void)
 {
-  assert(!serd_new_integer(42, SERD_STRING("notauri")));
+  assert(!serd_new_integer(NULL, 42, SERD_STRING("notauri")));
 
   const int64_t test_values[]  = {0, -0, -23, 23, -12340, 1000, -1000};
   const char*   test_strings[] = {
     "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], SERD_EMPTY_STRING());
+    SerdNode* node =
+      serd_new_integer(NULL, test_values[i], SERD_EMPTY_STRING());
     const char* node_str = serd_node_string(node);
     assert(!strcmp(node_str, test_strings[i]));
     const size_t len = strlen(node_str);
@@ -302,7 +307,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);
   }
 }
 
@@ -312,12 +317,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
@@ -336,8 +341,8 @@ test_get_integer(void)
 static void
 test_base64(void)
 {
-  assert(!serd_new_base64(&SERD_URI_NULL, 1, SERD_STRING("notauri")));
-  assert(!serd_new_base64(&SERD_URI_NULL, 0, SERD_EMPTY_STRING()));
+  assert(!serd_new_base64(NULL, &SERD_URI_NULL, 1, SERD_STRING("notauri")));
+  assert(!serd_new_base64(NULL, &SERD_URI_NULL, 0, SERD_EMPTY_STRING()));
 
   // Test valid base64 blobs with a range of sizes
   for (size_t size = 1; size < 256; ++size) {
@@ -346,7 +351,7 @@ test_base64(void)
       data[i] = (uint8_t)((size + i) % 256);
     }
 
-    SerdNode*    blob     = serd_new_base64(data, size, SERD_EMPTY_STRING());
+    SerdNode*    blob = serd_new_base64(NULL, data, size, SERD_EMPTY_STRING());
     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);
@@ -365,8 +370,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);
   }
 }
@@ -377,7 +382,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);
 
@@ -392,7 +397,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
@@ -402,14 +407,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
@@ -420,69 +427,75 @@ 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_syntax(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));
-  serd_node_free(hello);
+  serd_node_free(NULL, hello);
 }
 
 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
 test_new(void)
 {
-  assert(!serd_node_new(SERD_URI,
+  assert(!serd_node_new(NULL,
+                        SERD_URI,
                         SERD_STRING("http://example.org/"),
                         SERD_HAS_DATATYPE,
                         SERD_STRING("http://example.org/uris/cant/have/me")));
 
-  assert(!serd_node_new(SERD_URI,
+  assert(!serd_node_new(NULL,
+                        SERD_URI,
                         SERD_STRING("http://example.org/"),
                         SERD_HAS_LANGUAGE,
                         SERD_STRING("in-valid")));
 
-  assert(!serd_node_new(SERD_BLANK,
+  assert(!serd_node_new(NULL,
+                        SERD_BLANK,
                         SERD_STRING("b0"),
                         SERD_HAS_DATATYPE,
                         SERD_STRING("http://example.org/uris/cant/have/me")));
 
-  assert(!serd_node_new(
-    SERD_BLANK, SERD_STRING("b0"), SERD_HAS_LANGUAGE, SERD_STRING("in-valid")));
+  assert(!serd_node_new(NULL,
+                        SERD_BLANK,
+                        SERD_STRING("b0"),
+                        SERD_HAS_LANGUAGE,
+                        SERD_STRING("in-valid")));
 }
 
 static void
@@ -491,35 +504,46 @@ test_literal(void)
   static const SerdStringView hello_str = SERD_STRING("hello");
   static 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));
 
@@ -529,11 +553,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));
 
@@ -542,50 +567,53 @@ 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_token(SERD_BLANK, SERD_STRING("b0"));
+  SerdNode* blank = serd_new_token(NULL, SERD_BLANK, 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_token(
-    SERD_URI, SERD_STRING("http://www.w3.org/2001/XMLSchema#short"));
+    NULL, SERD_URI, 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"));
 
   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, SERD_EMPTY_STRING());
-  SerdNode* short_integer = serd_new_integer(4, SERD_STRING(NS_XSD "short"));
-  SerdNode* blank         = serd_new_token(SERD_BLANK, SERD_STRING("b1"));
+  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, SERD_EMPTY_STRING());
+  SerdNode* short_integer =
+    serd_new_integer(NULL, 4, SERD_STRING(NS_XSD "short"));
+  SerdNode* blank = serd_new_token(NULL, SERD_BLANK, SERD_STRING("b1"));
 
-  SerdNode* uri = serd_new_uri(SERD_STRING("http://example.org/"));
+  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"));
 
@@ -602,19 +630,19 @@ test_compare(void)
   assert(serd_node_compare(integer, short_integer) < 0);
   assert(serd_node_compare(aardvark, badger) < 0);
 
-  serd_node_free(uri);
-  serd_node_free(blank);
-  serd_node_free(short_integer);
-  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, short_integer);
+  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_node_syntax.c b/test/test_node_syntax.c
index d9b0afbb..582ba8aa 100644
--- a/test/test_node_syntax.c
+++ b/test/test_node_syntax.c
@@ -16,12 +16,53 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
 #include <stdbool.h>
 #include <string.h>
 
+static void
+test_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdNode* const node = serd_new_string(&allocator.base, SERD_STRING("node"));
+
+  // Successfully convert a node to count the number of allocations
+
+  const size_t n_setup_allocs = allocator.n_allocations;
+
+  char* const str =
+    serd_node_to_syntax(&allocator.base, node, SERD_TURTLE, NULL);
+
+  SerdNode* const copy =
+    serd_node_from_syntax(&allocator.base, str, SERD_TURTLE, NULL);
+
+  // Test that each allocation failing is handled gracefully
+  const size_t n_new_allocs = allocator.n_allocations - n_setup_allocs;
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    char* const s =
+      serd_node_to_syntax(&allocator.base, node, SERD_TURTLE, NULL);
+
+    SerdNode* const c =
+      serd_node_from_syntax(&allocator.base, str, SERD_TURTLE, NULL);
+
+    assert(!s || !c);
+
+    serd_free(&allocator.base, s);
+    serd_node_free(&allocator.base, c);
+  }
+
+  serd_node_free(&allocator.base, copy);
+  serd_free(&allocator.base, str);
+  serd_node_free(&allocator.base, node);
+}
+
 static bool
 check(SerdWorld* const  world,
       const SerdSyntax  syntax,
@@ -31,14 +72,14 @@ check(SerdWorld* const  world,
   SerdEnv* const env =
     serd_env_new(world, SERD_STRING("http://example.org/base/"));
 
-  char* const     str  = serd_node_to_syntax(node, syntax, env);
-  SerdNode* const copy = serd_node_from_syntax(str, syntax, env);
+  char* const     str  = serd_node_to_syntax(NULL, node, syntax, env);
+  SerdNode* const copy = serd_node_from_syntax(NULL, str, syntax, env);
 
   const bool success = !strcmp(str, expected) && serd_node_equals(copy, node);
 
-  serd_node_free(copy);
-  serd_free(str);
-  serd_node_free(node);
+  serd_node_free(serd_world_allocator(world), copy);
+  serd_free(serd_world_allocator(world), str);
+  serd_node_free(NULL, node);
   serd_env_free(env);
   return success;
 }
@@ -54,107 +95,111 @@ test_common(SerdWorld* const world, const SerdSyntax syntax)
   static const SerdStringView num_type =
     SERD_STRING("http://example.org/Decimal");
 
+  assert(check(
+    world, syntax, serd_new_string(NULL, SERD_STRING("node")), "\"node\""));
+
   assert(
-    check(world, syntax, serd_new_string(SERD_STRING("node")), "\"node\""));
+    check(world,
+          syntax,
+          serd_new_literal(
+            NULL, SERD_STRING("hallo"), SERD_HAS_LANGUAGE, SERD_STRING("de")),
+          "\"hallo\"@de"));
 
-  assert(check(world,
-               syntax,
-               serd_new_literal(
-                 SERD_STRING("hallo"), SERD_HAS_LANGUAGE, SERD_STRING("de")),
-               "\"hallo\"@de"));
+  assert(
+    check(world,
+          syntax,
+          serd_new_literal(NULL, SERD_STRING("X"), SERD_HAS_DATATYPE, datatype),
+          "\"X\"^^<http://example.org/Datatype>"));
 
   assert(check(world,
                syntax,
-               serd_new_literal(SERD_STRING("X"), SERD_HAS_DATATYPE, datatype),
-               "\"X\"^^<http://example.org/Datatype>"));
+               serd_new_token(NULL, SERD_BLANK, SERD_STRING("blank")),
+               "_:blank"));
 
   assert(check(world,
                syntax,
-               serd_new_token(SERD_BLANK, SERD_STRING("blank")),
-               "_:blank"));
-
-  assert(check(
-    world, syntax, serd_new_token(SERD_BLANK, SERD_STRING("b0")), "_:b0"));
+               serd_new_token(NULL, SERD_BLANK, SERD_STRING("b0")),
+               "_:b0"));
 
   assert(check(world,
                syntax,
-               serd_new_token(SERD_BLANK, SERD_STRING("named1")),
+               serd_new_token(NULL, SERD_BLANK, SERD_STRING("named1")),
                "_:named1"));
 
   assert(check(world,
                syntax,
-               serd_new_uri(SERD_STRING("http://example.org/")),
+               serd_new_uri(NULL, SERD_STRING("http://example.org/")),
                "<http://example.org/>"));
 
   assert(check(world,
                syntax,
-               serd_new_double(1.25),
+               serd_new_double(NULL, 1.25),
                "\"1.25E0\"^^<http://www.w3.org/2001/XMLSchema#double>"));
 
   assert(check(world,
                syntax,
-               serd_new_float(1.25),
+               serd_new_float(NULL, 1.25),
                "\"1.25E0\"^^<http://www.w3.org/2001/XMLSchema#float>"));
 
   assert(check(world,
                syntax,
-               serd_new_integer(1234, num_type),
+               serd_new_integer(NULL, 1234, num_type),
                "\"1234\"^^<http://example.org/Decimal>"));
 
   assert(
     check(world,
           syntax,
-          serd_new_base64(data, sizeof(data), SERD_EMPTY_STRING()),
+          serd_new_base64(NULL, data, sizeof(data), SERD_EMPTY_STRING()),
           "\"BAAAAAIAAAA=\"^^<http://www.w3.org/2001/XMLSchema#base64Binary>"));
 }
 
 static void
 test_ntriples(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
 
   test_common(world, SERD_NTRIPLES);
 
   {
     // No relative URIs in NTriples, so converting one fails without an env
-    SerdNode* const rel = serd_new_uri(SERD_STRING("rel/uri"));
-    assert(!serd_node_to_syntax(rel, SERD_NTRIPLES, NULL));
-    assert(!serd_node_from_syntax("<rel/uri>", SERD_NTRIPLES, NULL));
+    SerdNode* const rel = serd_new_uri(NULL, SERD_STRING("rel/uri"));
+    assert(!serd_node_to_syntax(NULL, rel, SERD_NTRIPLES, NULL));
+    assert(!serd_node_from_syntax(NULL, "<rel/uri>", SERD_NTRIPLES, NULL));
 
     // If a relative URI can be expanded then all's well
     SerdEnv* const env =
       serd_env_new(world, SERD_STRING("http://example.org/base/"));
-    char* const str = serd_node_to_syntax(rel, SERD_NTRIPLES, env);
+    char* const str = serd_node_to_syntax(NULL, rel, SERD_NTRIPLES, env);
     assert(!strcmp(str, "<http://example.org/base/rel/uri>"));
 
-    SerdNode* const copy = serd_node_from_syntax(str, SERD_NTRIPLES, env);
+    SerdNode* const copy = serd_node_from_syntax(NULL, str, SERD_NTRIPLES, env);
 
     assert(!strcmp(serd_node_string(copy), "http://example.org/base/rel/uri"));
 
-    serd_node_free(copy);
+    serd_node_free(serd_world_allocator(world), copy);
     serd_env_free(env);
-    serd_free(str);
-    serd_node_free(rel);
+    serd_free(serd_world_allocator(world), str);
+    serd_node_free(NULL, rel);
   }
 
   assert(check(world,
                SERD_NTRIPLES,
-               serd_new_decimal(1.25),
+               serd_new_decimal(NULL, 1.25),
                "\"1.25\"^^<http://www.w3.org/2001/XMLSchema#decimal>"));
 
   assert(check(world,
                SERD_NTRIPLES,
-               serd_new_integer(1234, SERD_EMPTY_STRING()),
+               serd_new_integer(NULL, 1234, SERD_EMPTY_STRING()),
                "\"1234\"^^<http://www.w3.org/2001/XMLSchema#integer>"));
 
   assert(check(world,
                SERD_NTRIPLES,
-               serd_new_boolean(true),
+               serd_new_boolean(NULL, true),
                "\"true\"^^<http://www.w3.org/2001/XMLSchema#boolean>"));
 
   assert(check(world,
                SERD_NTRIPLES,
-               serd_new_boolean(false),
+               serd_new_boolean(NULL, false),
                "\"false\"^^<http://www.w3.org/2001/XMLSchema#boolean>"));
 
   serd_world_free(world);
@@ -166,22 +211,27 @@ test_turtle(void)
   static const SerdStringView xsd_integer =
     SERD_STRING("http://www.w3.org/2001/XMLSchema#integer");
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
 
   test_common(world, SERD_TURTLE);
 
-  check(world, SERD_TURTLE, serd_new_uri(SERD_STRING("rel/uri")), "<rel/uri>");
+  check(world,
+        SERD_TURTLE,
+        serd_new_uri(NULL, SERD_STRING("rel/uri")),
+        "<rel/uri>");
 
-  assert(check(world, SERD_TURTLE, serd_new_decimal(1.25), "1.25"));
+  assert(check(world, SERD_TURTLE, serd_new_decimal(NULL, 1.25), "1.25"));
 
-  assert(check(
-    world, SERD_TURTLE, serd_new_integer(1234, SERD_EMPTY_STRING()), "1234"));
+  assert(check(world,
+               SERD_TURTLE,
+               serd_new_integer(NULL, 1234, SERD_EMPTY_STRING()),
+               "1234"));
 
-  assert(
-    check(world, SERD_TURTLE, serd_new_integer(1234, xsd_integer), "1234"));
+  assert(check(
+    world, SERD_TURTLE, serd_new_integer(NULL, 1234, xsd_integer), "1234"));
 
-  assert(check(world, SERD_TURTLE, serd_new_boolean(true), "true"));
-  assert(check(world, SERD_TURTLE, serd_new_boolean(false), "false"));
+  assert(check(world, SERD_TURTLE, serd_new_boolean(NULL, true), "true"));
+  assert(check(world, SERD_TURTLE, serd_new_boolean(NULL, false), "false"));
 
   serd_world_free(world);
 }
@@ -189,6 +239,7 @@ test_turtle(void)
 int
 main(void)
 {
+  test_failed_alloc();
   test_ntriples();
   test_turtle();
 
diff --git a/test/test_nodes.c b/test/test_nodes.c
index c841acc4..2cdfbc3c 100644
--- a/test/test_nodes.c
+++ b/test/test_nodes.c
@@ -16,6 +16,7 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
 #include "serd/serd.h"
 
 #include <assert.h>
@@ -26,10 +27,64 @@
 #define NS_XSD "http://www.w3.org/2001/XMLSchema#"
 
 static void
+test_new_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  // Successfully allocate a node set to count the number of allocations
+  SerdNodes* nodes = serd_nodes_new(&allocator.base);
+  assert(nodes);
+
+  // 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_nodes_new(&allocator.base));
+  }
+
+  serd_nodes_free(nodes);
+}
+
+static void
+test_intern_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdNode* const node = serd_new_string(&allocator.base, SERD_STRING("node"));
+
+  // Successfully intern a node to count the number of allocations
+  SerdNodes*      nodes     = serd_nodes_new(&allocator.base);
+  const SerdNode* interned1 = serd_nodes_intern(nodes, node);
+  assert(serd_node_equals(node, interned1));
+  assert(serd_nodes_size(nodes) == 1u);
+
+  const size_t n_new_allocs = allocator.n_allocations;
+  serd_nodes_free(nodes);
+
+  // Test that each allocation failing is handled gracefully
+  for (size_t i = 0; i < n_new_allocs; ++i) {
+    allocator.n_remaining = i;
+
+    if ((nodes = serd_nodes_new(&allocator.base))) {
+      const SerdNode* interned2 = serd_nodes_intern(nodes, node);
+      if (interned2) {
+        assert(serd_node_equals(node, interned2));
+        assert(serd_nodes_size(nodes) == 1u);
+      }
+      serd_nodes_free(nodes);
+    }
+  }
+
+  serd_node_free(&allocator.base, node);
+}
+
+static void
 test_intern(void)
 {
-  SerdNodes* nodes = serd_nodes_new();
-  SerdNode*  node  = serd_new_string(SERD_STRING("node"));
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* nodes = serd_nodes_new(allocator);
+  SerdNode*  node  = serd_new_string(NULL, SERD_STRING("node"));
 
   assert(serd_nodes_size(nodes) == 0u);
   assert(!serd_nodes_intern(nodes, NULL));
@@ -43,7 +98,7 @@ test_intern(void)
   assert(interned1 == interned2);
   assert(serd_nodes_size(nodes) == 1u);
 
-  serd_node_free(node);
+  serd_node_free(NULL, node);
   serd_nodes_free(nodes);
 }
 
@@ -52,7 +107,9 @@ test_string(void)
 {
   static const SerdStringView string = SERD_STRING("string");
 
-  SerdNodes* const      nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
   const SerdNode* const node  = serd_nodes_string(nodes, string);
 
   assert(node);
@@ -68,7 +125,9 @@ test_string(void)
 static void
 test_invalid_literal(void)
 {
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   assert(!serd_nodes_literal(nodes,
                              SERD_STRING("double meta"),
@@ -94,7 +153,9 @@ test_plain_literal(void)
   static const SerdStringView string   = SERD_STRING("string");
   static const SerdStringView language = SERD_STRING("en");
 
-  SerdNodes* const      nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
   const SerdNode* const node =
     serd_nodes_literal(nodes, string, SERD_HAS_LANGUAGE, language);
 
@@ -137,7 +198,9 @@ test_typed_literal(void)
   static const SerdStringView string   = SERD_STRING("string");
   static const SerdStringView datatype = SERD_STRING("http://example.org/Type");
 
-  SerdNodes* const      nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
   const SerdNode* const node =
     serd_nodes_literal(nodes, string, SERD_HAS_DATATYPE, datatype);
 
@@ -165,7 +228,9 @@ test_typed_literal(void)
 static void
 test_boolean(void)
 {
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   const SerdNode* const false1 = serd_nodes_boolean(nodes, false);
   const SerdNode* const false2 = serd_nodes_boolean(nodes, false);
@@ -195,7 +260,9 @@ test_boolean(void)
 static void
 test_decimal(void)
 {
-  SerdNodes* const      nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
   const SerdNode* const a     = serd_nodes_decimal(nodes, -12.3456789);
   const SerdNode* const b     = serd_nodes_decimal(nodes, -12.3456789);
 
@@ -214,7 +281,9 @@ test_decimal(void)
 static void
 test_double(void)
 {
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   const SerdNode* const a = serd_nodes_double(nodes, -1.2E3);
   const SerdNode* const b = serd_nodes_double(nodes, -1.2E3);
@@ -230,7 +299,9 @@ test_double(void)
 static void
 test_float(void)
 {
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   const SerdNode* const a = serd_nodes_float(nodes, -1.2E3f);
   const SerdNode* const b = serd_nodes_float(nodes, -1.2E3f);
@@ -246,7 +317,9 @@ test_float(void)
 static void
 test_integer(void)
 {
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   const SerdNode* const a =
     serd_nodes_integer(nodes, -1234567890, SERD_EMPTY_STRING());
@@ -271,7 +344,9 @@ test_base64(void)
 {
   static const char data[] = {'f', 'o', 'o', 'b', 'a', 'r'};
 
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   const SerdNode* const a =
     serd_nodes_base64(nodes, &data, sizeof(data), SERD_EMPTY_STRING());
@@ -308,7 +383,9 @@ test_uri(void)
 {
   static const SerdStringView string = SERD_STRING("http://example.org/");
 
-  SerdNodes* const      nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
   const SerdNode* const node  = serd_nodes_uri(nodes, string);
 
   assert(node);
@@ -326,7 +403,9 @@ test_parsed_uri(void)
 {
   static const SerdStringView string = SERD_STRING("http://example.org/");
 
-  SerdNodes* const      nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
   const SerdURIView     uri   = serd_parse_uri(string.buf);
   const SerdNode* const node  = serd_nodes_parsed_uri(nodes, uri);
 
@@ -354,7 +433,9 @@ test_blank(void)
 {
   static const SerdStringView string = SERD_STRING("b42");
 
-  SerdNodes* const      nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const      nodes = serd_nodes_new(allocator);
   const SerdNode* const node  = serd_nodes_blank(nodes, string);
 
   assert(node);
@@ -370,7 +451,9 @@ test_blank(void)
 static void
 test_deref(void)
 {
-  SerdNodes*      nodes    = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes*      nodes    = serd_nodes_new(allocator);
   const SerdNode* original = serd_nodes_string(nodes, SERD_STRING("node"));
   const SerdNode* another  = serd_nodes_string(nodes, SERD_STRING("node"));
 
@@ -397,9 +480,9 @@ test_deref(void)
   assert(!strcmp(serd_node_string(imposter), "node"));
 
   // Check that dereferencing some random unknown node doesn't crash
-  SerdNode* unmanaged = serd_new_string(SERD_STRING("unmanaged"));
+  SerdNode* unmanaged = serd_new_string(NULL, SERD_STRING("unmanaged"));
   serd_nodes_deref(nodes, unmanaged);
-  serd_node_free(unmanaged);
+  serd_node_free(NULL, unmanaged);
 
   serd_nodes_deref(nodes, NULL);
   serd_nodes_deref(nodes, imposter);
@@ -410,8 +493,10 @@ test_deref(void)
 static void
 test_get(void)
 {
-  SerdNodes* nodes = serd_nodes_new();
-  SerdNode*  node  = serd_new_string(SERD_STRING("node"));
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* nodes = serd_nodes_new(allocator);
+  SerdNode*  node  = serd_new_string(NULL, SERD_STRING("node"));
 
   assert(!serd_nodes_get(nodes, NULL));
   assert(!serd_nodes_get(nodes, node));
@@ -420,13 +505,15 @@ test_get(void)
   assert(serd_node_equals(node, interned1));
   assert(serd_nodes_get(nodes, node) == interned1);
 
-  serd_node_free(node);
+  serd_node_free(NULL, node);
   serd_nodes_free(nodes);
 }
 
 int
 main(void)
 {
+  test_new_failed_alloc();
+  test_intern_failed_alloc();
   test_intern();
   test_string();
   test_invalid_literal();
diff --git a/test/test_overflow.c b/test/test_overflow.c
index f7fdfa58..2461d713 100644
--- a/test/test_overflow.c
+++ b/test/test_overflow.c
@@ -38,7 +38,7 @@ test_size(SerdWorld* const      world,
 
   assert(reader);
 
-  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);
@@ -46,7 +46,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);
@@ -85,7 +85,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);
@@ -211,7 +211,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_read_chunk.c b/test/test_read_chunk.c
index 59f99910..507bbb35 100644
--- a/test/test_read_chunk.c
+++ b/test/test_read_chunk.c
@@ -91,7 +91,7 @@ on_event(void* handle, const SerdEvent* event)
 int
 main(void)
 {
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   SerdSink*  sink  = serd_sink_new(world, NULL, on_event, NULL);
 
   static const char* const string = "@prefix eg: <http://example.org/> .\n"
diff --git a/test/test_reader.c b/test/test_reader.c
index 80d9533b..095f736e 100644
--- a/test/test_reader.c
+++ b/test/test_reader.c
@@ -16,6 +16,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
@@ -33,6 +35,89 @@ count_statements(void* handle, const SerdEvent* event)
   return SERD_SUCCESS;
 }
 
+static void
+test_new_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  FILE* const temp = tmpfile();
+  assert(temp);
+
+  fprintf(temp, "_:s <http://example.org/p> _:o .\n");
+  fflush(temp);
+  fseek(temp, 0L, SEEK_SET);
+
+  SerdWorld* world   = serd_world_new(&allocator.base);
+  size_t     ignored = 0u;
+  SerdSink*  sink    = serd_sink_new(world, &ignored, count_statements, NULL);
+  SerdEnv*   env     = serd_env_new(world, SERD_EMPTY_STRING());
+
+  // 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, 4096);
+  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, 4096));
+  }
+
+  serd_reader_free(reader);
+  serd_env_free(env);
+  serd_sink_free(sink);
+  serd_world_free(world);
+  fclose(temp);
+}
+
+static void
+test_start_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  FILE* const temp = tmpfile();
+  assert(temp);
+
+  fprintf(temp, "_:s <http://example.org/p> _:o .\n");
+  fflush(temp);
+  fseek(temp, 0L, SEEK_SET);
+
+  SerdWorld*  world   = serd_world_new(&allocator.base);
+  size_t      ignored = 0u;
+  SerdSink*   sink    = serd_sink_new(world, &ignored, count_statements, NULL);
+  SerdEnv*    env     = serd_env_new(world, SERD_EMPTY_STRING());
+  SerdReader* reader = serd_reader_new(world, SERD_TURTLE, 0u, env, sink, 4096);
+
+  assert(reader);
+
+  SerdInputStream in = serd_open_input_stream(
+    (SerdReadFunc)fread, (SerdErrorFunc)ferror, NULL, temp);
+
+  // 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, temp);
+
+    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(temp);
+}
+
 SERD_PURE_FUNC
 static size_t
 prepare_test_read(void* buf, size_t size, size_t nmemb, void* stream)
@@ -58,7 +143,7 @@ prepare_test_error(void* stream)
 static void
 test_prepare_error(void)
 {
-  SerdWorld* const world        = serd_world_new();
+  SerdWorld* const world        = serd_world_new(NULL);
   size_t           n_statements = 0;
   FILE* const      f            = tmpfile();
 
@@ -93,7 +178,7 @@ test_prepare_error(void)
 static void
 test_read_string(void)
 {
-  SerdWorld* world        = serd_world_new();
+  SerdWorld* world        = serd_world_new(NULL);
   size_t     n_statements = 0;
 
   SerdSink* sink = serd_sink_new(world, &n_statements, count_statements, NULL);
@@ -196,7 +281,7 @@ test_read_eof_by_page(void)
   fflush(temp);
   fseek(temp, 0L, SEEK_SET);
 
-  SerdWorld* world   = serd_world_new();
+  SerdWorld* world   = serd_world_new(NULL);
   size_t     ignored = 0u;
   SerdSink*  sink    = serd_sink_new(world, &ignored, count_statements, NULL);
   SerdEnv*   env     = serd_env_new(world, SERD_EMPTY_STRING());
@@ -224,7 +309,7 @@ test_read_eof_by_page(void)
 static void
 test_read_eof_by_byte(void)
 {
-  SerdWorld* world   = serd_world_new();
+  SerdWorld* world   = serd_world_new(NULL);
   size_t     ignored = 0u;
   SerdSink*  sink    = serd_sink_new(world, &ignored, count_statements, NULL);
   SerdEnv*   env     = serd_env_new(world, SERD_EMPTY_STRING());
@@ -252,7 +337,7 @@ test_read_eof_by_byte(void)
 static void
 test_read_chunks(void)
 {
-  SerdWorld*        world        = serd_world_new();
+  SerdWorld*        world        = serd_world_new(NULL);
   size_t            n_statements = 0;
   FILE* const       f            = tmpfile();
   static const char null         = 0;
@@ -324,12 +409,13 @@ test_read_chunks(void)
 static void
 test_read_empty(void)
 {
-  SerdWorld* const world        = serd_world_new();
+  SerdWorld* const world        = serd_world_new(NULL);
   size_t           n_statements = 0;
   FILE* const      f            = tmpfile();
 
   SerdSink* const sink =
     serd_sink_new(world, &n_statements, count_statements, NULL);
+
   assert(sink);
 
   SerdEnv* const    env = serd_env_new(world, SERD_EMPTY_STRING());
@@ -377,7 +463,7 @@ check_cursor(void* handle, const SerdEvent* event)
 static void
 test_error_cursor(void)
 {
-  SerdWorld*        world  = serd_world_new();
+  SerdWorld*        world  = serd_world_new(NULL);
   bool              called = false;
   SerdSink*         sink   = serd_sink_new(world, &called, check_cursor, NULL);
   SerdEnv* const    env    = serd_env_new(world, SERD_EMPTY_STRING());
@@ -391,7 +477,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);
 
@@ -402,7 +488,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);
@@ -412,6 +498,8 @@ test_error_cursor(void)
 int
 main(void)
 {
+  test_new_failed_alloc();
+  test_start_failed_alloc();
   test_prepare_error();
   test_read_string();
   test_read_eof_by_page();
diff --git a/test/test_reader_writer.c b/test/test_reader_writer.c
index 52be8d74..69383225 100644
--- a/test/test_reader_writer.c
+++ b/test/test_reader_writer.c
@@ -36,8 +36,8 @@ count_statements(void* handle, const SerdEvent* event)
 static void
 test_writer(const char* const path)
 {
+  SerdWorld* world = serd_world_new(NULL);
   FILE*      fd    = fopen(path, "wb");
-  SerdWorld* world = serd_world_new();
   SerdEnv*   env   = serd_env_new(world, SERD_EMPTY_STRING());
   assert(fd);
 
@@ -108,7 +108,7 @@ test_writer(const char* const path)
   serd_close_output(&output);
 
   // Test buffer sink
-  SerdBuffer buffer = {NULL, 0};
+  SerdBuffer buffer = {NULL, NULL, 0};
 
   output = serd_open_output_buffer(&buffer);
   writer = serd_writer_new(world, SERD_TURTLE, 0, env, &output, 1);
@@ -124,7 +124,7 @@ test_writer(const char* const path)
 
   assert(out);
   assert(!strcmp(out, "@base <http://example.org/base> .\n"));
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
   serd_env_free(env);
   serd_world_free(world);
@@ -133,7 +133,7 @@ test_writer(const char* const path)
 static void
 test_reader(const char* path)
 {
-  SerdWorld* world        = serd_world_new();
+  SerdWorld* world        = serd_world_new(NULL);
   size_t     n_statements = 0;
 
   SerdSink* const sink =
diff --git a/test/test_sink.c b/test/test_sink.c
index 7c49cc04..9812d487 100644
--- a/test/test_sink.c
+++ b/test/test_sink.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2019-2020 David Robillard <d@drobilla.net>
+  Copyright 2019-2021 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -16,6 +16,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
@@ -95,10 +97,34 @@ on_event(void* const handle, const SerdEvent* const event)
 }
 
 static void
+test_failed_alloc(void)
+{
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  SerdWorld* const world          = serd_world_new(&allocator.base);
+  const size_t     n_world_allocs = allocator.n_allocations;
+
+  // Successfully allocate a sink to count the number of allocations
+  SerdSink* const sink = serd_sink_new(world, NULL, NULL, NULL);
+  assert(sink);
+
+  // 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_sink_new(world, NULL, NULL, NULL));
+  }
+
+  serd_sink_free(sink);
+  serd_world_free(world);
+}
+
+static void
 test_callbacks(void)
 {
-  SerdWorld* const world = serd_world_new();
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdWorld* const     world     = serd_world_new(NULL);
+  SerdAllocator* const allocator = serd_world_allocator(world);
+  SerdNodes* const     nodes     = serd_nodes_new(allocator);
 
   const SerdNode* base  = serd_nodes_uri(nodes, SERD_STRING(NS_EG));
   const SerdNode* name  = serd_nodes_string(nodes, SERD_STRING("eg"));
@@ -108,7 +134,7 @@ test_callbacks(void)
   SerdEnv* env = serd_env_new(world, serd_node_string_view(base));
 
   SerdStatement* const statement =
-    serd_statement_new(base, uri, blank, NULL, NULL);
+    serd_statement_new(allocator, base, uri, blank, NULL, NULL);
 
   State state = {0, 0, 0, 0, 0, SERD_SUCCESS};
 
@@ -162,7 +188,7 @@ test_callbacks(void)
 
   serd_sink_free(sink);
 
-  serd_statement_free(statement);
+  serd_statement_free(allocator, statement);
   serd_env_free(env);
   serd_nodes_free(nodes);
   serd_world_free(world);
@@ -174,7 +200,7 @@ test_free(void)
   // Free of null should (as always) not crash
   serd_sink_free(NULL);
 
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
 
   // Set up a sink with dynamically allocated data and a free function
   uintptr_t* data = (uintptr_t*)calloc(1, sizeof(uintptr_t));
@@ -189,6 +215,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 45605dd1..b3f2c483 100644
--- a/test/test_statement.c
+++ b/test/test_statement.c
@@ -16,19 +16,78 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
 #include <stddef.h>
+#include <stdint.h>
 
 #define NS_EG "http://example.org/"
 
 static void
+test_invalid_new(void)
+{
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  assert(!serd_statement_copy(allocator, NULL));
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  const SerdNode* const s = serd_nodes_string(nodes, SERD_STRING("s"));
+  const SerdNode* const u = serd_nodes_uri(nodes, SERD_STRING(NS_EG "u"));
+  const SerdNode* const b = serd_nodes_blank(nodes, SERD_STRING(NS_EG "b"));
+
+  // S, P, and G may not be strings (must be resources)
+  assert(!serd_statement_new(allocator, s, u, u, u, NULL));
+  assert(!serd_statement_new(allocator, u, s, u, u, NULL));
+  assert(!serd_statement_new(allocator, u, u, u, s, NULL));
+
+  // P may not be a blank node
+  assert(!serd_statement_new(allocator, u, b, u, u, NULL));
+
+  serd_nodes_free(nodes);
+}
+
+static void
 test_copy(void)
 {
-  assert(!serd_statement_copy(NULL));
+  assert(!serd_statement_copy(NULL, NULL));
+
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  assert(!serd_statement_copy(allocator, NULL));
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
+
+  const SerdNode* const s = serd_nodes_uri(nodes, SERD_STRING(NS_EG "s"));
+  const SerdNode* const p = serd_nodes_uri(nodes, SERD_STRING(NS_EG "p"));
+  const SerdNode* const o = serd_nodes_uri(nodes, SERD_STRING(NS_EG "o"));
+  const SerdNode* const g = serd_nodes_uri(nodes, SERD_STRING(NS_EG "g"));
+
+  SerdStatement* const statement =
+    serd_statement_new(allocator, s, p, o, g, NULL);
+
+  SerdStatement* const copy = serd_statement_copy(allocator, statement);
+
+  assert(serd_statement_equals(copy, statement));
+
+  serd_statement_free(allocator, copy);
+  serd_statement_free(allocator, statement);
+  serd_nodes_free(nodes);
+}
+
+static void
+test_copy_with_caret(void)
+{
+  assert(!serd_statement_copy(NULL, NULL));
 
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  assert(!serd_statement_copy(allocator, NULL));
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   const SerdNode* const f = serd_nodes_string(nodes, SERD_STRING("file"));
   const SerdNode* const s = serd_nodes_uri(nodes, SERD_STRING(NS_EG "s"));
@@ -36,29 +95,35 @@ test_copy(void)
   const SerdNode* const o = serd_nodes_uri(nodes, SERD_STRING(NS_EG "o"));
   const SerdNode* const g = serd_nodes_uri(nodes, 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(allocator, f, 1, 1);
+
+  SerdStatement* const statement =
+    serd_statement_new(allocator, s, p, o, g, caret);
+
+  SerdStatement* const copy = serd_statement_copy(allocator, 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_statement_free(allocator, copy);
+  serd_caret_free(allocator, caret);
+  serd_statement_free(allocator, statement);
   serd_nodes_free(nodes);
 }
 
 static void
 test_free(void)
 {
-  serd_statement_free(NULL);
+  serd_statement_free(serd_default_allocator(), NULL);
+  serd_statement_free(NULL, NULL);
 }
 
 static void
 test_fields(void)
 {
-  SerdNodes* const nodes = serd_nodes_new();
+  SerdAllocator* const allocator = serd_default_allocator();
+
+  SerdNodes* const nodes = serd_nodes_new(allocator);
 
   const SerdNode* const f = serd_nodes_string(nodes, SERD_STRING("file"));
   const SerdNode* const s = serd_nodes_uri(nodes, SERD_STRING(NS_EG "s"));
@@ -66,8 +131,10 @@ test_fields(void)
   const SerdNode* const o = serd_nodes_uri(nodes, SERD_STRING(NS_EG "o"));
   const SerdNode* const g = serd_nodes_uri(nodes, 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(allocator, f, 1, 1);
+
+  SerdStatement* const statement =
+    serd_statement_new(allocator, s, p, o, g, caret);
 
   assert(serd_statement_equals(statement, statement));
   assert(!serd_statement_equals(statement, NULL));
@@ -94,33 +161,86 @@ 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(allocator, o, p, o, g, caret);
   assert(!serd_statement_equals(statement, diff_s));
-  serd_statement_free(diff_s);
+  serd_statement_free(allocator, diff_s);
 
-  SerdStatement* const diff_p = serd_statement_new(s, o, o, g, caret);
+  SerdStatement* const diff_p =
+    serd_statement_new(allocator, s, o, o, g, caret);
   assert(!serd_statement_equals(statement, diff_p));
-  serd_statement_free(diff_p);
+  serd_statement_free(allocator, diff_p);
 
-  SerdStatement* const diff_o = serd_statement_new(s, p, s, g, caret);
+  SerdStatement* const diff_o =
+    serd_statement_new(allocator, s, p, s, g, caret);
   assert(!serd_statement_equals(statement, diff_o));
-  serd_statement_free(diff_o);
+  serd_statement_free(allocator, diff_o);
 
-  SerdStatement* const diff_g = serd_statement_new(s, p, o, s, caret);
+  SerdStatement* const diff_g =
+    serd_statement_new(allocator, s, p, o, s, caret);
   assert(!serd_statement_equals(statement, diff_g));
-  serd_statement_free(diff_g);
+  serd_statement_free(allocator, diff_g);
+
+  serd_statement_free(allocator, statement);
+  serd_caret_free(allocator, caret);
+  serd_nodes_free(nodes);
+}
+
+static void
+test_failed_alloc(void)
+{
+  SerdNodes* const nodes = serd_nodes_new(serd_default_allocator());
+
+  const SerdNode* const f = serd_nodes_string(nodes, SERD_STRING("file"));
+  const SerdNode* const s = serd_nodes_uri(nodes, SERD_STRING(NS_EG "s"));
+  const SerdNode* const p = serd_nodes_uri(nodes, SERD_STRING(NS_EG "p"));
+  const SerdNode* const o = serd_nodes_uri(nodes, SERD_STRING(NS_EG "o"));
+  const SerdNode* const g = serd_nodes_uri(nodes, SERD_STRING(NS_EG "g"));
 
-  serd_statement_free(statement);
-  serd_caret_free(caret);
+  SerdCaret* const caret = serd_caret_new(serd_default_allocator(), f, 1, 1);
+
+  SerdFailingAllocator allocator = serd_failing_allocator();
+
+  // Successfully allocate a statement to count the number of allocations
+  SerdStatement* const statement =
+    serd_statement_new(&allocator.base, s, p, o, g, caret);
+  assert(statement);
+
+  // 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_statement_new(&allocator.base, s, p, o, g, caret));
+  }
+
+  // Successfully copy the statement to count the number of allocations
+  allocator.n_allocations   = 0;
+  allocator.n_remaining     = SIZE_MAX;
+  SerdStatement* const copy = serd_statement_copy(&allocator.base, statement);
+  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_statement_copy(&allocator.base, statement));
+  }
+
+  serd_statement_free(&allocator.base, copy);
+  serd_statement_free(&allocator.base, statement);
+  serd_caret_free(&allocator.base, caret);
   serd_nodes_free(nodes);
 }
 
 int
 main(void)
 {
+  test_invalid_new();
   test_copy();
+  test_copy_with_caret();
   test_free();
   test_fields();
+  test_failed_alloc();
 
   return 0;
 }
diff --git a/test/test_string.c b/test/test_string.c
index c91284bb..cdc4bc33 100644
--- a/test/test_string.c
+++ b/test/test_string.c
@@ -48,7 +48,7 @@ test_strerror(void)
 static void
 test_canonical_path(const char* const path)
 {
-  char* const canonical = serd_canonical_path(path);
+  char* const canonical = serd_canonical_path(NULL, path);
 
   assert(canonical);
   assert(!strstr(canonical, "../"));
@@ -62,7 +62,7 @@ test_canonical_path(const char* const path)
   assert(canonical[0] == '/');
 #endif
 
-  serd_free(canonical);
+  serd_free(NULL, canonical);
 }
 
 int
diff --git a/test/test_terse_write.c b/test/test_terse_write.c
index 02f6bebf..480bb880 100644
--- a/test/test_terse_write.c
+++ b/test/test_terse_write.c
@@ -20,7 +20,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#"
@@ -42,10 +41,10 @@ check_output(SerdWriter* writer, SerdBuffer* buffer, const char* expected)
 static int
 test(void)
 {
-  SerdBuffer buffer = {NULL, 0};
-  SerdWorld* world  = serd_world_new();
+  SerdWorld* world  = serd_world_new(NULL);
+  SerdBuffer buffer = {NULL, NULL, 0};
   SerdEnv*   env    = serd_env_new(world, SERD_EMPTY_STRING());
-  SerdNodes* nodes  = serd_nodes_new();
+  SerdNodes* nodes  = serd_nodes_new(serd_world_allocator(world));
 
   const SerdNode* b1 = serd_nodes_blank(nodes, SERD_STRING("b1"));
   const SerdNode* l1 = serd_nodes_blank(nodes, SERD_STRING("l1"));
@@ -100,10 +99,10 @@ test(void)
 
   serd_writer_free(writer);
   serd_close_output(&output);
+  serd_free(NULL, buffer.buf);
   serd_nodes_free(nodes);
   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 5d204a71..49d72630 100644
--- a/test/test_uri.c
+++ b/test/test_uri.c
@@ -1,5 +1,5 @@
 /*
-  Copyright 2011-2020 David Robillard <d@drobilla.net>
+  Copyright 2011-2021 David Robillard <d@drobilla.net>
 
   Permission to use, copy, modify, and/or distribute this software for any
   purpose with or without fee is hereby granted, provided that the above
@@ -16,6 +16,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
@@ -24,6 +26,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"));
@@ -55,19 +86,20 @@ test_file_uri(const char* const hostname,
   }
 
   SerdNode* node =
-    serd_new_file_uri(SERD_STRING(path), SERD_OPTIONAL_STRING(hostname));
+    serd_new_file_uri(NULL, SERD_STRING(path), SERD_OPTIONAL_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*       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
@@ -80,22 +112,22 @@ test_uri_parsing(void)
   test_file_uri(NULL, "a/relative <path>", "a/relative%20%3Cpath%3E", NULL);
 
   // 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
@@ -107,12 +139,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.buf));
 
-  serd_node_free(nil);
+  serd_node_free(NULL, nil);
 }
 
 static void
@@ -161,11 +193,11 @@ check_rel_uri(const char*     uri_string,
     !root || serd_uri_is_within(uri, serd_node_uri_view(root));
 
   SerdNode* const rel =
-    is_within ? serd_new_parsed_uri(serd_relative_uri(uri, base_uri))
-              : serd_new_uri(SERD_STRING(uri_string));
+    is_within ? serd_new_parsed_uri(NULL, serd_relative_uri(uri, base_uri))
+              : serd_new_uri(NULL, SERD_STRING(uri_string));
 
   const int ret = strcmp(serd_node_string(rel), expected);
-  serd_node_free(rel);
+  serd_node_free(NULL, rel);
   assert(!ret);
 }
 
@@ -173,9 +205,10 @@ static void
 test_relative_uri(void)
 {
   SerdNode* const root =
-    serd_new_uri(SERD_STRING("http://example.org/a/b/ignored"));
+    serd_new_uri(NULL, SERD_STRING("http://example.org/a/b/ignored"));
 
-  SerdNode* const base = serd_new_uri(SERD_STRING("http://example.org/a/b/c/"));
+  SerdNode* const base =
+    serd_new_uri(NULL, SERD_STRING("http://example.org/a/b/c/"));
 
   check_rel_uri("http://example.org/a/b/c/foo", base, NULL, "foo");
   check_rel_uri("http://example.org/a/", base, NULL, "../../");
@@ -189,10 +222,10 @@ test_relative_uri(void)
     const SerdURIView ref  = serd_parse_uri("child");
     const SerdURIView abs  = serd_resolve_uri(ref, serd_node_uri_view(base));
     const SerdURIView rel  = serd_relative_uri(abs, serd_node_uri_view(root));
-    SerdNode* const   node = serd_new_parsed_uri(rel);
+    SerdNode* const   node = serd_new_parsed_uri(NULL, rel);
 
     assert(!strcmp(serd_node_string(node), "c/child"));
-    serd_node_free(node);
+    serd_node_free(NULL, node);
   }
   {
     // Check failure when path_prefix is not available for use
@@ -204,8 +237,8 @@ test_relative_uri(void)
     assert(!memcmp(&upref, &SERD_URI_NULL, sizeof(ref)));
   }
 
-  serd_node_free(base);
-  serd_node_free(root);
+  serd_node_free(NULL, base);
+  serd_node_free(NULL, root);
 }
 
 static void
@@ -221,15 +254,16 @@ test_uri_resolution(void)
   const SerdURIView rel_foo_uri  = serd_relative_uri(abs_foo_uri, base_uri);
   const SerdURIView resolved_uri = serd_resolve_uri(rel_foo_uri, base_uri);
 
-  SerdNode* const resolved = serd_new_parsed_uri(resolved_uri);
+  SerdNode* const resolved = serd_new_parsed_uri(NULL, resolved_uri);
   assert(!strcmp(serd_node_string(resolved), "http://example.org/a/b/c/foo"));
 
-  serd_node_free(resolved);
+  serd_node_free(NULL, resolved);
 }
 
 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 8045d1bf..23958b19 100644
--- a/test/test_world.c
+++ b/test/test_world.c
@@ -16,6 +16,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
@@ -23,9 +25,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) {
@@ -41,7 +62,7 @@ test_get_blank(void)
 static void
 test_nodes(void)
 {
-  SerdWorld* const world = serd_world_new();
+  SerdWorld* const world = serd_world_new(NULL);
   SerdNodes* const nodes = serd_world_nodes(world);
 
   assert(serd_nodes_size(nodes) > 0u);
@@ -52,6 +73,7 @@ test_nodes(void)
 int
 main(void)
 {
+  test_new_failed_alloc();
   test_get_blank();
   test_nodes();
 
diff --git a/test/test_writer.c b/test/test_writer.c
index 7e2386be..23ac222c 100644
--- a/test/test_writer.c
+++ b/test/test_writer.c
@@ -16,6 +16,8 @@
 
 #undef NDEBUG
 
+#include "failing_allocator.h"
+
 #include "serd/serd.h"
 
 #include <assert.h>
@@ -28,23 +30,112 @@
 static void
 test_writer_new(void)
 {
-  SerdWorld*       world  = serd_world_new();
+  SerdWorld*       world  = serd_world_new(NULL);
   SerdEnv*         env    = serd_env_new(world, SERD_EMPTY_STRING());
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {serd_world_allocator(world), NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   assert(!serd_writer_new(world, SERD_TURTLE, 0u, env, &output, 0));
 
+  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(world, 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, 1);
+
+  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, 1));
+  }
+
+  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);
+  SerdNodes*       nodes  = serd_world_nodes(world);
+  SerdEnv*         env    = serd_env_new(world, SERD_EMPTY_STRING());
+  SerdBuffer       buffer = {&allocator.base, NULL, 0};
+  SerdOutputStream output = serd_open_output_buffer(&buffer);
+
+  const SerdNode* s =
+    serd_nodes_uri(nodes, SERD_STRING("http://example.org/s"));
+
+  const SerdNode* p1 =
+    serd_nodes_uri(nodes, SERD_STRING("http://example.org/p"));
+
+  const SerdNode* p2 = serd_nodes_uri(
+    nodes, SERD_STRING("http://example.org/dramatically/longer/predicate"));
+
+  const SerdNode* o = serd_nodes_blank(nodes, 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, 1);
+  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, 1))) {
+      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_world_free(world);
 }
 
 static void
 test_write_bad_event(void)
 {
-  SerdWorld*       world  = serd_world_new();
+  SerdWorld*       world  = serd_world_new(NULL);
   SerdEnv*         env    = serd_env_new(world, SERD_EMPTY_STRING());
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer = serd_writer_new(world, SERD_TURTLE, 0u, env, &output, 1);
@@ -60,7 +151,7 @@ test_write_bad_event(void)
 
   assert(out);
   assert(!strcmp(out, ""));
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
   serd_writer_free(writer);
   serd_env_free(env);
@@ -70,10 +161,10 @@ test_write_bad_event(void)
 static void
 test_write_long_literal(void)
 {
-  SerdWorld*       world  = serd_world_new();
+  SerdWorld*       world  = serd_world_new(NULL);
   SerdNodes*       nodes  = serd_world_nodes(world);
   SerdEnv*         env    = serd_env_new(world, SERD_EMPTY_STRING());
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer = serd_writer_new(world, SERD_TURTLE, 0u, env, &output, 1);
@@ -106,7 +197,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);
 }
@@ -126,7 +217,7 @@ null_sink(const void* const buf,
 static void
 test_writer_stack_overflow(void)
 {
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   SerdNodes* nodes = serd_world_nodes(world);
   SerdEnv*   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
@@ -178,7 +269,7 @@ test_strict_write(void)
 {
   static const char* path = "serd_strict_write_test.ttl";
 
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   SerdNodes* nodes = serd_world_nodes(world);
   SerdEnv*   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
@@ -231,7 +322,7 @@ faulty_sink(const void* const buf,
 static void
 test_write_error(void)
 {
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   SerdNodes* nodes = serd_world_nodes(world);
   SerdEnv*   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
@@ -277,7 +368,7 @@ test_write_error(void)
 static void
 test_write_empty_syntax(void)
 {
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   SerdNodes* nodes = serd_world_nodes(world);
   SerdEnv*   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
@@ -290,7 +381,7 @@ test_write_empty_syntax(void)
   const SerdNode* o =
     serd_nodes_uri(nodes, SERD_STRING("http://example.org/o"));
 
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer =
@@ -305,7 +396,7 @@ test_write_empty_syntax(void)
 
   assert(out);
   assert(strlen(out) == 0);
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
   serd_writer_free(writer);
   serd_close_output(&output);
@@ -316,7 +407,7 @@ test_write_empty_syntax(void)
 static void
 test_write_bad_uri(void)
 {
-  SerdWorld* world = serd_world_new();
+  SerdWorld* world = serd_world_new(NULL);
   SerdNodes* nodes = serd_world_nodes(world);
   SerdEnv*   env   = serd_env_new(world, SERD_EMPTY_STRING());
 
@@ -328,7 +419,7 @@ test_write_bad_uri(void)
 
   const SerdNode* rel = serd_nodes_uri(nodes, SERD_STRING("rel"));
 
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer =
@@ -343,7 +434,7 @@ test_write_bad_uri(void)
   assert(st == SERD_BAD_ARG);
 
   serd_close_output(&output);
-  serd_free(buffer.buf);
+  serd_free(NULL, buffer.buf);
   serd_writer_free(writer);
   serd_close_output(&output);
   serd_env_free(env);
@@ -353,10 +444,10 @@ test_write_bad_uri(void)
 static void
 check_pname_escape(const char* const lname, const char* const expected)
 {
-  SerdWorld*       world  = serd_world_new();
+  SerdWorld*       world  = serd_world_new(NULL);
   SerdNodes*       nodes  = serd_world_nodes(world);
   SerdEnv*         env    = serd_env_new(world, SERD_EMPTY_STRING());
-  SerdBuffer       buffer = {NULL, 0};
+  SerdBuffer       buffer = {NULL, NULL, 0};
   SerdOutputStream output = serd_open_output_buffer(&buffer);
 
   SerdWriter* writer = serd_writer_new(world, SERD_TURTLE, 0u, env, &output, 1);
@@ -389,7 +480,7 @@ check_pname_escape(const char* const lname, const char* const expected)
   char* out = (char*)buffer.buf;
 
   assert(!strcmp(out, expected));
-  serd_free(out);
+  serd_free(NULL, buffer.buf);
 
   free(uri);
   serd_world_free(world);
@@ -430,6 +521,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_stack_overflow();