b24413180f560 (Greg Kroah-Hartman 2017-11-01 15:07:57 +0100 1) // SPDX-License-Identifier: GPL-2.0
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 2) /*
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 3) * linux/fs/hfs/bfind.c
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 4) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 5) * Copyright (C) 2001
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 6) * Brad Boyer (flar@allandria.com)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 7) * (C) 2003 Ardis Technologies <roman@ardistech.com>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 8) *
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 9) * Search routines for btrees
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 10) */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 11)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 12) #include <linux/slab.h>
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 13) #include "btree.h"
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 14)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 15) int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 16) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 17) void *ptr;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 18)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 19) fd->tree = tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 20) fd->bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 21) ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 22) if (!ptr)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 23) return -ENOMEM;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 24) fd->search_key = ptr;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 25) fd->key = ptr + tree->max_key_len + 2;
c2b3e1f76e5c9 (Joe Perches 2013-04-30 15:27:54 -0700 26) hfs_dbg(BNODE_REFS, "find_init: %d (%p)\n",
c2b3e1f76e5c9 (Joe Perches 2013-04-30 15:27:54 -0700 27) tree->cnid, __builtin_return_address(0));
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 28) switch (tree->cnid) {
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 29) case HFS_CAT_CNID:
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 30) mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX);
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 31) break;
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 32) case HFS_EXT_CNID:
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 33) mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX);
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 34) break;
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 35) case HFS_ATTR_CNID:
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 36) mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX);
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 37) break;
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 38) default:
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 39) return -EINVAL;
ca03de06def9a (Desmond Cheong Zhi Xi 2021-07-14 21:27:08 -0700 40) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 41) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 42) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 43)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 44) void hfs_find_exit(struct hfs_find_data *fd)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 45) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 46) hfs_bnode_put(fd->bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 47) kfree(fd->search_key);
c2b3e1f76e5c9 (Joe Perches 2013-04-30 15:27:54 -0700 48) hfs_dbg(BNODE_REFS, "find_exit: %d (%p)\n",
c2b3e1f76e5c9 (Joe Perches 2013-04-30 15:27:54 -0700 49) fd->tree->cnid, __builtin_return_address(0));
4a9410355406c (Thomas Gleixner 2010-09-07 14:33:08 +0000 50) mutex_unlock(&fd->tree->tree_lock);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 51) fd->tree = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 52) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 53)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 54) /* Find the record in bnode that best matches key (not greater than...)*/
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 55) int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 56) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 57) int cmpval;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 58) u16 off, len, keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 59) int rec;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 60) int b, e;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 61) int res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 62)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 63) b = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 64) e = bnode->num_recs - 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 65) res = -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 66) do {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 67) rec = (e + b) / 2;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 68) len = hfs_brec_lenoff(bnode, rec, &off);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 69) keylen = hfs_brec_keylen(bnode, rec);
55581d018ed34 (Eric Sandeen 2008-02-06 01:37:10 -0800 70) if (keylen == 0) {
cf05946250831 (Eric Sandeen 2008-01-08 15:33:20 -0800 71) res = -EINVAL;
55581d018ed34 (Eric Sandeen 2008-02-06 01:37:10 -0800 72) goto fail;
cf05946250831 (Eric Sandeen 2008-01-08 15:33:20 -0800 73) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 74) hfs_bnode_read(bnode, fd->key, off, keylen);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 75) cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 76) if (!cmpval) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 77) e = rec;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 78) res = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 79) goto done;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 80) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 81) if (cmpval < 0)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 82) b = rec + 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 83) else
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 84) e = rec - 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 85) } while (b <= e);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 86) if (rec != e && e >= 0) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 87) len = hfs_brec_lenoff(bnode, e, &off);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 88) keylen = hfs_brec_keylen(bnode, e);
55581d018ed34 (Eric Sandeen 2008-02-06 01:37:10 -0800 89) if (keylen == 0) {
cf05946250831 (Eric Sandeen 2008-01-08 15:33:20 -0800 90) res = -EINVAL;
55581d018ed34 (Eric Sandeen 2008-02-06 01:37:10 -0800 91) goto fail;
cf05946250831 (Eric Sandeen 2008-01-08 15:33:20 -0800 92) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 93) hfs_bnode_read(bnode, fd->key, off, keylen);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 94) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 95) done:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 96) fd->record = e;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 97) fd->keyoffset = off;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 98) fd->keylength = keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 99) fd->entryoffset = off + keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 100) fd->entrylength = len - keylen;
55581d018ed34 (Eric Sandeen 2008-02-06 01:37:10 -0800 101) fail:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 102) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 103) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 104)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 105) /* Traverse a B*Tree from the root to a leaf finding best fit to key */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 106) /* Return allocated copy of node found, set recnum to best record */
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 107) int hfs_brec_find(struct hfs_find_data *fd)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 108) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 109) struct hfs_btree *tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 110) struct hfs_bnode *bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 111) u32 nidx, parent;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 112) __be32 data;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 113) int height, res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 114)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 115) tree = fd->tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 116) if (fd->bnode)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 117) hfs_bnode_put(fd->bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 118) fd->bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 119) nidx = tree->root;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 120) if (!nidx)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 121) return -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 122) height = tree->depth;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 123) res = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 124) parent = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 125) for (;;) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 126) bnode = hfs_bnode_find(tree, nidx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 127) if (IS_ERR(bnode)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 128) res = PTR_ERR(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 129) bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 130) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 131) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 132) if (bnode->height != height)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 133) goto invalid;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 134) if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 135) goto invalid;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 136) bnode->parent = parent;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 137)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 138) res = __hfs_brec_find(bnode, fd);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 139) if (!height)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 140) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 141) if (fd->record < 0)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 142) goto release;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 143)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 144) parent = nidx;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 145) hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 146) nidx = be32_to_cpu(data);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 147) hfs_bnode_put(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 148) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 149) fd->bnode = bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 150) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 151)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 152) invalid:
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 153) pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 154) height, bnode->height, bnode->type, nidx, parent);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 155) res = -EIO;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 156) release:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 157) hfs_bnode_put(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 158) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 159) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 160)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 161) int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 162) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 163) int res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 164)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 165) res = hfs_brec_find(fd);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 166) if (res)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 167) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 168) if (fd->entrylength > rec_len)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 169) return -EINVAL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 170) hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 171) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 172) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 173)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 174) int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 175) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 176) struct hfs_btree *tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 177) struct hfs_bnode *bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 178) int idx, res = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 179) u16 off, len, keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 180)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 181) bnode = fd->bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 182) tree = bnode->tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 183)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 184) if (cnt < 0) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 185) cnt = -cnt;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 186) while (cnt > fd->record) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 187) cnt -= fd->record + 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 188) fd->record = bnode->num_recs - 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 189) idx = bnode->prev;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 190) if (!idx) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 191) res = -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 192) goto out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 193) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 194) hfs_bnode_put(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 195) bnode = hfs_bnode_find(tree, idx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 196) if (IS_ERR(bnode)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 197) res = PTR_ERR(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 198) bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 199) goto out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 200) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 201) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 202) fd->record -= cnt;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 203) } else {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 204) while (cnt >= bnode->num_recs - fd->record) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 205) cnt -= bnode->num_recs - fd->record;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 206) fd->record = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 207) idx = bnode->next;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 208) if (!idx) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 209) res = -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 210) goto out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 211) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 212) hfs_bnode_put(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 213) bnode = hfs_bnode_find(tree, idx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 214) if (IS_ERR(bnode)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 215) res = PTR_ERR(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 216) bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 217) goto out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 218) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 219) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 220) fd->record += cnt;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 221) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 222)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 223) len = hfs_brec_lenoff(bnode, fd->record, &off);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 224) keylen = hfs_brec_keylen(bnode, fd->record);
55581d018ed34 (Eric Sandeen 2008-02-06 01:37:10 -0800 225) if (keylen == 0) {
cf05946250831 (Eric Sandeen 2008-01-08 15:33:20 -0800 226) res = -EINVAL;
cf05946250831 (Eric Sandeen 2008-01-08 15:33:20 -0800 227) goto out;
cf05946250831 (Eric Sandeen 2008-01-08 15:33:20 -0800 228) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 229) fd->keyoffset = off;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 230) fd->keylength = keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 231) fd->entryoffset = off + keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 232) fd->entrylength = len - keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 233) hfs_bnode_read(bnode, fd->key, off, keylen);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 234) out:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 235) fd->bnode = bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 236) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 237) }