MDEV-7061: Augment innochecksum to give insight of fragmentation

Merged https://github.com/facebook/mysql-5.6/commit/615dd07d900ce08948340b6c11e37fd1d2a91065 from https://github.com/facebook/mysql-5.6/
authored by rongrong. Removed C++11 requirement by using
std::map instead of std::unordered_set.

Add analysis to leaf pages to estimate how fragmented an index is
and how much benefit we can get out of defragmentation.

1 files changed, 459 insertions, 2 deletions

diff --git a/extra/innochecksum.cc b/extra/innochecksum.cc
index e93a6405e53..1f323b9d730 100644
--- a/extra/innochecksum.cc
+++ b/extra/innochecksum.cc
@@ -1,5 +1,6 @@
 /*
    Copyright (c) 2005, 2012, Oracle and/or its affiliates. All rights reserved.
+   Copyright (c) 2014, 2015, MariaDB Corporation.
 
    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
@@ -43,8 +44,10 @@ The parts not included are excluded by #ifndef UNIV_INNOCHECKSUM. */
 
 #include "univ.i"                /*  include all of this */
 
+#define FLST_BASE_NODE_SIZE (4 + 2 * FIL_ADDR_SIZE)
 #define FLST_NODE_SIZE (2 * FIL_ADDR_SIZE)
 #define FSEG_PAGE_DATA FIL_PAGE_DATA
+#define MLOG_1BYTE (1)
 
 #include "ut0ut.h"
 #include "ut0byte.h"
@@ -58,7 +61,6 @@ The parts not included are excluded by #ifndef UNIV_INNOCHECKSUM. */
 #include "trx0undo.h"            /* TRX_* */
 #include "fsp0fsp.h"             /* fsp_flags_get_page_size() &
                                     fsp_flags_get_zip_size() */
-#include "mach0data.h"           /* mach_read_from_4() */
 #include "ut0crc32.h"            /* ut_crc32_init() */
 
 #ifdef UNIV_NONINL
@@ -77,11 +79,79 @@ static ulong end_page;
 static ulong do_page;
 static my_bool use_end_page;
 static my_bool do_one_page;
+static my_bool per_page_details;
+static my_bool do_leaf;
+static ulong n_merge;
 ulong srv_page_size;              /* replaces declaration in srv0srv.c */
 static ulong physical_page_size;  /* Page size in bytes on disk. */
 static ulong logical_page_size;   /* Page size when uncompressed. */
 static bool compressed= false;    /* Is tablespace compressed */
 
+int n_undo_state_active;
+int n_undo_state_cached;
+int n_undo_state_to_free;
+int n_undo_state_to_purge;
+int n_undo_state_prepared;
+int n_undo_state_other;
+int n_undo_insert, n_undo_update, n_undo_other;
+int n_bad_checksum;
+int n_fil_page_index;
+int n_fil_page_undo_log;
+int n_fil_page_inode;
+int n_fil_page_ibuf_free_list;
+int n_fil_page_allocated;
+int n_fil_page_ibuf_bitmap;
+int n_fil_page_type_sys;
+int n_fil_page_type_trx_sys;
+int n_fil_page_type_fsp_hdr;
+int n_fil_page_type_allocated;
+int n_fil_page_type_xdes;
+int n_fil_page_type_blob;
+int n_fil_page_type_zblob;
+int n_fil_page_type_other;
+
+int n_fil_page_max_index_id;
+
+#define SIZE_RANGES_FOR_PAGE 10
+#define NUM_RETRIES 3
+#define DEFAULT_RETRY_DELAY 1000000
+
+struct per_page_stats {
+  ulint n_recs;
+  ulint data_size;
+  ulint left_page_no;
+  ulint right_page_no;
+  per_page_stats(ulint n, ulint data, ulint left, ulint right) :
+      n_recs(n), data_size(data), left_page_no(left), right_page_no(right) {}
+  per_page_stats() : n_recs(0), data_size(0), left_page_no(0), right_page_no(0) {}
+};
+
+struct per_index_stats {
+  unsigned long long pages;
+  unsigned long long leaf_pages;
+  ulint first_leaf_page;
+  ulint count;
+  ulint free_pages;
+  ulint max_data_size;
+  unsigned long long total_n_recs;
+  unsigned long long total_data_bytes;
+
+  /*!< first element for empty pages,
+  last element for pages with more than logical_page_size */
+  unsigned long long pages_in_size_range[SIZE_RANGES_FOR_PAGE+2];
+
+  std::map<ulint, per_page_stats> leaves;
+
+  per_index_stats():pages(0), leaf_pages(0), first_leaf_page(0),
+                    count(0), free_pages(0), max_data_size(0), total_n_recs(0),
+                    total_data_bytes(0)
+  {
+    memset(pages_in_size_range, 0, sizeof(pages_in_size_range));
+  }
+};
+
+std::map<unsigned long long, per_index_stats> index_ids;
+
 /* Get the page size of the filespace from the filespace header. */
 static
 my_bool
