subject:"\[squid\-dev\] \[MERGE\] Fix splay"

Re: [squid-dev] [MERGE] Fix splay

2015-01-06 Thread Tsantilas Christos


Hi all,
I am getting assertions while squid.conf parsed using the latest squid 
sources. Looks that the reason is the splay trees. Is it possible that 
this patch causes these bugs?


I am seeing this problem when an acl localhost src 127.0.0.1/32 line 
is parsed (duplicate value?) or when proxy_auth or snmp_community acls 
parsed.


Backtace for proxy_auth acl line (acl UserChtsanti proxy_auth 
chtsanti) is the following:


#0  findchar* (this=0x0, compare=0xb89f80 Debug::Levels,
value=@0x7fff4bcf01e8: 0x1396b50 chtsanti) at 
../../include/splay.h:287

#1  Splaychar*::insert (this=0x0,
value=@0x7fff4bcf01e8: 0x1396b50 chtsanti,
compare=0x6a6620 splaystrcmp(char* const, char* const))
at ../../include/splay.h:302
#2  0x006a7130 in ACLUserData::parse (this=0x1395f50)
at UserData.cc:120
#3  0x006e5d8e in ACL::ParseAclLine (parser=...,
head=0xcb2318 Config+1336) at Acl.cc:263
#4  0x0052ad18 in parse_acl (ae=optimized out) at cache_cf.cc:1292
#5  parse_line (buff=optimized out) at cf_parser.cci:921
#6  0x0052c2b2 in parseOneConfigFile (
file_name=file_name@entry=0x1386d30 squid-http-bypass.conf,
depth=depth@entry=0) at cache_cf.cc:543
#7  0x0052cde9 in parseConfigFile (
file_name=0x1386d30 squid-http-bypass.conf) at cache_cf.cc:584
#8  0x005ffe51 in SquidMain (argc=optimized out, 
argv=0x7fff4bcf08a8)

at main.cc:1397
#9  0x0050815b in SquidMainSafe (argv=optimized out,
argc=optimized out) at main.cc:1251
#10 main (argc=optimized out, argv=optimized out) at main.cc:1244
(gdb) up
#1  Splaychar*::insert (this=0x0,
value=@0x7fff4bcf01e8: 0x1396b50 chtsanti,
compare=0x6a6620 splaystrcmp(char* const, char* const))
at ../../include/splay.h:302
302 assert (!find (value, compare));



On 01/06/2015 05:52 AM, Amos Jeffries wrote:

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On 3/01/2015 1:54 a.m., Kinkie wrote:

I believe this is missing several delete Foo; in the ACL
destructors. You used new() to allocate the Splay objects,
there should be matching delete() at the same owner/abstraction
level. For example:  ACLIP::~ACLIP() { if (data) {
data-destroy(IPSplay::DefaultFree); data-destroy(); delete
data; } }  ... although, it would be even better if the data
members could be made non-pointers now they are Splay objects.
Is that easy enough to do in this patch ?


Well, splay doesn't have a destructor :\ I'll see if I can do
something about it.


Other than the new() / delete() issue. +1.


Ok, thanks. I'll also see about the empty lines.



For the record this was merged as trunk rev.13810.

Amos
-BEGIN PGP SIGNATURE-
Version: GnuPG v2.0.22 (MingW32)

iQEcBAEBAgAGBQJUq1wFAAoJELJo5wb/XPRjjcIIAI1DKgOnGgX+l5HQXsc6YK2J
ALTV1FryIfE0v179uSy2RshWuq3VdgDbVBHQmHjLhcEtK2wJVNHBWzML7Bqfpdn8
O5ayKRqsjg5nhSsgr0NbaGhivK/JCM5vO3Q4vejFQp2Oy3geZOBvZfntFoUBp1xu
o2P5ZzgFU1sQ9LoM5WoCjfWwfb7BOrKbwkEX/BzK0v9iOx9b3U6dpOtCKT11EDTg
MW9x0UVjAC/TVRY9bXiBAEUHG4TPPIa5Syrx9bIqobA8u2UTLd36TQqNdfJDz3jP
sVGN6B/p6W4gbEsTJnqfP7YEXmhb+gMvCYNdNvlhS7152APdi8+TNNJkSaqWGQQ=
=buZA
-END PGP SIGNATURE-
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev



