sys/fs/efs/efs_dir.h

   1 /*      $NetBSD$        */
   2
   3 /*
   4  * Copyright (c) 2006 Stephen M. Rumble <rumble@ephemeral.org>
   5  *
   6  * Permission to use, copy, modify, and distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 /*
  20  * EFS directory block and directory entry formats.
  21  *
  22  * See IRIX dir(4)
  23  */
  24
  25 #ifndef _FS_EFS_EFS_DIR_H_
  26 #define _FS_EFS_EFS_DIR_H_
  27
  28 /*
  29  * EFS directory block (512 bytes on disk)
  30  */
  31
  32 #define EFS_DIRBLK_MAGIC        0xbeef
  33 #define EFS_DIRBLK_SIZE         EFS_BB_SIZE
  34 #define EFS_DIRBLK_HEADER_SIZE  4
  35 #define EFS_DIRBLK_SPACE_SIZE   (EFS_DIRBLK_SIZE - EFS_DIRBLK_HEADER_SIZE)
  36
  37 struct efs_dirblk {
  38         uint16_t        db_magic;       /* must be EFS_DIRBLK_MAGIC */
  39         uint8_t         db_firstused;   /* first dir entry offset (compacted) */
  40         uint8_t         db_slots;       /* total number of entry offsets */
  41
  42         /*
  43          * The following db_space is used for three things:
  44          *  1) Array of entry offsets, one byte each, relative to the
  45          *     efs_dirblk structure (not db_space!). These are stored right
  46          *     shifted by one, thus providing 9 bits to address the entries.
  47          *  2) Array of even-sized directory entries, which exist at even
  48          *     offsets, of course.
  49          *  3) Free space between the two arrays used for expanding either.
  50          *
  51          * The entry offsets exist in the lower offset range of de_space,
  52          * followed by efs_dirent structures higher up:
  53          *
  54          *  db_space[sizeof(db_space)]  _______________________  _
  55          *                             |                       |  |
  56          *                             |  efs_dirent at z << 1 |  |
  57          *                             |_______________________|  |
  58          *                             |                       |  |
  59          *                             |  efs_dirent at x << 1 |  |-- directory
  60          *                             |                       |  |    entries
  61          *                             |_______________________|  |
  62          *                             |                       |  |
  63          *                             |  efs_dirent at y << 1 |  |
  64          * db_space[db_firstused << 1] |_______________________| _|
  65          *                             |          ...          |
  66          *                             |       free space      |
  67          *                             |          ...          |
  68          *          db_space[db_slots] |_______________________| _
  69          *                             |___________z___________|  |
  70          *                             |___________0___________|  |-- directory
  71          *                             |___________y___________|  |    entry
  72          *                 db_space[0] |___________x___________| _|     offsets
  73          *
  74          * In the above diagram, db_firstused would be equal to y. Note that
  75          * directory entry offsets need not occur in the same order as their
  76          * corresponding entries. The size of the offset array is indicated
  77          * by 'db_slots'. Unused slots in the middle of the array are zeroed.
  78          *
  79          * A range of free space between the end of the offset array and the
  80          * first directory entry is used for allocating new entry offsets and
  81          * directory entries. Its size is equal to ('db_firstused' << 1) -
  82          * 'db_slots'.
  83          *
  84          * When a directory entry is added, the directory offset array is
  85          * searched for a zeroed entry to use. If none is available and space
  86          * permits, it is allocated from the bottom of the free space region
  87          * and 'db_slots' is incremented. The space for the directory entry is
  88          * allocated from the top of free space, and the offset is stored.
  89          *
  90          * When a directory entry is removed, all directory entries below it
  91          * are moved up in order to expand the free space region. If the
  92          * corresponding entry offset borders the free space (it is last in the
  93          * array), it is coalesced into the free space region and 'db_slots' is
  94          * decremented.
  95          *
  96          * XXX when all entries removed, (how) do we free the dirblk?
  97          *
  98          * According to IRIX dir(4), the offset of a directory entry's offset
  99          * within the array of offsets does not change (say what?). That is, if
 100          * directory entry P's offset is contained in db_space[3], it will
 101          * remain in db_space[3] until it is removed. In other words, they do
 102          * not reshuffle the entry offsets in order to coalesce the unused
 103          * offset array entries into the free space region. Since we allocate
 104          * from zeroed ones before dipping into free space, this is typically
 105          * not a problem. However, it leaves open the case where many older
 106          * files are removed, thus leaving a valid array offset at the top,
 107          * which reduces free space and potentially keeps a large directory
 108          * entry from being added. Since there's no technical reason why moving
 109          * them around would violate the format, I'm guessing that IRIX does
 110          * some sort of caching of index offsets within the array. A few quick
 111          * tests seems to indicate that coalescing can be slightly more
 112          * performant. One could also sort array offsets by de_namelen and
 113          * binary search on lookup, but I am not sure how much performance could
 114          * be gained since there are only 72 entries at maximum, far less on
 115          * average, and many unix files have similar length. Quick tests show
 116          * no appreciable difference when using binary search, as one would
 117          * suspect.
 118          */
 119         uint8_t         db_space[EFS_DIRBLK_SPACE_SIZE];
 120 } __packed;
 121
 122 /*
 123  * 'db_slots' (directory entry offset array size) can be no larger
 124  * than (EFS_DIRBLK_SPACE_SIZE / 9), as each efs_dirent struct is
 125  * minimally 6 bytes and requires one 1-byte offset entry.
 126  */
 127 #define EFS_DIRBLK_SLOTS_MAX    (EFS_DIRBLK_SPACE_SIZE / 7)
 128
 129 #define EFS_DIRBLK_SLOT_FREE    (0)     /* free, uncoalesced slots are zeroed */
 130
 131 /*
 132  * Directory entry structure, which resides in efs_dirblk->space. Minimally
 133  * 6 bytes on-disk, maximally 260 bytes.
 134  *
 135  * The allocation within efs_dirblk->space must always be even, so the
 136  * structure is always padded by one byte if the efs_dirent struct is odd. This
 137  * occurs when de_namelen is even. The macros below handle this irregularity. It
 138  * should be noted that despite this, de_namelen will always reflect the true
 139  * length of de_name, which is NOT nul-terminated. Therefore without a priori
 140  * knowledge of this scheme, one cannot accurately calculate the efs_dirent size
 141  * based on the de_namelen field alone, rather EFS_DIRENT_SIZE() must be used.
 142  */
 143 struct efs_dirent {
 144         /* entry's inode number */
 145         union {
 146                 uint32_t l;
 147                 uint16_t s[2];
 148         } de_u;
 149
 150         /*
 151          * de_name is of variable length (1 <= de_namelen <= 255). Note that
 152          * the string is NOT nul-terminated.
 153          */
 154         uint8_t         de_namelen;
 155         char            de_name[1];     /* variably sized */
 156 } __packed;
 157
 158 #define de_inumber      de_u.l
 159
 160 #define EFS_DIRBLK_TO_DIRENT(_d, _o)    (struct efs_dirent *)((char *)(_d) + _o)
 161
 162 /*
 163  * Offsets are stored on-disk right shifted one to squeeze 512 even-byte
 164  * boundary offsets into a uint8_t. Before being compacted, the least
 165  * significant bits of an offset must, of course, be zero.
 166  */
 167 #define EFS_DIRENT_OFF_SHFT             1
 168 #define EFS_DIRENT_OFF_EXPND(_x)        ((_x) << EFS_DIRENT_OFF_SHFT)
 169 #define EFS_DIRENT_OFF_COMPT(_x)        ((_x) >> EFS_DIRENT_OFF_SHFT)
 170 #define EFS_DIRENT_OFF_VALID(_x)        (((_x) & 0x1) == 0 && (_x) < \
 171                                          EFS_DIRBLK_SPACE_SIZE) /*if expanded*/
 172
 173 #define EFS_DIRENT_NAMELEN_MAX          255
 174
 175 #define EFS_DIRENT_SIZE_MIN     (sizeof(struct efs_dirent))
 176 #define EFS_DIRENT_SIZE_MAX     (EFS_DIRENT_SIZE_MIN+EFS_DIRENT_NAMELEN_MAX - 1)
 177
 178 /*
 179  * Calculate the size of struct efs_dirent given the provided namelen. If our
 180  * namelen were even, then struct efs_dirent's size would be odd. In such a case
 181  * we must pad to ensure 16-bit alignment of the structure.
 182  */
 183 #define EFS_DIRENT_SIZE(_x)     (EFS_DIRENT_SIZE_MIN + (_x) - ((_x) & 0x1))
 184
 185 #endif /* !_FS_EFS_EFS_DIR_H_ */