1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:nil -*-
2 // vim: ts=8 sw=2 smarttab
4 #include "sub_items_stage.h"
6 #include "crimson/os/seastore/onode_manager/staged-fltree/node_extent_mutable.h"
8 namespace crimson::os::seastore::onode
{
11 const laddr_packed_t
* internal_sub_items_t::insert_at(
12 NodeExtentMutable
& mut
, const internal_sub_items_t
& sub_items
,
13 const full_key_t
<KT
>& key
, const laddr_t
& value
,
14 index_t index
, node_offset_t size
, const char* p_left_bound
)
16 assert(index
<= sub_items
.keys());
17 assert(size
== estimate_insert
<KT
>(key
, value
));
18 const char* p_shift_start
= p_left_bound
;
19 const char* p_shift_end
= reinterpret_cast<const char*>(
20 sub_items
.p_first_item
+ 1 - index
);
21 mut
.shift_absolute(p_shift_start
, p_shift_end
- p_shift_start
, -(int)size
);
23 auto p_insert
= const_cast<char*>(p_shift_end
) - size
;
24 auto item
= internal_sub_item_t
{
25 snap_gen_t::from_key
<KT
>(key
), laddr_packed_t
{value
}};
26 mut
.copy_in_absolute(p_insert
, item
);
27 return &reinterpret_cast<internal_sub_item_t
*>(p_insert
)->value
;
29 #define IA_TEMPLATE(KT) \
30 template const laddr_packed_t* internal_sub_items_t::insert_at<KT>( \
31 NodeExtentMutable&, const internal_sub_items_t&, const full_key_t<KT>&, \
32 const laddr_t&, index_t, node_offset_t, const char*)
33 IA_TEMPLATE(KeyT::VIEW
);
34 IA_TEMPLATE(KeyT::HOBJ
);
36 node_offset_t
internal_sub_items_t::trim_until(
37 NodeExtentMutable
& mut
, internal_sub_items_t
& items
, index_t index
)
40 auto keys
= items
.keys();
41 assert(index
<= keys
);
42 size_t ret
= sizeof(internal_sub_item_t
) * (keys
- index
);
43 assert(ret
< mut
.get_length());
47 node_offset_t
internal_sub_items_t::erase_at(
48 NodeExtentMutable
& mut
, const internal_sub_items_t
& sub_items
,
49 index_t index
, const char* p_left_bound
)
51 assert(index
< sub_items
.keys());
52 node_offset_t erase_size
= sizeof(internal_sub_item_t
);
53 const char* p_shift_start
= p_left_bound
;
54 const char* p_shift_end
= reinterpret_cast<const char*>(
55 sub_items
.p_first_item
- index
);
56 mut
.shift_absolute(p_shift_start
, p_shift_end
- p_shift_start
, erase_size
);
61 void internal_sub_items_t::Appender
<KT
>::append(
62 const internal_sub_items_t
& src
, index_t from
, index_t items
)
64 assert(from
<= src
.keys());
68 assert(from
< src
.keys());
69 assert(from
+ items
<= src
.keys());
70 node_offset_t size
= sizeof(internal_sub_item_t
) * items
;
72 p_mut
->copy_in_absolute(p_append
, src
.p_first_item
+ 1 - from
- items
, size
);
76 void internal_sub_items_t::Appender
<KT
>::append(
77 const full_key_t
<KT
>& key
, const laddr_t
& value
,
78 const laddr_packed_t
*& p_value
)
80 p_append
-= sizeof(internal_sub_item_t
);
81 auto item
= internal_sub_item_t
{
82 snap_gen_t::from_key
<KT
>(key
), laddr_packed_t
{value
}};
83 p_mut
->copy_in_absolute(p_append
, item
);
84 p_value
= &reinterpret_cast<internal_sub_item_t
*>(p_append
)->value
;
88 const value_header_t
* leaf_sub_items_t::insert_at(
89 NodeExtentMutable
& mut
, const leaf_sub_items_t
& sub_items
,
90 const full_key_t
<KT
>& key
, const value_config_t
& value
,
91 index_t index
, node_offset_t size
, const char* p_left_bound
)
93 assert(index
<= sub_items
.keys());
94 assert(size
== estimate_insert
<KT
>(key
, value
));
95 // a. [... item(index)] << size
96 const char* p_shift_start
= p_left_bound
;
97 const char* p_shift_end
= sub_items
.get_item_end(index
);
98 mut
.shift_absolute(p_shift_start
, p_shift_end
- p_shift_start
, -(int)size
);
101 auto p_insert
= const_cast<char*>(p_shift_end
- size
);
102 auto p_value
= reinterpret_cast<value_header_t
*>(p_insert
);
103 p_value
->initiate(mut
, value
);
104 p_insert
+= value
.allocation_size();
105 mut
.copy_in_absolute(p_insert
, snap_gen_t::template from_key
<KT
>(key
));
106 assert(p_insert
+ sizeof(snap_gen_t
) + sizeof(node_offset_t
) == p_shift_end
);
108 // c. compensate affected offsets
109 auto item_size
= value
.allocation_size() + sizeof(snap_gen_t
);
110 for (auto i
= index
; i
< sub_items
.keys(); ++i
) {
111 const node_offset_packed_t
& offset_i
= sub_items
.get_offset(i
);
112 mut
.copy_in_absolute((void*)&offset_i
, node_offset_t(offset_i
.value
+ item_size
));
115 // d. [item(index-1) ... item(0) ... offset(index)] <<< sizeof(node_offset_t)
116 const char* p_offset
= (index
== 0 ?
117 (const char*)&sub_items
.get_offset(0) + sizeof(node_offset_t
) :
118 (const char*)&sub_items
.get_offset(index
- 1));
119 p_shift_start
= p_shift_end
;
120 p_shift_end
= p_offset
;
121 mut
.shift_absolute(p_shift_start
, p_shift_end
- p_shift_start
, -(int)sizeof(node_offset_t
));
124 node_offset_t offset_to_item_start
= item_size
+ sub_items
.get_offset_to_end(index
);
125 mut
.copy_in_absolute(
126 const_cast<char*>(p_shift_end
) - sizeof(node_offset_t
), offset_to_item_start
);
128 // f. update num_sub_keys
129 mut
.copy_in_absolute((void*)sub_items
.p_num_keys
, num_keys_t(sub_items
.keys() + 1));
133 template const value_header_t
* leaf_sub_items_t::insert_at
<KeyT::HOBJ
>(
134 NodeExtentMutable
&, const leaf_sub_items_t
&, const full_key_t
<KeyT::HOBJ
>&,
135 const value_config_t
&, index_t
, node_offset_t
, const char*);
137 node_offset_t
leaf_sub_items_t::trim_until(
138 NodeExtentMutable
& mut
, leaf_sub_items_t
& items
, index_t index
)
141 auto keys
= items
.keys();
142 assert(index
<= keys
);
146 index_t trim_items
= keys
- index
;
147 const char* p_items_start
= items
.p_start();
148 const char* p_shift_start
= items
.get_item_end(index
);
149 const char* p_shift_end
= items
.get_item_end(0);
150 size_t size_trim_offsets
= sizeof(node_offset_t
) * trim_items
;
151 mut
.shift_absolute(p_shift_start
, p_shift_end
- p_shift_start
,
153 mut
.copy_in_absolute((void*)items
.p_num_keys
, num_keys_t(index
));
154 size_t ret
= size_trim_offsets
+ (p_shift_start
- p_items_start
);
155 assert(ret
< mut
.get_length());
159 node_offset_t
leaf_sub_items_t::erase_at(
160 NodeExtentMutable
& mut
, const leaf_sub_items_t
& sub_items
,
161 index_t index
, const char* p_left_bound
)
163 assert(sub_items
.keys() > 0);
164 assert(index
< sub_items
.keys());
165 auto p_item_start
= sub_items
.get_item_start(index
);
166 auto p_item_end
= sub_items
.get_item_end(index
);
167 assert(p_item_start
< p_item_end
);
168 node_offset_t item_erase_size
= p_item_end
- p_item_start
;
169 node_offset_t erase_size
= item_erase_size
+ sizeof(node_offset_t
);
170 auto p_offset_end
= (const char*)&sub_items
.get_offset(index
);
172 // a. compensate affected offset[n] ... offset[index+1]
173 for (auto i
= index
+ 1; i
< sub_items
.keys(); ++i
) {
174 const node_offset_packed_t
& offset_i
= sub_items
.get_offset(i
);
175 mut
.copy_in_absolute((void*)&offset_i
, node_offset_t(offset_i
.value
- item_erase_size
));
178 // b. kv[index-1] ... kv[0] ... offset[index+1] >> sizeof(node_offset_t)
179 mut
.shift_absolute(p_item_end
, p_offset_end
- p_item_end
, sizeof(node_offset_t
));
181 // c. ... kv[n] ... kv[index+1] >> item_erase_size
182 mut
.shift_absolute(p_left_bound
, p_item_start
- p_left_bound
, erase_size
);
184 // d. update num_keys
185 mut
.copy_in_absolute((void*)sub_items
.p_num_keys
, num_keys_t(sub_items
.keys() - 1));
190 template class internal_sub_items_t::Appender
<KeyT::VIEW
>;
191 template class internal_sub_items_t::Appender
<KeyT::HOBJ
>;
193 // helper type for the visitor
194 template<class... Ts
> struct overloaded
: Ts
... { using Ts::operator()...; };
195 // explicit deduction guide
196 template<class... Ts
> overloaded(Ts
...) -> overloaded
<Ts
...>;
199 void leaf_sub_items_t::Appender
<KT
>::append(
200 const leaf_sub_items_t
& src
, index_t from
, index_t items
)
204 assert(cnt
<= APPENDER_LIMIT
);
205 assert(from
<= src
.keys());
210 assert(*op_src
== src
);
214 assert(from
< src
.keys());
215 assert(from
+ items
<= src
.keys());
216 appends
[cnt
] = range_items_t
{from
, items
};
219 // append from existing
220 assert(op_dst
.has_value());
224 assert(items
== src
.keys());
226 num_keys_t num_keys
= op_dst
->keys();
227 node_offset_t compensate
= op_dst
->get_offset(num_keys
- 1).value
;
228 const char* p_items_start
= op_dst
->p_start();
229 const char* p_items_end
= op_dst
->p_items_end
;
231 // update dst num_keys
233 p_mut
->copy_in_absolute((char*)op_dst
->p_num_keys
, num_keys
);
236 std::size_t src_offsets_size
= sizeof(node_offset_t
) * items
;
237 p_mut
->shift_absolute(p_items_start
,
238 p_items_end
- p_items_start
,
239 -(int)src_offsets_size
);
241 // fill offsets from src
242 node_offset_t offset
;
243 char* p_cur_offset
= const_cast<char*>(p_items_end
);
244 for (auto i
= from
; i
< from
+ items
; ++i
) {
245 offset
= src
.get_offset(i
).value
+ compensate
;
246 p_cur_offset
-= sizeof(node_offset_t
);
247 p_mut
->copy_in_absolute(p_cur_offset
, offset
);
250 // fill items from src
251 auto p_src_items_start
= src
.get_item_end(from
+ items
);
252 std::size_t src_items_size
= src
.get_item_end(from
) - p_src_items_start
;
253 p_appended
= const_cast<char*>(p_items_start
) - src_offsets_size
- src_items_size
;
254 p_mut
->copy_in_absolute(p_appended
, p_src_items_start
, src_items_size
);
259 char* leaf_sub_items_t::Appender
<KT
>::wrap()
261 if (op_dst
.has_value()) {
262 // append from existing
268 auto p_cur
= p_append
;
269 num_keys_t num_keys
= 0;
270 for (auto i
= 0u; i
< cnt
; ++i
) {
271 auto& a
= appends
[i
];
272 std::visit(overloaded
{
273 [&] (const range_items_t
& arg
) { num_keys
+= arg
.items
; },
274 [&] (const kv_item_t
& arg
) { ++num_keys
; }
278 p_cur
-= sizeof(num_keys_t
);
279 p_mut
->copy_in_absolute(p_cur
, num_keys
);
281 node_offset_t last_offset
= 0;
282 for (auto i
= 0u; i
< cnt
; ++i
) {
283 auto& a
= appends
[i
];
284 std::visit(overloaded
{
285 [&] (const range_items_t
& arg
) {
286 int compensate
= (last_offset
- op_src
->get_offset_to_end(arg
.from
));
287 node_offset_t offset
;
288 for (auto i
= arg
.from
; i
< arg
.from
+ arg
.items
; ++i
) {
289 offset
= op_src
->get_offset(i
).value
+ compensate
;
290 p_cur
-= sizeof(node_offset_t
);
291 p_mut
->copy_in_absolute(p_cur
, offset
);
293 last_offset
= offset
;
295 [&] (const kv_item_t
& arg
) {
296 last_offset
+= sizeof(snap_gen_t
) + arg
.value_config
.allocation_size();
297 p_cur
-= sizeof(node_offset_t
);
298 p_mut
->copy_in_absolute(p_cur
, last_offset
);
303 for (auto i
= 0u; i
< cnt
; ++i
) {
304 auto& a
= appends
[i
];
305 std::visit(overloaded
{
306 [&] (const range_items_t
& arg
) {
307 auto _p_start
= op_src
->get_item_end(arg
.from
+ arg
.items
);
308 size_t _len
= op_src
->get_item_end(arg
.from
) - _p_start
;
310 p_mut
->copy_in_absolute(p_cur
, _p_start
, _len
);
312 [&] (const kv_item_t
& arg
) {
314 p_cur
-= sizeof(snap_gen_t
);
315 p_mut
->copy_in_absolute(p_cur
, snap_gen_t::template from_key
<KT
>(*arg
.p_key
));
316 p_cur
-= arg
.value_config
.allocation_size();
317 auto p_value
= reinterpret_cast<value_header_t
*>(p_cur
);
318 p_value
->initiate(*p_mut
, arg
.value_config
);
326 template class leaf_sub_items_t::Appender
<KeyT::VIEW
>;
327 template class leaf_sub_items_t::Appender
<KeyT::HOBJ
>;