Hi squid community,
we experience segfaults with squid 6.1 (and also older versions) during
"squid -k reconfigure" on several linux systems, caused by a stack overflow.
The circumstances are rather special:
- we have a huge dst ip blacklist (> 300.000 enties)
- this original list is sorted (by raw ip value)
- the proxy is a hot standby system so there are no client requests
between start of squid and reconfigure
We could trace the cause of the segfault to the destroy-method of
SplayNode (in include/splay.h):
- destroy of the top node is run on every reconfigure
- destroy is recursive, so the function calls stack on the stack :-)
up to the depth of the splay tree
- the insertion of an ordered ip list into the splay tree creates a
degenerate splay tree (each node has only a left child) with a depth
of the number of ip entries in the list
- due to the inactivity of the proxy there is no rebalancing of the
tree through find calls
On amd64 every stack frame needs 32 byte. So the regular linux stack of
8 MB can hold about ~262.000 stack frames. On other architectures
the limit is reached even faster (s390x: 160 bytes per stack frame ->
52.000 frames).
We tried to increase the stack size via ulimits and systemd, but though
the squid master process got the increased limits, the kid-processes are
always spawned with a soft limit of 8 MB and crash on reaching it.
Only forcing a new soft limit via prlimit on an already running kid
could avoid the crash.
I've attached a patch that modifies the destroy method of SplayNode to
avoid recursive calls of destroy in single child nodes by moving the
subtrees of the child to the parent node before destroying the child non
recursively.
With this patch we could no longer reproduce the segfaults, even with a
list of 10.000.000 ordered ips.
Any ideas, comments, better solutions?
Thanks in advance for any advice.
best regards
Martin
--- a/include/splay.h
+++ b/include/splay.h
@@ -133,11 +133,37 @@ template<class V>
void
SplayNode<V>::destroy(SPLAYFREE * free_func)
{
- if (left)
- left->destroy(free_func);
+ /* try to minimize recursion depth on degenerate trees,
+ * by taking over the subtrees of the only child in single
+ * child nodes. */
+ SplayNode<V> *child = nullptr;
+ for (;;) {
+ child = nullptr;
- if (right)
- right->destroy(free_func);
+ if (right == nullptr) {
+ if (left == nullptr) /* leaf node */
+ break;
+ /* only left child exists */
+ child = left;
+ } else if (left == nullptr) {
+ /* only right child exists */
+ child = right;
+ } else {
+ /* both children contain data => remove right one recursively */
+ right->destroy(free_func);
+ right = nullptr;
+ child = left;
+ }
+
+ /* first take over subtrees of only child ... */
+ left = child->left;
+ right = child->right;
+ child->left = nullptr;
+ child->right = nullptr;
+ /* then destroy it */
+ child->destroy(free_func);
+ }
+ /* no more children -> done */
free_func(data);
_______________________________________________
squid-users mailing list
squid-users@xxxxxxxxxxxxxxxxxxxxx
http://lists.squid-cache.org/listinfo/squid-users
