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 BUG_ON(!rec_found); 122 b = 0; 123 e = bnode->num_recs - 1; 124 res = -ENOENT; 125 do { 126 rec = (e + b) / 2; 127 len = hfs_brec_lenoff(bnode, rec, &off); 128 keylen = hfs_brec_keylen(bnode, rec); 129 if (keylen == 0) { 130 res = -EINVAL; 131 goto fail; 132 } 133 hfs_bnode_read(bnode, fd->key, off, keylen); 134 if (rec_found(bnode, fd, &b, &e, &rec)) { 135 res = 0; 136 goto done; 137 } 138 } while (b <= e); 139 140 if (rec != e && e >= 0) { 141 len = hfs_brec_lenoff(bnode, e, &off); 142 keylen = hfs_brec_keylen(bnode, e); 143 if (keylen == 0) { 144 res = -EINVAL; 145 goto fail; 146 } 147 hfs_bnode_read(bnode, fd->key, off, keylen); 148 } 149 150 done: 151 fd->record = e; 152 fd->keyoffset = off; 153 fd->keylength = keylen; 154 fd->entryoffset = off + keylen; 155 fd->entrylength = len - keylen; 156 157 fail: 158 return res; 159 } 160 161 /* Traverse a B*Tree from the root to a leaf finding best fit to key */ 162 /* Return allocated copy of node found, set recnum to best record */ 163 int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare) 164 { 165 struct hfs_btree *tree; 166 struct hfs_bnode *bnode; 167 u32 nidx, parent; 168 __be32 data; 169 int height, res; 170 171 tree = fd->tree; 172 if (fd->bnode) 173 hfs_bnode_put(fd->bnode); 174 fd->bnode = NULL; 175 nidx = tree->root; 176 if (!nidx) 177 return -ENOENT; 178 height = tree->depth; 179 res = 0; 180 parent = 0; 181 for (;;) { 182 bnode = hfs_bnode_find(tree, nidx); 183 if (IS_ERR(bnode)) { 184 res = PTR_ERR(bnode); 185 bnode = NULL; 186 break; 187 } 188 if (bnode->height != height) 189 goto invalid; 190 if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF)) 191 goto invalid; 192 bnode->parent = parent; 193 194 res = __hfs_brec_find(bnode, fd, do_key_compare); 195 if (!height) 196 break; 197 if (fd->record < 0) 198 goto release; 199 200 parent = nidx; 201 hfs_bnode_read(bnode, &data, fd->entryoffset, 4); 202 nidx = be32_to_cpu(data); 203 hfs_bnode_put(bnode); 204 } 205 fd->bnode = bnode; 206 return res; 207 208 invalid: 209 pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n", 210 height, bnode->height, bnode->type, nidx, parent); 211 res = -EIO; 212 release: 213 hfs_bnode_put(bnode); 214 return res; 215 } 216 217 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len) 218 { 219 int res; 220 221 res = hfs_brec_find(fd, hfs_find_rec_by_key); 222 if (res) 223 return res; 224 if (fd->entrylength > rec_len) 225 return -EINVAL; 226 hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength); 227 return 0; 228 } 229 230 int hfs_brec_goto(struct hfs_find_data *fd, int cnt) 231 { 232 struct hfs_btree *tree; 233 struct hfs_bnode *bnode; 234 int idx, res = 0; 235 u16 off, len, keylen; 236 237 bnode = fd->bnode; 238 tree = bnode->tree; 239 240 if (cnt < 0) { 241 cnt = -cnt; 242 while (cnt > fd->record) { 243 cnt -= fd->record + 1; 244 fd->record = bnode->num_recs - 1; 245 idx = bnode->prev; 246 if (!idx) { 247 res = -ENOENT; 248 goto out; 249 } 250 hfs_bnode_put(bnode); 251 bnode = hfs_bnode_find(tree, idx); 252 if (IS_ERR(bnode)) { 253 res = PTR_ERR(bnode); 254 bnode = NULL; 255 goto out; 256 } 257 } 258 fd->record -= cnt; 259 } else { 260 while (cnt >= bnode->num_recs - fd->record) { 261 cnt -= bnode->num_recs - fd->record; 262 fd->record = 0; 263 idx = bnode->next; 264 if (!idx) { 265 res = -ENOENT; 266 goto out; 267 } 268 hfs_bnode_put(bnode); 269 bnode = hfs_bnode_find(tree, idx); 270 if (IS_ERR(bnode)) { 271 res = PTR_ERR(bnode); 272 bnode = NULL; 273 goto out; 274 } 275 } 276 fd->record += cnt; 277 } 278 279 len = hfs_brec_lenoff(bnode, fd->record, &off); 280 keylen = hfs_brec_keylen(bnode, fd->record); 281 if (keylen == 0) { 282 res = -EINVAL; 283 goto out; 284 } 285 fd->keyoffset = off; 286 fd->keylength = keylen; 287 fd->entryoffset = off + keylen; 288 fd->entrylength = len - keylen; 289 hfs_bnode_read(bnode, fd->key, off, keylen); 290 out: 291 fd->bnode = bnode; 292 return res; 293 } 294