idnits 2.17.1 draft-keiser-afs3-directory-object-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (April 23, 2012) is 4386 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group T. Keiser 3 Internet-Draft Sine Nomine 4 Intended status: Informational April 23, 2012 5 Expires: October 25, 2012 7 AFS-3 Directory Object Type Definition 8 draft-keiser-afs3-directory-object-00 10 Abstract 12 Directory lookups in the AFS-3 distributed file system are supported 13 by defining a canonical encoding for a directory object, and 14 transmitting all--or part--of that object from a file server to its 15 clients so that clients may resolve paths into AFS file IDs (FIDs). 16 This memo describes the AFS-3 directory object wire encoding. 18 Internet Draft Comments 20 Comments regarding this draft are solicited. Please include the 21 AFS-3 protocol standardization mailing list 22 (afs3-standardization@openafs.org) as a recipient of any comments. 24 Status of this Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at http://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on October 25, 2012. 41 Copyright Notice 43 Copyright (c) 2012 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (http://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 59 1.1. Abbreviations . . . . . . . . . . . . . . . . . . . . . . 3 60 2. Conventions . . . . . . . . . . . . . . . . . . . . . . . . . 4 61 3. Constants . . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 4. Directory Object Structure . . . . . . . . . . . . . . . . . . 5 63 5. Page Structure . . . . . . . . . . . . . . . . . . . . . . . . 5 64 5.1. Record Index . . . . . . . . . . . . . . . . . . . . . . . 6 65 5.2. Page header . . . . . . . . . . . . . . . . . . . . . . . 6 66 5.2.1. Allocation Bitmap . . . . . . . . . . . . . . . . . . 7 67 6. Page N=0 structure . . . . . . . . . . . . . . . . . . . . . . 8 68 6.1. Directory Header . . . . . . . . . . . . . . . . . . . . . 9 69 7. Page N>0 structure . . . . . . . . . . . . . . . . . . . . . . 10 70 8. Directory Entry . . . . . . . . . . . . . . . . . . . . . . . 10 71 8.1. Directory Entry Record . . . . . . . . . . . . . . . . . . 11 72 8.2. Directory Entry Extension Record . . . . . . . . . . . . . 12 73 9. Name Hash Function . . . . . . . . . . . . . . . . . . . . . . 13 74 10. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 13 75 11. AFS Assign Numbers Registrar Considerations . . . . . . . . . 13 76 12. Security Considerations . . . . . . . . . . . . . . . . . . . 13 77 13. References . . . . . . . . . . . . . . . . . . . . . . . . . . 14 78 13.1. Normative References . . . . . . . . . . . . . . . . . . . 14 79 13.2. Informative References . . . . . . . . . . . . . . . . . . 14 80 Appendix A. Example Directory Object . . . . . . . . . . . . . . 14 81 A.1. 18-character name string . . . . . . . . . . . . . . . . . 15 82 Appendix B. C Implementation of Directory Hash Function . . . . . 16 83 Author's Address . . . . . . . . . . . . . . . . . . . . . . . . . 16 85 1. Introduction 87 AFS-3 [AFS1] [AFS2] is a distributed file system that has its origins 88 in the VICE project [CMU-ITC-84-020] [VICE1] at the Carnegie Mellon 89 University Information Technology Center [CMU-ITC-83-025], a joint 90 venture between CMU and IBM. VICE later became AFS when CMU moved 91 development to a new commercial venture called Transarc Corporation, 92 which later became IBM Pittsburgh Labs. AFS-3 is a suite of un- 93 standardized network protocols based on a remote procedure call (RPC) 94 suite known as Rx [AFS3-RX]. While de jure standards for AFS-3 fail 95 to exist, the various AFS-3 implementations have agreed upon certain 96 de facto standards, largely helped by the existence of an open source 97 fork called OpenAFS that has served the role of reference 98 implementation. In addition to using OpenAFS as a reference, IBM 99 wrote and donated developer documentation that contains somewhat 100 outdated specifications for the Rx protocol and all AFS-3 remote 101 procedure calls, as well as a detailed description of the AFS-3 102 system architecture. 104 Unlike most classical network file systems, AFS-3 explicitly eschews 105 remote procedure calls to facilitate file server-assisted directory 106 lookup operations. This was a conscious decision meant to limit 107 server load by placing lookup operations on the clients. In the 108 common cases, where there is significant locality of reference to 109 directory entries, this results in a substantial reduction in server 110 load (especially given the AFS-3 cache coherence model). It should 111 be noted that 23 years of empirical evidence have borne out this 112 decision as useful for many general-purpose workloads, while 113 disadvantageous for certain very specific workloads (e.g., large 114 directory objects with extremely non-uniform directory entry 115 reference distributions--where the server overhead of a lookup rpc 116 would would inconsequential compared to the directory file transfer 117 overhead of the existing model). 119 Due to the distributed nature of AFS-3 directory objects, a canonical 120 directory wire-format is an intrinsic part of the AFS-3 protocol. 121 This memo documents the directory object wire format; a future 122 document will document the lookup and modification algorithms, which 123 by the decentralized nature of AFS-3 directories, must be implemented 124 in the to-be-specified manner. 126 1.1. Abbreviations 128 AFS - Historically, AFS stood for the Andrew File System; AFS no 129 longer stands for anything 131 RPC - Remote Procedure Call 133 Rx - The Remote Procedure Call mechanism utilized by AFS-3 135 XDR - eXternal Data Representation 137 2. Conventions 139 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 140 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 141 document are to be interpreted as described in RFC 2119 [RFC2119]. 143 3. Constants 145 AFS_PAGESIZE = 2048 147 the size of each page in an AFS-3 directory object (in octets) 149 MAXPAGES = 128 151 the maximum number of pages in a legacy directory object 153 BIGMAXPAGES = 1023 155 the maximum number of pages in a new (circa 1988) directory 156 object 158 NHASHENT = 128 160 number of hash buckets in the entry name hash table 162 RECSIZE = 32 164 number of octets in a record 166 LRECSIZE = 5 168 base-2 logarithm of RECSIZE 170 EPP = 64 172 number of records per page 174 LEPP = 6 176 base-2 logarithm of EPP 178 DHE = 12 180 number of records taken up in page 0 by the directory header 182 4. Directory Object Structure 184 An AFS-3 directory object consists of between 1 and BIGMAXPAGES 185 (1023) "pages" of length AFS_PAGESIZE (2048 octet). 187 (MSB) (LSB) 188 0 1 2 3 189 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 190 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 191 | page #0000 | 192 ~ (2048 octets) ~ 193 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 194 ~ ... ~ 195 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 196 | page #1022 | 197 ~ (2048 octets) ~ 198 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 200 Directory Structure 202 5. Page Structure 204 All pages in a directory object are AFS_PAGESIZE (2048 octets) in 205 length. All pages are subdivided into EPP (64) records, each RECSIZE 206 (32 octets) in length. 208 (MSB) (LSB) 209 0 1 2 3 210 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 211 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 212 | record #00 | 213 ~ (32 octets) ~ 214 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 215 ~ ... ~ 216 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 217 | record #63 | 218 ~ (32 octets) ~ 219 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 221 Page Structure 223 5.1. Record Index 225 Each record within a directory object is referenced by an index 226 number. This number represents the offset from the start of the 227 file, in units of records, i.e., in multiples of RECSIZE. A record 228 index of 0 would thus point to record 0 in page 0, and a record index 229 of 67 would point to record 3 in page 1. Computing the file offset 230 from an index is simply a matter of left logical shifting the index 231 value by LRECSIZE (5) bits. Conversely, computing the index from a 232 file offset merely involves a right logical shift by LRECSIZE (5) 233 bits. 235 5.2. Page header 237 Each 2048-octet page within an AFS-3 directory object contains a 32- 238 octet (RECSIZE) header at offset 0 in the following form: 240 (MSB) (LSB) 241 0 1 2 3 242 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 243 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 244 | pgcount | tag | 245 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 246 | reserved | | 247 +-+-+-+-+-+-+-+-+ + 248 | allocation bitmap | 249 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 250 | | | 251 +-+-+-+-+-+-+-+-+ + 252 | reserved | 253 ~ (19 octets) ~ 254 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 256 Directory Page Header 258 pgcount: 16 bits (unsigned integer) 260 This field only holds meaning for page 0. For the modern (post- 261 1988) directory format, this field holds the count of valid 262 directory pages (in network byte order) within the directory 263 object. When this value is zero, it denotes a legacy directory 264 object. Legacy directory objects are considered a deprecated and 265 historical vestige, and thus their format is not described in 266 this memo. 268 tag: 16 bits (unsigned integer) 270 This field MUST contain the magic value 1234 in network byte 271 order. 273 allocation bitmap: 8 octets (bit string) 275 The allocation bitmap is a bit field which contains one bit per 276 record slot within the page. The bit field is thus 8 (EPP/8) 277 octets in length. A bit value of zero indicates the entry is 278 free; a value of 1 indicates the entry has been allocated. The 279 allocation bitmap will be discussed further in Section 5.2.1. 281 5.2.1. Allocation Bitmap 283 The allocation bitmap contains one bit per record. The least 284 significant bit of the first octet within the bitmap references the 285 page header object (which is stored at offset 0). The second least 286 significant bit of the first octet within the bitmap references the 287 record index 1 (offset 32 octets into the page), and so on and so 288 forth...until the most significant bit of the eighth octet of the 289 allocation bitmap references the 64th--and final--record of the page 290 (record 63 at page offset 2016). 292 The following invariants hold: 294 page_entry_offset = page_entry_index << LRECSIZE 296 alloc_bitmap_index = page_entry_index >> 3 298 alloc_bitmap_bit_num = page_entry_index & 0x7 300 alloc_bitmap_bit = 1 << alloc_bitmap_bit_num 302 The variable page_entry_index, which is an unsigned integer between 0 303 and 63, can be derived from the record index (Section 5.1) by bit- 304 wise ANDing it with EPP-1. 306 The equations above are written in C pseudocode--the variables are 307 all assumed to be unsigned integers, and the operators are assumed to 308 be identical to the ANSI C standard. 310 6. Page N=0 structure 312 Page 0 is special due to the directory header. It is structured as 313 follows: 315 1. a page header (see Section 5.2) 317 2. a directory header (see Section 6.1) 319 3. 51 data records (EPP-DHE-1=51) 320 (MSB) (LSB) 321 0 1 2 3 322 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 323 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 324 | page header | 325 ~ (32 octets) ~ 326 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 327 | directory header | 328 ~ (384 octets) ~ 329 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 330 | data record #13 | 331 ~ (32 octets) ~ 332 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 333 ~ ... ~ 334 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 335 | data record #63 | 336 ~ (32 octets) ~ 337 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 339 Directory Page N=0 Structure 341 6.1. Directory Header 343 The directory header structure is a 384-octet structure that is 344 stored at an offset of 32 octets from the beginning of the directory 345 object (i.e., directly following the page 0 page header--see 346 Section 5.2). The directory header layout is as follows: 348 (MSB) (LSB) 349 0 1 2 3 350 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 351 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 352 | page 0 map | page 1 map | page 2 map | page 3 map | 353 ~ ~ 354 | page 124 map | page 125 map | page 126 map | page 127 map | 355 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 356 | hash chain 0 | hash chain 1 | 357 ~ ~ 358 | hash chain 126 | hash chain 127 | 359 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 361 Directory Header 363 page map: 365 Each of the MAXPAGES page map fields corresponds to one of the 366 MAXPAGES pages in a legacy directory object. Each field contains 367 the count of available entries in this directory page. A value 368 of EPP indicates that this page has not yet been allocated (i.e., 369 the page header has not been initialized). 371 hash chain: 373 Each of the NHASHENT hash chain fields contains a record index 374 for the first directory entry name that hashes to this bucket 375 (see Section 5.1, and see Section 9 for a description of the hash 376 function) 378 7. Page N>0 structure 380 Each page N>0 is structured as follows: 382 1. a page header (see Section 5.2) 384 2. EPP-1 (63) data records 386 (MSB) (LSB) 387 0 1 2 3 388 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 389 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 390 | header | 391 ~ (32 octets) ~ 392 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 393 | data record #01 | 394 ~ (32 octets) ~ 395 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 396 ~ ... ~ 397 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 398 | data record #63 | 399 ~ (32 octets) ~ 400 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 402 Directory Page N>0 Structure 404 8. Directory Entry 406 Since entry names are of variable length, directory entries are 407 structured as follows: 409 o a directory entry record (see Section 8.1) 411 o zero or more directory entry extension record(s) (see Section 8.2) 412 This sequence of records MUST be contiguous, and MUST NOT cross a 413 directory page boundary. 415 8.1. Directory Entry Record 417 A directory entry record contains the dirent entry metadata (i.e., 418 the vnode number and uniquifier, the name hash table next pointer, 419 flag bits, and the first twenty octets of the entry name string. Its 420 layout is as follows: 422 (MSB) (LSB) 423 0 1 2 3 424 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 425 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 426 | flags | reserved | next | 427 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 428 | vnode | 429 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 430 | uniquifier | 431 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 432 | name | 433 ~ (20 octets) ~ 434 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 436 Directory Entry Record 438 flags: 8 bits 440 This is an 8-bit wide bit vector. Currently, only one bit is 441 defined: FFIRST (0x1). This flag bit is asserted in every record 442 of this type. There are vestiges in the OpenAFS implementation 443 suggesting that the original intention was to have a second flag 444 bit FNEXT (0x2)--being asserted in the first octet of extension 445 records--which would allow parsers to distinguish between entry 446 records and extension records. However, this idea was never 447 implemented (in fact, the concept of a flags field in an 448 extension record does not exist), and thus this flag bit has no 449 meaning. It should be noted that some tools have attempted to 450 use this bit to distinguish between entry records and entry 451 extension records (under the assumption that 0x1 is not a valid 452 ASCII value for a file name string). This technique is obviously 453 error-prone, and thus SHOULD NOT be relied upon. 455 next: 16 bits (unsigned integer) 457 This field contains a record index (see Section 5.1) pointing to 458 the next directory entry record on this name hash chain. A value 459 of zero indicates this is the last record on this chain. This 460 entry MUST point to a record index which contains a data record 461 of the directory entry type (see Section 8). 463 vnode: 32 bits (unsigned integer) 465 This field contains the target vnode number for this directory 466 entry. Together with the uniquifier field, this forms the 467 equivalent of an inode number in the directory entry of a typical 468 on-disk Unix file system. 470 uniquifier: 32 bits (unsigned integer) 472 This field contains the target uniquifier for this directory 473 entry. Together with the vnode field, this forms the equivalent 474 of an inode number in the directory entry of a typical on-disk 475 Unix file system. 477 name: 20 octets (null-terminated string) 479 The first 20 octets of the directory entry's name string are 480 contained in this field. If the name string (including null 481 terminator) exceeds 20 octets, then this string will continue in 482 a sequence of one or more directory entry extension records (see 483 Section 8.2) that MUST directly proceed this record. 485 8.2. Directory Entry Extension Record 487 When a file name string exceeds the 20 octets set aside in an entry 488 record, one or more extension records MUST be allocated contiguously 489 following the base entry record in order to contain the rest of the 490 name string. The layout of an extension record is as follows: 492 (MSB) (LSB) 493 0 1 2 3 494 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 495 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 496 | name | 497 ~ (32 octets) ~ 498 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 500 Directory Entry Extension Record 502 name: 32 octets (string) 504 This field contains part of an extended directory entry name 505 string. If this is the last directory entry extension record, 506 then this field MUST contain a null terminator character (octet 507 value zero) within its 32 octets. 509 9. Name Hash Function 511 The hash function is a loop over each of the octets within the name 512 string. The hash is computed using integer arithmetic on an unsigned 513 32-bit integer. The hash MUST be initialized to zero before 514 commencing iteration over the characters in the name string. For 515 each character, the hash value is multiplied by the constant 173, and 516 then the value of the current character is added to the hash. When 517 the null terminator is encountered, the loop is terminated before the 518 hash is multiplied by 173. 520 For reasons unknown to the author, the resultant unsigned hash value 521 is then compared against the value 2^31. If the hash value is less 522 than 2^31 (i.e., what would be the sign bit--if the hash value were 523 signed-- is not asserted), then the resultant hash value will be the 524 value computed in the above loop bitwise ANDed with the constant 525 NHASHENT-1 (127). However, if the hash value is greater than or 526 equal to 2^31, then the resultant hash value will first be bitwise 527 anded with the constant NHASHENT-1 (127), and then the value will be 528 subtracted from the constant NHASHENT (128) to yield the final hash 529 value. 531 10. IANA Considerations 533 This memo includes no request to IANA. 535 11. AFS Assign Numbers Registrar Considerations 537 This memo includes no request to the AFS Assigned Numbers Registrar. 539 12. Security Considerations 541 Directory metadata can contain sensistive information. This memo 542 merely specifies the wire format encoding. Any implementation which 543 may be utilized to store and retrieve directories containing entries 544 whose name strings might reveal sensitive information should take 545 precautions to ensure that they are never transmitted in the clear, 546 and should take steps to ensure that those entries are not cached on 547 machines lacking appropriate physical and network security. 549 13. References 550 13.1. Normative References 552 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 553 Requirement Levels", BCP 14, RFC 2119, March 1997. 555 13.2. Informative References 557 [AFS1] Howard, J., "An Overview of the Andrew File System"", 558 Proc. 1988 USENIX Winter Tech. Conf. pp. 23-26, 559 February 1988. 561 [AFS2] Howard, J., Kazar, M., Menees, S., Nichols, D., 562 Satyanarayanan, M., Sidebotham, R., and M. West, "Scale 563 and Performance in a Distributed File System", ACM Trans. 564 Comp. Sys. Vol. 6, No. 1, pp. 51-81, February 1988. 566 [AFS3-RX] Zayas, E., "AFS-3 Programmer's Reference: Specification 567 for the Rx Remote Procedure Call Facility", Transarc Corp. 568 Tech. Rep. FS-00-D164, August 1991. 570 [CMU-ITC-83-025] 571 Morris, J., Van Houweling, D., and K. Slack, "The 572 Information Technology Center", CMU ITC Tech. Rep. CMU- 573 ITC-83-025, 1983. 575 [CMU-ITC-84-020] 576 West, M., "VICE File System Services", CMU ITC Tech. 577 Rep. CMU-ITC-84-020, August 1984. 579 [VICE1] Satyanarayanan, M., Howard, J., Nichols, D., Sidebotham, 580 R., Spector, A., and M. West, "The ITC Distributed File 581 System: Principles and Design", Proc. 10th ACM Symp. 582 Operating Sys. Princ. Vol. 19, No. 5, December 1985. 584 Appendix A. Example Directory Object 585 A.1. 18-character name string 587 (MSB) (LSB) 588 0 1 2 3 589 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 590 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 591 | pgcount=1 | tag=1234 | 592 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 593 | reserved |1| 0xfff |1 1| | 594 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 595 | 0... | 596 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 597 | | | 598 +-+-+-+-+-+-+-+-+ + 599 | reserved | 600 ~ (19 octets) ~ 601 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 602 | map[0]=49 | | 603 +-+-+-+-+-+-+-+-+ + 604 | map[1...127]=0x40 0x40 0x40 ... | 605 ~ (127 octets) ~ 606 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 607 | hash[0...127]=0x0000 0x0000 ... | 608 ~ (256 octets) ~ 609 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 610 | flags=0x1 | reserved | next=0x0000 | 611 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 612 | vnode | 613 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 614 | uniquifier | 615 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 616 | name="iamexactly018chars" | 617 ~ (18 octets) ~ 618 + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 619 | | nul | ? | 620 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 621 | allocated extent record full of garbage | 622 ~ (32 octets) ~ 623 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 624 | unallocated garbage | 625 ~ (1568 octets) ~ 626 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 628 18-Character Name String 630 Appendix B. C Implementation of Directory Hash Function 632 #define NHASHENT 128 634 unsigned int 635 dir_name_hash(const char * name) 636 { 637 unsigned int hash = 0; 639 while(*name++) { 640 hash *= 173; 641 hash += *name; 642 } 644 if (hash & 0x80000000) { 645 return NHASHENT - (hash & (NHASHENT-1)); 646 } else { 647 return hash & (NHASHENT-1); 648 } 649 } 651 Figure 1 653 Author's Address 655 Thomas Keiser 656 Sine Nomine Associates 657 43596 Blacksmith Square 658 Ashburn, VA 20147 659 USA 661 Phone: +1 703 723 6673 662 Email: tkeiser@sinenomine.net