To:       Distribution

From:     E. J. Wallman

Date:     January 26, 1983

Subject:  More on improvements to the Multics search facility


    In MTB-565,  Benson Margulies pointed out  two major deficiencies
in the Multics search facility (search_paths_, etal.), and proposed a
technology and implementation to overcome those deficiencies.

    This paper presents an alternative to the proposal in MTB-565.

    Please address comments to the author:

via Multics mail:
    Wallman.Multics at System M

via forum meeting:
    >udd>Multics>C&F>C&F_Maintenance (C&F) on System M

via hardcopy mail:
    Ed Wallman, MS Z-30 (AZ05)
    PO Box 8000,
    Phoneix, AZ 85066

via telephone:
    (602) 862-6637 (HVN 357)


Multics Project internal working  documentation.  Not to be reproduced
or distributed outside the Multics Project.

page 2                         MTB-609


    In  MTB-565,  Margulies  points  out  two  major  search facility

    1)  Manipulation  of a  search list with  the *_search_paths com-
        mands is clumsy and tedious due to the necessity to reference
        existing paths exactly  as they are recorded in  the the list
        (and displayed by print_search_paths).

    2)  There is no feature that provides verification that a path to
        be entered into a search list is valid for the purpose of the
        list.  For example,  some lists may need to  preclude the use
        of -referencing_dir, others may require that only directories
        be searched, and still others  may require only segments with
        specific suffices (eg., the dictionaries).

    This  MTB  addresses  each  of these  points  in  greater detail,
answering the first completely and the second in part.

Manipulation of Search Lists

    There  are three  different objects  that can  be entered  into a
search list:

    o   keywords
        Keywords present  no problem.  Since  they are few  in number
        and  completely  determined by  the  *_search_paths commands,
        their representation in the search  list can be coerced to be
        their unique long forms.  Thus,  they need no further identi-

    o   storage system objects
        Similarly, storage system objects  present no problem.  Since
        they exist, the storage system  can be queried for their UIDs
        and  the  UIDs  used  to determine  if  the  random pathnames
        returned  by  expand_pathname_  (or   the  use  of  different
        addnames  by  the  user) do  indeed  refer to  the  same real
        object.  There is a 36 bit  pad word in the sl_info structure
        that can be used for  UIDs compatibly.  Since the search list
        structure is  to be changed for  support of path verification
        (see discussion following), a UID  datum can be added to that
        structure.  Note that the search  list is maintained soley by
        the search_paths_  entrypoints so that  any structure changes
        are  transparent  to callers  using  the search  facility for

        This approach  suffers one flaw:   if the owner  of a storage
        system object recreates it (thus changing the UID) during the
        life of a process, the  UID recorded in that process's search
        segment becomes invalid and references  to the path will have
        to revert to the "exact path" techinque.

                               MTB-609                         page 3

    o   nonobjects
        The creation  of pseudo-UIDs for  nonobjects (in this  MTB, a
        "nonobject"  is  anything that  is not  known to  the storage
        system;   examples   are  pathnames   containing  nonexistent
        entrynames,  archive  component  pathnames,  and  FNP channel
        numbers)  appears to  be an insoluble  problem.  For example,
        consider a  search list that contains  the paths >udd>a>b>foo
        and  >exl>a>b>foo,  where  both  "b"  directories  exist  and
        neither  "foo"  exists.  If  a user  has >udd>a>b  as working
        directory and references "foo",  get_wdir_ could quite easily
        return  >user_dir_dir>a>b  (since it,  like expand_pathname_,
        gets  paths from  the pathname associative  store).  Which of
        the   nonexistent  "foo"s   is  being   referenced?   Several
        possibilities have been suggested:

        1)  Refuse to enter nonobjects into the search list.  This is
            the  solution enforced  by set_search_rules  and "solves"
            the  problem by  avoiding it.  However,  this solution is
            unacceptable  for  search  lists  (even for  the  case of
            nonexistent  entrynames)  since  the  search  facility is
            intended  to  be able  to search  for "anything"  that an
            application using may want to search for.  If all objects
            not known to the storage system were ruled out, the basic
            intent of the search facility would be subverted.

        2)  Record the UID for each real entryname in the search path
            in  the  process  search segment.   While  feasible, this
            solution  is very  unattractive because of  the amount of
            implementation work  needed and the high  cost in perfor-
            mance  due  to the  addition  of more  arrays  with refer
            extents.  Further, this makes  the problem of search path
            referencing even  more obscure since  all names appearing
            after  the  last real  entryname would  still have  to be
            given exactly  and the point  in the pathname  where this
            need arises is not visible  to the user.  Someday, it may
            be  desirable  to  add  starname  support  to  the search
            facility.   If  this  happens, the  number  of nonobjects
            appearing in search lists will escalate drastically.

        3)  Provide  a  "regular  expression" feature  like  the text
            editors.  This is a feasible solution and far less costly
            than 2).  If the user types, say, "dsp list /.*foo/", the
            program will scan the search  list for hits and query for
            action  on  each  hit.   However,  the  proper  action in
            response to "asp list bar -after /.*foo/" is not clear.

        4)  Do nothing.  Although it  retains the current undesirable
            behavior of path manipulation  with regard to nonobjects,
            this  is the  expedient solution.  Indeed,  the user will
            penalized  for  inaccurate  typing  of  paths,  but  such
            penalization  is  certainly  not unknown  in  the Multics
            command environment.

