[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Nits]

Versions: 00

Network Working Group                                          T. Keiser
Internet-Draft                                               Sine Nomine
Intended status: Informational                            April 23, 2012
Expires: October 25, 2012


                 AFS-3 Directory Object Type Definition
                 draft-keiser-afs3-directory-object-00

Abstract

   Directory lookups in the AFS-3 distributed file system are supported
   by defining a canonical encoding for a directory object, and
   transmitting all--or part--of that object from a file server to its
   clients so that clients may resolve paths into AFS file IDs (FIDs).
   This memo describes the AFS-3 directory object wire encoding.

Internet Draft Comments

   Comments regarding this draft are solicited.  Please include the
   AFS-3 protocol standardization mailing list
   (afs3-standardization@openafs.org) as a recipient of any comments.

Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   This Internet-Draft will expire on October 25, 2012.

Copyright Notice

   Copyright (c) 2012 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of



Keiser                  Expires October 25, 2012                [Page 1]


Internet-Draft           AFS-3 Directory Object               April 2012


   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1.  Abbreviations  . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Conventions  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Constants  . . . . . . . . . . . . . . . . . . . . . . . . . .  4
   4.  Directory Object Structure . . . . . . . . . . . . . . . . . .  5
   5.  Page Structure . . . . . . . . . . . . . . . . . . . . . . . .  5
     5.1.  Record Index . . . . . . . . . . . . . . . . . . . . . . .  6
     5.2.  Page header  . . . . . . . . . . . . . . . . . . . . . . .  6
       5.2.1.  Allocation Bitmap  . . . . . . . . . . . . . . . . . .  7
   6.  Page N=0 structure . . . . . . . . . . . . . . . . . . . . . .  8
     6.1.  Directory Header . . . . . . . . . . . . . . . . . . . . .  9
   7.  Page N>0 structure . . . . . . . . . . . . . . . . . . . . . . 10
   8.  Directory Entry  . . . . . . . . . . . . . . . . . . . . . . . 10
     8.1.  Directory Entry Record . . . . . . . . . . . . . . . . . . 11
     8.2.  Directory Entry Extension Record . . . . . . . . . . . . . 12
   9.  Name Hash Function . . . . . . . . . . . . . . . . . . . . . . 13
   10. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 13
   11. AFS Assign Numbers Registrar Considerations  . . . . . . . . . 13
   12. Security Considerations  . . . . . . . . . . . . . . . . . . . 13
   13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14
     13.1. Normative References . . . . . . . . . . . . . . . . . . . 14
     13.2. Informative References . . . . . . . . . . . . . . . . . . 14
   Appendix A.  Example Directory Object  . . . . . . . . . . . . . . 14
     A.1.  18-character name string . . . . . . . . . . . . . . . . . 15
   Appendix B.  C Implementation of Directory Hash Function . . . . . 16
   Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 16















Keiser                  Expires October 25, 2012                [Page 2]


Internet-Draft           AFS-3 Directory Object               April 2012


1.  Introduction

   AFS-3 [AFS1] [AFS2] is a distributed file system that has its origins
   in the VICE project [CMU-ITC-84-020] [VICE1] at the Carnegie Mellon
   University Information Technology Center [CMU-ITC-83-025], a joint
   venture between CMU and IBM.  VICE later became AFS when CMU moved
   development to a new commercial venture called Transarc Corporation,
   which later became IBM Pittsburgh Labs.  AFS-3 is a suite of un-
   standardized network protocols based on a remote procedure call (RPC)
   suite known as Rx [AFS3-RX].  While de jure standards for AFS-3 fail
   to exist, the various AFS-3 implementations have agreed upon certain
   de facto standards, largely helped by the existence of an open source
   fork called OpenAFS that has served the role of reference
   implementation.  In addition to using OpenAFS as a reference, IBM
   wrote and donated developer documentation that contains somewhat
   outdated specifications for the Rx protocol and all AFS-3 remote
   procedure calls, as well as a detailed description of the AFS-3
   system architecture.

   Unlike most classical network file systems, AFS-3 explicitly eschews
   remote procedure calls to facilitate file server-assisted directory
   lookup operations.  This was a conscious decision meant to limit
   server load by placing lookup operations on the clients.  In the
   common cases, where there is significant locality of reference to
   directory entries, this results in a substantial reduction in server
   load (especially given the AFS-3 cache coherence model).  It should
   be noted that 23 years of empirical evidence have borne out this
   decision as useful for many general-purpose workloads, while
   disadvantageous for certain very specific workloads (e.g., large
   directory objects with extremely non-uniform directory entry
   reference distributions--where the server overhead of a lookup rpc
   would would inconsequential compared to the directory file transfer
   overhead of the existing model).

   Due to the distributed nature of AFS-3 directory objects, a canonical
   directory wire-format is an intrinsic part of the AFS-3 protocol.
   This memo documents the directory object wire format; a future
   document will document the lookup and modification algorithms, which
   by the decentralized nature of AFS-3 directories, must be implemented
   in the to-be-specified manner.

1.1.  Abbreviations

   AFS    -  Historically, AFS stood for the Andrew File System; AFS no
           longer stands for anything






Keiser                  Expires October 25, 2012                [Page 3]


Internet-Draft           AFS-3 Directory Object               April 2012


   RPC    -  Remote Procedure Call

   Rx     -  The Remote Procedure Call mechanism utilized by AFS-3

   XDR    -  eXternal Data Representation


2.  Conventions

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC 2119 [RFC2119].


3.  Constants

   AFS_PAGESIZE = 2048

       the size of each page in an AFS-3 directory object (in octets)

   MAXPAGES     =  128

       the maximum number of pages in a legacy directory object

   BIGMAXPAGES  = 1023

       the maximum number of pages in a new (circa 1988) directory
       object

   NHASHENT     =  128

       number of hash buckets in the entry name hash table

   RECSIZE      =   32

       number of octets in a record

   LRECSIZE     =    5

       base-2 logarithm of RECSIZE

   EPP          =   64

       number of records per page







Keiser                  Expires October 25, 2012                [Page 4]


Internet-Draft           AFS-3 Directory Object               April 2012


   LEPP         =    6

       base-2 logarithm of EPP

   DHE          =   12

       number of records taken up in page 0 by the directory header


4.  Directory Object Structure

   An AFS-3 directory object consists of between 1 and BIGMAXPAGES
   (1023) "pages" of length AFS_PAGESIZE (2048 octet).

     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          page  #0000                          |
     ~                         (2048 octets)                         ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     ~                              ...                              ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          page  #1022                          |
     ~                         (2048 octets)                         ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                            Directory Structure


5.  Page Structure

   All pages in a directory object are AFS_PAGESIZE (2048 octets) in
   length.  All pages are subdivided into EPP (64) records, each RECSIZE
   (32 octets) in length.
















Keiser                  Expires October 25, 2012                [Page 5]


Internet-Draft           AFS-3 Directory Object               April 2012


     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          record #00                           |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     ~                              ...                              ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          record #63                           |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                              Page Structure

5.1.  Record Index

   Each record within a directory object is referenced by an index
   number.  This number represents the offset from the start of the
   file, in units of records, i.e., in multiples of RECSIZE.  A record
   index of 0 would thus point to record 0 in page 0, and a record index
   of 67 would point to record 3 in page 1.  Computing the file offset
   from an index is simply a matter of left logical shifting the index
   value by LRECSIZE (5) bits.  Conversely, computing the index from a
   file offset merely involves a right logical shift by LRECSIZE (5)
   bits.

5.2.  Page header

   Each 2048-octet page within an AFS-3 directory object contains a 32-
   octet (RECSIZE) header at offset 0 in the following form:




















Keiser                  Expires October 25, 2012                [Page 6]


