1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#include <linux/kernel.h>
25#include <linux/string.h>
26#include <linux/slab.h>
27#include <linux/mm.h>
28#include <linux/buffer_head.h>
29
30#include "befs.h"
31#include "btree.h"
32#include "datastream.h"
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81struct befs_btree_node {
82 befs_host_btree_nodehead head;
83 struct buffer_head *bh;
84 befs_btree_nodehead *od_node;
85};
86
87
88static const befs_off_t BEFS_BT_INVAL = 0xffffffffffffffffULL;
89
90
91static int befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
92 befs_btree_super * bt_super,
93 struct befs_btree_node *this_node,
94 befs_off_t * node_off);
95
96static int befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds,
97 befs_btree_super * sup);
98
99static int befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
100 struct befs_btree_node *node,
101 befs_off_t node_off);
102
103static int befs_leafnode(struct befs_btree_node *node);
104
105static fs16 *befs_bt_keylen_index(struct befs_btree_node *node);
106
107static fs64 *befs_bt_valarray(struct befs_btree_node *node);
108
109static char *befs_bt_keydata(struct befs_btree_node *node);
110
111static int befs_find_key(struct super_block *sb,
112 struct befs_btree_node *node,
113 const char *findkey, befs_off_t * value);
114
115static char *befs_bt_get_key(struct super_block *sb,
116 struct befs_btree_node *node,
117 int index, u16 * keylen);
118
119static int befs_compare_strings(const void *key1, int keylen1,
120 const void *key2, int keylen2);
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136static int
137befs_bt_read_super(struct super_block *sb, const befs_data_stream *ds,
138 befs_btree_super * sup)
139{
140 struct buffer_head *bh;
141 befs_disk_btree_super *od_sup;
142
143 befs_debug(sb, "---> %s", __func__);
144
145 bh = befs_read_datastream(sb, ds, 0, NULL);
146
147 if (!bh) {
148 befs_error(sb, "Couldn't read index header.");
149 goto error;
150 }
151 od_sup = (befs_disk_btree_super *) bh->b_data;
152 befs_dump_index_entry(sb, od_sup);
153
154 sup->magic = fs32_to_cpu(sb, od_sup->magic);
155 sup->node_size = fs32_to_cpu(sb, od_sup->node_size);
156 sup->max_depth = fs32_to_cpu(sb, od_sup->max_depth);
157 sup->data_type = fs32_to_cpu(sb, od_sup->data_type);
158 sup->root_node_ptr = fs64_to_cpu(sb, od_sup->root_node_ptr);
159
160 brelse(bh);
161 if (sup->magic != BEFS_BTREE_MAGIC) {
162 befs_error(sb, "Index header has bad magic.");
163 goto error;
164 }
165
166 befs_debug(sb, "<--- %s", __func__);
167 return BEFS_OK;
168
169 error:
170 befs_debug(sb, "<--- %s ERROR", __func__);
171 return BEFS_ERR;
172}
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193static int
194befs_bt_read_node(struct super_block *sb, const befs_data_stream *ds,
195 struct befs_btree_node *node, befs_off_t node_off)
196{
197 uint off = 0;
198
199 befs_debug(sb, "---> %s", __func__);
200
201 if (node->bh)
202 brelse(node->bh);
203
204 node->bh = befs_read_datastream(sb, ds, node_off, &off);
205 if (!node->bh) {
206 befs_error(sb, "%s failed to read "
207 "node at %llu", __func__, node_off);
208 befs_debug(sb, "<--- %s ERROR", __func__);
209
210 return BEFS_ERR;
211 }
212 node->od_node =
213 (befs_btree_nodehead *) ((void *) node->bh->b_data + off);
214
215 befs_dump_index_node(sb, node->od_node);
216
217 node->head.left = fs64_to_cpu(sb, node->od_node->left);
218 node->head.right = fs64_to_cpu(sb, node->od_node->right);
219 node->head.overflow = fs64_to_cpu(sb, node->od_node->overflow);
220 node->head.all_key_count =
221 fs16_to_cpu(sb, node->od_node->all_key_count);
222 node->head.all_key_length =
223 fs16_to_cpu(sb, node->od_node->all_key_length);
224
225 befs_debug(sb, "<--- %s", __func__);
226 return BEFS_OK;
227}
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247int
248befs_btree_find(struct super_block *sb, const befs_data_stream *ds,
249 const char *key, befs_off_t * value)
250{
251 struct befs_btree_node *this_node;
252 befs_btree_super bt_super;
253 befs_off_t node_off;
254 int res;
255
256 befs_debug(sb, "---> %s Key: %s", __func__, key);
257
258 if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
259 befs_error(sb,
260 "befs_btree_find() failed to read index superblock");
261 goto error;
262 }
263
264 this_node = kmalloc(sizeof(struct befs_btree_node),
265 GFP_NOFS);
266 if (!this_node) {
267 befs_error(sb, "befs_btree_find() failed to allocate %zu "
268 "bytes of memory", sizeof(struct befs_btree_node));
269 goto error;
270 }
271
272 this_node->bh = NULL;
273
274
275 node_off = bt_super.root_node_ptr;
276 if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
277 befs_error(sb, "befs_btree_find() failed to read "
278 "node at %llu", node_off);
279 goto error_alloc;
280 }
281
282 while (!befs_leafnode(this_node)) {
283 res = befs_find_key(sb, this_node, key, &node_off);
284
285 if (res == BEFS_BT_OVERFLOW)
286 node_off = this_node->head.overflow;
287 if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
288 befs_error(sb, "befs_btree_find() failed to read "
289 "node at %llu", node_off);
290 goto error_alloc;
291 }
292 }
293
294
295 res = befs_find_key(sb, this_node, key, value);
296
297 brelse(this_node->bh);
298 kfree(this_node);
299
300 if (res != BEFS_BT_MATCH) {
301 befs_error(sb, "<--- %s Key %s not found", __func__, key);
302 befs_debug(sb, "<--- %s ERROR", __func__);
303 *value = 0;
304 return BEFS_BT_NOT_FOUND;
305 }
306 befs_debug(sb, "<--- %s Found key %s, value %llu", __func__,
307 key, *value);
308 return BEFS_OK;
309
310 error_alloc:
311 kfree(this_node);
312 error:
313 *value = 0;
314 befs_debug(sb, "<--- %s ERROR", __func__);
315 return BEFS_ERR;
316}
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332static int
333befs_find_key(struct super_block *sb, struct befs_btree_node *node,
334 const char *findkey, befs_off_t * value)
335{
336 int first, last, mid;
337 int eq;
338 u16 keylen;
339 int findkey_len;
340 char *thiskey;
341 fs64 *valarray;
342
343 befs_debug(sb, "---> %s %s", __func__, findkey);
344
345 findkey_len = strlen(findkey);
346
347
348 last = node->head.all_key_count - 1;
349 thiskey = befs_bt_get_key(sb, node, last, &keylen);
350
351 eq = befs_compare_strings(thiskey, keylen, findkey, findkey_len);
352 if (eq < 0) {
353 befs_debug(sb, "<--- node can't contain %s", findkey);
354 return BEFS_BT_OVERFLOW;
355 }
356
357 valarray = befs_bt_valarray(node);
358
359
360 first = 0;
361 mid = 0;
362 while (last >= first) {
363 mid = (last + first) / 2;
364 befs_debug(sb, "first: %d, last: %d, mid: %d", first, last,
365 mid);
366 thiskey = befs_bt_get_key(sb, node, mid, &keylen);
367 eq = befs_compare_strings(thiskey, keylen, findkey,
368 findkey_len);
369
370 if (eq == 0) {
371 befs_debug(sb, "<--- %s found %s at %d",
372 __func__, thiskey, mid);
373
374 *value = fs64_to_cpu(sb, valarray[mid]);
375 return BEFS_BT_MATCH;
376 }
377 if (eq > 0)
378 last = mid - 1;
379 else
380 first = mid + 1;
381 }
382
383
384 if (eq < 0)
385 *value = fs64_to_cpu(sb, valarray[mid + 1]);
386 else
387 *value = fs64_to_cpu(sb, valarray[mid]);
388 befs_error(sb, "<--- %s %s not found", __func__, findkey);
389 befs_debug(sb, "<--- %s ERROR", __func__);
390 return BEFS_BT_NOT_FOUND;
391}
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413int
414befs_btree_read(struct super_block *sb, const befs_data_stream *ds,
415 loff_t key_no, size_t bufsize, char *keybuf, size_t * keysize,
416 befs_off_t * value)
417{
418 struct befs_btree_node *this_node;
419 befs_btree_super bt_super;
420 befs_off_t node_off;
421 int cur_key;
422 fs64 *valarray;
423 char *keystart;
424 u16 keylen;
425 int res;
426
427 uint key_sum = 0;
428
429 befs_debug(sb, "---> %s", __func__);
430
431 if (befs_bt_read_super(sb, ds, &bt_super) != BEFS_OK) {
432 befs_error(sb,
433 "befs_btree_read() failed to read index superblock");
434 goto error;
435 }
436
437 this_node = kmalloc(sizeof(struct befs_btree_node), GFP_NOFS);
438 if (this_node == NULL) {
439 befs_error(sb, "befs_btree_read() failed to allocate %zu "
440 "bytes of memory", sizeof(struct befs_btree_node));
441 goto error;
442 }
443
444 node_off = bt_super.root_node_ptr;
445 this_node->bh = NULL;
446
447
448 res = befs_btree_seekleaf(sb, ds, &bt_super, this_node, &node_off);
449 if (res == BEFS_BT_EMPTY) {
450 brelse(this_node->bh);
451 kfree(this_node);
452 *value = 0;
453 *keysize = 0;
454 befs_debug(sb, "<--- %s Tree is EMPTY", __func__);
455 return BEFS_BT_EMPTY;
456 } else if (res == BEFS_ERR) {
457 goto error_alloc;
458 }
459
460
461
462 while (key_sum + this_node->head.all_key_count <= key_no) {
463
464
465 if (this_node->head.right == BEFS_BT_INVAL) {
466 *keysize = 0;
467 *value = 0;
468 befs_debug(sb,
469 "<--- %s END of keys at %llu", __func__,
470 (unsigned long long)
471 key_sum + this_node->head.all_key_count);
472 brelse(this_node->bh);
473 kfree(this_node);
474 return BEFS_BT_END;
475 }
476
477 key_sum += this_node->head.all_key_count;
478 node_off = this_node->head.right;
479
480 if (befs_bt_read_node(sb, ds, this_node, node_off) != BEFS_OK) {
481 befs_error(sb, "%s failed to read node at %llu",
482 __func__, (unsigned long long)node_off);
483 goto error_alloc;
484 }
485 }
486
487
488 cur_key = key_no - key_sum;
489
490
491 valarray = befs_bt_valarray(this_node);
492
493 keystart = befs_bt_get_key(sb, this_node, cur_key, &keylen);
494
495 befs_debug(sb, "Read [%llu,%d]: keysize %d",
496 (long long unsigned int)node_off, (int)cur_key,
497 (int)keylen);
498
499 if (bufsize < keylen + 1) {
500 befs_error(sb, "%s keybuf too small (%zu) "
501 "for key of size %d", __func__, bufsize, keylen);
502 brelse(this_node->bh);
503 goto error_alloc;
504 }
505
506 strlcpy(keybuf, keystart, keylen + 1);
507 *value = fs64_to_cpu(sb, valarray[cur_key]);
508 *keysize = keylen;
509
510 befs_debug(sb, "Read [%llu,%d]: Key \"%.*s\", Value %llu", node_off,
511 cur_key, keylen, keybuf, *value);
512
513 brelse(this_node->bh);
514 kfree(this_node);
515
516 befs_debug(sb, "<--- %s", __func__);
517
518 return BEFS_OK;
519
520 error_alloc:
521 kfree(this_node);
522
523 error:
524 *keysize = 0;
525 *value = 0;
526 befs_debug(sb, "<--- %s ERROR", __func__);
527 return BEFS_ERR;
528}
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544static int
545befs_btree_seekleaf(struct super_block *sb, const befs_data_stream *ds,
546 befs_btree_super *bt_super,
547 struct befs_btree_node *this_node,
548 befs_off_t * node_off)
549{
550
551 befs_debug(sb, "---> %s", __func__);
552
553 if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
554 befs_error(sb, "%s failed to read "
555 "node at %llu", __func__, *node_off);
556 goto error;
557 }
558 befs_debug(sb, "Seekleaf to root node %llu", *node_off);
559
560 if (this_node->head.all_key_count == 0 && befs_leafnode(this_node)) {
561 befs_debug(sb, "<--- %s Tree is EMPTY", __func__);
562 return BEFS_BT_EMPTY;
563 }
564
565 while (!befs_leafnode(this_node)) {
566
567 if (this_node->head.all_key_count == 0) {
568 befs_debug(sb, "%s encountered "
569 "an empty interior node: %llu. Using Overflow "
570 "node: %llu", __func__, *node_off,
571 this_node->head.overflow);
572 *node_off = this_node->head.overflow;
573 } else {
574 fs64 *valarray = befs_bt_valarray(this_node);
575 *node_off = fs64_to_cpu(sb, valarray[0]);
576 }
577 if (befs_bt_read_node(sb, ds, this_node, *node_off) != BEFS_OK) {
578 befs_error(sb, "%s failed to read "
579 "node at %llu", __func__, *node_off);
580 goto error;
581 }
582
583 befs_debug(sb, "Seekleaf to child node %llu", *node_off);
584 }
585 befs_debug(sb, "Node %llu is a leaf node", *node_off);
586
587 return BEFS_OK;
588
589 error:
590 befs_debug(sb, "<--- %s ERROR", __func__);
591 return BEFS_ERR;
592}
593
594
595
596
597
598
599
600
601static int
602befs_leafnode(struct befs_btree_node *node)
603{
604
605 if (node->head.overflow == BEFS_BT_INVAL)
606 return 1;
607 else
608 return 0;
609}
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624static fs16 *
625befs_bt_keylen_index(struct befs_btree_node *node)
626{
627 const int keylen_align = 8;
628 unsigned long int off =
629 (sizeof (befs_btree_nodehead) + node->head.all_key_length);
630 ulong tmp = off % keylen_align;
631
632 if (tmp)
633 off += keylen_align - tmp;
634
635 return (fs16 *) ((void *) node->od_node + off);
636}
637
638
639
640
641
642
643
644
645static fs64 *
646befs_bt_valarray(struct befs_btree_node *node)
647{
648 void *keylen_index_start = (void *) befs_bt_keylen_index(node);
649 size_t keylen_index_size = node->head.all_key_count * sizeof (fs16);
650
651 return (fs64 *) (keylen_index_start + keylen_index_size);
652}
653
654
655
656
657
658
659
660
661static char *
662befs_bt_keydata(struct befs_btree_node *node)
663{
664 return (char *) ((void *) node->od_node + sizeof (befs_btree_nodehead));
665}
666
667
668
669
670
671
672
673
674
675
676
677static char *
678befs_bt_get_key(struct super_block *sb, struct befs_btree_node *node,
679 int index, u16 * keylen)
680{
681 int prev_key_end;
682 char *keystart;
683 fs16 *keylen_index;
684
685 if (index < 0 || index > node->head.all_key_count) {
686 *keylen = 0;
687 return NULL;
688 }
689
690 keystart = befs_bt_keydata(node);
691 keylen_index = befs_bt_keylen_index(node);
692
693 if (index == 0)
694 prev_key_end = 0;
695 else
696 prev_key_end = fs16_to_cpu(sb, keylen_index[index - 1]);
697
698 *keylen = fs16_to_cpu(sb, keylen_index[index]) - prev_key_end;
699
700 return keystart + prev_key_end;
701}
702
703
704
705
706
707
708
709
710
711
712
713
714static int
715befs_compare_strings(const void *key1, int keylen1,
716 const void *key2, int keylen2)
717{
718 int len = min_t(int, keylen1, keylen2);
719 int result = strncmp(key1, key2, len);
720 if (result == 0)
721 result = keylen1 - keylen2;
722 return result;
723}
724
725
726#if 0
727static int
728btree_compare_int32(cont void *key1, int keylen1, const void *key2, int keylen2)
729{
730 return *(int32_t *) key1 - *(int32_t *) key2;
731}
732
733static int
734btree_compare_uint32(cont void *key1, int keylen1,
735 const void *key2, int keylen2)
736{
737 if (*(u_int32_t *) key1 == *(u_int32_t *) key2)
738 return 0;
739 else if (*(u_int32_t *) key1 > *(u_int32_t *) key2)
740 return 1;
741
742 return -1;
743}
744static int
745btree_compare_int64(cont void *key1, int keylen1, const void *key2, int keylen2)
746{
747 if (*(int64_t *) key1 == *(int64_t *) key2)
748 return 0;
749 else if (*(int64_t *) key1 > *(int64_t *) key2)
750 return 1;
751
752 return -1;
753}
754
755static int
756btree_compare_uint64(cont void *key1, int keylen1,
757 const void *key2, int keylen2)
758{
759 if (*(u_int64_t *) key1 == *(u_int64_t *) key2)
760 return 0;
761 else if (*(u_int64_t *) key1 > *(u_int64_t *) key2)
762 return 1;
763
764 return -1;
765}
766
767static int
768btree_compare_float(cont void *key1, int keylen1, const void *key2, int keylen2)
769{
770 float result = *(float *) key1 - *(float *) key2;
771 if (result == 0.0f)
772 return 0;
773
774 return (result < 0.0f) ? -1 : 1;
775}
776
777static int
778btree_compare_double(cont void *key1, int keylen1,
779 const void *key2, int keylen2)
780{
781 double result = *(double *) key1 - *(double *) key2;
782 if (result == 0.0)
783 return 0;
784
785 return (result < 0.0) ? -1 : 1;
786}
787#endif
788