src/parse-extent-tree.awk

   1 # SPDX-License-Identifier: GPL-2.0
   2 # Copyright (c) 2019 Nikolay Borisov, SUSE LLC.  All Rights Reserved.
   3 #
   4 # Parses btrfs' extent tree for holes. Holes are the ranges between 2 adjacent
   5 # extent blocks. For example if we have the following 2 metadata items in the
   6 # extent tree:
   7 #       item 6 key (30425088 METADATA_ITEM 0) itemoff 16019 itemsize 33
   8 #       item 7 key (30490624 METADATA_ITEM 0) itemoff 15986 itemsize 33
   9 #
  10 # There is a whole of 64k between then - 30490624−30425088 = 65536
  11 # Same logic applies for adjacent EXTENT_ITEMS.
  12 #
  13 # The script requires the following parameters passed on command line:
  14 #     * sectorsize - how many bytes per sector, used to convert the output of
  15 #     the script to sectors.
  16 #     * nodesize - size of metadata extents, used for internal calculations
  17
  18 # Given an extent line "item 2 key (13672448 EXTENT_ITEM 65536) itemoff 16153 itemsize 53"
  19 # or "item 6 key (30425088 METADATA_ITEM 0) itemoff 16019 itemsize 33" returns
  20 # either 65536 (for data extents) or the fixes nodesize value for metadata
  21 # extents.
  22 function get_extent_size(line, tmp) {
  23         if (line ~ data_match || line ~ bg_match) {
  24                 split(line, tmp)
  25                 gsub(/\)/,"", tmp[6])
  26                 return tmp[6]
  27         } else if (line ~ metadata_match) {
  28                 return nodesize
  29         }
  30 }
  31
  32 # given a 'item 2 key (13672448 EXTENT_ITEM 65536) itemoff 16153 itemsize 53'
  33 # and returns 13672448.
  34 function get_extent_offset(line, tmp) {
  35         split(line, tmp)
  36         gsub(/\(/,"",tmp[4])
  37         return tmp[4]
  38 }
  39
  40 # This function parses all the extents belonging to a particular block group
  41 # which are accumulated in lines[] and calculates the offsets of the holes
  42 # part of this block group.
  43 #
  44 # base_offset and bg_line are local variables
  45 function print_array(base_offset, bg_line)
  46 {
  47         if (match(lines[0], bg_match)) {
  48                 # we don't have an extent at the beginning of of blockgroup, so we
  49                 # have a hole between blockgroup offset and first extent offset
  50                 bg_line = lines[0]
  51                 prev_size=0
  52                 prev_offset=get_extent_offset(bg_line)
  53                 delete lines[0]
  54         } else {
  55                 # we have an extent at the beginning of block group, so initialize
  56                 # the prev_* vars correctly
  57                 bg_line = lines[1]
  58                 prev_size = get_extent_size(lines[0])
  59                 prev_offset = get_extent_offset(lines[0])
  60                 delete lines[1]
  61                 delete lines[0]
  62         }
  63
  64         bg_offset=get_extent_offset(bg_line)
  65         bgend=bg_offset + get_extent_size(bg_line)
  66
  67         for (i in lines) {
  68                         cur_size = get_extent_size(lines[i])
  69                         cur_offset = get_extent_offset(lines[i])
  70                         if (cur_offset  != prev_offset + prev_size)
  71                                 print int((prev_size + prev_offset) / sectorsize), int((cur_offset-1) / sectorsize)
  72                         prev_size = cur_size
  73                         prev_offset = cur_offset
  74         }
  75
  76         print int((prev_size + prev_offset) / sectorsize), int((bgend-1) / sectorsize)
  77         total_printed++
  78         delete lines
  79 }
  80
  81 BEGIN {
  82         loi_match="^.item [0-9]* key \\([0-9]* (BLOCK_GROUP_ITEM|METADATA_ITEM|EXTENT_ITEM) [0-9]*\\).*"
  83         metadata_match="^.item [0-9]* key \\([0-9]* METADATA_ITEM [0-9]*\\).*"
  84         data_match="^.item [0-9]* key \\([0-9]* EXTENT_ITEM [0-9]*\\).*"
  85         bg_match="^.item [0-9]* key \\([0-9]* BLOCK_GROUP_ITEM [0-9]*\\).*"
  86         node_match="^node.*$"
  87         leaf_match="^leaf [0-9]* flags"
  88         line_count=0
  89         total_printed=0
  90         skip_lines=0
  91 }
  92
  93 {
  94         # skip lines not belonging to a leaf
  95         if (match($0, node_match)) {
  96                 skip_lines=1
  97         } else if (match($0, leaf_match)) {
  98                 skip_lines=0
  99         }
 100
 101         if (!match($0, loi_match) || skip_lines == 1) next;
 102
 103         # we have a line of interest, we need to parse it. First check if there is
 104         # anything in the array
 105         if (line_count==0) {
 106                 lines[line_count++]=$0;
 107         } else {
 108                 prev_line=lines[line_count-1]
 109                 split(prev_line, prev_line_fields)
 110                 prev_objectid=prev_line_fields[4]
 111                 objectid=$4
 112
 113                 if (objectid == prev_objectid && match($0, bg_match)) {
 114                         if (total_printed>0) {
 115                                 # We are adding a BG after we have added its first extent
 116                                 # previously, consider this a record ending event and just print
 117                                 # the array
 118
 119                                 delete lines[line_count-1]
 120                                 print_array()
 121                                 # we now start a new array with current and previous lines
 122                                 line_count=0
 123                                 lines[line_count++]=prev_line
 124                                 lines[line_count++]=$0
 125                         } else {
 126                                 # first 2 added lines are EXTENT and BG that match, in this case
 127                                 # just add them
 128                                 lines[line_count++]=$0
 129
 130                         }
 131                 } else if (match($0, bg_match)) {
 132                         # ordinary end of record
 133                         print_array()
 134                         line_count=0
 135                         lines[line_count++]=$0
 136                 } else {
 137                         lines[line_count++]=$0
 138                 }
 139         }
 140 }
 141
 142 END {
 143         print_array()
 144 }