Internet-Draft           AFS-3 Directory Object               April 2012


     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |            pgcount            |              tag              |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |   reserved    |                                               |
     +-+-+-+-+-+-+-+-+                                               +
     |                       allocation bitmap                       |
     +               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |               |                                               |
     +-+-+-+-+-+-+-+-+                                               +
     |                           reserved                            |
     ~                          (19 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                           Directory Page Header

   pgcount: 16 bits (unsigned integer)

       This field only holds meaning for page 0.  For the modern (post-
       1988) directory format, this field holds the count of valid
       directory pages (in network byte order) within the directory
       object.  When this value is zero, it denotes a legacy directory
       object.  Legacy directory objects are considered a deprecated and
       historical vestige, and thus their format is not described in
       this memo.

   tag: 16 bits (unsigned integer)

       This field MUST contain the magic value 1234 in network byte
       order.

   allocation bitmap: 8 octets (bit string)

       The allocation bitmap is a bit field which contains one bit per
       record slot within the page.  The bit field is thus 8 (EPP/8)
       octets in length.  A bit value of zero indicates the entry is
       free; a value of 1 indicates the entry has been allocated.  The
       allocation bitmap will be discussed further in Section 5.2.1.

5.2.1.  Allocation Bitmap

   The allocation bitmap contains one bit per record.  The least
   significant bit of the first octet within the bitmap references the
   page header object (which is stored at offset 0).  The second least
   significant bit of the first octet within the bitmap references the
   record index 1 (offset 32 octets into the page), and so on and so



Keiser                  Expires October 25, 2012                [Page 7]


Internet-Draft           AFS-3 Directory Object               April 2012


   forth...until the most significant bit of the eighth octet of the
   allocation bitmap references the 64th--and final--record of the page
   (record 63 at page offset 2016).

   The following invariants hold:

       page_entry_offset = page_entry_index << LRECSIZE

       alloc_bitmap_index = page_entry_index >> 3

       alloc_bitmap_bit_num = page_entry_index & 0x7

       alloc_bitmap_bit = 1 << alloc_bitmap_bit_num

   The variable page_entry_index, which is an unsigned integer between 0
   and 63, can be derived from the record index (Section 5.1) by bit-
   wise ANDing it with EPP-1.

   The equations above are written in C pseudocode--the variables are
   all assumed to be unsigned integers, and the operators are assumed to
   be identical to the ANSI C standard.


6.  Page N=0 structure

   Page 0 is special due to the directory header.  It is structured as
   follows:

   1.  a page header (see Section 5.2)

   2.  a directory header (see Section 6.1)

   3.  51 data records (EPP-DHE-1=51)


















Keiser                  Expires October 25, 2012                [Page 8]


Internet-Draft           AFS-3 Directory Object               April 2012


     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          page header                          |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                       directory header                        |
     ~                         (384 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                        data record #13                        |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     ~                              ...                              ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                        data record #63                        |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Directory Page N=0 Structure

6.1.  Directory Header

   The directory header structure is a 384-octet structure that is
   stored at an offset of 32 octets from the beginning of the directory
   object (i.e., directly following the page 0 page header--see
   Section 5.2).  The directory header layout is as follows:

     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     | page   0  map | page   1  map | page   2  map | page   3  map |
     ~                                                               ~
     | page 124  map | page 125  map | page 126  map | page 127  map |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |        hash chain    0        |        hash chain    1        |
     ~                                                               ~
     |        hash chain  126        |        hash chain  127        |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                             Directory Header

   page map:

       Each of the MAXPAGES page map fields corresponds to one of the
       MAXPAGES pages in a legacy directory object.  Each field contains
       the count of available entries in this directory page.  A value



Keiser                  Expires October 25, 2012                [Page 9]


Internet-Draft           AFS-3 Directory Object               April 2012


       of EPP indicates that this page has not yet been allocated (i.e.,
       the page header has not been initialized).

   hash chain:

       Each of the NHASHENT hash chain fields contains a record index
       for the first directory entry name that hashes to this bucket
       (see Section 5.1, and see Section 9 for a description of the hash
       function)


7.  Page N>0 structure

   Each page N>0 is structured as follows:

   1.  a page header (see Section 5.2)

   2.  EPP-1 (63) data records


     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                            header                             |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                        data record #01                        |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     ~                              ...                              ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                        data record #63                        |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                       Directory Page N>0 Structure


8.  Directory Entry

   Since entry names are of variable length, directory entries are
   structured as follows:

   o  a directory entry record (see Section 8.1)

   o  zero or more directory entry extension record(s) (see Section 8.2)




Keiser                  Expires October 25, 2012               [Page 10]


Internet-Draft           AFS-3 Directory Object               April 2012


   This sequence of records MUST be contiguous, and MUST NOT cross a
   directory page boundary.

8.1.  Directory Entry Record

   A directory entry record contains the dirent entry metadata (i.e.,
   the vnode number and uniquifier, the name hash table next pointer,
   flag bits, and the first twenty octets of the entry name string.  Its
   layout is as follows:

     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |     flags     |   reserved    |             next              |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                             vnode                             |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          uniquifier                           |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                             name                              |
     ~                          (20 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                          Directory Entry Record

   flags: 8 bits

       This is an 8-bit wide bit vector.  Currently, only one bit is
       defined: FFIRST (0x1).  This flag bit is asserted in every record
       of this type.  There are vestiges in the OpenAFS implementation
       suggesting that the original intention was to have a second flag
       bit FNEXT (0x2)--being asserted in the first octet of extension
       records--which would allow parsers to distinguish between entry
       records and extension records.  However, this idea was never
       implemented (in fact, the concept of a flags field in an
       extension record does not exist), and thus this flag bit has no
       meaning.  It should be noted that some tools have attempted to
       use this bit to distinguish between entry records and entry
       extension records (under the assumption that 0x1 is not a valid
       ASCII value for a file name string).  This technique is obviously
       error-prone, and thus SHOULD NOT be relied upon.

   next: 16 bits (unsigned integer)

       This field contains a record index (see Section 5.1) pointing to
       the next directory entry record on this name hash chain.  A value
       of zero indicates this is the last record on this chain.  This



Keiser                  Expires October 25, 2012               [Page 11]


Internet-Draft           AFS-3 Directory Object               April 2012


       entry MUST point to a record index which contains a data record
       of the directory entry type (see Section 8).

   vnode: 32 bits (unsigned integer)

       This field contains the target vnode number for this directory
       entry.  Together with the uniquifier field, this forms the
       equivalent of an inode number in the directory entry of a typical
       on-disk Unix file system.

   uniquifier: 32 bits (unsigned integer)

       This field contains the target uniquifier for this directory
       entry.  Together with the vnode field, this forms the equivalent
       of an inode number in the directory entry of a typical on-disk
       Unix file system.

   name: 20 octets (null-terminated string)

       The first 20 octets of the directory entry's name string are
       contained in this field.  If the name string (including null
       terminator) exceeds 20 octets, then this string will continue in
       a sequence of one or more directory entry extension records (see
       Section 8.2) that MUST directly proceed this record.

8.2.  Directory Entry Extension Record

   When a file name string exceeds the 20 octets set aside in an entry
   record, one or more extension records MUST be allocated contiguously
   following the base entry record in order to contain the rest of the
   name string.  The layout of an extension record is as follows:

     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                             name                              |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                     Directory Entry Extension Record

   name: 32 octets (string)

       This field contains part of an extended directory entry name
       string.  If this is the last directory entry extension record,
       then this field MUST contain a null terminator character (octet
       value zero) within its 32 octets.



Keiser                  Expires October 25, 2012               [Page 12]


Internet-Draft           AFS-3 Directory Object               April 2012


9.  Name Hash Function

   The hash function is a loop over each of the octets within the name
   string.  The hash is computed using integer arithmetic on an unsigned
   32-bit integer.  The hash MUST be initialized to zero before
   commencing iteration over the characters in the name string.  For
   each character, the hash value is multiplied by the constant 173, and
   then the value of the current character is added to the hash.  When
   the null terminator is encountered, the loop is terminated before the
   hash is multiplied by 173.

   For reasons unknown to the author, the resultant unsigned hash value
   is then compared against the value 2^31.  If the hash value is less
   than 2^31 (i.e., what would be the sign bit--if the hash value were
   signed-- is not asserted), then the resultant hash value will be the
   value computed in the above loop bitwise ANDed with the constant
   NHASHENT-1 (127).  However, if the hash value is greater than or
   equal to 2^31, then the resultant hash value will first be bitwise
   anded with the constant NHASHENT-1 (127), and then the value will be
   subtracted from the constant NHASHENT (128) to yield the final hash
   value.


10.  IANA Considerations

   This memo includes no request to IANA.


11.  AFS Assign Numbers Registrar Considerations

   This memo includes no request to the AFS Assigned Numbers Registrar.


12.  Security Considerations

   Directory metadata can contain sensistive information.  This memo
   merely specifies the wire format encoding.  Any implementation which
   may be utilized to store and retrieve directories containing entries
   whose name strings might reveal sensitive information should take
   precautions to ensure that they are never transmitted in the clear,
   and should take steps to ensure that those entries are not cached on
   machines lacking appropriate physical and network security.


13.  References






Keiser                  Expires October 25, 2012               [Page 13]


Internet-Draft           AFS-3 Directory Object               April 2012


13.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.

13.2.  Informative References

   [AFS1]     Howard, J., "An Overview of the Andrew File System"",
              Proc. 1988 USENIX Winter Tech. Conf. pp. 23-26,
              February 1988.

   [AFS2]     Howard, J., Kazar, M., Menees, S., Nichols, D.,
              Satyanarayanan, M., Sidebotham, R., and M. West, "Scale
              and Performance in a Distributed File System", ACM Trans.
              Comp. Sys. Vol. 6, No. 1, pp. 51-81, February 1988.

   [AFS3-RX]  Zayas, E., "AFS-3 Programmer's Reference: Specification
              for the Rx Remote Procedure Call Facility", Transarc Corp.
              Tech. Rep. FS-00-D164, August 1991.

   [CMU-ITC-83-025]
              Morris, J., Van Houweling, D., and K. Slack, "The
              Information Technology Center", CMU ITC Tech. Rep. CMU-
              ITC-83-025, 1983.

   [CMU-ITC-84-020]
              West, M., "VICE File System Services", CMU ITC Tech.
              Rep. CMU-ITC-84-020, August 1984.

   [VICE1]    Satyanarayanan, M., Howard, J., Nichols, D., Sidebotham,
              R., Spector, A., and M. West, "The ITC Distributed File
              System: Principles and Design", Proc. 10th ACM Symp.
              Operating Sys. Princ. Vol. 19, No. 5, December 1985.


Appendix A.  Example Directory Object















Keiser                  Expires October 25, 2012               [Page 14]


Internet-Draft           AFS-3 Directory Object               April 2012


A.1.  18-character name string

     (MSB)                                                       (LSB)
      0                   1                   2                   3
      0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |           pgcount=1           |           tag=1234            |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |   reserved    |1|         0xfff         |1 1|                 |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+                 +
     |                             0...                              |
     +               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |               |                                               |
     +-+-+-+-+-+-+-+-+                                               +
     |                           reserved                            |
     ~                          (19 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |   map[0]=49   |                                               |
     +-+-+-+-+-+-+-+-+                                               +
     |                map[1...127]=0x40 0x40 0x40 ...                |
     ~                         (127 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                hash[0...127]=0x0000 0x0000 ...                |
     ~                         (256 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |   flags=0x1   |   reserved    |          next=0x0000          |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                             vnode                             |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                          uniquifier                           |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                   name="iamexactly018chars"                   |
     ~                          (18 octets)                          ~
     +                               +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                               |      nul      |       ?       |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |            allocated extent record full of garbage            |
     ~                          (32 octets)                          ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                      unallocated garbage                      |
     ~                         (1568 octets)                         ~
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                         18-Character Name String







Keiser                  Expires October 25, 2012               [Page 15]


Internet-Draft           AFS-3 Directory Object               April 2012


Appendix B.  C Implementation of Directory Hash Function

   #define NHASHENT 128

   unsigned int
   dir_name_hash(const char * name)
   {
       unsigned int hash = 0;

       while(*name++) {
           hash *= 173;
           hash += *name;
       }

       if (hash & 0x80000000) {
           return NHASHENT - (hash & (NHASHENT-1));
       } else {
           return hash & (NHASHENT-1);
       }
   }

                                 Figure 1


Author's Address

   Thomas Keiser
   Sine Nomine Associates
   43596 Blacksmith Square
   Ashburn, VA  20147
   USA

   Phone: +1 703 723 6673
   Email: tkeiser@sinenomine.net

















Keiser                  Expires October 25, 2012               [Page 16]


Html markup produced by rfcmarkup 1.127, available from https://tools.ietf.org/tools/rfcmarkup/