Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Provide a way to call btree_print_tree() to print all BTrees under a given trunk node. #533

Open
gapisback opened this issue Jan 16, 2023 · 0 comments
Open

Provide a way to call btree_print_tree() to print all BTrees under a given trunk node. #533

gapisback opened this issue Jan 16, 2023 · 0 comments
Assignees
@gapisback
Labels
enhancement New feature or request

Comments

@gapisback
Copy link
Collaborator

Existing routine btree_print_tree() works well to print the entire BTree and all its sub-trees from a starting BTree root node. Provide an interface to call this directly from a specific Trunk node.

This will be useful for debugging tree manipulations, especially to see the result of a flush and compact operation.
@gapisback gapisback self-assigned this Jan 16, 2023
@gapisback gapisback added the enhancement New feature or request label Jan 16, 2023
gapisback added a commit that referenced this issue Jan 18, 2023
@gapisback
(#533) Add print fn to print branch BTrees under trunk node.
c22886d 
- Introduce trunk_print_branch_btrees() to walk the root-addresses
  of branch BTree nodes for a given trunk node, and to invoke the
  BTree print methods on each such branch. The top-level BTree
  root node is being printed right, but upon recursing down, we
  are running into an unallocated page error.
  allocator_page_valid() is consistently failing for all sub-trees
  under root branch BTree.
gapisback added a commit that referenced this issue Feb 2, 2023
@gapisback
(#533) Add print fn to print branch BTrees under trunk node.
f36cd47 
- Introduce trunk_print_branch_btrees() to walk the root-addresses
  of branch BTree nodes for a given trunk node, and to invoke the
  BTree print methods on each such branch. The top-level BTree
  root node is being printed right, but upon recursing down, we
  are running into an unallocated page error.
  allocator_page_valid() is consistently failing for all sub-trees
  under root branch BTree.
gapisback added a commit that referenced this issue Feb 3, 2023
@gapisback
(#533) Add print fn to print branch BTrees under trunk node.
e626968 
- Introduce trunk_print_branch_btrees() to walk the root-addresses
  of branch BTree nodes for a given trunk node, and to invoke the
  BTree print methods on each such branch. The top-level BTree
  root node is being printed right, but upon recursing down, we
  are running into an unallocated page error.
  allocator_page_valid() is consistently failing for all sub-trees
  under root branch BTree.
gapisback added a commit that referenced this issue Feb 9, 2023
@gapisback
Multi-PRs: Collection of various print / debug code enhancements.
cd7a6cf 
(#537) Add unit-tests to exercise rc/allocator.c; Other minor cleanup.

This commit refactors and does some minor cleanup of code in allocator.{h,c}
and couple of related files. Some page / extent number / offset
boolean and conversion macros are added, along with new unit-tests.
No significant change in code-logic is being introduced with this fix.

(#538) Unit-test to exercise mini_allocator. Minor cleanup of module.

This commit does some minor cleanup of the mini-allocator module.
Some interfaces are slightly changed to streamline init / deinit
interfaces. A new unit-test is added to exercise core interfaces
of this page allocation system, and to exercise / test the print
methods for keyed and unkeyed page allocation schemes.

Extend print methods to also print page_addr and extent_addr as
page_num and extent_num, where applicable.

(#530) Add test cases to exercise print methods for mini-allocator metapages

This commit adds new print function to drive the functions for printing
keyed / unkeyed metadata pages of the mini-allocator. Existing test cases
are enhanced as follows to eventually exercise these print methods.

- Add bunch of print functions in trunk.c to find out routing filter
  metadata pages and to invoke underlying print methods on such pages.
  Print pivot key and other filter-related data.

- Extend splinter_test:test_splinter_print_diags() to exercise the print
  function that will walk through routing filter metadata pages for one
  pivot key off of the trunk's root node and eventually callss
  mini_unkeyed_print().

- Add new test_splinter_verbose_print_diags test case to exercise the
  verbose print logging in trunk.c (for a small data set).

- Modularize code in btree_stress_test.c to carve out code that is used
  to build new unit-test case, test_btree_print_diags(). First, this
  invokes btree_print_tree(), to see outputs of packed BTree node.
  Then, invokes mini_keyed_print(), to print keyed mini-allocator's
  metadata pages.

Identify Memtable v/s Branch page types via BTree-print routines.

This commit extends BTree-print routines to also report the page
type, whether it's a branch or a memtable BTree. As the structures and
print methods are shared between two objects, this extra information
will help in diagnostics. Trunk nodes are likewise identified.
Minor fix in trunk_print_pivots() to align outputs for pivot key's string.

Fix compilation errors that show in debug builds. Readjust output formatting.

(#533) Add print fn to print branch BTrees under trunk node.

- Introduce trunk_print_branch_btrees() to walk the root-addresses
  of branch BTree nodes for a given trunk node, and to invoke the
  BTree print methods on each such branch. The top-level BTree
  root node is being printed right, but upon recursing down, we
  are running into an unallocated page error.
  allocator_page_valid() is consistently failing for all sub-trees
  under root branch BTree.

Tentative fix to by-pass "unallocated page errors".

The previous commit runs into issues while trying to print BTree
sub-trees under branch BTree root pages. We run into the following
errors:

btree_print_subtree() -> allocator_page_valid(), which will fail
complaining that "Trying to access an unreferenced extent. ..."
as (refcount==0)

I wondered if this is because we use the mini-allocator to allocate
pages for BTrees, and perhaps, these pages are not being recorded
as referenced in the allocator's reference count.

This commit, thus, implements a by-pass 'fix' to pass-down the page
type. Deep inside allocator_page_valid(), we try to ignore refcount==0
in case the page's type is PAGE_TYPE_BRANCH. This still runs into
the following stack:

---
    linenumber=2108,
    functionname=0x7ffff7f9f9a0 <__FUNCTION__.17> "clockcache_get_internal",
    expr=0x7ffff7f9ee98 "(extent_ref_count > 1)",
    message=0x7ffff7f9edf8 "Attempt to get a buffer for page addr=%lu, page type=%d ('%s'), from extent addr=%lu, (extent number=%lu), which is an unallocated extent, extent_ref_count=%u.") at src/platform_linux/platform.c:370
    blocking=1, type=PAGE_TYPE_BRANCH, page=0x7fffffffe230) at src/clockcache.c:2108
    type=PAGE_TYPE_BRANCH) at src/clockcache.c:2267
    blocking=1, type=PAGE_TYPE_BRANCH) at src/clockcache.c:295
    type=PAGE_TYPE_BRANCH) at src/cache.h:283
    node=0x7fffffffe380, type=PAGE_TYPE_BRANCH) at src/btree.c:1043
    cc=0x555555577040, cfg=0x7fffb550c0c0, node=0x7fffffffe380, type=PAGE_TYPE_BRANCH)
    at src/btree.c:3259
    cc=0x555555577040, cfg=0x7fffb550c0c0, addr=4319870976, type=PAGE_TYPE_BRANCH)
    at src/btree.c:3281
    cc=0x555555577040, cfg=0x7fffb550c0c0, addr=4319608832, type=PAGE_TYPE_BRANCH)
    at src/btree.c:3300
    cc=0x555555577040, cfg=0x7fffb550c0c0, root_addr=4319608832) at src/btree.c:3337
    arg=0x7ffff7ed3780 <_IO_2_1_stdout_>) at src/trunk.c:8943
---

The mystery is how come the same access functions to read BTree sub-tree's
child-pages in btree_lookup_node() seemingly works fine.

One issue is that existing tests that exercise that function for query tests
are always only dealing with PAGE_TYPE_MEMTABLE. This may be the reason why
they don't run into branch BTree pages that appear unallocated.

Needs further consult & investigation.

Fix merge issue.

Print BTree & Trunk addresses as extent & page number. Add unit-tests.

Consistently report page 'addr' as extent number and page number for
BTree and Trunk node page print methods. Add unit test-cases to verify
BTree extent / page-number conversion macros.

(#156) Extend trunk_node_print_branches(). Call it from unit-test print_diags.

This commit adds minor improvements to trunk_node_print_branches() to:

- Print sum of {# of branches, num tuples & num of kv-bytes} for
  each trunk node.
- Add trunk_node_stats{} to gather metrics as we traverse trunk nodes
  during printing. Report one-line summary of aggregate metrics.

- Extend unit-test test_splinter_print_diags() to now also call
  trunk_print_branches() so we have a basic exercise of this
  print method.

Fix merge-issues: Call set_log_streams_for_tests() as needed in new unit-tests.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@gapisback gapisback

Labels
enhancement New feature or request
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@gapisback