1/* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2// vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4:
3#ident "$Id$"
4/*======
5This file is part of PerconaFT.
6
7
8Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved.
9
10 PerconaFT is free software: you can redistribute it and/or modify
11 it under the terms of the GNU General Public License, version 2,
12 as published by the Free Software Foundation.
13
14 PerconaFT is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
21
22----------------------------------------
23
24 PerconaFT is free software: you can redistribute it and/or modify
25 it under the terms of the GNU Affero General Public License, version 3,
26 as published by the Free Software Foundation.
27
28 PerconaFT is distributed in the hope that it will be useful,
29 but WITHOUT ANY WARRANTY; without even the implied warranty of
30 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
31 GNU Affero General Public License for more details.
32
33 You should have received a copy of the GNU Affero General Public License
34 along with PerconaFT. If not, see <http://www.gnu.org/licenses/>.
35======= */
36
37#ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved."
38
39#pragma once
40
41#include <db.h>
42
43#include "portability/toku_pthread.h"
44#include "portability/toku_stdint.h"
45#include "portability/toku_stdlib.h"
46#include "ft/serialize/rbtree_mhs.h"
47
48// Block allocator.
49//
50// A block allocator manages the allocation of variable-sized blocks.
51// The translation of block numbers to addresses is handled elsewhere.
52// The allocation of block numbers is handled elsewhere.
53//
54// When creating a block allocator we also specify a certain-sized
55// block at the beginning that is preallocated (and cannot be allocated or
56// freed)
57//
58// We can allocate blocks of a particular size at a particular location.
59// We can free blocks.
60// We can determine the size of a block.
61#define MAX_BYTE 0xffffffffffffffff
62class BlockAllocator {
63 public:
64 static const size_t BLOCK_ALLOCATOR_ALIGNMENT = 4096;
65
66 // How much must be reserved at the beginning for the block?
67 // The actual header is 8+4+4+8+8_4+8+ the length of the db names + 1
68 // pointer for each root.
69 // So 4096 should be enough.
70 static const size_t BLOCK_ALLOCATOR_HEADER_RESERVE = 4096;
71
72 static_assert(BLOCK_ALLOCATOR_HEADER_RESERVE % BLOCK_ALLOCATOR_ALIGNMENT ==
73 0,
74 "block allocator header must have proper alignment");
75
76 static const size_t BLOCK_ALLOCATOR_TOTAL_HEADER_RESERVE =
77 BLOCK_ALLOCATOR_HEADER_RESERVE * 2;
78
79 struct BlockPair {
80 uint64_t _offset;
81 uint64_t _size;
82 BlockPair(uint64_t o, uint64_t s) : _offset(o), _size(s) {}
83 int operator<(const struct BlockPair &rhs) const {
84 return _offset < rhs._offset;
85 }
86 int operator<(const uint64_t &o) const { return _offset < o; }
87 };
88
89 // Effect: Create a block allocator, in which the first RESERVE_AT_BEGINNING
90 // bytes are not put into a block.
91 // The default allocation strategy is first fit
92 // (BA_STRATEGY_FIRST_FIT)
93 // All blocks be start on a multiple of ALIGNMENT.
94 // Aborts if we run out of memory.
95 // Parameters
96 // reserve_at_beginning (IN) Size of reserved block at beginning.
97 // This size does not have to be aligned.
98 // alignment (IN) Block alignment.
99 void Create(uint64_t reserve_at_beginning, uint64_t alignment);
100
101 // Effect: Create a block allocator, in which the first RESERVE_AT_BEGINNING
102 // bytes are not put into a block.
103 // The allocator is initialized to contain `n_blocks' of BlockPairs,
104 // taken from `pairs'
105 // All blocks be start on a multiple of ALIGNMENT.
106 // Aborts if we run out of memory.
107 // Parameters
108 // pairs, unowned array of pairs to copy
109 // n_blocks, Size of pairs array
110 // reserve_at_beginning (IN) Size of reserved block at beginning.
111 // This size does not have to be aligned.
112 // alignment (IN) Block alignment.
113 void CreateFromBlockPairs(uint64_t reserve_at_beginning,
114 uint64_t alignment,
115 struct BlockPair *pairs,
116 uint64_t n_blocks);
117
118 // Effect: Destroy this block allocator
119 void Destroy();
120
121 // Effect: Allocate a block of the specified size at an address chosen by
122 // the allocator.
123 // Aborts if anything goes wrong.
124 // The block address will be a multiple of the alignment.
125 // Parameters:
126 // size (IN): The size of the block. (The size does not have to be
127 // aligned.)
128 // offset (OUT): The location of the block.
129 // block soon (perhaps in the next checkpoint)
130 // Heat values are lexiographically ordered (like integers),
131 // but their specific values are arbitrary
132 void AllocBlock(uint64_t size, uint64_t *offset);
133
134 // Effect: Free the block at offset.
135 // Requires: There must be a block currently allocated at that offset.
136 // Parameters:
137 // offset (IN): The offset of the block.
138 void FreeBlock(uint64_t offset, uint64_t size);
139
140 // Effect: Check to see if the block allocator is OK. This may take a long
141 // time.
142 // Usage Hints: Probably only use this for unit tests.
143 // TODO: Private?
144 void Validate() const;
145
146 // Effect: Return the unallocated block address of "infinite" size.
147 // That is, return the smallest address that is above all the allocated
148 // blocks.
149 uint64_t AllocatedLimit() const;
150
151 // Effect: Consider the blocks in sorted order. The reserved block at the
152 // beginning is number 0. The next one is number 1 and so forth.
153 // Return the offset and size of the block with that number.
154 // Return 0 if there is a block that big, return nonzero if b is too big.
155 // Rationale: This is probably useful only for tests.
156 int NthBlockInLayoutOrder(uint64_t b, uint64_t *offset, uint64_t *size);
157
158 // Effect: Fill in report to indicate how the file is used.
159 // Requires:
160 // report->file_size_bytes is filled in
161 // report->data_bytes is filled in
162 // report->checkpoint_bytes_additional is filled in
163 void UnusedStatistics(TOKU_DB_FRAGMENTATION report);
164
165 // Effect: Fill in report->data_bytes with the number of bytes in use
166 // Fill in report->data_blocks with the number of BlockPairs in use
167 // Fill in unused statistics using this->get_unused_statistics()
168 // Requires:
169 // report->file_size is ignored on return
170 // report->checkpoint_bytes_additional is ignored on return
171 void Statistics(TOKU_DB_FRAGMENTATION report);
172
173 virtual ~BlockAllocator(){};
174
175 private:
176 void CreateInternal(uint64_t reserve_at_beginning, uint64_t alignment);
177
178 // How much to reserve at the beginning
179 uint64_t _reserve_at_beginning;
180 // Block alignment
181 uint64_t _alignment;
182 // How many blocks
183 uint64_t _n_blocks;
184 uint64_t _n_bytes_in_use;
185
186 // These blocks are sorted by address.
187 MhsRbTree::Tree *_tree;
188};
189