To: krb5-bugs@mit.edu
From: Ken Raeburn <raeburn@mit.edu>
Date: Fri, 27 Aug 2004 17:12:11 -0400
Subject: profile iterator breaks when modifications made

(This is a problem Miro ran into long ago, but we haven't bothered to
track down.)

If a program uses an iterator to walk over a set of entries in the
profile with a particular set of names, it's fine.  If the same
program deletes entries from the profile when the iterator is
examining them, the iterator can get confused.

The simplest case is: Iterate over the list of KDCs for a realm.  As
each entry is returned, delete it, and save out the result.  There
should be no KDCs left; instead, the second one is always left.

After throwing together a Tcl wrapper (using SWIG) for the profile
library API, I've managed to reproduce the problem quite nicely:

  set x [profile_init /tmp/krb5.conf]
  puts [list Opened new profile object: $x]
  set dr [profile_get_string $x libdefaults default_realm]
  puts [list Default realm is $dr]
  set kdcs [profile_get_values $x [list realms $dr kdc]]
  puts [list KDC list: $kdcs]
  set i [profile_iterator_create $x [list realms $dr kdc] 0]

  puts [list New iterator over KDC list: $i]
  set a hello
  while {[string length [lindex $a 0]]} {
          set a [profile_iterator $i]
          puts [list Iterator returns value: $a]
  }
  puts done

  set i [profile_iterator_create $x [list realms $dr kdc] 0]
  puts [list New iterator over KDC list: $i]
  set a hello
  while {[string length [lindex $a 0]]} {
          set a [profile_iterator $i]
          puts [list Iterator returns value: $a]
          set server [lindex $a 1]
          if [string length $server] {
                  puts [list Deleting node: $server]
                  profile_update_relation $x [list realms $dr kdc] $server
                  set kdcs {}
                  catch {
                          set kdcs [profile_get_values $x [list realms $dr kdc]]
                  } z
                  puts [list New KDC list: $kdcs]
          }
  }
  profile_release $x

shows the incorrect result:

  Opened new profile object: _d0d40508_profile_t
  Default realm is ATHENA.MIT.EDU
  KDC list: {kerberos.mit.edu:88 kerberos-1.mit.edu:88 kerberos-2.mit.edu:88
kerberos-3.mit.edu:88}
  New iterator over KDC list: _20020608_iter_t
  Iterator returns value: {kdc kerberos.mit.edu:88}
  Iterator returns value: {kdc kerberos-1.mit.edu:88}
  Iterator returns value: {kdc kerberos-2.mit.edu:88}
  Iterator returns value: {kdc kerberos-3.mit.edu:88}
  Iterator returns value: {{} {}}
  done
  New iterator over KDC list: _d85c0608_iter_t
  Iterator returns value: {kdc kerberos.mit.edu:88}
  Deleting node: kerberos.mit.edu:88
  New KDC list: {kerberos-1.mit.edu:88 kerberos-2.mit.edu:88 kerberos-3.mit.edu:88}
*** Note that at this point the iterator should return kerberos-1, but
*** never does; hence, the caller doesn't delete it.
  Iterator returns value: {kdc kerberos-2.mit.edu:88}
  Deleting node: kerberos-2.mit.edu:88
  New KDC list: {kerberos-1.mit.edu:88 kerberos-3.mit.edu:88}
  Iterator returns value: {kdc kerberos-3.mit.edu:88}
  Deleting node: kerberos-3.mit.edu:88
  New KDC list: kerberos-1.mit.edu:88
  Iterator returns value: {{} {}}

Ken

To: krb5-bugs@mit.edu
From: Ken Raeburn <raeburn@mit.edu>
Date: Fri, 27 Aug 2004 17:40:06 -0400
Subject: [krbdev.mit.edu #2685] profile library iterator bug
RT-Send-Cc: 

Problem analysis:

The iterator and the file data both contain serial numbers.

If the code notices that the file has been updated, the data is
re-read, and the serial number is incremented.  When the profile data
is "unshared" in order to make modifications, the current
implementation simply stores a null pointer and forces a re-reading of
the file data, including the serial number bump.

When an iterator is created, its serial number is copied from the file
data.  The iterator also includes a count of how many items it has
read.  If, while using the iterator, the code notices that the file
data serial number has been updated, the current pointers into the
file data are discarded, new pointers are fetched, and the code skips
over the saved number of entries with the corresponding set of labels.

So, in the simple test case I described:
 - The iterator copies the original file data serial number.
 - The first entry is returned, and the iterator counter indicates one
   entry has already been returned.
 - The file data is "unshared" and modified, with a serial number
   update.  The first entry has been deleted, and thus the new first
   entry is the former second entry.
 - The iterator code notices the serial number change, and looks up
   the new KDC list, skipping over the new first entry (which is now
   the original second entry), to point to the new second entry
   (formerly the third entry).
 - The remaining entries, except for the now-first entry, are returned
   by the iterator and deleted without problem.

So the iterator effectively never sees that first entry, and thus it
doesn't get deleted.

To fix this, perhaps the iterator should not use a simple index, but
some uid (unique per profile data tree) associated with the node.  The
"unsharing" process can duplicate the old tree, including uids, so the
iterator code can find its place more correctly.

I suspect there may also be potential problems with the iterator
hanging on to pointers to nodes that have been deleted from the tree,
storage freed, etc.  (If not for the current test case, then try one
with multiple iterators, or otherwise deleting all entries while one
iterator is in the middle of the list.)  So the deleted nodes should
probably just get a flag set, instead of being deleted immediately.
Or, if we want to be more aggressive about freeing storage as early as
possible, a ref count of iterators currently pointed to the node.

This would still leave open the problem of re-synchronizing the
iterator after re-reading the contents of a file updated externally.

Ken

P.S.  The Tcl wrapper program has been checked in in the util/profile
directory, but is not built by default, and does not get installed.
It's essentially tclsh with a few profile_* commands added.

RT-Send-CC: lxs@mit.edu

I forgot to attach it to this ticket, but the checkin I just did,
particularly version 1.27 of util/profile/prof_tree.c, should fix this.
 Please try it out and see.