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/hfsplus/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 "hfsplus_fs.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",
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 27) tree->cnid, __builtin_return_address(0));
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 28) switch (tree->cnid) {
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 29) case HFSPLUS_CAT_CNID:
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 30) mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 31) break;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 32) case HFSPLUS_EXT_CNID:
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 33) mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 34) break;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 35) case HFSPLUS_ATTR_CNID:
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 36) mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 37) break;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 38) default:
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 39) BUG();
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 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",
2753cc281c9a0 (Anton Salikhmetov 2010-12-16 18:08:38 +0200 49) fd->tree->cnid, __builtin_return_address(0));
467c3d9cd541e (Thomas Gleixner 2010-10-01 05:46:52 +0200 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)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 54) int hfs_find_1st_rec_by_cnid(struct hfs_bnode *bnode,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 55) struct hfs_find_data *fd,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 56) int *begin,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 57) int *end,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 58) int *cur_rec)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 59) {
5f3726f9457d5 (Vyacheslav Dubeyko 2013-04-30 15:27:53 -0700 60) __be32 cur_cnid;
5f3726f9457d5 (Vyacheslav Dubeyko 2013-04-30 15:27:53 -0700 61) __be32 search_cnid;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 62)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 63) if (bnode->tree->cnid == HFSPLUS_EXT_CNID) {
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 64) cur_cnid = fd->key->ext.cnid;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 65) search_cnid = fd->search_key->ext.cnid;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 66) } else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) {
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 67) cur_cnid = fd->key->cat.parent;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 68) search_cnid = fd->search_key->cat.parent;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 69) } else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) {
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 70) cur_cnid = fd->key->attr.cnid;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 71) search_cnid = fd->search_key->attr.cnid;
5f3726f9457d5 (Vyacheslav Dubeyko 2013-04-30 15:27:53 -0700 72) } else {
5f3726f9457d5 (Vyacheslav Dubeyko 2013-04-30 15:27:53 -0700 73) cur_cnid = 0; /* used-uninitialized warning */
5f3726f9457d5 (Vyacheslav Dubeyko 2013-04-30 15:27:53 -0700 74) search_cnid = 0;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 75) BUG();
5f3726f9457d5 (Vyacheslav Dubeyko 2013-04-30 15:27:53 -0700 76) }
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 77)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 78) if (cur_cnid == search_cnid) {
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 79) (*end) = (*cur_rec);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 80) if ((*begin) == (*end))
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 81) return 1;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 82) } else {
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 83) if (be32_to_cpu(cur_cnid) < be32_to_cpu(search_cnid))
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 84) (*begin) = (*cur_rec) + 1;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 85) else
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 86) (*end) = (*cur_rec) - 1;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 87) }
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 88)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 89) return 0;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 90) }
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 91)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 92) int hfs_find_rec_by_key(struct hfs_bnode *bnode,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 93) struct hfs_find_data *fd,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 94) int *begin,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 95) int *end,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 96) int *cur_rec)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 97) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 98) int cmpval;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 99)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 100) cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 101) if (!cmpval) {
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 102) (*end) = (*cur_rec);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 103) return 1;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 104) }
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 105) if (cmpval < 0)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 106) (*begin) = (*cur_rec) + 1;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 107) else
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 108) *(end) = (*cur_rec) - 1;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 109)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 110) return 0;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 111) }
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 112)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 113) /* Find the record in bnode that best matches key (not greater than...)*/
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 114) int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 115) search_strategy_t rec_found)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 116) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 117) u16 off, len, keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 118) int rec;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 119) int b, e;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 120) int res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 121)
7ce844a20eb58 (Fabian Frederick 2015-04-16 12:47:09 -0700 122) BUG_ON(!rec_found);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 123) b = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 124) e = bnode->num_recs - 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 125) res = -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 126) do {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 127) rec = (e + b) / 2;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 128) len = hfs_brec_lenoff(bnode, rec, &off);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 129) keylen = hfs_brec_keylen(bnode, rec);
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 130) if (keylen == 0) {
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 131) res = -EINVAL;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 132) goto fail;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 133) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 134) hfs_bnode_read(bnode, fd->key, off, keylen);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 135) if (rec_found(bnode, fd, &b, &e, &rec)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 136) res = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 137) goto done;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 138) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 139) } while (b <= e);
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 140)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 141) if (rec != e && e >= 0) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 142) len = hfs_brec_lenoff(bnode, e, &off);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 143) keylen = hfs_brec_keylen(bnode, e);
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 144) if (keylen == 0) {
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 145) res = -EINVAL;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 146) goto fail;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 147) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 148) hfs_bnode_read(bnode, fd->key, off, keylen);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 149) }
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 150)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 151) done:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 152) fd->record = e;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 153) fd->keyoffset = off;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 154) fd->keylength = keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 155) fd->entryoffset = off + keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 156) fd->entrylength = len - keylen;
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 157)
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 158) fail:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 159) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 160) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 161)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 162) /* 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 163) /* Return allocated copy of node found, set recnum to best record */
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 164) int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 165) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 166) struct hfs_btree *tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 167) struct hfs_bnode *bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 168) u32 nidx, parent;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 169) __be32 data;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 170) int height, res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 171)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 172) tree = fd->tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 173) if (fd->bnode)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 174) hfs_bnode_put(fd->bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 175) fd->bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 176) nidx = tree->root;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 177) if (!nidx)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 178) return -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 179) height = tree->depth;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 180) res = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 181) parent = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 182) for (;;) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 183) bnode = hfs_bnode_find(tree, nidx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 184) if (IS_ERR(bnode)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 185) res = PTR_ERR(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 186) bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 187) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 188) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 189) if (bnode->height != height)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 190) goto invalid;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 191) if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 192) goto invalid;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 193) bnode->parent = parent;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 194)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 195) res = __hfs_brec_find(bnode, fd, do_key_compare);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 196) if (!height)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 197) break;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 198) if (fd->record < 0)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 199) goto release;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 200)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 201) parent = nidx;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 202) hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 203) nidx = be32_to_cpu(data);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 204) hfs_bnode_put(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 205) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 206) fd->bnode = bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 207) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 208)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 209) invalid:
d614267329f2b (Joe Perches 2013-04-30 15:27:55 -0700 210) pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 211) height, bnode->height, bnode->type, nidx, parent);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 212) res = -EIO;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 213) release:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 214) hfs_bnode_put(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 215) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 216) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 217)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 218) int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 219) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 220) int res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 221)
324ef39a8a4f6 (Vyacheslav Dubeyko 2013-02-27 17:03:04 -0800 222) res = hfs_brec_find(fd, hfs_find_rec_by_key);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 223) if (res)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 224) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 225) if (fd->entrylength > rec_len)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 226) return -EINVAL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 227) hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 228) return 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 229) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 230)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 231) int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 232) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 233) struct hfs_btree *tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 234) struct hfs_bnode *bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 235) int idx, res = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 236) u16 off, len, keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 237)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 238) bnode = fd->bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 239) tree = bnode->tree;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 240)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 241) if (cnt < 0) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 242) cnt = -cnt;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 243) while (cnt > fd->record) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 244) cnt -= fd->record + 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 245) fd->record = bnode->num_recs - 1;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 246) idx = bnode->prev;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 247) if (!idx) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 248) res = -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 249) goto out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 250) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 251) hfs_bnode_put(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 252) bnode = hfs_bnode_find(tree, idx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 253) if (IS_ERR(bnode)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 254) res = PTR_ERR(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 255) bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 256) goto out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 257) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 258) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 259) fd->record -= cnt;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 260) } else {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 261) while (cnt >= bnode->num_recs - fd->record) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 262) cnt -= bnode->num_recs - fd->record;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 263) fd->record = 0;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 264) idx = bnode->next;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 265) if (!idx) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 266) res = -ENOENT;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 267) goto out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 268) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 269) hfs_bnode_put(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 270) bnode = hfs_bnode_find(tree, idx);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 271) if (IS_ERR(bnode)) {
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 272) res = PTR_ERR(bnode);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 273) bnode = NULL;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 274) goto out;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 275) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 276) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 277) fd->record += cnt;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 278) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 279)
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 280) len = hfs_brec_lenoff(bnode, fd->record, &off);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 281) keylen = hfs_brec_keylen(bnode, fd->record);
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 282) if (keylen == 0) {
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 283) res = -EINVAL;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 284) goto out;
9250f925972d0 (Eric Sandeen 2010-10-14 09:53:48 -0400 285) }
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 286) fd->keyoffset = off;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 287) fd->keylength = keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 288) fd->entryoffset = off + keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 289) fd->entrylength = len - keylen;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 290) hfs_bnode_read(bnode, fd->key, off, keylen);
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 291) out:
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 292) fd->bnode = bnode;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 293) return res;
^1da177e4c3f4 (Linus Torvalds 2005-04-16 15:20:36 -0700 294) }
VisionFive2 Linux kernel
StarFive Tech Linux Kernel for VisionFive (JH7110) boards (mirror)
More than 9999 Commits
32 Branches
54 Tags