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
13#include <unordered_map>
14
15using namespace std;
16
17namespace duckdb {
18constexpr uint32_t DEFAULT_UNDO_CHUNK_SIZE = 4096 * 3;
19constexpr uint32_t UNDO_ENTRY_HEADER_SIZE = sizeof(UndoFlags) + sizeof(uint32_t);
20
21UndoBuffer::UndoBuffer() {
22 head = make_unique<UndoChunk>(0);
23 tail = head.get();
24}
25
26UndoChunk::UndoChunk(idx_t size) : current_position(0), maximum_size(size), prev(nullptr) {
27 if (size > 0) {
28 data = unique_ptr<data_t[]>(new data_t[maximum_size]);
29 }
30}
31UndoChunk::~UndoChunk() {
32 if (next) {
33 auto current_next = move(next);
34 while (current_next) {
35 current_next = move(current_next->next);
36 }
37 }
38}
39
40data_ptr_t UndoChunk::WriteEntry(UndoFlags type, uint32_t len) {
41 *((UndoFlags *)(data.get() + current_position)) = type;
42 current_position += sizeof(UndoFlags);
43 *((uint32_t *)(data.get() + current_position)) = len;
44 current_position += sizeof(uint32_t);
45
46 data_ptr_t result = data.get() + current_position;
47 current_position += len;
48 return result;
49}
50
51data_ptr_t UndoBuffer::CreateEntry(UndoFlags type, idx_t len) {
52 assert(len <= std::numeric_limits<uint32_t>::max());
53 idx_t needed_space = len + UNDO_ENTRY_HEADER_SIZE;
54 if (head->current_position + needed_space >= head->maximum_size) {
55 auto new_chunk =
56 make_unique<UndoChunk>(needed_space > DEFAULT_UNDO_CHUNK_SIZE ? needed_space : DEFAULT_UNDO_CHUNK_SIZE);
57 head->prev = new_chunk.get();
58 new_chunk->next = move(head);
59 head = move(new_chunk);
60 }
61 return head->WriteEntry(type, len);
62}
63
64template <class T> void UndoBuffer::IterateEntries(UndoBuffer::IteratorState &state, T &&callback) {
65 // iterate in insertion order: start with the tail
66 state.current = tail;
67 while (state.current) {
68 state.start = state.current->data.get();
69 state.end = state.start + state.current->current_position;
70 while (state.start < state.end) {
71 UndoFlags type = *((UndoFlags *)state.start);
72 state.start += sizeof(UndoFlags);
73 uint32_t len = *((uint32_t *)state.start);
74 state.start += sizeof(uint32_t);
75 callback(type, state.start);
76 state.start += len;
77 }
78 state.current = state.current->prev;
79 }
80}
81
82template <class T>
83void UndoBuffer::IterateEntries(UndoBuffer::IteratorState &state, UndoBuffer::IteratorState &end_state, T &&callback) {
84 // iterate in insertion order: start with the tail
85 state.current = tail;
86 while (state.current) {
87 state.start = state.current->data.get();
88 state.end =
89 state.current == end_state.current ? end_state.start : state.start + state.current->current_position;
90 while (state.start < state.end) {
91 UndoFlags type = *((UndoFlags *)state.start);
92 state.start += sizeof(UndoFlags);
93 uint32_t len = *((uint32_t *)state.start);
94 state.start += sizeof(uint32_t);
95 callback(type, state.start);
96 state.start += len;
97 }
98 if (state.current == end_state.current) {
99 // finished executing until the current end state
100 return;
101 }
102 state.current = state.current->prev;
103 }
104}
105
106template <class T> void UndoBuffer::ReverseIterateEntries(T &&callback) {
107 // iterate in reverse insertion order: start with the head
108 auto current = head.get();
109 while (current) {
110 data_ptr_t start = current->data.get();
111 data_ptr_t end = start + current->current_position;
112 // create a vector with all nodes in this chunk
113 vector<pair<UndoFlags, data_ptr_t>> nodes;
114 while (start < end) {
115 UndoFlags type = *((UndoFlags *)start);
116 start += sizeof(UndoFlags);
117 uint32_t len = *((uint32_t *)start);
118 start += sizeof(uint32_t);
119 nodes.push_back(make_pair(type, start));
120 start += len;
121 }
122 // iterate over it in reverse order
123 for (idx_t i = nodes.size(); i > 0; i--) {
124 callback(nodes[i - 1].first, nodes[i - 1].second);
125 }
126 current = current->next.get();
127 }
128}
129
130bool UndoBuffer::ChangesMade() {
131 return head->maximum_size > 0;
132}
133
134void UndoBuffer::Cleanup() {
135 // garbage collect everything in the Undo Chunk
136 // this should only happen if
137 // (1) the transaction this UndoBuffer belongs to has successfully
138 // committed
139 // (on Rollback the Rollback() function should be called, that clears
140 // the chunks)
141 // (2) there is no active transaction with start_id < commit_id of this
142 // transaction
143 CleanupState state;
144 UndoBuffer::IteratorState iterator_state;
145 IterateEntries(iterator_state, [&](UndoFlags type, data_ptr_t data) { state.CleanupEntry(type, data); });
146}
147
148void UndoBuffer::Commit(UndoBuffer::IteratorState &iterator_state, WriteAheadLog *log, transaction_t commit_id) {
149 CommitState state(commit_id, log);
150 if (log) {
151 // commit WITH write ahead log
152 IterateEntries(iterator_state, [&](UndoFlags type, data_ptr_t data) { state.CommitEntry<true>(type, data); });
153 } else {
154 // comit WITHOUT write ahead log
155 IterateEntries(iterator_state, [&](UndoFlags type, data_ptr_t data) { state.CommitEntry<false>(type, data); });
156 }
157}
158
159void UndoBuffer::RevertCommit(UndoBuffer::IteratorState &end_state, transaction_t transaction_id) {
160 CommitState state(transaction_id, nullptr);
161 UndoBuffer::IteratorState start_state;
162 IterateEntries(start_state, end_state, [&](UndoFlags type, data_ptr_t data) { state.RevertCommit(type, data); });
163}
164
165void UndoBuffer::Rollback() noexcept {
166 // rollback needs to be performed in reverse
167 RollbackState state;
168 ReverseIterateEntries([&](UndoFlags type, data_ptr_t data) { state.RollbackEntry(type, data); });
169}
170} // namespace duckdb
171