___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [MERGE] Fix splay

2015-01-06 Thread Kinkie

Fix committed as r13825.
I am not convinced this is all however. For some reason duplicate
values in ACLs are not handled correctly in calling code, and this
triggers an assert in Splay-insert(). I suspect that this was not
noticed before as this check is not performed when clients call
SplayNode-insert directly.
I've added an explicit check in ACLIP, but I am convinced that there are more.

IMVHO a possible solution is to change in Splay::insert()
- assert (find (value, compare) == NULL);
+ if (find(value, compare) != NULL) return;

aka ignoring duplicates.

What do you guys think?
Please keep in mind I am conducting work to replace Splay with
std::map or std::unordered_map where it makes sense (which is almost
everywhere, IMO).



On Tue, Jan 6, 2015 at 9:21 PM, Kinkie gkin...@gmail.com wrote:
 Hi,
   I'm working on this right now. I missed constructing several Splays,
 this is artifact of the C-ish construction pattern for several
 involved classes.
 Sorry about the breakage.

 On Tue, Jan 6, 2015 at 9:12 PM, Tsantilas Christos
 chtsa...@users.sourceforge.net wrote:
 Hi all,
 I am getting assertions while squid.conf parsed using the latest squid
 sources. Looks that the reason is the splay trees. Is it possible that this
 patch causes these bugs?

 I am seeing this problem when an acl localhost src 127.0.0.1/32 line is
 parsed (duplicate value?) or when proxy_auth or snmp_community acls
 parsed.

 Backtace for proxy_auth acl line (acl UserChtsanti proxy_auth chtsanti) is
 the following:

 #0  findchar* (this=0x0, compare=0xb89f80 Debug::Levels,
 value=@0x7fff4bcf01e8: 0x1396b50 chtsanti) at
 ../../include/splay.h:287
 #1  Splaychar*::insert (this=0x0,
 value=@0x7fff4bcf01e8: 0x1396b50 chtsanti,
 compare=0x6a6620 splaystrcmp(char* const, char* const))
 at ../../include/splay.h:302
 #2  0x006a7130 in ACLUserData::parse (this=0x1395f50)
 at UserData.cc:120
 #3  0x006e5d8e in ACL::ParseAclLine (parser=...,
 head=0xcb2318 Config+1336) at Acl.cc:263
 #4  0x0052ad18 in parse_acl (ae=optimized out) at cache_cf.cc:1292
 #5  parse_line (buff=optimized out) at cf_parser.cci:921
 #6  0x0052c2b2 in parseOneConfigFile (
 file_name=file_name@entry=0x1386d30 squid-http-bypass.conf,
 depth=depth@entry=0) at cache_cf.cc:543
 #7  0x0052cde9 in parseConfigFile (
 file_name=0x1386d30 squid-http-bypass.conf) at cache_cf.cc:584
 #8  0x005ffe51 in SquidMain (argc=optimized out,
 argv=0x7fff4bcf08a8)
 at main.cc:1397
 #9  0x0050815b in SquidMainSafe (argv=optimized out,
 argc=optimized out) at main.cc:1251
 #10 main (argc=optimized out, argv=optimized out) at main.cc:1244
 (gdb) up
 #1  Splaychar*::insert (this=0x0,
 value=@0x7fff4bcf01e8: 0x1396b50 chtsanti,
 compare=0x6a6620 splaystrcmp(char* const, char* const))
 at ../../include/splay.h:302
 302 assert (!find (value, compare));




 On 01/06/2015 05:52 AM, Amos Jeffries wrote:

 -BEGIN PGP SIGNED MESSAGE-
 Hash: SHA1

 On 3/01/2015 1:54 a.m., Kinkie wrote:

 I believe this is missing several delete Foo; in the ACL
 destructors. You used new() to allocate the Splay objects,
 there should be matching delete() at the same owner/abstraction
 level. For example:  ACLIP::~ACLIP() { if (data) {
 data-destroy(IPSplay::DefaultFree); data-destroy(); delete
 data; } }  ... although, it would be even better if the data
 members could be made non-pointers now they are Splay objects.
 Is that easy enough to do in this patch ?


 Well, splay doesn't have a destructor :\ I'll see if I can do
 something about it.

 Other than the new() / delete() issue. +1.


 Ok, thanks. I'll also see about the empty lines.


 For the record this was merged as trunk rev.13810.

 Amos
 -BEGIN PGP SIGNATURE-
 Version: GnuPG v2.0.22 (MingW32)

 iQEcBAEBAgAGBQJUq1wFAAoJELJo5wb/XPRjjcIIAI1DKgOnGgX+l5HQXsc6YK2J
 ALTV1FryIfE0v179uSy2RshWuq3VdgDbVBHQmHjLhcEtK2wJVNHBWzML7Bqfpdn8
 O5ayKRqsjg5nhSsgr0NbaGhivK/JCM5vO3Q4vejFQp2Oy3geZOBvZfntFoUBp1xu
 o2P5ZzgFU1sQ9LoM5WoCjfWwfb7BOrKbwkEX/BzK0v9iOx9b3U6dpOtCKT11EDTg
 MW9x0UVjAC/TVRY9bXiBAEUHG4TPPIa5Syrx9bIqobA8u2UTLd36TQqNdfJDz3jP
 sVGN6B/p6W4gbEsTJnqfP7YEXmhb+gMvCYNdNvlhS7152APdi8+TNNJkSaqWGQQ=
 =buZA
 -END PGP SIGNATURE-
 ___
 squid-dev mailing list
 squid-dev@lists.squid-cache.org
 http://lists.squid-cache.org/listinfo/squid-dev


 ___
 squid-dev mailing list
 squid-dev@lists.squid-cache.org
 http://lists.squid-cache.org/listinfo/squid-dev



 --
 Francesco



