1 /* 2 * linux/fs/hfsplus/bfind.c 3 * 4 * Copyright (C) 2001 5 * Brad Boyer (flar@allandria.com) 6 * (C) 2003 Ardis Technologies <roman@ardistech.com> 7 * 8 * Search routines for btrees 9 */ 10 11 #include <linux/slab.h> 12 #include "hfsplus_fs.h" 13 14 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd) 15 { 16 void *ptr; 17 18 fd->tree = tree; 19 fd->bnode = NULL; 20 ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL); 21 if (!ptr) 22 return -ENOMEM; 23 fd->search_key = ptr; 24 fd->key = ptr + tree->max_key_len + 2; 25 hfs_dbg(BNODE_REFS, "find_init: %d (%p)\n", 26 tree->cnid, __builtin_return_address(0)); 27 switch (tree->cnid) { 28 case HFSPLUS_CAT_CNID: 29 mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX); 30 break; 31 case HFSPLUS_EXT_CNID: 32 mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX); 33 break; 34 case HFSPLUS_ATTR_CNID: 35 mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX); 36 break; 37 default: 38 BUG(); 39 } 40 return 0; 41 } 42 43 void hfs_find_exit(struct hfs_find_data *fd) 44 { 45 hfs_bnode_put(fd->bnode); 46 kfree(fd->search_key); 47 hfs_dbg(BNODE_REFS, "find_exit: %d (%p)\n", 48 fd->tree->cnid, __builtin_return_address(0)); 49 mutex_unlock(&fd->tree->tree_lock); 50 fd->tree = NULL; 51 } 52 53 int hfs_find_1st_rec_by_cnid(struct hfs_bnode *bnode, 54 struct hfs_find_data *fd, 55 int *begin, 56 int *end, 57 int *cur_rec) 58 { 59 __be32 cur_cnid; 60 __be32 search_cnid; 61 62 if (bnode->tree->cnid == HFSPLUS_EXT_CNID) { 63 cur_cnid = fd->key->ext.cnid; 64 search_cnid = fd->search_key->ext.cnid; 65 } else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) { 66 cur_cnid = fd->key->cat.parent; 67 search_cnid = fd->search_key->cat.parent; 68 } else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) { 69 cur_cnid = fd->key->attr.cnid; 70 search_cnid = fd->search_key->attr.cnid; 71 } else { 72 cur_cnid = 0; /* used-uninitialized warning */ 73 search_cnid = 0; 74 BUG(); 75 } 76 77 if (cur_cnid == search_cnid) { 78 (*end) = (*cur_rec); 79 if ((*begin) == (*end)) 80 return 1; 81 } else { 82 if (be32_to_cpu(cur_cnid) < be32_to_cpu(search_cnid)) 83 (*begin) = (*cur_rec) + 1; 84 else 85 (*end) = (*cur_rec) - 1; 86 } 87 88 return 0; 89 } 90 91 int hfs_find_rec_by_key(struct hfs_bnode *bnode, 92 struct hfs_find_data *fd, 93 int *begin, 94 int *end, 95 int *cur_rec) 96 { 97 int cmpval; 98 99 cmpval = bnode->tree->keycmp(fd->key, fd->search_key); 100 if (!cmpval) { 101 (*end) = (*cur_rec); 102 return 1; 103 } 104 if (cmpval < 0) 105 (*begin) = (*cur_rec) + 1; 106 else 107 *(end) = (*cur_rec) - 1; 108 109 return 0; 110 } 111 112 /* Find the record in bnode that best matches key (not greater than...)*/ 113 int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd, 114 search_strategy_t rec_found) 115 { 116 u16 off, len, keylen; 117 int rec; 118 int b, e; 119 int res; 120 121 if (!rec_found) 122 BUG(); 123 124 b = 0; 125 e = bnode->num_recs - 1; 126 res = -ENOENT; 127 do { 128 rec = (e + b) / 2; 129 len = hfs_brec_lenoff(bnode, rec, &off); 130 keylen = hfs_brec_keylen(bnode, rec); 131 if (keylen == 0) { 132 res = -EINVAL; 133 goto fail; 134 } 135 hfs_bnode_read(bnode, fd->key, off, keylen); 136 if (rec_found(bnode, fd, &b, &e, &rec)) { 137 res = 0; 138 goto done; 139 } 140 } while (b <= e); 141 142 if (rec != e && e >= 0) { 143 len = hfs_brec_lenoff(bnode, e, &off); 144 keylen = hfs_brec_keylen(bnode, e); 145 if (keylen == 0) { 146 res = -EINVAL; 147 goto fail; 148 } 149 hfs_bnode_read(bnode, fd->key, off, keylen); 150 } 151 152 done: 153 fd->record = e; 154 fd->keyoffset = off; 155 fd->keylength = keylen; 156 fd->entryoffset = off + keylen; 157 fd->entrylength = len - keylen; 158 159 fail: 160 return res; 161 } 162 163 /* Traverse a B*Tree from the root to a leaf finding best fit to key */ 164 /* Return allocated copy of node found, set recnum to best record */ 165 int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) 166 { 167 struct hfs_btree *tree; 168 struct hfs_bnode *bnode; 169 u32 nidx, parent; 170 __be32 data; 171 int height, res; 172 173 tree = fd->tree; 174 if (fd->bnode) 175 hfs_bnode_put(fd->bnode); 176 fd->bnode = NULL; 177 nidx = tree->root; 178 if (!nidx) 179 return -ENOENT; 180 height = tree->depth; 181 res = 0; 182 parent = 0; 183 for (;;) { 184 bnode = hfs_bnode_find(tree, nidx); 185 if (IS_ERR(bnode)) { 186 res = PTR_ERR(bnode); 187 bnode = NULL; 188 break; 189 } 190 if (bnode->height != height) 191 goto invalid; 192 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) 193 goto invalid; 194 bnode->parent = parent; 195 196 res = __hfs_brec_find(bnode, fd, do_key_compare); 197 if (!height) 198 break; 199 if (fd->record < 0) 200 goto release; 201 202 parent = nidx; 203 hfs_bnode_read(bnode, &data, fd->entryoffset, 4); 204 nidx = be32_to_cpu(data); 205 hfs_bnode_put(bnode); 206 } 207 fd->bnode = bnode; 208 return res; 209 210 invalid: 211 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n", 212 height, bnode->height, bnode->type, nidx, parent); 213 res = -EIO; 214 release: 215 hfs_bnode_put(bnode); 216 return res; 217 } 218 219 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len) 220 { 221 int res; 222 223 res = hfs_brec_find(fd, hfs_find_rec_by_key); 224 if (res) 225 return res; 226 if (fd->entrylength > rec_len) 227 return -EINVAL; 228 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); 229 return 0; 230 } 231 232 int hfs_brec_goto(struct hfs_find_data *fd, int cnt) 233 { 234 struct hfs_btree *tree; 235 struct hfs_bnode *bnode; 236 int idx, res = 0; 237 u16 off, len, keylen; 238 239 bnode = fd->bnode; 240 tree = bnode->tree; 241 242 if (cnt < 0) { 243 cnt = -cnt; 244 while (cnt > fd->record) { 245 cnt -= fd->record + 1; 246 fd->record = bnode->num_recs - 1; 247 idx = bnode->prev; 248 if (!idx) { 249 res = -ENOENT; 250 goto out; 251 } 252 hfs_bnode_put(bnode); 253 bnode = hfs_bnode_find(tree, idx); 254 if (IS_ERR(bnode)) { 255 res = PTR_ERR(bnode); 256 bnode = NULL; 257 goto out; 258 } 259 } 260 fd->record -= cnt; 261 } else { 262 while (cnt >= bnode->num_recs - fd->record) { 263 cnt -= bnode->num_recs - fd->record; 264 fd->record = 0; 265 idx = bnode->next; 266 if (!idx) { 267 res = -ENOENT; 268 goto out; 269 } 270 hfs_bnode_put(bnode); 271 bnode = hfs_bnode_find(tree, idx); 272 if (IS_ERR(bnode)) { 273 res = PTR_ERR(bnode); 274 bnode = NULL; 275 goto out; 276 } 277 } 278 fd->record += cnt; 279 } 280 281 len = hfs_brec_lenoff(bnode, fd->record, &off); 282 keylen = hfs_brec_keylen(bnode, fd->record); 283 if (keylen == 0) { 284 res = -EINVAL; 285 goto out; 286 } 287 fd->keyoffset = off; 288 fd->keylength = keylen; 289 fd->entryoffset = off + keylen; 290 fd->entrylength = len - keylen; 291 hfs_bnode_read(bnode, fd->key, off, keylen); 292 out: 293 fd->bnode = bnode; 294 return res; 295 } 296