1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
2 // vim: ts=8 sw=2 smarttab
6 #include "key_layout.h"
7 #include "crimson/os/seastore/onode_manager/staged-fltree/node_types.h"
9 namespace crimson::os::seastore::onode
{
11 class NodeExtentMutable
;
13 struct node_header_t
{
14 static constexpr unsigned FIELD_TYPE_BITS
= 6u;
15 static_assert(static_cast<uint8_t>(field_type_t::_MAX
) <= 1u << FIELD_TYPE_BITS
);
16 static constexpr unsigned NODE_TYPE_BITS
= 1u;
17 static constexpr unsigned B_LEVEL_TAIL_BITS
= 1u;
18 using bits_t
= uint8_t;
21 std::optional
<field_type_t
> get_field_type() const {
22 if (field_type
>= FIELD_TYPE_MAGIC
&&
23 field_type
< static_cast<uint8_t>(field_type_t::_MAX
)) {
24 return static_cast<field_type_t
>(field_type
);
29 node_type_t
get_node_type() const {
30 return static_cast<node_type_t
>(node_type
);
32 bool get_is_level_tail() const {
36 static void bootstrap_extent(
37 NodeExtentMutable
&, field_type_t
, node_type_t
, bool, level_t
);
39 static void update_is_level_tail(NodeExtentMutable
&, const node_header_t
&, bool);
41 bits_t field_type
: FIELD_TYPE_BITS
;
42 bits_t node_type
: NODE_TYPE_BITS
;
43 bits_t is_level_tail
: B_LEVEL_TAIL_BITS
;
44 static_assert(sizeof(bits_t
) * 8 ==
45 FIELD_TYPE_BITS
+ NODE_TYPE_BITS
+ B_LEVEL_TAIL_BITS
);
49 void set_field_type(field_type_t type
) {
50 field_type
= static_cast<uint8_t>(type
);
52 void set_node_type(node_type_t type
) {
53 node_type
= static_cast<uint8_t>(type
);
55 void set_is_level_tail(bool value
) {
56 is_level_tail
= static_cast<uint8_t>(value
);
58 } __attribute__((packed
));
59 inline std::ostream
& operator<<(std::ostream
& os
, const node_header_t
& header
) {
60 auto field_type
= header
.get_field_type();
61 if (field_type
.has_value()) {
62 os
<< "header" << header
.get_node_type() << *field_type
63 << "(is_level_tail=" << header
.get_is_level_tail()
64 << ", level=" << (unsigned)header
.level
<< ")";
66 os
<< "header(INVALID)";
71 template <typename FixedKeyType
, field_type_t _FIELD_TYPE
>
73 using key_t
= FixedKeyType
;
74 static constexpr field_type_t FIELD_TYPE
= _FIELD_TYPE
;
75 static constexpr node_offset_t OVERHEAD
= sizeof(_slot_t
) - sizeof(key_t
);
78 node_offset_t right_offset
;
79 } __attribute__((packed
));
80 using slot_0_t
= _slot_t
<shard_pool_crush_t
, field_type_t::N0
>;
81 using slot_1_t
= _slot_t
<crush_t
, field_type_t::N1
>;
82 using slot_3_t
= _slot_t
<snap_gen_t
, field_type_t::N3
>;
89 template <typename FieldType
>
90 const char* fields_start(const FieldType
& node
) {
91 return reinterpret_cast<const char*>(&node
);
94 template <node_type_t NODE_TYPE
, typename FieldType
>
95 node_range_t
fields_free_range_before(
96 const FieldType
& node
, index_t index
, extent_len_t node_size
) {
97 assert(index
<= node
.num_keys
);
98 extent_len_t offset_start
= node
.get_key_start_offset(index
, node_size
);
99 extent_len_t offset_end
= node
.get_item_end_offset(index
, node_size
);
100 if constexpr (NODE_TYPE
== node_type_t::INTERNAL
) {
101 if (node
.is_level_tail() && index
== node
.num_keys
) {
102 offset_end
-= sizeof(laddr_t
);
105 assert(offset_start
<= offset_end
);
106 assert(offset_end
- offset_start
< node_size
);
107 return {offset_start
, offset_end
};
111 * _node_fields_013_t (node_fields_0_t, node_fields_1_t, leaf_fields_3_t
113 * The STAGE_LEFT layout implementation for node N0/N1, or the STAGE_RIGHT
114 * layout implementation for leaf node N3.
116 * The node layout storing n slots:
118 * # <----------------------------- node range --------------------------------------> #
119 * # #<~># free space #
120 * # <----- left part -----------------------------> # <~# <----- right slots -------> #
121 * # # <---- left slots -------------> #~> # #
122 * # # slots [2, n) |<~># #<~>| right slots [2, n) #
123 * # # <- slot 0 -> | <- slot 1 -> | # # | <-- s1 --> | <-- s0 --> #
125 * # | num_ # | right | | right | # # | next-stage | next-stage #
126 * # header | keys # key | offset | key | offset | # # | container | container #
127 * # | # 0 | 0 | 1 | 1 |...#...#...| or onode 1 | or onode 0 #
130 * | +----------------+ |
131 * +--------------------------------------------+
133 template <typename SlotType
>
134 struct _node_fields_013_t
{
135 // should be enough to index all keys under 64 KiB node
136 using num_keys_t
= uint16_t;
137 using key_t
= typename
SlotType::key_t
;
138 using key_get_type
= const key_t
&;
139 using me_t
= _node_fields_013_t
<SlotType
>;
140 static constexpr field_type_t FIELD_TYPE
= SlotType::FIELD_TYPE
;
141 static constexpr node_offset_t HEADER_SIZE
=
142 sizeof(node_header_t
) + sizeof(num_keys_t
);
143 static constexpr node_offset_t ITEM_OVERHEAD
= SlotType::OVERHEAD
;
145 bool is_level_tail() const { return header
.get_is_level_tail(); }
146 extent_len_t
total_size(extent_len_t node_size
) const {
149 key_get_type
get_key(
150 index_t index
, extent_len_t node_size
) const {
151 assert(index
< num_keys
);
152 return slots
[index
].key
;
154 node_offset_t
get_key_start_offset(
155 index_t index
, extent_len_t node_size
) const {
156 assert(index
<= num_keys
);
157 auto offset
= HEADER_SIZE
+ sizeof(SlotType
) * index
;
158 assert(offset
< node_size
);
161 node_offset_t
get_item_start_offset(
162 index_t index
, extent_len_t node_size
) const {
163 assert(index
< num_keys
);
164 auto offset
= slots
[index
].right_offset
;
165 assert(offset
< node_size
);
168 const void* p_offset(index_t index
) const {
169 assert(index
< num_keys
);
170 return &slots
[index
].right_offset
;
172 extent_len_t
get_item_end_offset(
173 index_t index
, extent_len_t node_size
) const {
174 return index
== 0 ? node_size
175 : get_item_start_offset(index
- 1, node_size
);
177 template <node_type_t NODE_TYPE
>
178 node_offset_t
free_size_before(
179 index_t index
, extent_len_t node_size
) const {
180 auto range
= fields_free_range_before
<NODE_TYPE
>(*this, index
, node_size
);
181 return range
.end
- range
.start
;
184 static node_offset_t
estimate_insert_one() { return sizeof(SlotType
); }
185 template <IsFullKey Key
>
186 static void insert_at(
187 NodeExtentMutable
&, const Key
& key
,
188 const me_t
& node
, index_t index
, node_offset_t size_right
);
189 static node_offset_t
erase_at(NodeExtentMutable
&, const me_t
&, index_t
, const char*);
190 static void update_size_at(
191 NodeExtentMutable
&, const me_t
& node
, index_t index
, int change
);
192 static void append_key(
193 NodeExtentMutable
&, const key_t
& key
, char*& p_append
);
194 template <IsFullKey Key
>
195 static void append_key(
196 NodeExtentMutable
& mut
, const Key
& key
, char*& p_append
) {
197 append_key(mut
, key_t::from_key(key
), p_append
);
199 static void append_offset(
200 NodeExtentMutable
& mut
, node_offset_t offset_to_right
, char*& p_append
);
202 node_header_t header
;
203 num_keys_t num_keys
= 0u;
205 } __attribute__((packed
));
206 using node_fields_0_t
= _node_fields_013_t
<slot_0_t
>;
207 using node_fields_1_t
= _node_fields_013_t
<slot_1_t
>;
212 * The STAGE_STRING layout implementation for node N2.
214 * The node layout storing n slots:
216 * # <--------------------------------- node range ----------------------------------------> #
217 * # #<~># free space #
218 * # <------- left part ---------------> # <~# <--------- right slots ---------------------> #
219 * # # <---- offsets ----> #~> #<~>| slots [2, n) #
220 * # # offsets [2, n) |<~># # | <----- slot 1 ----> | <----- slot 0 ----> #
222 * # | num_ # offset | offset | # # | next-stage | ns-oid | next-stage | ns-oid #
223 * # header | keys # 0 | 1 |...#...#...| container1 | 1 | container0 | 0 #
226 * | +----------------+ |
227 * +-----------------------------------------------+
229 struct node_fields_2_t
{
230 // should be enough to index all keys under 64 KiB node
231 using num_keys_t
= uint16_t;
232 using key_t
= ns_oid_view_t
;
233 using key_get_type
= key_t
;
234 static constexpr field_type_t FIELD_TYPE
= field_type_t::N2
;
235 static constexpr node_offset_t HEADER_SIZE
=
236 sizeof(node_header_t
) + sizeof(num_keys_t
);
237 static constexpr node_offset_t ITEM_OVERHEAD
= sizeof(node_offset_t
);
239 bool is_level_tail() const { return header
.get_is_level_tail(); }
240 extent_len_t
total_size(extent_len_t node_size
) const {
243 key_get_type
get_key(
244 index_t index
, extent_len_t node_size
) const {
245 assert(index
< num_keys
);
246 auto item_end_offset
= get_item_end_offset(index
, node_size
);
247 const char* p_start
= fields_start(*this);
248 return key_t(p_start
+ item_end_offset
);
250 node_offset_t
get_key_start_offset(
251 index_t index
, extent_len_t node_size
) const {
252 assert(index
<= num_keys
);
253 auto offset
= HEADER_SIZE
+ sizeof(node_offset_t
) * num_keys
;
254 assert(offset
< node_size
);
257 node_offset_t
get_item_start_offset(
258 index_t index
, extent_len_t node_size
) const {
259 assert(index
< num_keys
);
260 auto offset
= offsets
[index
];
261 assert(offset
< node_size
);
264 const void* p_offset(index_t index
) const {
265 assert(index
< num_keys
);
266 return &offsets
[index
];
268 extent_len_t
get_item_end_offset(
269 index_t index
, extent_len_t node_size
) const {
270 return index
== 0 ? node_size
271 : get_item_start_offset(index
- 1, node_size
);
273 template <node_type_t NODE_TYPE
>
274 node_offset_t
free_size_before(
275 index_t index
, extent_len_t node_size
) const {
276 auto range
= fields_free_range_before
<NODE_TYPE
>(*this, index
, node_size
);
277 return range
.end
- range
.start
;
280 static node_offset_t
estimate_insert_one() { return sizeof(node_offset_t
); }
281 template <IsFullKey Key
>
282 static void insert_at(
283 NodeExtentMutable
& mut
, const Key
& key
,
284 const node_fields_2_t
& node
, index_t index
, node_offset_t size_right
) {
285 ceph_abort("not implemented");
287 static void update_size_at(
288 NodeExtentMutable
& mut
, const node_fields_2_t
& node
, index_t index
, int change
) {
289 ceph_abort("not implemented");
291 static void append_key(
292 NodeExtentMutable
& mut
, const key_t
& key
, char*& p_append
) {
293 ns_oid_view_t::append(mut
, key
, p_append
);
295 template <IsFullKey Key
>
296 static void append_key(
297 NodeExtentMutable
& mut
, const Key
& key
, char*& p_append
) {
298 ns_oid_view_t::append(mut
, key
, p_append
);
300 static void append_offset(
301 NodeExtentMutable
& mut
, node_offset_t offset_to_right
, char*& p_append
);
303 node_header_t header
;
304 num_keys_t num_keys
= 0u;
305 node_offset_t offsets
[];
306 } __attribute__((packed
));
309 * internal_fields_3_t
311 * The STAGE_RIGHT layout implementation for N2.
313 * The node layout storing 3 children:
315 * # <---------------- node range ---------------------------> #
316 * # # <-- keys ---> # <---- laddrs -----------> #
317 * # free space: # |<~># |<~>#
319 * # | num_ # key | key | # laddr | laddr | laddr | #
320 * # header | keys # 0 | 1 |...# 0 | 1 | 2 |...#
322 struct internal_fields_3_t
{
323 using key_get_type
= const snap_gen_t
&;
324 // should be enough to index all keys under 64 KiB node
325 using num_keys_t
= uint16_t;
326 static constexpr field_type_t FIELD_TYPE
= field_type_t::N3
;
327 static constexpr node_offset_t HEADER_SIZE
=
328 sizeof(node_header_t
) + sizeof(num_keys_t
);
329 static constexpr node_offset_t ITEM_SIZE
=
330 sizeof(snap_gen_t
) + sizeof(laddr_t
);
331 static constexpr node_offset_t ITEM_OVERHEAD
= 0u;
333 bool is_level_tail() const { return header
.get_is_level_tail(); }
334 extent_len_t
total_size(extent_len_t node_size
) const {
335 if (is_level_tail()) {
336 return node_size
- sizeof(snap_gen_t
);
341 key_get_type
get_key(
342 index_t index
, extent_len_t node_size
) const {
343 assert(index
< num_keys
);
346 template <node_type_t NODE_TYPE
>
347 std::enable_if_t
<NODE_TYPE
== node_type_t::INTERNAL
, node_offset_t
>
348 free_size_before(index_t index
, extent_len_t node_size
) const {
349 assert(index
<= num_keys
);
350 assert(num_keys
<= get_max_num_keys(node_size
));
351 extent_len_t free
= total_size(node_size
) - HEADER_SIZE
-
353 if (is_level_tail() && index
== num_keys
) {
354 free
-= sizeof(laddr_t
);
359 const laddr_packed_t
* get_p_child_addr(
360 index_t index
, extent_len_t node_size
) const {
362 if (is_level_tail()) {
363 assert(index
<= num_keys
);
365 assert(index
< num_keys
);
368 auto p_addrs
= reinterpret_cast<const laddr_packed_t
*>(
369 &keys
[get_num_keys_limit(node_size
)]);
370 auto ret
= p_addrs
+ index
;
371 assert((const char*)ret
< fields_start(*this) + node_size
);
375 static node_offset_t
estimate_insert_one() { return ITEM_SIZE
; }
377 template <IsFullKey Key
>
378 static void insert_at(
379 NodeExtentMutable
& mut
, const Key
& key
,
380 const internal_fields_3_t
& node
,
381 index_t index
, node_offset_t size_right
) {
382 ceph_abort("not implemented");
384 static void update_size_at(
385 NodeExtentMutable
& mut
, const internal_fields_3_t
& node
,
386 index_t index
, int change
) {
387 ceph_abort("not implemented");
390 node_header_t header
;
391 num_keys_t num_keys
= 0u;
395 num_keys_t
get_max_num_keys(extent_len_t node_size
) const {
396 auto num_limit
= get_num_keys_limit(node_size
);
397 return (is_level_tail() ? num_limit
- 1 : num_limit
);
399 static num_keys_t
get_num_keys_limit(extent_len_t node_size
) {
400 return (node_size
- HEADER_SIZE
) / ITEM_SIZE
;
402 } __attribute__((packed
));
404 using leaf_fields_3_t
= _node_fields_013_t
<slot_3_t
>;