aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid Robillard <d@drobilla.net>2021-01-13 23:47:44 +0100
committerDavid Robillard <d@drobilla.net>2023-12-02 16:27:02 -0500
commit3fc450d7f586388135028ac83870d288834c34a1 (patch)
treea80cbe021ff2b946b1126a4b79c835d98fecbea3
parentfb95ceca3b744e47e973585aa682515365ac9eb0 (diff)
downloadserd-3fc450d7f586388135028ac83870d288834c34a1.tar.gz
serd-3fc450d7f586388135028ac83870d288834c34a1.tar.bz2
serd-3fc450d7f586388135028ac83870d288834c34a1.zip
Simplify stack management by popping in bulk at higher levels
Since all memory used by the reader is POD in the stack, there is no benefit to forcing code to explicitly pop everything pushed to the stack, since any function can record an offset and pop back down to it regardless of what its callers pushed if it knows that it does not need those items. This is slightly more efficient (due to avoiding many pop calls), but also more resilient since "leaks" at deeper levels of recursion get nuked by some caller regardless of what was pushed. This should help prevent future regressions like f6437f606 (Fix memory consumption when reading documents).
-rw-r--r--src/n3.c111
-rw-r--r--src/reader.c34
-rw-r--r--src/reader.h15
-rw-r--r--src/stack.h34
4 files changed, 55 insertions, 139 deletions
diff --git a/src/n3.c b/src/n3.c
index e35b8940..36f90c4f 100644
--- a/src/n3.c
+++ b/src/n3.c
@@ -740,7 +740,6 @@ read_IRIREF(SerdReader* const reader, SerdNode** const dest)
*dest = push_node(reader, SERD_URI, "", 0);
if (!fancy_syntax(reader) && read_IRIREF_scheme(reader, *dest)) {
- *dest = pop_node(reader, *dest);
return r_err(reader, SERD_BAD_SYNTAX, "expected IRI scheme\n");
}
@@ -751,24 +750,18 @@ read_IRIREF(SerdReader* const reader, SerdNode** const dest)
switch (c) {
case '"':
case '<':
- *dest = pop_node(reader, *dest);
return r_err(reader, SERD_BAD_SYNTAX, "invalid IRI character '%c'\n", c);
-
case '>':
return SERD_SUCCESS;
-
case '\\':
if (read_UCHAR(reader, *dest, &code)) {
- *dest = pop_node(reader, *dest);
return r_err(reader, SERD_BAD_SYNTAX, "invalid IRI escape\n");
}
-
switch (code) {
case 0:
case ' ':
case '<':
case '>':
- *dest = pop_node(reader, *dest);
return r_err(reader,
SERD_BAD_SYNTAX,
"invalid escaped IRI character U+%04X\n",
@@ -777,15 +770,12 @@ read_IRIREF(SerdReader* const reader, SerdNode** const dest)
break;
}
break;
-
case '^':
case '`':
case '{':
case '|':
case '}':
- *dest = pop_node(reader, *dest);
return r_err(reader, SERD_BAD_SYNTAX, "invalid IRI character '%c'\n", c);
-
default:
if (c <= 0x20) {
st = r_err(reader,
@@ -802,14 +792,12 @@ read_IRIREF(SerdReader* const reader, SerdNode** const dest)
push_byte(reader, *dest, c);
} else if (read_utf8_character(reader, *dest, (uint8_t)c)) {
if (reader->strict) {
- *dest = pop_node(reader, *dest);
return SERD_BAD_SYNTAX;
}
}
}
}
- *dest = pop_node(reader, *dest);
return st;
}
@@ -952,7 +940,7 @@ read_literal(SerdReader* const reader,
SerdStatus st = read_String(reader, *dest, flags);
if (st) {
- *dest = pop_node(reader, *dest);
+ *dest = NULL;
return st;
}
@@ -961,10 +949,7 @@ read_literal(SerdReader* const reader,
skip_byte(reader, '@');
*flags |= SERD_HAS_LANGUAGE;
if ((st = read_LANGTAG(reader, lang))) {
- *datatype = pop_node(reader, *datatype);
- *lang = pop_node(reader, *lang);
- *dest = pop_node(reader, *dest);
- return r_err(reader, st, "bad language tag\n");
+ return r_err(reader, st, "bad literal\n");
}
break;
case '^':
@@ -975,9 +960,6 @@ read_literal(SerdReader* const reader,
*flags |= SERD_HAS_DATATYPE;
if ((st = read_iri(reader, datatype, ate_dot))) {
- *datatype = pop_node(reader, *datatype);
- *lang = pop_node(reader, *lang);
- *dest = pop_node(reader, *dest);
return r_err(reader, st, "bad datatype\n");
}
break;
@@ -988,6 +970,7 @@ read_literal(SerdReader* const reader,
static SerdStatus
read_verb(SerdReader* const reader, SerdNode** const dest)
{
+ const size_t orig_stack_size = reader->stack.size;
if (peek_byte(reader) == '<') {
return read_IRIREF(reader, dest);
}
@@ -1005,14 +988,14 @@ read_verb(SerdReader* const reader, SerdNode** const dest)
const int next = peek_byte(reader);
if (!st && node->length == 1 && serd_node_string(node)[0] == 'a' &&
next != ':' && !is_PN_CHARS_BASE((uint32_t)next)) {
- pop_node(reader, *dest);
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
*dest = push_node(reader, SERD_URI, NS_RDF "type", 47);
return SERD_SUCCESS;
}
if (st > SERD_FAILURE ||
(st = read_PrefixedName(reader, *dest, false, &ate_dot)) || ate_dot) {
- *dest = pop_node(reader, *dest);
+ *dest = NULL;
st = st > SERD_FAILURE ? st : SERD_BAD_SYNTAX;
return r_err(reader, st, "bad verb\n");
}
@@ -1041,8 +1024,7 @@ read_BLANK_NODE_LABEL(SerdReader* const reader,
if (is_digit(c) || c == '_') {
push_byte(reader, n, eat_byte_safe(reader, c));
} else if ((st = read_PN_CHARS(reader, n))) {
- st = st > SERD_FAILURE ? st : SERD_BAD_SYNTAX;
- *dest = pop_node(reader, n);
+ st = st > SERD_FAILURE ? st : SERD_BAD_SYNTAX;
return r_err(reader, st, "invalid name start\n");
}
@@ -1072,7 +1054,6 @@ read_BLANK_NODE_LABEL(SerdReader* const reader,
buf[reader->bprefix_len] = 'B'; // Prevent clash
reader->seen_genid = true;
} else if (reader->seen_genid && buf[reader->bprefix_len] == 'B') {
- *dest = pop_node(reader, n);
return r_err(reader,
SERD_BAD_LABEL,
"found both 'b' and 'B' blank IDs, prefix required\n");
@@ -1145,9 +1126,7 @@ read_object(SerdReader* const reader,
static const char* const XSD_BOOLEAN = NS_XSD "boolean";
static const size_t XSD_BOOLEAN_LEN = 40;
-#ifndef NDEBUG
const size_t orig_stack_size = reader->stack.size;
-#endif
SerdStatus st = SERD_FAILURE;
@@ -1227,7 +1206,6 @@ read_object(SerdReader* const reader,
} else {
if ((st = read_PrefixedName(reader, o, false, ate_dot))) {
st = st > SERD_FAILURE ? st : SERD_BAD_SYNTAX;
- pop_node(reader, o);
return r_err(reader, st, "expected prefixed name\n");
}
}
@@ -1246,9 +1224,7 @@ read_object(SerdReader* const reader,
return SERD_SUCCESS;
}
- pop_node(reader, lang);
- pop_node(reader, datatype);
- pop_node(reader, o);
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
#ifndef NDEBUG
assert(reader->stack.size == orig_stack_size);
#endif
@@ -1277,11 +1253,13 @@ read_predicateObjectList(SerdReader* const reader,
ReadContext ctx,
bool* const ate_dot)
{
+ const size_t orig_stack_size = reader->stack.size;
+
SerdStatus st = SERD_SUCCESS;
while (!(st = read_verb(reader, &ctx.predicate)) && read_ws_star(reader) &&
!(st = read_objectList(reader, ctx, ate_dot))) {
- ctx.predicate = pop_node(reader, ctx.predicate);
if (*ate_dot) {
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
return SERD_SUCCESS;
}
@@ -1291,10 +1269,12 @@ read_predicateObjectList(SerdReader* const reader,
read_ws_star(reader);
switch (c = peek_byte(reader)) {
case EOF:
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
return r_err(reader, SERD_BAD_SYNTAX, "unexpected end of file\n");
case '.':
case ']':
case '}':
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
return SERD_SUCCESS;
case ';':
skip_byte(reader, c);
@@ -1303,29 +1283,24 @@ read_predicateObjectList(SerdReader* const reader,
} while (c == ';');
if (!ate_semi) {
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
return r_err(reader, SERD_BAD_SYNTAX, "missing ';' or '.'\n");
}
}
- ctx.predicate = pop_node(reader, ctx.predicate);
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
+ ctx.predicate = 0;
return st;
}
static SerdStatus
-end_collection(SerdReader* const reader,
- const ReadContext ctx,
- SerdNode* const n1,
- SerdNode* const n2,
- const SerdStatus st)
+end_collection(SerdReader* const reader, ReadContext ctx, const SerdStatus st)
{
- pop_node(reader, n2);
- pop_node(reader, n1);
*ctx.flags &= ~(unsigned)SERD_LIST_CONT;
if (!st) {
return (eat_byte_check(reader, ')') == ')') ? SERD_SUCCESS
: SERD_BAD_SYNTAX;
}
-
return st;
}
@@ -1351,14 +1326,13 @@ read_collection(SerdReader* const reader,
}
if (end) {
- return end_collection(reader, ctx, 0, 0, st);
+ return end_collection(reader, ctx, st);
}
/* The order of node allocation here is necessarily not in stack order,
so we create two nodes and recycle them throughout. */
SerdNode* n1 =
push_node_padded(reader, genid_size(reader), SERD_BLANK, "", 0);
- SerdNode* n2 = 0;
SerdNode* node = n1;
SerdNode* rest = 0;
@@ -1372,14 +1346,14 @@ read_collection(SerdReader* const reader,
ctx.predicate = reader->rdf_first;
bool ate_dot = false;
if ((st = read_object(reader, &ctx, true, &ate_dot)) || ate_dot) {
- return end_collection(reader, ctx, n1, n2, st);
+ return end_collection(reader, ctx, st);
}
if (!(end = peek_delim(reader, ')'))) {
/* Give rest a new ID. Done as late as possible to ensure it is
used and > IDs generated by read_object above. */
if (!rest) {
- rest = n2 = blank_id(reader); // First pass, push
+ rest = blank_id(reader); // First pass, push
} else {
set_blank_id(reader, rest, genid_size(reader));
}
@@ -1395,7 +1369,7 @@ read_collection(SerdReader* const reader,
node = ctx.subject; // invariant
}
- return end_collection(reader, ctx, n1, n2, st);
+ return end_collection(reader, ctx, st);
}
static SerdStatus
@@ -1421,7 +1395,6 @@ read_subject(SerdReader* const reader,
}
if (ate_dot) {
- pop_node(reader, *dest);
return r_err(reader, SERD_BAD_SYNTAX, "subject ends with '.'\n");
}
@@ -1485,7 +1458,6 @@ read_base(SerdReader* const reader, const bool sparql, const bool token)
SerdNode* uri = NULL;
TRY(st, read_IRIREF(reader, &uri));
TRY(st, serd_sink_write_base(reader->sink, uri));
- pop_node(reader, uri);
read_ws_star(reader);
if (!sparql) {
@@ -1516,7 +1488,6 @@ read_prefixID(SerdReader* const reader, const bool sparql, const bool token)
TRY_FAILING(st, read_PN_PREFIX(reader, name));
if (eat_byte_check(reader, ':') != ':') {
- pop_node(reader, name);
return SERD_BAD_SYNTAX;
}
@@ -1526,8 +1497,6 @@ read_prefixID(SerdReader* const reader, const bool sparql, const bool token)
st = serd_sink_write_prefix(reader->sink, name, uri);
- pop_node(reader, uri);
- pop_node(reader, name);
if (!sparql) {
read_ws_star(reader);
st = eat_byte_check(reader, '.') ? SERD_SUCCESS : SERD_BAD_SYNTAX;
@@ -1571,8 +1540,10 @@ read_wrappedGraph(SerdReader* const reader, ReadContext* const ctx)
read_ws_star(reader);
while (peek_byte(reader) != '}') {
- bool ate_dot = false;
- int s_type = 0;
+ const size_t orig_stack_size = reader->stack.size;
+ bool ate_dot = false;
+ int s_type = 0;
+
ctx->subject = 0;
SerdStatus st = read_subject(reader, *ctx, &ctx->subject, &s_type);
if (st) {
@@ -1583,7 +1554,7 @@ read_wrappedGraph(SerdReader* const reader, ReadContext* const ctx)
return r_err(reader, st, "bad predicate object list\n");
}
- ctx->subject = pop_node(reader, ctx->subject);
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
read_ws_star(reader);
if (peek_byte(reader) == '.') {
skip_byte(reader, '.');
@@ -1611,10 +1582,6 @@ tokcmp(SerdNode* const node, const char* const tok, const size_t n)
SerdStatus
read_n3_statement(SerdReader* const reader)
{
-#ifndef NDEBUG
- const size_t orig_stack_size = reader->stack.size;
-#endif
-
SerdStatementFlags flags = 0;
ReadContext ctx = {0, 0, 0, 0, 0, 0, &flags};
bool ate_dot = false;
@@ -1651,12 +1618,11 @@ read_n3_statement(SerdReader* const reader)
} else if (!tokcmp(ctx.subject, "prefix", 6)) {
st = read_prefixID(reader, true, false);
} else if (!tokcmp(ctx.subject, "graph", 5)) {
- ctx.subject = pop_node(reader, ctx.subject);
+ ctx.subject = NULL;
read_ws_star(reader);
TRY(st, read_labelOrSubject(reader, &ctx.graph));
read_ws_star(reader);
TRY(st, read_wrappedGraph(reader, &ctx));
- pop_node(reader, ctx.graph);
ctx.graph = 0;
read_ws_star(reader);
} else if (!tokcmp(ctx.subject, "true", 4) ||
@@ -1667,9 +1633,8 @@ read_n3_statement(SerdReader* const reader)
return r_err(reader, SERD_BAD_SYNTAX, "invalid graph name\n");
}
ctx.graph = ctx.subject;
- ctx.subject = 0;
+ ctx.subject = NULL;
TRY(st, read_wrappedGraph(reader, &ctx));
- pop_node(reader, ctx.graph);
read_ws_star(reader);
} else if ((st = read_triples(reader, ctx, &ate_dot))) {
if (st == SERD_FAILURE && s_type == '[') {
@@ -1686,15 +1651,9 @@ read_n3_statement(SerdReader* const reader)
st =
(eat_byte_check(reader, '.') == '.') ? SERD_SUCCESS : SERD_BAD_SYNTAX;
}
-
- ctx.subject = pop_node(reader, ctx.subject);
break;
}
-#ifndef NDEBUG
- assert(reader->stack.size == orig_stack_size);
-#endif
-
return st;
}
@@ -1715,13 +1674,18 @@ SerdStatus
read_turtleTrigDoc(SerdReader* const reader)
{
while (!reader->source.eof) {
- const SerdStatus st = read_n3_statement(reader);
+ const size_t orig_stack_size = reader->stack.size;
+ const SerdStatus st = read_n3_statement(reader);
+
if (st > SERD_FAILURE) {
if (reader->strict) {
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
return st;
}
serd_reader_skip_until_byte(reader, '\n');
}
+
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
}
return SERD_SUCCESS;
@@ -1775,11 +1739,6 @@ read_nquads_statement(SerdReader* const reader)
TRY(st, emit_statement(reader, ctx, ctx.object));
- pop_node(reader, ctx.graph);
- pop_node(reader, ctx.lang);
- pop_node(reader, ctx.datatype);
- pop_node(reader, ctx.object);
-
return SERD_SUCCESS;
}
@@ -1789,7 +1748,11 @@ read_nquadsDoc(SerdReader* const reader)
SerdStatus st = SERD_SUCCESS;
while (!reader->source.eof && !st) {
+ const size_t orig_stack_size = reader->stack.size;
+
st = read_nquads_statement(reader);
+
+ serd_stack_pop_to(&reader->stack, orig_stack_size);
}
return st;
diff --git a/src/reader.c b/src/reader.c
index 3b4dfd2b..ae50adab 100644
--- a/src/reader.c
+++ b/src/reader.c
@@ -69,6 +69,13 @@ push_node_padded(SerdReader* const reader,
const char* const str,
const size_t length)
{
+ // Push a null byte to ensure the previous node was null terminated
+ char* terminator = (char*)serd_stack_push(&reader->stack, 1);
+ if (!terminator) {
+ return NULL;
+ }
+ *terminator = 0;
+
void* mem = serd_stack_push_aligned(
&reader->stack, sizeof(SerdNode) + maxlen + 1, sizeof(SerdNode));
@@ -85,12 +92,6 @@ push_node_padded(SerdReader* const reader,
char* buf = (char*)(node + 1);
memcpy(buf, str, length + 1);
-#ifdef SERD_STACK_CHECK
- reader->allocs = (SerdNode**)realloc(
- reader->allocs, sizeof(reader->allocs) * (++reader->n_allocs));
- reader->allocs[reader->n_allocs - 1] =
- (SerdNode*)((char*)mem - reader->stack.buf);
-#endif
return node;
}
@@ -103,21 +104,6 @@ push_node(SerdReader* const reader,
return push_node_padded(reader, length, type, str, length);
}
-SerdNode*
-pop_node(SerdReader* const reader, const SerdNode* const node)
-{
- if (node && node != reader->rdf_first && node != reader->rdf_rest &&
- node != reader->rdf_nil) {
-#ifdef SERD_STACK_CHECK
- SERD_STACK_ASSERT_TOP(reader, node);
- --reader->n_allocs;
-#endif
- char* const top = reader->stack.buf + reader->stack.size;
- serd_stack_pop_aligned(&reader->stack, (size_t)(top - (char*)node));
- }
- return NULL;
-}
-
SerdStatus
emit_statement(SerdReader* const reader,
const ReadContext ctx,
@@ -204,15 +190,9 @@ serd_reader_free(SerdReader* const reader)
return;
}
- pop_node(reader, reader->rdf_nil);
- pop_node(reader, reader->rdf_rest);
- pop_node(reader, reader->rdf_first);
serd_reader_finish(reader);
serd_node_free(reader->default_graph);
-#ifdef SERD_STACK_CHECK
- free(reader->allocs);
-#endif
free(reader->stack.buf);
free(reader->bprefix);
free(reader);
diff --git a/src/reader.h b/src/reader.h
index a39fc278..d126aeaa 100644
--- a/src/reader.h
+++ b/src/reader.h
@@ -22,13 +22,6 @@
#include <stdint.h>
#include <stdio.h>
-#ifdef SERD_STACK_CHECK
-# define SERD_STACK_ASSERT_TOP(reader, ref) \
- assert(ref == reader->allocs[reader->n_allocs - 1]);
-#else
-# define SERD_STACK_ASSERT_TOP(reader, ref)
-#endif
-
typedef struct {
SerdNode* graph;
SerdNode* subject;
@@ -56,10 +49,6 @@ struct SerdReaderImpl {
size_t bprefix_len;
bool strict; ///< True iff strict parsing
bool seen_genid;
-#ifdef SERD_STACK_CHECK
- SerdNode** allocs; ///< Stack of push offsets
- size_t n_allocs; ///< Number of stack pushes
-#endif
};
SERD_LOG_FUNC(3, 4)
@@ -88,9 +77,6 @@ blank_id(SerdReader* reader);
void
set_blank_id(SerdReader* reader, SerdNode* node, size_t buf_size);
-SerdNode*
-pop_node(SerdReader* reader, const SerdNode* node);
-
SerdStatus
emit_statement(SerdReader* reader, ReadContext ctx, SerdNode* o);
@@ -161,7 +147,6 @@ static inline SerdStatus
push_byte(SerdReader* reader, SerdNode* node, const int c)
{
assert(c != EOF);
- SERD_STACK_ASSERT_TOP(reader, ref);
char* const s = (char*)serd_stack_push(&reader->stack, 1);
if (!s) {
diff --git a/src/stack.h b/src/stack.h
index e6e46372..4592705e 100644
--- a/src/stack.h
+++ b/src/stack.h
@@ -7,8 +7,8 @@
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
-#include <stdint.h>
#include <stdlib.h>
+#include <string.h>
/** An offset to start the stack at. Note 0 is reserved for NULL. */
#define SERD_STACK_BOTTOM sizeof(void*)
@@ -68,40 +68,28 @@ serd_stack_pop(SerdStack* stack, size_t n_bytes)
stack->size -= n_bytes;
}
+static inline void
+serd_stack_pop_to(SerdStack* stack, size_t n_bytes)
+{
+ assert(stack->size >= n_bytes);
+ stack->size = n_bytes;
+}
+
static inline void*
serd_stack_push_aligned(SerdStack* stack, size_t n_bytes, size_t align)
{
- // Push one byte to ensure space for a pad count
- if (!serd_stack_push(stack, 1)) {
- return NULL;
- }
-
// Push padding if necessary
const size_t pad = align - stack->size % align;
if (pad > 0) {
- if (!serd_stack_push(stack, pad)) {
+ void* padding = serd_stack_push(stack, pad);
+ if (!padding) {
return NULL;
}
+ memset(padding, 0, pad);
}
- // Set top of stack to pad count so we can properly pop later
- stack->buf[stack->size - 1] = (char)pad;
-
// Push requested space at aligned location
return serd_stack_push(stack, n_bytes);
}
-static inline void
-serd_stack_pop_aligned(SerdStack* stack, size_t n_bytes)
-{
- // Pop requested space down to aligned location
- serd_stack_pop(stack, n_bytes);
-
- // Get amount of padding from top of stack
- const uint8_t pad = (uint8_t)stack->buf[stack->size - 1];
-
- // Pop padding and pad count
- serd_stack_pop(stack, pad + 1U);
-}
-
#endif // SERD_SRC_STACK_H