page 4                         MTB-609

        Thus, since there seem to  be no criteria for determining the
        unique identity of nonobjects, we choose the last alternative
        and do nothing.


    The support of UIDs for storage system objects can be implemented
with the  following trivial change  in the sl_info  structure and the
addition  of a  UID datum to  the structure  of a search  list in the
process search  segment (see discussion of  path verification follow-

/* Modified  12/21/82 by Ed Wallman: Changed sl_info.paths.pad2 to
             sl_info.paths.uid in support of relative pathnames.
             This is a compatible change; no new version number.
dcl 1 sl_info       aligned based (sl_info_p),
      2 version     fixed bin,     /* Must be 1 */
      2 num_paths   fixed bin,     /* Number of search paths */
      2 change_index_p             /* Pointer to list's update count */
                    pointer,       /* IN THE PROCESS SEARCH SEG */
      2 change_index               /* This list's update count */
                    fixed bin (71),
      2 pad1        (6) bit (36),  /* Must be zero */
      2 paths       (sl_info_num_paths refer (sl_info.num_paths)),
        3 type      fixed bin,     /* Type of search path */
        3 code      fixed bin (35),/* Standard status code for path */
        3 uid       bit (36) aligned,/* Unique id of path */
        3 pathname  char (168) unaligned;/* Search pathname */

Verification of Search Paths

    This is the more serious of the two deficiencies and deserves the
more work.   If a user  enters an inappropriate path,  for example, a
directory  named "foo.dict"  into the  dictionary search  list, there
will no notice given until the dictionary commands attempt to use the
path.   That subsequent  notice can  be quite  abrupt and unfriendly.
For the example given, the error is:

    Error: This operation is not allowed for a directory. >udd>...
           (by >unb>find_dictionary_word ...)
           etc. ...

followed by failure of the  dictionary command to proceed through the
rest of the search list.

                               MTB-609                         page 5

    Thus, two new needed features are suggested:(1)

    1)  control over the type of path to be entered
        This  can be  supported by the  addition of a  word of switch
        bits  with  specific bit  positions  assigned to  the various
        allowable objects.

    2)  a list of allowed/required suffices
        This list is clearly needed.   Currently, there are two lists
        defined  in  search_list_defaults_  (dictionary  and declare)
        that require segments with a specific suffix.

Where to Store the New data?

    These new data must be kept in the default search list since that
is the  only place that  allows the control  to be exercised  for the
entire system.  It cannot be kept  in sl_info because the storage for
that structure is destroyed after  each invocation of a *_search_path
command; it  cannot be kept  in the process search  list because that
would require the sharing of active search segments, an approach that
does not seem feasible.


(1) This  MTB  addresses  only  control  over  valid  keywords, valid
    storage system  objects, and suffixes on  storage system objects.
    Control  over  nonobjects  and  the  contents  of  storage system
    objects, although  addressed by Margulies, are  not covered here;
    they are left for the next round of search facility enhancements.

    Note  that  the  switch  bit  word  is  sufficiently  powerful to
    encompass  a  great number  of  different objects,  and  that the
    suffix  technology proposed  could be  modified into  a much more
    general "name type" technology.

    In  particular,  Margulies  suggests  that  an  entry  point into
    LISTNAME_sl_  could be  designed to  provide verification  of the
    contents  of  a  search  object.   For  example,  the  dictionary
    commands can only make effective  use of non-empty keyed files, a
    list for searching for a dial_out channel should contain only FNP
    channel id strings, certain search  archives could be required to
    contain components named, say, "frobus_*.*", etc.  However, since
    the dictionary commands (the premier  candidate as caller of this
    new  interface) currently  does no  internal checking  on its own
    behalf, creation  of the interface  is not judged to  have a high

    (As evidence of the lack of  checking, simply create an empty MSF
    or SSF  named foo.dict, add  that path to  your dictionary search
    list,  and  use "find_dictionary_word  barfo".  The  command will
    blandly tell you it could not find the word!)