@@ -159,6 +229,14 @@ static struct my_option innochecksum_options[] =
   {"page", 'p', "Check only this page (0 based).",
     &do_page, &do_page, 0, GET_ULONG, REQUIRED_ARG,
     0, 0, (longlong) 2L*1024L*1024L*1024L, 0, 1, 0},
+  {"per_page_details", 'i', "Print out per-page detail information.",
+    &per_page_details, &per_page_details, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0}
+    ,
+  {"leaf", 'l', "Examine leaf index pages",
+    &do_leaf, &do_leaf, 0, GET_BOOL, NO_ARG, 0, 0, 0, 0, 0, 0},
+  {"merge", 'm', "leaf page count if merge given number of consecutive pages",
+   &n_merge, &n_merge, 0, GET_ULONG, REQUIRED_ARG,
+   0, 0, (longlong)10L, 0, 1, 0},
   {0, 0, 0, 0, 0, 0, GET_NO_ARG, NO_ARG, 0, 0, 0, 0, 0, 0}
 };
 
@@ -230,12 +308,342 @@ static int get_options(
   return 0;
 } /* get_options */
 
+/*********************************************************************//**
+Gets the file page type.
+@return type; NOTE that if the type has not been written to page, the
+return value not defined */
+ulint
+fil_page_get_type(
+/*==============*/
+       uchar*  page)   /*!< in: file page */
+{
+       return(mach_read_from_2(page + FIL_PAGE_TYPE));
+}
+
+/**************************************************************//**
+Gets the index id field of a page.
+@return        index id */
+ib_uint64_t
+btr_page_get_index_id(
+/*==================*/
+       uchar*  page)   /*!< in: index page */
+{
+       return(mach_read_from_8(page + PAGE_HEADER + PAGE_INDEX_ID));
+}
+
+/********************************************************//**
+Gets the next index page number.
+@return	next page number */
+ulint
+btr_page_get_next(
+/*==============*/
+  const page_t* page) /*!< in: index page */
+{
+  return(mach_read_from_4(page + FIL_PAGE_NEXT));
+}
+
+/********************************************************//**
+Gets the previous index page number.
+@return	prev page number */
+ulint
+btr_page_get_prev(
+/*==============*/
+  const page_t* page) /*!< in: index page */
+{
+  return(mach_read_from_4(page + FIL_PAGE_PREV));
+}
+
+void
+parse_page(
+/*=======*/
+  uchar* page, /* in: buffer page */
+  uchar* xdes) /* in: extend descriptor page */
+{
+       ib_uint64_t id;
+       ulint x;
+       ulint n_recs;
+       ulint page_no;
+       ulint left_page_no;
+       ulint right_page_no;
+       ulint data_bytes;
+       int is_leaf;
+       int size_range_id;
+
+       switch (fil_page_get_type(page)) {
+       case FIL_PAGE_INDEX:
+               n_fil_page_index++;
+               id = btr_page_get_index_id(page);
+               n_recs = page_get_n_recs(page);
+               page_no = page_get_page_no(page);
+               left_page_no = btr_page_get_prev(page);
+               right_page_no = btr_page_get_next(page);
+               data_bytes = page_get_data_size(page);
+               is_leaf = page_is_leaf(page);
+               size_range_id = (data_bytes * SIZE_RANGES_FOR_PAGE
+                                + logical_page_size - 1) /
+                                logical_page_size;
+               if (size_range_id > SIZE_RANGES_FOR_PAGE + 1) {
+                 /* data_bytes is bigger than logical_page_size */
+                 size_range_id = SIZE_RANGES_FOR_PAGE + 1;
+               }
+               if (per_page_details) {
+                 printf("index %lu page %lu leaf %u n_recs %lu data_bytes %lu"
+                         "\n", id, page_no, is_leaf, n_recs, data_bytes);
+               }
+               /* update per-index statistics */
+               {
+                 if (index_ids.count(id) == 0) {
+                   index_ids[id] = per_index_stats();
+                 }
+		 std::map<unsigned long long, per_index_stats>::iterator it;
+		 it = index_ids.find(id);
+                 per_index_stats &index = (it->second);
+                 uchar* des = xdes + XDES_ARR_OFFSET
+                   + XDES_SIZE * ((page_no & (physical_page_size - 1))
+                                  / FSP_EXTENT_SIZE);
+                 if (xdes_get_bit(des, XDES_FREE_BIT,
+                                  page_no % FSP_EXTENT_SIZE)) {
+                   index.free_pages++;
+                   return;
+                 }
+                 index.pages++;
+                 if (is_leaf) {
+                   index.leaf_pages++;
+                   if (data_bytes > index.max_data_size) {
+                     index.max_data_size = data_bytes;
+                   }
+		   struct per_page_stats pp(n_recs, data_bytes,
+			   left_page_no, right_page_no);
+
+                   index.leaves[page_no] = pp;
+
+                   if (left_page_no == ULINT32_UNDEFINED) {
+                     index.first_leaf_page = page_no;
+                     index.count++;
+                   }
+                 }
+                 index.total_n_recs += n_recs;
+                 index.total_data_bytes += data_bytes;
+                 index.pages_in_size_range[size_range_id] ++;
+               }
+
+               break;
+       case FIL_PAGE_UNDO_LOG:
+               if (per_page_details) {
+                       printf("FIL_PAGE_UNDO_LOG\n");
+               }
+               n_fil_page_undo_log++;
+               x = mach_read_from_2(page + TRX_UNDO_PAGE_HDR +
+                                    TRX_UNDO_PAGE_TYPE);
+               if (x == TRX_UNDO_INSERT)
+                       n_undo_insert++;
+               else if (x == TRX_UNDO_UPDATE)
+                       n_undo_update++;
+               else
+                       n_undo_other++;
+
+               x = mach_read_from_2(page + TRX_UNDO_SEG_HDR + TRX_UNDO_STATE);
+               switch (x) {
+                       case TRX_UNDO_ACTIVE: n_undo_state_active++; break;
+                       case TRX_UNDO_CACHED: n_undo_state_cached++; break;
+                       case TRX_UNDO_TO_FREE: n_undo_state_to_free++; break;
+                       case TRX_UNDO_TO_PURGE: n_undo_state_to_purge++; break;
+                       case TRX_UNDO_PREPARED: n_undo_state_prepared++; break;
+                       default: n_undo_state_other++; break;
+               }
+               break;
+       case FIL_PAGE_INODE:
+               if (per_page_details) {
+                       printf("FIL_PAGE_INODE\n");
+               }
+               n_fil_page_inode++;
+               break;
+       case FIL_PAGE_IBUF_FREE_LIST:
+               if (per_page_details) {
+                       printf("FIL_PAGE_IBUF_FREE_LIST\n");
+               }
+               n_fil_page_ibuf_free_list++;
+               break;
+       case FIL_PAGE_TYPE_ALLOCATED:
+               if (per_page_details) {
+                       printf("FIL_PAGE_TYPE_ALLOCATED\n");
+               }
+               n_fil_page_type_allocated++;
+               break;
+       case FIL_PAGE_IBUF_BITMAP:
+               if (per_page_details) {
+                       printf("FIL_PAGE_IBUF_BITMAP\n");
+               }
+               n_fil_page_ibuf_bitmap++;
+               break;
+       case FIL_PAGE_TYPE_SYS:
+               if (per_page_details) {
+                       printf("FIL_PAGE_TYPE_SYS\n");
+               }
+               n_fil_page_type_sys++;
+               break;
+       case FIL_PAGE_TYPE_TRX_SYS:
+               if (per_page_details) {
+                       printf("FIL_PAGE_TYPE_TRX_SYS\n");
+               }
+               n_fil_page_type_trx_sys++;
+               break;
+       case FIL_PAGE_TYPE_FSP_HDR:
+               if (per_page_details) {
+                       printf("FIL_PAGE_TYPE_FSP_HDR\n");
+               }
+               memcpy(xdes, page, physical_page_size);
+               n_fil_page_type_fsp_hdr++;
+               break;
+       case FIL_PAGE_TYPE_XDES:
+               if (per_page_details) {
+                       printf("FIL_PAGE_TYPE_XDES\n");
+               }
+               memcpy(xdes, page, physical_page_size);
+               n_fil_page_type_xdes++;
+               break;
+       case FIL_PAGE_TYPE_BLOB:
+               if (per_page_details) {
+                       printf("FIL_PAGE_TYPE_BLOB\n");
+               }
+               n_fil_page_type_blob++;
+               break;
+       case FIL_PAGE_TYPE_ZBLOB:
+       case FIL_PAGE_TYPE_ZBLOB2:
+               if (per_page_details) {
+                       printf("FIL_PAGE_TYPE_ZBLOB/2\n");
+               }
+               n_fil_page_type_zblob++;
+               break;
+       default:
+               if (per_page_details) {
+                       printf("FIL_PAGE_TYPE_OTHER\n");
+               }
+               n_fil_page_type_other++;
+       }
+}
+
+void print_index_leaf_stats(unsigned long long id, const per_index_stats& index)
+{
+  ulint page_no = index.first_leaf_page;
+  std::map<ulint, per_page_stats>::const_iterator it_page = index.leaves.find(page_no);
+  printf("\nindex: %llu leaf page stats: n_pages = %llu\n",
+         id, index.leaf_pages);
+  printf("page_no\tdata_size\tn_recs\n");
+  while (it_page != index.leaves.end()) {
+    const per_page_stats& stat = it_page->second;
+    printf("%lu\t%lu\t%lu\n", it_page->first, stat.data_size, stat.n_recs);
+    page_no = stat.right_page_no;
+    it_page = index.leaves.find(page_no);
+  }
+}
+
+void defrag_analysis(unsigned long long id, const per_index_stats& index)
+{
+  // TODO: make it work for compressed pages too
+  std::map<ulint, per_page_stats>::const_iterator it = index.leaves.find(index.first_leaf_page);
+  ulint n_pages = 0;
+  ulint n_leaf_pages = 0;
+  while (it != index.leaves.end()) {
+    ulint data_size_total = 0;
+    for (ulong i = 0; i < n_merge; i++) {
+      const per_page_stats& stat = it->second;
+      n_leaf_pages ++;
+      data_size_total += stat.data_size;
+      it = index.leaves.find(stat.right_page_no);
+      if (it == index.leaves.end()) {
+        break;
+      }
+    }
+    if (index.max_data_size) {
+      n_pages += data_size_total / index.max_data_size;
+      if (data_size_total % index.max_data_size != 0) {
+        n_pages += 1;
+      }
+    }
+  }
+  if (index.leaf_pages)
+    printf("count = %lu free = %lu\n", index.count, index.free_pages);
+    printf("%llu\t\t%llu\t\t%lu\t\t%lu\t\t%lu\t\t%.2f\t%lu\n",
+           id, index.leaf_pages, n_leaf_pages, n_merge, n_pages,
+           1.0 - (double)n_pages / (double)n_leaf_pages, index.max_data_size);
+}
+
+void print_leaf_stats()
+{
+  printf("\n**************************************************\n");
+  printf("index_id\t#leaf_pages\t#actual_leaf_pages\tn_merge\t"
+         "#leaf_after_merge\tdefrag\n");
+  for (std::map<unsigned long long, per_index_stats>::const_iterator it = index_ids.begin(); it != index_ids.end(); it++) {
+    const per_index_stats& index = it->second;
+    if (verbose) {
+      print_index_leaf_stats(it->first, index);
+    }
+    if (n_merge) {
+      defrag_analysis(it->first, index);
+    }
+  }
+}
+
+void
+print_stats()
+/*========*/
+{
+       unsigned long long i;
+
+       printf("%d\tbad checksum\n", n_bad_checksum);
+       printf("%d\tFIL_PAGE_INDEX\n", n_fil_page_index);
+       printf("%d\tFIL_PAGE_UNDO_LOG\n", n_fil_page_undo_log);
+       printf("%d\tFIL_PAGE_INODE\n", n_fil_page_inode);
+       printf("%d\tFIL_PAGE_IBUF_FREE_LIST\n", n_fil_page_ibuf_free_list);
+       printf("%d\tFIL_PAGE_TYPE_ALLOCATED\n", n_fil_page_type_allocated);
+       printf("%d\tFIL_PAGE_IBUF_BITMAP\n", n_fil_page_ibuf_bitmap);
+       printf("%d\tFIL_PAGE_TYPE_SYS\n", n_fil_page_type_sys);
+       printf("%d\tFIL_PAGE_TYPE_TRX_SYS\n", n_fil_page_type_trx_sys);
+       printf("%d\tFIL_PAGE_TYPE_FSP_HDR\n", n_fil_page_type_fsp_hdr);
+       printf("%d\tFIL_PAGE_TYPE_XDES\n", n_fil_page_type_xdes);
+       printf("%d\tFIL_PAGE_TYPE_BLOB\n", n_fil_page_type_blob);
+       printf("%d\tFIL_PAGE_TYPE_ZBLOB\n", n_fil_page_type_zblob);
+       printf("%d\tother\n", n_fil_page_type_other);
+       printf("%d\tmax index_id\n", n_fil_page_max_index_id);
+       printf("undo type: %d insert, %d update, %d other\n",
+               n_undo_insert, n_undo_update, n_undo_other);
+       printf("undo state: %d active, %d cached, %d to_free, %d to_purge,"
+               " %d prepared, %d other\n", n_undo_state_active,
+               n_undo_state_cached, n_undo_state_to_free,
+               n_undo_state_to_purge, n_undo_state_prepared,
+               n_undo_state_other);
+
+       printf("index_id\t#pages\t\t#leaf_pages\t#recs_per_page"
+               "\t#bytes_per_page\n");
+       for (std::map<unsigned long long, per_index_stats>::const_iterator it = index_ids.begin(); it != index_ids.end(); it++) {
+         const per_index_stats& index = it->second;
+         printf("%lld\t\t%lld\t\t%lld\t\t%lld\t\t%lld\n",
+                it->first, index.pages, index.leaf_pages,
+                index.total_n_recs / index.pages,
+                index.total_data_bytes / index.pages);
+       }
+       printf("\n");
+       printf("index_id\tpage_data_bytes_histgram(empty,...,oversized)\n");
+       for (std::map<unsigned long long, per_index_stats>::const_iterator it = index_ids.begin(); it != index_ids.end(); it++) {
+         printf("%lld\t", it->first);
+         const per_index_stats& index = it->second;
+         for (i = 0; i < SIZE_RANGES_FOR_PAGE+2; i++) {
+           printf("\t%lld", index.pages_in_size_range[i]);
+         }
+         printf("\n");
+       }
+       if (do_leaf) {
+         print_leaf_stats();
+       }
+}
+
 int main(int argc, char **argv)
 {
   FILE* f;                       /* our input file */
   char* filename;                /* our input filename. */
   unsigned char *big_buf, *buf;
-
+  unsigned char *big_xdes, *xdes;
   ulong bytes;                   /* bytes read count */
   ulint ct;                      /* current page number (0 based) */
   time_t now;                    /* current time */
@@ -297,6 +705,19 @@ int main(int argc, char **argv)
   buf = (unsigned char*)ut_align_down(big_buf
                                       + UNIV_PAGE_SIZE_MAX, UNIV_PAGE_SIZE_MAX);
 
+  big_xdes = (unsigned char *)malloc(2 * UNIV_PAGE_SIZE_MAX);
+  if (big_xdes == NULL)
+  {
+    fprintf(stderr, "Error; failed to allocate memory\n");
+    perror("");
+    return 1;
+  }
+
+  /* Make sure the page is aligned */
+  xdes = (unsigned char*)ut_align_down(big_xdes
+                                      + UNIV_PAGE_SIZE_MAX, UNIV_PAGE_SIZE_MAX);
+
+
   if (!get_page_size(f, buf, &logical_page_size, &physical_page_size))
   {
     free(big_buf);
@@ -349,6 +770,7 @@ int main(int argc, char **argv)
     {
       perror("Error; Unable to obtain file descriptor number");
       free(big_buf);
+      free(big_xdes);
       return 1;
     }
 
@@ -358,6 +780,7 @@ int main(int argc, char **argv)
     {
       perror("Error; Unable to seek to necessary offset");
       free(big_buf);
+      free(big_xdes);
       return 1;
     }
   }
@@ -367,10 +790,13 @@ int main(int argc, char **argv)
   lastt= 0;
   while (!feof(f))
   {
+    int page_ok = 1;
     bytes= fread(buf, 1, physical_page_size, f);
     if (!bytes && feof(f))
     {
+      print_stats();
       free(big_buf);
+      free(big_xdes);
       return 0;
     }
 
@@ -379,6 +805,7 @@ int main(int argc, char **argv)
       fprintf(stderr, "Error reading %lu bytes", physical_page_size);
       perror(" ");
       free(big_buf);
+      free(big_xdes);
       return 1;
     }
 
@@ -389,8 +816,10 @@ int main(int argc, char **argv)
         if (!skip_corrupt)
         {
           free(big_buf);
+	  free(big_xdes);
           return 1;
         }
+        page_ok = 0;
       }
     } else {
 
@@ -405,8 +834,10 @@ int main(int argc, char **argv)
         if (!skip_corrupt)
         {
           free(big_buf);
+	  free(big_xdes);
           return 1;
         }
+        page_ok = 0;
       }
 
       /* check old method of checksumming */
