Subject: FACEPATH problem - finding the best match

From: [email-masked] (Dirk Craeynest)
Date: Tue, 15 Oct 91 16:14:45 MET

[ Rich Burridge suggested to post this problem on the faces mailing list
  so that hopefully somebody will be able to verify one way or the other
  whether this is a bug or not. -- dc ]

The `faces' manual entry claims (faces version 1.5.6):

----------------------------------------
  To access the face for the mail name machine.dom.ain!uid take the
  result of the first successful open from the following list of files
  (where $DIR represents iteration over the list of directories in
  FACEPATH):
        $DIR/machine.dom.ain/uid/iconname
        $DIR/dom.ain/uid/iconname
        $DIR/ain/uid/iconname
        $DIR/misc./uid/iconname
        $DIR/machine.dom.ain/unknown/iconname
        $DIR/dom.ain/unknown/iconname
        $DIR/ain/unknown/iconname
        $DIR/misc./unknown/iconname
----------------------------------------

This means that all directories in the FACEPATH are first searched for
the directory machine.dom.ain/uid.  If no match is found, then the
search is repeated for the directory dom.ain/uid, again in all
directories in the FACEPATH; and so on, until misc./unknown.

That's the expected behavior: the `best' match is used, regardless of
the face directory (at least that's what we expect, after reading the
documentation ;-) ).

Unfortunately, the code doesn't implement that!  In the file main.c, in
procedure make_iconname, the main loop [1] iterates over the directories
in the FACEPATH.  Each iteration step looks for a match [2] as described
above.

