rss-tools/vendor/go.etcd.io/bbolt/tx_check.go (view raw)
| 1 | package bbolt |
| 2 | |
| 3 | import ( |
| 4 | "encoding/hex" |
| 5 | "fmt" |
| 6 | |
| 7 | "go.etcd.io/bbolt/internal/common" |
| 8 | ) |
| 9 | |
| 10 | // Check performs several consistency checks on the database for this transaction. |
| 11 | // An error is returned if any inconsistency is found. |
| 12 | // |
| 13 | // It can be safely run concurrently on a writable transaction. However, this |
| 14 | // incurs a high cost for large databases and databases with a lot of subbuckets |
| 15 | // because of caching. This overhead can be removed if running on a read-only |
| 16 | // transaction, however, it is not safe to execute other writer transactions at |
| 17 | // the same time. |
| 18 | // |
| 19 | // It also allows users to provide a customized `KVStringer` implementation, |
| 20 | // so that bolt can generate human-readable diagnostic messages. |
| 21 | func (tx *Tx) Check(options ...CheckOption) <-chan error { |
| 22 | chkConfig := checkConfig{ |
| 23 | kvStringer: HexKVStringer(), |
| 24 | } |
| 25 | for _, op := range options { |
| 26 | op(&chkConfig) |
| 27 | } |
| 28 | |
| 29 | ch := make(chan error) |
| 30 | go func() { |
| 31 | // Close the channel to signal completion. |
| 32 | defer close(ch) |
| 33 | tx.check(chkConfig, ch) |
| 34 | }() |
| 35 | return ch |
| 36 | } |
| 37 | |
| 38 | func (tx *Tx) check(cfg checkConfig, ch chan error) { |
| 39 | // Force loading free list if opened in ReadOnly mode. |
| 40 | tx.db.loadFreelist() |
| 41 | |
| 42 | // Check if any pages are double freed. |
| 43 | freed := make(map[common.Pgid]bool) |
| 44 | all := make([]common.Pgid, tx.db.freelist.Count()) |
| 45 | tx.db.freelist.Copyall(all) |
| 46 | for _, id := range all { |
| 47 | if freed[id] { |
| 48 | ch <- fmt.Errorf("page %d: already freed", id) |
| 49 | } |
| 50 | freed[id] = true |
| 51 | } |
| 52 | |
| 53 | // Track every reachable page. |
| 54 | reachable := make(map[common.Pgid]*common.Page) |
| 55 | reachable[0] = tx.page(0) // meta0 |
| 56 | reachable[1] = tx.page(1) // meta1 |
| 57 | if tx.meta.Freelist() != common.PgidNoFreelist { |
| 58 | for i := uint32(0); i <= tx.page(tx.meta.Freelist()).Overflow(); i++ { |
| 59 | reachable[tx.meta.Freelist()+common.Pgid(i)] = tx.page(tx.meta.Freelist()) |
| 60 | } |
| 61 | } |
| 62 | |
| 63 | if cfg.pageId == 0 { |
| 64 | // Check the whole db file, starting from the root bucket and |
| 65 | // recursively check all child buckets. |
| 66 | tx.recursivelyCheckBucket(&tx.root, reachable, freed, cfg.kvStringer, ch) |
| 67 | |
| 68 | // Ensure all pages below high water mark are either reachable or freed. |
| 69 | for i := common.Pgid(0); i < tx.meta.Pgid(); i++ { |
| 70 | _, isReachable := reachable[i] |
| 71 | if !isReachable && !freed[i] { |
| 72 | ch <- fmt.Errorf("page %d: unreachable unfreed", int(i)) |
| 73 | } |
| 74 | } |
| 75 | } else { |
| 76 | // Check the db file starting from a specified pageId. |
| 77 | if cfg.pageId < 2 || cfg.pageId >= uint64(tx.meta.Pgid()) { |
| 78 | ch <- fmt.Errorf("page ID (%d) out of range [%d, %d)", cfg.pageId, 2, tx.meta.Pgid()) |
| 79 | return |
| 80 | } |
| 81 | |
| 82 | tx.recursivelyCheckPage(common.Pgid(cfg.pageId), reachable, freed, cfg.kvStringer, ch) |
| 83 | } |
| 84 | } |
| 85 | |
| 86 | func (tx *Tx) recursivelyCheckPage(pageId common.Pgid, reachable map[common.Pgid]*common.Page, freed map[common.Pgid]bool, |
| 87 | kvStringer KVStringer, ch chan error) { |
| 88 | tx.checkInvariantProperties(pageId, reachable, freed, kvStringer, ch) |
| 89 | tx.recursivelyCheckBucketInPage(pageId, reachable, freed, kvStringer, ch) |
| 90 | } |
| 91 | |
| 92 | func (tx *Tx) recursivelyCheckBucketInPage(pageId common.Pgid, reachable map[common.Pgid]*common.Page, freed map[common.Pgid]bool, |
| 93 | kvStringer KVStringer, ch chan error) { |
| 94 | p := tx.page(pageId) |
| 95 | |
| 96 | switch { |
| 97 | case p.IsBranchPage(): |
| 98 | for i := range p.BranchPageElements() { |
| 99 | elem := p.BranchPageElement(uint16(i)) |
| 100 | tx.recursivelyCheckBucketInPage(elem.Pgid(), reachable, freed, kvStringer, ch) |
| 101 | } |
| 102 | case p.IsLeafPage(): |
| 103 | for i := range p.LeafPageElements() { |
| 104 | elem := p.LeafPageElement(uint16(i)) |
| 105 | if elem.IsBucketEntry() { |
| 106 | inBkt := common.NewInBucket(pageId, 0) |
| 107 | tmpBucket := Bucket{ |
| 108 | InBucket: &inBkt, |
| 109 | rootNode: &node{isLeaf: p.IsLeafPage()}, |
| 110 | FillPercent: DefaultFillPercent, |
| 111 | tx: tx, |
| 112 | } |
| 113 | if child := tmpBucket.Bucket(elem.Key()); child != nil { |
| 114 | tx.recursivelyCheckBucket(child, reachable, freed, kvStringer, ch) |
| 115 | } |
| 116 | } |
| 117 | } |
| 118 | default: |
| 119 | ch <- fmt.Errorf("unexpected page type (flags: %x) for pgId:%d", p.Flags(), pageId) |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | func (tx *Tx) recursivelyCheckBucket(b *Bucket, reachable map[common.Pgid]*common.Page, freed map[common.Pgid]bool, |
| 124 | kvStringer KVStringer, ch chan error) { |
| 125 | // Ignore inline buckets. |
| 126 | if b.RootPage() == 0 { |
| 127 | return |
| 128 | } |
| 129 | |
| 130 | tx.checkInvariantProperties(b.RootPage(), reachable, freed, kvStringer, ch) |
| 131 | |
| 132 | // Check each bucket within this bucket. |
| 133 | _ = b.ForEachBucket(func(k []byte) error { |
| 134 | if child := b.Bucket(k); child != nil { |
| 135 | tx.recursivelyCheckBucket(child, reachable, freed, kvStringer, ch) |
| 136 | } |
| 137 | return nil |
| 138 | }) |
| 139 | } |
| 140 | |
| 141 | func (tx *Tx) checkInvariantProperties(pageId common.Pgid, reachable map[common.Pgid]*common.Page, freed map[common.Pgid]bool, |
| 142 | kvStringer KVStringer, ch chan error) { |
| 143 | tx.forEachPage(pageId, func(p *common.Page, _ int, stack []common.Pgid) { |
| 144 | verifyPageReachable(p, tx.meta.Pgid(), stack, reachable, freed, ch) |
| 145 | }) |
| 146 | |
| 147 | tx.recursivelyCheckPageKeyOrder(pageId, kvStringer.KeyToString, ch) |
| 148 | } |
| 149 | |
| 150 | func verifyPageReachable(p *common.Page, hwm common.Pgid, stack []common.Pgid, reachable map[common.Pgid]*common.Page, freed map[common.Pgid]bool, ch chan error) { |
| 151 | if p.Id() > hwm { |
| 152 | ch <- fmt.Errorf("page %d: out of bounds: %d (stack: %v)", int(p.Id()), int(hwm), stack) |
| 153 | } |
| 154 | |
| 155 | // Ensure each page is only referenced once. |
| 156 | for i := common.Pgid(0); i <= common.Pgid(p.Overflow()); i++ { |
| 157 | var id = p.Id() + i |
| 158 | if _, ok := reachable[id]; ok { |
| 159 | ch <- fmt.Errorf("page %d: multiple references (stack: %v)", int(id), stack) |
| 160 | } |
| 161 | reachable[id] = p |
| 162 | } |
| 163 | |
| 164 | // We should only encounter un-freed leaf and branch pages. |
| 165 | if freed[p.Id()] { |
| 166 | ch <- fmt.Errorf("page %d: reachable freed", int(p.Id())) |
| 167 | } else if !p.IsBranchPage() && !p.IsLeafPage() { |
| 168 | ch <- fmt.Errorf("page %d: invalid type: %s (stack: %v)", int(p.Id()), p.Typ(), stack) |
| 169 | } |
| 170 | } |
| 171 | |
| 172 | // recursivelyCheckPageKeyOrder verifies database consistency with respect to b-tree |
| 173 | // key order constraints: |
| 174 | // - keys on pages must be sorted |
| 175 | // - keys on children pages are between 2 consecutive keys on the parent's branch page). |
| 176 | func (tx *Tx) recursivelyCheckPageKeyOrder(pgId common.Pgid, keyToString func([]byte) string, ch chan error) { |
| 177 | tx.recursivelyCheckPageKeyOrderInternal(pgId, nil, nil, nil, keyToString, ch) |
| 178 | } |
| 179 | |
| 180 | // recursivelyCheckPageKeyOrderInternal verifies that all keys in the subtree rooted at `pgid` are: |
| 181 | // - >=`minKeyClosed` (can be nil) |
| 182 | // - <`maxKeyOpen` (can be nil) |
| 183 | // - Are in right ordering relationship to their parents. |
| 184 | // `pagesStack` is expected to contain IDs of pages from the tree root to `pgid` for the clean debugging message. |
| 185 | func (tx *Tx) recursivelyCheckPageKeyOrderInternal( |
| 186 | pgId common.Pgid, minKeyClosed, maxKeyOpen []byte, pagesStack []common.Pgid, |
| 187 | keyToString func([]byte) string, ch chan error) (maxKeyInSubtree []byte) { |
| 188 | |
| 189 | p := tx.page(pgId) |
| 190 | pagesStack = append(pagesStack, pgId) |
| 191 | switch { |
| 192 | case p.IsBranchPage(): |
| 193 | // For branch page we navigate ranges of all subpages. |
| 194 | runningMin := minKeyClosed |
| 195 | for i := range p.BranchPageElements() { |
| 196 | elem := p.BranchPageElement(uint16(i)) |
| 197 | verifyKeyOrder(elem.Pgid(), "branch", i, elem.Key(), runningMin, maxKeyOpen, ch, keyToString, pagesStack) |
| 198 | |
| 199 | maxKey := maxKeyOpen |
| 200 | if i < len(p.BranchPageElements())-1 { |
| 201 | maxKey = p.BranchPageElement(uint16(i + 1)).Key() |
| 202 | } |
| 203 | maxKeyInSubtree = tx.recursivelyCheckPageKeyOrderInternal(elem.Pgid(), elem.Key(), maxKey, pagesStack, keyToString, ch) |
| 204 | runningMin = maxKeyInSubtree |
| 205 | } |
| 206 | return maxKeyInSubtree |
| 207 | case p.IsLeafPage(): |
| 208 | runningMin := minKeyClosed |
| 209 | for i := range p.LeafPageElements() { |
| 210 | elem := p.LeafPageElement(uint16(i)) |
| 211 | verifyKeyOrder(pgId, "leaf", i, elem.Key(), runningMin, maxKeyOpen, ch, keyToString, pagesStack) |
| 212 | runningMin = elem.Key() |
| 213 | } |
| 214 | if p.Count() > 0 { |
| 215 | return p.LeafPageElement(p.Count() - 1).Key() |
| 216 | } |
| 217 | default: |
| 218 | ch <- fmt.Errorf("unexpected page type (flags: %x) for pgId:%d", p.Flags(), pgId) |
| 219 | } |
| 220 | return maxKeyInSubtree |
| 221 | } |
| 222 | |
| 223 | /*** |
| 224 | * verifyKeyOrder checks whether an entry with given #index on pgId (pageType: "branch|leaf") that has given "key", |
| 225 | * is within range determined by (previousKey..maxKeyOpen) and reports found violations to the channel (ch). |
| 226 | */ |
| 227 | func verifyKeyOrder(pgId common.Pgid, pageType string, index int, key []byte, previousKey []byte, maxKeyOpen []byte, ch chan error, keyToString func([]byte) string, pagesStack []common.Pgid) { |
| 228 | if index == 0 && previousKey != nil && compareKeys(previousKey, key) > 0 { |
| 229 | ch <- fmt.Errorf("the first key[%d]=(hex)%s on %s page(%d) needs to be >= the key in the ancestor (%s). Stack: %v", |
| 230 | index, keyToString(key), pageType, pgId, keyToString(previousKey), pagesStack) |
| 231 | } |
| 232 | if index > 0 { |
| 233 | cmpRet := compareKeys(previousKey, key) |
| 234 | if cmpRet > 0 { |
| 235 | ch <- fmt.Errorf("key[%d]=(hex)%s on %s page(%d) needs to be > (found <) than previous element (hex)%s. Stack: %v", |
| 236 | index, keyToString(key), pageType, pgId, keyToString(previousKey), pagesStack) |
| 237 | } |
| 238 | if cmpRet == 0 { |
| 239 | ch <- fmt.Errorf("key[%d]=(hex)%s on %s page(%d) needs to be > (found =) than previous element (hex)%s. Stack: %v", |
| 240 | index, keyToString(key), pageType, pgId, keyToString(previousKey), pagesStack) |
| 241 | } |
| 242 | } |
| 243 | if maxKeyOpen != nil && compareKeys(key, maxKeyOpen) >= 0 { |
| 244 | ch <- fmt.Errorf("key[%d]=(hex)%s on %s page(%d) needs to be < than key of the next element in ancestor (hex)%s. Pages stack: %v", |
| 245 | index, keyToString(key), pageType, pgId, keyToString(previousKey), pagesStack) |
| 246 | } |
| 247 | } |
| 248 | |
| 249 | // =========================================================================================== |
| 250 | |
| 251 | type checkConfig struct { |
| 252 | kvStringer KVStringer |
| 253 | pageId uint64 |
| 254 | } |
| 255 | |
| 256 | type CheckOption func(options *checkConfig) |
| 257 | |
| 258 | func WithKVStringer(kvStringer KVStringer) CheckOption { |
| 259 | return func(c *checkConfig) { |
| 260 | c.kvStringer = kvStringer |
| 261 | } |
| 262 | } |
| 263 | |
| 264 | // WithPageId sets a page ID from which the check command starts to check |
| 265 | func WithPageId(pageId uint64) CheckOption { |
| 266 | return func(c *checkConfig) { |
| 267 | c.pageId = pageId |
| 268 | } |
| 269 | } |
| 270 | |
| 271 | // KVStringer allows to prepare human-readable diagnostic messages. |
| 272 | type KVStringer interface { |
| 273 | KeyToString([]byte) string |
| 274 | ValueToString([]byte) string |
| 275 | } |
| 276 | |
| 277 | // HexKVStringer serializes both key & value to hex representation. |
| 278 | func HexKVStringer() KVStringer { |
| 279 | return hexKvStringer{} |
| 280 | } |
| 281 | |
| 282 | type hexKvStringer struct{} |
| 283 | |
| 284 | func (_ hexKvStringer) KeyToString(key []byte) string { |
| 285 | return hex.EncodeToString(key) |
| 286 | } |
| 287 | |
| 288 | func (_ hexKvStringer) ValueToString(value []byte) string { |
| 289 | return hex.EncodeToString(value) |
| 290 | } |