Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  *  linux/fs/hfsplus/brec.c
0004  *
0005  * Copyright (C) 2001
0006  * Brad Boyer (flar@allandria.com)
0007  * (C) 2003 Ardis Technologies <roman@ardistech.com>
0008  *
0009  * Handle individual btree records
0010  */
0011 
0012 #include "hfsplus_fs.h"
0013 #include "hfsplus_raw.h"
0014 
0015 static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd);
0016 static int hfs_brec_update_parent(struct hfs_find_data *fd);
0017 static int hfs_btree_inc_height(struct hfs_btree *);
0018 
0019 /* Get the length and offset of the given record in the given node */
0020 u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off)
0021 {
0022     __be16 retval[2];
0023     u16 dataoff;
0024 
0025     dataoff = node->tree->node_size - (rec + 2) * 2;
0026     hfs_bnode_read(node, retval, dataoff, 4);
0027     *off = be16_to_cpu(retval[1]);
0028     return be16_to_cpu(retval[0]) - *off;
0029 }
0030 
0031 /* Get the length of the key from a keyed record */
0032 u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
0033 {
0034     u16 retval, recoff;
0035 
0036     if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF)
0037         return 0;
0038 
0039     if ((node->type == HFS_NODE_INDEX) &&
0040        !(node->tree->attributes & HFS_TREE_VARIDXKEYS) &&
0041        (node->tree->cnid != HFSPLUS_ATTR_CNID)) {
0042         retval = node->tree->max_key_len + 2;
0043     } else {
0044         recoff = hfs_bnode_read_u16(node,
0045             node->tree->node_size - (rec + 1) * 2);
0046         if (!recoff)
0047             return 0;
0048         if (recoff > node->tree->node_size - 2) {
0049             pr_err("recoff %d too large\n", recoff);
0050             return 0;
0051         }
0052 
0053         retval = hfs_bnode_read_u16(node, recoff) + 2;
0054         if (retval > node->tree->max_key_len + 2) {
0055             pr_err("keylen %d too large\n",
0056                 retval);
0057             retval = 0;
0058         }
0059     }
0060     return retval;
0061 }
0062 
0063 int hfs_brec_insert(struct hfs_find_data *fd, void *entry, int entry_len)
0064 {
0065     struct hfs_btree *tree;
0066     struct hfs_bnode *node, *new_node;
0067     int size, key_len, rec;
0068     int data_off, end_off;
0069     int idx_rec_off, data_rec_off, end_rec_off;
0070     __be32 cnid;
0071 
0072     tree = fd->tree;
0073     if (!fd->bnode) {
0074         if (!tree->root)
0075             hfs_btree_inc_height(tree);
0076         node = hfs_bnode_find(tree, tree->leaf_head);
0077         if (IS_ERR(node))
0078             return PTR_ERR(node);
0079         fd->bnode = node;
0080         fd->record = -1;
0081     }
0082     new_node = NULL;
0083     key_len = be16_to_cpu(fd->search_key->key_len) + 2;
0084 again:
0085     /* new record idx and complete record size */
0086     rec = fd->record + 1;
0087     size = key_len + entry_len;
0088 
0089     node = fd->bnode;
0090     hfs_bnode_dump(node);
0091     /* get last offset */
0092     end_rec_off = tree->node_size - (node->num_recs + 1) * 2;
0093     end_off = hfs_bnode_read_u16(node, end_rec_off);
0094     end_rec_off -= 2;
0095     hfs_dbg(BNODE_MOD, "insert_rec: %d, %d, %d, %d\n",
0096         rec, size, end_off, end_rec_off);
0097     if (size > end_rec_off - end_off) {
0098         if (new_node)
0099             panic("not enough room!\n");
0100         new_node = hfs_bnode_split(fd);
0101         if (IS_ERR(new_node))
0102             return PTR_ERR(new_node);
0103         goto again;
0104     }
0105     if (node->type == HFS_NODE_LEAF) {
0106         tree->leaf_count++;
0107         mark_inode_dirty(tree->inode);
0108     }
0109     node->num_recs++;
0110     /* write new last offset */
0111     hfs_bnode_write_u16(node,
0112         offsetof(struct hfs_bnode_desc, num_recs),
0113         node->num_recs);
0114     hfs_bnode_write_u16(node, end_rec_off, end_off + size);
0115     data_off = end_off;
0116     data_rec_off = end_rec_off + 2;
0117     idx_rec_off = tree->node_size - (rec + 1) * 2;
0118     if (idx_rec_off == data_rec_off)
0119         goto skip;
0120     /* move all following entries */
0121     do {
0122         data_off = hfs_bnode_read_u16(node, data_rec_off + 2);
0123         hfs_bnode_write_u16(node, data_rec_off, data_off + size);
0124         data_rec_off += 2;
0125     } while (data_rec_off < idx_rec_off);
0126 
0127     /* move data away */
0128     hfs_bnode_move(node, data_off + size, data_off,
0129                end_off - data_off);
0130 
0131 skip:
0132     hfs_bnode_write(node, fd->search_key, data_off, key_len);
0133     hfs_bnode_write(node, entry, data_off + key_len, entry_len);
0134     hfs_bnode_dump(node);
0135 
0136     /*
0137      * update parent key if we inserted a key
0138      * at the start of the node and it is not the new node
0139      */
0140     if (!rec && new_node != node) {
0141         hfs_bnode_read_key(node, fd->search_key, data_off + size);
0142         hfs_brec_update_parent(fd);
0143     }
0144 
0145     if (new_node) {
0146         hfs_bnode_put(fd->bnode);
0147         if (!new_node->parent) {
0148             hfs_btree_inc_height(tree);
0149             new_node->parent = tree->root;
0150         }
0151         fd->bnode = hfs_bnode_find(tree, new_node->parent);
0152 
0153         /* create index data entry */
0154         cnid = cpu_to_be32(new_node->this);
0155         entry = &cnid;
0156         entry_len = sizeof(cnid);
0157 
0158         /* get index key */
0159         hfs_bnode_read_key(new_node, fd->search_key, 14);
0160         __hfs_brec_find(fd->bnode, fd, hfs_find_rec_by_key);
0161 
0162         hfs_bnode_put(new_node);
0163         new_node = NULL;
0164 
0165         if ((tree->attributes & HFS_TREE_VARIDXKEYS) ||
0166                 (tree->cnid == HFSPLUS_ATTR_CNID))
0167             key_len = be16_to_cpu(fd->search_key->key_len) + 2;
0168         else {
0169             fd->search_key->key_len =
0170                 cpu_to_be16(tree->max_key_len);
0171             key_len = tree->max_key_len + 2;
0172         }
0173         goto again;
0174     }
0175 
0176     return 0;
0177 }
0178 
0179 int hfs_brec_remove(struct hfs_find_data *fd)
0180 {
0181     struct hfs_btree *tree;
0182     struct hfs_bnode *node, *parent;
0183     int end_off, rec_off, data_off, size;
0184 
0185     tree = fd->tree;
0186     node = fd->bnode;
0187 again:
0188     rec_off = tree->node_size - (fd->record + 2) * 2;
0189     end_off = tree->node_size - (node->num_recs + 1) * 2;
0190 
0191     if (node->type == HFS_NODE_LEAF) {
0192         tree->leaf_count--;
0193         mark_inode_dirty(tree->inode);
0194     }
0195     hfs_bnode_dump(node);
0196     hfs_dbg(BNODE_MOD, "remove_rec: %d, %d\n",
0197         fd->record, fd->keylength + fd->entrylength);
0198     if (!--node->num_recs) {
0199         hfs_bnode_unlink(node);
0200         if (!node->parent)
0201             return 0;
0202         parent = hfs_bnode_find(tree, node->parent);
0203         if (IS_ERR(parent))
0204             return PTR_ERR(parent);
0205         hfs_bnode_put(node);
0206         node = fd->bnode = parent;
0207 
0208         __hfs_brec_find(node, fd, hfs_find_rec_by_key);
0209         goto again;
0210     }
0211     hfs_bnode_write_u16(node,
0212         offsetof(struct hfs_bnode_desc, num_recs),
0213         node->num_recs);
0214 
0215     if (rec_off == end_off)
0216         goto skip;
0217     size = fd->keylength + fd->entrylength;
0218 
0219     do {
0220         data_off = hfs_bnode_read_u16(node, rec_off);
0221         hfs_bnode_write_u16(node, rec_off + 2, data_off - size);
0222         rec_off -= 2;
0223     } while (rec_off >= end_off);
0224 
0225     /* fill hole */
0226     hfs_bnode_move(node, fd->keyoffset, fd->keyoffset + size,
0227                data_off - fd->keyoffset - size);
0228 skip:
0229     hfs_bnode_dump(node);
0230     if (!fd->record)
0231         hfs_brec_update_parent(fd);
0232     return 0;
0233 }
0234 
0235 static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
0236 {
0237     struct hfs_btree *tree;
0238     struct hfs_bnode *node, *new_node, *next_node;
0239     struct hfs_bnode_desc node_desc;
0240     int num_recs, new_rec_off, new_off, old_rec_off;
0241     int data_start, data_end, size;
0242 
0243     tree = fd->tree;
0244     node = fd->bnode;
0245     new_node = hfs_bmap_alloc(tree);
0246     if (IS_ERR(new_node))
0247         return new_node;
0248     hfs_bnode_get(node);
0249     hfs_dbg(BNODE_MOD, "split_nodes: %d - %d - %d\n",
0250         node->this, new_node->this, node->next);
0251     new_node->next = node->next;
0252     new_node->prev = node->this;
0253     new_node->parent = node->parent;
0254     new_node->type = node->type;
0255     new_node->height = node->height;
0256 
0257     if (node->next)
0258         next_node = hfs_bnode_find(tree, node->next);
0259     else
0260         next_node = NULL;
0261 
0262     if (IS_ERR(next_node)) {
0263         hfs_bnode_put(node);
0264         hfs_bnode_put(new_node);
0265         return next_node;
0266     }
0267 
0268     size = tree->node_size / 2 - node->num_recs * 2 - 14;
0269     old_rec_off = tree->node_size - 4;
0270     num_recs = 1;
0271     for (;;) {
0272         data_start = hfs_bnode_read_u16(node, old_rec_off);
0273         if (data_start > size)
0274             break;
0275         old_rec_off -= 2;
0276         if (++num_recs < node->num_recs)
0277             continue;
0278         /* panic? */
0279         hfs_bnode_put(node);
0280         hfs_bnode_put(new_node);
0281         if (next_node)
0282             hfs_bnode_put(next_node);
0283         return ERR_PTR(-ENOSPC);
0284     }
0285 
0286     if (fd->record + 1 < num_recs) {
0287         /* new record is in the lower half,
0288          * so leave some more space there
0289          */
0290         old_rec_off += 2;
0291         num_recs--;
0292         data_start = hfs_bnode_read_u16(node, old_rec_off);
0293     } else {
0294         hfs_bnode_put(node);
0295         hfs_bnode_get(new_node);
0296         fd->bnode = new_node;
0297         fd->record -= num_recs;
0298         fd->keyoffset -= data_start - 14;
0299         fd->entryoffset -= data_start - 14;
0300     }
0301     new_node->num_recs = node->num_recs - num_recs;
0302     node->num_recs = num_recs;
0303 
0304     new_rec_off = tree->node_size - 2;
0305     new_off = 14;
0306     size = data_start - new_off;
0307     num_recs = new_node->num_recs;
0308     data_end = data_start;
0309     while (num_recs) {
0310         hfs_bnode_write_u16(new_node, new_rec_off, new_off);
0311         old_rec_off -= 2;
0312         new_rec_off -= 2;
0313         data_end = hfs_bnode_read_u16(node, old_rec_off);
0314         new_off = data_end - size;
0315         num_recs--;
0316     }
0317     hfs_bnode_write_u16(new_node, new_rec_off, new_off);
0318     hfs_bnode_copy(new_node, 14, node, data_start, data_end - data_start);
0319 
0320     /* update new bnode header */
0321     node_desc.next = cpu_to_be32(new_node->next);
0322     node_desc.prev = cpu_to_be32(new_node->prev);
0323     node_desc.type = new_node->type;
0324     node_desc.height = new_node->height;
0325     node_desc.num_recs = cpu_to_be16(new_node->num_recs);
0326     node_desc.reserved = 0;
0327     hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));
0328 
0329     /* update previous bnode header */
0330     node->next = new_node->this;
0331     hfs_bnode_read(node, &node_desc, 0, sizeof(node_desc));
0332     node_desc.next = cpu_to_be32(node->next);
0333     node_desc.num_recs = cpu_to_be16(node->num_recs);
0334     hfs_bnode_write(node, &node_desc, 0, sizeof(node_desc));
0335 
0336     /* update next bnode header */
0337     if (next_node) {
0338         next_node->prev = new_node->this;
0339         hfs_bnode_read(next_node, &node_desc, 0, sizeof(node_desc));
0340         node_desc.prev = cpu_to_be32(next_node->prev);
0341         hfs_bnode_write(next_node, &node_desc, 0, sizeof(node_desc));
0342         hfs_bnode_put(next_node);
0343     } else if (node->this == tree->leaf_tail) {
0344         /* if there is no next node, this might be the new tail */
0345         tree->leaf_tail = new_node->this;
0346         mark_inode_dirty(tree->inode);
0347     }
0348 
0349     hfs_bnode_dump(node);
0350     hfs_bnode_dump(new_node);
0351     hfs_bnode_put(node);
0352 
0353     return new_node;
0354 }
0355 
0356 static int hfs_brec_update_parent(struct hfs_find_data *fd)
0357 {
0358     struct hfs_btree *tree;
0359     struct hfs_bnode *node, *new_node, *parent;
0360     int newkeylen, diff;
0361     int rec, rec_off, end_rec_off;
0362     int start_off, end_off;
0363 
0364     tree = fd->tree;
0365     node = fd->bnode;
0366     new_node = NULL;
0367     if (!node->parent)
0368         return 0;
0369 
0370 again:
0371     parent = hfs_bnode_find(tree, node->parent);
0372     if (IS_ERR(parent))
0373         return PTR_ERR(parent);
0374     __hfs_brec_find(parent, fd, hfs_find_rec_by_key);
0375     if (fd->record < 0)
0376         return -ENOENT;
0377     hfs_bnode_dump(parent);
0378     rec = fd->record;
0379 
0380     /* size difference between old and new key */
0381     if ((tree->attributes & HFS_TREE_VARIDXKEYS) ||
0382                 (tree->cnid == HFSPLUS_ATTR_CNID))
0383         newkeylen = hfs_bnode_read_u16(node, 14) + 2;
0384     else
0385         fd->keylength = newkeylen = tree->max_key_len + 2;
0386     hfs_dbg(BNODE_MOD, "update_rec: %d, %d, %d\n",
0387         rec, fd->keylength, newkeylen);
0388 
0389     rec_off = tree->node_size - (rec + 2) * 2;
0390     end_rec_off = tree->node_size - (parent->num_recs + 1) * 2;
0391     diff = newkeylen - fd->keylength;
0392     if (!diff)
0393         goto skip;
0394     if (diff > 0) {
0395         end_off = hfs_bnode_read_u16(parent, end_rec_off);
0396         if (end_rec_off - end_off < diff) {
0397 
0398             hfs_dbg(BNODE_MOD, "splitting index node\n");
0399             fd->bnode = parent;
0400             new_node = hfs_bnode_split(fd);
0401             if (IS_ERR(new_node))
0402                 return PTR_ERR(new_node);
0403             parent = fd->bnode;
0404             rec = fd->record;
0405             rec_off = tree->node_size - (rec + 2) * 2;
0406             end_rec_off = tree->node_size -
0407                 (parent->num_recs + 1) * 2;
0408         }
0409     }
0410 
0411     end_off = start_off = hfs_bnode_read_u16(parent, rec_off);
0412     hfs_bnode_write_u16(parent, rec_off, start_off + diff);
0413     start_off -= 4; /* move previous cnid too */
0414 
0415     while (rec_off > end_rec_off) {
0416         rec_off -= 2;
0417         end_off = hfs_bnode_read_u16(parent, rec_off);
0418         hfs_bnode_write_u16(parent, rec_off, end_off + diff);
0419     }
0420     hfs_bnode_move(parent, start_off + diff, start_off,
0421                end_off - start_off);
0422 skip:
0423     hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen);
0424     hfs_bnode_dump(parent);
0425 
0426     hfs_bnode_put(node);
0427     node = parent;
0428 
0429     if (new_node) {
0430         __be32 cnid;
0431 
0432         if (!new_node->parent) {
0433             hfs_btree_inc_height(tree);
0434             new_node->parent = tree->root;
0435         }
0436         fd->bnode = hfs_bnode_find(tree, new_node->parent);
0437         /* create index key and entry */
0438         hfs_bnode_read_key(new_node, fd->search_key, 14);
0439         cnid = cpu_to_be32(new_node->this);
0440 
0441         __hfs_brec_find(fd->bnode, fd, hfs_find_rec_by_key);
0442         hfs_brec_insert(fd, &cnid, sizeof(cnid));
0443         hfs_bnode_put(fd->bnode);
0444         hfs_bnode_put(new_node);
0445 
0446         if (!rec) {
0447             if (new_node == node)
0448                 goto out;
0449             /* restore search_key */
0450             hfs_bnode_read_key(node, fd->search_key, 14);
0451         }
0452         new_node = NULL;
0453     }
0454 
0455     if (!rec && node->parent)
0456         goto again;
0457 out:
0458     fd->bnode = node;
0459     return 0;
0460 }
0461 
0462 static int hfs_btree_inc_height(struct hfs_btree *tree)
0463 {
0464     struct hfs_bnode *node, *new_node;
0465     struct hfs_bnode_desc node_desc;
0466     int key_size, rec;
0467     __be32 cnid;
0468 
0469     node = NULL;
0470     if (tree->root) {
0471         node = hfs_bnode_find(tree, tree->root);
0472         if (IS_ERR(node))
0473             return PTR_ERR(node);
0474     }
0475     new_node = hfs_bmap_alloc(tree);
0476     if (IS_ERR(new_node)) {
0477         hfs_bnode_put(node);
0478         return PTR_ERR(new_node);
0479     }
0480 
0481     tree->root = new_node->this;
0482     if (!tree->depth) {
0483         tree->leaf_head = tree->leaf_tail = new_node->this;
0484         new_node->type = HFS_NODE_LEAF;
0485         new_node->num_recs = 0;
0486     } else {
0487         new_node->type = HFS_NODE_INDEX;
0488         new_node->num_recs = 1;
0489     }
0490     new_node->parent = 0;
0491     new_node->next = 0;
0492     new_node->prev = 0;
0493     new_node->height = ++tree->depth;
0494 
0495     node_desc.next = cpu_to_be32(new_node->next);
0496     node_desc.prev = cpu_to_be32(new_node->prev);
0497     node_desc.type = new_node->type;
0498     node_desc.height = new_node->height;
0499     node_desc.num_recs = cpu_to_be16(new_node->num_recs);
0500     node_desc.reserved = 0;
0501     hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));
0502 
0503     rec = tree->node_size - 2;
0504     hfs_bnode_write_u16(new_node, rec, 14);
0505 
0506     if (node) {
0507         /* insert old root idx into new root */
0508         node->parent = tree->root;
0509         if (node->type == HFS_NODE_LEAF ||
0510                 tree->attributes & HFS_TREE_VARIDXKEYS ||
0511                 tree->cnid == HFSPLUS_ATTR_CNID)
0512             key_size = hfs_bnode_read_u16(node, 14) + 2;
0513         else
0514             key_size = tree->max_key_len + 2;
0515         hfs_bnode_copy(new_node, 14, node, 14, key_size);
0516 
0517         if (!(tree->attributes & HFS_TREE_VARIDXKEYS) &&
0518                 (tree->cnid != HFSPLUS_ATTR_CNID)) {
0519             key_size = tree->max_key_len + 2;
0520             hfs_bnode_write_u16(new_node, 14, tree->max_key_len);
0521         }
0522         cnid = cpu_to_be32(node->this);
0523         hfs_bnode_write(new_node, &cnid, 14 + key_size, 4);
0524 
0525         rec -= 2;
0526         hfs_bnode_write_u16(new_node, rec, 14 + key_size + 4);
0527 
0528         hfs_bnode_put(node);
0529     }
0530     hfs_bnode_put(new_node);
0531     mark_inode_dirty(tree->inode);
0532 
0533     return 0;
0534 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!