page 6                         MTB-609

    Margulies suggests  that the data  be kept and enforced  by a new
per-list support module, LISTNAME_sl_.  Although feasible and techni-
cally correct, this approach is  unattractive because it requires the
creation and maintenance of several new system modules.

How to Support ad hoc Search Lists?

    The next  question is that  of support for  path verification for
search  lists that  are not  defined in  search_list_defaults_.  If a
developer wants to create a new or replacement search list, s/he need
merely replicate the code  found in search_list_defaults_.cds for the
new list.

    However, if the new default list is a replacement for a list that
is already defined in search_list_defaults_  or is in a directory not
in the user's  current search rules, the search  facility cannot find
it!  It uses the dynamic  linker (without -referencing_dir) to locate
the  default  list   ONLY  after  it  fails  to   find  the  list  in
search_list_defaults_.  Even  then, it will  not be found  unless the
user  has taken  overt action (like  initiating or setting  a link in
wdir)  to make  it findable by  the linker.  This  shortcoming can be
overcome  by  providing  a  new  control  argument, -default_pathname
(-dpn), for (set add)_search_paths.  The usage would be:

    ssp list -dft -dpn path>
    asp list foo {-modifiers} -dpn path>

The  presence of  this path  in the  command line  would override the
prior use of search_list_defaults_.

    Note  that  this  proposal  does  not  support  verification  for
dynamically  created  lists, that  is,  lists that  are  created with
set_search_paths but dont have a anywhere.(1)


    Since the  details of the  search structure must now  be known to
both search_paths_  and the *_search_paths  commands, the declaration
of  the structure  has been taken  out of  search_paths_.pl1 and made
into  a  new include  file.   That include  file is  presented below.
Further,  the  code  in   <list>_default.cds  must  be  significantly
expanded.   Excerpts  from a  modified  search_list_defaults_.cds are
also shown below.

    There  are  no new  system  modules, no  new entrypoints,  and no
changes to any  of the interfaces to search_paths_;  the only changes

(1) Such support could be added  with more new control arguments, but
    the complexity of the implementation doesnt seem justified by the
    expected utility of the feature.

                               MTB-609                         page 7

are to the actions performed by those various entrypoints.  Thus, all
callers of those search_paths_ entrypoints need no work.

Compatibility and Flag Days

    Although  there  are no  changes in  the interfaces  involving in
searching, there  are in those involving  management of search lists.
The version of the process search segment will change and the default
search lists will acquire a brand new version number.

    The  first  version change  poses  no problems  since  the search
facility  is already  able to  cope with  a dynamic  change in search
segment version (there  is a flaw in that  the process search segment
will be recreated with defaults instead of the paths that were in the
existing search segment, but the problem is thought to be minor since
dynamic version switching of search  facility versions is not a usual
user action).

    The second version change has  an eventual flag day.  To minimize
the trauma  of that day,  code has been added  (and clearly delimited
for  ease  of  removal)  to support  both  version  SRCH0001  and the
obsolete un-version and  a warning will be issued  when an un-version
default search list is used (this  warning will be deactivated in the
EXL  installation).  Thus,  users will  get at  least one  release of
noisome warning  messages to clean  up their default  search list act
before the obsolete version support is removed.

page 8                         MTB-609

/*                  BEGIN search_segment.incl.pl1           */

/*        search segment data structures

Created 12/31/82 by Ed Wallman with declarations taken from search_paths_.pl1
Modified 12/31/82 by Ed Wallman: Added list control feature - version 3 of
          search_seg and version SRCH0001 of default_search_list.

          The list_header must remain in the same generation of storage because
          users are given pointers to list_header.update_count */

/* format: style2,ind3,ll80,dclind4,idind16,comcol41,linecom */

