1 2 3#include "hfs_btree.h" 4 5/*================ File-local functions ================*/ 6 7/* 8 * hfs_bnode_ditch() 9 * 10 * Description: 11 * This function deletes an entire linked list of bnodes, so it 12 * does not need to keep the linked list consistent as 13 * hfs_bnode_delete() does. 14 * Called by hfs_btree_init() for error cleanup and by hfs_btree_free(). 15 * Input Variable(s): 16 * struct hfs_bnode *bn: pointer to the first (struct hfs_bnode) in 17 * the linked list to be deleted. 18 * Output Variable(s): 19 * NONE 20 * Returns: 21 * void 22 * Preconditions: 23 * 'bn' is NULL or points to a "valid" (struct hfs_bnode) with a 'prev' 24 * field of NULL. 25 * Postconditions: 26 * 'bn' and all (struct hfs_bnode)s in the chain of 'next' pointers 27 * are deleted, freeing the associated memory and hfs_buffer_put()ing 28 * the associated buffer. 29 */ 30static void hfs_bnode_ditch(struct hfs_bnode *bn) { 31 struct hfs_bnode *tmp; 32#if defined(DEBUG_BNODES) || defined(DEBUG_ALL) 33 extern int bnode_count; 34#endif 35 36 while (bn != NULL) { 37 tmp = bn->next; 38#if defined(DEBUG_BNODES) || defined(DEBUG_ALL) 39 hfs_warn("deleting node %d from tree %d with count %d\n", 40 bn->node, (int)ntohl(bn->tree->entry.cnid), bn->count); 41 --bnode_count; 42#endif 43 hfs_buffer_put(bn->buf); /* safe: checks for NULL argument */ 44 45 /* free all but the header */ 46 if (bn->node) { 47 HFS_DELETE(bn); 48 } 49 bn = tmp; 50 } 51} 52 53/*================ Global functions ================*/ 54 55/* 56 * hfs_btree_free() 57 * 58 * Description: 59 * This function frees a (struct hfs_btree) obtained from hfs_btree_init(). 60 * Called by hfs_put_super(). 61 * Input Variable(s): 62 * struct hfs_btree *bt: pointer to the (struct hfs_btree) to free 63 * Output Variable(s): 64 * NONE 65 * Returns: 66 * void 67 * Preconditions: 68 * 'bt' is NULL or points to a "valid" (struct hfs_btree) 69 * Postconditions: 70 * If 'bt' points to a "valid" (struct hfs_btree) then all (struct 71 * hfs_bnode)s associated with 'bt' are freed by calling 72 * hfs_bnode_ditch() and the memory associated with the (struct 73 * hfs_btree) is freed. 74 * If 'bt' is NULL or not "valid" an error is printed and nothing 75 * is changed. 76 */ 77void hfs_btree_free(struct hfs_btree *bt) 78{ 79 int lcv; 80 81 if (bt && (bt->magic == HFS_BTREE_MAGIC)) { 82 hfs_extent_free(&bt->entry.u.file.data_fork); 83 84 for (lcv=0; lcv<HFS_CACHELEN; ++lcv) { 85#if defined(DEBUG_BNODES) || defined(DEBUG_ALL) 86 hfs_warn("deleting nodes from bucket %d:\n", lcv); 87#endif 88 hfs_bnode_ditch(bt->cache[lcv]); 89 } 90 91#if defined(DEBUG_BNODES) || defined(DEBUG_ALL) 92 hfs_warn("deleting header and bitmap nodes\n"); 93#endif 94 hfs_bnode_ditch(&bt->head); 95 96#if defined(DEBUG_BNODES) || defined(DEBUG_ALL) 97 hfs_warn("deleting root node\n"); 98#endif 99 hfs_bnode_ditch(bt->root); 100 101 HFS_DELETE(bt); 102 } else if (bt) { 103 hfs_warn("hfs_btree_free: corrupted hfs_btree.\n"); 104 } 105} 106 107/* 108 * hfs_btree_init() 109 * 110 * Description: 111 * Given some vital information from the MDB (HFS superblock), 112 * initializes the fields of a (struct hfs_btree). 113 * Input Variable(s): 114 * struct hfs_mdb *mdb: pointer to the MDB 115 * ino_t cnid: the CNID (HFS_CAT_CNID or HFS_EXT_CNID) of the B-tree 116 * hfs_u32 tsize: the size, in bytes, of the B-tree 117 * hfs_u32 csize: the size, in bytes, of the clump size for the B-tree 118 * Output Variable(s): 119 * NONE 120 * Returns: 121 * (struct hfs_btree *): pointer to the initialized hfs_btree on success, 122 * or NULL on failure 123 * Preconditions: 124 * 'mdb' points to a "valid" (struct hfs_mdb) 125 * Postconditions: 126 * Assuming the inputs are what they claim to be, no errors occur 127 * reading from disk, and no inconsistencies are noticed in the data 128 * read from disk, the return value is a pointer to a "valid" 129 * (struct hfs_btree). If there are errors reading from disk or 130 * inconsistencies are noticed in the data read from disk, then and 131 * all resources that were allocated are released and NULL is 132 * returned. If the inputs are not what they claim to be or if they 133 * are unnoticed inconsistencies in the data read from disk then the 134 * returned hfs_btree is probably going to lead to errors when it is 135 * used in a non-trivial way. 136 */ 137struct hfs_btree * hfs_btree_init(struct hfs_mdb *mdb, ino_t cnid, 138 hfs_byte_t ext[12], 139 hfs_u32 tsize, hfs_u32 csize) 140{ 141 struct hfs_btree * bt; 142 struct BTHdrRec * th; 143 struct hfs_bnode * tmp; 144 unsigned int next; 145#if defined(DEBUG_HEADER) || defined(DEBUG_ALL) 146 unsigned char *p, *q; 147#endif 148 149 if (!mdb || !ext || !HFS_NEW(bt)) { 150 goto bail3; 151 } 152 153 bt->magic = HFS_BTREE_MAGIC; 154 bt->sys_mdb = mdb->sys_mdb; 155 bt->reserved = 0; 156 bt->lock = 0; 157 hfs_init_waitqueue(&bt->wait); 158 bt->dirt = 0; 159 memset(bt->cache, 0, sizeof(bt->cache)); 160 161 162 bt->entry.mdb = mdb; 163 bt->entry.cnid = cnid; 164 bt->entry.type = HFS_CDR_FIL; 165 bt->entry.u.file.magic = HFS_FILE_MAGIC; 166 bt->entry.u.file.clumpablks = (csize / mdb->alloc_blksz) 167 >> HFS_SECTOR_SIZE_BITS; 168 bt->entry.u.file.data_fork.entry = &bt->entry; 169 bt->entry.u.file.data_fork.lsize = tsize; 170 bt->entry.u.file.data_fork.psize = tsize >> HFS_SECTOR_SIZE_BITS; 171 bt->entry.u.file.data_fork.fork = HFS_FK_DATA; 172 hfs_extent_in(&bt->entry.u.file.data_fork, ext); 173 174 hfs_bnode_read(&bt->head, bt, 0, HFS_STICKY); 175 if (!hfs_buffer_ok(bt->head.buf)) { 176 goto bail2; 177 } 178 th = (struct BTHdrRec *)((char *)hfs_buffer_data(bt->head.buf) + 179 sizeof(struct NodeDescriptor)); 180 181 /* read in the bitmap nodes (if any) */ 182 tmp = &bt->head; 183 while ((next = tmp->ndFLink)) { 184 if (!HFS_NEW(tmp->next)) { 185 goto bail2; 186 } 187 hfs_bnode_read(tmp->next, bt, next, HFS_STICKY); 188 if (!hfs_buffer_ok(tmp->next->buf)) { 189 goto bail2; 190 } 191 tmp->next->prev = tmp; 192 tmp = tmp->next; 193 } 194 195 if (hfs_get_ns(th->bthNodeSize) != htons(HFS_SECTOR_SIZE)) { 196 hfs_warn("hfs_btree_init: bthNodeSize!=512 not supported\n"); 197 goto bail2; 198 } 199 200 if (cnid == htonl(HFS_CAT_CNID)) { 201 bt->compare = (hfs_cmpfn)hfs_cat_compare; 202 } else if (cnid == htonl(HFS_EXT_CNID)) { 203 bt->compare = (hfs_cmpfn)hfs_ext_compare; 204 } else { 205 goto bail2; 206 } 207 bt->bthDepth = hfs_get_hs(th->bthDepth); 208 bt->bthRoot = hfs_get_hl(th->bthRoot); 209 bt->bthNRecs = hfs_get_hl(th->bthNRecs); 210 bt->bthFNode = hfs_get_hl(th->bthFNode); 211 bt->bthLNode = hfs_get_hl(th->bthLNode); 212 bt->bthNNodes = hfs_get_hl(th->bthNNodes); 213 bt->bthFree = hfs_get_hl(th->bthFree); 214 bt->bthKeyLen = hfs_get_hs(th->bthKeyLen); 215 216#if defined(DEBUG_HEADER) || defined(DEBUG_ALL) 217 hfs_warn("bthDepth %d\n", bt->bthDepth); 218 hfs_warn("bthRoot %d\n", bt->bthRoot); 219 hfs_warn("bthNRecs %d\n", bt->bthNRecs); 220 hfs_warn("bthFNode %d\n", bt->bthFNode); 221 hfs_warn("bthLNode %d\n", bt->bthLNode); 222 hfs_warn("bthKeyLen %d\n", bt->bthKeyLen); 223 hfs_warn("bthNNodes %d\n", bt->bthNNodes); 224 hfs_warn("bthFree %d\n", bt->bthFree); 225 p = (unsigned char *)hfs_buffer_data(bt->head.buf); 226 q = p + HFS_SECTOR_SIZE; 227 while (p < q) { 228 hfs_warn("%02x %02x %02x %02x %02x %02x %02x %02x " 229 "%02x %02x %02x %02x %02x %02x %02x %02x\n", 230 *p++, *p++, *p++, *p++, *p++, *p++, *p++, *p++, 231 *p++, *p++, *p++, *p++, *p++, *p++, *p++, *p++); 232 } 233#endif 234 235 /* Read in the root if it exists. 236 The header always exists, but the root exists only if the 237 tree is non-empty */ 238 if (bt->bthDepth && bt->bthRoot) { 239 if (!HFS_NEW(bt->root)) { 240 goto bail2; 241 } 242 hfs_bnode_read(bt->root, bt, bt->bthRoot, HFS_STICKY); 243 if (!hfs_buffer_ok(bt->root->buf)) { 244 goto bail1; 245 } 246 } else { 247 bt->root = NULL; 248 } 249 250 return bt; 251 252 bail1: 253 hfs_bnode_ditch(bt->root); 254 bail2: 255 hfs_bnode_ditch(&bt->head); 256 HFS_DELETE(bt); 257 bail3: 258 return NULL; 259} 260 261/* 262 * hfs_btree_commit() 263 * 264 * Called to write a possibly dirty btree back to disk. 265 */ 266void hfs_btree_commit(struct hfs_btree *bt, hfs_byte_t ext[12], hfs_lword_t size) 267{ 268 if (bt->dirt) { 269 struct BTHdrRec *th; 270 th = (struct BTHdrRec *)((char *)hfs_buffer_data(bt->head.buf) + 271 sizeof(struct NodeDescriptor)); 272 273 hfs_put_hs(bt->bthDepth, th->bthDepth); 274 hfs_put_hl(bt->bthRoot, th->bthRoot); 275 hfs_put_hl(bt->bthNRecs, th->bthNRecs); 276 hfs_put_hl(bt->bthFNode, th->bthFNode); 277 hfs_put_hl(bt->bthLNode, th->bthLNode); 278 hfs_put_hl(bt->bthNNodes, th->bthNNodes); 279 hfs_put_hl(bt->bthFree, th->bthFree); 280 hfs_buffer_dirty(bt->head.buf); 281 282 /* 283 * Commit the bnodes which are not cached. 284 * The map nodes don't need to be committed here because 285 * they are committed every time they are changed. 286 */ 287 hfs_bnode_commit(&bt->head); 288 if (bt->root) { 289 hfs_bnode_commit(bt->root); 290 } 291 292 293 hfs_put_hl(bt->bthNNodes << HFS_SECTOR_SIZE_BITS, size); 294 hfs_extent_out(&bt->entry.u.file.data_fork, ext); 295 /* hfs_buffer_dirty(mdb->buf); (Done by caller) */ 296 297 bt->dirt = 0; 298 } 299} 300