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