---main.c---line 609--------------------
  enum min_type
  make_iconname(facepath, community, user) /* Construct the icon name.*/
  char *facepath[MAXPATHS+1], *community, *user ;
  {

  /* Sets up community and user based on the first successful
   * open from the following list of files:
   *
   * $(FACEDIR)/community/user/[face.ps, sun.icon, 48x48x1, face.xbm]
   * $(FACEDIR)/misc./user/[face.ps, sun.icon, 48x48x1, face.xbm]
   * $(FACEDIR)/community/unknown/[face.ps, sun.icon, 48x48x1, face.xbm]
   * $(FACEDIR)/misc./unknown/[face.ps, sun.icon, 48x48x1, face.xbm]
[...]
   */
[...]

[1] for (id = 0; facepath[id] != NULL; id++) {

  /* Chdir temporarily to the current facedir for faster namei accesses,
   * if possible.
   */

      path = (chdir(facepath[id])) ? facepath[id] : "." ;

[2]   for (iu = 0; iuser[iu] != NULL; iu++)
[2]     for (ic = 0; icomm[ic] != NULL; ic++)
[2]       for (cptr = icomm[ic]; cptr != NULL; cptr = index(cptr, '.'))
            {
[...]
----------------------------------------

We find this a rather serious problem.

If, for example, in one facedir we have
  $DIR1/cs.kuleuven.ac.be/dirk/face.xbm
and in another facedir we have
  $DIR2/kuleuven.ac.be/unknown/face.xbm

Depending upon the order of $DIR1 and $DIR2 in the FACEPATH
  [email-masked]
will be matched with the first or the second face.xbm.
Thus, if $DIR2 precedes $DIR1, the `incomplete match'
  $DIR2/kuleuven.ac.be/unknown/face.xbm
takes precedence over the `complete match'
  $DIR1/cs.kuleuven.ac.be/dirk/face.xbm...

Solution:
  turn the loops [1] and [2] inside out, i.e. iterate in loop [2] over
  all directories in the FACEPATH.

Comments?

Dirk Craeynest                    | domain: [email-masked]
   The Absynt project:  Semantics | bitnet: [email-masked]
   Directed Compiler Construction | uucp:   [email-masked]
Katholieke Universiteit Leuven    |         ...!mcsun!ub4b!kulcs!dirk
Department of Computer Science    | phone:  ++32(0)16-201015 x3555
Celestijnenlaan 200 A             | fax:    ++32(0)16-205308
B-3001 Leuven (Heverlee), Belgium | telex:  23674 kuleuv b

---

From: Steve Kinzler <[email-masked]>
Date: Tue, 15 Oct 91 12:58:56 -0500

Written Oct 15 by [email-masked],[email-masked] in mail:
+---------- "FACEPATH problem - finding the best match" ----------
| The `faces' manual entry claims (faces version 1.5.6):
|
|   To access the face for the mail name machine.dom.ain!uid take the
|   result of the first successful open from the following list of files
|   (where $DIR represents iteration over the list of directories in
|   FACEPATH):
|         $DIR/machine.dom.ain/uid/iconname
|         $DIR/dom.ain/uid/iconname
|         $DIR/ain/uid/iconname
|         $DIR/misc./uid/iconname
|         $DIR/machine.dom.ain/unknown/iconname
|         $DIR/dom.ain/unknown/iconname
|         $DIR/ain/unknown/iconname
|         $DIR/misc./unknown/iconname

Yes, this is rather unclear.  Nonetheless, I have always understood it
to work the way the code is really implemented, and this is the way I
think it should remain.

| [1] for (id = 0; facepath[id] != NULL; id++) {

| [3]   path = (chdir(facepath[id])) ? facepath[id] : "." ;

| [2]   for (iu = 0; iuser[iu] != NULL; iu++)
| [2]     for (ic = 0; icomm[ic] != NULL; ic++)
| [2]       for (cptr = icomm[ic]; cptr != NULL; cptr = index(cptr, '.'))
|             {

| If, for example, in one facedir we have
|   $DIR1/cs.kuleuven.ac.be/dirk/face.xbm
| and in another facedir we have
|   $DIR2/kuleuven.ac.be/unknown/face.xbm

| Depending upon the order of $DIR1 and $DIR2 in the FACEPATH
|   [email-masked]
| will be matched with the first or the second face.xbm.
| Thus, if $DIR2 precedes $DIR1, the `incomplete match'
|   $DIR2/kuleuven.ac.be/unknown/face.xbm
| takes precedence over the `complete match'
|   $DIR1/cs.kuleuven.ac.be/dirk/face.xbm...

On the other hand, we have
  $DIR1/indiana.edu/kinzler/face.xbm
since my face is the same on all the indiana.edu subdomains (cs,ucs,cica,etc) &
  $DIR2/cs.indiana.edu/unknown/face.xbm

Now I intentionally put $DIR1 (local) ahead of $DIR2 (logos) so that
I see my face and not the default department logo.

Another reason to leave it as is, is that changing the order of the loops
would make the algorithm less efficient since the overhead of changing
face directories ([3]) applies once for every lookup attempt instead of
once for every face directory.  Right now, this overhead is low, but I
can envision something like having a hashed index of a face directory's
contents in each face directory for fast lookup instead of using the
filesystem (something I'd like to implement if ever I find the time) --
then the overhead (opening and closing the indices) becomes significant.

I think with a functional seperation of face directories and consideration
to their ordering, problems such as you describe can be avoided.

from the brain of Steve Kinzler    /o)\    [email-masked]
an organ with a mind of its own    \(o/    {ames,rutgers}!iuvax!kinzler

---

From: [email-masked] (Rex Monty Di Bona)
Date: Wed, 16 Oct 1991 15:33:33 +1000

When we looked at the faces program, we decided that the directory searching
was bogus. We already had a complete hierarchy from those good old V8 days
that was addressed as domain/domain/domain/domain/user/48x48x1. We also
changed the lookup searcgh to be user then community then facepath,
ie...
for (iu = 0; iuser[iu] != NULL; iu++)
    for (ic = 0; icomm[ic] != NULL; ic++)
      for (id = 0; facepath[id] != NULL; id++)
      {
which is what we believe is a closer reflection of how a 'normal person' would
look things up. This reduces the directory search at each level, as we now
have smaller directories. The top level directory is:

$ ls /n/icon
ETC          ch           faces        is           nl           su
MISC         cl           fi           it           no           th
MISC.old     com          fr           jp           nz           uk
README       cr           gov          kr           org          us
ar           cs           gr           machine.tab  others       usa
at           de           hu           mil          oz           uucp
au           dk           ie           mx           pt           yu
be           edu          il           my           se           za
ca           es           in           net          sg

It also, we believe, makes it easier to add new users/domains, and to
have links (oz is a link to au/oz for historical reasons :-)

We also search 'backwards' in the hierarchy, so the more exact match
is found first.

For those concerned with efficiency, the directories that are used most often,
ie, the local machine, would be kept in 'cache' by the machine. Since the
directories are now smaller, the directory search should be performed faster
too.

					Rex.

P.s. If there is interest we can post the diffs to patch to this format.

---

From: richb (Rich Burridge)
Date: Thu, 17 Oct 91 10:04:41 PDT

>was bogus.
> ...
>[details deleted]
>...

I have to agree that the current situation is a bit out of hand. I'd like
faces to get back to being a truer reflection of the V8 (and I assume V9, V10
and Plan9) vismon program.

How do other people feel about this?

Rather than have an unofficial set of patches flying around, I'd like to
make this an official change. As it's a major change, I'd bump the version
number, and reset the patchlevel to 0.

I'd also have to liase with Steve Kinzler to get the current databases
converted over to this format.

Responses to me or the mailing list please.

PS: I've just recently converted my machine over to SVR4. It's nice to
    know the mailing list still works, even though a lot of things broke.
    I'm having to generate an SVR4 version of faces, so those changes
    will be in the next patch, plus various other small changes that
    people have sent me. It seems a good time to sort out the face
    lookup once and for all.

PPS: Rex can you send me your diffs please?

---

From: Steve Kinzler <[email-masked]>
Date: Thu, 17 Oct 91 08:45:30 -0500

Written Oct 16 23:58:15 1991 by [email-masked] in mail:[email-masked]
+---------- "Re: FACEPATH problem - finding the best match" ----------
| I have to agree that the current situation is a bit out of hand. I'd like
| faces to get back to being a truer reflection of the V8 (and I assume V9, V10
| and Plan9) vismon program.
| How do other people feel about this?

Sounds good to me.  I think the ain/dom/machine database format would
be an improvement.  Not sure about having the facepath lookup loop
innermost ...

| I'd also have to liase with Steve Kinzler to get the current databases
| converted over to this format.

It should be fairly easy to work up something to convert a database from
one format to another -- and to rework the scripts that deal with the
database to work with the new format.