mirror of
https://github.com/kaspanet/kaspad.git
synced 2025-09-13 13:00:10 +00:00
6 Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
Mike Zak
|
e87d00c9cf |
[NOD-1063] Fix a bug in which a block is pointing directly to a block in the selected parent chain below the reindex root
commit e303efef4209b8d62f1aac2cb57ac79829411556
Author: stasatdaglabs <stas@daglabs.com>
Date: Mon Jun 29 11:59:36 2020 +0300
[NOD-1063] Rename a test.
commit bfecd57470ec8aeb0a1b0ef82c051dde364c536e
Author: stasatdaglabs <stas@daglabs.com>
Date: Mon Jun 29 11:57:36 2020 +0300
[NOD-1063] Fix a comment.
commit b969e5922da16a3734806c03075fe2e45e64958b
Author: stasatdaglabs <stas@daglabs.com>
Date: Sun Jun 28 18:14:44 2020 +0300
[NOD-1063] Convert modifiedTreeNode to an out param.
commit 170f9872f432b2f7177cb099149c9959031e4f1e
Author: stasatdaglabs <stas@daglabs.com>
Date: Sun Jun 28 17:05:01 2020 +0300
[NOD-1063] Fix a bug in which a block is added to the selected parent chain below the reindex root.
|
||
|
stasatdaglabs
|
57b1653383
|
[NOD-1063] Optimize deep reachability tree insertions (#773)
* [NOD-1055] Give higher priority for requesting missing ancestors when sending a getdata message (#767) * [NOD-1063] Remove the remainingInterval field. * [NOD-1063] Add helper functions to reachabilityTreeNode. * [NOD-1063] Add reachabilityReindexRoot. * [NOD-1063] Start implementing findNextReachabilityReindexRoot. * [NOD-1063] Implement findCommonAncestor. * [NOD-1063] Implement findReachabilityTreeAncestorInChildren. * [NOD-1063] Add reachabilityReindexWindow. * [NOD-1063] Fix findReachabilityTreeAncestorInChildren. * [NOD-1063] Remove BlockDAG reference in findReachabilityTreeAncestorInChildren. * [NOD-1063] Extract updateReachabilityReindexRoot to a separate function. * [NOD-1063] Add reachabilityReindexSlack. * [NOD-1063] Implement splitReindexRootChildrenAroundChosen. * [NOD-1063] Implement calcReachabilityTreeNodeSizes. * [NOD-1063] Implement propagateChildIntervals. * [NOD-1063] Extract tightenReachabilityTreeIntervalsBeforeChosenReindexRootChild and tightenReachabilityTreeIntervalsAfterChosenReindexRootChild to separate functions. * [NOD-1063] Implement expandReachabilityTreeIntervalInChosenReindexRootChild. * [NOD-1063] Finished implementing concentrateReachabilityTreeIntervalAroundReindexRootChild. * [NOD-1063] Begin implementing reindexIntervalsBeforeReindexRoot. * [NOD-1063] Implement top-level logic of reindexIntervalsBeforeReindexRoot. * [NOD-1063] Implement reclaimIntervalBeforeChosenChild. * [NOD-1063] Add a debug log for reindexIntervalsBeforeReindexRoot. * [NOD-1063] Rename reindexIntervalsBeforeReindexRoot to reindexIntervalsEarlierThanReindexRoot. * [NOD-1063] Implement reclaimIntervalAfterChosenChild. * [NOD-1063] Add a debug log for updateReachabilityReindexRoot. * [NOD-1063] Convert modifiedTreeNodes from slices to sets. * [NOD-1063] Fix findCommonAncestor. * [NOD-1063] Fix reindexIntervalsEarlierThanReindexRoot.` * [NOD-1063] Remove redundant nil conditions. * [NOD-1063] Make map[*reachabilityTreeNode]struct{} into a type alias with a copyAllFrom method. * [NOD-1063] Remove setInterval. * [NOD-1063] Create a new struct to hold reachability stuff called reachabilityTree. * [NOD-1063] Rename functions under reachabilityTree. * [NOD-1063] Move reachabilityStore into reachabilityTree. * [NOD-1063] Move the rest of the functions in reachability.go into the reachabilityTree struct. * [NOD-1063] Update newReachabilityTree to take an instance of reachabilityStore. * [NOD-1063] Fix merge errors. * [NOD-1063] Fix merge errors. * [NOD-1063] Pass a reference to the dag into reachabilityTree. * [NOD-1063] Use Wrapf instead of Errorf. * [NOD-1063] Merge assignments. * [NOD-1063] Disambiguate a varaible name. * [NOD-1063] Add a test case for intervalBefore. * [NOD-1063] Simplify splitChildrenAroundChosenChild. * [NOD-1063] Fold temporary variables into newReachabilityInterval. * [NOD-1063] Fold more temporary variables into newReachabilityInterval. * [NOD-1063] Fix a bug in expandIntervalInReindexRootChosenChild. * [NOD-1063] Remove blockNode from futureCoveringBlock. * [NOD-1063] Get rid of futureCoveringBlock. * [NOD-1063] Use findIndex directly in findAncestorAmongChildren. * [NOD-1063] Make findIndex a bit nicer to use. Also rename it to findAncestorIndexOfNode. * [NOD-1063] Rename childIntervalAllocationRange to intervalRangeForChildAllocation. * [NOD-1063] Optimize findCommonAncestor. * [NOD-1063] In reindexIntervalsBeforeChosenChild, use chosenChild.interval.start - 1 instead of childrenBeforeChosen[len(childrenBeforeChosen)-1].interval.end + 1. * [NOD-1063] Rename reindexIntervalsBeforeChosenChild to reindexIntervalsBeforeNode. * [NOD-1063] Add a comment explain what "the chosen child" is. * [NOD-1063] In concentrateIntervalAroundReindexRootChosenChild, rename modifiedTreeNodes to allModifiedTreeNodes. * [NOD-1063] Extract propagateIntervals to a function. * [NOD-1063] Extract interval "contains" logic to a separate function. * [NOD-1063] Simplify "looping up" logic in reclaimIntervalXXXChosenChild. * [NOD-1063] Add comments to reclaimIntervalXXXChosenChild. * [NOD-1063] Rename copyAllFrom to addAll. * [NOD-1063] Rename reachabilityStore (the variable) to just store. * [NOD-1063] Fix an error message. * [NOD-1063] Reword a comment. * [NOD-1063] Don't return -1 from findAncestorIndexOfNode. * [NOD-1063] Extract slackReachabilityIntervalForReclaiming to a constant. * [NOD-1063] Add a missing condition. * [NOD-1063] Call isAncestorOf directly in insertNode. * [NOD-1063] Rename chosenReindexRootChild to reindexRootChosenChild. * [NOD-1063] Rename treeNodeSet to orderedTreeNodeSet. * [NOD-1063] Add a disclaimer to orderedTreeNodeSet. * [NOD-1063] Implement StoreReachabilityReindexRoot and FetchReachabilityReindexRoot. * [NOD-1063] Move storing the reindex root to within reachabilityTree. * [NOD-1063] Remove isAncestorOf from reachabilityInterval. * [NOD-1063] Add a comment about graph theory conventions. * [NOD-1063] Fix tests. * [NOD-1063] Change inclusion in isAncestorOf functions. * [NOD-1063] Rename a test. * [NOD-1063] Implement TestIsInFuture. * [NOD-1063] Fix error messages in TestIsInFuture. * [NOD-1063] Fix error messages in TestIsInFuture. * [NOD-1063] Rename isInSelectedParentChain to isInSelectedParentChainOf. * [NOD-1063] Rename isInFuture to isInPast. * [NOD-1063] Expand on a comment. * [NOD-1063] Rename modifiedTreeNodes. * [NOD-1063] Implement test: TestReindexIntervalsEarlierThanReindexRoot. * [NOD-1063] Implement test: TestUpdateReindexRoot. * [NOD-1063] Explain a check. * [NOD-1063] Use a method instead of calling reachabilityStore.loaded directly. * [NOD-1063] Lowercasified an error message. * [NOD-1063] Fix failing test. Co-authored-by: Ori Newman <orinewman1@gmail.com> |
||
|
Ori Newman
|
895f67a8d4
|
[NOD-1035] Use reachability to check finality (#763)
* [NOD-1034] Use reachability to check finality * [NOD-1034] Add comments and rename variables * [NOD-1034] Fix comments * [NOD-1034] Rename checkFinalityRules->checkFinalityViolation * [NOD-1034] Change isAncestorOf to be exclusive * [NOD-1034] Make isAncestorOf exclusive and also more explicit, and add TestReachabilityTreeNodeIsAncestorOf |
||
|
Ori Newman
|
36d866375e
|
[NOD-881] Don't recalculate subtreesize for children (#678)
* [NOD-881] Don't recalculate subtreesize for children * [NOD-881] Make BenchmarkReindexInterval clearer * [NOD-881] Use b.ResetTimer * [NOD-881] Fix BenchmarkReindexInterval to use b.N |
||
|
stasatdaglabs
|
51ff9e2562
|
[NOD-571] Cover ghostdag in tests where possible (#613)
* [NOD-571] Cover reachabilityInterval split methods. * [NOD-571] Cover reindexInterval. * [NOD-571] Cover reachability String() methods. * [NOD-571] Cover blueAnticoneSize. * [NOD-571] Remove unnecessary error from setTreeNode. * [NOD-571] Add TestGHOSTDAGErrors. * [NOD-571] Use PrepareBlockForTest in TestBlueAnticoneSizeErrors. * [NOD-571] Use PrepareBlockForTest in TestGHOSTDAGErrors. * [NOD-571] Add substring checks to TestSplitFractionErrors. * [NOD-571] Add substring checks to TestSplitExactErrors and TestSplitWithExponentialBiasErrors. * [NOD-571] Add comments to TestReindexIntervalErrors. * [NOD-571] Add additional info in some error messages. * [NOD-571] Fix error messages. |
||
|
Ori Newman
|
2174a0a7f2 |
[NOD-497] Implement GHOSTDAG (#575)
* [NOD-540] Implement reachability (#545) * [NOD-540] Begin implementing reachability. * [NOD-540] Finish implementing reachability. * [NOD-540] Implement TestIsFutureBlock. * [NOD-540] Implement TestInsertFutureBlock. * [NOD-540] Add comments. * [NOD-540] Add comment for interval in blockNode. * [NOD-540] Updated comments over insertFutureBlock and isFutureBlock. * [NOD-540] Implement interval splitting methods. * [NOD-540] Begin implementing tree manipulation in blockNode. * [NOD-540] Implement countSubtreesUp. * [NOD-540] Add a comment explaining an impossible condition. * [NOD-540] Implement applyIntervalDown. * [NOD-540] Moved the reachability tree stuff into reachability.go. * [NOD-540] Add some comments. * [NOD-540] Add more comments, implement isInPast. * [NOD-540] Fix comments. * [NOD-540] Implement TestSplitFraction. * [NOD-540] Implement TestSplitExact. * [NOD-540] Implement TestSplit. * [NOD-540] Add comments to structs. * [NOD-540] Implement TestAddTreeChild. * [NOD-540] Fix a comment. * [NOD-540] Rename isInPast to isAncestorOf. * [NOD-540] Rename futureBlocks to futureCoveringSet. * [NOD-540] Rename isFutureBlock to isInFuture. * [NOD-540] move reachabilityInterval to the top of reachability.go. * [NOD-540] Change "s.t." to "such that" in a comment. * [NOD-540] Fix indentation. * [NOD-540] Fix a potential bug involving float inaccuracy. * [NOD-540] Wrote a more descriptive error message. * [NOD-540] Fix error messsage. * [NOD-540] Fix the recursive countSubtreesUp. * [NOD-540] Rename countSubtreesUp to countSubtrees and applyIntervalDown to propagateInterval. * [NOD-540] Implement updating reachability for a valid new block. * [NOD-540] Implement a disk storage for reachability data. * [NOD-540] Fix not all tree nodes being written to the database. * [NOD-540] Implement serialization for reachabilityData. * [NOD-540] Implement some deserialization for reachabilityData. * [NOD-540] Implement restoring the reachabilityStore on node restart. * [NOD-540] Made interval and remainingInterval pointers. * [NOD-540] Rename setTreeInterval to setInterval. * [NOD-540] Rename reindexTreeIntervals to reindexIntervals and fixed the comment above it. * [NOD-540] Expand the comment above reindexIntervals. * [NOD-540] Fix comment above countSubtrees. * [NOD-540] Fix comment above countSubtrees some more. * [NOD-540] Fix comment above split. * [NOD-540] Fix comment above isAncestorOf. * [NOD-540] Fix comment above reachabilityTreeNode. * [NOD-540] Fix weird condition in addTreeChild. * [NOD-540] Rename addTreeChild to addChild. * [NOD-540] Fix weird condition in splitFraction. * [NOD-540] Reverse the lines in reachabilityTreeNode.String(). * [NOD-540] Renamed f to fraction and x to size. * [NOD-540] Fix comment above bisect. * [NOD-540] Implement rtn.isAncestorOf(). * [NOD-540] Use treeNode isAncestorOf instead of treeInterval isAncestorOf. * [NOD-540] Use newReachabilityInterval instead of struct initialization. * [NOD-540] Make reachabilityTreeNode.String() use strings.Join. * [NOD-540] Use sync.RWMutex instead of locks.PriorityMutex. * [NOD-540] Rename thisTreeNode to newTreeNode. * [NOD-540] Rename setTreeNode to addTreeNode. * [NOD-540] Extracted selectedParentAnticone to a separate function. * [NOD-540] Rename node to this. * [NOD-540] Move updateReachability and isAncestorOf from dag.go to reachability.go. * [NOD-540] Add whitespace after multiline function signatures in reachability.go. * [NOD-540] Make splitFraction return an error on empty interval. * [NOD-540] Add a comment about rounding to splitFraction. * [NOD-540] Replace sneaky tabs with spaces. * [NOD-540] Rename split to splitExponential. * [NOD-540] Extract exponentialFractions to a separate function. * [NOD-540] Rename bisect to findIndex. * [NOD-540] Add call to reachabilityStore.clearDirtyEntries at the end of saveChangesFromBlock. * [NOD-540] Explain the dirty hack in reachabilityStore.init(). * [NOD-540] Split the function signature for deserializeReachabilityData to two lines. * [NOD-540] Add a comment about float precision loss to exponentialFractions. * [NOD-540] Corrected a comment about float precision loss to exponentialFractions. * [NOD-540] Fixed a comment about float precision loss to exponentialFractions some more. * [NOD-540] Added further comments above futureCoveringBlockSet. * [NOD-540] Rename addTreeNode to setTreeNode. * [NOD-540] Rename splitExponential to splitWithExponentialBias. * [NOD-540] Fix object references in reachabilityData deserialization (#563) * [NOD-540] Fix broken references in deserialization. * [NOD-540] Fix broken references in futureCoveringSet deserialization. Also add comments. * [NOD-540] Don't deserialize on the first pass in reachabilityStore.init(). * [NOD-540] Remove redundant assignment to loaded[hash]. * [NOD-540] Use NewHash instead of SetBytes. Rename data to destination. * [NOD-540] Preallocate futureCoveringSet. * [NOD-541] Implement GHOSTDAG (#560) * [NOD-541] Implement GHOSTDAG * [NOD-541] Replace the old PHANTOM variant with GHOSTDAG * [NOD-541] Move dag.updateReachability to the top of dag.applyDAGChanges to update reachability before the virtual block is updated * [NOD-541] Fix blueAnticoneSize * [NOD-541] Initialize node.bluesAnticoneSizes * [NOD-541] Fix pastUTXO and applyBlueBlocks blues order * [NOD-541] Add serialization logic to node.bluesAnticoneSizes * [NOD-541] Fix GHOSTDAG to not count the new block and the blue candidates anticone, add selected parent to blues, and save to node.bluesAnticoneSizes properly * [NOD-541] Fix test names in inner strings * [NOD-541] Writing TestGHOSTDAG * [NOD-541] In blueAnticoneSize change node->current * [NOD-541] name ghostdag return values * [NOD-541] fix ghostdag to return slice * [NOD-541] Split k-cluster violation rules * [NOD-541] Add missing space * [NOD-541] Add comment to ghostdag * [NOD-541] In selectedParentAnticone rename past->selectedParentPast * [NOD-541] Fix misrefernces to TestChainUpdates * [NOD-541] Fix ghostdag comment * [NOD-541] Make PrepareBlockForTest in blockdag package * [NOD-541] Make PrepareBlockForTest in blockdag package * [NOD-541] Assign to selectedParentAnticone[i] instead of appending * [NOD-541] Remove redundant forceTransactions arguments from PrepareBlockForTEST * [NOD-541] Add non-selected parents to anticoneHeap * [NOD-541] add test for ghostdag * [NOD-541] Add comments * [NOD-541] Use adjusted time for initializing blockNode * [NOD-541] Rename isAncestorOf -> isAncestorOfBlueCandidate * [NOD-541] Remove params from PrepareBlockForTest * [NOD-541] Fix TestChainHeight * [NOD-541] Remove recursive lock * [NOD-541] Fix TestTxIndexConnectBlock * [NOD-541] Fix TestBlueBlockWindow * [NOD-541] Put prepareAndProcessBlock in common_test.go * [NOD-541] Fix TestConfirmations * [NOD-541] Fix TestAcceptingBlock * [NOD-541] Fix TestDifficulty * [NOD-541] Fix TestVirtualBlock * [NOD-541] Fix TestSelectedPath * [NOD-541] Fix TestChainUpdates * [NOD-541] Shorten TestDifficulty test time * [NOD-541] Make PrepareBlockForTest use minimal valid block time * [NOD-541] Remove TODO comment * [NOD-541] Move blockdag related mining functions to mining.go * [NOD-541] Use NextBlockCoinbaseTransaction instead of NextBlockCoinbaseTransactionNoLock in NextCoinbaseFromAddress * [NOD-541] Remove useMinimalTime from BlockForMining * [NOD-541] Make MedianAdjustedTime a *BlockDAG method * [NOD-541] Fix ghostdag to use anticone slice instead of heap * [NOD-541] Fix NewBlockTemplate locks * [NOD-541] Fix ghostdag comments * [NOD-541] Convert MedianAdjustedTime to NextBlockTime * [NOD-541] Fix ghostdag comment * [NOD-541] Fix TestGHOSTDAG comment * [NOD-541] Add comment before sanity check * [NOD-541] Explicitly initialize .blues in ghostdag * [NOD-541] Rename *blockNode.lessThan to *blockNode.less * [NOD-541] Remove redundant check if block != chainBlock * [NOD-541] Fix comment * [NOD-541] Fix comment * [NOD-497] Add comment; General refactoring * [NOD-497] General refactoring. * [NOD-497] Use isAncestor of the tree rather than the node * [NOD-497] Remove reachability mutex lock as it is redundant (dag lock is held so no need); General refactoring. * [NOD-497] Update comment * [NOD-497] Undo test blocktimestamp * [NOD-497] Update comments; Use BlockNode.less for blockset; * [NOD-497] Change processBlock to return boolean and not the delay duration (merge conflict) * [NOD-497] Undo change for bluest to use less; Change blocknode less to use daghash.Less Co-authored-by: stasatdaglabs <39559713+stasatdaglabs@users.noreply.github.com> Co-authored-by: Dan Aharoni <dereeno@protonmail.com> |