Ticket History #615: bugs with the handling of ->prev in util/profile/prof_tree.c

From chas@cmf.nrl.navy.mil Sat Jul 18 10:47:34 1998
Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU [18.69.0.28]) by rt-11.MIT.EDU (8.7.5/8.7.3) with SMTP id KAA16325 for <bugs@RT-11.MIT.EDU>; Sat, 18 Jul 1998 10:47:33 -0400
Received: from ginger.cmf.nrl.navy.mil by MIT.EDU with SMTP
id AA23720; Sat, 18 Jul 98 10:47:48 EDT
Received: from borg.cmf.nrl.navy.mil (chas@borg.cmf.nrl.navy.mil [134.207.10.148])
by ginger.cmf.nrl.navy.mil (8.8.5/8.8.5) with ESMTP id KAA03317;
Sat, 18 Jul 1998 10:47:19 -0400 (EDT)
Received: (from chas@localhost)
by borg.cmf.nrl.navy.mil (8.8.5/8.8.5) id KAA07065;
Sat, 18 Jul 1998 10:47:17 -0400 (EDT)
Message-Id: <199807181447.KAA07065@borg.cmf.nrl.navy.mil>
Date: Sat, 18 Jul 1998 10:47:17 -0400 (EDT)
From: Chas Williams <chas@cmf.nrl.navy.mil>
Reply-To: chas@cmf.nrl.navy.mil
To: krb5-bugs@MIT.EDU
Cc: kenh@cmf.nrl.navy.mil
Subject: bugs with the handling of ->prev in util/profile library
X-Send-Pr-Version: 3.99

Center for Computational Science
Naval Research Laboratory
powerpc, macos 8.1


in prof_tree.c, in profile_delete_node_relation(), you will see
the following code:

if (p->next)
p->next->prev = p;
profile_free_node(p);

this is obviously wrong, since you assign the p->next->prev to
something with gets freed in the next line. its probably a typo.
the programmer meant to assign p->next->prev to p->prev.

in prof_tree.c, in profile_add_node(), insertion into the middle
of a link list doesnt update the ->prev pointer of the following
list item. in the notation used the source code, imagine a
two item list, with 'last' pointing to the head of the list,
and 'p' pointing to the end of the list. 'new' is the node that
is about to be inserted in between:

from profile_add_node():

new->prev = last;
if (last)
last->next = new;
else
section->first_child = new;
if (p)
new->next = p;

the state before this code is:

-> ->
null last p null
<- <-

'running' the code does the following assignments:

new.prev = last;
last.next = new;
new.next = p;

this gives the following (broken) linked list:

-> -> ->
null last new p null
<- <- /
<-------

p.prev is never changed, and breaks the list the the backward
direction. note that the foward direction is fine, and this
actually doesnt cause problems until one attempts to delete a node
in the middle of the list. p.prev should point to new.

this bug appeared in the macintosh 'cns-config' application.
modifying the profile in memory produced strange results (often
crashing) -- its the only kerberos application that uses the
delete_node profile functions (in order to edit the configuration
file via a 'friendly' user interface) hopefully the above is
sufficient.
a context diff follows:

diff -c -r krb5-1.0.3.macos/src/util/profile/prof_tree.c krb5-1.0.3/src/util/profile/prof_tree.c
*** krb5-1.0.3.macos/src/util/profile/prof_tree.c Fri Jul 17 18:32:26 1998
--- krb5-1.0.3/src/util/profile/prof_tree.c Mon Nov 17 22:51:18 1997
***************
*** 166,175 ****
last->next = new;
else
section->first_child = new;
! if (p) {
new->next = p;
- p->prev = new;
- }
if (ret_node)
*ret_node = new;
return 0;
--- 166,173 ----
last->next = new;
else
section->first_child = new;
! if (p)
new->next = p;
if (ret_node)
*ret_node = new;
return 0;
***************
*** 319,325 ****
section->first_child = p->next;
next = p->next;
if (p->next)
! p->next->prev = p->prev;
profile_free_node(p);
p = next;
}
--- 317,323 ----
section->first_child = p->next;
next = p->next;
if (p->next)
! p->next->prev = p;
profile_free_node(p);
p = next;
}


From: tytso@MIT.EDU
To: chas@cmf.nrl.navy.mil
Cc: krb5-bugs@MIT.EDU, krb5-unassigned@RT-11.MIT.EDU, kenh@cmf.nrl.navy.mil,
gnats-admin@RT-11.MIT.EDU, krb5-prs@RT-11.MIT.EDU
Subject: Re: krb5-libs/615: bugs with the handling of ->prev in util/profile library
Date: Thu, 6 Aug 1998 22:05:24 -0400

Hi Chas,

Thanks for reporting the bugs on the profile library! I used
a slightly different fix for the profile_add_node() to make the code a
little smaller and cleaner.

- Ted

Index: prof_tree.c
===================================================================
RCS file: /cvs/krbdev/krb5/src/util/profile/prof_tree.c,v
retrieving revision 1.6
retrieving revision 1.7
diff -u -r1.6 -r1.7
--- prof_tree.c 1997/03/25 06:29:54 1.6
+++ prof_tree.c 1998/08/07 02:03:31 1.7
@@ -145,9 +145,14 @@
if (section->value)
return PROF_ADD_NOT_SECTION;

+ /*
+ * Find the place to insert the new node. We look for the
+ * place *after* the last match of the node name, since
+ * order matters.
+ */
for (p=section->first_child, last = 0; p; last = p, p = p->next) {
cmp = strcmp(p->name, name);
- if (cmp >= 0)
+ if (cmp > 0)
break;
}
retval = profile_create_node(name, value, &new);
@@ -155,19 +160,14 @@
return retval;
new->group_level = section->group_level+1;
new->parent = section;
- if (cmp == 0) {
- do {
- last = p;
- p = p->next;
- } while (p && strcmp(p->name, name) == 0);
- }
new->prev = last;
+ new->next = p;
+ if (p)
+ p->prev = new;
if (last)
last->next = new;
else
section->first_child = new;
- if (p)
- new->next = p;
if (ret_node)
*ret_node = new;
return 0;
@@ -317,7 +317,7 @@
section->first_child = p->next;
next = p->next;
if (p->next)
- p->next->prev = p;
+ p->next->prev = p->prev;
profile_free_node(p);
p = next;
}

Responsible-Changed-From-To: krb5-unassigned->tytso@mit.edu
Responsible-Changed-By: tytso
Responsible-Changed-When: Thu Aug 6 22:07:33 1998
Responsible-Changed-Why:

State-Changed-From-To: open-closed
State-Changed-By: tytso
State-Changed-When: Thu Aug 6 22:07:58 1998
State-Changed-Why: Fix committed to tree.