dcl 1 search_seg    based (search_seg_ptr),
      2 header,
        3 version   fixed binary,  /* search segment version */
        3 first_list_header_off    /* offset of first list's list_header */
                    offset (search_seg.area),
        3 last_list_header_off     /* offset of last list's list_header */
                    offset (search_seg.area),
      2 area        area (sys_info$max_seg_size
                    - divide (length (unspec (search_seg.header)), 36, 19))

dcl 1 list_header   based (search_list_header_ptr),
      2 link                       /* offset of next list's list_header */
                    offset (search_seg.area),
      2 back_link                  /* offset of last list's list_header */
                    offset (search_seg.area),
      2 list_control_off           /* offset of list_control */
                    offset (search_seg.area),
      2 list_name_off              /* offset of list_name */
                    offset (search_seg.area),
      2 search_list_off            /* offset of search_list */
                    offset (search_seg.area),
      2 update_count               /* number of search list updates */
                    fixed binary (71);

dcl 1 list_control  based (search_list_control_ptr),
      2 sws         bit (36),      /* allowed keyword switches */
      2 suffix_count               /* number of required suffixes */
                    fixed bin,
      2 suffixes    (list_control_suffix_count
                    refer (list_control.suffix_count)) char (32);

dcl 1 list_name     based (search_list_name_ptr),
      2 name_count  fixed binary,  /* number of synonyms */
      2 names       (list_name_name_count refer (list_name.name_count))
                    char (32);     /* search list names */

dcl 1 search_list   based (search_list_ptr),
      2 path_count  fixed binary,  /* number of search paths */
      2 paths       (search_list_path_count refer (search_list.path_count))

                               MTB-609                         page 9

        3 type      fixed binary,  /* search path type */
                                   /* FS UID, if any */
        3 uid       bit (36) aligned,
        3 pathname  char (168),    /* search pathname */
        3 mark      bit (1);       /* temporary */

dcl 1 default_search_list
                    based (default_search_list_ptr),
      2 version     char (8),      /* structure version id */
      2 control_sws bit (36),      /* list control switches */
      2 name_count  fixed binary,  /* number of synonyms */
      2 path_count  fixed binary,  /* number of search paths */
      2 suffix_count
                    fixed bin,     /* number of suffixes */
      2 names       (0 refer (default_search_list.name_count)) char (32),
      2 suffixes    (0 refer (default_search_list.suffix_count)) char (32),
      2 paths       (0 refer (default_search_list.path_count)),
        3 type      fixed binary,  /* search path type */
        3 pathname  char (168);    /* search pathname */

dcl 1 v0_default_search_list            /* OLD (V0) DEFAULT SEARCH LIST */
                    based (default_search_list_ptr),
      2 name_count  fixed binary,       /* number of synonyms */
      2 path_count  fixed binary,       /* number of search paths */
      2 names            (0 refer (v0_default_search_list.name_count))
                    char (32),
      2 paths       (0 refer (v0_default_search_list.path_count)),
        3 type      fixed binary,       /* search path type */
        3 pathname  char (168);         /* search pathname */

dcl search_seg_ptr  ptr init (null);
                                   /* pointer to the search segment */
dcl search_seg_version_3
                    fixed binary internal static options (constant)
                    initial (3);
dcl search_list_header_ptr         /* pointer to a list header */
                    ptr init (null);
dcl search_list_control_ptr        /* pointer to a list control structure */
                    ptr init (null);
dcl list_control_suffix_count
                    fixed bin init (0);
dcl search_list_name_ptr           /* pointer to a list name structure */
                    ptr init (null);
dcl list_name_name_count
                    fixed bin init (0);
dcl search_list_ptr                /* pointer to a search list */
                    ptr init (null);
dcl search_list_path_count
                    fixed bin init (0);
dcl default_search_list_ptr        /* pointer to a default search list */
                    ptr init (null);

page 10                        MTB-609

                    char (8) int static options (constant)
                    init ("SRCH0001");

dcl RDIR_SW                        /* ref dir keyword switch bit */
                    bit (36) init ("400000000000"b3);
dcl WDIR_SW                        /* working dir keyword switch bit */
                    bit (36) init ("200000000000"b3);
dcl PDIR_SW                        /* process dir keyword switch bit */
                    bit (36) init ("100000000000"b3);
dcl HDIR_SW                        /* home dir keyword switch bit */
                    bit (36) init ("040000000000"b3);
dcl DIR_PATH_SW                    /* directory pathname switch bit */
                    bit (36) init ("020000000000"b3);
