From 8260ce22ad9c50711878c233095f7f3fb4a82ac2 Mon Sep 17 00:00:00 2001 From: Tomohiro Kusumi Date: Tue, 29 Mar 2016 03:43:29 +0900 Subject: [PATCH] sbin/hammer: Don't always print BC error on nodes with 0 count B-Tree nodes having 0 count ("BC") isn't necessarily an error. This is rare case, but hammer prune (or other operations that delete nodes) could happen to leave B-Tree nodes with 0 count. In the following hammer show result, there is repetition of L14298648..14298661 pattern (which includes "BC") for another 25 times after below three. This structure tells nodes with "BC" aren't generated by node split, because node split always results in having at least two nodes (original and new node) at the same level under the parent node of the original node. It was probably generated by something happened after split. The following path [B] seems to be the case that could genearate this structure. As shown in [A] it usually recursively calls node remove path against its parent node until it first hits a parent with >1 count. However, as shown in [B] if it fails to get a lock while in the recursive path, the path ends there before it hits >1 count node. This results in losing a chance to erase a node element within the first >1 count node that has a pointer to all the children so far including the 0 count node prune ioctl was originally trying to delete, and leaves the 0 count node along with (1 or more) parent 1 count node(s). hammer show should recognize this and not mark it as an error since this is intended behavior. [A] hammer_ioc_prune() -> hammer_delete_at_cursor(HAMMER_DELETE_DESTROY) -> hammer_btree_delete() /* --ondisk->count == 0 */ -> btree_remove() /* parent->ondisk->count == 1 */ -> hammer_cursor_up_locked() /* success */ -> btree_remove() /* parent->ondisk->count == 1 */ -> hammer_cursor_up_locked() /* success */ -> btree_remove() /* parent->ondisk->count == 1 */ -> hammer_cursor_up_locked() /* success */ -> btree_remove() /* parent->ondisk->count > 1 */ -> bcopy(&elm[1], &elm[0], newsize); ondisk->count--; ... ... ... ... [B] hammer_ioc_prune() -> hammer_delete_at_cursor(HAMMER_DELETE_DESTROY) -> hammer_btree_delete() /* --ondisk->count == 0 */ -> btree_remove() /* parent->ondisk->count == 1 */ -> hammer_cursor_up_locked() /* failed */ /* recursive call ends here without erasing elm in parent */ --- ... 14298558 NODE 8000003e99042000 cnt=43 p=8000003e8d7f7000 type=I depth=1 mirror=00000005127ef970 fill=z8:v0:0:32050:270336=70% { 14298559 G------ ELM 0 I lo=00040002 obj=0000000460f4fda4 rt=10 key=000000000000a000 tid=0000000460f8f990 14298560 del=0000000000000000 ot=00 suboff=8000003e99041000 mirror=0000000466e4b890 14298561 G------ ELM 1 I lo=00040002 obj=00000004627d568b rt=10 key=00000000000005d0 tid=00000004627f52d0 14298562 del=0000000000000000 ot=00 suboff=8000003e99044000 mirror=000000046b5c6600 14298563 G------ ELM 2 I lo=00040002 obj=0000000463ed92b1 rt=10 key=00000000000b2000 tid=0000000463f691c0 14298564 del=0000000000000000 ot=00 suboff=8000003e99046000 mirror=000000046b5ce630 ... 14298639 G------ ELM 40 I lo=00040002 obj=000000050c1bac40 rt=10 key=0000000000056000 tid=000000050d52dad0 14298640 del=0000000000000000 ot=00 suboff=8000003e997f5000 mirror=00000005127ef970 14298641 G------ ELM 41 I lo=00040002 obj=00000005107f5a71 rt=10 key=0000000000004000 tid=000000051083d600 14298642 del=0000000000000000 ot=00 suboff=8000003e99b0e000 mirror=00000005127ef910 14298643 G------ ELM 42 I lo=00040002 obj=000000051158802f rt=10 key=000000000000e000 tid=00000005115c01a0 14298644 del=0000000000000000 ot=00 suboff=8000003e9ac72000 mirror=00000005127ef970 14298645 G------ RBN 43 * lo=ffffffff obj=7fffffffffffffff rt=ffff key=7fffffffffffffff tid=ffffffffffffffff 14298646 < del=0000000000000000 ot=00 suboff=0000000000000000 mirror=0000000000000000 14298647 } 14298648 NODE 8000003e99041000 cnt=01 p=8000003e99042000 type=I depth=2 mirror=0000000466e4b890 fill=z8:v0:0:32050:266240=70% { 14298649 G------ ELM 0 I lo=00040002 obj=00000004623f3e4f rt=10 key=0000000000006000 tid=00000004627cd020 14298650 del=0000000000000000 ot=00 suboff=8000003e99040000 mirror=0000000466e4b890 14298651 G------ RBN 1 * lo=00040002 obj=00000004627d568b rt=10 key=00000000000005d0 tid=00000004627f52d0 14298652 del=0000000000000000 ot=00 suboff=0000000000000000 mirror=0000000463507320 14298653 } 14298654 NODE 8000003e99040000 cnt=01 p=8000003e99041000 type=I depth=3 mirror=000000046347eff0 fill=z8:v0:0:32050:262144=70% { 14298655 G------ ELM 0 L lo=00040002 obj=00000004626043ca rt=10 key=0000000000006000 tid=00000004627d5070 14298656 del=0000000000000000 ot=00 suboff=800000395b96a000 mirror=000000046347eff0 14298657 G------ RBN 1 * lo=00040002 obj=00000004627d568b rt=10 key=00000000000005d0 tid=00000004627f52d0 14298658 del=0000000000000000 ot=00 suboff=0000000000000000 mirror=0000000000000000 14298659 } * 14298660 BC NODE 800000395b96a000 cnt=00 p=8000003e99040000 type=L depth=4 mirror=000000046347eff0 fill=z8:v0:0:29367:1482752=1% { 14298661 } 14298662 NODE 8000003e99044000 cnt=01 p=8000003e99042000 type=I depth=2 mirror=000000046b5c6600 fill=z8:v0:0:32050:278528=70% { 14298663 G------ ELM 0 I lo=00040002 obj=0000000463b8866f rt=10 key=000000000000e000 tid=0000000463bc0550 14298664 del=0000000000000000 ot=00 suboff=8000003e99043000 mirror=000000046b5c65e0 14298665 G------ RBN 1 * lo=00040002 obj=0000000463ed92b1 rt=10 key=00000000000b2000 tid=0000000463f691c0 14298666 del=0000000000000000 ot=00 suboff=0000000000000000 mirror=0000000464009780 14298667 } 14298668 NODE 8000003e99043000 cnt=01 p=8000003e99044000 type=I depth=3 mirror=000000046b5b6540 fill=z8:v0:0:32050:274432=70% { 14298669 G------ ELM 0 L lo=00040002 obj=0000000463ba883a rt=10 key=0000000000052000 tid=0000000463bc0570 14298670 del=0000000000000000 ot=00 suboff=800000395c948000 mirror=0000000467587c20 14298671 G------ RBN 1 * lo=00040002 obj=0000000463ed92b1 rt=10 key=00000000000b2000 tid=0000000463f691c0 14298672 del=0000000000000000 ot=00 suboff=0000000000000000 mirror=0000000000000000 14298673 } * 14298674 BC NODE 800000395c948000 cnt=00 p=8000003e99043000 type=L depth=4 mirror=0000000467587c20 fill=z8:v0:0:29369:1343488=1% { 14298675 } 14298676 NODE 8000003e99046000 cnt=01 p=8000003e99042000 type=I depth=2 mirror=000000046b5ce630 fill=z8:v0:0:32050:286720=70% { 14298677 G------ ELM 0 I lo=00040002 obj=0000000463f5167f rt=10 key=0000000000d28000 tid=0000000463f69160 14298678 del=0000000000000000 ot=00 suboff=8000003e99045000 mirror=000000046b5c6600 14298679 G------ RBN 1 * lo=00040002 obj=0000000464a2c0bb rt=10 key=0000000000000f60 tid=0000000464a9c460 14298680 del=0000000000000000 ot=00 suboff=0000000000000000 mirror=0000000466a39890 14298681 } 14298682 NODE 8000003e99045000 cnt=01 p=8000003e99046000 type=I depth=3 mirror=0000000467587fc0 fill=z8:v0:0:32050:282624=70% { 14298683 G------ ELM 0 L lo=00040002 obj=0000000463f5944f rt=10 key=0000000000b18000 tid=0000000463f691c0 14298684 del=0000000000000000 ot=00 suboff=800000395cb74000 mirror=0000000467587dc0 14298685 G------ RBN 1 * lo=00040002 obj=0000000464a2c0bb rt=10 key=0000000000000f60 tid=0000000464a9c460 14298686 del=0000000000000000 ot=00 suboff=0000000000000000 mirror=0000000000000000 14298687 } * 14298688 BC NODE 800000395cb74000 cnt=00 p=8000003e99045000 type=L depth=4 mirror=0000000467587dc0 fill=z8:v0:0:29369:3620864=1% { 14298689 } ... --- sbin/hammer/cmd_show.c | 38 ++++++++++++++++++++++++++++------- sys/vfs/hammer/hammer_btree.c | 8 ++++++-- 2 files changed, 37 insertions(+), 9 deletions(-) diff --git a/sbin/hammer/cmd_show.c b/sbin/hammer/cmd_show.c index 1400b4a2c3..f75119c3ae 100644 --- a/sbin/hammer/cmd_show.c +++ b/sbin/hammer/cmd_show.c @@ -57,6 +57,7 @@ static void print_btree_node(hammer_off_t node_offset, hammer_tid_t mirror_tid, hammer_base_elm_t left_bound, hammer_base_elm_t right_bound); +static int test_node_count(hammer_node_ondisk_t node, char *badmp); static void print_btree_elm(hammer_node_ondisk_t node, hammer_off_t node_offset, hammer_btree_elm_t elm, hammer_base_elm_t left_bound, @@ -203,7 +204,6 @@ print_btree_node(hammer_off_t node_offset, hammer_node_ondisk_t node; hammer_btree_elm_t elm; int i; - int maxcount; char badc = ' '; /* good */ char badm = ' '; /* good */ const char *ext; @@ -221,13 +221,9 @@ print_btree_node(hammer_off_t node_offset, badc = 'B'; badm = 'M'; } - maxcount = hammer_node_max_elements(node->type); - if (maxcount == -1) { - badc = 'B'; - badm = 'U'; - } else if (node->count == 0 || node->count > maxcount) { + if (test_node_count(node, &badm) == -1) { badc = 'B'; - badm = 'C'; + assert(badm != ' '); } } @@ -300,6 +296,34 @@ print_btree_node(hammer_off_t node_offset, depth--; } +static int +test_node_count(hammer_node_ondisk_t node, char *badmp) +{ + hammer_node_ondisk_t parent_node; + struct buffer_info *buffer = NULL; + int maxcount; + + maxcount = hammer_node_max_elements(node->type); + + if (maxcount == -1) { + *badmp = 'U'; + return(-1); + } else if (node->count > maxcount) { + *badmp = 'C'; + return(-1); + } else if (node->count == 0) { + parent_node = get_node(node->parent, &buffer); + if (parent_node->count != 1) { + *badmp = 'C'; + rel_buffer(buffer); + return(-1); + } + rel_buffer(buffer); + } + + return(0); +} + static __inline int is_root_btree_beg(uint8_t type, int i, hammer_btree_elm_t elm) diff --git a/sys/vfs/hammer/hammer_btree.c b/sys/vfs/hammer/hammer_btree.c index 8832091db0..9bdf27eb65 100644 --- a/sys/vfs/hammer/hammer_btree.c +++ b/sys/vfs/hammer/hammer_btree.c @@ -2252,7 +2252,9 @@ btree_remove(hammer_cursor_t cursor, int *ndelete) * get the lock, just let the leaf remain * empty. */ - /**/ + /* + * hammer show doesn't consider this as an error. + */ } hammer_unlock(&node->lock); hammer_rel_node(node); @@ -2262,7 +2264,9 @@ btree_remove(hammer_cursor_t cursor, int *ndelete) * get the lock, just let the leaf remain * empty. */ - /**/ + /* + * hammer show doesn't consider this as an error. + */ } } else { KKASSERT(parent->ondisk->count > 1); -- 2.41.0