fs/hfs/bfind.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/hfs/bfind.c
0004  *
0005  * Copyright (C) 2001
0006  * Brad Boyer (flar@allandria.com)
0007  * (C) 2003 Ardis Technologies <roman@ardistech.com>
0008  *
0009  * Search routines for btrees
0010  */
0011
0012 #include <linux/slab.h>
0013 #include "btree.h"
0014
0015 int hfs_find_init(struct hfs_btree *tree, struct hfs_find_data *fd)
0016 {
0017     void *ptr;
0018
0019     fd->tree = tree;
0020     fd->bnode = NULL;
0021     ptr = kmalloc(tree->max_key_len * 2 + 4, GFP_KERNEL);
0022     if (!ptr)
0023         return -ENOMEM;
0024     fd->search_key = ptr;
0025     fd->key = ptr + tree->max_key_len + 2;
0026     hfs_dbg(BNODE_REFS, "find_init: %d (%p)\n",
0027         tree->cnid, __builtin_return_address(0));
0028     switch (tree->cnid) {
0029     case HFS_CAT_CNID:
0030         mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX);
0031         break;
0032     case HFS_EXT_CNID:
0033         mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX);
0034         break;
0035     case HFS_ATTR_CNID:
0036         mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX);
0037         break;
0038     default:
0039         return -EINVAL;
0040     }
0041     return 0;
0042 }
0043
0044 void hfs_find_exit(struct hfs_find_data *fd)
0045 {
0046     hfs_bnode_put(fd->bnode);
0047     kfree(fd->search_key);
0048     hfs_dbg(BNODE_REFS, "find_exit: %d (%p)\n",
0049         fd->tree->cnid, __builtin_return_address(0));
0050     mutex_unlock(&fd->tree->tree_lock);
0051     fd->tree = NULL;
0052 }
0053
0054 /* Find the record in bnode that best matches key (not greater than...)*/
0055 int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd)
0056 {
0057     int cmpval;
0058     u16 off, len, keylen;
0059     int rec;
0060     int b, e;
0061     int res;
0062
0063     b = 0;
0064     e = bnode->num_recs - 1;
0065     res = -ENOENT;
0066     do {
0067         rec = (e + b) / 2;
0068         len = hfs_brec_lenoff(bnode, rec, &off);
0069         keylen = hfs_brec_keylen(bnode, rec);
0070         if (keylen == 0) {
0071             res = -EINVAL;
0072             goto fail;
0073         }
0074         hfs_bnode_read(bnode, fd->key, off, keylen);
0075         cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
0076         if (!cmpval) {
0077             e = rec;
0078             res = 0;
0079             goto done;
0080         }
0081         if (cmpval < 0)
0082             b = rec + 1;
0083         else
0084             e = rec - 1;
0085     } while (b <= e);
0086     if (rec != e && e >= 0) {
0087         len = hfs_brec_lenoff(bnode, e, &off);
0088         keylen = hfs_brec_keylen(bnode, e);
0089         if (keylen == 0) {
0090             res = -EINVAL;
0091             goto fail;
0092         }
0093         hfs_bnode_read(bnode, fd->key, off, keylen);
0094     }
0095 done:
0096     fd->record = e;
0097     fd->keyoffset = off;
0098     fd->keylength = keylen;
0099     fd->entryoffset = off + keylen;
0100     fd->entrylength = len - keylen;
0101 fail:
0102     return res;
0103 }
0104
0105 /* Traverse a B*Tree from the root to a leaf finding best fit to key */
0106 /* Return allocated copy of node found, set recnum to best record */
0107 int hfs_brec_find(struct hfs_find_data *fd)
0108 {
0109     struct hfs_btree *tree;
0110     struct hfs_bnode *bnode;
0111     u32 nidx, parent;
0112     __be32 data;
0113     int height, res;
0114
0115     tree = fd->tree;
0116     if (fd->bnode)
0117         hfs_bnode_put(fd->bnode);
0118     fd->bnode = NULL;
0119     nidx = tree->root;
0120     if (!nidx)
0121         return -ENOENT;
0122     height = tree->depth;
0123     res = 0;
0124     parent = 0;
0125     for (;;) {
0126         bnode = hfs_bnode_find(tree, nidx);
0127         if (IS_ERR(bnode)) {
0128             res = PTR_ERR(bnode);
0129             bnode = NULL;
0130             break;
0131         }
0132         if (bnode->height != height)
0133             goto invalid;
0134         if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
0135             goto invalid;
0136         bnode->parent = parent;
0137
0138         res = __hfs_brec_find(bnode, fd);
0139         if (!height)
0140             break;
0141         if (fd->record < 0)
0142             goto release;
0143
0144         parent = nidx;
0145         hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
0146         nidx = be32_to_cpu(data);
0147         hfs_bnode_put(bnode);
0148     }
0149     fd->bnode = bnode;
0150     return res;
0151
0152 invalid:
0153     pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
0154            height, bnode->height, bnode->type, nidx, parent);
0155     res = -EIO;
0156 release:
0157     hfs_bnode_put(bnode);
0158     return res;
0159 }
0160
0161 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
0162 {
0163     int res;
0164
0165     res = hfs_brec_find(fd);
0166     if (res)
0167         return res;
0168     if (fd->entrylength > rec_len)
0169         return -EINVAL;
0170     hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
0171     return 0;
0172 }
0173
0174 int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
0175 {
0176     struct hfs_btree *tree;
0177     struct hfs_bnode *bnode;
0178     int idx, res = 0;
0179     u16 off, len, keylen;
0180
0181     bnode = fd->bnode;
0182     tree = bnode->tree;
0183
0184     if (cnt < 0) {
0185         cnt = -cnt;
0186         while (cnt > fd->record) {
0187             cnt -= fd->record + 1;
0188             fd->record = bnode->num_recs - 1;
0189             idx = bnode->prev;
0190             if (!idx) {
0191                 res = -ENOENT;
0192                 goto out;
0193             }
0194             hfs_bnode_put(bnode);
0195             bnode = hfs_bnode_find(tree, idx);
0196             if (IS_ERR(bnode)) {
0197                 res = PTR_ERR(bnode);
0198                 bnode = NULL;
0199                 goto out;
0200             }
0201         }
0202         fd->record -= cnt;
0203     } else {
0204         while (cnt >= bnode->num_recs - fd->record) {
0205             cnt -= bnode->num_recs - fd->record;
0206             fd->record = 0;
0207             idx = bnode->next;
0208             if (!idx) {
0209                 res = -ENOENT;
0210                 goto out;
0211             }
0212             hfs_bnode_put(bnode);
0213             bnode = hfs_bnode_find(tree, idx);
0214             if (IS_ERR(bnode)) {
0215                 res = PTR_ERR(bnode);
0216                 bnode = NULL;
0217                 goto out;
0218             }
0219         }
0220         fd->record += cnt;
0221     }
0222
0223     len = hfs_brec_lenoff(bnode, fd->record, &off);
0224     keylen = hfs_brec_keylen(bnode, fd->record);
0225     if (keylen == 0) {
0226         res = -EINVAL;
0227         goto out;
0228     }
0229     fd->keyoffset = off;
0230     fd->keylength = keylen;
0231     fd->entryoffset = off + keylen;
0232     fd->entrylength = len - keylen;
0233     hfs_bnode_read(bnode, fd->key, off, keylen);
0234 out:
0235     fd->bnode = bnode;
0236     return res;
0237 }