-- 
Francesco
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

[squid-dev] [MERGE] Fix splay

2015-01-02 Thread Kinkie

Hi,
  splay uses lots of C-isms still, which make recent clang fail the build badly.

Things like:
SplayNodefoo *root = NULL
root-insert(data)

The attached patch :
- migrates all clients from using the now-private SplayNode API to Splay
- fixes Splay to account for some corner-cases
- removes always-true or always-false conditionals in SplayNode (if
(this == NULL))
- ports parts of the unit test (most were not ported assuming the aim
is to test the private API)

This builds and checks fine on ubuntu utopic with gcc and clang (clang
halts the build on a similar issue in src/comm/Read.cc but that's
another topic).

Public branch is at lp:~squid/squid/splayfix

To me this is a reasonable merge candidate; please review.

Thanks

-- 
Francesco
# Bazaar merge directive format 2 (Bazaar 0.90)
# revision_id: kin...@squid-cache.org-20150102100820-l6yces6mxkfziuge
# target_branch: file:///home/kinkie/squid/workspace/trunk/
# testament_sha1: f965cabac98083ebf3b7830322685d08ae20c2be
# timestamp: 2015-01-02 11:21:21 +0100
# base_revision_id: squid...@squid-cache.org-20150102061206-\
#   7e9auwijezfkedc5
# 
# Begin patch
=== modified file 'include/splay.h'
--- include/splay.h	2014-12-20 12:12:02 +
+++ include/splay.h	2015-01-02 10:08:20 +
@@ -15,6 +15,8 @@
 
 #include stack
 
