dm-btree-internal.h 3.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147
  1. /*
  2. * Copyright (C) 2011 Red Hat, Inc.
  3. *
  4. * This file is released under the GPL.
  5. */
  6. #ifndef DM_BTREE_INTERNAL_H
  7. #define DM_BTREE_INTERNAL_H
  8. #include "dm-btree.h"
  9. /*----------------------------------------------------------------*/
  10. /*
  11. * We'll need 2 accessor functions for n->csum and n->blocknr
  12. * to support dm-btree-spine.c in that case.
  13. */
  14. enum node_flags {
  15. INTERNAL_NODE = 1,
  16. LEAF_NODE = 1 << 1
  17. };
  18. /*
  19. * Every btree node begins with this structure. Make sure it's a multiple
  20. * of 8-bytes in size, otherwise the 64bit keys will be mis-aligned.
  21. */
  22. struct node_header {
  23. __le32 csum;
  24. __le32 flags;
  25. __le64 blocknr; /* Block this node is supposed to live in. */
  26. __le32 nr_entries;
  27. __le32 max_entries;
  28. __le32 value_size;
  29. __le32 padding;
  30. } __attribute__((packed, aligned(8)));
  31. struct btree_node {
  32. struct node_header header;
  33. __le64 keys[];
  34. } __attribute__((packed, aligned(8)));
  35. /*
  36. * Locks a block using the btree node validator.
  37. */
  38. int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
  39. struct dm_block **result);
  40. void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
  41. struct dm_btree_value_type *vt);
  42. int new_block(struct dm_btree_info *info, struct dm_block **result);
  43. void unlock_block(struct dm_btree_info *info, struct dm_block *b);
  44. /*
  45. * Spines keep track of the rolling locks. There are 2 variants, read-only
  46. * and one that uses shadowing. These are separate structs to allow the
  47. * type checker to spot misuse, for example accidentally calling read_lock
  48. * on a shadow spine.
  49. */
  50. struct ro_spine {
  51. struct dm_btree_info *info;
  52. int count;
  53. struct dm_block *nodes[2];
  54. };
  55. void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
  56. void exit_ro_spine(struct ro_spine *s);
  57. int ro_step(struct ro_spine *s, dm_block_t new_child);
  58. void ro_pop(struct ro_spine *s);
  59. struct btree_node *ro_node(struct ro_spine *s);
  60. struct shadow_spine {
  61. struct dm_btree_info *info;
  62. int count;
  63. struct dm_block *nodes[2];
  64. dm_block_t root;
  65. };
  66. void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
  67. int exit_shadow_spine(struct shadow_spine *s);
  68. int shadow_step(struct shadow_spine *s, dm_block_t b,
  69. struct dm_btree_value_type *vt);
  70. /*
  71. * The spine must have at least one entry before calling this.
  72. */
  73. struct dm_block *shadow_current(struct shadow_spine *s);
  74. /*
  75. * The spine must have at least two entries before calling this.
  76. */
  77. struct dm_block *shadow_parent(struct shadow_spine *s);
  78. int shadow_has_parent(struct shadow_spine *s);
  79. int shadow_root(struct shadow_spine *s);
  80. /*
  81. * Some inlines.
  82. */
  83. static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
  84. {
  85. return n->keys + index;
  86. }
  87. static inline void *value_base(struct btree_node *n)
  88. {
  89. return &n->keys[le32_to_cpu(n->header.max_entries)];
  90. }
  91. static inline void *value_ptr(struct btree_node *n, uint32_t index)
  92. {
  93. uint32_t value_size = le32_to_cpu(n->header.value_size);
  94. return value_base(n) + (value_size * index);
  95. }
  96. /*
  97. * Assumes the values are suitably-aligned and converts to core format.
  98. */
  99. static inline uint64_t value64(struct btree_node *n, uint32_t index)
  100. {
  101. __le64 *values_le = value_base(n);
  102. return le64_to_cpu(values_le[index]);
  103. }
  104. /*
  105. * Searching for a key within a single node.
  106. */
  107. int lower_bound(struct btree_node *n, uint64_t key);
  108. extern struct dm_block_validator btree_node_validator;
  109. /*
  110. * Value type for upper levels of multi-level btrees.
  111. */
  112. extern void init_le64_type(struct dm_transaction_manager *tm,
  113. struct dm_btree_value_type *vt);
  114. #endif /* DM_BTREE_INTERNAL_H */