dcl SEG_PATH_SW                    /* segment pathname switch bit */
                    bit (36) init ("010000000000"b3);
dcl MSF_PATH_SW                    /* MSF pathname switch bit */
                    bit (36) init ("004000000000"b3);
dcl KEYS_OK                        /* keywords allowed */
                    bit (36) init ("740000000000"b3);
dcl KEYS_DIRS_OK                   /* keywords and directories allowed */
                    bit (36) init ("760000000000"b3);

/*                  END search_segment.incl.pl1             */

   Modified 01/01/83 by Ed Wallman: Added info for list control feature.

search_list_defaults_:                  /* exerpts ONLY */

/* automatic */

          dcl     1 lists                aligned,
                    2 comp               bit (0) aligned,
                    2 compose,
                      3 version          char (8),
                      3 control_sws      bit (36),
                      3 name_count       fixed binary,
                      3 path_count       fixed binary,
                      3 suffix_count     fixed bin,
                      3 names            (2) char (32),
                      3 suffixes         (1) char (32),
                      3 paths            (4) like search_path,
                    2 dcl                bit (0) aligned,
                    2 declare,
                      3 version          char (8),
                      3 control_sws      bit (36),
                      3 name_count       fixed binary,
                      3 path_count       fixed binary,
                      3 suffix_count     fixed bin,
                      3 names            (2) char (32),
                      3 suffixes         (1) char (32),

                               MTB-609                        page 11

                      3 paths            (1) like search_path,
                    2 dict               bit (0) aligned,
                    2 dictionary,
                      3 version          char (8),
                      3 control_sws      bit (36),
                      3 name_count       fixed binary,
                      3 path_count       fixed binary,
                      3 suffix_count     fixed bin,
                      3 names            (2) char (32),
                      3 suffixes         (1) char (32),
                      3 paths            (1) like search_path,
/* program */

          lists.compose.version = DEFAULT_SEARCH_LIST_VERSION_1;
          lists.compose.control_sws = KEYS_DIRS_OK;
          lists.compose.name_count = hbound (lists.compose.names, 1);
          lists.compose.path_count = hbound (lists.compose.paths, 1);
          lists.compose.suffix_count = hbound (lists.compose.suffixes, 1);
          lists.compose.suffixes (*) = "";
          lists.compose.names (1) = "compose";
          lists.compose.names (2) = "comp";
          lists.compose.paths (1).type = WORKING_DIR;
          lists.compose.paths (1).pathname = "-working_dir";
          lists.compose.paths (2).type = UNEXPANDED_PATH;
          lists.compose.paths (2).pathname = ">udd>[user project]>compose_macros";
          lists.compose.paths (3).type = REFERENCING_DIR;
          lists.compose.paths (3).pathname = "-referencing_dir";
          lists.compose.paths (4).type = ABSOLUTE_PATH;
          lists.compose.paths (4).pathname = ">unb";

          lists.declare.version = DEFAULT_SEARCH_LIST_VERSION_1;
          lists.declare.control_sws = SEG_PATH_SW;
          lists.declare.name_count = hbound (lists.declare.names, 1);
          lists.declare.path_count = hbound (lists.declare.paths, 1);
          lists.declare.suffix_count = hbound (lists.declare.suffixes, 1);
          lists.declare.suffixes (1) = ".dcl";
          lists.declare.names (1) = "declare";
          lists.declare.names (2) = "dcl";
          lists.declare.paths (1).type = ABSOLUTE_PATH;
          lists.declare.paths (1).pathname = ">sss>pl1.dcl";

          lists.dictionary.version = DEFAULT_SEARCH_LIST_VERSION_1;
          lists.dictionary.control_sws = SEG_PATH_SW;
          lists.dictionary.name_count = hbound (lists.dictionary.names, 1);
          lists.dictionary.path_count = hbound (lists.dictionary.paths, 1);
          lists.dictionary.suffix_count = hbound (lists.dictionary.suffixes, 1);
          lists.dictionary.suffixes (1) = ".dict";
          lists.dictionary.names (1) = "dictionary";
          lists.dictionary.names (2) = "dict";
          lists.dictionary.paths (1).type = ABSOLUTE_PATH;
          lists.dictionary.paths (1).pathname = ">unb>standard.dict";

page 12                        MTB-609



Finally, the  concepts discussed have been  implemented and are ready
for exposure in EXL when it is deemed advisable to do so.