1#include "duckdb/transaction/undo_buffer.hpp"
2
3#include "duckdb/catalog/catalog_entry.hpp"
4#include "duckdb/catalog/catalog_entry/list.hpp"
5#include "duckdb/catalog/catalog_set.hpp"
6#include "duckdb/common/exception.hpp"
7#include "duckdb/storage/data_table.hpp"
8#include "duckdb/storage/write_ahead_log.hpp"
9#include "duckdb/transaction/cleanup_state.hpp"
10#include "duckdb/transaction/commit_state.hpp"
11#include "duckdb/transaction/rollback_state.hpp"
12#include "duckdb/common/pair.hpp"
13
14#include <unordered_map>
15
16namespace duckdb {
17constexpr uint32_t UNDO_ENTRY_HEADER_SIZE = sizeof(UndoFlags) + sizeof(uint32_t);
18
19UndoBuffer::UndoBuffer(ClientContext &context_p) : context(context_p), allocator(BufferAllocator::Get(context&: context_p)) {
20}
21
22data_ptr_t UndoBuffer::CreateEntry(UndoFlags type, idx_t len) {
23 D_ASSERT(len <= NumericLimits<uint32_t>::Maximum());
24 len = AlignValue(n: len);
25 idx_t needed_space = len + UNDO_ENTRY_HEADER_SIZE;
26 auto data = allocator.Allocate(size: needed_space);
27 Store<UndoFlags>(val: type, ptr: data);
28 data += sizeof(UndoFlags);
29 Store<uint32_t>(val: len, ptr: data);
30 data += sizeof(uint32_t);
31 return data;
32}
33
34template <class T>
35void UndoBuffer::IterateEntries(UndoBuffer::IteratorState &state, T &&callback) {
36 // iterate in insertion order: start with the tail
37 state.current = allocator.GetTail();
38 while (state.current) {
39 state.start = state.current->data.get();
40 state.end = state.start + state.current->current_position;
41 while (state.start < state.end) {
42 UndoFlags type = Load<UndoFlags>(ptr: state.start);
43 state.start += sizeof(UndoFlags);
44
45 uint32_t len = Load<uint32_t>(ptr: state.start);
46 state.start += sizeof(uint32_t);
47 callback(type, state.start);
48 state.start += len;
49 }
50 state.current = state.current->prev;
51 }
52}
53
54template <class T>
55void UndoBuffer::IterateEntries(UndoBuffer::IteratorState &state, UndoBuffer::IteratorState &end_state, T &&callback) {
56 // iterate in insertion order: start with the tail
57 state.current = allocator.GetTail();
58 while (state.current) {
59 state.start = state.current->data.get();
60 state.end =
61 state.current == end_state.current ? end_state.start : state.start + state.current->current_position;
62 while (state.start < state.end) {
63 auto type = Load<UndoFlags>(ptr: state.start);
64 state.start += sizeof(UndoFlags);
65 auto len = Load<uint32_t>(ptr: state.start);
66 state.start += sizeof(uint32_t);
67 callback(type, state.start);
68 state.start += len;
69 }
70 if (state.current == end_state.current) {
71 // finished executing until the current end state
72 return;
73 }
74 state.current = state.current->prev;
75 }
76}
77
78template <class T>
79void UndoBuffer::ReverseIterateEntries(T &&callback) {
80 // iterate in reverse insertion order: start with the head
81 auto current = allocator.GetHead();
82 while (current) {
83 data_ptr_t start = current->data.get();
84 data_ptr_t end = start + current->current_position;
85 // create a vector with all nodes in this chunk
86 vector<pair<UndoFlags, data_ptr_t>> nodes;
87 while (start < end) {
88 auto type = Load<UndoFlags>(ptr: start);
89 start += sizeof(UndoFlags);
90 auto len = Load<uint32_t>(ptr: start);
91 start += sizeof(uint32_t);
92 nodes.emplace_back(args&: type, args&: start);
93 start += len;
94 }
95 // iterate over it in reverse order
96 for (idx_t i = nodes.size(); i > 0; i--) {
97 callback(nodes[i - 1].first, nodes[i - 1].second);
98 }
99 current = current->next.get();
100 }
101}
102
103bool UndoBuffer::ChangesMade() {
104 return !allocator.IsEmpty();
105}
106
107idx_t UndoBuffer::EstimatedSize() {
108 idx_t estimated_size = 0;
109 auto node = allocator.GetHead();
110 while (node) {
111 estimated_size += node->current_position;
112 node = node->next.get();
113 }
114 return estimated_size;
115}
116
117void UndoBuffer::Cleanup() {
118 // garbage collect everything in the Undo Chunk
119 // this should only happen if
120 // (1) the transaction this UndoBuffer belongs to has successfully
121 // committed
122 // (on Rollback the Rollback() function should be called, that clears
123 // the chunks)
124 // (2) there is no active transaction with start_id < commit_id of this
125 // transaction
126 CleanupState state;
127 UndoBuffer::IteratorState iterator_state;
128 IterateEntries(state&: iterator_state, callback: [&](UndoFlags type, data_ptr_t data) { state.CleanupEntry(type, data); });
129
130 // possibly vacuum indexes
131 for (const auto &table : state.indexed_tables) {
132 table.second->info->indexes.Scan(callback: [&](Index &index) {
133 index.Vacuum();
134 return false;
135 });
136 }
137}
138
139void UndoBuffer::Commit(UndoBuffer::IteratorState &iterator_state, optional_ptr<WriteAheadLog> log,
140 transaction_t commit_id) {
141 CommitState state(context, commit_id, log);
142 if (log) {
143 // commit WITH write ahead log
144 IterateEntries(state&: iterator_state, callback: [&](UndoFlags type, data_ptr_t data) { state.CommitEntry<true>(type, data); });
145 } else {
146 // commit WITHOUT write ahead log
147 IterateEntries(state&: iterator_state, callback: [&](UndoFlags type, data_ptr_t data) { state.CommitEntry<false>(type, data); });
148 }
149}
150
151void UndoBuffer::RevertCommit(UndoBuffer::IteratorState &end_state, transaction_t transaction_id) {
152 CommitState state(context, transaction_id, nullptr);
153 UndoBuffer::IteratorState start_state;
154 IterateEntries(state&: start_state, end_state, callback: [&](UndoFlags type, data_ptr_t data) { state.RevertCommit(type, data); });
155}
156
157void UndoBuffer::Rollback() noexcept {
158 // rollback needs to be performed in reverse
159 RollbackState state;
160 ReverseIterateEntries(callback: [&](UndoFlags type, data_ptr_t data) { state.RollbackEntry(type, data); });
161}
162} // namespace duckdb
163