fs/hfsplus/bfind.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/hfsplus/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 "hfsplus_fs.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 HFSPLUS_CAT_CNID:
0030         mutex_lock_nested(&tree->tree_lock, CATALOG_BTREE_MUTEX);
0031         break;
0032     case HFSPLUS_EXT_CNID:
0033         mutex_lock_nested(&tree->tree_lock, EXTENTS_BTREE_MUTEX);
0034         break;
0035     case HFSPLUS_ATTR_CNID:
0036         mutex_lock_nested(&tree->tree_lock, ATTR_BTREE_MUTEX);
0037         break;
0038     default:
0039         BUG();
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 int hfs_find_1st_rec_by_cnid(struct hfs_bnode *bnode,
0055                 struct hfs_find_data *fd,
0056                 int *begin,
0057                 int *end,
0058                 int *cur_rec)
0059 {
0060     __be32 cur_cnid;
0061     __be32 search_cnid;
0062
0063     if (bnode->tree->cnid == HFSPLUS_EXT_CNID) {
0064         cur_cnid = fd->key->ext.cnid;
0065         search_cnid = fd->search_key->ext.cnid;
0066     } else if (bnode->tree->cnid == HFSPLUS_CAT_CNID) {
0067         cur_cnid = fd->key->cat.parent;
0068         search_cnid = fd->search_key->cat.parent;
0069     } else if (bnode->tree->cnid == HFSPLUS_ATTR_CNID) {
0070         cur_cnid = fd->key->attr.cnid;
0071         search_cnid = fd->search_key->attr.cnid;
0072     } else {
0073         cur_cnid = 0;   /* used-uninitialized warning */
0074         search_cnid = 0;
0075         BUG();
0076     }
0077
0078     if (cur_cnid == search_cnid) {
0079         (*end) = (*cur_rec);
0080         if ((*begin) == (*end))
0081             return 1;
0082     } else {
0083         if (be32_to_cpu(cur_cnid) < be32_to_cpu(search_cnid))
0084             (*begin) = (*cur_rec) + 1;
0085         else
0086             (*end) = (*cur_rec) - 1;
0087     }
0088
0089     return 0;
0090 }
0091
0092 int hfs_find_rec_by_key(struct hfs_bnode *bnode,
0093                 struct hfs_find_data *fd,
0094                 int *begin,
0095                 int *end,
0096                 int *cur_rec)
0097 {
0098     int cmpval;
0099
0100     cmpval = bnode->tree->keycmp(fd->key, fd->search_key);
0101     if (!cmpval) {
0102         (*end) = (*cur_rec);
0103         return 1;
0104     }
0105     if (cmpval < 0)
0106         (*begin) = (*cur_rec) + 1;
0107     else
0108         *(end) = (*cur_rec) - 1;
0109
0110     return 0;
0111 }
0112
0113 /* Find the record in bnode that best matches key (not greater than...)*/
0114 int __hfs_brec_find(struct hfs_bnode *bnode, struct hfs_find_data *fd,
0115                     search_strategy_t rec_found)
0116 {
0117     u16 off, len, keylen;
0118     int rec;
0119     int b, e;
0120     int res;
0121
0122     BUG_ON(!rec_found);
0123     b = 0;
0124     e = bnode->num_recs - 1;
0125     res = -ENOENT;
0126     do {
0127         rec = (e + b) / 2;
0128         len = hfs_brec_lenoff(bnode, rec, &off);
0129         keylen = hfs_brec_keylen(bnode, rec);
0130         if (keylen == 0) {
0131             res = -EINVAL;
0132             goto fail;
0133         }
0134         hfs_bnode_read(bnode, fd->key, off, keylen);
0135         if (rec_found(bnode, fd, &b, &e, &rec)) {
0136             res = 0;
0137             goto done;
0138         }
0139     } while (b <= e);
0140
0141     if (rec != e && e >= 0) {
0142         len = hfs_brec_lenoff(bnode, e, &off);
0143         keylen = hfs_brec_keylen(bnode, e);
0144         if (keylen == 0) {
0145             res = -EINVAL;
0146             goto fail;
0147         }
0148         hfs_bnode_read(bnode, fd->key, off, keylen);
0149     }
0150
0151 done:
0152     fd->record = e;
0153     fd->keyoffset = off;
0154     fd->keylength = keylen;
0155     fd->entryoffset = off + keylen;
0156     fd->entrylength = len - keylen;
0157
0158 fail:
0159     return res;
0160 }
0161
0162 /* Traverse a B*Tree from the root to a leaf finding best fit to key */
0163 /* Return allocated copy of node found, set recnum to best record */
0164 int hfs_brec_find(struct hfs_find_data *fd, search_strategy_t do_key_compare)
0165 {
0166     struct hfs_btree *tree;
0167     struct hfs_bnode *bnode;
0168     u32 nidx, parent;
0169     __be32 data;
0170     int height, res;
0171
0172     tree = fd->tree;
0173     if (fd->bnode)
0174         hfs_bnode_put(fd->bnode);
0175     fd->bnode = NULL;
0176     nidx = tree->root;
0177     if (!nidx)
0178         return -ENOENT;
0179     height = tree->depth;
0180     res = 0;
0181     parent = 0;
0182     for (;;) {
0183         bnode = hfs_bnode_find(tree, nidx);
0184         if (IS_ERR(bnode)) {
0185             res = PTR_ERR(bnode);
0186             bnode = NULL;
0187             break;
0188         }
0189         if (bnode->height != height)
0190             goto invalid;
0191         if (bnode->type != (--height ? HFS_NODE_INDEX : HFS_NODE_LEAF))
0192             goto invalid;
0193         bnode->parent = parent;
0194
0195         res = __hfs_brec_find(bnode, fd, do_key_compare);
0196         if (!height)
0197             break;
0198         if (fd->record < 0)
0199             goto release;
0200
0201         parent = nidx;
0202         hfs_bnode_read(bnode, &data, fd->entryoffset, 4);
0203         nidx = be32_to_cpu(data);
0204         hfs_bnode_put(bnode);
0205     }
0206     fd->bnode = bnode;
0207     return res;
0208
0209 invalid:
0210     pr_err("inconsistency in B*Tree (%d,%d,%d,%u,%u)\n",
0211         height, bnode->height, bnode->type, nidx, parent);
0212     res = -EIO;
0213 release:
0214     hfs_bnode_put(bnode);
0215     return res;
0216 }
0217
0218 int hfs_brec_read(struct hfs_find_data *fd, void *rec, int rec_len)
0219 {
0220     int res;
0221
0222     res = hfs_brec_find(fd, hfs_find_rec_by_key);
0223     if (res)
0224         return res;
0225     if (fd->entrylength > rec_len)
0226         return -EINVAL;
0227     hfs_bnode_read(fd->bnode, rec, fd->entryoffset, fd->entrylength);
0228     return 0;
0229 }
0230
0231 int hfs_brec_goto(struct hfs_find_data *fd, int cnt)
0232 {
0233     struct hfs_btree *tree;
0234     struct hfs_bnode *bnode;
0235     int idx, res = 0;
0236     u16 off, len, keylen;
0237
0238     bnode = fd->bnode;
0239     tree = bnode->tree;
0240
0241     if (cnt < 0) {
0242         cnt = -cnt;
0243         while (cnt > fd->record) {
0244             cnt -= fd->record + 1;
0245             fd->record = bnode->num_recs - 1;
0246             idx = bnode->prev;
0247             if (!idx) {
0248                 res = -ENOENT;
0249                 goto out;
0250             }
0251             hfs_bnode_put(bnode);
0252             bnode = hfs_bnode_find(tree, idx);
0253             if (IS_ERR(bnode)) {
0254                 res = PTR_ERR(bnode);
0255                 bnode = NULL;
0256                 goto out;
0257             }
0258         }
0259         fd->record -= cnt;
0260     } else {
0261         while (cnt >= bnode->num_recs - fd->record) {
0262             cnt -= bnode->num_recs - fd->record;
0263             fd->record = 0;
0264             idx = bnode->next;
0265             if (!idx) {
0266                 res = -ENOENT;
0267                 goto out;
0268             }
0269             hfs_bnode_put(bnode);
0270             bnode = hfs_bnode_find(tree, idx);
0271             if (IS_ERR(bnode)) {
0272                 res = PTR_ERR(bnode);
0273                 bnode = NULL;
0274                 goto out;
0275             }
0276         }
0277         fd->record += cnt;
0278     }
0279
0280     len = hfs_brec_lenoff(bnode, fd->record, &off);
0281     keylen = hfs_brec_keylen(bnode, fd->record);
0282     if (keylen == 0) {
0283         res = -EINVAL;
0284         goto out;
0285     }
0286     fd->keyoffset = off;
0287     fd->keylength = keylen;
0288     fd->entryoffset = off + keylen;
0289     fd->entrylength = len - keylen;
0290     hfs_bnode_read(bnode, fd->key, off, keylen);
0291 out:
0292     fd->bnode = bnode;
0293     return res;
0294 }