1 /* $NetBSD: efs_dir.h,v 1.2 2016/07/07 06:55:42 msaitoh Exp $ */ 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_ */ 186