+
+// private class of Splay. Do not use directly
 template class V
 class SplayNode
 {
@@ -30,9 +32,8 @@
 Value data;
 mutable SplayNodeV *left;
 mutable SplayNodeV *right;
-void destroy(SPLAYFREE *);
+void destroy(SPLAYFREE * = DefaultFree);
 void walk(SPLAYWALKEE *, void *callerState);
-bool empty() const { return this == NULL; }
 SplayNodeV const * start() const;
 SplayNodeV const * finish() const;
 
@@ -40,6 +41,8 @@
 
 SplayNodeV * insert(Value data, SPLAYCMP * compare);
 
+/// look in the splay for data for where compare(data,candidate) == true.
+/// return NULL if not found, a pointer to the sought data if found.
 template class FindValue SplayNodeV * splay(const FindValue data, int( * compare)(FindValue const a, Value const b)) const;
 
 /// recursively visit left nodes, this node, and then right nodes
@@ -68,11 +71,12 @@
 
 mutable SplayNodeV * head;
 template class FindValue Value const *find (FindValue const , int( * compare)(FindValue const a, Value const b)) const;
+
 void insert(Value const , SPLAYCMP *compare);
 
 void remove(Value const , SPLAYCMP *compare);
 
-void destroy(SPLAYFREE *);
+void destroy(SPLAYFREE * = SplayNodeV::DefaultFree);
 
 SplayNodeV const * start() const;
 
@@ -80,6 +84,8 @@
 
 size_t size() const;
 
+bool empty() const { return size() == 0; }
+
 const_iterator begin() const;
 
 const_iterator end() const;
@@ -92,17 +98,6 @@
 
 SQUIDCEXTERN int splayLastResult;
 
-SQUIDCEXTERN splayNode *splay_insert(void *, splayNode *, splayNode::SPLAYCMP *);
-
-SQUIDCEXTERN splayNode *splay_delete(const void *, splayNode *, splayNode::SPLAYCMP *);
-
-SQUIDCEXTERN splayNode *splay_splay(const void **, splayNode *, splayNode::SPLAYCMP *);
-
-SQUIDCEXTERN void splay_destroy(splayNode *, splayNode::SPLAYFREE *);
-
-SQUIDCEXTERN void splay_walk(splayNode *, splayNode::SPLAYWALKEE *, void *callerState);
-
-/* inline methods */
 templateclass V
 SplayNodeV::SplayNode (Value const someData) : data(someData), left(NULL), right (NULL) {}
 
@@ -110,9 +105,6 @@
 void
 SplayNodeV::walk(SPLAYWALKEE * walkee, void *state)
 {
-if (this == NULL)
-return;
-
 if (left)
 left-walk(walkee, state);
 
@@ -126,7 +118,7 @@
 SplayNodeV const *
 SplayNodeV::start() const
 {
-if (this  left)
+if (left)
 return left-start();
 
 return this;
@@ -136,7 +128,7 @@
 SplayNodeV const *
 SplayNodeV::finish() const
 {
-if (this  right)
+if (right)
 return right-finish();
 
 return this;
@@ -146,9 +138,6 @@
 void
 SplayNodeV::destroy(SPLAYFREE * free_func)
 {
-if (!this)
-return;
-
 if (left)
 left-destroy(free_func);
 
@@ -164,9 +153,6 @@
 SplayNodeV *
 SplayNodeV::remove(Value const dataToRemove, SPLAYCMP * compare)
 {
-if (this == NULL)
-return NULL;
-
 SplayNodeV *result = splay(dataToRemove, compare);
 
 if (splayLastResult == 0) { /* found it */
@@ -194,13 +180,6 @@
 {
 /* create node to insert */
 SplayNodeV *newNode = new SplayNodeV(dataToInsert);
-
-if (this == NULL) {
-splayLastResult = -1;
-newNode-left = newNode-right = NULL;
-return newNode;
-}
-
 SplayNodeV *newTop = splay(dataToInsert, compare);
 
 if (splayLastResult  0) {
@@ -225,12 +204,6 @@
 SplayNodeV *
 SplayNodeV::splay(FindValue const dataToFind, int( * compare)(FindValue const a, Value const b)) const
 {
-if (this == NULL) {
-/* can't have compared successfully :} */
-splayLastResult = -1;
-return NULL;
-}
-
 Value temp = Value();
 SplayNodeV N(temp);
 SplayNodeV *l;
@@ -316,6

Re: [squid-dev] [MERGE] Fix splay

2015-01-02 Thread Amos Jeffries

-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1

On 2/01/2015 11:25 p.m., Kinkie wrote:
 Hi, splay uses lots of C-isms still, which make recent clang fail
 the build badly.
 
 Things like: SplayNodefoo *root = NULL root-insert(data)
 
 The attached patch : - migrates all clients from using the
 now-private SplayNode API to Splay - fixes Splay to account for
 some corner-cases - removes always-true or always-false
 conditionals in SplayNode (if (this == NULL)) - ports parts of the
 unit test (most were not ported assuming the aim is to test the
 private API)
 
 This builds and checks fine on ubuntu utopic with gcc and clang
 (clang halts the build on a similar issue in src/comm/Read.cc but
 that's another topic).
 
 Public branch is at lp:~squid/squid/splayfix
 
 To me this is a reasonable merge candidate; please review.
 
 Thanks
 


I believe this is missing several delete Foo; in the ACL
destructors. You used new() to allocate the Splay objects, there
should be matching delete() at the same owner/abstraction level.
For example:

 ACLIP::~ACLIP()
 {
if (data) {
data-destroy(IPSplay::DefaultFree);
data-destroy();
delete data;
 }
 }

... although, it would be even better if the data members could be
made non-pointers now they are Splay objects. Is that easy enough to
do in this patch ?


Please dont leave empty lines lying around. Like this one in
src/acl/Ip.h that was before the private:

 IPSplay *data;

- -private:
- -static void DumpIpListWalkee(acl_ip_data * const  ip, void *state);
 };

 ... there are also empty lines being added like at the top of
include/splay.h:

 #include stack

+
+// private class of Splay. Do not use directly



in test-suite/splay.cc:
* s/oher/other/


Other than the new() / delete() issue. +1.

Amos
-BEGIN PGP SIGNATURE-
Version: GnuPG v2.0.22 (MingW32)

iQEcBAEBAgAGBQJUpn/5AAoJELJo5wb/XPRjHBEH/jSJmWgLn7hJNE11x22zxySy
zrlkcDt7MgFCID6bEDvJO27cmQIw+30yfx58pSYkQkyc5dI3xNmRrPyucUrBo6ih
zT11q8BhG/0I4XYVKuS6OhGxLwFIILqwEFL2szQ10XKgiJyhNaBbDXnrJZ+KFVOZ
srDgEwpGr3W1xp18riQX283VyX8n9vRpzGUa0GavHao8bqCGOuiKlGUc/aEXKMPz
S8aZ5eYBRhN6tuVhj41QpcdRBvmk/MfLS52v8EgH7+IBFT2gQyrkKikTERkqOCdn
tLDRDYoKAjavjrf7gdllXiZyrcMeBCyOSVjTWWrU48OYSK9UKrE+WfjiuxBCJJo=
=hxLW
-END PGP SIGNATURE-
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [MERGE] Fix splay

2015-01-02 Thread Kinkie

 I believe this is missing several delete Foo; in the ACL
 destructors. You used new() to allocate the Splay objects, there
 should be matching delete() at the same owner/abstraction level.
 For example:
 
  ACLIP::~ACLIP()
  {
 if (data) {
 data-destroy(IPSplay::DefaultFree);
 data-destroy();
 delete data;
  }
  }
 
 ... although, it would be even better if the data members could be
 made non-pointers now they are Splay objects. Is that easy enough to
 do in this patch ?

Well, splay doesn't have a destructor :\
I'll see if I can do something about it.

 Other than the new() / delete() issue. +1.

Ok, thanks. I'll also see about the empty lines.

-- 
Francesco
___
squid-dev mailing list
squid-dev@lists.squid-cache.org
http://lists.squid-cache.org/listinfo/squid-dev

Re: [squid-dev] [MERGE] Fix splay

Re: [squid-dev] [MERGE] Fix splay

[squid-dev] [MERGE] Fix splay

Re: [squid-dev] [MERGE] Fix splay

Re: [squid-dev] [MERGE] Fix splay

5 matches

Site Navigation

Mail list logo

Footer information