@@ -420,8 +851,10 @@ int main(int argc, char **argv)
         if (!skip_corrupt)
         {
           free(big_buf);
+	  free(big_xdes);
           return 1;
         }
+        page_ok = 0;
       }
 
       /* now check the new method */
@@ -437,19 +870,41 @@ int main(int argc, char **argv)
         if (!skip_corrupt)
         {
           free(big_buf);
+	  free(big_xdes);
           return 1;
         }
+        page_ok = 0;
       }
     }
     /* end if this was the last page we were supposed to check */
     if (use_end_page && (ct >= end_page))
     {
+      print_stats();
       free(big_buf);
+      free(big_xdes);
       return 0;
     }
 
+    if (per_page_details)
+    {
+      printf("page %ld ", ct);
+    }
+
     /* do counter increase and progress printing */
     ct++;
+
+    if (!page_ok)
+    {
+      if (per_page_details)
+      {
+        printf("BAD_CHECKSUM\n");
+      }
+      n_bad_checksum++;
+      continue;
+    }
+
+    parse_page(buf, xdes);
+
     if (verbose)
     {
       if (ct % 64 == 0)
@@ -464,6 +919,8 @@ int main(int argc, char **argv)
       }
     }
   }
+  print_stats();
   free(big_buf);
+  free(big_xdes);
   return 0;
 }