doc/txt/prdb.txt

   1 This document describes the file format of the protection database file.
   2
   3 The actual prdb.DB0 file on disk begins with a ubik header, which is not
   4 exposed to the callers of ubik_ RPCs.  64 octets are reserved for this header,
   5 though only 16 are used.  The first 16 octets contain the representation
   6 of a struct ubik_hdr, with all fields in network byte order:
   7
   8        0                   1                   2                   3
   9        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
  10       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  11       |                           ubik_magic                          |
  12       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  13       |            padding            |          header_size          |
  14       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  15       |                             epoch                             |
  16       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  17       |                            counter                            |
  18       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  19       |                            [unused]                           |
  20       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  21       |                            [unused]                           |
  22       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  23       |                            [unused]                           |
  24       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  25       |                            [unused]                           |
  26       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  27       |                            [unused]                           |
  28       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  29       |                            [unused]                           |
  30       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  31       |                            [unused]                           |
  32       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  33       |                            [unused]                           |
  34       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  35       |                            [unused]                           |
  36       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  37       |                            [unused]                           |
  38       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  39       |                            [unused]                           |
  40       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  41       |                            [unused]                           |
  42       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  43        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
  44        0                   1                   2                   3
  45
  46 ubik_magic is a global constant, 0x00354545.
  47
  48 padding is an unused field and should always be zeros.
  49
  50 header_size is the length of the reserved space for the ubik header,
  51 and will always be 0x64.
  52
  53 epoch is the ubik epoch.
  54
  55 counter is the ubik counter for transactions and updates.
  56
  57 The unused space should always be zeros.
  58
  59 The ubik header is not exposed through the PR_ RPC package, and as such
  60 is not considered to be part of the logical prdb database.  Subsequent
  61 discussion will refer to addresses and offsets; these addresses are logical
  62 addresses within the prdb, and do not include the size of the ubik header.
  63 When using logical addresses to index into the file on disk, the size of
  64 the ubik header must be added to the offset used.
  65
  66
  67 Immediately following the ubik header on disk (so, at the beginning of the
  68 logical prdb) is the prdb header, which consumes 65600 octets.
  69 The majority of this space is for two hash tables, enabling
  70 quick lookups of prdb entries by name and by id.  All fields with integer
  71 values are stored in network byte order.
  72
  73 The prdb header structure is:
  74
  75         0                   1                   2                   3
  76         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
  77 octets +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  78      0 |                            version                            |
  79        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  80        |                          headerSize                           |
  81        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  82        |                            freePtr                            |
  83        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  84        |                            eofPtr                             |
  85        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  86        |                           maxGroup                            |
  87        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  88        |                             maxID                             |
  89        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  90        |                           maxForeign                          |
  91        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  92        |                            maxInst                            |
  93        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  94     32 |                            orphan                             |
  95        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  96        |                           usercount                           |
  97        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  98        |                          groupcount                           |
  99        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 100        |                         foreigncount                          |
 101        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 102        |                           instcount                           |
 103        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 104        |                          [reserved]                           |
 105        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 106        |                          [reserved]                           |
 107        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 108        |                          [reserved]                           |
 109        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 110     64 |                          [reserved]                           |
 111        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 112        |                          [reserved]                           |
 113        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 114         0                   1                   2                   3
 115         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
 116        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 117     72 |                           nameHash                            |
 118        |                                                               |
 119        ~                              ...                              ~
 120  32832 |                                                               |
 121        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 122  32836 |                            idHash                             |
 123        |                                                               |
 124        ~                              ...                              ~
 125  65596 |                                                               |
 126        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 127         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
 128         0                   1                   2                   3
 129
 130 version is the PR database version number.  Only version number 0 is
 131 presently in use.
 132
 133 headerSize is the size in octets of the prdb header (currently 0x10040).
 134
 135 freePtr is the logical index (in octets) of the first unused prentry in the
 136 prdb (that is, the first logical hole in the database file).  If the database
 137 file is densely packed, this field is zero.  This index is not the actual
 138 index into the prdb.DB0 file on disk, because logical indices within the
 139 prdb do not account for the 64-octet space reserved for the ubik header.
 140
 141 eofPtr is the index (in octets) of the end of the database file.  When a new
 142 entry is created that extends the database file, it will be created at this
 143 logical index.  (Again, this logical index excludes the 64-octet ubik header.)
 144
 145 maxGroup is the most negative group ID allocated, stored as a 32-bit
 146 twos-complement signed integer.
 147
 148 maxId is the largest user ID allocated to a local-realm user.
 149
 150 maxForeign is the largest user ID allocated to a foreign-realm user.
 151
 152 maxInst is reserved for a feature which is not yet implemented.
 153
 154 orphan is the pointer to the head of the list of "orphaned" prdb entries.
 155 Entries are orphaned when their owner gets deleted; at that time, they are
 156 added to the head of the orphan list.
 157
 158 usercount is the number of user entries in the prdb.
 159
 160 groupcount is the number of group entries in the prdb, including mandatory
 161 groups such as system:backup, system:administrators, system:ptsviewers,
 162 system:authuser, and system:anyuser.
 163
 164 foreigncount is the number of foreign users that have registered with the
 165 prdb.
 166
 167 instcount is reserved for a feature which is not yet implemented.
 168
 169 Five 32-bit fields are reserved for future expansion.
 170
 171 The nameHash and idHash fields each contain 8191 entries; each entry is 32 bits,
 172 so the space consumed by each hash table is 32764 octets.
 173
 174 The NameHash hash function is targetted for ASCII text.  Each octet is
 175 treated as an unsigned integer from which 31 (decimal) is subtracted
 176 (corresponding to the 7-bit control characters), and the resulting stream
 177 of integers is used as the coefficients of a power series with base 31 (also
 178 decimal), with the least significant coefficient appearing first.
 179 For example, if a name string was the (highly unlikely and nigh-unusable)
 180 stream of octets (in hex):
 181 21 22 23 24
 182 Then the power series used in the hash function calculation would be
 183 (all numbers in decimal):
 184 2 + 3 * 31 + 4 * 31**2 + 5 * 31**3
 185 The value of this power series is stored in an unsigned 32-bit integer,
 186 and as such is implicitly computed modulo 2**32.  The remainder modulo
 187 8191 (the size of the hash table) of this 32-bit value is used as the
 188 index into the hash table for this name entry.
 189 (This hash function can be easily implemented iteratively.)
 190
 191 The IdHash hash function is very simple; it is just the remainder modulo
 192 8191 (the size of the hash table) of the absolute value of the user or
 193 group id.  Note that a group id of INT_MIN would cause undefined behavior
 194 in the evaluation of this hash function, and is given the name PRBADID
 195 and used as a sentinel.
 196
 197 Hash collisions are treated in the standard way of having a linked list
 198 of entries with the same hash.  The hash table itself holds the id of the
 199 entry which is the head of the list, and the nextName and nextID fields
 200 of each entry chain the lists for the respective hash tables.
 201
 202
 203 prdb entries follow immediately after the prdb header.  Each entry is
 204 192 octets in size, and may represent either a user or a group or (if
 205 enabled) a supergroup entry, or a continuation entry.
 206
 207 User and group entries use the same format for the data structure (user
 208 ids are positive and group ids are negative, and their structures parallel
 209 each other), and continuation entries are used when a user belongs to more
 210 than PRSIZE (10) groups or a group has more than PRSIZE users in it.
 211 supergroup entries share many fields with the user/group entries, but
 212 the binary format is slightly different.  In all cases, integer fields
 213 are represented in network byte order.
 214
 215 All entries have a flags field in the second 16 bits which is used to indicate
 216 what type the entry is -- PRFREE, PRGRP, PRCONT, PRCELL, PRFOREIGN, or PRINST
 217 (not used).  The other fields which are invariant in the block structure
 218 (i.e., present in all types of entry) are id, cellid, and next.  At present
 219 there is also a reserved field in all entry types at a fixed offset; this
 220 field can be used for future extensions.  Another invariant is that each
 221 block (outside the header) is pointed to from some other location.  Continuation
 222 blocks are pointed to from the 'next' field of the previous block, and
 223 user/group entries are locatable from the name and id hash tables, either
 224 directly from the header or through a nextName/nextID pointer.  The head
 225 of the free list is in the prdb header directly.
 226
 227 The layout of the invariant fields is:
 228
 229         0                   1                   2                   3
 230         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
 231 octets +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 232      0 |       [entry-specific]        |          type_flags           |
 233        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 234        |                              id                               |
 235        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 236        |                            cellid                             |
 237        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 238        |                             next                              |
 239        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 240     16 |                       [entry-specific]                        |
 241        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 242        |                       [entry-specific]                        |
 243        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 244        |                       [entry-specific]                        |
 245        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 246        |                       [entry-specific]                        |
 247        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 248     32 |                           reserved                            |
 249        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 250
 251 type_flags specifies the type of this prdb entry:
 252 0x1     PRFREE    -- the entry is on the free list
 253 0x2     PRGRP     -- the entry is a group entry
 254 0x4     PRCONT    -- the entry is a continuation block
 255 0x8     PRCELL    -- the entry is a cell entry
 256 0x10    PRFOREIGN -- the entry is for a foreign user
 257 0x20    PRINST    -- the entry is a sub/super instance
 258 0x3f    PRTYPE    -- bitmask for "type" bits
 259 Other bits are allocated for status flags on the entry:
 260 0x40    PRACCESS  -- access checking is enabled
 261 0x80    PRQUOTA   -- group creation quota checking is enabled
 262 Note that this document specifies the on-disk data format, which is in
 263 network byte order. Because the fundamental quantum of ubik accesses is
 264 a 32-bit word, byte swaps between host and network byte order are done
 265 on 32-bit words, so the in-memory representation may place the bits
 266 holding type_flags in the other half of the word.
 267
 268 id is the ID number of the user or group, or the user/group to which
 269 an continuation or other extension entry belongs.  User entries are positive
 270 and group entries are negative.
 271
 272 cellid is only used for foreign user entries (not foreign groups).
 273 Group entries are allocated for system:authuser@remotecell with
 274 a (negative 32-bit) group id of a particular substructure.  Foreign
 275 user entries have their cellid field set to the id of the
 276 system:authuser@remotecell group corresponding to the remotecell of the
 277 foreign user.  (Additionally, foreign user entries are allocated pts ids
 278 with a particular substructure.)
 279 There is no particularly good reason for the cellid field to remain an
 280 invariant in future extensions.
 281
 282 next is a pointer to the next entry in a chain of related data for this
 283 entry, e.g. a continuation block.  For type PRFREE entries, it is a pointer
 284 to the next block on the free list.
 285
 286
 287 The layout of a user or group entry (struct prentry) is:
 288
 289         0                   1                   2                   3
 290         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
 291 octets +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 292      0 |           prp_flags           |          type_flags           |
 293        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 294        |                              id                               |
 295        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 296        |                            cellid                             |
 297        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 298        |                             next                              |
 299        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 300     16 |                          createTime                           |
 301        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 302        |                            addTime                            |
 303        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 304        |                          removeTime                           |
 305        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 306        |                          changeTime                           |
 307        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 308     32 |                           reserved0                           |
 309        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 310        |                           entries[0]                          |
 311        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 312        |                           entries[1]                          |
 313        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 314        |                           entries[2]                          |
 315        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 316     48 |                           entries[3]                          |
 317        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 318        |                           entries[4]                          |
 319        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 320        |                           entries[5]                          |
 321        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 322        |                           entries[6]                          |
 323        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 324     64 |                           entries[7]                          |
 325        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 326        |                           entries[8]                          |
 327        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 328        |                           entries[9]                          |
 329        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 330         0                   1                   2                   3
 331         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
 332        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 333        |                             nextID                            |
 334        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 335     80 |                            nextName                           |
 336        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 337        |                             owner                             |
 338        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 339        |                            creator                            |
 340        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 341        |                            ngroups                            |
 342        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 343     96 |                             nusers                            |
 344        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 345        |                             count                             |
 346        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 347        |                            instance                           |
 348        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 349        |                             owned                             |
 350        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 351    112 |                           nextOwned                           |
 352        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 353        |                            parent                             |
 354        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 355        |                            sibling                            |
 356        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 357        |                             child                             |
 358        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 359    128 |                             name                              |
 360        +                                                               +
 361        |                                                               |
 362        +                                                               +
 363        |                                                               |
 364        +                                                               +
 365        |                                                               |
 366        +                                                               +
 367    144 |                                                               |
 368        +                                                               +
 369        |                                                               |
 370        +                                                               +
 371        |                                                               |
 372        +                                                               +
 373        |                                                               |
 374        +                                                               +
 375    160 |                                                               |
 376        +                                                               +
 377        |                                                               |
 378        +                                                               +
 379        |                                                               |
 380        +                                                               +
 381        |                                                               |
 382        +                                                               +
 383    176 |                                                               |
 384        +                                                               +
 385        |                                                               |
 386        +                                                               +
 387        |                                                               |
 388        +                                                               +
 389    188 |                                                               |
 390        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 391         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
 392         0                   1                   2                   3
 393
 394 prp_flags and type_flags are consolidated into a single "flags" field for
 395 API purposes.
 396 prp_flags hold the access bits for entries, e.g., PRP_STATUS_ANY
 397 and PRP_ADD_MEM.
 398 Because prp_flags and type_flags are consolidated
 399 into a single 'flags' field for the API, the in-memory layout will have
 400 prp_flags and type_flags swapped on little-endian machines.
 401
 402 [id and cellid are per the entry-invariant fields]
 403
 404 next is a pointer to the next continuation block for this entry, or (for
 405 type PRFREE entries) a pointer to the next block on the free list.
 406
 407 createTime holds the time at which this entry was created, in seconds from
 408 the Unix epoch.
 409
 410 addTime is the most recent time at which an entry was added to this
 411 usr/group's membership list, in seconds since the Unix epoch.
 412
 413 removeTime is the most recent time at which an entry was removed from this
 414 user/group's membership list, in seconds since the Unix epoch.
 415
 416 changeTime is the most recent time at which the entry was changed with
 417 a PR_ChangeEntry RPC (that is, renamed or renumbered or had owner
 418 or name change).  Changing the access flags does not update this time.
 419
 420 reserved[0] is reserved for future use.
 421
 422 entries[0-9] hold the first ten elements of this entry's membership list
 423 (the users in this group, or the groups of which this user is a member).
 424 They are populated in increasing order; when fewer than ten elements are
 425 present, the unused fields are zero or PRBADID.  Additional elements of the
 426 membership list are stored in continuation block(s).
 427
 428 nextID is a pointer for the hash table chain in the header's idHash hash
 429 table.  All prdb entries whose id hashes to the same value are stored in
 430 a singly-linked list; this field effects the linkage of that list.
 431
 432 nextName is similar to nextID, but for the nameHash hash table instead of
 433 the idHash hash table.
 434
 435 owner is the id of the the prdb entry which owns this entry.
 436
 437 creator is the id of the prdb entry which created this entry.
 438
 439 ngroups is the number of groups this entry is still allowed to create
 440 (it is the quota minus the number of groups which have been created).
 441 For regular group entries, this field is always zero.
 442 For foreign group entries, this is the number of (foreign) users who are
 443 members of that group.
 444
 445 nusers is nominally the foreign user registration quota for a user entry,
 446 that is, the number of foreign user entries this user is still allowed to
 447 create.  However, this quota value is never actually used -- the presence of
 448 nusers for user entries was intended to support a feature which has not been
 449 implemented.
 450 For regular group entries, it is always zero.
 451 For foreign group entries (i.e., system:authuser@remotecell), nusers is the
 452 number of foreign user entries which are members of the group.
 453 (It is used when allocating user ids for new foreign users from that cell.)
 454
 455 count is the cardinality of this entry's membership list.  That is, for user
 456 entries, the number of groups of which this user is a member; for group entries,
 457 the number of users in the group.
 458
 459 instances is reserved for a feature which is not yet implemented.
 460
 461 owned is the head of the linked list of entries owned by this entry.
 462 Both users and groups may own group entries (user entries always display
 463 as being owned by system:administrators though the numerical value of this
 464 field is zero).  The nextOwned field of the group entries chains this list.
 465
 466 nextOwned is the pointer to the next entry in the list of groups owned
 467 by a the owner of this group.
 468 For user entries, this field is always zero.
 469
 470 parent is reserved for a feature which is not yet implemented.
 471
 472 sibling is reserved for a feature which is not yet implemented.
 473
 474 child is reserved for a feature which is not yet implemented.
 475
 476 name holds the name of this entry.  For users, it is the krb4 name;
 477 for groups, is is an ASCII string.  The name is NUL-terminated, making the
 478 maximum permissible length of a name 63 characters.  Unused portions of this
 479 field should be zeroed.
 480
 481
 482 Supergroup entries are quite similar to regular user/group entries, differing
 483 only at the 'instance', 'parent', 'sibling', and 'child' fields,
 484 which are replace by 'countsg', 'nextsg', 'supergroup[0]', and
 485 'supergroup[1]', respectively.  Putting the byte offsets in, those fields
 486 are:
 487
 488         0                   1                   2                   3
 489         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
 490 octets +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 491    104 |                            countsg                            |
 492        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 493        |                             owned                             |
 494        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 495    112 |                           nextOwned                           |
 496        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 497        |                            nextsg                             |
 498        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 499        |                         supergroup[0]                         |
 500        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 501        |                         supergroup[1]                         |
 502        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 503    128 |                             name                              |
 504        ~                                                               ~
 505    188 |                                                               |
 506        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 507         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
 508         0                   1                   2                   3
 509
 510 countsg is the number of groups of which this group is a member, akin to
 511 the 'count' field of a user entry.
 512
 513 nextsg is a pointer to a chain of continuation blocks holding additional
 514 supergroup entries for this group.  That is, the 'entries' elements of the
 515 continuation blocks will be groups of which this group is a member, akin
 516 to supergroup[0-1].  This chain is extended using the 'next' pointer of
 517 the contentry structure, if necessary.
 518
 519 supergroup[0-1] are the first two groups of which this group is a member.
 520 These supergroup elements are used in increasing order, and unused elements
 521 should be zero (but PRBADID is also okay).
 522
 523
 524 Continuation entries have a simpler structure, retaining a few key fields
 525 that are shared amongst all types of entry but leaving a large contiguous
 526 block of space to be used as an array of ids.  Again, all integer
 527 fields are stored in network byte order.  The format is:
 528
 529         0                   1                   2                   3
 530         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
 531 octets +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 532      0 |             unused            |          type_flags           |
 533        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 534        |                              id                               |
 535        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 536        |                            cellid                             |
 537        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 538        |                             next                              |
 539        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 540     16 |                          reserved[0]                          |
 541        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 542        |                          reserved[1]                          |
 543        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 544        |                          reserved[2]                          |
 545        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 546        |                          reserved[3]                          |
 547        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 548     32 |                          reserved[4]                          |
 549        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 550        |                           entries[0]                          |
 551        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 552        |                           entries[1]                          |
 553        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 554        |                           entries[2]                          |
 555        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 556     48 |                           entries[3]                          |
 557        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 558        ~                              ...                              ~
 559        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 560    188 |                          entries[38]                          |
 561        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 562         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
 563         0                   1                   2                   3
 564
 565 the type_flags field is again exposed via the API as a 32-bit 'flags' field,
 566 but only the low 16 bits are used for flags by continuation entries.
 567
 568 id and cellid are retained as a consistency check for the entry -- these
 569 fields should be identical amongst the main entry and all continuation
 570 blocks chained to it.
 571
 572 The four Time fields present in the user/group entries are not needed for
 573 continuation entries, but are left as reserved so as to make the space
 574 used for holding ids a contiguous array.
 575
 576 Each continuation block can hold up to 39 additional prdb ids associated
 577 with the original user or group entry, extending the original 10 entries
 578 available in the main entry block (for user/group membership) or the
 579 original 2 entries available in the main group block (for supergroup
 580 membership).