~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/hfs/brec.c

Version: ~ [ linux-5.2-rc4 ] ~ [ linux-5.1.9 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.50 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.125 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.181 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.181 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.68 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.39.4 ] ~ [ linux-2.6.38.8 ] ~ [ linux-2.6.37.6 ] ~ [ linux-2.6.36.4 ] ~ [ linux-2.6.35.14 ] ~ [ linux-2.6.34.15 ] ~ [ linux-2.6.33.20 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /*
  2  *  linux/fs/hfs/brec.c
  3  *
  4  * Copyright (C) 2001
  5  * Brad Boyer (flar@allandria.com)
  6  * (C) 2003 Ardis Technologies <roman@ardistech.com>
  7  *
  8  * Handle individual btree records
  9  */
 10 
 11 #include "btree.h"
 12 
 13 static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd);
 14 static int hfs_brec_update_parent(struct hfs_find_data *fd);
 15 static int hfs_btree_inc_height(struct hfs_btree *tree);
 16 
 17 /* Get the length and offset of the given record in the given node */
 18 u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off)
 19 {
 20         __be16 retval[2];
 21         u16 dataoff;
 22 
 23         dataoff = node->tree->node_size - (rec + 2) * 2;
 24         hfs_bnode_read(node, retval, dataoff, 4);
 25         *off = be16_to_cpu(retval[1]);
 26         return be16_to_cpu(retval[0]) - *off;
 27 }
 28 
 29 /* Get the length of the key from a keyed record */
 30 u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec)
 31 {
 32         u16 retval, recoff;
 33 
 34         if (node->type != HFS_NODE_INDEX && node->type != HFS_NODE_LEAF)
 35                 return 0;
 36 
 37         if ((node->type == HFS_NODE_INDEX) &&
 38            !(node->tree->attributes & HFS_TREE_VARIDXKEYS)) {
 39                 if (node->tree->attributes & HFS_TREE_BIGKEYS)
 40                         retval = node->tree->max_key_len + 2;
 41                 else
 42                         retval = node->tree->max_key_len + 1;
 43         } else {
 44                 recoff = hfs_bnode_read_u16(node, node->tree->node_size - (rec + 1) * 2);
 45                 if (!recoff)
 46                         return 0;
 47                 if (node->tree->attributes & HFS_TREE_BIGKEYS) {
 48                         retval = hfs_bnode_read_u16(node, recoff) + 2;
 49                         if (retval > node->tree->max_key_len + 2) {
 50                                 pr_err("keylen %d too large\n", retval);
 51                                 retval = 0;
 52                         }
 53                 } else {
 54                         retval = (hfs_bnode_read_u8(node, recoff) | 1) + 1;
 55                         if (retval > node->tree->max_key_len + 1) {
 56                                 pr_err("keylen %d too large\n", retval);
 57                                 retval = 0;
 58                         }
 59                 }
 60         }
 61         return retval;
 62 }
 63 
 64 int hfs_brec_insert(struct hfs_find_data *fd, void *entry, int entry_len)
 65 {
 66         struct hfs_btree *tree;
 67         struct hfs_bnode *node, *new_node;
 68         int size, key_len, rec;
 69         int data_off, end_off;
 70         int idx_rec_off, data_rec_off, end_rec_off;
 71         __be32 cnid;
 72 
 73         tree = fd->tree;
 74         if (!fd->bnode) {
 75                 if (!tree->root)
 76                         hfs_btree_inc_height(tree);
 77                 fd->bnode = hfs_bnode_find(tree, tree->leaf_head);
 78                 if (IS_ERR(fd->bnode))
 79                         return PTR_ERR(fd->bnode);
 80                 fd->record = -1;
 81         }
 82         new_node = NULL;
 83         key_len = (fd->search_key->key_len | 1) + 1;
 84 again:
 85         /* new record idx and complete record size */
 86         rec = fd->record + 1;
 87         size = key_len + entry_len;
 88 
 89         node = fd->bnode;
 90         hfs_bnode_dump(node);
 91         /* get last offset */
 92         end_rec_off = tree->node_size - (node->num_recs + 1) * 2;
 93         end_off = hfs_bnode_read_u16(node, end_rec_off);
 94         end_rec_off -= 2;
 95         hfs_dbg(BNODE_MOD, "insert_rec: %d, %d, %d, %d\n",
 96                 rec, size, end_off, end_rec_off);
 97         if (size > end_rec_off - end_off) {
 98                 if (new_node)
 99                         panic("not enough room!\n");
100                 new_node = hfs_bnode_split(fd);
101                 if (IS_ERR(new_node))
102                         return PTR_ERR(new_node);
103                 goto again;
104         }
105         if (node->type == HFS_NODE_LEAF) {
106                 tree->leaf_count++;
107                 mark_inode_dirty(tree->inode);
108         }
109         node->num_recs++;
110         /* write new last offset */
111         hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs);
112         hfs_bnode_write_u16(node, end_rec_off, end_off + size);
113         data_off = end_off;
114         data_rec_off = end_rec_off + 2;
115         idx_rec_off = tree->node_size - (rec + 1) * 2;
116         if (idx_rec_off == data_rec_off)
117                 goto skip;
118         /* move all following entries */
119         do {
120                 data_off = hfs_bnode_read_u16(node, data_rec_off + 2);
121                 hfs_bnode_write_u16(node, data_rec_off, data_off + size);
122                 data_rec_off += 2;
123         } while (data_rec_off < idx_rec_off);
124 
125         /* move data away */
126         hfs_bnode_move(node, data_off + size, data_off,
127                        end_off - data_off);
128 
129 skip:
130         hfs_bnode_write(node, fd->search_key, data_off, key_len);
131         hfs_bnode_write(node, entry, data_off + key_len, entry_len);
132         hfs_bnode_dump(node);
133 
134         if (new_node) {
135                 /* update parent key if we inserted a key
136                  * at the start of the first node
137                  */
138                 if (!rec && new_node != node)
139                         hfs_brec_update_parent(fd);
140 
141                 hfs_bnode_put(fd->bnode);
142                 if (!new_node->parent) {
143                         hfs_btree_inc_height(tree);
144                         new_node->parent = tree->root;
145                 }
146                 fd->bnode = hfs_bnode_find(tree, new_node->parent);
147 
148                 /* create index data entry */
149                 cnid = cpu_to_be32(new_node->this);
150                 entry = &cnid;
151                 entry_len = sizeof(cnid);
152 
153                 /* get index key */
154                 hfs_bnode_read_key(new_node, fd->search_key, 14);
155                 __hfs_brec_find(fd->bnode, fd);
156 
157                 hfs_bnode_put(new_node);
158                 new_node = NULL;
159 
160                 if (tree->attributes & HFS_TREE_VARIDXKEYS)
161                         key_len = fd->search_key->key_len + 1;
162                 else {
163                         fd->search_key->key_len = tree->max_key_len;
164                         key_len = tree->max_key_len + 1;
165                 }
166                 goto again;
167         }
168 
169         if (!rec)
170                 hfs_brec_update_parent(fd);
171 
172         return 0;
173 }
174 
175 int hfs_brec_remove(struct hfs_find_data *fd)
176 {
177         struct hfs_btree *tree;
178         struct hfs_bnode *node, *parent;
179         int end_off, rec_off, data_off, size;
180 
181         tree = fd->tree;
182         node = fd->bnode;
183 again:
184         rec_off = tree->node_size - (fd->record + 2) * 2;
185         end_off = tree->node_size - (node->num_recs + 1) * 2;
186 
187         if (node->type == HFS_NODE_LEAF) {
188                 tree->leaf_count--;
189                 mark_inode_dirty(tree->inode);
190         }
191         hfs_bnode_dump(node);
192         hfs_dbg(BNODE_MOD, "remove_rec: %d, %d\n",
193                 fd->record, fd->keylength + fd->entrylength);
194         if (!--node->num_recs) {
195                 hfs_bnode_unlink(node);
196                 if (!node->parent)
197                         return 0;
198                 parent = hfs_bnode_find(tree, node->parent);
199                 if (IS_ERR(parent))
200                         return PTR_ERR(parent);
201                 hfs_bnode_put(node);
202                 node = fd->bnode = parent;
203 
204                 __hfs_brec_find(node, fd);
205                 goto again;
206         }
207         hfs_bnode_write_u16(node, offsetof(struct hfs_bnode_desc, num_recs), node->num_recs);
208 
209         if (rec_off == end_off)
210                 goto skip;
211         size = fd->keylength + fd->entrylength;
212 
213         do {
214                 data_off = hfs_bnode_read_u16(node, rec_off);
215                 hfs_bnode_write_u16(node, rec_off + 2, data_off - size);
216                 rec_off -= 2;
217         } while (rec_off >= end_off);
218 
219         /* fill hole */
220         hfs_bnode_move(node, fd->keyoffset, fd->keyoffset + size,
221                        data_off - fd->keyoffset - size);
222 skip:
223         hfs_bnode_dump(node);
224         if (!fd->record)
225                 hfs_brec_update_parent(fd);
226         return 0;
227 }
228 
229 static struct hfs_bnode *hfs_bnode_split(struct hfs_find_data *fd)
230 {
231         struct hfs_btree *tree;
232         struct hfs_bnode *node, *new_node, *next_node;
233         struct hfs_bnode_desc node_desc;
234         int num_recs, new_rec_off, new_off, old_rec_off;
235         int data_start, data_end, size;
236 
237         tree = fd->tree;
238         node = fd->bnode;
239         new_node = hfs_bmap_alloc(tree);
240         if (IS_ERR(new_node))
241                 return new_node;
242         hfs_bnode_get(node);
243         hfs_dbg(BNODE_MOD, "split_nodes: %d - %d - %d\n",
244                 node->this, new_node->this, node->next);
245         new_node->next = node->next;
246         new_node->prev = node->this;
247         new_node->parent = node->parent;
248         new_node->type = node->type;
249         new_node->height = node->height;
250 
251         if (node->next)
252                 next_node = hfs_bnode_find(tree, node->next);
253         else
254                 next_node = NULL;
255 
256         if (IS_ERR(next_node)) {
257                 hfs_bnode_put(node);
258                 hfs_bnode_put(new_node);
259                 return next_node;
260         }
261 
262         size = tree->node_size / 2 - node->num_recs * 2 - 14;
263         old_rec_off = tree->node_size - 4;
264         num_recs = 1;
265         for (;;) {
266                 data_start = hfs_bnode_read_u16(node, old_rec_off);
267                 if (data_start > size)
268                         break;
269                 old_rec_off -= 2;
270                 if (++num_recs < node->num_recs)
271                         continue;
272                 /* panic? */
273                 hfs_bnode_put(node);
274                 hfs_bnode_put(new_node);
275                 if (next_node)
276                         hfs_bnode_put(next_node);
277                 return ERR_PTR(-ENOSPC);
278         }
279 
280         if (fd->record + 1 < num_recs) {
281                 /* new record is in the lower half,
282                  * so leave some more space there
283                  */
284                 old_rec_off += 2;
285                 num_recs--;
286                 data_start = hfs_bnode_read_u16(node, old_rec_off);
287         } else {
288                 hfs_bnode_put(node);
289                 hfs_bnode_get(new_node);
290                 fd->bnode = new_node;
291                 fd->record -= num_recs;
292                 fd->keyoffset -= data_start - 14;
293                 fd->entryoffset -= data_start - 14;
294         }
295         new_node->num_recs = node->num_recs - num_recs;
296         node->num_recs = num_recs;
297 
298         new_rec_off = tree->node_size - 2;
299         new_off = 14;
300         size = data_start - new_off;
301         num_recs = new_node->num_recs;
302         data_end = data_start;
303         while (num_recs) {
304                 hfs_bnode_write_u16(new_node, new_rec_off, new_off);
305                 old_rec_off -= 2;
306                 new_rec_off -= 2;
307                 data_end = hfs_bnode_read_u16(node, old_rec_off);
308                 new_off = data_end - size;
309                 num_recs--;
310         }
311         hfs_bnode_write_u16(new_node, new_rec_off, new_off);
312         hfs_bnode_copy(new_node, 14, node, data_start, data_end - data_start);
313 
314         /* update new bnode header */
315         node_desc.next = cpu_to_be32(new_node->next);
316         node_desc.prev = cpu_to_be32(new_node->prev);
317         node_desc.type = new_node->type;
318         node_desc.height = new_node->height;
319         node_desc.num_recs = cpu_to_be16(new_node->num_recs);
320         node_desc.reserved = 0;
321         hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));
322 
323         /* update previous bnode header */
324         node->next = new_node->this;
325         hfs_bnode_read(node, &node_desc, 0, sizeof(node_desc));
326         node_desc.next = cpu_to_be32(node->next);
327         node_desc.num_recs = cpu_to_be16(node->num_recs);
328         hfs_bnode_write(node, &node_desc, 0, sizeof(node_desc));
329 
330         /* update next bnode header */
331         if (next_node) {
332                 next_node->prev = new_node->this;
333                 hfs_bnode_read(next_node, &node_desc, 0, sizeof(node_desc));
334                 node_desc.prev = cpu_to_be32(next_node->prev);
335                 hfs_bnode_write(next_node, &node_desc, 0, sizeof(node_desc));
336                 hfs_bnode_put(next_node);
337         } else if (node->this == tree->leaf_tail) {
338                 /* if there is no next node, this might be the new tail */
339                 tree->leaf_tail = new_node->this;
340                 mark_inode_dirty(tree->inode);
341         }
342 
343         hfs_bnode_dump(node);
344         hfs_bnode_dump(new_node);
345         hfs_bnode_put(node);
346 
347         return new_node;
348 }
349 
350 static int hfs_brec_update_parent(struct hfs_find_data *fd)
351 {
352         struct hfs_btree *tree;
353         struct hfs_bnode *node, *new_node, *parent;
354         int newkeylen, diff;
355         int rec, rec_off, end_rec_off;
356         int start_off, end_off;
357 
358         tree = fd->tree;
359         node = fd->bnode;
360         new_node = NULL;
361         if (!node->parent)
362                 return 0;
363 
364 again:
365         parent = hfs_bnode_find(tree, node->parent);
366         if (IS_ERR(parent))
367                 return PTR_ERR(parent);
368         __hfs_brec_find(parent, fd);
369         hfs_bnode_dump(parent);
370         rec = fd->record;
371 
372         /* size difference between old and new key */
373         if (tree->attributes & HFS_TREE_VARIDXKEYS)
374                 newkeylen = (hfs_bnode_read_u8(node, 14) | 1) + 1;
375         else
376                 fd->keylength = newkeylen = tree->max_key_len + 1;
377         hfs_dbg(BNODE_MOD, "update_rec: %d, %d, %d\n",
378                 rec, fd->keylength, newkeylen);
379 
380         rec_off = tree->node_size - (rec + 2) * 2;
381         end_rec_off = tree->node_size - (parent->num_recs + 1) * 2;
382         diff = newkeylen - fd->keylength;
383         if (!diff)
384                 goto skip;
385         if (diff > 0) {
386                 end_off = hfs_bnode_read_u16(parent, end_rec_off);
387                 if (end_rec_off - end_off < diff) {
388 
389                         printk(KERN_DEBUG "splitting index node...\n");
390                         fd->bnode = parent;
391                         new_node = hfs_bnode_split(fd);
392                         if (IS_ERR(new_node))
393                                 return PTR_ERR(new_node);
394                         parent = fd->bnode;
395                         rec = fd->record;
396                         rec_off = tree->node_size - (rec + 2) * 2;
397                         end_rec_off = tree->node_size - (parent->num_recs + 1) * 2;
398                 }
399         }
400 
401         end_off = start_off = hfs_bnode_read_u16(parent, rec_off);
402         hfs_bnode_write_u16(parent, rec_off, start_off + diff);
403         start_off -= 4; /* move previous cnid too */
404 
405         while (rec_off > end_rec_off) {
406                 rec_off -= 2;
407                 end_off = hfs_bnode_read_u16(parent, rec_off);
408                 hfs_bnode_write_u16(parent, rec_off, end_off + diff);
409         }
410         hfs_bnode_move(parent, start_off + diff, start_off,
411                        end_off - start_off);
412 skip:
413         hfs_bnode_copy(parent, fd->keyoffset, node, 14, newkeylen);
414         if (!(tree->attributes & HFS_TREE_VARIDXKEYS))
415                 hfs_bnode_write_u8(parent, fd->keyoffset, newkeylen - 1);
416         hfs_bnode_dump(parent);
417 
418         hfs_bnode_put(node);
419         node = parent;
420 
421         if (new_node) {
422                 __be32 cnid;
423 
424                 fd->bnode = hfs_bnode_find(tree, new_node->parent);
425                 /* create index key and entry */
426                 hfs_bnode_read_key(new_node, fd->search_key, 14);
427                 cnid = cpu_to_be32(new_node->this);
428 
429                 __hfs_brec_find(fd->bnode, fd);
430                 hfs_brec_insert(fd, &cnid, sizeof(cnid));
431                 hfs_bnode_put(fd->bnode);
432                 hfs_bnode_put(new_node);
433 
434                 if (!rec) {
435                         if (new_node == node)
436                                 goto out;
437                         /* restore search_key */
438                         hfs_bnode_read_key(node, fd->search_key, 14);
439                 }
440         }
441 
442         if (!rec && node->parent)
443                 goto again;
444 out:
445         fd->bnode = node;
446         return 0;
447 }
448 
449 static int hfs_btree_inc_height(struct hfs_btree *tree)
450 {
451         struct hfs_bnode *node, *new_node;
452         struct hfs_bnode_desc node_desc;
453         int key_size, rec;
454         __be32 cnid;
455 
456         node = NULL;
457         if (tree->root) {
458                 node = hfs_bnode_find(tree, tree->root);
459                 if (IS_ERR(node))
460                         return PTR_ERR(node);
461         }
462         new_node = hfs_bmap_alloc(tree);
463         if (IS_ERR(new_node)) {
464                 hfs_bnode_put(node);
465                 return PTR_ERR(new_node);
466         }
467 
468         tree->root = new_node->this;
469         if (!tree->depth) {
470                 tree->leaf_head = tree->leaf_tail = new_node->this;
471                 new_node->type = HFS_NODE_LEAF;
472                 new_node->num_recs = 0;
473         } else {
474                 new_node->type = HFS_NODE_INDEX;
475                 new_node->num_recs = 1;
476         }
477         new_node->parent = 0;
478         new_node->next = 0;
479         new_node->prev = 0;
480         new_node->height = ++tree->depth;
481 
482         node_desc.next = cpu_to_be32(new_node->next);
483         node_desc.prev = cpu_to_be32(new_node->prev);
484         node_desc.type = new_node->type;
485         node_desc.height = new_node->height;
486         node_desc.num_recs = cpu_to_be16(new_node->num_recs);
487         node_desc.reserved = 0;
488         hfs_bnode_write(new_node, &node_desc, 0, sizeof(node_desc));
489 
490         rec = tree->node_size - 2;
491         hfs_bnode_write_u16(new_node, rec, 14);
492 
493         if (node) {
494                 /* insert old root idx into new root */
495                 node->parent = tree->root;
496                 if (node->type == HFS_NODE_LEAF ||
497                     tree->attributes & HFS_TREE_VARIDXKEYS)
498                         key_size = hfs_bnode_read_u8(node, 14) + 1;
499                 else
500                         key_size = tree->max_key_len + 1;
501                 hfs_bnode_copy(new_node, 14, node, 14, key_size);
502 
503                 if (!(tree->attributes & HFS_TREE_VARIDXKEYS)) {
504                         key_size = tree->max_key_len + 1;
505                         hfs_bnode_write_u8(new_node, 14, tree->max_key_len);
506                 }
507                 key_size = (key_size + 1) & -2;
508                 cnid = cpu_to_be32(node->this);
509                 hfs_bnode_write(new_node, &cnid, 14 + key_size, 4);
510 
511                 rec -= 2;
512                 hfs_bnode_write_u16(new_node, rec, 14 + key_size + 4);
513 
514                 hfs_bnode_put(node);
515         }
516         hfs_bnode_put(new_node);
517         mark_inode_dirty(tree->inode);
518 
519         return 0;
520 }
521 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp