The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
common scanEntity: use a more appropriate type for 'len'
This addresses a problem where the subtraction of two pointers, `endp - t`, can
in theory exceed the size of an `int`. In practice this cannot occur, but using
a more correct type squashes a -Wconversion and -Wsign-conversion warning in
this code.
common undoClusterEdges: use cgraph wrapper for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
common new_queue: use cgraph wrappers for allocation
The lib/cgraph/alloc.h wrappers are similar to the older lib/common/memory.h
wrappers except (1) they are header-only and (2) they live in a directory
(cgraph) that is at the root of the dependency tree. The long term plan is to
replace all use of lib/common/memory.h with lib/cgraph/alloc.h.
A mistake in 632fe0bd1cfc6a4f636db4f85206aff6720bdc6b made this test read from
/dev/null instead of the input file it was supposed to read. Note that this
required some tweak to the skip condition. The Windows platforms on which this
fails seems all over the place and expressing the exact pattern seemed too
complex. For the curious, what we currently see in CI is:
I would not be surprised if these results are not stable. It is likely this
failure presents across all platforms, but is dependent on things like Address
Space Layout Randomization to exhibit.
This change switches both `agxbinit` and zero-initialization (`agxbuf xb = {0}`)
to result in a buffer with inline storage. This means string data is written
inline until it becomes too large to store within the `agxbuf` struct itself,
when it is then relocated to the heap.
This is an optimization. Short dynamic strings can now be written completely
without heap allocation. For example, stringifying a number
(`agxbprint(&xb, "%d", i)`) will fit fully within the inline buffer.
Some performance evaluation comparing the merge-base of this series
(740c4bf1edba931be0698de7bfde629eba2f40c0) to the current commit follows. These
numbers were derived using `/usr/bin/time` and Valgrind on `-O3 -flto -DNDEBUG`
builds of Graphviz. Instruction counts are provided for examples that are not
too long running.
¹ `dot -Tsvg -o /dev/null tests/regression_tests/large/long_chain`.
² “long” in the table is a graph generated by the following script:
print("digraph {")
for i in range(80000):
print(f" N{i} -> N{i + 1}")
print("}")
This represents something like a best case scenario to observe the effect of
this optimization. Lots of small unique strings. Run as
`dot -Tsvg -o /dev/null long.dot`.
³ The test case from https://gitlab.com/graphviz/graphviz/-/issues/456 run as
`dot -Tsvg -o /dev/null 456.dot`. Note that this actually errors out
eventually.
⁴ The test case from https://gitlab.com/graphviz/graphviz/-/issues/456 but with
`concentrate=true` removed. Run as `dot -Tsvg -o /dev/null 456.dot`.
⁵ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1652 run as
`neato -Tsvg -o /dev/null 1652.dot`.
⁶ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1652 run as
`dot -Tsvg -Gnslimit=2.0 -o /dev/null 1652.dot`. Note that this eventually
crashes.
⁷ swedish-flat.dot Magnus attached to
https://gitlab.com/graphviz/graphviz/-/issues/1718 run as
`circo -Tsvg -o /dev/null swedish-flag.dot`.
⁸ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1864 run as
`neato -Tsvg -o /dev/null 1864.dot`.
⁹ The test case from https://gitlab.com/graphviz/graphviz/-/issues/1864 run as
`twopi -Tsvg -o /dev/null 1864.dot`.
¹⁰ The test case from https://gitlab.com/graphviz/graphviz/-/issues/2064 run as
`dot -Gnslimit=2 -Gnslimit1=2 -Gmaxiter=5000 -Tsvg -o /dev/null 2064.dot`.
¹¹The tests/2095.dot test case from prior to minimization
(3819821ea70fae730dd224936628ed3929b03531). Run as
`dot -Tsvg -o /dev/null 2095.dot`.
As indicated by the changes to the layout diagram in this diff, previously we
were essentially wasting a number of bytes (3 on x86, 7 on x86-64) on structure
padding. Through some rearrangement and packing, we can make these bytes usable
for the inline storage area.
The definition of the struct is not quite what you might expect to see. The
`located` field is in the first member of the union but is actually used
regardless of what mode an `agxbuf` is in (heap, stack, inline). This is
necessary to get the desired packing. It does not overlap with other struct
fields, though reading and writing a struct through different union members is
well defined in C99.
This optimization might seem a little niche. But `agxbuf` objects are
extensively used. Once inline `agxbuf` objects become possible (an upcoming
commit), this saves us heap allocations in numerous scenarios.
cgraph agxbuf: support storing short strings inline
This commit implements Small String Optimization (SSO) for `axgbuf`. Strings
up to a certain size (24 bytes unterminated on x86-64) can be stored inline
within an `agxbuf` structure itself with no external backing memory.
There is currently no way to create a buffer in inline mode. Neither
`agxbuf_init` nor zero-initialization gives a path to this. The ability to
create inline strings will be added in an upcoming commit.
When a string is stored inline, its size is maintained in the `located` field
instead of in the `size` field.
CI: suppress -Wmissing-braces in CentOS 7 CMake build
The compiler on CentOS 7 is an older version of GCC, 4.8.5, which spuriously
issues warnings for code like `foo_t x = {0}` where `foo_t` is a struct
containing an aggregate (array, struct, union). This form of initialization is
meant to be valid for all structs in C99. We need to suppress this to avoid CI
warnings that fail the build in an upcoming commit.
cgraph agxbuf: use an enumerated type for buffer location
This does not change the semantics; 0 still means heap-allocated and 1 means
stack-allocated. However this is preparation for introducing a third location a
buffer can be hosted in.
This eases some upcoming changes to the internal structure of the `agxbuf` type.
This alters the semantics of `deparse` (the buffer’s size ends up 0 on
completion of this function), but this is acceptable as all callers go on to
immediately free the buffer.
cgraph: avoid accessing agxbuf internals in the scanner
This eases some upcoming changes to the internal structure of the `agxbuf` type.
The trailing calls to `agxbclear` are removed because they are no longer
necessary; the `agxbuse` call does the same thing.
1349b895eca0bb04855ba46162d0ec7ba3c65010 refactored `printTok` to introduce a
call to `agxbput` that passes in the return value from a previous `agxbuse` on
the same buffer. This pointer still points into the destination buffer and
`agxbput` bottoms out on a call to `memcpy`. So this ends up calling `memcpy`
with overlapping source and destination, something that is undefined behavior in
C.
This change introduces a local alternative for this situation, because this is
the only known place where we need to do such a thing.
A number of other functions in agxbuf.h open code the logic of `agxblen`. Moving
this function higher in the header will enable us to de-duplicate this code. The
goal here is to fully abstract this, as an upcoming commit will make the way the
length of an `agxbuf` is calculated conditional.
While working on Small String Optimization, it became clear that a variant of
this test case which just passes an invalid string through the Graphviz binary
provokes some non-trivial behavior which is worth testing.
cgraph: remove unimplemented 'attrmacro' in the grammar
Parsing this entity would result in calling `appendattr` in a way that failed an
assertion. Thankfully it is unimplemented, so this is unreachable. However, it
is also not practical anymore to implement this. The lexer (lib/cgraph/scan.l)
treats `@` as an end-of-file marker. So future modifications to the DOT language
to interpret `@` as an attribute macro would break a lot of existing things.
cgraph: pass destructor as a macro parameter instead of struct member
This smoothes down a number of rough edges in the generic list implementation:
1. No need to noisily cast e.g. `free` as a destructor at the initialization
site.
2. The generic list struct is reduced by the size of a function pointer. This
is not significant when a list is used entirely locally as the compiler can
destructure this type as an optimization. But when passing objects of this
type between functions, this can help.
3. Some functions like free of the generic list zeroed the structure, losing
the destructor. This could be improved by retaining it, but it seemed
simpler to remove the opportunity for this confusion altogether.
An alternative to creating the new `DEFINE_LIST_WITH_DTOR` macro would be to
implement `DEFINE_LIST` as a variadic macro, taking an optional third parameter.
However the gymnastics required to achieve this in C99 (search the internet for
macro argument counting) make it not worth it.
common parse_style: remove static backing buffer for 'ps_xb'
There seems little value retaining this when it adds complication and was a
contributing factor in the bug just fixed. This potentially slightly degrades
performance (initial style use results in a heap allocation), but is unlikely to
be measurable and should be regained back if we implement Small String
Optimization on `agxbuf`.
fix out-of-bounds memory reads with large 'style' strings
Parsing a large style would acquire pointers into the `agxbuf` it wrote into,
but then go on to append more data to the buffer, potentially triggering a
reallocation thus leaving those prior pointers dangling. Later attempts to
access the style would read from these (now invalid) pointers. This bug has
existed since the very first commit of Graphviz.
Note that this change does nothing to alter the NUL-separated-string design of
the return value of `parse_style`. This still remains because some callers rely
on it, despite it being known as problematic.
common printTok: remove use of 'agxbstart' to access agxbuf data
Reaching into something that is notionally the internals of the `agxbuf` type
was causing some complications in upcoming changes. Specifically, the lifetime
of the pointer returned from `agxbstart` makes it error prone. Any operation
that appends more data to the `agxbuf` must conservatively be assumed to
invalidate a pointer previously returned from `agxbstart`.
Although this instance was not retaining the returned pointer, the `agxbstart`
interface seems dangerous to provide given that it is difficult to use safely.
By removing its sole use here, we clear the way for its removal in future.
This new phrasing is potentially less efficient, as data is now extracted from
the buffer and then written back into the same buffer. However (1) a good
contemporary compiler will inline all calls and realize the accumulated
operation on the buffer is a no-op and (2) this is debug code, so performance is
not critical.
gvgen: replace 'gv_stack_t' with generic list for int stack
The generic list implementation is an improvement over `gv_stack_t` in that it
is both more flexible and type safe. Migrating to it has two primary
improvements:
1. Maintaining type safety. There is now no need to cast when pushing and
popping the stack. This removes two compiler warnings and leads to shorter,
more readable code.
2. Memory reduction. On 64-bit platforms with a 32-bit int (e.g. x86-64),
`gv_stack_t` uses 8 bytes per int element for storage. In contrast, the
generic list uses 4 bytes per int.
sparse: replace 'IntStack' with generic list implementation
Apart from reducing the amount of code to maintain going forwards, this removes
several warts:
1. `IntStack_push` returned a value indicating whether it succeeded or failed.
The caller was ignoring this. We now exit on push failure.
2. `IntStack_pop` used an awkward flag-based protocol to detect an empty
stack. We now use a cleaner “is empty” guard on the pop call.
3. Iterating over all stack elements sometimes used < length and sometimes
≤ last. There were reasons for this (`SIZE_MAX` was used as a sentinel
last value, and length was calculated based on last). But it led to code
that was harder than necessary to understand at the call site.
projects / graphviz / log