]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | /* | |
4 | * Ceph - scalable distributed file system | |
5 | * | |
6 | * Copyright (C) 2016 Red Hat | |
7 | * | |
8 | * This is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU Lesser General Public | |
10 | * License version 2.1, as published by the Free Software | |
11 | * Foundation. See file COPYING. | |
12 | * | |
13 | */ | |
14 | #ifndef PGTRANSACTION_H | |
15 | #define PGTRANSACTION_H | |
16 | ||
17 | #include <map> | |
18 | #include <memory> | |
9f95a23c | 19 | #include <optional> |
7c673cae FG |
20 | |
21 | #include "common/hobject.h" | |
22 | #include "osd/osd_types.h" | |
23 | #include "osd/osd_internal_types.h" | |
24 | #include "common/interval_map.h" | |
25 | #include "common/inline_variant.h" | |
26 | ||
27 | /** | |
28 | * This class represents transactions which can be submitted to | |
29 | * a PGBackend. For expediency, there are some constraints on | |
30 | * the operations submitted: | |
31 | * 1) Rename sources may only be referenced prior to the rename | |
32 | * operation to the destination. | |
33 | * 2) The graph formed by edges of source->destination for clones | |
34 | * (Create) and Renames must be acyclic. | |
35 | * 3) clone_range sources must not be modified by the same | |
36 | * transaction | |
37 | */ | |
38 | class PGTransaction { | |
39 | public: | |
40 | map<hobject_t, ObjectContextRef> obc_map; | |
41 | ||
42 | class ObjectOperation { | |
43 | public: | |
44 | struct Init | |
45 | { | |
46 | struct None {}; | |
47 | struct Create {}; | |
48 | struct Clone { | |
49 | hobject_t source; | |
50 | }; | |
51 | struct Rename { | |
52 | hobject_t source; // must be temp object | |
53 | }; | |
54 | }; | |
55 | using InitType = boost::variant< | |
56 | Init::None, | |
57 | Init::Create, | |
58 | Init::Clone, | |
59 | Init::Rename>; | |
60 | ||
61 | InitType init_type = Init::None(); | |
62 | bool delete_first = false; | |
63 | ||
64 | /** | |
65 | * is_none() && is_delete() indicates that we are deleting an | |
66 | * object which already exists and not recreating it. delete_first means | |
67 | * that the transaction logically removes the object. | |
68 | ||
69 | * There are really 4 cases: | |
70 | ||
71 | * 1) We are modifying an existing object (is_none() && | |
72 | * !is_delete()) | |
73 | * a) If it's an append, we just write into the log entry the old size | |
74 | * b) If it's an actual overwrite, we save the old versions of the | |
75 | * extents being overwritten and write those offsets into the log | |
76 | * entry | |
77 | * 2) We are removing and then recreating an object (!is_none() && is_delete()) | |
78 | * -- stash | |
79 | * 3) We are removing an object (is_none() && is_delete()) -- stash | |
80 | * 4) We are creating an object (!is_none() && !is_delete()) -- create (no | |
81 | * stash) | |
82 | * | |
83 | * Create, Clone, Rename are the three ways we can recreate it. | |
84 | * ECBackend transaction planning needs this context | |
85 | * to figure out how to perform the transaction. | |
86 | */ | |
87 | bool deletes_first() const { | |
88 | return delete_first; | |
89 | } | |
90 | bool is_delete() const { | |
91 | return boost::get<Init::None>(&init_type) != nullptr && delete_first; | |
92 | } | |
93 | bool is_none() const { | |
94 | return boost::get<Init::None>(&init_type) != nullptr && !delete_first; | |
95 | } | |
96 | bool is_fresh_object() const { | |
97 | return boost::get<Init::None>(&init_type) == nullptr; | |
98 | } | |
99 | bool is_rename() const { | |
100 | return boost::get<Init::Rename>(&init_type) != nullptr; | |
101 | } | |
102 | bool has_source(hobject_t *source = nullptr) const { | |
103 | return match( | |
104 | init_type, | |
105 | [&](const Init::Clone &op) -> bool { | |
106 | if (source) | |
107 | *source = op.source; | |
108 | return true; | |
109 | }, | |
110 | [&](const Init::Rename &op) -> bool { | |
111 | if (source) | |
112 | *source = op.source; | |
113 | return true; | |
114 | }, | |
115 | [&](const Init::None &) -> bool { return false; }, | |
116 | [&](const Init::Create &) -> bool { return false; }); | |
117 | } | |
118 | ||
119 | bool clear_omap = false; | |
120 | ||
121 | /** | |
122 | * truncate | |
123 | * <lowest, last> ? | |
124 | * | |
125 | * truncate is represented as a pair because in the event of | |
126 | * multiple truncates within a single transaction we need to | |
127 | * remember the lowest truncate and the final object size | |
128 | * (the last truncate). We also adjust the buffers map | |
129 | * to account for truncates overriding previous writes */ | |
9f95a23c | 130 | std::optional<pair<uint64_t, uint64_t> > truncate = std::nullopt; |
7c673cae | 131 | |
9f95a23c | 132 | std::map<string, std::optional<bufferlist> > attr_updates; |
7c673cae | 133 | |
9f95a23c | 134 | enum class OmapUpdateType {Remove, Insert, RemoveRange}; |
7c673cae FG |
135 | std::vector<std::pair<OmapUpdateType, bufferlist> > omap_updates; |
136 | ||
9f95a23c | 137 | std::optional<bufferlist> omap_header; |
7c673cae FG |
138 | |
139 | /// (old, new) -- only valid with no truncate or buffer updates | |
9f95a23c | 140 | std::optional<pair<set<snapid_t>, set<snapid_t> > > updated_snaps; |
7c673cae FG |
141 | |
142 | struct alloc_hint_t { | |
143 | uint64_t expected_object_size; | |
144 | uint64_t expected_write_size; | |
145 | uint32_t flags; | |
146 | }; | |
9f95a23c | 147 | std::optional<alloc_hint_t> alloc_hint; |
7c673cae FG |
148 | |
149 | struct BufferUpdate { | |
150 | struct Write { | |
151 | bufferlist buffer; | |
152 | uint32_t fadvise_flags; | |
153 | }; | |
154 | struct Zero { | |
155 | uint64_t len; | |
156 | }; | |
157 | struct CloneRange { | |
158 | hobject_t from; | |
159 | uint64_t offset; | |
160 | uint64_t len; | |
161 | }; | |
162 | }; | |
163 | using BufferUpdateType = boost::variant< | |
164 | BufferUpdate::Write, | |
165 | BufferUpdate::Zero, | |
166 | BufferUpdate::CloneRange>; | |
167 | ||
168 | private: | |
169 | struct SplitMerger { | |
170 | BufferUpdateType split( | |
171 | uint64_t offset, | |
172 | uint64_t len, | |
173 | const BufferUpdateType &bu) const { | |
174 | return match( | |
175 | bu, | |
176 | [&](const BufferUpdate::Write &w) -> BufferUpdateType { | |
177 | bufferlist bl; | |
178 | bl.substr_of(w.buffer, offset, len); | |
179 | return BufferUpdate::Write{bl, w.fadvise_flags}; | |
180 | }, | |
181 | [&](const BufferUpdate::Zero &) -> BufferUpdateType { | |
182 | return BufferUpdate::Zero{len}; | |
183 | }, | |
184 | [&](const BufferUpdate::CloneRange &c) -> BufferUpdateType { | |
185 | return BufferUpdate::CloneRange{c.from, c.offset + offset, len}; | |
186 | }); | |
187 | } | |
188 | uint64_t length( | |
189 | const BufferUpdateType &left) const { | |
190 | return match( | |
191 | left, | |
192 | [&](const BufferUpdate::Write &w) -> uint64_t { | |
193 | return w.buffer.length(); | |
194 | }, | |
195 | [&](const BufferUpdate::Zero &z) -> uint64_t { | |
196 | return z.len; | |
197 | }, | |
198 | [&](const BufferUpdate::CloneRange &c) -> uint64_t { | |
199 | return c.len; | |
200 | }); | |
201 | } | |
202 | bool can_merge( | |
203 | const BufferUpdateType &left, | |
204 | const BufferUpdateType &right) const { | |
205 | return match( | |
206 | left, | |
207 | [&](const BufferUpdate::Write &w) -> bool { | |
208 | auto r = boost::get<BufferUpdate::Write>(&right); | |
209 | return r != nullptr && (w.fadvise_flags == r->fadvise_flags); | |
210 | }, | |
211 | [&](const BufferUpdate::Zero &) -> bool { | |
212 | auto r = boost::get<BufferUpdate::Zero>(&right); | |
213 | return r != nullptr; | |
214 | }, | |
215 | [&](const BufferUpdate::CloneRange &c) -> bool { | |
216 | return false; | |
217 | }); | |
218 | } | |
219 | BufferUpdateType merge( | |
220 | BufferUpdateType &&left, | |
221 | BufferUpdateType &&right) const { | |
222 | return match( | |
223 | left, | |
224 | [&](const BufferUpdate::Write &w) -> BufferUpdateType { | |
225 | auto r = boost::get<BufferUpdate::Write>(&right); | |
11fdf7f2 | 226 | ceph_assert(r && w.fadvise_flags == r->fadvise_flags); |
7c673cae FG |
227 | bufferlist bl = w.buffer; |
228 | bl.append(r->buffer); | |
229 | return BufferUpdate::Write{bl, w.fadvise_flags}; | |
230 | }, | |
231 | [&](const BufferUpdate::Zero &z) -> BufferUpdateType { | |
232 | auto r = boost::get<BufferUpdate::Zero>(&right); | |
11fdf7f2 | 233 | ceph_assert(r); |
7c673cae FG |
234 | return BufferUpdate::Zero{z.len + r->len}; |
235 | }, | |
236 | [&](const BufferUpdate::CloneRange &c) -> BufferUpdateType { | |
11fdf7f2 | 237 | ceph_abort_msg("violates can_merge condition"); |
7c673cae FG |
238 | return left; |
239 | }); | |
240 | } | |
241 | }; | |
242 | public: | |
243 | using buffer_update_type = interval_map< | |
244 | uint64_t, BufferUpdateType, SplitMerger>; | |
245 | buffer_update_type buffer_updates; | |
246 | ||
247 | friend class PGTransaction; | |
248 | }; | |
249 | map<hobject_t, ObjectOperation> op_map; | |
250 | private: | |
251 | ObjectOperation &get_object_op_for_modify(const hobject_t &hoid) { | |
252 | auto &op = op_map[hoid]; | |
11fdf7f2 | 253 | ceph_assert(!op.is_delete()); |
7c673cae FG |
254 | return op; |
255 | } | |
256 | ObjectOperation &get_object_op(const hobject_t &hoid) { | |
257 | return op_map[hoid]; | |
258 | } | |
259 | public: | |
260 | void add_obc( | |
261 | ObjectContextRef obc) { | |
11fdf7f2 | 262 | ceph_assert(obc); |
7c673cae FG |
263 | obc_map[obc->obs.oi.soid] = obc; |
264 | } | |
265 | /// Sets up state for new object | |
266 | void create( | |
267 | const hobject_t &hoid | |
268 | ) { | |
269 | auto &op = op_map[hoid]; | |
11fdf7f2 | 270 | ceph_assert(op.is_none() || op.is_delete()); |
7c673cae FG |
271 | op.init_type = ObjectOperation::Init::Create(); |
272 | } | |
273 | ||
274 | /// Sets up state for target cloned from source | |
275 | void clone( | |
276 | const hobject_t &target, ///< [in] obj to clone to | |
277 | const hobject_t &source ///< [in] obj to clone from | |
278 | ) { | |
279 | auto &op = op_map[target]; | |
11fdf7f2 | 280 | ceph_assert(op.is_none() || op.is_delete()); |
7c673cae FG |
281 | op.init_type = ObjectOperation::Init::Clone{source}; |
282 | } | |
283 | ||
284 | /// Sets up state for target renamed from source | |
285 | void rename( | |
11fdf7f2 TL |
286 | const hobject_t &target, ///< [in] to, must not exist, be non-temp |
287 | const hobject_t &source ///< [in] source (must be a temp object) | |
7c673cae | 288 | ) { |
11fdf7f2 TL |
289 | ceph_assert(source.is_temp()); |
290 | ceph_assert(!target.is_temp()); | |
7c673cae | 291 | auto &op = op_map[target]; |
11fdf7f2 | 292 | ceph_assert(op.is_none() || op.is_delete()); |
7c673cae FG |
293 | |
294 | bool del_first = op.is_delete(); | |
295 | auto iter = op_map.find(source); | |
296 | if (iter != op_map.end()) { | |
297 | op = iter->second; | |
298 | op_map.erase(iter); | |
299 | op.delete_first = del_first; | |
300 | } | |
301 | ||
302 | op.init_type = ObjectOperation::Init::Rename{source}; | |
303 | } | |
304 | ||
305 | /// Remove -- must not be called on rename target | |
306 | void remove( | |
307 | const hobject_t &hoid ///< [in] obj to remove | |
308 | ) { | |
309 | auto &op = get_object_op_for_modify(hoid); | |
310 | if (!op.is_fresh_object()) { | |
11fdf7f2 | 311 | ceph_assert(!op.updated_snaps); |
7c673cae FG |
312 | op = ObjectOperation(); |
313 | op.delete_first = true; | |
314 | } else { | |
11fdf7f2 | 315 | ceph_assert(!op.is_rename()); |
7c673cae FG |
316 | op_map.erase(hoid); // make it a noop if it's a fresh object |
317 | } | |
318 | } | |
319 | ||
320 | void update_snaps( | |
321 | const hobject_t &hoid, ///< [in] object for snaps | |
322 | const set<snapid_t> &old_snaps,///< [in] old snaps value | |
323 | const set<snapid_t> &new_snaps ///< [in] new snaps value | |
324 | ) { | |
325 | auto &op = get_object_op(hoid); | |
11fdf7f2 TL |
326 | ceph_assert(!op.updated_snaps); |
327 | ceph_assert(op.buffer_updates.empty()); | |
328 | ceph_assert(!op.truncate); | |
7c673cae FG |
329 | op.updated_snaps = make_pair( |
330 | old_snaps, | |
331 | new_snaps); | |
332 | } | |
333 | ||
334 | /// Clears, truncates | |
335 | void omap_clear( | |
336 | const hobject_t &hoid ///< [in] object to clear omap | |
337 | ) { | |
338 | auto &op = get_object_op_for_modify(hoid); | |
339 | op.clear_omap = true; | |
340 | op.omap_updates.clear(); | |
9f95a23c | 341 | op.omap_header = std::nullopt; |
7c673cae FG |
342 | } |
343 | void truncate( | |
344 | const hobject_t &hoid, ///< [in] object | |
345 | uint64_t off ///< [in] offset to truncate to | |
346 | ) { | |
347 | auto &op = get_object_op_for_modify(hoid); | |
11fdf7f2 | 348 | ceph_assert(!op.updated_snaps); |
7c673cae FG |
349 | op.buffer_updates.erase( |
350 | off, | |
351 | std::numeric_limits<uint64_t>::max() - off); | |
352 | if (!op.truncate || off < op.truncate->first) { | |
353 | op.truncate = std::pair<uint64_t, uint64_t>(off, off); | |
354 | } else { | |
355 | op.truncate->second = off; | |
356 | } | |
357 | } | |
358 | ||
359 | /// Attr ops | |
360 | void setattrs( | |
361 | const hobject_t &hoid, ///< [in] object to write | |
362 | map<string, bufferlist> &attrs ///< [in] attrs, may be cleared | |
363 | ) { | |
364 | auto &op = get_object_op_for_modify(hoid); | |
365 | for (auto &&i: attrs) { | |
28e407b8 AA |
366 | auto& d = op.attr_updates[i.first]; |
367 | d = i.second; | |
368 | d->rebuild(); | |
7c673cae FG |
369 | } |
370 | } | |
371 | void setattr( | |
372 | const hobject_t &hoid, ///< [in] object to write | |
373 | const string &attrname, ///< [in] attr to write | |
374 | bufferlist &bl ///< [in] val to write, may be claimed | |
375 | ) { | |
376 | auto &op = get_object_op_for_modify(hoid); | |
28e407b8 AA |
377 | auto& d = op.attr_updates[attrname]; |
378 | d = bl; | |
379 | d->rebuild(); | |
7c673cae FG |
380 | } |
381 | void rmattr( | |
382 | const hobject_t &hoid, ///< [in] object to write | |
383 | const string &attrname ///< [in] attr to remove | |
384 | ) { | |
385 | auto &op = get_object_op_for_modify(hoid); | |
9f95a23c | 386 | op.attr_updates[attrname] = std::nullopt; |
7c673cae FG |
387 | } |
388 | ||
389 | /// set alloc hint | |
390 | void set_alloc_hint( | |
391 | const hobject_t &hoid, ///< [in] object (must exist) | |
392 | uint64_t expected_object_size, ///< [in] | |
393 | uint64_t expected_write_size, | |
394 | uint32_t flags | |
395 | ) { | |
396 | auto &op = get_object_op_for_modify(hoid); | |
397 | op.alloc_hint = ObjectOperation::alloc_hint_t{ | |
398 | expected_object_size, expected_write_size, flags}; | |
399 | } | |
400 | ||
401 | /// Buffer updates | |
402 | void write( | |
403 | const hobject_t &hoid, ///< [in] object to write | |
404 | uint64_t off, ///< [in] off at which to write | |
405 | uint64_t len, ///< [in] len to write from bl | |
406 | bufferlist &bl, ///< [in] bl to write will be claimed to len | |
407 | uint32_t fadvise_flags = 0 ///< [in] fadvise hint | |
408 | ) { | |
409 | auto &op = get_object_op_for_modify(hoid); | |
11fdf7f2 TL |
410 | ceph_assert(!op.updated_snaps); |
411 | ceph_assert(len > 0); | |
412 | ceph_assert(len == bl.length()); | |
7c673cae FG |
413 | op.buffer_updates.insert( |
414 | off, | |
415 | len, | |
416 | ObjectOperation::BufferUpdate::Write{bl, fadvise_flags}); | |
417 | } | |
418 | void clone_range( | |
419 | const hobject_t &from, ///< [in] from | |
420 | const hobject_t &to, ///< [in] to | |
421 | uint64_t fromoff, ///< [in] offset | |
422 | uint64_t len, ///< [in] len | |
423 | uint64_t tooff ///< [in] offset | |
424 | ) { | |
425 | auto &op = get_object_op_for_modify(to); | |
11fdf7f2 | 426 | ceph_assert(!op.updated_snaps); |
7c673cae FG |
427 | op.buffer_updates.insert( |
428 | tooff, | |
429 | len, | |
430 | ObjectOperation::BufferUpdate::CloneRange{from, fromoff, len}); | |
431 | } | |
432 | void zero( | |
433 | const hobject_t &hoid, ///< [in] object | |
434 | uint64_t off, ///< [in] offset to start zeroing at | |
435 | uint64_t len ///< [in] amount to zero | |
436 | ) { | |
437 | auto &op = get_object_op_for_modify(hoid); | |
11fdf7f2 | 438 | ceph_assert(!op.updated_snaps); |
7c673cae FG |
439 | op.buffer_updates.insert( |
440 | off, | |
441 | len, | |
442 | ObjectOperation::BufferUpdate::Zero{len}); | |
443 | } | |
444 | ||
445 | /// Omap updates | |
446 | void omap_setkeys( | |
447 | const hobject_t &hoid, ///< [in] object to write | |
448 | bufferlist &keys_bl ///< [in] encoded map<string, bufferlist> | |
449 | ) { | |
450 | auto &op = get_object_op_for_modify(hoid); | |
451 | op.omap_updates.emplace_back( | |
452 | make_pair( | |
453 | ObjectOperation::OmapUpdateType::Insert, | |
454 | keys_bl)); | |
455 | } | |
456 | void omap_setkeys( | |
457 | const hobject_t &hoid, ///< [in] object to write | |
458 | map<string, bufferlist> &keys ///< [in] omap keys, may be cleared | |
459 | ) { | |
460 | bufferlist bl; | |
11fdf7f2 | 461 | encode(keys, bl); |
7c673cae FG |
462 | omap_setkeys(hoid, bl); |
463 | } | |
464 | void omap_rmkeys( | |
465 | const hobject_t &hoid, ///< [in] object to write | |
466 | bufferlist &keys_bl ///< [in] encode set<string> | |
467 | ) { | |
468 | auto &op = get_object_op_for_modify(hoid); | |
469 | op.omap_updates.emplace_back( | |
470 | make_pair( | |
471 | ObjectOperation::OmapUpdateType::Remove, | |
472 | keys_bl)); | |
473 | } | |
474 | void omap_rmkeys( | |
475 | const hobject_t &hoid, ///< [in] object to write | |
476 | set<string> &keys ///< [in] omap keys, may be cleared | |
477 | ) { | |
478 | bufferlist bl; | |
11fdf7f2 | 479 | encode(keys, bl); |
7c673cae FG |
480 | omap_rmkeys(hoid, bl); |
481 | } | |
9f95a23c TL |
482 | void omap_rmkeyrange( |
483 | const hobject_t &hoid, ///< [in] object to write | |
484 | bufferlist &range_bl ///< [in] encode string[2] | |
485 | ) { | |
486 | auto &op = get_object_op_for_modify(hoid); | |
487 | op.omap_updates.emplace_back( | |
488 | make_pair( | |
489 | ObjectOperation::OmapUpdateType::RemoveRange, | |
490 | range_bl)); | |
491 | } | |
492 | void omap_rmkeyrange( | |
493 | const hobject_t &hoid, ///< [in] object to write | |
494 | std::string& key_begin, ///< [in] first key in range | |
495 | std::string& key_end ///< [in] first key past range, range is [first,last) | |
496 | ) { | |
497 | bufferlist bl; | |
498 | ::encode(key_begin, bl); | |
499 | ::encode(key_end, bl); | |
500 | omap_rmkeyrange(hoid, bl); | |
501 | } | |
7c673cae FG |
502 | void omap_setheader( |
503 | const hobject_t &hoid, ///< [in] object to write | |
504 | bufferlist &header ///< [in] header | |
505 | ) { | |
506 | auto &op = get_object_op_for_modify(hoid); | |
507 | op.omap_header = header; | |
508 | } | |
509 | ||
510 | bool empty() const { | |
511 | return op_map.empty(); | |
512 | } | |
513 | ||
514 | uint64_t get_bytes_written() const { | |
515 | uint64_t ret = 0; | |
516 | for (auto &&i: op_map) { | |
517 | for (auto &&j: i.second.buffer_updates) { | |
518 | ret += j.get_len(); | |
519 | } | |
520 | } | |
521 | return ret; | |
522 | } | |
523 | ||
524 | void nop( | |
525 | const hobject_t &hoid ///< [in] obj to which we are doing nothing | |
526 | ) { | |
527 | get_object_op_for_modify(hoid); | |
528 | } | |
529 | ||
530 | /* Calls t() on all pair<hobject_t, ObjectOperation> & such that clone/rename | |
531 | * sinks are always called before clone sources | |
532 | * | |
533 | * TODO: add a fast path for the single object case and possibly the single | |
534 | * object clone from source case (make_writeable made a clone). | |
535 | * | |
536 | * This structure only requires that the source->sink graph be acyclic. | |
537 | * This is much more general than is actually required by PrimaryLogPG. | |
538 | * Only 4 flavors of multi-object transactions actually happen: | |
539 | * 1) rename temp -> object for copyfrom | |
540 | * 2) clone head -> clone, modify head for make_writeable on normal head write | |
541 | * 3) clone clone -> head for rollback | |
542 | * 4) 2 + 3 | |
543 | * | |
544 | * We can bypass the below logic for single object transactions trivially | |
545 | * (including case 1 above since temp doesn't show up again). | |
546 | * For 2-3, we could add something ad-hoc to ensure that they happen in the | |
547 | * right order, but it actually seems easier to just do the graph construction. | |
548 | */ | |
549 | template <typename T> | |
550 | void safe_create_traverse(T &&t) { | |
551 | map<hobject_t, list<hobject_t>> dgraph; | |
552 | list<hobject_t> stack; | |
553 | ||
554 | // Populate stack with roots, dgraph with edges | |
555 | for (auto &&opair: op_map) { | |
556 | hobject_t source; | |
557 | if (opair.second.has_source(&source)) { | |
558 | auto &l = dgraph[source]; | |
559 | if (l.empty() && !op_map.count(source)) { | |
560 | /* Source oids not in op_map need to be added as roots | |
561 | * (but only once!) */ | |
562 | stack.push_back(source); | |
563 | } | |
564 | l.push_back(opair.first); | |
565 | } else { | |
566 | stack.push_back(opair.first); | |
567 | } | |
568 | } | |
569 | ||
570 | /* Why don't we need to worry about accessing the same node | |
571 | * twice? dgraph nodes always have in-degree at most 1 because | |
572 | * the inverse graph nodes (source->dest) can have out-degree | |
573 | * at most 1 (only one possible source). We do a post-order | |
574 | * depth-first traversal here to ensure we call f on children | |
575 | * before parents. | |
576 | */ | |
577 | while (!stack.empty()) { | |
578 | hobject_t &cur = stack.front(); | |
579 | auto diter = dgraph.find(cur); | |
580 | if (diter == dgraph.end()) { | |
581 | /* Leaf: pop and call t() */ | |
582 | auto opiter = op_map.find(cur); | |
583 | if (opiter != op_map.end()) | |
584 | t(*opiter); | |
585 | stack.pop_front(); | |
586 | } else { | |
587 | /* Internal node: push children onto stack, remove edge, | |
588 | * recurse. When this node is encountered again, it'll | |
589 | * be a leaf */ | |
11fdf7f2 | 590 | ceph_assert(!diter->second.empty()); |
7c673cae FG |
591 | stack.splice(stack.begin(), diter->second); |
592 | dgraph.erase(diter); | |
593 | } | |
594 | } | |
595 | } | |
596 | }; | |
597 | using PGTransactionUPtr = std::unique_ptr<PGTransaction>; | |
598 | ||
599 | #endif |